过程间循环兴趣路径剖析方法

罗芳

（四川大学计算机学院，成都　610065）

过程间循环兴趣路径剖析方法

罗芳

（四川大学计算机学院，成都610065）

路径剖析；过程间路径；兴趣路径；多态；动态分析

0　引言

路径剖析作为动态软件分析的一个重要领域，其目的在于：根据大量执行情况，给出执行路径的执行频率，主要应用于计算机架构、程序编译、调试、测试和软件维护等方面有着重要的应用[1]，同时还可以应用在路径敏感代码的优化[2]、代码布局优化[3]以及静态分支预测的改进[4]等方面。

为了获取执行的路径和频率,剖析方法需要在目标程序中装插探针（probe），接下来是在程序执行过程中计算探针值并收集执行信息，最后根据路径末端的探针值（路径编码）和相关信息各条路径的执行次数。而在每次程序执行完毕后，使用探针变量值来唯一确定执行路径的编码，而要保证剖析结果的精确性，每条可剖析路径的编码必须是唯一的。

现有的剖析方法可分为过程内剖析和过程间剖析，也可分为选择性剖析和非选择性剖析。1996年Ball等人提出了首个路径剖析方法EPP（Efficient Path Profiling）[5]是一种过程内非选择性剖析方法，可以十分精确、高效地剖析过程内的所有无环CFG（Control Flow Graph）的路径。

之后出现的方法有些致力于提升循环处理能力。例如2004年Tallam提出的过程内有环路径近似剖析方法ExPP（Extended Path Profiling）[6]，可以精确地剖析循环次数在两次以内的路径。而Roy等人在ExPP的基础上改进提出了kIPP（Profiling k-iteration paths）[7]可以剖析含有k次以内的循环路径。而王璐璐等人在EPP的基础上改进提出的PAP（Profiling All Paths）,可以剖析任意有限次循环的路径。

有的方法着重在将路径剖析扩展到选择性剖析。基于EPP，Apiwattanapong提出了SPP（Selective Path Profiling），Viswani等人提出了PrePP（Preferential Path Profiling），这两种方法都可以进行选择性剖析，区别在于SPP方法会分配较大权值给兴趣路径中的边，以降低非兴趣路径的编码，而PrePP方法分配较小的权值给兴趣路径中的边，以压缩兴趣路径的编码，使其能够使用数组存储以提高效率。而ESPP算法是对SPP的改进，可以有效地保证剖析的精确度。但是这些方法都不能很好地剖析循环路径。所以又有研究人员提出了PSP（Profiling Selected Paths）方法，可以剖析有环CFG的路径。

目前的研究人员主要致力于以上两个方向的研究，对于已有剖析方法，或能够精确地剖析过程间循环路径，或能够剖析过程内兴趣路径，而很少有文献讨论过程间循环兴趣路径的剖析，本文结合了PIP（Profiling Inter-Procedural Paths）方法剖析过程间循环路径的特点和PSP（Profiling Selected Paths with Loop）方法剖析兴趣路径的特点提出了一种剖析过程间循环兴趣路径（PISP）的方法，旨在提高过程间循环路径的剖析效率。

1　相关介绍

1.1PIP

PIP[9]能够精确地剖析过程间带有循环的路径。为了描述多态调用信息，PIP中提出了一种方法调用模型——PCCG（Polymorphic Cluster Call Grapth），图1 为一个PCCG的示例，图1（a）给出了一个具有5个方法的调用图，包含了方法的调用关系和覆盖关系。其中有两个调用关系（实线所示），A指向B，C指向D，同时包含了三个覆盖关系（虚线所示），分别是C覆盖A，D覆盖B和E覆盖D。

在图1（a）的基础上可以通过一下3个步骤得到相应的PCCG图，并可将所有可能的调度包含在转化后的PCCG中：

①如图1（b）,在图1（a）中添加3条潜在调用边：AD、AE和CE，以拆分多态调用边；

②在拆分多态调用边的基础上，如图1（c）所示将方法A和C归为一簇，将B、D、E归为一簇，若方法A有调用另一个簇中的方法C，则方法A有一条调用边指向C所在的方法簇，再删除冗余的调用边；

图1　PCCG示例图

③如图1（d）所示如果方法C调用的另一个簇中的方法D，则D所在的方法簇中每一个方法都添加一条返回边指向C所在的方法簇。

