相连多寄存器组体系结构上的寄存器分配技术

发布时间：2020-09-15 17:36

　　寄存器分配是编译器后端一个十分重要的阶段。寄存器分配的有效性直接影响着编译器的优化效果和处理器性能的发挥。随着计算机体系结构的发展,为了支持多核多线程、异步访存以及减少寄存器件读写端口,出现了一类相连多寄存器组结构的处理器。在这类处理器上分配好寄存器是对编译器的一大挑战。本文对相连多寄存器组体系结构上的寄存器分配关键技术进行了研究。本文的主要贡献如下: 1.提出了一种相连多寄存器组结构上的寄存器分配方法。传统通用处理器的寄存器组之间相互独立,各自存放不同类型数据,指令的操作数只能来自唯一一个寄存器组。在这种独立寄存器组结构上只须分别对每个寄存器组使用目前流行的Chaitin方法即可。但在相连寄存器组结构的处理器上,各寄存器组字长相同并有数据通路相连,能存放相同的数据,指令的操作数可来自多个寄存器组。出现了需要确定变量的寄存器组属性及解决寄存器组冲突的新问题,使得Chaitin方法不再直接适用。我们通过提出寄存器组划分图的概念以及对它相应的建立、化简和分裂方法,解决了上述问题。 2.提出了三种双操作数冲突解决技术。为了减少寄存器堆的读写端口个数,进而提高寄存器的访问速度,有的处理器要求所有二元操作指令的两个源操作数必须来自不同的寄存器组。随之出现的新问题是,我们既要为变量指派寄存器组,又要为其分配寄存器,两者之间互相影响。我们提出了冲突图概念,并把这种双操作数冲突约束下的寄存器分配问题分解为二个子问题:组指派子问题和寄存器分配子问题。前者通过对冲突图2-着色解决,后者通过对干涉图K-着色解决。根据解决这二个子问题的次序,提出了三种方法:先于寄存器分配的组指派、后于寄存器分配的组指派、结合式寄存器分配与组指派。 3.提出了一种复写合并与活跃区域分裂相结合的寄存器分配方法。Chaitin方法的一个缺陷是溢出一个活跃区域时会全程溢出,代价较大。我们的方法是事先把活跃区域分裂成多个碎片,然后依赖复写合并激进地合并碎片。如果合并后的活跃区域出现分配失败,就按原来的裂痕进行反合并。由此我们获得了一种在溢出全部活跃区域、溢出部分活跃区域、用拷贝指令换取溢出之间做出更好选择的能力。 4.为开放源码编译器ORC增添了新的基础设施。ORC被国内外多所著名大学和研究机构采用,做为其研究平台。我们在ORC中实现了多种图着色寄存器分配方法以及ORC后端的SSA表示。例如Chaitin方法、Briggs乐观式着色方法、George迭代式合并方法和我们提出的新方法。与ORC原有方法相比,我们在253.perlbmk、186.crafty上分别取得了3.4%和13.3%的性能加速比。图着色寄存器分配和SSA表示是编译研究中二个重要的基础设施,我们的实现为ORC平台添加了新的资源。上面提到的前两点在ORC/IXP编译器中实现,第三点在ORC/龙芯MIPS编译器中实现。
【学位单位】：中国科学院研究生院（计算技术研究所）
【学位级别】：博士
【学位年份】：2005
【中图分类】：TP333

【引证文献】