Table Of Contents
Utilities¶
Yacc¶
// .. automodule:: yacc
Burg¶
Bottom up rewrite generator¶
This script takes as input a description of patterns and outputs a matcher class that can match trees given the patterns.
Patterns are specified as follows:
reg -> ADDI32(reg, reg) 2 (. add NT0 NT1 .)
reg -> MULI32(reg, reg) 3 (. .)
or a multiply add:
reg -> ADDI32(MULI32(reg, reg), reg) 4 (. muladd $1, $2, $3 .)
The general specification pattern is:
[result] -> [tree] [cost] [template code]
Trees¶
A tree is described using parenthesis notation. For example a node X with three child nodes is described as:
X(a, b, b)
Trees can be nested:
X(Y(a, a), a)
The ‘a’ in the example above indicates an open connection to a next tree pattern.
In the example above ‘reg’ is a non-terminal. ADDI32 is a terminal. non-terminals cannot have child nodes. A special case occurs in this case:
reg -> rc
where ‘rc’ is a non-terminal. This is an example of a chain rule. Chain rules can be used to allow several variants of non-terminals.
The generated matcher uses dynamic programming to find the best match of the tree. This strategy consists of two steps:
- label: During this phase the given tree is traversed in a bottom up way. each node is labelled with a possible matching rule and the corresponding cost.
- select: In this step, the tree is traversed again, selecting at each point the cheapest way to get to the goal.