aboutsummaryrefslogtreecommitdiff
path: root/lib/Analysis/ScalarEvolution.cpp
diff options
context:
space:
mode:
Diffstat (limited to 'lib/Analysis/ScalarEvolution.cpp')
-rw-r--r--lib/Analysis/ScalarEvolution.cpp89
1 files changed, 73 insertions, 16 deletions
diff --git a/lib/Analysis/ScalarEvolution.cpp b/lib/Analysis/ScalarEvolution.cpp
index bc2cfd6fcc42..5ce0a1adeaa0 100644
--- a/lib/Analysis/ScalarEvolution.cpp
+++ b/lib/Analysis/ScalarEvolution.cpp
@@ -148,6 +148,7 @@ STATISTIC(NumBruteForceTripCountsComputed,
static cl::opt<unsigned>
MaxBruteForceIterations("scalar-evolution-max-iterations", cl::ReallyHidden,
+ cl::ZeroOrMore,
cl::desc("Maximum number of iterations SCEV will "
"symbolically execute a constant "
"derived loop"),
@@ -157,6 +158,9 @@ MaxBruteForceIterations("scalar-evolution-max-iterations", cl::ReallyHidden,
static cl::opt<bool> VerifySCEV(
"verify-scev", cl::Hidden,
cl::desc("Verify ScalarEvolution's backedge taken counts (slow)"));
+static cl::opt<bool> VerifySCEVStrict(
+ "verify-scev-strict", cl::Hidden,
+ cl::desc("Enable stricter verification with -verify-scev is passed"));
static cl::opt<bool>
VerifySCEVMap("verify-scev-maps", cl::Hidden,
cl::desc("Verify no dangling value in ScalarEvolution's "
@@ -1707,7 +1711,7 @@ ScalarEvolution::getZeroExtendExpr(const SCEV *Op, Type *Ty, unsigned Depth) {
// in infinite recursion. In the later case, the analysis code will
// cope with a conservative value, and it will take care to purge
// that value once it has finished.
- const SCEV *MaxBECount = getMaxBackedgeTakenCount(L);
+ const SCEV *MaxBECount = getConstantMaxBackedgeTakenCount(L);
if (!isa<SCEVCouldNotCompute>(MaxBECount)) {
// Manually compute the final value for AR, checking for
// overflow.
@@ -2051,7 +2055,7 @@ ScalarEvolution::getSignExtendExpr(const SCEV *Op, Type *Ty, unsigned Depth) {
// in infinite recursion. In the later case, the analysis code will
// cope with a conservative value, and it will take care to purge
// that value once it has finished.
- const SCEV *MaxBECount = getMaxBackedgeTakenCount(L);
+ const SCEV *MaxBECount = getConstantMaxBackedgeTakenCount(L);
if (!isa<SCEVCouldNotCompute>(MaxBECount)) {
// Manually compute the final value for AR, checking for
// overflow.
@@ -3421,7 +3425,7 @@ ScalarEvolution::getAddRecExpr(SmallVectorImpl<const SCEV *> &Operands,
return getAddRecExpr(Operands, L, SCEV::FlagAnyWrap); // {X,+,0} --> X
}
- // It's tempting to want to call getMaxBackedgeTakenCount count here and
+ // It's tempting to want to call getConstantMaxBackedgeTakenCount count here and
// use that information to infer NUW and NSW flags. However, computing a
// BE count requires calling getAddRecExpr, so we may not yet have a
// meaningful BE count at this point (and if we don't, we'd be stuck
@@ -4991,7 +4995,7 @@ const SCEV *ScalarEvolution::createSimpleAffineAddRec(PHINode *PN,
// overflow.
if (auto *BEInst = dyn_cast<Instruction>(BEValueV))
if (isLoopInvariant(Accum, L) && isAddRecNeverPoison(BEInst, L))
- (void)getAddRecExpr(getAddExpr(StartVal, Accum, Flags), Accum, L, Flags);
+ (void)getAddRecExpr(getAddExpr(StartVal, Accum), Accum, L, Flags);
return PHISCEV;
}
@@ -5596,6 +5600,22 @@ ScalarEvolution::getRangeRef(const SCEV *S,
ConservativeResult.intersectWith(X, RangeType));
}
+ if (const SCEVSMinExpr *SMin = dyn_cast<SCEVSMinExpr>(S)) {
+ ConstantRange X = getRangeRef(SMin->getOperand(0), SignHint);
+ for (unsigned i = 1, e = SMin->getNumOperands(); i != e; ++i)
+ X = X.smin(getRangeRef(SMin->getOperand(i), SignHint));
+ return setRange(SMin, SignHint,
+ ConservativeResult.intersectWith(X, RangeType));
+ }
+
+ if (const SCEVUMinExpr *UMin = dyn_cast<SCEVUMinExpr>(S)) {
+ ConstantRange X = getRangeRef(UMin->getOperand(0), SignHint);
+ for (unsigned i = 1, e = UMin->getNumOperands(); i != e; ++i)
+ X = X.umin(getRangeRef(UMin->getOperand(i), SignHint));
+ return setRange(UMin, SignHint,
+ ConservativeResult.intersectWith(X, RangeType));
+ }
+
if (const SCEVUDivExpr *UDiv = dyn_cast<SCEVUDivExpr>(S)) {
ConstantRange X = getRangeRef(UDiv->getLHS(), SignHint);
ConstantRange Y = getRangeRef(UDiv->getRHS(), SignHint);
@@ -5654,7 +5674,7 @@ ScalarEvolution::getRangeRef(const SCEV *S,
// TODO: non-affine addrec
if (AddRec->isAffine()) {
- const SCEV *MaxBECount = getMaxBackedgeTakenCount(AddRec->getLoop());
+ const SCEV *MaxBECount = getConstantMaxBackedgeTakenCount(AddRec->getLoop());
if (!isa<SCEVCouldNotCompute>(MaxBECount) &&
getTypeSizeInBits(MaxBECount->getType()) <= BitWidth) {
auto RangeFromAffine = getRangeForAffineAR(
@@ -6523,7 +6543,7 @@ unsigned ScalarEvolution::getSmallConstantTripCount(const Loop *L,
unsigned ScalarEvolution::getSmallConstantMaxTripCount(const Loop *L) {
const auto *MaxExitCount =
- dyn_cast<SCEVConstant>(getMaxBackedgeTakenCount(L));
+ dyn_cast<SCEVConstant>(getConstantMaxBackedgeTakenCount(L));
return getConstantTripCount(MaxExitCount);
}
@@ -6599,7 +6619,7 @@ const SCEV *ScalarEvolution::getBackedgeTakenCount(const Loop *L) {
/// Similar to getBackedgeTakenCount, except return the least SCEV value that is
/// known never to be less than the actual backedge taken count.
-const SCEV *ScalarEvolution::getMaxBackedgeTakenCount(const Loop *L) {
+const SCEV *ScalarEvolution::getConstantMaxBackedgeTakenCount(const Loop *L) {
return getBackedgeTakenInfo(L).getMax(this);
}
@@ -9833,6 +9853,10 @@ Optional<APInt> ScalarEvolution::computeConstantDifference(const SCEV *More,
// We avoid subtracting expressions here because this function is usually
// fairly deep in the call stack (i.e. is called many times).
+ // X - X = 0.
+ if (More == Less)
+ return APInt(getTypeSizeInBits(More->getType()), 0);
+
if (isa<SCEVAddRecExpr>(Less) && isa<SCEVAddRecExpr>(More)) {
const auto *LAR = cast<SCEVAddRecExpr>(Less);
const auto *MAR = cast<SCEVAddRecExpr>(More);
@@ -10314,10 +10338,43 @@ bool ScalarEvolution::isImpliedViaOperations(ICmpInst::Predicate Pred,
return false;
}
+static bool isKnownPredicateExtendIdiom(ICmpInst::Predicate Pred,
+ const SCEV *LHS, const SCEV *RHS) {
+ // zext x u<= sext x, sext x s<= zext x
+ switch (Pred) {
+ case ICmpInst::ICMP_SGE:
+ std::swap(LHS, RHS);
+ LLVM_FALLTHROUGH;
+ case ICmpInst::ICMP_SLE: {
+ // If operand >=s 0 then ZExt == SExt. If operand <s 0 then SExt <s ZExt.
+ const SCEVSignExtendExpr *SExt = dyn_cast<SCEVSignExtendExpr>(LHS);
+ const SCEVZeroExtendExpr *ZExt = dyn_cast<SCEVZeroExtendExpr>(RHS);
+ if (SExt && ZExt && SExt->getOperand() == ZExt->getOperand())
+ return true;
+ break;
+ }
+ case ICmpInst::ICMP_UGE:
+ std::swap(LHS, RHS);
+ LLVM_FALLTHROUGH;
+ case ICmpInst::ICMP_ULE: {
+ // If operand >=s 0 then ZExt == SExt. If operand <s 0 then ZExt <u SExt.
+ const SCEVZeroExtendExpr *ZExt = dyn_cast<SCEVZeroExtendExpr>(LHS);
+ const SCEVSignExtendExpr *SExt = dyn_cast<SCEVSignExtendExpr>(RHS);
+ if (SExt && ZExt && SExt->getOperand() == ZExt->getOperand())
+ return true;
+ break;
+ }
+ default:
+ break;
+ };
+ return false;
+}
+
bool
ScalarEvolution::isKnownViaNonRecursiveReasoning(ICmpInst::Predicate Pred,
const SCEV *LHS, const SCEV *RHS) {
- return isKnownPredicateViaConstantRanges(Pred, LHS, RHS) ||
+ return isKnownPredicateExtendIdiom(Pred, LHS, RHS) ||
+ isKnownPredicateViaConstantRanges(Pred, LHS, RHS) ||
IsKnownPredicateViaMinOrMax(*this, Pred, LHS, RHS) ||
IsKnownPredicateViaAddRecStart(*this, Pred, LHS, RHS) ||
isKnownPredicateViaNoOverflow(Pred, LHS, RHS);
@@ -11434,8 +11491,8 @@ static void PrintLoopInfo(raw_ostream &OS, ScalarEvolution *SE,
L->getHeader()->printAsOperand(OS, /*PrintType=*/false);
OS << ": ";
- if (!isa<SCEVCouldNotCompute>(SE->getMaxBackedgeTakenCount(L))) {
- OS << "max backedge-taken count is " << *SE->getMaxBackedgeTakenCount(L);
+ if (!isa<SCEVCouldNotCompute>(SE->getConstantMaxBackedgeTakenCount(L))) {
+ OS << "max backedge-taken count is " << *SE->getConstantMaxBackedgeTakenCount(L);
if (SE->isBackedgeTakenCountMaxOrZero(L))
OS << ", actual taken count either this or zero.";
} else {
@@ -11901,14 +11958,14 @@ void ScalarEvolution::verify() const {
SE.getTypeSizeInBits(NewBECount->getType()))
CurBECount = SE2.getZeroExtendExpr(CurBECount, NewBECount->getType());
- auto *ConstantDelta =
- dyn_cast<SCEVConstant>(SE2.getMinusSCEV(CurBECount, NewBECount));
+ const SCEV *Delta = SE2.getMinusSCEV(CurBECount, NewBECount);
- if (ConstantDelta && ConstantDelta->getAPInt() != 0) {
- dbgs() << "Trip Count Changed!\n";
+ // Unless VerifySCEVStrict is set, we only compare constant deltas.
+ if ((VerifySCEVStrict || isa<SCEVConstant>(Delta)) && !Delta->isZero()) {
+ dbgs() << "Trip Count for " << *L << " Changed!\n";
dbgs() << "Old: " << *CurBECount << "\n";
dbgs() << "New: " << *NewBECount << "\n";
- dbgs() << "Delta: " << *ConstantDelta << "\n";
+ dbgs() << "Delta: " << *Delta << "\n";
std::abort();
}
}
@@ -11959,7 +12016,7 @@ ScalarEvolutionWrapperPass::ScalarEvolutionWrapperPass() : FunctionPass(ID) {
bool ScalarEvolutionWrapperPass::runOnFunction(Function &F) {
SE.reset(new ScalarEvolution(
- F, getAnalysis<TargetLibraryInfoWrapperPass>().getTLI(),
+ F, getAnalysis<TargetLibraryInfoWrapperPass>().getTLI(F),
getAnalysis<AssumptionCacheTracker>().getAssumptionCache(F),
getAnalysis<DominatorTreeWrapperPass>().getDomTree(),
getAnalysis<LoopInfoWrapperPass>().getLoopInfo()));