<div dir="ltr"><br><div class="gmail_extra"><br><div class="gmail_quote">On Tue, May 3, 2016 at 5:25 PM, Amos Robinson via llvm-dev <span dir="ltr"><<a href="mailto:llvm-dev@lists.llvm.org" target="_blank">llvm-dev@lists.llvm.org</a>></span> wrote:<br><blockquote class="gmail_quote" style="margin:0px 0px 0px 0.8ex;border-left-width:1px;border-left-style:solid;border-left-color:rgb(204,204,204);padding-left:1ex"><div dir="ltr">Hello,<div>I was hoping to get some clarification on the aim of the GVN pass. I have been reading a bit about global value numbering, and from what I understand, there are polynomial time algorithms for removing duplicate computations from loops[1].</div></div></blockquote><div>Yes</div><div><br></div><div>The current GVN will not do it.</div><div> <br></div><blockquote class="gmail_quote" style="margin:0px 0px 0px 0.8ex;border-left-width:1px;border-left-style:solid;border-left-color:rgb(204,204,204);padding-left:1ex"><div dir="ltr"><div><br></div><div>I have an example program[2] which computes the sum of an array twice, in two separate accumulators.</div><div>Here, sum0 and sum1 are both sums of the array A.</div><div><br></div><div><div><span style="line-height:1.5">void b01_sums(int size, int* A)</span><br></div><div>{</div><div>  int sum0 = 0;</div><div>  int sum1 = 0;</div><div>  for (int i = 0; i != size; ++i)</div><div>  {</div><div>    sum0 = sum0 + A[i];</div><div>    sum1 = sum1 + A[i];</div><div>    printf("sum0: %d\nsum1: %d\n", sum0, sum1);</div><div>  }</div><div>}</div></div><div><br></div><div>I would have expected global value numbering to see that sum0 and sum1 are initialised and updated with the same value, and so merge them into a single accumulator.</div></div></blockquote><div><br></div><div><br></div><div>The current GVN uses a very weak algorithm.  All phi nodes are given new values, so in the above it will never discover the in-loop equivalences.</div><div>The GVN on the newgvn branch i have will remove these, and is more complicated</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>The one i saw some hope for was <a href="http://link.springer.com/chapter/10.1007%2F978-3-540-76637-7_22">http://link.springer.com/chapter/10.1007%2F978-3-540-76637-7_22</a></div><div>I haven't had a chance to play with it.</div><div><br></div></div><br></div></div>