A1 Vertaisarvioitu alkuperäisartikkeli tieteellisessä lehdessä
Axioms as generic rewrite rules in C++ with concepts
Tekijät: Xiaolong Tang, Jaakko Järvi
Kustantaja: ELSEVIER SCIENCE BV
Julkaisuvuosi: 2015
Journal: Science of Computer Programming
Tietokannassa oleva lehden nimi: SCIENCE OF COMPUTER PROGRAMMING
Lehden akronyymi: SCI COMPUT PROGRAM
Vuosikerta: 97
Aloitussivu: 320
Lopetussivu: 330
Sivujen määrä: 11
ISSN: 0167-6423
DOI: https://doi.org/10.1016/j.scico.2014.05.006
Verkko-osoite: https://doi.org/10.1016/j.scico.2014.05.006
Tiivistelmä
Compilers are typically hardwired to attempt many optimizations only on expressions that involve particular built-in types. Ideally, however, an optimizing compiler would recognize a rewrite opportunity for user-defined types as well, whenever the operands of an expression satisfy the algebraic properties that justify the rewrite. This paper applies the principles and techniques of generic programming and the "concepts" language feature, that was proposed to C++, to approximate this ideal. Concretely, a concept defines the signature and algebraic laws of a class of types. We attach rewrite rules to a concept, and by doing this make them applicable to the entire class of types that the concept defines. The annotation burden to a programmer is small-we take the-existing-declarations that a type models a particular concept as the annotation that enables generic rewrites. To apply generic rewrite rules, we instantiate them to type-specific rules. We use data flow information from the compiler's existing analyses to determine when these rules can be applied, and show how to interleave their application with function inlining to find more rewrite opportunities. Our prototype is implemented as an extension of the ConceptGCC compiler; our experiments show the approach is effective in eliminating abstraction penalties. (C) 2014 Elsevier B.V. All rights reserved.
Compilers are typically hardwired to attempt many optimizations only on expressions that involve particular built-in types. Ideally, however, an optimizing compiler would recognize a rewrite opportunity for user-defined types as well, whenever the operands of an expression satisfy the algebraic properties that justify the rewrite. This paper applies the principles and techniques of generic programming and the "concepts" language feature, that was proposed to C++, to approximate this ideal. Concretely, a concept defines the signature and algebraic laws of a class of types. We attach rewrite rules to a concept, and by doing this make them applicable to the entire class of types that the concept defines. The annotation burden to a programmer is small-we take the-existing-declarations that a type models a particular concept as the annotation that enables generic rewrites. To apply generic rewrite rules, we instantiate them to type-specific rules. We use data flow information from the compiler's existing analyses to determine when these rules can be applied, and show how to interleave their application with function inlining to find more rewrite opportunities. Our prototype is implemented as an extension of the ConceptGCC compiler; our experiments show the approach is effective in eliminating abstraction penalties. (C) 2014 Elsevier B.V. All rights reserved.
Turun yliopiston Tutkimustietojärjestelmän portaali