MIPS 中的子程序和函数

在所有编程语言中，函数可能是最基础的单元。它给了我们最简单的程序抽象的形式。它提供了接口（如原型），并且允许我们在不知其实现方式的情况下使用函数。

因此，汇编语言必须提供机制来实现函数就可以说得通了。为了区分编程语言和汇编语言中的函数，我把汇编语言中的函数称为子程序。在任何情况下，C 语言中的函数和汇编语言中的子程序都有着不同之处。如果我不小心将其称为函数，我实际上是指 MIPS 子程序。

在一个子程序背后有两种思想。

你必须可以从任何地方调用子程序。
一旦子程序完成，其必须返回调用子程序的地方。

我们将看看这些是如何实现的。

合作

调用子程序包含两个参与者：调用者（caller）和被调用者（callee）。调用者调用子程序。调用者的工作是为子程序设置参数，跳转到子程序。在这时，被调用者接手。

被调用者就是调用者调用的子程序。被调用者不了解是什么代码调用了它。它只“知道”它被调用了。这和 C 或 C++ 中的一样。当一个函数被调用，它很难知道谁调用了它。在调试器中，你可以查看调用栈，但是通常函数自身不知道。

被调用者使用调用者提供的参数，然后运行。当运行结束后，被调用者保存返回值，将控制（如跳回）还给调用者。

当被调用者的代码被执行时，被调用者可能会调用一个辅助子程序。因此，被调用者可能将变成调用者。因此，调用者和被调用者的概念并不总是清晰划分的。

调用者调用子程序
被调用者是子程序本身，被称为调用者。

这种机制展现了提供参数的调用者，和使用参数运算并返回值，最后回到使用返回值的调用者的被调用者之间的一种协定，也被称为协议（Protocol）。

有限的资源

当你使用 C 或 C++ 或 Java 编程的时候，你习惯于调用使用本地变量的函数。每次你调用函数，就产生新的一系列本地变量。这也是为什么递归函数调用可以运行。每次递归调用使用其自身的本地变量和参数（除非参数一引用的形式传递）。在过程化的语言中，这将使编写函数变得更容易。

当你使用汇编语言编程时，在程序中只有一系列的寄存器可以使用。这些寄存器实际上相当于全局变量。很容易在调用子程序时认为，当子程序调用结束后，寄存器中的值保持不变。

然而，这么想你就错了。当你调用子程序时，除非另有约定，你必须认为子程序将使用所有的寄存器（除了栈指针）。因此，如果你调用子程序，保存在寄存器里的值可能会被覆盖。毕竟，被调用的子程序也需要使用寄存器，但只有一套寄存器可以使用。

你是被调用者

MIPS 将 8 个寄存器 $s0 - $s7 设计为被保留的寄存器（saved register）。如果使用这些寄存器，将由被调用者来保持这些寄存器的值。这将不会被 CPU 自动执行。这仅仅是 MIPS 程序员遵守的惯例。

这看起来是一个好主意。假设，你正在编写子程序 FOO，子程序 FOO 调用子程序 BAR。所以，你认为“我们将要使用寄存器 $s0 - $s7，因为被调用者保存了他们。因此当我调用 BAR，BAR 将为我保存这些寄存器”。因此，认为没有必要保存这些被保留。

除了这不是正确的看法。任何子程序都可以成为调用者和被调用者。事实上，你开始的看法，将你想象成被调用者。毕竟，你提供了一个子程序给其他人（也可能是你自己）调用。很容易将你自己当作是调用者，但是要将自己先当作被调用者。

因为你现在将自己当作是被调用者，下面这些是你必须做的：

决定你要使用哪些被保留的寄存器
将这些被保留的寄存器中的值保存到栈中
使用被保留的寄存器，运行子程序代码
在从子程序调用返回前，取出栈中被保留的寄存器的值
返回调用你的那个子程序。

