编译器构造（上半部分）

编译器构造：具体语法、抽象语法、解释器与 x86 基础

1 学习目标

本课程设定的核心学习目标包括以下五个主要方面：

• 理解具体语法（Concrete Syntax）与抽象语法（Abstract Syntax）之间的关系及其差异。
• 了解如何使用解析器生成器（Parser Generator）根据定义好的语法规则生成解析器（Parser）。
• 掌握如何将计算机程序内部表示为抽象语法树（AST, Abstract Syntax Trees）。
• 学习如何通过对抽象语法树进行递归遍历，从而实现基础的解释器、编译器以及代码优化器。
• 熟悉 x86 指令集的基础知识，以及程序函数调用所依赖的调用约定（Calling Convention）。

2 编译器设计的核心问题

当我们着手实现一个将高级语言转换为汇编代码的编译器时，必须明确并解决以下四个关键问题：

1. 我们正在编译的源语言，其语法（Syntax）结构是怎样的？
2. 我们正在编译的源语言，其背后的语义（Semantics）是什么？
3. 我们如何才能将这些高级语言语义，如实地在底层汇编代码中实现？
4. 我们如何通过程序化的方式，自动化地生成这些目标汇编代码？

3 具体语法与抽象语法

3.1 什么是具体语法

程序的具体语法指的是作为编译器的初始输入内容的文本表示形式。 编译器前端（特别是其中的解析器环节）主要执行两项任务：

1. 识别（Recognition）：判定输入的程序文本是否结构良好（well-formed）。如果输入代码包含格式或拼写错误，这一步会予以拒绝。
2. 解析（Parsing）：为程序构建一种更便于后续处理和使用的内部数据结构，通常称为抽象语法树（AST）。

3.2 具体语法细节与抽象语法的提取

• 具体语法中包含了许多与实际的语义执行（即解释器或编译器的核心实现逻辑）无关的细节。这些无关细节包括：空格的排版、注释内容、确切的括号匹配层级，以及具体的变量名选择等。
• 抽象语法树（AST）则是对具体语法的提炼，它会主动忽略具体语法中那些在语义层面上无关紧要的细节部分。
• 因此，从宏观来看，各种风格迥异的具体语法最终都能被解析成同一棵抽象语法树。例如，嵌套的函数调用 add1(sub1(17))（Applicative 风格）、Lisp 风格的 (add1 (sub1 17))、类似方法的调用 17.sub1.add1，以及汇编指令式的按行排列方式，它们在本质上的逻辑是相同的，都可以表示为相同的 AST。

4 扩展 Snake 语言 v0.1 "Adder"

在名为 "Snake" 语言的初期版本（v0.1 "Adder"）中，目标是为其添加基础的算术计算能力，并借此观察整个编译器流水线是如何受到影响和做出调整的。

• 具体语法示例：可以是一个简单的数字 42，也可以是基于函数调用的单步计算如 add1(42) 或 sub1(42)，或者是嵌套计算如 sub1(add1(add1(42)))。
• 语法规则描述：核心语法规则可以抽象为一个 <expr>。该 <expr> 可以被定义为一个具体的数字（NUMBER），也可以被定义为 add1(<expr>) 或是 sub1(<expr>) 形式。
• 支持参数输入：通过扩展该规则，可以接受一个外部输入。此时，程序的语法规则变为 def main(x): <expr>，而在 <expr> 的内部，除了数字和函数调用，还可以将变量 x 直接作为一个合法的表达式参与计算。

5 x86 汇编基础

x86 "抽象机器"将极其底层的硬件细节进行了抽象化，向开发者呈现了一个相对合理的、便于推导和生成代码的机器计算模型。

5.1 x86 寄存器

• 数量与容量：拥有 16 个通用的 64 位寄存器，例如 rax, rcx, rdx, rbx, rdi, rsi, rsp, rbp，以及 r8 到 r15。每个寄存器可存放一个 64 位（8 字节）的数值，总共提供了 128 字节的速度极快的存储空间。
• 特性：对于多数不同的操作指令，这些寄存器的地位基本上是等价的，无需严格区分。但其中有一个关键的例外是 rsp，它承担着“栈指针”（Stack Pointer）的重要职责。
• 位部分访问：处理器同样允许指令仅对某个寄存器的部分位进行操作。以 rax 为例，可以使用 eax 访问其低 32 位，使用 ax 访问低 16 位，使用 al 访问低 8 位，使用 ah 访问 8-15 位区间。为了简化实现逻辑，除非有特殊指令的强制性要求，我们默认处理和运用完整的 64 位寄存器形式。

5.2 核心指令集

• mov dest, src

• 语义与用途：该指令的作用是将源 src 中的值原样拷贝至目标内存位置 dest。这可以被广泛应用于数据的加载、数据的存储、常量的设定，以及执行复杂的地址推演（例如 mov rdx, 13 或 mov rax, rdi）。

• add dest, src

• 语义与副作用：此指令将 src 内的值累加到 dest 对应的值上，并用最终结果覆盖掉 dest 的原值，相当于高级语言中的 dest += src。作为一个附带影响（副作用），该指令还会同步更新 RFLAGS 寄存器的状态标志。

• 注意事项：如果涉及使用常量，常量最大只能使用 32 位的数值。

• sub dest, src

• 语义与副作用：此指令计算 dest 减去 src，并把所得结果保留在 dest 中，逻辑上等同于 dest -= src。与 add 类似，这也会更新 RFLAGS 寄存器，并且同样存在常量只能为 32 位的严苛限制。

• ret

• 语义：指令会从当前的栈顶（根据 rsp 指针指向的位置）弹出一个记录有返回地址的值，并使得程序的执行流跳转到该指定地址。

• 简化理解：如果您在实现一个函数，只要保证 rsp 在被调用期间经历种种操作后，能够在此指令执行前完好如初（即并未发生位移偏离），那么该指令就会精确安全地将控制权移交回外层的调用者手里。

6 System V AMD64 调用约定（基础阶段）

在多函数交互协作的环境下，为了保证不出错，目前的函数调用需遵守以下阶段性协定：

• 函数完成全部计算后，应当将其返回值确切地保存在 rax 寄存器内部。
• 任何函数若需要接收外部输入的第一个参数，该参数必然要优先存储于 rdi 寄存器之中。
• 寄存器 rsp 必须时刻紧盯栈内专门保存的函数返回地址，使得只要在 rsp 没有被擅自改动的前提下，ret 指令就能实现平稳、正确的跳转返回。

7 梳理总结

本文档对编译构建涉及的前端理论与后端基础概念做了详尽整理：

• 演示了语言功能的自然扩展：如增加 add1、sub1，以及变量输入的结合。
• 解释了具体代码表象（具体语法）及对应的验证过程（识别器/Recognizers）。
• 深入探讨了程序更深层的骨架表达（抽象语法/AST），及相应使用的解析工具链（Parsers 和 Parser generators）。
• 明确了通过枚举（enum）、模式匹配（pattern matching）、以及递归下降（recursive descent）等范式在 AST 上编程的思路。
• 罗列了基础的 x86 指令级操作知识：寄存器分配、数据移动（mov）、运算（add、sub）以及退出控制（ret）。
• 初步引入了关于在代码编译期直接计算值与在运行期进行计算的差异对比，这也是一种最基础的代码优化思想。

复杂表达式、求值顺序、基本块与延续（Continuations）

1 学习目标

本部分设定了以下核心学习目标：

• 完成局部变量的简单内存分配方案。
• 解决多参数（二元等）操作在执行过程中的语义问题。
• 掌握如何将嵌套的递归表达式编译为按顺序执行的底层汇编代码。
• 正式引入编译器中的第一版中间表示（Intermediate Representation, IR）。

2 编译 Let 表达式与内存分配

在解释器层面，程序中每个变量的值通常被保存在类似 HashMap 的数据结构中。但在编译为机器码时，我们必须确保代码在运行时能够通过内存地址访问到每个变量的具体值。

2.1 变量到内存的映射

• 为了成功编译代码，编译器需要建立一套机制，将变量名称明确映射到特定的内存位置。
• 当一个变量超出其作用域时，它的值就不再被需要，其占用的内存应当能够被复用。
• 内存分配的核心原则是：只需要确保分配的内存位置相对于当前作用域内的其他存活变量是唯一的即可，以避免内存浪费。
• 实现这一点的关键在于设计合适的环境（Environment）结构来追踪变量的作用域与内存槽位。

2.2 Let 表达式的代码生成策略

• 普通表达式计算完成后，将其结果存放在 rax 寄存器中。
• 遇到 let 变量绑定时，将此时 rax 中的值推入（保存）到栈的内存空间中。
• 当后续需要查找并使用该变量时，再从栈对应的内存位置将数据加载回 rax 寄存器中。

3 x86 内存模型与约定

为了更好地进行变量分配，必须了解目标硬件的内存架构。

• 寄存器：x86 架构拥有 16 个通用的 64 位寄存器（包括 rax, rcx, rdx, rbx, rdi, rsi, rsp, rbp, 及 r8-r15）。这构成了 128 字节读取速度极快的可用存储区。
• 内存空间：抽象机器允许我们按字节访问极其庞大的内存区域。尽管地址是 64 位值，但当前硬件普遍只使用低 48 位，这为我们提供了高达 $2^{48}$ 字节（约 128 TB）的可用寻址空间。

3.1 mov 指令细节

mov dest, src 指令支持寄存器或内存地址之间的数值传递，但在使用方括号 [] 对地址进行“解引用”时有严格的语法限制：

• mov rax, rdi：将 rdi 中存储的值直接拷贝到 rax。
• mov rax, [rdi]：将 rdi 寄存器内部数值作为内存地址，读取该地址所指向的内存数据，并加载到 rax。
• mov [rax], rdi：将 rdi 的值写入到 rax 所指向的内存地址中。
• 不允许的操作：mov [rax], [rdi] 在 x86 语法中是非法的，不能在一条指令中直接实现内存到内存的移动。

3.2 栈内存约定

我们依靠“栈指针”（rsp）来追踪与操作栈内存。

• 调用约定规定：当函数被调用时，rsp 会精确指向调用者（Caller）的返回地址（Return Address）。
• 较高的内存地址区域，是由调用者所拥有并已经使用的。
• 较低的内存地址区域，对于当前被调用的函数（Callee）来说是自由且空闲的，可以任意分配。
• 因此，我们通常利用栈上低于 rsp 的空闲空间来存储局部变量（例如按偏移量 -8*1, -8*2 来存放变量）。

4 扩展源语言：二元操作与语义探讨

在为编译器进一步扩充基础运算（如二元算术运算）时，需要再次审视编译器构建的几个核心问题：代码的语法、代码的语义、如何在汇编中实现语义、以及如何通过代码生成汇编。

• 抽象语法的优势：对于表达式解析，抽象语法树（AST）本身是不需要记录括号等具体语法特征的。解析器（Parser）会在前期应用操作符优先级规则（如 PEMDAS）来消除歧义，最终产出唯一的 AST 树状结构。
• 求值顺序的语义问题：遇到如 e1 op e2（例如减法或乘法）的二元表达式时，语义上我们必须明确是先计算 e1 还是先计算 e2。求值顺序的区别在处理具有副作用（如打印或改变外部状态）的语言扩展中会带来截然不同的运行结果。

5 引入中间表示（Intermediate Representation, IR）

直接将复杂的二元操作编译为 x86 代码远比一元操作困难。

• 主要冲突在于：当前策略一直使用 rax 作为中间结果存放地。但复合表达式中包含大量的隐式中间结果，如果在二元操作中直接递归求值左右两段表达式，新计算的值会立刻覆盖掉之前存在 rax 中的尚未参与运算的值。
• 解决方案：我们需要将抽象语法树转化为一种新形式，在这个形式里，所有的中间结果都会被显式地赋予一个变量；并且所有的运算操作，必须只针对“立即表达式”（如数字常量或单一变量）来执行。
• 这就引入了 中间表示（IR） 的概念。我们在 AST 和汇编代码之间，插入一个降级（Lowering）的处理阶段。
• IR 是编译器内部使用的一种编程语言，人类程序员不会直接去编写它，它完全由编译器的转换逻辑生成。
• IR 更加贴近目标机器的逻辑，但巧妙地抽象掉了底层汇编语言（如寄存器与内存严格区分等）的繁琐复杂性。它还能够统一对接不同的硬件后端平台，并在这一层集中进行代码优化。

6 静态单赋值片段（Static Single Assignment, SSA）

本课程中使用的核心中间表示形式被称为静态单赋值（SSA）。为了满足当前需求，我们只使用了 SSA 的一个简化片段：将源程序最终编译为单一的“基本块”（Basic Block）。

6.1 SSA 与源语言的差异

• SSA 中不存在向左嵌套的 Let 变量绑定逻辑。
• 作为操作指令的参数，必须是立即可用的“立即值”（Immediate values），不能传递复杂的嵌套表达式。
• 整个代码块必须以一个显式的 return 语句作为结尾。

