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. Second, the control locality of paths is even more pronounced than code locality in a program as whole. 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.