理论计算机科学电子笔记131（2005）99-110www.elsevier.com/locate/entcs基于区域的内存管理的快速逃逸分析G. Salagnac1，3S. Yovine1， 3D。 Garbervetsky加伯韦茨基2，4摘要我们提出了一种逃逸分析算法，该算法受到Gay和Steensgaard [11]的启发，但比Gay和Steensgaard提出的算法更精确。我们的算法的主要目的是使用基于区域的内存管理器产生有用的信息来分配内存。该算法结合了基于变量的过程内和过程间点分析。这是一项正在进行的工作，旨在实现面向应用程序的精确性和可扩展性之间的权衡。我们在几个典型的编程模式上说明了该算法，并在几个基准上显示了第一个原型的实验结果。关键词：逃逸分析动态内存管理。1介绍垃圾收集（GC）[14]不用于实时嵌入式系统。原因是动态内存回收的时间行为非常难以预测。已经提出了几种用于实时嵌入式应用的GC算法（例如，[12、17、16、13]）。然而，这些方法是不可移植的（因为它们对底层execution平台施加了限制性条件），需要额外的内存，和/或不能真正确保1V ERIMAG，Cene t reEqua t ion，2Ave.V ign a t e，38610Gi`eres，Frannce. E-mail：firstname. imag.fr。2计算机科学学院，阿根廷布宜诺斯艾利斯大学电邮地址：diegog@dc.uba.ar网站。3部分得到了项目CANOO（Min. Research，法国）和MADEJA（Rhizone-Alpees，法国）的支助。4部分由ANCyT资助PICT 11738和IBM Eclipse创新资助项目支持1571-0661 © 2005 Elsevier B. V.在CC BY-NC-ND许可下开放访问。doi：10.1016/j.entcs.2005.01.026100G. Salagnac等人理论计算机科学电子笔记131（2005）99可预测的执行时间。克服GC算法的缺点的一个有吸引力的解决方案是在区域中分配对象（例如，[18]）与计算单元（通常是线程或方法）的生命周期相关联当相应的单元完成其执行时，区域被释放。例如，Java实时规范（RTSJ）[2]采用了这种方法，其中区域可以与可运行对象相关联，[10]实现了C的库和编译器。这些基于区域的方法定义了可用于显式和手动处理程序内对象的分配和释放的API。但是，在将对象映射到区域时必须小心，以避免悬挂引用。因此，使用这样的API编程容易出错，主要是因为确定对象直接使用API对存储器管理进行编程的替代方案在于自动转换程序，以便（a）通过对基于区域的存储器分配器的调用来替换（只要可能）“新”语句，以及（b）进行适当的调用（即，保证不存在悬空引用）到释放器。这种方法需要分析程序行为来确定动态分配对象的生存期。在[8]中，分析基于profiling，而[9，4]依赖于静态（指向和逃逸）分析。逃逸分析的目的是保守地确定一个对象是从一个方法逃逸还是被一个方法捕获。直观地说，当一个对象的生存期比方法的生存期长时，它会转义方法，所以当方法结束执行时，在以下情况下，它可以在其执行结束时被安全地收集。已经提出了几种方法来逃避Java分析，其中大多数旨在在堆栈上分配对象，并删除不必要的同步。[1]工作在字节码上，由于基于堆栈的模型，这带来了额外的复杂性。[5，19]使用指向分析来确定对象是否通过指向图中的路径逸出方法。[11]提出了一种快速但非常保守的逃逸分析，基于求解从静态单分配（SSA）形式[7]的程序。对于Java中基于区域的分配，我们知道两种工作。[9]利用方法调用链和转义分析来动态地将分配站点映射到与方法相关联的区域。[4]定义了一种指向分析，以确定具有相似生命期的对象的区域（具有预防级别的分辨率，而不是方法级别）。在本文中，我们提出了一个算法逃逸分析的启发，但更精确，在[11]中提出的我们算法的主要目的G. Salagnac等人理论计算机科学电子笔记131（2005）99101RITHM是使用基于区域的存储器管理器来产生有用的信息以分配存储器该算法结合了基于变量的过程内和过程间点分析。这是一项正在进行的工作，旨在实现面向应用程序的精确性和可扩展性之间的权衡。我们在几个典型的编程模式上说明了该算法，并在几个基准上显示了第一个原型的实验结果2该算法在本节中，我们将详细描述我们的逃逸分析算法。我们假设程序是静态单赋值形式（SSA）[7]，也就是说，每个变量在程序中只被赋值一次。将程序转换为SSA是有代价的，但是给了对MIMO不敏感的分析以对MIMO敏感的分析的能力。我们的算法主要基于局部变量，而不是复杂的点到图，这将是更昂贵的建设和工作。该分析基于抽象解释[6]，并计算局部变量和方法的几个属性。2.1性能2.1.1逃脱对于方法的每个局部变量v，escape（v）∈Escape，其中Escape是图1（a）中的格，表示v是否可以从其方法中逃逸，也就是说，如果v指向的对象以某种方式引用，则其生存期可能超过方法。变量v会逃逸，因为它会被返回（escape（v）=RETURNED）或被复制到全局变量（escape（v）=STATIC）。当一个变量被存储到一个对象字段（escape（v）=FIELD）时，v可以通过一个引用链进行转义。在这种情况下，确定v是否逃逸需要进一步的分析，这将在后面解释。 T值代表转义的变量通过几种方式，或者当分析不能计算更紧密的信息时（例如，当V用作非分析方法中的参数时）。例如，在图1（b）所示的程序中 ， escape （ a ） =STATIC ， escape （ b ） =RETURNED ， escape （ c ）=RETURNED，escape（d）=T。请注意，escape（v）=n不足以说明v指向的对象是方法的局部对象。它只意味着该方法不会创建从方法外部到对象的任何新引用路径，但该对象可能已经可以从外部访问。图1（b）中的变量b就是这种情况，它是静态变量s的别名。102G. Salagnac等人理论计算机科学电子笔记131（2005）99不3↑s场返回静态public voidonDestination（）{Object a=m1（）;int n = nums（）;}public void run（）{Objectc=new Object（）;return c;s↑3⊥(a) 逃逸晶格}public void run（）{Object d=new Object（）;s=d;返回d;}}(b) Test01计划Fig. 1. 转义格和Test01程序3.1.2mfresh设MFresh为格：T ≤RETURNED≤ T。对于每个方法m，mfresh（m）∈MFresh描述了m返回的对象如何转义：mfresh（m）= n当m不返回任何对象（它可能是void，或者返回一些原始类型值）时; mfresh（m）= T当返回的值已经知道以不同的方式从m中转义时; mfresh（m）= RETURNED当m返回一个（或几个）不转义的对象时。 如果没有其他路径指向这个对象（见2.2.2节），m的调用者可以捕获它。3.1.3网站设站点为P（AllocationSites{UNKNOWN}），其中AllocationSites是程序中所有分配站点的集合。对于每个局部变量v，sites（v）∈Sites包含所有可以创建由v引用的对象的分配站点。sites（v）总是可以在唯一的（感谢SSA）语句中计算，其中v被定义。保守地说，如果我们不能确定v可以指向的所有站点由于未分析的方法调用），将未知添加到站点（v）。在图1（b）的程序中，站点（a）=站点（c）={[m1：c=new Object]}，以及sites（b）=sites（d）={[m2：d=newObject]}。3.1.4msites对于每个方法m，msites（m）是Sites的一个元素，表示对象在哪里被m从m中删除。 在图1（b）的程序中，msites（m0）={[m 1：c=新对象]}，msites（m 1）={[m 2：d=新对象]}。注意，如果mfresh（m）=RETURNED，那么来自msites（m）的对象可能被m的调用者捕获，但这并不确定。在某些复杂的情况下，仍然可能存在指向这些对象的引用路径。 例如在图6（a）所示的程序中，e变量没有被m0捕获。G. Salagnac等人理论计算机科学电子笔记131（2005）991033.1.5非参考的isdereferenced（v）是真的，如果在m中isdereferenced（v）或其别名之一。也就是说，isv.f出现在赋值语句的右侧。3.1.6用作参数usedasparameter（v）为true，如果usedasparameter（v）或其别名之一在方法调用中用作具体参数。3.1.7def对于每个变量v，def（v）表示v是如何定义的。3.1.8菲尔德斯fielduse显示局部变量之间的引用关系。对于m中的每一个v，fielduse（v）是m中的变量u的集合，使得v可以是u.f的别名（对于某个域f）。fielduse主要在变量v被FIELD转义时有用：例如，如果escape（v）=FIELD，但fielduse（v）的所有变量都被m捕获，那么v也是如此。3.1.9mrefs图当对象通过多个方法传递时，关于局部变量的知识通常不足以确定对象的生存期，这就是为什么需要引用图。我们的参考图非常简单，以最小化分析的算法成本。 mrefs是AllocationSites的子集×F ields×AllocationSites，其中（α，f，β）∈mrefs表示：在α中，可以用它的场指向在β3.1.10侧我们分析的主要目标是确定在哪些区域分配对象。每个方法m都有一个关联的区域，包含不转义m的对象。为了确定区域，我们计算m的每个变量v，其中v指向的对象存在，即side（v）：• side（v）= INSIDE，当v指向的对象被m捕获时。如果它们是由m创建的，则可以将它们分配到m所在的区域。如果它们是由被调用者创建的，则m可以要求将它们分配到其区域中，如[ 9 ]中所述;• side（v）= OUTSIDE，当v指向的对象寿命长于m时。如果它们是由m创建的，它们必须在它的堆栈框架之外分配。但是这样的对象可以被m的调用者n捕获，在这种情况下，m可以在n的区域中分配对象。104G. Salagnac等人理论计算机科学电子笔记131（2005）99在图6（a）中呈现了一个示例：由m2分配的RefObject由m1捕获。我们的分析通过计算侧（a）=外部和侧（c）=内部来检测这种情况。2.2规则该 算 法 分 两 个 阶 段 工 作 。 首 先 ， 它 为 每 个 变 量 确 定 escape ， sites ，isdereferenced，usedasparameter，fielduse，def的值，它构建mrefs图并计算msites和mfresh值。为了计算这些值，该算法求解图2和图3中的最小定点。在第二阶段，该算法使用这些值来计算每个变量的边值，如图4所示。这是侧和站点的组合，将使我们能够检测字节码，以便为捕获的站点使用区域内存分配器。α：v：=newα∈sites（v）v：=0（v1..vn）def（v）=PHI1. nsites（v）位置（vi）逃逸（v）±逃逸（vi）逃逸（vi）±逃逸（v）isdereferenced（v）≥ isdereferenced（vi） isdereferenced（vi）≥isdereferenced（v） usedasparameter（v）≥ usedasparameter（vi）usedasparameter（vi）≥usedasparameter（v） field use（v） fielduse（vi）fielduse（vi） fielduse（v）v：=v1def（v）=COPY其他属性：类似于表达式v1.f：= vescape（v）±FIELD场use（v）3v1mrefs{s1−→fs2，s1∈sites（v1），s2∈sites（v2）}s：=v逃逸（v）±静态mrefs<${UNKNOWN−→s，s∈ sites（vi）}v：=sdef（v）=静态（v）第三章v：=pdef（v）=PARAM（v）第三章其他属性：类似于表达式v：=常数def（v）=CONSTANT（v）第三章v：=v1.fdef（v）=FIELDisdereferenced（v1）≥true站点% s（v）%s|s′∈sites（v1），s′−→fs}如果未知∈sites（vi）sites（v）3未知返回mvescape（v）±RETURNEDmfresh（m）± escape（v）msites（m） msites（v）图二. 逃逸分析规则G. Salagnac等人理论计算机科学电子笔记131（2005）99105v：=v0.m（v1.. vn）在这里可以调用的函数mIfistobeprocessed（m）网站（v）如果mfresh（m）/=RETURNED逃逸（v）±mfresh（m）i = 0.. nusedasparameter（vi）≥true设 m 的 第 i 个 形 式 参 数 pi 为isderefected （vi ） ≥isderefected（ pi ） ， 若 <$escape （ pi ） ∈{RETURNED，<$}逃逸（vi）±Tmrefs<${UNKNOWN−→s，s∈ sites（vi）}如果isdereferenced（pi）=truemrefs{UNKNOWN −→ s |s′∈ sites（vi），s′−→ s）}其他（v）第三章i = 0.. nusedasparameter（vi）≥true被解引用（vi）≥true转义（vi）±Tmrefs <${UNKNOWN−→s，s∈sites（vi）}图三. 逃逸分析规则2.2.1一期这些规则大多很简单。它们只是过程内的信息传播。唯一复杂的规则是图3中的规则，它处理方法调用。这并不是微不足道的，因为我们不想执行完整的指向分析，也不想对方法调用过于保守我们的分析旨在处理应用程序的任意部分。这就是为什么我们有一个istobeprocessed谓词，它告诉我们一个方法是否必须被分析。如果不是，例如因为方法是本机的，或者不可用，我们必须保守。对于未分析的方法，我们假设所有参数都逃逸，并由UNKNOWN站点引用。另一方面，如果对方法进行分析，那么我们可以更精确。显然，我们有sites（v）和msites（m），也就是说，v将指向m返回的任何对象。如果这些对象已经转义（mfresh（m）/=RETURNED），则返回值也不可捕获。（逃逸（v）±mfresh（m））为了处理m的参数，我们将形式参数（pi）与具体参数（vi）进行匹配：如果pi从m中逃逸，则认为vi从当前方法中逃逸，并且我们将来自UNKNOWN的边放置到指向的所有站点。在vi。如果pi没有转义，但是在m中被解引用，那么如果不进行指向分析，我们就不能精确地了解在这种情况下，我们保守地认为vi的所有子元素都逃脱了。106G. Salagnac等人理论计算机科学电子笔记131（2005）992.2.2二阶段def（v）逃脱（v）新RETVAL参数静态复制PHI领域恒定⊥（三）（三）外面（一）（二）外面领域（二）（二）外面（一）（二）外面返回外面外面外面外面外面外面静态不外面外面外面外面外面外面外面外面外面外面外面外面（一）v：=0（v1.. vn）orv：=v1侧（v）±侧（vi）i侧（vi）±侧（v）（三）若sites（v）s. 未知~ sside（v）=OUTSIDE其他（二）如果n ∈fielduse（v）s. side（u）=OUTSIDE或s.t. isdereferenced（u）已取消引用的参数（u）side（v）=OUTSIDE其他side（v）=INSIDE（三）见图4。 边的计算（v）一旦到达固定点，算法使用图4所示的规则计算每个变量的side（v）。这不是一次计算，而是第二个最小定点，因为（1）和（2）规则：• （1）规则说，如果一个变量可以别名另一个变量，那么这两个变量不能有不同的侧值。• 类似地，（2）规则说，如果一个变量v被另一个变量的字段引用f=v），除非u是，否则v不能被捕获2.2.3示例让我们来看看图中的例子。5（a）.首先，m0构建一个小的链式结构，然后调用m1，使最后一个元素（t3）转义。如图所示。在图5（b）中，对m0的分析理解了m0的行为，但由于我们只能将x与t1匹配，而不能将a与t2匹配，因此我们无法跟踪M1的。尽管如此，为了保持保守，我们将从UNKNOWN到t2的位置放置一条边，因为x在m1中被解引用。注意，t2和t3被用作参数，因为它们是构造函数的this参数。这就是为什么唯一捕获的站点是[m0：t1 = new RefObject]。第二个例子，如图6（a）所示，说明了msites属性。m2方法分配两个对象，并使一个（a）指向另一个（b），这是转义的。然后它返回a，由m1捕获（side（c）=INSIDE）。 m1解引用c以获取Object并返回它，但m0无法捕获它G. Salagnac等人理论计算机科学电子笔记131（2005）99107Objectf;}public void run（）{RefObject t1=new RefObject（）; RefObject t2=newRefObject（）;Object t3=newObject（）; t1.f=t2;t2.f=t3;m1（t1）;}staticObject %s;void m1（RefObject % x）{RefObject a=（RefObject）x.f;Objectb=a.f;b = 0;}}（b）mrefs图(a) Test25计划逃脱mfresh defIsD uP字段使用网站msites侧m0t1 NEW true true [][m0：t1 =new RefObject] INSIDEt2 FIELD NEW false true [t1][m0：t2 = new RefObject] OUTSIDE t3 FIELD NEW true true[t2][m0：t3 = new java.lang.Object] OUTSIDEm1迷你X轴PARAM真正false[][UNKNOWN]Outside aPunctureField虚 假false [][UNKNOWN] OUTSIDE b静态领域虚假false [][UNKNOWN] OUTSIDE(c)分析结果图五. Test25计划因为从UNKNOWN到[m2：b = new Object]的边。3实证结果我们已经使用Soot框架[15] v.2.2.1实现了该算法的原型版本。表1给出了我们的算法在Jolden基准测试中的结果[3]。前两列是程序的行数和分配站点的数量。接下来的三列显示了我们的escape分析所花费的时间，以秒为单位，不包括Soot最后三列给出了INSIDE变量和分配位置的数量，如我们的算法所计算的，以及可堆叠变量的数量，如我们的G S分析[ 11 ]的实现所我们的分析比[11]更精确，因为它包含了所有的规则。也就是说，[11]意义上的所有可堆叠变量都是INSIDE变量，但反之则不成立。在我们的实验中，我们没有使用任何分析代码的内联。有趣的未知t2=新Ft3=新Ft1=新108G. Salagnac等人理论计算机科学电子笔记131（2005）99public void run（）{int n = nums（）;}public void run（）{RefObject c=m2（）;Object d=c.f;return d;}publicvoid run（）{Object a=new Object（）;Object b=new Object（）;s=b;a.f=b;return a;(b) mrefs图}}(a) Test30计划转义mfreshdefISD起来菲尔德斯网站msites侧M0e⊥⊥RETVAL假假∅∅[m2：b = new Object]外面M1C返回⊥RETVAL真假∅[m2：b = new Object][m2：a = newRefObject]内部D返回领域假假∅[m2：b = new Object]外面M2返回[m2：a = newRefObject]一返回新假真：∅[m2：a = newRefObject]外面B不新真真[r1][m2：b = new Object]外面(c)分析结果见图6。 Test30计划程序线分配网站分析时间内部G S可堆叠变数逃脱侧总变量网站bh1128419.43023.5132.481342123比索尔340107.87611.50919.385777em3d462268.55115.70624.257131111健康562288.45419.41427.868181310MST473168.10614.26022.366887周边7451311.35723.94435.301777功率765213.6281.1594.787995treeadd1951110.87627.53938.415666tsp5451211.1930.20141.220777Voronoi10003512.77866.56679.344342031表1分析结果注意，如果没有内联，[11]在图5和图6的程序中找不到任何可堆叠的变量。如[11]所述，两种分析都将受益于方法内联。我们没有足够的时间来使用计算出的信息，未知b=新Fa=新G. Salagnac等人理论计算机科学电子笔记131（2005）99109如[9]中所述的工具基准。我们指望很快这样做。无论如何，在另一个测试程序上的初步实现显示，当将GC与基于区域的管理器w.r.t.一起使用时，总内存使用量增加了20%。仅限GC，即使实际区域分配的内存约为5%。此外，对于每个测试用例，只分析了整个调用图的一个子图。 子图包含所有应用程序方法和程序可传递调用的库方法的子集。这就解释了为什么只有几个分配站点。然而，这些结果是有趣的，因为分析的分配位点的重要部分确实被计算为被捕获。我们的算法是参数化的一组类进行分析。这允许用户根据特定的应用程序行为针对性能微调分析交易精度。确认我们感谢Chaker Nakhli和匿名裁判的有益评论。引用[1] B.布兰切特Escape Analysis for Java（TM）. 理论和实践 ACM TOPLAS，25（6）：713-775，2003.[2] G. Bollella和J. Gosling。Java的实时规范。Addison-Wesley Longman出版公司股份有限公司、两千[3] B. Cahoon和K. S.麦金利 java控制器中软件预取链接数据结构的数据流分析PACT2001年[4] S. Cherem和R.鲁吉娜Java程序的区域分析和转换。在ISMMPress.[5] J. - D. 崔M. 古普塔M. 塞拉诺，诉C. 斯里达尔，和S.Midki使用转义分析的Java堆栈分配和同步优化。ACM TOPLAS，25（6）：876-910，2003.[6] P. Cousot和R.库索抽象解释及其在逻辑程序中的应用。Journal of Logic Programming，13（2-3）：103-179，1992.[7] R. Cytron，J. Ferrante，B. K.罗森，M。N. Wegman和F. K.扎德克高效地计算静态单赋值形式和控制依赖图。ACM TOPLAS，13（4）：451[8] M. Deters和R. 塞隆自动发现实时Java的作用域内存区域。 在ISMM[9] D. 加伯韦茨基角Nakhli，S.Yovine和H.佐加蒂java中作用域内存的程序插装和运行时04年房车赛。出现在ENTCS中。[10] D. Gay和A.艾肯 区域语言支持。 在SIGPLAN PLDI[11] D. 盖伊和B。斯坦斯加德基于对象程序的快速转义分析和堆栈分配在CCSpringer-Verlag，2000.[12] R.亨里克森嵌入式系统中的垃圾收集调度。PhD.论文，隆德理工学院，1998年7月。[13] T. Higuera，V. Issarny，M.班戈湾Cabillic，J-Ph. Lesot，and F.帕兰实时Java的内存管理：使用硬件支持的高效解决方案。实时系统杂志，2002年。110G. Salagnac等人理论计算机科学电子笔记131（2005）99[14] R. Jones和R.琳丝垃圾收集。自动动态内存管理算法。John Wiley and Sons，1996年。[15] V. Sundaresan，P. Lam，E.加尼翁河瓦利赖湖Henrique和P. Co. Soot -一个Java优化框架。在CASCON 1999的Proceedings，第125-135页[16] T. Ritzau和P. Fritzon。 减少硬实时垃圾收集中的内存开销在EMSOFT'02，法国格勒诺布尔。LNCS 2491，2002年。[17] F.西伯特在Java的非移动垃圾收集器中消除外部碎片。2000年的案例。[18] M. Tofte和J-P. Talpin。 基于区域的内存管理。 信息与计算，1997年。[19] J. Whaley 和 M. 里纳德组成指针 和逃脱 分析为 Java 程序. 在OOPSLAPress.
