Interprocedural Path Profiling

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 c..