Index: llvm/include/llvm/Analysis/ScalarEvolution.h
===================================================================
--- llvm/include/llvm/Analysis/ScalarEvolution.h
+++ llvm/include/llvm/Analysis/ScalarEvolution.h
@@ -1101,8 +1101,12 @@
   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);
+  /// block. NOTE: If UseCache is true (default), this method is not truly
+  /// const. It's going to modify its internal (mutable) cache structure.
+  /// If UseCache is false, it is truly const, but is potentially *very*
+  /// expensive. This should only used for validation of cached values.
+  BlockDisposition getBlockDisposition(const SCEV *S, const BasicBlock *BB,
+                                       bool UseCache = true) const;
 
   /// Return true if elements that makes up the given SCEV dominate the
   /// specified basic block.
@@ -1493,13 +1497,14 @@
   LoopDisposition computeLoopDisposition(const SCEV *S, const Loop *L);
 
   /// Memoized computeBlockDisposition results.
-  DenseMap<
+  mutable DenseMap<
       const SCEV *,
-      SmallVector<PointerIntPair<const BasicBlock *, 2, BlockDisposition>, 2>>
-      BlockDispositions;
+      SmallVector<PointerIntPair<const BasicBlock *, 2, BlockDisposition>, 2> >
+  BlockDispositions;
 
   /// Compute a BlockDisposition value.
-  BlockDisposition computeBlockDisposition(const SCEV *S, const BasicBlock *BB);
+  BlockDisposition computeBlockDisposition(const SCEV *S, const BasicBlock *BB,
+                                           bool UseCache = true) const;
 
   /// Stores all SCEV that use a given SCEV as its direct operand.
   DenseMap<const SCEV *, SmallPtrSet<const SCEV *, 16> > SCEVUsers;
Index: llvm/lib/Analysis/ScalarEvolution.cpp
===================================================================
--- llvm/lib/Analysis/ScalarEvolution.cpp
+++ llvm/lib/Analysis/ScalarEvolution.cpp
@@ -12510,6 +12510,18 @@
   llvm_unreachable("Unknown ScalarEvolution::LoopDisposition kind!");
 }
 
+static StringRef blockDispositionToStr(ScalarEvolution::BlockDisposition BD) {
+  switch (BD) {
+  case ScalarEvolution::DoesNotDominateBlock:
+    return "Does not dominate block";
+  case ScalarEvolution::DominatesBlock:
+    return "Dominates block";
+  case ScalarEvolution::ProperlyDominatesBlock:
+    return "Properly dominates block";
+  }
+  llvm_unreachable("Unknown ScalarEvolution::BlockDisposition kind!");
+}
+
 void ScalarEvolution::print(raw_ostream &OS) const {
   // ScalarEvolution's implementation of the print method is to print
   // out SCEV values of all instructions that are interesting. Doing
@@ -12709,26 +12721,32 @@
 }
 
 ScalarEvolution::BlockDisposition
