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.
This is a preview of subscription content, log in via an institution to check access.
Access this chapter
Tax calculation will be finalised at checkout
Purchases are for personal use only
Preview
Unable to display preview. Download preview PDF.
Similar content being viewed by others
References
Cann, D.C.: Compilation Techniques for High Performance Applicative Computation. PhD thesis, Computer Science Department, Colorado State University (1989)
Bacon, D.F., Graham, S.L., Sharp, O.J.: Compiler transformations for high-performance computing. ACM Computing Surveys 26, 345–420 (1994)
Padua, D., Wolfe, M.: Advanced Compiler Optimizations for Supercomputers. ACM Comm. 29, 1184–1201 (1986)
Scholz, S.B.: Single Assignment C — efficient support for high-level array operations in a functional setting. Journal of Functional Programming 13, 1005–1059 (2003)
Scholz, S.B.: With-loop-folding in sac–Condensing Consecutive Array Operations. In: Clack, C., Hammond, K., Davie, T. (eds.) IFL 1997. LNCS, vol. 1467, pp. 72–92. Springer, Heidelberg (1998)
Rugina, R., Rinard, M.: Symbolic bounds analysis of pointers, array indices, and accessed memory regions. In: PLDI 2000 Conference Proceedings, pp. 182–195. ACM, New York (2000)
Dutertre, B., de Moura, L.: The yices smt solver. Technical report, SRI International (2006)
Pugh, W.: A practical algorithm for exact array dependence analysis. CACM 35, 102–115 (1992)
Kelly, W., Maslov, V., Pugh, W., Rosser, E., Shpeisman, T., Wonnacott, D.: The OMEGA library, version 1.1.0 interface guide. Technical report, University of Maryland (1996)
Trojahner, K., Grelck, C., Scholz, S.B.: On Optimising Shape-Generic Array Language Programs using Symbolic Structural Information. In: Horváth, Z., Zsók, V., Butterfield, A. (eds.) IFL 2006. LNCS, vol. 4449, pp. 1–18. Springer, Heidelberg (2007)
Cytron, R., Ferrante, J., Rosen, B.K., Wegman, M.N., Zadeck, F.K.: An efficient method for computing static single assignment form. In: Conference Record of the Sixteenth Annual ACM Symposium on Principles of Programming Languages, pp. 23–35 (1989)
Herhut, S., Scholz, S.B., Bernecky, R., Grelck, C., Trojahner, K.: From contracts towards dependent types: Proofs by partial evaluation. In: Chitil, O., Horváth, Z., Zsók, V. (eds.) IFL 2007. LNCS, vol. 5083, pp. 254–273. Springer, Heidelberg (2008)
Browne, S., Deane, C., Ho, G., Mucci, P.: Papi: A portable interface to hardware performance counters. In: HPCMP Users Group Conference, U.S Department of Defense (1999)
Mucci, P.: Papiex - execute arbitrary application and measure hardware performance counters with papi (2009)
Bernecky, R.: APEX: The APL Parallel Executor. Master’s thesis, University of Toronto (1997)
Menon, V.S., Glew, N., Murphy, B.R., McCreight, A., Shpeisman, T., Tabatabai, A.-R., Petersen, L.: A verifiable SSA program representation for aggressive compiler optimization. In: POPL 2006 Conference Proceedings, pp. 397–408. ACM, New York (2006)
Freeman, T., Pfenning, F.: Refinement types for ml. SIGPLAN Not. 26, 268–277 (1991)
Xi, H., Pfenning, F.: Dependent Types in Practical Programming. In: POPL 1999, pp. 214–227. ACM Press, New York (1999)
Rushby, J., Owre, S., Shankar, N.: Subtypes for specifications: Predicate subtyping in PVS. IEEE Transactions on Software Engineering 24, 709–720 (1998)
Author information
Authors and Affiliations
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2010 Springer-Verlag Berlin Heidelberg
About this paper
Cite this paper
Bernecky, R., Herhut, S., Scholz, SB. (2010). Symbiotic Expressions. In: Morazán, M.T., Scholz, SB. (eds) Implementation and Application of Functional Languages. IFL 2009. Lecture Notes in Computer Science, vol 6041. Springer, Berlin, Heidelberg. https://doi.org/10.1007/978-3-642-16478-1_7
Download citation
DOI: https://doi.org/10.1007/978-3-642-16478-1_7
Publisher Name: Springer, Berlin, Heidelberg
Print ISBN: 978-3-642-16477-4
Online ISBN: 978-3-642-16478-1
eBook Packages: Computer ScienceComputer Science (R0)