假设你处在步骤 3。你将被保留的寄存器的值保存在栈中，然后运行代码。你觉得调用一个子程序。你需要再保存一次被保留的寄存器吗？这时，你可以就自己当作调用者，因此你不必再次保存寄存器。事实上，你已经在步骤 2 保存了它们。

你将要调用的子程序将保存其所要用到的寄存器到栈中，可能与你保存的寄存器不同。不需要担心，因为这由子程序来决定。

因此，在编写子程序时正确的心态应该是认为“我是被调用者”。

栈

如果寄存器是共享的，同时你不指望子程序保存寄存器的值，你该怎么做，来为你的子程序保留一些其他程序不会覆盖的内存片段。

通常来说，每一个子程序使用一部分栈，并认为每一个子程序将只使用其自身的那一部分栈。

让我们看看在一次调用中发生了什么。

调用者将参数压入栈中（调用者栈框架）
调用者将返回值的地址压入栈中（调用者栈框架）
被调用者在调用者的栈框架中访问参数
被调用者为本地变量开辟空间（被调用者框架）
被调用者自身可能调用其他子程序
当被调用者计算出返回值，其将返回值保存在栈中调用者的那部分中。记住，调用者在栈中为返回值保留恋空间。
被调用者将栈指针复原到其被调用前的指向。因此栈指针现在指向返回值。
调用者取得返回值，最终将返回值和参数弹出栈。

这种想法是相当古老的，也是 MIPS 解决子程序调用的方法。值得上面的方法其与 MIPS 实际使用的方法对照，看看其是如何工作的。

在 MIPS 中，

调用者将参数保存在寄存器 $a0 - $a3 中。其总共能保存4个参数。如果有更多的参数，或者有传值的结构，其将被保存在栈中。
调用者不需要将返回值的位置压入栈中。寄存器 $v0 和 $v1 来保留返回值。
被调用者从寄存器中访问参数和返回值。
如果需要保存寄存器（只有当其要调用子程序时），被调用者在栈中开辟空间。
被调用者自身可能调用子程序
当被调用者计算出返回值时，将其保存在寄存器 $v0（如果需要，和 $v1 中）。
被调用者将栈指针复原到其被调用前的指向。因此栈指针现在指向返回值。
调用者从 $v0 中取回返回值。如果需要调用其他子程序，需要将返回值保存在栈中（否则，其将在下一个子程序调用中被覆盖）。

每一个子程序在运行的时候将保留一部分栈供自身使用。这被称为栈框架（stack fram）。通常，子程序只使用自身的栈，但当被调用者需要访问调用者传入的参数时例外。参数被认为是调用者栈的一部分（你可以将其视为共享的）。

对一个子程序，可能有不止一个栈框架。例如，递归函数对每一个递归调用都有一个栈框架。子程序不必是递归的，因为有两个以上的与子程序相关的栈框架。

例如，你可能有一个函数 findMin() 来计算一个数组的最小值。findMin() 可能在 foo() 中被调用，foo() 之后调用 bar()，而bar() 自身也调用 findMin()，因此 findmin() 在调用栈中有两个栈框架，即使其中没有一个函数是递归的。

在一个子程序调用时什么是必须发生的

让我们假设你需要调用子程序 QUIKSORT。

我们需要做什么呢？如果是 C，你必须传两个参数给子程序，然后调用。

让我们看看它是如何工作的。

	.... | # Set up arguments
	1000 |    j QUICKSORT    # Call QUICKSORT
	.... | ....
	.... | ....
	2000 | QUICKSORT:  # Code for quicksort

在上面的图中，我将内存地址写在左侧。其显示了你保存在内存中的指令。假设在地址 1000 调用了 QUICKSORT。现在我们使用“j”指令调用它。

快速排序的代码开始于地址 2000。因此跳转到 QUICKSORT 意味着将程序计数器（program counter）的值改为 2000。程序计数器是一个隐含的寄存器，保存了当前指令的地址。

好的，目前为止，一切正常。我们成功地跳转到了正确的子程序。QUICKSORT 做了其需要做的，然后它将跳转回来。