6.2 SSA 与机器汇编的差异

• 在 SSA 中，所有局部变量在赋值后即为“不可变”（Immutable）的，且没有真实的物理寄存器与内存槽位的区分。
• 它将硬件的调用约定进行了高度抽象处理。

6.3 SSA 程序结构总结

• 一个 SSA 程序通常包含一个程序入口点、一个输入参数以及一个基本块。
• 基本块是一连串的针对立即值（变量或常量）执行的简单图灵原语操作，末尾跟着返回指令。
• 为了确保无状态冲突，SSA 中所有的绑定变量在全局范围内都必须拥有完全独一无二的名称。

7 延续（Continuations）与从 AST 生成 SSA

由于 SSA 剥离了复杂性并极其类似于极简版的源语言，从 SSA 生成 x86 汇编就变得极其直截了当（应用之前单一 let 编译的技术，再加上对二元指令的支持即可）。难点在于如何将复杂的 AST 降级为线性的 SSA。

7.1 后序遍历与扁平化

• 观察生成的 SSA 代码可以发现，每一行扁平化的赋值语句其实都对应着 AST 中的一个子表达式。
• 而原本嵌套在最深处的子表达式，会被首先求值并放置在生成的 SSA 代码的顶部。
• 这本质上是一个使用“后序遍历”（Postorder Traversal）将树形数据结构转化为扁平化链表的过程。

7.2 延续传递风格（Continuation-passing Style）

• 为了以组合且优雅的方式生成这段代码，我们在编译子表达式时，必须传入一个额外的参数，这个参数回答了一个关键问题：“在这个子表达式计算完之后，接下来需要运行什么代码？”
• 这个“接下来需要运行的代码”就被称作该表达式的延续（Continuation）。
• 在实际的转换逻辑中，用于表达式降级处理的函数需要接受这个“延续”参数。该参数主要由两部分构成：

1. 用于接收当前子表达式计算结果的目标变量的名称。
2. 当编译生成的代码顺利把结果放置到该目标变量后，下一步需要继续执行的代码块（Block）。

• 为了保证逻辑的严密，在这个平铺的过程中，编译器必须不断地生成全新的独立变量名，确保这批生成的变量互不相同，同时也与源程序里的原有变量绝不重名。

编译器中的条件控制流与 SSA 扩展 (Compiler Conditionals and SSA Extension)

1 学习目标

本节内容的核心目标是理解并实现编译器中的条件控制流：

• 掌握条件表达式的语法（Syntax）和语义（Semantics） 。

• 理解在底层 x86 汇编中是如何编码条件控制流的 。

• 理解 x86 架构中指令指针（Instruction Pointer）是如何被（隐式地）操作的 。

• 学习如何将现有的基本块中间表示（Basic Block IR）扩展为支持条件分支的静态单赋值中间表示（SSA IR） 。

• 掌握从高级语言的条件表达式向 SSA IR 进行降级（Lowering）的过程 。

2 扩展 Snake 语言：引入 "Boa"

在构建编译器时，每次扩展语言都需要解决四个核心问题：

1. 我们要编译的语言语法是什么？

2. 该语言的语义是什么？

3. 我们如何在汇编代码中实现这些语义？

4. 我们如何调整中间表示（IR）以适应新特性，并最终通过程序化方式生成汇编代码？

在之前的 "Adder" 版本中，编译器仅支持直线型代码（Straightline code），即按顺序执行算术运算，并将变量和中间结果存入内存 。而在 "Boa"（Snake v0.2）版本中，我们将为语言引入条件控制流（Conditional control flow）和循环控制流 。

3 条件表达式的语法与语义

3.1 具体语法与抽象语法

• 具体语法：引入了类似 Python 风格的条件判断：if <expr> : <expr> else: <expr> 。

• 抽象语法（AST）：在表达式枚举结构中增加了一种 If 变体： If { cond: Box<Exp>, thn: Box<Exp>, els: Box<Exp> } 。

3.2 语义规则

• 布尔值约定：语言本身不包含独立的布尔数据类型，只包含整数。我们遵循类似 C 语言的约定：0 代表假（False），其他所有整数均代表真（True） 。

• 强制的 else 分支：在 "Boa" 中，if 是一个表达式（类似于 Rust 的 if 或 C 语言的三元运算符 ? [cite_start]:），它必须能计算出一个值。因此，if 表达式强制要求必须包含 else 分支 。例如：if 5: 6 else: 7 的结果是 6，if 0: 6 else: 7 的结果是 7 。

• 短路求值（惰性求值）：语义上必须保证在运行时，if 表达式只会求值两个分支中的其中一个，绝不能同时求值 thn 和 els 分支，这在具有外部副作用的程序中尤为关键 。

4 x86 架构中的控制流

在 x86 汇编中，并没有直接对应高级语言 if 的原语，因此我们需要利用底层的跳转指令和状态寄存器来构建条件控制流 。

4.1 指令指针与顺序执行

• rip 寄存器：下一条要执行的指令由专门的“指令指针”寄存器 rip 决定 。

• 在抽象机器中，每一步执行都从读取 [rip] 指向的内存中的二进制汇编指令开始 。

• 绝大多数指令（如 mov, add）在执行完毕后，会将 rip 增加该指令编码的字节长度，从而使得下一时刻程序顺次执行内存中的下一条指令 。

4.2 跳转指令

汇编代码的执行本质上是在内存地址间穿梭，汇编标签（Labels）实际上是内存地址的别名 。

• 无条件跳转 jmp loc：直接将指令指针 rip 设置为 loc，打破顺序执行 。loc 通常是同一文件中的标签，也可以是寄存器或内存地址 。

• 条件跳转 jcc loc ：这是一系列条件跳转指令的统称，cc 代表具体的条件码（Condition code）。如果满足特定的条件码，则将 rip 设置为 loc；否则，像普通指令一样顺序递增 rip 。

4.3 rflags 寄存器与比较操作

条件跳转的判定依赖于硬件的状态标志，这些标志存储在 rflags 寄存器中 。

• rflags：一个 64 位寄存器，包含多个按位存储的布尔标志 。最相关的几个标志包括：

• OF (Overflow Flag)：溢出标志。发生溢出时为 1，否则为 0 。

• SF (Sign Flag)：符号标志。计算结果为负数时为 1，否则为 0 。

• ZF (Zero Flag)：零标志。计算结果为 0 时为 1，否则为 0 。

• 算术指令（如 add, sub）会作为副作用更新这些标志，但 mov 指令不会改变标志 。

• cmp arg1, arg2：比较指令。它的行为类似于执行减法操作（arg1 - arg2）以便根据计算结果更新 rflags 的各项标志，但它不会将结果写回 arg1 。

• test arg1, arg2：测试指令。其行为类似于按位与（Bitwise AND），仅用于更新标志位而不修改操作数本身，常被用来检查特定位是否已被置为 1 。

4.4 常见条件码（Condition Codes）

条件码的作用是将 rflags 中的多个标志组合解释为逻辑布尔条件 ：

• e / z (等于 / 为零)：当 ZF 为 1 时满足 。

• ne / nz (不等于 / 不为零)：当 ~ZF 时满足 。

• l (小于)：当 OF ^ SF （溢出标志与符号标志的异或结果为真）满足时触发 。

• le (小于等于)：当 (OF ^ SF) | [cite_start]ZF 满足时触发 。

• g (大于)：等于小于等于条件的取反，即 ~((OF ^ SF) | ZF) 。

• ge (大于等于)：等于小于条件的取反，即 ~(OF ^ SF) 。

5 扩展 SSA 与基本块编译

为了支持分支结构，必须改进现有的编译器中间表示（SSA）。以前的 SSA 只包含单一的操作序列并以 return 结束 。 当前的 SSA 被扩展了如下能力：

1. 允许在内部定义多个额外的、带有独立标签的代码块，即基本块（Basic Blocks） 。

2. 允许一个基本块以 跳转分支（Branching） 的形式作为结束，而非仅仅依靠返回（Return）结束 。

5.1 基本块的汇编编译方案

• 对于 SSA 中的每一个基本块，编译器均会生成一段带有相应标签名称的汇编代码块 。

• 需要保证条件分支的代码块在其主基本块的代码之后进行发射（Emitted） 。

• 高级条件分支可以利用 x86 的条件跳转指令（jcc）与无条件跳转指令（jmp）巧妙结合来编码映射 。

6 条件表达式的延续（Continuations）与合并点（Join Points）

将抽象语法树（AST）降级至 SSA 时，最大的难点在于处理 if 表达式的延续（Continuation）。所谓的延续，是指当 if 表达式本身求值结束后，程序接下来理应继续执行的代码逻辑 。

6.1 延续复制导致的指数爆炸

• 朴素策略：分别为 thn 和 els 分支创建带有独特标签的块。编译并求值条件 cond 后，通过跳转进入对应分支 。为了继续执行表达式后的步骤，将后续“延续”的代码段直接复制到两个分支的末尾 。

• 致命缺陷：这种做法虽然在行为逻辑上没问题，但在工程实践中是完全不可接受的 。如果代码中包含若干串联的 if 表达式，不断对延续代码进行拷贝会导致生成文件的体积呈现指数级爆炸（Exponential Blowup） 。优秀的编译器优化应当维持生成的代码体积呈线性增长 。

6.2 引入合并点（Join Points）

为了做到在不复制代码的前提下共享同一段延续，我们需要在 SSA 范式中添加 合并点（Join Points） 这一概念。

• 合并点是一个独立的全新基本块，承载着公共延续的逻辑。当两个独立条件分支各自执行完毕时，它们统一跳转入该合并点 。

• 该方法正是利用了跳转指令通过标签即可无成本完成控制流转移的优势 。

6.3 维持 SSA 属性及参数化块

合并点面临了一个严峻的 SSA 挑战：由于在不同的分支执行路线上，某个变量最终可能产生截然不同的值，我们该如何将这个值正确汇聚并传递给延续代码，同时不破坏静态单赋值特性？

• 方案一：普通变量覆盖赋值（破坏 SSA 规则） 在两条分支中对同一个共享变量 x 进行重写赋值 。

• 弊端：直接打破了静态单赋值原则。由于延续块无法静态确定 x 最后被哪里定义，这将使后续数据流分析与性能优化举步维艰 。

• 方案二：引入 $\phi$ 节点（Phi Nodes） 这是正统的 SSA 操作形式，通过伪指令 x = ϕ(x1, x2) 进行汇聚 。

• 工作机制：它实质也是对 x 的一次赋值，但这次赋值的数据来源究竟是 x1 还是 x2，是由程序“刚刚是从哪个分支跳跃而来”所决定的 。

• 优缺点：由于完美保持了 SSA 属性，它在 LLVM、GCC 等资深工业级编译器中统治了数十年 。但它的语义十分怪异，由于该节点必须严格置于块的最顶端，在实际生成汇编时，真实的移动操作（mov）必须被巧妙前置塞进前驱块里才能运作，带来了诸多不便 。

• 方案三：参数化块（Parameterized Blocks） 将延续基本块设计为可以接受外部传入参数的“函数”。例如通过 l(x1, x2) 的形式暴露出参数占位符 。

• 工作机制：当执行跳转时，前驱块必须同时完成实参的传递，如执行 br l(y1, y2) 。

• 优缺点：不仅能完全维系 SSA 属性，而且在生成底层汇编代码以及维护逻辑一致性上远比 Phi 节点简明清晰。如今较新的现代编译器技术栈（如 Swift, MLIR 等）越来越倾向于使用此方案 。

7 控制流图（Control Flow Graph, CFG）

控制流图是一种将 SSA 程序进行可视化剖析的数据结构 。

• 顶点（Nodes）：CFG 中的图节点精确对应 SSA 的每一个基本块 。

• 边（Edges）：节点之间的有向边对应着基本块末尾触发的程序分支 。

• 从树到有向无环图（DAG）：普通的线性条件分支如果不加以复用，只能长成庞大的树状流结构；而在引入合并点技术之后，分开的分支又得以合流，这就构建成了更为紧凑的控制流 DAG（有向无环图） 。使用 DAG 结构化地记录代码流程，从根源上消除了复制带来的指数爆炸灾难 。在后续加入了循环控制特性的章节中，流图将进一步摆脱无环的限制 。

编译器构造：参数化块、布尔值与尾调用

1 核心学习目标

本阶段的学习重点在于掌握以下几个编译器的核心概念与机制：

• 理解为什么需要引入合并点（Join points）、参数化块（Parameterized blocks）以及相应的代码生成技术。
• 理解在向编程语言中引入多种数据类型时所面临的设计权衡与选择。
• 掌握如何将尾调用（Tail-calls）高效地编译转换至 SSA 参数化块以及底层的汇编代码中。

2 条件分支与延续的挑战

