Index: llvm/lib/CodeGen/SelectionDAG/TargetLowering.cpp
===================================================================
--- llvm/lib/CodeGen/SelectionDAG/TargetLowering.cpp
+++ llvm/lib/CodeGen/SelectionDAG/TargetLowering.cpp
@@ -7835,6 +7835,44 @@
                        DAG.getNode(ISD::CTLZ, dl, VT, Tmp));
   }
 
+  if (NumBitsPerElt == 32 && !VT.isVector() && !isOperationLegal(ISD::CTPOP, VT)) {
+    APInt DeBruijn(32, 0x077CB531U);
+    APInt BitWidth(32, NumBitsPerElt);
+    APInt ShiftAmt(32, *(BitWidth - BitWidth.logBase2()).getRawData());
+    SDValue Neg = DAG.getNode(ISD::SUB, dl, VT, DAG.getConstant(0, dl, VT), Op);
+    SDValue Lookup = DAG.getNode(
+	ISD::SRL, dl, VT,
+	DAG.getNode(ISD::MUL, dl, VT, DAG.getNode(ISD::AND, dl, VT, Op, Neg),
+		    DAG.getConstant(*DeBruijn.getRawData(), dl, VT)),
+	DAG.getConstant(*ShiftAmt.getRawData(), dl, VT));
+
+    // Create a table in constant data pool
+    std::vector<Constant *> Elts;
+    SmallVector<uint8_t, 32> RshrArr;
+
+    for (unsigned int i = 0; i < NumBitsPerElt; i++) {
+      APInt Lshr(32, *DeBruijn.rotl(i).getRawData());
+      unsigned int Rshr = *Lshr.getRawData() >> *ShiftAmt.getRawData();
+      RshrArr[Rshr] = i;
+    }
+
+    for (unsigned int i = 0; i < NumBitsPerElt; i++) {
+      SDValue Index = DAG.getConstant(RshrArr[i], dl, VT);
+      ConstantSDNode *IndexNode = cast<ConstantSDNode>(Index);
+      ConstantInt *CI = const_cast<ConstantInt *>(IndexNode->getConstantIntValue());
+      Elts.push_back(CI);
+    }
+    const DataLayout &TD = DAG.getDataLayout();
+
+    // Create a ConstantArray of size NumBitsPerElt
+    auto *CA = ConstantArray::get(ArrayType::get(Elts[0]->getType(), NumBitsPerElt), Elts);
+    SDValue CPIdx = DAG.getConstantPool(CA, getPointerTy(TD),
+					TD.getPrefTypeAlign(Elts[0]->getType()));
+    Align Alignment = cast<ConstantPoolSDNode>(CPIdx)->getAlign();
+    return DAG.getLoad(VT, dl, DAG.getEntryNode(), DAG.getMemBasePlusOffset(CPIdx, Lookup, dl),
+                     MachinePointerInfo::getConstantPool(
+                         DAG.getMachineFunction()), Alignment);
+  }
   return DAG.getNode(ISD::CTPOP, dl, VT, Tmp);
 }
 
Index: llvm/test/CodeGen/RISCV/rv32zbb.ll
===================================================================
--- llvm/test/CodeGen/RISCV/rv32zbb.ll
+++ llvm/test/CodeGen/RISCV/rv32zbb.ll
@@ -176,29 +176,16 @@
 ; RV32I-NEXT:    sw ra, 12(sp) # 4-byte Folded Spill
 ; RV32I-NEXT:    beqz a0, .LBB2_2
 ; RV32I-NEXT:  # %bb.1: # %cond.false
-; RV32I-NEXT:    addi a1, a0, -1
-; RV32I-NEXT:    not a0, a0
-; RV32I-NEXT:    and a0, a0, a1
-; RV32I-NEXT:    srli a1, a0, 1
-; RV32I-NEXT:    lui a2, 349525
-; RV32I-NEXT:    addi a2, a2, 1365
-; RV32I-NEXT:    and a1, a1, a2
-; RV32I-NEXT:    sub a0, a0, a1
-; RV32I-NEXT:    lui a1, 209715
-; RV32I-NEXT:    addi a1, a1, 819
-; RV32I-NEXT:    and a2, a0, a1
-; RV32I-NEXT:    srli a0, a0, 2
+; RV32I-NEXT:    neg a1, a0
 ; RV32I-NEXT:    and a0, a0, a1
