Index: llvm/include/llvm/CodeGen/TargetLowering.h
===================================================================
--- llvm/include/llvm/CodeGen/TargetLowering.h
+++ llvm/include/llvm/CodeGen/TargetLowering.h
@@ -4755,6 +4755,12 @@
   /// \returns The expansion result or SDValue() if it fails.
   SDValue expandCTLZ(SDNode *N, SelectionDAG &DAG) const;
 
+  /// Emit Table Lookup if ISD::CTLZ and ISD::CTPOP are not legal.
+  /// \param N Node to expand
+  /// \returns Reference to table generated in Constant Pool.
+  SDValue CTTZTableLookup(SDNode *N, SelectionDAG &DAG, SDLoc dl, EVT VT,
+                          SDValue Op, unsigned NumBitsPerElt) const;
+
   /// Expand CTTZ/CTTZ_ZERO_UNDEF nodes. Expands vector/scalar CTTZ nodes,
   /// vector nodes can only succeed if all operations are legal/custom.
   /// \param N Node to expand
Index: llvm/lib/CodeGen/SelectionDAG/TargetLowering.cpp
===================================================================
--- llvm/lib/CodeGen/SelectionDAG/TargetLowering.cpp
+++ llvm/lib/CodeGen/SelectionDAG/TargetLowering.cpp
@@ -7954,11 +7954,56 @@
   return DAG.getNode(ISD::CTPOP, dl, VT, Op);
 }
 
+SDValue TargetLowering::CTTZTableLookup(SDNode *Node, SelectionDAG &DAG,
+                                        SDLoc dl, EVT VT, SDValue Op,
+                                        unsigned BitWidth) const {
+  APInt DeBruijn = BitWidth == 32 ? APInt(32, 0x077CB531U)
+                                  : APInt(64, 0x0218A392CD3D5DBFULL);
+  const DataLayout &TD = DAG.getDataLayout();
+  MachinePointerInfo PtrInfo = MachinePointerInfo::getConstantPool(DAG.getMachineFunction());
+  unsigned ShiftAmt = BitWidth - Log2_32(BitWidth);
+  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.getZExtValue(), dl, VT)),
+      DAG.getShiftAmountConstant(ShiftAmt, VT, dl));
+  Lookup = DAG.getSExtOrTrunc(Lookup, dl, VT);
+
+  SmallVector<uint8_t> Table(BitWidth, 0);
+  for (unsigned i = 0; i < BitWidth; i++) {
+    APInt Shl = DeBruijn.shl(i);
+    APInt Lshr = Shl.lshr(ShiftAmt);
+    Table[Lshr.getZExtValue()] = i;
+  }
+
+  // Create a ConstantArray in Constant Pool
+  auto *CA = ConstantDataArray::get(*DAG.getContext(), Table);
+  SDValue CPIdx = DAG.getConstantPool(
+      CA, getPointerTy(TD),
+      TD.getPrefTypeAlign(VT.getTypeForEVT(*DAG.getContext())));
+  Align Alignment = cast<ConstantPoolSDNode>(CPIdx)->getAlign();
+  SDValue Load = DAG.getLoad(
+      VT, dl, DAG.getEntryNode(),
+      DAG.getMemBasePlusOffset(CPIdx, Lookup, dl), PtrInfo, Alignment);
+  SDValue ZExtOrTrunc = DAG.getZExtOrTrunc(Load, dl, VT);
+  if (isTypeLegal(VT))
+    return ZExtOrTrunc;
+  else {
+    LoadSDNode *LD = cast<LoadSDNode>(ZExtOrTrunc);
+    return DAG.getExtLoad(
+        ISD::ZEXTLOAD, dl, VT, DAG.getEntryNode(),
+        DAG.getMemBasePlusOffset(CPIdx, Lookup, dl), PtrInfo, VT,
+        Alignment, LD->getMemOperand()->getFlags(), LD->getAAInfo());
+  }
+}
+
 SDValue TargetLowering::expandCTTZ(SDNode *Node, SelectionDAG &DAG) const {
   SDLoc dl(Node);
   EVT VT = Node->getValueType(0);
   SDValue Op = Node->getOperand(0);
   unsigned NumBitsPerElt = VT.getScalarSizeInBits();
+  const TargetLowering &TLI = DAG.getTargetLoweringInfo();
 
   // If the non-ZERO_UNDEF version is supported we can use that instead.
   if (Node->getOpcode() == ISD::CTTZ_ZERO_UNDEF &&
@@ -7987,6 +8032,11 @@
                         !isOperationLegalOrCustomOrPromote(ISD::XOR, VT)))
     return SDValue();
 
