TABLE OF CONTENTS We now turn to a discussion of how the various transformations that enhance register usage fit together, illustrating the principles with a complete treatment of matrix multiplication.
Before turning to an extended example of the register improvement strategies, we should comment on the order of transformations discussed in this chapter. One goal for that ordering is to change the original code as little as possible. That is, we should not make any change unless it improves the code's performance and, given two alternatives that provide roughly equal performance improvements, we should choose the one that changes the code the least. Keeping the code as close as possible to the original helps programmers understand the changes more easily.
That having been said, we present the recommended order of transformations for register allocation:
Loop interchange: Loop interchange should be done first because it brings reuse to the innermost loop, which should be a priority. Fusion might interfere with this process.
Loop alignment and fusion: This can achieve extra reuse across loops, particularly when compiling code generated by a preprocessor, such as a Fortran 90 front end (see Section 13.2).
Unroll-and-jam: This achieves outer loop reuse when there are dependences carried by other than the inner loop after interchange is finished.
Scalar replacement: This sets up the standard coloring-based register allocator by replacing array references that can be reused with scalar variables.
The use of all four of these steps...
