《计算机组成与设计 硬件/软件接口》2.8.2 嵌套过程 非叶过程的调用（以递归计算阶乘为例）

Jan. 21, 2020

来源：《计算机组成与设计 硬件/软件接口》第二章 指令：计算机的语言，代码、思路均摘抄自此书

从这篇文章里，我们来从汇编层面理解函数调用的机制。

概念：叶过程

叶过程：不调用其他过程的过程

我们当然希望他们都是叶过程，这样就不需要这一章了。但是显然不会，我们会在一个函数中调用另一个函数，这要求我们保留正在执行的函数的同时，还要给要调用的函数提供寄存器……如果需要参数，我们就要提前将参数装入寄存器（在MIPS中为$a0~$a3），如果有返回值，我们要将要在函数返回时将返回值装到寄存器里……

解决寄存器的问题

为了具体搞清楚我们在函数中调用函数时发生了什么，书上提供了一个典型的函数调用的情况：使用递归方法计算阶乘。 下面我都把函数叫成了过程。

把这段C代码翻译成汇编代码。

int fact(int n){
    if(n>1) reutrn (1);
    else return (n * fact(n-1));
}

对于几个专用的寄存器，如存放地址的$ra，存放参数的$a0~$a3。对于上面的过程，显然不存在叶过程，就是每个过程都可能会再调用一个过程（这里就是他自己），我们希望的是在迭代的过程中保留每一次调用时的状态，单靠寄存器显然不现实。比如存放调用位置的下一条指令的地址的$ra，我们肯定会在下一次调用时再次用到它，但是我们还不能让它之前的值直接被覆盖，因为最后我们要一级一级地返回到最初调用的位置。

为了保留寄存器的值，我们要将它们暂存入存储器中，留待下次使用。我们使用栈来存储。控制栈地址的指针是$sp。MIPS中的栈由高地址向低地址存储，

所以第一步，就是将可能将要被覆盖的寄存器存栈。

fact: addi $sp, $sp, -8 # 让栈向低地址延伸8个字节（两个字），为即将存入的两个寄存器的值留出空间
sw   $ra, 4($sp)  # 将返回地址存到栈中
sw   $a0, 9($sp)  # 将第一个参数存到栈中

好了，如果我们之后要调用某一个过程，尽管让它去使用$ra和$a0这两个寄存器，因为我们已经提前将他们的值保存到存储器中了。

接下来是if语句

slti $t0, $a0, 1     # 测试n是否小于1，小于则置位，结果保存在$t0【if(n<1) $t0 = 1 else $t0 = 0】
beq  $t0, $zero, L1  # 若$t0=0（即n≥1），则跳往else。否则继续往下执行
# 下面就是（n<1的情况，这时候该return了）
addi $v0, $zero, 1   # $v0 = 1，这是返回值
addi $sp, $sp, 8     # 栈退出2个字，即栈地址向高处走8个字节，栈地址+8
# 按理说，我们在这儿应该将之前存入栈的值都恢复出来，但是这里没有必要了，因为我们并没有在之后覆盖它们
jr   $ra             # 返回调用者[1]

接下来是else语句

L1: addi $a0, $a0, -1   # 计算表达式(n-1)的值，存入参数寄存器$a0供接下来的调用，
                        # 这里我们就覆盖了参数寄存器的值，所以在后面要恢复它
jal fact                # 调用fact
                        # jal指令（跳转和链接指令）会将自己所在的位置的下一条指令的地址保存到寄存器$ra中
                        # 所以这里实际上覆盖了$ra，也要在后面恢复它

在n<0之前，程序会在上面的代码间循环，最后一次循环结束后，栈的状况大概是这样

地址	栈
高地址	$ra （第一次调用）
	n
	$ra () （星号在下一个代码块中，指向指令的地址）
	n-1
	$ra ()
	.....
	$ra (*)
低地址	0

恢复参数的过程 （我们观察前面的指令，当我们最后带着小于1的n再一次调用fact时，函数将返回到$ra，$ra存放的即是上一个代码块最后一条指令jal fact的下一条指令，也就是下面第一条指令）

lw $a0, 0($sp)    # 恢复参数*
lw $ra, 4($sp)    # 恢复返回地址
addi $sp, $sp, 8  # 栈地址加8，即弹出两个字

计算最终的值

mul $v0, $a0, $v0  # 乘法指令
jr  $ra            # 无条件跳转，跳到$ra存储的地址