（计算机软件与理论专业论文）注解信息制导的动态二进制翻译器内存优化.pdf

论文独创性声明 本论文是我个人在导师指导下进行的研究工作及取得的研究成果。论文中除 了特别加以标注和致谢的地方外，不包含其他人或其它机构已经发表或撰写过的 研究成果。其他同志对本研究的启发和所做的贡献均已在论文中作了明确的声明 并表示了谢意。 作者签名：缝垫盘 同期： 论文使用授权声明 本人完全了解复旦大学有关保留、使用学位论文的规定，即：学校有权保留 送交论文的复印件，允许论文被查阅和借阅；学校可以公布论文的全部或部分内 容，可以采用影印、缩印或其它复制手段保存论文。保密的论文在解密后遵守此 璇。作者签名：盈醯翮签名：重芏茎赵嗍狸：纽作者签名：垄鑫壑盘导师签名：鬈芏茎理同期：2 丑：亟：! 摘要 关键字：注解信息，动态二进制翻译器，内存优化，寄存器化 动态二进制翻译器能够在运行时将针对源体系结构编译的软件动态翻译成 目标体系结构的软件并使之运行。尽管随着新的体系结构不断涌现，动态二进制 翻译器技术越来越流行，但是动态二进制翻译器往往会受限于在翻译码上可执行 的优化方法，无法使翻译码的执行性能同移植程序的执行性能相媲美。因为源可 执行文件中只有二进制代码，缺乏源程序高级语言的信息，丽且动态二进制翻译 器在翻译过程中需要保证翻译码同源码在二进制级别上的兼容性，因此动态二进 制翻译器往往无法采用一些在静态编译器中常用的代码优化方法。另外，为了保 证在异常发生的情况下能够恢复出一个精确的体系结构状态，翻译码中的指令调 度被限制在个相对较小的范围内，更进一步的限制了动态二进制翻译器的翻译 码优化。本文则从一个创新的角度提出了一种解决上述问题的方法。该方法在静 态编译器中收集那些对动态二进制翻译器优化有帮助的信息，并在可执行文件中 开辟一个独立的注解信息段，将这些优化相关的信息以一定的格式写入其中。在 动态二进制翻译阶段，动态二进制翻译器就可以利用注解信息对翻译码迸一步优 化，提高翻译码的质量。本文在g c c4 0 和i a - 3 2e x e c u t i o nl a y e r 上实现了注解 信息制导的动态二进制翻译框架，并且选择在可执行文件中生成内存优化相关的 注解信息。基于注解信息，本文在动态二进制翻译器队3 2e l 中尝试了包括寄 存器化，放宽m e m o r yo r d 嘶n g 的限制，加强访存指令的地址消岐和放宽精确异 常处理等内存优化。本文选择s p e c 2 0 0 0 为基准测试程序，实验结果表明注解信 息制导的动态二进制翻译器中的内存优化能够在引入相对较小的额外开销下获 得十分不错的性能提升。实验数据显示优化后，s p e c 印2 0 0 0 的整体性能提高了 1 5 0 3 ，而s p e c i n t 2 0 0 0 的整体性能则提高了1 2 1 。对于某些特定的基准测试 程序，性能提升甚至达到了3 7 0 9 。 3 a b s t m e t a b s t r a c t k e y w o r d s ：m e t a d a t a ，d y n a m i cb i n a r yt r a n s l a t o r , m e m o r yo p t i m i z a t i o n ， r e g i s t e r i z a t i o n d y n a m i cb i n a r yt r a n s l a t o ro f f e r ss o l u t i o n sf o rt r a n s l a t i n ga n dr u n n i n gs o u r c e a r c h i t e c t u r eb i n a r i e so nt a r g e ta r c h i t e c t u r ea tr u n t i m e r e g a r d l e s so f i t sg r o w i n g p o p u l a r i t ya sn e w a r c h i t e c t u r e sk e 印e m e r g i n g ，p r a c t i c a id y n a m i cb i n a r yt r a n s l a t o r s u s u a l l ys u f f e rf r o mt h el i m i t e do p t i m i z a t i o n sp e r f o r m e dw h e ng e n e r a t i n gt r a n s l a t e d c o d e t h ep e r f o r m a n c eo f t r a n s l a t e dc o d ei sp o o r l yc o m p a r e dt ot h a to f t h en a t i v e c o d e s i n c et h ee x e c u t a b l ef i l e so n l yc o n t a i np u r eb i n a r i e sa n du s u a l l yl a c kt h eu s e f u l i n f o r m a t i o na v a i l a b l ei nh i 曲l e v e ls o u r c ec o d e ，ad y n a m i cb i n a r yt r a n s l a t o ri sn o t a b l et op e r f o r mt y p i c a lo p t i m i z a t i o n st h a ta r ep o p u l a ri nas m i l ec o m p i l e r i na d d i t i o n , b i n a r yl e v e lc o m p a t i b i l i t yh a st ob ek e p td u r i n gt h ep r o c e s s i n go f b i n a r yt r a n s l a t i o n , w h i c hf u r t h e rp r e v e n t sad y n a m i cb i n a r yt r a n s l a t o rf r o ma g g r e s s i v eo p t i m i z a t i o u s f u r t h e r m o r e ，i no r d e rt oe n s u r eap r e c i c o n t e x tr e c o v e r yw h e ne x c e p t i o nh a p p e n si n t h et r a n s l a t e dc o d e ，i n s t r u c t i o ns c h e d u l i n gh a st ob ec o n s e r v a t i v e l yl i m i t e dt oas m a l l w i n d o wi nad y n a m i cb i n a r yt r a n s l a t o r t oa d d r e s st h e s ei s s u e s ，t h i sp a p e rp r o p o s e s a ni n n o v a t i v em e t h o do f p a s s i n gp e r f o r m a n c ec r i t i c a li n f o r m a t i o nf r o ms t a t i c c o m p i l a t i o nt od y n a m i cb i n a r yt r a n s l a t i o n t h ei n f o r m a t i o ni sc o l l e c t e dd u r i n gs t a t i c c o m p i l a t i o na n ds t o r e du s i n gap r e d e f i n e df o r m a ti nas e p a r a t es e c t i o nc a l l e dm e t a d a t a s e c t i o ni nt h ef i n a le x e c u t a b l ef i l e i nb i n a r yt r a n s l a t i o np h a s e ，ad y n a m i cb i n a r y t r a n s l a t o rc a nu t i l i z et h em e m d a mt op e r f o r ma g g r e s s i v eo p t i m i z a t i o n sa n di m p r o v e t h ep e r f o r m a n c eo f t h et r a n s l a t e dc o d e w eh a v ei m p l e m e n t e dag e n e r a la n d e x t e n s i b l ef r a m e w o r ko f m e t a d a t ad r i v e no p t i m i z a t i o u si ng c c4 0a n di a - 3 2 e x e c u t i o nl a y e r , a n ds e l e c t e dm e t a d a mr e l a t e dt om e m o r yo p t i m i z a t i o na so u rt a r g e t t h em e t a d a t ae n a b l e si a - 3 2e lt op e r f o r mm e m o r yo p t i m i z a t i o n ss u c ha s r e g i s t e r i z a t i o n ，m e m o r yo r d e r i n gr e l a x a t i o n , m e m o r yd i s a m b i g u a t i o ne n h a n c e m e n t a n dp r e c i s ee x c e p t i o ns e m a n t i c sr e l a x a t i o n w cc h o s es p e c 2 0 0 0t ob eo u r b e n c h m a r ka n de x p e r i m e n t ss h o w e dap o s i t i v ep e r f o r m a n c ei m p r o v e m e n tw h i l e i n t r o d u c i n gm o d e s to v e r h e a d t h eo v e r a l lp e r f o r m a n c ei m p r o v e m e n tr e a c h e s1 5 0 3 f o rs p e c f p 2 0 0 0a n d1 2 1 f o rs p e c i n t 2 0 0 0 f o rs o m es p e c i f i cb e n c h m a r k , t h e p e r f o r m a n c ei m p r o v e m e n ti sg ! v e nu p t o3 7 0 9 4 简介 1 筒奔 动态二进制翻译技术是一种即时编译技术 1 1 1 9 ，它将针对源体系结构编译 生成的二进制码( 源二进制码) 动态翻译成可以在目标体系结构上运行的二进制 码( 翻译码) 。动态二进制翻译技术主要被用来保证目标体系结构对源体系结构 的向后兼容。利用动态二进制翻译技术，所有源软件无需移植就可以直接在与源 体系结构不兼容的目标机器上运行。 随着计算机体系结构的不断推陈出新，目前主流的体系结构肯定会被新的体 系结构所替代。因此当前编译生成的软件并不一定能够在将来的主流机器上执 行。即便将来的体系结构兼容目前的主流体系结构，其微体系结构肯定会有较大 的改动和变化。因此，针对目前的微体系结构进行优化编译的软件在将来的体系 结构上的执行性能势必大打折扣。为了能够提高软件的执行性能，需要将软件的 源代码针对目标体系结构重新编译优化并进行调试。但是源代码中往往会有大量 平台相关的特性存在，例如将一个3 2 位的软件编译成6 4 位的软件，源代码中有 效数据的长度变化将会为重新编译和优化带来不少麻烦，因此重新编译和优化源 代码的移植方法将会十分的费时费力。利用动态二进制翻译技术，就可以针对目 标体系结构实现一个源体系结构的模拟器，针对源体系结构编译优化的软件就可 以通过该模拟器直接运行在目标机器上，从而避免了对源代码进行重新编译和优 化的麻烦。 1 1 动态二进制翻译器的基本框架 源二进制程序在动态二进制翻译器上的执行往往分为两个基本阶段：翻译阶 段和执行阶段。在翻译阶段。动态二进制翻译器对源二进制码进行解码之后将其 翻译为目标体系结构上的二进制码，即翻译码。翻译完毕后，动态二进制翻译器 便切换到翻译码中进入执行阶段。当程序在翻译码中运行至尚未翻译的代码片段 时，便会切换回动态二进制翻译器从该点开始继续翻译源二进制码。这样源二进 制程序就可以在目标机上执行。动态二进制翻译器的基本框架如图l - 1 所示。 5 简介 图1 - 1 ：动态二进制翻译器框架 动态二进制翻译器的翻译往往会包含三个阶段：解释执行阶段，普通翻译阶 段，优化翻译阶段。当源二进制码首次执行时，动态二进制翻译器会对其进行解 释执行。解释执行将不会保存任何翻译结果，如果该源二进制码再次被执行时， 它将再次被翻译。为了避免重复翻译带来的开销，当源二进制码的执行次数达到 某一阀值时，便会进入普通翻译阶段。此时，动态二进制翻译器对该源二迸制码 进行翻译，并将生成的翻译码保存在内存中。如此，当程序再次执行到该源二进 制码时，就可以直接执行相对应的翻译码，而无需重新翻译。由于普通翻译阶段 需要翻译的源二进制码往往很多，因此动态二进制翻译器会采用简单快速的翻译 算法，并且在翻译码中加入一些额外的代码来收集该翻译码的动态执行行为信 息，该翻译码被称为普通翻译码。对于那些频繁执行的关键代码块，当其执行次 数超过某一个更高的阀值时，它将被动态二进制翻译器再次翻译，并且进入优化 翻译阶段。在优化翻译阶段，动态二进制翻译器将花费更多的时间，采用更加复 杂的算法对翻译码进行优化翻译，以期得到更高质量的翻译码。优化翻译阶段生 成的翻译码被称为优化翻译码，其执行效率远远高于普通翻译阶段生成的普通翻 译码。 动态二进制翻译器在生成翻译码的时候，会将源二进制码块和翻译码块的对 应关系记录在一张对应表中，该表被称为翻译映射表。翻译映射表中的每一项记 录了一对源二进制码块的首地址和与其相对应的翻译码块的首地址。当程序执行 完一个翻译码块后，会根据当前源二进制码的i p ( i n s t r u c t i o np o i n t e r ) 地址在翻 译映射表中寻找其相应的翻译码。如果命中，那么就可以从翻译映射表中读取后 6 简介 继翻译码的入口地址，直接跳转到该翻译码继续执行。若没有在翻译映射表中找 到对应项，说明该源二进制码尚未被翻译，那么动态二进制翻译器就会从该皿 地址开始翻译源二进制码。在动态二进制翻译器和翻译码间进行上下文切换十分 费时，为了避免每执行完一个翻译码块就要查询翻译映射表，对于直接跳转指令， 动态二进制翻译器可做如下优化。若某一翻译码块a 的后继翻译码块b 已被生 成，动态二进制翻译器便可在翻译指令时将后继翻译码块b 的入口地址回填到 该翻译码块a 末尾的跳转指令的目标地址中，这样，翻译码块a 执行完毕后， 就可通过该跳转指令直接跳转到后继翻译码b ，而无需切换到动态二进制翻译器 的上下文查询翻译映射表。当翻译码被更新，例如从普通翻译码被更新为优化翻 译码，动态二进制翻译器不仅需要更新翻译映射表，还需要对所有该翻译码的前 驱翻译码中的跳转指令的目标地址进行更新。 ， h， l ? j i l l 、 、 图1 - 2 ：热路径的构造 动态二进制翻译器的普通翻译往往是按照源二进制码的基本块为单位进行翻 译的，而优化翻译通常会采取热路径的方式翻译源二进制码【1 h 2 5 。动态二进 制翻译器会在普通翻译码中加入一些额外代码来收集普通翻译码的动态执行行 为信息。例如在普通翻译码中加入计数代码统计该普通翻译码的执行次数，从而 判断该普通翻译码的执行次数是否达到阀值。或者为普通翻译码的条件跳转指令 加入计数代码统计该跳转指令的跳转次数。动态二进制翻译器可以结合普通翻译 码的执行次数和条件跳转指令的跳转次数推测该普通翻译码的后续翻译码，并可 以此为今后构造热路径提供依据。如图1 2 所示，动态二进制翻译器在构造热路 径时可以得到以下信息，翻译码块a 跳转到翻译码块b 的频率为7 0 ，翻译码 块d 跳转到a 的频率为9 0 。根据以上信息，动态二进制翻译器就会将翻译码 7 简介 块a ，b 和d 串联起来，经过代码优化后，构成一个新的翻译码块a ，即热路 径a 。然后更新翻译映射表，将普通翻译码块a ，b ，d 更新为热路径a 。最 后更新所有翻译码块a 的前驱翻译码块的跳转指令，将热路径a 的地址回填到 这些跳转指令的目标地址。这样，今后当程序再次执行到二进制码a 的入口处， 就会直接执行热路径a 了。 1 2 动态二进制翻译器的特点和局限性 动态二进制翻译器在各个领域被广泛运用。动态二迸制翻译器的一大好处是 能够让用户在新的体系结构上直接运行遗留体系结构上的程序。当源体系结构与 目标体系结构相同时，动态二进制翻译器能够被用来动态优化二进制程序【5 】， 或者为二进制程序提供安全的运行环境【1 2 】。动态二进制翻译器还能被用于降低 硬件的复杂度和能耗【1 0 】，提供高性能的代码分析和检测工具 1 7 】。随着基于二 进制代码翻译的应用越来越多，越来越多的程序将会运行在动态二进制翻译器 上，而动态二进制翻译器也将会变得越来越普遍。 但是，动态二进制翻译器常常由于翻译码的性能不佳而受人诟病。在那些对 c p u 要求较高的程序中，相比动态二进制翻译器本身的执行开销，大部分的程 序执行时间都花在了翻译码上，因此翻译码的性能对于整个程序的执行性能尤为 关键。此外，除了提供不同体系结构下程序的兼容性，动态二进制翻译器还需要 发掘目标体系结构的性能潜力。因此研究如何提高翻译码的执行性能成了多年来 动态二进制翻译器的研究重点【l 】【l1 1 9 2 0 】。 尽管如此，和直接在目标体系结构上编译的二进制码相比，动态二进制翻译 器生成的翻译码性能还是不能令人满意。由于动态二进制翻译器的输入是源二进 制码，它缺乏一些高级语言中才有的重要信息。而通常这些信息对于静态编译器 在编译生成二进制码时的优化有很大的帮助。更进一步，动态二进制翻译器也可 以被认为是对源体系结构进行模拟的虚拟机，因此需要动态二进制翻译器在翻译 执行的过程中保证翻译码和源二进制码在二进制级别上的兼容性。这一要求不仅 添加了动态二进制翻译器的翻译限制，而且加剧了翻译码的优化难度。例如二进 制级别的兼容性要求有：1 ) 每一条源指令的语义必须被翻译指令精确模拟，2 ) 在翻译码的执行过程中能够保证源体系结构的精确异常得到正确处理，3 ) 在翻 译码中按照源体系结构的规范维持源二进制码中访存指令的访问顺序等。 鉴于动态二进制翻译器的广泛运用，程序在动态二进制翻译器上运行的机会 将会越来越多。因此，本文认为在针对某一体系结构编译源代码生成二进制码的 时候，不仅需要考虑该二进制码在该体系结构上执行的性能，而且需要考虑该二 进制码今后在动态二进制翻译器上的执行性能【2 6 】。在静态编译源程序的时候加 3 简介 入对动态二进制翻译器的支持将能够帮助二进制码快速适应动态二进制翻译器 的执行环境，并且通过动态二进制翻译器被快速移植到新的体系结构上，同时尽 可能降低程序的性能损失。因此，本文认为将原先独立的两个系统，静态编译器 系统和动态二进制翻译器系统视为一个系统能够从一个崭新的角度来提高源二 进制码在动态二进制翻译器上的执行性能。当然，这也要求在动态二进制翻译器 中加入的注解信息具有通用性和体系结构无关性，即注解信息能够被不同体系结 构的动态二进制翻译器所利用。 另外，本文所提的方法还能够帮助那些希望所开发的软件能够在不同平台， 或者在将来的平台上运行的软件开发者。虽然他们希望看到自己的软件运行在其 他的体系结构上或者新的体系结构上，但是他们往往缺乏足够的人力资源或者其 他资源将软件移植到其它体系结构或平台上，或者他们在等待新的体系结构或平 台趋于成熟。此时，如果动态二进制翻译器能够提供他们可观的性能，那么动态 二进制翻译技术对于他们而言将十分有吸引力。我们相信这些软件开发者将很乐 意接受一个高效的，针对动态二进制翻译器优化的静态编译器。这个静态编译器 能够编译出带有动态二进制翻译器优化相关的注解信息的二进制程序，帮助他们 的软件在动态二进制翻译器上获得额外的性能提升。 同样，我们的方法还能够帮助提高那些遗留软件在动态二进制翻译器上的性 能。尽管该方法需要软件开发者重新编译他们的软件，但是这并不会像软件移植 那样带来额外的代码修改，软件测试和软件验证，更不会对软件的质量带来任何 威胁。而且我们的方法可以被用来仅仅编译那些核心的，性能关键的软件模块， 而无需重新编译所有的源代码，这样可以进一步减少软件重新编译的开销。因此 我们相信注解信息制导的动态二进制翻译器优化能够帮助那些软件开发者和那 些急需在新的体系结构上改善性能的遗留软件，具有相当不错的应用前景。 1 3 注解信息制导的动态二进制翻译器优化简介 本文从一个创新的角度提出了在动态二进制翻译器中进一步优化翻译码的方 法。该方法收集源高级语言在静态编译过程中的有用信息，在最终生成的二进制 文件中加入一个额外的信息段来描述该二进制程序的行为，并将此信息传递给动 态二进制翻译器。图1 3 给出了该方法的框架。我们定义该额外信息为注解信息， 并定义二进制文件中的额外信息段为注解信息段。注解信息由静态编译器生成并 按照预先定义好的格式存储在二进制文件的注解信息段中，动态二进制翻译器中 的注解信息分析器会根据该格式将注解信息提取出来供优化翻译码所用。当含有 注解信息段的二进制文件执行在源体系结构或者没有注解信息分析器的动态二 进制翻译器上时，注解信息段将不会对该二进制程序的正常执行带来任何影响。 9 简介 在图1 3 所示的注解信息制导的动态二进制翻译框架中，可以在静态编译阶段加 入p g o ( p r o f i l eg u i d e do p t i m i z a t i o n ) 执行阶段，通过结合静态编译收集得到的 信息和p g o 执行得到的反馈信息，可以在静态编译阶段生成更加准确的注解信 息。同样在动态二进制翻译器中，可以将注解信息和动态收集到的程序执行行为 信息相结合，从而对翻译码进行更有针对性的优化。注解信息不仅可以用于翻译 码的优化，而且也可以用于降低动态二进制翻译器的翻译优化开销，本文将重点 关注那些能够被用于指导翻译码优化的注解信息。 图1 3 ：注解信息制导动态二进制翻译的基本框架 1 4 注解信息制导的动态二进制翻译器内存优化 本文着重于注解信息制导的动态二进制翻译器内存优化，尤其关注那些能够 被翻译成寄存器访问的访存指令。在静态编译阶段，只要一个变量符合下述条件， 静态编译器就可以在中间语言中将它表示成一个虚拟寄存器( 在g c c 中被称为 伪寄存器) 。该变量不是v o l a t i l e 变量，对其他线程不可见，并且它的地址没有 被其它指令引用。尽管寄存器分配会竭尽所能为每一个虚拟寄存器分配一个物理 寄存器，但有些时候静态编译器迫于有限的物理寄存器数目，还是不得不用内存 空间来表示某些虚拟寄存器。在动态二进制翻译的过程中，如果目标体系结构有 空闲的物理寄存器，这些用来表示虚拟寄存器的内存空间就可以被重新映射回物 理寄存器。我们定义那些用于表示虚拟寄存器的内存空间为可寄存器化内存空间 1 0 简介 ( r e g i s t e r i z a b l em e m o r y ) ，简称r e m 。同时定义那些访问可寄存器化内存空问 的访存指令为r e m 指令。 一个r e m 指令的例子如图1 - 4 所示，图的左面是用c + + 语言写的函数加d l ， 右面是对应于该函数的i a - 3 2 0 二进制码片断。函数f o o o 中有四个局部变量，分 别是i ，j ，k ，埘，变量七和明不是r e m ，因为在函数f o o o 调用函数# n c o 时， 变量k 是以引用的方式作为参数被传递到函数f u n c o 的，其值有可能在函数f u n c o 中被修改。而变量m 则被声明为v o l a t i l e 变量，因此在静态编译的时候，变量埘 是必须被存放在内存堆栈上的。变量i 和，是r e m 变量，由图1 4 所示，与变 量i 相对应的堆栈空间是 e b p - 2 8 1 ，而与变量，相对应的不仅有堆栈空间 e b p 2 町， 还有寄存器p a x 。如果有足够的物理寄存器，那么r e m 变量i ，j 在静态编译优 化时可以被放入到寄存器中，而无需存放在堆栈上。如图1 - 4 右半部分所示，当 r e m 变量，的值被指令m o ve a x , d w o r dp 豫 e b p - 2 q 载入到寄存器e a x 之后， 后续指令对r e m 变量_ ，的访问就可以直接访问e a x ，而无需从堆栈上再次载入。 但是迫于物理寄存器数目有限，r e m 变量无法常驻于寄存器之中。堆栈空间 心细一2 8 1 ， e b p - 2 4 可被认为是r e m ，而访问这两个内存地址的内存指令是r e m 指令。如果有多余的寄存器，动态二进制翻译器可以将这两个r e m 空间映射到 目标体系结构的物理寄存器中，同时将r e m 指令翻译成寄存器访问指令。 一 i i “3 2 自 4 i n tf u n c ( i n t & a ) ： - , q ；二= 二， v o i df o o o ， i n t i j k = 1 ： k 曲p - 1 2 1 | (】 v o l a t i l ei n tm ：ime “d w o r op t r e b p - 1 2 i m n ，- 2 嘲 w h i l e o ) f jw o p - 2 , q () = i = ( | n op n o r d p t r e b p - | ， w o p - 1 6 1 (1 i + + ： i - w v m x , d w o r dp t r 陋呻2 i 】+ j 互。；j ) 暇m ( j c c ) f u n c ( k ) ： f _ 删d w o r dp t r e b p - 2 8 , e a x i + = j ； n l2 j ： r n o vd w o r dp t rl 融耻1 田e 截 ) ) f j c c 图1 _ 4 ：r e m 指令的例子 简介 除了寄存器化，给予r e m 指令的特性，本文也研究了其他诸如放宽m e m o r y o r d e r i n g 的限制，加强访存指令的地址消岐和放宽精确异常处理等内存优化方 法，将在下文中详细阐述。 g c c 是一个被广泛应用的开源静态编译器，i a 3 2e l ( i a 一3 2e x e c u t i o nl a y e r ) 是由i n t e l 。公司开发的在i t a n i u m 固上运行n 3 2 程序的动态二进制翻译器 1 6 】。 我们修改了静态编译器g c c4 0 和动态二进制翻译器i a - 3 2e l ，实现了注解信 息制导动态二进制翻译的框架。我们通过修改g c c4 0 ，使之在编译过程中收集 与优化相关的注解信息，尤其是r e m 指令相关信息，最后将生成的注解信息存 放在二进制文件的注解信息段。我们也修改i a - 3 2e l ，使之能将二进制文件中的 注解信息提取出来并结合到翻译码的优化之中。在利用这些注解信息进行了诸如 r e m 空间寄存器化和针对r e m 指令的其他内存优化之后，i a - 3 2e l 取得了相 当可观的性能提升。我们用s p e c 2 0 0 0v 1 3 作为我们的基准测试程序，注解信息 制导的内存优化能够使其在i a - 3 2e l 上获得不错的性能提升。实验数据表明， i a - 3 2e l 能够通过利用注解信息优化翻译码提高s p e c f p 2 0 0 0 的总体性能达 1 5 0 3 之多，提高s p e c i n t 2 0 0 0 的总体性能1 2 1 。 本文剩余部分将按如下顺序展开。在第二部分，我们将着重描述注解信息的 格式，以及如何在静态编译器中生成注解信息和在动态二进制翻译器中读取注解 信息。第三部分将着重讨论基于注解信息的翻译码优化，详细讨论包括寄存器化， 放宽m e m o r yo r d e r i n g 的限制，加强访存指令的地址消岐和放宽精确异常处理等 基于r e m 指令注解信息的内存优化。在第四部分，我们将展示注解信息制导的 动态二进制翻译优化的试验数据，并分析其优化效果，给予相应的评价。最后我 们将在第五部分讨论相关工作，在第六部分对全文进行总结。 注解信息 2 注鳃信息 2 。1 注解信息格式 注解信息是按照一定的格式保存在二进制文件的注解信息段中的，静态编译 器按照预先定义的注解信息格式将注解信息写入到注解信息段中，动态二进制翻 译器也按照该格式将注解信息从二进制文件中读出。因此，定义一个能够快速读 取，便于扩展的注解信息格式尤为重要。 2 1 1 通用注解信息格式 为了便于管理和对注解信息进行分类，我们以函数为注解信息的基本单位， 并定义其为函数注解信息。每一个函数注解信息中记录着与该函数相关的注解信 息。二进制文件的注解信息段是由若干个函数注解信息组成的，图2 1 给出了一 个函数注解信息的格式。 每个函数注解信息都有一个函数注解信息头，用于描述该函数的一些特性。 除了函数注解信息头，函数注解信息还包括代码区间注解信息，代码区间的范围 可以是函数中某一连续地址的代码段，也可以是整个函数本身。函数注解信息可 以由一个或者多个代码区间注解信息组成。 函数注解信息头描述的是与该函数相关的一些信息和特性，例如函数入口地 址和函数长度能够给出所有在函数内的二进制码的范围。函数注解信息头的大小 是固定的，但是函数注解信息内有多少个代码区间注解信息以及函数注解信息本 身的大小是不定的。为了保证注解信息能够自我描述并且易于动态二进制翻译器 快速定位和读取，在函数注解信息头中加入了两个额外的字段，函数注解信息长 度和代码区间注解信息的个数。前者给出了该函数注解信息的总长度，后者则给 出了在该函数注解信息中有多少个代码区间注解信息。函数注解信息头中还可以 加入其它字段，例如验证字段，可用来标明当前注解信息格式的版本号，如果该 版本号和动态二进制翻译器所预期的版本号不相符合，那么动态二进制翻译器可 以选择不读取该函数注解信息。 代码区间注解信息描述的是函数中某一连续地址区间中的二迸制码的属性。 代码区间注解信息紧接着函数注解信息头按任意顺序排列。代码区间注解信息由 代码区间注解信息头和若干注解信息记录组成。 1 3 注解信息 代码区间注解信息头类似函数信息头，不仅描述了该代码区间的范围，而且 描述了该代码区间注解信息的长度。为了能够有效的减少代码区间注解信息的总 长度，代码区间起始地址和结束地址用它们和函数起始地址的偏移量来表示。根 据函数长度不同，该偏移量字段的大小也可随之改变，我们可以在函数注解信息 头的保留字段中标明代码区间注解信息头中偏移量字段的大小。通常情况下，代 码区间起始地址和结束地址的字段仅需两个字节即可。 注解信息 段 函数注解j 礁裟i，一一一一一 l霪餮窘 霪嚣唇雪一注解记录 卜 萋鲁垡跫 二l 篓1 一一一一一 信息1 注解记录 头 荫数起始地址 函数长度 函数注解信息长度 代码区闻注解信息 数目 保留字段 代码区间起始地址 代码区间结柬地址 代码区间注解信息 长度 注解记录数日 注解记录类型 注解记录长度 注解记录体 另一个注解记录 另一个代码区间 图2 1 ：通用注解信息格式 每一个代码区间注解信息中可以包括若干条注解记录。每条注解记录的长度 并不固定，而且可以用来记录不同种类的注解信息。注解记录中保存的是描述该 1 4 注解信息 代码区间的注解信息。每条注解记录都有注解记录头和注解记录体组成。注解记 录头不仅描述了该注解记录的长度，而且给出了该注解记录的具体类型。每一个 注解记录类型都可以按照各自的格式存储注解信息。 上述通用注解信息格式具有如下特点：1 ) 简洁2 ) 易于读取3 ) 自我描述4 ) 灵活性和扩展性5 ) 平台无关性。 2 1 2r e m 注解记录格式 因为r e m 是按照函数为单位划分的，因此我们选择为每一个函数注解信息 加入一条r e m 注解记录来标示该函数中的r e m 指令。首先，我们寻找出所有 的r e m 指令，并且按照其访问的r e m 地址对它们进行分组。然后为每一组r e m 指令进行编号，称之为r e m 号。此时，每一条r e m 指令都将获得一个r e m 号， 该号可用于标明r e m 指令访问的r e m 地址。 其实，我们通过生成初始r e m 映射表来标示r e m 指令在源二迸制码中的位 置。我们依据该函数的源二进制码的大小生成一个相同大小的初始g e m 映射表 并将其初始化为全零。我们对源二进制码中的每一条r e m 指令，计算其相对于 该函数起始地址的偏移量，并依据该偏移量在初始r e m 映射表中找到对应的字 节，将该r e m 指令的g e m 号写入到该偏移量中。至此，初始g e m 映射表就被 生成了。 最后，我们将初始g e m 映射表进一步压缩后生成r e m 注解记录。我们分别 对初始r e m 映射表中的数据零和g e m 号进行压缩。在r e m 注解信息中，我们 定义每一个字节要么用来表示在初始r e m 映射表中连续数据零的个数，要么用 来表示一个g e m 号。因此，我们定义在r e m 注解信息中，当一个字节的最高 比特位为0 时，该字节的剩余7 位比特将被用于表示连续数据零的数目，而当一 个字节的最高比特位为l 时，该字节的剩余7 位比特则给出了一个r e m 号。由 此，我们可将一个初始g e m 映射表压缩成r e m 注解记录，并最终将该记录保 存在注解信息段中。 因为我们仅用7 位比特来表示g e m 号或者表示连续数据零，因此其最大可 表示范围为1 2 8 。当函数中出现超过1 2 8 个连续数据零时，我们可以用两个或多 个连续最高比特位为0 的字节来表示这些连续数据零。在注解信息中连续n 个 最高位比特为零的字节可以表示n * 1 2 8 个连续数据零。而当函数中出现超过1 2 8 个g e m 号时，我们可以通过扩大注解记录中用来表示r e m 号的数据长度来实 现，例如我们可以将两个连续字节视为整体来表示g e m 号，这样就可以有1 5 位比特的数据来表示r e m 号，从而可以表示多达3 2 7 6 8 个r e m 号，对于一般 1 5 注解信息 的函数而言已经绰绰有余了。对于不同的压缩方法，我们可以在注解记录头中的 注解记录类型中用比特位表明，方便动态二进制翻译器读取。 我们根据图l - 4 中的代码片段生成其相应的r e m 注解记录来进一步描述 r e m 注解记录的生成过程，如图2 2 所示。图中共有三条r e m 指令，为了方 便，我们用指令中访存地址的立即数偏移作为该指令的r e m 号，例如指令a d d d w o r d p 豫膨助0 8 1 ，e a x 的r e m 号是2 8 。指令i n c d w o r d p 豫 e b p - 2 8 1 相对 于该代码区间的首地址偏移量为8 ，因此在初始r e m 映射表中，偏移量为8 的 地方填入该r e m 指令的r e m 号，2 8 。同理，另外两条r e a m 指令的r e m 号分 别被写入到初始r e m 映射表中偏移量为1 5 和3 4 的地方。初始r e m 映射表中 的其余字节均为零。我们将根据该初始r e m 映射表压缩生成r e m 注解记录。 初始r e m 映射表中的起始连续7 个零在r e m 注解记录中被表示为o x 7 。初始 r e m 映射表中的第8 个字节2 8 在r e m 注解记录中被表示成r e m 号0 x 9 c ，因 为r e m 号总数小于1 2 8 ，因此我们在r e m 注解记录中用一个字节来表示r e m 号。最后我们将生成一个7 个字节大小的注解记录来表示图中源二进制码中的 r e m 指令。 图2 2 ：r e m 注解记录格式 1 6 注解信息 2 。2 在静态编译器中生成注解信息 在二进制文件中生成注解信息不仅需要修改编译器，还需要修改汇编器和链 接器。我们选择开源的静态编译器g c c4 0 1 2 2 来进行实验。g c c 和其它流行的 静态编译器一样，有一整套工具来完成整个编译过程。当用户在命令行中执行 g c c 命令时，以下工具c c l ，a s 和埘会分别按序被调用来完成整个编译工作。源 高级语言代码首先会由c c l 编译成汇编码，然后再由汇编器a s 翻译生成可重定 向的目标文件。最终，链接器腽将所有的可重定向目标文件链接起来生成最终 的可执行二进制文件。因此，为了在最终可执行的二进制文件中能够生成注解信 息段，我们不仅需要修改g c c 的编译器c c l ，也需要修改g c c 的汇编器a s 和 链接器搿。 大多数注解信息是在编译阶段收集得到的。编译器首先对高级语言编写的源 程序进行解析，并且以函数为单位通过中间语言生成语法分析树。然后对语法分 析树进行多次遍历，并不断对中间语言进行优化，最终将优化完毕的语法分析树 编译成汇编指令。在这个过程中，高级语言的信息逐渐被丢失，因此，编译器中 的注解信息生成器在此阶段的主要任务是分析并整理出有用的注解信息。以收集 r e m 指令的注解信息为例，首先我们在寄存器分配前找出所有伪寄存器( p s e u d o r e g i s t e r ) 【2 2 】。伪寄存器中存放的是所有未被声明为v o l a t i l e 并且没有被其它任 何指令引用的标量型变量。当g c c 开始进行局部寄存器分配，全局寄存器分配 和寄存器重新分配【2 2 】时，我们记录那些会被暂时写入到堆栈上的伪寄存器，并 且跟踪记录所有访问这些堆栈内存空间的访存指令。在寄存器分配结束之后，我 们还会在其后续优化中跟踪记录我们所收集到的这些访存指令，以察看这些指令 是否被其他优化更新或者删除，继而保证该阶段所收集的注解信息的正确性。最 终，我们将收集到的初始注解信息和汇编指令一起写入到编译器生成的汇编文件 中。 我们修改汇编器使之不仅会将汇编文件中的初始注解信息按照上一节描述 的注解信息格式写入目标文件，而且会为那些可重定向的注解信息生成相应的桩 ( s t u b s ) 。在每个目标文件中，都会生成两个按照标准b f d ( b i n a r y f i l e d e s c r i p t o r ) 2 3 文件格式生成的注解信息段，个是常规的注解信息段，另一个是可重定向 的注解信息段。汇编器会按照注解信息的类型分别将他们写入到常规的注解信息 段或者可重定向的注解信息段。例如类似函数长度之类的注解信息在将汇编指令 进行二进制编码的时候就可确定，因此汇编器会将其写入到常规的注解信息段 中。而像函数入口地址之类的注解信息要到最后链接的时候才能确定，因此汇编 1 7 注解信息 器会在常规的注解信息段中为其保留一个桩，并将该桩写入到可重定向的注解信 息段的数据项中。 最后在链接器中，所有可重定向的目标文件会被链接并生成最终的可执行二 进制文件。因此在链接时，需要计算那些可重定向的注解信息的值，并根据可重 定向的注解信息段中的数据项获得保留桩的地址，将计算值回填入常规注解信息 段中的保留桩。当链接全部完成后，链接器所要做的就是计算最终注解信息段的 大小，并在二进制文件中预留足够的空间，然后合并所有目标文件中的注解信息 段生成一个最终注解信息段，最后将此注解信息段写入到可执行二进制文件中。 2 。3 在动态二进制翻译器中读取注解信息 程序往往会将大多数执行时间花费在很小一段代码上。同时，为了避免动态 二进制翻译器读取注解信息的开销过高，我们提出了一种分步，按需读取注解信 息的方法。我们在动态二进制翻译器中加入了一个注解信息分析器，如图2 - 3 所示。注解信息分析器一方面从源二进制码中读取注解信息，并将这些注解信息 整理后以内部表示的形式存储在动态二进制翻译器的内存中。另一方面，动态二 进制翻译器在翻译的过程中也可以通过注解信息分析器查询感兴趣的注解信息。 图2 3 ：注解信息分析器 在可执行二进制文件被装载时，注解信息分析器会扫描注解信息段，并为每 个函数注解信息建立索引。注解信息分析器会依次读入每个函数注解信息的地 址，以及该函数注解信息的函数注解信息头。函数注解信息头包括函数起始地址， 函数长度，函数注解信息长度等字段。为了加速查询一个指令地址所在的函数， 1 8 注解信息 我们利用a v l 2 4 树来存放索引信息，该树被称为注解信息a v l 树。所有注解 信息a v l 树的节点对应于一个注解信息段中的一个函数注解信息，其内容包含 函数起始地址，函数长度，函数注解信息首地址，注解信息是否被读取等字段。 注解信息a v l 树中节点的关键字是函数起始地址。注解信息索引建立的算法如 图2 - 4 所示。分步读取的方法使注解信息分析器在程序起始阶段只需要读取- d , 段注解信息即可，避免了在