二进制翻译中动静结合的寄存器分配优化方法

王 军 庞建民 傅立国 岳 峰 单 征 张家豪

(数学工程与先进计算国家重点实验室(战略支援部队信息工程大学) 郑州 450002)

二进制翻译[1]是一种即时编译技术，其核心目标是将一种体系结构的指令序列转换成功能等价的另一种可执行指令序列，已广泛用于软件安全分析[2-3]、程序行为分析[4]、软件逆向工程、系统虚拟等领域，并已成为软件移植[5]的主流技术之一.二进制翻译的过程可分为前端解码、中间优化以及后端编码3个部分.前端解码的主要工作类似于反汇编，依据源指令的特点分离出每条机器指令，将二进制可执行程序翻译成中间代码；中端优化的主要工作是优化生成的中间代码，通过分析中间代码组织关系简化中间代码，常用的冗余代码消除方法有常量传播[6]、变量活性分析[7]和标志位优化等[8]；后端编码的主要工作是本地目标代码的生成，将优化后的中间代码转换生成本地可执行的代码序列，其中包含寄存器分配过程.

寄存器分配无论是在高性能应用程序编译，还是在高性能程序翻译，又或者在充分利用高性能处理器的目标上，都有着重要的研究意义，好的寄存器分配方式可以有效提高程序执行效率.寄存器分配的目的是尽可能地将程序中的值保存在寄存器中，从而最大限度地减少访存次数，提高程序的执行效率，寄存器分配优化的重点在如何处理寄存器溢出问题.

不同于传统编译器中的寄存器分配，二进制翻译中寄存器分配的实质更像是寄存器映射，需要重点考虑源平台寄存器使用情况.目前常用的寄存器分配方法主要是寄存器图着色法、线性扫描法以及基于这2种方法的优化变种.二进制翻译，尤其是动态二进制翻译最常采用基于线性扫描的寄存器分配方法.

目前，已有较多人针对二进制翻译中的寄存器分配进行了研究.Liang等人[9]对动态二进制翻译器QEMU(quick emulator)中寄存器的管理及分配机制进行了详细的描述，但并未给出一种有效的改进方法；吴浩[10]通过对比实验说明了中间表示降低了二进制翻译的性能，并在x86平台翻译ARM程序时采用寄存器直接映射策略提高了翻译效率，但是该方法需要大幅度地修改QEMU的翻译机制且通用性不强.文延华等人[11]在Alpha平台翻译PowerPC程序时，对PowerPC中的特殊寄存器采用二进制翻译模拟、提出分段映射和特殊寄存器裁剪相结合的方法获得了一定的优化效果，但寄存器裁剪函数较为复杂且可被优化的程序较少；廖银等人[12]在MIPS平台模拟x86平台寄存器时采用直接映射策略，利用本地平台通用寄存器数量多的特点，直接将x86的8个通用寄存器一一映射到MIPS的通用寄存器上，简化了指令翻译的规则，降低了代码膨胀率，但该方法依赖于特定的硬件基础，通用性和可移植性不够强；Cai等人[13]在cross-bit系统中提出了简化的寄存器图着色法，使用3个链表收集变量定值引用信息，将活跃变量构造成一个图，之后遇到寄存器溢出情况则重新构造冲突图，但冲突图的构造大大增加了翻译的开销，整体的效率提升有限；Liang等人[14]基于QEMU的中间表示，分析变量的定值与引用，使用链表存储变量的生命周期和使用情况，减少了中间表示指令数目，但由于需要多次遍历采集基本块内变量的定值与引用信息，算法的复杂度较高且不具有良好的移植性.

