[LLVMdev] Moving dependent code into conditional statements

[Chris Lattner]

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

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