This is an archive of the discontinued LLVM Phabricator instance.

[SCEV][NFC] Apply mass forgetMemoizedResults queries where possible
ClosedPublic

Authored by mkazantsev on Oct 11 2021, 11:00 PM.

Details

Summary

When forgetting multiple SCEVs, rather than doing this one by one, we can
instead use mass updates. We plan to make them more efficient than they
are now, potentially improving compile time.

Diff Detail

Event Timeline

mkazantsev created this revision.Oct 11 2021, 11:00 PM
mkazantsev requested review of this revision.Oct 11 2021, 11:00 PM
Herald added a project: Restricted Project. · View Herald TranscriptOct 11 2021, 11:01 PM
nikic added a comment.Oct 12 2021, 1:55 AM
llvm/lib/Analysis/ScalarEvolution.cpp
7569

We should be collecting these into a vector as well.

12836

You can just pass S directly, no need to create SmallVector for single-element ArrayRef.

I think we can do more of this kind, e.g. in forgetLoops. Will look into it more.

llvm/lib/Analysis/ScalarEvolution.cpp
7569

Good point!

mkazantsev retitled this revision from [SCEV][NFC] Tackle quadratic CT consumption in forgetValue to [SCEV][NFC] Tackle quadratic CT consumption when forgetting memoized results.
mkazantsev edited the summary of this revision. (Show Details)

Found some more places where it can be done. @nikic could you please check the CT now?

nikic added a comment.Oct 13 2021, 9:35 AM
llvm/lib/Analysis/ScalarEvolution.cpp
7486

Just wondering, does the problem described in this comment affect the new invalidation mechanism?

mkazantsev added inline comments.Oct 13 2021, 7:51 PM
llvm/lib/Analysis/ScalarEvolution.cpp
7486

If I'm reading this correctly, the new mechanism will drop trip count cache. The notion that we can sometimes forget something not for correctness purposes, but for the sole purpose of getting better results, is interesting. If it doesn't lead to any dangling pointers or directly wrong cached results, maybe we should consider non-recursive invalidation here.

mkazantsev added inline comments.Oct 13 2021, 9:10 PM
llvm/lib/Analysis/ScalarEvolution.cpp
7486

Giving it some more thought, I think this one might be a source of bugs. Imagine that exit count depends on a hypothetical SCEV (not corresponding to any existing instruction directly) which, in turn, uses value being forgotten. When it is destroyed, how do we ensure that we'll not end up with exit count referencing (indirectly) a dangling pointer?

Max, a suggestion review structure wise. If you flip the order of this patch and the one it's currently built on (i.e. by adding a forgetMemoizedResults arrayref wrapper), this can be easily landed as NFC. It won't really have any benefit compile time wise on it's own, but the change itself is not unreasonable. Inverting the review stack this way makes it easier to track the overall state of what's in review.

In fact, if you want to do that, you can consider this a conditional LGTM.

Two minor opportunities to exploit set invalidation for efficiency. I'll leave it to you whether these are worth separate review or not.

llvm/lib/Analysis/ScalarEvolution.cpp
12844

There's an opportunity to exploit the invalidation of sets at a time here by replacing multiple walks, with one walk and a set membership check.

12854

Same here. Though, I don't believe we have an set optimized contains_any already, so this might not be worth bothering with.

mkazantsev planned changes to this revision.Oct 21 2021, 10:32 PM

Ok, I also think that this one can go first.

mkazantsev retitled this revision from [SCEV][NFC] Tackle quadratic CT consumption when forgetting memoized results to [SCEV][NFC] Apply pass forgetMemoizedResults queries where possible.
mkazantsev edited the summary of this revision. (Show Details)
mkazantsev added reviewers: lebedev.ri, efriedma.
mkazantsev added inline comments.
llvm/lib/Analysis/ScalarEvolution.cpp
12844

Good point, I'll try to make this in a follow-up.

mkazantsev retitled this revision from [SCEV][NFC] Apply pass forgetMemoizedResults queries where possible to [SCEV][NFC] Apply mass forgetMemoizedResults queries where possible.Oct 21 2021, 11:29 PM
reames accepted this revision.Oct 22 2021, 10:11 AM

LGTM

This revision is now accepted and ready to land.Oct 22 2021, 10:11 AM
This revision was landed with ongoing or failed builds.Oct 25 2021, 12:05 AM
This revision was automatically updated to reflect the committed changes.