做编译实验做到“优化和目标代码生成”这一步很多同学都会有一种“前面都白学了”的错乱感。前面几个实验好歹还能对着语法树、符号表单步调试到了实验六题目直接扔给你一段中间代码让你“优化一下”再“生成目标代码”评分系统跑几个用例错一个就是零分。我当初在这个实验上卡了将近两周中间代码优化的部分看似简单但真正的坑几乎全部藏在“怎么保证优化前后语义一致”和“目标代码生成的寄存器怎么管理”这两件事里。这篇博客就围绕我在这门课的PTA平台上实验六的完整实践来写内容包括实验题目的常见形态、我自己选择的优化策略与实现顺序、目标代码生成时的指令映射和寄存器分配思路以及我在测试过程中遇到的一个能让你排查到崩溃的经典问题。无论你是刚开始做这个实验还是已经写完但卡在最后几个测试点这篇内容应该都能给你一些直接能用的参考。文章里涉及的代码和伪代码都以我实际采用的简化方案为准不同学校、不同平台的具体格式要求可能有差异但背后的思路是通用的。1. 实验到底让你做什么从题面拆解到评分逻辑1.1 实验题面的典型形态我这次拿到的题目核心内容分两个阶段第一阶段是输入一段类三地址码的中间代码要求做若干优化后输出第二阶段是在优化结果的基础上生成目标汇编代码。听起来很清晰但实际操作之前必须先弄清楚两个问题输入格式长什么样、输出格式要怎么对齐。PTA平台上这类实验通常会给一个固定的输入文本结构大概是这种样子t1 2 3 t2 a t1 t3 a t1 x t2 * t3每行一条三地址指令变量是字母加数字的组合临时变量用t开头常数是十进制整数。题目要求优化的部分往往会有“消除公共子表达式”“常量折叠”“删除死代码”等关键词但不会告诉你具体用哪几个策略而是通过测试用例隐式考察。第二个阶段的目标代码生成常见要求是输出一套简化汇编比如类似RISC风格的指令集合。每一条三地址指令需要被翻译成若干条目标指令寄存器数量有限。这时候就牵扯到寄存器分配策略而你写死几个寄存器、每个变量住在哪个寄存器里都会直接影响到输出能不能通过比对。1.2 评分与判题机制决定了优先级我记得刚开始做的时候总想着把优化做得越“高级”越好结果一上来就实现了循环不变式外提和线性扫描寄存器分配代码写得特别复杂然后发现PTA平台判题根本不认我的格式——有几个输出行的空格数量和缩进风格跟样例不一致全部被判错。折腾了一整天才明白这类实验的评分通常有两种模式。第一种是文本比对模式平台把你的输出和标准输出做逐字符比对哪怕多一个空格、少一个换行都会被判错。这种模式下优化是否彻底反而不是第一优先级输出格式必须和题目样例完全一致才是保分的关键。第二种是运行验证模式平台把你生成的汇编代码拿去编译运行通过输入数据来验证输出结果。这种模式更考验代码生成的正确性只要结果对中间过程怎么安排寄存器、是否做了优化原则上不影响得分但前提是运行时不崩、不产生未定义行为。我做的这个实验偏向第一种模式所以我的第一原则是先把输出格式摸清楚再谈优化深度。建议你们拿到题目之后先写一个最朴素的“逐行翻译”版本不做任何优化存粹把输入文件读进来、按照原顺序输出一遍或者生成一个最基础的目标代码版本提交一次看看判题系统是否给出“格式错误”“答案错误”还是“通过”。这一步能帮你快速确定平台的判题导向比闷头写完整程序再提交要高效得多。2. 中间代码优化先跑通“手动可验证”的四种经典优化2.1 优化的选择性价比最高的组合实验要求里提到的优化手段其实有很多常量折叠、常量传播、复写传播、死代码删除、公共子表达式消除、循环不变式外提甚至更激进的算法。但作为一个学期末的实验我认为没有必要把所有优化都实现一遍因为判题用例基本集中在几个容易考察的层面上。我自己最终实现的是下面四个它们组合起来已经能应对绝大多数用例优化类型作用适用场景常量折叠把编译期能算出来的表达式直接算成常数t1 2 3变成t1 5常量传播把已知常数的变量代入后续使用处t1 5; t2 t1 1在折叠后变成t2 6复写传播把x y这种复制语句中的x用y替换前提是中间没有被重新赋值t2 t1; t3 t2 1变成t3 t1 1如果t1此刻仍是原值死代码删除删除后续不被引用、且没有副作用的赋值语句一个临时变量被赋值后再也没有被读取可以整行删掉这四个优化点实现起来不复杂而且每一个都可以独立验证。我的建议是不要一次性全部写完每写完一个优化就先用一个小例子手动推演一遍确认输出符合预期再叠加下一个。2.2 公共子表达式消除从“看着像”到“确定是”公共子表达式消除Common Subexpression EliminationCSE是这四个优化里稍难的一个但它非常容易出现在判题用例里。上面的例子中t2 a t1 t3 a t1这里a t1被计算了两次第二次可以直接引用第一次的结果t3 t2。然后再通过复写传播把后续使用t3的地方替换为t2进一步消除这个复制语句。实现CSE的关键是给每个表达式建立一个“键”。你不能再按字符串匹配因为a t1和t1 a在加法的语义下是同一个表达式但在减法、除法下不是。我的做法是把表达式标准化成一个元组(操作符, 操作数列表)其中操作数如果是由常数折叠得到的数值就先换成折叠后的数值否则保持变量名不变。然后维护一个从表达式元组到“当前可用的临时变量名”的映射表每当遇到一个形如t A op B的三地址指令就查一下映射表里是否已存在等价表达式如果存在就把t替换为之前那个结果变量并记录t和那个变量之间的复写关系。这里有一个非常关键的坑CSE的作用范围不能跨越赋值语句。假如中间某条指令重新修改了a或t1的值那么后面的a t1和前面的a t1语义上就完全是两回事。我第一版实现没做这个检查直接全局查表导致一个测试用例把a重新赋值之后后面的表达式仍然复用了旧结果输出完全错误。后面在代码里加入“变量重定义时清空涉及该表达式的映射项”的逻辑才算真正解决。2.3 活跃变量分析死代码删除的数学基础死代码删除听起来很简单一个变量被赋值后没有被读取就能删掉。但“没有被读取”不能只看这一行之后到函数结尾因为变量的生存范围可能会被跳转语句改变。虽然实验里的输入大多是顺序结构但保险起见我还是实现了经典的数据流分析思路——活跃变量分析Liveness Analysis。活跃变量分析是一个反向数据流问题也就是说要从基本块的出口往入口方向传播信息。我简化后的思路是每个基本块先收集use集合在赋值前被读取的变量和def集合被赋值的变量。 初始情况下出口活跃变量集合为空。 反复迭代对于基本块入口活跃 use ∪ (出口活跃 - def)。 当前后两轮迭代结果不再变化时分析结束。有了活跃变量信息死代码删除的判断就非常准确一条形如x 表达式的指令如果表达式里不包含任何可能产生副作用的内容调用函数、访问数组等并且x在指令出口处的活跃变量集合中不存在就可以安全删除。这样做的意义在于不是“看着像没用的代码”就删而是用严格的数学定义证明它确实算死代码。在写实验报告的时候这一步也能帮你加分因为能体现出你真的理解数据流分析而不只是用了某个现成库。需要注意的是这个实验输入的三地址码通常不包含函数调用所以“副作用”的判断在大多数情况下是安全的。一旦题目扩展出函数调用删除一条赋值语句就可能需要更保守这里就不展开了。3. 目标代码生成从三地址码到目标汇编的朴素实现3.1 指令映射模板先把每条指令翻译对优化做完之后输入到代码生成器的三地址码已经比较“干净”了。目标代码生成阶段的核心任务是把每一条类三地址指令映射到一段目标指令序列。我用的目标平台是一套简化指令集包含load、store、add、sub、mul、div、label、jmp、beq等基本指令和许多编译原理教材里用到的教学汇编很像。我建立的映射模板如下三地址指令目标指令序列示例说明x y zload r1, y; load r2, z; add r1, r1, r2; store x, r1y和z先在寄存器中运算结果从r1写回xx y * zload r1, y; load r2, z; mul r1, r1, r2; store x, r1乘法只是操作符不同模板完全一致x c常数赋给变量load r1, c; store x, r1常数直接加载到寄存器x yload r1, y; store x, r1复制语句也可以做寄存器复写但朴素方案下先落地内存更安全goto Ljmp L无条件跳转if x y goto Lload r1, x; load r2, y; bgt r1, r2, L条件跳转指令需要专门设计label Llabel L:直接映射成标签这个阶段我犯过一个印象深刻的错误在映射x y z时先load r1, y再load r2, z结果发现如果x恰好是某个寄存器已经保存的变量那么store的目标会覆盖掉这个寄存器之前保存的值下一轮使用该寄存器时数据就错了。这里真正的问题在于寄存器分配策略不够严谨而不是指令映射模板本身有问题。3.2 寄存器分配的朴素策略固定池加溢出实验中最痛苦的部分其实就是寄存器不够用怎么办。我一开始天真地认为只要每个变量固定占一个寄存器就行结果寄存器数量有限而测试用例里的临时变量动辄几十个。我采用的方案是一个固定的寄存器池比如 4 个通用寄存器 r1 到 r4。每个三地址指令需要用到临时寄存器时按顺序从池中取如果池空了就把当前某个寄存器的值“溢出”到内存中的一个临时槽位然后腾出寄存器给新变量。这里的溢出spill本质上就是把寄存器里的值store到内存、下次用到时再load回来。虽然类似线性扫描寄存器分配的算法能做得更聪明但实验场景下朴素的“取用完就释放”策略往往是够用的。我的做法是把每条三地址指令看成独立的小片段每个片段内部使用寄存器后立即将结果store到目标变量对应的内存位置随后这些寄存器就可以重新分配。这样寄存器池永远不会因为跨指令的变量生命周期而耗尽。不过这导致生成的代码非常冗余比如每一行都会伴随多个load和store。可毕竟实验的判题标准是正确性而冗余指令在文本比对模式下只要不改变格式就可以接受所以这个方案通过率很高。如果你精力充裕可以对连续使用同一寄存器的情况做一个简单优化如果上一条指令结束时的r1恰好是我们下一条需要的值就不重新load。我后来加了这个“寄存器缓存”机制代码长度直接减少了差不多三分之一运行时也快了不少。3.3 为什么建议先单独跑通“没有优化版本”的生成器在正式做优化之前我强烈建议你先完成“不做任何优化直接把原始三地址码翻译成目标代码”的版本并确保这个版本能通过运行验证。这样可以在最大程度上把“代码生成正确性”和“优化正确性”两个问题隔离开。如果连未优化版本的目标代码都不能通过那么优化之后出问题你根本不清楚是优化步骤引入的bug还是代码生成器本身的bug。当时我就是把这个未优化版本当作基准线。每次实现一个优化策略跑一遍同样的测试用例如果输出结果和基准线的运行结果一致说明这个优化没有破坏语义如果结果不同就说明优化逻辑里有问题。这个方法帮我排查问题节省了大量时间。4. 一次让我排查到深夜的“复写传播”bug完整链路复盘4.1 症状只有包含复制语句的用例会错我实现完复写传播之后跑了三个测试用例其中一个立即报错另外两个通过。报错用例的输入大概是这样的t1 a b t2 t1 a 3 t3 t2 1 x t3我的复写传播逻辑在遇到t2 t1时把后续所有用到t2的地方替换成了t1。所以t3 t2 1被我改写成了t3 t1 1。问题就在于t2是在a 3之前被赋值的而t1 a b使用的是赋值前的a。但a 3这条指令重新定义了a如果我继续把t3里的t2替换成t1那t1 1使用的a已经是新值和原程序的语义完全不一致。原程序里t2其实保存了a b这个值在某个时刻的快照——尽管t1的值等于旧的a b但在a被重新赋值之后再用t1去计算t3用的已经是被覆盖过的t1如果t1也被更新的话或旧值。正确的做法是只有当t1从定义点开始到“使用点”之间都没有被重新赋值时复写传播才是安全的。这个条件我没有做到于是数据在“复制”到一半的时候“变质”了。4.2 排查链路从生成代码反推优化结果这个bug的排查过程比我想象中麻烦因为它不像数组越界那样会直接崩溃而是算出一个错误但合理的数值。我的排查步骤大致是这样第一步把优化后的中间代码打印出来和原始输入逐行对比。这一步很快就看到了问题t3 t2 1果然被替换成了t3 t1 1而且t1在使用点之前并没有被重新赋值。但这里我忽略了关键点t1虽然没有被重新赋值可t1所依赖的a被重新赋值了通过“依赖链”间接影响了t1的取值。第二步跟踪t1的定义t1 a b。既然a在t1定义之后、t3使用t2之前出现了重定义那么t1已经不是那个“旧快照”了。这里我意识到我的复写传播只检查了“复写关系中源变量是否被重新赋值”但没有检查“源变量所依赖的变量是否被重新赋值”。第三步也是最危险的一步当我试图启用变量定义链追踪来解决这个问题时发现需要对整段指令建立比较完整的定义-使用链。这才符合教科书里所说的“复写传播需要数据流分析信息”。于是我把复写传播从“字符串替换”改成“基于定义点列表的安全替换”在传播一条复写关系x y时要求x、y以及y的活跃定义变量在传播路径中都没有被重定义否则就停止这条传播。4.3 修复方案与验证最终的修复并不复杂维护一个“失效变量集合”每当遇到v ...的赋值指令时把所有已经记录的、复写关系中源变量或目标变量包含v的条目标记为失效之后这些条目不再参与替换。比如上面例子中遇到a 3时由于t1 a b定义了t1且t1依赖a那么涉及t1的复写关系t2 t1就自动失效后续t3 t2 1就不会被替换成t3 t1 1。修复之后的验证方法也很直接跑了一遍所有测试用例并和未优化版本的目标代码输出做运行结果比对。全部通过。这个经历给我的教训是复写传播看起来是最简单的优化但它对数据流信息的要求一点都不低千万不要觉得“一行复制嘛能有什么问题”。4.4 另一个隐藏的坑输出格式的精确对齐除了优化逻辑本身格式化输出也折腾了我不少时间。PTA平台上的很多题目对输出的模板要求非常严格包括标签后面有没有冒号、寄存器的名字是不是小写、每行末尾有没有多余空格等等。我一开始生成的汇编代码里标签行是L1:而标准样例是L1后跟一个空格再加指令这类细微差别很容易被误判成“答案错误”。经过反复尝试我总结出一个高效套路先从上传的“样例输入输出”里提取出完整的格式模板然后把自己的生成结果逐字符对比。不要用肉眼对比最好在命令行里用diff或者写个脚本逐行比较定位到第一个不一致的位置再修改生成逻辑。我在这个环节花的时间甚至比调试复写传播bug还多但确实很值因为一旦格式对了整个实验的通过率会一下子拉高。5. 进阶扩展窥孔优化与后续可以自己折腾的方向5.1 窥孔优化清理代码生成阶段的“垃圾指令”当代码生成器稳定运行之后我尝试在生成的汇编代码上做了一轮窥孔优化Peephole Optimization。所谓窥孔就是在一个小的滑动窗口内观察相邻指令寻找可以合并或删除的模式。比如load r1, x store x, r1如果load和store之间没有其他修改x的指令那么这两句相当于什么都没做可以删掉。还有一种常见模式是连续两次load同一个变量第二句也可以省略。我的实现非常简单把生成的汇编指令按行存进列表用一个长度为3的窗口依次扫描匹配到预设的冗余模式就删除。循环几轮直到没有变化。这一轮优化让代码量减少了不少而且没有影响正确性。如果你实验已经做完非常建议试一下这个方向因为窥孔优化对逻辑的要求不高但代码量一看就是“做了优化”。5.2 更彻底的寄存器分配从实验到工业级的距离实验阶段的朴素寄存器池方案在功能上是完备的但离实际编译器的寄存器分配还有很大距离。比如线性扫描寄存器分配算法需要你先为每个变量计算活跃区间live interval再按区间端点排序最后按区间分配寄存器必要时进行溢出。图着色算法则把寄存器分配看成图着色问题每个变量是一个节点变量之间的活跃冲突是边颜色数量就是寄存器数量。这些算法在真实编译器里非常成熟但要在实验范围内实现一遍工作量会翻好几倍。以我的经验来说如果你只是想完成实验并通过评分不必碰这些高级算法但如果你想趁这个机会把编译原理后端吃透可以试着把活跃区间计算的模块写出来哪怕只是输出每个变量的live range也足够你在报告里写出非常有深度的内容。5.3 给后来人一个明确的验收清单最后整理一份我在做实验时对照用的清单防止漏掉关键点输入解析是否正确三地址码的格式是否完全按照题目描述读取优化前的“基准生成器”是否能稳定通过运行验证每种优化是否单独用一个用例验证过再叠加其他优化格式是否符合平台样例标签、寄存器名、空格、换行是否逐一比对生成的汇编代码是否在语义上等价于原始三地址码尤其在“变量被重定义”的场景下是否有越界寄存器或内存槽位使用注意寄存器池是否满这份清单如果全部打勾实验基本就能稳过。不要急着投入大量的时间到循环不变式外提等高级优化先把基础正确性和格式保证好这才是PTA这类平台真正的得分命门。写到这里实验六本身的内容基本讲完了。回想整个过程最值得的其实不是最后那个分数而是我意识到“编译优化”这四个字背后每一个微小的变换都必须有严格的数据流依据。你在中间代码上看似随手做的复写传播背后是定义-使用链的完整逻辑你不做检查的CSE很可能在隐蔽的语义错误中毁掉一整段代码。这些经验在以后写解释器、写静态分析工具甚至做数据库查询优化的时候都会用得上。最后分享一个我个人的小习惯每一次只改一个环节改完立刻拿基准用例回归不要让多个未知变量叠加在一起排查那样会消耗掉你所有的耐心。希望这篇记录能对你的实验有点帮助。