在编译条件表达式（如 if 语句）时，除了需要处理分支逻辑本身，还必须妥善处理该表达式的延续（Continuation）。延续指的是在表达式的结果计算完毕之后，程序接下来应当执行的代码逻辑。由于最终的结果可能是在 if 的任意一个分支中计算得出的，因此这段延续代码必须保证在任何一条分支执行结束后都能被正确触发运行。

2.1 复制延续带来的指数爆炸问题

一种最直观的编译策略是将这段延续代码直接复制粘贴到 then 和 else 两个分支的末尾。然而，当程序中存在连续的或嵌套的 if 表达式时，这种简单的复制策略会导致生成的 SSA（静态单赋值）程序体积发生灾难性的指数级膨胀（Exponential Blowup）。

2.2 解决方案：合并点 (Join Points)

为了在汇编代码级别避免无谓的复制，编译器可以创建一个全新的代码块，并让每一个条件分支在执行完毕后都跳转（Jump）至该块。这种做法利用了汇编标签（Label）跳转的极低成本，实现了多分支对同一段延续代码的“共享”。合并点正是用于处理不同代码执行路径共享同一延续的必备机制。

3 参数化块 (Parameterized Blocks)

为了在中间表示（IR）层面优雅地实现合并点，编译器引入了参数化块的概念，它直接在 SSA 语法结构中表示延续。

• 基本块可以像函数一样拥有输入参数，这些参数的作用域仅限于该基本块内部。
• 当控制流分支需要跳转至一个参数化块时，必须同时为其提供对应的实参（例如 br l(y1, y2, y3)）。
• 优势：这种方法完美维持了 SSA 范式的属性，使代码生成过程和良构性条件都变得十分简单，当前包括 Swift、MLIR 和 MLton 在内的较新式基于 SSA 的编译器都采用了这种设计。
• 劣势：它在 SSA 程序的语法上将不同的合并点分离开了，并且由于学术界大多使用传统的 $\phi$ 节点（Phi nodes）记号，学习者在阅读相关论文时需要进行思维和符号的转换。

3.1 SSA 程序的良构性 (Well-formedness)

与原语言一样，SSA 程序同样拥有严格的作用域规则。

• 子块（Sub-blocks）可以声明块的名称，这些块名只能在其父级子块声明的体内被引用。
• 操作指令和基本块可以声明变量，这些变量只能在其声明之后的块体内部被使用。
• 编译器开发者可以根据上述规则将抽象语法树的作用域检查器适配到 SSA 层面，这能作为一个有效的“代码静态检查（Linting）”过程，在调试期间快速捕获格式非法的 SSA 生成错误。

4 扩展数据类型与布尔运算

在编译器的演进版本（例如名为 "Boa" 的阶段）中，引入了逻辑操作符，这意味着语言将面临多数据类型（整数和布尔值）的混合处理。 处理不同数据类型主要有四种主流策略：

1. 静态拒绝类型混合：严格区分整数和布尔值，在编译阶段拒绝类型不匹配的程序。
2. 静态插入强制转换：在编译期间自动为不同但相关的类型插入双向转换逻辑。
3. 动态检查（强动态类型）：在运行时严格检查类型，发现类型不符即抛出错误。
4. 动态强制转换（弱动态类型）：允许变量包含任何类型，在类型化操作的输入端自动插入动态的强制类型转换。这是编译器当前阶段所采用的策略。

4.1 数据表示与强制转换规则

• 布尔值：在底层表示中，true 为 1，false 为 0。
• 整数向布尔转换：任何非零的 64 位值都会被强制转换为 1 (true)，零则转换为 0 (false)。
• 布尔向整数转换：直接映射，true 为 1，false 为 0。

4.2 x86 底层实现细节

• setcc loc 指令族可以根据条件码（Condition code）的结果将对应的最低位赋值到 loc，但一个极为特殊的限制是 loc 必须是一个 1 字节大小的寄存器（例如 al）。
• 在实现逻辑运算时，不能简单粗暴地依赖底层的按位操作符（如 and, or）。例如 0xF0 and 0x0F 计算结果为 0 而非预期的逻辑真 1。
• 强制转换的逻辑既可以在汇编生成阶段直接注入到每个操作前，也可以作为诸如 intToBool 的显式操作在 SSA 层面进行表示，后者具有能被后续优化阶段消除的显著优势。

5 循环控制流与函数支持

为了实现诸如有限状态机级别的计算能力，编译器必须支持循环控制流图，其源级表达通常分为函数式（递归、尾调用）和命令式（循环、可变变量）两大阵营。

5.1 一阶函数与作用域

• 在一阶（First-order）语言中，函数不能被作为值进行传递。因此可以把函数视为独立的命名空间，并且允许函数名发生遮蔽（Shadowing）。
• 函数定义默认是支持递归和相互递归（Mutual recursion）的，所有互相递归的函数均在彼此的作用域内可见。
• 因为函数调用的目标地址是静态可知的，编译器可以在静态编译阶段进行元数检查（Arity-checking），确保参数的数量准确无误。

6 尾部位置与编译尾调用 (Tail Calls)

6.1 什么是尾位置？

判断一个表达式是否处于“尾位置（Tail Position）”，完全取决于它的上下文结构：

• 被调用函数的结果如果立即成为外层调用者的返回值，则该调用处于尾位置。
• let 表达式的绑定部分以及基础的算术和函数调用参数绝不在尾位置，因为计算完它们后还需要执行后续操作。
• 仅当 let 本身或 if 本身处于尾位置时，其 let 主体或 if 的条件分支才同样处于尾位置。
• 函数声明的主体天然处于尾位置。

6.2 尾调用的编译策略

• 每个函数定义可以直接编译为相应的 SSA 基本块。
• 当识别出代码是尾调用时，由于不需要准备返回和处理后续的延续代码，因此可以直接将其编译为一个携带参数的跳转分支（Branch with arguments），按从左向右的顺序处理参数即可。
• 难点与隐患：在语义上，带参数的分支要求所有变量经历一场“同时发生的更新”。而在真实的 x86 架构中，这些移动操作必须被依次序列化。若不加防范，这种序列化极其容易造成内存覆盖导致正确性故障。为了安全起见，目前一种简单的方法是引入额外的临时变量来暂存目标参数，以确保新变量被分配到更安全的栈位置，从而规避覆盖风险。

7 SSA 代码的最小化优化 (Minimal SSA)

如果函数仅在局部发生尾调用，可以将其平滑转换为带参数的 SSA 块，但这往往会产生不够精简的中间表示。

• 极简 SSA 目标：所谓极简的 SSA 程序，是指那些尽可能少使用块参数（或 $\phi$ 节点）的程序。每一个多余的参数在底层都意味着产生多余的 mov 指令和潜在的内存开销。
• 实现步骤：SSA 最小化主要包括两个优化阶段：

1. 块下沉 (Block Sinking)：通过支配（Dominate）关系的判断，如果块 g 只有在块 f 内部才被调用，说明 f 支配了 g。此时可将 g 的定义推入到 f 内部，从而使得大量的外部变量直接进入 g 的作用域范围，无需再作为参数传递。
2. 参数丢弃 (Parameter Dropping)：在分析后如果发现某个参数 x 永远只被外部的同一个变量 y 或者其自身进行实例化，那么该参数 x 就是冗余的。编译器可以直接剔除参数 x，并在其作用域内用 y 替换所有相关的引用。

尾调用、极简 SSA 与命令式代码编译 (Tail Calls, Minimal SSA & Imperative Code)

1 学习目标

本部分设定了以下几个核心学习目标：

• 澄清和纠正先前关于布尔值实现的细节。
• 明确在什么情况下，函数可以被直接编译为 SSA 的基本块。
• 探讨将“带参数分支（Branch with arguments）”编译至底层 x86 汇编代码时可能遇到的陷阱与隐患。
• 定义什么是极简 SSA 形式（Minimal SSA form），了解其带来的优势以及构建它的具体步骤。
• 学习如何将命令式（Imperative）代码编译并转换为 SSA 形式。

2 布尔值表示与强制类型转换 (Coercions)

2.1 运行时的布尔值表示方案

在运行时处理布尔值时，通常有两种直观的方案：

1. 宽泛表示：所有 64 位的值都可以作为有效的布尔值。其中 0 代表 false，其他任何非零值都代表 true。这种方案更贴近很多高级语言的语义。
2. 严格表示：只有绝对的 0 和 1 才是合法的布尔值。这种方案在底层硬件指令的实现上更加容易支持。

2.2 x86 按位操作与逻辑运算的差异

• x86 提供了 and dest, src 和 or dest, src 指令，但这些是按位运算（Bitwise），而不是逻辑运算（Logical）。
• 例如，如果直接对 0xF0 和 0x0F 执行按位 and 操作，结果会是 0。但在高级语言的逻辑概念中，这两个非零值都代表 true，它们的逻辑 and 结果理应也是 true（非零）。
• 只有当所有的输入都被严格限定为 0 或 1 时，按位操作的结果才会与逻辑操作完美吻合。

2.3 强制转换 (Coercions) 的实现策略

为了解决上述差异，编译器需要引入强制转换。

1. 在汇编层实现：在每一次执行逻辑运算之前，直接生成汇编代码将输入值强制转换为 0 或 1。
2. 在 SSA 层实现：在 SSA 中间表示中显式地添加一个 intToBool 的强制转换节点，随后再由该节点生成对应的底层汇编代码。

• SSA 层实现的优势：这种显式的类型转换不仅极大简化了后端代码生成阶段的逻辑，更重要的是，它能在编译器的优化阶段被各种分析遍（Passes）识别，并在冗余时被直接优化消除。
• 转换为 SSA 的流程示例：表达式 x && y 在 SSA 中会被降级表示为 $b = intToBool(x); $c = intToBool(y); res = b & c。
• 底层 x86 实现细节：intToBool(y) 在底层的汇编实现通常是利用 cmp rax, 0，随后将 rax 清零，并利用 setne al 指令结合条件码将最低位赋值为 1（当原值非零时）。

3 扩展语言：支持循环控制流图

为了使语言能够表达带有循环的控制流图（Cyclic control-flow graphs），通常需要引入两类源级别的编程特性：

1. 函数式特性 (Functional)：递归函数（Recursive functions）以及尾调用（Tail calls）。
2. 命令式特性 (Imperative)：while/for 循环语句，以及可变变量（Mutable variables）。

3.1 递归与变量捕获

• 递归函数：函数定义本身是递归的，即该函数名不仅在其定义之后的延续上下文中可见，在其自身的函数体内部同样是在作用域内的。
• 相互递归 (Mutual Recursion)：如果多个函数定义被 and 关键字连接声明，它们彼此之间均在对方的作用域内，可以互相调用。
• 变量捕获 (Variable Capture)：函数体可以合法地访问并在其定义时刻处于作用域内的外部变量。

4 尾位置与尾调用 (Tail Position)

函数调用何时能被直接编译为一个简单的带参数分支（Branch with arguments），而不是一次真正意义上消耗栈空间的函数调用？答案是当该调用处于 尾位置（Tail Position） 时。

4.1 尾位置的定义

• 当被调用函数的计算结果立即成为外层调用者的直接返回值时，称该调用处于尾位置。
• 如果在尾位置，由于调用后无需执行其他代码，我们可以直接抛弃当前的栈帧状态，使用一个带参数的分支跳转直接取代真实的函数调用机制。否则，这必须是一个真实的函数调用，需要向调用栈中压入数据以保留当前状态。
• 表达式是否处于尾位置，完全取决于它的上下文环境，而非表达式自身的长相。

4.2 各种表达式的尾位置判定规则

• 程序的 main 表达式（最外层表达式）永远处于尾位置。
• 基础运算操作（prim）的参数或是函数调用的参数绝不在尾位置，因为对它们求值结束后，还要接着执行该运算或调用本身。
• let 绑定的右侧表达式绝不在尾位置，因为算完后需要执行 let 的主体（Body）。
• 只有当 let 表达式本身处于尾位置时，它的主体（Body）才处于尾位置。
• if 表达式的条件（Cond）位置绝不在尾位置，算完后需要执行条件分支判定。
• 只有当 if 表达式本身处于尾位置时，其内部的 thn 和 els 分支才处于尾位置。
• 函数声明的主体（Body）永远处于尾位置。

5 将尾调用编译为带参数的分支

5.1 编译策略

• 每个函数的定义可以直接编译成对应的 SSA 基本块。
• 相互递归的函数也会被编译成相互递归引用的代码块。
• 对于尾部发生的函数调用，编译器不生成 call 指令，而是从左到右依次处理参数，并将其编译为一次携带这些参数的直接分支跳转（Branch with arguments）。

5.2 带参数分支的底层陷阱：序列化更新问题

