首页 / 知识

哪个(如果有的话)C ++编译器会进行尾递归优化？

2023-04-13 14:30:00

Which, if any, C++ compilers do tail-recursion optimization?

在我看来，在C和C ++中进行尾递归优化是完美的，但是在调试时我似乎永远不会看到表示此优化的帧堆栈。这有点好，因为堆栈告诉我递归的深度。但是，优化也会很好。

是否有任何C ++编译器进行此优化？为什么？为什么不？

我如何告诉编译器这样做？

对于MSVC：/O2或/Ox
对于GCC：-O2或-O3

如何在某种情况下检查编译器是否已完成此操作？

对于MSVC，启用PDB输出以跟踪代码，然后检查代码
对于GCC ..？

我仍然会建议如何确定编译器是否对某个函数进行了优化(尽管我发现它让人放心，Konrad告诉我假设它)

总是可以通过进行无限递归来检查编译器是否完成此操作，并检查它是否导致无限循环或堆栈溢出(我用GCC做了这个并发现-O2就足够了)，但是我希望能够检查我知道会终止的某个功能。我很想有一个简单的方法来检查这个:)

经过一些测试，我发现析构函数破坏了进行优化的可能性。有时可能值得更改某些变量和临时值的范围，以确保它们在return语句开始之前超出范围。

如果在尾调用后需要运行任何析构函数，则无法进行尾调用优化。

所有当前的主流编译器都能很好地执行尾调优化(并且已经完成了十多年)，即使对于相互递归的调用，例如：

1
2
3
4
5
6
7
8
9

int bar(int, int);

int foo(int n, int acc) {
return (n == 0) ? acc : bar(n - 1, acc + 2);
}

int bar(int n, int acc) {
return (n == 0) ? acc : foo(n - 1, acc + 1);
}

让编译器进行优化非常简单：只需开启优化速度：

对于MSVC，请使用/O2或/Ox。
对于GCC，Clang和ICC，请使用-O3

检查编译器是否进行优化的一种简单方法是执行一个调用，否则会导致堆栈溢出 - 或者查看程序集输出。

作为一个有趣的历史记录，在Mark Probst的毕业论文中，C的尾调优化被添加到GCC。论文描述了实施中的一些有趣的警告。值得一读。

gcc 4.3.2将此函数(crappy / trivial atoi()实现)完全内联到main()中。优化级别-O1。我注意到如果我玩它(甚至将它从static更改为extern，尾递归相当快，所以我不会依赖它来获得程序的正确性。

1
2
3
4
5
6
7
8
9
10
11
12
13
14

#include <stdio.h>
static int atoi(const char *str, int n)
{
if (str == 0 || *str == 0)
return n;
return atoi(str+1, n*10 + *str-'0');
}
int main(int argc, char **argv)
{
for (int i = 1; i != argc; ++i)
printf("%s -> %d
", argv[i], atoi(argv[i], 0));
return 0;
}

除了显而易见之外(编译器不会进行这种优化)，C ++中的尾调用优化存在一个复杂性：析构函数。

给出如下内容：

1
2
3
4
5
6