递归调用汇编代码翻译的一些心得

本文最后更新于：2024年4月22日 晚上

前言

教程 函数调用 - 计算机组成教程 (buaa.edu.cn) 中曾介绍过如何将带有递归函数调用的c语言代码翻译成汇编指令。P2课下也涉及了部分需要应用递归的题目，在此总结一下我完成此类汇编翻译的一些心得。

我们在此就以 P2_L0_full_1 - 系统能力课程实验平台 (buaa.edu.cn) 当作例题，简要介绍一下设计思路。

例题1：全排列生成

题干

题目编号 1121-36

题目要求

实现满足下面功能的汇编程序：

  1. 使用mips实现全排列生成算法。

  2. 以0x00000000为数据段起始地址。

  3. 输入一个小于等于6的正整数，求出n的全排列，并按照字典序输出。

  4. 每组数据最多执行500,000条指令。

  5. 请使用syscall结束指令

    1
    2
    li   $v0, 10
    syscall

输入格式

只输入一行，输入一个整数n **(0 < n <= 6)**。

输出格式

按照字典序输出n!行数组，每行输出n个数字，数字之间以空格隔开，每行最后一个数字后可以有空格。

输入样例

1
4

输出样例

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
1 2 3 4
1 2 4 3
1 3 2 4
1 3 4 2
1 4 2 3
1 4 3 2
2 1 3 4
2 1 4 3
2 3 1 4
2 3 4 1
2 4 1 3
2 4 3 1
3 1 2 4
3 1 4 2
3 2 1 4
3 2 4 1
3 4 1 2
3 4 2 1
4 1 2 3
4 1 3 2
4 2 1 3
4 2 3 1
4 3 1 2
4 3 2 1

提交要求

  1. 请勿使用 .globl main
  2. 不考虑延迟槽
  3. 只需要提交.asm文件。
  4. 程序的初始地址设置为Compact,Data at Address 0。

解答步骤

在此分享一下我完成汇编代码的一些思路步骤。

第一步：完成符合要求的C语言代码

C语言的代码与汇编指令具有很高的相似性，如果有一份正确的C语言代码，汇编编程题就相当于一个“翻译题”。

全排列问题的C语言代码如下：（如果对此有疑问的话，可以去网上搜索一下全排列的相关讲解，在此不展开说明）

全排列问题的C语言解答

第二步：一些必要的macro

使用宏可有效提高代码的复用性，提高代码的可读性。

我比较习惯用的macro有：

  • 取array[i]的值到%d

    1
    2
    3
    4
    .macro getNum(%d,%i)
    	sll %d,%i,2
    	lw %d,array(%d)
    .end_macro

  • 取array[i] [j]的值到%d，矩阵的列数为%n

    1
    2
    3
    4
    5
    6
    .macro getNum(%d,%i,%j,%n)
    	mul %d,%i,%n
    	add %d,%d,%j
    	sll %d,%d,2
    	lw %d,array(%d)
    .end_macro

  • 将字压入栈

    1
    2
    3
    4
    .macro push(%src)
    	sw   %src, 0($sp)
    	subi $sp, $sp, 4
    .end_macro

    相对应的弹出栈

    1
    2
    3
    4
    .macro pop(%des)
    	addi $sp, $sp, 4
    	lw   %des, 0($sp)
    .end_macro

第三步：合理规划寄存器

s0-s7是留给“需要保存的变量”，如常量，全局变量等；t0-t9是留给“临时变量”，如循环时常用的i、j、k变量等。对于一般的题目，我使用s0来保存n的值，t0留给循环变量i，t9留给计算出来的临时地址。

当然，如何分配主要还是看自己写的顺不顺手，只要自己有一套可操作的规则即可。

第四步：完成代码

我们在此先给出完整的汇编代码。如果对递归调用之外的地方存在疑问，可以再去阅读额外的讲解。

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
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
.data
	array: .space 32
	symbol: .space 32
	blank: .asciiz " "
	next_line: .asciiz "\n"
	
.macro push(%src)
	sw   %src, 0($sp)
	subi $sp, $sp, 4
.end_macro

.macro pop(%des)
	addi $sp, $sp, 4
	lw   %des, 0($sp)
.end_macro

