冲突图
复习
- 活跃变量分析：得到各变量的活跃区间
- 图：用节点和边表示关系
- 寄存器分配：把值映射到寄存器
TL;DR
- 冲突图把“不能共用寄存器”的变量连起来
- 节点是变量，边表示它们的活跃区间重叠
- 寄存器分配由此变成图的着色问题
- 它把分配问题抽象成了图论问题
正文
上一章得到了每个变量的活跃区间。现在要把“谁和谁不能共用寄存器”这件事，画成一张图——冲突图（interference graph），也叫干涉图。
同时活着，就画一条边
冲突图的构造非常直接：
- 节点：每个变量是一个节点
- 边：如果两个变量的活跃区间有重叠（也就是它们会同时活着），就在它们之间连一条边
这条边代表“冲突”：这两个变量不能共用同一个寄存器，否则一个会把另一个的值覆盖掉。
反过来，没有边的两个变量，就说明它们的活跃区间不重叠，可以共用同一个寄存器。
分配 = 着色
有了冲突图，“分配寄存器”这个问题就变了个模样：
给每个节点上一种“颜色”，颜色代表寄存器；要求相邻的节点颜色不同。
这就是图论里的着色问题（graph coloring）。可用颜色的数量，就等于可用的寄存器数量。
这么一转化，好处太大了：寄存器分配本来是个零碎的工程问题，现在成了一个有成熟算法和图论结论的问题。把实际问题抽象成已知的数学问题，正是计算机科学里屡试不爽的招数。
那么，如果颜色不够用（寄存器不够），该怎么办？下一章揭晓。
思考题 1
冲突图的节点和边，分别代表什么？
思考题 2
为什么寄存器分配可以转化成“图着色”？
小结
知识点
- 冲突图以变量为节点
- 活跃区间重叠的两个变量之间连边
- 有边表示不能共用寄存器
- 寄存器分配等价于给冲突图着色
参考资料
- Wikipedia(zh)：寄存器分配：以冲突图为基础的分配
- Wikipedia(zh)：图着色问题：给相邻节点着不同颜色
思考题答案（仅供参考）
思考题 1
节点代表一个变量（一个需要存放的值）；边表示这两个变量的活跃区间重叠、会同时存活，因而不能共用同一个寄存器。
思考题 2
因为“不能共用寄存器”正好对应“相邻节点颜色要不同”：把寄存器看成颜色，只要相邻节点异色，就保证同时存活的变量不会共用寄存器。于是分配问题就等价于给冲突图着色。
协议
本作品采用知识共享署名-非商业性使用-相同方式共享 4.0 国际许可协议进行许可。
封面图
设计师 | 南国微雪