Rust 开发编译器速成（二）：计算编译器
书接上文。本章节会接触一些真正硬核的东西，包括从 Ast 生成 IR，以及制作一个迷你版的 LLVM，并且能够输出 LLVM IR 代码。
目标
我们会实现一个 AOT 编译器，它能够编译类似如下的语句：
11;-mem*3-1;print(mem);print(mem+7);
输出:
1-4
23
可以使用命令行
1calc -e "1;-mem*3-1;print(mem);print(mem+7);" | lli -
来运行。
环境准备
我们会沿用上一章节的代码，所以请确保你已经完成了上一章节的代码。
然后我们虽然不需要依赖 LLVM 就能生成 LLVM IR，但为了能够运行 LLVM IR，我们还是需要安装 LLVM。以 MacOS 为例：
1brew install llvm
确保 lli 命令能够运行即可。
另外我们多了一个依赖：
1id-arena = "2.2.1"
它的作用是提供竞技场分配，这样我们可以避免使用令人头秃的 Rc<RefCell<T>> 以及对应的 Weak。下面用了你就知道了。
生成 IR 前的准备
LLVM 中的 Value
首先需要介绍一下 Value。
Value 是所有 IR 实体的基类。每个 Value 都是一个命名的值，可以是整数、浮点数、指针、函数等等。Value 可以作为操作数用于构建表达式或指令，并用于定义全局变量、局部变量和函数的参数和返回值。
Value 有许多子类，如 Instruction、Argument、Constant 等等，它们各自有不同的功能。但是，不同的 Value 实例都有一些共同的特点，例如它们都有一个唯一的名称（以及命名前缀），可以拥有一个类型，还可以被分配给任何指令作为操作数。
在 LLVM IR 中，每个局部变量和全局变量都必须有一个唯一的名称，因此它们的名称通常以 % 或 @ 符号开头，以避免与 LLVM IR 中的关键字发生冲突。
我们的 IR 实体抽象
我打算使用 ValueTrait 来表示相当于 LLVM IR 中的 Value 基类的东西。如下：
1type ValueId = id_arena::Id<Value>;
2
3pub trait ValueTrait {
4 fn name(&self) -> String;
5 fn set_name(&mut self, name: String);
6 fn ty(&self) -> IrType;
7 fn set_ty(&mut self, ty: IrType);
8}
其中 IrType 是类型信息。我们提供的是最简单的编译器，所以它是：
1pub enum IrType {
2 Void,
3 Int,
4}
然后我们把 Value 分成三类：
1#[derive(Debug, Clone)]
2pub enum Value {
3 Global(GlobalValue),
4 Instruction(InstructionValue),
5 Constant(ConstantValue),
6}
其中 GlobalValue 表示全局变量，InstructionValue 表示指令，ConstantValue 表示立即数。
GlobalValue 的定义：
1#[derive(Debug, Clone)]
2pub struct GlobalValue {
3 pub name: String,
4 pub ty: IrType,
5}
ConstantValue:
1#[derive(Debug, Clone, Copy, PartialEq)]
2pub enum ConstantValue {
3 Int(i64),
4}
指令的话有这些：
1#[derive(Debug, Clone)]
2pub enum InstructionValue {
3 BinaryOperator(BinaryOperator),
4 LoadInst(LoadInst),
5 StoreInst(StoreInst),
6 AllocaInst(AllocaInst),
7 PrintIntInst(PrintIntInst),
8}
前四个都是 LLVM 中经典的指令，最后一个是我们自己定义的打印指令。我不想引入 CallInst，那样会大大增加我们例子的复杂度。
为了让这些 Value 都实现 ValueTrait，我写了一些宏，这样可以减少一些重复。然后得到这样的代码：
1use std::{cell::RefCell, fmt::format};
2
3use id_arena::Arena;
4
5use crate::ast::*;
6
7type ValueId = id_arena::Id<Value>;
8
9#[derive(Debug, Clone)]
10
11pub enum IrType {
12 Void,
13 Int,
14}
15
16pub trait ValueTrait {
17 fn name(&self) -> String;
18 fn set_name(&mut self, name: String);
19 fn ty(&self) -> IrType;
20 fn set_ty(&mut self, ty: IrType);
21}
22
23macro_rules! impl_value_trait {
24 ($type_name:ident) => {
25 impl ValueTrait for $type_name {
26 fn name(&self) -> String {
27 self.name.clone()
28 }
29
30 fn set_name(&mut self, name: String) {
31 self.name = name;
32 }
33
34 fn ty(&self) -> IrType {
35 self.ty.clone()
36 }
37
38 fn set_ty(&mut self, ty: IrType) {
39 self.ty = ty;
40 }
41 }
42 };
43}
44
45macro_rules! dummy_value_trait {
46 ($type_name:ident) => {
47 impl ValueTrait for $type_name {
48 fn name(&self) -> String {
49 "".to_string()
50 }
51
52 fn set_name(&mut self, name: String) {
53
54 }
55
56 fn ty(&self) -> IrType {
57 IrType::Void
58 }
59
60 fn set_ty(&mut self, ty: IrType) {
61
62 }
63 }
64 };
65}
66
67macro_rules! impl_value_trait_for_enum {
68 ($enum_name:ident { $($variant:ident($variant_ty:ty)),+ $(,)? }) => {
69 impl ValueTrait for $enum_name {
70 fn name(&self) -> String {
71 match self {
72 $( $enum_name::$variant(value) => value.name(), )+
73 }
74 }
75
76 fn set_name(&mut self, name: String) {
77 match self {
78 $( $enum_name::$variant(value) => value.set_name(name), )+
79 }
80 }
81
82 fn ty(&self) -> IrType {
83 match self {
84 $( $enum_name::$variant(value) => value.ty(), )+
85 }
86 }
87
88 fn set_ty(&mut self, ty: IrType) {
89 match self {
90 $( $enum_name::$variant(value) => value.set_ty(ty), )+
91 }
92 }
93 }
94 };
95}
96
97#[derive(Debug, Clone)]
98pub struct GlobalValue {
99 pub name: String,
100 pub ty: IrType,
101}
102
103impl_value_trait!(GlobalValue);
104
105#[derive(Debug, Clone, Copy, PartialEq)]
106pub enum ConstantValue {
107 Int(i64),
108}
109
110impl ValueTrait for ConstantValue {
111 fn name(&self) -> String {
112 "".to_string()
113 }
114
115 fn set_name(&mut self, name: String) {
116
117 }
118
119 fn ty(&self) -> IrType {
120 match self {
121 ConstantValue::Int(_) => IrType::Int,
122 }
123 }
124
125 fn set_ty(&mut self, ty: IrType) {
126
127 }
128}
129
130#[derive(Debug, Clone)]
131pub enum BinaryOp {
132 Add,
133 Sub,
134 Mul,
135 Div,
136}
137#[derive(Debug, Clone)]
138
139pub struct LoadInst {
140 pub name: String,
141 pub ty: IrType,
142 pub source: ValueId,
143}
144
145impl_value_trait!(LoadInst);
146
147#[derive(Debug, Clone)]
148
149pub struct StoreInst {
150 pub source: ValueId,
151 pub destination: ValueId,
152}
153
154dummy_value_trait!(StoreInst);
155
156#[derive(Debug, Clone)]
157
158pub struct AllocaInst {
159 pub name: String,
160 pub ty: IrType,
161}
162
163impl_value_trait!(AllocaInst);
164
165
166#[derive(Debug, Clone)]
167pub struct PrintIntInst {
168 pub param: ValueId,
169}
170
171dummy_value_trait!(PrintIntInst);
172
173#[derive(Debug, Clone)]
174
175pub struct BinaryOperator {
176 pub name: String,
177 pub ty: IrType,
178 pub operation: BinaryOp,
179 pub left_operand: ValueId,
180 pub right_operand: ValueId,
181}
182
183impl_value_trait!(BinaryOperator);
184
185#[derive(Debug, Clone)]
186pub enum Value {
187 Global(GlobalValue),
188 Instruction(InstructionValue),
189 Constant(ConstantValue),
190}
191
192impl_value_trait_for_enum!(Value {
193 Global(GlobalValue),
194 Instruction(InstructionValue),
195 Constant(ConstantValue),
196});
197
198#[derive(Debug, Clone)]
199pub enum InstructionValue {
200 BinaryOperator(BinaryOperator),
201 LoadInst(LoadInst),
202 StoreInst(StoreInst),
203 AllocaInst(AllocaInst),
204 PrintIntInst(PrintIntInst),
205}
206
207impl_value_trait_for_enum!(InstructionValue {
208 BinaryOperator(BinaryOperator),
209 LoadInst(LoadInst),
210 StoreInst(StoreInst),
211 AllocaInst(AllocaInst),
212 PrintIntInst(PrintIntInst),
213});
IR 的生成
IR 的生成我们需要关注这些信息：
-
如何生成指令序列
-
如何处理指令之间的数据依赖
-
每个指令如何处理，例如读写、四则运算等
-
如何确保生成的指令是静态单赋值的
实际上 IR 的生成非常简单，我们对按照 AST 的结构进行遍历，然后生成对应的 IR 指令即可。
由于指令之间可能存在依赖，比如：
1int a = 1;
2int b = a + 1;
这里的 b 依赖于 a，所以我们需要在生成 b 的指令之前，先生成 a 的指令，这一点靠遍历 AST 可以做到。但还需要在生成 b 的指令时，知道 a 的相关指令的引用。这一点可以通过函数调用的参数返回来做到。
然后我们遍历 Ast 的过程中，将产生的中间表达式的指令或者语句的指令统统追加到一个 instructions 数组，就可以生成指令序列。就是这么简单。
为了生成静态单赋值的代码，并且变量编号连续（从 0 开始，每次加 1），我们需要一个全局的计数器，每次生成一个新的变量时，就将计数器加 1，然后将计数器的值作为变量的编号。
需要注意的是有的指令没有名字，例如 CallInst，BranchInst 和 StoreInst，所以我们之前设计的时候故意没有给他们一个 name 字段。
基于这些信息，可以开始编写代码了。
1
2impl Context {
3 pub fn new() -> Self {
4 let mut context = Self {
5 values: RefCell::new(Arena::new()),
6 instructions: vec![],
7 next_id: 1,
8 global_variables: std::collections::HashMap::new(),
9 };
10 context.create_global_variable("mem".to_string());
11 context
12 }
13
14 pub fn generate_local_name(&mut self) -> String {
15 let name = format!("%{}", self.next_id);
16 self.next_id += 1;
17 name
18 }
19
20 pub fn create_global_variable(&mut self, name: String) -> ValueId {
21 let value = Value::Global(GlobalValue {name: format!("@{}", name), ty: IrType::Int});
22 let id = self.values.borrow_mut().alloc(value);
23 self.global_variables.insert(name, id);
24 id
25 }
26}
27
28pub trait IrGenerator {
29 fn to_ir(&self, context: &mut Context);
30}
31
32impl IrGenerator for TransUnit {
33 fn to_ir(&self, context: &mut Context) {
34 self.block.to_ir(context);
35 }
36}
37
38impl IrGenerator for Block {
39 fn to_ir(&self, context: &mut Context) {
40 for stmt in &self.stmts {
41 stmt.to_ir(context);
42 }
43 }
44}
45
46impl IrGenerator for Stmt {
47 fn to_ir(&self, context: &mut Context) {
48 match self {
49 Stmt::ExprStmt(expr) => {
50 let tmp = expr.to_ir(context);
51 // save to mem
52 let mem = context.global_variables.get("mem").unwrap();
53 let store_inst = StoreInst {
54 source: tmp,
55 destination: *mem,
56 };
57 let inst_value_id = context.values.borrow_mut().alloc(Value::Instruction(
58 InstructionValue::StoreInst(store_inst),
59 ));
60 context.instructions.push(inst_value_id);
61 }
62 Stmt::PrintStmt(expr) => {
63 let value_id = expr.to_ir(context);
64 let print_var_inst = PrintIntInst {
65 param: value_id,
66 };
67 let inst_value_id = context.values.borrow_mut().alloc(Value::Instruction(
68 InstructionValue::PrintIntInst(print_var_inst),
69 ));
70 context.instructions.push(inst_value_id);
71 }
72 }
73 }
74}
75
76impl Expr {
77 fn to_ir(&self, context: &mut Context) -> ValueId {
78 match self {
79 Expr::Primary(primary_expr) => primary_expr.to_ir(context),
80 Expr::Prefix(prefix_expr) => prefix_expr.to_ir(context),
81 Expr::Infix(infix_expr) => infix_expr.to_ir(context),
82 }
83 }
84}
85
86impl PrimaryExpr {
87 fn to_ir(&self, context: &mut Context) -> ValueId {
88 match self {
89 PrimaryExpr::Mem => {
90 let name = context.generate_local_name();
91 let mem = context.global_variables.get("mem").unwrap();
92 let load_inst = LoadInst {
93 name: name,
94 ty: IrType::Int,
95 source: *mem,
96 };
97 let inst_value_id = context.values.borrow_mut().alloc(Value::Instruction(
98 InstructionValue::LoadInst(load_inst),
99 ));
100 context.instructions.push(inst_value_id);
101 inst_value_id
102 }
103 PrimaryExpr::Int(i) => {
104 let value = Value::Constant(ConstantValue::Int(*i));
105 let id = context.values.borrow_mut().alloc(value);
106 id
107 }
108 PrimaryExpr::Expr(expr) => expr.to_ir(context),
109 }
110 }
111}
112
113impl PrefixExpr {
114 fn to_ir(&self, context: &mut Context) -> ValueId {
115 let expr_value_id = self.expr.to_ir(context);
116 match self.op {
117 PrefixOp::Plus => expr_value_id,
118 PrefixOp::Minus => {
119 let zero = context
120 .values
121 .borrow_mut()
122 .alloc(Value::Constant(ConstantValue::Int(0)));
123 let bin_op = BinaryOperator {
124 name: context.generate_local_name(),
125 ty: IrType::Int,
126 operation: BinaryOp::Sub,
127 left_operand: zero,
128 right_operand: expr_value_id,
129 };
130 let id = context
131 .values
132 .borrow_mut()
133 .alloc(Value::Instruction(InstructionValue::BinaryOperator(bin_op)));
134 context.instructions.push(id);
135 id
136 }
137 }
138 }
139}
140
141impl InfixExpr {
142 fn to_ir(&self, context: &mut Context) -> ValueId {
143 let lhs_value_id = self.lhs.to_ir(context);
144 let rhs_value_id = self.rhs.to_ir(context);
145 let bin_op = match self.op {
146 InfixOp::Plus => BinaryOp::Add,
147 InfixOp::Minus => BinaryOp::Sub,
148 InfixOp::Multiply => BinaryOp::Mul,
149 InfixOp::Divide => BinaryOp::Div,
150 };
151
152 let bin_inst = BinaryOperator {
153 name: context.generate_local_name(),
154 ty: IrType::Int,
155 operation: bin_op,
156 left_operand: lhs_value_id,
157 right_operand: rhs_value_id,
158 };
159 let id = context.values.borrow_mut().alloc(Value::Instruction(
160 InstructionValue::BinaryOperator(bin_inst),
161 ));
162 context.instructions.push(id);
163 id
164 }
165}
CodeGen
完成了 IR 生成，代码生成也是同样的道理。直接遍历指令序列，然后调用对应的 emit_ir 函数就行。
1use crate::ir::*;
2
3pub trait LlvmEmitter {
4 fn emit_ir(&self) -> String;
5}
6impl LlvmEmitter for Context {
7 fn emit_ir(&self) -> String {
8 let mut llvm_ir = String::new();
9
10 // Emit external print function declaration
11 // llvm_ir.push_str("declare void @print(i64)\n\n");
12 llvm_ir.push_str(r#"
13@.str = private unnamed_addr constant [6 x i8] c"%lld\0A\00", align 1
14
15define dso_local void @print(i64 noundef %0) #0{
16 %2 = alloca i64, align 8
17 store i64 %0, i64* %2, align 8
18 %3 = load i64, i64* %2, align 8
19 %4 = call i32 (i8*, ...) @printf(i8* noundef getelementptr inbounds ([6 x i8], [6 x i8]* @.str, i64 0, i64 0), i64 noundef %3)
20 ret void
21}
22
23declare i32 @printf(i8*, ...)
24"#);
25
26 // Emit global variable declarations
27 for (name, id) in &self.global_variables {
28 let global_var = format!("@{} = global i64 0\n", name);
29 llvm_ir.push_str(&global_var);
30 }
31
32 // Emit function definition
33 llvm_ir.push_str("define void @main() {\n");
34
35 // Emit instructions
36 for inst_id in &self.instructions {
37 let value = &self.values.borrow()[*inst_id];
38 match value {
39 Value::Instruction(instruction) => {
40 let llvm_instruction = emit_instruction(instruction, self);
41 llvm_ir.push_str(&llvm_instruction);
42 }
43 _ => (),
44 }
45 }
46
47 // Emit function end
48 llvm_ir.push_str(" ret void\n}\n");
49 llvm_ir
50 }
51}
52
53
54fn emit_instruction(instruction: &InstructionValue, context: &Context) -> String {
55 match instruction {
56 InstructionValue::LoadInst(load_inst) => {
57 let arena = context.values.borrow();
58 let src = arena.get(load_inst.source).unwrap();
59 format!(" {} = load i64, i64* {}\n", load_inst.name, emit_operand(src, context))
60 }
61 InstructionValue::StoreInst(store_inst) => {
62 let arena = context.values.borrow();
63 let dest = arena.get(store_inst.destination).unwrap();
64 let src = arena.get(store_inst.source).unwrap();
65 format!(
66 " store i64 {}, i64* {}\n",
67 emit_operand(src, context),
68 emit_operand(dest, context)
69 )
70 }
71 InstructionValue::AllocaInst(alloc_inst) => match alloc_inst.ty {
72 IrType::Int => format!(" {} = alloca i64\n", instruction.name()),
73 IrType::Void => unreachable!(),
74 },
75 InstructionValue::BinaryOperator(bin_op) => {
76 let operation = match bin_op.operation {
77 BinaryOp::Add => "add",
78 BinaryOp::Sub => "sub",
79 BinaryOp::Mul => "mul",
80 BinaryOp::Div => "sdiv",
81 };
82 let arena = context.values.borrow();
83 let left = arena.get(bin_op.left_operand).unwrap();
84 let right = arena.get(bin_op.right_operand).unwrap();
85 format!(
86 " {} = {} i64 {}, {}\n",
87 instruction.name(),
88 operation,
89 emit_operand(left, context),
90 emit_operand(right, context)
91 )
92 }
93 InstructionValue::PrintIntInst(print_var_inst) => {
94 let arena = context.values.borrow();
95 let param_val = arena.get(print_var_inst.param).unwrap();
96 format!(
97 " call void @print(i64 {})\n",
98 emit_operand(param_val, context)
99 )
100 }
101 }
102}
103
104fn emit_operand(value: &Value, context: &Context) -> String {
105 match value {
106 Value::Instruction(inst) => inst.name(),
107 Value::Global(global) => format!("{}", global.name()),
108 Value::Constant(constant) => format!("{}", match constant {
109 ConstantValue::Int(int) => int,
110 }),
111 }
112}
这里我们硬编码了一个 print 函数，这是因为我们没法直接生成 printf 的调用，那样太麻烦了。所以我们直接写一个 print 函数，然后在 main 函数中调用它。
经过以上步骤，我们就完成了一个简单的编译器。我们可以用它来编译一些简单的代码，比如下面这个例子：
1cargo run -- -e "4;mem+9;mem/2;print(mem);"
生成的 LLVM IR 如下：
1@.str = private unnamed_addr constant [6 x i8] c"%lld\0A\00", align 1
2
3define dso_local void @print(i64 noundef %0) #0{
4 %2 = alloca i64, align 8
5 store i64 %0, i64* %2, align 8
6 %3 = load i64, i64* %2, align 8
7 %4 = call i32 (i8*, ...) @printf(i8* noundef getelementptr inbounds ([6 x i8], [6 x i8]* @.str, i64 0, i64 0), i64 noundef %3)
8 ret void
9}
10
11declare i32 @printf(i8*, ...)
12@mem = global i64 0
13define void @main() {
14 store i64 4, i64* @mem
15 %1 = load i64, i64* @mem
16 %2 = add i64 %1, 9
17 store i64 %2, i64* @mem
18 %3 = load i64, i64* @mem
19 %4 = sdiv i64 %3, 2
20 store i64 %4, i64* @mem
21 %5 = load i64, i64* @mem
22 call void @print(i64 %5)
23 ret void
24}
使用 lli 运行，得到：
16
总结
这个教程主要是写给我的零基础队友们的。希望读者现在能够掌握编译的整体思维框架。
实际中的编译器，还有更多需要处理的东西，比如条件跳转、循环、函数调用、数组、高维数组、结构体、指针等等。有了这个项目的例子，我们可以逐步地学习更多。