A Code Reordering Transformation for Improved Cache Performance

We prove theorems that show that if we can reorder a program's memory refer-ence stream such that the reordered memory reference stream satises a disjointness property, then the transformed program corresponding to the reordered stream is guar-anteed to have fewer misses for any cache with arbitrary size or organization so long as the cache uses the LRU replacement policy. We can apply these results to reorder instructions within a basic block, to transform loops, to reorder blocks within a pro-cedure, or to reorder procedures within a program so as to improve hit rate for any cache that uses LRU replacement. Based on these theorems, we develop algorithmic methods for program transforma-tion to improve cache performance. While there has been a lot of work in improving cache performance using program transformations, our work diers from previous work in that it can be applied at many dierent levels, from the basic block to procedural levels, and does not require xing the size or organization of a cache prior to program transformation. We present preliminary experimental results that show that reordering based on our methods can result in signicant improvements in hit rate and program performance.