Dynamic memory disambiguation for array references

Abstract

Memory disambiguation, or alias analysis, is a key component of modern optimizing compilers. Any optimization that reorders or changes code containing memory operations must analyze the memory references to ensure that the original semantics of the program are not changed. The recent proliferation of machines able to exploit parallelism, either at the coarse grain or more commonly at the instruction level, has led to the development of sophisticated memory disambiguation algorithms. In particular, much work has been done on disambiguating array references across different loop iterations. While these algorithms can be very effective for certain classes of programs, there exist array references that cannot be disambiguated at compile time. Even references that theoretically can be disambiguated at compile time may require techniques that are much more sophisticated and expensive than currently used. In this paper, we present a new algorithm for dynamic memory disambiguation for array references that allows us to overcome limitations of static analysis. For array references that cannot be accurately analyzed at compile time, we defer the disambiguation process until run-time. We have implemented our analysis algorithm in a prototype version of the IBM XL compiler and used the generated information for several compiler optimizations: software pipelining with global instruction scheduling, loop-invariant motion and redundant load elimination. We evaluated the algorithm on an IBM POWER2 system using the SPEC92 benchmarks. We show that for numeric C benchmarks, dynamic memory disambiguation can greatly improve run-time performance. Perhaps more importantly, we show that even for the programs that cannot benefit from dynamic analysis, the overhead of our algorithm does not degrade performance.