Completeness of automatically generated instruction selectors

The use of tree pattern matching for instruction selection has proven very successful in modern compilers. This can be attributed to the declarative nature of tree grammar specifications, which greatly simplifies the development of fast high-quality code generators. The approach has also been adopted widely by generator tools that aim to automatically extract the instruction selector, as well as other compiler components, for application-specific instruction processors from generic processor models.

A major advantage of tree pattern matching is that it is suitable for static analysis and allows to verify properties of a given specification. Completeness is an important example of such a property, in particular for automatically generated compilers. Tree automata can be used to prove that a given instruction selector specification is complete, i.e., can actually generate machine code for all possible input programs.

Traditional approaches for completeness tests cannot represent dynamic checks that may disable certain matching rules during code generation. However, these dynamic checks occur very frequently in compilers targeting application-specific processors. The dynamic checks arise from hidden properties that are not captured by the terminal symbols of the tree grammar notation.

We apply terminal splitting to the instruction selector specifications that are automatically derived from structural processor models to make these properties explicit. The transformed specification is then verified using a traditional completeness test. If the test fails, counter examples are presented that allow to adopt the compiler or extend the processor model accordingly.