Teach ScalarEvolution to make use of no-overflow flags when
analyzing add recurrences.
git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@77034 91177308-0d34-0410-b5e6-96231b3b80d8
diff --git a/lib/Analysis/ScalarEvolution.cpp b/lib/Analysis/ScalarEvolution.cpp
index c77c7c4..49af579 100644
--- a/lib/Analysis/ScalarEvolution.cpp
+++ b/lib/Analysis/ScalarEvolution.cpp
@@ -734,6 +734,13 @@
unsigned BitWidth = getTypeSizeInBits(AR->getType());
const Loop *L = AR->getLoop();
+ // If we have special knowledge that this addrec won't overflow,
+ // we don't need to do any further analysis.
+ if (AR->hasNoUnsignedOverflow())
+ return getAddRecExpr(getZeroExtendExpr(Start, Ty),
+ getZeroExtendExpr(Step, Ty),
+ L);
+
// Check whether the backedge-taken count is SCEVCouldNotCompute.
// Note that this serves two purposes: It filters out loops that are
// simply not analyzable, and it covers the case where this code is
@@ -866,6 +873,13 @@
unsigned BitWidth = getTypeSizeInBits(AR->getType());
const Loop *L = AR->getLoop();
+ // If we have special knowledge that this addrec won't overflow,
+ // we don't need to do any further analysis.
+ if (AR->hasNoSignedOverflow())
+ return getAddRecExpr(getSignExtendExpr(Start, Ty),
+ getSignExtendExpr(Step, Ty),
+ L);
+
// Check whether the backedge-taken count is SCEVCouldNotCompute.
// Note that this serves two purposes: It filters out loops that are
// simply not analyzable, and it covers the case where this code is
@@ -2344,8 +2358,29 @@
cast<SCEVAddRecExpr>(Accum)->getLoop() == L)) {
const SCEV *StartVal =
getSCEV(PN->getIncomingValue(IncomingEdge));
- const SCEV *PHISCEV =
- getAddRecExpr(StartVal, Accum, L);
+ const SCEVAddRecExpr *PHISCEV =
+ cast<SCEVAddRecExpr>(getAddRecExpr(StartVal, Accum, L));
+
+ // If the increment doesn't overflow, then neither the addrec nor the
+ // post-increment will overflow.
+ if (const AddOperator *OBO = dyn_cast<AddOperator>(BEValueV))
+ if (OBO->getOperand(0) == PN &&
+ getSCEV(OBO->getOperand(1)) ==
+ PHISCEV->getStepRecurrence(*this)) {
+ const SCEVAddRecExpr *PostInc = PHISCEV->getPostIncExpr(*this);
+ if (OBO->hasNoUnsignedOverflow()) {
+ const_cast<SCEVAddRecExpr *>(PHISCEV)
+ ->setHasNoUnsignedOverflow(true);
+ const_cast<SCEVAddRecExpr *>(PostInc)
+ ->setHasNoUnsignedOverflow(true);
+ }
+ if (OBO->hasNoSignedOverflow()) {
+ const_cast<SCEVAddRecExpr *>(PHISCEV)
+ ->setHasNoSignedOverflow(true);
+ const_cast<SCEVAddRecExpr *>(PostInc)
+ ->setHasNoSignedOverflow(true);
+ }
+ }
// Okay, for the entire analysis of this edge we assumed the PHI
// to be symbolic. We now need to go back and purge all of the