[IRCE] Enable increasing loops of variable bounds
CanBeMin is currently used which will report true for any unknown
values, but often a check is performed outside the loop which covers
this situation:
for (int i = 0; i < N; ++i)
...
if (N > 0)
for (int i = 0; i < N; ++i)
...
So I've add 'LoopGuardedAgainstMin' which reports whether N is
greater than the minimum value which then allows loop with a variable
loop count to be optimised. I've also moved the increasing bound
checking into its own function and replaced SumCanReachMax is another
isLoopEntryGuardedByCond function.
llvm-svn: 328480
diff --git a/llvm/lib/Transforms/Scalar/InductiveRangeCheckElimination.cpp b/llvm/lib/Transforms/Scalar/InductiveRangeCheckElimination.cpp
index 9d965d8..940db29 100644
--- a/llvm/lib/Transforms/Scalar/InductiveRangeCheckElimination.cpp
+++ b/llvm/lib/Transforms/Scalar/InductiveRangeCheckElimination.cpp
@@ -702,27 +702,59 @@
SE.getUnsignedRange(S).contains(Max);
}
-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(
- Signed ? APInt::getSignedMaxValue(
- cast<IntegerType>(S1->getType())->getBitWidth())
- : APInt::getMaxValue(
- cast<IntegerType>(S1->getType())->getBitWidth()));
- const SCEV *CapForS1 = SE.getMinusSCEV(Max, S2);
- return !SE.isKnownPredicate(Signed ? ICmpInst::ICMP_SLT : ICmpInst::ICMP_ULT,
- S1, CapForS1);
+/// Given a loop with an increasing induction variable, is it possible to
+/// safely calculate the bounds of a new loop using the given Predicate.
+static bool isSafeIncreasingBound(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: isSafeIncreasingBound with:\n");
+ DEBUG(dbgs() << "irce: Start: " << *Start);
+ DEBUG(dbgs() << "irce: Step: " << *Step);
+ DEBUG(dbgs() << "irce: BoundSCEV: " << *BoundSCEV);
+ 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_SLT : CmpInst::ICMP_ULT;
+
+ if (LatchBrExitIdx == 1)
+ return SE.isLoopEntryGuardedByCond(L, BoundPred, Start, BoundSCEV);
+
+ assert(LatchBrExitIdx == 0 && "LatchBrExitIdx should be 0 or 1");
+
+ const SCEV *StepMinusOne =
+ SE.getMinusSCEV(Step, SE.getOne(Step->getType()));
+ unsigned BitWidth = cast<IntegerType>(BoundSCEV->getType())->getBitWidth();
+ APInt Max = IsSigned ? APInt::getSignedMaxValue(BitWidth) :
+ APInt::getMaxValue(BitWidth);
+ const SCEV *Limit = SE.getMinusSCEV(SE.getConstant(Max), StepMinusOne);
+
+ return (SE.isLoopEntryGuardedByCond(L, BoundPred, Start,
+ SE.getAddExpr(BoundSCEV, Step)) &&
+ SE.isLoopEntryGuardedByCond(L, BoundPred, BoundSCEV, Limit));
}
-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 CannotBeMinInLoop(const SCEV *BoundSCEV, Loop *L,
+ ScalarEvolution &SE, bool Signed) {
+ unsigned BitWidth = cast<IntegerType>(BoundSCEV->getType())->getBitWidth();
+ APInt Min = Signed ? APInt::getSignedMinValue(BitWidth) :
+ APInt::getMinValue(BitWidth);
+ auto Predicate = Signed ? ICmpInst::ICMP_SGT : ICmpInst::ICMP_UGT;
+ return SE.isAvailableAtLoopEntry(BoundSCEV, L) &&
+ SE.isLoopEntryGuardedByCond(L, Predicate, BoundSCEV,
+ SE.getConstant(Min));
}
static bool SumCanReachMin(ScalarEvolution &SE, const SCEV *S1, const SCEV *S2,
@@ -904,17 +936,24 @@
Pred = ICmpInst::ICMP_ULT;
else
Pred = ICmpInst::ICMP_SLT;
- else if (Pred == ICmpInst::ICMP_EQ && LatchBrExitIdx == 0 &&
- !CanBeMin(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_UGT if both are non-negative?
- Pred = ICmpInst::ICMP_SGT;
- RightSCEV = SE.getMinusSCEV(RightSCEV, SE.getOne(RightSCEV->getType()));
- DecreasedRightValueByOne = true;
+ if (IndVarBase->getNoWrapFlags(SCEV::FlagNUW) &&
+ CannotBeMinInLoop(RightSCEV, &L, SE, /*Signed*/false)) {
+ Pred = ICmpInst::ICMP_UGT;
+ RightSCEV = SE.getMinusSCEV(RightSCEV,
+ SE.getOne(RightSCEV->getType()));
+ DecreasedRightValueByOne = true;
+ } else if (CannotBeMinInLoop(RightSCEV, &L, SE, /*Signed*/true)) {
+ Pred = ICmpInst::ICMP_SGT;
+ RightSCEV = SE.getMinusSCEV(RightSCEV,
+ SE.getOne(RightSCEV->getType()));
+ DecreasedRightValueByOne = true;
+ }
}
}
@@ -928,36 +967,18 @@
return None;
}
- IsSignedPredicate =
- Pred == ICmpInst::ICMP_SLT || Pred == ICmpInst::ICMP_SGT;
-
+ IsSignedPredicate = ICmpInst::isSigned(Pred);
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_SLT : CmpInst::ICMP_ULT;
-
+ if (!isSafeIncreasingBound(IndVarStart, RightSCEV, Step, Pred,
+ LatchBrExitIdx, &L, SE)) {
+ FailureReason = "Unsafe loop bounds";
+ return None;
+ }
if (LatchBrExitIdx == 0) {
- const SCEV *StepMinusOne = SE.getMinusSCEV(Step,
- SE.getOne(Step->getType()));
- if (SumCanReachMax(SE, RightSCEV, StepMinusOne, IsSignedPredicate)) {
- // TODO: this restriction is easily removable -- we just have to
- // remember that the icmp was an slt and not an sle.
- FailureReason = "limit may overflow when coercing le to lt";
- return None;
- }
-
- if (!SE.isAvailableAtLoopEntry(RightSCEV, &L) ||
- !SE.isLoopEntryGuardedByCond(&L, BoundPred, IndVarStart,
- SE.getAddExpr(RightSCEV, Step))) {
- FailureReason = "Induction variable start not bounded by upper limit";
- return None;
- }
-
// We need to increase the right value unless we have already decreased
// it virtually when we replaced EQ with SGT.
if (!DecreasedRightValueByOne) {
@@ -965,11 +986,6 @@
RightValue = B.CreateAdd(RightValue, One);
}
} else {
- if (!SE.isAvailableAtLoopEntry(RightSCEV, &L) ||
- !SE.isLoopEntryGuardedByCond(&L, BoundPred, IndVarStart, RightSCEV)) {
- FailureReason = "Induction variable start not bounded by upper limit";
- return None;
- }
assert(!DecreasedRightValueByOne &&
"Right value can be decreased only for LatchBrExitIdx == 0!");
}
@@ -1479,13 +1495,15 @@
if (Increasing)
ExitPreLoopAtSCEV = *SR.LowLimit;
else {
- if (CanBeMin(SE, *SR.HighLimit, IsSignedPredicate)) {
+ if (CannotBeMinInLoop(*SR.HighLimit, &OriginalLoop, SE,
+ IsSignedPredicate))
+ ExitPreLoopAtSCEV = SE.getAddExpr(*SR.HighLimit, MinusOneS);
+ else {
DEBUG(dbgs() << "irce: could not prove no-overflow when computing "
<< "preloop exit limit. HighLimit = " << *(*SR.HighLimit)
<< "\n");
return false;
}
- ExitPreLoopAtSCEV = SE.getAddExpr(*SR.HighLimit, MinusOneS);
}
if (!isSafeToExpandAt(ExitPreLoopAtSCEV, InsertPt, SE)) {
@@ -1505,13 +1523,15 @@
if (Increasing)
ExitMainLoopAtSCEV = *SR.HighLimit;
else {
- if (CanBeMin(SE, *SR.LowLimit, IsSignedPredicate)) {
+ if (CannotBeMinInLoop(*SR.LowLimit, &OriginalLoop, SE,
+ IsSignedPredicate))
+ ExitMainLoopAtSCEV = SE.getAddExpr(*SR.LowLimit, MinusOneS);
+ else {
DEBUG(dbgs() << "irce: could not prove no-overflow when computing "
<< "mainloop exit limit. LowLimit = " << *(*SR.LowLimit)
<< "\n");
return false;
}
- ExitMainLoopAtSCEV = SE.getAddExpr(*SR.LowLimit, MinusOneS);
}
if (!isSafeToExpandAt(ExitMainLoopAtSCEV, InsertPt, SE)) {