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?
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
}
}
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?
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.
No wonder it’s faster to execute in the if statement!