GCC转换通过阿克曼

Question

gcc(我尝试在Mac和Linux上使用-O3标志的4.7.2)将ackermann函数优化为具有大本地堆栈的单个调用。下面是Ackermann代码示例:

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));
}

当反汇编时，只有一个递归调用ack函数，而不是两个调用(我无法解析发生了什么- ack现在被gcc转换为具有8个参数的函数，以及49个int和9个char的本地堆栈)。我试图查找gcc为将Ackermann函数优化为单个调用所做的转换，但没有找到任何感兴趣的内容。我将感谢有关gcc执行哪些主要转换以将深度递归Ackermann转换为单个递归调用的指针。LLVM gcc(我在mac上尝试了v4.2)并没有将其减少到单个递归调用，并且使用-O3标志慢了4倍。这个优化看起来很有趣。

Answer 1

第一步是尾部调用消除。GCC在大多数优化级别上都这样做。基本上，所有在尾部位置的函数调用都被转换成goto，像这样:

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;
}

现在只剩下一个递归调用，GCC仅在-O3级别将其内联几次迭代。结果就是你看到的那个巨大的怪物。