• 语义要求：在 SSA 中，“带参数的分支”在语义上要求所有的变量更新操作必须是 “同时发生（Simultaneous）” 的。
• 架构现实与覆盖风险：真实的底层 x86 架构并不支持将多个内存位置同时赋值，我们不得不把这种同时赋值的逻辑强行序列化（拆分成多条 mov 指令顺次执行）。如果不加防范，这种序列化极其容易导致变量互相覆盖。例如在赋值 b = y 的途中，y 所在内存位置可能在上一条指令赋值 a = ... 时已被错误覆盖。
• 临时解决方案：为了保证正确性，编译器会引入额外的临时变量。即将参数先统统搬移到栈上更高的、绝对安全不被覆盖的临时新槽位中，最后再进行跳转（后续我们会在寄存器分配阶段利用更优的方案彻底解决它）。

6 极简 SSA 形式 (Minimal SSA) 与优化

尽管函数式代码可以直接且容易地转化为 SSA，但朴素的转换产生的往往不是最优解。

• 极简 SSA 定义：一个 SSA 程序被称为是“极简的”，当且仅当它使用了尽可能少的块参数（也即尽可能少的 Phi 节点）。
• 为何追求极简：向带有参数的代码块进行分支跳转时，底层通常需要生成 mov 数据移动指令，这可能会触发昂贵的内存读写。消除不必要的参数就是消除无谓的性能开销。

6.1 SSA 最小化的两大阶段

1. 块下沉 (Block Sinking)：

• 将基本块的定义尽力向 SSA 抽象语法树的内部“深推”。
• 如果块 f 完全支配（Dominates）块 g（即 g 只有可能在 f 或 g 内部被调用），那么我们就可以将 g 的定义整个移动到 f 的作用域内部。
• 结果：原本必须作为参数从外部传递给 g 的变量，现在直接置于了 g 的可用词法作用域内，参数由此可以被优化掉。

2. 参数丢弃 (Parameter Dropping)：

• 通过分析，如果发现某个参数 x 在所有可能的调用路径上，永远只被唯一的一个特定变量 y（或是 x 它自身）实例化，那么参数 x 就是冗余的。
• 编译器可以直接删掉该块参数，并在代码块内部将所有出现 x 的地方无缝替换为外部的作用域变量 y。

7 命令式语言扩展：Imp

在函数式特征之外，课程引入了具有“命令式 (Imperative)”特征的语言子集——被称为 "Imp"。 它的主要特性包括：严格区分“语句 (statement)”与“表达式 (expression)”、包含循环结构 while、包含可变变量 (Mutable variables)，以及控制流关键字 return / break / continue。

7.1 良构性检查 (Well-formedness)

在编译前，针对命令式代码必须执行相应的安全检查：

1. 作用域与遮蔽：和之前一样，要求变量必须先声明后使用。允许变量遮蔽（Shadowing）。在语义上，被遮蔽的变量和一个新的同名可变变量是两个截然不同的事物。为了避免混淆，通过重命名机制分配唯一名称。
2. 返回安全：如果实现的是一个必须返回结果的逻辑，编译器必须检查验证每一条独立的代码执行路径最终都能以一个 return 语句妥善结束。
3. 裸中断防护：必须验证 break 和 continue 关键字绝对只能出现在一个封闭的 while 循环体内部。

7.2 编译 Imperative 代码至 SSA 的五个步骤

命令式语言最大的颠覆是变量的更新。在 SSA 范式中变量其实是绝对不可变（Immutable）的，这种冲突如何调和？

1. 表达式与声明：行为同此前的 Adder 一致。变量的初次声明在 SSA 中体现为不可变的常量赋值初始化。
2. 处理变量更新 (Variable Updates)：

• 核心思想是“追踪变量版本”。在一个环境中，编译器会记录当前作用域内每个变量最新指向的具体“版本（Version）”。
• 任何对可变变量 x 的覆盖更新操作，在 SSA 生成阶段都会被转化成一个对其全新版本影子变量的赋值。更新 x 相当于利用新计算出的值创建了一个在 SSA 中永远绑定的新常量。

3. 条件分支与合并点 (Join Points)：

• 由于 if-else 分支可能在两条路径上更新不同数量的外部变量，汇合时如何处理？
• 方案：采用粗略 Phi 节点插入法 (Crude ϕ-node insertion)。简单粗暴地将当前作用域内所有已知变量一股脑全部作为合并点块的参数传入。尽管这产生了海量冗余参数，但我们在后处理阶段仰赖前面提到的参数丢弃优化遍（Pass），将其自动清理。

4. 编译 While 循环：

• 每个 while 循环都会在控制流图中产生特定的合并点。由于循环有两个潜在的前驱入口（从循环外刚进入，以及上一次循环体执行完毕跳回），循环的 条件判定块 (Check block) 本身就是一个典型的合并点，必须加入块参数。
• 如果循环内部出现了 continue 操作，它代表的是无条件跳回到循环判定的开头。

5. Break、Continue 与 Return：

• return 很简单：编译对应表达式并输出一条结尾终止指令即可。
• break：分支跳转到负责循环退出后收尾工作的“出口块 (Exit block)”。
• 当使用 break 时，出口块可能接收来自判定失败的正常跳转，也可能接收来自循环内部中途 break 的提前跳转，因此出口块同样升级为了一个需要参数的合并点。

一个重要结论 (Theorem)：只要命令式代码结构工整（像循环、If 都符合良好嵌套），直接利用粗略 Phi 节点参数传入策略，加上后续简单的参数丢弃优化，由于无需进行复杂的块下沉（因为嵌套结构已天然保证了支配关系），就能直接产出极为优秀的极简 SSA 形式。

8 SSA 范式的优势总结

为何现代的命令式语言编译器（它的前端代码充斥着变量值的改写），在其中段（Middle-end）分析时都要费尽周折地转化成没有任何变量变异（Mutation）的 SSA 形式？

• 程序变得极易推导分析：如果出现 y = ... 和 z = ... 两个完全相同定义的变量，在 SSA 中我们随时可以直接将后续的 z 放心替换为 y（即公共子表达式消除优化）。这在随时会被随机更新的传统命令式结构中是完全不可能安全做到的。
• 极其高效的数据流图构建：在 SSA 结构下，分析算法可以跳过海量无关紧要的控制流干扰，将每一个“变量的使用端”直接与它的“唯一生产端”建立高速映射。更密集的信息和更少的指针追踪，使得编译器在实现诸如常量折叠、活跃性分析时执行得更加迅速和轻量。

编译器构造：可变变量、循环与非尾调用

1 学习目标

本节核心目标围绕如何处理带有状态变异的命令式代码，并将其转换为高度优化的底层结构：

• 了解如何将包含可变变量的代码编译为静态单赋值（SSA）形式，同时严谨地满足 SSA 的“静态单赋值”核心约束属性。
• 掌握如何将控制流中的循环（Loops）结构编译并表达为 SSA 的基本代码块。
• 探讨设计哲学：既然底层目标汇编语言在本质上是命令式的，为何编译器要在中间阶段大费周折，把命令式的源代码专门转换为一种函数式的中间表示（IR）？
• 学习非尾部的函数调用（Non-tail function calls）及其在底层系统中的栈管理实现。

2 表达循环控制流的语言特性

为了在源代码级别表达具有循环控制流图（Cyclic control-flow graphs）的程序，主流语言通常提供两类编程特性：

1. 函数式特性：通过递归函数（Recursive functions）与尾调用（Tail calls）来实现循环。正如之前所学，如果我们只允许发生尾调用，这些函数在编译器的底层表示中，与 SSA 中的参数化块（Parameterized blocks）几乎是完全等价的。为了获得更优的极简 SSA 形式，我们需要通过块下沉（Block sinking）和参数丢弃（Parameter dropping）等后置处理。
2. 命令式特性：通过显式的循环语句（Loops）和可变变量（Mutable variables）来实现状态更新与重复执行。

3 命令式 Snake 语言（Imp）设计

为了研究后者的编译过程，引入了一个具有典型命令式特性的扩展语言 "Imp"，它具有以下显著特征：

• 严格区分语句与表达式（Statement-expression distinction）：表达式负责计算出值，而语句负责产生控制流或改变状态。
• 支持可变变量：如定义 var m = 100; 然后随后可以执行重新赋值 m := m - n。
• 控制流循环与跳转关键字：支持经典的 while 循环结构，以及 return、break、continue 等中断控制关键字。

3.1 语法结构设计

• 具体语法（Concrete Syntax）：程序的执行体被定义为代码块 <block>，内部包含一连串的语句 <statement>。语句涵盖了变量声明（var IDENTIFIER = <expr>）、变量更新（IDENTIFIER := <expr>）、条件判断（带有块的主体）、循环（while）及各种跳转控制。表达式 <expr> 则退化为只负责返回单纯的数据值或运算结果。
• 抽象语法（Abstract Syntax）：在编译器内部数据结构中，这被建模为相应的枚举类型。如 Block 定义了代码的序列化；Statement 包含了 VarDecl, VarUpdate, If, While, Break 等变体；Expression 包含了变量寻址、数字常量以及基础的元运算 Prim。

3.2 编译前的良构性检查 (Well-formedness)

在进行代码转换之前，编译器前端必须进行严密的安全校验：

• 作用域与遮蔽（Scope & Shadowing）：要求所有变量必须在声明后才能被使用。语言本身允许变量名的重复遮蔽，但在语义上，被遮蔽的变量实际上代表着一个独立的新可变空间。为避免后续的混淆和错误，检查器必须像往常一样，通过变量重命名将它们转换为全局唯一的变量名。
• 完备的返回检查：如果当前实现的是一个具备返回值的过程（Procedure），编译器必须静态验证其内部每一条可能的执行路径最终都会以一个有效的 return 语句妥善结束。
• 裸跳转防护（Naked break/continue）：必须严格验证 break 和 continue 这两个用于循环中断的关键字，它们在词法上只能出现于一个受保护的、封闭的 while 循环体内部。如果出现在循环外部，必须立刻报错拒绝编译。

3.3 运行时语义 (Semantics)

• 在执行阶段，每一个声明的变量在行为上表现得就像一个对应的 64 位的物理“寄存器”。
• 在求值运算时，系统需要时刻追踪并更新作用域内所有这些变量的当前物理状态。
• 对于 while 循环的语义：系统会首先检查其条件表达式。如果结果为真（true），则执行完整的代码块然后自动回到起点重复；如果为假（false），则跳过代码块，继续执行紧跟在循环后面的语句。
• break：遇到时无条件中止循环，直接跳转（goto）至循环之后的下一条语句。
• continue：遇到时无条件放弃当前轮次剩下的代码，直接跳转回当前所在循环的起始判定点。

4 从命令式代码到 SSA 的五步编译法

由于静态单赋值（SSA）的严苛约束要求程序中的任何变量一旦被绑定就成为不可变常量，编译器需要一系列策略来消解源程序中的大量“变量变异（Mutation）”。

• 第一步：基础表达式与变量声明 这与基础直线代码的编译一致：将层级嵌套的表达式树通过临时变量扁平化为直线型汇编指令逻辑。Imp 中的变量声明 var x = ... 在进入 SSA 时，仅仅意味着在环境里发生了一次不可变的常量变量初始化绑定。
• 第二步：处理变量更新 (Variable Updates) 核心思想是“追踪变量版本”。编译器通过一个内部环境字典，时刻记录当前作用域内每个业务变量关联的最新“SSA 版本标识”。一旦在源程序中遇到对可变变量执行覆盖更新（如 x := y），编译器在 SSA 中会直接将其当作一次对某个全新影子变量的赋值分配。后续所有对 x 的使用，都会自动挂载到这个最新的影子版本上。
• 第三步：条件分支与合并点 (Join Points) 由于 if 和 else 两条分支路线在执行时，可能会对环境中的外部变量进行次数不等、结果不一的重新赋值，当两股控制流汇聚时，必须解决状态冲突。 方案是采用粗略 ϕ 节点插入法（Crude ϕ-node insertion）：这是一种相当暴力但有效的方案，它会将当前作用域内所有已知的存活变量，统统作为外部参数强行添加到合并点块（Join point block）的参数列表中。这在初期会产生惊人数量的冗余参数，但我们在后续会利用 SSA 的最小化处理将其清理干净。
• 第四步：编译 While 循环 循环的语义通过精巧的 SSA 基本块组合来编码。在循环的控制流图（CFG）中，负责判定循环条件的条件检查块（Loop check block）自身具有两个数据流入路径：一是刚从循环外侧进来的初次执行流，二是从循环体末端成功执行完毕后跳回的循环流。因此，条件检查块本身必然是一个关键的合并点（Join point），它必须携带所有的块参数以维系不断更新的循环状态。
• 第五步：处理 Return, Break, Continue
• return 的处理极其直接：编译跟随的表达式，并在指令序列末尾附加上 ret 终止操作即可。
• break 和 continue 的编译强依赖于具体的上下文。当编译器进入一个 while 循环体开始翻译时，会事先生成两个虚拟代码块标识：一个是循环入口点（Entry point），另一个是循环终结的出口点（Exit point）。
• 当遇到 continue 时，将其编译为一个无条件跳转至循环入口块的指令。
• 当遇到 break 时，将其编译为一个无条件跳转至循环出口块的指令。正因如此，由于存在中途跳出的控制流可能性，循环的出口块也随之升级为了一个接收多方汇聚的合并点。

