Search

Many code-generator generators use tree pattern matching and dynamic programming. This paper describes a simple program that generates matchers that are fast, compact, and easy to understand. It is simpler than common alternatives: 200–700 lines of Icon or 950 lines of C versus 3000 lines of C for Twig and 5000 for burg. Its matchers run up to 25 times faster than Twig's. They are necessarily slower than burg's BURS (bottom-up rewrite system) matchers, but they are more flexible and still practical.

SUMMARY This paper describes the management of register spills in a retargetable C compiler. Spills are rare, which means that testing is a bigger problem than performance. The trade-offs have been arranged so that the common case (no spills) generates respectable code quickly and the uncommon case (spills) is less efficient but as simple as possible. The technique has proven practical and is in production use on VAX, Motorola 68020, SPARC and MIPS machines.

SUMMARY Code generators based on bottom-up rewrite systems (BURS) are automatically generated from machinedescription grammars. They produce locally optimal code for expression trees, but their tables are large and require compile-time interpretation. This paper describes a program that compiles BURS tables into a combination of hard code and data. Hard-coding exposed important opportunities for compression that were previously hidden in the tables, so the hard-coded code generators are not just faster but also significantly smaller than their predecessors. A VAX code generator takes 21.4Kbytes and identifies optimal assembly code in about 50 VAX instructions per node.