<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><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. However, the assembly output still contains both accumulators:</div><div><br></div><div>$ gcc sums.c -c -O3 -save-temps</div><div><div>. . .</div><div><span class="Apple-tab-span" style="line-height:1.5;white-space:pre">    </span># A[i] (only once)</div><div><span class="Apple-tab-span" style="white-space:pre">   </span>movl<span class="Apple-tab-span" style="white-space:pre">        </span>(%r15), %eax</div><div><span class="Apple-tab-span" style="white-space:pre"> </span># add sum0 and sum1</div><div><span class="Apple-tab-span" style="white-space:pre">  </span>addl<span class="Apple-tab-span" style="white-space:pre">        </span>%eax, %ebx</div><div><span class="Apple-tab-span" style="white-space:pre">   </span>addl<span class="Apple-tab-span" style="white-space:pre">        </span>%eax, %r13d</div></div><div><br></div><div>I have tried a few variations on the C code: pulling out the array reads into a single binding makes no difference, while moving the printf outside of the loop allows the loop to be vectorised, but there are still two accumulators.</div><div>I am wondering whether I am missing some particular invocation (perhaps to enable fixpoints over loops in the GVN analysis?), or otherwise, if there is some reason that means this sort of analysis is impractical for real programs.</div><div><br></div><div>I am using the Apple clang 6, but also tried with llvm opt 3.6:</div><div><br></div><div><div>$ gcc --version</div><div>Configured with: --prefix=/Library/Developer/CommandLineTools/usr --with-gxx-include-dir=/usr/include/c++/4.2.1</div><div>Apple LLVM version 6.0 (clang-600.0.57) (based on LLVM 3.5svn)</div><div>Target: x86_64-apple-darwin13.4.0</div><div>Thread model: posix</div><div><div>$ /usr/local/opt/llvm/bin/opt --version</div><div>LLVM (<a href="http://llvm.org/">http://llvm.org/</a>):</div><div>  LLVM version 3.6.2</div><div>  Optimized build.</div><div>  Built Apr 10 2016 (02:50:09).</div><div>  Default target: x86_64-apple-darwin13.4.0</div><div>  Host CPU: core-avx2</div></div></div><div><br></div><div>Thanks,</div><div>Amos Robinson</div><div><br></div><div>[1]: Gulwani & Necula: <span style="line-height:1.5">A Polynomial-Time Algorithm for Global
Value Numbering</span><span style="line-height:1.5"> <a href="http://www.eecs.berkeley.edu/~necula/Papers/gvndet-journal06.pdf">http://www.eecs.berkeley.edu/~necula/Papers/gvndet-journal06.pdf</a></span></div><div><br></div><div><span style="line-height:1.5">[2]: Example code and assembly output </span><a href="https://gist.github.com/amosr/06938ee5becaf5249de5634499bc1add">https://gist.github.com/amosr/06938ee5becaf5249de5634499bc1add</a></div></div>