Inter-Iteration Scalar Replacement in the Presence of Conditional Control-Flow
Abstract
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.
Document Details
- Document Type
- Technical Report
- Publication Date
- Feb 01, 2004
- Accession Number
- ADA461114
Entities
People
- Mihai Budiu
- Seth C. Goldstein
Organizations
- Carnegie Mellon University