[Firm] libfirm Erweiterung um IR bäume zu durchsuchen

Matthias Braun matthias.braun at kit.edu
Thu Nov 14 17:04:55 CET 2013

(for the non-german speakers: the question was how to match patterns in
a graph, whether we should define some sort of regular expressions for

This is a problem that we find alot in libfirm: ir/ir/iropt.c is
basically a collection of hundrets of graph patterns which can be
replaced by "better" patterns for optimisation. Also our backends
basically match graph fragments and replace them with target machine

The closest thing in the literature is probably the graph transformation
community. We used to have a lot of research in that direction in the
form of the grgen tool (I guess Sebastian can tell you more about that).
The last thing I heard though is that the graph transformation tools
still don't beat the manually programmed rules in libfirm, because the
manually programmed rules make use of the fact, that we have a huge
number of patterns we search concurrently and all patterns start a
distinguished root node, these assumptions are not made by general graph
transformation systems from what I understood.

The compiler literature also knows similar problems as the topic of
"code selection" although literature there mostly focuses on finding
such patterns efficiently, and most literature is only about expression
trees and not graphs.

We did a have a study thesis doing something similar for trying to
declaratively specify the rules in ir/ir/iropt.c and generating the code
for it. You can find the results here:
Unfortunately this is an external tool, and pretty much gearred toward
producing such replacement rules and it has to be used as a preprocessor
before compilation.

Having had all these complicated systems I personally went back to
manually coding pattern matching. It's not as bad as it sounds if you
create factor out helper functions for often occuring smaller patterns
which you use to identify the big patterns.

Anyhow it may be interesting to do another attempt at creating a graph
pattern description language and generating/executing such pattern
descriptions, and I'd happily give some more opinions/experiences if you
want to start such a project.


On Do, 2013-11-14 at 16:20 +0100, Martin Haaß KIT wrote:
> Hi Matthias,
> ich möchte kleine Teilbäume im irg finden, um diese zu
> extrahieren/umzubauen etc. und mein aktueller code ist ein schlimmes
> if-else-if-else. Ich dachte um so einen Teilbaum zu finden wäre ein
> regulärer Ausdruck nützlich.
> Habt ihr da was? Gibt es da was passendes in Literatur? Für xml gibt es
> ja z.b. xpath.
> Wenn nicht könnte man daraus eventuell ne Studenten Arbeit machen:
> rausfinden was es da so gibt, eigenes set definieren und implementieren.
> Grüße
>  Martin
> PS:/add{0:add{?:shl{0:(a=proj),1:tv[1])},?:(a=proj)},1:*}/ =~ ptr :P

More information about the Firm mailing list