小编joh*_*lys的帖子

当我用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 …