[SCEV] Invalidate user SCEVs along with operand SCEVs to avoid cache corruption

[mkazantsev]

Summary

Following discussion in D110390, it seems that we are suffering from unability
to traverse users of a SCEV being invalidated. The result of that is that ScalarEvolution's
inner caches may store obsolete data about SCEVs even if their operands are
forgotten. It creates problems when we try to verify the contents of those caches.

It's also a frequent situation when messing with cache causes very sneaky and
hard-to-analyze bugs related to corruption of memory when dealing with cached
data. They are lurking there because ScalarEvolution's veirfication is not powerful
enough and misses many problematic cases. I plan to make SCEV's verification
much stricter in follow-ups, and this requires dangling-pointers-free caches.

This patch makes sure that, whenever we forget cached information for a SCEV,
we also forget it for all SCEVs that (transitively) use it.

This may have negative compile time impact. It's a sacrifice we are more
than willing to make to enforce correctness. We can also save some time by
reworking invokers of forgetMemoizedResults (maybe we can forget multiple
SCEVs with single query).

[mkazantsev]

If it's too bad in terms of compile time, I have some ideas how to improve it. Need to know whether they are needed immediately or can be done as follow-ups.

[reames]

Before anything else, I'd really love to see compile time data. @nikic Can you easily collect?

Style wise, I think this makes a lot more sense to have a user list on the SCEV itself than a separate structure, but we can debate that separately.

[mkazantsev]

In D111533#3055325, @reames wrote:

Style wise, I think this makes a lot more sense to have a user list on the SCEV itself than a separate structure, but we can debate that separately.

We can't do it without const_casts, and consts_casts may cause UB. I don't want to take this risk unless you have *really* strong arguments in favour of this.

[reames]

In D111533#3055421, @mkazantsev wrote:

In D111533#3055325, @reames wrote:

Style wise, I think this makes a lot more sense to have a user list on the SCEV itself than a separate structure, but we can debate that separately.

We can't do it without const_casts, and consts_casts may cause UB. I don't want to take this risk unless you have *really* strong arguments in favour of this.

You can always make the UseList field mutable, but let's hold that debate until we have CT numbers. One reason I prefer the field is likely better cache locality, but I could be completely wrong about that and measurements to see if it matters are a good starting point.

[nikic]

Compile-time on CTMark: https://llvm-compile-time-tracker.com/compare.php?from=943b3048484b7e3cf04f4d51c23c82fcece2185d&to=5e2c6abab42241c06680941be06fddcb9279e63d&stat=instructions

It doesn't look terrible at least, though some individual files go up by up to 7%. However, I suspect that as implemented this will make some of our already bad cases worse, i.e. when we're scanning over a large use-def graph, and this will effectively revisit SCEVs through an additional SCEV-level use graph. Passing in the Visited set and retaining it across a whole forgetValue()/forgetLoop() call would probably make things better at little additional complexity.

[mkazantsev]

I think we can save a lot of time by making mass requests from forgetValue/loop. Let me wright a draft...

[mkazantsev]

@nikic could you please re-measure this one together with D111602?

[mkazantsev]

Just forwarding here:

And here's both patches together: http://llvm-compile-time-tracker.com/compare.php?from=943b3048484b7e3cf04f4d51c23c82fcece2185d&to=82329ed73bb4100f3641703982cb661f77b95344&stat=instructions

So with the CT algorithmic fix isn't so bad. At least it's not spiralling out of control. Can we continue discussion assuming that it's fairly fine?

[mkazantsev]

Ping

[danilaml]

llvm/lib/Analysis/ScalarEvolution.cpp

4083–4086

Why is this if needed?

[reames]

I think this makes sense, and is worth the remaining compile time cost. If you want to rebase over the other patch (see my suggestion there), and address the minor style comments, I'd be willing to LGTM.

llvm/lib/Analysis/ScalarEvolution.cpp

1102

Please address the lint check.

4083–4086

Yeah, the default constructor should handle this case if I'm reading it right.

12739

I'm not sure this is the right place for the use list walk. Doing it here has the effecting of leaving all the user SCEVs around, and simplify forgetting the cached property of said SCEVs. Is that actually what we want? In particular, the (transitively reached) SCEVs will still be in the ValueExprMap and thus still mapped to the instructions.

