[IRCE] Use NUW flag for indvar

[samparker]

Summary

IsInductionVar currently looks for nsw properties for the induction variable, and this patch now adds the use of nuw. isKnownNonNegative has also been added as a helper function which uses isLoopEntryGuardedByCond to check that the value is greater or equal than zero. If this is valid, I will extract it out into SCEV's isKnownNonNegative.

[mkazantsev]

lib/Transforms/Scalar/InductiveRangeCheckElimination.cpp

705

I don't think that these two checks make any sense, because isLoopEntryGuardedByCond makes trivial checks anyways. You are just duplicating efforts.

712

Are different values of IsSigned flag really needed here? :) You could've created zero constant just once.

936

This does not feel right. What if the indvar goes from SINT_MAX - 10 to SINT_MIN + 10 and, thus, has signed wrap? In this case it might have nuw, but if we deal with signed predicates, we might miscompile.

I think the correct approach would be to identify whether the latch predicate is signed or unsigned, and if it is unsigned, then we may check nuw instead of nsw.

972

If these two changes (i.e. checking of nuw flag and advanced non-negative) check can be separated into 2 patches, plase do.

[mkazantsev]

lib/Transforms/Scalar/InductiveRangeCheckElimination.cpp

936

BTW, why it is && and not ||? I think you were extending the scope of optimization, not narrowing it.

936

Ah, forget it, it's !... Scratch my 2nd comment on that.

[samparker]

lib/Transforms/Scalar/InductiveRangeCheckElimination.cpp

705

Removing isKnownNonNegative has no effects on the tests, but removing isKnownNegative is causing eq_ne and non_known_positive_end tests to fail. I will investigate.

712

:)

936

Good point!

[mkazantsev]

lib/Transforms/Scalar/InductiveRangeCheckElimination.cpp

705

It is strange, and maybe it is because of potential problem @ line 936. That is why I'd prefer these changes go separately. The part about isKnownNonNegative looks pretty safe, the part about nuw may be more fishy.

[samparker]

Split the helper function out to D45481 and rebased.

[mkazantsev]

lib/Transforms/Scalar/InductiveRangeCheckElimination.cpp

928

Why not (Signed && HasNoSignedWrap(AR)) || (!IsSigned && AR->hasNoUnsignedWrap())?

929

Actually I look into it and the old implementation seems suspicious to me. We only check nsw, but when we don't have nuw and actually do have an unsigned wrap, why don't we have a bug on unsigned latch predicates? Or we do, but not aware about?.. :)

929

If you look at HasNoSignedWrap, it has a bit more complex check than just looking into the immediate flag, it also tries to go through sext to find this flag. Can we do the same for nuw and zext to keep things consistent?

964

It seems to be an independent change, please commit it separately as NFC.

test/Transforms/IRCE/variable-loop-bounds.ll

328

Same, this can go as NFC without approval.

361

Please add CHECK or CHECK-NOT on existence/non-existence of preloop and postloop, so that we can make sure that IRCE does good job generating/not generating them.

Also the same applies to the tests above, you can add these checks as NFC separately (not super-urgent, but useful).

[samparker]

lib/Transforms/Scalar/InductiveRangeCheckElimination.cpp

929

Is this case handled on line 915?

929

Ok, I'll make some changes. I also need to handle equality differently, because I believe its classed as unsigned which messes up the NoSignedWrap check.

[samparker]

lib/Transforms/Scalar/InductiveRangeCheckElimination.cpp

929

I'm trying to understand test_02 of decrementing_loop. The test looks like it should work, but I can't figure out how the transform is making the decision. If I try to check nuw on unsigned and nsw on signed values, this test stops being transformed because it figures the indvar is NSW but ULT is being used.

[mkazantsev]

Hi Sam,

In test_02 in decrementing loop %idx starts from %len.a and then make a range check on %idx < %len.a which always fails on 1st iteration. In practice it means that we should have a preloop (in this particular case it means that we deoptimize on 1st iteration). So IRCE here basically makes no sense, but if it DOES happen (i.e. the compiler is not smart enough to understand its non-profitability), it MUST make a preloop.

It does not have nuw flag because of %len.a is zero then %idx.next = sub i32 %idx, 1 is calculated with passing from 0 to -1 which is an unsigned overflow, so this instruction does not have a nuw, so SCEV might also not set nuw for the addrec.

