[llvm-dev] [MemorySSA] inserting or removing memory instructions
Piotr Padlewski via llvm-dev
llvm-dev at lists.llvm.org
Sat Feb 18 16:05:35 PST 2017
Thanks for the reply. I still don't understand a couple of things.
Let's take a look at MemorySSATest.MoveAStore test.
The dump of MSSA looks like after each operation with my comments looks
like below. I also added question after each transformation:
; Just after constructing
define void @F(i8*) {
; 1 = MemoryDef(liveOnEntry)
store i8 16, i8* %0
br i1 true, label %2, label %3
; <label>:2: ; preds = %1
; 2 = MemoryDef(1)
store i8 16, i8* %0
br label %4
; <label>:3: ; preds = %1
br label %4
; <label>:4: ; preds = %3, %2
; 3 = MemoryPhi({%2,2},{%3,1})
; MemoryUse(3)
%5 = load i8, i8* %0
}
Everything is OK.
; Hoisting mem def 2.
define void @F(i8*) {
; 1 = MemoryDef(liveOnEntry)
store i8 16, i8* %0
; 2 = MemoryDef(1)
store i8 16, i8* %0
br i1 true, label %2, label %3
; <label>:2: ; preds = %1
br label %4
; <label>:3: ; preds = %1
br label %4
; <label>:4: ; preds = %3, %2
; 3 = MemoryPhi({%2,2},{%3,1})
; MemoryUse(3)
%5 = load i8, i8* %0
}
Why phi is still using 1 = MemoryDef? I would expect the phi to be
transformed to
3 = MemoryPhi({%2,2},{%3,2})
or even removed.
; After calling MSSA.createMemoryAccessAfter(SideStore, EntryStoreAccess,
EntryStoreAccess);
define void @F(i8*) {
; 1 = MemoryDef(liveOnEntry)
store i8 16, i8* %0
; 4 = MemoryDef(1)
store i8 16, i8* %0
br i1 true, label %2, label %3
; <label>:2: ; preds = %1
br label %4
; <label>:3: ; preds = %1
br label %4
; <label>:4: ; preds = %3, %2
; 3 = MemoryPhi({%2,2},{%3,1})
; MemoryUse(3)
%5 = load i8, i8* %0
}
If createMemoryAccessAfter didn't remove 2 = MemoryDef, then where it is?
Is it still somewhere in MSSA, and dump just don't print it?
; After calling EntryStoreAccess->replaceAllUsesWith(NewStoreAccess);
define void @F(i8*) {
; 1 = MemoryDef(liveOnEntry)
store i8 16, i8* %0
; 4 = MemoryDef(4)
store i8 16, i8* %0
br i1 true, label %2, label %3
; <label>:2: ; preds = %1
br label %4
; <label>:3: ; preds = %1
br label %4
; <label>:4: ; preds = %3, %2
; 3 = MemoryPhi({%2,2},{%3,4})
; MemoryUse(3)
%5 = load i8, i8* %0
}
4 = MemoryDef(4) looks very suspisious..
; After calling MSSA.removeMemoryAccess(SideStoreAccess);
define void @F(i8*) {
; 1 = MemoryDef(liveOnEntry)
store i8 16, i8* %0
; 4 = MemoryDef(4)
store i8 16, i8* %0
br i1 true, label %2, label %3
; <label>:2: ; preds = %1
br label %4
; <label>:3: ; preds = %1
br label %4
; <label>:4: ; preds = %3, %2
; 3 = MemoryPhi({%2,4},{%3,4})
; MemoryUse(3)
%5 = load i8, i8* %0
}
There is also very similar test - MoveAStoreUpdater and
MoveAStoreUpdaterMove, that uses updater - instead
produce exactly what I would expect at the end:
define void @F(i8*) {
; 1 = MemoryDef(liveOnEntry)
store i8 16, i8* %0
; 4 = MemoryDef(4)
store i8 16, i8* %0
br i1 true, label %2, label %3
; <label>:2: ; preds = %1
br label %4
; <label>:3: ; preds = %1
br label %4
; <label>:4: ; preds = %3, %2
; 3 = MemoryPhi({%2,4},{%3,4})
; MemoryUse(3)
%5 = load i8, i8* %0
}
This seems a little counter-intuitive that there exist another class that
is doing updates better than MemorySSA, and that the functions from
memoryssa are public (which resulted in my confusion on what
the methods are doing). Is it because for some cases, the updating API that
mssa provides is sufficient (and faster?)? Do you have some plans or ideas
how we could make it easier to use?
The other topic is that I am trying to come up with the updater for
instruction using !invariant.group, and I have no idea how much the
updating in MSSA should do and how much MemorySSAUpdater should fix.
There is also another problem that I am not sure if I should fix, because I
don't see O(1) solution for it.
For code:
store 42, %p, !invariant.group !0
store 42, %p, !invariant.group !0
store 42, %p, !invariant.group !0
store 42, %p, !invariant.group !0
store 42, %p, !invariant.group !0
load %p, !invarian.group !0
; The same maybe in different blocks
load %p, !invarian.group !0
load %p, !invarian.group !0
I would expect to have all loads uses the first store. Then if I would
start removing stores starting from the top I have to update all the uses
all
over again, which is O(#uses). It is probably something that could be
solved with the disjoint set data structure, but it gets more complicated
if I can't replace all uses with another def
(because they diverge), so I would have to find the first memoryDef that
dominates all the invariant.group uses in given path, or use the closest
non-invariant.group def if it doesn't exist, like here:
define void @hard(i8* %p) {
; 1 = MemoryDef(liveOnEntry)
store i8 42, i8* %p, !invariant.group !0
; 2 = MemoryDef(1)
call void @clobber8(i8* %p)
br i1 undef, label %b1, label %b2
b1: ; preds = %0
; 3 = MemoryDef(2)
store i8 42, i8* %p, !invariant.group !0
; MemoryUse(1)
%1 = load i8, i8* %p, !invariant.group !0
br label %b3
b2: ; preds = %0
; MemoryUse(1)
%2 = load i8, i8* %p, !invariant.group !0
br label %b3
b3: ; preds = %b2, %b1
; 5 = MemoryPhi({b1,3},{b2,2})
; MemoryUse(1)
%3 = load i8, i8* %p, !invariant.group !0
; 4 = MemoryDef(5)
store i8 42, i8* %p, !invariant.group !0
; MemoryUse(1)
%4 = load i8, i8* %p, !invariant.group !0
ret void
}
After removing the first instruction I would expect:
define void @hard(i8* %p) {
; 1 = MemoryDef(liveOnEntry)
call void @clobber8(i8* %p)
br i1 undef, label %b1, label %b2
b1: ; preds = %0
; 2 = MemoryDef(1)
store i8 42, i8* %p, !invariant.group !0
; MemoryUse(2)
%1 = load i8, i8* %p, !invariant.group !0
br label %b3
b2: ; preds = %0
; MemoryUse(1)
%2 = load i8, i8* %p, !invariant.group !0
br label %b3
b3: ; preds = %b2, %b1
; 4 = MemoryPhi({b1,2},{b2,1})
; MemoryUse(4)
%3 = load i8, i8* %p, !invariant.group !0
; 3 = MemoryDef(4)
store i8 42, i8* %p, !invariant.group !0
; MemoryUse(4)
%4 = load i8, i8* %p, !invariant.group !0
ret void
}
Which requires %1, %2, %3 and %4 be updated with different defs.
Piotr
2017-02-17 22:56 GMT+01:00 Daniel Berlin <dberlin at dberlin.org>:
> In particular, if you want to add support, the right way to know what to
> rename is (off the top of my head)
>
> add a flag or something to have renamepass reset all uses it sees (you
> only have to change the uses, defs are all linked together and thus already
> fixed by the updater). Right now it only does that if they have no
> defining access.
>
> Make it skip blocks already in the visited set (the incomingval to pass to
> successors is the existing incoming val if getDefsList.rbegin() ==
> getDefsList.rend(), and getDefsList.rbegin() otherwise) to prevent
> duplicate work from the below:
>
> Now:
> call renamepass on the bb for the inserted def, using the defining access
> of the first def as the incoming val.
> call renamepass on the bb of each inserted phi (you can use a null
> incoming val since incoming val will become the phi)
>
> This should rename all of the affected uses.
>
>
>
>
> On Fri, Feb 17, 2017 at 1:37 PM, Daniel Berlin <dberlin at dberlin.org>
> wrote:
>
>>
>>
>> On Fri, Feb 17, 2017 at 1:19 PM, Piotr Padlewski <
>> piotr.padlewski at gmail.com> wrote:
>>
>>> Hi guys,
>>> a question about updating memory SSA:
>>> Is it expected that e.g insertion of MemoryDef doesn't change all
>>> dominated uses?
>>>
>> At the moment, it is expected you are essentially just hoisting/sinking
>> them, not actually changing the aliasing.
>> The test does not obviously test this constraint, and is pretty contrived.
>> If you have a use case where we need to rename affected uses, i'm happy
>> to make it do that, it's trivial.
>>
>>
>>> For example test case CreateLoadsAndStoreUpdater produces:
>>>
>>> define void @F(i8*) {
>>> ; 1 = MemoryDef(liveOnEntry)
>>> store i8 16, i8* %0
>>> ; 4 = MemoryDef(1)
>>> store i8 16, i8* %0
>>> br i1 true, label %2, label %3
>>>
>>> ; <label>:2: ; preds = %1
>>> ; 2 = MemoryDef(4)
>>> store i8 16, i8* %0
>>> br label %4
>>>
>>> ; <label>:3: ; preds = %1
>>> br label %4
>>>
>>> ; <label>:4: ; preds = %3, %2
>>> ; 3 = MemoryPhi({%3,4},{%2,2})
>>> ; MemoryUse(3)
>>> %5 = load i8, i8* %0
>>> ; MemoryUse(1)
>>> %6 = load i8, i8* %0
>>> }
>>>
>>> What is the general behavior that I can expect when I insert or remove
>>> def/use?
>>>
>>
>> So far, it is built to replace all the hoist/sink/removal/etc cases.
>> It should work for all of those cases.
>>
>> For use insertion, it will always be correct.
>> For stores, It will even work if you sink a store to a branch.
>> It will produce wrong results if you insert new stores in the way of old
>> stores.
>>
>>
>> Another general question: what is the use of MemorySSAUpdater?
>>>
>>
>> To replace hand-written broken updating.
>>
>>> When should I use updater and when the MemorySSA API is sufficient?
>>>
>>
>> Unless you are just removing accesses, you should use the Updater.
>>
>> Due to the single-variable nature of memoryssa, there are tricky cases
>> that need to be handled.
>>
>>
>
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://lists.llvm.org/pipermail/llvm-dev/attachments/20170219/4bbe0b84/attachment.html>
More information about the llvm-dev
mailing list