Run-time disambiguation: coping with statically unpredictable dependencies

A technique called run-time disambiguation (RTD) is presented for antialiasing of indirect memory references that cannot normally be disambiguated at compile time. The technique relies on assumptions about the run-time behavior of a program to allow static transformations of the code, in an effort to extract parallelism. The importance of the technique lies in its ability to supplement (and even partially replace) more expensive fully static dependency analysis. RTD works even in situations where the fully static approach is completely ineffective. Evidence of the importance of memory disambiguation in general, and RTD in particular, for parallelizing compilers, is presented. The implementation and effectiveness of the technique in the context of the Bulldog compiler is discussed