时间戳

首页 > 解决方案 > 溢出符号不会提高可着色性

compiler-construction - 溢出符号不会提高可着色性

问题描述

假设我有一些代码的中间表示：

t1 = 1
t2 = 2
t3 = 3

t4 = t1 + t2
t5 = t3 + t4

use t5

r0最终目标是仅使用两个 ARM 寄存器和进行寄存器分配r1，并且可能会溢出一些符号。

第一步是计算每条指令的有效范围：

t1 = 1       |
t2 = 2       | t1
t3 = 3       | t1, t2

t4 = t1 + t2 | t1, t2, t3 (this is going to become a problem)
t5 = t3 + t4 | t3, t4

use t5       | t5

注册干涉图

              t2
            /    \     
           /      \    
          /        \   
        t1----------t3
                    | 
                    | 
        t5          t4

通过图形着色注册分配

现在在它上面使用 Chaitin 的算法来用两个寄存器给它上色：

  1. 查找边数少于 2 的节点
    1. 找到 =>t5
    2. 从图表中删除它
    3. 将其压入堆栈：[t5]
  2. 查找边数少于 2 的节点
    1. 找到 =>t4
    2. 从图中删除它，推：[t5, t4]
  3. 没有少于 2 条边的节点！（我们正在看t1 - t2 - t3三角形）
    1. 随机选择一个（或具有最高程度（所有剩余节点为 2））=> t3（这可能是一个问题）
    2. 从图中删除它，推：[t5, t4, t3]
  4. 查找边数少于 2 的节点
    1. 成立t2
    2. 从图中删除它，推：[t5, t4, t3, t2]
  5. 推送最后一个节点：[t5, t4, t3, t2, t1]

现在以相反的顺序分配寄存器：

  1. 流行符号 =>t1
    1. 冲突节点：无
    2. 分配：t1 => r0
    3. 放回t1图中
  2. 流行音乐t2
    1. 冲突节点：{t1: r0}
    2. 我们还有一个免费注册
    3. 分配：t2 => r1
    4. 放回t2图中
  3. 流行音乐t3
    1. 冲突节点：{t1: r0, t2: r1}
    2. 哎呀！没有更多的免费注册！
    3. 洒它=>t3 => m0
    4. 放回t3图中
  4. 不再需要溢出！

最终任务：

t1 -> r0
t2 -> r1
t3 -> m0 (spilled)
t4 -> r0 (or r1)
t5 -> r0 (or r1)

插入溢出物

现在，按照这个（幻灯片 29）和这个（幻灯片 4）：

在使用 [溢出符号t3] 的每个操作之前，插入t3 := load m0

在定义 [溢出符号t3] 的每个操作之后，插入store t3, m0

让我们这样做并计算生存范围：

t1 = 1       |
t2 = 2       | t1

t3 = 3       | t1, t2
// STORE
store t3, m0 | t1, t2, t3 (STILL 3 SYMBOLS!)

t4 = t1 + t2 | t1, t2

// LOAD
t3 = load m0 | t4
t5 = t3 + t4 | t3, t4

use t5       | t5

问题

如您所见，我们仍然有一个指令，其中三个符号相互干扰，并且我们还将获得与以前相同的 RIG。

所以溢出没有用！

现在，我暴力破解了手动溢出的可能候选对象，发现如果我们溢出任何一个符号，RIG 仍然不是2-colorable ，但如果我们溢出这些符号对中的任何一个，它就会变成 2-colorable：

...and 还有t1, t2and t3，但只溢出两个符号看起来更简单。

实际问题

我如何决定要溢出什么？我使用什么启发式方法？我还希望算法进行全局寄存器分配，因此简单的生存范围和线性扫描分配（而不是构建 RIG）似乎是一种非常麻烦的方法。

此外，如果我在溢出的代码上重新运行相同的算法，结果将t3再次“溢出”，即使它已经完成，所以代码将永远循环。更有什者，如果我继续溢出t3和插入load/store代码，我会得到越来越多的指令 wheret1和干扰t2，t3所以情况会越来越糟。

这是假设我可以t3 = load m0，而在 ARM 上（我的目标）m0应该首先存储在它自己的寄存器中。

标签： compiler-constructionarmcpu-registersintermediate-language

解决方案

推荐阅读