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

[Hal Finkel via llvm-dev]

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