Browse Theses

A desirable organization for a compiler has a target machine independent, source language dependent front end, and a target machine dependent, source language independent back end. The two parts communicate through an intermediate representation (IR). The back end, also called a code generator, translates the IR to target machine instructions. The Graham-Glanville code generation method can be used as the basis for the code generator. The method uses a grammar of linearized instruction patterns to describe the target machine. An LR-like parser is used to cover the IR with instruction patterns. This dissertation develops the necessary techniques to make the Graham-Glanville approach a practical code generation method.

We describe a major experiment in which a production quality Graham-Glanville code generator was developed, retargeted to three different target machines, and used to translate real programs written in "C", Pascal and Fortran into good code for those machines. In the course of the experiment, we tested new code generation ideas, and developed several significant improvements to the method. A methodology is given to write machine description grammars to exploit the structure of the target machine. A syntactic approach has been developed, in which almost all semantic attributes required to select code are encoded directly into the grammar. This encoding simplifies the code generator, although it increases the size of the grammar. Tools are described that compensate for the grammatical size, and ease designing the grammar. The tools exploit properties of the IR, and encode attributes into the grammar. Despite the large grammars, the parser is quickly constructed by exploiting the observed properties of machine description grammars. A discussion of instances in which less than optimal code can be produced, and remedies for those instances is given. The aspects of the code generator design that facilitate retargeting are described. They include the use of IR transformations and the centralization of machine dependent information.

The retargeted code generators are compared with one another and with another code generator for the same front ends. An evaluation is given that demonstrates the success of our methods and the practicality of the Graham-Glanville approach.