编译器后端实战从源码到汇编、LLVM IR 与代码优化参考宫文学《编译原理》极客时间后端部分课程 22–28。本文不堆砌理论而是用 Python 真正动手实现一个微型语言的后端把同一门语言分别编译成x86-64 汇编、生成LLVM IR并在 AST 上实现常量折叠 死代码消除两个优化 pass。所有示例均在华为云 ECSUbuntu 24.04gcc 13.3 / clang 18真实运行输出原样贴出。一、引言编译器后端到底在做什么前端把源码变成 AST抽象语法树后端的工作则是把 AST 进一步变成可执行的目标代码。它要解决三件事指令选择AST 里的a b落到哪条机器指令寄存器怎么分配运行模型函数调用遵循什么约定栈帧怎么布局系统调用怎么触发优化能不能在不改变语义的前提下让生成出的代码更小、更快本文用一门“微型语言”贯穿这三点。它支持整数算术、变量与赋值、if、while和print。我们约定程序最后一条语句求值得到的寄存器%rax作为退出码返回print则额外把整数打印到标准输出——这样既直观又能用echo $?立刻看到结果。后端的“主流程”可以这样串起来源码 →词法/语法→ AST →代码生成→ 汇编/LLVM IR →汇编器/链接器或 JIT→ 可执行文件 →运行→ 真实输出。优化 pass 则插在“AST → 目标代码”之间的某一层对树或线性 IR 做等价改写。本文的三部分正好对应这条流水线的三个关键横截面。二、核心概念速览汇编Assembly离机器码只差一步的“可读机器指令”。本文生成 x86-64 的 ATT 风格汇编用asld直接链成可执行文件不依赖任何 C 运行时。LLVM IR一种强类型、SSA静态单赋值形式的中间表示介于源码与机器码之间。它的好处是可移植、可被多种优化 pass 反复加工再交给后端生成各平台机器码。代码优化在 AST 或线性 IR 上做等价变换。本文实现两个教科书级 pass——常量折叠编译期算常数与死代码消除删掉永不读取的赋值。三、Part 1汇编代码生成3.0 词法与语法递归下降汇编生成器的前半段是标准的前端铺垫但因为它和后端共用同一套 AST这里也一并交代。词法分析把字符流切成 token数字、标识符、运算符语法分析用递归下降法按优先级构造 AST。运算符优先级从高到低为一元负号 * / % - 比较 !||对应一组互相调用的parse_*函数defparse_mul(self):# 处理 * / %leftself.parse_unary()whileself.peek()[1]in(*,/,%):opself.next()[1]rightself.parse_unary()left(bin,op,left,right)returnleft这样2 3 * 4会被正确解析成( 2 (* 3 4))而非(* ( 2 3) 4)——优先级就是靠“先调用的函数层级更高”自然落地的。3.1 编译器总体结构整个编译器只有约 300 行 Python分三段词法→语法递归下降→代码生成。AST 用元组表示例如(bin, , (num, 2), (bin, *, (num, 3), (num, 4)))。代码生成器AsmGen持有一个指令列表和变量集合每遇到一个 AST 节点就“吐”出对应的汇编行到收尾时把出现过的变量统一在.bss段声明为.quad 0。表达式求值的统一约定是结果一律放在%rax。遇到二元运算时先算左操作数压栈再算右操作数最后弹出左操作数参与运算# 加法left rightself.gen_expr(l)self.emit(push %rax)# 保存左操作数self.gen_expr(r)# %rax 右操作数self.emit(pop %rdi)# %rdi 左操作数self.emit(add %rdi, %rax)# rax left right乘法用imul除法要分外小心——idiv做的是rdx:rax / 操作数所以先要把右操作数放进%rcx、左操作数放进%rax并清掉%rdxself.emit(mov %rax, %rcx)# 右操作数self.emit(pop %rax)# %rax 左操作数self.emit(xor %rdx, %rdx)self.emit(idiv %rcx)# rax 商, rdx 余数3.2 变量、print 与退出变量统一放在.bss段用var_名字标号引用数据访问使用RIP 相对寻址mov var_x(%rip), %rax这样生成的代码在 PIE / 非 PIE 下都能正常链接。print需要先做“整数 → 十进制字符串”的转换再调用write系统调用。我们把待打印值存入被调用者保存寄存器%r12调用print_int子过程返回后再把%r12拷回%rax保证打印后退出码依然正确self.emit(mov %rax, %r12)# 保存待打印值self.emit(call print_int)self.emit(mov %r12, %rax)程序末尾把%rax作为退出码交还系统mov %rax, %rdi mov $60, %rax # syscall: exit syscall3.3 真实运行效果示例examples/expr.tinyx 2 3 * 4; y (x - 5) / 2; print x; print y; z x * y 10; print z;$ python3 asm_gen.py examples/expr.tiny /root/compiler/back# …生成 expr.s核心片段…mov$2, %rax push %rax mov$3, %rax push %rax mov$4, %rax pop %rdi imul %rdi, %rax# 3*4 12pop %rdiadd%rdi, %rax# 2 12 14 - var_x# …-------------------- 运行结果 -------------------- 标准输出:14466退出码(exit status)66注意3 * 4被先算乘法优先级更高2 12 14存入var_x与手算完全一致最终z 14*410 66退出码正是 66。再跑一个带while和if的例子examples/loop.tiny求 1…10 之和并打印-7的绝对值$ python3 asm_gen.py examples/loop.tiny /root/compiler/back -------------------- 运行结果 -------------------- 标准输出:557退出码(exit status)7sum 12…10 55a -7经if (a 0) a -a后变为7退出码 7。循环与分支控制流.Lwhtop/.Lwhend标号 jz跳转完全由我们的代码生成器产出。四、Part 2生成 LLVM IR 并运行比起手写汇编LLVM IR 是更“高级”的中间表示。它强类型、SSA 形式每个值只赋值一次且有现成的clang/lli工具链可直接运行。下面用 Python 拼出一段 IR实现递归阶乘和循环求和define i64 fact(i64 %n) { entry: %le icmp sle i64 %n, 1 br i1 %le, label %base, label %rec base: ret i64 1 rec: %n1 sub i64 %n, 1 %f call i64 fact(i64 %n1) %r mul i64 %n, %f ret i64 %r }循环则用brphi表达。phi是 SSA 处理“控制流汇合”的关键在循环头变量i/acc究竟取初值还是上次迭代的更新值由“来自哪个前驱基本块”决定loop: %i phi i64 [ 1, %entry ], [ %i1, %body ] %acc phi i64 [ 0, %entry ], [ %acc1, %body ] %c icmp sle i64 %i, %n br i1 %c, label %body, label %done body: %acc1 add i64 %acc, %i %i1 add i64 %i, 1 br label %loop done: ret i64 %accmain调用二者并用 C 库的printf打印。同一份.ll我们两种运行方式都验证$ python3 llvm_gen.py /root/compiler/back -------------------- 运行结果 --------------------[clang 运行]退出码0362880055[lli 运行]退出码0362880055fact(10) 3628800sum(10) 55。clang把 IR 编译成原生可执行文件、lli直接解释执行结果完全一致——这正是中间表示“一次生成、多后端复用”的价值。五、Part 3代码优化常量折叠 死代码消除优化在 AST 上做最直观且平台无关。常量折叠遍历 AST只要某子表达式的两个操作数都是编译期常量就直接算出来。核心是一个compute_bin函数对/和%按 x86-64idiv的“向零截断”语义处理。例如3 5 * 2折叠为1320 / 4折叠为5。死代码消除删除“结果永不被读取”的赋值。我们先扫描全程序收集“被读取变量集合”所有var节点再删除那些 LHS 不在集合中、又不是最后一条语句的assign。示例examples/opt.tiny$ python3 optimize.py examples/opt.tiny优化前源码a35*2;# 折叠为 a 13b100;# b 从未被读取 - 死代码ca 1;# a 是变量保留为 c (a 1)d20/4;# 折叠为 d 5unused999;# 死代码print a c d;# 结果 13 14 5 32优化后源码a13;c(a 1);d5;print((a c) d);优化验证解释器 优化前: 最终值32, 打印[32]解释器 优化后: 最终值32, 打印[32]语义一致(最终值打印): True 删除的语句数:6-4(减少2条)优化后编译运行asm_gen标准输出:32退出码(exit status)32注意a c d没有被继续折叠成32——因为a是变量只是恰好被折叠成常量13但 AST 层面它仍是var节点没有做“常量传播”。这恰恰是教学上的好提醒折叠只发生在纯常量子树上变量引用需要额外的常量传播 pass 才能进一步消掉。为了证明优化“真正安全”我们用内置解释器分别执行优化前后程序断言最终值与打印完全一致再把优化后的 AST 反序列化为源码、经由asm_gen编译成可执行文件实跑退出码 32。三重验证下语义零偏离。关于数据流分析工业级 DCE 不是简单全局扫描而是基于“可用/定值use-def / def-use”数据流分析。它的基本思想是顺着控制流图CFG做前向/后向的数据流迭代——定值definition一条语句给变量x赋了值就说它“定值”了x使用use某条语句读取了x就说它“使用”了x可用定值available definitions从程序入口到某点x的最后一次定值是什么活跃变量live variables从某点往后哪些变量的值还会被用到。如果一个定值x ...之后x的“使用”集合为空即在所有路径上都不活跃这个定值就是死的可以安全删除。本文的“全局读取集”判定相当于把整个程序拍平后做的一次粗略活跃性分析只保留至少被读取过一次的变量。它对没有分支/循环干扰的线性代码完全正确但在复杂控制流下会偏保守漏删或需要更精细的 CFG 迭代才能既安全又彻底。这正是后续进阶优化如基于支配树的 DCE要解决的问题。六、难点解析调用约定与寄存器保存x86-64 下%rax是返回值寄存器%rdi是第一个参数print_int用%r12被调用者保存传递待打印值避免被syscall破坏。若误用%rbx且不在调用前后保存会导致退出码错乱——我们正是踩过这个坑后改用%r12。栈帧与push/pop配对算二元运算时频繁压栈保存左操作数必须保证push/pop严格配对否则栈失衡会让ret跳飞。IR 设计SSA 与 phi手写汇编时变量是“可重复赋值”的内存/寄存器而 LLVM IR 的 SSA 要求每个值只赋值一次于是控制流汇合处必须用phi节点按来源块选择值。理解phi是读懂现代编译器 IR 的钥匙。优化正确性任何优化都必须“语义等价”。我们用解释器断言 真实编译运行双重校验确保折叠/删除没有悄悄改变程序含义。七、小结本文用一个不足 400 行的 Python 项目完整走通了编译器后端的三条主线汇编生成手写 ATT 汇编 系统调用理解指令选择、寄存器约定与栈帧LLVM IR用 SSA/phi 表达递归与循环复用成熟工具链clang/lli代码优化在 AST 上落地常量折叠与死代码消除并以真实运行验证等价性。源码与一键运行脚本均放在m2:/root/compiler/back/本地镜像在D:/D/compiler-work/code/back/。执行bash run_all.sh即可在 ECS 上一键复现全部输出已保存为output.txt。后端并不神秘——它就是把“正确的语义”翻译成“正确的机器动作”而优化则是在这道翻译里不断做“等价但更好”的取舍。回看本文的三个数字最直观expr.tiny以退出码66返回计算结果fact(10)经 LLVM 跑出3628800opt.tiny在删掉两条死代码后仍以退出码32保持语义不变。这些不是打印在纸上的假设而是as/ld/clang/lli在真实机器上给出的答案——动手跑通比任何图示都更能建立对后端的直觉。下一篇预告基于 DAG 的公共子表达式消除、寄存器分配入门以及把本文的线性栈式求值升级为真实寄存器分配。 编译器后端实战：从源码到汇编、LLVM IR 与代码优化
编译器后端实战从源码到汇编、LLVM IR 与代码优化参考宫文学《编译原理》极客时间后端部分课程 22–28。本文不堆砌理论而是用 Python 真正动手实现一个微型语言的后端把同一门语言分别编译成x86-64 汇编、生成LLVM IR并在 AST 上实现常量折叠 死代码消除两个优化 pass。所有示例均在华为云 ECSUbuntu 24.04gcc 13.3 / clang 18真实运行输出原样贴出。一、引言编译器后端到底在做什么前端把源码变成 AST抽象语法树后端的工作则是把 AST 进一步变成可执行的目标代码。它要解决三件事指令选择AST 里的a b落到哪条机器指令寄存器怎么分配运行模型函数调用遵循什么约定栈帧怎么布局系统调用怎么触发优化能不能在不改变语义的前提下让生成出的代码更小、更快本文用一门“微型语言”贯穿这三点。它支持整数算术、变量与赋值、if、while和print。我们约定程序最后一条语句求值得到的寄存器%rax作为退出码返回print则额外把整数打印到标准输出——这样既直观又能用echo $?立刻看到结果。后端的“主流程”可以这样串起来源码 →词法/语法→ AST →代码生成→ 汇编/LLVM IR →汇编器/链接器或 JIT→ 可执行文件 →运行→ 真实输出。优化 pass 则插在“AST → 目标代码”之间的某一层对树或线性 IR 做等价改写。本文的三部分正好对应这条流水线的三个关键横截面。二、核心概念速览汇编Assembly离机器码只差一步的“可读机器指令”。本文生成 x86-64 的 ATT 风格汇编用asld直接链成可执行文件不依赖任何 C 运行时。LLVM IR一种强类型、SSA静态单赋值形式的中间表示介于源码与机器码之间。它的好处是可移植、可被多种优化 pass 反复加工再交给后端生成各平台机器码。代码优化在 AST 或线性 IR 上做等价变换。本文实现两个教科书级 pass——常量折叠编译期算常数与死代码消除删掉永不读取的赋值。三、Part 1汇编代码生成3.0 词法与语法递归下降汇编生成器的前半段是标准的前端铺垫但因为它和后端共用同一套 AST这里也一并交代。词法分析把字符流切成 token数字、标识符、运算符语法分析用递归下降法按优先级构造 AST。运算符优先级从高到低为一元负号 * / % - 比较 !||对应一组互相调用的parse_*函数defparse_mul(self):# 处理 * / %leftself.parse_unary()whileself.peek()[1]in(*,/,%):opself.next()[1]rightself.parse_unary()left(bin,op,left,right)returnleft这样2 3 * 4会被正确解析成( 2 (* 3 4))而非(* ( 2 3) 4)——优先级就是靠“先调用的函数层级更高”自然落地的。3.1 编译器总体结构整个编译器只有约 300 行 Python分三段词法→语法递归下降→代码生成。AST 用元组表示例如(bin, , (num, 2), (bin, *, (num, 3), (num, 4)))。代码生成器AsmGen持有一个指令列表和变量集合每遇到一个 AST 节点就“吐”出对应的汇编行到收尾时把出现过的变量统一在.bss段声明为.quad 0。表达式求值的统一约定是结果一律放在%rax。遇到二元运算时先算左操作数压栈再算右操作数最后弹出左操作数参与运算# 加法left rightself.gen_expr(l)self.emit(push %rax)# 保存左操作数self.gen_expr(r)# %rax 右操作数self.emit(pop %rdi)# %rdi 左操作数self.emit(add %rdi, %rax)# rax left right乘法用imul除法要分外小心——idiv做的是rdx:rax / 操作数所以先要把右操作数放进%rcx、左操作数放进%rax并清掉%rdxself.emit(mov %rax, %rcx)# 右操作数self.emit(pop %rax)# %rax 左操作数self.emit(xor %rdx, %rdx)self.emit(idiv %rcx)# rax 商, rdx 余数3.2 变量、print 与退出变量统一放在.bss段用var_名字标号引用数据访问使用RIP 相对寻址mov var_x(%rip), %rax这样生成的代码在 PIE / 非 PIE 下都能正常链接。print需要先做“整数 → 十进制字符串”的转换再调用write系统调用。我们把待打印值存入被调用者保存寄存器%r12调用print_int子过程返回后再把%r12拷回%rax保证打印后退出码依然正确self.emit(mov %rax, %r12)# 保存待打印值self.emit(call print_int)self.emit(mov %r12, %rax)程序末尾把%rax作为退出码交还系统mov %rax, %rdi mov $60, %rax # syscall: exit syscall3.3 真实运行效果示例examples/expr.tinyx 2 3 * 4; y (x - 5) / 2; print x; print y; z x * y 10; print z;$ python3 asm_gen.py examples/expr.tiny /root/compiler/back# …生成 expr.s核心片段…mov$2, %rax push %rax mov$3, %rax push %rax mov$4, %rax pop %rdi imul %rdi, %rax# 3*4 12pop %rdiadd%rdi, %rax# 2 12 14 - var_x# …-------------------- 运行结果 -------------------- 标准输出:14466退出码(exit status)66注意3 * 4被先算乘法优先级更高2 12 14存入var_x与手算完全一致最终z 14*410 66退出码正是 66。再跑一个带while和if的例子examples/loop.tiny求 1…10 之和并打印-7的绝对值$ python3 asm_gen.py examples/loop.tiny /root/compiler/back -------------------- 运行结果 -------------------- 标准输出:557退出码(exit status)7sum 12…10 55a -7经if (a 0) a -a后变为7退出码 7。循环与分支控制流.Lwhtop/.Lwhend标号 jz跳转完全由我们的代码生成器产出。四、Part 2生成 LLVM IR 并运行比起手写汇编LLVM IR 是更“高级”的中间表示。它强类型、SSA 形式每个值只赋值一次且有现成的clang/lli工具链可直接运行。下面用 Python 拼出一段 IR实现递归阶乘和循环求和define i64 fact(i64 %n) { entry: %le icmp sle i64 %n, 1 br i1 %le, label %base, label %rec base: ret i64 1 rec: %n1 sub i64 %n, 1 %f call i64 fact(i64 %n1) %r mul i64 %n, %f ret i64 %r }循环则用brphi表达。phi是 SSA 处理“控制流汇合”的关键在循环头变量i/acc究竟取初值还是上次迭代的更新值由“来自哪个前驱基本块”决定loop: %i phi i64 [ 1, %entry ], [ %i1, %body ] %acc phi i64 [ 0, %entry ], [ %acc1, %body ] %c icmp sle i64 %i, %n br i1 %c, label %body, label %done body: %acc1 add i64 %acc, %i %i1 add i64 %i, 1 br label %loop done: ret i64 %accmain调用二者并用 C 库的printf打印。同一份.ll我们两种运行方式都验证$ python3 llvm_gen.py /root/compiler/back -------------------- 运行结果 --------------------[clang 运行]退出码0362880055[lli 运行]退出码0362880055fact(10) 3628800sum(10) 55。clang把 IR 编译成原生可执行文件、lli直接解释执行结果完全一致——这正是中间表示“一次生成、多后端复用”的价值。五、Part 3代码优化常量折叠 死代码消除优化在 AST 上做最直观且平台无关。常量折叠遍历 AST只要某子表达式的两个操作数都是编译期常量就直接算出来。核心是一个compute_bin函数对/和%按 x86-64idiv的“向零截断”语义处理。例如3 5 * 2折叠为1320 / 4折叠为5。死代码消除删除“结果永不被读取”的赋值。我们先扫描全程序收集“被读取变量集合”所有var节点再删除那些 LHS 不在集合中、又不是最后一条语句的assign。示例examples/opt.tiny$ python3 optimize.py examples/opt.tiny优化前源码a35*2;# 折叠为 a 13b100;# b 从未被读取 - 死代码ca 1;# a 是变量保留为 c (a 1)d20/4;# 折叠为 d 5unused999;# 死代码print a c d;# 结果 13 14 5 32优化后源码a13;c(a 1);d5;print((a c) d);优化验证解释器 优化前: 最终值32, 打印[32]解释器 优化后: 最终值32, 打印[32]语义一致(最终值打印): True 删除的语句数:6-4(减少2条)优化后编译运行asm_gen标准输出:32退出码(exit status)32注意a c d没有被继续折叠成32——因为a是变量只是恰好被折叠成常量13但 AST 层面它仍是var节点没有做“常量传播”。这恰恰是教学上的好提醒折叠只发生在纯常量子树上变量引用需要额外的常量传播 pass 才能进一步消掉。为了证明优化“真正安全”我们用内置解释器分别执行优化前后程序断言最终值与打印完全一致再把优化后的 AST 反序列化为源码、经由asm_gen编译成可执行文件实跑退出码 32。三重验证下语义零偏离。关于数据流分析工业级 DCE 不是简单全局扫描而是基于“可用/定值use-def / def-use”数据流分析。它的基本思想是顺着控制流图CFG做前向/后向的数据流迭代——定值definition一条语句给变量x赋了值就说它“定值”了x使用use某条语句读取了x就说它“使用”了x可用定值available definitions从程序入口到某点x的最后一次定值是什么活跃变量live variables从某点往后哪些变量的值还会被用到。如果一个定值x ...之后x的“使用”集合为空即在所有路径上都不活跃这个定值就是死的可以安全删除。本文的“全局读取集”判定相当于把整个程序拍平后做的一次粗略活跃性分析只保留至少被读取过一次的变量。它对没有分支/循环干扰的线性代码完全正确但在复杂控制流下会偏保守漏删或需要更精细的 CFG 迭代才能既安全又彻底。这正是后续进阶优化如基于支配树的 DCE要解决的问题。六、难点解析调用约定与寄存器保存x86-64 下%rax是返回值寄存器%rdi是第一个参数print_int用%r12被调用者保存传递待打印值避免被syscall破坏。若误用%rbx且不在调用前后保存会导致退出码错乱——我们正是踩过这个坑后改用%r12。栈帧与push/pop配对算二元运算时频繁压栈保存左操作数必须保证push/pop严格配对否则栈失衡会让ret跳飞。IR 设计SSA 与 phi手写汇编时变量是“可重复赋值”的内存/寄存器而 LLVM IR 的 SSA 要求每个值只赋值一次于是控制流汇合处必须用phi节点按来源块选择值。理解phi是读懂现代编译器 IR 的钥匙。优化正确性任何优化都必须“语义等价”。我们用解释器断言 真实编译运行双重校验确保折叠/删除没有悄悄改变程序含义。七、小结本文用一个不足 400 行的 Python 项目完整走通了编译器后端的三条主线汇编生成手写 ATT 汇编 系统调用理解指令选择、寄存器约定与栈帧LLVM IR用 SSA/phi 表达递归与循环复用成熟工具链clang/lli代码优化在 AST 上落地常量折叠与死代码消除并以真实运行验证等价性。源码与一键运行脚本均放在m2:/root/compiler/back/本地镜像在D:/D/compiler-work/code/back/。执行bash run_all.sh即可在 ECS 上一键复现全部输出已保存为output.txt。后端并不神秘——它就是把“正确的语义”翻译成“正确的机器动作”而优化则是在这道翻译里不断做“等价但更好”的取舍。回看本文的三个数字最直观expr.tiny以退出码66返回计算结果fact(10)经 LLVM 跑出3628800opt.tiny在删掉两条死代码后仍以退出码32保持语义不变。这些不是打印在纸上的假设而是as/ld/clang/lli在真实机器上给出的答案——动手跑通比任何图示都更能建立对后端的直觉。下一篇预告基于 DAG 的公共子表达式消除、寄存器分配入门以及把本文的线性栈式求值升级为真实寄存器分配。