除了，我们将要跳转到哪里？

程序计数器没有保存其跳转的历史。当我们在 QUICKSORT 中时，我们不知道我们怎么到那里的。唯一知道的这个信息的地方只有子程序被调用的地方。

因此，当我们在地址 1000 跳转时，我们知道我们需要返回到哪里。因此，我们需要将信息保存，以便能返回到那里。

调用子程序

调用子程序最终的指令是 jal，意思是“跳转并链接”（"jump-and-link"）。

jal 将标记（label）作为操作数。这个标记是子程序在内存中的地址。汇编器将标记翻译为地址。

跳转到那个地址意味着更新程序计数器为子程序的地址。

jal 将返回地址保存在寄存器 $r31 中。这个寄存器也被称为 $ra（“ra”表示返回地址（return address））。

所以我们用 jal 代替 j。

	.... | # Set up arguments
	1000 |    jal QUICKSORT    # Call QUICKSORT
	.... | ....
	.... | ....
	2000 | QUICKSORT:  # Code for quicksort

我们怎么知道什么东东保存到31号寄存器中？

我们要保存地址1000。按照上面的方法，一旦 QUICKSORT 子程序结束，它能够返回调用它的那个指令，即保存在地址 1000 的那个指令。

然而，这样做就太傻了。地址 1000 保存了 jal 指令，我们将会不停地调用相同的子程序。

我们相应执行内存中下一个指令。因为每一个 MIPS 指令使用 4 字节，指令的地址即为 1000 + 4 = 1004。

所以，1004 保存在 31 号寄存器中。

使用 jr 返回到调用者那里

我们有了 jal 调用子程序，但是一旦我们在子程序中要返回，我们需要跳转回去。

我们要跳转到哪里？到 31 号寄存器里保存的地址里。我们要怎么跳转？

有一个特殊的指令能够跳转到保存在寄存器里的地址上。这就是 jr，意思是“跳转到寄存器”（"jump register"）。

在子程序 QUICKSORT 末尾，我们要调用 jr $ra。

	2000 | QUICKSORT:  # Code for quicksort
	.... | .....
	.... | .....
	20ff |             jr \$ra  # Return back

子程序调用辅助子程序时的问题

你可能已经注意到一个问题。当我们使用 jal 调用 QUICKSORT 时，参数被传到 $a0 - $a3，返回地址保存在 $ra。

要是 QUICKSORT 调用了一个辅助子程序 HELPER，怎么办？

让我们先定义一个辅助子程序：

辅助子程序是任何一个在子程序中 jal 调用的子程序。

当 QUICKSORT 调用 HELPER 时，使用寄存器 $a0 - $a3 将参数被传递给 HELPER，jal 将覆盖返回地址。

这是汇编语言的一个标准问题。寄存器对所有子程序共享。当你调用一个辅助子程序时，其将使用和你一样的寄存器。

考虑什么将被保存在栈中

当你编写一个子程序时，你应该决定什么将被保存在栈中。

这是一些建议：

如果子程序是一个叶子过程，即其将不会有 jal 指令，那么将简单了。你不必在栈中保存任何寄存器，除了 $s0 - $s7。
如果子程序有 jal 指令，那么列出当前子程序正在使用的寄存器。至少，你要保存 $ra，因为 jal 覆盖了它。
然后问问你自己，在调用子程序后你是否需要使用这些寄存器。答案通常是yes，所以他们要压入栈中。
如果有可能调用至少两个子程序，你需要在每一个子程序调用结束后保存其返回值。
一旦你要退出程序时，你要复原返回地址，调整栈指针。

为啥你需要在栈中保存返回值？让我们看看一个调用了两个辅助子程序的子程序的例子，BAR 和 CAT：

	FOO:  ....
		  ....
	  	  jal BAR
	  	  move \$t0, \$v0   # Save return value to t0
	  	  ....
	  	  jal CAT
	  	  add \$v0, \$v0, \$t0   # Uh oh! Error! \$t0 may have changed!

