ARRAY DATA-FLOW ANALYSIS FOR LOAD-STORE OPTIMIZATIONS IN FINE-GRAIN ARCHITECTURES

The performence of scientific programs on modern processors can be sig nificantly degraded by memory references that frequently arise due to load and store operations associated with array references. We have de veloped techniques for optimally allocating registers to array element s whose values are repeatedly referenced over one or more loop iterati ons. The resulting placement of loads and stores is optimal in that nu mber of loads and stores encoutered along each path through the loop i s minimal for the given program branching structure, To place load, st ore, and register-to-register shift operations without introducing ful ly/partially redundant and dead memory operations, a detailed value fl ow analysis of array references is required. We present an analysis fr amework to efficiently solve various data flow problems required by ar ray 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 fin e-grain architectures.