.text
main:
	li   $v0, 5
	li   $s1, 1
	li   $t9, 0
	syscall
	move $s0, $v0
	init_loop:
		sll  $t8, $t9, 2
		sw   $0, symbol($t8)
		addi $t9, $t9, 1
		blt  $t9, $s0, init_loop
	li   $t0, 0 # index
	jal  FullArray
	li   $v0, 10
	syscall

FullArray:
	blt  $t0, $s0, search
	print:
		li   $t9, 0
		print_loop:
			sll  $t8, $t9, 2
			lw   $a0, array($t8)
			li   $v0, 1
			syscall
			li   $v0, 4
			la   $a0, blank
			syscall
			addi $t9, $t9, 1
			blt  $t9, $s0, print_loop
		print_end:
			li   $v0, 4
			la   $a0, next_line
			syscall
			jr   $ra
			
	search:
		li   $t1, 0 # i
		loop:
			sll  $t9, $t1, 2
			lw   $t8, symbol($t9)
			bne  $t8, $0, Else
			If:
				addi $t2, $t1, 1
				sll  $t9, $t0, 2
				sw   $t2, array($t9)
				sll  $t9, $t1, 2
				sw   $s1, symbol($t9)
				
				push($ra)
				push($t0)
				push($t1)
				
				addi $t0, $t0, 1
				jal  FullArray
				
				pop($t1)
				pop($t0)
				pop($ra)
				
				sll  $t9, $t1, 2
				sw   $0, symbol($t9)
			
			Else:
				addi $t1, $t1, 1
				blt  $t1, $s0, loop
		loop_end:
		jr   $ra

两个注意事项

1.注意return的位置

观察C语言代码，我们发现有两个需要return的位置。一般来说，return直接写作jr $ra即可。

2.递归调用前后的处理工作

我们把上面代码中设计递归调用的片段截取下来：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
addi $t2, $t1, 1
sll  $t9, $t0, 2
sw   $t2, array($t9)
sll  $t9, $t1, 2
sw   $s1, symbol($t9)
				
push($ra)
push($t0)
push($t1)
				
addi $t0, $t0, 1
jal  FullArray
				
pop($t1)
pop($t0)
pop($ra)
				
sll  $t9, $t1, 2
sw   $0, symbol($t9)

这里，$ra存储的是之前调用的位置+4，比如说在执行完jal FullArray之后，$ra存储的是pop($t1)的地址。$t0存的是参数index，$t1存的是FullArray里的遍历变量i。

进行push和pop的原因，无非是对寄存器内原有的值进行保护。对寄存器的保护(进行push和pop操作)一定是在函数调用前后进行的，而往往不是刚进入函数的时候。

难点在于，哪些变量需要被push？

  • 首先，$ra是必须被存在栈里的，否则调用结束后返回调用位置可能会出现异常；

  • 然后，函数的参数、返回值等一般是需要被push的，在这里就是index；

  • 其次，就是一些涉及到函数“状态”的量，比如说变量i，因为是对不同数字是否被占用进行遍历，存在遍历的先后顺序，所以i的不同会导致函数的“当前状态不同”；

    假如不对i进行保存，i=3时递归到第二层，在第二层中假设i最后为0且未进入第三层递归，那么再回到第一层时，i的值就与之前发生了变化，会造成函数执行异常；

  • 最后，调用者(caller)调用的函数(callee)中，callee使用到了一些caller中使用的寄存器，那么进行函数调用的时候需要保护caller中的这些寄存器。

确定了需要被push和pop的变量之后，我们还需要注意push和pop的顺序是否对应，栈是后入先出，最先push($ra)就要最后pop($ra)。

完成了push和pop的代码之后，我们就需要更新函数的参数

1
addi $t0, $t0, 1 # 下一个FullArray调用时参数为index + 1

然后就可以递归调用了！

（一般来说函数的参数保存在a0-a3寄存器里，当我意识到这点时已经晚了）

至此，一个完整的含有递归的汇编代码就完成了！

借助上面的分析，看看下面这两道例题，并尝试自己解决。

例题2：哈密顿回路

题干

题目编号 1109-5 challenge！哈密顿回路 - 计算机组成教程 (buaa.edu.cn)

题目要求

输入一个具有n个顶点的无向图G，判断G是否有哈密顿回路哈密顿图 - OI Wiki (oi-wiki.org)。

