Moonbit 与 llvm 共舞 下篇 - llvm后端生成
引言
在编程语言设计的过程中，语法前端负责理解和验证程序的结构与语义，而编译器后端则承担着将这些抽象概念转化为可执行机器代码的重任。后端的实现不仅需要对目标体系结构有深入的理解，更要掌握复杂的优化技术来生成高效的代码。
LLVM（Low Level Virtual Machine）作为现代编译器基础设施的集大成者，为我们提供了一个强大而灵活的解决方案。通过将程序转换为LLVM中间表示（Intermediate Representation, IR），我们可以利用LLVM成熟的工具链将代码编译到多种目标架构，包括RISC-V、ARM和x86等。
Moonbit的LLVM生态
Moonbit官方提供了两个重要的LLVM相关项目：
- **
llvm.mbt**：原版LLVM的Moonbit语言绑定，提供对llvm-c接口的直接访问。需要安装完整的LLVM工具链，只能生成native后端，需要自行解决编译和链接的问题，但能够生成与原版LLVM完全兼容的IR。- **
MoonLLVM**：纯Moonbit实现的LLVM仿制版，无需外部依赖即可生成LLVM IR，支持JavaScript和WebAssembly后端本文选择
llvm.mbt作为我们的工具，其API设计参考了Rust生态中广受好评的inkwell库。
在上篇《Moonbit 与 LLVM 共舞：实现现代编译器（上篇）》中，我们已经完成了从源代码到类型化抽象语法树的转换。本篇将承接这一成果，重点阐述代码生成的核心技术和实现细节。
第一章：LLVM类型系统的Moonbit表示
在深入代码生成之前，我们需要首先理解llvm.mbt如何在Moonbit的类型系统中表示LLVM的各种概念。LLVM的类型系统相当复杂，包含基本类型、复合类型和函数类型等多个层次。
Trait Object：类型的抽象表示
在llvm.mbt的API设计中，你会频繁遇到&Type这一核心概念。这并非一个具体的struct或enum，而是一个Trait Object——可以将其理解为面向对象编程中抽象基类的函数式对等物。
// &Type是一个trait object，代表任意LLVM类型
let Unit
some_type: &Type = Unit
context.() -> Unit
i32_type()
类型识别与转换
要确定一个&Type的具体类型，我们需要通过as_type_enum接口进行运行时类型检查：
pub fn (ty : Unit) -> String
identify_type(Unit
ty: &Type) -> String
String {
match Unit
ty.() -> Unit
as_type_enum() {
(Unit) -> Unit
IntType(Unit
int_ty) => "Integer type with \{Unit
int_ty.() -> Unit
get_bit_width()} bits"
(_/0) -> Unit
FloatType(_/0
float_ty) => "Floating point type"
(_/0) -> Unit
PointerType(_/0
ptr_ty) => "Pointer type"
(_/0) -> Unit
FunctionType(_/0
func_ty) => "Function type"
(_/0) -> Unit
ArrayType(_/0
array_ty) => "Array type"
(_/0) -> Unit
StructType(_/0
struct_ty) => "Structure type"
(_/0) -> Unit
VectorType(_/0
vec_ty) => "Vector type"
(_/0) -> Unit
ScalableVectorType(_/0
svec_ty) => "Scalable vector type"
(_/0) -> Unit
MetadataType(_/0
meta_ty) => "Metadata type"
}
}
安全的类型转换策略
当我们确信某个&Type具有特定的类型时，有多种转换方式可供选择：
- 直接转换（适用于确定性 场景）
let Unit
ty: &Type = Unit
context.() -> Unit
i32_type()
let ?
i32_ty = Unit
ty.() -> ?
into_int_type() // 直接转换，错误由llvm.mbt处理
let ?
bit_width = ?
i32_ty.() -> ?
get_bit_width() // 调用IntType特有的方法
- 防御性转换（推荐的生产环境做法）
let Unit
ty: &Type = () -> Unit
get_some_type() // 从某处获得的未知类型
guard ty.as_type_enum() is IntType(i32_ty) else {
raise CodeGenError("Expected integer type, got \{ty}")
}
// 现在可以安全地使用i32_ty
let ?
bit_width = ?
i32_ty.() -> ?
get_bit_width()
复合类型的构造
LLVM支持多种复合类型，这些类型通常通过基本类型的方法来构造：
pub fn (context : ?) -> Unit
create_composite_types(?
context: @llvm.Context) -> Unit
Unit {
let Unit
i32_ty = ?
context.() -> Unit
i32_type()
let Unit
f64_ty = ?
context.() -> Unit
f64_type()
// 数组类型：[16 x i32]
let Unit
i32_array_ty = Unit
i32_ty.(Int) -> Unit
array_type(16)
// 函数类型：i32 (i32, i32)
let Unit
add_func_ty = Unit
i32_ty.(Array[Unit]) -> Unit
fn_type([Unit
i32_ty, Unit
i32_ty])
// 结构体类型：{i32, f64}
let Unit
struct_ty = ?
context.(Array[Unit]) -> Unit
struct_type([Unit
i32_ty, Unit
f64_ty])
// 指针类型（LLVM 18+中所有指针都是opaque）
let Unit
ptr_ty = Unit
i32_ty.() -> Unit
ptr_type()
// 输出类型信息用于验证
(input : String) -> Unit
Prints any value that implements the Show trait to the standard output,
followed by a newline.
Parameters:
value : The value to be printed. Must implement the Show trait.
Example:
println(42)
println("Hello, World!")
println([1, 2, 3])
println("Array type: \{Unit
i32_array_ty}") // [16 x i32]
(input : String) -> Unit
Prints any value that implements the Show trait to the standard output,
followed by a newline.
Parameters:
value : The value to be printed. Must implement the Show trait.
Example:
println(42)
println("Hello, World!")
println([1, 2, 3])
println("Function type: \{Unit
add_func_ty}") // i32 (i32, i32)
(input : String) -> Unit
Prints any value that implements the Show trait to the standard output,
followed by a newline.
Parameters:
value : The value to be printed. Must implement the Show trait.
Example:
println(42)
println("Hello, World!")
println([1, 2, 3])
println("Struct type: \{Unit
struct_ty}") // {i32, f64}
(input : String) -> Unit
Prints any value that implements the Show trait to the standard output,
followed by a newline.
Parameters:
value : The value to be printed. Must implement the Show trait.
Example:
println(42)
println("Hello, World!")
println([1, 2, 3])
println("Pointer type: \{Unit
ptr_ty}") // ptr
}
重要提醒：Opaque指针
自LLVM 18版本开始，所有指针类型都采用了opaque指针设计。这意味着无论指向什么类型，所有指针在IR中都表示为
ptr，指向的具体类型信息在类型系统中不再可见。
第二章：LLVM值系统与BasicValue概念
相比类型系统，LLVM的值系统会复杂一些。llvm.mbt与inkwell一致，将值分为两个重要的抽象层次。Value 和 BasicValue。不同点在于在于区分值的创建来源和值的使用方式：
- Value：关注值是如何产生的（常量、指令结果等）
- BasicValue：关注值具有什么样的基本类型（整数、浮点数、指针等）
实际应用示例
pub fn (context : ?, builder : ?) -> Unit
demonstrate_value_system(?
context: Context, ?
builder: Builder) -> Unit
Unit {
let Unit
i32_ty = ?
context.() -> Unit
i32_type()
// 创建两个整数常量 - 这些直接就是IntValue
let Unit
const1 = Unit
i32_ty.(Int) -> Unit
const_int(10) // Value: IntValue, BasicValue: IntValue
let Unit
const2 = Unit
i32_ty.(Int) -> Unit
const_int(20) // Value: IntValue, BasicValue: IntValue
// 执行加法运算 - 结果是一个指令InstructionValue
let Unit
add_result = ?
builder.(Unit, Unit) -> Unit
build_int_add(Unit
const1, Unit
const2)
// 在不同的上下文中，我们需要不同的视角：
// 作为指令来检查其属性
let Unit
instruction = Unit
add_result.() -> Unit
as_instruction()
(input : String) -> Unit
Prints any value that implements the Show trait to the standard output,
followed by a newline.
Parameters:
value : The value to be printed. Must implement the Show trait.
Example:
println(42)
println("Hello, World!")
println([1, 2, 3])
println("Instruction opcode: \{Unit
instruction.() -> Unit
get_opcode()}")
// 作为基本值来获取其类型
let Unit
basic_value = Unit
add_result.() -> Unit
into_basic_value()
(input : String) -> Unit
Prints any value that implements the Show trait to the standard output,
followed by a newline.
Parameters:
value : The value to be printed. Must implement the Show trait.
Example:
println(42)
println("Hello, World!")
println([1, 2, 3])
println("Result type: \{Unit
basic_value.() -> Unit
get_type()}")
// 作为整数值来进行后续计算
let Unit
int_value = Unit
add_result.() -> Unit
into_int_value()
let Unit
final_result = ?
builder.(Unit, Unit) -> Unit
build_int_mul(Unit
int_value, Unit
const1)
}
值类型的完整分类
- ValueEnum：所有可能的值类型
pub enum ValueEnum {
(?) -> ValueEnum
IntValue(IntValue) // 整数值
(?) -> ValueEnum
FloatValue(FloatValue) // 浮点数值
(?) -> ValueEnum
PointerValue(PointerValue) // 指针值
(?) -> ValueEnum
StructValue(StructValue) // 结构体值
(?) -> ValueEnum
FunctionValue(FunctionValue) // 函数值
(?) -> ValueEnum
ArrayValue(ArrayValue) // 数组值
(?) -> ValueEnum
VectorValue(VectorValue) // 向量值
(?) -> ValueEnum
PhiValue(PhiValue) // Phi节点值
(?) -> ValueEnum
ScalableVectorValue(ScalableVectorValue) // 可伸缩向量值
(?) -> ValueEnum
MetadataValue(MetadataValue) // 元数据值
(?) -> ValueEnum
CallSiteValue(CallSiteValue) // 调用点值
(?) -> ValueEnum
GlobalValue(GlobalValue) // 全局值
(?) -> ValueEnum
InstructionValue(InstructionValue) // 指令值
} derive(trait Show {
output(Self, &Logger) -> Unit
to_string(Self) -> String
}
Trait for types that can be converted to String
Show)
- BasicValueEnum：具有基本类型的值
pub enum BasicValueEnum {
(?) -> BasicValueEnum
ArrayValue(ArrayValue) // 数组值
(?) -> BasicValueEnum
IntValue(IntValue) // 整数值
(?) -> BasicValueEnum
FloatValue(FloatValue) // 浮点数值
(?) -> BasicValueEnum
PointerValue(PointerValue) // 指针值
(?) -> BasicValueEnum
StructValue(StructValue) // 结构体值
(?) -> BasicValueEnum
VectorValue(VectorValue) // 向量值
(?) -> BasicValueEnum
ScalableVectorValue(ScalableVectorValue) // 可伸缩向量值
} derive(trait Show {
output(Self, &Logger) -> Unit
to_string(Self) -> String
}
Trait for types that can be converted to String
Show)
💡 值转换的最佳实践
在实际的代码生成过程中，我们经常需要在不同的值视角之间进行转换：
pub fn (instruction_result : Unit) -> Unit
value_conversion_patterns(Unit
instruction_result: &Value) -> Unit
Unit {
// 模式1：我知道这是什么类型，直接转换
let Unit
int_val = Unit
instruction_result.() -> Unit
into_int_value()
// 模式2：我只需要一个基本值，不关心具体类型
let Unit
basic_val = Unit
instruction_result.() -> Unit
into_basic_value()
// 模式3：防御性编程，检查后转换
match Unit
instruction_result.() -> Unit
as_value_enum() {
// 处理整数值
(Unit) -> Unit
IntValue(Unit
int_val) => (Unit) -> Unit
handle_integer(Unit
int_val)
// 处理浮点值
(Unit) -> Unit
FloatValue(Unit
float_val) => (Unit) -> Unit
handle_float(Unit
float_val)
_ => raise Error
CodeGenError("Unexpected value type")
}
}
通过这种双层抽象，llvm.mbt既保持了LLVM值系统的完整性，又为Moonbit开发者提供了直观易用的接口。
第三章：LLVM IR生成实战
在理解了类型和值系统的基础上，让我们通过一个完整的示例来演示如何使用llvm.mbt生成LLVM IR。这个示例将实现一个简单的 muladd 函数，展示从初始化到指令生成的完整流程。
基础设施初始化
任何LLVM程序的开始都需要建立三个核心组件：
pub fn () -> (?, ?, ?)
initialize_llvm() -> (Context, Module, Builder) {
// 1. 创建LLVM上下文 - 所有LLVM对象的容器
let ?
context = () -> ?
@llvm.Context::create()
// 2. 创建模块 - 函数和全局变量的容器
let ?
module = ?
context.(String) -> ?
create_module("demo_module")
// 3. 创建IR构建器 - 用于生成指令
let ?
builder = ?
context.() -> ?
create_builder()
(?
context, ?
module, ?
builder)
}
一个简单的函数生成示例
让我们实现一个计算 (a * b) + c 的函数：
pub fn () -> String
generate_muladd_function() -> String
String {
// 初始化LLVM基础设施
let (?
context, ?
module, ?
builder) = () -> (?, ?, ?)
initialize_llvm()
// 定义函数签名
let Unit
i32_ty = ?
context.() -> Unit
i32_type()
let Unit
func_type = Unit
i32_ty.(Array[Unit]) -> Unit
fn_type([Unit
i32_ty, Unit
i32_ty, Unit
i32_ty])
let Unit
func_value = ?
module.(String, Unit) -> Unit
add_function("muladd", Unit
func_type)
// 创建函数入口基本块
let Unit
entry_block = ?
context.(Unit, String) -> Unit
append_basic_block(Unit
func_value, "entry")
?
builder.(Unit) -> Unit
position_at_end(Unit
entry_block)
// 获取函数参数
let Unit
arg_a = Unit
func_value.(Int) -> Unit
get_nth_param(0).() -> Unit
unwrap().() -> Unit
into_int_value()
let Unit
arg_b = Unit
func_value.(Int) -> Unit
get_nth_param(1).() -> Unit
unwrap().() -> Unit
into_int_value()
let Unit
arg_c = Unit
func_value.(Int) -> Unit
get_nth_param(2).() -> Unit
unwrap().() -> Unit
into_int_value()
// 生成计算指令
let Unit
mul_result = ?
builder.(Unit, Unit) -> Unit
build_int_mul(Unit
arg_a, Unit
arg_b).() -> Unit
into_int_value()
let Unit
add_result = ?
builder.(Unit, Unit) -> Unit
build_int_add(Unit
mul_result, Unit
arg_c)
// 生成返回指令
let _ = ?
builder.(Unit) -> Unit
build_return(Unit
add_result)
// 输出生成的IR
?
module.() -> String
dump()
}
生成的LLVM IR
运行上述代码将产生以下LLVM中间表示：
; ModuleID = 'demo_module'
source_filename = "demo_module"
define i32 @muladd(i32 %0, i32 %1, i32 %2) {
entry:
%3 = mul i32 %0, %1
%4 = add i32 %3, %2
ret i32 %4
}
💡 代码生成最佳实践
- 命名约定
有返回值的指令，构建接口有一个name的label argument，可以给指令的结果添加名称。
let ?
mul_result = Unit
builder.(Unit, Unit, String) -> ?
build_int_mul(Unit
lhs, Unit
rhs, String
name="temp_product")
let ?
final_result = Unit
builder.(?, Unit, String) -> ?
build_int_add(?
mul_result, Unit
offset, String
name="final_sum")
- 错误处理
使用raise而并非panic来进行错误处理，对不好直接确定的情况进行异常管理。
// 对可能失败的操作进行检查
match func_value.get_nth_param(index) {
Some(param) => param.into_int_value()
None => raise CodeGenError("Function parameter \{index} not found")
}
第四章：TinyMoonbit编译器实现
现在让我们将注意力转向真正的编译器实现，将上篇文章中构建的抽象语法树转换为LLVM IR。
类型映射：从Parser到LLVM
首先需要建立TinyMoonbit类型系统与LLVM类型系统之间的映射关系：
pub struct CodeGen {
?
parser_program : Program // 源程序的AST表示
?
llvm_context : @llvm.Context // LLVM上下文
?
llvm_module : @llvm.Module // LLVM模块
?
builder : @llvm.Builder // IR构建器
Map[String, ?]
llvm_functions : type Map[K, V]
Mutable linked hash map that maintains the order of insertion, not thread safe.
Example
let map = { 3: "three", 8 : "eight", 1 : "one"}
assert_eq(map.get(2), None)
assert_eq(map.get(3), Some("three"))
map.set(3, "updated")
assert_eq(map.get(3), Some("updated"))
Map[String
String, @llvm.FunctionValue] // 函数映射表
}
pub fn (?, ?) -> Unit raise
convert_type(?
self : Self, ?
parser_type : Type) -> &@llvm.Type raise {
match ?
parser_type {
Type::?
Unit => ?
selfUnit
.?
llvm_contextUnit
.() -> Unit
void_typeUnit
() as &@llvm.Type
Type::?
Bool => ?
self.?
llvm_context.() -> Unit
bool_type()
Type::?
Int => ?
self.?
llvm_context.() -> Unit
i32_type()
Type::?
Double => ?
self.?
llvm_context.() -> Unit
f64_type()
// 可以根据需要扩展更多类型
}
}
环境管理：变量到值的映射
在代码生成阶段，我们需要维护一个从变量名到LLVM值的映射关系：
pub struct Env {
Env?
parent : struct Env {
parent: Env?
symbols: Map[String, Unit]
codegen: CodeGen
parser_function: ?
llvm_function: ?
}
Env? // 父环境引用
Map[String, Unit]
symbols : type Map[K, V]
Mutable linked hash map that maintains the order of insertion, not thread safe.
Example
let map = { 3: "three", 8 : "eight", 1 : "one"}
assert_eq(map.get(2), None)
assert_eq(map.get(3), Some("three"))
map.set(3, "updated")
assert_eq(map.get(3), Some("updated"))
Map[String
String, &@llvm.Value] // 局部变量映射
// 全局信息
CodeGen
codegen : struct CodeGen {
parser_program: ?
llvm_context: ?
llvm_module: ?
builder: ?
llvm_functions: Map[String, ?]
}
CodeGen // 代码生成器引用
?
parser_function : Function // 当前函数的AST
?
llvm_function : @llvm.FunctionValue // 当前函数的LLVM表示
}
pub fn (?, String) -> Unit?
get_symbol(?
self : Self, String
name : String
String) -> &@llvm.Value? {
match ?
self.Map[String, Unit]
symbols.(self : Map[String, Unit], key : String) -> Unit?
Retrieves the value associated with a given key in the hash map.
Parameters:
self : The hash map to search in.key : The key to look up in the map.
Returns Some(value) if the key exists in the map, None otherwise.
Example:
let map = { "key": 42 }
inspect(map.get("key"), content="Some(42)")
inspect(map.get("nonexistent"), content="None")
get(String
name) {
(Unit) -> Unit?
Some(Unit
value) => (Unit) -> Unit?
Some(Unit
value)
Unit?
None =>
match ?
self.Env?
parent {
(Env) -> Env?
Some(Env
parent_env) => Env
parent_env.(String) -> Unit?
get_symbol(String
name)
Env?
None => Unit?
None
}
}
}
变量处理：内存分配策略
TinyMoonbit作为一个系统级语言，支持变量的重新赋值。在LLVM IR的SSA（Static Single Assignment）形式中，我们需要采用alloca + load/store的模式来实现可变变量：
pub fn Stmt::(?, Env) -> Unit raise
emit(?
self : Self, Env
env : struct Env {
parent: Env?
symbols: Map[String, Unit]
codegen: CodeGen
parser_function: ?
llvm_function: ?
}
Env) -> Unit
Unit raise {
match ?
self {
// 变量声明：例如let x : Int = 5;
(String, Unit, Unit) -> ?
Let(String
var_name, Unit
var_type, Unit
init_expr) => {
// 转换类型并分配栈空间
let Unit
llvm_type = Env
env.CodeGen
codegen.(Unit) -> Unit
convert_type(Unit
var_type)
let Unit
alloca = Env
env.CodeGen
codegen.?
builder.(Unit, String) -> Unit
build_alloca(Unit
llvm_type, String
var_name)
// 将分配的指针记录到符号表
Env
env.Map[String, Unit]
symbols.(self : Map[String, Unit], key : String, value : Unit) -> Unit
Sets a key-value pair into the hash map. If the key already exists, updates
its value. If the hash map is near full capacity, automatically
grows the internal storage to accommodate more entries.
Parameters:
map : The hash map to modify.key : The key to insert or update. Must implement Hash and Eq traits.value : The value to associate with the key.
Example:
let map : Map[String, Int] = Map::new()
map.set("key", 42)
inspect(map.get("key"), content="Some(42)")
map.set("key", 24) // update existing key
inspect(map.get("key"), content="Some(24)")
set(String
var_name, Unit
allocaUnit
as &@llvm.Value)
// 计算初始化表达式的值
let Unit
init_value = Unit
init_expr.(Env) -> Unit
emit(Env
env).() -> Unit
into_basic_value()
// 将初始值存储到分配的内存
let _ = Env
env.CodeGen
codegen.?
builder.(Unit, Unit) -> Unit
build_store(Unit
alloca, Unit
init_value)
}
// 变量赋值：x = 10;
(Unit, Unit) -> ?
Assign(Unit
var_name, Unit
rhs_expr) => {
// 从符号表获取变量的内存地址
guard let (_/0) -> Unit
Some(_/0
var_ptr) = Env
env.(Unit) -> Unit
get_symbol(Unit
var_name) else {
raise Error
CodeGenError("Undefined variable: \{Unit
var_name}")
}
// 计算右侧表达式的值
let Unit
rhs_value = Unit
rhs_expr.(Env) -> Unit
emit(Env
env).() -> Unit
into_basic_value()
// 存储新值到变量内存
let _ = Env
env.CodeGen
codegen.?
builder.(Unit, Unit) -> Unit
build_store(Unit
var_ptr, Unit
rhs_value)
}
// 其他语句类型...
_ => { /* 处理其他语句 */ }
}
}
设计决策：为什么使用alloca？
在函数式语言中，不可变变量可以直接映射为SSA值。但TinyMoonbit支持变量重新赋值，这与SSA的"每个变量只赋值一次"原则冲突。
alloca + load/store 模式是处理可变变量的标准做法：
-
alloca：在栈上分配内存空间-
store：将值写入内存-
load：从内存读取值LLVM的优化过程会自动将简单的alloca转换回值形式（mem2reg优化）。
表达式代码生成
表达式的代码生成相对直观，主要是根据表达式类型调用相应的指令构建方法：
fn Expr::(?, Env) -> Unit raise
emit(?
self: Self, Env
env: struct Env {
parent: Env?
symbols: Map[String, Unit]
codegen: CodeGen
parser_function: ?
llvm_function: ?
}
Env) -> &@llvm.Value raise {
match ?
self {
(Unit) -> ?
AtomExpr(Unit
atom_expr, ..) => Unit
atom_expr.(Env) -> Unit
emit(Env
env)
(String, Unit, _/0) -> ?
Unary("-", Unit
expr, _/0
ty = (_/0) -> _/0
Some(_/0
Int)) => {
let Unit
value = Unit
expr.() -> Unit
emit().() -> Unit
into_int_value()
let Unit
zero = Env
env.Unit
gen.Unit
llvm_ctx.() -> Unit
i32_type().() -> Unit
const_zeor()
Env
env.Unit
gen.?
builder.(Unit, Unit) -> Unit
build_int_sub(Unit
zero, Unit
value)
}
(String, Unit, _/0) -> ?
Unary("-", Unit
expr, _/0
ty = (_/0) -> _/0
Some(_/0
Double)) => {
let Unit
value = Unit
expr.() -> Unit
emit().() -> Unit
into_float_value()
Env
env.Unit
gen.?
builder.(Unit) -> Unit
build_float_neg(Unit
value)
}
(String, Unit, Unit, _/0) -> ?
Binary("+", Unit
lhs, Unit
rhs, _/0
ty=(_/0) -> _/0
Some(_/0
Int)) => {
let Unit
lhs_val = Unit
lhs.() -> Unit
emit().() -> Unit
into_int_value()
let Unit
rhs_val = Unit
rhs.() -> Unit
emit().() -> Unit
into_int_value()
Env
env.Unit
gen.?
builder.(Unit, Unit) -> Unit
build_int_add(Unit
lhs_val, Unit
rhs_val)
}
// ... others
}
}
技术细节：浮点数取负
注意在处理浮点数取负时，我们使用
build_float_neg 而不是用零减去操作数。这是因为：
- IEEE 754标准：浮点数有特殊值（如NaN、∞），简单的减法可能产生不正确的结果
- 性能考虑：专用的否定指令在现代处理器上通常更高效
- 精度保证：避免了不必要的舍入误差
第五章：控制流指令的实现
控制流是程序逻辑的骨架，包括条件分支和循环结构。在LLVM IR中，控制流通过基本块（Basic Blocks）和分支指令来实现。每个基本块代表一个没有内部跳转的指令序列，块与块之间通过分支指令连接。
条件分支：if-else语句的实现
条件分支需要创建多个基本块来表示不同的执行路径：
fn Stmt::(?, Env) -> Unit raise
emit(?
self: Self, Env
env: struct Env {
parent: Env?
symbols: Map[String, Unit]
codegen: CodeGen
parser_function: ?
llvm_function: ?
}
Env) -> Unit
Unit raise {
let Unit
ctx = Env
env.Unit
gen.Unit
llvm_ctx
let Unit
func = Env
env.Unit
llvm_func
let ?
builder = Env
env.Unit
gen.?
builder
match ?
self {
(Unit, Unit, Unit) -> ?
If(Unit
cond, Unit
then_stmts, Unit
else_stmts) => {
let Unit
cond_val = Unit
cond.(Env) -> Unit
emit(Env
env).() -> Unit
into_int_value()
// 创建三个基本块
let Unit
then_block = Unit
ctx.(Unit) -> Unit
append_basic_block(Unit
llvm_func)
let Unit
else_block = Unit
ctx.(Unit) -> Unit
append_basic_block(Unit
llvm_func)
let Unit
merge_block = Unit
ctx.(Unit) -> Unit
append_basic_block(Unit
llvm_func)
// 创建跳转指令
let _ = ?
builder.(Unit, Unit, Unit) -> Unit
build_conditional_branch(
Unit
cond_val, Unit
then_block, Unit
else_block,
)
// 生成then_block的代码
?
builder.(Unit) -> Unit
position_at_end(Unit
then_block)
let Unit
then_env = ?
self.() -> Unit
subenv()
Unit
then_stmts.((Unit) -> Unit) -> Unit
each(Unit
s => Unit
s.(Unit) -> Unit
emitStmt(Unit
then_env))
let _ = ?
builder.(Unit) -> Unit
build_unconditional_branch(Unit
merge_block)
// 生成else_block的代码
?
builder.(Unit) -> Unit
position_at_end(Unit
else_block)
let Unit
else_env = ?
self.() -> Unit
subenv()
Unit
else_stmts.((Unit) -> Unit) -> Unit
each(Unit
s => Unit
s.(Unit) -> Unit
emitStmt(Unit
else_env))
let _ = ?
builder.(Unit) -> Unit
build_unconditional_branch(Unit
merge_block)
// 代码生成完毕后，builder的位置要在merge_block上
?
builder.(Unit) -> Unit
position_at_end(Unit
merge_block)
}
// ...
}
}
生成的LLVM IR示例
对于以下TinyMoonbit代码：
if x > 0 {
y = x + 1;
} else {
y = x - 1;
}
将生成类似这样的LLVM IR：
%1 = load i32, ptr %x, align 4
%2 = icmp sgt i32 %1, 0
br i1 %2, label %if.then, label %if.else
if.then: ; preds = %0
%3 = load i32, ptr %x, align 4
%4 = add i32 %3, 1
store i32 %4, ptr %y, align 4
br label %if.end
if.else: ; preds = %0
%5 = load i32, ptr %x, align 4
%6 = sub i32 %5, 1
store i32 %6, ptr %y, align 4
br label %if.end
if.end: ; preds = %if.else, %if.then
; 后续代码...
循环结构：while语句的实现
循环的实现需要特别注意条件检查和循环体的正确连接：
fn Stmt::(?, Env) -> Unit raise
emit(?
self: Self, Env
env: struct Env {
parent: Env?
symbols: Map[String, Unit]
codegen: CodeGen
parser_function: ?
llvm_function: ?
}
Env) -> Unit
Unit raise {
let Unit
ctx = Env
env.Unit
gen.Unit
llvm_ctx
let Unit
func = Env
env.Unit
llvm_func
let ?
builder = Env
env.Unit
gen.?
builder
match ?
self {
(Unit, Unit) -> ?
While(Unit
cond, Unit
body) => {
// 生成三个块
let Unit
cond_block = Unit
ctx.(Unit) -> Unit
append_basic_block(.llvm_func)
let Unit
body_block = Unit
ctx.(Unit) -> Unit
append_basic_block(Unit
llvm_func)
let Unit
merge_block = Unit
ctx.(Unit) -> Unit
append_basic_block(Unit
llvm_func)
// 首先无条件跳转到cond块
let _ = ?
builder.(Unit) -> Unit
build_unconditional_branch(Unit
cond_block)
?
builder.(Unit) -> Unit
position_at_end(Unit
cond_block)
// 在cond块内生成代码，以及条件跳转指令
let Unit
cond_val = Unit
cond.() -> Unit
emit().() -> Unit
into_int_value()
let _ = ?
builder.(Unit, Unit, Unit) -> Unit
build_conditional_branch(
Unit
cond_val, Unit
body_block, Unit
merge_block,
)
?
builder.(Unit) -> Unit
position_at_end(Unit
body_block)
// 对body块生成代码，末尾需要一个无条件跳转指令，到cond块
let Unit
body_env = ?
self.() -> Unit
subenv()
Unit
body.((Unit) -> Unit) -> Unit
each(Unit
s => Unit
s.(Unit) -> Unit
emitStmt(Unit
body_env))
let _ = ?
builder.(Unit) -> Unit
build_unconditional_branch(Unit
cond_block)
// 代码生成结束以后，跳转到merge block
?
builder.(Unit) -> Unit
position_at_end(Unit
merge_block)
}
// ...
}
}
生成的LLVM IR示例
对于TinyMoonbit代码：
while i < 10 {
i = i + 1;
}
将生成：
br label %while.cond
while.cond: ; preds = %while.body, %0
%1 = load i32, ptr %i, align 4
%2 = icmp slt i32 %1, 10
br i1 %2, label %while.body, label %while.end
while.body: ; preds = %while.cond
%3 = load i32, ptr %i, align 4
%4 = add i32 %3, 1
store i32 %4, ptr %i, align 4
br label %while.cond
while.end: ; preds = %while.cond
; 后续代码...
**💡 控制流设计要点 **
- 基本块的命名策略
append_basic_block 函数同样有name这个label argument。
// 使用描述性的块名称，便于调试和理解
let ?
then_block = Unit
context.(Unit, String) -> ?
append_basic_block(Unit
func, String
name="if.then")
let ?
else_block = Unit
context.(Unit, String) -> ?
append_basic_block(Unit
func, String
name="if.else")
let ?
merge_block = Unit
context.(Unit, String) -> ?
append_basic_block(Unit
func, String
name="if.end")
- 作用域管理
// 为每个分支和循环体创建独立的作用域
let ?
branch_env = Unit
env.() -> ?
sub_env()
branch_stmts.each( stmt => stmt.emit(branch_env) }
- 构建器位置管理
末尾注意将指令构建器放到正确的基本块上。
// 始终确保构建器指向正确的基本块
builder.position_at_end(merge_block)
// 在这个块中生成指令...
第六章：从LLVM IR到机器代码
在生成完整的LLVM IR之后，我们需要将其转换为目标机器的汇编代码。虽然llvm.mbt提供了完整的目标机器配置API，但对于学习目的，我们可以使用更简便的方法。
使用llc工具链进行编译
最直接的方法是将生成的LLVM IR输出到文件，然后使用LLVM工具链进行编译：
调用Module的dump函数即可，也可以使用println函数。
let CodeGen
gen : struct CodeGen {
parser_program: ?
llvm_context: ?
llvm_module: ?
builder: ?
llvm_functions: Map[String, ?]
}
CodeGen = ...
let ?
prog = CodeGen
gen.?
llvm_prog
prog.dump() // 更建议使用dump，会比println快一点，效果相同
// or println(prog)
完整的编译流程示例
让我们看一个完整的从源代码到汇编代码的编译流程：
- TinyMoonbit源代码
fn (n : Int) -> Int
factorial(Int
n: Int
Int) -> Int
Int {
if Int
n (x : Int, y : Int) -> Bool
<= 1 {
return 1;
}
return Int
n (self : Int, other : Int) -> Int
Multiplies two 32-bit integers. This is the implementation of the *
operator for Int.
Parameters:
self : The first integer operand.other : The second integer operand.
Returns the product of the two integers. If the result overflows the range of
Int, it wraps around according to two's complement arithmetic.
Example:
inspect(42 * 2, content="84")
inspect(-10 * 3, content="-30")
let max = 2147483647 // Int.max_value
inspect(max * 2, content="-2") // Overflow wraps around
* (n : Int) -> Int
factorial(Int
n (self : Int, other : Int) -> Int
Performs subtraction between two 32-bit integers, following standard two's
complement arithmetic rules. When the result overflows or underflows, it
wraps around within the 32-bit integer range.
Parameters:
self : The minuend (the number being subtracted from).other : The subtrahend (the number to subtract).
Returns the difference between self and other.
Example:
let a = 42
let b = 10
inspect(a - b, content="32")
let max = 2147483647 // Int maximum value
inspect(max - -1, content="-2147483648") // Overflow case
- 1);
}
fn main() -> Unit {
let Int
result: Int
Int = (n : Int) -> Int
factorial(5);
(Int) -> Unit
print_int(Int
result);
}
- 生成的LLVM IR
; ModuleID = 'tinymoonbit'
source_filename = "tinymoonbit"
define i32 @factorial(i32 %0) {
entry:
%1 = alloca i32, align 4
store i32 %0, ptr %1, align 4
%2 = load i32, ptr %1, align 4
%3 = icmp sle i32 %2, 1
br i1 %3, label %4, label %6
4: ; preds = %entry
ret i32 1
6: ; preds = %entry
%7 = load i32, ptr %1, align 4
%8 = load i32, ptr %1, align 4
%9 = sub i32 %8, 1
%10 = call i32 @factorial(i32 %9)
%11 = mul i32 %7, %10
ret i32 %11
}
define void @main() {
entry:
%0 = alloca i32, align 4
%1 = call i32 @factorial(i32 5)
store i32 %1, ptr %0, align 4
%2 = load i32, ptr %0, align 4
call void @print_int(i32 %2)
ret void
}
declare void @print_int(i32 %0)
- 使用LLC生成RISC-V汇编
# 生成llvm ir
moon run main --target native > fact.ll
# 生成RISC-V 64位汇编代码
llc -march=riscv64 -mattr=+m -o fact.s fact.ll
- 生成的RISC-V汇编片段
factorial:
.Lfunc_begin0:
.cfi_startproc
addi sp, sp, -32
.cfi_def_cfa_offset 32
sd ra, 24(sp)
.cfi_offset ra, -8
sd s0, 16(sp)
.cfi_offset s0, -16
addi s0, sp, 32
.cfi_def_cfa s0, 0
sw a0, -20(s0)
lw a0, -20(s0)
li a1, 1
blt a1, a0, .LBB0_2
li a0, 1
j .LBB0_3
.LBB0_2:
lw a0, -20(s0)
lw a1, -20(s0)
addi a1, a1, -1
sw a0, -24(s0)
mv a0, a1
call factorial
lw a1, -24(s0)
mul a0, a1, a0
.LBB0_3:
ld ra, 24(sp)
ld s0, 16(sp)
addi sp, sp, 32
ret
结语
通过本系列的两篇文章，我们完成了一个功能完整的编译器实现。尽管功能简单，但比 较完整。从字符流的词法分析，到抽象语法树的构建，再到LLVM IR的生成和机器代码的输出。
回顾
上篇：
- 基于模式匹配的优雅词法分析器
- 递归下降语法分析器的实现
- 完整的类型检查系统
- 环境链作用域管理
下篇：
- LLVM类型和值系统的深入理解
- SSA形式下的变量管理策略
- 控制流指令的正确实现
- 完整的代码生成流水线
Moonbit在编译器开发中的优势
通过这个实践项目，我们深刻体会到了Moonbit在编译器构建领域的独特价值：
- 表达力强大的模式匹配：极大简化了AST处理和类型分析的复杂度。
- 函数式编程范式：不可变数据结构和纯函数使得编译器逻辑更加清晰可靠。
- 现代化的类型系统：trait对象、泛型和错误处理机制提供了充分的抽象能力。
- 优秀的工程特性：derive功能、JSON序列化等特性显著提升了开发效率。
结语
编译器技术代表了计算机科学理论与工程实践的完美结合。通过Moonbit这一现代化的工具，我们能够以更加优雅和高效的方式探索 这个古老而又充满活力的领域。
希望本系列文章能够为读者在编译器设计的道路上提供一个有力的帮助。
学习资源推荐
