[LoopIdiomRecognize] Teach CTLZ/CTTZ idiom recognition to handle not being able to find a pre-loop check for the input being 0.

[craig.topper]

Summary

To find the zero check we look for a branch whose condition is
a zero compare with the same Value* passed to the phi for the loop.
InstCombine knows some tricks that can break this. The one I observed
is when the input to the loop is a llvm.abs intrinsic. InstCombine
rewrites icmp eq (llvm.abs X), 0 to icmp eq X, 0 since the absolute
value doesn't change 0 or produce 0 for any other inputs. I believe
the original motivating case for this tranform featured an absolute
value before the loop so we should make this work.

I didn't want to teach this pass to also look through llvm.abs as
it seemed like we'd inevitably need to teach it more things to look
through. So instead I've inserted a new zero check for this case to
select the count value the loop should produce if there was no
zero check before the loop. This new zero check will hopefully be
optimized by InstCombine and eventually determined to be unneeded
and removed. If not, it's probably still cheaper than the loop.

[spatel]

This makes sense to me, but I'm not as familiar with LIR as others, so might want to get a 2nd look.

llvm/lib/Transforms/Scalar/LoopIdiomRecognize.cpp

1781–1784

It's not clear to me what cost model metrics we're using. Does this change the equation?

llvm/test/Transforms/LoopIdiom/X86/ctlz.ll

259–260

Can you add a -O1 (or -O2?) test in a pre-commit to PhaseOrdering that starts from the IR for the actual C code we're trying to model? (could run it through -mem2reg if that makes it less obnoxious).

That way, we'll have coverage to make sure we can get through a full instcombine+LIR+instcombine sequence with the expected output.

712–715

But we do transform this loop now - update comment.

[craig.topper]

Add phase ordering test.

[craig.topper]

Update test comment.

[craig.topper]

llvm/lib/Transforms/Scalar/LoopIdiomRecognize.cpp

1781–1784

I think the cost model is if the loop just counts bits and doesn't do anything else, always expand to ctlz since the loop will get deleted. If the loop has other instructions, check if ctlz cost is TCC_Basic (for X86 I think this is is lzcnt or tzcnt intructions enabled). If is then do the transform, the loop will stay but it's trip count will be determine by the ctlz.

If the loop is going to get removed, then the extra select I'm inserting probably doesn't matter. If the loop won't get removed, I'm not sure if the extra select and icmp should be costed. In many cases there probably is a real zero check and other optimizations will remove the extra instructions. I think the original case just counted bits, but it's been a few years since I looked at it. So if we're concerned I can probably handle just the case that the loop will be removed.

[spatel]

LGTM

[craig.topper]

llvm/test/Transforms/LoopIdiom/X86/ctlz.ll

294

I think this needs to be TMP3 not TMP1.

[lebedev.ri]

Hm, i've just completed mine's recognizeShiftUntilZero(), and i thought it would resolve this,
but there the shifee is stationary, while here we have shift recurrence (always shift by one).
So more idioms to support...

[aaronpuchert]

llvm/lib/Transforms/Scalar/LoopIdiomRecognize.cpp

1811

Going with NewCount here shouldn't have unintended side effects, though we'd need to use a different Ty I think.

llvm/test/Transforms/LoopIdiom/X86/ctlz.ll

294

Agreed. They differ for ABS_N = 0 where TMP1 = 0 but TMP3 = 1. With TCPHI = 0 we get TCDEC = -1 hence TOBOOL = false in the first iteration, so we don't exit as we should. In fact we'll eventually violate the nsw I think.

[lebedev.ri]

This review may be stuck/dead, consider abandoning if no longer relevant.
Removing myself as reviewer in attempt to clean dashboard.

llvm/lib/Transforms/Scalar/LoopIdiomRecognize.cpp

 //===- LoopIdiomRecognize.cpp - Loop idiom recognition --------------------===//
 //
 // Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
 // See https://llvm.org/LICENSE.txt for license information.
 // SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
 //
 //===----------------------------------------------------------------------===//
 //
