[SCEV] Verify contents of loop disposition cache

[mkazantsev]

Summary

It seems that it is sometimes broken. Initial motivation for this was
investigation of https://github.com/llvm/llvm-project/issues/56260, but
it also seems that we have found an unrelated bug in LoopFusion that leaves
broken caches.

[nikic]

llvm/lib/Analysis/ScalarEvolution.cpp

13991

Why does this not use the usual approach of comparing with the loop disposition on the other ScalarEvolution instance (SE2)?

[mkazantsev]

llvm/lib/Analysis/ScalarEvolution.cpp

13991

I was hesitant about this because SE2 might also have wrong cache state (for same reasons). On other hand we might invalidate it all the time... Let's see if it works.

[mkazantsev]

llvm/lib/Analysis/ScalarEvolution.cpp

13991

Ok, if we believe that only transform passes may break this, then it's fine.

[mkazantsev]

Changed to SE2 comparison as Nikita has suggested.

[nikic]

LGTM

llvm/lib/Analysis/ScalarEvolution.cpp

13992

disposition

[mkazantsev]

Fix for the found bug:https://reviews.llvm.org/D134173

[fhahn]

Thanks for extending the verifier, LGTM!

[RKSimon]

@mkazantsev Please can you take a look at the build failures on EXPENSIVE_CHECKS builds? https://lab.llvm.org/buildbot/#/builders/104/builds/9004

[nikic]

@RKSimon Should be fixed by https://github.com/llvm/llvm-project/commit/36f325413ec27819f8e4c1cd22d5f5e8a6a43000. Or maybe not fixed, but worked around :)

llvm/include/llvm/Analysis/ScalarEvolution.h

public:
   /// ICMP_EQ or ICMP_NE. ControllingFiniteLoop is set if this comparison
   /// controls the exit of a loop known to have a finite number of iterations.
   bool SimplifyICmpOperands(ICmpInst::Predicate &Pred, const SCEV *&LHS,
                             const SCEV *&RHS, unsigned Depth = 0,
                             bool ControllingFiniteLoop = false);
 
   /// Return the "disposition" of the given SCEV with respect to the given
   /// loop.
-  LoopDisposition getLoopDisposition(const SCEV *S, const Loop *L) const;
+  LoopDisposition getLoopDisposition(const SCEV *S, const Loop *L,
+                                     bool UseCache = true) const;
 
   /// Return true if the value of the given SCEV is unchanging in the
   /// specified loop.
-  bool isLoopInvariant(const SCEV *S, const Loop *L) const;
+  bool isLoopInvariant(const SCEV *S, const Loop *L,
+                       bool UseCache = true) const;
 
   /// Determine if the SCEV can be evaluated at loop's entry. It is true if it
   /// doesn't depend on a SCEVUnknown of an instruction which is dominated by
   /// the header of loop L.
   bool isAvailableAtLoopEntry(const SCEV *S, const Loop *L);
 
   /// 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
private:
   /// Return a \c LoopProperties instance for \p L, creating one if necessary.
   LoopProperties getLoopProperties(const Loop *L);
 
   bool loopHasNoSideEffects(const Loop *L) {
     return getLoopProperties(L).HasNoSideEffects;
   }
 
   /// Compute a LoopDisposition value.
-  LoopDisposition computeLoopDisposition(const SCEV *S, const Loop *L) const;
+  LoopDisposition computeLoopDisposition(const SCEV *S, const Loop *L,
+                                         bool UseCache) const;
 
   /// Memoized computeBlockDisposition results.
   DenseMap<
       const SCEV *,
       SmallVector<PointerIntPair<const BasicBlock *, 2, BlockDisposition>, 2>>
       BlockDispositions;
 
   /// Compute a BlockDisposition value.

llvm/lib/Analysis/ScalarEvolution.cpp

