[GHC] #4470: Loop optimization: identical counters

[GHC]

#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