Compilers using tree parsing for instruction selection

This page lists some of the compilers that use tree parsing.

This information was collected mostly by Florian Brandner. If you have any additional information, mail me.


Uses a iBURG-style tree matcher, dynamic costs are used to check for value ranges, query type information and special symbols (e.g., a virtual frame pointer). In addition to the matching rules the target description contains detailed information on the available instructions, i.e., register constraints. These constraints are considered in subsequent passes such as register allocation and scheduling. Paper: A Retargetable Code Generator for the Generic Intermediate Language in COINS.


Instruction selector based on ocamlburg - a port of IBURG to ocaml. Dynamic costs are permitted and used to check for value ranges and type information. Paper: C--: a portable assembly language


Uses lBURG, and extended version of iBURG that allows for dynamic costs. Similarly to the other systems these costs are used to check for value ranges, type information (on converts) and equivalence of nodes in the IR tree (required for x86 read-modify-write instructions that read and write the same memory location).

Jikes RVM

Uses jBURG a Java implementation of iBURG. Dynamic costs are used to check for value ranges and equivalence of nodes. In addition the IR represents all types of comparisons as on terminal symbol for the tree pattern matcher, thus dynamic costs are required to verify the actual kind of comparison (e.g., ==, <=, <, etc.). Paper: The Jalapeņo Dynamic Optimizing Compiler for Java


Performs instruction selection on general graphs covering the complete function (may contain cycles caused by PHI nodes). Subtrees of this graph are translated to machine instructions using a BURS, shared nodes need to return the result in a general purpose register. Dynamic checks are used to check for value ranges, type information, flags of operations (e.g., atomic loads/stores), and features of the target processor such as MMX and SSE extensions detected at runtime. In addition acquiring fast-locks is optimized by examining the surrounding graph (possibly outside of the current subtree). Paper: The Java HotSpotTM Server Compiler

Proprietary Compilers

Backend specifications based on BEG.
They use an in-house tree-parsing automaton generator (i.e., BURG-type technology).

Anton Ertl