本文结合QEMU[15]的翻译原理、QEMU使用的中间表示TCG (tiny code generation)中临时变量与寄存器分配之间的关系以及QEMU的寄存器分配机制[9]，引入全局寄存器静态映射和局部寄存器动态分配思想[16]，提出了基于优先级的动静结合二进制翻译寄存器分配优化算法.首先，根据x86平台应用程序各寄存器使用情况的整体统计数据进行全局寄存器静态映射；然后依据基本块内中间表示每条指令需求的寄存器数量及寄存器分配次数，排序确定各寄存器在基本块内分配的优先级顺序，动态分配寄存器；最后溢出循环块内未使用的全局寄存器供局部变量使用，并将全局寄存器的维护放在循环之外，尽可能减少因寄存器溢出而导致的冗余访存指令，尤其是循环体内的冗余访存指令，提高程序的执行效率.

1 相关工作

QEMU是一个广泛使用的支持用户级和系统级翻译的多源到多目标的动态二进制翻译系统[15].QEMU的动态翻译过程如图1所示，其中寄存器分配工作在QEMU翻译后端进行.

Fig. 1 QEMU translation process图1 QEMU翻译过程

为了实现多源到多目标的翻译，QEMU中采用了机器无关的中间表示TCG.基于TCG，不同源平台只需要变换前端解码器而不需要改动后端编码器，即可实现多源到目标平台的翻译，具有很好的跨平台特性.QEMU动态翻译的基本原理是利用指令变换时的语义等价，将源体系架构程序的指令翻译成一条或者多条TCG中间表示，然后将TCG中间表示变换成目标平台的一条或者多条指令，保证上述两者转换过程中指令语义的一致，实现不同平台上指令的等价.

本文提出的基于优先级的二进制翻译寄存器分配优化算法，主要是针对课题组基于QEMU研发的反馈式静态二进制翻译器FD-SQEMU(feedback static QEMU)设计的，但是该算法具有很好的跨平台特性和扩展性，稍加改动即可在动态二进制翻译中使用.

1.1 基于QEMU的反馈式静态翻译器FD-SQEMU

课题组基于QEMU，采用了QEMU的前端分析和TCG中间表示，设计了反馈式静态二进制翻译框架FD-SQEMU，该静态翻译器继承了QEMU跨平台的特性.FD-SQEMU除了前端源指令提取、TCG中端分析优化和后端目标代码生成3个过程外，还添加了动态执行反馈阶段，用以解决静态二进制翻译中存在的代码发现和代码定位问题.FD-SQEMU的框架结构如图2所示:

Fig. 2 Framework of FD-SQEMU 图2 FD-SQEMU框架设计

FD-SQEMU前端的源文件解析器和前端解码器以及中端TCG分析优化器均采用QEMU的相应模块，删除了QEMU中控制中心、缓存管理和执行模块，后端则添加了目标文件生成器，重点是引入了动态执行反馈模块实现静态二进制翻译中代码发现和代码定位.

源文件解析器、前端解码器和新添加的预处理模块构成FD-SQEMU的前端，负责将源平台二进制代码(本文即x86代码)翻译成中间代码TCG；

TCG分析优化器构成FD-SQEMU的中端，负责对TCG中间表示进行平台无关优化，包括TCG的优化，同时对源程序变量信息进行统计；

后端翻译器和目标文件生成器，构成FD-SQEMU的后端，负责将TCG中间代码翻译成目标平台的二进制代码(本文为申威架构的代码)；

动态执行反馈模块主要是模拟执行,用以获取反馈静态无法得到的间接跳转和间接调用目标地址，辅助解决静态二进制翻译中代码发现和代码定位问题.

与QEMU和基于LLVM的动态二进制翻译器[17]相比，FD-SQEMU分离翻译、代码优化与目标程序执行阶段，使得在同等优化手段下，FD-SQEMU能够采用不同层次的优化算法，生成高质量的执行代码.本文提出的寄存器优化方法在中端TCG分析优化器内进行相关信息分析，在后端代码生成阶段进行实际实现.

1.2 TCG指令

