ackermann的gcc转换传递

Question

gcc(我尝试4.7.2使用带有-O3标志的Mac和Linux )将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)并没有将它减少到单个递归调用,并且使用-O3flag会慢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级别,将其内联几次迭代.导致你看到的巨大怪物.