Register Promotion by Partial Redundancy Elimination of Loads and Stores

Abstract

An algorithm for register promotion is presented 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 ac-cesses to the memory location. The recent SSAPRE al-gorithm for eliminating partial redundancy using a sparse SSA representation forms the foundation for the present al-gorithm to eliminate redundancy among memory accesses, enabling us to achieve both computational and live range op-timality in our register promotion results. We discuss how to effect speculative code motion in the SSAPRE framework. We present two different algorithms for performing specu-lative code motion: the conservative speculation algorithm used in the absence of profile data, and the the profile-driven