Fix handling of overflow in loop calculation by adding new UDiv SCEV. This SCEV
is disabled in the sense that it will refuse to create one from a UDiv
instruction, until the code is better tested.
git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@44163 91177308-0d34-0410-b5e6-96231b3b80d8
diff --git a/lib/Analysis/ScalarEvolution.cpp b/lib/Analysis/ScalarEvolution.cpp
index 6c91dca..70321fa 100644
--- a/lib/Analysis/ScalarEvolution.cpp
+++ b/lib/Analysis/ScalarEvolution.cpp
@@ -344,6 +344,24 @@
return LHS->getType();
}
+// SCEVUDivs - Only allow the creation of one SCEVUDivExpr for any particular
+// input. Don't use a SCEVHandle here, or else the object will never be
+// deleted!
+static ManagedStatic<std::map<std::pair<SCEV*, SCEV*>,
+ SCEVUDivExpr*> > SCEVUDivs;
+
+SCEVUDivExpr::~SCEVUDivExpr() {
+ SCEVUDivs->erase(std::make_pair(LHS, RHS));
+}
+
+void SCEVUDivExpr::print(std::ostream &OS) const {
+ OS << "(" << *LHS << " /u " << *RHS << ")";
+}
+
+const Type *SCEVUDivExpr::getType() const {
+ return LHS->getType();
+}
+
// SCEVAddRecExprs - Only allow the creation of one SCEVAddRecExpr for any
// particular input. Don't use a SCEVHandle here, or else the object will never
// be deleted!
@@ -573,7 +591,7 @@
for (unsigned i = 1, e = getNumOperands(); i != e; ++i) {
SCEVHandle BC = PartialFact(It, i, SE);
Divisor *= i;
- SCEVHandle Val = SE.getSDivExpr(SE.getMulExpr(BC, getOperand(i)),
+ SCEVHandle Val = SE.getUDivExpr(SE.getMulExpr(BC, getOperand(i)),
SE.getIntegerSCEV(Divisor,Ty));
Result = SE.getAddExpr(Result, Val);
}
@@ -1037,7 +1055,8 @@
return Result;
}
-SCEVHandle ScalarEvolution::getSDivExpr(const SCEVHandle &LHS, const SCEVHandle &RHS) {
+SCEVHandle ScalarEvolution::getSDivExpr(const SCEVHandle &LHS,
+ const SCEVHandle &RHS) {
if (SCEVConstant *RHSC = dyn_cast<SCEVConstant>(RHS)) {
if (RHSC->getValue()->equalsInt(1))
return LHS; // X sdiv 1 --> x
@@ -1058,6 +1077,26 @@
return Result;
}
+SCEVHandle ScalarEvolution::getUDivExpr(const SCEVHandle &LHS,
+ const SCEVHandle &RHS) {
+ if (SCEVConstant *RHSC = dyn_cast<SCEVConstant>(RHS)) {
+ if (RHSC->getValue()->equalsInt(1))
+ return LHS; // X udiv 1 --> x
+
+ if (SCEVConstant *LHSC = dyn_cast<SCEVConstant>(LHS)) {
+ Constant *LHSCV = LHSC->getValue();
+ Constant *RHSCV = RHSC->getValue();
+ return getUnknown(ConstantExpr::getUDiv(LHSCV, RHSCV));
+ }
+ }
+
+ // FIXME: implement folding of (X*4)/4 when we know X*4 doesn't overflow.
+
+ SCEVUDivExpr *&Result = (*SCEVUDivs)[std::make_pair(LHS, RHS)];
+ if (Result == 0) Result = new SCEVUDivExpr(LHS, RHS);
+ return Result;
+}
+
/// SCEVAddRecExpr::get - Get a add recurrence expression for the
/// specified loop. Simplify the expression as much as possible.
@@ -1484,8 +1523,6 @@
case Instruction::SDiv:
return SE.getSDivExpr(getSCEV(I->getOperand(0)),
getSCEV(I->getOperand(1)));
- break;
-
case Instruction::Sub:
return SE.getMinusSCEV(getSCEV(I->getOperand(0)),
getSCEV(I->getOperand(1)));
@@ -2145,6 +2182,16 @@
return SE.getSDivExpr(LHS, RHS);
}
+ if (SCEVUDivExpr *Div = dyn_cast<SCEVUDivExpr>(V)) {
+ SCEVHandle LHS = getSCEVAtScope(Div->getLHS(), L);
+ if (LHS == UnknownValue) return LHS;
+ SCEVHandle RHS = getSCEVAtScope(Div->getRHS(), L);
+ if (RHS == UnknownValue) return RHS;
+ if (LHS == Div->getLHS() && RHS == Div->getRHS())
+ return Div; // must be loop invariant
+ return SE.getUDivExpr(LHS, RHS);
+ }
+
// If this is a loop recurrence for a loop that does not contain L, then we
// are dealing with the final value computed by the loop.
if (SCEVAddRecExpr *AddRec = dyn_cast<SCEVAddRecExpr>(V)) {