diff options
| -rw-r--r-- | include/llvm/Analysis/ScalarEvolution.h | 71 | ||||
| -rw-r--r-- | include/llvm/Analysis/ScalarEvolutionExpander.h | 4 | ||||
| -rw-r--r-- | include/llvm/Analysis/ScalarEvolutionExpressions.h | 139 | ||||
| -rw-r--r-- | lib/Analysis/ScalarEvolution.cpp | 360 | ||||
| -rw-r--r-- | lib/Analysis/ScalarEvolutionExpander.cpp | 10 | ||||
| -rw-r--r-- | lib/Transforms/Scalar/IndVarSimplify.cpp | 6 | ||||
| -rw-r--r-- | lib/Transforms/Scalar/LoopStrengthReduce.cpp | 154 |
7 files changed, 388 insertions, 356 deletions
diff --git a/include/llvm/Analysis/ScalarEvolution.h b/include/llvm/Analysis/ScalarEvolution.h index b6a58fe005..9e9da6c32c 100644 --- a/include/llvm/Analysis/ScalarEvolution.h +++ b/include/llvm/Analysis/ScalarEvolution.h @@ -27,12 +27,15 @@ #include <set> namespace llvm { + class APInt; + class ConstantInt; class Instruction; class Type; class ConstantRange; class Loop; class LoopInfo; class SCEVHandle; + class ScalarEvolution; /// SCEV - This class represent an analyzed expression in the program. These /// are reference counted opaque objects that the client is not allowed to @@ -56,16 +59,6 @@ namespace llvm { public: explicit SCEV(unsigned SCEVTy) : SCEVType(SCEVTy), RefCount(0) {} - /// getNegativeSCEV - Return the SCEV object corresponding to -V. - /// - static SCEVHandle getNegativeSCEV(const SCEVHandle &V); - - /// getMinusSCEV - Return LHS-RHS. - /// - static SCEVHandle getMinusSCEV(const SCEVHandle &LHS, - const SCEVHandle &RHS); - - unsigned getSCEVType() const { return SCEVType; } /// getValueRange - Return the tightest constant bounds that this value is @@ -97,7 +90,8 @@ namespace llvm { /// returns itself. virtual SCEVHandle replaceSymbolicValuesWithConcrete(const SCEVHandle &Sym, - const SCEVHandle &Conc) const = 0; + const SCEVHandle &Conc, + ScalarEvolution &SE) const = 0; /// print - Print out the internal representation of this scalar to the /// specified stream. This should really only be used for debugging @@ -131,7 +125,8 @@ namespace llvm { void print(std::ostream *OS) const { if (OS) print(*OS); } virtual SCEVHandle replaceSymbolicValuesWithConcrete(const SCEVHandle &Sym, - const SCEVHandle &Conc) const; + const SCEVHandle &Conc, + ScalarEvolution &SE) const; /// Methods for support type inquiry through isa, cast, and dyn_cast: static inline bool classof(const SCEVCouldNotCompute *S) { return true; } @@ -204,6 +199,58 @@ namespace llvm { /// specified expression. SCEVHandle getSCEV(Value *V) const; + SCEVHandle getConstant(ConstantInt *V); + SCEVHandle getConstant(const APInt& Val); + SCEVHandle getTruncateExpr(const SCEVHandle &Op, const Type *Ty); + SCEVHandle getZeroExtendExpr(const SCEVHandle &Op, const Type *Ty); + SCEVHandle getSignExtendExpr(const SCEVHandle &Op, const Type *Ty); + SCEVHandle getAddExpr(std::vector<SCEVHandle> &Ops); + SCEVHandle getAddExpr(const SCEVHandle &LHS, const SCEVHandle &RHS) { + std::vector<SCEVHandle> Ops; + Ops.push_back(LHS); + Ops.push_back(RHS); + return getAddExpr(Ops); + } + SCEVHandle getAddExpr(const SCEVHandle &Op0, const SCEVHandle &Op1, + const SCEVHandle &Op2) { + std::vector<SCEVHandle> Ops; + Ops.push_back(Op0); + Ops.push_back(Op1); + Ops.push_back(Op2); + return getAddExpr(Ops); + } + SCEVHandle getMulExpr(std::vector<SCEVHandle> &Ops); + SCEVHandle getMulExpr(const SCEVHandle &LHS, const SCEVHandle &RHS) { + std::vector<SCEVHandle> Ops; + Ops.push_back(LHS); + Ops.push_back(RHS); + return getMulExpr(Ops); + } + SCEVHandle getSDivExpr(const SCEVHandle &LHS, const SCEVHandle &RHS); + SCEVHandle getAddRecExpr(const SCEVHandle &Start, const SCEVHandle &Step, + const Loop *L); + SCEVHandle getAddRecExpr(std::vector<SCEVHandle> &Operands, + const Loop *L); + SCEVHandle getAddRecExpr(const std::vector<SCEVHandle> &Operands, + const Loop *L) { + std::vector<SCEVHandle> NewOp(Operands); + return getAddRecExpr(NewOp, L); + } + SCEVHandle getUnknown(Value *V); + + /// getNegativeSCEV - Return the SCEV object corresponding to -V. + /// + SCEVHandle getNegativeSCEV(const SCEVHandle &V); + + /// getMinusSCEV - Return LHS-RHS. + /// + SCEVHandle getMinusSCEV(const SCEVHandle &LHS, + const SCEVHandle &RHS); + + /// getIntegerSCEV - Given an integer or FP type, create a constant for the + /// specified signed integer value and return a SCEV for the constant. + SCEVHandle getIntegerSCEV(int Val, const Type *Ty); + /// hasSCEV - Return true if the SCEV for this value has already been /// computed. bool hasSCEV(Value *V) const; diff --git a/include/llvm/Analysis/ScalarEvolutionExpander.h b/include/llvm/Analysis/ScalarEvolutionExpander.h index 8866de54df..8582067e10 100644 --- a/include/llvm/Analysis/ScalarEvolutionExpander.h +++ b/include/llvm/Analysis/ScalarEvolutionExpander.h @@ -61,8 +61,8 @@ namespace llvm { /// starts at zero and steps by one on each iteration. Value *getOrInsertCanonicalInductionVariable(const Loop *L, const Type *Ty){ assert(Ty->isInteger() && "Can only insert integer induction variables!"); - SCEVHandle H = SCEVAddRecExpr::get(SCEVUnknown::getIntegerSCEV(0, Ty), - SCEVUnknown::getIntegerSCEV(1, Ty), L); + SCEVHandle H = SE.getAddRecExpr(SE.getIntegerSCEV(0, Ty), + SE.getIntegerSCEV(1, Ty), L); return expand(H); } diff --git a/include/llvm/Analysis/ScalarEvolutionExpressions.h b/include/llvm/Analysis/ScalarEvolutionExpressions.h index af1656ee8e..7fbeff7de0 100644 --- a/include/llvm/Analysis/ScalarEvolutionExpressions.h +++ b/include/llvm/Analysis/ScalarEvolutionExpressions.h @@ -32,16 +32,13 @@ namespace llvm { /// SCEVConstant - This class represents a constant integer value. /// class SCEVConstant : public SCEV { + friend class ScalarEvolution; + ConstantInt *V; explicit SCEVConstant(ConstantInt *v) : SCEV(scConstant), V(v) {} virtual ~SCEVConstant(); public: - /// get method - This just gets and returns a new SCEVConstant object. - /// - static SCEVHandle get(ConstantInt *V); - static SCEVHandle get(const APInt& Val); - ConstantInt *getValue() const { return V; } /// getValueRange - Return the tightest constant bounds that this value is @@ -59,7 +56,8 @@ namespace llvm { virtual const Type *getType() const; SCEVHandle replaceSymbolicValuesWithConcrete(const SCEVHandle &Sym, - const SCEVHandle &Conc) const { + const SCEVHandle &Conc, + ScalarEvolution &SE) const { return this; } @@ -78,15 +76,13 @@ namespace llvm { /// to a smaller integer value. /// class SCEVTruncateExpr : public SCEV { + friend class ScalarEvolution; + SCEVHandle Op; const Type *Ty; SCEVTruncateExpr(const SCEVHandle &op, const Type *ty); virtual ~SCEVTruncateExpr(); public: - /// get method - This just gets and returns a new SCEVTruncate object - /// - static SCEVHandle get(const SCEVHandle &Op, const Type *Ty); - const SCEVHandle &getOperand() const { return Op; } virtual const Type *getType() const { return Ty; } @@ -99,11 +95,12 @@ namespace llvm { } SCEVHandle replaceSymbolicValuesWithConcrete(const SCEVHandle &Sym, - const SCEVHandle &Conc) const { - SCEVHandle H = Op->replaceSymbolicValuesWithConcrete(Sym, Conc); + const SCEVHandle &Conc, + ScalarEvolution &SE) const { + SCEVHandle H = Op->replaceSymbolicValuesWithConcrete(Sym, Conc, SE); if (H == Op) return this; - return get(H, Ty); + return SE.getTruncateExpr(H, Ty); } /// getValueRange - Return the tightest constant bounds that this value is @@ -125,15 +122,13 @@ namespace llvm { /// integer value to a larger integer value. /// class SCEVZeroExtendExpr : public SCEV { + friend class ScalarEvolution; + SCEVHandle Op; const Type *Ty; SCEVZeroExtendExpr(const SCEVHandle &op, const Type *ty); virtual ~SCEVZeroExtendExpr(); public: - /// get method - This just gets and returns a new SCEVZeroExtend object - /// - static SCEVHandle get(const SCEVHandle &Op, const Type *Ty); - const SCEVHandle &getOperand() const { return Op; } virtual const Type *getType() const { return Ty; } @@ -150,11 +145,12 @@ namespace llvm { virtual ConstantRange getValueRange() const; SCEVHandle replaceSymbolicValuesWithConcrete(const SCEVHandle &Sym, - const SCEVHandle &Conc) const { - SCEVHandle H = Op->replaceSymbolicValuesWithConcrete(Sym, Conc); + const SCEVHandle &Conc, + ScalarEvolution &SE) const { + SCEVHandle H = Op->replaceSymbolicValuesWithConcrete(Sym, Conc, SE); if (H == Op) return this; - return get(H, Ty); + return SE.getZeroExtendExpr(H, Ty); } virtual void print(std::ostream &OS) const; @@ -172,15 +168,13 @@ namespace llvm { /// integer value to a larger integer value. /// class SCEVSignExtendExpr : public SCEV { + friend class ScalarEvolution; + SCEVHandle Op; const Type *Ty; SCEVSignExtendExpr(const SCEVHandle &op, const Type *ty); virtual ~SCEVSignExtendExpr(); public: - /// get method - This just gets and returns a new SCEVSignExtend object - /// - static SCEVHandle get(const SCEVHandle &Op, const Type *Ty); - const SCEVHandle &getOperand() const { return Op; } virtual const Type *getType() const { return Ty; } @@ -197,11 +191,12 @@ namespace llvm { virtual ConstantRange getValueRange() const; SCEVHandle replaceSymbolicValuesWithConcrete(const SCEVHandle &Sym, - const SCEVHandle &Conc) const { - SCEVHandle H = Op->replaceSymbolicValuesWithConcrete(Sym, Conc); + const SCEVHandle &Conc, + ScalarEvolution &SE) const { + SCEVHandle H = Op->replaceSymbolicValuesWithConcrete(Sym, Conc, SE); if (H == Op) return this; - return get(H, Ty); + return SE.getSignExtendExpr(H, Ty); } virtual void print(std::ostream &OS) const; @@ -220,6 +215,8 @@ namespace llvm { /// operators. /// class SCEVCommutativeExpr : public SCEV { + friend class ScalarEvolution; + std::vector<SCEVHandle> Operands; protected: @@ -264,7 +261,8 @@ namespace llvm { } SCEVHandle replaceSymbolicValuesWithConcrete(const SCEVHandle &Sym, - const SCEVHandle &Conc) const; + const SCEVHandle &Conc, + ScalarEvolution &SE) const; virtual const char *getOperationStr() const = 0; @@ -285,29 +283,13 @@ namespace llvm { /// SCEVAddExpr - This node represents an addition of some number of SCEVs. /// class SCEVAddExpr : public SCEVCommutativeExpr { + friend class ScalarEvolution; + SCEVAddExpr(const std::vector<SCEVHandle> &ops) : SCEVCommutativeExpr(scAddExpr, ops) { } public: - static SCEVHandle get(std::vector<SCEVHandle> &Ops); - - static SCEVHandle get(const SCEVHandle &LHS, const SCEVHandle &RHS) { - std::vector<SCEVHandle> Ops; - Ops.push_back(LHS); - Ops.push_back(RHS); - return get(Ops); - } - - static SCEVHandle get(const SCEVHandle &Op0, const SCEVHandle &Op1, - const SCEVHandle &Op2) { - std::vector<SCEVHandle> Ops; - Ops.push_back(Op0); - Ops.push_back(Op1); - Ops.push_back(Op2); - return get(Ops); - } - virtual const char *getOperationStr() const { return " + "; } /// Methods for support type inquiry through isa, cast, and dyn_cast: @@ -321,20 +303,13 @@ namespace llvm { /// SCEVMulExpr - This node represents multiplication of some number of SCEVs. /// class SCEVMulExpr : public SCEVCommutativeExpr { + friend class ScalarEvolution; + SCEVMulExpr(const std::vector<SCEVHandle> &ops) : SCEVCommutativeExpr(scMulExpr, ops) { } public: - static SCEVHandle get(std::vector<SCEVHandle> &Ops); - - static SCEVHandle get(const SCEVHandle &LHS, const SCEVHandle &RHS) { - std::vector<SCEVHandle> Ops; - Ops.push_back(LHS); - Ops.push_back(RHS); - return get(Ops); - } - virtual const char *getOperationStr() const { return " * "; } /// Methods for support type inquiry through isa, cast, and dyn_cast: @@ -349,16 +324,14 @@ namespace llvm { /// SCEVSDivExpr - This class represents a binary signed division operation. /// class SCEVSDivExpr : public SCEV { + friend class ScalarEvolution; + SCEVHandle LHS, RHS; SCEVSDivExpr(const SCEVHandle &lhs, const SCEVHandle &rhs) : SCEV(scSDivExpr), LHS(lhs), RHS(rhs) {} virtual ~SCEVSDivExpr(); public: - /// get method - This just gets and returns a new SCEVSDiv object. - /// - static SCEVHandle get(const SCEVHandle &LHS, const SCEVHandle &RHS); - const SCEVHandle &getLHS() const { return LHS; } const SCEVHandle &getRHS() const { return RHS; } @@ -372,13 +345,14 @@ namespace llvm { } SCEVHandle replaceSymbolicValuesWithConcrete(const SCEVHandle &Sym, - const SCEVHandle &Conc) const { - SCEVHandle L = LHS->replaceSymbolicValuesWithConcrete(Sym, Conc); - SCEVHandle R = RHS->replaceSymbolicValuesWithConcrete(Sym, Conc); + const SCEVHandle &Conc, + ScalarEvolution &SE) const { + SCEVHandle L = LHS->replaceSymbolicValuesWithConcrete(Sym, Conc, SE); + SCEVHandle R = RHS->replaceSymbolicValuesWithConcrete(Sym, Conc, SE); if (L == LHS && R == RHS) return this; else - return get(L, R); + return SE.getSDivExpr(L, R); } @@ -402,6 +376,8 @@ namespace llvm { /// All operands of an AddRec are required to be loop invariant. /// class SCEVAddRecExpr : public SCEV { + friend class ScalarEvolution; + std::vector<SCEVHandle> Operands; const Loop *L; @@ -413,16 +389,6 @@ namespace llvm { } ~SCEVAddRecExpr(); public: - static SCEVHandle get(const SCEVHandle &Start, const SCEVHandle &Step, - const Loop *); - static SCEVHandle get(std::vector<SCEVHandle> &Operands, - const Loop *); - static SCEVHandle get(const std::vector<SCEVHandle> &Operands, - const Loop *L) { - std::vector<SCEVHandle> NewOp(Operands); - return get(NewOp, L); - } - typedef std::vector<SCEVHandle>::const_iterator op_iterator; op_iterator op_begin() const { return Operands.begin(); } op_iterator op_end() const { return Operands.end(); } @@ -436,10 +402,10 @@ namespace llvm { /// getStepRecurrence - This method constructs and returns the recurrence /// indicating how much this expression steps by. If this is a polynomial /// of degree N, it returns a chrec of degree N-1. - SCEVHandle getStepRecurrence() const { + SCEVHandle getStepRecurrence(ScalarEvolution &SE) const { if (getNumOperands() == 2) return getOperand(1); - return SCEVAddRecExpr::get(std::vector<SCEVHandle>(op_begin()+1,op_end()), - getLoop()); + return SE.getAddRecExpr(std::vector<SCEVHandle>(op_begin()+1,op_end()), + getLoop()); } virtual bool hasComputableLoopEvolution(const Loop *QL) const { @@ -468,7 +434,7 @@ namespace llvm { /// evaluateAtIteration - Return the value of this chain of recurrences at /// the specified iteration number. - SCEVHandle evaluateAtIteration(SCEVHandle It) const; + SCEVHandle evaluateAtIteration(SCEVHandle It, ScalarEvolution &SE) const; /// getNumIterationsInRange - Return the number of iterations of this loop /// that produce values in the specified constant range. Another way of @@ -476,10 +442,12 @@ namespace llvm { /// value is not in the condition, thus computing the exit count. If the /// iteration count can't be computed, an instance of SCEVCouldNotCompute is /// returned. - SCEVHandle getNumIterationsInRange(ConstantRange Range) const; + SCEVHandle getNumIterationsInRange(ConstantRange Range, + ScalarEvolution &SE) const; SCEVHandle replaceSymbolicValuesWithConcrete(const SCEVHandle &Sym, - const SCEVHandle &Conc) const; + const SCEVHandle &Conc, + ScalarEvolution &SE) const; virtual void print(std::ostream &OS) const; void print(std::ostream *OS) const { if (OS) print(*OS); } @@ -497,20 +465,14 @@ namespace llvm { /// value for the analysis. /// class SCEVUnknown : public SCEV { + friend class ScalarEvolution; + Value *V; SCEVUnknown(Value *v) : SCEV(scUnknown), V(v) {} protected: ~SCEVUnknown(); public: - /// get method - For SCEVUnknown, this just gets and returns a new - /// SCEVUnknown. - static SCEVHandle get(Value *V); - - /// getIntegerSCEV - Given an integer or FP type, create a constant for the - /// specified signed integer value and return a SCEV for the constant. - static SCEVHandle getIntegerSCEV(int Val, const Type *Ty); - Value *getValue() const { return V; } virtual bool isLoopInvariant(const Loop *L) const; @@ -519,7 +481,8 @@ namespace llvm { } SCEVHandle replaceSymbolicValuesWithConcrete(const SCEVHandle &Sym, - const SCEVHandle &Conc) const { + const SCEVHandle &Conc, + ScalarEvolution &SE) const { if (&*Sym == this) return Conc; return this; } diff --git a/lib/Analysis/ScalarEvolution.cpp b/lib/Analysis/ScalarEvolution.cpp index 069f6ec714..6c91dca330 100644 --- a/lib/Analysis/ScalarEvolution.cpp +++ b/lib/Analysis/ScalarEvolution.cpp @@ -154,7 +154,8 @@ bool SCEVCouldNotCompute::hasComputableLoopEvolution(const Loop *L) const { SCEVHandle SCEVCouldNotCompute:: replaceSymbolicValuesWithConcrete(const SCEVHandle &Sym, - const SCEVHandle &Conc) const { + const SCEVHandle &Conc, + ScalarEvolution &SE) const { return this; } @@ -177,14 +178,14 @@ SCEVConstant::~SCEVConstant() { SCEVConstants->erase(V); } -SCEVHandle SCEVConstant::get(ConstantInt *V) { +SCEVHandle ScalarEvolution::getConstant(ConstantInt *V) { SCEVConstant *&R = (*SCEVConstants)[V]; if (R == 0) R = new SCEVConstant(V); return R; } -SCEVHandle SCEVConstant::get(const APInt& Val) { - return get(ConstantInt::get(Val)); +SCEVHandle ScalarEvolution::getConstant(const APInt& Val) { + return getConstant(ConstantInt::get(Val)); } ConstantRange SCEVConstant::getValueRange() const { @@ -298,9 +299,11 @@ void SCEVCommutativeExpr::print(std::ostream &OS) const { SCEVHandle SCEVCommutativeExpr:: replaceSymbolicValuesWithConcrete(const SCEVHandle &Sym, - const SCEVHandle &Conc) const { + const SCEVHandle &Conc, + ScalarEvolution &SE) const { for (unsigned i = 0, e = getNumOperands(); i != e; ++i) { - SCEVHandle H = getOperand(i)->replaceSymbolicValuesWithConcrete(Sym, Conc); + SCEVHandle H = + getOperand(i)->replaceSymbolicValuesWithConcrete(Sym, Conc, SE); if (H != getOperand(i)) { std::vector<SCEVHandle> NewOps; NewOps.reserve(getNumOperands()); @@ -309,12 +312,12 @@ replaceSymbolicValuesWithConcrete(const SCEVHandle &Sym, NewOps.push_back(H); for (++i; i != e; ++i) NewOps.push_back(getOperand(i)-> - replaceSymbolicValuesWithConcrete(Sym, Conc)); + replaceSymbolicValuesWithConcrete(Sym, Conc, SE)); if (isa<SCEVAddExpr>(this)) - return SCEVAddExpr::get(NewOps); + return SE.getAddExpr(NewOps); else if (isa<SCEVMulExpr>(this)) - return SCEVMulExpr::get(NewOps); + return SE.getMulExpr(NewOps); else assert(0 && "Unknown commutative expr!"); } @@ -355,9 +358,11 @@ SCEVAddRecExpr::~SCEVAddRecExpr() { SCEVHandle SCEVAddRecExpr:: replaceSymbolicValuesWithConcrete(const SCEVHandle &Sym, - const SCEVHandle &Conc) const { + const SCEVHandle &Conc, + ScalarEvolution &SE) const { for (unsigned i = 0, e = getNumOperands(); i != e; ++i) { - SCEVHandle H = getOperand(i)->replaceSymbolicValuesWithConcrete(Sym, Conc); + SCEVHandle H = + getOperand(i)->replaceSymbolicValuesWithConcrete(Sym, Conc, SE); if (H != getOperand(i)) { std::vector<SCEVHandle> NewOps; NewOps.reserve(getNumOperands()); @@ -366,9 +371,9 @@ replaceSymbolicValuesWithConcrete(const SCEVHandle &Sym, NewOps.push_back(H); for (++i; i != e; ++i) NewOps.push_back(getOperand(i)-> - replaceSymbolicValuesWithConcrete(Sym, Conc)); + replaceSymbolicValuesWithConcrete(Sym, Conc, SE)); - return get(NewOps, L); + return SE.getAddRecExpr(NewOps, L); } } return this; @@ -480,7 +485,7 @@ static void GroupByComplexity(std::vector<SCEVHandle> &Ops) { /// getIntegerSCEV - Given an integer or FP type, create a constant for the /// specified signed integer value and return a SCEV for the constant. -SCEVHandle SCEVUnknown::getIntegerSCEV(int Val, const Type *Ty) { +SCEVHandle ScalarEvolution::getIntegerSCEV(int Val, const Type *Ty) { Constant *C; if (Val == 0) C = Constant::getNullValue(Ty); @@ -489,42 +494,45 @@ SCEVHandle SCEVUnknown::getIntegerSCEV(int Val, const Type *Ty) { APFloat::IEEEdouble, Val)); else C = ConstantInt::get(Ty, Val); - return SCEVUnknown::get(C); + return getUnknown(C); } /// getTruncateOrZeroExtend - Return a SCEV corresponding to a conversion of the /// input value to the specified type. If the type must be extended, it is zero /// extended. -static SCEVHandle getTruncateOrZeroExtend(const SCEVHandle &V, const Type *Ty) { +static SCEVHandle getTruncateOrZeroExtend(const SCEVHandle &V, const Type *Ty, + ScalarEvolution &SE) { const Type *SrcTy = V->getType(); assert(SrcTy->isInteger() && Ty->isInteger() && "Cannot truncate or zero extend with non-integer arguments!"); if (SrcTy->getPrimitiveSizeInBits() == Ty->getPrimitiveSizeInBits()) return V; // No conversion if (SrcTy->getPrimitiveSizeInBits() > Ty->getPrimitiveSizeInBits()) - return SCEVTruncateExpr::get(V, Ty); - return SCEVZeroExtendExpr::get(V, Ty); + return SE.getTruncateExpr(V, Ty); + return SE.getZeroExtendExpr(V, Ty); } /// getNegativeSCEV - Return a SCEV corresponding to -V = -1*V /// -SCEVHandle SCEV::getNegativeSCEV(const SCEVHandle &V) { +SCEVHandle ScalarEvolution::getNegativeSCEV(const SCEVHandle &V) { if (SCEVConstant *VC = dyn_cast<SCEVConstant>(V)) - return SCEVUnknown::get(ConstantExpr::getNeg(VC->getValue())); + return getUnknown(ConstantExpr::getNeg(VC->getValue())); - return SCEVMulExpr::get(V, SCEVUnknown::getIntegerSCEV(-1, V->getType())); + return getMulExpr(V, getIntegerSCEV(-1, V->getType())); } /// getMinusSCEV - Return a SCEV corresponding to LHS - RHS. /// -SCEVHandle SCEV::getMinusSCEV(const SCEVHandle &LHS, const SCEVHandle &RHS) { +SCEVHandle ScalarEvolution::getMinusSCEV(const SCEVHandle &LHS, + const SCEVHandle &RHS) { // X - Y --> X + -Y - return SCEVAddExpr::get(LHS, SCEV::getNegativeSCEV(RHS)); + return getAddExpr(LHS, getNegativeSCEV(RHS)); } /// PartialFact - Compute V!/(V-NumSteps)! -static SCEVHandle PartialFact(SCEVHandle V, unsigned NumSteps) { +static SCEVHandle PartialFact(SCEVHandle V, unsigned NumSteps, + ScalarEvolution &SE) { // Handle this case efficiently, it is common to have constant iteration // counts while computing loop exit values. if (SCEVConstant *SC = dyn_cast<SCEVConstant>(V)) { @@ -532,17 +540,17 @@ static SCEVHandle PartialFact(SCEVHandle V, unsigned NumSteps) { APInt Result(Val.getBitWidth(), 1); for (; NumSteps; --NumSteps) Result *= Val-(NumSteps-1); - return SCEVConstant::get(Result); + return SE.getConstant(Result); } const Type *Ty = V->getType(); if (NumSteps == 0) - return SCEVUnknown::getIntegerSCEV(1, Ty); + return SE.getIntegerSCEV(1, Ty); SCEVHandle Result = V; for (unsigned i = 1; i != NumSteps; ++i) - Result = SCEVMulExpr::get(Result, SCEV::getMinusSCEV(V, - SCEVUnknown::getIntegerSCEV(i, Ty))); + Result = SE.getMulExpr(Result, SE.getMinusSCEV(V, + SE.getIntegerSCEV(i, Ty))); return Result; } @@ -557,16 +565,17 @@ static SCEVHandle PartialFact(SCEVHandle V, unsigned NumSteps) { /// FIXME/VERIFY: I don't trust that this is correct in the face of overflow. /// Is the binomial equation safe using modular arithmetic?? /// -SCEVHandle SCEVAddRecExpr::evaluateAtIteration(SCEVHandle It) const { +SCEVHandle SCEVAddRecExpr::evaluateAtIteration(SCEVHandle It, + ScalarEvolution &SE) const { SCEVHandle Result = getStart(); int Divisor = 1; const Type *Ty = It->getType(); for (unsigned i = 1, e = getNumOperands(); i != e; ++i) { - SCEVHandle BC = PartialFact(It, i); + SCEVHandle BC = PartialFact(It, i, SE); Divisor *= i; - SCEVHandle Val = SCEVSDivExpr::get(SCEVMulExpr::get(BC, getOperand(i)), - SCEVUnknown::getIntegerSCEV(Divisor,Ty)); - Result = SCEVAddExpr::get(Result, Val); + SCEVHandle Val = SE.getSDivExpr(SE.getMulExpr(BC, getOperand(i)), + SE.getIntegerSCEV(Divisor,Ty)); + Result = SE.getAddExpr(Result, Val); } return Result; } @@ -576,9 +585,9 @@ SCEVHandle SCEVAddRecExpr::evaluateAtIteration(SCEVHandle It) const { // SCEV Expression folder implementations //===----------------------------------------------------------------------===// -SCEVHandle SCEVTruncateExpr::get(const SCEVHandle &Op, const Type *Ty) { +SCEVHandle ScalarEvolution::getTruncateExpr(const SCEVHandle &Op, const Type *Ty) { if (SCEVConstant *SC = dyn_cast<SCEVConstant>(Op)) - return SCEVUnknown::get( + return getUnknown( ConstantExpr::getTrunc(SC->getValue(), Ty)); // If the input value is a chrec scev made out of constants, truncate @@ -588,11 +597,11 @@ SCEVHandle SCEVTruncateExpr::get(const SCEVHandle &Op, const Type *Ty) { for (unsigned i = 0, e = AddRec->getNumOperands(); i != e; ++i) // FIXME: This should allow truncation of other expression types! if (isa<SCEVConstant>(AddRec->getOperand(i))) - Operands.push_back(get(AddRec->getOperand(i), Ty)); + Operands.push_back(getTruncateExpr(AddRec->getOperand(i), Ty)); else break; if (Operands.size() == AddRec->getNumOperands()) - return SCEVAddRecExpr::get(Operands, AddRec->getLoop()); + return getAddRecExpr(Operands, AddRec->getLoop()); } SCEVTruncateExpr *&Result = (*SCEVTruncates)[std::make_pair(Op, Ty)]; @@ -600,9 +609,9 @@ SCEVHandle SCEVTruncateExpr::get(const SCEVHandle &Op, const Type *Ty) { return Result; } -SCEVHandle SCEVZeroExtendExpr::get(const SCEVHandle &Op, const Type *Ty) { +SCEVHandle ScalarEvolution::getZeroExtendExpr(const SCEVHandle &Op, const Type *Ty) { if (SCEVConstant *SC = dyn_cast<SCEVConstant>(Op)) - return SCEVUnknown::get( + return getUnknown( ConstantExpr::getZExt(SC->getValue(), Ty)); // FIXME: If the input value is a chrec scev, and we can prove that the value @@ -615,9 +624,9 @@ SCEVHandle SCEVZeroExtendExpr::get(const SCEVHandle &Op, const Type *Ty) { return Result; } -SCEVHandle SCEVSignExtendExpr::get(const SCEVHandle &Op, const Type *Ty) { +SCEVHandle ScalarEvolution::getSignExtendExpr(const SCEVHandle &Op, const Type *Ty) { if (SCEVConstant *SC = dyn_cast<SCEVConstant>(Op)) - return SCEVUnknown::get( + return getUnknown( ConstantExpr::getSExt(SC->getValue(), Ty)); // FIXME: If the input value is a chrec scev, and we can prove that the value @@ -631,7 +640,7 @@ SCEVHandle SCEVSignExtendExpr::get(const SCEVHandle &Op, const Type *Ty) { } // get - Get a canonical add expression, or something simpler if possible. -SCEVHandle SCEVAddExpr::get(std::vector<SCEVHandle> &Ops) { +SCEVHandle ScalarEvolution::getAddExpr(std::vector<SCEVHandle> &Ops) { assert(!Ops.empty() && "Cannot get empty add!"); if (Ops.size() == 1) return Ops[0]; @@ -648,7 +657,7 @@ SCEVHandle SCEVAddExpr::get(std::vector<SCEVHandle> &Ops) { Constant *Fold = ConstantInt::get(LHSC->getValue()->getValue() + RHSC->getValue()->getValue()); if (ConstantInt *CI = dyn_cast<ConstantInt>(Fold)) { - Ops[0] = SCEVConstant::get(CI); + Ops[0] = getConstant(CI); Ops.erase(Ops.begin()+1); // Erase the folded element if (Ops.size() == 1) return Ops[0]; LHSC = cast<SCEVConstant>(Ops[0]); @@ -677,13 +686,13 @@ SCEVHandle SCEVAddExpr::get(std::vector<SCEVHandle> &Ops) { if (Ops[i] == Ops[i+1]) { // X + Y + Y --> X + Y*2 // Found a match, merge the two values into a multiply, and add any // remaining values to the result. - SCEVHandle Two = SCEVUnknown::getIntegerSCEV(2, Ty); - SCEVHandle Mul = SCEVMulExpr::get(Ops[i], Two); + SCEVHandle Two = getIntegerSCEV(2, Ty); + SCEVHandle Mul = getMulExpr(Ops[i], Two); if (Ops.size() == 2) return Mul; Ops.erase(Ops.begin()+i, Ops.begin()+i+2); Ops.push_back(Mul); - return SCEVAddExpr::get(Ops); + return getAddExpr(Ops); } // Now we know the first non-constant operand. Skip past any cast SCEVs. @@ -705,7 +714,7 @@ SCEVHandle SCEVAddExpr::get(std::vector<SCEVHandle> &Ops) { // and they are not necessarily sorted. Recurse to resort and resimplify // any operands we just aquired. if (DeletedAdd) - return get(Ops); + return getAddExpr(Ops); } // Skip over the add expression until we get to a multiply. @@ -728,11 +737,11 @@ SCEVHandle SCEVAddExpr::get(std::vector<SCEVHandle> &Ops) { // Y*Z term. std::vector<SCEVHandle> MulOps(Mul->op_begin(), Mul->op_end()); MulOps.erase(MulOps.begin()+MulOp); - InnerMul = SCEVMulExpr::get(MulOps); + InnerMul = getMulExpr(MulOps); } - SCEVHandle One = SCEVUnknown::getIntegerSCEV(1, Ty); - SCEVHandle AddOne = SCEVAddExpr::get(InnerMul, One); - SCEVHandle OuterMul = SCEVMulExpr::get(AddOne, Ops[AddOp]); + SCEVHandle One = getIntegerSCEV(1, Ty); + SCEVHandle AddOne = getAddExpr(InnerMul, One); + SCEVHandle OuterMul = getMulExpr(AddOne, Ops[AddOp]); if (Ops.size() == 2) return OuterMul; if (AddOp < Idx) { Ops.erase(Ops.begin()+AddOp); @@ -742,7 +751,7 @@ SCEVHandle SCEVAddExpr::get(std::vector<SCEVHandle> &Ops) { Ops.erase(Ops.begin()+AddOp-1); } Ops.push_back(OuterMul); - return SCEVAddExpr::get(Ops); + return getAddExpr(Ops); } // Check this multiply against other multiplies being added together. @@ -760,22 +769,22 @@ SCEVHandle SCEVAddExpr::get(std::vector<SCEVHandle> &Ops) { if (Mul->getNumOperands() != 2) { std::vector<SCEVHandle> MulOps(Mul->op_begin(), Mul->op_end()); MulOps.erase(MulOps.begin()+MulOp); - InnerMul1 = SCEVMulExpr::get(MulOps); + InnerMul1 = getMulExpr(MulOps); } SCEVHandle InnerMul2 = OtherMul->getOperand(OMulOp == 0); if (OtherMul->getNumOperands() != 2) { std::vector<SCEVHandle> MulOps(OtherMul->op_begin(), OtherMul->op_end()); MulOps.erase(MulOps.begin()+OMulOp); - InnerMul2 = SCEVMulExpr::get(MulOps); + InnerMul2 = getMulExpr(MulOps); } - SCEVHandle InnerMulSum = SCEVAddExpr::get(InnerMul1,InnerMul2); - SCEVHandle OuterMul = SCEVMulExpr::get(MulOpSCEV, InnerMulSum); + SCEVHandle InnerMulSum = getAddExpr(InnerMul1,InnerMul2); + SCEVHandle OuterMul = getMulExpr(MulOpSCEV, InnerMulSum); if (Ops.size() == 2) return OuterMul; Ops.erase(Ops.begin()+Idx); Ops.erase(Ops.begin()+OtherMulIdx-1); Ops.push_back(OuterMul); - return SCEVAddExpr::get(Ops); + return getAddExpr(Ops); } } } @@ -806,9 +815,9 @@ SCEVHandle SCEVAddExpr::get(std::vector<SCEVHandle> &Ops) { LIOps.push_back(AddRec->getStart()); std::vector<SCEVHandle> AddRecOps(AddRec->op_begin(), AddRec->op_end()); - AddRecOps[0] = SCEVAddExpr::get(LIOps); + AddRecOps[0] = getAddExpr(LIOps); - SCEVHandle NewRec = SCEVAddRecExpr::get(AddRecOps, AddRec->getLoop()); + SCEVHandle NewRec = getAddRecExpr(AddRecOps, AddRec->getLoop()); // If all of the other operands were loop invariant, we are done. if (Ops.size() == 1) return NewRec; @@ -818,7 +827,7 @@ SCEVHandle SCEVAddExpr::get(std::vector<SCEVHandle> &Ops) { Ops[i] = NewRec; break; } - return SCEVAddExpr::get(Ops); + return getAddExpr(Ops); } // Okay, if there weren't any loop invariants to be folded, check to see if @@ -837,16 +846,16 @@ SCEVHandle SCEVAddExpr::get(std::vector<SCEVHandle> &Ops) { OtherAddRec->op_end()); break; } - NewOps[i] = SCEVAddExpr::get(NewOps[i], OtherAddRec->getOperand(i)); + NewOps[i] = getAddExpr(NewOps[i], OtherAddRec->getOperand(i)); } - SCEVHandle NewAddRec = SCEVAddRecExpr::get(NewOps, AddRec->getLoop()); + SCEVHandle NewAddRec = getAddRecExpr(NewOps, AddRec->getLoop()); if (Ops.size() == 2) return NewAddRec; Ops.erase(Ops.begin()+Idx); Ops.erase(Ops.begin()+OtherIdx-1); Ops.push_back(NewAddRec); - return SCEVAddExpr::get(Ops); + return getAddExpr(Ops); } |