源码：https://github.com/felicityin/sysy-rs本文中的例子拷贝自：https://pku-minic.github.io/online-doc实现语言的过程大概为：词法分析、语法分析、语义分析、优化、代码生成。可以使用 larlpop 进行词法、语法解析，这部分的文档较为充足，既可以阅读官方的教程，也可以阅读该教程：https://michael-f-bryan.github.io/calc/book/html/intro.html。本文主要讲述在用 larlpop 生成 AST (Abstract Syntax Tree) 后，如何使用 inkwell 将其转为 LLVM IR，该过程会进行一些语义分析和优化。最后将 LLVM IR 交给 LLVM，LLVM 将其生成指定平台的目标代码。IR 指中间表达方式，介于高级语言和汇编语言之间。与高级语言相比，丢弃了语法和语义特征，比如作用域、面向对象等；与汇编语言相比，不会有硬件相关的细节，比如目标机器架构、操作系统等。本文不考虑浮点型，整型只考虑 i32。1 LLVM 数据结构Context: 拥有和管理 LLVM 核心基础设施的核心“全局”数据，包括类型和常量统一表。let context = Context::create(); let builder = context.create_module("module"); let module = context.create_builder(); context.f64_type().const_float(0.0) context.append_basic_block(function, "then");Module: 是所有其它 LLVM IR 对象的顶级容器。每个模块直接包含全局变量列表、函数列表、该模块所依赖的库（或其它模块）列表、符号表以及有关目标特性的各种数据。module.add_function(proto.name.as_str(), fn_type, None); module.add_global(llvm_type, None, var_name); module.get_first_global().unwrap() module.get_last_global().unwrap() let global_value = self.module.add_global(llvm_type, None, var_name); global_value.set_linkage(Linkage::Common); global_value.set_constant(true); global_value.set_initializer(&value_after_cast); global_value.set_initializer(&llvm_type.const_zero()); global_value.as_pointer_value()Builder: 生成 LLVM 指令。追踪当前指令要插入的位置，创建新指令。一个 basic block 中可包含多条指令，一个函数中可包含多个 basic block。builder.build_conditional_branch(cond, then_bb, else_bb); builder.position_at_end(then_bb); builder.build_phi(self.context.f64_type(), "iftmp"); builder.build_store(start_alloca, start); builder.build_load(start_alloca, var_name); builder.build_float_add(lhs, rhs, "tmpadd")), builder.build_call(fun, &[lhs.into(), rhs.into()], "tmpbin")2 表达式2.1 一元表达式变补 (取负数): 0 减去操作数.builder.build_int_neg(exp, "int_neg")逻辑取反: 操作数和 0 比较相等builder.build_int_compare( IntPredicate::EQ, compiler.int_type.const_int(0_u64, true), exp, "logical_not_result_int", )2.2 算术表达式builder.build_int_add(lhs, rhs, "int_add") builder.build_int_sub(lhs, rhs, "int_sub") builder.build_int_mul(lhs, rhs, "int_mul") builder.build_int_signed_div(lhs, rhs, "int_div") builder.build_int_signed_rem(lhs, rhs, "int_mod")2.3 比较和逻辑表达式比较表达式builder.build_int_compare(IntPredicate::EQ, lhs, rhs, "int_eq") builder.build_int_compare(IntPredicate::NE, lhs, rhs, "int_ne") builder.build_int_compare(IntPredicate::SLT, lhs, rhs, "int_lt") builder.build_int_compare(IntPredicate::SGT, lhs, rhs, "int_gt") builder.build_int_compare(IntPredicate::SLE, lhs, rhs, "int_le") builder.build_int_compare(IntPredicate::SGE, lhs, rhs, "int_ge")逻辑表达式builder.build_and(lhs, rhs, "logical_and") builder.build_or(lhs, rhs, "logical_or")3 常量和变量3.1 常量常量会在编译期直接求值，存到作用域列表中，后面用到的时候直接取出来。3.2 变量和赋值例子：int main() { int x = 10; x = x + 1; return x; }int x = 10为变量 x 申请一块内存，返回内存指针 ptr将常量 10 赋值给 ptr// 1 let ptr = builder.build_alloca(context.i32_type(), "x"); // 2 let v = context.i32_type().const_int(v, false); builder.build_store(ptr, v);将变量 x 添加到作用域列表中，无 IRint x = 10 生成的 LLVM IR：// 1 %x = alloca i32, align 4 // 2 store i32 10, ptr %x, align 4x = x + 1将 x 从作用域列表中取出，无 IR计算 x + 1将 x 加载到内存计算将 x + 1 的结果赋值给 l_x将新的 x 存回作用域列表，无 IR// 1 let x_l = get_from_scope(); // 2.a let x_r = builder.build_load(context.i32_type(), x_l, "x"); // 2.b let v = context.i32_type().const_int(10, false); builder.build_int_add(x_r, v, "int_add") // 3 builder.build_store(x_r, x_l); // 4 insert_to_scope(x_l);x = x + 1 生成 LLVM IR：// 2.a %x1 = load i32, ptr %x, align 4 // 2.b %int_add = add i32 %x1, 1 // 3 store i32 %int_add, ptr %x, align 44 语句块和作用域语句块语法一个大括号内的内容为一个语句块。作用域支持作用域嵌套在进入和退出代码块时更新符号表的层次结构只在当前作用域添加符号能够跨作用域查询符号定义作用域实现生成 block IR 时，在进入 block 时，push 新的作用域，退出时，弹出作用域。// 在进入 block 时，push 新的作用域 scopes.push(HashMap::new()); // 为 block 内的每个元素生成 IR for item in &self.items { item.generate(compiler)?; } // 退出 block 时，弹出作用域 compiler.scopes.pop();5 if 语句例子：int main() { if (1 < 2) { } else { } return 0; }LLVM：let if_block = context.append_basic_block(func, "if_block"); let else_block = context.append_basic_block(func, "else_block"); let after_block = context.append_basic_block(func, "after_block"); // 生成 condition expr 的 IR let cond_value = self.cond_expr.generate()?; // 生成条件分支 builder.build_conditional_branch(cond_value.into_int_value(), if_block, else_block); // 移动到 if block builder.position_at_end(if_block); // 生成 if block 的 IR self.then_stmt.generate(compiler)?; // if block 中可能会嵌套别的 block，cur block 不一定是 if block // 如果 cur block 有 return 的话，直接退出 if block if cur_block.unwrap().get_terminator().is_some() { builder.build_unconditional_branch(after_block); } // 移动到 else block builder.position_at_end(else_block); // 生成 else block 的 IR self.else_stmt.generate(compiler)?;生成的 LLVM IR：br i1 true, label %if_block, label %else_block if_block: else_block: after_block:6 while 语句例子：int main() { int i = 0; while (i < 10) { i = i + 1; } return 0; }LLVM：let while_head = context.append_basic_block(func, "while_head"); let while_body = context.append_basic_block(func, "while_body"); let after_while = context.append_basic_block(func, "after_while"); // 从外边跳到本循环 builder.build_unconditional_branch(while_head); // 移动到 while head builder.position_at_end(while_head); // 生成 condition expr 的 IR let cond_value = self.cond_expr.generate()?; // 生成条件分支 builder.build_conditional_branch(cond_value.into_int_value(), while_body, after_while); // 记录本循环信息，以便后续 return 后 continue 时找到本循环 loops.push(Loop { loop_head: while_head, after_loop: after_while, }); // 移动到 while body builder.position_at_end(while_body); // 生成循环体的 IR self.body.generate(compiler)?; // while body 中可能会嵌套别的 block，cur block 不一定是 while body // 如果 cur block 没有 return 的话，跳回 while head if cur_block.unwrap().get_terminator().is_none() { builder.build_unconditional_branch(while_head); } // 删掉本循环信息 loops.pop(); // 移到 after while block，从而退出 while body block builder.position_at_end(after_while);生成的 LLVM IR：define i32 @main() { entry: %i = alloca i32, align 4 store i32 0, ptr %i, align 4 br label %while_head while_head: ; preds = %while_body, %entry %i1 = load i32, ptr %i, align 4 %int_lt = icmp slt i32 %i1, 10 br i1 %int_lt, label %while_body, label %after_while while_body: ; preds = %while_head %i2 = load i32, ptr %i, align 4 %int_add = add i32 %i2, 1 store i32 %int_add, ptr %i, align 4 br label %while_head after_while: ; preds = %while_head ret i32 0 }7 函数和全局变量7.1 函数定义例子：int half(int x) { return x / 2; } void f() {}函数签名：let mut params_type = Vec::new(); for param in self.params.iter() { params_type.push(BasicMetadataTypeEnum::from(context.i32_type()); } let fn_type = match self.ty { FuncType::Int => context.i32_type().fn_type(params_type.as_ref(), false), FuncType::Void => context.i32_type().fn_type(params_type.as_ref(), false), };将函数添加到 module：let function = module.add_function(&self.id, fn_type, None);开始实现函数：let entry_block = context.append_basic_block(function, "entry"); // 移动到 entry block builder.position_at_end(entry_block);创建新的作用域：compiler.scopes.push(HashMap::new());加载入参：for (idx, param) in self.params.iter().enumerate() { // 为入参分配空间 let ptr = compiler.builder.build_alloca(context.i32_type(), &param.id); // 获取第 n 个参数 let value = function .get_nth_param(idx as u32) .expect("the function signatures have been added before"); // option：为参数设置名称，方便阅读生成的 LLVM IR value.set_name(&param.id); // 加载入参 builder.build_store(ptr, value); // 将入参添加到当前作用域 compiler.new_value(&param.id, Variable::new_mut(ptr, llvm_type, array_type))?; }生成函数体 IR：self.block.generate(compiler)?;退出作用域：compiler.scopes.pop();生成的 LLVM IR：define i32 @half(i32 %x1) { entry: %x = alloca i32, align 4 store i32 %x1, ptr %x, align 4 %x2 = load i32, ptr %x, align 4 %int_div = sdiv i32 %x2, 2 ret i32 %int_div } define void @f() { entry: ret void }7.2 函数调用例子：int main() { f(); return half(10); }从 module 中获取已经定义好的函数，并检查参数个数是否匹配：let fv = module.get_function(&self.id).unwrap(); if self.args.len() != fv.get_type().count_param_types() as usize { return Err(CompileErr::ArgCountMismatch { id: self.id.clone(), expect: fv.get_type().count_param_types() as usize, found: self.args.len(), }); }生成参数类型：let llvm_params_value = self.args .iter() .by_ref() .map(|arg| arg.generate(compiler).unwrap().into()) .collect::<Vec<BasicMetadataValueEnum>>();调用函数：compiler.builder.build_call( fv, llvm_params_value.as_slice(), &self.id, ) .try_as_basic_value() .left() .unwrap_or(compiler.int_type.const_zero().as_basic_value_enum())生成的 LLVM IR：define i32 @main() { entry: call void @f() %half = call i32 @half(i32 10) ret i32 %half }7.3 全局变量和常量例子：int var; const int one = 1; int main() { return var + one; }全局常量：// 将全局常量添加到 module let global = module.add_global(context.i32_type(), None, &self.id); // 初始化 let v = context.i32_type().const_int(init, false).as_basic_value_enum(); global.set_initializer(&v); // 将全局常量添加到作用域符号表 ...全局变量：// 为全局变量分配内存 let global = module.add_global(context.i32_type(), None, &self.id); // 将全局变量添加到作用域符号表 ...生成的 LLVM IR：@var = external global i32 define i32 @main() { entry: %var = load i32, ptr @var, align 4 %int_add = add i32 %var, 1 ret i32 %int_add }8 数组8.1 声明数组8.1.1 全局数组例子：int a[2][3]; int main() { return 0; }为数组每一维的长度进行编译期求值：let dims = self.dims .iter() .rev() .map(|x| { x.eval(compiler).unwrap() as u32 }) .collect::<Vec<u32>>();例如，对于 a1+1 会得到 [2, 3]，逆序后，得到 [3, 2]生成数组类型：let array_type = dims.iter() .fold( compiler.int_type.as_basic_type_enum(), |acc, len| acc.array_type(len.to_owned()).as_basic_type_enum(), ) };添加到 module：module.add_global(llvm_type, None, &self.id);生成的 LLVM IR：; ModuleID = 'module' source_filename = "module" @a = external global [2 x [3 x i32]] define i32 @main() { entry: ret i32 0 }8.1.2 局部数组例子：int main() { int a[2][3]; }为数组每一维的长度进行编译期求值，同 8.1.1生成数组类型，同 8.1.1为数组分配空间let ptr = compiler.builder.build_alloca(llvm_type, &self.id);生成的 LLVM IR：; ModuleID = 'module' source_filename = "module" define i32 @main() { entry: %a = alloca [2 x [3 x i32]], align 4 ret i32 0 }8.2 数组初始化例子：int a[2][3] = {1, 2, 3, {4}}; void f() { int e = 1; int g[2] = {e, 2}; return; } int main() { int b[2][3] = {1, 2, 3, {4}}; return 0; }8.2.1 常量数组 or 全局数组为数组每一维的长度进行编译期求值，同 8.1.1为初始化列表的元素进行编译期求值例如，对于 const int arr[2] = {1, 1 + 1}; ，需要得到 const int arr[2] = {1, 2}; 。reshape 初始化列表用户可能会这样初始化数组：int arr[2][3] = {1, 2, 3, {4}};我们需要将其补充完整：int arr[2][3] = {{1, 2, 3}, {4, 0, 0}};步骤：从最低维起，记录各维度的长度 len_1, len_2, …, len_n 和总长度 total_1, total_2, …, total_n。例如，对于 int arr2，会得到 [(3, 3), (2, 6)]；对于 int arr2[4]，会得到 [(4, 4), (3, 12), (2, 24)]初始化待填充列表 reshaped，会比实际多一维。例如，对于 int a2，得到 [][][]依次处理初始化列表，可能会遇到整数或嵌套的初始化列表。如果是整数：直接将整数添加到当前所处理维度的 reshaped[0] 中。例如，对于 int arr[2][3] = {1, 2}; 看到初始化列表中的第 2 个元素 2 时，将其放到 reshaped[0] 中，得到 [1, 2][][]如果是嵌套的初始化列表：说明需要填充待填充列表的下一个维度了，当前已经填充完毕的元素的个数必须是 len_n 的整数倍，否则这个初始化列表没有对齐数组维度的边界，属于语义错误。然后递归处理，把结果添加到 reshaped 的对齐的维度中。例如，对于 int arr[2][3] = {{1, 2, 3}, {4}}; 看到 {4} 时，初始化列表应该是 [ [1, 2, 3] ][] ，然后把 {4} 添加到所对齐的维度中，得到 [ [1, 2, 3] [4] ][]carry：如果发现 reshaped[0] 已经达到当前维度的长度 len_n，则将其添加到下一维 reshaped[1] 中，并将 reshaped[0] 丢弃。例如，对于 int arr[2][3] = {1, 2, 3}; 当前处理的最低维度为 1，当前维度的长度为 3，当待填充列表成为了 [1, 2, 3][][] 时，应进一步变为 [ [1, 2, 3] ][] 。补 0：如果发现 reshaped[0] 的长度没有达到当前维度的总长度 total_n，则填充 0。例如，对于 int arr[2][3] = {{1, 2, 3}, {4}}; 当前处理的最低维度为 2，当前维度的总长度为 total_n = 6，当待填充列表成为了 [ [1, 2, 3], [4] ][] 时，应进一步变为 [ [1, 2, 3], [4, 0, 0] ][] 。carry： [ [1, 2, 3], [4, 0, 0] ][] —> [ [1, 2, 3], [4, 0, 0] ] 。一个具体的例子：int arr[2][3][4] = {1, 2, 3, 4, {5}, {6}, {7, 8}};reshaped 变化过程如下所示：// 初始化待填充列表 [][][][] // 依次填充最低维 [1][][][] [1, 2, 3, 4][][][] // carry：处理 (4, 4)，满了 4 个元素，将这 4 个元素作为一个 list，放到下一维 [] [[1, 2, 3, 4]] [] [] // 添加 [5]，递归处理，最终得到： [] [[1, 2, 3, 4] [5, 0, 0, 0]] [] [] // 添加 [5] 时的递归过程，list = [5]，lens = [(4, 4)] // [][] // [5][] // [5, 0, 0, 0][] // 补 0，直到达到 total_1 = 4 // [] [[5, 0, 0, 0]] // carry // [] [[1, 2, 3, 4] [5, 0, 0, 0]] [] [] // 从递归返回，将递归结果放到当前待填充列表 // 添加 [6]，递归处理，最终得到： [] [[1, 2, 3, 4] [5, 0, 0, 0] [6, 0, 0, 0]] [] [] // carry：处理 (3, 12)，满了 3 个元素，将这个 3 个元素作为一个 list，添加到下一维 [] [] [[[1, 2, 3, 4] [5, 0, 0, 0] [6, 0, 0, 0]]] [] // 添加 [7, 8]，递归处理，最终得到： [] [] [[[1, 2, 3, 4] [5, 0, 0, 0] [6, 0, 0, 0]] [[7, 8, 0, 0] [0, 0, 0, 0] [0, 0, 0, 0]]] [] // 添加 [7, 8] 时的递归过程，list = [7, 8]，lens = [(4, 4), (3, 12)] // [][][] // [7, 8][][] // [7, 8, 0, 0] [] [] // 补 0，直到达到 total_2 = 12 // [] [[7, 8, 0, 0]] [] // 补 0 的过程中会发生 carry // [0, 0, 0, 0] [[7, 8, 0, 0]] [] // 继续补 0 // [] [[7, 8, 0, 0] [0, 0, 0, 0]] [] // carry // [] [[7, 8, 0, 0] [0, 0, 0, 0] [0, 0, 0, 0]] [] // 继续补 0，carry // [] [] [[[7, 8, 0, 0] [0, 0, 0, 0] [0, 0, 0, 0]]] // carry // 从递归返回，将递归结果放到当前待填充列表： // [] [] [[[1, 2, 3, 4] [5, 0, 0, 0] [6, 0, 0, 0]] [[7, 8, 0, 0] [0, 0, 0, 0] [0, 0, 0, 0]]] [] // carry：处理 (2, 24)，满了 2 个元素，将这个 2 个元素作为一个 list，添加到下一维 [] [] [] [[[[1, 2, 3, 4] [5, 0, 0, 0] [6, 0, 0, 0]] [[7, 8, 0, 0] [0, 0, 0, 0] [0, 0, 0, 0]]]] // 最终得到： int arr[2][3][4] = { {{1, 2, 3, 4}, {5, 0, 0, 0}, {6, 0, 0, 0}}, {{7, 8, 0, 0}, {0, 0, 0, 0}, {0, 0, 0, 0}} };将 reshape 后的初始化列表平铺成一个列表例如，将int arr[2][3][4] = { {{1, 2, 3, 4}, {5, 0, 0, 0}, {6, 0, 0, 0}}, {{7, 8, 0, 0}, {0, 0, 0, 0}, {0, 0, 0, 0}} };改为{1, 2, 3, 4, 5, 0, 0, 0, 6, 0, 0, 0, 7, 8, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0}初始化全局数组声明数组的时候，需要确保数组类型是正确的。从低维开始根据第 5 步生成的列表构建数组：let mut dims = dims.iter(); let top_size = *dims.next().unwrap(); // 处理最低维度，会得到 ArrayValue 列表 let mut arrays = values .chunks(top_size as usize) .map(|a| context.i32_type().const_array(a)) .collect::<Vec<ArrayValue>>(); let mut ty = context.i32_type().array_type(top_size); // 处理剩下的每个维度 for d in dims { arrays = arrays .chunks(*d as usize) .map(|a| ty.const_array(a)) .collect::<Vec<ArrayValue>>(); ty = ty.array_type(*d); }例如，int arr2[4] = {1, 2, 3, 4, 5, 0, 0, 0, 6, 0, 0, 0, 7, 8, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0} 的变化过程为：1, 2, 3, 4, 5, 0, 0, 0, 6, 0, 0, 0, 7, 8, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0 // 处理最低维度，每 4 个 i32 一组，得到 6 组 [4 x i32] {1, 2, 3, 4}, {5, 0, 0, 0}, {6, 0, 0, 0}, {7, 8, 0, 0}, {0, 0, 0, 0}, {0, 0, 0, 0} // 处理较高维度，每 3 个 [4 x i32] 一组，得到 2 组 [3 x [4 x i32]] {{1, 2, 3, 4}, {5, 0, 0, 0}, {6, 0, 0, 0}}, {{7, 8, 0, 0}, {0, 0, 0, 0}, {0, 0, 0, 0}} // 处理最高维度，每 2 个 [3 x [4 x i32]] 一组，得到 1 组 [2 x [3 x [4 x i32]]] {{{1, 2, 3, 4}, {5, 0, 0, 0}, {6, 0, 0, 0}}, {{7, 8, 0, 0}, {0, 0, 0, 0}, {0, 0, 0, 0}}}将数组添加到全局符号，为数组设置初始化列表，将数组设为常量：let const_array = module.add_global( ty, Some(AddressSpace::default()), &id ); // arrays 最后只剩下一个元素 const_array.set_initializer(&arrays[0]); const_array.set_constant(true);最终，const int a2 = {1, 2, 3, {4}}; 生成的 IR 为：@arr = constant [2 x [3 x [4 x i32]]] [[3 x [4 x i32]] [[4 x i32] [i32 1, i32 2, i32 3, i32 4], [4 x i32] [i32 5, i32 0, i32 0, i32 0], [4 x i32] [i32 6, i32 0, i32 0, i32 0]], [3 x [4 x i32]] [[4 x i32] [i32 7, i32 8, i32 0, i32 0], [4 x i32] zeroinitializer, [4 x i32] zeroinitializer]]一个完整例子的 LLVM IR：const int a[2][3] = {1, 2, 3, {4}}; int c[2][3] = {1, 2, 3, {4}}; int main() { const int b[2][3] = {1, 2, 3, {4}}; return 0; }; ModuleID = 'module' source_filename = "module" @a = constant [2 x [3 x i32]] [[3 x i32] [i32 1, i32 2, i32 3], [3 x i32] [i32 4, i32 0, i32 0]] @c = constant [2 x [3 x i32]] [[3 x i32] [i32 1, i32 2, i32 3], [3 x i32] [i32 4, i32 0, i32 0]] @b = private unnamed_addr constant [2 x [3 x i32]] [[3 x i32] [i32 1, i32 2, i32 3], [3 x i32] [i32 4, i32 0, i32 0]] define i32 @main() { entry: %b = alloca [2 x [3 x i32]], align 4 call void @llvm.memcpy.p0.p0.i32(ptr align 4 %b, ptr align 4 @b, i32 24, i1 false) ret i32 0 } ; Function Attrs: argmemonly nocallback nofree nounwind willreturn declare void @llvm.memcpy.p0.p0.i32(ptr noalias nocapture writeonly, ptr noalias nocapture readonly, i32, i1 immarg) #0 attributes #0 = { argmemonly nocallback nofree nounwind willreturn }8.2.2 局部数组为数组每一维的长度进行编译期求值，同 8.1.1为数组分配空间，同 8.1.2如果有初始化列表：求初始化列表如果初始化列表中的元素都是常量，进行编译器求值即可，同 8.1.1如果初始化列表中有变量，为初始化列表中的每个元素生成 IRreshape 初始化列表，同 8.1.1将初始化列表赋值给数组步骤 3.c 中，如果初始化列表中都是常量，可以采用 8.2.1 中的方法先声明一个临时全局常量数组 const_array，然后将该数组 memcpy 到局部数组：const_array.set_visibility(inkwell::GlobalVisibility::Hidden); const_array.set_linkage(inkwell::module::Linkage::Private); const_array.set_unnamed_addr(true); let bytes_to_copy = len * std::mem::size_of::<i32>(); builder.build_memcpy( ptr, 4, const_array.as_pointer_value(), 4, compiler.int_type.const_int(bytes_to_copy as u64, false) ).unwrap();例如，对于int main() { int d[2][3] = {1, 2, 3, {4}}; return 0; }会得到d = private unnamed_addr constant [2 x [3 x i32]] [[3 x i32] [i32 1, i32 2, i32 3], [3 x i32] [i32 4, i32 0, i32 0]] define i32 @main() { entry: %d = alloca [2 x [3 x i32]], align 4 call void @llvm.memcpy.p0.p0.i32(ptr align 4 %d, ptr align 4 @d, i32 24, i1 false) ret i32 0 }步骤 3.c 中，如果初始化列表中有变量，则先加载变量，然后赋值给数组。赋值的时候，需要先根据下标获得当前数组元素地址：for (i, v) in init.iter().enumerate() { // 计算数组当前元素下标 let mut index = vec![context.i32_type().const_zero()]; let mut e = i as u32; for d in dims.iter() { index.insert(1, context.i32_type().const_int((e % d).into(), false)); e /= d; } // 获得当前数组元素地址 let elemptr = unsafe { builder.build_in_bounds_gep(array_type, ptr, &index, &format!("elemptr{i}")) }; // 从初始化列表获得常量或变量 let elem = match v { Initializer::Const(c) => context.i32_type() .const_int(c.to_owned(), false) .as_basic_value_enum(), Initializer::Value(v) => v.to_owned(), _ => unreachable!(), }; // 赋值 builder.build_store(elemptr, elem); }例如，对于：int e = 1 int g[2] = {e, 2};生成的 IR 为：%e = alloca i32, align 4 store i32 1, ptr %e, align 4 %g = alloca [2 x i32], align 4 %e1 = load i32, ptr %e, align 4 %elemptr0 = getelementptr inbounds [2 x i32], ptr %g, i32 0, i32 0 store i32 %e1, ptr %elemptr0, align 4 %elemptr1 = getelementptr inbounds [2 x i32], ptr %g, i32 0, i32 1 store i32 2, ptr %elemptr1, align 4getelementptr 用来进行地址计算，非常类似于数组的索引和字段选择，但是又有点不同，它会需要一个额外的 0 索引，详见：经常被误解的 GetElementPtr(GEP) 指令一个完整例子的 LLVM IR：void f() { int e = 1; int g[2] = {e, 2}; return; } int main() { int d[2][3] = {1, 2, 3, {4}}; return 0; }; ModuleID = 'module' source_filename = "module" @d = private unnamed_addr constant [2 x [3 x i32]] [[3 x i32] [i32 1, i32 2, i32 3], [3 x i32] [i32 4, i32 0, i32 0]] define void @f() { entry: %e = alloca i32, align 4 store i32 1, ptr %e, align 4 %g = alloca [2 x i32], align 4 %e1 = load i32, ptr %e, align 4 %elemptr0 = getelementptr inbounds [2 x i32], ptr %g, i32 0, i32 0 store i32 %e1, ptr %elemptr0, align 4 %elemptr1 = getelementptr inbounds [2 x i32], ptr %g, i32 0, i32 1 store i32 2, ptr %elemptr1, align 4 ret void } define i32 @main() { entry: %d = alloca [2 x [3 x i32]], align 4 call void @llvm.memcpy.p0.p0.i32(ptr align 4 %d, ptr align 4 @d, i32 24, i1 false) ret i32 0 } ; Function Attrs: argmemonly nocallback nofree nounwind willreturn declare void @llvm.memcpy.p0.p0.i32(ptr noalias nocapture writeonly, ptr noalias nocapture readonly, i32, i1 immarg) #0 attributes #0 = { argmemonly nocallback nofree nounwind willreturn }8.3 数组参数例子：void f(int a[][3]) { return; } int main() { int arr[2][3]; f(arr); return 0; }在调用函数时，需要为 FuncCall 生成 IR，应先构造入参，当入参是数组时，需要获取数组首元素的地址：unsafe { builder.build_in_bounds_gep( array_type, ptr, vec![context.i32_type().const_zero(), context.i32_type().const_zero()].as_ref(), "array" ).as_basic_value_enum() }其中，array_type 是数组类型，ptr 是数组地址。例如，对于 int arr2，array_type 是 [2 x [3 x i32]]，生成方式为：let array_type = dims.iter() .fold( context.i32_type().as_basic_type_enum(), |acc, len| acc.array_type(len.to_owned()).as_basic_type_enum(), )ptr 是 builder.build_alloca() 时生成的地址。所以，将 int arr2 传给 f(arr) 时，会生成：%array = getelementptr inbounds [2 x [3 x i32]], ptr %arr, i32 0, i32 0在为函数定义 FuncDef 生成 IR 时，在将函数添加到 module 时，需要先为参数生成 IR，当参数是数组参数时，参数的类型为指针：let param_type = if param.dims.is_some() { BasicMetadataTypeEnum::from( context.i32_type().ptr_type(AddressSpace::default()) ) }在函数中，需要获取数组参数类型：let param_type = if let Some(ref dims) = param.dims { context.i32_type().ptr_type(AddressSpace::default()).as_basic_type_enum() }然后与之前非数组参数一样，为参数分配空间，加载参数：let ptr = builder.build_alloca(param_type, &param.id); let value = function.get_nth_param(idx as u32).unwrap(); builder.build_store(ptr, value);一个完整例子的 LLVM IR：void f(int a[][3]) { return; } int main() { int arr[2][3]; f(arr); return 0; }; ModuleID = 'module' source_filename = "module" define void @f(ptr %a1) { entry: %a = alloca ptr, align 8 store ptr %a1, ptr %a, align 8 ret void } define i32 @main() { entry: %arr = alloca [2 x [3 x i32]], align 4 %array = getelementptr inbounds [2 x [3 x i32]], ptr %arr, i32 0, i32 0 call void @f(ptr %array) ret i32 0 }8.4 访问数组8.4.1 访问非参数数组例子：int main() { int arr[2][3] = {1, 2, 3, {4}}; int b = arr[1][2]; return 0; }数组元素作为右值，先获取数组元素地址，然后加载到内存：let mut idx_vals = vec![context.i32_type().const_zero()]; idx_vals.extend(lval.indices .iter() .map(|expr| context.i32_type() .const_int(expr.eval(compiler).unwrap() as u64, false) ), ); builder.build_load( context.i32_type(), unsafe { builder.build_in_bounds_gep( array_type, ptr, idx_vals.as_ref(), "index_access" ) }, "array_item" )生成的 LLVM IR：; ModuleID = 'module' source_filename = "module" @arr = private unnamed_addr constant [2 x [3 x i32]] [[3 x i32] [i32 1, i32 2, i32 3], [3 x i32] [i32 4, i32 0, i32 0]] define i32 @main() { entry: %arr = alloca [2 x [3 x i32]], align 4 call void @llvm.memcpy.p0.p0.i32(ptr align 4 %arr, ptr align 4 @arr, i32 24, i1 false) %b = alloca i32, align 4 %index_access = getelementptr inbounds [2 x [3 x i32]], ptr %arr, i32 0, i32 1, i32 2 %array_item = load i32, ptr %index_access, align 4 store i32 %array_item, ptr %b, align 4 ret i32 0 } ; Function Attrs: argmemonly nocallback nofree nounwind willreturn declare void @llvm.memcpy.p0.p0.i32(ptr noalias nocapture writeonly, ptr noalias nocapture readonly, i32, i1 immarg) #0 attributes #0 = { argmemonly nocallback nofree nounwind willreturn }8.4.2 访问参数数组例子：void f(int a[][3]) { int b = a[1][2]; return; }参数数组元素作为右值，先获取数组元素地址，然后加载到内存：let idx_vals = lval.indices .iter() .map(|expr| context.i32_type() .const_int(expr.eval(compiler).unwrap() as u64, false) ).collect::<Vec<IntValue>>(); builder.build_load( context.i32_type(), unsafe { compiler.builder.build_in_bounds_gep( array_type, ptr, idx_vals.as_ref(), "index_access" ) }, "array_item" )想对于 8.4.1，只是下标有所不同，少了一个 0。一个完整例子的 LLVM IR：void f(int a[][3]) { int b = a[1][2]; return; }; ModuleID = 'module' source_filename = "module" define void @f(ptr %a1) { entry: %a = alloca ptr, align 8 store ptr %a1, ptr %a, align 8 %b = alloca i32, align 4 %index_access = getelementptr inbounds [3 x i32], ptr %a, i32 1, i32 2 %array_item = load i32, ptr %index_access, align 4 store i32 %array_item, ptr %b, align 4 ret void }8.5 修改数组8.5.1 修改非参数数组例子：int main() { int arr[2][3]; arr[1][2] = 5; return 0; }数组元素作为左值，需要先获取地址：let mut idx_vals = vec![context.i32_type().const_zero()]; idx_vals.extend(self.indices .iter() .map(|expr| context.i32_type() .const_int(expr.eval(compiler).unwrap() as u64, false) ), ); Ok(unsafe { builder.build_in_bounds_gep( array_type, ptr, idx_vals.as_ref(), "index_access" ).as_basic_value_enum() })生成的 LLVM IR：; ModuleID = 'module' source_filename = "module" define i32 @main() { entry: %arr = alloca [2 x [3 x i32]], align 4 %index_access = getelementptr inbounds [2 x [3 x i32]], ptr %arr, i32 0, i32 1, i32 2 store i32 5, ptr %index_access, align 4 ret i32 0 }8.5.2 修改参数数组例子：void f(int a[][3]) { a[1][2] = 3; return; }参数数组元素作为左值，需要先加载数组，然后获取数组元素地址：let ptr = builder.build_load( context.i32_type().ptr_type(AddressSpace::default()), ptr, "array_ptr" ).into_pointer_value(); let idx_vals = self.indices .iter() .map(|expr| context.i32_type() .const_int(expr.eval(compiler).unwrap() as u64, false) ).collect::<Vec<IntValue>>(); Ok(unsafe { builder.build_in_bounds_gep( array_type, ptr, idx_vals.as_ref(), "index_access" ).as_basic_value_enum() })相对于 8.5.1，只是多了第一行中的加载数组。生成的 LLVM IR：; ModuleID = 'module' source_filename = "module" define void @f(ptr %a1) { entry: %a = alloca ptr, align 8 store ptr %a1, ptr %a, align 8 %array_ptr = load ptr, ptr %a, align 8 %index_access = getelementptr inbounds [3 x i32], ptr %array_ptr, i32 1, i32 2 store i32 3, ptr %index_access, align 4 ret void }9 小技巧先大概明白生成的 LLVM IR 应该是什么样子，然后再使用 Inkwell 写出对应的 LLVM IR。如果不知道 LLVM IR 应该是什么样的，可以先写出 C 代码，然后用如下命令生成 LLVM IR：clang -emit-llvm -S your_code.c -o your_code.ll
本文跟着 LLVM Tutorial 教程完成，加上了一些注释。本文中的代码并非工程最佳实践。1 目标用 LLVM 实现一门简单的语言 Kaleidoscope，实现对如下代码的编译运行：# 斐波那契数列函数定义 def fib(x) if x < 3 then 1 else fib(x - 1) + fib(x - 2) fib(40) # 函数声明 extern sin(arg) extern cos(arg) extern atan2(arg1 arg2) # 声明后的函数可调用 atan2(sin(.4), cos(42))为方便，Kaleidoscope 只支持 float64 数据类型。2 词法分析 Lexer词法分析是把程序分割成一个个 Token 的过程。Token 包括 if、else、int 等关键字，age 等标识符，+、-、= 等操作符，以及数字、字符串变量等。2.1 Token 种类// The lexer returns tokens [0-255] if it is an unknown character, otherwise one // of these for known things. enum Token { TOKEN_EOF = -1, // commands TOKEN_DEF = -2, TOKEN_EXTERN = -3, // primary TOKEN_IDENTIFIER = -4, TOKEN_NUMBER = -5, }; // 如果当前 Token 是 TOKEN_IDENTIFIER，记录变量 static std::string g_identifier_str; // 如果当前 Token 是 TOKEN_NUMBER，记录数值 static double g_num_val; 2.2 识别 Token/// 返回从标准输入中解析出的 token // TOKEN_EOF: 'def' // TOKEN_EXTERN: 'extern' // TOKEN_IDENTIFIER: [a-zA-Z][a-zA-Z0-9]* // TOKEN_NUMBER: [0-9.]+ static int GetToken() { static int last_char = ' '; // 跳过空格 while (isspace(last_char)) last_char = getchar(); // 识别关键字或变量 [a-zA-Z][a-zA-Z0-9]* if (isalpha(last_char)) { g_identifier_str = last_char; while (isalnum((last_char = getchar()))) g_identifier_str += last_char; if (g_identifier_str == "def") return TOEKN_DEF; if (g_identifier_str == "extern") return TOKEN_EXTERN; return TOKEN_IDENTIFIER; } // 识别数字: [0-9.]+ if (isdigit(last_char) || last_char == '.') { std::string num_str; do { num_str += last_char; last_char = getchar(); } while (isdigit(last_char) || last_char == '.'); g_num_val = strtod(num_str.c_str(), nullptr); return TOKEN_NUMBER; } // 跳过注释 if (last_char == '#') { // Comment until end of line. do last_char = getchar(); while (last_char != EOF && last_char != '\n' && last_char != '\r'); if (last_char != EOF) return GetToken(); } // 识别文件结束 if (last_char == EOF) return TOEKN_EOF; // 未知，直接返回 ascii 码 int this_char = last_char; last_char = getchar(); return this_char; }3 语法分析 Parser语法分析是在词法分析的基础上识别出程序的语法结构，这个结构是树状的，称为抽象语法树（Abstract Syntax Tree，AST）。形成 AST 后，计算机就会比较容易处理，比如从根节点遍历整棵树就可以获得表达式的值。3.1 定义 AST 节点/// 所有表达式节点的基类 class ExprAST { public: virtual ~ExprAST() {} }; /// 数值表达式 class NumberExprAST : public ExprAST { double val_; public: NumberExprAST(double val) : val_(val) {} }; /// 变量表达式 class VariableExprAST : public ExprAST { std::string name_; public: VariableExprAST(const std::string &name) : name_(name) {} }; /// 二元运算表达式 class BinaryExprAST : public ExprAST { char opcode_; std::unique_ptr<ExprAST> lhs, rhs; public: BinaryExprAST(char opcode, std::unique_ptr<ExprAST> lhs, std::unique_ptr<ExprAST> rhs) : opcode_(opcode), lhs_(std::move(lhs)), rhs_(std::move(rhs)) {} }; /// 函数调用表达式 class CallExprAST : public ExprAST { std::string callee_; std::vector<std::unique_ptr<ExprAST>> args_; public: CallExprAST(const std::string &callee, std::vector<std::unique_ptr<ExprAST>> args) : callee_(callee), args_(std::move(args)) {} }; /// 函数接口 /// 包含函数名称，参数名称 class PrototypeAST { std::string name_; std::vector<std::string> args_; public: PrototypeAST(const std::string &name, std::vector<std::string> args) : name_(name), args_(std::move(args)) {} const std::string &name() const { return name_; } }; /// 函数表达式 class FunctionAST { std::unique_ptr<PrototypeAST> proto_; std::unique_ptr<ExprAST> body_; public: FunctionAST(std::unique_ptr<PrototypeAST> proto, std::unique_ptr<ExprAST> body) : proto_(std::move(proto)), body_(std::move(body)) {} };后面的章节中会讨论条件表达式。3.2 解析基本表达式为方便，定义一个 helper 函数：// parser 正在查看的 token static int g_cur_token; // 从 lexer 中读取下一个 token 并更新 g_cur_token static int NextToken() { return g_cur_token = GetToken(); }解析基本表达式：/// numberexpr ::= number // 解析数值，构造 NumberExprAST // 如果当前 token 是 TOKEN_NUMBER，获取数字变量并创建 NumberExprAST，然后将 lexer 前进到下一个 token static std::unique_ptr<ExprAST> ParseNumberExpr() { auto result = std::make_unique<NumberExprAST>(g_num_val); NextToken(); // consume the number return std::move(result); } /// parenexpr ::= '(' expression ')' // 解析括号表达式，构造 ExprAST // 如果当前 token 是 '('，获取括号里面的表达式 static std::unique_ptr<ExprAST> ParseParenExpr() { NextToken(); // eat (. auto expr = ParseExpression(); if (!expr) return nullptr; if (g_cur_token != ')') return LogError("expected ')'"); NextToken(); // eat ). return expr; } /// identifierexpr /// ::= identifier /// ::= identifier '(' expression* ')' // 解析变量，构造 VariableExprAST；或解析函数调用，构造 CallExprAST // 如果当前 token 是 TOEN_IDENTIFIER， // 会预读一个 token，根据其是否为 '(' 来决定当前 identifier 是变量还是函数调用 static std::unique_ptr<ExprAST> ParseIdentifierExpr() { std::string id_name = g_identifier_str; NextToken(); // eat identifier. if (g_cur_token != '(') // Simple variable ref. return std::make_unique<VariableExprAST>(id_name); // Call. NextToken(); // eat ( std::vector<std::unique_ptr<ExprAST>> args; if (g_cur_token != ')') { while (1) { if (auto arg = ParseExpression()) args.push_back(std::move(arg)); else return nullptr; if (g_cur_token == ')') break; if (g_cur_token != ',') return LogError("Expected ')' or ',' in argument list"); NextToken(); } } // Eat the ')'. NextToken(); return std::make_unique<CallExprAST>(id_name, std::move(args)); } /// primary /// ::= identifierexpr /// ::= numberexpr /// ::= parenexpr // 解析基本表达式 static std::unique_ptr<ExprAST> ParsePrimary() { switch (g_cur_token) { default: return LogError("unknown token when expecting an expression"); case TOKEN_IDENTIFIER: return ParseIdentifierExpr(); case TOKEN_NUMBER: return ParseNumberExpr(); case '(': return ParseParenExpr(); }3.3 解析二元表达式接下来解析二元表达式，Kaleidoscope 只支持 4 种二元操作符，优先级从低到高为：< + - *其中，+ 和 - 的优先级相同。定义优先级：/// BinopPrecedence - This holds the precedence for each binary operator that is /// defined. static std::map<char, int> g_binop_precedence; /// GetTokenPrecedence - Get the precedence of the pending binary operator token. static int GetTokenPrecedence() { if (!isascii(g_cur_token)) return -1; // Make sure it's a declared binop. int tok_prec = g_binop_precedence[g_cur_token]; if (tok_prec <= 0) return -1; return tok_prec; } int main() { // Install standard binary operators. // 1 is lowest precedence. g_binop_precedence['<'] = 10; g_binop_precedence['+'] = 20; g_binop_precedence['-'] = 20; g_binop_precedence['*'] = 40; // highest. ... }对于表达式 a+b+(c+d)*e*f+g，可看作是被二元操作符分隔的基本表达式流，先解析第一个基本表达式 a，然后解析剩余的 [+, b] [+, (c+d)] [*, e] [*, f] 和 [+, g]。即，复杂表达式可以抽象为一个 primaryexpr 跟着多个[binop, primaryexpr]二元组。/// expression /// ::= primary binoprhs static std::unique_ptr<ExprAST> ParseExpression() { auto lhs = ParsePrimary(); if (!lhs) return nullptr; return ParseBinOpRHS(0, std::move(lhs)); }对于表达式 a+b+(c+d)*e*f+g，a 会被传入 ParseBinOpRHS，且当前 token 是 +。ParseBinOpRHS 的第一个参数表示可被消耗的操作符的最小优先级，假如该值是 40，而当前被解析流是 [+, a]，该函数将不会消耗任何 token，因为 + 的优先级仅为 20，比 40 小。因为非法二元操作符的优先级是 -1，所以如果遇到一元表达式，该函数会直接返回的。/// binoprhs /// ::= ('+' primary)* static std::unique_ptr<ExprAST> ParseBinOpRHS(int min_precedence, std::unique_ptr<ExprAST> lhs) { // If this is a binop, find its precedence. while (true) { int tok_prec = GetTokenPrecedence(); // If this is a binop that binds at least as tightly as the current binop, // consume it, otherwise we are done. // 因为非法二元操作符的优先级是 -1，所以如果遇到一元表达式，该函数会直接返回的 if (tok_prec < min_precedence) return lhs; // Okay, we know this is a binop. int binop = g_cur_token; NextToken(); // eat binop // Parse the primary expression after the binary operator. // 解析括号表达式 auto rhs = ParsePrimary(); if (!rhs) return nullptr; // If BinOp binds less tightly with RHS than the operator after RHS, let // the pending operator take RHS as its LHS. // 有两种可能的解析方式 // (lhs binop rhs) binop unparsed // lhs binop (rhs binop unparsed) int next_prec = GetTokenPrecedence(); if (tok_prec < next_prec) { rhs = ParseBinOpRHS(tok_prec + 1, std::move(rhs)); if (!rhs) return nullptr; } // Merge lhs/rhs. lhs = std::make_unique<BinaryExprAST>(binop, std::move(lhs), std::move(rhs)); } }3.4 解析剩余部分解析函数原型：/// prototype /// ::= id '(' id* ')' static std::unique_ptr<PrototypeAST> ParsePrototype() { if (g_cur_token != TOKEN_IDENTIFIER) return LogErrorP("Expected function name in prototype"); std::string fn_name = g_identifier_str; NextToken(); if (g_cur_token != '(') return LogErrorP("Expected '(' in prototype"); // Read the list of argument names. std::vector<std::string> arg_names; while (NextToken() == TOKEN_IDENTIFIER) arg_names.push_back(g_dentifier_str); if (g_cur_token != ')') return LogErrorP("Expected ')' in prototype"); // success. NextToken(); // eat ')'. return std::make_unique<PrototypeAST>(fn_name, std::move(arg_names)); }解析函数：def + 函数原型 + 函数体，函数体是一个表达式。/// definition ::= 'def' prototype expression static std::unique_ptr<FunctionAST> ParseDefinition() { NextToken(); // eat def. auto proto = ParsePrototype(); if (!proto) return nullptr; if (auto expr = ParseExpression()) return std::make_unique<FunctionAST>(std::move(proto), std::move(expr)); return nullptr; }解析 extern 表达式：/// external ::= 'extern' prototype static std::unique_ptr<PrototypeAST> ParseExtern() { NextToken(); // eat extern. return ParsePrototype(); }为顶层代码实现匿名函数：/// toplevelexpr ::= expression static std::unique_ptr<FunctionAST> ParseTopLevelExpr() { if (auto expr = ParseExpression()) { // Make an anonymous proto. auto proto = std::make_unique<PrototypeAST>("", std::vector<std::string>()); return std::make_unique<FunctionAST>(std::move(proto), std::move(expr)); } return nullptr; }3.5 Driver/// top ::= definition | external | expression | ';' static void MainLoop() { while (1) { fprintf(stderr, "ready> "); switch (g_cur_token) { case TOKEN_EOF: return; case ';': // ignore top-level semicolons. NextToken(); break; case TOKEN_DEF: HandleDefinition(); break; case TOKEN_EXTERN: HandleExtern(); break; default: HandleTopLevelExpression(); break; } } }编译运行：# Compile $ clang++ -g -O3 toy.cpp `llvm-config --cxxflags` # Run $ ./a.out ready> def foo(x y) x+foo(y, 4.0); Parsed a function definition. ready> def foo(x y) x+y y; Parsed a function definition. Parsed a top-level expr ready> def foo(x y) x+y ); Parsed a function definition. Error: unknown token when expecting an expression ready> extern sin(a); ready> Parsed an extern ready> ^D4 语义分析语义分析是消除语义模糊，比如：数据类型不匹配是否要做自动转换？由于本文中涉及的数据类型都是 float64 类型，所以不涉及数据类型推导、转换等。如果一个代码块内部和外部有相同名称的变量，用哪个？同一个作用域内，不允许有两个相同名称的变量。语义分析还会生成一些属性信息，并标注在 AST 上。5 生成 LLVM IRIR 指中间表达方式，介于高级语言和汇编语言之间。与高级语言相比，丢弃了语法和语义特征，比如作用域、面向对象等；与汇编语言相比，不会有硬件相关的细节，比如目标机器架构、操作系统等。先 include 一些 LLVM 头文件并定义全局变量：#include "llvm/ADT/APFloat.h" #include "llvm/ADT/STLExtras.h" #include "llvm/IR/BasicBlock.h" #include "llvm/IR/Constants.h" #include "llvm/IR/DerivedTypes.h" #include "llvm/IR/Function.h" #include "llvm/IR/IRBuilder.h" #include "llvm/IR/LLVMContext.h" #include "llvm/IR/LegacyPassManager.h" #include "llvm/IR/Module.h" #include "llvm/IR/Type.h" #include "llvm/IR/Verifier.h" #include "llvm/Support/TargetSelect.h" #include "llvm/Target/TargetMachine.h" #include "llvm/Transforms/InstCombine/InstCombine.h" #include "llvm/Transforms/Scalar.h" #include "llvm/Transforms/Scalar/GVN.h" // 记录一些全局数据，比如各模块中用到的类型和常量 static std::unique_ptr<LLVMContext> g_llvm_context; // 一个文件就是一个模块 // 模块中包含函数、全局变量 static std::unique_ptr<Module> g_llvm_module; // 用于创建 LLVM 指令 static std::unique_ptr<IRBuilder<>> g_ir_builder; // 用于记录函数的变量参数 static std::map<std::string, Value *> g_named_values;5.1 添加 Codegen()在每个 AST 类中添加 Codegen()，用于生成 LLVM IR。/// ExprAST - Base class for all expression nodes. class ExprAST { public: virtual ~ExprAST() {} virtual Value *Codegen() = 0; }; /// NumberExprAST - Expression class for numeric literals like "1.0". class NumberExprAST : public ExprAST { double val_; public: NumberExprAST(double Val) : val_(val) {} virtual Value *Codegen(); }; ...也可以通过 visitor 模式生成 LLVM IR，本文并非工程最佳实践，添加 Codegen() 会更简单一些。Codegen() 会返回 LLVM Value，Value 用来表示 SSA（Static Single Assignment）值，一个变量只能被定义一次，然后多次使用，便于代码优化。5.2 实现 Codegen()实现 NumberExprAST 的 Codegen()：Value *NumberExprAST::Codegen() { return ConstantFP::get(g_llvm_context, APFloat(val_)); }在 LLVM IR 中，所有常量都是唯一且共享的，所以使用 get 而不是 new/create。实现 VariableExprAST 的 Codegen()：Value *VariableExprAST::Codegen() { // Look this variable up in the function. Value *v = g_named_values[name_]; if (!v) LogErrorV("Unknown variable name"); return v; } 目前 g_named_values 中仅保存函数参数，在生成的函数的 IR 时，会生成参数的 IR，并存放到 g_named_values 中，所以这里仅仅是获取。后面 g_named_values 中会保存循环中的变量和本地变量。实现 BinaryExprAST 的 Codegen()：Value *BinaryExprAST::Codegen() { Value *l = lhs_->Codegen(); Value *r = rhs_->Codegen(); if (!l || !r) return nullptr; switch (opcode_) { case '+': return Builder.CreateFAdd(l, r, "addtmp"); case '-': return Builder.CreateFSub(l, r, "subtmp"); case '*': return Builder.CreateFMul(l, r, "multmp"); case '<': l = Builder.CreateFCmpULT(l, r, "cmptmp"); // Convert bool 0/1 to double 0.0 or 1.0 return Builder.CreateUIToFP(l, Type::GetDoubleTypepe(*g_llvm_context), "booltmp"); default: return LogErrorV("invalid binary operator"); } }递归地生成左边表达式是 IR 和右边表达式的 IR，然后计算结果。Builder.CreateFAdd() 用来插入加法的 IR 指令，第三个参数表示名称，使得生成的 IR 便于阅读。LLVM 指令要求比较严格，比如，加法指令的 L 和 R 的数据类型必须相同，结果类型必须和操作数类型匹配。另外，CreateFCmpULT() 返回 bool 型，但 Kaleidoscope 中的数据类型都为 float64，所以需要通过 CreateUIToFP() 转换一下。实现 CallExprAST 的 Codegen()：Value *CallExprAST::Codegen() { // Look up the name in the global module table. // LLVM Module 中存放了所有的函数 Function *callee = g_llvm_module->getFunction(callee_); if (!callee) return LogErrorV("Unknown function referenced"); // If argument mismatch error. if (callee->arg_size() != args.size()) return LogErrorV("Incorrect # arguments passed"); std::vector<Value *> args_v; for (unsigned i = 0, e = args_.size(); i != e; ++i) { args_v.push_back(args_[i]->Codegen()); if (!args_v.back()) return nullptr; } return g_ir_builder.CreateCall(callee, args_v, "calltmp"); } 实现 PrototypeAST 的 Codegen()：// 返回的是 Function* 而非 Value* Function *PrototypeAST::Codegen() { // Make the function type: double(double, double) etc. std::vector<Type*> doubles(args_.size(), Type::GetDoubleTypepe(*g_llvm_context)); // 在 LLVM 中，Types 是唯一的，所以使用 get 而非 new // false 表示参数个数是固定的 FunctionType *f_type = FunctionType::get(Type::GetDoubleTypepe(*g_llvm_context), doubles, false); // 生成 IR // 第 2 个参数表明函数可能定义在当前模块外，或者本函数可被其它模块调用 // 第 4 个参数表明了要插入到哪个模块 Function *fun = Function::Create(f_type, Function::ExternalLinkage, name_, g_llvm_module.get()); // Set names for all arguments. // 本步骤不是必须的，可以使得生成的 IR 更具可读性 // 也使得后续的代码可以直接通过参数名称引用参数，而避免遍历 PrototypeAST unsigned idx = 0; for (auto &arg : fun->args()) arg.setName(args[Idx++]); return fun; }实现 FunctionAST 的 Codegen()：会加上函数体Function *FunctionAST::Codegen() { // First, check for an existing function from a previous 'extern' declaration. // 可能会有 extern 声明 Function *function = g_llvm_module->getFunction(proto_->name()); if (!function) function = proto_->Codegen(); if (!function) return nullptr; if (!function->empty()) return (Function*)LogErrorV("Function cannot be redefined."); // Create a new basic block to start insertion into. // 创建一个名称为 entry 的基本块，会被插入到 function // llvm block 用于定义control flow graph, 但我们暂不实现 control flow，创建一个单独的 block 即可 BasicBlock *bb = BasicBlock::Create(g_llvm_context, "entry", function); // 设置指令插入点，即后面的指令会被插入到 bb Builder.SetInsertPoint(bb); // Record the function arguments in the g_named_values map. // g_named_values 会被 VariableExprAST 访问 g_named_values.clear(); for (auto &arg : function->args()) g_named_values[arg.getName()] = &arg; // 会将计算表达式的 IR 发送到 entry block 中，并返回计算结果 if (Value *ret_val = body_->Codegen()) { // Finish off the function. // 利用计算结果创建返回值 g_ir_builder.CreateRet(ret_val); // Validate the generated code, checking for consistency. verifyFunction(*function); return function; } // Error reading body, remove function. function->eraseFromParent(); return nullptr; }该代码目前还存在一个问题，如果 FunctionAST::Codegen() 发现了一个已经存在的 IR，并不会检查其签名。5.3 运行ready> 4+5; Read top-level expression: define double @0() { entry: ret double 9.000000e+00 } ready> def foo(a b) a*a + 2*a*b + b*b; Read function definition: define double @foo(double %a, double %b) { entry: %multmp = fmul double %a, %a %multmp1 = fmul double 2.000000e+00, %a %multmp2 = fmul double %multmp1, %b %addtmp = fadd double %multmp, %multmp2 %multmp3 = fmul double %b, %b %addtmp4 = fadd double %addtmp, %multmp3 ret double %addtmp4 }6 优化IRBuilder 生成的 IR 如下：ready> def test(x) 1+2+x; Read function definition: define double @test(double %x) { entry: %addtmp = fadd double 3.000000e+00, %x ret double %addtmp }可以看到，自动进行了常量折叠。但是如果想对如下 IR 优化，还需要引入 LLVM 中的 pass。ready> def test(x) (1+2+x)*(x+(1+2)); ready> Read function definition: define double @test(double %x) { entry: %addtmp = fadd double 3.000000e+00, %x %addtmp1 = fadd double %x, 3.000000e+00 %multmp = fmul double %addtmp, %addtmp1 ret double %multmp }可以选择是否启用 pass，并调整 pass 的顺序。LLVM 既提供针对整个 Module 的 pass，也提供针对单个函数的 pass。本文中，对每个函数单独优化，初始化 pass 管理器：static std::unique_ptr<legacy::FunctionPassManager> g_fpm; void InitializeModuleAndPassManager(void) { // Open a new module. g_llvm_module = std::make_unique<Module>("my cool jit", g_llvm_context); // Create a new pass manager attached to it. g_fpm = std::make_unique<legacy::FunctionPassManager>(g_llvm_module.get()); // Do simple "peephole" optimizations and bit-twiddling optzns. g_fpm->add(createInstructionCombiningPass()); // Reassociate expressions. g_fpm->add(createReassociatePass()); // Eliminate Common SubExpressions. g_fpm->add(createGVNPass()); // Simplify the control flow graph (deleting unreachable blocks, etc). g_fpm->add(createCFGSimplificationPass()); g_fpm->doInitialization(); }在 FunctionAST::Codegen() 中添加如下代码：if (Value *ret_val = body_->Codegen()) { // Finish off the function. g_ir_builder.CreateRet(ret_val); // Validate the generated code, checking for consistency. verifyFunction(*function); // Optimize the function. g_fpm->run(*function); return function; }测试并查看效果：ready> def test(x) (1+2+x)*(x+(1+2)); ready> Read function definition: define double @test(double %x) { entry: %addtmp = fadd double %x, 3.000000e+00 %multmp = fmul double %addtmp, %addtmp ret double %multmp }7 添加 JIT提前编译（AOT）：编译成可执行文件后，再执行。即时编译（JIT）：在需要运行某段代码的时候，再编译。Java、JavaScript 等语言都是通过即时编译提高性能的JIT 原理：动态申请内存，加载目标代码到内存，并赋予内存可执行权限。定义 JIT 的全局变量，并通过 InitializeNativeTarget* 函数初始化环境。#include "KaleidoscopeJIT.h" static std::unique_ptr<KaleidoscopeJIT> g_jit; ... int main() { InitializeNativeTarget(); InitializeNativeTargetAsmPrinter(); InitializeNativeTargetAsmParser(); g_jit = std::make_unique<KaleidoscopeJIT>(); ... return 0; }其中，KaleidoscopeJIT.h 是从 LLVM 的源码 llvm-src/examples/Kaleidoscope/include/KaleidoscopeJIT.h 中拷贝过来的。为 JIT 设置数据布局：void InitializeModuleAndPassManager(void) { // Open a new module. g_llvm_module = std::make_unique<Module>("my cool jit", g_llvm_context); g_llvm_module->setDataLayout(g_jit->getTargetMachine().createDataLayout()); // Create a new pass manager attached to it. g_fpm = std::make_unique<legacy::FunctionPassManager>(g_llvm_module.get()); ...修改顶层解析函数：static void HandleTopLevelExpression() { // Evaluate a top-level expression into an anonymous function. if (auto fn_ast = ParseTopLevelExpr()) { if (fn_ast->Codegen()) { // 顶层函数 Codegen 后，将包含顶层函数的模块添加到 JIT // addModule 会触发模块中所有函数的 Codegen，并返回一个句柄 handle // 后续可以通过 handle 删除该模块 auto handle = g_jit->addModule(std::move(g_llvm_module)); // 一旦模块被添加到JIT中，就不能再对其进行修改 // 因此我们还通过调用InitializeModuleAndPassManager（）打开一个新模块来保存后续代码。 InitializeModuleAndPassManager(); // 通过顶层函数的名称搜索其符号 auto expr_symbol = g_jit->findSymbol("__anon_expr"); assert(expr_symbol && "Function not found"); // 获取符号地址，强制转换为函数指针 (double (*)())（无参数，并返回一个 double） double (*fp)() = (double (*)())(intptr_t)expr_symbol.getAddress(); fprintf(stderr, "Evaluated to %f\n", fp()); // Delete the anonymous expression module from the JIT. g_jit->removeModule(handle); }运行：ready> def testfunc(x y) x + y*2; Read function definition: define double @testfunc(double %x, double %y) { entry: %multmp = fmul double %y, 2.000000e+00 %addtmp = fadd double %multmp, %x ret double %addtmp } ready> testfunc(4, 10); Read top-level expression: define double @1() { entry: %calltmp = call double @testfunc(double 4.000000e+00, double 1.000000e+01) ret double %calltmp } Evaluated to 24.000000 ready> testfunc(5, 10); ready> LLVM ERROR: Program used external function 'testfunc' which could not be resolved!可以看到存在一个问题，所有函数都在同一个模块中，当模块被删除并释放后，函数定义也随之被删除。最简单的解决方式是将顶层函数和其它函数定义分别放在不同的模块中，这样即时顶层函数所在模块被删掉，也不会影响到其它函数。我们也可以更进一步，将每个函数都放在自己的模块中，这样函数就可以被多次添加到 JIT 中了。当我们在 JIT 中查找函数符号时，总是会返回被最新定义的：ready> def foo(x) x + 1; Read function definition: define double @foo(double %x) { entry: %addtmp = fadd double %x, 1.000000e+00 ret double %addtmp } ready> foo(2); Evaluated to 3.000000 ready> def foo(x) x + 2; define double @foo(double %x) { entry: %addtmp = fadd double %x, 2.000000e+00 ret double %addtmp } ready> foo(2); Evaluated to 4.000000在每个新打开的模块中重新生成函数定义：static std::unique_ptr<KaleidoscopeJIT> g_jit; // 存放函数的最新定义 static std::map<std::string, std::unique_ptr<PrototypeAST>> g_function_protos; ... Function *GetFunction(std::string Name) { // 首先，在模块中搜寻函数定义 if (auto *f = g_llvm_module->getFunction(Name)) return f; // 如果没有找到，就根据 g_function_protos 新生成定义 auto fn = g_function_protos.find(Name); if (fn != g_function_protos.end()) return fn->second->Codegen(); // If no existing prototype exists, return null. return nullptr; } ... Value *CallExprAST::Codegen() { // Look up the name in the global module table. // 替换 g_llvm_module->getFunction() Function *callee = GetFunction(Callee); ... Function *FunctionAST::Codegen() { // Transfer ownership of the prototype to the g_function_protos map, but keep a // reference to it for use below. auto &proto = *proto_; // 先更新 g_function_protos，然后再调用 getFunction g_function_protos[proto_->name()] = std::move(proto_); Function *function = GetFunction(proto.name()); if (!function) return nullptr;还需要更新 HandleDefinition 和 HandleExtern：static void HandleDefinition() { if (auto fn_ast = ParseDefinition()) { if (auto *fn_ir = fn_ast->Codegen()) { fprintf(stderr, "Read function definition:"); fn_ir->print(errs()); fprintf(stderr, "\n"); // 将最新定义的函数添加到 JIT g_jit->addModule(std::move(g_llvm_module)); // 打开新模块 InitializeModuleAndPassManager(); } } else { // Skip token for error recovery. NextToken(); } } static void HandleExtern() { if (auto proto_ast = ParseExtern()) { if (auto *fn_ir = proto_ast->Codegen()) { fprintf(stderr, "Read extern: "); fn_ir->print(errs()); fprintf(stderr, "\n"); // 更新 g_function_protos g_function_protos[proto_ast->name()] = std::move(proto_ast); } } else { // Skip token for error recovery. NextToken(); } }再次运行：ready> def foo(x) x + 1; ready> foo(2); Evaluated to 3.000000 ready> def foo(x) x + 2; ready> foo(2); Evaluated to 4.0000008 控制流8.1 支持 If/Then/Else在 lexer 中支持新的 token：// control TOKEN_IF = -6, TOKEN_then_ = -7, TOKEN_else_ = -8,识别新 token：... if (g_identifier_str == "if") return TOKEN_IF; if (g_identifier_str == "then") return TOKEN_THEN; if (g_identifier_str == "else") return TOKEN_ELSE;添加新的 AST 节点：/// IfExprAST - Expression class for if/then/else. class IfExprAST : public ExprAST { std::unique_ptr<ExprAST> cond_, then_, else_; public: IfExprAST(std::unique_ptr<ExprAST> cond, std::unique_ptr<ExprAST> then, std::unique_ptr<ExprAST> else) : cond_(std::move(cond)), then_(std::move(then)), else_(std::move(else)) {} Value *Codegen() override; };定义新的解析函数：/// ifexpr ::= 'if' expression 'then' expression 'else' expression static std::unique_ptr<ExprAST> ParseIfExpr() { NextToken(); // eat the if. // condition. auto cond = ParseExpression(); if (!cond) return nullptr; if (g_cur_token != TOKEN_THEN) return LogError("expected then"); NextToken(); // eat the then auto then_expr = ParseExpression(); if (!then_expr) return nullptr; if (g_cur_token != TOKEN_ELSE) return LogError("expected else"); NextToken(); auto else_expr = ParseExpression(); if (!else) return nullptr; return std::make_unique<IfExprAST>(std::move(cond), std::move(then_expr), std::move(else_expr)); }修改基本表达式的解析：static std::unique_ptr<ExprAST> ParsePrimary() { switch (g_cur_token) { default: return LogError("unknown token when expecting an expression"); case TOKEN_IDENTIFIER: return ParseIdentifierExpr(); case TOKEN_NUMBER: return ParseNumberExpr(); case '(': return ParseParenExpr(); case TOKEN_IF: return ParseIfExpr(); } }生成 IR：Value *IfExprAST::Codegen() { Value *cond_v = cond_->Codegen(); if (!cond_v) return nullptr; // Convert condition to a bool by comparing non-equal to 0.0. // 创建fcmp one指令, cond_value = (cond_value != 0.0) cond_v = g_ir_builder.CreateFCmpONE( cond_v, ConstantFP::get(g_llvm_context, APFloat(0.0)), "ifcond"); // 获取要插入指令的函数 Function *function = g_ir_builder.GetInsertBlock()->getParent(); // Create blocks for the then and else cases. Insert the 'then' block at the // end of the function. // 创建 3 个 block，并将 then block 插入到函数中 // 另外两个 block 还没有被插入到函数中，因为后面要先为 then_bb 生成指令 BasicBlock *then_bb = BasicBlock::Create(*g_llvm_context, "then", function); BasicBlock *else_bb = BasicBlock::Create(*g_llvm_context, "else"); BasicBlock *merge_bb = BasicBlock::Create(*g_llvm_context, "ifcond"); // 创建条件跳转指令，cond_v 是 1 的时候跳转到 then_bb，0 的时候跳转到 else_bb Builder.CreateCondBr(cond_v, then_bb, else_bb); // ---------------------- Emit then value. // 将指令插入点移到 then_bb g_ir_builder.SetInsertPoint(then_bb); Value *then_v = then_->Codegen(); if (!then_v) return nullptr; // 为了结束 then_bb，创建了一个到 merge_bb 的无条件跳转指令 g_ir_builder.CreateBr(merge_bb); // Codegen of 'Then' can change the current block, update ThenBB for the PHI. // 更新 ThenBB，因为 ThenBB 可能已经改变了 Builder 要插入指令的 block // 比如内部可能会有 if/then/else，而我们需要获取最终有结果的 block then_bb = g_ir_builder.GetInsertBlock(); // ----------------------- Emit else block. // 将 ElseBB 添加到函数中 function->getBasicBlockList().push_back(else_bb); g_ir_builder.SetInsertPoint(else_bb); Value *else_v = else_->Codegen(); if (!else_v) return nullptr; g_ir_builder.CreateBr(MergeBB); // Codegen of 'else_' can change the current block, update else_bb for the PHI. else_bb = g_ir_builder.GetInsertBlock(); // ------------------------ Emit merge block. function->getBasicBlockList().push_back(merge_bb); g_ir_builder.SetInsertPoint(merge_bb); // 创建 PHI 指令：浮点型，2 个候选值 PHINode *pn = Builder.CreatePHI(Type::GetDoubleTypepe(g_llvm_context), 2, "iftmp"); pn->addIncoming(then_v, then_bb); // 如果是来自 then_bb 的跳转，采用 then_v pn->addIncoming(else_v, else_bb); // 如果是来自 else_bb 的跳转，采用 else_v return pn; }8.2 支持 for 循环表达式接下来支持 for 表达式：extern putchard(char); def printstar(n) for i = 1, i < n, 1.0 in putchard(42); # ascii 42 = '*' # print 100 '*' characters printstar(100);扩展 lexer：... in enum Token ... TOKEN_FOR = -9, TOKEN_IN = -10, ... in GetToken ... if (g_identifier_str == "for") return TOKEN_FOR; if (g_identifier_str == "in") return TOKEN_IN; return TOKEN_IDENTIFIER;扩展 AST：/// ForExprAST - Expression class for for/in. class ForExprAST : public ExprAST { std::string var_name_; std::unique_ptr<ExprAST> start_, end_, step_, body_; public: ForExprAST(const std::string &var_name, std::unique_ptr<ExprAST> start, std::unique_ptr<ExprAST> end, std::unique_ptr<ExprAST> step, std::unique_ptr<ExprAST> body;) : var_name_(var_name), start_(std::move(start)), end_(std::move(end)), step_(std::move(step)), body_(std::move(body)) {} Value *Codegen() override; };扩展 Parser：/// forexpr ::= 'for' identifier '=' expr ',' expr (',' expr)? 'in' expression static std::unique_ptr<ExprAST> ParseForExpr() { NextToken(); // eat the for. if (g_cur_token != TOKEN_IDENTIFIER) return LogError("expected identifier after for"); std::string identifier_name = g_identifier_str; NextToken(); // eat identifier. if (g_cur_token != '=') return LogError("expected '=' after for"); NextToken(); // eat '='. auto start = ParseExpression(); if (!start) return nullptr; if (g_cur_token != ',') return LogError("expected ',' after for start_ value"); NextToken(); auto end = ParseExpression(); if (!end) return nullptr; // The step value is optional. std::unique_ptr<ExprAST> step; if (g_cur_token == ',') { NextToken(); step = ParseExpression(); if (!step) return nullptr; } if (g_cur_token != TOKEN_IN) return LogError("expected 'in' after for"); NextToken(); // eat 'in'. auto body = ParseExpression(); if (!body) return nullptr; return std::make_unique<ForExprAST>(identifier_name, std::move(start), std::move(end), std::move(step), std::move(body)); }再次更新对基本表达式的解析：static std::unique_ptr<ExprAST> ParsePrimary() { switch (g_cur_token) { ... case TOKEN_FOR: return ParseForExpr(); } }生成 IR：// Output for-loop as: // var = alloca double // ... // start = startexpr // store start -> var // goto loop // loop: // ... // bodyexpr // ... // loopend: // step = stepexpr // endcond = endexpr // // curvar = load var // nextvar = curvar + step // store nextvar -> var // br endcond, loop, endloop // outloop: Value *ForExprAST::Codegen() { // Emit the start code first, without 'variable' in scope. Value *start_val = start_->Codegen(); if (!start_val) return nullptr; // Make the new basic block for the loop header, inserting after current // block. Function *function = g_ir_builder->GetInsertBlock()->getParent(); // 获得当前 block BasicBlock *preheader_bb = g_ir_builder->GetInsertBlock(); // 新增 loop_bb BasicBlock *loop_bb = BasicBlock::Create(g_llvm_context, "loop", function); // Insert an explicit fall through from the current block to the LoopBB. // 添加从当前 block 到 loop_bb 的跳转指令 g_ir_builder.CreateBr(loop_bb); // Start insertion in loop_bb. // 开始在 loop_bb 内增加指令 g_ir_builder.SetInsertPoint(loop_bb); // Start the PHI node with an entry for Start. // 新增 PHI 指令 PHINode *variable = Builder.CreatePHI(Type::GetDoubleTypepe(g_llvm_context), 2, var_name_.c_str()) // 如果是来自 preheader_bb 的跳转，则取 start_val 的值 variable->addIncoming(start_val, preheader_bb); // Within the loop, the variable is defined equal to the PHI node. If it // shadows an existing variable, we have to restore it, so save it now. // 防止 loop 中的变量覆盖已有的同名变量 Value *old_val = g_named_values[var_name_]; g_named_values[var_name_] = variable; // Emit the body of the loop. // This, like any other expr, can change the // current BB. Note that we ignore the value computed by the body, but don't // allow an error. // body 可能会用到刚刚更新到 g_named_values 中的 loop 变量 if (!body_->Codegen()) return nullptr; // Emit the step value. Value *step_val = nullptr; if (step_) { step_val = step_->Codegen(); if (!step_val) return nullptr; } else { // If not specified, use 1.0. step_val = ConstantFP::get(g_llvm_context, APFloat(1.0)); } // 生成 body 后，需要计算下次循环中的变量值 Value *next_var = g_ir_builder.CreateFAdd(variable, step_val, "nextvar"); // Compute the end condition. Value *end_cond = end_->Codegen(); if (!end_ond) return nullptr; // Convert condition to a bool by comparing non-equal to 0.0. end_cond = g_ir_builder.CreateFCmpONE( end_cond, ConstantFP::get(g_llvm_context, APFloat(0.0)), "loopcond"); // Create the "after loop" block and insert it. BasicBlock *loop_end_bb = g_ir_builder.GetInsertBlock(); BasicBlock *after_bb = BasicBlock::Create(g_llvm_context, "afterloop", function); // Insert the conditional branch into the end of loop_end_bb. // 创建条件跳转指令，决定是否要退出循环 g_ir_builder.CreateCondBr(end_cond, loop_bb, after_bb); // Any new code will be inserted in after_bb. // 后续的指令会插入到 after_bb 中 g_ir_builder.SetInsertPoint(after_bb); // Add a new entry to the PHI node for the backedge. // 如果是再次循环，则取 next_var 值 variable->addIncoming(next_var, loop_end_bb); // Restore the unshadowed variable. // loop 中的变量只能在 loop 作用域内使用 if (old_val) g_g_named_values[var_name_] = old_val; else g_named_values.erase(var_name_); // for expr always returns 0.0. return Constant::getNullValue(Type::GetDoubleTypepe(g_llvm_context)); }可以看到，loop 中也用到了 PHI 指令，如果是第一次循环，则循环变量取 StartVal 值；否则，取 NextVal 值。编译运行：# Compile clang++ -g toy.cpp `llvm-config --cxxflags --ldflags --system-libs --libs core orcjit native` -O3 -o toy # Run ./toy9 用户自定义运算符我们将允许用户新增不存在的运算符，比如：# 定义一元运算符 ! def unary!(v) if v then 0 else 1; # 定义二元运算符 >，优先级为 10 def binary> 10 (LHS RHS) RHS < LHS; # Binary "logical or", (note that it does not "short circuit") # 定义二元运算符 |，优先级为 5 def binary| 5 (LHS RHS) if LHS then 1 else if RHS then 1 else 0; # Define = with slightly lower precedence than relationals. # 定义二元运算符 =，优先级为 9 def binary= 9 (LHS RHS) !(LHS < RHS | LHS > RHS);9.1 自定义二元运算符扩展 Lexer：enum Token { ... // operators TOKEN_BINARY = -11, TOKEN_UNARY = -12, }; ... static int GetToken() { ... if (g_identifier_str == "binary") return TOKEN_BINARY; if (g_identifier_str == "unary") return TOKEN_UNARY; return TOKEN_IDENTIFIER; }新增的二元操作符会被视为一个函数，所以不需要新增 AST 节点，只需扩展 PrototypeAST 节点即可：/// PrototypeAST - This class represents the "prototype" for a function, /// which captures its argument names as well as if it is an operator. class PrototypeAST { std::string name_; std::vector<std::string> args_; bool is_operator_; // 是否为操作符 unsigned precedence_; // 二元操作符的优先级 public: PrototypeAST(const std::string &name, std::vector<std::string> args_, bool is_operator = false, unsigned prec = 0) : name_(name), args_(std::move(args)), is_operator_(is_operator), precedence_(prec) {} Function *Codegen(); const std::string &name() const { return name_; } bool IsUnaryOpcode() const { return is_operator_ && args_.size() == 1; } bool IsBinaryOpcode() const { return is_operator_ && args_.size() == 2; } char operator_name() const { assert(IsUnaryOpcode() || IsBinaryOpcode()); return name_[name_.size() - 1]; } unsigned binary_precedence() const { return precedence_; } };修改 Parser：/// prototype /// ::= id '(' id* ')' /// ::= binary LETTER number? (id, id) static std::unique_ptr<PrototypeAST> ParsePrototype() { std::string fn_name; unsigned kind = 0; // 0 = identifier, 1 = unary, 2 = binary. unsigned binary_precedence = 30; switch (g_cur_token) { default: return LogErrorP("Expected function name in prototype"); case TOKEN_IDENTIFIER: fn_name = g_identifier_str; kind = 0; NextToken(); break; // 解析二元操作符名称和优先级 case TOKEN_BINARY: NextToken(); if (!isascii(g_cur_token)) return LogErrorP("Expected binary operator"); fn_name = "binary"; fn_name += (char)g_cur_token; kind = 2; NextToken(); // Read the precedence if present. if (g_cur_token == TOKEN_NUMBER) { if (g_num_val < 1 || g_num_val > 100) return LogErrorP("Invalid precedence: must be 1..100"); binary_precedence = (unsigned)g_num_val; NextToken(); } break; } if (g_cur_token != '(') return LogErrorP("Expected '(' in prototype"); std::vector<std::string> arg_names; while (NextToken() == TOKEN_IDENTIFIER) arg_names.push_back(g_identifier_str); if (g_cur_token != ')') return LogErrorP("Expected ')' in proto_type"); // success. NextToken(); // eat ')'. // Verify right number of names for operator. if (kind && arg_names.size() != kind) return LogErrorP("Invalid number of oprand_s for operator"); return std::make_unique<PrototypeAST>(fn_name, arg_names, kind != 0, binary_precedence); }生成 IR：Value *BinaryExprAST::Codegen() { Value *l = lhs_->Codegen(); Value *r = rhs_->Codegen(); if (!l || !r) return nullptr; switch (opcode_) { case '+': return g_ir_builder->CreateFAdd(l, r, "addtmp"); case '-': return g_ir_builder->CreateFSub(l, r, "subtmp"); case '*': return g_ir_builder->CreateFMul(l, r, "multmp"); case '<': l = g_ir_builder->CreateFCmpULT(l, r, "cmptmp"); // Convert bool 0/1 to double 0.0 or 1.0 return g_ir_builder->CreateUIToFP(l, Type::GetDoubleTypepe(*g_llvm_context), "booltmp"); default: break; } // If it wasn't a builtin binary operator, it must be a user defined one. Emit // a call to it. Function *f = GetFunction(std::string("binary") + opcode_); assert(f && "binary operator not found!"); Value *opcodes[] = {l, r}; return g_ir_builder->CreateCall(f, opcodes, "binopcode"); }顶层函数的 IR：Function *FunctionAST::Codegen() { // Transfer ownership of the prototype to the g_function_protos map, but keep a // reference to it for use below. auto &proto = *proto_; g_function_protos[proto_->name()] = std::move(proto_); Function *function = GetFunction(proto.name()); if (!function) return nullptr; // If this is an operator, install it. if (P.IsBinaryOp()) // 注册优先级，为后续 Codegen 作准备 g_binopcode_precedence[proto.operator_name()] = proto.binary_precedence(); // Create a new basic block to start insertion into. BasicBlock *bb = BasicBlock::Create(*g_llvm_context, "entry", function); ...9.2 自定义一元运算符支持自定义二元操作符只是扩展了已有框架，而支持一元操作符会更具挑战。添加 AST 节点：/// UnaryExprAST - Expression class for a unary operator. class UnaryExprAST : public ExprAST { char opcode_; std::unique_ptr<ExprAST> operand_; public: UnaryExprAST(char opcode, std::unique_ptr<ExprAST> oprand) : opcode_(opcode), oprand_(std::move(oprand)) {} Value *Codegen() override; };添加 Parser：/// unary /// ::= primary /// ::= '!' unary static std::unique_ptr<ExprAST> ParseUnary() { // If the current token is not an operator, it must be a primary expr. if (!isascii(g_cur_token) || g_cur_token == '(' || g_cur_token == ',') return ParsePrimary(); // If this is a unary operator, read it. int opcode = g_cur_token; NextToken(); if (auto operand = ParseUnary()) return std::make_unique<UnaryExprAST>(opcode, std::move(operand)); return nullptr; }以上代码先处理一元运算符，然后将剩余部分看作另外一个一元运算表达式，这样的话就能处理有多个一元运算符的情况了，比如 !!x。接下来，需要想办法让 ParseUnary 被调用到。可以将调用 ParsePrimary 的地方替换为调用 ParseUnary：/// binoprhs /// ::= ('+' unary)* static std::unique_ptr<ExprAST> ParseBinOpRHS(int min_expr_prec, std::unique_ptr<ExprAST> lhs) { ... // Parse the unary expression after the binary operator. auto rhs = ParseUnary(); if (!rhs) return nullptr; ... } /// expression /// ::= unary binoprhs static std::unique_ptr<ExprAST> ParseExpression() { auto lhs = ParseUnary(); if (!lhs) return nullptr; return ParseBinOpRHS(0, std::move(lhs)); }扩展对 Prototype 的解析：/// prototype /// ::= id '(' id* ')' /// ::= binary LETTER number? (id, id) /// ::= unary LETTER (id) static std::unique_ptr<PrototypeAST> ParsePrototype() { std::string fn_name; unsigned kind = 0; // 0 = identifier, 1 = unary, 2 = binary. unsigned binary_precedence = 30; switch (g_cur_token) { default: return LogErrorP("Expected function name in prototype"); case TOKEN_IDENTIFIER: fn_name = g_identifier_str; kind = 0; NextToken(); break; case TOKEN_UNARY: NextToken(); if (!isascii(g_cur_token)) return LogErrorP("Expected unary operator"); fn_name = "unary"; fn_name += (char)g_cur_token; kind = 1; NextToken(); break; case TOKEN_BINARY: ...生成 IR：Value *UnaryExprAST::Codegen() { Value *oprand_v = oprand_->Codegen(); if (!oprand_v) return nullptr; Function *f = GetFunction(std::string("unary") + opcode_); if (!f) return LogErrorV("Unknown unary operator"); g_ir_builder->CreateCall(f, oprand_v, "unopcode"); } 10 可变变量接下来将支持如下两个功能：通过等号给变量赋值。定义新变量。比如支持如下示例：# Define ':' for sequencing: as a low-precedence operator that ignores operands # and just returns the RHS. def binary : 1 (x y) y; # Recursive fib, we could do this before. def fib(x) if (x < 3) then 1 else fib(x-1)+fib(x-2); # Iterative fib. def fibi(x) var a = 1, b = 1, c in (for i = 3, i < x in c = a + b : a = b : b = c) : b; # Call it. fibi(10);为了改变变量，需要改变变量申请方式，并添加新的操作符。10.1 修改已有变量g_named_values 中存放对应符号名称的 LLVM Value*，为了支持变量，需要改为存放符号的”内存地址“。首先，将 g_named_values 改为映射 AllocaInst*，而不再映射 Value*：static std::map<std::string, AllocaInst*> g_named_values;需要一个 helper 函数确保在函数的入口块中创建 alloca：/// CreateEntryBlockAlloca - Create an alloca instruction in the entry block of /// the function. This is used for mutable variables etc. static AllocaInst *CreateEntryBlockAlloca(Function *function, const std::string &var_name) { // 创建 IRBuilder，指向了入口块的第一条指令 IRBuilder<> tmp_b(&function->getEntryBlock(), function->getEntryBlock().begin()); // 创建 alloca return tmp_b.CreateAlloca(Type::GetDoubleTypepe(g_llvm_context), 0, var_name.c_str()); }在新模式中，变量位于栈中，所以要使用它们的话，需要从栈中加载：Value *VariableExprAST::Codegen() { // Look this variable up in the function. Value *v = g_named_values[name_]; if (!v) return LogErrorV("Unknown variable name"); // Load the value. g_ir_builder->CreateLoad(Type::GetDoubleTypepe(*g_llvm_context), v, name_.c_str()); }接下来需要更新定义变量的地方以使用 alloca，先从 ForExprAST::Codegen() 开始：Function *function = Builder.GetInsertBlock()->getParent(); // Create an alloca for the variable in the entry block. AllocaInst *alloca = CreateEntryBlockAlloca(function, var_name_); // Emit the start code first, without 'variable' in scope. Value *start_val = start_->Codegen(); if (!start_val) return nullptr; // Store the value into the alloca. g_ir_builder->CreateStore(start_val, alloca); ... // Compute the end condition. Value *end_condition = end_->Codegen(); if (!end_condition) return nullptr; // Reload, increment, and restore the alloca. This handles the case where // the body of the loop mutates the variable. Value *cur_var = g_ir_builder->CreateLoad(Type::GetDoubleTypepe(*g_llvm_context), alloca, var_name_.c_str()); Value *next_var = g_ir_builder->CreateFAdd(cur_var, step_val, "nextvar"); g_ir_builder->CreateStore(next_var, alloca); ...可以看到，使用了变量后，便不需要再创建 PHI 节点了，而是通过 load/store 访问所需的变量。支持函数参数变量：Function *FunctionAST::Codegen() { ... g_ir_builder->SetInsertPoint(bb); // Record the function arguments in the g_named_values map. g_named_values.clear(); for (auto &arg : function->args()) { // Create an alloca for this variable. AllocaInst *alloca = CreateEntryBlockAlloca(function, arg.name()); // Store the initial value into the alloca. g_ir_builder->CreateStore(&arg, alloca); // Add arguments to variable symbol table. g_named_values[std::string(arg.name())] = alloca; } if (Value *ret_val = body_->Codegen()) { ...为每个参数创建一个 alloca，即在栈上申请内存，然后将参数值保存进去，最后将 alloca 更新到 g_named_values 中。使用内存保存临时变量的性能比较低，可以使用 mem2reg 优化，使用寄存器存放变量：// Promote allocas to registers. g_fpm->add(createPromoteMemoryToRegisterPass()); // Do simple "peephole" optimizations and bit-twiddling optzns. g_fpm->add(createInstructionCombiningPass()); // Reassociate expressions. g_fpm->add(createReassociatePass()); ...10.2 新的赋值符号设置优先级：int main() { // Install standard binary operators. // 1 is lowest precedence. g_binopcode_precedence['='] = 2; g_binopcode_precedence['<'] = 10; g_binopcode_precedence['+'] = 20; g_binopcode_precedence['-'] = 20;生成 IR：Value *BinaryExprAST::Codegen() { // Special case '=' because we don't want to emit the LHS as an expression. if (opcode_ == '=') { // Assignment requires the LHS to be an identifier. // 左值必须是个变量 VariableExprAST *lhs = static_cast<VariableExprAST *>(lhs_.get()); if (!lhs) return LogErrorV("destination of '=' must be a variable"); // Codegen the RHS. // 生成右值 Value *val = rhs_->Codegen(); if (!val) return nullptr; // Look up the name. Value *variable = g_named_values[lhs->name()]; if (!variable) return LogErrorV("Unknown variable name"); // 赋值 g_ir_builder->CreateStore(val, variable); return val; } ...因为有了赋值符号和变量，所以可运行如下代码：# Function to print a double. extern printd(x); # Define ':' for sequencing: as a low-precedence operator that ignores operands # and just returns the RHS. def binary : 1 (x y) y; def test(x) printd(x) : x = 4 : printd(x); test(123);10.3 自定义本地变量添加 var/in，和之前一样，扩展 Kaleidoscope 一般需要扩展：Lexer、Parser、AST 和生成 IR。扩展 Lexer：enum Token { ... // var definition TOKEN_VAR = -13 ... } ... static int GetToken() { ... if (g_identifier_str == "var") return TOKEN_VAR; return TOKEN_IDENTIFIER; ...定义 AST 节点：/// VarExprAST - Expression class for var/in // 可以一次性定义多个变量 class VarExprAST : public ExprAST { std::vector<std::pair<std::string, std::unique_ptr<ExprAST>>> var_names_; std::unique_ptr<ExprAST> body_; // 对变量要执行的操作 public: VarExprAST( std::vector<std::pair<std::string, std::unique_ptr<ExprAST>>> var_names_, std::unique_ptr<ExprAST> body) : var_names_(std::move(var_names_)), body_(std::move(body)) {} Value *Codegen() override; };扩展 Parser。先添加到基本表达式中：/// primary /// ::= identifierexpr /// ::= numberexpr /// ::= parenexpr /// ::= ifexpr /// ::= forexpr /// ::= varexpr static std::unique_ptr<ExprAST> ParsePrimary() { switch (g_cur_token) { ... case TOKEN_VAR: return ParseVarExpr(); } }然后定义 ParseVarExpr：/// varexpr ::= 'var' identifier ('=' expression)? // (',' identifier ('=' expression)?)* 'in' expression static std::unique_ptr<ExprAST> ParseVarExpr() { NextToken(); // eat the var. std::vector<std::pair<std::string, std::unique_ptr<ExprAST>>> var_names; // At least one variable name is required. if (g_cur_token != TOKEN_IDENTIFIER) return LogError("expected identifier after var"); // 解析所有变量 while (1) { std::string name = g_identifier_str; NextToken(); // eat identifier. // Read the opcodetional initializer. std::unique_ptr<ExprAST> init = nullptr; if (g_cur_token == '=') { NextToken(); // eat the '='. init = ParseExpression(); if (!init) return nullptr; } var_names.push_back(std::make_pair(name, std::move(init))); // End of var list, exit loop. if (g_cur_token != ',') break; NextToken(); // eat the ','. if (g_cur_token != TOKEN_IDENTIFIER) return LogError("expected identifier list after var"); } // At this point, we have to have 'in'. if (g_cur_token != TOKEN_IN) return LogError("expected 'in' keyword after 'var'"); NextToken(); // eat 'in'. // 针对变量要执行的操作 auto body = ParseExpression(); if (!body) return nullptr; return std::make_unique<VarExprAST>(std::move(var_names), std::move(body)); }生成 IR：Value *VarExprAST::Codegen() { std::vector<AllocaInst *> old_bindings; Function *function = Builder.GetInsertBlock()->getParent(); // Register all variables and emit their initializer. // 初始化每个变量，并注册到符号表中 for (unsigned i = 0, e = var_names_.size(); i != e; ++i) { const std::string &var_name = var_names_[i].first; ExprAST *init = var_names[i].second.get(); // Emit the initializer before adding the variable to scope, this prevents // the initializer from referencing the variable itself, and permits stuff // like this: // var a = 1 in // var a = a in ... # refers to outer 'a'. Value *init_val; if (init) { init_val = init->Codegen(); if (!init_val) return nullptr; } else { // If not specified, use 0.0. init_val = ConstantFP::get(*g_llvm_context, APFloat(0.0)); } AllocaInst *alloca = CreateEntryBlockAlloca(function, var_name); g_ir_builder->CreateStore(init_val, alloca); // Remember the old variable binding so that we can restore the binding when // we unrecurse. old_bindings.push_back(g_named_values[var_name]); // Remember this binding. g_named_values[var_name] = alloca; } // Codegen the body, now that all vars are in scope. // body 可以访问到所有的自定义变量 Value *body_val = body_->Codegen(); if (!body_val) return nullptr; // Pop all our variables from scope. for (unsigned i = 0, e = var_names_.size(); i != e; ++i) g_named_values[var_names_[i].first] = old_bindings[i]; // Return the body computation. return body_val; }现在可以支持如下示例了：extern printd(x) def foo(x) if x < 3 then 1 else foo(x - 1) + foo(x - 2) for i = 1, i < 10, 1.0 in printd(foo(i))编译运行：# Compile clang++ -g toy.cpp `llvm-config --cxxflags --ldflags --system-libs --libs core orcjit native` -O3 -o toy # Run ./toy11 编译生成目标文件LLVM 支持跨平台编译，可使用“target triple”的字符串指定体系结构，其形式为<arch>-<vendor>-<sys>-<abi>。例如，clang 认为我们的体系结构为：$ clang --version | grep Target Target: x86_64-unknown-linux-gnu我们并不需要硬编码体系结构，LLVM 的 sys::getDefaultTargetTriple 会返回当前机器的体系结构：auto target_triple = sys::getDefaultTargetTriple();TargetMachine 类提供了对机器的完整描述，可以帮助我们配置特定的 feature 或特定的 CPU。比如，我们可以查看支持哪些 feature 和 CPU：$ llvm-as < /dev/null | llc -march=x86 -mattr=help Available CPUs for this target: amdfam10 - Select the amdfam10 processor. athlon - Select the athlon processor. athlon-4 - Select the athlon-4 processor. ... Available features for this target: 16bit-mode - 16-bit mode (i8086). 32bit-mode - 32-bit mode (80386). 3dnow - Enable 3DNow! instructions. 3dnowa - Enable 3DNow! Athlon instructions. ...比如，我们可以使用不包含任何附加 feature 的通用 CPU：auto cpu = "generic"; auto features = ""; TargetOptions opt; auto rm = Optional<Reloc::Model>(); auto target_machine = target->createTargetMachine(target_triple, cpu, features, opt, rm);完整代码如下：int main() { ... // Run the main "interpreter loop" now. MainLoop(); // Initialize the target registry etc. // 初始化生成 IR 的所有 target // LLVM 并不要求我们链接所有的 target，如果我们只是使用 JIT，可以不组装打印机 InitializeAllTargetInfos(); InitializeAllTargets(); InitializeAllTargetMCs(); InitializeAllAsmParsers(); InitializeAllAsmPrinters(); // 返回当前机器的体系结构 auto target_triple = sys::getDefaultTargetTriple(); g_llvm_module->setTargetTriple(target_triple); // 获取 Target std::string error; auto target = TargetRegistry::lookupTarget(target_triple, error); // Print an error and exit if we couldn't find the requested target. // This generally occurs if we've forgotten to initialise the // TargetRegistry or we have a bogus target triple. if (!target) { errs() << error; return 1; } // 使用不包含任何附加 feature 的通用 CPU auto cpu = "generic"; auto features = ""; TargetOptions opt; auto rm = Optional<Reloc::Model>(); // TargetMachine 类提供对机器的完整描述 auto target_machine = target->createTargetMachine(target_triple, cpu, features, opt, rm); // 配置 Module，这一步不是必须的，但是有助于优化 g_llvm_module->setDataLayout(target_machine->createDataLayout()); g_llvm_module->setTargetTriple(target_triple); // 目标文件 auto filename = "output.o"; std::error_code err_code; raw_fd_ostream dest(filename, err_code, sys::fs::OF_None); if (err_code) { errs() << "Could not open file: " << err_code.message(); return 1; } // 定义一个生成目标的 pass legacy::PassManager pass; auto file_type = CGFT_ObjectFile; if (target_machine->addPassesToEmitFile(pass, dest, nullptr, file_type)) { errs() << "TheTargetMachine can't emit a file of this type"; return 1; } // 运行 pass pass.run(*g_llvm_module); dest.flush(); outs() << "Wrote " << filename << "\n"; return 0; }编译运行：$ clang++ -g -O3 toy.cpp `llvm-config --cxxflags --ldflags --system-libs --libs all` -o toy $ ./toy ready> def average(x y) (x + y) * 0.5; ^D Wrote output.o12 添加 Debug 信息12.1 提前编译模式我们无法在 JIT 模式下 debug，而是需要进行提前编译（AOT），为此需要一个源码文件。优化会将多条指令合并成一个，还可能会去掉一些变量，所以为了 debug，我们先去掉优化。首先，我们将包含顶级语句的匿名函数设为“main”：auto proto = std::make_unique<PrototypeAST>("main", std::vector<std::string>());然后去掉命令行代码：@@ -1129,7 +1129,6 @@ static void HandleTopLevelExpression() { /// top ::= definition | external | expression | ';' static void MainLoop() { while (1) { - fprintf(stderr, "ready> "); switch (g_cur_token) { case TOKEN_EOF: return; @@ -1184,7 +1183,6 @@ int main() { g_binop_precedence['*'] = 40; // highest. // Prime the first token. - fprintf(stderr, "ready> "); NextToken();最后，关掉所有的优化和 JIT：static void HandleTopLevelExpression() { // Evaluate a top-level expression into an anonymous function. if (auto fn_ast = ParseTopLevelExpr()) { if (!fn_ast->codegen()) { fprintf(stderr, "Error generating code for top level expr"); } } else { // Skip token for error recovery. NextToken(); } }通过以上改动，我们便可通过如下命令将 Kaleidoscope 编译为一个可执行程序 a.out/a.exe：Kaleidoscope-Ch9 < fib.ks | & clang -x ir -12.2 DWARF 设置源码级调试需要使用格式化的数据，以便调试器将二进制文件和机器码转换回源代码。LLVM 中，通常使用 DWARF 格式，一种表示类型、源位置和变量位置的紧凑编码。与 IRBuilder 类似，DIBuilder 可以为 LLVM IR 文件构建 debug 元数据。我们将使用 DIBuilder 来构建所有 IR 级别的描述。static std::unique_ptr<DIBuilder> g_di_builder; struct DebugInfo { DICompileUnit *compile_unit_; // 编译单元，可以理解为是一个源码文件 DIType *di_type_; DIType *GetDoubleTypepe(); } g_dbg_info; // 只需要考虑 double 类型就好了 DIType *DebugInfo::GetDoubleType() { if (di_type_) return di_type_; di_type_ = g_di_builder->createBasicType("double", 64, dwarf::DW_ATE_float); return di_type_; }在 main 中构建 module 时：g_di_builder = new DIBuilder(*g_llvm_module); g_dbg_info.compile_unit_ = g_di_builder->createCompileUnit( // 使用了 C 中的常量， // 因为调试器不一定理解它不识别的语言的调用约定或默认 ABI， // 所以在 LLVM 代码生成中遵循 C ABI 是最准确的。 // 这确保了我们可以从调试器中调用函数并让它们执行 dwarf::DW_LANG_C, // 硬编码了文件名 g_di_builder->createFile("fib.ks", "."), "Kaleidoscope Compiler", 0, "", 0);在 main 的末尾处添加：g_di_builder->finalize();12.3 函数接下来需要将一些函数定义添加到 debug 信息中。在 PrototypeAST::Codegen() 中添加几行代码来描述程序的上下文。本例中是“文件”和函数本身的定义。上下文：DIFile *unit = DBuilder->createFile(g_dbg_info.compile_unit_.getFilename(), g_dbg_info.compile_unit_.getDirectory());使用源位置 0（因为 AST 还没有源码位置信息） 并构建函数定义：DIScope *f_context = unit; unsigned line_no = p.line(); unsigned scope_line = line_no; // DISubprogram 中包含了函数的所有元数据 DISubprogram *sp = g_di_builder->createFunction( f_context, p.name(), StringRef(), unit, line_no, CreateFunctionType(function->arg_size(), unit), scope_line, DINode::Flagprototyped, DISubprogram::SPFlagDefinition); function->setSubprogram(sp);12.4 源位置debug 最重要的就是精确的源位置。在 Lexer 中添加源位置信息，跟踪行号和列号：struct SourceLocation { int line_; int col_; }; static SourceLocation g_cur_loc; static SourceLocation g_lex_loc = {1, 0}; static int Advance() { int last_char = getchar(); if (last_char == '\n' || last_char == '\r') { g_lex_loc.line_++; g_lex_loc.col_ = 0; } else g_lex_loc.col_++; return last_char; }在 AST 中添加源位置信息：class ExprAST { SourceLocation loc_; public: ExprAST(SourceLocation loc = g_cur_loc) : loc_(loc) {} virtual ~ExprAST() {} virtual Value *Codegen() = 0; int line() const { return loc_.line_; } int col() const { return loc_.col_; } virtual raw_ostream &Dump(raw_ostream &out, int ind) { return out << ':' << line() << ':' << col() << '\n'; } };创建 AST 的时候将源位置信息传进去：lhs = std::make_unique<BinaryExprAST>(bin_loc, binopcode, std::move(lhs), std::move(rhs));为了确保每条指令都能获得正确的源位置，每到达一个新位置时都需要告诉 Builder。使用一个 helper 函数来实现此功能：void DebugInfo::EmitLocation(ExprAST *ast) { DIScope *scope; if (lexical_blocks_.empty()) scope = compile_unit_; else scope = lexical_blocks_.back(); g_ir_builder->SetCurrentDebugLocation(DILocation::get( scope->getContext(), ast->line(), ast->col(), scope)); }这既告诉了 main IRBuilder 我们在哪里，也告诉了我们在什么作用域内。在 DebugInfo 创建了一个栈作用域：std::vector<DIScope *> lexical_blocks_;每当为一个函数生成 code 时，便将该函数的作用域入栈：// Push the current scope. g_dbg_info.lexical_blocks_.push_back(sp);结束生成 code 时，将该函数的作用域出栈：// Pop off the lexical block for the function since we added it // unconditionally. g_dbg_info.lexical_blocks_.pop_back();每当为一个新的 AST 生成 code 时，都需要发射位置：g_dbg_info.EmitLocation(this);12.5 变量现在有了函数，我们需要能够打印出作用域内的变量。// Record the function arguments in the g_named_values map. g_named_values.clear(); unsigned arg_idx = 0; for (auto &arg : function->args()) { // Create an alloca for this variable. AllocaInst *alloca = CreateEntryBlockAlloca(function, arg.name()); // Create a debug descriptor for the variable. // 给变量一个作用域（sp），源码位置，类型和参数下标 DILocalVariable *des = g_di_builder->createParameterVariable( sp, arg.name(), ++arg_idx, unit, line_no, g_dbg_info.GetDoubleType(), true); // 告诉 IR 我们在 alloca 中获取到一个变量（给出了变量的位置） // 并在 declare 上为作用域的起始位置设置源位置 g_di_builder->insertDeclare(alloca, des, g_di_builder->createExpression(), DILocation::get(SP->getContext(), line_no, 0, sp), g_ir_builder->GetInsertBlock()); // Store the initial value into the alloca. g_ir_builder.CreateStore(&arg, alloca); // Add arguments to variable symbol table. g_named_values[arg.name()] = alloca; }在 FunctionST::Codegen中，添加了几行，避免为函数序言生成行信息，以便调试器知道在设置断点时跳过这些指令：// Unset the location for the prologue emission (leading instructions with no // location in a function are considered part of the prologue and the debugger // will run past them when breaking on a function) g_dbg_info.EmitLocation(nullptr);当真正开始为函数体生成 code 时发射位置：g_dbg_info.EmitLocation(body_.get());有了这些，我们就有了足够的调试信息，可以在函数中设置断点、打印参数变量和调用函数。编译运行：# Compile clang++ -g toy.cpp `llvm-config --cxxflags --ldflags --system-libs --libs core orcjit native` -O3 -o toy # Run ./toy参考https://llvm.org/docs/tutorial/index.html宫文学. 编译原理之美.