void ScalarEvolution::print(raw_ostream &OS) const {
   OS << "Determining loop execution counts for: ";
   F.printAsOperand(OS, /*PrintType=*/false);
   OS << "\n";
   for (Loop *I : LI)
     PrintLoopInfo(OS, &SE, I);
 }
 
 ScalarEvolution::LoopDisposition
-ScalarEvolution::getLoopDisposition(const SCEV *S, const Loop *L) const {
+ScalarEvolution::getLoopDisposition(const SCEV *S, const Loop *L,
+                                    bool UseCache) const {
+  if (UseCache) {
     auto &Values = LoopDispositions[S];
     for (auto &V : Values) {
       if (V.getPointer() == L)
         return V.getInt();
     }
     Values.emplace_back(L, LoopVariant);
-  LoopDisposition D = computeLoopDisposition(S, L);
+  }
+  LoopDisposition D = computeLoopDisposition(S, L, UseCache);
+  if (UseCache) {
     auto &Values2 = LoopDispositions[S];
     for (auto &V : llvm::reverse(Values2)) {
       if (V.getPointer() == L) {
         V.setInt(D);
         break;
       }
     }
+  }
   return D;
 }
 
 ScalarEvolution::LoopDisposition
-ScalarEvolution::computeLoopDisposition(const SCEV *S, const Loop *L) const {
+ScalarEvolution::computeLoopDisposition(const SCEV *S, const Loop *L,
+                                        bool UseCache) const {
   switch (S->getSCEVType()) {
   case scConstant:
     return LoopInvariant;
   case scPtrToInt:
   case scTruncate:
   case scZeroExtend:
   case scSignExtend:
-    return getLoopDisposition(cast<SCEVCastExpr>(S)->getOperand(), L);
+    return getLoopDisposition(cast<SCEVCastExpr>(S)->getOperand(), L, UseCache);
   case scAddRecExpr: {
     const SCEVAddRecExpr *AR = cast<SCEVAddRecExpr>(S);
 
     // If L is the addrec's loop, it's computable.
     if (AR->getLoop() == L)
       return LoopComputable;
 
     // Add recurrences are never invariant in the function-body (null loop).
     if (!L)
       return LoopVariant;
 
     // Everything that is not defined at loop entry is variant.
     if (DT.dominates(L->getHeader(), AR->getLoop()->getHeader()))
       return LoopVariant;
     assert(!L->contains(AR->getLoop()) && "Containing loop's header does not"
            " dominate the contained loop's header?");
 
     // This recurrence is invariant w.r.t. L if AR's loop contains L.
     if (AR->getLoop()->contains(L))
       return LoopInvariant;
 
     // This recurrence is variant w.r.t. L if any of its operands
     // are variant.
     for (const auto *Op : AR->operands())
-      if (!isLoopInvariant(Op, L))
+      if (!isLoopInvariant(Op, L, UseCache))
         return LoopVariant;
 
     // Otherwise it's loop-invariant.
     return LoopInvariant;
   }
   case scAddExpr:
   case scMulExpr:
   case scUMaxExpr:
   case scSMaxExpr:
   case scUMinExpr:
   case scSMinExpr:
   case scSequentialUMinExpr: {
     bool HasVarying = false;
     for (const auto *Op : cast<SCEVNAryExpr>(S)->operands()) {
-      LoopDisposition D = getLoopDisposition(Op, L);
+      LoopDisposition D = getLoopDisposition(Op, L, UseCache);
       if (D == LoopVariant)
         return LoopVariant;
       if (D == LoopComputable)
         HasVarying = true;
     }
     return HasVarying ? LoopComputable : LoopInvariant;
   }
   case scUDivExpr: {
     const SCEVUDivExpr *UDiv = cast<SCEVUDivExpr>(S);
-    LoopDisposition LD = getLoopDisposition(UDiv->getLHS(), L);
+    LoopDisposition LD = getLoopDisposition(UDiv->getLHS(), L, UseCache);
     if (LD == LoopVariant)
       return LoopVariant;
-    LoopDisposition RD = getLoopDisposition(UDiv->getRHS(), L);
+    LoopDisposition RD = getLoopDisposition(UDiv->getRHS(), L, UseCache);
     if (RD == LoopVariant)
       return LoopVariant;
     return (LD == LoopInvariant && RD == LoopInvariant) ?
            LoopInvariant : LoopComputable;
   }
   case scUnknown:
     // All non-instruction values are loop invariant.  All instructions are loop
     // invariant if they are not contained in the specified loop.
     // Instructions are never considered invariant in the function body
     // (null loop) because they are defined within the "loop".
     if (auto *I = dyn_cast<Instruction>(cast<SCEVUnknown>(S)->getValue()))
       return (L && !L->contains(I)) ? LoopInvariant : LoopVariant;
     return LoopInvariant;
   case scCouldNotCompute:
     llvm_unreachable("Attempt to use a SCEVCouldNotCompute object!");
   }
   llvm_unreachable("Unknown SCEV kind!");
 }
 
-bool ScalarEvolution::isLoopInvariant(const SCEV *S, const Loop *L) const {
-  return getLoopDisposition(S, L) == LoopInvariant;
+bool ScalarEvolution::isLoopInvariant(const SCEV *S, const Loop *L,
+                                      bool UseCache) const {
+  return getLoopDisposition(S, L, UseCache) == LoopInvariant;
 }
 
 bool ScalarEvolution::hasComputableLoopEvolution(const SCEV *S,
                                                  const Loop *L) const {
   return getLoopDisposition(S, L) == LoopComputable;
 }
 
 ScalarEvolution::BlockDisposition
for (const auto &LoopAndBEInfo : BECounts) {
                  << *LoopAndBEInfo.first << " missing from BECountUsers\n";
           std::abort();
         }
       }
     }
   };
   VerifyBECountUsers(/* Predicated */ false);
   VerifyBECountUsers(/* Predicated */ true);
