[lc3]LC-3 子程序调用与模拟栈调用递归函数[zt]
clq
浏览(426) -
2023-04-10 21:37:23 发表
编辑
关键字:
https://blog.csdn.net/weixin_44176696/article/details/106526201
----------------------------------------------------------------
LC-3 子程序调用与模拟栈调用递归函数
AkagiSenpai
于 2020-06-03 21:48:22 发布 1815
收藏 14
分类专栏： 计算机系统 文章标签： 指针 LC-3 汇编 栈 递归
版权
计算机系统 专栏收录该内容
34 篇文章 95 订阅
订阅专栏
目录
TRAP机制调用子程序
TRAP调用
TRAP返回
例子 TRAP x21 （系统函数）输出字符源码
模拟栈
方法介绍
栈指针
存取数据
函数栈帧结构
一次递归调用需要的语句
汇编代码
运行结果
在LC-3的编程中，有时候需要重复调用一些子程序，但是又不能像c语言一样定义函数，但是LC-3提供了相当的机制供我们使用
TRAP机制调用子程序
在上一篇文章【LC-3简易四子棋（深大计系1实验4） 思路+代码+详细注释】中，我们提到：
对于输入输出，我们通过一些“伪操作”进行“系统调用”来实现读取字符，输出字符，可是这些操作的本质是TRAP机制来完成的调用
在这里插入图片描述
TRAP调用
TRAP将目标中断矢量（也就是trap的操作数，比如TRAP x21操作数是0x21）的高位补0得到一个数x，然后去内存x处寻找下一条指令的地址，即将内存x处的值压入PC寄存器中
比如TRAP x21，内存x0021处，存的是子程序首地址，这个地址会被压入PC
TRAP返回
函数都要返回，那么TRAP会在进入子程序之前，将返回地址存到R7
在一个子程序的最后，必须使用RET指令，即JSRR R7 跳转到R7寄存器对应的地址
这意味着我们不能够在子程序里面不经保存就修改R7的值，这样会使得子程序无法返回，上一篇文章提到的【在一个子程序里不保存R7就调用另一个子程序，最终结果不正确】就是因为这个问题导致的
因为TRAP的操作数只有8位，所以支持256个子程序
例子 TRAP x21 （系统函数）输出字符源码
在LC-3的系统函数中，x21负责输出一个字符，字符的值存放在R0
我们可以看看它的源码，首先找到0x0021内存处，查看真正的起始地址，可以看到是0x0430
在这里插入图片描述
我们跳转到0x0430查看源码
在这里插入图片描述
可以看到，子程序调用第一步就是保存要用的寄存器的值，然后开始读取KBSR键盘输入标志位，死循环直到键盘输入标志位为1，之后读取数据到R0，然后RET，注意所有子程序都要RET
模拟栈
方法介绍
因为LC-3这种调用机制，使得函数只能被调用一层，多层调用需要不断的保存返回地址，而R7将会被覆盖！
因此，递归就难以实现了，但是我们可以通过模拟一个栈，来实现保存函数的参数，返回地址，返回值，来实现递归函数
我们将要实现一个这样的函数来计算等差数列的前n项和
int func(int x)
{
if(x==0) return 0;
return x+func(x-1);
}
1
2
3
4
5
栈指针
我们使用一个地址标号sp来作为栈指针，sp里面存的值表示栈顶在内存中的位置，约定sp永远指向第一个空余的栈位置，如图所示：
在这里插入图片描述
存取数据
如上，因为栈指针的特殊结构，即【指向第一个空闲的栈位置】，我们读取栈顶数据的时候就要小心：
存数据：
数据存入栈指针指向的内存
栈指针++
在这里插入图片描述
取数据：
1.栈指针--
2.取栈指针指向的内存的数据
在这里插入图片描述
函数栈帧结构
我们在函数调用之前，分别压入返回地址，形参x，然后函数处理，弹出形参和返回地址，然后把返回值压栈
在这里插入图片描述
一次递归调用需要的语句
一次调用函数需要以下语句
返回地址压栈
形参压栈
栈指针+2
递归调用
从栈中弹出返回值
汇编代码
.ORIG x3000
LD R0, sp ; 取栈指针到R0
LEA R1, EOC ; R1读取返回地址
AND R2, R2, #0
ADD R2, R2, #10 ; R2载入形参10
STR R1, R0, #0 ; 返回地址压栈
STR R2, R0, #1 ; 形参压栈
ADD R0, R0, #2 ; 栈指针++
ST R0, sp ; 存栈指针
BRnzp func ; 调用
EOC LD R0, sp ; 取栈指针到R0
LDR R2, R0, #-1 ; R2存返回值
ADD R0, R0, #-1
ST R0, sp ; 存栈指针
TRAP x25 ; 程序结束
func LD R0, sp ; 取栈指针到R0
LDR R1, R0, #-1 ; 取栈中的值即参数1到R1
BRz ret0 ; 如果x=0返回0
BRnzp call ; 否则递归
ret0 AND R2, R2, #0
ADD R2, R2, #0 ; R2=0
BRnzp retv
call LD R0, sp
LEA R2, call
ADD R2, R2, #10 ; R2存返回地址
STR R2, R0, #0 ; 返回地址压栈
ADD R0, R0, #1 ; 栈指针++
ADD R3, R1, #-1 ; R3=R1-1
STR R3, R0, #0 ; 参数R3压栈
ADD R0, R0, #1 ; 栈指针++
ST R0, sp ; 指针存回去
BRnzp func ; 递归调用x-1
LD R0, sp ; 递归返回地点
STR R2, R0, #-1 ; 读取栈中的返回值到R2
ADD R0, R0, #-1 ; 弹出返回值
ST R0, sp ; 存栈指针
; 将R2作为返回值压栈
retv LD R0, sp ; 取栈指针到R0
LDR R1, R0, #-1 ; 取参数1到R1
LDR R3, R0, #-2 ; 取返回地址到R3
ADD R2, R2, R1 ; return x+func(x-1)
STR R2, R0, #-2 ; 返回值压栈
ADD R0, R0, #-1
ST R0, sp ; 存栈指针
JSRR R3 ; 返回
sp .FILL 0x4396
.END
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
运行结果
本帖子属于以下条目()
NEWBT官方QQ群1: 276678893
可求档连环画,漫画;询问文本处理大师等软件使用技巧;求档softhub软件下载及使用技巧.
但不可"开车",严禁国家敏感话题,不可求档涉及版权的文档软件.
验证问题说明申请入群原因即可.
