[SCEV] Replace NumTripCountsComputed stat with NumExitCountsComputed

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.

Differential Revision: https://reviews.llvm.org/D149251

1 files changed, 10 insertions, 23 deletions

diff --git a/llvm/lib/Analysis/ScalarEvolution.cpp b/llvm/lib/Analysis/ScalarEvolution.cpp
index aec1e34..2ad7870 100644
--- a/llvm/lib/Analysis/ScalarEvolution.cpp
+++ b/llvm/lib/Analysis/ScalarEvolution.cpp
@@ -135,10 +135,10 @@ 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");
 
@@ -8450,23 +8450,6 @@ ScalarEvolution::getBackedgeTakenInfo(const Loop *L) {
   // 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
@@ -8852,7 +8835,9 @@ ScalarEvolution::computeBackedgeTakenCount(const Loop *L,
 
     // 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;
@@ -8860,9 +8845,11 @@ ScalarEvolution::computeBackedgeTakenCount(const Loop *L,
     // 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: