<html><head><style type='text/css'>p { margin: 0; }</style></head><body><div style='font-family: arial,helvetica,sans-serif; font-size: 10pt; color: #000000'><br><br><hr id="zwchr"><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;"><b>From: </b>"Daniel Berlin via llvm-dev" <llvm-dev@lists.llvm.org><br><b>To: </b>"Amos Robinson" <amos.robinson@gmail.com><br><b>Cc: </b>"llvm-dev" <llvm-dev@lists.llvm.org><br><b>Sent: </b>Tuesday, May 3, 2016 7:39:54 PM<br><b>Subject: </b>Re: [llvm-dev] GVN pass: does global value numbering remove duplicate computations in loops?<br><br><div dir="ltr"><br><div id="DWT15637" 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: 1px solid 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: 1px solid 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" target="_blank">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></blockquote><br>If I recall correctly, AWZ will get this too (https://courses.cs.washington.edu/courses/cse501/04wi/papers/alpern-popl88.pdf). 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> -Hal<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>
<br>_______________________________________________<br>LLVM Developers mailing list<br>llvm-dev@lists.llvm.org<br>http://lists.llvm.org/cgi-bin/mailman/listinfo/llvm-dev<br></blockquote><br><br><br>-- <br><div><span name="x"></span>Hal Finkel<br>Assistant Computational Scientist<br>Leadership Computing Facility<br>Argonne National Laboratory<span name="x"></span><br></div></div></body></html>