#4470: Loop optimization: identical counters
---------------------------------+------------------------------------------
Reporter: choenerzs | Owner:
Type: feature request | Status: new
Priority: normal | Component: Compiler
Version: | Keywords: loop optimization
Testcase: | Blockedby:
Os: Unknown/Multiple | Blocking:
Architecture: Unknown/Multiple | Failure: None/Unknown
---------------------------------+------------------------------------------
Comment(by batterseapower):
Very interesting. The reason that LLVM doesn't get this is the same reason
that it doesn't optimise this C program:
{{{
int wf(int sp[]) {
if (sp[0] == 0) {
return sp[2] + sp[3];
} else {
sp[3] = sp[3] + (sp[1] * 5);
sp[2] = (sp[2] + sp[0]) + 1;
sp[1] = sp[1] - 1;
sp[0] = sp[0] - 1;
return wf(sp);
}
}
int g(int a) {
int sp[] = { a, a, 0, 0 };
return wf(sp);
}
int main(void) {
printf("%d\n", g(5));
return 0;
}
}}}
If we rewrite the program to eliminate the "sp" array, we get this:
{{{
int wf(int a, int b, int c, int d) {
if (a == 0) {
return c + d;
} else {
return wf(a - 1, b - 1, (c + a) + 1, d + (b * 5));
}
}
int g(int a) {
return wf(a, a, 0, 0);
}
int main(void) {
printf("%d\n", g(5));
return 0;
}
}}}
LLVM *can* optimise this definition of g(int). Indeed, it identifiers a as
an induction variable and turns it into an incrementing counter, and
eliminates the computation of b.
It looks like LLVM has a big blind spot for pointer-carried arguments, and
needs to do some promotion of elements of an input array into registers
before we can reuse its loop optimisation infrastructure. In fact, it
looks like LLVM's loop optimisations are being *totally disabled* by our
use of sp[] right now - so there are big wins to be had.
I have posted this example to the llvm list in the hope of some insight:
http://article.gmane.org/gmane.comp.compilers.llvm.devel/36068
--
Ticket URL: <http://hackage.haskell.org/trac/ghc/ticket/4470#comment:3>
GHC <http://www.haskell.org/ghc/>
The Glasgow Haskell Compiler
_______________________________________________
Glasgow-haskell-bugs mailing list
[email protected]
http://www.haskell.org/mailman/listinfo/glasgow-haskell-bugs
