[SCEV] Enable verification in LoopPM

[nikic]

Summary

Currently, we hardly ever actually run SCEV verification, even in tests with -verify-scev. This is because the NewPM LPM does not verify SCEV. The reason for this is that SCEV verification can actually change the result of subsequent SCEV queries, which means that you see different transformations depending on whether verification is enabled or not.

To allow verification in the LPM, this limits verification to BECounts that have actually been cached. It will not calculate new BECounts.

BackedgeTakenInfo::getExact() is still not entirely readonly, it still calls getUMinFromMismatchedTypes(). But I hope that this is not problematic in the same way. (This could be avoided by performing the umin in the other SCEV instance, but this would require duplicating some of the code.)

[nikic]

The pr35406.ll failure can be reduced to this:

define i32 @test() {
entry:
  br label %loop1

loop1:
  br i1 false, label %loop2, label %loop1.latch

loop2:
  %iv = phi i32 [ 0, %loop1 ], [ %iv.next, %loop2 ]
  %iv.next = add nuw nsw i32 %iv, 1
  %cmp = icmp ne i32 %iv.next, 1
  br i1 %cmp, label %loop1.latch, label %loop2

loop1.latch:
  br label %loop1
}

; opt -indvars

define i32 @test() {
entry:
  br label %loop1

loop1:                                            ; preds = %loop1.latch, %entry
  br i1 true, label %loop2.preheader, label %loop1.latch

loop2.preheader:                                  ; preds = %loop1
  br label %loop2

loop2:                                            ; preds = %loop2.preheader, %loop2
  br i1 true, label %loop1.latch.loopexit, label %loop2

loop1.latch.loopexit:                             ; preds = %loop2
  br label %loop1.latch

loop1.latch:                                      ; preds = %loop1.latch.loopexit, %loop1
  br label %loop1
}

In this case the BECount of the inner loop legitimately changes from 1 to 0, and this isn't wrong, because the loop is unreachable.

We make use of the fact that the loop is unreachable due to https://github.com/llvm/llvm-project/blob/20a093e2bc310283ec216ab47fddb68f0bdaa6f0/llvm/lib/Analysis/ScalarEvolution.cpp#L11024-L11027, introduced in D98706. And apparently this is already a known issue, with a variant reported in: https://github.com/llvm/llvm-project/issues/50523

I'm not really sure what to do about that. I think the options are a) give up on BECount verification entirely, b) drop that isImpliedCond() change, as I think it is of very limited practical value (the next SimplifyCFG will eliminate that code entirely, so it is irrelevant how we optimize it) or c) try to limit BECount verification to loops that are reachable, while taking into account constant branches.

[mkazantsev]

Why can't we just give up verification of unreachable loops/blocks?

[nikic]

Rebase

[reames]

LGTM

