Fully delete stale SCEVs from ValuesAtScope map

[reames]

Summary

This fixes the regression reported against D111533. I don't actually believe this is a regression, but trying to message things enough to trigger without that change doesn't seem particular worthwhile either.

[nikic]

The idea here is right, but I'm concerned that this will have pathological cases, because we need to scan the whole ValuesAtScopes map any time we forget something. This map can be large. The proper way to handle this would be to add a reverse map for invalidation purposes (similar to D114784, but for ValuesAtScope).

llvm/lib/Analysis/ScalarEvolution.cpp

12897

Should be easy to do with llvm::remove_if().

[nikic]

Implementation using reverse map up at D114788.

Mild compile-time effect can already be seen for the average case, and would probably be much worse (quadratic) for degenerate cases:

This patch: https://llvm-compile-time-tracker.com/compare.php?from=eee035235ebd76b0e1b62f6dec989874a3102233&to=96a6af0ec6a64c58dea81c71cb8e3b8f04c7e1b6&stat=instructions
Reverse map: https://llvm-compile-time-tracker.com/compare.php?from=72d45d2131f55751be7654e5d13115fe5b150dbb&to=a653588a31f275b318f1fbe6be0c274b2acf1e22&stat=instructions

[reames]

Abandon in favor of @nikic's alternate patch.

[uabelho]

@nikic patch indeed solved the problem.
Thanks!

llvm/lib/Analysis/ScalarEvolution.cpp

if (Users != SCEVUsers.end())
       for (auto *User : Users->second)
         if (ToForget.insert(User).second)
           Worklist.push_back(User);
   }
 
   for (auto *S : ToForget)
     forgetMemoizedResultsImpl(S);
 
+  for (auto &KV : ValuesAtScopes) {
+    // We could delete only the entry in the inner array.
+    typedef std::pair<const Loop *, const SCEV *> EntryTy;
+    if (llvm::any_of(KV.second,
+                     [&](const EntryTy &E) {
+                       return ToForget.count(E.second); }))
+      KV.second.clear();
+  }
+
   for (auto I = PredicatedSCEVRewrites.begin();
        I != PredicatedSCEVRewrites.end();) {
     std::pair<const SCEV *, const Loop *> Entry = I->first;
     if (ToForget.count(Entry.first))
       PredicatedSCEVRewrites.erase(I++);
     else
       ++I;
   }

llvm/test/Transforms/IndVarSimplify/bbi-63564.ll

+; NOTE: Assertions have been autogenerated by utils/update_test_checks.py
+; RUN: opt -passes='loop-mssa(indvars,indvars)' -S < %s | FileCheck %s
+
+target triple = "x86_64-unknown-linux-gnu"
+
+@c = external global i16, align 1
+@a = external global i16, align 1
+
+; When we delete %c.promoted, we need to ensure we clear the getSCEVAtScope
+; cache or we'll crash trying to access loop disposition of the exit value
+; for the remaining IV.
+define void @f() {
+; CHECK-LABEL: @f(
+; CHECK-NEXT:  entry:
+; CHECK-NEXT:    br label [[FOR_COND:%.*]]
+; CHECK:       for.cond:
+; CHECK-NEXT:    br i1 false, label [[FOR_BODY:%.*]], label [[FOR_END4:%.*]]
+; CHECK:       for.body:
+; CHECK-NEXT:    br label [[FOR_BODY2:%.*]]
+; CHECK:       for.body2:
+; CHECK-NEXT:    [[INC2:%.*]] = phi i16 [ undef, [[FOR_BODY]] ], [ [[INC:%.*]], [[FOR_BODY2]] ]
+; CHECK-NEXT:    [[INC]] = add nsw i16 [[INC2]], 1
+; CHECK-NEXT:    store i16 [[INC]], i16* undef, align 1
+; CHECK-NEXT:    br i1 true, label [[FOR_BODY2]], label [[CRIT_EDGE:%.*]]
+; CHECK:       crit_edge:
+; CHECK-NEXT:    [[INC_LCSSA:%.*]] = phi i16 [ [[INC]], [[FOR_BODY2]] ]
+; CHECK-NEXT:    store i16 [[INC_LCSSA]], i16* @a, align 1
+; CHECK-NEXT:    unreachable
+; CHECK:       for.end4:
+; CHECK-NEXT:    ret void
+;
+entry:
+  br label %for.cond
+
+for.cond:                                         ; preds = %entry
+  br i1 false, label %for.body, label %for.end4
+
+for.body:                                         ; preds = %for.cond
+  %c.promoted = load i16, i16* @c, align 1
+  br label %for.body2
+
+for.body2:                                        ; preds = %for.body2, %for.body
+  %inc33 = phi i16 [ %c.promoted, %for.body ], [ %inc3, %for.body2 ]
+  %inc2 = phi i16 [ undef, %for.body ], [ %inc, %for.body2 ]
+  %inc = add nsw i16 %inc2, 1
+  store i16 %inc, i16* undef, align 1
+  %inc3 = add nsw i16 %inc33, 1
+  %tobool = icmp ne i16 %inc3, 0
+  br i1 %tobool, label %for.body2, label %crit_edge
+
+crit_edge:                                        ; preds = %for.body2
+  %inc.lcssa = phi i16 [ %inc, %for.body2 ]
+  store i16 %inc.lcssa, i16* @a, align 1
+  unreachable
+
+for.end4:                                         ; preds = %for.cond
+  ret void
+}