X-Git-Url: http://demsky.eecs.uci.edu/git/?a=blobdiff_plain;f=include%2Fllvm%2FAnalysis%2FScalarEvolution.h;h=c60cea9917dffd898890f1d6990f791833e032ec;hb=ee118f3bc8d3c1baaf4c4ae50b0cff1d2db10d39;hp=26dd4dd5fcf315abd17732aeba4660e382c5072a;hpb=c846d65f992799fb3a3b015020ed815c0b855663;p=oota-llvm.git diff --git a/include/llvm/Analysis/ScalarEvolution.h b/include/llvm/Analysis/ScalarEvolution.h index 26dd4dd5fcf..c60cea9917d 100644 --- a/include/llvm/Analysis/ScalarEvolution.h +++ b/include/llvm/Analysis/ScalarEvolution.h @@ -23,18 +23,19 @@ #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/Support/Allocator.h" -#include "llvm/Support/ConstantRange.h" #include "llvm/Support/DataTypes.h" -#include "llvm/Support/ValueHandle.h" #include namespace llvm { class APInt; + class AssumptionCache; class Constant; class ConstantInt; class DominatorTree; @@ -70,8 +71,8 @@ namespace llvm { unsigned short SubclassData; private: - SCEV(const SCEV &) LLVM_DELETED_FUNCTION; - void operator=(const SCEV &) LLVM_DELETED_FUNCTION; + SCEV(const SCEV &) = delete; + void operator=(const SCEV &) = delete; public: /// NoWrapFlags are bitfield indices into SubclassData. @@ -81,12 +82,13 @@ namespace llvm { /// operator. NSW is a misnomer that we use to mean no signed overflow or /// underflow. /// - /// AddRec expression may have a no-self-wraparound property if the - /// result can never reach the start value. This property is independent of - /// the actual start value and step direction. Self-wraparound is defined - /// purely in terms of the recurrence's loop, step size, and - /// bitwidth. Formally, a recurrence with no self-wraparound satisfies: - /// abs(step) * max-iteration(loop) <= unsigned-max(bitwidth). + /// AddRec expressions may have a no-self-wraparound property if, in + /// the integer domain, abs(step) * max-iteration(loop) <= + /// unsigned-max(bitwidth). This means that the recurrence will never reach + /// its start value if the step is non-zero. Computing the same value on + /// each iteration is not considered wrapping, and recurrences with step = 0 + /// are trivially . is independent of the sign of step and the + /// value the add recurrence starts with. /// /// Note that NUW and NSW are also valid properties of a recurrence, and /// either implies NW. For convenience, NW will be set for a recurrence @@ -128,9 +130,11 @@ namespace llvm { /// purposes. void print(raw_ostream &OS) const; +#if !defined(NDEBUG) || defined(LLVM_ENABLE_DUMP) /// dump - This method is used for debugging. /// void dump() const; +#endif }; // Specialize FoldingSetTrait for SCEV to avoid needing to compute @@ -207,10 +211,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; @@ -221,13 +225,16 @@ namespace llvm { /// Function *F; + /// The tracker for @llvm.assume intrinsics in this function. + AssumptionCache *AC; + /// 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. /// @@ -253,10 +260,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; @@ -280,7 +287,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 { @@ -310,7 +317,7 @@ namespace llvm { const SCEV *Max; public: - BackedgeTakenInfo() : Max(0) {} + BackedgeTakenInfo() : Max(nullptr) {} /// Initialize BackedgeTakenInfo from a list of exact exit counts. BackedgeTakenInfo( @@ -366,14 +373,17 @@ namespace llvm { /// LoopDispositions - Memoized computeLoopDisposition results. DenseMap, 2> > LoopDispositions; + SmallVector, 2>> + LoopDispositions; /// computeLoopDisposition - Compute a LoopDisposition value. LoopDisposition computeLoopDisposition(const SCEV *S, const Loop *L); /// BlockDispositions - Memoized computeBlockDisposition results. - DenseMap, 2> > BlockDispositions; + DenseMap< + const SCEV *, + SmallVector, 2>> + BlockDispositions; /// computeBlockDisposition - Compute a BlockDisposition value. BlockDisposition computeBlockDisposition(const SCEV *S, const BasicBlock *BB); @@ -458,6 +468,13 @@ namespace llvm { 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 /// backedge-taken count. @@ -613,6 +630,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, @@ -730,6 +748,13 @@ namespace llvm { bool isLoopBackedgeGuardedByCond(const Loop *L, ICmpInst::Predicate Pred, const SCEV *LHS, const SCEV *RHS); + /// \brief Returns the maximum trip count of the loop if it is a single-exit + /// loop and we can compute a small maximum for that loop. + /// + /// Implemented in terms of the \c getSmallConstantTripCount overload with + /// the single exiting block passed to it. See that routine for details. + unsigned getSmallConstantTripCount(Loop *L); + /// getSmallConstantTripCount - Returns the maximum trip count of this loop /// as a normal unsigned value. Returns 0 if the trip count is unknown or /// not constant. This "trip count" assumes that control exits via @@ -739,6 +764,14 @@ namespace llvm { /// the loop exits prematurely via another branch. unsigned getSmallConstantTripCount(Loop *L, BasicBlock *ExitingBlock); + /// \brief Returns the largest constant divisor of the trip count of the + /// loop if it is a single-exit loop and we can compute a small maximum for + /// that loop. + /// + /// Implemented in terms of the \c getSmallConstantTripMultiple overload with + /// the single exiting block passed to it. See that routine for details. + unsigned getSmallConstantTripMultiple(Loop *L); + /// getSmallConstantTripMultiple - Returns the largest constant divisor of /// the trip count of this loop as a normal unsigned value, if /// possible. This means that the actual trip count is always a multiple of @@ -776,7 +809,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 @@ -875,11 +909,20 @@ 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; - virtual void verifyAnalysis() 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