Lesson 21.2 — Optimal tree tiling: dynamic programming, twig, iburg and lburg¶

Techniques: Aho–Johnson dynamic programming; tree-grammar code-generator generators (twig, iburg, lburg) · Lab: labs/ch21-isel E3 (DP) · Prerequisites: Lesson 21.1 (tile grammars, Definitions 21.1.2–21.1.4) · Time: 4–6 hours

Maximal munch lost one unit of cost on a[i] = p[3] (Lesson 21.1, Proposition 21.1.14). It chose the root tile by size alone, before it knew what the subtrees would cost. The fix is to decide bottom-up. First find, for every node and every nonterminal, the cheapest way to derive that subtree. Then choose the root tile, when all the subtrees' costs are known. On a tree this is exact, because the best derivation of a subtree does not depend on what happens above it. The result is optimal tree tiling in linear time. It is the idea behind Aho and Johnson's 1976 paper and behind every "BURG-family" code-generator generator: twig, iburg, lburg, HotSpot's ADLC and, with precomputed states, BURG itself (Lesson 21.3).

1. Problem and motivation¶

Given a statement tree \(t\) and a tile grammar \(G\) (Definition 21.1.2), find a tiling of \(t\) of minimum cost \(\mathrm{OPT}(t)\) (Definition 21.1.4) and emit its code. A brute-force search is hopeless: the number of tilings grows exponentially with the tree (Proposition 21.2.9). LLVM does not tile trees optimally, since its selectors work on DAGs (Lesson 21.4). The lab's third selector, however, is exactly this algorithm, and it is the one the tests trust to be optimum.

Aho–Johnson dynamic programming¶

Sethi and Ullman had shown how to evaluate an arithmetic expression tree with the fewest registers and loads, for a simple machine [SU70]. Aho and Johnson generalized this to a whole class of register machines with arbitrary instructions, including memory operands and complex addressing modes [AJ76]. Their key result is that an optimal program can always be taken in a normal form where each subtree is evaluated contiguously. That makes the optimal cost a function of (subtree, number of free registers) that can be tabulated bottom-up, in time linear in the tree. Remove the register bound and you get the plain tiling DP, which all later generators use. [Dragon2, §8.11] presents the register-bounded version.

Tree-grammar generators (twig, iburg, lburg)¶

Writing the DP by hand for every target is tedious and error-prone, so the next step was to generate it from a grammar like Table 21.1.1. twig [AGT89] reads tree patterns with costs and actions. It finds matches with a top-down tree automaton built with Aho–Corasick techniques [HO82] and runs the DP while it matches. iburg [FHP92b] reads a BURG-style grammar and emits a C labeler that hard-codes the DP: one if per rule, one closure function per nonterminal, with costs computed while compiling. It was written to be "simple and efficient" next to the table-driven BURG, and it allows dynamic costs, C expressions that can depend on the node. lburg, lcc's variant of iburg, drives the code generators of the lcc C compiler [FH95, Ch. 14].

2. Definitions and algorithms¶

Definition 21.2.1 (Labels)

For a node \(v\) of \(t\) and a nonterminal \(A\), the label \(C(v, A)\) is the minimum cost of an \(A\)-derivation of \(t_v\), or \(\infty\) if there is none. A best rule \(\mathrm{rule}(v, A)\) is the rule at the root of some \(A\)-derivation of cost \(C(v, A)\). The cost of a rule at a node is \(c(r, v) = c(r) + \sum_{(u, B)} C(u, B)\), where the sum ranges over the operand nodes \(u \in \mathrm{ops}(\pi_r, v)\) with their nonterminals \(B\) (Definition 21.1.3). For a chain rule \(A \to B\) at \(v\) it is \(c(r) + C(v, B)\).

Labels of two nodes of the running example

At n4 SHL(TEMP i, CONST 3): \(c(\text{r14}, n4) = 1 + C(n2, \mathsf{reg}) + C(n3, \mathsf{reg}) = 1 + 0 + 1 = 2\) and \(c(\text{r15}, n4) = 1 + C(n2, \mathsf{reg}) = 1\), so \(C(n4, \mathsf{reg}) = 1\) with rule r15. At n5 ADD(TEMP a, n4): r8 gives \(1 + 0 + 1 = 2\), r16 gives \(1 + 0 + 0 = 1\) (its pattern swallows n4 and n3, so only the two TEMP operands count), and \(C(n5, \mathsf{reg}) = 1\).

Definition 21.2.2 (Chain closure)

Let \(C_0(v, \cdot)\) be the costs from non-chain rules alone. The chain closure is the least function \(C(v, \cdot) \le C_0(v, \cdot)\) with \(C(v, A) \le c(A \to B) + C(v, B)\) for every chain rule \(A \to B\). Because all costs are non-negative, it is the shortest-path distance to \(A\) in the graph whose edges \(B \to A\) weigh \(c(A \to B)\), starting from the values \(C_0\).

Aho–Johnson dynamic programming¶

Algorithm 21.2.3 (Optimal labeling by dynamic programming)

