Journal of Software:2012.23(6):1413-1428

(东南大学 计算机科学与工程学院,江苏 南京 211189)
Profiling All Paths
WANG Lu-Lu,LI Bi-Xin,ZHOU Xiao-Yu
(School of Computer Science and Engineering, Southeast University, Nanjing 211189, China)
Chart / table
Similar Articles
Article :Browse 3565   Download 3157
Received:December 16, 2010    Revised:August 24, 2011
> 中文摘要: 路径剖析是动态分析的一项重要技术,通过获取和分析程序中各条路径的执行次数,在编译优化、软件调试和测试等诸多方面发挥重要作用.针对现有技术剖析能力不足的情况(即只能或者剖析非循环路径,或者首先界定循环体执行次数的上限、然后对于执行循环体不多于该次数的路径进行剖析),对使用单个探针变量剖析过程内路径的方法进行了改进,提出了全路径剖析PAP 方法,利用探针插装和回溯过程获取路径的执行次数,可以剖析过程内包含任意有限长度的路径;进一步地,针对PAP 方法所需探针数目多于EPP 方法的问题,通过对控制流图中包含的可规约无环子图实施EPP 方法,可以减少PAP 方法所需探针的数目.另外,作为PAP 方法的一个典型应用,还讨论了如何通过在方法调用图中添加返回边,再利用PAP 方法获取方法层次的执行序列的基本思想,满足了某些方法级动态影响分析技术的需要.实验和实例分析表明,PAP 在处理循环路径剖析的问题上是有效的,并有很好的效率.
Abstract:Path profiling, an important technique in dynamic program analysis, which collects the execution times of different paths, has been widely used in a variety of areas. However, existing intra-procedural profiling techniques have inadequate abilities in loops, i.e., they can only either solve profiling acyclic paths, or limit loop iterations to a certain number first, and then profile paths under such a limitation. This paper presents a new profiling technique called PAP (profiling all paths), which can profile finite-length paths inside a procedural. PAP consists of two basic phases: one is the probe instrumentation which assigns a unique pathid for each path, and the other is backwalk which uses the pathids to determine the corresponding executed paths. Furthermore, breakpoints are introduced to store the probe value which may overflow during long executions, and the probe amount is reduced base on the integration of PAP with an existing profiling technique. Besides, this paper also discusses how to use PAP to profile executed sequences on the method level. As shown in the results of the case study and experiments, PAP is effective and efficient in profiling cyclic paths.
文章编号:     中图分类号:    文献标志码:
基金项目:国家自然科学基金(60973149); 国家教育部博士点基金(20100092110022) 国家自然科学基金(60973149); 国家教育部博士点基金(20100092110022)
Foundation items:
Reference text:


WANG Lu-Lu,LI Bi-Xin,ZHOU Xiao-Yu.Profiling All Paths.Journal of Software,2012,23(6):1413-1428