Maybe we should be forgetting all the transitive inst->SCEV mappings as well? If we've, e.g., added flags to the IR instruction, that could very well map to a new SCEV node.

Hm, thinking about it, that's a deeper change than it first sounded. So yes, I'm convinced this is a reasonable starting point. :)

[nikic]

I think tracking users is generally the right thing to do, but I have some reservations about the approach. This makes a big implicit change, and I don't think we have a good understanding of the effects it has for all users of this API.

For example, if I look at https://github.com/llvm/llvm-project/blob/13c31539f7da403fee11fe2163249837460c3bf2/llvm/lib/Analysis/ScalarEvolution.cpp#L4424, which forgets all values using a SCEVUnknown placeholder, it seems like we should be replacing that code with just an invalidation of the SCEV node and it's users, rather than doing walks both on SCEV users and IR users. Of course, this would require also clearing out the corresponding SCEV <-> IR mappings at the same time.

I'm also thinking that the concept of invalid SCEVs (see checkValidity()) becomes rather silly if we're tracking users -- we should be dropping the invalid SCEV users directly and guarantee that none of the SCEVs in the map are invalid.

I would prefer it if we initially only landed the infrastructure to track users (without touching invalidation) and then migrate over individual invalidation users.

[nikic]

llvm/include/llvm/Analysis/ScalarEvolution.h

1505 ↗

