Hard‐coding bottom‐up code generation tables to save time and space

Abstract

Code generators based on bottom‐up rewrite systems (BURS) are automatically generated from machine‐description 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.