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 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_SCALAREVOLUTION_EXPRESSIONS_H
00015 #define LLVM_ANALYSIS_SCALAREVOLUTION_EXPRESSIONS_H
00016 
00017 #include "llvm/Analysis/ScalarEvolution.h"
00018 #include "llvm/Support/ErrorHandling.h"
00019 
00020 namespace llvm {
00021   class ConstantInt;
00022   class ConstantRange;
00023   class DominatorTree;
00024 
00025   enum SCEVTypes {
00026     // These should be ordered in terms of increasing complexity to make the
00027     // folders simpler.
00028     scConstant, scTruncate, scZeroExtend, scSignExtend, scAddExpr, scMulExpr,
00029     scUDivExpr, scAddRecExpr, scUMaxExpr, scSMaxExpr,
00030     scFieldOffset, scAllocSize, scUnknown, scCouldNotCompute
00031   };
00032 
00033   //===--------------------------------------------------------------------===//
00034   /// SCEVConstant - This class represents a constant integer value.
00035   ///
00036   class SCEVConstant : public SCEV {
00037     friend class ScalarEvolution;
00038 
00039     ConstantInt *V;
00040     SCEVConstant(const FoldingSetNodeID &ID, ConstantInt *v) :
00041       SCEV(ID, scConstant), V(v) {}
00042   public:
00043     ConstantInt *getValue() const { return V; }
00044 
00045     virtual bool isLoopInvariant(const Loop *L) const {
00046       return true;
00047     }
00048 
00049     virtual bool hasComputableLoopEvolution(const Loop *L) const {
00050       return false;  // Not loop variant
00051     }
00052 
00053     virtual const Type *getType() const;
00054 
00055     virtual bool hasOperand(const SCEV *) const {
00056       return false;
00057     }
00058 
00059     bool dominates(BasicBlock *BB, DominatorTree *DT) const {
00060       return true;
00061     }
00062 
00063     virtual void print(raw_ostream &OS) const;
00064 
00065     /// Methods for support type inquiry through isa, cast, and dyn_cast:
00066     static inline bool classof(const SCEVConstant *S) { return true; }
00067     static inline bool classof(const SCEV *S) {
00068       return S->getSCEVType() == scConstant;
00069     }
00070   };
00071 
00072   //===--------------------------------------------------------------------===//
00073   /// SCEVCastExpr - This is the base class for unary cast operator classes.
00074   ///
00075   class SCEVCastExpr : public SCEV {
00076   protected:
00077     const SCEV *Op;
00078     const Type *Ty;
00079 
00080     SCEVCastExpr(const FoldingSetNodeID &ID,
00081                  unsigned SCEVTy, const SCEV *op, const Type *ty);
00082 
00083   public:
00084     const SCEV *getOperand() const { return Op; }
00085     virtual const Type *getType() const { return Ty; }
00086 
00087     virtual bool isLoopInvariant(const Loop *L) const {
00088       return Op->isLoopInvariant(L);
00089     }
00090 
00091     virtual bool hasComputableLoopEvolution(const Loop *L) const {
00092       return Op->hasComputableLoopEvolution(L);
00093     }
00094 
00095     virtual bool hasOperand(const SCEV *O) const {
00096       return Op == O || Op->hasOperand(O);
00097     }
00098 
00099     virtual bool dominates(BasicBlock *BB, DominatorTree *DT) const;
00100 
00101     /// Methods for support type inquiry through isa, cast, and dyn_cast:
00102     static inline bool classof(const SCEVCastExpr *S) { return true; }
00103     static inline bool classof(const SCEV *S) {
00104       return S->getSCEVType() == scTruncate ||
00105              S->getSCEVType() == scZeroExtend ||
00106              S->getSCEVType() == scSignExtend;
00107     }
00108   };
00109 
00110   //===--------------------------------------------------------------------===//
00111   /// SCEVTruncateExpr - This class represents a truncation of an integer value
00112   /// to a smaller integer value.
00113   ///
00114   class SCEVTruncateExpr : public SCEVCastExpr {
00115     friend class ScalarEvolution;
00116 
00117     SCEVTruncateExpr(const FoldingSetNodeID &ID,
00118                      const SCEV *op, const Type *ty);
00119 
00120   public:
00121     virtual void print(raw_ostream &OS) const;
00122 
00123     /// Methods for support type inquiry through isa, cast, and dyn_cast:
00124     static inline bool classof(const SCEVTruncateExpr *S) { return true; }
00125     static inline bool classof(const SCEV *S) {
00126       return S->getSCEVType() == scTruncate;
00127     }
00128   };
00129 
00130   //===--------------------------------------------------------------------===//
00131   /// SCEVZeroExtendExpr - This class represents a zero extension of a small
00132   /// integer value to a larger integer value.
00133   ///
00134   class SCEVZeroExtendExpr : public SCEVCastExpr {
00135     friend class ScalarEvolution;
00136 
00137     SCEVZeroExtendExpr(const FoldingSetNodeID &ID,
00138                        const SCEV *op, const Type *ty);
00139 
00140   public:
00141     virtual void print(raw_ostream &OS) const;
00142 
00143     /// Methods for support type inquiry through isa, cast, and dyn_cast:
00144     static inline bool classof(const SCEVZeroExtendExpr *S) { return true; }
00145     static inline bool classof(const SCEV *S) {
00146       return S->getSCEVType() == scZeroExtend;
00147     }
00148   };
00149 
00150   //===--------------------------------------------------------------------===//
00151   /// SCEVSignExtendExpr - This class represents a sign extension of a small
00152   /// integer value to a larger integer value.
00153   ///
00154   class SCEVSignExtendExpr : public SCEVCastExpr {
00155     friend class ScalarEvolution;
00156 
00157     SCEVSignExtendExpr(const FoldingSetNodeID &ID,
00158                        const SCEV *op, const Type *ty);
00159 
00160   public:
00161     virtual void print(raw_ostream &OS) const;
00162 
00163     /// Methods for support type inquiry through isa, cast, and dyn_cast:
00164     static inline bool classof(const SCEVSignExtendExpr *S) { return true; }
00165     static inline bool classof(const SCEV *S) {
00166       return S->getSCEVType() == scSignExtend;
00167     }
00168   };
00169 
00170 
00171   //===--------------------------------------------------------------------===//
00172   /// SCEVNAryExpr - This node is a base class providing common
00173   /// functionality for n'ary operators.
00174   ///
00175   class SCEVNAryExpr : public SCEV {
00176   protected:
00177     SmallVector<const SCEV *, 8> Operands;
00178 
00179     SCEVNAryExpr(const FoldingSetNodeID &ID,
00180                  enum SCEVTypes T, const SmallVectorImpl<const SCEV *> &ops)
00181       : SCEV(ID, T), Operands(ops.begin(), ops.end()) {}
00182 
00183   public:
00184     unsigned getNumOperands() const { return (unsigned)Operands.size(); }
00185     const SCEV *getOperand(unsigned i) const {
00186       assert(i < Operands.size() && "Operand index out of range!");
00187       return Operands[i];
00188     }
00189 
00190     const SmallVectorImpl<const SCEV *> &getOperands() const {
00191       return Operands;
00192     }
00193     typedef SmallVectorImpl<const SCEV *>::const_iterator op_iterator;
00194     op_iterator op_begin() const { return Operands.begin(); }
00195     op_iterator op_end() const { return Operands.end(); }
00196 
00197     virtual bool isLoopInvariant(const Loop *L) const {
00198       for (unsigned i = 0, e = getNumOperands(); i != e; ++i)
00199         if (!getOperand(i)->isLoopInvariant(L)) return false;
00200       return true;
00201     }
00202 
00203     // hasComputableLoopEvolution - N-ary expressions have computable loop
00204     // evolutions iff they have at least one operand that varies with the loop,
00205     // but that all varying operands are computable.
00206     virtual bool hasComputableLoopEvolution(const Loop *L) const {
00207       bool HasVarying = false;
00208       for (unsigned i = 0, e = getNumOperands(); i != e; ++i)
00209         if (!getOperand(i)->isLoopInvariant(L)) {
00210           if (getOperand(i)->hasComputableLoopEvolution(L))
00211             HasVarying = true;
00212           else
00213             return false;
00214         }
00215       return HasVarying;
00216     }
00217 
00218     virtual bool hasOperand(const SCEV *O) const {
00219       for (unsigned i = 0, e = getNumOperands(); i != e; ++i)
00220         if (O == getOperand(i) || getOperand(i)->hasOperand(O))
00221           return true;
00222       return false;
00223     }
00224 
00225     bool dominates(BasicBlock *BB, DominatorTree *DT) const;
00226 
00227     virtual const Type *getType() const { return getOperand(0)->getType(); }
00228 
00229     /// Methods for support type inquiry through isa, cast, and dyn_cast:
00230     static inline bool classof(const SCEVNAryExpr *S) { return true; }
00231     static inline bool classof(const SCEV *S) {
00232       return S->getSCEVType() == scAddExpr ||
00233              S->getSCEVType() == scMulExpr ||
00234              S->getSCEVType() == scSMaxExpr ||
00235              S->getSCEVType() == scUMaxExpr ||
00236              S->getSCEVType() == scAddRecExpr;
00237     }
00238   };
00239 
00240   //===--------------------------------------------------------------------===//
00241   /// SCEVCommutativeExpr - This node is the base class for n'ary commutative
00242   /// operators.
00243   ///
00244   class SCEVCommutativeExpr : public SCEVNAryExpr {
00245   protected:
00246     SCEVCommutativeExpr(const FoldingSetNodeID &ID,
00247                         enum SCEVTypes T,
00248                         const SmallVectorImpl<const SCEV *> &ops)
00249       : SCEVNAryExpr(ID, T, ops) {}
00250 
00251   public:
00252     virtual const char *getOperationStr() const = 0;
00253 
00254     virtual void print(raw_ostream &OS) const;
00255 
00256     /// Methods for support type inquiry through isa, cast, and dyn_cast:
00257     static inline bool classof(const SCEVCommutativeExpr *S) { return true; }
00258     static inline bool classof(const SCEV *S) {
00259       return S->getSCEVType() == scAddExpr ||
00260              S->getSCEVType() == scMulExpr ||
00261              S->getSCEVType() == scSMaxExpr ||
00262              S->getSCEVType() == scUMaxExpr;
00263     }
00264   };
00265 
00266 
00267   //===--------------------------------------------------------------------===//
00268   /// SCEVAddExpr - This node represents an addition of some number of SCEVs.
00269   ///
00270   class SCEVAddExpr : public SCEVCommutativeExpr {
00271     friend class ScalarEvolution;
00272 
00273     SCEVAddExpr(const FoldingSetNodeID &ID,
00274                 const SmallVectorImpl<const SCEV *> &ops)
00275       : SCEVCommutativeExpr(ID, scAddExpr, ops) {
00276     }
00277 
00278   public:
00279     virtual const char *getOperationStr() const { return " + "; }
00280 
00281     /// Methods for support type inquiry through isa, cast, and dyn_cast:
00282     static inline bool classof(const SCEVAddExpr *S) { return true; }
00283     static inline bool classof(const SCEV *S) {
00284       return S->getSCEVType() == scAddExpr;
00285     }
00286   };
00287 
00288   //===--------------------------------------------------------------------===//
00289   /// SCEVMulExpr - This node represents multiplication of some number of SCEVs.
00290   ///
00291   class SCEVMulExpr : public SCEVCommutativeExpr {
00292     friend class ScalarEvolution;
00293 
00294     SCEVMulExpr(const FoldingSetNodeID &ID,
00295                 const SmallVectorImpl<const SCEV *> &ops)
00296       : SCEVCommutativeExpr(ID, scMulExpr, ops) {
00297     }
00298 
00299   public:
00300     virtual const char *getOperationStr() const { return " * "; }
00301 
00302     /// Methods for support type inquiry through isa, cast, and dyn_cast:
00303     static inline bool classof(const SCEVMulExpr *S) { return true; }
00304     static inline bool classof(const SCEV *S) {
00305       return S->getSCEVType() == scMulExpr;
00306     }
00307   };
00308 
00309 
00310   //===--------------------------------------------------------------------===//
00311   /// SCEVUDivExpr - This class represents a binary unsigned division operation.
00312   ///
00313   class SCEVUDivExpr : public SCEV {
00314     friend class ScalarEvolution;
00315 
00316     const SCEV *LHS;
00317     const SCEV *RHS;
00318     SCEVUDivExpr(const FoldingSetNodeID &ID, const SCEV *lhs, const SCEV *rhs)
00319       : SCEV(ID, scUDivExpr), LHS(lhs), RHS(rhs) {}
00320 
00321   public:
00322     const SCEV *getLHS() const { return LHS; }
00323     const SCEV *getRHS() const { return RHS; }
00324 
00325     virtual bool isLoopInvariant(const Loop *L) const {
00326       return LHS->isLoopInvariant(L) && RHS->isLoopInvariant(L);
00327     }
00328 
00329     virtual bool hasComputableLoopEvolution(const Loop *L) const {
00330       return LHS->hasComputableLoopEvolution(L) &&
00331              RHS->hasComputableLoopEvolution(L);
00332     }
00333 
00334     virtual bool hasOperand(const SCEV *O) const {
00335       return O == LHS || O == RHS || LHS->hasOperand(O) || RHS->hasOperand(O);
00336     }
00337 
00338     bool dominates(BasicBlock *BB, DominatorTree *DT) const;
00339 
00340     virtual const Type *getType() const;
00341 
00342     void print(raw_ostream &OS) const;
00343 
00344     /// Methods for support type inquiry through isa, cast, and dyn_cast:
00345     static inline bool classof(const SCEVUDivExpr *S) { return true; }
00346     static inline bool classof(const SCEV *S) {
00347       return S->getSCEVType() == scUDivExpr;
00348     }
00349   };
00350 
00351 
00352   //===--------------------------------------------------------------------===//
00353   /// SCEVAddRecExpr - This node represents a polynomial recurrence on the trip
00354   /// count of the specified loop.  This is the primary focus of the
00355   /// ScalarEvolution framework; all the other SCEV subclasses are mostly just
00356   /// supporting infrastructure to allow SCEVAddRecExpr expressions to be
00357   /// created and analyzed.
00358   ///
00359   /// All operands of an AddRec are required to be loop invariant.
00360   ///
00361   class SCEVAddRecExpr : public SCEVNAryExpr {
00362     friend class ScalarEvolution;
00363 
00364     const Loop *L;
00365 
00366     SCEVAddRecExpr(const FoldingSetNodeID &ID,
00367                    const SmallVectorImpl<const SCEV *> &ops, const Loop *l)
00368       : SCEVNAryExpr(ID, scAddRecExpr, ops), L(l) {
00369       for (size_t i = 0, e = Operands.size(); i != e; ++i)
00370         assert(Operands[i]->isLoopInvariant(l) &&
00371                "Operands of AddRec must be loop-invariant!");
00372     }
00373 
00374   public:
00375     const SCEV *getStart() const { return Operands[0]; }
00376     const Loop *getLoop() const { return L; }
00377 
00378     /// getStepRecurrence - This method constructs and returns the recurrence
00379     /// indicating how much this expression steps by.  If this is a polynomial
00380     /// of degree N, it returns a chrec of degree N-1.
00381     const SCEV *getStepRecurrence(ScalarEvolution &SE) const {
00382       if (isAffine()) return getOperand(1);
00383       return SE.getAddRecExpr(SmallVector<const SCEV *, 3>(op_begin()+1,
00384                                                            op_end()),
00385                               getLoop());
00386     }
00387 
00388     virtual bool hasComputableLoopEvolution(const Loop *QL) const {
00389       if (L == QL) return true;
00390       return false;
00391     }
00392 
00393     virtual bool isLoopInvariant(const Loop *QueryLoop) const;
00394 
00395     /// isAffine - Return true if this is an affine AddRec (i.e., it represents
00396     /// an expressions A+B*x where A and B are loop invariant values.
00397     bool isAffine() const {
00398       // We know that the start value is invariant.  This expression is thus
00399       // affine iff the step is also invariant.
00400       return getNumOperands() == 2;
00401     }
00402 
00403     /// isQuadratic - Return true if this is an quadratic AddRec (i.e., it
00404     /// represents an expressions A+B*x+C*x^2 where A, B and C are loop
00405     /// invariant values.  This corresponds to an addrec of the form {L,+,M,+,N}
00406     bool isQuadratic() const {
00407       return getNumOperands() == 3;
00408     }
00409 
00410     /// evaluateAtIteration - Return the value of this chain of recurrences at
00411     /// the specified iteration number.
00412     const SCEV *evaluateAtIteration(const SCEV *It, ScalarEvolution &SE) const;
00413 
00414     /// getNumIterationsInRange - Return the number of iterations of this loop
00415     /// that produce values in the specified constant range.  Another way of
00416     /// looking at this is that it returns the first iteration number where the
00417     /// value is not in the condition, thus computing the exit count.  If the
00418     /// iteration count can't be computed, an instance of SCEVCouldNotCompute is
00419     /// returned.
00420     const SCEV *getNumIterationsInRange(ConstantRange Range,
00421                                        ScalarEvolution &SE) const;
00422 
00423     /// getPostIncExpr - Return an expression representing the value of
00424     /// this expression one iteration of the loop ahead.
00425     const SCEVAddRecExpr *getPostIncExpr(ScalarEvolution &SE) const {
00426       return cast<SCEVAddRecExpr>(SE.getAddExpr(this, getStepRecurrence(SE)));
00427     }
00428 
00429     bool hasNoUnsignedWrap() const { return SubclassData & (1 << 0); }
00430     void setHasNoUnsignedWrap(bool B) {
00431       SubclassData = (SubclassData & ~(1 << 0)) | (B << 0);
00432     }
00433     bool hasNoSignedWrap() const { return SubclassData & (1 << 1); }
00434     void setHasNoSignedWrap(bool B) {
00435       SubclassData = (SubclassData & ~(1 << 1)) | (B << 1);
00436     }
00437 
00438     virtual void print(raw_ostream &OS) const;
00439 
00440     /// Methods for support type inquiry through isa, cast, and dyn_cast:
00441     static inline bool classof(const SCEVAddRecExpr *S) { return true; }
00442     static inline bool classof(const SCEV *S) {
00443       return S->getSCEVType() == scAddRecExpr;
00444     }
00445   };
00446 
00447 
00448   //===--------------------------------------------------------------------===//
00449   /// SCEVSMaxExpr - This class represents a signed maximum selection.
00450   ///
00451   class SCEVSMaxExpr : public SCEVCommutativeExpr {
00452     friend class ScalarEvolution;
00453 
00454     SCEVSMaxExpr(const FoldingSetNodeID &ID,
00455                  const SmallVectorImpl<const SCEV *> &ops)
00456       : SCEVCommutativeExpr(ID, scSMaxExpr, ops) {
00457     }
00458 
00459   public:
00460     virtual const char *getOperationStr() const { return " smax "; }
00461 
00462     /// Methods for support type inquiry through isa, cast, and dyn_cast:
00463     static inline bool classof(const SCEVSMaxExpr *S) { return true; }
00464     static inline bool classof(const SCEV *S) {
00465       return S->getSCEVType() == scSMaxExpr;
00466     }
00467   };
00468 
00469 
00470   //===--------------------------------------------------------------------===//
00471   /// SCEVUMaxExpr - This class represents an unsigned maximum selection.
00472   ///
00473   class SCEVUMaxExpr : public SCEVCommutativeExpr {
00474     friend class ScalarEvolution;
00475 
00476     SCEVUMaxExpr(const FoldingSetNodeID &ID,
00477                  const SmallVectorImpl<const SCEV *> &ops)
00478       : SCEVCommutativeExpr(ID, scUMaxExpr, ops) {
00479     }
00480 
00481   public:
00482     virtual const char *getOperationStr() const { return " umax "; }
00483 
00484     /// Methods for support type inquiry through isa, cast, and dyn_cast:
00485     static inline bool classof(const SCEVUMaxExpr *S) { return true; }
00486     static inline bool classof(const SCEV *S) {
00487       return S->getSCEVType() == scUMaxExpr;
00488     }
00489   };
00490 
00491   //===--------------------------------------------------------------------===//
00492   /// SCEVTargetDataConstant - This node is the base class for representing
00493   /// target-dependent values in a target-independent way.
00494   ///
00495   class SCEVTargetDataConstant : public SCEV {
00496   protected:
00497     const Type *Ty;
00498     SCEVTargetDataConstant(const FoldingSetNodeID &ID, enum SCEVTypes T,
00499                            const Type *ty) :
00500       SCEV(ID, T), Ty(ty) {}
00501 
00502   public:
00503     virtual bool isLoopInvariant(const Loop *) const { return true; }
00504     virtual bool hasComputableLoopEvolution(const Loop *) const {
00505       return false; // not computable
00506     }
00507 
00508     virtual bool hasOperand(const SCEV *) const {
00509       return false;
00510     }
00511 
00512     bool dominates(BasicBlock *, DominatorTree *) const {
00513       return true;
00514     }
00515 
00516     virtual const Type *getType() const { return Ty; }
00517 
00518     /// Methods for support type inquiry through isa, cast, and dyn_cast:
00519     static inline bool classof(const SCEVTargetDataConstant *S) { return true; }
00520     static inline bool classof(const SCEV *S) {
00521       return S->getSCEVType() == scFieldOffset ||
00522              S->getSCEVType() == scAllocSize;
00523     }
00524   };
00525 
00526   //===--------------------------------------------------------------------===//
00527   /// SCEVFieldOffsetExpr - This node represents an offsetof expression.
00528   ///
00529   class SCEVFieldOffsetExpr : public SCEVTargetDataConstant {
00530     friend class ScalarEvolution;
00531 
00532     const StructType *STy;
00533     unsigned FieldNo;
00534     SCEVFieldOffsetExpr(const FoldingSetNodeID &ID, const Type *ty,
00535                         const StructType *sty, unsigned fieldno) :
00536       SCEVTargetDataConstant(ID, scFieldOffset, ty),
00537       STy(sty), FieldNo(fieldno) {}
00538 
00539   public:
00540     const StructType *getStructType() const { return STy; }
00541     unsigned getFieldNo() const { return FieldNo; }
00542 
00543     virtual void print(raw_ostream &OS) const;
00544 
00545     /// Methods for support type inquiry through isa, cast, and dyn_cast:
00546     static inline bool classof(const SCEVFieldOffsetExpr *S) { return true; }
00547     static inline bool classof(const SCEV *S) {
00548       return S->getSCEVType() == scFieldOffset;
00549     }
00550   };
00551 
00552   //===--------------------------------------------------------------------===//
00553   /// SCEVAllocSize - This node represents a sizeof expression.
00554   ///
00555   class SCEVAllocSizeExpr : public SCEVTargetDataConstant {
00556     friend class ScalarEvolution;
00557 
00558     const Type *AllocTy;
00559     SCEVAllocSizeExpr(const FoldingSetNodeID &ID,
00560                       const Type *ty, const Type *allocty) :
00561       SCEVTargetDataConstant(ID, scAllocSize, ty),
00562       AllocTy(allocty) {}
00563 
00564   public:
00565     const Type *getAllocType() const { return AllocTy; }
00566 
00567     virtual void print(raw_ostream &OS) const;
00568 
00569     /// Methods for support type inquiry through isa, cast, and dyn_cast:
00570     static inline bool classof(const SCEVAllocSizeExpr *S) { return true; }
00571     static inline bool classof(const SCEV *S) {
00572       return S->getSCEVType() == scAllocSize;
00573     }
00574   };
00575 
00576   //===--------------------------------------------------------------------===//
00577   /// SCEVUnknown - This means that we are dealing with an entirely unknown SCEV
00578   /// value, and only represent it as it's LLVM Value.  This is the "bottom"
00579   /// value for the analysis.
00580   ///
00581   class SCEVUnknown : public SCEV {
00582     friend class ScalarEvolution;
00583 
00584     Value *V;
00585     SCEVUnknown(const FoldingSetNodeID &ID, Value *v) :
00586       SCEV(ID, scUnknown), V(v) {}
00587 
00588   public:
00589     Value *getValue() const { return V; }
00590 
00591     virtual bool isLoopInvariant(const Loop *L) const;
00592     virtual bool hasComputableLoopEvolution(const Loop *QL) const {
00593       return false; // not computable
00594     }
00595 
00596     virtual bool hasOperand(const SCEV *) const {
00597       return false;
00598     }
00599 
00600     bool dominates(BasicBlock *BB, DominatorTree *DT) const;
00601 
00602     virtual const Type *getType() const;
00603 
00604     virtual void print(raw_ostream &OS) const;
00605 
00606     /// Methods for support type inquiry through isa, cast, and dyn_cast:
00607     static inline bool classof(const SCEVUnknown *S) { return true; }
00608     static inline bool classof(const SCEV *S) {
00609       return S->getSCEVType() == scUnknown;
00610     }
00611   };
00612 
00613   /// SCEVVisitor - This class defines a simple visitor class that may be used
00614   /// for various SCEV analysis purposes.
00615   template<typename SC, typename RetVal=void>
00616   struct SCEVVisitor {
00617     RetVal visit(const SCEV *S) {
00618       switch (S->getSCEVType()) {
00619       case scConstant:
00620         return ((SC*)this)->visitConstant((const SCEVConstant*)S);
00621       case scTruncate:
00622         return ((SC*)this)->visitTruncateExpr((const SCEVTruncateExpr*)S);
00623       case scZeroExtend:
00624         return ((SC*)this)->visitZeroExtendExpr((const SCEVZeroExtendExpr*)S);
00625       case scSignExtend:
00626         return ((SC*)this)->visitSignExtendExpr((const SCEVSignExtendExpr*)S);
00627       case scAddExpr:
00628         return ((SC*)this)->visitAddExpr((const SCEVAddExpr*)S);
00629       case scMulExpr:
00630         return ((SC*)this)->visitMulExpr((const SCEVMulExpr*)S);
00631       case scUDivExpr:
00632         return ((SC*)this)->visitUDivExpr((const SCEVUDivExpr*)S);
00633       case scAddRecExpr:
00634         return ((SC*)this)->visitAddRecExpr((const SCEVAddRecExpr*)S);
00635       case scSMaxExpr:
00636         return ((SC*)this)->visitSMaxExpr((const SCEVSMaxExpr*)S);
00637       case scUMaxExpr:
00638         return ((SC*)this)->visitUMaxExpr((const SCEVUMaxExpr*)S);
00639       case scFieldOffset:
00640         return ((SC*)this)->visitFieldOffsetExpr((const SCEVFieldOffsetExpr*)S);
00641       case scAllocSize:
00642         return ((SC*)this)->visitAllocSizeExpr((const SCEVAllocSizeExpr*)S);
00643       case scUnknown:
00644         return ((SC*)this)->visitUnknown((const SCEVUnknown*)S);
00645       case scCouldNotCompute:
00646         return ((SC*)this)->visitCouldNotCompute((const SCEVCouldNotCompute*)S);
00647       default:
00648         llvm_unreachable("Unknown SCEV type!");
00649       }
00650     }
00651 
00652     RetVal visitCouldNotCompute(const SCEVCouldNotCompute *S) {
00653       llvm_unreachable("Invalid use of SCEVCouldNotCompute!");
00654       return RetVal();
00655     }
00656   };
00657 }
00658 
00659 #endif