return APIntOps::sdiv(A, B);
}
+static const APInt urem(const SCEVConstant *C1, const SCEVConstant *C2) {
+ APInt A = C1->getValue()->getValue();
+ APInt B = C2->getValue()->getValue();
+ uint32_t ABW = A.getBitWidth();
+ uint32_t BBW = B.getBitWidth();
+
+ if (ABW > BBW)
+ B = B.zext(ABW);
+ else if (ABW < BBW)
+ A = A.zext(BBW);
+
+ return APIntOps::urem(A, B);
+}
+
+static const APInt udiv(const SCEVConstant *C1, const SCEVConstant *C2) {
+ APInt A = C1->getValue()->getValue();
+ APInt B = C2->getValue()->getValue();
+ uint32_t ABW = A.getBitWidth();
+ uint32_t BBW = B.getBitWidth();
+
+ if (ABW > BBW)
+ B = B.zext(ABW);
+ else if (ABW < BBW)
+ A = A.zext(BBW);
+
+ return APIntOps::udiv(A, B);
+}
+
namespace {
struct FindSCEVSize {
int Size;
namespace {
-struct SCEVDivision : public SCEVVisitor<SCEVDivision, void> {
+template <typename Derived>
+struct SCEVDivision : public SCEVVisitor<Derived, void> {
public:
// Computes the Quotient and Remainder of the division of Numerator by
// Denominator.
const SCEV **Remainder) {
assert(Numerator && Denominator && "Uninitialized SCEV");
- SCEVDivision D(SE, Numerator, Denominator);
+ Derived D(SE, Numerator, Denominator);
// Check for the trivial case here to avoid having to check for it in the
// rest of the code.
*Remainder = D.Remainder;
}
- SCEVDivision(ScalarEvolution &S, const SCEV *Numerator, const SCEV *Denominator)
- : SE(S), Denominator(Denominator) {
- Zero = SE.getConstant(Denominator->getType(), 0);
- One = SE.getConstant(Denominator->getType(), 1);
-
- // By default, we don't know how to divide Expr by Denominator.
- // Providing the default here simplifies the rest of the code.
- Quotient = Zero;
- Remainder = Numerator;
- }
-
// Except in the trivial case described above, we do not know how to divide
// Expr by Denominator for the following functions with empty implementation.
void visitTruncateExpr(const SCEVTruncateExpr *Numerator) {}
void visitUnknown(const SCEVUnknown *Numerator) {}
void visitCouldNotCompute(const SCEVCouldNotCompute *Numerator) {}
- void visitConstant(const SCEVConstant *Numerator) {
- if (const SCEVConstant *D = dyn_cast<SCEVConstant>(Denominator)) {
- Quotient = SE.getConstant(sdiv(Numerator, D));
- Remainder = SE.getConstant(srem(Numerator, D));
- return;
- }
- }
-
void visitAddRecExpr(const SCEVAddRecExpr *Numerator) {
const SCEV *StartQ, *StartR, *StepQ, *StepR;
assert(Numerator->isAffine() && "Numerator should be affine");
}
private:
+ SCEVDivision(ScalarEvolution &S, const SCEV *Numerator,
+ const SCEV *Denominator)
+ : SE(S), Denominator(Denominator) {
+ Zero = SE.getConstant(Denominator->getType(), 0);
+ One = SE.getConstant(Denominator->getType(), 1);
+
+ // By default, we don't know how to divide Expr by Denominator.
+ // Providing the default here simplifies the rest of the code.
+ Quotient = Zero;
+ Remainder = Numerator;
+ }
+
ScalarEvolution &SE;
const SCEV *Denominator, *Quotient, *Remainder, *Zero, *One;
+
+ friend struct SCEVSDivision;
+ friend struct SCEVUDivision;
};
-}
+struct SCEVSDivision : public SCEVDivision<SCEVSDivision> {
+ SCEVSDivision(ScalarEvolution &S, const SCEV *Numerator,
+ const SCEV *Denominator)
+ : SCEVDivision(S, Numerator, Denominator) {}
+
+ void visitConstant(const SCEVConstant *Numerator) {
+ if (const SCEVConstant *D = dyn_cast<SCEVConstant>(Denominator)) {
+ Quotient = SE.getConstant(sdiv(Numerator, D));
+ Remainder = SE.getConstant(srem(Numerator, D));
+ return;
+ }
+ }
+};
+struct SCEVUDivision : public SCEVDivision<SCEVUDivision> {
+ SCEVUDivision(ScalarEvolution &S, const SCEV *Numerator,
+ const SCEV *Denominator)
+ : SCEVDivision(S, Numerator, Denominator) {}
+
+ void visitConstant(const SCEVConstant *Numerator) {
+ if (const SCEVConstant *D = dyn_cast<SCEVConstant>(Denominator)) {
+ Quotient = SE.getConstant(udiv(Numerator, D));
+ Remainder = SE.getConstant(urem(Numerator, D));
+ return;
+ }
+ }
+};
+
+}
//===----------------------------------------------------------------------===//
// Simple SCEV method implementations
return r;
}
+/// Determine if any of the operands in this SCEV are a constant or if
+/// any of the add or multiply expressions in this SCEV contain a constant.
+static bool containsConstantSomewhere(const SCEV *StartExpr) {
+ SmallVector<const SCEV *, 4> Ops;
+ Ops.push_back(StartExpr);
+ while (!Ops.empty()) {
+ const SCEV *CurrentExpr = Ops.pop_back_val();
+ if (isa<SCEVConstant>(*CurrentExpr))
+ return true;
+
+ if (isa<SCEVAddExpr>(*CurrentExpr) || isa<SCEVMulExpr>(*CurrentExpr)) {
+ const auto *CurrentNAry = cast<SCEVNAryExpr>(CurrentExpr);
+ for (const SCEV *Operand : CurrentNAry->operands())
+ Ops.push_back(Operand);
+ }
+ }
+ return false;
+}
+
/// getMulExpr - Get a canonical multiply expression, or something simpler if
/// possible.
const SCEV *ScalarEvolution::getMulExpr(SmallVectorImpl<const SCEV *> &Ops,
// C1*(C2+V) -> C1*C2 + C1*V
if (Ops.size() == 2)
- if (const SCEVAddExpr *Add = dyn_cast<SCEVAddExpr>(Ops[1]))
- if (Add->getNumOperands() == 2 &&
- isa<SCEVConstant>(Add->getOperand(0)))
- return getAddExpr(getMulExpr(LHSC, Add->getOperand(0)),
- getMulExpr(LHSC, Add->getOperand(1)));
+ if (const SCEVAddExpr *Add = dyn_cast<SCEVAddExpr>(Ops[1]))
+ // If any of Add's ops are Adds or Muls with a constant,
+ // apply this transformation as well.
+ if (Add->getNumOperands() == 2)
+ if (containsConstantSomewhere(Add))
+ return getAddExpr(getMulExpr(LHSC, Add->getOperand(0)),
+ getMulExpr(LHSC, Add->getOperand(1)));
++Idx;
while (const SCEVConstant *RHSC = dyn_cast<SCEVConstant>(Ops[Idx])) {
Visited.insert(PN);
while (!Worklist.empty()) {
Instruction *I = Worklist.pop_back_val();
- if (!Visited.insert(I)) continue;
+ if (!Visited.insert(I).second)
+ continue;
ValueExprMapType::iterator It =
ValueExprMap.find_as(static_cast<Value *>(I));
assert(NumRanges >= 1);
for (unsigned i = 0; i < NumRanges; ++i) {
- ConstantInt *Lower = cast<ConstantInt>(MD->getOperand(2*i + 0));
- ConstantInt *Upper = cast<ConstantInt>(MD->getOperand(2*i + 1));
+ ConstantInt *Lower =
+ mdconst::extract<ConstantInt>(MD->getOperand(2 * i + 0));
+ ConstantInt *Upper =
+ mdconst::extract<ConstantInt>(MD->getOperand(2 * i + 1));
ConstantRange Range(Lower->getValue(), Upper->getValue());
TotalRange = TotalRange.unionWith(Range);
}
SmallPtrSet<Instruction *, 8> Visited;
while (!Worklist.empty()) {
Instruction *I = Worklist.pop_back_val();
- if (!Visited.insert(I)) continue;
+ if (!Visited.insert(I).second)
+ continue;
ValueExprMapType::iterator It =
ValueExprMap.find_as(static_cast<Value *>(I));
SmallPtrSet<Instruction *, 8> Visited;
while (!Worklist.empty()) {
Instruction *I = Worklist.pop_back_val();
- if (!Visited.insert(I)) continue;
+ if (!Visited.insert(I).second)
+ continue;
ValueExprMapType::iterator It =
ValueExprMap.find_as(static_cast<Value *>(I));
SmallPtrSet<Instruction *, 8> Visited;
while (!Worklist.empty()) {
I = Worklist.pop_back_val();
- if (!Visited.insert(I)) continue;
+ if (!Visited.insert(I).second)
+ continue;
ValueExprMapType::iterator It =
ValueExprMap.find_as(static_cast<Value *>(I));
// backedge count.
const SCEV *Q, *R;
ScalarEvolution &SE = *const_cast<ScalarEvolution *>(this);
- SCEVDivision::divide(SE, Distance, Step, &Q, &R);
+ SCEVUDivision::divide(SE, Distance, Step, &Q, &R);
if (R->isZero()) {
const SCEV *Exact =
getUDivExactExpr(Distance, CountDown ? getNegativeSCEV(Step) : Step);
for (const SCEV *&Term : Terms) {
// Normalize the terms before the next call to findArrayDimensionsRec.
const SCEV *Q, *R;
- SCEVDivision::divide(SE, Term, Step, &Q, &R);
+ SCEVSDivision::divide(SE, Term, Step, &Q, &R);
// Bail out when GCD does not evenly divide one of the terms.
if (!R->isZero())
// Divide all terms by the element size.
for (const SCEV *&Term : Terms) {
const SCEV *Q, *R;
- SCEVDivision::divide(SE, Term, ElementSize, &Q, &R);
+ SCEVSDivision::divide(SE, Term, ElementSize, &Q, &R);
Term = Q;
}
int Last = Sizes.size() - 1;
for (int i = Last; i >= 0; i--) {
const SCEV *Q, *R;
- SCEVDivision::divide(SE, Res, Sizes[i], &Q, &R);
+ SCEVSDivision::divide(SE, Res, Sizes[i], &Q, &R);
DEBUG({
dbgs() << "Res: " << *Res << "\n";
// that until everything else is done.
if (U == Old)
continue;
- if (!Visited.insert(U))
+ if (!Visited.insert(U).second)
continue;
if (PHINode *PN = dyn_cast<PHINode>(U))
SE->ConstantEvolutionLoopExitValue.erase(PN);
projects / oota-llvm.git / blobdiff