+
+  // Verify intergity of loop disposition cache.
+  for (auto &It : LoopDispositions) {
+    const SCEV *S = It.first;
+    auto &Values = It.second;
+    for (auto &V : Values) {
+      auto CachedDisposition = V.getInt();
+      auto *Loop = V.getPointer();
+      auto RecomputedLoopDisposition =
+          getLoopDisposition(S, Loop, /*UseCache*/ false);
+      if (CachedDisposition != RecomputedLoopDisposition) {
+        dbgs() << "Cached dispoisition of " << *S << " for loop " << *Loop
+               << " is incorrect: cached "
+               << loopDispositionToStr(CachedDisposition) << ", actual "
+               << loopDispositionToStr(RecomputedLoopDisposition) << "\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/double_loop_nest_inner_guard.ll

 ; RUN: opt -S -loop-fusion < %s 2>&1 | FileCheck %s
+; XFAIL: *
+; REQUIRES: asserts
+; Fails due to incorrect cached loop disposition.
 
 ; Verify that LoopFusion can fuse two double-loop nests with guarded inner
 ; loops. Loops are in canonical form.
 
 @a = common global [10 x [10 x i32]] zeroinitializer
 @b = common global [10 x [10 x i32]] zeroinitializer
 @c = common global [10 x [10 x i32]] zeroinitializer
 

llvm/test/Transforms/LoopFusion/loop_nest.ll

 ; RUN: opt -S -loop-fusion < %s | FileCheck %s
+; XFAIL: *
+; REQUIRES: asserts
+; Fails due to incorrect cached loop disposition.
 ;
 ;    int A[1024][1024];
 ;    int B[1024][1024];
 ;
 ;    #define EXPENSIVE_PURE_COMPUTATION(i) ((i - 3) * (i + 3) % i)
 ;
 ;    void dep_free() {
 ;

llvm/test/Transforms/LoopFusion/triple_loop_nest_inner_guard.ll

 ; RUN: opt -S -loop-fusion < %s 2>&1 | FileCheck %s
+; XFAIL: *
+; REQUIRES: asserts
+; Fails due to incorrect cached loop disposition.
 
 ; 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