Inter-Iteration Scalar Replacement in the Presence of Conditional Control-Flow
CARNEGIE-MELLON UNIV PITTSBURGH PA SCHOOL OF COMPUTER SCIENCE
Pagination or Media Count:
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.
- Numerical Mathematics
- Computer Programming and Software