L03 Compiling Code, Procedures, and Stacks

MIT 6.004 Spring 2019 L03 Compiling Code, Procedures, and Stacks，由Silvina Hanono Wachman讲述。

本次讲座继续深入讨论了如何将高级编程语言转换成汇编语言，并开始探索如何处理程序（Procedures）。

主要内容

指令集回顾

到目前为止，学习了几种RISC-V指令集架构中的指令类型：
1. 计算指令（ALU操作），包括寄存器-寄存器操作和寄存器-立即数操作
2. 控制流指令，包括无条件跳转和条件分支
3. 加载和存储指令，用于在内存和寄存器之间传输信息
4. 新引入了加载上半部分立即数（Load Upper Immediate）指令，以解决常量大小的限制问题。
C语言到汇编语言转换

详细讲解了将C语言代码转换成汇编语言的步骤，包括变量到寄存器的分配、将复杂操作分解为简单操作等。
编译条件和循环语句

提供了方法论，解释了如何将if-then、if-then-else和while循环等高级语言构造转换为汇编语言。
程序（Procedures）

讨论了程序实现的关键要素，包括入口点、参数传递、局部存储和退出点。特别强调了使用栈和激活记录来管理程序调用所需的信息，以及如何处理嵌套程序调用。
调用约定

引入了调用约定，详细规定了哪些寄存器由调用者保存，哪些由被调用者保存。定义了专门的寄存器用于参数传递和返回值。
程序调用和返回示例

通过计算最大公约数（GCD）的程序示例，展示了如何实现程序的调用和返回，以及如何通过跳转和链接指令（Jump and Link）来保存和恢复程序执行的上下文。

分页知识点

RISC-V回顾

计算指令由算术逻辑单元（ALU）执行。
- 寄存器-寄存器指令格式为 op dest, src1, src2，其中 op 是操作码，dest 是目标寄存器，src1 和 src2 是源寄存器。
- 寄存器-立即数指令格式为 op dest, src1, const，其中 const 是立即数常量。
控制流指令分为无条件跳转（jal 和 jalr）和有条件比较跳转（comp src1, src2, label）。
加载和存储指令包括 lw dest, offset(base) 和 sw src, offset(base)，这里的 base 是基址寄存器，offset 是一个小的常数。
伪指令是其他指令的简写形式。

处理常量

执行 a = b + 3。假设 a 在寄存器 x1 中，b 在 x2 中。对于12位的小常数，可以通过寄存器-立即数ALU操作来处理，例如 addi x1, x2, 3。
执行 a = b + 0x123456。最大的12位2进制补码常数是 2047（0x7FF）。使用 li 伪指令来将寄存器设置为较大的常数，例如通过两条指令 lui x4, 0x123 和 addi x4, x4, 0x456 来生成 0x123456。lui 指令将 0x123 放置到寄存器 x4 的高位，而 addi 则将 0x456 加到 x4 中。
li 伪指令也可以用来处理小常数。

编译简单表达式

将变量分配给寄存器。
将运算符翻译为计算指令。
使用寄存器-立即数指令来处理含有小常数的操作，如 addi。
使用 li 伪指令来处理大常数。
例如，C代码
```
int x, y, z; y = (x + 3) | (y + 123456); z = (x * 4) ^ y;
```
对应的RISC-V汇编代码为：
```
// x: x10, y: x11, z: x12
// x13, x14 used for temporaries
addi x13, x10, 3
li x14, 123456
add x14, x11, x14
or x11, x13, x14
slli x13, x10, 2
xor x12, x13, x11
```
- 这段汇编代码首先将 x 加 3 然后存储在 x13 中，将 y 加上 123456 并与 x13 进行或操作后存储回 y（即 x11）。接着，它将 x 左移2位（相当于乘以4）存储在 x13 中，然后将结果与 y 进行异或操作后存储到 z（即 x12）。

编译条件语句

if语句

在C语言中的if语句可以通过使用分支指令编译到RISC-V汇编语言中。
C语言示例和对应的RISC-V汇编示例如下：
```
if (expr) {
    if-body
}
```
编译为：
```
// 将表达式expr编译到xN寄存器中
beqz xN, endif
// 编译if-body部分
endif:
```
- 这里beqz是分支指令，它检查寄存器xN中的值是否为0，如果为0，则跳转到endif标签。
- endif是一个标签，用于在编译if-body之后标记代码的结束位置。

