（计算机软件与理论专业论文）对象生命期分析及其应用研究.pdf

摘要 摘要 j a v a 语言使用垃圾收集器自动回收儿用对象的内存单元，造成j a v a 语言帽 较于c + + 等其它面向对象语言运行效率低。因此，有必要通过优化对象内存空 间管理模式，提高j a v a 虚拟机的运行性能。 对象生命期分析为j a v a 语言对象内存空间管理模式的优化提供了基本的依 据，其通过对程序进行分析获得程序中对象的乍命期信息。逃逸分析是获得对 象生命期信息的一种晕要的分析手段，但其获得的信息不够精确，不能很好地 辅助对象内存空间管理优化工作的进行。 为了解决上述问题，本文提出了一种荩丁逃逸分析的对象中命期分析方法， 并以其为基础实现了一种对象内存空间管理模式的优化j 髓用：j l t ( j u s t i n t i m e c o m p i l e r ) 辅助g c ( g a r b a g ec o l l e c t o r ) 优化应用。围绕着对象生命期分析和j i t 辅助g c 优化应用，本文重点探讨并完成了以下丁作： 1 提出一种基于逃逸分析的对象生命期分析算法，以获得更为精确的对象 生命期信息。 本文提出了一种基于逃逸分析的、增量式、过程间的对象牛命剜分析，结 合过程内与过程间的分析算法，分析非全局对象的生命期信息。 2 扩展即时编译器高级中间表示指令集及相关解析操作以支持代码变换。 为实现代码优化变换，在即时编译器高级中间表示指令集上增加支持对象 显式回收的指令。在低级中间表示层甚至更底层实现对这些扩展指令的解析。 3 利用对象生命期分析结果设计并实现代码变换策略。 基_ 丁对象生命期分析提供的分析结果，实现在高级中间表示层进行的代码 变换，旨在适当的程序点处插入夕匕亡对象的回收操作并保证运行时执行。 4 结合即时编译器流水线体系结构，以优化遍的形式实现分析和变换。 我们在a p a c h eh a r n l o n y 的即时编译器中以优化遍的形式实现了对象生命期 分析和j i t 辅助g c 的优化应用。实验结果表明，分析较为精确地计算出局部对 象的生命期信息，j i t 辅助g c 比普通的g c 更具高效性。 关键词：对象生命期分析逃逸状态流水线框架j i t 辅助g c 代码插桩变换 a b s t r a c t ab s t r a c t j a v ai sak i n do fo 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 ew i t hu n u s e do b i e c t m e m o 叫r e c i a i m e db yg ca u t o m a t j c a j j y i tm a k e sj a v aw o r kj e s se f e c j v e l yf h a n o t l l e ri a u g u a g e ss u c ha sc + + i ti sn e c e s s a 吖t oi m p r o v e t h ee f n ci e n c yo fj a v av i r t u a i m a c h i n eb yo p t i m i z a t i o n sf o ro b j e c tm e m e o r ym a n a g e m e n tm o d e l o b j e c tl i f e t i m ea n a i y s i sc a np r o v i d et h eb a s i ci n f o r m a t i o nt h a to p t i mi z a t i o n sf o r o b j e c tm e m e o 吖m a n a g e m e n tm o d e io fj a v an e e d i ta n a l y z e sp r o g r a m sa n dg e t st h e o b j e c tl i 危t i m ei n f o n n a t i o nf o rt h eo b j e c t st h a ta p p e a ri nt h ep r o g r a m e s c a p ea n a l y s i s i sam e t h o dw h i c hc a nc a p t u r eo b j e c tl i f e t i m ei n f o 彻a t i o n ，h o w e v e r ，t h ei n f o m l a t i o n t h a ti tg e t si sn o te n o u g hf o r l o t so f o p t i m i z a t i o n sf o ro b j e c tm e m o 叫m a n 鸭e m e n t a st ot h e o i u t i o n sf o rt h ep r o b l e m sm e t i o n e da b o v e ，w ep u tf o r w a r da no b j e c t li f e t i m e a n a i y s i sm e t h o db a s e do ne s c a p ea n a i y s i s ，a n da no p t i mi z a t i o nc a i l e d j l t a s s i s t e dg cb a s e do nt h i s a n a l y s i s f o rt h eo b j e c tl i f e t j n l ea n a i y s i sa n di t s o p t i m i z a t i o na p p “c a t i o n ，t h i sp a p e rm a i n i yd e p i c t sa n dd i s c u s s e st h ef o i l o w i n g 、】i ，o r k s ： 1 p u t sf o n f l ，a r da no b j e c ti i f e t i m ea n a l y s i sa i g o r j t h m ，t og e tm o r e p r e c i s eo b j e c ti i f e t i m el n f o r m a t i o n i n t h i sp a p e r ，w ed e s c r i b ean e wo b j e c tl i f e t i m e a n a l y s i sa l g o r i t h mw h i c hi s b a s e do ne s c a p ea n a l y s i s i ti sak i n do fi n c r e m e n t a la n dc r o s s p r o c e d u r a ia n a i y s i s t h ea n a i y s i sp e r f o n n si n t r a a n d i n t e r - p r o c e d u r a la l g o r i t h m s ，a n da n a i y z e st h e l i 佬t i m ei n f o r m a t i o nf o rn o n 9 1 0 b a lo b i e c t s 2 e x t e n d sj l th i rj n s t r u c t j o n s e ta n d i m p i e m e n t s t h e c o r r e s p o n d i n gr e s o i u t i o no p e r a t i o n si nl i ri e v e i ，t os u p p o r th i r t r a n s f b r m a t i o n s f o rt h ei m p i e m e n t a t i o nf o rh l rt r a n s f o r m a t i o n s ，w ea d ds o m en e wk i n d so fh i r i n s t r u c t i o n s ，t os u p p o r te x p i i c i to b j e c tm e m o 叮r e c i a m a t i o no p e r a t i o n s a n dw ea l s o i m p l e m e n tt h er e s o i u t i o np r o c e s sf o rt h ea d d i t i o n a ii n s t r u c t i o n si nl iri e v e l 3 d e s i g n sa n di m p i e m e n t sh i rt r a n s f o r m a t i o nu s i n gt h e a n a l y s i s 舱s u i t so fo b j e c ti i f e t i m ea n a l y s i s w eu s et h ea n a i y s i sr e s u l t sp r o v i d e db yt h eo b j e c tl i f e t i m ea n a l y s l st o m p l e m e n h i ri n s t r u m e n tt r a n s f o r m a t i o n t h i s h l ri n s t r u m e n tt r a n s f o r m a t l o n w 1 i im s e r t e x p l i c i tm e m e o 拶r e c l a m a t i o no p e r a t i o n si n t oa p p r o p r a t ep r o g r a mp o m t s ，a n d m a k e s u r et h eo p e r a t i o n sw o u l db ee x e c u t e d - 4 i m p l e m e n t sa n a l y s i sa n dh l rt r a n s f o r m a t i o n i nt h ef o r mo f o p t m i z a t i o np a s si nt h ep i p e i i n ef r a m e w o r k o fj ii w ei m d i e m e n tb o t ho b j e c tl i f e t i m ea n a l y s i sa n dh i ri n s t r u m e n t 。a n 5 t o 肿a t l o n i nt h ef o 眦o fo p t i m i z a t i o np a s si nj i t o fa p a c h eh a m l o n y n ee x p e 姗e n t a lr e s u l t s s h o wt h a to u ra n a i y s i s c a ng e tt h eo b j e c tl i f e t i m e i n f o r m a t i o np 。e c l 3 e ly ，a n d m 二a s s i s t c dg cc a nw o r km o r ee f ! f i c i e n t l yt h a nc o m m o ng c i nj a v av l r t u a im a c h l n e k e yw or d s ：。b j e c t 撇i m ea n a l y s i s ；e s c a p es t a t e ；呻e l i n e 仔a m e w 。r k ；j i t - a s s i s t e d g c ；h i ri n s t r u m e n tt r a n s f o n n a t i o n 1 1 1 中国科学技术大学学位论文原创性和授权使用声明 本人声明所呈交的学位论文，是本人在导师指导下进行研究工作 所取得的成果。除已特别加以标注和致谢的地方外，论文中不包含任 何他人已经发表或撰写过的研究成果。与我一同工作的同志对本研究 所做的贡献均已在论文中作了明确的说明。 本人授权中国科学技术大学拥有学位论文的部分使用权，即：学 校有权按有关规定向国家有关部门或机构送交论文的复印件和电子 版，允许论文被查阅和借阅，可以将学位论文编入有关数据库进行检 索，可以采用影印、缩印或扫描等复制手段保存、汇编学位论文。 保密的学位论文在解密后也遵守此规定。 作者签名：丝 伽d 辟如咖 第l 章绪论 第l 章绪论 住j a v a 语言上，针对程序中对象内存空间管理模式的优化工作包括对象分 配模式的优化和对象回收模式的优化两类。而对象乍命期分析( ob i e c tl i f e t i m e a n a l y s i s ) 是对象内存空间管理模式优化工作的基础，它为优化工作提供必要的 程序对象生命期相关信息。本文提出了一种对象生命期分析技术，并基于该分 析实现了一类对象回收模式的优化应用t 作。 本章首先介绍了对象生命期分析技术及其戍用的研究背景，接着对当今国 内外研究的相关工作做出分析和比较，最后给出本文的研究内容。 1 1 问题描述 j a v a 是种面向对象的程序设计语言，程序巾的对象主要是在内存堆( 简 称堆，h e a p ) 中分配并l 司时进行初始化，而垃圾收集器( g a r b a g ec o i l e c t o r ，简 称g c ) 统一管理对象在堆中的分配、访问与回收。对象的堆上分配以及g c 的 对象自动内存回收方式都使得j a v a 语言相比于c 抖等其它语言效率要低得多， 因此，有必要针对对象的分配模式和回收模式进行优化，以提高j a v a 虚拟机的 运行性能。 不论是对象分配模式还是对象回收模式的优化，必须掌握程序中出现的对 象的生命期信息，这需要有对象生命期分析技术的辅助与支撑。对象生命期分 析是一类程序分析技术，它通过程序分析获得程序中对象的生命期信息，是许 多面向对象语言对象内存空f b j 管理优化工作的基础。在现今的周内外研究工作 当中，有多类程序分析技术，如逃逸分析( e s c a p e a n a l y s i s ) 和指针分析( p o i n t s t o a n a l v s i s ) 等，可以获得对象的生命期相关信息，特别是逃逸分析，它是近年来 绝大多数j a v a 语言对象内存空问优化研究工作的基础。作为种数据流分析技 术，逃逸分析可以捕获程序中对象的逃逸状态，并住一定程度上反映了对象的 生命期状态，然而，在获得对象的生命期信息方而，分析能力还非常有限，获 得的对象生命期信息也不是很充分。 j i t 辅助g c ( j i t a s s i s t e dg c ) 是j a v a 语言上一种对象回收模式的优化工 第1 章绪论 作。图1 1 给出了儿t 辅助g c 优化工作的框架。它在即时编泽器( j u s t i n t i m e c o m p i l e r ，简称j l t ) 端进行程序分析获得程序中对象的生命期信息，并利用分 析结果进行相应的代码变换等操作；而存g c 端进行部分对象的显式回收运行时 操作，从而以部分对象的显式内存回收( e x p l i c i tm e m o r yr e c i a m a t i o n ) 来辅助 剩余对象的自动内存回收( a u t o m a t i cm e m o 眄r e c l a m a t i o n ) 操作。对十传统的 g c ，对象的回收模式是自动地回收，这种回收模式虽然使得对象的管理对程序 员变得透明，但是大大地增加了j a v a 虚拟机的开销；而j l t 辅助g c 则提出了 一种新式的对象同收模式，它通过使得一部分对象在程序运行中显式地被释放， 从而缩小自动被回收对象的范围，减轻g c 自动回收对象的负担，提高虚拟机执 行效率。 1 2 相关工作 图i 1j i t 辅助g c 优化工作大致框架 在面向对象程序设计语言中，对象生命期分析( o b j e c tl i f e t i m ea n a i y s i s ) 旨在获得运行时动态分配的对象在整个程序中与其生命期相关的一些信息。在 静态分析技术方而，r u g g i e r ie ta i ( 1 9 8 8 ) 【2 6 】巾提出一种称作生命期分析( l f e t i m e a m l y s i s ) 的方法，静态地分析具有静态类犁系统目动态分配对象的程序；存动 态分析技术方面，i n o u ee ta l ( 2 0 0 3 ) 【1 8 】为精确地预测运行中的对象生命期行为， 提出了一种通过建立预测器函数( p r e d i c t o rf u n c t i o n ) 跟踪样本程序的执行过程 以获得反馈信息的方法。 然而，在大部分的国内外相关工作q j ，更多的是采用逃逸分析( e s c a p e 2 第l 章绪沦 a n a i y s i s ) 技术来进行有关对象生命期状态的分析。作为一种过程间的数据流分 析技术，逃逸分析可以获得对象的生命期相关信息，并能够应用于许多程序优 化工作当中，是一类重要的对象生命期分析手段。 在所有的对象内存空间管理模式的优化工作当中，改变对象分配方式或回 收方式往往口以在很大程度上减轻g c 管理刘象的负担。其中，比较典型的对象 分配优化方式有：对象的栈上分配( s t a c k a l i o c a t i o n ) 和基于区域的对象分配方 式( r e g i o n b a s e da l l o c a t i o n ) ；而比较典型的对象回收优化方式有：显式回收辅 助g c 的自动回收方式( e x p i i c i tm e m o 巧r e c i a m a t i o na s s i s t e da u t o m a t i cm e m o 叮 r e c l a m a t i o n ) 。 1 2 1 逃逸分析 早期有些在函数式语言( f u n c t i o nl a n g u 蝎e ) 之上的逃逸分析研究，如 d e u t s c h ( 1 9 9 7 ) 蚴和b i a n c h e t ( 1 9 9 8 ) f 3 】，他们认为一旦某个值( v a i u e ) 存入 另外一个值中，它便逃逸了，这种观点对于函数式语言的分析是适用的。 近年来，逃逸分析主要运用于j a v a 编译运行系统的优化工作q j ，用于讣算 对象的逃逸状态( e s c a p es t a t e ) ，并以此作为程序优化工作的依据。逃逸状态反 映了对象的生命期状态，在逃逸分析中，对象的逃逸状态口j 以有三类：未逃逸 状态( n o e s c a p e ) 、方法逃逸状态( m e t h o d e s c a p e ) 和伞局逃逸状态 ( g l o b a l - e s c a p e ) 。 根据分析是在编译时进行还是在运行时进行，逃逸分析技术口j 以分为静态 分析和动态分析两类。前者分析是祉程序编泽时进行的，易于实现但具有一定 的局限性；后者分析是在程序运行时进行的，精确度更高但实现起来更为复杂 且系统开销较大。 1 2 1 1 静态逃逸分析( 编译时分析) 目前，绝大多数逃逸分析的实现都是基于。个所谓的“封闭世界( c l o s e d w b r l d ) 为前提，即所有可能被执行的方法在做逃逸分析前都已经得知并且程序 的实际运行不会改变它们之间的调用关系。在这种前提下，静态逃逸分析口j 以 很好地进行正确目较为精确的对象分析。 1 简单的逃逸分析。一种保守的观点：一个对象一旦被存入了另一个对象 中，该对象便逃逸出去了。借助于这个想法，g a ye ta l ( 2 0 0 0 ) 【| 3 】提出 3 第l 章绪论 了一个非常简单而快速的逃逸分析算法用于j a v a 中未逃逸对象的栈中 分配。虽然这个算法简单而且快速，但刘于j a v a 语言来说，非常地不精 确。 2 过程间流和上下文非敏感的静态的逃逸分析。b o 鲥ae ta i ( 1 9 9 9 ) f 6 】提出 了一个此类分析方法，用十对象上的不必要同步的消除，该方法日j 以分 析对象中的域的状态，然而在某些情况下( 如对象的多次传递引用) 不 是很精确。 3 过程间非流敏感上下文敏感的逃逸分析。b l a n c h e t ( 19 9 9 ，2 0 0 3 ) 【4 】【5 1 提 出了一个建市在s s a 格式( s t a t i cs i n g i e a s s i g n m e n tf o r m ) 的此类分析。 w a n ge ta l ( 2 0 0 6 ) 吲在i n t e l 的o r p ( o p e nr u n t i m ep l a t f o r m ) 上实现 了一个逃逸分析框架并运用于同步消除优化中，j i ：提出了一些传播算 法，如b o t t o m u p 和u p d o w n 算法等，用于在对象上传播逃逸状态。这 类算法精确度比较好也较为复杂，但是对于数组、循环等分析还不够。 在逃逸分析中，经常会运用一些程序抽象( p r o g r a ma b s t r a c t ) 来表征j a v a 程序中一个方法，并以此为基础进行分析。在静态逃逸分析中，较为典犁的程 序抽象有： 1 c h o ie ta l ( 1 9 9 9 ，2 0 0 3 ) 【8 】f 9 1 的逃逸分析算法引入了一个称为连接图 ( c o n n e c t i o ng r a p h ) 的程序抽象用以确市对象、对象引用之间的可达性。 逃逸分析被映射到连接图上的可到达问题。连接图可以很容易地为每个 方法建立相关结构，歹i ：能在不同的方法调用上下文中被利用以避免重复 计算。 2 w a n ge ta i ( 2 0 0 6 ) 【3 2 】的逃逸分析算法引入一个称为方法概要( m e t h o d s u m m a r y ) 的程序抽象来进行逃逸分析，其不仅描述了方法中各个对象、 变量的信息，还描述了方法内凋用点( c a l l e es t u b ) 信息等。算法则对 每个j a v a 方法所刘应的方法概要结构进行过程间的分析以及刘象的逃 逸状态计算。 3 s a l c i a n ue ta l ( 2 0 0 i ) 【2 7 】提出的算法结合了逃逸分析和指针分析，并通 过一个称为并行交互图( p a r a l l e li n t e r a c t i o ng r a p h ) 的程序抽象获取线程 间交互信息，并提取精确的对象逃逸信息和指向信息等。 4 第l 章绪沦 1 2 1 2 动态逃逸分析( 运行时分析) j a v a 程序支持动态类载入( d y n a m i cc i a s sl o a d i n g ) 、本地方法调用( n a t i v e i n v o c a t i o n ) 和反射机制( r e f l e c t i o n ) 等特性，这些特征将打破“封闭世界”的 约定，使得真实的j a v a 程序运行在一个“开放世界( o p e nw b r l d ) ”中，因此纯 粹的静态逃逸分析不能有效地处理这些问题。动态的逃逸分析可以收集运行时 的各类信息，并根据收集到的信息执行逃逸分析。 在动态编译器上下文中，k o t z m a n ne ta i ( 2 0 0 5 ) 【1 9 】提出了一个新的过程内 和过程间算法用丁- 动态编译上下文( 支持处理动态类装载和反优化 ( d e o p t i m i z a t i o n ) ) 中的逃逸分析，并在s u n 的m i c r o s y s t e m 平台上的j a v ah o t s p o t 用户编译器巾实现；而n i s h i y a m a ( 2 0 0 4 ) 【2 3j 则将基于读障栅( r e a d b a r r i e 卜b a s e d ) 的动态逃逸分析用于减少运行时的数据竞争检测，并在s u n 的m i c r o s y s t e m 平台 上的j a v ah o t s p o t 虚拟机中实现。动态分析较之于静态分析更为复杂且难于实 现，却更为精确。l e ee ta l ( 2 0 0 6 ) 【2 l 】实现了一个两阶段的线程逃逸分析：0 f 1 1 i n e 阶段和0 n l i n e 阶段，自，j 者实现的足静念的逃逸分析，后者则实现运行时的分析， 该分析主要运用于分析多线程程序。 在动态的逃逸分析中，也利用了一些程序抽象来辅助程序分析。w h a l e ye ta i ( 1 9 9 9 ) 【3 3 】和v i v i e ne ta l ( 2 0 0 1 ) 提出了一个称为指向一逃逸图( p o i n t t oe s c a p e g r a p h ) 的程序抽象，并基于此结构进行逃逸分析算法的设计。该程序抽象不仅 描述了局部变量和对象巾的域如何引用其它的对象，还包括逃逸信息，而其上 的算法结合了逃逸分析和指针分析。w h a l e ye ta i ( 1 9 9 9 ) i 圳的算法被设计成为 可以分析完整的或不完整的程序的任意区域中的对象是否逃逸出这个区域，因 此适合分析动态载入的程序。v i v i e ne ta l ( 2 0 0 1 ) 【3 l 】的算法则结合前一次分析的 实验数据、本次分析的分析结果以及前一次运行的反馈信息来较为精确地估计 运行中对象的生命期行为。 在国内的相关工作巾，史晓华等( 2 0 0 8 ) 【l 】贝0 针对于“开放世界”逃逸分析 将面临的许多重要的问题，提出了一个新的逃逸分析架构，以正确、全面地捕 捉动态载入的类和方法并分析它们与原有程序的关系，有效地控制算法的复杂 性，保证即时编译器的重新分析时间不会过长。该分析架构在i n t e l 的开放式j a v a 虚拟机系统0 r p 中实现。 5 第l 童绪沦 1 2 1 3 逃逸分析的形式化证明 也有一些研究t 作致力丁形式化证明逃逸分析的正确性。b l a n c h e t ( 1 9 9 8 ) 【3 】针对函数式语言上的逃逸分析，从语言的语法上着手进行止确性证明。b l a n c h e t ( 1 9 9 9 ，2 0 0 3 ) 【4 】【5 1 在完全的j a v a 语言( f u l lj a v a t ml a n g u a g e ) 上实现逃逸分析 的同时，形式化地描述了分析过程并证明其正确性。针对j a v a 这类面向对象语 言，h i l le ta l ( 2 0 0 2 a ) 【1 5 】从实际的逃逸分析计算过程中形式化抽象了一个在具 体状态( c o n c r e t es t a t e ) 下的逃逸属性( e s c a p ep r o p e r t y ) 作为分析的一个抽象 解释( a b s t r a c ti n t e r p r e t a t j o n ) ，并描述了一种方法，使得在给定的一组面向对象 程序具体执行操作( c o n c r e t eo p e r a t i o n ) 的情况卜，可以通过这个逃逸属性推导 出最优的抽象操作( a b s t r a c to p e r a t i o n ) 。同年，h i l le ta l ( 2 0 0 2 b ) 【j 又提出了 该逃逸属性的另一个更为具体的重定义( r e f i n e m e n t ) ，并在该重定义的逃逸属性 基础上引导出更为精确的逃逸分析。而h 1 | e ta i ( 2 0 0 6 ) i l 7j 则致力于对这两个逃 逸属性所引导出来的结果进行形工i = 化的正确性证明。 1 2 1 4 逃逸分析的应用 为了达到更好的分析效果或获得更好的分析性能，有些分析 二作往往将逃 逸分析与其它的分析相结合，如：w h a l e ye ta l ( 1 9 9 9 ) 、v i v i e ne ta l ( 2 0 0 1 ) 【3 1 1 和s a l c i a n ue t a l ( 2 0 0 1 ) 【2 7 1 提出了合并了逃逸分析与指针分析的算法，以获得 更为精确的分析结果；c h e r e me ta i ( 2 0 0 7 b ) 】提出了一种结合了逃逸分析与效 果分析( e 虢c t a n a l y s i s ) 的算法，以获取描述j a v a 程序堆效果( h e a pe 行e c t s ) 的轻量级方法描述( l i g h t w e i 曲tm e t h o ds u m m a r y ) 。 逃逸分析可以有许多种优化应用，它除了口j 以用丁对象内存空间管理优化 工作之外，还可以用于其它诸如多线程等方面的优化工作。在逃逸分析的这些 优化应用工作当中，栈上分配( s t a c k a l i o c a t i o n ) 9 。3 2 0 2 _ 3 1 3 3 埽口不必要同步的 消除( s y n c h r o n i z a t i o ne l i m i n a t i o n ) 【l 2 4 ，6 8 ，9 乳2 1 2 7 ，3 2 ，3 3 1 是逃逸分析的两个弘要的应 用。在其它的优化工作方面，n i s h i y a m a ( 2 0 0 4 ) 和l e ee ta l ( 2 0 0 6 ) 【2 。】应用 逃逸分析检测多线程间的数据竞争；s o u t e r ( 2 0 0 2 ) 【2 9 】提出了一种利用逃逸分析 进行面向对象软件测试与再测试技术。 1 2 2 对象内存空间管理优化应用 6 针对于j a v a 语言，对象内存空间管理模式包括对象分配模式和对象叫收模 第l 童绪论 式两类，相应的优化应用也有对象分配模式优化和对象回收模式优化荫类。 1 2 2 1 对象分配模式优化 j a v a 语言中对象是在堆中进行分配的。对象分配模式的优化应用主要集中 在如何改变对象的分配模式，从而有效地减少在堆中分配的对象。有多种优化 方式可以达到该目的：对象的栈上分配( s t a c ka l l o c a t i o n ) 、基于区域的对象分 配方式( r e g i o n _ b a s e da 1 1 0 c a t i o n ) ，对象的标量替换( s c a l a rr e p l a c e m e n t ) 等， 它们同时也分别是逃逸分析的一种优化应用。 对象的栈上分配方式，利用程序分析技术获得对象的生命期特征，将一部 分对象分配在方法的运行栈中，从而减少堆中分配的对象。c h o ie ta l ( 1 9 9 9 ，2 0 0 3 ) 嘲【9 】、w h a l e ye ta l ( 1 9 9 9 ) 【3 3 】等许多t 作分别描述了各类静态或动态的逃逸分析 算法如何实现对象的栈上分配优化。i 刊时，该优化应用也是逃逸分析最主要的 优化应用之一。 基于区域的对象分配方式，引入了一种新型的对象分配模式，使得一部分 对象分配在方法或线程所对应的区域( r e g i o n ) 中，从而减少堆中分配的对象。 s a i c i a n ue ta l ( 2 0 0 1 ) 【2 7 】将逃逸分析和指针分析应用于该分配模式的优化； s a l a g n a ce ta l ( 2 0 0 5 ) 【2 8 】通过结合逃逸分析与基丁变量的指针分析，实现了一个 基于该分配模式的原型系统。 对象的标量替换，根据对象的生命期特征，发现程序中可以被替换为标量 的对象，将这部分对象转换为在方法运行栈中分配的普通数据。k o t z m a n ne ta i ( 2 0 0 5 。2 0 0 7 ) 【1 9 1 【2 0 1 都提到了在逃逸分析的辅助下，标量替换可以承担g c 的一 部分负担，但其并不是近年来对象生命期分析方式的优化应用的核心。 1 2 2 2 对象回收模式优化 众所周知，g c 的自动内存同收方式是j a v a 语言区别于c + + 等其它面向对象 语言的一大特征，但同时也导致j a v a 程序的运行效率相比于c + + 较低。m c d o w e i l ( 1 9 9 8 ) 【2 2 通过对虚拟机的插桩测试，以提供的测试数据表明，在减少g c 处 理的垃圾对象方面的优化工作具有很大的价值。 对于对象的回收模式的优化，大部分工作主要集中在如何有效地减少g c 管 理的对象，且并不改变j a v a 程序埘象管理对程序员的透明性。在这些优化工作 当中，显式回收辅助g c 的自动回收方式( e x p i i c i tm e m o 呵r e c l a m a t i o na s s i s t e d 7 第1 章绪沦 a u t o m a t i cm e m o r yr e c l a m a t i o n ) 是一种新式的埘象回收模式，它可以有效地减 少g c 处理的垃圾对象。本文即将阐述的j i t 辅助g c 优化应用是该新式的刘象 回收模式的种，其特点在于程序分析部分的实现是存即时编译器中进行的。 g u y e re ta i ( 2 0 0 6 ) i m j 通过一种称为f r e e m e 的分析实现一种显式内存回收 工作，以辅助g c 的自动内存同收工作。在他们的工作中，f r e e m e 分析首先进 行一种轻量级的活跃信息指针分析以获得短生命期的死广对象，并对源程序捅 入对象的回收操作；而g c 也提供对这类对象的回收操作的运行时支持。 c h e r e me ta i ( 2 0 0 7 a ) 【1 0 j 也是利用对源程序自动插入对象的回收操作，实现 部分对象的显式内存回收工作。它使用了一种唯一性推导算法( u n i q u e n e s s i n 佗r e n c ea i g o r i t h m ) 对源程序进行分析，识别持有单一引用的变量和对象域， 并展开过程内及过程间分析计算全局的唯一性依赖关系( u n i q u e n e s s d e p e n d e n c y ) ，最后利用这些唯一性信息指导对源程序的捅桩工作。 重2 3 分析优化框架 程序分析及程序优化工作实现在编译器中，并根据编译器的不l - j 分析优化 框架特征，有着不同的实现。本文调研了两个比较重要的j a v a 编译分析优化框 架：s 0 0 t 和a p a c h eh a r m o n y 项目中的即时编译器( j u s t i n t i m ec o mp i l e r ，简称 j i t ) 。 由m c g i l l 大学的s a b l e 研究组研制的s o o t ( r 勾ae ta i ，1 9 9 9 ) 【2 5 】，提供了一 种可扩展的编译分析优化框架，并提供了多种中间表示以适应不同的分析优化 需求。其框架结构清晰，源码组织有条不紊，且本身是由j a v a 晤言实现的，可 以非常方便地扩展字节码上的分析、变换、优化、反编译以及注解等不同的需 求。 而由a p a c h e 软件基金会提供的开源j a v as e 平台a p a c h eh a r m o n y ( t h e a p a c h es o r w a r ef o u n d a t i o n ，2 0 0 3 2 0 0 8 ) 【3 0 】上的即时编译器( j u s t i n t i m e c o m p i l e r ，简称j i t ) ，提供了一种流水线结构的编译分析优化框架，并提供了两 级中间表示以保持分析优化的实现具有平台无关件。其用c + + 浯言实现，且通 过命令行选项和配置文件实现高度列配置性，并支持热点方法( h o t s o p t s ) 的重 编译。 由于s 0 0 t 仅仅是一个静态的编泽优化框架抑或是一个静态j a v a 编译器，它 8 第1 章绪沦 并不支持热点方法的重编泽，不属于即时编泽器的范畴。在进行了两种编泽分 析优化框架的比较之后，本文阐述的对象生命期分析及其优化应用则选择基于 a p a c h eh a r m o n y 项目中的j i t 即时编译器进行实现。 1 3 研究内容 根据上节中介绍的围绕对象生命期分析及对象管理优化应用展开的相关研 究工作及其分析，本文在充分调研的同时，提出了一种基于逃逸分析的对象生 命期分析方法，并在j a v a 即时编译器( j u s t i n t i m ec o mp i i e r ，简称j i t ) 端实 现该分析以及相应的代码变换步骤，旨在为j i t 辅助g c ( j l t - a s s i s t e dg c ) 优 化应用工作提供前端的支持。 由1 1 节中图1 1 中可以得知，j i t 辅助g c 优化工作可大致划分为两部分： 分析变换部分( j i t 前端) 和g c 部分( g c 后端) 。分析变换部分需执行对象 生命期分析以及完成相应的代码优化变换：而g c 部分设计对象的分配与回收策 略并提供相应的运行时支持接口。 围绕陔优化工作，本文主要致力于研究j i t 前端的分析变换部分，而g c 后 端部分由本研究小组另一位成员炅廷鹏进行设计与实现，并在其硕士论文巾详 加描述。因此，本文重点探讨并完成了以下工作： 1 提出一种基于逃逸分析的生命期分析算法，以获得比逃逸分析更为精确 的对象生命期信息 对象生命期分析策略及算法是实现j i t 辅助g c 优化工作的关键之一。存上 节中相关研究工作的介绍与分析中，可以看出，人部分影f 究上作采用逃逸分析 作为获取对象生命期信息的个重要手段，也有相当部分的研究工作结合逃逸 分析和其它的分析以获得更为精确的对象生命期信息。为更好地支持该优化工 作的进行，本文提出了一种基于逃逸分析的、增量式、过程问的对象生命期分 析方法，并结合属性( p r o p e n y ) 的过程内与过程间的传播算法，识别对象的逃 逸状态并分析非全局对象的生命期。 2 扩展j i t 高级中间表示指令集合及其相应的解析操作，以支持在j l t 中 进行的代码变换 为及时地释放部分可以回收的对象空间，在j i t 的高级中问表示的指令集上 增加若干指令，以处理这类显式回收对象的分配与回收操作。在低级中间表示 9 第1 章绪论 层甚至更底层实现对这砦扩展指令的解析。 3 利用分析结果，设计并实现代码插桩变换策略，以保证对象及时地被释 放 利用对象生命期分析提供的分析结果，实现基于高级中间表示的代码插桩 变换，旨在适当的程序点处插入死亡对缘的同收指令，保证变换后的程序代码 最终得以执行，并能在执行过程中适时地释放可以回收的对象。 4 结合j i t 流水线体系结构特点，以优化遍的形式规划生命期分析与代码 优化变换的实现 j i t 以优化遍的形式实现中间代码上的每一类分析与优化，并通过流水线的 编译框架结合配置文件选择性地调用执行优化遍。本文中的对象生命期分析和 代码变换分别以相关联的两个优化遍的形式实现，爿：通过配置文件的设置保证 即时编译器在适当的时候调用执行。j l t 端分析与代码变换结合g c 端运行时支 持，实现j i t 辅助g c 原型系统。 1 4 论文组织 本文的其余部分是这样组织的： 第2 章介绍后文中用到的基本概念。 第3 章描述一种基于逃逸分析的对象生命期分析方法和策略。 第4 章讨论第3 章中所提出的算法在即时编译器中的实现，以及在实现过 程中需要考虑的一些问题及相应的解决策略。 第5 章介绍了对象生命期分析的一个优化应用：j i t 辅助g c 的实现，并重 点介绍该优化应用的前端实现部分。 第6 章给出了实验结果及分析。 第7 章对全文进行总结。 l o 第2 童基本概念 第2 章基本概念 本章介绍对象生命期分析涉及到的一些背景知识，包括程序分析技术的分 类和逃逸分析的基本概念。我们调研和分析了两种编译分析优化框架：s o o t 和 a p a c h eh a m o n y 中的即时编译器，同时对二者进行了比较，并选取后者作为本 文中提出的分析和优化应用的实现平台。 2 1 程序分析技术的分类 在编译运行系统中进行的程序分析技术多种多样，并以不同的角度可以有 不同的分类。 1 根据是否考虑控制流，程序分析技术可以分为流敏感( f l o ws e n s i t i v e ) 和非流敏感( f l o wi n s e n s i t i v e ) 两类。程序r f lm 现的控制流有多种情况， 除了代码顺次执行的普通摔制流之外，还有循环、分支( 条件跳转、无 条件跳转) 等控制流存在。流敏感的分析会考虑对循环、分支等特殊控 制流情况的处理，而后者的分析将忽略这些特殊的控制流情况。 2 根据是否考虑调用上下文，可以分为上下文敏感( c o n t e x ts e n s i t i v e ) 和 上下文非敏感( c o n t e x ti n s e n s i t i v e ) 两类。前者在分析时会结合当前方 法的调用匕下文的一些相关信息进行该方法的分析，而后者在分析时只 关注该方法本身的代码，而不会考虑方法的调用上下文。 3 根据分析是否考虑过程之间的影响可以分为过程问( i n t e r p r o c e d u r a i ) 和 过程内( i n t r a p r o c e d u r a l ) 两类。过程问的分