Page MenuHomePhabricator

[SCEV] Support clearing Block/LoopDispositions for a single value.
ClosedPublic

Authored by fhahn on Sep 25 2022, 1:18 PM.

Details

Summary

Extend forgetBlockAndLoopDisposition to allow clearing information for a
single value. This can be useful when only a single value is changed,
e.g. because the instruction is moved.

For loop dispositions, we also need to clear the cached values for all
SCEV users, because they may depend on the starting value's loop
disposition.

Diff Detail

Event Timeline

fhahn created this revision.Sep 25 2022, 1:18 PM
Herald added a project: Restricted Project. · View Herald TranscriptSep 25 2022, 1:18 PM
fhahn requested review of this revision.Sep 25 2022, 1:18 PM
Herald added a project: Restricted Project. · View Herald TranscriptSep 25 2022, 1:18 PM
mkazantsev added inline comments.Sep 26 2022, 2:33 AM
llvm/lib/Analysis/ScalarEvolution.cpp
8387
if (!V)
  return;
...
8395

I' not sure this is right. Imagine we have:

a = ...
x = a + 1;
y = b + 1;

Loop dispositions for a and y have been cached but not for x. If we stop at x, then y won't be invalidated.

Is this an impossible situation?

8406

not needed?

fhahn updated this revision to Diff 465154.Oct 4 2022, 2:06 PM

Restructure code to use early exits as suggested, thanks!

fhahn marked 3 inline comments as done.Oct 4 2022, 2:16 PM
fhahn added inline comments.
llvm/lib/Analysis/ScalarEvolution.cpp
8387

Simplified as suggested with a slight change to clear the full cache on this path, thanks!

8395

Loop dispositions for a and y have been cached but not for x. If we stop at x, then y won't be invalidated.

I might be missing something, but a specific value should only be passed in for invalidation if only this value changed in the IR (e.g. because it as hoisted or sunk). So if a's loop disposition becomes invalid, I think we would only need to invalidate x, because y doesn't use either a or x.

A slightly different scenario could be where y depends on x.

a = ...
x = a + 1;
y = x + 1;

Now if x would not be cached but y would, then we would not invalidate y at the moment.

I *think* this shouldn't happen, because when computing y's loop disposition I think we require x's disposition to already be known (ie. in the cache). From looking at the existing code, it doesn't look like current invalidation could introduce any such gaps.

Does that make sense? We could also go the more conservative route and remove the early continue, but I have a slight preference towards keeping it for now and revisit if any cases show up where the verifier runs into such gaps.

8406

Gone in the re-structured version, thanks!

fhahn marked 3 inline comments as done.Oct 6 2022, 3:06 PM

ping :)

nikic added inline comments.Oct 7 2022, 2:45 AM
llvm/lib/Analysis/ScalarEvolution.cpp
8395

nit: Space after =

8399

nit: Line length

8400

I don't really get why loop and block dispositions get different handling here. Aren't block dispositions computed in essentially the same recursive way?

fhahn updated this revision to Diff 466042.Oct 7 2022, 4:59 AM

Fix formatting, also clear block dispositions for all users recursively.

fhahn added inline comments.Oct 7 2022, 5:02 AM
llvm/lib/Analysis/ScalarEvolution.cpp
8395

Formatting should also be fixed now, sorry about that.

8400

You are right, my initial thinking only considered dominance between the changed expression and the SCEV users, but not considered that the cache relates SCEV expressions to arbitrary blocks. Updated!

nikic accepted this revision.Oct 7 2022, 5:04 AM

LG

llvm/lib/Analysis/ScalarEvolution.cpp
8418

This line shouldn't be there?

llvm/lib/Transforms/Scalar/LoopDeletion.cpp
92

Declaration can be moved inside the if.

This revision is now accepted and ready to land.Oct 7 2022, 5:04 AM
fhahn updated this revision to Diff 466064.Oct 7 2022, 6:45 AM

Address latest comments, planning to land shortly

fhahn marked 2 inline comments as done.Oct 7 2022, 7:49 AM
fhahn added inline comments.
llvm/lib/Analysis/ScalarEvolution.cpp
8418

Yep, that was left over from earlier versions, removed, thanks!

llvm/lib/Transforms/Scalar/LoopDeletion.cpp
92

Moved, thanks

This revision was automatically updated to reflect the committed changes.
fhahn marked 2 inline comments as done.