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 disambi- guation 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 systmem 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.
Talk
Overheads (0 bytes)