OPTIMIX

OPTIMIX is a specification language for the specification of optimizers based on graph rewriting developed by UweAssman at the University of Karlsruhe [3]. A specification consists of a set of modules that each define a set of rewrite systems that consist of a list of graph rewrite rules. A rule matches a subgraph of the graph and adds or deletes edges and nodes. In order to avoid non-termination and non-confluence a transformation is defined in several separate rewrite systems that are then consecutively applied.

Only a restricted set of rewrite systems is supported that can be divided in two flavours. (1) Edge Addition Rewrite Systems (EARS) consist only of rules that add edges. These are used for program analysis; extra edges express relations between program nodes, e.g., is a subexpression of. (2) General Graph Rewrite Systems are used to express transformations. However, only those systems are supported that can be proven to be terminating according to a termination check. This boils down to systems that do not create new redexes after transformation steps.

In effect, an OPTIMIX rewrite system specification appears to be an abstraction of a certain class of while-programs that perform a loop over the program tree/graph finding all applications of the rules and then applying the transformations once.

A specification is translated to a C program in which each rewrite system corresponds to a C function that performs a transformation. These C functions have to be invoked from a C program that implements the rest of the compiler. Data types are declared with a data definition language (CoSy-fSDL or AST from the Cocktail package).

The specification method is related to Datalog.

OPTIMIX is an imperative specification language in the sense that there is one tree/graph that is manipulated. Other paradigms are usually functional, i.e., compute a new tree from an old one.

References

• Online articles on OPTIMIX [1]
• The OPTIMIX homepage [2]

See Also

Other TransformationSystems