[LoopIdiomRecognize] Only convert loops to ctlz if we can prove that the input is non-negative.

[craig.topper]

Summary

Loop idiom recognize tries to convert loops like

int foo(int x) {
  int cnt = 0;
  while (x) {
    x >>= 1;
    ++cnt;
  }
  return cnt;
}

into calls to ctlz, but if x is initially negative this loop should be infinite.

It happens that the cases that motivated this change have an absolute value of x before the loop. So this patch restricts the transform to cases where we know x is positive. Note: We are relying on the absolute value of INT_MIN to be undefined so we can assume that the result is always positive.

Fixes PR37479

[efriedma]

Missing patch.

[craig.topper]

Add the code changes.

[hfinkel]

Out of curiosity, did the original test case come from C/C++? Because if it did, given that we get to assume infinite loops like this don't happen in C/C++, we may end up "breaking" this again in the future.

In any case, I recommend actually using the phrase "infinite loop" in the comment to make it clear what's going on.

[craig.topper]

The original motivating code is something like the loop in the htest_one_block function here https://github.com/mozilla/mozjpeg/blob/master/jchuff.c

[efriedma]

test/Transforms/LoopIdiom/ARM/ctlz.ll

16 ↗

(On Diff #148498)

Please update this comment.

54 ↗

(On Diff #148498)

Given that shr11 is known positive, it seems likely some other pass will convert it to an lshr. (If that doesn't happen now, it likely will some time in the future.)

[craig.topper]

Mention in infinite loop in comments. Update C code in comments in ARM test. Change ashr to lshr in tests when its directly after the abs pattern. InstCombine is able to convert those. The ashr inside the loop dont' get changed because value tracking doesn't understand the recurrence I guess.

I've left FIXME comments to handle lshr loops in the future. But I don't have a motivating example of those yet.

[craig.topper]

Ping

[efriedma]

LGTM

I'm worried the motivating case will break once instcombine or CorrelatedValuePropagation gets a bit smarter... but I guess that's sort of orthogonal to this patch.

llvm/trunk/lib/Transforms/Scalar/LoopIdiomRecognize.cpp

static bool detectCTLZIdiom(Loop *CurLoop, PHINode *&PhiX,
   // step 1: Check if the loop-back branch is in desirable form.
   if (Value *T = matchCondition(
           dyn_cast<BranchInst>(LoopEntry->getTerminator()), LoopEntry))
     DefX = dyn_cast<Instruction>(T);
   else
     return false;
 
   // step 2: detect instructions corresponding to "x.next = x >> 1"
+  // TODO: Support loops that use LShr.
   if (!DefX || DefX->getOpcode() != Instruction::AShr)
     return false;
   ConstantInt *Shft = dyn_cast<ConstantInt>(DefX->getOperand(1));
   if (!Shft || !Shft->isOne())
     return false;
   VarX = DefX->getOperand(0);
 
   // step 3: Check the recurrence of variable X
bool LoopIdiomRecognize::recognizeAndInsertCTLZ() {
   // 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;
   // It is safe to assume Preheader exist as it was checked in
   // parent function RunOnLoop.
   BasicBlock *PH = CurLoop->getLoopPreheader();
   Value *InitX = PhiX->getIncomingValueForBlock(PH);
+
+  // Make sure the initial value can't be negative otherwise the ashr in the
+  // loop might never reach zero which would make the loop infinite.
+  // TODO: Support loops that use lshr and wouldn't need this check.
+  if (!isKnownNonNegative(InitX, *DL))
+    return false;
+
   // If we check X != 0 before entering the loop we don't need a zero
   // check in CTLZ intrinsic, but only if Cnt Phi is not used outside of the
   // loop (if it is used we count CTLZ(X >> 1)).
   if (!IsCntPhiUsedOutsideLoop)
     if (BasicBlock *PreCondBB = PH->getSinglePredecessor())
       if (BranchInst *PreCondBr =
           dyn_cast<BranchInst>(PreCondBB->getTerminator())) {
         if (matchCondition(PreCondBr, PH) == InitX)

llvm/trunk/test/Transforms/LoopIdiom/ARM/ctlz.ll

 ; RUN: opt -loop-idiom -mtriple=armv7a < %s -S | FileCheck -check-prefix=LZCNT --check-prefix=ALL %s
 ; RUN: opt -loop-idiom -mtriple=armv4t < %s -S | FileCheck -check-prefix=NOLZCNT --check-prefix=ALL %s
 
 ; Recognize CTLZ builtin pattern.
 ; Here we'll just convert loop to countable,
 ; so do not insert builtin if CPU do not support CTLZ
 ;
 ; int ctlz_and_other(int n, char *a)
 ; {
+;   n = n >= 0 ? n : -n;
 ;   int i = 0, n0 = n;
 ;   while(n >>= 1) {
 ;     a[i] = (n0 & (1 << i)) ? 1 : 0;
 ;     i++;
 ;   }
 ;   return i;
 ; }
 ;
 ; LZCNT:  entry
 ; LZCNT:  %0 = call i32 @llvm.ctlz.i32(i32 %shr8, i1 true)
 ; LZCNT-NEXT:  %1 = sub i32 32, %0
 ; LZCNT-NEXT:  %2 = zext i32 %1 to i64
 ; LZCNT:  %indvars.iv.next.lcssa = phi i64 [ %2, %while.body ]
 ; LZCNT:  %4 = trunc i64 %indvars.iv.next.lcssa to i32
 ; LZCNT:  %i.0.lcssa = phi i32 [ 0, %entry ], [ %4, %while.end.loopexit ]
 ; LZCNT:  ret i32 %i.0.lcssa
 
 ; NOLZCNT:  entry
 ; NOLZCNT-NOT:  @llvm.ctlz
 
 ; Function Attrs: norecurse nounwind uwtable
 define i32 @ctlz_and_other(i32 %n, i8* nocapture %a) {
 entry:
-  %shr8 = ashr i32 %n, 1
+  %c = icmp sgt i32 %n, 0
+  %negn = sub nsw i32 0, %n
+  %abs_n = select i1 %c, i32 %n, i32 %negn
+  %shr8 = lshr i32 %abs_n, 1
   %tobool9 = icmp eq i32 %shr8, 0
   br i1 %tobool9, label %while.end, label %while.body.preheader
 
 while.body.preheader:                             ; preds = %entry
   br label %while.body
 
 while.body:                                       ; preds = %while.body.preheader, %while.body
   %indvars.iv = phi i64 [ %indvars.iv.next, %while.body ], [ 0, %while.body.preheader ]
   %shr11 = phi i32 [ %shr, %while.body ], [ %shr8, %while.body.preheader ]
   %0 = trunc i64 %indvars.iv to i32
   %shl = shl i32 1, %0
-  %and = and i32 %shl, %n
+  %and = and i32 %shl, %abs_n
   %tobool1 = icmp ne i32 %and, 0
   %conv = zext i1 %tobool1 to i8
   %arrayidx = getelementptr inbounds i8, i8* %a, i64 %indvars.iv
   store i8 %conv, i8* %arrayidx, align 1
   %indvars.iv.next = add nuw i64 %indvars.iv, 1
   %shr = ashr i32 %shr11, 1
   %tobool = icmp eq i32 %shr, 0
   br i1 %tobool, label %while.end.loopexit, label %while.body
 
 while.end.loopexit:                               ; preds = %while.body
   %1 = trunc i64 %indvars.iv.next to i32
   br label %while.end
 
 while.end:                                        ; preds = %while.end.loopexit, %entry
   %i.0.lcssa = phi i32 [ 0, %entry ], [ %1, %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_zero_check(int n)
 ; {
+;   n = n >= 0 ? n : -n;
 ;   int i = 0;
 ;   while(n) {
 ;     n >>= 1;
 ;     i++;
 ;   }
 ;   return i;
 ; }
 ;
 ; ALL:  entry
-; ALL:  %0 = call i32 @llvm.ctlz.i32(i32 %n, i1 true)
+; ALL:  %0 = call i32 @llvm.ctlz.i32(i32 %abs_n, i1 true)
 ; ALL-NEXT:  %1 = sub i32 32, %0
 ; ALL:  %inc.lcssa = phi i32 [ %1, %while.body ]
 ; ALL:  %i.0.lcssa = phi i32 [ 0, %entry ], [ %inc.lcssa, %while.end.loopexit ]
 ; ALL:  ret i32 %i.0.lcssa
 
 ; Function Attrs: norecurse nounwind readnone uwtable
 define i32 @ctlz_zero_check(i32 %n) {
 entry:
-  %tobool4 = icmp eq i32 %n, 0
+  %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 %abs_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 ], [ %n, %while.body.preheader ]
+  %n.addr.05 = phi i32 [ %shr, %while.body ], [ %abs_n, %while.body.preheader ]
   %shr = ashr 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++;
 ;   }
 ;   return i;
 ; }
 ;
 ; ALL:  entry
-; ALL:  %0 = ashr i32 %n, 1
+; ALL:  %0 = ashr i32 %abs_n, 1
 ; ALL-NEXT:  %1 = call i32 @llvm.ctlz.i32(i32 %0, i1 false)
 ; ALL-NEXT:  %2 = sub i32 32, %1
 ; ALL-NEXT:  %3 = add i32 %2, 1
 ; ALL:  %i.0.lcssa = phi i32 [ %2, %while.cond ]
 ; ALL:  ret i32 %i.0.lcssa
 
 ; Function Attrs: norecurse nounwind readnone uwtable
 define i32 @ctlz(i32 %n) {
 entry:
+  %c = icmp sgt i32 %n, 0
+  %negn = sub nsw i32 0, %n
+  %abs_n = select i1 %c, i32 %n, i32 %negn
   br label %while.cond
 
 while.cond:                                       ; preds = %while.cond, %entry
-  %n.addr.0 = phi i32 [ %n, %entry ], [ %shr, %while.cond ]
+  %n.addr.0 = phi i32 [ %abs_n, %entry ], [ %shr, %while.cond ]
   %i.0 = phi i32 [ 0, %entry ], [ %inc, %while.cond ]
   %shr = ashr i32 %n.addr.0, 1
   %tobool = icmp eq i32 %shr, 0
   %inc = add nsw i32 %i.0, 1
   br i1 %tobool, label %while.end, label %while.cond
 
 while.end:                                        ; preds = %while.cond
   ret i32 %i.0
 }
 
 ; Recognize CTLZ builtin pattern.
 ; Here it will replace the loop -
 ; assume builtin is always profitable.
 ;
 ; int ctlz_add(int n, int i0)
 ; {
+;   n = n >= 0 ? n : -n;
 ;   int i = i0;
 ;   while(n >>= 1) {
 ;     i++;
 ;   }
 ;   return i;
 ; }
 ;
 ; ALL:  entry
-; ALL:  %0 = ashr i32 %n, 1
+; ALL:  %0 = ashr i32 %abs_n, 1
 ; ALL-NEXT:  %1 = call i32 @llvm.ctlz.i32(i32 %0, i1 false)
 ; ALL-NEXT:  %2 = sub i32 32, %1
 ; ALL-NEXT:  %3 = add i32 %2, 1
 ; ALL-NEXT:  %4 = add i32 %2, %i0
 ; ALL:  %i.0.lcssa = phi i32 [ %4, %while.cond ]
 ; ALL:  ret i32 %i.0.lcssa
 ;
 ; Function Attrs: norecurse nounwind readnone uwtable
 define i32 @ctlz_add(i32 %n, i32 %i0) {
 entry:
+  %c = icmp sgt i32 %n, 0
+  %negn = sub nsw i32 0, %n
+  %abs_n = select i1 %c, i32 %n, i32 %negn
   br label %while.cond
 
 while.cond:                                       ; preds = %while.cond, %entry
-  %n.addr.0 = phi i32 [ %n, %entry ], [ %shr, %while.cond ]
+  %n.addr.0 = phi i32 [ %abs_n, %entry ], [ %shr, %while.cond ]
   %i.0 = phi i32 [ %i0, %entry ], [ %inc, %while.cond ]
   %shr = ashr i32 %n.addr.0, 1
   %tobool = icmp eq i32 %shr, 0
   %inc = add nsw i32 %i.0, 1
   br i1 %tobool, label %while.end, label %while.cond
 
 while.end:                                        ; preds = %while.cond
   ret i32 %i.0
 }

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

 ; RUN: opt -loop-idiom -mtriple=x86_64 -mcpu=core-avx2 < %s -S | FileCheck -check-prefix=LZCNT --check-prefix=ALL %s
 ; RUN: opt -loop-idiom -mtriple=x86_64 -mcpu=corei7 < %s -S | FileCheck -check-prefix=NOLZCNT --check-prefix=ALL %s
 
 ; Recognize CTLZ builtin pattern.
 ; Here we'll just convert loop to countable,
 ; so do not insert builtin if CPU do not support CTLZ
 ;
 ; int ctlz_and_other(int n, char *a)
 ; {
+;   n = n >= 0 ? n : -n;
 ;   int i = 0, n0 = n;
 ;   while(n >>= 1) {
 ;     a[i] = (n0 & (1 << i)) ? 1 : 0;
 ;     i++;
 ;   }
 ;   return i;
 ; }
 ;
 ; LZCNT:  entry
 ; LZCNT:  %0 = call i32 @llvm.ctlz.i32(i32 %shr8, i1 true)
 ; LZCNT-NEXT:  %1 = sub i32 32, %0
 ; LZCNT-NEXT:  %2 = zext i32 %1 to i64
 ; LZCNT:  %indvars.iv.next.lcssa = phi i64 [ %2, %while.body ]
 ; LZCNT:  %4 = trunc i64 %indvars.iv.next.lcssa to i32
 ; LZCNT:  %i.0.lcssa = phi i32 [ 0, %entry ], [ %4, %while.end.loopexit ]
 ; LZCNT:  ret i32 %i.0.lcssa
 
 ; NOLZCNT:  entry
 ; NOLZCNT-NOT:  @llvm.ctlz
 
 ; Function Attrs: norecurse nounwind uwtable
 define i32 @ctlz_and_other(i32 %n, i8* nocapture %a) {
 entry:
-  %shr8 = ashr i32 %n, 1
+  %c = icmp sgt i32 %n, 0
+  %negn = sub nsw i32 0, %n
+  %abs_n = select i1 %c, i32 %n, i32 %negn
+  %shr8 = lshr i32 %abs_n, 1
   %tobool9 = icmp eq i32 %shr8, 0
   br i1 %tobool9, label %while.end, label %while.body.preheader
 
 while.body.preheader:                             ; preds = %entry
   br label %while.body
 
 while.body:                                       ; preds = %while.body.preheader, %while.body
   %indvars.iv = phi i64 [ %indvars.iv.next, %while.body ], [ 0, %while.body.preheader ]
   %shr11 = phi i32 [ %shr, %while.body ], [ %shr8, %while.body.preheader ]
   %0 = trunc i64 %indvars.iv to i32
   %shl = shl i32 1, %0
-  %and = and i32 %shl, %n
+  %and = and i32 %shl, %abs_n
   %tobool1 = icmp ne i32 %and, 0
   %conv = zext i1 %tobool1 to i8
   %arrayidx = getelementptr inbounds i8, i8* %a, i64 %indvars.iv
   store i8 %conv, i8* %arrayidx, align 1
   %indvars.iv.next = add nuw i64 %indvars.iv, 1
   %shr = ashr i32 %shr11, 1
   %tobool = icmp eq i32 %shr, 0
   br i1 %tobool, label %while.end.loopexit, label %while.body
 
 while.end.loopexit:                               ; preds = %while.body
   %1 = trunc i64 %indvars.iv.next to i32
   br label %while.end
 
 while.end:                                        ; preds = %while.end.loopexit, %entry
   %i.0.lcssa = phi i32 [ 0, %entry ], [ %1, %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_zero_check(int n)
 ; {
+;   n = n >= 0 ? n : -n;
 ;   int i = 0;
 ;   while(n) {
 ;     n >>= 1;
 ;     i++;
 ;   }
 ;   return i;
 ; }
 ;
 ; ALL:  entry
-; ALL:  %0 = call i32 @llvm.ctlz.i32(i32 %n, i1 true)
+; ALL:  %0 = call i32 @llvm.ctlz.i32(i32 %abs_n, i1 true)
 ; ALL-NEXT:  %1 = sub i32 32, %0
 ; ALL:  %inc.lcssa = phi i32 [ %1, %while.body ]
 ; ALL:  %i.0.lcssa = phi i32 [ 0, %entry ], [ %inc.lcssa, %while.end.loopexit ]
 ; ALL:  ret i32 %i.0.lcssa
 
 ; Function Attrs: norecurse nounwind readnone uwtable
 define i32 @ctlz_zero_check(i32 %n) {
 entry:
-  %tobool4 = icmp eq i32 %n, 0
+  %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 %abs_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 ], [ %n, %while.body.preheader ]
+  %n.addr.05 = phi i32 [ %shr, %while.body ], [ %abs_n, %while.body.preheader ]
   %shr = ashr 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++;
 ;   }
 ;   return i;
 ; }
 ;
 ; ALL:  entry
-; ALL:  %0 = ashr i32 %n, 1
+; ALL:  %0 = ashr i32 %abs_n, 1
 ; ALL-NEXT:  %1 = call i32 @llvm.ctlz.i32(i32 %0, i1 false)
 ; ALL-NEXT:  %2 = sub i32 32, %1
 ; ALL-NEXT:  %3 = add i32 %2, 1
 ; ALL:  %i.0.lcssa = phi i32 [ %2, %while.cond ]
 ; ALL:  ret i32 %i.0.lcssa
 
 ; Function Attrs: norecurse nounwind readnone uwtable
 define i32 @ctlz(i32 %n) {
 entry:
+  %c = icmp sgt i32 %n, 0
+  %negn = sub nsw i32 0, %n
+  %abs_n = select i1 %c, i32 %n, i32 %negn
   br label %while.cond
 
 while.cond:                                       ; preds = %while.cond, %entry
-  %n.addr.0 = phi i32 [ %n, %entry ], [ %shr, %while.cond ]
+  %n.addr.0 = phi i32 [ %abs_n, %entry ], [ %shr, %while.cond ]
   %i.0 = phi i32 [ 0, %entry ], [ %inc, %while.cond ]
   %shr = ashr i32 %n.addr.0, 1
   %tobool = icmp eq i32 %shr, 0
   %inc = add nsw i32 %i.0, 1
   br i1 %tobool, label %while.end, label %while.cond
 
 while.end:                                        ; preds = %while.cond
   ret i32 %i.0
 }
 
 ; Recognize CTLZ builtin pattern.
 ; Here it will replace the loop -
 ; assume builtin is always profitable.
 ;
 ; int ctlz_add(int n, int i0)
 ; {
+;   n = n >= 0 ? n : -n;
 ;   int i = i0;
 ;   while(n >>= 1) {
 ;     i++;
 ;   }
 ;   return i;
 ; }
 ;
 ; ALL:  entry
-; ALL:  %0 = ashr i32 %n, 1
+; ALL:  %0 = ashr i32 %abs_n, 1
 ; ALL-NEXT:  %1 = call i32 @llvm.ctlz.i32(i32 %0, i1 false)
 ; ALL-NEXT:  %2 = sub i32 32, %1
 ; ALL-NEXT:  %3 = add i32 %2, 1
 ; ALL-NEXT:  %4 = add i32 %2, %i0
 ; ALL:  %i.0.lcssa = phi i32 [ %4, %while.cond ]
 ; ALL:  ret i32 %i.0.lcssa
 ;
 ; Function Attrs: norecurse nounwind readnone uwtable
 define i32 @ctlz_add(i32 %n, i32 %i0) {
 entry:
+  %c = icmp sgt i32 %n, 0
+  %negn = sub nsw i32 0, %n
+  %abs_n = select i1 %c, i32 %n, i32 %negn
   br label %while.cond
 
 while.cond:                                       ; preds = %while.cond, %entry
-  %n.addr.0 = phi i32 [ %n, %entry ], [ %shr, %while.cond ]
+  %n.addr.0 = phi i32 [ %abs_n, %entry ], [ %shr, %while.cond ]
   %i.0 = phi i32 [ %i0, %entry ], [ %inc, %while.cond ]
   %shr = ashr i32 %n.addr.0, 1
   %tobool = icmp eq i32 %shr, 0
   %inc = add nsw i32 %i.0, 1
   br i1 %tobool, label %while.end, label %while.cond
 
 while.end:                                        ; preds = %while.cond
   ret i32 %i.0
 }
 
 ; This loop contains a volatile store. If x is initially negative,
 ; the code will be an infinite loop because the ashr will eventually produce
 ; all ones and continue doing so. This prevents the loop from terminating. If
 ; we convert this to a countable loop using ctlz that loop will only run 32
 ; times. This is different than the infinite number of times of the original.
-; FIXME: Don't transform this loop.
 define i32 @foo(i32 %x) {
 ; LZCNT-LABEL: @foo(
 ; LZCNT-NEXT:  entry:
 ; LZCNT-NEXT:    [[V:%.*]] = alloca i8, align 1
 ; LZCNT-NEXT:    [[TOBOOL4:%.*]] = icmp eq i32 [[X:%.*]], 0
 ; LZCNT-NEXT:    br i1 [[TOBOOL4]], label [[WHILE_END:%.*]], label [[WHILE_BODY_LR_PH:%.*]]
 ; LZCNT:       while.body.lr.ph:
-; LZCNT-NEXT:    [[TMP0:%.*]] = call i32 @llvm.ctlz.i32(i32 [[X]], i1 true)
-; LZCNT-NEXT:    [[TMP1:%.*]] = sub i32 32, [[TMP0]]
 ; LZCNT-NEXT:    br label [[WHILE_BODY:%.*]]
 ; LZCNT:       while.body:
-; LZCNT-NEXT:    [[TCPHI:%.*]] = phi i32 [ [[TMP1]], [[WHILE_BODY_LR_PH]] ], [ [[TCDEC:%.*]], [[WHILE_BODY]] ]
 ; LZCNT-NEXT:    [[CNT_06:%.*]] = phi i32 [ 0, [[WHILE_BODY_LR_PH]] ], [ [[INC:%.*]], [[WHILE_BODY]] ]
 ; LZCNT-NEXT:    [[X_ADDR_05:%.*]] = phi i32 [ [[X]], [[WHILE_BODY_LR_PH]] ], [ [[SHR:%.*]], [[WHILE_BODY]] ]
 ; LZCNT-NEXT:    [[SHR]] = ashr i32 [[X_ADDR_05]], 1
 ; LZCNT-NEXT:    [[INC]] = add i32 [[CNT_06]], 1
 ; LZCNT-NEXT:    store volatile i8 42, i8* [[V]], align 1
-; LZCNT-NEXT:    [[TCDEC]] = sub nsw i32 [[TCPHI]], 1
-; LZCNT-NEXT:    [[TOBOOL:%.*]] = icmp eq i32 [[TCDEC]], 0
+; LZCNT-NEXT:    [[TOBOOL:%.*]] = icmp eq i32 [[SHR]], 0
 ; LZCNT-NEXT:    br i1 [[TOBOOL]], label [[WHILE_COND_WHILE_END_CRIT_EDGE:%.*]], label [[WHILE_BODY]]
 ; LZCNT:       while.cond.while.end_crit_edge:
-; LZCNT-NEXT:    [[SPLIT:%.*]] = phi i32 [ [[TMP1]], [[WHILE_BODY]] ]
+; LZCNT-NEXT:    [[SPLIT:%.*]] = phi i32 [ [[INC]], [[WHILE_BODY]] ]
 ; LZCNT-NEXT:    br label [[WHILE_END]]
 ; LZCNT:       while.end:
 ; LZCNT-NEXT:    [[CNT_0_LCSSA:%.*]] = phi i32 [ [[SPLIT]], [[WHILE_COND_WHILE_END_CRIT_EDGE]] ], [ 0, [[ENTRY:%.*]] ]
 ; LZCNT-NEXT:    ret i32 [[CNT_0_LCSSA]]
 ;
 ; NOLZCNT-LABEL: @foo(
 ; NOLZCNT-NEXT:  entry:
 ; NOLZCNT-NEXT:    [[V:%.*]] = alloca i8, align 1