-; RV32I-NEXT:    add a0, a2, a0
-; RV32I-NEXT:    srli a1, a0, 4
-; RV32I-NEXT:    add a0, a0, a1
-; RV32I-NEXT:    lui a1, 61681
-; RV32I-NEXT:    addi a1, a1, -241
-; RV32I-NEXT:    and a0, a0, a1
-; RV32I-NEXT:    lui a1, 4112
-; RV32I-NEXT:    addi a1, a1, 257
+; RV32I-NEXT:    lui a1, 30667
+; RV32I-NEXT:    addi a1, a1, 1329
 ; RV32I-NEXT:    call __mulsi3@plt
-; RV32I-NEXT:    srli a0, a0, 24
+; RV32I-NEXT:    srli a0, a0, 27
+; RV32I-NEXT:    lui a1, %hi(.LCPI2_0)
+; RV32I-NEXT:    addi a1, a1, %lo(.LCPI2_0)
+; RV32I-NEXT:    add a0, a1, a0
+; RV32I-NEXT:    lw a0, 0(a0)
 ; RV32I-NEXT:    j .LBB2_3
 ; RV32I-NEXT:  .LBB2_2:
 ; RV32I-NEXT:    li a0, 32
@@ -227,56 +214,32 @@
 ; RV32I-NEXT:    sw s2, 16(sp) # 4-byte Folded Spill
 ; RV32I-NEXT:    sw s3, 12(sp) # 4-byte Folded Spill
 ; RV32I-NEXT:    sw s4, 8(sp) # 4-byte Folded Spill
-; RV32I-NEXT:    sw s5, 4(sp) # 4-byte Folded Spill
-; RV32I-NEXT:    sw s6, 0(sp) # 4-byte Folded Spill
 ; RV32I-NEXT:    mv s1, a1
 ; RV32I-NEXT:    mv s2, a0
-; RV32I-NEXT:    addi a0, a0, -1
-; RV32I-NEXT:    not a1, s2
-; RV32I-NEXT:    and a0, a1, a0
-; RV32I-NEXT:    srli a1, a0, 1
-; RV32I-NEXT:    lui a2, 349525
-; RV32I-NEXT:    addi s4, a2, 1365
-; RV32I-NEXT:    and a1, a1, s4
-; RV32I-NEXT:    sub a0, a0, a1
-; RV32I-NEXT:    lui a1, 209715
-; RV32I-NEXT:    addi s5, a1, 819
-; RV32I-NEXT:    and a1, a0, s5
-; RV32I-NEXT:    srli a0, a0, 2
-; RV32I-NEXT:    and a0, a0, s5
-; RV32I-NEXT:    add a0, a1, a0
-; RV32I-NEXT:    srli a1, a0, 4
-; RV32I-NEXT:    add a0, a0, a1
-; RV32I-NEXT:    lui a1, 61681
-; RV32I-NEXT:    addi s6, a1, -241
-; RV32I-NEXT:    and a0, a0, s6
-; RV32I-NEXT:    lui a1, 4112
-; RV32I-NEXT:    addi s3, a1, 257
+; RV32I-NEXT:    neg a0, a0
+; RV32I-NEXT:    and a0, s2, a0
+; RV32I-NEXT:    lui a1, 30667
+; RV32I-NEXT:    addi s3, a1, 1329
 ; RV32I-NEXT:    mv a1, s3
 ; RV32I-NEXT:    call __mulsi3@plt
 ; RV32I-NEXT:    mv s0, a0
