面向ARM平台的二进制翻译系统标志位优化

杜 彬,赵瑞珍,李 琼

(北京交通大学计算机与信息技术学院,北京100044)

面向ARM平台的二进制翻译系统标志位优化

杜 彬,赵瑞珍,李 琼

(北京交通大学计算机与信息技术学院,北京100044)

二进制翻译系统是不同平台之间代码移植的桥梁,而系统性能是制约其应用的主要因素。在二进制翻译中,翻译经过标志位分析处理后的非冗余标志位需要较多的指令,极大影响了系统的性能。针对该问题,提出一种标志位的模式优化方法,在标志位分析处理基础上,将定值标志位和使用标志位的ARM指令组成固定模式,根据不同的模式用MIPS指令组合翻译达到相同的语义。实验结果表明,利用标志位的模式优化方法可使翻译产生的MIPS代码量减少14%,系统性能平均提高13.7%。

二进制翻译;标志位的模式优化;条件执行;模式头;模式尾

1 概述

在当今的手持终端(如手机、平板电脑)市场中, ARM占据着绝大多数的份额,而MIPS作为后来者,缺乏与之相配套的应用软件。由于ARM平台上的很多应用软件并不开源,大大增加了程序移植的难度。在这样的条件下,使用二进制翻译系统,将ARM平台上的软件直接移植到MIPS平台上,是一个合适的选择。而性能是制约二进制翻译系统应用的一个重要因素,为了提高系统的性能,对它的优化必不可少。标志位优化就是其中一个非常有效的优化。

Fx!32[1]是一个结合解释执行和静态翻译2种模式的二进制翻译系统。采用延迟计算的方法,在执行标志位定值的指令时,把所有计算标志位需要用的信息(包括操作数,操作码等信息)保存起来,当需要使用到标志位时再通过保存的信息计算标志位。

Queensland大学开发的 UQBT[2]可变源、可变目标的静态二进制翻译器,在与ISA相关的低层中间表示转化到与ISA无关的高层中间表示的过程中,通过数据流分析去除冗余的标志位定值,对非冗余的标志位引用标志位,按照一定模式转化为相应的高层中间表示。但该方法只对由高级语言编译生成的程序才有效,如果源程序本身是汇编代码而导致不能正确确定模式,这种方法就失效了。

Intel的IA32 EL[3]构建不完全数据流图,一般包含多个基本块,然后在此数据流图上进行标志位分析。但是在基本块边界上,就会产生冗余的无法消除的标志位定值。

文献[4-5]提出了基于edge profile的热路径选择算法FHFS,并在热路径上实施基于模式匹配的指令组合优化翻译和标志位延迟计算的优化,其中模式匹配是将相邻的一些指令作为指令组合翻译。

文献[6]中提出的立即计算和延迟计算相结合算法以及数据流和延迟计算相结合算法,这2个算法本身开销很小,但是只对基本块内部进行分析,而基本块间采用延迟计算,所以只是基本块内的冗余标志位定值可以消除。

文献[7]提出基于动态反馈的标志位线性分析算法,该算法分析后继基本块的标志位定值和引用,可以基本上可以消除冗余标志位定值。

文献[8]描述了一个为嵌入式系统设计的将ARM二进制程序翻译到类MIPS平台的静态二进制翻译器,在FX!32标志位分析处理基础上,对于需要计算的标志位,分配4个独立的寄存器来保存4个标志位以减少定值每个标志位时的移位操作[8]。但当目标平台的寄存器不够时,该方法有局限性。

文献[1-3,6-8]中标志位分析处理后还需对非冗余的标志位定值及其使用进行翻译,文献[4-5]中仅对简单的模式进行匹配翻译。本文在上述分析的基础上,提出模式化翻译ARM标志位的方法,将定值标志位的ARM指令与使用标志位的ARM指令组成一个模式,翻译时根据不同模式用不同MIPS指令组合达到相同的功能,这样不仅可以消除文献[8]中寄存器可能不够用的局限性,还可以减少因翻译标志位的定值和使用而产生的代码量。

2 标志位的模式优化

定义 定值标志位的ARM指令为模式头,使用标志位的ARM指令为模式尾。

标志位的模式优化就是以基本块(translation block,TB)为单位扫描并查找记录TB内模式头和相应的模式尾,翻译的时候根据记录的头尾组合信息用相应的MIPS指令来实现标志位的定值及其使用。

模式头尾组合通常有3类:一个模式头对应一个模式尾,即一头一尾;一个模式头对应多个模式尾,即一头多尾;一条指令既定值标志位又本身是否执行需要看条件是否满足,如addseq,若eq条件满足才执行add并根据运算结果置相应标志位,定义add为潜在的模式头,而这样的一类模式组合中,既有模式头和模式尾,也存在潜在的模式头,称为多头多尾。