输入格式

第一行是一个整数n，代表G有n个顶点，第二行是一个整数m，代表G有m条边，接下来的2 * m行，每行具有一个整数，设每个奇数行的数为a，它下一行的数b，序号为a, b的两个顶点间具有一条边，两个整数之间以回车隔开（点的标号从 1 开始）。

输出格式

输出一个整数，若为 0 则代表G不具有哈密顿回路，若为 1 则代表G具有哈密顿回路。

约定

1、0 < n < 100

2、0 < m < 100

3、请勿使用 .globl main

4、最大运行指令条数限制为 100000

5、请使用 syscall 结束程序：

1
2
li $v0, 10
syscall

输入样例1

1
2
3
4
5
6
7
8
9
10
11
12
13
14
5
6
1
2
1
3
2
3
2
4
3
5
4
5

输出样例1

1
1

输入样例2

1
2
3
4
5
6
7
8
9
10
11
12
13
14
5
6
1
2
1
3
2
3
2
4
1
4
4
5

输出样例2

1
0

提交要求

  1. 请勿使用 .globl main
  2. 不考虑延迟槽
  3. 只需要提交.asm文件。
  4. 程序的初始地址设置为Compact,Data at Address 0。

参考C语言代码

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
#include <stdio.h>
int G[8][8];    // 采用邻接矩阵存储图中的边
int book[8];    // 用于记录每个点是否已经走过
int m, n, ans;

void dfs(int x) {
    book[x] = 1;
    int flag = 1, i;
    // 判断是否经过了所有的点
    for (i = 0; i < n; i++) {
        flag &= book[i];
    }
    // 判断是否形成一条哈密顿回路
    if (flag && G[x][0]) {
        ans = 1;
        return;
    }
    // 搜索与之相邻且未经过的边
    for (i = 0; i < n; i++) {
        if (!book[i] && G[x][i]) {
            dfs(i);
        }
    }
    book[x] = 0;
}

int main() {
    scanf("%d%d", &n, &m);
    int i, x, y;
    for (i = 0; i < m; i++) {
        scanf("%d%d", &x, &y);
        G[x - 1][y - 1] = 1;
        G[y - 1][x - 1] = 1;
    }
    // 从第0个点（编号为1）开始深搜
    dfs(0);
    printf("%d", ans);
    return 0;
}

参考解答

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
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
.data
	G: .space 280
	book: .space 40
	
.macro get(%des, %i, %j, %col)
	mult %i, %col
	mflo %des
	add  %des, %des, %j
	sll  %des, %des, 2
.end_macro

.macro push(%src)
	sw   %src, 0($sp)
	subi $sp, $sp, 4
.end_macro

.macro pop(%des)
	addi $sp, $sp, 4
	lw   %des, 0($sp)
.end_macro
	
.text
	li   $v0, 5
	syscall
	move $s0, $v0 # n
	li   $v0, 5
	syscall
	move $s1, $v0 # m
	li   $s7, 1 # constant
	
	li   $t0, 0
	loop1:
		beq  $t0, $s1, loop1_end
		li   $v0, 5
		syscall
		move $t1, $v0
		subi $t1, $t1, 1
		li   $v0, 5
		syscall
		move $t2, $v0
		subi $t2, $t2, 1
		get($t9, $t1, $t2, $s1)
		sw   $s7, G($t9)
		get($t9, $t2, $t1, $s1)
		sw   $s7, G($t9)
		addi $t0, $t0, 1
		j    loop1
	loop1_end:
	
	li   $a0, 0
	li   $s2, 0 # ans
	jal  dfs
	
	## print answer
	li   $v0, 1
	move $a0, $s2
	syscall
	li   $v0, 10
	syscall
	