-; RV32I-NEXT:    addi a0, s1, -1
-; RV32I-NEXT:    not a1, s1
-; RV32I-NEXT:    and a0, a1, a0
-; RV32I-NEXT:    srli a1, a0, 1
-; RV32I-NEXT:    and a1, a1, s4
-; RV32I-NEXT:    sub a0, a0, a1
-; RV32I-NEXT:    and a1, a0, s5
-; RV32I-NEXT:    srli a0, a0, 2
-; RV32I-NEXT:    and a0, a0, s5
-; RV32I-NEXT:    add a0, a1, a0
-; RV32I-NEXT:    srli a1, a0, 4
-; RV32I-NEXT:    add a0, a0, a1
-; RV32I-NEXT:    and a0, a0, s6
+; RV32I-NEXT:    lui a0, %hi(.LCPI3_0)
+; RV32I-NEXT:    addi s4, a0, %lo(.LCPI3_0)
+; RV32I-NEXT:    neg a0, s1
+; RV32I-NEXT:    and a0, s1, a0
 ; RV32I-NEXT:    mv a1, s3
 ; RV32I-NEXT:    call __mulsi3@plt
 ; RV32I-NEXT:    bnez s2, .LBB3_2
 ; RV32I-NEXT:  # %bb.1:
-; RV32I-NEXT:    srli a0, a0, 24
+; RV32I-NEXT:    srli a0, a0, 27
+; RV32I-NEXT:    add a0, s4, a0
+; RV32I-NEXT:    lw a0, 0(a0)
 ; RV32I-NEXT:    addi a0, a0, 32
 ; RV32I-NEXT:    j .LBB3_3
 ; RV32I-NEXT:  .LBB3_2:
-; RV32I-NEXT:    srli a0, s0, 24
+; RV32I-NEXT:    srli a0, s0, 27
+; RV32I-NEXT:    add a0, s4, a0
+; RV32I-NEXT:    lw a0, 0(a0)
 ; RV32I-NEXT:  .LBB3_3:
 ; RV32I-NEXT:    li a1, 0
 ; RV32I-NEXT:    lw ra, 28(sp) # 4-byte Folded Reload
@@ -285,8 +248,6 @@
 ; RV32I-NEXT:    lw s2, 16(sp) # 4-byte Folded Reload
 ; RV32I-NEXT:    lw s3, 12(sp) # 4-byte Folded Reload
 ; RV32I-NEXT:    lw s4, 8(sp) # 4-byte Folded Reload
-; RV32I-NEXT:    lw s5, 4(sp) # 4-byte Folded Reload
-; RV32I-NEXT:    lw s6, 0(sp) # 4-byte Folded Reload
 ; RV32I-NEXT:    addi sp, sp, 32
 ; RV32I-NEXT:    ret
 ;
Index: llvm/test/CodeGen/SPARC/cttz.ll
===================================================================
--- /dev/null
+++ llvm/test/CodeGen/SPARC/cttz.ll
@@ -0,0 +1,36 @@
+; NOTE: Assertions have been autogenerated by utils/update_llc_test_checks.py
+; RUN: llc < %s -march=sparc -mcpu=v9 | FileCheck %s
+
+@f.table = internal unnamed_addr constant [32 x i8] c"\00\01\1C\02\1D\0E\18\03\1E\16\14\0F\19\11\04\08\1F\1B\0D\17\15\13\10\07\1A\0C\12\06\0B\05\0A\09", align 1
+
+define i32 @f(i32 %x) {
+; CHECK-LABEL: f:
+; CHECK:         .cfi_startproc
+; CHECK-NEXT:  ! %bb.0: ! %entry
+; CHECK-NEXT:    mov %g0, %o1
+; CHECK-NEXT:    sub %o1, %o0, %o1
+; CHECK-NEXT:    and %o0, %o1, %o1
+; CHECK-NEXT:    sethi 122669, %o2
+; CHECK-NEXT:    or %o2, 305, %o2
+; CHECK-NEXT:    smul %o1, %o2, %o1
+; CHECK-NEXT:    srl %o1, 27, %o1
+; CHECK-NEXT:    sethi %hi(.LCPI0_0), %o2
+; CHECK-NEXT:    add %o2, %lo(.LCPI0_0), %o2
+; CHECK-NEXT:    ld [%o2+%o1], %o1
+; CHECK-NEXT:    cmp %o0, 0
+; CHECK-NEXT:    move %icc, 0, %o1
+; CHECK-NEXT:    retl
+; CHECK-NEXT:    mov %o1, %o0
+entry:
+  %0 = call i32 @llvm.cttz.i32(i32 %x, i1 true)
+  %1 = icmp eq i32 %x, 0
+  %2 = select i1 %1, i32 0, i32 %0
+  %3 = trunc i32 %2 to i8
+  %conv = zext i8 %3 to i32
+  ret i32 %conv
+}
+
+; Function Attrs: nocallback nofree nosync nounwind readnone speculatable willreturn
+declare i32 @llvm.cttz.i32(i32, i1 immarg) #0
+
+attributes #0 = { nocallback nofree nosync nounwind readnone speculatable willreturn }
Index: llvm/test/CodeGen/VE/Scalar/cttz.ll
===================================================================
--- llvm/test/CodeGen/VE/Scalar/cttz.ll
+++ llvm/test/CodeGen/VE/Scalar/cttz.ll
@@ -1,3 +1,4 @@
+; NOTE: Assertions have been autogenerated by utils/update_llc_test_checks.py
 ; RUN: llc < %s -mtriple=ve-unknown-unknown | FileCheck %s
 
 declare i128 @llvm.cttz.i128(i128, i1)
