X-Git-Url: http://plrg.eecs.uci.edu/git/?a=blobdiff_plain;f=include%2Fllvm%2FAnalysis%2FScalarEvolution.h;h=1467ffeecc9cdf4b2d2c71069e6c96469affd108;hb=ed05e3703e07dfeae33acdd3cc5ad07b5f5b86c6;hp=67c9a4d14fe09d187fabb7d1a11c84913422701e;hpb=ed84062812c7b8a82d0e8128a22aa1aa07a14d79;p=oota-llvm.git diff --git a/include/llvm/Analysis/ScalarEvolution.h b/include/llvm/Analysis/ScalarEvolution.h index 67c9a4d14fe..1467ffeecc9 100644 --- a/include/llvm/Analysis/ScalarEvolution.h +++ b/include/llvm/Analysis/ScalarEvolution.h @@ -21,20 +21,21 @@ #ifndef LLVM_ANALYSIS_SCALAREVOLUTION_H #define LLVM_ANALYSIS_SCALAREVOLUTION_H +#include "llvm/ADT/DenseSet.h" +#include "llvm/ADT/FoldingSet.h" +#include "llvm/IR/ConstantRange.h" +#include "llvm/IR/Function.h" +#include "llvm/IR/Instructions.h" +#include "llvm/IR/Operator.h" +#include "llvm/IR/ValueHandle.h" #include "llvm/Pass.h" -#include "llvm/Instructions.h" -#include "llvm/Function.h" -#include "llvm/Operator.h" -#include "llvm/Support/DataTypes.h" -#include "llvm/Support/ValueHandle.h" #include "llvm/Support/Allocator.h" -#include "llvm/Support/ConstantRange.h" -#include "llvm/ADT/FoldingSet.h" -#include "llvm/ADT/DenseSet.h" +#include "llvm/Support/DataTypes.h" #include namespace llvm { class APInt; + class AssumptionTracker; class Constant; class ConstantInt; class DominatorTree; @@ -189,15 +190,16 @@ namespace llvm { /// Convenient NoWrapFlags manipulation that hides enum casts and is /// visible in the ScalarEvolution name space. - static SCEV::NoWrapFlags maskFlags(SCEV::NoWrapFlags Flags, int Mask) { + static SCEV::NoWrapFlags LLVM_ATTRIBUTE_UNUSED_RESULT + maskFlags(SCEV::NoWrapFlags Flags, int Mask) { return (SCEV::NoWrapFlags)(Flags & Mask); } - static SCEV::NoWrapFlags setFlags(SCEV::NoWrapFlags Flags, - SCEV::NoWrapFlags OnFlags) { + static SCEV::NoWrapFlags LLVM_ATTRIBUTE_UNUSED_RESULT + setFlags(SCEV::NoWrapFlags Flags, SCEV::NoWrapFlags OnFlags) { return (SCEV::NoWrapFlags)(Flags | OnFlags); } - static SCEV::NoWrapFlags clearFlags(SCEV::NoWrapFlags Flags, - SCEV::NoWrapFlags OffFlags) { + static SCEV::NoWrapFlags LLVM_ATTRIBUTE_UNUSED_RESULT + clearFlags(SCEV::NoWrapFlags Flags, SCEV::NoWrapFlags OffFlags) { return (SCEV::NoWrapFlags)(Flags & ~OffFlags); } @@ -206,10 +208,10 @@ namespace llvm { /// notified whenever a Value is deleted. class SCEVCallbackVH : public CallbackVH { ScalarEvolution *SE; - virtual void deleted(); - virtual void allUsesReplacedWith(Value *New); + void deleted() override; + void allUsesReplacedWith(Value *New) override; public: - SCEVCallbackVH(Value *V, ScalarEvolution *SE = 0); + SCEVCallbackVH(Value *V, ScalarEvolution *SE = nullptr); }; friend class SCEVCallbackVH; @@ -220,13 +222,16 @@ namespace llvm { /// Function *F; + /// The tracker for @llvm.assume intrinsics in this function. + AssumptionTracker *AT; + /// LI - The loop information for the function we are currently analyzing. /// LoopInfo *LI; - /// TD - The target data information for the target we are targeting. + /// The DataLayout information for the target we are targeting. /// - DataLayout *TD; + const DataLayout *DL; /// TLI - The target library information for the target we are targeting. /// @@ -252,10 +257,10 @@ namespace llvm { /// Mark predicate values currently being processed by isImpliedCond. DenseSet PendingLoopPredicates; - /// ExitLimit - Information about the number of loop iterations for - /// which a loop exit's branch condition evaluates to the not-taken path. - /// This is a temporary pair of exact and max expressions that are - /// eventually summarized in ExitNotTakenInfo and BackedgeTakenInfo. + /// ExitLimit - Information about the number of loop iterations for which a + /// loop exit's branch condition evaluates to the not-taken path. This is a + /// temporary pair of exact and max expressions that are eventually + /// summarized in ExitNotTakenInfo and BackedgeTakenInfo. struct ExitLimit { const SCEV *Exact; const SCEV *Max; @@ -279,7 +284,7 @@ namespace llvm { const SCEV *ExactNotTaken; PointerIntPair NextExit; - ExitNotTakenInfo() : ExitingBlock(0), ExactNotTaken(0) {} + ExitNotTakenInfo() : ExitingBlock(nullptr), ExactNotTaken(nullptr) {} /// isCompleteList - Return true if all loop exits are computable. bool isCompleteList() const { @@ -309,7 +314,7 @@ namespace llvm { const SCEV *Max; public: - BackedgeTakenInfo() : Max(0) {} + BackedgeTakenInfo() : Max(nullptr) {} /// Initialize BackedgeTakenInfo from a list of exact exit counts. BackedgeTakenInfo( @@ -338,6 +343,10 @@ namespace llvm { /// getMax - Get the max backedge taken count for the loop. const SCEV *getMax(ScalarEvolution *SE) const; + /// Return true if any backedge taken count expressions refer to the given + /// subexpression. + bool hasOperand(const SCEV *S, ScalarEvolution *SE) const; + /// clear - Invalidate this result and free associated memory. void clear(); }; @@ -357,18 +366,18 @@ namespace llvm { /// that we attempt to compute getSCEVAtScope information for, which can /// be expensive in extreme cases. DenseMap > ValuesAtScopes; + SmallVector, 2> > ValuesAtScopes; /// LoopDispositions - Memoized computeLoopDisposition results. DenseMap > LoopDispositions; + SmallVector, 2> > LoopDispositions; /// computeLoopDisposition - Compute a LoopDisposition value. LoopDisposition computeLoopDisposition(const SCEV *S, const Loop *L); /// BlockDispositions - Memoized computeBlockDisposition results. DenseMap > BlockDispositions; + SmallVector, 2> > BlockDispositions; /// computeBlockDisposition - Compute a BlockDisposition value. BlockDisposition computeBlockDisposition(const SCEV *S, const BasicBlock *BB); @@ -422,14 +431,6 @@ namespace llvm { /// resolution. void ForgetSymbolicName(Instruction *I, const SCEV *SymName); - /// getBECount - Subtract the end and start values and divide by the step, - /// rounding up, to get the number of times the backedge is executed. Return - /// CouldNotCompute if an intermediate computation overflows. - const SCEV *getBECount(const SCEV *Start, - const SCEV *End, - const SCEV *Step, - bool NoWrap); - /// getBackedgeTakenInfo - Return the BackedgeTakenInfo for the given /// loop, lazily computing new values if the loop hasn't been analyzed /// yet. @@ -449,7 +450,8 @@ namespace llvm { ExitLimit ComputeExitLimitFromCond(const Loop *L, Value *ExitCond, BasicBlock *TBB, - BasicBlock *FBB); + BasicBlock *FBB, + bool IsSubExpr); /// ComputeExitLimitFromICmp - Compute the number of times the backedge of /// the specified loop will execute if its exit condition were a conditional @@ -457,7 +459,15 @@ namespace llvm { ExitLimit ComputeExitLimitFromICmp(const Loop *L, ICmpInst *ExitCond, BasicBlock *TBB, - BasicBlock *FBB); + BasicBlock *FBB, + bool IsSubExpr); + + /// ComputeExitLimitFromSingleExitSwitch - Compute the number of times the + /// backedge of the specified loop will execute if its exit condition were a + /// switch with a single exiting case to ExitingBB. + ExitLimit + ComputeExitLimitFromSingleExitSwitch(const Loop *L, SwitchInst *Switch, + BasicBlock *ExitingBB, bool IsSubExpr); /// ComputeLoadConstantCompareExitLimit - Given an exit condition /// of 'icmp op load X, cst', try to see if we can compute the @@ -479,7 +489,7 @@ namespace llvm { /// HowFarToZero - Return the number of times an exit condition comparing /// the specified value to zero will execute. If not computable, return /// CouldNotCompute. - ExitLimit HowFarToZero(const SCEV *V, const Loop *L); + ExitLimit HowFarToZero(const SCEV *V, const Loop *L, bool IsSubExpr); /// HowFarToNonZero - Return the number of times an exit condition checking /// the specified value for nonzero will execute. If not computable, return @@ -491,7 +501,9 @@ namespace llvm { /// computable, return CouldNotCompute. isSigned specifies whether the /// less-than is signed. ExitLimit HowManyLessThans(const SCEV *LHS, const SCEV *RHS, - const Loop *L, bool isSigned); + const Loop *L, bool isSigned, bool IsSubExpr); + ExitLimit HowManyGreaterThans(const SCEV *LHS, const SCEV *RHS, + const Loop *L, bool isSigned, bool IsSubExpr); /// getPredecessorWithUniqueSuccessorForBB - Return a predecessor of BB /// (which may not be an immediate predecessor) which has exactly one @@ -539,6 +551,10 @@ namespace llvm { /// forgetMemoizedResults - Drop memoized information computed for S. void forgetMemoizedResults(const SCEV *S); + /// Return false iff given SCEV contains a SCEVUnknown with NULL value- + /// pointer. + bool checkValidity(const SCEV *S) const; + public: static char ID; // Pass identification, replacement for typeid ScalarEvolution(); @@ -608,6 +624,7 @@ namespace llvm { return getMulExpr(Ops, Flags); } const SCEV *getUDivExpr(const SCEV *LHS, const SCEV *RHS); + const SCEV *getUDivExactExpr(const SCEV *LHS, const SCEV *RHS); const SCEV *getAddRecExpr(const SCEV *Start, const SCEV *Step, const Loop *L, SCEV::NoWrapFlags Flags); const SCEV *getAddRecExpr(SmallVectorImpl &Operands, @@ -626,21 +643,15 @@ namespace llvm { const SCEV *getUnknown(Value *V); const SCEV *getCouldNotCompute(); - /// getSizeOfExpr - Return an expression for sizeof on the given type. + /// getSizeOfExpr - Return an expression for sizeof AllocTy that is type + /// IntTy /// - const SCEV *getSizeOfExpr(Type *AllocTy); + const SCEV *getSizeOfExpr(Type *IntTy, Type *AllocTy); - /// getAlignOfExpr - Return an expression for alignof on the given type. + /// getOffsetOfExpr - Return an expression for offsetof on the given field + /// with type IntTy /// - const SCEV *getAlignOfExpr(Type *AllocTy); - - /// getOffsetOfExpr - Return an expression for offsetof on the given field. - /// - const SCEV *getOffsetOfExpr(StructType *STy, unsigned FieldNo); - - /// getOffsetOfExpr - Return an expression for offsetof on the given field. - /// - const SCEV *getOffsetOfExpr(Type *CTy, Constant *FieldNo); + const SCEV *getOffsetOfExpr(Type *IntTy, StructType *STy, unsigned FieldNo); /// getNegativeSCEV - Return the SCEV object corresponding to -V. /// @@ -777,7 +788,8 @@ namespace llvm { /// forgetLoop - 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. + /// compute a trip count, or if the loop is deleted. This call is + /// potentially expensive for large loop bodies. void forgetLoop(const Loop *L); /// forgetValue - This method should be called by the client when it has @@ -785,6 +797,13 @@ namespace llvm { /// disconnect it from a def-use chain linking it to a loop. void forgetValue(Value *V); + /// \brief Called when the client has changed the disposition of values in + /// this loop. + /// + /// We don't have a way to invalidate per-loop dispositions. Clear and + /// recompute is simpler. + void forgetLoopDispositions(const Loop *L) { LoopDispositions.clear(); } + /// GetMinTrailingZeros - Determine the minimum number of zero bits that S /// is guaranteed to end in (at every loop iteration). It is, at the same /// time, the minimum number of times S is divisible by 2. For example, @@ -831,7 +850,7 @@ namespace llvm { /// SimplifyICmpOperands - Simplify LHS and RHS in a comparison with /// predicate Pred. Return true iff any changes were made. If the - /// operands are provably equal or inequal, LHS and RHS are set to + /// operands are provably equal or unequal, LHS and RHS are set to /// the same value and Pred is set to either ICMP_EQ or ICMP_NE. /// bool SimplifyICmpOperands(ICmpInst::Predicate &Pred, @@ -869,10 +888,38 @@ namespace llvm { /// indirect operand. bool hasOperand(const SCEV *S, const SCEV *Op) const; - virtual bool runOnFunction(Function &F); - virtual void releaseMemory(); - virtual void getAnalysisUsage(AnalysisUsage &AU) const; - virtual void print(raw_ostream &OS, const Module* = 0) const; + /// Return the size of an element read or written by Inst. + const SCEV *getElementSize(Instruction *Inst); + + /// Compute the array dimensions Sizes from the set of Terms extracted from + /// the memory access function of this SCEVAddRecExpr. + void findArrayDimensions(SmallVectorImpl &Terms, + SmallVectorImpl &Sizes, + const SCEV *ElementSize) const; + + bool runOnFunction(Function &F) override; + void releaseMemory() override; + void getAnalysisUsage(AnalysisUsage &AU) const override; + void print(raw_ostream &OS, const Module* = nullptr) const override; + void verifyAnalysis() const override; + + private: + /// Compute the backedge taken count knowing the interval difference, the + /// stride and presence of the equality in the comparison. + const SCEV *computeBECount(const SCEV *Delta, const SCEV *Stride, + bool Equality); + + /// Verify if an linear IV with positive stride can overflow when in a + /// less-than comparison, knowing the invariant term of the comparison, + /// the stride and the knowledge of NSW/NUW flags on the recurrence. + bool doesIVOverflowOnLT(const SCEV *RHS, const SCEV *Stride, + bool IsSigned, bool NoWrap); + + /// Verify if an linear IV with negative stride can overflow when in a + /// greater-than comparison, knowing the invariant term of the comparison, + /// the stride and the knowledge of NSW/NUW flags on the recurrence. + bool doesIVOverflowOnGT(const SCEV *RHS, const SCEV *Stride, + bool IsSigned, bool NoWrap); private: FoldingSet UniqueSCEVs;