Nicolas Capens
2009-Oct-14 07:21 UTC
[LLVMdev] Moving dependent code into conditional statements
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:
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
-------------- next part --------------
An HTML attachment was scrubbed...
URL:
<http://lists.llvm.org/pipermail/llvm-dev/attachments/20091014/e7f5f18d/attachment.html>
Chris Lattner
2009-Oct-14 15:22 UTC
[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/c60a1b3d/attachment.html>
Samuel Crow
2009-Oct-14 16:19 UTC
[LLVMdev] Moving dependent code into conditional statements
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>
Vikram S. Adve
2009-Oct-14 17:54 UTC
[LLVMdev] Moving dependent code into conditional statements
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 casesThe 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>