(I'm assuming that the unreachable loop issue was resolved. I think I remember seeing that change land at least.)

llvm/include/llvm/Analysis/ScalarEvolution.h

 class SCEVAddRecExpr;
 class SCEVUnknown;
 class StructType;
 class TargetLibraryInfo;
 class Type;
 class Value;
 enum SCEVTypes : unsigned short;
 
+extern bool VerifySCEV;
+
 /// This class represents an analyzed expression in the program.  These are
 /// opaque objects that the client is not allowed to do much with directly.
 ///
 class SCEV : public FoldingSetNode {
   friend struct FoldingSetTrait<SCEV>;
 
   /// A reference to an Interned FoldingSetNodeID for this node.  The
   /// ScalarEvolution's BumpPtrAllocator holds the data.

llvm/lib/Analysis/ScalarEvolution.cpp

 
 STATISTIC(NumTripCountsComputed,
           "Number of loops with predictable loop counts");
 STATISTIC(NumTripCountsNotComputed,
           "Number of loops without predictable loop counts");
 STATISTIC(NumBruteForceTripCountsComputed,
           "Number of loops with trip counts computed by force");
 
+// FIXME: Enable this with EXPENSIVE_CHECKS when the test suite is clean.
+bool llvm::VerifySCEV = false;
+
 static cl::opt<unsigned>
 MaxBruteForceIterations("scalar-evolution-max-iterations", cl::ReallyHidden,
                         cl::ZeroOrMore,
                         cl::desc("Maximum number of iterations SCEV will "
                                  "symbolically execute a constant "
                                  "derived loop"),
                         cl::init(100));
 
-// FIXME: Enable this with EXPENSIVE_CHECKS when the test suite is clean.
-static cl::opt<bool> VerifySCEV(
-    "verify-scev", cl::Hidden,
+static cl::opt<bool, true> VerifySCEVOpt(
+    "verify-scev", cl::Hidden, cl::location(VerifySCEV),
     cl::desc("Verify ScalarEvolution's backedge taken counts (slow)"));
 static cl::opt<bool> VerifySCEVStrict(
     "verify-scev-strict", cl::Hidden,
     cl::desc("Enable stricter verification with -verify-scev is passed"));
 static cl::opt<bool>
     VerifySCEVMap("verify-scev-maps", cl::Hidden,
                   cl::desc("Verify no dangling value in ScalarEvolution's "
                            "ExprValueMap (slow)"));
while (!LoopStack.empty()) {
     auto *L = LoopStack.pop_back_val();
     llvm::append_range(LoopStack, *L);
 
     // Only verify BECounts in reachable loops. For an unreachable loop,
     // any BECount is legal.
     if (!ReachableBlocks.contains(L->getHeader()))
       continue;
 
-    auto *CurBECount = SCM.visit(
-        const_cast<ScalarEvolution *>(this)->getBackedgeTakenCount(L));
+    // Only verify cached BECounts. Computing new BECounts may change the
+    // results of subsequent SCEV uses.
+    auto It = BackedgeTakenCounts.find(L);
+    if (It == BackedgeTakenCounts.end())
+      continue;
+
+    auto *CurBECount =
+        SCM.visit(It->second.getExact(L, const_cast<ScalarEvolution *>(this)));
     auto *NewBECount = SE2.getBackedgeTakenCount(L);
 
     if (CurBECount == SE2.getCouldNotCompute() ||
         NewBECount == SE2.getCouldNotCompute()) {
       // NB! This situation is legal, but is very suspicious -- whatever pass
       // change the loop to make a trip count go from could not compute to
       // computable or vice-versa *should have* invalidated SCEV.  However, we
       // choose not to assert here (for now) since we don't want false

llvm/lib/Transforms/Scalar/LoopPassManager.cpp

else
       PI.runAfterPass<Loop>(*Pass, *L, PassPA);
 
     if (LAR.MSSA && !PassPA.getChecker<MemorySSAAnalysis>().preserved())
       report_fatal_error("Loop pass manager using MemorySSA contains a pass "
                          "that does not preserve MemorySSA");
 
 #ifndef NDEBUG
     // LoopAnalysisResults should always be valid.
-    // Note that we don't LAR.SE.verify() because that can change observed SE
-    // queries. See PR44815.
     if (VerifyDomInfo)
       LAR.DT.verify();
     if (VerifyLoopInfo)
       LAR.LI.verify(LAR.DT);
+    if (VerifySCEV)
+      LAR.SE.verify();
     if (LAR.MSSA && VerifyMemorySSA)
       LAR.MSSA->verifyMemorySSA();
 #endif
 
     // If the loop hasn't been deleted, we need to handle invalidation here.
     if (!Updater.skipCurrentLoop())
       // We know that the loop pass couldn't have invalidated any other
       // loop's analyses (that's the contract of a loop pass), so directly

llvm/test/Transforms/IndVarSimplify/X86/deterministic-scev-verify.ll

-; RUN: opt -indvars -stats -disable-output < %s 2>&1 | FileCheck %s --check-prefix=STATS
-; RUN: opt -indvars -S < %s | FileCheck %s --check-prefix=IR
-; REQUIRES: asserts
+; RUN: opt -indvars -S < %s | FileCheck %s
 
 ; Check that IndVarSimplify's result is not influenced by stray calls to
 ; ScalarEvolution in debug builds. However, -verify-indvars may still do
 ; such calls.
 ; llvm.org/PR44815
 
-; STATS: 1 scalar-evolution - Number of loops with trip counts computed by force
-; STATS: 2 scalar-evolution - Number of loops with predictable loop counts
-
 ; In this test, adding -verify-indvars causes %tmp13 to not be optimized away.
-; IR-LABEL: @foo
-; IR-NOT:   phi i32
+; CHECK-LABEL: @foo
+; CHECK-NOT:   phi i32
 
 target triple = "x86_64-unknown-linux-gnu"
 
 @b = external dso_local local_unnamed_addr global i32
 
 define dso_local void @foo() {
 tmp0:
   br label %tmp12

llvm/test/Transforms/IndVarSimplify/X86/pr35406.ll

 ; NOTE: Assertions have been autogenerated by utils/update_test_checks.py
-; RUN: opt -S -passes='loop(indvars),verify<scalar-evolution>' %s | FileCheck %s
+; RUN: opt -S -indvars -verify-scev %s | FileCheck %s
 target datalayout = "e-m:e-i64:64-f80:128-n8:16:32:64-S128-ni:1"
 target triple = "x86_64-unknown-linux-gnu"
 
 define i32 @testDiv(i8* %p, i64* %p1) {
 ; CHECK-LABEL: @testDiv(
 ; CHECK-NEXT:  entry:
 ; CHECK-NEXT:    br label [[LOOP1:%.*]]
 ; CHECK:       loop1: