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

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

的寄存器分配问题 [26−28] . 该问题限制了寄存器组的大小为固定的大小. 尽管与寄存器绑定问题存在一定的相似性,
但在传统硬件设计领域中, 将多个变量分配到同一寄存器的不同位中会导致物理寄存器布局变得极为复杂, 同时
也会增加物理寄存器的寻址和存储延迟. 因此, 这种技术始终受到一定程度的限制 [28] . 当将寄存器打包算法应用
于寄存器绑定问题时, 实际的分配效果可能稍逊于 Cong 等人提出的方法 [11,27] .

1.3 位宽分析
位宽分析作为位宽感知的寄存器绑定算法的基本组成部分, 主要利用静态分析技术推断变量的位宽 [29−31] . 传
统高级语言如 C/C++等描述电路的逻辑结构存在很大局限性, 因为这些语言只提供具有受限长度的计算类型, 例
如固定位宽的 8/16/32/64 等. 研究显示, 在一组用 C 编写的基准程序中, 平均有 40% 的位宽冗余 [29] , 识别出这些多
余的比特可以降低潜在的硬件资源成本. 经验公式 [32−34] 表明, 乘法器的面积与两个输入的位宽乘积成正比, 加法器
的面积则与输入的位宽成正比. 对于寄存器和多路复用器等其他资源类型, 可以采用合理的线性假设来估计它们
的面积和位宽之间的关系. 由于操作位的减少也可以带来布线成本的节省, 因此通过优化电路的位宽分配, 还可以
有效地减少电路的面积和功耗. 然而, 从传统物理意义范畴出发为硬件设计明确指定比特宽度费时费力. 因此更理
想的设计流程是自动分析变量和操作的位宽, 以减轻设计者的负担并减少出错的机会. 本文的寄存器绑定算法未
G 存在完美消除序列.
限制位宽分析的具体实现方式, 因此, 任何实现方式都可以满足我们的需求.
当前编译器主要从范围分析与位掩码分析两种层面对变量位宽进行分析. Stephenson 等人 [29] 提出了基于变量
范围分析的位宽分析技术, 该方法试图通过变量范围的正向与反向传播来估计变量的范围, 从而实现对变量的高
位截断技术. Gort 等人 [35] 提出了掩码分析与范围分析相结合的位宽分析技术, 使得位宽分析可以针对变量的每个
比特进行精确的分析. 这两种分析形式提供了不同层面的互补信息, 因此需要综合考虑 [35] .

2 背景知识与研究动机

本节主要对相关背景知识与研究动机进行梳理, 首先我们对后文将要涉及的图论相关知识进行简单介绍. 然
后我们给出本文所关心的寄存器绑定问题的定义与典型样例. 我们首先介绍一种寄存器绑定问题的经典抽象方法
加权区间图着色 (WIGC) 抽象 [11] . 接着我们介绍一种通过插入额外的拷贝指令在多项式时间内给出最优解的优化
算法 [13] . 最后我们通过样例分析指出了两种方法中存在的寄存器浪费现象, 并由此引出我们新的设计.

2.1 背景知识

本节总结了弦图理论中的相关概念. 对于无向图 G(V,E) , 图上的一个环中不相邻的两个顶点相连的边称为弦.
给定无向图 G(V,E) , 如果图中任何一个长度大于 3 的环至少有一条弦, 则称 G 是弦图.
v 相邻的顶点集合, 若一个图的子图顶点两两相邻, 则称该子图为团, 我们记顶点数
我们使用 N(v) 表示与顶点
最多的团为最大团, 其顶点数记为团数 ω(G) . 如果顶点 v ∈ V 的邻域 N(V)∪{v} 是一个团, 则称该点为单纯点. 我们
称一个点的序列 v 1 ,v 2 ,...,v n 为一个完美消除序列 (PEO), 当且仅当该序列满足顶点 v i 在 v i ,v i+1 ,...,v n 的诱导子图中
为一个单纯点.
给定一些区间, 用每个顶点表示一个区间, 若两个区间的交集非空, 则代表两区间的顶点间存在一条边, 由此
构成的图称为区间图. 关于弦图与区间图, 有如下几个重要的结论 [23] .
定理 1. 无向图 G(V,E) 是弦图当且仅当
定理 2. 弦图 G 的色数 χ(G) 等于团数 ω(G) .
引理 1. 区间图必定为弦图.

引理 2. 弦图 G 按照 PEO 逆序贪心着色, 该方案的着色数等于 χ(G) .
引理 3. 区间图按顶点对应区间的右端点从小到大排序, 该序列为完美消除序列.

2.2 寄存器绑定问题定义
由于本文关注的问题是调度后的寄存器绑定问题, 因此如无额外说明, 假定后文提及的每个输入程序都是满
足 SSA 形式的线性结构程序, 且本文中的寄存器绑定问题不涉及指令间的调度. 以下给出寄存器绑定问题定义.