[LLVMdev] Separating loop nests based on profile information?

[Daniel Berlin]

On Thu, Jan 8, 2015 at 2:37 PM, Philip Reames <listmail at philipreames.com>
wrote:

>
> On 01/07/2015 05:33 PM, Chandler Carruth wrote:
>
>
> On Wed, Jan 7, 2015 at 5:19 PM, Philip Reames <listmail at philipreames.com>
> wrote:
>
>> I've been playing with approaches to getting better optimization of loops
>> which contain infrequently executed slow paths.  I've gotten as far as
>> throwing together a proof of concept implementation of a profile guided
>> optimization to separate a single loop with multiple latches into a loop
>> nest, but I want to get feedback from interested parties before investing
>> much more effort.
>>
>> The primary case I'm concerned about looks something like this C example:
>> while( some_condition )
>>   //do lots of work here
>>   if (!some_rare_condition) { <-- This is loop variant
>>     helper();
>>   }
>> }
>>
>> The key point here is that the 'do lots of work' section contains things
>> we could lift out of the loop, but our knowledge of memory gets completely
>> destoryed by the 'helper' call which doesn't get inlined.  This ends up
>> crippling LICM in particular, and GVN to a lessor degree.
>>
>> The approach I've been playing with would create this loop structure:
>> goto inner
>> while (true) {
>>   outer:
>>   helper();
>>   inner:
>>   while( some_condition )
>>     //do lots of work here
>>     if (!some_rare_condition) { <-- This is loop variant
>>       goto outer;
>>     }
>>   }
>> }
>>
>> (Excuse the psuedo-C.  Hopefully the idea is clear.)
>>
>
>  Yep.
>
>  I've not thought about this a lot, but I have two initial questions that
> maybe you can answer:
>
>  How does this compare with classical approaches of loop peeling,
> partitioning, fission, or whatever you might call it? Is there any
> literature behind this approach or some literature it should be compared
> with? (I genuinely don't know this area that well, so I'm of little help
> here...)
>
> I'm not aware of any literature that covers the specific transform I'm
> suggesting here.  This is probably a lack of awareness on my part, not a
> lack of literature though.
>

http://webdocs.cs.ualberta.ca/~amaral/papers/BartonCC05.pdf

This is essentially index set splitting with the goal of it being an
enabling optimization for LICM.

(At least, as i've seen it implemented in other compilers)
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://lists.llvm.org/pipermail/llvm-dev/attachments/20150112/b62acf89/attachment.html>