Page MenuHomePhabricator

[MemorySSA] Repair AccessList invariants after insertion of new MemoryUseOrDef.
AbandonedPublic

Authored by bryant on Oct 30 2016, 3:03 AM.

Details

Summary

An invariant of AccessLists is that the defining access of a Use or Def is the nearest preceding Def node. For instance, within a BasicBlock:

0 = MemoryDef(liveOnEntry)
1 = MemoryDef(0)
2 = MemoryUse(n)
3 = MemoryDef(m)

1 is the nearest parent Def of 2 and 3, and m and n must be 1.

This patch simplifies the interfaces of createMemoryAccessBefore/After, and augments them to maintain this invariant.

Additionally, when inserting a new Def after an existing Def, there is currently no (clean) way to update the users of the old Def to use the new Def. So createDefiningAccess now permits the option of updating the users.

Diff Detail

Repository
rL LLVM

Event Timeline

bryant updated this revision to Diff 76330.Oct 30 2016, 3:03 AM
bryant retitled this revision from to [MemorySSA] Repair AccessList invariants after insertion of new MemoryUseOrDef..
bryant updated this object.
bryant set the repository for this revision to rL LLVM.
bryant added a subscriber: llvm-commits.
bryant added inline comments.Oct 30 2016, 3:07 AM
lib/Transforms/Utils/MemorySSA.cpp
1619

Not sure if this line (as well as the similar one above) should go away.

unittests/Transforms/Utils/MemorySSA.cpp
138

I'm unsure if this should be removed, since use replacement is already conducted inside createMemoryAccessAfter's call to createDefiningAccess.

bryant created this revision.
bryant added reviewers: dberlin, george.burgess.iv.
bryant added a subscriber: llvm-commits.
bryant set the repository for this revision to rL LLVM.

An invariant of AccessLists is that the defining access of a Use or Def is the nearest preceding Def node.

False
This is correct for def's but not for uses.

For instance, within a BasicBlock:

0 = MemoryDef(liveOnEntry)
1 = MemoryDef(0)
2 = MemoryUse(n)
3 = MemoryDef(m)

1 is the nearest parent Def of 2 and 3, and m and n must be 1.

Given the above, this is incorrect.
n may be 0

IE the following is perfectly legal

0 = MemoryDef(liveOnEntry)
1 = MemoryDef(0)
2 = MemoryUse(0)
3 = MemoryDef(1)

Thanks for clearing up my misunderstanding regarding MemoryUses.

This patch simplifies the interfaces of createMemoryAccessBefore/After, and augments them to maintain this invariant.

Additionally, when inserting a new Def after an existing Def, there is currently no (clean) way to update the users of the old Def to use the new Def.

RAUW works exactly to do this case.

I'm not so sure that it's sufficient. Suppose, for instance, that I wanted to insert a MemoryDef between 1 and 2 in the below AccessList:

0 = MemoryDef(liveOnEntry)
1 = MemoryDef(0)
2 = MemoryDef(1)
3 = MemoryUse(1)

Invoking createMemoryAccess followed by RAUW of 1's uses with 4 would result in:

0 = MemoryDef(liveOnEntry)
1 = MemoryDef(0)
4 = MemoryDef(4)   ; <=======
2 = MemoryDef(4)
3 = MemoryUse(4)

So RAUW needs to happen before setting 4's defining access to 1, but this isn't possible with the current createDefiningAccess. What other options are there? RAUW with a bogus Def, create, then re-RAUW to the newly created Def? I feel like I'm missing something obvious, so clarification would be much appreciated.

bryant abandoned this revision.Nov 14 2016, 11:21 PM

Abandoning this in favor of https://reviews.llvm.org/D26661 . It's enough to be able to move MemoryUseOrDefs around in a semantics-preserving fashion.