羅芳

（四川大學(xué)計算機學(xué)院，成都　610065）

過程間循環(huán)興趣路徑剖析方法

羅芳

（四川大學(xué)計算機學(xué)院，成都610065）

路徑剖析；過程間路徑；興趣路徑；多態(tài)；動態(tài)分析

0　引言

路徑剖析作為動態(tài)軟件分析的一個重要領(lǐng)域，其目的在于：根據(jù)大量執(zhí)行情況，給出執(zhí)行路徑的執(zhí)行頻率，主要應(yīng)用于計算機架構(gòu)、程序編譯、調(diào)試、測試和軟件維護等方面有著重要的應(yīng)用[1]，同時還可以應(yīng)用在路徑敏感代碼的優(yōu)化[2]、代碼布局優(yōu)化[3]以及靜態(tài)分支預(yù)測的改進[4]等方面。

為了獲取執(zhí)行的路徑和頻率,剖析方法需要在目標(biāo)程序中裝插探針（probe），接下來是在程序執(zhí)行過程中計算探針值并收集執(zhí)行信息，最后根據(jù)路徑末端的探針值（路徑編碼）和相關(guān)信息各條路徑的執(zhí)行次數(shù)。而在每次程序執(zhí)行完畢后，使用探針變量值來唯一確定執(zhí)行路徑的編碼，而要保證剖析結(jié)果的精確性，每條可剖析路徑的編碼必須是唯一的。

現(xiàn)有的剖析方法可分為過程內(nèi)剖析和過程間剖析，也可分為選擇性剖析和非選擇性剖析。1996年Ball等人提出了首個路徑剖析方法EPP（Efficient Path Profiling）[5]是一種過程內(nèi)非選擇性剖析方法，可以十分精確、高效地剖析過程內(nèi)的所有無環(huán)CFG（Control Flow Graph）的路徑。

之后出現(xiàn)的方法有些致力于提升循環(huán)處理能力。例如2004年Tallam提出的過程內(nèi)有環(huán)路徑近似剖析方法ExPP（Extended Path Profiling）[6]，可以精確地剖析循環(huán)次數(shù)在兩次以內(nèi)的路徑。而Roy等人在ExPP的基礎(chǔ)上改進提出了kIPP（Profiling k-iteration paths）[7]可以剖析含有k次以內(nèi)的循環(huán)路徑。而王璐璐等人在EPP的基礎(chǔ)上改進提出的PAP（Profiling All Paths）,可以剖析任意有限次循環(huán)的路徑。

有的方法著重在將路徑剖析擴展到選擇性剖析?；贓PP，Apiwattanapong提出了SPP（Selective Path Profiling），Viswani等人提出了PrePP（Preferential Path Profiling），這兩種方法都可以進行選擇性剖析，區(qū)別在于SPP方法會分配較大權(quán)值給興趣路徑中的邊，以降低非興趣路徑的編碼，而PrePP方法分配較小的權(quán)值給興趣路徑中的邊，以壓縮興趣路徑的編碼，使其能夠使用數(shù)組存儲以提高效率。而ESPP算法是對SPP的改進，可以有效地保證剖析的精確度。但是這些方法都不能很好地剖析循環(huán)路徑。所以又有研究人員提出了PSP（Profiling Selected Paths）方法，可以剖析有環(huán)CFG的路徑。

目前的研究人員主要致力于以上兩個方向的研究，對于已有剖析方法，或能夠精確地剖析過程間循環(huán)路徑，或能夠剖析過程內(nèi)興趣路徑，而很少有文獻討論過程間循環(huán)興趣路徑的剖析，本文結(jié)合了PIP（Profiling Inter-Procedural Paths）方法剖析過程間循環(huán)路徑的特點和PSP（Profiling Selected Paths with Loop）方法剖析興趣路徑的特點提出了一種剖析過程間循環(huán)興趣路徑（PISP）的方法，旨在提高過程間循環(huán)路徑的剖析效率。

1　相關(guān)介紹

1.1PIP

PIP[9]能夠精確地剖析過程間帶有循環(huán)的路徑。為了描述多態(tài)調(diào)用信息，PIP中提出了一種方法調(diào)用模型——PCCG（Polymorphic Cluster Call Grapth），圖1 為一個PCCG的示例，圖1（a）給出了一個具有5個方法的調(diào)用圖，包含了方法的調(diào)用關(guān)系和覆蓋關(guān)系。其中有兩個調(diào)用關(guān)系（實線所示），A指向B，C指向D，同時包含了三個覆蓋關(guān)系（虛線所示），分別是C覆蓋A，D覆蓋B和E覆蓋D。

