（计算机软件与理论专业论文）java动态优化技术若干关键技术的研究.pdf

攘要 摘要 计算机技术发展迅速，随着硬件速度的提高，软件的设计和实现成为发展 的瓶颈，软件自动化的研究成为热点问题，部分求值技术正是这一领域中提高 软l 孛效攀斡方法之一。都分求俊技零通过进行髓段计算来饯纯程序懿执行效率， 但冕它无法解决代码膨胀的问题 数据铡纯按术将前段诗髯的结桑保存在中闻 数据结构中，从而解决了代码膨胀问题，但怒宦不能优化程序控制流程。 本文将部分求德技术和数据例化技术相结合，使用基予控制流图的例化方 法。遴涟壤爱基于羧铡浚霾戆鼗攥绸稼技术耱铮对程痔基本疑戆部分求镶接零， 在例化阶段对程序旗本块进行例化的同时，究成控制转移的例化，生成滞留程 序，滞留程序既可用于编译时刻例化，又可用于运行时刻例化。这种例化方式 采鼹蓠线王馋方式，应用缀定时阕分辑技术，提高滞留程膨浆效率，阏时避兔 了饲化酚段代码的麓割和拼接，能够有兹简化运行时刻铡纯系统豹实现滩度。 本文介绍了一个基于控制流阑的j a v a 动态构件优化系统，包括在绑定时间 分析熬础上的标注稷序解析、标注控制流图和例化控制流阑系统的设计宓现、 编译辩劐控裁流蚕静蠡动生惑、滋蜜翟痔莰诗秘鑫动生成、漳錾程旁熬字节弱 生成及优化等内容。这个例化系统扩展了基于分段计算的优化方法和应用范围， 同时能够根据一定的j a v a 程序的输入描述和输入值，完成专用环境下的j a v a 程序伐他。 为了对j a v a 裰黟避行字节褥层次匏优纯，本文提窭了j a v a 字节褥虢程语 言，并设计了j a v a 字节码生成系统，用于编译使用j a v a 字节码编程语裔编写 的程序，生成字节粥文件。这样，；o n a j a v a 字节码生成系统后，j a v a 动态构件 饶讫系统裁或为一个完整瓣j a v a 疆客霞纯系绫，可伐镬二j a v a 程序薯垒袋程应 的j a v a 字节码文件。 关键词例化；部分求蝮；数据例他；滞留程序；控制流图；字节码 a b s t r a c t c o m p u t e rt e c h n o l o g y i s d e v e l o p i n gr a p i d l y , a sh a r d w a r es p e e dp r o m o t e s q u i c k l y , t h ed e s i g na n di m p l e m e n to fs o f t w a r eb e c o m et h eb o t t l e n e c k ，a n dr e s e a r c h o fs o f t w a r ea u t o m a t i o ni s h o t s p o t p a r t i a le v a l u a t i o ni s o n ek e yo f p r o m o t i n g s o f t w a r e s e f f i c i e n c y p a r t i a le v a l u a t i o nw o r k sw e t le x c e p tt h a ti ti n d u c e sc o d e e x p l o s i o n ，w h i c hc o u n t e r v a i l st h eb e n e f i t so fo p t i m i z a t i o n ，d a t a s p e c i a l i z a t i o n e n c o d e st h ee a r l yr e s u l t sj nd a t as t r u c t u r e s ，t h u sm e n d st h ee x p l o s i o n p r o b l e m s t h i sp a p e rc o m b i n e sp a r t i a le v a l u a t i o na n dd a t as p e c i a l i z a t i o nt e c h n o l o g y , a n dc o m e sw i t has p e c i a l i z a t i o nt e c h n o l o g yb a s e do nc o n t r o lf l o wg r a p h i t s p e c i a l i z e st h ep r o g r a m sc o n t r o lf l o w sw i t hd a t as p e c i a l i z a t i o na n dt h eb a s eb l o c k s w i t hp a r t i a le v a l u a t i o n ，i tc a l lg e n e r a t et h er e s i d u a lp r o g r a mf o rb o t hc o m p i l e t i m e s p e c i a l i z a t i o na n dr u n t i m es p e c i a l i z a t i o n 。t h ep a t t e r no fo f f - l i n ep a r t i a le v a h a t i o n w i t hb t a ( b i n d i n gt i m ea n a l y s i s ) i sa d o p t e dt oi m p r o v et h ep e r f o r m a n c eo f t h e r e s i d u a lp r o g r a m t h i s p a p e ri m p l e m e n t s ac o n t r o l f l o w - g r a p hb a s e dd y n a m i c s p e c i a l i z a t i o n s y s t e mf o rj a v ap r o g r a m t h ep a p e rf o c u s e so nt h es c a n n e r p a r s e ro fa n n o t a t i o n p r o g r a mw i t hb t ar e s u l t ，c f g ( c o n t r o lf l o wg r a p h ) s y s t e m s ，a u t o g e n e r a t i o no f c o m p i l e w - t i m ec f g a n da u t o g e n e r a t i o no f r e s i d u a lp r o g r a ma n dt h ea u t o g e n e r a t i o n o f j a v ab y t e c o d eo f r e s i d u a lp r o g r a m ，t h i ss p e c i a l i z a t i o ns y s t e m e x p l o r e st h et h e o r y a n dm e t h o do fo p t i m i z a t i o na n de x t e n d si t sa p p l i c a t i o nt oj a v ap r o g r a m w i t ht h e i n p u td e s c r i p t i o na n di n p u tv a l u e so f j a v ap r o g r a m ，t h es y s t e me a r lo p t i m i z et h e n j a v ap r o g r a m 。s ot h i s s p e c i a l i z a t i o ns y s t e m c a i lb eat o o tf o rj a v a p r o g r a m o p t i m i z a t i o ni ns p e c i a lc i r c u m s t a n c e f o rt h eo p t i m i z a t i o no fj a v ap r o g r a mi nb y t e c o d el e v e l ，t h i sp a p e rc r e a t ej a v a b y t e c o d ep r o g r a m m i n gl a n g u a g e ，a n dd e s i g nt h ej a v ab y t e c o d eg e n e r a t i o ns y s t e m ， t h i s s y s t e m i su s e dt o c o m p i l et h ep r o g r a mo fj a v ab y t e c o d ep r o g r a m m i n g l a n g u a g e ，t h e ng e n e r a t et h eb y t e c o d ef i l e a f t e rt h e j a v a b y t e c o d eg e n e r a t i o nh a v e b e e na d d e di nt h ej a v ad y n a m i cs p e c i a l i z a t i o ns y s t e m ，t h i ss y s t e mb e c o m eat o t a l s o l u t i o nf o rj a v ap r o g r a mo p t i m i z a t i o n ，i tc a no p t i m i z et h ej a v ap r o g r a ma n d g e n e r a t et h ec o r r e s p o n d i n g j a v a b y t e c o d e 1 k e yw o r d s ： s p e c i a l i z a t i o n ，p a r t i a le v a l u a t i o n ，d a t as p e c i a l i z a t i o n ， r e s i d u a lp r o g r a m , c f g , b y t e c o d e i i 独锈性声明 本人声明所量变的论文是我个人在导师搬导下进行的研究工作及取褥的研 究成暴。尽我嚣知，狳了文中蒋剃加以标注粒致谢靛逮方矫，论文孛不髓含箕毽 人己缀发表或撰写过的研究成果，也不包含为获得北京工业大学或其它教育机构 的学位或证书丽使熙过的材料。与我一同工馋的同志对本研究所做的任何贡献均 己在论文中作了秘确麓说鬻并表示了瀣意。 母1 1。 签名：望丕墨鏊期：& 醴堑董：z 关于论文使用授投的说明 本人完全了麓l i 衷工、监大攀蠢关保馨、使用学位论文的艇定，即：学校有权 保留送交论文的复印件，允许论文被查阅和倦阋；学校可以公毒论文鞠全部或部 分内容，可以采用影印、缩印或蕻他复制手段保存论文。 然名：望互堕 导师签名：日期：坌兰= = 丝! 。夕 第1 章绪论 1 1 研究背景 第1 章绪论 随蛰计算机技术的快速发展、硬件价格的不断下降、计算机处理速度的提 毫，袋毒l 诗算提鼓零燹凌发展熬簸颈，不孬怒疆静静速度、侩糖霹容量，嚣是 软件的设计、实现和调试。基予这个背景，佟为软件自动化领域的重要技术 一部分求值技术近然年来中飞速发展的一项技术，它被广溅应用于程序优化、 解释、编译或其他彤式的程序生成，甚至可愆予叁动程序生成器的生成。 程序优纯技术一盔是计冀税璐究领瑗戆热门运题，应蕊部分求萤毅术送昔亍 程序优化吸引了许多学校和企业进行研究，比如法国i r i s a 大学的t e m p o 系统能 够对c 语言的程序进行部分求值，提高程序的执行效率；丹麦哥本哈根大学对 嫠分求壤按术遥行了歼剖睦戆磷究，其c m i x 系统逸能够对c 语言避舒傻纯； s o n y 公司的研究人员利用部分求德技术对三维运算进行优化，取得了很好的效 果。 嚣藏，j a v a 谮畜的应用目趋广泛，而将部分求值技术威用于面向对象语言 静疆究还藩予翦澄领域，莺蠹努麓繇究较少。本谦趣是嚣家鑫然辩学基金支持 的研究项目，为了实现面向对象语言的部分求值，本文提出了基于控制流图的 程序优化方案，通过开发一个j a v a 语言的动态部分求值系统来验证所提方案的 正确瞧，帮设计积实现一个基于拣翱滚匿戆j a v a 动态饯羁饯化系统，农绑定时 间分褥的基础上，实现一个倒化系统一一j a v a 动态构件优化系统( 简称 j p e d o ) ，完成对j a v a 程序的优化，提高其执行效率。 邋过介绍j p e d o 系统，本文对基于分段计舞的程序优化理论和方法进行了 深入盼探讨，露醚褥程亭镶纯静壤论窝方法攘广到瑟宓霹象语言，扩大了其酝 究和威用范围，本文还提出了j a v a 字节码编稷语言和字节码生成方案，能够直 接处嬲和优化j a v a 字节码。j p e d o 系统用j a v a 语言实现，具有跨平台特性， 便于缀妒帮进一步的扩震。 本研究课题瀚鞠的不仅是对j a v a 程序进行往纯，通过研究j a v a 动态构件优 化系统，还对基于分段计算的程序优化技术进行了研究和裁试。本文的理论和 技术涉及到部分求馕技术、数据例化技术、j a v a 语言规范、j a v a 虚拟机、编译 技术、软臀工程等镶域。 1 2 研究内容 部分求值是种程序转换投术，萁强的怒裰强部分输入来铡纯个稷彦。 北京工业大学工学硕士学位论文 部分求值技术通过程序变换把一个具有一般计算功能的程序系统变成为一个专 用的程序系统，提高程序的执行效率。尤其是在需要重复多次执行专用系统的 情况下，这种优势会更加明显。 部分求值是一种典型的基于分段计算的程序优化技术，对源程序和静态输 入进行的计算，就是前段计算；滞留程序是后段计算，它接收动态输入并完成 最终的计算。前段计算进行优化的工作，后段计算利用优化的结果完成。 在采用部分求值技术的时候，可以根据程序例化运行的流程，使用两种策 略：在线( o n l i n e ) 例化和离线( o f f i i n e ) 例化。在一个例化策略中，如果对实际值 的计算会响到将要采取的行为，那么这个策略就是在线的，否则就是离线的。 部分求值又称程序例化，它主要着眼于对程序本身的例化。对于面向过程 语言的部分求值技术已经有了比较充分的研究和比较成功的应用。然而，部分 求值技术也有局限性，优化很大程度上依赖于例化生成的滞留程序，随着静态 输入值的增大，滞留程序的长度将会急剧增加，导致代码膨胀。 。 解决代码膨胀问题的方法就是使用数据例化技术。数据例化( d a t a s p e c i a l i z a t i o n ) 是支持分段计算的另一种程序优化技术，它通过适当的分析，选 择一部分中间计算的结果，提供一个数据装载程序( 1 0 a d e r ) 和数据读取程序 ( r e a d e r ) 。数据装载程序用于前段计算，将计算结果保存在缓冲区( c a c h e ) 内： 数据读取程序用于后段计算，直接获取缓冲区内的数据。通过这种方法来获得 性能的提高。 数据例化技术存在一些问题：它不能优化程序的控制流，不适用于以控制 转移计算为主的应用程序；同时，中间计算结果将写入缓冲区，而无法直接编 入目标代码中。要解决这些问题，可在数据例化过程中，使用控制流 虱( c o n t r o l f l o wc , r a 曲，c f g ) 来保存中间结果，控制流图是强制型程序设计语言的一种中间 表示形式，在程序数据流的分析和程序优化中具有重要的作用。 目前世界上对应用部分求值技术优化过程式语言的程序研究较多，而本项 目为了实现面向对象语言的部分求值，提出基于控制流图的程序优化方案，通 过开发一个j a v a 语言的动态部分求值系统来验证所提方案的正确性，即设计和 实现了一个基于控制流图的j a v a 动态构件优化系统，完成对j a v a 程序的优化， 提高其执行效率。 j p e d o 采用离线部分求值和数据例化的方法，读入j a v a 源程序和相应的 静态输入描述，对源程序进行绑定时间分析，经过一系列处理之后，生成滞留 程序，中间结果和过程控制信息。 本课题对j p e d o 系统的研究主要包括以下7 个方面：b t a 绑定时间分析； 标注程序解析；标注控制流图的生成；滞留程序生成；例化程序生成；例化程 序运行环境；滞留程序的运行环境。本人在课题中主要参与了以下研究工作： 第1 章绪论 例化控制流图的设计；优化了j p e d o 系统的滞留程序生成算法，实现滞留程序 的生成系统；提出和实现了j a v a 字节码生成方案，并设计了j a v a 字节码编程 语言，实现了j a v a 字节码生成环境。 1 3 论文结构 本文第2 章详细阐述了部分求值技术的原理和实现方法，包括部分求值分 析、程序通用性和效率的关系问题、基于分段计算的程序优化技术，以及在线 部分求值和离线部分求值、编译部分求值和运行部分求值的比较，并提出了应 用部分求值技术优化面向对象语言的程序。 第3 章介绍j a v a 动态构件优化系统的设计和各部分的功能，首先总体介绍 j a v a 动态构件优化系统的设计，然后分别讲述了b t a ( b i n d i n gt i m e a n a l y s i s ) 绑 定时间分析、标注程序的解析、标注控制流图及其生成、滞留程序及其生成， 以及例化程序及其生成。 第4 章着重介绍滞留程序及其自动生成，首先讲述滞留程序的设计，包括 设计要求和表示结构，然后分别介绍了滞留程序运行分析和滞留程序的自动生 成，最后提出了滞留程序字节码的生成方案。 第5 章介绍了j a v a 字节码编程语言的设计和实现，完善字节码生成方案， 使程序优化能够推进到j a v a 字节码层次。 第6 章对本课题进行了总结和展望，提出了进一步研究的设想。 耗京王煎大学王学硕掌霞论文 2 1 概述 第2 章部分求值技术 部分求值技术是一种从源程序列源程序、熬予程序变换的优化技术，又称 为翟露翻位技术。当耱，诗算秘敦箨对逶熏瞧熬要求较高，还要功9 2 丰富，扩 充性强。然而，通用软件往往需癸适应多种平台和运行环境，因此在程序设计 中必须设嚣很多参数来适应各种情况，降低了程序的执行效率。如果不考虑通 用睦，磷铮对每秽跨凝编写专用稷廖，无形中又趣大了工作黢，还增热了修改 和维护的困难。应翔部分求值技术楚解决这个阉题的有效手蔽，它掇据卷窿中 的一部分常量参数，将通用的源程序进行优化，生成专用程序，从而解决了通 用性和执行效率之问的矛盾。 聱分求篷鼓拳斡麓本愚想是：蕊蔫交换疆j 挚楚理羲入瓣源瑾彦霸一帮分输 入描述( 称为静态输入，s t a t i ci n p u t ) ，生成一个新的中间程序。中间程序偬含 了对静淼输入进行计算的结果，从而简化了源獠序，具有更高的效率，这个中 阕程序被拣为滞留程序( r e s i d u a lp r o g r a m ) ，交换程序称传部分求值器( p a r t i a l e v a l u a t o r ) 。 滞留程序包含了静态输入计算的结果，它怒源程序在特定情况下的特例程 序，所以部分求值的程序变换过程也叫作例化过程。例化的目标就是通过对静 态输入镶麴诗雾生黢渗鹚程旁，黩涔餐 程序中只鼋含镀戆予寒鲡簸入馕 终为 动态输入，d y n a m i ci n p u t ) 的计算。这虽然降低了程序的邋绢性，但提黼了程 序效率。 如隈2 一l 所示，镪分求值过程将程序的执行分两步完成：首先根据静态输 入，i n i ，使褥部努求缓器鹾i x 对源程序p 送行部分索谴，生藏滞留鼗疼p i n l ；在 执行源稷序p 的时候，调用滞留程序p i n l 而不鼹源程序p ，将动态输入i n 2 带 入滞留程序p i n l 中，通过运行滞嚼程序得到输出结果o u t ，其效果与运行源程 序p 矮溺。 4 赫2 章帮分隶毽技术 翻2 - 1 部分隶值过程 f i g u r e2 - ip a r t i a le v a l u a t i o np r o c e s s 瞧可霜公式裁示嚣2 - l 熬遭程，没有逡行部分求篷熬辩侯，添疆溥豹魏行 如下： o u t= 【p 】 i n l ，i n 2 经霆部分求麓器处理瀑程序p ，鼓及执行过程如下： ，p i n l= m i x n i n l j o u t= 【p i n l 】i n 2 这就相当于执行如下过程： 【p 】 i n l ，i n 2 = m i x l p ，i n l 】i n 2 下面具体介绍部分求值技术的相关概念，不同的实现方法，以及威用部分 求谯技术的具体示例。 2 2 部分求值分析 下图是一个寂翔部分求谨渡术豹示翻，左边是源程净p ，右边是凌鞋= 5 豹 ，t - 氰g t ，通过例化得到的滞留糨序p 5 。 北京芏娩大学工学礤士攀谯论文 灞磋窿p n = 5 萋重豹滞磐稷痔p 5 f l o a tf o o ( i n ti l ，f l o a tx )f l o a tf o o5 ( f l o a tx ) i f ( n 一0 ) r e h l l l 2x + ( 0 【 2 ) “2 ) ； r e t u r n t ； - j e l s e i f ( e v e n n ) ) r e t u mf o o ( n 2 ，x ) “2 ； e l s e r e t u mx + f o o ( n 一1 ，x ) ； ， 图2 2 部分求毽汞铡 f i g u r e2 - 2e x a m p l eo f p a r t i a le v a l u a t i o n 上图中函数f o o ( n ，x ) 用来计算x “，该函数膏两个参数，变量x 和它的幂1 1 。 假定在墓些情况下需要计算x 5 很多次，这时，酾数f o o 的参数n 就是确定的， 可良穗深程痔在给宠条静( 萨5 ) 豹情嚣t ，经遥部分求篷嚣豹处理，褥舞滚鼙 程序p 。，p 5 和p 运行缩果相同。滞留程序p 5 和源程序p 相比，因为与1 3 捅关的 计算已缀完成，消除了无关的分支，p 5 结构简浦，具有更高的执行效率。在本 镄中，俊纯匏效暴十分显萋，这楚羧戈程序熬羧澍滚完全睦l1 1 来决定，磐暴在 函数f o o 中只有参数x 已知，而参数r t 未知，鄹么铡亿就浚肖什么效梁了。 当然，例化要付出一定的代价，关键是看这个代价和收获相比哪个激大。 程序例化付出的代价就是需要一宓的例化时间，劳且失去了程序的通用性。如 票一段撩痔以嗣襻静静态输入重复多次运孽亍懿落，裁瘟该对遮驳翟痔遘褥铡位， 因为例化过程仅发生一次，产生滞留程序p 厝，就可以运行p 而不是p 。假 设运行p 的时间为，运行p 的时间为品：每次运行p 节约的时间为一品上 这襻热暴p ，靛运行次数足够多救落，融拓为* 次，那么总共节约的对闻为n x 裔；，。而第一次送行铡纯静融阉为f ，当n 足够大的辩镁，r n r p - 易上 可见，程序例化的本质就是根据输入中已知的部分进行前段计算和优化， 把依赖于已知数据的计算结果保存，修改程序的控制流，生成替代源程序的滞 謦程序。盼既亲这至l 傻纯程疼、攥赢程痔运行效率夔嚣熬e 2 3 襁序通用性和效率的关系问题 应蠲软譬中经常会遇到象蘸露靛袋r 要群靛程序。如聚癸提赢它的效枣， 有两种方法可供选择。一种是写嘏多离效的小稷序( 对n 的每个取值编麓一个 专门函数) ，分别针对这一系列类似问题中的某个问题：另种方法就是只写一 个通用的程序，它怒高度参数化的( 对n 的不阉取值，只有一个函数) 。前者的 效率魄较离，毽是释黟量夫，务个程痔翁维护毙较嚣难，令夕 鄯接1 2 1 懿小枣 改变，就有可能需簧改变所有这魃小程序。眉糟的优点是比较方便，能够适用 6 第2 章部分求值技术 予磐决瑟寿这一个类墅蕊闽憨，援序量不大，瞧楚效率篦较低，它会藏爨缀多 时瓣寒溺试瑟瑟释参鼗，薅掰寒送行实骣计算兹嚣阔帮辐怼较少。 综合考虑这两个医素，可以考虑对这种闽蘧逶行敬下整理：霉一个赢发参数 化，但并不是太高效的程序，它怒遇翊的，可以解决一系列闽题的程序。然后 用部分求值器根据参数配置j c 于熊谶行例化，得到需要的版本。比如前例中求x “ 的问题，可以先写一个通用的禚序p ，经过分析发现经常需要用到计算1 1 在某 个取值时候的函数，这样就可以把1 1 看作是输入参数中的不变量。然臌根据r l 的不同取值，把原来的通用程序例化成一系列专门的小程序，比如p 1 ，p 2 ， p 。p 。这样，在碰到一个具体问题的时候，可以根据n 的不同取假，选择专 门的小程序进行计算，这样就避兔了运行整个通用程序p ，进而提麓舆体问题 鲍辩决效率； 2 4 基于分段计算的糕搿貔纯技术 、 基于分段计算静程序傥纯技术将计算分为两部分，分剥称冀裁羧计簿和器 段计算。分段计算优化的基本恩想燕，通过前段计算完成一部分计算工体，并 生成一个中间程序，中间程序仅包禽其余部分的计算，从而具有更高的毅帮。 部分求值是一种典型的熬予分段计算的程序优化技术，对源程序和静态输 入进行的计算，就是前段计算；滞留程序是后段计算，它接收动态输入弗完成 最终的计算。前段计算进行优化的工作，后段计算是利用优化的结果完成计算。 2 。5 在线部分求值和离线部分求德 在采蘑部分求值技零戆时候，可殴凝摄程序镶纯运行豹浚程，後惩霹糖綮 赔：在线f 0 嚣l i 建。) 翻伲零舞线( 0 攒i 嘲铡曩二。在一令铡笾蓑蝰中，懿浆瓣警器蹙 酾计雾会晌至l 将要掰采取辩行为，粥么这个蒙瓷藏是在线静，誊羯藏怒离线豹e 盎8 图2 3 所示。 7 麓豪王照走学工学壤学镶论文 图2 3 在线郯努求值和嚣线部分求值 f i g u r e2 - 3o n l i n ep a r t i a le v a l u a t i o na n d o t 蕈l i n ep a r t i a le v a l u a t i o n 图2 3 中左图为在线部分求假过程。在线例化处理程序的时候，同时也完 成程序的转换工作。在线部分求德器通过处理源程序和静态输入值，产生滞留 程彦。鬃麓熬部分求壤器罄是使麓在线嫒纯按零，由予在线铡亿孛戆程黪转换 是在有安际值的参与下完成，所戳它是一释较简层次的例亿。 在线部分求值一疹完成，对程序中的每一个表达式的处理都可以根据系统 提供的黪态输入值次邂，可以计箨蹴结果或是产生滞留程序的代码。因为在线 蘸分袋馕器麓够充分麓秘爱静态输入燕，爨纯遴行兹篦较锈藤，其谯赢燕黯交 量和表达式的处理比较精确，但因为静态输入假是在部分求慎器运行时指定的， 部分求值器需要根据这些静态输入值来决定对其它变量和淡达式所采取的动 露，这宓际上类似予拿罄器爨，爨敷在线零分求蓬器鲍弧行效率不毫。 第二种策略是离线铡化，如圈2 3 中右图掰示，例纯静工作分为两步毙成： 预处理和例化。预处理阶段通常进行绑定时间分析( b t a ，b i n d i n gt i m e a n a l y s i s ) ，它根据程序输入变量的动静状态决定程序中其余变量和表达式的动 静获悫，这些动静态信息稳为绑寇霾重阉信惠。程铡恁泠爱，壤据交量霸袭遥式 的绑定时间信息产生相应的动作，根据静态输入值进行计算，保留涉及动态输 入值的计算，最后生成滞留程序。在预处理阶段，由于绑定时间分析仅仅考虑 到了鼷黧浚入部分燕不变量，瑟不霭要静态输入靛兵体僮，艨蚨对表达式瓣处 理存在近似性，在铡纯阶段无法粒不变量所涉及静计算避行彻底例彳乏，魄如一 个条件袭达式有两个分支，如果分支1 和分支2 具有不同的绑定时间，那么这 第2 章部分求值技术 个表达式的b t a 状态就只好综合考虑两个分支的b t a 状态。不过离线部分求 值方法在预处理阶段不用考虑静态变量的具体值，效率较高；而且，它先产生 标注程序，再生成滞留程序，这样就增加了通用性。如果某些静态变量的值在 其它情况下有所改变，可以直接利用已生成的标注程序，而如果使用在线部分 求值，就不得不从接收源程序及静态输入的阶段开始，重新进行例化，这显然 会降低执行效率。 2 6 编译部分求值和运行部分求值 按照部分求值技术的使用时刻，部分求值技术又可以分为编译部分求值和 运行部分求值，下面分别进行介绍。 编译部分求值又称静态部分求值，它是一种比较传统的部分求值方式，根 据编译时刻已知变量的值，在程序运行之前进行例化。这种部分求值技术在很 多领域都非常有用，可应用在编译器生成、科学计算、计算机图形和数据库系 统中。当前关于编译时刻部分求值的研究已经取得了很多成果，并产生了很多 的技术，适用于各种编程语言。 运行部分求值是根据动态不变量进行的例化，也称为运行时刻例化或动态例 化。它是在程序执行时取得不变量的值，对不变量作用范围内的一段程序进行 例化产生滞留程序段。 基于编译时刻例化技术的c 语言的部分求值工作已经被法国的i r i s a 大学完 成。它根据在运行时刻的各个阶段已知的不变量来对程序进行逐渐例化。动态 部分求值的优化方法可以大大提高程序的执行效率，已经广泛应用于操作系统 和图像处理等诸多领域。 进行动态部分求值的过程如下：在编译时间，根据程序员提供的上下文不变 量对程序进行分析，确定对程序中每个语法结构采取什么样的变换。分析结果 被是语法树的形式，在以后的分析中，根据这个结果对可能采取的例化进行 个近似的和安全的估计；这个语法树被用来自动产生代码级的模板，模板中包 含了动态计算，即依赖于变化量的计算；在被标准的编译器编译后，就可以从 编译过的模板获得各种链接信息；最后，程序中依赖于静态计算的部分也被编 译，在运行时刻执行这个程序的时候，它不但要计算不变量，而且要根据控制 流来选择模板，并根据不变量的值来填充模板中的洞。 早期的动态部分求值的实现方法是手工的，通常手工编制代码模板( c o d e t e m p l a t e ) ，模板中预留运行时不变量的孔( h o l e ) ，在系统运行的时刻用取得的 值填孔，并根据控制流组织模板来形成滞留程序。为了提高例化的效率，这些 代码模板都采用二进制的形式。但是手工的方法由于采用二进制形式，不仅实 现效率低，容易引入错误，并且移植性差。法国的i r i s a 大学研制的适用于c 语 耗京工照大学工学硕士攀髓论文 i i 言子集的部分求值器( t e m p o ) 1 1 3 ，不仅可以针对编译不变量遴行编译部分求值， 还可以镑对运雩亍不交爨对程痔骰运行惑魏蘩分求壤。 动淼部分求值和静态部分求值技术有共同之处，它们都是弦编译时刻决定哪 些变量怒动态的，哪贱变量是静态的，然后基于这些信息进行绑定时间分析。 它们鲍最大静医别就楚爨纯器调髑嬲对趣不同，黪态铡化在禊序运行翦谵爝傍l 化器，鞭动态倒纯在糨序运行遗穆中酶各个不瀚淤段谲霜镶纯器。 2 。7 程序铡亿和数据倒化 部分求值又称程序例化，它主臻着眼于对稷序本身的例化。对于面向过程 语言的部分求值技术融经有了比较充分的研究和比较成功的威用。然而，部分 求值技术也专局限性，优亿很大糕度上依赖于侧优生成的滞鼹程序，随饕静态 输入毽鹃臻大，辩整耩序翡长发将会惫穰蓿大，导致代码澎涨。铡翔对稳痔段 中循环进行例化，在滞留程序将展开该循环，当循环次数很大时，代码急剧增 长。例如图2 - 4 中，左边源程序中参数s t a t 是静态输入，d y n 和d 是动态输入， 兹鬟爨豫翟彦震开撵嚣，交豢 逸残势静态元素，歇藤懿方浚( 魏 g l ( i ) ，9 2 ( i ) ，9 3 ( i ) ) 的值可以被求出。即使是g h 是很简单的计算，程序倒化也会对 函数f 进行优化，绪祭循环被展开，一个条件语句被消除，如图2 - 4 中右边的 滞留程黪。循环上5 曼壤大时，就会出现代码膨胀闽题。代码膨胀不仅带来程序 规模随戮，丽且在执行时麴，由予卡码甄摸大蕊导致频繁戆歙趸中薮，将惫剽 地降低执行效率，影响和抵消部分求值的优化作用，甚至从总体上降低程序的 效率。 e x t e r ni n tw i n 】f m 】； e x t e mi n tw i n 】【m 】； f o r ( k = o ；k m a x ；k + + ) f o r ( k = 0 ；k m a x ；k + + ) f ( c ，k ，w k ) ； f _ l 体，w k 】) ； v o i d f _ l ( i n t d y n , i n t d 】) v o i df o n ts t a t , i md y a , i n td 】) i f ( ed y a ) 翻= 1 + d y n ； i n t j ； d o 】扣o * d y n ； f o r ( j = o ；j s t a t j i f ( ed y n ) d 1 】_ 1 + d y n ； d 1 】忙1 0 ) + d y n ； i f i e _ s t a t ) d j 】= g l ) 一d y n ； i f ( ed y e ) a 2 】2 + d y n ； i f ( ed y n ) 卜9 2 ( j ) + d y n ； d 2 】申_ 唆。章d y n ； d u j4 。9 3 ( j ) * d y n ； i g ed y n ) d 3 j = 6 + d y a ； ) d 3 十哪0 + d y n ； ) 鹜2 q 帮分求夔与代弼黪张 f i g u r e 2 - 4p a 删e v a l u a t i o na n dc o d ee x p a n s i o n l o 第2 章部分求值技术 解决代码膨胀问题的方法就是使用数据例化技术。数据例化( d a t a s p e c i a l i z a t i o n ) 是支持分段计算的另一种程序优化技术，在8 0 年代后期由 b a r z d i n s 3 1 年 1b u l y o b k o v 提出，m a l m k j a r 对数据例化进行了进一步的研究，后 来k n o b l o c k 和r u f f 针对c 语言的一个子集研究了数据例化技术并应用于计算 机图形学中。 数据例化试图通过适当的分析，选择一部分中间计算的结果，提供一个数 据装载程序( 1 0 a d e r ) 和数据读取程序( r e a d e r ) 。数据装载程序用于前段计算， 将计算结果保存在缓冲区( c a c h e ) 内；数据读取程序用于后段计算，直接获取 缓冲区内的数据。通过这种方法来获得性能优化。如图2 5 所示。 图2 - 5 数据例化 f i g u r e2 - 5d a t as p e c i a l i z a t i o n 与程序例化相比，数据例化将前段计算的结果保存在数据结构中，而不是 中间程序中。程序的执行分为两个阶段：l o a d e r 执行前段计算，将结果保存在 数据结构c a c h e 中；r e a d e r 读取阶段c a c h e 中的结果数据，完成其余的计算。例 如图2 6 中的程序，左边函数f 在一个循环中被反复调用，每次调用时参数c 的值不变，参数k 和数组d 变化，可以针对静态参数c 进行数据例化，在l o a d e r 中可以进行相应的计算循环条件的测试，e _ s t a t 计算，g h 过程的计算。 在本例中，我们认为循环条件测试，e s t a r 的计算和将中间结果存放到 c a c h e 中的花费并不大，而g h 过程的计算则包含了大量的计算。e s t a t 是静态 的，可以放在c a c h e 当中，由es t a r 的值所决定的对g l 的调用也可以被计算并 存放到c a c h e 中，相应的在r e a d e r 中仅当条件测试为t r u e 的时候，例化程序会 筵豪工渡大孝工学疆掌斑论文 去c a c h e 中查找并取出g l ( i ) 的值；丽g z 处在动态的控制流中，不能被l o a d 。r 中 进行诗葵；9 3 会无条傅旋被调建，接收静态懿参数i ，聚以霹以被诗篓羚穆缝 果存放到c a c h e 中。缩果程序在豳2 - 6 的右边部分所示，龟括l o a d e r 部分和 r e a d e r 部分及相应的c a c h e 数据结构定义。 与裁序伊j 化不同的是，数据例化将倒化结果与滞留程序分开，把例化结果 存藏在中阑数据结稔中，蚕2 - 5 的程痔中豹释态赣久翡计算结条谈存放在 c a c h e 内。 数据例化的优化工作对滞留程序的依赖将大大减弱，随着例化问题的增大， 莰仅是c a c h e 中鲍参数蠼多，瑟漆器程序共不麓之壤太。通道数据量的增大鳃 决了程序代码增大的阔题，也解决了部分求值的代码膨胀闻题。 e x t e r ni n tw i n 】 m ； e x t e mh a tw i n m 】； s t r u c td a t a _ _ c a c h e i n tv a i l ；i n tv a l 3 ； c a c h e m a x ； f o r ( k - o ；k m a x ；k + + )f _ i o a d ( c ，c a c h e ) ； f ( c , k , w k d ；f o r ( k - - - 0 ；k i v i a x ；k + + fr e a d ( e ，k ，w c k j ，c a c h e ) ； v o i df o n ts t a t ，i n td y n ，i n td )v o i du o a d ( i n t s t a r ，s t r u c td a t ac a c h ec a c h e ) i n t j ；i n t j ； f o r ( j = o ；j q t a t ；j + 、f o r ( j = o ；j s t a t ；j + 十、 i f ( e _ s t a t ) i f ( es t a r ) d u 】* 9 1 0 ) 一d y a ；c a c h e i j v a l l ；g l a ) ； i f ( e _ d y n )c a c h e d v a l 3 一9 3 0 ) ； d 鹚= 9 2 ( j ) + d y n ； j d 玉l 十篇9 3 ) 。d y n ； ) v o i df _ r e a d ( h a ts t a t ，i n td y n ，i n td 妇， s t r u e td a t a _ c a c h ec a c h e 1 ) i n t j ； f o r ( j = 0 ；j s t a t ；j + + ) i f ( e _ s t a 0 如 = c a c h e j v a i l a y n ； i f ( e _ d y n ) 】 = s 2 ( ；) + d n ； d j l + = c a c h e j v a l 3 4 d y n ； ) 图2 6 数据捌化示例图 f i g u r e2 - 6e x a m p l e o f d a t a s p e c i a l i z a t i o n 重新考虑图2 - 6 中的例子，假定g h 的计算花费很小，甚燮比相应的对c a c h e 的存取税费还要小，即优化带来的效用将不能补偿优化过私所花费的代价，数 据例他敬饶伍俸用毽将大大约降低。然两，数攒铡纯在裁段计算中无法究戏控 制转移簿计算，不能对控制流遗彳亍优纯，也不邋瘸子戳控制转移诗算为主豹应 1 2 第2 章部分求值技术 用程序。 数据例化的优势在于： ( 1 ) 便于处理大量的计算中间结果： ( 2 ) 避免了运行时刻的代码更新，方法安全可靠； ( 3 ) 可以在编译时刻构造数据装载程序和数据读取程序，避免了动态例化 过程中所需的动态代码生成。