作者为了学习优化编译器的制作，针对 6502 架构构建了一个编译器，其生成的代码比 GCC、LLVM 及其他编译器都快。

• 作弊免责声明：编译器有三个优势，一是生成“非法”指令，二是花费大量 CPU 预算进行指令选择，三是进行循环展开等空间换时间的优化，但这些在不同编译器间难以公平比较。

• 快速概述：算法基于多年前的动画系统，结合了指令选择与寄存器分配，用延续编写。将 IR 的基本块表示为有向无环图的 SSA 形式，先打破这两个属性，生成多个组合，用动态规划和分支定界法修剪，将基本块输出作为后继输入，应用模拟退火找到结果，最后插入额外指令并进行优化。

  • 基本块 IR：每个基本块的 IR 是有向无环图的 SSA 形式，节点表示值，边表示数据流向，是一个依赖图。
  • 排序：用拓扑排序创建节点的全序，但 DAG 有多个有效排序，可通过添加“假”边和贪心算法影响排序，优先选择图中最长路径的节点，以减少寄存器压力和存储。
  • 基本块指令选择 - 部分 1：动画：基于 NES 游戏动画系统，通过展开循环生成快速代码，对于有多个寄存器的情况，用 brute-force 搜索和修剪组合来优化加载指令，用哈希表存储和比较组合。
  • 基本块指令选择 - 部分 2：编译器：将算法应用于 IR 操作，生成组合并修剪，考虑不同 IR 操作生成的不同汇编指令和“cpu_state”结构体，最后通过额外的 passes 去除不必要的存储指令。
  • 基本块指令选择 - 部分 3：延续：用延续将编译 IR 操作的细节抽象化，创建构建块，用组合函数覆盖多种汇编序列，更易编写。
  • 控制流 - 部分 1：基础知识：算法可处理控制流，为每个基本块分配标签，生成单独的代码并连接。
  • 控制流 - 部分 2：优化：分别编译基本块会导致冗余加载，通过传递基本块的结果作为输入来解决，类似模拟退火过程，直到达到固定点。
  • 控制流 - 部分 3：一些加载需要：仅选择最低成本的组合会导致输入输出状态不匹配，需要插入加载指令，这是一个优化问题，类似于 PBQP。
  • 控制流 - 部分 4：PBQP：用 PBQP 求解器选择最优组合，可解决控制流中的问题，使代码更优。
• 复杂度和性能：创建顺序复杂度约为 O(N²)，去 SSA 复杂度假设为 O(N²)，基本块代码生成复杂度为 O(N)，PBQP 问题复杂度为 O(N)和 O(N³)，反复生成基本块复杂度较高但模拟退火后为 O(N)，缓存 miss 可避免。
• 结论：编译器效果良好，延续使添加新操作容易，生成的代码不错但不是最好，作者对其他代码生成技术了解不多，现在的算法更适合 RISC 架构。