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

Hal Finkel via llvm-dev
2016-05-04T00:55:42Z

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