Abstract
We present a method of specifying standard imperative program optimisations as a rewrite system. To achieve this we have extended the idea of matching sub-terms in expressions with simple patterns to matching blocks in a control flow graph. In order to express the complex restrictions on the applicability of these rewrites we add temporal logic side conditions. The combination of these features allows a flexible, high level, yet executable specification of many of the transformations found in optimising compilers.
Chapter PDF
Similar content being viewed by others
Keywords
These keywords were added by machine and not by the authors. This process is experimental and the keywords may be updated as the learning algorithm improves.
References
A. V. Aho, R. Sethi, and J. D. Ullman. Compilers: Principles, Techniques and Tools. Addison Wesley, 1985.
A. Aiken, M. Fuhndrich, J. Foster, and Z. Su. A toolkit for constructing type-and constraint-based program analyses. In Second International Workshop on Types in Compilation (TIC’ 98), March 1998.
A. W. Appel. Modern Compiler Implementation in ML. Cambridge University Press, 1998.
U. Assmann. How to uniformly specify program analysis and transformation with graph rewrite systems. In P. Fritzson, editor, Compiler Construction 1996, volume 1060 of Lecture Notes in Computer Science. Springer, 1996.
Uwe Aßmann. On Edge Addition Rewrite Systems and Their Relevance to Program Analysis. In J. Cuny, H. Ehrig, G. Engels, and G. Rozenberg, editors, 5th Int. Workshop on Graph Grammars and Their Application To Computer Science, Williamsburg, volume 1073 of Lecture Notes in Computer Science, pages 321–335, Heidelberg, November 1994. Springer.
Uwe Aßmann. OPTIMIX, A Tool for Rewriting and Optimizing Programs. In Graph Grammar Handbook, Vol. II. Chapman-Hall, 1999.
A. J. C Bik, P. J. Brinkhaus, P. M. W. Knijnenburg, and H. A. G. Wijshoff. Transformation mechanisms in mt1. Technical report, Leiden Institute of Advanced Computer Science, 1998.
J. M. Boyle. A transformational component for programming languages grammar. Technical Report ANL-7690, Argonne National Laboratory, IL, 1970.
J. M. Boyle. Abstract programming and program transformation. In Software Reusability Volume 1, pages 361–413. Addison-Wesley, 1989.
E. M. Clarke, E. A. Emerson, and A. P. Sistla. Automatic verification of finite-state concurrent systems using temporal logic specifications. ACM Transactions on Programming Languages and Systems, 8:244–263, 1996.
J. R. Cordy, I. H. Carmichael, and R. Halliday. The TXL programming language, version 8. Legasys Corporation, April 1995.
Steven Dawson, C. R. Ramakrishnan, and David S. Warren. Practical program analysis using general purpose logic programming systems — A case study. ACM SIGPLAN Notices, 31(5):117–126, May 1996.
D. R. Engler. Incorporating application semantics and control into compilation. In Proceedings of the First Conference on Domain-Specific Languages, pages 103–118. USENIX, 1987.
D. R. Engler. Interface compilation: Steps toward compiling program interfaces as languages. IEEE Transactions on Software Engineering, 25(3):387–400, 1999.
R. E. Faith, L. S. Nyland, and J. F. Prins. KHEPERA: A system for rapid implementation of domain-specific languages. In Proceedings USENIX Conference on Domain-Specific Languages, pages 243–255, 1997.
R. Giegerich, U. Moncke, and R. Wilhelm. Invariance of approximative semantics with respect to program transformations, 1981.
S. Z. Guyer and C. Lin. An annotation language for optimizing software libraries. In Second conference on Domain-Specific Languages, pages 39–52. USENIX, 199.
S. Z. Guyer and C. Lin. Broadway: A software architecture for scientific computing. Proceedings of the IFIPS Working Group 2.5 Working Conference on Software Architectures for Scientific Computing Applications. (to appear) October, 2000., 2000.
S. Z. Guyer and C. Lin. Optimizing high performance software libraries. In Proceedings of the 13th International Workshop on Languages and Compilers for Parallel Computing. August, 2000., 2000.
R. Heckmann. A functional language for the specification of complex tree transformations. In ESOP’ 88, Lecture Notes in Computer Science. Springer-Verlag, 1988.
R. Johnson, D. Pearson, and K. Pingali. Finding regions fast: Single entry single exit and control regions in linear time, 1993.
M. Klein, J. Knoop, D. Koschutzski, and B. Steffen. DFA & OPT-METAFrame: a toolkit for program analysis and optimization. In Proceedings of the 2nd International Workshop on Tools and Algorithms for the Construction and Analysis of Systems (TACAS’ 96), volume 1055 of Lecture Notes in Computer Science, pages 418–421. Springer, 1996.
J. Knoop, O. Ruthing, and B. Steffen. Towards a tool kit for the automatic generation of interprocedural data flow analyses. Journal of Programming Languages, 4:211–246, 1996.
P. Lipps, U. Monke, and R. Wilhelm. OPTRAN-a language/system for the specification of program transformations: system overview and experiences. In Proceedings 2nd Workshop on Compiler Compilers and High Speed Compilation, volume 371 of Lecture Notes in Computer Science, pages 52–65, 1988.
Florian Martin. PAG-an efficient program analyzer generator. International Journal on Software Tools for Technology Transfer, 2(1):46–67, 1998.
S. Muchnick. Advanced Compiler Design and Implementation. Morgan Kaufmann, 1997.
R. Paige. Viewing a program transformation system at work. In Proceedings Programming Language Implementation and Logic Programming (PLILP), and Algebraic and Logic Programming (ALP), volume 844 of Lecture Notes in Computer Science, pages 5–24. Springer, 1994.
B. Steffen. Data flow analysis as model checking. In Proceedings of Theoretical Aspects of Computer Science, pages 346–364, 1991.
B. Steffen. Generating data flow analysis algorithms from modal specifications. Science of Computer Programming, 21:115–139, 1993.
S. W. K. Tjiang and J. L. Henessy. Sharlit — a tool for building optimizers. In ACM SIGPLAN Conference on Programming Language Design and Implementation, 1992.
Todd L. Veldhuizen and Dennis Gannon. Active libraries: Rethinking the roles of compilers and libraries. In Proceedings of the SIAM Workshop on Object Oriented Methods for Inter-operable Scientific and Engineering Computing (OO’98). SIAM Press, 1998.
E. Visser, Z. Benaissa, and A. Tolmach. Building program optimizers with rewriting strategies. In International Conference on Functional Programming’ 98, ACM SigPlan, pages 13–26. ACM Press, 1998.
D. Whitfeld and M. L. Soffa. An approach for exploring code-improving transformations. ACM Transactions on Programming Languages and Systems, 19(6):1053–1084, 1997.
Author information
Authors and Affiliations
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2001 Springer-Verlag Berlin Heidelberg
About this paper
Cite this paper
Lacey, D., de Moor, O. (2001). Imperative Program Transformation by Rewriting. In: Wilhelm, R. (eds) Compiler Construction. CC 2001. Lecture Notes in Computer Science, vol 2027. Springer, Berlin, Heidelberg. https://doi.org/10.1007/3-540-45306-7_5
Download citation
DOI: https://doi.org/10.1007/3-540-45306-7_5
Published:
Publisher Name: Springer, Berlin, Heidelberg
Print ISBN: 978-3-540-41861-0
Online ISBN: 978-3-540-45306-2
eBook Packages: Springer Book Archive