summaryrefslogtreecommitdiffstats
path: root/llvm
diff options
context:
space:
mode:
Diffstat (limited to 'llvm')
-rw-r--r--llvm/include/llvm/Analysis/ScalarEvolution.h26
-rw-r--r--llvm/lib/Analysis/ScalarEvolution.cpp47
-rw-r--r--llvm/test/Analysis/ScalarEvolution/nsw.ll2
-rw-r--r--llvm/test/Analysis/ScalarEvolution/trip-count-pow2.ll10
4 files changed, 58 insertions, 27 deletions
diff --git a/llvm/include/llvm/Analysis/ScalarEvolution.h b/llvm/include/llvm/Analysis/ScalarEvolution.h
index ceca6cb389a..ac54bd4cfff 100644
--- a/llvm/include/llvm/Analysis/ScalarEvolution.h
+++ b/llvm/include/llvm/Analysis/ScalarEvolution.h
@@ -656,10 +656,12 @@ private:
/// Test whether this BackedgeTakenInfo contains complete information.
bool hasFullInfo() const { return isComplete(); }
- /// Return an expression indicating the exact backedge-taken count of the
- /// loop if it is known or SCEVCouldNotCompute otherwise. This is the
- /// number of times the loop header can be guaranteed to execute, minus
- /// one.
+ /// Return an expression indicating the exact *backedge-taken*
+ /// count of the loop if it is known or SCEVCouldNotCompute
+ /// otherwise. If execution makes it to the backedge on every
+ /// iteration (i.e. there are no abnormal exists like exception
+ /// throws and thread exits) then this is the number of times the
+ /// loop header will execute minus one.
///
/// If the SCEV predicate associated with the answer can be different
/// from AlwaysTrue, we must add a (non null) Predicates argument.
@@ -1398,11 +1400,11 @@ public:
const SCEV *getExitCount(const Loop *L, BasicBlock *ExitingBlock);
/// If the specified loop has a predictable backedge-taken count, return it,
- /// otherwise return a SCEVCouldNotCompute object. The backedge-taken count
- /// is the number of times the loop header will be branched to from within
- /// the loop. This is one less than the trip count of the loop, since it
- /// doesn't count the first iteration, when the header is branched to from
- /// outside the loop.
+ /// otherwise return a SCEVCouldNotCompute object. The backedge-taken count is
+ /// the number of times the loop header will be branched to from within the
+ /// loop, assuming there are no abnormal exists like exception throws. This is
+ /// one less than the trip count of the loop, since it doesn't count the first
+ /// iteration, when the header is branched to from outside the loop.
///
/// Note that it is not valid to call this method on a loop without a
/// loop-invariant backedge-taken count (see
@@ -1417,8 +1419,10 @@ public:
const SCEV *getPredicatedBackedgeTakenCount(const Loop *L,
SCEVUnionPredicate &Predicates);
- /// Similar to getBackedgeTakenCount, except return the least SCEV value
- /// that is known never to be less than the actual backedge taken count.
+ /// When successful, this returns a SCEVConstant that is greater than or equal
+ /// to (i.e. a "conservative over-approximation") of the value returend by
+ /// getBackedgeTakenCount. If such a value cannot be computed, it returns the
+ /// SCEVCouldNotCompute object.
const SCEV *getMaxBackedgeTakenCount(const Loop *L);
/// Return true if the backedge taken count is either the value returned by
diff --git a/llvm/lib/Analysis/ScalarEvolution.cpp b/llvm/lib/Analysis/ScalarEvolution.cpp
index 3f3e8cebb24..78ded8141c0 100644
--- a/llvm/lib/Analysis/ScalarEvolution.cpp
+++ b/llvm/lib/Analysis/ScalarEvolution.cpp
@@ -5947,6 +5947,8 @@ ScalarEvolution::BackedgeTakenInfo::getMax(ScalarEvolution *SE) const {
if (any_of(ExitNotTaken, PredicateNotAlwaysTrue) || !getMax())
return SE->getCouldNotCompute();
+ assert((isa<SCEVCouldNotCompute>(getMax()) || isa<SCEVConstant>(getMax())) &&
+ "No point in having a non-constant max backedge taken count!");
return getMax();
}
@@ -5972,7 +5974,11 @@ bool ScalarEvolution::BackedgeTakenInfo::hasOperand(const SCEV *S,
}
ScalarEvolution::ExitLimit::ExitLimit(const SCEV *E)
- : ExactNotTaken(E), MaxNotTaken(E), MaxOrZero(false) {}
+ : ExactNotTaken(E), MaxNotTaken(E), MaxOrZero(false) {
+ assert((isa<SCEVCouldNotCompute>(MaxNotTaken) ||
+ isa<SCEVConstant>(MaxNotTaken)) &&
+ "No point in having a non-constant max backedge taken count!");
+}
ScalarEvolution::ExitLimit::ExitLimit(
const SCEV *E, const SCEV *M, bool MaxOrZero,
@@ -5981,6 +5987,9 @@ ScalarEvolution::ExitLimit::ExitLimit(
assert((isa<SCEVCouldNotCompute>(ExactNotTaken) ||
!isa<SCEVCouldNotCompute>(MaxNotTaken)) &&
"Exact is not allowed to be less precise than Max");
+ assert((isa<SCEVCouldNotCompute>(MaxNotTaken) ||
+ isa<SCEVConstant>(MaxNotTaken)) &&
+ "No point in having a non-constant max backedge taken count!");
for (auto *PredSet : PredSetList)
for (auto *P : *PredSet)
addPredicate(P);
@@ -5989,11 +5998,19 @@ ScalarEvolution::ExitLimit::ExitLimit(
ScalarEvolution::ExitLimit::ExitLimit(
const SCEV *E, const SCEV *M, bool MaxOrZero,
const SmallPtrSetImpl<const SCEVPredicate *> &PredSet)
- : ExitLimit(E, M, MaxOrZero, {&PredSet}) {}
+ : ExitLimit(E, M, MaxOrZero, {&PredSet}) {
+ assert((isa<SCEVCouldNotCompute>(MaxNotTaken) ||
+ isa<SCEVConstant>(MaxNotTaken)) &&
+ "No point in having a non-constant max backedge taken count!");
+}
ScalarEvolution::ExitLimit::ExitLimit(const SCEV *E, const SCEV *M,
bool MaxOrZero)
- : ExitLimit(E, M, MaxOrZero, None) {}
+ : ExitLimit(E, M, MaxOrZero, None) {
+ assert((isa<SCEVCouldNotCompute>(MaxNotTaken) ||
+ isa<SCEVConstant>(MaxNotTaken)) &&
+ "No point in having a non-constant max backedge taken count!");
+}
/// Allocate memory for BackedgeTakenInfo and copy the not-taken count of each
/// computable exit into a persistent ExitNotTakenInfo array.
@@ -6018,6 +6035,8 @@ ScalarEvolution::BackedgeTakenInfo::BackedgeTakenInfo(
return ExitNotTakenInfo(ExitBB, EL.ExactNotTaken, std::move(Predicate));
});
+ assert((isa<SCEVCouldNotCompute>(MaxCount) || isa<SCEVConstant>(MaxCount)) &&
+ "No point in having a non-constant max backedge taken count!");
}
/// Invalidate this result and free the ExitNotTakenInfo array.
@@ -6279,7 +6298,7 @@ ScalarEvolution::ExitLimit ScalarEvolution::computeExitLimitFromCondImpl(
// to not.
if (isa<SCEVCouldNotCompute>(MaxBECount) &&
!isa<SCEVCouldNotCompute>(BECount))
- MaxBECount = BECount;
+ MaxBECount = getConstant(getUnsignedRange(BECount).getUnsignedMax());
return ExitLimit(BECount, MaxBECount, false,
{&EL0.Predicates, &EL1.Predicates});
@@ -7583,13 +7602,20 @@ ScalarEvolution::howFarToZero(const SCEV *V, const Loop *L, bool ControlsExit,
loopHasNoAbnormalExits(AddRec->getLoop())) {
const SCEV *Exact =
getUDivExpr(Distance, CountDown ? getNegativeSCEV(Step) : Step);
- return ExitLimit(Exact, Exact, false, Predicates);
+ const SCEV *Max =
+ Exact == getCouldNotCompute()
+ ? Exact
+ : getConstant(getUnsignedRange(Exact).getUnsignedMax());
+ return ExitLimit(Exact, Max, false, Predicates);
}
// Solve the general equation.
- const SCEV *E = SolveLinEquationWithOverflow(
- StepC->getAPInt(), getNegativeSCEV(Start), *this);
- return ExitLimit(E, E, false, Predicates);
+ const SCEV *E = SolveLinEquationWithOverflow(StepC->getAPInt(),
+ getNegativeSCEV(Start), *this);
+ const SCEV *M = E == getCouldNotCompute()
+ ? E
+ : getConstant(getUnsignedRange(E).getUnsignedMax());
+ return ExitLimit(E, M, false, Predicates);
}
ScalarEvolution::ExitLimit
@@ -9218,8 +9244,9 @@ ScalarEvolution::howManyLessThans(const SCEV *LHS, const SCEV *RHS,
getConstant(StrideForMaxBECount), false);
}
- if (isa<SCEVCouldNotCompute>(MaxBECount))
- MaxBECount = BECount;
+ if (isa<SCEVCouldNotCompute>(MaxBECount) &&
+ !isa<SCEVCouldNotCompute>(BECount))
+ MaxBECount = getConstant(getUnsignedRange(BECount).getUnsignedMax());
return ExitLimit(BECount, MaxBECount, MaxOrZero, Predicates);
}
diff --git a/llvm/test/Analysis/ScalarEvolution/nsw.ll b/llvm/test/Analysis/ScalarEvolution/nsw.ll
index a3752919d33..39b958d3ea0 100644
--- a/llvm/test/Analysis/ScalarEvolution/nsw.ll
+++ b/llvm/test/Analysis/ScalarEvolution/nsw.ll
@@ -102,7 +102,7 @@ for.body.i.i: ; preds = %entry, %for.body.i.
%cmp.i.i = icmp eq i32* %ptrincdec.i.i, %end
br i1 %cmp.i.i, label %_ZSt4fillIPiiEvT_S1_RKT0_.exit, label %for.body.i.i
; CHECK: Loop %for.body.i.i: backedge-taken count is ((-4 + (-1 * %begin) + %end) /u 4)
-; CHECK: Loop %for.body.i.i: max backedge-taken count is ((-4 + (-1 * %begin) + %end) /u 4)
+; CHECK: Loop %for.body.i.i: max backedge-taken count is 4611686018427387903
_ZSt4fillIPiiEvT_S1_RKT0_.exit: ; preds = %for.body.i.i, %entry
ret void
}
diff --git a/llvm/test/Analysis/ScalarEvolution/trip-count-pow2.ll b/llvm/test/Analysis/ScalarEvolution/trip-count-pow2.ll
index 8d053060b50..04d1b9544ab 100644
--- a/llvm/test/Analysis/ScalarEvolution/trip-count-pow2.ll
+++ b/llvm/test/Analysis/ScalarEvolution/trip-count-pow2.ll
@@ -14,7 +14,7 @@ exit:
; CHECK-LABEL: @test1
; CHECK: Loop %loop: backedge-taken count is ((-32 + (96 * %n)) /u 32)
-; CHECK: Loop %loop: max backedge-taken count is ((-32 + (96 * %n)) /u 32)
+; CHECK: Loop %loop: max backedge-taken count is 134217727
}
; PR19183
@@ -32,7 +32,7 @@ exit:
; CHECK-LABEL: @test2
; CHECK: Loop %loop: backedge-taken count is ((-32 + (32 * (%n /u 32))) /u 32)
-; CHECK: Loop %loop: max backedge-taken count is ((-32 + (32 * (%n /u 32))) /u 32)
+; CHECK: Loop %loop: max backedge-taken count is 134217727
}
define void @test3(i32 %n) {
@@ -49,7 +49,7 @@ exit:
; CHECK-LABEL: @test3
; CHECK: Loop %loop: backedge-taken count is ((-32 + (32 * %n)) /u 32)
-; CHECK: Loop %loop: max backedge-taken count is ((-32 + (32 * %n)) /u 32)
+; CHECK: Loop %loop: max backedge-taken count is 134217727
}
define void @test4(i32 %n) {
@@ -66,7 +66,7 @@ exit:
; CHECK-LABEL: @test4
; CHECK: Loop %loop: backedge-taken count is ((-4 + (-1431655764 * %n)) /u 4)
-; CHECK: Loop %loop: max backedge-taken count is ((-4 + (-1431655764 * %n)) /u 4)
+; CHECK: Loop %loop: max backedge-taken count is 1073741823
}
define void @test5(i32 %n) {
@@ -83,5 +83,5 @@ exit:
; CHECK-LABEL: @test5
; CHECK: Loop %loop: backedge-taken count is ((-4 + (4 * %n)) /u 4)
-; CHECK: Loop %loop: max backedge-taken count is ((-4 + (4 * %n)) /u 4)
+; CHECK: Loop %loop: max backedge-taken count is 1073741823
}
OpenPOWER on IntegriCloud