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 的生成我们需要关注这些信息:

  1. 如何生成指令序列

  2. 如何处理指令之间的数据依赖

  3. 每个指令如何处理,例如读写、四则运算等

  4. 如何确保生成的指令是静态单赋值的

实际上 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

总结

这个教程主要是写给我的零基础队友们的。希望读者现在能够掌握编译的整体思维框架。

实际中的编译器,还有更多需要处理的东西,比如条件跳转、循环、函数调用、数组、高维数组、结构体、指针等等。有了这个项目的例子,我们可以逐步地学习更多。


最近发布

要查看全部文章,请点击右上角“归档”