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

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

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.

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


On Tue, May 3, 2016 at 7:42 PM, Amos Robinson <amos.robinson at gmail.com>
wrote:
> > 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/20160503/2dbe66ec/attachment.html>

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>