[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 ↗

(On Diff #381486)

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 ↗

(On Diff #381486)

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
private:
 
   /// 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;
 
+  /// Return false iff given SCEV is, or contains, a SCEV that has been erased
+  /// from ExprValueMap.
+  bool containsDanglingPointers(const SCEV *S) const;
+
   /// 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>
   bool proveNoWrapByVaryingStart(const SCEV *Start, const SCEV *Step,
                                  const Loop *L);

llvm/lib/Analysis/ScalarEvolution.cpp

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;
   });
 
   return !ContainsNulls;
 }
 
+bool ScalarEvolution::containsDanglingPointers(const SCEV *S) const {
+  return SCEVExprContains(
+      S, [this](const SCEV *S) { return !ExprValueMap.count(S); });
+}
+
 bool ScalarEvolution::containsAddRecurrence(const SCEV *S) {
   HasRecMapType::iterator I = HasRecMap.find(S);
   if (I != HasRecMap.end())
     return I->second;
 
   bool FoundAddRec =
       SCEVExprContains(S, [](const SCEV *S) { return isa<SCEVAddRecExpr>(S); });
   HasRecMap.insert({S, FoundAddRec});
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;
+    if (containsDanglingPointers(S))
+      // FIXME: Remove this when we wipe out dangling pointers from all maps.
+      continue;
+    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/LoopRotate/pr51981-scev-problem-verification.ll

+; RUN: opt < %s -passes='verify<scalar-evolution>,loop(loop-rotate),verify<scalar-evolution>' -disable-output 2>&1 | FileCheck %s
+; FIXME: BlockDisposition cache is in invalid state after this transform.
+;
+; Cached block disposition of SCEV %wide for basic block: loop.inner has changed!
+; Cached: Properly dominates block
+; Actual: Does not dominate block
+;
+; XFAIL: *
+; REQUIRES: asserts
+
+@offset = external dso_local global i32, align 1
+@array = internal global [11263 x i32] zeroinitializer, align 1
+
+define void @test_function(i1 %cond) {
+; CHECK-LABEL: test_function
+entry:
+  br label %loop.outer.header
+
+loop.outer.header:                                ; preds = %loop.outer.latch, %entry
+  %wide = load i32, i32* @offset, align 1
+  br i1 %cond, label %exit, label %loop.inner.ph
+
+loop.inner.ph:                                    ; preds = %loop.outer.header
+  %narrow = trunc i32 %wide to i16
+  br label %loop.inner
+
+loop.inner:                                       ; preds = %loop.inner, %loop.inner.ph
+  %iv = phi i16 [ %narrow, %loop.inner.ph ], [ %iv.plus, %loop.inner ]
+  %iv.promoted = zext i16 %iv to i32
+  %gep = getelementptr inbounds [11263 x i32], [11263 x i32]* @array, i32 0, i32 %iv.promoted
+  store i32 7, i32* %gep, align 1
+  %iv.plus = add i16 %iv, 1
+  %cmp = icmp ult i16 %iv.plus, 700
+  br i1 %cmp, label %loop.inner, label %loop.outer.latch
+
+loop.outer.latch:                                 ; preds = %loop.inner
+  br label %loop.outer.header
+
+exit:                                             ; preds = %loop.outer.header
+  ret void
+}