SCEV::~SCEV() {}
void SCEV::dump() const {
print(cerr);
+ cerr << '\n';
}
uint32_t SCEV::getBitWidth() const {
return LHS->getType();
}
+
+// SCEVSDivs - Only allow the creation of one SCEVSDivExpr 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*>,
+ SCEVSDivExpr*> > SCEVSDivs;
+
+SCEVSDivExpr::~SCEVSDivExpr() {
+ SCEVSDivs->erase(std::make_pair(LHS, RHS));
+}
+
+void SCEVSDivExpr::print(std::ostream &OS) const {
+ OS << "(" << *LHS << " /s " << *RHS << ")";
+}
+
+const Type *SCEVSDivExpr::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!
}
SCEVHandle ScalarEvolution::getUDivExpr(const SCEVHandle &LHS, const SCEVHandle &RHS) {
+ if (LHS == RHS)
+ return getIntegerSCEV(1, LHS->getType()); // X udiv X --> 1
+
if (SCEVConstant *RHSC = dyn_cast<SCEVConstant>(RHS)) {
if (RHSC->getValue()->equalsInt(1))
- return LHS; // X udiv 1 --> x
+ return LHS; // X udiv 1 --> X
if (SCEVConstant *LHSC = dyn_cast<SCEVConstant>(LHS)) {
Constant *LHSCV = LHSC->getValue();
}
}
- // 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;
}
+SCEVHandle ScalarEvolution::getSDivExpr(const SCEVHandle &LHS, const SCEVHandle &RHS) {
+ if (LHS == RHS)
+ return getIntegerSCEV(1, LHS->getType()); // X sdiv X --> 1
+
+ if (SCEVConstant *RHSC = dyn_cast<SCEVConstant>(RHS)) {
+ if (RHSC->getValue()->equalsInt(1))
+ return LHS; // X sdiv 1 --> X
+
+ if (RHSC->getValue()->isAllOnesValue())
+ return getNegativeSCEV(LHS); // X sdiv -1 --> -X
+
+ if (SCEVConstant *LHSC = dyn_cast<SCEVConstant>(LHS)) {
+ Constant *LHSCV = LHSC->getValue();
+ Constant *RHSCV = RHSC->getValue();
+ return getUnknown(ConstantExpr::getSDiv(LHSCV, RHSCV));
+ }
+ }
+
+ SCEVSDivExpr *&Result = (*SCEVSDivs)[std::make_pair(LHS, RHS)];
+ if (Result == 0) Result = new SCEVSDivExpr(LHS, RHS);
+ return Result;
+}
+
/// SCEVAddRecExpr::get - Get a add recurrence expression for the
/// specified loop. Simplify the expression as much as possible.
return MinOpRes;
}
- // SCEVUDivExpr, SCEVUnknown
+ // SCEVUDivExpr, SCEVSDivExpr, SCEVUnknown
return 0;
}
case Instruction::UDiv:
return SE.getUDivExpr(getSCEV(U->getOperand(0)),
getSCEV(U->getOperand(1)));
+ case Instruction::SDiv:
+ return SE.getSDivExpr(getSCEV(U->getOperand(0)),
+ getSCEV(U->getOperand(1)));
case Instruction::Sub:
return SE.getMinusSCEV(getSCEV(U->getOperand(0)),
getSCEV(U->getOperand(1)));
break;
case Instruction::LShr:
- // Turn logical shift right of a constant into a unsigned divide.
+ // Turn logical shift right of a constant into an unsigned divide.
if (ConstantInt *SA = dyn_cast<ConstantInt>(U->getOperand(1))) {
uint32_t BitWidth = cast<IntegerType>(V->getType())->getBitWidth();
Constant *X = ConstantInt::get(
return Comm;
}
- if (SCEVUDivExpr *Div = dyn_cast<SCEVUDivExpr>(V)) {
- SCEVHandle LHS = getSCEVAtScope(Div->getLHS(), L);
+ if (SCEVUDivExpr *UDiv = dyn_cast<SCEVUDivExpr>(V)) {
+ SCEVHandle LHS = getSCEVAtScope(UDiv->getLHS(), L);
if (LHS == UnknownValue) return LHS;
- SCEVHandle RHS = getSCEVAtScope(Div->getRHS(), L);
+ SCEVHandle RHS = getSCEVAtScope(UDiv->getRHS(), L);
if (RHS == UnknownValue) return RHS;
- if (LHS == Div->getLHS() && RHS == Div->getRHS())
- return Div; // must be loop invariant
+ if (LHS == UDiv->getLHS() && RHS == UDiv->getRHS())
+ return UDiv; // must be loop invariant
return SE.getUDivExpr(LHS, RHS);
}
+ if (SCEVSDivExpr *SDiv = dyn_cast<SCEVSDivExpr>(V)) {
+ SCEVHandle LHS = getSCEVAtScope(SDiv->getLHS(), L);
+ if (LHS == UnknownValue) return LHS;
+ SCEVHandle RHS = getSCEVAtScope(SDiv->getRHS(), L);
+ if (RHS == UnknownValue) return RHS;
+ if (LHS == SDiv->getLHS() && RHS == SDiv->getRHS())
+ return SDiv; // must be loop invariant
+ return SE.getSDivExpr(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)) {
bool isSigned, bool trueWhenEqual) {
// Return true when the distance from RHS to maxint > Stride.
- if (!isa<SCEVConstant>(Stride))
+ SCEVConstant *SC = dyn_cast<SCEVConstant>(Stride);
+ if (!SC)
return true;
- SCEVConstant *SC = cast<SCEVConstant>(Stride);
if (SC->getValue()->isZero())
return true;
if (!trueWhenEqual && SC->getValue()->isOne())
return false;
- if (!isa<SCEVConstant>(RHS))
+ SCEVConstant *R = dyn_cast<SCEVConstant>(RHS);
+ if (!R)
return true;
- SCEVConstant *R = cast<SCEVConstant>(RHS);
-
- if (isSigned)
- return true; // XXX: because we don't have an sdiv scev.
// If negative, it wraps around every iteration, but we don't care about that.
APInt S = SC->getValue()->getValue().abs();
- APInt Dist = APInt::getMaxValue(R->getValue()->getBitWidth()) -
- R->getValue()->getValue();
+ uint32_t Width = R->getValue()->getBitWidth();
+ APInt Dist = (isSigned ? APInt::getSignedMaxValue(Width)
+ : APInt::getMaxValue(Width))
+ - R->getValue()->getValue();
+ // Because we're looking at distance, we perform an unsigned comparison,
+ // regardless of the sign of the computation.
if (trueWhenEqual)
return !S.ult(Dist);
else
// m. So, we count the number of iterations in which {n,+,s} < m is true.
// Note that we cannot simply return max(m-n,0)/s because it's not safe to
// treat m-n as signed nor unsigned due to overflow possibility.
+ //
+ // Assuming that the loop will run at least once, we know that it will
+ // run (m-n)/s times.
// First, we get the value of the LHS in the first iteration: n
SCEVHandle Start = AddRec->getOperand(0);
SCEVHandle One = SE.getIntegerSCEV(1, RHS->getType());
- // Assuming that the loop will run at least once, we know that it will
- // run (m-n)/s times.
- SCEVHandle End = RHS;
-
- if (!executesAtLeastOnce(L, isSigned, trueWhenEqual,
- SE.getMinusSCEV(Start, One), RHS)) {
- // If not, we get the value of the LHS in the first iteration in which
- // the above condition doesn't hold. This equals to max(m,n).
- End = isSigned ? SE.getSMaxExpr(RHS, Start)
- : SE.getUMaxExpr(RHS, Start);
- }
-
// If the expression is less-than-or-equal to, we need to extend the
// loop by one iteration.
//
// The loop won't actually run (m-n)/s times because the loop iterations
- // won't divide evenly. For example, if you have {2,+,5} u< 10 the
+ // might not divide cleanly. For example, if you have {2,+,5} u< 10 the
// division would equal one, but the loop runs twice putting the
// induction variable at 12.
-
+ SCEVHandle End = SE.getAddExpr(RHS, Stride);
if (!trueWhenEqual)
- // (Stride - 1) is correct only because we know it's unsigned.
- // What we really want is to decrease the magnitude of Stride by one.
- Start = SE.getMinusSCEV(Start, SE.getMinusSCEV(Stride, One));
- else
- Start = SE.getMinusSCEV(Start, Stride);
+ End = SE.getMinusSCEV(End, One);
+
+ if (!executesAtLeastOnce(L, isSigned, trueWhenEqual,
+ SE.getMinusSCEV(Start, One), RHS)) {
+ // If not, we get the value of the LHS in the first iteration in which
+ // the above condition doesn't hold. This equals to max(m,n).
+ End = isSigned ? SE.getSMaxExpr(End, Start)
+ : SE.getUMaxExpr(End, Start);
+ }
// Finally, we subtract these two values to get the number of times the
- // backedge is executed: max(m,n)-n.
+ // backedge is executed: (max(m,n)-n)/s.
+ //
+ // Note that a trip count is always positive. Using SDiv here produces
+ // wrong answers when Start < End.
return SE.getUDivExpr(SE.getMinusSCEV(End, Start), Stride);
}