<div dir="ltr"><br><div class="gmail_extra"><br><div class="gmail_quote">On Sat, Feb 18, 2017 at 4:05 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:0px 0px 0px 0.8ex;border-left:1px solid rgb(204,204,204);padding-left:1ex"><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></blockquote><div>This test doesn't use the updater?<br><br></div><div>This is the destructive test of trying to update it without the updater.</div><div> <br></div><blockquote class="gmail_quote" style="margin:0px 0px 0px 0.8ex;border-left:1px solid rgb(204,204,204);padding-left:1ex"><div dir="ltr"><div></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><span class="gmail-"><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></span><span class="gmail-"><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></span><div><font face="monospace, monospace">; 2 = MemoryDef(1)</font></div><span class="gmail-"><div><font face="monospace, monospace">  store i8 16, i8* %0</font></div></span><span class="gmail-"><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></span><div><font face="monospace, monospace">; 3 = MemoryPhi({%2,2},{%3,1})</font></div><span class="gmail-"><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></span><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><span class="gmail-"><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></span><div><font face="monospace, monospace">; 2 = MemoryDef(1)</font></div><span class="gmail-"><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></span><span class="gmail-"><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></span><div><font face="monospace, monospace">; 3 = MemoryPhi({%2,2},{%3,1})</font></div><span class="gmail-"><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></span><div>Why phi is still using 1 = MemoryDef?</div></div></div></blockquote><div><br></div><div>This is not an updater test.</div><div>This literally just moved it using the normal IR moving.</div><div>As you can see, it generates a broken thing in the middle state.</div><div><br></div><div> <br></div><blockquote class="gmail_quote" style="margin:0px 0px 0px 0.8ex;border-left:1px solid rgb(204,204,204);padding-left:1ex"><div dir="ltr"><div><div> 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></div></blockquote><div><br></div><div><br></div><div> </div><blockquote class="gmail_quote" style="margin:0px 0px 0px 0.8ex;border-left:1px solid rgb(204,204,204);padding-left:1ex"><div dir="ltr"><div><div><br></div><div><font face="monospace, monospace">; After calling MSSA.createMemoryAccessAfter(S<wbr>ideStore, EntryStoreAccess, EntryStoreAccess);</font></div><span class="gmail-"><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></span><span class="gmail-"><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></span><div><font face="monospace, monospace">; 3 = MemoryPhi({%2,2},{%3,1})</font></div><span class="gmail-"><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></span><div><font face="monospace, monospace">If createMemoryAccessAfter didn't remove 2 = MemoryDef, then where it is?</font></div></div></div></blockquote><div>This is why it says:<br>"  /// Note: If a MemoryAccess already exists for I, this function will make it</div><div>  /// inaccessible and it *must* have removeMemoryAccess called on it. "<br></div><div><br></div><blockquote class="gmail_quote" style="margin:0px 0px 0px 0.8ex;border-left:1px solid rgb(204,204,204);padding-left:1ex"><div dir="ltr"><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-><wbr>replaceAllUsesWith(<wbr>NewStoreAccess);</div><span class="gmail-"><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></span><div><font face="monospace, monospace">; 4 = MemoryDef(4)</font></div><span class="gmail-"><div><font face="monospace, monospace">  store i8 16, i8* %0</font></div></span><span class="gmail-"><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></span><span class="gmail-"><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></span><div><font face="monospace, monospace">; 3 = MemoryPhi({%2,2},{%3,4})</font></div><span class="gmail-"><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></span><div>4 = MemoryDef(4) looks very suspisious..</div></div></div></blockquote><div><br></div><div>And today we discover updating is hard without the updater ;)</div><div><br></div><div>Yes, it needs to reset the defining access after, but the destructive test is not doing that.</div><div> </div><blockquote class="gmail_quote" style="margin:0px 0px 0px 0.8ex;border-left:1px solid rgb(204,204,204);padding-left:1ex"><div dir="ltr"><div><div><br></div><div>;<font face="monospace, monospace"> After calling MSSA.<wbr>removeMemoryAccess(<wbr>SideStoreAccess);</font><br></div><span class="gmail-"><div>define void @F(i8*) {</div><div>; 1 = MemoryDef(liveOnEntry)</div><div>  store i8 16, i8* %0</div></span><div>; 4 = MemoryDef(4)</div><span class="gmail-"><div>  store i8 16, i8* %0</div></span><span class="gmail-"><div>  br i1 true, label %2, label %3</div><div><br></div><div>; <label>:2:                                      ; preds = %1</div></span><span class="gmail-"><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></span><div>; 3 = MemoryPhi({%2,4},{%3,4})</div><span class="gmail-"><div>; MemoryUse(3)</div><div>  %5 = load i8, i8* %0</div><div>}</div></span></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><span class="gmail-"><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></span><div><font face="monospace, monospace">; 4 = MemoryDef(4)</font></div><span class="gmail-"><div><font face="monospace, monospace">  store i8 16, i8* %0</font></div></span><span class="gmail-"><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></span><span class="gmail-"><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></span><div><font face="monospace, monospace">; 3 = MemoryPhi({%2,4},{%3,4})</font></div><span class="gmail-"><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></span></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).</div></div></blockquote><div><br></div><div>First, I was asked to split the updater into it's own class/file, so i did :)</div><div> We could add getUpdater to MemorySSA, and move all the functions there.</div><div>We probably should</div><div><br></div><div>ATM we have to have createMemory* available because the updater works on memory accesses, not instructions.</div><div>We could make it work on instructions but it's a bit trickier.</div><div>The main reason i did not start that way was because most things know where they are putting the new memory accesses, but we do not.</div><div>So, we'd have to locate the nearest memory access to the new instruction  in the block (IE a worst case O(n) walk in either direction, but mssa lookups) just to know where it's been placed.</div><div><br></div><div>The real intent is that people create the  memory access and then just hand it to the updater.</div><div><br></div><div>We could speed up the walk by turning what is currently the createMemoryAccess* into hints to the updater to know where to start the walk/where to go.</div><div> </div><blockquote class="gmail_quote" style="margin:0px 0px 0px 0.8ex;border-left:1px solid rgb(204,204,204);padding-left:1ex"><div dir="ltr"><div>Is it because for some cases, the updating API that mssa provides is sufficient (and faster?)? </div></div></blockquote><div><br></div><div>The removal case is the only sane case anymore,IMHO.</div><div><br></div><div>I think we should move the functions to the updater to start, and then slowly deprecate them.</div><div><br></div><blockquote class="gmail_quote" style="margin:0px 0px 0px 0.8ex;border-left:1px solid rgb(204,204,204);padding-left:1ex"><div dir="ltr"><div>Do you have some plans or ideas how we could make it easier to use?</div></div></blockquote><div><br></div><div>It's just the old way is too hard for people to use, and the new way is not fully adopted yet.</div><div> <br></div><blockquote class="gmail_quote" style="margin:0px 0px 0px 0.8ex;border-left:1px solid rgb(204,204,204);padding-left:1ex"><div dir="ltr"><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></blockquote><div><br></div><div>I'm not sure why invariant.group requires anything from MemorySSA updating, maybe you can explain?</div><div>The neither the updater or removal promise that uses will be optimized.</div><div>In fact, it resets optimized on uses.</div><div><br></div><div>The walker will properly fix up and reoptimize uses where they need it.</div><div><br></div><div><br></div><blockquote class="gmail_quote" style="margin:0px 0px 0px 0.8ex;border-left:1px solid rgb(204,204,204);padding-left:1ex"><div dir="ltr"><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. </div></div></blockquote><div>They will, assuming the optimizer did not hit any limits.</div><div> </div><blockquote class="gmail_quote" style="margin:0px 0px 0px 0.8ex;border-left:1px solid rgb(204,204,204);padding-left:1ex"><div dir="ltr"><div>Then if I would start removing stores starting from the top I have to update all the uses all</div><div>over again, </div></div></blockquote><div><br></div><div>This is why you would not remove them top down. Stores are removed in post-dom order, or you are insane :)</div><div><br></div><div>Yes, if you do this top-down, instead of bottom up, it's O(Instructions * Uses).</div><div><br></div><div>That's actually true of the opposite order for non-memory as well:</div><div>%1 = add 1, 1<br></div><div><div>%2 = add 1, 1</div><div><div>%3 = add  1, 1</div></div><div><div>%4 = add  1, 1</div></div><div><div>%5 = add  1, 1</div></div><div><br></div></div><div>use (%1)</div><div><div>use (%1)</div></div><div><div>use (%1)</div></div><div><div>use (%1)</div></div><div><div>use (%1)</div></div><div><div>use (%1)</div><div>use (%1)<br></div></div><div><br></div><div>If you are eliminating top-down using later-accesses  to say that earlier are dead (as you are suggesting):</div><div><br></div><div>You would do </div><div>%1->replaceAllUses(%2)</div><div>%1->erasefromParent()</div><div><div>%2->replaceAllUses(%3)</div></div><div>...</div><div><br></div><div>It has the same time bounds.</div><div><br></div><div> <br></div><blockquote class="gmail_quote" style="margin:0px 0px 0px 0.8ex;border-left:1px solid rgb(204,204,204);padding-left:1ex"><div dir="ltr"><div>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></blockquote><div><br></div><div><br></div><div> <br></div><blockquote class="gmail_quote" style="margin:0px 0px 0px 0.8ex;border-left:1px solid rgb(204,204,204);padding-left:1ex"><div dir="ltr"><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(5)</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(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>After removing the first instruction I would expect:</div></div></blockquote><div><br></div><div>Nope.</div><div>As mentioned, neither removal, nor the updater,  guarantees optimized uses.</div><div>The walker will reoptimize them and reset defining access as necessary.</div><div><br></div><div>Instead, all that will happen in your example, if you remove store 2, is that we will produce a conservatively correct answer:<br>We will repoint all uses that pointed at 2 at 2's defining access.</div><div><br></div><div>This is guaranteed to be a thing that dominates 2 (by the SSA property). It's also guaranteed not to be wrong.  Whatever uses reached 2 could not have aliased with anything in the way.</div><div>So the next thing it could possibly be aliased to is 2's defining access.</div><div><br></div><div>Thus, we will produce <br></div><blockquote class="gmail_quote" style="margin:0px 0px 0px 0.8ex;border-left:1px solid rgb(204,204,204);padding-left:1ex"><div dir="ltr"><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">; 3 = MemoryDef(1)</font></div></div></div></blockquote><div><br></div><div>Note you had reset the memorydef id of this to 2, which will never happen :)</div><div> </div><blockquote class="gmail_quote" style="margin:0px 0px 0px 0.8ex;border-left:1px solid rgb(204,204,204);padding-left:1ex"><div dir="ltr"><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">; 4 = MemoryPhi({b1,3},{b2,1})</font></div><div><font face="monospace, monospace">; MemoryUse(5)</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></blockquote><div><br></div><div><br></div><div>Again, we do not guarantee reoptimized uses at each intermediate point.</div><div>Doing so would be N^3 worst case.</div><div>Instead, we guarantee that when you call getClobberingMemoryAccess on a def or use, it gives you the most optimal answer.</div><div>As a side effect, it resets the definingaccess of the use (mainly so it doesn't waste time on the same links next time)</div><div><br></div><div>We used to guarantee the optimized property all the time in the underlying IR itself, but as you've discovered, it is hard invariant to maintain.</div><div><br></div><div>This does mean that *uses* of a store may include false-aliases that need to be disambiguated if you haven't called getMemoryAccess</div><div>But that's the price of admission ATM.</div><div>We'd need MemorySSI to solve that well.</div><div><br></div><div>Updating it fast otherwise basically requires some interesting linking.</div><div>IE what you really want, is, for each memory location or even each store, the stores to be linked in a way that looks like a dominator tree</div><div><br></div><div><a href="http://link.springer.com/chapter/10.1007/978-3-319-10936-7_13">http://link.springer.com/chapter/10.1007/978-3-319-10936-7_13</a></div><div><br></div><div>has a neat way to handle the storage and finding using quadtrees.</div><div> <br></div><div>But, Store optimizations are much less common than hoist ones for LLVM.</div><div>It's easy enough to teach those things to remove in the right order</div><div><br></div><div><br></div><div><br></div></div></div></div>