尾部呼叫优化如何工作

大多数本科计算机科学课程都会教给学生有关尾部呼叫优化（TCO）的知识，即使您没有正式的计算机科学背景，也要谈论这个概念，足以使您无论如何都要熟悉它，尤其是如果您曾经完成任何功能编程。但是，我认为通常讲授TCO的方式非常令人困惑，因为通常在递归的上下文中讲授TCO。之所以如此，是因为没有TCO，许多递归函数可能会使堆栈崩溃，从而导致堆栈溢出。因此，通过在递归的背景下向人们介绍TCO，您可以教会他们为什么优化编译器（或解释器）可以有效地运行尾递归代码，而不会引起堆栈溢出。

但是，TCO的递归情况实际上不是常态：实际上，如果您使用C，C ++或任何其他大多数语言使用优化的编译器重写代码，则几乎可以肯定的是，TCO已遍及整个程序即使他们不使用任何递归。了解TCO的非递归情况实际上要简单得多，而且如果您了解非递归的情况，您会意识到，实际上没有什么特别的方法可以将TCO应用于递归函数。

首先，我将重新介绍函数调用在x86上的工作方式。请注意，基本上每个ISA都具有相同的模型，包括ARM，因此我要说的是x86专用的，除了寄存器和我将使用的x86助记符。

您的计算机上有一堆寄存器，其中一个是程序计数器（PC），在x86中也称为指令指针。每次CPU执行一条指令时，它都会自动递增PC，使其指向下一条指令。例如，假设我们在x86中执行一个nop指令，这是一个使用单个字节编码的非操作指令。执行nopin指令后，PC将前进1，因为那是nop的大小并将其前进1会导致它指向下一条指令。有一些特殊的指令以不同的方式修改PC：jmp（即＆＃34; jump＆＃34;），调用和ret（即＆＃34; return＆＃34;）。通常，使用立即操作数调用jmp和call，该操作数是用于调整PC的字节数偏移量，而ret没有参数。

我们将从jmp开始，因为这是这些说明中的更简单的方法。像jmp $ 15这样的指令意味着将PC设置为比当前值高15，换言之，它将PC向前跳转15个字节的指令值（此处是逗AT＆amp; T语法，这就是为什么15的前面带有$的原因-这表示它是立即数，而不是内存地址。如果操作数为负值，也可以向后跳转。通常，此指令用于实现基本的流控制结构，例如if，else，for等。

jmp的表弟是call，它的工作原理与jmp完全相同，除了它还有将PC推入堆栈的副作用。更精确地说，在指令执行之前先对PC进行onx86调整，因此，当调用将PC压入堆栈时，实际上是在调用指令之后压入指令的地址。将PC推入堆栈，以便调用的函数可以返回到正确的位置。要从函数返回，函数将执行ret，后者将栈顶值弹出，然后跳回该位置。 call和ret都是简单的便捷说明，就像执行push + jmp或pop + jmp一样。

void foo（int x）{int y = x * 2; printf（＆＃34; x =％d，y =％d \ n＆＃34 ;, x，y）;}

如果使用gcc -O1编译此代码，它将以明显的方式为此功能生成程序集。外观如下：

（gdb）disas foo函数foo的汇编代码的转储：0x0000000000000000＆lt; + 0＆gt ;: sub $ 0x8，％rsp 0x0000000000000004＆lt; + 4＆gt ;: mov％edi，％esi 0x0000000000000006＆lt; + 6＆gt ;: lea（％rdi， ％rdi，1），％edx 0x0000000000000009＆lt; + 9＆gt ;: mov $ 0x0，％edi 0x000000000000000e＆lt; + 14＆gt ;: mov $ 0x0，％eax 0x0000000000000013＆lt; + 19＆gt ;:呼叫0x18＆lt; foo + 24＆gt; 0x0000000000000018＆lt; + 24＆gt ;:添加$ 0x8，％rsp 0x000000000000001c＆lt; + 28＆gt ;: ret

我不会解释其中的每一行，而是会解释重要的位。第一个指令sub $ 0x8，％rsp在栈中为我们C代码中的变量y保留了8个字节的空间。倒数第二条指令是添加$ 0x8，％rsp，它将堆栈指针调整回其原始值，而last指令是ret，它以前面描述的方式返回调用方（即，从堆栈中弹出返回地址并跳转到它） 。通常，在调用ret之前，函数始终需要撤消对堆栈指针（％rsp）所做的任何调整，以便ret在返回之前弹出正确的值。在此示例中，还有一个有趣的调用指令；这实际上是一个虚假的操作数，因为编译器仅看到printf（）的前向声明，并且不知道它实际在哪里。在最后的链接步骤中，将对调用指令的操作数进行更新，以使其调用libc。

（gdb）disas foo函数foo的汇编代码的转储：0x0000000000000000＆lt; + 0＆gt ;: mov％edi，％esi 0x0000000000000002＆lt; + 2＆gt ;: lea（％rdi，％rdi，1），％edx 0x0000000000000005＆lt; + 5＆gt; ;：xor％eax，％eax 0x0000000000000007＆lt; + 7＆gt ;: mov $ 0x0，％edi 0x000000000000000c＆lt; + 12＆gt ;: jmp 0x11

