[LLVMdev] Moving dependent code into conditional statements

[Vikram S. Adve]

On Oct 14, 2009, at 10:22 AM, Chris Lattner wrote:

>
> On Oct 14, 2009, at 12:21 AM, Nicolas Capens wrote:
>
>> Hi all,
>>
>> Is there any existing optimization pass that will move as much code  
>> into the body of a forward branch as possible? Consider the  
>> following example:
>
> Hi Nicolas,
>
> Instcombine does this in simple cases


The general version of this looks like classical PRE.

--Vikram
Associate Professor, Computer Science
University of Illinois at Urbana-Champaign
http://llvm.org/~vadve



> (see "See if we can trivially sink this instruction to a successor  
> basic block.") but it misses this case because the if gets folded  
> into a select early.  It was also not handling the "phi use" case  
> very aggressively, which I fixed in r84103.  We now sink the divide  
> and add in this example:
>
> int foo(int x)
> {
>     for(int i = 0; i < 1000000; i++)
>     {
>         int y = (x + 1) / x;   // Expensive calculation! Result  
> written to memory.
>
>         if(x == 0)   // Forward branch
>         {
> bar();
>             x = y;   // Body
>         }
>     }
>
>     return x;
> }
>
>
> -Chris
>
>
>>
>> int foo(int x)
>> {
>>     for(int i = 0; i < 1000000; i++)
>>     {
>>         int y = (x + 1) / x;   // Expensive calculation! Result  
>> written to memory.
>>
>>         if(x == 0)   // Forward branch
>>         {
>>             x = y;   // Body
>>         }
>>     }
>>
>>     return x;
>> }
>>
>> It appears that LLVM compiles this quite literally, performing the  
>> expensive calculation a million times. Yet it could be rewritten  
>> like this:
>>
>> int foo(int x)
>> {
>>     for(int i = 0; i < 1000000; i++)
>>     {
>>         if(x == 0)   // Unlikely to hit
>>         {
>>             int y = (x + 1) / x;
>>             x = y;
>>         }
>>     }
>>
>>     return x;
>> }
>>
>> This runs way faster.
>>
>> I noticed there’s a loop hoisting optimization (moving as many  
>> independent operations out of the body of a backward branch), but  
>> I’m looking for its twin. Did I overlook it or is it not yet  
>> supported?
>>
>> Thanks,
>>
>> Nicolas
>> _______________________________________________
>> LLVM Developers mailing list
>> LLVMdev at cs.uiuc.edu         http://llvm.cs.uiuc.edu
>> http://lists.cs.uiuc.edu/mailman/listinfo/llvmdev
>
> <ATT00001.txt>

-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://lists.llvm.org/pipermail/llvm-dev/attachments/20091014/6dcdeee2/attachment.html>