[SCEV] Replace NumTripCountsComputed stat with NumExitCountsComputed

[dmakogon]

Summary

This fixes assertion crash in https://github.com/llvm/llvm-project/issues/62380.

In the beginning of ScalarEvolution::getBackedgeTakenInfo we make sure that BackedgeTakenCounts contains an entry for the given loop.
Then we call computeBackedgeTakenCount which computes the result, and in the end we insert it in the map like so:

return BackedgeTakenCounts.find(L)->second = std::move(Result);

So we expect that the entry for L still exists in the cache.
However, it can get deleted. When it has computed the result, getBackedgeTakenInfo clears all the cached SCEVs that use the AddRecs in the loop.
In the crashing example, getBackedgeTakenInfo first gets called on an inner loop, and during this call it gets called again on its parent loop
. This recursion happens after the call to computeBackedgeTakenCount. And it happens so that some SCEV from the BTI of the child loop uses an AddRec of the parent loop. So when we successfully compute BTI for the parent loop, we erase already computed result for the child one.

The recursion happens in some debug only code that updates statistics. The algorithm itself is non-recursive.
Namely the recursive call happens in BackedgeTakenInfo::getExact function and its return value is only used to compare it against SCEVCouldNotCompute.

As suggested by @nikic I replaced the NumTripCountsComputed and NumTripCountsNotComputed with NumExitCountsComputed and NumExitCountsNotComputed respectively. They are updated during computations made for single exits. It relieves us of the need to compute exact exit count for the loop just to update the named statistic and thus the recursion cannot happen anymore.

[dmakogon]

Remove leftover debug print

[mkazantsev]

llvm/lib/Analysis/ScalarEvolution.cpp

8419

Please land this refactoring separately.

8444

I wonder, if the key can now be erased, what protects us from infinite recursion?

[mkazantsev]

llvm/lib/Analysis/ScalarEvolution.cpp

8452–8453

If the recursion only exists in this debug code to count statistics, and not used in normal algorithm execution, why do we need it at all? I'd rather throw this away than add extra checks/updates just because a non-recursive algorithm becomes recursive because of stat computation.

[dmakogon]

Reworked the change as discussed offline with Max. The recursive call could happen in code that updates some stats. Namely in BackedgeTakenInfo::getExact. But the only usage of its result was to compare it against SCEVCouldNotCompute. So I added a new API to BackedgeTakenInfo which returns whether it can compute the exact exit count for loop and used it instead of its computation.

[nikic]

I think it might make more sense to replace NumTripCountsComputed with NumExitCountsComputed etc (actually NumBruteForceTripCountsComputed already has this meaning, the name is a lie). I think this is the more interesting quantity to look at in terms of how good our calculations are, because whether we can determine an exit count is something we can influence, while whether a BECount can be determined from those exit counts is largely just a question of loop structure.

[dmakogon]

As suggested by @nikic I replaced the NumTripCountsComputed and NumTripCountsNotComputed with NumExitCountsComputed and NumExitCountsNotComputed respectively. They are updated during computations made for single exits. It relieves us of the need to compute exact exit count for the loop just to update the named statistic and thus the recursion cannot happen anymore.

[nikic]

llvm/lib/Analysis/ScalarEvolution.cpp

8848

Should we count SymbolicMax or Exact as a "computed" exit count? The previous code was using the exact BECount.

[dmakogon]

Don't count symbolic exit counts in statistics

llvm/lib/Analysis/ScalarEvolution.cpp

8848

Yeah, we shouldn't. Fixed

[nikic]

LGTM

llvm/lib/Analysis/ScalarEvolution.cpp

 #include <utility>
 #include <vector>
 
 using namespace llvm;
 using namespace PatternMatch;
 
 #define DEBUG_TYPE "scalar-evolution"
 
-STATISTIC(NumTripCountsComputed,
-          "Number of loops with predictable loop counts");
-STATISTIC(NumTripCountsNotComputed,
-          "Number of loops without predictable loop counts");
+STATISTIC(NumExitCountsComputed,
+          "Number of loop exits with predictable exit counts");
+STATISTIC(NumExitCountsNotComputed,
+          "Number of loop exits without predictable exit counts");
 STATISTIC(NumBruteForceTripCountsComputed,
           "Number of loops with trip counts computed by force");
 
 #ifdef EXPENSIVE_CHECKS
 bool llvm::VerifySCEV = true;
 #else
 bool llvm::VerifySCEV = false;
 #endif
