Browse Prior Art Database

Code Generation and Machine Descriptions Disclosure Number: IPCOM000128907D
Original Publication Date: 1979-Dec-31
Included in the Prior Art Database: 2005-Sep-20

Publishing Venue

Software Patent Institute

Related People

R. G. G. Catted: AUTHOR [+3]


2. Formalization of Instruction Set Processors

This text was extracted from a PDF file.
This is the abbreviated version, containing approximately 4% of the total text.

Page 1 of 37


©; Copyright 1979 by Xerox Corporation; used with permission

Code Generation and Machine Descriptions

by R. G. G. Catted

CSL-79-8 Octobe r 1979


This is a collection of three papers covering a Ph.D. dissertation, "Formalization and Automatic Derivation of Code Generators," Cattell[1978]. The papers are revised reprints of versions appearing in the literature. The papers describe, respectively,

1. A code generator generator (this paper includes an overview of the thesis),

2. The model of machines (instruction set processors), and

3. The table~driven code generator and portions of the compiler in which it operates.

The tables for the code generator (3) are derived by the code generator generator (1) from the machine description (2). Thus the three papers describe the three main parts of the thesis work<.

CR Categories: 4.12

Key words and phrases: Code Generator Generator, Compiler-compiler, Machine [description, Optimizing Compiler, Code Generation, Compiler Generator, Computer Description

XEROX PALO ALTO RESEARCH CENTER 3333 Coyote Hill Road / Palo Alto / California 94304

Table of Contents

Automatic Derivation of Code Generators from Machine Descriptions

1. Introduction

2. Formalization of Instruction Set Processors

3. Formalization of Code Generation

4. Automatic Derivation of Code Generators

4.1 Tree Equivalence Axioms

4.2 Search

4.3 Example

4.4 Select

Dec 31, 1979

Page 1

Page 2 of 37

Code Generation and Machine Descriptions

5. Summary

5.1 Results 5.2 Limitations and Future Research

Machine Descriptions for Automatic Derivation of Code Generators

1. Automatic Generation of Machine-Dependent Software

2. Instruction Set Processors

3. Summary

4. Appendix: Example Machine Description

Code Generation in a Machine-lndependent Compiler

1. Introduction

2. Instruction Set Processor Formalization

3. Operations Preceding Code Generation

3.1 Context Determination

3.2 Unary Complement/Target path Determination

3.3 Evaluation Order

3.4 Flow Analysis

3.5 Access Mode Determination

3.6 Temporary Name Assignment

4. Operations Following Code Generation

5. Code Generation

5.1. Abstract Code Generation

5.2. The Code Generator 5.2.1. Overview 5.2.2. Pattern Matching 5.2.3. Reverse Code Generation 5.3 Use of Flow Analysis and Temporary Allocation Information

6. Summary


Dec 31, 1979

Page 2

Page 3 of 37

Code Generation and Machine Descriptions

I would like to thank Bill Wulf, Mario Barbacci, Allen Newell, Alice Parker, Joe Newcomer, John Oakley, Steve Saunders, Susan Graham, Chris Fraser, Bruce Schatz, Steve Hobbs, Steve Crocker, Bruce Leverett, and Doug Clark for their invaluable comments and conversations concerning my thesis work.

Automatic Derivation of Code Generators from Machine Descriptions

R. G. G. Cattell Carnegie-Mellon University


Work with compiler-compilers has dealt principally with automatic generation of parsers and lexical ana...