Mercurial > hg > Members > tobaru > cbc > CbC_llvm
diff include/llvm/Analysis/ScalarEvolution.h @ 121:803732b1fca8
LLVM 5.0
author | kono |
---|---|
date | Fri, 27 Oct 2017 17:07:41 +0900 (2017-10-27) |
parents | 1172e4bd9c6f |
children |
line wrap: on
line diff
--- a/include/llvm/Analysis/ScalarEvolution.h Fri Nov 25 19:14:25 2016 +0900 +++ b/include/llvm/Analysis/ScalarEvolution.h Fri Oct 27 17:07:41 2017 +0900 @@ -21,11 +21,21 @@ #ifndef LLVM_ANALYSIS_SCALAREVOLUTION_H #define LLVM_ANALYSIS_SCALAREVOLUTION_H -#include "llvm/ADT/DenseSet.h" +#include "llvm/ADT/APInt.h" +#include "llvm/ADT/ArrayRef.h" +#include "llvm/ADT/DenseMap.h" +#include "llvm/ADT/DenseMapInfo.h" #include "llvm/ADT/FoldingSet.h" +#include "llvm/ADT/Hashing.h" +#include "llvm/ADT/Optional.h" +#include "llvm/ADT/PointerIntPair.h" #include "llvm/ADT/SetVector.h" +#include "llvm/ADT/SmallPtrSet.h" +#include "llvm/ADT/SmallVector.h" #include "llvm/Analysis/LoopInfo.h" #include "llvm/IR/ConstantRange.h" +#include "llvm/IR/Function.h" +#include "llvm/IR/InstrTypes.h" #include "llvm/IR/Instructions.h" #include "llvm/IR/Operator.h" #include "llvm/IR/PassManager.h" @@ -33,30 +43,33 @@ #include "llvm/IR/ValueMap.h" #include "llvm/Pass.h" #include "llvm/Support/Allocator.h" -#include "llvm/Support/DataTypes.h" +#include "llvm/Support/Casting.h" +#include "llvm/Support/Compiler.h" +#include <algorithm> +#include <cassert> +#include <cstdint> +#include <memory> +#include <utility> namespace llvm { -class APInt; + class AssumptionCache; +class BasicBlock; class Constant; class ConstantInt; +class DataLayout; class DominatorTree; -class Type; +class GEPOperator; +class Instruction; +class LLVMContext; +class raw_ostream; class ScalarEvolution; -class DataLayout; -class TargetLibraryInfo; -class LLVMContext; -class Operator; -class SCEV; class SCEVAddRecExpr; -class SCEVConstant; -class SCEVExpander; -class SCEVPredicate; class SCEVUnknown; -class Function; - -template <> struct FoldingSetTrait<SCEV>; -template <> struct FoldingSetTrait<SCEVPredicate>; +class StructType; +class TargetLibraryInfo; +class Type; +class Value; /// This class represents an analyzed expression in the program. These are /// opaque objects that the client is not allowed to do much with directly. @@ -74,11 +87,7 @@ protected: /// This field is initialized to zero and may be used in subclasses to store /// miscellaneous information. - unsigned short SubclassData; - -private: - SCEV(const SCEV &) = delete; - void operator=(const SCEV &) = delete; + unsigned short SubclassData = 0; public: /// NoWrapFlags are bitfield indices into SubclassData. @@ -108,24 +117,22 @@ }; explicit SCEV(const FoldingSetNodeIDRef ID, unsigned SCEVTy) - : FastID(ID), SCEVType(SCEVTy), SubclassData(0) {} + : FastID(ID), SCEVType(SCEVTy) {} + SCEV(const SCEV &) = delete; + SCEV &operator=(const SCEV &) = delete; unsigned getSCEVType() const { return SCEVType; } /// Return the LLVM type of this SCEV expression. - /// Type *getType() const; /// Return true if the expression is a constant zero. - /// bool isZero() const; /// Return true if the expression is a constant one. - /// bool isOne() const; /// Return true if the expression is a constant all-ones value. - /// bool isAllOnesValue() const; /// Return true if the specified scev is negated, but not a constant. @@ -136,7 +143,6 @@ void print(raw_ostream &OS) const; /// This method is used for debugging. - /// void dump() const; }; @@ -144,10 +150,12 @@ // temporary FoldingSetNodeID values. template <> struct FoldingSetTrait<SCEV> : DefaultFoldingSetTrait<SCEV> { static void Profile(const SCEV &X, FoldingSetNodeID &ID) { ID = X.FastID; } + static bool Equals(const SCEV &X, const FoldingSetNodeID &ID, unsigned IDHash, FoldingSetNodeID &TempID) { return ID == X.FastID; } + static unsigned ComputeHash(const SCEV &X, FoldingSetNodeID &TempID) { return X.FastID.ComputeHash(); } @@ -221,7 +229,6 @@ // temporary FoldingSetNodeID values. template <> struct FoldingSetTrait<SCEVPredicate> : DefaultFoldingSetTrait<SCEVPredicate> { - static void Profile(const SCEVPredicate &X, FoldingSetNodeID &ID) { ID = X.FastID; } @@ -230,6 +237,7 @@ unsigned IDHash, FoldingSetNodeID &TempID) { return ID == X.FastID; } + static unsigned ComputeHash(const SCEVPredicate &X, FoldingSetNodeID &TempID) { return X.FastID.ComputeHash(); @@ -237,17 +245,15 @@ }; /// This class represents an assumption that two SCEV expressions are equal, -/// and this can be checked at run-time. We assume that the left hand side is -/// a SCEVUnknown and the right hand side a constant. +/// and this can be checked at run-time. class SCEVEqualPredicate final : public SCEVPredicate { - /// We assume that LHS == RHS, where LHS is a SCEVUnknown and RHS a - /// constant. - const SCEVUnknown *LHS; - const SCEVConstant *RHS; + /// We assume that LHS == RHS. + const SCEV *LHS; + const SCEV *RHS; public: - SCEVEqualPredicate(const FoldingSetNodeIDRef ID, const SCEVUnknown *LHS, - const SCEVConstant *RHS); + SCEVEqualPredicate(const FoldingSetNodeIDRef ID, const SCEV *LHS, + const SCEV *RHS); /// Implementation of the SCEVPredicate interface bool implies(const SCEVPredicate *N) const override; @@ -256,13 +262,13 @@ const SCEV *getExpr() const override; /// Returns the left hand side of the equality. - const SCEVUnknown *getLHS() const { return LHS; } + const SCEV *getLHS() const { return LHS; } /// Returns the right hand side of the equality. - const SCEVConstant *getRHS() const { return RHS; } + const SCEV *getRHS() const { return RHS; } /// Methods for support type inquiry through isa, cast, and dyn_cast: - static inline bool classof(const SCEVPredicate *P) { + static bool classof(const SCEVPredicate *P) { return P->getKind() == P_Equal; } }; @@ -353,6 +359,7 @@ /// Returns the set assumed no overflow flags. IncrementWrapFlags getFlags() const { return Flags; } + /// Implementation of the SCEVPredicate interface const SCEV *getExpr() const override; bool implies(const SCEVPredicate *N) const override; @@ -360,7 +367,7 @@ bool isAlwaysTrue() const override; /// Methods for support type inquiry through isa, cast, and dyn_cast: - static inline bool classof(const SCEVPredicate *P) { + static bool classof(const SCEVPredicate *P) { return P->getKind() == P_Wrap; } }; @@ -373,11 +380,12 @@ /// ScalarEvolution::Preds folding set. This is why the \c add function is sound. class SCEVUnionPredicate final : public SCEVPredicate { private: - typedef DenseMap<const SCEV *, SmallVector<const SCEVPredicate *, 4>> - PredicateMap; + using PredicateMap = + DenseMap<const SCEV *, SmallVector<const SCEVPredicate *, 4>>; /// Vector with references to all predicates in this union. SmallVector<const SCEVPredicate *, 16> Preds; + /// Maps SCEVs to predicates for quick look-ups. PredicateMap SCEVToPreds; @@ -406,11 +414,40 @@ unsigned getComplexity() const override { return Preds.size(); } /// Methods for support type inquiry through isa, cast, and dyn_cast: - static inline bool classof(const SCEVPredicate *P) { + static bool classof(const SCEVPredicate *P) { return P->getKind() == P_Union; } }; +struct ExitLimitQuery { + ExitLimitQuery(const Loop *L, BasicBlock *ExitingBlock, bool AllowPredicates) + : L(L), ExitingBlock(ExitingBlock), AllowPredicates(AllowPredicates) {} + + const Loop *L; + BasicBlock *ExitingBlock; + bool AllowPredicates; +}; + +template <> struct DenseMapInfo<ExitLimitQuery> { + static inline ExitLimitQuery getEmptyKey() { + return ExitLimitQuery(nullptr, nullptr, true); + } + + static inline ExitLimitQuery getTombstoneKey() { + return ExitLimitQuery(nullptr, nullptr, false); + } + + static unsigned getHashValue(ExitLimitQuery Val) { + return hash_combine(hash_combine(Val.L, Val.ExitingBlock), + Val.AllowPredicates); + } + + static bool isEqual(ExitLimitQuery LHS, ExitLimitQuery RHS) { + return LHS.L == RHS.L && LHS.ExitingBlock == RHS.ExitingBlock && + LHS.AllowPredicates == RHS.AllowPredicates; + } +}; + /// The main scalar evolution driver. Because client code (intentionally) /// can't do much with the SCEV objects directly, they must ask this class /// for services. @@ -445,11 +482,542 @@ return (SCEV::NoWrapFlags)(Flags & ~OffFlags); } + ScalarEvolution(Function &F, TargetLibraryInfo &TLI, AssumptionCache &AC, + DominatorTree &DT, LoopInfo &LI); + ScalarEvolution(ScalarEvolution &&Arg); + ~ScalarEvolution(); + + LLVMContext &getContext() const { return F.getContext(); } + + /// 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(Type *Ty) const; + + /// Return the size in bits of the specified type, for which isSCEVable must + /// return true. + uint64_t getTypeSizeInBits(Type *Ty) const; + + /// 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. + Type *getEffectiveSCEVType(Type *Ty) const; + + // Returns a wider type among {Ty1, Ty2}. + Type *getWiderType(Type *Ty1, Type *Ty2) const; + + /// Return true if the SCEV is a scAddRecExpr or it contains + /// scAddRecExpr. The result will be cached in HasRecMap. + bool containsAddRecurrence(const SCEV *S); + + /// Erase Value from ValueExprMap and ExprValueMap. + void eraseValueFromMap(Value *V); + + /// Return a SCEV expression for the full generality of the specified + /// expression. + const SCEV *getSCEV(Value *V); + + const SCEV *getConstant(ConstantInt *V); + const SCEV *getConstant(const APInt &Val); + const SCEV *getConstant(Type *Ty, uint64_t V, bool isSigned = false); + const SCEV *getTruncateExpr(const SCEV *Op, Type *Ty); + const SCEV *getZeroExtendExpr(const SCEV *Op, Type *Ty, unsigned Depth = 0); + const SCEV *getSignExtendExpr(const SCEV *Op, Type *Ty, unsigned Depth = 0); + const SCEV *getAnyExtendExpr(const SCEV *Op, Type *Ty); + const SCEV *getAddExpr(SmallVectorImpl<const SCEV *> &Ops, + SCEV::NoWrapFlags Flags = SCEV::FlagAnyWrap, + unsigned Depth = 0); + const SCEV *getAddExpr(const SCEV *LHS, const SCEV *RHS, + SCEV::NoWrapFlags Flags = SCEV::FlagAnyWrap, + unsigned Depth = 0) { + SmallVector<const SCEV *, 2> Ops = {LHS, RHS}; + return getAddExpr(Ops, Flags, Depth); + } + const SCEV *getAddExpr(const SCEV *Op0, const SCEV *Op1, const SCEV *Op2, + SCEV::NoWrapFlags Flags = SCEV::FlagAnyWrap, + unsigned Depth = 0) { + SmallVector<const SCEV *, 3> Ops = {Op0, Op1, Op2}; + return getAddExpr(Ops, Flags, Depth); + } + const SCEV *getMulExpr(SmallVectorImpl<const SCEV *> &Ops, + SCEV::NoWrapFlags Flags = SCEV::FlagAnyWrap, + unsigned Depth = 0); + const SCEV *getMulExpr(const SCEV *LHS, const SCEV *RHS, + SCEV::NoWrapFlags Flags = SCEV::FlagAnyWrap, + unsigned Depth = 0) { + SmallVector<const SCEV *, 2> Ops = {LHS, RHS}; + return getMulExpr(Ops, Flags, Depth); + } + const SCEV *getMulExpr(const SCEV *Op0, const SCEV *Op1, const SCEV *Op2, + SCEV::NoWrapFlags Flags = SCEV::FlagAnyWrap, + unsigned Depth = 0) { + SmallVector<const SCEV *, 3> Ops = {Op0, Op1, Op2}; + return getMulExpr(Ops, Flags, Depth); + } + const SCEV *getUDivExpr(const SCEV *LHS, const SCEV *RHS); + const SCEV *getUDivExactExpr(const SCEV *LHS, const SCEV *RHS); + const SCEV *getURemExpr(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<const SCEV *> &Operands, + const Loop *L, SCEV::NoWrapFlags Flags); + const SCEV *getAddRecExpr(const SmallVectorImpl<const SCEV *> &Operands, + const Loop *L, SCEV::NoWrapFlags Flags) { + SmallVector<const SCEV *, 4> NewOp(Operands.begin(), Operands.end()); + return getAddRecExpr(NewOp, L, Flags); + } + + /// Checks if \p SymbolicPHI can be rewritten as an AddRecExpr under some + /// Predicates. If successful return these <AddRecExpr, Predicates>; + /// The function is intended to be called from PSCEV (the caller will decide + /// whether to actually add the predicates and carry out the rewrites). + Optional<std::pair<const SCEV *, SmallVector<const SCEVPredicate *, 3>>> + createAddRecFromPHIWithCasts(const SCEVUnknown *SymbolicPHI); + + /// Returns an expression for a GEP + /// + /// \p GEP The GEP. The indices contained in the GEP itself are ignored, + /// instead we use IndexExprs. + /// \p IndexExprs The expressions for the indices. + const SCEV *getGEPExpr(GEPOperator *GEP, + const SmallVectorImpl<const SCEV *> &IndexExprs); + 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); + const SCEV *getUMaxExpr(SmallVectorImpl<const SCEV *> &Operands); + const SCEV *getSMinExpr(const SCEV *LHS, const SCEV *RHS); + const SCEV *getUMinExpr(const SCEV *LHS, const SCEV *RHS); + const SCEV *getUnknown(Value *V); + const SCEV *getCouldNotCompute(); + + /// Return a SCEV for the constant 0 of a specific type. + const SCEV *getZero(Type *Ty) { return getConstant(Ty, 0); } + + /// Return a SCEV for the constant 1 of a specific type. + const SCEV *getOne(Type *Ty) { return getConstant(Ty, 1); } + + /// Return an expression for sizeof AllocTy that is type IntTy + const SCEV *getSizeOfExpr(Type *IntTy, Type *AllocTy); + + /// Return an expression for offsetof on the given field with type IntTy + const SCEV *getOffsetOfExpr(Type *IntTy, StructType *STy, unsigned FieldNo); + + /// Return the SCEV object corresponding to -V. + const SCEV *getNegativeSCEV(const SCEV *V, + SCEV::NoWrapFlags Flags = SCEV::FlagAnyWrap); + + /// Return the SCEV object corresponding to ~V. + const SCEV *getNotSCEV(const SCEV *V); + + /// Return LHS-RHS. Minus is represented in SCEV as A+B*-1. + const SCEV *getMinusSCEV(const SCEV *LHS, const SCEV *RHS, + SCEV::NoWrapFlags Flags = SCEV::FlagAnyWrap, + unsigned Depth = 0); + + /// 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. + const SCEV *getTruncateOrZeroExtend(const SCEV *V, Type *Ty); + + /// 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. + const SCEV *getTruncateOrSignExtend(const SCEV *V, Type *Ty); + + /// 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. + const SCEV *getNoopOrZeroExtend(const SCEV *V, Type *Ty); + + /// 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. + const SCEV *getNoopOrSignExtend(const SCEV *V, Type *Ty); + + /// Return a SCEV corresponding to a conversion of the input value to the + /// specified type. If the type must be extended, it is extended with + /// unspecified bits. The conversion must not be narrowing. + const SCEV *getNoopOrAnyExtend(const SCEV *V, Type *Ty); + + /// Return a SCEV corresponding to a conversion of the input value to the + /// specified type. The conversion must not be widening. + const SCEV *getTruncateOrNoop(const SCEV *V, Type *Ty); + + /// Promote the operands to the wider of the types using zero-extension, and + /// then perform a umax operation with them. + const SCEV *getUMaxFromMismatchedTypes(const SCEV *LHS, const SCEV *RHS); + + /// Promote the operands to the wider of the types using zero-extension, and + /// then perform a umin operation with them. + const SCEV *getUMinFromMismatchedTypes(const SCEV *LHS, const SCEV *RHS); + + /// Transitively follow the chain of pointer-type operands until reaching a + /// SCEV that does not have a single pointer operand. This returns a + /// SCEVUnknown pointer for well-formed pointer-type expressions, but corner + /// cases do exist. + const SCEV *getPointerBase(const SCEV *V); + + /// Return a SCEV expression for the specified value at the specified scope + /// in the program. The L value specifies a loop nest to evaluate the + /// expression at, where null is the top-level or a specified loop is + /// immediately inside of the loop. + /// + /// 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. + /// + /// In the case that a relevant loop exit value cannot be computed, the + /// original value V is returned. + const SCEV *getSCEVAtScope(const SCEV *S, const Loop *L); + + /// This is a convenience function which does getSCEVAtScope(getSCEV(V), L). + const SCEV *getSCEVAtScope(Value *V, const Loop *L); + + /// 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, and to eliminate casts. + bool isLoopEntryGuardedByCond(const Loop *L, ICmpInst::Predicate Pred, + const SCEV *LHS, const SCEV *RHS); + + /// Test whether the backedge of the loop is protected by a conditional + /// between LHS and RHS. This is used to to eliminate casts. + bool isLoopBackedgeGuardedByCond(const Loop *L, ICmpInst::Predicate Pred, + const SCEV *LHS, const SCEV *RHS); + + /// 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(const Loop *L); + + /// 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 ExitingBlock. More + /// precisely, it is the number of times that control may reach ExitingBlock + /// before taking the branch. For loops with multiple exits, it may not be + /// the number times that the loop header executes if the loop exits + /// prematurely via another branch. + unsigned getSmallConstantTripCount(const Loop *L, BasicBlock *ExitingBlock); + + /// Returns the upper bound of the loop trip count as a normal unsigned + /// value. + /// Returns 0 if the trip count is unknown or not constant. + unsigned getSmallConstantMaxTripCount(const Loop *L); + + /// 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(const Loop *L); + + /// 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 the returned value (don't forget the trip + /// count could very well be zero as well!). As explained in the comments + /// for getSmallConstantTripCount, this assumes that control exits the loop + /// via ExitingBlock. + unsigned getSmallConstantTripMultiple(const Loop *L, + BasicBlock *ExitingBlock); + + /// Get the expression for the number of loop iterations for which this loop + /// is guaranteed not to exit via ExitingBlock. Otherwise return + /// SCEVCouldNotCompute. + const SCEV *getExitCount(const Loop *L, BasicBlock *ExitingBlock); + + /// 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, assuming there are no abnormal exists like exception throws. 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). + const SCEV *getBackedgeTakenCount(const Loop *L); + + /// Similar to getBackedgeTakenCount, except it will add a set of + /// SCEV predicates to Predicates that are required to be true in order for + /// the answer to be correct. Predicates can be checked with run-time + /// checks and can be used to perform loop versioning. + const SCEV *getPredicatedBackedgeTakenCount(const Loop *L, + SCEVUnionPredicate &Predicates); + + /// When successful, this returns a SCEVConstant that is greater than or equal + /// to (i.e. a "conservative over-approximation") of the value returend by + /// getBackedgeTakenCount. If such a value cannot be computed, it returns the + /// SCEVCouldNotCompute object. + const SCEV *getMaxBackedgeTakenCount(const Loop *L); + + /// Return true if the backedge taken count is either the value returned by + /// getMaxBackedgeTakenCount or zero. + bool isBackedgeTakenCountMaxOrZero(const Loop *L); + + /// Return true if the specified loop has an analyzable loop-invariant + /// backedge-taken count. + bool hasLoopInvariantBackedgeTakenCount(const Loop *L); + + /// 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. This call is potentially expensive for large + /// loop bodies. + void forgetLoop(const Loop *L); + + /// This method should be called by the client when it has changed a value + /// in a way that may effect its value, or which may disconnect it from a + /// def-use chain linking it to a loop. + void forgetValue(Value *V); + + /// 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(); } + + /// 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, given {4,+,8} it returns 2. + /// If S is guaranteed to be 0, it returns the bitwidth of S. + uint32_t GetMinTrailingZeros(const SCEV *S); + + /// Determine the unsigned range for a particular SCEV. + /// NOTE: This returns a copy of the reference returned by getRangeRef. + ConstantRange getUnsignedRange(const SCEV *S) { + return getRangeRef(S, HINT_RANGE_UNSIGNED); + } + + /// Determine the min of the unsigned range for a particular SCEV. + APInt getUnsignedRangeMin(const SCEV *S) { + return getRangeRef(S, HINT_RANGE_UNSIGNED).getUnsignedMin(); + } + + /// Determine the max of the unsigned range for a particular SCEV. + APInt getUnsignedRangeMax(const SCEV *S) { + return getRangeRef(S, HINT_RANGE_UNSIGNED).getUnsignedMax(); + } + + /// Determine the signed range for a particular SCEV. + /// NOTE: This returns a copy of the reference returned by getRangeRef. + ConstantRange getSignedRange(const SCEV *S) { + return getRangeRef(S, HINT_RANGE_SIGNED); + } + + /// Determine the min of the signed range for a particular SCEV. + APInt getSignedRangeMin(const SCEV *S) { + return getRangeRef(S, HINT_RANGE_SIGNED).getSignedMin(); + } + + /// Determine the max of the signed range for a particular SCEV. + APInt getSignedRangeMax(const SCEV *S) { + return getRangeRef(S, HINT_RANGE_SIGNED).getSignedMax(); + } + + /// Test if the given expression is known to be negative. + bool isKnownNegative(const SCEV *S); + + /// Test if the given expression is known to be positive. + bool isKnownPositive(const SCEV *S); + + /// Test if the given expression is known to be non-negative. + bool isKnownNonNegative(const SCEV *S); + + /// Test if the given expression is known to be non-positive. + bool isKnownNonPositive(const SCEV *S); + + /// Test if the given expression is known to be non-zero. + bool isKnownNonZero(const SCEV *S); + + /// Test if the given expression is known to satisfy the condition described + /// by Pred, LHS, and RHS. + bool isKnownPredicate(ICmpInst::Predicate Pred, const SCEV *LHS, + const SCEV *RHS); + + /// Return true if, for all loop invariant X, the predicate "LHS `Pred` X" + /// is monotonically increasing or decreasing. In the former case set + /// `Increasing` to true and in the latter case set `Increasing` to false. + /// + /// A predicate is said to be monotonically increasing if may go from being + /// false to being true as the loop iterates, but never the other way + /// around. A predicate is said to be monotonically decreasing if may go + /// from being true to being false as the loop iterates, but never the other + /// way around. + bool isMonotonicPredicate(const SCEVAddRecExpr *LHS, ICmpInst::Predicate Pred, + bool &Increasing); + + /// Return true if the result of the predicate LHS `Pred` RHS is loop + /// invariant with respect to L. Set InvariantPred, InvariantLHS and + /// InvariantLHS so that InvariantLHS `InvariantPred` InvariantRHS is the + /// loop invariant form of LHS `Pred` RHS. + bool isLoopInvariantPredicate(ICmpInst::Predicate Pred, const SCEV *LHS, + const SCEV *RHS, const Loop *L, + ICmpInst::Predicate &InvariantPred, + const SCEV *&InvariantLHS, + const SCEV *&InvariantRHS); + + /// Simplify LHS and RHS in a comparison with predicate Pred. Return true + /// iff any changes were made. If the 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, const SCEV *&LHS, + const SCEV *&RHS, unsigned Depth = 0); + + /// Return the "disposition" of the given SCEV with respect to the given + /// loop. + LoopDisposition getLoopDisposition(const SCEV *S, const Loop *L); + + /// Return true if the value of the given SCEV is unchanging in the + /// specified loop. + bool isLoopInvariant(const SCEV *S, const Loop *L); + + /// Determine if the SCEV can be evaluated at loop's entry. It is true if it + /// doesn't depend on a SCEVUnknown of an instruction which is dominated by + /// the header of loop L. + bool isAvailableAtLoopEntry(const SCEV *S, const Loop *L); + + /// Return true if the given SCEV changes value in a known way in the + /// specified loop. This property being true implies that the value is + /// variant in the loop AND that we can emit an expression to compute the + /// value of the expression at any particular loop iteration. + bool hasComputableLoopEvolution(const SCEV *S, const Loop *L); + + /// Return the "disposition" of the given SCEV with respect to the given + /// block. + BlockDisposition getBlockDisposition(const SCEV *S, const BasicBlock *BB); + + /// Return true if elements that makes up the given SCEV dominate the + /// specified basic block. + bool dominates(const SCEV *S, const BasicBlock *BB); + + /// Return true if elements that makes up the given SCEV properly dominate + /// the specified basic block. + bool properlyDominates(const SCEV *S, const BasicBlock *BB); + + /// Test whether the given SCEV has Op as a direct or indirect operand. + bool hasOperand(const SCEV *S, const SCEV *Op) 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 (second step of + /// delinearization). + void findArrayDimensions(SmallVectorImpl<const SCEV *> &Terms, + SmallVectorImpl<const SCEV *> &Sizes, + const SCEV *ElementSize); + + void print(raw_ostream &OS) const; + void verify() const; + bool invalidate(Function &F, const PreservedAnalyses &PA, + FunctionAnalysisManager::Invalidator &Inv); + + /// Collect parametric terms occurring in step expressions (first step of + /// delinearization). + void collectParametricTerms(const SCEV *Expr, + SmallVectorImpl<const SCEV *> &Terms); + + /// Return in Subscripts the access functions for each dimension in Sizes + /// (third step of delinearization). + void computeAccessFunctions(const SCEV *Expr, + SmallVectorImpl<const SCEV *> &Subscripts, + SmallVectorImpl<const SCEV *> &Sizes); + + /// Split this SCEVAddRecExpr into two vectors of SCEVs representing the + /// subscripts and sizes of an array access. + /// + /// The delinearization is a 3 step process: the first two steps compute the + /// sizes of each subscript and the third step computes the access functions + /// for the delinearized array: + /// + /// 1. Find the terms in the step functions + /// 2. Compute the array size + /// 3. Compute the access function: divide the SCEV by the array size + /// starting with the innermost dimensions found in step 2. The Quotient + /// is the SCEV to be divided in the next step of the recursion. The + /// Remainder is the subscript of the innermost dimension. Loop over all + /// array dimensions computed in step 2. + /// + /// To compute a uniform array size for several memory accesses to the same + /// object, one can collect in step 1 all the step terms for all the memory + /// accesses, and compute in step 2 a unique array shape. This guarantees + /// that the array shape will be the same across all memory accesses. + /// + /// FIXME: We could derive the result of steps 1 and 2 from a description of + /// the array shape given in metadata. + /// + /// Example: + /// + /// A[][n][m] + /// + /// for i + /// for j + /// for k + /// A[j+k][2i][5i] = + /// + /// The initial SCEV: + /// + /// A[{{{0,+,2*m+5}_i, +, n*m}_j, +, n*m}_k] + /// + /// 1. Find the different terms in the step functions: + /// -> [2*m, 5, n*m, n*m] + /// + /// 2. Compute the array size: sort and unique them + /// -> [n*m, 2*m, 5] + /// find the GCD of all the terms = 1 + /// divide by the GCD and erase constant terms + /// -> [n*m, 2*m] + /// GCD = m + /// divide by GCD -> [n, 2] + /// remove constant terms + /// -> [n] + /// size of the array is A[unknown][n][m] + /// + /// 3. Compute the access function + /// a. Divide {{{0,+,2*m+5}_i, +, n*m}_j, +, n*m}_k by the innermost size m + /// Quotient: {{{0,+,2}_i, +, n}_j, +, n}_k + /// Remainder: {{{0,+,5}_i, +, 0}_j, +, 0}_k + /// The remainder is the subscript of the innermost array dimension: [5i]. + /// + /// b. Divide Quotient: {{{0,+,2}_i, +, n}_j, +, n}_k by next outer size n + /// Quotient: {{{0,+,0}_i, +, 1}_j, +, 1}_k + /// Remainder: {{{0,+,2}_i, +, 0}_j, +, 0}_k + /// The Remainder is the subscript of the next array dimension: [2i]. + /// + /// The subscript of the outermost dimension is the Quotient: [j+k]. + /// + /// Overall, we have: A[][n][m], and the access function: A[j+k][2i][5i]. + void delinearize(const SCEV *Expr, SmallVectorImpl<const SCEV *> &Subscripts, + SmallVectorImpl<const SCEV *> &Sizes, + const SCEV *ElementSize); + + /// Return the DataLayout associated with the module this SCEV instance is + /// operating on. + const DataLayout &getDataLayout() const { + return F.getParent()->getDataLayout(); + } + + const SCEVPredicate *getEqualPredicate(const SCEV *LHS, const SCEV *RHS); + + const SCEVPredicate * + getWrapPredicate(const SCEVAddRecExpr *AR, + SCEVWrapPredicate::IncrementWrapFlags AddedFlags); + + /// Re-writes the SCEV according to the Predicates in \p A. + const SCEV *rewriteUsingPredicate(const SCEV *S, const Loop *L, + SCEVUnionPredicate &A); + /// Tries to convert the \p S expression to an AddRec expression, + /// adding additional predicates to \p Preds as required. + const SCEVAddRecExpr *convertSCEVToAddRecWithPredicates( + const SCEV *S, const Loop *L, + SmallPtrSetImpl<const SCEVPredicate *> &Preds); + private: /// A CallbackVH to arrange for ScalarEvolution to be notified whenever a /// Value is deleted. class SCEVCallbackVH final : public CallbackVH { ScalarEvolution *SE; + void deleted() override; void allUsesReplacedWith(Value *New) override; @@ -462,44 +1030,37 @@ friend class SCEVUnknown; /// The function we are analyzing. - /// Function &F; /// Does the module have any calls to the llvm.experimental.guard intrinsic /// at all? If this is false, we avoid doing work that will only help if /// thare are guards present in the IR. - /// bool HasGuards; /// The target library information for the target we are targeting. - /// TargetLibraryInfo &TLI; /// The tracker for @llvm.assume intrinsics in this function. AssumptionCache &AC; /// The dominator tree. - /// DominatorTree &DT; /// The loop information for the function we are currently analyzing. - /// LoopInfo &LI; /// This SCEV is used to represent unknown trip counts and things. std::unique_ptr<SCEVCouldNotCompute> CouldNotCompute; - /// The typedef for HasRecMap. - /// - typedef DenseMap<const SCEV *, bool> HasRecMapType; + /// The type for HasRecMap. + using HasRecMapType = DenseMap<const SCEV *, bool>; /// This is a cache to record whether a SCEV contains any scAddRecExpr. HasRecMapType HasRecMap; - /// The typedef for ExprValueMap. - /// - typedef std::pair<Value *, ConstantInt *> ValueOffsetPair; - typedef DenseMap<const SCEV *, SetVector<ValueOffsetPair>> ExprValueMapType; + /// The type for ExprValueMap. + using ValueOffsetPair = std::pair<Value *, ConstantInt *>; + using ExprValueMapType = DenseMap<const SCEV *, SetVector<ValueOffsetPair>>; /// ExprValueMap -- This map records the original values from which /// the SCEV expr is generated from. @@ -523,13 +1084,11 @@ /// to V - Offset. ExprValueMapType ExprValueMap; - /// The typedef for ValueExprMap. - /// - typedef DenseMap<SCEVCallbackVH, const SCEV *, DenseMapInfo<Value *>> - ValueExprMapType; + /// The type for ValueExprMap. + using ValueExprMapType = + DenseMap<SCEVCallbackVH, const SCEV *, DenseMapInfo<Value *>>; /// This is a cache of the values we have analyzed so far. - /// ValueExprMapType ValueExprMap; /// Mark predicate values currently being processed by isImpliedCond. @@ -537,11 +1096,20 @@ /// Set to true by isLoopBackedgeGuardedByCond when we're walking the set of /// conditions dominating the backedge of a loop. - bool WalkingBEDominatingConds; + bool WalkingBEDominatingConds = false; /// Set to true by isKnownPredicateViaSplitting when we're trying to prove a /// predicate by splitting it into a set of independent predicates. - bool ProvingSplitPredicate; + bool ProvingSplitPredicate = false; + + /// Memoized values for the GetMinTrailingZeros + DenseMap<const SCEV *, uint32_t> MinTrailingZerosCache; + + /// Return the Value set from which the SCEV expr is generated. + SetVector<ValueOffsetPair> *getSCEVValues(const SCEV *S); + + /// Private helper method for the GetMinTrailingZeros method + uint32_t GetMinTrailingZerosImpl(const SCEV *S); /// 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 @@ -550,7 +1118,9 @@ struct ExitLimit { const SCEV *ExactNotTaken; // The exit is not taken exactly this many times const SCEV *MaxNotTaken; // The exit is not taken at most this many times - bool MaxOrZero; // Not taken either exactly MaxNotTaken or zero times + + // Not taken either exactly MaxNotTaken or zero times + bool MaxOrZero = false; /// A set of predicate guards for this ExitLimit. The result is only valid /// if all of the predicates in \c Predicates evaluate to 'true' at @@ -562,27 +1132,16 @@ Predicates.insert(P); } - /*implicit*/ ExitLimit(const SCEV *E) - : ExactNotTaken(E), MaxNotTaken(E), MaxOrZero(false) {} + /*implicit*/ ExitLimit(const SCEV *E); ExitLimit( const SCEV *E, const SCEV *M, bool MaxOrZero, - ArrayRef<const SmallPtrSetImpl<const SCEVPredicate *> *> PredSetList) - : ExactNotTaken(E), MaxNotTaken(M), MaxOrZero(MaxOrZero) { - assert((isa<SCEVCouldNotCompute>(ExactNotTaken) || - !isa<SCEVCouldNotCompute>(MaxNotTaken)) && - "Exact is not allowed to be less precise than Max"); - for (auto *PredSet : PredSetList) - for (auto *P : *PredSet) - addPredicate(P); - } + ArrayRef<const SmallPtrSetImpl<const SCEVPredicate *> *> PredSetList); ExitLimit(const SCEV *E, const SCEV *M, bool MaxOrZero, - const SmallPtrSetImpl<const SCEVPredicate *> &PredSet) - : ExitLimit(E, M, MaxOrZero, {&PredSet}) {} + const SmallPtrSetImpl<const SCEVPredicate *> &PredSet); - ExitLimit(const SCEV *E, const SCEV *M, bool MaxOrZero) - : ExitLimit(E, M, MaxOrZero, None) {} + ExitLimit(const SCEV *E, const SCEV *M, bool MaxOrZero); /// Test whether this ExitLimit contains any computed information, or /// whether it's all SCEVCouldNotCompute values. @@ -591,6 +1150,8 @@ !isa<SCEVCouldNotCompute>(MaxNotTaken); } + bool hasOperand(const SCEV *S) const; + /// Test whether this ExitLimit contains all information. bool hasFullInfo() const { return !isa<SCEVCouldNotCompute>(ExactNotTaken); @@ -600,18 +1161,19 @@ /// Information about the number of times a particular loop exit may be /// reached before exiting the loop. struct ExitNotTakenInfo { - AssertingVH<BasicBlock> ExitingBlock; + PoisoningVH<BasicBlock> ExitingBlock; const SCEV *ExactNotTaken; std::unique_ptr<SCEVUnionPredicate> Predicate; - bool hasAlwaysTruePredicate() const { - return !Predicate || Predicate->isAlwaysTrue(); - } - explicit ExitNotTakenInfo(AssertingVH<BasicBlock> ExitingBlock, + explicit ExitNotTakenInfo(PoisoningVH<BasicBlock> ExitingBlock, const SCEV *ExactNotTaken, std::unique_ptr<SCEVUnionPredicate> Predicate) : ExitingBlock(ExitingBlock), ExactNotTaken(ExactNotTaken), Predicate(std::move(Predicate)) {} + + bool hasAlwaysTruePredicate() const { + return !Predicate || Predicate->isAlwaysTrue(); + } }; /// Information about the backedge-taken count of a loop. This currently @@ -632,7 +1194,7 @@ PointerIntPair<const SCEV *, 1> MaxAndComplete; /// True iff the backedge is taken either exactly Max or zero times. - bool MaxOrZero; + bool MaxOrZero = false; /// \name Helper projection functions on \c MaxAndComplete. /// @{ @@ -642,11 +1204,10 @@ public: BackedgeTakenInfo() : MaxAndComplete(nullptr, 0) {} - BackedgeTakenInfo(BackedgeTakenInfo &&) = default; BackedgeTakenInfo &operator=(BackedgeTakenInfo &&) = default; - typedef std::pair<BasicBlock *, ExitLimit> EdgeExitInfo; + using EdgeExitInfo = std::pair<BasicBlock *, ExitLimit>; /// Initialize BackedgeTakenInfo from a list of exact exit counts. BackedgeTakenInfo(SmallVectorImpl<EdgeExitInfo> &&ExitCounts, bool Complete, @@ -661,10 +1222,12 @@ /// Test whether this BackedgeTakenInfo contains complete information. bool hasFullInfo() const { return isComplete(); } - /// Return an expression indicating the exact backedge-taken count of the - /// loop if it is known or SCEVCouldNotCompute otherwise. This is the - /// number of times the loop header can be guaranteed to execute, minus - /// one. + /// Return an expression indicating the exact *backedge-taken* + /// count of the loop if it is known or SCEVCouldNotCompute + /// otherwise. If execution makes it to the backedge on every + /// iteration (i.e. there are no abnormal exists like exception + /// throws and thread exits) then this is the number of times the + /// loop header will execute minus one. /// /// If the SCEV predicate associated with the answer can be different /// from AlwaysTrue, we must add a (non null) Predicates argument. @@ -709,6 +1272,9 @@ /// function as they are computed. DenseMap<const Loop *, BackedgeTakenInfo> PredicatedBackedgeTakenCounts; + // Cache the calculated exit limits for the loops. + DenseMap<ExitLimitQuery, ExitLimit> ExitLimits; + /// 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 @@ -776,18 +1342,20 @@ /// Set the memoized range for the given SCEV. const ConstantRange &setRange(const SCEV *S, RangeSignHint Hint, - const ConstantRange &CR) { + ConstantRange CR) { DenseMap<const SCEV *, ConstantRange> &Cache = Hint == HINT_RANGE_UNSIGNED ? UnsignedRanges : SignedRanges; - auto Pair = Cache.insert({S, CR}); + auto Pair = Cache.try_emplace(S, std::move(CR)); if (!Pair.second) - Pair.first->second = CR; + Pair.first->second = std::move(CR); return Pair.first->second; } /// Determine the range for a particular SCEV. - ConstantRange getRange(const SCEV *S, RangeSignHint Hint); + /// NOTE: This returns a reference to an entry in a cache. It must be + /// copied if its needed for longer. + const ConstantRange &getRangeRef(const SCEV *S, RangeSignHint Hint); /// Determines the range for the affine SCEVAddRecExpr {\p Start,+,\p Stop}. /// Helper for \c getRange. @@ -810,6 +1378,10 @@ /// Helper function called from createNodeForPHI. const SCEV *createAddRecFromPHI(PHINode *PN); + /// A helper function for createAddRecFromPHI to handle simple cases. + const SCEV *createSimpleAffineAddRec(PHINode *PN, Value *BEValueV, + Value *StartValueV); + /// Helper function called from createNodeForPHI. const SCEV *createNodeFromSelectLikePHI(PHINode *PN); @@ -825,7 +1397,6 @@ /// Implementation code for getSCEVAtScope; called at most once for each /// SCEV+Loop pair. - /// const SCEV *computeSCEVAtScope(const SCEV *S, const Loop *L); /// This looks up computed SCEV values for all instructions that depend on @@ -855,6 +1426,9 @@ ExitLimit computeExitLimit(const Loop *L, BasicBlock *ExitingBlock, bool AllowPredicates = false); + ExitLimit computeExitLimitImpl(const Loop *L, BasicBlock *ExitingBlock, + bool AllowPredicates = false); + /// Compute the number of times the backedge of the specified loop will /// execute if its exit condition were a conditional branch of ExitCond, /// TBB, and FBB. @@ -871,6 +1445,48 @@ bool ControlsExit, bool AllowPredicates = false); + // Helper functions for computeExitLimitFromCond to avoid exponential time + // complexity. + + class ExitLimitCache { + // It may look like we need key on the whole (L, TBB, FBB, ControlsExit, + // AllowPredicates) tuple, but recursive calls to + // computeExitLimitFromCondCached from computeExitLimitFromCondImpl only + // vary the in \c ExitCond and \c ControlsExit parameters. We remember the + // initial values of the other values to assert our assumption. + SmallDenseMap<PointerIntPair<Value *, 1>, ExitLimit> TripCountMap; + + const Loop *L; + BasicBlock *TBB; + BasicBlock *FBB; + bool AllowPredicates; + + public: + ExitLimitCache(const Loop *L, BasicBlock *TBB, BasicBlock *FBB, + bool AllowPredicates) + : L(L), TBB(TBB), FBB(FBB), AllowPredicates(AllowPredicates) {} + + Optional<ExitLimit> find(const Loop *L, Value *ExitCond, BasicBlock *TBB, + BasicBlock *FBB, bool ControlsExit, + bool AllowPredicates); + + void insert(const Loop *L, Value *ExitCond, BasicBlock *TBB, + BasicBlock *FBB, bool ControlsExit, bool AllowPredicates, + const ExitLimit &EL); + }; + + using ExitLimitCacheTy = ExitLimitCache; + + ExitLimit computeExitLimitFromCondCached(ExitLimitCacheTy &Cache, + const Loop *L, Value *ExitCond, + BasicBlock *TBB, BasicBlock *FBB, + bool ControlsExit, + bool AllowPredicates); + ExitLimit computeExitLimitFromCondImpl(ExitLimitCacheTy &Cache, const Loop *L, + Value *ExitCond, BasicBlock *TBB, + BasicBlock *FBB, bool ControlsExit, + bool AllowPredicates); + /// Compute the number of times the backedge of the specified loop will /// execute if its exit condition were a conditional branch of the ICmpInst /// ExitCond, TBB, and FBB. If AllowPredicates is set, this call will try @@ -972,6 +1588,20 @@ /// Test whether the condition described by Pred, LHS, and RHS is true /// whenever the condition described by Pred, FoundLHS, and FoundRHS is + /// true. Here LHS is an operation that includes FoundLHS as one of its + /// arguments. + bool isImpliedViaOperations(ICmpInst::Predicate Pred, + const SCEV *LHS, const SCEV *RHS, + const SCEV *FoundLHS, const SCEV *FoundRHS, + unsigned Depth = 0); + + /// Test whether the condition described by Pred, LHS, and RHS is true. + /// Use only simple non-recursive types of checks, such as range analysis etc. + bool isKnownViaSimpleReasoning(ICmpInst::Predicate Pred, + const SCEV *LHS, const SCEV *RHS); + + /// Test whether the condition described by Pred, LHS, and RHS is true + /// whenever the condition described by Pred, FoundLHS, and FoundRHS is /// true. bool isImpliedCondOperandsHelper(ICmpInst::Predicate Pred, const SCEV *LHS, const SCEV *RHS, const SCEV *FoundLHS, @@ -1009,7 +1639,6 @@ /// Test if the given expression is known to satisfy the condition described /// by Pred and the known constant ranges of LHS and RHS. - /// bool isKnownPredicateViaConstantRanges(ICmpInst::Predicate Pred, const SCEV *LHS, const SCEV *RHS); @@ -1039,8 +1668,9 @@ /// to be a constant. Optional<APInt> computeConstantDifference(const SCEV *LHS, const SCEV *RHS); - /// Drop memoized information computed for S. - void forgetMemoizedResults(const SCEV *S); + /// Drop memoized information computed for S. Only erase Exit Limits info if + /// we expect that the operation we have made is going to change it. + void forgetMemoizedResults(const SCEV *S, bool EraseExitLimit = true); /// Return an existing SCEV for V if there is one, otherwise return nullptr. const SCEV *getExistingSCEV(Value *V); @@ -1054,7 +1684,6 @@ /// 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); @@ -1065,18 +1694,6 @@ bool isMonotonicPredicateImpl(const SCEVAddRecExpr *LHS, ICmpInst::Predicate Pred, bool &Increasing); - /// Return true if, for all loop invariant X, the predicate "LHS `Pred` X" - /// is monotonically increasing or decreasing. In the former case set - /// `Increasing` to true and in the latter case set `Increasing` to false. - /// - /// A predicate is said to be monotonically increasing if may go from being - /// false to being true as the loop iterates, but never the other way - /// around. A predicate is said to be monotonically decreasing if may go - /// from being true to being false as the loop iterates, but never the other - /// way around. - bool isMonotonicPredicate(const SCEVAddRecExpr *LHS, ICmpInst::Predicate Pred, - bool &Increasing); - /// Return SCEV no-wrap flags that can be proven based on reasoning about /// how poison produced from no-wrap flags on this value (e.g. a nuw add) /// would trigger undefined behavior on overflow. @@ -1106,499 +1723,34 @@ /// add recurrence on the loop \p L. bool isAddRecNeverPoison(const Instruction *I, const Loop *L); -public: - ScalarEvolution(Function &F, TargetLibraryInfo &TLI, AssumptionCache &AC, - DominatorTree &DT, LoopInfo &LI); - ~ScalarEvolution(); - ScalarEvolution(ScalarEvolution &&Arg); - - LLVMContext &getContext() const { return F.getContext(); } - - /// 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(Type *Ty) const; - - /// Return the size in bits of the specified type, for which isSCEVable must - /// return true. - uint64_t getTypeSizeInBits(Type *Ty) const; - - /// 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. - Type *getEffectiveSCEVType(Type *Ty) const; - - /// Return true if the SCEV is a scAddRecExpr or it contains - /// scAddRecExpr. The result will be cached in HasRecMap. - /// - bool containsAddRecurrence(const SCEV *S); - - /// Return the Value set from which the SCEV expr is generated. - SetVector<ValueOffsetPair> *getSCEVValues(const SCEV *S); - - /// Erase Value from ValueExprMap and ExprValueMap. - void eraseValueFromMap(Value *V); - - /// Return a SCEV expression for the full generality of the specified - /// expression. - const SCEV *getSCEV(Value *V); - - const SCEV *getConstant(ConstantInt *V); - const SCEV *getConstant(const APInt &Val); - const SCEV *getConstant(Type *Ty, uint64_t V, bool isSigned = false); - const SCEV *getTruncateExpr(const SCEV *Op, Type *Ty); - const SCEV *getZeroExtendExpr(const SCEV *Op, Type *Ty); - const SCEV *getSignExtendExpr(const SCEV *Op, Type *Ty); - const SCEV *getAnyExtendExpr(const SCEV *Op, Type *Ty); - const SCEV *getAddExpr(SmallVectorImpl<const SCEV *> &Ops, - SCEV::NoWrapFlags Flags = SCEV::FlagAnyWrap); - const SCEV *getAddExpr(const SCEV *LHS, const SCEV *RHS, - SCEV::NoWrapFlags Flags = SCEV::FlagAnyWrap) { - SmallVector<const SCEV *, 2> Ops = {LHS, RHS}; - return getAddExpr(Ops, Flags); - } - const SCEV *getAddExpr(const SCEV *Op0, const SCEV *Op1, const SCEV *Op2, - SCEV::NoWrapFlags Flags = SCEV::FlagAnyWrap) { - SmallVector<const SCEV *, 3> Ops = {Op0, Op1, Op2}; - return getAddExpr(Ops, Flags); - } - const SCEV *getMulExpr(SmallVectorImpl<const SCEV *> &Ops, - SCEV::NoWrapFlags Flags = SCEV::FlagAnyWrap); - const SCEV *getMulExpr(const SCEV *LHS, const SCEV *RHS, - SCEV::NoWrapFlags Flags = SCEV::FlagAnyWrap) { - SmallVector<const SCEV *, 2> Ops = {LHS, RHS}; - return getMulExpr(Ops, Flags); - } - const SCEV *getMulExpr(const SCEV *Op0, const SCEV *Op1, const SCEV *Op2, - SCEV::NoWrapFlags Flags = SCEV::FlagAnyWrap) { - SmallVector<const SCEV *, 3> Ops = {Op0, Op1, Op2}; - 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<const SCEV *> &Operands, - const Loop *L, SCEV::NoWrapFlags Flags); - const SCEV *getAddRecExpr(const SmallVectorImpl<const SCEV *> &Operands, - const Loop *L, SCEV::NoWrapFlags Flags) { - SmallVector<const SCEV *, 4> NewOp(Operands.begin(), Operands.end()); - return getAddRecExpr(NewOp, L, Flags); - } - /// Returns an expression for a GEP - /// - /// \p GEP The GEP. The indices contained in the GEP itself are ignored, - /// instead we use IndexExprs. - /// \p IndexExprs The expressions for the indices. - const SCEV *getGEPExpr(GEPOperator *GEP, - const SmallVectorImpl<const SCEV *> &IndexExprs); - 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); - const SCEV *getUMaxExpr(SmallVectorImpl<const SCEV *> &Operands); - const SCEV *getSMinExpr(const SCEV *LHS, const SCEV *RHS); - const SCEV *getUMinExpr(const SCEV *LHS, const SCEV *RHS); - const SCEV *getUnknown(Value *V); - const SCEV *getCouldNotCompute(); - - /// Return a SCEV for the constant 0 of a specific type. - const SCEV *getZero(Type *Ty) { return getConstant(Ty, 0); } - - /// Return a SCEV for the constant 1 of a specific type. - const SCEV *getOne(Type *Ty) { return getConstant(Ty, 1); } - - /// Return an expression for sizeof AllocTy that is type IntTy - /// - const SCEV *getSizeOfExpr(Type *IntTy, Type *AllocTy); - - /// Return an expression for offsetof on the given field with type IntTy - /// - const SCEV *getOffsetOfExpr(Type *IntTy, StructType *STy, unsigned FieldNo); - - /// Return the SCEV object corresponding to -V. - /// - const SCEV *getNegativeSCEV(const SCEV *V, - SCEV::NoWrapFlags Flags = SCEV::FlagAnyWrap); - - /// Return the SCEV object corresponding to ~V. - /// - const SCEV *getNotSCEV(const SCEV *V); - - /// Return LHS-RHS. Minus is represented in SCEV as A+B*-1. - const SCEV *getMinusSCEV(const SCEV *LHS, const SCEV *RHS, - SCEV::NoWrapFlags Flags = SCEV::FlagAnyWrap); - - /// 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. - const SCEV *getTruncateOrZeroExtend(const SCEV *V, Type *Ty); - - /// 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. - const SCEV *getTruncateOrSignExtend(const SCEV *V, Type *Ty); - - /// 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. - const SCEV *getNoopOrZeroExtend(const SCEV *V, Type *Ty); - - /// 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. - const SCEV *getNoopOrSignExtend(const SCEV *V, Type *Ty); - - /// Return a SCEV corresponding to a conversion of the input value to the - /// specified type. If the type must be extended, it is extended with - /// unspecified bits. The conversion must not be narrowing. - const SCEV *getNoopOrAnyExtend(const SCEV *V, Type *Ty); - - /// Return a SCEV corresponding to a conversion of the input value to the - /// specified type. The conversion must not be widening. - const SCEV *getTruncateOrNoop(const SCEV *V, Type *Ty); - - /// Promote the operands to the wider of the types using zero-extension, and - /// then perform a umax operation with them. - const SCEV *getUMaxFromMismatchedTypes(const SCEV *LHS, const SCEV *RHS); - - /// Promote the operands to the wider of the types using zero-extension, and - /// then perform a umin operation with them. - const SCEV *getUMinFromMismatchedTypes(const SCEV *LHS, const SCEV *RHS); - - /// Transitively follow the chain of pointer-type operands until reaching a - /// SCEV that does not have a single pointer operand. This returns a - /// SCEVUnknown pointer for well-formed pointer-type expressions, but corner - /// cases do exist. - const SCEV *getPointerBase(const SCEV *V); - - /// Return a SCEV expression for the specified value at the specified scope - /// in the program. The L value specifies a loop nest to evaluate the - /// expression at, where null is the top-level or a specified loop is - /// immediately inside of the loop. - /// - /// 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. - /// - /// In the case that a relevant loop exit value cannot be computed, the - /// original value V is returned. - const SCEV *getSCEVAtScope(const SCEV *S, const Loop *L); - - /// This is a convenience function which does getSCEVAtScope(getSCEV(V), L). - const SCEV *getSCEVAtScope(Value *V, const Loop *L); - - /// 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, and to eliminate casts. - bool isLoopEntryGuardedByCond(const Loop *L, ICmpInst::Predicate Pred, - const SCEV *LHS, const SCEV *RHS); - - /// Test whether the backedge of the loop is protected by a conditional - /// between LHS and RHS. This is used to to eliminate casts. - bool isLoopBackedgeGuardedByCond(const Loop *L, ICmpInst::Predicate Pred, - const SCEV *LHS, const SCEV *RHS); - - /// 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); - - /// 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 ExitingBlock. More - /// precisely, it is the number of times that control may reach ExitingBlock - /// before taking the branch. For loops with multiple exits, it may not be - /// the number times that the loop header executes if the loop exits - /// prematurely via another branch. - unsigned getSmallConstantTripCount(Loop *L, BasicBlock *ExitingBlock); - - /// Returns the upper bound of the loop trip count as a normal unsigned - /// value. - /// Returns 0 if the trip count is unknown or not constant. - unsigned getSmallConstantMaxTripCount(Loop *L); - - /// 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); - - /// 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 the returned value (don't forget the trip - /// count could very well be zero as well!). As explained in the comments - /// for getSmallConstantTripCount, this assumes that control exits the loop - /// via ExitingBlock. - unsigned getSmallConstantTripMultiple(Loop *L, BasicBlock *ExitingBlock); - - /// Get the expression for the number of loop iterations for which this loop - /// is guaranteed not to exit via ExitingBlock. Otherwise return - /// SCEVCouldNotCompute. - const SCEV *getExitCount(Loop *L, BasicBlock *ExitingBlock); + /// Similar to createAddRecFromPHI, but with the additional flexibility of + /// suggesting runtime overflow checks in case casts are encountered. + /// If successful, the analysis records that for this loop, \p SymbolicPHI, + /// which is the UnknownSCEV currently representing the PHI, can be rewritten + /// into an AddRec, assuming some predicates; The function then returns the + /// AddRec and the predicates as a pair, and caches this pair in + /// PredicatedSCEVRewrites. + /// If the analysis is not successful, a mapping from the \p SymbolicPHI to + /// itself (with no predicates) is recorded, and a nullptr with an empty + /// predicates vector is returned as a pair. + Optional<std::pair<const SCEV *, SmallVector<const SCEVPredicate *, 3>>> + createAddRecFromPHIWithCastsImpl(const SCEVUnknown *SymbolicPHI); - /// 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). - /// - const SCEV *getBackedgeTakenCount(const Loop *L); - - /// Similar to getBackedgeTakenCount, except it will add a set of - /// SCEV predicates to Predicates that are required to be true in order for - /// the answer to be correct. Predicates can be checked with run-time - /// checks and can be used to perform loop versioning. - const SCEV *getPredicatedBackedgeTakenCount(const Loop *L, - SCEVUnionPredicate &Predicates); - - /// Similar to getBackedgeTakenCount, except return the least SCEV value - /// that is known never to be less than the actual backedge taken count. - const SCEV *getMaxBackedgeTakenCount(const Loop *L); - - /// Return true if the backedge taken count is either the value returned by - /// getMaxBackedgeTakenCount or zero. - bool isBackedgeTakenCountMaxOrZero(const Loop *L); - - /// Return true if the specified loop has an analyzable loop-invariant - /// backedge-taken count. - bool hasLoopInvariantBackedgeTakenCount(const Loop *L); - - /// 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. This call is potentially expensive for large - /// loop bodies. - void forgetLoop(const Loop *L); - - /// This method should be called by the client when it has changed a value - /// in a way that may effect its value, or which may disconnect it from a - /// def-use chain linking it to a loop. - void forgetValue(Value *V); - - /// 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(); } - - /// 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, given {4,+,8} it returns 2. - /// If S is guaranteed to be 0, it returns the bitwidth of S. - uint32_t GetMinTrailingZeros(const SCEV *S); - - /// Determine the unsigned range for a particular SCEV. - /// - ConstantRange getUnsignedRange(const SCEV *S) { - return getRange(S, HINT_RANGE_UNSIGNED); - } - - /// Determine the signed range for a particular SCEV. - /// - ConstantRange getSignedRange(const SCEV *S) { - return getRange(S, HINT_RANGE_SIGNED); - } - - /// Test if the given expression is known to be negative. - /// - bool isKnownNegative(const SCEV *S); - - /// Test if the given expression is known to be positive. - /// - bool isKnownPositive(const SCEV *S); - - /// Test if the given expression is known to be non-negative. - /// - bool isKnownNonNegative(const SCEV *S); - - /// Test if the given expression is known to be non-positive. - /// - bool isKnownNonPositive(const SCEV *S); - - /// Test if the given expression is known to be non-zero. - /// - bool isKnownNonZero(const SCEV *S); - - /// Test if the given expression is known to satisfy the condition described - /// by Pred, LHS, and RHS. - /// - bool isKnownPredicate(ICmpInst::Predicate Pred, const SCEV *LHS, - const SCEV *RHS); - - /// Return true if the result of the predicate LHS `Pred` RHS is loop - /// invariant with respect to L. Set InvariantPred, InvariantLHS and - /// InvariantLHS so that InvariantLHS `InvariantPred` InvariantRHS is the - /// loop invariant form of LHS `Pred` RHS. - bool isLoopInvariantPredicate(ICmpInst::Predicate Pred, const SCEV *LHS, - const SCEV *RHS, const Loop *L, - ICmpInst::Predicate &InvariantPred, - const SCEV *&InvariantLHS, - const SCEV *&InvariantRHS); - - /// Simplify LHS and RHS in a comparison with predicate Pred. Return true - /// iff any changes were made. If the 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, const SCEV *&LHS, - const SCEV *&RHS, unsigned Depth = 0); - - /// Return the "disposition" of the given SCEV with respect to the given - /// loop. - LoopDisposition getLoopDisposition(const SCEV *S, const Loop *L); - - /// Return true if the value of the given SCEV is unchanging in the - /// specified loop. - bool isLoopInvariant(const SCEV *S, const Loop *L); - - /// Return true if the given SCEV changes value in a known way in the - /// specified loop. This property being true implies that the value is - /// variant in the loop AND that we can emit an expression to compute the - /// value of the expression at any particular loop iteration. - bool hasComputableLoopEvolution(const SCEV *S, const Loop *L); - - /// Return the "disposition" of the given SCEV with respect to the given - /// block. - BlockDisposition getBlockDisposition(const SCEV *S, const BasicBlock *BB); - - /// Return true if elements that makes up the given SCEV dominate the - /// specified basic block. - bool dominates(const SCEV *S, const BasicBlock *BB); - - /// Return true if elements that makes up the given SCEV properly dominate - /// the specified basic block. - bool properlyDominates(const SCEV *S, const BasicBlock *BB); - - /// Test whether the given SCEV has Op as a direct or indirect operand. - bool hasOperand(const SCEV *S, const SCEV *Op) 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 (second step of - /// delinearization). - void findArrayDimensions(SmallVectorImpl<const SCEV *> &Terms, - SmallVectorImpl<const SCEV *> &Sizes, - const SCEV *ElementSize) const; - - void print(raw_ostream &OS) const; - void verify() const; - - /// Collect parametric terms occurring in step expressions (first step of - /// delinearization). - void collectParametricTerms(const SCEV *Expr, - SmallVectorImpl<const SCEV *> &Terms); - - /// Return in Subscripts the access functions for each dimension in Sizes - /// (third step of delinearization). - void computeAccessFunctions(const SCEV *Expr, - SmallVectorImpl<const SCEV *> &Subscripts, - SmallVectorImpl<const SCEV *> &Sizes); - - /// Split this SCEVAddRecExpr into two vectors of SCEVs representing the - /// subscripts and sizes of an array access. - /// - /// The delinearization is a 3 step process: the first two steps compute the - /// sizes of each subscript and the third step computes the access functions - /// for the delinearized array: - /// - /// 1. Find the terms in the step functions - /// 2. Compute the array size - /// 3. Compute the access function: divide the SCEV by the array size - /// starting with the innermost dimensions found in step 2. The Quotient - /// is the SCEV to be divided in the next step of the recursion. The - /// Remainder is the subscript of the innermost dimension. Loop over all - /// array dimensions computed in step 2. - /// - /// To compute a uniform array size for several memory accesses to the same - /// object, one can collect in step 1 all the step terms for all the memory - /// accesses, and compute in step 2 a unique array shape. This guarantees - /// that the array shape will be the same across all memory accesses. - /// - /// FIXME: We could derive the result of steps 1 and 2 from a description of - /// the array shape given in metadata. - /// - /// Example: - /// - /// A[][n][m] - /// - /// for i - /// for j - /// for k - /// A[j+k][2i][5i] = - /// - /// The initial SCEV: - /// - /// A[{{{0,+,2*m+5}_i, +, n*m}_j, +, n*m}_k] - /// - /// 1. Find the different terms in the step functions: - /// -> [2*m, 5, n*m, n*m] - /// - /// 2. Compute the array size: sort and unique them - /// -> [n*m, 2*m, 5] - /// find the GCD of all the terms = 1 - /// divide by the GCD and erase constant terms - /// -> [n*m, 2*m] - /// GCD = m - /// divide by GCD -> [n, 2] - /// remove constant terms - /// -> [n] - /// size of the array is A[unknown][n][m] - /// - /// 3. Compute the access function - /// a. Divide {{{0,+,2*m+5}_i, +, n*m}_j, +, n*m}_k by the innermost size m - /// Quotient: {{{0,+,2}_i, +, n}_j, +, n}_k - /// Remainder: {{{0,+,5}_i, +, 0}_j, +, 0}_k - /// The remainder is the subscript of the innermost array dimension: [5i]. - /// - /// b. Divide Quotient: {{{0,+,2}_i, +, n}_j, +, n}_k by next outer size n - /// Quotient: {{{0,+,0}_i, +, 1}_j, +, 1}_k - /// Remainder: {{{0,+,2}_i, +, 0}_j, +, 0}_k - /// The Remainder is the subscript of the next array dimension: [2i]. - /// - /// The subscript of the outermost dimension is the Quotient: [j+k]. - /// - /// Overall, we have: A[][n][m], and the access function: A[j+k][2i][5i]. - void delinearize(const SCEV *Expr, SmallVectorImpl<const SCEV *> &Subscripts, - SmallVectorImpl<const SCEV *> &Sizes, - const SCEV *ElementSize); - - /// Return the DataLayout associated with the module this SCEV instance is - /// operating on. - const DataLayout &getDataLayout() const { - return F.getParent()->getDataLayout(); - } - - const SCEVPredicate *getEqualPredicate(const SCEVUnknown *LHS, - const SCEVConstant *RHS); - - const SCEVPredicate * - getWrapPredicate(const SCEVAddRecExpr *AR, - SCEVWrapPredicate::IncrementWrapFlags AddedFlags); - - /// Re-writes the SCEV according to the Predicates in \p A. - const SCEV *rewriteUsingPredicate(const SCEV *S, const Loop *L, - SCEVUnionPredicate &A); - /// Tries to convert the \p S expression to an AddRec expression, - /// adding additional predicates to \p Preds as required. - const SCEVAddRecExpr *convertSCEVToAddRecWithPredicates( - const SCEV *S, const Loop *L, - SmallPtrSetImpl<const SCEVPredicate *> &Preds); - -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); + /// Compute the maximum backedge count based on the range of values + /// permitted by Start, End, and Stride. This is for loops of the form + /// {Start, +, Stride} LT End. + /// + /// Precondition: the induction variable is known to be positive. We *don't* + /// assert these preconditions so please be careful. + const SCEV *computeMaxBECountForLT(const SCEV *Start, const SCEV *Stride, + const SCEV *End, unsigned BitWidth, + bool IsSigned); + /// 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. @@ -1611,25 +1763,47 @@ bool doesIVOverflowOnGT(const SCEV *RHS, const SCEV *Stride, bool IsSigned, bool NoWrap); -private: + /// Get add expr already created or create a new one. + const SCEV *getOrCreateAddExpr(SmallVectorImpl<const SCEV *> &Ops, + SCEV::NoWrapFlags Flags); + + /// Get mul expr already created or create a new one. + const SCEV *getOrCreateMulExpr(SmallVectorImpl<const SCEV *> &Ops, + SCEV::NoWrapFlags Flags); + + /// Find all of the loops transitively used in \p S, and update \c LoopUsers + /// accordingly. + void addToLoopUseLists(const SCEV *S); + FoldingSet<SCEV> UniqueSCEVs; FoldingSet<SCEVPredicate> UniquePreds; BumpPtrAllocator SCEVAllocator; + /// This maps loops to a list of SCEV expressions that (transitively) use said + /// loop. + DenseMap<const Loop *, SmallVector<const SCEV *, 4>> LoopUsers; + + /// Cache tentative mappings from UnknownSCEVs in a Loop, to a SCEV expression + /// they can be rewritten into under certain predicates. + DenseMap<std::pair<const SCEVUnknown *, const Loop *>, + std::pair<const SCEV *, SmallVector<const SCEVPredicate *, 3>>> + PredicatedSCEVRewrites; + /// The head of a linked list of all SCEVUnknown values that have been /// allocated. This is used by releaseMemory to locate them all and call /// their destructors. - SCEVUnknown *FirstUnknown; + SCEVUnknown *FirstUnknown = nullptr; }; /// Analysis pass that exposes the \c ScalarEvolution for a function. class ScalarEvolutionAnalysis : public AnalysisInfoMixin<ScalarEvolutionAnalysis> { friend AnalysisInfoMixin<ScalarEvolutionAnalysis>; + static AnalysisKey Key; public: - typedef ScalarEvolution Result; + using Result = ScalarEvolution; ScalarEvolution run(Function &F, FunctionAnalysisManager &AM); }; @@ -1641,6 +1815,7 @@ public: explicit ScalarEvolutionPrinterPass(raw_ostream &OS) : OS(OS) {} + PreservedAnalyses run(Function &F, FunctionAnalysisManager &AM); }; @@ -1678,6 +1853,7 @@ class PredicatedScalarEvolution { public: PredicatedScalarEvolution(ScalarEvolution &SE, Loop &L); + const SCEVUnionPredicate &getUnionPredicate() const; /// Returns the SCEV expression of V, in the context of the current SCEV @@ -1722,7 +1898,7 @@ /// Holds a SCEV and the version number of the SCEV predicate used to /// perform the rewrite of the expression. - typedef std::pair<unsigned, const SCEV *> RewriteEntry; + using RewriteEntry = std::pair<unsigned, const SCEV *>; /// Maps a SCEV to the rewrite result of that SCEV at a certain version /// number. If this number doesn't match the current Generation, we will @@ -1748,11 +1924,12 @@ /// expression we mark it with the version of the predicate. We use this to /// figure out if the predicate has changed from the last rewrite of the /// SCEV. If so, we need to perform a new rewrite. - unsigned Generation; + unsigned Generation = 0; /// The backedge taken count. - const SCEV *BackedgeCount; + const SCEV *BackedgeCount = nullptr; }; -} -#endif +} // end namespace llvm + +#endif // LLVM_ANALYSIS_SCALAREVOLUTION_H