TCG指令类似于一种RISC(reduced instruction set computer)的指令，同样拥有数据传送、算术运算、逻辑运算、程序控制指令及其他指令[18].QEMU在tcg/tcg-opc.h中对所有TCG指令进行了定义，TCG指令格式定义为DEF(name,oargs,iargs,cargs,flags)，其中name为微指令的名字，oargs为指令输出参数个数，iargs为指令输入参数个数，cargs为指令常数个数，flags标志指令是否影响内存内容.此外，该结构体中还有参数args_ct与sorted，该参数与具体体系结构的寄存器紧密相关.

TCG指令的操作数称为临时变量，构成TCG中间表示的基础，是源机器指令操作数到目标机器指令数传递、存储与计算的桥梁.根据临时变量生命周期的不同划分，TCG定义了普通变量(temp)、普通本地变量(localtemp)、全局变量(globaltemp)和全局寄存器变量(globalregtemp)四种临时变量类型.TCG变量统一用结构体TCGTemp进行描述，变量类型通过结构体TCGTemp中的标志位进行区分.

全局变量和全局寄存器变量生命周期贯穿程序的整个翻译过程，分配的地址只有程序退出时才被收回.全局寄存器变量一般固定分配宿主机某一个寄存器值，用来保存源机器CPUState结构体的指针，实现源机器状态数据的快速读取，加快程序执行速度；普通变量生命周期范围为一个基本块，基本块执行结束变量被标注为“释放”状态，备下一个指令块使用.普通本地变量的生命周期为一个函数，与普通变量不同的是在某些基本块末尾处需要保存执行时的数据流信息以供函数内另一个基本块使用，即需要将基本块的执行信息进行回写.

临时变量内容均存储在TCG上下文的512个TCGTemp的静态数组static_temps中.其中全局变量和全局寄存器变量采取一次性分配策略建立运行时环境，在以后翻译的过程中不会再进行分配，生命周期贯穿程序始终.全局变量源机器平台运行环境env一般用全局寄存器变量表示，源机器平台如标志寄存器用全局内存变量表示，存储分布在静态数组static_temps的起始处；普通变量和普通本地变量依据源机器指令进行动态分配，存储在数组后面部分，每分配出一个，则将该空间打上标记进行标识.临时变量的存储空间分布如图3所示：

Fig. 3 Temporary variable memory format图3 临时变量内存布局

2 QEMU中TCG寄存器分配机制研究

寄存器作为CPU体系最重要的信息存储部件，它的读写速度远远快于存储器，它的利用效率直接影响程序的执行速度；在二进制翻译中，寄存器分配的好坏同样对目标程序的执行效率有着重要影响.

如引言所述，二进制翻译的过程是将源体系的可执行代码翻译成中间代码再翻译成本地可执行代码的过程；从寄存器映射的角度看，二进制翻译是从源体系的寄存器直接映射到虚拟机维护的一套内存虚拟寄存器，再由虚拟寄存器映射到目标体系上的寄存器的过程，临时变量是上述寄存器转换的“传输者”.

2.1 QEMU中TCG寄存器分配机制

QEMU中寄存器分配的主体包括2个部分[19]：1)内存虚拟寄存器;2)中间代码使用的临时变量.一套虚拟寄存器是一片连续的内存区域，内存虚拟寄存器主要是TCG中间表示源自于源体系寄存器的一一映射，以x86代码为例，如图4所示.对于内存虚拟寄存器，QEMU采用静态直接映射方法，使用固定的寄存器绑定方式实现源体系寄存器到本地寄存器的映射.如x86的宿主机用ebp寄存器指向env，利用ebp寄存器偏移即可获取整个虚拟寄存器，实现源体系寄存器到本地寄存器的映射.

Fig. 4 Mapping from source register to TCG virtual register图4 源体系寄存器到TCG虚拟寄存器的映射

TCG中间代码使用的临时变量类似于传统编译器中的虚拟寄存器，对于翻译程序而言，相对于通用寄存器不存在差异性，但其到本地目标寄存器的映射要复杂得多.

