diff options
Diffstat (limited to 'clang-r353983/include/llvm/Analysis/ScalarEvolution.h')
| -rw-r--r-- | clang-r353983/include/llvm/Analysis/ScalarEvolution.h | 2034 |
1 files changed, 2034 insertions, 0 deletions
diff --git a/clang-r353983/include/llvm/Analysis/ScalarEvolution.h b/clang-r353983/include/llvm/Analysis/ScalarEvolution.h new file mode 100644 index 00000000..f3a03511 --- /dev/null +++ b/clang-r353983/include/llvm/Analysis/ScalarEvolution.h @@ -0,0 +1,2034 @@ +//===- llvm/Analysis/ScalarEvolution.h - Scalar Evolution -------*- C++ -*-===// +// +// Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions. +// See https://llvm.org/LICENSE.txt for license information. +// SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception +// +//===----------------------------------------------------------------------===// +// +// The ScalarEvolution class is an LLVM pass which can be used to analyze and +// categorize scalar expressions in loops. It specializes in recognizing +// general induction variables, representing them with the abstract and opaque +// SCEV class. Given this analysis, trip counts of loops and other important +// properties can be obtained. +// +// This analysis is primarily useful for induction variable substitution and +// strength reduction. +// +//===----------------------------------------------------------------------===// + +#ifndef LLVM_ANALYSIS_SCALAREVOLUTION_H +#define LLVM_ANALYSIS_SCALAREVOLUTION_H + +#include "llvm/ADT/APInt.h" +#include "llvm/ADT/ArrayRef.h" +#include "llvm/ADT/DenseMap.h" +#include "llvm/ADT/DenseMapInfo.h" +#include "llvm/ADT/FoldingSet.h" +#include "llvm/ADT/Hashing.h" +#include "llvm/ADT/Optional.h" +#include "llvm/ADT/PointerIntPair.h" +#include "llvm/ADT/SetVector.h" +#include "llvm/ADT/SmallPtrSet.h" +#include "llvm/ADT/SmallVector.h" +#include "llvm/Analysis/LoopInfo.h" +#include "llvm/IR/ConstantRange.h" +#include "llvm/IR/Function.h" +#include "llvm/IR/InstrTypes.h" +#include "llvm/IR/Instructions.h" +#include "llvm/IR/Operator.h" +#include "llvm/IR/PassManager.h" +#include "llvm/IR/ValueHandle.h" +#include "llvm/IR/ValueMap.h" +#include "llvm/Pass.h" +#include "llvm/Support/Allocator.h" +#include "llvm/Support/Casting.h" +#include "llvm/Support/Compiler.h" +#include <algorithm> +#include <cassert> +#include <cstdint> +#include <memory> +#include <utility> + +namespace llvm { + +class AssumptionCache; +class BasicBlock; +class Constant; +class ConstantInt; +class DataLayout; +class DominatorTree; +class GEPOperator; +class Instruction; +class LLVMContext; +class raw_ostream; +class ScalarEvolution; +class SCEVAddRecExpr; +class SCEVUnknown; +class StructType; +class TargetLibraryInfo; +class Type; +class Value; + +/// This class represents an analyzed expression in the program. These are +/// opaque objects that the client is not allowed to do much with directly. +/// +class SCEV : public FoldingSetNode { + friend struct FoldingSetTrait<SCEV>; + + /// 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: + // Estimated complexity of this node's expression tree size. + const unsigned short ExpressionSize; + + /// This field is initialized to zero and may be used in subclasses to store + /// miscellaneous information. + unsigned short SubclassData = 0; + +public: + /// NoWrapFlags are bitfield indices into SubclassData. + /// + /// Add and Mul expressions may have no-unsigned-wrap <NUW> or + /// no-signed-wrap <NSW> 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 <NW> property if, in + /// the integer domain, abs(step) * max-iteration(loop) <= + /// unsigned-max(bitwidth). This means that the recurrence will never reach + /// its start value if the step is non-zero. Computing the same value on + /// each iteration is not considered wrapping, and recurrences with step = 0 + /// are trivially <NW>. <NW> is independent of the sign of step and the + /// value the add recurrence starts with. + /// + /// Note that NUW and NSW are also valid properties of a recurrence, and + /// either implies NW. For convenience, NW will be set for a recurrence + /// 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, + unsigned short ExpressionSize) + : FastID(ID), SCEVType(SCEVTy), ExpressionSize(ExpressionSize) {} + SCEV(const SCEV &) = delete; + SCEV &operator=(const SCEV &) = delete; + + unsigned getSCEVType() const { return SCEVType; } + + /// Return the LLVM type of this SCEV expression. + Type *getType() const; + + /// Return true if the expression is a constant zero. + bool isZero() const; + + /// Return true if the expression is a constant one. + bool isOne() const; + + /// Return true if the expression is a constant all-ones value. + bool isAllOnesValue() const; + + /// Return true if the specified scev is negated, but not a constant. + bool isNonConstantNegative() const; + + // Returns estimated size of the mathematical expression represented by this + // SCEV. The rules of its calculation are following: + // 1) Size of a SCEV without operands (like constants and SCEVUnknown) is 1; + // 2) Size SCEV with operands Op1, Op2, ..., OpN is calculated by formula: + // (1 + Size(Op1) + ... + Size(OpN)). + // This value gives us an estimation of time we need to traverse through this + // SCEV and all its operands recursively. We may use it to avoid performing + // heavy transformations on SCEVs of excessive size for sake of saving the + // compilation time. + unsigned short getExpressionSize() const { + return ExpressionSize; + } + + /// 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<SCEV> : DefaultFoldingSetTrait<SCEV> { + static void Profile(const SCEV &X, FoldingSetNodeID &ID) { ID = X.FastID; } + + static bool Equals(const SCEV &X, const FoldingSetNodeID &ID, unsigned IDHash, + FoldingSetNodeID &TempID) { + return ID == X.FastID; + } + + static unsigned ComputeHash(const SCEV &X, FoldingSetNodeID &TempID) { + return X.FastID.ComputeHash(); + } +}; + +inline raw_ostream &operator<<(raw_ostream &OS, const SCEV &S) { + S.print(OS); + return OS; +} + +/// 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(); + + /// Methods for support type inquiry through isa, cast, and dyn_cast: + static bool classof(const SCEV *S); +}; + +/// This class represents an assumption made using SCEV expressions which can +/// be checked at run-time. +class SCEVPredicate : public FoldingSetNode { + friend struct FoldingSetTrait<SCEVPredicate>; + + /// A reference to an Interned FoldingSetNodeID for this node. The + /// ScalarEvolution's BumpPtrAllocator holds the data. + FoldingSetNodeIDRef FastID; + +public: + enum SCEVPredicateKind { P_Union, P_Equal, P_Wrap }; + +protected: + SCEVPredicateKind Kind; + ~SCEVPredicate() = default; + SCEVPredicate(const SCEVPredicate &) = default; + SCEVPredicate &operator=(const SCEVPredicate &) = default; + +public: + SCEVPredicate(const FoldingSetNodeIDRef ID, SCEVPredicateKind Kind); + + SCEVPredicateKind getKind() const { return 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; } + + /// 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 true if this predicate implies \p N. + virtual bool implies(const SCEVPredicate *N) 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 the SCEV to which this predicate applies, or nullptr if this is + /// a SCEVUnionPredicate. + virtual const SCEV *getExpr() const = 0; +}; + +inline raw_ostream &operator<<(raw_ostream &OS, const SCEVPredicate &P) { + P.print(OS); + return OS; +} + +// Specialize FoldingSetTrait for SCEVPredicate to avoid needing to compute +// temporary FoldingSetNodeID values. +template <> +struct FoldingSetTrait<SCEVPredicate> : DefaultFoldingSetTrait<SCEVPredicate> { + 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(); + } +}; + +/// This class represents an assumption that two SCEV expressions are equal, +/// and this can be checked at run-time. +class SCEVEqualPredicate final : public SCEVPredicate { + /// We assume that LHS == RHS. + const SCEV *LHS; + const SCEV *RHS; + +public: + SCEVEqualPredicate(const FoldingSetNodeIDRef ID, const SCEV *LHS, + const SCEV *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 SCEV *getLHS() const { return LHS; } + + /// Returns the right hand side of the equality. + const SCEV *getRHS() const { return RHS; } + + /// Methods for support type inquiry through isa, cast, and dyn_cast: + static 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 + }; + + /// Convenient IncrementWrapFlags manipulation methods. + LLVM_NODISCARD static SCEVWrapPredicate::IncrementWrapFlags + 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); + } + + LLVM_NODISCARD static SCEVWrapPredicate::IncrementWrapFlags + maskFlags(SCEVWrapPredicate::IncrementWrapFlags Flags, int Mask) { + assert((Flags & IncrementNoWrapMask) == Flags && "Invalid flags value!"); + assert((Mask & IncrementNoWrapMask) == Mask && "Invalid mask value!"); + + return (SCEVWrapPredicate::IncrementWrapFlags)(Flags & Mask); + } + + LLVM_NODISCARD static SCEVWrapPredicate::IncrementWrapFlags + setFlags(SCEVWrapPredicate::IncrementWrapFlags Flags, + SCEVWrapPredicate::IncrementWrapFlags OnFlags) { + assert((Flags & IncrementNoWrapMask) == Flags && "Invalid flags value!"); + assert((OnFlags & IncrementNoWrapMask) == OnFlags && + "Invalid flags value!"); + + return (SCEVWrapPredicate::IncrementWrapFlags)(Flags | OnFlags); + } + + /// Returns the set of SCEVWrapPredicate no wrap flags implied by a + /// SCEVAddRecExpr. + LLVM_NODISCARD 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 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. +/// +/// NB! Unlike other SCEVPredicate sub-classes this class does not live in the +/// ScalarEvolution::Preds folding set. This is why the \c add function is sound. +class SCEVUnionPredicate final : public SCEVPredicate { +private: + using PredicateMap = + DenseMap<const SCEV *, SmallVector<const SCEVPredicate *, 4>>; + + /// Vector with references to all predicates in this union. + SmallVector<const SCEVPredicate *, 16> Preds; + + /// Maps SCEVs to predicates for quick look-ups. + PredicateMap SCEVToPreds; + +public: + SCEVUnionPredicate(); + + const SmallVectorImpl<const SCEVPredicate *> &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<const SCEVPredicate *> 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 bool classof(const SCEVPredicate *P) { + return P->getKind() == P_Union; + } +}; + +struct ExitLimitQuery { + ExitLimitQuery(const Loop *L, BasicBlock *ExitingBlock, bool AllowPredicates) + : L(L), ExitingBlock(ExitingBlock), AllowPredicates(AllowPredicates) {} + + const Loop *L; + BasicBlock *ExitingBlock; + bool AllowPredicates; +}; + +template <> struct DenseMapInfo<ExitLimitQuery> { + static inline ExitLimitQuery getEmptyKey() { + return ExitLimitQuery(nullptr, nullptr, true); + } + + static inline ExitLimitQuery getTombstoneKey() { + return ExitLimitQuery(nullptr, nullptr, false); + } + + static unsigned getHashValue(ExitLimitQuery Val) { + return hash_combine(hash_combine(Val.L, Val.ExitingBlock), + Val.AllowPredicates); + } + + static bool isEqual(ExitLimitQuery LHS, ExitLimitQuery RHS) { + return LHS.L == RHS.L && LHS.ExitingBlock == RHS.ExitingBlock && + LHS.AllowPredicates == RHS.AllowPredicates; + } +}; + +/// The main scalar evolution driver. Because client code (intentionally) +/// can't do much with the SCEV objects directly, they must ask this class +/// for services. +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. + LLVM_NODISCARD static SCEV::NoWrapFlags maskFlags(SCEV::NoWrapFlags Flags, + int Mask) { + return (SCEV::NoWrapFlags)(Flags & Mask); + } + LLVM_NODISCARD static SCEV::NoWrapFlags setFlags(SCEV::NoWrapFlags Flags, + SCEV::NoWrapFlags OnFlags) { + return (SCEV::NoWrapFlags)(Flags | OnFlags); + } + LLVM_NODISCARD static SCEV::NoWrapFlags + clearFlags(SCEV::NoWrapFlags Flags, SCEV::NoWrapFlags OffFlags) { + return (SCEV::NoWrapFlags)(Flags & ~OffFlags); + } + + ScalarEvolution(Function &F, TargetLibraryInfo &TLI, AssumptionCache &AC, + DominatorTree &DT, LoopInfo &LI); + ScalarEvolution(ScalarEvolution &&Arg); + ~ScalarEvolution(); + + LLVMContext &getContext() const { return F.getContext(); } + + /// Test if values of the given type are analyzable within the SCEV + /// framework. This primarily includes integer types, and it can optionally + /// include pointer types if the ScalarEvolution class has access to + /// target-specific information. + bool isSCEVable(Type *Ty) const; + + /// Return the size in bits of the specified type, for which isSCEVable must + /// return true. + uint64_t getTypeSizeInBits(Type *Ty) const; + + /// Return a type with the same bitwidth as the given type and which + /// represents how SCEV will treat the given type, for which isSCEVable must + /// return true. For pointer types, this is the pointer-sized integer type. + Type *getEffectiveSCEVType(Type *Ty) const; + + // Returns a wider type among {Ty1, Ty2}. + Type *getWiderType(Type *Ty1, Type *Ty2) const; + + /// Return true if the SCEV is a scAddRecExpr or it contains + /// scAddRecExpr. The result will be cached in HasRecMap. + bool containsAddRecurrence(const SCEV *S); + + /// Erase Value from ValueExprMap and ExprValueMap. + void eraseValueFromMap(Value *V); + + /// Return a SCEV expression for the full generality of the specified + /// expression. + const SCEV *getSCEV(Value *V); + + const SCEV *getConstant(ConstantInt *V); + const SCEV *getConstant(const APInt &Val); + const SCEV *getConstant(Type *Ty, uint64_t V, bool isSigned = false); + const SCEV *getTruncateExpr(const SCEV *Op, Type *Ty); + const SCEV *getZeroExtendExpr(const SCEV *Op, Type *Ty, unsigned Depth = 0); + const SCEV *getSignExtendExpr(const SCEV *Op, Type *Ty, unsigned Depth = 0); + const SCEV *getAnyExtendExpr(const SCEV *Op, Type *Ty); + const SCEV *getAddExpr(SmallVectorImpl<const SCEV *> &Ops, + SCEV::NoWrapFlags Flags = SCEV::FlagAnyWrap, + unsigned Depth = 0); + const SCEV *getAddExpr(const SCEV *LHS, const SCEV *RHS, + SCEV::NoWrapFlags Flags = SCEV::FlagAnyWrap, + unsigned Depth = 0) { + SmallVector<const SCEV *, 2> Ops = {LHS, RHS}; + return getAddExpr(Ops, Flags, Depth); + } + const SCEV *getAddExpr(const SCEV *Op0, const SCEV *Op1, const SCEV *Op2, + SCEV::NoWrapFlags Flags = SCEV::FlagAnyWrap, + unsigned Depth = 0) { + SmallVector<const SCEV *, 3> Ops = {Op0, Op1, Op2}; + return getAddExpr(Ops, Flags, Depth); + } + const SCEV *getMulExpr(SmallVectorImpl<const SCEV *> &Ops, + SCEV::NoWrapFlags Flags = SCEV::FlagAnyWrap, + unsigned Depth = 0); + const SCEV *getMulExpr(const SCEV *LHS, const SCEV *RHS, + SCEV::NoWrapFlags Flags = SCEV::FlagAnyWrap, + unsigned Depth = 0) { + SmallVector<const SCEV *, 2> Ops = {LHS, RHS}; + return getMulExpr(Ops, Flags, Depth); + } + const SCEV *getMulExpr(const SCEV *Op0, const SCEV *Op1, const SCEV *Op2, + SCEV::NoWrapFlags Flags = SCEV::FlagAnyWrap, + unsigned Depth = 0) { + SmallVector<const SCEV *, 3> Ops = {Op0, Op1, Op2}; + return getMulExpr(Ops, Flags, Depth); + } + const SCEV *getUDivExpr(const SCEV *LHS, const SCEV *RHS); + const SCEV *getUDivExactExpr(const SCEV *LHS, const SCEV *RHS); + const SCEV *getURemExpr(const SCEV *LHS, const SCEV *RHS); + const SCEV *getAddRecExpr(const SCEV *Start, const SCEV *Step, const Loop *L, + SCEV::NoWrapFlags Flags); + const SCEV *getAddRecExpr(SmallVectorImpl<const SCEV *> &Operands, + const Loop *L, SCEV::NoWrapFlags Flags); + const SCEV *getAddRecExpr(const SmallVectorImpl<const SCEV *> &Operands, + const Loop *L, SCEV::NoWrapFlags Flags) { + SmallVector<const SCEV *, 4> NewOp(Operands.begin(), Operands.end()); + return getAddRecExpr(NewOp, L, Flags); + } + + /// Checks if \p SymbolicPHI can be rewritten as an AddRecExpr under some + /// Predicates. If successful return these <AddRecExpr, Predicates>; + /// The function is intended to be called from PSCEV (the caller will decide + /// whether to actually add the predicates and carry out the rewrites). + Optional<std::pair<const SCEV *, SmallVector<const SCEVPredicate *, 3>>> + createAddRecFromPHIWithCasts(const SCEVUnknown *SymbolicPHI); + + /// Returns an expression for a GEP + /// + /// \p GEP The GEP. The indices contained in the GEP itself are ignored, + /// instead we use IndexExprs. + /// \p IndexExprs The expressions for the indices. + const SCEV *getGEPExpr(GEPOperator *GEP, + const SmallVectorImpl<const SCEV *> &IndexExprs); + const SCEV *getSMaxExpr(const SCEV *LHS, const SCEV *RHS); + const SCEV *getSMaxExpr(SmallVectorImpl<const SCEV *> &Operands); + const SCEV *getUMaxExpr(const SCEV *LHS, const SCEV *RHS); + const SCEV *getUMaxExpr(SmallVectorImpl<const SCEV *> &Operands); + const SCEV *getSMinExpr(const SCEV *LHS, const SCEV *RHS); + const SCEV *getSMinExpr(SmallVectorImpl<const SCEV *> &Operands); + const SCEV *getUMinExpr(const SCEV *LHS, const SCEV *RHS); + const SCEV *getUMinExpr(SmallVectorImpl<const SCEV *> &Operands); + const SCEV *getUnknown(Value *V); + const SCEV *getCouldNotCompute(); + + /// Return a SCEV for the constant 0 of a specific type. + const SCEV *getZero(Type *Ty) { return getConstant(Ty, 0); } + + /// Return a SCEV for the constant 1 of a specific type. + const SCEV *getOne(Type *Ty) { return getConstant(Ty, 1); } + + /// Return an expression for sizeof AllocTy that is type IntTy + const SCEV *getSizeOfExpr(Type *IntTy, Type *AllocTy); + + /// Return an expression for offsetof on the given field with type IntTy + const SCEV *getOffsetOfExpr(Type *IntTy, StructType *STy, unsigned FieldNo); + + /// Return the SCEV object corresponding to -V. + const SCEV *getNegativeSCEV(const SCEV *V, + SCEV::NoWrapFlags Flags = SCEV::FlagAnyWrap); + + /// Return the SCEV object corresponding to ~V. + const SCEV *getNotSCEV(const SCEV *V); + + /// Return LHS-RHS. Minus is represented in SCEV as A+B*-1. + const SCEV *getMinusSCEV(const SCEV *LHS, const SCEV *RHS, + SCEV::NoWrapFlags Flags = SCEV::FlagAnyWrap, + unsigned Depth = 0); + + /// Return a SCEV corresponding to a conversion of the input value to the + /// specified type. If the type must be extended, it is zero extended. + const SCEV *getTruncateOrZeroExtend(const SCEV *V, Type *Ty); + + /// Return a SCEV corresponding to a conversion of the input value to the + /// specified type. If the type must be extended, it is sign extended. + const SCEV *getTruncateOrSignExtend(const SCEV *V, Type *Ty); + + /// Return a SCEV corresponding to a conversion of the input value to the + /// specified type. If the type must be extended, it is zero extended. The + /// conversion must not be narrowing. + const SCEV *getNoopOrZeroExtend(const SCEV *V, Type *Ty); + + /// Return a SCEV corresponding to a conversion of the input value to the + /// specified type. If the type must be extended, it is sign extended. The + /// conversion must not be narrowing. + const SCEV *getNoopOrSignExtend(const SCEV *V, Type *Ty); + + /// Return a SCEV corresponding to a conversion of the input value to the + /// specified type. If the type must be extended, it is extended with + /// unspecified bits. The conversion must not be narrowing. + const SCEV *getNoopOrAnyExtend(const SCEV *V, Type *Ty); + + /// Return a SCEV corresponding to a conversion of the input value to the + /// specified type. The conversion must not be widening. + const SCEV *getTruncateOrNoop(const SCEV *V, Type *Ty); + + /// Promote the operands to the wider of the types using zero-extension, and + /// then perform a umax operation with them. + const SCEV *getUMaxFromMismatchedTypes(const SCEV *LHS, const SCEV *RHS); + + /// Promote the operands to the wider of the types using zero-extension, and + /// then perform a umin operation with them. + const SCEV *getUMinFromMismatchedTypes(const SCEV *LHS, const SCEV *RHS); + + /// Promote the operands to the wider of the types using zero-extension, and + /// then perform a umin operation with them. N-ary function. + const SCEV *getUMinFromMismatchedTypes(SmallVectorImpl<const SCEV *> &Ops); + + /// 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 eliminate casts. + bool isLoopBackedgeGuardedByCond(const Loop *L, ICmpInst::Predicate Pred, + const SCEV *LHS, const SCEV *RHS); + + /// Returns the maximum trip count of the loop if it is a single-exit + /// loop and we can compute a small maximum for that loop. + /// + /// Implemented in terms of the \c getSmallConstantTripCount overload with + /// the single exiting block passed to it. See that routine for details. + unsigned getSmallConstantTripCount(const Loop *L); + + /// Returns the maximum trip count of this loop as a normal unsigned + /// value. Returns 0 if the trip count is unknown or not constant. This + /// "trip count" assumes that control exits via ExitingBlock. More + /// precisely, it is the number of times that control may reach ExitingBlock + /// before taking the branch. For loops with multiple exits, it may not be + /// the number times that the loop header executes if the loop exits + /// prematurely via another branch. + unsigned getSmallConstantTripCount(const Loop *L, BasicBlock *ExitingBlock); + + /// Returns the upper bound of the loop trip count as a normal unsigned + /// value. + /// Returns 0 if the trip count is unknown or not constant. + unsigned getSmallConstantMaxTripCount(const Loop *L); + + /// Returns the largest constant divisor of the trip count of the + /// loop if it is a single-exit loop and we can compute a small maximum for + /// that loop. + /// + /// Implemented in terms of the \c getSmallConstantTripMultiple overload with + /// the single exiting block passed to it. See that routine for details. + unsigned getSmallConstantTripMultiple(const Loop *L); + + /// Returns the largest constant divisor of the trip count of this loop as a + /// normal unsigned value, if possible. This means that the actual trip + /// count is always a multiple of the returned value (don't forget the trip + /// count could very well be zero as well!). As explained in the comments + /// for getSmallConstantTripCount, this assumes that control exits the loop + /// via ExitingBlock. + unsigned getSmallConstantTripMultiple(const Loop *L, + BasicBlock *ExitingBlock); + + /// Get the expression for the number of loop iterations for which this loop + /// is guaranteed not to exit via ExitingBlock. Otherwise return + /// SCEVCouldNotCompute. + const SCEV *getExitCount(const Loop *L, BasicBlock *ExitingBlock); + + /// If the specified loop has a predictable backedge-taken count, return it, + /// otherwise return a SCEVCouldNotCompute object. The backedge-taken count is + /// the number of times the loop header will be branched to from within the + /// loop, assuming there are no abnormal exists like exception throws. This is + /// one less than the trip count of the loop, since it doesn't count the first + /// iteration, when the header is branched to from outside the loop. + /// + /// Note that it is not valid to call this method on a loop without a + /// loop-invariant backedge-taken count (see + /// hasLoopInvariantBackedgeTakenCount). + const SCEV *getBackedgeTakenCount(const Loop *L); + + /// Similar to getBackedgeTakenCount, except it will add a set of + /// SCEV predicates to Predicates that are required to be true in order for + /// the answer to be correct. Predicates can be checked with run-time + /// checks and can be used to perform loop versioning. + const SCEV *getPredicatedBackedgeTakenCount(const Loop *L, + SCEVUnionPredicate &Predicates); + + /// When successful, this returns a SCEVConstant that is greater than or equal + /// to (i.e. a "conservative over-approximation") of the value returend by + /// getBackedgeTakenCount. If such a value cannot be computed, it returns the + /// SCEVCouldNotCompute object. + const SCEV *getMaxBackedgeTakenCount(const Loop *L); + + /// Return true if the backedge taken count is either the value returned by + /// getMaxBackedgeTakenCount or zero. + bool isBackedgeTakenCountMaxOrZero(const Loop *L); + + /// Return true if the specified loop has an analyzable loop-invariant + /// backedge-taken count. + bool hasLoopInvariantBackedgeTakenCount(const Loop *L); + + /// This method should be called by the client when it has changed a loop in + /// a way that may effect ScalarEvolution's ability to compute a trip count, + /// or if the loop is deleted. This call is potentially expensive for large + /// loop bodies. + void forgetLoop(const Loop *L); + + // This method invokes forgetLoop for the outermost loop of the given loop + // \p L, making ScalarEvolution forget about all this subtree. This needs to + // be done whenever we make a transform that may affect the parameters of the + // outer loop, such as exit counts for branches. + void forgetTopmostLoop(const Loop *L); + + /// This method should be called by the client when it has changed a value + /// in a way that may effect its value, or which may disconnect it from a + /// def-use chain linking it to a loop. + void forgetValue(Value *V); + + /// Called when the client has changed the disposition of values in + /// this loop. + /// + /// We don't have a way to invalidate per-loop dispositions. Clear and + /// recompute is simpler. + void forgetLoopDispositions(const Loop *L) { LoopDispositions.clear(); } + + /// Determine the minimum number of zero bits that S is guaranteed to end in + /// (at every loop iteration). It is, at the same time, the minimum number + /// of times S is divisible by 2. For example, given {4,+,8} it returns 2. + /// If S is guaranteed to be 0, it returns the bitwidth of S. + uint32_t GetMinTrailingZeros(const SCEV *S); + + /// Determine the unsigned range for a particular SCEV. + /// NOTE: This returns a copy of the reference returned by getRangeRef. + ConstantRange getUnsignedRange(const SCEV *S) { + return getRangeRef(S, HINT_RANGE_UNSIGNED); + } + + /// Determine the min of the unsigned range for a particular SCEV. + APInt getUnsignedRangeMin(const SCEV *S) { + return getRangeRef(S, HINT_RANGE_UNSIGNED).getUnsignedMin(); + } + + /// Determine the max of the unsigned range for a particular SCEV. + APInt getUnsignedRangeMax(const SCEV *S) { + return getRangeRef(S, HINT_RANGE_UNSIGNED).getUnsignedMax(); + } + + /// Determine the signed range for a particular SCEV. + /// NOTE: This returns a copy of the reference returned by getRangeRef. + ConstantRange getSignedRange(const SCEV *S) { + return getRangeRef(S, HINT_RANGE_SIGNED); + } + + /// Determine the min of the signed range for a particular SCEV. + APInt getSignedRangeMin(const SCEV *S) { + return getRangeRef(S, HINT_RANGE_SIGNED).getSignedMin(); + } + + /// Determine the max of the signed range for a particular SCEV. + APInt getSignedRangeMax(const SCEV *S) { + return getRangeRef(S, HINT_RANGE_SIGNED).getSignedMax(); + } + + /// Test if the given expression is known to be negative. + bool isKnownNegative(const SCEV *S); + + /// Test if the given expression is known to be positive. + bool isKnownPositive(const SCEV *S); + + /// Test if the given expression is known to be non-negative. + bool isKnownNonNegative(const SCEV *S); + + /// Test if the given expression is known to be non-positive. + bool isKnownNonPositive(const SCEV *S); + + /// Test if the given expression is known to be non-zero. + bool isKnownNonZero(const SCEV *S); + + /// Splits SCEV expression \p S into two SCEVs. One of them is obtained from + /// \p S by substitution of all AddRec sub-expression related to loop \p L + /// with initial value of that SCEV. The second is obtained from \p S by + /// substitution of all AddRec sub-expressions related to loop \p L with post + /// increment of this AddRec in the loop \p L. In both cases all other AddRec + /// sub-expressions (not related to \p L) remain the same. + /// If the \p S contains non-invariant unknown SCEV the function returns + /// CouldNotCompute SCEV in both values of std::pair. + /// For example, for SCEV S={0, +, 1}<L1> + {0, +, 1}<L2> and loop L=L1 + /// the function returns pair: + /// first = {0, +, 1}<L2> + /// second = {1, +, 1}<L1> + {0, +, 1}<L2> + /// We can see that for the first AddRec sub-expression it was replaced with + /// 0 (initial value) for the first element and to {1, +, 1}<L1> (post + /// increment value) for the second one. In both cases AddRec expression + /// related to L2 remains the same. + std::pair<const SCEV *, const SCEV *> SplitIntoInitAndPostInc(const Loop *L, + const SCEV *S); + + /// We'd like to check the predicate on every iteration of the most dominated + /// loop between loops used in LHS and RHS. + /// To do this we use the following list of steps: + /// 1. Collect set S all loops on which either LHS or RHS depend. + /// 2. If S is non-empty + /// a. Let PD be the element of S which is dominated by all other elements. + /// b. Let E(LHS) be value of LHS on entry of PD. + /// To get E(LHS), we should just take LHS and replace all AddRecs that are + /// attached to PD on with their entry values. + /// Define E(RHS) in the same way. + /// c. Let B(LHS) be value of L on backedge of PD. + /// To get B(LHS), we should just take LHS and replace all AddRecs that are + /// attached to PD on with their backedge values. + /// Define B(RHS) in the same way. + /// d. Note that E(LHS) and E(RHS) are automatically available on entry of PD, + /// so we can assert on that. + /// e. Return true if isLoopEntryGuardedByCond(Pred, E(LHS), E(RHS)) && + /// isLoopBackedgeGuardedByCond(Pred, B(LHS), B(RHS)) + bool isKnownViaInduction(ICmpInst::Predicate Pred, const SCEV *LHS, + const SCEV *RHS); + + /// 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); + + /// Test if the condition described by Pred, LHS, RHS is known to be true on + /// every iteration of the loop of the recurrency LHS. + bool isKnownOnEveryIteration(ICmpInst::Predicate Pred, + const SCEVAddRecExpr *LHS, const SCEV *RHS); + + /// Return true if, for all loop invariant X, the predicate "LHS `Pred` X" + /// is monotonically increasing or decreasing. In the former case set + /// `Increasing` to true and in the latter case set `Increasing` to false. + /// + /// A predicate is said to be monotonically increasing if may go from being + /// false to being true as the loop iterates, but never the other way + /// around. A predicate is said to be monotonically decreasing if may go + /// from being true to being false as the loop iterates, but never the other + /// way around. + bool isMonotonicPredicate(const SCEVAddRecExpr *LHS, ICmpInst::Predicate Pred, + bool &Increasing); + + /// Return true if the result of the predicate LHS `Pred` RHS is loop + /// invariant with respect to L. Set InvariantPred, InvariantLHS and + /// InvariantLHS so that InvariantLHS `InvariantPred` InvariantRHS is the + /// loop invariant form of LHS `Pred` RHS. + bool isLoopInvariantPredicate(ICmpInst::Predicate Pred, const SCEV *LHS, + const SCEV *RHS, const Loop *L, + ICmpInst::Predicate &InvariantPred, + const SCEV *&InvariantLHS, + const SCEV *&InvariantRHS); + + /// Simplify LHS and RHS in a comparison with predicate Pred. Return true + /// iff any changes were made. If the operands are provably equal or + /// unequal, LHS and RHS are set to the same value and Pred is set to either + /// ICMP_EQ or ICMP_NE. + bool SimplifyICmpOperands(ICmpInst::Predicate &Pred, const SCEV *&LHS, + const SCEV *&RHS, unsigned Depth = 0); + + /// Return the "disposition" of the given SCEV with respect to the given + /// loop. + LoopDisposition getLoopDisposition(const SCEV *S, const Loop *L); + + /// Return true if the value of the given SCEV is unchanging in the + /// specified loop. + bool isLoopInvariant(const SCEV *S, const Loop *L); + + /// Determine if the SCEV can be evaluated at loop's entry. It is true if it + /// doesn't depend on a SCEVUnknown of an instruction which is dominated by + /// the header of loop L. + bool isAvailableAtLoopEntry(const SCEV *S, const Loop *L); + + /// Return true if the given SCEV changes value in a known way in the + /// specified loop. This property being true implies that the value is + /// variant in the loop AND that we can emit an expression to compute the + /// value of the expression at any particular loop iteration. + bool hasComputableLoopEvolution(const SCEV *S, const Loop *L); + + /// Return the "disposition" of the given SCEV with respect to the given + /// block. + BlockDisposition getBlockDisposition(const SCEV *S, const BasicBlock *BB); + + /// Return true if elements that makes up the given SCEV dominate the + /// specified basic block. + bool dominates(const SCEV *S, const BasicBlock *BB); + + /// Return true if elements that makes up the given SCEV properly dominate + /// the specified basic block. + bool properlyDominates(const SCEV *S, const BasicBlock *BB); + + /// Test whether the given SCEV has Op as a direct or indirect operand. + bool hasOperand(const SCEV *S, const SCEV *Op) const; + + /// Return the size of an element read or written by Inst. + const SCEV *getElementSize(Instruction *Inst); + + /// Compute the array dimensions Sizes from the set of Terms extracted from + /// the memory access function of this SCEVAddRecExpr (second step of + /// delinearization). + void findArrayDimensions(SmallVectorImpl<const SCEV *> &Terms, + SmallVectorImpl<const SCEV *> &Sizes, + const SCEV *ElementSize); + + void print(raw_ostream &OS) const; + void verify() const; + bool invalidate(Function &F, const PreservedAnalyses &PA, + FunctionAnalysisManager::Invalidator &Inv); + + /// Collect parametric terms occurring in step expressions (first step of + /// delinearization). + void collectParametricTerms(const SCEV *Expr, + SmallVectorImpl<const SCEV *> &Terms); + + /// Return in Subscripts the access functions for each dimension in Sizes + /// (third step of delinearization). + void computeAccessFunctions(const SCEV *Expr, + SmallVectorImpl<const SCEV *> &Subscripts, + SmallVectorImpl<const SCEV *> &Sizes); + + /// Split this SCEVAddRecExpr into two vectors of SCEVs representing the + /// subscripts and sizes of an array access. + /// + /// The delinearization is a 3 step process: the first two steps compute the + /// sizes of each subscript and the third step computes the access functions + /// for the delinearized array: + /// + /// 1. Find the terms in the step functions + /// 2. Compute the array size + /// 3. Compute the access function: divide the SCEV by the array size + /// starting with the innermost dimensions found in step 2. The Quotient + /// is the SCEV to be divided in the next step of the recursion. The + /// Remainder is the subscript of the innermost dimension. Loop over all + /// array dimensions computed in step 2. + /// + /// To compute a uniform array size for several memory accesses to the same + /// object, one can collect in step 1 all the step terms for all the memory + /// accesses, and compute in step 2 a unique array shape. This guarantees + /// that the array shape will be the same across all memory accesses. + /// + /// FIXME: We could derive the result of steps 1 and 2 from a description of + /// the array shape given in metadata. + /// + /// Example: + /// + /// A[][n][m] + /// + /// for i + /// for j + /// for k + /// A[j+k][2i][5i] = + /// + /// The initial SCEV: + /// + /// A[{{{0,+,2*m+5}_i, +, n*m}_j, +, n*m}_k] + /// + /// 1. Find the different terms in the step functions: + /// -> [2*m, 5, n*m, n*m] + /// + /// 2. Compute the array size: sort and unique them + /// -> [n*m, 2*m, 5] + /// find the GCD of all the terms = 1 + /// divide by the GCD and erase constant terms + /// -> [n*m, 2*m] + /// GCD = m + /// divide by GCD -> [n, 2] + /// remove constant terms + /// -> [n] + /// size of the array is A[unknown][n][m] + /// + /// 3. Compute the access function + /// a. Divide {{{0,+,2*m+5}_i, +, n*m}_j, +, n*m}_k by the innermost size m + /// Quotient: {{{0,+,2}_i, +, n}_j, +, n}_k + /// Remainder: {{{0,+,5}_i, +, 0}_j, +, 0}_k + /// The remainder is the subscript of the innermost array dimension: [5i]. + /// + /// b. Divide Quotient: {{{0,+,2}_i, +, n}_j, +, n}_k by next outer size n + /// Quotient: {{{0,+,0}_i, +, 1}_j, +, 1}_k + /// Remainder: {{{0,+,2}_i, +, 0}_j, +, 0}_k + /// The Remainder is the subscript of the next array dimension: [2i]. + /// + /// The subscript of the outermost dimension is the Quotient: [j+k]. + /// + /// Overall, we have: A[][n][m], and the access function: A[j+k][2i][5i]. + void delinearize(const SCEV *Expr, SmallVectorImpl<const SCEV *> &Subscripts, + SmallVectorImpl<const SCEV *> &Sizes, + const SCEV *ElementSize); + + /// Return the DataLayout associated with the module this SCEV instance is + /// operating on. + const DataLayout &getDataLayout() const { + return F.getParent()->getDataLayout(); + } + + const SCEVPredicate *getEqualPredicate(const SCEV *LHS, const SCEV *RHS); + + const SCEVPredicate * + getWrapPredicate(const SCEVAddRecExpr *AR, + SCEVWrapPredicate::IncrementWrapFlags AddedFlags); + + /// Re-writes the SCEV according to the Predicates in \p A. + const SCEV *rewriteUsingPredicate(const SCEV *S, const Loop *L, + SCEVUnionPredicate &A); + /// Tries to convert the \p S expression to an AddRec expression, + /// adding additional predicates to \p Preds as required. + const SCEVAddRecExpr *convertSCEVToAddRecWithPredicates( + const SCEV *S, const Loop *L, + SmallPtrSetImpl<const SCEVPredicate *> &Preds); + +private: + /// A CallbackVH to arrange for ScalarEvolution to be notified whenever a + /// Value is deleted. + class SCEVCallbackVH final : public CallbackVH { + ScalarEvolution *SE; + + void deleted() override; + void allUsesReplacedWith(Value *New) override; + + public: + SCEVCallbackVH(Value *V, ScalarEvolution *SE = nullptr); + }; + + friend class SCEVCallbackVH; + friend class SCEVExpander; + friend class SCEVUnknown; + + /// The function we are analyzing. + Function &F; + + /// Does the module have any calls to the llvm.experimental.guard intrinsic + /// at all? If this is false, we avoid doing work that will only help if + /// thare are guards present in the IR. + bool HasGuards; + + /// The target library information for the target we are targeting. + TargetLibraryInfo &TLI; + + /// The tracker for \@llvm.assume intrinsics in this function. + AssumptionCache &AC; + + /// The dominator tree. + DominatorTree &DT; + + /// The loop information for the function we are currently analyzing. + LoopInfo &LI; + + /// This SCEV is used to represent unknown trip counts and things. + std::unique_ptr<SCEVCouldNotCompute> CouldNotCompute; + + /// The type for HasRecMap. + using HasRecMapType = DenseMap<const SCEV *, bool>; + + /// This is a cache to record whether a SCEV contains any scAddRecExpr. + HasRecMapType HasRecMap; + + /// The type for ExprValueMap. + using ValueOffsetPair = std::pair<Value *, ConstantInt *>; + using ExprValueMapType = DenseMap<const SCEV *, SetVector<ValueOffsetPair>>; + + /// ExprValueMap -- This map records the original values from which + /// the SCEV expr is generated from. + /// + /// 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 type for ValueExprMap. + using ValueExprMapType = + DenseMap<SCEVCallbackVH, const SCEV *, DenseMapInfo<Value *>>; + + /// This is a cache of the values we have analyzed so far. + ValueExprMapType ValueExprMap; + + /// Mark predicate values currently being processed by isImpliedCond. + SmallPtrSet<Value *, 6> PendingLoopPredicates; + + /// Mark SCEVUnknown Phis currently being processed by getRangeRef. + SmallPtrSet<const PHINode *, 6> PendingPhiRanges; + + // Mark SCEVUnknown Phis currently being processed by isImpliedViaMerge. + SmallPtrSet<const PHINode *, 6> PendingMerges; + + /// Set to true by isLoopBackedgeGuardedByCond when we're walking the set of + /// conditions dominating the backedge of a loop. + bool WalkingBEDominatingConds = false; + + /// Set to true by isKnownPredicateViaSplitting when we're trying to prove a + /// predicate by splitting it into a set of independent predicates. + bool ProvingSplitPredicate = false; + + /// Memoized values for the GetMinTrailingZeros + DenseMap<const SCEV *, uint32_t> MinTrailingZerosCache; + + /// Return the Value set from which the SCEV expr is generated. + SetVector<ValueOffsetPair> *getSCEVValues(const SCEV *S); + + /// Private helper method for the GetMinTrailingZeros method + uint32_t GetMinTrailingZerosImpl(const SCEV *S); + + /// Information about the number of loop iterations for which a loop exit's + /// branch condition evaluates to the not-taken path. This is a temporary + /// pair of exact and max expressions that are eventually summarized in + /// ExitNotTakenInfo and BackedgeTakenInfo. + struct ExitLimit { + const SCEV *ExactNotTaken; // The exit is not taken exactly this many times + const SCEV *MaxNotTaken; // The exit is not taken at most this many times + + // Not taken either exactly MaxNotTaken or zero times + bool MaxOrZero = false; + + /// A set of predicate guards for this ExitLimit. The result is only valid + /// if all of the predicates in \c Predicates evaluate to 'true' at + /// run-time. + SmallPtrSet<const SCEVPredicate *, 4> Predicates; + + void addPredicate(const SCEVPredicate *P) { + assert(!isa<SCEVUnionPredicate>(P) && "Only add leaf predicates here!"); + Predicates.insert(P); + } + + /*implicit*/ ExitLimit(const SCEV *E); + + ExitLimit( + const SCEV *E, const SCEV *M, bool MaxOrZero, + ArrayRef<const SmallPtrSetImpl<const SCEVPredicate *> *> PredSetList); + + ExitLimit(const SCEV *E, const SCEV *M, bool MaxOrZero, + const SmallPtrSetImpl<const SCEVPredicate *> &PredSet); + + ExitLimit(const SCEV *E, const SCEV *M, bool MaxOrZero); + + /// Test whether this ExitLimit contains any computed information, or + /// whether it's all SCEVCouldNotCompute values. + bool hasAnyInfo() const { + return !isa<SCEVCouldNotCompute>(ExactNotTaken) || + !isa<SCEVCouldNotCompute>(MaxNotTaken); + } + + bool hasOperand(const SCEV *S) const; + + /// Test whether this ExitLimit contains all information. + bool hasFullInfo() const { + return !isa<SCEVCouldNotCompute>(ExactNotTaken); + } + }; + + /// Information about the number of times a particular loop exit may be + /// reached before exiting the loop. + struct ExitNotTakenInfo { + PoisoningVH<BasicBlock> ExitingBlock; + const SCEV *ExactNotTaken; + std::unique_ptr<SCEVUnionPredicate> Predicate; + + explicit ExitNotTakenInfo(PoisoningVH<BasicBlock> ExitingBlock, + const SCEV *ExactNotTaken, + std::unique_ptr<SCEVUnionPredicate> Predicate) + : ExitingBlock(ExitingBlock), ExactNotTaken(ExactNotTaken), + Predicate(std::move(Predicate)) {} + + bool hasAlwaysTruePredicate() const { + return !Predicate || Predicate->isAlwaysTrue(); + } + }; + + /// Information about the backedge-taken count of a loop. This currently + /// 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. + SmallVector<ExitNotTakenInfo, 1> ExitNotTaken; + + /// The pointer part of \c MaxAndComplete is 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. + /// + /// The integer part of \c MaxAndComplete is a boolean indicating if \c + /// ExitNotTaken has an element for every exiting block in the loop. + PointerIntPair<const SCEV *, 1> MaxAndComplete; + + /// True iff the backedge is taken either exactly Max or zero times. + bool MaxOrZero = false; + + /// \name Helper projection functions on \c MaxAndComplete. + /// @{ + bool isComplete() const { return MaxAndComplete.getInt(); } + const SCEV *getMax() const { return MaxAndComplete.getPointer(); } + /// @} + + public: + BackedgeTakenInfo() : MaxAndComplete(nullptr, 0) {} + BackedgeTakenInfo(BackedgeTakenInfo &&) = default; + BackedgeTakenInfo &operator=(BackedgeTakenInfo &&) = default; + + using EdgeExitInfo = std::pair<BasicBlock *, ExitLimit>; + + /// Initialize BackedgeTakenInfo from a list of exact exit counts. + BackedgeTakenInfo(ArrayRef<EdgeExitInfo> ExitCounts, bool Complete, + const SCEV *MaxCount, bool MaxOrZero); + + /// Test whether this BackedgeTakenInfo contains any computed information, + /// or whether it's all SCEVCouldNotCompute values. + bool hasAnyInfo() const { + return !ExitNotTaken.empty() || !isa<SCEVCouldNotCompute>(getMax()); + } + + /// Test whether this BackedgeTakenInfo contains complete information. + bool hasFullInfo() const { return isComplete(); } + + /// Return an expression indicating the exact *backedge-taken* + /// count of the loop if it is known or SCEVCouldNotCompute + /// otherwise. If execution makes it to the backedge on every + /// iteration (i.e. there are no abnormal exists like exception + /// throws and thread exits) then this is the number of times the + /// loop header will execute minus one. + /// + /// If the SCEV predicate associated with the answer can be different + /// from AlwaysTrue, we must add a (non null) Predicates argument. + /// 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(const Loop *L, 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 the number of times this backedge is taken is either the + /// value returned by getMax or zero. + bool isMaxOrZero(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<const Loop *, BackedgeTakenInfo> BackedgeTakenCounts; + + /// Cache the predicated backedge-taken count of the loops for this + /// function as they are computed. + DenseMap<const Loop *, BackedgeTakenInfo> 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<PHINode *, Constant *> 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<const SCEV *, SmallVector<std::pair<const Loop *, const SCEV *>, 2>> + ValuesAtScopes; + + /// Memoized computeLoopDisposition results. + DenseMap<const SCEV *, + SmallVector<PointerIntPair<const Loop *, 2, LoopDisposition>, 2>> + LoopDispositions; + + struct LoopProperties { + /// Set to true if the loop contains no instruction that can have side + /// effects (i.e. via throwing an exception, volatile or atomic access). + bool HasNoAbnormalExits; + + /// Set to true if the loop 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 HasNoSideEffects; + }; + + /// Cache for \c getLoopProperties. + DenseMap<const Loop *, LoopProperties> LoopPropertiesCache; + + /// Return a \c LoopProperties instance for \p L, creating one if necessary. + LoopProperties getLoopProperties(const Loop *L); + + bool loopHasNoSideEffects(const Loop *L) { + return getLoopProperties(L).HasNoSideEffects; + } + + bool loopHasNoAbnormalExits(const Loop *L) { + return getLoopProperties(L).HasNoAbnormalExits; + } + + /// Compute a LoopDisposition value. + LoopDisposition computeLoopDisposition(const SCEV *S, const Loop *L); + + /// Memoized computeBlockDisposition results. + DenseMap< + const SCEV *, + SmallVector<PointerIntPair<const BasicBlock *, 2, BlockDisposition>, 2>> + BlockDispositions; + + /// Compute a BlockDisposition value. + BlockDisposition computeBlockDisposition(const SCEV *S, const BasicBlock *BB); + + /// Memoized results from getRange + DenseMap<const SCEV *, ConstantRange> UnsignedRanges; + + /// Memoized results from getRange + DenseMap<const SCEV *, ConstantRange> 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, + ConstantRange CR) { + DenseMap<const SCEV *, ConstantRange> &Cache = + Hint == HINT_RANGE_UNSIGNED ? UnsignedRanges : SignedRanges; + + auto Pair = Cache.try_emplace(S, std::move(CR)); + if (!Pair.second) + Pair.first->second = std::move(CR); + return Pair.first->second; + } + + /// Determine the range for a particular SCEV. + /// NOTE: This returns a reference to an entry in a cache. It must be + /// copied if its needed for longer. + const ConstantRange &getRangeRef(const SCEV *S, RangeSignHint Hint); + + /// Determines the range for the affine SCEVAddRecExpr {\p Start,+,\p Stop}. + /// Helper for \c getRange. + 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); + + /// A helper function for createAddRecFromPHI to handle simple cases. + const SCEV *createSimpleAffineAddRec(PHINode *PN, Value *BEValueV, + Value *StartValueV); + + /// Helper function called from createNodeForPHI. + const SCEV *createNodeFromSelectLikePHI(PHINode *PN); + + /// 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); + + /// Provide the special handling we need to analyze GEP SCEVs. + const SCEV *createNodeForGEP(GEPOperator *GEP); + + /// 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. + /// + /// \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, + bool ExitIfTrue, bool ControlsExit, + bool AllowPredicates = false); + + // Helper functions for computeExitLimitFromCond to avoid exponential time + // complexity. + + class ExitLimitCache { + // It may look like we need key on the whole (L, ExitIfTrue, ControlsExit, + // AllowPredicates) tuple, but recursive calls to + // computeExitLimitFromCondCached from computeExitLimitFromCondImpl only + // vary the in \c ExitCond and \c ControlsExit parameters. We remember the + // initial values of the other values to assert our assumption. + SmallDenseMap<PointerIntPair<Value *, 1>, ExitLimit> TripCountMap; + + const Loop *L; + bool ExitIfTrue; + bool AllowPredicates; + + public: + ExitLimitCache(const Loop *L, bool ExitIfTrue, bool AllowPredicates) + : L(L), ExitIfTrue(ExitIfTrue), AllowPredicates(AllowPredicates) {} + + Optional<ExitLimit> find(const Loop *L, Value *ExitCond, bool ExitIfTrue, + bool ControlsExit, bool AllowPredicates); + + void insert(const Loop *L, Value *ExitCond, bool ExitIfTrue, + bool ControlsExit, bool AllowPredicates, const ExitLimit &EL); + }; + + using ExitLimitCacheTy = ExitLimitCache; + + ExitLimit computeExitLimitFromCondCached(ExitLimitCacheTy &Cache, + const Loop *L, Value *ExitCond, + bool ExitIfTrue, + bool ControlsExit, + bool AllowPredicates); + ExitLimit computeExitLimitFromCondImpl(ExitLimitCacheTy &Cache, const Loop *L, + Value *ExitCond, bool ExitIfTrue, + bool ControlsExit, + bool AllowPredicates); + + /// Compute the number of times the backedge of the specified loop will + /// execute if its exit condition were a conditional branch of the ICmpInst + /// ExitCond and ExitIfTrue. 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, + bool ExitIfTrue, + 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<BasicBlock *, BasicBlock *> + 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. Here LHS is an operation that includes FoundLHS as one of its + /// arguments. + bool isImpliedViaOperations(ICmpInst::Predicate Pred, + const SCEV *LHS, const SCEV *RHS, + const SCEV *FoundLHS, const SCEV *FoundRHS, + unsigned Depth = 0); + + /// Test whether the condition described by Pred, LHS, and RHS is true. + /// Use only simple non-recursive types of checks, such as range analysis etc. + bool isKnownViaNonRecursiveReasoning(ICmpInst::Predicate Pred, + const SCEV *LHS, const SCEV *RHS); + + /// Test whether the condition described by Pred, LHS, and RHS is true + /// whenever the condition described by Pred, FoundLHS, and FoundRHS is + /// true. + bool isImpliedCondOperandsHelper(ICmpInst::Predicate Pred, const SCEV *LHS, + const SCEV *RHS, const SCEV *FoundLHS, + 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); + + /// 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 figure out predicate for Phis which are SCEVUnknown + /// if it is true for every possible incoming value from their respective + /// basic blocks. + bool isImpliedViaMerge(ICmpInst::Predicate Pred, + const SCEV *LHS, const SCEV *RHS, + const SCEV *FoundLHS, const SCEV *FoundRHS, + unsigned Depth); + + /// 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); + + /// 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)<nsw>" 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)<Flags>". + 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<APInt> 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 <typename ExtendOpTy> + bool proveNoWrapByVaryingStart(const SCEV *Start, const SCEV *Step, + const Loop *L); + + /// Try to prove NSW or NUW on \p AR relying on ConstantRange manipulation. + SCEV::NoWrapFlags proveNoWrapViaConstantRanges(const SCEVAddRecExpr *AR); + + bool isMonotonicPredicateImpl(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 (<condition>) { + /// 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 "<condition>" 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 <nsw> 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); + + /// Similar to createAddRecFromPHI, but with the additional flexibility of + /// suggesting runtime overflow checks in case casts are encountered. + /// If successful, the analysis records that for this loop, \p SymbolicPHI, + /// which is the UnknownSCEV currently representing the PHI, can be rewritten + /// into an AddRec, assuming some predicates; The function then returns the + /// AddRec and the predicates as a pair, and caches this pair in + /// PredicatedSCEVRewrites. + /// If the analysis is not successful, a mapping from the \p SymbolicPHI to + /// itself (with no predicates) is recorded, and a nullptr with an empty + /// predicates vector is returned as a pair. + Optional<std::pair<const SCEV *, SmallVector<const SCEVPredicate *, 3>>> + createAddRecFromPHIWithCastsImpl(const SCEVUnknown *SymbolicPHI); + + /// Compute the backedge taken count knowing the interval difference, the + /// stride and presence of the equality in the comparison. + const SCEV *computeBECount(const SCEV *Delta, const SCEV *Stride, + bool Equality); + + /// Compute the maximum backedge count based on the range of values + /// permitted by Start, End, and Stride. This is for loops of the form + /// {Start, +, Stride} LT End. + /// + /// Precondition: the induction variable is known to be positive. We *don't* + /// assert these preconditions so please be careful. + const SCEV *computeMaxBECountForLT(const SCEV *Start, const SCEV *Stride, + const SCEV *End, unsigned BitWidth, + bool IsSigned); + + /// Verify if an linear IV with positive stride can overflow when in a + /// less-than comparison, knowing the invariant term of the comparison, + /// the stride and the knowledge of NSW/NUW flags on the recurrence. + 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); + + /// Get add expr already created or create a new one. + const SCEV *getOrCreateAddExpr(ArrayRef<const SCEV *> Ops, + SCEV::NoWrapFlags Flags); + + /// Get mul expr already created or create a new one. + const SCEV *getOrCreateMulExpr(ArrayRef<const SCEV *> Ops, + SCEV::NoWrapFlags Flags); + + // Get addrec expr already created or create a new one. + const SCEV *getOrCreateAddRecExpr(ArrayRef<const SCEV *> Ops, + const Loop *L, SCEV::NoWrapFlags Flags); + + /// Return x if \p Val is f(x) where f is a 1-1 function. + const SCEV *stripInjectiveFunctions(const SCEV *Val) const; + + /// Find all of the loops transitively used in \p S, and fill \p LoopsUsed. + /// A loop is considered "used" by an expression if it contains + /// an add rec on said loop. + void getUsedLoops(const SCEV *S, SmallPtrSetImpl<const Loop *> &LoopsUsed); + + /// Find all of the loops transitively used in \p S, and update \c LoopUsers + /// accordingly. + void addToLoopUseLists(const SCEV *S); + + /// Try to match the pattern generated by getURemExpr(A, B). If successful, + /// Assign A and B to LHS and RHS, respectively. + bool matchURem(const SCEV *Expr, const SCEV *&LHS, const SCEV *&RHS); + + FoldingSet<SCEV> UniqueSCEVs; + FoldingSet<SCEVPredicate> UniquePreds; + BumpPtrAllocator SCEVAllocator; + + /// This maps loops to a list of SCEV expressions that (transitively) use said + /// loop. + DenseMap<const Loop *, SmallVector<const SCEV *, 4>> LoopUsers; + + /// Cache tentative mappings from UnknownSCEVs in a Loop, to a SCEV expression + /// they can be rewritten into under certain predicates. + DenseMap<std::pair<const SCEVUnknown *, const Loop *>, + std::pair<const SCEV *, SmallVector<const SCEVPredicate *, 3>>> + PredicatedSCEVRewrites; + + /// The head of a linked list of all SCEVUnknown values that have been + /// allocated. This is used by releaseMemory to locate them all and call + /// their destructors. + SCEVUnknown *FirstUnknown = nullptr; +}; + +/// Analysis pass that exposes the \c ScalarEvolution for a function. +class ScalarEvolutionAnalysis + : public AnalysisInfoMixin<ScalarEvolutionAnalysis> { + friend AnalysisInfoMixin<ScalarEvolutionAnalysis>; + + static AnalysisKey Key; + +public: + using Result = ScalarEvolution; + + ScalarEvolution run(Function &F, FunctionAnalysisManager &AM); +}; + +/// Printer pass for the \c ScalarEvolutionAnalysis results. +class ScalarEvolutionPrinterPass + : public PassInfoMixin<ScalarEvolutionPrinterPass> { + raw_ostream &OS; + +public: + explicit ScalarEvolutionPrinterPass(raw_ostream &OS) : OS(OS) {} + + PreservedAnalyses run(Function &F, FunctionAnalysisManager &AM); +}; + +class ScalarEvolutionWrapperPass : public FunctionPass { + std::unique_ptr<ScalarEvolution> 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; + + /// Check if \p AR1 and \p AR2 are equal, while taking into account + /// Equal predicates in Preds. + bool areAddRecsEqualWithPreds(const SCEVAddRecExpr *AR1, + const SCEVAddRecExpr *AR2) 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. + using RewriteEntry = std::pair<unsigned, const SCEV *>; + + /// Maps a SCEV to the rewrite result of that SCEV at a certain version + /// number. If this number doesn't match the current Generation, we will + /// 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<const SCEV *, RewriteEntry> RewriteMap; + + /// Records what NoWrap flags we've added to a Value *. + ValueMap<Value *, SCEVWrapPredicate::IncrementWrapFlags> 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 = 0; + + /// The backedge taken count. + const SCEV *BackedgeCount = nullptr; +}; + +} // end namespace llvm + +#endif // LLVM_ANALYSIS_SCALAREVOLUTION_H |