Page 60 - 《软件学报》2024年第6期

2636 软件学报 2024 年第 35 卷第 6 期

5 bit 4 bit 3 bit 7 bit 5 bit 4 bit 7 bit 15 bit
a c b a c b a b c
d
d d
Swap
e e
e

(a) Cong 算法 (共 19 bit) (b) Swap 算法 (共 16 bit) (c) ቋႪٚσ (共 15 bit)
图 2 3 种寄存器绑定方案对例 1 产生的分配结果示意图

2.4 Swap 算法
Canesche 等人 [13] 在 WIGC 抽象的基础上, 进一步提出了通过插入复制和交换指令来降低寄存器数量的方法,
我们称之为 Swap 算法.
Swap 算法首先在每个基本块中的连续指令之间插入并行拷贝, 从而将每个变量的活跃区间限制在了相邻的
两条指令之间, 不同程序点间的活跃变量相互独立. 接着独立地解决每个程序点上的加权区间图着色问题. 最后,
Swap 算法尝试合并多个程序点不同着色方案, 并给出的最优拼接方案. Swap 算法对例 1 的解决方案需要在第 2
和第 3 条指令之间插入交换指令, 以便将变量 c 和 d 的活跃区间分割开来. 这样, 变量 和 d 的部分活跃区间可以
c
e 共享一个 7 位寄存器, 而其余活跃区间可以共享一个 4 位寄存器. 该方案总共需要分配 16 个寄存器.
与变量 b 和
与 Cong 算法方法相比在比特位宽上共减少了 3 位, 但同时需要增加一条交换指令.
Swap 算法以插入额外指令为代价减少了绑定的寄存器数量, 它是 WIGC 抽象的一种改进形式, 由于过程中的
每一步算法均是最优解, 因此 Swap 算法是一种多项式时间的最优解算法. 但 Swap 算法的最优性限制在该算法设
置的对齐约束之中, 对于整个寄存器绑定问题的求解并非最优, 我们将在第 2.5 节中详细阐述.

2.5 研究动机
本节通过样例分析仔细研究了 4 bit 寄存器, 是由子着色方案的
算法可能造成的寄存器浪费现象, 并由此指出已有算法的
算法与
Cong
Swap
局限性. 我们将在第 3 节中通过引入新的抽象来解决这些问题.
为了使接下来的分析更加清晰明确, 我们将绑定算法中寄存器的空闲状态定义为寄存器空泡, 并通过对寄存
器空泡的分析来评估已有算法的分配方案. 一般而言主要寄存器空泡包括两种不同的状态, 一是变量位宽与寄存
器大小不匹配产生的位宽冗余, 二是由于冲突关系造成的寄存器空置. 图 2 中的灰色区域展示了不同绑定方案产
生的寄存器空泡, 通常我们认为寄存器空泡的范围越大, 造成寄存器浪费的可能性也就越高.
Cong 算法将可能同时产生两种类型的寄存器空泡. 如图 2(a) 所示, 变量 b 与变量 合并时, 6 bit 变量 b 存储
e
在 7 bit 寄存器中, 产生了 1 bit 的位宽冗余; 变量 b 的活跃区间结束, 的活跃区间开始之前, 寄存器处于空闲状态
e
且无法被其他变量复用, 从而产生了寄存器空置. 因此 Cong 算法在 3 种绑定方案中产生了最多的寄存器空泡.
Swap 算法通过插入交换与并行拷贝指令, 解决了寄存器空置产生的寄存器空泡问题, 但却仍然存在两点缺
陷. 其一, Swap 算法需要合并多个子着色方案, 在合并过程中会扩大合并的寄存器大小, 因此增加了位宽冗余产生
的寄存器空泡. 如图 2(b) 所示的 4 bit 寄存器与 3 bit 寄存器合并而成, 因此造成了
额外的位宽冗余. 其二, 拷贝指令产生额外代价. Swap 算法频繁地移动数据会使得电路的控制逻辑变得更为复杂.
如图 2(b) 所示, 算法插入了额外的交换指令, 这可能会增加多路复用器的使用, 反而导致综合后的电路面积更大,
我们将在第 4.5 节详细阐述这一矛盾.
已有绑定算法产生大量寄存器空泡的根本原因在于对寄存器的利用存在不合理的限制. 与寄存器分配问题不
同, 寄存器绑定问题中, 寄存器的连线可以根据绑定结果生成, 无需遵循通用可编程寄存器常见的对齐约束. Cong
算法采用的 WIGC 抽象, 仅允许同一独立集内的变量共享同一个寄存器, 为寄存器绑定问题引入了额外的对齐约
束. Swap 算法虽然对 WIGC 抽象有所改进, 但仍未能够完全消除对齐约束带来的影响. 如图 2(c) 所示显示了一种