（计算机软件与理论专业论文）java程序部分求值描述语言及其应用框架.pdf

摘爱 摘要 部分求值是啼婿呈序优化技术，又称为程序例化技术，是通过程序变换把一个具 有般计算功能的程序系统变成为个专用的程序系统，来达到提高程序执行效率的 目的。尤其是在需要重复多次执行专用系统的青况下，部分求值的优化效果会非常明 显。 部分求值技术是解决程序通用性和专用性之间矛盾的种有效手段。根据程序的 输入，自动判断输入的性质，提取出程序其中经常重复执行、并具有相同结果的部分， 于巴通用程序转换成其各一定程度上的专用程序，从而缓解该矛盾。 对于经过部分求值处理之后的j a 忸程序，尽管在执行效率上得到了改善，并且计 算结果与原始j a 惯程序的计算结果完全一致，但程序之间的接口却发生了显著的改 变。 在部分求值处理过程中，需要向部分求值器传递原始程序的参数动静状态信息， 以便部分求值器判断原始程序中每个变量和表达式的状态，并决定处理这些变量和表 达式的方式。 为了方便部分求值这种软件自动化技术的应用，本文提出了种面向j a v a 语言的 部分求值描述语言，以及应用模型，并实现了相应的应用框架自动生成系统。鉴于j a v a 程序的多样性，j p e s l 描述语言必须能够描述部分求值器处理各种j a v a 应用时所需的 信息，以便部分求值器进行部分求值处理。为此，除了提供描述通用信息的语法规则 之外，j p e s l 描述语言还提供了描述r 加应用和a p p l e t 应用的语法规则。 关键词：部分求值，描述语言，程序自动生成，j p e s l 北京工业大学工学硕士学位论文 a b s t r a c t p 枷a le v a l 咖o ni sa 虹n do ft 。c h l 0 1 0 9 yo fp m g r a m0 p 血n i z a t i o n ，a l s 0c a l l e dp r o g r a m s p e c i a d o n t l 】i si sas y s 协nw 1 1 i c h 昀n s 旬r i t la 寥f l e r a lp r o g m m 幻a 删a lp i - 0 眦c o l r 印v e t h e e 伍c i e n c y o f m e p r | d g m m 酗i a l l y i i l 血es i n l 面o n m 砒n d s 旺e c u t e 吐1 e s p e c i a l p m g 瞄1 1 1r e p e a 蛳m e e 丘k i sw mb e v e 呵r l o 协k f 恤a le 涮嘶o ni sav a 埘m e 吐1 0 dt 0s 0 l v em e 删c tb c h e 咎n 抛i i z a 士i o na n d s p e c i a 蛳o r l w i nj u d 萨t 1 1 ep i d p e r c yo fp r o g 聊mi 印u td a t a 鲫幻n 1 卸j c a l l m a n d 铡m i c f 也e f ，o 而伽w k c h w i l l b c 瓤c c m e d r q 删y i i l p i o 昙i a m ，和d 擘e t 黜r e s 此s o w mg e c ap i o 皇阳m w i m a c 叭a i ne ) ( t 耐o f 驰捌o n t 0a l l e v i 疵m e 1 1 丑i c l 7 i kj a v ap m g 衄：1 1 v e 耐船p a m a le v a l u 撕o n 柏璐向毗l a l i o n o v mr e c e i v eb e c 时e 压c i e l l c y a n ds 硼e e x e c 皿o n 托s u n b u 蛐e j i i 嘧自c e b e 讹憾l p r 曜印m w m c b _ a r l 8 c r e m a r k a b 耻 i n 小ec 咄o f p 枷a le v a h 洳位呱自m l a l i o n ，p 枷a le v a h l 锄0 rw i l lm q 味她抽f o f l t 洳 o f p 矾仰就锶o f 蕊醢诃p i 啪t o j u d g e 也es 【a 钯o f 嘲yv 缸a b k s 谳戗p r 鹤s i o n s 证 o r i 季砌p 删驴1 1 1 锄d d e 嘲丽n e t 】e m o d e t o d e a l 州m t h 髑e v a r i 曲l e s 锄d a ( p r 嚣如m 1 1 1l 量l i st b e 蠡s ，ho i d 盯幻f 配i 】主t a t et h e 印p u c 撕o no f p a a 1e v a h 捌妇l 、e 芦o p o s ef o n a i da p 枷a le v a l u 撕o n 甲。c i 丘c a 如1l a l 】g g e 衙j a v a a n d i 乜印p h c 缸0 n 勋m 跗删：k ，m o r 0 0 v w e h a d i m p l e n l t e dac 0 玳哪0 1 1 d i n g 印p h c 撕o n i 1 1 t e r f a c ea t 】妇m 血萨明碰o ns y 吐c m f o rm e 廿1 r e ea p p k 撕o nf 0 玎1 1 si 1 1j a v a0 0 c a lp m g m ，l n _ r 锄l ei n v 0 c 撕0 np r o g m a n d a p p 蛾 p r o g 唧均，p a m a l e v a l 删o ns p 。c i 撕0 nl 柚孵删d e ss e 睢c o n l a i l l e dj i l 向m 撕o n 南r 吐l e a p p h c 鲥o nm 魄白c e 删细m 撕c 群n 蒯o ns y s 咖w 色a l s 0d i s c u 鼹l l c 印p 撕吼m o d e l s u s e d b y 印p h c 撕0 n i n t e r f 犯e i i l 廿1 i s p 印既 i ( e y w o r d sp a 撕a lc 、，a 1 咖a 玛即e c i ! 丘c 撕o nl a l l 睁【a 炉，p m 翘哺m a u 协m 撕c g 蝴钟蕊o r k 择琶s l 第一章绪论 郝分求值概述 第一章绪论 部分求疆是一哥 疆澎绽纯技术，又稼麓程痔镪化，是遴遥程| 事受抉把个其有一 般计算功能的程序系统变成为专用程序系统，来达到提高程序执行效率的目的。尤其 是在需簧重复多次魏行专鞠系统静情嚣下，帮乡 隶餐盼浅纯效采# 常锈显。 通用程序往往为了保证在各种可能的输入条件下部能正常运行，$ 琶供了许移通用 弋玛。毽慰予那塑经零反笈发生鑫冬输入条箨，通蒡；疆黼没有褪供其裔镑对注豹代码， 而使用通用代码统一对待。在这种情况下，程序眭能必定不理想。如果不考虑粳序的 逶援性，专f 1 为经常发生豹稔入条 譬镐写专瘸程窿，那么不仅会黼e 工作受趱，丽置 还会使程穿的应用范围变得非常狭窄。 部分求篷按) l 之是解决糕声逶躅经鞠专鬻健之阕矛藩豹耪蠢效手羧。宅缀攒疆净 的输入，自动判断输入的性质，提取出程序其中经常熏复执行、并具有相同结聚的部 分，把遴瘸程序转换 一定黻上凝各专震靛熬程澎，钛瑟缓解该矛瓣。 在本学位论文中，主要介绍部分求值技术在j a 忸程宁优化方面的成用和实践。在 这里，聱分求篷耪摇_ | 莘铡纯其有程潮豹含义。 在部分求值过程中，将首先判断输 参数的性质，判断出哪些参数为静态参数， 缓些为动态参数，并攫据这些癌惠标记程露，然蓐搽攘标记蕊惑产生壤应静渗辩程亭 和例化程序。在部分求值醴程中，能够确定其具体值的表达式或者变量，称为静态变 爨；反之，就是动态交量。然后，涝整程痔怒剩下款羧入参数箨为叁己输入，接行 滞留程序后，即。目r 产生最终结果。 1 2 部分求值基本原理 部分求值技术本身是一种程j 袱化技术，能够改蒋程序代隅的执 j ：效率；同时， j a 垤本身囊子蓑颞跨乎台姆建，因救j a v a 在狸序执行效率上存袭先天疑陵。这耱现实 北京工业大学工学硕士学位论文 状况促成了部分求值技术在j a v a 领域的应用。 本项目的主要目的是为了实现一个j a v a 软件工具，提供了程序动态部分求值功能。 纽童动态部分求值之后的；a 忱程序，能够根据当前的运行环境实时优化自身结构，从 而实现程序逻辑上的优化，同时提高运行效率。 下面给出了一个简单的范例来解释一些基本的部分求值原理。 在该范例中，原始程序如图1 1 所示，有一个函数勋z ) 来计算x 的n 次方。在某 些特定的青况下，我们需要多次计算x 的5 次方，这样，我们能够确定两个输 参数 中的个，即参数n 。根据这个已经确定的参数n ，把原始代码修改为图1 2 所示的程 亭代码。 图1 1 原始程序代码 f i g u r e1 - lq i 醇氇l p h 礤n c o d e 图1 - 2 当n 等于5 时，进行的例化处理 f i 昏聪1 2i f ne c f 脚s5 爿，e c i a i j 绉6 0 n 缸娟加蛐五饼1 当输 参数n 等于5 的情况下，将原始代码进行部分求值处理，得到个滞留程 序，即图1 - 2 所示代码。与原始代码相比，与n 相关的计算已经提前完成，消除了无 ，廷哆 支，所以图1 之所示代码结构非常简洁，因此具备较高的运行效率，而且运行结 果同原始代码完全相同。 显然，经过部分求值处理的代码在结构上得到了更具针对性的优化。当n = 5 的输 入条件下，我们可以不必使用通用的原始代码，而是直接使用经过专门优化的代码来 进行剩余的计算。 鹅一章绪论 注意：在这个例子中，因为程序的控制流程更多的是由参数n 决定，因此如果能 够事先确定参数n 的输入，即n 为静态参数，那么经过部分求值处理后的优化效剽辱 会十分明显。相反，参数x 对程序流程的影响并不大，因此在x 为静态参数的隋况下， 部分求值的优化效果就不是十分理想。 1 3 部分求值的分类 1 3 1 在线例化和离线例化 根据程申例化的流程，可以把部分求值技术分为两类：在线例化和离线例化。 在线例化方法是在处理程序的同时，也完成了程序的转换，这种部分求值方法将 会根据原始程箭日静态数据生成滞留程序。但是在线例化要求输入静态数据，即输入 具体的参数值。在线例化的基本流程请参阅图1 3 。 图1 - 3 在线例化流程 f i 毋e l - 3 0 咄m 印e d 出蜘帆n o w 离线例化方法包含两个阶段：预处理阶段和例化阶段。在预处理阶段，将原始程 序和输入数据作为预处理器的输入，预处理器将会输出对应的标注程序。标注程序中 给出了程序中变量和各种表达式绑定时间的静态和动态划分信息。在例化阶段，将静 态数据作为部分求值器的输入，根据预处理阶段生成的标注程序，生成滞留程序。离 线侈4 化方法的基本流程请参阅图1 _ 4 。 北京工业大学工学硕士学位论史 f 漏聍jf 输入数据 l 兰f 1 l 预处理器l i l 标注程序静态输 数据 l l 、，。，。 i 部一1 1 | 滞留程序i 、- ，j 图l _ 4 离线例化流程 f i g 哼1 4 0 m 妇s p 舒吐z 嘶b a w 从图1 3 可以看出，在线例化只需一步，而目程序中每个表达式部可以根据静态 数据确定自己的输出，即计算出实际数据还是产生滞留程序代码。这种方法的优点是 对变量和表达式的处理比较精确，能够充分利用静态数据。但由于静态数据是在进行 部分求值处理的时候输入的，是预先确定的，而不是运行时刻实时输入的数据，因此 数据比铰局限，因此在线例化的效率并不理想。 在离线例化中，预处理阶段通常包含一个约束时间分析( 也称绑定时间分析或 瑚噙) 过程。在约束时间分析过程中，将会根据程宇输入参数的动静状态来决定程序 内部代码中其余变量和表达式的动静状态。在例化阶段，将会根据代码中变量和表达 式的动静状态，进行不同的处理，即计算出静态数据的具体结果，或保留动态部分的 计算，并生成滞留程序。由于这种方法在预处理阶段不必考虑静态数据，因此效率相 坤陵高。而且，由于该崩去首先生蒯戚拚呈序，然后再生j $ 错留程序，因此通用性较 高。 第一章绪论 1 _ 3 2 编译部分求值和运行部分求值 由于部分求值是根据输入数据中的不变量来别化程申，而不变又是相对的，也就 是说，有些变量的值在编译时刻就已经知道，而有些变量的值只有在运行时亥恻一能知 道。根据确定不变量的时间，把部分求值应用分为编译部分求值和运行部分求值。 编译部分求值又叫静态部分求值，是一种比较传统的部分求值方法。该方法在编 译时刻使用能够确定的变量值来例化程序，该过程位于程j 韵重行之前。这种部分求值 技术已弪应用于很多领域，例如编译器生成、科学计算、计算机图形和数据库系统等。 现在关于编译时刻部分求值的研究已经产生了很多的原理和技术，并目适用于各种编 程语言。现在的研究主题包括：高层次语言的终结分析，强制性语言结构的部分求值 和快速绑定时间分析。 运行部分求值是在程序j 蚕行时刻，根据动态不变量进行程序例化，这种例化叫做 运行时刻例化，也叫动态例化。它是在程序执行时取得变量的值，对不变量影响的一 段程序进行例化产生滞留程序段。对于c 语言，这个工作已经完成了，它基于编译时 刻例化技术的基础。运行时亥捌化并不象通常那样被分为两个阶段，因为它是根据在 运行日j 刻的各个阶段确定的不变量值来逐渐例化程序的。动态部分求值的优化方法可 以大：埒黾高程序的执行效率。目前，动态部分求值已经广泛应用于操作系统和图像处 理等诸多 g 轷1 田l 田】。 1 4 国内外的研究现状 部分求值技术目前在国际上主要有两个系统，都是c 语言的部分求值系统，而我 们的项目则是对部分求值技术进行创新和改进，应用在了目前非常流行的、具有效率 挖掘潜力的j a v a 语言上。 1 4 1c m 奴 c - m 奴是哥本哈根大学t o p p s 研究组开发的个c 语言部分求值系统，能够完 成c 程序的静态部分求值。系统采用基于控制流图的绑定时间分析技术，通过生成应 北京工业大学t 学硕士学位论文 垌程序的生成扩展器，来完成c 程序的部分求值。生成扩展器的运行将接收输入数据， 訇螺努态计算，进行循环展开、常数代八和函数例化等程序优化，生成c 程序的滞 留程序。c m i 】( 在科学计算，图形学，操作系统等领域已经有了有效的应用。但是， c m i ) ( 不能直接生成滞留程序的目标代码， 序例化，不可避免的存在代码膨胀的问题， 1 4 2 娜 不支持运行时刻部分求值的功能。作为程 会响程序的执行效率。 ，r 咖p 0 是法国u s a 大学c 0 m p 0 研究组开发的个c 语言部分求值系统，支 持c 程序的编译时刻部分求值和运行时刻部分求值。系统采用基于模板的动态代码生 成技术；在编译阶段，根据绑定时间分析等程申分析技术的结果，生成目标代码模板， 以模扳参数的形式支持静态计算结果的保存：并且产生生成扩展器。在程序例化阶段， 7 成扩展器 卖取静态输 ，完成静态计算，将计算结果填入目标代码模扳；并且，通 过模板的复制和拼接，完成滞留程序的生成。t e m p 0 也有一定程度的应用，t 目1 1 p 0 对 s 吼的r p c 协议进行改造优化，总体性能提高了1 5 倍，而优化舌的进程调度程序的 效率，提高至原来的3 7 5 倍。在t e 彻p o 中，滞留程序目标代码的直接生成使得应用 程序能够在运行时刻得到高性能的目标程序，但也可能防碍了某些传统的代码优化技 术的使用。另一方面，滞留程序的代码长蚵能远远超过源程序代码的长度。 在本项目中，基于控制流图的离线数据伊i 化技术采用了根据控制流图进行程序分 析和程序变换的技术。在一定程度上，可以利用c 郴x 前端的程序分析，以及生成扩 腱器的构造方法。不同之处在于g m i x 系统构造的生成扩展器将用于构造滞留程序， 而我们的离线数据例化系统将产生控制流图的生成器。生成的控制流图数据能够用于 编译时刻例化，也可以直接用于运行时亥唰化。同时，系统也完全避免了程序的代码 膨胀。和1 b m 的动态代码生成技术相比，基于控制流图的数据例化通过生成搭剐流 图数据的方法代替了代码模板的复锟印拼接，控制流图生成器的复存牲明显地低于程 序生成扩展器，从而简化了编译生成器的实现难度：同时，完全避免了滞留程序的代 码膨胀。同c m i ) ( 和晰为代表的程序例化技术相比，基于控制流图的数据例化具 自- 无代码膨胀，实现简单的优点；然而，这些优势的取得是以牺牲常数代入等程f 争优 化机会为代价的。它能够完成控制转移的优化，但控制流图的使用仍有一定的解释负 第一章绪论 担；它采用了在运行时刻传递基本块参数的方法，其执行效率将明显地低于程序例化 实现的常数代入。因此，从原理上讲，这种技术更适合于处理规模较大的应用程序， 更易于在运行时亥螂分求值中发挥其优势。 北京工业大学 学硕上学位论文 2 1 简介 第二章系统概述 本系统是个应用于j a ：v a 语言的部分求值系统，致力于使用部分求值技术对j a v a 程序进行变化，以达蛩 p 0 化系统陛能的目的。通过读入j a v a 原始程序，并结合静态数 据，经过部分求值器的处理，生成滞留程序、中间结果和程序控制信息，而这里的滞 留程序就是经过优化后的程序。 由于采用了离线部分求值方法和数据例化方法，因此系统把对静态数据的描述和 静态数据的实际值分成了两个部分，分别在不同的处理阶段使用。 本课题试图使用控制流图形式保存前段计算结果和程序控制信息，并把这些售息 收荏缓存中；而后段计算将根据缓存中保存的控书慌图信息引用前段计算的结果。 与传统的数据例化方法不同，这种方法能够完成程序控制转移的优化。该方洲吏 用基于控制流图的数据例化技术，并利用离线程| 芋例化和绑定时间分析技术，来构造 控制流图生崩器；并且直接生成滞留程痔。 基于控制流图的程序例化避免在例化阶段直接修改程序代码，刚氐了部分求值系 统的复杂陛。这些优点有利于实现尚陛能的运行时刻咧化系统。 2 2 1 部分求值 也被称作程序例化，主要着眼于对程序本身的例化。部分求值根据原始程序输入 中一部分静忽鼬冒产蛔带留程i 芋，而滞留程亭中包含了静翻扩瑚关的前段计算结果。 但部分求值技术存在一定的局限性，即很大程度匕，优化效果依赖于例化生成的滞留 程亭，随着静态数据的增加，滞留程序的长度急剧加大，将会导致代码膨胀。 第二章系统概述 例如，对程序中的循环进行部分求值，滞留程序将会展开循环。当循环次数过大 的时候，必然会导致滞留程序的代码急剧膨胀。代码膨胀不仅会带来程咩规模问题， 在栩芋运行时刻，由于代码规模过大而导致频繁的缺页中断，反而会急剧阿氐执行效 率，影响和抵消部分求值的优化作用，甚至会产生相反的结果。 2 2 - 2 数据例化 是支持分段计算的另种程序优化技术，在8 0 年代后期由b a i z d 妇和b u l y o b k o v 提出来。数据例化试图通过适当的分析，选择计算的部分中间结果。提供个数据装 载程序( 1 0 a d e r ) 和数据读取程序( r e a d 盯) ；前者用于前段计算，将计算结果放在缓冲 区中；而后者用于后段计算，直接从缓冲区获取前段计算结果，从而达到优化眭能的 目的。 与程序例化相比，数据例化将中间计算结果保存在数据结构中，而不是中间程序 中。程序的执行被分为两段：1 ) l o a d e r ：执行前段计算，并将计算结果保存在缓存( c a c h e ) 中；2 ) r e a d 盯：读取缓存中的中间计算结果，继续后段计算，完成其余的计算i 嘶呈。 与程序例化最根本的区别，在于数据例化将例化结果和例化程序区分开，将中间 计算结果蔚注中间数据中，而不是保有在滞留程序代码中。所以；攻据例化对滞留程序 的依赖大大削弱。随着例化规模的扩大，随之扩大的只有保存在缓存中的中间计算结 果，滞留程序的规模并不随之发生变化。换句话说，数据例化是通过数据量的增加来 缓解程荆弋码膨胀的问题。 2 2 _ 3 数据例化和程序例化的结合 数据例化的优势在于： i 便于处理以计算为中心的程序； i 避免了运行时刻的代码更新，安全性更高； i i i 可在编译时刻构造数据装载程序( 1 0 l a d 盯) 和数据读取程序( r e a d e r ) ，避免动 态例化带来的动态代码生成问题； 数据例化的主要弱点在于： i 无法优化程序的控制流，不适用于以控制转移为主的程序； 北京工业大学t 学硕士学位论文 i 将中间计算结果写入缓冲，而无法直接嵌 到目标代码中： 当原始程序的计算量并不大，甚至小于对缓存的访问时间，也就是说数据例化的 优化作用已经被增加的额外处理抵消掉了，数据例化处理并没有改善程申| 生能，反而 蝌氐了程序性能。 而且，数据例化的前段计算过程中，无法对控制转移进行提前计算，换句话说， 就是无法对程序的控制流进行优化，对于那些以控制转移为主的程序来说，数据例化 并不能起到优化的作用。 如e 所述，程序例化和数据例化都具有自己区别于对方的优势和缺点，适用于不 同的黼领域。选择程序例化还是数据例化，关键在于例化问题的规模和前段计算 代价之间的平衡。 在同“程序当中，可能某些程序段应该使用数据例化，而另一! 螺序段应该使用 程亭例化。比如个简单的例子，在个双重循环中，内层循环的执行次数不多，适 合进行程f 宁例化：相反，外层循环的最大循环次数很大，这样就不适合使用程序例化， 面应该使用数据例化方法。只有在合适的情况下使用合适的例化方法，才能得到最大 限度的优化效果，因此程序例化和数据例化不应该孤立起来，应该相互结合，扬长避 短，把两种例化方法的优势充分发挥出来，同时尽可能避免每种方法可能带来的缺点 和问题。只有这样，才能使例化方法的优化效果更显著。 2 2 4 控制流图： 控制流图是强制性语言的种中间表示形式，对程序数据流的分析和程f 芋优化有 着非常重要的作用。 控制流图是拥有一个根节点的有向图，节点可以为下述几种类型： i 语句节点( 赋值、输入输出语句等) ：控制流图中的该类型节点具有个前趋 节点和一个后继节点； i 谓词节点：控制流图中的该类型节点具有一个前趋节点和两个后继节点。两 个后继节点当中，个是真后继节点，个是假后继节点。 i i i 特殊节点：即入口节点和出口节点。入口节点是控制流图的根节点，并以出 口节点为假后继节点，以程序的第个语句所在节点为真后继节点；出口节 点没有后继节点。从入口节点可以至i j j 态其它任何节点，从任何节点都可以到 达出口节点。 第一章系统概述 至于控制流图的边，要么具有t m 柞a l s e 标记，要么没有任何标记。以谓词节点 为出发节点的边具有t n e ，f a l s e 标记，而以其它类型节点为出发节点的边没有任何标 记。 控带蜿图中的每个节点标志了一个状态。 在本课题的例化系统中，控制流图中存放着前段计算结果和程序控制信息，相当 于数据例化中的缓存。不仅如此，数据例化的缓存中只包含了数据信息，而控制流图 中还包含了部分程序控制信息培。 2 3 系统总体结构 参阅本课题的系统总结构图，即图2 1 。 北京工业大学工学硕士学位论立 输入抒区描述 i n p mp ar c j t i o n 标注控制流图 自动生成 j a v a & 十( w a ) ib 1 r a 分析 c 盏裟舔，卜1 氟 ( 陆曲gt 聊ea n a i y s 塔) 广7 拓拄程序h n n ) 标注语法拷结掏 f n o d e & t r 钾) h l 标注控制流圈 及其自动生成 标注控制流图蛐c 龟 ( 1 1 i l o 吼e dc f g l 7 1 v 妻磬霎岩磬广f 一 舶她成陬i ：赢 擞甚h 例化程序1j 厮 例化程序i j 运行环境j l 。_ j 铡化运行环境 蜊化控制激田 s p e c c f g ( s p b 舡e dc f g l 标注程序解析 ( p a r s e “s c a n n 盯1 i i 标注程序解析 i v 滞留程序及 其自动生成 动杏输 值 & “ki n d u i f 噬到 i 、巡i 滞留运行环境段结果 程序最终结果o u t、 图2 1 系统总结构图 f 酒姑2 - ls y s 魄i l m 妇南m w o r k d 】a r t 篓黧紫麓翌鬻跫黔输入的描述，根据静态输入的描述，谢谳 塞黧缝，生成j a 标注程序，标注程序决定了对丽馘；赫花蒜苗? 程度和深度。 。”、 一1 2 第二章系统概述 i 标注程序解析：解析标注程序，建立类一域一语句一表达式的树结构( t r e e 结构) ，并让t r e e 结构包含b i a 结果信息，成为标注语法树结构。 池标注控制流图的生成：根据标注语法树结构，将源程序按控制结构分成基本 块，并变换成由基本块组成的控制流图，生成标注控制流图。这部分的工 作包括一个控制流图的数据结构及一组相关的结点数据结构，还有组功能 及相应的算法。 i v 滞留程序生成：滞留程序由标注控制流图生成，对标注控制流图进行优化生 成滞留程序。控制流图中包含一系列的基本块，基本块也有b l a 状态，每个 基本块中有一系列的语句，这些语句的b t a 状态决定基本块的b i a 状态，由基 本块和块内语句的状态，决定生成的滞留程序。滞留程序渎取动态的输入和 前段计算的中间结果完成最终计算。这部分的内容包括滞留程序的设计、结 构、生成方法等；本系统的滞留程序与传统部分求值中滞留程序的生成有根 本的区别，传统的滞留程序直接包含前段计算的结果。 v 例化程序生成：例化程序也是由标注控制流图生成，例化程序接收静态输入 的值，进行前段计算，得到前段计算的中间结果和优化控制流程信息，生成 例化控制流图，支持滞留程序的最终运行：它的运行需要程序的静态输入值， 生成则需要保存在控制流图中的静态输入描述信息。例化程序和滞留程序都 是由标注控制流图生成的，它们的生成不存在先后关系和数据及控制的依赖 关系，是并列的，标注控制流图是生成例化程序和滞留程序唯来源。这一 部分内容包括例化程序的设计、例化程序运行生成的例化控制流图、例化程 序生成方法等内容。 v i 例化程序运行环境：为侈i 眦程芋的运行提供支撑，是一个与具体被例化程序 无关的程序库，维护程序中各函数的控制流图及其基本块操作，以类库的形 式为例化程序的执行提供支持。例化程序运行环境的另部分，就是例化程 序如何接收静态输 值生成作为中间结果的例化控制流图。 v i i 滞留程序的运行环境：为滞留程序的运行提供支持环境，支持数据缓冲区的 读取，例化控制流图的解释执行，是个与具体被例化程序无关的程宁律， 以类库的的形式为滞留程序的执行提供支持。例化程序、例化程序运行环境 等程序为产生、构造合理优化的中间结果和控制信息提供良好的支持。 v i i i 例化控审蜿图：也就是中间结果和控制信息，是本系统中很重要的部分， 例化程序的运行结果，保存在例化控制流图数据结构中，也包含了优化后的 控制流图。滞留程序将根据f 电仃 ，接收动态输入的值，完成计算。 北京工业大学工学硕士学位沦文 第三章四e s l 语言的设计 3 1 j p e s l 语言的设计背景 本课题利用基于控制流图的程序例化技术实现了针对j a v a 语言的部分求值器，对 输入的j a v a 程序j 蝴0 化处理，同时根据部分静态数据，生成保存了前段计算结果和 程序控制信息的滞留程序；在程序的实际运行时刻，将会利用保存在滞留程序中的前 段计算结果和经过优化的程序控制信息，进行剩余部分的计算。这样，那些静态计算 作已经被提取出来，提前计算出结果，并保存在滞留程序中；在程序的运行时刻， 直j 安使丹j 提前计算好的结果来 进行剩余的计算，因此在运行时刻，实际上只进行了全部计算工作的部分。基 r 上述的基本思想，来达到优化程序执行陛能的目的。 基于以下几个方面的目的，需要提供种部分求值需求描述语言( p a m a l e v a l u 觚o n s p e c i 丘c 撕o nl a n g u a g e ) ，向部分求值器描述原始程序所需的接口信鼠、处理方式、参 数动静状态信息和特殊处理方式所需的一些额外信息。利用这些售息，部分求值器就 能够知道在程序m 位置、使用什么方式进行例化处理唧1 2 8 1 嘲帅】。 3 1 1 描述接口信息 对于经过部分求值处理之后的j a v a 程序，尽管在执行效率上得到了改善，并且计 算结果与原始j a v a 程序的计算结果完全一致，但程序之间的接口却发生了显著的改 变。 首先，一段完整的计算过程在经过部分求值处理之后，被拆分成了滞留程j 亨坪口例 化程序两部分。当程序运行时刻，滞留程序需要读取程序中保存的前段计算结果和经 过优化的程序控制信息。而这们卖取的过程会极大地影响到程序执行的整体性能和执 行的正确陛，因此，这两部分之间的交互便变得非常重要。 而且，由于j a v a 面向对象的特| 生，一段程序往往会在多个位置被重用多次，不仅 第三章j p e s l 语占的设汁 仅应用在同程序的不同位置，还会应用在多个程序中。因此，对于经过部分求值处 理的j a v a 程序来说，易用性和封装l 生同样重要。为了扩大部分求值器的| 立用范围，必 须使经过部分求值处理的程序具有与原始程序相同或相近的面向对象特眭，例如封装、 多态等。 基于上述两个原因，本课题需要为程亭内部和外部交互提供完备的程序框架，由 程序框架来完成对滞留程序读取操作和对外操作的封装。这样，例化程序和滞留程序 之间的交互就会具备高度的封装性，同时使部分求值处理后的程序变得更容易使用、 重用性更高。 在提供程序应用框架的同时，部分求值器需要输入一些描述信息来满足自动生成 程序匣用框架的需要。为此，部分求值需求描述语言有责任负责提供这些信息。 3 1 _ 2 描述处理方式信息 j a v a 程序可分为本地程序、砌m 限e n l o t em 曲0 di n v o k 撕o n ，远程方法激淘程序和 a p p l e t 程序。 i 本地j a 忸程序：本地j a v a 程序使用统一的方式处理全部j a v a 对象，即每个 类定义的成员变量和成员函数都屎存在本地的对象实例中。调用本地j a 忸对 象的成员变量或成员方法，都会矗接引用保存在本地对象实例中的成员变量 或成员方法。而且，对象之间的交互都是本地操作，对象本身也保存在本地。 i i 咖程序：同本地j a v a 程序相反，在大多数情况下，r m i 客户端调用的远 程对象并不位于i u 客户端所在的计算机，而是驻留在一个或多个服务器 上。砌客户端和砌m 服务器端之间通过命名服务获得相互之间的位置， i 咖服务器首先要向命名服务注册自己将要驻留的对m 远程对象，然后r 客户端将会根据正确的名称向命名服务发送查找请求，并由命名服务返回远 程对象。当砌v i i 客户端通过命名服务获得了远程对象副本的时候，就可以把 该远程对象的方法当作本地方法一样调用。对象的方法实际上是在服务器上 运行，然后把计算的结果返回给客户端。 na p p h 程序：j a v aa p p l d 是种可以嵌入到网页中的小应用程序。当用户访 问包含a p p 慨小应用程序的网页时，a p p 融将被下载到用户的计拿鲫上执行。 a p p l e t 依赖于岗i 览器，必须在浏览器内运行，无法朝蝤蚕行。由浏览器控制 a p p l e t 的生存周期。同上面两种类型的j a v a 程序相比，a p p l e t 的程序结构很 特殊。首先，却p k 程序没有m a i l l 函数，浏览器负责启动和销毁a p p l e t ；另 外，为了使浏览器能够控制a p p l e c 的生存周期，却p k 向浏览器提供了一些 北京工业大学工学顾士学位论文 控制自己运行方式的方法。因此，针对这种特殊结构的j a v a 程序，部分求值 器采用了不同的处理方式，并需要生成了a p p l d 专用的程序应用框架。 针对这三类j a v a 程序，部分求值器将会采取不同的处理方式。这时，也必须同时 生成寸应的程序应用框架。为此，部分求值描述语言必须提供当前输入的j a v a 程序所 需的处理方式，以及使用该处理方式生成程序应用框架所需的额外信息。 3 1 3 参数动静状态信息 部分求值过程中，部分求值器把原始程序分成两个部分，即例化程序和滞留程序。 在拆分过程中，部分求值器将会根据原始程序代码以及输入的部分静态数据来判断 原始程序的结构，并判断每个变量和表达式的动静状态，以便决定采用什么方式处理 这些变量和表达式。 但是，在大多数情况下，仅仅依靠原始程序代码，根本无法判断每个变量和表达 式的动静状态。虽然原始程序代码提供了程序的流程信，铆结构信息，但却无法体现 输入参数的信息，例如，在什么情况下，什么输入参数将会固定不变，以及该参数的 值：什么参数的输 将会对程序抽_ 亍的性能影响最大等等。因此为了说明输入参数的 动静状态和内部不变量，有必要将参数的动静状态信息作为部分求值器的输入。 另外，有的时候，部分求值器的使用者会希望能够自己指定某些参数为某种状态。 因i 比! 蟛页通过种力i 渐需 亳哒的信息程五箍给部分习t 值器。 如上所述，在部分求值处理过程中，需要向部分求僵器崩整原始程序的参数动静 状态信息，以便部分求值器判断原始程序中每个变量和表达式的状态，并决定处理这 些变量和表达式的方式。 3 2j p e s l 语言的设计 s 吼公司为j a v a 程序设计语言提供了功能强大的开发包。使用j a v a 程序设计语言 及其相关开发包，不仅仅可以开发本地和网络应用程序，还可以编写a p p 融，实现动 态页面效果：而且，j a 语言提供了实现分布式计算的开发包- 远程方法激活( 鼢m ， r e n l o t e t v i d h o di n v o c a 蛀o n ) 。 鉴于j a v a 程序的多样性，俐巳s l 描述语言必须能够描述部分求值器处理各种j a v a 第三章j p e s l 语言的设计 应用时所需的信息，队便部分求值器进行部分求值处理。为此，除了提供尚苤通用信 息的译狲规则之外，j p e s l 描述语言还据供了描述i m 应用和a p p l d 应用的评狲规 则。 为实现上述功能，j p e s l 描述语言提供了如下基本元素： 表3 1 ：j p e s l 基本元素表 1 。幽l e3 1 t p f s i t a 西c e i 臼t 郾虹l i s f i m e t h o d ：为函数方法说明关键字。使用该关键字，描述语言能够向部分求 值器指定原始程序中需要处理的某个方法，并提供处理过程中所需的参数动 静状态等信息。而且，在m 既h o d 关键字构成的语句块中，还可以提供不 变量表，来说明该方法中存在的不变量。 i s 觚：静态参数关键字。使用该关键字，描述语言能够向部分求值器指定 原始程序中某个函数：方法中某个参数为静态。 试d y n a m i c ：动态参数关键字。使用该关键字，描述语言能够向部分求值器 指定原始程序中某个函数方法中某个参数为动态。 i v d e n ：标识符。在该描述语言中， 、 、 、 、 、c 嫂潼名 、 和锄p l e i 参 数名 都是标识符。 v 砌丑订a r eo 胍c t 烈狼f a c e ：远程对象接口关键字。由于部分求值删备 会处理砌m 应用程序，而r m i 应用程序包含黜皿服务器端和r m i 客户端， 以及砌皿远程列缘。当砌v i i 客户端向砌m 服务器发送请求的时候，如果服 务器接受到了该请求，会将r 卜_ 远程对象返回给客户端，但并不是把远程对 北京工业大学工学硕士学位论文 象直接返回，而是向客户端提供鼢m 远程接口，通过砌远程接口调用底 层的代理来引用远程对象。j p e s l 描述语言中的 r e m o ，i eo b j e c t 孙r 1 1 e r f a c e 关键字指定了这们立程中使用到的r 远 程x 寸象接口的名称。 v i 洲a r eo b j e c t 巩伊i 脚盯：远程对象关键字。在砌v i i 服务器上运行 雍葑垂弄呈对象，谚0 运螽呈x j 刍臭实现了r e h c ) 1 eo b j 】二c tb 哪r f a c e 关键字指 定的远程对缘接口。j p e s l 描述语言中的砌m 【0 ，r e0 b j e c t 脚p i 融厦d 盯 关键字指定了远程对象的名称。 v i i s e i e rs o i 瓜c e s ：i t 服务器名称关键字。部分求值器处理远程对象之 后，将会为优化后的远程对缘生成一个新的类名，而黜m 服务器本身也魍含 了对远程对象的引用，如果希望f t 服务器能够继续使用，那么必须要把 i u v i i 服务器中砌m 远程对象的名称替换成七 亡化f 舌的远程对象类名。因此， j p e s l 描述语言提供了s e i 己v e rs o u r c e s 关键字，来指定i t m i 服务器类 的名称。 v i i i c i 皿卧汀s o i 瓜c e s ：i t h 皿客户端名称关键字。部分求值处理远程对象之后， 将会生成个新的远程对象接口，为了使用经过优化的远程对象，1 0 m 客户 端必须修改内部引用的远程对象接口名称。为此，j p e s l 描述语言提供了 c im n t 洲i r c e s 关键字，来指定砌m 客户端的名称。 i ) ( a p p l 正tc k 峪s ：a p p l 成名称关键字。由于部分求值黔榭a p p hl 弱莲 行部分求值处理，因此j p e s l 描述语言需要为a p p l 哉的处理提供些辅助信 息。 x a p p 强tm m is ： r r 咖文件名称关键字。使用a p p l e t aa s s 关键字 指定的却p 搬的h i m l 文件名称。经过部分求值处理之后，将会生成另外 个经过优化的邸p l 吐类，那么引用该a 卵h 的 r m 亿文件就需要修改引 用时使用的a p p 搬类名称。 妯a p p l e tp a ra m e 耵球s ：a p p 赋的h m 几参数名称。在使用该a p p 蛾的 删，文件中，通常使用 书谥为a p p k 指定了多个参数名称和参 数直，这样a p p 敞撕时刻自嘲动态谗玻土型 参数值。在部分求澎也理过 程中，将会将这些参数值直接固化在代码中，以便提供a p p 妇执行时的性能。 a p p l e tp a r a m 既t s 关键字指定了m m l 中提供的a p p i e t 参数名称。 j p e s l 描述语言的完整语法规则如下： 第三章j p e s l 语言的设计 | ( a p p l e t 对象类说明 专r 跚o r 巳_ o b j e c t j n t e r f a c e= ： r 删r e o b j e c t j l p l 删 ： s e r v e rs o u r c e s _ ， ： c l i e n ts o u 陋e sk ， ： ( a p p l e t 对象类说明 专a p p l 叫c l a s s_ ： a p p l 田s = f ， a p p l e tp a r a 唧e r s = ， ) ：) 专 专忸t h o d ) 专脏t h o d ( ) 专 ( ) ， 专 = s t a t i c ( 参数浣明 专 d y n a f l i c 专 ( ： 专 ： 专： i d e n 专 北京工业大学丁学硕士学位论文 3 3 详细程序设计 3 3 ij p e s l 描述语言数据对象设计 上面陈述了j p e s l 描述语言的文法设计，为了使部分求值器能眵使用该描述语言 描述的规俐言息，必须实现j p e s l 描述语言的解析工具，并向部分求值器提供保存有 规格信息的数据对象。 由于j p e s l 描述语言中需要为三种类型的j a v a 应用提供规格信息说明，即本地应 用、r m 【远程应用和a p p 搬应用。因此，解析j p e s l 描述语言之后，需要为这三种 不同的应用保存信息。 由此得到的数据对象设计如下： 图3 1j p e s l 舅啪弘蟓设计圈 f i 昏聆3 1j p e s l d a 诅喇e c b d 囟争d 瑶r t i s c r i p t d a t a ：保存了全部规格信息。内部使用了三个v 。c 鼢对象，分别保存了 胁n o t e h _ l f b 、a p p l e t h l f b 和f u l l c h 而类型的元素。 第三章j p e s l 语言的设计 j r e m o c e h 怕：保存了全部r 加应用相关的规格信息。其中包括远程对象接口 名称、远程对象名称、r 服务器名称列表和r 客户端名称列表。 i i i a p p l e 【h l 如：保存了全部a p p l c t 应用相关的规格信息。其中包括a p p l c t 的名 称和该a p p l c t 的参数信息，a p p l e t 的参数信息保存在p 越l h l l b 类型的成员中。 i v p a m h 面：保存了a p p l e t 的参数信息。这些信息不仅仅指明了该a p p l e t 所使 用的参数信息，还提供了使用该a p p l e c 的m m ，文件的名称。 v f u