编译器资料
记录编译器写了什么以及目前的思考
参考资料
- Engineer a Compiler ：涵盖了写编译器过程中各种问题，但感觉更为适合带着问题去找答案
- 现代编译原理 ：主要看了寄存器分配的章节，写的非常清楚，可以给到夯
- Mx编译器手册 ：作为索引不错，刚入手时从里面了解到“该做什么”
asm
先将ir中的phi去除掉，去除的方式是改用move语句代替，这里并非汇编中的’mv’，因为一部分的move可以在后面的寄存器分配中得到优化。这里存在一些数据冲突的情况，可能需要插入额外的块来解决。phi具有一个性质，一个块中的赋值是并行的，因此需要特别处理交换数据的情况。
graph-coloring
虚拟寄存器是无限的，但物理寄存器是有限的。为了提高效率，需要找到最合理的将物理寄存器分配给变量的方式。若运行的同一时刻两个变量同时需要被记录，则它们无法记录在同一物理寄存器中。由此性质可以建立冲突图，将每个变量抽象为节点，存在活跃冲突的节点间连边。寄存器分配问题被转换为了如何使用K种颜色为该图着色，使得任两个相邻节点颜色不同的图着色问题。判断染色是否成立为一NP难问题，我们实现启发式算法使得溢出尽可能少的点的情况下，染色成立。
对于一条move中的两个变量，两者在一些情况下实际不存在冲突，如仅在phi的消除时出现。此时将其规划在一个物理寄存器中是合理的。在建图时我们为这些边做特殊的标记，在染色过程中可以将其合并。
在染色前，图中会存在K个预着色的节点，它们间相互冲突。这些代表机器寄存器，它们的度数应当设为无限大，因为它们永远不会被溢出或简化。一个被使用的机器寄存器会存在活跃范围（如一个函数参数），因此也会和普通变量产生冲突。
执行算法时，我们重复以下操作：
- 找到所有度数小于K且不包含move边的节点，直接删除。这些节点一定可以合理染色
- 寻找move边相连的节点，若能够合并则合并为一个点
- 放弃某个move边，将其视为普通边
- 将一个节点从图中删除，标记为溢出
删除的节点被记录在栈中，当所有节点都被删除，再尝试对原图染色，将节点从删除的栈中弹出依次染色，若存在不可染色节点，将其实际溢出，在块中插入load和store，随后重复整个流程，直到染色可行。
合并操作中，应当选择不会使图的性质变得更坏的判断标准，即我们不希望合并后的图从可着色变为不可着色。常用的标准有
- Geroge：对a的每一个邻居t，t的度数小于K或者t与b冲突。
- Brigg ：合并后产生的节点所拥有的度数不小于K的邻节点个数小于K。
Brigg 实际表明，合并后的节点可在简化（步骤1）中被消除。而 George 表明 a 合并到 b 不会影响 b 的合并情况。当两个节点中存在一个是物理寄存器时，我们应该选用 George，因为显然 Brigg 期望合并后的点被简化掉。当然，我们实现时不妨让两个约束满足其一即可。
在图染色过程中，被标记溢出的点并不意味必定溢出。重新染色时，可能存在某个度数>K的节点相邻点中有颜色相同的，从而可以染色。这被称为“乐观”溢出，这也说明我们仅在寻找一个近似的解。
删除高度数节点时，优先选择判据有很多种，如度数最高，活跃区间最长等，个人认为对效果的影响没有那么大，在实现中，选择优先删除度数最高的节点。
听说存在一种在ssa上进行的寄存器分配。但ssa形式的代码必定需要被转换为其它格式，这会导致额外的寄存器需求，如果有时间可能会研究一下这个方案。但个人认为效果上不会比图染色明显优秀，但是是一种非常优雅的线性方案。