This is an archive of the discontinued LLVM Phabricator instance.

[EarlyCSE] Exploit open ended invariant.start scopes
ClosedPublic

Authored by reames on Feb 23 2018, 8:32 PM.

Details

Summary

If we have an invariant.start with no corresponding invariant.end, then the memory location becomes invariant indefinitely after the invariant.start. As a result, anything dominated by the start is guaranteed to see the value the memory location had when the invariant.start executed.

This patch adds an AvailableInvariants table which tracks the generation a particular memory location became invariant and then uses that information to allow value forwarding that would otherwise be disallowed by potentially aliasing stores. (Reminder: In EarlyCSE everything clobbers everything by default.)

This should be compatible with the MemorySSA variant, but design is generational. We can and should add first class support for invariant.start within MemorySSA at a later time.

Diff Detail

Repository
rL LLVM

Event Timeline

reames created this revision.Feb 23 2018, 8:32 PM
anna added a comment.Mar 9 2018, 12:34 PM

Patch looks good to me. Let's wait if anyone else has any comments.

lib/Transforms/Scalar/EarlyCSE.cpp
695 ↗(On Diff #135772)

I couldn't parse this comment.

803 ↗(On Diff #135772)

Pls add a comment here that this handles invariant end. So, AvailableInvariants are guaranteed to be invariant indefinitely from CurrentGeneration onwards.

test/Transforms/EarlyCSE/invariant-loads.ll
99 ↗(On Diff #135772)

why are we not able to catch this case? invariant.load is more powerful than invariant.start and we unconditionally return true for isOperatingOnInvariantMemAt

test/Transforms/EarlyCSE/invariant.start.ll
257 ↗(On Diff #135772)

Any idea if MemorySSA will catch this case?

reames added inline comments.Mar 9 2018, 3:18 PM
lib/Transforms/Scalar/EarlyCSE.cpp
695 ↗(On Diff #135772)

There are a family of intrinsics which were partially taught to early CSE "as if" they were real loads and stores. This code doesn't handle them yet because it was added as a layer on tp of MemLoc, not part of the MemLoc routines themselves. I have no plans to handle them.

test/Transforms/EarlyCSE/invariant-loads.ll
99 ↗(On Diff #135772)

The way this works currently is that we're only creating invariant scopes for invariant.start calls. I agree we could (and in the near future will) create them for invariant.load, but at the moment we're not. Given that, the call advances the generation. The unconditional "yes" for invariant_loads isn't triggered since we never pass in the load. Instead, we see the store is not an invariant_load and fallback to the conservative logic.

test/Transforms/EarlyCSE/invariant.start.ll
257 ↗(On Diff #135772)

At the moment, MemorySSA has no knowledge of invariant.start, so no. I do plan on adding support, but I'm going to start with open ended scopes.

reames updated this revision to Diff 137851.Mar 9 2018, 3:20 PM

Clarify a couple of comments.

Note: Since this has been LGTM, I'm going to wait until next week for additional comment and then submit.

anna added inline comments.Mar 12 2018, 10:48 AM
test/Transforms/EarlyCSE/invariant-loads.ll
99 ↗(On Diff #135772)

ah that makes sense! Thanks for the clarification.

This revision was not accepted when it landed; it landed in state Needs Review.Mar 14 2018, 2:37 PM
This revision was automatically updated to reflect the committed changes.