if-else语句

if/else语句的编译与if语句类似，但需要处理两种情况（if-body和else-body）。
C语言示例和对应的RISC-V汇编示例如下：
```
if (expr) {
    if-body
} else {
    else-body
}
```
编译为：
```
// 将表达式expr编译到xN寄存器中
beqz xN, else
// 编译if-body部分
j endif
else:
// 编译else-body部分
endif:
```
- 如果表达式expr计算结果为假（即xN为0），程序会跳转到else标签，执行else-body部分；否则执行if-body部分后跳过else-body。

编译循环

while循环

while循环可以使用反向分支来编译。
C语言示例和对应的RISC-V汇编示例如下：
```
while (expr) {
    while-body
}
```
编译为：
```
while:
// 将表达式expr编译到xN寄存器中
beqz xN, endwhile
// 编译while-body部分
j while
endwhile:
```
- 在此示例中，beqz指令检查xN是否为0，如果为0则跳转到endwhile标签，表示循环结束。如果不为0，则继续执行while-body部分，然后跳回到while标签处，重新评估循环条件。

整合所有内容

综合示例

上述的循环和条件语句可以结合起来编译更复杂的结构。
C语言示例和对应的RISC-V汇编示例如下：
```
while (x != y) {
    if (x > y) {
        x = x - y;
    } else {
        y = y - x;
    }
}
```
编译为：
```
// x: x10, y: x11
j compare
loop:
// 编译while-body部分
compare:
bne x10, x11, loop
```
- 在这个例子中，bne指令用来比较x10和x11，如果它们不相等（即x != y），则跳回loop标签继续执行循环体。

下面部分展示了如何将一个包含while循环和if-else条件语句的复杂C语言代码块转换为RISC-V汇编代码。

C代码示例:

while (x != y) {
    if (x > y) {
        x = x - y;
    } else {
        y = y - x;
    }
}

对应的RISC-V汇编代码:

// x: x10, y: x11
j compare
loop:
    ble x10, x11, else
    sub x10, x10, x11
    j endif
else:
    sub x11, x11, x10
endif:
compare:
    bne x10, x11, loop

这段汇编代码首先跳转到compare标签来检查循环条件。如果x <= y（ble指令），则跳转到else分支。在if分支中，x减去y的结果存回x（sub x10, x10, x11），否则else分支中y减去x的结果存回y（sub x11, x11, x10）。结束if或else分支后，跳回到compare以重新检查循环条件。

过程

过程定义:

过程（也称为函数或子程序）是执行特定任务的可重用代码片段，具有单一的命名入口点和零个或多个形式参数。当过程执行完毕后，它会返回到调用者。
使用过程可以实现抽象和重用，允许从简单过程的集合中组成大型程序。

C代码示例:

int gcd(int a, int b) {
    int x = a;
    int y = b;
    while (x != y) {
        if (x > y) {
            x = x - y;
        } else {
            y = y - x;
        }
    }
    return x;
}

对应的RISC-V汇编代码:

// x: x10, y: x11
j compare
loop:
    ble x10, x11, else
    sub x10, x10, x11
    j endif
else:
    sub x11, x11, x10
endif:
compare:
    bne x10, x11, loop

这段代码定义了一个计算两个整数最大公约数（GCD）的函数。函数体的汇编代码与前面的循环几乎相同，因为核心逻辑是类似的。函数最终返回x，在汇编中通常使用a0（或x10）寄存器来返回值。

管理过程的寄存器空间

当一个过程（调用者）调用另一个过程（被调用者）时，它们共享同一套寄存器集。
如果按照某种约定来划分调用者和被调用者之间的寄存器，当多个过程相互调用时会非常复杂，且寄存器本身就很稀缺。
更好的解决方案是，调用者不应该依赖于被调用过程如何管理其寄存器空间。
调用者或被调用者应该将调用者的寄存器保存在内存中，并在过程调用完成后恢复这些寄存器值。

通过这种方式，RISC-V汇编确保每个过程可以在不干扰其他过程的情况下运行。

实现过程

调用者需要通过寄存器向被调用的过程传递参数并从被调用的过程获取结果。
一个过程可以从多个不同位置被调用。调用者可以通过执行一个无条件跳转指令到达被调用的过程代码。
然而，为了返回到调用过程中的正确位置，被调用的过程需要知道它应该使用哪个返回地址。因此，返回地址必须被保存并传递给被调用的过程。

