编译器后端实战：从源码到汇编、LLVM IR 与代码优化-酒店常州论坛

编译器后端实战：从源码到汇编、LLVM IR 与代码优化

参考宫文学《编译原理》（极客时间）后端部分（课程 22–28）。本文不堆砌理论，而是用 Python 真正动手实现一个微型语言的后端：把同一门语言分别编译成x86-64 汇编、生成LLVM IR，并在 AST 上实现常量折叠 + 死代码消除两个优化 pass。所有示例均在华为云 ECS（Ubuntu 24.04，gcc 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 的 AT&T 风格汇编，用as+ld直接链成可执行文件，不依赖任何 C 运行时。
LLVM IR：一种强类型、SSA（静态单赋值）形式的中间表示，介于源码与机器码之间。它的好处是可移植、可被多种优化 pass 反复加工，再交给后端生成各平台机器码。
代码优化：在 AST 或线性 IR 上做等价变换。本文实现两个教科书级 pass——常量折叠（编译期算常数）与死代码消除（删掉永不读取的赋值）。

三、Part 1：汇编代码生成

3.0 词法与语法：递归下降

汇编生成器的前半段是标准的前端铺垫，但因为它和后端共用同一套 AST，这里也一并交代。词法分析把字符流切成 token（数字、标识符、运算符），语法分析用递归下降法按优先级构造 AST。运算符优先级从高到低为：一元负号 >* / %>+ -> 比较 >== !=>&&>||，对应一组互相调用的parse_*函数：

defparse_mul(self):# 处理 * / %left=self.parse_unary()whileself.peek()[1]in('*','/','%'):op=self.next()[1]right=self.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并清掉%rdx：

self.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 syscall

3.3 真实运行效果

示例examples/expr.tiny：x = 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*4+10 = 66，退出码正是 66。

再跑一个带while和if的例子examples/loop.tiny（求 1…10 之和并打印-7的绝对值）：

$ python3 asm_gen.py examples/loop.tiny /root/compiler/back -------------------- 运行结果 -------------------- 标准输出:557退出码(exit status)=7

sum = 1+2+…+10 = 55，a = -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 }

循环则用br+phi表达。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 %acc

main调用二者并用 C 库的printf打印。同一份.ll我们两种运行方式都验证：

$ python3 llvm_gen.py /root/compiler/back -------------------- 运行结果 --------------------[clang 运行]退出码=0362880055[lli 运行]退出码=0362880055

fact(10) = 3628800，sum(10) = 55。clang把 IR 编译成原生可执行文件、lli直接解释执行，结果完全一致——这正是中间表示“一次生成、多后端复用”的价值。

五、Part 3：代码优化（常量折叠 + 死代码消除）

优化在 AST 上做，最直观且平台无关。

常量折叠：遍历 AST，只要某子表达式的两个操作数都是编译期常量，就直接算出来。核心是一个compute_bin函数，对/和%按 x86-64idiv的“向零截断”语义处理。例如3 + 5 * 2折叠为13，20 / 4折叠为5。

死代码消除：删除“结果永不被读取”的赋值。我们先扫描全程序收集“被读取变量集合”（所有var节点），再删除那些 LHS 不在集合中、又不是最后一条语句的assign。

示例examples/opt.tiny：

$ python3 optimize.py examples/opt.tiny====================优化前源码====================a=3+5*2;# 折叠为 a = 13b=100;# b 从未被读取 -> 死代码c=a +1;# a 是变量，保留为 c = (a + 1)d=20/4;# 折叠为 d = 5unused=999;# 死代码print a + c + d;# 结果 = 13 + 14 + 5 = 32====================优化后源码====================a=13;c=(a +1);d=5;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 项目，完整走通了编译器后端的三条主线：

汇编生成：手写 AT&T 汇编 + 系统调用，理解指令选择、寄存器约定与栈帧；
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 跑出3628800；opt.tiny在删掉两条死代码后仍以退出码32保持语义不变。这些不是打印在纸上的假设，而是as/ld/clang/lli在真实机器上给出的答案——动手跑通，比任何图示都更能建立对后端的直觉。

下一篇预告：基于 DAG 的公共子表达式消除、寄存器分配入门，以及把本文的线性栈式求值升级为真实寄存器分配。

企业官网建设流程全解析