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

[Amos Robinson via llvm-dev]

On Wed, 4 May 2016 at 14:21 Daniel Berlin <dberlin at dberlin.org> wrote:

> As a general rule of thumb, if it only removes scalar code, it's pretty
> useless.
> If it helps it prove it can remove memory operations, it's great.
>

Perhaps I am misunderstanding, but I agree my example wasn't very exciting
as-is but I imagine you could replace addition with some reasonably
expensive function call and it would be a bit more compelling.
However, I am coming at this from a much higher level of abstraction: I am
working on a query compiler that takes a whole bunch of queries and fuses
them together into one. Removing duplicates in this case is also much
simpler than general GVN, and I'm just trying to get a good story about the
relationship.


>
Often, in your example, it's accesses that are loop invariant but common to
> other accesses in the loop that are most promising.
>
> IE (taken from a test i wrote for GCC's VN)
> int vnum_test8(int *data)
> {
>   int i;
>   int stop = data[3];
>   int m = data[4];
>   int n = m;
>   int p;
>   for (i=0; i<stop; i++) {
>     int k = data[2];
>     data[k] = 2;
>     data[0] = m - n;
>     k = data[1];
>     m = m + k;
>     n = n + k;
>     p = data[0];
>   }
>   return p;
> }
>
> We test that we eliminate m-n in favor of 0, replace n with m, and set p
> to 0
>
>
> Note that this requires proving a bunch of things about the memory
> accesses here, and properly value numbering memory accesses (which current
> GVN will not do).
>

Do you mean, for example, proving that accessing data[k] does not segfault
here, or aliasing things?
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://lists.llvm.org/pipermail/llvm-dev/attachments/20160504/fe22cee3/attachment.html>