diff options
Diffstat (limited to 'llvm/lib/Analysis/ScalarEvolution.cpp')
| -rw-r--r-- | llvm/lib/Analysis/ScalarEvolution.cpp | 695 |
1 files changed, 142 insertions, 553 deletions
diff --git a/llvm/lib/Analysis/ScalarEvolution.cpp b/llvm/lib/Analysis/ScalarEvolution.cpp index 8a2a8dceefb..0d880ed74a8 100644 --- a/llvm/lib/Analysis/ScalarEvolution.cpp +++ b/llvm/lib/Analysis/ScalarEvolution.cpp @@ -63,7 +63,7 @@ // //===----------------------------------------------------------------------===// -#include "llvm/Analysis/ScalarEvolution.h" +#include "llvm/Analysis/ScalarEvolutionExpressions.h" #include "llvm/Constants.h" #include "llvm/DerivedTypes.h" #include "llvm/Instructions.h" @@ -101,13 +101,6 @@ namespace { // Implementation of the SCEV class. // namespace { - enum SCEVTypes { - // These should be ordered in terms of increasing complexity to make the - // folders simpler. - scConstant, scTruncate, scZeroExtend, scAddExpr, scMulExpr, scUDivExpr, - scAddRecExpr, scUnknown, scCouldNotCompute - }; - /// SCEVComplexityCompare - Return true if the complexity of the LHS is less /// than the complexity of the RHS. If the SCEVs have identical complexity, /// order them by their addresses. This comparator is used to canonicalize @@ -172,593 +165,181 @@ bool SCEVCouldNotCompute::classof(const SCEV *S) { } -//===----------------------------------------------------------------------===// -// SCEVConstant - This class represents a constant integer value. -// -namespace { - class SCEVConstant; - // SCEVConstants - Only allow the creation of one SCEVConstant for any - // particular value. Don't use a SCEVHandle here, or else the object will - // never be deleted! - std::map<ConstantInt*, SCEVConstant*> SCEVConstants; - - class SCEVConstant : public SCEV { - ConstantInt *V; - SCEVConstant(ConstantInt *v) : SCEV(scConstant), V(v) {} - - virtual ~SCEVConstant() { - SCEVConstants.erase(V); - } - public: - /// get method - This just gets and returns a new SCEVConstant object. - /// - static SCEVHandle get(ConstantInt *V) { - // Make sure that SCEVConstant instances are all unsigned. - if (V->getType()->isSigned()) { - const Type *NewTy = V->getType()->getUnsignedVersion(); - V = cast<ConstantUInt>(ConstantExpr::getCast(V, NewTy)); - } - - SCEVConstant *&R = SCEVConstants[V]; - if (R == 0) R = new SCEVConstant(V); - return R; - } - - ConstantInt *getValue() const { return V; } - - /// getValueRange - Return the tightest constant bounds that this value is - /// known to have. This method is only valid on integer SCEV objects. - virtual ConstantRange getValueRange() const { - return ConstantRange(V); - } - - virtual bool isLoopInvariant(const Loop *L) const { - return true; - } - - virtual bool hasComputableLoopEvolution(const Loop *L) const { - return false; // Not loop variant - } - - virtual const Type *getType() const { return V->getType(); } - - Value *expandCodeFor(ScalarEvolutionRewriter &SER, - Instruction *InsertPt) { - return getValue(); - } - - virtual void print(std::ostream &OS) const { - WriteAsOperand(OS, V, false); - } +// SCEVConstants - Only allow the creation of one SCEVConstant for any +// particular value. Don't use a SCEVHandle here, or else the object will +// never be deleted! +static std::map<ConstantInt*, SCEVConstant*> SCEVConstants; + - /// Methods for support type inquiry through isa, cast, and dyn_cast: - static inline bool classof(const SCEVConstant *S) { return true; } - static inline bool classof(const SCEV *S) { - return S->getSCEVType() == scConstant; - } - }; +SCEVConstant::~SCEVConstant() { + SCEVConstants.erase(V); } - -//===----------------------------------------------------------------------===// -// SCEVTruncateExpr - This class represents a truncation of an integer value to -// a smaller integer value. -// -namespace { - class SCEVTruncateExpr; - // SCEVTruncates - Only allow the creation of one SCEVTruncateExpr for any - // particular input. Don't use a SCEVHandle here, or else the object will - // never be deleted! - std::map<std::pair<SCEV*, const Type*>, SCEVTruncateExpr*> SCEVTruncates; - - class SCEVTruncateExpr : public SCEV { - SCEVHandle Op; - const Type *Ty; - SCEVTruncateExpr(const SCEVHandle &op, const Type *ty) - : SCEV(scTruncate), Op(op), Ty(ty) { - assert(Op->getType()->isInteger() && Ty->isInteger() && - Ty->isUnsigned() && - "Cannot truncate non-integer value!"); - assert(Op->getType()->getPrimitiveSize() > Ty->getPrimitiveSize() && - "This is not a truncating conversion!"); - } - - virtual ~SCEVTruncateExpr() { - SCEVTruncates.erase(std::make_pair(Op, Ty)); - } - 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; } - - virtual bool isLoopInvariant(const Loop *L) const { - return Op->isLoopInvariant(L); - } - - virtual bool hasComputableLoopEvolution(const Loop *L) const { - return Op->hasComputableLoopEvolution(L); - } - - /// getValueRange - Return the tightest constant bounds that this value is - /// known to have. This method is only valid on integer SCEV objects. - virtual ConstantRange getValueRange() const { - return getOperand()->getValueRange().truncate(getType()); - } - - Value *expandCodeFor(ScalarEvolutionRewriter &SER, - Instruction *InsertPt); - - virtual void print(std::ostream &OS) const { - OS << "(truncate " << *Op << " to " << *Ty << ")"; - } - - /// Methods for support type inquiry through isa, cast, and dyn_cast: - static inline bool classof(const SCEVTruncateExpr *S) { return true; } - static inline bool classof(const SCEV *S) { - return S->getSCEVType() == scTruncate; - } - }; +SCEVHandle SCEVConstant::get(ConstantInt *V) { + // Make sure that SCEVConstant instances are all unsigned. + if (V->getType()->isSigned()) { + const Type *NewTy = V->getType()->getUnsignedVersion(); + V = cast<ConstantUInt>(ConstantExpr::getCast(V, NewTy)); + } + + SCEVConstant *&R = SCEVConstants[V]; + if (R == 0) R = new SCEVConstant(V); + return R; } - -//===----------------------------------------------------------------------===// -// SCEVZeroExtendExpr - This class represents a zero extension of a small -// integer value to a larger integer value. -// -namespace { - class SCEVZeroExtendExpr; - // SCEVZeroExtends - Only allow the creation of one SCEVZeroExtendExpr for any - // particular input. Don't use a SCEVHandle here, or else the object will - // never be deleted! - std::map<std::pair<SCEV*, const Type*>, SCEVZeroExtendExpr*> SCEVZeroExtends; - - class SCEVZeroExtendExpr : public SCEV { - SCEVHandle Op; - const Type *Ty; - SCEVZeroExtendExpr(const SCEVHandle &op, const Type *ty) - : SCEV(scTruncate), Op(Op), Ty(ty) { - assert(Op->getType()->isInteger() && Ty->isInteger() && - Ty->isUnsigned() && - "Cannot zero extend non-integer value!"); - assert(Op->getType()->getPrimitiveSize() < Ty->getPrimitiveSize() && - "This is not an extending conversion!"); - } - - virtual ~SCEVZeroExtendExpr() { - SCEVZeroExtends.erase(std::make_pair(Op, Ty)); - } - 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; } - - virtual bool isLoopInvariant(const Loop *L) const { - return Op->isLoopInvariant(L); - } - - virtual bool hasComputableLoopEvolution(const Loop *L) const { - return Op->hasComputableLoopEvolution(L); - } - - /// getValueRange - Return the tightest constant bounds that this value is - /// known to have. This method is only valid on integer SCEV objects. - virtual ConstantRange getValueRange() const { - return getOperand()->getValueRange().zeroExtend(getType()); - } - - Value *expandCodeFor(ScalarEvolutionRewriter &SER, - Instruction *InsertPt); - - virtual void print(std::ostream &OS) const { - OS << "(zeroextend " << *Op << " to " << *Ty << ")"; - } - - /// Methods for support type inquiry through isa, cast, and dyn_cast: - static inline bool classof(const SCEVZeroExtendExpr *S) { return true; } - static inline bool classof(const SCEV *S) { - return S->getSCEVType() == scZeroExtend; - } - }; +ConstantRange SCEVConstant::getValueRange() const { + return ConstantRange(V); } +const Type *SCEVConstant::getType() const { return V->getType(); } -//===----------------------------------------------------------------------===// -// SCEVCommutativeExpr - This node is the base class for n'ary commutative -// operators. - -namespace { - class SCEVCommutativeExpr; - // SCEVCommExprs - Only allow the creation of one SCEVCommutativeExpr for any - // particular input. Don't use a SCEVHandle here, or else the object will - // never be deleted! - std::map<std::pair<unsigned, std::vector<SCEV*> >, - SCEVCommutativeExpr*> SCEVCommExprs; - - class SCEVCommutativeExpr : public SCEV { - std::vector<SCEVHandle> Operands; - - protected: - SCEVCommutativeExpr(enum SCEVTypes T, const std::vector<SCEVHandle> &ops) - : SCEV(T) { - Operands.reserve(ops.size()); - Operands.insert(Operands.end(), ops.begin(), ops.end()); - } - - ~SCEVCommutativeExpr() { - SCEVCommExprs.erase(std::make_pair(getSCEVType(), - std::vector<SCEV*>(Operands.begin(), - Operands.end()))); - } - - public: - unsigned getNumOperands() const { return Operands.size(); } - const SCEVHandle &getOperand(unsigned i) const { - assert(i < Operands.size() && "Operand index out of range!"); - return Operands[i]; - } - - const std::vector<SCEVHandle> &getOperands() const { return Operands; } - typedef std::vector<SCEVHandle>::const_iterator op_iterator; - op_iterator op_begin() const { return Operands.begin(); } - op_iterator op_end() const { return Operands.end(); } - - - virtual bool isLoopInvariant(const Loop *L) const { - for (unsigned i = 0, e = getNumOperands(); i != e; ++i) - if (!getOperand(i)->isLoopInvariant(L)) return false; - return true; - } - - virtual bool hasComputableLoopEvolution(const Loop *L) const { - for (unsigned i = 0, e = getNumOperands(); i != e; ++i) - if (getOperand(i)->hasComputableLoopEvolution(L)) return true; - return false; - } - - virtual const Type *getType() const { return getOperand(0)->getType(); } - - virtual const char *getOperationStr() const = 0; - - virtual void print(std::ostream &OS) const { - assert(Operands.size() > 1 && "This plus expr shouldn't exist!"); - const char *OpStr = getOperationStr(); - OS << "(" << *Operands[0]; - for (unsigned i = 1, e = Operands.size(); i != e; ++i) - OS << OpStr << *Operands[i]; - OS << ")"; - } - - /// Methods for support type inquiry through isa, cast, and dyn_cast: - static inline bool classof(const SCEVCommutativeExpr *S) { return true; } - static inline bool classof(const SCEV *S) { - return S->getSCEVType() == scAddExpr || - S->getSCEVType() == scMulExpr; - } - }; +void SCEVConstant::print(std::ostream &OS) const { + WriteAsOperand(OS, V, false); } -//===----------------------------------------------------------------------===// -// SCEVAddExpr - This node represents an addition of some number of SCEV's. -// -namespace { - class SCEVAddExpr : public SCEVCommutativeExpr { - SCEVAddExpr(const std::vector<SCEVHandle> &ops) - : SCEVCommutativeExpr(scAddExpr, ops) { - } - - public: - static SCEVHandle get(std::vector<SCEVHandle> &Ops); +// SCEVTruncates - Only allow the creation of one SCEVTruncateExpr for any +// particular input. Don't use a SCEVHandle here, or else the object will +// never be deleted! +static std::map<std::pair<SCEV*, const Type*>, SCEVTruncateExpr*> SCEVTruncates; - 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 " + "; } - - Value *expandCodeFor(ScalarEvolutionRewriter &SER, - Instruction *InsertPt); - - /// Methods for support type inquiry through isa, cast, and dyn_cast: - static inline bool classof(const SCEVAddExpr *S) { return true; } - static inline bool classof(const SCEV *S) { - return S->getSCEVType() == scAddExpr; - } - }; +SCEVTruncateExpr::SCEVTruncateExpr(const SCEVHandle &op, const Type *ty) + : SCEV(scTruncate), Op(op), Ty(ty) { + assert(Op->getType()->isInteger() && Ty->isInteger() && + Ty->isUnsigned() && + "Cannot truncate non-integer value!"); + assert(Op->getType()->getPrimitiveSize() > Ty->getPrimitiveSize() && + "This is not a truncating conversion!"); } -//===----------------------------------------------------------------------===// -// SCEVMulExpr - This node represents multiplication of some number of SCEV's. -// -namespace { - class SCEVMulExpr : public SCEVCommutativeExpr { - 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 " * "; } - - Value *expandCodeFor(ScalarEvolutionRewriter &SER, - Instruction *InsertPt); - - /// Methods for support type inquiry through isa, cast, and dyn_cast: - static inline bool classof(const SCEVMulExpr *S) { return true; } - static inline bool classof(const SCEV *S) { - return S->getSCEVType() == scMulExpr; - } - }; +SCEVTruncateExpr::~SCEVTruncateExpr() { + SCEVTruncates.erase(std::make_pair(Op, Ty)); } - -//===----------------------------------------------------------------------===// -// SCEVUDivExpr - This class represents a binary unsigned division operation. -// -namespace { - class SCEVUDivExpr; - // 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! - std::map<std::pair<SCEV*, SCEV*>, SCEVUDivExpr*> SCEVUDivs; - - class SCEVUDivExpr : public SCEV { - SCEVHandle LHS, RHS; - SCEVUDivExpr(const SCEVHandle &lhs, const SCEVHandle &rhs) - : SCEV(scUDivExpr), LHS(lhs), RHS(rhs) {} - - virtual ~SCEVUDivExpr() { - SCEVUDivs.erase(std::make_pair(LHS, RHS)); - } - public: - /// get method - This just gets and returns a new SCEVUDiv object. - /// - static SCEVHandle get(const SCEVHandle &LHS, const SCEVHandle &RHS); - - const SCEVHandle &getLHS() const { return LHS; } - const SCEVHandle &getRHS() const { return RHS; } - - virtual bool isLoopInvariant(const Loop *L) const { - return LHS->isLoopInvariant(L) && RHS->isLoopInvariant(L); - } - - virtual bool hasComputableLoopEvolution(const Loop *L) const { - return LHS->hasComputableLoopEvolution(L) && - RHS->hasComputableLoopEvolution(L); - } - - virtual const Type *getType() const { - const Type *Ty = LHS->getType(); - if (Ty->isSigned()) Ty = Ty->getUnsignedVersion(); - return Ty; - } - - Value *expandCodeFor(ScalarEvolutionRewriter &SER, - Instruction *InsertPt); - - virtual void print(std::ostream &OS) const { - OS << "(" << *LHS << " /u " << *RHS << ")"; - } - - /// Methods for support type inquiry through isa, cast, and dyn_cast: - static inline bool classof(const SCEVUDivExpr *S) { return true; } - static inline bool classof(const SCEV *S) { - return S->getSCEVType() == scUDivExpr; - } - }; +ConstantRange SCEVTruncateExpr::getValueRange() const { + return getOperand()->getValueRange().truncate(getType()); } +void SCEVTruncateExpr::print(std::ostream &OS) const { + OS << "(truncate " << *Op << " to " << *Ty << ")"; +} -//===----------------------------------------------------------------------===// - -// SCEVAddRecExpr - This node represents a polynomial recurrence on the trip -// count of the specified loop. -// -// All operands of an AddRec are required to be loop invariant. -// -namespace { - class SCEVAddRecExpr; - // 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! - std::map<std::pair<const Loop *, std::vector<SCEV*> >, - SCEVAddRecExpr*> SCEVAddRecExprs; - - class SCEVAddRecExpr : public SCEV { - std::vector<SCEVHandle> Operands; - const Loop *L; - - SCEVAddRecExpr(const std::vector<SCEVHandle> &ops, const Loop *l) - : SCEV(scAddRecExpr), Operands(ops), L(l) { - for (unsigned i = 0, e = Operands.size(); i != e; ++i) - assert(Operands[i]->isLoopInvariant(l) && - "Operands of AddRec must be loop-invariant!"); - } - ~SCEVAddRecExpr() { - SCEVAddRecExprs.erase(std::make_pair(L, - std::vector<SCEV*>(Operands.begin(), - Operands.end()))); - } - 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(); } - - unsigned getNumOperands() const { return Operands.size(); } - const SCEVHandle &getOperand(unsigned i) const { return Operands[i]; } - const SCEVHandle &getStart() const { return Operands[0]; } - const Loop *getLoop() const { return L; } - +// SCEVZeroExtends - Only allow the creation of one SCEVZeroExtendExpr for any +// particular input. Don't use a SCEVHandle here, or else the object will never +// be deleted! +static std::map<std::pair<SCEV*, const Type*>, + SCEVZeroExtendExpr*> SCEVZeroExtends; - /// 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 { - if (getNumOperands() == 2) return getOperand(1); - return SCEVAddRecExpr::get(std::vector<SCEVHandle>(op_begin()+1,op_end()), - getLoop()); - } +SCEVZeroExtendExpr::SCEVZeroExtendExpr(const SCEVHandle &op, const Type *ty) + : SCEV(scTruncate), Op(Op), Ty(ty) { + assert(Op->getType()->isInteger() && Ty->isInteger() && + Ty->isUnsigned() && + "Cannot zero extend non-integer value!"); + assert(Op->getType()->getPrimitiveSize() < Ty->getPrimitiveSize() && + "This is not an extending conversion!"); +} - virtual bool hasComputableLoopEvolution(const Loop *QL) const { - if (L == QL) return true; - /// FIXME: What if the start or step value a recurrence for the specified - /// loop? - return false; - } +SCEVZeroExtendExpr::~SCEVZeroExtendExpr() { + SCEVZeroExtends.erase(std::make_pair(Op, Ty)); +} +ConstantRange SCEVZeroExtendExpr::getValueRange() const { + return getOperand()->getValueRange().zeroExtend(getType()); +} - virtual bool isLoopInvariant(const Loop *QueryLoop) const { - // This recurrence is invariant w.r.t to QueryLoop iff QueryLoop doesn't - // contain L. - return !QueryLoop->contains(L->getHeader()); - } +void SCEVZeroExtendExpr::print(std::ostream &OS) const { + OS << "(zeroextend " << *Op << " to " << *Ty << ")"; +} - virtual const Type *getType() const { return Operands[0]->getType(); } +// SCEVCommExprs - Only allow the creation of one SCEVCommutativeExpr for any +// particular input. Don't use a SCEVHandle here, or else the object will never +// be deleted! +static std::map<std::pair<unsigned, std::vector<SCEV*> >, + SCEVCommutativeExpr*> SCEVCommExprs; - Value *expandCodeFor(ScalarEvolutionRewriter &SER, - Instruction *InsertPt); +SCEVCommutativeExpr::~SCEVCommutativeExpr() { + SCEVCommExprs.erase(std::make_pair(getSCEVType(), + std::vector<SCEV*>(Operands.begin(), + Operands.end()))); +} +void SCEVCommutativeExpr::print(std::ostream &OS) const { + assert(Operands.size() > 1 && "This plus expr shouldn't exist!"); + const char *OpStr = getOperationStr(); + OS << "(" << *Operands[0]; + for (unsigned i = 1, e = Operands.size(); i != e; ++i) + OS << OpStr << *Operands[i]; + OS << ")"; +} - /// isAffine - Return true if this is an affine AddRec (i.e., it represents - /// an expressions A+B*x where A and B are loop invariant values. - bool isAffine() const { - // We know that the start value is invariant. This expression is thus - // affine iff the step is also invariant. - return getNumOperands() == 2; - } +// 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 std::map<std::pair<SCEV*, SCEV*>, SCEVUDivExpr*> SCEVUDivs; - /// isQuadratic - Return true if this is an quadratic AddRec (i.e., it - /// represents an expressions A+B*x+C*x^2 where A, B and C are loop - /// invariant values. This corresponds to an addrec of the form {L,+,M,+,N} - bool isQuadratic() const { - return getNumOperands() == 3; - } +SCEVUDivExpr::~SCEVUDivExpr() { + SCEVUDivs.erase(std::make_pair(LHS, RHS)); +} - /// evaluateAtIteration - Return the value of this chain of recurrences at - /// the specified iteration number. - SCEVHandle evaluateAtIteration(SCEVHandle It) const; +void SCEVUDivExpr::print(std::ostream &OS) const { + OS << "(" << *LHS << " /u " << *RHS << ")"; +} - /// getNumIterationsInRange - Return the number of iterations of this loop - /// that produce values in the specified constant range. Another way of - /// looking at this is that it returns the first iteration number where the - /// 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; +const Type *SCEVUDivExpr::getType() const { + const Type *Ty = LHS->getType(); + if (Ty->isSigned()) Ty = Ty->getUnsignedVersion(); + return Ty; +} +// 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! +static std::map<std::pair<const Loop *, std::vector<SCEV*> >, + SCEVAddRecExpr*> SCEVAddRecExprs; - virtual void print(std::ostream &OS) const { - OS << "{" << *Operands[0]; - for (unsigned i = 1, e = Operands.size(); i != e; ++i) - OS << ",+," << *Operands[i]; - OS << "}<" << L->getHeader()->getName() + ">"; - } +SCEVAddRecExpr::~SCEVAddRecExpr() { + SCEVAddRecExprs.erase(std::make_pair(L, + std::vector<SCEV*>(Operands.begin(), + Operands.end()))); +} - /// Methods for support type inquiry through isa, cast, and dyn_cast: - static inline bool classof(const SCEVAddRecExpr *S) { return true; } - static inline bool classof(const SCEV *S) { - return S->getSCEVType() == scAddRecExpr; - } - }; +bool SCEVAddRecExpr::isLoopInvariant(const Loop *QueryLoop) const { + // This recurrence is invariant w.r.t to QueryLoop iff QueryLoop doesn't + // contain L. + return !QueryLoop->contains(L->getHeader()); } -//===----------------------------------------------------------------------===// -// SCEVUnknown - This means that we are dealing with an entirely unknown SCEV -// value, and only represent it as it's LLVM Value. This is the "bottom" value -// for the analysis. -// -namespace { - class SCEVUnknown; - // SCEVUnknowns - Only allow the creation of one SCEVUnknown for any - // particular value. Don't use a SCEVHandle here, or else the object will - // never be deleted! - std::map<Value*, SCEVUnknown*> SCEVUnknowns; - - class SCEVUnknown : public SCEV { - Value *V; - SCEVUnknown(Value *v) : SCEV(scUnknown), V(v) {} - - protected: - ~SCEVUnknown() { SCEVUnknowns.erase(V); } - public: - /// get method - For SCEVUnknown, this just gets and returns a new - /// SCEVUnknown. - static SCEVHandle get(Value *V) { - if (ConstantInt *CI = dyn_cast<ConstantInt>(V)) - return SCEVConstant::get(CI); - SCEVUnknown *&Result = SCEVUnknowns[V]; - if (Result == 0) Result = new SCEVUnknown(V); - return Result; - } +void SCEVAddRecExpr::print(std::ostream &OS) const { + OS << "{" << *Operands[0]; + for (unsigned i = 1, e = Operands.size(); i != e; ++i) + OS << ",+," << *Operands[i]; + OS << "}<" << L->getHeader()->getName() + ">"; +} - Value *getValue() const { return V; } +// SCEVUnknowns - Only allow the creation of one SCEVUnknown for any particular +// value. Don't use a SCEVHandle here, or else the object will never be +// deleted! +static std::map<Value*, SCEVUnknown*> SCEVUnknowns; - Value *expandCodeFor(ScalarEvolutionRewriter &SER, - Instruction *InsertPt) { - return V; - } +SCEVUnknown::~SCEVUnknown() { SCEVUnknowns.erase(V); } - virtual bool isLoopInvariant(const Loop *L) const { - // All non-instruction values are loop invariant. All instructions are - // loop invariant if they are not contained in the specified loop. - if (Instruction *I = dyn_cast<Instruction>(V)) - return !L->contains(I->getParent()); - return true; - } +bool SCEVUnknown::isLoopInvariant(const Loop *L) const { + // All non-instruction values are loop invariant. All instructions are loop + // invariant if they are not contained in the specified loop. + if (Instruction *I = dyn_cast<Instruction>(V)) + return !L->contains(I->getParent()); + return true; +} - virtual bool hasComputableLoopEvolution(const Loop *QL) const { - return false; // not computable - } +const Type *SCEVUnknown::getType() const { + return V->getType(); +} - virtual const Type *getType() const { return V->getType(); } +void SCEVUnknown::print(std::ostream &OS) const { + WriteAsOperand(OS, V, false); +} - virtual void print(std::ostream &OS) const { - WriteAsOperand(OS, V, false); - } - /// Methods for support type inquiry through isa, cast, and dyn_cast: - static inline bool classof(const SCEVUnknown *S) { return true; } - static inline bool classof(const SCEV *S) { - return S->getSCEVType() == scUnknown; - } - }; -} //===----------------------------------------------------------------------===// // Simple SCEV method implementations @@ -1375,6 +956,14 @@ SCEVHandle SCEVAddRecExpr::get(std::vector<SCEVHandle> &Operands, return Result; } +SCEVHandle SCEVUnknown::get(Value *V) { + if (ConstantInt *CI = dyn_cast<ConstantInt>(V)) + return SCEVConstant::get(CI); + SCEVUnknown *&Result = SCEVUnknowns[V]; + if (Result == 0) Result = new SCEVUnknown(V); + return Result; +} + //===----------------------------------------------------------------------===// // Non-trivial closed-form SCEV Expanders |
