From 0d1cc519bbeaae973ec323e502d4d62b6a5be2cf Mon Sep 17 00:00:00 2001 From: Sanjoy Das Date: Sun, 25 Sep 2016 23:11:51 +0000 Subject: [PATCH] [SCEV] Clang format most of the SCEV header; NFC The indentation for the declared classes was not as per LLVM coding style. git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@282362 91177308-0d34-0410-b5e6-96231b3b80d8 --- include/llvm/Analysis/ScalarEvolution.h | 3283 +++++++++++------------ 1 file changed, 1631 insertions(+), 1652 deletions(-) diff --git a/include/llvm/Analysis/ScalarEvolution.h b/include/llvm/Analysis/ScalarEvolution.h index a97c6b74953..0194a3d8029 100644 --- a/include/llvm/Analysis/ScalarEvolution.h +++ b/include/llvm/Analysis/ScalarEvolution.h @@ -36,1799 +36,1778 @@ #include "llvm/Support/DataTypes.h" namespace llvm { - class APInt; - class AssumptionCache; - class Constant; - class ConstantInt; - class DominatorTree; - class Type; - 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; - template <> struct FoldingSetTrait; - - /// This class represents an analyzed expression in the program. These are - /// opaque objects that the client is not allowed to do much with directly. - /// - class SCEV : public FoldingSetNode { - friend struct FoldingSetTrait; - - /// A reference to an Interned FoldingSetNodeID for this node. The - /// ScalarEvolution's BumpPtrAllocator holds the data. - FoldingSetNodeIDRef FastID; - - // The SCEV baseclass this node corresponds to - const unsigned short SCEVType; - - 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; +class APInt; +class AssumptionCache; +class Constant; +class ConstantInt; +class DominatorTree; +class Type; +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; +template <> struct FoldingSetTrait; + +/// This class represents an analyzed expression in the program. These are +/// opaque objects that the client is not allowed to do much with directly. +/// +class SCEV : public FoldingSetNode { + friend struct FoldingSetTrait; + + /// A reference to an Interned FoldingSetNodeID for this node. The + /// ScalarEvolution's BumpPtrAllocator holds the data. + FoldingSetNodeIDRef FastID; + + // The SCEV baseclass this node corresponds to + const unsigned short SCEVType; + +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; + +public: + /// NoWrapFlags are bitfield indices into SubclassData. + /// + /// Add and Mul expressions may have no-unsigned-wrap or + /// no-signed-wrap properties, which are derived from the IR + /// operator. NSW is a misnomer that we use to mean no signed overflow or + /// underflow. + /// + /// 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 + /// whenever either NUW or NSW are set. + enum NoWrapFlags { + FlagAnyWrap = 0, // No guarantee. + FlagNW = (1 << 0), // No self-wrap. + FlagNUW = (1 << 1), // No unsigned wrap. + FlagNSW = (1 << 2), // No signed wrap. + NoWrapMask = (1 << 3) - 1 + }; - public: - /// NoWrapFlags are bitfield indices into SubclassData. - /// - /// Add and Mul expressions may have no-unsigned-wrap or - /// no-signed-wrap properties, which are derived from the IR - /// operator. NSW is a misnomer that we use to mean no signed overflow or - /// underflow. - /// - /// 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 - /// whenever either NUW or NSW are set. - enum NoWrapFlags { FlagAnyWrap = 0, // No guarantee. - FlagNW = (1 << 0), // No self-wrap. - FlagNUW = (1 << 1), // No unsigned wrap. - FlagNSW = (1 << 2), // No signed wrap. - NoWrapMask = (1 << 3) -1 }; + explicit SCEV(const FoldingSetNodeIDRef ID, unsigned SCEVTy) + : FastID(ID), SCEVType(SCEVTy), SubclassData(0) {} - explicit SCEV(const FoldingSetNodeIDRef ID, unsigned SCEVTy) : - FastID(ID), SCEVType(SCEVTy), SubclassData(0) {} + unsigned getSCEVType() const { return SCEVType; } - unsigned getSCEVType() const { return SCEVType; } + /// Return the LLVM type of this SCEV expression. + /// + Type *getType() const; - /// 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 zero. - /// - bool isZero() const; + /// Return true if the expression is a constant one. + /// + bool isOne() 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 expression is a constant all-ones value. - /// - bool isAllOnesValue() const; + /// Return true if the specified scev is negated, but not a constant. + bool isNonConstantNegative() const; - /// Return true if the specified scev is negated, but not a constant. - bool isNonConstantNegative() const; + /// Print out the internal representation of this scalar to the specified + /// stream. This should really only be used for debugging purposes. + void print(raw_ostream &OS) const; - /// Print out the internal representation of this scalar to the specified - /// stream. This should really only be used for debugging purposes. - void print(raw_ostream &OS) const; + /// This method is used for debugging. + /// + void dump() const; +}; + +// Specialize FoldingSetTrait for SCEV to avoid needing to compute +// temporary FoldingSetNodeID values. +template <> struct FoldingSetTrait : DefaultFoldingSetTrait { + 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(); + } +}; - /// This method is used for debugging. - /// - void dump() const; - }; +inline raw_ostream &operator<<(raw_ostream &OS, const SCEV &S) { + S.print(OS); + return OS; +} - // Specialize FoldingSetTrait for SCEV to avoid needing to compute - // temporary FoldingSetNodeID values. - template<> struct FoldingSetTrait : DefaultFoldingSetTrait { - 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(); - } - }; +/// An object of this class is returned by queries that could not be answered. +/// For example, if you ask for the number of iterations of a linked-list +/// traversal loop, you will get one of these. None of the standard SCEV +/// operations are valid on this class, it is just a marker. +struct SCEVCouldNotCompute : public SCEV { + SCEVCouldNotCompute(); - inline raw_ostream &operator<<(raw_ostream &OS, const SCEV &S) { - S.print(OS); - return OS; - } + /// Methods for support type inquiry through isa, cast, and dyn_cast: + static bool classof(const SCEV *S); +}; - /// An object of this class is returned by queries that could not be answered. - /// For example, if you ask for the number of iterations of a linked-list - /// traversal loop, you will get one of these. None of the standard SCEV - /// operations are valid on this class, it is just a marker. - struct SCEVCouldNotCompute : public SCEV { - SCEVCouldNotCompute(); +/// This class represents an assumption made using SCEV expressions which can +/// be checked at run-time. +class SCEVPredicate : public FoldingSetNode { + friend struct FoldingSetTrait; - /// Methods for support type inquiry through isa, cast, and dyn_cast: - static bool classof(const SCEV *S); - }; + /// A reference to an Interned FoldingSetNodeID for this node. The + /// ScalarEvolution's BumpPtrAllocator holds the data. + FoldingSetNodeIDRef FastID; - /// This class represents an assumption made using SCEV expressions which can - /// be checked at run-time. - class SCEVPredicate : public FoldingSetNode { - friend struct FoldingSetTrait; +public: + enum SCEVPredicateKind { P_Union, P_Equal, P_Wrap }; - /// A reference to an Interned FoldingSetNodeID for this node. The - /// ScalarEvolution's BumpPtrAllocator holds the data. - FoldingSetNodeIDRef FastID; +protected: + SCEVPredicateKind Kind; + ~SCEVPredicate() = default; + SCEVPredicate(const SCEVPredicate &) = default; + SCEVPredicate &operator=(const SCEVPredicate &) = default; - public: - enum SCEVPredicateKind { P_Union, P_Equal, P_Wrap }; +public: + SCEVPredicate(const FoldingSetNodeIDRef ID, SCEVPredicateKind Kind); - protected: - SCEVPredicateKind Kind; - ~SCEVPredicate() = default; - SCEVPredicate(const SCEVPredicate&) = default; - SCEVPredicate &operator=(const SCEVPredicate&) = default; + SCEVPredicateKind getKind() const { return Kind; } - public: - SCEVPredicate(const FoldingSetNodeIDRef ID, SCEVPredicateKind Kind); + /// Returns the estimated complexity of this predicate. This is roughly + /// measured in the number of run-time checks required. + virtual unsigned getComplexity() const { return 1; } - SCEVPredicateKind getKind() const { return Kind; } + /// Returns true if the predicate is always true. This means that no + /// assumptions were made and nothing needs to be checked at run-time. + virtual bool isAlwaysTrue() const = 0; - /// Returns the estimated complexity of this predicate. This is roughly - /// measured in the number of run-time checks required. - virtual unsigned getComplexity() const { return 1; } + /// Returns true if this predicate implies \p N. + virtual bool implies(const SCEVPredicate *N) const = 0; - /// Returns true if the predicate is always true. This means that no - /// assumptions were made and nothing needs to be checked at run-time. - virtual bool isAlwaysTrue() const = 0; + /// Prints a textual representation of this predicate with an indentation of + /// \p Depth. + virtual void print(raw_ostream &OS, unsigned Depth = 0) const = 0; - /// Returns true if this predicate implies \p N. - virtual bool implies(const SCEVPredicate *N) const = 0; + /// Returns the SCEV to which this predicate applies, or nullptr if this is + /// a SCEVUnionPredicate. + virtual const SCEV *getExpr() const = 0; +}; - /// Prints a textual representation of this predicate with an indentation of - /// \p Depth. - virtual void print(raw_ostream &OS, unsigned Depth = 0) const = 0; +inline raw_ostream &operator<<(raw_ostream &OS, const SCEVPredicate &P) { + P.print(OS); + return OS; +} - /// Returns the SCEV to which this predicate applies, or nullptr if this is - /// a SCEVUnionPredicate. - virtual const SCEV *getExpr() const = 0; - }; +// Specialize FoldingSetTrait for SCEVPredicate to avoid needing to compute +// temporary FoldingSetNodeID values. +template <> +struct FoldingSetTrait : DefaultFoldingSetTrait { - inline raw_ostream &operator<<(raw_ostream &OS, const SCEVPredicate &P) { - P.print(OS); - return OS; + static void Profile(const SCEVPredicate &X, FoldingSetNodeID &ID) { + ID = X.FastID; } - // Specialize FoldingSetTrait for SCEVPredicate to avoid needing to compute - // temporary FoldingSetNodeID values. - template <> - struct FoldingSetTrait - : DefaultFoldingSetTrait { - - static void Profile(const SCEVPredicate &X, FoldingSetNodeID &ID) { - ID = X.FastID; - } - - static bool Equals(const SCEVPredicate &X, const FoldingSetNodeID &ID, - unsigned IDHash, FoldingSetNodeID &TempID) { - return ID == X.FastID; - } - static unsigned ComputeHash(const SCEVPredicate &X, - FoldingSetNodeID &TempID) { - return X.FastID.ComputeHash(); - } + static bool Equals(const SCEVPredicate &X, const FoldingSetNodeID &ID, + unsigned IDHash, FoldingSetNodeID &TempID) { + return ID == X.FastID; + } + static unsigned ComputeHash(const SCEVPredicate &X, + FoldingSetNodeID &TempID) { + return X.FastID.ComputeHash(); + } +}; + +/// 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. +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; + +public: + SCEVEqualPredicate(const FoldingSetNodeIDRef ID, const SCEVUnknown *LHS, + const SCEVConstant *RHS); + + /// Implementation of the SCEVPredicate interface + bool implies(const SCEVPredicate *N) const override; + void print(raw_ostream &OS, unsigned Depth = 0) const override; + bool isAlwaysTrue() const override; + const SCEV *getExpr() const override; + + /// Returns the left hand side of the equality. + const SCEVUnknown *getLHS() const { return LHS; } + + /// Returns the right hand side of the equality. + const SCEVConstant *getRHS() const { return RHS; } + + /// Methods for support type inquiry through isa, cast, and dyn_cast: + static inline bool classof(const SCEVPredicate *P) { + return P->getKind() == P_Equal; + } +}; + +/// This class represents an assumption made on an AddRec expression. Given an +/// affine AddRec expression {a,+,b}, we assume that it has the nssw or nusw +/// flags (defined below) in the first X iterations of the loop, where X is a +/// SCEV expression returned by getPredicatedBackedgeTakenCount). +/// +/// Note that this does not imply that X is equal to the backedge taken +/// count. This means that if we have a nusw predicate for i32 {0,+,1} with a +/// predicated backedge taken count of X, we only guarantee that {0,+,1} has +/// nusw in the first X iterations. {0,+,1} may still wrap in the loop if we +/// have more than X iterations. +class SCEVWrapPredicate final : public SCEVPredicate { +public: + /// Similar to SCEV::NoWrapFlags, but with slightly different semantics + /// for FlagNUSW. The increment is considered to be signed, and a + b + /// (where b is the increment) is considered to wrap if: + /// zext(a + b) != zext(a) + sext(b) + /// + /// If Signed is a function that takes an n-bit tuple and maps to the + /// integer domain as the tuples value interpreted as twos complement, + /// and Unsigned a function that takes an n-bit tuple and maps to the + /// integer domain as as the base two value of input tuple, then a + b + /// has IncrementNUSW iff: + /// + /// 0 <= Unsigned(a) + Signed(b) < 2^n + /// + /// The IncrementNSSW flag has identical semantics with SCEV::FlagNSW. + /// + /// Note that the IncrementNUSW flag is not commutative: if base + inc + /// has IncrementNUSW, then inc + base doesn't neccessarily have this + /// property. The reason for this is that this is used for sign/zero + /// extending affine AddRec SCEV expressions when a SCEVWrapPredicate is + /// assumed. A {base,+,inc} expression is already non-commutative with + /// regards to base and inc, since it is interpreted as: + /// (((base + inc) + inc) + inc) ... + enum IncrementWrapFlags { + IncrementAnyWrap = 0, // No guarantee. + IncrementNUSW = (1 << 0), // No unsigned with signed increment wrap. + IncrementNSSW = (1 << 1), // No signed with signed increment wrap + // (equivalent with SCEV::NSW) + IncrementNoWrapMask = (1 << 2) - 1 }; - /// 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. - 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; - - public: - SCEVEqualPredicate(const FoldingSetNodeIDRef ID, const SCEVUnknown *LHS, - const SCEVConstant *RHS); - - /// Implementation of the SCEVPredicate interface - bool implies(const SCEVPredicate *N) const override; - void print(raw_ostream &OS, unsigned Depth = 0) const override; - bool isAlwaysTrue() const override; - const SCEV *getExpr() const override; - - /// Returns the left hand side of the equality. - const SCEVUnknown *getLHS() const { return LHS; } + /// Convenient IncrementWrapFlags manipulation methods. + static SCEVWrapPredicate::IncrementWrapFlags LLVM_ATTRIBUTE_UNUSED_RESULT + clearFlags(SCEVWrapPredicate::IncrementWrapFlags Flags, + SCEVWrapPredicate::IncrementWrapFlags OffFlags) { + assert((Flags & IncrementNoWrapMask) == Flags && "Invalid flags value!"); + assert((OffFlags & IncrementNoWrapMask) == OffFlags && + "Invalid flags value!"); + return (SCEVWrapPredicate::IncrementWrapFlags)(Flags & ~OffFlags); + } - /// Returns the right hand side of the equality. - const SCEVConstant *getRHS() const { return RHS; } + static SCEVWrapPredicate::IncrementWrapFlags LLVM_ATTRIBUTE_UNUSED_RESULT + maskFlags(SCEVWrapPredicate::IncrementWrapFlags Flags, int Mask) { + assert((Flags & IncrementNoWrapMask) == Flags && "Invalid flags value!"); + assert((Mask & IncrementNoWrapMask) == Mask && "Invalid mask value!"); - /// Methods for support type inquiry through isa, cast, and dyn_cast: - static inline bool classof(const SCEVPredicate *P) { - return P->getKind() == P_Equal; - } - }; + return (SCEVWrapPredicate::IncrementWrapFlags)(Flags & Mask); + } - /// This class represents an assumption made on an AddRec expression. Given an - /// affine AddRec expression {a,+,b}, we assume that it has the nssw or nusw - /// flags (defined below) in the first X iterations of the loop, where X is a - /// SCEV expression returned by getPredicatedBackedgeTakenCount). - /// - /// Note that this does not imply that X is equal to the backedge taken - /// count. This means that if we have a nusw predicate for i32 {0,+,1} with a - /// predicated backedge taken count of X, we only guarantee that {0,+,1} has - /// nusw in the first X iterations. {0,+,1} may still wrap in the loop if we - /// have more than X iterations. - class SCEVWrapPredicate final : public SCEVPredicate { - public: - /// Similar to SCEV::NoWrapFlags, but with slightly different semantics - /// for FlagNUSW. The increment is considered to be signed, and a + b - /// (where b is the increment) is considered to wrap if: - /// zext(a + b) != zext(a) + sext(b) - /// - /// If Signed is a function that takes an n-bit tuple and maps to the - /// integer domain as the tuples value interpreted as twos complement, - /// and Unsigned a function that takes an n-bit tuple and maps to the - /// integer domain as as the base two value of input tuple, then a + b - /// has IncrementNUSW iff: - /// - /// 0 <= Unsigned(a) + Signed(b) < 2^n - /// - /// The IncrementNSSW flag has identical semantics with SCEV::FlagNSW. - /// - /// Note that the IncrementNUSW flag is not commutative: if base + inc - /// has IncrementNUSW, then inc + base doesn't neccessarily have this - /// property. The reason for this is that this is used for sign/zero - /// extending affine AddRec SCEV expressions when a SCEVWrapPredicate is - /// assumed. A {base,+,inc} expression is already non-commutative with - /// regards to base and inc, since it is interpreted as: - /// (((base + inc) + inc) + inc) ... - enum IncrementWrapFlags { - IncrementAnyWrap = 0, // No guarantee. - IncrementNUSW = (1 << 0), // No unsigned with signed increment wrap. - IncrementNSSW = (1 << 1), // No signed with signed increment wrap - // (equivalent with SCEV::NSW) - IncrementNoWrapMask = (1 << 2) - 1 - }; + static SCEVWrapPredicate::IncrementWrapFlags LLVM_ATTRIBUTE_UNUSED_RESULT + setFlags(SCEVWrapPredicate::IncrementWrapFlags Flags, + SCEVWrapPredicate::IncrementWrapFlags OnFlags) { + assert((Flags & IncrementNoWrapMask) == Flags && "Invalid flags value!"); + assert((OnFlags & IncrementNoWrapMask) == OnFlags && + "Invalid flags value!"); - /// Convenient IncrementWrapFlags manipulation methods. - static SCEVWrapPredicate::IncrementWrapFlags LLVM_ATTRIBUTE_UNUSED_RESULT - clearFlags(SCEVWrapPredicate::IncrementWrapFlags Flags, - SCEVWrapPredicate::IncrementWrapFlags OffFlags) { - assert((Flags & IncrementNoWrapMask) == Flags && "Invalid flags value!"); - assert((OffFlags & IncrementNoWrapMask) == OffFlags && - "Invalid flags value!"); - return (SCEVWrapPredicate::IncrementWrapFlags)(Flags & ~OffFlags); - } + return (SCEVWrapPredicate::IncrementWrapFlags)(Flags | OnFlags); + } - static SCEVWrapPredicate::IncrementWrapFlags LLVM_ATTRIBUTE_UNUSED_RESULT - maskFlags(SCEVWrapPredicate::IncrementWrapFlags Flags, int Mask) { - assert((Flags & IncrementNoWrapMask) == Flags && "Invalid flags value!"); - assert((Mask & IncrementNoWrapMask) == Mask && "Invalid mask value!"); + /// Returns the set of SCEVWrapPredicate no wrap flags implied by a + /// SCEVAddRecExpr. + static SCEVWrapPredicate::IncrementWrapFlags + getImpliedFlags(const SCEVAddRecExpr *AR, ScalarEvolution &SE); + +private: + const SCEVAddRecExpr *AR; + IncrementWrapFlags Flags; + +public: + explicit SCEVWrapPredicate(const FoldingSetNodeIDRef ID, + const SCEVAddRecExpr *AR, + IncrementWrapFlags Flags); + + /// 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; + void print(raw_ostream &OS, unsigned Depth = 0) const override; + bool isAlwaysTrue() const override; + + /// Methods for support type inquiry through isa, cast, and dyn_cast: + static inline bool classof(const SCEVPredicate *P) { + return P->getKind() == P_Wrap; + } +}; + +/// This class represents a composition of other SCEV predicates, and is the +/// class that most clients will interact with. This is equivalent to a +/// logical "AND" of all the predicates in the union. +class SCEVUnionPredicate final : public SCEVPredicate { +private: + typedef DenseMap> + PredicateMap; + + /// Vector with references to all predicates in this union. + SmallVector Preds; + /// Maps SCEVs to predicates for quick look-ups. + PredicateMap SCEVToPreds; + +public: + SCEVUnionPredicate(); + + const SmallVectorImpl &getPredicates() const { + return Preds; + } - return (SCEVWrapPredicate::IncrementWrapFlags)(Flags & Mask); - } + /// Adds a predicate to this union. + void add(const SCEVPredicate *N); - static SCEVWrapPredicate::IncrementWrapFlags LLVM_ATTRIBUTE_UNUSED_RESULT - setFlags(SCEVWrapPredicate::IncrementWrapFlags Flags, - SCEVWrapPredicate::IncrementWrapFlags OnFlags) { - assert((Flags & IncrementNoWrapMask) == Flags && "Invalid flags value!"); - assert((OnFlags & IncrementNoWrapMask) == OnFlags && - "Invalid flags value!"); + /// Returns a reference to a vector containing all predicates which apply to + /// \p Expr. + ArrayRef getPredicatesForExpr(const SCEV *Expr); - return (SCEVWrapPredicate::IncrementWrapFlags)(Flags | OnFlags); - } + /// Implementation of the SCEVPredicate interface + bool isAlwaysTrue() const override; + bool implies(const SCEVPredicate *N) const override; + void print(raw_ostream &OS, unsigned Depth) const override; + const SCEV *getExpr() const override; - /// Returns the set of SCEVWrapPredicate no wrap flags implied by a - /// SCEVAddRecExpr. - static SCEVWrapPredicate::IncrementWrapFlags - getImpliedFlags(const SCEVAddRecExpr *AR, ScalarEvolution &SE); + /// We estimate the complexity of a union predicate as the size number of + /// predicates in the union. + unsigned getComplexity() const override { return Preds.size(); } - private: - const SCEVAddRecExpr *AR; - IncrementWrapFlags Flags; + /// Methods for support type inquiry through isa, cast, and dyn_cast: + static inline bool classof(const SCEVPredicate *P) { + return P->getKind() == P_Union; + } +}; + +/// 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. +class ScalarEvolution { +public: + /// An enum describing the relationship between a SCEV and a loop. + enum LoopDisposition { + LoopVariant, ///< The SCEV is loop-variant (unknown). + LoopInvariant, ///< The SCEV is loop-invariant. + LoopComputable ///< The SCEV varies predictably with the loop. + }; - public: - explicit SCEVWrapPredicate(const FoldingSetNodeIDRef ID, - const SCEVAddRecExpr *AR, - IncrementWrapFlags Flags); - - /// 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; - void print(raw_ostream &OS, unsigned Depth = 0) const override; - bool isAlwaysTrue() const override; - - /// Methods for support type inquiry through isa, cast, and dyn_cast: - static inline bool classof(const SCEVPredicate *P) { - return P->getKind() == P_Wrap; - } + /// An enum describing the relationship between a SCEV and a basic block. + enum BlockDisposition { + DoesNotDominateBlock, ///< The SCEV does not dominate the block. + DominatesBlock, ///< The SCEV dominates the block. + ProperlyDominatesBlock ///< The SCEV properly dominates the block. }; - /// This class represents a composition of other SCEV predicates, and is the - /// class that most clients will interact with. This is equivalent to a - /// logical "AND" of all the predicates in the union. - class SCEVUnionPredicate final : public SCEVPredicate { - private: - typedef DenseMap> - PredicateMap; + /// Convenient NoWrapFlags manipulation that hides enum casts and is + /// visible in the ScalarEvolution name space. + static SCEV::NoWrapFlags LLVM_ATTRIBUTE_UNUSED_RESULT + maskFlags(SCEV::NoWrapFlags Flags, int Mask) { + return (SCEV::NoWrapFlags)(Flags & Mask); + } + static SCEV::NoWrapFlags LLVM_ATTRIBUTE_UNUSED_RESULT + setFlags(SCEV::NoWrapFlags Flags, SCEV::NoWrapFlags OnFlags) { + return (SCEV::NoWrapFlags)(Flags | OnFlags); + } + static SCEV::NoWrapFlags LLVM_ATTRIBUTE_UNUSED_RESULT + clearFlags(SCEV::NoWrapFlags Flags, SCEV::NoWrapFlags OffFlags) { + return (SCEV::NoWrapFlags)(Flags & ~OffFlags); + } - /// Vector with references to all predicates in this union. - SmallVector Preds; - /// Maps SCEVs to predicates for quick look-ups. - PredicateMap SCEVToPreds; +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; public: - SCEVUnionPredicate(); - - const SmallVectorImpl &getPredicates() const { - return Preds; - } - - /// Adds a predicate to this union. - void add(const SCEVPredicate *N); - - /// Returns a reference to a vector containing all predicates which apply to - /// \p Expr. - ArrayRef getPredicatesForExpr(const SCEV *Expr); - - /// Implementation of the SCEVPredicate interface - bool isAlwaysTrue() const override; - bool implies(const SCEVPredicate *N) const override; - void print(raw_ostream &OS, unsigned Depth) const override; - const SCEV *getExpr() const override; - - /// We estimate the complexity of a union predicate as the size number of - /// predicates in the union. - 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) { - return P->getKind() == P_Union; - } + SCEVCallbackVH(Value *V, ScalarEvolution *SE = nullptr); }; - /// 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. - class ScalarEvolution { - public: - /// An enum describing the relationship between a SCEV and a loop. - enum LoopDisposition { - LoopVariant, ///< The SCEV is loop-variant (unknown). - LoopInvariant, ///< The SCEV is loop-invariant. - LoopComputable ///< The SCEV varies predictably with the loop. - }; - - /// An enum describing the relationship between a SCEV and a basic block. - enum BlockDisposition { - DoesNotDominateBlock, ///< The SCEV does not dominate the block. - DominatesBlock, ///< The SCEV dominates the block. - ProperlyDominatesBlock ///< The SCEV properly dominates the block. - }; - - /// Convenient NoWrapFlags manipulation that hides enum casts and is - /// visible in the ScalarEvolution name space. - static SCEV::NoWrapFlags LLVM_ATTRIBUTE_UNUSED_RESULT - maskFlags(SCEV::NoWrapFlags Flags, int Mask) { - return (SCEV::NoWrapFlags)(Flags & Mask); - } - static SCEV::NoWrapFlags LLVM_ATTRIBUTE_UNUSED_RESULT - setFlags(SCEV::NoWrapFlags Flags, SCEV::NoWrapFlags OnFlags) { - return (SCEV::NoWrapFlags)(Flags | OnFlags); - } - static SCEV::NoWrapFlags LLVM_ATTRIBUTE_UNUSED_RESULT - clearFlags(SCEV::NoWrapFlags Flags, SCEV::NoWrapFlags OffFlags) { - return (SCEV::NoWrapFlags)(Flags & ~OffFlags); - } - - 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; - public: - SCEVCallbackVH(Value *V, ScalarEvolution *SE = nullptr); - }; + friend class SCEVCallbackVH; + friend class SCEVExpander; + friend class SCEVUnknown; - friend class SCEVCallbackVH; - friend class SCEVExpander; - friend class SCEVUnknown; - - /// The function we are analyzing. - /// - Function &F; + /// 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; + /// 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 target library information for the target we are targeting. + /// + TargetLibraryInfo &TLI; - /// The tracker for @llvm.assume intrinsics in this function. - AssumptionCache &AC; + /// The tracker for @llvm.assume intrinsics in this function. + AssumptionCache &AC; - /// The dominator tree. - /// - DominatorTree &DT; + /// The dominator tree. + /// + DominatorTree &DT; - /// The loop information for the function we are currently analyzing. - /// - LoopInfo &LI; + /// 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 CouldNotCompute; + /// This SCEV is used to represent unknown trip counts and things. + std::unique_ptr CouldNotCompute; - /// The typedef for HasRecMap. - /// - typedef DenseMap HasRecMapType; + /// The typedef for HasRecMap. + /// + typedef DenseMap HasRecMapType; - /// This is a cache to record whether a SCEV contains any scAddRecExpr. - HasRecMapType HasRecMap; + /// This is a cache to record whether a SCEV contains any scAddRecExpr. + HasRecMapType HasRecMap; - /// The typedef for ExprValueMap. - /// - typedef std::pair ValueOffsetPair; - typedef DenseMap> ExprValueMapType; + /// The typedef for ExprValueMap. + /// + typedef std::pair ValueOffsetPair; + typedef DenseMap> ExprValueMapType; - /// ExprValueMap -- This map records the original values from which - /// the SCEV expr is generated from. - /// - /// We want to represent the mapping as SCEV -> ValueOffsetPair instead - /// of SCEV -> Value: - /// Suppose we know S1 expands to V1, and - /// S1 = S2 + C_a - /// S3 = S2 + C_b - /// where C_a and C_b are different SCEVConstants. Then we'd like to - /// expand S3 as V1 - C_a + C_b instead of expanding S2 literally. - /// It is helpful when S2 is a complex SCEV expr. - /// - /// In order to do that, we represent ExprValueMap as a mapping from - /// SCEV to ValueOffsetPair. We will save both S1->{V1, 0} and - /// S2->{V1, C_a} into the map when we create SCEV for V1. When S3 - /// is expanded, it will first expand S2 to V1 - C_a because of - /// S2->{V1, C_a} in the map, then expand S3 to V1 - C_a + C_b. - /// - /// Note: S->{V, Offset} in the ExprValueMap means S can be expanded - /// to V - Offset. - ExprValueMapType ExprValueMap; + /// ExprValueMap -- This map records the original values from which + /// the SCEV expr is generated from. + /// + /// We want to represent the mapping as SCEV -> ValueOffsetPair instead + /// of SCEV -> Value: + /// Suppose we know S1 expands to V1, and + /// S1 = S2 + C_a + /// S3 = S2 + C_b + /// where C_a and C_b are different SCEVConstants. Then we'd like to + /// expand S3 as V1 - C_a + C_b instead of expanding S2 literally. + /// It is helpful when S2 is a complex SCEV expr. + /// + /// In order to do that, we represent ExprValueMap as a mapping from + /// SCEV to ValueOffsetPair. We will save both S1->{V1, 0} and + /// S2->{V1, C_a} into the map when we create SCEV for V1. When S3 + /// is expanded, it will first expand S2 to V1 - C_a because of + /// S2->{V1, C_a} in the map, then expand S3 to V1 - C_a + C_b. + /// + /// Note: S->{V, Offset} in the ExprValueMap means S can be expanded + /// to V - Offset. + ExprValueMapType ExprValueMap; - /// The typedef for ValueExprMap. - /// - typedef DenseMap > + /// The typedef for ValueExprMap. + /// + typedef DenseMap> ValueExprMapType; - /// This is a cache of the values we have analyzed so far. - /// - ValueExprMapType ValueExprMap; - - /// Mark predicate values currently being processed by isImpliedCond. - DenseSet PendingLoopPredicates; - - /// Set to true by isLoopBackedgeGuardedByCond when we're walking the set of - /// conditions dominating the backedge of a loop. - bool WalkingBEDominatingConds; - - /// Set to true by isKnownPredicateViaSplitting when we're trying to prove a - /// predicate by splitting it into a set of independent predicates. - bool ProvingSplitPredicate; - - /// 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; - - /// A predicate union guard for this ExitLimit. The result is only - /// valid if this predicate evaluates to 'true' at run-time. - SCEVUnionPredicate Pred; - - /*implicit*/ ExitLimit(const SCEV *E) : Exact(E), Max(E) {} - - ExitLimit(const SCEV *E, const SCEV *M, SCEVUnionPredicate &P) - : Exact(E), Max(M), Pred(P) { - assert((isa(Exact) || - !isa(Max)) && - "Exact is not allowed to be less precise than Max"); - } - - /// Test whether this ExitLimit contains any computed information, or - /// whether it's all SCEVCouldNotCompute values. - bool hasAnyInfo() const { - return !isa(Exact) || - !isa(Max); - } + /// This is a cache of the values we have analyzed so far. + /// + ValueExprMapType ValueExprMap; + + /// Mark predicate values currently being processed by isImpliedCond. + DenseSet PendingLoopPredicates; + + /// Set to true by isLoopBackedgeGuardedByCond when we're walking the set of + /// conditions dominating the backedge of a loop. + bool WalkingBEDominatingConds; + + /// Set to true by isKnownPredicateViaSplitting when we're trying to prove a + /// predicate by splitting it into a set of independent predicates. + bool ProvingSplitPredicate; + + /// 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; + + /// A predicate union guard for this ExitLimit. The result is only + /// valid if this predicate evaluates to 'true' at run-time. + SCEVUnionPredicate Pred; + + /*implicit*/ ExitLimit(const SCEV *E) : Exact(E), Max(E) {} + + ExitLimit(const SCEV *E, const SCEV *M, SCEVUnionPredicate &P) + : Exact(E), Max(M), Pred(P) { + assert( + (isa(Exact) || !isa(Max)) && + "Exact is not allowed to be less precise than Max"); + } - /// Test whether this ExitLimit contains all information. - bool hasFullInfo() const { return !isa(Exact); } - }; + /// Test whether this ExitLimit contains any computed information, or + /// whether it's all SCEVCouldNotCompute values. + bool hasAnyInfo() const { + return !isa(Exact) || !isa(Max); + } - /// Forward declaration of ExitNotTakenExtras - struct ExitNotTakenExtras; + /// Test whether this ExitLimit contains all information. + bool hasFullInfo() const { return !isa(Exact); } + }; - /// Information about the number of times a particular loop exit may be - /// reached before exiting the loop. - struct ExitNotTakenInfo { - AssertingVH ExitingBlock; - const SCEV *ExactNotTaken; + /// Forward declaration of ExitNotTakenExtras + struct ExitNotTakenExtras; - ExitNotTakenExtras *ExtraInfo; - bool Complete; + /// Information about the number of times a particular loop exit may be + /// reached before exiting the loop. + struct ExitNotTakenInfo { + AssertingVH ExitingBlock; + const SCEV *ExactNotTaken; - ExitNotTakenInfo() - : ExitingBlock(nullptr), ExactNotTaken(nullptr), ExtraInfo(nullptr), - Complete(true) {} + ExitNotTakenExtras *ExtraInfo; + bool Complete; - ExitNotTakenInfo(BasicBlock *ExitBlock, const SCEV *Expr, - ExitNotTakenExtras *Ptr) - : ExitingBlock(ExitBlock), ExactNotTaken(Expr), ExtraInfo(Ptr), - Complete(true) {} + ExitNotTakenInfo() + : ExitingBlock(nullptr), ExactNotTaken(nullptr), ExtraInfo(nullptr), + Complete(true) {} - /// Return true if all loop exits are computable. - bool isCompleteList() const { return Complete; } + ExitNotTakenInfo(BasicBlock *ExitBlock, const SCEV *Expr, + ExitNotTakenExtras *Ptr) + : ExitingBlock(ExitBlock), ExactNotTaken(Expr), ExtraInfo(Ptr), + Complete(true) {} - /// Sets the incomplete property, indicating that one of the loop exits - /// doesn't have a corresponding ExitNotTakenInfo entry. - void setIncomplete() { Complete = false; } + /// Return true if all loop exits are computable. + bool isCompleteList() const { return Complete; } - /// Returns a pointer to the predicate associated with this information, - /// or nullptr if this doesn't exist (meaning always true). - SCEVUnionPredicate *getPred() const { - if (ExtraInfo) - return &ExtraInfo->Pred; + /// Sets the incomplete property, indicating that one of the loop exits + /// doesn't have a corresponding ExitNotTakenInfo entry. + void setIncomplete() { Complete = false; } - return nullptr; - } + /// Returns a pointer to the predicate associated with this information, + /// or nullptr if this doesn't exist (meaning always true). + SCEVUnionPredicate *getPred() const { + if (ExtraInfo) + return &ExtraInfo->Pred; - /// Return true if the SCEV predicate associated with this information - /// is always true. - bool hasAlwaysTruePred() const { - return !getPred() || getPred()->isAlwaysTrue(); - } + return nullptr; + } - /// Defines a simple forward iterator for ExitNotTakenInfo. - class ExitNotTakenInfoIterator - : public std::iterator { - const ExitNotTakenInfo *Start; - unsigned Position; + /// Return true if the SCEV predicate associated with this information + /// is always true. + bool hasAlwaysTruePred() const { + return !getPred() || getPred()->isAlwaysTrue(); + } - public: - ExitNotTakenInfoIterator(const ExitNotTakenInfo *Start, - unsigned Position) - : Start(Start), Position(Position) {} + /// Defines a simple forward iterator for ExitNotTakenInfo. + class ExitNotTakenInfoIterator + : public std::iterator { + const ExitNotTakenInfo *Start; + unsigned Position; - const ExitNotTakenInfo &operator*() const { - if (Position == 0) - return *Start; + public: + ExitNotTakenInfoIterator(const ExitNotTakenInfo *Start, unsigned Position) + : Start(Start), Position(Position) {} - return Start->ExtraInfo->Exits[Position - 1]; - } + const ExitNotTakenInfo &operator*() const { + if (Position == 0) + return *Start; - const ExitNotTakenInfo *operator->() const { - if (Position == 0) - return Start; + return Start->ExtraInfo->Exits[Position - 1]; + } - return &Start->ExtraInfo->Exits[Position - 1]; - } + const ExitNotTakenInfo *operator->() const { + if (Position == 0) + return Start; - bool operator==(const ExitNotTakenInfoIterator &RHS) const { - return Start == RHS.Start && Position == RHS.Position; - } + return &Start->ExtraInfo->Exits[Position - 1]; + } - bool operator!=(const ExitNotTakenInfoIterator &RHS) const { - return Start != RHS.Start || Position != RHS.Position; - } + bool operator==(const ExitNotTakenInfoIterator &RHS) const { + return Start == RHS.Start && Position == RHS.Position; + } - ExitNotTakenInfoIterator &operator++() { // Preincrement - if (!Start) - return *this; + bool operator!=(const ExitNotTakenInfoIterator &RHS) const { + return Start != RHS.Start || Position != RHS.Position; + } - unsigned Elements = - Start->ExtraInfo ? Start->ExtraInfo->Exits.size() + 1 : 1; + ExitNotTakenInfoIterator &operator++() { // Preincrement + if (!Start) + return *this; - ++Position; + unsigned Elements = + Start->ExtraInfo ? Start->ExtraInfo->Exits.size() + 1 : 1; - // We've run out of elements. - if (Position == Elements) { - Start = nullptr; - Position = 0; - } + ++Position; - return *this; - } - ExitNotTakenInfoIterator operator++(int) { // Postincrement - ExitNotTakenInfoIterator Tmp = *this; - ++*this; - return Tmp; + // We've run out of elements. + if (Position == Elements) { + Start = nullptr; + Position = 0; } - }; - /// Iterators - ExitNotTakenInfoIterator begin() const { - return ExitNotTakenInfoIterator(this, 0); + return *this; } - ExitNotTakenInfoIterator end() const { - return ExitNotTakenInfoIterator(nullptr, 0); + ExitNotTakenInfoIterator operator++(int) { // Postincrement + ExitNotTakenInfoIterator Tmp = *this; + ++*this; + return Tmp; } }; - /// Describes the extra information that a ExitNotTakenInfo can have. - struct ExitNotTakenExtras { - /// The predicate associated with the ExitNotTakenInfo struct. - SCEVUnionPredicate Pred; - - /// The extra exits in the loop. Only the ExitNotTakenExtras structure - /// pointed to by the first ExitNotTakenInfo struct (associated with the - /// first loop exit) will populate this vector to prevent having - /// redundant information. - SmallVector Exits; - }; - - /// A struct containing the information attached to a backedge. - struct EdgeInfo { - EdgeInfo(BasicBlock *Block, const SCEV *Taken, SCEVUnionPredicate &P) : - ExitBlock(Block), Taken(Taken), Pred(std::move(P)) {} - - /// The exit basic block. - BasicBlock *ExitBlock; - - /// The (exact) number of time we take the edge back. - const SCEV *Taken; - - /// The SCEV predicated associated with Taken. If Pred doesn't evaluate - /// to true, the information in Taken is not valid (or equivalent with - /// a CouldNotCompute. - SCEVUnionPredicate Pred; - }; - - /// Information about the backedge-taken count of a loop. This currently - /// includes an exact count and a maximum count. - /// - class BackedgeTakenInfo { - /// A list of computable exits and their not-taken counts. Loops almost - /// never have more than one computable exit. - ExitNotTakenInfo ExitNotTaken; - - /// An expression indicating the least maximum backedge-taken count of the - /// loop that is known, or a SCEVCouldNotCompute. This expression is only - /// valid if the predicates associated with all loop exits are true. - const SCEV *Max; - - public: - BackedgeTakenInfo() : Max(nullptr) {} - - /// Initialize BackedgeTakenInfo from a list of exact exit counts. - BackedgeTakenInfo(SmallVectorImpl &ExitCounts, bool Complete, - const SCEV *MaxCount); - - /// Test whether this BackedgeTakenInfo contains any computed information, - /// or whether it's all SCEVCouldNotCompute values. - bool hasAnyInfo() const { - return ExitNotTaken.ExitingBlock || !isa(Max); - } - - /// Test whether this BackedgeTakenInfo contains complete information. - bool hasFullInfo() const { return ExitNotTaken.isCompleteList(); } - - /// 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. - /// - /// If the SCEV predicate associated with the answer can be different - /// from AlwaysTrue, we must add a (non null) Predicates argument. - /// The SCEV predicate associated with the answer will be added to - /// Predicates. A run-time check needs to be emitted for the SCEV - /// predicate in order for the answer to be valid. - /// - /// Note that we should always know if we need to pass a predicate - /// argument or not from the way the ExitCounts vector was computed. - /// If we allowed SCEV predicates to be generated when populating this - /// vector, this information can contain them and therefore a - /// SCEVPredicate argument should be added to getExact. - const SCEV *getExact(ScalarEvolution *SE, - SCEVUnionPredicate *Predicates = nullptr) const; - - /// Return the number of times this loop exit may fall through to the back - /// edge, or SCEVCouldNotCompute. The loop is guaranteed not to exit via - /// this block before this number of iterations, but may exit via another - /// block. - const SCEV *getExact(BasicBlock *ExitingBlock, ScalarEvolution *SE) const; - - /// 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; - - /// Invalidate this result and free associated memory. - void clear(); - }; - - /// Cache the backedge-taken count of the loops for this function as they - /// are computed. - DenseMap BackedgeTakenCounts; - - /// Cache the predicated backedge-taken count of the loops for this - /// function as they are computed. - DenseMap PredicatedBackedgeTakenCounts; - - /// This map contains entries for all of the PHI instructions that we - /// attempt to compute constant evolutions for. This allows us to avoid - /// potentially expensive recomputation of these properties. An instruction - /// maps to null if we are unable to compute its exit value. - DenseMap ConstantEvolutionLoopExitValue; - - /// This map contains entries for all the expressions that we attempt to - /// compute getSCEVAtScope information for, which can be expensive in - /// extreme cases. - DenseMap, 2> > ValuesAtScopes; - - /// Memoized computeLoopDisposition results. - DenseMap, 2>> - LoopDispositions; - - /// Cache for \c loopHasNoAbnormalExits. - DenseMap LoopHasNoAbnormalExits; - - /// Cache for \c loopHasNoSideEffects. - DenseMap LoopHasNoSideEffects; - - /// Returns true if \p L contains no instruction that can have side effects - /// (i.e. via throwing an exception, volatile or atomic access). - bool loopHasNoSideEffects(const Loop *L); - - /// Returns true if \p L contains no instruction that can abnormally exit - /// the loop (i.e. via throwing an exception, by terminating the thread - /// cleanly or by infinite looping in a called function). Strictly - /// speaking, the last one is not leaving the loop, but is identical to - /// leaving the loop for reasoning about undefined behavior. - bool loopHasNoAbnormalExits(const Loop *L); - - /// Compute a LoopDisposition value. - LoopDisposition computeLoopDisposition(const SCEV *S, const Loop *L); - - /// Memoized computeBlockDisposition results. - DenseMap< - const SCEV *, - SmallVector, 2>> - BlockDispositions; - - /// Compute a BlockDisposition value. - BlockDisposition computeBlockDisposition(const SCEV *S, const BasicBlock *BB); - - /// Memoized results from getRange - DenseMap UnsignedRanges; - - /// Memoized results from getRange - DenseMap SignedRanges; - - /// Used to parameterize getRange - enum RangeSignHint { HINT_RANGE_UNSIGNED, HINT_RANGE_SIGNED }; - - /// Set the memoized range for the given SCEV. - const ConstantRange &setRange(const SCEV *S, RangeSignHint Hint, - const ConstantRange &CR) { - DenseMap &Cache = - Hint == HINT_RANGE_UNSIGNED ? UnsignedRanges : SignedRanges; - - auto Pair = Cache.insert({S, CR}); - if (!Pair.second) - Pair.first->second = CR; - return Pair.first->second; + /// Iterators + ExitNotTakenInfoIterator begin() const { + return ExitNotTakenInfoIterator(this, 0); } + ExitNotTakenInfoIterator end() const { + return ExitNotTakenInfoIterator(nullptr, 0); + } + }; - /// Determine the range for a particular SCEV. - ConstantRange getRange(const SCEV *S, RangeSignHint Hint); - - /// Determines the range for the affine SCEVAddRecExpr {\p Start,+,\p Stop}. - /// Helper for \c getRange. - ConstantRange getRangeForAffineAR(const SCEV *Start, const SCEV *Stop, - const SCEV *MaxBECount, - unsigned BitWidth); - - /// Try to compute a range for the affine SCEVAddRecExpr {\p Start,+,\p - /// Stop} by "factoring out" a ternary expression from the add recurrence. - /// Helper called by \c getRange. - ConstantRange getRangeViaFactoring(const SCEV *Start, const SCEV *Stop, - const SCEV *MaxBECount, - unsigned BitWidth); - - /// We know that there is no SCEV for the specified value. Analyze the - /// expression. - const SCEV *createSCEV(Value *V); - - /// Provide the special handling we need to analyze PHI SCEVs. - const SCEV *createNodeForPHI(PHINode *PN); - - /// Helper function called from createNodeForPHI. - const SCEV *createAddRecFromPHI(PHINode *PN); - - /// Helper function called from createNodeForPHI. - const SCEV *createNodeFromSelectLikePHI(PHINode *PN); + /// Describes the extra information that a ExitNotTakenInfo can have. + struct ExitNotTakenExtras { + /// The predicate associated with the ExitNotTakenInfo struct. + SCEVUnionPredicate Pred; - /// Provide special handling for a select-like instruction (currently this - /// is either a select instruction or a phi node). \p I is the instruction - /// being processed, and it is assumed equivalent to "Cond ? TrueVal : - /// FalseVal". - const SCEV *createNodeForSelectOrPHI(Instruction *I, Value *Cond, - Value *TrueVal, Value *FalseVal); + /// The extra exits in the loop. Only the ExitNotTakenExtras structure + /// pointed to by the first ExitNotTakenInfo struct (associated with the + /// first loop exit) will populate this vector to prevent having + /// redundant information. + SmallVector Exits; + }; - /// Provide the special handling we need to analyze GEP SCEVs. - const SCEV *createNodeForGEP(GEPOperator *GEP); + /// A struct containing the information attached to a backedge. + struct EdgeInfo { + EdgeInfo(BasicBlock *Block, const SCEV *Taken, SCEVUnionPredicate &P) + : ExitBlock(Block), Taken(Taken), Pred(std::move(P)) {} - /// 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 - /// the given instruction and removes them from the ValueExprMap map if they - /// reference SymName. This is used during PHI resolution. - void forgetSymbolicName(Instruction *I, const SCEV *SymName); - - /// Return the BackedgeTakenInfo for the given loop, lazily computing new - /// values if the loop hasn't been analyzed yet. The returned result is - /// guaranteed not to be predicated. - const BackedgeTakenInfo &getBackedgeTakenInfo(const Loop *L); - - /// Similar to getBackedgeTakenInfo, but will add predicates as required - /// with the purpose of returning complete information. - const BackedgeTakenInfo &getPredicatedBackedgeTakenInfo(const Loop *L); - - /// Compute the number of times the specified loop will iterate. - /// If AllowPredicates is set, we will create new SCEV predicates as - /// necessary in order to return an exact answer. - BackedgeTakenInfo computeBackedgeTakenCount(const Loop *L, - bool AllowPredicates = false); - - /// Compute the number of times the backedge of the specified loop will - /// execute if it exits via the specified block. If AllowPredicates is set, - /// this call will try to use a minimal set of SCEV predicates in order to - /// return an exact answer. - ExitLimit computeExitLimit(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. - /// - /// \p ControlsExit is true if ExitCond directly controls the exit - /// branch. In this case, we can assume that the loop exits only if the - /// condition is true and can infer that failing to meet the condition prior - /// to integer wraparound results in undefined behavior. - /// - /// If \p AllowPredicates is set, this call will try to use a minimal set of - /// SCEV predicates in order to return an exact answer. - ExitLimit computeExitLimitFromCond(const Loop *L, - Value *ExitCond, - BasicBlock *TBB, - BasicBlock *FBB, - bool ControlsExit, - 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 the ICmpInst - /// ExitCond, TBB, and FBB. If AllowPredicates is set, this call will try - /// to use a minimal set of SCEV predicates in order to return an exact - /// answer. - ExitLimit computeExitLimitFromICmp(const Loop *L, - ICmpInst *ExitCond, - BasicBlock *TBB, - BasicBlock *FBB, - bool IsSubExpr, - bool AllowPredicates = false); - - /// 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); - - /// Given an exit condition of 'icmp op load X, cst', try to see if we can - /// compute the backedge-taken count. - ExitLimit computeLoadConstantCompareExitLimit(LoadInst *LI, - Constant *RHS, - const Loop *L, - ICmpInst::Predicate p); - - /// Compute the exit limit of a loop that is controlled by a - /// "(IV >> 1) != 0" type comparison. We cannot compute the exact trip - /// count in these cases (since SCEV has no way of expressing them), but we - /// can still sometimes compute an upper bound. - /// - /// Return an ExitLimit for a loop whose backedge is guarded by `LHS Pred - /// RHS`. - ExitLimit computeShiftCompareExitLimit(Value *LHS, Value *RHS, - const Loop *L, - ICmpInst::Predicate Pred); - - /// If the loop is known to execute a constant number of times (the - /// condition evolves only from constants), try to evaluate a few iterations - /// of the loop until we get the exit condition gets a value of ExitWhen - /// (true or false). If we cannot evaluate the exit count of the loop, - /// return CouldNotCompute. - const SCEV *computeExitCountExhaustively(const Loop *L, - Value *Cond, - bool ExitWhen); - - /// Return the number of times an exit condition comparing the specified - /// value to zero will execute. If not computable, return CouldNotCompute. - /// If AllowPredicates is set, this call will try to use a minimal set of - /// SCEV predicates in order to return an exact answer. - ExitLimit howFarToZero(const SCEV *V, const Loop *L, bool IsSubExpr, - bool AllowPredicates = false); - - /// Return the number of times an exit condition checking the specified - /// value for nonzero will execute. If not computable, return - /// CouldNotCompute. - ExitLimit howFarToNonZero(const SCEV *V, const Loop *L); - - /// Return the number of times an exit condition containing the specified - /// less-than comparison will execute. If not computable, return - /// CouldNotCompute. - /// - /// \p isSigned specifies whether the less-than is signed. - /// - /// \p ControlsExit is true when the LHS < RHS condition directly controls - /// the branch (loops exits only if condition is true). In this case, we can - /// use NoWrapFlags to skip overflow checks. - /// - /// If \p AllowPredicates is set, this call will try to use a minimal set of - /// SCEV predicates in order to return an exact answer. - ExitLimit howManyLessThans(const SCEV *LHS, const SCEV *RHS, const Loop *L, - bool isSigned, bool ControlsExit, - bool AllowPredicates = false); - - ExitLimit howManyGreaterThans(const SCEV *LHS, const SCEV *RHS, - const Loop *L, bool isSigned, bool IsSubExpr, - bool AllowPredicates = false); - - /// Return a predecessor of BB (which may not be an immediate predecessor) - /// which has exactly one successor from which BB is reachable, or null if - /// no such block is found. - std::pair - getPredecessorWithUniqueSuccessorForBB(BasicBlock *BB); - - /// Test whether the condition described by Pred, LHS, and RHS is true - /// whenever the given FoundCondValue value evaluates to true. - bool isImpliedCond(ICmpInst::Predicate Pred, - const SCEV *LHS, const SCEV *RHS, - Value *FoundCondValue, - bool Inverse); - - /// Test whether the condition described by Pred, LHS, and RHS is true - /// whenever the condition described by FoundPred, FoundLHS, FoundRHS is - /// true. - bool isImpliedCond(ICmpInst::Predicate Pred, const SCEV *LHS, - const SCEV *RHS, ICmpInst::Predicate FoundPred, - const SCEV *FoundLHS, const SCEV *FoundRHS); - - /// Test whether the condition described by Pred, LHS, and RHS is true - /// whenever the condition described by Pred, FoundLHS, and FoundRHS is - /// true. - bool isImpliedCondOperands(ICmpInst::Predicate Pred, - const SCEV *LHS, const SCEV *RHS, - const SCEV *FoundLHS, const SCEV *FoundRHS); - - /// 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, - const SCEV *FoundRHS); - - /// 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. Tries to get - /// cases like "X `sgt` 0 => X - 1 `sgt` -1". - bool isImpliedCondOperandsViaRanges(ICmpInst::Predicate Pred, - const SCEV *LHS, const SCEV *RHS, - const SCEV *FoundLHS, - const SCEV *FoundRHS); - - /// Return true if the condition denoted by \p LHS \p Pred \p RHS is implied - /// by a call to \c @llvm.experimental.guard in \p BB. - bool isImpliedViaGuard(BasicBlock *BB, 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. - /// - /// This routine tries to rule out certain kinds of integer overflow, and - /// then tries to reason about arithmetic properties of the predicates. - bool isImpliedCondOperandsViaNoOverflow(ICmpInst::Predicate Pred, - const SCEV *LHS, const SCEV *RHS, - const SCEV *FoundLHS, - const SCEV *FoundRHS); - - /// If we know that the specified Phi is in the header of its containing - /// loop, we know the loop executes a constant number of times, and the PHI - /// node is just a recurrence involving constants, fold it. - Constant *getConstantEvolutionLoopExitValue(PHINode *PN, const APInt& BEs, - const Loop *L); - - /// 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); + /// The exit basic block. + BasicBlock *ExitBlock; - /// Try to prove the condition described by "LHS Pred RHS" by ruling out - /// integer overflow. - /// - /// For instance, this will return true for "A s< (A + C)" if C is - /// positive. - bool isKnownPredicateViaNoOverflow(ICmpInst::Predicate Pred, - const SCEV *LHS, const SCEV *RHS); - - /// Try to split Pred LHS RHS into logical conjunctions (and's) and try to - /// prove them individually. - bool isKnownPredicateViaSplitting(ICmpInst::Predicate Pred, const SCEV *LHS, - const SCEV *RHS); - - /// Try to match the Expr as "(L + R)". - bool splitBinaryAdd(const SCEV *Expr, const SCEV *&L, const SCEV *&R, - SCEV::NoWrapFlags &Flags); - - /// Compute \p LHS - \p RHS and returns the result as an APInt if it is a - /// constant, and None if it isn't. - /// - /// This is intended to be a cheaper version of getMinusSCEV. We can be - /// frugal here since we just bail out of actually constructing and - /// canonicalizing an expression in the cases where the result isn't going - /// to be a constant. - Optional computeConstantDifference(const SCEV *LHS, const SCEV *RHS); - - /// Drop memoized information computed for S. - void forgetMemoizedResults(const SCEV *S); - - /// Return an existing SCEV for V if there is one, otherwise return nullptr. - const SCEV *getExistingSCEV(Value *V); - - /// Return false iff given SCEV contains a SCEVUnknown with NULL value- - /// 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 - bool proveNoWrapByVaryingStart(const SCEV *Start, const SCEV *Step, - const Loop *L); + /// The (exact) number of time we take the edge back. + const SCEV *Taken; - /// Try to prove NSW or NUW on \p AR relying on ConstantRange manipulation. - SCEV::NoWrapFlags proveNoWrapViaConstantRanges(const SCEVAddRecExpr *AR); + /// The SCEV predicated associated with Taken. If Pred doesn't evaluate + /// to true, the information in Taken is not valid (or equivalent with + /// a CouldNotCompute. + SCEVUnionPredicate Pred; + }; - bool isMonotonicPredicateImpl(const SCEVAddRecExpr *LHS, - ICmpInst::Predicate Pred, bool &Increasing); + /// Information about the backedge-taken count of a loop. This currently + /// includes an exact count and a maximum count. + /// + class BackedgeTakenInfo { + /// A list of computable exits and their not-taken counts. Loops almost + /// never have more than one computable exit. + ExitNotTakenInfo ExitNotTaken; - /// 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. - SCEV::NoWrapFlags getNoWrapFlagsFromUB(const Value *V); - - /// Return true if the SCEV corresponding to \p I is never poison. Proving - /// this is more complex than proving that just \p I is never poison, since - /// SCEV commons expressions across control flow, and you can have cases - /// like: - /// - /// idx0 = a + b; - /// ptr[idx0] = 100; - /// if () { - /// idx1 = a +nsw b; - /// ptr[idx1] = 200; - /// } - /// - /// where the SCEV expression (+ a b) is guaranteed to not be poison (and - /// hence not sign-overflow) only if "" is true. Since both - /// `idx0` and `idx1` will be mapped to the same SCEV expression, (+ a b), - /// it is not okay to annotate (+ a b) with in the above example. - bool isSCEVExprNeverPoison(const Instruction *I); - - /// This is like \c isSCEVExprNeverPoison but it specifically works for - /// instructions that will get mapped to SCEV add recurrences. Return true - /// if \p I will never generate poison under the assumption that \p I is an - /// add recurrence on the loop \p L. - bool isAddRecNeverPoison(const Instruction *I, const Loop *L); + /// An expression indicating the least maximum backedge-taken count of the + /// loop that is known, or a SCEVCouldNotCompute. This expression is only + /// valid if the predicates associated with all loop exits are true. + const SCEV *Max; 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 *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 &Ops, - SCEV::NoWrapFlags Flags = SCEV::FlagAnyWrap); - const SCEV *getAddExpr(const SCEV *LHS, const SCEV *RHS, - SCEV::NoWrapFlags Flags = SCEV::FlagAnyWrap) { - SmallVector 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 Ops = {Op0, Op1, Op2}; - return getAddExpr(Ops, Flags); - } - const SCEV *getMulExpr(SmallVectorImpl &Ops, - SCEV::NoWrapFlags Flags = SCEV::FlagAnyWrap); - const SCEV *getMulExpr(const SCEV *LHS, const SCEV *RHS, - SCEV::NoWrapFlags Flags = SCEV::FlagAnyWrap) { - SmallVector 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 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 &Operands, - const Loop *L, SCEV::NoWrapFlags Flags); - const SCEV *getAddRecExpr(const SmallVectorImpl &Operands, - const Loop *L, SCEV::NoWrapFlags Flags) { - SmallVector NewOp(Operands.begin(), Operands.end()); - return getAddRecExpr(NewOp, L, Flags); - } - /// 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 &IndexExprs, - bool InBounds = false); - const SCEV *getSMaxExpr(const SCEV *LHS, const SCEV *RHS); - const SCEV *getSMaxExpr(SmallVectorImpl &Operands); - const SCEV *getUMaxExpr(const SCEV *LHS, const SCEV *RHS); - const SCEV *getUMaxExpr(SmallVectorImpl &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); + BackedgeTakenInfo() : Max(nullptr) {} - /// Return the SCEV object corresponding to -V. - /// - const SCEV *getNegativeSCEV(const SCEV *V, - SCEV::NoWrapFlags Flags = SCEV::FlagAnyWrap); + /// Initialize BackedgeTakenInfo from a list of exact exit counts. + BackedgeTakenInfo(SmallVectorImpl &ExitCounts, bool Complete, + const SCEV *MaxCount); - /// 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 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); - - /// 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 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 whether this BackedgeTakenInfo contains any computed information, + /// or whether it's all SCEVCouldNotCompute values. + bool hasAnyInfo() const { + return ExitNotTaken.ExitingBlock || !isa(Max); } - /// 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 + /// Test whether this BackedgeTakenInfo contains complete information. + bool hasFullInfo() const { return ExitNotTaken.isCompleteList(); } + + /// 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. + /// + /// If the SCEV predicate associated with the answer can be different + /// from AlwaysTrue, we must add a (non null) Predicates argument. + /// The SCEV predicate associated with the answer will be added to + /// Predicates. A run-time check needs to be emitted for the SCEV + /// predicate in order for the answer to be valid. + /// + /// Note that we should always know if we need to pass a predicate + /// argument or not from the way the ExitCounts vector was computed. + /// If we allowed SCEV predicates to be generated when populating this + /// vector, this information can contain them and therefore a + /// SCEVPredicate argument should be added to getExact. + const SCEV *getExact(ScalarEvolution *SE, + SCEVUnionPredicate *Predicates = nullptr) const; + + /// Return the number of times this loop exit may fall through to the back + /// edge, or SCEVCouldNotCompute. The loop is guaranteed not to exit via + /// this block before this number of iterations, but may exit via another /// 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 &Terms, - SmallVectorImpl &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 &Terms); - + const SCEV *getExact(BasicBlock *ExitingBlock, ScalarEvolution *SE) const; + /// Get the max backedge taken count for the loop. + const SCEV *getMax(ScalarEvolution *SE) const; - /// Return in Subscripts the access functions for each dimension in Sizes - /// (third step of delinearization). - void computeAccessFunctions(const SCEV *Expr, - SmallVectorImpl &Subscripts, - SmallVectorImpl &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 &Subscripts, - SmallVectorImpl &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(); - } + /// Return true if any backedge taken count expressions refer to the given + /// subexpression. + bool hasOperand(const SCEV *S, ScalarEvolution *SE) const; - 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, - SCEVUnionPredicate &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); - - /// 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; - FoldingSet UniquePreds; - BumpPtrAllocator SCEVAllocator; - - /// 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; + /// Invalidate this result and free associated memory. + void clear(); }; - /// Analysis pass that exposes the \c ScalarEvolution for a function. - class ScalarEvolutionAnalysis - : public AnalysisInfoMixin { - friend AnalysisInfoMixin; - static char PassID; + /// Cache the backedge-taken count of the loops for this function as they + /// are computed. + DenseMap BackedgeTakenCounts; + + /// Cache the predicated backedge-taken count of the loops for this + /// function as they are computed. + DenseMap PredicatedBackedgeTakenCounts; + + /// This map contains entries for all of the PHI instructions that we + /// attempt to compute constant evolutions for. This allows us to avoid + /// potentially expensive recomputation of these properties. An instruction + /// maps to null if we are unable to compute its exit value. + DenseMap ConstantEvolutionLoopExitValue; + + /// This map contains entries for all the expressions that we attempt to + /// compute getSCEVAtScope information for, which can be expensive in + /// extreme cases. + DenseMap, 2>> + ValuesAtScopes; + + /// Memoized computeLoopDisposition results. + DenseMap, 2>> + LoopDispositions; + + /// Cache for \c loopHasNoAbnormalExits. + DenseMap LoopHasNoAbnormalExits; + + /// Cache for \c loopHasNoSideEffects. + DenseMap LoopHasNoSideEffects; + + /// Returns true if \p L contains no instruction that can have side effects + /// (i.e. via throwing an exception, volatile or atomic access). + bool loopHasNoSideEffects(const Loop *L); + + /// Returns true if \p L contains no instruction that can abnormally exit + /// the loop (i.e. via throwing an exception, by terminating the thread + /// cleanly or by infinite looping in a called function). Strictly + /// speaking, the last one is not leaving the loop, but is identical to + /// leaving the loop for reasoning about undefined behavior. + bool loopHasNoAbnormalExits(const Loop *L); + + /// Compute a LoopDisposition value. + LoopDisposition computeLoopDisposition(const SCEV *S, const Loop *L); + + /// Memoized computeBlockDisposition results. + DenseMap< + const SCEV *, + SmallVector, 2>> + BlockDispositions; + + /// Compute a BlockDisposition value. + BlockDisposition computeBlockDisposition(const SCEV *S, const BasicBlock *BB); + + /// Memoized results from getRange + DenseMap UnsignedRanges; + + /// Memoized results from getRange + DenseMap SignedRanges; + + /// Used to parameterize getRange + enum RangeSignHint { HINT_RANGE_UNSIGNED, HINT_RANGE_SIGNED }; + + /// Set the memoized range for the given SCEV. + const ConstantRange &setRange(const SCEV *S, RangeSignHint Hint, + const ConstantRange &CR) { + DenseMap &Cache = + Hint == HINT_RANGE_UNSIGNED ? UnsignedRanges : SignedRanges; + + auto Pair = Cache.insert({S, CR}); + if (!Pair.second) + Pair.first->second = CR; + return Pair.first->second; + } - public: - typedef ScalarEvolution Result; + /// Determine the range for a particular SCEV. + ConstantRange getRange(const SCEV *S, RangeSignHint Hint); - ScalarEvolution run(Function &F, FunctionAnalysisManager &AM); - }; + /// Determines the range for the affine SCEVAddRecExpr {\p Start,+,\p Stop}. + /// Helper for \c getRange. + ConstantRange getRangeForAffineAR(const SCEV *Start, const SCEV *Stop, + const SCEV *MaxBECount, unsigned BitWidth); - /// Printer pass for the \c ScalarEvolutionAnalysis results. - class ScalarEvolutionPrinterPass - : public PassInfoMixin { - raw_ostream &OS; + /// Try to compute a range for the affine SCEVAddRecExpr {\p Start,+,\p + /// Stop} by "factoring out" a ternary expression from the add recurrence. + /// Helper called by \c getRange. + ConstantRange getRangeViaFactoring(const SCEV *Start, const SCEV *Stop, + const SCEV *MaxBECount, unsigned BitWidth); - public: - explicit ScalarEvolutionPrinterPass(raw_ostream &OS) : OS(OS) {} - PreservedAnalyses run(Function &F, FunctionAnalysisManager &AM); - }; + /// We know that there is no SCEV for the specified value. Analyze the + /// expression. + const SCEV *createSCEV(Value *V); - class ScalarEvolutionWrapperPass : public FunctionPass { - std::unique_ptr SE; + /// Provide the special handling we need to analyze PHI SCEVs. + const SCEV *createNodeForPHI(PHINode *PN); - public: - static char ID; + /// Helper function called from createNodeForPHI. + const SCEV *createAddRecFromPHI(PHINode *PN); - ScalarEvolutionWrapperPass(); + /// Helper function called from createNodeForPHI. + const SCEV *createNodeFromSelectLikePHI(PHINode *PN); - ScalarEvolution &getSE() { return *SE; } - const ScalarEvolution &getSE() const { return *SE; } + /// Provide special handling for a select-like instruction (currently this + /// is either a select instruction or a phi node). \p I is the instruction + /// being processed, and it is assumed equivalent to "Cond ? TrueVal : + /// FalseVal". + const SCEV *createNodeForSelectOrPHI(Instruction *I, Value *Cond, + Value *TrueVal, Value *FalseVal); - 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; - }; + /// Provide the special handling we need to analyze GEP SCEVs. + const SCEV *createNodeForGEP(GEPOperator *GEP); - /// An interface layer with SCEV used to manage how we see SCEV expressions - /// for values in the context of existing predicates. We can add new - /// predicates, but we cannot remove them. - /// - /// This layer has multiple purposes: - /// - provides a simple interface for SCEV versioning. - /// - guarantees that the order of transformations applied on a SCEV - /// expression for a single Value is consistent across two different - /// getSCEV calls. This means that, for example, once we've obtained - /// an AddRec expression for a certain value through expression - /// rewriting, we will continue to get an AddRec expression for that - /// Value. - /// - lowers the number of expression rewrites. - class PredicatedScalarEvolution { - public: - PredicatedScalarEvolution(ScalarEvolution &SE, Loop &L); - const SCEVUnionPredicate &getUnionPredicate() const; + /// 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 + /// the given instruction and removes them from the ValueExprMap map if they + /// reference SymName. This is used during PHI resolution. + void forgetSymbolicName(Instruction *I, const SCEV *SymName); + + /// Return the BackedgeTakenInfo for the given loop, lazily computing new + /// values if the loop hasn't been analyzed yet. The returned result is + /// guaranteed not to be predicated. + const BackedgeTakenInfo &getBackedgeTakenInfo(const Loop *L); + + /// Similar to getBackedgeTakenInfo, but will add predicates as required + /// with the purpose of returning complete information. + const BackedgeTakenInfo &getPredicatedBackedgeTakenInfo(const Loop *L); + + /// Compute the number of times the specified loop will iterate. + /// If AllowPredicates is set, we will create new SCEV predicates as + /// necessary in order to return an exact answer. + BackedgeTakenInfo computeBackedgeTakenCount(const Loop *L, + bool AllowPredicates = false); + + /// Compute the number of times the backedge of the specified loop will + /// execute if it exits via the specified block. If AllowPredicates is set, + /// this call will try to use a minimal set of SCEV predicates in order to + /// return an exact answer. + ExitLimit computeExitLimit(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. + /// + /// \p ControlsExit is true if ExitCond directly controls the exit + /// branch. In this case, we can assume that the loop exits only if the + /// condition is true and can infer that failing to meet the condition prior + /// to integer wraparound results in undefined behavior. + /// + /// If \p AllowPredicates is set, this call will try to use a minimal set of + /// SCEV predicates in order to return an exact answer. + ExitLimit computeExitLimitFromCond(const Loop *L, Value *ExitCond, + BasicBlock *TBB, BasicBlock *FBB, + bool ControlsExit, + 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 the ICmpInst + /// ExitCond, TBB, and FBB. If AllowPredicates is set, this call will try + /// to use a minimal set of SCEV predicates in order to return an exact + /// answer. + ExitLimit computeExitLimitFromICmp(const Loop *L, ICmpInst *ExitCond, + BasicBlock *TBB, BasicBlock *FBB, + bool IsSubExpr, + bool AllowPredicates = false); + + /// 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); + + /// Given an exit condition of 'icmp op load X, cst', try to see if we can + /// compute the backedge-taken count. + ExitLimit computeLoadConstantCompareExitLimit(LoadInst *LI, Constant *RHS, + const Loop *L, + ICmpInst::Predicate p); + + /// Compute the exit limit of a loop that is controlled by a + /// "(IV >> 1) != 0" type comparison. We cannot compute the exact trip + /// count in these cases (since SCEV has no way of expressing them), but we + /// can still sometimes compute an upper bound. + /// + /// Return an ExitLimit for a loop whose backedge is guarded by `LHS Pred + /// RHS`. + ExitLimit computeShiftCompareExitLimit(Value *LHS, Value *RHS, const Loop *L, + ICmpInst::Predicate Pred); + + /// If the loop is known to execute a constant number of times (the + /// condition evolves only from constants), try to evaluate a few iterations + /// of the loop until we get the exit condition gets a value of ExitWhen + /// (true or false). If we cannot evaluate the exit count of the loop, + /// return CouldNotCompute. + const SCEV *computeExitCountExhaustively(const Loop *L, Value *Cond, + bool ExitWhen); + + /// Return the number of times an exit condition comparing the specified + /// value to zero will execute. If not computable, return CouldNotCompute. + /// If AllowPredicates is set, this call will try to use a minimal set of + /// SCEV predicates in order to return an exact answer. + ExitLimit howFarToZero(const SCEV *V, const Loop *L, bool IsSubExpr, + bool AllowPredicates = false); + + /// Return the number of times an exit condition checking the specified + /// value for nonzero will execute. If not computable, return + /// CouldNotCompute. + ExitLimit howFarToNonZero(const SCEV *V, const Loop *L); + + /// Return the number of times an exit condition containing the specified + /// less-than comparison will execute. If not computable, return + /// CouldNotCompute. + /// + /// \p isSigned specifies whether the less-than is signed. + /// + /// \p ControlsExit is true when the LHS < RHS condition directly controls + /// the branch (loops exits only if condition is true). In this case, we can + /// use NoWrapFlags to skip overflow checks. + /// + /// If \p AllowPredicates is set, this call will try to use a minimal set of + /// SCEV predicates in order to return an exact answer. + ExitLimit howManyLessThans(const SCEV *LHS, const SCEV *RHS, const Loop *L, + bool isSigned, bool ControlsExit, + bool AllowPredicates = false); + + ExitLimit howManyGreaterThans(const SCEV *LHS, const SCEV *RHS, const Loop *L, + bool isSigned, bool IsSubExpr, + bool AllowPredicates = false); + + /// Return a predecessor of BB (which may not be an immediate predecessor) + /// which has exactly one successor from which BB is reachable, or null if + /// no such block is found. + std::pair + getPredecessorWithUniqueSuccessorForBB(BasicBlock *BB); + + /// Test whether the condition described by Pred, LHS, and RHS is true + /// whenever the given FoundCondValue value evaluates to true. + bool isImpliedCond(ICmpInst::Predicate Pred, const SCEV *LHS, const SCEV *RHS, + Value *FoundCondValue, bool Inverse); + + /// Test whether the condition described by Pred, LHS, and RHS is true + /// whenever the condition described by FoundPred, FoundLHS, FoundRHS is + /// true. + bool isImpliedCond(ICmpInst::Predicate Pred, const SCEV *LHS, const SCEV *RHS, + ICmpInst::Predicate FoundPred, const SCEV *FoundLHS, + const SCEV *FoundRHS); + + /// Test whether the condition described by Pred, LHS, and RHS is true + /// whenever the condition described by Pred, FoundLHS, and FoundRHS is + /// true. + bool isImpliedCondOperands(ICmpInst::Predicate Pred, const SCEV *LHS, + const SCEV *RHS, const SCEV *FoundLHS, + const SCEV *FoundRHS); + + /// 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, + const SCEV *FoundRHS); + + /// 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. Tries to get + /// cases like "X `sgt` 0 => X - 1 `sgt` -1". + bool isImpliedCondOperandsViaRanges(ICmpInst::Predicate Pred, const SCEV *LHS, + const SCEV *RHS, const SCEV *FoundLHS, + const SCEV *FoundRHS); + + /// Return true if the condition denoted by \p LHS \p Pred \p RHS is implied + /// by a call to \c @llvm.experimental.guard in \p BB. + bool isImpliedViaGuard(BasicBlock *BB, 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. + /// + /// This routine tries to rule out certain kinds of integer overflow, and + /// then tries to reason about arithmetic properties of the predicates. + bool isImpliedCondOperandsViaNoOverflow(ICmpInst::Predicate Pred, + const SCEV *LHS, const SCEV *RHS, + const SCEV *FoundLHS, + const SCEV *FoundRHS); + + /// If we know that the specified Phi is in the header of its containing + /// loop, we know the loop executes a constant number of times, and the PHI + /// node is just a recurrence involving constants, fold it. + Constant *getConstantEvolutionLoopExitValue(PHINode *PN, const APInt &BEs, + const Loop *L); + + /// 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); - /// Returns the SCEV expression of V, in the context of the current SCEV - /// predicate. The order of transformations applied on the expression of V - /// returned by ScalarEvolution is guaranteed to be preserved, even when - /// adding new predicates. - const SCEV *getSCEV(Value *V); + /// Try to prove the condition described by "LHS Pred RHS" by ruling out + /// integer overflow. + /// + /// For instance, this will return true for "A s< (A + C)" if C is + /// positive. + bool isKnownPredicateViaNoOverflow(ICmpInst::Predicate Pred, const SCEV *LHS, + const SCEV *RHS); + + /// Try to split Pred LHS RHS into logical conjunctions (and's) and try to + /// prove them individually. + bool isKnownPredicateViaSplitting(ICmpInst::Predicate Pred, const SCEV *LHS, + const SCEV *RHS); + + /// Try to match the Expr as "(L + R)". + bool splitBinaryAdd(const SCEV *Expr, const SCEV *&L, const SCEV *&R, + SCEV::NoWrapFlags &Flags); + + /// Compute \p LHS - \p RHS and returns the result as an APInt if it is a + /// constant, and None if it isn't. + /// + /// This is intended to be a cheaper version of getMinusSCEV. We can be + /// frugal here since we just bail out of actually constructing and + /// canonicalizing an expression in the cases where the result isn't going + /// to be a constant. + Optional computeConstantDifference(const SCEV *LHS, const SCEV *RHS); + + /// Drop memoized information computed for S. + void forgetMemoizedResults(const SCEV *S); + + /// Return an existing SCEV for V if there is one, otherwise return nullptr. + const SCEV *getExistingSCEV(Value *V); + + /// Return false iff given SCEV contains a SCEVUnknown with NULL value- + /// 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 + bool proveNoWrapByVaryingStart(const SCEV *Start, const SCEV *Step, + const Loop *L); - /// Get the (predicated) backedge count for the analyzed loop. - const SCEV *getBackedgeTakenCount(); + /// Try to prove NSW or NUW on \p AR relying on ConstantRange manipulation. + SCEV::NoWrapFlags proveNoWrapViaConstantRanges(const SCEVAddRecExpr *AR); - /// Adds a new predicate. - void addPredicate(const SCEVPredicate &Pred); + bool isMonotonicPredicateImpl(const SCEVAddRecExpr *LHS, + ICmpInst::Predicate Pred, bool &Increasing); - /// Attempts to produce an AddRecExpr for V by adding additional SCEV - /// predicates. If we can't transform the expression into an AddRecExpr we - /// return nullptr and not add additional SCEV predicates to the current - /// context. - const SCEVAddRecExpr *getAsAddRec(Value *V); + /// 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. + SCEV::NoWrapFlags getNoWrapFlagsFromUB(const Value *V); + + /// Return true if the SCEV corresponding to \p I is never poison. Proving + /// this is more complex than proving that just \p I is never poison, since + /// SCEV commons expressions across control flow, and you can have cases + /// like: + /// + /// idx0 = a + b; + /// ptr[idx0] = 100; + /// if () { + /// idx1 = a +nsw b; + /// ptr[idx1] = 200; + /// } + /// + /// where the SCEV expression (+ a b) is guaranteed to not be poison (and + /// hence not sign-overflow) only if "" is true. Since both + /// `idx0` and `idx1` will be mapped to the same SCEV expression, (+ a b), + /// it is not okay to annotate (+ a b) with in the above example. + bool isSCEVExprNeverPoison(const Instruction *I); + + /// This is like \c isSCEVExprNeverPoison but it specifically works for + /// instructions that will get mapped to SCEV add recurrences. Return true + /// if \p I will never generate poison under the assumption that \p I is an + /// 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 *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 &Ops, + SCEV::NoWrapFlags Flags = SCEV::FlagAnyWrap); + const SCEV *getAddExpr(const SCEV *LHS, const SCEV *RHS, + SCEV::NoWrapFlags Flags = SCEV::FlagAnyWrap) { + SmallVector 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 Ops = {Op0, Op1, Op2}; + return getAddExpr(Ops, Flags); + } + const SCEV *getMulExpr(SmallVectorImpl &Ops, + SCEV::NoWrapFlags Flags = SCEV::FlagAnyWrap); + const SCEV *getMulExpr(const SCEV *LHS, const SCEV *RHS, + SCEV::NoWrapFlags Flags = SCEV::FlagAnyWrap) { + SmallVector 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 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 &Operands, + const Loop *L, SCEV::NoWrapFlags Flags); + const SCEV *getAddRecExpr(const SmallVectorImpl &Operands, + const Loop *L, SCEV::NoWrapFlags Flags) { + SmallVector NewOp(Operands.begin(), Operands.end()); + return getAddRecExpr(NewOp, L, Flags); + } + /// 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 &IndexExprs, + bool InBounds = false); + const SCEV *getSMaxExpr(const SCEV *LHS, const SCEV *RHS); + const SCEV *getSMaxExpr(SmallVectorImpl &Operands); + const SCEV *getUMaxExpr(const SCEV *LHS, const SCEV *RHS); + const SCEV *getUMaxExpr(SmallVectorImpl &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); - /// Proves that V doesn't overflow by adding SCEV predicate. - void setNoOverflow(Value *V, SCEVWrapPredicate::IncrementWrapFlags Flags); + /// Return an expression for offsetof on the given field with type IntTy + /// + const SCEV *getOffsetOfExpr(Type *IntTy, StructType *STy, unsigned FieldNo); - /// Returns true if we've proved that V doesn't wrap by means of a SCEV - /// predicate. - bool hasNoOverflow(Value *V, SCEVWrapPredicate::IncrementWrapFlags Flags); + /// Return the SCEV object corresponding to -V. + /// + const SCEV *getNegativeSCEV(const SCEV *V, + SCEV::NoWrapFlags Flags = SCEV::FlagAnyWrap); - /// Returns the ScalarEvolution analysis used. - ScalarEvolution *getSE() const { return &SE; } + /// Return the SCEV object corresponding to ~V. + /// + const SCEV *getNotSCEV(const SCEV *V); - /// We need to explicitly define the copy constructor because of FlagsMap. - PredicatedScalarEvolution(const PredicatedScalarEvolution&); + /// 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); - /// Print the SCEV mappings done by the Predicated Scalar Evolution. - /// The printed text is indented by \p Depth. - void print(raw_ostream &OS, unsigned Depth) const; + /// 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 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); + + /// 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 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(); } - private: - /// Increments the version number of the predicate. This needs to be called - /// every time the SCEV predicate changes. - void updateGeneration(); + /// 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); - /// Holds a SCEV and the version number of the SCEV predicate used to - /// perform the rewrite of the expression. - typedef std::pair RewriteEntry; + /// Determine the unsigned range for a particular SCEV. + /// + ConstantRange getUnsignedRange(const SCEV *S) { + return getRange(S, HINT_RANGE_UNSIGNED); + } - /// 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 - /// need to do a rewrite. To preserve the transformation order of previous - /// rewrites, we will rewrite the previous result instead of the original - /// SCEV. - DenseMap RewriteMap; + /// Determine the signed range for a particular SCEV. + /// + ConstantRange getSignedRange(const SCEV *S) { + return getRange(S, HINT_RANGE_SIGNED); + } - /// Records what NoWrap flags we've added to a Value *. - ValueMap FlagsMap; + /// Test if the given expression is known to be negative. + /// + bool isKnownNegative(const SCEV *S); - /// The ScalarEvolution analysis. - ScalarEvolution &SE; + /// Test if the given expression is known to be positive. + /// + bool isKnownPositive(const SCEV *S); - /// The analyzed Loop. - const Loop &L; + /// Test if the given expression is known to be non-negative. + /// + bool isKnownNonNegative(const SCEV *S); - /// The SCEVPredicate that forms our context. We will rewrite all - /// expressions assuming that this predicate true. - SCEVUnionPredicate Preds; + /// Test if the given expression is known to be non-positive. + /// + bool isKnownNonPositive(const SCEV *S); - /// Marks the version of the SCEV predicate used. When rewriting a SCEV - /// 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; + /// Test if the given expression is known to be non-zero. + /// + bool isKnownNonZero(const SCEV *S); - /// The backedge taken count. - const SCEV *BackedgeCount; - }; + /// 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 &Terms, + SmallVectorImpl &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 &Terms); + + /// Return in Subscripts the access functions for each dimension in Sizes + /// (third step of delinearization). + void computeAccessFunctions(const SCEV *Expr, + SmallVectorImpl &Subscripts, + SmallVectorImpl &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 &Subscripts, + SmallVectorImpl &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, + SCEVUnionPredicate &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); + + /// 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; + FoldingSet UniquePreds; + BumpPtrAllocator SCEVAllocator; + + /// 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; +}; + +/// Analysis pass that exposes the \c ScalarEvolution for a function. +class ScalarEvolutionAnalysis + : public AnalysisInfoMixin { + friend AnalysisInfoMixin; + static char PassID; + +public: + typedef ScalarEvolution Result; + + ScalarEvolution run(Function &F, FunctionAnalysisManager &AM); +}; + +/// Printer pass for the \c ScalarEvolutionAnalysis results. +class ScalarEvolutionPrinterPass + : public PassInfoMixin { + raw_ostream &OS; + +public: + explicit ScalarEvolutionPrinterPass(raw_ostream &OS) : OS(OS) {} + PreservedAnalyses run(Function &F, FunctionAnalysisManager &AM); +}; + +class ScalarEvolutionWrapperPass : public FunctionPass { + std::unique_ptr SE; + +public: + static char ID; + + ScalarEvolutionWrapperPass(); + + ScalarEvolution &getSE() { return *SE; } + const ScalarEvolution &getSE() const { return *SE; } + + 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; +}; + +/// An interface layer with SCEV used to manage how we see SCEV expressions +/// for values in the context of existing predicates. We can add new +/// predicates, but we cannot remove them. +/// +/// This layer has multiple purposes: +/// - provides a simple interface for SCEV versioning. +/// - guarantees that the order of transformations applied on a SCEV +/// expression for a single Value is consistent across two different +/// getSCEV calls. This means that, for example, once we've obtained +/// an AddRec expression for a certain value through expression +/// rewriting, we will continue to get an AddRec expression for that +/// Value. +/// - lowers the number of expression rewrites. +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 + /// predicate. The order of transformations applied on the expression of V + /// returned by ScalarEvolution is guaranteed to be preserved, even when + /// adding new predicates. + const SCEV *getSCEV(Value *V); + + /// Get the (predicated) backedge count for the analyzed loop. + const SCEV *getBackedgeTakenCount(); + + /// Adds a new predicate. + void addPredicate(const SCEVPredicate &Pred); + + /// Attempts to produce an AddRecExpr for V by adding additional SCEV + /// predicates. If we can't transform the expression into an AddRecExpr we + /// return nullptr and not add additional SCEV predicates to the current + /// context. + const SCEVAddRecExpr *getAsAddRec(Value *V); + + /// Proves that V doesn't overflow by adding SCEV predicate. + void setNoOverflow(Value *V, SCEVWrapPredicate::IncrementWrapFlags Flags); + + /// Returns true if we've proved that V doesn't wrap by means of a SCEV + /// predicate. + bool hasNoOverflow(Value *V, SCEVWrapPredicate::IncrementWrapFlags Flags); + + /// Returns the ScalarEvolution analysis used. + ScalarEvolution *getSE() const { return &SE; } + + /// We need to explicitly define the copy constructor because of FlagsMap. + PredicatedScalarEvolution(const PredicatedScalarEvolution &); + + /// Print the SCEV mappings done by the Predicated Scalar Evolution. + /// The printed text is indented by \p Depth. + void print(raw_ostream &OS, unsigned Depth) const; + +private: + /// Increments the version number of the predicate. This needs to be called + /// every time the SCEV predicate changes. + void updateGeneration(); + + /// Holds a SCEV and the version number of the SCEV predicate used to + /// perform the rewrite of the expression. + typedef std::pair RewriteEntry; + + /// 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 + /// need to do a rewrite. To preserve the transformation order of previous + /// rewrites, we will rewrite the previous result instead of the original + /// SCEV. + DenseMap RewriteMap; + + /// Records what NoWrap flags we've added to a Value *. + ValueMap FlagsMap; + + /// The ScalarEvolution analysis. + ScalarEvolution &SE; + + /// The analyzed Loop. + const Loop &L; + + /// The SCEVPredicate that forms our context. We will rewrite all + /// expressions assuming that this predicate true. + SCEVUnionPredicate Preds; + + /// Marks the version of the SCEV predicate used. When rewriting a SCEV + /// 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; + + /// The backedge taken count. + const SCEV *BackedgeCount; +}; } #endif -- 2.50.1