(On Diff #378605)

I would expect that on average there's less than 16 users for a given SCEV.

[reames]

In D111533#3078423, @nikic wrote:

(snip)

I generally agree that once we have users, we should revisit a bunch of how we do invalidation. I have no problem with this being used in one place first, but I agree we can and should push this further.

I would prefer it if we initially only landed the infrastructure to track users (without touching invalidation) and then migrate over individual invalidation users.

I have no problem with this approach. I don't advocate it, but I'd be completely fine with the SCEV user infrastructure landing on it's own.

(Oh, one thing that occurred to me. We should probably add verification/asserts of the use links themselves at some point. I would be fine with that being a separate patch.)

[mkazantsev]

llvm/lib/Analysis/ScalarEvolution.cpp

1102

But it's what LLVM's in-bult clang-format is generating...

4083–4086

Good point!

[mkazantsev]

Thanks for the input, I'll try to split out everything that can be split to make this one easier.

[mkazantsev]

llvm/include/llvm/Analysis/ScalarEvolution.h

1505 ↗

(On Diff #378605)

Honestly, this depends on workload. Let's reduce it down to 8. I think the reasonable choise here requires research too big to be made.

[mkazantsev]

All splittable parts are split out.

[reames]

I'd LGTM this, but Nikita seemed to prefer a slightly different approach. Give him a chance to response and redirect if he feels necessary, and if not, you can treat this as LGTMed in a day or two.

[mkazantsev]

Upon that, I'm going to merge it tomorrow if there will be no objections.

[nikic]

In D111533#3089254, @mkazantsev wrote:

Upon that, I'm going to merge it tomorrow if there will be no objections.

Yeah, feel free. I didn't have time to work on this and don't want to hold it up further.

llvm/lib/Analysis/ScalarEvolution.cpp

12741

Might make sense to initialize this from ToForget to avoid duplicates in the initial worklist?

12769

Hm ... we don't really need to consider user SCEVs here, as the used SCEV will be part of the operands as well.

Alternatively, if we're already considering user SCEVs, we no longer need the hasOperand() approach, we could directly check whether ENT.ExactNotTaken == S.

[nikic]

llvm/lib/Analysis/ScalarEvolution.cpp

12769

To finish the thought, we could do something like for (const auto &EI : BEInfo.ExitNotTaken) if (ToForget.contains(EI.ExactNotTaken)) erase(), which makes this approximately O(exits) rather than O(loops * scevs). In any case, that's for a followup...

[mkazantsev]

llvm/lib/Analysis/ScalarEvolution.cpp

12741

Good catch!

12769

Thanks for the idea. I'll try to follow-up on that.

[uabelho]

Hi,

The following starts crashing with this patch:

opt -passes='loop-mssa(indvars,indvars)' -o /dev/null bbi-63564.ll

We hit this assert:

opt: ../include/llvm/Support/Casting.h:104: static bool llvm::isa_impl_cl<llvm::Instruction, const llvm::Value *>::doit(const From *) [To = llvm::Instruction, From = const llvm::Value *]: Assertion `Val && "isa<> used on a null pointer"' failed.

bbi-63564.ll1 KBDownload

[nikic]

Just looking at the trace, I suspect we leave behind invalid SCEVs in ValuesAtScope. This is basically a (SCEV, Loop) -> SCEV map, and while we do clear entries if the SCEV on the left side is invalidated, we don't if the SCEV on the right is.

[reames]

In D111533#3159337, @nikic wrote:

Just looking at the trace, I suspect we leave behind invalid SCEVs in ValuesAtScope. This is basically a (SCEV, Loop) -> SCEV map, and while we do clear entries if the SCEV on the left side is invalidated, we don't if the SCEV on the right is.

This is exactly correct. I just finished confirming this experimentally when I saw your comment.

[reames]

Fix for reported issue out for review here: https://reviews.llvm.org/D114738

llvm/lib/Analysis/ScalarEvolution.cpp

if (auto *U = dyn_cast<SCEVUnknown>(Op)) {
 
     // Create an explicit cast node.
     // We can reuse the existing insert position since if we get here,
     // we won't have made any changes which would invalidate it.
     SCEV *S = new (SCEVAllocator)
         SCEVPtrToIntExpr(ID.Intern(SCEVAllocator), Op, IntPtrTy);
     UniqueSCEVs.InsertNode(S, IP);
     addToLoopUseLists(S);
     registerUser(S, Op);
     return S;
   }
 
   assert(Depth == 0 && "getLosslessPtrToIntExpr() should not self-recurse for "
                        "non-SCEVUnknown's.");
 
   // Otherwise, we've got some expression that is more complex than just a
   // single SCEVUnknown. But we don't want to have a SCEVPtrToIntExpr of an
if (I != ValueExprMap.end()) {
     }
     ValueExprMap.erase(V);
   }
 }
 
 /// Return an existing SCEV if it exists, otherwise analyze the expression and
 /// create a new one.
 const SCEV *ScalarEvolution::getSCEV(Value *V) {
   assert(isSCEVable(V->getType()) && "Value is not SCEVable!");
 
   const SCEV *S = getExistingSCEV(V);
   if (S == nullptr) {
     S = createSCEV(V);
     // During PHI resolution, it is possible to create two SCEVs for the same
     // V, so it is needed to double check whether V->S is inserted into
     // ValueExprMap before insert S->{V, 0} into ExprValueMap.
     std::pair<ValueExprMapType::iterator, bool> Pair =
         ValueExprMap.insert({SCEVCallbackVH(V, this), S});
     if (Pair.second) {
       ExprValueMap[S].insert({V, nullptr});

 bool ScalarEvolution::properlyDominates(const SCEV *S, const BasicBlock *BB) {
   return getBlockDisposition(S, BB) == ProperlyDominatesBlock;
 }
 
 bool ScalarEvolution::hasOperand(const SCEV *S, const SCEV *Op) const {
   return SCEVExprContains(S, [&](const SCEV *Expr) { return Expr == Op; });
 }
 
 void ScalarEvolution::forgetMemoizedResults(ArrayRef<const SCEV *> SCEVs) {
-  for (auto *S : SCEVs)
-    forgetMemoizedResultsImpl(S);
   SmallPtrSet<const SCEV *, 8> ToForget(SCEVs.begin(), SCEVs.end());
+  SmallVector<const SCEV *, 8> Worklist(ToForget.begin(), ToForget.end());
+
+  while (!Worklist.empty()) {
+    const SCEV *Curr = Worklist.pop_back_val();
+    auto Users = SCEVUsers.find(Curr);
+    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 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;
   }
 
   auto RemoveSCEVFromBackedgeMap = [&ToForget](
       DenseMap<const Loop *, BackedgeTakenInfo> &Map) {
         for (auto I = Map.begin(), E = Map.end(); I != E;) {
           BackedgeTakenInfo &BEInfo = I->second;
           if (any_of(ToForget,
                      [&BEInfo](const SCEV *S) { return BEInfo.hasOperand(S); }))
             Map.erase(I++);
           else
             ++I;
         }
   };
 
   RemoveSCEVFromBackedgeMap(BackedgeTakenCounts);
   RemoveSCEVFromBackedgeMap(PredicatedBackedgeTakenCounts);