bool LoopIdiomRecognize::recognizeAndInsertFFS() {
   // If both CntInst and CntPhi are used outside the loop the profitability
   // is questionable.
   if (IsCntInstUsedOutsideLoop && IsCntPhiUsedOutsideLoop)
     return false;
 
   // For some CPUs result of CTLZ(X) intrinsic is undefined
   // when X is 0. If we can not guarantee X != 0, we need to check this
   // when expand.
-  bool ZeroCheck = false;
+  bool FoundZeroCheck = false;
   // It is safe to assume Preheader exist as it was checked in
   // parent function RunOnLoop.
   BasicBlock *PH = CurLoop->getLoopPreheader();
 
-  // If we are using the count instruction outside the loop, make sure we
-  // have a zero check as a precondition. Without the check the loop would run
-  // one iteration for before any check of the input value. This means 0 and 1
-  // would have identical behavior in the original loop and thus
+  // If we are using the count instruction outside the loop, see if we have a
+  // zero check as a precondition. Without the check the loop would run one
+  // iteration before any check of the input value. This means an input of 0
+  // or 1 would produce the same count result. If were aren't able to find
+  // the zero check, we'll need to insert our own to select a different result
+  // for an input of 0.
   if (!IsCntPhiUsedOutsideLoop) {
-    auto *PreCondBB = PH->getSinglePredecessor();
-    if (!PreCondBB)
-      return false;
-    auto *PreCondBI = dyn_cast<BranchInst>(PreCondBB->getTerminator());
-    if (!PreCondBI)
-      return false;
-    if (matchCondition(PreCondBI, PH) != InitX)
-      return false;
-    ZeroCheck = true;
+    if (auto *PreCondBB = PH->getSinglePredecessor())
+      if (auto *PreCondBI = dyn_cast<BranchInst>(PreCondBB->getTerminator()))
+        if (matchCondition(PreCondBI, PH) == InitX)
+          FoundZeroCheck = true;
   }
 
   // Check if CTLZ / CTTZ intrinsic is profitable. Assume it is always
   // profitable if we delete the loop.
 
   // the loop has only 6 instructions:
   //  %n.addr.0 = phi [ %n, %entry ], [ %shr, %while.cond ]
   //  %i.0 = phi [ %i0, %entry ], [ %inc, %while.cond ]
   //  %shr = ashr %n.addr.0, 1
   //  %tobool = icmp eq %shr, 0
   //  %inc = add nsw %i.0, 1
   //  br i1 %tobool
 
-  const Value *Args[] = {
-      InitX, ZeroCheck ? ConstantInt::getTrue(InitX->getContext())
-                       : ConstantInt::getFalse(InitX->getContext())};
+  const Value *Args[] = {InitX, ConstantInt::getBool(InitX->getContext(),
+                                                     !IsCntPhiUsedOutsideLoop)};
 
   // @llvm.dbg doesn't count as they have no semantic effect.
   auto InstWithoutDebugIt = CurLoop->getHeader()->instructionsWithoutDebug();
   uint32_t HeaderSize =
       std::distance(InstWithoutDebugIt.begin(), InstWithoutDebugIt.end());
 
   IntrinsicCostAttributes Attrs(IntrinID, InitX->getType(), Args);
   InstructionCost Cost =
     TTI->getIntrinsicInstrCost(Attrs, TargetTransformInfo::TCK_SizeAndLatency);
   if (HeaderSize != IdiomCanonicalSize &&
       Cost > TargetTransformInfo::TCC_Basic)
     return false;
 
   transformLoopToCountable(IntrinID, PH, CntInst, CntPhi, InitX, DefX,
-                           DefX->getDebugLoc(), ZeroCheck,
+                           DefX->getDebugLoc(), FoundZeroCheck,
                            IsCntPhiUsedOutsideLoop);
   return true;
 }
 
 /// Recognizes a population count idiom in a non-countable loop.
 ///
 /// If detected, transforms the relevant code to issue the popcount intrinsic
 /// function call, and returns true; otherwise, returns false.
