LLVM API Documentation

ScalarEvolutionExpressions.h

Go to the documentation of this file.
00001 //===- llvm/Analysis/ScalarEvolutionExpressions.h - SCEV Exprs --*- C++ -*-===//
00002 //
00003 //                     The LLVM Compiler Infrastructure
00004 //
00005 // This file was developed by the LLVM research group and is distributed under
00006 // the University of Illinois Open Source License. See LICENSE.TXT for details.
00007 //
00008 //===----------------------------------------------------------------------===//
00009 //
00010 // This file defines the classes used to represent and build scalar expressions.
00011 //
00012 //===----------------------------------------------------------------------===//
00013 
00014 #ifndef LLVM_ANALYSIS_SCALAREVOLUTION_EXPRESSIONS_H
00015 #define LLVM_ANALYSIS_SCALAREVOLUTION_EXPRESSIONS_H
00016 
00017 #include "llvm/Analysis/ScalarEvolution.h"
00018 
00019 namespace llvm {
00020   class ConstantInt;
00021   class ConstantRange;
00022 
00023   enum SCEVTypes {
00024     // These should be ordered in terms of increasing complexity to make the
00025     // folders simpler.
00026     scConstant, scTruncate, scZeroExtend, scAddExpr, scMulExpr, scSDivExpr,
00027     scAddRecExpr, scUnknown, scCouldNotCompute
00028   };
00029 
00030   //===--------------------------------------------------------------------===//
00031   /// SCEVConstant - This class represents a constant integer value.
00032   ///
00033   class SCEVConstant : public SCEV {
00034     ConstantInt *V;
00035     SCEVConstant(ConstantInt *v) : SCEV(scConstant), V(v) {}
00036 
00037     virtual ~SCEVConstant();
00038   public:
00039     /// get method - This just gets and returns a new SCEVConstant object.
00040     ///
00041     static SCEVHandle get(ConstantInt *V);
00042 
00043     ConstantInt *getValue() const { return V; }
00044 
00045     /// getValueRange - Return the tightest constant bounds that this value is
00046     /// known to have.  This method is only valid on integer SCEV objects.
00047     virtual ConstantRange getValueRange() const;
00048 
00049     virtual bool isLoopInvariant(const Loop *L) const {
00050       return true;
00051     }
00052 
00053     virtual bool hasComputableLoopEvolution(const Loop *L) const {
00054       return false;  // Not loop variant
00055     }
00056 
00057     virtual const Type *getType() const;
00058 
00059     SCEVHandle replaceSymbolicValuesWithConcrete(const SCEVHandle &Sym,
00060                                                  const SCEVHandle &Conc) const {
00061       return this;
00062     }
00063 
00064     virtual void print(std::ostream &OS) const;
00065 
00066     /// Methods for support type inquiry through isa, cast, and dyn_cast:
00067     static inline bool classof(const SCEVConstant *S) { return true; }
00068     static inline bool classof(const SCEV *S) {
00069       return S->getSCEVType() == scConstant;
00070     }
00071   };
00072 
00073   //===--------------------------------------------------------------------===//
00074   /// SCEVTruncateExpr - This class represents a truncation of an integer value
00075   /// to a smaller integer value.
00076   ///
00077   class SCEVTruncateExpr : public SCEV {
00078     SCEVHandle Op;
00079     const Type *Ty;
00080     SCEVTruncateExpr(const SCEVHandle &op, const Type *ty);
00081     virtual ~SCEVTruncateExpr();
00082   public:
00083     /// get method - This just gets and returns a new SCEVTruncate object
00084     ///
00085     static SCEVHandle get(const SCEVHandle &Op, const Type *Ty);
00086 
00087     const SCEVHandle &getOperand() const { return Op; }
00088     virtual const Type *getType() const { return Ty; }
00089 
00090     virtual bool isLoopInvariant(const Loop *L) const {
00091       return Op->isLoopInvariant(L);
00092     }
00093 
00094     virtual bool hasComputableLoopEvolution(const Loop *L) const {
00095       return Op->hasComputableLoopEvolution(L);
00096     }
00097 
00098     SCEVHandle replaceSymbolicValuesWithConcrete(const SCEVHandle &Sym,
00099                                                  const SCEVHandle &Conc) const {
00100       SCEVHandle H = Op->replaceSymbolicValuesWithConcrete(Sym, Conc);
00101       if (H == Op)
00102         return this;
00103       return get(H, Ty);
00104     }
00105 
00106     /// getValueRange - Return the tightest constant bounds that this value is
00107     /// known to have.  This method is only valid on integer SCEV objects.
00108     virtual ConstantRange getValueRange() const;
00109 
00110     virtual void print(std::ostream &OS) const;
00111 
00112     /// Methods for support type inquiry through isa, cast, and dyn_cast:
00113     static inline bool classof(const SCEVTruncateExpr *S) { return true; }
00114     static inline bool classof(const SCEV *S) {
00115       return S->getSCEVType() == scTruncate;
00116     }
00117   };
00118 
00119   //===--------------------------------------------------------------------===//
00120   /// SCEVZeroExtendExpr - This class represents a zero extension of a small
00121   /// integer value to a larger integer value.
00122   ///
00123   class SCEVZeroExtendExpr : public SCEV {
00124     SCEVHandle Op;
00125     const Type *Ty;
00126     SCEVZeroExtendExpr(const SCEVHandle &op, const Type *ty);
00127     virtual ~SCEVZeroExtendExpr();
00128   public:
00129     /// get method - This just gets and returns a new SCEVZeroExtend object
00130     ///
00131     static SCEVHandle get(const SCEVHandle &Op, const Type *Ty);
00132 
00133     const SCEVHandle &getOperand() const { return Op; }
00134     virtual const Type *getType() const { return Ty; }
00135 
00136     virtual bool isLoopInvariant(const Loop *L) const {
00137       return Op->isLoopInvariant(L);
00138     }
00139 
00140     virtual bool hasComputableLoopEvolution(const Loop *L) const {
00141       return Op->hasComputableLoopEvolution(L);
00142     }
00143 
00144     /// getValueRange - Return the tightest constant bounds that this value is
00145     /// known to have.  This method is only valid on integer SCEV objects.
00146     virtual ConstantRange getValueRange() const;
00147 
00148     SCEVHandle replaceSymbolicValuesWithConcrete(const SCEVHandle &Sym,
00149                                                  const SCEVHandle &Conc) const {
00150       SCEVHandle H = Op->replaceSymbolicValuesWithConcrete(Sym, Conc);
00151       if (H == Op)
00152         return this;
00153       return get(H, Ty);
00154     }
00155 
00156     virtual void print(std::ostream &OS) const;
00157 
00158     /// Methods for support type inquiry through isa, cast, and dyn_cast:
00159     static inline bool classof(const SCEVZeroExtendExpr *S) { return true; }
00160     static inline bool classof(const SCEV *S) {
00161       return S->getSCEVType() == scZeroExtend;
00162     }
00163   };
00164 
00165 
00166   //===--------------------------------------------------------------------===//
00167   /// SCEVCommutativeExpr - This node is the base class for n'ary commutative
00168   /// operators.
00169   ///
00170   class SCEVCommutativeExpr : public SCEV {
00171     std::vector<SCEVHandle> Operands;
00172 
00173   protected:
00174     SCEVCommutativeExpr(enum SCEVTypes T, const std::vector<SCEVHandle> &ops)
00175       : SCEV(T) {
00176       Operands.reserve(ops.size());
00177       Operands.insert(Operands.end(), ops.begin(), ops.end());
00178     }
00179     ~SCEVCommutativeExpr();
00180 
00181   public:
00182     unsigned getNumOperands() const { return Operands.size(); }
00183     const SCEVHandle &getOperand(unsigned i) const {
00184       assert(i < Operands.size() && "Operand index out of range!");
00185       return Operands[i];
00186     }
00187 
00188     const std::vector<SCEVHandle> &getOperands() const { return Operands; }
00189     typedef std::vector<SCEVHandle>::const_iterator op_iterator;
00190     op_iterator op_begin() const { return Operands.begin(); }
00191     op_iterator op_end() const { return Operands.end(); }
00192 
00193 
00194     virtual bool isLoopInvariant(const Loop *L) const {
00195       for (unsigned i = 0, e = getNumOperands(); i != e; ++i)
00196         if (!getOperand(i)->isLoopInvariant(L)) return false;
00197       return true;
00198     }
00199 
00200     // hasComputableLoopEvolution - Commutative expressions have computable loop
00201     // evolutions iff they have at least one operand that varies with the loop,
00202     // but that all varying operands are computable.
00203     virtual bool hasComputableLoopEvolution(const Loop *L) const {
00204       bool HasVarying = false;
00205       for (unsigned i = 0, e = getNumOperands(); i != e; ++i)
00206         if (!getOperand(i)->isLoopInvariant(L))
00207           if (getOperand(i)->hasComputableLoopEvolution(L))
00208             HasVarying = true;
00209           else
00210             return false;
00211       return HasVarying;
00212     }
00213 
00214     SCEVHandle replaceSymbolicValuesWithConcrete(const SCEVHandle &Sym,
00215                                                  const SCEVHandle &Conc) const;
00216 
00217     virtual const char *getOperationStr() const = 0;
00218 
00219     virtual const Type *getType() const { return getOperand(0)->getType(); }
00220     virtual void print(std::ostream &OS) const;
00221 
00222     /// Methods for support type inquiry through isa, cast, and dyn_cast:
00223     static inline bool classof(const SCEVCommutativeExpr *S) { return true; }
00224     static inline bool classof(const SCEV *S) {
00225       return S->getSCEVType() == scAddExpr ||
00226              S->getSCEVType() == scMulExpr;
00227     }
00228   };
00229 
00230 
00231   //===--------------------------------------------------------------------===//
00232   /// SCEVAddExpr - This node represents an addition of some number of SCEVs.
00233   ///
00234   class SCEVAddExpr : public SCEVCommutativeExpr {
00235     SCEVAddExpr(const std::vector<SCEVHandle> &ops)
00236       : SCEVCommutativeExpr(scAddExpr, ops) {
00237     }
00238 
00239   public:
00240     static SCEVHandle get(std::vector<SCEVHandle> &Ops);
00241 
00242     static SCEVHandle get(const SCEVHandle &LHS, const SCEVHandle &RHS) {
00243       std::vector<SCEVHandle> Ops;
00244       Ops.push_back(LHS);
00245       Ops.push_back(RHS);
00246       return get(Ops);
00247     }
00248 
00249     static SCEVHandle get(const SCEVHandle &Op0, const SCEVHandle &Op1,
00250                           const SCEVHandle &Op2) {
00251       std::vector<SCEVHandle> Ops;
00252       Ops.push_back(Op0);
00253       Ops.push_back(Op1);
00254       Ops.push_back(Op2);
00255       return get(Ops);
00256     }
00257 
00258     virtual const char *getOperationStr() const { return " + "; }
00259 
00260     /// Methods for support type inquiry through isa, cast, and dyn_cast:
00261     static inline bool classof(const SCEVAddExpr *S) { return true; }
00262     static inline bool classof(const SCEV *S) {
00263       return S->getSCEVType() == scAddExpr;
00264     }
00265   };
00266 
00267   //===--------------------------------------------------------------------===//
00268   /// SCEVMulExpr - This node represents multiplication of some number of SCEVs.
00269   ///
00270   class SCEVMulExpr : public SCEVCommutativeExpr {
00271     SCEVMulExpr(const std::vector<SCEVHandle> &ops)
00272       : SCEVCommutativeExpr(scMulExpr, ops) {
00273     }
00274 
00275   public:
00276     static SCEVHandle get(std::vector<SCEVHandle> &Ops);
00277 
00278     static SCEVHandle get(const SCEVHandle &LHS, const SCEVHandle &RHS) {
00279       std::vector<SCEVHandle> Ops;
00280       Ops.push_back(LHS);
00281       Ops.push_back(RHS);
00282       return get(Ops);
00283     }
00284 
00285     virtual const char *getOperationStr() const { return " * "; }
00286 
00287     /// Methods for support type inquiry through isa, cast, and dyn_cast:
00288     static inline bool classof(const SCEVMulExpr *S) { return true; }
00289     static inline bool classof(const SCEV *S) {
00290       return S->getSCEVType() == scMulExpr;
00291     }
00292   };
00293 
00294 
00295   //===--------------------------------------------------------------------===//
00296   /// SCEVSDivExpr - This class represents a binary unsigned division operation.
00297   ///
00298   class SCEVSDivExpr : public SCEV {
00299     SCEVHandle LHS, RHS;
00300     SCEVSDivExpr(const SCEVHandle &lhs, const SCEVHandle &rhs)
00301       : SCEV(scSDivExpr), LHS(lhs), RHS(rhs) {}
00302 
00303     virtual ~SCEVSDivExpr();
00304   public:
00305     /// get method - This just gets and returns a new SCEVSDiv object.
00306     ///
00307     static SCEVHandle get(const SCEVHandle &LHS, const SCEVHandle &RHS);
00308 
00309     const SCEVHandle &getLHS() const { return LHS; }
00310     const SCEVHandle &getRHS() const { return RHS; }
00311 
00312     virtual bool isLoopInvariant(const Loop *L) const {
00313       return LHS->isLoopInvariant(L) && RHS->isLoopInvariant(L);
00314     }
00315 
00316     virtual bool hasComputableLoopEvolution(const Loop *L) const {
00317       return LHS->hasComputableLoopEvolution(L) &&
00318              RHS->hasComputableLoopEvolution(L);
00319     }
00320 
00321     SCEVHandle replaceSymbolicValuesWithConcrete(const SCEVHandle &Sym,
00322                                                  const SCEVHandle &Conc) const {
00323       SCEVHandle L = LHS->replaceSymbolicValuesWithConcrete(Sym, Conc);
00324       SCEVHandle R = RHS->replaceSymbolicValuesWithConcrete(Sym, Conc);
00325       if (L == LHS && R == RHS)
00326         return this;
00327       else
00328         return get(L, R);
00329     }
00330 
00331 
00332     virtual const Type *getType() const;
00333 
00334     void print(std::ostream &OS) const;
00335 
00336     /// Methods for support type inquiry through isa, cast, and dyn_cast:
00337     static inline bool classof(const SCEVSDivExpr *S) { return true; }
00338     static inline bool classof(const SCEV *S) {
00339       return S->getSCEVType() == scSDivExpr;
00340     }
00341   };
00342 
00343 
00344   //===--------------------------------------------------------------------===//
00345   /// SCEVAddRecExpr - This node represents a polynomial recurrence on the trip
00346   /// count of the specified loop.
00347   ///
00348   /// All operands of an AddRec are required to be loop invariant.
00349   ///
00350   class SCEVAddRecExpr : public SCEV {
00351     std::vector<SCEVHandle> Operands;
00352     const Loop *L;
00353 
00354     SCEVAddRecExpr(const std::vector<SCEVHandle> &ops, const Loop *l)
00355       : SCEV(scAddRecExpr), Operands(ops), L(l) {
00356       for (unsigned i = 0, e = Operands.size(); i != e; ++i)
00357         assert(Operands[i]->isLoopInvariant(l) &&
00358                "Operands of AddRec must be loop-invariant!");
00359     }
00360     ~SCEVAddRecExpr();
00361   public:
00362     static SCEVHandle get(const SCEVHandle &Start, const SCEVHandle &Step,
00363                           const Loop *);
00364     static SCEVHandle get(std::vector<SCEVHandle> &Operands,
00365                           const Loop *);
00366     static SCEVHandle get(const std::vector<SCEVHandle> &Operands,
00367                           const Loop *L) {
00368       std::vector<SCEVHandle> NewOp(Operands);
00369       return get(NewOp, L);
00370     }
00371 
00372     typedef std::vector<SCEVHandle>::const_iterator op_iterator;
00373     op_iterator op_begin() const { return Operands.begin(); }
00374     op_iterator op_end() const { return Operands.end(); }
00375 
00376     unsigned getNumOperands() const { return Operands.size(); }
00377     const SCEVHandle &getOperand(unsigned i) const { return Operands[i]; }
00378     const SCEVHandle &getStart() const { return Operands[0]; }
00379     const Loop *getLoop() const { return L; }
00380 
00381 
00382     /// getStepRecurrence - This method constructs and returns the recurrence
00383     /// indicating how much this expression steps by.  If this is a polynomial
00384     /// of degree N, it returns a chrec of degree N-1.
00385     SCEVHandle getStepRecurrence() const {
00386       if (getNumOperands() == 2) return getOperand(1);
00387       return SCEVAddRecExpr::get(std::vector<SCEVHandle>(op_begin()+1,op_end()),
00388                                  getLoop());
00389     }
00390 
00391     virtual bool hasComputableLoopEvolution(const Loop *QL) const {
00392       if (L == QL) return true;
00393       return false;
00394     }
00395 
00396     virtual bool isLoopInvariant(const Loop *QueryLoop) const;
00397 
00398     virtual const Type *getType() const { return Operands[0]->getType(); }
00399 
00400     /// isAffine - Return true if this is an affine AddRec (i.e., it represents
00401     /// an expressions A+B*x where A and B are loop invariant values.
00402     bool isAffine() const {
00403       // We know that the start value is invariant.  This expression is thus
00404       // affine iff the step is also invariant.
00405       return getNumOperands() == 2;
00406     }
00407 
00408     /// isQuadratic - Return true if this is an quadratic AddRec (i.e., it
00409     /// represents an expressions A+B*x+C*x^2 where A, B and C are loop
00410     /// invariant values.  This corresponds to an addrec of the form {L,+,M,+,N}
00411     bool isQuadratic() const {
00412       return getNumOperands() == 3;
00413     }
00414 
00415     /// evaluateAtIteration - Return the value of this chain of recurrences at
00416     /// the specified iteration number.
00417     SCEVHandle evaluateAtIteration(SCEVHandle It) const;
00418 
00419     /// getNumIterationsInRange - Return the number of iterations of this loop
00420     /// that produce values in the specified constant range.  Another way of
00421     /// looking at this is that it returns the first iteration number where the
00422     /// value is not in the condition, thus computing the exit count.  If the
00423     /// iteration count can't be computed, an instance of SCEVCouldNotCompute is
00424     /// returned.
00425     SCEVHandle getNumIterationsInRange(ConstantRange Range) const;
00426 
00427     SCEVHandle replaceSymbolicValuesWithConcrete(const SCEVHandle &Sym,
00428                                                  const SCEVHandle &Conc) const;
00429 
00430     virtual void print(std::ostream &OS) const;
00431 
00432     /// Methods for support type inquiry through isa, cast, and dyn_cast:
00433     static inline bool classof(const SCEVAddRecExpr *S) { return true; }
00434     static inline bool classof(const SCEV *S) {
00435       return S->getSCEVType() == scAddRecExpr;
00436     }
00437   };
00438 
00439   //===--------------------------------------------------------------------===//
00440   /// SCEVUnknown - This means that we are dealing with an entirely unknown SCEV
00441   /// value, and only represent it as it's LLVM Value.  This is the "bottom"
00442   /// value for the analysis.
00443   ///
00444   class SCEVUnknown : public SCEV {
00445     Value *V;
00446     SCEVUnknown(Value *v) : SCEV(scUnknown), V(v) {}
00447 
00448   protected:
00449     ~SCEVUnknown();
00450   public:
00451     /// get method - For SCEVUnknown, this just gets and returns a new
00452     /// SCEVUnknown.
00453     static SCEVHandle get(Value *V);
00454 
00455     /// getIntegerSCEV - Given an integer or FP type, create a constant for the
00456     /// specified signed integer value and return a SCEV for the constant.
00457     static SCEVHandle getIntegerSCEV(int Val, const Type *Ty);
00458 
00459     Value *getValue() const { return V; }
00460 
00461     virtual bool isLoopInvariant(const Loop *L) const;
00462     virtual bool hasComputableLoopEvolution(const Loop *QL) const {
00463       return false; // not computable
00464     }
00465 
00466     SCEVHandle replaceSymbolicValuesWithConcrete(const SCEVHandle &Sym,
00467                                                  const SCEVHandle &Conc) const {
00468       if (&*Sym == this) return Conc;
00469       return this;
00470     }
00471 
00472     virtual const Type *getType() const;
00473 
00474     virtual void print(std::ostream &OS) const;
00475 
00476     /// Methods for support type inquiry through isa, cast, and dyn_cast:
00477     static inline bool classof(const SCEVUnknown *S) { return true; }
00478     static inline bool classof(const SCEV *S) {
00479       return S->getSCEVType() == scUnknown;
00480     }
00481   };
00482 
00483   /// SCEVVisitor - This class defines a simple visitor class that may be used
00484   /// for various SCEV analysis purposes.
00485   template<typename SC, typename RetVal=void>
00486   struct SCEVVisitor {
00487     RetVal visit(SCEV *S) {
00488       switch (S->getSCEVType()) {
00489       case scConstant:
00490         return ((SC*)this)->visitConstant((SCEVConstant*)S);
00491       case scTruncate:
00492         return ((SC*)this)->visitTruncateExpr((SCEVTruncateExpr*)S);
00493       case scZeroExtend:
00494         return ((SC*)this)->visitZeroExtendExpr((SCEVZeroExtendExpr*)S);
00495       case scAddExpr:
00496         return ((SC*)this)->visitAddExpr((SCEVAddExpr*)S);
00497       case scMulExpr:
00498         return ((SC*)this)->visitMulExpr((SCEVMulExpr*)S);
00499       case scSDivExpr:
00500         return ((SC*)this)->visitSDivExpr((SCEVSDivExpr*)S);
00501       case scAddRecExpr:
00502         return ((SC*)this)->visitAddRecExpr((SCEVAddRecExpr*)S);
00503       case scUnknown:
00504         return ((SC*)this)->visitUnknown((SCEVUnknown*)S);
00505       case scCouldNotCompute:
00506         return ((SC*)this)->visitCouldNotCompute((SCEVCouldNotCompute*)S);
00507       default:
00508         assert(0 && "Unknown SCEV type!");
00509         abort();
00510       }
00511     }
00512 
00513     RetVal visitCouldNotCompute(SCEVCouldNotCompute *S) {
00514       assert(0 && "Invalid use of SCEVCouldNotCompute!");
00515       abort();
00516       return RetVal();
00517     }
00518   };
00519 }
00520 
00521 #endif
00522