dfs:
	sll  $t9, $a0, 2
	sw   $s7, book($t9)
	li   $t8, 0 # i
	li   $t1, 1 # flag
	
	loop2:
		beq  $t8, $s0, loop2_end
		sll  $t9, $t8, 2
		lw   $t9, book($t9)
		and  $t1, $t1, $t9
		addi $t8, $t8, 1
		j    loop2
	loop2_end:
		
	get($t9, $a0, $0, $s1)
	lw   $t9, G($t9)
	bne  $t1, $s7, Nope
	bne  $t9, $s7, Nope
	
	li   $s2, 1
	jr   $ra
	
	Nope:
	li   $t0, 0 # i in stack
	loop3:
		beq  $t0, $s0, loop3_end
		sll  $t9, $t0, 2
		lw   $t9, book($t9)
		bne  $t9, $0, Else
		get($t9, $a0, $t0, $s1)
		lw   $t9, G($t9)
		beq  $t9, $0, Else
		
		push($ra)
		push($t0)
		push($a0)
		
		move $a0, $t0
		jal  dfs
		
		pop($a0)
		pop($t0)
		pop($ra)
		
		Else:
		addi $t0, $t0, 1
		j    loop3
	loop3_end:
	
	sll  $t9, $a0, 2
	sw   $0, book($t9)
	jr   $ra

例题3：01迷宫

题干

题目编号 1121-38 P2_L1_puzzle - 系统能力课程实验平台 (buaa.edu.cn)

题目要求

  1. 使用mips实现01迷宫路线数目计算。
  2. 以0x00000000为数据段起始地址。
  3. 输入一个n*m的01矩阵作为01迷宫，并给定他的起点与终点，求出他不同逃跑路线的数目（不同逃跑路线中可以有相同的部分，但是不能完全相同）。
  4. 每组数据最多执行5,000,000条指令。

示例

迷宫示例

  1. 上图表示的是一个4*5的01矩阵，这个矩阵就是一个01迷宫。
  2. 如上图，以红色0作为起点，绿色0作为终点，每一次行进只能选择上下左右中值为0且未走过的位置，满足上述条件的路线，即为一条迷宫逃跑路线。如右图中，蓝色的路线即为一条逃跑路线。

输入格式

前两行输入两个整数n和m（n、m均为正整数并且小于等于7），分别代表01矩阵行数和列数。接下来的n*m行，每行输入1个整数（0或1），对应着01矩阵各个元素值(第i*m+j个整数为矩阵的第（i+1）行第j个元素，即一行一行输入)。接下来的四行分别代表迷宫的起点和终点，每行一个整数，分别代表起点与终点行数和列数。

输出格式

只输出一个整数，代表逃跑路线的数目。

输入样例

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
4
5
0
0
1
0
0
1
0
0
0
1
1
0
1
0
1
1
0
0
0
0
1
1
4
5

输出样例

1
2

提交要求

  1. 请勿使用 .globl main
  2. 不考虑延迟槽
  3. 只需要提交.asm文件。
  4. 程序的初始地址设置为Compact,Data at Address 0。

参考C语言代码

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
#include <stdio.h>
#define M 100007
#define N 1007
#define INF 0x3f3f3f3f
#define ll long long
#define db double
int n, m, cnt = 0;
int start_x, start_y, end_x, end_y;
int space[8][8], book[8][8];
int dir[4][2] = {{0, 1}, {1, 0}, {0, -1}, {-1, 0}};
void dfs(int x, int y) {
    // printf("%d\n", cnt);
    if (x == end_x && y == end_y) {
        cnt++;
        return;
    }
    for (int i = 0; i < 4; i++) {
        int tx = x + dir[i][0];
        int ty = y + dir[i][1];
        if (tx <= 0 || tx > n || ty <= 0 || ty > m || book[tx][ty] ||
            space[tx][ty]) {
            continue;
        }
        book[tx][ty] = 1;
        dfs(tx, ty);
        book[tx][ty] = 0;
    }
}
int main() {
    scanf("%d%d", &n, &m);
    for (int i = 1; i <= n; i++) {
        for (int j = 1; j <= m; j++) {
            scanf("%d", &space[i][j]);
        }
    }
    scanf("%d%d", &start_x, &start_y);
    scanf("%d%d", &end_x, &end_y);
    book[start_x][start_y] = 1;
    dfs(start_x, start_y);
    printf("%d", cnt);
    return 0;
}

参考解答

解答1

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
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
.data
	map: .space 400
	dir: .space 48

.macro get_map(%des, %i, %j, %col)
	mult %i, %col
	mflo %des
	add  %des, %des, %j
	sll  %des, %des, 2
.end_macro

.macro get_dir(%des, %i, %j)
	sll  %des, %i, 1
	add  %des, %des, %j
	sll  %des, %des, 2
