Refereed journal article or data article (A1)

Axioms as generic rewrite rules in C++ with concepts




List of 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 number: 97

Number of pages: 11

ISSN: 0167-6423

DOI: http://dx.doi.org/10.1016/j.scico.2014.05.006

URL: 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.


Last updated on 2021-24-06 at 10:51