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

论文题目: 相连多寄存器组体系结构上的寄存器分配技术

论文类型: 博士论文

论文专业: 计算机系统结构

作者: 张军超

导师: 张兆庆

关键词: 寄存器分配,图着色,相连多寄存器组,复写合并,活跃区域分裂

文献来源: 中国科学院研究生院（计算技术研究所）

发表年度: 2005

论文摘要: 寄存器分配是编译器后端一个十分重要的阶段。寄存器分配的有效性直接影响着编译器的优化效果和处理器性能的发挥。随着计算机体系结构的发展,为了支持多核多线程、异步访存以及减少寄存器件读写端口,出现了一类相连多寄存器组结构的处理器。在这类处理器上分配好寄存器是对编译器的一大挑战。本文对相连多寄存器组体系结构上的寄存器分配关键技术进行了研究。本文的主要贡献如下: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编译器中实现。

论文目录:

摘要

Abstract

图目录

表目录

第一章 引言

1.1 编译器与计算机体系结构

1.2 编译器的结构

1.3 ORC 编译器

1.4 寄存器分配与优化

1.5 图着色寄存器分配方法

1.6 论文概述

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

1.6.2 双操作数冲突的解决技术

1.6.3 复写合并与活跃区域分裂

第二章 图着色寄存器分配

2.1 图着色寄存器分配

2.2 Chaitin 式图着色寄存器分配

2.2.1 重命名

2.2.2 干涉

2.2.3 干涉图

2.2.4 复写合并

2.2.5 溢出

2.2.6 着色

2.2.7 选择溢出节点

2.3 其它图着色寄存器分配方法

第三章 相连多寄存器组体系结构上的寄存器分配

3.1 独立寄存器组体系结构及其寄存器分配算法

3.2 相连寄存器组体系结构的出现

3.3 Intel IXP 系列网络处理器

3.3.1 网络处理器的出现背景

3.3.2 IXP 系列网络处理器的结构

3.4 IXP 的编程环境与Microengine 上寄存器分配的新问题

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

3.5.1 确定寄存器组属性的时机

3.5.2 准备工作: 重命名和删除冗余指令

3.5.3 确定寄存器组属性

3.5.4 解决寄存器组冲突

3.5.5 组内寄存器分配

3.6 其他人的工作

3.7 总结

第四章 双操作数冲突解决技术

4.1 问题描述

4.2 问题分析

4.3 前人工作

4.4 一种双操作数冲突解决技术

4.4.1 先于寄存器分配的组指派(Pre-RA)

4.4.2 后于寄存器分配的组指派(Post-RA)

4.4.3 结合式寄存器分配和组指派(Combined-RA)

4.5 总结

第五章 复写合并与活跃区域分裂

5.1 复写合并

5.2 活跃区域分裂

5.2.1 基于基本块的分裂

5.2.2 基于循环的分裂

5.2.3 基于SSA 的分裂

5.2.4 活跃区域分裂与碎片溢出

5.3 活跃区域分裂与复写合并相结合的寄存器分配

5.4 总结

第六章实验环境与实验数据

6.1 Shangri-La: 一个网络程序编程环境

6.2 Shangri-La 在Intel IXP 上的实现

6.3 Shangri-La ME 编译器中寄存器分配器的测试

6.4 复写合并与活跃区域分裂相结合的寄存器分配的测试

6.4.1 实验平台与实验方法

6.4.2 实验结果

第七章 工程实现

7.1 ORC 后端中间表示简介

7.2 计算深度优先序

7.3 ORC 后端SSA 的实现

7.3.1 SSA 表示简介

7.3.2 计算支配前沿

7.3.3 插入φ函数

7.3.4 SSA 重命名

7.4 计算循环信息

7.5 图着色寄存器分配的实现

7.5.1 活跃区域重命名

7.5.2 活跃变量分析

7.5.3 建立干涉图

7.5.4 合并

7.5.5 计算溢出代价

7.5.6 着色

第八章 结束语

8.1 本文的主要贡献

8.2 下一步的工作

参考文献

致谢

作者简历

发布时间: 2006-12-27

参考文献

• [1].面向动态二进制翻译的动态优化和微处理器体系结构支撑技术研究[D]. 唐遇星.国防科学技术大学2005
• [2].流体系结构关键技术研究[D]. 文梅.国防科学技术大学2006
• [3].低功耗技术研究—体系结构和编译优化[D]. 易会战.国防科学技术大学2006
• [4].超深亚微米微处理器漏流功耗的体系结构级优化技术研究[D]. 张承义.国防科学技术大学2006
• [5].基三体系结构中并行运算的关键机制研究[D]. 李嘉欣.北京理工大学2010
• [6].高效能流体系结构关键技术研究[D]. 伍楠.国防科学技术大学2008
• [7].面向多核体系结构的并行优化关键技术研究[D]. 刘聪.国防科学技术大学2014
• [8].流体系结构指令管理及系统虚拟化仿真技术研究[D]. 何义.国防科学技术大学2010
• [9].面向异构体系结构的稀疏矩阵算法研究[D]. 邹丹.国防科学技术大学2013
• [10].片上高性能嵌入式计算—面向软基带的应用并行处理模型及体系结构[D]. 张波涛.国防科学技术大学2011

相关论文

• [1].龙芯2号处理器多线程技术研究[D]. 李祖松.中国科学院研究生院（计算技术研究所）2006
• [2].高性能存储系统研究[D]. 郇丹丹.中国科学院研究生院（计算技术研究所）2006
• [3].高性能通用处理器核的低功耗技术研究[D]. 张戈.中国科学院研究生院（计算技术研究所）2006
• [4].低功耗嵌入式处理器设计研究[D]. 范东睿.中国科学院研究生院（计算技术研究所）2005
• [5].低功耗浮点乘法部件的研究与设计[D]. 周旭.中国科学院研究生院（计算技术研究所）2005
• [6].存储控制系统性能优化技术研究[D]. 李文.中国科学院研究生院（计算技术研究所）2005
• [7].同时多线程处理器前端系统的研究[D]. 何立强.中国科学院研究生院（计算技术研究所）2004
• [8].基于区域的编译技术和栈寄存器优化[D]. 刘旸.中国科学院研究生院（计算技术研究所）2003
• [9].微处理器性能分析与优化[D]. 张福新.中国科学院研究生院（计算技术研究所）2005
• [10].多核处理器的访存模拟与优化技术研究[D]. 高翔.中国科学技术大学2007

标签：寄存器分配论文;  图着色论文;  相连多寄存器组论文;  复写合并论文;  活跃区域分裂论文;