（计算机软件与理论专业论文）即时编译器辅助的对象回收和空间复用.pdf

摘要 摘要 j a v a 语言采用垃圾收集器( g a r b a g ec o l l e c t o r ，g c ) 在堆上处理j a v a 应用程序 的对象分配请求并自动管理对象的回收。g c 减轻了程序员管理内存的负担，但 是需要耗费大量的时空开销识别堆中哪些对象是死亡的，从而成为影响j a v a 虚 拟机性能的重要因素之一。 即时编译器( j u s t - i n t i m ec o m p i l e r ，j i a 3 辅助的垃圾收集技术通过由j i t 分析 应用程序并在其中安插显式释放对象甚至是特殊的对象分配等指令，辅助g c 改 进对象的回收与分配，是减轻g c 自动回收负担的一种有效途径。本课题组围绕 着即时编译器辅助的垃圾收集技术开展研究，前期已初步实现一个改进对象回收 的原型系统，该系统只能处理单线程和规模较小的程序，并且其中的对象生命期 分析算法和插桩算法的性能有待改善。本文致力于改进原有系统，重点提出一种 新的对象生命期分析和插桩算法，探讨完成以下工作： l 、提出一种结合活跃变量分析和指针分析的对象生命期分析算法，以获得 更为精确的对象生命期信息。这种算法是过程间的、流敏感的、上下文敏感的， 它主要分析识别应用程序中的非全局对象及其死亡位置。 2 、基于对象生命期分析结果，提出一种在程序中安插显式内存释放指令的 插桩算法。算法基于控制流中的支配关系，通过提供不同的插桩策略来保证插桩 的j 下确性和灵活性，能主动识别和释放已死亡的对象及其域所引用的内存空间。 3 、设计一种能够输出每条内存释放指令收益的日志系统。该日志系统不仅 能获得垃圾收集和对象显式回收的信息，还能获得每条内存释放指令的收益信 息，从而为下步丌展对象分配模式上的优化奠定了基础。 4 、在原有的即时编译器辅助的垃圾收集系统上实现了上述工作。其中对象 生命期分析和插桩算法以一个优化遍的形式实现。改进后的系统比原有系统更高 效，且能够处理多线程和规模较大程序。，实验结果表明改进后的系统能够回收大 量内存空间，减轻g c 负担，提高内存剥用率和j a v a 应用程序的执行效率。 关键词：对象生命期分析插桩算法显式回收即时编译器辅助的垃圾收集 a b s t r a c t a b s t r a c t j a v ap r o g r a m m i n gl a n g u a g eu s e sg a r b a g ec o l l e c t o rt od e a l 、 ，i t l lt h eo b j e c t a l l o c a t i o n r e q u e s t s o f j a v a a p p l i c a t i o n sa n da u t o m a t i c a l l ym a n a g e t h e o b j e c t r e c l a m a t i o ni nh e a p g a r b a g ec o l l e c t o rc a nr e d u c ep r o g r a m m e re f f o r t ，b u ti tc o s t sa m a s so ft i m ea n ds p a c et oi d e n t i f yd e a do b j e c t si nh e a p ，s oi tb e c o m e so n eo ft h em o s t i m p o r t a n tf a c t o r st h a ti n f l u e n c et h ej a v av i r t u a lm a c h i n ep e r f o r m a n c e a ne f f e c t i v ea p p r o a c ht or e d u c eg a r b a g ec o l l e c t o ra u t o m a t i cr e c l a m a t i o ne f f o r ti s j u s t i n t i m ec o m p i l e ra s s i s t e dg a r b a g ec o l l e c t i o n ( j i t - a s s i s t e dg c ) t h a ti st os a y , j i t c o m p i l e ra n a l y s e st h ea p p l i c a t i o n st oi n s t r u m e n tt h ee x p l i c i t ”f r e e ”i n s t r u c t i o n sa n d e v e nt h es p e c i a lo b j e c ta l l o c a t i o ni n s t r u c t i o n st oa s s i s tg a r b a g ec o l l e c t o ri ni m p r o v i n g t h eo b j e c ta l l o c a t i o na n dr e c l a m a t i o n o u rl a bh a dd e v e l o p e dt h es t u d i e so n j i t - a s s i s t e dg ca n di m p l e m e n t e dap r o t o t y p es y s t e mf o c u s e so ni m p r o v i n go b j e c t r e c l a m a t i o nb e f o r e t h ef o r m e rs y s t e m ，h o w e v e r c a l lo n l yd e a l 诵t i lt h es i n g l et h r e a d a n ds m a l l s c a l e a p p l i c a t i o n s ，t h ep e r f o r m a n c eo fo b j e c t l i f e t i m e a n a l y s i s a n d i n s t r u m e n ta l g o r i t h mi nt h ef o r m e rs y s t e mi sl o w 。i no r d e rt oi m p r o v et h ef o r m e r s y s t e m ，n e wo b j e c tl i f e t i m ea n a l y s i sa n di n s t r u m e n ta l g o r i t h m sa r ep r e s e n t e di nt h i s p a p e r t h i sp a p e rm a i n l yd e p i c t sa n d d i s c u s s e st h ef o l l o w i n gw o r k s ： 1 、p r e s e n t sa no b j e c tl i f e t i m ea n a l y s i sa l g o r i t h mw h i c hc o m b i n e sl i v e v a r i a b l ea n a l y s i sa n dp o i n t s t o a n a l y s i s ，t og e tm o r ep r e c i s eo b j e c tl i f e t i m e i n f o r m a t i o n t h eo b j e c tl i f e t i m ea l g o r i t h mi si n t e r - m e t h o d ，f l o ws e n s i t i v ea n dc o n t e x t s e n s i t i v e ，u s e dt oi n d e n t i f yt h en o n - g l o b a lo b j e c t sa n dt h e i rd e a dl o c a t i o n s 2 、b a s e do nt h er e s u l t so ft h eo b j e c tl i f e t i m ea n a l y s i s ，p r e s e n t sai n s t r u m e n t a l g o r i t h mt oi n s e r tt h ee x p l i c i t f r e e i n s t r u c t i o n si na p p l i c a t i o n s t h ei n s t r u m e n t a l g o r i t h mb a s e s o nt h ed o m i n a t i o nr e l a t i o n si nt h ec o n t r o lf l o wa n dv a r i o u s i n s t r u m e n t i n g s t r a t e g i e sa r ep r e s e n t e d t oe n s u r et h ev a l i d i t ya n df l e x i b i l i t yo f i n s t r u m e n t a t i o n m o r e o v e r , i tc a ni n i t i a t i v e l yi n d e n t i f ya n df r e et h em e m o r ys p a c e s t h a tr e f e r e n c e db yo b j e c t so rt h e i rf i e l d s 3 、d e s i g n sal o gs y s t e m t h el o gs y s t e mn o to n l yc a ng a i nt h ei n f o r m a t i o na b o u t g a r b a g ec o l l e c t i o na n do b j e c te x p l i c i tr e c l a m a t i o n ，b u ta l s oc a ng a i nt h ei n f o r m a t i o n o fe a c he x p l i c i t f r e e ”i n s t r u c t i o ni n c o m e ，l a i dt h ef o u n d a t i o nf o rt h en e x ts t u d yo n t h eo b j e c ta l l o c a t i o no p t i m i z a t i o n 4 、b a s e do nt h ef r a m e w o r ko ft h ef o r m e rj i t - a s s i s t e dg cs y s t e m ， h l 1 m p l e m e n t st h ea b o v ew o r k t h eo b j e c tl i f e t i m e a n a l y s i sa n dh i ri n s 加l m e m t r a n s 士o h n a t l o na rei m p l e m e n t e di nt h ef o r mo fa no p t i m i z a t i o np a s s t h e i m p r o v i n g j i t - a s s i s t e dg cs y s t e mc a nd e a lw i t ht h em u l t i p l et h r e a d s a n dl a r g e - s c a l ea p p l i c a t i o i l s a n dm o r ee f f i c i e n tt h a nt h ef o r m e rs y s t e m e x p e r i m e n t a l r e s u l t ss h o wt h a tt h e l m p r o v i n gj i t - a s s i s t e dg cs y s t e mc a nr e c l a i mp l e n t i f u lm e m o r y s p a c e s ，r e d u c eg c e n o n ， 1 m p r o v et h em e m o r yu t i l i t ya n dt h ep e r f o r m a n c eo fj a v a a p p l i c a t i o n s e f f i c i e n t l y k e yw o r d s ：o b j e c tl i f e t i m e a l l a l y s i s ，i n s t r u m e n ta l g o r i t h m ，e x p l i c i tr e c l a m a t i o n ， j u s t i n - t i m ec o m p i l e ra s s i s t e dg a r b a g ec o l l e c t i o n l v 中国科学技术大学学位论文原创性和授权使用声明 本人声明所呈交的学位论文，是本人在导师指导下进行研究工作 所取得的成果。除已特别加以标注和致谢的地方外，论文中不包含任 何他人已经发表或撰写过的研究成果。与我一同工作的同志对本研究 所做的贡献均已在论文中作了明确的说明。 本人授权中国科学技术大学拥有学位论文的部分使用权，即：学 校有权按有关规定向国家有关部门或机构送交论文的复印件和电子 版，允许论文被查阅和借阅，可以将学位论文编入有关数据库进行检 索，可以采用影印、缩印或扫描等复制手段保存、汇编学位论文。 保密的学位论文在解密后也遵守此规定。 作者魏五! 三唧 i 。1 年s 叫日 1 第1 章绪论 第1 章绪论 j a v a 语言采用垃圾收集器( g a r b a g ec o l l e c t o r ，g c ) 进行内存管理。g c 采用自 动的内存管理技术在堆上管理对象的分配与回收，它的性能是影响j a v a 虚拟机 ( j a v a v i r t u a lm a c h i n e ，j v m ) 性能的重要因素之一。 为了降低g c 管理内存的时空开销，目前的研究工作主要集中在两方面：一 是改进g c 本身的算法；二是编译器支持的内存管理。而对象生命期分析( o b j e c t l i f e t i m ea n a l y s i s ) 是编译器支持的内存管理技术的基础，它为优化工作提供必要 的程序对象生命期相关信息。本课题组开展了即时编译器( j u s t - i n - t i m ec o m p i l e r ， j i t ) 辅助的内存优化技术的研究工作，前期已初步实现了即时编译器辅助的垃圾 收集( j i t 辅助的g c ) 系统，侧重在对象回收模式上进行优化，能处理单线程和规 模较小的程序，但在对象生命期分析算法和插桩算法上均存在不足，系统运行效 率较低。本文针对前期工作的不足，重点提出一种对象生命期分析技术和插桩算 法，并将分析结果应用到j i t 辅助的g c 优化中。 本章首先介绍了j i t 辅助的g c 的研究背景，接着对当今国内外研究的相关 工作、本课题组已有工作做出分析和比较，最后给出本文的研究内容。 1 1 问题描述 c 与c h 这类语言采用显式的内存管理技术，主要特点是由程序员显式给出 动态内存的分配和释放请求，由系统来对这些请求进行响应处理。这种内存管理 方法具有效率高的特点，但是会因为程序员的不当操作导致很多问题。例如程序 员忘记释放不再使用的内存，这将引起内存泄漏；或者过早释放了仍然在使用的 内存，这将引起悬空引用：或者不小心将同一块内存释放了两次，会导致运行时 错误。 j a v a 这类语言采用垃圾收集器在堆上自动的管理对象的分配与回收。当堆空 间不足时，g c 自动启动垃圾收集来识别并回收堆中的死亡对象。由于内存空间 的回收工作与程序员无关，所以这大大地减轻了程序员的编程负担，也降低了程 序中与内存相关的错误发生几率；但是g c 也为整个系统运行带来了额外的开 销，是影响j a v a 虚拟机性能的重要因素之一。一般地，自动内存管理也称作隐 式内存管理。 j i t 辅助的g c 是j a v a 语言上一种关于内存管理的优化工作，不仅可以在对 象的回收模式上进行优化，还可以在对象的分配模式上进行优化。图1 1 给出了 第1 章绪论 j i t 辅助的g c 优化工作的框架，做法是由j i t 分析应用程序中对象的生命期特 征，以识别确定其中的死亡对象及位置，并在程序中合适的位置安插显式释放内 存的指令来主动通知g c 回收内存；g c 接到显式内存释放请求后，不仅可以立 即回收内存空间还可以采取某些策略对这些空间进行有效重用，从而减轻了g c 自动回收内存的负担，提高j a v a 应用程序的执行效率。当前本课题组的研究工 作集中在对象显式回收优化上，在对象分配上只进行了部分改进，下一步本课题 组将开展对象分配优化的研究工作。 r、 ，、 垃圾收集器 g c 虚 拟 机 广 蓍 内o - - 核 v m c o r e 薹 p 图1 1j i t 辅助的g c 优化工作大致框架 由于g c 有大量的时空开销消耗在识别堆中哪些对象是死亡的，因此j i t 辅 助的g c 技术能够减轻g c 的负担，提高j a v a 应用程序的执行效率，对实时系统 和内存受限的系统具有重要的意义。j i t 辅助的g c 的关键研究问题集中在对象 的生命期分析、显式内存释放等指令的插桩变换、g c 对对象显式回收和分配优 化的支持这三个方面。已有的研究工作在对象生命期分析和插桩变换上均有不 足：大部分基于逃逸分析的对象生命期分析算法可以识别对象能否被分配在堆以 外的空间或被显式回收，但是在确定对象的生命期上精度不够，不能很好地指导 显式内存回收优化工作；对于显式内存释放等指令的插桩，尚没有一个很好的算 法来应对应用程序中的多种情况，很多情况对分析出的死亡对象无法插桩显式内 存释放指令。 本文研究的重要问题就是设计一种对象生命期分析算法和插桩算法，使得不 仅能够得到精确的对象生命期信息，还能够根据对象死亡信息正确、灵活、有效 地插桩显式内存释放指令。此外，为了进一步地开展在对象分配上的优化工作， 本文研究的另一个问题就是如何设计一个日志系统，使得不仅能够获得垃圾收集 内部行为和对象显式回收的信息，还能够获得详细的每条内存释放指令收益信 息，为下一步的研究工作奠定基础。 2 第1 章绪论 1 2 相关工作 由于内存空间的限制，内存管理的优化工作一直是研究的热点。2 0 世纪6 0 年代，第一个应用于编程语言l i s p 的垃圾收集器【5 】诞生，自此以后研究人员对垃 圾收集算法做了大量的研究，提出了很多垃圾收集算法1 6 1 0 , 1 2 。而编译器支持的 内存管理技术是近些年新的研究方向，它的做法是通过程序分析获得应用程序中 对象的特征，从而进行一系列优化，如对象的栈上分配( s t a c k a l l o c a t i o n ) 【2 ，g - - 2 0 、 基于区域的对象分配方式( r e g i o n b a s e da l l o c a t i o n ) 口h 引、编译器支持的对象显式 回收 2 4 - 2 6 1 。 1 2 1 垃圾收集技术的发展 标记清扫算法是计算机史上一个用于内存自动管理的算法，由m c c a r t h y 在 1 9 6 0 年提出【5 j 并成功地应用于l i s p 语言，后来的很多垃圾收集算法都使用了该 技术【7 8 】。标记清扫算法是一种基于跟踪的垃圾收集技术，包含标记和清扫两个 阶段。标记阶段从根集( r o o ts e t ) 中的对象节点出发，沿着对象的引用域遍历整 个堆空间，所有可达的对象被认为是活对象，不可达的对象被认为是死对象；清 扫阶段回收死亡对象占用的空间，用于满足新的分配需求。该算法的好处是只需 要操作指针，不需要移动对象，很适合用来管理大对象，且可以处理环形引用的 对象。但是对象分配的无序性也降低了空间上的访问局部性，且会逐渐导致系统 堆的碎片化。 引用计数算法由c o l l i n s 在1 9 6 0 年提出【6 j ，它的基本思想是为每个对象计算 指向它的引用的次数，当一个对象的引用计数为0 时，表明该对象不可能再被访 问到，即已经死亡，可以将它占用的内存空间归还给垃圾收集器重新分配出去。 该算法实现简单，但不能处理对象间的环形引用。 复制算法由m i n s k y 在1 9 6 3 年提t b g l 。该算法将堆空间分成两个大小相等半 区( s e m i s p a c e ) ，一个包含现有的数据，一个包含已经废弃的数据。当垃圾收集 运行时，活对象从当前区拷贝到另一半区，收集完成时，另一半区只包含活对象， “垃圾 被留下来，因而另一半区成为一个新的活跃半区，内存分配从新的活跃 半区开始分配。它的优点是消除了堆碎片、分配成本低、空间局部性比较好。由 于每次只能使用其中的一个半区，故空问的利用率低，且对于那些生命期长的对 象需要来回复制。 标记紧压( m a r k c o m p a c t ) 算法是标记清除算法和复制算法的有机结合，最 早由h a r t 在1 9 6 4 年提出l l0 1 。该算法首先同标记清除算法一样对堆中的对象进 行标记，然后将堆中的活对象紧压到堆的- 1 。标记紧压算法的总体执行效率 3 第1 章绪论 高于标记清除算法，又不像复制算法那样需要牺牲一半的存储空间，还解决了 堆中的碎片问题。之后，a b u a i a d h 等人又提出了一种更高效的紧压算法l l l j ，只 需要三次遍历即可完成紧压过程，且算法的空间开销很小。 分代垃圾收集算法是由l i e b e r m a n 等人在1 9 8 3 年提出【l2 】的一种基于对象生 命期特征的垃圾收集算法，它基于的假设是大部分对象在分配后很短的时间内死 亡，只有一小部分对象会活得很久。它将堆空间被分成两个或多个区域，这些区 域被称为代( g e n e r a t i o n ) ，将对象按年龄分别存放到堆的不同代中，对不同的代可 以采用不同的垃圾收集策略。分代垃圾收集器的目的是利用较短的时间收集死亡 率较高的空间，从而得到较高的收集效率。由于主要是以收集年轻的代为主，分 代垃圾收集器同时也有效地降低了每次收集的平均暂停时间。 传统的垃圾收集算法都是需要先暂停应用程序的执行，等待垃圾收集算法完 成后，应用程序再继续执行。当垃圾收集执行的时间过长，将会严重影响用户程 序的执行效率，d i j k s t m 提出了并发的垃圾收集算法i l 引。所谓并发是指应用程序 的执行和垃圾收集算法的执行可以同时进行，这样垃圾收集的过程可以在应用程 。序执行过程中完成，减少了应用程序执行的停顿时间，从而提高应用程序的执行 效率。这几年又陆续出现这方面的相关工作，主要有【1 4 1 引。 g c 管理的对象可以根据其大小分为普通对象和大对象。其中大对象的管理 具有移动成本高，个数相对少，无法在事先规定大小的块中进行分配等特点。一 些垃圾收集器【i 7 1 将大对象的管理和普通对象分开管理，使用一个专门的大对 象空f i l l ( l a r g eo b j e c ts p a c e ，l o s ) 来管理大对象。堆空间划分成l o s 与非l o s ， 当其中一方没有空闲空问时就要发生垃圾收集，而且一般对l o s 和与非l o s 空 间的收集分丌进行。因此l o s 的引入会降低堆的利用率，并影响并行执行的可 扩展性。也有一些垃圾收集器【7 8 l 不引入l o s ，通常采用非移动算法，如标记 清扫算法，管理整个堆，避免了引入l o s 带来的缺点。 1 2 2 编译器辅助的内存管理优化技术 编译器辅助的内存管理优化技术的一般思想是：编译器通过对象生命期分析 技术分析出应用程序中对象的特征，然后将分析结果应用到对象的分配与回收 中。 在面向对象程序设计语言中，对象生命期分析旨在获得运行时动态分配的对 象在整个程序中与其生命期相关的一些信息。在国内外丌展的与对象生命期分析 相关工作中，大部分采用逃逸分析( e s c a p ea n a l y s i s ) 技术来分析对象生命期状态 的信息。还有部分工作采用指针分析、或逃逸分析与指针分析褶结合的技术来获 得对象的生命期状态。 4 第1 章绪论 逃逸分析技术 逃逸分析用来分析程序中的对象是否逃逸出某个上下文( 方法或线程) ，作为 一种过程间的数据流分析技术，它可以获得对象的生命期相关信息，并能够应用 于许多程序优化工作当中，是一类重要的对象生命期分析手段。近年来，逃逸分 析主要运用于j a v a 编译运行系统的优化工作中，用于计算对象的逃逸状态 ( e s c a p es t a t e ) ，并以此作为程序优化工作的依据。逃逸状态反映了对象的生命期 状态，在逃逸分析中，对象的逃逸状态一般可以分为三类：未逃逸状态 f 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 ) 。未 逃逸状态是指对象在一个方法中创建，在该方法中死亡。方法逃逸状态是指对象 的生命期逃逸出了创建它的方法，但未逃逸出创建它的线程。全局逃逸状态是指 对象是多线程共享对象，一般不能显式释放。 在逃逸分析中，经常会运用一些程序抽象( p r o g r a ma b s t r a c t ) 来表征j a v a 程序 中一个方法，并以此为基础进行分析。在逃逸分析中，较为典型的程序抽象有： 连接图( c o n n e c t i o ng r a p h ) ：描述方法中各个对象、变量的可达性信息，逃 逸分析被映射为连接图上的可达性问题。连接图可以很容易地为每个方法建立相 关结构，并能在不同的方法调用上下文中被利用以避免重复计算。c h o i 等【1 蛇o l 首先引入连接图的概念，而本课题组之前设计实现的逃逸分析算法【4 l 也是基于连 接图的程序抽象，但在构造的过程上与c h o i 等【阱2 0 l 不同。 一 方法摘要( m e t h o ds u m m a r y ) ：不仅描述了方法中使用的一些对象和变量的 信息，还描述了方法内调用点( c a l l e es t u b ) 信息等。w a n g 等提出的逃逸分析算法 p o 】引入此概念，其算法在调用点对主调方法和被调用方法对应的方法摘要结构进 行过程间的信息分析以及对象的逃逸状态计算，使得分析具有上下文敏感性。 c h e r e m 等1 3 9 j 提出了一个创建轻量级方法摘要的分析方法，并将该分析结果应用 到堆上对象的显式回收优化【2 5 砣6 】中。 指向逃逸图( p o i n t t oe s c a p eg r a p h ) ：该程序抽象不仅描述了局部变量和对象 中的域如何引用其他的对象，还包括逃逸信息。而在其上的算法结合了逃逸分析 和指针分析两种技术。w h a l e y 等【隅1 和v i v i e n 等【3 4 j 提出的逃逸分析算法都基于此 程序抽象。w h a l e y 等【l8 j 的算法被设计成可以分析完整的或不完整的程序的任意 区域中的对象是否逃逸出这个区域，因此适合分析动态载入的程序。v i v i e 等i 蚓 的算法则结合的一次分析的实验数据、本次分析的分析结果以及前一次运行的反 馈信息柬较为精确地估计运行中对象的生命期行为。 并行交互图( p a r a l l e li n t e r a c t i o ng r a p h ) ：并行交互图刻画了被分析的方法( 或 线程) a n 它的调用者( 或其他并行线程) 问的所有潜在交互，包含信息最多。它为多 线程访问的对象维护了指向关系、逃逸状态、操作顺序等信息，使得基于此程序 5 第1 章绪论 抽象的算法可以分析并行线程间的交互。此外还维护了线程间的交互信息。 s a l c i a n u 等【2 l 】提出的算法基于此程序抽象获取线程间交互信息，结合了逃逸分析 和指针分析，并提取精确的对象逃逸信息和指向信息等。相比连接图和指向逃逸 图，并行交互图的构造过程较复杂。 根据分析是在编译时进行还是在运行时进行，逃逸分析技术可以分为静态分 析和动态分析两类。前者是在程序编译时进行的，易于实现但具有一定的局限性； 后者需要编译时的代码插桩和程序运行时的信息收集与在线或离线分析，精确度 更高但实现起来更为复杂且系统开销较大。 静态逃逸分析( 编译时分析) ：目前绝大多数逃逸分析的实现都是基于一个所 谓的“封闭世界( c l o s e dw o r l d ) ”为前提，即所有可能被执行的方法在做逃逸分 析前都已经得知并且程序的实际运行不会改变它们之间的调用关系。在这种前提 下，静态逃逸分析可以很好地进行正确且较为精确的对象分析。 根据分析的特征，静态逃逸分析可以分为以下三类。根据分析的特征，静态 逃逸分析可以分为以下三类。1 ) 简单的逃逸分析。它基于一种保守的观点，即： 一个对象一旦被存入另一个对象中，该对象便逃逸出去了。借助于这个想法， g a y 等【2 7 】提出了一个非常简单而快速的逃逸分析算法，并将分析出的j a v a 应用 程序中逃逸状态为未逃逸的对象进行栈上分配。这个算法简单而且快速，但非常 不精确。2 ) 上下文不敏感的逃逸分析。b o g d a 等i z s j 提出了一个此类分析方法，用 于消除对象上的不必要的同步操作，该方法可以分析对象中的域所引用的对象的 逃逸状态，不过在某些情况下( 如对象的多次传递引用) 不是很精确。3 ) 上下文 敏感的逃逸分析。w a n g 等【3 0 j 在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 ) 上实现了一 个逃逸分析框架并运用于同步消除优化中，算法在调用点对调用方法和被调用方 法每对应的方法摘要结构进行过程间的信息分析以及对象的逃逸状态计算，保证 了上下文敏感性的特征。b l a n c h e t 2 9 , 3 2 1 提出了一种建立在s s a 格式( s t a t i cs i n g l e a s s i g n m e n tf o r m ) 的此类分析。这类算法精确度比较好也较为复杂，但是对于数 组、循环等分析还不够。 。 动态逃逸分析( 运行时分析) ：j a v a 程序支持动态类载入、本地方法调用和反 射机制等特性，这些特征将打破对“封闭世界”的约定，使得真实的j a v a 程序 运行在一个“开放世界( o p e nw o r l d ) 中，因此纯粹的静态逃逸分析不能有效地 处理这些问题。动态的逃逸分析可以收集运行时的各类信息，并根据收集到的信 息执行逃逸分析。 在动态编译器上下文中。k o t z m a n n 等【3 3 】提出了一种新的过程内和过程间算 法用于动态编译上下文( 支持处理动态类装载和反优化( 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 用户编译器中实现；而 6 第l 章绪论 n i s h i y a m a t 3 5 】则将基于读障栅( r e a d b a 玎i e r - b a s e d ) 的动态逃逸分析用于减少运行 时的数据竞争检测，并在j a v ah o t s p o t 虚拟机中实现。l e e 等1 3 6 j 实现了一种两阶 段的线程逃逸分析：o f f l i n e 阶段和o n l i n e 阶段，前者实现的是静态的逃逸分析， 后者则实现运行时的分析，该分析主要运用于分析多线程程序。在国内的相关工 作中，史晓华等i l 】针对“开放世界”逃逸分析面临的许多重要问题，提出了一种 逃逸分析架构，以正确、全面地捕捉动态载入的类和方法并分析它们与原有程序 的关系，有效地控制算法的复杂性，保证即时编译器的重新分析时间不会过长。 其他分析技术 g u y e r 掣2 4 】通过一种称为f r e e m e 的分析实现一种显式内存回收工作，以辅 助g c 的自动内存回收工作。在他们的工作中，f r e e m e 分析首先进行一种轻量 级的活跃变量分析和指针分析以获得短生命期的死亡对象，并对源程序插入对象 的回收操作：而后端的g c 也提供对这类对象的回收操作的运行时支持。f r e e - m e 分析无法识别域所引用的对象的生命期。 c h e r e m 等【2 6 】也是利用对源程序自动插入对象的回收操作，实现部分对象的 显式内存回收工作。它使用了一种唯一性推断算法( u n i q u e n e s si n f e r e n c e a l g o r i t h m ) 对源程序进行分析，识别持有单一引用的变量和对象域，并展开过程 内及过程间分析计算全局的唯一性依赖关系( u n i q u e n e s sd e p e n d e n c y ) ，通过为对 象所属的类添加析构器的方式来释放整个对象空间。 优化应用 编译器支持的内存优化技术主要应用在对象的栈上分配、基于区域的分配和 堆上对象的显式回收三个方面。其中对象的栈上分配和基于区域的分配属于对象 分配模式上的优化，堆上对象的显式回收属于对象回收模式上的优化。 对象的栈上分配方式：对于那些没有逃逸出方法的对象，在方法结束后，将 不会再使用，因此可以将其分配在栈上。栈式分配与堆分配相比，具有3 个很重 要的优点：( 1 ) 栈式分配比堆分配减少了同步操作；( 2 ) 栈式分配减轻了垃圾收集 器的负担：( 3 ) 栈空间始终是c a c h e 热点，对栈的操作速度明显快于对堆的操作。 但在栈上分配对象可能潜在的会引起栈溢出。一些逃逸分析工作【1 8 2 0 1 将逃逸分 析结果应用到对象的栈上分配上。特别地，王雷等【2 】引入了对象栈、区域栈帧等 的概念，将方法调用栈和对象分配栈区分开来，将循环作为区域栈帧建立和释放 的基本单位，实现了基于逃逸分析的循环中栈式分配优化。 基于区域的对象分配方式：这类方法将一部分对象分配在方法或线程所对应 的区域( r e g i o n ) 中，当方法调用结束或者线程任务结束时，就可以把它们对应的 区域空间进行回收。对象可以进行区域分配的前提条件是该对象的生命期没有超 7 第1 章绪论 过该区域对应的方法或线程的生命期。s a l c i a n u 等t 2 1 1 静态地验证了将逃逸分析和 指针分析的结果应用于该分配模式的可行性，当一个区域中的对象不试图创建到 另一个具有更短生命期的区域中的另一个对象的引用时，基于区域的分配是正确 的；s a l a g n a c 等【2 2 】实现了一个基于该分配模式的原型系统；g a y 等【2 3 1 在c 语言 的编译器中实现了基于区域的分配模式。 堆上对象的显式回收：编译器在编译期间进行程序分析，得到死亡对象信息， 然后在合适的位置插桩显式内存释放等指令来主动通知g c 回收内存，这将大大 减轻g c 回收内存空间的负担，而且为内存空间的重用提供了机会。g u y e r 等1 2 4 在即时编译器中通过轻量级的称为f r e e m e 的分析获得短生命期的死亡对象，并 对源程序插入对象的回收操作；而g c 也提供对这类对象的回收操作的运行时支 持，但分析对域引用的对象空间无法释放。c h e r e m 等【2 5 - 2 6 】是利用对源程序自动 插入对象的回收操作，实现部分对象的显式内存回收工作。它使用了一种唯一性 推断算法对源程序进行分析，识别持有单一引用的变量和对象域，并展开过程内 及过程间分析计算全局的唯一性依赖关系，最后利用这些唯一性信息指导对源程 序的插桩工作。 现有的编译器辅助的内存管理优化存在一些不足。对象的栈上分配和基于区 域的分配是对象分配模式上的优化。对象栈上分配有很多优点，但在栈上分配对 象可能会引起栈溢出。基于区域的分配方式的正确性验证非常复杂，静态时正确 性验证需要复杂的线程间分析，而动态时检查除了有检查的开销，还需要引入失 败模式处理。堆上对象的显式回收是对象回收模式上的优化，g u y e r 等1 2 4 的 f r e e m e 分析能够释放部分短生命期的死亡对象，但分析对域引用的对象无法释 放。c h e r e m 等1 2 5 - - 2 6 j 的工作除了引入显式内存释放指令来释放对象空间，还为部 分类引入析构器来释放该类的实例对象的域所引用的空闯，这涉及到修改基本 库；该工作先在s o o t 平台【4 1j 上完成分析和插桩，然后在j i k e sr v m t 4 0 l 平台上运 行，而在用j a v a 语言编写的j i k e sr v m 中插桩j a v a 库代码是非常困难的任务， 该工作最后没有完成库变换。 1 2 3 本课题组已有工作 本课题组也在开展编译器支持的内存管理优化这方面的研究。研究的主要目 标是通过研究j i t 辅助的g c 所涉及的程序分析、插桩变换以及内存管理等技术， 不仅能使g c 即时地回收已经死亡的对象所占用的空间，还可以采取一些策略对 这些空间进行重用、甚至对部分对象采取特殊的分配方式。j i t 辅助的g c 技术 能够减轻g c 负担，提高内存利用率和j a v a 应用程序的执行效率，对实时系统 和内存受限的系统具有重要的意义。 r 第1 章绪论 本课题组已经在开源的j a v as e 平台a p a c h eh a r m o n y l 3 l j 上初步实现了j f i t 辅 助的g c 系统。已有的系统重点集中在对象显式回收上做优化，能处理单线程、 规模较小的程序，但分析算法存在不足，系统运行效率较低。已取得的研究成果 主要包括：在j i t 侧，提出一种基于逃逸分析的对象生命期分析方法【4 j ，该分析 是过程间的、流敏感的( 划分标准是：是否考虑程序执行的语句顺序，该分析考 虑了顺序流，没有考虑分支与循环) 、上下文敏感的，不仅能分析对象是否全局 共享，而且能计算和分析非全局共享对象的生命期在线程中的哪个方法内结束， 为对象的显式内存释放指令的插桩奠定了基础。在g c 侧，实现了基于j i t 辅助 的并行垃圾收集器叫，能够支持显式的对象回收操作，且可以及时有效地重用部 分对象空间。在本文的第2 章将详细讨论已有的j i t 辅助的g c 系统。 1 3 研究内容 在充分调研国内外相关研究工作的同时，本文致力于改进本课题组原有的即 时编译器辅助的垃圾收集系统，重点研究其中的对象生命期分析算法和显式内存 释放等指令( 本文的其余章节称之为f r e e 指令) 的插桩变换。 由1 1 节中的图1 1 可以得知，j 1 t 辅助的g c 优化工作主要涉及到三个模块： 即时编译器( j i t ) 、虚拟机核心( v m c o r e ) 和垃圾收集( g c ) 器部分。j i t 侧负责完成 对象生命期分析以及相应的插桩变换；v m c o r e 侧负责j i t 与g c 的交换、启动。 而g c 部分负责设计对象的分配与回收策略、提供相应的运行时支持接口、统计 信息收集与输出。本文的工作涉及到了这三个模块，但重点在j i t 部分的对象生 命期分析与f r e e 指令的插桩变换。本文主要探讨并完成了以下工作： 1 、提出一种结合活跃变量分析和指针分析的对象生命期分析算法，以获得 精确的对象生命期信息。 对象生命期分析策略及算法是实现即时编译器辅助的内存管理优化的基础。 通过结合活跃变量信息，使得分析出的对象生命期分析更为精确，不仅能够分析 出对象在哪个方法中死亡，还可以获得对象在方法的那个基本块中死亡，为f r e e 指令的插桩提供的详细的信息。本文提出的对象生命期分析是过程间的、流敏感 的( 该分析考虑了顺序流和循环，没有考虑分支) 、上下文敏感的，自下而上的过 程问信息传播过程使得所提出的算法不仅能够识别方法内死亡的对象的生命期， 还能够识别那些逃逸出方法的对象的生命期信息。 2 、利用对象生命期分析结果，设计f r e e 指令的插桩策略与代码变换方法。 插桩就是根据对象生命期分析得到的死亡对象信息，确定一个合适的插桩位 置和选择合适的引用然后安插f r e e 指令。提出的插桩算法首先考虑了控制流中的 9 第1 章绪论 支配关系，保证了插桩的显式释放内存的指令的正确性；其次在描述对象引用时 引入域描述且在插桩时能够主动生成指令获得对象的域引用，从而能释放对象的 域所引用的对象内存空间，达到对整个对象空间的释放；最后为不同对象提供不 同的插桩类型，保证可以高效地利用对象生命期分析信息，使得分析出的死亡对 象空间尽可能多的被释放。 3 、对原有的日志系统进行改进，设计一种能够用于评估每条内存释放指令 收益的日志系统。 原有的日志系统能够获得分配空间大小、显式回收空间大小、重用空间大小、 垃圾收集次数及执行时间等信息。本文在原有的日志系统基础上，设计一种新的 日志系统，不仅能够获得垃圾收集和对象显式回收的总体信息，还可以进一步获 得每条内存释放指令的收益。新的日志系统将为指导下一步的对象分配模式上优 化工作奠定了基础。 4 、在原有的, l i l t 辅助的g c 系统上，设计实现了上述工作，提高了系统在 对象的显式回收及其空间复用上的能力。 j i t 以优化遍的形式实现中间代码上的每一类分析与优化。本文中的对象生 命期分析和插桩变换以优化遍的形式实现，并