TABLE OF CONTENTS Allen and Kennedy pioneered the use of dependence for optimization of register use on vector machines in the paper "Vector Register Allocation" [22] and in Allen's dissertation [16]. John Cocke proposed the technique of unroll-and-jam for use in the RS/6000, one of the first machines with extremely long latencies for cache misses. The idea was first published in the original paper by Callahan, Cocke, and Kennedy [55]. The idea of using scalar replacement to achieve register reuse on uniprocessors was due to Carr and Kennedy [67]. Carr implemented scalar replacement and unroll-and-jam and reported on its effectiveness in a series of papers with Callahan and Kennedy [65, 66]. Algorithms for pruning the dependence graph were developed by Brandes [43], Rosene [237], and Carr [64]. Handling of complex loop nests was also due to Carr and Kennedy [66].
Loop alignment was originally discussed by Allen, Callahan, and Kennedy as a way to eliminate carried dependences in parallelization [25]. The applicability of alignment to improve opportunities for register reuse after fusion is new, although it has been studied as a mechanism for cache reuse improvement [103, 105].
The greedy weighted fusion algorithm presented in this chapter is due to Kennedy [171, 172]. Kennedy and McKinley [176] developed the original proof that weighted fusion is NP-complete and presented a heuristic strategy based on repetitive application of Goldberg and Tarjan's maximum flow algorithm for networks [176]. The resulting algorithm takes time O( kEV log ( V 2