+  // Emit Table Lookup if ISD::CTLZ and ISD::CTPOP are not legal.
+  if (!VT.isVector() && TLI.isOperationExpand(ISD::CTPOP, VT) &&
+      !isOperationLegal(ISD::CTLZ, VT))
+    return CTTZTableLookup(Node, DAG, dl, VT, Op, NumBitsPerElt);
+
   // for now, we use: { return popcount(~x & (x - 1)); }
   // unless the target has ctlz but not ctpop, in which case we use:
   // { return 32 - nlz(~x & (x-1)); }
Index: llvm/test/CodeGen/ARM/cttz.ll
===================================================================
--- llvm/test/CodeGen/ARM/cttz.ll
+++ llvm/test/CodeGen/ARM/cttz.ll
@@ -25,24 +25,13 @@
 ; CHECK-THUMB-NEXT:    lsls r1, r0, #24
 ; CHECK-THUMB-NEXT:    beq .LBB0_2
 ; CHECK-THUMB-NEXT:  @ %bb.1: @ %cond.false
-; CHECK-THUMB-NEXT:    subs r1, r0, #1
-; CHECK-THUMB-NEXT:    bics r1, r0
-; CHECK-THUMB-NEXT:    lsrs r0, r1, #1
-; CHECK-THUMB-NEXT:    ldr r2, .LCPI0_0
-; CHECK-THUMB-NEXT:    ands r2, r0
-; CHECK-THUMB-NEXT:    subs r0, r1, r2
-; CHECK-THUMB-NEXT:    ldr r1, .LCPI0_1
-; CHECK-THUMB-NEXT:    lsrs r2, r0, #2
-; CHECK-THUMB-NEXT:    ands r0, r1
-; CHECK-THUMB-NEXT:    ands r2, r1
-; CHECK-THUMB-NEXT:    adds r0, r0, r2
-; CHECK-THUMB-NEXT:    lsrs r1, r0, #4
-; CHECK-THUMB-NEXT:    adds r0, r0, r1
-; CHECK-THUMB-NEXT:    ldr r1, .LCPI0_2
+; CHECK-THUMB-NEXT:    rsbs r1, r0, #0
 ; CHECK-THUMB-NEXT:    ands r1, r0
-; CHECK-THUMB-NEXT:    ldr r0, .LCPI0_3
+; CHECK-THUMB-NEXT:    ldr r0, .LCPI0_0
 ; CHECK-THUMB-NEXT:    muls r0, r1, r0
-; CHECK-THUMB-NEXT:    lsrs r0, r0, #24
+; CHECK-THUMB-NEXT:    lsrs r0, r0, #27
+; CHECK-THUMB-NEXT:    adr r1, .LCPI0_1
+; CHECK-THUMB-NEXT:    ldr r0, [r1, r0]
 ; CHECK-THUMB-NEXT:    bx lr
 ; CHECK-THUMB-NEXT:  .LBB0_2:
 ; CHECK-THUMB-NEXT:    movs r0, #8
@@ -50,13 +39,9 @@
 ; CHECK-THUMB-NEXT:    .p2align 2
 ; CHECK-THUMB-NEXT:  @ %bb.3:
 ; CHECK-THUMB-NEXT:  .LCPI0_0:
-; CHECK-THUMB-NEXT:    .long 1431655765 @ 0x55555555
+; CHECK-THUMB-NEXT:    .long 125613361 @ 0x77cb531
 ; CHECK-THUMB-NEXT:  .LCPI0_1:
-; CHECK-THUMB-NEXT:    .long 858993459 @ 0x33333333
-; CHECK-THUMB-NEXT:  .LCPI0_2:
-; CHECK-THUMB-NEXT:    .long 252645135 @ 0xf0f0f0f
-; CHECK-THUMB-NEXT:  .LCPI0_3:
-; CHECK-THUMB-NEXT:    .long 16843009 @ 0x1010101
+; CHECK-THUMB-NEXT:    .ascii "\000\001\034\002\035\016\030\003\036\026\024\017\031\021\004\b\037\033\r\027\025\023\020\007\032\f\022\006\013\005\n\t"
   %tmp = call i8 @llvm.cttz.i8(i8 %a, i1 false)
   ret i8 %tmp
 }
@@ -74,24 +59,13 @@
 ; CHECK-THUMB-NEXT:    lsls r1, r0, #16
 ; CHECK-THUMB-NEXT:    beq .LBB1_2
 ; CHECK-THUMB-NEXT:  @ %bb.1: @ %cond.false