在圖1（a）的基礎(chǔ)上可以通過一下3個步驟得到相應(yīng)的PCCG圖，并可將所有可能的調(diào)度包含在轉(zhuǎn)化后的PCCG中：

①如圖1（b）,在圖1（a）中添加3條潛在調(diào)用邊：AD、AE和CE，以拆分多態(tài)調(diào)用邊；

②在拆分多態(tài)調(diào)用邊的基礎(chǔ)上，如圖1（c）所示將方法A和C歸為一簇，將B、D、E歸為一簇，若方法A有調(diào)用另一個簇中的方法C，則方法A有一條調(diào)用邊指向C所在的方法簇，再刪除冗余的調(diào)用邊；

圖1　PCCG示例圖

③如圖1（d）所示如果方法C調(diào)用的另一個簇中的方法D，則D所在的方法簇中每一個方法都添加一條返回邊指向C所在的方法簇。

而PIP方法是根據(jù)輸入的過程間控制流圖、過程調(diào)用關(guān)系和方法集簇得到PCCG圖，其中方法集簇策略有三種：策略SC（每個方法單獨作為一個簇）、策略IC（所有存在覆蓋關(guān)系的方法歸為一簇）、策略AC（所有方法歸為一簇）。然后再在PCCG模型上穿插探針，對于入度大于一的被調(diào)用簇的n條入邊，分別分配探針n（0），n（1），…，如圖1（d）所示，并根據(jù)探針對程序進行裝插，最后運行裝插后的程序，收集執(zhí)行路徑的編碼及其頻率，將之解碼為剖析結(jié)果。

1.2PSP

PSP能夠精確的剖析循環(huán)興趣路徑，并使用檢測非興趣路徑和提前終止技術(shù)兩種方法來降低耗費[10]，即如果在執(zhí)行過程中檢測到執(zhí)行路徑是非興趣路徑，則提前終止執(zhí)行以減少執(zhí)行時間。為盡可能早盡可能多的檢測出非興趣路徑，以減少PSP方法中提出了三種檢測技術(shù)：

①T1.檢測臨時編碼，其檢測依據(jù)是非興趣路徑和興趣路徑的臨時編碼在某些位置上不同，在執(zhí)行過程中如果發(fā)現(xiàn)當(dāng)前的臨時編碼不屬于任何一個興趣路徑，則提前結(jié)束；

②T2.檢查局部編碼，其依據(jù)是興趣路徑和非興趣路徑會在CFG執(zhí)行不同的路徑片段，在無環(huán)子圖上使用ESPP，并在子圖出口出檢查局部編碼，若發(fā)現(xiàn)執(zhí)行的是非興趣路徑，則提前結(jié)束；

③T3.檢測邊界邊集合，其依據(jù)是在興趣路徑上只會執(zhí)行興趣邊，執(zhí)行了邊界邊和無效邊的路徑肯定是非興趣路徑，所以可以在邊界邊上進行檢測。

基于上述三種檢測方法提出了PSP0～PSP3四種方法，PSP0使用T1檢測臨時編碼，PSP1使用T2檢測局部編碼，PSP2使用T3檢測邊界邊集合，而PSP3同時使用T2、T3，即同時檢測局部編碼和邊界邊集合。

PSP0需要進行路徑檢測其前驅(qū)有多條出邊的節(jié)點，首先使用PAP算法得到相應(yīng)的探針，再在CFG必要的位置計算興趣路徑的臨時編碼，并以該臨時編碼裝插路徑檢測的探針，其時間消耗為O（E+N*I），（E為CFG的邊數(shù)，N為節(jié)點數(shù)，I為興趣路徑的數(shù)目）。

PSP1使用ESPP的局部探針變量對RAS（無環(huán)子圖）進行選擇性剖析，并在RAS的出口處使用T2對局部編碼，若發(fā)現(xiàn)當(dāng)前執(zhí)行的不屬于興趣路徑，則體檢結(jié)束，若在RAS出口沒有找檢測到非興趣路徑，則將局部編碼結(jié)合到PAP的全局探針變量的計算之中，繼續(xù)執(zhí)行。其時間消耗為O（S*P’*E2+S*P’*E*I），其中S指的是CFG中無環(huán)子圖的數(shù)量，E指CFG的邊數(shù)，I為興趣路徑的數(shù)量，P’指的是各個無環(huán)子圖中靜態(tài)路徑數(shù)的上限。

