[SCEV] Remove the walk of the entire expression subgraph on every lookup of a cached SCEV for a particular value.

[chandlerc]

Summary

This was added waaaaay back in r185843 to handle the issue where
a SCEVUnknown wrapped around an IR value is deleted when the IR value is
deleted. It becomes null and makes the entire expression subgraph
containing it invalid. The fix was to check for these null nodes in the
subgraph on every query because SCEVs don't have uselists to update.
Unfortunately, this means querying every SCEV in a large graph is
trivially quadratic. Bad news. A great example of this is the unittest
ScalarEvolutionTests::SCEVAddExpr which becomes quite slow with a larger
number of expressions. When the loop was at 1000, the test took well
over 20 seconds for me.

Unfortunately, we *really* don't want to add uselist based invalidation
here because it will make removing instruction walk their subgraphs!
Especially considering that a common pattern is to delete the IR and
then forget the loop, this would be a big waste.

So this patch introduces a different approach. We add a generation count
to ScalarEvolution, and for composite expression SCEVs (SCEVExpr base
class in this patch, but a better name would be welocme) we track the
generation count at which the SCEV was valid. Then, each time the value
handle invalidates a SCEVUnknown node at the leaves of a subgraph it
also moves the generation count forward. When we validate, we check the
subgraphs with old generation counts, *and update the generation count
where valid*. We also clear out the part of the subgraph that we
trivially know is invalid rather than leaving it around to consume
memory. This essentially allows the validation of a subgraph to be
cached *between* queries to SCEVs.

Now, as long as the deletion of the IR and the queries to SCEV are
*batched*, the quadratic component falls away. This seems very likely to
be true in practice and certainly is true in the unittest. That unittest
with the loop size set to 1000 is over 5x faster with this patch.
Naturally, I can magnify this difference by making the size of the graph
larger. =]

When discussing this, there were some initial concerns around memory
overhead, but because this is isolated in compound expressions,
I suspect it will be fine. The largest overhead is likely from the unary
cast expressions, but even there it seems likely to be a reasonable cost
given the other things cached for every SCEV.

Unfortunately (but maybe fortunately?), this makes SCEV *much* more strict
about caching SCEVs across IR mutations because that can cause it to build new
expressions out of these cached SCEVs with skewed generations. The only failure
of this kind in 'check-llvm' was loop reroll which I've fixed here to forget
the loop after it deletes tons of instructions and not cache things across that
deletion.

However, if you run with this patch and assertions across the test suite, the
unroller also triggers the assert that catches skewed generations when building
new expresisons. This one is especially concerning as it appears to happen
before the unroller modifies any IR, making it look like some other pass forgot
to call forgetLoop? Unclear. It's also generally unclear whether we want this
degree of strictness, or if we don't, how/when we should re-validate cached
SCEVs.

I'm sadly out of time to keep hacking on this, but I wanted to send it out in
case others are interested in pushing this forward.

include/llvm/Analysis/ScalarEvolution.h

private:
   /// The dominator tree.
   ///
   DominatorTree &DT;
 
   /// The loop information for the function we are currently analyzing.
   ///
   LoopInfo &LI;
 
+  /// The generation count of the analysis.
+  ///
+  /// This is used by various parts of the analysis to track which SCEVs have
+  /// been lazily updated after some partial invalidation event.
+  uint64_t Generation;
+
   /// 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;
 
   /// This is a cache to record whether a SCEV contains any scAddRecExpr.
private:
   Optional<APInt> computeConstantDifference(const SCEV *LHS, const SCEV *RHS);
 
   /// Drop memoized information computed for S.
   void forgetMemoizedResults(const SCEV *S);
 
   /// Return an existing SCEV for V if there is one, otherwise return nullptr.
   const SCEV *getExistingSCEV(Value *V);
 
-  /// Return false iff given SCEV contains a SCEVUnknown with NULL value-
-  /// pointer.
-  bool checkValidity(const SCEV *S) const;
+  /// Validate a SCEV's subgraph.
+  ///
+  /// This will ensure that the given SCEV and all SCEVs it transitively
+  /// references are valid. If any part of the subgraph is detected to be
+  /// invalid, this will remove those SCEVs from the analysis and return false.
+  /// Note that this may not remove *all* invalid SCEVs from the analysis, but
+  /// will definitively remove `S` if invalid and will remove others
+  /// optimistically.
+  bool validateSCEVSubgraph(const SCEV *S);
 
   /// Return true if `ExtendOpTy`({`Start`,+,`Step`}) can be proved to be
   /// equal to {`ExtendOpTy`(`Start`),+,`ExtendOpTy`(`Step`)}.  This is
   /// equivalent to proving no signed (resp. unsigned) wrap in
   /// {`Start`,+,`Step`} if `ExtendOpTy` is `SCEVSignExtendExpr`
   /// (resp. `SCEVZeroExtendExpr`).
   ///
   template <typename ExtendOpTy>
public:
   /// 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);
 
+  /// Increment the SCEV generation.
+  ///
+  /// This shifts the generation count forward.
+  void incrementSCEVGeneration();
+
   /// 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);
private:
   /// the stride and the knowledge of NSW/NUW flags on the recurrence.
   bool doesIVOverflowOnGT(const SCEV *RHS, const SCEV *Stride, bool IsSigned,
                           bool NoWrap);
 
   /// Get add expr already created or create a new one
   const SCEV *getOrCreateAddExpr(SmallVectorImpl<const SCEV *> &Ops,
                                  SCEV::NoWrapFlags Flags);
 
+  SCEV *lookupUniqueSCEV(const FoldingSetNodeID &ID, void *&IP) {
+    if (SCEV *S = UniqueSCEVs.FindNodeOrInsertPos(ID, IP))
+      if (validateSCEVSubgraph(S))
+        return S;
+    return nullptr;
+  }
+
 private:
   FoldingSet<SCEV> UniqueSCEVs;
   FoldingSet<SCEVPredicate> UniquePreds;
   BumpPtrAllocator SCEVAllocator;
 
   /// The head of a linked list of all SCEVUnknown values that have been
   /// allocated. This is used by releaseMemory to locate them all and call
   /// their destructors.

include/llvm/Analysis/ScalarEvolutionExpressions.h

public:
     Type *getType() const { return V->getType(); }
 
     /// Methods for support type inquiry through isa, cast, and dyn_cast:
     static inline bool classof(const SCEV *S) {
       return S->getSCEVType() == scConstant;
     }
   };
 
+  /// This is the base class for all expression classes.
+  ///
+  /// The common aspect to them is that they reference other SCEVs as part of
+  /// their definition and so we need to be able to invalidate them when part
+  /// of their expression graph changes.
+  class SCEVExpr : public SCEV {
+  private:
+    // This is mutable as it inherently doesn't make up part of the SCEV state.
+    mutable uint64_t Generation;
+
+  public:
+    explicit SCEVExpr(const FoldingSetNodeIDRef ID, unsigned SCEVTy,
+                      uint64_t CurrentGeneration)
+        : SCEV(ID, SCEVTy), Generation(CurrentGeneration) {}
+
+    uint64_t getGeneration() const { return Generation; }
+
+    void setGeneration(uint64_t NewGen) const { Generation = NewGen; }
+
+    /// Methods for support type inquiry through isa, cast, and dyn_cast:
+    static inline bool classof(const SCEV *S) {
+    switch (S->getSCEVType()) {
+    case scTruncate:
+    case scZeroExtend:
+    case scSignExtend:
+    case scAddExpr:
+    case scMulExpr:
+    case scSMaxExpr:
+    case scUMaxExpr:
+    case scAddRecExpr:
+    case scUDivExpr:
+      return true;
+
+    case scUnknown:
+    case scConstant:
+    case scCouldNotCompute:
+      return false;
+    }
+      llvm_unreachable("Uncovered SCEV type!");
+    }
+
+#ifndef NDEBUG
+    /// Helper to assert (in debug builds) that SCEVs have the current
+    /// gerenation.
+    static void verifyGeneration(ArrayRef<const SCEV *> SCEVs,
+                                 uint64_t CurrentGeneration);
+#endif
+  };
+
   /// This is the base class for unary cast operator classes.
