Compilation wide alias analysis

Abstract

The intermediate code in a compiler can be divided into three broad categories: register operations, branching instructions, and storage operations. Register operations and branch instructions1 have transparent semantics, i.e. they are easy to understand. Storage operations are more difficult to understand because of their underlying addressing computations. Because many different address expressions can map to the same address, care must be taken when either reordering or removing memory operations to assure that the source program still computes the same result. While there is a one-to-one mapping between the register operations and values computed in the program, no simple relationship exists for the storage operations. Loads and stores typically reference sets of memory locations, and two seemingly independent address expressions may evaluate to the same storage location. Thus, while it is fairly straight-forward to reorder register operations, the ability to reorder storage operations is limited by the ability to reason about the addresses that may be created in the reordered computations. The analysis of the computations that produce the addresses is called alias analysis. In the absence of alias analysis, each write operation becomes a barrier that no other memory reference can cross. Barriers inhibit many optimizations, especially those that attempt to either remove redundant computations, or move operations to locations where the execution is less costly. We present both an alias analysis phase as well as several transformations that make use of this information. The paper concludes with some simple measurements as well as directions for further work.