[LLVMdev] Moving dependent code into conditional statements

[Samuel Crow]

Hi Nicolas,

Your example has more expense in that calculation than you may have intended.  Why are you trying to divide by 0?  It seems to me that that would trigger an exception on any processor I know of.  :-)  No wonder it's faster to execute in the if statement!

That being said, would llvm-gcc or clang have a way to figure stuff like that divide by zero out before you execute the code and get the exception?

--Sam


>
>From: Chris Lattner <clattner at apple.com>
>To: Nicolas Capens <nicolas at capens.net>
>Cc: LLVM Developers Mailing List <llvmdev at cs.uiuc.edu>
>Sent: Wed, October 14, 2009 10:22:53 AM
>Subject: Re: [LLVMdev] Moving dependent code into conditional statements
>
>
>
>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/0fa4adbb/attachment.html>