-  class SCEVCastExpr : public SCEV {
+  class SCEVCastExpr : public SCEVExpr {
   protected:
     const SCEV *Op;
     Type *Ty;
 
     SCEVCastExpr(const FoldingSetNodeIDRef ID,
-                 unsigned SCEVTy, const SCEV *op, Type *ty);
+                 unsigned SCEVTy, const SCEV *op, Type *ty,
+                 uint64_t CurrentGeneration);
 
   public:
     const SCEV *getOperand() const { return Op; }
     Type *getType() const { return Ty; }
 
     /// Methods for support type inquiry through isa, cast, and dyn_cast:
     static inline bool classof(const SCEV *S) {
       return S->getSCEVType() == scTruncate ||
              S->getSCEVType() == scZeroExtend ||
              S->getSCEVType() == scSignExtend;
     }
   };
 
   /// This class represents a truncation of an integer value to a
   /// smaller integer value.
   class SCEVTruncateExpr : public SCEVCastExpr {
     friend class ScalarEvolution;
 
     SCEVTruncateExpr(const FoldingSetNodeIDRef ID,
-                     const SCEV *op, Type *ty);
+                     const SCEV *op, Type *ty,
+                     uint64_t CurrentGeneration);
 
   public:
     /// Methods for support type inquiry through isa, cast, and dyn_cast:
     static inline bool classof(const SCEV *S) {
       return S->getSCEVType() == scTruncate;
     }
   };
 
   /// This class represents a zero extension of a small integer value
   /// to a larger integer value.
   class SCEVZeroExtendExpr : public SCEVCastExpr {
     friend class ScalarEvolution;
 
     SCEVZeroExtendExpr(const FoldingSetNodeIDRef ID,
-                       const SCEV *op, Type *ty);
+                       const SCEV *op, Type *ty,
+                     uint64_t CurrentGeneration);
 
   public:
     /// Methods for support type inquiry through isa, cast, and dyn_cast:
     static inline bool classof(const SCEV *S) {
       return S->getSCEVType() == scZeroExtend;
     }
   };
 
   /// This class represents a sign extension of a small integer value
   /// to a larger integer value.
   class SCEVSignExtendExpr : public SCEVCastExpr {
     friend class ScalarEvolution;
 
     SCEVSignExtendExpr(const FoldingSetNodeIDRef ID,
-                       const SCEV *op, Type *ty);
+                       const SCEV *op, Type *ty,
+                     uint64_t CurrentGeneration);
 
   public:
     /// Methods for support type inquiry through isa, cast, and dyn_cast:
     static inline bool classof(const SCEV *S) {
       return S->getSCEVType() == scSignExtend;
     }
   };
 
 
   /// This node is a base class providing common functionality for
   /// n'ary operators.
-  class SCEVNAryExpr : public SCEV {
+  class SCEVNAryExpr : public SCEVExpr {
   protected:
     // Since SCEVs are immutable, ScalarEvolution allocates operand
     // arrays with its SCEVAllocator, so this class just needs a simple
     // pointer rather than a more elaborate vector-like data structure.
     // This also avoids the need for a non-trivial destructor.
     const SCEV *const *Operands;
     size_t NumOperands;
 
-    SCEVNAryExpr(const FoldingSetNodeIDRef ID,
-                 enum SCEVTypes T, const SCEV *const *O, size_t N)
-      : SCEV(ID, T), Operands(O), NumOperands(N) {}
+    SCEVNAryExpr(const FoldingSetNodeIDRef ID, enum SCEVTypes T,
+                 const SCEV *const *O, size_t N, uint64_t CurrentGeneration)
+        : SCEVExpr(ID, T, CurrentGeneration), Operands(O), NumOperands(N) {
+#ifndef NDEBUG
+      verifyGeneration(makeArrayRef(Operands, NumOperands), CurrentGeneration);
+#endif
+    }
 
   public:
     size_t getNumOperands() const { return NumOperands; }
     const SCEV *getOperand(unsigned i) const {
       assert(i < NumOperands && "Operand index out of range!");
       return Operands[i];
     }
 
static inline bool classof(const SCEV *S) {
              S->getSCEVType() == scAddRecExpr;
     }
   };
 
   /// This node is the base class for n'ary commutative operators.
   class SCEVCommutativeExpr : public SCEVNAryExpr {
   protected:
     SCEVCommutativeExpr(const FoldingSetNodeIDRef ID,
-                        enum SCEVTypes T, const SCEV *const *O, size_t N)
-      : SCEVNAryExpr(ID, T, O, N) {}
+                        enum SCEVTypes T, const SCEV *const *O, size_t N,
+                        uint64_t CurrentGeneration)
+      : SCEVNAryExpr(ID, T, O, N, CurrentGeneration) {}
 
   public:
     /// Methods for support type inquiry through isa, cast, and dyn_cast:
     static inline bool classof(const SCEV *S) {
       return S->getSCEVType() == scAddExpr ||
              S->getSCEVType() == scMulExpr ||
              S->getSCEVType() == scSMaxExpr ||
              S->getSCEVType() == scUMaxExpr;
     }
 
     /// Set flags for a non-recurrence without clearing previously set flags.
     void setNoWrapFlags(NoWrapFlags Flags) {
       SubclassData |= Flags;
     }
   };
 
 
   /// This node represents an addition of some number of SCEVs.
   class SCEVAddExpr : public SCEVCommutativeExpr {
     friend class ScalarEvolution;
 
     SCEVAddExpr(const FoldingSetNodeIDRef ID,
-                const SCEV *const *O, size_t N)
-      : SCEVCommutativeExpr(ID, scAddExpr, O, N) {
+                const SCEV *const *O, size_t N,
+                        uint64_t CurrentGeneration)
+      : SCEVCommutativeExpr(ID, scAddExpr, O, N, CurrentGeneration) {
     }
 
   public:
     Type *getType() const {
       // Use the type of the last operand, which is likely to be a pointer
       // type, if there is one. This doesn't usually matter, but it can help
       // reduce casts when the expressions are expanded.
       return getOperand(getNumOperands() - 1)->getType();
     }
 
     /// Methods for support type inquiry through isa, cast, and dyn_cast:
     static inline bool classof(const SCEV *S) {
       return S->getSCEVType() == scAddExpr;
     }
   };
 
 
   /// This node represents multiplication of some number of SCEVs.
   class SCEVMulExpr : public SCEVCommutativeExpr {
     friend class ScalarEvolution;
 
     SCEVMulExpr(const FoldingSetNodeIDRef ID,
-                const SCEV *const *O, size_t N)
-      : SCEVCommutativeExpr(ID, scMulExpr, O, N) {
+                const SCEV *const *O, size_t N,
+                        uint64_t CurrentGeneration)
+      : SCEVCommutativeExpr(ID, scMulExpr, O, N, CurrentGeneration) {
     }
 
   public:
     /// Methods for support type inquiry through isa, cast, and dyn_cast:
     static inline bool classof(const SCEV *S) {
       return S->getSCEVType() == scMulExpr;
     }
   };
 
 
   /// This class represents a binary unsigned division operation.