对于QEMU中间代码使用的临时变量，其寄存器分配采用线性扫描静态固定分配机制(first-mean-busy, FMB)，即“最靠前者最忙碌”，通过线性扫描目标体系提供的寄存器数组索引进行本地寄存器的分配.分配的具体实现过程为：1)当中间变量需要进行本地寄存器分配时，依据中间指令操作码和中间变量位置，确定临时变量可分配寄存器范围.2)从数组的起点开始遍历，当遇到某寄存器处于“空闲状态”时，即分配该寄存器,并将该寄存器的状态置为“忙碌”，中止遍历，待对应中间变量使用结束后即释放该寄存器；若遍历完的寄存器数组索引都处于“忙碌”的状态，则采用线性遍历寄存器数组从数组中强制“溢出”一个寄存器作为指定分配的寄存器，因溢出的寄存器保存着上一个临时变量的值，在释放寄存器的同时需将“溢出”的寄存器中的值写回内存中，以保证寄存器中的值不丢失.

2.2 TCG寄存器分配机制的缺陷

根据2.1节对TCG寄存器分配机制的分析，TCG指令内变量的寄存器分配采用优先级的方法，利用操作数可分配寄存器个数划分优先级，避免了寄存器分配竞争时导致操作数分配不到寄存器资源；指令间的寄存器分配方法采取简单的线性扫描和溢出，缺少指令间寄存器分配的优化算法，若发生资源竞争，则进行现行的寄存器溢出处理，显然存在不合理之处，以申威宿主机翻译x86可执行程序为例，如图5所示：

Fig. 5 TCG intermediate representation and local instruction after translation 图5 TCG中间表示与翻译后的本地代码

图5中左边为TCG中间代码(为观察方便，在TCG中间表示中添加了对应的x86汇编码);右边为翻译后生成的申威本地指令，每条中间指令对应生成相应的申威本地指令.其中x指令部分将$9寄存器分配给了tmp0，y指令部分也给tmp0分配$9寄存器时，z指令部分分别将$9和$10寄存器分配给tmp0和tmp1.在这里，QEMU实际上没有考虑指令间寄存器的使用情况，鉴于可能存在的寄存器溢出情况，在每条指令寄存器使用完毕后，都做了回写处理，引入了冗余访存指令①②③④，这是因为QEMU在进行寄存器分配时忽略了指令间的联系，引入了冗余指令，另外若下一指令或者指令块要继续使用rdx和rax中值，则⑤⑥⑦访存指令也是冗余且可以消除的.

Fig. 6 Example of registers allocation for loops图6 有关循环的寄存器分配例子

另外，QEMU中TCG寄存器分配机制也没考虑到程序上下文对寄存器分配的影响，忽略了循环体内寄存器分配对程序整体效率的影响，以图6为例进行说明.

如图6(a)所示，基本块或者几个基本块拼接成的循环块CB1位于循环体内，假设执行频率N=1 000，当对CB1循环块进行寄存器分配时,若发现寄存器不够用，则很可能会溢出一个寄存器，假设是A，那么循环块的头尾会各添加一个访存指令如图6(b)所示，如此store和load指令都在循环体内部，显然会降低程序性能，如果在寄存器分配前进行评估，优先满足循环体内部的寄存器需求，如此A可能因为无法分配到寄存器而溢出，如图6(c)所示，这样成功把访存指令移到了循环之外，有效提高了翻译后本地程序的性能.

针对上述由于寄存器溢出而导致的冗余访存问题，本文结合全局寄存器静态分配和局部寄存器动态分配思想，提出基于优先级的动静结合寄存器分配算法(a dynamic and static combined registers allocation algorithm based on priority).首先依据程序的静态统计特征，实现静态全局寄存器的直接映射，以减少全局寄存器的维护开销；然后借助程序的控制流程图，结合变量活性分析基本块内指令操作数寄存器分配个数，减少指令间寄存器以及循环体内不必要的寄存器溢出，以减少本地代码的膨胀率，提高翻译目标程序的执行效率.

