Automatically Generating Back Ends Using Declarative Machine Descriptions

João Dias and Norman Ramsey

Despite years of work on retargetable compilers, creating a good, reliable back end for an optimizing compiler still entails a lot of hard work. Moreover, a critical component of the back end—the instruction selector—must be written by a person who is expert in both the compiler's intermediate code and the target machine's instruction set. By generating the instruction selector from declarative machine descriptions we have (a) made it unnecessary for one person to be both a compiler expert and a machine expert, and (b) made creating an optimizing back end easier than ever before.

Our achievement rests on two new results. First, finding a mapping from intermediate code to machine code is an undecidable problem. Second, using heuristic search, we can find mappings for machines of practical interest, in at most a few minutes of CPU time.

Our most significant new idea is that heuristic search should be controlled by algebraic laws. Laws are used not only to show when a sequence of instructions implements part of an intermediate code, but also as the primary heuristic for limiting the search: we drop a sequence of instructions not when it gets too long or when it computes too complicated a result, but when too much reasoning will be required to show that the result computed might be useful.

A crucial invariant of our search is that we consider only computations that we know can be implemented entirely by machine instructions. This invariant makes our algorithm significantly simpler than earlier search algorithms, which start with goal computations whose implementations by machine instructions are not known.

Full paper

The paper is available as US Letter PostScript (351K), US Letter PDF (217K), US Letter TeX DVI (122K),