而PIP方法是根据输入的过程间控制流图、过程调用关系和方法集簇得到PCCG图，其中方法集簇策略有三种：策略SC（每个方法单独作为一个簇）、策略IC（所有存在覆盖关系的方法归为一簇）、策略AC（所有方法归为一簇）。然后再在PCCG模型上穿插探针，对于入度大于一的被调用簇的n条入边，分别分配探针n（0），n（1），…，如图1（d）所示，并根据探针对程序进行装插，最后运行装插后的程序，收集执行路径的编码及其频率，将之解码为剖析结果。

1.2PSP

PSP能够精确的剖析循环兴趣路径，并使用检测非兴趣路径和提前终止技术两种方法来降低耗费[10]，即如果在执行过程中检测到执行路径是非兴趣路径，则提前终止执行以减少执行时间。为尽可能早尽可能多的检测出非兴趣路径，以减少PSP方法中提出了三种检测技术：

①T1.检测临时编码，其检测依据是非兴趣路径和兴趣路径的临时编码在某些位置上不同，在执行过程中如果发现当前的临时编码不属于任何一个兴趣路径，则提前结束；

②T2.检查局部编码，其依据是兴趣路径和非兴趣路径会在CFG执行不同的路径片段，在无环子图上使用ESPP，并在子图出口出检查局部编码，若发现执行的是非兴趣路径，则提前结束；

③T3.检测边界边集合，其依据是在兴趣路径上只会执行兴趣边，执行了边界边和无效边的路径肯定是非兴趣路径，所以可以在边界边上进行检测。

基于上述三种检测方法提出了PSP0～PSP3四种方法，PSP0使用T1检测临时编码，PSP1使用T2检测局部编码，PSP2使用T3检测边界边集合，而PSP3同时使用T2、T3，即同时检测局部编码和边界边集合。

PSP0需要进行路径检测其前驱有多条出边的节点，首先使用PAP算法得到相应的探针，再在CFG必要的位置计算兴趣路径的临时编码，并以该临时编码装插路径检测的探针，其时间消耗为O（E+N*I），（E为CFG的边数，N为节点数，I为兴趣路径的数目）。

PSP1使用ESPP的局部探针变量对RAS（无环子图）进行选择性剖析，并在RAS的出口处使用T2对局部编码，若发现当前执行的不属于兴趣路径，则体检结束，若在RAS出口没有找检测到非兴趣路径，则将局部编码结合到PAP的全局探针变量的计算之中，继续执行。其时间消耗为O（S*P’*E2+S*P’*E*I），其中S指的是CFG中无环子图的数量，E指CFG的边数，I为兴趣路径的数量，P’指的是各个无环子图中静态路径数的上限。

PSP2在进行探针装插时根据T3的检测机制，需要在边界边上装插提前结束的探针，使得无效边不可达，并且在无效边上删除所有的探针，以简化CFG，再使用PAP算法剖析简化后的CFG，最后将探针前推以减少探针数量。算法的时间消耗是O（E*I），其中E是CFG的边数，I是兴趣路径的总数。

PSP3是同时使用T2、T3两种检测方法，首先使用PSP2并删除CFG中的非兴趣路径，以简化CFG，然后应用PSP1检测在简化后的CFG中的RAS（无环子图）。算法的时间消耗为PSP1和PSP2的和，即O（S*P’*E2+S*P’*E*I+E*I）（参数含义参照PSP1和PSP2）。

2　过程间循环兴趣路径剖析

这一节主要描述了PISP方法的实现细节。PISP方法是将PIP方法和PSP方法相结合，PIP方法用于剖析过程间循环路径，而PSP用于剖析过程内循环路径。

PISP方法中，我们首先使用PIP方法根据过程间控制流图和调用关系生成相应的PCCG图，生成PCCG图时采用SC（Single-procedure Cluster）集簇策略，即每个方法单独作为一个簇。而后在每一个方法内部使用PSP0方法装插探针，即先使用PAP算法得到相应的探针，再在CFG必要的位置计算兴趣路径的临时编码，并以该临时编码装插路径检测的探针。

算法.PISP（G,CG,PI）

输入:G带剖析的CFG

3　实验分析

本节对PISP方法进行测试，在基准程序上对PISP 和PIP方法进行比较，以验证PISP方法的有效性，根据上一节的理论分析，PISP可以精确地剖析过程间的循环路径，PIP可以精确的剖析过程间路径，所以PISP的剖析效率要比PIP高。

