Path-based compilation
Michael D. Smith, Paul C. Martin, Reginald Clifford Young · 1998
Many compilers use profiles of programs to direct the focus and degree of performance optimizations. Profiles are statistics from program runs, usually collected at individual points in the program text, e.g., branches, call sites, or memory accesses. But optimizations based on individual sample points in the program miss an important detail of program behavior: how pieces of the program relate to each other dynamically. A path profile collects statistics over paths (sequences of points) in the program, linking the statistics to the dynamic behavior. By instrumenting and collecting path profiles through a program, we can exploit this dynamic behavior, improving performance more than point profiling techniques have allowed. This thesis shows how to collect path profiles efficiently, then applies the path profiles to two optimizations, static correlated branch prediction and path-based superblock scheduling. These two optimizations address different performance aspects of modern machines; many other optimizations can also benefit from path profile information. Path profiles can be collected with asymptotic efficiency comparable to point profiles. This thesis reports wall-clock times for a path profiler that performs within a factor of five of the overhead of point profilers. Path-based static correlated branch prediction (SCBP) exhibits better branch prediction accuracy than previously thought possible for static prediction techniques; cycle-level performance models show that SCBP improves performance on multiple-issue, deeply pipelined microprocessors like those being built today. In path-based superblock scheduling, path profiles guide the selection of blocks to build superblocks. Global instruction schedulers group instructions that are likely to execute together into scheduling regions and attempt to reduce program cycle counts by compacting regions. Path profiles improve on the former task over point profiles. This improvement translates to lower cycle counts to complete a program with code expansion and cache miss rates similar to or better than that of superblock selection using point profiles. Path profiling is practical and general; path profiles can be used to perform better optimizations. With tuning, path profiling overheads are similar to those of point profilers. This thesis demonstrates the generality of path statistics by exhibiting two optimizations that benefit from them, but many other optimizations can use the more detailed characterization of program behavior that path profiles provide.