LLVM  mainline
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 is distributed under the University of Illinois Open Source
00006 // 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_SCALAREVOLUTIONEXPRESSIONS_H
00015 #define LLVM_ANALYSIS_SCALAREVOLUTIONEXPRESSIONS_H
00016 
00017 #include "llvm/ADT/SmallPtrSet.h"
00018 #include "llvm/ADT/iterator_range.h"
00019 #include "llvm/Analysis/ScalarEvolution.h"
00020 #include "llvm/Support/ErrorHandling.h"
00021 
00022 namespace llvm {
00023   class ConstantInt;
00024   class ConstantRange;
00025   class DominatorTree;
00026 
00027   enum SCEVTypes {
00028     // These should be ordered in terms of increasing complexity to make the
00029     // folders simpler.
00030     scConstant, scTruncate, scZeroExtend, scSignExtend, scAddExpr, scMulExpr,
00031     scUDivExpr, scAddRecExpr, scUMaxExpr, scSMaxExpr,
00032     scUnknown, scCouldNotCompute
00033   };
00034 
00035   //===--------------------------------------------------------------------===//
00036   /// SCEVConstant - This class represents a constant integer value.
00037   ///
00038   class SCEVConstant : public SCEV {
00039     friend class ScalarEvolution;
00040 
00041     ConstantInt *V;
00042     SCEVConstant(const FoldingSetNodeIDRef ID, ConstantInt *v) :
00043       SCEV(ID, scConstant), V(v) {}
00044   public:
00045     ConstantInt *getValue() const { return V; }
00046     const APInt &getAPInt() const { return getValue()->getValue(); }
00047 
00048     Type *getType() const { return V->getType(); }
00049 
00050     /// Methods for support type inquiry through isa, cast, and dyn_cast:
00051     static inline bool classof(const SCEV *S) {
00052       return S->getSCEVType() == scConstant;
00053     }
00054   };
00055 
00056   //===--------------------------------------------------------------------===//
00057   /// SCEVCastExpr - This is the base class for unary cast operator classes.
00058   ///
00059   class SCEVCastExpr : public SCEV {
00060   protected:
00061     const SCEV *Op;
00062     Type *Ty;
00063 
00064     SCEVCastExpr(const FoldingSetNodeIDRef ID,
00065                  unsigned SCEVTy, const SCEV *op, Type *ty);
00066 
00067   public:
00068     const SCEV *getOperand() const { return Op; }
00069     Type *getType() const { return Ty; }
00070 
00071     /// Methods for support type inquiry through isa, cast, and dyn_cast:
00072     static inline bool classof(const SCEV *S) {
00073       return S->getSCEVType() == scTruncate ||
00074              S->getSCEVType() == scZeroExtend ||
00075              S->getSCEVType() == scSignExtend;
00076     }
00077   };
00078 
00079   //===--------------------------------------------------------------------===//
00080   /// SCEVTruncateExpr - This class represents a truncation of an integer value
00081   /// to a smaller integer value.
00082   ///
00083   class SCEVTruncateExpr : public SCEVCastExpr {
00084     friend class ScalarEvolution;
00085 
00086     SCEVTruncateExpr(const FoldingSetNodeIDRef ID,
00087                      const SCEV *op, Type *ty);
00088 
00089   public:
00090     /// Methods for support type inquiry through isa, cast, and dyn_cast:
00091     static inline bool classof(const SCEV *S) {
00092       return S->getSCEVType() == scTruncate;
00093     }
00094   };
00095 
00096   //===--------------------------------------------------------------------===//
00097   /// SCEVZeroExtendExpr - This class represents a zero extension of a small
00098   /// integer value to a larger integer value.
00099   ///
00100   class SCEVZeroExtendExpr : public SCEVCastExpr {
00101     friend class ScalarEvolution;
00102 
00103     SCEVZeroExtendExpr(const FoldingSetNodeIDRef ID,
00104                        const SCEV *op, Type *ty);
00105 
00106   public:
00107     /// Methods for support type inquiry through isa, cast, and dyn_cast:
00108     static inline bool classof(const SCEV *S) {
00109       return S->getSCEVType() == scZeroExtend;
00110     }
00111   };
00112 
00113   //===--------------------------------------------------------------------===//
00114   /// SCEVSignExtendExpr - This class represents a sign extension of a small
00115   /// integer value to a larger integer value.
00116   ///
00117   class SCEVSignExtendExpr : public SCEVCastExpr {
00118     friend class ScalarEvolution;
00119 
00120     SCEVSignExtendExpr(const FoldingSetNodeIDRef ID,
00121                        const SCEV *op, Type *ty);
00122 
00123   public:
00124     /// Methods for support type inquiry through isa, cast, and dyn_cast:
00125     static inline bool classof(const SCEV *S) {
00126       return S->getSCEVType() == scSignExtend;
00127     }
00128   };
00129 
00130 
00131   //===--------------------------------------------------------------------===//
00132   /// SCEVNAryExpr - This node is a base class providing common
00133   /// functionality for n'ary operators.
00134   ///
00135   class SCEVNAryExpr : public SCEV {
00136   protected:
00137     // Since SCEVs are immutable, ScalarEvolution allocates operand
00138     // arrays with its SCEVAllocator, so this class just needs a simple
00139     // pointer rather than a more elaborate vector-like data structure.
00140     // This also avoids the need for a non-trivial destructor.
00141     const SCEV *const *Operands;
00142     size_t NumOperands;
00143 
00144     SCEVNAryExpr(const FoldingSetNodeIDRef ID,
00145                  enum SCEVTypes T, const SCEV *const *O, size_t N)
00146       : SCEV(ID, T), Operands(O), NumOperands(N) {}
00147 
00148   public:
00149     size_t getNumOperands() const { return NumOperands; }
00150     const SCEV *getOperand(unsigned i) const {
00151       assert(i < NumOperands && "Operand index out of range!");
00152       return Operands[i];
00153     }
00154 
00155     typedef const SCEV *const *op_iterator;
00156     typedef iterator_range<op_iterator> op_range;
00157     op_iterator op_begin() const { return Operands; }
00158     op_iterator op_end() const { return Operands + NumOperands; }
00159     op_range operands() const {
00160       return make_range(op_begin(), op_end());
00161     }
00162 
00163     Type *getType() const { return getOperand(0)->getType(); }
00164 
00165     NoWrapFlags getNoWrapFlags(NoWrapFlags Mask = NoWrapMask) const {
00166       return (NoWrapFlags)(SubclassData & Mask);
00167     }
00168 
00169     /// Methods for support type inquiry through isa, cast, and dyn_cast:
00170     static inline bool classof(const SCEV *S) {
00171       return S->getSCEVType() == scAddExpr ||
00172              S->getSCEVType() == scMulExpr ||
00173              S->getSCEVType() == scSMaxExpr ||
00174              S->getSCEVType() == scUMaxExpr ||
00175              S->getSCEVType() == scAddRecExpr;
00176     }
00177   };
00178 
00179   //===--------------------------------------------------------------------===//
00180   /// SCEVCommutativeExpr - This node is the base class for n'ary commutative
00181   /// operators.
00182   ///
00183   class SCEVCommutativeExpr : public SCEVNAryExpr {
00184   protected:
00185     SCEVCommutativeExpr(const FoldingSetNodeIDRef ID,
00186                         enum SCEVTypes T, const SCEV *const *O, size_t N)
00187       : SCEVNAryExpr(ID, T, O, N) {}
00188 
00189   public:
00190     /// Methods for support type inquiry through isa, cast, and dyn_cast:
00191     static inline bool classof(const SCEV *S) {
00192       return S->getSCEVType() == scAddExpr ||
00193              S->getSCEVType() == scMulExpr ||
00194              S->getSCEVType() == scSMaxExpr ||
00195              S->getSCEVType() == scUMaxExpr;
00196     }
00197 
00198     /// Set flags for a non-recurrence without clearing previously set flags.
00199     void setNoWrapFlags(NoWrapFlags Flags) {
00200       SubclassData |= Flags;
00201     }
00202   };
00203 
00204 
00205   //===--------------------------------------------------------------------===//
00206   /// SCEVAddExpr - This node represents an addition of some number of SCEVs.
00207   ///
00208   class SCEVAddExpr : public SCEVCommutativeExpr {
00209     friend class ScalarEvolution;
00210 
00211     SCEVAddExpr(const FoldingSetNodeIDRef ID,
00212                 const SCEV *const *O, size_t N)
00213       : SCEVCommutativeExpr(ID, scAddExpr, O, N) {
00214     }
00215 
00216   public:
00217     Type *getType() const {
00218       // Use the type of the last operand, which is likely to be a pointer
00219       // type, if there is one. This doesn't usually matter, but it can help
00220       // reduce casts when the expressions are expanded.
00221       return getOperand(getNumOperands() - 1)->getType();
00222     }
00223 
00224     /// Methods for support type inquiry through isa, cast, and dyn_cast:
00225     static inline bool classof(const SCEV *S) {
00226       return S->getSCEVType() == scAddExpr;
00227     }
00228   };
00229 
00230   //===--------------------------------------------------------------------===//
00231   /// SCEVMulExpr - This node represents multiplication of some number of SCEVs.
00232   ///
00233   class SCEVMulExpr : public SCEVCommutativeExpr {
00234     friend class ScalarEvolution;
00235 
00236     SCEVMulExpr(const FoldingSetNodeIDRef ID,
00237                 const SCEV *const *O, size_t N)
00238       : SCEVCommutativeExpr(ID, scMulExpr, O, N) {
00239     }
00240 
00241   public:
00242     /// Methods for support type inquiry through isa, cast, and dyn_cast:
00243     static inline bool classof(const SCEV *S) {
00244       return S->getSCEVType() == scMulExpr;
00245     }
00246   };
00247 
00248 
00249   //===--------------------------------------------------------------------===//
00250   /// SCEVUDivExpr - This class represents a binary unsigned division operation.
00251   ///
00252   class SCEVUDivExpr : public SCEV {
00253     friend class ScalarEvolution;
00254 
00255     const SCEV *LHS;
00256     const SCEV *RHS;
00257     SCEVUDivExpr(const FoldingSetNodeIDRef ID, const SCEV *lhs, const SCEV *rhs)
00258       : SCEV(ID, scUDivExpr), LHS(lhs), RHS(rhs) {}
00259 
00260   public:
00261     const SCEV *getLHS() const { return LHS; }
00262     const SCEV *getRHS() const { return RHS; }
00263 
00264     Type *getType() const {
00265       // In most cases the types of LHS and RHS will be the same, but in some
00266       // crazy cases one or the other may be a pointer. ScalarEvolution doesn't
00267       // depend on the type for correctness, but handling types carefully can
00268       // avoid extra casts in the SCEVExpander. The LHS is more likely to be
00269       // a pointer type than the RHS, so use the RHS' type here.
00270       return getRHS()->getType();
00271     }
00272 
00273     /// Methods for support type inquiry through isa, cast, and dyn_cast:
00274     static inline bool classof(const SCEV *S) {
00275       return S->getSCEVType() == scUDivExpr;
00276     }
00277   };
00278 
00279 
00280   //===--------------------------------------------------------------------===//
00281   /// SCEVAddRecExpr - This node represents a polynomial recurrence on the trip
00282   /// count of the specified loop.  This is the primary focus of the
00283   /// ScalarEvolution framework; all the other SCEV subclasses are mostly just
00284   /// supporting infrastructure to allow SCEVAddRecExpr expressions to be
00285   /// created and analyzed.
00286   ///
00287   /// All operands of an AddRec are required to be loop invariant.
00288   ///
00289   class SCEVAddRecExpr : public SCEVNAryExpr {
00290     friend class ScalarEvolution;
00291 
00292     const Loop *L;
00293 
00294     SCEVAddRecExpr(const FoldingSetNodeIDRef ID,
00295                    const SCEV *const *O, size_t N, const Loop *l)
00296       : SCEVNAryExpr(ID, scAddRecExpr, O, N), L(l) {}
00297 
00298   public:
00299     const SCEV *getStart() const { return Operands[0]; }
00300     const Loop *getLoop() const { return L; }
00301 
00302     /// getStepRecurrence - This method constructs and returns the recurrence
00303     /// indicating how much this expression steps by.  If this is a polynomial
00304     /// of degree N, it returns a chrec of degree N-1.
00305     /// We cannot determine whether the step recurrence has self-wraparound.
00306     const SCEV *getStepRecurrence(ScalarEvolution &SE) const {
00307       if (isAffine()) return getOperand(1);
00308       return SE.getAddRecExpr(SmallVector<const SCEV *, 3>(op_begin()+1,
00309                                                            op_end()),
00310                               getLoop(), FlagAnyWrap);
00311     }
00312 
00313     /// isAffine - Return true if this represents an expression
00314     /// A + B*x where A and B are loop invariant values.
00315     bool isAffine() const {
00316       // We know that the start value is invariant.  This expression is thus
00317       // affine iff the step is also invariant.
00318       return getNumOperands() == 2;
00319     }
00320 
00321     /// isQuadratic - Return true if this represents an expression
00322     /// A + B*x + C*x^2 where A, B and C are loop invariant values.
00323     /// This corresponds to an addrec of the form {L,+,M,+,N}
00324     bool isQuadratic() const {
00325       return getNumOperands() == 3;
00326     }
00327 
00328     /// Set flags for a recurrence without clearing any previously set flags.
00329     /// For AddRec, either NUW or NSW implies NW. Keep track of this fact here
00330     /// to make it easier to propagate flags.
00331     void setNoWrapFlags(NoWrapFlags Flags) {
00332       if (Flags & (FlagNUW | FlagNSW))
00333         Flags = ScalarEvolution::setFlags(Flags, FlagNW);
00334       SubclassData |= Flags;
00335     }
00336 
00337     /// evaluateAtIteration - Return the value of this chain of recurrences at
00338     /// the specified iteration number.
00339     const SCEV *evaluateAtIteration(const SCEV *It, ScalarEvolution &SE) const;
00340 
00341     /// getNumIterationsInRange - Return the number of iterations of this loop
00342     /// that produce values in the specified constant range.  Another way of
00343     /// looking at this is that it returns the first iteration number where the
00344     /// value is not in the condition, thus computing the exit count.  If the
00345     /// iteration count can't be computed, an instance of SCEVCouldNotCompute is
00346     /// returned.
00347     const SCEV *getNumIterationsInRange(ConstantRange Range,
00348                                        ScalarEvolution &SE) const;
00349 
00350     /// getPostIncExpr - Return an expression representing the value of
00351     /// this expression one iteration of the loop ahead.
00352     const SCEVAddRecExpr *getPostIncExpr(ScalarEvolution &SE) const {
00353       return cast<SCEVAddRecExpr>(SE.getAddExpr(this, getStepRecurrence(SE)));
00354     }
00355 
00356     /// Methods for support type inquiry through isa, cast, and dyn_cast:
00357     static inline bool classof(const SCEV *S) {
00358       return S->getSCEVType() == scAddRecExpr;
00359     }
00360   };
00361 
00362   //===--------------------------------------------------------------------===//
00363   /// SCEVSMaxExpr - This class represents a signed maximum selection.
00364   ///
00365   class SCEVSMaxExpr : public SCEVCommutativeExpr {
00366     friend class ScalarEvolution;
00367 
00368     SCEVSMaxExpr(const FoldingSetNodeIDRef ID,
00369                  const SCEV *const *O, size_t N)
00370       : SCEVCommutativeExpr(ID, scSMaxExpr, O, N) {
00371       // Max never overflows.
00372       setNoWrapFlags((NoWrapFlags)(FlagNUW | FlagNSW));
00373     }
00374 
00375   public:
00376     /// Methods for support type inquiry through isa, cast, and dyn_cast:
00377     static inline bool classof(const SCEV *S) {
00378       return S->getSCEVType() == scSMaxExpr;
00379     }
00380   };
00381 
00382 
00383   //===--------------------------------------------------------------------===//
00384   /// SCEVUMaxExpr - This class represents an unsigned maximum selection.
00385   ///
00386   class SCEVUMaxExpr : public SCEVCommutativeExpr {
00387     friend class ScalarEvolution;
00388 
00389     SCEVUMaxExpr(const FoldingSetNodeIDRef ID,
00390                  const SCEV *const *O, size_t N)
00391       : SCEVCommutativeExpr(ID, scUMaxExpr, O, N) {
00392       // Max never overflows.
00393       setNoWrapFlags((NoWrapFlags)(FlagNUW | FlagNSW));
00394     }
00395 
00396   public:
00397     /// Methods for support type inquiry through isa, cast, and dyn_cast:
00398     static inline bool classof(const SCEV *S) {
00399       return S->getSCEVType() == scUMaxExpr;
00400     }
00401   };
00402 
00403   //===--------------------------------------------------------------------===//
00404   /// SCEVUnknown - This means that we are dealing with an entirely unknown SCEV
00405   /// value, and only represent it as its LLVM Value.  This is the "bottom"
00406   /// value for the analysis.
00407   ///
00408   class SCEVUnknown final : public SCEV, private CallbackVH {
00409     friend class ScalarEvolution;
00410 
00411     // Implement CallbackVH.
00412     void deleted() override;
00413     void allUsesReplacedWith(Value *New) override;
00414 
00415     /// SE - The parent ScalarEvolution value. This is used to update
00416     /// the parent's maps when the value associated with a SCEVUnknown
00417     /// is deleted or RAUW'd.
00418     ScalarEvolution *SE;
00419 
00420     /// Next - The next pointer in the linked list of all
00421     /// SCEVUnknown instances owned by a ScalarEvolution.
00422     SCEVUnknown *Next;
00423 
00424     SCEVUnknown(const FoldingSetNodeIDRef ID, Value *V,
00425                 ScalarEvolution *se, SCEVUnknown *next) :
00426       SCEV(ID, scUnknown), CallbackVH(V), SE(se), Next(next) {}
00427 
00428   public:
00429     Value *getValue() const { return getValPtr(); }
00430 
00431     /// isSizeOf, isAlignOf, isOffsetOf - Test whether this is a special
00432     /// constant representing a type size, alignment, or field offset in
00433     /// a target-independent manner, and hasn't happened to have been
00434     /// folded with other operations into something unrecognizable. This
00435     /// is mainly only useful for pretty-printing and other situations
00436     /// where it isn't absolutely required for these to succeed.
00437     bool isSizeOf(Type *&AllocTy) const;
00438     bool isAlignOf(Type *&AllocTy) const;
00439     bool isOffsetOf(Type *&STy, Constant *&FieldNo) const;
00440 
00441     Type *getType() const { return getValPtr()->getType(); }
00442 
00443     /// Methods for support type inquiry through isa, cast, and dyn_cast:
00444     static inline bool classof(const SCEV *S) {
00445       return S->getSCEVType() == scUnknown;
00446     }
00447   };
00448 
00449   /// SCEVVisitor - This class defines a simple visitor class that may be used
00450   /// for various SCEV analysis purposes.
00451   template<typename SC, typename RetVal=void>
00452   struct SCEVVisitor {
00453     RetVal visit(const SCEV *S) {
00454       switch (S->getSCEVType()) {
00455       case scConstant:
00456         return ((SC*)this)->visitConstant((const SCEVConstant*)S);
00457       case scTruncate:
00458         return ((SC*)this)->visitTruncateExpr((const SCEVTruncateExpr*)S);
00459       case scZeroExtend:
00460         return ((SC*)this)->visitZeroExtendExpr((const SCEVZeroExtendExpr*)S);
00461       case scSignExtend:
00462         return ((SC*)this)->visitSignExtendExpr((const SCEVSignExtendExpr*)S);
00463       case scAddExpr:
00464         return ((SC*)this)->visitAddExpr((const SCEVAddExpr*)S);
00465       case scMulExpr:
00466         return ((SC*)this)->visitMulExpr((const SCEVMulExpr*)S);
00467       case scUDivExpr:
00468         return ((SC*)this)->visitUDivExpr((const SCEVUDivExpr*)S);
00469       case scAddRecExpr:
00470         return ((SC*)this)->visitAddRecExpr((const SCEVAddRecExpr*)S);
00471       case scSMaxExpr:
00472         return ((SC*)this)->visitSMaxExpr((const SCEVSMaxExpr*)S);
00473       case scUMaxExpr:
00474         return ((SC*)this)->visitUMaxExpr((const SCEVUMaxExpr*)S);
00475       case scUnknown:
00476         return ((SC*)this)->visitUnknown((const SCEVUnknown*)S);
00477       case scCouldNotCompute:
00478         return ((SC*)this)->visitCouldNotCompute((const SCEVCouldNotCompute*)S);
00479       default:
00480         llvm_unreachable("Unknown SCEV type!");
00481       }
00482     }
00483 
00484     RetVal visitCouldNotCompute(const SCEVCouldNotCompute *S) {
00485       llvm_unreachable("Invalid use of SCEVCouldNotCompute!");
00486     }
00487   };
00488 
00489   /// Visit all nodes in the expression tree using worklist traversal.
00490   ///
00491   /// Visitor implements:
00492   ///   // return true to follow this node.
00493   ///   bool follow(const SCEV *S);
00494   ///   // return true to terminate the search.
00495   ///   bool isDone();
00496   template<typename SV>
00497   class SCEVTraversal {
00498     SV &Visitor;
00499     SmallVector<const SCEV *, 8> Worklist;
00500     SmallPtrSet<const SCEV *, 8> Visited;
00501 
00502     void push(const SCEV *S) {
00503       if (Visited.insert(S).second && Visitor.follow(S))
00504         Worklist.push_back(S);
00505     }
00506   public:
00507     SCEVTraversal(SV& V): Visitor(V) {}
00508 
00509     void visitAll(const SCEV *Root) {
00510       push(Root);
00511       while (!Worklist.empty() && !Visitor.isDone()) {
00512         const SCEV *S = Worklist.pop_back_val();
00513 
00514         switch (S->getSCEVType()) {
00515         case scConstant:
00516         case scUnknown:
00517           break;
00518         case scTruncate:
00519         case scZeroExtend:
00520         case scSignExtend:
00521           push(cast<SCEVCastExpr>(S)->getOperand());
00522           break;
00523         case scAddExpr:
00524         case scMulExpr:
00525         case scSMaxExpr:
00526         case scUMaxExpr:
00527         case scAddRecExpr:
00528     for (const auto *Op : cast<SCEVNAryExpr>(S)->operands())
00529       push(Op);
00530           break;
00531         case scUDivExpr: {
00532           const SCEVUDivExpr *UDiv = cast<SCEVUDivExpr>(S);
00533           push(UDiv->getLHS());
00534           push(UDiv->getRHS());
00535           break;
00536         }
00537         case scCouldNotCompute:
00538           llvm_unreachable("Attempt to use a SCEVCouldNotCompute object!");
00539         default:
00540           llvm_unreachable("Unknown SCEV kind!");
00541         }
00542       }
00543     }
00544   };
00545 
00546   /// Use SCEVTraversal to visit all nodes in the given expression tree.
00547   template<typename SV>
00548   void visitAll(const SCEV *Root, SV& Visitor) {
00549     SCEVTraversal<SV> T(Visitor);
00550     T.visitAll(Root);
00551   }
00552 
00553   /// Recursively visits a SCEV expression and re-writes it.
00554   template<typename SC>
00555   class SCEVRewriteVisitor : public SCEVVisitor<SC, const SCEV *> {
00556   protected:
00557     ScalarEvolution &SE;
00558   public:
00559     SCEVRewriteVisitor(ScalarEvolution &SE) : SE(SE) {}
00560 
00561     const SCEV *visitConstant(const SCEVConstant *Constant) {
00562       return Constant;
00563     }
00564 
00565     const SCEV *visitTruncateExpr(const SCEVTruncateExpr *Expr) {
00566       const SCEV *Operand = ((SC*)this)->visit(Expr->getOperand());
00567       return SE.getTruncateExpr(Operand, Expr->getType());
00568     }
00569 
00570     const SCEV *visitZeroExtendExpr(const SCEVZeroExtendExpr *Expr) {
00571       const SCEV *Operand = ((SC*)this)->visit(Expr->getOperand());
00572       return SE.getZeroExtendExpr(Operand, Expr->getType());
00573     }
00574 
00575     const SCEV *visitSignExtendExpr(const SCEVSignExtendExpr *Expr) {
00576       const SCEV *Operand = ((SC*)this)->visit(Expr->getOperand());
00577       return SE.getSignExtendExpr(Operand, Expr->getType());
00578     }
00579 
00580     const SCEV *visitAddExpr(const SCEVAddExpr *Expr) {
00581       SmallVector<const SCEV *, 2> Operands;
00582       for (int i = 0, e = Expr->getNumOperands(); i < e; ++i)
00583         Operands.push_back(((SC*)this)->visit(Expr->getOperand(i)));
00584       return SE.getAddExpr(Operands);
00585     }
00586 
00587     const SCEV *visitMulExpr(const SCEVMulExpr *Expr) {
00588       SmallVector<const SCEV *, 2> Operands;
00589       for (int i = 0, e = Expr->getNumOperands(); i < e; ++i)
00590         Operands.push_back(((SC*)this)->visit(Expr->getOperand(i)));
00591       return SE.getMulExpr(Operands);
00592     }
00593 
00594     const SCEV *visitUDivExpr(const SCEVUDivExpr *Expr) {
00595       return SE.getUDivExpr(((SC*)this)->visit(Expr->getLHS()),
00596                             ((SC*)this)->visit(Expr->getRHS()));
00597     }
00598 
00599     const SCEV *visitAddRecExpr(const SCEVAddRecExpr *Expr) {
00600       SmallVector<const SCEV *, 2> Operands;
00601       for (int i = 0, e = Expr->getNumOperands(); i < e; ++i)
00602         Operands.push_back(((SC*)this)->visit(Expr->getOperand(i)));
00603       return SE.getAddRecExpr(Operands, Expr->getLoop(),
00604                               Expr->getNoWrapFlags());
00605     }
00606 
00607     const SCEV *visitSMaxExpr(const SCEVSMaxExpr *Expr) {
00608       SmallVector<const SCEV *, 2> Operands;
00609       for (int i = 0, e = Expr->getNumOperands(); i < e; ++i)
00610         Operands.push_back(((SC*)this)->visit(Expr->getOperand(i)));
00611       return SE.getSMaxExpr(Operands);
00612     }
00613 
00614     const SCEV *visitUMaxExpr(const SCEVUMaxExpr *Expr) {
00615       SmallVector<const SCEV *, 2> Operands;
00616       for (int i = 0, e = Expr->getNumOperands(); i < e; ++i)
00617         Operands.push_back(((SC*)this)->visit(Expr->getOperand(i)));
00618       return SE.getUMaxExpr(Operands);
00619     }
00620 
00621     const SCEV *visitUnknown(const SCEVUnknown *Expr) {
00622       return Expr;
00623     }
00624 
00625     const SCEV *visitCouldNotCompute(const SCEVCouldNotCompute *Expr) {
00626       return Expr;
00627     }
00628   };
00629 
00630   typedef DenseMap<const Value*, Value*> ValueToValueMap;
00631 
00632   /// The SCEVParameterRewriter takes a scalar evolution expression and updates
00633   /// the SCEVUnknown components following the Map (Value -> Value).
00634   class SCEVParameterRewriter : public SCEVRewriteVisitor<SCEVParameterRewriter> {
00635   public:
00636     static const SCEV *rewrite(const SCEV *Scev, ScalarEvolution &SE,
00637                                ValueToValueMap &Map,
00638                                bool InterpretConsts = false) {
00639       SCEVParameterRewriter Rewriter(SE, Map, InterpretConsts);
00640       return Rewriter.visit(Scev);
00641     }
00642 
00643     SCEVParameterRewriter(ScalarEvolution &SE, ValueToValueMap &M, bool C)
00644       : SCEVRewriteVisitor(SE), Map(M), InterpretConsts(C) {}
00645 
00646     const SCEV *visitUnknown(const SCEVUnknown *Expr) {
00647       Value *V = Expr->getValue();
00648       if (Map.count(V)) {
00649         Value *NV = Map[V];
00650         if (InterpretConsts && isa<ConstantInt>(NV))
00651           return SE.getConstant(cast<ConstantInt>(NV));
00652         return SE.getUnknown(NV);
00653       }
00654       return Expr;
00655     }
00656 
00657   private:
00658     ValueToValueMap &Map;
00659     bool InterpretConsts;
00660   };
00661 
00662   typedef DenseMap<const Loop*, const SCEV*> LoopToScevMapT;
00663 
00664   /// The SCEVLoopAddRecRewriter takes a scalar evolution expression and applies
00665   /// the Map (Loop -> SCEV) to all AddRecExprs.
00666   class SCEVLoopAddRecRewriter
00667       : public SCEVRewriteVisitor<SCEVLoopAddRecRewriter> {
00668   public:
00669     static const SCEV *rewrite(const SCEV *Scev, LoopToScevMapT &Map,
00670                                ScalarEvolution &SE) {
00671       SCEVLoopAddRecRewriter Rewriter(SE, Map);
00672       return Rewriter.visit(Scev);
00673     }
00674 
00675     SCEVLoopAddRecRewriter(ScalarEvolution &SE, LoopToScevMapT &M)
00676         : SCEVRewriteVisitor(SE), Map(M) {}
00677 
00678     const SCEV *visitAddRecExpr(const SCEVAddRecExpr *Expr) {
00679       SmallVector<const SCEV *, 2> Operands;
00680       for (int i = 0, e = Expr->getNumOperands(); i < e; ++i)
00681         Operands.push_back(visit(Expr->getOperand(i)));
00682 
00683       const Loop *L = Expr->getLoop();
00684       const SCEV *Res = SE.getAddRecExpr(Operands, L, Expr->getNoWrapFlags());
00685 
00686       if (0 == Map.count(L))
00687         return Res;
00688 
00689       const SCEVAddRecExpr *Rec = cast<SCEVAddRecExpr>(Res);
00690       return Rec->evaluateAtIteration(Map[L], SE);
00691     }
00692 
00693   private:
00694     LoopToScevMapT &Map;
00695   };
00696 
00697 /// Applies the Map (Loop -> SCEV) to the given Scev.
00698 static inline const SCEV *apply(const SCEV *Scev, LoopToScevMapT &Map,
00699                                 ScalarEvolution &SE) {
00700   return SCEVLoopAddRecRewriter::rewrite(Scev, Map, SE);
00701 }
00702 
00703 }
00704 
00705 #endif