过程链接

控制权如何在调用者和被调用者之间传递？
- 使用
```
jal ra, label
```
  （跳转并链接）指令，该指令做了以下事情：
  1. 在返回地址寄存器ra中存储proc_call指令后面第四个字节的地址。
  2. 跳转到标签label处的指令，这里的label是过程的名称。
  3. 在执行完过程后，使用j ra（跳转到ra寄存器中的地址）返回到调用者并继续执行。

过程调用的复杂性

如果一个过程A调用了过程B，过程B又调用了过程C，那么单一的返回地址寄存器是不够用的；过程C的返回地址将会覆盖过程A的返回地址。
在存储过程A的寄存器的内存空间中也存在类似的复杂性——这个空间必须与存储过程B寄存器的空间不同。

过程的存储需求

过程调用的基本要求包括输入参数、返回地址和结果。
局部存储需求包括：
- 编译器无法放在寄存器中的变量。
- 保存我们将要覆写的调用者寄存器值的空间。

每次过程调用都会有它自己的所有这些数据的实例，这被称为过程的激活记录（activation record）。

栈的洞察

栈是一种数据结构，用于存储激活记录（activation records）。
激活记录按照后进先出（LIFO）的顺序被分配和释放。
栈的操作包括push（压入）、pop（弹出）以及访问栈顶元素。
我们只需要访问当前正在执行的过程的激活记录。

RISC-V栈

栈位于内存中，需要一个寄存器来指向它。在RISC-V中，栈指针sp是寄存器x2。
栈的增长方向是向下的，即从高地址向低地址增长。
- 执行push操作会减小栈指针sp的值。
- 执行pop操作会增加栈指针sp的值。
sp寄存器指向栈顶，即最后一个压入栈的元素。
使用栈的规则是：可以在任何时候使用栈，但在使用完毕后要恢复到原始状态。

使用栈

示例的入栈序列:

addi sp, sp, -N
sw ra, 0(sp)
sw a0, 4(sp)

对应的出栈序列:
```
lw ra, 0(sp)
lw a0, 4(sp)
addi sp, sp, N
```
这些操作分别表示在进入和退出过程时保存和恢复寄存器，以及分配和释放栈空间。

入栈序列好像有些混淆？先sw a0, 4(sp)才更符合LIFO吧，又或者属于同一次的入栈不用在意顺序。

调用约定

调用约定指定了过程间寄存器使用的规则。
RISC-V调用约定为寄存器x0-x31提供了符号名称以指明它们的作用：
- a0到a7 (x10到x17)：用于函数参数。
- a0和a1 (x10和x11)：用于函数返回值。
- ra (x1)：用于返回地址。
- t0到t6 (x5-x7, x28-x31)：用作临时寄存器。
- s0到s11 (x8-x9, x18-x27)：被保存的寄存器。
- sp (x2)：栈指针。
- gp (x3)：全局指针。
- tp (x4)：线程指针。
- zero (x0)：硬连线零。

每个寄存器的保存责任分为调用者（Caller）和被调用者（Callee），这决定了在过程调用过程中哪些寄存器需要被保存和恢复。

通过这样的约定，不同的过程可以预知哪些寄存器在调用后会被保留其值，哪些寄存器可能会被修改，从而在编写代码时可以做出适当的寄存器使用决策。

调用者保存与被调用者保存寄存器

调用者保存寄存器：在函数调用时不保留。如果调用者希望保持其值不变，它必须在将控制权交给被调用者之前将其保存在栈上。通常，这包括参数寄存器（aN），返回地址（ra），和临时寄存器（tN）。
被调用者保存寄存器：在函数调用时必须保留。如果被调用者希望使用这些寄存器，它必须在使用前将其原始值保存在栈上，并在返回控制权给调用者之前恢复它们。这通常包括已保存的寄存器（sN）和栈指针（sp）。

使用被调用者保存寄存器的例子

在这个例子中，函数f用到了两个被调用者保存寄存器s0和s1来存储临时值。在函数调用的开始，这些寄存器的值被保存到了栈上。函数完成后，这些值从栈上恢复，以保证这些寄存器的值在函数调用前后保持不变。

使用调用者保存寄存器的例子

