<div dir="ltr">Thanks for the reply. I still don't understand a couple of things.<div>Let's take a look at MemorySSATest.MoveAStore test.</div><div><br></div><div>The dump of MSSA looks like after each operation with my comments looks like below. I also added question after each transformation:</div><div><br></div><div>; Just after constructing</div><div><div><font face="monospace, monospace">define void @F(i8*) {</font></div><div><font face="monospace, monospace">; 1 = MemoryDef(liveOnEntry)</font></div><div><font face="monospace, monospace"> store i8 16, i8* %0</font></div><div><font face="monospace, monospace"> br i1 true, label %2, label %3</font></div><div><font face="monospace, monospace"><br></font></div><div><font face="monospace, monospace">; <label>:2: ; preds = %1</font></div><div><font face="monospace, monospace">; 2 = MemoryDef(1)</font></div><div><font face="monospace, monospace"> store i8 16, i8* %0</font></div><div><font face="monospace, monospace"> br label %4</font></div><div><font face="monospace, monospace"><br></font></div><div><font face="monospace, monospace">; <label>:3: ; preds = %1</font></div><div><font face="monospace, monospace"> br label %4</font></div><div><font face="monospace, monospace"><br></font></div><div><font face="monospace, monospace">; <label>:4: ; preds = %3, %2</font></div><div><font face="monospace, monospace">; 3 = MemoryPhi({%2,2},{%3,1})</font></div><div><font face="monospace, monospace">; MemoryUse(3)</font></div><div><font face="monospace, monospace"> %5 = load i8, i8* %0</font></div><div><font face="monospace, monospace">}</font></div><div><font face="monospace, monospace">Ev</font>erything is OK.</div><div><br></div><div><font face="monospace, monospace">; Hoisting mem def 2.</font></div><div><font face="monospace, monospace">define void @F(i8*) {</font></div><div><font face="monospace, monospace">; 1 = MemoryDef(liveOnEntry)</font></div><div><font face="monospace, monospace"> store i8 16, i8* %0</font></div><div><font face="monospace, monospace">; 2 = MemoryDef(1)</font></div><div><font face="monospace, monospace"> store i8 16, i8* %0</font></div><div><font face="monospace, monospace"> br i1 true, label %2, label %3</font></div><div><font face="monospace, monospace"><br></font></div><div><font face="monospace, monospace">; <label>:2: ; preds = %1</font></div><div><font face="monospace, monospace"> br label %4</font></div><div><font face="monospace, monospace"><br></font></div><div><font face="monospace, monospace">; <label>:3: ; preds = %1</font></div><div><font face="monospace, monospace"> br label %4</font></div><div><font face="monospace, monospace"><br></font></div><div><font face="monospace, monospace">; <label>:4: ; preds = %3, %2</font></div><div><font face="monospace, monospace">; 3 = MemoryPhi({%2,2},{%3,1})</font></div><div><font face="monospace, monospace">; MemoryUse(3)</font></div><div><font face="monospace, monospace"> %5 = load i8, i8* %0</font></div><div><font face="monospace, monospace">}</font></div><div>Why phi is still using 1 = MemoryDef? I would expect the phi to be transformed to</div><div><font face="monospace, monospace">3 = MemoryPhi({%2,2},{%3,2})</font><br></div><div><font face="arial, helvetica, sans-serif">or even removed.</font></div><div><br></div><div><font face="monospace, monospace">; After calling MSSA.createMemoryAccessAfter(<wbr>SideStore, EntryStoreAccess, EntryStoreAccess);</font></div><div><font face="monospace, monospace">define void @F(i8*) {</font></div><div><font face="monospace, monospace">; 1 = MemoryDef(liveOnEntry)</font></div><div><font face="monospace, monospace"> store i8 16, i8* %0</font></div><div><font face="monospace, monospace">; 4 = MemoryDef(1)</font></div><div><font face="monospace, monospace"> store i8 16, i8* %0</font></div><div><font face="monospace, monospace"> br i1 true, label %2, label %3</font></div><div><font face="monospace, monospace"><br></font></div><div><font face="monospace, monospace">; <label>:2: ; preds = %1</font></div><div><font face="monospace, monospace"> br label %4</font></div><div><font face="monospace, monospace"><br></font></div><div><font face="monospace, monospace">; <label>:3: ; preds = %1</font></div><div><font face="monospace, monospace"> br label %4</font></div><div><font face="monospace, monospace"><br></font></div><div><font face="monospace, monospace">; <label>:4: ; preds = %3, %2</font></div><div><font face="monospace, monospace">; 3 = MemoryPhi({%2,2},{%3,1})</font></div><div><font face="monospace, monospace">; MemoryUse(3)</font></div><div><font face="monospace, monospace"> %5 = load i8, i8* %0</font></div><div><font face="monospace, monospace">}</font></div><div><font face="monospace, monospace">If createMemoryAccessAfter didn't remove 2 = MemoryDef, then where it is?</font></div><div><font face="monospace, monospace">Is it still somewhere in MSSA, and dump just don't print it?</font></div><div><font face="monospace, monospace"><br></font></div><div>; After calling EntryStoreAccess->replaceAllUsesWith(NewStoreAccess);</div><div><font face="monospace, monospace">define void @F(i8*) {</font></div><div><font face="monospace, monospace">; 1 = MemoryDef(liveOnEntry)</font></div><div><font face="monospace, monospace"> store i8 16, i8* %0</font></div><div><font face="monospace, monospace">; 4 = MemoryDef(4)</font></div><div><font face="monospace, monospace"> store i8 16, i8* %0</font></div><div><font face="monospace, monospace"> br i1 true, label %2, label %3</font></div><div><font face="monospace, monospace"><br></font></div><div><font face="monospace, monospace">; <label>:2: ; preds = %1</font></div><div><font face="monospace, monospace"> br label %4</font></div><div><font face="monospace, monospace"><br></font></div><div><font face="monospace, monospace">; <label>:3: ; preds = %1</font></div><div><font face="monospace, monospace"> br label %4</font></div><div><font face="monospace, monospace"><br></font></div><div><font face="monospace, monospace">; <label>:4: ; preds = %3, %2</font></div><div><font face="monospace, monospace">; 3 = MemoryPhi({%2,2},{%3,4})</font></div><div><font face="monospace, monospace">; MemoryUse(3)</font></div><div><font face="monospace, monospace"> %5 = load i8, i8* %0</font></div><div><font face="monospace, monospace">}</font></div><div>4 = MemoryDef(4) looks very suspisious..</div><div><br></div><div>;<font face="monospace, monospace"> After calling MSSA.removeMemoryAccess(SideStoreAccess);</font><br></div><div>define void @F(i8*) {</div><div>; 1 = MemoryDef(liveOnEntry)</div><div> store i8 16, i8* %0</div><div>; 4 = MemoryDef(4)</div><div> store i8 16, i8* %0</div><div> br i1 true, label %2, label %3</div><div><br></div><div>; <label>:2: ; preds = %1</div><div> br label %4</div><div><br></div><div>; <label>:3: ; preds = %1</div><div> br label %4</div><div><br></div><div>; <label>:4: ; preds = %3, %2</div><div>; 3 = MemoryPhi({%2,4},{%3,4})</div><div>; MemoryUse(3)</div><div> %5 = load i8, i8* %0</div><div>}</div></div><div><br></div><div><br></div><div>There is also very similar test - MoveAStoreUpdater and MoveAStoreUpdaterMove, that uses updater - instead</div><div>produce exactly what I would expect at the end:</div><div><br></div><div><div><font face="monospace, monospace">define void @F(i8*) {</font></div><div><font face="monospace, monospace">; 1 = MemoryDef(liveOnEntry)</font></div><div><font face="monospace, monospace"> store i8 16, i8* %0</font></div><div><font face="monospace, monospace">; 4 = MemoryDef(4)</font></div><div><font face="monospace, monospace"> store i8 16, i8* %0</font></div><div><font face="monospace, monospace"> br i1 true, label %2, label %3</font></div><div><font face="monospace, monospace"><br></font></div><div><font face="monospace, monospace">; <label>:2: ; preds = %1</font></div><div><font face="monospace, monospace"> br label %4</font></div><div><font face="monospace, monospace"><br></font></div><div><font face="monospace, monospace">; <label>:3: ; preds = %1</font></div><div><font face="monospace, monospace"> br label %4</font></div><div><font face="monospace, monospace"><br></font></div><div><font face="monospace, monospace">; <label>:4: ; preds = %3, %2</font></div><div><font face="monospace, monospace">; 3 = MemoryPhi({%2,4},{%3,4})</font></div><div><font face="monospace, monospace">; MemoryUse(3)</font></div><div><font face="monospace, monospace"> %5 = load i8, i8* %0</font></div><div><font face="monospace, monospace">}</font></div></div><div><br></div><div>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 </div><div>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?</div><div><br></div><div>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.</div><div>There is also another problem that I am not sure if I should fix, because I don't see O(1) solution for it.</div><div><br></div><div>For code:</div><div><br></div><div>store 42, %p, !invariant.group !0</div><div><div>store 42, %p, !invariant.group !0</div></div><div><div>store 42, %p, !invariant.group !0</div></div><div><div>store 42, %p, !invariant.group !0</div></div><div><div>store 42, %p, !invariant.group !0</div></div><div><br></div><div>load %p, !invarian.group !0</div><div>; The same maybe in different blocks<br></div><div>load %p, !invarian.group !0</div><div>load %p, !invarian.group !0</div><div><br></div><div>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</div><div>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</div><div>(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:</div><div><br></div><div><div><font face="monospace, monospace">define void @hard(i8* %p) {</font></div><div><font face="monospace, monospace">; 1 = MemoryDef(liveOnEntry)</font></div><div><font face="monospace, monospace"> store i8 42, i8* %p, !invariant.group !0</font></div><div><font face="monospace, monospace">; 2 = MemoryDef(1)</font></div><div><font face="monospace, monospace"> call void @clobber8(i8* %p)</font></div><div><font face="monospace, monospace"> br i1 undef, label %b1, label %b2</font></div><div><font face="monospace, monospace"><br></font></div><div><font face="monospace, monospace">b1: ; preds = %0</font></div><div><font face="monospace, monospace">; 3 = MemoryDef(2)</font></div><div><font face="monospace, monospace"> store i8 42, i8* %p, !invariant.group !0</font></div><div><font face="monospace, monospace">; MemoryUse(1)</font></div><div><font face="monospace, monospace"> %1 = load i8, i8* %p, !invariant.group !0</font></div><div><font face="monospace, monospace"> br label %b3</font></div><div><font face="monospace, monospace"><br></font></div><div><font face="monospace, monospace">b2: ; preds = %0</font></div><div><font face="monospace, monospace">; MemoryUse(1)</font></div><div><font face="monospace, monospace"> %2 = load i8, i8* %p, !invariant.group !0</font></div><div><font face="monospace, monospace"> br label %b3</font></div><div><font face="monospace, monospace"><br></font></div><div><font face="monospace, monospace">b3: ; preds = %b2, %b1</font></div><div><font face="monospace, monospace">; 5 = MemoryPhi({b1,3},{b2,2})</font></div><div><font face="monospace, monospace">; MemoryUse(1)</font></div><div><font face="monospace, monospace"> %3 = load i8, i8* %p, !invariant.group !0</font></div><div><font face="monospace, monospace">; 4 = MemoryDef(5)</font></div><div><font face="monospace, monospace"> store i8 42, i8* %p, !invariant.group !0</font></div><div><font face="monospace, monospace">; MemoryUse(1)</font></div><div><font face="monospace, monospace"> %4 = load i8, i8* %p, !invariant.group !0</font></div><div><font face="monospace, monospace"> ret void</font></div><div><font face="monospace, monospace">}</font></div></div><div><br></div><div>After removing the first instruction I would expect:</div><div><br></div><div><div><font face="monospace, monospace">define void @hard(i8* %p) {</font></div><div><font face="monospace, monospace">; 1 = MemoryDef(liveOnEntry)</font></div><div><font face="monospace, monospace"> call void @clobber8(i8* %p)</font></div><div><font face="monospace, monospace"> br i1 undef, label %b1, label %b2</font></div><div><font face="monospace, monospace"><br></font></div><div><font face="monospace, monospace">b1: ; preds = %0</font></div><div><font face="monospace, monospace">; 2 = MemoryDef(1)</font></div><div><font face="monospace, monospace"> store i8 42, i8* %p, !invariant.group !0</font></div><div><font face="monospace, monospace">; MemoryUse(2)</font></div><div><font face="monospace, monospace"> %1 = load i8, i8* %p, !invariant.group !0</font></div><div><font face="monospace, monospace"> br label %b3</font></div><div><font face="monospace, monospace"><br></font></div><div><font face="monospace, monospace">b2: ; preds = %0</font></div><div><font face="monospace, monospace">; MemoryUse(1)</font></div><div><font face="monospace, monospace"> %2 = load i8, i8* %p, !invariant.group !0</font></div><div><font face="monospace, monospace"> br label %b3</font></div><div><font face="monospace, monospace"><br></font></div><div><font face="monospace, monospace">b3: ; preds = %b2, %b1</font></div><div><font face="monospace, monospace">; 4 = MemoryPhi({b1,2},{b2,1})</font></div><div><font face="monospace, monospace">; MemoryUse(4)</font></div><div><font face="monospace, monospace"> %3 = load i8, i8* %p, !invariant.group !0</font></div><div><font face="monospace, monospace">; 3 = MemoryDef(4)</font></div><div><font face="monospace, monospace"> store i8 42, i8* %p, !invariant.group !0</font></div><div><font face="monospace, monospace">; MemoryUse(4)</font></div><div><font face="monospace, monospace"> %4 = load i8, i8* %p, !invariant.group !0</font></div><div><font face="monospace, monospace"> ret void</font></div><div><font face="monospace, monospace">}</font></div></div><div><br></div><div>Which requires %1, %2, %3 and %4 be updated with different defs.</div><div><br></div><div><br></div><div>Piotr<br><div><br></div></div></div><div class="gmail_extra"><br><div class="gmail_quote">2017-02-17 22:56 GMT+01:00 Daniel Berlin <span dir="ltr"><<a href="mailto:dberlin@dberlin.org" target="_blank">dberlin@dberlin.org</a>></span>:<br><blockquote class="gmail_quote" style="margin:0 0 0 .8ex;border-left:1px #ccc solid;padding-left:1ex"><div dir="ltr">In particular, if you want to add support, the right way to know what to rename is (off the top of my head)<div><br></div><div>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.</div><div><br></div><div>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:</div><div><br></div><div>Now:</div><div> call renamepass on the bb for the inserted def, using the defining access of the first def as the incoming val.</div><div>call renamepass on the bb of each inserted phi (you can use a null incoming val since incoming val will become the phi)</div><div><br></div><div>This should rename all of the affected uses.</div><div><br></div><div> <br></div><div><br></div></div><div class="HOEnZb"><div class="h5"><div class="gmail_extra"><br><div class="gmail_quote">On Fri, Feb 17, 2017 at 1:37 PM, Daniel Berlin <span dir="ltr"><<a href="mailto:dberlin@dberlin.org" target="_blank">dberlin@dberlin.org</a>></span> wrote:<br><blockquote class="gmail_quote" style="margin:0 0 0 .8ex;border-left:1px #ccc solid;padding-left:1ex"><div dir="ltr"><br><div class="gmail_extra"><br><div class="gmail_quote"><span>On Fri, Feb 17, 2017 at 1:19 PM, Piotr Padlewski <span dir="ltr"><<a href="mailto:piotr.padlewski@gmail.com" target="_blank">piotr.padlewski@gmail.com</a>></span> wrote:<br><blockquote class="gmail_quote" style="margin:0 0 0 .8ex;border-left:1px #ccc solid;padding-left:1ex"><div dir="ltr">Hi guys,<div>a question about updating memory SSA:</div><div>Is it expected that e.g insertion of MemoryDef doesn't change all dominated uses?</div></div></blockquote></span><div>At the moment, it is expected you are essentially just hoisting/sinking them, not actually changing the aliasing.</div><div>The test does not obviously test this constraint, and is pretty contrived.</div><div>If you have a use case where we need to rename affected uses, i'm happy to make it do that, it's trivial.</div><span><div> </div><blockquote class="gmail_quote" style="margin:0 0 0 .8ex;border-left:1px #ccc solid;padding-left:1ex"><div dir="ltr"><div>For example test case CreateLoadsAndStoreUpdate<wbr>r produces:</div><div><br></div><div><div>define void @F(i8*) {</div><div>; 1 = MemoryDef(liveOnEntry)</div><div> store i8 16, i8* %0</div><div>; 4 = MemoryDef(1)</div><div> store i8 16, i8* %0</div><div> br i1 true, label %2, label %3</div><div><br></div><div>; <label>:2: ; preds = %1</div><div>; 2 = MemoryDef(4)</div><div> store i8 16, i8* %0</div><div> br label %4</div><div><br></div><div>; <label>:3: ; preds = %1</div><div> br label %4</div><div><br></div><div>; <label>:4: ; preds = %3, %2</div><div>; 3 = MemoryPhi({%3,4},{%2,2})</div><div>; MemoryUse(3)</div><div> %5 = load i8, i8* %0</div><div>; MemoryUse(1)</div><div> %6 = load i8, i8* %0</div><div>}</div></div><div><br></div><div>What is the general behavior that I can expect when I insert or remove def/use?</div></div></blockquote><div><br></div></span><div>So far, it is built to replace all the hoist/sink/removal/etc cases.</div><div>It should work for all of those cases.</div><div><br></div><div>For use insertion, it will always be correct.</div><div>For stores, It will even work if you sink a store to a branch.</div><div>It will produce wrong results if you insert new stores in the way of old stores.</div><span><div><br></div><div><br></div><blockquote class="gmail_quote" style="margin:0 0 0 .8ex;border-left:1px #ccc solid;padding-left:1ex"><div dir="ltr"><div>Another general question: what is the use of MemorySSAUpdater? </div></div></blockquote><div><br></div></span><div>To replace hand-written broken updating.</div><span><blockquote class="gmail_quote" style="margin:0 0 0 .8ex;border-left:1px #ccc solid;padding-left:1ex"><div dir="ltr"><div>When should I use updater and when the MemorySSA API is sufficient? </div></div></blockquote><div><br></div></span><div>Unless you are just removing accesses, you should use the Updater.</div><div><br></div><div>Due to the single-variable nature of memoryssa, there are tricky cases that need to be handled.</div><div><br></div></div></div></div>
</blockquote></div><br></div>
</div></div></blockquote></div><br></div>