This is an archive of the discontinued LLVM Phabricator instance.

Make promoteLoopAccessesToScalars independent of AliasSet [NFC]
ClosedPublic

Authored by asbirlea on Jul 14 2017, 2:36 PM.

Details

Summary

The current promoteLoopAccessesToScalars method receives an AliasSet, but
the information used is in fact a list of Value*, known to must alias.
Create the list ahead of time to make this method independent of the AliasSet class.

While there is no functionality change, this adds overhead for creating
a set of Value*, when promotion would normally exit earlier.
This is meant to be as a first refactoring step in order to start replacing
AliasSetTracker with MemorySSA.
And while the end goal is to redesign LICM, the first few steps will focus on
adding MemorySSA as an alternative to the AliasSetTracker using most of the
existing functionality.

Diff Detail

Repository
rL LLVM

Event Timeline

asbirlea created this revision.Jul 14 2017, 2:36 PM
sanjoy added inline comments.Jul 14 2017, 7:16 PM
lib/Transforms/Scalar/LICM.cpp
306 ↗(On Diff #106710)

I'd just remove this.

309 ↗(On Diff #106710)

Can you see duplicates here? If not, I'd suggest changing this to a SmallVector (and pass in an ArrayRef to promoteLoopAccessesToScalars).

Actually, one good reason for switching to passing in a vector of pointers to promoteLoopAccessesToScalars is that we probably (?) want a deterministic order of insertion into LoopUses since that will influence what LoopPromoter does.

asbirlea updated this revision to Diff 106748.Jul 14 2017, 8:36 PM

Remove/update comments.

asbirlea marked an inline comment as done.Jul 14 2017, 8:46 PM
asbirlea added inline comments.
lib/Transforms/Scalar/LICM.cpp
309 ↗(On Diff #106710)

I'm not 100% sure if I can see duplicates, but the way I see the AliasSets being built it looks possible. The values are stored as a list in AliasSet:PointerRec.

The actual reason for keeping the PointerMustAliases as a set, is that in the alternative implementation I have (using MemorySSA) values can be deleted.
This happens to enable promotion after promotion.
In the AliasSetTracker, when this case comes up, there's the callback in LoopPromoter that updates the AliasSet. With MemSSA, something similar updates a SmallPtrSet<Value*>.

FWIW, I'm not planning to land this until I get the follow-up patch up for review and get input on both.

sanjoy requested changes to this revision.Sep 11 2017, 12:09 PM
sanjoy added inline comments.
lib/Transforms/Scalar/LICM.cpp
304 ↗(On Diff #106748)

The indent looks off here (clang-format should fix it).

307 ↗(On Diff #106748)

LLVM style avoids { for single statement loops and if statements.

1037 ↗(On Diff #106748)

Does this modify PointerMustAliases? If not, make this a const reference.

1047 ↗(On Diff #106748)

I think this can introduce non-determinism since SmallPtrSet does not have a deterministic order. You'll need some other way to pick a canonical address (just passing it in explicitly is fine).

1135 ↗(On Diff #106748)

Whitespace is off (but again, clang-format will fix this).

And the iteration order is not deterministic here either and this can produce non-deterministic output (via LoopUses). I'm not a 100% sure about the non-determinism, but we should use a stable iteration order unless we can prove that the output will be deterministic.

This revision now requires changes to proceed.Sep 11 2017, 12:09 PM
asbirlea updated this revision to Diff 114728.Sep 11 2017, 4:07 PM
asbirlea edited edge metadata.

Address comments.

asbirlea updated this revision to Diff 114730.Sep 11 2017, 4:15 PM

Remove comment.

sanjoy accepted this revision.Sep 11 2017, 4:25 PM
sanjoy added inline comments.
lib/Transforms/Scalar/LICM.cpp
971 ↗(On Diff #114728)

You could also add a getSetRef() (like getArrayRef()) method to SetVector to expose the contained set and pass that into LoopPromoter instead of changing LoopPromoter itself.

But this is fine too.

This revision is now accepted and ready to land.Sep 11 2017, 4:25 PM
asbirlea marked 6 inline comments as done.Sep 12 2017, 2:19 PM

Thanks for the review!

lib/Transforms/Scalar/LICM.cpp
971 ↗(On Diff #114728)

Noted as a future change.

1047 ↗(On Diff #106748)

Changed to SmallSetVector.

1135 ↗(On Diff #106748)

As above, SmallSetVector.

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