Input: a statement tree \(t\); a tile grammar \(G\) with non-negative costs.
Output: labels \(C(v, A)\) and best rules \(\mathrm{rule}(v, A)\) for every node \(v\) and nonterminal \(A\).
Precondition: costs are non-negative integers (dynamic costs, Definition 21.2.10, are evaluated to such integers at the node).
Postcondition: \(C(v, A)\) is the minimum cost of an \(A\)-derivation of \(t_v\) (Theorem 21.2.7), and \(\mathrm{rule}(v, A)\) attains it. Ties go to the lower rule number.
Invariant: when Label(v) starts its own loop, every proper descendant \(u\) of \(v\) already has its final labels \(C(u, \cdot)\) (postorder).

function Label(v):
    for each child u of v: Label(u)                       # postorder
    for each nonterminal A: C[v][A] ← ∞; rule[v][A] ← none
    for each non-chain rule r = A → π, in rule-number order:
        if Matches(π, v):                                 # Algorithm 21.1.8
            cost ← c(r, v)                                # c(r) + Σ C[u][B] over operand nodes
            if cost < C[v][A]: C[v][A] ← cost; rule[v][A] ← r
    ChainClosure(v)

function ChainClosure(v):                                 # Bellman–Ford over nonterminals
    repeat |N| times:
        changed ← false
        for each chain rule r = A → B:
            if c(r) + C[v][B] < C[v][A]:
                C[v][A] ← c(r) + C[v][B]; rule[v][A] ← r; changed ← true
        if not changed: return

Algorithm 21.2.4 (Reduce: emit the optimum tiling)

Input: a labeled tree (Algorithm 21.2.3); the goal \(S\) at the root.
Output: the code of a tiling of cost \(C(\mathrm{root}, S)\).
Precondition: \(C(\mathrm{root}, S) < \infty\).
Postcondition: the emitted derivation uses \(\mathrm{rule}(v, A)\) at every pair \((v, A)\) it visits, and its cost is \(C(\mathrm{root}, S)\).
Invariant: Reduce(v, A) is only called with \(C(v, A) < \infty\). On return, the code for an \(A\)-derivation of \(t_v\) of cost \(C(v, A)\) has been emitted.

function Reduce(v, A):
    r ← rule[v][A]
    if r is a chain rule A → B:
        x ← Reduce(v, B)
        return Emit(r, [x])                       # Emit as in Algorithm 21.1.6
    operands ← []
    for each leaf ℓ of pattern(r), left to right:
        u ← the node ℓ maps to at v
        if ℓ is a nonterminal B: operands.append(Reduce(u, B))    # children first
        else:                    operands.append(Attribute(u))
    return Emit(r, operands)

The register-bounded version of Aho and Johnson labels each node with a vector instead. \(C_j(v)\) is the cost of computing \(t_v\) into a register using at most \(j\) registers, and \(C_0(v)\) the cost of computing it into memory. Take a machine with \(k\) registers and four instructions, each of cost 1: LD R, m, OP R, R, R', OP R, R, m (right operand in memory) and ST m, R. All leaves are variables in memory.

Algorithm 21.2.5 (Aho–Johnson with \(k\) registers, after [AJ76] and [Dragon2, §8.11])

Input: an expression tree whose leaves are memory variables; the machine above with \(k \ge 1\) registers.
Output: \(C_j(v)\) for \(0 \le j \le k\) at every node, and the choice that attains it.
Precondition: there are no common subexpressions (it is a tree). Every binary operator has the four instructions above.
Postcondition: \(C_k(\mathrm{root})\) is the cost of an optimal program that leaves the value in a register (Theorem 21.2.8).
Invariant: children are labeled before parents, and \(C_1(v) \ge C_2(v) \ge \dots \ge C_k(v)\) (more registers never hurt).

function AJ(v):                                           # returns the vector C[v][0..k]
    if v is a leaf: C[v][0] ← 0; C[v][j] ← 1 for j = 1..k; return   # already in memory / LD
    AJ(l); AJ(r)                                          # v = OP(l, r)
    for j = 1..k:
        C[v][j] ← C[r][0] + C[l][j] + 1                   # (d) r into memory first, OP R,R,m
        if r is a leaf: C[v][j] ← min(C[v][j], C[l][j] + 1)          # (a) OP R, R, m directly
        if j ≥ 2:
            C[v][j] ← min(C[v][j], C[l][j] + C[r][j-1] + 1,   # (b) l first, then r in j−1 regs
                                   C[r][j] + C[l][j-1] + 1)   # (c) r first, then l
    C[v][0] ← C[v][k] + 1                                 # compute with all k registers, ST

Lemma 21.2.6 (Optimal substructure)

Let \(D\) be an \(A\)-derivation of \(t_v\) whose root rule \(r\) has operand nodes \(u_1, \dots, u_m\) with nonterminals \(B_1, \dots, B_m\) (or, for a chain rule \(A \to B\), a \(B\)-derivation of \(t_v\) itself). Replacing any sub-derivation by a cheaper \(B_i\)-derivation of \(t_{u_i}\) gives another \(A\)-derivation of \(t_v\) with lower cost. Hence in a minimum-cost \(A\)-derivation every sub-derivation is of minimum cost.

