（计算机软件与理论专业论文）动态二进制翻译与动态优化相关问题研究.pdf

摘要 动态二进制翻译和动态优化是软件移植和提升系统性能的新途径，近年来围 绕该领域展开了大量研究，并出现了一系列有影响的系统。由于在动态二进制翻 译和动态优化中，大量工作在运行时完成，因而提高了对开销控制的要求，必须 承认，作为具有移植背景的技术来说，这是其被动的一面。但延迟到运行时也有 其积极的意义和特殊的机会，那就是可以利用静态无法获得的即时信息进行有针 对性的优化。鉴于此，在技术路线上，动态二进制翻译和动态优化也应该采取跟 静态编译及优化不同的途径，静态侧重分析，而动态则应侧重反馈：静态要求全 面，而动态则强调重点；静态算法追求最优性，而动态的策略讲究简单高效。 本论文中作者的主要贡献分为两部分： 第一部分关于动态二进制翻译中如何解决效率和翻译质量相协调的问题，作 者提出了基于模式的动态二进制翻译。与编译时依靠分析的优化方法不同，我们 根据统计规律将频繁出现的模式提取出来，离线完成优化翻译的工作，并将优化 了的模式翻译方式嵌入到翻译器中，动态翻译代码时一旦遇到该模式即可套用 之。该方法既可以优化翻译质量，又减少了大量运行时优化开销。 第二部分比较动态优化中的热路径预测策略。热路径预测是动态优化中的关 键，它涉及到如何高效的收集程序运行时信息以及如何利用程序运行特征进行实 例化优化。本文首先给出了一个基于e d g ep r o f i l e 的热路径预测方案e p b ，而后 将其与著名的d y n a m o 热路径选择方法进行实测比较，试验结果表明，由e p b 生成的热路径代码具有更好的局部性，相应的，运行性能提高更显著。 关键词：动态二进制翻译按模式翻译动态优化热路径 垫查兰些型型堡皇垫查垡些塑茎塑璧型塑 t w o t o p i c s o nd y n a m i c b i n a r yt r a n s l a t i o na n do p t i m i z a t i o n b a it o n g x i n ( c o m p u t e ra r c h i t e c t u r e ) d i r e c t e db yf a nj i a n p i n g d y n a m i cb i n a r yt r a n s l a t i o na n dd y n a m i co p t i m i z a t i o n a r en e w a p p r o a c h e st om i g r a t e a p p l i c a t i o n sa n dt oi m p r o v es y s t e mp e r f o r m a n c e r e s e a r c h e sa r ec a i t i e do u ti nt h i s f i e l da l o n gw i t hm a n yi n f l u e n t i a ls y s t e m sb u i l t i nd y n a m i cb i n a r yt r a n s l a t i o na n d d y n a m i co p t i m i z a t i o n ，l o t s o fo p t i m i z a t i o nw o r k sa r e d e l a y e dt or 、_ m t i m e ，w h i c h d e m a n d sm o r eo no v e r h e a dc o n t r o l l i n g ，d e s p i t eo ft h eo v e r h e a dl i m i t a t i o n ，w ea r e p r o v i d e dw i t hm a n yo p t i m i z a t i o no p p o r t u n i t i e sa tr u n t i m et h a t a r en o ta v a i l a b l ea t s t a t i c c o m p i l et i m e t h e r e b yd y n a m i cb i n a r yt r a n s l a t i o n a n dd y n a m i co p t i m i z a t i o n s h o u l dt a k ed i f f e r e n tm e t h o d sf r o ms t a t i c c o m p i l a t i o n i nt h a t c o n s i d e r i n gm o r e f e e d b a c kt h a na n a l y s i s ，d e m a n d i n gm o r e e f f i c i e n c yt h a no p t i m u m 1 、h et h e s i sm a i n l y c o m p r i s e st w op a r t s ： i nt h ef i r s t p a r t ，i s s u e sa b o u tt r a n s l a t i o ne f f i c i e n c ya n dq u a l i t ya r ed i s c u s s e da n da p a t t e r n b a s e d b i n a r y t r a n s l a t i o nm e t h o di s p r o p o s e d w ef i g u r e o u t f r e q u e n t t r a n s l a t i o np a t t e r n sa c c o r d i n gt os t a t i s t i c a la n a l y s i sa n de n c o d et h ep a t t e r n si n t ot h e t r a n s l a t o ra sm e t a - i n f o r m a t i o n o n c et h ep a t t e r n sa r cm a t c h e dd u r i n g t r a n s l a t i o n ， s o u r c eo b j e c tc o d e s e g m e n t sa r ee a s i l ym a p p e dt ot a r g e to b j e c tc o d e t h ep a t t e r n b a s e dt r a n s l a t i o nm e t h o dn o t o n l yi m p r o v e s t r a n s l a t i o n q u a l i t y , b u ta l s o r e d u c e s m n t i m eo v e r h e a d i nt h es e c o n dp a r t ，w ec o m p a r et w oh o tt r a c ep r e d i c t i o ns c h e m e s f i r s tw e p r o p o s e a l l e d g ep r o f i l eb a s e dh o tt r a c ep r e d i c t i o ns c h e m ec a l l e de p b ，t h e ni n t r o d u c ea nf a m o u s h o tt r a c e p r e d i c t i o n m e t h o d d y n a m o ，b o t h a r e i m p l e m e n t e d i no u r s y s t e m e x p e r i m e n t ss h o w t h a te p b p r o d u c e sh o tt r a c ec o d ew i t hm o r el o c a l i t yt h a nd y n a m o ， a n db e h a v e sb e t t e ra st or u n t i m ep e r f o r m a n c e k e yw o r d s ：d y n a m i cb i n a r y t r a n s l a t i o n ；p a t t e r n b a s e d t r a n s l a t i o n ；d y n a m i c o p t i m i z a t i o n ；h o tt r a c e 动态一进制翻详与动态优化相关问题研究 声明 本人声明所呈交的论文是我个人在导师指导下进行的研究工作 及取得的研究成果。就我所知，除了文中特别加以标注和致谢的地方 外，论文中不包含其他人已经发表或撰写过的研究成果。与我一同工 作的同志对本研究所做的任何贡献均已在论文中作了明确的说明并 表示了谢意。 作者签名： 白彳小 日期：山扫p ，r 2 j 关于论文使用授权的说明 中国科学院计算技术研究所有权处理、保留送交论文的复印件， 允许论文被查阅和借阅；并可以公布论文的全部或部分内容，可以采 用影印、缩印或其它复制手段保存该论文。 名碡。f 锄繇甥嘲坼q ， 墨! 兰三垄型壁堡墨垫查垡些尘塑一 第1 章二进制翻译及动态优化介绍 软件应用的移植是处理器升级换代所面临的重要问题。开发新的处理器可能 会因为失去相应软件的支持，而影响其广泛应用；另一方面，没有广泛应用的处 理器也很难得到更多软件开发商的支持。这种处理器和支持软件之间相互钳制的 关系，既使得新处理器的设计不得不考虑兼容老处理器，也阻碍了新处理器的广 泛应用。在这种情况下，研究不同平台之间的软件移植，不仅对软件重用有重大 意义，更可以开阔处理器研发的思路，促进新处理器的创新。 一般可以有几种方法把老处理器上的代码移植到新处理器上 1 】，分别是：1 ， 提供专门的运行模式执行老代码，如i n t e l 的i t a n i u m 处理器存在专门执行x 8 6 代 码的硬件；2 ，重新编译：3 ，使用软件方法，解释或翻译应用程序。采用第一种 方法，显然无法利用新处理器的些先进特性，并且增加了新处理器韵硬件复杂 度，甚至还会影响原有代码的执行效率；采用第二种方法可以达到很好的效率， 但由于有些程序已经无法获得源代码，因而失去定的可行性；有些程序依赖于 共享代码库，而这些共享代码以目标代码形式出现，可能没有源码；有些源程序 语者没有编译到新指令集的编译器；此外操作系统的差异还可能使得只有修改源 代码4 能重新编译这些例程。 第三种方法，称之为二进制翻译( b i n a r yt r a n s l a t i o n ) 应运而生。它是一种 直接翻译可执行二进制程序的技术，能够把一种处理器上的二进制程序翻译到另 外一种处理器上执行。它使得不同处理器之间的二进制程序可以较容易的相互移 植，扩大了硬件软件的适用范围，有助于打破前面提到的处理器和支持软件之 间相互限制的局面。 1 1 二进制翻译技术概述 二二进制翻译也是一种编译技术，它与传统编译的差别在于其编译处理对象不 同。传统编译处理的对象是某一种高级语言，经过编译处理生成某种机器的目标 代码；二进制翻译处理的对象是某种机器的二进制代码，该二进制代码是经过传 统编译生成的，经过二进制翻译处理后生成另一种机器的二进制代码。按照传统 编译程序前端、中端和后端的划分，我们可以理解为二进制翻译是拥有特殊前端 的编译器。 垫查三些i ! 塑堡兰垄查垡些塑薹塑星塑互一 1 11 二进制翻译方法分类及比较 基于软件的二进制翻译，可以分为两类：静态翻译，动态翻译。除翻译外， 解释也是一种执行方式，由于解释容易保证程序的正确性，常常被用于辅助翻译。 解释执行对源处理器代码中的每条指令实时解释执行，系统不保存也不缓存 解释过的指令，不需要用户干涉，也不进行任何优化。解释器相对容易开发，比 较容易与老的体系结构高度兼容，但效率很差e 1 e 2 。 静态翻译是在源处理器代码执行之前对其进行翻译，将源机器上的二进制可 执行程序文件a 完全翻译成目标机器上的二进制可执行程序文件b ，然后在目 标机t 执行程序b 。一次翻译的结果可以多次使用。静态翻译器离线翻译程序， 有足够的时间进行更完整细致的优化，效率较高。然而，静态翻译器可能无法完 整地翻译一个程序 3 ，因而需要依赖解释器的支持 2 ：而且静态翻译器需要终 端用户的参与【1 ，这给用户使用造成了很大不便。 动态翻译则在程序运行时对执行到的片段进行翻译，克服了静态翻译的一些 缺点，比如晚静态翻译时由于不能知道控制流中某点的寄存器或内存的值，从而 不能解决代码挖掘问题。而且动态翻译还可以解决大部分实际情况中的自修改代 码问题，而这对于静态翻译是不可能解决的【2 】。动态翻译可以利用执行时的动 态信息束发掘静态编译器所不能发现的优化机会。动态翻译器对用户可以做到完 全透明，无需用户干预 4 e 5 】 6 7 。 下面我们用表格的形式总结一下上述三种方法的优缺点【1 【2 ： 袁格三种软件执行方式的比较 优点缺点 解释执行 容易开发，不需要用户干涉，高度兼容效章根差 静态翻译离线熟详，可以进行更好的优化，效率依赖解释器、运行环境的支持，需要 较高。终端用户的参与给用户使用造成r 不便 动态翻译无需解释器和运行环境支持，无需用户翻译的代码效率不如静态翻译高，对 参| = j ，利用动态信息发掘优化机会目标机器有额外的守间开销 1 1 2 动态二进制翻译系统框架 动态二进制翻译是一种兼顾正确性和效率的软件执行方式，其基本框架也相 对固定，图1 给出了结合解释的动态二进制翻译器的大致系统结构。 兰! 童三堂型塑堡墨垫查垡些坌塑 图1 动态二进制翻译系统框架 目标机嚣平台 斗调用关系 卜数据流 一个解释执行和动态翻译相结合的二进制翻译系统，通常包括控制模块、启 动模块、运行环境仿真模块、解释器、动态翻译器、本地码执行模块等主要模块。 控制模块控制整个系统的翻译执行过程，从而可以使系统的工作对用户透明；本 地码执行模块负责在翻译系统自身的执行和生成的目标机器代码执行之间的切 换工作：运行环境仿真模块支持源机器代码调用系统调用以及处理信号。 整个翻译执行过程如下：在目标机器平台下执行源机器代码时，嵌入操作系 统的启动模块启动整个翻译系统，并将源机器代码加载到内存，然后控制模块启 动解释器对源机器代码解释执行，并根据需要统计代码执行路径等信息。当某段 源机器代码的执行达到一定热度，就启动动态翻译器翻译并对其进行简单优化， 编码生成目标机器代码片段，此后再执行到该源机器代码片段时就不再解释执 行，而是通过本地码执行模块来直接执行翻译生成的目标机器代码。 为了提高翻译后代码的效率，对于那些执行热度极高的目标机器代码片段， 还需要对其进一步优化，这就会用到下文提到的动态优化技术。 1 2 动态优化技术简介 动态优化技术 8 】 9 1 0 1 1 】 1 2 1 3 】【1 4 】【1 5 】既可以作为一种独立的代码优化 技术，又可以作为二进制翻译所必需的后端优化器，而二进制代码的动态优化技 术也需要解码器等模块的支持，因此动态优化技术与二进制翻泽技术具有密切的 关系。 动态优化技术是在应用程序的运行时刻对程序的信息进行收集和分析，并对 程序的关键段进行必要的优化，从而提高程序的性能。由于在动态时刻对程序进 行上述处理要耗费时_ 、白j ，所以动态优化必须及时发现程序的关键段，并采用快速 苎查= 些型型堡! 堕查垡些塑耋塑望型丝一 而高效的分析、优化方式，以得到理想的优化效果。动态优化系统所用到的热路 径选择技术可以用纯软件方式实现，若硬件结构可以提供必要的支持，则动态优 化系统的效率可望得到显著提高【1 6 】。 二进制翻译要兼顾正确性和高效率，在实现不同系列的c p u 间的软件平滑 移植目标时，动态翻译能够保证程序执行的正确性，但其造成运行时的开销需要 通过优化生成高质量的目标机代码来弥补，从而动态优化作为翻译器后端优化器 的研究不断涌现：即便是同一个系列的芯片，由于不同的“代”之间，芯片的具体 硬件资源不同，虽然面向旧的芯片的可执行代码可以直接在新的芯片上执行，但 由于该二进制代码程序不能充分利用新的芯片的功能部件，程序的效率不能令人 满意，凶此也需要动态重优化技术的支持。 1 3 有代表性的二进制翻译及动态优化系统 目前，二进制翻译已经得到了广泛的重视和研究，见表格2 。早在1 9 8 7 年， h p 公司就开发了最早的一个商用二进制翻译系统，用来将h p3 0 0 0 的客户转移 到新的p a 体系结构上。1 9 9 1 年t a n d e m 公司开发了个将c i s c 移植到r i s c 的静态翻译器，采用解释器作为补充。1 9 9 2 年开始d e c 公司开发了系列的二 进制翻译器，用柬将v a x v m s ，m i p s u n i x ，s p a r c u n i x 以及x 8 6 w i n n t 上的 代码翻译到他们新开发的a l p h a 机器上，这其中以f x 1 3 2 最有代表性。1 9 9 4 年 a p p l e 公司在p o w e r m a c 上开发了一个m o t o r o l a6 8 0 0 0 解释器，后来改进成翻 译器。i b m 公司1 9 9 6 年开发的d a i s y ，是利用二进制翻译调度p o w e r p c 代码到 超长指令字( v l i w ) 处理器，增加并行性。1 9 9 9 年开发b o a 系统，动态翻译了 p o w e r p c 的整个系统，用简单的指令实现原来语义，简化硬件。2 0 0 0 年t r a n s m e t a 公司宣抽了t r a n s m e t a 处理器芯片和同态代码软件，用来在完全不同的硬件基础 之上翻译运行x 8 6 代码，甚至包括w i n d o w s 。 以e 提到的翻译器都与机器特性高度相关，重利用是非常困难的。1 9 9 4 年 a 1 t 公司丌发的f l a s h p o r t 二进制翻译器可以运用到多个源、目标平台。但不 能完全自动化，需要一个专业用户通过图形用户界面( o u i ) 进行交互完成。 q u e e n l a n d 开发的u q b t 以及u q d b t ，都是基于对机器指令和操作系统属性描 述的可变源、可变目标的二进制翻泽器框架，可以看作是一个翻译器的生成器。 表格2 二进制翻译器 名称研究单参考目的源平台目的平台 位 b e r g h e th p 【1 8 最早的商用二进制翻泽( h p 3 0 0 0 ，( h pp r e c i s i o n a l ( 1 9 8 7 )系统；用于软件模拟和m p e v ) a r c h i - t e “u ” 墨! 皇三垄! ! 塑堡塾望查垡些竺塑一 目标代码翻译 m p e x l l m i m i cl b m 1 9 】 对每条源机器指令代码 i b m s y s t e m i b mr tp c ( 1 9 8 7 ) 扩展倍数为4 的软件模 3 7 0 拟器 a c c e 【e r a - t a n d e 2 0 将c i s c 移植到r i s c 的 t n s c i s ct n s 瓜 t o t ( 1 9 9 1 ) m静态翻译器，采用解释 器作为补充 v e s t d i g i t a l 2 i 2 2 从d i g i t a l 公司的v a x( v a x ，( a l p h a ， 和m i p s 到6 4 位a l p h ao p e n v m s ) ，o p e n v m s ) ， ( 1 9 9 3 ) 静态翻译器，采用解释 ( m 1 p s ，( a l p h a ，o s f 1 ) 器作为补充u l t r i x ) f l a s h p o r t a t t 2 】 跨越多个源和目标平台 6 8 x 0m a c p o w e rm a c ，i b m ( 1 9 9 4 ) 的二进制翻译，需要人 旧mr s 6 0 0 0 s p a r c ， 为干预 s y s t e r r d 3 6 0 ，h p ，m i p s ，p e n t i u m 3 7 0 ，3 8 0 m a e a p p l e 2 】在p o w e r m a c 上开发的 6 8 0 x 0r i s c b a s e du n i x ( 1 9 9 4 ) 一个m o t o r o l a6 8 0 0 0 解 释器，后来改进成翻译 器。 f r e e p o r td i g i t a l 2 】 静态翻译器，采用解释 ( s p a r c ，( a l p h a ，o s f 1 ) e x p r e s s器作为补充，翻译用户s u n o s ( 1 9 9 5 ) 模式程序，3 2 位、6 44 1 x 、 位都可 f x 3 2 d i g i t a l 2 3 1 2 4 流行的x 8 6 应用程序到 ( x 8 6 ， ( a i p h a ，w i n d o w s ( 1 9 9 6 )a l p h a 的混合模拟器和 w i n d o w s n t 、 _ _ = 进制翻译器 n t ) d a i s y i b m 【5 】利用二进制翻译调度( p o w e r p c ，v l l w ( 1 9 9 6 )p o w e r p c 代码到超长指 u n i x v l 令字( v l l w ) 处理器，增 加并行性 a r i e sh p 4 】解释和动态翻译相结h pp r e c i s i o ni a 。6 4 ( 1 9 9 9 )合，简化了应用程序从a r c h i t e c h pp r e c i s i o n t u r e ， a r c h i t e c t u r e 、到i a 一6 4 的翻译； b o a】b m 【6 2 5 动态翻译了p o w e r p c ( p o w e r p c ， ( p o w e r p c ，u n i x v ) ( 】9 9 9 )的整个系统，用简单的 u n i x v ) 指令实现原来语义，简 动态二进制翻译与动态优化相关问题研究 化硬件 u o b t 、 q u e e n s 2 2 6 1 1 2 7 】 利用机器指令描述开发可变 可变 u q d b j 【 3 0 】 的可变源、可变目标的 i a n d 人 静态( 动态) 二进制翻 译器 c o d et r a n s m 7 动态翻译运行x 8 6 代 x 8 6t r a n s m e t a 芯片 m o r p h i n g 码，翻译全部程序包括 s o t t w a r e t a 公司 w i n d o w s 操作系统 ( 2 0 0 0 ) b i n t r a n维也纳 f 3 1 多源多目标的动态翻译可变可变 技术大 器 学( 奥地 利) 由于静态二进制翻译器的局限性，所有的实用系统都不采用纯静态的翻译， 而是选择了动态模拟或动态翻译再加上动态优化的方式，这样就可以在保证程序 能够正确执行的基础上，尽量提高效率，如d a i s y ，a r i e s ，b o a ，t r a n s m e t a 等 系统。而且动态翻译还可以对用户透明，从而无需用户对其过程进行干涉。 h p 公司开发的d y n a m o 8 9 是一个动态优化器的原型。它的输入是本地二 迸制可执行代码，通过解释执行并观察程序的行为而不需要任何采样代码，不需 要对代码进行预分析，也不需要为以后的执行写出信息。解释执行程序时收集的 p r o f i l e 信息帮助动态选择频繁执行的热路径( h o t t r a c e ) ，然后对这些热路径运用 代码重布局、消除间接转移、以及一些常规优化技术，然后将优化生成的代码存 放在一个软件c a c h e 中，当再执行到这些路径的时候就不解释而直接执行软件 c a c h c 中优化后的代码，从而使程序的执行效率得到大幅度提升。 j a v a 编译器将j a v a 源代码编译成平台无关的j a v ab y t e c o d e 格式，然后被分 发到备种平台，由j a v a 虚拟机( j v m ) 实时解释执行。在高性能实现的j v m 中， j u s t i n - t i m e ( j i t ) 编译器实时地将j a v a 字节码翻译成本地码，来减少解释执行 的开销。由于翻译本身在程序执行期间进行，编译时间成为程序执行时间的一部 分，因而编译中的优化需要考虑动态优化的特点，即需要在优化的代码质量和编 译时间之矧进行权衡。许多j a v a 虚拟机中都采用了j i t 编译，如s u n 公司的 h o t s p o t 3 4 、汉城国立大学和i b m 合作开发的开放源码l a t t ev m 3 3 、h a t e i 的 o r p 3 2 。 需要注意的是，虽然动态优化可以很好地提高动态翻译生成代码的效率，但 我们也不能忽视其自身的开销。因而用较低的动态优化开销换取关键路径上的高 效代码，是动态优化系统大幅度提高代码执行效率的关键。 第1 章二= 进制翻译及动态优化介绍 1 4 本论文要讨论的问题 在动态二进制翻译和优化中，协调质量与效率的关系是要解决的重要问题。 实际上，动态翻译和优化可以采取与静态编译时孑然不同的路线，静态编译优化 侧重语义分析，而动态翻译优化可以更依赖统计信息，静态编译优化强调全面， 追求算法的最优性，而动态翻译优化则可以针对重点，采用简单而效率高的算法 来达到较好的效果。 本论文中基于上述思想展开了两方面的研究，第3 章探讨如何解决兼顾翻译 质量和效率的问题，作者提出了基于模式的动态二进制翻译，与编译时依靠分析 的优化方法不同，我们将统计大概率出现的模式提取出来，对其进行优化翻译的 工作在离线时完成，并将这些模式的优化翻译方式嵌入到翻译器本身，旦遇到 陔模式即可套用之。该方法既可以优化翻译质量，又减少了大量运行时优化开销。 第4 章比较动念优化中的热路径预测策略。热路径预测是动态优化中的关 键，它涉及到如何高效的收集程序运行时信息以及如何利用程序运行特征进行实 例化优化。作者首先给出了一个基于e d g ep r o f i l e 的热路径预测方案e p b ，而后 将其与著名的d y n a m o 热路径选择方法进行实测比较，给出了算法对比和性能分 析。 在讨论这两个具体问题之前，第2 章将介绍动态本论文基于的二进制翻译系 统框架。 动态二进制翻译与动态优化相关问题研究 2 1 总体框架 第2 章动态二进制翻译系统框架 本论文展开的研究基于自主研发的动态二进制翻译系统，该系统以 x 8 6 l i n u x 为源平台，m i p s l i n u x 为目标平台。系统框架由五个模块构成，分别 是装入器、b t 控制器、基本块信息管理器、翻译器和优化器，如图2 所示。图 中圆弧框表示模块，方框表示翻译好的目标代码片段区域，实箭头代表控制转移， 虚箭头代表写入数据。 图2 动态二进制翻译器系统框架 本系统中翻译和执行的基本单位是基本块，即段以控制转移指令为结束的 顺序代码( 与编译中定义的基本块稍有区别，为了便于动态实现) ，并通过基本 块描述表来统一管理基本块信息，每个描述表项表示个基本块，内中包含该基 本块在源目标代码中对应的起始和终止地址，以及翻译后本地代码片段的入口地 址等信息。 系统的运作过程如下所述： 首先将要翻译执行的源可执行文件及其依赖的库文件装入进程空间，做必要 的初始化工作，而后携带源目标程序入口p c ( 程序计数器，后文中p c 均指源目 标程序的程序计数器值) 进入主循环，直到满足结束条件退出。主循环迭代过程 错2 章动态二进制翻译系统框架 第一步：首先在基本块描述表中查找以当前p c 为起始地址的基本块，如果 未找到则调用基本块信息管理器生成新的基本块( 从当前p c 到下一条控制转移 指令之静的顺序代码) ，而后调用翻译模块将该基本块翻译成本地代码，写入专 门存放基本块本地代码片段的内存区域，我们称之为b l o c k c a c h e 。 第二步：在返回基本块描述表项后查看当前是否满足优化条件，如果满足优 化条件则调用优化器进行优化，本系统实施的是基于热路径的优化，优化过程可 分为三个阶段：首先根据热路径选择算法寻找构成热路径的基本块序列，而后基 于该基本块序列进行优化，撮后是热路径的代码生成和嵌入，热路径代码被存入 的专门的内存区域，我们称之为t r a c ec a c h e 。而后返回b y 控制器。 第三步：在基本块描述表项中读出本地代码片段入口地址，将上下文切换到 本地执行态，跳入翻译好的本地码中执行。本地代码片段执行结束后返回，再经 上下文切换到b t 控制器，获得当前p c ，转入下个迭代。 2 2 基本块连接 执行完一个翻译好的基本块后，如果退回到b y 控制器则会极大的降低执行 效率，因为这需要进行上下文切换，很可能还伴随其它不必要的操作。如果在基 本块执行完毕之后，不进行上下文切换，紧接着跳入后继基本块的本地码入口， 则会大大提高执行效率。为实现这个功能，在翻译好的基本块后面添加小段用 于获得后继基本块入1 2 1 地址的代码，称之为连接s t u b 。如果目标基本块存在并已 经被翻译过，则不必经过上下文切换到b t 控制器来等待目标的指派，而直接跳 图3b r a n c h 类型基本块的连接s t u b 动态二进制翻译1 j 动态优化相关问题研究 转到目标基本块的本地代码入口，这种基本块连接是提高性能的有效手段之一a 为了实现基本块的快速连接，在系统实现中专门用一个寄存器r b b 存放指 向当甜基本块信息表项的指针。基本块信息表项中有几个域分别记录该基本块翻 译后本地码入口地址( e n t r y ) 、邻接基本块的信息表项指针( p t rb b t h r ) 以) ；f l z 目标基 本块的信息表项指针( p t l b b t g t ) ，这几个域是实现基本块连接所必需的。当进行 基本块连接时，只需以r b b 为基址，通过偏移来获得后继基本块信息表项指针， 继而找到后继基本块的本地码入口地址。图3 给出了b r a n c h 类型基本块的连接 s t u b ，它的含义如下： 首先判断是否跳转成功，如果成功则取出跳转目标基本块的信息表项指针， 否则取出邻接基本块的信息表项指针。 如果指针为空，院明后继基本块尚未生成，返回b t 控制器，否则以该指针 为基地址取出后继基本块的本地码入口地址域e n t r y 的值，如果该值为零，则表 明浚基本块尚未被翻译，没有对应的本地码入口地址，同样退回b t 控制器，否 则说明该基本块已被翻译，此时将前面取出的基本块信息表项指针存入r b b ，而 后跳入该基本块的本地码入口。 对于其它直接控制转移的基本块来说，其连接s t u b 的构成与b r a n c h 类型的 类似，并且由于没有条件判断而更为简单。对于间接控制转移的情况，例如 j u m p + 、c a l l + 或者r e t ，则需要调用查找间接跳转目标的过程。间接跳转的目标用 个h a s h 表来组织，以便于进行快速查找。 2 3 热路径连接 基本块连接虽然可以避免大量的上下文切换，从而大大提高执行效率，但 s t u b 代码本身还是有一定开销的，如前面介绍，基本块连接时，先要获得目标后 继基本块的信息表项指针，而后取出该信息表项中的本地码入v i 地址域的值，每 次取值都要判断是否为空，直到最后取出的目标地址有效，才可跳入执行。实际 上，当代码频繁执行时，这样的查找目标的方法也是冗长的。在引进热路径优化 时，为了减少查找目标的开销，我们对热路径代码之间的连接采取了更简单直接 的方法，如下所述。 当生成新的热路径代码时，如果热路径出e 1 对应的目标基本块已经是某个热 路径的入口，则该出口直接跳入热路径代码，无需再经过连接s t u b ，否则将出口 信息记录下来，以后若生成了以出1 2 1 目标基本块为入口的热n s 圣_ n ，则可进行重 定位。图4 ( a ) 给出了一个热路径连接的例子，当生成热路径t r a c e2 时，由于b 的出口目标是基本块d 已经是热路径t r a c el 的入口，因此该出口可以直接跳入 t r a c e2 ，丽无需构造s t u b 来查找d 的基本块信息表项；c 的出口目标是e ，当前 尚未形成以e 开头的热路径，因此只能通过s t u b 间接查找e 的入1 2 1 。生成热路 第2 章动态二进制翻译系统框架 径后将所有未能直接连接起来的出口信息记录下来，以后一旦生成了以对应出口 目标基本块为入v a 的热路径，再将出口目标重定位到新的热路径代码，从而实现 热路径的连接。如( b ) 所示，t r a c e3 在t r a c e2 之后生成，其入口为基本块e ，于 是将所有以e 为目标的热路径出口重定位，其中包括t r a c e2 ，这样t r a c e2 的c 出口就不再需要s t u b 中转了。 图4 热路径代码的连接 由于热路径占据了大部分执行时间，因此这种热路径间的直接连接可以显著 提高运行性能。 2 4 p r o f i l i n g 支持 为了支持动态p r o f i l i n g ，在基本块信息表项中设置两个域t h r _ e d g e _ c n t 和 t g t e d g e e n t ，分别记录两条控制流边的执行次数。由于有r b b 指向当前基本块 的信息表项，因此插装代码只需以r b b 为基址寄存器读写t h r _ e d g e _ c n t 和 t g t _ e d g e c n t 两个域即可完成快速的e d g ep r o f i l i n g 。对于b l o c kp r o f i l i n g 来说，则 只需用其中一个域来记录基本块的执行次数。 2 5 论文研究内容涉及的模块 本论文的研究内容涉及到图2 中的深色框模块。其中基于模式的动态二进 制翻译属于翻译模块中的内容，热路径预测属于优化模块中的内容。翻译模块和 优化模块是动态二进制翻译系统中关系性能最重要的部分，本文的研究内容体现 了系统的关键之处。 动态二进制翻译与动态优化相关问题研究 3 1 引言 第3 章基于模式的指令翻译优化 编译是一种完成从读入源语言程序到生成目标语言程序的变换过程，二进制 翻译可以被看成是一种特殊的编译形式，它与高级语言编译的区别在于前者是两 种低级语义之间的变换，而后者是从高级语义到低级语义的变换。由于二进制翻 译是低级语义之间的变换，如果两种指令集体系结构的语义差异较大，则难以实 现指令的直接对应。通常的作法有两种，一种是借助中间表示来完成源到目标机 器的翻译，例如u q b t 2 6 及u q d b t 3 0 采用多层中间表示的形式来沟通不同机 器之间的语义差别，根据机器描述将待翻译的源目标代码识别为源机器的低层中 间表示，再通过语义映射将源机器低层中间表示提升到高层中间表示，进而在高 层中间表示上进行机器无关的优化，而后将其翻译成面向目标机器的低层中间表 示，再展开针对目标机器的优化，最后将优化好的中间表示根据目标机器描述转 化成目标代码。采用多层中间表示的方法有利于实现多源多目标的= 进制翻译， 但带来的问题是运行时开销过大，因而不适合动态二进制翻译；另一种翻译方式 是无需中间表示，直接将源机器指令对应成目标机器的指令序列，例如 b i n t r a n 3 1 1 ，b i n t r a n 通过l i s p 描述的机器模型将每条源机器指令匹配成一串目标 机器的指令，并实现匹配的最小化，只要输入源和目标的机器描述便可自动生成 图5 两种动态翻译优化模式 第3 章基于模式的指令翻译优化 翻译器。由于没有结合指令序列上下文，这样作实际上是对每个源机器指令进行 单独的指令选择，翻译出来的结果也必然无法保证质量，因而需要在翻译出的目 标代码上展开类似编译时代码生成期间的优化，包括删除冗余指令、分配寄存器 以及指令调度等，以便适应目标体系结构的特性。 对于动态二进制翻译来说，这些工作需要在运行时进行，这种翻译优化模式 可以用图5 上部分的过程示意，分析这个过程不难发现其中大量工作具有重复 性。实际翻译中，有一些反复出现的异地代码片段被优化成相同的目标代码，我 们将这类情况称为翻译模式。如果优化个片段的开销是d ，则程序中该片段出 现7 次就会导致月声的丌销。如果d ，或h 值较大，那么优化翻译这段代码片段将 导致巨大的运行时开销。既然是一种翻译模式，就可以将模式的元信息嵌入到翻 译器本身中，在动态翻译时，一旦遇到符合该模式的代码即可完成直接对应，从 而省去了重复优化的开销。图5 下部分的过程表示基于模式的翻译，灰色部分 的重复开销被省略掉。 要达到较理想的优化效果，翻译模式的选取是重要的一环，合适的翻译模式 需要满足几个条件： 1 ，模式代码体现i s a 之间的较大语义间隔： 2 ，模式代码在程序中具有较高的出现频率： 3 ，模式代码基本反映一个高级语义单元，从而保证片段简短，以便实现快 速匹配。 所谓指令集之间的语义间隔，可以用图2 来解释，它是影响翻译质量的主要 s e m a n t i c u n i t 镕“。，。f v f ui s a l 一- + w ， w ji s a2 图6 不同i s a 之间的语义间隔 “w 。 w k i s a 2 垫查三垄型塑堡皇垫查垡些塑茎坚望塑型 原因。高级语言被编译生成目标代码时，同样一个高层语义单元被翻译成面向不 同i s a 的指令序列，其中 v ，) 为i s a1 的指令序列， w ， 为i s a2 的指令序 列。现欲将i s a1 的代码翻译成i s a2 的代码，若按照传统二进制翻译方法，每 条i s al 的指令被对应成i s a2 的指令序列，则 v 。 被翻译为 w 。 ， ，准确 的况，“w 。 是i s a 2 对i s a1 的模拟。同样表达s e m a n t i c u n i t i g h m f 的语义， fw 。 相对于 w ， 来得复杂，甚至通过编译优化也无法还原最优状态。我们 可以用 w 。 与 w 的差距来度量i s a 间的语义间隔，差距越大则语义间隔 越大。 面向单独指令的指令选择方式显然无法跨越指令集问的语义问隔，因为每条 指令的翻译都是孤立的。如果不进行语义的提升，则解决语义间隔问题最好的办 法是成组翻译，成组翻译的有效性便有模式保证。 动态二进制翻译的运行时性质要求模式必须有所选择，除了语义间隔较大 外，被选取的模式必须频繁出现，以便保证匹配的效率。这些满足要求的模式被 称为常见模式。常见模式的划分需要通过对程序运行信息进行量化统计分析来确 定。 本章内容主要论及x 8 6 指令集到m i p s 指令集之间的翻译模式，由于x 8 6 和m i p s 分别是c i s c 与r i s c 结构的典型代表，应用于这两者之间的方法对不 同指令集代码间的翻译具有借鉴意义。 3 2 x 8 6 到m i p s 指令集的语义问隔 x 8 6i s a 属于典型的c i s c 结构，而m i p s i s a 属于r i s c 结构。它们之间的 语义间隔表现在很多方面，包括访存模式的不同：x 8 6 可以直接改变内存单元的 值，而m i p s 只能先将数据载入寄存器进行计算再存入内存；x 8 6 有单字节、双 字节以及四字节三种寄存器模式可以选择，而m i p s 只有四字一种寄存器宽度f 仅 指3 2 位) 一种；这些语义间隔在翻译时比较容易处理，只需通过临时寄存器中转 一下即可。但有一种语义间隔对翻译质量影响较大，那就是x 8 6 指令集对标志 位的使用，导致与m i p s 指令集在处理基本计算的作法上存在很大差异。 一般的，整数计算可以分为有符号和无符号两种，对于x 8 6 体系结构来说， 有符弓和无符号的区别体现在对标志寄存器中标志位( o f 记录溢出，c f 记录借 位，s f ? 记录符号位，z f 记录是否为零) 的读写上，而m i p s 体系结构将有符号、 无符号的区别直接体现在指令中。下面以加法操作为例比较两种体系结构实现的 不同。 x 8 6 的加法指令形式为 3 5 1 ： f o r m a t ： 0 4 由a d da l m m 8 a d d i m m 8 t o a l 墨! 茎墨三燮茎塑堂全塑堡垡垡一 0 5 wa d da x i m m l 6a d di m m l 6 t oa x 0 5i da d de a x ，i m m 3 2a d di m m 3 2 i oe a x 8 d ，0i ba d dr m 8 , t r a m 8a d di m m 8 t or i m 8 8 1 ，0i wa d dr i m l 6 i m m l 6a d d m m l 6 t or m 1 6 8 1 oj da d dr i m 3 2 i m m 3 2a d di m m 3 2t or m 3 2 8 3 0 i b a d dr m 1 6 i m m 8 a d ds i g n e x t e n d e dn m 8 t or l m f 6 8 3 o i b a d d