gcc transformation pass for ackermann

gcc, optimization

Solution

The first pass is tail-call elimination. GCC does this at most optimization levels. Essentially, all function calls in tail position are transformed into goto's, like this:

int ack(int m, int n) {
begin:
  if (m == 0) return n + 1;
  if (n == 0) { m -= 1; n = 1; goto begin; }
  n = ack(m, n-1); m -= 1; goto begin;
}

Now there is only one recursive call remaining and GCC, at -O3 level only, inlines this for a couple of iterations. Resulting in the huge monster you saw.

Problem

`gcc` (I tried `4.7.2` on Mac and Linux with `-O3` flag) optimizes ackermann function to a single call with a big local stack. An example Ackermann code below: ``` int ack(int m,int n){ if(m == 0) return n+1; if(n == 0) return ack(m-1,1); return ack(m-1,ack(m,n-1)); } ``` When disassembled, there is only one recursive call to `ack` function, instead of two calls (I couldn't parse what is going on -`ack` is now transformed by gcc into a function with 8 arguments, and local stack of 49 int and 9 char). I tried to look up what kind of transformation passes gcc did to optimize Ackermann function to a single call, but didn't find anything of interest. I will appreciate pointers on what major transformation passes gcc performed to convert the deeply recursive Ackermann to a single recursive call. LLVM gcc (I tried v4.2 on mac) doesn't reduce it to single recursive call yet, and is 4x slower with `-O3` flag. This optimization seems very interesting.

Original source