1. 区间图：用于局部寄存器分配，基本块内的每个活跃范围看作一个区间（最早定义位置+最新使用位置），所有活跃范围构成区间图。区间图是一种不精确的冲突图（因为高估了活跃范围的范围而导致伪冲突，比如认为一个复制操作连接的或两个源相同目标不同的复制操作产生重叠的两个活跃范围冲突，但实际没有冲突），优势在于着色是P（复杂度O(|V|)或O(|E|)）而非NP问题。llvm早期的线性扫描分配器是基于区间图在全局的扩展，比较适用于JIT编译（减少编译时间）
2. 一般图：用于全局寄存器分配，是一种精确的冲突图（由一组定义与一组使用构成的网络）。优势在于努力最小化溢出活跃范围而生成高效执行的代码，但会牺牲编译时间。llvm的greedy寄存器分配是基于一般图的代表。编译器使用的冲突图可能会将机器约束条件比如多寄存器值/调用约定编码进去而存在重复边，导致不满足图论中的简单图定义，故这里采用一般图
3. 弦图：定义详见
https://oi-wiki.org/graph/chord。基于静态单赋值形式名建立的冲突图是弦图。优势在于可以做到最佳着色（复杂度O(|V|+|E|)）而非启发式（基于一般图的全局寄存器分配使用启发式），利于减少寄存器压力。劣势在于必须将指派寄存器后的仍然为静态单赋值代码转换为机器码，而这种转换可能增加寄存器压力，以及插入一些可能非必要的复制操作，若复制操作实现的数据流与ssa phi函数对应，则分配器无法合并这种复制，这将破坏弦图的性质
4. 冲突图拆分：查找其中的团分割即连通子图，移除它划分得到不相交的一些子图，这样一来，各子图可独立着色（有点类似活跃范围拆分）而利于减少寄存器压力，另外实现上还能节省下三角布尔矩阵（用于快速判断两结点是否冲突）的规模
#############################
寄存器分配与图论的染色理论相关。其它的比如常量传播与格代数及不动点相关，循环优化与多面体、矩阵相关。这三方面是我目前看到的编译器所用数学理论
posted on 2023-10-04 13:08
春秋十二月 阅读(3794)
评论(0) 编辑 收藏 引用 所属分类:
Compiler