[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

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

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

10

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

10

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;
 
   /// Memoized results from getRange
   DenseMap<const SCEV *, ConstantRange> UnsignedRanges;
 
   /// Memoized results from getRange
   DenseMap<const SCEV *, ConstantRange> SignedRanges;
 
   /// Used to parameterize getRange

llvm/lib/Analysis/ScalarEvolution.cpp

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
+               << " has changed!\nCached: " << CachedDisposition
+               << "\nActual: " << 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/LCSSA/pr44058.ll

 ; RUN: opt -passes="verify<scalar-evolution>,lcssa,verify<scalar-evolution>" -verify-scev-strict -S %s
 
 ; The first SCEV verification is required because it queries SCEV and populates
 ; SCEV caches. Second SCEV verification checks if the caches are in valid state.
 
+; FIXME: breaks due to SCEV verification failure. Cached deleted values.
+; REQUIRES: asserts
+; XFAIL: *
+
 ; Check that the second SCEV verification doesn't fail.
 define void @foo(i32* %arg, i32* %arg1, i1 %arg2) {
 bb:
   br label %bb3
 
 bb3:                                              ; preds = %bb13, %bb
   %tmp = load i32, i32* %arg
   %tmp4 = load i32, i32* %arg1

llvm/test/Transforms/LCSSA/pr44320.ll

 ; RUN: opt -passes="verify<scalar-evolution>,lcssa,verify<scalar-evolution>" -verify-scev-strict -S -disable-output %s
 
 ; The first SCEV verification is required because it queries SCEV and populates
 ; SCEV caches. Second SCEV verification checks if the caches are in valid state.
 
+; FIXME: breaks due to SCEV verification failure. Cached deleted values.
+; REQUIRES: asserts
+; XFAIL: *
+
 ; Check that the second SCEV verification doesn't fail.
 define void @test(i32* %arg, i32* %arg1, i1 %arg2, i1 %arg3) {
 bb:
   br label %bb6
 
 bb5:
   br label %bb6
 

llvm/test/Transforms/LoopFusion/triple_loop_nest_inner_guard.ll

 ; RUN: opt -S -loop-fusion < %s 2>&1 | FileCheck %s
 
+; FIXME: breaks due to SCEV verification failure. Cached deleted values.
+; REQUIRES: asserts
+; XFAIL: *
+
 ; Verify that LoopFusion can fuse two triple-loop nests with guarded inner
 ; loops. Loops are in canonical form.
 
 @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]]:
 ; CHECK: br label %[[OUTER_BODY_MIDDLE_GUARD:outer1.body.middle1.guard]]