三地址码这东西我最早是在《编译原理》课上见到的。当时觉得它不过是一种中间表示考试会写t1 a b这种四元式就行。后来真动手写过解释器、接触过GCC和LLVM里头的IR之后才意识到三地址码根本不是一个答题格式而是编译器工程里最有生命力的设计之一。如果你正在学编译原理、打算写一个玩具语言、或者好奇x y * z这条代码在编译过程中到底被翻译成了什么这篇东西应该能给你一个非常具体的答案。别被三地址这名字吓到它没那么玄。简单说它就是一种把复杂表达式拆成简单指令的表示方法每条指令最多三个操作数像积木一样堆出完整程序逻辑。后面我不仅会解释原理还会带你看一个完整例子、做点代码优化、顺便聊聊GCC和LLVM是怎么用这类表示的。1. 三地址码到底是个什么东西从名字说起1.1 为什么叫三地址先解决最直白的问题为什么叫三地址码因为它的每条指令最多包含三个地址。这里的地址不是说内存绝对地址而是一个更宽泛的概念——可以是变量名、临时变量、常量甚至一个标识符。举个例子x y * z这种表达式如果写成一条三地址码指令常见形态是t1 y * z t2 x t1第二条指令t2 x t1里参与运算的是x和t1两个操作数结果落到t2。这就有两个源地址和一个目标地址恰好三个操作数位置。所以叫三地址。如果表达式只有一元运算比如-x那么指令只有两个位置参与比如t1 -x。严格说这是二地址但因为整套指令系统里绝大多数指令都遵循最多三个地址的格式学术界惯例还是统称三地址码。C语言里的赋值表达式最接近这种形态。你看a b c就是一个典型三地址操作b、c读出来送到加法器/ALU结果写回a。三地址码无非是把这种结构固定下来、再补充跳转、函数调用等控制流指令而已。所以三地址码的本质是一种线性化的中间表示。树结构里父子关系一目了然但机器不知道树是什么东西。三地址码把这些层级关系拍平变成一个纯顺序的指令序列——层面的顺序就是执行顺序遇到跳转除外。1.2 三地址码的典型形式与四元式教科书上聊三地址码绕不开四元式这个概念。两者意思很接近一条三地址指令在实现时常用四个字段来表示也就是操作符、第一操作数、第二操作数、结果。对应x y op z四个字段分别是op、y、z、x。四元式的结构可以用下表快速建立直觉编号操作符左操作数右操作数结果语义1*yzt1将 y 与 z 相乘存入 t12xt1t2将 x 与 t1 相加存入 t23:t2-a将 t2 赋值给 a这种表格式的存储方式在编译器内部的指令容器里非常常见。数组存四元式每一行四个字段编译器后端做优化时直接遍历数组即可。为什么用四元式而不用三元式一个很实际的原因是在三元式里计算结果需要用指令编号来引用比如第1条指令的结果。一旦你调整指令顺序比如做指令调度优化所有引用第1条指令的位置都要跟着改维护起来非常折磨。四元式给每个结果一个独立的临时变量名这种解耦让优化器可以更自由地重排指令。这里额外提一句很多教材说三地址码就是四元式严格讲不准确。三地址码是一种语义层面的表示形式四元式是它的一个具体实现方案。你可以用结构体、对象、数组各种方式去实现三地址码。LLVM IR在处理二元运算时其实也是类似四元式的思路只是字段更丰富。理解到这一层后面看GIMPLE、LLVM IR就不会觉得陌生。2. 编译器为什么要中间这一层三地址码的价值2.1 机器无关的优化入口编译器拿到的源码是一棵抽象语法树AST。AST适合表达语法结构但不适合做优化。原因是AST太高了a 0、a * 1、a - a这些模式在AST里看起来是不同形态的节点优化器得写一堆递归遍历逻辑才能识别。而三地址码把一切拍平成指令序列模式匹配变得极其直接——扫描到某条指令检查它的操作数是不是常量就能做折叠。比如这段C语言代码int foo() { int a 5; int b 7; return a b; }AST里需要维护两个VarDecl节点、一个BinaryOp节点、一个Return节点不能一眼看出结果等于12。但转成三地址码后t1 5 t2 7 t3 t1 t2 return t3优化器一眼就能看到t1 t2的双方都是常量直接折叠成t3 12。接着做传播优化把t3替换到return语句里进一步可以删除t1、t2两条死指令最终得到return 12这就是教科书上常说的常量折叠与传播。如果没有三地址码这层扁平化表示想做这些优化得在AST上写大量模式匹配逻辑费劲且容易漏。实际编译器几乎都会在中间表示层做多趟优化因为这一层的目标指令和具体CPU无关。同样的优化逻辑既适用于x86也适用于ARM、RISC-V。如果你直接在汇编层做优化每换一个目标架构都得重新实现一遍。2.2 简化后端移植三地址码的另一个巨大价值在于将前端和后端解耦。编译器前端只需要负责把高级语言翻译成三地址码后端则负责把三地址码翻译成目标机器指令。两者之间用三地址码做接口前端不需要关心目标平台是x86还是ARM后端也不需要关心源码是C还是Java。这就是为什么LLVM能这么轻松地支持多种语言Clang把C/C翻译成LLVM IRRust编译器把Rust翻译成LLVM IRSwift也一样。大家汇合到同一套中间表示后所有现有的优化pass和数十个后端架构直接复用。三地址码虽然不是LLVM IR的全部但LLVM IR确实是沿着三地址这个思路设计的——每个指令都有明确的操作码、操作数和结果全局性信息用符号表管理。还有人问为什么不直接用JVM字节码当中间表示答案在于抽象层级。JVM字节码是为虚拟机设计的指令集仍然隐含了栈式求值模型。而三地址码更接近寄存器机器模型在优化时更容易做数据流分析。栈式IR的分析需要大量栈语义推导寄存器式/三地址式的分析就直观得多。2.3 从表达式到三地址码的拆解逻辑这里我想把拆解这件事讲透。很多人写表达式求值没问题但一到生成三地址码就卡壳。其实核心规则只有两条遇到二元运算先递归处理左操作数再处理右操作数每个运算都需要一个新的临时变量来存放结果。以a b * c为例手工生成过程是这样的把 b * c 看成子问题 先算 b * c结果放 t1 再用 a t1 算 a t1结果放 t2 最终 t2 就是整个表达式的值这实际上和后缀表达式求值、递归下降求值的思路一致只是多了一步给每个中间结果命名。如果你写过表达式求值器生成三地址码几乎不需要额外学什么东西。带赋值和重命名的复杂表达式比如x (a b) * (c d)t1 a b t2 c d t3 t1 * t2 x t3注意c d和a b没有依赖关系理论上两条加法的执行顺序可以交换。三地址码把这种顺序不敏感暴露出来了乱序执行和调度器就是靠这种信息来优化指令执行的。3. 三地址码的常见指令类型与生成细节3.1 指令类型一览三地址码不止x y op z这一种。控制流、函数调用、返回值都得有对应指令。整理一份我工作中最常用到的指令集合指令类别示例说明赋值t1 42把常量写进变量/临时变量二元运算t2 t1 a加减乘除、位运算、比较运算都归此类一元运算t3 -t2取负、逻辑非、按位取反拷贝b a一个操作数赋值给另一个无条件跳转goto L1跳到某个标签条件跳转if t1 t2 goto L2根据比较结果决定是否跳转标签L2:跳转目标函数调用param x/t4 call foo传入参数、调用函数并取得返回值函数返回return t4返回给调用方数组操作t5 arr[i]/arr[i] t6数组元素读写需要专门的索引操作地址运算t7 obj.field取地址或取字段地址指针间接访问t8 *t7显式解引用在GCC的GIMPLE里表达式已经被拆得足够小所以这些指令类别基本能覆盖大部分场景。、||这类短路的逻辑表达式会转成条件跳转而不是直接的布尔运算。?:三元表达式也会转成跳转结构这些都是生成阶段要注意的语义细节。3.2 如何从AST生成三地址码一个完整例子我用一个简单但完整的例子带你看生成过程。假设有这段类C代码int main() { int a 2; int b 3; if (a b) { a a b; } else { b a * 2; } return a b; }第一步编译器前端已经得到AST有声明节点、赋值节点、if节点、二元运算节点、return节点等。接下来做三地址码生成大致会输出这样的指令序列t0 2 a t0 t1 3 b t1 if a b goto L_if goto L_else L_else: t2 a * 2 b t2 goto L_end L_if: t3 a b a t3 L_end: t4 a b return t4这里goto L_else的处理是很多新手容易犯错的点。if a b goto L_if条件成立时跳去if分支条件不成立时不能直接掉进L_else之前的那条指令而是要显式跳过去。如果条件判断是if a b goto L_else那就不需要goto L_else可以直接落下来执行。不同生成策略的差别在这里生成的指令数量也会有细微差异。if语句翻译的整体框架也可以总结成口诀先做条件判断条件成立跳到then分支条件不成立跳或落到else分支两个分支结束后统一跳到end标签。这个框架对while、for同样适用只是跳转方向不同。你还可以看到分支合并时a b被计算了两次——L_if分支里算过一次L_end处return t4又算了一次。这种浪费正是三地址码层面可以做公共子表达式消除的素材后面第4节会演示。3.3 临时变量的管理与偏移计算三地址码生成器会源源不断地创建t0、t1、t2...这种临时变量。如果你不管一长条程序能产生成百上千个临时名。这本身不是大问题因为三地址码只是中间形态后面会做寄存器分配、栈偏移计算。但管理不好会让调试变得非常痛苦。我在自己写的教学编译器里通常用一张符号表统一管理临时变量普通变量用原始名字临时变量统一用t 递增序号每个临时变量记录类型、名称、在当前函数内的生命周期起点和终点。生命周期尤其是关键信息。从生成时间点开始到最后一次被引用结束这个区间就是临时变量的活跃区间live range。寄存器分配器会利用活跃区间信息把短命的临时变量塞进同一个物理寄存器塞不下的临时变量再溢出到栈上。在代码生成后期每个临时变量都要分配一个栈偏移。一个典型的栈帧布局是高地址 [ 调用者的栈 ] [ 返回地址 ] [ 保存的寄存器 ] [ 局部变量区 ] [ 临时变量区 ] 低地址具体偏移怎么算取决于目标平台的对齐规则。但三地址码层不需要关心这些它只负责正确使用符号名。这种分层隔离让前端和后端有了清晰的边界。4. 在三地址码上做优化几个能落地的例子4.1 常量折叠与传播前面已经提过常量折叠这里给出更完整的实操逻辑。假设你的三地址码里有这样一段t1 5 t2 7 t3 t1 t2 a t3优化器可以这样处理记录每个变量的当前已知状态遍历到t1 5记下t1是常量5遍历到t3 t1 t2查表发现t1 5、t2 7于是把指令折叠成t3 12继续记录t3是常量12遍历到a t3把a也标记为常量12如果后面没有任何指令引用t1、t2、t3将它们标记为死代码并删除。这一段优化后代码变成a 12如果你的目标机器支持立即数寻址那么a 12这条指令最终会被编译成一条mov指令。这个优化在AST上是很难一次做到的但在三地址码上就是一个线性扫描。这里有个细节值得注意不是所有变量都能被常量传播。如果某个变量在分支里被赋值两次它的值就不一定是常量。因此实现常量传播时遇到分支汇合点要合并状态有一个分支传回未知就得标记为未知。简单的实现可以在控制流图CFG上做复杂度也不高。4.2 公共子表达式消除回到第3.2节那个例子L_end处计算了a b但其实在L_if分支里刚算过。如果a和b在中间没有被修改这个加法可以复用之前的临时变量。公共子表达式消除CSE的逻辑大概是遍历指令维护一个表达式到临时变量的映射表比如(a b) - t3遇到t4 a b查表发现(a b)已经有t3并且a、b在这中间没被修改过就把t4替换成t3如果替换后t4没有其他地方使用删除t4 a b。实际实现还需要判断赋值操作是否杀死了映射表中的表达式。比如如果中间有条a 0那么(a b)就不再复用了因为用t3代表旧值已经失效。这就是经典的可用表达式分析在数据流分析课程里属于标准题目。我在自己的教学编译器里实现CSE时踩过最大的坑是没有考虑数组元素的修改。arr[i] 1之后t arr[i]不能随便复用。虽然三地址码层面看不出来但分析层面需要把写数组当作写未知内存处理。所以做CSE时我通常保守地认为任何对内存的写操作都会杀死所有和内存有关的表达式。4.3 死代码消除与临时变量复用死代码消除DCE很反直觉但特别有用。原理是从程序的出口return、函数末尾反向遍历标记哪些变量是活跃的一个指令的结果如果没有任何活跃的读取者这条指令就是死的。比如优化后的常量传播留下t1 5 t2 7 a 12反向遍历从a 12开始a是活跃的t2 7定义了t2但没有任何指令读t2所以这条指令可以删除t1 5同理删除。最终t1、t2消失。临时变量复用的思想更进阶一点。假设原始代码产生三个临时变量但它们的活跃区间完全没有重叠就可以让它们复用同一个物理/虚拟寄存器甚至复用同一个临时变量名。t1 a b t2 c d t3 e f如果三条加法互不依赖且t1、t2、t3的使用范围不同那么寄存器分配器可能只用两个寄存器就搞定。三地址码把这种无关性用扁平指令序列呈现出来优化器只需要做活跃性分析不需要看抽象语法树。这也是很多后端优化pass都依赖三地址码的原因。5. 现实世界里的三地址码GIMPLE、LLVM IR与教学实践5.1 GCC GIMPLE里怎么体现三地址思想GCC是一个老牌但极其复杂的编译器。它有好几层中间表示其中GIMPLE就是典型的三地址码风格。GCC前端比如C前端先把源码转成GENERIC树再降级为GIMPLE。GIMPLE的核心限制包括表达式必须是三地址形式最多一个二元运算不允许复杂的嵌套表达式控制流显式地用goto表示副作用单独成句。举个例子源码a b c * d;在GIMPLE里会变成类似t1 c * d; a b t1;这和三地址码教科书里的形式几乎一模一样。区别在于GIMPLE还携带大量类型信息、对齐信息、别名分析信息方便后续优化。GCC的优化pass大都在GIMPLE这一层进行只有很靠后的阶段才下降成RTLRegister Transfer LanguageRTL更接近目标机器的寄存器传输描述。对我们写编译器的人GCC最大的启示是中间表示可以分成高层IR和低层IR。GIMPLE是高层IR和语言比较接近RTL是低层IR和机器比较接近。你的三地址码不一定非要从头到尾保持不变完全可以学GCC搞两层甚至三层。5.2 LLVM IR与三地址码的异同LLVM IR是三地址码思想的现代升级版。先看一个clang生成的LLVM IR片段源文件demo.c内容int demo(int x, int y) { return (x y) * 2; }用clang -S -emit-llvm demo.c会得到类似define i32 demo(i32 %x, i32 %y) { entry: %add add nsw i32 %x, %y %mul mul nsw i32 %add, 2 ret i32 %mul }里面%add add i32 %x, %y就是一条典型的三地址指令%add是结果%x和%y是操作数。但LLVM IR比基础三地址码多了几个重要特性静态单赋值形式SSA每个变量只能被赋值一次。%add只出现一次之后永远不能重新赋值。如果要表示变量变化就新建一个带版本号的变量。这让数据流分析简单很多缺点是转回可执行代码时需要做Phi节点消除。显式类型系统i32、float、ptr等写在每个操作数上后端直接知道操作宽度。带有内存访问模型load/store指令分离内存作为显式操作对象出现和寄存器操作不同。所以你可以把LLVM IR理解成三地址码 SSA 强类型 内存模型。它大体上还是三地址形态但深度工程化以后衍生出很多额外约定。学习三地址码时能够直接读懂LLVM IR是非常实用的技能。为了加深理解我建议你装一个带clang的环境亲手写几个C表达式然后执行clang -S -emit-llvm -O0 demo.c -o demo.ll看看没优化时指令有多啰嗦再用-O2跑一遍对比优化前后差异。这种体验比背十遍定义都来得直观。5.3 自己写一个迷你三地址码解释器要多难不要觉得三地址码只能停在纸面。它完全可以被直接解释执行这也常是我让学生快速理解三地址码的方式。我写过一个极简解释器核心循环如下用一段伪代码说明结构不是完整实现# 伪代码说明解释器主循环思路 registers {} def execute_ir(instructions): ip 0 while ip len(instructions): ins instructions[ip] op, dst, src1, src2 ins.op, ins.dst, ins.src1, ins.src2 if op BINOP: v1 registers[src1] v2 registers[src2] if ins.operator : registers[dst] v1 v2 elif ins.operator *: registers[dst] v1 * v2 elif op COPY: registers[dst] registers[src1] elif op CONST: registers[dst] src1 elif op JUMP: ip ins.target continue elif op COND_JUMP: v1 registers[src1] v2 registers[src2] if compare(v1, ins.compare_op, v2): ip ins.target continue elif op RETURN: return registers[dst] ip 1整个解释器不到200行Python就能写完但它已经能执行第3.2节示例里的简单控制流了。如果你对编译或编程语言实现感兴趣动手写一个这样的解释器远比单纯看教材管用。方式也很简单先定义一个指令结构体再定义符号表然后写AST到指令的转换器最后写循环执行器。一步步来三地址码就完全活了。6. 常见问题与避坑经验6.1 三地址码和四元式是不是一回事很多初学者会问做课程设计时到底该写三地址码还是四元式其实两者描述的是同一层IR只是视角略有不同。三地址码是语义描述每条指令最多三个地址四元式是实现描述用操作符、左操作数、右操作数、结果四个字段来存储一条指令。如果你在C里实现IR可以用一个struct Quad保存四个字段也可以用一个Instruction对象保存op/dst/src1/src2。至于输出时管它叫三地址码还是四元式全看你课程设计的命名偏好。重要的是底层结构一致别混为一谈。我见过有的教材把param x、call foo这类调用指令也算在三地址码里有的则单独划分。不要被这种分类差异绕晕实际编译器里指令集设计本来就可以自由扩展没有统一标准。6.2 临时变量爆炸怎么办生成三地址码最直观的坏味道就是临时变量满天飞。一个x a b * c - d / e表达式不优化可能生成四五条指令。在大型程序里这很正常不需要慌。重点是不要自己手动复制粘贴临时变量命名。我踩过的坑是曾经用一个全局计数器生成临时变量名但没考虑嵌套作用域重名结果生成出两个同名的临时变量其实是不同值。正确做法是临时变量名要么带函数作用域前缀要么用符号表保证唯一性。另外临时变量多了之后跳转标签也容易撞名。我习惯统一用L%d生成标签但要注意每个函数独立编号否则跨函数goto会被后端误判。生产级编译器里标签通常在函数内有效不考虑跨函数跳转。6.3 类型信息丢在哪一层三地址码本身往往不携带完整类型信息。比如x y z不告诉我们是整数加法还是浮点加法也不知道是8位、16位还是32位。这在高级语言编译里会出问题因为char加法不能按int加法来生成。所以在真正实现三地址码时最好在每个指令里保留一个type字段或者在符号表里记录每个变量的类型。举个最简单的例子t1 a b # int t2 c d # float如果一个指令没有类型标注后端会不知所措不知道要生成整数add指令还是浮点fadd指令。GIMPLE和LLVM IR都把类型信息做得很重原因就在这里。如果你只是做课程设计可以先用一个简单假设所有变量都是32位整数。但如果你要做一个真实语言一开始就保留类型后面会省很多事。6.4 学习/实操建议最后聊点学习方法。三地址码不是一个需要背的知识点而是一个用来观察程序执行过程的好工具。我觉得最有效的学习路径是手写AST转三地址码的生成器覆盖表达式、赋值、if、while、函数调用给生成的IR写一个解释器跑通基本控制流实现一个简单优化pass比如常量传播或CSE用clang -S -emit-llvm对比C代码与LLVM IR看一眼工业界怎么落地。按这个顺序走下来你不仅懂了三地址码还顺带把编译器的前后端、优化、运行机制都串起来了。如果要读代码参考我建议去看一些教学编译器比如经典的Let’s Build a Compiler系列的C版本或者看LLVM的Kaleidoscope教程。这两者都能让你看到三地址码和实际IR设计的交互。尤其是Kaleidoscope里面AST生成LLVM IR的代码非常适合初学者逐行读。照着LLVM的教程做你会发现生成IR的过程无非就是遍历AST、创建指令对象、塞进指令列表等指令多了就到了优化环节。想通这一点三地址码就算真正掌握了。