Paper Info
Title
Completeness of automatically generated instruction selectors
Abstract
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.
Year
DOI
Venue
2010
10.1109/ASAP.2010.5540994
ASAP
Keywords
Field
DocType
Completeness Test,Dynamic Check,Instruction Selection,Processor Description Language,Tree Pattern Matching
Automata theory,Programming language,Instruction set,Computer science,Instruction selection,Static analysis,Parallel computing,Code generation,Compiler,Theoretical computer science,Machine code,Pattern matching
Conference
ISSN
Citations 
PageRank 
2160-0511
1
0.35
References 
Authors
14
1
Name
Order
Citations
PageRank
Florian Brandner120214.97