X-Git-Url: http://demsky.eecs.uci.edu/git/?a=blobdiff_plain;f=include%2Fllvm%2FAnalysis%2FScalarEvolution.h;h=88002cb77530e8c0e05d042aab31506e277e3da6;hb=7714285efd2a7f4e503f0f600667193e63ee6d08;hp=0b148da56f955890873913f2f2c6f067e0d1115e;hpb=46bdfb0e6bb9de86b19562fc52fddefd7014cf73;p=oota-llvm.git diff --git a/include/llvm/Analysis/ScalarEvolution.h b/include/llvm/Analysis/ScalarEvolution.h index 0b148da56f9..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 { @@ -32,9 +33,10 @@ namespace llvm { class Type; class SCEVHandle; 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 { @@ -71,14 +73,14 @@ namespace llvm { /// virtual const Type *getType() const = 0; - /// getBitWidth - Get the bit width of the type, if it has one, 0 otherwise. - /// - uint32_t getBitWidth() const; - /// isZero - Return true if the expression is a constant zero. /// 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 @@ -96,7 +98,8 @@ namespace llvm { /// print - Print out the internal representation of this scalar to the /// specified stream. This should really only be used for debugging /// purposes. - virtual void print(std::ostream &OS) const = 0; + virtual void print(raw_ostream &OS) const = 0; + void print(std::ostream &OS) const; void print(std::ostream *OS) const { if (OS) print(*OS); } /// dump - This method is used for debugging. @@ -104,6 +107,11 @@ namespace llvm { void dump() const; }; + inline raw_ostream &operator<<(raw_ostream &OS, const SCEV &S) { + S.print(OS); + return OS; + } + inline std::ostream &operator<<(std::ostream &OS, const SCEV &S) { S.print(OS); return OS; @@ -116,13 +124,13 @@ namespace llvm { /// marker. struct SCEVCouldNotCompute : public SCEV { SCEVCouldNotCompute(); + ~SCEVCouldNotCompute(); // None of these methods are valid for this object. virtual bool isLoopInvariant(const Loop *L) const; virtual const Type *getType() const; virtual bool hasComputableLoopEvolution(const Loop *L) const; - virtual void print(std::ostream &OS) const; - void print(std::ostream *OS) const { if (OS) print(*OS); } + virtual void print(raw_ostream &OS) const; virtual SCEVHandle replaceSymbolicValuesWithConcrete(const SCEVHandle &Sym, const SCEVHandle &Conc, @@ -140,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(); } @@ -152,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) { @@ -181,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; } @@ -194,14 +202,191 @@ namespace llvm { /// they must ask this class for services. /// class ScalarEvolution : public FunctionPass { - void *Impl; // ScalarEvolution uses the pimpl pattern + /// 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; + + /// LI - The loop information for the function we are currently analyzing. + /// + LoopInfo *LI; + + /// TD - The target data information for the target we are targetting. + /// + TargetData *TD; + + /// UnknownValue - This SCEV is used to represent unknown trip counts and + /// things. + SCEVHandle UnknownValue; + + /// Scalars - This is a cache of the scalars we have analyzed so far. + /// + std::map Scalars; + + /// BackedgeTakenInfo - Information about the backedge-taken count + /// of a loop. This currently inclues an exact count and a maximum count. + /// + struct BackedgeTakenInfo { + /// Exact - An expression indicating the exact backedge-taken count of + /// the loop if it is known, or a SCEVCouldNotCompute otherwise. + SCEVHandle Exact; + + /// Exact - An expression indicating the least maximum backedge-taken + /// count of the loop that is known, or a SCEVCouldNotCompute. + SCEVHandle Max; + + /*implicit*/ BackedgeTakenInfo(SCEVHandle exact) : + Exact(exact), Max(exact) {} + + /*implicit*/ BackedgeTakenInfo(const SCEV *exact) : + Exact(exact), Max(exact) {} + + BackedgeTakenInfo(SCEVHandle exact, SCEVHandle max) : + Exact(exact), Max(max) {} + + /// hasAnyInfo - Test whether this BackedgeTakenInfo contains any + /// computed information, or whether it's all SCEVCouldNotCompute + /// values. + bool hasAnyInfo() const { + return !isa(Exact) || + !isa(Max); + } + }; + + /// BackedgeTakenCounts - Cache the backedge-taken count of the loops for + /// this function as they are computed. + std::map BackedgeTakenCounts; + + /// ConstantEvolutionLoopExitValue - This map contains entries for all of + /// the PHI instructions that we attempt to compute constant evolutions for. + /// This allows us to avoid potentially expensive recomputation of these + /// properties. An instruction maps to null if we are unable to compute its + /// 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); + + /// createNodeForPHI - Provide the special handling we need to analyze PHI + /// 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 + /// PHI resolution. + void ReplaceSymbolicValueWithConcrete(Instruction *I, + const SCEVHandle &SymName, + const SCEVHandle &NewVal); + + /// getBackedgeTakenInfo - Return the BackedgeTakenInfo for the given + /// loop, lazily computing new values if the loop hasn't been analyzed + /// yet. + const BackedgeTakenInfo &getBackedgeTakenInfo(const Loop *L); + + /// ComputeBackedgeTakenCount - Compute the number of times the specified + /// loop will iterate. + BackedgeTakenInfo ComputeBackedgeTakenCount(const Loop *L); + + /// ComputeLoadConstantCompareBackedgeTakenCount - Given an exit condition + /// of 'icmp op load X, cst', try to see if we can compute the trip count. + SCEVHandle + ComputeLoadConstantCompareBackedgeTakenCount(LoadInst *LI, + Constant *RHS, + const Loop *L, + ICmpInst::Predicate p); + + /// ComputeBackedgeTakenCountExhaustively - If the trip is known to execute + /// a constant number of times (the condition evolves only from constants), + /// try to evaluate a few iterations of the loop until we get the exit + /// condition gets a value of ExitWhen (true or false). If we cannot + /// evaluate the trip count of the loop, return UnknownValue. + SCEVHandle ComputeBackedgeTakenCountExhaustively(const Loop *L, Value *Cond, + bool ExitWhen); + + /// HowFarToZero - Return the number of times a backedge comparing the + /// specified value to zero will execute. If not computable, return + /// UnknownValue. + 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(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(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 + /// successor from which BB is reachable, or null if no such block is + /// found. + BasicBlock* getPredecessorWithUniqueSuccessorForBB(BasicBlock *BB); + + /// getConstantEvolutionLoopExitValue - If we know that the specified Phi is + /// in the header of its containing loop, we know the loop executes a + /// constant number of times, and the PHI node is just a recurrence + /// involving constants, fold it. + Constant *getConstantEvolutionLoopExitValue(PHINode *PN, const APInt& BEs, + 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 - ScalarEvolution() : FunctionPass(&ID), Impl(0) {} + ScalarEvolution(); + + /// isSCEVable - Test if values of the given type are analyzable within + /// the SCEV framework. This primarily includes integer types, and it + /// can optionally include pointer types if the ScalarEvolution class + /// has access to target-specific information. + bool isSCEVable(const Type *Ty) const; + + /// getTypeSizeInBits - Return the size in bits of the specified type, + /// for which isSCEVable must return true. + uint64_t getTypeSizeInBits(const Type *Ty) const; + + /// getEffectiveSCEVType - Return a type with the same bitwidth as + /// the given type and which represents how SCEV will treat the given + /// type, for which isSCEVable must return true. For pointer types, + /// this is the pointer-sized integer type. + const Type *getEffectiveSCEVType(const Type *Ty) const; /// getSCEV - Return a SCEV expression handle for the full generality of the /// specified expression. - SCEVHandle getSCEV(Value *V) const; + SCEVHandle getSCEV(Value *V); SCEVHandle getConstant(ConstantInt *V); SCEVHandle getConstant(const APInt& Val); @@ -245,6 +430,7 @@ namespace llvm { SCEVHandle getUMaxExpr(const SCEVHandle &LHS, const SCEVHandle &RHS); SCEVHandle getUMaxExpr(std::vector Operands); SCEVHandle getUnknown(Value *V); + SCEVHandle getCouldNotCompute(); /// getNegativeSCEV - Return the SCEV object corresponding to -V. /// @@ -269,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); @@ -289,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. - SCEVHandle getSCEVAtScope(Value *V, const Loop *L) const; + /// 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 @@ -309,11 +515,16 @@ namespace llvm { /// loop-invariant backedge-taken count (see /// hasLoopInvariantBackedgeTakenCount). /// - SCEVHandle getBackedgeTakenCount(const Loop *L) const; + SCEVHandle getBackedgeTakenCount(const Loop *L); + + /// getMaxBackedgeTakenCount - Similar to getBackedgeTakenCount, except + /// return the least SCEV value that is known never to be less than the + /// actual backedge taken count. + SCEVHandle getMaxBackedgeTakenCount(const Loop *L); /// hasLoopInvariantBackedgeTakenCount - Return true if the specified loop /// has an analyzable loop-invariant backedge-taken count. - bool hasLoopInvariantBackedgeTakenCount(const Loop *L) const; + bool hasLoopInvariantBackedgeTakenCount(const Loop *L); /// forgetLoopBackedgeTakenCount - This method should be called by the /// client when it has changed a loop in a way that may effect @@ -321,14 +532,10 @@ 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) const; - virtual bool runOnFunction(Function &F); virtual void releaseMemory(); virtual void getAnalysisUsage(AnalysisUsage &AU) const; + void print(raw_ostream &OS, const Module* = 0) const; virtual void print(std::ostream &OS, const Module* = 0) const; void print(std::ostream *OS, const Module* M = 0) const { if (OS) print(*OS, M);