optimization - ackermann 的 gcc 转换过程

Question

gcc(我在 Mac 和 Linux 上使用 -O3 标志尝试了 4.7.2)将 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 执行哪些主要转换过程以将深度递归阿克曼转换为单个递归调用的指示。 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 级别将其内联几次迭代。结果就是你看到的巨大怪物。