Automatic Code Generation Using Dynamic Programming: a Practical Approach

Building compiler back ends from declarative specifications that map tree structured intermediate representations onto target machine code is the topic of this book. Although many tools and approaches have been devised to tackle the problem of automated code generation, there is still room for improvement. In this context we present HBURG, an implementation of a code generator generator that emits compiler back ends from concise tree pattern specifications written in our code generator description language. The language features attribute grammar style specifications and allows for great flexibility with respect to the placement of semantic actions. Our main contribution is to show that these language features can be integrated into automatically generated code generators that perform optimal instruction selection based on tree pattern matching combined with dynamic programming. In order to substantiate claims about the usefulness of our language we provide two complete examples that demonstrate how to specify code generators for RISC and CISC architectures. Compiler writers are the primary target audience of this book.