Symbiotic expressions

Robert Bernecky, Stephan Herhut, Sven-Bodo Scholz

Research output: Chapter in Book/Report/Conference proceedingConference contribution

4 Citations (Scopus)

Abstract

We introduce symbiotic expressions, a method for algebraic simplification within a compiler, in lieu of an SMT solver, such as Yices or the Omega Calculator. Symbiotic expressions are compiler-generated expressions, temporarily injected into a program's abstract syntax tree (AST). The compiler's normal optimizations interpret and simplify those expressions, making their results available for the compiler to use as a basis for decisions about further optimization of the source program. The expressions are symbiotic, in the sense that both parties benefit: an optimization benefits, by using the compiler itself to simplify expressions that have been attached, lamprey-like, to the AST by the optimization; the program being compiled benefits, from improved run-time in both serial and parallel environments.

We show the utility of symbiotic expressions by using them to extend the SAC compiler's With-Loop-Folding optimization, currently limited to Arrays of Known Shape (AKS), to Arrays of Known Dimensionality (AKD). We show that, in conjunction with array-based constant-folding, injection and propagation of array extrema, and compiler-based expression simplification, symbiotic expressions are an effective tool for implementing advanced array optimizations. Symbiotic expressions are also simpler and more likely to be correct than hard-coded analysis, and are flexible and relatively easy to use. Finally, symbiotic expressions are synergistic: they take immediate advantage of new or improved optimizations in the compiler. Symbiotic expressions are a useful addition to a compiler writer's toolkit, giving the compiler a restricted subset of the analysis power of an SMT solver.

Original languageEnglish
Title of host publicationImplementation and Application of Functional Languages
Subtitle of host publication21st International Symposium, IFL 2009, South Orange, NJ, USA, September 23-25, 2009, Revised Selected Papers
EditorsMarco T Morazán, Sven-Bodo Scholz
PublisherSpringer
Pages107-124
Number of pages18
ISBN (Electronic)978-3-642-16478-1
ISBN (Print)978-3-642-16477-4
DOIs
Publication statusPublished - 2011
Event21st International Symposium on Implementation and Application of Functional Languages - South Orange, NJ, United States
Duration: 23 Sep 200925 Sep 2009

Publication series

NameLecture Notes in Computer Science
Volume6041
ISSN (Print)0302-9743

Conference

Conference21st International Symposium on Implementation and Application of Functional Languages
CountryUnited States
CitySouth Orange, NJ
Period23/09/0925/09/09

Cite this

Bernecky, R., Herhut, S., & Scholz, S-B. (2011). Symbiotic expressions. In M. T. Morazán, & S-B. Scholz (Eds.), Implementation and Application of Functional Languages: 21st International Symposium, IFL 2009, South Orange, NJ, USA, September 23-25, 2009, Revised Selected Papers (pp. 107-124). (Lecture Notes in Computer Science; Vol. 6041). Springer. https://doi.org/10.1007/978-3-642-16478-1_7