Method, system, and computer program product for performing register promotion via load and store placement optimization within an optimizing compiler

摘要

A method, system, and computer program product for performing register promotion, that optimizes placement of load and store operations of a computer program within a compiler. Based on the observation that the circumstances for promoting a memory location's value to register coincide with situations where the program exhibits partial redundancy between accesses to the memory location, the system is an approach to register promotion that models the optimization as two separate problems: (1) the partial redundancy elimination (PRE) of loads and (2) the PRE of stores. Both of these problems are solved through a sparse approach to PRE. The static single assignment PRE (SSAPRE) method for eliminating partial redundancy using a sparse SSA representation representations the foundation in eliminating redundancy among memory accesses, enabling the achievement of both computational and live range optimality in register promotion results. A static single use (SSU) representation is defined allowing the dual of the SSAPRE algorithm, called SSUPRE, to perform the partial redundancy elimination of stores. SSUPRE is performed after the PRE of loads, taking advantage of the loads' having been converted into pseudo-register references so that there are fewer barriers to the movement of stores. Consequently, the compiler produces more efficient, register-promoted executable program code from the SSA representation.