THE DESIGN AND IMPLEMENTATION OF RAP - A PDG-BASED REGISTER ALLOCATOR

This paper describes the design and implementation of a register alloc ator that performs the allocation over the Program Dependence Graph (P DG) 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, mult iple processor machines, and architectures that exhibit instruction le vel parallelism. Variations of the PDG have also been used for debuggi ng and integrating different versions of a program via program-slicing , and to enable translation of imperative programs for data-flow machi nes 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 regis ter allocation can be attained without constructing an additional stru cture used solely for register allocation. (C) 1998 John Whey & Sons, Ltd.