图1是SPEC2000中175.vpr程序经过标志位分析处理后翻译生成的一段代码,源平台为ARM,目标平台为MIPS。在这段代码中,ARM指令cmp比较2个寄存器r2和r3的值,根据比较结果对C和Z标志位定值。指令bls中ls是执行条件,使用标志位C和Z,若C==0或者Z==1则跳转[9]。标志位的一次定值,即更新标志位寄存器相应标志位的翻译,平均需要4条MIPS指令[10],标志位一次使用的翻译平均需要2条MIPS指令。由此可见,在标志位分析处理之后,翻译非冗余的标志位定值和使用依然产生较多的指令。

图1 删除冗余标志位定值后翻译产生的代码

2.1 模式头尾组合的查找和记录

对模式头尾组合的查找和记录是从TB的最后一条指令开始往前扫描完成的,具体的算法语言描述如下:

(1)从后往前挨个指令扫描TB,若该指令不是模式尾,即不使用标志位,则继续往前查找,若是模式尾,则转步骤(2)。

(2)从该模式尾往前扫描对应的模式头,即模式头必须定值了该模式尾所有使用到的标志位,若找不到对应的模式头,则转步骤(1)继续查找新的模式尾,若能找到,则记录模式头尾信息,转步骤(3)。

(3)从该模式尾再往前扫描直到模式头,查找尾对应的潜在模式头,同样潜在模式头也必须定值了该模式尾所有使用的标志位。记录该模式尾对应的所有潜在模式头。

(4)重复步骤(1)～步骤(3)直到扫描到TB的第1条指令结束。其中,步骤(1)、步骤(2)完成一头一尾和一头多尾的查找和记录,若多个不同的模式尾对应相同的模式头即同一条ARM指令,说明这是一头多尾形式,需要将多个尾记录到尾链表中,并记录多个尾的位置信息,如是第几个尾。步骤(3)完成多头多尾的记录,模式尾对应的所有潜在模式头也需记录在潜在模式头链表中。至此,TB中所有模式记录完毕,下面就可以根据不同的模式进行翻译了。

2.2 各种模式的翻译

各种模式头包括潜在模式头的翻译方法相同,翻译模式头的时候是保存源操作数还是保存目的操作数要看尾的信息。在一个或多个模式尾的翻译中有需要源操作数的,那么翻译模式头就保存源操作数,若翻译遇到需要目的操作数的模式尾时,只需利用源操作数运算便可得到目的操作数。另外需要注意的是,若后继TB使用了该模式头定值的标志位,那么此处标志位的定值翻译不可省略。

2.2.1 一头一尾

模式中无潜在模式头且只有一个模式尾,就用一头一尾的方法来处理。图1中的模式是典型的一头一尾形式,只有一个模式头cmp和一个模式尾bls。这个模式的翻译如图2所示。

图2 模式优化后的代码

r2,r3为源操作数,翻译cmp时只需将源保存,翻译bls时利用保存的源比较跳转,就可以完成这2条ARM的功能。

2.2.2 一头多尾

模式中无潜在模式头且有多个模式尾,就采用一头多尾的方法来处理。这里模式尾的翻译和该模式尾在多个尾中的相对位置有关。一种情况是各个尾的执行条件不同,这种情况可以看成多组一头一尾的形式,不再赘述。另一种比较特殊且常见的情况是多个模式尾相邻且执行条件相同,图3是多个相同模式尾相邻且执行条件相同的情况,来自SPEC2000中164.bzip程序经过标志位分析处理后生成的代码片段。

图3 多个模式尾相邻且执行条件相同的翻译

翻译第一个模式尾不再是让其跳转到下一条指令的地址,而是跳转到最后一个尾的下一条指令的地址,这样在实际运行时如果条件lt不满足,就直接跳转到add执行。其余模式尾的条件可以不用翻译。

2.2.3 多头多尾

模式中有潜在的模式头,那么此模式为多头多尾形式。图4是SPEC2000中181.mcf程序经过标志位分析处理后生成的代码片段。第1个和第2个模式尾的翻译方式同一头多尾形式,第3个模式尾的翻译有所不同,因第3个尾使用的标志位,既可能是sub定值的,又可能是teq定值的(若第3条ARM指令的执行条件满足)。经分析发现,模式sub-eq和teq-eq可以用一种翻译方式,即跟t8中保存的运算结果比较跳转,这样把第3个尾翻译为 bnez t8, target,则t8总是保存定值标志位的那条ARM指令的目的操作数,就能保证翻译的正确性。因此诸如sub-eq,teq-eq这些具有相同执行条件但模式头不同的模式,翻译时尽量用相同的MIPS指令。

图4 多头多尾的翻译代码

图5统计了SEPC CINT2000中10个程序中出现多头多尾模式的个数,共计1 019个多头多尾模式都可以用上述方法翻译而正确执行。

图5 多头多尾模式的数量

3 实验数据

实验的目标平台是兼容MIPS的龙芯3A机器,主频900 MHz,内存2 GB。将模式优化应用一个从ARM到MIPS的二进制翻译系统中,经SPEC2000 CINT2000目录中10个整形基准程序测试通过。其中 SPEC2000是由 crosstool-ng-1.18.0建立的ARM交叉编译工具链编译生成,由于工具链限制, 253.perlbmk和300.twolf没有编译成功,在此不对这2个基准程序做实验测试。