5 极简 SSA 形式与优化的绝对优势

对于命令式语言向 SSA 转换的过程中，一个重要的理论结论诞生了： 尽管使用“粗略 ϕ 节点插入”会产生海量无用的额外参数，但由于命令式代码（如 If 结构和 While 结构）在语法层面上是极其工整、结构良好且自然嵌套的，这就意味着编译器完全不需要执行复杂的“块下沉（Block sinking）”优化。这些嵌套的代码块天然已经乖乖地处在它们的直接支配者（Immediate dominators）内部。 因此，定理：粗略 ϕ 节点插入法 + 简单的参数丢弃策略（Parameter dropping） = 完美的极简 SSA 形式。极简的 SSA 形式最大程度上缩减了参数量，直接避免了在底层生成大量昂贵的 mov 内存拷贝汇编指令。

现代编译器为何痴迷于 SSA 形式？ 在现代工业级编译器基础设施中，前端接收可以任意突变的命令式代码，后端目标则输出操作物理寄存器同样会突变的汇编指令，但处于两者之间至关重要的中段优化层（Middle end）却一律采用变量绝对不可变的函数式 SSA 中间表示。主要原因如下：

1. 彻底解放了公共子表达式消除优化（Common Subexpression Elimination）： 在一般的命令式语境下，如果存在 x = 1; y = x + 1; ...; z = x + 1;，编译器为了把后面的 z 优化为直接取 y 的值，必须耗费大量算力去静态证明在省略号期间变量 x 绝对没有遭受过暗中修改。而在 SSA 下，因为任何变量都不可能被篡改，一旦结构相同就可以闭眼将其直接折叠替换。这种分析在 SSA 下几乎是免费的（Free）。
2. 极大提升了程序数据流分析的效率： SSA 结构允许编译器建立非常清爽的数据结构，直接将每一个“变量的使用场景”与它的“全球唯一生产来源”进行闪电级的直接映射。这使得算法可以直接跳过中间无穷无尽无关紧要的控制流噪音。由于更多的高质量分析信息被直接“显化”在了 SSA 的格式结构中，编译器开发者能更轻松地堆砌更强大的深层优化逻辑，同时编译器程序自身的运行速度也能变得更加高效轻量。

6 扩展外部特性：引入非尾部调用的 Cobra

截至目前，编译器的能力虽足以应付复杂的局内控制流计算，但却完全无法与外围广阔的操作系统世界沟通（无法读取文件、无法向终端屏幕打印结果、无随机数生成等）。为了填补空白，语言的 Cobra 扩展允许通过导入（Import）来无缝桥接并复用底层（例如利用 Rust 的 stub.rs）实现的外部函数模块（Extern functions）。

• 良构性保障：外部函数定义应被视为与本地函数位于相同的全局作用域中。本地的私有定义被允许去遮蔽（Shadow）这些全局外部声明。特别注意，在重命名的名称解析阶段，编译器绝对禁止更改任何外部函数的原始字符名称，因为最终在二进制构建环节，链接器（Linker）极其依赖这些真实的字符名称去找寻具体的二进制实现体。
• 向 SSA 引擎的改动：必须在 SSA 语义的顶层支持注入 extern 声明头。更重要的是，引入了一个具有破坏性的新底层操作原语——非尾部调用（call 操作），需要注意的是，它是一个普通操作，而非阻断控制流图的终止指令。在降级时，若侦测到是对内部函数的尾调用，保持旧做法编译为跳跃分支；若侦测到的是对外部库函数的调用，不论是否处于尾部位置，一律将其编译为真实的、消耗系统调用栈资源的标准 call 指令流程。

7 非尾部函数调用与底层栈架构

当程序发生一次非尾部的真实函数调用时，其与分支跳转的核心区别在于：主调函数需要被调函数完工后精准无误地找到回家的路，以便继续执行自己残存的计算任务（即它的延续，Continuation）。

7.1 x86 栈操作基石

• 自由空间指针：编译器必须指定一块区域作为程序的空闲活动区，在 x86 体系下，rsp（栈指针寄存器）被作为界碑，精准指向此刻可供新数据安全降落的最高栈顶。
• push arg 指令：其硬核语义等同于：首先 sub rsp, 8 将栈顶界碑向下拓展出 8 字节的空降区，随后执行 mov [rsp], arg 把实参数据安置进去。
• pop reg 指令：等同于：先通过 mov reg, [rsp] 抄录下栈顶的数据，然后安全回收空间 add rsp, 8。
• call loc 指令：它是一次融合操作，等同于 jmp 和 push 的无缝结合。它会强制将下一条指令（回家的路）的内存地址暴力压入物理栈（push），然后将指令指针寄存器 rip 飞跃至目标地址 loc。
• ret 返回指令：等效于 pop 加 jmp。它会从栈顶将回家地址拽出来，并且立即跳转飞梭回去。

7.2 System V AMD64 调用约定 (Calling Convention)

当编译器生成的汇编逻辑需要跟外界已有的外部 C 库或 Rust 库安全握手通信时，绝不能随心所欲，必须严格服从当地的标准化协议。在 64 位 Linux 与 macOS 系统生态中，最高法则为 System V AMD64 ABI。该协议详尽刻画了主调方（Caller）和被调方（Callee）之间权力与义务的边界：

• 数据的传递法则：当被调函数开始执行的第一秒，它的前 6 个参数必须已经静静躺在特定的金牌寄存器组合中（按顺序为 rdi, rsi, rdx, rcx, r8, r9）。任何溢出的第 7 到第 N 个参数，则必须由主调方按序铺陈排布在底层栈结构中特定的连续内存坐标内（例如 [rsp + 8], [rsp + 16] 等位置）。

• 强制栈对齐机制：极其关键的是，由于部分高级多媒体硬件指令集（如 SSE）对存取速度有极端要求，调用方在扣下调用扳机的瞬间（即执行 call 指令的前夕），必须确保 rsp 的数值能够被 16 完美整除（rsp % 16 == 0）。而当被调函数由于压入了返回地址而正式降落时，rsp 则会处于 rsp % 16 == 8 的偏移态。

• 返回值的交接：一切执行妥当后，最终返回的数据必须被安置在 rax 寄存器中等待主调方签收。

• 寄存器的所有权与保护：

• 易失性（Volatile / Caller-save）寄存器：这是一片弱肉强食的法外之地。被调方可以随意粉碎并使用这些空间而无需承担任何复原的法律责任。如果主调方还有重要数据存留在这些地带（如 rax, r10, r11，以及所有的传参寄存器），主调方必须在拨出调用电话前，自行掏钱在自己安全的栈区域备份这些财产。

• 非易失性（Non-volatile / Callee-save）寄存器：这是一片受到严格保护的自留地。被调方若想在此处大展身手（如使用 rbx, rbp, r12-r15），必须肩负起沉重的复原包袱，在自己返回谢幕前，一丝不苟地将原先居住在这里的数据毫无差错地还原回去。

• 主调方清理责任 (Caller cleanup)：在 C 语言的遗留下，由于允许类似 printf 这样的不定参数函数存在，被调方根本不知道调用方到底往栈上塞了多少个超编的传参货物。因此在这个调用约定中，清理栈上多余参数空间的擦屁股工作，必须全权由主调方负责。这一设计带来的一个巨大负面后果是：在这个主流约定下，只要面临目标函数所需参数量远大于主调函数的场景，编译器从硬件底层就完全丧失了进行安全尾调用优化的可能性。

编译器构造：外部函数调用与调用约定

1 学习目标

本部分的重点在于掌握以下几个核心概念：

• 探讨如何在编译器中实现真正的（非尾部）函数调用。
• 了解什么是调用约定（Calling Convention）以及我们为什么在编译系统交互中迫切需要它。
• 掌握用于操作和实现函数调用栈的 x86 底层核心指令（例如 push, pop, call, ret）。
• 学习并对比在实际工程中管理栈局部变量（Stack-local variables）的两种主流内存管理策略。
• 深入剖析 AMD System V 64 位调用约定的具体机制与规则细节。
• 区分易失性（Volatile / Caller-save）和非易失性（Non-volatile / Callee-save）寄存器的概念以及它们对编译器代码生成的不同要求。

2 扩展 Snake 语言：引入外部系统函数

在之前的语言演进版本（Adder 和 Boa）中，我们的代码只支持直线型代码、条件分支以及本地函数的尾调用（Tail-called functions）。尽管这已经足以构建出可以内部循环的逻辑块，但由于无法与外界沟通，它依然缺少两项极其关键的能力：

1. 与操作系统进行交互的权限：例如在屏幕打印标准输出、从键盘读取输入、处理文件 I/O、或者调用系统接口生成随机数等。
2. 构建可复用子过程（Sub-procedures）：也就是支持非尾部的普通、嵌套函数调用，执行后还能返回继续之前的操作。

为了获得这些能力，最新的语言扩展版本（Cobra）提供了一种外部导入方案，它允许通过 extern 关键字（如 extern read(), extern print(x)），来引入和调用底层的外部库函数（例如这些函数实际可能实现在配套的 Rust stub.rs 代码文件中）。

3 SSA 中间表示的底层变更

为了支持这些新特性，编译器的核心中间件表示（SSA）需要执行相应的语法升级：

• 编译器必须有能力在生成的 SSA 程序的顶层区域附加上关于 extern 函数的声明。
• 在 SSA 内部必须引入一个新的原语指令符：call。并且值得特别指出的是，普通的 call 动作在此处并不属于终结控制流的终止符（Terminator），而是一个实打实能计算并传出返回值的中间过程语句（例如 $x = call f(x1, ...)）。
• 代码降级策略（Lowering）的变化应对：
• 如果对内部定义的本地函数发起调用，并且这恰好是一次尾调用（Tail call），编译器仍会沿袭先前的成熟策略，将其直接编译为带有传递参数的分支跳转（Branch with arguments），以节省开销。
• 但是，如果试图去调用一个外部的函数库，即使这段调用发生在代码的尾部位置，受到底层调用约定的苛刻限制，我们也只能老老实实地把它编译为一次真正的物理 call 操作，并在外部计算结束后再单独执行一条 return 指令交还结果。

4 底层栈机制与 x86 指令交互

每当程序引发一次非尾部的函数调用时，它在跳转前必须确保自己知道当函数完工后“该沿着原路回到哪里”，这就需要传递延续（Continuation）。而要承载这一回溯过程，系统严重依赖内存堆栈架构和一整套 x86 汇编指令。

4.1 栈指针定位

• 抽象汇编机器使用特殊的寄存器 rsp（栈指针）来标记目前栈数据到达了哪里。需要注意的是，在 x86 内存空间中栈是向着更低地址的方向逐步生长的。这意味着在 rsp 以上（数值上较大的高地址区域）是已经被旧有变量和数据占据过的区域，而在 rsp 以下（低地址区域）才是可以安全开辟新空间的地方。

4.2 管理堆栈的核心指令

• push arg 指令：

• 语义分解：这等效于先做一次 sub rsp, 8（向更低地址探索出全新的 8 个字节空间），紧接着做一次 mov [rsp], arg（将新数据存放在新栈顶位置）。

• pop reg 指令：

• 语义分解：它等同于先做一次 mov reg, [rsp]（把当前栈顶存放的数据安全提取到指定的寄存器中），随后做一次 add rsp, 8（将栈的界线收回以退还空间）。

• call loc 复合指令：

• 执行逻辑：这实际上是 jmp 跳跃与 push 压栈动作的强力结合。当触发 call 的瞬间，硬件会自动抓取到该条指令紧接在后的下一条指令的实际内存地址，并将其强制压入栈（push）作为返回基准点，在这之后才把程序执行指针 rip 迅速导向目标跳转地址 loc。

• ret 退出指令：

• 执行逻辑：这是退场的命令，也是 pop 与 jmp 的结合。它会从当时栈的顶端抽取出最初保留的那串返回地址，并旋即将程序指针重新指回那里，完成一次闭环控制。

5 系统调用约定：System V AMD 64 ABI

在现代软件工程中，想要用我们的自研语言去无缝链接并调用另一门语言（例如 C 或是 Rust）生成的外部二进制库时，就绝不允许乱来，双方的编译器都必须共同遵守一份标准化的通信黑话协议——即调用约定（Calling Convention）。 对于 64 位的 Linux 和 Intel 架构 Mac 系统而言，默认的 C 语言跨平台标准便是 System V AMD 64 ABI 约定。

