[SCEV] Verify contents of cached Block Dispositions

[mkazantsev]

Summary

We have some evidence that SCEV's cached BlockDispositions are sometimes
wrong (i.e. cached result is different from what computeBlockDisposition would
return), but not clear where and how exactly the cache had gone astray.

Currently SCEV blindly believes that its cache is valid and does not bother to check
it, so such problems may lurk between passes. This patch tries to fix this situation.

[fhahn]

Looks like a good thing to verify to me, thanks! I can't tell due to missing context in the diff, are the new checks enabled by default? If so, do you think this will cause any verification failures during bootstrapping that should be addressed first?

llvm/test/Transforms/LCSSA/pr44058.ll

6 ↗

(On Diff #374736)

Looks like all changed tests fail verification due to caching deleted values. Are there any cases where the disposition of a value changes?

[mkazantsev]

In D110385#3019934, @fhahn wrote:

Looks like a good thing to verify to me, thanks! I can't tell due to missing context in the diff, are the new checks enabled by default? If so, do you think this will cause any verification failures during bootstrapping that should be addressed first?

Yes, the checks are now on by default.

All these failures are fixed in D110390. I'm going to merge them together. Further on, if other failures are found, we should treat it as a bug.

[mkazantsev]

llvm/test/Transforms/LCSSA/pr44058.ll

6 ↗

(On Diff #374736)

All the failures are due to dangling pointers. We don't have an API to somehow invalidate this cache, and I'm surprised it doesn't break on every step. I've tried to fix things up in D110390.

[mkazantsev]

Updated revision w/ context.

[mkazantsev]

Updated.

• Now we ignore SCEVs that contain dangling pointers.
• Thanks @bjope for finding an example where it ACTUALLY cathes a problem, see D110813. Added this as unit test.
• Printing block name instead of entire block dump;
• Printing smart block dispositions as string instead of ints.

[mkazantsev]

Rebased. Now, when we wipe out obsolete data from caches, this is not failing. The only failure seems to be a real bug in LoopFusion.

[mkazantsev]

Needs rebase. Withdrawing from review for now.

[mkazantsev]

Rebased

[mkazantsev]

This one is now ready for review. Please feel free to take a look.

[mkazantsev]

Ping

[bjope]

llvm/test/Transforms/LoopFusion/triple_loop_nest_inner_guard.ll

6

I figure this is a fault that we now detect that should be tracked somehow. Should there be a reference to a bugzilla issue here?

[reames]

FYI, the issue fixed in D114738 could cause this check to fail. As such, this is blocked on that patch.

llvm/test/Transforms/LoopFusion/triple_loop_nest_inner_guard.ll

6

This to me looks to be a blocker. We must understand where this failure is coming from and fix it before landing the verification.

[reames]

Please refresh once XFAIL root caused and fixed.

[mkazantsev]

No plan to make further progress here.

llvm/include/llvm/Analysis/ScalarEvolution.h

public:
 
   /// 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);
+  /// 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.
   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);
private:
   /// Return true if this loop is finite by assumption.  That is,
   /// to be infinite, it must also be undefined.
   bool loopIsFiniteByAssumption(const Loop *L);
 
   /// Compute a LoopDisposition value.
   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> >
 
   /// 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 *, 8> > SCEVUsers;
 
   /// Memoized results from getRange
   DenseMap<const SCEV *, ConstantRange> UnsignedRanges;
 
   /// Memoized results from getRange

llvm/lib/Analysis/ScalarEvolution.cpp

static StringRef loopDispositionToStr(ScalarEvolution::LoopDisposition LD) {
   case ScalarEvolution::LoopInvariant:
     return "Invariant";
   case ScalarEvolution::LoopComputable:
     return "Computable";
   }
   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
   // this potentially causes it to create new SCEV objects though,
   // which technically conflicts with the const qualifier. This isn't
   // observable from outside the class though, so casting away the
   // const isn't dangerous.
   ScalarEvolution &SE = *const_cast<ScalarEvolution *>(this);
bool ScalarEvolution::isLoopInvariant(const SCEV *S, const Loop *L) {
   return getLoopDisposition(S, L) == LoopInvariant;
 }
 
 bool ScalarEvolution::hasComputableLoopEvolution(const SCEV *S, const Loop *L) {
   return getLoopDisposition(S, L) == LoopComputable;
 }
 
 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];
+  if (UseCache) {
     for (auto &V : Values) {
       if (V.getPointer() == BB)
         return V.getInt();
     }
     Values.emplace_back(BB, DoesNotDominateBlock);
-  BlockDisposition D = computeBlockDisposition(S, BB);
+  }
+  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;
   case scPtrToInt:
   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
     // produces the addrec's value is a PHI, and a PHI effectively properly
     // dominates its entire containing block.
     const SCEVAddRecExpr *AR = cast<SCEVAddRecExpr>(S);
     if (!DT.dominates(AR->getLoop()->getHeader(), BB))
       return DoesNotDominateBlock;
 
     // Fall through into SCEVNAryExpr handling.
     LLVM_FALLTHROUGH;
   }
   case scAddExpr:
   case scMulExpr:
   case scUMaxExpr:
   case scSMaxExpr:
   case scUMinExpr:
   case scSMinExpr: {
     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)
         Proper = false;
     }
     return Proper ? ProperlyDominatesBlock : DominatesBlock;
   }
   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) ?
       ProperlyDominatesBlock : DominatesBlock;
   }
   case scUnknown:
     if (Instruction *I =
           dyn_cast<Instruction>(cast<SCEVUnknown>(S)->getValue())) {
void ScalarEvolution::verify() const {
   // Check for SCEV expressions referencing invalid/deleted loops.
   for (auto &KV : ValueExprMap) {
     auto *AR = dyn_cast<SCEVAddRecExpr>(KV.second);
     if (!AR)
       continue;
     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(
     Function &F, const PreservedAnalyses &PA,
     FunctionAnalysisManager::Invalidator &Inv) {
   // Invalidate the ScalarEvolution object whenever it isn't preserved or one
   // of its dependencies is invalidated.
   auto PAC = PA.getChecker<ScalarEvolutionAnalysis>();

llvm/test/Transforms/LoopFusion/triple_loop_nest_inner_guard.ll

 ; RUN: opt -S -loop-fusion < %s 2>&1 | FileCheck %s
 
 ; 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
 
 ; CHECK-LABEL: @triple_loop_nest_inner_guard
 ; CHECK: br i1 %{{.*}}, label %[[OUTER_PH:outer1.ph]], label %[[FUNC_EXIT:func_exit]]
 
 ; CHECK: [[OUTER_PH]]: