本节书摘来自华章计算机《计算机系统：系统架构与操作系统的高度集成》一书中的第2章，第2.8节,作者：（美）拉姆阿堪德兰（Ramachandran, U.）（美）莱希（Leahy, W. D.）著， 更多章节内容可以访问云栖社区“华章计算机”公众号查看。
2.8 编译函数调用
编译高级语言中的过程调用或函数调用有一些需要特别注意的事情。
首先，我们来回顾程序员脑海中过程调用的模型。程序在main函数中调用了函数foo。程序的控制流转移到了该函数的入口处。退出foo时，控制流返回到main函数中紧接着调用foo函数的语句。下面是这个模型的样子：
首先我们定义几个术语：调用者（caller）指的是做出过程调用的实体（在这个例子中是main函数）；被调用者（callee）是被调用的实体（例子中的foo）。
让我们一一列出编译一个过程调用的步骤：
1）保证调用者的状态（即调用者使用的寄存器）被保护好以便从过程调用中返回时得以恢复。
2）将实际参数传递给被调用者。
3）记住返回地址。
4）将控制权转交给被调用者。
5）为被调用者的局部变量分配空间。
6）从被调用者接收返回值并传给调用者。
7）返回调用点。
我们现有的指令集体系结构的功能能够满足前面这些要求吗？为了回答这个问题，我们讨论一下列表中的每一项。我们首先在2.8.1节中探讨保存调用者状态的结果，然后在2.8.2节考虑余下的杂项。
2.8.1 调用者的状态
首先定义什么是调用者的状态。执行被调用者代码所需的资源有内存（被调用者的代码和数据）和处理器中的寄存器（所有的算术/逻辑指令会都用到它们）。编译器会确保调用者和被调用者使用不同的内存（例外情况是高级语言的语义要求的共享内存）。所以，处理器的寄存器中的内容才是我们需要担心的“状态”，因为当调用者调用被调用者时，它自身的某些结果正存储在寄存器中。因为我们不知道被调用者将使用哪些寄存器，谨慎的做法是在过程调用前先将它们都保存起来，然后在返回时再恢复。
现在我们需要一个地方来保存这些寄存器。我们先尝试硬件的解决方案。我们引入一个影子寄存器组，我们将在调用前把寄存器保存到里面，从过程中返回时再将这个影子寄存器组中的值恢复到处理器的寄存器中（见图2-7）。
我们知道，在模块化的代码中，过程的调用是很频繁的，因此快速地保存/恢复状态非常重要。鉴于影子寄存器组位于处理器内部，而所有的保存/恢复操作都发生在硬件层面，所以影子寄存器组看起来是个好主意。
这个想法的最大问题在于，它假设被调用的过程不会再进一步调用其他过程了。根据我们写高级语言程序的经验，这个假设完全站不住脚。实际上，我们需要与嵌套过程调用的层数一样多的影子寄存器组（见图2-8）。
图2-8 嵌套的过程调用中状态的保存和恢复。将影子寄存器组的想法扩展至一个嵌套的过程调用序列
我们来讨论硬件实现这些影子寄存器组的意义。嵌套过程调用（即图2-8中的链）的层数是程序的动态属性。硬件解决方案必须是有限的，与影子寄存器组的数量相关。并且由于成本和复杂性的原因，这个数量不能任意大。尽管如此，还是有的体系结构，如SPARC，为此实现了一种称为寄存器窗口的硬件机制。SPARC提供了128个硬件寄存器，但任意时刻都只有32个是可见的。那些不可见的寄存器就成了影子寄存器组，像图2-8所示的那样工作。
图2-8还向我们提示了一种可能的软件实现方案：使用你们可能已经在数据结构中学习过的栈。我们在调用点将状态保存入栈中，在返回的时候恢复。因为栈具有后进先出（LIFO）的特性，它正好满足了嵌套过程调用的需求。
栈可以通过软件的抽象在内存中实现，所以就不受嵌套层次的限制了。
编译器需要维护一个指向栈的指针以保存和恢复状态。这并不需要在体系结构上添加任何新东西。编译器会选择处理器中的一个寄存器作为专用的栈指针。注意，这并不是体系结构必需的要求，而仅仅是为编译器提供方便。另外，每个编译器都有选择不同寄存器作为栈指针的自由。这指的是编译器将不会使用这个寄存器来保存程序变量，因为栈指针已经被保留作为编译器内部的专用功能了。
刚才我们通过选定一个寄存器作为栈指针来说明了软件使用寄存器的惯例。
硬件解决方案的一个好处是，它是用硬件实现的，所以很快。现在我们用软件方式来实现栈，代价是每次过程调用和返回时需要在内存和处理器寄存器之间来回搬运数据。想想看能不能既保持软件方式的弹性，又具有硬件方式的性能优势呢？软件方式无法达到硬件方式的高速，但确实可以减少那些浪费的部分。
先探讨一下在每次调用和返回的时候是否真的需要保存或恢复所有的寄存器。之前的途径是调用者（即代表调用者的编译器）负责保存和恢复。如果被调用者根本没有使用任何寄存器，那么整个保存和恢复寄存器的工作都白做了。因此，我们可以把这个工作交给被调用者，让它在运行时保存将要使用的寄存器而在过程返回时恢复它们。同样地，如果调用者在过程返回后根本不使用这些寄存器里的值，那么这个工作也白费了。
为了走出这个困境，让我们再扩展一下软件惯例的想法。这里打个比方来帮助大家理解。这是一个关于两个懒惰的室友的故事。他们都想做尽可能少的家务，但是，他们每天都得吃饭，所以最终他们达成了一个协议。他们有一个公用的盘子，每个人有各自的几个碟子。他们决定遵守的规则如下：
自己的碟子永远都不需要清洗。
如果使用了别人的碟子，那么每次用完后必须洗干净。
盘子并不保证是干净的，所以每个人在用盘子之前，如果需要的话，最好是自己洗一遍。
有了这个惯例，每个人的工作都只剩一点了—如果他们不使用盘子和别人的碟子，那么根本就不需要工作！
过程调用的软件惯例采取的方式和这个懒人比喻差不多。当然，过程调用与这个比喻不同的是，它是不对称的（存在着调用者与被调用者的秩序）。调用者获得寄存器中属于他自己的一个子集（称为s寄存器组）。调用者可以任意使用这些寄存器，不用担心被调用者会冲掉里面的数据。被调用者如果需要使用s寄存器组，则需要保存和恢复它们。与盘子类似，还有一部分寄存器（称为t寄存器组）是调用者和被调用者所共有的。它们使用这些寄存器都不需要保存或恢复。现在，正如懒人比喻里的那样，如果调用者在过程返回后不使用t寄存器组中的值，那么在过程调用时就不需要干活。同样地，如果被调用者不使用s寄存器组，那么它也不需要考虑保存和恢复的事情。
寄存器的保存和恢复将在栈中实现。当我们讨论完过程调用和返回的其他工作之后，还会接着补全关于过程调用和返回的软件惯例。
2.8.2 过程调用剩余的工作
1）参数传递 一种权宜之计是，使用处理器中的寄存器来传递参数。再一次地，编译器将建立一套软件惯例，将某些寄存器保留供传参专用。
当然，过程所需的参数个数可能会超过这些寄存器数量的限制。这种情况下，编译器会使用栈来传递多出的这些参数。软件惯例保证被调用者借助于栈指针知道在栈中的何处取得参数。
2）记住返回地址 我们在之前讲分支指令时提到过处理器中的程序计数器（PC）。迄今为止我们介绍过的高级语言结构都不需要记住自己位于程序何处。所以，现在需要一条新的指令将PC值保存在一个众所周知的地方，以便能在过程返回中使用它。
我们引入一条新的指令：
这条指令的语义如下：
将返回地址保存在rlink中（可以是任意一个处理器的寄存器）。
将PC置为rtarget中的值（即被调用者的起始地址）。
我们回到软件惯例的问题上来。编译器会指定一个寄存器作为rtarget来保存目标例程的地址，而指定另一个寄存器作为rlink来保存返回地址。也就是说，这些寄存器将不能用来存放普通的程序变量。
因此，在调用点，过程调用被编译为
从过程中返回的方式很直接，因为我们已经有无条件跳转指令了，
完成了从过程调用中返回的任务。
3）将控制权移交给被调用者 第3步是通过JAL指令将控制权移交给被调用者。
4）被调用者局部变量的空间 使用栈可以很方便地为被调用者所需的局部变量分配空间。软件惯例保证了被调用者借助于栈指针可以方便地找到局部变量的所在。
5）返回值 一个方法是编译器保留某些寄存器用于返回值。与参数传递时相同，如果返回值超出了这些寄存器能够保存的能力范围，剩余的返回值将通过栈进行传递。软件惯例保证了调用者借助于栈指针能够找到返回值。
6）返回到调用点 正如前面提到的，简单的一条跳转到rlink的指令就能将控制权交回到调用点。
2.8.3 软件惯例
为了让讨论更具体些，我们这里介绍一套处理器寄存器及其使用的软件惯例：
寄存器s0～s2是调用者的寄存器。
寄存器t0～t2是临时寄存器。
寄存器a0～a2是传参寄存器。
寄存器v0用于保存返回值。
寄存器ra用于保存返回地址。
寄存器at用于保存目标地址。
寄存器sp用作栈指针。
在展示如何使用这些软件惯例来编译过程调用之前，我们需要强调一些栈的细节。许多编译器采用的惯例是，栈从高地址往低地址增长。基本的栈操作如下：
压栈（push）减小栈指针并将值保存于栈指针指向的内存中。
弹出（pop）取出栈指针指向的值并增大栈指针。
图2-9～图2-20展示了编译器产生的运行时生成栈帧的代码。在所有的图中，低地址是栈的顶部而高地址是栈的底部，与栈从高地址往低地址增长一致。
2.8.4 活动记录
栈中与当前执行的过程有关的一部分区域被称为该过程的活动记录。活动记录是调用者与被调用者之间进行通信的区域。图2-9～图2-19显示了调用者和被调用者之间如何建立活动记录，被调用者如何使用活动记录，以及返回时（调用者和被调用者）如何拆除活动记录。依赖于过程调用的嵌套，栈上可能会有多个活动记录存在。但是在任意时刻，都有且仅有一个与当前正在执行的过程有关的活动记录是在活动的。
考虑下面的序列：
图2-21展示了前面这个调用序列的活动记录和栈的情况。
图2-21 调用序列的活动记录。注意，只有最顶端的活动记录才是对当前执行的过程有意义的
2.8.5 递归
对程序员来说，最有力的工具莫过于递归了。我们不需要在指令集体系结构上增加任何东西就能支持递归。栈机制保证了过程的每个实例（无论它们是属于相同还是不同的过程）都拥有一个新的活动记录。当然，能被递归调用的过程必须写成支持递归的代码，这是程序员考虑的范围。指令集为了不需要做任何改变就能支持递归。
2.8.6 帧指针
在程序执行的过程中显而易见的是，必须能够定位放在栈上的所有东西的位置。在程序执行之前，它们的绝对位置是不知道的。很明显它们能够通过用栈指针的偏移量表示出来，但这条途径有一个问题。某些编译器会生成在函数执行过程中（即栈帧已经建好之后）修改栈指针的代码。例如，一些语言支持在栈上动态分配。尽管可以跟踪栈指针的移动，但是这带来的需要额外维护的信息以及在运行时间上的代价决定了这是一个馊主意。常用的解决方案是指定一个通用寄存器作为帧指针，包含在当前函数的活动记录中的一个已知的位置。在函数执行过程中，这个地址是不会改变的。用一个例子来理清这个问题和解决方案。考虑下面的过程：
我们假设栈指针（用$sp表示）在调用foo的第6步（见图2-14）之后的值是100。在第7步中，被调用者为局部变量（a和b）分配了空间。按照栈从高地址向低地址增长的惯例，a被分配在地址96而b被分配在地址92。现在$sp的值是92了。图2-22展示了这个情况。
图2-22 过程中的局部变量分配之后栈的状态。注意现在栈指针的值是92。
foo过程开始执行。“if”语句生成的代码需要将a和b装入寄存器中。这对编译器来说非常直截了当。下面的两条指令
将a和b分别装入寄存器r1和r2中。
注意，如果上一步计算正确的话，下一步会发生什么呢？现在程序新分配了一个变量c，它也是在栈中分配的。然而，这个局部变量的分配并不在foo的执行前（见图2-15，第7步）进行。这是个有条件的分配，只在if语句为真的时候进行。变量c的地址是88，现在$sp的值是88。图2-23展示了现在的情况。
图2-23 变量c分配之后栈的状态，此时对应着过程中的语句（2）。注意现在栈指针的值是92
在if语句块中，我们可能需要加载和存储变量a和b（见代码块中的语句3）。生成变量a和b的正确地址是个诡异的问题。原来变量a对于$sp的偏移量是4，现在，对于当前的$sp来说，偏移量则是8。因此，在语句（3）中为了加载变量a和b，编译器需要生成下面的代码：
当if语句执行完毕之后，c被从栈中释放掉，$sp又变成了92。现在a对于当前$sp的偏移量又是4了。这与图2-22所表示的是一样的。
读者可以看出，栈能够扩大和缩小这个事实使得编译器更难写了。依赖于当前的栈指针，各个局部变量的偏移量都在改变。
这正是选择寄存器作为帧指针的原因。帧指针包含了栈中与被执行过程相关的活动记录的第一个地址，并且在这个过程的执行过程中都不会改变。当然，如果该过程又调用了别的过程，则它的帧指针也需要进行保存和恢复，这由被调用者来完成。因此，被调用者所做的第一件事就是将帧指针保存到栈中，并将当前的栈指针值复制给帧指针。如图2-24所示。
这个帧指针是栈上一个固定的套子（对于一个过程来说），它指向当前执行的过程的活动记录（AR）的首地址。
