SamuFlore's Dimension

德才兼備、知行合一

0%

[CO P2]宏、函数与栈

发表于 分类于 Valine：
4.4k 9 分钟

序

我曾写过我更偏好于进入函数后入栈，离开函数前出栈，但这样我一道题都做不对。

宏

MIPS 中，可以通过这样的方式来定义宏：

1
2
3
4
5
.macro name(%param1, %param2, ...)
    ############
    # function #
    ############
.end_macro

命名的时候也可以不要参数，这样使用的时候也不用传入参数。

在我看来宏其实和函数区别并不明显。但是宏比较适合定义一些反复使用，同时简约的函数，比如结束进程：

1
2
3
4
.macro end
    li $v0, 10
    syscall
.end_macro

非要说这样可以节约很多行代码，其实好像也没有，但是看起来就是舒服一点（

以下是一些很常用的宏：

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
# exit program
.macro end 
    li $v0, 10
    syscall
.end_macro

# read an int
.macro readNum(%r) 
    li $v0, 5
    syscall
    move %r, $v0
.end_macro

# read a char, you don't need to input an "enter" or a "space" between two chars, or these invisible sh*ts will be read!
.macro readChar(%r) 
    li $v0, 12
    syscall
    move %r, $v0
.end_macro

# print an int
.macro printNum(%r) 
    move $a0, %r
    li $v0, 1
    syscall
.end_macro

# print a char
.macro printChar(%r) 
    la $a0, %r
    li $v0, 4
    syscall
.end_macro

# push %r into stack
.macro push(%r) 
    addi    $sp, $sp, -4
    sw      %r, 0($sp)
.end_macro

# pop stack elements to %r
.macro pop(%r)
    lw      %r, 0($sp)
    addi    $sp, $sp, 4
.end_macro

# get an element's address offset of a matrix
.macro getIndex1(%ans, %i, %j, %n) # "n" for the number of columns of the matrix
    mult %i, %n
    mflo %ans # ans = i * n
    add %ans, %ans, %j # ans = i * n + j
    sll %ans, %ans, 2 # ans = 4 * (i * n + j)
.end_macro
# usage: 
# lw $des matrix($offset)
# sw $src matrix($offset)
# "offset" is the "%ans"
# tips: if the columns number is 2^n, use "sll" instead of "mult, mflo"

# get an element's address offset of an array
.macro getIndex2(%ans, %index)
    sll %ans, %index, 2 # ans = 4 * index
.end_macro

注意：两个宏可以取同一个名字，编译器通过传入的参数来判断展开为哪一段代码，比如：

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
.data
str: .asciiz " is a number.\n"

.macro print(%r)
    la $a0, %r
    li $v0, 4
    syscall
.end_macro

.macro print(%r1, %r2)
    move $a0, %r1
    li $v0, 1
    syscall
    la $a0, %r2
    li $v0, 4
    syscall
.end_macro

.text
li $t0, 114514
print(str)
print($t0, str)

li $v0, 10
syscall

两次输出分别为 is a number. 和 114514 is a number.。

函数与栈

MIPS 中被称之为“函数”的东西，是比宏复杂得多了。一般来说，都需要用一个标签名来隔离开，并用 jal 指令进入函数体，执行完再 jr $ra 回来。比如说：

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
.data

#################

.macro
##########
.end_macro

#################

.text
########
# code #
########

jal dfs
# print or sth.

end

dfs:
    ########
    # code #
    ########

    jr $ra

这就不是像宏一样展开了。函数体独立于主程序外（其实可以给主程序也加个标签叫做 main:），要用的时候相对跳转过去，用完了还得返回之前的位置执行下一行指令。其实宏和函数并没有严格界限，还得视情况而定。不过某种情况下我们还是得用这种标签法，那就是函数涉及递归时。

考虑翻译递归函数的 C 语言代码为 MIPS：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
void dfs(int i)
{
    if (condition)
    {
        // print or sth.
        return;
    }
    else
    {
        if (condition)
        {
            dfs(i + 1);
        }
    }
}

要进入 dfs，我们使用 jal，return 或执行到函数尾时，我们用 jr $ra 结束这一层函数调用，回到上一层函数调用。执行 dfs(i + 1) 时，我们用 jal dfs 调用子函数。
然而，在讨论出入栈问题时，我们必须明确：

  1. 要出入栈的内容包括：$ra，调用子函数时会改变、从子函数回来时要恢复的元素（在这里，比如说 i）。

  2. 调用子函数后，栈顶保存的是上一层函数中第一条指定的内容。我们通过例子来看：

首先 i 肯定需要用一个寄存器保存，我们就假设是 $t0。

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
main:
li $t0, 0 # t0 = i

jal dfs

end

dfs:
    <condition> branch1
    j branch2
    branch1:
        # print or sth.
        jr $ra # return
    branch2:
    
    <condition> branch3
    j branch4
    branch3:
        push($ra)
        push($t0)
        addi $t0, $t0, 1
        jal dfs
        pop($t0)
        pop($ra)
        # some code use $t0
    branch4:
    
    jr $ra # end of dfs

我们把第 n 层 dfs 称作 dfsn，从 dfs1 开始。

  1. 首先，main 调用 dfs1，假设进入第二个条件判断并满足条件，那么 $ra 和 $t0 入栈。入栈的 $ra 指向 main 的 end，$t0 为 0。

  2. $t0 + 1 变成 1。jal 跳转 dfs2。此时新的 $ra 指向 dfs1 的 pop($t0)，$t0 为 1。

  3. 假设 dfs2 仍然进入第二个条件判断并满足条件，那么入栈的 $ra 指向 dfs1 的 pop($t0)，$t0 为 1。

  4. $t0 + 1 变成 2。jal 跳转 dfs3。此时新的 $ra 指向 dfs2 的 pop($t0)，$t0 为 2。

  5. 让 dfs3 满足第一个条件，使用 jr 回到 dfs2 的 pop($ra) 吧。经过两个 pop 后，$ra 指向了 dfs1 的 pop($ra)，$t0 为 1。

  6. 到 dfs2 函数尾，jr 回到 dfs1 的 pop($ra)，经过两个 pop 后，$ra 指向了 main 的 end，$t0 为 0。

  7. 到 dfs1 函数尾，jr 回到 main 的 end，运行 end 结束。

显然这样是可以的，不会弄乱每层 i 的值，也能正常回到主函数。

另一种出入栈方式是：

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
main:
li $t0, 1 # t0 = i

jal dfs

end

dfs:
    push($ra)
    push($t0)

    <condition> branch1
    j branch2
    branch1:
        # print or sth.
        jr $ra # return
    branch2:
    
    <condition> branch3
    j branch4
    branch3:
        
        addi $t0, $t0, 1
        jal dfs
        # some code use $t0
    branch4:
    
    pop($t0)
    pop($ra)
    jr $ra # end of dfs

同样的：

  1. main 调用 dfs1，入栈 $ra 指向 main 的 end，$t0 = 0。

  2. 满足第二个条件，$t0 = 1，jal 跳转 dfs2 后 $ra 指向 dfs1 的 # some code use $t0，$t0 = 1。

  3. 入栈 $ra 指向 dfs1 的 # some code use $t0，$t0 = 1。

  4. 满足第二个条件，$t0 = 2，jal 跳转 dfs3 后 $ra 指向 dfs2 的 # some code use $t0，$t0 = 2。

  5. dfs3 满足第一个条件，jr 回到 dfs2 的 # some code use $t0，这时候，问题出现了。

什么问题呢？回到 dfs2 的时候，$t0 是 2，下文使用 $t0 的时候，都是用 2 来运行的。可是 dfs2 对应的 $t0 应该是 1（调用 dfs1 时 $t0 为 0，dfs2 时为 1）。这是为什么呢？

原因出在 addi $t0, $t0, 1 上。这是因为我们需要 dfs(i + 1)。按理说，是将 i + 1 传入下一层函数，不应该改变本层 i 的值。但是 MIPS 并不如 C 语言那样智能，给你创建 i 的副本来保存不同层的值。所有层的 i 都存放在 $t0 这个寄存器中。这就是为什么我们需要手动出入栈。在第一种写法，我们是先入 dfsn 的栈，再跳转 dfsn+1，而第二种写法是 先跳转 dfsn+1，再入 dfsn 的栈。在 $ra 上面，这两种是等效的，均可以实现递归-回溯。但是要用到 $t0，则第二种需要手动减去 $t0 的增加值：

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
main:
li $t0, 1 # t0 = i

jal dfs

end

dfs:
    push($ra)
    push($t0)

    <condition> branch1
    j branch2
    branch1:
        # print or sth.
        jr $ra # return
    branch2:
    
    <condition> branch3
    j branch4
    branch3:
        
        addi $t0, $t0, 1
        jal dfs
        addi $t0, $t0, -1 # add this line
        # some code use $t0
    branch4:
    
    pop($t0)
    pop($ra)
    jr $ra # end of dfs
-------------本文结束 感谢您的时间-------------
相 關 博 文

欢迎关注我的其它发布渠道