3.1 指令数比

图6给出了在SPEC2000 test输入集下,模式优化前后的指令数比。

图6 模式优化前后的指令数比

这里用指令数比作为衡量系统性能的一个指标。指令数比就是翻译1条ARM指令平均需要MIPS指令的条数。以164.gzip为例,优化前,翻译1条ARM指令大概需要4.2条MIPS指令,优化后,翻译需要的MIPS指令数为3.6。平均来看,模式优化后比模式优化前翻译需要的MIPS指令数减少达14%。

3.2 系统性能

图7给出了在SPEC2000 test、ref、train3个输入集下,应用模式优化后二进制翻译系统的性能提升。平均来看,应用模式优化带来的系统提升在各个输入集下到达13.7%。

图7 模式优化后二进制翻译系统的性能

4 结束语

本文提出一种在ARM翻译到MIPS中的标志位模式优化方法,利用若干MIPS指令组合来达到某些固定ARM指令组合的功能,这样可以减少翻译标志位的定值和使用而生成的代码量。此优化方法经过正确性验证,可以有效地降低翻译标志位而造成的代码膨胀,从而提高系统的性能。文中多头多尾的处理只是对SPEC2000的10个整形基准程序中出现的多头多尾情况做了讨论及处理。下一步将对该部分内容继续进行研究。另外,文中保存操作数的指令可以利用经典编译优化进一步精简。

[1] Chernoff A,Herdeg M,Hookway R,et al.FX!32——A Profile-directed Binary Translator[J].IEEE Micro, 1998,18(2):56-64.

[2] Cifuentes C,van Emmerik M.UQBT:Adaptable Binary Translation at Low Cost[J].IEEE Computer,2000,33 (3):60-66.

[3] Baraz L,Devor T,Etzion O,et al.IA-32Execution Layer:A Two-phase Dynamic Translator Designed to SupportIA-32 Applications on Itanium ®-based Systems[C]//Proc.of MICRO’03.Piscataway,USA: IEEE Press,2003:191-201.

[4] 白童心.动态二进制翻译与动态优化相关问题研究[D].北京:中国科学院计算技术研究所,2004.

[5] 白童心,冯晓兵,武成岗,等.优化动态二级制翻译器DigitalBridge[J].计算机工程,2005,31(10):103-105.

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

[7] 唐 锋,武成岗,冯晓兵,等.基于动态反馈的标志位线性分析算法[J].软件学报,2007,18(7):1603-1611.

[8] Chen J Y,Wang W,Huang T H,et al.On Static Binary Translation and Optimization for ARM Based Applications[C]//Proc.ofthe 6th Workshop on Optimizations for DSP and Embedded Systems. New York,USA:ACM Press,2008:1-10.

[9] ARM.Architecture Reference Manual ARM.v7-A and ARM®v7-R Edition[EB/OL].(2011-10-21).http:// infocenter.arm.com/help/topic/com.arm.doc.ddi0406b/ index.html.

[10] MIPS.Architecture for Programmers Volume II-A:The MIPS64.Instruction Set[EB/OL].(2011-05-21).http://scc. ustc.edu.cn/zlsc/lxwycj/200910/W020100308600769158777. pdf.

编辑 索书志

Flag Bit Optimization in Binary Translation System Oriented to ARM Platform

DU Bin,ZHAO Rui-zhen,LI Qiong
(School of Computer and Information Technology,Beijing Jiaotong University,Beijing 100044,China)

Binary translation system is a bridge between codes of different platforms,while the performance of the system restricts its application.In binary translation,after data flow analysis on those flags,the translation of conditional flags still needs plenty of native instructions which greatly affects the performance of systems.To solve this problem,a flag pattern optimization method is presented,this method which is based on data flow analysis makes ARM instruction of definition flag and usage flag become a fixed pattern,and depends on different patterns to achieve the same semantic by choosing appropriate MIPS instructions.Experimental results show that MIPS code generated by translating has a 14% reduction,and the system performance is improved by 13.7%.

binary translation;pattern optimization of flag bit;conditional execution;pattern head;pattern tail

1000-3428(2014)10-0318-04

A

TP391

10.3969/j.issn.1000-3428.2014.10.059

杜 彬(1986-),男,硕士研究生,主研方向:二进制翻译,编译优化;赵瑞珍,教授、博士生导师;李 琼,硕士研究生。

2013-09-09

2013-10-22E-mail:11120422@bjtu.edu.cn

中文引用格式:杜 彬,赵瑞珍,李 琼.面向ARM平台的二进制翻译系统标志位优化[J].计算机工程,2014, 40(10):318-321.

英文引用格式:Du Bin,Zhao Ruizhen,Li Qiong.Flag Bit Optimization in Binary Translation System Oriented to ARM Platform[J].Computer Engineering,2014,40(10):318-321.