[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

13980

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

13980

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

13980

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

13981

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/lib/Analysis/ScalarEvolution.cpp

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 (const auto &It : LoopDispositions) {
+    const SCEV *S = It.first;
+    auto &Values = It.second;
+    for (auto &V : Values) {
+      auto CachedDisposition = V.getInt();
+      const auto *Loop = V.getPointer();
+      const auto RecomputedDisposition = SE2.getLoopDisposition(S, Loop);
+      if (CachedDisposition != RecomputedDisposition) {
+        dbgs() << "Cached disposition of " << *S << " for loop " << *Loop
+               << " is incorrect: cached "
+               << loopDispositionToStr(CachedDisposition) << ", actual "
+               << loopDispositionToStr(RecomputedDisposition) << "\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