Pertinent path profiling: Tracking interactions among relevant statements

Acyclic path profiles are an indispensable tool geared towards multiple ends, with applications spanning from compiler optimizations to software engineering. Though such profiles provide an usable approximation to the program trace, many a times programmers are more interested in uncovering high-level interactions among a set of pertinent statements - not so much in the overall control-flow profile of the program. We propose a new profiling technique, Pertinent Path Profiling, which attempts to unveil such high-level interactions efficiently: given a control-flow graph and a set of pertinent basic-blocks (containing the relevant statements, Pertinent Path Profiling uniquely and efficiently identifies these high-level interactions, revealing execution demeanors that are otherwise difficult to discover via current control-flow profiling schemes. Additionally, if the number of pertinent basic-blocks is small, most of the time our algorithm yields much smaller path-frequency tables than those obtained by acyclic path profilers: if we are interested in a pertinent path profile with about 30% of the basic-blocks marked pertinent, most functions shrink their path-tables to about 15% of that of the acyclic path profiler. We illustrate a couple of possible applications of this new technology and provide experimental results on a set of benchmark programs to testify the utility of this new profiling technique.