Completeness of automatically generated instruction selectors

Florian Brandner

Research output: Chapter in Book/Report/Conference proceedingArticle in proceedingsResearchpeer-review


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.
Keyword: Generators,Automata,Tree Pattern Matching,Completeness Test,Program processors,Radiation detectors,Dynamic Check,Instruction Selection,Pattern matching,Grammar,Processor Description Language,Semantics
Original languageEnglish
Title of host publication21st IEEE International Conference on Application-Specific Systems, Architectures and Processors
Place of PublicationNew York
Publication date2010
ISBN (Print)978-14-24-46966-6
ISBN (Electronic)978-1-4244-6965-9
Publication statusPublished - 2010
Externally publishedYes
Event21st IEEE International Conference on Application-specific Systems, Architectures and Processors - Rennes, France
Duration: 7 Jul 20109 Jul 2010
Conference number: 21


Conference21st IEEE International Conference on Application-specific Systems, Architectures and Processors
Internet address


Dive into the research topics of 'Completeness of automatically generated instruction selectors'. Together they form a unique fingerprint.

Cite this