编译器开发反思

Posted on Nov 9, 2024

纵横计不就，慷慨志犹存

今年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. 在此基础上再寻找新的优化可能

而我们组就偏向于蒙头写代码，想到什么写什么了。

这里的教训时：如果对于名次还是比较在意，比赛开始时就应该早早搜集信息，明确目标。

团队管理的总结

开发出现问题的一个重要原因就是团队管理没有做好。虽然是四个人的小组，但大部分工作却由两个人完成。可以预想，如果只有两个人，开发效率反而会更高。或许，在开始时应该多了解一些团队管理的技巧的…

最一开始人们结成团队，肯定是拥有共同的目标。我们经过利益权衡后选择加入团队，以使得自己的利益最大化。可是加入团队后，却往往丢失了主动性，开始变得依赖管理者，并因为各种琐事而推脱团队事物。经常，只有管理者才一直把团队的利益放在心理（这是我在几次合作中的体会）。也许这也和不同文化有关，如「文化与组织」这本书里说的，华人在团队合作中往往习惯于集权，管理者往往具有更大权力，但相应的，成员也会更缺乏“主人翁意识”。在这种情况下，管理者正确运用自己的“权力”，做出更好地决策就更为重要了，在适当时候，不妨果断一些…

我在团队合作中感受到的问题有：

  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完成情况来了解每个人的动力值，及时给动力值不足的人重新分配任务
  • 学习
    • 系统化