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

[Daniel Berlin via llvm-dev]

On Tue, May 3, 2016 at 10:00 PM, Amos Robinson <amos.robinson at gmail.com>
wrote:

>
>
> 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.
>
What i've given you is a broad generalization that comes down to "on modern
processors you often have to remove 20-100x more arithmetic to match the
improvement from removing a single load or other memory op".

They often can issue multiple arithmetic ops per cycle, and get the results
from all of them in a single cycle.

Are there exceptions to my generalization? Sure. If you call a function 10
billion times, and you remove a single cycle from it, ...


> 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.
>
GVN would work well for this, but depending on your situation, it may also
be massive overkill ;)


>
>>
> 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?
>
>
It does not require any aliasing assistance, just symbolically evaluating
where these things access.
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://lists.llvm.org/pipermail/llvm-dev/attachments/20160504/8e7576fd/attachment.html>