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

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

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

针对二进制翻译器QEMU(quick emulator)在寄存器映射时未考虑基本块之间以及循环体之间对寄存器需求的差异,造成不必要的寄存器溢出而导致的冗余访存开销问题,引入全局寄存器静态映射和局部寄存器动态分配思想,提出高效的基于优先级的动静结合寄存器映射优化算法.该算法首先基于源平台不同寄存器使用的统计特征和各变量的生命周期,静态进行全局寄存器映射;然后依据中间表示与源平台寄存器之间的映射关系,获取基本块中间指令需求寄存器次数并排序确定寄存器分配的优先级;之后依据优先级顺序动态进行寄存器分配,从而减少寄存器溢出次数,降低生成的本地代码的膨胀率以及访存次数,提高目标程序性能.对NBENCH、典型的递归程序和SPEC2006的测试表明:该算法有效地减少了本地代码的访存次数,提高了程序性能,平均比优化前性能分别提升了8.67%, 8.25%, 8.10%.

关键词 二进制翻译;寄存器分配;翻译器QEMU;反馈式静态二进制翻译器FD-SQEMU;TCG中间表示

二进制翻译[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_ctsorted,该参数与具体体系结构的寄存器紧密相关.

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程序寄存器使用情况统计

x86RegistersPercentage ofUse Frequency∕%x86RegistersPercentage ofUse Frequency∕%eax29.6esp16.0ebx12.6ebp4.8ecx8.1edi6.5edx13.3esi9.1

表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翻译器在进行寄存器分配优化后对测试用例进行翻译,对比两次翻译后得到的目标程序的运行时间,以评估基于优先级的动静结合寄存器分配优化算法的实际优化效果.

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

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

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 指令翻译的正确性测试

Test InstructionTest ResultData Movement Instructions√Destination Address Transfer Instruction√Arithmetic Instruction√Logical Instruction√String Instructions√Program Transfer Instructions√Shift and Bit Instructions√

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

Table 3 Correct Test
表3 正确性测试

Test CaseBefore OptimizationAfter OptimizationNUMERIC_SORT√√STRING_SORT√√BITFIELD√√FP EMULATION√√FOURIER√√IDEA√√HUFFMAN√√NUEURAL NET√√LU DECOMPOSITION√√FIBONACCI√√QUICKSORT√√MERGESORT√√N-QUEEN√√BZIP2√√MILC√√SPECRAND√√MCF√√

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 优化前部分申威本地寄存器使用频率

SWRegistersPercentage of Use Frequency∕%SWRegistersPercentage of Use Frequency∕%S033.2T11.9S130.9T20.7S225.6T30.2S36.3T40.1S40.9T50S50.2T60

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

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

SWRegistersPercentage of Use Frequency∕%SWRegistersPercentage of Use Frequency∕%S013.5T120.2S112.3T218.9S26.3T315.4S30.8T48.6S40.2T53.2S50.1T60.5

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

4.4 循环热代码性能测试

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

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

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

Table 6 NBENCH Tasks
表6 NBENCH测试任务

Test CaseTasksNUMERIC_SORTSort an array of long integersSTRING_SORTSort an array of strings of arbitrary lengthBITFIELDExecute a variety of bit manipulation functionsFP EMULATIONA small software floating-point packageFOURIERA numerical analysis routine for calculating series approximations of waveformsASSIGNMENTA well-known task allocation algorithmIDEAA text and graphics compression algorithmHUFFMANA relatively new block cipher algorithmNUEURAL NETA small but functional back-propagation network simulatorLU DECOMPOSITIONA robust algorithm for solving linear equations

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

4.5 递归热代码性能测试

递归算法是会反复执行的热代码,在实际程序中递归代码也是大量存在的,递归程序中对单一或某些函数的反复调用会产生大量的函数调用和返回指令,此时全局寄存器的分配和溢出处理也直接影响着程序执行效率.本文对典型的递归算法进行了测试,测试结果如图10所示:

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的性能以及提高高性能计算程序的执行效率方面都有重要的意义.

参考文献

[1]Altman E R, Kaeli D, Sheffer Y. Welcome to the opportunities of binary translation[J]. Computer, 2000, 33(3): 40-45

[2]Shan Zheng, Guo Haoran, Pang Jianmin. BTMD: A framework of binary translation based malcode detector[C] //Proc of the 4th Int Conf on Cyber-Enabled Distributed Computing and Knowledge Discovery. Los Alamitos, CA: IEEE Computer Society, 2012: 39-43

[3]Ma Jinxin, Li Zhoujun, Hu Chaojian, et al. A reconstruction method of type abstraction in binary code[J]. Journal of Computer Research and Development, 2013, 50(11): 2418-2428 (in Chinese)

(马金鑫, 李舟军, 忽朝俭, 等. 一种重构二进制代码中类型抽象的方法[J]. 计算机研究与发展, 2013, 50(11): 2418-2428)

[4]Zhao Tianlei, Tang Yuxing, Fu Guitao, et al. Accelerating program behavior analysis with dynamic binary translation[J]. Journal of Computer Research and Development, 2012, 49(1): 35-43 (in Chinese)

(赵天磊, 唐遇星, 付桂涛, 等. 利用动态二进制翻译加速应用程序行为特征分析[J]. 计算机研究与发展, 2012, 49(1): 35-43)

[5]Chen Jingsong, Lan Xuhui, Wei Zhong. Software transplant based on instruction simulation[J]. Electronic Instrumen-tation Customer, 2010 (1): 55-57

[6]Wegman M N, Zadeck F K. Constant propagation with conditional branches[J]. ACM Transactions on Programming Languages and Systems, 1991, 13(2): 181-210

[7]Muth R. Register liveness analysis of executable code[C/OL]. 1998[2017-08-05]. http://robert.muth.org/Papers/unpub-liveness.pdf

[8]Ma Xiangning, Wu Chenggang, Tang Feng, et al. Two condition code optimization approaches in binary translation[J]. Journal of Computer Research and Development, 2005, 42(2): 329-337 (in Chinese)

(马湘宁, 武成岗, 唐锋, 等. 二进制翻译中的标志位优化技术[J]. 计算机研究与发展, 2005, 42(2): 329-337)

[9]Liang Alei, Guan Haibing, Li Zengxing. A research on register mapping strategies of QEMU[C] //Proc of the 2nd Int Symp on Intelligence Computation and Application. Berlin: Springer, 2007: 168-172

[10]Wu Hao. Optimization technology of QEMU[D]. Shanghai: Shanghai Jiao Tong University, 2007 (in Chinese)(吴浩. 二进制翻译系统QEMU中的优化技术[D]. 上海: 上海交通大学, 2007)

[11]Wen Yanhua, Tang Daguo, Qi Fengbin. Register mapping and register function cutting out implementation in binary translation[J]. Journal of Software, 2009, 20(2): 1-7 (in Chinese)

(文延华, 唐大国, 漆锋滨. 二进制翻译中的寄存器映射与剪裁的实现[J]. 软件学报, 2009, 20(2): 1-7)

[12]Liao Yin, Sun Guangzhong, Jiang Haitao, et al. All registers direct mapping method in dynamic binary translation[J]. Computer Applications and Software, 2011, 28(11): 21-24 (in Chinese)

(廖银, 孙广中, 姜海涛, 等. 动态二进制翻译中全寄存器直接映射方法[J]. 计算机应用与软件, 2011, 28(11): 21-24)

[13]Cai Zhanju, Liang Alei, Qi Zhengwei, et al. Performance comparison of register allocation algorithms in dynamic binary translation[C] //Proc of the 1st Int Conf on Knowledge and Systems Engineering. Los Alamitos, CA: IEEE Computer Society, 2009: 113-119

[14]Liang Yi, Shao Yuanhua, Yang Guowu, et al. Register allocation for QEMU dynamic binary translation systems[J]. International Journal of Hybrid Information Technology, 2015, 8(2): 199-210

[15]Bellard F. QEMU, a fast and portable dynamic translator[C] //Proc of the 2nd Conf on USENIX Technical. Berkeley: USENIX Association, 2005: 41-41

[16]Jiang Jun, Wang Chao, Wei Hongmei. An optimization strategy for local register allocation[J]. Computer Applications and Software, 2013, 30(12): 215-217 (in Chinese)

(姜军, 王超, 尉红梅. 一种局部寄存器分配的优化策略[J]. 计算机应用与软件, 2013, 30(12): 215-217)

[17]Hong Dingyong, Hsu Chunchen, Yew Penchung, et al. HQEMU: A multi-threaded and retargetable dynamic binary translator on multicores[C] //Proc of the 10th Int Symp on Code Generation and Optimization. New York: ACM, 2012: 104-113

[18]Zhang Xichao, Guo Xiangying, Zhao Lei. Study on TCG dynamic binary translation technique[J]. Computer Application and Software, 2013, 30(11): 34-37 (in Chinese)

(张西超, 郭向英, 赵雷, 等. TCG动态二进制翻译技术研究[J]. 计算机应用于研究, 2013, 30(11): 34-37)

[19]Dai Tao, Shan Zheng, Lu Shuaibing, et al. Register allocation algorithm of dynamic binary translation based on priority[J]. Journal of Zhejiang University, 2016, 50(7), 1338-1346 (in Chinese)

(戴涛, 单征, 卢帅兵, 等. 基于优先级动态二进制翻译寄存器分配算法[J]. 浙江大学学报, 2016, 50(7): 1338-1346)

A Dynamic and Static Combined Register Mapping Method in Binary Translation

Wang Jun, Pang Jianmin, Fu Liguo, Yue Feng, Shan Zheng, and Zhang Jiahao

(State Key Laboratory of Mathematical Engineering and Advanced Computing (Strategic Support Force Information Engineering University), Zhengzhou 450002)

Abstract To reduce the redundant memory access caused by unnecessary registers overflow in binary translation, as the registers mapping in binary translation ignores the difference of register requirements among basic blocks and loop blocks, an efficient dynamic and static combined registers mapping optimization algorithm based on priority is proposed, introduces the idea of allocating global register statically and allocating local register dynamically. Firstly, global register is mapped statically to reduce the global register overflow cost and maintenance overhead, according to statistical features of different registers used on the source platform and the life cycle of variable. Then, the number of registers requested by intermediate instruction can be obtained, based on the intermediate representation. Therefore, the priority of registers allocation is determined. Lastly, dynamically allocate the registers in order to reduce the number of registers overflow, to reduce the expansion rate of the generated local code and memory access times. Thus, the performance of the target program is improved. The test results of NBENCH, representative recursive programs and SPEC2006 show that, the algorithm effectively reduces the memory access of local code, and improves the program performance with an average increase of 8.56%, 8.14%, and 8.01%, respectively.

Key words binary translation; register allocation; quick emulator (QEMU); feedback static QEMU (FD-SQEMU); TCG intermediate code

(wj_xd@foxmail.com)

中图法分类号 TP314

收稿日期2017-11-28;

修回日期:2018-11-13

基金项目国家自然科学基金项目(61472447,61802433)

This work was supported by the National Natural Science Foundation of China (61472447, 61802433).

通信作者 庞建民(jianmin_pang@126.com)

Wang Jun, born in 1992. PhD candidate. His main research interests include computer archi-tecture and high perfor-mance computing.

Pang Jianmin, born in 1964. PhD, professor, PhD supervisor. Senior member of CCF. His main research interests include computer architecture, information security and high performance computing.

Fu Liguo, born in 1989. PhD. His main research interests include advanced compi-lation and high performance computing.

Yue Feng, born in 1985. PhD. Member of CCF. His main research interests include advanced compilation and high perfor-mance computing.

Shan Zheng, born in 1964. PhD, professor, PhD supervisor. Senior member of CCF. His main research interests include computer architecture, information security and high performance calculation.

Zhang Jiahao, born in 1991. Master. His main research interests include computer architecture and high performance computing.