随笔

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

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

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

概念:叶过程

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

我们当然希望他们都是叶过程,这样就不需要这一章了。但是显然不会,我们会在一个函数中调用另一个函数,这要求我们保留正在执行的函数的同时,还要给要调用的函数提供寄存器……如果需要参数,我们就要提前将参数装入寄存器(在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存储的地址
(0)

本文由 橙叶博客 作者:FrankGreg 发表,转载请注明来源!

热评文章

发表评论