This paper presents an efficient procedure for path profiling.
Based on some well-known graph algorithms, such as the minimum
spanning tree algorithm, the authors successfully find a way
to assign an unique state for each path in a DAG, and add
optimized instrumentation such that the overhead is just about
30% for the SPEC95 benchmarks. With this low overhead, path
profiling can be more widely utilized to optimize compiler,
debuging and dynamic branch prediction.