X-Git-Url: http://demsky.eecs.uci.edu/git/?a=blobdiff_plain;f=include%2Fllvm%2FAnalysis%2FScalarEvolution.h;h=88002cb77530e8c0e05d042aab31506e277e3da6;hb=7714285efd2a7f4e503f0f600667193e63ee6d08;hp=a52f273b2c716f90b66777ec2dd89818c41f7c77;hpb=019b92a70c11319f5ab96c9f5e66e4e111a972f8;p=oota-llvm.git diff --git a/include/llvm/Analysis/ScalarEvolution.h b/include/llvm/Analysis/ScalarEvolution.h index a52f273b2c7..88002cb7753 100644 --- a/include/llvm/Analysis/ScalarEvolution.h +++ b/include/llvm/Analysis/ScalarEvolution.h @@ -2,8 +2,8 @@ // // The LLVM Compiler Infrastructure // -// This file was developed by the LLVM research group and is distributed under -// the University of Illinois Open Source License. See LICENSE.TXT for details. +// This file is distributed under the University of Illinois Open Source +// License. See LICENSE.TXT for details. // //===----------------------------------------------------------------------===// // @@ -24,20 +24,19 @@ #include "llvm/Pass.h" #include "llvm/Analysis/LoopInfo.h" #include "llvm/Support/DataTypes.h" -#include "llvm/Support/Streams.h" -#include +#include "llvm/Support/ValueHandle.h" +#include namespace llvm { class APInt; class ConstantInt; - class Instruction; class Type; - class ConstantRange; 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 { @@ -60,10 +59,6 @@ namespace llvm { unsigned getSCEVType() const { return SCEVType; } - /// getValueRange - Return the tightest constant bounds that this value is - /// known to have. This method is only valid on integer SCEV objects. - virtual ConstantRange getValueRange() const; - /// isLoopInvariant - Return true if the value of this SCEV is unchanging in /// the specified loop. virtual bool isLoopInvariant(const Loop *L) const = 0; @@ -78,9 +73,13 @@ 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 @@ -92,10 +91,15 @@ namespace llvm { const SCEVHandle &Conc, ScalarEvolution &SE) const = 0; + /// dominates - Return true if elements that makes up this SCEV dominates + /// the specified basic block. + virtual bool dominates(BasicBlock *BB, DominatorTree *DT) const = 0; + /// 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. @@ -103,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; @@ -115,18 +124,22 @@ 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, ScalarEvolution &SE) const; + virtual bool dominates(BasicBlock *BB, DominatorTree *DT) const { + return true; + } + /// Methods for support type inquiry through isa, cast, and dyn_cast: static inline bool classof(const SCEVCouldNotCompute *S) { return true; } static bool classof(const SCEV *S); @@ -135,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(); } @@ -147,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) { @@ -176,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; } @@ -189,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((intptr_t)&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); @@ -225,7 +415,7 @@ namespace llvm { Ops.push_back(RHS); return getMulExpr(Ops); } - SCEVHandle getSDivExpr(const SCEVHandle &LHS, const SCEVHandle &RHS); + SCEVHandle getUDivExpr(const SCEVHandle &LHS, const SCEVHandle &RHS); SCEVHandle getAddRecExpr(const SCEVHandle &Start, const SCEVHandle &Step, const Loop *L); SCEVHandle getAddRecExpr(std::vector &Operands, @@ -235,17 +425,51 @@ namespace llvm { std::vector NewOp(Operands); return getAddRecExpr(NewOp, L); } + SCEVHandle getSMaxExpr(const SCEVHandle &LHS, const SCEVHandle &RHS); + SCEVHandle getSMaxExpr(std::vector Operands); + 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. /// SCEVHandle getNegativeSCEV(const SCEVHandle &V); + /// getNotSCEV - Return the SCEV object corresponding to ~V. + /// + SCEVHandle getNotSCEV(const SCEVHandle &V); + /// getMinusSCEV - Return LHS-RHS. /// SCEVHandle getMinusSCEV(const SCEVHandle &LHS, const SCEVHandle &RHS); + /// getTruncateOrZeroExtend - 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. + SCEVHandle getTruncateOrZeroExtend(const SCEVHandle &V, const Type *Ty); + + /// getTruncateOrSignExtend - 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. + 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); @@ -266,26 +490,52 @@ 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. This is used to help avoid max + /// expressions in loop trip counts. + bool isLoopGuardedByCond(const Loop *L, ICmpInst::Predicate Pred, + const SCEV *LHS, const SCEV *RHS); + + /// getBackedgeTakenCount - If the specified loop has a predictable + /// backedge-taken count, return it, otherwise return a SCEVCouldNotCompute + /// object. The backedge-taken count is the number of times the loop header + /// will be branched to from within the loop. This is one less than the + /// trip count of the loop, since it doesn't count the first iteration, + /// when the header is branched to from outside the loop. + /// + /// Note that it is not valid to call this method on a loop without a + /// loop-invariant backedge-taken count (see + /// hasLoopInvariantBackedgeTakenCount). + /// + SCEVHandle getBackedgeTakenCount(const Loop *L); - /// getIterationCount - If the specified loop has a predictable iteration - /// count, return it, otherwise return a SCEVCouldNotCompute object. - SCEVHandle getIterationCount(const Loop *L) const; + /// 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); - /// hasLoopInvariantIterationCount - Return true if the specified loop has - /// an analyzable loop-invariant iteration count. - bool hasLoopInvariantIterationCount(const Loop *L) const; + /// hasLoopInvariantBackedgeTakenCount - Return true if the specified loop + /// has an analyzable loop-invariant backedge-taken count. + bool hasLoopInvariantBackedgeTakenCount(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; + /// forgetLoopBackedgeTakenCount - This method should be called by the + /// client when it has changed a loop in a way that may effect + /// ScalarEvolution's ability to compute a trip count, or if the loop + /// is deleted. + void forgetLoopBackedgeTakenCount(const Loop *L); 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);