3 基于优先级的动静结合寄存器分配算法

目前QEMU中使用的TCG寄存器分配机制的主要缺陷在于仅解决了指令内操作数分配的竞争，让指令内操作数分配到最优的寄存器，而对指令间寄存器采用固定的分配顺序，忽略了基本块内指令组成以及对寄存器需求的差异性，指令间固定的寄存器分配顺序与指令内的寄存器最优分配并没有实现整个基本块以及整个程序中寄存器分配的最优.

寄存器分配效率提高的关键在于如何最大限度减少寄存器溢出带来的开销.基于此，考虑到将目标程序中最常用的寄存器固定映射到本地机器的寄存器，可以有效避免过多的访存操作，提高翻译后的程序性能.因此，对x86应用程序和部分系统程序中寄存器使用情况进行统计对于寄存器的分配是有指导意义的.以系统Linux-0.2启动过程为例，x86上各寄存器使用情况统计结果如表1所示：

Table 1 Register Usage Statistics on x86 Program表1 x86程序寄存器使用情况统计

表1给出了系统Linux-0.2在启动时x86平台各寄存器的使用情况，从表1中可以看出x86架构运行时最常使用的寄存器是eax，ebx，edx，esp.x86应用程序寄存器的使用情况与此相似.

基于x86平台各寄存器使用情况的统计特征，在翻译程序具体进行寄存器分配时，首先根据x86寄存器使用情况，采用寄存器直接映射方式进行全局寄存器静态分配.如在翻译中具体进行寄存器分配时，可首先将x86上eax，ebx，edx，esp寄存器映射到申威处理器通用寄存器$9，$10，$11，$12上；然后当翻译x86指令时，即可直接使用对应的已固定映射到本地的通用寄存器替换x86中eax，ebx，edx，esp寄存器，而无需再从内存模拟的虚拟寄存器中加载，可以有效减少访存操作，提高程序运行效率.

在全局寄存器静态直接映射分配的基础上，再根据翻译程序基本块的特性进行局部的动态寄存器分配.具体做法是:首先通过变量活性分析遍历基本块内有效的中间指令，预估统计指令内操作数需求寄存器数;然后依据预估的寄存器数排序确定寄存器分配优先顺序.若可分配的寄存器预估需求数目越大，则基本块内指令对该寄存器的需求就越大，分配该寄存器的优先级越高，优先分配该寄存器，依次进行，优先级最低的寄存器最慢分配出去.如此，剩余指令对寄存器需求的可能性变小，从而最大限度地减少寄存器溢出的可能性并使寄存器溢出的代价减少.具体的算法流程图如图7所示:

Fig. 7 Algorithm flowchart图7 算法流程图

1) TCG作为FD-SQEMU前端代码解析和后端目标代码生成的纽带，记录了基本块内全局变量个数和基本块跳转等信息.在此基础上，添加基本块内寄存器需求数组regRequestNum和寄存器优先级数组regPriority，分别记录基本块内需求寄存器的局部变量个数(即寄存器需求数)和基本块内各寄存器分配的次序(即需求该寄存器的优先程度).在翻译每个基本块之初，对这2个数组进行初始化.

2) 借助变量活性分析线性扫描基本块内TCG指令，统计寄存器需求数目.这里对已固定分配寄存器的全局变量不作变量处理，但进行块内使用标记；对于其他变量，只须将对应各TCG指令内需求寄存器的计数器regRequestNum采取迭代累加的方法，即可完成寄存器分配计数器的统计，该迭代累加算法的伪代码如图8所示：

Fig. 8 Pseudo-code algorithm
图8 部分算法伪代码

4) 依据控制流程图判断该基本块是否是循环体内的基本块，若是且该循环块内仍有多次使用的变量未分配到寄存器，则将该循环体内未使用的全局寄存器溢出，供该循环块内变量使用；并依据循环优化中代码外提方法将该全局寄存器的状态维护代码外提到循环体外.如此，可进一步提高目标平台寄存器的利用率，减少寄存器溢出开销，提高程序运行效率.

