（计算机系统结构专业论文）二进制翻译中的库函数处理和代码cache管理.pdf

摘要 二进制翻译技术是用软件方法解决代码移植问题的重要手段，- - 迸锖, j 翻译及相关优化 技术的研究，在遗产代码移植、硬件设计、程序性能提高、网络应用、系统安全等方面都 有重要的意义，已经成为是现代编译技术研究的热点之一。本文首先综述了二进制翻译的 研究现状和基本原理，然后介绍了本文研究工作的两个实验平台d i g i t a lb r i d g e 系统和 d i g i t a l b r i d g e v e r s i o n 7 系统，接着对二进制翻译这研究领域中的两个问题进行了研究， 最后对论文的研究工作进行总结并展望进一步的工作 围绕如何提高二进制翻译系统的性能问题，本文主要讨论了两方面的工作： 第一部分主要是探讨如何有效地解决二进制翻译中出现的系统库函数调用的问题与 以往对这类问题的处理方法不同的是，本文的方法采用对库函数分类的思想，对两类系统 库函数分别处理。既利用了目标机本地的库函数调用约定，又充分结合了动静结合二进制 翻译的技术特点，具有较好的执行效率 第二部分主要是研究如何高效地管理翻译出来的目标机本地码。通过对常见的代码 c a c h e 管理策略的分析，提出一种多级双粒度的代码c a c h e 管理策略它是对全清空策略、 f i f o 策略、多级c a c h e 等思想的综合，具备它们的优点。同时也回避了它们的缺点通过 实验来确定管理策略中的参数，并且与其他常见的代码c a c h e 管理策略进行对比，证明本 文的方法能够对代码j c a c h e 实现高效的管理 关键词：二进制翻译；库函数处理；可包装库函数；p l t 短路库函数；代码c a c h e ；l r c 管 理策略 l i b r a r yf u n c t i o nd i s p o s i n ga n dc o d ec a c h em a n a g e m e n ti nb i n a r yt r a n s l a t i o n y a n gh a o ( c o m p u t e r a r c h i t e c t u r e ) d i r e c t e db yf e n gx i a o b i n g b i n a r yt r a n s l a t i o ni sa ni m p o r t a n tt e c h n i q u et or e s o l v et h ep r o b l e mo fc o d em i g r a t i o n t h e r e s e a r c ho nb i n a r yt r a n s l a t i o na n dt h er e l a t e do l y d m i z a f i o n , h a v es i g n i f i c a n tm e a n i n g si nm a n y f i e l d s 。s u c h 勰l e g a c yc o d em i g r a t i o n , h a r d w a r ed e s i g n , p r o g r a mp e r f o n n a n c 冶i m p r o v e m e n t ， n e t w o r ka p p l i c a t i o n , a n ds y s t e m 翼a l 嘲y s ot h i sr e s e a r c hb e c o n l 船p o p u l a ri nc o m p i l e rt e c h n i q u e f i e l d 。 t h er e s e a r c hb a c k g r o u n d , t h er e l a t e d 伽帕艘研s ，a n ds o r t i em c a l 够o fb i n a w t r a n s l a l i o nm - e i n t r o d u c e df i r s t t h e nt w ob i n a r yw a n s l a t i o ns y s t e m s , d i 咖lb r i d g ea n dd i g n mb r i d g ev e r s i o n 2 , w h i c h 淝b o t hd e v e l o p e db yu s , a 把i n m x t u c e d f o l l o w e dw eh a v ear e s e a r c ha b o u tt w o p r o b l e m si nt h ef i e l d a tl a s t , c o n c l u d et h e w h o l e p a p e r a n dv i e wt h ef u t u r ew o r k i n 雠f i r s tp a r t , i s s u ea b o u td i s p o s i n gt h el i b r a r yf u n c t i o n sc a l lf a s ta n de f f i c i e n t l yi nt h eb i n a r y t r a n s l a t i o ns y s t e mi sd i s c u s s e & d i f f e r e n tf r o mt h eo t h e rm e t h o d sa b o u tt h ep r o b l e m , o n e a l g o r i t h mw i t hc l a s s i f i e dt l 】i n o d n gi sp r e s e n t e dt od i s p o s et h ep r o b l e m , w h i c hi sb a s e d o nt h e d y l 旧m l ob i n a r yt r a n s l a t o ri n t e g r a t e dw i t h 麟cp r e - t r a n s l a t o t h i sm e t h o dn i 妇u s eo ft h e m e r i to fd ) 咖i ct r a n s l a t i o na n ds t 撕ct r a n s l a t i o n , m dm a k e sl l o ft h ec o n v e n t i o no ft h e f u n o i o nc a l l0 1 1t h et a r g e tp r o c e s s o rt or e d u c et h er e d u n d a n tm e m o r ya c c e 鹤s ot h ep e r f o r m a n c e h a sb e e ni m p r o v e dg r e a t l y i nt h es e c o n dp a r 4 自s s u ea b o u tm a m o n gt h ec o d ec a c h ee f f i c i e n t l yi nt h eb i n a r yr a n s l a f i o n t e d m o l o g yi sd l s a m 嘲lb ya 1 1 a l y z m gt h ef a m i l i a rc o d ec a c h em a n a g e m e n ts c h e m e s , an 唧 m a n a g e m e n ts c h e m ei sp l 镪献i ti n 嘲嘞t h em e r i to f t h ef u l lf l u s hs c h e m e ，f i f o 妇 a n dm u l t i - l e v e lc a c h e , a n dt a k e st h et e m p o r a la n ds p a t i a ll o c a l i t ya n dc o d er e p l a c i n go v e r h e a d i n t oa c c o u n lb yd o i n ge x p e r i m e n t s , e a ) n f l r mt h ep a r a m e t e ri nt h es c h e m ea n dc o m p a r ew i t ht h e o t h e rc o d ec a c h em a n a g e m e n ts c h e m e i tp r o v eo u tt h em e t h o di nt h i st h e s i sh a sg o o d p e r f o r m a n c ea n de f f i c i e n t l ym a n a g e st h ec o d ec a c h e k e y w o r & ：b i n a r yt r a n s l a t i o n ；l i b r a r y f u n c t i o nd i s p o s e ；j a c k e tl i b r a r yf u n c t i o n ； p l t - s h o r t c u tl i b r a r yf u n c t i o n ；c o d ec a c h e ；l r cs c h e m e u i 声明 我声明本论文是我本人在导师指导下进行的研究工作及取得的研究成 果。尽我所知，除了文中特别加以标注和致谢的地方外，本论文中不包含 其他人已经发表或撰写过的研究成果。与我一同工作的同志对本研究所做 的任何贡献均已在论文中作了明确的说明并表示了谢意。 储签名吲勿治 吼枷反多，厂 论文版权使用授权书 本人授权中国科学院计算技术研究所可以保留并向国家有关部门或机 构送交本论文的复印件和电子文档，允许本论文被查阅和借阅，可以将本 论文的全部或部分内容编入有关数据库进行检索，可以采用影印、缩印或 扫描等复制手段保存、汇编本论文。 ( 保密论文在解密后适用本授权书。) 作者签砷悲导师躲夕撕左隰伽以 二进制翻译和动态优化简介 第一章二进制翻译和动态优化简介 1 1 二进制翻译技术的产生背景 当前，不同平台之间的软件移植是一个研究的热点，不仅对软件重用有重大意义，而 且对于开阔处理器研发的思路，促进新处理器创新也有现实的意义现在大多数的商业化 微处理器为了兼容，仍然保留着上一代产品的所有指令，尽管其中有的指令也许已经有几 十年的历史了，并且已经很少使用了虽然大家都明白这些i s a ( i n s t r u c t i o ns e t a r c h i t e c t u r e ) 的缺点很多，但是硬件开发商们仍然不愿意去开发一套全新的i s a ，因为 如果他们这么做，就会冒很大的风险：一方面，基于原来i s a 的软件就不能再使用了，客 户在原来i s a 上的软件投资就会浪费了；另一方面，软件开发商觉得为一个全新的体系结 构写应用软件有一定难度，不仅费时而且开销巨大如果这种体系结构没有赢得足够的市 场份额，那么软件开发商为其开发软件是会面临很大风险的由于这两方面的制绀。限制 了芯片设计的改革，也限制了新的竞争者进入芯片设计领域 把旧的i s a j 标代码在新的i s a 体系结构中执行，可以有以下三种方法可供选择选择： 1 在新处理器上提供一种特殊模式执行代码仿真，如i n t e l 的安腾处理器存在专门执 行x 8 6 代h 的硬件 6 】； 2 重新编译程序，成为新处理器的二进制代码； 3 用软件的方法解释或翻译应用程序； 第一种方法，无法利用新处理器的一些先进特性，并且增加了新机器的硬件复杂度， 甚至还会影响原有代码的执行效率 第二种方法虽然可以达到很好的效率，但由于现存的许多应用程序无法获得源代码， 因而失去一定的可行性；有些程序依赖于共享代码库，而这些共享代码以目标代码形式出 现，可能没有源码；有些源程序语言没有编译到新指令集的编译器；此外操作系统的差异 还可能使得只有修改源代码才能重新编译这些例程 第三种方法，称之为二进制翻译技术( b i n a r yt r a n s l a t i o n ) 应运而生它是一种直 接翻译可执行二进制程序的技术，能够把一种机器上的二进制程序翻译到另外一种机器 上，有助于打破i s 脚其软件基础之问形成的扼制创新的局面，打破c p u 设计改革的瓶颈， 使开发新i s a 机器变得可行，同时也使得一种机器上的二进制程序能够很容易地移植到另 一种机器上，扩大了硬件软件的适用范围。二进制翻译大大减少了硬件厂商和软件厂商 二进制翻译中的库函数处理和代码c a c h e 管理 开发新产品时所面对的巨大的市场风险。i n t e l 公司研制的二进制翻译系统在性能方面较 好，因此在新的安腾处理器上去掉了硬件仿真x 8 6 体系结构的部分，说明二进制翻译确实 可以缓解软硬件之间的矛盾。 从软件开发方面考虑，二进制翻译也很有意义。在软件生命周期中，软件维护费用几 乎占了5 0 9 6 。软件维护工作一般发生在二进制翻译及其应用客户使用软件产品的过程中， 通常分为如下几类：纠错性维护，完善性维护，适应性维护。纠错性维护指排除在用户使 用过程中发现的错误，大概占维护费用的2 5 ；完善性维护包括增加新的功能或改变已有 的功能，使其更符合用户的需求，比如：用户要求增加新的报表，增强统计功能等，大概 占维护费用的5 5 ；适应性维护指系统环境的变更导致系统的修改，如0 s 平台的改变、硬 件平台的改变、数据库平台的改变等，大概占维护费用的2 0 0 5 。二进制翻译技术有助于减 少这2 0 0 5 的适应性维护，它可以使得我们不用花很多时间和编程工作就能把旧平台( 1 e g a c y p l a t f o r m ) 上的软件比较容易得移植到新平台上。 1 2 二进制翻译技术简介 二进制翻译也是一种编译技术，它与传统编译器的差别在于其编译处理对象不同。传 统编译器处理的是某一种高级语言，经过编译处理生成某种机器的目标代码而二进制翻 译处理的是某种机器的二进制代码，该二进制代码是经过传统编译器生成的，经过二进制 翻译处理后生成另一种机器的二进制代码。按照传统编译程序前端、中端和后端的划分， 我们可以把二进制翻译理解为拥有特殊前端的编译器。 像编译器那样，二迸制翻译在概念上可以分为三个阶段 1 3 ，如图1 1 所示 图1 二进制翻译示意图 1 源二进制程序的前端解码器：根据源机器的指令结构特点，通过指令模式匹配对 二进制码进行处理，完成类似反汇编的功能。 2 二进制翻译和动态优化简介 2 转换程序表示的分析器；完成不同中间表示的转换工作，来逐渐去除源机器的影 响，有利于实现到目标机器的转化，并且对程序进行分析，做部分优化 3 后端优化和编码的编码器：类似于一般编译器，从一种中间语言生成优化的目标 机代码。 二进制翻译器的基本步骤主要有从数据文件中区分代码和数据，把源平台上的数据映 射在目标平台上以及翻译指令 2 8 。基于软件的二进审4 翻译根据不同的分类原则可以分成 不同的种类。按照实现方法的不同主要分为三类：解释执行、静态翻译和动态翻译。按照 翻译对象的不同可以分为两类：应用程序级翻译系统和系统级翻译系统，它们分别针对魏 译应用程序和翻译整个操作系统两类应用 1 2 i 按照实现的分类比较 解释执行对程序中的每条指令实时解释执行，执行一条解释一条，系统不保存也不缓 存解释过的指令，不需要用户干涉，也不进行任何优化解释器相对容易开发，不用花多 大力气就可以与老的体系结构高度兼容，但效率很差，通常一条指令被解释为十几条指令 甚至更多【1 3 】 3 4 】但解释执行容易保证程序的正确性，常常被用于辅助翻译。 o 静态翻译是在程序执行之前对其进行翻译，将源机器上的二进制可执行程序文件a 完 全翻译成目标机器上的二进制可执行程序文件b ，然后在目标机上执行程r f b 一次翻译的 结果可以多次使用。静态翻译器离线翻译程序，因而比起动态翻译器来，有足够的时间进 行更完整、更细致的优化，故效率较高而且，静态翻译器还可以利用程序以往执行的记 录进行优化，即基于p r o f i l i n g 的优化，获取更好的优化结果然而，静态翻译器因为无 法得知间接控制转移的目标地址，因此可能无法完整地翻译一个程序。需要依赖解释器的 支持，才能完成全部的翻译解释器要求翻译的程序运行时必须能够支持老机器的全部运 行环境，并且需要支持操作系统调用的翻译和映射，这些都是巨大的开销 动态翻译基于动态编译技术，在程序运行时对执行到的片段进行翻译，即输入的源二 进制文件经动态分析，在运行时被翻译成目标机器码它克服了静态翻译的一些缺点，比 如说静态翻译时由于不能知道控制流中某点的寄存器或内存的值，从而不能得知控制流的 流向。而且动态翻译还可以解决大部分实际情况中的自修改代码问题，而这对于静态翻译 是不可能解决的 1 3 动态翻译可以执行一些静态翻译无法应用的优化，例如 d y n a m i c a l l y - d i s p a t c h e dc a l l s 和过程内嵌。动态翻译器对用户可以做到完全透明，无需 用户干预 4 儿7 e 9 1 5 虽然动态翻译器拥有上述诸多优点，翻译过程却由于受到动态 执行的限制而不能进行更全面细致的优化，使得翻译生成的代码效率比静态翻译器较差 【3 4 】。 3 二进制翻译中的库函觳处理和代码c a c h e 管理 表l 是这三种实现方法的优缺点对比。 表l 三种执行方式的比较 优点 缺点 解释执行 容易开发币薯蛰i l l 户r - 砂岛j 堡撞毒教# 搬笔 静卷翻译 扁线嗣弹u n 毽蛆 了雹好昭健l ，诎奉壤搬解释器坫行环埂的点持，需登 较硒。终制蹦户的警与给崩户使用造，越r 币僵 动态翻译 七嵩孵争f 嚣私远 ，环埯矗= 持z ，嚣j j 户纠i f 的代码绶睾不如静态翱详岛，对 参刺朋动态信息艋掘觉1 ，机会日杯机器白搬蚪的宅删 f 销 基于上面对静态翻译和动态翻译的优劣势的比较，我们有一种新的思路就是把动静翻 译结合起来，综合其优点。优化以静态为主，对翻译出来的本地码进行深度优化，避免动 态优化本身的时间消耗。动态通过翻译执行本地码，把静态不能识别的间接入口点传给静 态帮助其扩大翻译优化的范围。经过动静多遍迭代，最后几乎所有的本地代码都由静态翻 译产生 i 2 2 按照翻译对象分类 应用程序级二进制翻译系统，其功能是能够在目标机上，通过二进制翻译直接运行源 机器的应用程序级二进制代码，是模拟应用程序在操作系统之上的程序行为，如a l p h a 公 司开发的f x1 3 2 系统 1 2 、咿公司开发的a r i e s 系统 1 5 等等。在目标机器硬件系统 之上，直接运行着本地的操作系统，这个操作系统既可以支持目标机本地应用程序的执行， 又可以支持二进制翻译系统的运行源机器应用程序的执行，是通过二进制翻译系统翻译 或解释源机器二进制代码来执行的。当源机器应用程序调用操作系统提供的系统函数，执 行硬件相关的操作时，可以由翻译系统转化为对目标机本地操作系统的函数调用来完成。 如果源机器代码编译时的操作系统与目标机操作系统相同或者类似，这个转换过程比较容 易；若两个操作系统差别很大，就需要为每个源机器系统调用找到目标机系统调用的功能 相似的函数，建立映射关系，这个过程比较困难 1 3 。 系统级二进制翻译系统需要在目标机器平台上模拟整个源机器平台的硬件，不仅包括 模拟源机器平台的指令，而且需要模拟内存管理单元，外设管理等等，因而能够在二进制 翻译系统的支持下启动源机器的整个操作系统，然后在这个操作系统之上再执行所有的源 机器应用程序v i r t u a lp c 4 3 ，v m w a r e 4 4 ，b o c h s 4 5 ，e m b r a 4 6 】，s i m o $ 3 5 都属 于系统级的模拟器，t r a n s m e t a 公司开发的c o d em o r p h i n g 软件 9 3 6 和i b m 开发的b o a 系统 7 8 3 、d a i s y 系统 4 5 4 7 是硬件功能层的系统级翻译。系统级二进制翻译系统 4 二进制翻译和动态优化简介 直接运行在目标机硬件平台上，与硬件系统一起构成一个虚拟的硬件平台，即能够支持不 同于真实硬件指令级的新的指令集，从而使源机器的操作系统和应用程序能够在这个虚拟 的硬件平台上顺利执行。此类二进制翻译系统要支持源机器体系结构下的所有特性，包括 系统级指令在内的整个指令集，所有寄存器、内存、外部端口的读写，尤其是源机器和目 标机器对外部端口定义的差异，会对二进制翻译造成很大困难，医此系统级二进制翻译系 统比应用级二进制翻译系统更加复杂，其运行效率一般也会低于应用程序级翻译，但是可 以解决应用级二进制翻译系统因为底层差异而解决不了的问题，适用性更强 i 3 动态优化技术简介 动态优化技术 1 8 4 0 儿4 8 4 9 5 0 既可以作为一种独立的代码优化技术，又可以作 为二进制翻译所必需的后端优化器，而二进制代码的动态优化技术也需要解码器等模块的 支持，因此动态优化技术与二进制翻译技术具有密切的关系 动态优化技术是在应用程序的运行时刻对程序的信息进行收集和分析，并对程序的关 键段( 热路径) 进行必要的优化，从而提高程序的性能由于在动态时刻对程序进行上述 处理要耗费时闻，所以动态优化必须及时发现程序的关键段，并采用快速而高效的分析、 优化方式，以得到理想的优化效果动态优化系统所用到的熟路径选择技术可以用纯软件 方式实现，也可以由硬件结构提供必要的支持 6 】，这样性能会有显著提高 二进制翻译要兼顾正确性和高效率，在实现不同系列的c p u 问的软件平滑移植目标时， 动态翻译能够保证程序执行的正确性，但其造成运行时的开销需要通过优化生成高质量的 目标机代码来弥补，从而动态优化作为翻译器后端优化器的研究不断涌现；即便是同一个 系列的芯片，由于不同的“代”之间，芯片的具体硬件资源不同，虽然面向旧的芯片的可 执行代码可以直接在新的芯片上执行 6 ，但由于该二进制代码程序不能充分利用新的芯 片的硬件资源，程序的效率不能令人满意，因此也需要动态重优化技术的支持 1 8 】 i 4 二进制翻译及动态优化系统现况综述 二进制翻译和动态优化技术作为当前已经成为研究的一个热点方向，得到了广泛重 视，已经取得了许多研究成果，并相继研制出了很多实验性和商用的系统。 本节首先概述二进制翻译技术的发展历史，并以表格的形式介绍了一些有代表性的二 进制翻译系统，然后列举两个比较典型动态优化系统 i 4 i 二进制翻译技术发展历史概述 国际上，二进制翻译已经得到了广泛的重视和研究早在1 9 8 7 年，h p 公司就开发了最 5 二进制翻译中的库函数处理和代码c a c h e 管理 早的一个商用二进制翻译系统，用来将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 ) 惦，m i p s u n i x ，s 1 ) a r c u n i x 以 及x 8 6 w i n n t 上的代码翻译到他们新开发的a l p h a 机器上，这其中以f x13 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 代码到超长指令字( 、，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 舱t a 公司宣布了t r a n s m e t a 处理器芯片和同态代 码软件，用来在完全不同的硬件基础之上翻译运行x 8 6 代码，甚至包括w i n d o w s 以上提到的翻译器都与机器特性高度相关，重利用是非常困难的1 9 9 4 年a 1 町公司开 发的f l a s h p o r t 一- - 进制翻译器可以运用到多个源、目标平台。但不能完全自动化，需要一 个专业用户通过图形用户界面( g u i ) 进行交互完成。q u e e n l a n d 开发的u q 盯以及u q d b t ， 都是基于对机器指令和操作系统属性描述的可变源、可变目标的二进制翻译器框架，可以 看作是一个翻译器的生成器。 下面的表2 中列出了二进制翻译研究历史中一些有代表性的系统，他们反映了二进制 翻译的研究历史和发展过程，基本涵盖了各个研究阶段的技术成果对这些已有技术和系 统的研究，将会对我们研究二进制翻译技术起到重要的指导意义，有益我们开发出更加高 效实用的二进制翻译技术和系统。 表2 二进制翻译系统简介 名称研究单位 目的 源平台目的平台 b e r g he t a l 【2 6 】 h p 最早的商用二进制翻( h a 3 0 0 0 , n pp r e c i s i o n ( 1 9 8 7 ) 译系统：用于软件模 m p e v l a r c h i - t e c t u m , 拟和目标代码翻译 m p e x l ) m i m i c 5 1 】 l b m 对每条源机器指令代 i b ms y s t e mi b m i r r p c ( 1 9 8 7 ) 码扩展倍数为4 的软 3 7 0 件模拟器 a c c e l e r a t o rt a n d e m 将c i s c 移植到r i s c t n s c i s ct n s r i s c 【2 7 】( 1 9 9 1 ) 的静态翻译器，采用 解释器作为补充 v e s ，r m x d i 西t a l从d i g i t a l 公司的( v a x ，( a l p h a 2 8 2 9 ( 1 9 9 3 )v a x 和m i p s 到6 4o p e n v m s ) ， o p e n v m s ) ， 位a l p h a 静态翻泽 ( m i p s ，( a l p h ao s f 1 ) 器，采用解释器作为 u h f i x ) 6 ，：。，k：0p$、“ 二进制翻译和动态优化简介 补充 f l a s h p r o t 矾飞 跨越多个源和目标平 6 8 x 0 m a c ， p o w e r m a c ， 【1 3 】0 9 9 4 ) 台的二进制翻译，需 i b mi b mr s 6 0 0 0 要人为干预 s y s t e m 3 6 0 ，3s p a r c ，h p ， 7 0 , 3 8 0m i p s ，p e n t i t l n l m a e 1 3 1a p p l e在p o w e r m a e 上开发 6 8 0 x or i s c 0 9 9 4 )的一个m o t o r o l a 6 8 0 0 0 解释器，后来 b a s e du n i x 改进成翻译器。二进 制翻译也被用来在不 同的机器上运行 w i n d o w s 程序。 f r e e p o r td i g i t a l静态翻译器，采用解( s p a r c ， ( a l p h a , o s w l ) e x p r e s s 释器作为补充，翻译 s u n o s4 1 x ) 【1 3 0 9 9 5 ) 用户模式程序，3 2 位、“位都可 ， f x1 3 2 d i g i t a l流行的x 8 6 应用程序 0 c 8 6 , f a 2 p h a , 【1 1 1 2 1 5 2 到a l p h a 的混合模拟 w i n d o w sw i n d o w $ 器和二进制翻译器 n n 0 9 9 6 ) n t i d a i s y 4 【5 】 i b m 利用二进制翻译迁移 ( p o w e r p c ，v l i w p o w e r p c 代码到超长 u n i x v ) ( 1 9 9 6 ) 指令字( v l i w ) 处理 器，增加并行性 a r i e s i s h p 解释和动态翻译相结 h pp r e c i s i o ni a 6 4 ( 1 9 9 9 ) 合，简化了应用程序 a r e h i t e e t t i r e , 从h pp r e c i s i o n a r c h i t e c t u r e , 到 i a 6 4 的翻译； b o a 7 i 【8 】 i b m 动态翻译了p o w e r p c( p o w e r p c ，( p o w e r p c ， ( 2 9 9 9 ) 的整个系统，用简单 u n i x v )u n i x v ) 指令实现原来语义， 简化硬件 u q b t q u e e n s l a n d 大 利用机器指令描述歼可变可变 【1 2 1 3 24 】 学 发的町变源、可变目 ( 2 9 9 9 ) 标的静态二进制翻译 器 7 = 进制翻译中的库函数处理和代码c a c h e 瞥理 u q d b t 5 3 】 q u e e n s l a n d 大利用机器指令描述开 可变可变 ( 2 0 0 0 ) 学发的可变源、可变且 标的动态二进制翻译 器 w a l k a b o u t 3 0 】 s u n 解释和动态翻译相结可变可变 3 1 】( 2 0 0 1 )m i c r o s y s t e m s 合的可变源，可变目 l a b o m t o f i e s 标的翻译器 c o d e t r a n s m e t a用来在完全不同的硬x 8 6v l i w 核心的 m o r p h i n g件基础之上翻译运行 c r u s o e 芯片 s o i t w a r e 公司 x 8 6 代码，甚至包括 9 1 1 3 6 1 ( 2 0 0 0 ) w i n d o w s 。 b i n t r a n s 5 4 】 维也纳科技大利用机器指令描述语可变可变 学言，可变源，可变目 标的系统缴动态二进 制翻译 s t r a t a 5 5 5 6 】弗吉尼亚大 多源多目标的动态翻可变可变 学，微软译器 i a 一3 2i n t e l通过软件方法在i p f i a 3 2 ( x 8 6 )i a 6 4 ( 安腾处理 e x e c u t i o n 上执行i a 3 2 的应用 器系列) l a y e r 1 7 】 程序 q u i c k t r a n s i t 【 t m n s i t i v e 多源多目标的动态翻可变可变 1 6 1 译器 从上表可以看出，这些二进制翻译系统按照源和目标是否可变可分为两类，一类是固 定源和目标的二进制翻译系统，即翻译系统的源机器和目标机器都是确定的；另一类是可 变源和目标的二进制翻译系统，即翻译系统可以为多种源机器和耳标机器服务。对于固定 源和目标的二进制翻译系统，由于其源和目标机器确定，容易对系统进行机器相关的优化， 获得较好的翻译效率。但这类系统不能为新- - 趟t $ 0 翻译系统的开发提供可用的代码，因而 每次开发新系统时，都要花费大量时间从零开始而可变源和目标的二进制翻译系统通过 使用机器描述刻画不同机器的特点，用工具为不同机器自动生成解码器、编码器、以及更 高层的语义抽象单元，并且将部分优化抽象到与机器无关，从而降低二进制翻译系统移植 代价，达到缩短二进制翻译系统开发周期的目标。 氛 1 4 2 动态优化系统 动态优化技术既可以作为一种独立的代码优化技术，又可以作为二迸制翻译所必需的 3 二进制翻译和动态优化简介 后端优化器。动态优化是伴随着计算机系统和应用发展的新趋势而出现的软件和硬件技 术的发展往往呈现出截然不同的方向性，而且技术发展得越快，这种差别越大，导致系统 的性能交付面临着巨大的挑战。比如在高端的服务器市场上，为了尽可能提高性能，处理 器提供了可供编译器发挥更大余地的机制。然而与此同时，软件技术的趋势却给静态编译 优化制造了诸多障碍，目益增多的面向对象语言和动态连接库的使用导致了大量的运行时 绑定，使得传统优化策略很难在编译阶段把握所有的可执行代码，从而达不到理想的优化 效果又比如在p c - $ 场上存在大量遗留代码，重新编译所有的遗留代码显然不现实，因而 微处理器面临应用兼容性问题。另外，i n t e r n e t 应用与移动计算的广泛化也给编译器带来 新的挑战，在网络设备可以动态的下载、连接的环境下，传统的静态优化概念变得模糊起 来，并且传统的编译器制造的胖代码形式也不适合在内存空间有限的网络设备上应用 所有问题都要求一种新的性能提升机制来弥补系统和应用的差距，而原有的不是通过 硬件就是通过编译器来提高性能的观念已经不适应新出现的计算环境 动态优化并不是要取代静态的编译优化，在某种意义上说两者是互补的，它们的作用 域不同，一个是静态的，一个是动态的，动态优化器完成对最频繁执行代码序列的最新修一 正，这使得它可以跨越动态连接调用边界和虚函数调用，而静态编译不能为之另外，它 可以实施针对特定p a t h 的优化，而不会引起多余的代码复制 一 r 需要注意的是，虽然动态优化可以很好地提高动态翻译生成代码的效率，但我们也不 能忽视其自身的开销因而用较低的动态优化开销换取关键路径上的高效代码，是动态优 化系统大幅度提高代码执行效率的关键。 一 1 4 2 - 1 d y n a m o 系统 d y n a m o 是一个动态优化器的原型它的输入是本地二进制可执行代码，通过解释执行 并观察程序的行为而不需要任何注释和采样代码，不需要对代码进行预分析，也不需要为 以后的执行写出信息。解释执行程序时收集的p r o f i l e 信息帮助动态选择h o tt r a c e 。并将 其存放在一个软件c a c h e 中，当以后再度执行到这些t r a c e 的时候就不再解释而直接切换到 软件c a c h e 中执行，从而得到执行效率的大幅度提升 d y n a m o 从解释输入程序的指令开始，输入程序必须是用户模式的可执行程序，可以引 起动态连接和系统调用。解释主要是作为一种不用插桩来考察程序行为的手段通过解释， 1 ) y n a m o 为满足“t r a c e 起点”的程序地址设置计数器并累加计数当某个计数器的值达到 一个事先设好的临界值，解释器进入“代码生成模式，在这种模式下构成t r a c e 的指令被 放进一个缓冲区当到达“t r a c e 终点”时，缓冲内的指令序列被快速的优化处理优化 器( o p t i m i z e r ) 把t r a c e 指令序列做成一个可执行单元，叫做f r a g m e n t ，优化f r a g m e n t ， 并把他交给连接器( 1 i n k e r ) 连接器把f r a g m e n t 代码释放进一个软件c a c h e ，并把它和 9 二进制翻译中的库函数处理和代码c a c h e 警理 c a c h e 内的其他f r a g m e n t 进行连接f r a g m e n t 用指令序列中第一个指令的地址作为标识 ( f r a g m e n t 入口点) 在正常模式下，每当解释器解释到一个成功转移指令时。都要查看c a c h e 中是否存在 以转移目标地址为入口点的f r a g m e n t ，如果命中则控制直接跳至f j c a c h e 中的f r a g m e n t 入 口，f r a g m e n t 代码直接在处理器上执行，此时d y n a m o 被挂起。f r a g m e n t 中的代码逐渐充斥 处理器中的指令c a c h e ，最终用户得到性能的激增。 最后，当转移离开软件c a c h e 的地址空间时，控制重新回至l j d y n a m o 。软件c 8 c h e 中的代 码执行被挂起，出口转移指令的目标地址计数加一，如果计数达到了临界值则o y n a m o 进入 代码生成模式，产生一个新的t r a c e 。 1 屯2 2 j a v a 的j i t - j a v a 编译器将j a v a 源代码编译成平台无关的j a v ab y t e c o d e 格式，然后被分发到各种 平台，f l j j a v a 虚拟机( j ) 实时解释执行。在高性能实现的j 中，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 公司商业虚拟机j d k 、汉城国立大学和i b h 合作开发的开放源码l a t t e w 7 0 7 l 】、i n t e l 的开放源码m r l 7 2 7 3 。 1 5 本文讨论的问题及文章的组织 在二进制翻译系统中，有两类比较重要的问题：库函数处理和翻译出来的本地代码的 管理这两类问题不仅关系到源程序执行的正确性，而且也关系到源程序执行的性能本 文将集中对这两类问题进行探讨和研究。 在第三章中将讨论如何正确有效地处理源程序中出现的系统库函数调用。本文提出的 算法采用一种对库函数分类的思想，很好地利用了动静结合二进制翻译的技术特点和目标 机本地的函数调用约定，减少不必要的内存操作，提高源二进制代码在目标机上的执行效 率并且能够在系统库函数和系统调用之间灵活地切换，对于系统库函数有较强的适用性。 在第四章中将会提出一种软件模拟的代码c a c h e 管理策略，来存储翻译出来的本地代 码这个策略将会平衡时间与空间的矛盾，在尽可能少地占用内存的情况下，对程序性能 产生尽可能小的影响。该策略兼具全清空策略、f i f o 策略和多级c a c h e 的优点，并且考虑 了程序的时间空间局部性、执行特性和替换开销，具有较好的性能。通过与其他策略的对 比，说明其实现了代码c a c h e 的高效管理。 0 二进制翻译和动态优化简介 本史分五章来组织：第一章作为本文的引言部分，主要是对二进制翻译和动态优化系 统进行了综述性的介绍；第二章介绍了作者参与开发的动态= 进制翻译器d i g i t 8 1b r i d g e 和动静结合二进制翻译器d i g i t a lb r i d g ev 2 ，以及与本文讨论的问题相关的模块，这两 个系统也是本文所讨论问题的实验平台第三章介绍了二进制翻译中对系统库函数调用的 处理，提出了基于动静结合二进制翻译系统的一种算法，具有较好的性能。第四章介绍了 如何管理翻译出来的目标机本地代码，提出一种新的软件模拟的代码c a c h e 的管理策略。 第五章对全文进行总结，并提出迸一步的工作展望 攀 二进制翻译中的库函数处理和代码c a c h e 管理 第二章二进制翻译系统框架 x 8 6 系列的机器作为c i s c 体系结构的主流机型，拥有大量的应用软件群作为支持，已 经形成一种垄断的姿态而国产自主知识产权的微处理器由于多种原因，大多采用与x 8 6 不同的指令集体系结构( i n s u u c i o ns e t a r c h i t e c t u r e ，i s a ) 。i s a 的不兼容导致了国产的微 处理器的应用软件相对x 8 6 而言非常匮乏，阻碍了其发展和创新，限制了它的市场应用和 推广。 本文研究内容所基于的课题，主要是面向不同i s a 三l 间的二进制翻译及动态优化技术， 其主要目标是在国产微处理器和x 8 6 问搭建一个数字化桥梁，实现从x 8 6 系列机器到国产处 “理器的代码移植，利用x 8 6 机器原有的大量应用软件，来丰富国产处理器的应用软件，为 国产自主知识产权的微处理器及其市场化提供支持。在实现代码移植的同时，还通过运用 动态优化技术，提高被移植代码的执行效率。 本章将主要介绍作者参与开发的动态二进制翻译器d i g i t a lb r i d g e 和动静结合二进制 翻译器d i g i t a lb r i d g ev e r s i o n 2 的框架结构，以及与本文所讨论问题相关的两个模块 2 1 动态二进制翻译系统d i g i t a lb r i d g e d i g i t a lb r i d g e 系统是一个将解释、动态翻译和动态优化三者有机结合在一起的应用 程序级二进制翻译系统，用于将x 8 6 处理器上的二进制代码翻译成m i p s 处理器上的二进制 代码。该系统初始时通过解释来执行程序，在解释执行的过程中收集程序的p r o f i l e 信息， 并根据这些信息对源二进制代码进行集中的翻译和优化，得到效率较高的本地码。基本框 架如图2 。 1 2 二进制翻译系统框架 图2d i g i t a lb r i d g e 系统总框图 如图2 所示，d i g i t a lb r i d g e 系统主要由盼控制器、文件加载模块、解释器、库函数 调用处理器、动态信息管理器、