-; CHECK-THUMB-NEXT:    subs r1, r0, #1
-; CHECK-THUMB-NEXT:    bics r1, r0
-; CHECK-THUMB-NEXT:    lsrs r0, r1, #1
-; CHECK-THUMB-NEXT:    ldr r2, .LCPI1_0
-; CHECK-THUMB-NEXT:    ands r2, r0
-; CHECK-THUMB-NEXT:    subs r0, r1, r2
-; CHECK-THUMB-NEXT:    ldr r1, .LCPI1_1
-; CHECK-THUMB-NEXT:    lsrs r2, r0, #2
-; CHECK-THUMB-NEXT:    ands r0, r1
-; CHECK-THUMB-NEXT:    ands r2, r1
-; CHECK-THUMB-NEXT:    adds r0, r0, r2
-; CHECK-THUMB-NEXT:    lsrs r1, r0, #4
-; CHECK-THUMB-NEXT:    adds r0, r0, r1
-; CHECK-THUMB-NEXT:    ldr r1, .LCPI1_2
+; CHECK-THUMB-NEXT:    rsbs r1, r0, #0
 ; CHECK-THUMB-NEXT:    ands r1, r0
-; CHECK-THUMB-NEXT:    ldr r0, .LCPI1_3
+; CHECK-THUMB-NEXT:    ldr r0, .LCPI1_0
 ; CHECK-THUMB-NEXT:    muls r0, r1, r0
-; CHECK-THUMB-NEXT:    lsrs r0, r0, #24
+; CHECK-THUMB-NEXT:    lsrs r0, r0, #27
+; CHECK-THUMB-NEXT:    adr r1, .LCPI1_1
+; CHECK-THUMB-NEXT:    ldr r0, [r1, r0]
 ; CHECK-THUMB-NEXT:    bx lr
 ; CHECK-THUMB-NEXT:  .LBB1_2:
 ; CHECK-THUMB-NEXT:    movs r0, #16
@@ -99,13 +73,9 @@
 ; CHECK-THUMB-NEXT:    .p2align 2
 ; CHECK-THUMB-NEXT:  @ %bb.3:
 ; CHECK-THUMB-NEXT:  .LCPI1_0:
-; CHECK-THUMB-NEXT:    .long 1431655765 @ 0x55555555
+; CHECK-THUMB-NEXT:    .long 125613361 @ 0x77cb531
 ; CHECK-THUMB-NEXT:  .LCPI1_1:
-; CHECK-THUMB-NEXT:    .long 858993459 @ 0x33333333
-; CHECK-THUMB-NEXT:  .LCPI1_2:
-; CHECK-THUMB-NEXT:    .long 252645135 @ 0xf0f0f0f
-; CHECK-THUMB-NEXT:  .LCPI1_3:
-; CHECK-THUMB-NEXT:    .long 16843009 @ 0x1010101
+; CHECK-THUMB-NEXT:    .ascii "\000\001\034\002\035\016\030\003\036\026\024\017\031\021\004\b\037\033\r\027\025\023\020\007\032\f\022\006\013\005\n\t"
   %tmp = call i16 @llvm.cttz.i16(i16 %a, i1 false)
   ret i16 %tmp
 }
@@ -122,24 +92,13 @@
 ; CHECK-THUMB-NEXT:    cmp r0, #0
 ; CHECK-THUMB-NEXT:    beq .LBB2_2
 ; CHECK-THUMB-NEXT:  @ %bb.1: @ %cond.false
-; CHECK-THUMB-NEXT:    subs r1, r0, #1
-; CHECK-THUMB-NEXT:    bics r1, r0
-; CHECK-THUMB-NEXT:    lsrs r0, r1, #1
-; CHECK-THUMB-NEXT:    ldr r2, .LCPI2_0
-; CHECK-THUMB-NEXT:    ands r2, r0
-; CHECK-THUMB-NEXT:    subs r0, r1, r2
-; CHECK-THUMB-NEXT:    ldr r1, .LCPI2_1
-; CHECK-THUMB-NEXT:    lsrs r2, r0, #2
-; CHECK-THUMB-NEXT:    ands r0, r1
-; CHECK-THUMB-NEXT:    ands r2, r1
-; CHECK-THUMB-NEXT:    adds r0, r0, r2
-; CHECK-THUMB-NEXT:    lsrs r1, r0, #4
-; CHECK-THUMB-NEXT:    adds r0, r0, r1
-; CHECK-THUMB-NEXT:    ldr r1, .LCPI2_2
+; CHECK-THUMB-NEXT:    rsbs r1, r0, #0
 ; CHECK-THUMB-NEXT:    ands r1, r0
-; CHECK-THUMB-NEXT:    ldr r0, .LCPI2_3
+; CHECK-THUMB-NEXT:    ldr r0, .LCPI2_0
 ; CHECK-THUMB-NEXT:    muls r0, r1, r0
-; CHECK-THUMB-NEXT:    lsrs r0, r0, #24
+; CHECK-THUMB-NEXT:    lsrs r0, r0, #27
+; CHECK-THUMB-NEXT:    adr r1, .LCPI2_1
+; CHECK-THUMB-NEXT:    ldr r0, [r1, r0]
 ; CHECK-THUMB-NEXT:    bx lr
 ; CHECK-THUMB-NEXT:  .LBB2_2:
 ; CHECK-THUMB-NEXT:    movs r0, #32
