[IRCE] Enable decreasing loops of variable bounds

[samparker]

Summary

As a part 2 to my previous patch, this updates the logic for the decreasing safety checks in a similar manner:

• CanBeMax is replaced by CannotBeMaxInLoop which queries isLoopEntryGuardedByCond on the maximum value.
• SumCanReachMin is replaced by isSafeDecreasingBound which includes some logic from parseLoopStructure and, again, has been updated to use isLoopEntryGuardedByCond on the given bounds.

[mkazantsev]

Under variable bounds, do you mean somethign that varies in the loop or just a non-constant?

[mkazantsev]

lib/Transforms/Scalar/InductiveRangeCheckElimination.cpp

697

BTW, this (and same for min) look general enough to be moved to Scalar Evolution analysis. Please consider making this in future, maybe someone else will need them. For now, I'm OK with what we have here.

716

Just a general observation (this problem seems to exist in old code as well): if the predicate is unsigned, the loop cannot be decreasing. In unsigned, all values are seen as non-negative. So this logic makes no sense. Could you please check that we only come here with signed predicates? If so, please add an assert on that.

718

Assert that step is known negative?

[samparker]

lib/Transforms/Scalar/InductiveRangeCheckElimination.cpp

716

But if we know that the limit is a non negative, why couldn't an unsigned comparison be used? test_02 in decrementing-loop.ll does just this. If sub can legally handle unsigned values, I can't see why we wouldn't be able to use unsigned compares in this case.

[mkazantsev]

LGTM

lib/Transforms/Scalar/InductiveRangeCheckElimination.cpp

716

Ok, it makes sense (yet at the first glance this confused me slightly :) ). We can always legally replace sgt with ugt if we prove non-negativity of both, so I'm fine with that.

lib/Transforms/Scalar/InductiveRangeCheckElimination.cpp

 
 void LoopConstrainer::replacePHIBlock(PHINode *PN, BasicBlock *Block,
                                       BasicBlock *ReplaceBy) {
   for (unsigned i = 0, e = PN->getNumIncomingValues(); i != e; ++i)
     if (PN->getIncomingBlock(i) == Block)
       PN->setIncomingBlock(i, ReplaceBy);
 }
 
