diff options
Diffstat (limited to 'include/llvm/Analysis/ScalarEvolution.h')
| -rw-r--r-- | include/llvm/Analysis/ScalarEvolution.h | 98 |
1 files changed, 66 insertions, 32 deletions
diff --git a/include/llvm/Analysis/ScalarEvolution.h b/include/llvm/Analysis/ScalarEvolution.h index f394e335257f8..1d1bd67b61ff5 100644 --- a/include/llvm/Analysis/ScalarEvolution.h +++ b/include/llvm/Analysis/ScalarEvolution.h @@ -71,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. @@ -82,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 <NW> 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 <NW> 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 <NW>. <NW> 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 @@ -231,10 +232,6 @@ namespace llvm { /// LoopInfo *LI; - /// The DataLayout information for the target we are targeting. - /// - const DataLayout *DL; - /// TLI - The target library information for the target we are targeting. /// TargetLibraryInfo *TLI; @@ -259,6 +256,10 @@ namespace llvm { /// Mark predicate values currently being processed by isImpliedCond. DenseSet<Value*> PendingLoopPredicates; + /// Set to true by isLoopBackedgeGuardedByCond when we're walking the set of + /// conditions dominating the backedge of a loop. + bool WalkingBEDominatingConds; + /// 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 @@ -372,44 +373,46 @@ namespace llvm { /// LoopDispositions - Memoized computeLoopDisposition results. DenseMap<const SCEV *, - SmallVector<std::pair<const Loop *, LoopDisposition>, 2> > LoopDispositions; + SmallVector<PointerIntPair<const Loop *, 2, LoopDisposition>, 2>> + LoopDispositions; /// computeLoopDisposition - Compute a LoopDisposition value. LoopDisposition computeLoopDisposition(const SCEV *S, const Loop *L); /// BlockDispositions - Memoized computeBlockDisposition results. - DenseMap<const SCEV *, - SmallVector<std::pair<const BasicBlock *, BlockDisposition>, 2> > BlockDispositions; + DenseMap< + const SCEV *, + SmallVector<PointerIntPair<const BasicBlock *, 2, BlockDisposition>, 2>> + BlockDispositions; /// computeBlockDisposition - Compute a BlockDisposition value. BlockDisposition computeBlockDisposition(const SCEV *S, const BasicBlock *BB); - /// UnsignedRanges - Memoized results from getUnsignedRange + /// UnsignedRanges - Memoized results from getRange DenseMap<const SCEV *, ConstantRange> UnsignedRanges; - /// SignedRanges - Memoized results from getSignedRange + /// SignedRanges - Memoized results from getRange DenseMap<const SCEV *, ConstantRange> SignedRanges; - /// setUnsignedRange - Set the memoized unsigned range for the given SCEV. - const ConstantRange &setUnsignedRange(const SCEV *S, - const ConstantRange &CR) { - std::pair<DenseMap<const SCEV *, ConstantRange>::iterator, bool> Pair = - UnsignedRanges.insert(std::make_pair(S, CR)); - if (!Pair.second) - Pair.first->second = CR; - return Pair.first->second; - } + /// RangeSignHint - Used to parameterize getRange + enum RangeSignHint { HINT_RANGE_UNSIGNED, HINT_RANGE_SIGNED }; + + /// setRange - Set the memoized range for the given SCEV. + const ConstantRange &setRange(const SCEV *S, RangeSignHint Hint, + const ConstantRange &CR) { + DenseMap<const SCEV *, ConstantRange> &Cache = + Hint == HINT_RANGE_UNSIGNED ? UnsignedRanges : SignedRanges; - /// setUnsignedRange - Set the memoized signed range for the given SCEV. - const ConstantRange &setSignedRange(const SCEV *S, - const ConstantRange &CR) { std::pair<DenseMap<const SCEV *, ConstantRange>::iterator, bool> Pair = - SignedRanges.insert(std::make_pair(S, CR)); + Cache.insert(std::make_pair(S, CR)); if (!Pair.second) Pair.first->second = CR; return Pair.first->second; } + /// getRange - Determine the range for a particular SCEV. + ConstantRange getRange(const SCEV *S, RangeSignHint Hint); + /// createSCEV - We know that there is no SCEV for the specified value. /// Analyze the expression. const SCEV *createSCEV(Value *V); @@ -536,6 +539,15 @@ namespace llvm { const SCEV *FoundLHS, const SCEV *FoundRHS); + /// isImpliedCondOperandsViaRanges - Test whether the condition described by + /// Pred, LHS, and RHS is true whenever the condition described by Pred, + /// FoundLHS, and FoundRHS is true. Utility function used by + /// isImpliedCondOperands. + bool isImpliedCondOperandsViaRanges(ICmpInst::Predicate Pred, + const SCEV *LHS, const SCEV *RHS, + const SCEV *FoundLHS, + const SCEV *FoundRHS); + /// 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 @@ -557,6 +569,15 @@ namespace llvm { /// pointer. bool checkValidity(const SCEV *S) const; + // Return true if `ExtendOpTy`({`Start`,+,`Step`}) can be proved to be equal + // to {`ExtendOpTy`(`Start`),+,`ExtendOpTy`(`Step`)}. This is equivalent to + // proving no signed (resp. unsigned) wrap in {`Start`,+,`Step`} if + // `ExtendOpTy` is `SCEVSignExtendExpr` (resp. `SCEVZeroExtendExpr`). + // + template<typename ExtendOpTy> + bool proveNoWrapByVaryingStart(const SCEV *Start, const SCEV *Step, + const Loop *L); + public: static char ID; // Pass identification, replacement for typeid ScalarEvolution(); @@ -636,6 +657,15 @@ namespace llvm { SmallVector<const SCEV *, 4> NewOp(Operands.begin(), Operands.end()); return getAddRecExpr(NewOp, L, Flags); } + /// \brief Returns an expression for a GEP + /// + /// \p PointeeType The type used as the basis for the pointer arithmetics + /// \p BaseExpr The expression for the pointer operand. + /// \p IndexExprs The expressions for the indices. + /// \p InBounds Whether the GEP is in bounds. + const SCEV *getGEPExpr(Type *PointeeType, const SCEV *BaseExpr, + const SmallVectorImpl<const SCEV *> &IndexExprs, + bool InBounds = false); const SCEV *getSMaxExpr(const SCEV *LHS, const SCEV *RHS); const SCEV *getSMaxExpr(SmallVectorImpl<const SCEV *> &Operands); const SCEV *getUMaxExpr(const SCEV *LHS, const SCEV *RHS); @@ -830,11 +860,15 @@ namespace llvm { /// getUnsignedRange - Determine the unsigned range for a particular SCEV. /// - ConstantRange getUnsignedRange(const SCEV *S); + ConstantRange getUnsignedRange(const SCEV *S) { + return getRange(S, HINT_RANGE_UNSIGNED); + } /// getSignedRange - Determine the signed range for a particular SCEV. /// - ConstantRange getSignedRange(const SCEV *S); + ConstantRange getSignedRange(const SCEV *S) { + return getRange(S, HINT_RANGE_SIGNED); + } /// isKnownNegative - Test if the given expression is known to be negative. /// |