static void PushLoopPHIs(const Loop *L,
   BasicBlock *Header = L->getHeader();
 
   // Push all Loop-header PHIs onto the Worklist stack.
   for (PHINode &PN : Header->phis())
     if (Visited.insert(&PN).second)
       Worklist.push_back(&PN);
 }
 
 const ScalarEvolution::BackedgeTakenInfo &
 ScalarEvolution::getPredicatedBackedgeTakenInfo(const Loop *L) {
   auto &BTI = getBackedgeTakenInfo(L);
   if (BTI.hasFullInfo())
     return BTI;
 
   auto Pair = PredicatedBackedgeTakenCounts.insert({L, BackedgeTakenInfo()});
 
   if (!Pair.second)
     return Pair.first->second;
 
   BackedgeTakenInfo Result =
       computeBackedgeTakenCount(L, /*AllowPredicates=*/true);
 
   return PredicatedBackedgeTakenCounts.find(L)->second = std::move(Result);
 }
 
 ScalarEvolution::BackedgeTakenInfo &
 ScalarEvolution::getBackedgeTakenInfo(const Loop *L) {
   // Initially insert an invalid entry for this loop. If the insertion
   // succeeds, proceed to actually compute a backedge-taken count and
   // update the value. The temporary CouldNotCompute value tells SCEV
   // code elsewhere that it shouldn't attempt to request a new
   // backedge-taken count, which could result in infinite recursion.
   std::pair<DenseMap<const Loop *, BackedgeTakenInfo>::iterator, bool> Pair =
       BackedgeTakenCounts.insert({L, BackedgeTakenInfo()});
   if (!Pair.second)
     return Pair.first->second;
 
   // computeBackedgeTakenCount may allocate memory for its result. Inserting it
   // into the BackedgeTakenCounts map transfers ownership. Otherwise, the result
   // must be cleared in this scope.
   BackedgeTakenInfo Result = computeBackedgeTakenCount(L);
 
-  // In product build, there are no usage of statistic.
-  (void)NumTripCountsComputed;
-  (void)NumTripCountsNotComputed;
-#if LLVM_ENABLE_STATS || !defined(NDEBUG)
-  const SCEV *BEExact = Result.getExact(L, this);
-  if (BEExact != getCouldNotCompute()) {
-    assert(isLoopInvariant(BEExact, L) &&
-           isLoopInvariant(Result.getConstantMax(this), L) &&
-           "Computed backedge-taken count isn't loop invariant for loop!");
-    ++NumTripCountsComputed;
-  } else if (Result.getConstantMax(this) == getCouldNotCompute() &&
-             isa<PHINode>(L->getHeader()->begin())) {
-    // Only count loops that have phi nodes as not being computable.
-    ++NumTripCountsNotComputed;
-  }
-#endif // LLVM_ENABLE_STATS || !defined(NDEBUG)
-
   // Now that we know more about the trip count for this loop, forget any
   // existing SCEV values for PHI nodes in this loop since they are only
   // conservative estimates made without the benefit of trip count
   // information. This invalidation is not necessary for correctness, and is
   // only done to produce more precise results.
   if (Result.hasAnyInfo()) {
     // Invalidate any expression using an addrec in this loop.
     SmallVector<const SCEV *, 8> ToForget;
     auto LoopUsersIt = LoopUsers.find(L);
for (unsigned i = 0, e = ExitingBlocks.size(); i != e; ++i) {
 
     ExitLimit EL = computeExitLimit(L, ExitBB, AllowPredicates);
 
     assert((AllowPredicates || EL.Predicates.empty()) &&
            "Predicated exit limit when predicates are not allowed!");
 
     // 1. For each exit that can be computed, add an entry to ExitCounts.
     // CouldComputeBECount is true only if all exits can be computed.
-    if (EL.ExactNotTaken == getCouldNotCompute())
+    if (EL.ExactNotTaken != getCouldNotCompute())
+      ++NumExitCountsComputed;
+    else
       // We couldn't compute an exact value for this exit, so
       // we won't be able to compute an exact value for the loop.
       CouldComputeBECount = false;
     // Remember exit count if either exact or symbolic is known. Because
     // Exact always implies symbolic, only check symbolic.
     if (EL.SymbolicMaxNotTaken != getCouldNotCompute())
       ExitCounts.emplace_back(ExitBB, EL);
-    else
+    else {
       assert(EL.ExactNotTaken == getCouldNotCompute() &&
              "Exact is known but symbolic isn't?");
+      ++NumExitCountsNotComputed;
+    }
 
     // 2. Derive the loop's MaxBECount from each exit's max number of
     // non-exiting iterations. Partition the loop exits into two kinds:
     // LoopMustExits and LoopMayExits.
     //
     // If the exit dominates the loop latch, it is a LoopMustExit otherwise it
     // is a LoopMayExit.  If any computable LoopMustExit is found, then
     // MaxBECount is the minimum EL.ConstantMaxNotTaken of computable

llvm/test/Analysis/ScalarEvolution/pr62380.ll

+; NOTE: Assertions have been autogenerated by utils/update_test_checks.py UTC_ARGS: --version 2
 ; RUN: opt -passes='loop(loop-deletion),loop-mssa(loop-predication,licm<allowspeculation>,simple-loop-unswitch<nontrivial>),loop(loop-predication)' -S < %s | FileCheck %s
 
-; REQUIRES: asserts
-; XFAIL: *
-
 target datalayout = "e-m:e-p270:32:32-p271:32:32-p272:64:64-i64:64-f80:128-n8:16:32:64-S128-ni:1-p2:32:8:8:32-ni:2"
 target triple = "x86_64-unknown-linux-gnu"
 
 define void @test(i32 %arg) {
+; CHECK-LABEL: define void @test
+; CHECK-SAME: (i32 [[ARG:%.*]]) {
+; CHECK-NEXT:  bb:
+; CHECK-NEXT:    br label [[BB1:%.*]]
+; CHECK:       bb1:
+; CHECK-NEXT:    br label [[BB2:%.*]]
+; CHECK:       bb2:
+; CHECK-NEXT:    br i1 false, label [[BB3_PREHEADER:%.*]], label [[BB1]]
+; CHECK:       bb3.preheader:
+; CHECK-NEXT:    [[LOAD_LE:%.*]] = load i32, ptr null, align 4
+; CHECK-NEXT:    br label [[BB3:%.*]]
+; CHECK:       bb3.loopexit:
+; CHECK-NEXT:    br label [[BB3]]
+; CHECK:       bb3:
+; CHECK-NEXT:    [[PHI:%.*]] = phi i32 [ [[ADD:%.*]], [[BB3_LOOPEXIT:%.*]] ], [ 0, [[BB3_PREHEADER]] ]
+; CHECK-NEXT:    [[ADD]] = add i32 [[PHI]], 1
+; CHECK-NEXT:    [[ICMP:%.*]] = icmp ult i32 [[PHI]], [[LOAD_LE]]
+; CHECK-NEXT:    br i1 [[ICMP]], label [[BB5:%.*]], label [[BB4:%.*]]
+; CHECK:       bb4:
+; CHECK-NEXT:    ret void
+; CHECK:       bb5:
+; CHECK-NEXT:    [[CALL:%.*]] = call i1 @llvm.experimental.widenable.condition()
+; CHECK-NEXT:    br i1 [[CALL]], label [[BB9_PREHEADER:%.*]], label [[BB14:%.*]]
+; CHECK:       bb9.preheader:
+; CHECK-NEXT:    br label [[BB9:%.*]]
+; CHECK:       bb6:
+; CHECK-NEXT:    [[ADD7:%.*]] = add i32 [[PHI10:%.*]], 1
+; CHECK-NEXT:    [[ICMP8:%.*]] = icmp ugt i32 [[PHI10]], 1
+; CHECK-NEXT:    br i1 [[ICMP8]], label [[BB3_LOOPEXIT]], label [[BB9]]
+; CHECK:       bb9:
+; CHECK-NEXT:    [[PHI10]] = phi i32 [ [[ADD7]], [[BB6:%.*]] ], [ [[PHI]], [[BB9_PREHEADER]] ]
+; CHECK-NEXT:    [[ICMP11:%.*]] = icmp ult i32 [[PHI10]], [[ARG]]
+; CHECK-NEXT:    [[CALL12:%.*]] = call i1 @llvm.experimental.widenable.condition()
+; CHECK-NEXT:    [[AND:%.*]] = and i1 [[ICMP11]], true
+; CHECK-NEXT:    br i1 [[AND]], label [[BB6]], label [[BB13:%.*]]
+; CHECK:       bb13:
+; CHECK-NEXT:    ret void
+; CHECK:       bb14:
+; CHECK-NEXT:    ret void
+;
 bb:
   br label %bb1
 
 bb1:                                              ; preds = %bb2, %bb
   %load = load i32, ptr null, align 4
   br label %bb2
 
 bb2:                                              ; preds = %bb1