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

[Daniel Berlin via llvm-dev]

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>