[SCEV][NFC] Verify intergity of SCEVUsers

[mkazantsev]

Summary

Make sure that, for every living SCEV, we have all its direct
operand tracking it as their user.

[mkazantsev]

Not 100% sure it should be UniqueSCEVs to iterate on; besides, we don't verify obsolete dangling users so far (at least not before we start dropping them). Ideas for further improvement welcome.

[reames]

In D112402#3083147, @mkazantsev wrote:

Not 100% sure it should be UniqueSCEVs to iterate on.

I think it's the right one. This is a property which should hold for all SCEVs. We'll miss stale unknowns (since they're removed from that set), but that's okay because they have no operands.

besides, we don't verify obsolete dangling users so far (at least not before we start dropping them)

I have no idea what you mean by this. Expand?

I'd LGTM this except for open question above. I'm concerned I'm missing something.

llvm/lib/Analysis/ScalarEvolution.cpp

12900

This code exists in at least one other place (getDefiningScopeBound). I'm fine with this landing as is, but we should probably start thinking about how to abstract user and operand walks.

12913

Minor: Can you make the normal case an early continue to reduce nesting?

[mkazantsev]

I have no idea what you mean by this. Expand?

Never mind, I confused myself thinking that we'd remove dependencies of SCEVs on forget, but we never do it actually. So it should never be the case.

[mkazantsev]

llvm/lib/Analysis/ScalarEvolution.cpp

12900

Will see if I can follow-up with factoring out this common part.

[mkazantsev]

Reduced nest.

[mkazantsev]

llvm/lib/Analysis/ScalarEvolution.cpp

12900

https://reviews.llvm.org/D112516

[reames]

LGTM

llvm/lib/Analysis/ScalarEvolution.cpp

void ScalarEvolution::verify() const {
   // 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");
   }
+
+  // Verify intergity of SCEV users.
+  for (const auto &S : UniqueSCEVs) {
+    SmallPtrSet<const SCEV *, 4> Ops;
+    if (const auto *NS = dyn_cast<SCEVNAryExpr>(&S))
+      Ops.insert(NS->op_begin(), NS->op_end());
+    else if (const auto *CS = dyn_cast<SCEVCastExpr>(&S))
+      Ops.insert(CS->getOperand());
+    else if (const auto *DS = dyn_cast<SCEVUDivExpr>(&S)) {
+      Ops.insert(DS->getLHS());
+      Ops.insert(DS->getRHS());
+    }
+    for (const auto *Op : Ops) {
+      // We do not store dependencies of constants.
+      if (isa<SCEVConstant>(Op))
+        continue;
+      auto It = SCEVUsers.find(Op);
+      if (It != SCEVUsers.end() && It->second.count(&S))
+        continue;
+      dbgs() << "Use of operand  " << *Op << " by user " << S
+             << " is not being tracked!\n";
+      std::abort();
+    }
+  }
 }
 
 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>();