.end_macro

.macro push(%src)
	sw   %src, 0($sp)
	subi $sp, $sp, 4
.end_macro

.macro pop(%des)
	addi $sp, $sp, 4
	lw   %des, 0($sp)
.end_macro

.text
li   $s6, -1
li   $s7, 1 # const
li   $t8, 4

init_dir:
	li   $t0, 0
	li   $t1, 0
	get_dir($t9, $t0, $t1)
	sw   $0, dir($t9)
	li   $t1, 1
	get_dir($t9, $t0, $t1)
	sw   $s7, dir($t9)
	
	li   $t0, 1
	li   $t1, 0
	get_dir($t9, $t0, $t1)
	sw   $s7, dir($t9)
	li   $t1, 1
	get_dir($t9, $t0, $t1)
	sw   $0, dir($t9)
	
	li   $t0, 2
	li   $t1, 0
	get_dir($t9, $t0, $t1)
	sw   $0, dir($t9)
	li   $t1, 1
	get_dir($t9, $t0, $t1)
	sw   $s6, dir($t9)
	
	li   $t0, 3
	li   $t1, 0
	get_dir($t9, $t0, $t1)
	sw   $s6, dir($t9)
	li   $t1, 1
	get_dir($t9, $t0, $t1)
	sw   $0, dir($t9)
	
main:
	li   $v0, 5
	syscall
	move $s0, $v0 # n
	li   $v0, 5
	syscall
	move $s1, $v0 # m
	
	li   $t0, 1 # i
	input1:
		bgt  $t0, $s0, input1_end
		li   $t1, 1 # j
		input2:
			bgt  $t1, $s1, input2_end
			get_map($t9, $t0, $t1, $s1)
			li   $v0, 5
			syscall
			sw   $v0, map($t9)
			addi $t1, $t1, 1
			j    input2
		input2_end:
		addi $t0, $t0, 1
		j    input1
	input1_end:
	
	li   $v0, 5
	syscall
	move $s2, $v0 # start_x
	li   $v0, 5
	syscall
	move $s3, $v0 # start_y
	li   $v0, 5
	syscall
	move $s4, $v0 # end_x
	li   $v0, 5
	syscall
	move $s5, $v0 # end_y
	li   $t7, 0 # result
	
	get_map($t9, $s2, $s3, $s1)
	sw   $s6, map($t9)
	move $a1, $s2 # argument x
	move $a2, $s3 # argument y
	
	jal  dfs
	
	li   $v0, 1
	move $a0, $t7
	syscall
	li   $v0, 10
	syscall
	
dfs:
	bne  $a1, $s4, Else
	bne  $a2, $s5, Else
	If0:
		addi $t7, $t7, 1
		jr   $ra
	Else:
	
	li   $t0, 0 # for int i = 0;
	loop:
		bge  $t0, $t8, loop_end
		get_dir($t9, $t0, $0)
		lw   $t1, dir($t9)
		get_dir($t9, $t0, $s7)
		lw   $t2, dir($t9)
		add  $t1, $t1, $a1 #tx
		add  $t2, $t2, $a2 #ty
		
		ble  $t1, $0, If
		ble  $t2, $0, If
		bgt  $t1, $s0, If
		bgt  $t2, $s1, If
		
		get_map($t9, $t1, $t2, $s1)
		lw   $t3, map($t9)
		bne  $t3, $0, If
		
		# possible
		sw   $s6, map($t9)
		push($ra)
		push($a2)
		push($a1)
		push($t2)
		push($t1)
		push($t0)
		move $a1, $t1
		move $a2, $t2
		
		jal  dfs
		
		pop($t0)
		pop($t1)
		pop($t2)
		pop($a1)
		pop($a2)
		pop($ra)
		get_map($t9, $t1, $t2, $s1)
		sw   $0, map($t9)
		
		If:
		addi $t0, $t0, 1
		j    loop
	loop_end:
	jr   $ra
课内学习
#计算机组成
递归调用汇编代码翻译的一些心得
https://galaxy-jewxw.github.io/2023/10/21/递归调用汇编代码翻译的一些心得/
作者
Traumtänzer aka 'Jew1!5!'
发布于
2023年10月21日
许可协议