PSP2在進行探針裝插時根據(jù)T3的檢測機制，需要在邊界邊上裝插提前結(jié)束的探針，使得無效邊不可達，并且在無效邊上刪除所有的探針，以簡化CFG，再使用PAP算法剖析簡化后的CFG，最后將探針前推以減少探針數(shù)量。算法的時間消耗是O（E*I），其中E是CFG的邊數(shù)，I是興趣路徑的總數(shù)。

PSP3是同時使用T2、T3兩種檢測方法，首先使用PSP2并刪除CFG中的非興趣路徑，以簡化CFG，然后應(yīng)用PSP1檢測在簡化后的CFG中的RAS（無環(huán)子圖）。算法的時間消耗為PSP1和PSP2的和，即O（S*P’*E2+S*P’*E*I+E*I）（參數(shù)含義參照PSP1和PSP2）。

2　過程間循環(huán)興趣路徑剖析

這一節(jié)主要描述了PISP方法的實現(xiàn)細節(jié)。PISP方法是將PIP方法和PSP方法相結(jié)合，PIP方法用于剖析過程間循環(huán)路徑，而PSP用于剖析過程內(nèi)循環(huán)路徑。

PISP方法中，我們首先使用PIP方法根據(jù)過程間控制流圖和調(diào)用關(guān)系生成相應(yīng)的PCCG圖，生成PCCG圖時采用SC（Single-procedure Cluster）集簇策略，即每個方法單獨作為一個簇。而后在每一個方法內(nèi)部使用PSP0方法裝插探針，即先使用PAP算法得到相應(yīng)的探針，再在CFG必要的位置計算興趣路徑的臨時編碼，并以該臨時編碼裝插路徑檢測的探針。

算法.PISP（G,CG,PI）

輸入:G帶剖析的CFG

3　實驗分析

本節(jié)對PISP方法進行測試，在基準(zhǔn)程序上對PISP 和PIP方法進行比較，以驗證PISP方法的有效性，根據(jù)上一節(jié)的理論分析，PISP可以精確地剖析過程間的循環(huán)路徑，PIP可以精確的剖析過程間路徑，所以PISP的剖析效率要比PIP高。

對于基準(zhǔn)程序的選擇，有如下幾個原則：①包的入口方法為static類型一邊構(gòu)建測試用例；②以入口函數(shù)及其可達的方法所構(gòu)建的調(diào)用圖必須包含較多的調(diào)用邊；③入口方法的參數(shù)必須易于構(gòu)建。在JDK中我們按照這三個準(zhǔn)則選擇其中4個作為測試程序。如表1所示：

首先我們給出PISP方法（使用一條興趣路徑）和PIP方法的裝插后的4個基準(zhǔn)函程序的時間，如圖2 所示，圖中Original系列指的是未裝插之前的程序執(zhí)行時間，PIP系列是指使用PIP方法并按照SC集簇策略裝插后的程序執(zhí)行時間，PISP系列是指使用PISP方法裝插后的程序執(zhí)行時間。

由圖2 的結(jié)果可以看出，PISP方法是有效的，在四個基準(zhǔn)程序上，使用PISP方法剖析使得剖析的時間普遍有所減少，其中writeAdobeSegment函數(shù)的剖析時間耗費有了明顯的減少，從0.913ms降到了0.6934ms，這是程序執(zhí)行時間的長短，除與原始程序單次執(zhí)行時間有關(guān)之外，還與程序的調(diào)用數(shù)目、程序節(jié)點總數(shù)、程序循環(huán)總數(shù)、循環(huán)體節(jié)點占總結(jié)點的比例有關(guān)。

圖2　PISP和PIP執(zhí)行時間的對比

表1　符合條件的JDK入口方法及其調(diào)用邊信息

[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]王璐璐,李必信.一種面向有環(huán)興趣路徑的過程內(nèi)剖析方法.計算機學(xué)報[0254-4164]年:2014卷:37期:12頁:2464-2481.

[10]王璐璐,李必信.過程間循環(huán)路徑剖析方法.計算機學(xué)報，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-），女，四川資陽人，碩士研究生，研究方向為動態(tài)分析

2015-12-08

2016-01-12

提出一種新的過程間循環(huán)路徑選擇性剖析方法PISP，可以精確地剖析帶有循環(huán)的過程間興趣路徑。該方法是將PIP 和PSP方法相結(jié)合，在過程間采用PSP生成相應(yīng)的PCCG圖，之后在過程內(nèi)使用PIP方法來進行剖析。理論分析和實驗評估表明PISP方法能夠精確地剖析過程間循環(huán)興趣路徑并使用興趣路徑來提升剖析效率。

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.