Rastislav Bodik, Rajiv Gupta
The performance of scientific programs on modern processors can be significantly degraded by memory references that frequently arise due to load and store operations associated with array references. We have developed techniques for optimally allocating registers to array elements whose values are repeatedly referenced over one or more loop iterations. The resulting placement of loads and stores is optimal in that the number of loads and stores encountered along each path through the loop is minimal for the given program branching structure. The placement of shifts minimizes the average number of shifts per loop iteration.
To place load, store, and register-to-register shift operations without introducing fully/partially redundant and dead memory operations, a detailed value flow analysis of array references is required. We present an analysis framework to efficiently solve various data flow problems required by array load-store optimizations. The framework determines the collective behavior of recurrent references spread over multiple loop iterations. We also demonstrate how our algorithms can be adapted for various fine-grain architectures.
As applications of the framework we develop techniques for determining the placement of loads, stores, and register-to-register shift operations at points such that placement of fully/partially redundant and dead memory operations is avoided. We avoid redundant and dead operations that are exposed by examining a single loop iteration as well as multiple loop iterations.
Keywords: data flow analysis, data dependence analysis, load-store optimizations, partial redundancy elimination, partial dead code elimination.