-  class SCEVUDivExpr : public SCEV {
+  class SCEVUDivExpr : public SCEVExpr {
     friend class ScalarEvolution;
 
     const SCEV *LHS;
     const SCEV *RHS;
-    SCEVUDivExpr(const FoldingSetNodeIDRef ID, const SCEV *lhs, const SCEV *rhs)
-      : SCEV(ID, scUDivExpr), LHS(lhs), RHS(rhs) {}
+    SCEVUDivExpr(const FoldingSetNodeIDRef ID, const SCEV *lhs, const SCEV *rhs,
+                 uint64_t CurrentGeneration)
+        : SCEVExpr(ID, scUDivExpr, CurrentGeneration), LHS(lhs), RHS(rhs) {
+#ifndef NDEBUG
+      verifyGeneration({LHS, RHS}, CurrentGeneration);
+#endif
+    }
 
   public:
     const SCEV *getLHS() const { return LHS; }
     const SCEV *getRHS() const { return RHS; }
 
     Type *getType() const {
       // In most cases the types of LHS and RHS will be the same, but in some
       // crazy cases one or the other may be a pointer. ScalarEvolution doesn't
#endif
   /// All operands of an AddRec are required to be loop invariant.
   ///
   class SCEVAddRecExpr : public SCEVNAryExpr {
     friend class ScalarEvolution;
 
     const Loop *L;
 
     SCEVAddRecExpr(const FoldingSetNodeIDRef ID,
-                   const SCEV *const *O, size_t N, const Loop *l)
-      : SCEVNAryExpr(ID, scAddRecExpr, O, N), L(l) {}
+                   const SCEV *const *O, size_t N, const Loop *l,
+                        uint64_t CurrentGeneration)
+      : SCEVNAryExpr(ID, scAddRecExpr, O, N, CurrentGeneration), L(l) {}
 
   public:
     const SCEV *getStart() const { return Operands[0]; }
     const Loop *getLoop() const { return L; }
 
     /// Constructs and returns the recurrence indicating how much this
     /// expression steps by.  If this is a polynomial of degree N, it
     /// returns a chrec of degree N-1.  We cannot determine whether
public:
     }
   };
 
   /// This class represents a signed maximum selection.
   class SCEVSMaxExpr : public SCEVCommutativeExpr {
     friend class ScalarEvolution;
 
     SCEVSMaxExpr(const FoldingSetNodeIDRef ID,
-                 const SCEV *const *O, size_t N)
-      : SCEVCommutativeExpr(ID, scSMaxExpr, O, N) {
+                 const SCEV *const *O, size_t N,
+                        uint64_t CurrentGeneration)
+      : SCEVCommutativeExpr(ID, scSMaxExpr, O, N, CurrentGeneration) {
       // Max never overflows.
       setNoWrapFlags((NoWrapFlags)(FlagNUW | FlagNSW));
     }
 
   public:
     /// Methods for support type inquiry through isa, cast, and dyn_cast:
     static inline bool classof(const SCEV *S) {
       return S->getSCEVType() == scSMaxExpr;
     }
   };
 
 
   /// This class represents an unsigned maximum selection.
   class SCEVUMaxExpr : public SCEVCommutativeExpr {
     friend class ScalarEvolution;
 
     SCEVUMaxExpr(const FoldingSetNodeIDRef ID,
-                 const SCEV *const *O, size_t N)
-      : SCEVCommutativeExpr(ID, scUMaxExpr, O, N) {
+                 const SCEV *const *O, size_t N,
+                        uint64_t CurrentGeneration)
+      : SCEVCommutativeExpr(ID, scUMaxExpr, O, N, CurrentGeneration) {
       // Max never overflows.
       setNoWrapFlags((NoWrapFlags)(FlagNUW | FlagNSW));
     }
 
   public:
     /// Methods for support type inquiry through isa, cast, and dyn_cast:
     static inline bool classof(const SCEV *S) {
       return S->getSCEVType() == scUMaxExpr;

lib/Analysis/ScalarEvolution.cpp

bool SCEVCouldNotCompute::classof(const SCEV *S) {
   return S->getSCEVType() == scCouldNotCompute;
 }
 
 const SCEV *ScalarEvolution::getConstant(ConstantInt *V) {
   FoldingSetNodeID ID;
   ID.AddInteger(scConstant);
   ID.AddPointer(V);
   void *IP = nullptr;
-  if (const SCEV *S = UniqueSCEVs.FindNodeOrInsertPos(ID, IP)) return S;
+  if (const SCEV *S = lookupUniqueSCEV(ID, IP)) return S;
   SCEV *S = new (SCEVAllocator) SCEVConstant(ID.Intern(SCEVAllocator), V);
   UniqueSCEVs.InsertNode(S, IP);
   return S;
 }
 
 const SCEV *ScalarEvolution::getConstant(const APInt &Val) {
   return getConstant(ConstantInt::get(getContext(), Val));
 }
 
 const SCEV *
 ScalarEvolution::getConstant(Type *Ty, uint64_t V, bool isSigned) {
   IntegerType *ITy = cast<IntegerType>(getEffectiveSCEVType(Ty));
   return getConstant(ConstantInt::get(ITy, V, isSigned));
 }
 
-SCEVCastExpr::SCEVCastExpr(const FoldingSetNodeIDRef ID,
-                           unsigned SCEVTy, const SCEV *op, Type *ty)
-  : SCEV(ID, SCEVTy), Op(op), Ty(ty) {}
-
-SCEVTruncateExpr::SCEVTruncateExpr(const FoldingSetNodeIDRef ID,
-                                   const SCEV *op, Type *ty)
-  : SCEVCastExpr(ID, scTruncate, op, ty) {
+#ifndef NDEBUG
+void SCEVExpr::verifyGeneration(ArrayRef<const SCEV *> SCEVs,
+                                uint64_t CurrentGeneration) {
+  for (const SCEV *S : SCEVs) {
+    switch (S->getSCEVType()) {
+    case scUnknown:
+    case scConstant:
+      // No generation.
+      continue;
+
+    case scTruncate:
+    case scZeroExtend:
+    case scSignExtend:
+    case scAddExpr:
+    case scMulExpr:
+    case scSMaxExpr:
+    case scUMaxExpr:
+    case scAddRecExpr:
+    case scUDivExpr:
+      assert(cast<SCEVExpr>(S)->getGeneration() == CurrentGeneration &&
+             "Unexpected generation!");
+      continue;
+
+    case scCouldNotCompute:
+      llvm_unreachable("Attempt to use a SCEVCouldNotCompute object!");
+    }
+    llvm_unreachable("Unknown SCEV kind!");
+  }
+}
+#endif
+
+SCEVCastExpr::SCEVCastExpr(const FoldingSetNodeIDRef ID, unsigned SCEVTy,
+                           const SCEV *op, Type *ty, uint64_t CurrentGeneration)
+    : SCEVExpr(ID, SCEVTy, CurrentGeneration), Op(op), Ty(ty) {
+#ifndef NDEBUG
+  verifyGeneration({Op}, CurrentGeneration);
+#endif
+}
+
+SCEVTruncateExpr::SCEVTruncateExpr(const FoldingSetNodeIDRef ID, const SCEV *op,
+                                   Type *ty, uint64_t CurrentGeneration)
+    : SCEVCastExpr(ID, scTruncate, op, ty, CurrentGeneration) {
   assert((Op->getType()->isIntegerTy() || Op->getType()->isPointerTy()) &&
          (Ty->isIntegerTy() || Ty->isPointerTy()) &&
          "Cannot truncate non-integer value!");
 }
 
 SCEVZeroExtendExpr::SCEVZeroExtendExpr(const FoldingSetNodeIDRef ID,
-                                       const SCEV *op, Type *ty)
-  : SCEVCastExpr(ID, scZeroExtend, op, ty) {
+                                       const SCEV *op, Type *ty,
+                                       uint64_t CurrentGeneration)
+    : SCEVCastExpr(ID, scZeroExtend, op, ty, CurrentGeneration) {
   assert((Op->getType()->isIntegerTy() || Op->getType()->isPointerTy()) &&
          (Ty->isIntegerTy() || Ty->isPointerTy()) &&
          "Cannot zero extend non-integer value!");
 }
 
 SCEVSignExtendExpr::SCEVSignExtendExpr(const FoldingSetNodeIDRef ID,
-                                       const SCEV *op, Type *ty)
-  : SCEVCastExpr(ID, scSignExtend, op, ty) {
+                                       const SCEV *op, Type *ty,
+                                       uint64_t CurrentGeneration)
+    : SCEVCastExpr(ID, scSignExtend, op, ty, CurrentGeneration) {
   assert((Op->getType()->isIntegerTy() || Op->getType()->isPointerTy()) &&
          (Ty->isIntegerTy() || Ty->isPointerTy()) &&
          "Cannot sign extend non-integer value!");
 }
 
 void SCEVUnknown::deleted() {
   // Clear this SCEVUnknown from various maps.
   SE->forgetMemoizedResults(this);
 
   // Remove this SCEVUnknown from the uniquing map.
   SE->UniqueSCEVs.RemoveNode(this);
 
+  // Increment the generation so that users will be updated when next queried.
+  SE->incrementSCEVGeneration();
+
   // Release the value.
   setValPtr(nullptr);
 }
 
 void SCEVUnknown::allUsesReplacedWith(Value *New) {
   // Clear this SCEVUnknown from various maps.
   SE->forgetMemoizedResults(this);
 
assert(isSCEVable(Ty) &&
          "This is not a conversion to a SCEVable type!");
   Ty = getEffectiveSCEVType(Ty);
 
   FoldingSetNodeID ID;
   ID.AddInteger(scTruncate);
   ID.AddPointer(Op);
   ID.AddPointer(Ty);
   void *IP = nullptr;
-  if (const SCEV *S = UniqueSCEVs.FindNodeOrInsertPos(ID, IP)) return S;
+  if (const SCEV *S = lookupUniqueSCEV(ID, IP)) return S;
 
   // Fold if the operand is constant.
   if (const SCEVConstant *SC = dyn_cast<SCEVConstant>(Op))
     return getConstant(
       cast<ConstantInt>(ConstantExpr::getTrunc(SC->getValue(), Ty)));
 
   // trunc(trunc(x)) --> trunc(x)
   if (const SCEVTruncateExpr *ST = dyn_cast<SCEVTruncateExpr>(Op))
for (const SCEV *Op : AddRec->operands())
       Operands.push_back(getTruncateExpr(Op, Ty));
     return getAddRecExpr(Operands, AddRec->getLoop(), SCEV::FlagAnyWrap);
   }
 
   // The cast wasn't folded; create an explicit cast node. We can reuse
   // the existing insert position since if we get here, we won't have
   // made any changes which would invalidate it.
   SCEV *S = new (SCEVAllocator) SCEVTruncateExpr(ID.Intern(SCEVAllocator),
-                                                 Op, Ty);
+                                                 Op, Ty, Generation);
   UniqueSCEVs.InsertNode(S, IP);
   return S;
 }
 
 // Get the limit of a recurrence such that incrementing by Step cannot cause
 // signed overflow as long as the value of the recurrence within the
 // loop does not exceed this limit before incrementing.
 static const SCEV *getSignedOverflowLimitForStep(const SCEV *Step,
for (unsigned Delta : {-2, -1, 1, 2}) {
     const SCEV *PreStart = getConstant(StartAI - Delta);
 
     FoldingSetNodeID ID;
     ID.AddInteger(scAddRecExpr);
     ID.AddPointer(PreStart);
     ID.AddPointer(Step);
     ID.AddPointer(L);
     void *IP = nullptr;
-    const auto *PreAR =
-      static_cast<SCEVAddRecExpr *>(UniqueSCEVs.FindNodeOrInsertPos(ID, IP));
+    const auto *PreAR = static_cast<SCEVAddRecExpr *>(lookupUniqueSCEV(ID, IP));
 
     // Give up if we don't already have the add recurrence we need because
     // actually constructing an add recurrence is relatively expensive.
     if (PreAR && PreAR->getNoWrapFlags(WrapType)) {  // proves (2)
       const SCEV *DeltaS = getConstant(StartC->getType(), Delta);
       ICmpInst::Predicate Pred = ICmpInst::BAD_ICMP_PREDICATE;
       const SCEV *Limit = ExtendOpTraits<ExtendOpTy>::getOverflowLimitForStep(
           DeltaS, &Pred, this);
const SCEV *ScalarEvolution::getZeroExtendExpr(const SCEV *Op,
 
   // Before doing any expensive analysis, check to see if we've already
   // computed a SCEV for this Op and Ty.
   FoldingSetNodeID ID;
   ID.AddInteger(scZeroExtend);
   ID.AddPointer(Op);
   ID.AddPointer(Ty);
   void *IP = nullptr;
-  if (const SCEV *S = UniqueSCEVs.FindNodeOrInsertPos(ID, IP)) return S;
+  if (const SCEV *S = lookupUniqueSCEV(ID, IP)) return S;
 
   // zext(trunc(x)) --> zext(x) or x or trunc(x)
   if (const SCEVTruncateExpr *ST = dyn_cast<SCEVTruncateExpr>(Op)) {
     // It's possible the bits taken off by the truncate were all zero bits. If
     // so, we should be able to simplify this further.
     const SCEV *X = ST->getOperand();
     ConstantRange CR = getUnsignedRange(X);
     unsigned TruncBits = getTypeSizeInBits(ST->getType());
if (SA->hasNoUnsignedWrap()) {
       for (const auto *Op : SA->operands())
         Ops.push_back(getZeroExtendExpr(Op, Ty));
       return getAddExpr(Ops, SCEV::FlagNUW);
     }
   }
 
   // The cast wasn't folded; create an explicit cast node.
   // Recompute the insert position, as it may have been invalidated.
-  if (const SCEV *S = UniqueSCEVs.FindNodeOrInsertPos(ID, IP)) return S;
+  if (const SCEV *S = lookupUniqueSCEV(ID, IP)) return S;
   SCEV *S = new (SCEVAllocator) SCEVZeroExtendExpr(ID.Intern(SCEVAllocator),
-                                                   Op, Ty);
+                                                   Op, Ty, Generation);
   UniqueSCEVs.InsertNode(S, IP);
   return S;
 }
 
 const SCEV *ScalarEvolution::getSignExtendExpr(const SCEV *Op,
                                                Type *Ty) {
   assert(getTypeSizeInBits(Op->getType()) < getTypeSizeInBits(Ty) &&
          "This is not an extending conversion!");
const SCEV *ScalarEvolution::getSignExtendExpr(const SCEV *Op,
 
   // Before doing any expensive analysis, check to see if we've already
   // computed a SCEV for this Op and Ty.
   FoldingSetNodeID ID;
   ID.AddInteger(scSignExtend);
   ID.AddPointer(Op);
   ID.AddPointer(Ty);
   void *IP = nullptr;
-  if (const SCEV *S = UniqueSCEVs.FindNodeOrInsertPos(ID, IP)) return S;
+  if (const SCEV *S = lookupUniqueSCEV(ID, IP)) return S;
 
   // sext(trunc(x)) --> sext(x) or x or trunc(x)
   if (const SCEVTruncateExpr *ST = dyn_cast<SCEVTruncateExpr>(Op)) {
     // It's possible the bits taken off by the truncate were all sign bits. If
     // so, we should be able to simplify this further.
     const SCEV *X = ST->getOperand();
     ConstantRange CR = getSignedRange(X);
     unsigned TruncBits = getTypeSizeInBits(ST->getType());
const SCEV *ScalarEvolution::getSignExtendExpr(const SCEV *Op,
 
   // If the input value is provably positive and we could not simplify
   // away the sext build a zext instead.
   if (isKnownNonNegative(Op))
     return getZeroExtendExpr(Op, Ty);
 
   // The cast wasn't folded; create an explicit cast node.
   // Recompute the insert position, as it may have been invalidated.
-  if (const SCEV *S = UniqueSCEVs.FindNodeOrInsertPos(ID, IP)) return S;
+  if (const SCEV *S = lookupUniqueSCEV(ID, IP)) return S;
   SCEV *S = new (SCEVAllocator) SCEVSignExtendExpr(ID.Intern(SCEVAllocator),
-                                                   Op, Ty);
+                                                   Op, Ty, Generation);
   UniqueSCEVs.InsertNode(S, IP);
   return S;
 }
 
 /// getAnyExtendExpr - Return a SCEV for the given operand extended with
 /// unspecified bits out to the given type.
 ///
 const SCEV *ScalarEvolution::getAnyExtendExpr(const SCEV *Op,

 const SCEV *
 ScalarEvolution::getOrCreateAddExpr(SmallVectorImpl<const SCEV *> &Ops,
                                     SCEV::NoWrapFlags Flags) {
   FoldingSetNodeID ID;
   ID.AddInteger(scAddExpr);
   for (unsigned i = 0, e = Ops.size(); i != e; ++i)
     ID.AddPointer(Ops[i]);
   void *IP = nullptr;
-  SCEVAddExpr *S =
-      static_cast<SCEVAddExpr *>(UniqueSCEVs.FindNodeOrInsertPos(ID, IP));
+  auto *S = static_cast<SCEVAddExpr *>(lookupUniqueSCEV(ID, IP));
   if (!S) {
     const SCEV **O = SCEVAllocator.Allocate<const SCEV *>(Ops.size());
     std::uninitialized_copy(Ops.begin(), Ops.end(), O);
     S = new (SCEVAllocator)
-        SCEVAddExpr(ID.Intern(SCEVAllocator), O, Ops.size());
+        SCEVAddExpr(ID.Intern(SCEVAllocator), O, Ops.size(), Generation);
     UniqueSCEVs.InsertNode(S, IP);
   }
   S->setNoWrapFlags(Flags);
   return S;
 }
 
 static uint64_t umul_ov(uint64_t i, uint64_t j, bool &Overflow) {
   uint64_t k = i*j;
#endif
 
   // Okay, it looks like we really DO need an mul expr.  Check to see if we
   // already have one, otherwise create a new one.
   FoldingSetNodeID ID;
   ID.AddInteger(scMulExpr);
   for (unsigned i = 0, e = Ops.size(); i != e; ++i)
     ID.AddPointer(Ops[i]);
   void *IP = nullptr;
-  SCEVMulExpr *S =
-    static_cast<SCEVMulExpr *>(UniqueSCEVs.FindNodeOrInsertPos(ID, IP));
+  auto *S = static_cast<SCEVMulExpr *>(lookupUniqueSCEV(ID, IP));
   if (!S) {
     const SCEV **O = SCEVAllocator.Allocate<const SCEV *>(Ops.size());
     std::uninitialized_copy(Ops.begin(), Ops.end(), O);
     S = new (SCEVAllocator) SCEVMulExpr(ID.Intern(SCEVAllocator),
-                                        O, Ops.size());
+                                        O, Ops.size(), Generation);
     UniqueSCEVs.InsertNode(S, IP);
   }
   S->setNoWrapFlags(Flags);
   return S;
 }
 
 /// Get a canonical unsigned division expression, or something simpler if
 /// possible.
if (const SCEVConstant *RHSC = dyn_cast<SCEVConstant>(RHS)) {
     }
   }
 
   FoldingSetNodeID ID;
   ID.AddInteger(scUDivExpr);
   ID.AddPointer(LHS);
   ID.AddPointer(RHS);
   void *IP = nullptr;
-  if (const SCEV *S = UniqueSCEVs.FindNodeOrInsertPos(ID, IP)) return S;
+  if (const SCEV *S = lookupUniqueSCEV(ID, IP)) return S;
   SCEV *S = new (SCEVAllocator) SCEVUDivExpr(ID.Intern(SCEVAllocator),
-                                             LHS, RHS);
+                                             LHS, RHS, Generation);
   UniqueSCEVs.InsertNode(S, IP);
   return S;
 }
 
 static const APInt gcd(const SCEVConstant *C1, const SCEVConstant *C2) {
   APInt A = C1->getAPInt().abs();
   APInt B = C2->getAPInt().abs();
   uint32_t ABW = A.getBitWidth();
#endif
   // Okay, it looks like we really DO need an addrec expr.  Check to see if we
   // already have one, otherwise create a new one.
   FoldingSetNodeID ID;
   ID.AddInteger(scAddRecExpr);
   for (unsigned i = 0, e = Operands.size(); i != e; ++i)
     ID.AddPointer(Operands[i]);
   ID.AddPointer(L);
   void *IP = nullptr;
-  SCEVAddRecExpr *S =
-    static_cast<SCEVAddRecExpr *>(UniqueSCEVs.FindNodeOrInsertPos(ID, IP));
+  auto *S = static_cast<SCEVAddRecExpr *>(lookupUniqueSCEV(ID, IP));
   if (!S) {
     const SCEV **O = SCEVAllocator.Allocate<const SCEV *>(Operands.size());
     std::uninitialized_copy(Operands.begin(), Operands.end(), O);
     S = new (SCEVAllocator) SCEVAddRecExpr(ID.Intern(SCEVAllocator),
-                                           O, Operands.size(), L);
+                                           O, Operands.size(), L, Generation);
     UniqueSCEVs.InsertNode(S, IP);
   }
   S->setNoWrapFlags(Flags);
   return S;
 }
 
 const SCEV *
 ScalarEvolution::getGEPExpr(GEPOperator *GEP,
#endif
 
   // Okay, it looks like we really DO need an smax expr.  Check to see if we
   // already have one, otherwise create a new one.
   FoldingSetNodeID ID;
   ID.AddInteger(scSMaxExpr);
   for (unsigned i = 0, e = Ops.size(); i != e; ++i)
     ID.AddPointer(Ops[i]);
   void *IP = nullptr;
-  if (const SCEV *S = UniqueSCEVs.FindNodeOrInsertPos(ID, IP)) return S;
+  if (const SCEV *S = lookupUniqueSCEV(ID, IP)) return S;
   const SCEV **O = SCEVAllocator.Allocate<const SCEV *>(Ops.size());
   std::uninitialized_copy(Ops.begin(), Ops.end(), O);
   SCEV *S = new (SCEVAllocator) SCEVSMaxExpr(ID.Intern(SCEVAllocator),
-                                             O, Ops.size());
+                                             O, Ops.size(), Generation);
   UniqueSCEVs.InsertNode(S, IP);
   return S;
 }
 
 const SCEV *ScalarEvolution::getUMaxExpr(const SCEV *LHS,
                                          const SCEV *RHS) {
   SmallVector<const SCEV *, 2> Ops = {LHS, RHS};
   return getUMaxExpr(Ops);
#endif
 
   // Okay, it looks like we really DO need a umax expr.  Check to see if we
   // already have one, otherwise create a new one.
   FoldingSetNodeID ID;
   ID.AddInteger(scUMaxExpr);
   for (unsigned i = 0, e = Ops.size(); i != e; ++i)
     ID.AddPointer(Ops[i]);
   void *IP = nullptr;
-  if (const SCEV *S = UniqueSCEVs.FindNodeOrInsertPos(ID, IP)) return S;
+  if (const SCEV *S = lookupUniqueSCEV(ID, IP)) return S;
   const SCEV **O = SCEVAllocator.Allocate<const SCEV *>(Ops.size());
   std::uninitialized_copy(Ops.begin(), Ops.end(), O);
-  SCEV *S = new (SCEVAllocator) SCEVUMaxExpr(ID.Intern(SCEVAllocator),
-                                             O, Ops.size());
+  SCEV *S = new (SCEVAllocator)
+      SCEVUMaxExpr(ID.Intern(SCEVAllocator), O, Ops.size(), Generation);
   UniqueSCEVs.InsertNode(S, IP);
   return S;
 }
 
 const SCEV *ScalarEvolution::getSMinExpr(const SCEV *LHS,
                                          const SCEV *RHS) {
   // ~smax(~x, ~y) == smin(x, y).
   return getNotSCEV(getSMaxExpr(getNotSCEV(LHS), getNotSCEV(RHS)));
const SCEV *ScalarEvolution::getUnknown(Value *V) {
   // here.  createSCEV only calls getUnknown after checking for all other
   // interesting possibilities, and any other code that calls getUnknown
   // is doing so in order to hide a value from SCEV canonicalization.
 
   FoldingSetNodeID ID;
   ID.AddInteger(scUnknown);
   ID.AddPointer(V);
   void *IP = nullptr;
-  if (SCEV *S = UniqueSCEVs.FindNodeOrInsertPos(ID, IP)) {
+  if (const SCEV *S = lookupUniqueSCEV(ID, IP)) {
     assert(cast<SCEVUnknown>(S)->getValue() == V &&
            "Stale SCEVUnknown in uniquing map!");
     return S;
   }
   SCEV *S = new (SCEVAllocator) SCEVUnknown(ID.Intern(SCEVAllocator), V, this,
                                             FirstUnknown);
   FirstUnknown = cast<SCEVUnknown>(S);
   UniqueSCEVs.InsertNode(S, IP);
Type *ScalarEvolution::getEffectiveSCEVType(Type *Ty) const {
   assert(Ty->isPointerTy() && "Unexpected non-pointer non-integer type!");
   return getDataLayout().getIntPtrType(Ty);
 }
 
 const SCEV *ScalarEvolution::getCouldNotCompute() {
   return CouldNotCompute.get();
 }
 
-bool ScalarEvolution::checkValidity(const SCEV *S) const {
-  bool ContainsNulls = SCEVExprContains(S, [](const SCEV *S) {
-    auto *SU = dyn_cast<SCEVUnknown>(S);
-    return SU && SU->getValue() == nullptr;
-  });
+bool ScalarEvolution::validateSCEVSubgraph(const SCEV *S) {
+  // We do a depth-first search of the SCEV expression DAG looking for
+  // potentially invalid expressions. Any expression with a generation older
+  // than the current one needs to be recursively validated. Once recursively
+  // validated, we can update the generation count to prune subsequent walks.
+  SmallVector<std::pair<const SCEV *, size_t>, 8> Stack;
+  size_t Index = 0;
+  for (;;) {
+    switch (S->getSCEVType()) {
+    case scConstant:
+      break;
+    case scUnknown: {
+      const auto *SU = cast<SCEVUnknown>(S);
+      if (SU->getValue() == nullptr) {
+        while (!Stack.empty()) {
+          const SCEV *S = Stack.pop_back_val().first;
+          if (SetVector<ValueOffsetPair> *SV = getSCEVValues(S))
+            for (auto &VO : *SV)
+              ValueExprMap.erase(VO.first);
+          forgetMemoizedResults(S);
+        }
+        return false;
+      }
+      break;
+    }
+    case scTruncate:
+    case scZeroExtend:
+    case scSignExtend: {
+      const auto *Cast = cast<SCEVCastExpr>(S);
+      if (Index != 0) {
+        // Finished visiting subgraph and it remained valid, update generation
+        // and break.
+        Cast->setGeneration(Generation);
+        break;
+      }
+      // First visit, test and if necessary recurse.
+      if (Cast->getGeneration() == Generation)
+        break;
+
+      Stack.push_back({S, Index + 1});
+      S = Cast->getOperand();
+      Index = 0;
+      continue;
+    }
+    case scAddExpr:
+    case scMulExpr:
+    case scSMaxExpr:
+    case scUMaxExpr:
+    case scAddRecExpr: {
+      const auto *NAry = cast<SCEVNAryExpr>(S);
+      if (Index == NAry->getNumOperands()) {
+        NAry->setGeneration(Generation);
+        break;
+      }
+      if (NAry->getGeneration() == Generation)
+        break;
+
+      Stack.push_back({S, Index + 1});
+      S = NAry->getOperand(Index);
+      Index = 0;
+      continue;
+    }
+    case scUDivExpr: {
+      const auto *UDiv = cast<SCEVUDivExpr>(S);
+      if (Index == 2) {
+        UDiv->setGeneration(Generation);
+        break;
+      }
+
+      if (Index == 0 && UDiv->getGeneration() == Generation)
+          break;
 
-  return !ContainsNulls;
+      Stack.push_back({S, Index + 1});
+      S = Index == 0 ? UDiv->getLHS() : UDiv->getRHS();
+      Index = 0;
+      continue;
+    }
+    case scCouldNotCompute:
+      llvm_unreachable("Attempt to use a SCEVCouldNotCompute object!");
+    default:
+      llvm_unreachable("Unknown SCEV kind!");
+    }
+
+    if (Stack.empty())
+      break;
+    std::tie(S, Index) = Stack.pop_back_val();
+  }
+
+  return true;
 }
 
 bool ScalarEvolution::containsAddRecurrence(const SCEV *S) {
   HasRecMapType::iterator I = HasRecMap.find(S);
   if (I != HasRecMap.end())
     return I->second;
 
   bool FoundAddRec = SCEVExprContains(S, isa<SCEVAddRecExpr, const SCEV *>);
if (VerifySCEVMap) {
     // Check there is no dangling Value in the set returned.
     for (const auto &VE : SI->second)
       assert(ValueExprMap.count(VE.first));
   }
 #endif
   return &SI->second;
 }
 
+void ScalarEvolution::incrementSCEVGeneration() {
+  // Note that we never wrap the generation count. This would require calling
+  // this function 2^64 times which would require doing nothing else for a Unix
+  // epoch. However, there is no *semantic* problem wrapping here as the
+  // generation count works in the modular space rather than requiring an
+  // ordering.
+  assert(Generation != UINT64_MAX && "Likely memory corruption: the generation "
+                                     "count has reached the max value!");
+  ++Generation;
+}
+
 /// Erase Value from ValueExprMap and ExprValueMap. ValueExprMap.erase(V)
 /// cannot be used separately. eraseValueFromMap should be used to remove
 /// V from ValueExprMap and ExprValueMap at the same time.
 void ScalarEvolution::eraseValueFromMap(Value *V) {
   ValueExprMapType::iterator I = ValueExprMap.find_as(V);
   if (I != ValueExprMap.end()) {
     const SCEV *S = I->second;
     // Remove {V, 0} from the set of ExprValueMap[S]

 }
 
 const SCEV *ScalarEvolution::getExistingSCEV(Value *V) {
   assert(isSCEVable(V->getType()) && "Value is not SCEVable!");
 
   ValueExprMapType::iterator I = ValueExprMap.find_as(V);
   if (I != ValueExprMap.end()) {
     const SCEV *S = I->second;
-    if (checkValidity(S))
+    if (validateSCEVSubgraph(S))
       return S;
-    eraseValueFromMap(V);
-    forgetMemoizedResults(S);
   }
   return nullptr;
 }
 
 /// Return a SCEV corresponding to -V = -1*V
 ///
 const SCEV *ScalarEvolution::getNegativeSCEV(const SCEV *V,
                                              SCEV::NoWrapFlags Flags) {

 
 //===----------------------------------------------------------------------===//
 //                   ScalarEvolution Class Implementation
 //===----------------------------------------------------------------------===//
 
 ScalarEvolution::ScalarEvolution(Function &F, TargetLibraryInfo &TLI,
                                  AssumptionCache &AC, DominatorTree &DT,
                                  LoopInfo &LI)
-    : F(F), TLI(TLI), AC(AC), DT(DT), LI(LI),
+    : F(F), TLI(TLI), AC(AC), DT(DT), LI(LI), Generation(0),
       CouldNotCompute(new SCEVCouldNotCompute()),
       WalkingBEDominatingConds(false), ProvingSplitPredicate(false),
       ValuesAtScopes(64), LoopDispositions(64), BlockDispositions(64),
       FirstUnknown(nullptr) {
 
   // To use guards for proving predicates, we need to scan every instruction in
   // relevant basic blocks, and not just terminators.  Doing this is a waste of
   // time if the IR does not actually contain any calls to
   // @llvm.experimental.guard, so do a quick check and remember this beforehand.
   //
   // This pessimizes the case where a pass that preserves ScalarEvolution wants
   // to _add_ guards to the module when there weren't any before, and wants
   // ScalarEvolution to optimize based on those guards.  For now we prefer to be
   // efficient in lieu of being smart in that rather obscure case.
 
   auto *GuardDecl = F.getParent()->getFunction(
       Intrinsic::getName(Intrinsic::experimental_guard));
   HasGuards = GuardDecl && !GuardDecl->use_empty();
 }
 
 ScalarEvolution::ScalarEvolution(ScalarEvolution &&Arg)
     : F(Arg.F), HasGuards(Arg.HasGuards), TLI(Arg.TLI), AC(Arg.AC), DT(Arg.DT),
-      LI(Arg.LI), CouldNotCompute(std::move(Arg.CouldNotCompute)),
+      LI(Arg.LI), Generation(Arg.Generation),
+      CouldNotCompute(std::move(Arg.CouldNotCompute)),
       ValueExprMap(std::move(Arg.ValueExprMap)),
       PendingLoopPredicates(std::move(Arg.PendingLoopPredicates)),
       WalkingBEDominatingConds(false), ProvingSplitPredicate(false),
       BackedgeTakenCounts(std::move(Arg.BackedgeTakenCounts)),
       PredicatedBackedgeTakenCounts(
           std::move(Arg.PredicatedBackedgeTakenCounts)),
       ConstantEvolutionLoopExitValue(
           std::move(Arg.ConstantEvolutionLoopExitValue)),

lib/Transforms/Scalar/LoopRerollPass.cpp

struct DAGRootTracker {
             LoopControlIV(LoopCtrlIV) {}
 
       /// Stage 1: Find all the DAG roots for the induction variable.
       bool findRoots();
       /// Stage 2: Validate if the found roots are valid.
       bool validate(ReductionTracker &Reductions);
       /// Stage 3: Assuming validate() returned true, perform the
       /// replacement.
-      /// @param IterCount The maximum iteration count of L.
-      void replace(const SCEV *IterCount);
+      void replace();
 
     protected:
       typedef MapVector<Instruction*, BitVector> UsesTy;
 
       void findRootsRecursive(Instruction *IVU,
                               SmallInstructionSet SubsumedInsts);
       bool findRootsBase(Instruction *IVU, SmallInstructionSet SubsumedInsts);
       bool collectPossibleRoots(Instruction *Base,
protected:
       UsesTy::iterator nextInstr(int Val, UsesTy &In,
                                  const SmallInstructionSet &Exclude,
                                  UsesTy::iterator *StartI=nullptr);
       bool isBaseInst(Instruction *I);
       bool isRootInst(Instruction *I);
       bool instrDependsOn(Instruction *I,
                           UsesTy::iterator Start,
                           UsesTy::iterator End);
-      void replaceIV(Instruction *Inst, Instruction *IV, const SCEV *IterCount);
+      void replaceIV(Instruction *Inst, Instruction *IV);
       void updateNonLoopCtrlIncr();
 
       LoopReroll *Parent;
 
       // Members of Parent, replicated here for brevity.
       Loop *L;
       ScalarEvolution *SE;
       AliasAnalysis *AA;
bool isCompareUsedByBranch(Instruction *I) {
         return false;
       return I->hasOneUse() && TI->getOperand(0) == I;
     };
 
     bool isLoopControlIV(Loop *L, Instruction *IV);
     void collectPossibleIVs(Loop *L, SmallInstructionVector &PossibleIVs);
     void collectPossibleReductions(Loop *L,
            ReductionTracker &Reductions);
-    bool reroll(Instruction *IV, Loop *L, BasicBlock *Header, const SCEV *IterCount,
+    bool reroll(Instruction *IV, Loop *L, BasicBlock *Header,
                 ReductionTracker &Reductions);
   };
 }
 
 char LoopReroll::ID = 0;
 INITIALIZE_PASS_BEGIN(LoopReroll, "loop-reroll", "Reroll loops", false, false)
 INITIALIZE_PASS_DEPENDENCY(LoopPass)
 INITIALIZE_PASS_DEPENDENCY(TargetLibraryInfoWrapperPass)
bool LoopReroll::DAGRootTracker::validate(ReductionTracker &Reductions) {
   }
 
   DEBUG(dbgs() << "LRR: Matched all iteration increments for " <<
                   *IV << "\n");
 
   return true;
 }
 
-void LoopReroll::DAGRootTracker::replace(const SCEV *IterCount) {
+void LoopReroll::DAGRootTracker::replace() {
   BasicBlock *Header = L->getHeader();
   // Remove instructions associated with non-base iterations.
   for (BasicBlock::reverse_iterator J = Header->rbegin(), JE = Header->rend();
        J != JE;) {
     unsigned I = Uses[&*J].find_first();
     if (I > 0 && I < IL_All) {
       DEBUG(dbgs() << "LRR: removing: " << *J << "\n");
       J++->eraseFromParent();
       continue;
     }
 
     ++J;
   }
+  // Flush the cached information about this loop in SCEV as we've mutated it
+  // heavily.
+  SE->forgetLoop(L);
 
   bool HasTwoIVs = LoopControlIV && LoopControlIV != IV;
 
   if (HasTwoIVs) {
     updateNonLoopCtrlIncr();
-    replaceIV(LoopControlIV, LoopControlIV, IterCount);
+    replaceIV(LoopControlIV, LoopControlIV);
   } else
     // We need to create a new induction variable for each different BaseInst.
     for (auto &DRS : RootSets)
       // Insert the new induction variable.
-      replaceIV(DRS.BaseInst, IV, IterCount);
+      replaceIV(DRS.BaseInst, IV);
 
   SimplifyInstructionsInBlock(Header, TLI);
   DeleteDeadPHIs(Header, TLI);
 }
 
 // For non-loop-control IVs, we only need to update the last increment
 // with right amount, then we are done.
 void LoopReroll::DAGRootTracker::updateNonLoopCtrlIncr() {
for (auto *LoopInc : LoopIncs) {
     } else
       NewInc = SE->getUDivExpr(COp, ScaleSCEV);
 
     LoopInc->setOperand(1, dyn_cast<SCEVConstant>(NewInc)->getValue());
   }
 }
 
 void LoopReroll::DAGRootTracker::replaceIV(Instruction *Inst,
-                                           Instruction *InstIV,
-                                           const SCEV *IterCount) {
+                                           Instruction *InstIV) {
   BasicBlock *Header = L->getHeader();
   int64_t Inc = IVToIncMap[InstIV];
   bool NeedNewIV = InstIV == LoopControlIV;
   bool Negative = !NeedNewIV && Inc < 0;
 
   const SCEVAddRecExpr *RealIVSCEV = cast<SCEVAddRecExpr>(SE->getSCEV(Inst));
   const SCEV *Start = RealIVSCEV->getStart();
 
const SCEV *NewIVSCEV =
 
     for (auto &KV : Uses)
       if (KV.second.find_first() == 0)
         KV.first->replaceUsesOfWith(Inst, NewIV);
 
     if (BranchInst *BI = dyn_cast<BranchInst>(Header->getTerminator())) {
       // FIXME: Why do we need this check?
       if (Uses[BI].find_first() == IL_All) {
+        const SCEV *LIBETC = SE->getBackedgeTakenCount(L);
+        const SCEV *IterCount =
+            SE->getAddExpr(LIBETC, SE->getOne(LIBETC->getType()));
         const SCEV *ICSCEV = RealIVSCEV->evaluateAtIteration(IterCount, *SE);
 
         if (NeedNewIV)
           ICSCEV = SE->getMulExpr(IterCount,
                                   SE->getConstant(IterCount->getType(), Scale));
 
         // Iteration count SCEV minus or plus 1
         const SCEV *MinusPlus1SCEV =

 //     cannot reorder those side-effect-producing instructions, and rerolling
 //     fails.
 //
 // Finally, we make sure that all loop instructions are either loop increment
 // roots, belong to simple latch code, parts of validated reductions, part of
 // f(%iv) or part of some f(%iv.i). If all of that is true (and all reductions
 // have been validated), then we reroll the loop.
 bool LoopReroll::reroll(Instruction *IV, Loop *L, BasicBlock *Header,
-                        const SCEV *IterCount,
                         ReductionTracker &Reductions) {
   DAGRootTracker DAGRoots(this, L, IV, SE, AA, TLI, DT, LI, PreserveLCSSA,
                           IVToIncMap, LoopControlIV);
 
   if (!DAGRoots.findRoots())
     return false;
   DEBUG(dbgs() << "LRR: Found all root induction increments for: " <<
                   *IV << "\n");
 
   if (!DAGRoots.validate(Reductions))
     return false;
   if (!Reductions.validateSelected())
     return false;
   // At this point, we've validated the rerolling, and we're committed to
   // making changes!
 
   Reductions.replaceSelected();
-  DAGRoots.replace(IterCount);
+  DAGRoots.replace();
 
   ++NumRerolledLoops;
   return true;
 }
 
 bool LoopReroll::runOnLoop(Loop *L, LPPassManager &LPM) {
   if (skipLoop(L))
     return false;
bool LoopReroll::runOnLoop(Loop *L, LPPassManager &LPM) {
 
   // For now, we'll handle only single BB loops.
   if (L->getNumBlocks() > 1)
     return false;
 
   if (!SE->hasLoopInvariantBackedgeTakenCount(L))
     return false;
 
-  const SCEV *LIBETC = SE->getBackedgeTakenCount(L);
-  const SCEV *IterCount = SE->getAddExpr(LIBETC, SE->getOne(LIBETC->getType()));
   DEBUG(dbgs() << "\n Before Reroll:\n" << *(L->getHeader()) << "\n");
-  DEBUG(dbgs() << "LRR: iteration count = " << *IterCount << "\n");
+  DEBUG(dbgs() << "LRR: iteration count = "
+               << *SE->getAddExpr(
+                      SE->getBackedgeTakenCount(L),
+                      SE->getOne(SE->getBackedgeTakenCount(L)->getType()))
+               << "\n");
 
   // First, we need to find the induction variable with respect to which we can
   // reroll (there may be several possible options).
   SmallInstructionVector PossibleIVs;
   IVToIncMap.clear();
   LoopControlIV = nullptr;
   collectPossibleIVs(L, PossibleIVs);
 
   if (PossibleIVs.empty()) {
     DEBUG(dbgs() << "LRR: No possible IVs found\n");
     return false;
   }
 
   ReductionTracker Reductions;
   collectPossibleReductions(L, Reductions);
   bool Changed = false;
 
   // For each possible IV, collect the associated possible set of 'root' nodes
   // (i+1, i+2, etc.).
   for (Instruction *PossibleIV : PossibleIVs)
-    if (reroll(PossibleIV, L, Header, IterCount, Reductions)) {
+    if (reroll(PossibleIV, L, Header, Reductions)) {
       Changed = true;
       break;
     }
   DEBUG(dbgs() << "\n After Reroll:\n" << *(L->getHeader()) << "\n");
 
   // Trip count of L has changed so SE must be re-evaluated.
   if (Changed)
     SE->forgetLoop(L);
 
   return Changed;
 }