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

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

>
>
> 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)).
>
> Yes, AWZ will get some, and the hash based ones will get some different
ones.

The one i have implemented unifies AWZ and hash based and will also do
predication/value inference.
-------------- next part --------------
An HTML attachment was scrubbed...
URL:
<http://lists.llvm.org/pipermail/llvm-dev/attachments/20160503/541e7b7c/attachment-0001.html>

> The GVN on the newgvn branch i have will remove these, and is more
complicated
> The one i have implemented unifies AWZ and hash based and will also do
predication/value inference.

This is exciting news. It sounds like it will find a lot of the interesting
cases.
> 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.

Yes, fair enough. I thought that might be the case. A lot of the examples
in the papers seem a bit contrived anyway, so it would be interesting to
know just how many "real" opportunities are being missed.
>  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.
This looks very promising, thank you.



On Wed, 4 May 2016 at 11:01 Daniel Berlin <dberlin at dberlin.org> wrote:
>
>> 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)).
>>
>> Yes, AWZ will get some, and the hash based ones will get some different
> ones.
>
> The one i have implemented unifies AWZ and hash based and will also do
> predication/value inference.
>
>
>
-------------- next part --------------
An HTML attachment was scrubbed...
URL:
<http://lists.llvm.org/pipermail/llvm-dev/attachments/20160504/6aad11c2/attachment.html>