diff include/llvm/Analysis/ScalarEvolution.h @ 121:803732b1fca8

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