[LoopUnroll] countToEliminateCompares(): fix handling of [in]equality predicates (PR43840)

[lebedev.ri]

Summary

I believe this bisects to https://reviews.llvm.org/D44983 ([LoopUnroll] Only peel if a predicate becomes known in the loop body.)

While that revision did contain tests that showed arguably-subpar peeling for
[in]equality predicates that [not] happen in the middle of the loop,
it also disabled peeling for the *first* loop iteration,
because latch would be canonicalized to [in]equality comparison..

That was intentional as per https://reviews.llvm.org/D44983#1059583.
I'm not 100% sure that i'm using correct checks here,
but this fix appears to be going in the right direction..

Let me know if i'm missing some checks here..

Fixes PR43840.

[fhahn]

I'm not really sure how that would look, if we look at -loop-unroll -O3
for those tests, said loops no longer have that condition anyway.
And if we do peel off one more iteration regardless, then we bloat
the code by performing one loop iteration outside of the loop,
without simplifying the loop.

The interesting test cases for the FIXME are test7 and test8. In those cases, we have to peel off 4 iterations, to eliminate the condition in the loop, but with the current logic we peel off only 3: we currently try to peel until a condition in the loop becomes known. For monotonic predicates, we know it will stay known for the rest of the loop (and can be eliminated further down the road).

For EQ/NE that's not the case. In some cases (like in the tests), it is enough to peel one additional iteration, if the predicate becomes known for the rest of the loop. I think the reason why the conditions in test7 and test8 get eliminated with -loop-unroll -O3 is that they will get peeled twice. It would also be good to add an additional test cases with NE/EQ predicates that alternate (e.g. a check that the induction variable is even/odd). For such loops, peeling of the first iteration is not really helpful.

[lebedev.ri]

In D69617#1732064, @fhahn wrote:

I'm not really sure how that would look, if we look at -loop-unroll -O3
for those tests, said loops no longer have that condition anyway.
And if we do peel off one more iteration regardless, then we bloat
the code by performing one loop iteration outside of the loop,
without simplifying the loop.

The interesting test cases for the FIXME are test7 and test8. In those cases, we have to peel off 4 iterations, to eliminate the condition in the loop, but with the current logic we peel off only 3: we currently try to peel until a condition in the loop becomes known. For monotonic predicates, we know it will stay known for the rest of the loop (and can be eliminated further down the road).

For EQ/NE that's not the case. In some cases (like in the tests), it is enough to peel one additional iteration, if the predicate becomes known for the rest of the loop. I think the reason why the conditions in test7 and test8 get eliminated with -loop-unroll -O3 is that they will get peeled twice. It would also be good to add an additional test cases with NE/EQ predicates that alternate (e.g. a check that the induction variable is even/odd). For such loops, peeling of the first iteration is not really helpful.

Thank you for taking a look! I should have been more specific.
That much i understand. It works if we are looking for i!=/==3.
But as you can see from the tests, if we were looking for i!=/==0,
we then end up peeling one iteration more than we need to.

To make it more visible, -loop-unroll -simplifycfg -instcombine -simplifycfg output for those tests:

define void @test12__peel_first_iter_via_eq_pred(i32 %len) {
entry:
  %cmp5 = icmp sgt i32 %len, 0
  br i1 %cmp5, label %if.then.peel, label %for.cond.cleanup

if.then.peel:                                     ; preds = %entry
  call void @init()
  call void @sink()
  %exitcond.peel = icmp eq i32 %len, 1
  br i1 %exitcond.peel, label %for.cond.cleanup, label %if.end.peel5

if.end.peel5:                                     ; preds = %if.then.peel
  call void @sink()                                                          ; <- BAD
  %exitcond.peel7 = icmp eq i32 %len, 2
  br i1 %exitcond.peel7, label %for.cond.cleanup, label %for.body

for.cond.cleanup:                                 ; preds = %if.then.peel, %if.end.peel5, %for.body, %entry
  ret void

for.body:                                         ; preds = %if.end.peel5, %for.body
  %i.06 = phi i32 [ %inc, %for.body ], [ 2, %if.end.peel5 ]
  call void @sink()
  %inc = add nuw nsw i32 %i.06, 1
  %exitcond = icmp eq i32 %inc, %len
  br i1 %exitcond, label %for.cond.cleanup, label %for.body, !llvm.loop !0
}

define void @test13__peel_first_iter_via_ne_pred(i32 %len) {
entry:
  %cmp5 = icmp sgt i32 %len, 0
  br i1 %cmp5, label %if.then.peel, label %for.cond.cleanup

if.then.peel:                                     ; preds = %entry
  call void @init()
  call void @sink()
  %exitcond.peel = icmp eq i32 %len, 1
  br i1 %exitcond.peel, label %for.cond.cleanup, label %if.end.peel5

if.end.peel5:                                     ; preds = %if.then.peel
  call void @sink()                                                          ; <- BAD
  %exitcond.peel7 = icmp eq i32 %len, 2
  br i1 %exitcond.peel7, label %for.cond.cleanup, label %for.body

for.cond.cleanup:                                 ; preds = %if.then.peel, %if.end.peel5, %for.body, %entry
  ret void

for.body:                                         ; preds = %if.end.peel5, %for.body
  %i.06 = phi i32 [ %inc, %for.body ], [ 2, %if.end.peel5 ]
  call void @sink()
  %inc = add nuw nsw i32 %i.06, 1
  %exitcond = icmp eq i32 %inc, %len
  br i1 %exitcond, label %for.cond.cleanup, label %for.body, !llvm.loop !2
}

declare void @init()

declare void @sink()

[lebedev.ri]

Okay, this looks super ugly to me, but this seems to do the right thing..

[lebedev.ri]

Denoise the diff.

[lebedev.ri]

Undo unneeded check.

[xbolva00]

llvm/test/Transforms/LoopUnroll/peel-loop-conditions.ll

524–525

Remove fixme

[lebedev.ri]

Update comments.

[lebedev.ri]