Proof

By Definition 21.1.4, a derivation is a rule application plus independent derivations of the operand subtrees \(t_{u_i}\). These subtrees are pairwise disjoint (the operand nodes of a tree pattern are roots of disjoint subtrees), and nothing in the definition relates the derivation of one subtree to another or to the context above \(v\). So any \(B_i\)-derivation of \(t_{u_i}\) can replace the old one, and the result is again an \(A\)-derivation. Its cost is the sum of its rule costs, which drops by exactly the difference. If some sub-derivation of a minimum derivation were not minimum, this exchange would contradict minimality.

Theorem 21.2.7 (Dynamic programming finds an optimum tiling)

With non-negative costs, Algorithm 21.2.3 computes \(C(v, A)\) equal to the minimum cost of an \(A\)-derivation of \(t_v\) for every \(v\) and \(A\), and Algorithm 21.2.4 emits a tiling of cost \(C(\mathrm{root}, S) = \mathrm{OPT}(t)\).

Proof

By induction on the height of \(t_v\), with an inner argument for chain rules.

Let \(C^\ast(v, A)\) be the true minimum. Any \(A\)-derivation of \(t_v\) ends in a finite sequence of chain rules \(A = A_0 \to A_1 \to \dots \to A_q\) applied at \(v\), followed by a non-chain rule \(r = A_q \to \pi\) matching at \(v\) with derivations of the operand subtrees. We may assume no nonterminal repeats in the chain: a repeat \(A_i = A_j\) (\(i < j\)) can be cut out, and since costs are non-negative this does not increase the cost. So \(q < \lvert N \rvert\).

Non-chain part. By the induction hypothesis every operand \(u\) of every rule has final labels \(C(u, B) = C^\ast(u, B)\). By Lemma 21.2.6, the cheapest derivation starting with \(r\) costs exactly \(c(r, v)\). The loop over non-chain rules therefore sets \(C(v, A) = C_0(v, A) = \min_r c(r, v)\), the minimum over derivations that start without a chain rule.

Chain part. ChainClosure is Bellman–Ford on the graph of Definition 21.2.2. After round \(i\), \(C(v, A)\) is at most the cost of every derivation whose chain prefix has length at most \(i\) (induction on \(i\): a prefix of length \(i\) is a chain rule \(A \to A_1\) followed by a prefix of length \(i - 1\) for \(A_1\), which round \(i - 1\) already accounts for). Every value is also the cost of an actual derivation, so \(C(v, A) \ge C^\ast(v, A)\). Since optimal chain prefixes have length at most \(\lvert N \rvert - 1\), the \(\lvert N \rvert\) rounds reach \(C^\ast\) (an early exit happens only at a fixed point, where nothing can decrease further).

Reduce. By induction on the order of calls, Reduce(v, A) follows \(\mathrm{rule}(v, A)\). The chosen rule's cost \(c(r, v)\) equals \(C(v, A)\) and is built from the operands' labels, so recursion on them emits derivations of exactly those costs. The total is \(C(\mathrm{root}, S) = C^\ast(\mathrm{root}, S) = \mathrm{OPT}(t)\).

Theorem 21.2.8 (Aho–Johnson: contiguous evaluation, optimality)

For the machine of Algorithm 21.2.5 and an expression tree \(t\), some optimal program evaluates \(t\) contiguously: when it starts computing a subtree \(t_u\) into a register, it finishes \(t_u\) before starting any instruction for a subtree disjoint from \(t_u\) (except values it has already stored to memory). Consequently \(C_k(\mathrm{root})\) from Algorithm 21.2.5 is the cost of an optimal program that leaves the value in a register.

Proof sketch (full proof: [AJ76, §3–4] (the Strong Normal Form theorem))

Take an optimal program and look at its last instruction, which computes the root \(\mathrm{OP}(l, r)\). Its register operands hold \(l\) (and, in the register–register form, \(r\)). Aho and Johnson show by an exchange argument that the instructions computing \(l\) and those computing \(r\) can be reordered into two blocks, one after the other, without increasing the number of instructions. Values that must be kept across both blocks are stored to memory at the moment their subtree completes. The block computed first may use all \(j\) registers. The second may use only \(j - 1\), because one register holds the first result, unless the first result was stored, in which case the second gets all \(j\) and the operation reads memory. These are exactly cases (b), (c) and (d) of the recurrence, and case (a) is the leaf operand read directly from memory. Applying the argument recursively gives the normal form, and the recurrence minimizes over all normal-form programs. Monotonicity in \(j\) follows because any program using \(j - 1\) registers is also valid with \(j\).

Proposition 21.2.9 (Tilings can be counted by the same recursion)