假设你以一个程序员的身份阅读这段代码。在第一个注释中，$v0 是被保存的到一个临时寄存器。这个程序员知道 jal CAT 将覆盖 $v0。但是，其不会真正被保存。

为啥？

因为CAT子程序可能会覆盖 $t0！又一次你必须假设一个行为良好的子程序可能会覆盖任何一个寄存器，除了被保留的寄存器和栈指针。一个差的子程序可能会更改被保留的寄存器和栈指针，但是我们假设这不会发生，否则，我们编程时将十分困难。

一个解决方法是使用被保留的寄存器 $s0，但是这意味着我们必须使用另一个规则。如果你使用被保留的寄存器，你必须在使用前将其保存到栈中。因此，我们必须保存 $s0 。另一种方法是使用栈。

所以，解决方法是：

	FOO:  ....
		  ....
		  jal BAR
		  sw  \$v0, 4(\$sp)     # Save return value to stack
		  ....
		  jal CAT
		  sw  \$t0, 4(\$sp)     # Get old return value from stack
		  \$v0, \$v0, \$t0   # Fixed problem!

我们将返回值保存在 4($sp) 中。想必，你会在栈中选一个好位置保存它。4($sp) 只是一个随意的选择。

什么时候保存并复原栈？

作为一个习惯问题，程序员们经常在子程序开始时将寄存器保存在栈中。这是一个好习惯，因此你必须谨记。在调用 jr $ra 前他们从栈中复原。

当你要返回到调用者那里时，问问你自己什么值是真的需要从栈中复原的。有人会争论使用哪一种方法参数寄存器需要复原。通常，你可以假设参数允许被覆盖。

当然，$ra 需要调整，栈指针也是如此。如果你使用框架指针（见下一节），你也必须复原框架指针。

记录什么需要从栈中复原，能为你节省一些步骤。但是，通常复原多余的寄存器不会有什么损失（除了一些循环）。

返回值是有技巧的

解决辅助子程序的返回值是最具技巧性的，特别是在调用两个（或更多）的辅助子程序时（即，之前的 BAR 和 CAT）。

你不能在最初保存 BAR 的返回值，因为你还没有调用 BAR。你必须等到你调用辅助程序的时候。在 jal 后，你可以将返回值保存到栈中。然后，你调用第二个辅助子程序（也就是，CAT），一旦你调用结束，你就能能从栈中取回 BAR 的返回值。

如果没有像 CAT 一样的第二个辅助子程序，那么没有必要保存第一个辅助子程序（即，BAR）的返回值到栈中。

Pascal 的函数？

我们讨论的大部分涉及类 C 的语言的函数/子程序。C 不支持像 Pascal 中支持的在函数中嵌套其他函数。Pascal 的函数可以嵌套，内部的函数可以访问外部函数的参数。

栈结构更加复杂。我们不想讨论其原理。关键是设计一个比我们正在使用的更加复杂的栈。我们选择 C 的栈风格，因为它更加简单，它让我们在汇编语言中写与 C 类似的子程序。

总结

调用子程序，是调用者和被调用者之间的协作。

在 MIPS 中，

调用者将参数保存在寄存器 $a0 - $a3 中。其总共能保存4个参数。如果有更多的参数，或者有传值的结构，其将被保存在栈中。
调用者使用 jal 加上子程序的标记。返回地址保存在 $ra 中。
返回地址是 PC + 4，PC 是 jal 指令的地址。
如果被调用者使用框架指针，它通常将其设置为栈指针。旧的栈指针必须在之前被保存到栈中。
被调用者通常在开头将其需要使用的寄存器保存到栈中。如果被调用者调用了辅助子程序，必须将 $ra入栈，同时也必须将临时寄存器或被保留的寄存器入栈。
当子程序结束，返回值要保存在 $v0 - $v1 中。
被调用者使用 jr $ra 返回到调用者那里。

版权声明
本文转载自Jiarong Wei的博客, 由其翻译自Subroutines/Functions in MIPS