# 编译器开发反思 > 纵横计不就，慷慨志犹存 今年5月到8月间参加了 CSCC 举办的编译系统设计赛，但实际上集中开发也就是7月。尽管达成了最初的目标——“学习编译器后端知识”与“找回写代码的感觉”，但最后的名次却不尽人意。虽然比赛8月早已结束，近日写总结也不算为晚（总还未完全忘记）。 # 我们的编译器实现 ## 前端 - 使用`antlr4`生成`lexer`和`parser`，构建抽象语法树（AST）。 - 采用访问者模式遍历AST，构建中间代码（IR）。 ## 中端 ### IR设计 IR结构设计参考了LLVM IR的设计，基本组件包括： - **Module**: Module是IR的顶级容器，用于表示一个完整的程序或翻译单元。它包含函数、全局变量和相关的元数据。 - **Function**: Function表示程序中的一个函数，由一系列基本块（BasicBlock）组成。每个函数在Module中唯一标识。 - **BasicBlock**: BasicBlock是IR中的基本执行单元，由一系列指令组成。每个基本块以终结指令（如`br`或`ret`）结束，并且在执行过程中不包含控制流跳转。 - **Instruction**: Instruction是IR中的操作指令，类似于机器指令。每个指令可以产生一个值，并作为其他指令的操作数。常见指令包括算术运算（如`add`、`sub`）、内存访问（如`load`、`store`）和控制流指令（如`br`、`ret`）。 - **Value**: Value是IR中的数据表示，包括变量、常量和指令的结果。所有的Instruction和Constant都是Value的子类。 ### IR优化 中端实现了各类优化，提升了代码性能。实现的优化包括： - **MemToReg**: 实现寄存器提升（Promote Memory to Register），减少内存访问。 - **CommonSubexpElimination**: 消除公共子表达式，减少重复计算。 - **MergeBlock**: 合并基本块以简化控制流图。 - **Inlining**: 函数内联，减少函数调用开销。 - **LoopSimplify**: 简化循环结构。 - **LoopInvariantCodeMotion**: 循环不变代码外提。 - **GlobalCodeMotion**: 全局代码移动。 - **GlobalValueNumbering**: 全局值编号，优化冗余计算。 - **LoopUnroll**: 循环展开，提高性能。 - **TailRecursionElimination**: 消除尾递归。 - **DeadCodeElimination**: 死代码消除。 - **ConstantFolding**: 常量折叠，计算常量表达式。 - **GlobalVariableLocalize**: 全局变量本地化，减少全局变量使用。 - **StrengthReduction**: 强度削减，用更低代价运算代替高代价运算。 - **LoadElimination**: 加载消除，减少不必要的内存加载。 - **Reassociate**: 重结合运算。 - **GEPSimplify**: 简化GEP指令。 - **CFGSimplify**: 控制流图简化。 - **StoreElimination.cc**: 存储消除，减少不必要的内存存储。 - **LruCache.cc**: 缓存递归纯函数的结果，避免冗余函数调用。 - **InductionVariableSimplify.cc**: 简化归纳变量。 ## 后端 - **Instruction Seletction**: 将中间代码转换为面向目标机器的低层IR。 - **Register Allocation**: 采用SSA分配算法，先溢出以减小寄存器压力，再对寄存器进行着色。 - **Peephole Optimization**: 实施一系列小规模的代码优化，如指令合并和消除冗余指令。 - **Instruction Scheduling**: 采用 Local List Scheduling 算法，进行简单的指令重排，并针对 SIFive u74 的双发射特性进行了优化。 - **Branch Simplification**: 实施和控制流相关的一些优化，如消除冗余跳转指令，基本块排序。 # 开发的流程与思路 ## 理想 vs 现实 最一开始确定的开发原则有两条： 1. 渐进式开发 2. 测试驱动开发 渐进式开发 主要指先实现 Sysy 的一个可工作子集，然后再不断扩充功能，直到实现完整的 Sysy 语言。在此之后慢慢增加各种优化。 这样做的好处有： 1. 在大部分时间都有一个可以正常运作的编译器，可以增强开发者信心 2. 每次实现一小部分功能，方便实现和测试 此外就是测试驱动开发，意思是每当实现一个功能时，先写好测试用例，然后进行开发。 这样做的好处有： 1. 开发时有一个明确的目标，增强动力 2. 每一部分代码都有测试，保证代码的正确性 同时编译器又可以分为前端，中端和后端三个部分。 最初的计划是小组四名成员，一人负责前端实现，两人负责中端框架实现，一人负责后端框架以及无优化下的翻译实现。在基本框架实现完成后进行调试，得到一个最简单的无优化编译器。之后再做进一步计划，渐进式不断增加新的优化pass。 然而这个计划却没有成功——我们前后中三端各自实现了一个月，才分别实现好，最后一起debug十余天后就到ddl了... 究其原因，是前端成为了我们的开发瓶颈。在后端和中端开发完成后，前端依然不能正常运行，以至于中后端bug无法及时暴露和修复。如果没有前端，中后端测试时只能通过直接调用API构造IR测试用例，但这又过于繁琐（当然也可以再实现一个 IR parser，这就更麻烦了，更何况有许多现成的 Sysy 语言测例可以利用）。所以我们还是选择等待前端完成后再debug，在这段时间抓紧时间实现一些优化 pass。但等到前端实现完成时，中后端也已经积累了非常多的bug，最后大把时间都花在了debug上... ## 陷入debug困境的原因 造成这样灾难性后果的原因主要有两点： 第一，**开发规划不明确**。 在一开始我认为前端较为简单，能在短时间内实现完整的 Sysy parser，而中端只是仿照 LLVM 实现，并不复杂（而且中前端的许多知识在本院课程中都已经学过）。所以实现一个可以 work 的无优化编译器应该并不困难。 可是当前端明显暴露出短板时，我才意识到直接实现一个完整前端的工作量较大，也许先实现一个 Sysy 的子集是更合理的。于是我告诉前端开发同学，“只要先实现 Sysy 的一个子集”，“能先跑起来就好”。可是当时的我却并没有 **明确规定** Sysy 的哪个子集？如果我不去明确规定划分，前端可能也不知道如何选取一个易于实现的子集——如果前端有选取易于实现子集的能力，那么显然他也能在短时间内实现完整个前端。所以，前端开发同学最后还是花了一个月时间，实现了一个充满 bug 的完整前端。 第二，**测试的基础设施不完善**。 其次是测试驱动开发中遇到的问题：在前端遇到瓶颈时，中端和后端仍然不管不顾蒙头开发。可是现在回想一下，尽管没有前端不能进行系统测试，但是对部分函数进行**单元测试**总是可以的。实际上我在编写代码时也对部分函数感到不放心，但还是决定先把问题放着，等到集成测试时再 debug ——最后的集成测试时就成了一场灾难。实际上，c++虽然没有 rust 那么方便做单元测试，但是也有 Google test 等框架来帮忙。在前端迟迟没有完成的情况下，单元测试就更为必要了。 第三，**出现问题时没有及时调整分工**。 在前端遇到瓶颈时，当时更优的解决方法其实应该是让后端和中端的同学去协助前端，而不是让他们仍然开发各自模块。但是因为前端同学总是承诺马上就要做完了（实际上却一拖再拖），一直到20余天后中端开发同学才去帮忙实现。承诺往往是不可靠的，进行计划调整时其实应该更重视过往经验，而非开发人员的口头承诺。 ## 亮点不充分的原因 这里的亮点指我们在比赛中与其他队伍相比，较为亮眼的部分。当然，最后就成绩来看，也并没有什么非常亮眼之处了。 大部分组的亮点基本可以分为以下三类： 1. 出色，完备的代码 2. 实现了好的算法 3. 优秀的基础设施 因为赶工，基本就不求 基础设施 和 代码质量 ... 可能唯一值得一提的是算法。 中端参考了往年代码，实现了大部分的常见优化。后端在寄存器分配时使用了基于弦图的SSA分配算法，并且针对硬件做了简单的 Instruction Scheduling。不过SSA分配算法带来的性能提升并不大（实现上也略有粗制滥造之处），指令重排也是后期临时添加，提升效果非常有限。尽管如此，因为中后端优化实现的都比较完全,在初赛时也有一个不错的成绩。 但8月因为种种事情，在决赛以及之前并没有做多少新的优化，而其他组这期间大都在中端做了许多激进的优化：如函数记忆化，数组访问优化，以及一些针对特殊用例的优化。 最后也得知，许多队伍都参照了往年代码（这也就是比赛为什么一年比一年卷的原因），因此他们的目标很明确： 1. 实现往年第一名实现过的所有优化 2. 在此基础上再寻找新的优化可能 而我们组就偏向于蒙头写代码，想到什么写什么了。 这里的教训时：如果对于名次还是比较在意，比赛开始时就应该早早搜集信息，明确目标。 # 团队管理的总结 开发出现问题的一个重要原因就是团队管理没有做好。虽然是四个人的小组，但大部分工作却由两个人完成。可以预想，如果只有两个人，开发效率反而会更高。或许，在开始时应该多了解一些[团队管理的技巧](https://wiki.mbalib.com/wiki/%E5%9B%A2%E9%98%9F%E7%AE%A1%E7%90%86)的... 最一开始人们结成团队，肯定是拥有共同的目标。我们经过利益权衡后选择加入团队，以使得自己的利益最大化。可是加入团队后，却往往丢失了主动性，开始变得依赖管理者，并因为各种琐事而推脱团队事物。经常，只有管理者才一直把团队的利益放在心理（这是我在几次合作中的体会）。也许这也和不同文化有关，如「文化与组织」这本书里说的，华人在团队合作中往往习惯于集权，管理者往往具有更大权力，但相应的，成员也会更缺乏“主人翁意识”。在这种情况下，管理者正确运用自己的“权力”，做出更好地决策就更为重要了，在适当时候，不妨果断一些... 我在团队合作中感受到的问题有： 1. 信息交流不足 1. 几个陌生人组队，很容易陷入尴尬状态，不能充分讨论，博采众长。 2. 此时就需要管理者破冰，主动召开会议，客观分析现状，让每个都发言，都能有参与感 1. 这样经过充分讨论做出的决策，每个人也更认同 2. 动机不足 1. 偷懒是人的天性... 尤其是成员，如果管理者没有分配任务，明确目标，就很容易偷懒 2. 所以就需要管理者主动给每个人分配有明确验收标准的任务，并确定DDL 3. 难以决策 1. 可能因为华人文化的特点，大家都习惯于听从管理者的命令，不愿意主动提出自己想法 2. 此时决策就需要管理者更自信一点，去一锤定音了 1. 虽然大家没有明确提出自己意见，但是他们认同决策与否可以通过执行决策是否积极来判断 2. 但发现大家的动力不足时，应该主动了解原因，调整决策 # 后端知识学习经验 我主要负责后端的实现。因为之前对于编译器后端了解较少，实现时也在短时间内学习了大量新知识。 在学习新知识时，往往会遇到许多困难。比如在学习某个寄存器分配算法时，我会先去看看一些经典的大部头教科书，提出算法的 paper，以及相关课程的slide，或者 youtube 上的讲解视频，最后是一些程序员的博客，中文所写的综述。不过在学习时我也并没有明确规划，而是这个看一点那个看一点，最后还是感到一头雾水。 经典教科书的问题有： 1. 英语所写，较难抓住重点和关键的思想；工作记忆有限，梳理不清条理 2. 都是讲最经典的实现，用简单的例子慢慢引入，学习时较为耗费时间，且很难知道研究现状和该问题各种算法的综合比较 paper的问题有： 1. 因为阅读经验不足，也难抓住重点 2. context较多，就会变得难以理解；而且不知道该论文在领域内处于一个什么样的位置 slide的问题有： 1. 虽然能抓住核心，但太简略难懂，许多图像意义需要脑补，不好理解 youtube视频以及博客的问题有： 1. 虽然许多资料深入浅出，但许多深入内容的较少，也有许多价值不高的内容 .... 经过一些挫折后，我尝试着给出一个较为系统化的新知识学习方案，也许能以后作为参考。 1. STFW 搜集各种信息，并分类整理搜集到的信息 2. 了解相关背景知识和发展历程，心里有一个大概的框架 3. 深入学习其中一个经典案例，搞清楚核心的思想，基本的抽象；这一步可以做一些笔记，或者在草稿纸上模拟，以加深理解 4. 再去搜集一些综述，了解该领域发展现状，能有一个更细致的框架 5. 此时根据自己的目标 以及 刚刚学习到的框架，为目标选择一个适合的目标算法，然后去学习 6. 当选定目标算法并实现时，可以参考开源项目代码以及开发人员的实现相关博客 # 总结 + 项目 + 明确规定目标：可以文档化规范化需求 + 完善基础设施：既有集成测试，也有单元测试 + 及时识别瓶颈并处理 + 留够时间做killer feature + 管理 + 交流：充分协商，打开思路，让每个人获得参与感 + 动机：设置ddl + 决策：果断决策，不断迭代（对于集中式团队） + 比如：通过ddl完成情况来了解每个人的动力值，及时给动力值不足的人重新分配任务 + 学习 + 系统化