[SCEV] Verify that all mapped SCEV AddRecs refer to valid loops.

[fhahn]

Summary

This check helps to guard against cases where expressions referring to
invalidated/deleted loops are not properly invalidated.

The additional check is motivated by the reproducer shared for 8fdac7cb7abb
and I think in general make sense as a sanity check.

It would probably be even better to iterate over all unique SCEVs, but
that currently causes a few assertion in loop fusion, which I still need
to investigate.

IIUC expressions should be deleted from UniqueSCEVs as soon
as the last value handle to an expression is removed from
ValueExprMap.

[fhahn]

It would probably be even better to iterate over all unique SCEVs, but
that currently causes a few assertion in loop fusion, which I still need
to investigate.

I took a look at the assertion failures in loop fusion when iterating over all UniqueSCEVs. Loop fusion uses a SCEV rewriter to map SCEVs from one loop to another to check distances between expressions, but they are not used subsequently. This results in some expressions in UniqueSCEVs that reference the old loop, but are not referenced by any expression. I think that shouldn't be a big problem, especially as we currently do not have a convenient way to remove entries from UniqueSCEVs.

[reames]

A cleaner way to handle this check would be to enumerate all loops in LoopInfo, and then check that the loop of every AR is in that set. I the loop has already been deleted, dereferencing it to check the valid flags seems a bit suspect.

Actually, why not just implement the isInvalid check on Loop that way?

[fhahn]

In D88166#2298419, @reames wrote:

A cleaner way to handle this check would be to enumerate all loops in LoopInfo, and then check that the loop of every AR is in that set. I the loop has already been deleted, dereferencing it to check the valid flags seems a bit suspect.

Sounds good, I updated the code here, as it seems clearer.

Actually, why not just implement the isInvalid check on Loop that way?

LoopInfo manages the memory for each allocated loop and the memory is only really deleted when LI's memory is released. So the pointers to loops should stay valid as long as LI is alive, which allows for this quick check if the loop is valid. Not sure if there's a big benefit from changing that at the moment. What do you think?

[reames]

LGTM

In D88166#2300363, @fhahn wrote:

Actually, why not just implement the isInvalid check on Loop that way?

LoopInfo manages the memory for each allocated loop and the memory is only really deleted when LI's memory is released. So the pointers to loops should stay valid as long as LI is alive, which allows for this quick check if the loop is valid. Not sure if there's a big benefit from changing that at the moment. What do you think?

I haven't dug into this, but the comments on isInvalid say that the flag is set by the destructor. That's classic UB even if the underlying memory is retained. If we can avoid relying on UB for our asserts, and yet still be efficient, that seems like a win.

Just to be clear here, this is the abstract "it would be better if", not the "please go and change X before landing".

llvm/lib/Analysis/ScalarEvolution.cpp

while (!LoopStack.empty()) {
     if ((VerifySCEVStrict || isa<SCEVConstant>(Delta)) && !Delta->isZero()) {
       dbgs() << "Trip Count for " << *L << " Changed!\n";
       dbgs() << "Old: " << *CurBECount << "\n";
       dbgs() << "New: " << *NewBECount << "\n";
       dbgs() << "Delta: " << *Delta << "\n";
       std::abort();
     }
   }
+
+  // Collect all valid loops currently in LoopInfo.
+  SmallPtrSet<Loop *, 32> ValidLoops;
+  SmallVector<Loop *, 32> Worklist(LI.begin(), LI.end());
+  while (!Worklist.empty()) {
+    Loop *L = Worklist.pop_back_val();
+    if (ValidLoops.contains(L))
+      continue;
+    ValidLoops.insert(L);
+    Worklist.append(L->begin(), L->end());
+  }
+  // Check for SCEV expressions referencing invalid/deleted loops.
+  for (auto &KV : ValueExprMap) {
+    auto *AR = dyn_cast<SCEVAddRecExpr>(KV.second);
+    if (!AR)
+      continue;
+    assert(ValidLoops.contains(AR->getLoop()) &&
+           "AddRec references invalid loop");
+  }
 }
 
 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>();