<div dir="ltr">For the curious<br><br>On clang as a bytecode file, just running mem2reg, basicaa, and gvn<div><br></div><div>Before we had:<br>    561 gvn             - Number of instructions PRE'd<br></div><div><br></div><div>After this patch we have:</div><div><br></div><div>   1517 gvn             - Number of instructions PRE'd<br></div><div><br></div></div><br><div class="gmail_quote">On Wed Jan 28 2015 at 3:15:20 PM Daniel Berlin <<a href="mailto:dberlin@dberlin.org">dberlin@dberlin.org</a>> wrote:<br><blockquote class="gmail_quote" style="margin:0 0 0 .8ex;border-left:1px #ccc solid;padding-left:1ex"><div dir="ltr">Current PRE tries to not increase code size.<div>It does this with a check whether or not the number of places it would have to insert is 1 or not.</div><div><br></div><div>The problem with this is that the answer could also be "we have to insert in zero places" in the case it's available in all predecessors.</div><div> :)</div><div><br></div><div>Normal dominator based elimination in GVN will not catch these cases because the branches do not dominate the merge point.</div><div><br></div><div>A simple example</div><div><span style="font-size:13.1999998092651px">int c;</span></div><div><div>int d;</div><div>int pre(int foo, int a, int b)</div><div>{</div><div><span style="font-size:13.1999998092651px">      int g;</span></div><div><span style="font-size:13.1999998092651px">      if (foo) {</span></div><div><span style="white-space:pre-wrap">        </span>  c = a+b;</div><div>      } <span style="font-size:13.1999998092651px">else </span><span style="font-size:13.1999998092651px">{</span></div><div><span style="white-space:pre-wrap">   </span>  d = a+ b;</div><div>      }</div><div><span style="white-space:pre-wrap">   </span>g = a+b;</div><div><span style="white-space:pre-wrap"> </span>return g;</div><div>}</div></div><div><br></div><div>Without this patch, PRE (and GVN) will not eliminate g = a+b.</div><div>With this patch, PRE will create phi(c, d) and eliminate g = a + b.</div><div><br></div><div>(It is tremendously more difficult to make current GVN understand the problem, and GCC solves this the same way i'm about to).</div><div><br></div><div>The patch looks large because of code movement, but it basically all boils down to changing this check:</div><div><br></div><div>if (NumWithout != 1 || NumWith == 0)</div><div><br></div><div>to</div><div>if (NumWithout > 1 || NumWith == 0)</div><div><br></div><div>and skipping insertion when NumWithout == 0</div><div><br></div><div>testcase included.</div><div><br></div></div></blockquote></div>