In path profiling, a program is instrumented with code that counts the number of times particular path fragments of the program are executed. This paper extends the intraprocedural path-profiling technique of Ball and Larus to collect information about interprocedural paths (i.e., paths that may cross procedure boundaries).

Interprocedural path profiling is complicated by the need to account for a procedure's calling context. To handle this complication, we generalize the ``path-naming'' scheme of the Ball-Larus instrumentation algorithm. In the Ball-Larus work, each edge is labeled with a number, and the ``name'' of a path is the sum of the numbers on the edges of the path. Our instrumentation technique uses an edge-labeling scheme that is in much the same spirit, but to handle the calling-context problem, edges are labeled with functions instead of values. In effect, the edge-functions allow edges to be numbered differently depending on the calling context. A key step in the process of creating the proper edge functions is related to a method proposed by Sharir and Pnueli for solving context-sensitive interprocedural dataflow-analysis problems.

Some of the machinery that we develop to handle the calling-context problem for purposes of interprocedural path profiling suggests other variants of both intraprocedural and interprocedural path profiling, as well as a variety of hybrid intra-/interprocedural schemes.

(Click here to access the paper: PostScript, PDF.)