static CallInst *createPopcntIntrinsic(IRBuilder<> &IRBuilder, Value *Val,
   Function *Func = Intrinsic::getDeclaration(M, Intrinsic::ctpop, Tys);
   CallInst *CI = IRBuilder.CreateCall(Func, Ops);
   CI->setDebugLoc(DL);
 
   return CI;
 }
 
 static CallInst *createFFSIntrinsic(IRBuilder<> &IRBuilder, Value *Val,
-                                    const DebugLoc &DL, bool ZeroCheck,
+                                    const DebugLoc &DL, bool ZeroUndef,
                                     Intrinsic::ID IID) {
-  Value *Ops[] = {Val, ZeroCheck ? IRBuilder.getTrue() : IRBuilder.getFalse()};
+  Value *Ops[] = {Val, ZeroUndef ? IRBuilder.getTrue() : IRBuilder.getFalse()};
   Type *Tys[] = {Val->getType()};
 
   Module *M = IRBuilder.GetInsertBlock()->getParent()->getParent();
   Function *Func = Intrinsic::getDeclaration(M, IID, Tys);
   CallInst *CI = IRBuilder.CreateCall(Func, Ops);
   CI->setDebugLoc(DL);
 
   return CI;

 /// or
 /// Use(Count + Cnt0) // Use(CntInst)
 ///
 /// If LOOP_BODY is empty the loop will be deleted.
 /// If CntInst and DefX are not used in LOOP_BODY they will be removed.
 void LoopIdiomRecognize::transformLoopToCountable(
     Intrinsic::ID IntrinID, BasicBlock *Preheader, Instruction *CntInst,
     PHINode *CntPhi, Value *InitX, Instruction *DefX, const DebugLoc &DL,
-    bool ZeroCheck, bool IsCntPhiUsedOutsideLoop) {
+    bool FoundZeroCheck, bool IsCntPhiUsedOutsideLoop) {
   BranchInst *PreheaderBr = cast<BranchInst>(Preheader->getTerminator());
 
   // Step 1: Insert the CTLZ/CTTZ instruction at the end of the preheader block
   IRBuilder<> Builder(PreheaderBr);
   Builder.SetCurrentDebugLocation(DL);
 
   //   Count = BitWidth - CTLZ(InitX);
   //   NewCount = Count;
else if (DefX->getOpcode() == Instruction::LShr)
           Builder.CreateLShr(InitX, ConstantInt::get(InitX->getType(), 1));
     else if (DefX->getOpcode() == Instruction::Shl) // cttz
       InitXNext =
           Builder.CreateShl(InitX, ConstantInt::get(InitX->getType(), 1));
     else
       llvm_unreachable("Unexpected opcode!");
   } else
     InitXNext = InitX;
-  Value *FFS = createFFSIntrinsic(Builder, InitXNext, DL, ZeroCheck, IntrinID);
+  // If the count phi is not used outside the loop, we should use the zero
+  // undef form. If we didn't find a zero check we'll insert our own later.
+  Value *FFS = createFFSIntrinsic(Builder, InitXNext, DL,
+                                  !IsCntPhiUsedOutsideLoop, IntrinID);
   Value *Count = Builder.CreateSub(
       ConstantInt::get(FFS->getType(), FFS->getType()->getIntegerBitWidth()),
       FFS);
   Value *NewCount = Count;
   if (IsCntPhiUsedOutsideLoop) {
     NewCount = Count;
     Count = Builder.CreateAdd(Count, ConstantInt::get(Count->getType(), 1));
   }
if (cast<ConstantInt>(CntInst->getOperand(1))->isOne()) {
     if (!InitConst || !InitConst->isZero())
       NewCount = Builder.CreateAdd(NewCount, CntInitVal);
   } else {
     // If the count was being decremented in the loop, subtract NewCount from
     // the counter's initial value.
     NewCount = Builder.CreateSub(CntInitVal, NewCount);
   }
 
+  // If the count instruction is used outside the loop and we didn't find a zero
+  // check, we need to insert one. It's possible the zero check exists, but was
+  // missed by our simple check. Later passes may be able to optimize out this
+  // new check.
+  if (!IsCntPhiUsedOutsideLoop && !FoundZeroCheck) {
+    // If we didn't find the zero check, we need to assume we'll execute one
+    // iteration of the loop when the input is zero. If the input is zero, we
+    // need to select the initial value incremented/decremented by the count
+    // instruction's immediate operand.
+    Value *Cmp = Builder.CreateICmpEQ(
+        InitXNext, ConstantInt::get(InitXNext->getType(), 0));
+    Value *AltCount = Builder.CreateAdd(CntInitVal, CntInst->getOperand(1));
+    NewCount = Builder.CreateSelect(Cmp, AltCount, NewCount);
+  }
+
   // Step 2: Insert new IV and loop condition:
   // loop:
   //   ...
   //   PhiCount = PHI [Count, Dec]
   //   ...
   //   Dec = PhiCount - 1
   //   ...
   //   Br: loop if (Dec != 0)
   BasicBlock *Body = *(CurLoop->block_begin());
   auto *LbBr = cast<BranchInst>(Body->getTerminator());
   ICmpInst *LbCond = cast<ICmpInst>(LbBr->getCondition());
   Type *Ty = Count->getType();
 
   PHINode *TcPhi = PHINode::Create(Ty, 2, "tcphi", &Body->front());
 
   Builder.SetInsertPoint(LbCond);
   Instruction *TcDec = cast<Instruction>(
       Builder.CreateSub(TcPhi, ConstantInt::get(Ty, 1),
                         "tcdec", false, true));
 
   TcPhi->addIncoming(Count, Preheader);
   TcPhi->addIncoming(TcDec, Body);
 
   CmpInst::Predicate Pred =
       (LbBr->getSuccessor(0) == Body) ? CmpInst::ICMP_NE : CmpInst::ICMP_EQ;
   LbCond->setPredicate(Pred);
   LbCond->setOperand(0, TcDec);
   LbCond->setOperand(1, ConstantInt::get(Ty, 0));
 

llvm/test/Transforms/LoopIdiom/X86/ctlz.ll

 while.end:                                        ; preds = %while.end.loopexit, %entry
   %i.0.lcssa = phi i32 [ 0, %entry ], [ %inc, %while.end.loopexit ]
   ret i32 %i.0.lcssa
 }
 
 ; Recognize CTLZ builtin pattern.
 ; Here it will replace the loop -
 ; assume builtin is always profitable.