4 实验和结果

实验采用由QEMU改造的FD-SQEMU模拟器作为二进制翻译平台，首先借助FD-SQEMU翻译器使用QEMU中默认的寄存器分配方法对测试用例进行翻译;然后借助FD-SQEMU翻译器在进行寄存器分配优化后对测试用例进行翻译，对比两次翻译后得到的目标程序的运行时间，以评估基于优先级的动静结合寄存器分配优化算法的实际优化效果.

令Tbefore和Tafter分别表示在使用寄存器分配优化算法前和使用寄存器分配优化算法后的本地目标程序的执行时间，则使用寄存器分配优化后与优化前的加速比为

在实际进行测试验证时，实验通过正确性测试、循环热代码测试、递归热代码测试和整体性能测试对提出的算法进行整体评估.

4.1 实验环境

1) 源平台.x86平台，操作系统为Fedora11 Linux 2.6.29.4 编译器gcc-4.6.4.

2) 目标平台.国产申威处理器，主频1.4 GHz，内存4 GB，操作系统为Fedora，内核版本3.8.0，编译器为 gcc，版本 4.5.3.

3) 测试集.NBENCH-2.2.3，手动实现的主流递归算法和SPEC2006测试集[19].

4.2 正确性测试

针对寄存器优化算法的正确性测试主要分为2个部分：指令翻译测试和实际程序翻译测试.

指令翻译测试借助FD-SQEMU自带的test-i386测试集，重点对x86架构用户态的指令进行了测试.依据x86指令分类情况，具体的测试结果如表2所示.

在保证了单条指令翻译的正确性后，对实际程序翻译进行了正确性测试.具体测试过程为：1)在x86平台上编译SPEC CPU2006和NBENCH测试集等测试程序并运行记录结果；2)在目标平台上运行翻译后的可执行程序，并与x86上运行结果相比对.部分程序的测试结果如表3所示.

实验结果表明，优化前后的目标程序执行结果与源x86平台上程序执行结果相同，表明基于优先级的动静结合寄存器分配算法能够进行正确的翻译，保证了程序的等价翻译，具有较高的可信度.

Table 2 Correctness Testing of Instruction Translation表2 指令翻译的正确性测试

Note：“√” mean that the test instructions have passed the correctness verification.

Table 3 Correct Test表3 正确性测试

Note：“√” mean that the test cases have passed the correctness verification.

4.3 寄存器分配相关信息分析

申威处理器共计有6个全局寄存器S0～S5、12个临时寄存器T0～T11.使用QEMU现有的寄存器分配机制进行二进制翻译时，大量使用了S0，S1，S2寄存器，并在每次全局寄存器使用完毕后将其中的值写回存储器，一是对其余现有的寄存器利用率较低，二是引入了不必要的寄存器维护开销；在改进寄存器分配方式后，各基本块对申威寄存器的使用更加均衡，能有效减少因寄存器溢出导致的访存次数.寄存器分配方式改进前，各申威本地寄存器使用频率如表4所示:

所谓盈利能力，通常来讲是指企业获取利润的能力，表现为一定时期内企业收益数额的多少，一般用净资产收益率、成本费用利润率、销售利润率、总资产报酬率、盈余现金保障倍数和资本收益率六项。由前文分析可知，生产性服务业“营改增”会影响企业营业税金及附加、所得税费、企业利润等项目，通过减少企业的税负，带来企业成本的降低与更多资金的流动。企业将这笔节省出来的资金用于研发设备的投入或者扩大再生产时，由于《企业所得税法》规定了研发费用的加计扣除等税收优惠政策，这就会使得企业在进一步减轻其税负时，盈利能力得到提高。

Table 4 Registers Usage Frequency of SW Before Optimization表4 优化前部分申威本地寄存器使用频率

