现代编译器优化如何将递归转换为返回常量？

Question

当我用g ++编译下面的简单递归代码时,汇编代码只返回i,好像g ++可以像人类那样做一些代数技巧.

int Identity(int i) {
  if (i == 1)
    return 1;
  else
    return Identity(i-1)+1;
}

我不认为这种优化是关于尾递归的,显然,g ++必须至少做这两件事:

1. 如果我们传递一个负值,这个代码将落入一个无限循环,那么g ++是否有效消除这个错误呢？
2. 虽然可以枚举从1到INT_MAX的所有值,然后g ++可以告诉该函数将返回i,显然g ++使用更智能的检测方法,因为编译过程非常快.因此我的问题是,编译器优化如何做到这一点？

如何重现

% g++ -v
gcc version 8.2.1 20181127 (GCC)

% g++ a.cpp -c -O2 && objdump -d a.o
Disassembly of section .text:
0000000000000000 <_Z8Identityi>:
   0:   89 f8                   mov    %edi,%eax
   2:   c3

更新: 感谢很多人回答这个问题.我在这里收集了一些讨论和更新.

1. 编译器使用某种方法来知道传递负值会导致UB.也许编译器使用相同的方法来进行代数技巧.
2. 关于尾递归:根据维基百科,我以前的代码不是尾递归形式.我尝试了尾递归版本,gcc生成了正确的while循环.但是,它不能像我以前的代码那样返回i.
3. 有人指出编译器可能试图"证明"f(x)= x,但我仍然不知道所用实际优化技术的名称.我对这种优化的确切名称感兴趣,例如常见的子表达式消除(CSE)或它们的某种组合或其他.

更新+回答: 感谢下面的答案(我已经标记它有用,并且还检查了manlio的答案),我想我理解编译器如何以简单的方式完成此操作.请参阅下面的示例.首先,现代gcc可以做一些比尾递归更强大的东西,所以代码转换成这样的东西:

// Equivalent to return i
int Identity_v2(int i) {
  int ans = 0;
  for (int i = x; i != 0; i--, ans++) {}
  return ans;
}
// Equivalent to return i >= 0 ? i : 0
int Identity_v3(int x) {
  int ans = 0;
  for (int i = x; i >= 0; i--, ans++) {}
  return ans;
}

(我猜)编译器可以知道ans和i共享相同的delta,并且在离开循环时也知道i = 0.因此,编译器知道它应该返回i.在v3中,我使用>=运算符,因此编译器也会为我检查输入的符号.这可能比我猜想的要简单得多.

Answer 1

GCC的优化传递以一种称为GIMPLE的格式处理代码的中间表示.

使用这些-fdump-*选项,您可以要求GCC输出树的中间状态,并发现有关执行的优化的许多详细信息.

在这种情况下,有趣的文件是(数字可能会有所不同,具体取决于GCC版本):

.004t.gimple

这是出发点:

int Identity(int) (int i)
{
  int D.2330;
  int D.2331;
  int D.2332;

  if (i == 1) goto <D.2328>; else goto <D.2329>;
  <D.2328>:
  D.2330 = 1;
  return D.2330;
  <D.2329>:
  D.2331 = i + -1;
  D.2332 = Identity (D.2331);
  D.2330 = D.2332 + 1;
  return D.2330;
}

.038t.eipa_sra

呈现递归的最后一个优化源:

int Identity(int) (int i)
{
  int _1;
  int _6;
  int _8;
  int _10;

  <bb 2>:
  if (i_3(D) == 1)
    goto <bb 4>;
  else
    goto <bb 3>;

  <bb 3>:
  _6 = i_3(D) + -1;
  _8 = Identity (_6);
  _10 = _8 + 1;

  <bb 4>:
  # _1 = PHI <1(2), _10(3)>
  return _1;
}

与SSA一样,GCC会PHI在需要的基本块的开头插入伪函数,以便合并变量的多个可能值.

这里:

# _1 = PHI <1(2), _10(3)>

根据我们是否通过块或块到达此处,其中_1任一个获取1或的值._1023

.039t.tailr1

这是递归已转换为循环的第一个转储:

int Identity(int) (int i)
{
  int _1;
  int add_acc_4;
  int _6;
  int acc_tmp_8;
  int add_acc_10;

  <bb 2>:
  # i_3 = PHI <i_9(D)(0), _6(3)>
  # add_acc_4 = PHI <0(0), add_acc_10(3)>
  if (i_3 == 1)
    goto <bb 4>;
  else
    goto <bb 3>;

  <bb 3>:
  _6 = i_3 + -1;
  add_acc_10 = add_acc_4 + 1;
  goto <bb 2>;

  <bb 4>:
  # _1 = PHI <1(2)>
  acc_tmp_8 = add_acc_4 + _1;
  return acc_tmp_8;
}

处理尾调用的相同优化也处理通过创建累加器使调用尾递归的微不足道的情况.

https://github.com/gcc-mirror/gcc/blob/master/gcc/tree-tailcall.c文件的起始注释中有一个非常类似的示例:

该文件实现了尾递归消除.它还用于分析尾调用,将结果传递到rtl级别,用于sibcall优化.

除了标准的尾递归消除之外,我们还通过创建累加器来处理使调用尾递归的最微不足道的情况.

例如以下功能

int sum (int n)
{
  if (n > 0)
    return n + sum (n - 1);
  else
    return 0;
}

变成了

int sum (int n)
{
  int acc = 0;
  while (n > 0)
    acc += n--;
  return acc;
}

为此,我们维护两个累加器(a_acc和m_acc),指示当我们到达return x语句时,我们应该返回a_acc + x * m_acc .它们最初初始化为0和1,因此显然保留了函数的语义.如果我们保证累加器的值永远不会改变,我们省略累加器.

有三种情况如何退出该功能.第一个在adjust_return_value中处理,另外两个在adjust_accumulator_values中处理(第二种情况实际上是第三种情况的特殊情况,为了清楚起见,我们单独呈现它):

1. 只返回x,其中x没有任何剩余的特殊形状.我们将其重写为相当于回报的gimple m_acc * x + a_acc.
2. 返回f (...),f当前函数在哪里,以经典的尾递归消除方式重写,分配参数并跳转到函数的开头.累加器的值不变.
3. 返回a + m * f(...),在哪里a,m不依赖于呼叫f.为了保留之前描述的语义,我们希望以最终返回的方式重写它 a_acc + (a + m * f(...)) * m_acc = (a_acc + a * m_acc) + (m * m_acc) * f(...).也就是说,我们增加a_acc的a * m_acc,乘m_acc用m和消除尾调用f.通过设置a = 0或获得刚刚添加或仅增加值的特殊情况m = 1.