<div dir="ltr">Hey Dan,<div> The intent from the beginning was to use the NewGVN infrastructure to help do the numbering, partially inspired by your responses to the original Machine Outliner RFC (That is actually how this started to some degree), but the infrastructure wasn't quite ready when I started.</div><div><br></div><div>Thanks,</div><div> River Riddle</div><div><br></div><div><div class="gmail_extra"><div class="gmail_quote">On Thu, Sep 21, 2017 at 7:45 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"><div class="gmail_extra"><div class="gmail_quote"><span class=""><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"><span id="m_2098772277896481278gmail-m_2501191158221039965gmail-docs-internal-guid-a13201fd-543a-33e0-60b3-3e86acafde79"><p dir="ltr" style="line-height:1.38;margin-top:0pt;margin-bottom:0pt"><span style="font-size:11pt;font-family:"Times New Roman";color:rgb(0,0,0);background-color:transparent;vertical-align:baseline;white-space:pre-wrap"> </span></p><p dir="ltr" style="line-height:1.38;margin-top:0pt;margin-bottom:0pt"><span style="font-size:12pt;font-family:"Times New Roman";color:rgb(0,0,0);background-color:transparent;font-weight:700;vertical-align:baseline;white-space:pre-wrap">--- Algorithmic differences with the Machine Outliner ----</span></p><br><p dir="ltr" style="line-height:1.38;margin-top:0pt;margin-bottom:0pt"><span style="font-size:11pt;font-family:"Times New Roman";color:rgb(0,0,0);background-color:transparent;vertical-align:baseline;white-space:pre-wrap"> </span><span style="font-size:11pt;font-family:"Times New Roman";color:rgb(0,0,0);background-color:transparent;vertical-align:baseline;white-space:pre-wrap"><span class="m_2098772277896481278gmail-m_2501191158221039965gmail-Apple-tab-span" style="white-space:pre-wrap"> </span></span><span style="font-size:11pt;font-family:"Times New Roman";color:rgb(0,0,0);background-color:transparent;vertical-align:baseline;white-space:pre-wrap">There was a lot of confusion on how exactly the algorithm I am proposing differs from what is available in the Machine Outliner. The similarities of the two outliners lie in the usage of a string matching algorithm and candidate pruning. The first step in the algorithm is to basically do the same common substring / pruning algorithm the post-RA MO uses but with a specially chosen congruence relation. I’d like to delve into the differences between the two:</span></p><p dir="ltr" style="line-height:1.38;margin-top:0pt;margin-bottom:0pt"><span style="font-size:11pt;font-family:"Times New Roman";color:rgb(0,0,0);background-color:transparent;vertical-align:baseline;white-space:pre-wrap"> </span></p><p dir="ltr" style="line-height:1.38;margin-top:0pt;margin-bottom:0pt"><span style="font-size:11pt;font-family:"Times New Roman";color:rgb(0,0,0);background-color:transparent;font-weight:700;vertical-align:baseline;white-space:pre-wrap">Congruence Detection:</span></p><p dir="ltr" style="line-height:1.38;margin-top:0pt;margin-bottom:0pt"><span style="font-size:11pt;font-family:"Times New Roman";color:rgb(0,0,0);background-color:transparent;vertical-align:baseline;white-space:pre-wrap"> </span></p><p dir="ltr" style="line-height:1.38;margin-top:0pt;margin-bottom:0pt"><span style="font-size:11pt;font-family:"Times New Roman";color:rgb(0,0,0);background-color:transparent;vertical-align:baseline;white-space:pre-wrap">-</span><span style="font-size:7pt;font-family:"Times New Roman";color:rgb(0,0,0);background-color:transparent;vertical-align:baseline;white-space:pre-wrap"> </span><span style="font-size:11pt;font-family:"Times New Roman";color:rgb(0,0,0);background-color:transparent;vertical-align:baseline;white-space:pre-wrap">Machine Outliner</span></p><p dir="ltr" style="line-height:1.38;margin-top:0pt;margin-bottom:0pt"><span style="font-size:11pt;font-family:"Times New Roman";color:rgb(0,0,0);background-color:transparent;vertical-align:baseline;white-space:pre-wrap"> The machine outliner has the advantage of having this problem already taken care of by the register allocator, it simply checks to see if the two machine instructions are identical.</span></p><p dir="ltr" style="line-height:1.38;margin-top:0pt;margin-bottom:0pt"><span style="font-size:11pt;font-family:"Times New Roman";color:rgb(0,0,0);background-color:transparent;vertical-align:baseline;white-space:pre-wrap"> </span></p><p dir="ltr" style="line-height:1.38;margin-top:0pt;margin-bottom:0pt"><span style="font-size:11pt;font-family:"Times New Roman";color:rgb(0,0,0);background-color:transparent;vertical-align:baseline;white-space:pre-wrap">-</span><span style="font-size:7pt;font-family:"Times New Roman";color:rgb(0,0,0);background-color:transparent;vertical-align:baseline;white-space:pre-wrap"> </span><span style="font-size:11pt;font-family:"Times New Roman";color:rgb(0,0,0);background-color:transparent;vertical-align:baseline;white-space:pre-wrap">IR Outliner</span></p><p dir="ltr" style="line-height:1.38;margin-top:0pt;margin-bottom:0pt"><span style="font-size:11pt;font-family:"Times New Roman";color:rgb(0,0,0);background-color:transparent;vertical-align:baseline;white-space:pre-wrap"> In the IR outliner we work on semantic equivalence, i.e. we care the operations being performed are equivalent and not the values. This creates a need to add verification that we do have exact equivalence when we need it, e.g. ShuffleVector’s shuffle mask, not taking the address of InlineASM, etc.</span></p><p dir="ltr" style="line-height:1.38;margin-top:0pt;margin-bottom:0pt"><span style="font-size:11pt;font-family:"Times New Roman";color:rgb(0,0,0);background-color:transparent;vertical-align:baseline;white-space:pre-wrap"> </span></p><p dir="ltr" style="line-height:1.38;margin-top:0pt;margin-bottom:0pt"><span style="font-size:11pt;font-family:"Times New Roman";color:rgb(0,0,0);background-color:transparent;vertical-align:baseline;white-space:pre-wrap">A quick example of semantic equivalence:</span></p><p dir="ltr" style="line-height:1.38;margin-top:0pt;margin-bottom:0pt"><span style="font-size:11pt;font-family:"Times New Roman";color:rgb(0,0,0);background-color:transparent;vertical-align:baseline;white-space:pre-wrap">%1 = add i32 1, i32 2</span></p><p dir="ltr" style="line-height:1.38;margin-top:0pt;margin-bottom:0pt"><span style="font-size:11pt;font-family:"Times New Roman";color:rgb(0,0,0);background-color:transparent;vertical-align:baseline;white-space:pre-wrap">%2 = add i32 2, i32 3</span></p><p dir="ltr" style="line-height:1.38;margin-top:0pt;margin-bottom:0pt"><span style="font-size:11pt;font-family:"Times New Roman";color:rgb(0,0,0);background-color:transparent;vertical-align:baseline;white-space:pre-wrap"> </span></p><p dir="ltr" style="line-height:1.38;margin-top:0pt;margin-bottom:0pt"><span style="font-size:11pt;font-family:"Times New Roman";color:rgb(0,0,0);background-color:transparent;vertical-align:baseline;white-space:pre-wrap">These two instructions are not identical because the values of the operands are not identical. They are, however, semantically equivalent because they both perform the add operation.</span></p><p dir="ltr" style="line-height:1.38;margin-top:0pt;margin-bottom:0pt"><span style="font-size:11pt;font-family:"Times New Roman";color:rgb(0,0,0);background-color:transparent;vertical-align:baseline;white-space:pre-wrap">This can be seen by simply removing the operand values used in the calculations:</span></p><p dir="ltr" style="line-height:1.38;margin-top:0pt;margin-bottom:0pt"><span style="font-size:11pt;font-family:"Times New Roman";color:rgb(0,0,0);background-color:transparent;vertical-align:baseline;white-space:pre-wrap">%1 = add i32 , i32</span></p><p dir="ltr" style="line-height:1.38;margin-top:0pt;margin-bottom:0pt"><span style="font-size:11pt;font-family:"Times New Roman";color:rgb(0,0,0);background-color:transparent;vertical-align:baseline;white-space:pre-wrap">%2 = add i32 , i32</span></p><p dir="ltr" style="line-height:1.38;margin-top:0pt;margin-bottom:0pt"><span style="font-size:11pt;font-family:"Times New Roman";color:rgb(0,0,0);background-color:transparent;vertical-align:baseline;white-space:pre-wrap"> <br></span></p></span></div></blockquote></span><div>FWIW, you could use the core NewGVN structures (GVNExpression.h) to do this and just not fill in the operands.</div><div>GVNSink does a variant of this by using them.</div><div>In particular, the variant it does is: "do these instructions contribute to their uses in an equivalent way". This is the same problem, but if you weren't going to be willing to add any function arguments to fill in operand values.</div><div><br></div><div><br></div><div>IE</div><div><div><br></div><div>/// [ %a1 = add i32 %b, 1 ] [ %c1 = add i32 %d, 1 ]</div><div>/// [ %a2 = xor i32 %a1, 1 ] [ %c2 = xor i32 %c1, 1 ]</div><div>/// \ /</div><div>/// [ %e = phi i32 %a2, %c2 ]</div><div>/// [ add i32 %e, 4 ]</div></div><div><br></div><div><br></div><div>These would value number differently using a normal value numbering algorithm.</div><div>GVNSink instead computes "could i common a1 and c1, could i do that by adding a phi".</div><div><br></div><div><br></div><div>(Though i realize now the computation it performs can now be performed in a single pass. It's just the reverse of what we do in NewGVN. We look for things we can convert into phi of ops, it looks for things it can convert into op of phis to save instructions)</div><div><br></div></div></div></div>
</blockquote></div><br></div></div></div>