做编译原理课程的人十有八九都会在中间代码生成这一章卡一下。前面词法分析、语法分析再难好歹是在读到了这一章突然变成写要自己设计一套中间表示把语法树翻译过去很多同学就是从这儿开始掉队的。这篇东西我按自己带着学生做课程实验、也实际写过小编译器的经验来写不谈虚的直接讲中间代码生成里最核心的几件事为什么要有中间表示、三地址码怎么回事、表达式和控制流怎么翻译、回填怎么做最后聊聊SSA和工程里真实的中间表示长什么样。1. 为什么要有中间代码从AST往前走这一步的真正价值中间代码生成在整个编译流程里的位置前面是语义分析产出的抽象语法树后面是代码优化和目标代码生成。很多人第一次学到这儿会问一句语法树都分析出来了直接翻译成汇编不行吗非要中间插一层不是脱裤子放屁吗1.1 前端后端解耦是中间代码存在的根本理由这个问题的答案得从编译器的工程架构说起。你写一个C语言编译器总希望它能同时输出x86、ARM、RISC-V几个平台的机器码吧如果语法分析做完直接生成汇编那每支持一个新平台整个编译器的后半段全要重写词法分析、语法分析这些跟平台无关的工作也得跟着遭殃。中间代码这一层本质上就是把分析和生成切开的一道缝。前端只负责把源代码变成与机器无关的中间表示后端只负责把中间表示变成某个具体平台的机器码。这样换平台的时候前端完全不用动换语言的时候只要新语言的前端能产出同一种中间表示后端也完全不用动。LLVM能支持那么多语言和那么多后端靠的就是LLVM IR这层中间表示。类比一下就是前端是设计院画图纸后端是施工队干活中间代码就是那张标准化的施工图。设计师不用懂混凝土标号施工队也不用懂方案构思只要图纸是同一套规范谁跟谁都能对接。1.2 中间代码给优化留出了真正的操作空间还有一个理由跟优化有关。AST是很高层的结构它保留了源代码里的语法信息比如循环、分支这些都是现成的节点。但高级语法结构对优化器来说并不友好——优化器想在变量赋值算术运算跳转这种最基础的粒度上做文章而不是在WhileStatement这种节点级别上。三地址码这种扁平的指令序列每条指令只干一件简单的事数据流分析做起来才顺手。比如常量传播在中间代码上就是扫一遍把t2 t1 1里的t1替换成已知常量放到AST上你得自己在语法树里爬来爬去找赋值表达式节点累都累死了。记住这个观点中间代码是为优化器准备的不是给人类看的。所有中间表示的设计出发点都是怎么让机器分析和变换起来最省事。2. 三地址码与四元式最朴素的中间表示长什么样三地址码是整个中间代码生成这一章的基石概念。名字听着玄乎其实特别直白一条指令里最多出现三个地址两个操作数加一个结果比如t a b里的a、b、t就是三个地址。2.1 从一段C语段到三地址码先找找感觉拿最经典的例子开刀把c a b * 2翻译成三地址码第一反应是照着运算符优先级老老实实来t1 b * 2 t2 a t1 c t2这就是三地址码的核心形态。t1、t2是编译器临时生成的变量用来保存中间结果。注意一个细节翻译的顺序是先右子树后左子树这跟我们做语法树的后序遍历完全一致。所以从AST生成三地址码本质就是一次带上临时变量分配的后序遍历。再看个更复杂点的表达式比如带下标的数组访问a[i] 2 * a[i] 1t1 i * 4 // 计算偏移量int占4字节 t2 a t1 // 算出元素的地址 t3 *t2 // 取a[i]的值 t4 2 * t3 // 2 * a[i] t5 t4 1 // 加1 t6 a t1 // 重新计算a[i]的地址 *t6 t5 // 写回这里暴露了一个非常现实的问题同一个表达式a[i]的地址被算了两遍。如果用户写的是a[i] 2 * a[i] 1编译器真的会蠢到算两次吗在没做优化的朴素翻译里真的会。这个问题靠的就是后面代码优化阶段的公共子表达式删除CSE来解决三地址码这种每条指令只做一件事的格式让CSE这类优化做起来特别方便——因为它一眼就能看到a t1被重复计算了。2.2 四元式、三元式和间接三元式的取舍三地址码落实到具体数据结构上最常见的是四元式也是国内教材讲得最多的形式。四元式就是四个字段(op, arg1, arg2, result)。上面那段数组访问的代码用四元式表示就是( *, i, 4, t1 ) ( , a, t1, t2 ) ( *, t2, _, t3 ) ( *, 2, t3, t4 ) ( , t4, 1, t5 ) ( , a, t1, t6 ) ( , t5, _, t7 )op是操作符arg1和arg2是两个操作数result是结果存放位置。那个*是我用来表示取值运算的写法不同教材记法不一样有的写作[]或者load看习惯就行。四元式最大的好处是修改容易——每条指令都是独立的四元组想插入、删除、移动一条指令操作一个数组元素或者链表节点就行。代价是临时变量多得吓人比如上面那个例子里的t1到t7。三元式把i操作数换成指针直接引用另一条指令的结果省了临时变量但移动指令的时候所有引用它的地方都得跟着改优化器用起来很痛苦。所以工程上四元式更流行LLVM IR本质上也是一种广义的四元式。3. 表达式与赋值语句的翻译细节全藏在寻址和类型转换里表达式翻译是整个中间代码生成里最机械的部分逻辑上就是个树的后序遍历。但在实际写代码的时候会碰到几个教科书上容易一笔带过、实际却会让你卡半天的细节。3.1 临时变量的命名与管理规则临时变量叫t1、t2还是tmp_a都无所谓关键是怎么保证不重名。最土的办法是维护一个全局计数器每生成一个临时变量就加一。但有个坑如果你把t1这种名字直接用作目标平台上的寄存器或者栈变量名一旦用户源代码里也定义了同名变量就撞车了。工程上的做法是给编译器内部符号加前缀或者在符号表里单独建一个命名空间。比如编译器生成的临时变量统一叫%t1因为%在C语言里不是合法标识符永远不会跟用户变量冲突。JVM字节码里的临时变量干脆没有名字直接用$0、$1这样的槽位编号从根源上杜绝了撞车。另一个细节是临时变量能不能复用。朴素实现是每条计算结果都用新临时变量这样代码是对的但临时变量会爆炸。稍微聪明点的做法是DFS遍历表达式树时算完t1之后如果t1不再被需要下一个结果可以继续写进t1。这就是寄存器分配里活跃变量分析的雏形优化阶段会专门做初学阶段不用自己折腾老老实实递增计数器就行。3.2 类型不一致时的自动转换指令C语言里写int i; double d; x i d;如果x是double翻译的时候就必须在中间代码里显式插入类型转换指令。不会真的直接生成t2 i d——因为CPU的整数加法指令和浮点加法指令根本不是一回事。翻译的实际流程是t1 int_to_double(i) // 把int提升成double t2 t1 d // 浮点加法 x t2这就是语义分析阶段已经算好的类型合一结果在中间代码生成阶段落地。不同语言隐式转换规则差别很大C的整型提升、Java的数值拓宽、Python那种全是对象的模型到了类型转换这一块都会体现在中间代码里。这块有个常见实验坑如果你实现的编译器支持int和float混合运算一定要在中间代码里区分(int)和(float)两种指令不能图省事都用同一个。否则后面优化阶段跟汇编生成阶段根本不知道这条加法是整数加还是浮点加。3.3 数组寻址的偏移量乘法数组访问a[i]翻译成地址计算时i必须乘以元素大小。很多第一次写编译器的人会忘记这一步直接生成t2 a i然后跑到第三天突然发现int a[10]的输出完全不对。元素大小怎么来语义分析阶段符号表里已经存了数组元素的类型信息生成中间代码时从符号表里查一下元素类型乘上该类型占用的字节数就行。如果是结构体数组或者二维数组偏移计算会更复杂但本质还是每个维度的下标乘以对应维度的跨度最后加起来。这里有个性能优化的小技巧如果数组元素大小是2的幂比如4、8、16偏移量乘法i * 4可以直接优化成移位i 2这个优化在中间代码层就能做不用等到汇编阶段。4. 控制流语句的翻译标号、跳转和语句的嵌套控制流语句翻译的核心挑战在于把嵌套的结构化语句翻译成扁平的跳转指令序列。如果你只处理单条if-else或者单个while那很简单但一旦语句嵌套起来跳转目标标号的生成和管理就会变得棘手。4.1 if-else 和 while 的翻译模板先看最基础的if (E) S1 else S2。它的跳转结构长这样计算E的值 if E为假 goto L_false S1的代码 goto L_next L_false: S2的代码 L_next:这里有两个关键点。第一条件跳转的指令必须是一个独立的语句也就是说要先计算好条件表达式E的值存进临时变量再根据临时变量是否为0跳转。第二goto L_next这条跳转是怎么来的如果你不写它S1执行完之后会直接掉进S2的代码块逻辑就错了。再来个while (E) S的翻译模板L_begin: 计算E的值 if E为假 goto L_end S的代码 goto L_begin L_end:这种模板在课堂练习里玩玩绝对没问题但真实编译器里通常会做一个优化——把条件的跳转指令反过来用减少不必要的跳转指令。比如if (i 10)不再翻译成取反跳转而是直接生成if i 10 goto L_false。翻译的时候需要知道i 10的对偶比较是i 10这就要根据运算符类型查表了。4.2 嵌套语句的标号编号问题模板很简单但嵌套起来就麻烦了。先看这个if (x 0) while (y 10) y y 1;翻译过程中会涉及多层语句块的跳转标号管理。你手工在纸上推演没问题但写代码的时候就知道每个语句翻译都需要知道自己该往哪里跳、从哪里接着跳。经典的做法是给每个语句的翻译函数传两个额外的参数next这个语句执行完之后跳到哪里和break_continuebreak和continue的目标标号返回值是它生成的代码序列需要留下的未完成跳转链。这样从外层往内层递归翻译时外层把内层需要的break目标值传进去内层翻译完再把剩下的未完成跳转目标交给外层回填。用递归下降的思路来写控制流翻译比一口气生成完整跳转逻辑要清晰得多这也是为什么很多人的课程设计里中间代码生成都用递归下降而不是用YACC——YACC做语法分析很爽但往语义动作里塞翻译代码很容易把动作顺序搞乱。4.3 短路求值在控制流语句里的自然体现C语言里和||是短路求值的a b在a为假时不会计算b。这个语义在翻译if (a b)时是天然要求跳转的if a 0 goto L_false if b 0 goto L_false goto L_true L_false: 条件为假的代码 L_true: 条件为真的代码这跟上一节布尔表达式的翻译是配套的。如果你实现的编译器把翻译成先算出结果再判断真假也就是不短路那严格来说语义就已经错了——因为a b在a为假时要求b根本不被求值不短路等于改变了程序行为。注意的短路求值不是优化而是语言语义的一部分。同理if (p ! NULL p-value 0)这种代码在非短路语义下会直接崩溃所以翻译的时候千万别图省事把布尔表达式先整体算值。5. 布尔表达式的回填技术链条式管理待定跳转目标控制流翻译里最绕的一个点就是布尔表达式的回填。很多同学在中间代码生成这一章第一次接触回填这个概念觉得玄乎其实就是先把跳转指令生成好但目标地址暂时空着等条件算出来之后再回头把地址补上。5.1 为什么不能一次就把跳转目标全定下来假设你要翻译if (a b c d) S这个条件下面的S还没翻译你怎么知道条件为真时该跳到哪所以翻译布尔表达式时你只能先给每条跳转指令分配好位置但跳转目标用待定标记着。真正往回填的时候是等S的代码生成完之后才知道真分支的目标地址。这个先创建未完成跳转、最后回头填地址的机制就叫回填。为了知道哪些指令需要回填每翻译完一个布尔表达式你要记录两条链子——真链条件为真时跳转的所有指令列表和假链条件为假时跳转的所有指令列表。5.2 手工实现回填的一个简单思路用一个链表存待回填指令列表每个节点记着指令序号和一个指向跳转目标的占位符。翻译布尔表达式E1 E2时翻译E1生成if E1 0 goto ?这个?放进E1的假链。翻译E2同样生成跳转指令跳转目标待定。合并E1和E2的真链假链则保留两者各自的部分。等上层语句比如if知道真/假分支的真实地址后遍历这些链子把占位符替换成真实标号。实现的时候别忘了链表里的每个节点必须能定位到具体的跳转指令不然回填的时候不知道该改哪条指令的字段。四元式的result字段直接用指令序号回填就是往四元式数组的第几个元素里写目标地址数据结构选对了会省很多事。5.3 回填过程的一个完整例子拿a b c d做真链和假链演示。假设翻译顺序如下(104) if a b goto ____ ; 真链目标待定 (105) goto ____ ; 假链目标待定条件整体为假时到此 (106) if c d goto ____ ; 真链目标待定 (107) goto ____ ; 假链目标待定的结果是两个条件都为真才为真所以整体真链是104和106两条整体假链是从105和107两条分别跳出的链。等if语句翻译完知道了真分支的目标是L_true假分支目标是L_false就遍历真链把104和106的目标都改成L_true遍历假链把105和107的目标都改成L_false。这个机制的巧妙之处在于链是可以合并、可以拆分的嵌套表达式翻译时真链假链不断增长但每条跳转指令只属于一条链不会搞混。6. 从三地址码到SSA现代编译器的中间表示进化史到这里你已经掌握了经典教材里的中间代码生成全流程——三地址码、四元式、回填。但如果你去读LLVM的文档或者GCC的内核代码会发现现实世界的中间表示已经往前走了一大步。6.1 静态单赋值形式SSA到底好在哪静态单赋值Static Single Assignment, SSA的核心约束特别简单每个变量只能被赋值一次。如果要给同一个变量多次赋值就不断地创造新版本// 普通三地址码 x 1 x x 2 y x * 3 // SSA形式 x0 1 x1 x0 2 y0 x1 * 3光看这个例子你可能觉得SSA只是把变量改了个名。但它的威力在于当程序有控制流分支时一个变量在不同分支里可能被赋予不同值汇合之后到底取哪个这时候就需要phi函数也叫φ函数登场L_entry: if cond goto L_a else goto L_b L_a: v1 10 goto L_join L_b: v2 20 goto L_join L_join: v3 phi(v1, v2) // 从L_a来取v1从L_b来取v2有了SSA和phi函数很多优化的正确性判定就变得极其简单。比如死代码删除普通三地址码里你得做活跃变量分析才能判断一个赋值有没有被使用SSA里一个值如果从来没被引用删掉就行——因为每个变量只有一次定义引用关系一目了然。说实话本科编译原理课程能把经典三地址码和回填掌握好就已经很扎实了。SSA可以作为印象分去了解但不必在课程设计里硬上不然一个学期下来可能光在折腾phi函数的插入问题上。6.2 真实世界里的三种常见中间表示工程里的中间表示不只是四元式一种形态不同编译器选了不同路线中间表示代表编译器特点线性指令序列三地址码风格经典教材、某些Java编译器直观、容易翻译但优化信息少树形/图结构如AST直接优化某些脚本语言实现方便做高层优化但低层优化不顺手基于栈的字节码JVM、Python的bytecode指令紧凑、解释器实现简单但要进行数据流分析比较别扭GCC走的是GIMPLE路线一种把表达式拆到极简的三地址码LLVM走的是SSA形式的IRJVM走的是栈式字节码。有意思的是栈式字节码跟前两种都不太一样——它的指令没有显式操作数全靠栈顶数据来运算。比如i a b在JVM字节码里是iload_1 ; 把本地变量1a压栈 iload_2 ; 把本地变量2b压栈 iadd ; 弹出两个值相加结果压栈 istore_3 ; 弹出栈顶值存入本地变量3i这种设计让字节码非常紧凑解释器也简单但做优化的时候就需要先把栈式指令还原成类似三地址码的形式。这就是为什么Java的JIT编译器内部其实也是先做一次stack-to-register转换再进入优化流程。7. 实验里最容易翻车的三个细节最后分享几个在课程实验和实际写编译器过程中踩过的坑每一个都花了我不少时间才定位到。7.1 标号命名空间必须独立管理生成标号时如果直接叫L1、L2这种名字建议配合一个全局计数器。但更隐蔽的问题是if语句的真分支和假分支里如果各自包含另一个if内层if生成的标号可能与外层冲突。我见过有同学用if_1、while_2这种手工命名方式一旦嵌套层数变多就乱套了。最稳妥的做法是维护一个全局整数label_counter每次需要新标号就label_counter然后生成一个在源代码层面不可能出现的名字比如__L%d。临时变量同理。7.2 四元式的结构别拘泥于四个字段教科书上四元式是(op, arg1, arg2, result)但实际用的时候你会发现总有指令用不满四个字段。比如无条件跳转goto L实际上只有op和result两个字段取值运算t3 *t2需要一个间接寻址标志函数调用call foo需要参数的个数信息——这时候result字段塞的就不是变量名而是一个参数数量。灵活处理的方式是设计结构体加一个extra字段或者attr标记位。我建议你在一开始设计数据结构时就留好扩展位不然写到函数调用那一周天天都在改前面的数据结构定义。7.3 翻译完一定要做手推验证中间代码生成这个阶段几乎没有调试器能直接帮你检查翻译得对不对。我个人的土办法是找几段覆盖各种语法结构的测试用例把手推的中间代码写在纸上或者注释里然后跑程序比对自己的输出。比如测短路求值就用if (a ! 0 b / a 1)这种用例——如果生成的中间代码不短路运行时就会除零崩溃。测回填就用嵌套的if-else if-else if确保每个分支的跳转目标都是对的。写编译器这件事中间代码生成部分可以说是最像程序员日常写业务代码的一个阶段——它没有特别玄的算法就是一套又一套的规则翻译但规则一多边界条件就多边界条件一多就需要足够细心的测试来兜底。把这一章啃下来你对程序是怎么被计算机理解的这件事的理解会比前五章加起来都要深一截。