@@ -147,13 +106,9 @@
 ; CHECK-THUMB-NEXT:    .p2align 2
 ; CHECK-THUMB-NEXT:  @ %bb.3:
 ; CHECK-THUMB-NEXT:  .LCPI2_0:
-; CHECK-THUMB-NEXT:    .long 1431655765 @ 0x55555555
+; CHECK-THUMB-NEXT:    .long 125613361 @ 0x77cb531
 ; CHECK-THUMB-NEXT:  .LCPI2_1:
-; CHECK-THUMB-NEXT:    .long 858993459 @ 0x33333333
-; CHECK-THUMB-NEXT:  .LCPI2_2:
-; CHECK-THUMB-NEXT:    .long 252645135 @ 0xf0f0f0f
-; CHECK-THUMB-NEXT:  .LCPI2_3:
-; CHECK-THUMB-NEXT:    .long 16843009 @ 0x1010101
+; CHECK-THUMB-NEXT:    .ascii "\000\001\034\002\035\016\030\003\036\026\024\017\031\021\004\b\037\033\r\027\025\023\020\007\032\f\022\006\013\005\n\t"
   %tmp = call i32 @llvm.cttz.i32(i32 %a, i1 false)
   ret i32 %tmp
 }
@@ -173,59 +128,33 @@
 ;
 ; CHECK-THUMB-LABEL: test_i64:
 ; CHECK-THUMB:       @ %bb.0:
-; CHECK-THUMB-NEXT:    .save {r4, r5, r7, lr}
-; CHECK-THUMB-NEXT:    push {r4, r5, r7, lr}
-; CHECK-THUMB-NEXT:    ldr r5, .LCPI3_0
-; CHECK-THUMB-NEXT:    ldr r4, .LCPI3_1
-; CHECK-THUMB-NEXT:    ldr r3, .LCPI3_2
-; CHECK-THUMB-NEXT:    ldr r2, .LCPI3_3
+; CHECK-THUMB-NEXT:    ldr r3, .LCPI3_0
+; CHECK-THUMB-NEXT:    adr r2, .LCPI3_1
 ; CHECK-THUMB-NEXT:    cmp r0, #0
 ; CHECK-THUMB-NEXT:    bne .LBB3_2
 ; CHECK-THUMB-NEXT:  @ %bb.1:
-; CHECK-THUMB-NEXT:    subs r0, r1, #1
-; CHECK-THUMB-NEXT:    bics r0, r1
-; CHECK-THUMB-NEXT:    lsrs r1, r0, #1
-; CHECK-THUMB-NEXT:    ands r1, r5
-; CHECK-THUMB-NEXT:    subs r0, r0, r1
-; CHECK-THUMB-NEXT:    lsrs r1, r0, #2
-; CHECK-THUMB-NEXT:    ands r0, r4
-; CHECK-THUMB-NEXT:    ands r1, r4
-; CHECK-THUMB-NEXT:    adds r0, r0, r1
-; CHECK-THUMB-NEXT:    lsrs r1, r0, #4
-; CHECK-THUMB-NEXT:    adds r0, r0, r1
-; CHECK-THUMB-NEXT:    ands r0, r3
-; CHECK-THUMB-NEXT:    muls r2, r0, r2
-; CHECK-THUMB-NEXT:    lsrs r0, r2, #24
+; CHECK-THUMB-NEXT:    rsbs r0, r1, #0
+; CHECK-THUMB-NEXT:    ands r0, r1
+; CHECK-THUMB-NEXT:    muls r3, r0, r3
+; CHECK-THUMB-NEXT:    lsrs r0, r3, #27
+; CHECK-THUMB-NEXT:    ldr r0, [r2, r0]
 ; CHECK-THUMB-NEXT:    adds r0, #32
 ; CHECK-THUMB-NEXT:    movs r1, #0
-; CHECK-THUMB-NEXT:    pop {r4, r5, r7, pc}
+; CHECK-THUMB-NEXT:    bx lr
 ; CHECK-THUMB-NEXT:  .LBB3_2:
-; CHECK-THUMB-NEXT:    subs r1, r0, #1
-; CHECK-THUMB-NEXT:    bics r1, r0
-; CHECK-THUMB-NEXT:    lsrs r0, r1, #1
-; CHECK-THUMB-NEXT:    ands r0, r5
-; CHECK-THUMB-NEXT:    subs r0, r1, r0
-; CHECK-THUMB-NEXT:    lsrs r1, r0, #2
-; CHECK-THUMB-NEXT:    ands r0, r4
-; CHECK-THUMB-NEXT:    ands r1, r4
-; CHECK-THUMB-NEXT:    adds r0, r0, r1
-; CHECK-THUMB-NEXT:    lsrs r1, r0, #4
-; CHECK-THUMB-NEXT:    adds r0, r0, r1
-; CHECK-THUMB-NEXT:    ands r0, r3
-; CHECK-THUMB-NEXT:    muls r2, r0, r2
-; CHECK-THUMB-NEXT:    lsrs r0, r2, #24
+; CHECK-THUMB-NEXT:    rsbs r1, r0, #0
+; CHECK-THUMB-NEXT:    ands r1, r0
+; CHECK-THUMB-NEXT:    muls r3, r1, r3
+; CHECK-THUMB-NEXT:    lsrs r0, r3, #27
+; CHECK-THUMB-NEXT:    ldr r0, [r2, r0]
 ; CHECK-THUMB-NEXT:    movs r1, #0
-; CHECK-THUMB-NEXT:    pop {r4, r5, r7, pc}
+; CHECK-THUMB-NEXT:    bx lr
 ; CHECK-THUMB-NEXT:    .p2align 2
 ; CHECK-THUMB-NEXT:  @ %bb.3:
 ; CHECK-THUMB-NEXT:  .LCPI3_0:
-; CHECK-THUMB-NEXT:    .long 1431655765 @ 0x55555555
+; CHECK-THUMB-NEXT:    .long 125613361 @ 0x77cb531
 ; CHECK-THUMB-NEXT:  .LCPI3_1:
-; CHECK-THUMB-NEXT:    .long 858993459 @ 0x33333333
-; CHECK-THUMB-NEXT:  .LCPI3_2:
-; CHECK-THUMB-NEXT:    .long 252645135 @ 0xf0f0f0f
-; CHECK-THUMB-NEXT:  .LCPI3_3:
-; CHECK-THUMB-NEXT:    .long 16843009 @ 0x1010101
+; CHECK-THUMB-NEXT:    .ascii "\000\001\034\002\035\016\030\003\036\026\024\017\031\021\004\b\037\033\r\027\025\023\020\007\032\f\022\006\013\005\n\t"
   %tmp = call i64 @llvm.cttz.i64(i64 %a, i1 false)
   ret i64 %tmp
 }
@@ -241,35 +170,20 @@
 ;
 ; CHECK-THUMB-LABEL: test_i8_zero_undef:
 ; CHECK-THUMB:       @ %bb.0:
-; CHECK-THUMB-NEXT:    subs r1, r0, #1
-; CHECK-THUMB-NEXT:    bics r1, r0
-; CHECK-THUMB-NEXT:    lsrs r0, r1, #1
-; CHECK-THUMB-NEXT:    ldr r2, .LCPI4_0
-; CHECK-THUMB-NEXT:    ands r2, r0
-; CHECK-THUMB-NEXT:    subs r0, r1, r2
-; CHECK-THUMB-NEXT:    ldr r1, .LCPI4_1
-; CHECK-THUMB-NEXT:    lsrs r2, r0, #2
-; CHECK-THUMB-NEXT:    ands r0, r1
-; CHECK-THUMB-NEXT:    ands r2, r1
-; CHECK-THUMB-NEXT:    adds r0, r0, r2
-; CHECK-THUMB-NEXT:    lsrs r1, r0, #4
-; CHECK-THUMB-NEXT:    adds r0, r0, r1
-; CHECK-THUMB-NEXT:    ldr r1, .LCPI4_2
+; CHECK-THUMB-NEXT:    rsbs r1, r0, #0
 ; CHECK-THUMB-NEXT:    ands r1, r0
-; CHECK-THUMB-NEXT:    ldr r0, .LCPI4_3
+; CHECK-THUMB-NEXT:    ldr r0, .LCPI4_0
 ; CHECK-THUMB-NEXT:    muls r0, r1, r0
-; CHECK-THUMB-NEXT:    lsrs r0, r0, #24
+; CHECK-THUMB-NEXT:    lsrs r0, r0, #27
+; CHECK-THUMB-NEXT:    adr r1, .LCPI4_1
+; CHECK-THUMB-NEXT:    ldr r0, [r1, r0]
 ; CHECK-THUMB-NEXT:    bx lr
 ; CHECK-THUMB-NEXT:    .p2align 2
 ; CHECK-THUMB-NEXT:  @ %bb.1:
 ; CHECK-THUMB-NEXT:  .LCPI4_0:
-; CHECK-THUMB-NEXT:    .long 1431655765 @ 0x55555555
+; CHECK-THUMB-NEXT:    .long 125613361 @ 0x77cb531
 ; CHECK-THUMB-NEXT:  .LCPI4_1:
-; CHECK-THUMB-NEXT:    .long 858993459 @ 0x33333333
-; CHECK-THUMB-NEXT:  .LCPI4_2:
-; CHECK-THUMB-NEXT:    .long 252645135 @ 0xf0f0f0f
-; CHECK-THUMB-NEXT:  .LCPI4_3:
-; CHECK-THUMB-NEXT:    .long 16843009 @ 0x1010101
+; CHECK-THUMB-NEXT:    .ascii "\000\001\034\002\035\016\030\003\036\026\024\017\031\021\004\b\037\033\r\027\025\023\020\007\032\f\022\006\013\005\n\t"
   %tmp = call i8 @llvm.cttz.i8(i8 %a, i1 true)
   ret i8 %tmp
 }
@@ -283,35 +197,20 @@
 ;
 ; CHECK-THUMB-LABEL: test_i16_zero_undef:
 ; CHECK-THUMB:       @ %bb.0:
-; CHECK-THUMB-NEXT:    subs r1, r0, #1
-; CHECK-THUMB-NEXT:    bics r1, r0
-; CHECK-THUMB-NEXT:    lsrs r0, r1, #1
-; CHECK-THUMB-NEXT:    ldr r2, .LCPI5_0
-; CHECK-THUMB-NEXT:    ands r2, r0
-; CHECK-THUMB-NEXT:    subs r0, r1, r2
-; CHECK-THUMB-NEXT:    ldr r1, .LCPI5_1
-; CHECK-THUMB-NEXT:    lsrs r2, r0, #2
-; CHECK-THUMB-NEXT:    ands r0, r1
-; CHECK-THUMB-NEXT:    ands r2, r1
-; CHECK-THUMB-NEXT:    adds r0, r0, r2
-; CHECK-THUMB-NEXT:    lsrs r1, r0, #4
-; CHECK-THUMB-NEXT:    adds r0, r0, r1
-; CHECK-THUMB-NEXT:    ldr r1, .LCPI5_2
+; CHECK-THUMB-NEXT:    rsbs r1, r0, #0
 ; CHECK-THUMB-NEXT:    ands r1, r0
-; CHECK-THUMB-NEXT:    ldr r0, .LCPI5_3
+; CHECK-THUMB-NEXT:    ldr r0, .LCPI5_0
 ; CHECK-THUMB-NEXT:    muls r0, r1, r0
-; CHECK-THUMB-NEXT:    lsrs r0, r0, #24
+; CHECK-THUMB-NEXT:    lsrs r0, r0, #27
+; CHECK-THUMB-NEXT:    adr r1, .LCPI5_1
+; CHECK-THUMB-NEXT:    ldr r0, [r1, r0]
 ; CHECK-THUMB-NEXT:    bx lr
 ; CHECK-THUMB-NEXT:    .p2align 2
 ; CHECK-THUMB-NEXT:  @ %bb.1:
 ; CHECK-THUMB-NEXT:  .LCPI5_0:
-; CHECK-THUMB-NEXT:    .long 1431655765 @ 0x55555555
+; CHECK-THUMB-NEXT:    .long 125613361 @ 0x77cb531
 ; CHECK-THUMB-NEXT:  .LCPI5_1:
-; CHECK-THUMB-NEXT:    .long 858993459 @ 0x33333333
-; CHECK-THUMB-NEXT:  .LCPI5_2:
-; CHECK-THUMB-NEXT:    .long 252645135 @ 0xf0f0f0f
-; CHECK-THUMB-NEXT:  .LCPI5_3:
-; CHECK-THUMB-NEXT:    .long 16843009 @ 0x1010101
+; CHECK-THUMB-NEXT:    .ascii "\000\001\034\002\035\016\030\003\036\026\024\017\031\021\004\b\037\033\r\027\025\023\020\007\032\f\022\006\013\005\n\t"
   %tmp = call i16 @llvm.cttz.i16(i16 %a, i1 true)
   ret i16 %tmp
 }
@@ -326,35 +225,20 @@
 ;
 ; CHECK-THUMB-LABEL: test_i32_zero_undef:
 ; CHECK-THUMB:       @ %bb.0:
-; CHECK-THUMB-NEXT:    subs r1, r0, #1
-; CHECK-THUMB-NEXT:    bics r1, r0
-; CHECK-THUMB-NEXT:    lsrs r0, r1, #1
-; CHECK-THUMB-NEXT:    ldr r2, .LCPI6_0
-; CHECK-THUMB-NEXT:    ands r2, r0
-; CHECK-THUMB-NEXT:    subs r0, r1, r2
-; CHECK-THUMB-NEXT:    ldr r1, .LCPI6_1
-; CHECK-THUMB-NEXT:    lsrs r2, r0, #2
-; CHECK-THUMB-NEXT:    ands r0, r1
-; CHECK-THUMB-NEXT:    ands r2, r1
-; CHECK-THUMB-NEXT:    adds r0, r0, r2
-; CHECK-THUMB-NEXT:    lsrs r1, r0, #4
-; CHECK-THUMB-NEXT:    adds r0, r0, r1
-; CHECK-THUMB-NEXT:    ldr r1, .LCPI6_2
+; CHECK-THUMB-NEXT:    rsbs r1, r0, #0
 ; CHECK-THUMB-NEXT:    ands r1, r0