+; The C code here represents how other loop transformations and instcombine
+; may optimize the earlier ctlz_zero_check test case. The precondition check
+; for 0 is using the input to the absolute value pattern instead of the output.
+; This makes it different than the Value* passed to the loop phi. So we won't
+; be able to tell the input was checked for 0 so our replacement will need to
+; account for this.
+;
+; int ctlz_zero_check_elided_abs(int n)
+; {
+;   int abs_n = n >= 0 ? n : -n;
+;   if (!n)
+;     return 0;
+;   int i = 0;
+;   do {
+;     abs_n >>= 1;
+;     i++;
+;   } while (abs_n);
+;   return i;
+; }
+;
+define i32 @ctlz_zero_check_elided_abs(i32 %n) {
+; ALL-LABEL: @ctlz_zero_check_elided_abs(
+; ALL-NEXT:  entry:
+; ALL-NEXT:    [[C:%.*]] = icmp sgt i32 [[N:%.*]], 0
+; ALL-NEXT:    [[NEGN:%.*]] = sub nsw i32 0, [[N]]
+; ALL-NEXT:    [[ABS_N:%.*]] = select i1 [[C]], i32 [[N]], i32 [[NEGN]]
+; ALL-NEXT:    [[TOBOOL4:%.*]] = icmp eq i32 [[N]], 0
+; ALL-NEXT:    br i1 [[TOBOOL4]], label [[WHILE_END:%.*]], label [[WHILE_BODY_PREHEADER:%.*]]
+; ALL:       while.body.preheader:
+; ALL-NEXT:    [[TMP0:%.*]] = call i32 @llvm.ctlz.i32(i32 [[ABS_N]], i1 true)
+; ALL-NEXT:    [[TMP1:%.*]] = sub i32 32, [[TMP0]]
+; ALL-NEXT:    [[TMP2:%.*]] = icmp eq i32 [[ABS_N]], 0
+; ALL-NEXT:    [[TMP3:%.*]] = select i1 [[TMP2]], i32 1, i32 [[TMP1]]
+; ALL-NEXT:    br label [[WHILE_BODY:%.*]]
+; ALL:       while.body:
+; ALL-NEXT:    [[TCPHI:%.*]] = phi i32 [ [[TMP1]], [[WHILE_BODY_PREHEADER]] ], [ [[TCDEC:%.*]], [[WHILE_BODY]] ]
+; ALL-NEXT:    [[I_06:%.*]] = phi i32 [ [[INC:%.*]], [[WHILE_BODY]] ], [ 0, [[WHILE_BODY_PREHEADER]] ]
+; ALL-NEXT:    [[N_ADDR_05:%.*]] = phi i32 [ [[SHR:%.*]], [[WHILE_BODY]] ], [ [[ABS_N]], [[WHILE_BODY_PREHEADER]] ]
+; ALL-NEXT:    [[SHR]] = lshr i32 [[N_ADDR_05]], 1
+; ALL-NEXT:    [[INC]] = add nsw i32 [[I_06]], 1
+; ALL-NEXT:    [[TCDEC]] = sub nsw i32 [[TCPHI]], 1
+; ALL-NEXT:    [[TOBOOL:%.*]] = icmp eq i32 [[TCDEC]], 0
+; ALL-NEXT:    br i1 [[TOBOOL]], label [[WHILE_END_LOOPEXIT:%.*]], label [[WHILE_BODY]]
+; ALL:       while.end.loopexit:
+; ALL-NEXT:    [[INC_LCSSA:%.*]] = phi i32 [ [[TMP3]], [[WHILE_BODY]] ]
+; ALL-NEXT:    br label [[WHILE_END]]
+; ALL:       while.end:
+; ALL-NEXT:    [[I_0_LCSSA:%.*]] = phi i32 [ 0, [[ENTRY:%.*]] ], [ [[INC_LCSSA]], [[WHILE_END_LOOPEXIT]] ]
+; ALL-NEXT:    ret i32 [[I_0_LCSSA]]
+;
+entry:
+  %c = icmp sgt i32 %n, 0
+  %negn = sub nsw i32 0, %n
+  %abs_n = select i1 %c, i32 %n, i32 %negn
+  %tobool4 = icmp eq i32 %n, 0
+  br i1 %tobool4, label %while.end, label %while.body.preheader
+
+while.body.preheader:                             ; preds = %entry
+  br label %while.body
+
+while.body:                                       ; preds = %while.body.preheader, %while.body
+  %i.06 = phi i32 [ %inc, %while.body ], [ 0, %while.body.preheader ]
+  %n.addr.05 = phi i32 [ %shr, %while.body ], [ %abs_n, %while.body.preheader ]
+  %shr = lshr i32 %n.addr.05, 1
+  %inc = add nsw i32 %i.06, 1
+  %tobool = icmp eq i32 %shr, 0
+  br i1 %tobool, label %while.end.loopexit, label %while.body
+
+while.end.loopexit:                               ; preds = %while.body
+  br label %while.end
+
+while.end:                                        ; preds = %while.end.loopexit, %entry
+  %i.0.lcssa = phi i32 [ 0, %entry ], [ %inc, %while.end.loopexit ]
+  ret i32 %i.0.lcssa
+}
+
+
+; Recognize CTLZ builtin pattern.
+; Here it will replace the loop -
+; assume builtin is always profitable.
 ;
 ; int ctlz(int n)
 ; {
 ;   n = n >= 0 ? n : -n;
 ;   int i = 0;
 ;   while(n >>= 1) {
 ;     i++;
 ;   }

 while.cond.while.end_crit_edge:                   ; preds = %while.body
   %split = phi i32 [ %inc, %while.body ]
   br label %while.end
 
 while.end:                                        ; preds = %while.cond.while.end_crit_edge, %entry
   %cnt.0.lcssa = phi i32 [ %split, %while.cond.while.end_crit_edge ], [ 0, %entry ]
   ret i32 %cnt.0.lcssa
 }
 
-; We can't easily transform this loop. It returns 1 for an input of both
-; 0 and 1.
+; This loop has no check for n being 0 before entering the loop so we need to
+; make one in order to use ctlz since an input of 0 or 1 will produce the same
+; count.
 ;
-; int ctlz_bad(unsigned n)
+; int ctlz_no_zero_check(unsigned n)
 ; {
 ;   int i = 0;
 ;   do {
 ;     i++;
 ;     n >>= 1;
 ;   } while(n != 0) {
 ;   return i;
 ; }
 ;
-define i32 @ctlz_bad(i32 %n) {
-; ALL-LABEL: @ctlz_bad(
+define i32 @ctlz_no_zero_check(i32 %n) {
+; ALL-LABEL: @ctlz_no_zero_check(
 ; ALL-NEXT:  entry:
+; ALL-NEXT:    [[TMP0:%.*]] = call i32 @llvm.ctlz.i32(i32 [[N:%.*]], i1 true)
+; ALL-NEXT:    [[TMP1:%.*]] = sub i32 32, [[TMP0]]
+; ALL-NEXT:    [[TMP2:%.*]] = icmp eq i32 [[N]], 0
+; ALL-NEXT:    [[TMP3:%.*]] = select i1 [[TMP2]], i32 1, i32 [[TMP1]]
 ; ALL-NEXT:    br label [[WHILE_COND:%.*]]
 ; ALL:       while.cond:
-; ALL-NEXT:    [[N_ADDR_0:%.*]] = phi i32 [ [[N:%.*]], [[ENTRY:%.*]] ], [ [[SHR:%.*]], [[WHILE_COND]] ]
+; ALL-NEXT:    [[TCPHI:%.*]] = phi i32 [ [[TMP1]], [[ENTRY:%.*]] ], [ [[TCDEC:%.*]], [[WHILE_COND]] ]
+; ALL-NEXT:    [[N_ADDR_0:%.*]] = phi i32 [ [[N]], [[ENTRY]] ], [ [[SHR:%.*]], [[WHILE_COND]] ]
 ; ALL-NEXT:    [[I_0:%.*]] = phi i32 [ 0, [[ENTRY]] ], [ [[INC:%.*]], [[WHILE_COND]] ]
 ; ALL-NEXT:    [[SHR]] = lshr i32 [[N_ADDR_0]], 1
-; ALL-NEXT:    [[TOBOOL:%.*]] = icmp eq i32 [[SHR]], 0
+; ALL-NEXT:    [[TCDEC]] = sub nsw i32 [[TCPHI]], 1
+; ALL-NEXT:    [[TOBOOL:%.*]] = icmp eq i32 [[TCDEC]], 0
 ; ALL-NEXT:    [[INC]] = add nsw i32 [[I_0]], 1
 ; ALL-NEXT:    br i1 [[TOBOOL]], label [[WHILE_END:%.*]], label [[WHILE_COND]]
 ; ALL:       while.end:
-; ALL-NEXT:    [[INC_LCSSA:%.*]] = phi i32 [ [[INC]], [[WHILE_COND]] ]
+; ALL-NEXT:    [[INC_LCSSA:%.*]] = phi i32 [ [[TMP3]], [[WHILE_COND]] ]
 ; ALL-NEXT:    ret i32 [[INC_LCSSA]]
 ;
 entry:
   br label %while.cond
 
 while.cond:                                       ; preds = %while.cond, %entry
   %n.addr.0 = phi i32 [ %n, %entry ], [ %shr, %while.cond ]
   %i.0 = phi i32 [ 0, %entry ], [ %inc, %while.cond ]

llvm/test/Transforms/PhaseOrdering/X86/ctlz-loop.ll

 ; NOTE: Assertions have been autogenerated by utils/update_test_checks.py
 ; RUN: opt < %s -O1 -S -mattr=+lzcnt | FileCheck %s
 
 target datalayout = "e-m:e-p270:32:32-p271:32:32-p272:64:64-i64:64-f80:128-n8:16:32:64-S128"
 target triple = "x86_64-unknown-linux-gnu"
 
 ; This test ensures we are able to optimize the following loop to an llvm.abs
 ; followed by an llvm.ctlz.
-; FIXME: LoopIdiom recongize is not forming llvm.ctlz.
 
 ; int ctlz_zero_check(int n)
 ; {
 ;   n = n >= 0 ? n : -n;
 ;   int i = 0;
 ;   while(n) {
 ;     n >>= 1;
 ;     i++;
 ;   }
 ;   return i;
 ; }
 
+; FIXME: The icmp and select in the output are unnecessary.
 define i32 @ctlz_loop_with_abs(i32 %n) {
 ; CHECK-LABEL: @ctlz_loop_with_abs(
 ; CHECK-NEXT:  entry:
 ; CHECK-NEXT:    [[TOBOOL_NOT1:%.*]] = icmp eq i32 [[N:%.*]], 0
-; CHECK-NEXT:    br i1 [[TOBOOL_NOT1]], label [[WHILE_END:%.*]], label [[WHILE_BODY_PREHEADER:%.*]]
-; CHECK:       while.body.preheader:
 ; CHECK-NEXT:    [[TMP0:%.*]] = call i32 @llvm.abs.i32(i32 [[N]], i1 true)
-; CHECK-NEXT:    br label [[WHILE_BODY:%.*]]
-; CHECK:       while.body:
-; CHECK-NEXT:    [[N_ADDR_03:%.*]] = phi i32 [ [[TMP1:%.*]], [[WHILE_BODY]] ], [ [[TMP0]], [[WHILE_BODY_PREHEADER]] ]
-; CHECK-NEXT:    [[I_02:%.*]] = phi i32 [ [[INC:%.*]], [[WHILE_BODY]] ], [ 0, [[WHILE_BODY_PREHEADER]] ]
-; CHECK-NEXT:    [[TMP1]] = lshr i32 [[N_ADDR_03]], 1
-; CHECK-NEXT:    [[INC]] = add nuw nsw i32 [[I_02]], 1
-; CHECK-NEXT:    [[TOBOOL_NOT:%.*]] = icmp eq i32 [[TMP1]], 0
-; CHECK-NEXT:    br i1 [[TOBOOL_NOT]], label [[WHILE_END]], label [[WHILE_BODY]]
-; CHECK:       while.end:
-; CHECK-NEXT:    [[I_0_LCSSA:%.*]] = phi i32 [ 0, [[ENTRY:%.*]] ], [ [[INC]], [[WHILE_BODY]] ]
+; CHECK-NEXT:    [[TMP1:%.*]] = call i32 @llvm.ctlz.i32(i32 [[TMP0]], i1 true), !range [[RNG0:![0-9]+]]
+; CHECK-NEXT:    [[TMP2:%.*]] = sub nuw nsw i32 32, [[TMP1]]
+; CHECK-NEXT:    [[I_0_LCSSA:%.*]] = select i1 [[TOBOOL_NOT1]], i32 0, i32 [[TMP2]]
 ; CHECK-NEXT:    ret i32 [[I_0_LCSSA]]
 ;
 entry:
   %cmp = icmp sge i32 %n, 0
   br i1 %cmp, label %cond.true, label %cond.false
 
 cond.true:                                        ; preds = %entry
   br label %cond.end