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.