A1 Refereed original research article in a scientific journal
Axioms as generic rewrite rules in C++ with concepts
Authors: Xiaolong Tang, Jaakko Järvi
Publisher: ELSEVIER SCIENCE BV
Publication year: 2015
Journal: Science of Computer Programming
Journal name in source: SCIENCE OF COMPUTER PROGRAMMING
Journal acronym: SCI COMPUT PROGRAM
Volume: 97
First page : 320
Last page: 330
Number of pages: 11
ISSN: 0167-6423
DOI: https://doi.org/10.1016/j.scico.2014.05.006
Web address : https://doi.org/10.1016/j.scico.2014.05.006
Abstract
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.
UTU Research Portal