A(n imperative) program - in a higher-level language and more importantly in assembly language or intermediate representations like LLVM - can be formalized as a directed "port graph", in which vertices are instructions and ports correspond to input/output operands/arguments. An optimization applied of a program's code therefore corresponds to a rewrite applied to its port digraph.

Now, graph rewriting is a small but somewhat-active area, in itself. What I'm wondering if these kinds of systems have been actually put to explicit use in the context of a compiler. That is, representing the optimization phase as a rewriting process, or a derivation using a port-graph grammar.

I'm not much of a "compilers guy" - I took a basic course on them in my undergraduate degree, and I know about LLVM and its IR - but it seems to me that graph rewriting systems is the "obvious" formalism to use; and at the same time - I don't see almost any FOSS projects involving such systems, nor do the papers about them discuss their use in compilers.

Note: I'm more interested in practical-use, popular-language compilers more than academia-only systems, but I'll take what I can get.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.