X-Git-Url: http://demsky.eecs.uci.edu/git/?a=blobdiff_plain;f=include%2Fllvm%2FAnalysis%2FScalarEvolution.h;h=88002cb77530e8c0e05d042aab31506e277e3da6;hb=7714285efd2a7f4e503f0f600667193e63ee6d08;hp=7404f9c00d96b61f339e40c35196ddf89a7d0b2f;hpb=a1af757e0af9c2fb5ade4b06408e1adfa0425c6c;p=oota-llvm.git diff --git a/include/llvm/Analysis/ScalarEvolution.h b/include/llvm/Analysis/ScalarEvolution.h index 7404f9c00d9..88002cb7753 100644 --- a/include/llvm/Analysis/ScalarEvolution.h +++ b/include/llvm/Analysis/ScalarEvolution.h @@ -24,6 +24,7 @@ #include "llvm/Pass.h" #include "llvm/Analysis/LoopInfo.h" #include "llvm/Support/DataTypes.h" +#include "llvm/Support/ValueHandle.h" #include namespace llvm { @@ -34,8 +35,8 @@ namespace llvm { class ScalarEvolution; class TargetData; - /// SCEV - This class represent an analyzed expression in the program. These - /// are reference counted opaque objects that the client is not allowed to + /// SCEV - This class represents an analyzed expression in the program. These + /// are reference-counted opaque objects that the client is not allowed to /// do much with directly. /// class SCEV { @@ -76,6 +77,10 @@ namespace llvm { /// bool isZero() const; + /// isOne - Return true if the expression is a constant one. + /// + bool isOne() const; + /// replaceSymbolicValuesWithConcrete - If this SCEV internally references /// the symbolic value "Sym", construct and return a new SCEV that produces /// the same value, but which uses the concrete value Conc instead of the @@ -143,10 +148,10 @@ namespace llvm { /// SCEVHandle - This class is used to maintain the SCEV object's refcounts, /// freeing the objects when the last reference is dropped. class SCEVHandle { - SCEV *S; + const SCEV *S; SCEVHandle(); // DO NOT IMPLEMENT public: - SCEVHandle(const SCEV *s) : S(const_cast(s)) { + SCEVHandle(const SCEV *s) : S(s) { assert(S && "Cannot create a handle to a null SCEV!"); S->addRef(); } @@ -155,13 +160,13 @@ namespace llvm { } ~SCEVHandle() { S->dropRef(); } - operator SCEV*() const { return S; } + operator const SCEV*() const { return S; } - SCEV &operator*() const { return *S; } - SCEV *operator->() const { return S; } + const SCEV &operator*() const { return *S; } + const SCEV *operator->() const { return S; } - bool operator==(SCEV *RHS) const { return S == RHS; } - bool operator!=(SCEV *RHS) const { return S != RHS; } + bool operator==(const SCEV *RHS) const { return S == RHS; } + bool operator!=(const SCEV *RHS) const { return S != RHS; } const SCEVHandle &operator=(SCEV *RHS) { if (S != RHS) { @@ -184,7 +189,7 @@ namespace llvm { template struct simplify_type; template<> struct simplify_type { - typedef SCEV* SimpleType; + typedef const SCEV* SimpleType; static SimpleType getSimplifiedValue(const SCEVHandle &Node) { return Node; } @@ -197,6 +202,19 @@ namespace llvm { /// they must ask this class for services. /// class ScalarEvolution : public FunctionPass { + /// SCEVCallbackVH - A CallbackVH to arrange for ScalarEvolution to be + /// notified whenever a Value is deleted. + class SCEVCallbackVH : public CallbackVH { + ScalarEvolution *SE; + virtual void deleted(); + virtual void allUsesReplacedWith(Value *New); + public: + SCEVCallbackVH(Value *V, ScalarEvolution *SE = 0); + }; + + friend class SCEVCallbackVH; + friend class SCEVExpander; + /// F - The function we are analyzing. /// Function *F; @@ -215,7 +233,7 @@ namespace llvm { /// Scalars - This is a cache of the scalars we have analyzed so far. /// - std::map Scalars; + std::map Scalars; /// BackedgeTakenInfo - Information about the backedge-taken count /// of a loop. This currently inclues an exact count and a maximum count. @@ -232,7 +250,7 @@ namespace llvm { /*implicit*/ BackedgeTakenInfo(SCEVHandle exact) : Exact(exact), Max(exact) {} - /*implicit*/ BackedgeTakenInfo(SCEV *exact) : + /*implicit*/ BackedgeTakenInfo(const SCEV *exact) : Exact(exact), Max(exact) {} BackedgeTakenInfo(SCEVHandle exact, SCEVHandle max) : @@ -258,6 +276,11 @@ namespace llvm { /// exit value. std::map ConstantEvolutionLoopExitValue; + /// ValuesAtScopes - This map contains entries for all the instructions + /// that we attempt to compute getSCEVAtScope information for without + /// using SCEV techniques, which can be expensive. + std::map > ValuesAtScopes; + /// createSCEV - We know that there is no SCEV for the specified value. /// Analyze the expression. SCEVHandle createSCEV(Value *V); @@ -266,6 +289,10 @@ namespace llvm { /// SCEVs. SCEVHandle createNodeForPHI(PHINode *PN); + /// createNodeForGEP - Provide the special handling we need to analyze GEP + /// SCEVs. + SCEVHandle createNodeForGEP(User *GEP); + /// ReplaceSymbolicValueWithConcrete - This looks up the computed SCEV value /// for the specified instruction and replaces any references to the /// symbolic value SymName with the specified value. This is used during @@ -302,18 +329,22 @@ namespace llvm { /// HowFarToZero - Return the number of times a backedge comparing the /// specified value to zero will execute. If not computable, return /// UnknownValue. - SCEVHandle HowFarToZero(SCEV *V, const Loop *L); + SCEVHandle HowFarToZero(const SCEV *V, const Loop *L); /// HowFarToNonZero - Return the number of times a backedge checking the /// specified value for nonzero will execute. If not computable, return /// UnknownValue. - SCEVHandle HowFarToNonZero(SCEV *V, const Loop *L); + SCEVHandle HowFarToNonZero(const SCEV *V, const Loop *L); /// HowManyLessThans - Return the number of times a backedge containing the /// specified less-than comparison will execute. If not computable, return /// UnknownValue. isSigned specifies whether the less-than is signed. - BackedgeTakenInfo HowManyLessThans(SCEV *LHS, SCEV *RHS, const Loop *L, - bool isSigned); + BackedgeTakenInfo HowManyLessThans(const SCEV *LHS, const SCEV *RHS, + const Loop *L, bool isSigned); + + /// getLoopPredecessor - If the given loop's header has exactly one unique + /// predecessor outside the loop, return it. Otherwise return null. + BasicBlock *getLoopPredecessor(const Loop *L); /// getPredecessorWithUniqueSuccessorForBB - Return a predecessor of BB /// (which may not be an immediate predecessor) which has exactly one @@ -328,10 +359,10 @@ namespace llvm { Constant *getConstantEvolutionLoopExitValue(PHINode *PN, const APInt& BEs, const Loop *L); - /// getSCEVAtScope - Compute the value of the specified expression within - /// the indicated loop (which may be null to indicate in no loop). If the - /// expression cannot be evaluated, return UnknownValue itself. - SCEVHandle getSCEVAtScope(SCEV *S, const Loop *L); + /// forgetLoopPHIs - Delete the memoized SCEVs associated with the + /// PHI nodes in the given loop. This is used when the trip count of + /// the loop may have changed. + void forgetLoopPHIs(const Loop *L); public: static char ID; // Pass identification, replacement for typeid @@ -424,6 +455,21 @@ namespace llvm { /// extended, it is sign extended. SCEVHandle getTruncateOrSignExtend(const SCEVHandle &V, const Type *Ty); + /// getNoopOrZeroExtend - Return a SCEV corresponding to a conversion of + /// the input value to the specified type. If the type must be extended, + /// it is zero extended. The conversion must not be narrowing. + SCEVHandle getNoopOrZeroExtend(const SCEVHandle &V, const Type *Ty); + + /// getNoopOrSignExtend - Return a SCEV corresponding to a conversion of + /// the input value to the specified type. If the type must be extended, + /// it is sign extended. The conversion must not be narrowing. + SCEVHandle getNoopOrSignExtend(const SCEVHandle &V, const Type *Ty); + + /// getTruncateOrNoop - Return a SCEV corresponding to a conversion of the + /// input value to the specified type. The conversion must not be + /// widening. + SCEVHandle getTruncateOrNoop(const SCEVHandle &V, const Type *Ty); + /// getIntegerSCEV - Given an integer or FP type, create a constant for the /// specified signed integer value and return a SCEV for the constant. SCEVHandle getIntegerSCEV(int Val, const Type *Ty); @@ -444,14 +490,19 @@ namespace llvm { /// This method can be used to compute the exit value for a variable defined /// in a loop by querying what the value will hold in the parent loop. /// - /// If this value is not computable at this scope, a SCEVCouldNotCompute - /// object is returned. + /// In the case that a relevant loop exit value cannot be computed, the + /// original value V is returned. + SCEVHandle getSCEVAtScope(const SCEV *S, const Loop *L); + + /// getSCEVAtScope - This is a convenience function which does + /// getSCEVAtScope(getSCEV(V), L). SCEVHandle getSCEVAtScope(Value *V, const Loop *L); /// isLoopGuardedByCond - Test whether entry to the loop is protected by - /// a conditional between LHS and RHS. + /// a conditional between LHS and RHS. This is used to help avoid max + /// expressions in loop trip counts. bool isLoopGuardedByCond(const Loop *L, ICmpInst::Predicate Pred, - SCEV *LHS, SCEV *RHS); + const SCEV *LHS, const SCEV *RHS); /// getBackedgeTakenCount - If the specified loop has a predictable /// backedge-taken count, return it, otherwise return a SCEVCouldNotCompute @@ -481,11 +532,6 @@ namespace llvm { /// is deleted. void forgetLoopBackedgeTakenCount(const Loop *L); - /// deleteValueFromRecords - This method should be called by the - /// client before it removes a Value from the program, to make sure - /// that no dangling references are left around. - void deleteValueFromRecords(Value *V); - virtual bool runOnFunction(Function &F); virtual void releaseMemory(); virtual void getAnalysisUsage(AnalysisUsage &AU) const;