[LLVMdev] Moving dependent code into conditional statements

[Vinod Grover]

This is done by partial dead code elimination (PDE), which moves
computations forward without them redundant. This was first reported in PLDI
94 (I think) - the basic version is bit-vector based and is O(n^4) in
complexity. There is no good SSA version that I am aware of - though there
was one which I cant recall at the moment that uses value graphs.
Vinod


On Wed, Oct 14, 2009 at 10:54 AM, Vikram S. Adve <vadve at illinois.edu> wrote:

> 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>
>
>
>
> _______________________________________________
> 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/eb4f44ba/attachment.html>