Fix edge-case handling - if we need to peel that one extra iteration,
we should still respect the MaxPeelCount, and if we aren't allowed
to peel, we should give up, not do subpar peeling job.

[fhahn]

LGTM, with a few outstanding comments!

I think some cases could still slip through the cracks, but the most important negative cases are covered by the test cases.

llvm/lib/Transforms/Utils/LoopUnrollPeel.cpp

216

please update the comment, it still mentions we not supporting non-monotonic predicates.

241

IMO it would be slightly better to make the captures explicit (here and below)

255

nit: ...does the predicate .... become known...

259

maybe replace 'we're done here' with' Give up'. like below, to make it clear that we do not want to peel for the given condition.

267

I think we don't need to check the inverse predicate is known, when we already know the regular predicate is known, which is the previous check. Similarly, we already know know SE.isKnownPredicate(ICmpInst::getInversePredicate(Pred), IterVal, RightSCEV), so we should not need to check !SE.isKnownPredicate(Pred, IterVal, RightSCEV)

It might be worth having those 2 as an assertion though, in case I am missing something.

[lebedev.ri]

@fhahn thank you for the review!
Addressed review notes.

[lebedev.ri]

Re-rebase, NFC.

[lebedev.ri]

llvm/lib/Transforms/Utils/LoopUnrollPeel.cpp

267

This is indeed a mess.
I believe this is what you had in mind?

[lebedev.ri]

@fhahn @hfinkel @reames
While there, can anyone give any general suggestion about https://bugs.llvm.org/show_bug.cgi?id=43910, https://bugs.llvm.org/show_bug.cgi?id=43892 ?
Is there any existing pass where something like that fit?

[efriedma]

This is probably not the best place to discuss other loop optimizations. I'll comment in the bugs.

llvm/lib/Transforms/Utils/LoopUnrollPeel.cpp

if (!isa<SCEVAddRecExpr>(LeftSCEV)) {
       } else
         continue;
     }
 
     const SCEVAddRecExpr *LeftAR = cast<SCEVAddRecExpr>(LeftSCEV);
 
     // Avoid huge SCEV computations in the loop below, make sure we only
     // consider AddRecs of the loop we are trying to peel and avoid
     // non-monotonic predicates, as we will not be able to simplify the loop
     // body.
-    // FIXME: For the non-monotonic predicates ICMP_EQ and ICMP_NE we can
-    //        simplify the loop, if we peel 1 additional iteration, if there
-    //        is no wrapping.
+    if (!LeftAR->isAffine() || LeftAR->getLoop() != &L)
+      continue;
     bool Increasing;
-    if (!LeftAR->isAffine() || LeftAR->getLoop() != &L ||
+    if (!(ICmpInst::isEquality(Pred) && LeftAR->hasNoSelfWrap()) &&
         !SE.isMonotonicPredicate(LeftAR, Pred, Increasing))
       continue;
     (void)Increasing;
 
     // Check if extending the current DesiredPeelCount lets us evaluate Pred
     // or !Pred in the loop body statically.
     unsigned NewPeelCount = DesiredPeelCount;
 
     const SCEV *IterVal = LeftAR->evaluateAtIteration(
         SE.getConstant(LeftSCEV->getType(), NewPeelCount), SE);
 
     // If the original condition is not known, get the negated predicate
     // (which holds on the else branch) and check if it is known. This allows
     // us to peel of iterations that make the original condition false.
     if (!SE.isKnownPredicate(Pred, IterVal, RightSCEV))
       Pred = ICmpInst::getInversePredicate(Pred);
 
     const SCEV *Step = LeftAR->getStepRecurrence(SE);
-    while (NewPeelCount < MaxPeelCount &&
-           SE.isKnownPredicate(Pred, IterVal, RightSCEV)) {
-      IterVal = SE.getAddExpr(IterVal, Step);
+    const SCEV *NextIterVal = SE.getAddExpr(IterVal, Step);
+    auto PeelOneMoreIteration = [&]() {
+      IterVal = NextIterVal;
+      NextIterVal = SE.getAddExpr(IterVal, Step);
       NewPeelCount++;
-    }
+    };
 
-    // Only peel the loop if the monotonic predicate !Pred becomes known in the
-    // first iteration of the loop body after peeling.
-    if (NewPeelCount > DesiredPeelCount &&
-        SE.isKnownPredicate(ICmpInst::getInversePredicate(Pred), IterVal,
+    auto CanPeelOneMoreIteration = [&]() {
+      return NewPeelCount < MaxPeelCount;
+    };
+
+    while (CanPeelOneMoreIteration() &&
+           SE.isKnownPredicate(Pred, IterVal, RightSCEV))
+      PeelOneMoreIteration();
+
+    // With *that* peel count, does the predicate !Pred becomes known in the
+    // first iteration of the loop body after peeling?
+    if (!SE.isKnownPredicate(ICmpInst::getInversePredicate(Pred), IterVal,
                              RightSCEV))
-      DesiredPeelCount = NewPeelCount;
+      continue; // If not, we're done here.
+
+    // However, for equality comparisons, that isn't always sufficient to
+    // eliminate the comparsion in loop body, we may need to peel one more
+    // iteration. See if Pred then becomes known again, and !Pred unknown.
+    if (ICmpInst::isEquality(Pred) &&
+        !SE.isKnownPredicate(Pred, IterVal, RightSCEV) &&
+        SE.isKnownPredicate(Pred, NextIterVal, RightSCEV) &&
+        !SE.isKnownPredicate(ICmpInst::getInversePredicate(Pred), NextIterVal,
+                             RightSCEV)) {
+      if (!CanPeelOneMoreIteration())
+        continue; // Need to peel one more iteration, but can't. Give up.
+      PeelOneMoreIteration(); // Great!
+    }
+
+    DesiredPeelCount = std::max(DesiredPeelCount, NewPeelCount);
   }
 
   return DesiredPeelCount;
 }
 
 // Return the number of iterations we want to peel off.
 void llvm::computePeelCount(Loop *L, unsigned LoopSize,
                             TargetTransformInfo::UnrollingPreferences &UP,

llvm/test/Transforms/LoopUnroll/peel-loop-conditions.ll

 ; NOTE: Assertions have been autogenerated by utils/update_test_checks.py
-; RUN: opt < %s -S -loop-unroll -verify-dom-info | FileCheck %s
+; RUN: opt < %s -S -loop-unroll -unroll-peel-max-count=4 -verify-dom-info | FileCheck %s
 
 declare void @f1()
 declare void @f2()
 
 ; Check that we can peel off iterations that make conditions true.
 define void @test1(i32 %k) {
 ; CHECK-LABEL: @test1(
 ; CHECK-NEXT:  for.body.lr.ph:
for.inc:
   %j.inc = add nsw i32 %j, 1
   %cmp = icmp slt i32 %inc, %k
   br i1 %cmp, label %for.body, label %for.end
 
 for.end:
   ret void
 }
 
 define void @test7(i32 %k) {
-; FIXME: Could simplify loop body by peeling one additional iteration after
-;        i != 3 becomes false
 ; CHECK-LABEL: @test7(
 ; CHECK-NEXT:  for.body.lr.ph:
+; CHECK-NEXT:    br label [[FOR_BODY_PEEL_BEGIN:%.*]]
+; CHECK:       for.body.peel.begin:
+; CHECK-NEXT:    br label [[FOR_BODY_PEEL:%.*]]
+; CHECK:       for.body.peel:
+; CHECK-NEXT:    [[CMP1_PEEL:%.*]] = icmp ne i32 0, 3
+; CHECK-NEXT:    br i1 [[CMP1_PEEL]], label [[IF_THEN_PEEL:%.*]], label [[FOR_INC_PEEL:%.*]]
+; CHECK:       if.then.peel:
+; CHECK-NEXT:    call void @f1()
+; CHECK-NEXT:    br label [[FOR_INC_PEEL]]
+; CHECK:       for.inc.peel:
+; CHECK-NEXT:    [[INC_PEEL:%.*]] = add nsw i32 0, 1
+; CHECK-NEXT:    [[CMP_PEEL:%.*]] = icmp slt i32 [[INC_PEEL]], [[K:%.*]]
+; CHECK-NEXT:    br i1 [[CMP_PEEL]], label [[FOR_BODY_PEEL_NEXT:%.*]], label [[FOR_END:%.*]]
+; CHECK:       for.body.peel.next:
+; CHECK-NEXT:    br label [[FOR_BODY_PEEL2:%.*]]
+; CHECK:       for.body.peel2:
+; CHECK-NEXT:    [[CMP1_PEEL3:%.*]] = icmp ne i32 [[INC_PEEL]], 3
+; CHECK-NEXT:    br i1 [[CMP1_PEEL3]], label [[IF_THEN_PEEL4:%.*]], label [[FOR_INC_PEEL5:%.*]]
+; CHECK:       if.then.peel4:
+; CHECK-NEXT:    call void @f1()
+; CHECK-NEXT:    br label [[FOR_INC_PEEL5]]
+; CHECK:       for.inc.peel5:
+; CHECK-NEXT:    [[INC_PEEL6:%.*]] = add nsw i32 [[INC_PEEL]], 1
+; CHECK-NEXT:    [[CMP_PEEL7:%.*]] = icmp slt i32 [[INC_PEEL6]], [[K]]
+; CHECK-NEXT:    br i1 [[CMP_PEEL7]], label [[FOR_BODY_PEEL_NEXT1:%.*]], label [[FOR_END]]
+; CHECK:       for.body.peel.next1:
+; CHECK-NEXT:    br label [[FOR_BODY_PEEL9:%.*]]
+; CHECK:       for.body.peel9:
+; CHECK-NEXT:    [[CMP1_PEEL10:%.*]] = icmp ne i32 [[INC_PEEL6]], 3
+; CHECK-NEXT:    br i1 [[CMP1_PEEL10]], label [[IF_THEN_PEEL11:%.*]], label [[FOR_INC_PEEL12:%.*]]
+; CHECK:       if.then.peel11:
+; CHECK-NEXT:    call void @f1()
+; CHECK-NEXT:    br label [[FOR_INC_PEEL12]]
+; CHECK:       for.inc.peel12:
+; CHECK-NEXT:    [[INC_PEEL13:%.*]] = add nsw i32 [[INC_PEEL6]], 1
+; CHECK-NEXT:    [[CMP_PEEL14:%.*]] = icmp slt i32 [[INC_PEEL13]], [[K]]
+; CHECK-NEXT:    br i1 [[CMP_PEEL14]], label [[FOR_BODY_PEEL_NEXT8:%.*]], label [[FOR_END]]
+; CHECK:       for.body.peel.next8:
+; CHECK-NEXT:    br label [[FOR_BODY_PEEL16:%.*]]
+; CHECK:       for.body.peel16:
+; CHECK-NEXT:    [[CMP1_PEEL17:%.*]] = icmp ne i32 [[INC_PEEL13]], 3
+; CHECK-NEXT:    br i1 [[CMP1_PEEL17]], label [[IF_THEN_PEEL18:%.*]], label [[FOR_INC_PEEL19:%.*]]
+; CHECK:       if.then.peel18:
+; CHECK-NEXT:    call void @f1()
+; CHECK-NEXT:    br label [[FOR_INC_PEEL19]]
+; CHECK:       for.inc.peel19:
+; CHECK-NEXT:    [[INC_PEEL20:%.*]] = add nsw i32 [[INC_PEEL13]], 1
+; CHECK-NEXT:    [[CMP_PEEL21:%.*]] = icmp slt i32 [[INC_PEEL20]], [[K]]
+; CHECK-NEXT:    br i1 [[CMP_PEEL21]], label [[FOR_BODY_PEEL_NEXT15:%.*]], label [[FOR_END]]
+; CHECK:       for.body.peel.next15:
+; CHECK-NEXT:    br label [[FOR_BODY_PEEL_NEXT22:%.*]]
+; CHECK:       for.body.peel.next22:
+; CHECK-NEXT:    br label [[FOR_BODY_LR_PH_PEEL_NEWPH:%.*]]
+; CHECK:       for.body.lr.ph.peel.newph:
 ; CHECK-NEXT:    br label [[FOR_BODY:%.*]]
 ; CHECK:       for.body:
-; CHECK-NEXT:    [[I_05:%.*]] = phi i32 [ 0, [[FOR_BODY_LR_PH:%.*]] ], [ [[INC:%.*]], [[FOR_INC:%.*]] ]
-; CHECK-NEXT:    [[CMP1:%.*]] = icmp ne i32 [[I_05]], 3
-; CHECK-NEXT:    br i1 [[CMP1]], label [[IF_THEN:%.*]], label [[FOR_INC]]
+; CHECK-NEXT:    [[I_05:%.*]] = phi i32 [ [[INC_PEEL20]], [[FOR_BODY_LR_PH_PEEL_NEWPH]] ], [ [[INC:%.*]], [[FOR_INC:%.*]] ]
+; CHECK-NEXT:    br i1 true, label [[IF_THEN:%.*]], label [[FOR_INC]]
 ; CHECK:       if.then:
 ; CHECK-NEXT:    call void @f1()
 ; CHECK-NEXT:    br label [[FOR_INC]]
 ; CHECK:       for.inc:
-; CHECK-NEXT:    [[INC]] = add nsw i32 [[I_05]], 1
-; CHECK-NEXT:    [[CMP:%.*]] = icmp slt i32 [[INC]], [[K:%.*]]
-; CHECK-NEXT:    br i1 [[CMP]], label [[FOR_BODY]], label [[FOR_END:%.*]]
+; CHECK-NEXT:    [[INC]] = add nuw nsw i32 [[I_05]], 1
+; CHECK-NEXT:    [[CMP:%.*]] = icmp slt i32 [[INC]], [[K]]
+; CHECK-NEXT:    br i1 [[CMP]], label [[FOR_BODY]], label [[FOR_END_LOOPEXIT:%.*]], !llvm.loop !6
+; CHECK:       for.end.loopexit:
+; CHECK-NEXT:    br label [[FOR_END]]
 ; CHECK:       for.end:
 ; CHECK-NEXT:    ret void
 ;
 for.body.lr.ph:
   br label %for.body
 
 for.body:
   %i.05 = phi i32 [ 0, %for.body.lr.ph ], [ %inc, %for.inc ]
for.inc:
   %cmp = icmp slt i32 %inc, %k
   br i1 %cmp, label %for.body, label %for.end
 
 for.end:
   ret void
 }
 
 define void @test8(i32 %k) {
-; FIXME: Could simplify loop body by peeling one additional iteration after
-;        i == 3 becomes true.
 ; CHECK-LABEL: @test8(
 ; CHECK-NEXT:  for.body.lr.ph:
+; CHECK-NEXT:    br label [[FOR_BODY_PEEL_BEGIN:%.*]]
+; CHECK:       for.body.peel.begin:
+; CHECK-NEXT:    br label [[FOR_BODY_PEEL:%.*]]
+; CHECK:       for.body.peel:
+; CHECK-NEXT:    [[CMP1_PEEL:%.*]] = icmp eq i32 0, 3
+; CHECK-NEXT:    br i1 [[CMP1_PEEL]], label [[IF_THEN_PEEL:%.*]], label [[FOR_INC_PEEL:%.*]]
+; CHECK:       if.then.peel:
+; CHECK-NEXT:    call void @f1()
+; CHECK-NEXT:    br label [[FOR_INC_PEEL]]
+; CHECK:       for.inc.peel:
+; CHECK-NEXT:    [[INC_PEEL:%.*]] = add nsw i32 0, 1
+; CHECK-NEXT:    [[CMP_PEEL:%.*]] = icmp slt i32 [[INC_PEEL]], [[K:%.*]]
+; CHECK-NEXT:    br i1 [[CMP_PEEL]], label [[FOR_BODY_PEEL_NEXT:%.*]], label [[FOR_END:%.*]]
+; CHECK:       for.body.peel.next:
+; CHECK-NEXT:    br label [[FOR_BODY_PEEL2:%.*]]
+; CHECK:       for.body.peel2:
+; CHECK-NEXT:    [[CMP1_PEEL3:%.*]] = icmp eq i32 [[INC_PEEL]], 3
+; CHECK-NEXT:    br i1 [[CMP1_PEEL3]], label [[IF_THEN_PEEL4:%.*]], label [[FOR_INC_PEEL5:%.*]]
+; CHECK:       if.then.peel4:
+; CHECK-NEXT:    call void @f1()
+; CHECK-NEXT:    br label [[FOR_INC_PEEL5]]
+; CHECK:       for.inc.peel5:
+; CHECK-NEXT:    [[INC_PEEL6:%.*]] = add nsw i32 [[INC_PEEL]], 1
+; CHECK-NEXT:    [[CMP_PEEL7:%.*]] = icmp slt i32 [[INC_PEEL6]], [[K]]
+; CHECK-NEXT:    br i1 [[CMP_PEEL7]], label [[FOR_BODY_PEEL_NEXT1:%.*]], label [[FOR_END]]
+; CHECK:       for.body.peel.next1:
+; CHECK-NEXT:    br label [[FOR_BODY_PEEL9:%.*]]
+; CHECK:       for.body.peel9:
+; CHECK-NEXT:    [[CMP1_PEEL10:%.*]] = icmp eq i32 [[INC_PEEL6]], 3
+; CHECK-NEXT:    br i1 [[CMP1_PEEL10]], label [[IF_THEN_PEEL11:%.*]], label [[FOR_INC_PEEL12:%.*]]
+; CHECK:       if.then.peel11:
+; CHECK-NEXT:    call void @f1()
+; CHECK-NEXT:    br label [[FOR_INC_PEEL12]]
+; CHECK:       for.inc.peel12:
+; CHECK-NEXT:    [[INC_PEEL13:%.*]] = add nsw i32 [[INC_PEEL6]], 1
+; CHECK-NEXT:    [[CMP_PEEL14:%.*]] = icmp slt i32 [[INC_PEEL13]], [[K]]
+; CHECK-NEXT:    br i1 [[CMP_PEEL14]], label [[FOR_BODY_PEEL_NEXT8:%.*]], label [[FOR_END]]
+; CHECK:       for.body.peel.next8:
+; CHECK-NEXT:    br label [[FOR_BODY_PEEL16:%.*]]
+; CHECK:       for.body.peel16:
+; CHECK-NEXT:    [[CMP1_PEEL17:%.*]] = icmp eq i32 [[INC_PEEL13]], 3
+; CHECK-NEXT:    br i1 [[CMP1_PEEL17]], label [[IF_THEN_PEEL18:%.*]], label [[FOR_INC_PEEL19:%.*]]
+; CHECK:       if.then.peel18:
+; CHECK-NEXT:    call void @f1()
+; CHECK-NEXT:    br label [[FOR_INC_PEEL19]]
+; CHECK:       for.inc.peel19:
+; CHECK-NEXT:    [[INC_PEEL20:%.*]] = add nsw i32 [[INC_PEEL13]], 1
+; CHECK-NEXT:    [[CMP_PEEL21:%.*]] = icmp slt i32 [[INC_PEEL20]], [[K]]
+; CHECK-NEXT:    br i1 [[CMP_PEEL21]], label [[FOR_BODY_PEEL_NEXT15:%.*]], label [[FOR_END]]
+; CHECK:       for.body.peel.next15:
+; CHECK-NEXT:    br label [[FOR_BODY_PEEL_NEXT22:%.*]]
+; CHECK:       for.body.peel.next22:
+; CHECK-NEXT:    br label [[FOR_BODY_LR_PH_PEEL_NEWPH:%.*]]
+; CHECK:       for.body.lr.ph.peel.newph:
 ; CHECK-NEXT:    br label [[FOR_BODY:%.*]]
 ; CHECK:       for.body:
-; CHECK-NEXT:    [[I_05:%.*]] = phi i32 [ 0, [[FOR_BODY_LR_PH:%.*]] ], [ [[INC:%.*]], [[FOR_INC:%.*]] ]
-; CHECK-NEXT:    [[CMP1:%.*]] = icmp eq i32 [[I_05]], 3
-; CHECK-NEXT:    br i1 [[CMP1]], label [[IF_THEN:%.*]], label [[FOR_INC]]
+; CHECK-NEXT:    [[I_05:%.*]] = phi i32 [ [[INC_PEEL20]], [[FOR_BODY_LR_PH_PEEL_NEWPH]] ], [ [[INC:%.*]], [[FOR_INC:%.*]] ]
+; CHECK-NEXT:    br i1 false, label [[IF_THEN:%.*]], label [[FOR_INC]]
 ; CHECK:       if.then:
 ; CHECK-NEXT:    call void @f1()
 ; CHECK-NEXT:    br label [[FOR_INC]]
 ; CHECK:       for.inc:
-; CHECK-NEXT:    [[INC]] = add nsw i32 [[I_05]], 1
-; CHECK-NEXT:    [[CMP:%.*]] = icmp slt i32 [[INC]], [[K:%.*]]
-; CHECK-NEXT:    br i1 [[CMP]], label [[FOR_BODY]], label [[FOR_END:%.*]]
+; CHECK-NEXT:    [[INC]] = add nuw nsw i32 [[I_05]], 1
+; CHECK-NEXT:    [[CMP:%.*]] = icmp slt i32 [[INC]], [[K]]
+; CHECK-NEXT:    br i1 [[CMP]], label [[FOR_BODY]], label [[FOR_END_LOOPEXIT:%.*]], !llvm.loop !7
+; CHECK:       for.end.loopexit:
+; CHECK-NEXT:    br label [[FOR_END]]
 ; CHECK:       for.end:
 ; CHECK-NEXT:    ret void
 ;
 for.body.lr.ph:
   br label %for.body
 
 for.body:
   %i.05 = phi i32 [ 0, %for.body.lr.ph ], [ %inc, %for.inc ]

 ; CHECK-NEXT:    br i1 false, label [[IF_THEN:%.*]], label [[IF_END]]
 ; CHECK:       if.then:
 ; CHECK-NEXT:    call void @init()
 ; CHECK-NEXT:    br label [[IF_END]]
 ; CHECK:       if.end:
 ; CHECK-NEXT:    call void @sink()
 ; CHECK-NEXT:    [[INC]] = add nuw nsw i32 [[I_06]], 1
 ; CHECK-NEXT:    [[EXITCOND:%.*]] = icmp eq i32 [[INC]], [[LEN]]
-; CHECK-NEXT:    br i1 [[EXITCOND]], label [[FOR_COND_CLEANUP_LOOPEXIT_LOOPEXIT:%.*]], label [[FOR_BODY]], !llvm.loop !6
+; CHECK-NEXT:    br i1 [[EXITCOND]], label [[FOR_COND_CLEANUP_LOOPEXIT_LOOPEXIT:%.*]], label [[FOR_BODY]], !llvm.loop !8
 ;
 entry:
   %cmp5 = icmp sgt i32 %len, 0
   br i1 %cmp5, label %for.body, label %for.cond.cleanup
 
 for.cond.cleanup:                                 ; preds = %if.end, %entry
   ret void
 

 ; CHECK-NEXT:    br i1 true, label [[IF_END]], label [[IF_THEN:%.*]]
 ; CHECK:       if.then:
 ; CHECK-NEXT:    call void @init()
 ; CHECK-NEXT:    br label [[IF_END]]
 ; CHECK:       if.end:
 ; CHECK-NEXT:    call void @sink()
 ; CHECK-NEXT:    [[INC]] = add nuw nsw i32 [[I_06]], 1
 ; CHECK-NEXT:    [[EXITCOND:%.*]] = icmp eq i32 [[INC]], [[LEN]]
-; CHECK-NEXT:    br i1 [[EXITCOND]], label [[FOR_COND_CLEANUP_LOOPEXIT_LOOPEXIT:%.*]], label [[FOR_BODY]], !llvm.loop !8
+; CHECK-NEXT:    br i1 [[EXITCOND]], label [[FOR_COND_CLEANUP_LOOPEXIT_LOOPEXIT:%.*]], label [[FOR_BODY]], !llvm.loop !10
 ;
 entry:
   %cmp5 = icmp sgt i32 %len, 0
   br i1 %cmp5, label %for.body, label %for.cond.cleanup
 
 for.cond.cleanup:                                 ; preds = %if.end, %entry
   ret void
 
 for.body:                                         ; preds = %entry, %if.end
   %i.06 = phi i32 [ %inc, %if.end ], [ 0, %entry ]
   %cmp1 = icmp sgt i32 %i.06, 0
   br i1 %cmp1, label %if.end, label %if.then
 
 if.then:                                          ; preds = %for.body
   call void @init()
   br label %if.end
 
 if.end:                                           ; preds = %if.then, %for.body
   call void @sink()
   %inc = add nuw nsw i32 %i.06, 1
   %exitcond = icmp eq i32 %inc, %len
   br i1 %exitcond, label %for.cond.cleanup, label %for.body
 }
 
+; NOTE: here we should only peel the first iteration,
+;       i.e. all calls to sink() must stay in loop.
 define void @test12__peel_first_iter_via_eq_pred(i32 %len) {
 ; CHECK-LABEL: @test12__peel_first_iter_via_eq_pred(
 ; CHECK-NEXT:  entry:
 ; CHECK-NEXT:    [[CMP5:%.*]] = icmp sgt i32 [[LEN:%.*]], 0
 ; CHECK-NEXT:    br i1 [[CMP5]], label [[FOR_BODY_PREHEADER:%.*]], label [[FOR_COND_CLEANUP:%.*]]
 ; CHECK:       for.body.preheader:
+; CHECK-NEXT:    br label [[FOR_BODY_PEEL_BEGIN:%.*]]
+; CHECK:       for.body.peel.begin:
+; CHECK-NEXT:    br label [[FOR_BODY_PEEL:%.*]]
+; CHECK:       for.body.peel:
+; CHECK-NEXT:    [[CMP1_PEEL:%.*]] = icmp eq i32 0, 0
+; CHECK-NEXT:    br i1 [[CMP1_PEEL]], label [[IF_THEN_PEEL:%.*]], label [[IF_END_PEEL:%.*]]
+; CHECK:       if.then.peel:
+; CHECK-NEXT:    call void @init()
+; CHECK-NEXT:    br label [[IF_END_PEEL]]
+; CHECK:       if.end.peel:
+; CHECK-NEXT:    call void @sink()
+; CHECK-NEXT:    [[INC_PEEL:%.*]] = add nuw nsw i32 0, 1
+; CHECK-NEXT:    [[EXITCOND_PEEL:%.*]] = icmp eq i32 [[INC_PEEL]], [[LEN]]
+; CHECK-NEXT:    br i1 [[EXITCOND_PEEL]], label [[FOR_COND_CLEANUP_LOOPEXIT:%.*]], label [[FOR_BODY_PEEL_NEXT:%.*]]
+; CHECK:       for.body.peel.next:
+; CHECK-NEXT:    br label [[FOR_BODY_PEEL_NEXT1:%.*]]
+; CHECK:       for.body.peel.next1:
+; CHECK-NEXT:    br label [[FOR_BODY_PREHEADER_PEEL_NEWPH:%.*]]
+; CHECK:       for.body.preheader.peel.newph:
 ; CHECK-NEXT:    br label [[FOR_BODY:%.*]]
+; CHECK:       for.cond.cleanup.loopexit.loopexit:
+; CHECK-NEXT:    br label [[FOR_COND_CLEANUP_LOOPEXIT]]
 ; CHECK:       for.cond.cleanup.loopexit:
 ; CHECK-NEXT:    br label [[FOR_COND_CLEANUP]]
 ; CHECK:       for.cond.cleanup:
 ; CHECK-NEXT:    ret void
 ; CHECK:       for.body:
-; CHECK-NEXT:    [[I_06:%.*]] = phi i32 [ [[INC:%.*]], [[IF_END:%.*]] ], [ 0, [[FOR_BODY_PREHEADER]] ]
-; CHECK-NEXT:    [[CMP1:%.*]] = icmp eq i32 [[I_06]], 0
-; CHECK-NEXT:    br i1 [[CMP1]], label [[IF_THEN:%.*]], label [[IF_END]]
+; CHECK-NEXT:    [[I_06:%.*]] = phi i32 [ [[INC:%.*]], [[IF_END:%.*]] ], [ [[INC_PEEL]], [[FOR_BODY_PREHEADER_PEEL_NEWPH]] ]
+; CHECK-NEXT:    br i1 false, label [[IF_THEN:%.*]], label [[IF_END]]
 ; CHECK:       if.then:
 ; CHECK-NEXT:    call void @init()
 ; CHECK-NEXT:    br label [[IF_END]]
 ; CHECK:       if.end:
 ; CHECK-NEXT:    call void @sink()
 ; CHECK-NEXT:    [[INC]] = add nuw nsw i32 [[I_06]], 1
 ; CHECK-NEXT:    [[EXITCOND:%.*]] = icmp eq i32 [[INC]], [[LEN]]
-; CHECK-NEXT:    br i1 [[EXITCOND]], label [[FOR_COND_CLEANUP_LOOPEXIT:%.*]], label [[FOR_BODY]]
+; CHECK-NEXT:    br i1 [[EXITCOND]], label [[FOR_COND_CLEANUP_LOOPEXIT_LOOPEXIT:%.*]], label [[FOR_BODY]], !llvm.loop !11
 ;
 entry:
   %cmp5 = icmp sgt i32 %len, 0
   br i1 %cmp5, label %for.body, label %for.cond.cleanup
 
 for.cond.cleanup:                                 ; preds = %if.end, %entry
   ret void
 
 for.body:                                         ; preds = %entry, %if.end
   %i.06 = phi i32 [ %inc, %if.end ], [ 0, %entry ]
   %cmp1 = icmp eq i32 %i.06, 0
   br i1 %cmp1, label %if.then, label %if.end
 
 if.then:                                          ; preds = %for.body
   call void @init()
   br label %if.end
 
 if.end:                                           ; preds = %if.then, %for.body
   call void @sink()
   %inc = add nuw nsw i32 %i.06, 1
   %exitcond = icmp eq i32 %inc, %len
   br i1 %exitcond, label %for.cond.cleanup, label %for.body
 }
 
+; NOTE: here we should only peel the first iteration,
+;       i.e. all calls to sink() must stay in loop.
 define void @test13__peel_first_iter_via_ne_pred(i32 %len) {
 ; CHECK-LABEL: @test13__peel_first_iter_via_ne_pred(
 ; CHECK-NEXT:  entry:
 ; CHECK-NEXT:    [[CMP5:%.*]] = icmp sgt i32 [[LEN:%.*]], 0
 ; CHECK-NEXT:    br i1 [[CMP5]], label [[FOR_BODY_PREHEADER:%.*]], label [[FOR_COND_CLEANUP:%.*]]
 ; CHECK:       for.body.preheader:
+; CHECK-NEXT:    br label [[FOR_BODY_PEEL_BEGIN:%.*]]
+; CHECK:       for.body.peel.begin:
+; CHECK-NEXT:    br label [[FOR_BODY_PEEL:%.*]]
+; CHECK:       for.body.peel:
+; CHECK-NEXT:    [[CMP1_PEEL:%.*]] = icmp ne i32 0, 0
+; CHECK-NEXT:    br i1 [[CMP1_PEEL]], label [[IF_END_PEEL:%.*]], label [[IF_THEN_PEEL:%.*]]
+; CHECK:       if.then.peel:
+; CHECK-NEXT:    call void @init()
+; CHECK-NEXT:    br label [[IF_END_PEEL]]
+; CHECK:       if.end.peel:
+; CHECK-NEXT:    call void @sink()
+; CHECK-NEXT:    [[INC_PEEL:%.*]] = add nuw nsw i32 0, 1
+; CHECK-NEXT:    [[EXITCOND_PEEL:%.*]] = icmp eq i32 [[INC_PEEL]], [[LEN]]
+; CHECK-NEXT:    br i1 [[EXITCOND_PEEL]], label [[FOR_COND_CLEANUP_LOOPEXIT:%.*]], label [[FOR_BODY_PEEL_NEXT:%.*]]
+; CHECK:       for.body.peel.next:
+; CHECK-NEXT:    br label [[FOR_BODY_PEEL_NEXT1:%.*]]
+; CHECK:       for.body.peel.next1:
+; CHECK-NEXT:    br label [[FOR_BODY_PREHEADER_PEEL_NEWPH:%.*]]
+; CHECK:       for.body.preheader.peel.newph:
 ; CHECK-NEXT:    br label [[FOR_BODY:%.*]]
+; CHECK:       for.cond.cleanup.loopexit.loopexit:
+; CHECK-NEXT:    br label [[FOR_COND_CLEANUP_LOOPEXIT]]
 ; CHECK:       for.cond.cleanup.loopexit:
 ; CHECK-NEXT:    br label [[FOR_COND_CLEANUP]]
 ; CHECK:       for.cond.cleanup:
 ; CHECK-NEXT:    ret void
 ; CHECK:       for.body:
-; CHECK-NEXT:    [[I_06:%.*]] = phi i32 [ [[INC:%.*]], [[IF_END:%.*]] ], [ 0, [[FOR_BODY_PREHEADER]] ]
-; CHECK-NEXT:    [[CMP1:%.*]] = icmp ne i32 [[I_06]], 0
-; CHECK-NEXT:    br i1 [[CMP1]], label [[IF_END]], label [[IF_THEN:%.*]]
+; CHECK-NEXT:    [[I_06:%.*]] = phi i32 [ [[INC:%.*]], [[IF_END:%.*]] ], [ [[INC_PEEL]], [[FOR_BODY_PREHEADER_PEEL_NEWPH]] ]
+; CHECK-NEXT:    br i1 true, label [[IF_END]], label [[IF_THEN:%.*]]
 ; CHECK:       if.then:
 ; CHECK-NEXT:    call void @init()
 ; CHECK-NEXT:    br label [[IF_END]]
 ; CHECK:       if.end:
 ; CHECK-NEXT:    call void @sink()
 ; CHECK-NEXT:    [[INC]] = add nuw nsw i32 [[I_06]], 1
 ; CHECK-NEXT:    [[EXITCOND:%.*]] = icmp eq i32 [[INC]], [[LEN]]
-; CHECK-NEXT:    br i1 [[EXITCOND]], label [[FOR_COND_CLEANUP_LOOPEXIT:%.*]], label [[FOR_BODY]]
+; CHECK-NEXT:    br i1 [[EXITCOND]], label [[FOR_COND_CLEANUP_LOOPEXIT_LOOPEXIT:%.*]], label [[FOR_BODY]], !llvm.loop !12
 ;
 entry:
   %cmp5 = icmp sgt i32 %len, 0
   br i1 %cmp5, label %for.body, label %for.cond.cleanup
 
 for.cond.cleanup:                                 ; preds = %if.end, %entry
   ret void
 
 for.body:                                         ; preds = %entry, %if.end
   %i.06 = phi i32 [ %inc, %if.end ], [ 0, %entry ]
   %cmp1 = icmp ne i32 %i.06, 0
   br i1 %cmp1, label %if.end, label %if.then
 
 if.then:                                          ; preds = %for.body
   call void @init()
   br label %if.end
 
 if.end:                                           ; preds = %if.then, %for.body
   call void @sink()
   %inc = add nuw nsw i32 %i.06, 1
   %exitcond = icmp eq i32 %inc, %len
   br i1 %exitcond, label %for.cond.cleanup, label %for.body
 }
 
+; No peeling is profitable here.
 define void @test15__ivar_mod2_is_1(i32 %len) {
 ; CHECK-LABEL: @test15__ivar_mod2_is_1(
 ; CHECK-NEXT:  entry:
 ; CHECK-NEXT:    [[CMP5:%.*]] = icmp sgt i32 [[LEN:%.*]], 0
 ; CHECK-NEXT:    br i1 [[CMP5]], label [[FOR_BODY_PREHEADER:%.*]], label [[FOR_COND_CLEANUP:%.*]]
 ; CHECK:       for.body.preheader:
 ; CHECK-NEXT:    br label [[FOR_BODY:%.*]]
 ; CHECK:       for.cond.cleanup.loopexit:

 
 if.end:                                           ; preds = %if.then, %for.body
   call void @sink()
   %inc = add nuw nsw i32 %i.06, 1
   %exitcond = icmp eq i32 %inc, %len
   br i1 %exitcond, label %for.cond.cleanup, label %for.body
 }
 
+; No peeling is profitable here.
 define void @test16__ivar_mod2_is_0(i32 %len) {
 ; CHECK-LABEL: @test16__ivar_mod2_is_0(
 ; CHECK-NEXT:  entry:
 ; CHECK-NEXT:    [[CMP5:%.*]] = icmp sgt i32 [[LEN:%.*]], 0
 ; CHECK-NEXT:    br i1 [[CMP5]], label [[FOR_BODY_PREHEADER:%.*]], label [[FOR_COND_CLEANUP:%.*]]
 ; CHECK:       for.body.preheader:
 ; CHECK-NEXT:    br label [[FOR_BODY:%.*]]
 ; CHECK:       for.cond.cleanup.loopexit:

 
 if.end:                                           ; preds = %if.then, %for.body
   call void @sink()
   %inc = add nuw nsw i32 %i.06, 1
   %exitcond = icmp eq i32 %inc, %len
   br i1 %exitcond, label %for.cond.cleanup, label %for.body
 }
 
+; Similar to @test7, we need to peel one extra iteration, and we can't do that
+; as per the -unroll-peel-max-count=4, so this shouldn't be peeled at all.
+define void @test17(i32 %k) {
+; CHECK-LABEL: @test17(
+; CHECK-NEXT:  for.body.lr.ph:
+; CHECK-NEXT:    br label [[FOR_BODY:%.*]]
+; CHECK:       for.body:
+; CHECK-NEXT:    [[I_05:%.*]] = phi i32 [ 0, [[FOR_BODY_LR_PH:%.*]] ], [ [[INC:%.*]], [[FOR_INC:%.*]] ]
+; CHECK-NEXT:    [[CMP1:%.*]] = icmp ne i32 [[I_05]], 4
+; CHECK-NEXT:    br i1 [[CMP1]], label [[IF_THEN:%.*]], label [[FOR_INC]]
+; CHECK:       if.then:
+; CHECK-NEXT:    call void @f1()
+; CHECK-NEXT:    br label [[FOR_INC]]
+; CHECK:       for.inc:
+; CHECK-NEXT:    [[INC]] = add nsw i32 [[I_05]], 1
+; CHECK-NEXT:    [[CMP:%.*]] = icmp slt i32 [[INC]], [[K:%.*]]
+; CHECK-NEXT:    br i1 [[CMP]], label [[FOR_BODY]], label [[FOR_END:%.*]]
+; CHECK:       for.end:
+; CHECK-NEXT:    ret void
+;
+for.body.lr.ph:
+  br label %for.body
+
+for.body:
+  %i.05 = phi i32 [ 0, %for.body.lr.ph ], [ %inc, %for.inc ]
+  %cmp1 = icmp ne i32 %i.05, 4
+  br i1 %cmp1, label %if.then, label %for.inc
+
+if.then:
+  call void @f1()
+  br label %for.inc
+
+for.inc:
+  %inc = add nsw i32 %i.05, 1
+  %cmp = icmp slt i32 %inc, %k
+  br i1 %cmp, label %for.body, label %for.end
+
+for.end:
+  ret void
+}
+
+; Similar to @test8, we need to peel one extra iteration, and we can't do that
+; as per the -unroll-peel-max-count=4, so this shouldn't be peeled at all.
+define void @test18(i32 %k) {
+; CHECK-LABEL: @test18(
+; CHECK-NEXT:  for.body.lr.ph:
+; CHECK-NEXT:    br label [[FOR_BODY:%.*]]
+; CHECK:       for.body:
+; CHECK-NEXT:    [[I_05:%.*]] = phi i32 [ 0, [[FOR_BODY_LR_PH:%.*]] ], [ [[INC:%.*]], [[FOR_INC:%.*]] ]
+; CHECK-NEXT:    [[CMP1:%.*]] = icmp eq i32 [[I_05]], 4
+; CHECK-NEXT:    br i1 [[CMP1]], label [[IF_THEN:%.*]], label [[FOR_INC]]
+; CHECK:       if.then:
+; CHECK-NEXT:    call void @f1()
+; CHECK-NEXT:    br label [[FOR_INC]]
+; CHECK:       for.inc:
+; CHECK-NEXT:    [[INC]] = add nsw i32 [[I_05]], 1
+; CHECK-NEXT:    [[CMP:%.*]] = icmp slt i32 [[INC]], [[K:%.*]]
+; CHECK-NEXT:    br i1 [[CMP]], label [[FOR_BODY]], label [[FOR_END:%.*]]
+; CHECK:       for.end:
+; CHECK-NEXT:    ret void
+;
+for.body.lr.ph:
+  br label %for.body
+
+for.body:
+  %i.05 = phi i32 [ 0, %for.body.lr.ph ], [ %inc, %for.inc ]
+  %cmp1 = icmp eq i32 %i.05, 4
+  br i1 %cmp1, label %if.then, label %for.inc
+
+if.then:
+  call void @f1()
+  br label %for.inc
+
+for.inc:
+  %inc = add nsw i32 %i.05, 1
+  %cmp = icmp slt i32 %inc, %k
+  br i1 %cmp, label %for.body, label %for.end
+
+for.end:
+  ret void
+}
+
 declare void @init()
 declare void @sink()