Marshall Kirk McKusick

EECS Department
University of California, Berkeley
Technical Report No. UCB/CSD-84-214
December 1984

http://www2.eecs.berkeley.edu/Pubs/TechRpts/1984/CSD-84-214.pdf

This dissertation investigates the problems of register allocation and intermediate language design in retargetable code generators. The goal is to develop tools that allow high quality code generators to be constructed rapidly.

Formal methods are used to attack the problem of register allocation in a Graham-Glanville table driven code generator. Previous work in register allocation has used a single register allocator following the code generator of the compiler. In this research, the register allocator is split into two phases, a global register allocator for variables and compiler temporaries within a procedure and a local register allocator for temporaries within an expression. The global register allocator is included in an optimizer that runs before code generation. The local register allocator is part of the code generator. Data flow information computed by the optimizer is passed to the local register allocator to suggest which temporaries are good candidates to be assigned to registers. The allocators are table driven so that they can be easily specified and changed.

Experiments were conducted on several multiple pass register allocator algorithms that use graph coloring. Metrics for evaluating the effectiveness of code generators are given and are used to evaluate the register allocation algorithms. Regardless of whether a global optimizer pass is made, the most effective local allocation algorithm improves the running time of a low level language, such as C, by only 1-2%. Higher level languages, such as Pascal, may be improved by as much as 8-10% because the language semantics reduce potential interference from aliasing.

The intermediate language that is passed from a language specific front end to a target machine dependent code generator must be both flexible and compact. General hints are given for the design of intermediate languages. Specific improvements are suggested for the intermediate language used by the UNIX compilers.

Advisor: Susan L. Graham

BibTeX citation:

@phdthesis{McKusick:CSD-84-214,
    Author = {McKusick, Marshall Kirk},
    Title = {Register Allocation and Data Conversion in Machine Independent Code Generators},
    School = {EECS Department, University of California, Berkeley},
    Year = {1984},
    Month = {Dec},
    URL = {http://www2.eecs.berkeley.edu/Pubs/TechRpts/1984/5933.html},
    Number = {UCB/CSD-84-214},
    Abstract = {This dissertation investigates the problems of register allocation and intermediate language design in retargetable code generators.  The goal is to develop tools that allow high quality code generators to be constructed rapidly.  <p>  Formal methods are used to attack the problem of register allocation in a Graham-Glanville table driven code generator. Previous work in register allocation has used a single register allocator following the code generator of the compiler.  In this research, the register allocator is split into two phases, a global register allocator for variables and compiler temporaries within a procedure and a local register allocator for temporaries within an expression. The global register allocator is included in an optimizer that runs before code generation. The local register allocator is part of the code generator. Data flow information computed by the optimizer is passed to the local register allocator to suggest which temporaries are good candidates to be assigned to registers. The allocators are table driven so that they can be easily specified and changed.  <p>  Experiments were conducted on several multiple pass register allocator algorithms that use graph coloring. Metrics for evaluating the effectiveness of code generators are given and are used to evaluate the register allocation algorithms. Regardless of whether a global optimizer pass is made, the most effective local allocation algorithm improves the running time of a low level language, such as C, by only 1-2%. Higher level languages, such as Pascal, may be improved by as much as 8-10% because the language semantics reduce potential interference from aliasing.  <p>  The intermediate language that is passed from a language specific front end to a target machine dependent code generator must be both flexible and compact. General hints are given for the design of intermediate languages. Specific improvements are suggested for the intermediate language used by the UNIX compilers.}
}

EndNote citation:

%0 Thesis
%A McKusick, Marshall Kirk
%T Register Allocation and Data Conversion in Machine Independent Code Generators
%I EECS Department, University of California, Berkeley
%D 1984
%@ UCB/CSD-84-214
%U http://www2.eecs.berkeley.edu/Pubs/TechRpts/1984/5933.html
%F McKusick:CSD-84-214