A program path records a program's control transfers through a sequence of consecutively executed basic blocks. Although a program's execution traces a single path, practicality demands this path be broken into shorter, more manageable path segments. The difficulty is that the number of potential paths through a program with loops is unbounded, which makes individual paths difficult to identify and name. On the other hand, a complete path can be assembled from shorter subpaths, such as Ball and Larus's acyclic paths.
Paths are a useful for two reasons. First, they concisely capture the execution history of many instructions, and so record a program's dynamic control flow. The set of (acyclic) paths executed by a program, its path spectra, compactly describes much of the program's dynamic behavior. Second, the control locality of paths is even more pronounced than code locality in a program as whole. Code locality is typified by the 80-20 rule-the observation that 80% of a program's execution occurs in only 20% of its code. If programs are viewed as a collection of paths, the 80-20 rule becomes the 100-0 rule, since programs execute only a miniscule fraction of the possible paths through the nearly infinite maze of their flow graph. The 80-20 rule reappears, however, within the domain of executed paths, as programs spend most of their time in a small number of "hot paths."
PP is a fast path profiler. A path profiler associates event counts with paths through programs. For example, the events can be simply the beginnings of new paths, in which case the profile just counts the number of times each path executes, or the events can be hardware events like data cache misses, in which case the profile counts the number of times each path suffered a cache miss.
PP does two different kinds of path profiling: flow profiling and context profiling. In flow profiling, the paths are acyclic, intraprocedural paths through control flow graphs. In context profiling, the paths are paths in the call graph: events are associated with nodes in a data structure called the calling context tree, which is a bounded representation of the dynamic call tree.
PP is build on EEL, a library for editing executable files. EEL currently runs on SPARC-based machines (SunOS and Solaris). The machine-specific code in EEL and QPT2 is collected in a few files. Porting to a new machine requires a couple months of effort.
HPB (Hot Path Browser) is a Java tool that can display the paths that a program executes. It reads the output of PP and displays a program's executed path in several linked windows.
PP is distributed along with EEL, which is available as part of WARTS.
PP is distributed with the full source and a small amount of documentation. PP is copyrighted by James Larus and Glenn Ammons and is distributed under the terms of the WARTS license. A copy of the license is available on ftp.cs.wisc.edu in ~ftp/pub/warts/license.ps, or can be obtained by contacting me at the address below.
James Larus
Computer Sciences Department
1210 West Dayton Street
University of Wisconsin
Madison, WI 53706
larus@cs.wisc.edu
(608) 262-9519