I think (I didn't check it, though) that if you insert a check %len.a != 0 above the loop and only go to the loop with this condition, it will have nuw. I hope it helps!

• Max

[mkazantsev]

lib/Transforms/Scalar/InductiveRangeCheckElimination.cpp

929

Is this case handled on line 915?

No, I mean something like

for (i = -10; i <u 10; i++)

This does have nsw but does not have a nuw because traversal from -1 to 0 is an unsigned wrap. However in this case we will fail on 1st iteration, so it sholdn't be a bug in practice, but it's still fishy.

929

See my comment, I hope it will help. I think that either inserting the check len.a != 0 before the loop or not expecting that IRCE will handle this case will be OK. I would prefer the first option of it works.

[samparker]

Hi Max,

Thanks, the reason why I don't understand why nuw isn't used is because the range data !{i32 0, i32 2147483647} is used for %len.a and the loop is only entered if %len.a != 0. The loop then exits when %idx < 2, so surely we should be able to discern that nuw is applicable? isKnownNonNegativeInLoop is also not helping in this case, but it would seem there's enough information here. Could it be that SCEV not be using the range metadata in conjunction with the entry and exit conditions?

thanks,
sam

[samparker]

Max,

After starting and playing around for the day, I've got to the root question of: why do we do the wrap checks anyway? Aren't the following range checks in the IsIncreasing/Decreasing blocks enough?

[mkazantsev]

In D45439#1065206, @samparker wrote:

Hi Max,

Thanks, the reason why I don't understand why nuw isn't used is because the range data !{i32 0, i32 2147483647} is used for %len.a and the loop is only entered if %len.a != 0. The loop then exits when %idx < 2, so surely we should be able to discern that nuw is applicable? isKnownNonNegativeInLoop is also not helping in this case, but it would seem there's enough information here. Could it be that SCEV not be using the range metadata in conjunction with the entry and exit conditions?

thanks,
sam

Wow, I've overlooked that it already has 1st iteration check. :) Well, we cannot always expect that SCEV is smart enough to do something, maybe in this particular case it simply failed to prove the non-negativity of the indvar. It's not a bug, SCEV is just now as smart as humans are. I will take a look into this case when I have some time, maybe we can improve the situation by teaching SCEV to derive nuw here. Feel free to take a look into it as well.

In D45439#1065630, @samparker wrote:

Max,

After starting and playing around for the day, I've got to the root question of: why do we do the wrap checks anyway? Aren't the following range checks in the IsIncreasing/Decreasing blocks enough?

Just omitting the nsw check is clearly wrong. Look at the logic for ne predicates.

if (Pred == ICmpInst::ICMP_NE && LatchBrExitIdx == 1)
  // while (++i != len) {         while (++i < len) {
  //   ...                 --->     ...
  // }                            }
  // If both parts are known non-negative, it is profitable to use
  // unsigned comparison in increasing loop. This allows us to make the
  // comparison check against "RightSCEV + 1" more optimistic.
  if (SE.isKnownNonNegative(IndVarStart) &&
      SE.isKnownNonNegative(RightSCEV))
    Pred = ICmpInst::ICMP_ULT;
  else
    Pred = ICmpInst::ICMP_SLT;

This will not be an equivalent transform if i is greater than len on 1st iteration but then overflows and can still reach len after that. So with ne we will make a lot of iterations and then exit the loop, and with lt we will fail on the 1st iteration.

However in other cases, when predicate was slt/ult from the beginning, it's an interesting question whether we need this condition or not. I will give it some thought and run fuzzer testing to see what happens, it should either expose some problems which are not obvious or give a clue that you might be right and we don't need NoWrap flag check at all.

[mkazantsev]

Interesting... I've made a dummy patch which lifts the restricton on nsw in cases when we are not dealing with eq/ne, and it passed 5000 complex fuzzed tests (which usually fail if there is some obvious bug). I also don't see a place where we would really need the no wrap other than eq/ne.

@samparker do you have a chance to prepare a patch that lifts this restriction? I can do it as well, but I'm a bit loaded atm. If we can get rid of no-wrap requirements at all, it will be a way better than using nuw. :)

[samparker]

Sure Max, thanks for doing the testing.

[samparker]

Now that we're only looking for nsw with equality predicates, we should now be able to use nuw as well as nsw. HasNoSignedWrap has been renamed and queries hasNoSelfWrap, while still attempting to also search for nsw.

[mkazantsev]

lib/Transforms/Scalar/InductiveRangeCheckElimination.cpp

894

This is incorrect. If counter value goes from -1 to (SINT_MAX + 1) (both included), it has both signed and unsigned wrap and has no self-wrap.

[mkazantsev]

lib/Transforms/Scalar/InductiveRangeCheckElimination.cpp

894

Just to clarify the example: we start with i = -1 and go up with step of 1 and exit the loop when i = SINT_MAX + 1. In this case when we pass from -1 to 0 we are making an unsigned wrap and when we pass from SINT_MAX to SINT_MAX + 1 we are making a signed wrap. There is no self-wrap because this variable will never reach -1 again.

[mkazantsev]

lib/Transforms/Scalar/InductiveRangeCheckElimination.cpp

907

Do you have a plan to do the same for zext? I'm OK if it's in a follow-up patch.

[samparker]

lib/Transforms/Scalar/InductiveRangeCheckElimination.cpp

894

From the SCEV header comments, I understand that NoSelfWrap can be used to query whether either nsw or nuw has been set.

907

Yes, happy to do that in a follow-up.

[mkazantsev]

lib/Transforms/Scalar/InductiveRangeCheckElimination.cpp

894

It is not quite right. If either of nsw or nuw is set then nw is also present automatically. But nw can also be present of none of those is set, like in my example of iterations from -1 to -2^31 + 1. It crosses both signed and unsigned range borders but does not cross its initial value -1.

[mkazantsev]

lib/Transforms/Scalar/InductiveRangeCheckElimination.cpp

894

I mean, it iterates from -1 to min_int + 1 with step 1, through overflow.

[samparker]

lib/Transforms/Scalar/InductiveRangeCheckElimination.cpp

894

Ah, ok, thanks.

lib/Transforms/Scalar/InductiveRangeCheckElimination.cpp

   APInt Max = Signed ? APInt::getSignedMaxValue(BitWidth) :
     APInt::getMaxValue(BitWidth);
   auto Predicate = Signed ? ICmpInst::ICMP_SLT : ICmpInst::ICMP_ULT;
   return SE.isAvailableAtLoopEntry(BoundSCEV, L) &&
          SE.isLoopEntryGuardedByCond(L, Predicate, BoundSCEV,
                                      SE.getConstant(Max));
 }
 
+static bool isKnownNonNegative(const SCEV *BoundSCEV, Loop *L,
+                               ScalarEvolution &SE) {
+  if (SE.isKnownNonNegative(BoundSCEV))
+    return true;
+  if (SE.isKnownNegative(BoundSCEV))
+    return false;
+
+  Type *Ty = BoundSCEV->getType();
+  return (SE.isLoopEntryGuardedByCond(L, ICmpInst::ICMP_SGE, BoundSCEV,
+                                      SE.getConstant(Ty, 0, true)) ||
+          SE.isLoopEntryGuardedByCond(L, ICmpInst::ICMP_UGE, BoundSCEV,
+                                      SE.getConstant(Ty, 0, false)));
+}
+
 /// Given a loop with an deccreasing induction variable, is it possible to
 /// safely calculate the bounds of a new loop using the given Predicate.
 static bool isSafeDecreasingBound(const SCEV *Start,
                                   const SCEV *BoundSCEV, const SCEV *Step,
                                   ICmpInst::Predicate Pred,
                                   unsigned LatchBrExitIdx,
                                   Loop *L, ScalarEvolution &SE) {
   if (Pred != ICmpInst::ICMP_SLT && Pred != ICmpInst::ICMP_SGT &&

   const SCEV *RightSCEV = SE.getSCEV(RightValue);
 
   // We canonicalize `ICI` such that `LeftSCEV` is an add recurrence.
   if (!isa<SCEVAddRecExpr>(LeftSCEV)) {
     if (isa<SCEVAddRecExpr>(RightSCEV)) {
       std::swap(LeftSCEV, RightSCEV);
       std::swap(LeftValue, RightValue);
       Pred = ICmpInst::getSwappedPredicate(Pred);
     } else {
       FailureReason = "no add recurrences in the icmp";
       return None;
     }
   }
 
   auto HasNoSignedWrap = [&](const SCEVAddRecExpr *AR) {
     if (AR->getNoWrapFlags(SCEV::FlagNSW))
       return true;
 
     IntegerType *Ty = cast<IntegerType>(AR->getType());
     IntegerType *WideTy =
         IntegerType::get(Ty->getContext(), Ty->getBitWidth() * 2);
 
     const SCEVAddRecExpr *ExtendAfterOp =
         dyn_cast<SCEVAddRecExpr>(SE.getSignExtendExpr(AR, WideTy));
     if (ExtendAfterOp) {
       const SCEV *ExtendedStart = SE.getSignExtendExpr(AR->getStart(), WideTy);
       const SCEV *ExtendedStep =
           SE.getSignExtendExpr(AR->getStepRecurrence(SE), WideTy);
 
       bool NoSignedWrap = ExtendAfterOp->getStart() == ExtendedStart &&
                           ExtendAfterOp->getStepRecurrence(SE) == ExtendedStep;
 
       if (NoSignedWrap)
         return true;
     }
 
     // We may have proved this when computing the sign extension above.
     return AR->getNoWrapFlags(SCEV::FlagNSW) != SCEV::FlagAnyWrap;
   };
 
   // Here we check whether the suggested AddRec is an induction variable that
   // can be handled (i.e. with known constant step), and if yes, calculate its
   // step and identify whether it is increasing or decreasing.
   auto IsInductionVar = [&](const SCEVAddRecExpr *AR, bool &IsIncreasing,
                             ConstantInt *&StepCI) {
     if (!AR->isAffine())
       return false;
 
     // Currently we only work with induction variables that have been proved to
     // not wrap.  This restriction can potentially be lifted in the future.
-
-    if (!HasNoSignedWrap(AR))
+    if (!HasNoSignedWrap(AR) && !AR->hasNoUnsignedWrap())
       return false;
 
     if (const SCEVConstant *StepExpr =
             dyn_cast<SCEVConstant>(AR->getStepRecurrence(SE))) {
       StepCI = StepExpr->getValue();
       assert(!StepCI->isZero() && "Zero step?");
       IsIncreasing = !StepCI->isNegative();
       return true;
     }
 
     return false;
   };
 
   // `ICI` is interpreted as taking the backedge if the *next* value of the
   // induction variable satisfies some constraint.
 
   const SCEVAddRecExpr *IndVarBase = cast<SCEVAddRecExpr>(LeftSCEV);
   bool IsIncreasing = false;
   bool IsSignedPredicate = true;
   ConstantInt *StepCI;
   if (!IsInductionVar(IndVarBase, IsIncreasing, StepCI)) {
     FailureReason = "LHS in icmp not induction variable";
     return None;
   }
 
   const SCEV *StartNext = IndVarBase->getStart();
   const SCEV *Addend = SE.getNegativeSCEV(IndVarBase->getStepRecurrence(SE));
   const SCEV *IndVarStart = SE.getAddExpr(StartNext, Addend);
   const SCEV *Step = SE.getSCEV(StepCI);
 
   ConstantInt *One = ConstantInt::get(IndVarTy, 1);
   if (IsIncreasing) {
     bool DecreasedRightValueByOne = false;
     if (StepCI->isOne()) {
       // Try to turn eq/ne predicates to those we can work with.
-      if (Pred == ICmpInst::ICMP_NE && LatchBrExitIdx == 1)
+      if (Pred == ICmpInst::ICMP_NE && LatchBrExitIdx == 1) {
         // while (++i != len) {         while (++i < len) {
         //   ...                 --->     ...
         // }                            }
         // If both parts are known non-negative, it is profitable to use
         // unsigned comparison in increasing loop. This allows us to make the
         // comparison check against "RightSCEV + 1" more optimistic.
-        if (SE.isKnownNonNegative(IndVarStart) &&
-            SE.isKnownNonNegative(RightSCEV))
+        if (isKnownNonNegative(IndVarStart, &L, SE) &&
+            isKnownNonNegative(RightSCEV, &L, SE))
           Pred = ICmpInst::ICMP_ULT;
         else
           Pred = ICmpInst::ICMP_SLT;
-      else if (Pred == ICmpInst::ICMP_EQ && LatchBrExitIdx == 0) {
+      } else if (Pred == ICmpInst::ICMP_EQ && LatchBrExitIdx == 0) {
         // while (true) {               while (true) {
         //   if (++i == len)     --->     if (++i > len - 1)
         //     break;                       break;
         //   ...                          ...
         // }                            }
         if (IndVarBase->getNoWrapFlags(SCEV::FlagNUW) &&
             CannotBeMinInLoop(RightSCEV, &L, SE, /*Signed*/false)) {
           Pred = ICmpInst::ICMP_UGT;

test/Transforms/IRCE/stride_more_than_1.ll

 ; RUN: opt -verify-loop-info -irce-print-changed-loops -irce -S < %s 2>&1 | FileCheck %s
 ; RUN: opt -verify-loop-info -irce-print-changed-loops -passes='require<branch-prob>,loop(irce)' -S < %s 2>&1 | FileCheck %s
 
 ; CHECK: irce: in function test_01: constrained Loop at depth 1 containing: %loop<header><exiting>,%in.bounds<latch><exiting>
 ; CHECK: irce: in function test_02: constrained Loop at depth 1 containing: %loop<header><exiting>,%in.bounds<latch><exiting>
 ; CHECK: irce: in function test_03: constrained Loop at depth 1 containing: %loop<header><exiting>,%in.bounds<latch><exiting>
-; CHECK-NOT: irce: in function test_04: constrained Loop at depth 1 containing: %loop<header><exiting>,%in.bounds<latch><exiting>
+; CHECK: irce: in function test_04: constrained Loop at depth 1 containing: %loop<header><exiting>,%in.bounds<latch><exiting>
 ; CHECK: irce: in function test_05: constrained Loop at depth 1 containing: %loop<header><exiting>,%in.bounds<latch><exiting>
 ; CHECK: irce: in function test_06: constrained Loop at depth 1 containing: %loop<header><exiting>,%in.bounds<latch><exiting>
 ; CHECK-NOT: irce: in function test_07: constrained Loop at depth 1 containing: %loop<header><exiting>,%in.bounds<latch><exiting>
 ; CHECK: irce: in function test_08: constrained Loop at depth 1 containing: %loop<header><exiting>,%in.bounds<latch><exiting>
 
 ; IV = 0; IV <s 100; IV += 7; 0 <= Len <= 50. IRCE is allowed.
 define void @test_01(i32* %arr, i32* %a_len_ptr) {
 

 
 out.of.bounds:
   ret void
 
 exit:
   ret void
 }
 
-; IV = 0; IV <s MAX_INT; IV += 7; 0 <= Len <= MAX_INT - 6. IRCE is not allowed,
-; because we cannot guarantee that IV + 7 will not exceed MAX_INT.
-; Negative test.
+; IV = 0; IV <s MAX_INT; IV += 7; 0 <= Len <= MAX_INT - 6. IRCE is allowed
+; because the branch would fail once idx.next == MAX_INT - 1 keeping the
+; access in bounds.
 define void @test_04(i32* %arr, i32* %a_len_ptr) {
 
-; CHECK:      @test_04(
+; CHECK:  @test_04(
+; CHECK:  loop:
+; CHECK:  [[IV:%[^ ]+]] = phi i32
+; CHECK:  [[IDX_NEXT:%[^ ]+]] = add i32 [[IV]], 7
+; CHECK:  main.exit.selector:
+; CHECK:  [[PSEUDO_PHI:%[^ ]+]] =  phi i32 [ [[IDX_NEXT]], %in.bounds ]
+; CHECK:  [[COND:%[^ ]+]] = icmp slt i32 [[PSEUDO_PHI]], 2147483647
+; CHECK:  br i1 [[COND]], label %main.pseudo.exit, label %exit
 
 entry:
   %len = load i32, i32* %a_len_ptr, !range !2
   br label %loop
 
 loop:
   %idx = phi i32 [ 0, %entry ], [ %idx.next, %in.bounds ]
   %idx.next = add i32 %idx, 7

test/Transforms/IRCE/variable-loop-bounds.ll

 ; RUN: opt -irce -S -verify-loop-info -irce-print-changed-loops -irce-skip-profitability-checks < %s 2>&1 | FileCheck %s
 
 ; CHECK: irce: in function test_inc_eq: constrained Loop at depth 1 containing: %for.body<header>,%if.else,%if.then,%for.inc<latch><exiting>
 ; CHECK: irce: in function test_inc_ne: constrained Loop at depth 1 containing: %for.body<header>,%if.else,%if.then,%for.inc<latch><exiting>
 ; CHECK: irce: in function test_inc_slt: constrained Loop at depth 1 containing: %for.body<header>,%if.else,%if.then,%for.inc<latch><exiting>
 ; CHECK: irce: in function test_inc_ult: constrained Loop at depth 1 containing: %for.body<header>,%if.else,%if.then,%for.inc<latch><exiting>
 ; CHECK: irce: in function signed_var_imm_dec_sgt: constrained Loop at depth 1 containing: %for.body<header>,%if.else,%for.inc<latch><exiting>
 ; CHECK-NOT: irce: in function signed_var_imm_dec_slt: constrained Loop at depth 1 containing: %for.body<header>,%if.else,%for.inc<latch><exiting>
 ; CHECK: irce: in function signed_var_imm_dec_sge: constrained Loop at depth 1 containing: %for.body<header>,%if.else,%for.inc<latch><exiting>
 ; CHECK: irce: in function signed_var_imm_dec_ne: constrained Loop at depth 1 containing: %for.body<header>,%if.else,%for.inc<latch><exiting>
 ; CHECK-NOT: irce: in function signed_var_imm_dec_eq: constrained Loop at depth 1 containing: %for.body<header>,%if.else,%for.inc<latch><exiting>
+; CHECK: irce: in function test_inc_eq_var_nuw: constrained Loop at depth 1 containing: %for.body<header>,%if.else,%if.then,%for.inc<latch><exiting>
+; CHECK: irce: in function test_inc_ne_var_nuw: constrained Loop at depth 1 containing: %for.body<header>,%if.else,%if.then,%for.inc<latch><exiting>
+; CHECK: irce: in function test_inc_ult_var_nuw: constrained Loop at depth 1 containing: %for.body<header>,%if.else,%if.then,%for.inc<latch><exiting>
+; CHECK: irce: in function test_dec_ult_ugt_var_imm_nuw: constrained Loop at depth 1 containing: %for.body<header>,%if.else,%if.then,%for.inc<latch><exiting>
 
 ; CHECK-LABEL: test_inc_eq(
 ; CHECK: main.exit.selector:
 ; CHECK: [[PSEUDO_PHI:%[^ ]+]] = phi i32 [ %inc, %for.inc ]
 ; CHECK: [[COND:%[^ ]+]] = icmp ult i32 [[PSEUDO_PHI]], %N
 ; CHECK: br i1 [[COND]], label %main.pseudo.exit, label %for.cond.cleanup.loopexit
 define void @test_inc_eq(i32* nocapture %a, i32* nocapture readonly %b, i32* nocapture readonly %c, i32 %N) {
 entry:

   %inc = add nuw nsw i32 %i.017, 1
   %exitcond = icmp eq i32 %inc, %N
   br i1 %exitcond, label %for.cond.cleanup, label %for.body
 }
 
 ; CHECK-LABEL: test_inc_ne
 ; CHECK: main.exit.selector:
 ; CHECK: [[PSEUDO_PHI:%[^ ]+]] = phi i32 [ %inc, %for.inc ]
-; CHECK: [[COND:%[^ ]+]] = icmp slt i32 [[PSEUDO_PHI]], %N
+; CHECK: [[COND:%[^ ]+]] = icmp ult i32 [[PSEUDO_PHI]], %N
 ; CHECK: br i1 [[COND]], label %main.pseudo.exit, label %for.cond.cleanup.loopexit
 define void @test_inc_ne(i32* nocapture %a, i32* nocapture readonly %b, i32* nocapture readonly %c, i32 %N) {
 entry:
   %cmp16 = icmp sgt i32 %N, 0
   br i1 %cmp16, label %for.body, label %for.cond.cleanup
 
 for.cond.cleanup:
   ret void

 for.inc:                                          ; preds = %for.body, %if.else
   %storemerge = phi i32 [ %add, %if.else ], [ %mul, %for.body ]
   store i32 %storemerge, i32* %arrayidx3, align 4
   %dec = add nsw i32 %iv, -1
   %cmp = icmp ne i32 %dec, %M
   br i1 %cmp, label %for.body, label %for.cond.cleanup
 }
 
+; CHECK-LABEL: signed_var_imm_dec_eq
 define void @signed_var_imm_dec_eq(i32* nocapture %a, i32* nocapture readonly %b, i32* nocapture readonly %c, i32 %M) {
 entry:
   %cmp14 = icmp slt i32 %M, 1024
   br i1 %cmp14, label %for.body, label %for.cond.cleanup
 
 for.cond.cleanup:                                 ; preds = %for.inc, %entry
   ret void
 

 
 for.inc:                                          ; preds = %for.body, %if.else
   %storemerge = phi i32 [ %add, %if.else ], [ %mul, %for.body ]
   store i32 %storemerge, i32* %arrayidx3, align 4
   %dec = add nsw i32 %iv, -1
   %cmp = icmp eq i32 %dec, %M
   br i1 %cmp, label %for.cond.cleanup, label %for.body
 }
+
+; CHECK-LABEL: test_inc_eq_var_nuw(
+; CHECK: main.exit.selector:
+; CHECK: [[PSEUDO_PHI:%[^ ]+]] = phi i32 [ %inc, %for.inc ]
+; CHECK: [[COND:%[^ ]+]] = icmp ult i32 [[PSEUDO_PHI]], %N
+; CHECK: br i1 [[COND]], label %main.pseudo.exit, label %for.cond.cleanup.loopexit
+define void @test_inc_eq_var_nuw(i32* nocapture %a, i32* nocapture readonly %b, i32* nocapture readonly %c, i32 %N, i32 %M) {
+entry:
+  %cmp16 = icmp ugt i32 %N, 0
+  br i1 %cmp16, label %for.body, label %for.cond.cleanup
+
+for.cond.cleanup:
+  ret void
+
+for.body:
+  %i.017 = phi i32 [ %inc, %for.inc ], [ 0, %entry ]
+  %cmp1 = icmp ult i32 %i.017, %M
+  %arrayidx = getelementptr inbounds i32, i32* %b, i32 %i.017
+  %0 = load i32, i32* %arrayidx, align 4
+  %arrayidx2 = getelementptr inbounds i32, i32* %c, i32 %i.017
+  %1 = load i32, i32* %arrayidx2, align 4
+  br i1 %cmp1, label %if.then, label %if.else
+
+if.then:
+  %sub = sub i32 %0, %1
+  %arrayidx3 = getelementptr inbounds i32, i32* %a, i32 %i.017
+  %2 = load i32, i32* %arrayidx3, align 4
+  %add = add nsw i32 %sub, %2
+  store i32 %add, i32* %arrayidx3, align 4
+  br label %for.inc
+
+if.else:
+  %add6 = add nsw i32 %1, %0
+  %arrayidx7 = getelementptr inbounds i32, i32* %a, i32 %i.017
+  store i32 %add6, i32* %arrayidx7, align 4
+  br label %for.inc
+
+for.inc:
+  %inc = add nuw i32 %i.017, 1
+  %exitcond = icmp eq i32 %inc, %N
+  br i1 %exitcond, label %for.cond.cleanup, label %for.body
+}
+
+; CHECK-LABEL: test_inc_ne_var_nuw
+; CHECK: main.exit.selector:
+; CHECK: [[PSEUDO_PHI:%[^ ]+]] = phi i32 [ %inc, %for.inc ]
+; CHECK: [[COND:%[^ ]+]] = icmp ult i32 [[PSEUDO_PHI]], %N
+; CHECK: br i1 [[COND]], label %main.pseudo.exit, label %for.cond.cleanup.loopexit
+define void @test_inc_ne_var_nuw(i32* nocapture %a, i32* nocapture readonly %b, i32* nocapture readonly %c, i32 %N, i32 %M) {
+entry:
+  %cmp16 = icmp ugt i32 %N, 0
+  br i1 %cmp16, label %for.body, label %for.cond.cleanup
+
+for.cond.cleanup:
+  ret void
+
+for.body:
+  %i.017 = phi i32 [ %inc, %for.inc ], [ 0, %entry ]
+  %cmp1 = icmp ult i32 %i.017, %M
+  %arrayidx = getelementptr inbounds i32, i32* %b, i32 %i.017
+  %0 = load i32, i32* %arrayidx, align 4
+  %arrayidx2 = getelementptr inbounds i32, i32* %c, i32 %i.017
+  %1 = load i32, i32* %arrayidx2, align 4
+  br i1 %cmp1, label %if.then, label %if.else
+
+if.then:
+  %sub = sub i32 %0, %1
+  %arrayidx3 = getelementptr inbounds i32, i32* %a, i32 %i.017
+  %2 = load i32, i32* %arrayidx3, align 4
+  %add = add nsw i32 %sub, %2
+  store i32 %add, i32* %arrayidx3, align 4
+  br label %for.inc
+
+if.else:
+  %add6 = add nsw i32 %1, %0
+  %arrayidx7 = getelementptr inbounds i32, i32* %a, i32 %i.017
+  store i32 %add6, i32* %arrayidx7, align 4
+  br label %for.inc
+
+for.inc:
+  %inc = add nuw i32 %i.017, 1
+  %exitcond = icmp ne i32 %inc, %N
+  br i1 %exitcond, label %for.body, label %for.cond.cleanup
+}
+
+; CHECK-LABEL: test_inc_ult_var_nuw
+; CHECK: main.exit.selector:
+; CHECK: [[PSEUDO_PHI:%[^ ]+]] = phi i32 [ %inc, %for.inc ]
+; CHECK: [[COND:%[^ ]+]] = icmp ult i32 [[PSEUDO_PHI]], %N
+; CHECK: br i1 [[COND]], label %main.pseudo.exit, label %for.cond.cleanup.loopexit
+define void @test_inc_ult_var_nuw(i32* nocapture %a, i32* nocapture readonly %b, i32* nocapture readonly %c, i32 %N, i32 %M) {
+entry:
+  %cmp16 = icmp ugt i32 %N, 0
+  br i1 %cmp16, label %for.body, label %for.cond.cleanup
+
+for.cond.cleanup:
+  ret void
+
+for.body:
+  %i.017 = phi i32 [ %inc, %for.inc ], [ 0, %entry ]
+  %cmp1 = icmp ult i32 %i.017, %M
+  %arrayidx = getelementptr inbounds i32, i32* %b, i32 %i.017
+  %0 = load i32, i32* %arrayidx, align 4
+  %arrayidx2 = getelementptr inbounds i32, i32* %c, i32 %i.017
+  %1 = load i32, i32* %arrayidx2, align 4
+  br i1 %cmp1, label %if.then, label %if.else
+
+if.then:
+  %sub = sub i32 %0, %1
+  %arrayidx3 = getelementptr inbounds i32, i32* %a, i32 %i.017
+  %2 = load i32, i32* %arrayidx3, align 4
+  %add = add nsw i32 %sub, %2
+  store i32 %add, i32* %arrayidx3, align 4
+  br label %for.inc
+
+if.else:
+  %add6 = add nsw i32 %1, %0
+  %arrayidx7 = getelementptr inbounds i32, i32* %a, i32 %i.017
+  store i32 %add6, i32* %arrayidx7, align 4
+  br label %for.inc
+
+for.inc:
+  %inc = add nuw i32 %i.017, 1
+  %exitcond = icmp ult i32 %inc, %N
+  br i1 %exitcond, label %for.body, label %for.cond.cleanup
+}
+
+; CHECK-LABEL: test_dec_ult_ugt_var_imm_nuw(
+; CHECK: for.body:
+; CHECK: [[IV:%[^ ]+]] = phi i32 [ %inc, %for.inc ], [ %i.017.preloop.copy, %mainloop ]
+; CHECK: [[COND:%[^ ]+]] = icmp ult i32 [[IV]], %M
+; CHECK: br i1 true, label %if.then, label %if.else
+define void @test_dec_ult_ugt_var_imm_nuw(i32* nocapture %a, i32* nocapture readonly %b, i32* nocapture readonly %c, i32 %N, i32 %M) {
+entry:
+  br label %for.body
+
+for.cond.cleanup:
+  ret void
+
+for.body:
+  %i.017 = phi i32 [ %inc, %for.inc ], [ 1024, %entry ]
+  %cmp1 = icmp ult i32 %i.017, %M
+  %arrayidx = getelementptr inbounds i32, i32* %b, i32 %i.017
+  %0 = load i32, i32* %arrayidx, align 4
+  %arrayidx2 = getelementptr inbounds i32, i32* %c, i32 %i.017
+  %1 = load i32, i32* %arrayidx2, align 4
+  br i1 %cmp1, label %if.then, label %if.else
+
+if.then:
+  %sub = sub i32 %0, %1
+  %arrayidx3 = getelementptr inbounds i32, i32* %a, i32 %i.017
+  %2 = load i32, i32* %arrayidx3, align 4
+  %add = add nsw i32 %sub, %2
+  store i32 %add, i32* %arrayidx3, align 4
+  br label %for.inc
+
+if.else:
+  %add6 = add nsw i32 %1, %0
+  %arrayidx7 = getelementptr inbounds i32, i32* %a, i32 %i.017
+  store i32 %add6, i32* %arrayidx7, align 4
+  br label %for.inc
+
+for.inc:
+  %inc = add nuw i32 %i.017, -1
+  %exitcond = icmp ugt i32 %inc, 0
+  br i1 %exitcond, label %for.body, label %for.cond.cleanup
+}
+