LCOV - code coverage report
Current view: top level - include/llvm/Analysis - ScalarEvolution.h (source / functions) Hit Total Coverage
Test: llvm-toolchain.info Lines: 73 79 92.4 %
Date: 2018-07-13 00:08:38 Functions: 16 21 76.2 %
Legend: Lines: hit not hit

          Line data    Source code
       1             : //===- llvm/Analysis/ScalarEvolution.h - Scalar Evolution -------*- C++ -*-===//
       2             : //
       3             : //                     The LLVM Compiler Infrastructure
       4             : //
       5             : // This file is distributed under the University of Illinois Open Source
       6             : // License. See LICENSE.TXT for details.
       7             : //
       8             : //===----------------------------------------------------------------------===//
       9             : //
      10             : // The ScalarEvolution class is an LLVM pass which can be used to analyze and
      11             : // categorize scalar expressions in loops.  It specializes in recognizing
      12             : // general induction variables, representing them with the abstract and opaque
      13             : // SCEV class.  Given this analysis, trip counts of loops and other important
      14             : // properties can be obtained.
      15             : //
      16             : // This analysis is primarily useful for induction variable substitution and
      17             : // strength reduction.
      18             : //
      19             : //===----------------------------------------------------------------------===//
      20             : 
      21             : #ifndef LLVM_ANALYSIS_SCALAREVOLUTION_H
      22             : #define LLVM_ANALYSIS_SCALAREVOLUTION_H
      23             : 
      24             : #include "llvm/ADT/APInt.h"
      25             : #include "llvm/ADT/ArrayRef.h"
      26             : #include "llvm/ADT/DenseMap.h"
      27             : #include "llvm/ADT/DenseMapInfo.h"
      28             : #include "llvm/ADT/FoldingSet.h"
      29             : #include "llvm/ADT/Hashing.h"
      30             : #include "llvm/ADT/Optional.h"
      31             : #include "llvm/ADT/PointerIntPair.h"
      32             : #include "llvm/ADT/SetVector.h"
      33             : #include "llvm/ADT/SmallPtrSet.h"
      34             : #include "llvm/ADT/SmallVector.h"
      35             : #include "llvm/Analysis/LoopInfo.h"
      36             : #include "llvm/IR/ConstantRange.h"
      37             : #include "llvm/IR/Function.h"
      38             : #include "llvm/IR/InstrTypes.h"
      39             : #include "llvm/IR/Instructions.h"
      40             : #include "llvm/IR/Operator.h"
      41             : #include "llvm/IR/PassManager.h"
      42             : #include "llvm/IR/ValueHandle.h"
      43             : #include "llvm/IR/ValueMap.h"
      44             : #include "llvm/Pass.h"
      45             : #include "llvm/Support/Allocator.h"
      46             : #include "llvm/Support/Casting.h"
      47             : #include "llvm/Support/Compiler.h"
      48             : #include <algorithm>
      49             : #include <cassert>
      50             : #include <cstdint>
      51             : #include <memory>
      52             : #include <utility>
      53             : 
      54             : namespace llvm {
      55             : 
      56             : class AssumptionCache;
      57             : class BasicBlock;
      58             : class Constant;
      59             : class ConstantInt;
      60             : class DataLayout;
      61             : class DominatorTree;
      62             : class GEPOperator;
      63             : class Instruction;
      64             : class LLVMContext;
      65             : class raw_ostream;
      66             : class ScalarEvolution;
      67             : class SCEVAddRecExpr;
      68             : class SCEVUnknown;
      69             : class StructType;
      70             : class TargetLibraryInfo;
      71             : class Type;
      72             : class Value;
      73             : 
      74             : /// This class represents an analyzed expression in the program.  These are
      75             : /// opaque objects that the client is not allowed to do much with directly.
      76             : ///
      77             : class SCEV : public FoldingSetNode {
      78             :   friend struct FoldingSetTrait<SCEV>;
      79             : 
      80             :   /// A reference to an Interned FoldingSetNodeID for this node.  The
      81             :   /// ScalarEvolution's BumpPtrAllocator holds the data.
      82             :   FoldingSetNodeIDRef FastID;
      83             : 
      84             :   // The SCEV baseclass this node corresponds to
      85             :   const unsigned short SCEVType;
      86             : 
      87             : protected:
      88             :   /// This field is initialized to zero and may be used in subclasses to store
      89             :   /// miscellaneous information.
      90             :   unsigned short SubclassData = 0;
      91             : 
      92             : public:
      93             :   /// NoWrapFlags are bitfield indices into SubclassData.
      94             :   ///
      95             :   /// Add and Mul expressions may have no-unsigned-wrap <NUW> or
      96             :   /// no-signed-wrap <NSW> properties, which are derived from the IR
      97             :   /// operator. NSW is a misnomer that we use to mean no signed overflow or
      98             :   /// underflow.
      99             :   ///
     100             :   /// AddRec expressions may have a no-self-wraparound <NW> property if, in
     101             :   /// the integer domain, abs(step) * max-iteration(loop) <=
     102             :   /// unsigned-max(bitwidth).  This means that the recurrence will never reach
     103             :   /// its start value if the step is non-zero.  Computing the same value on
     104             :   /// each iteration is not considered wrapping, and recurrences with step = 0
     105             :   /// are trivially <NW>.  <NW> is independent of the sign of step and the
     106             :   /// value the add recurrence starts with.
     107             :   ///
     108             :   /// Note that NUW and NSW are also valid properties of a recurrence, and
     109             :   /// either implies NW. For convenience, NW will be set for a recurrence
     110             :   /// whenever either NUW or NSW are set.
     111             :   enum NoWrapFlags {
     112             :     FlagAnyWrap = 0,    // No guarantee.
     113             :     FlagNW = (1 << 0),  // No self-wrap.
     114             :     FlagNUW = (1 << 1), // No unsigned wrap.
     115             :     FlagNSW = (1 << 2), // No signed wrap.
     116             :     NoWrapMask = (1 << 3) - 1
     117             :   };
     118             : 
     119             :   explicit SCEV(const FoldingSetNodeIDRef ID, unsigned SCEVTy)
     120     3341350 :       : FastID(ID), SCEVType(SCEVTy) {}
     121             :   SCEV(const SCEV &) = delete;
     122             :   SCEV &operator=(const SCEV &) = delete;
     123             : 
     124    35745539 :   unsigned getSCEVType() const { return SCEVType; }
     125             : 
     126             :   /// Return the LLVM type of this SCEV expression.
     127             :   Type *getType() const;
     128             : 
     129             :   /// Return true if the expression is a constant zero.
     130             :   bool isZero() const;
     131             : 
     132             :   /// Return true if the expression is a constant one.
     133             :   bool isOne() const;
     134             : 
     135             :   /// Return true if the expression is a constant all-ones value.
     136             :   bool isAllOnesValue() const;
     137             : 
     138             :   /// Return true if the specified scev is negated, but not a constant.
     139             :   bool isNonConstantNegative() const;
     140             : 
     141             :   /// Print out the internal representation of this scalar to the specified
     142             :   /// stream.  This should really only be used for debugging purposes.
     143             :   void print(raw_ostream &OS) const;
     144             : 
     145             :   /// This method is used for debugging.
     146             :   void dump() const;
     147             : };
     148             : 
     149             : // Specialize FoldingSetTrait for SCEV to avoid needing to compute
     150             : // temporary FoldingSetNodeID values.
     151             : template <> struct FoldingSetTrait<SCEV> : DefaultFoldingSetTrait<SCEV> {
     152           0 :   static void Profile(const SCEV &X, FoldingSetNodeID &ID) { ID = X.FastID; }
     153             : 
     154             :   static bool Equals(const SCEV &X, const FoldingSetNodeID &ID, unsigned IDHash,
     155             :                      FoldingSetNodeID &TempID) {
     156     9850398 :     return ID == X.FastID;
     157             :   }
     158             : 
     159             :   static unsigned ComputeHash(const SCEV &X, FoldingSetNodeID &TempID) {
     160      393129 :     return X.FastID.ComputeHash();
     161             :   }
     162             : };
     163             : 
     164       44279 : inline raw_ostream &operator<<(raw_ostream &OS, const SCEV &S) {
     165       48955 :   S.print(OS);
     166       44279 :   return OS;
     167             : }
     168             : 
     169             : /// An object of this class is returned by queries that could not be answered.
     170             : /// For example, if you ask for the number of iterations of a linked-list
     171             : /// traversal loop, you will get one of these.  None of the standard SCEV
     172             : /// operations are valid on this class, it is just a marker.
     173             : struct SCEVCouldNotCompute : public SCEV {
     174             :   SCEVCouldNotCompute();
     175             : 
     176             :   /// Methods for support type inquiry through isa, cast, and dyn_cast:
     177             :   static bool classof(const SCEV *S);
     178             : };
     179             : 
     180             : /// This class represents an assumption made using SCEV expressions which can
     181             : /// be checked at run-time.
     182         180 : class SCEVPredicate : public FoldingSetNode {
     183             :   friend struct FoldingSetTrait<SCEVPredicate>;
     184             : 
     185             :   /// A reference to an Interned FoldingSetNodeID for this node.  The
     186             :   /// ScalarEvolution's BumpPtrAllocator holds the data.
     187             :   FoldingSetNodeIDRef FastID;
     188             : 
     189             : public:
     190             :   enum SCEVPredicateKind { P_Union, P_Equal, P_Wrap };
     191             : 
     192             : protected:
     193             :   SCEVPredicateKind Kind;
     194             :   ~SCEVPredicate() = default;
     195        2527 :   SCEVPredicate(const SCEVPredicate &) = default;
     196             :   SCEVPredicate &operator=(const SCEVPredicate &) = default;
     197             : 
     198             : public:
     199             :   SCEVPredicate(const FoldingSetNodeIDRef ID, SCEVPredicateKind Kind);
     200             : 
     201             :   SCEVPredicateKind getKind() const { return Kind; }
     202             : 
     203             :   /// Returns the estimated complexity of this predicate.  This is roughly
     204             :   /// measured in the number of run-time checks required.
     205           0 :   virtual unsigned getComplexity() const { return 1; }
     206             : 
     207             :   /// Returns true if the predicate is always true. This means that no
     208             :   /// assumptions were made and nothing needs to be checked at run-time.
     209             :   virtual bool isAlwaysTrue() const = 0;
     210             : 
     211             :   /// Returns true if this predicate implies \p N.
     212             :   virtual bool implies(const SCEVPredicate *N) const = 0;
     213             : 
     214             :   /// Prints a textual representation of this predicate with an indentation of
     215             :   /// \p Depth.
     216             :   virtual void print(raw_ostream &OS, unsigned Depth = 0) const = 0;
     217             : 
     218             :   /// Returns the SCEV to which this predicate applies, or nullptr if this is
     219             :   /// a SCEVUnionPredicate.
     220             :   virtual const SCEV *getExpr() const = 0;
     221             : };
     222             : 
     223             : inline raw_ostream &operator<<(raw_ostream &OS, const SCEVPredicate &P) {
     224             :   P.print(OS);
     225             :   return OS;
     226             : }
     227             : 
     228             : // Specialize FoldingSetTrait for SCEVPredicate to avoid needing to compute
     229             : // temporary FoldingSetNodeID values.
     230             : template <>
     231             : struct FoldingSetTrait<SCEVPredicate> : DefaultFoldingSetTrait<SCEVPredicate> {
     232           0 :   static void Profile(const SCEVPredicate &X, FoldingSetNodeID &ID) {
     233           0 :     ID = X.FastID;
     234           0 :   }
     235             : 
     236             :   static bool Equals(const SCEVPredicate &X, const FoldingSetNodeID &ID,
     237             :                      unsigned IDHash, FoldingSetNodeID &TempID) {
     238         169 :     return ID == X.FastID;
     239             :   }
     240             : 
     241             :   static unsigned ComputeHash(const SCEVPredicate &X,
     242             :                               FoldingSetNodeID &TempID) {
     243           0 :     return X.FastID.ComputeHash();
     244             :   }
     245             : };
     246             : 
     247             : /// This class represents an assumption that two SCEV expressions are equal,
     248             : /// and this can be checked at run-time.
     249             : class SCEVEqualPredicate final : public SCEVPredicate {
     250             :   /// We assume that LHS == RHS.
     251             :   const SCEV *LHS;
     252             :   const SCEV *RHS;
     253             : 
     254             : public:
     255             :   SCEVEqualPredicate(const FoldingSetNodeIDRef ID, const SCEV *LHS,
     256             :                      const SCEV *RHS);
     257             : 
     258             :   /// Implementation of the SCEVPredicate interface
     259             :   bool implies(const SCEVPredicate *N) const override;
     260             :   void print(raw_ostream &OS, unsigned Depth = 0) const override;
     261             :   bool isAlwaysTrue() const override;
     262             :   const SCEV *getExpr() const override;
     263             : 
     264             :   /// Returns the left hand side of the equality.
     265             :   const SCEV *getLHS() const { return LHS; }
     266             : 
     267             :   /// Returns the right hand side of the equality.
     268             :   const SCEV *getRHS() const { return RHS; }
     269             : 
     270             :   /// Methods for support type inquiry through isa, cast, and dyn_cast:
     271             :   static bool classof(const SCEVPredicate *P) {
     272          91 :     return P->getKind() == P_Equal;
     273             :   }
     274             : };
     275             : 
     276             : /// This class represents an assumption made on an AddRec expression. Given an
     277             : /// affine AddRec expression {a,+,b}, we assume that it has the nssw or nusw
     278             : /// flags (defined below) in the first X iterations of the loop, where X is a
     279             : /// SCEV expression returned by getPredicatedBackedgeTakenCount).
     280             : ///
     281             : /// Note that this does not imply that X is equal to the backedge taken
     282             : /// count. This means that if we have a nusw predicate for i32 {0,+,1} with a
     283             : /// predicated backedge taken count of X, we only guarantee that {0,+,1} has
     284             : /// nusw in the first X iterations. {0,+,1} may still wrap in the loop if we
     285             : /// have more than X iterations.
     286             : class SCEVWrapPredicate final : public SCEVPredicate {
     287             : public:
     288             :   /// Similar to SCEV::NoWrapFlags, but with slightly different semantics
     289             :   /// for FlagNUSW. The increment is considered to be signed, and a + b
     290             :   /// (where b is the increment) is considered to wrap if:
     291             :   ///    zext(a + b) != zext(a) + sext(b)
     292             :   ///
     293             :   /// If Signed is a function that takes an n-bit tuple and maps to the
     294             :   /// integer domain as the tuples value interpreted as twos complement,
     295             :   /// and Unsigned a function that takes an n-bit tuple and maps to the
     296             :   /// integer domain as as the base two value of input tuple, then a + b
     297             :   /// has IncrementNUSW iff:
     298             :   ///
     299             :   /// 0 <= Unsigned(a) + Signed(b) < 2^n
     300             :   ///
     301             :   /// The IncrementNSSW flag has identical semantics with SCEV::FlagNSW.
     302             :   ///
     303             :   /// Note that the IncrementNUSW flag is not commutative: if base + inc
     304             :   /// has IncrementNUSW, then inc + base doesn't neccessarily have this
     305             :   /// property. The reason for this is that this is used for sign/zero
     306             :   /// extending affine AddRec SCEV expressions when a SCEVWrapPredicate is
     307             :   /// assumed. A {base,+,inc} expression is already non-commutative with
     308             :   /// regards to base and inc, since it is interpreted as:
     309             :   ///     (((base + inc) + inc) + inc) ...
     310             :   enum IncrementWrapFlags {
     311             :     IncrementAnyWrap = 0,     // No guarantee.
     312             :     IncrementNUSW = (1 << 0), // No unsigned with signed increment wrap.
     313             :     IncrementNSSW = (1 << 1), // No signed with signed increment wrap
     314             :                               // (equivalent with SCEV::NSW)
     315             :     IncrementNoWrapMask = (1 << 2) - 1
     316             :   };
     317             : 
     318             :   /// Convenient IncrementWrapFlags manipulation methods.
     319             :   LLVM_NODISCARD static SCEVWrapPredicate::IncrementWrapFlags
     320             :   clearFlags(SCEVWrapPredicate::IncrementWrapFlags Flags,
     321             :              SCEVWrapPredicate::IncrementWrapFlags OffFlags) {
     322             :     assert((Flags & IncrementNoWrapMask) == Flags && "Invalid flags value!");
     323             :     assert((OffFlags & IncrementNoWrapMask) == OffFlags &&
     324             :            "Invalid flags value!");
     325        1386 :     return (SCEVWrapPredicate::IncrementWrapFlags)(Flags & ~OffFlags);
     326             :   }
     327             : 
     328             :   LLVM_NODISCARD static SCEVWrapPredicate::IncrementWrapFlags
     329             :   maskFlags(SCEVWrapPredicate::IncrementWrapFlags Flags, int Mask) {
     330             :     assert((Flags & IncrementNoWrapMask) == Flags && "Invalid flags value!");
     331             :     assert((Mask & IncrementNoWrapMask) == Mask && "Invalid mask value!");
     332             : 
     333             :     return (SCEVWrapPredicate::IncrementWrapFlags)(Flags & Mask);
     334             :   }
     335             : 
     336             :   LLVM_NODISCARD static SCEVWrapPredicate::IncrementWrapFlags
     337             :   setFlags(SCEVWrapPredicate::IncrementWrapFlags Flags,
     338             :            SCEVWrapPredicate::IncrementWrapFlags OnFlags) {
     339             :     assert((Flags & IncrementNoWrapMask) == Flags && "Invalid flags value!");
     340             :     assert((OnFlags & IncrementNoWrapMask) == OnFlags &&
     341             :            "Invalid flags value!");
     342             : 
     343         142 :     return (SCEVWrapPredicate::IncrementWrapFlags)(Flags | OnFlags);
     344             :   }
     345             : 
     346             :   /// Returns the set of SCEVWrapPredicate no wrap flags implied by a
     347             :   /// SCEVAddRecExpr.
     348             :   LLVM_NODISCARD static SCEVWrapPredicate::IncrementWrapFlags
     349             :   getImpliedFlags(const SCEVAddRecExpr *AR, ScalarEvolution &SE);
     350             : 
     351             : private:
     352             :   const SCEVAddRecExpr *AR;
     353             :   IncrementWrapFlags Flags;
     354             : 
     355             : public:
     356             :   explicit SCEVWrapPredicate(const FoldingSetNodeIDRef ID,
     357             :                              const SCEVAddRecExpr *AR,
     358             :                              IncrementWrapFlags Flags);
     359             : 
     360             :   /// Returns the set assumed no overflow flags.
     361             :   IncrementWrapFlags getFlags() const { return Flags; }
     362             : 
     363             :   /// Implementation of the SCEVPredicate interface
     364             :   const SCEV *getExpr() const override;
     365             :   bool implies(const SCEVPredicate *N) const override;
     366             :   void print(raw_ostream &OS, unsigned Depth = 0) const override;
     367             :   bool isAlwaysTrue() const override;
     368             : 
     369             :   /// Methods for support type inquiry through isa, cast, and dyn_cast:
     370             :   static bool classof(const SCEVPredicate *P) {
     371         195 :     return P->getKind() == P_Wrap;
     372             :   }
     373             : };
     374             : 
     375             : /// This class represents a composition of other SCEV predicates, and is the
     376             : /// class that most clients will interact with.  This is equivalent to a
     377             : /// logical "AND" of all the predicates in the union.
     378             : ///
     379             : /// NB! Unlike other SCEVPredicate sub-classes this class does not live in the
     380             : /// ScalarEvolution::Preds folding set.  This is why the \c add function is sound.
     381       38164 : class SCEVUnionPredicate final : public SCEVPredicate {
     382             : private:
     383             :   using PredicateMap =
     384             :       DenseMap<const SCEV *, SmallVector<const SCEVPredicate *, 4>>;
     385             : 
     386             :   /// Vector with references to all predicates in this union.
     387             :   SmallVector<const SCEVPredicate *, 16> Preds;
     388             : 
     389             :   /// Maps SCEVs to predicates for quick look-ups.
     390             :   PredicateMap SCEVToPreds;
     391             : 
     392             : public:
     393             :   SCEVUnionPredicate();
     394             : 
     395             :   const SmallVectorImpl<const SCEVPredicate *> &getPredicates() const {
     396             :     return Preds;
     397             :   }
     398             : 
     399             :   /// Adds a predicate to this union.
     400             :   void add(const SCEVPredicate *N);
     401             : 
     402             :   /// Returns a reference to a vector containing all predicates which apply to
     403             :   /// \p Expr.
     404             :   ArrayRef<const SCEVPredicate *> getPredicatesForExpr(const SCEV *Expr);
     405             : 
     406             :   /// Implementation of the SCEVPredicate interface
     407             :   bool isAlwaysTrue() const override;
     408             :   bool implies(const SCEVPredicate *N) const override;
     409             :   void print(raw_ostream &OS, unsigned Depth) const override;
     410             :   const SCEV *getExpr() const override;
     411             : 
     412             :   /// We estimate the complexity of a union predicate as the size number of
     413             :   /// predicates in the union.
     414         926 :   unsigned getComplexity() const override { return Preds.size(); }
     415             : 
     416             :   /// Methods for support type inquiry through isa, cast, and dyn_cast:
     417             :   static bool classof(const SCEVPredicate *P) {
     418        5272 :     return P->getKind() == P_Union;
     419             :   }
     420             : };
     421             : 
     422             : struct ExitLimitQuery {
     423             :   ExitLimitQuery(const Loop *L, BasicBlock *ExitingBlock, bool AllowPredicates)
     424             :       : L(L), ExitingBlock(ExitingBlock), AllowPredicates(AllowPredicates) {}
     425             : 
     426             :   const Loop *L;
     427             :   BasicBlock *ExitingBlock;
     428             :   bool AllowPredicates;
     429             : };
     430             : 
     431             : template <> struct DenseMapInfo<ExitLimitQuery> {
     432             :   static inline ExitLimitQuery getEmptyKey() {
     433             :     return ExitLimitQuery(nullptr, nullptr, true);
     434             :   }
     435             : 
     436             :   static inline ExitLimitQuery getTombstoneKey() {
     437             :     return ExitLimitQuery(nullptr, nullptr, false);
     438             :   }
     439             : 
     440             :   static unsigned getHashValue(ExitLimitQuery Val) {
     441             :     return hash_combine(hash_combine(Val.L, Val.ExitingBlock),
     442             :                         Val.AllowPredicates);
     443             :   }
     444             : 
     445             :   static bool isEqual(ExitLimitQuery LHS, ExitLimitQuery RHS) {
     446             :     return LHS.L == RHS.L && LHS.ExitingBlock == RHS.ExitingBlock &&
     447             :            LHS.AllowPredicates == RHS.AllowPredicates;
     448             :   }
     449             : };
     450             : 
     451             : /// The main scalar evolution driver. Because client code (intentionally)
     452             : /// can't do much with the SCEV objects directly, they must ask this class
     453             : /// for services.
     454             : class ScalarEvolution {
     455             : public:
     456             :   /// An enum describing the relationship between a SCEV and a loop.
     457             :   enum LoopDisposition {
     458             :     LoopVariant,   ///< The SCEV is loop-variant (unknown).
     459             :     LoopInvariant, ///< The SCEV is loop-invariant.
     460             :     LoopComputable ///< The SCEV varies predictably with the loop.
     461             :   };
     462             : 
     463             :   /// An enum describing the relationship between a SCEV and a basic block.
     464             :   enum BlockDisposition {
     465             :     DoesNotDominateBlock,  ///< The SCEV does not dominate the block.
     466             :     DominatesBlock,        ///< The SCEV dominates the block.
     467             :     ProperlyDominatesBlock ///< The SCEV properly dominates the block.
     468             :   };
     469             : 
     470             :   /// Convenient NoWrapFlags manipulation that hides enum casts and is
     471             :   /// visible in the ScalarEvolution name space.
     472             :   LLVM_NODISCARD static SCEV::NoWrapFlags maskFlags(SCEV::NoWrapFlags Flags,
     473             :                                                     int Mask) {
     474     9338949 :     return (SCEV::NoWrapFlags)(Flags & Mask);
     475             :   }
     476             :   LLVM_NODISCARD static SCEV::NoWrapFlags setFlags(SCEV::NoWrapFlags Flags,
     477             :                                                    SCEV::NoWrapFlags OnFlags) {
     478     2937409 :     return (SCEV::NoWrapFlags)(Flags | OnFlags);
     479             :   }
     480             :   LLVM_NODISCARD static SCEV::NoWrapFlags
     481             :   clearFlags(SCEV::NoWrapFlags Flags, SCEV::NoWrapFlags OffFlags) {
     482       28894 :     return (SCEV::NoWrapFlags)(Flags & ~OffFlags);
     483             :   }
     484             : 
     485             :   ScalarEvolution(Function &F, TargetLibraryInfo &TLI, AssumptionCache &AC,
     486             :                   DominatorTree &DT, LoopInfo &LI);
     487             :   ScalarEvolution(ScalarEvolution &&Arg);
     488             :   ~ScalarEvolution();
     489             : 
     490     2715392 :   LLVMContext &getContext() const { return F.getContext(); }
     491             : 
     492             :   /// Test if values of the given type are analyzable within the SCEV
     493             :   /// framework. This primarily includes integer types, and it can optionally
     494             :   /// include pointer types if the ScalarEvolution class has access to
     495             :   /// target-specific information.
     496             :   bool isSCEVable(Type *Ty) const;
     497             : 
     498             :   /// Return the size in bits of the specified type, for which isSCEVable must
     499             :   /// return true.
     500             :   uint64_t getTypeSizeInBits(Type *Ty) const;
     501             : 
     502             :   /// Return a type with the same bitwidth as the given type and which
     503             :   /// represents how SCEV will treat the given type, for which isSCEVable must
     504             :   /// return true. For pointer types, this is the pointer-sized integer type.
     505             :   Type *getEffectiveSCEVType(Type *Ty) const;
     506             : 
     507             :   // Returns a wider type among {Ty1, Ty2}.
     508             :   Type *getWiderType(Type *Ty1, Type *Ty2) const;
     509             : 
     510             :   /// Return true if the SCEV is a scAddRecExpr or it contains
     511             :   /// scAddRecExpr. The result will be cached in HasRecMap.
     512             :   bool containsAddRecurrence(const SCEV *S);
     513             : 
     514             :   /// Erase Value from ValueExprMap and ExprValueMap.
     515             :   void eraseValueFromMap(Value *V);
     516             : 
     517             :   /// Return a SCEV expression for the full generality of the specified
     518             :   /// expression.
     519             :   const SCEV *getSCEV(Value *V);
     520             : 
     521             :   const SCEV *getConstant(ConstantInt *V);
     522             :   const SCEV *getConstant(const APInt &Val);
     523             :   const SCEV *getConstant(Type *Ty, uint64_t V, bool isSigned = false);
     524             :   const SCEV *getTruncateExpr(const SCEV *Op, Type *Ty);
     525             :   const SCEV *getZeroExtendExpr(const SCEV *Op, Type *Ty, unsigned Depth = 0);
     526             :   const SCEV *getSignExtendExpr(const SCEV *Op, Type *Ty, unsigned Depth = 0);
     527             :   const SCEV *getAnyExtendExpr(const SCEV *Op, Type *Ty);
     528             :   const SCEV *getAddExpr(SmallVectorImpl<const SCEV *> &Ops,
     529             :                          SCEV::NoWrapFlags Flags = SCEV::FlagAnyWrap,
     530             :                          unsigned Depth = 0);
     531     1599729 :   const SCEV *getAddExpr(const SCEV *LHS, const SCEV *RHS,
     532             :                          SCEV::NoWrapFlags Flags = SCEV::FlagAnyWrap,
     533             :                          unsigned Depth = 0) {
     534     3199458 :     SmallVector<const SCEV *, 2> Ops = {LHS, RHS};
     535     3199458 :     return getAddExpr(Ops, Flags, Depth);
     536             :   }
     537             :   const SCEV *getAddExpr(const SCEV *Op0, const SCEV *Op1, const SCEV *Op2,
     538             :                          SCEV::NoWrapFlags Flags = SCEV::FlagAnyWrap,
     539             :                          unsigned Depth = 0) {
     540             :     SmallVector<const SCEV *, 3> Ops = {Op0, Op1, Op2};
     541             :     return getAddExpr(Ops, Flags, Depth);
     542             :   }
     543             :   const SCEV *getMulExpr(SmallVectorImpl<const SCEV *> &Ops,
     544             :                          SCEV::NoWrapFlags Flags = SCEV::FlagAnyWrap,
     545             :                          unsigned Depth = 0);
     546     1153220 :   const SCEV *getMulExpr(const SCEV *LHS, const SCEV *RHS,
     547             :                          SCEV::NoWrapFlags Flags = SCEV::FlagAnyWrap,
     548             :                          unsigned Depth = 0) {
     549     2306440 :     SmallVector<const SCEV *, 2> Ops = {LHS, RHS};
     550     2306440 :     return getMulExpr(Ops, Flags, Depth);
     551             :   }
     552        6129 :   const SCEV *getMulExpr(const SCEV *Op0, const SCEV *Op1, const SCEV *Op2,
     553             :                          SCEV::NoWrapFlags Flags = SCEV::FlagAnyWrap,
     554             :                          unsigned Depth = 0) {
     555       12258 :     SmallVector<const SCEV *, 3> Ops = {Op0, Op1, Op2};
     556       12258 :     return getMulExpr(Ops, Flags, Depth);
     557             :   }
     558             :   const SCEV *getUDivExpr(const SCEV *LHS, const SCEV *RHS);
     559             :   const SCEV *getUDivExactExpr(const SCEV *LHS, const SCEV *RHS);
     560             :   const SCEV *getURemExpr(const SCEV *LHS, const SCEV *RHS);
     561             :   const SCEV *getAddRecExpr(const SCEV *Start, const SCEV *Step, const Loop *L,
     562             :                             SCEV::NoWrapFlags Flags);
     563             :   const SCEV *getAddRecExpr(SmallVectorImpl<const SCEV *> &Operands,
     564             :                             const Loop *L, SCEV::NoWrapFlags Flags);
     565         125 :   const SCEV *getAddRecExpr(const SmallVectorImpl<const SCEV *> &Operands,
     566             :                             const Loop *L, SCEV::NoWrapFlags Flags) {
     567             :     SmallVector<const SCEV *, 4> NewOp(Operands.begin(), Operands.end());
     568         250 :     return getAddRecExpr(NewOp, L, Flags);
     569             :   }
     570             : 
     571             :   /// Checks if \p SymbolicPHI can be rewritten as an AddRecExpr under some
     572             :   /// Predicates. If successful return these <AddRecExpr, Predicates>;
     573             :   /// The function is intended to be called from PSCEV (the caller will decide
     574             :   /// whether to actually add the predicates and carry out the rewrites).
     575             :   Optional<std::pair<const SCEV *, SmallVector<const SCEVPredicate *, 3>>>
     576             :   createAddRecFromPHIWithCasts(const SCEVUnknown *SymbolicPHI);
     577             : 
     578             :   /// Returns an expression for a GEP
     579             :   ///
     580             :   /// \p GEP The GEP. The indices contained in the GEP itself are ignored,
     581             :   /// instead we use IndexExprs.
     582             :   /// \p IndexExprs The expressions for the indices.
     583             :   const SCEV *getGEPExpr(GEPOperator *GEP,
     584             :                          const SmallVectorImpl<const SCEV *> &IndexExprs);
     585             :   const SCEV *getSMaxExpr(const SCEV *LHS, const SCEV *RHS);
     586             :   const SCEV *getSMaxExpr(SmallVectorImpl<const SCEV *> &Operands);
     587             :   const SCEV *getUMaxExpr(const SCEV *LHS, const SCEV *RHS);
     588             :   const SCEV *getUMaxExpr(SmallVectorImpl<const SCEV *> &Operands);
     589             :   const SCEV *getSMinExpr(const SCEV *LHS, const SCEV *RHS);
     590             :   const SCEV *getSMinExpr(SmallVectorImpl<const SCEV *> &Operands);
     591             :   const SCEV *getUMinExpr(const SCEV *LHS, const SCEV *RHS);
     592             :   const SCEV *getUMinExpr(SmallVectorImpl<const SCEV *> &Operands);
     593             :   const SCEV *getUnknown(Value *V);
     594             :   const SCEV *getCouldNotCompute();
     595             : 
     596             :   /// Return a SCEV for the constant 0 of a specific type.
     597      433691 :   const SCEV *getZero(Type *Ty) { return getConstant(Ty, 0); }
     598             : 
     599             :   /// Return a SCEV for the constant 1 of a specific type.
     600       78667 :   const SCEV *getOne(Type *Ty) { return getConstant(Ty, 1); }
     601             : 
     602             :   /// Return an expression for sizeof AllocTy that is type IntTy
     603             :   const SCEV *getSizeOfExpr(Type *IntTy, Type *AllocTy);
     604             : 
     605             :   /// Return an expression for offsetof on the given field with type IntTy
     606             :   const SCEV *getOffsetOfExpr(Type *IntTy, StructType *STy, unsigned FieldNo);
     607             : 
     608             :   /// Return the SCEV object corresponding to -V.
     609             :   const SCEV *getNegativeSCEV(const SCEV *V,
     610             :                               SCEV::NoWrapFlags Flags = SCEV::FlagAnyWrap);
     611             : 
     612             :   /// Return the SCEV object corresponding to ~V.
     613             :   const SCEV *getNotSCEV(const SCEV *V);
     614             : 
     615             :   /// Return LHS-RHS.  Minus is represented in SCEV as A+B*-1.
     616             :   const SCEV *getMinusSCEV(const SCEV *LHS, const SCEV *RHS,
     617             :                            SCEV::NoWrapFlags Flags = SCEV::FlagAnyWrap,
     618             :                            unsigned Depth = 0);
     619             : 
     620             :   /// Return a SCEV corresponding to a conversion of the input value to the
     621             :   /// specified type.  If the type must be extended, it is zero extended.
     622             :   const SCEV *getTruncateOrZeroExtend(const SCEV *V, Type *Ty);
     623             : 
     624             :   /// Return a SCEV corresponding to a conversion of the input value to the
     625             :   /// specified type.  If the type must be extended, it is sign extended.
     626             :   const SCEV *getTruncateOrSignExtend(const SCEV *V, Type *Ty);
     627             : 
     628             :   /// Return a SCEV corresponding to a conversion of the input value to the
     629             :   /// specified type.  If the type must be extended, it is zero extended.  The
     630             :   /// conversion must not be narrowing.
     631             :   const SCEV *getNoopOrZeroExtend(const SCEV *V, Type *Ty);
     632             : 
     633             :   /// Return a SCEV corresponding to a conversion of the input value to the
     634             :   /// specified type.  If the type must be extended, it is sign extended.  The
     635             :   /// conversion must not be narrowing.
     636             :   const SCEV *getNoopOrSignExtend(const SCEV *V, Type *Ty);
     637             : 
     638             :   /// Return a SCEV corresponding to a conversion of the input value to the
     639             :   /// specified type. If the type must be extended, it is extended with
     640             :   /// unspecified bits. The conversion must not be narrowing.
     641             :   const SCEV *getNoopOrAnyExtend(const SCEV *V, Type *Ty);
     642             : 
     643             :   /// Return a SCEV corresponding to a conversion of the input value to the
     644             :   /// specified type.  The conversion must not be widening.
     645             :   const SCEV *getTruncateOrNoop(const SCEV *V, Type *Ty);
     646             : 
     647             :   /// Promote the operands to the wider of the types using zero-extension, and
     648             :   /// then perform a umax operation with them.
     649             :   const SCEV *getUMaxFromMismatchedTypes(const SCEV *LHS, const SCEV *RHS);
     650             : 
     651             :   /// Promote the operands to the wider of the types using zero-extension, and
     652             :   /// then perform a umin operation with them.
     653             :   const SCEV *getUMinFromMismatchedTypes(const SCEV *LHS, const SCEV *RHS);
     654             : 
     655             :   /// Promote the operands to the wider of the types using zero-extension, and
     656             :   /// then perform a umin operation with them. N-ary function.
     657             :   const SCEV *getUMinFromMismatchedTypes(SmallVectorImpl<const SCEV *> &Ops);
     658             : 
     659             :   /// Transitively follow the chain of pointer-type operands until reaching a
     660             :   /// SCEV that does not have a single pointer operand. This returns a
     661             :   /// SCEVUnknown pointer for well-formed pointer-type expressions, but corner
     662             :   /// cases do exist.
     663             :   const SCEV *getPointerBase(const SCEV *V);
     664             : 
     665             :   /// Return a SCEV expression for the specified value at the specified scope
     666             :   /// in the program.  The L value specifies a loop nest to evaluate the
     667             :   /// expression at, where null is the top-level or a specified loop is
     668             :   /// immediately inside of the loop.
     669             :   ///
     670             :   /// This method can be used to compute the exit value for a variable defined
     671             :   /// in a loop by querying what the value will hold in the parent loop.
     672             :   ///
     673             :   /// In the case that a relevant loop exit value cannot be computed, the
     674             :   /// original value V is returned.
     675             :   const SCEV *getSCEVAtScope(const SCEV *S, const Loop *L);
     676             : 
     677             :   /// This is a convenience function which does getSCEVAtScope(getSCEV(V), L).
     678             :   const SCEV *getSCEVAtScope(Value *V, const Loop *L);
     679             : 
     680             :   /// Test whether entry to the loop is protected by a conditional between LHS
     681             :   /// and RHS.  This is used to help avoid max expressions in loop trip
     682             :   /// counts, and to eliminate casts.
     683             :   bool isLoopEntryGuardedByCond(const Loop *L, ICmpInst::Predicate Pred,
     684             :                                 const SCEV *LHS, const SCEV *RHS);
     685             : 
     686             :   /// Test whether the backedge of the loop is protected by a conditional
     687             :   /// between LHS and RHS.  This is used to eliminate casts.
     688             :   bool isLoopBackedgeGuardedByCond(const Loop *L, ICmpInst::Predicate Pred,
     689             :                                    const SCEV *LHS, const SCEV *RHS);
     690             : 
     691             :   /// Returns the maximum trip count of the loop if it is a single-exit
     692             :   /// loop and we can compute a small maximum for that loop.
     693             :   ///
     694             :   /// Implemented in terms of the \c getSmallConstantTripCount overload with
     695             :   /// the single exiting block passed to it. See that routine for details.
     696             :   unsigned getSmallConstantTripCount(const Loop *L);
     697             : 
     698             :   /// Returns the maximum trip count of this loop as a normal unsigned
     699             :   /// value. Returns 0 if the trip count is unknown or not constant. This
     700             :   /// "trip count" assumes that control exits via ExitingBlock. More
     701             :   /// precisely, it is the number of times that control may reach ExitingBlock
     702             :   /// before taking the branch. For loops with multiple exits, it may not be
     703             :   /// the number times that the loop header executes if the loop exits
     704             :   /// prematurely via another branch.
     705             :   unsigned getSmallConstantTripCount(const Loop *L, BasicBlock *ExitingBlock);
     706             : 
     707             :   /// Returns the upper bound of the loop trip count as a normal unsigned
     708             :   /// value.
     709             :   /// Returns 0 if the trip count is unknown or not constant.
     710             :   unsigned getSmallConstantMaxTripCount(const Loop *L);
     711             : 
     712             :   /// Returns the largest constant divisor of the trip count of the
     713             :   /// loop if it is a single-exit loop and we can compute a small maximum for
     714             :   /// that loop.
     715             :   ///
     716             :   /// Implemented in terms of the \c getSmallConstantTripMultiple overload with
     717             :   /// the single exiting block passed to it. See that routine for details.
     718             :   unsigned getSmallConstantTripMultiple(const Loop *L);
     719             : 
     720             :   /// Returns the largest constant divisor of the trip count of this loop as a
     721             :   /// normal unsigned value, if possible. This means that the actual trip
     722             :   /// count is always a multiple of the returned value (don't forget the trip
     723             :   /// count could very well be zero as well!). As explained in the comments
     724             :   /// for getSmallConstantTripCount, this assumes that control exits the loop
     725             :   /// via ExitingBlock.
     726             :   unsigned getSmallConstantTripMultiple(const Loop *L,
     727             :                                         BasicBlock *ExitingBlock);
     728             : 
     729             :   /// Get the expression for the number of loop iterations for which this loop
     730             :   /// is guaranteed not to exit via ExitingBlock. Otherwise return
     731             :   /// SCEVCouldNotCompute.
     732             :   const SCEV *getExitCount(const Loop *L, BasicBlock *ExitingBlock);
     733             : 
     734             :   /// If the specified loop has a predictable backedge-taken count, return it,
     735             :   /// otherwise return a SCEVCouldNotCompute object. The backedge-taken count is
     736             :   /// the number of times the loop header will be branched to from within the
     737             :   /// loop, assuming there are no abnormal exists like exception throws. This is
     738             :   /// one less than the trip count of the loop, since it doesn't count the first
     739             :   /// iteration, when the header is branched to from outside the loop.
     740             :   ///
     741             :   /// Note that it is not valid to call this method on a loop without a
     742             :   /// loop-invariant backedge-taken count (see
     743             :   /// hasLoopInvariantBackedgeTakenCount).
     744             :   const SCEV *getBackedgeTakenCount(const Loop *L);
     745             : 
     746             :   /// Similar to getBackedgeTakenCount, except it will add a set of
     747             :   /// SCEV predicates to Predicates that are required to be true in order for
     748             :   /// the answer to be correct. Predicates can be checked with run-time
     749             :   /// checks and can be used to perform loop versioning.
     750             :   const SCEV *getPredicatedBackedgeTakenCount(const Loop *L,
     751             :                                               SCEVUnionPredicate &Predicates);
     752             : 
     753             :   /// When successful, this returns a SCEVConstant that is greater than or equal
     754             :   /// to (i.e. a "conservative over-approximation") of the value returend by
     755             :   /// getBackedgeTakenCount.  If such a value cannot be computed, it returns the
     756             :   /// SCEVCouldNotCompute object.
     757             :   const SCEV *getMaxBackedgeTakenCount(const Loop *L);
     758             : 
     759             :   /// Return true if the backedge taken count is either the value returned by
     760             :   /// getMaxBackedgeTakenCount or zero.
     761             :   bool isBackedgeTakenCountMaxOrZero(const Loop *L);
     762             : 
     763             :   /// Return true if the specified loop has an analyzable loop-invariant
     764             :   /// backedge-taken count.
     765             :   bool hasLoopInvariantBackedgeTakenCount(const Loop *L);
     766             : 
     767             :   /// This method should be called by the client when it has changed a loop in
     768             :   /// a way that may effect ScalarEvolution's ability to compute a trip count,
     769             :   /// or if the loop is deleted.  This call is potentially expensive for large
     770             :   /// loop bodies.
     771             :   void forgetLoop(const Loop *L);
     772             : 
     773             :   // This method invokes forgetLoop for the outermost loop of the given loop
     774             :   // \p L, making ScalarEvolution forget about all this subtree. This needs to
     775             :   // be done whenever we make a transform that may affect the parameters of the
     776             :   // outer loop, such as exit counts for branches.
     777             :   void forgetTopmostLoop(const Loop *L);
     778             : 
     779             :   /// This method should be called by the client when it has changed a value
     780             :   /// in a way that may effect its value, or which may disconnect it from a
     781             :   /// def-use chain linking it to a loop.
     782             :   void forgetValue(Value *V);
     783             : 
     784             :   /// Called when the client has changed the disposition of values in
     785             :   /// this loop.
     786             :   ///
     787             :   /// We don't have a way to invalidate per-loop dispositions. Clear and
     788             :   /// recompute is simpler.
     789        2202 :   void forgetLoopDispositions(const Loop *L) { LoopDispositions.clear(); }
     790             : 
     791             :   /// Determine the minimum number of zero bits that S is guaranteed to end in
     792             :   /// (at every loop iteration).  It is, at the same time, the minimum number
     793             :   /// of times S is divisible by 2.  For example, given {4,+,8} it returns 2.
     794             :   /// If S is guaranteed to be 0, it returns the bitwidth of S.
     795             :   uint32_t GetMinTrailingZeros(const SCEV *S);
     796             : 
     797             :   /// Determine the unsigned range for a particular SCEV.
     798             :   /// NOTE: This returns a copy of the reference returned by getRangeRef.
     799        1498 :   ConstantRange getUnsignedRange(const SCEV *S) {
     800     1917423 :     return getRangeRef(S, HINT_RANGE_UNSIGNED);
     801             :   }
     802             : 
     803             :   /// Determine the min of the unsigned range for a particular SCEV.
     804             :   APInt getUnsignedRangeMin(const SCEV *S) {
     805       12657 :     return getRangeRef(S, HINT_RANGE_UNSIGNED).getUnsignedMin();
     806             :   }
     807             : 
     808             :   /// Determine the max of the unsigned range for a particular SCEV.
     809        2899 :   APInt getUnsignedRangeMax(const SCEV *S) {
     810      305560 :     return getRangeRef(S, HINT_RANGE_UNSIGNED).getUnsignedMax();
     811             :   }
     812             : 
     813             :   /// Determine the signed range for a particular SCEV.
     814             :   /// NOTE: This returns a copy of the reference returned by getRangeRef.
     815         382 :   ConstantRange getSignedRange(const SCEV *S) {
     816     1619408 :     return getRangeRef(S, HINT_RANGE_SIGNED);
     817             :   }
     818             : 
     819             :   /// Determine the min of the signed range for a particular SCEV.
     820       12282 :   APInt getSignedRangeMin(const SCEV *S) {
     821     2198206 :     return getRangeRef(S, HINT_RANGE_SIGNED).getSignedMin();
     822             :   }
     823             : 
     824             :   /// Determine the max of the signed range for a particular SCEV.
     825             :   APInt getSignedRangeMax(const SCEV *S) {
     826      178898 :     return getRangeRef(S, HINT_RANGE_SIGNED).getSignedMax();
     827             :   }
     828             : 
     829             :   /// Test if the given expression is known to be negative.
     830             :   bool isKnownNegative(const SCEV *S);
     831             : 
     832             :   /// Test if the given expression is known to be positive.
     833             :   bool isKnownPositive(const SCEV *S);
     834             : 
     835             :   /// Test if the given expression is known to be non-negative.
     836             :   bool isKnownNonNegative(const SCEV *S);
     837             : 
     838             :   /// Test if the given expression is known to be non-positive.
     839             :   bool isKnownNonPositive(const SCEV *S);
     840             : 
     841             :   /// Test if the given expression is known to be non-zero.
     842             :   bool isKnownNonZero(const SCEV *S);
     843             : 
     844             :   /// Splits SCEV expression \p S into two SCEVs. One of them is obtained from
     845             :   /// \p S by substitution of all AddRec sub-expression related to loop \p L
     846             :   /// with initial value of that SCEV. The second is obtained from \p S by
     847             :   /// substitution of all AddRec sub-expressions related to loop \p L with post
     848             :   /// increment of this AddRec in the loop \p L. In both cases all other AddRec
     849             :   /// sub-expressions (not related to \p L) remain the same.
     850             :   /// If the \p S contains non-invariant unknown SCEV the function returns
     851             :   /// CouldNotCompute SCEV in both values of std::pair.
     852             :   /// For example, for SCEV S={0, +, 1}<L1> + {0, +, 1}<L2> and loop L=L1
     853             :   /// the function returns pair:
     854             :   /// first = {0, +, 1}<L2>
     855             :   /// second = {1, +, 1}<L1> + {0, +, 1}<L2>
     856             :   /// We can see that for the first AddRec sub-expression it was replaced with
     857             :   /// 0 (initial value) for the first element and to {1, +, 1}<L1> (post
     858             :   /// increment value) for the second one. In both cases AddRec expression
     859             :   /// related to L2 remains the same.
     860             :   std::pair<const SCEV *, const SCEV *> SplitIntoInitAndPostInc(const Loop *L,
     861             :                                                                 const SCEV *S);
     862             : 
     863             :   /// We'd like to check the predicate on every iteration of the most dominated
     864             :   /// loop between loops used in LHS and RHS.
     865             :   /// To do this we use the following list of steps:
     866             :   /// 1. Collect set S all loops on which either LHS or RHS depend.
     867             :   /// 2. If S is non-empty
     868             :   /// a. Let PD be the element of S which is dominated by all other elements.
     869             :   /// b. Let E(LHS) be value of LHS on entry of PD.
     870             :   ///    To get E(LHS), we should just take LHS and replace all AddRecs that are
     871             :   ///    attached to PD on with their entry values.
     872             :   ///    Define E(RHS) in the same way.
     873             :   /// c. Let B(LHS) be value of L on backedge of PD.
     874             :   ///    To get B(LHS), we should just take LHS and replace all AddRecs that are
     875             :   ///    attached to PD on with their backedge values.
     876             :   ///    Define B(RHS) in the same way.
     877             :   /// d. Note that E(LHS) and E(RHS) are automatically available on entry of PD,
     878             :   ///    so we can assert on that.
     879             :   /// e. Return true if isLoopEntryGuardedByCond(Pred, E(LHS), E(RHS)) &&
     880             :   ///                   isLoopBackedgeGuardedByCond(Pred, B(LHS), B(RHS))
     881             :   bool isKnownViaInduction(ICmpInst::Predicate Pred, const SCEV *LHS,
     882             :                            const SCEV *RHS);
     883             : 
     884             :   /// Test if the given expression is known to satisfy the condition described
     885             :   /// by Pred, LHS, and RHS.
     886             :   bool isKnownPredicate(ICmpInst::Predicate Pred, const SCEV *LHS,
     887             :                         const SCEV *RHS);
     888             : 
     889             :   /// Test if the condition described by Pred, LHS, RHS is known to be true on
     890             :   /// every iteration of the loop of the recurrency LHS.
     891             :   bool isKnownOnEveryIteration(ICmpInst::Predicate Pred,
     892             :                                const SCEVAddRecExpr *LHS, const SCEV *RHS);
     893             : 
     894             :   /// Return true if, for all loop invariant X, the predicate "LHS `Pred` X"
     895             :   /// is monotonically increasing or decreasing.  In the former case set
     896             :   /// `Increasing` to true and in the latter case set `Increasing` to false.
     897             :   ///
     898             :   /// A predicate is said to be monotonically increasing if may go from being
     899             :   /// false to being true as the loop iterates, but never the other way
     900             :   /// around.  A predicate is said to be monotonically decreasing if may go
     901             :   /// from being true to being false as the loop iterates, but never the other
     902             :   /// way around.
     903             :   bool isMonotonicPredicate(const SCEVAddRecExpr *LHS, ICmpInst::Predicate Pred,
     904             :                             bool &Increasing);
     905             : 
     906             :   /// Return true if the result of the predicate LHS `Pred` RHS is loop
     907             :   /// invariant with respect to L.  Set InvariantPred, InvariantLHS and
     908             :   /// InvariantLHS so that InvariantLHS `InvariantPred` InvariantRHS is the
     909             :   /// loop invariant form of LHS `Pred` RHS.
     910             :   bool isLoopInvariantPredicate(ICmpInst::Predicate Pred, const SCEV *LHS,
     911             :                                 const SCEV *RHS, const Loop *L,
     912             :                                 ICmpInst::Predicate &InvariantPred,
     913             :                                 const SCEV *&InvariantLHS,
     914             :                                 const SCEV *&InvariantRHS);
     915             : 
     916             :   /// Simplify LHS and RHS in a comparison with predicate Pred. Return true
     917             :   /// iff any changes were made. If the operands are provably equal or
     918             :   /// unequal, LHS and RHS are set to the same value and Pred is set to either
     919             :   /// ICMP_EQ or ICMP_NE.
     920             :   bool SimplifyICmpOperands(ICmpInst::Predicate &Pred, const SCEV *&LHS,
     921             :                             const SCEV *&RHS, unsigned Depth = 0);
     922             : 
     923             :   /// Return the "disposition" of the given SCEV with respect to the given
     924             :   /// loop.
     925             :   LoopDisposition getLoopDisposition(const SCEV *S, const Loop *L);
     926             : 
     927             :   /// Return true if the value of the given SCEV is unchanging in the
     928             :   /// specified loop.
     929             :   bool isLoopInvariant(const SCEV *S, const Loop *L);
     930             : 
     931             :   /// Determine if the SCEV can be evaluated at loop's entry. It is true if it
     932             :   /// doesn't depend on a SCEVUnknown of an instruction which is dominated by
     933             :   /// the header of loop L.
     934             :   bool isAvailableAtLoopEntry(const SCEV *S, const Loop *L);
     935             : 
     936             :   /// Return true if the given SCEV changes value in a known way in the
     937             :   /// specified loop.  This property being true implies that the value is
     938             :   /// variant in the loop AND that we can emit an expression to compute the
     939             :   /// value of the expression at any particular loop iteration.
     940             :   bool hasComputableLoopEvolution(const SCEV *S, const Loop *L);
     941             : 
     942             :   /// Return the "disposition" of the given SCEV with respect to the given
     943             :   /// block.
     944             :   BlockDisposition getBlockDisposition(const SCEV *S, const BasicBlock *BB);
     945             : 
     946             :   /// Return true if elements that makes up the given SCEV dominate the
     947             :   /// specified basic block.
     948             :   bool dominates(const SCEV *S, const BasicBlock *BB);
     949             : 
     950             :   /// Return true if elements that makes up the given SCEV properly dominate
     951             :   /// the specified basic block.
     952             :   bool properlyDominates(const SCEV *S, const BasicBlock *BB);
     953             : 
     954             :   /// Test whether the given SCEV has Op as a direct or indirect operand.
     955             :   bool hasOperand(const SCEV *S, const SCEV *Op) const;
     956             : 
     957             :   /// Return the size of an element read or written by Inst.
     958             :   const SCEV *getElementSize(Instruction *Inst);
     959             : 
     960             :   /// Compute the array dimensions Sizes from the set of Terms extracted from
     961             :   /// the memory access function of this SCEVAddRecExpr (second step of
     962             :   /// delinearization).
     963             :   void findArrayDimensions(SmallVectorImpl<const SCEV *> &Terms,
     964             :                            SmallVectorImpl<const SCEV *> &Sizes,
     965             :                            const SCEV *ElementSize);
     966             : 
     967             :   void print(raw_ostream &OS) const;
     968             :   void verify() const;
     969             :   bool invalidate(Function &F, const PreservedAnalyses &PA,
     970             :                   FunctionAnalysisManager::Invalidator &Inv);
     971             : 
     972             :   /// Collect parametric terms occurring in step expressions (first step of
     973             :   /// delinearization).
     974             :   void collectParametricTerms(const SCEV *Expr,
     975             :                               SmallVectorImpl<const SCEV *> &Terms);
     976             : 
     977             :   /// Return in Subscripts the access functions for each dimension in Sizes
     978             :   /// (third step of delinearization).
     979             :   void computeAccessFunctions(const SCEV *Expr,
     980             :                               SmallVectorImpl<const SCEV *> &Subscripts,
     981             :                               SmallVectorImpl<const SCEV *> &Sizes);
     982             : 
     983             :   /// Split this SCEVAddRecExpr into two vectors of SCEVs representing the
     984             :   /// subscripts and sizes of an array access.
     985             :   ///
     986             :   /// The delinearization is a 3 step process: the first two steps compute the
     987             :   /// sizes of each subscript and the third step computes the access functions
     988             :   /// for the delinearized array:
     989             :   ///
     990             :   /// 1. Find the terms in the step functions
     991             :   /// 2. Compute the array size
     992             :   /// 3. Compute the access function: divide the SCEV by the array size
     993             :   ///    starting with the innermost dimensions found in step 2. The Quotient
     994             :   ///    is the SCEV to be divided in the next step of the recursion. The
     995             :   ///    Remainder is the subscript of the innermost dimension. Loop over all
     996             :   ///    array dimensions computed in step 2.
     997             :   ///
     998             :   /// To compute a uniform array size for several memory accesses to the same
     999             :   /// object, one can collect in step 1 all the step terms for all the memory
    1000             :   /// accesses, and compute in step 2 a unique array shape. This guarantees
    1001             :   /// that the array shape will be the same across all memory accesses.
    1002             :   ///
    1003             :   /// FIXME: We could derive the result of steps 1 and 2 from a description of
    1004             :   /// the array shape given in metadata.
    1005             :   ///
    1006             :   /// Example:
    1007             :   ///
    1008             :   /// A[][n][m]
    1009             :   ///
    1010             :   /// for i
    1011             :   ///   for j
    1012             :   ///     for k
    1013             :   ///       A[j+k][2i][5i] =
    1014             :   ///
    1015             :   /// The initial SCEV:
    1016             :   ///
    1017             :   /// A[{{{0,+,2*m+5}_i, +, n*m}_j, +, n*m}_k]
    1018             :   ///
    1019             :   /// 1. Find the different terms in the step functions:
    1020             :   /// -> [2*m, 5, n*m, n*m]
    1021             :   ///
    1022             :   /// 2. Compute the array size: sort and unique them
    1023             :   /// -> [n*m, 2*m, 5]
    1024             :   /// find the GCD of all the terms = 1
    1025             :   /// divide by the GCD and erase constant terms
    1026             :   /// -> [n*m, 2*m]
    1027             :   /// GCD = m
    1028             :   /// divide by GCD -> [n, 2]
    1029             :   /// remove constant terms
    1030             :   /// -> [n]
    1031             :   /// size of the array is A[unknown][n][m]
    1032             :   ///
    1033             :   /// 3. Compute the access function
    1034             :   /// a. Divide {{{0,+,2*m+5}_i, +, n*m}_j, +, n*m}_k by the innermost size m
    1035             :   /// Quotient: {{{0,+,2}_i, +, n}_j, +, n}_k
    1036             :   /// Remainder: {{{0,+,5}_i, +, 0}_j, +, 0}_k
    1037             :   /// The remainder is the subscript of the innermost array dimension: [5i].
    1038             :   ///
    1039             :   /// b. Divide Quotient: {{{0,+,2}_i, +, n}_j, +, n}_k by next outer size n
    1040             :   /// Quotient: {{{0,+,0}_i, +, 1}_j, +, 1}_k
    1041             :   /// Remainder: {{{0,+,2}_i, +, 0}_j, +, 0}_k
    1042             :   /// The Remainder is the subscript of the next array dimension: [2i].
    1043             :   ///
    1044             :   /// The subscript of the outermost dimension is the Quotient: [j+k].
    1045             :   ///
    1046             :   /// Overall, we have: A[][n][m], and the access function: A[j+k][2i][5i].
    1047             :   void delinearize(const SCEV *Expr, SmallVectorImpl<const SCEV *> &Subscripts,
    1048             :                    SmallVectorImpl<const SCEV *> &Sizes,
    1049             :                    const SCEV *ElementSize);
    1050             : 
    1051             :   /// Return the DataLayout associated with the module this SCEV instance is
    1052             :   /// operating on.
    1053             :   const DataLayout &getDataLayout() const {
    1054     4649761 :     return F.getParent()->getDataLayout();
    1055             :   }
    1056             : 
    1057             :   const SCEVPredicate *getEqualPredicate(const SCEV *LHS, const SCEV *RHS);
    1058             : 
    1059             :   const SCEVPredicate *
    1060             :   getWrapPredicate(const SCEVAddRecExpr *AR,
    1061             :                    SCEVWrapPredicate::IncrementWrapFlags AddedFlags);
    1062             : 
    1063             :   /// Re-writes the SCEV according to the Predicates in \p A.
    1064             :   const SCEV *rewriteUsingPredicate(const SCEV *S, const Loop *L,
    1065             :                                     SCEVUnionPredicate &A);
    1066             :   /// Tries to convert the \p S expression to an AddRec expression,
    1067             :   /// adding additional predicates to \p Preds as required.
    1068             :   const SCEVAddRecExpr *convertSCEVToAddRecWithPredicates(
    1069             :       const SCEV *S, const Loop *L,
    1070             :       SmallPtrSetImpl<const SCEVPredicate *> &Preds);
    1071             : 
    1072             : private:
    1073             :   /// A CallbackVH to arrange for ScalarEvolution to be notified whenever a
    1074             :   /// Value is deleted.
    1075    14948650 :   class SCEVCallbackVH final : public CallbackVH {
    1076             :     ScalarEvolution *SE;
    1077             : 
    1078             :     void deleted() override;
    1079             :     void allUsesReplacedWith(Value *New) override;
    1080             : 
    1081             :   public:
    1082             :     SCEVCallbackVH(Value *V, ScalarEvolution *SE = nullptr);
    1083             :   };
    1084             : 
    1085             :   friend class SCEVCallbackVH;
    1086             :   friend class SCEVExpander;
    1087             :   friend class SCEVUnknown;
    1088             : 
    1089             :   /// The function we are analyzing.
    1090             :   Function &F;
    1091             : 
    1092             :   /// Does the module have any calls to the llvm.experimental.guard intrinsic
    1093             :   /// at all?  If this is false, we avoid doing work that will only help if
    1094             :   /// thare are guards present in the IR.
    1095             :   bool HasGuards;
    1096             : 
    1097             :   /// The target library information for the target we are targeting.
    1098             :   TargetLibraryInfo &TLI;
    1099             : 
    1100             :   /// The tracker for \@llvm.assume intrinsics in this function.
    1101             :   AssumptionCache &AC;
    1102             : 
    1103             :   /// The dominator tree.
    1104             :   DominatorTree &DT;
    1105             : 
    1106             :   /// The loop information for the function we are currently analyzing.
    1107             :   LoopInfo &LI;
    1108             : 
    1109             :   /// This SCEV is used to represent unknown trip counts and things.
    1110             :   std::unique_ptr<SCEVCouldNotCompute> CouldNotCompute;
    1111             : 
    1112             :   /// The type for HasRecMap.
    1113             :   using HasRecMapType = DenseMap<const SCEV *, bool>;
    1114             : 
    1115             :   /// This is a cache to record whether a SCEV contains any scAddRecExpr.
    1116             :   HasRecMapType HasRecMap;
    1117             : 
    1118             :   /// The type for ExprValueMap.
    1119             :   using ValueOffsetPair = std::pair<Value *, ConstantInt *>;
    1120             :   using ExprValueMapType = DenseMap<const SCEV *, SetVector<ValueOffsetPair>>;
    1121             : 
    1122             :   /// ExprValueMap -- This map records the original values from which
    1123             :   /// the SCEV expr is generated from.
    1124             :   ///
    1125             :   /// We want to represent the mapping as SCEV -> ValueOffsetPair instead
    1126             :   /// of SCEV -> Value:
    1127             :   /// Suppose we know S1 expands to V1, and
    1128             :   ///  S1 = S2 + C_a
    1129             :   ///  S3 = S2 + C_b
    1130             :   /// where C_a and C_b are different SCEVConstants. Then we'd like to
    1131             :   /// expand S3 as V1 - C_a + C_b instead of expanding S2 literally.
    1132             :   /// It is helpful when S2 is a complex SCEV expr.
    1133             :   ///
    1134             :   /// In order to do that, we represent ExprValueMap as a mapping from
    1135             :   /// SCEV to ValueOffsetPair. We will save both S1->{V1, 0} and
    1136             :   /// S2->{V1, C_a} into the map when we create SCEV for V1. When S3
    1137             :   /// is expanded, it will first expand S2 to V1 - C_a because of
    1138             :   /// S2->{V1, C_a} in the map, then expand S3 to V1 - C_a + C_b.
    1139             :   ///
    1140             :   /// Note: S->{V, Offset} in the ExprValueMap means S can be expanded
    1141             :   /// to V - Offset.
    1142             :   ExprValueMapType ExprValueMap;
    1143             : 
    1144             :   /// The type for ValueExprMap.
    1145             :   using ValueExprMapType =
    1146             :       DenseMap<SCEVCallbackVH, const SCEV *, DenseMapInfo<Value *>>;
    1147             : 
    1148             :   /// This is a cache of the values we have analyzed so far.
    1149             :   ValueExprMapType ValueExprMap;
    1150             : 
    1151             :   /// Mark predicate values currently being processed by isImpliedCond.
    1152             :   SmallPtrSet<Value *, 6> PendingLoopPredicates;
    1153             : 
    1154             :   /// Mark SCEVUnknown Phis currently being processed by getRangeRef.
    1155             :   SmallPtrSet<const PHINode *, 6> PendingPhiRanges;
    1156             : 
    1157             :   // Mark SCEVUnknown Phis currently being processed by isImpliedViaMerge.
    1158             :   SmallPtrSet<const PHINode *, 6> PendingMerges;
    1159             : 
    1160             :   /// Set to true by isLoopBackedgeGuardedByCond when we're walking the set of
    1161             :   /// conditions dominating the backedge of a loop.
    1162             :   bool WalkingBEDominatingConds = false;
    1163             : 
    1164             :   /// Set to true by isKnownPredicateViaSplitting when we're trying to prove a
    1165             :   /// predicate by splitting it into a set of independent predicates.
    1166             :   bool ProvingSplitPredicate = false;
    1167             : 
    1168             :   /// Memoized values for the GetMinTrailingZeros
    1169             :   DenseMap<const SCEV *, uint32_t> MinTrailingZerosCache;
    1170             : 
    1171             :   /// Return the Value set from which the SCEV expr is generated.
    1172             :   SetVector<ValueOffsetPair> *getSCEVValues(const SCEV *S);
    1173             : 
    1174             :   /// Private helper method for the GetMinTrailingZeros method
    1175             :   uint32_t GetMinTrailingZerosImpl(const SCEV *S);
    1176             : 
    1177             :   /// Information about the number of loop iterations for which a loop exit's
    1178             :   /// branch condition evaluates to the not-taken path.  This is a temporary
    1179             :   /// pair of exact and max expressions that are eventually summarized in
    1180             :   /// ExitNotTakenInfo and BackedgeTakenInfo.
    1181      155732 :   struct ExitLimit {
    1182             :     const SCEV *ExactNotTaken; // The exit is not taken exactly this many times
    1183             :     const SCEV *MaxNotTaken; // The exit is not taken at most this many times
    1184             : 
    1185             :     // Not taken either exactly MaxNotTaken or zero times
    1186             :     bool MaxOrZero = false;
    1187             : 
    1188             :     /// A set of predicate guards for this ExitLimit. The result is only valid
    1189             :     /// if all of the predicates in \c Predicates evaluate to 'true' at
    1190             :     /// run-time.
    1191             :     SmallPtrSet<const SCEVPredicate *, 4> Predicates;
    1192             : 
    1193             :     void addPredicate(const SCEVPredicate *P) {
    1194             :       assert(!isa<SCEVUnionPredicate>(P) && "Only add leaf predicates here!");
    1195          13 :       Predicates.insert(P);
    1196             :     }
    1197             : 
    1198             :     /*implicit*/ ExitLimit(const SCEV *E);
    1199             : 
    1200             :     ExitLimit(
    1201             :         const SCEV *E, const SCEV *M, bool MaxOrZero,
    1202             :         ArrayRef<const SmallPtrSetImpl<const SCEVPredicate *> *> PredSetList);
    1203             : 
    1204             :     ExitLimit(const SCEV *E, const SCEV *M, bool MaxOrZero,
    1205             :               const SmallPtrSetImpl<const SCEVPredicate *> &PredSet);
    1206             : 
    1207             :     ExitLimit(const SCEV *E, const SCEV *M, bool MaxOrZero);
    1208             : 
    1209             :     /// Test whether this ExitLimit contains any computed information, or
    1210             :     /// whether it's all SCEVCouldNotCompute values.
    1211       18458 :     bool hasAnyInfo() const {
    1212       47736 :       return !isa<SCEVCouldNotCompute>(ExactNotTaken) ||
    1213       29278 :              !isa<SCEVCouldNotCompute>(MaxNotTaken);
    1214             :     }
    1215             : 
    1216             :     bool hasOperand(const SCEV *S) const;
    1217             : 
    1218             :     /// Test whether this ExitLimit contains all information.
    1219             :     bool hasFullInfo() const {
    1220       24582 :       return !isa<SCEVCouldNotCompute>(ExactNotTaken);
    1221             :     }
    1222             :   };
    1223             : 
    1224             :   /// Information about the number of times a particular loop exit may be
    1225             :   /// reached before exiting the loop.
    1226       80468 :   struct ExitNotTakenInfo {
    1227             :     PoisoningVH<BasicBlock> ExitingBlock;
    1228             :     const SCEV *ExactNotTaken;
    1229             :     std::unique_ptr<SCEVUnionPredicate> Predicate;
    1230             : 
    1231             :     explicit ExitNotTakenInfo(PoisoningVH<BasicBlock> ExitingBlock,
    1232             :                               const SCEV *ExactNotTaken,
    1233             :                               std::unique_ptr<SCEVUnionPredicate> Predicate)
    1234             :         : ExitingBlock(ExitingBlock), ExactNotTaken(ExactNotTaken),
    1235       16382 :           Predicate(std::move(Predicate)) {}
    1236             : 
    1237             :     bool hasAlwaysTruePredicate() const {
    1238      198705 :       return !Predicate || Predicate->isAlwaysTrue();
    1239             :     }
    1240             :   };
    1241             : 
    1242             :   /// Information about the backedge-taken count of a loop. This currently
    1243             :   /// includes an exact count and a maximum count.
    1244             :   ///
    1245      707800 :   class BackedgeTakenInfo {
    1246             :     /// A list of computable exits and their not-taken counts.  Loops almost
    1247             :     /// never have more than one computable exit.
    1248             :     SmallVector<ExitNotTakenInfo, 1> ExitNotTaken;
    1249             : 
    1250             :     /// The pointer part of \c MaxAndComplete is an expression indicating the
    1251             :     /// least maximum backedge-taken count of the loop that is known, or a
    1252             :     /// SCEVCouldNotCompute. This expression is only valid if the predicates
    1253             :     /// associated with all loop exits are true.
    1254             :     ///
    1255             :     /// The integer part of \c MaxAndComplete is a boolean indicating if \c
    1256             :     /// ExitNotTaken has an element for every exiting block in the loop.
    1257             :     PointerIntPair<const SCEV *, 1> MaxAndComplete;
    1258             : 
    1259             :     /// True iff the backedge is taken either exactly Max or zero times.
    1260             :     bool MaxOrZero = false;
    1261             : 
    1262             :     /// \name Helper projection functions on \c MaxAndComplete.
    1263             :     /// @{
    1264             :     bool isComplete() const { return MaxAndComplete.getInt(); }
    1265             :     const SCEV *getMax() const { return MaxAndComplete.getPointer(); }
    1266             :     /// @}
    1267             : 
    1268             :   public:
    1269      639832 :     BackedgeTakenInfo() : MaxAndComplete(nullptr, 0) {}
    1270      685208 :     BackedgeTakenInfo(BackedgeTakenInfo &&) = default;
    1271             :     BackedgeTakenInfo &operator=(BackedgeTakenInfo &&) = default;
    1272             : 
    1273             :     using EdgeExitInfo = std::pair<BasicBlock *, ExitLimit>;
    1274             : 
    1275             :     /// Initialize BackedgeTakenInfo from a list of exact exit counts.
    1276             :     BackedgeTakenInfo(SmallVectorImpl<EdgeExitInfo> &&ExitCounts, bool Complete,
    1277             :                       const SCEV *MaxCount, bool MaxOrZero);
    1278             : 
    1279             :     /// Test whether this BackedgeTakenInfo contains any computed information,
    1280             :     /// or whether it's all SCEVCouldNotCompute values.
    1281             :     bool hasAnyInfo() const {
    1282       27638 :       return !ExitNotTaken.empty() || !isa<SCEVCouldNotCompute>(getMax());
    1283             :     }
    1284             : 
    1285             :     /// Test whether this BackedgeTakenInfo contains complete information.
    1286             :     bool hasFullInfo() const { return isComplete(); }
    1287             : 
    1288             :     /// Return an expression indicating the exact *backedge-taken*
    1289             :     /// count of the loop if it is known or SCEVCouldNotCompute
    1290             :     /// otherwise.  If execution makes it to the backedge on every
    1291             :     /// iteration (i.e. there are no abnormal exists like exception
    1292             :     /// throws and thread exits) then this is the number of times the
    1293             :     /// loop header will execute minus one.
    1294             :     ///
    1295             :     /// If the SCEV predicate associated with the answer can be different
    1296             :     /// from AlwaysTrue, we must add a (non null) Predicates argument.
    1297             :     /// The SCEV predicate associated with the answer will be added to
    1298             :     /// Predicates. A run-time check needs to be emitted for the SCEV
    1299             :     /// predicate in order for the answer to be valid.
    1300             :     ///
    1301             :     /// Note that we should always know if we need to pass a predicate
    1302             :     /// argument or not from the way the ExitCounts vector was computed.
    1303             :     /// If we allowed SCEV predicates to be generated when populating this
    1304             :     /// vector, this information can contain them and therefore a
    1305             :     /// SCEVPredicate argument should be added to getExact.
    1306             :     const SCEV *getExact(const Loop *L, ScalarEvolution *SE,
    1307             :                          SCEVUnionPredicate *Predicates = nullptr) const;
    1308             : 
    1309             :     /// Return the number of times this loop exit may fall through to the back
    1310             :     /// edge, or SCEVCouldNotCompute. The loop is guaranteed not to exit via
    1311             :     /// this block before this number of iterations, but may exit via another
    1312             :     /// block.
    1313             :     const SCEV *getExact(BasicBlock *ExitingBlock, ScalarEvolution *SE) const;
    1314             : 
    1315             :     /// Get the max backedge taken count for the loop.
    1316             :     const SCEV *getMax(ScalarEvolution *SE) const;
    1317             : 
    1318             :     /// Return true if the number of times this backedge is taken is either the
    1319             :     /// value returned by getMax or zero.
    1320             :     bool isMaxOrZero(ScalarEvolution *SE) const;
    1321             : 
    1322             :     /// Return true if any backedge taken count expressions refer to the given
    1323             :     /// subexpression.
    1324             :     bool hasOperand(const SCEV *S, ScalarEvolution *SE) const;
    1325             : 
    1326             :     /// Invalidate this result and free associated memory.
    1327             :     void clear();
    1328             :   };
    1329             : 
    1330             :   /// Cache the backedge-taken count of the loops for this function as they
    1331             :   /// are computed.
    1332             :   DenseMap<const Loop *, BackedgeTakenInfo> BackedgeTakenCounts;
    1333             : 
    1334             :   /// Cache the predicated backedge-taken count of the loops for this
    1335             :   /// function as they are computed.
    1336             :   DenseMap<const Loop *, BackedgeTakenInfo> PredicatedBackedgeTakenCounts;
    1337             : 
    1338             :   /// This map contains entries for all of the PHI instructions that we
    1339             :   /// attempt to compute constant evolutions for.  This allows us to avoid
    1340             :   /// potentially expensive recomputation of these properties.  An instruction
    1341             :   /// maps to null if we are unable to compute its exit value.
    1342             :   DenseMap<PHINode *, Constant *> ConstantEvolutionLoopExitValue;
    1343             : 
    1344             :   /// This map contains entries for all the expressions that we attempt to
    1345             :   /// compute getSCEVAtScope information for, which can be expensive in
    1346             :   /// extreme cases.
    1347             :   DenseMap<const SCEV *, SmallVector<std::pair<const Loop *, const SCEV *>, 2>>
    1348             :       ValuesAtScopes;
    1349             : 
    1350             :   /// Memoized computeLoopDisposition results.
    1351             :   DenseMap<const SCEV *,
    1352             :            SmallVector<PointerIntPair<const Loop *, 2, LoopDisposition>, 2>>
    1353             :       LoopDispositions;
    1354             : 
    1355             :   struct LoopProperties {
    1356             :     /// Set to true if the loop contains no instruction that can have side
    1357             :     /// effects (i.e. via throwing an exception, volatile or atomic access).
    1358             :     bool HasNoAbnormalExits;
    1359             : 
    1360             :     /// Set to true if the loop contains no instruction that can abnormally exit
    1361             :     /// the loop (i.e. via throwing an exception, by terminating the thread
    1362             :     /// cleanly or by infinite looping in a called function).  Strictly
    1363             :     /// speaking, the last one is not leaving the loop, but is identical to
    1364             :     /// leaving the loop for reasoning about undefined behavior.
    1365             :     bool HasNoSideEffects;
    1366             :   };
    1367             : 
    1368             :   /// Cache for \c getLoopProperties.
    1369             :   DenseMap<const Loop *, LoopProperties> LoopPropertiesCache;
    1370             : 
    1371             :   /// Return a \c LoopProperties instance for \p L, creating one if necessary.
    1372             :   LoopProperties getLoopProperties(const Loop *L);
    1373             : 
    1374             :   bool loopHasNoSideEffects(const Loop *L) {
    1375           7 :     return getLoopProperties(L).HasNoSideEffects;
    1376             :   }
    1377             : 
    1378             :   bool loopHasNoAbnormalExits(const Loop *L) {
    1379       21283 :     return getLoopProperties(L).HasNoAbnormalExits;
    1380             :   }
    1381             : 
    1382             :   /// Compute a LoopDisposition value.
    1383             :   LoopDisposition computeLoopDisposition(const SCEV *S, const Loop *L);
    1384             : 
    1385             :   /// Memoized computeBlockDisposition results.
    1386             :   DenseMap<
    1387             :       const SCEV *,
    1388             :       SmallVector<PointerIntPair<const BasicBlock *, 2, BlockDisposition>, 2>>
    1389             :       BlockDispositions;
    1390             : 
    1391             :   /// Compute a BlockDisposition value.
    1392             :   BlockDisposition computeBlockDisposition(const SCEV *S, const BasicBlock *BB);
    1393             : 
    1394             :   /// Memoized results from getRange
    1395             :   DenseMap<const SCEV *, ConstantRange> UnsignedRanges;
    1396             : 
    1397             :   /// Memoized results from getRange
    1398             :   DenseMap<const SCEV *, ConstantRange> SignedRanges;
    1399             : 
    1400             :   /// Used to parameterize getRange
    1401             :   enum RangeSignHint { HINT_RANGE_UNSIGNED, HINT_RANGE_SIGNED };
    1402             : 
    1403             :   /// Set the memoized range for the given SCEV.
    1404     1235746 :   const ConstantRange &setRange(const SCEV *S, RangeSignHint Hint,
    1405             :                                 ConstantRange CR) {
    1406     1235746 :     DenseMap<const SCEV *, ConstantRange> &Cache =
    1407             :         Hint == HINT_RANGE_UNSIGNED ? UnsignedRanges : SignedRanges;
    1408             : 
    1409     1235746 :     auto Pair = Cache.try_emplace(S, std::move(CR));
    1410     1235746 :     if (!Pair.second)
    1411        6550 :       Pair.first->second = std::move(CR);
    1412     1235746 :     return Pair.first->second;
    1413             :   }
    1414             : 
    1415             :   /// Determine the range for a particular SCEV.
    1416             :   /// NOTE: This returns a reference to an entry in a cache. It must be
    1417             :   /// copied if its needed for longer.
    1418             :   const ConstantRange &getRangeRef(const SCEV *S, RangeSignHint Hint);
    1419             : 
    1420             :   /// Determines the range for the affine SCEVAddRecExpr {\p Start,+,\p Stop}.
    1421             :   /// Helper for \c getRange.
    1422             :   ConstantRange getRangeForAffineAR(const SCEV *Start, const SCEV *Stop,
    1423             :                                     const SCEV *MaxBECount, unsigned BitWidth);
    1424             : 
    1425             :   /// Try to compute a range for the affine SCEVAddRecExpr {\p Start,+,\p
    1426             :   /// Stop} by "factoring out" a ternary expression from the add recurrence.
    1427             :   /// Helper called by \c getRange.
    1428             :   ConstantRange getRangeViaFactoring(const SCEV *Start, const SCEV *Stop,
    1429             :                                      const SCEV *MaxBECount, unsigned BitWidth);
    1430             : 
    1431             :   /// We know that there is no SCEV for the specified value.  Analyze the
    1432             :   /// expression.
    1433             :   const SCEV *createSCEV(Value *V);
    1434             : 
    1435             :   /// Provide the special handling we need to analyze PHI SCEVs.
    1436             :   const SCEV *createNodeForPHI(PHINode *PN);
    1437             : 
    1438             :   /// Helper function called from createNodeForPHI.
    1439             :   const SCEV *createAddRecFromPHI(PHINode *PN);
    1440             : 
    1441             :   /// A helper function for createAddRecFromPHI to handle simple cases.
    1442             :   const SCEV *createSimpleAffineAddRec(PHINode *PN, Value *BEValueV,
    1443             :                                             Value *StartValueV);
    1444             : 
    1445             :   /// Helper function called from createNodeForPHI.
    1446             :   const SCEV *createNodeFromSelectLikePHI(PHINode *PN);
    1447             : 
    1448             :   /// Provide special handling for a select-like instruction (currently this
    1449             :   /// is either a select instruction or a phi node).  \p I is the instruction
    1450             :   /// being processed, and it is assumed equivalent to "Cond ? TrueVal :
    1451             :   /// FalseVal".
    1452             :   const SCEV *createNodeForSelectOrPHI(Instruction *I, Value *Cond,
    1453             :                                        Value *TrueVal, Value *FalseVal);
    1454             : 
    1455             :   /// Provide the special handling we need to analyze GEP SCEVs.
    1456             :   const SCEV *createNodeForGEP(GEPOperator *GEP);
    1457             : 
    1458             :   /// Implementation code for getSCEVAtScope; called at most once for each
    1459             :   /// SCEV+Loop pair.
    1460             :   const SCEV *computeSCEVAtScope(const SCEV *S, const Loop *L);
    1461             : 
    1462             :   /// This looks up computed SCEV values for all instructions that depend on
    1463             :   /// the given instruction and removes them from the ValueExprMap map if they
    1464             :   /// reference SymName. This is used during PHI resolution.
    1465             :   void forgetSymbolicName(Instruction *I, const SCEV *SymName);
    1466             : 
    1467             :   /// Return the BackedgeTakenInfo for the given loop, lazily computing new
    1468             :   /// values if the loop hasn't been analyzed yet. The returned result is
    1469             :   /// guaranteed not to be predicated.
    1470             :   const BackedgeTakenInfo &getBackedgeTakenInfo(const Loop *L);
    1471             : 
    1472             :   /// Similar to getBackedgeTakenInfo, but will add predicates as required
    1473             :   /// with the purpose of returning complete information.
    1474             :   const BackedgeTakenInfo &getPredicatedBackedgeTakenInfo(const Loop *L);
    1475             : 
    1476             :   /// Compute the number of times the specified loop will iterate.
    1477             :   /// If AllowPredicates is set, we will create new SCEV predicates as
    1478             :   /// necessary in order to return an exact answer.
    1479             :   BackedgeTakenInfo computeBackedgeTakenCount(const Loop *L,
    1480             :                                               bool AllowPredicates = false);
    1481             : 
    1482             :   /// Compute the number of times the backedge of the specified loop will
    1483             :   /// execute if it exits via the specified block. If AllowPredicates is set,
    1484             :   /// this call will try to use a minimal set of SCEV predicates in order to
    1485             :   /// return an exact answer.
    1486             :   ExitLimit computeExitLimit(const Loop *L, BasicBlock *ExitingBlock,
    1487             :                              bool AllowPredicates = false);
    1488             : 
    1489             :   /// Compute the number of times the backedge of the specified loop will
    1490             :   /// execute if its exit condition were a conditional branch of ExitCond.
    1491             :   ///
    1492             :   /// \p ControlsExit is true if ExitCond directly controls the exit
    1493             :   /// branch. In this case, we can assume that the loop exits only if the
    1494             :   /// condition is true and can infer that failing to meet the condition prior
    1495             :   /// to integer wraparound results in undefined behavior.
    1496             :   ///
    1497             :   /// If \p AllowPredicates is set, this call will try to use a minimal set of
    1498             :   /// SCEV predicates in order to return an exact answer.
    1499             :   ExitLimit computeExitLimitFromCond(const Loop *L, Value *ExitCond,
    1500             :                                      bool ExitIfTrue, bool ControlsExit,
    1501             :                                      bool AllowPredicates = false);
    1502             : 
    1503             :   // Helper functions for computeExitLimitFromCond to avoid exponential time
    1504             :   // complexity.
    1505             : 
    1506       25805 :   class ExitLimitCache {
    1507             :     // It may look like we need key on the whole (L, ExitIfTrue, ControlsExit,
    1508             :     // AllowPredicates) tuple, but recursive calls to
    1509             :     // computeExitLimitFromCondCached from computeExitLimitFromCondImpl only
    1510             :     // vary the in \c ExitCond and \c ControlsExit parameters.  We remember the
    1511             :     // initial values of the other values to assert our assumption.
    1512             :     SmallDenseMap<PointerIntPair<Value *, 1>, ExitLimit> TripCountMap;
    1513             : 
    1514             :     const Loop *L;
    1515             :     bool ExitIfTrue;
    1516             :     bool AllowPredicates;
    1517             : 
    1518             :   public:
    1519             :     ExitLimitCache(const Loop *L, bool ExitIfTrue, bool AllowPredicates)
    1520       51610 :         : L(L), ExitIfTrue(ExitIfTrue), AllowPredicates(AllowPredicates) {}
    1521             : 
    1522             :     Optional<ExitLimit> find(const Loop *L, Value *ExitCond, bool ExitIfTrue,
    1523             :                              bool ControlsExit, bool AllowPredicates);
    1524             : 
    1525             :     void insert(const Loop *L, Value *ExitCond, bool ExitIfTrue,
    1526             :                 bool ControlsExit, bool AllowPredicates, const ExitLimit &EL);
    1527             :   };
    1528             : 
    1529             :   using ExitLimitCacheTy = ExitLimitCache;
    1530             : 
    1531             :   ExitLimit computeExitLimitFromCondCached(ExitLimitCacheTy &Cache,
    1532             :                                            const Loop *L, Value *ExitCond,
    1533             :                                            bool ExitIfTrue,
    1534             :                                            bool ControlsExit,
    1535             :                                            bool AllowPredicates);
    1536             :   ExitLimit computeExitLimitFromCondImpl(ExitLimitCacheTy &Cache, const Loop *L,
    1537             :                                          Value *ExitCond, bool ExitIfTrue,
    1538             :                                          bool ControlsExit,
    1539             :                                          bool AllowPredicates);
    1540             : 
    1541             :   /// Compute the number of times the backedge of the specified loop will
    1542             :   /// execute if its exit condition were a conditional branch of the ICmpInst
    1543             :   /// ExitCond and ExitIfTrue. If AllowPredicates is set, this call will try
    1544             :   /// to use a minimal set of SCEV predicates in order to return an exact
    1545             :   /// answer.
    1546             :   ExitLimit computeExitLimitFromICmp(const Loop *L, ICmpInst *ExitCond,
    1547             :                                      bool ExitIfTrue,
    1548             :                                      bool IsSubExpr,
    1549             :                                      bool AllowPredicates = false);
    1550             : 
    1551             :   /// Compute the number of times the backedge of the specified loop will
    1552             :   /// execute if its exit condition were a switch with a single exiting case
    1553             :   /// to ExitingBB.
    1554             :   ExitLimit computeExitLimitFromSingleExitSwitch(const Loop *L,
    1555             :                                                  SwitchInst *Switch,
    1556             :                                                  BasicBlock *ExitingBB,
    1557             :                                                  bool IsSubExpr);
    1558             : 
    1559             :   /// Given an exit condition of 'icmp op load X, cst', try to see if we can
    1560             :   /// compute the backedge-taken count.
    1561             :   ExitLimit computeLoadConstantCompareExitLimit(LoadInst *LI, Constant *RHS,
    1562             :                                                 const Loop *L,
    1563             :                                                 ICmpInst::Predicate p);
    1564             : 
    1565             :   /// Compute the exit limit of a loop that is controlled by a
    1566             :   /// "(IV >> 1) != 0" type comparison.  We cannot compute the exact trip
    1567             :   /// count in these cases (since SCEV has no way of expressing them), but we
    1568             :   /// can still sometimes compute an upper bound.
    1569             :   ///
    1570             :   /// Return an ExitLimit for a loop whose backedge is guarded by `LHS Pred
    1571             :   /// RHS`.
    1572             :   ExitLimit computeShiftCompareExitLimit(Value *LHS, Value *RHS, const Loop *L,
    1573             :                                          ICmpInst::Predicate Pred);
    1574             : 
    1575             :   /// If the loop is known to execute a constant number of times (the
    1576             :   /// condition evolves only from constants), try to evaluate a few iterations
    1577             :   /// of the loop until we get the exit condition gets a value of ExitWhen
    1578             :   /// (true or false).  If we cannot evaluate the exit count of the loop,
    1579             :   /// return CouldNotCompute.
    1580             :   const SCEV *computeExitCountExhaustively(const Loop *L, Value *Cond,
    1581             :                                            bool ExitWhen);
    1582             : 
    1583             :   /// Return the number of times an exit condition comparing the specified
    1584             :   /// value to zero will execute.  If not computable, return CouldNotCompute.
    1585             :   /// If AllowPredicates is set, this call will try to use a minimal set of
    1586             :   /// SCEV predicates in order to return an exact answer.
    1587             :   ExitLimit howFarToZero(const SCEV *V, const Loop *L, bool IsSubExpr,
    1588             :                          bool AllowPredicates = false);
    1589             : 
    1590             :   /// Return the number of times an exit condition checking the specified
    1591             :   /// value for nonzero will execute.  If not computable, return
    1592             :   /// CouldNotCompute.
    1593             :   ExitLimit howFarToNonZero(const SCEV *V, const Loop *L);
    1594             : 
    1595             :   /// Return the number of times an exit condition containing the specified
    1596             :   /// less-than comparison will execute.  If not computable, return
    1597             :   /// CouldNotCompute.
    1598             :   ///
    1599             :   /// \p isSigned specifies whether the less-than is signed.
    1600             :   ///
    1601             :   /// \p ControlsExit is true when the LHS < RHS condition directly controls
    1602             :   /// the branch (loops exits only if condition is true). In this case, we can
    1603             :   /// use NoWrapFlags to skip overflow checks.
    1604             :   ///
    1605             :   /// If \p AllowPredicates is set, this call will try to use a minimal set of
    1606             :   /// SCEV predicates in order to return an exact answer.
    1607             :   ExitLimit howManyLessThans(const SCEV *LHS, const SCEV *RHS, const Loop *L,
    1608             :                              bool isSigned, bool ControlsExit,
    1609             :                              bool AllowPredicates = false);
    1610             : 
    1611             :   ExitLimit howManyGreaterThans(const SCEV *LHS, const SCEV *RHS, const Loop *L,
    1612             :                                 bool isSigned, bool IsSubExpr,
    1613             :                                 bool AllowPredicates = false);
    1614             : 
    1615             :   /// Return a predecessor of BB (which may not be an immediate predecessor)
    1616             :   /// which has exactly one successor from which BB is reachable, or null if
    1617             :   /// no such block is found.
    1618             :   std::pair<BasicBlock *, BasicBlock *>
    1619             :   getPredecessorWithUniqueSuccessorForBB(BasicBlock *BB);
    1620             : 
    1621             :   /// Test whether the condition described by Pred, LHS, and RHS is true
    1622             :   /// whenever the given FoundCondValue value evaluates to true.
    1623             :   bool isImpliedCond(ICmpInst::Predicate Pred, const SCEV *LHS, const SCEV *RHS,
    1624             :                      Value *FoundCondValue, bool Inverse);
    1625             : 
    1626             :   /// Test whether the condition described by Pred, LHS, and RHS is true
    1627             :   /// whenever the condition described by FoundPred, FoundLHS, FoundRHS is
    1628             :   /// true.
    1629             :   bool isImpliedCond(ICmpInst::Predicate Pred, const SCEV *LHS, const SCEV *RHS,
    1630             :                      ICmpInst::Predicate FoundPred, const SCEV *FoundLHS,
    1631             :                      const SCEV *FoundRHS);
    1632             : 
    1633             :   /// Test whether the condition described by Pred, LHS, and RHS is true
    1634             :   /// whenever the condition described by Pred, FoundLHS, and FoundRHS is
    1635             :   /// true.
    1636             :   bool isImpliedCondOperands(ICmpInst::Predicate Pred, const SCEV *LHS,
    1637             :                              const SCEV *RHS, const SCEV *FoundLHS,
    1638             :                              const SCEV *FoundRHS);
    1639             : 
    1640             :   /// Test whether the condition described by Pred, LHS, and RHS is true
    1641             :   /// whenever the condition described by Pred, FoundLHS, and FoundRHS is
    1642             :   /// true. Here LHS is an operation that includes FoundLHS as one of its
    1643             :   /// arguments.
    1644             :   bool isImpliedViaOperations(ICmpInst::Predicate Pred,
    1645             :                               const SCEV *LHS, const SCEV *RHS,
    1646             :                               const SCEV *FoundLHS, const SCEV *FoundRHS,
    1647             :                               unsigned Depth = 0);
    1648             : 
    1649             :   /// Test whether the condition described by Pred, LHS, and RHS is true.
    1650             :   /// Use only simple non-recursive types of checks, such as range analysis etc.
    1651             :   bool isKnownViaNonRecursiveReasoning(ICmpInst::Predicate Pred,
    1652             :                                        const SCEV *LHS, const SCEV *RHS);
    1653             : 
    1654             :   /// Test whether the condition described by Pred, LHS, and RHS is true
    1655             :   /// whenever the condition described by Pred, FoundLHS, and FoundRHS is
    1656             :   /// true.
    1657             :   bool isImpliedCondOperandsHelper(ICmpInst::Predicate Pred, const SCEV *LHS,
    1658             :                                    const SCEV *RHS, const SCEV *FoundLHS,
    1659             :                                    const SCEV *FoundRHS);
    1660             : 
    1661             :   /// Test whether the condition described by Pred, LHS, and RHS is true
    1662             :   /// whenever the condition described by Pred, FoundLHS, and FoundRHS is
    1663             :   /// true.  Utility function used by isImpliedCondOperands.  Tries to get
    1664             :   /// cases like "X `sgt` 0 => X - 1 `sgt` -1".
    1665             :   bool isImpliedCondOperandsViaRanges(ICmpInst::Predicate Pred, const SCEV *LHS,
    1666             :                                       const SCEV *RHS, const SCEV *FoundLHS,
    1667             :                                       const SCEV *FoundRHS);
    1668             : 
    1669             :   /// Return true if the condition denoted by \p LHS \p Pred \p RHS is implied
    1670             :   /// by a call to \c @llvm.experimental.guard in \p BB.
    1671             :   bool isImpliedViaGuard(BasicBlock *BB, ICmpInst::Predicate Pred,
    1672             :                          const SCEV *LHS, const SCEV *RHS);
    1673             : 
    1674             :   /// Test whether the condition described by Pred, LHS, and RHS is true
    1675             :   /// whenever the condition described by Pred, FoundLHS, and FoundRHS is
    1676             :   /// true.
    1677             :   ///
    1678             :   /// This routine tries to rule out certain kinds of integer overflow, and
    1679             :   /// then tries to reason about arithmetic properties of the predicates.
    1680             :   bool isImpliedCondOperandsViaNoOverflow(ICmpInst::Predicate Pred,
    1681             :                                           const SCEV *LHS, const SCEV *RHS,
    1682             :                                           const SCEV *FoundLHS,
    1683             :                                           const SCEV *FoundRHS);
    1684             : 
    1685             :   /// Test whether the condition described by Pred, LHS, and RHS is true
    1686             :   /// whenever the condition described by Pred, FoundLHS, and FoundRHS is
    1687             :   /// true.
    1688             :   ///
    1689             :   /// This routine tries to figure out predicate for Phis which are SCEVUnknown
    1690             :   /// if it is true for every possible incoming value from their respective
    1691             :   /// basic blocks.
    1692             :   bool isImpliedViaMerge(ICmpInst::Predicate Pred,
    1693             :                          const SCEV *LHS, const SCEV *RHS,
    1694             :                          const SCEV *FoundLHS, const SCEV *FoundRHS,
    1695             :                          unsigned Depth);
    1696             : 
    1697             :   /// If we know that the specified Phi is in the header of its containing
    1698             :   /// loop, we know the loop executes a constant number of times, and the PHI
    1699             :   /// node is just a recurrence involving constants, fold it.
    1700             :   Constant *getConstantEvolutionLoopExitValue(PHINode *PN, const APInt &BEs,
    1701             :                                               const Loop *L);
    1702             : 
    1703             :   /// Test if the given expression is known to satisfy the condition described
    1704             :   /// by Pred and the known constant ranges of LHS and RHS.
    1705             :   bool isKnownPredicateViaConstantRanges(ICmpInst::Predicate Pred,
    1706             :                                          const SCEV *LHS, const SCEV *RHS);
    1707             : 
    1708             :   /// Try to prove the condition described by "LHS Pred RHS" by ruling out
    1709             :   /// integer overflow.
    1710             :   ///
    1711             :   /// For instance, this will return true for "A s< (A + C)<nsw>" if C is
    1712             :   /// positive.
    1713             :   bool isKnownPredicateViaNoOverflow(ICmpInst::Predicate Pred, const SCEV *LHS,
    1714             :                                      const SCEV *RHS);
    1715             : 
    1716             :   /// Try to split Pred LHS RHS into logical conjunctions (and's) and try to
    1717             :   /// prove them individually.
    1718             :   bool isKnownPredicateViaSplitting(ICmpInst::Predicate Pred, const SCEV *LHS,
    1719             :                                     const SCEV *RHS);
    1720             : 
    1721             :   /// Try to match the Expr as "(L + R)<Flags>".
    1722             :   bool splitBinaryAdd(const SCEV *Expr, const SCEV *&L, const SCEV *&R,
    1723             :                       SCEV::NoWrapFlags &Flags);
    1724             : 
    1725             :   /// Compute \p LHS - \p RHS and returns the result as an APInt if it is a
    1726             :   /// constant, and None if it isn't.
    1727             :   ///
    1728             :   /// This is intended to be a cheaper version of getMinusSCEV.  We can be
    1729             :   /// frugal here since we just bail out of actually constructing and
    1730             :   /// canonicalizing an expression in the cases where the result isn't going
    1731             :   /// to be a constant.
    1732             :   Optional<APInt> computeConstantDifference(const SCEV *LHS, const SCEV *RHS);
    1733             : 
    1734             :   /// Drop memoized information computed for S.
    1735             :   void forgetMemoizedResults(const SCEV *S);
    1736             : 
    1737             :   /// Return an existing SCEV for V if there is one, otherwise return nullptr.
    1738             :   const SCEV *getExistingSCEV(Value *V);
    1739             : 
    1740             :   /// Return false iff given SCEV contains a SCEVUnknown with NULL value-
    1741             :   /// pointer.
    1742             :   bool checkValidity(const SCEV *S) const;
    1743             : 
    1744             :   /// Return true if `ExtendOpTy`({`Start`,+,`Step`}) can be proved to be
    1745             :   /// equal to {`ExtendOpTy`(`Start`),+,`ExtendOpTy`(`Step`)}.  This is
    1746             :   /// equivalent to proving no signed (resp. unsigned) wrap in
    1747             :   /// {`Start`,+,`Step`} if `ExtendOpTy` is `SCEVSignExtendExpr`
    1748             :   /// (resp. `SCEVZeroExtendExpr`).
    1749             :   template <typename ExtendOpTy>
    1750             :   bool proveNoWrapByVaryingStart(const SCEV *Start, const SCEV *Step,
    1751             :                                  const Loop *L);
    1752             : 
    1753             :   /// Try to prove NSW or NUW on \p AR relying on ConstantRange manipulation.
    1754             :   SCEV::NoWrapFlags proveNoWrapViaConstantRanges(const SCEVAddRecExpr *AR);
    1755             : 
    1756             :   bool isMonotonicPredicateImpl(const SCEVAddRecExpr *LHS,
    1757             :                                 ICmpInst::Predicate Pred, bool &Increasing);
    1758             : 
    1759             :   /// Return SCEV no-wrap flags that can be proven based on reasoning about
    1760             :   /// how poison produced from no-wrap flags on this value (e.g. a nuw add)
    1761             :   /// would trigger undefined behavior on overflow.
    1762             :   SCEV::NoWrapFlags getNoWrapFlagsFromUB(const Value *V);
    1763             : 
    1764             :   /// Return true if the SCEV corresponding to \p I is never poison.  Proving
    1765             :   /// this is more complex than proving that just \p I is never poison, since
    1766             :   /// SCEV commons expressions across control flow, and you can have cases
    1767             :   /// like:
    1768             :   ///
    1769             :   ///   idx0 = a + b;
    1770             :   ///   ptr[idx0] = 100;
    1771             :   ///   if (<condition>) {
    1772             :   ///     idx1 = a +nsw b;
    1773             :   ///     ptr[idx1] = 200;
    1774             :   ///   }
    1775             :   ///
    1776             :   /// where the SCEV expression (+ a b) is guaranteed to not be poison (and
    1777             :   /// hence not sign-overflow) only if "<condition>" is true.  Since both
    1778             :   /// `idx0` and `idx1` will be mapped to the same SCEV expression, (+ a b),
    1779             :   /// it is not okay to annotate (+ a b) with <nsw> in the above example.
    1780             :   bool isSCEVExprNeverPoison(const Instruction *I);
    1781             : 
    1782             :   /// This is like \c isSCEVExprNeverPoison but it specifically works for
    1783             :   /// instructions that will get mapped to SCEV add recurrences.  Return true
    1784             :   /// if \p I will never generate poison under the assumption that \p I is an
    1785             :   /// add recurrence on the loop \p L.
    1786             :   bool isAddRecNeverPoison(const Instruction *I, const Loop *L);
    1787             : 
    1788             :   /// Similar to createAddRecFromPHI, but with the additional flexibility of
    1789             :   /// suggesting runtime overflow checks in case casts are encountered.
    1790             :   /// If successful, the analysis records that for this loop, \p SymbolicPHI,
    1791             :   /// which is the UnknownSCEV currently representing the PHI, can be rewritten
    1792             :   /// into an AddRec, assuming some predicates; The function then returns the
    1793             :   /// AddRec and the predicates as a pair, and caches this pair in
    1794             :   /// PredicatedSCEVRewrites.
    1795             :   /// If the analysis is not successful, a mapping from the \p SymbolicPHI to
    1796             :   /// itself (with no predicates) is recorded, and a nullptr with an empty
    1797             :   /// predicates vector is returned as a pair.
    1798             :   Optional<std::pair<const SCEV *, SmallVector<const SCEVPredicate *, 3>>>
    1799             :   createAddRecFromPHIWithCastsImpl(const SCEVUnknown *SymbolicPHI);
    1800             : 
    1801             :   /// Compute the backedge taken count knowing the interval difference, the
    1802             :   /// stride and presence of the equality in the comparison.
    1803             :   const SCEV *computeBECount(const SCEV *Delta, const SCEV *Stride,
    1804             :                              bool Equality);
    1805             : 
    1806             :   /// Compute the maximum backedge count based on the range of values
    1807             :   /// permitted by Start, End, and Stride. This is for loops of the form
    1808             :   /// {Start, +, Stride} LT End.
    1809             :   ///
    1810             :   /// Precondition: the induction variable is known to be positive.  We *don't*
    1811             :   /// assert these preconditions so please be careful.
    1812             :   const SCEV *computeMaxBECountForLT(const SCEV *Start, const SCEV *Stride,
    1813             :                                      const SCEV *End, unsigned BitWidth,
    1814             :                                      bool IsSigned);
    1815             : 
    1816             :   /// Verify if an linear IV with positive stride can overflow when in a
    1817             :   /// less-than comparison, knowing the invariant term of the comparison,
    1818             :   /// the stride and the knowledge of NSW/NUW flags on the recurrence.
    1819             :   bool doesIVOverflowOnLT(const SCEV *RHS, const SCEV *Stride, bool IsSigned,
    1820             :                           bool NoWrap);
    1821             : 
    1822             :   /// Verify if an linear IV with negative stride can overflow when in a
    1823             :   /// greater-than comparison, knowing the invariant term of the comparison,
    1824             :   /// the stride and the knowledge of NSW/NUW flags on the recurrence.
    1825             :   bool doesIVOverflowOnGT(const SCEV *RHS, const SCEV *Stride, bool IsSigned,
    1826             :                           bool NoWrap);
    1827             : 
    1828             :   /// Get add expr already created or create a new one.
    1829             :   const SCEV *getOrCreateAddExpr(SmallVectorImpl<const SCEV *> &Ops,
    1830             :                                  SCEV::NoWrapFlags Flags);
    1831             : 
    1832             :   /// Get mul expr already created or create a new one.
    1833             :   const SCEV *getOrCreateMulExpr(SmallVectorImpl<const SCEV *> &Ops,
    1834             :                                  SCEV::NoWrapFlags Flags);
    1835             : 
    1836             :   /// Return x if \p Val is f(x) where f is a 1-1 function.
    1837             :   const SCEV *stripInjectiveFunctions(const SCEV *Val) const;
    1838             : 
    1839             :   /// Find all of the loops transitively used in \p S, and fill \p LoopsUsed.
    1840             :   /// A loop is considered "used" by an expression if it contains
    1841             :   /// an add rec on said loop.
    1842             :   void getUsedLoops(const SCEV *S, SmallPtrSetImpl<const Loop *> &LoopsUsed);
    1843             : 
    1844             :   /// Find all of the loops transitively used in \p S, and update \c LoopUsers
    1845             :   /// accordingly.
    1846             :   void addToLoopUseLists(const SCEV *S);
    1847             : 
    1848             :   /// Try to match the pattern generated by getURemExpr(A, B). If successful,
    1849             :   /// Assign A and B to LHS and RHS, respectively.
    1850             :   bool matchURem(const SCEV *Expr, const SCEV *&LHS, const SCEV *&RHS);
    1851             : 
    1852             :   FoldingSet<SCEV> UniqueSCEVs;
    1853             :   FoldingSet<SCEVPredicate> UniquePreds;
    1854             :   BumpPtrAllocator SCEVAllocator;
    1855             : 
    1856             :   /// This maps loops to a list of SCEV expressions that (transitively) use said
    1857             :   /// loop.
    1858             :   DenseMap<const Loop *, SmallVector<const SCEV *, 4>> LoopUsers;
    1859             : 
    1860             :   /// Cache tentative mappings from UnknownSCEVs in a Loop, to a SCEV expression
    1861             :   /// they can be rewritten into under certain predicates.
    1862             :   DenseMap<std::pair<const SCEVUnknown *, const Loop *>,
    1863             :            std::pair<const SCEV *, SmallVector<const SCEVPredicate *, 3>>>
    1864             :       PredicatedSCEVRewrites;
    1865             : 
    1866             :   /// The head of a linked list of all SCEVUnknown values that have been
    1867             :   /// allocated. This is used by releaseMemory to locate them all and call
    1868             :   /// their destructors.
    1869             :   SCEVUnknown *FirstUnknown = nullptr;
    1870             : };
    1871             : 
    1872             : /// Analysis pass that exposes the \c ScalarEvolution for a function.
    1873             : class ScalarEvolutionAnalysis
    1874             :     : public AnalysisInfoMixin<ScalarEvolutionAnalysis> {
    1875             :   friend AnalysisInfoMixin<ScalarEvolutionAnalysis>;
    1876             : 
    1877             :   static AnalysisKey Key;
    1878             : 
    1879             : public:
    1880             :   using Result = ScalarEvolution;
    1881             : 
    1882             :   ScalarEvolution run(Function &F, FunctionAnalysisManager &AM);
    1883             : };
    1884             : 
    1885             : /// Printer pass for the \c ScalarEvolutionAnalysis results.
    1886             : class ScalarEvolutionPrinterPass
    1887             :     : public PassInfoMixin<ScalarEvolutionPrinterPass> {
    1888             :   raw_ostream &OS;
    1889             : 
    1890             : public:
    1891           6 :   explicit ScalarEvolutionPrinterPass(raw_ostream &OS) : OS(OS) {}
    1892             : 
    1893             :   PreservedAnalyses run(Function &F, FunctionAnalysisManager &AM);
    1894             : };
    1895             : 
    1896      100990 : class ScalarEvolutionWrapperPass : public FunctionPass {
    1897             :   std::unique_ptr<ScalarEvolution> SE;
    1898             : 
    1899             : public:
    1900             :   static char ID;
    1901             : 
    1902             :   ScalarEvolutionWrapperPass();
    1903             : 
    1904             :   ScalarEvolution &getSE() { return *SE; }
    1905             :   const ScalarEvolution &getSE() const { return *SE; }
    1906             : 
    1907             :   bool runOnFunction(Function &F) override;
    1908             :   void releaseMemory() override;
    1909             :   void getAnalysisUsage(AnalysisUsage &AU) const override;
    1910             :   void print(raw_ostream &OS, const Module * = nullptr) const override;
    1911             :   void verifyAnalysis() const override;
    1912             : };
    1913             : 
    1914             : /// An interface layer with SCEV used to manage how we see SCEV expressions
    1915             : /// for values in the context of existing predicates. We can add new
    1916             : /// predicates, but we cannot remove them.
    1917             : ///
    1918             : /// This layer has multiple purposes:
    1919             : ///   - provides a simple interface for SCEV versioning.
    1920             : ///   - guarantees that the order of transformations applied on a SCEV
    1921             : ///     expression for a single Value is consistent across two different
    1922             : ///     getSCEV calls. This means that, for example, once we've obtained
    1923             : ///     an AddRec expression for a certain value through expression
    1924             : ///     rewriting, we will continue to get an AddRec expression for that
    1925             : ///     Value.
    1926             : ///   - lowers the number of expression rewrites.
    1927       18888 : class PredicatedScalarEvolution {
    1928             : public:
    1929             :   PredicatedScalarEvolution(ScalarEvolution &SE, Loop &L);
    1930             : 
    1931             :   const SCEVUnionPredicate &getUnionPredicate() const;
    1932             : 
    1933             :   /// Returns the SCEV expression of V, in the context of the current SCEV
    1934             :   /// predicate.  The order of transformations applied on the expression of V
    1935             :   /// returned by ScalarEvolution is guaranteed to be preserved, even when
    1936             :   /// adding new predicates.
    1937             :   const SCEV *getSCEV(Value *V);
    1938             : 
    1939             :   /// Get the (predicated) backedge count for the analyzed loop.
    1940             :   const SCEV *getBackedgeTakenCount();
    1941             : 
    1942             :   /// Adds a new predicate.
    1943             :   void addPredicate(const SCEVPredicate &Pred);
    1944             : 
    1945             :   /// Attempts to produce an AddRecExpr for V by adding additional SCEV
    1946             :   /// predicates. If we can't transform the expression into an AddRecExpr we
    1947             :   /// return nullptr and not add additional SCEV predicates to the current
    1948             :   /// context.
    1949             :   const SCEVAddRecExpr *getAsAddRec(Value *V);
    1950             : 
    1951             :   /// Proves that V doesn't overflow by adding SCEV predicate.
    1952             :   void setNoOverflow(Value *V, SCEVWrapPredicate::IncrementWrapFlags Flags);
    1953             : 
    1954             :   /// Returns true if we've proved that V doesn't wrap by means of a SCEV
    1955             :   /// predicate.
    1956             :   bool hasNoOverflow(Value *V, SCEVWrapPredicate::IncrementWrapFlags Flags);
    1957             : 
    1958             :   /// Returns the ScalarEvolution analysis used.
    1959             :   ScalarEvolution *getSE() const { return &SE; }
    1960             : 
    1961             :   /// We need to explicitly define the copy constructor because of FlagsMap.
    1962             :   PredicatedScalarEvolution(const PredicatedScalarEvolution &);
    1963             : 
    1964             :   /// Print the SCEV mappings done by the Predicated Scalar Evolution.
    1965             :   /// The printed text is indented by \p Depth.
    1966             :   void print(raw_ostream &OS, unsigned Depth) const;
    1967             : 
    1968             :   /// Check if \p AR1 and \p AR2 are equal, while taking into account
    1969             :   /// Equal predicates in Preds.
    1970             :   bool areAddRecsEqualWithPreds(const SCEVAddRecExpr *AR1,
    1971             :                                 const SCEVAddRecExpr *AR2) const;
    1972             : 
    1973             : private:
    1974             :   /// Increments the version number of the predicate.  This needs to be called
    1975             :   /// every time the SCEV predicate changes.
    1976             :   void updateGeneration();
    1977             : 
    1978             :   /// Holds a SCEV and the version number of the SCEV predicate used to
    1979             :   /// perform the rewrite of the expression.
    1980             :   using RewriteEntry = std::pair<unsigned, const SCEV *>;
    1981             : 
    1982             :   /// Maps a SCEV to the rewrite result of that SCEV at a certain version
    1983             :   /// number. If this number doesn't match the current Generation, we will
    1984             :   /// need to do a rewrite. To preserve the transformation order of previous
    1985             :   /// rewrites, we will rewrite the previous result instead of the original
    1986             :   /// SCEV.
    1987             :   DenseMap<const SCEV *, RewriteEntry> RewriteMap;
    1988             : 
    1989             :   /// Records what NoWrap flags we've added to a Value *.
    1990             :   ValueMap<Value *, SCEVWrapPredicate::IncrementWrapFlags> FlagsMap;
    1991             : 
    1992             :   /// The ScalarEvolution analysis.
    1993             :   ScalarEvolution &SE;
    1994             : 
    1995             :   /// The analyzed Loop.
    1996             :   const Loop &L;
    1997             : 
    1998             :   /// The SCEVPredicate that forms our context. We will rewrite all
    1999             :   /// expressions assuming that this predicate true.
    2000             :   SCEVUnionPredicate Preds;
    2001             : 
    2002             :   /// Marks the version of the SCEV predicate used. When rewriting a SCEV
    2003             :   /// expression we mark it with the version of the predicate. We use this to
    2004             :   /// figure out if the predicate has changed from the last rewrite of the
    2005             :   /// SCEV. If so, we need to perform a new rewrite.
    2006             :   unsigned Generation = 0;
    2007             : 
    2008             :   /// The backedge taken count.
    2009             :   const SCEV *BackedgeCount = nullptr;
    2010             : };
    2011             : 
    2012             : } // end namespace llvm
    2013             : 
    2014             : #endif // LLVM_ANALYSIS_SCALAREVOLUTION_H

Generated by: LCOV version 1.13