Let \(\#(v, A)\) be the number of \(A\)-derivations of \(t_v\) in a chain-free grammar. Then \(\#(v, A) = \sum_{r = A \to \pi \text{ matching at } v} \prod_{(u, B)} \#(u, B)\), with the product over the operand nodes of \(r\) at \(v\). There are grammars and families of trees where \(\#(\mathrm{root}, S)\) grows exponentially in \(n\) while Algorithm 21.2.3 runs in \(O(n)\).

Proof

A derivation is a choice of root rule followed by independent choices of sub-derivations (Definition 21.1.4), so the counts multiply across operands and add across rules. For the family: in Tessera, let \(t^{(k)}\) be MOVE(TEMP x, e_k) with \(e_0 =\) TEMP y and \(e_{k} =\) ADD(e_{k-1}, CONST 1). At each ADD both r8 (operands \(e_{k-1}\) and the constant, whose only reg rule is r7) and r9 (operand \(e_{k-1}\)) match, so \(\#(e_k, \mathsf{reg}) = \#(e_{k-1}) \cdot 1 + \#(e_{k-1}) = 2\,\#(e_{k-1})\), which gives \(2^k\) tilings for \(n = 2k + 3\) nodes. Algorithm 21.2.3 does \(O(1)\) work per node for a fixed grammar (§5).

Tree-grammar generators (twig, iburg, lburg)¶

Definition 21.2.10 (Dynamic cost)

A dynamic cost replaces the constant \(c(r)\) by a function \(c_r(v) \in \mathbb{N} \cup \{\infty\}\) of the node where \(r\) is applied. \(c_r(v)\) may inspect the subtree \(t_v\) (its constants, whether two subtrees are equal) but not its context. The value \(\infty\) (lburg's LBURG_MAX) means "does not apply here", so a dynamic cost is also a predicate. Example: lcc's con1: CNSTI4 "1" range(a, 1, 1) costs 0 if the constant is 1 and LBURG_MAX otherwise.

Algorithm 21.2.11 (The labeler that iburg and lburg generate)

Input: a grammar in the lburg/iburg format; generation happens once, when the compiler is built.
Output: C code: a state record per node (cost[] and rule fields per nonterminal), a function _label(p) and closure functions _closure_A(p, c).
Precondition: chain rules have constant costs (lburg's rule, so closures can be generated as straight-line code). Dynamic costs are C expressions.
Postcondition: at compile time, _label computes exactly the labels of Algorithm 21.2.3 (with \(c_r(v)\) in place of \(c(r)\)).
Invariant: the generated code for operator \(o\) contains one if per rule whose pattern root is \(o\), in rule order. Each tests the pattern's inner operators and adds the operands' costs.

function Generate(G):
    emit "struct state { int cost[|N|]; struct { rule per nonterminal } rule; }"
    for each nonterminal A: emit ClosureFunction(A)
    emit "void _label(NODEPTR p) {"
    emit "  label the children; allocate state; set every cost to MAX"
    emit "  switch (OP_LABEL(p)) {"
    for each operator o:
        emit "  case o:"
        for each non-chain rule r = A → π with root(π) = o, in order:
            emit "    if (" InnerOperatorTests(π) ") {"
            emit "      c = " SumOfOperandCosts(π) " + " CostExpression(r) ";"
            emit "      if (c < p->cost[A]) { p->cost[A] = c; p->rule.A = r;"
            emit "                            _closure_A(p, c); } }"
    emit "  } }"

function ClosureFunction(B):              # propagate a new cost of B along chain rules A → B
    emit "void _closure_B(state *p, int c) {"
    for each chain rule r = A → B:
        emit "  if (c + c(r) < p->cost[A]) { p->cost[A] = c + c(r); p->rule.A = r;"
        emit "                               _closure_A(p, c + c(r)); }"
    emit "}"

The closure functions call each other recursively instead of iterating to a fixed point. This terminates because an update requires a strict decrease, and costs are non-negative integers.

Proposition 21.2.12 (Dynamic costs keep the DP exact)

If every dynamic cost \(c_r(v)\) depends only on \(t_v\), then Theorem 21.2.7 holds with \(c_r(v)\) in place of \(c(r)\). If a cost depends on anything outside \(t_v\) (the parent, a register allocation decision), optimality is lost in general.

Proof

Lemma 21.2.6 used only two facts: the derivations of disjoint subtrees are independent, and the cost of the rule at \(v\) does not depend on which sub-derivations are chosen. A cost that is a function of \(t_v\) is fixed once \(t_v\) is, so both facts still hold, and the induction of Theorem 21.2.7 goes through verbatim. For the negative part, suppose the cost of the rule at \(u\) depends on the rule chosen at its parent. Then \(C(u, B)\) is not well defined before the parent is decided, and the bottom-up order breaks. For example, "this load is free if the parent folds it" must be modelled as a larger pattern at the parent, not as a context-dependent cost at the child.

3. Worked example¶

Aho–Johnson dynamic programming¶

The tiling DP on the running example. The tree is a[i] = p[3] with nodes n1–n10 as in Lesson 21.1 §3. One row per node in postorder, listing every rule that matches with its cost \(c(r, v)\). The table is generated by the drill oracle (tiling.dp(..., trace)):

node	label	matching rules: cost \(c(r, v)\)	\(C(v, \cdot)\)	rule
n1	`TEMP a`	r6: 0	reg 0	r6
n2	`TEMP i`	r6: 0	reg 0	r6
n3	`CONST 3`	r7: 1	reg 1	r7
n4	`SHL`	r14: 1+0+1 = 2; r15: 1+0 = 1	reg 1	r15
n5	`ADD`	r8: 1+0+1 = 2; r16: 1+0+0 = 1	reg 1	r16
n6	`TEMP p`	r6: 0	reg 0	r6
n7	`CONST 24`	r7: 1	reg 1	r7
n8	`ADD`	r8: 1+0+1 = 2; r9: 1+0 = 1	reg 1	r9
n9	`MEM`	r17: 2+1 = 3; r18: 2+0 = 2; r20: 2+0+1 = 3	reg 2	r18
n10	`STORE`	r2: 2+1+2 = 5; r5: 4+1+1 = 6	stmt 5	r2

The decisive row is n10. The DP knows both alternatives' full costs: r5 movm would need n5 and n8 in registers (1 + 1). r2 needs n5 and n9 (1 + 2). \(5 < 6\), so it picks r2.
Tessera has no chain rules, so every ChainClosure exits in its first round with no change.

Reduce(n10, stmt) then follows the rule column (children first):

shadd r1, a, i, 3        # Reduce(n5, reg): r16
ld    r2, 24(p)          # Reduce(n9, reg): r18
st    r2, 0(r1)          # r2 at n10
cost 5

Counting the tilings (Proposition 21.2.9), bottom-up. Each entry is the sum over matching rules of the product of the operand counts:

node	count	how
n1, n2, n6	1	r6
n3, n7	1	r7
n4	2	r14: 1·1, r15: 1
n5	3	r8: #n1·#n4 = 2, r16: #n1·#n2 = 1
n8	2	r8: 1·1, r9: 1
n9	4	r17: #n8 = 2, r18: #n6 = 1, r20: #n6·#n7 = 1
n10	18	r2: #n5·#n9 = 12, r5: #n5·#n8 = 6

The running example has 18 tilings, and the DP explored all of them implicitly by keeping one number per (node, nonterminal). tools/course/tests/test_ch21.py checks the count and the minimum against explicit enumeration.

Aho–Johnson with registers. Evaluate \((a - b) + (c - d)\) on the 4-instruction machine of Algorithm 21.2.5. Leaves: \(C_0 = 0\), \(C_j = 1\) (one LD).

node	\(C_0\)	\(C_1\)	\(C_2\)	how (\(k = 2\))
`a`, `b`, `c`, `d`	0	1	1	`LD`
`a - b`	3	2	2	(a): `LD R, a; SUB R, R, b`; \(C_0 = C_2 + 1\) (`ST`)
`c - d`	3	2	2	same
`(a-b)+(c-d)`	6	6	5	\(C_1\): only (d) applies, \(3 + 2 + 1 = 6\). \(C_2\): (b) \(C_2(l) + C_1(r) + 1 = 2 + 2 + 1 = 5\)

With one register the right operand must go through memory (compute c - d, store it, compute a - b, ADD R, R, t): 6 instructions. With two registers the two halves live side by side: 5 instructions. The DP chose contiguous evaluation in both cases (Theorem 21.2.8).

Try it

./course drill dp-tiling --seed 2 --difficulty hard --solution labels a random Tessera tree in the table format above and counts its tilings. Your lab selector must agree with it: build/<preset>/bin/ch21-isel --algo=dp labs/ch21-isel/inputs/running.tree prints cost 5.

Tree-grammar generators (twig, iburg, lburg)¶

iburg's labeler does the same computation with chain rules. Its sample grammar sample4.brg (Fraser, Hanson and Proebsting's own test [FHP92b]) has nonterminals stmt, reg, disp, rc, con and chain rules such as reg: disp (cost 1) and rc: reg (cost 0). Labeling i = c + 4 visits each node once, and every "matched" line in the real trace of §7 is one successful if of Algorithm 21.2.11 or one step of a closure function.

4. Invariants and correctness¶

Aho–Johnson dynamic programming¶

Lemma 21.2.6, Theorem 21.2.7 and Theorem 21.2.8 above cover correctness. The two preconditions that matter:

Non-negative costs. With a negative chain-rule cycle (say \(A \to B\) at cost \(-1\) and \(B \to A\) at cost 0), labels would decrease forever. Bellman–Ford's \(\lvert N \rvert\)-round bound would stop with a value that is not the infimum, and the infimum is \(-\infty\) anyway. Every real grammar has non-negative costs.
Tree shape. On a DAG, a shared node would be counted once per parent, since each parent adds its label. The DP then either duplicates the shared computation or charges for it twice. That is why DAG selection is a different problem (Lesson 21.4, Theorem 21.4.4).

Tree-grammar generators (twig, iburg, lburg)¶

Proposition 21.2.12 gives the condition for dynamic costs: they must depend on the subtree only. lcc's memop(a) in §7 respects it, since it inspects the ASGN node and its subtree to check that the store address equals the load address. It is exactly the kind of test a tree pattern cannot express (two equal subtrees), made into a cost.

5. Complexity¶

Variables: \(n\) nodes, \(R\) rules (\(R_o\) with root operator \(o\), \(R_c\) chain rules), \(p\) the largest pattern size, \(\lvert N \rvert\) nonterminals.

Technique	Time (worst)	Time (typical)	Space	Justification
Aho–Johnson DP (tiling form)	\(O(n (R p + \lvert N \rvert R_c))\)	\(O(n \max_o R_o \, p)\): linear in \(n\)	\(O(n \lvert N \rvert)\) labels	one visit per node; each rule matched in \(O(p)\) and costed in \(O(p)\); closure \(\le \lvert N \rvert\) rounds of \(R_c\)
Aho–Johnson with \(k\) registers	\(O(n k)\)	\(O(nk)\)	\(O(nk)\)	each binary node computes \(k + 1\) entries from \(O(1)\) cases
iburg/lburg generated labeler	same as DP, plus dynamic cost evaluation	a few hundred ns per node (a `switch`, a handful of `if`s)	one state record per node	Algorithm 21.2.11 is Algorithm 21.2.3 compiled
twig	\(O(n \cdot \text{matches})\) with Aho–Corasick matching	linear	automaton size	[AGT89]

The DP's cost does not depend on the number of tilings. On the family of Proposition 21.2.9, the DP does \(2k + 3\) node visits for \(2^k\) tilings.

A pathological family for the DP's constant. A grammar with many nonterminals and dense chain rules makes each closure cost \(\Theta(\lvert N \rvert \cdot R_c)\). With \(\lvert N \rvert\) nonterminals all connected by chain rules in a cycle (\(A_1 \to A_2 \to \dots \to A_{\lvert N \rvert} \to A_1\), all cost 1), a new cheap value for \(A_1\) has to travel \(\lvert N \rvert - 1\) steps. Algorithm 21.2.3 needs that many rounds, and the recursive closures of Algorithm 21.2.11 make that many calls, at every node. This is one reason BURG (Lesson 21.3) precomputes closures once, at generator time.

Real-world scale. The lab's DP selector takes 59 µs per program against munch's 36 µs, over 71197 nodes (§5 of Lesson 21.1). That is about 1.6× munch's time for 0.6 % better code on that corpus. iburg's labelers were fast enough for lcc's production use, while doing more work per node than BURG's table lookups [FHP92b].

Aho–Johnson dynamic programming¶

Sethi–Ullman numbering [SU70]: for a machine whose instructions are all "register op register" or "register op memory", the optimal number of registers for a tree is a label computed bottom-up (\(\max(l, r)\) if \(l \ne r\), else \(l + 1\)). This is the \(k\)-free special case of Aho–Johnson that minimizes loads and stores rather than instructions.
Costs as vectors. Aho–Johnson labels with a cost per register budget. Grammars instead use one nonterminal per location class (reg, mem, imm). Register pressure then drops out of selection and goes to the register allocator (Ch 22), which is what every modern selector does.
Precompute the DP. BURS/BURG move the whole labeling to generator time (Lesson 21.3): faster labeling, a bigger generator, and no dynamic costs.

Tree-grammar generators (twig, iburg, lburg)¶

Top-down matching (twig). Match with a tree automaton, then run the DP [AGT89]. Cheap matching at the price of automaton construction. Hoffmann and O'Donnell give the underlying top-down and bottom-up tree-matching algorithms and their table sizes [HO82].
Dynamic costs and predicates (iburg, lburg). More expressive (immediate ranges, memop) at the price of labeling-time evaluation. BURG-style tables cannot contain them, because they depend on the node.
Cost bounds in the generator (HotSpot ADLC). ADLC tracks lower and upper bounds of each production's cost while generating the DFA routines. It drops tests that can never win and skips cost comparisons that always win (cost_check in src/hotspot/share/adlc/dfa.cpp, JDK 21) [HS-ADLC]. This gives smaller, faster labelers with the same results.

7. In real compilers¶

Aho–Johnson dynamic programming¶

HotSpot's C2 compiler selects instructions with this DP. Matcher::Label_Root walks each expression tree of the sea of nodes bottom-up and calls State::DFA at every node. DFA is generated from the .ad machine description and fills per-operand cost and rule arrays exactly as Algorithm 21.2.3 does. Matcher::ReduceInst then emits from the root's cheapest rule, as Algorithm 21.2.4 does (src/hotspot/share/opto/matcher.cpp, JDK 21) [HS-Matcher]. Despite its name, DFA computes costs while compiling; it is not a precomputed automaton.

HotSpot C2: instruction costs in the x86-64 machine description

Reproduce (OpenJDK tag jdk-21-ga; needs network access to GitHub):

curl -sL https://raw.githubusercontent.com/openjdk/jdk/jdk-21-ga/src/hotspot/cpu/x86/x86_64.ad \
  | sed -n '/^instruct addL_rReg_mem(/,/^%}/p;/^instruct addL_mem_rReg(/,/^%}/p'

Output (complete):

instruct addL_rReg_mem(rRegL dst, memory src, rFlagsReg cr)
%{
  match(Set dst (AddL dst (LoadL src)));
  effect(KILL cr);

  ins_cost(150); // XXX
  format %{ "addq    $dst, $src\t# long" %}
  ins_encode %{
    __ addq($dst$$Register, $src$$Address);
  %}
  ins_pipe(ialu_reg_mem);
%}
instruct addL_mem_rReg(memory dst, rRegL src, rFlagsReg cr)
%{
  match(Set dst (StoreL dst (AddL (LoadL dst) src)));
  effect(KILL cr);

  ins_cost(150); // XXX
  format %{ "addq    $dst, $src\t# long" %}
  ins_encode %{
    __ addq($dst$$Address, $src$$Register);
  %}
  ins_pipe(ialu_mem_reg);
%}

What to notice: each instruct is a grammar rule. The match clause is the pattern (AddL dst (LoadL src) is Tessera's r18 idea: a load folded into an operation), ins_cost is its cost, and operands such as memory and rRegL are nonterminals with their own rules elsewhere in the file. The second rule's pattern mentions dst twice (load and store the same address): a DAG pattern, which C2's matcher accepts because it checks that both inputs are the same node (Lesson 21.4). The // XXX next to the cost is in the original.

Tree-grammar generators (twig, iburg, lburg)¶

iburg's generator is iburg.c in github.com/drh/iburg (commit ef9d6452); lcc's lburg is lburg/lburg.c in github.com/drh/lcc (commit 2b5cf358), with the machine descriptions src/x86linux.md, src/mips.md and src/sparc.md [IBURG-Src, LCC-Src]. twig itself was an AT&T tool, and its source is not publicly available.

iburg's DP labeler, traced

Reproduce (iburg at commit ef9d6452000e3b371b446c198d2028dfa38b11c4, bison 3.8.2 as yacc, GCC 13.3.0; the sed hides node addresses):

git clone https://github.com/drh/iburg && cd iburg
git checkout ef9d6452000e3b371b446c198d2028dfa38b11c4
yacc gram.y 2>/dev/null && gcc -w -o iburg y.tab.c iburg.c
./iburg -I -T sample4.brg sample4.c && gcc -w -std=gnu89 -o sample4 sample4.c
Trace=-1 ./sample4 2>&1 | sed -E 's/0x(0x)?[0-9a-f]+/0x…/'

Output (complete):

0x… matched disp: ADDRLP = 11 with cost 0 vs. 32767
0x… matched reg: disp = 9 with cost 1 vs. 32767
0x… matched rc: reg = 13 with cost 1 vs. 32767
0x… matched stmt: reg = 5 with cost 1 vs. 32767
0x… matched disp: ADDRLP = 11 with cost 0 vs. 32767
0x… matched reg: disp = 9 with cost 1 vs. 32767
0x… matched rc: reg = 13 with cost 1 vs. 32767
0x… matched stmt: reg = 5 with cost 1 vs. 32767
0x… matched reg: CVCI(INDIRC(disp)) = 7 with cost 1 vs. 32767
0x… matched rc: reg = 13 with cost 1 vs. 32767
0x… matched stmt: reg = 5 with cost 1 vs. 32767
0x… matched con: CNSTI = 14 with cost 0 vs. 32767
0x… matched rc: con = 12 with cost 0 vs. 32767
0x… matched disp: ADDI(reg,con) = 10 with cost 1 vs. 32767
0x… matched reg: disp = 9 with cost 2 vs. 32767
0x… matched rc: reg = 13 with cost 2 vs. 32767
0x… matched stmt: reg = 5 with cost 2 vs. 32767
0x… matched reg: ADDI(reg,rc) = 6 with cost 2 vs. 2
0x… matched stmt: ASGNI(disp,reg) = 4 with cost 3 vs. 32767
stmt: ASGNI(disp,reg)
 disp: ADDRLP
 reg: disp
  disp: ADDI(reg,con)
   reg: CVCI(INDIRC(disp))
    disp: ADDRLP
   con: CNSTI
i = c + 4;

What to notice: this is Algorithm 21.2.3 running on i = c + 4 (tree ASGNI(ADDRLP i, ADDI(CVCI(INDIRC(ADDRLP c)), CNSTI 4))), one line per improvement, with 32767 as \(\infty\). The chain rules reg: disp and rc: reg fire right after every disp or reg is found. That is ChainClosure, done by the generated _closure_* functions of Algorithm 21.2.11. At the ADDI node, reg: ADDI(reg,rc) costs 2, which only ties reg: disp via disp: ADDI(reg,con) ("with cost 2 vs. 2"), so the earlier rule stays: ties go to the first rule found. The indented cover printed at the end is Reduce (Algorithm 21.2.4): the add becomes an address computation (disp), the cheaper way to use the constant 4.

lburg turns a dynamic cost into labeler code

Reproduce (lcc at commit 2b5cf358d9aa6759923dd7461f2df7f7f2a28471, GCC 13.3.0):

git clone https://github.com/drh/lcc && cd lcc
git checkout 2b5cf358d9aa6759923dd7461f2df7f7f2a28471
gcc -w -o lburg-bin lburg/gram.c lburg/lburg.c
./lburg-bin src/x86linux.md x86linux.c
grep -n 'incl %1' src/x86linux.md | head -1
grep -m1 -A8 'if (.*stmt: ASGNI4(addr,ADDI4(mem4,con1))' x86linux.c

Output (complete):

458:stmt: ASGNI4(addr,ADDI4(mem4,con1))     "incl %1\n"  memop(a)
        if (    /* stmt: ASGNI4(addr,ADDI4(mem4,con1)) */
            RIGHT_CHILD(a)->op == 4405 /* ADDI4 */
        ) {
            c = ((struct _state *)(LEFT_CHILD(a)->x.state))->cost[_addr_NT] + ((struct _state *)(LEFT_CHILD(RIGHT_CHILD(a))->x.state))->cost[_mem4_NT] + ((struct _state *)(RIGHT_CHILD(RIGHT_CHILD(a))->x.state))->cost[_con1_NT] + (memop(a));
            if (c + 0 < p->cost[_stmt_NT]) {
                p->cost[_stmt_NT] = c + 0;
                p->rule._stmt = 15;
            }
        }

What to notice: the rule x = x + 1 → incl has the dynamic cost memop(a). In src/x86.md, memop returns 3 if the store address and the load address are the same tree (sametree) and LBURG_MAX otherwise. The generated if is Algorithm 21.2.11: test the inner operator (ADDI4), add the operands' labels, add the rule's (dynamic) cost, and keep it if it improves cost[_stmt_NT]. The cost depends only on the subtree, so Proposition 21.2.12 keeps the DP optimal.

8. Comparison¶

Technique	Power / precision	Speed (asymptotic · practical)	Output / error quality	Implementation effort	Typical use
Aho–Johnson dynamic programming	optimum tiling of trees (Theorem 21.2.7); with registers, optimal for the machine class of [AJ76]	\(O(n R p)\), linear in \(n\) · lab: 59 µs per program (1.6× munch), cost 53632 = optimum	best possible for a tree; register-bounded version also minimizes spills	moderate: labels, chain closure, reduce	the lab's DP selector; HotSpot C2's matcher; textbook compilers
Tree-grammar generators (twig, iburg, lburg)	same optimum, from a grammar; dynamic costs add predicates (Proposition 21.2.12)	generated DP, linear · lcc compiles itself with it	same as DP; grammar errors surface as "no cover"	low per target once the generator exists	lcc (lburg), Jikes RVM's and HotSpot's generated matchers, many teaching compilers

Choose hand-written DP when your grammar is small and fixed (the lab), or you need register-aware costs (Aho–Johnson vectors).
Choose a generator (iburg/lburg) when you target several machines. Writing a grammar is much easier than writing and debugging a matcher, and dynamic costs let you express immediate ranges and equal-subtree conditions.

9. Assessment¶

Technique	Quiz ids (`solutions/quizzes/ch21.yaml`)	Drill	Flashcard tag	Exercises
Aho–Johnson dynamic programming	`dp-labels-running`, `dp-root-choice`	`./course drill dp-tiling`	`dp-tiling`	E3
Tree-grammar generators (twig, iburg, lburg)	`iburg-tie`, `dynamic-cost-context`	`./course drill dp-tiling` (the labels a generated labeler computes)	`iburg-lburg`	E4 ★ generates tables instead

Labeling top-down

Computing a node's label before its children's labels are final, for example by recursing into a child only when a pattern needs it, looks equivalent but can miss rules. A child reached through a large pattern is never labeled on its own, so a smaller pattern at the parent later reads \(\infty\) for it. Label every node in postorder first, then reduce.

References¶

See the chapter references.

Lesson 21.2 — Optimal tree tiling: dynamic programming, twig, iburg and lburg¶

1. Problem and motivation¶

Aho–Johnson dynamic programming¶

Tree-grammar generators (twig, iburg, lburg)¶

2. Definitions and algorithms¶

Aho–Johnson dynamic programming¶

Tree-grammar generators (twig, iburg, lburg)¶

3. Worked example¶

Aho–Johnson dynamic programming¶

Tree-grammar generators (twig, iburg, lburg)¶

4. Invariants and correctness¶

Aho–Johnson dynamic programming¶

Tree-grammar generators (twig, iburg, lburg)¶

5. Complexity¶

6. Variants and refinements¶

Aho–Johnson dynamic programming¶

Tree-grammar generators (twig, iburg, lburg)¶

7. In real compilers¶

Aho–Johnson dynamic programming¶

Tree-grammar generators (twig, iburg, lburg)¶

8. Comparison¶

9. Assessment¶

References¶