<div dir="ltr">As a general rule of thumb, if it only removes scalar code, it's pretty useless.<div>If it helps it prove it can remove memory operations, it's great.<br></div><div><br></div><div>Often, in your example, it's accesses that are loop invariant but common to other accesses in the loop that are most promising.</div><div><br></div><div>IE (taken from a test i wrote for GCC's VN)</div><div><div>int vnum_test8(int *data)</div><div>{</div><div> int i;</div><div> int stop = data[3];</div><div> int m = data[4];</div><div> int n = m;</div><div> int p;</div><div> for (i=0; i<stop; i++) {</div><div> int k = data[2];</div><div> data[k] = 2;</div><div> data[0] = m - n;</div><div> k = data[1];</div><div> m = m + k;</div><div> n = n + k;</div><div> p = data[0];</div><div> }</div><div> return p;</div><div>}</div></div><div><br></div><div>We test that we eliminate m-n in favor of 0, replace n with m, and set p to 0</div><div><br></div><div><br></div><div>Note that this requires proving a bunch of things about the memory accesses here, and properly value numbering memory accesses (which current GVN will not do).</div><div><br></div></div><div class="gmail_extra"><br><div class="gmail_quote">On Tue, May 3, 2016 at 7:42 PM, Amos Robinson <span dir="ltr"><<a href="mailto:amos.robinson@gmail.com" target="_blank">amos.robinson@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"><span class=""><div>> <span style="line-height:1.5">The GVN on the newgvn branch i have will remove these, and is more complicated</span></div></span><span class=""><div><span style="line-height:1.5">> </span><span style="line-height:1.5">The one i have implemented unifies AWZ and hash based and will also do predication/value inference.</span></div><div><span style="line-height:1.5"><br></span></div></span><div><span style="line-height:1.5">This is exciting news. It sounds like it will find a lot of the interesting cases.</span><br></div><span class=""><div><br></div><div>> Note that we don't do full-on polynomial time equivalence finding. While it would be fun to play with such algorithms, they are often not practical.</div><div><br></div></span><div>Yes, fair enough. I thought that might be the case. A lot of the examples in the papers seem a bit contrived anyway, so it would be interesting to know just how many "real" opportunities are being missed.</div><span class=""><div><br></div>> <span style="line-height:1.5">The one i saw some hope for was </span><a href="http://link.springer.com/chapter/10.1007%2F978-3-540-76637-7_22" style="line-height:1.5" target="_blank">http://link.springer.com/chapter/10.1007%2F978-3-540-76637-7_22</a><div>> I haven't had a chance to play with it.</div><div><br></div></span><div>This looks very promising, thank you.</div><div><br></div><div><br></div></div><div class="HOEnZb"><div class="h5"><br><div class="gmail_quote"><div dir="ltr">On Wed, 4 May 2016 at 11:01 Daniel Berlin <<a href="mailto:dberlin@dberlin.org" target="_blank">dberlin@dberlin.org</a>> wrote:<br></div><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"><blockquote class="gmail_quote" style="margin:0 0 0 .8ex;border-left:1px #ccc solid;padding-left:1ex"><div><div style="font-family:arial,helvetica,sans-serif;font-size:10pt;color:#000000"><br>If I recall correctly, AWZ will get this too (<a href="https://courses.cs.washington.edu/courses/cse501/04wi/papers/alpern-popl88.pdf" target="_blank">https://courses.cs.washington.edu/courses/cse501/04wi/papers/alpern-popl88.pdf</a>). AWZ is a Hopcroft-partitioning-based algorithm, and Hopcroft partitioning is O(n*log(n)).<br><blockquote style="border-left:2px solid rgb(16,16,255);margin-left:5px;padding-left:5px;color:rgb(0,0,0);font-weight:normal;font-style:normal;text-decoration:none;font-family:Helvetica,Arial,sans-serif;font-size:12pt"><div dir="ltr"><div class="gmail_extra"></div></div></blockquote></div></div></blockquote></div></div></div><div dir="ltr"><div class="gmail_extra"><div class="gmail_quote"><div>Yes, AWZ will get some, and the hash based ones will get some different ones.</div><div><br></div><div>The one i have implemented unifies AWZ and hash based and will also do predication/value inference.</div><div><br></div><div><br></div></div></div></div>
</blockquote></div>
</div></div></blockquote></div><br></div>