-; CHECK-THUMB-NEXT:    ldr r0, .LCPI6_3
+; CHECK-THUMB-NEXT:    ldr r0, .LCPI6_0
 ; CHECK-THUMB-NEXT:    muls r0, r1, r0
-; CHECK-THUMB-NEXT:    lsrs r0, r0, #24
+; CHECK-THUMB-NEXT:    lsrs r0, r0, #27
+; CHECK-THUMB-NEXT:    adr r1, .LCPI6_1
+; CHECK-THUMB-NEXT:    ldr r0, [r1, r0]
 ; CHECK-THUMB-NEXT:    bx lr
 ; CHECK-THUMB-NEXT:    .p2align 2
 ; CHECK-THUMB-NEXT:  @ %bb.1:
 ; CHECK-THUMB-NEXT:  .LCPI6_0:
-; CHECK-THUMB-NEXT:    .long 1431655765 @ 0x55555555
+; CHECK-THUMB-NEXT:    .long 125613361 @ 0x77cb531
 ; CHECK-THUMB-NEXT:  .LCPI6_1:
-; CHECK-THUMB-NEXT:    .long 858993459 @ 0x33333333
-; CHECK-THUMB-NEXT:  .LCPI6_2:
-; CHECK-THUMB-NEXT:    .long 252645135 @ 0xf0f0f0f
-; CHECK-THUMB-NEXT:  .LCPI6_3:
-; CHECK-THUMB-NEXT:    .long 16843009 @ 0x1010101
+; CHECK-THUMB-NEXT:    .ascii "\000\001\034\002\035\016\030\003\036\026\024\017\031\021\004\b\037\033\r\027\025\023\020\007\032\f\022\006\013\005\n\t"
   %tmp = call i32 @llvm.cttz.i32(i32 %a, i1 true)
   ret i32 %tmp
 }
@@ -374,59 +258,33 @@
 ;
 ; CHECK-THUMB-LABEL: test_i64_zero_undef:
 ; CHECK-THUMB:       @ %bb.0:
-; CHECK-THUMB-NEXT:    .save {r4, r5, r7, lr}
-; CHECK-THUMB-NEXT:    push {r4, r5, r7, lr}
-; CHECK-THUMB-NEXT:    ldr r5, .LCPI7_0
-; CHECK-THUMB-NEXT:    ldr r4, .LCPI7_1
-; CHECK-THUMB-NEXT:    ldr r3, .LCPI7_2
-; CHECK-THUMB-NEXT:    ldr r2, .LCPI7_3
+; CHECK-THUMB-NEXT:    ldr r3, .LCPI7_0
+; CHECK-THUMB-NEXT:    adr r2, .LCPI7_1
 ; CHECK-THUMB-NEXT:    cmp r0, #0
 ; CHECK-THUMB-NEXT:    bne .LBB7_2
 ; CHECK-THUMB-NEXT:  @ %bb.1:
-; CHECK-THUMB-NEXT:    subs r0, r1, #1
-; CHECK-THUMB-NEXT:    bics r0, r1
-; CHECK-THUMB-NEXT:    lsrs r1, r0, #1
-; CHECK-THUMB-NEXT:    ands r1, r5
-; CHECK-THUMB-NEXT:    subs r0, r0, r1
-; CHECK-THUMB-NEXT:    lsrs r1, r0, #2
-; CHECK-THUMB-NEXT:    ands r0, r4
-; CHECK-THUMB-NEXT:    ands r1, r4
-; CHECK-THUMB-NEXT:    adds r0, r0, r1
-; CHECK-THUMB-NEXT:    lsrs r1, r0, #4
-; CHECK-THUMB-NEXT:    adds r0, r0, r1
-; CHECK-THUMB-NEXT:    ands r0, r3
-; CHECK-THUMB-NEXT:    muls r2, r0, r2
-; CHECK-THUMB-NEXT:    lsrs r0, r2, #24
+; CHECK-THUMB-NEXT:    rsbs r0, r1, #0
+; CHECK-THUMB-NEXT:    ands r0, r1
+; CHECK-THUMB-NEXT:    muls r3, r0, r3
+; CHECK-THUMB-NEXT:    lsrs r0, r3, #27
+; CHECK-THUMB-NEXT:    ldr r0, [r2, r0]
 ; CHECK-THUMB-NEXT:    adds r0, #32
 ; CHECK-THUMB-NEXT:    movs r1, #0
