Register Allocation over the Program Dependence Graph

Author : Norris, Cindy; Pollock, Lori L.
Booktitle : Proceedings of the ACM SIGPLAN 1994 conference on Programming Language Design and Implementation
Date : Jun 1994
Publisher : ACM Press
Pages : 266 – 277
Keyword(s) : Register allocation
Document Type : In Conference Proceedings

Abstract :

This paper describes RAP, a Register Allocator that allocates registers over the Program Dependence Graph (PDG) representation of a program in a hierarchical manner. The PDG program representation has been used successfully for scalar optimization, the detection and improvement of parallelism for vector machines, multiple processor machines, and machines that exhibit instruction level parallelism, as well as debugging, the integration of different versions of a program, and translation of imperative programs for data flow machines. 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. Our experimental results have shown that on average, code allocated registers via RAP executed 2.7% faster than code allocated registers via a standard global register allocator.

Paper Link