@@ -38,10 +39,17 @@
 define signext i32 @func32s(i32 signext %p) {
 ; CHECK-LABEL: func32s:
 ; CHECK:       # %bb.0:
-; CHECK-NEXT:    adds.w.sx %s1, -1, %s0
-; CHECK-NEXT:    nnd %s0, %s0, %s1
+; CHECK-NEXT:    subs.w.sx %s1, 0, %s0
+; CHECK-NEXT:    and %s0, %s0, %s1
+; CHECK-NEXT:    lea %s1, 125613361
+; CHECK-NEXT:    muls.w.sx %s0, %s0, %s1
 ; CHECK-NEXT:    and %s0, %s0, (32)0
-; CHECK-NEXT:    pcnt %s0, %s0
+; CHECK-NEXT:    srl %s0, %s0, 27
+; CHECK-NEXT:    lea %s1, .LCPI2_0@lo
+; CHECK-NEXT:    and %s1, %s1, (32)0
+; CHECK-NEXT:    lea.sl %s1, .LCPI2_0@hi(, %s1)
+; CHECK-NEXT:    or %s0, 0, %s0
+; CHECK-NEXT:    ldl.zx %s0, (%s0, %s1)
 ; CHECK-NEXT:    b.l.t (, %s10)
   %r = tail call i32 @llvm.cttz.i32(i32 %p, i1 true)
   ret i32 %r
@@ -50,10 +58,17 @@
 define zeroext i32 @func32z(i32 zeroext %p) {
 ; CHECK-LABEL: func32z:
 ; CHECK:       # %bb.0:
-; CHECK-NEXT:    adds.w.sx %s1, -1, %s0
-; CHECK-NEXT:    nnd %s0, %s0, %s1
+; CHECK-NEXT:    subs.w.sx %s1, 0, %s0
+; CHECK-NEXT:    and %s0, %s0, %s1
+; CHECK-NEXT:    lea %s1, 125613361
+; CHECK-NEXT:    muls.w.sx %s0, %s0, %s1
 ; CHECK-NEXT:    and %s0, %s0, (32)0
-; CHECK-NEXT:    pcnt %s0, %s0
+; CHECK-NEXT:    srl %s0, %s0, 27
+; CHECK-NEXT:    lea %s1, .LCPI3_0@lo
+; CHECK-NEXT:    and %s1, %s1, (32)0
+; CHECK-NEXT:    lea.sl %s1, .LCPI3_0@hi(, %s1)
+; CHECK-NEXT:    or %s0, 0, %s0
+; CHECK-NEXT:    ldl.zx %s0, (%s0, %s1)
 ; CHECK-NEXT:    b.l.t (, %s10)
   %r = tail call i32 @llvm.cttz.i32(i32 %p, i1 true)
   ret i32 %r