33

我经常听到人们说 C 不执行尾调用消除。即使标准不能保证它,但无论如何,它在实践中不是由任何体面的实现来执行的吗?假设您只针对成熟、实现良好的编译器,而不关心为晦涩平台编写的原始编译器的绝对最大可移植性,那么依赖 C 中的尾调用消除是否合理?

另外,将尾调用优化排除在标准之外的理由是什么?

4

8 回答 8

31

像“C 不执行尾调用消除”这样的语句毫无意义。正如您正确指出的那样,这样的事情完全取决于实现。是的,任何体面的实现都可以轻松地将尾递归变成[相当于]一个循环。当然,C 编译器通常不会保证在每段特定代码中会发生哪些优化以及不会发生哪些优化。您必须编译它并亲自查看。

于 2010-08-18T16:27:51.437 回答
8

尽管现代编译器可能会在您打开优化时进行尾调用优化,但您的调试构建可能会在没有它的情况下运行,这样您就可以获得堆栈跟踪和步入/退出代码以及类似的美妙事情。在这种情况下,不需要尾调用优化。

由于尾调用优化并不总是可取的,因此将其强制要求编译器编写者是没有意义的。

于 2014-05-01T17:34:55.490 回答
7

我认为只有在预期或需要大量递归的情况下才需要保证尾调用优化;也就是说,在鼓励或强制执行函数式编程风格的语言中。(对于这些类型的语言,您可能会发现fororwhile循环要么被强烈反对,被认为不雅,甚至可能完全不存在于语言中,因此出于所有这些原因,您可能会诉诸递归,甚至可能更多。)

C 编程语言(恕我直言)显然在设计时并未考虑到函数式编程。有各种循环结构通常用于支持递归:for, do .. while, while. 在这样的语言中,在标准中规定尾调用优化没有多大意义,因为它并不是严格要求保证工作程序。

再次将此与没有while循环的函数式编程语言进行对比:这意味着您将需要递归;这反过来意味着该语言必须确保在多次迭代时堆栈溢出不会成为问题;因此这种语言的官方标准可能会选择规定尾调用优化。


PS:请注意我关于尾调用优化的论点中的一个小缺陷。最后,我提到了堆栈溢出。但是谁说函数调用总是需要堆栈呢?在某些平台上,函数调用可能以完全不同的方式实现,堆栈溢出甚至不会成为问题。这将是反对在标准中规定尾调用优化的另一个论点。(但不要误会,我可以看到这种优化的优点,即使没有堆栈!)

于 2010-08-18T16:46:56.933 回答
4

回答你最后一个问题:标准绝对不应该对优化做出任何陈述。可能存在或多或少难以实施的环境。

于 2010-08-18T16:28:16.317 回答
2

对于那些喜欢构造证明的人,这里是 godbolt 做一个很好的尾调用优化和内联:https ://godbolt.org/z/DMleUN

但是,如果您将优化调到 -O3(或者毫无疑问,如果您等待几年或使用不同的编译器),则优化将完全消除循环/递归。

这是一个即使使用 -O2 也可以优化为单个指令的示例:https ://godbolt.org/z/CNzWex

于 2018-08-20T07:55:09.023 回答
1

语言标准定义了语言的行为方式,而不是编译器需要如何实现。优化不是强制性的,因为它并不总是需要的。编译器提供选项,以便用户可以根据需要启用优化,也可以将其关闭。编译器优化会影响调试代码的能力(以逐行方式将 C 与汇编匹配变得更加困难),因此仅在用户请求时执行优化是有意义的。

于 2010-08-18T16:35:48.683 回答
0

编译器通常会识别一个函数在调用另一个函数后不需要做任何事情的情况,并用跳转替换该调用。许多可以安全地做到这一点的案例很容易识别,这些案例被称为“安全的低垂果实”。然而,即使在可以执行此类优化的编译器上,何时应该或将要执行它也可能并不总是很明显。各种因素可能使尾随呼叫的成本高于正常呼叫的成本,而这些因素可能并不总是可预测的。例如,如果一个函数以 结尾return foo(1,2,3,a,b,c,4,5,6);,将 a、b 和 c 复制到寄存器中,清理堆栈然后准备要传递的参数可能是可行的,但可能没有足够的寄存器可用于foo(a,b,c,d,e,f,g,h,i);同样处理。

如果一种语言有一个特殊的“尾调用”语法,要求编译器尽可能进行尾调用,否则拒绝编译,代码可以安全地假设这些函数可以嵌套任意深度。然而,当使用普通调用语法时,没有通用的方法可以知道编译器是否能够比“普通”更便宜地执行尾调用。

于 2018-08-20T17:57:12.457 回答
0

在某些情况下,尾调用优化可能会破坏 ABI,或者至少很难以保留语义的方式实现。例如,考虑共享库中与位置无关的代码:当各种不同的应用程序都依赖于相同的功能时,一些平台允许程序动态链接库以节省主内存。在这种情况下,库被加载一次并映射到程序的每个虚拟内存中,就好像它是系统上唯一的应用程序一样。在 UNIX 和其他一些系统上,这是通过对库使用与位置无关的代码来实现的,因此寻址是相对于偏移量的,而不是相对于固定地址空间的绝对值。然而,在许多平台上,位置无关代码不得进行尾调用优化。所涉及的问题是在程序中导航的偏移量必须保存在寄存器中。在英特尔 32 位上,%ebx使用的是被调用者保存的寄存器;其他平台也遵循这一概念。与使用普通调用的函数不同,那些部署尾调用的函数必须在分支到子例程之前恢复被调用者保存的寄存器,而不是在它们返回时恢复。通常,这没有问题,因为此时,最顶层的调用函数并不关心存储在 中的值%ebx,但位置无关代码取决于每个跳转、调用或分支命令的该值。

其他问题可能是面向对象语言 (C++) 中的待清理,这意味着函数中的最后一次调用实际上并不是最后一次调用——清理是。因此,在这种情况下,编译器通常不会进行优化。

当然,这也是setjmplongjmp问题的,因为这实际上意味着一个函数可以在实际完成之前多次完成执行。在编译时难以或不可能优化!

人们可能会想到更多的技术原因。这些只是一些考虑。

于 2018-02-17T10:04:27.350 回答