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.
Please land this refactoring separately.