-static bool CanBeMax(ScalarEvolution &SE, const SCEV *S, bool Signed) {
-  APInt Max = Signed ?
-      APInt::getSignedMaxValue(cast<IntegerType>(S->getType())->getBitWidth()) :
-      APInt::getMaxValue(cast<IntegerType>(S->getType())->getBitWidth());
-  return SE.getSignedRange(S).contains(Max) &&
-         SE.getUnsignedRange(S).contains(Max);
+static bool CannotBeMaxInLoop(const SCEV *BoundSCEV, Loop *L,
+                              ScalarEvolution &SE, bool Signed) {
+  unsigned BitWidth = cast<IntegerType>(BoundSCEV->getType())->getBitWidth();
+  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));
+}
+
+/// 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 &&
+      Pred != ICmpInst::ICMP_ULT && Pred != ICmpInst::ICMP_UGT)
+    return false;
+
+  if (!SE.isAvailableAtLoopEntry(BoundSCEV, L))
+    return false;
+
+  DEBUG(dbgs() << "irce: isSafeDecreasingBound with:\n");
+  DEBUG(dbgs() << "irce: Start: " << *Start << "\n");
+  DEBUG(dbgs() << "irce: Step: " << *Step << "\n");
+  DEBUG(dbgs() << "irce: BoundSCEV: " << *BoundSCEV << "\n");
+  DEBUG(dbgs() << "irce: Pred: " << ICmpInst::getPredicateName(Pred) << "\n");
+  DEBUG(dbgs() << "irce: LatchExitBrIdx: " << LatchBrExitIdx << "\n");
+
+  bool IsSigned = ICmpInst::isSigned(Pred);
+  // The predicate that we need to check that the induction variable lies
+  // within bounds.
+  ICmpInst::Predicate BoundPred =
+      IsSigned ? CmpInst::ICMP_SGT : CmpInst::ICMP_UGT;
+
+  if (LatchBrExitIdx == 1)
+    return SE.isLoopEntryGuardedByCond(L, BoundPred, Start, BoundSCEV);
+
+  assert(LatchBrExitIdx == 0 &&
+         "LatchBrExitIdx should be either 0 or 1");
+  
+  const SCEV *StepPlusOne = SE.getAddExpr(Step, SE.getOne(Step->getType()));
+  unsigned BitWidth = cast<IntegerType>(BoundSCEV->getType())->getBitWidth();
+  APInt Min = IsSigned ? APInt::getSignedMinValue(BitWidth) :
+    APInt::getMinValue(BitWidth);
+  const SCEV *Limit = SE.getMinusSCEV(SE.getConstant(Min), StepPlusOne);
+
+  const SCEV *MinusOne =
+    SE.getMinusSCEV(BoundSCEV, SE.getOne(BoundSCEV->getType()));
+
+  return SE.isLoopEntryGuardedByCond(L, BoundPred, Start, MinusOne) &&
+         SE.isLoopEntryGuardedByCond(L, BoundPred, BoundSCEV, Limit);
 }
 
 static bool SumCanReachMax(ScalarEvolution &SE, const SCEV *S1, const SCEV *S2,
                            bool Signed) {
   // S1 < INT_MAX - S2 ===> S1 + S2 < INT_MAX.
   assert(SE.isKnownNonNegative(S2) &&
          "We expected the 2nd arg to be non-negative!");
   const SCEV *Max = SE.getConstant(

 static bool CanBeMin(ScalarEvolution &SE, const SCEV *S, bool Signed) {
   APInt Min = Signed ?
       APInt::getSignedMinValue(cast<IntegerType>(S->getType())->getBitWidth()) :
       APInt::getMinValue(cast<IntegerType>(S->getType())->getBitWidth());
   return SE.getSignedRange(S).contains(Min) &&
          SE.getUnsignedRange(S).contains(Min);
 }
 
-static bool SumCanReachMin(ScalarEvolution &SE, const SCEV *S1, const SCEV *S2,
-                           bool Signed) {
-  // S1 > INT_MIN - S2 ===> S1 + S2 > INT_MIN.
-  assert(SE.isKnownNonPositive(S2) &&
-         "We expected the 2nd arg to be non-positive!");
-  const SCEV *Max = SE.getConstant(
-      Signed ? APInt::getSignedMinValue(
-                   cast<IntegerType>(S1->getType())->getBitWidth())
-             : APInt::getMinValue(
-                   cast<IntegerType>(S1->getType())->getBitWidth()));
-  const SCEV *CapForS1 = SE.getMinusSCEV(Max, S2);
-  return !SE.isKnownPredicate(Signed ? ICmpInst::ICMP_SGT : ICmpInst::ICMP_UGT,
-                              S1, CapForS1);
-}
-
 Optional<LoopStructure>
 LoopStructure::parseLoopStructure(ScalarEvolution &SE,
                                   BranchProbabilityInfo *BPI, Loop &L,
                                   const char *&FailureReason) {
   if (!L.isLoopSimplifyForm()) {
     FailureReason = "loop not in LoopSimplify form";
     return None;
   }

       if (Pred == ICmpInst::ICMP_NE && LatchBrExitIdx == 1)
         // while (--i != len) {         while (--i > len) {
         //   ...                 --->     ...
         // }                            }
         // We intentionally don't turn the predicate into UGT even if we know
         // that both operands are non-negative, because it will only pessimize
         // our check against "RightSCEV - 1".
         Pred = ICmpInst::ICMP_SGT;
-      else if (Pred == ICmpInst::ICMP_EQ && LatchBrExitIdx == 0 &&
-               !CanBeMax(SE, RightSCEV, /* IsSignedPredicate */ true)) {
+      else if (Pred == ICmpInst::ICMP_EQ && LatchBrExitIdx == 0) {
         // while (true) {               while (true) {
         //   if (--i == len)     --->     if (--i < len + 1)
         //     break;                       break;
         //   ...                          ...
         // }                            }
-        // TODO: Insert ICMP_ULT if both are non-negative?
-        Pred = ICmpInst::ICMP_SLT;
-        RightSCEV = SE.getAddExpr(RightSCEV, SE.getOne(RightSCEV->getType()));
-        IncreasedRightValueByOne = true;
+        if (IndVarBase->getNoWrapFlags(SCEV::FlagNUW) &&
+            CannotBeMaxInLoop(RightSCEV, &L, SE, /* Signed */ false)) {
+          Pred = ICmpInst::ICMP_ULT;
+          RightSCEV = SE.getAddExpr(RightSCEV, SE.getOne(RightSCEV->getType()));
+          IncreasedRightValueByOne = true;
+        } else if (CannotBeMaxInLoop(RightSCEV, &L, SE, /* Signed */ true)) {
+          Pred = ICmpInst::ICMP_SLT;
+          RightSCEV = SE.getAddExpr(RightSCEV, SE.getOne(RightSCEV->getType()));
+          IncreasedRightValueByOne = true;
+        }
       }
     }
 
     bool LTPred = (Pred == ICmpInst::ICMP_SLT || Pred == ICmpInst::ICMP_ULT);
     bool GTPred = (Pred == ICmpInst::ICMP_SGT || Pred == ICmpInst::ICMP_UGT);
 
     bool FoundExpectedPred =
         (GTPred && LatchBrExitIdx == 1) || (LTPred && LatchBrExitIdx == 0);
 
     if (!FoundExpectedPred) {
       FailureReason = "expected icmp sgt semantically, found something else";
       return None;
     }
 
     IsSignedPredicate =
         Pred == ICmpInst::ICMP_SLT || Pred == ICmpInst::ICMP_SGT;
 
     if (!IsSignedPredicate && !AllowUnsignedLatchCondition) {
       FailureReason = "unsigned latch conditions are explicitly prohibited";
       return None;
     }
 
-    // The predicate that we need to check that the induction variable lies
-    // within bounds.
-    ICmpInst::Predicate BoundPred =
-        IsSignedPredicate ? CmpInst::ICMP_SGT : CmpInst::ICMP_UGT;
+    if (!isSafeDecreasingBound(IndVarStart, RightSCEV, Step, Pred,
+                               LatchBrExitIdx, &L, SE)) {
+      FailureReason = "Unsafe bounds";
+      return None;
+    }
 
     if (LatchBrExitIdx == 0) {
-      const SCEV *StepPlusOne = SE.getAddExpr(Step, SE.getOne(Step->getType()));
-      if (SumCanReachMin(SE, RightSCEV, StepPlusOne, IsSignedPredicate)) {
-        // TODO: this restriction is easily removable -- we just have to
-        // remember that the icmp was an sgt and not an sge.
-        FailureReason = "limit may overflow when coercing ge to gt";
-        return None;
-      }
-
-      if (!SE.isAvailableAtLoopEntry(RightSCEV, &L) ||
-          !SE.isLoopEntryGuardedByCond(
-               &L, BoundPred, IndVarStart,
-               SE.getMinusSCEV(RightSCEV, SE.getOne(RightSCEV->getType())))) {
-        FailureReason = "Induction variable start not bounded by lower limit";
-        return None;
-      }
-
       // We need to decrease the right value unless we have already increased
       // it virtually when we replaced EQ with SLT.
       if (!IncreasedRightValueByOne) {
         IRBuilder<> B(Preheader->getTerminator());
         RightValue = B.CreateSub(RightValue, One);
       }
     } else {
-      if (!SE.isAvailableAtLoopEntry(RightSCEV, &L) ||
-          !SE.isLoopEntryGuardedByCond(&L, BoundPred, IndVarStart, RightSCEV)) {
-        FailureReason = "Induction variable start not bounded by lower limit";
-        return None;
-      }
       assert(!IncreasedRightValueByOne &&
              "Right value can be increased only for LatchBrExitIdx == 0!");
     }
   }
   BasicBlock *LatchExit = LatchBr->getSuccessor(LatchBrExitIdx);
 
   assert(SE.getLoopDisposition(LatchCount, &L) ==
              ScalarEvolution::LoopInvariant &&

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

+; RUN: opt -irce -S -verify-loop-info -irce-print-changed-loops -irce-skip-profitability-checks %s < %s 2>&1 | FileCheck %s
+; 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-LABEL: signed_var_imm_dec_sgt(
+; CHECK: main.exit.selector:
+; CHECK: [[PSEUDO_PHI:%[^ ]+]] = phi i32 [ %dec, %for.inc ]
+; CHECK: [[COND:%[^ ]+]] = icmp sgt i32 [[PSEUDO_PHI]], %M
+; CHECK: br i1 [[COND]]
+define void @signed_var_imm_dec_sgt(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.body:                                         ; preds = %entry, %for.inc
+  %iv = phi i32 [ %dec, %for.inc ], [ 1024, %entry ]
+  %cmp1 = icmp slt i32 %iv, 1024
+  %arrayidx = getelementptr inbounds i32, i32* %b, i32 %iv
+  %0 = load i32, i32* %arrayidx, align 4
+  %arrayidx2 = getelementptr inbounds i32, i32* %c, i32 %iv
+  %1 = load i32, i32* %arrayidx2, align 4
+  %mul = mul nsw i32 %1, %0
+  %arrayidx3 = getelementptr inbounds i32, i32* %a, i32 %iv
+  br i1 %cmp1, label %for.inc, label %if.else
+
+if.else:                                          ; preds = %for.body
+  %2 = load i32, i32* %arrayidx3, align 4
+  %add = add nsw i32 %2, %mul
+  br label %for.inc
+
+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 sgt i32 %dec, %M
+  br i1 %cmp, label %for.body, label %for.cond.cleanup
+}
+
+; CHECK-LABEL: signed_var_imm_dec_sge(
+; CHECK: main.exit.selector:          ; preds = %for.inc
+; CHECK: [[PSEUDO_PHI:%[^ ]+]] = phi i32 [ %iv, %for.inc ]
+; CHECK: [[COND:%[^ ]+]] = icmp sgt i32 [[PSEUDO_PHI]], %M
+; CHECK: br i1 [[COND]]
+define void @signed_var_imm_dec_sge(i32* nocapture %a, i32* nocapture readonly %b, i32* nocapture readonly %c, i32 %M) {
+entry:
+  %cmp14 = icmp sgt i32 %M, 1024
+  br i1 %cmp14, label %for.cond.cleanup, label %for.body
+
+for.cond.cleanup:                                 ; preds = %for.inc, %entry
+  ret void
+
+for.body:                                         ; preds = %entry, %for.inc
+  %iv = phi i32 [ %dec, %for.inc ], [ 1024, %entry ]
+  %cmp1 = icmp slt i32 %iv, 1024
+  %arrayidx = getelementptr inbounds i32, i32* %b, i32 %iv
+  %0 = load i32, i32* %arrayidx, align 4
+  %arrayidx2 = getelementptr inbounds i32, i32* %c, i32 %iv
+  %1 = load i32, i32* %arrayidx2, align 4
+  %mul = mul nsw i32 %1, %0
+  %arrayidx3 = getelementptr inbounds i32, i32* %a, i32 %iv
+  br i1 %cmp1, label %for.inc, label %if.else
+
+if.else:                                          ; preds = %for.body
+  %2 = load i32, i32* %arrayidx3, align 4
+  %add = add nsw i32 %2, %mul
+  br label %for.inc
+
+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 sgt i32 %iv, %M
+  br i1 %cmp, label %for.body, label %for.cond.cleanup
+}
+
+define void @signed_var_imm_dec_slt(i32* nocapture %a, i32* nocapture readonly %b, i32* nocapture readonly %c, i32 %M) {
+entry:
+  %cmp14 = icmp sgt i32 %M, 1024
+  br i1 %cmp14, label %for.cond.cleanup, label %for.body
+
+for.cond.cleanup:                                 ; preds = %for.inc, %entry
+  ret void
+
+for.body:                                         ; preds = %entry, %for.inc
+  %iv = phi i32 [ %dec, %for.inc ], [ 1024, %entry ]
+  %cmp1 = icmp slt i32 %iv, 1024
+  %arrayidx = getelementptr inbounds i32, i32* %b, i32 %iv
+  %0 = load i32, i32* %arrayidx, align 4
+  %arrayidx2 = getelementptr inbounds i32, i32* %c, i32 %iv
+  %1 = load i32, i32* %arrayidx2, align 4
+  %mul = mul nsw i32 %1, %0
+  %arrayidx3 = getelementptr inbounds i32, i32* %a, i32 %iv
+  br i1 %cmp1, label %for.inc, label %if.else
+
+if.else:                                          ; preds = %for.body
+  %2 = load i32, i32* %arrayidx3, align 4
+  %add = add nsw i32 %2, %mul
+  br label %for.inc
+
+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 slt i32 %iv, %M
+  br i1 %cmp, label %for.cond.cleanup, label %for.body
+}
+
+; CHECK-LABEL: signed_var_imm_dec_ne(
+; CHECK: main.exit.selector:          ; preds = %for.inc
+; CHECK: [[PSEUDO_PHI:%[^ ]+]] = phi i32 [ %dec, %for.inc ]
+; CHECK: [[COND:%[^ ]+]] = icmp sgt i32 [[PSEUDO_PHI]], %M
+; CHECK: br i1 [[COND]]
+define void @signed_var_imm_dec_ne(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.body:                                         ; preds = %entry, %for.inc
+  %iv = phi i32 [ %dec, %for.inc ], [ 1024, %entry ]
+  %cmp1 = icmp slt i32 %iv, 1024
+  %arrayidx = getelementptr inbounds i32, i32* %b, i32 %iv
+  %0 = load i32, i32* %arrayidx, align 4
+  %arrayidx2 = getelementptr inbounds i32, i32* %c, i32 %iv
+  %1 = load i32, i32* %arrayidx2, align 4
+  %mul = mul nsw i32 %1, %0
+  %arrayidx3 = getelementptr inbounds i32, i32* %a, i32 %iv
+  br i1 %cmp1, label %for.inc, label %if.else
+
+if.else:                                          ; preds = %for.body
+  %2 = load i32, i32* %arrayidx3, align 4
+  %add = add nsw i32 %2, %mul
+  br label %for.inc
+
+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
+}
+
+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.body:                                         ; preds = %entry, %for.inc
+  %iv = phi i32 [ %dec, %for.inc ], [ 1024, %entry ]
+  %cmp1 = icmp slt i32 %iv, 1024
+  %arrayidx = getelementptr inbounds i32, i32* %b, i32 %iv
+  %0 = load i32, i32* %arrayidx, align 4
+  %arrayidx2 = getelementptr inbounds i32, i32* %c, i32 %iv
+  %1 = load i32, i32* %arrayidx2, align 4
+  %mul = mul nsw i32 %1, %0
+  %arrayidx3 = getelementptr inbounds i32, i32* %a, i32 %iv
+  br i1 %cmp1, label %for.inc, label %if.else
+
+if.else:                                          ; preds = %for.body
+  %2 = load i32, i32* %arrayidx3, align 4
+  %add = add nsw i32 %2, %mul
+  br label %for.inc
+
+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
+}