Completeness of automatically generated instruction selectors

Florian Brandner 1
1 COMPSYS - Compilation and embedded computing systems
Inria Grenoble - Rhône-Alpes, LIP - Laboratoire de l'Informatique du Parallélisme
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.
Type de document :
Communication dans un congrès
François Charot, Frank Hannig, Jürgen Teich, and Christophe Wolinski. 21st IEEE International Conference on Application-specific Systems Architectures and Processors (ASAP), Jul 2010, Rennes, France. IEEE Computer Society, pp.175 - 182, 2010, 〈10.1109/ASAP.2010.5540994〉
Liste complète des métadonnées

https://hal-ens-lyon.archives-ouvertes.fr/ensl-00531354
Contributeur : Florian Brandner <>
Soumis le : mardi 2 novembre 2010 - 15:00:43
Dernière modification le : vendredi 20 avril 2018 - 15:44:23

Identifiants

Collections

Citation

Florian Brandner. Completeness of automatically generated instruction selectors. François Charot, Frank Hannig, Jürgen Teich, and Christophe Wolinski. 21st IEEE International Conference on Application-specific Systems Architectures and Processors (ASAP), Jul 2010, Rennes, France. IEEE Computer Society, pp.175 - 182, 2010, 〈10.1109/ASAP.2010.5540994〉. 〈ensl-00531354〉

Partager

Métriques

Consultations de la notice

205