这个例子展示了一个调用者如何保存和恢复寄存器的值。在这种情况下，调用者需要保证在调用另一个函数前保存a1寄存器的值，因为被调用的函数可能会修改a1寄存器的内容，调用者在调用之后可能还需要用到a1寄存器原来的值。

栈的使用示例

提供了在调用函数前、调用函数时和调用函数后栈的状态的视图。这帮助我们可视化如何在栈上分配和释放空间，并显示在函数调用期间如何保持寄存器s0和s1的值。

这些概念在函数调用过程中确保了变量的正确保存和恢复，这对于编写可以预测并一致地运行的程序至关重要。在编程和调试过程中，了解这些细节可以帮助理解函数调用可能出现的错误和行为异常。

补充

这里是一些关于在RISC-V架构中进行函数调用和栈操作的关键知识点总结：

调用约定：在RISC-V及许多其他体系结构中，调用约定定义了函数参数、返回值、和临时变量应如何在寄存器和栈之间传递。对于RISC-V，默认的调用约定规定了a0到a7用于前八个整数函数参数，a0和a1用于前两个返回值。
寄存器使用：RISC-V的调用约定还规定了哪些寄存器需要在函数调用前保存（caller-saved）和哪些寄存器需要在函数返回前保存（callee-saved）。
栈的后进先出（LIFO）原则：在函数调用时，最后压入栈的数据最先被弹出。保存寄存器值时，栈指针（sp）下移以分配空间，然后寄存器值依序压入。恢复寄存器值时，栈中的数据依序弹出，并且栈指针上移以释放空间。
寄存器的保存与恢复：通常，ra（返回地址寄存器）和函数参数（如果后续函数调用会更改它们）需要被保存在栈上。如果一个函数调用另一个函数，ra需要首先保存，以确保能够返回到正确的位置。
寄存器保存的必要性：如果一个函数（比如multiply）不会调用任何会更改a0或a1的函数，则在调用该函数之前不需要在栈上为这些寄存器分配空间。
栈指针的管理：函数调用前后，栈指针的位置应该保持一致。这意味着分配给栈帧的空间在函数返回前必须完全释放。

在嵌套函数调用的情况下，每一层函数都必须确保它调用的任何函数不会意外地改变它依赖的寄存器值。如果存在这种可能性，函数必须在调用之前将这些寄存器值保存在栈上，并在调用结束后从栈上恢复它们。

函数调用时保存寄存器的必须遵循LIFO原则的情况

当一个函数可能再调用另一个函数（即有嵌套函数调用）时，必须保存当前函数的返回地址ra。在这种情况下，LIFO原则非常重要，因为每个函数都需要在完成后能够返回到正确的位置。
如果sum函数或任何被调用的函数内部可能会导致ra寄存器被修改（比如通过另一个函数调用），那么在恢复寄存器时就必须严格遵守LIFO原则，首先恢复最后保存的寄存器，这通常是ra。

在这种情况下，如果不遵守LIFO原则，可能会导致返回到错误的地址，从而导致程序运行错误或崩溃。

在没有嵌套调用的情况下，为何可以灵活恢复寄存器

当sum函数调用完成后，ra没有被更改，因此可以安全地先恢复其他寄存器，例如a1。这是因为ra的值在栈上保持不变，没有被sum函数或其他任何操作修改。
sp（栈指针）保持不变，因此恢复寄存器的顺序可以灵活安排。只要所有必须的寄存器最终都被正确恢复，并且栈指针也被正确调整到函数调用前的状态，程序的执行流就不会受到影响。

总结来说，是否需要遵守严格的LIFO原则取决于函数调用的上下文。如果存在修改ra的操作，那么必须遵守LIFO。如果保证ra在整个调用期间不会被修改，恢复寄存器的顺序就可以有所灵活性。在编写汇编代码时，通常建议遵循一致的模式，以减少混淆和潜在的错误。

补充2

激活帧

激活帧（Activation Frame），也称为栈帧（Stack Frame），是在栈上为每次函数调用所分配的内存块。它包含了函数执行所需的所有信息，如：

局部变量：函数内声明的变量。
参数：传递给函数的参数。
返回地址：函数执行完毕后应返回到的代码位置。
保存的寄存器：调用前需要保存的寄存器，以便函数执行后能够恢复。

| MIT Digital Systems Notebook |