Procedure Mapping Using Static Call Graph Estimation

Amir H. Hashemi, David R. Kaeli, and Brad Calder

Workshop on the Interaction between Compilers and Computer Architectures, San Antonio, Texas, February 1997


As the gap between memory and processor performance continues to grow, it becomes increasingly important to exploit cache memory effectively. One technique used by compiler and linkers to improve the performance of the cache is code reordering. Code reordering optimizations rearrange a program so that sections of the program with temporal locality will be placed next to each other in the final program layout.

A number of software approaches to code reordering have been proposed. Their goal is to reduce the number of cache line conflicts. Most of these schemes use profile data in order to reposition the code in the address space. In this paper we present a link-time procedure mapping algorithm which uses a call graph constructed without the use of profile data. We will refer to this scheme as static call graph estimation. In this approach we use program-based heuristics to statically estimate the behavior of the call graph. Then once the estimated weighted call graph is formed, we can employ various procedure remapping algorithms. Our results show that we were able to reduce instruction cache miss rates by 20% on average when using our estimated static call graph with modern procedure reordering algorithms.