TABLE OF CONTENTS We have shown a variety of dependence-based techniques to increase the reuse of array values in uniprocessor CPU registers on modern uniprocessors. These methods are particularly useful for floating-point registers because these are often used to hold single elements from array data structures. Therefore, traditional coloring- based register allocation strategies are ineffective for these registers. The methods include the following:
Scalar replacement, which exposes reuse of subscripted variables to scalar compilers with good register allocation
Unroll-and-jam, which transforms programs to exploit register reuse in outer loops
Loop interchange, to shift loops carrying the most reuse to the innermost position
Loop fusion with alignment, to bring uses from different loops in a program together in a single loop
These techniques have been shown to be applicable to loops that include control flow and have trapezoidal iteration ranges. An important contribution of this chapter is the introduction of a fast algorithm that uses the greedy heuristic to solve the weighted fusion problem, which naturally arises from profitability concerns for loop fusion.
