llvm dev - May 2016 - GVN pass: does global value numbering remove duplicate computations in loops?

Hello,
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].

I have an example program[2] which computes the sum of an array twice, in
two separate accumulators.
Here, sum0 and sum1 are both sums of the array A.

void b01_sums(int size, int* A)
{
  int sum0 = 0;
  int sum1 = 0;
  for (int i = 0; i != size; ++i)
  {
    sum0 = sum0 + A[i];
    sum1 = sum1 + A[i];
    printf("sum0: %d\nsum1: %d\n", sum0, sum1);
  }
}

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:

$ gcc sums.c -c -O3 -save-temps
. . .
# A[i] (only once)
movl (%r15), %eax
# add sum0 and sum1
addl %eax, %ebx
addl %eax, %r13d

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.
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.

I am using the Apple clang 6, but also tried with llvm opt 3.6:

$ gcc --version
Configured with: --prefix=/Library/Developer/CommandLineTools/usr
--with-gxx-include-dir=/usr/include/c++/4.2.1
Apple LLVM version 6.0 (clang-600.0.57) (based on LLVM 3.5svn)
Target: x86_64-apple-darwin13.4.0
Thread model: posix
$ /usr/local/opt/llvm/bin/opt --version
LLVM (http://llvm.org/):
  LLVM version 3.6.2
  Optimized build.
  Built Apr 10 2016 (02:50:09).
  Default target: x86_64-apple-darwin13.4.0
  Host CPU: core-avx2

Thanks,
Amos Robinson

[1]: Gulwani & Necula: A Polynomial-Time Algorithm for Global Value
Numbering http://www.eecs.berkeley.edu/~necula/Papers/gvndet-journal06.pdf

[2]: Example code and assembly output
https://gist.github.com/amosr/06938ee5becaf5249de5634499bc1add
-------------- next part --------------
An HTML attachment was scrubbed...
URL:
<http://lists.llvm.org/pipermail/llvm-dev/attachments/20160504/0a0a8e24/attachment.html>

On Tue, May 3, 2016 at 5:25 PM, Amos Robinson via llvm-dev <
llvm-dev at lists.llvm.org> wrote:
> Hello,
> 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].
>
Yes

The current GVN will not do it.

>
> I have an example program[2] which computes the sum of an array twice, in
> two separate accumulators.
> Here, sum0 and sum1 are both sums of the array A.
>
> void b01_sums(int size, int* A)
> {
>   int sum0 = 0;
>   int sum1 = 0;
>   for (int i = 0; i != size; ++i)
>   {
>     sum0 = sum0 + A[i];
>     sum1 = sum1 + A[i];
>     printf("sum0: %d\nsum1: %d\n", sum0, sum1);
>   }
> }
>
> 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.
>

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.
The GVN on the newgvn branch i have will remove these, and is more
complicated
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.

The one i saw some hope for was
http://link.springer.com/chapter/10.1007%2F978-3-540-76637-7_22
I haven't had a chance to play with it.
-------------- next part --------------
An HTML attachment was scrubbed...
URL:
<http://lists.llvm.org/pipermail/llvm-dev/attachments/20160503/cf5146ad/attachment.html>

----- Original Message -----
> From: "Daniel Berlin via llvm-dev" <llvm-dev at
lists.llvm.org>
> To: "Amos Robinson" <amos.robinson at gmail.com>
> Cc: "llvm-dev" <llvm-dev at lists.llvm.org>
> Sent: Tuesday, May 3, 2016 7:39:54 PM
> Subject: Re: [llvm-dev] GVN pass: does global value numbering remove
> duplicate computations in loops?
> On Tue, May 3, 2016 at 5:25 PM, Amos Robinson via llvm-dev <
> llvm-dev at lists.llvm.org > wrote:
> > Hello,
> 
> > 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].
> 
> Yes
> The current GVN will not do it.
> > I have an example program[2] which computes the sum of an array
> > twice, in two separate accumulators.
> 
> > Here, sum0 and sum1 are both sums of the array A.
> 
> > void b01_sums(int size, int* A)
> 
> > {
> 
> > int sum0 = 0;
> 
> > int sum1 = 0;
> 
> > for (int i = 0; i != size; ++i)
> 
> > {
> 
> > sum0 = sum0 + A[i];
> 
> > sum1 = sum1 + A[i];
> 
> > printf("sum0: %d\nsum1: %d\n", sum0, sum1);
> 
> > }
> 
> > }
> 
> > 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.
> 
> 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.
> The GVN on the newgvn branch i have will remove these, and is more
> complicated
> 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.
> The one i saw some hope for was
> http://link.springer.com/chapter/10.1007%2F978-3-540-76637-7_22
> I haven't had a chance to play with it.
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)).

-Hal 
> _______________________________________________
> LLVM Developers mailing list
> llvm-dev at lists.llvm.org
> http://lists.llvm.org/cgi-bin/mailman/listinfo/llvm-dev
-- 

Hal Finkel 
Assistant Computational Scientist 
Leadership Computing Facility 
Argonne National Laboratory 
-------------- next part --------------
An HTML attachment was scrubbed...
URL:
<http://lists.llvm.org/pipermail/llvm-dev/attachments/20160503/9c468bd6/attachment.html>