（计算机软件与理论专业论文）java语言自动例化中扩展绑定时间分析技术的研究.pdf

捕竣 摘要 当前，计算机技术发展迅速。随着硬件速度的提高，软件的通用性设计和 复杂黎构成为疆暑整体往麓翡瓶颈，软件爨魂纯的麓究箴为热患阉逶，舔分求 值技术正是这一领域f 1 提高软件效率的方法之一。j a v a 语言作为种面向对象 程序设计语言具有许多良好的特，陡，但其解释执行的方式产生的程序性能问题 蓬老软 譬复杂疫豹提衰变键更鸯爨明攫，因此将邦分求值披寒应用予j a v a 港言是 该领域的研究热点。 在传统静瑟囱辩象语言部分求篷器审，鬃定辩阉分耩酶不精确导致程淳串 大量的可例化点被忽略，从而影响了整个部分求值的效果。为此本文提出了一 种扩展绑定时问分析技术，该技术在传统绑定时间分析之中弓l 入了对象分析， 将分辑豹蕈元歇类交必了对象，双方法变为了方法豹每次调臻，进慈提魄一静 对象类例化模型。程对象类例化模型中，闭一个类在不同绑定时间上下文环境 下构造静对象可敬瓣应多个类镶能模式，褥祥对个方法静多次调趸邈会由于 上下文环境不同丽对应多个方法例化模式。采用这种方法就可以确定同一个类 生成的不同对象在程序运行中各自具有的可例优点，而不必像传统绑定时间分 掇那撑只巍识裂熟们公共豹冒捌他点。生成对象类铡化模型后，扩展绑定融阅 分析会根据陔模型生成待例化程序，为其中的类例化模式生成待例化类，为方 法翻亿模式生成待铡纯方法。在符倒往程序翡基黼上，魏可鞋分涮对上述类对 象和方法调用进行标注，从丽提高绑定时间分析的精确憾。 这种方法已经用于实现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 ri 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 w i t hi h e p r o m o t i o no fh a r d w a r es p e e d ， s o 行w a r e sg e n e 珀1 i i ya n dt 1 1 ec o m p l e x i t yo fi t si n f r a s t r i l c t u r eb e c o m el h eb o t t l e n e c k ，s o t h e r e s e a r c ho fs o f t w a r ea u t o m a t i o nb e c o m e sah o t s p o t p a n i a le v a l u a t i o ni sj u s to n eo ft h em e t h o d s t op m m o t es o f t w a f e se f f i c i e n c y a sap o p u l a ro b j e c t o r i e n t e dp r o g r a m m i n gl a n g u a g e ，j a v ah a s m a n yg o o dp r o p e r t i e s b u ta l o n gw i t h t h er a i s eo fs o f t w a r e sc o m p l e x i ty j a v ap m g 阳m s c x p l a i n a n d m nm a n n e ra d d ss e v e r i t yt o t l l ep e r f b 珊加c ep r o b l e m 1 1 1 e r e f o r e ，a p p l y i n gp a r t i a l e v a l u a t i o nt e c l l l l i q u et oj a v ap f 0 簪哪i sak e yi s s u ei nt 1 1 i sa f c a 1 nt r a d i t i o n a lp a r t i a le v “u a t o rf o fo op m f a 衄i n g1 a n g u a g e ， t h eu n p c i s i o no f b i n d i n g - 噩m ea j i a l y s j sc 肌st h cl o s s o fm a n ys p e c i a l i z a b l ep o i l l t si ns 0 u r p r o g r a m ，a n d i m p a i r st h ee 彘c to fp a n i a le v a l u a t i o n t 0s o l v et h i s 口o b 王e l n ，t h i sp a p c rp r o p o s e sat e c h n i q u eo f e x t e n d e db i n d i n 目，n m ea n a l y s i s e b l ai n t f o d u c e so b j e c ta n a l y s i s i n t 0t r a d i t i o n a lb t a ， t f a n s f o 咖i n ga n a l y z i n gu n i tf r o mc l a s st 0o b j e c t ，f r o mm e t h o dt om e t h o dh v 0 c a t i o n a o c o r d i n g t ot h i s ，w ep r e s e n tas p c c i a l i z e c 1 a s sm o d e l _ t h em o d e lp r o v i d e sm u l t ic l 赫ss p e c i a l i z a t i o n p a t t e m sf o ro n ed a s sw h e ni t so b j e c t sa t ei n s t a n c e du n d e fd j f c e r e n tb t ae n v i m n m e n t ，a n d i ta l s o p r 0 “d e sm u l t im e t h o ds p e c i a l i z a t i o np a t t e m sf o ro n em e t h o dw h e ni t i si n v o k e du n d e rd i 雎呦t b t ae n v i m n m e n t 1 1 1 e ns p e c i a l i z a b l ep o i l l t so ft h o s eo b j e c t s ，w h i c h 眦i 瞄t a n c e df f o mt h es a m e c l a s s ，c a nb ed e t e 咖i n e d 佗s p e c t i v e ly ，b u th a v en on e e dt ob eu n i t e dj u s ta si n t r a d i t i o n a lb t a a f l e rg e n e r a t i n gi h es p e c i a l i z e c i a 龉m o d c l ，e b l ap m d u c c sp r c 。s p e c i a l i z e dp r o g m mt h a t i n c l u d e sp r e s p e c i a l i z e dc l a s sf o re v e r yc l a s ss p e c i a l i z a t i o np a t l e ma n dp 丁e s p e c i a l i z e dm e t h o d f o re v e r ym e t h o ds p e c i a l i z a t i o np a t i e m o nt h eb a s i so fp r c - s p e c i a l i z e dp r o g r a m ，w ec a na n n o l a i e e a c ho b j e c ta n dm e t h o dc a l j ，t h e r e b yi m p r o v i n gt h ep r e c i s i o no fb t a n i sp a p e rp r o v i d e sa ne f f e c t i v ew a yi oi m p l e m e n tp a r t i a le v a l u a t i o nf o rj a v ap r o g r a mw i t h h j g hp r e c i s i o n t h ea p p r o a c hh a sb e e na p p l i e dt oi h eb i n d i n g t i m ea n a l y s j so fj a v ap r o g r a m ，a n d c a na n a l y z em o s lo f 山es i g n a 】一t h r e a dj a v ap r o g r a m sa c c u r a t e i ya n dp r e c i s e ly k e y w o r d sp a n i a le v a l u a t i o n ；b i n d i n gt i m ea n a l y s i s ；a l i a sa j l a l y s i s 1 1 1 独创性声明 本人声明所呈交的论文是我个人在导师指导下进行的研究工作及取得的研 究成果。尽我所知，除了文中特别加以标注和致谢的地方外，论文中不包含其他 人已经发表或撰写过的研究成果，也不包含为获得北京工业大学或其它教育机构 的学位或证书而使用过的材料。与我一同工作的同志对本研究所做的任何贡献均 已在论文中作了明确的说明并表示了谢意。 签名：舷日期：垄丛丛7 关于论文使用授权的说明 本人完全了解北京工业大学有关保留、使用学位论文的规定，即：学校有权 保留送交论文的复印件，允许论文被查阅和借阅；学校可以公布论文的全部或部 分内容，可以采用影印、缩印或其他复制手段保存论文。 ( 保密的论文在解密后应遵守此规定) 签名：乏毯堑导师签名：塑盟 仉。j 开期： 步飞 1 1 研究背景 第1 章绪论 随着软件工程及软件复用技术的不断发展，可重用性、兼容性、可扩展性、可互 操作性已经成为软件设计的发展方向，这样可以大大减少重复开发，提高软件开发 的效率，但同时也造成软件结构的复杂化及性能的下降。 而程序优化技术也由此成为了计算机软件研究领域的热门闯题之一，涌现出了许 多好的方法和策略，比如具体类型分析( c o n c k t ct y p ei n f e r e n c e ) 、类型反馈( t y p e f e e 曲a c k ) 、部分求值( p a n i a le v a l u a t i o n ) 等。其中应用部分求值技术进行程序优化吸引 了许多学校和企业进行研究，并成功地构建了一批可以应用于各种主流语言的部分 求值器。 j a v a 作为一种面向对象程序设计语言哆拥有许多优点，如良好的可移植性、完 善的错误处理功能及垃圾回收机制，在提供强大功能的同时简化了程序开发的工作， 但由于j a v a 程序采用动态解释执行的方式，与c 等命令式语言编写的程序相比，在 执行效率上j a v a 程序有一定的劣势，因此如何提高j a v a 程序的执行效率已经成为 了许多专家学者的研究方向。随着大量的编译优化技术被应用于新版本的j a v a 编译 器口，”，j a v a 程序的执行效率得到了很大的提引。 但是随者计算机软件被应用于越柬越复杂的业务和场景，软件的通用性是不断增 加的，舌则业务需求上一些小的变动将会导致大量的重复开发工作，而这些通用的 软件在被应用于某特定场景时，就会产生或多或少的重复运算，这些重复运算可 能会对程序的运行效率产生较大影响。采用j a v a 语言编写的程序同样存在这一问题， 而且妇”语音的跨平台特性使它确更大的- 可能被府用f 对通用性要求较高的软件。 这时一蝗研究人员发现将部分求值技术应用于j a v a 程序是克服程序通用性提高对程 序执行效率影响的一种行之有效的解决方案。部分求值技术可咀根据特定的应用场 景，对通用程序进行改造，去掉或提前完成公共运算，为该应用场景生成专用程序， 很显然专门程序的运行效率要优于通用程序。一个好的部分求值解决方案应当能够 精确地定位当前场景中有哪些公共运算可以被提前处理，从而为该场景生成尽量简 化的专用程序。 化的专h j 程序。 北京i 业人学t = 学硕l 学位论文 本课题是国家自然科学基金支持的研究项目，为了更好的对j a v a 程序进行部分 求值，本文给 l 了j a v a 语言部分求值器中一些关键部分的设计思路和算法，这些算 法和策略能够帮助j a v a 语言。部分求值器在特定场景下生成更简化的专用程序。 本文主要考虑j a v a 语言的一个子集，但研究成果可以很容易地转化到其他面向 对象程序设计语言。研究过程中涉及到的理论和技术主要包括：部分求值技术、面 向对象语言原理、具体类型分析、编译技术。 1 2 部分求值简介 为了提出本研究的主要内容，这里简单介绍部分求值的相关概念1 4 j ，6 ，7 】更多的说 明请参见第二章。 在特定场景下，一个通用程序的输入通常可以分为两部分：静态输入和动态输 入，其中静态输入在程序运行过程中相当于所谓的不变量，动态部分也就是变量。 部分求值技术是一种典型的基于分段计算的程序优化技术，针对源程序和静态输入 进行的计算，就是前段计算；滞留程序( r e s i d u a lp r o g r a m ) 是后段计算，它接收动 态输入并完成最终的计算，这里的滞留程序也就是前面所说的专用程序。前段计算 进行优化的工作，后段计算利用优化的结果来完成。 例化就是一种基于分段计算的程序优化技术，部分求值技术就是根据不同的场景 对通用程序进行例化，从而达到优化程序执行效率的目的。根据例化的流程，部分 求值可以分为在线部分求值( o n l i n e ) 和离线( o f f l i n e ) 部分求值【8 】。在线部分求值在 例化过程中直接使用静态输入的取值确定后续的处理方法。而离线部分求值对源程 序进行例化前加入一个预处理阶段，叫做绑定时问分析( b i n d i n gt i m ea n a l y s i s ) ， 以下简称为b t a 。b t a 针对源程序中输入的状态( 动态静态，也可称为绑定时间状态) ， 分析出哪些运算可以在例化阶段完成，并且在分析过程中不考虑静态输入的取值， 这些可以在例化阶段完成的计算称为可例化点。b t a 完成之后的例化阶段根据静态输 入的取值完成可例化点的运算，生成滞留程序。 1 3 研究内容 本课题主要讨论采j f j 离线部分求值技术的j a v a 程序自动例化。而绑定时间分析 作为离线部分求值t j 的火键技术，根据给；的源f - ! j 和乖t ”芋输入的绑定时n j j 状态， 辩1 荦蛾论 对源程序进行分析，分析的结果通过绑定时n u 标记町将源程序区分为：可在例化阶 段完成的汁算( 静态计鲜) 和必须存运行阶敬完成的计算 c a l c ( e x p s ) 方法例化模式2 = 类例化模式2 c a l c ( e x p d ) 一l q 北京t 业人学丁学硕j j 学位论文 图3 _ 4j “a 程序示例 图3 _ 5 变换后的待例化程序 f i g u 悖3 4 a j a v ap f o g 辟m f i g u 佗3 _ 5p r e - s p