[llvm-dev] GVN pass: does global value numbering remove duplicate computations in loops?
Daniel Berlin via llvm-dev
llvm-dev at lists.llvm.org
Tue May 3 17:39:54 PDT 2016
On Tue, May 3, 2016 at 5:25 PM, Amos Robinson via llvm-dev <
llvm-dev at lists.llvm.org> wrote:
> 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.
The current GVN will not do it.
> I have an example program 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
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
I haven't had a chance to play with it.
-------------- next part --------------
An HTML attachment was scrubbed...
More information about the llvm-dev