The design and implementation of RAP: a PDG-based register allocator
Cindy Norris, Lori Pollock · Software Practice and Experience · 1998
This paper describes the design and implementation of a register allocator that performs the allocation over the Program Dependence Graph (PDG) representation of a routine. The PDG representation has been used successfully as the basis for various scalar optimizations, as well as for detecting and improving parallelization for vector machines, multiple processor machines, and architectures that exhibit instruction level parallelism. Variations of the PDG have also been used for debugging and integrating different versions of a program via program-slicing, and to enable translation of imperative programs for data-flow machines and demand-driven graph reducers. By basing register allocation on the PDG, the register allocation phase may be more easily integrated and intertwined with other optimization analyses and transformations. In addition, the advantages of a hierarchical approach to global register allocation can be attained without constructing an additional structure used solely for register allocation. © 1998 John Wiley & Sons, Ltd.