Improving register allocation for subscripted variables
David P. Callahan, Steve Carr, Ken Kennedy · ACM SIGPLAN Notices · 2004
Most conventional compilers fail to allocate array elements to registers because standard data-flow analysis treats arrays like scalars, making it impossible to analyze the definitions and uses of individual array elements. This deficiency is particularly troublesome for floating-point registers, which are most often used as temporary repositories for subscripted variables.In this paper, we present a source-to-source transformation, called scalar replacement , that finds opportunities for reuse of subscripted variables and replaces the references involved by references to temporary scalar variables. The objective is to increase the likelihood that these elements will be assigned to registers by the coloring-based register allocators found in most compilers. In addition, we present transformations to improve the overall effectiveness of scalar replacement and show how these transformations can be applied in a variety of loop nest types. Finally, we present experimental results showing that these techniques are extremely effective---capable of achieving integer factor speedups over code generated by good optimizing compilers of conventional design.
Cited by 246 works. doi:10.1145/989393.989428
Authors
References
- LINPACK Users' Guide
- Department of Computer Science
- Register allocation via coloring
- Register allocation & spilling via graph coloring
- The Structure of Computers and Computations
- Dependence graphs and compiler optimizations
- LINPACK User's Guide.
- Optimizing supercompilers for supercomputers
- Automatic translation of FORTRAN programs to vector form
- A data locality optimizing algorithm