改进寄存器分配方式后，各申威本地寄存器使用频率所占百分比如表5所示:

Table 5 Register Usage Frequency of SW After Optimization表5 优化后部分申威本地寄存器使用频率

如表5所示，该寄存器分配方式，有效地提高了本地临时寄存器的使用率，并且使申威寄存器的使用更加均衡，可以减少寄存器的溢出次数.在寄存器分配优化后，翻译后程序的指令平均减少了约2.3%.

4.4 循环热代码性能测试

NBENCH测试集的主要功能是通过计算一定时间内(一般是5 s)单项测试代码块的循环迭代次数来评价系统性能，其中每一个测试块都是典型的循环热代码，具体的NBENCH测试集各部分功能如表6所示.

使用寄存器分配优化前和优化后的FD-SQEMU在国产申威处理器上对NBENCH测试集进行对比测试，优化后相对于优化前的加速情况如图9所示.

如图9所示，对于不同的NBENCH测试项目，寄存器分配优化后获得的加速比也不同.

Table 6 NBENCH Tasks表6 NBENCH测试任务

Fig. 9 Speedup ratio on NBENCH after optimization 图9 优化后NBENCH加速情况

4.5 递归热代码性能测试

Fig. 10 Speedup ratio on recursive algorithms after optimization图10 优化后递归热代码加速情况

4.6 整体性能测试

SPEC2006测试集中的程序基本都是实际应用中常用到的程序，该测试集的执行结果能够反映出一个翻译系统的整体性能.在具体实验时，挑选了部分SPEC2006中常用的测试应用进行测试，采用FD-SQEMU在寄存器分配优化后翻译源程序为本地目标程序，该程序性能提升情况如图11所示:

Fig. 11 Speed up ratio on part of SPEC2006 after optimization图11 优化后部分SPEC2006测试项的加速情况

4.7 实验结果分析

通过对不同程序进行测试，根据图9～11中结果可以看出改进了寄存器分配方式后，各程序都有不错的性能提升，其中NBENCH测试集中STRING_SORT和BITFIELD的测试程序性能提升最高，最高达到了17.36%.改进寄存器分配方式后，根据图9中测试结果NBENCH各测试项性能提升4.35%～17.24%，平均性能提升约为8.56%；根据图10中测试结果， FIBONACCI, QUICKSORT等递归程序性能提升7.86%～8.54%，平均性能提升了8.14%；根据图11，SPEC2006程序性能提升了6.94%～9.62%，平均性能提升了8.01%.根据测试结果，说明该寄存器分配优化算法是有效的，且对于含循环、递归较多的程序，有更好的优化效果.

5 总 结

本文在分析QEMU的寄存器分配方法后，举例指出了该机制存在的缺陷，并在介绍了由QEMU改造的静态二进制翻译器FD-SQEMU后，借鉴传统编译器静态全局寄存器分配和动态局部寄存器分配思想后，提出了基于优先级的动静结合寄存器分配方法.该算法，首先依据x86应用程序统计特征进行全局寄存器静态直接映射分配;然后考虑各循环块以及基本块间寄存器需求的差异，利用TCG中间表示操作码与本地指令之间的映射关系统计基本块内需求的各寄存器次数，并排序确定优先级顺序进行寄存器分配;最后，溢出循环块内未使用的全局寄存器，给块内未分配到寄存器的变量使用，进一步减少了寄存器溢出的开销.通过NBENCH、某些经典递归程序和部分SPEC2006程序对该算法进行测试，结果表明该寄存器分配优化算法能有效提高目标程序的执行效率.另外，该算法对具体的目标平台依赖不大，具有很好的跨平台特性，另外，舍去该算法中依据程序控制流程图对循环块的处理亦可适用于动态二进制翻译.

寄存器分配的研究无论是对于传统编译器，还是对于二进制翻译，从更好地发挥CPU的性能以及提高高性能计算程序的执行效率方面都有重要的意义.