-ScalarEvolution::getBlockDisposition(const SCEV *S, const BasicBlock *BB) {
+ScalarEvolution::getBlockDisposition(const SCEV *S, const BasicBlock *BB,
+                                     bool UseCache) const {
   auto &Values = BlockDispositions[S];
-  for (auto &V : Values) {
-    if (V.getPointer() == BB)
-      return V.getInt();
-  }
-  Values.emplace_back(BB, DoesNotDominateBlock);
-  BlockDisposition D = computeBlockDisposition(S, BB);
-  auto &Values2 = BlockDispositions[S];
-  for (auto &V : make_range(Values2.rbegin(), Values2.rend())) {
-    if (V.getPointer() == BB) {
-      V.setInt(D);
-      break;
+  if (UseCache) {
+    for (auto &V : Values) {
+      if (V.getPointer() == BB)
+        return V.getInt();
+    }
+    Values.emplace_back(BB, DoesNotDominateBlock);
+  }
+  BlockDisposition D = computeBlockDisposition(S, BB, UseCache);
+  if (UseCache) {
+    auto &Values2 = BlockDispositions[S];
+    for (auto &V : make_range(Values2.rbegin(), Values2.rend())) {
+      if (V.getPointer() == BB) {
+        V.setInt(D);
+        break;
+      }
     }
   }
   return D;
 }
 
 ScalarEvolution::BlockDisposition
-ScalarEvolution::computeBlockDisposition(const SCEV *S, const BasicBlock *BB) {
+ScalarEvolution::computeBlockDisposition(const SCEV *S, const BasicBlock *BB,
+                                         bool UseCache) const {
   switch (S->getSCEVType()) {
   case scConstant:
     return ProperlyDominatesBlock;
@@ -12736,7 +12754,8 @@
   case scTruncate:
   case scZeroExtend:
   case scSignExtend:
-    return getBlockDisposition(cast<SCEVCastExpr>(S)->getOperand(), BB);
+    return getBlockDisposition(cast<SCEVCastExpr>(S)->getOperand(), BB,
+                               UseCache);
   case scAddRecExpr: {
     // This uses a "dominates" query instead of "properly dominates" query
     // to test for proper dominance too, because the instruction which
@@ -12758,7 +12777,7 @@
     const SCEVNAryExpr *NAry = cast<SCEVNAryExpr>(S);
     bool Proper = true;
     for (const SCEV *NAryOp : NAry->operands()) {
-      BlockDisposition D = getBlockDisposition(NAryOp, BB);
+      BlockDisposition D = getBlockDisposition(NAryOp, BB, UseCache);
       if (D == DoesNotDominateBlock)
         return DoesNotDominateBlock;
       if (D == DominatesBlock)
@@ -12769,10 +12788,10 @@
   case scUDivExpr: {
     const SCEVUDivExpr *UDiv = cast<SCEVUDivExpr>(S);
     const SCEV *LHS = UDiv->getLHS(), *RHS = UDiv->getRHS();
-    BlockDisposition LD = getBlockDisposition(LHS, BB);
+    BlockDisposition LD = getBlockDisposition(LHS, BB, UseCache);
     if (LD == DoesNotDominateBlock)
       return DoesNotDominateBlock;
-    BlockDisposition RD = getBlockDisposition(RHS, BB);
+    BlockDisposition RD = getBlockDisposition(RHS, BB, UseCache);
     if (RD == DoesNotDominateBlock)
       return DoesNotDominateBlock;
     return (LD == ProperlyDominatesBlock && RD == ProperlyDominatesBlock) ?
@@ -12974,6 +12993,26 @@
     assert(ValidLoops.contains(AR->getLoop()) &&
            "AddRec references invalid loop");
   }
+
+  // Verify cached block dispositions.
+  for (auto &It : BlockDispositions) {
+    const SCEV *S = It.first;
+    auto &Values = It.second;
+    for (auto &V : Values) {
+      auto *BB = V.getPointer();
+      auto CachedDisposition = V.getInt();
+      auto ActualDisposition = getBlockDisposition(S, BB, /*UseCache*/ false);
+      if (CachedDisposition != ActualDisposition) {
+        dbgs() << "Cached block disposition of SCEV " << *S
+               << " for basic block: " << BB->getName()
+               << " has changed!\nCached: "
+               << blockDispositionToStr(CachedDisposition)
+               << "\nActual: " << blockDispositionToStr(ActualDisposition)
+               << "\n";
+        std::abort();
+      }
+    }
+  }
 }
 
 bool ScalarEvolution::invalidate(
Index: llvm/test/Transforms/LoopFusion/triple_loop_nest_inner_guard.ll
===================================================================
--- llvm/test/Transforms/LoopFusion/triple_loop_nest_inner_guard.ll
+++ llvm/test/Transforms/LoopFusion/triple_loop_nest_inner_guard.ll
@@ -3,6 +3,10 @@
 ; Verify that LoopFusion can fuse two triple-loop nests with guarded inner
 ; loops. Loops are in canonical form.
 
+; Assertion `!isInvalid() && "Loop not in a valid state!"' failed during verification.
+; XFAIL: *
+; REQUIRES: asserts
+
 @a = common global [10 x [10 x [10 x i32]]] zeroinitializer
 @b = common global [10 x [10 x [10 x i32]]] zeroinitializer
 @c = common global [10 x [10 x [10 x i32]]] zeroinitializer