在此示例中，我们看到编译器通过使用lea将y的值直接加载到相关寄存器（在本例中为％edx）而不是在堆栈上使用空间的方式优化了堆栈代码，但这并不是真的与TCO相关。与TCO相关的有趣部分是功能的结尾。以前我们打过电话的地方，现在有了一个跳；而且值得一提的是，不再进行任何改造。再一次，jmp的操作数只是一个伪值，在链接时将被链接器替换。

这是尾叫优化。尾部调用优化发生在编译器立即将调用转换为ret，然后转换为单个jmp时。这种转换节省了一条指令，更重要的是，它消除了由调用和ret完成的隐式推/弹出操作。而且您的编译器会一直这样做，而不仅仅是递归函数调用。通常，只要某个函数的最后一条指令是另一个函数调用，就会应用TCO。那么它是怎样工作的？

在优化版本中，jmp指令将直接跳转到printf，而无需将PC推入堆栈。想象一下，这是一个更大程序的一部分，以及其他一些名为foo的子程序。输入foo后，调用者的地址将在堆栈的顶部。当foo在最后执行jmp时，它将直接跳到printf代码，并且foo的调用者的地址仍将位于堆栈的顶部。 printf函数本身具有自己的ret，可用于返回。由于foo不会将其自己的地址压入堆栈，因此当printf执行其ret指令时，它将实际上从堆栈中弹出与foo调用者地址相对应的值。

如果函数进行了递归尾调用，则将完全按照上面的方法应用TCO。一个简单的编译器实际上可以将递归TCO与非递归TCO完全相同，而无需任何特殊逻辑。为了好玩，让我们看一下阶乘的尾调：

/ *阶乘的尾调用递归助手* / int factorial_accumulate（int n，int accum）{return n＆lt; 2？ accum：factorial_accumulate（n-1，n * accum）;} int factorial（int n）{return factorial_accumulate（n，1）; }

请注意，这不是实现为n * factorial（n-1）的阶乘的朴素版本，因为在朴素的版本中，该函数需要进行递归调用，然后在返回之前乘以递归调用的返回值，这意味着递归通话不在尾部位置。

（gdb）disas factorial函数析构函数的汇编代码转储：0x0000000000000040＆lt; + 0＆gt ;: mov $ 0x1，％eax 0x0000000000000045＆lt; + 5＆gt ;: cmp $ 0x1，％edi 0x0000000000000048＆lt; + 8＆gt ;: jle 0x60＆lt; factorial + 32＆gt; 0x000000000000004a＆lt; + 10＆gt ;: nopw 0x0（％rax，％rax，1）0x0000000000000050＆lt; + 16＆gt ;: imul％edi，％eax 0x0000000000000053＆lt; + 19＆gt ;: sub $ 0x1，％edi 0x0000000000000056＆lt; + 22＆gt; ：cmp $ 0x1，％edi 0x0000000000000059＆lt; + 25＆gt ;: jne 0x50＆lt; factory + 16＆gt; 0x000000000000005b＆lt; + 27＆gt ;: ret 0x000000000000005c＆lt; + 28＆gt ;: nopl 0x0（％rax）0x0000000000000060＆lt; + 32＆gt ;:汇编程序转储的结尾。 ;：mov％esi，％eax 0x0000000000000022＆lt; + 2＆gt ;: cmp $ 0x1，％edi 0x0000000000000025＆lt; + 5＆gt ;: jle 0x3b＆lt; factor_accumulate + 27＆gt; 0x0000000000000027＆lt; + 7＆gt ;: nopw 0x0（％rax，％rax，1）0x0000000000000030＆lt; + 16＆gt ;: imul％edi，％eax 0x0000000000000033＆lt; + 19＆gt ;: sub $ 0x1，％edi 0x0000000000000036＆lt; + 22＆gt; ：cmp $ 0x1，％edi 0x0000000000000039＆lt; + 25＆gt ;: jne 0x30＆lt; factoral_accumulate + 16＆gt; 0x000000000000003b＆lt; + 27＆gt ;：汇编程序转储的retEnd。

这实际上很有趣！一方面，在factorialit的代码中完全内联了factorial_accumulate逻辑，因此factorial根本不调用factorial_accumulate。但是，编译器仍在我的目标文件中生成了factorial_accumulate的代码。如果您花一点时间通读此书，则可以看到factorial_accumlate的工作原理。前三个指令是对递归基本情况（即n <2）的mov，cmp，jle序列测试，在此基本情况下跳转到ret指令。当条件n ＜ 2为假，则代码进入指令循环imul进行乘法运算，将n减1，再执行另一个cmp以查看是否已击中基本情况，并且未击中返回具有基本情况的imul指令的jne 。当击打基本情况时，枪管会掉到后座。

阶乘的代码几乎完全以相同的方式工作，并且您将注意到基本相同的指令序列。一些寄存器是不同的，因为阶乘是用一个参数而不是两个参数来调用的。由于某种原因，它有两个ret语句，大概是出于对齐的原因（这也是为什么nopw和nopl指令在此处，它们是仅用于对齐目的的无操作指令的原因）。