对于基准程序的选择，有如下几个原则：①包的入口方法为static类型一边构建测试用例；②以入口函数及其可达的方法所构建的调用图必须包含较多的调用边；③入口方法的参数必须易于构建。在JDK中我们按照这三个准则选择其中4个作为测试程序。如表1所示：

首先我们给出PISP方法（使用一条兴趣路径）和PIP方法的装插后的4个基准函程序的时间，如图2 所示，图中Original系列指的是未装插之前的程序执行时间，PIP系列是指使用PIP方法并按照SC集簇策略装插后的程序执行时间，PISP系列是指使用PISP方法装插后的程序执行时间。

由图2 的结果可以看出，PISP方法是有效的，在四个基准程序上，使用PISP方法剖析使得剖析的时间普遍有所减少，其中writeAdobeSegment函数的剖析时间耗费有了明显的减少，从0.913ms降到了0.6934ms，这是程序执行时间的长短，除与原始程序单次执行时间有关之外，还与程序的调用数目、程序节点总数、程序循环总数、循环体节点占总结点的比例有关。

图2　PISP和PIP执行时间的对比

表1　符合条件的JDK入口方法及其调用边信息

[1]Ball T,Larus J R.Programs Follow Paths.Microsoft Research,Washington:Technical Report MSR-TR-99-01,1999.

[2]Bodik R,Gupta R,Soffa M L.Inter-Procedural Conditional Branch Elimination.Proceedings of the ACM SIGPLAN Conference on Programming Language Design and Implementation（PLDI）,Las Vegas,USA,1997:146-158.

[3]Fisher J A.Trace Scheduling:A Technique for Global Microcode Compaction.IEEE Transactions on Computer,1981,C-30:478-490.

[4]Ammons G,Larus J R.Improving Data Flow Analysis with Path Profiles.Proceedings of the ACM SIGPLAN Conference on Progranning Language Design and Implementation（PLDI）,Montreal,Canada1998:72-84

[5]Ball T,Larus J R.Efficient Path Profiling.Proceedings of 29th Annual ACM/IEEE International Symposium on Microarchitecture（Micro）.Paris,France,1996:46-57.

[6]Tallam S,Zhang X,Gupta R.Extending path Profiling Across Loop Backedges and Procedure Boundaries.In:Proc.of the Int'l Symp.on Code Generation and Optimization:Feedback-Directedand Runtime Optimization（CGO）.Washington:IEEE Com-puter Society,2004.251?264.[doi:10.1109/CGO.2004.1281679]

[7]Roy S,Srikant YN.Profiling K-iteration Paths:A Generalization of the Ball-Larus Profiling Algorithm.In:Proc.of the 2009 Int'l Symp.on Code Generationand Optimization（CGO）.Washington:IEEE Computer Society,2009.70?80.[doi:10.1109/ CGO.2009.11]

[8]Wang Lu-Lu,Li Bi-Xin,Zhou Xiao-Yu.Profiling All Paths.Journal of Software,?2012,?23（6）:1413-1428.

[9]王璐璐,李必信.一种面向有环兴趣路径的过程内剖析方法.计算机学报[0254-4164]年:2014卷:37期:12页:2464-2481.

[10]王璐璐,李必信.过程间循环路径剖析方法.计算机学报，2013，11（11）:2224-2235.

Path Profiling;Inter-Procedural;Interesting Paths;Dynamic Analysis

An Approach of Profiling Inter-Procedural Selected Paths with Loops

LUO Fang
（College of Computer Science,Sichuan University,Chengdu 610065）

罗芳（1991-），女，四川资阳人，硕士研究生，研究方向为动态分析

2015-12-08

2016-01-12

提出一种新的过程间循环路径选择性剖析方法PISP，可以精确地剖析带有循环的过程间兴趣路径。该方法是将PIP 和PSP方法相结合，在过程间采用PSP生成相应的PCCG图，之后在过程内使用PIP方法来进行剖析。理论分析和实验评估表明PISP方法能够精确地剖析过程间循环兴趣路径并使用兴趣路径来提升剖析效率。

Proposes an approach called PISP to profile inter-procedural selected paths,which enables custom selection for inter-procedural paths. The method is a combination of PIP and PSP,in the process using PSP to generate the corresponding PCCG diagram,and then use the PIP method to profile the process.Theoretical analysis and experimental evaluation indicate that PISP performs effectively in optimization of selective profiling.