Program analysis and optimization for machines with instruction cache
Scott McFarling · 1992
In modern processors, the performance of the memory hierarchy is crucial in determining the overall performance of a CPU. Among the most important factors in deciding the performance of a CPU is the cache performance, and particularly, the cache miss rate. Determining and improving the hit rate of a cache is one of the most important tasks undertaken by a computer designer. Exploring the set of alternative cache organization is quite expensive, since the designer has a large number of cache design parameters at his disposal, and because the primary technique used for evaluating caches, trace-driven simulation, is very expensive. Additionally, because of tradeoffs in a cache design, the maximum performance achievable with a pure hardware solution is limited. This thesis presents a model of instruction caches that accurately predicts instruction cache behavior using easily obtained profile information. The model provides information useful to memory hierarchy designers and to programmers interested in developing algorithms with improved instruction cache performance. In addition, an automatic optimizer is described that reduces the instruction cache miss rate by 80% for a set of 10 large Pascal programs with a 32KB direct-mapped instruction cache. The model can also be used by other compiler optimizations that affect instruction cache performance. In particular, a new method of procedure merging is described that attempts to find the best procedures to inline when instruction cache effects are included. iv Acknowledgments Thanks to my advisor John Hennessy for providing such an interesting and challenging environment and numerous suggestions for improving this thesis. Thanks to Steve Richardson, Steve Tjiang, C. Y. Chu, Paul Chow, Malcolm Wing, Mark Horowitz, Arturo Sal...