diff --git a/llvm/lib/Transforms/Scalar/LoopIdiomRecognize.cpp b/llvm/lib/Transforms/Scalar/LoopIdiomRecognize.cpp
--- a/llvm/lib/Transforms/Scalar/LoopIdiomRecognize.cpp
+++ b/llvm/lib/Transforms/Scalar/LoopIdiomRecognize.cpp
@@ -1953,8 +1953,7 @@
 /// \endcode
 static bool detectShiftUntilBitTestIdiom(Loop *CurLoop, Value *&BaseX,
                                          Value *&BitMask, Value *&BitPos,
-                                         Value *&CurrX, Value *&NextX,
-                                         size_t &CanonicalHeaderSize) {
+                                         Value *&CurrX, Value *&NextX) {
   LLVM_DEBUG(dbgs() << DEBUG_TYPE
              " Performing shift-until-bittest idiom detection.\n");
 
@@ -1985,7 +1984,6 @@
   // Step 2: Check if the backedge's condition is in desirable form.
 
   auto MatchVariableBitMask = [&]() {
-    CanonicalHeaderSize = 5;
     return ICmpInst::isEquality(Pred) && match(CmpRHS, m_Zero()) &&
            match(CmpLHS,
                  m_c_And(m_Value(CurrX),
@@ -1995,15 +1993,12 @@
                                              CurLoop))));
   };
   auto MatchConstantBitMask = [&]() {
-    CanonicalHeaderSize = 5;
     return ICmpInst::isEquality(Pred) && match(CmpRHS, m_Zero()) &&
            match(CmpLHS, m_And(m_Value(CurrX),
                                m_CombineAnd(m_Value(BitMask), m_Power2()))) &&
            (BitPos = ConstantExpr::getExactLogBase2(cast<Constant>(BitMask)));
   };
   auto MatchDecomposableConstantBitMask = [&]() {
-    CanonicalHeaderSize = 4;
-
     APInt Mask;
     return llvm::decomposeBitTestICmp(CmpLHS, CmpRHS, Pred, CurrX, Mask) &&
            ICmpInst::isEquality(Pred) && Mask.isPowerOf2() &&
@@ -2100,9 +2095,8 @@
   bool MadeChange = false;
 
   Value *X, *BitMask, *BitPos, *XCurr, *XNext;
-  size_t CanonicalHeaderSize;
-  if (!detectShiftUntilBitTestIdiom(CurLoop, X, BitMask, BitPos, XCurr, XNext,
-                                    CanonicalHeaderSize)) {
+  if (!detectShiftUntilBitTestIdiom(CurLoop, X, BitMask, BitPos, XCurr,
+                                    XNext)) {
     LLVM_DEBUG(dbgs() << DEBUG_TYPE
                " shift-until-bittest idiom detection failed.\n");
     return MadeChange;
@@ -2119,25 +2113,6 @@
   BasicBlock *SuccessorBB = CurLoop->getExitBlock();
   assert(LoopPreheaderBB && "There is only a single successor.");
 
-  // The loop must not have any other instructions other than the idiom itself.
-  // FIXME: we could just rewrite the loop with countable trip count.
-  size_t HeaderSize = LoopHeaderBB->sizeWithoutDebug();
-  assert(HeaderSize >= CanonicalHeaderSize);
-  if (HeaderSize > CanonicalHeaderSize) {
-    LLVM_DEBUG(dbgs() << DEBUG_TYPE " Won't be able to delete loop!\n");
-    return MadeChange;
-  }
-
-  // Only the recurrence itself is allowed to have uses outside of the loop.
-  if (any_of(SuccessorBB->phis(), [&](PHINode &PN) {
-        Value *IV = PN.getIncomingValueForBlock(LoopHeaderBB);
-        return IV != XCurr && IV != XNext && !CurLoop->isLoopInvariant(IV);
-      })) {
-    LLVM_DEBUG(dbgs() << DEBUG_TYPE " In-loop value is live-out!\n");
-    return MadeChange;
-  }
-  // FIXME: we *could* allow this.
-
   IRBuilder<> Builder(LoopPreheaderBB->getTerminator());
   Builder.SetCurrentDebugLocation(cast<Instruction>(XCurr)->getDebugLoc());
 
@@ -2147,7 +2122,9 @@
   TargetTransformInfo::TargetCostKind CostKind =
       TargetTransformInfo::TCK_SizeAndLatency;
 
-  // Also, the intrinsic and shift we'll use must be cheap.
+  // The rewrite is considered to be unprofitable iff and only iff
+  // the intrinsic/shift we'll is not cheap. Note that we are okay with *just*
+  // making the loop countable, even if nothing else changes.
   IntrinsicCostAttributes Attrs(
       IntrID, Ty, {UndefValue::get(Ty), /*is_zero_undef=*/Builder.getTrue()});
   int Cost = TTI->getIntrinsicInstrCost(Attrs, CostKind);
@@ -2199,24 +2176,40 @@
   Value *NewXNext = Builder.CreateShl(X, LoopTripCount);
   NewXNext->takeName(XNext);
 
-  // Step 3: Replace all references to the recurrence with
-  //         computed recurrence's final value.
+  // Step 3: Adjust the successor basic block to recieve the computed
+  //         recurrence's final value instead of the recurrence itself..
 
-  XCurr->replaceAllUsesWith(NewX);
-  XNext->replaceAllUsesWith(NewXNext);
+  XCurr->replaceUsesOutsideBlock(NewX, LoopHeaderBB);
+  XNext->replaceUsesOutsideBlock(NewXNext, LoopHeaderBB);
 
-  // Step 4: Fix the loop back-edge to always exit upon first iteration.
+  // Step 4: Rewrite the loop into a countable form, with canonical IV.
 
+  // The new canonical induction variable.
+  Builder.SetInsertPoint(&LoopHeaderBB->front());
+  auto *IV = Builder.CreatePHI(Ty, 2, CurLoop->getName() + ".iv");
+
+  // The induction itself.
+  // Note that while NUW is always safe, while NSW is only for bitwidths != 2.
   Builder.SetInsertPoint(LoopHeaderBB->getTerminator());
-  Builder.CreateCondBr(Builder.getTrue(), SuccessorBB, LoopHeaderBB);
+  auto *IVNext = Builder.CreateNUWAdd(IV, ConstantInt::get(Ty, 1),
+                                      IV->getName() + ".next");
+
+  // The loop trip count check.
+  auto *IVCheck = Builder.CreateICmpEQ(IVNext, LoopTripCount,
+                                       CurLoop->getName() + ".ivcheck");
+  Builder.CreateCondBr(IVCheck, SuccessorBB, LoopHeaderBB);
   LoopHeaderBB->getTerminator()->eraseFromParent();
 
+  // Populate the IV PHI.
+  IV->addIncoming(ConstantInt::get(Ty, 0), LoopPreheaderBB);
+  IV->addIncoming(IVNext, LoopHeaderBB);
+
   // Step 5: Forget the "non-computable" trip-count SCEV associated with the
   //   loop. The loop would otherwise not be deleted even if it becomes empty.
 
   SE->forgetLoop(CurLoop);
 
-  // Other passes will take care of actually deleting the loop.
+  // Other passes will take care of actually deleting the loop if possible.
 
   LLVM_DEBUG(dbgs() << DEBUG_TYPE " shift-until-bittest idiom optimized!\n");
 
diff --git a/llvm/test/Transforms/LoopIdiom/X86/left-shift-until-bittest.ll b/llvm/test/Transforms/LoopIdiom/X86/left-shift-until-bittest.ll
--- a/llvm/test/Transforms/LoopIdiom/X86/left-shift-until-bittest.ll
+++ b/llvm/test/Transforms/LoopIdiom/X86/left-shift-until-bittest.ll
@@ -31,15 +31,18 @@
 ; LZCNT-NEXT:    [[X_NEXT:%.*]] = shl i32 [[X]], [[LOOP_TRIPCOUNT]], [[DBG17]]
 ; LZCNT-NEXT:    br label [[LOOP:%.*]], [[DBG18:!dbg !.*]]
 ; LZCNT:       loop:
-; LZCNT-NEXT:    [[TMP0:%.*]] = phi i32 [ [[X]], [[ENTRY:%.*]] ], [ [[X_NEXT]], [[LOOP]] ], [[DBG17]]
-; LZCNT-NEXT:    call void @llvm.dbg.value(metadata i32 [[X_CURR]], [[META11:metadata !.*]], metadata !DIExpression()), [[DBG17]]
-; LZCNT-NEXT:    [[X_CURR_BITMASKED:%.*]] = and i32 [[X_CURR]], [[BITMASK]], [[DBG19:!dbg !.*]]
+; LZCNT-NEXT:    [[LOOP_IV:%.*]] = phi i32 [ 0, [[ENTRY:%.*]] ], [ [[LOOP_IV_NEXT:%.*]], [[LOOP]] ], [[DBG17]]
+; LZCNT-NEXT:    [[TMP0:%.*]] = phi i32 [ [[X]], [[ENTRY]] ], [ [[TMP1:%.*]], [[LOOP]] ], [[DBG17]]
+; LZCNT-NEXT:    call void @llvm.dbg.value(metadata i32 [[TMP0]], [[META11:metadata !.*]], metadata !DIExpression()), [[DBG17]]
+; LZCNT-NEXT:    [[X_CURR_BITMASKED:%.*]] = and i32 [[TMP0]], [[BITMASK]], [[DBG19:!dbg !.*]]
 ; LZCNT-NEXT:    call void @llvm.dbg.value(metadata i32 [[X_CURR_BITMASKED]], [[META12:metadata !.*]], metadata !DIExpression()), [[DBG19]]
 ; LZCNT-NEXT:    [[X_CURR_ISBITUNSET:%.*]] = icmp eq i32 [[X_CURR_BITMASKED]], 0, [[DBG20:!dbg !.*]]
 ; LZCNT-NEXT:    call void @llvm.dbg.value(metadata i1 [[X_CURR_ISBITUNSET]], [[META13:metadata !.*]], metadata !DIExpression()), [[DBG20]]
-; LZCNT-NEXT:    [[TMP1:%.*]] = shl i32 [[X_CURR]], 1, [[DBG21:!dbg !.*]]
-; LZCNT-NEXT:    call void @llvm.dbg.value(metadata i32 [[X_NEXT]], [[META15:metadata !.*]], metadata !DIExpression()), [[DBG21]]
-; LZCNT-NEXT:    br i1 true, label [[END:%.*]], label [[LOOP]], [[DBG22:!dbg !.*]]
+; LZCNT-NEXT:    [[TMP1]] = shl i32 [[TMP0]], 1, [[DBG21:!dbg !.*]]
+; LZCNT-NEXT:    call void @llvm.dbg.value(metadata i32 [[TMP1]], [[META15:metadata !.*]], metadata !DIExpression()), [[DBG21]]
+; LZCNT-NEXT:    [[LOOP_IV_NEXT]] = add nuw i32 [[LOOP_IV]], 1, [[DBG22:!dbg !.*]]
+; LZCNT-NEXT:    [[LOOP_IVCHECK:%.*]] = icmp eq i32 [[LOOP_IV_NEXT]], [[LOOP_TRIPCOUNT]], [[DBG22]]
+; LZCNT-NEXT:    br i1 [[LOOP_IVCHECK]], label [[END:%.*]], label [[LOOP]], [[DBG22]]
 ; LZCNT:       end:
 ; LZCNT-NEXT:    [[X_CURR_LCSSA:%.*]] = phi i32 [ [[X_CURR]], [[LOOP]] ], [[DBG17]]
 ; LZCNT-NEXT:    call void @llvm.dbg.value(metadata i32 [[X_CURR_LCSSA]], [[META11]], metadata !DIExpression()), [[DBG17]]
@@ -98,15 +101,18 @@
 ; LZCNT-NEXT:    [[X_NEXT:%.*]] = shl i16 [[X]], [[LOOP_TRIPCOUNT]], [[DBG33]]
 ; LZCNT-NEXT:    br label [[LOOP:%.*]], [[DBG34:!dbg !.*]]
 ; LZCNT:       loop:
-; LZCNT-NEXT:    [[TMP0:%.*]] = phi i16 [ [[X]], [[ENTRY:%.*]] ], [ [[X_NEXT]], [[LOOP]] ], [[DBG33]]
-; LZCNT-NEXT:    call void @llvm.dbg.value(metadata i16 [[X_CURR]], [[META28:metadata !.*]], metadata !DIExpression()), [[DBG33]]
-; LZCNT-NEXT:    [[X_CURR_BITMASKED:%.*]] = and i16 [[X_CURR]], [[BITMASK]], [[DBG35:!dbg !.*]]
+; LZCNT-NEXT:    [[LOOP_IV:%.*]] = phi i16 [ 0, [[ENTRY:%.*]] ], [ [[LOOP_IV_NEXT:%.*]], [[LOOP]] ], [[DBG33]]
+; LZCNT-NEXT:    [[TMP0:%.*]] = phi i16 [ [[X]], [[ENTRY]] ], [ [[TMP1:%.*]], [[LOOP]] ], [[DBG33]]
+; LZCNT-NEXT:    call void @llvm.dbg.value(metadata i16 [[TMP0]], [[META28:metadata !.*]], metadata !DIExpression()), [[DBG33]]
+; LZCNT-NEXT:    [[X_CURR_BITMASKED:%.*]] = and i16 [[TMP0]], [[BITMASK]], [[DBG35:!dbg !.*]]
 ; LZCNT-NEXT:    call void @llvm.dbg.value(metadata i16 [[X_CURR_BITMASKED]], [[META29:metadata !.*]], metadata !DIExpression()), [[DBG35]]
 ; LZCNT-NEXT:    [[X_CURR_ISBITUNSET:%.*]] = icmp eq i16 [[X_CURR_BITMASKED]], 0, [[DBG36:!dbg !.*]]
 ; LZCNT-NEXT:    call void @llvm.dbg.value(metadata i1 [[X_CURR_ISBITUNSET]], [[META30:metadata !.*]], metadata !DIExpression()), [[DBG36]]
-; LZCNT-NEXT:    [[TMP1:%.*]] = shl i16 [[X_CURR]], 1, [[DBG37:!dbg !.*]]
-; LZCNT-NEXT:    call void @llvm.dbg.value(metadata i16 [[X_NEXT]], [[META31:metadata !.*]], metadata !DIExpression()), [[DBG37]]
-; LZCNT-NEXT:    br i1 true, label [[END:%.*]], label [[LOOP]], [[DBG38:!dbg !.*]]
+; LZCNT-NEXT:    [[TMP1]] = shl i16 [[TMP0]], 1, [[DBG37:!dbg !.*]]
+; LZCNT-NEXT:    call void @llvm.dbg.value(metadata i16 [[TMP1]], [[META31:metadata !.*]], metadata !DIExpression()), [[DBG37]]
+; LZCNT-NEXT:    [[LOOP_IV_NEXT]] = add nuw i16 [[LOOP_IV]], 1, [[DBG38:!dbg !.*]]
+; LZCNT-NEXT:    [[LOOP_IVCHECK:%.*]] = icmp eq i16 [[LOOP_IV_NEXT]], [[LOOP_TRIPCOUNT]], [[DBG38]]
+; LZCNT-NEXT:    br i1 [[LOOP_IVCHECK]], label [[END:%.*]], label [[LOOP]], [[DBG38]]
 ; LZCNT:       end:
 ; LZCNT-NEXT:    [[X_CURR_LCSSA:%.*]] = phi i16 [ [[X_CURR]], [[LOOP]] ], [[DBG33]]
 ; LZCNT-NEXT:    call void @llvm.dbg.value(metadata i16 [[X_CURR_LCSSA]], [[META28]], metadata !DIExpression()), [[DBG33]]
@@ -160,15 +166,18 @@
 ; LZCNT-NEXT:    [[X_NEXT:%.*]] = shl i32 [[X]], [[LOOP_TRIPCOUNT]], [[DBG46]]
 ; LZCNT-NEXT:    br label [[LOOP:%.*]], [[DBG47:!dbg !.*]]
 ; LZCNT:       loop:
-; LZCNT-NEXT:    [[TMP0:%.*]] = phi i32 [ [[X]], [[ENTRY:%.*]] ], [ [[X_NEXT]], [[LOOP]] ], [[DBG46]]
-; LZCNT-NEXT:    call void @llvm.dbg.value(metadata i32 [[X_CURR]], [[META42:metadata !.*]], metadata !DIExpression()), [[DBG46]]
-; LZCNT-NEXT:    [[X_CURR_BITMASKED:%.*]] = and i32 [[X_CURR]], 16777216, [[DBG48:!dbg !.*]]
+; LZCNT-NEXT:    [[LOOP_IV:%.*]] = phi i32 [ 0, [[ENTRY:%.*]] ], [ [[LOOP_IV_NEXT:%.*]], [[LOOP]] ], [[DBG46]]
+; LZCNT-NEXT:    [[TMP0:%.*]] = phi i32 [ [[X]], [[ENTRY]] ], [ [[TMP1:%.*]], [[LOOP]] ], [[DBG46]]
+; LZCNT-NEXT:    call void @llvm.dbg.value(metadata i32 [[TMP0]], [[META42:metadata !.*]], metadata !DIExpression()), [[DBG46]]
+; LZCNT-NEXT:    [[X_CURR_BITMASKED:%.*]] = and i32 [[TMP0]], 16777216, [[DBG48:!dbg !.*]]
 ; LZCNT-NEXT:    call void @llvm.dbg.value(metadata i32 [[X_CURR_BITMASKED]], [[META43:metadata !.*]], metadata !DIExpression()), [[DBG48]]
 ; LZCNT-NEXT:    [[X_CURR_ISBITUNSET:%.*]] = icmp eq i32 [[X_CURR_BITMASKED]], 0, [[DBG49:!dbg !.*]]
 ; LZCNT-NEXT:    call void @llvm.dbg.value(metadata i1 [[X_CURR_ISBITUNSET]], [[META44:metadata !.*]], metadata !DIExpression()), [[DBG49]]
-; LZCNT-NEXT:    [[TMP1:%.*]] = shl i32 [[X_CURR]], 1, [[DBG50:!dbg !.*]]
-; LZCNT-NEXT:    call void @llvm.dbg.value(metadata i32 [[X_NEXT]], [[META45:metadata !.*]], metadata !DIExpression()), [[DBG50]]
-; LZCNT-NEXT:    br i1 true, label [[END:%.*]], label [[LOOP]], [[DBG51:!dbg !.*]]
+; LZCNT-NEXT:    [[TMP1]] = shl i32 [[TMP0]], 1, [[DBG50:!dbg !.*]]
+; LZCNT-NEXT:    call void @llvm.dbg.value(metadata i32 [[TMP1]], [[META45:metadata !.*]], metadata !DIExpression()), [[DBG50]]
+; LZCNT-NEXT:    [[LOOP_IV_NEXT]] = add nuw i32 [[LOOP_IV]], 1, [[DBG51:!dbg !.*]]
+; LZCNT-NEXT:    [[LOOP_IVCHECK:%.*]] = icmp eq i32 [[LOOP_IV_NEXT]], [[LOOP_TRIPCOUNT]], [[DBG51]]
+; LZCNT-NEXT:    br i1 [[LOOP_IVCHECK]], label [[END:%.*]], label [[LOOP]], [[DBG51]]
 ; LZCNT:       end:
 ; LZCNT-NEXT:    [[X_CURR_LCSSA:%.*]] = phi i32 [ [[X_CURR]], [[LOOP]] ], [[DBG46]]
 ; LZCNT-NEXT:    call void @llvm.dbg.value(metadata i32 [[X_CURR_LCSSA]], [[META42]], metadata !DIExpression()), [[DBG46]]
@@ -219,15 +228,18 @@
 ; LZCNT-NEXT:    [[X_NEXT:%.*]] = shl i32 [[X]], [[LOOP_TRIPCOUNT]], [[DBG59]]
 ; LZCNT-NEXT:    br label [[LOOP:%.*]], [[DBG60:!dbg !.*]]
 ; LZCNT:       loop:
-; LZCNT-NEXT:    [[TMP0:%.*]] = phi i32 [ [[X]], [[ENTRY:%.*]] ], [ [[X_NEXT]], [[LOOP]] ], [[DBG59]]
-; LZCNT-NEXT:    call void @llvm.dbg.value(metadata i32 [[X_CURR]], [[META55:metadata !.*]], metadata !DIExpression()), [[DBG59]]
-; LZCNT-NEXT:    [[X_CURR_BITMASKED:%.*]] = and i32 [[X_CURR]], 32768, [[DBG61:!dbg !.*]]
+; LZCNT-NEXT:    [[LOOP_IV:%.*]] = phi i32 [ 0, [[ENTRY:%.*]] ], [ [[LOOP_IV_NEXT:%.*]], [[LOOP]] ], [[DBG59]]
+; LZCNT-NEXT:    [[TMP0:%.*]] = phi i32 [ [[X]], [[ENTRY]] ], [ [[TMP1:%.*]], [[LOOP]] ], [[DBG59]]
+; LZCNT-NEXT:    call void @llvm.dbg.value(metadata i32 [[TMP0]], [[META55:metadata !.*]], metadata !DIExpression()), [[DBG59]]
+; LZCNT-NEXT:    [[X_CURR_BITMASKED:%.*]] = and i32 [[TMP0]], 32768, [[DBG61:!dbg !.*]]
 ; LZCNT-NEXT:    call void @llvm.dbg.value(metadata i32 [[X_CURR_BITMASKED]], [[META56:metadata !.*]], metadata !DIExpression()), [[DBG61]]
 ; LZCNT-NEXT:    [[X_CURR_ISBITUNSET:%.*]] = icmp eq i32 [[X_CURR_BITMASKED]], 0, [[DBG62:!dbg !.*]]
 ; LZCNT-NEXT:    call void @llvm.dbg.value(metadata i1 [[X_CURR_ISBITUNSET]], [[META57:metadata !.*]], metadata !DIExpression()), [[DBG62]]
-; LZCNT-NEXT:    [[TMP1:%.*]] = shl i32 [[X_CURR]], 1, [[DBG63:!dbg !.*]]
-; LZCNT-NEXT:    call void @llvm.dbg.value(metadata i32 [[X_NEXT]], [[META58:metadata !.*]], metadata !DIExpression()), [[DBG63]]
-; LZCNT-NEXT:    br i1 true, label [[END:%.*]], label [[LOOP]], [[DBG64:!dbg !.*]]
+; LZCNT-NEXT:    [[TMP1]] = shl i32 [[TMP0]], 1, [[DBG63:!dbg !.*]]
+; LZCNT-NEXT:    call void @llvm.dbg.value(metadata i32 [[TMP1]], [[META58:metadata !.*]], metadata !DIExpression()), [[DBG63]]
+; LZCNT-NEXT:    [[LOOP_IV_NEXT]] = add nuw i32 [[LOOP_IV]], 1, [[DBG64:!dbg !.*]]
+; LZCNT-NEXT:    [[LOOP_IVCHECK:%.*]] = icmp eq i32 [[LOOP_IV_NEXT]], [[LOOP_TRIPCOUNT]], [[DBG64]]
+; LZCNT-NEXT:    br i1 [[LOOP_IVCHECK]], label [[END:%.*]], label [[LOOP]], [[DBG64]]
 ; LZCNT:       end:
 ; LZCNT-NEXT:    [[X_CURR_LCSSA:%.*]] = phi i32 [ [[X_CURR]], [[LOOP]] ], [[DBG59]]
 ; LZCNT-NEXT:    call void @llvm.dbg.value(metadata i32 [[X_CURR_LCSSA]], [[META55]], metadata !DIExpression()), [[DBG59]]
@@ -283,15 +295,18 @@
 ; LZCNT-NEXT:    [[X_NEXT:%.*]] = shl i32 [[X]], [[LOOP_TRIPCOUNT]], [[DBG74]]
 ; LZCNT-NEXT:    br label [[LOOP:%.*]], [[DBG75:!dbg !.*]]
 ; LZCNT:       loop:
-; LZCNT-NEXT:    [[TMP0:%.*]] = phi i32 [ [[X]], [[ENTRY:%.*]] ], [ [[X_NEXT]], [[LOOP]] ], [[DBG74]]
-; LZCNT-NEXT:    call void @llvm.dbg.value(metadata i32 [[X_CURR]], [[META69:metadata !.*]], metadata !DIExpression()), [[DBG74]]
-; LZCNT-NEXT:    [[X_CURR_BITMASKED:%.*]] = and i32 [[X_CURR]], [[BITMASK]], [[DBG76:!dbg !.*]]
+; LZCNT-NEXT:    [[LOOP_IV:%.*]] = phi i32 [ 0, [[ENTRY:%.*]] ], [ [[LOOP_IV_NEXT:%.*]], [[LOOP]] ], [[DBG74]]
+; LZCNT-NEXT:    [[TMP0:%.*]] = phi i32 [ [[X]], [[ENTRY]] ], [ [[TMP1:%.*]], [[LOOP]] ], [[DBG74]]
+; LZCNT-NEXT:    call void @llvm.dbg.value(metadata i32 [[TMP0]], [[META69:metadata !.*]], metadata !DIExpression()), [[DBG74]]
+; LZCNT-NEXT:    [[X_CURR_BITMASKED:%.*]] = and i32 [[TMP0]], [[BITMASK]], [[DBG76:!dbg !.*]]
 ; LZCNT-NEXT:    call void @llvm.dbg.value(metadata i32 [[X_CURR_BITMASKED]], [[META70:metadata !.*]], metadata !DIExpression()), [[DBG76]]
 ; LZCNT-NEXT:    [[X_CURR_ISBITUNSET:%.*]] = icmp eq i32 [[X_CURR_BITMASKED]], 0, [[DBG77:!dbg !.*]]
 ; LZCNT-NEXT:    call void @llvm.dbg.value(metadata i1 [[X_CURR_ISBITUNSET]], [[META71:metadata !.*]], metadata !DIExpression()), [[DBG77]]
-; LZCNT-NEXT:    [[TMP1:%.*]] = shl i32 [[X_CURR]], 1, [[DBG78:!dbg !.*]]
-; LZCNT-NEXT:    call void @llvm.dbg.value(metadata i32 [[X_NEXT]], [[META72:metadata !.*]], metadata !DIExpression()), [[DBG78]]
-; LZCNT-NEXT:    br i1 true, label [[END:%.*]], label [[LOOP]], [[DBG79:!dbg !.*]]
+; LZCNT-NEXT:    [[TMP1]] = shl i32 [[TMP0]], 1, [[DBG78:!dbg !.*]]
+; LZCNT-NEXT:    call void @llvm.dbg.value(metadata i32 [[TMP1]], [[META72:metadata !.*]], metadata !DIExpression()), [[DBG78]]
+; LZCNT-NEXT:    [[LOOP_IV_NEXT]] = add nuw i32 [[LOOP_IV]], 1, [[DBG79:!dbg !.*]]
+; LZCNT-NEXT:    [[LOOP_IVCHECK:%.*]] = icmp eq i32 [[LOOP_IV_NEXT]], [[LOOP_TRIPCOUNT]], [[DBG79]]
+; LZCNT-NEXT:    br i1 [[LOOP_IVCHECK]], label [[END:%.*]], label [[LOOP]], [[DBG79]]
 ; LZCNT:       end:
 ; LZCNT-NEXT:    [[X_NEXT_LCSSA:%.*]] = phi i32 [ [[X_NEXT]], [[LOOP]] ], [[DBG78]]
 ; LZCNT-NEXT:    ret i32 [[X_NEXT_LCSSA]], [[DBG80:!dbg !.*]]
@@ -347,15 +362,18 @@
 ; LZCNT-NEXT:    [[X_NEXT:%.*]] = shl i32 [[X]], [[LOOP_TRIPCOUNT]], [[DBG89]]
 ; LZCNT-NEXT:    br label [[LOOP:%.*]], [[DBG90:!dbg !.*]]
 ; LZCNT:       loop:
-; LZCNT-NEXT:    [[TMP0:%.*]] = phi i32 [ [[X]], [[ENTRY:%.*]] ], [ [[X_NEXT]], [[LOOP]] ], [[DBG89]]
-; LZCNT-NEXT:    call void @llvm.dbg.value(metadata i32 [[X_CURR]], [[META84:metadata !.*]], metadata !DIExpression()), [[DBG89]]
-; LZCNT-NEXT:    [[X_CURR_BITMASKED:%.*]] = and i32 [[X_CURR]], [[BITMASK]], [[DBG91:!dbg !.*]]
+; LZCNT-NEXT:    [[LOOP_IV:%.*]] = phi i32 [ 0, [[ENTRY:%.*]] ], [ [[LOOP_IV_NEXT:%.*]], [[LOOP]] ], [[DBG89]]
+; LZCNT-NEXT:    [[TMP0:%.*]] = phi i32 [ [[X]], [[ENTRY]] ], [ [[TMP1:%.*]], [[LOOP]] ], [[DBG89]]
+; LZCNT-NEXT:    call void @llvm.dbg.value(metadata i32 [[TMP0]], [[META84:metadata !.*]], metadata !DIExpression()), [[DBG89]]
+; LZCNT-NEXT:    [[X_CURR_BITMASKED:%.*]] = and i32 [[TMP0]], [[BITMASK]], [[DBG91:!dbg !.*]]
 ; LZCNT-NEXT:    call void @llvm.dbg.value(metadata i32 [[X_CURR_BITMASKED]], [[META85:metadata !.*]], metadata !DIExpression()), [[DBG91]]
 ; LZCNT-NEXT:    [[X_CURR_ISBITUNSET:%.*]] = icmp eq i32 [[X_CURR_BITMASKED]], 0, [[DBG92:!dbg !.*]]
 ; LZCNT-NEXT:    call void @llvm.dbg.value(metadata i1 [[X_CURR_ISBITUNSET]], [[META86:metadata !.*]], metadata !DIExpression()), [[DBG92]]
-; LZCNT-NEXT:    [[TMP1:%.*]] = shl i32 [[X_CURR]], 1, [[DBG93:!dbg !.*]]
-; LZCNT-NEXT:    call void @llvm.dbg.value(metadata i32 [[X_NEXT]], [[META87:metadata !.*]], metadata !DIExpression()), [[DBG93]]
-; LZCNT-NEXT:    br i1 true, label [[END:%.*]], label [[LOOP]], [[DBG94:!dbg !.*]]
+; LZCNT-NEXT:    [[TMP1]] = shl i32 [[TMP0]], 1, [[DBG93:!dbg !.*]]
+; LZCNT-NEXT:    call void @llvm.dbg.value(metadata i32 [[TMP1]], [[META87:metadata !.*]], metadata !DIExpression()), [[DBG93]]
+; LZCNT-NEXT:    [[LOOP_IV_NEXT]] = add nuw i32 [[LOOP_IV]], 1, [[DBG94:!dbg !.*]]
+; LZCNT-NEXT:    [[LOOP_IVCHECK:%.*]] = icmp eq i32 [[LOOP_IV_NEXT]], [[LOOP_TRIPCOUNT]], [[DBG94]]
+; LZCNT-NEXT:    br i1 [[LOOP_IVCHECK]], label [[END:%.*]], label [[LOOP]], [[DBG94]]
 ; LZCNT:       end:
 ; LZCNT-NEXT:    [[X_CURR_LCSSA:%.*]] = phi i32 [ [[X_CURR]], [[LOOP]] ], [[DBG89]]
 ; LZCNT-NEXT:    [[X_NEXT_LCSSA:%.*]] = phi i32 [ [[X_NEXT]], [[LOOP]] ], [[DBG93]]
@@ -416,15 +434,18 @@
 ; LZCNT-NEXT:    [[X_NEXT:%.*]] = shl i32 [[X]], [[LOOP_TRIPCOUNT]], [[DBG104]]
 ; LZCNT-NEXT:    br label [[LOOP:%.*]], [[DBG105:!dbg !.*]]
 ; LZCNT:       loop:
-; LZCNT-NEXT:    [[TMP0:%.*]] = phi i32 [ [[X]], [[ENTRY:%.*]] ], [ [[X_NEXT]], [[LOOP]] ], [[DBG104]]
-; LZCNT-NEXT:    call void @llvm.dbg.value(metadata i32 [[X_CURR]], [[META100:metadata !.*]], metadata !DIExpression()), [[DBG104]]
-; LZCNT-NEXT:    [[X_CURR_BITMASKED:%.*]] = and i32 [[X_CURR]], -2147483648, [[DBG106:!dbg !.*]]
+; LZCNT-NEXT:    [[LOOP_IV:%.*]] = phi i32 [ 0, [[ENTRY:%.*]] ], [ [[LOOP_IV_NEXT:%.*]], [[LOOP]] ], [[DBG104]]
+; LZCNT-NEXT:    [[TMP0:%.*]] = phi i32 [ [[X]], [[ENTRY]] ], [ [[TMP1:%.*]], [[LOOP]] ], [[DBG104]]
+; LZCNT-NEXT:    call void @llvm.dbg.value(metadata i32 [[TMP0]], [[META100:metadata !.*]], metadata !DIExpression()), [[DBG104]]
+; LZCNT-NEXT:    [[X_CURR_BITMASKED:%.*]] = and i32 [[TMP0]], -2147483648, [[DBG106:!dbg !.*]]
 ; LZCNT-NEXT:    call void @llvm.dbg.value(metadata i32 [[X_CURR_BITMASKED]], [[META101:metadata !.*]], metadata !DIExpression()), [[DBG106]]
 ; LZCNT-NEXT:    [[X_CURR_ISBITUNSET:%.*]] = icmp eq i32 [[X_CURR_BITMASKED]], 0, [[DBG107:!dbg !.*]]
 ; LZCNT-NEXT:    call void @llvm.dbg.value(metadata i1 [[X_CURR_ISBITUNSET]], [[META102:metadata !.*]], metadata !DIExpression()), [[DBG107]]
-; LZCNT-NEXT:    [[TMP1:%.*]] = shl i32 [[X_CURR]], 1, [[DBG108:!dbg !.*]]
-; LZCNT-NEXT:    call void @llvm.dbg.value(metadata i32 [[X_NEXT]], [[META103:metadata !.*]], metadata !DIExpression()), [[DBG108]]
-; LZCNT-NEXT:    br i1 true, label [[END:%.*]], label [[LOOP]], [[DBG109:!dbg !.*]]
+; LZCNT-NEXT:    [[TMP1]] = shl i32 [[TMP0]], 1, [[DBG108:!dbg !.*]]
+; LZCNT-NEXT:    call void @llvm.dbg.value(metadata i32 [[TMP1]], [[META103:metadata !.*]], metadata !DIExpression()), [[DBG108]]
+; LZCNT-NEXT:    [[LOOP_IV_NEXT]] = add nuw i32 [[LOOP_IV]], 1, [[DBG109:!dbg !.*]]
+; LZCNT-NEXT:    [[LOOP_IVCHECK:%.*]] = icmp eq i32 [[LOOP_IV_NEXT]], [[LOOP_TRIPCOUNT]], [[DBG109]]
+; LZCNT-NEXT:    br i1 [[LOOP_IVCHECK]], label [[END:%.*]], label [[LOOP]], [[DBG109]]
 ; LZCNT:       end:
 ; LZCNT-NEXT:    [[X_CURR_LCSSA:%.*]] = phi i32 [ [[X_CURR]], [[LOOP]] ], [[DBG104]]
 ; LZCNT-NEXT:    call void @llvm.dbg.value(metadata i32 [[X_CURR_LCSSA]], [[META100]], metadata !DIExpression()), [[DBG104]]
@@ -474,13 +495,16 @@
 ; LZCNT-NEXT:    [[X_NEXT:%.*]] = shl i32 [[X]], [[LOOP_TRIPCOUNT]], [[DBG116]]
 ; LZCNT-NEXT:    br label [[LOOP:%.*]], [[DBG117:!dbg !.*]]
 ; LZCNT:       loop:
-; LZCNT-NEXT:    [[TMP0:%.*]] = phi i32 [ [[X]], [[ENTRY:%.*]] ], [ [[X_NEXT]], [[LOOP]] ], [[DBG116]]
-; LZCNT-NEXT:    call void @llvm.dbg.value(metadata i32 [[X_CURR]], [[META113:metadata !.*]], metadata !DIExpression()), [[DBG116]]
-; LZCNT-NEXT:    [[X_CURR_ISBITUNSET:%.*]] = icmp sgt i32 [[X_CURR]], -1, [[DBG118:!dbg !.*]]
+; LZCNT-NEXT:    [[LOOP_IV:%.*]] = phi i32 [ 0, [[ENTRY:%.*]] ], [ [[LOOP_IV_NEXT:%.*]], [[LOOP]] ], [[DBG116]]
+; LZCNT-NEXT:    [[TMP0:%.*]] = phi i32 [ [[X]], [[ENTRY]] ], [ [[TMP1:%.*]], [[LOOP]] ], [[DBG116]]
+; LZCNT-NEXT:    call void @llvm.dbg.value(metadata i32 [[TMP0]], [[META113:metadata !.*]], metadata !DIExpression()), [[DBG116]]
+; LZCNT-NEXT:    [[X_CURR_ISBITUNSET:%.*]] = icmp sgt i32 [[TMP0]], -1, [[DBG118:!dbg !.*]]
 ; LZCNT-NEXT:    call void @llvm.dbg.value(metadata i1 [[X_CURR_ISBITUNSET]], [[META114:metadata !.*]], metadata !DIExpression()), [[DBG118]]
-; LZCNT-NEXT:    [[TMP1:%.*]] = shl i32 [[X_CURR]], 1, [[DBG119:!dbg !.*]]
-; LZCNT-NEXT:    call void @llvm.dbg.value(metadata i32 [[X_NEXT]], [[META115:metadata !.*]], metadata !DIExpression()), [[DBG119]]
-; LZCNT-NEXT:    br i1 true, label [[END:%.*]], label [[LOOP]], [[DBG120:!dbg !.*]]
+; LZCNT-NEXT:    [[TMP1]] = shl i32 [[TMP0]], 1, [[DBG119:!dbg !.*]]
+; LZCNT-NEXT:    call void @llvm.dbg.value(metadata i32 [[TMP1]], [[META115:metadata !.*]], metadata !DIExpression()), [[DBG119]]
+; LZCNT-NEXT:    [[LOOP_IV_NEXT]] = add nuw i32 [[LOOP_IV]], 1, [[DBG120:!dbg !.*]]
+; LZCNT-NEXT:    [[LOOP_IVCHECK:%.*]] = icmp eq i32 [[LOOP_IV_NEXT]], [[LOOP_TRIPCOUNT]], [[DBG120]]
+; LZCNT-NEXT:    br i1 [[LOOP_IVCHECK]], label [[END:%.*]], label [[LOOP]], [[DBG120]]
 ; LZCNT:       end:
 ; LZCNT-NEXT:    [[X_CURR_LCSSA:%.*]] = phi i32 [ [[X_CURR]], [[LOOP]] ], [[DBG116]]
 ; LZCNT-NEXT:    call void @llvm.dbg.value(metadata i32 [[X_CURR_LCSSA]], [[META113]], metadata !DIExpression()), [[DBG116]]
@@ -533,15 +557,18 @@
 ; LZCNT-NEXT:    [[X_NEXT:%.*]] = shl i32 [[X]], [[LOOP_TRIPCOUNT]], [[DBG130]]
 ; LZCNT-NEXT:    br label [[LOOP:%.*]], [[DBG131:!dbg !.*]]
 ; LZCNT:       loop:
-; LZCNT-NEXT:    [[TMP0:%.*]] = phi i32 [ [[X]], [[ENTRY:%.*]] ], [ [[X_NEXT]], [[LOOP]] ], [[DBG130]]
-; LZCNT-NEXT:    call void @llvm.dbg.value(metadata i32 [[X_CURR]], [[META125:metadata !.*]], metadata !DIExpression()), [[DBG130]]
-; LZCNT-NEXT:    [[X_CURR_BITMASKED:%.*]] = and i32 [[X_CURR]], [[BITMASK]], [[DBG132:!dbg !.*]]
+; LZCNT-NEXT:    [[LOOP_IV:%.*]] = phi i32 [ 0, [[ENTRY:%.*]] ], [ [[LOOP_IV_NEXT:%.*]], [[LOOP]] ], [[DBG130]]
+; LZCNT-NEXT:    [[TMP0:%.*]] = phi i32 [ [[X]], [[ENTRY]] ], [ [[TMP1:%.*]], [[LOOP]] ], [[DBG130]]
+; LZCNT-NEXT:    call void @llvm.dbg.value(metadata i32 [[TMP0]], [[META125:metadata !.*]], metadata !DIExpression()), [[DBG130]]
+; LZCNT-NEXT:    [[X_CURR_BITMASKED:%.*]] = and i32 [[TMP0]], [[BITMASK]], [[DBG132:!dbg !.*]]
 ; LZCNT-NEXT:    call void @llvm.dbg.value(metadata i32 [[X_CURR_BITMASKED]], [[META126:metadata !.*]], metadata !DIExpression()), [[DBG132]]
 ; LZCNT-NEXT:    [[X_CURR_ISBITUNSET:%.*]] = icmp ne i32 [[X_CURR_BITMASKED]], 0, [[DBG133:!dbg !.*]]
 ; LZCNT-NEXT:    call void @llvm.dbg.value(metadata i1 [[X_CURR_ISBITUNSET]], [[META127:metadata !.*]], metadata !DIExpression()), [[DBG133]]
-; LZCNT-NEXT:    [[TMP1:%.*]] = shl i32 [[X_CURR]], 1, [[DBG134:!dbg !.*]]
-; LZCNT-NEXT:    call void @llvm.dbg.value(metadata i32 [[X_NEXT]], [[META128:metadata !.*]], metadata !DIExpression()), [[DBG134]]
-; LZCNT-NEXT:    br i1 true, label [[END:%.*]], label [[LOOP]], [[DBG135:!dbg !.*]]
+; LZCNT-NEXT:    [[TMP1]] = shl i32 [[TMP0]], 1, [[DBG134:!dbg !.*]]
+; LZCNT-NEXT:    call void @llvm.dbg.value(metadata i32 [[TMP1]], [[META128:metadata !.*]], metadata !DIExpression()), [[DBG134]]
+; LZCNT-NEXT:    [[LOOP_IV_NEXT]] = add nuw i32 [[LOOP_IV]], 1, [[DBG135:!dbg !.*]]
+; LZCNT-NEXT:    [[LOOP_IVCHECK:%.*]] = icmp eq i32 [[LOOP_IV_NEXT]], [[LOOP_TRIPCOUNT]], [[DBG135]]
+; LZCNT-NEXT:    br i1 [[LOOP_IVCHECK]], label [[END:%.*]], label [[LOOP]], [[DBG135]]
 ; LZCNT:       end:
 ; LZCNT-NEXT:    [[X_CURR_LCSSA:%.*]] = phi i32 [ [[X_CURR]], [[LOOP]] ], [[DBG130]]
 ; LZCNT-NEXT:    call void @llvm.dbg.value(metadata i32 [[X_CURR_LCSSA]], [[META125]], metadata !DIExpression()), [[DBG130]]
@@ -600,15 +627,18 @@
 ; LZCNT-NEXT:    [[X_NEXT:%.*]] = shl i32 [[X]], [[LOOP_TRIPCOUNT]], [[DBG145]]
 ; LZCNT-NEXT:    br label [[LOOP:%.*]], [[DBG146:!dbg !.*]]
 ; LZCNT:       loop:
-; LZCNT-NEXT:    [[TMP0:%.*]] = phi i32 [ [[X]], [[ENTRY:%.*]] ], [ [[X_NEXT]], [[LOOP]] ], [[DBG145]]
-; LZCNT-NEXT:    call void @llvm.dbg.value(metadata i32 [[X_CURR]], [[META140:metadata !.*]], metadata !DIExpression()), [[DBG145]]
-; LZCNT-NEXT:    [[X_CURR_BITMASKED:%.*]] = and i32 [[BITMASK]], [[X_CURR]], [[DBG147:!dbg !.*]]
+; LZCNT-NEXT:    [[LOOP_IV:%.*]] = phi i32 [ 0, [[ENTRY:%.*]] ], [ [[LOOP_IV_NEXT:%.*]], [[LOOP]] ], [[DBG145]]
+; LZCNT-NEXT:    [[TMP0:%.*]] = phi i32 [ [[X]], [[ENTRY]] ], [ [[TMP1:%.*]], [[LOOP]] ], [[DBG145]]
+; LZCNT-NEXT:    call void @llvm.dbg.value(metadata i32 [[TMP0]], [[META140:metadata !.*]], metadata !DIExpression()), [[DBG145]]
+; LZCNT-NEXT:    [[X_CURR_BITMASKED:%.*]] = and i32 [[BITMASK]], [[TMP0]], [[DBG147:!dbg !.*]]
 ; LZCNT-NEXT:    call void @llvm.dbg.value(metadata i32 [[X_CURR_BITMASKED]], [[META141:metadata !.*]], metadata !DIExpression()), [[DBG147]]
 ; LZCNT-NEXT:    [[X_CURR_ISBITUNSET:%.*]] = icmp eq i32 [[X_CURR_BITMASKED]], 0, [[DBG148:!dbg !.*]]
 ; LZCNT-NEXT:    call void @llvm.dbg.value(metadata i1 [[X_CURR_ISBITUNSET]], [[META142:metadata !.*]], metadata !DIExpression()), [[DBG148]]
-; LZCNT-NEXT:    [[TMP1:%.*]] = shl i32 [[X_CURR]], 1, [[DBG149:!dbg !.*]]
-; LZCNT-NEXT:    call void @llvm.dbg.value(metadata i32 [[X_NEXT]], [[META143:metadata !.*]], metadata !DIExpression()), [[DBG149]]
-; LZCNT-NEXT:    br i1 true, label [[END:%.*]], label [[LOOP]], [[DBG150:!dbg !.*]]
+; LZCNT-NEXT:    [[TMP1]] = shl i32 [[TMP0]], 1, [[DBG149:!dbg !.*]]
+; LZCNT-NEXT:    call void @llvm.dbg.value(metadata i32 [[TMP1]], [[META143:metadata !.*]], metadata !DIExpression()), [[DBG149]]
+; LZCNT-NEXT:    [[LOOP_IV_NEXT]] = add nuw i32 [[LOOP_IV]], 1, [[DBG150:!dbg !.*]]
+; LZCNT-NEXT:    [[LOOP_IVCHECK:%.*]] = icmp eq i32 [[LOOP_IV_NEXT]], [[LOOP_TRIPCOUNT]], [[DBG150]]
+; LZCNT-NEXT:    br i1 [[LOOP_IVCHECK]], label [[END:%.*]], label [[LOOP]], [[DBG150]]
 ; LZCNT:       end:
 ; LZCNT-NEXT:    [[X_CURR_LCSSA:%.*]] = phi i32 [ [[X_CURR]], [[LOOP]] ], [[DBG145]]
 ; LZCNT-NEXT:    call void @llvm.dbg.value(metadata i32 [[X_CURR_LCSSA]], [[META140]], metadata !DIExpression()), [[DBG145]]
@@ -668,15 +698,18 @@
 ; LZCNT-NEXT:    [[X_NEXT:%.*]] = shl i32 [[X]], [[LOOP_TRIPCOUNT]], [[DBG160]]
 ; LZCNT-NEXT:    br label [[LOOP:%.*]], [[DBG161:!dbg !.*]]
 ; LZCNT:       loop:
-; LZCNT-NEXT:    [[TMP0:%.*]] = phi i32 [ [[X_NEXT]], [[LOOP]] ], [ [[X]], [[ENTRY:%.*]] ], [[DBG160]]
-; LZCNT-NEXT:    call void @llvm.dbg.value(metadata i32 [[X_CURR]], [[META155:metadata !.*]], metadata !DIExpression()), [[DBG160]]
-; LZCNT-NEXT:    [[X_CURR_BITMASKED:%.*]] = and i32 [[X_CURR]], [[BITMASK]], [[DBG162:!dbg !.*]]
+; LZCNT-NEXT:    [[LOOP_IV:%.*]] = phi i32 [ 0, [[ENTRY:%.*]] ], [ [[LOOP_IV_NEXT:%.*]], [[LOOP]] ], [[DBG160]]
+; LZCNT-NEXT:    [[TMP0:%.*]] = phi i32 [ [[TMP1:%.*]], [[LOOP]] ], [ [[X]], [[ENTRY]] ], [[DBG160]]
+; LZCNT-NEXT:    call void @llvm.dbg.value(metadata i32 [[TMP0]], [[META155:metadata !.*]], metadata !DIExpression()), [[DBG160]]
+; LZCNT-NEXT:    [[X_CURR_BITMASKED:%.*]] = and i32 [[TMP0]], [[BITMASK]], [[DBG162:!dbg !.*]]
 ; LZCNT-NEXT:    call void @llvm.dbg.value(metadata i32 [[X_CURR_BITMASKED]], [[META156:metadata !.*]], metadata !DIExpression()), [[DBG162]]
 ; LZCNT-NEXT:    [[X_CURR_ISBITUNSET:%.*]] = icmp eq i32 [[X_CURR_BITMASKED]], 0, [[DBG163:!dbg !.*]]
 ; LZCNT-NEXT:    call void @llvm.dbg.value(metadata i1 [[X_CURR_ISBITUNSET]], [[META157:metadata !.*]], metadata !DIExpression()), [[DBG163]]
-; LZCNT-NEXT:    [[TMP1:%.*]] = shl i32 [[X_CURR]], 1, [[DBG164:!dbg !.*]]
-; LZCNT-NEXT:    call void @llvm.dbg.value(metadata i32 [[X_NEXT]], [[META158:metadata !.*]], metadata !DIExpression()), [[DBG164]]
-; LZCNT-NEXT:    br i1 true, label [[END:%.*]], label [[LOOP]], [[DBG165:!dbg !.*]]
+; LZCNT-NEXT:    [[TMP1]] = shl i32 [[TMP0]], 1, [[DBG164:!dbg !.*]]
+; LZCNT-NEXT:    call void @llvm.dbg.value(metadata i32 [[TMP1]], [[META158:metadata !.*]], metadata !DIExpression()), [[DBG164]]
+; LZCNT-NEXT:    [[LOOP_IV_NEXT]] = add nuw i32 [[LOOP_IV]], 1, [[DBG165:!dbg !.*]]
+; LZCNT-NEXT:    [[LOOP_IVCHECK:%.*]] = icmp eq i32 [[LOOP_IV_NEXT]], [[LOOP_TRIPCOUNT]], [[DBG165]]
+; LZCNT-NEXT:    br i1 [[LOOP_IVCHECK]], label [[END:%.*]], label [[LOOP]], [[DBG165]]
 ; LZCNT:       end:
 ; LZCNT-NEXT:    [[X_CURR_LCSSA:%.*]] = phi i32 [ [[X_CURR]], [[LOOP]] ], [[DBG160]]
 ; LZCNT-NEXT:    call void @llvm.dbg.value(metadata i32 [[X_CURR_LCSSA]], [[META155]], metadata !DIExpression()), [[DBG160]]
@@ -730,13 +763,16 @@
 ; LZCNT-NEXT:    [[X_NEXT:%.*]] = shl i32 [[X]], [[LOOP_TRIPCOUNT]], [[DBG172]]
 ; LZCNT-NEXT:    br label [[LOOP:%.*]], [[DBG173:!dbg !.*]]
 ; LZCNT:       loop:
-; LZCNT-NEXT:    [[TMP0:%.*]] = phi i32 [ [[X]], [[ENTRY:%.*]] ], [ [[X_NEXT]], [[LOOP]] ], [[DBG172]]
-; LZCNT-NEXT:    call void @llvm.dbg.value(metadata i32 [[X_CURR]], [[META169:metadata !.*]], metadata !DIExpression()), [[DBG172]]
-; LZCNT-NEXT:    [[X_CURR_ISBITUNSET:%.*]] = icmp slt i32 [[X_CURR]], 0, [[DBG174:!dbg !.*]]
+; LZCNT-NEXT:    [[LOOP_IV:%.*]] = phi i32 [ 0, [[ENTRY:%.*]] ], [ [[LOOP_IV_NEXT:%.*]], [[LOOP]] ], [[DBG172]]
+; LZCNT-NEXT:    [[TMP0:%.*]] = phi i32 [ [[X]], [[ENTRY]] ], [ [[TMP1:%.*]], [[LOOP]] ], [[DBG172]]
+; LZCNT-NEXT:    call void @llvm.dbg.value(metadata i32 [[TMP0]], [[META169:metadata !.*]], metadata !DIExpression()), [[DBG172]]
+; LZCNT-NEXT:    [[X_CURR_ISBITUNSET:%.*]] = icmp slt i32 [[TMP0]], 0, [[DBG174:!dbg !.*]]
 ; LZCNT-NEXT:    call void @llvm.dbg.value(metadata i1 [[X_CURR_ISBITUNSET]], [[META170:metadata !.*]], metadata !DIExpression()), [[DBG174]]
-; LZCNT-NEXT:    [[TMP1:%.*]] = shl i32 [[X_CURR]], 1, [[DBG175:!dbg !.*]]
-; LZCNT-NEXT:    call void @llvm.dbg.value(metadata i32 [[X_NEXT]], [[META171:metadata !.*]], metadata !DIExpression()), [[DBG175]]
-; LZCNT-NEXT:    br i1 true, label [[END:%.*]], label [[LOOP]], [[DBG176:!dbg !.*]]
+; LZCNT-NEXT:    [[TMP1]] = shl i32 [[TMP0]], 1, [[DBG175:!dbg !.*]]
+; LZCNT-NEXT:    call void @llvm.dbg.value(metadata i32 [[TMP1]], [[META171:metadata !.*]], metadata !DIExpression()), [[DBG175]]
+; LZCNT-NEXT:    [[LOOP_IV_NEXT]] = add nuw i32 [[LOOP_IV]], 1, [[DBG176:!dbg !.*]]
+; LZCNT-NEXT:    [[LOOP_IVCHECK:%.*]] = icmp eq i32 [[LOOP_IV_NEXT]], [[LOOP_TRIPCOUNT]], [[DBG176]]
+; LZCNT-NEXT:    br i1 [[LOOP_IVCHECK]], label [[END:%.*]], label [[LOOP]], [[DBG176]]
 ; LZCNT:       end:
 ; LZCNT-NEXT:    [[X_CURR_LCSSA:%.*]] = phi i32 [ [[X_CURR]], [[LOOP]] ], [[DBG172]]
 ; LZCNT-NEXT:    call void @llvm.dbg.value(metadata i32 [[X_CURR_LCSSA]], [[META169]], metadata !DIExpression()), [[DBG172]]
@@ -1283,28 +1319,62 @@
 ;-------------------------------------------------------------------------------
 ; Tests with extra cruft.
 
-; If loop body has any extra instructions we don't want to deal with it.
-define i32 @n26(i32 %x, i32 %bit) {
-; ALL-LABEL: @n26(
-; ALL-NEXT:  entry:
-; ALL-NEXT:    [[BITMASK:%.*]] = shl i32 1, [[BIT:%.*]], [[DBG389:!dbg !.*]]
-; ALL-NEXT:    call void @llvm.dbg.value(metadata i32 [[BITMASK]], [[META384:metadata !.*]], metadata !DIExpression()), [[DBG389]]
-; ALL-NEXT:    br label [[LOOP:%.*]], [[DBG390:!dbg !.*]]
-; ALL:       loop:
-; ALL-NEXT:    [[X_CURR:%.*]] = phi i32 [ [[X:%.*]], [[ENTRY:%.*]] ], [ [[X_NEXT:%.*]], [[LOOP]] ], [[DBG391:!dbg !.*]]
-; ALL-NEXT:    call void @llvm.dbg.value(metadata i32 [[X_CURR]], [[META385:metadata !.*]], metadata !DIExpression()), [[DBG391]]
-; ALL-NEXT:    call void @external_side_effect(), [[DBG392:!dbg !.*]]
-; ALL-NEXT:    [[X_CURR_BITMASKED:%.*]] = and i32 [[X_CURR]], [[BITMASK]], [[DBG393:!dbg !.*]]
-; ALL-NEXT:    call void @llvm.dbg.value(metadata i32 [[X_CURR_BITMASKED]], [[META386:metadata !.*]], metadata !DIExpression()), [[DBG393]]
-; ALL-NEXT:    [[X_CURR_ISBITUNSET:%.*]] = icmp eq i32 [[X_CURR_BITMASKED]], 0, [[DBG394:!dbg !.*]]
-; ALL-NEXT:    call void @llvm.dbg.value(metadata i1 [[X_CURR_ISBITUNSET]], [[META387:metadata !.*]], metadata !DIExpression()), [[DBG394]]
-; ALL-NEXT:    [[X_NEXT]] = shl i32 [[X_CURR]], 1, [[DBG395:!dbg !.*]]
-; ALL-NEXT:    call void @llvm.dbg.value(metadata i32 [[X_NEXT]], [[META388:metadata !.*]], metadata !DIExpression()), [[DBG395]]
-; ALL-NEXT:    br i1 [[X_CURR_ISBITUNSET]], label [[LOOP]], label [[END:%.*]], [[DBG396:!dbg !.*]]
-; ALL:       end:
-; ALL-NEXT:    [[X_CURR_LCSSA:%.*]] = phi i32 [ [[X_CURR]], [[LOOP]] ], [[DBG391]]
-; ALL-NEXT:    call void @llvm.dbg.value(metadata i32 [[X_CURR_LCSSA]], [[META385]], metadata !DIExpression()), [[DBG391]]
-; ALL-NEXT:    ret i32 [[X_CURR_LCSSA]], [[DBG397:!dbg !.*]]
+; If loop body has any extra instructions, we still want to make it countable.
+define i32 @p26(i32 %x, i32 %bit) {
+; LZCNT-LABEL: @p26(
+; LZCNT-NEXT:  entry:
+; LZCNT-NEXT:    [[BITMASK:%.*]] = shl i32 1, [[BIT:%.*]], [[DBG389:!dbg !.*]]
+; LZCNT-NEXT:    call void @llvm.dbg.value(metadata i32 [[BITMASK]], [[META384:metadata !.*]], metadata !DIExpression()), [[DBG389]]
+; LZCNT-NEXT:    [[BIT_LOWBITMASK:%.*]] = add i32 [[BITMASK]], -1, [[DBG390:!dbg !.*]]
+; LZCNT-NEXT:    [[BIT_MASK:%.*]] = or i32 [[BIT_LOWBITMASK]], [[BITMASK]], [[DBG390]]
+; LZCNT-NEXT:    [[X_MASKED:%.*]] = and i32 [[X:%.*]], [[BIT_MASK]], [[DBG390]]
+; LZCNT-NEXT:    [[X_MASKED_NUMLEADINGZEROS:%.*]] = call i32 @llvm.ctlz.i32(i32 [[X_MASKED]], i1 true), [[DBG390]]
+; LZCNT-NEXT:    [[X_MASKED_NUMACTIVEBITS:%.*]] = sub i32 32, [[X_MASKED_NUMLEADINGZEROS]], [[DBG390]]
+; LZCNT-NEXT:    [[X_MASKED_NUMLEADINGONEPOS:%.*]] = add i32 [[X_MASKED_NUMACTIVEBITS]], -1, [[DBG390]]
+; LZCNT-NEXT:    [[LOOP_BACKEDGETAKENCOUNT:%.*]] = sub i32 [[BIT]], [[X_MASKED_NUMLEADINGONEPOS]], [[DBG390]]
+; LZCNT-NEXT:    [[LOOP_TRIPCOUNT:%.*]] = add nuw i32 [[LOOP_BACKEDGETAKENCOUNT]], 1, [[DBG390]]
+; LZCNT-NEXT:    [[X_CURR:%.*]] = shl i32 [[X]], [[LOOP_BACKEDGETAKENCOUNT]], [[DBG390]]
+; LZCNT-NEXT:    [[X_NEXT:%.*]] = shl i32 [[X]], [[LOOP_TRIPCOUNT]], [[DBG390]]
+; LZCNT-NEXT:    br label [[LOOP:%.*]], [[DBG391:!dbg !.*]]
+; LZCNT:       loop:
+; LZCNT-NEXT:    [[LOOP_IV:%.*]] = phi i32 [ 0, [[ENTRY:%.*]] ], [ [[LOOP_IV_NEXT:%.*]], [[LOOP]] ], [[DBG390]]
+; LZCNT-NEXT:    [[TMP0:%.*]] = phi i32 [ [[X]], [[ENTRY]] ], [ [[TMP1:%.*]], [[LOOP]] ], [[DBG390]]
+; LZCNT-NEXT:    call void @llvm.dbg.value(metadata i32 [[TMP0]], [[META385:metadata !.*]], metadata !DIExpression()), [[DBG390]]
+; LZCNT-NEXT:    call void @external_side_effect(), [[DBG392:!dbg !.*]]
+; LZCNT-NEXT:    [[X_CURR_BITMASKED:%.*]] = and i32 [[TMP0]], [[BITMASK]], [[DBG393:!dbg !.*]]
+; LZCNT-NEXT:    call void @llvm.dbg.value(metadata i32 [[X_CURR_BITMASKED]], [[META386:metadata !.*]], metadata !DIExpression()), [[DBG393]]
+; LZCNT-NEXT:    [[X_CURR_ISBITUNSET:%.*]] = icmp eq i32 [[X_CURR_BITMASKED]], 0, [[DBG394:!dbg !.*]]
+; LZCNT-NEXT:    call void @llvm.dbg.value(metadata i1 [[X_CURR_ISBITUNSET]], [[META387:metadata !.*]], metadata !DIExpression()), [[DBG394]]
+; LZCNT-NEXT:    [[TMP1]] = shl i32 [[TMP0]], 1, [[DBG395:!dbg !.*]]
+; LZCNT-NEXT:    call void @llvm.dbg.value(metadata i32 [[TMP1]], [[META388:metadata !.*]], metadata !DIExpression()), [[DBG395]]
+; LZCNT-NEXT:    [[LOOP_IV_NEXT]] = add nuw i32 [[LOOP_IV]], 1, [[DBG396:!dbg !.*]]
+; LZCNT-NEXT:    [[LOOP_IVCHECK:%.*]] = icmp eq i32 [[LOOP_IV_NEXT]], [[LOOP_TRIPCOUNT]], [[DBG396]]
+; LZCNT-NEXT:    br i1 [[LOOP_IVCHECK]], label [[END:%.*]], label [[LOOP]], [[DBG396]]
+; LZCNT:       end:
+; LZCNT-NEXT:    [[X_CURR_LCSSA:%.*]] = phi i32 [ [[X_CURR]], [[LOOP]] ], [[DBG390]]
+; LZCNT-NEXT:    call void @llvm.dbg.value(metadata i32 [[X_CURR_LCSSA]], [[META385]], metadata !DIExpression()), [[DBG390]]
+; LZCNT-NEXT:    ret i32 [[X_CURR_LCSSA]], [[DBG397:!dbg !.*]]
+;
+; NOLZCNT-LABEL: @p26(
+; NOLZCNT-NEXT:  entry:
+; NOLZCNT-NEXT:    [[BITMASK:%.*]] = shl i32 1, [[BIT:%.*]], [[DBG389:!dbg !.*]]
+; NOLZCNT-NEXT:    call void @llvm.dbg.value(metadata i32 [[BITMASK]], [[META384:metadata !.*]], metadata !DIExpression()), [[DBG389]]
+; NOLZCNT-NEXT:    br label [[LOOP:%.*]], [[DBG390:!dbg !.*]]
+; NOLZCNT:       loop:
+; NOLZCNT-NEXT:    [[X_CURR:%.*]] = phi i32 [ [[X:%.*]], [[ENTRY:%.*]] ], [ [[X_NEXT:%.*]], [[LOOP]] ], [[DBG391:!dbg !.*]]
+; NOLZCNT-NEXT:    call void @llvm.dbg.value(metadata i32 [[X_CURR]], [[META385:metadata !.*]], metadata !DIExpression()), [[DBG391]]
+; NOLZCNT-NEXT:    call void @external_side_effect(), [[DBG392:!dbg !.*]]
+; NOLZCNT-NEXT:    [[X_CURR_BITMASKED:%.*]] = and i32 [[X_CURR]], [[BITMASK]], [[DBG393:!dbg !.*]]
+; NOLZCNT-NEXT:    call void @llvm.dbg.value(metadata i32 [[X_CURR_BITMASKED]], [[META386:metadata !.*]], metadata !DIExpression()), [[DBG393]]
+; NOLZCNT-NEXT:    [[X_CURR_ISBITUNSET:%.*]] = icmp eq i32 [[X_CURR_BITMASKED]], 0, [[DBG394:!dbg !.*]]
+; NOLZCNT-NEXT:    call void @llvm.dbg.value(metadata i1 [[X_CURR_ISBITUNSET]], [[META387:metadata !.*]], metadata !DIExpression()), [[DBG394]]
+; NOLZCNT-NEXT:    [[X_NEXT]] = shl i32 [[X_CURR]], 1, [[DBG395:!dbg !.*]]
+; NOLZCNT-NEXT:    call void @llvm.dbg.value(metadata i32 [[X_NEXT]], [[META388:metadata !.*]], metadata !DIExpression()), [[DBG395]]
+; NOLZCNT-NEXT:    br i1 [[X_CURR_ISBITUNSET]], label [[LOOP]], label [[END:%.*]], [[DBG396:!dbg !.*]]
+; NOLZCNT:       end:
+; NOLZCNT-NEXT:    [[X_CURR_LCSSA:%.*]] = phi i32 [ [[X_CURR]], [[LOOP]] ], [[DBG391]]
+; NOLZCNT-NEXT:    call void @llvm.dbg.value(metadata i32 [[X_CURR_LCSSA]], [[META385]], metadata !DIExpression()), [[DBG391]]
+; NOLZCNT-NEXT:    ret i32 [[X_CURR_LCSSA]], [[DBG397:!dbg !.*]]
 ;
 entry:
   %bitmask = shl i32 1, %bit
@@ -1322,23 +1392,50 @@
   ret i32 %x.curr
 }
 
-define i32 @n27(i32 %x) {
-; ALL-LABEL: @n27(
-; ALL-NEXT:  entry:
-; ALL-NEXT:    br label [[LOOP:%.*]], [[DBG403:!dbg !.*]]
-; ALL:       loop:
-; ALL-NEXT:    [[X_CURR:%.*]] = phi i32 [ [[X:%.*]], [[ENTRY:%.*]] ], [ [[X_NEXT:%.*]], [[LOOP]] ], [[DBG404:!dbg !.*]]
-; ALL-NEXT:    call void @llvm.dbg.value(metadata i32 [[X_CURR]], [[META400:metadata !.*]], metadata !DIExpression()), [[DBG404]]
-; ALL-NEXT:    call void @external_side_effect(), [[DBG405:!dbg !.*]]
-; ALL-NEXT:    [[X_CURR_ISBITUNSET:%.*]] = icmp sgt i32 [[X_CURR]], -1, [[DBG406:!dbg !.*]]
-; ALL-NEXT:    call void @llvm.dbg.value(metadata i1 [[X_CURR_ISBITUNSET]], [[META401:metadata !.*]], metadata !DIExpression()), [[DBG406]]
-; ALL-NEXT:    [[X_NEXT]] = shl i32 [[X_CURR]], 1, [[DBG407:!dbg !.*]]
-; ALL-NEXT:    call void @llvm.dbg.value(metadata i32 [[X_NEXT]], [[META402:metadata !.*]], metadata !DIExpression()), [[DBG407]]
-; ALL-NEXT:    br i1 [[X_CURR_ISBITUNSET]], label [[LOOP]], label [[END:%.*]], [[DBG408:!dbg !.*]]
-; ALL:       end:
-; ALL-NEXT:    [[X_CURR_LCSSA:%.*]] = phi i32 [ [[X_CURR]], [[LOOP]] ], [[DBG404]]
-; ALL-NEXT:    call void @llvm.dbg.value(metadata i32 [[X_CURR_LCSSA]], [[META400]], metadata !DIExpression()), [[DBG404]]
-; ALL-NEXT:    ret i32 [[X_CURR_LCSSA]], [[DBG409:!dbg !.*]]
+define i32 @p27(i32 %x) {
+; LZCNT-LABEL: @p27(
+; LZCNT-NEXT:  entry:
+; LZCNT-NEXT:    [[X_NUMLEADINGZEROS:%.*]] = call i32 @llvm.ctlz.i32(i32 [[X:%.*]], i1 true), [[DBG403:!dbg !.*]]
+; LZCNT-NEXT:    [[X_NUMACTIVEBITS:%.*]] = sub i32 32, [[X_NUMLEADINGZEROS]], [[DBG403]]
+; LZCNT-NEXT:    [[X_NUMLEADINGONEPOS:%.*]] = add i32 [[X_NUMACTIVEBITS]], -1, [[DBG403]]
+; LZCNT-NEXT:    [[LOOP_BACKEDGETAKENCOUNT:%.*]] = sub i32 31, [[X_NUMLEADINGONEPOS]], [[DBG403]]
+; LZCNT-NEXT:    [[LOOP_TRIPCOUNT:%.*]] = add nuw i32 [[LOOP_BACKEDGETAKENCOUNT]], 1, [[DBG403]]
+; LZCNT-NEXT:    [[X_CURR:%.*]] = shl i32 [[X]], [[LOOP_BACKEDGETAKENCOUNT]], [[DBG403]]
+; LZCNT-NEXT:    [[X_NEXT:%.*]] = shl i32 [[X]], [[LOOP_TRIPCOUNT]], [[DBG403]]
+; LZCNT-NEXT:    br label [[LOOP:%.*]], [[DBG404:!dbg !.*]]
+; LZCNT:       loop:
+; LZCNT-NEXT:    [[LOOP_IV:%.*]] = phi i32 [ 0, [[ENTRY:%.*]] ], [ [[LOOP_IV_NEXT:%.*]], [[LOOP]] ], [[DBG403]]
+; LZCNT-NEXT:    [[TMP0:%.*]] = phi i32 [ [[X]], [[ENTRY]] ], [ [[TMP1:%.*]], [[LOOP]] ], [[DBG403]]
+; LZCNT-NEXT:    call void @llvm.dbg.value(metadata i32 [[TMP0]], [[META400:metadata !.*]], metadata !DIExpression()), [[DBG403]]
+; LZCNT-NEXT:    call void @external_side_effect(), [[DBG405:!dbg !.*]]
+; LZCNT-NEXT:    [[X_CURR_ISBITUNSET:%.*]] = icmp sgt i32 [[TMP0]], -1, [[DBG406:!dbg !.*]]
+; LZCNT-NEXT:    call void @llvm.dbg.value(metadata i1 [[X_CURR_ISBITUNSET]], [[META401:metadata !.*]], metadata !DIExpression()), [[DBG406]]
+; LZCNT-NEXT:    [[TMP1]] = shl i32 [[TMP0]], 1, [[DBG407:!dbg !.*]]
+; LZCNT-NEXT:    call void @llvm.dbg.value(metadata i32 [[TMP1]], [[META402:metadata !.*]], metadata !DIExpression()), [[DBG407]]
+; LZCNT-NEXT:    [[LOOP_IV_NEXT]] = add nuw i32 [[LOOP_IV]], 1, [[DBG408:!dbg !.*]]
+; LZCNT-NEXT:    [[LOOP_IVCHECK:%.*]] = icmp eq i32 [[LOOP_IV_NEXT]], [[LOOP_TRIPCOUNT]], [[DBG408]]
+; LZCNT-NEXT:    br i1 [[LOOP_IVCHECK]], label [[END:%.*]], label [[LOOP]], [[DBG408]]
+; LZCNT:       end:
+; LZCNT-NEXT:    [[X_CURR_LCSSA:%.*]] = phi i32 [ [[X_CURR]], [[LOOP]] ], [[DBG403]]
+; LZCNT-NEXT:    call void @llvm.dbg.value(metadata i32 [[X_CURR_LCSSA]], [[META400]], metadata !DIExpression()), [[DBG403]]
+; LZCNT-NEXT:    ret i32 [[X_CURR_LCSSA]], [[DBG409:!dbg !.*]]
+;
+; NOLZCNT-LABEL: @p27(
+; NOLZCNT-NEXT:  entry:
+; NOLZCNT-NEXT:    br label [[LOOP:%.*]], [[DBG403:!dbg !.*]]
+; NOLZCNT:       loop:
+; NOLZCNT-NEXT:    [[X_CURR:%.*]] = phi i32 [ [[X:%.*]], [[ENTRY:%.*]] ], [ [[X_NEXT:%.*]], [[LOOP]] ], [[DBG404:!dbg !.*]]
+; NOLZCNT-NEXT:    call void @llvm.dbg.value(metadata i32 [[X_CURR]], [[META400:metadata !.*]], metadata !DIExpression()), [[DBG404]]
+; NOLZCNT-NEXT:    call void @external_side_effect(), [[DBG405:!dbg !.*]]
+; NOLZCNT-NEXT:    [[X_CURR_ISBITUNSET:%.*]] = icmp sgt i32 [[X_CURR]], -1, [[DBG406:!dbg !.*]]
+; NOLZCNT-NEXT:    call void @llvm.dbg.value(metadata i1 [[X_CURR_ISBITUNSET]], [[META401:metadata !.*]], metadata !DIExpression()), [[DBG406]]
+; NOLZCNT-NEXT:    [[X_NEXT]] = shl i32 [[X_CURR]], 1, [[DBG407:!dbg !.*]]
+; NOLZCNT-NEXT:    call void @llvm.dbg.value(metadata i32 [[X_NEXT]], [[META402:metadata !.*]], metadata !DIExpression()), [[DBG407]]
+; NOLZCNT-NEXT:    br i1 [[X_CURR_ISBITUNSET]], label [[LOOP]], label [[END:%.*]], [[DBG408:!dbg !.*]]
+; NOLZCNT:       end:
+; NOLZCNT-NEXT:    [[X_CURR_LCSSA:%.*]] = phi i32 [ [[X_CURR]], [[LOOP]] ], [[DBG404]]
+; NOLZCNT-NEXT:    call void @llvm.dbg.value(metadata i32 [[X_CURR_LCSSA]], [[META400]], metadata !DIExpression()), [[DBG404]]
+; NOLZCNT-NEXT:    ret i32 [[X_CURR_LCSSA]], [[DBG409:!dbg !.*]]
 ;
 entry:
   br label %loop
@@ -1354,29 +1451,64 @@
   ret i32 %x.curr
 }
 
-; In-loop instructions should not have uses outside of the loop.
-define i32 @n28(i32 %x, i32 %bit) {
-; ALL-LABEL: @n28(
-; ALL-NEXT:  entry:
-; ALL-NEXT:    [[BITMASK:%.*]] = shl i32 1, [[BIT:%.*]], [[DBG417:!dbg !.*]]
-; ALL-NEXT:    call void @llvm.dbg.value(metadata i32 [[BITMASK]], [[META412:metadata !.*]], metadata !DIExpression()), [[DBG417]]
-; ALL-NEXT:    br label [[LOOP:%.*]], [[DBG418:!dbg !.*]]
-; ALL:       loop:
-; ALL-NEXT:    [[X_CURR:%.*]] = phi i32 [ [[X:%.*]], [[ENTRY:%.*]] ], [ [[X_NEXT:%.*]], [[LOOP]] ], [[DBG419:!dbg !.*]]
-; ALL-NEXT:    call void @llvm.dbg.value(metadata i32 [[X_CURR]], [[META413:metadata !.*]], metadata !DIExpression()), [[DBG419]]
-; ALL-NEXT:    [[X_CURR_BITMASKED:%.*]] = and i32 [[X_CURR]], [[BITMASK]], [[DBG420:!dbg !.*]]
-; ALL-NEXT:    call void @llvm.dbg.value(metadata i32 [[X_CURR_BITMASKED]], [[META414:metadata !.*]], metadata !DIExpression()), [[DBG420]]
-; ALL-NEXT:    [[X_CURR_ISBITUNSET:%.*]] = icmp eq i32 [[X_CURR_BITMASKED]], 0, [[DBG421:!dbg !.*]]
-; ALL-NEXT:    call void @llvm.dbg.value(metadata i1 [[X_CURR_ISBITUNSET]], [[META415:metadata !.*]], metadata !DIExpression()), [[DBG421]]
-; ALL-NEXT:    [[X_NEXT]] = shl i32 [[X_CURR]], 1, [[DBG422:!dbg !.*]]
-; ALL-NEXT:    call void @llvm.dbg.value(metadata i32 [[X_NEXT]], [[META416:metadata !.*]], metadata !DIExpression()), [[DBG422]]
-; ALL-NEXT:    br i1 [[X_CURR_ISBITUNSET]], label [[LOOP]], label [[END:%.*]], [[DBG423:!dbg !.*]]
-; ALL:       end:
-; ALL-NEXT:    [[X_CURR_LCSSA:%.*]] = phi i32 [ [[X_CURR]], [[LOOP]] ], [[DBG419]]
-; ALL-NEXT:    [[X_CURR_BITMASKED_LCSSA:%.*]] = phi i32 [ [[X_CURR_BITMASKED]], [[LOOP]] ], [[DBG420]]
-; ALL-NEXT:    call void @llvm.dbg.value(metadata i32 [[X_CURR_LCSSA]], [[META413]], metadata !DIExpression()), [[DBG419]]
-; ALL-NEXT:    call void @use32(i32 [[X_CURR_BITMASKED_LCSSA]]), [[DBG424:!dbg !.*]]
-; ALL-NEXT:    ret i32 [[X_CURR_LCSSA]], [[DBG425:!dbg !.*]]
+; In-loop instructions can have uses outside of the loop.
+define i32 @p28(i32 %x, i32 %bit) {
+; LZCNT-LABEL: @p28(
+; LZCNT-NEXT:  entry:
+; LZCNT-NEXT:    [[BITMASK:%.*]] = shl i32 1, [[BIT:%.*]], [[DBG417:!dbg !.*]]
+; LZCNT-NEXT:    call void @llvm.dbg.value(metadata i32 [[BITMASK]], [[META412:metadata !.*]], metadata !DIExpression()), [[DBG417]]
+; LZCNT-NEXT:    [[BIT_LOWBITMASK:%.*]] = add i32 [[BITMASK]], -1, [[DBG418:!dbg !.*]]
+; LZCNT-NEXT:    [[BIT_MASK:%.*]] = or i32 [[BIT_LOWBITMASK]], [[BITMASK]], [[DBG418]]
+; LZCNT-NEXT:    [[X_MASKED:%.*]] = and i32 [[X:%.*]], [[BIT_MASK]], [[DBG418]]
+; LZCNT-NEXT:    [[X_MASKED_NUMLEADINGZEROS:%.*]] = call i32 @llvm.ctlz.i32(i32 [[X_MASKED]], i1 true), [[DBG418]]
+; LZCNT-NEXT:    [[X_MASKED_NUMACTIVEBITS:%.*]] = sub i32 32, [[X_MASKED_NUMLEADINGZEROS]], [[DBG418]]
+; LZCNT-NEXT:    [[X_MASKED_NUMLEADINGONEPOS:%.*]] = add i32 [[X_MASKED_NUMACTIVEBITS]], -1, [[DBG418]]
+; LZCNT-NEXT:    [[LOOP_BACKEDGETAKENCOUNT:%.*]] = sub i32 [[BIT]], [[X_MASKED_NUMLEADINGONEPOS]], [[DBG418]]
+; LZCNT-NEXT:    [[LOOP_TRIPCOUNT:%.*]] = add nuw i32 [[LOOP_BACKEDGETAKENCOUNT]], 1, [[DBG418]]
+; LZCNT-NEXT:    [[X_CURR:%.*]] = shl i32 [[X]], [[LOOP_BACKEDGETAKENCOUNT]], [[DBG418]]
+; LZCNT-NEXT:    [[X_NEXT:%.*]] = shl i32 [[X]], [[LOOP_TRIPCOUNT]], [[DBG418]]
+; LZCNT-NEXT:    br label [[LOOP:%.*]], [[DBG419:!dbg !.*]]
+; LZCNT:       loop:
+; LZCNT-NEXT:    [[LOOP_IV:%.*]] = phi i32 [ 0, [[ENTRY:%.*]] ], [ [[LOOP_IV_NEXT:%.*]], [[LOOP]] ], [[DBG418]]
+; LZCNT-NEXT:    [[TMP0:%.*]] = phi i32 [ [[X]], [[ENTRY]] ], [ [[TMP1:%.*]], [[LOOP]] ], [[DBG418]]
+; LZCNT-NEXT:    call void @llvm.dbg.value(metadata i32 [[TMP0]], [[META413:metadata !.*]], metadata !DIExpression()), [[DBG418]]
+; LZCNT-NEXT:    [[X_CURR_BITMASKED:%.*]] = and i32 [[TMP0]], [[BITMASK]], [[DBG420:!dbg !.*]]
+; LZCNT-NEXT:    call void @llvm.dbg.value(metadata i32 [[X_CURR_BITMASKED]], [[META414:metadata !.*]], metadata !DIExpression()), [[DBG420]]
+; LZCNT-NEXT:    [[X_CURR_ISBITUNSET:%.*]] = icmp eq i32 [[X_CURR_BITMASKED]], 0, [[DBG421:!dbg !.*]]
+; LZCNT-NEXT:    call void @llvm.dbg.value(metadata i1 [[X_CURR_ISBITUNSET]], [[META415:metadata !.*]], metadata !DIExpression()), [[DBG421]]
+; LZCNT-NEXT:    [[TMP1]] = shl i32 [[TMP0]], 1, [[DBG422:!dbg !.*]]
+; LZCNT-NEXT:    call void @llvm.dbg.value(metadata i32 [[TMP1]], [[META416:metadata !.*]], metadata !DIExpression()), [[DBG422]]
+; LZCNT-NEXT:    [[LOOP_IV_NEXT]] = add nuw i32 [[LOOP_IV]], 1, [[DBG423:!dbg !.*]]
+; LZCNT-NEXT:    [[LOOP_IVCHECK:%.*]] = icmp eq i32 [[LOOP_IV_NEXT]], [[LOOP_TRIPCOUNT]], [[DBG423]]
+; LZCNT-NEXT:    br i1 [[LOOP_IVCHECK]], label [[END:%.*]], label [[LOOP]], [[DBG423]]
+; LZCNT:       end:
+; LZCNT-NEXT:    [[X_CURR_LCSSA:%.*]] = phi i32 [ [[X_CURR]], [[LOOP]] ], [[DBG418]]
+; LZCNT-NEXT:    [[X_CURR_BITMASKED_LCSSA:%.*]] = phi i32 [ [[X_CURR_BITMASKED]], [[LOOP]] ], [[DBG420]]
+; LZCNT-NEXT:    call void @llvm.dbg.value(metadata i32 [[X_CURR_LCSSA]], [[META413]], metadata !DIExpression()), [[DBG418]]
+; LZCNT-NEXT:    call void @use32(i32 [[X_CURR_BITMASKED_LCSSA]]), [[DBG424:!dbg !.*]]
+; LZCNT-NEXT:    ret i32 [[X_CURR_LCSSA]], [[DBG425:!dbg !.*]]
+;
+; NOLZCNT-LABEL: @p28(
+; NOLZCNT-NEXT:  entry:
+; NOLZCNT-NEXT:    [[BITMASK:%.*]] = shl i32 1, [[BIT:%.*]], [[DBG417:!dbg !.*]]
+; NOLZCNT-NEXT:    call void @llvm.dbg.value(metadata i32 [[BITMASK]], [[META412:metadata !.*]], metadata !DIExpression()), [[DBG417]]
+; NOLZCNT-NEXT:    br label [[LOOP:%.*]], [[DBG418:!dbg !.*]]
+; NOLZCNT:       loop:
+; NOLZCNT-NEXT:    [[X_CURR:%.*]] = phi i32 [ [[X:%.*]], [[ENTRY:%.*]] ], [ [[X_NEXT:%.*]], [[LOOP]] ], [[DBG419:!dbg !.*]]
+; NOLZCNT-NEXT:    call void @llvm.dbg.value(metadata i32 [[X_CURR]], [[META413:metadata !.*]], metadata !DIExpression()), [[DBG419]]
+; NOLZCNT-NEXT:    [[X_CURR_BITMASKED:%.*]] = and i32 [[X_CURR]], [[BITMASK]], [[DBG420:!dbg !.*]]
+; NOLZCNT-NEXT:    call void @llvm.dbg.value(metadata i32 [[X_CURR_BITMASKED]], [[META414:metadata !.*]], metadata !DIExpression()), [[DBG420]]
+; NOLZCNT-NEXT:    [[X_CURR_ISBITUNSET:%.*]] = icmp eq i32 [[X_CURR_BITMASKED]], 0, [[DBG421:!dbg !.*]]
+; NOLZCNT-NEXT:    call void @llvm.dbg.value(metadata i1 [[X_CURR_ISBITUNSET]], [[META415:metadata !.*]], metadata !DIExpression()), [[DBG421]]
+; NOLZCNT-NEXT:    [[X_NEXT]] = shl i32 [[X_CURR]], 1, [[DBG422:!dbg !.*]]
+; NOLZCNT-NEXT:    call void @llvm.dbg.value(metadata i32 [[X_NEXT]], [[META416:metadata !.*]], metadata !DIExpression()), [[DBG422]]
+; NOLZCNT-NEXT:    br i1 [[X_CURR_ISBITUNSET]], label [[LOOP]], label [[END:%.*]], [[DBG423:!dbg !.*]]
+; NOLZCNT:       end:
+; NOLZCNT-NEXT:    [[X_CURR_LCSSA:%.*]] = phi i32 [ [[X_CURR]], [[LOOP]] ], [[DBG419]]
+; NOLZCNT-NEXT:    [[X_CURR_BITMASKED_LCSSA:%.*]] = phi i32 [ [[X_CURR_BITMASKED]], [[LOOP]] ], [[DBG420]]
+; NOLZCNT-NEXT:    call void @llvm.dbg.value(metadata i32 [[X_CURR_LCSSA]], [[META413]], metadata !DIExpression()), [[DBG419]]
+; NOLZCNT-NEXT:    call void @use32(i32 [[X_CURR_BITMASKED_LCSSA]]), [[DBG424:!dbg !.*]]
+; NOLZCNT-NEXT:    ret i32 [[X_CURR_LCSSA]], [[DBG425:!dbg !.*]]
 ;
 entry:
   %bitmask = shl i32 1, %bit
@@ -1393,28 +1525,63 @@
   call void @use32(i32 %x.curr.bitmasked)
   ret i32 %x.curr
 }
-define i32 @n29(i32 %x, i32 %bit) {
-; ALL-LABEL: @n29(
-; ALL-NEXT:  entry:
-; ALL-NEXT:    [[BITMASK:%.*]] = shl i32 1, [[BIT:%.*]], [[DBG433:!dbg !.*]]
-; ALL-NEXT:    call void @llvm.dbg.value(metadata i32 [[BITMASK]], [[META428:metadata !.*]], metadata !DIExpression()), [[DBG433]]
-; ALL-NEXT:    br label [[LOOP:%.*]], [[DBG434:!dbg !.*]]
-; ALL:       loop:
-; ALL-NEXT:    [[X_CURR:%.*]] = phi i32 [ [[X:%.*]], [[ENTRY:%.*]] ], [ [[X_NEXT:%.*]], [[LOOP]] ], [[DBG435:!dbg !.*]]
-; ALL-NEXT:    call void @llvm.dbg.value(metadata i32 [[X_CURR]], [[META429:metadata !.*]], metadata !DIExpression()), [[DBG435]]
-; ALL-NEXT:    [[X_CURR_BITMASKED:%.*]] = and i32 [[X_CURR]], [[BITMASK]], [[DBG436:!dbg !.*]]
-; ALL-NEXT:    call void @llvm.dbg.value(metadata i32 [[X_CURR_BITMASKED]], [[META430:metadata !.*]], metadata !DIExpression()), [[DBG436]]
-; ALL-NEXT:    [[X_CURR_ISBITUNSET:%.*]] = icmp eq i32 [[X_CURR_BITMASKED]], 0, [[DBG437:!dbg !.*]]
-; ALL-NEXT:    call void @llvm.dbg.value(metadata i1 [[X_CURR_ISBITUNSET]], [[META431:metadata !.*]], metadata !DIExpression()), [[DBG437]]
-; ALL-NEXT:    [[X_NEXT]] = shl i32 [[X_CURR]], 1, [[DBG438:!dbg !.*]]
-; ALL-NEXT:    call void @llvm.dbg.value(metadata i32 [[X_NEXT]], [[META432:metadata !.*]], metadata !DIExpression()), [[DBG438]]
-; ALL-NEXT:    br i1 [[X_CURR_ISBITUNSET]], label [[LOOP]], label [[END:%.*]], [[DBG439:!dbg !.*]]
-; ALL:       end:
-; ALL-NEXT:    [[X_CURR_LCSSA:%.*]] = phi i32 [ [[X_CURR]], [[LOOP]] ], [[DBG435]]
-; ALL-NEXT:    [[X_CURR_ISBITUNSET_LCSSA:%.*]] = phi i1 [ [[X_CURR_ISBITUNSET]], [[LOOP]] ], [[DBG437]]
-; ALL-NEXT:    call void @llvm.dbg.value(metadata i32 [[X_CURR_LCSSA]], [[META429]], metadata !DIExpression()), [[DBG435]]
-; ALL-NEXT:    call void @use1(i1 [[X_CURR_ISBITUNSET_LCSSA]]), [[DBG440:!dbg !.*]]
-; ALL-NEXT:    ret i32 [[X_CURR_LCSSA]], [[DBG441:!dbg !.*]]
+define i32 @p29(i32 %x, i32 %bit) {
+; LZCNT-LABEL: @p29(
+; LZCNT-NEXT:  entry:
+; LZCNT-NEXT:    [[BITMASK:%.*]] = shl i32 1, [[BIT:%.*]], [[DBG433:!dbg !.*]]
+; LZCNT-NEXT:    call void @llvm.dbg.value(metadata i32 [[BITMASK]], [[META428:metadata !.*]], metadata !DIExpression()), [[DBG433]]
+; LZCNT-NEXT:    [[BIT_LOWBITMASK:%.*]] = add i32 [[BITMASK]], -1, [[DBG434:!dbg !.*]]
+; LZCNT-NEXT:    [[BIT_MASK:%.*]] = or i32 [[BIT_LOWBITMASK]], [[BITMASK]], [[DBG434]]
+; LZCNT-NEXT:    [[X_MASKED:%.*]] = and i32 [[X:%.*]], [[BIT_MASK]], [[DBG434]]
+; LZCNT-NEXT:    [[X_MASKED_NUMLEADINGZEROS:%.*]] = call i32 @llvm.ctlz.i32(i32 [[X_MASKED]], i1 true), [[DBG434]]
+; LZCNT-NEXT:    [[X_MASKED_NUMACTIVEBITS:%.*]] = sub i32 32, [[X_MASKED_NUMLEADINGZEROS]], [[DBG434]]
+; LZCNT-NEXT:    [[X_MASKED_NUMLEADINGONEPOS:%.*]] = add i32 [[X_MASKED_NUMACTIVEBITS]], -1, [[DBG434]]
+; LZCNT-NEXT:    [[LOOP_BACKEDGETAKENCOUNT:%.*]] = sub i32 [[BIT]], [[X_MASKED_NUMLEADINGONEPOS]], [[DBG434]]
+; LZCNT-NEXT:    [[LOOP_TRIPCOUNT:%.*]] = add nuw i32 [[LOOP_BACKEDGETAKENCOUNT]], 1, [[DBG434]]
+; LZCNT-NEXT:    [[X_CURR:%.*]] = shl i32 [[X]], [[LOOP_BACKEDGETAKENCOUNT]], [[DBG434]]
+; LZCNT-NEXT:    [[X_NEXT:%.*]] = shl i32 [[X]], [[LOOP_TRIPCOUNT]], [[DBG434]]
+; LZCNT-NEXT:    br label [[LOOP:%.*]], [[DBG435:!dbg !.*]]
+; LZCNT:       loop:
+; LZCNT-NEXT:    [[LOOP_IV:%.*]] = phi i32 [ 0, [[ENTRY:%.*]] ], [ [[LOOP_IV_NEXT:%.*]], [[LOOP]] ], [[DBG434]]
+; LZCNT-NEXT:    [[TMP0:%.*]] = phi i32 [ [[X]], [[ENTRY]] ], [ [[TMP1:%.*]], [[LOOP]] ], [[DBG434]]
+; LZCNT-NEXT:    call void @llvm.dbg.value(metadata i32 [[TMP0]], [[META429:metadata !.*]], metadata !DIExpression()), [[DBG434]]
+; LZCNT-NEXT:    [[X_CURR_BITMASKED:%.*]] = and i32 [[TMP0]], [[BITMASK]], [[DBG436:!dbg !.*]]
+; LZCNT-NEXT:    call void @llvm.dbg.value(metadata i32 [[X_CURR_BITMASKED]], [[META430:metadata !.*]], metadata !DIExpression()), [[DBG436]]
+; LZCNT-NEXT:    [[X_CURR_ISBITUNSET:%.*]] = icmp eq i32 [[X_CURR_BITMASKED]], 0, [[DBG437:!dbg !.*]]
+; LZCNT-NEXT:    call void @llvm.dbg.value(metadata i1 [[X_CURR_ISBITUNSET]], [[META431:metadata !.*]], metadata !DIExpression()), [[DBG437]]
+; LZCNT-NEXT:    [[TMP1]] = shl i32 [[TMP0]], 1, [[DBG438:!dbg !.*]]
+; LZCNT-NEXT:    call void @llvm.dbg.value(metadata i32 [[TMP1]], [[META432:metadata !.*]], metadata !DIExpression()), [[DBG438]]
+; LZCNT-NEXT:    [[LOOP_IV_NEXT]] = add nuw i32 [[LOOP_IV]], 1, [[DBG439:!dbg !.*]]
+; LZCNT-NEXT:    [[LOOP_IVCHECK:%.*]] = icmp eq i32 [[LOOP_IV_NEXT]], [[LOOP_TRIPCOUNT]], [[DBG439]]
+; LZCNT-NEXT:    br i1 [[LOOP_IVCHECK]], label [[END:%.*]], label [[LOOP]], [[DBG439]]
+; LZCNT:       end:
+; LZCNT-NEXT:    [[X_CURR_LCSSA:%.*]] = phi i32 [ [[X_CURR]], [[LOOP]] ], [[DBG434]]
+; LZCNT-NEXT:    [[X_CURR_ISBITUNSET_LCSSA:%.*]] = phi i1 [ [[X_CURR_ISBITUNSET]], [[LOOP]] ], [[DBG437]]
+; LZCNT-NEXT:    call void @llvm.dbg.value(metadata i32 [[X_CURR_LCSSA]], [[META429]], metadata !DIExpression()), [[DBG434]]
+; LZCNT-NEXT:    call void @use1(i1 [[X_CURR_ISBITUNSET_LCSSA]]), [[DBG440:!dbg !.*]]
+; LZCNT-NEXT:    ret i32 [[X_CURR_LCSSA]], [[DBG441:!dbg !.*]]
+;
+; NOLZCNT-LABEL: @p29(
+; NOLZCNT-NEXT:  entry:
+; NOLZCNT-NEXT:    [[BITMASK:%.*]] = shl i32 1, [[BIT:%.*]], [[DBG433:!dbg !.*]]
+; NOLZCNT-NEXT:    call void @llvm.dbg.value(metadata i32 [[BITMASK]], [[META428:metadata !.*]], metadata !DIExpression()), [[DBG433]]
+; NOLZCNT-NEXT:    br label [[LOOP:%.*]], [[DBG434:!dbg !.*]]
+; NOLZCNT:       loop:
+; NOLZCNT-NEXT:    [[X_CURR:%.*]] = phi i32 [ [[X:%.*]], [[ENTRY:%.*]] ], [ [[X_NEXT:%.*]], [[LOOP]] ], [[DBG435:!dbg !.*]]
+; NOLZCNT-NEXT:    call void @llvm.dbg.value(metadata i32 [[X_CURR]], [[META429:metadata !.*]], metadata !DIExpression()), [[DBG435]]
+; NOLZCNT-NEXT:    [[X_CURR_BITMASKED:%.*]] = and i32 [[X_CURR]], [[BITMASK]], [[DBG436:!dbg !.*]]
+; NOLZCNT-NEXT:    call void @llvm.dbg.value(metadata i32 [[X_CURR_BITMASKED]], [[META430:metadata !.*]], metadata !DIExpression()), [[DBG436]]
+; NOLZCNT-NEXT:    [[X_CURR_ISBITUNSET:%.*]] = icmp eq i32 [[X_CURR_BITMASKED]], 0, [[DBG437:!dbg !.*]]
+; NOLZCNT-NEXT:    call void @llvm.dbg.value(metadata i1 [[X_CURR_ISBITUNSET]], [[META431:metadata !.*]], metadata !DIExpression()), [[DBG437]]
+; NOLZCNT-NEXT:    [[X_NEXT]] = shl i32 [[X_CURR]], 1, [[DBG438:!dbg !.*]]
+; NOLZCNT-NEXT:    call void @llvm.dbg.value(metadata i32 [[X_NEXT]], [[META432:metadata !.*]], metadata !DIExpression()), [[DBG438]]
+; NOLZCNT-NEXT:    br i1 [[X_CURR_ISBITUNSET]], label [[LOOP]], label [[END:%.*]], [[DBG439:!dbg !.*]]
+; NOLZCNT:       end:
+; NOLZCNT-NEXT:    [[X_CURR_LCSSA:%.*]] = phi i32 [ [[X_CURR]], [[LOOP]] ], [[DBG435]]
+; NOLZCNT-NEXT:    [[X_CURR_ISBITUNSET_LCSSA:%.*]] = phi i1 [ [[X_CURR_ISBITUNSET]], [[LOOP]] ], [[DBG437]]
+; NOLZCNT-NEXT:    call void @llvm.dbg.value(metadata i32 [[X_CURR_LCSSA]], [[META429]], metadata !DIExpression()), [[DBG435]]
+; NOLZCNT-NEXT:    call void @use1(i1 [[X_CURR_ISBITUNSET_LCSSA]]), [[DBG440:!dbg !.*]]
+; NOLZCNT-NEXT:    ret i32 [[X_CURR_LCSSA]], [[DBG441:!dbg !.*]]
 ;
 entry:
   %bitmask = shl i32 1, %bit