llvm dev - Oct 2016 - [PATCH] D26127: [MemorySSA] Repair AccessList invariants after insertion of new MemoryUseOrDef.

On Sun, Oct 30, 2016 at 4:08 PM, Bryant Wong <
3.14472+reviews.llvm.org at gmail.com> wrote:
>
> On Sun, Oct 30, 2016 at 6:48 PM, Daniel Berlin <dberlin at
dberlin.org>
> wrote:
>
>> In particular:
>> "
>> 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:
>> ....
>> "
>>
>> Which is why this is not the way one does this, anywhere.
>> If you wish to *replace* an existing access, the normal way is:
>>
>>
> As my original post indicates, I wish to insert an access, not replace
> anything. I've inserted a new memory instruction (memmove, memcpy, or
> memset), into the IR and wish to keep the MSSA tree synchronized.
>
This, in general, is not possible right now. See below.


>
>
>>            MemoryAccess *Def = OldMemAcc->getDefiningAccess();
>>            NewMemAcc >>               
MSSA->createMemoryAccessAfter(Repl, Def,
>> OldMemAccess->getMemoryInst());
>>            OldMemAcc->replaceAllUsesWith(NewMemAcc);
>>
>> It doesn't make any sense to create a replacing access with the
thing you
>> are going to replace as the definition.
>>
>> Really, I don't want to replace anything. I'm interested in
insertions.
> We have removals and replacements. So might insertion also be a valid
> concept with MSSA?
>
Yes-  but you said "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."

But this is not a sensible thing to do, either in LLVM's SSA IR or
MemorySSA, unless you a replacing an access.

There can be no clean way to update the users because insert of stores in
random places may cause new phi nodes to need to exist, etc[1]

The existing API's are meant for the existing users, which do not insert
completely new accesses, but instead, are moving or replacing existing
accesses.
This is why they all say this in their docs:

"This should be called when a memory instruction is created that is being
used to replace an existing memory instruction."

If you wish to insert brand new accesses, it needs a new API.

I have a batch updater in my work queue that would do this for you, and
take care of the easy cases easily, and make the hard cases possible.

Until then, you have no real choice but to rebuild MemorySSA if you are
inserting brand new memory instructions.


[1] The only cases you can handle easily are insertion in the middle of a
block with stores above and below you, insertion at the end of a block with
a store above you, insertion at the beginning of a block with a store below
you.

IMHO, it's not worth making APIs for each of these, each with verification,
and it will expensive if you need MemorySSA correct at all times vs say
"can update it once per iteration of my optimization"
-------------- next part --------------
An HTML attachment was scrubbed...
URL:
<http://lists.llvm.org/pipermail/llvm-dev/attachments/20161030/67793f27/attachment.html>