contrib/llvm/include/llvm/Analysis/ScalarEvolution.h

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