编译器概述
基本功能
本编译器基本具备如下功能：
- 将 SysY 程序编译为 Koopa IR；
- 由 Koopa IR 生成 RISC-V 汇编；
- 对后端生成的 RISC-V 汇编进行优化。
主要特点
我开发的编译器具备以下主要特性：
- 高度用户友好：当检测到语法或语义错误时，能够生成清晰、易于理解且便于调试的错误报告。
- 优化目标代码生成：能够产出经过优化的目标代码。
- 高效性能与内存管理：编译器实现旨在尽量上减少内存分配，从而实现高性能运行。
编译器设计
主要模块组成
编译器由 3 个主要模块组成：
- 语法分析器
- 前端（语义检查、IR生成）
- 后端（代码分析、汇编生成、汇编优化）
主要数据结构
编译器设计的核心理念是通过行为的组合来实现复杂逻辑，所以架构的焦点不在于数据结构，而在于定义在其上的方法。每个模块都围绕一个数据结构设计，并在其上定义方法以实现其特定逻辑。借助 Rust 的方法扩展机制，可以在不同的模块中实现同一结构的方法，以此来划分不同层次的逻辑，进而实现优秀的模块化。
前端
编译器前端以抽象语法树为核心。在语法分析阶段，根据 SDD 翻译方案来构造 AST，而在 IR 生成阶段，则定义为 AST 节点上的扩展方法。
抽象语法树的组织模式和 BNF 定义基本一致，每个非终结符对应一个数据结构定义。对于单一生成式的语法结构，采用 struct 储存，多生成式则使用 enum 储存，每条生成式对应到 enum 的一个变体。这种设计便于使用 SDD 翻译方案直接构造 AST。
以表达式（Expr）为例：
// ast/mod.rs
#[derive(Debug, Clone)]
pub enum Expr {
Unary {
op: Span<UnaryOp>,
expr: Box<Expr>,
},
Binary {
op: Span<BinaryOp>,
lhs: Box<Expr>,
rhs: Box<Expr>,
},
Number(Span<i32>),
LVal(Span<LVal>),
Call(Span<CallExpr>),
}其对应到如下的 BNF（不考虑二义性）：
Expr ::= UnaryOp Expr
| Expr BinaryOp Expr
| Number
| LVal
| CallExpr在 Expr 的定义中，还有一些 Span<T> 的结构，这些结构储存了 AST 节点在源文件中对应的位置信息。详细的设计见下文。
IR 生成部分没有独立的数据结构，而是在语法树基础上进行拓展。每个语法树节点实现名为 build_ir 或 build_ir_in 的拓展方法，构造当前节点对应的 IR 定义。
// irgen/mod.rs
impl ast::CompUnit {
/// Build IR from AST.
pub fn build_ir(self) -> Result<(Program, ProgramMetadata)> {
let mut symtable = SymbolTable::new();
let mut program = Program::new();
let mut metadata = ProgramMetadata::new();
symtable.push();
self.build_ir_in(&mut symtable, &mut program, &mut metadata)?;
symtable.pop();
Ok((program, metadata))
}
// ...
}后端
后端的实现同样以对已有数据结构的包装为基础。代码生成实现为 Koopa IR 的拓展方法。由于 Rust 语言的限制（无法为外部结构实现方法），一个辅助数据结构用于增加方法拓展。
// codegen/mod.rs
/// Code generator for Koopa IR.
#[repr(transparent)]
pub struct Codegen<T>(pub T);于是可以在此结构的基础上增加方法实现：
// codegen/mod.rs
impl Codegen<&koopa::ir::Program> {
/// Generate code from Koopa IR.
pub fn generate(self, analyzer: &mut Analyzer, opt_level: u8) -> Result<riscv::Program> {
let mut program = riscv::Program::new();
let mut program_ctx = ProgramContext {
global: analyzer.analyze_global_values(),
func_map: HashMap::new(),
};
// ...
}
}为了实现代码优化，后端生成的目标代码不是输出字符串，而是输出到一种与 RISC-V 汇编结构一致的内部表示。
// codegen/riscv.rs
/// RISC-V register.
#[derive(Debug, Clone, Copy, PartialOrd, Ord, PartialEq, Eq, Hash)]
#[repr(u8)]
#[allow(dead_code, missing_docs)]
pub enum RegId {
X0 = 0, // zero
// ...
}
/// RISC-V instruction (RV32I, RV32M).
#[derive(Debug, Clone, Copy, PartialEq, Eq, Hash)]
#[allow(dead_code)]
pub enum Inst {
// Data transfer
// --------------------
/// Load immediate.
Li(RegId, i32),
// ...
}
/// RISC-V basic block.
#[derive(Debug, Clone, PartialEq, Eq)]
pub struct Block {
/// Instructions in the basic block.
instructions: InstList,
}
/// RISC-V function.
#[derive(Debug, Clone, PartialEq, Eq)]
pub struct Function {
/// Name of the function.
pub id: FunctionId,
/// Basic blocks in the function.
blocks: BlockList,
}
/// RISC-V program.
pub struct Program {
/// Global variables in the program.
pub globals: Vec<Global>,
/// Functions in the program.
pub functions: Vec<Function>,
}代码分析
代码分析在后端中扮演着关键的角色，其架构受到太阿框架设计的启发。每个分析都通过一个数据结构保存其结果，并具备一个名为 analyze 的方法，用于执行分析并返回结果。此外，系统还包括一个全局的 Analyzer 结构，用于管理和缓存分析结果，以避免重复计算。
// analysis/cfg.rs
/// Control flow graph.
pub struct ControlFlowGraph {
pub(super) graph: DiGraph<BasicBlock, Edge>,
pub(super) bb_map: HashMap<BasicBlock, NodeIndex>,
pub(super) entry: NodeIndex,
pub(super) exits: Vec<NodeIndex>,
}
impl ControlFlowGraph {
/// Analyze the control flow graph of a function.
///
/// # Panics
/// Panics if the function has no basic blocks, i.e. a function declaration.
pub fn analyze(func: &FunctionData) -> Self {
// ...
}
}// analysis/mod.rs
/// Program analyser.
#[allow(dead_code)]
pub struct Analyzer<'a> {
program: &'a Program,
metadata: &'a ProgramMetadata,
global_values: OnceCell<Rc<GlobalValues>>,
cfg_cache: HashMap<Function, Rc<ControlFlowGraph>>,
dominators_cache: HashMap<Function, Rc<Dominators>>,
liveliness_cache: HashMap<Function, Rc<Liveliness>>,
local_vars_cache: HashMap<Function, Rc<LocalVars>>,
regalloc_cache: HashMap<Function, Rc<RegAlloc>>,
calls_cache: HashMap<Function, Rc<FunctionCalls>>,
frame_cache: HashMap<Function, Rc<Frame>>,
}主要设计考虑及算法选择
符号表的设计考虑
符号表采用 ChainMap 数据结构，其中包含一系列以栈形式存储的 HashMap。每当进入新的作用域时，会向符号表栈推入一个空的 HashMap，而在离开作用域时则将其弹出。当前作用域的符号定义会被插入位于栈顶的 HashMap。在需要查找符号时，会从栈顶到栈底依次遍历 HashMap，并返回找到的第一个符号定义。
寄存器分配策略
为每个Koopa IR中的值分配一个物理寄存器。基于在IR上进行的活跃变量分析的结果，采用贪心策略进行寄存器分配：当值进入其生存期时，如果存在空闲寄存器，则将其分配给该值；否则，将该值溢出到栈上。在值的生存期结束时，将其对应的寄存器标记为空闲状态。
为了处理溢出情况或其他需要临时变量的情况，将a0、t0和t1这几个寄存器保留为不分配给值的临时变量使用。
采用的优化策略
目前仅在目标代码层次进行进行了一些优化，如：复写传播、常量传播、死代码消除。
编译器实现
各阶段编码细节
Lv1. main函数和Lv2. 初试目标代码生成
在最初的这个阶段，编译器的大体架构已经确立，其以 AST和 IR 为核心，主要的逻辑实现在数据结构的扩展方法上。
与后续版本采用 wrapper struct 的方式不同，此时的后端采用了使用 helper trait 的方式来实现 Koopa IR 的扩展方法。这两种模式各有优势：前者具有更高的灵活性，而后者的语法更为自然。由于扩展方法主要用于编译器的内部实现，因此语法的重要性并不十分突出，这也是后续版本转向封装结构体模式的原因。
在这个版本中，已经实现了命令行参数解析的功能。由于 lab 要求的命令行格式较为特殊（单横线加多字母命令），现有的命令行解析库无法直接支持，因此命令行解析功能基本上是手动编写的。
Lv3. 表达式
在这个版本中，IR 开始引入中间值，因此寄存器分配成为了重点实现的功能。我选择的寄存器分配策略是基于活跃变量分析的贪心线性扫描，这个策略一直沿用到了最终的版本。
由于此时的 IR 只包含一个基本块，为了简化实现，分析过程中并未考虑流敏感性。为了减少内存分配，用两个哈希表表示分析结果：live_in 记录了每个基本块开始时活跃的变量集合（在这个阶段只有空集），live_out 记录了每条指令执行完后不再活跃的变量集合。这样，可以在一次正向遍历中，增量式地计算出每条指令对应的活跃变量集合。虽然这并非标准的活跃变量分析（因为无用赋值也会被视为活跃变量），但对于寄存器分配来说，这已经足够了。
Lv4. 常量和变量
从这个版本开始，引入了符号表。符号表的数据结构参考了 Python 标准库中的 ChainMap，它是一种以栈的形式存储一系列 HashMap 的结构。
在此之前，目标代码的生成是直接通过字符串拼接实现的。从这个版本开始，改为首先生成与 RISC-V 同构的中间表示，然后再输出为字符串。这种方式不仅便于后续的优化，也有利于利用类型检查避免一些错误的指令（例如，通过自定义 i12 类型来表示 12 位整数，从而避免输出数值越界的目标代码）。
为了提供用户友好的编译错误信息，这个版本的 AST 新增了保存语法节点位置信息的功能。由于并非所有节点都需要显式存储位置信息，一些类型的节点（如 Expr）的位置信息可以通过其子节点推断得出。为了减少不必要的存储开销，我设计了 Spanned trait 来抽象不同的存储行为。像 Expr 这样可以从子节点推断位置信息的节点，可以直接实现 Spanned trait；而需要显式存储位置信息的节点，则包装在 Span<T> 结构中。Span<T> 统一实现 Spanned trait。这类节点则实现 NonSpanned trait，以简化 Span<T> 的构造过程。
impl Spanned for Expr {
// ...
}
impl<T> Spanned for Span<T> {
fn start_pos(&self) -> usize { self.start }
fn end_pos(&self) -> usize { self.end }
}
pub trait NonSpanned {
/// Convert the syntax unit into a spanned syntax unit.
fn into_span(self, start: usize, end: usize) -> Span<Self>
where
Self: Sized,
{
Span { start, end, node: self }
}
}Lv5. 语句块和作用域
由于在 lv4 中，符号表数据结构已经支持了嵌套作用域，因此这部分在这个版本中没有进行修改。
这个版本开始使用基于 proptest 的随机测试。这种测试方法通过生成随机的测试样例，然后检查输入和输出后需要保持的性质。如果测试失败，它会尝试找到导致失败的最小样例。随机测试发现了在已有实现中存在的一些问题，例如不能处理存在多个 return 语句，或者缺少 return 语句的情况。在引入测试之后，这些在特殊情况下出现的问题得到了轻松修复。
然而，proptest 的挑战在于生成测试样例的代码维护难度较大。主要难点在于如何生成语义正确的程序。尽管 proptest 支持采用拒绝采样的方法，但过高的拒绝率会降低测试效率，因此仍需要保证大部分生成的程序是语义正确的。比较复杂的点是避免 use before define 和控制声明与一般语句的比例。随着后期程序语义的复杂性增加，维护难度也随之增大，这拖累了开发进度。因此，在后续版本中，我决定移除测试代码。proptest 是很有效的测试方案，但仍需要更好的方式来生成测试样例。
Lv6. if语句
本部分引入了复杂的控制流，这在前端和后端都导致了较大的修改需求。
前端实现上的挑战主要在于处理缺失 return 语句的情况。Koopa IR 规定基本块必须以 br、jump 或 ret 结尾。如果在生成 IR 时，发现一个基本块并未以这些语句结尾，需要插入一个 ret 语句以确保正确性。这就要求维护一个“当前基本块是否已结束”的状态，并在所有必要的地方进行检查。为了避免忽视必要的检查，我采用了 Rust 语言的一种零开销的防御性编程模式，将这个状态包装在一个标记为 #[must_use] 的透明结构体中。这样，每次接收到这个值时，都必须进行检查，否则编译器会发出未使用值的警告。
后端由于引入了控制流跳转，已有的程序分析部分需要全部重写。程序分析被独立为 analysis 模块，作为前后端的连接桥梁。在这个版本中，实现了构建控制流图及其分配树、活跃变量分析和寄存器分配等分析。
Lv7. while语句
本版本的架构基本上延续了 lv6，并没有进行太多的修改。循环的实现比预想的要简单得多。
Lv8. 函数和全局变量
本部分的前端实现相对简单，只需在符号表中增加新的函数声明类型。然而，在语法分析上，遇到了一些挑战：如果在语法层面区分函数返回值类型与变量类型，会产生规约-规约冲突。解决方案是将两者统一为同一语法单元，并在语义层面进行区分。
后端的实现关键在于栈帧的构建。在我的实现中，函数的栈帧自底向上依次为保存的 ra 寄存器、局部变量、溢出的临时值、调用者保存寄存器和函数参数。栈帧构建被实现为一个程序分析，包括记录局部变量、统计函数参数等子分析。
此外，还有一个需要注意的细节：在寄存器分配时，我直接为临时值分配物理寄存器，因此在函数参数传递时，保存在 a0~a7 的参数在赋值时存在顺序依赖关系，例如 mv a1, a2 必须在 mv a2, a0 之前执行，否则 a2 中保存的值会丢失。为解决这个问题，我构建了一个依赖图，在强连通分量上进行拓扑排序，然后根据排序结果进行调度。
Lv9. 数组
为了实现数组到指针的隐式转换，前端终于引入了完整的类型检查，这包括给符号表添加类型信息，以及区分左值和右值的不同行为。
多维数组的初始化规则相当复杂，且相关资料的解释也不甚明确。我的理解是，可以将其视为复杂进制下的自增器，其中数组维度代表每一位的进制。遇到一般值时，自增器加1；遇到嵌套初始化时，寻找最低的非零位，然后对这一位加1。当发生进位时，意味着需要将子初始化器包装为更高维数组的初始化器。实现代码如下：
impl Span<ast::InitVal> {
/// Canonicalize the initializer.
pub fn canonicalize(self, indices: &[i32]) -> Result<Span<ast::InitVal>> {
let span = self.span().into();
let new_ce = || CompileError::InvalidInitializer { span };
if indices.is_empty() {
// not an array
return ...;
}
let inits = match self.node {
ast::InitVal::Expr(_) => Err(new_ce())?,
ast::InitVal::InitList(inits) => inits,
};
let mut digits = vec![vec![]; indices.len()];
for init in inits {
let (base, init) = match init.node {
ast::InitVal::Expr(_) => (indices.len() - 1, init),
ast::InitVal::InitList(_) => {
let base = digits.iter()
.rposition(|d| !d.is_empty())
.unwrap_or(0);
let sub_indices = &indices[base + 1..];
let init = init.canonicalize(sub_indices)?;
(base, init)
}
};
let mut carry = Some(init);
for i in (0..=base).rev() {
let Some(carry) = carry.take() else { break };
digits[i].push(carry);
if digits[i].len() >= indices[i] as usize {
carry = Some(ast::InitVal::InitList(
std::mem::take(&mut digits[i])
).into_span(0, 0));
}
}
if let Some(carry) = carry {
return Ok(carry);
}
}
// pad zeros
let mut carry = None;
for i in (0..indices.len()).rev() {
debug_assert!(digits[i].len() < indices[i] as usize);
if let Some(carry) = carry.take() {
digits[i].push(carry);
}
digits[i].resize(indices[i] as usize, Self::zeroed(&indices[i + 1..]));
carry = Some(ast::InitVal::InitList(
std::mem::take(&mut digits[i])
).into_span(0, 0));
}
let carry = carry.unwrap();
Ok(carry)
}
/// Return a zeroed initializer list.
fn zeroed(indices: &[i32]) -> Span<ast::InitVal> {
match indices {
[] => ast::InitVal::Expr(ast::Expr::Number(0.into_span(0, 0)))
.into_span(0, 0),
[index, indices @ ..] => ast::InitVal::InitList(
(0..*index)
.map(|_| Self::zeroed(indices))
.collect::<Vec<_>>(),
)
.into_span(0, 0),
}
}
}工具软件介绍（若未使用特殊软件或库，则本部分可略过）
lalrpop：支持 SDD 的语法解析器koopa：IR 构造、解析、打印key-node-list：便于在任意位置删改的双向链表，用于目标代码的可优化表示clio和owo-colors：用于实现用户友好的命令行界面miette：输出用户友好的编译错误信息nolog：日志调试输出petgraph：图论算法valgrind：性能分析
测试情况说明
见上文 lv5 的编码细节。
实习总结
收获和体会
我比较熟悉 Rust 语言，选择编译这门课的其中一个原因便是可以使用 Rust 来编写 lab。完成超过 3000 行的 lab 代码，我对 Rust 语言中的各种设计模式有了更深的掌握。
在这次实践中，我大量运用了防御性编程的模式。通过精心的规划和设计，将唯一正确的代码安置在舒适区，尽可能地将所有容易出现逻辑错误的部分显露出来。由于编译器不太可能出现内存安全问题，主要的错误源头在于逻辑错误，因此，防御性编程的使用可以预防许多问题的发生。
学习过程中的难点，以及对实习过程和内容的建议
SysY 语法保留了 C 语言中一些由于历史原因而变得晦涩难懂的元素。例如，多维数组的初始化器写法，这一部分的实现难度并不在于编译原理，而在于理解 C 语言标准给出的定义。然而，在实际编程中，这些复杂的初始化器基本上很少会用到。
我认为，作为编译课程实验设计的语言，应该更加着重于贴近课程的知识和原理，避免引入不必要的设计噪声，没有必要为了迎合 C 语言而引入额外的复杂性。
对老师讲解内容与方式的建议
可以教教 Rust，有不少同学对这门语言挺恐惧的。