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

[Daniel Berlin via llvm-dev]

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>