5.1 进入调用时的苛刻要求 (Calling Protocol)

当一个函数开始接管 CPU 运转的首秒钟内，系统软硬件的排布必须严丝合缝地吻合以下铁律：

1. 优先寄存器传参：该函数的第 1 个至第 6 个实参，必须已经被主调方分毫不差地放置于 rdi, rsi, rdx, rcx, r8, r9 这六大金刚寄存器内。
2. 溢出栈传参：如果有第 7 个及更多数量的参数待处理，主调方必须提前将它们逐次摆放于系统栈中，固定位置从底向顶依次为：[rsp + 1 * 8], [rsp + 2 * 8]……以此类推。
3. 安全寻址点：此时最关键的游标 rsp 刚刚好瞄准着主调方的返回地址。

5.2 全身而退时的清理要求 (Returning Protocol)

当被调方准备结算结果并交还大权前，须执行下列仪式：

1. 所有费心算出的最终结果数据必须老实装在特定的 rax 寄存器里待查。
2. 凡是在栈内地址高于 rsp 的原本划归给主调者的那一带内存，绝对不可以被改乱，须全额原样奉还。
3. 以一个标准的 ret 动作将原 rsp 所携带的地址推出来，作为撤离的目的地。

6 易失性与非易失性寄存器：数据的归属保护

为了在执行过程避免双方误伤数据，调用约定对哪些寄存器能动、哪些不能动给出了分明的权利归属：

• 易失性寄存器（Volatile / Caller-save Registers）：

• 这类寄存器是“三不管地带”。被调用的外部函数可以肆无忌惮地将其覆盖、重写或破坏，事后也不需要负起还原的责任。

• 如果我们的编译程序（作为主调方 Caller）如果在拨打电话之前还有珍贵资产留在这些寄存器中（这包括 rax 运算器, r10, r11 以及那堆用来跑腿传参的通道寄存器），主调方就必须自己提前自费搞定备份（写入自己的安全栈区）以防数据覆灭。这被称为“主调者保存（Caller-save）”。

• 非易失性寄存器（Non-volatile / Callee-save Registers）：

• 这类寄存器属不可侵犯地带。如果被调方在内部计算非常吃紧，想借用一下类似 rbx, rbp, 或者从 r12 到 r15 这些尊贵的寄存器地盘，必须在借用前妥善复印一份留底，并在返回大统领权限之前，一字不差地将它们倒腾回原样。这种行为称作“被调者保存（Callee-save）”。

7 对齐陷阱与主调方清理

7.1 必须严守的栈对齐 (Stack Alignment)

由于许多被调用的现代化系统底层包含了例如 SSE 等针对极速多媒体流优化过的高频硬件指令，这些指令在访问数据时对内存排列结构有强制洁癖： 约定强制规定，主调方在敲下 call 指令扳机前的一瞬间，栈的当前底线值 rsp 必须能被 16 彻底整除（即 rsp % 16 == 0）。由于 call 本身随后强行塞入了一个大小为 8 字节的地址包裹，导致被调方在成功落地后的破门阶段，必然面临 rsp % 16 == 8 的偏移状态。如果编译器计算出了偏差导致这种对齐失效，由于平台容错率差异巨大，生成的系统经常会在云端测试器里诡异崩溃，极难定位追踪。

7.2 参数的清理责任归属 (Caller Cleanup)

按照约定法则，由调用者由于过度传参而在栈空间上垫出的那些占位垃圾，在返回之后仍然残留在堆栈内。此时处理这些堆栈的善后清理（调整指针扔掉废弃参数），必须完全交由外层的主调方（Caller）处理。

• 历史成因：这是 C 语言生态遗留下的惯例。因为存在诸如 printf 这样的不定数目可变长参数函数，内部执行者常常根本无从得知门外到底挤进来了多少参数箱子，从而无从去安全回收和清理。
• 严重的架构限制后果：这一机制引发了一个灾难。因为即使当面临需要优化内存的场景，但如果涉及一个传参爆多、严重依赖内存传递的函数链条，既然必须要调用方执行结束后清理现场，这就等于在硬件底层级截断了执行高规格尾调用优化的任何理论可能。

8 栈帧的区域管理

处于激活状态并在堆栈内存中维持自身局部变量的一段专属区域被称为“栈帧（Stack Frame）”。为了确保新的调用能顺利在其头顶开拓下一片干净的驻扎区而不至于践踏到底下的本地变量，程序必须精准测量目前活动区域的边界。通常采用两大路线解决问题：

1. 双指针流派（如部分传统 C 编译器风格）：指派 rbp 长期盯梢所在栈帧的下基石位置，指派 rsp 负责开疆扩土充当最上沿尖端。这允许代码中随时插播诸如 alloca 这种临时索要大量且不固定空间的动态变位分配动作，缺点则是活生生占用、浪费了一个稀缺的高速缓存寄存器 rbp。
2. 极简指针流派（现代编译器常用手段）：抛弃 rbp，从头至尾全权由 rsp 这个独狼作为总基准锚点。这要求编译器能在进入生成的汇编世界之前，就提前在内部静态算明所有本地变量合计有多大，从而让 rsp 精确避开特定区间。这既解放了富余的硬件资源，也契合了本课程中所探讨的不涉及动态增设空间的纯静态堆内存排布体系。

非尾部函数调用、函数定义与 Lambda 提升 (Non-tail Function Calls and Definitions, Lambda Lifting)

1 学习目标

本节核心内容围绕底层函数调用的实现以及处理嵌套函数作用域的编译技术，主要目标包括：

• 掌握在 x86 架构中如何实现 System V AMD64 函数调用约定。
• 了解在 x86 架构中如何编译和实现函数定义。
• 深入探讨并解决局部嵌套函数定义中的 变量捕获（Variable Capture） 问题。

2 x86 抽象机器与栈操作 (The Stack)

在执行非尾部函数调用时，程序必须依赖内存中的“栈”来保存状态与返回地址。

• 栈指针寄存器 (rsp)：到目前为止，我们一直将 rsp 视作栈帧的基准指针。在 x86 架构中，它作为一个真正的“栈指针”，时刻指向栈的顶部（在内存地址空间中，栈是向下生长的，即向更低的地址空间延伸）。

• 入栈与出栈指令：

• push / pop：这两个指令分别会将 rsp 的值自动减少或增加 8 个字节，并同时在 rsp 所指向的内存地址处存储或加载一个值。

• 调用与返回指令：

• call / ret：这是一对用于函数控制流转的指令。call 会将当前的指令指针（Instruction Pointer，即返回地址）压入栈中并发生跳转；而 ret 则会从栈顶弹出该返回地址，并更新指令指针以返回到调用点。

3 System V AMD64 调用约定 (Calling Convention)

为了让我们的编译器生成的代码能够与外部生态（如 C 或 Rust 库）安全交互，必须严格遵循平台标准——System V AMD64 调用约定。

3.1 进入函数时的机器状态 (Calling Protocol)

当一个被调用的函数开始执行时，系统状态必须严格满足以下五项条件：

1. 寄存器传参：函数的前 6 个参数必须依次存放在特定的硬件寄存器中，顺序为：rdi, rsi, rdx, rcx, r8, r9。
2. 栈传参：如果函数的参数超过 6 个，从第 7 个参数到第 N 个参数必须由调用者（Caller）按顺序放入栈中。其内存位置依次对应为 [rsp + 1*8], [rsp + 2*8], ... 直至 [rsp + (N-6)*8]。
3. 返回地址：此时的 rsp 必须精确指向主调函数压入的返回地址。
4. 栈对齐 (Stack Alignment)：系统强制要求在发生 call 指令跳转后，栈指针必须满足 rsp % 16 == 8 的对齐状态（因为在 call 发生前 rsp 必须是 16 字节对齐的，压入 8 字节的返回地址后，余数便成了 8）。

3.2 寄存器的易失性分类

• 易失性寄存器（Volatile / Caller-save）：这类寄存器的所有权归属于被调用者（Callee）。被调用者可以自由修改它们而无需恢复。如果主调者认为其中的数据有价值，必须在拨出调用之前自己把它们备份到栈上。
• 非易失性寄存器（Non-volatile / Callee-save）：这类寄存器受严格保护。如果被调用者在内部计算中需要借用它们，必须在函数返回之前将其完全恢复为调用刚发生时的原始状态。

3.3 退出函数时的清理规则 (Returning Protocol)

当被调用的函数执行完毕准备返回时：

1. 它必须将计算得到的最终返回值存放在 rax 寄存器中。
2. 栈内原本属于主调者的空间（即初始 rsp 地址之上的高地址区域）严禁被篡改，必须原样交还。
3. 执行 ret 指令弹出返回地址并完成跳转控制。
4. 主调方清理 (Caller Cleanup)：对于栈上压入的第 7 到第 N 个超额参数，被调用者概不负责，必须由主调函数在重新获得控制权后，自行调整 rsp 来清理这些废弃的参数占用。

4 扩展 Cobra 语言：支持内部函数定义

在这一阶段，编译器对名为 "Cobra" 的语言变体进行了扩展，允许进行局部的嵌套函数定义。

• 与 C 语言不同（C 语言仅允许在全局层级声明函数），Cobra 语言允许在程序的任何代码块或作用域内声明新函数，这在表现行为上类似于 Python 或 Rust。
• 在这种语法中，所有的内部行为相互嵌套，而函数定义本身通常也就成了一个表达式。

5 变量捕获的困境 (Variable Capture)

当语言支持嵌套函数定义时，立刻会面临一个严峻的语义与实现挑战——变量捕获。

• 现象描述：一个定义在内部的局部函数，在其函数体内引用了外部主调函数作用域中定义的变量（非全局变量，且不在自身的参数列表中）。
• 栈寻址的崩溃：如果我们只是一如往常地把内部函数当成普通代码块来编译，一旦发生调用，它会在栈上分配自己全新的栈帧。而它所捕获的变量，实际上物理存储在它的父函数（或更外层函数）的栈帧中。
• 试图通过计算与 rsp 的固定偏移量去读取这些外部变量是完全行不通的，因为在程序运行时，随着条件分支、循环或不同的调用深度，内部函数的栈顶 rsp 距离那个外部变量的物理内存距离是动态且不可预测的。

6 解决方案：Lambda 提升 (Lambda Lifting)

为了不陷入极其复杂的动态栈帧链寻址泥潭，编译器采用了一种非常优雅的转换算法，称为 Lambda 提升 (Lambda Lifting)。 它通过直接将嵌套函数的结构进行扁平化，从根本上消灭了“外部局部变量”这一概念。

6.1 核心思想

Lambda 提升的过程可以看作是将局部函数转化为全局函数的过程：

1. 提升 (Lifting)：将所有嵌套定义在内部的子函数统统“拔出”，转移到程序的最顶层（全局级别）。
2. 参数化捕获变量 (Parameterizing Captured Variables)：为了弥补提升后失去的外部作用域，编译器会将该函数原本捕获到的所有外部变量，强行追加为这个新全局函数的显式额外参数。
3. 改写调用端：在源代码中任何调用该函数、或发生控制流分支指向该函数的地方，编译器都会自动填补并传入这些被捕获的变量作为实参。

6.2 在 SSA 降级中实现

Lambda 提升并不一定要作为一次独立的 AST（抽象语法树）对 AST 的转换遍（Pass）。现代编译器常常将其直接无缝融合在从 AST 降级到 SSA（静态单赋值中间表示）的过程中。

• 在生成 SSA 代码时，如果发现正在调用一个带有捕获状态的函数，编译器会直接在底层生成一个新的顶级函数块（如 pow_call），并将所需变量打包附在它的参数签名中。

6.3 算法的两个关键步骤

要实现一个健壮的 Lambda 提升算法，编译器引擎必须解答两个核心问题：

1. 哪些函数需要被提升？
   • 答案是：所有声明在局部作用域中的嵌套函数都必须被提升，以确保最终底层代码只存在平级的基本块和全局函数调用。
2. 对于每一个被提升的函数，到底需要添加哪些额外的参数？
   • 答案是：需要对函数体进行静态的作用域分析，找出所有的自由变量（Free Variables）。即那些在函数体内参与了运算，但既不是在函数体内部定义的局部变量，也不是函数原本签名中的参数的变量。这些自由变量的集合，就是它需要补充进新签名的额外参数列表。

编译器构造：栈对齐、Lambda 提升与动态类型基础

1 学习目标

• 修正并补充关于栈对齐（Stack Alignment）的技术细节。
• 回顾 Lambda 提升（Lambda Lifting）的核心思想。
• 掌握 Lambda 提升的具体实现机制：确定哪些函数需要被提升，以及哪些变量需要被捕获。
• 了解动态类型（Dynamic Typing）的语义，及其在编译器中的实现策略探讨。

2 栈对齐（Stack Alignment）细节修正

在 x86 架构的 SysV AMD64 调用约定中，保持正确的栈对齐是防止程序崩溃的关键因素。