-; CHECK-THUMB-NEXT:    pop {r4, r5, r7, pc}
+; CHECK-THUMB-NEXT:    bx lr
 ; CHECK-THUMB-NEXT:  .LBB7_2:
-; CHECK-THUMB-NEXT:    subs r1, r0, #1
-; CHECK-THUMB-NEXT:    bics r1, r0
-; CHECK-THUMB-NEXT:    lsrs r0, r1, #1
-; CHECK-THUMB-NEXT:    ands r0, r5
-; CHECK-THUMB-NEXT:    subs r0, r1, r0
-; CHECK-THUMB-NEXT:    lsrs r1, r0, #2
-; CHECK-THUMB-NEXT:    ands r0, r4
-; CHECK-THUMB-NEXT:    ands r1, r4
-; CHECK-THUMB-NEXT:    adds r0, r0, r1
-; CHECK-THUMB-NEXT:    lsrs r1, r0, #4
-; CHECK-THUMB-NEXT:    adds r0, r0, r1
-; CHECK-THUMB-NEXT:    ands r0, r3
-; CHECK-THUMB-NEXT:    muls r2, r0, r2
-; CHECK-THUMB-NEXT:    lsrs r0, r2, #24
+; CHECK-THUMB-NEXT:    rsbs r1, r0, #0
+; CHECK-THUMB-NEXT:    ands r1, r0
+; CHECK-THUMB-NEXT:    muls r3, r1, r3
+; CHECK-THUMB-NEXT:    lsrs r0, r3, #27
+; CHECK-THUMB-NEXT:    ldr r0, [r2, r0]
 ; CHECK-THUMB-NEXT:    movs r1, #0
-; CHECK-THUMB-NEXT:    pop {r4, r5, r7, pc}
+; CHECK-THUMB-NEXT:    bx lr
 ; CHECK-THUMB-NEXT:    .p2align 2
 ; CHECK-THUMB-NEXT:  @ %bb.3:
 ; CHECK-THUMB-NEXT:  .LCPI7_0:
-; CHECK-THUMB-NEXT:    .long 1431655765 @ 0x55555555
+; CHECK-THUMB-NEXT:    .long 125613361 @ 0x77cb531
 ; CHECK-THUMB-NEXT:  .LCPI7_1:
-; CHECK-THUMB-NEXT:    .long 858993459 @ 0x33333333
-; CHECK-THUMB-NEXT:  .LCPI7_2:
-; CHECK-THUMB-NEXT:    .long 252645135 @ 0xf0f0f0f
-; CHECK-THUMB-NEXT:  .LCPI7_3:
-; CHECK-THUMB-NEXT:    .long 16843009 @ 0x1010101
+; CHECK-THUMB-NEXT:    .ascii "\000\001\034\002\035\016\030\003\036\026\024\017\031\021\004\b\037\033\r\027\025\023\020\007\032\f\022\006\013\005\n\t"
   %tmp = call i64 @llvm.cttz.i64(i64 %a, i1 true)
   ret i64 %tmp
 }
Index: llvm/test/CodeGen/RISCV/rv32zbb.ll
===================================================================
--- llvm/test/CodeGen/RISCV/rv32zbb.ll
+++ llvm/test/CodeGen/RISCV/rv32zbb.ll
@@ -175,29 +175,16 @@
 ; RV32I-NEXT:  # %bb.1: # %cond.false
 ; RV32I-NEXT:    addi sp, sp, -16
 ; RV32I-NEXT:    sw ra, 12(sp) # 4-byte Folded Spill
-; 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:    lw ra, 12(sp) # 4-byte Folded Reload
 ; RV32I-NEXT:    addi sp, sp, 16
 ; RV32I-NEXT:    ret
@@ -225,56 +212,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
@@ -283,8 +246,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,27 @@
+; NOTE: Assertions have been autogenerated by utils/update_llc_test_checks.py
+; RUN: llc < %s -march=sparc -mcpu=v9 | FileCheck %s
+
+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, %o0
+; CHECK-NEXT:    sethi 122669, %o1
+; CHECK-NEXT:    or %o1, 305, %o1
+; CHECK-NEXT:    smul %o0, %o1, %o0
+; CHECK-NEXT:    srl %o0, 27, %o0
+; CHECK-NEXT:    sethi %hi(.LCPI0_0), %o1
+; CHECK-NEXT:    add %o1, %lo(.LCPI0_0), %o1
+; CHECK-NEXT:    retl
+; CHECK-NEXT:    ld [%o1+%o0], %o0
+entry:
+  %0 = call i32 @llvm.cttz.i32(i32 %x, i1 true)
+  ret i32 %0
+}
+
+; 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 }