Inter-Iteration Scalar Replacement in the Presence of Conditional Control-Flow

We revisit the classical problem of scalar replacement of array elements and pointer accesses. We generalize the state-of-the-art algorithm, by Carr and Kennedy CK94, to handle a combination of both conditional control-flow and inter-iteration data reuse. The basis of our algorithm is to make the dataflow availability information precise using a technique we call SIDE Statically Instantiate and Dynamically Evaluate. In SIDE the compiler inserts explicit code to evaluate the dataflow information at runtime. Our algorithm operates within the same assumptions of the classical one perfect dependence information and has the same limitations increased register pressure. It is, however, optimal in the sense that within each code region where scalar promotion is applied given sufficient registers each memory location is read and written at most once.