The vpo compiler [3] attempts to calculate relative addresses for each data reference associated with load and store instructions after compiler optimizations have been performed (see Figure 1), which may not be trivial, especially for non-scalar data references. Compiler optimizations can move instructions between basic blocks and outside of loops so that expansion of registers used in the address calculation becomes more difficult. Our approach calculates relative data address information automatically after all compiler optimizations have been performed.
First, the compiler determines for each loop the set of its induction variables, their initial values and strides, and the loop-invariant registers. Next, expansion of actual parameter information is performed in order to be able to resolve any possible address parameters later. Then, expansion of addresses used in loads and stores is performed. Expansion is accomplished by examining each preceding instruction represented as an RTL (register transfer list) and replacing registers used as source values in the address with the source of the RTL setting that register. Induction variables associated with a loop are not expanded. Loop invariant values are expanded by proceeding to the end of the preheader block of that loop. Expansion of the addresses of scalar references to the run-time stack (e.g. local variables) is trivial. Expansion of references to static data (e.g. global variables) often requires expanding loop invariant registers since these addresses are constructed with instructions that may be moved out of a loop. Although, there is not room in this paper to give examples of calculating relative addresses of data memory references, we did find many instances where traditional techniques for calculating ranges of relative addresses were not adequate due to
Figure 3: Algorithm to Calculate Data Cache States
Figure 2: Virtual Address Space (SunOS)
interference from various compiler optimizations. For more details on statically determining address information from fully optimized code see [16].