[SCEV] Verify all IR -> SCEV mappings

[nikic]

Summary

This extends SCEV verification to check not only backedge-taken counts, but all entries in the IR -> SCEV cache. The restrictions are the same as for the BECount case, i.e. we ignore expressions based on undef, we only diagnose constant deltas (there are way too many false positives otherwise) and we limit to reachable code.

Not entirely sure whether doing this is worthwhile, as it's probably quite expensive, and I didn't catch any new issues in llvm-lit tests / llvm-test-suite at least.

[reames]

I think this is very worthwhile doing under expensive asserts, and probably any time we verify SCEV explicitly. Given that, LGTM

llvm/lib/Analysis/ScalarEvolution.cpp

const SCEV *visitCouldNotCompute(const SCEVCouldNotCompute *Expr) {
       return SE.getCouldNotCompute();
     }
   };
 
   SCEVMapper SCM(SE2);
   SmallPtrSet<BasicBlock *, 16> ReachableBlocks;
   getReachableBlocks(ReachableBlocks, F);
 
+  auto GetDelta = [&](const SCEV *Old, const SCEV *New) -> const SCEV * {
+    if (containsUndefs(Old) || containsUndefs(New)) {
+      // SCEV treats "undef" as an unknown but consistent value (i.e. it does
+      // not propagate undef aggressively).  This means we can (and do) fail
+      // verification in cases where a transform makes a value go from "undef"
+      // to "undef+1" (say).  The transform is fine, since in both cases the
+      // result is "undef", but SCEV thinks the value increased by 1.
+      return nullptr;
+    }
+
+    // Unless VerifySCEVStrict is set, we only compare constant deltas.
+    const SCEV *Delta = SE2.getMinusSCEV(Old, New);
+    if (!VerifySCEVStrict && !isa<SCEVConstant>(Delta))
+      return nullptr;
+
+    return Delta;
+  };
+
   while (!LoopStack.empty()) {
     auto *L = LoopStack.pop_back_val();
     llvm::append_range(LoopStack, *L);
 
     // Only verify BECounts in reachable loops. For an unreachable loop,
     // any BECount is legal.
     if (!ReachableBlocks.contains(L->getHeader()))
       continue;
if (CurBECount == SE2.getCouldNotCompute() ||
       // NB! This situation is legal, but is very suspicious -- whatever pass
       // change the loop to make a trip count go from could not compute to
       // computable or vice-versa *should have* invalidated SCEV.  However, we
       // choose not to assert here (for now) since we don't want false
       // positives.
       continue;
     }
 
-    if (containsUndefs(CurBECount) || containsUndefs(NewBECount)) {
-      // SCEV treats "undef" as an unknown but consistent value (i.e. it does
-      // not propagate undef aggressively).  This means we can (and do) fail
-      // verification in cases where a transform makes the trip count of a loop
-      // go from "undef" to "undef+1" (say).  The transform is fine, since in
-      // both cases the loop iterates "undef" times, but SCEV thinks we
-      // increased the trip count of the loop by 1 incorrectly.
-      continue;
-    }
-
     if (SE.getTypeSizeInBits(CurBECount->getType()) >
         SE.getTypeSizeInBits(NewBECount->getType()))
       NewBECount = SE2.getZeroExtendExpr(NewBECount, CurBECount->getType());
     else if (SE.getTypeSizeInBits(CurBECount->getType()) <
              SE.getTypeSizeInBits(NewBECount->getType()))
       CurBECount = SE2.getZeroExtendExpr(CurBECount, NewBECount->getType());
 
-    const SCEV *Delta = SE2.getMinusSCEV(CurBECount, NewBECount);
-
-    // Unless VerifySCEVStrict is set, we only compare constant deltas.
-    if ((VerifySCEVStrict || isa<SCEVConstant>(Delta)) && !Delta->isZero()) {
+    const SCEV *Delta = GetDelta(CurBECount, NewBECount);
+    if (Delta && !Delta->isZero()) {
       dbgs() << "Trip Count for " << *L << " Changed!\n";
       dbgs() << "Old: " << *CurBECount << "\n";
       dbgs() << "New: " << *NewBECount << "\n";
       dbgs() << "Delta: " << *Delta << "\n";
       std::abort();
     }
   }
 
#endif
 
     // Check that the value is also part of the reverse map.
     auto It = ExprValueMap.find(KV.second);
     if (It == ExprValueMap.end() || !It->second.contains(KV.first)) {
       dbgs() << "Value " << *KV.first
              << " is in ValueExprMap but not in ExprValueMap\n";
       std::abort();
     }
+
+    if (auto *I = dyn_cast<Instruction>(&*KV.first)) {
+      if (!ReachableBlocks.contains(I->getParent()))
+        continue;
+      const SCEV *OldSCEV = SCM.visit(KV.second);
+      const SCEV *NewSCEV = SE2.getSCEV(I);
+      const SCEV *Delta = GetDelta(OldSCEV, NewSCEV);
+      if (Delta && !Delta->isZero()) {
+        dbgs() << "SCEV for value " << *I << " changed!\n"
+               << "Old: " << *OldSCEV << "\n"
+               << "New: " << *NewSCEV << "\n"
+               << "Delta: " << *Delta << "\n";
+        std::abort();
+      }
+    }
   }
 
   for (const auto &KV : ExprValueMap) {
     for (Value *V : KV.second) {
       auto It = ValueExprMap.find_as(V);
       if (It == ValueExprMap.end()) {
         dbgs() << "Value " << *V
                << " is in ExprValueMap but not in ValueExprMap\n";