从零开始编写 C 编译器 Chapter 2.0 | Runtime Stack

Note: 所有代码、定义、术语命名都参考 Nora Sandler 的书籍 Write a C Compiler

在 Chapter 1 中我们实现了对 return 语句和 constant 的支持。这章将会实现对一元运算符(unary operator)的支持。具体的说，是 算数负号运算符 - 和 按位取反运算符 ~ 的支持。同时还引入 IR 来化简生成汇编的难度。

Introduce

考虑下列的 C 程序：

int main(void) {
    return ~(-2);
}

这份代码包含嵌套的表达式 ~(-2)，每个表达式都包含一个一元运算符：Negation (-) 或 Complement (~)。下表列出了这俩运算符的语义。

运算符	含义	示例	说明
-	算数取负	-2 -> 2	整数取负
~	按位取反	~(-2) -> 1	在补码系统中，~x = -x = 1

在本章结束后，我们的编译器应该生成如下汇编代码：

    .globl main
main:
    pushq    %rbp
    movq     %rsp, %rbp
    subq     $8, %rsp

    movl     $2, -4(%rbp)
    negl     -4(%rbp)

    movl     -4(%rbp), %r10d
    movl     %r10d, -8(%rbp)
    notl     -8(%rbp)

    movl     -8(%rbp), %eax
    movq     %rbp, %rsp
    popq     %rbp

    ret

现代编译器会进行一系列的优化，可能会直接在编译的时候计算出最终结果，所以汇编指令只有一条指令：$movl $1, %rax。目前我们不考虑优化。

我们目前没有编写寄存器分配，所以临时变量都暂时存放在栈上。开始的 3 条指令被称为 函数序言(function prologue)，是值在调用开始和结束时，由编译器自动生成的一段机器代码，用于建立和保存调用上下文，为局部变量分配空间，确保函数能正确执行并安全返回。目前，它的作用为将 %rbp 的值压入栈中，并将栈顶的值 %rsp 复制给 %rbp，并分配 \(8\) 字节的空间给新栈，用于存储局部变量。后续会有更详细的关于运行时栈的解释。%rsp 为 Stack Pointer Register，用于存储当前函数栈帧的栈顶元素地址。

第一条 movl 语句将 立即数 \(2\) 到一个内存地址中。-4(%rbp) 为寄存器寻址，表示地址为 \([rbp] - 4\) 的内存空间。%rbp 为 Base Pointer Register，一般用于保存当前函数栈帧的栈地地址，所以 -4(%rbp) 表示比 %rbp 小 4 的地址。之后 negl 指令将该地址中的值取负。

mov 指令的 源地址 src 和目的地址 dst 不能同时为内存，所以用 %r10d 来作为中转，通过两条 mov 指令将 -4(%rbp) 中的值转移到 -8(%rbp) 中。之后使用 notl 指令进行取反。

末尾的 3 条指令被称为 函数尾声(function epilogue)，与函数序言对应，用于传递返回值，恢复现场，释放全局变量。

在 System V ABI 中，函数栈帧的栈底指针为 %rbp 寄存器，函数栈帧的栈顶指针为 %rsp，函数的返回值通过 %rax 寄存器传递。

Runtime Stack

每个函数调用之后，编译器都会在内存中分配一块连续的地址空间，用于存储当前函数内的局部变量，临时计算结果等，这块空间被称为函数栈帧。所有函数调用的函数栈帧合起来被称为 运行时栈 (Runtime Stack)，也就是常说的栈区。

函数栈帧方向向低地址增长：栈顶实际上是栈中最低的内存地址。所以我们才会使用 %subq $8 %rsp 来为栈分配 \(8\) 字节的空间。同样，当我们向栈内 push 一个值的时候，%rsp 自动执行减操作。当执行 pushq $3 这样的指令的时候，实际执行了下面的操作：

• 将 \(3\) 放入栈顶的下一个空间。q 后缀表明 \(3\) 的类型为 long long，占用 \(8\) 字节的空间。
• 将 %rsp 的值减 \(8\)。%rsp 值向的是栈顶元素的最低地址，即 \(3\) 所占第一个字节。

popq src 指令执行相反的操作：将 %rsp 所指的元素复制到 src 中，然后将 rsp 加 \(8\)。

每当调用一个函数的时候，我们会通过 pushq %rbp 将上一个函数的栈底地址存入栈中。之后将栈顶地址 %rsp 复制给 %rbp，将当前栈顶设为新栈帧的基地址。此时，栈顶和栈底都是同一个位置，表明当前栈帧为空。之后通过 subq 指令将 %rsp 往下移动 \(n\) 个字节。这样当前栈帧就有了 \(n\) 个字节的可用空间，用于存储临时变量。这就是 function prologue 的实现原理。

function epilogue 也是同理，只不过执行相反的操作。

• movq %rbp, %rsp 将 %rsp 重置为 %rbp, 恢复栈为空的状态。也可以使用 addq $8, %rsp 来实现同样的操作，但是加法运算慢于寄存器赋值运算。
• popq %rbp 将刚开始压入栈顶的老 %rbp 值恢复，%rsp 自动加 \(8\)，这样就恢复到了调用前的状态。

C 语言中支持嵌套的表达式，但汇编语言中不支持。我们需要一系列的临时变量来存储这些中间值。正常来说，编译器会实现一套 寄存器分配算法 来管理和分配寄存器，但这部分过于复杂，目前所有运算都将在栈上运行。

在解析 function_definition 的时候，我们需要顺带解析出需要多少局部变量，并自动生成 function prologue 和 funciton epilogue 为栈上分配空间。