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

Amos Robinson via llvm-dev
2016-05-04T02:42:11Z

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