2.1 核心对齐规则

• 当一个函数刚被调用（进入函数体开始执行）时，系统默认栈指针处于 rsp % 16 == 8 的状态。
• 为了向下一个函数发起安全的调用，在执行 call 指令之前，必须绝对保证 rsp % 16 == 0（因为 call 指令会自动压入 8 字节的返回地址，使状态变回 8）。
• 编译器在编写当前函数的代码时，可以安全地假设当前函数是被正确调用的（即初始时刻 rsp % 16 == 8），因此接下来的任务就是在构建自身的栈帧时，抵消掉后续调用所需的对齐偏差。

2.2 内存布局与填充（Padding）计算

在为函数创建新的栈帧时，必须清点所有将会保存在栈上的内容总量：

• $L$ 代表栈上局部变量（Locals）的数量。
• $A$ 代表必须通过栈传递的参数（Stack-passed arguments）的数量（即超出了 6 个寄存器限制的额外参数）。
• 当 $L + A$ 是奇数时：如果我们将多出的外部参数紧挨着局部变量全部压入栈，由于总消耗空间为奇数乘 8，加上初始的 8 字节偏差，栈将自然达成 16 字节对齐。
• 当 $L + A$ 是偶数时：为了强制对齐，编译器必须在局部变量和栈传递参数之间人为加入一块 8 字节大小的 “填充间隙（Padding gap）”。

3 扩展语言：从 Boa 到 Cobra

随着语言不断演进，编译器架构也在发生变化：

• Adder 版本仅支持简单的直线型代码（类似于算术电路）。
• Boa 版本引入了条件分支和尾调用（Tail-called functions），提供了支持任意“局部”控制流的能力（相当于有限状态自动机）。
• Cobra 旨在补足 Boa 在实现完整函数体系时的缺陷：

1. 它需要能与操作系统发生交互（比如标准输入输出、文件 I/O 等），这要求引入外部函数（Extern functions）。
2. 它需要支持可复用的子过程，即必须完整支持非尾部调用（Non-tail calls）。

3.1 引入非尾部调用及 SSA 架构变化

为了在 Cobra 中同时享受尾调用的高效率和外部函数调用的通用性，编译器在 SSA（静态单赋值）表示上做了重要修改：

• 设计目标：对于普通的尾调用，仍然延续之前的高效策略将其编译为直接分支；对于非尾部调用和外部函数调用，则严格按照 SysV AMD64 调用约定执行，以此兼顾性能和跨语言通信（例如调用 Rust 写的底层函数）。

• 多顶层函数块架构：先前的版本只有一个主入口块，如今 SSA 结构被泛化，支持拥有多个顶层函数块（Top-level function blocks）。

• 函数（Functions）与基本块（Basic Blocks）的区别：

• 函数（Functions）：仅仅作为系统级 call 操作的目标，严格受 SysV 约定约束，只能处于代码的最顶层，其内部作用域唯一包含的外部变量只有它的输入参数。

• 基本块（Blocks）：作为普通 branch （跳转）的目标，参数在栈内偏移，它可以被嵌套，且可以自由引用外部作用域里的变量。

• 底层代码生成策略：在汇编生成时，SSA 函数块仅仅作为一个薄薄的“包装层”：它负责接收 SysV 约定传来放在特定寄存器里的参数，用 mov 指令将其平移到基本块所预期的栈内位置，然后再 jmp 到真正的执行基本块上。

4 变量捕获（Variable Capture）与 Lambda 提升

一旦语言支持在局部作用域定义嵌套函数，编译器就会面临一个经典的挑战：变量捕获（Variable Capture）。如果一个内部函数使用了其父函数作用域内定义的变量，并且该内部函数发生了非尾部的递归调用，此时该变量究竟存放在调用栈的哪一层将变得动态且无法预料。

4.1 两种主流解决思路

1. 静态链（Static Links）：在每次调用嵌套函数时，暗中传递一个指针，该指针指向定义这个函数的外部闭包所在的栈帧。这种方法传参极快，但每次要用到捕获变量时，都需要顺着指针在内存里爬行寻找，访问极其缓慢。
2. Lambda 提升（Lambda Lifting）：这是一种简单粗暴但极为有效的方法——找出所有被捕获的外部变量，并将它们强制作为额外的参数添加到被捕获函数的签名中。这种方法虽然传递时的拷贝开销较大，但使得所有的变量访问完全变回了最快的本地局部操作，并且可以轻松推广到头等函数支持。本编译器采用此方案。

4.2 Lambda 提升的具体实现（从 AST 到 SSA）

Lambda 提升并非一定要作为一次独立的 AST 重构遍来进行，它可以无缝融合在将 AST 降级为 SSA 的过程中。编译器一旦在转换过程中发现某个内部函数被调用，它就会将其提取到代码库最顶层，并在其参数列表里追加所有必需的捕获变量。

要实现 Lambda 提升，需考虑兼顾正确性（正确涵盖所有需要提升的元素）与效率（不浪费多余参数），这要求解决两个核心算法问题：

问题一：到底哪些函数必须被提升？

• 任何在代码中被明确非尾部调用（Non-tail called）的函数。
• 该函数对应的用于内部跳转的尾调用代码块版本。
• 最关键的是：任何在调用图（Call Graph）中能够被已经提升的函数尾调用的其他函数，即使这些函数本身从未在外部发生过非尾部调用，它们也必须跟着一起被提升。
• 算法实现：可以通过建立一张函数调用图，将非尾部调用的函数置入工作列表（Worklist），不断弹出并追踪其后继节点，直到找出所有受牵连的函数集合。

问题二：对每个被提升的函数，到底要添加哪些外部变量作为参数？

• 核心答案是：所有该函数在运行时栈帧中必须依赖的非局部变量。
• 正确但低效的做法：直接把在该函数定义位置当前作用域内所有可见的变量统统加进去。这会导致在底层的栈上传递大量函数体内根本碰都不碰的垃圾参数，严重浪费内存空间。
• 优化策略：为了保证性能，较好的做法是先无脑捕获所有可用变量以保证正确性，然后在 SSA 中间表示阶段运行活跃性分析（Liveness analysis），最后通过之前介绍过的参数丢弃（Parameter dropping）技术，将那些死变量统统修剪掉。

5 Cobra 编译流水线变更总结

• 前端（Frontend）：取消之前针对非尾部调用报错的限制；确保外部函数在作用域中可见，并防止在命名处理时对外部函数名进行乱码修饰（Name mangling）；在前端执行调用图分析，精准计算哪些函数和变量需要参与 Lambda 提升。
• 中端（Middle-end）：遇到外部库尾调用时，强行降级为普通函数调用处理；对于内部函数调用，如果是尾调用则走跳转逻辑，如果是普通调用则生成 SSA 的 call 指令；最重要的，在这个阶段将分析好的 Lambda 提升逻辑注入，修改这些调用的参数列表。
• 后端（Backend）：所有的 call 指令都被翻译成严格遵守 System V AMD64 标准的 x86 汇编调用代码，其余绝大部分难题都在 Lambda 提升阶段被提前消化完毕。

6 动态类型系统（Dynamic Typing）初探

在引入了函数和控制流后，下一个重大扩展（Snake v4：Diamondback）将致力于打破底层数据类型的桎梏。目前 Cobra 中的限制极为明显：它本质上只有一种称为 64 位整数的内存类型（布尔值只不过是恰好只有 0 和 1 的特权整数），且除了调用栈之外，缺乏使用大块内存（如变长数组）的手段。

6.1 现有语义的缺陷

在当前的 Boa/Cobra 中，由于底层都是整数，-1 && 3 会被静默执行，true + 5 会被当成算术运算，甚至对于同一个内存值，根本无法实现诸如 isInt(true) 或 isBool(1) 这种运行时检查。我们需要彻底改变语言的语义，让类型乱用变为明确的错误。

6.2 静态类型（Static）与动态类型（Dynamic）之争

要解决类型区分，编译器存在两条技术路线：

1. 静态类型（如 C/C++, Rust, Java）：通过在编译前端（Compile time）静态推导所有的变量类型，提早拒绝非法的类型混用。好处是编译器能根据可靠的类型生成最极简、最高效的底层代码。
2. 动态类型（如 Python, JavaScript）：允许同一变量容纳不同类型的数据，并在运行时（Runtime）即刻检查。这就要求编译器在底层数据中植入类型标签（Type tags），在每次执行运算操作（如加法）前，必须先生成一段额外的汇编逻辑去剥离标签、验证类型，再放行计算。

接下来的编译器迭代中，将通过在 64 位寄存器数据的某些位（如最低有效位 Least significant bit）嵌入特殊的标记模式，从而实现一套能够区分整数、布尔值及未来复杂类型的动态类型识别机制。

动态类型与堆分配

1 学习目标

本阶段编译器的核心学习目标如下：

• 探索动态类型值（Dynamically Typed Values）的设计空间及其表示方法。
• 掌握如何在底层汇编代码和静态单赋值（SSA）中间表示中实现动态类型检查。
• 理解并对比内存的栈分配（Stack Allocation）与堆分配（Heap Allocation）。
• 了解可变数组（Mutable Arrays）的语法与语义设计。
• 学习如何实现需要在堆上分配内存的大型复杂数据类型。

2 语言演进与引入动态类型的动机

在之前的版本（Boa 和 Cobra）中，布尔值和整数在底层并没有被区分为完全独立的数据类型。所有的整数都可以在逻辑运算中被使用，而所有的布尔值也可以参与算术运算。这导致了一些本应是错误的表达式（如 -1 && 3、true + 5 等）在旧版本中具有合法的计算语义。

新版本（Diamondback）引入了以下重大改变：

1. 动态类型检查：引入新的数据类型，并改变语言语义，使上述类型混用的操作在运行时抛出错误。同时，编译器需要支持 isInt 和 isBool 这样的内置操作，以便在运行时区分传入的变量到底是整数还是布尔值。
2. 堆分配的可变数组：引入可以动态确定大小的数组类型。它突破了单纯依赖栈内存的限制，允许程序使用无限量的内存，从而赋予了语言图灵完备（Turing complete）的计算能力。

3 动态类型值的数据表示方案

在 Diamondback 语言中，一个运行时的值不仅要包含底层的数据，还必须携带一个类型标签（Type tag）以匹配对应的值。在底层编译器中，有三种主要的设计策略来表示这些携带标签的值：

• 方案一：将值存储为 8 字节，使用额外的数据存储标签

• 将一个 Snake 值设计为 9 字节：其中第一个字节用于存储类型标签（例如 0x00 表示整数，0x01 表示布尔值），剩下的 64 位（8字节）存储底层的整数、布尔值或指针。

• 缺点：为了保证内存的字节对齐，这会产生大量的内存开销（1字节外加占位填充）；此外，底层硬件架构和调用约定都是高度面向 8 字节（64位）优化的，要在各处全面支持这种非标准大小的数据是非常繁琐的。

• 方案二：所有的值都作为指针（装箱数据 Boxed Data）

• 让所有的值都变成一个固定的 64 位指针，指向分配在堆上的一个对象，在堆上的内存空间中再分别存储标签和不限大小的数据。

• 缺点：虽然能在编译时保持统一的 64 位处理逻辑，但给每一个简单的运算值都带来了普遍的额外内存开销和间接访问成本。

• 方案三：标签指针折中方案（课程采用的方法）

• 强制所有值都必须装入单个 64 位空间内，通过利用该值的最低有效位（Least significant bits）来作为类型区分标签。

3.1 基于位标签（Bit-Tagging）的具体编码规则

• 整数（Integers）：将其表示为一个 63 位的有符号整数，并将最低位固定设置为 0 以表明这是一个整数类型。在底层的表现上，等于将原本的 63 位整数 $n$ 编码为 64 位整数 $2 \times n$。
• 布尔值（Booleans）：为了区别于整数，最低位必须设置为 1。具体而言，利用最低两位 0b01 来明确标识布尔值。剩余的高 62 位则按照之前的方式，利用 1 和 0 来分别编码 true 和 false（在这个格式中会有大量的位模式变成无效的“垃圾”数据）。
• 装箱数据/引用类型（Boxed Data）：诸如数组这样的大型结构，其值是在堆上分配的，其标签的第一位也是 1，但为了与布尔值区分，其最低两位会被设置为 0b11。剩下的高 62 位构成指向堆数据的物理指针。采用这种做法的安全前提是：所有在堆上分配的内存基址都保持了至少 4 字节的对齐（即地址原本的最后两位必然是 00），因此覆写最后两位不会破坏原始地址的还原。

4 动态类型操作的编译实现阶段

在动态类型系统中，实现诸如加减乘除或逻辑运算的底层原语均需要包含两个步骤：首先检查输入的标签是否正确，其次对去标签后的纯数据执行实际操作。开发者面临着将这一机制安置在哪个编译阶段的选择：

