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

Daniel Berlin via llvm-dev llvm-dev at lists.llvm.org
Wed May 4 09:26:01 PDT 2016

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

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

More information about the llvm-dev mailing list