Computing Reviews
Today's Issue Hot Topics Search Browse Recommended My Account Log In
Review Help
Search
Graph rewrite systems for program optimization
Assmann U. ACM Transactions on Programming Languages and Systems22 (4):583-637,2000.Type:Article
Date Reviewed: Jul 1 2001

This paper reports a major result in the use of graph rewrite systems for program optimization. It was first submitted to the Transactions in 1996. The central idea is to represent all the information in an optimizer as a set of relational graphs. The resulting algorithm is used to generate optimizers for any programming language, which can be embedded in any compiler. Two theoretical applications are developed: an exhaustive graph rewrite system including rule-based termination criteria, and stratification, which automatically selects stratified normal forms. This last technique is important in program optimization, where system convergence may be disturbed. Generation of the graphs begins with splitting a system into smaller rewrite systems, where fast algorithms can be generated or a handwritten algorithm used. Maintaining consistency in the resulting parts assumes the use of a uniform data model or graph schema. Thus, specifying the uniform schema is undertaken first.

Assmann’s system is intended to express a broad range of program analysis and transformation problems; to run efficiently; to be flexible; and to provide an open system. Its advantages over other systems are in preparing for analysis and transformation; global data-flow analysis; and the systematic marking of redexes (permutations of the nodes of a graph) so that a transformation need only be performed once.

It has, however, several limitations: there is no methodology for the specification of general abstract interpretations; special strategies must be used in interprocedural analysis; special termination proofs are needed for several nonexhaustive optimizations; transformations creating overlaps do not yield unique normal forms; and transformations referring to an arbitrary set of nodes cannot be specified.

Assmann reports on an optimizer generator, OPTIMIX, implemented specifically for the graph methods described. It takes graph rewrite specifications in textual form and generates evaluation procedures in C, which can be embedded in compilers. It is estimated that the use of OPTIMIX can save about 50 percent of development time in generating an optimizer, and that with an industrial-strength implementation savings could be as great as 70 to 80 percent.

Since this paper reports on work carried out over several years, an extensive bibliography of 53 entries is included.

Reviewer:  D. Appleby Review #: CR125234
Bookmark and Share
 
Translator Writing Systems And Compiler Generators (D.3.4 ... )
 
Would you recommend this review?
yes
no
Other reviews under "Translator Writing Systems And Compiler Generators": Date
The art of compiler design
Pittman T., Peters J., Prentice-Hall, Inc., Upper Saddle River, NJ, 1992. Type: Book (9780130481900)
Apr 1 1994
Compiler generation from denotational semantics
Paulson L., Cambridge University Press, New York, NY, 1984. Type: Book (9780521268431)
Jun 1 1985
Automatic compiler production: the front end
Reiss S. IEEE Transactions on Software Engineering SE-13(6): 609-627, 1987. Type: Article
Feb 1 1988
more...

E-Mail This Printer-Friendly
Send Your Comments
Contact Us
Reproduction in whole or in part without permission is prohibited.   Copyright 1999-2024 ThinkLoud®
Terms of Use
| Privacy Policy