• 选项一：完全在代码生成（x86汇编）阶段实现

• 这意味着在 SSA 阶段的值依然是动态类型的值。

• 缺点：这违背了 SSA 应作为汇编代码的轻量级包装的理念，导致代码生成逻辑异常复杂，并且由于复杂的位操作对基于 SSA 优化的中端系统不可见，编译器将错失大量的优化机会。

• 选项二：完全在向下转换为 SSA 的阶段实现

• 所有的类型检查逻辑都被显式转换为 SSA 里的分支跳转与位运算掩码指令。

• 缺点：虽然使底层的机器码生成变得十分简单，但由于检查逻辑完全散落在基础运算指令中，这使得编译器很难清理和优化掉那些不必要的标签检查步骤。

• 选项三：多阶段协同实现（采用策略）

• 在降级至 SSA 时，我们向中间表示中插入一种显式的内置类型断言（例如 assertInt(x) 或 assertBool(y)），但不立即处理具体的底层报错代码；同时使用按位掩码与位移手动执行计算逻辑。

• 具体的类型校验以及失败拦截则交由 x86 代码生成阶段去实现。

• 巨大的优化优势：通过在 SSA 中预留断言节点，编译器可以通过简单的静态分析推断出某些变量一定拥有合法的整型标签（例如刚经过运算产生的值）；分析一旦确认安全，便可一并移除这些多余的 assertInt 节点，大幅削减运行开销。

5 数组特性与堆分配内存模型

在拥有了动态类型的处理能力后，Diamondback 引入了强大的数组语法和功能：

• 语言允许静态分配 [x, x+1]、根据动态传入值分配大小 newArray(x)。
• 支持基础的索引读取 a[0] 和原地可变更新 a[1] := a[1] + 1，也可以通过 length(a) 随时查询数组长度。
• 由于数组可以被动态变异（Mutable updates），程序现在可以构建出诸如循环链表之类的循环数据结构。
• 在执行时，数组系统会对读写访问进行自动的运行时边界检查（Bounds checking），若发生越界将产生错误拦截。

5.1 放弃栈分配的必然性

由于数组的大小不固定，它们无法像局部标量一样简单地分配在函数的执行栈（Stack）上。

• 如果动态数据分配在一个函数的本地栈帧内部，并在随后作为指针返回被外层使用，那么当这个函数结束执行后，它的栈内存区域就失效了，紧接着发起的任意其他函数调用都会立即将其数据无情覆盖。
• 为了解决这个问题，对于其生命周期不直接绑定于特定局部栈帧的动态长效数据，必须将它们置于另一个单独的内存空间中，即堆（Heap）。

5.2 简化的堆模型与运行时支持

• 不同于栈指针在内存里总是向下增长，堆一般是从较低地址开始向高地址方向增长。
• 在这套编译系统中，堆模型极度简化：堆仅是一块独立于栈分配出的大型内存区域，依靠维护一个全局的“堆指针”追踪下一段未被使用的空闲边界。
• 为降低复杂性，系统暂时假设不会去回收和释放已用的内存（这种不回收策略在一些特殊高敏系统如导弹中也会被采用）。
• 由于内存的预分配与系统故障抛出需要与操作系统级别交互，汇编程序必须不断与基于 Rust 编写的运行时系统（Runtime System）对接。生成的汇编代码将通过调用运行时预先写好的原生函数来完成系统级操作。

6 数组内部对象与指针解析

当我们实际去实现可变数组时，需要处理对象在内存中的实际存放问题以及 Snake 值自身的指针表示问题：

1. 数组作为堆对象（Arrays as Objects）：在真实分配出的大块堆内存里，不仅需要把实际的数值以连续的形式排布存放（以此来支持底层汇编基于内存偏移量的高速 get 与 set 寻址），还必须单独拿出一块前置区域用于永久存储此数组当前的长度（length）。这个长度标识是之后应对查询和防止越界攻击的底层依据。
2. 数组作为被引用的值（Arrays as Values）：存储在运行栈上或是参与传递的 Snake 变量并非整个数组本体，而只是一枚指向内存空间的 64 位“标签指针”。就像前文所述，在提取该变量的值以寻址堆内容前，需要利用位掩码手段剥离其末尾的 0b11 伪装标签以还原真实的纯净内存地址。

堆分配与可变数组的实现 (Heap Allocation & Mutable Arrays)

1 学习目标

本部分设定了以下核心学习目标：

• 深刻理解 栈分配（Stack Allocation） 与 堆分配（Heap Allocation） 的核心差异。
• 掌握 可变数组（Mutable Arrays） 在编程语言中的具体语法（Syntax）与语义（Semantics）。
• 学习并实现那些体积庞大、需要在堆上动态分配内存的复杂数据类型。

2 语言演进：Diamondback 阶段

在编译器的演进历程中，语言的功能被不断扩展：

• Adder：仅支持无分支的直线型代码（类似于算术电路）。
• Boa：引入了局部控制流（支持条件分支，能力等同于有限状态自动机）。
• Cobra：引入了过程调用（Procedures）和外部函数接口（Extern），支持了非尾调用（能力等同于下推自动机）。
• Snake v4 (Diamondback)：

1. 引入了新的数据类型，并利用动态类型（Dynamic Typing）机制在运行时进行类型区分。
2. 引入了堆分配的、大小可变的数组（Heap-allocated variable-sized arrays）。这打破了内存使用的限制，使得语言的计算能力正式跃升为图灵完备（Turing complete）。

3 数组的语法与语义

在 Diamondback 中，程序获得了操作大规模数据的能力，主要包括以下数组特性：

3.1 数组创建

• 静态已知大小分配：let a = [x, x+1, x+2]。在代码字面上明确列出所有初始元素，分配一个固定大小的数组。
• 动态决定大小分配：newArray(x)。在运行时根据变量 x 的值决定数组的长度，分配后的数组元素默认初始化为 0。

3.2 数组操作与可变性

• 索引访问：a[0]。
• 原地更新（可变性）：a[1] := a[1] + 1。由于数组是可变的（Mutable），我们可以对已分配的数组内部元素进行修改。
• 获取长度：length(a)。
• 循环数据结构：因为数组是可变的，并且可以存储不同类型的值（包括对其他数组的引用），程序现在可以构建出复杂的循环数据结构（如循环链表）。

4 栈分配的局限性与堆分配的必然性

为什么数组不能像普通的局部变量一样分配在函数的栈帧（Stack Frame）中？

• 栈的生命周期限制：栈内存的作用域严格绑定于当前正在执行的函数。如果在函数内部的栈上分配了一个数组，并将该数组的指针作为结果返回，那么当该函数执行完毕（ret）后，这块栈内存就被视为“自由空间”。
• 数据覆写灾难：一旦发生后续的其他函数调用，新的栈帧会立刻覆盖掉这片旧内存，导致返回的数组指针指向了一堆被破坏的乱码数据。
• 引入堆（Heap）：为了存储那些生命周期需要超越创建它们的函数、且大小在运行时才能确定的数据，我们必须引入堆分配。堆内存是独立于调用栈的全局内存池，分配在堆上的数据会一直存活，直到被显式释放（或被垃圾回收器回收）。

5 数组的内存布局与对象表示

在底层实现数组时，需要解决两个不同层面的表示问题：对象在堆上的物理存储结构，以及变量如何持有这个对象的引用。

5.1 堆上的对象结构 (Arrays as Objects)

为了让数组能够正常工作，堆内存中不仅要存储数组的元素，还需要存储元数据：

1. 连续存储：元素必须在内存中连续排列，以便底层汇编能通过基础地址加偏移量的方式实现 get 和 set 的极速寻址。
2. 长度前缀（Length Prefix）：必须在数组数据序列的最开头（偏移量为 0 的位置）单独开辟 8 个字节，用于永久存储该数组的长度。这对于实现 length 操作以及在每次访问时进行 越界检查（Bounds checking） 至关重要。

• 结构示例：一个长度为 n 的数组，总共需要占用 8 * (n + 1) 个字节。

5.2 数组的标签指针表示 (Arrays as Values)

我们在栈上的局部变量（例如 let a = ... 中的 a）存储的并不是数组本身，而是一个指向堆中该数组起始位置的标签指针（Tagged Pointer）。

• 标签位：为了在动态类型系统中区分整数、布尔值和引用对象，我们将指针的最低两位（2 least significant bits）强制覆写为 0b11。
• 安全性保证：为什么覆写指针末尾是安全的？因为我们保证了堆内存的分配始终是 8字节对齐（8-byte aligned） 的。一个 8 字节对齐的物理内存地址，其二进制表示的最低三位永远是 000。因此，通过位运算 ptr | 0b11 加上标签，并在真正解引用前通过 ptr ^ 0b11 或 ptr - 3 剥离标签，就能完美还原真实的物理地址。

6 堆分配的运行时环境设计 (Runtime System)

由于堆内存是从操作系统中索要的大块空间，编译出的汇编程序需要与运行时系统（Runtime System，例如由 Rust 编写的宿主程序）进行交互。

6.1 内存的预分配与传递

1. Rust 运行时初始化：在真正的 Snake 代码运行前，Rust 环境的 main 函数会使用 malloc 预先向操作系统申请一块巨大且连续的内存区域作为堆（Heap）。
2. 传递给 Snake：当 Rust 准备调用 Snake 的汇编入口点（snake_main）时，它会将这块巨大堆内存的基地址作为第一个参数传递过去。
3. SysV AMD64 约定：根据调用约定，这第一个参数会被放置在 rdi 寄存器中传入。

6.2 堆分配指针寄存器 r15

为了在 Snake 代码中随时随地进行快速的高效分配，我们需要一个专用的寄存器来充当堆指针（Heap Pointer），时刻指向堆中下一个未被使用的空闲字节。

• 初始化：在 snake_main 启动的最开始，执行 mov r15, rdi，将全局堆基址安全地保存在 r15 寄存器中。
• 为何选择 r15？：因为 r15 在 SysV AMD64 约定中是一个非易失性寄存器（Callee-save register）。这意味着在整个 Snake 程序的运行周期内，即使中间调用了各种复杂的子函数，r15 的值也不会被意外篡改破坏。

6.3 碰撞指针分配逻辑 (Bump Allocation)

当前编译器采用了一种极度简化的、不含垃圾回收的线性分配法：

• 当需要分配一个长度为 n 的数组时：

1. 将数组长度 n 存入当前 r15 所指的地址：mov [r15], n。
2. 依次将计算好的元素存入 [r15 + 8], [r15 + 16] 等位置。
3. 记录当前的 r15 作为新数组的基址。
4. 将 r15 猛推向前方（即加上 8 * (n + 1) 字节），标志这块内存已被占用。
5. 将记录下的旧基址打上 0b11 标签并返回。

7 数组操作降级至 SSA (Translation to SSA)

在编译的中端阶段，高级语言的数组操作被显式降级为 SSA 中间表示，其中包括了类型检查和物理偏移量计算。

7.1 数组创建 ([e0, e1, ..., e(n-1)])

1. 依次编译所有的子表达式 e0 到 e(n-1)，结果存入临时变量 x0 到 x(n-1)。
2. 调用内部逻辑 arr = allocateArray(n)（这在汇编层对应上述的 r15 碰撞分配）。
3. 使用内部写操作 store(arr, 1, x0) 到 store(arr, n, x(n-1)) 将初始值填入正确偏移量。
4. 打上标签：res = arr | 0b11。
5. 将 res 传递给延续块（Continuation）。

7.2 数组访问 (e1[e2])

1. 编译数组基址表达式 e1 到 x1，编译索引表达式 e2 到 x2。
2. 动态类型检查：插入断言 assertArray(x1) 和 assertInt(x2)。
3. 剥离标签：arr = x1 ^ 0b11，还原出真实的堆指针。
4. 加载长度并检查越界：

• len = load(arr, 0)（读取第 0 个槽位的长度值）。
• ix = x2 >> 1（注意：因为整数 x2 在底层编码时最低位是 0 也就是乘以了 2，所以要获取真实的索引数值，必须算术右移 1 位）。
• assertInBounds(len, ix)（如果越界将引发运行时崩溃）。

5. 计算实际物理槽位并加载数据：

• ix2 = ix + 1（由于第 0 个槽位被长度信息占用，真实的数据存储槽位需要向后偏移 1 个单位）。
• res = load(arr, ix2)。

6. 将结果 res 传递给延续逻辑。

7.3 数组更新 (e1[e2] := e3)

1. 分别编译 e1, e2, e3 到 x1, x2, x3。
2. 执行与数组访问完全相同的断言、去标签、解整数编码（>> 1）以及越界检查流程。
3. 计算出真实的偏移量 ix2 = ix + 1。
4. 执行更新指令：store(arr, ix2, x3)。
5. 按照语义，更新语句没有具体的返回值或返回某个假值，随后继续执行延续代码。