Lesson 21.3 — Bottom-up rewrite systems: BURS theory, BURG and table compression¶

Techniques: BURS theory (Pelegrí-Llopart–Graham), BURG table generation (Fraser–Henry–Proebsting, Proebsting) · Lab: labs/ch21-isel E4 ★ (a BURG-style table generator) · Prerequisites: Lesson 21.2 (labels, chain closure, Theorem 21.2.7) · Time: 4–6 hours

The dynamic program of Lesson 21.2 is optimal and linear, but it does real work at every node of every tree the compiler ever selects: it matches all rules, adds up costs, compares them and closes over chain rules. Most of that work repeats. On Tessera, every ADD whose right child is a CONST ends up with the same label differences: reg costs one more than the helper that feeds ld c(r). BURS (bottom-up rewrite system) theory makes this precise. If you normalize every label vector so that its cheapest entry is 0, only finitely many vectors occur for most real grammars. Each vector, together with the best rule for each nonterminal, is a state of a bottom-up tree automaton. A generator can enumerate all the states and tabulate the transitions ahead of time, so the compiler labels a node with one table lookup. BURG is the generator that made this practical. For the chapter's toy ISA it produces 19 states, and the running example is labeled with ten lookups and selected with cost 5, exactly as the DP does.

1. Problem and motivation¶

The input is a tile grammar $G$ (Definition 21.1.2) with constant costs. The output is a finite automaton $(Q, \delta, \lambda)$: a set of states $Q$, a transition function $\delta$ from an operator and its children's states to a state, and for each state and nonterminal the rule to use. Labeling a tree bottom-up with $\delta$ and reducing with the stored rules must give an optimum tiling. The cost moves from compile time to compiler-build time, which pays off when the compiler selects code for millions of nodes.

BURS theory (Pelegrí-Llopart–Graham)¶

Pelegrí-Llopart and Graham introduced bottom-up rewrite systems as a model of code generation: tree rewrite rules with costs, applied bottom-up, where instruction selection is the special case in which every rule rewrites a pattern into a nonterminal [PG88]. Their key theorem is that for such systems the optimal choices can be precomputed into a finite automaton whenever the relative costs are bounded, which gives optimal code with constant work per node. Balachandran, Dhamdhere and Biswas gave a simpler table construction for the tree-grammar case [BDB90], and Chase showed how to compress the tables with per-child index maps [Cha87]. Hoffmann and O'Donnell's bottom-up pattern matching [HO82] is the cost-free ancestor: it tabulates which patterns match, not which is cheapest.

BURG table generation (Proebsting)¶

Proebsting turned the theory into a fast generator. His BURS table generation builds only the reachable states with a worklist, computes transitions through representer states (projections) so the tables stay small, and prunes states with triangle trimming [Pro92, Pro95]. BURG [FHP92a] packages this as a tool with the same input language as iburg. Its generated labelers do no cost arithmetic at compile time, and it pays for that with generation time, table size, and the loss of dynamic costs.

2. Definitions and algorithms¶

Definition 21.3.1 (Normal form)

A tile grammar is in normal form if every rule is either a chain rule $A \to B$ or a base rule $A \to o(B_1, \dots, B_k)$ with an operator $o$ of arity $k$ and nonterminals $B_i$ (a leaf operator has $k = 0$). Every grammar can be put in normal form: give every inner node $x$ of a pattern (including a terminal leaf such as CONST) a fresh helper nonterminal $H_x$ with the base rule $H_x \to \mathrm{op}(x)(\dots)$ of cost 0, and let the original rule keep its cost on its top node.

Normal form of a small grammar

Take the grammar $G_s$: r1 stmt: STORE(reg, reg) (2), r2 reg: TEMP (0), r3 reg: CONST (1), r4 reg: ADD(reg, reg) (1), r5 reg: ADD(reg, CONST) (1), r6 reg: MEM(reg) (2), r7 reg: MEM(ADD(reg, CONST)) (2). In normal form, r5 becomes reg: ADD(reg, c) (1) with helper c: CONST (0), and r7 becomes reg: MEM(d) (2) with helpers d: ADD(reg, c) (0) and c: CONST (0). The two CONST helpers are equal, so we share one c. The generator in tools/course/lib/tiling.py keeps them separate (_r5_1, _r7_2), which only duplicates a column of the states.

Definition 21.3.2 (δ-states)

For a node $v$, let $C(v, \cdot)$ be its labels (Definition 21.2.1) over the nonterminals of the normal-form grammar, and let $m_v = \min_A C(v, A)$. The δ-state of $v$ is the finite partial function $\sigma_v : A \mapsto (C(v, A) - m_v,\ \mathrm{rule}(v, A))$ defined on the nonterminals with $C(v, A) < \infty$. Two nodes are equivalent if they have the same δ-state. The set of δ-states of all trees over $\Sigma$ is $Q(G)$. The grammar is BURS-finite if $Q(G)$ is finite.

Definition 21.3.3 (Transition function)

For an operator $o$ of arity $k$ and δ-states $\sigma_1, \dots, \sigma_k$, let $\hat{C}(A) = \min\{\, c(r) + \sum_i \mathrm{cost}_{\sigma_i}(B_i) \mid r = A \to o(B_1, \dots, B_k),\ \text{every } B_i \in \mathrm{dom}(\sigma_i) \,\}$, close $\hat{C}$ under the chain rules (Definition 21.2.2), and normalize by subtracting its minimum. $\delta(o, \sigma_1, \dots, \sigma_k)$ is the result (with the minimizing rules). It is undefined if no rule applies.

BURS theory (Pelegrí-Llopart–Graham)¶

Algorithm 21.3.4 (BURS table generation by worklist)

Input: a grammar $G$ in normal form with constant non-negative costs; a bound $K$ on the number of states.
Output: the reachable δ-states $Q$, the leaf states, and the table $\delta$ for every operator and every tuple of states in $Q$. Or failure "not BURS-finite" if more than $K$ states appear.
Precondition: chain rules have non-negative costs (so Close terminates; Lemma 21.2.6).
Postcondition: $Q = Q(G)$ if $G$ is BURS-finite and $K \ge \lvert Q(G) \rvert$ (Theorem 21.3.7), and $\delta$ is total on $Q$ wherever a rule applies.
Invariant: every state in $Q$ is the δ-state of some tree, and every state whose index is below done has had all its transitions with the other states of index below done computed.

function GenerateTables(G, K):
    Q ← []; index ← empty map from state to number; δ ← empty table
    for each leaf operator o (arity 0):
        s ← Intern(Transition(o, ()))
        if s ≠ none: δ[o] ← s
    done ← 0
    while done < |Q|:                            # a new state appeared in the last round
        n ← |Q|
        for each operator o of arity k ≥ 1:
            for each tuple (s1..sk) of state numbers < n with some si ≥ done:
                s ← Intern(Transition(o, (Q[s1]..Q[sk])))
                if s ≠ none: δ[o, s1..sk] ← s
        done ← n
    return Q, δ

function Transition(o, σ1..σk):                  # Definition 21.3.3
    C ← empty map (nonterminal → (cost, rule))
    for each base rule r = A → o(B1..Bk):
        if every Bi ∈ dom(σi):
            cost ← c(r) + Σ_i cost_σi(Bi)
            if A ∉ C or cost < C[A].cost: C[A] ← (cost, r)
    Close(C)                                      # chain rules, as ChainClosure (Alg. 21.2.3)
    return C

function Intern(C):
    if C is empty: return none
    m ← min over A of C[A].cost
    σ ← { A ↦ (C[A].cost − m, C[A].rule) }        # normalize
    if σ ∉ index:
        if |Q| = K: fail "more than K states: not BURS-finite"
        index[σ] ← |Q|; append σ to Q
    return index[σ]

Algorithm 21.3.5 (Labeling and reduction with the tables)

Input: a tree $t$; the tables $Q, \delta$.
Output: a state per node, then the code of an optimum tiling.
Precondition: $t$ has a tiling (so every lookup is defined).
Postcondition: the emitted tiling costs $\mathrm{OPT}(t)$ (Theorem 21.3.7).
Invariant: after labeling, $\mathrm{state}(v) = \sigma_v$ for every node $v$.

function LabelByTable(v):
    for each child u of v: LabelByTable(u)
    state[v] ← δ[op(v), state[child_1(v)], .., state[child_k(v)]]      # one lookup

function ReduceByTable(v, A):                    # Algorithm 21.2.4 with rule[v][A] from the state
    r ← the rule that Q[state[v]] records for A
    ...exactly as Reduce, with this r...

For a grammar that was put in normal form, the state records the original rule for every original nonterminal. ReduceByTable then matches that rule's whole pattern at $v$ to find its operand nodes, as Reduce does. The provided runtime of the lab works this way (isel/BurgRuntime.h).

Lemma 21.3.6 (Normalization commutes with the transition)

Let $C_1, \dots, C_k$ be the label vectors of the children of a node labeled $o$, and let $C_i' = C_i + d_i$ for constants $d_i$ (every entry shifted by $d_i$). Then the parent's label vector computed from the $C_i'$ equals the one computed from the $C_i$ shifted by $\sum_i d_i$, with the same minimizing rules. Hence the parent's δ-state depends only on the children's δ-states.

Proof

Every base rule $r = A \to o(B_1, \dots, B_k)$ has cost $c(r) + \sum_i C_i'(B_i) = c(r) + \sum_i C_i(B_i) + \sum_i d_i$. Every candidate at the parent is therefore shifted by the same amount $D = \sum_i d_i$. The minimum over rules for each $A$ is shifted by $D$ and attained by the same rules (with the same tie-breaking, since the order of the candidates is unchanged). Chain closure adds rule costs to entries of this vector, so it too commutes with a uniform shift (every inequality $c(A \to B) + C(B) < C(A)$ is invariant under adding $D$ to both $C$ values). Normalizing subtracts the minimum, which removes $D$. Choosing $d_i = -m_{u_i}$ turns each $C_i$ into (the cost part of) $\sigma_{u_i}$, so $\sigma_v$ is a function of $\sigma_{u_1}, \dots, \sigma_{u_k}$ and $o$: that function is $\delta$.

Theorem 21.3.7 (BURS tables: correctness and the finiteness condition)

(a) If Algorithm 21.3.4 terminates, then for every tree $t$, LabelByTable assigns every node $v$ its δ-state $\sigma_v$, and ReduceByTable emits a tiling of cost $\mathrm{OPT}(t)$. (b) The algorithm terminates (with $K$ large enough) if and only if $G$ is BURS-finite, and this holds if and only if there is a bound $\Delta$ such that for every tree $t$ over $\Sigma$ and every nonterminal $A$ with $C(t, A) < \infty$, $C(t, A) - \min_B C(t, B) \le \Delta$.

Proof

(a) By induction on height. Leaves: GenerateTables stored $\delta[o] = $ the normalized labels of the leaf. Inner node $v$: the children have states $\sigma_{u_i}$ (induction), and Lemma 21.3.6 shows that $\sigma_v = \mathrm{Intern}(\mathrm{Transition}(o, \sigma_{u_1}, \dots))$, which is the table entry once the algorithm has processed that tuple. It has, because the loop computes $\delta$ for every tuple of known states (invariant) and ends only when no new state appears. Since $\sigma_v$ records the same best rules as the DP labels (Lemma 21.3.6: the minimizing rules are shift-invariant), ReduceByTable follows the same rules as Reduce, and Theorem 21.2.7 gives optimality.

(b) Bounded ⇒ finite. A δ-state maps each of the $\lvert N \rvert$ nonterminals to "undefined" or to a pair (difference in $\{0, \dots, \Delta\}$, one of at most $\lvert R \rvert$ rules). So $\lvert Q(G) \rvert \le (1 + (\Delta + 1) \lvert R \rvert)^{\lvert N \rvert}$. Every state the algorithm interns is the δ-state of some tree (invariant), so it interns at most that many and stops. Finite ⇒ bounded. Take $\Delta$ as the largest difference occurring in the finitely many states of $Q(G)$. Termination ⇔ finite. If $Q(G)$ is infinite, then for every $K$ some tree has a δ-state outside any fixed set of $K$ states, and the worklist reaches it: by induction on height, every tree's δ-state is interned in some round. So the algorithm fails for every $K$.

Proposition 21.3.8 (A grammar that is not BURS-finite)

The grammar of labs/ch21-isel/rules/unbounded.rules, with rules a: TEMP (0), b: TEMP (0), a: MEM(a) (1), b: MEM(b) (2), s: MOVE(TEMP, a) (0) and s: STORE(b, b) (0), has infinitely many δ-states.

Proof

Let $t_k = \mathsf{MEM}^k(\mathsf{TEMP})$. The only $a$-derivation of $t_k$ uses a: MEM(a) $k$ times, and the only $b$-derivation uses b: MEM(b) $k$ times, so $C(t_k, a) = k$ and $C(t_k, b) = 2k$. No other nonterminal derives $t_k$ (the s rules need a statement operator). So $\sigma_{t_k} = \{a \mapsto (0, \cdot),\ b \mapsto (k, \cdot)\}$, and these states are pairwise distinct. Theorem 21.3.7(b) then says Algorithm 21.3.4 fails for every $K$. Both $a$ and $b$ are needed (MOVE uses $a$, STORE uses $b$), so no trimming that preserves optimality can remove either one. The lab's test ch21.BursFiniteness.UnboundedGrammarIsRejected checks that the generator gives up.

BURG table generation (Proebsting)¶

Definition 21.3.9 (Projections and representer states)

For an operator $o$ and a child position $i$, let $N_{o,i}$ be the set of nonterminals that occur at position $i$ of some base rule for $o$. The projection $\pi_{o,i}(\sigma)$ of a state $\sigma$ is $\sigma$ restricted to $N_{o,i}$, renormalized so its minimum is 0, with the rules dropped. The distinct projections are the representer states of position $i$. The index map $\mu_{o,i}$ sends each state number to the number of its representer [Cha87, Pro95].

Algorithm 21.3.10 (Transitions through representer states)

Input: $G$ in normal form; the states found so far.
Output: for every operator $o$ of arity $k$: index maps $\mu_{o,1..k}$ and a table $T_o$ over representer tuples, with $\delta(o, s_1..s_k) = T_o[\mu_{o,1}(s_1), \dots, \mu_{o,k}(s_k)]$.
Precondition: as for Algorithm 21.3.4.
Postcondition: the compressed tables define the same $\delta$ (Proposition 21.3.11).
Invariant: $T_o$ has one entry per tuple of representers, not per tuple of states.

function CompressedTransitions(o):
    for i = 1..k:
        reps_i ← distinct values of Project(o, i, σ) over the states σ
        μ_i[s] ← position of Project(o, i, Q[s]) in reps_i, for every state s
    for each tuple (ρ1..ρk) in reps_1 × .. × reps_k:
        T_o[ρ1..ρk] ← Intern(Transition(o, ρ1..ρk))   # Transition only reads N_{o,i} entries
    return μ, T_o

function Project(o, i, σ):
    τ ← σ restricted to N_{o,i}, costs only
    if τ is empty: return "no match"
    subtract min(τ) from every entry; return τ

Proposition 21.3.11 (Projections are sufficient)

For every operator $o$ and states $\sigma_1, \dots, \sigma_k$, $\delta(o, \sigma_1, \dots, \sigma_k) = \delta(o, \pi_{o,1}(\sigma_1), \dots, \pi_{o,k}(\sigma_k))$, where on the right a projection is read as a state.

Proof

Transition (Definition 21.3.3) reads $\sigma_i$ only at the nonterminals $B_i$ of base rules for $o$, which all lie in $N_{o,i}$. So restricting $\sigma_i$ to $N_{o,i}$ does not change any candidate cost. Renormalizing the restriction shifts all of position $i$'s costs by a constant, and by Lemma 21.3.6 that does not change the normalized result or the chosen rules. The chosen child rules, dropped by the projection, are never read by Transition.

3. Worked example¶

BURS theory (Pelegrí-Llopart–Graham)¶

Run Algorithm 21.3.4 on the grammar $G_s$ of the example after Definition 21.3.1 (normal form with helpers c: CONST and d: ADD(reg, c)). States are written as {nonterminal: difference (rule)}. The computation was checked with tiling.burs_tables in tools/course/lib/tiling.py.

round	tuple processed	unnormalized costs	new state?
0	`CONST`	reg 1 (r3), c 0	s0 =
0	`TEMP`	reg 0 (r2)	s1 =
1	`MEM`(s0)	reg: r6 2 + 1 = 3	s2 =
1	`MEM`(s1)	reg: r6 2 + 0 = 2	s2
1	`ADD`(s0, s0)	reg: r4 1+1+1 = 3, r5 1+1+0 = 2; d: 0+1+0 = 1	s3 =
1	`ADD`(s1, s0)	reg: r4 2, r5 1; d: 0	s3
1	`ADD`(s0, s1), `ADD`(s1, s1)	reg: r4 only (s1 has no `c`)	s4 =
1	`STORE`(any, any) with `reg` on both sides	stmt: r1	s5 =
2	`MEM`(s3)	reg: r6 2 + 1 = 3, r7 2 + 0 = 2	s6 =
2	`MEM`(s2), `MEM`(s4); `ADD`/`STORE` with s2–s4	as round 1	s2, s3, s4, s5
2	`MEM`(s5), `ADD`(s5, ·), …	no rule applies (s5 has no `reg`)	undefined
3	tuples with s6	`MEM`(s6) → s2; `ADD`(·, s0) → s3; other `ADD` → s4; `STORE` → s5	none: stop

Seven states. Now label a[1] = p[3], the tree STORE(ADD(TEMP a, CONST 8), MEM(ADD(TEMP p, CONST 24))), with ten lookups and no arithmetic:

node	lookup	state
`TEMP a`, `TEMP p`	leaf `TEMP`	s1
`CONST 8`, `CONST 24`	leaf `CONST`	s0
`ADD(a, 8)`, `ADD(p, 24)`	δ(ADD, s1, s0)	s3
`MEM(ADD(p, 24))`	δ(MEM, s3)	s6
`STORE(…)`	δ(STORE, s3, s6)	s5

Reduction reads the rules from the states. stmt at s5 is r1, whose operands are the ADD (s3, reg via r5: addi r1, a, 8) and the MEM (s6, reg via r7: ld r2, 24(p)). The code is addi r1, a, 8; ld r2, 24(p); st r2, 0(r1), with cost $1 + 2 + 2 = 5$, the DP's result.

BURG table generation (Proebsting)¶

Compress $\delta$ for $G_s$ with Algorithm 21.3.10. For ADD, $N_{\mathsf{ADD},1} = \{\mathsf{reg}\}$ and $N_{\mathsf{ADD},2} = \{\mathsf{reg}, c\}$.

state	$\pi_{\mathsf{ADD},1}$	$\mu_{\mathsf{ADD},1}$	$\pi_{\mathsf{ADD},2}$	$\mu_{\mathsf{ADD},2}$	$\pi_{\mathsf{MEM},1}$ (over $\{\mathsf{reg}, d\}$)	$\mu_{\mathsf{MEM},1}$
s0	{reg: 0}	0	{reg: 1, c: 0}	1	{reg: 0}	0
s1, s2, s4, s6	{reg: 0}	0	{reg: 0}	0	{reg: 0}	0
s3	{reg: 0}	0	{reg: 0}	0	{reg: 1, d: 0}	1
s5	no match	—	no match	—	no match	—

The full ADD table has $6 \times 6 = 36$ entries over the six reg-states. The compressed one has $1 \times 2$: $T_{\mathsf{ADD}}[0][0] = $ s4 and $T_{\mathsf{ADD}}[0][1] = $ s3. MEM needs 2 entries instead of 6 (s2 and s6), and STORE needs 1 instead of 36. Chase's observation [Cha87] is that most positions of real grammars have very few representers.

Try it

The lab's part B (E4 ★) asks you to write Algorithm 21.3.4 for any rules file. Check your tables by selecting code with the provided runtime: ch21-burg gen labs/ch21-isel/rules/tessera.rules > t.tab && ch21-burg run labs/ch21-isel/rules/tessera.rules t.tab labs/ch21-isel/inputs/running.tree. For practice labeling by hand, ./course drill dp-tiling --seed 5 --difficulty medium --solution shows the labels whose normalized differences are the states.

4. Invariants and correctness¶

BURS theory (Pelegrí-Llopart–Graham)¶

Lemma 21.3.6 is the heart of BURS: only differences between nonterminals matter, because a parent adds the same constant to all candidates. Theorem 21.3.7 gives correctness and the exact finiteness condition. Proposition 21.3.8 shows the condition can fail even for tiny grammars: two nonterminals whose costs grow at different rates along the same family of trees. For grammars used in practice, differences are bounded because every value class can be converted into every other at a bounded cost (a reg can always be stored to mem or loaded back). This is the chain-rule argument: if for all nonterminals $A, B$ that derive a common tree there is a chain of rules from $B$ to $A$ of cost at most $c_{\max}$, then $\Delta \le c_{\max}$.

The preconditions that break the construction are dynamic costs, which make the state depend on attributes of the node that the tables cannot see, and non-constant chain costs, for the same reason. BURG therefore rejects them, and iburg/lburg (Lesson 21.2) exist partly to allow them.

BURG table generation (Proebsting)¶

Proposition 21.3.11 justifies the compression. Proebsting's triangle trimming goes further: it removes a nonterminal $A$ from a state when some other nonterminal $B$ in the state can be converted to $A$ by chain rules at a total cost no greater than $A$'s own difference. Then $A$ can never be needed at that cost, because every use of $A$ can be served through $B$. Removing such entries merges states that differ only in useless information and never changes the chosen tiling's cost [Pro95, §4]. The finiteness question is about the trimmed states. Trimming can make a grammar finite whose untrimmed state set is infinite, which Proposition 21.3.8's grammar does not allow, since neither nonterminal can be derived from the other.

5. Complexity¶

Variables: $\lvert Q \rvert$ states, $\lvert N \rvert$ nonterminals, $R$ rules, $k_{\max}$ the largest arity, $\rho_{o,i}$ the number of representers of position $i$ of operator $o$, $n$ tree nodes.

Technique	Generation time	Table size	Labeling time	Justification
BURS theory, uncompressed tables	$O(\lvert Q \rvert^{k_{\max}} \cdot (R + \lvert N \rvert R_c))$ per round, $\le \lvert Q \rvert$ rounds	$\sum_o \lvert Q \rvert^{\mathrm{ar}(o)}$ entries	$\Theta(n)$ lookups, $O(1)$ each	one `Transition` per tuple (Algorithm 21.3.4)
BURG with representers	$O(\sum_o \prod_i \rho_{o,i} \cdot R)$ plus projecting each state	$\sum_o \prod_i \rho_{o,i}$ plus index maps $\sum_{o,i} \lvert Q \rvert$	$\Theta(n)$ lookups plus index-map reads	Algorithm 21.3.10 and Proposition 21.3.11

Numbers on the lab grammars. Tessera (20 rules) has 19 states and 1155 transitions in the uncompressed table the lab's reference generator emits. The chain-rule version tessera-chain.rules has 16 states. The small grammar $G_s$ of §3 has 7 states, and representers shrink its binary tables from 36 to 1–2 entries.

A pathological family. The number of states can be exponential in the number of nonterminals. Take nonterminals $A_1, \dots, A_m$ and a hub $Z$, a leaf operator $\mathsf{X}$ with rules $A_i \to \mathsf{X}$ (cost 0), chain rules $Z \to A_i$ (cost 1) and $A_i \to Z$ (cost 0) for every $i$, and unary operators $\mathsf{F}_1, \dots, \mathsf{F}_m$ with rules $A_i \to \mathsf{F}_j(A_i)$ of cost 1 if $i = j$ and 0 otherwise. The chain rules let every $A_i$ be derived from every $A_j$ at cost 1, so all differences are 0 or 1 and the grammar is BURS-finite. Applying $\mathsf{F}_j$ raises $A_j$ to difference 1 and keeps the others. By induction on the number of operators applied, the tree $\mathsf{F}_{j_1}(\cdots \mathsf{F}_{j_q}(\mathsf{X}))$ has difference 1 exactly on $\{A_{j_1}, \dots, A_{j_q}\}$ as long as that set is not all of them. So every proper subset of $\{A_1, \dots, A_m\}$ appears as a distinct state: $\lvert Q \rvert \ge 2^m - 1$ with only $O(m^2)$ rules. A 20-rule grammar like Tessera does not do this, but the bound in Theorem 21.3.7 is not just an artifact of the proof.

Real-world scale. The iburg paper presents iburg as the simpler alternative to BURG: its labelers do cost arithmetic at every node, where BURG's do one lookup, and in exchange its generator is a few hundred lines and allows dynamic costs [FHP92b]. The measured comparisons are in the BURG and iburg papers [FHP92a, FHP92b]. On the lab's scale, table labeling of the running example takes 10 lookups, where the DP of Lesson 21.2 makes 16 successful rule matches (and more failed attempts) and adds up their costs.

BURS theory (Pelegrí-Llopart–Graham)¶

Full rewrite systems [PG88]: rules may rewrite a tree into another tree (commutativity, a − b → a + (−b)), not only into a nonterminal. This is more expressive, but the state construction becomes the local-rewrite-graph machinery of the paper and much harder to implement. Grammar-only BURS is what survived.
Top-down vs bottom-up automata [HO82]: top-down automata are smaller for some pattern sets but cannot carry cost differences upwards as naturally. Every cost-based generator after BURS is bottom-up.
Offline matching without costs (LLVM's DAG ISel matcher table): precompile the patterns into a decision table interpreted at compile time, but choose by a fixed priority instead of by cost (Lesson 21.5). This drops optimality to keep DAG support and C++ predicates.

BURG table generation (Proebsting)¶

Representer states / index maps [Cha87, Pro95]: much smaller tables for one extra indirection per child.
Triangle and chain-rule trimming [Pro95]: fewer states. Some grammars become finite that were not.
On-demand (lazy) state construction: build states the first time a tuple occurs while compiling and cache them. This keeps BURG's constant-time labeling after warm-up without enumerating unreachable states. Several later generators (for example jburg and wburg, surveyed in [Bli16, Ch. 3]) take this approach.

7. In real compilers¶

BURS theory (Pelegrí-Llopart–Graham)¶

No compiler you can run in this course ships BURS cost tables. The idea of precompiling the matcher is everywhere, though: LLVM's DAG instruction selector is a table generated by TableGen at build time and interpreted by SelectionDAGISel::SelectCodeCommon in llvm/lib/CodeGen/SelectionDAG/SelectionDAGISel.cpp (LLVM 23.1.2) [LLVM-SDISel]. The table is a bottom-up/top-down hybrid decision tree over opcodes, not a cost automaton. BURS-style generators were used in production by lcc's predecessors, by Jikes RVM's optimizing compiler and by JIT and embedded code generators surveyed in [Bli16, Ch. 3].

A precompiled matcher: the ADD part of Tessera's TableGen matcher table

Reproduce (llvm-tblgen 23.1.2; Tessera.td from Lesson 21.1 §7):

llvm-tblgen -gen-dag-isel -I "$(llvm-config --includedir)" Tessera.td \
  | sed -n '/TARGET_VAL(ISD::ADD)/,/TARGET_VAL(ISD::MUL)/p' | grep -E 'OPC_|Scope' | head -24

Output (abridged to the first 24 lines of the ADD case):

/*     42*/  OPC_Scope /*5 children */, 20, // ->64
/*     44*/   OPC_RecordChild0, // #0 = $s
/*     45*/   OPC_MoveChild1,
/*     46*/   OPC_CheckOpcode, TARGET_VAL(ISD::SHL),
/*     49*/   OPC_RecordChild0, // #1 = $t
/*     50*/   OPC_RecordChild1, // #2 = $k
/*     51*/   OPC_MoveChild1,
/*     52*/   OPC_CheckOpcode, TARGET_VAL(ISD::Constant),
/*     55*/   OPC_MoveParent,
/*     56*/   OPC_MoveParent,
/*     57*/   OPC_EmitConvertToTarget2, // #3 = ConvertToTarget #2
/*     58*/   OPC_MorphNodeTo1None, TARGET_VAL(Tessera::SHADD),
/*     64*/  /*Scope*/ 20, // ->85
/*     65*/   OPC_MoveChild0,
/*     66*/   OPC_CheckOpcode, TARGET_VAL(ISD::SHL),
/*     69*/   OPC_RecordChild0, // #0 = $t
/*     70*/   OPC_RecordChild1, // #1 = $k
/*     71*/   OPC_MoveChild1,
/*     72*/   OPC_CheckOpcode, TARGET_VAL(ISD::Constant),
/*     75*/   OPC_MoveParent,
/*     76*/   OPC_MoveParent,
/*     77*/   OPC_RecordChild1, // #2 = $s
/*     78*/   OPC_EmitConvertToTarget1, // #3 = ConvertToTarget #1
/*     79*/   OPC_MorphNodeTo1None, TARGET_VAL(Tessera::SHADD),

What to notice: like a BURS table, all the pattern-matching work was done when the compiler was built. At compile time the selector only interprets bytes: switch on the node's opcode, then try each OPC_Scope alternative (one per pattern, largest first) and backtrack to the next scope on a failed OPC_CheckOpcode. Unlike BURS, there are no states and no costs. Each check walks the DAG node's children again instead of looking up a precomputed state per node, and the first pattern that matches wins.

BURG table generation (Proebsting)¶

The lab's reference generator (solutions/labs/ch21-isel/src/Burg.cpp) implements Algorithm 21.3.4 without compression. It is the course's code, not a production system, but it produces BURG-style tables for any rules file and the provided runtime uses them with no cost arithmetic.

BURS tables for Tessera, and an unbounded grammar rejected

Reproduce (course lab tools, built with -DPEBBLE_USE_SOLUTION=isel against LLVM 23.1.2; B is your build directory):

B=build/linux
$B/bin/ch21-burg gen labs/ch21-isel/rules/tessera.rules > tessera.tab
grep -v '^trans' tessera.tab
grep -c '^trans' tessera.tab
$B/bin/ch21-burg run labs/ch21-isel/rules/tessera.rules tessera.tab labs/ch21-isel/inputs/running.tree
$B/bin/ch21-burg gen labs/ch21-isel/rules/unbounded.rules --max-states=100

Output (complete):

burs 1
# 19 states
state 0: reg=r7/1
state 1: reg=r6/0
state 2: reg=r19/1
state 3: reg=r17/2
state 4: reg=r9/1
state 5: reg=r8/1
state 6: reg=r11/0
state 7: reg=r10/0
state 8: reg=r12/3
state 9: reg=r15/1
state 10: reg=r14/0
state 11: stmt=r1/0
state 12: stmt=r4/0
state 13: stmt=r2/0
state 14: reg=r18/1
state 15: reg=r20/1
state 16: reg=r16/0
state 17: reg=r13/0
state 18: stmt=r3/0
leaf CONST 0
leaf TEMP 1
1155
  shadd r1, a, i, 3
  ld r2, 24(p)
  st r2, 0(r1)
cost 5
ch21-burg: more than 100 states: the grammar is not BURS-finite (normalized costs grow without bound)

What to notice: each state line is a δ-state (Definition 21.3.2) restricted to Tessera's own nonterminals. The differences are measured from the cheapest nonterminal including the hidden helper nonterminals of the normal form. That is why state 0 (a CONST) says reg=r7/1: its helper, the CONST operand of addi, costs 0. No state ever records r5 movm, because st + ld always tie it and ties go to the lower rule number. The automaton shows at a glance that movm is never part of an optimum tiling. The run selects the running example with 10 lookups and cost 5, and the last line is Proposition 21.3.8 on the generator's state limit.

8. Comparison¶

Technique	Power / precision	Speed (asymptotic · practical)	Output / error quality	Implementation effort	Typical use
BURS theory (Pelegrí-Llopart–Graham)	optimum tiling (Theorem 21.3.7) when the grammar is BURS-finite; no dynamic costs	labeling $\Theta(n)$ with $O(1)$ per node; generation up to exponential in the grammar	same code as DP; a non-finite grammar is rejected at build time	high: normal form, closure, state interning	the theory behind BURG; offline tables for fixed grammars
BURG table generation (Proebsting)	same, with representers and trimming	one lookup per node, no cost arithmetic; tables of $\sum_o \prod_i \rho_{o,i}$ entries	same code as DP	high generator, trivial runtime	historical production back ends, embedded and JIT generators; the lab's part B

Choose BURS/BURG tables when the grammar is fixed, has constant costs, and compile time per node matters more than build time or table size.
Choose iburg/lburg DP (Lesson 21.2) when you need dynamic costs (immediate ranges, same-address checks) or quick grammar edits.

9. Assessment¶

Technique	Quiz ids (`solutions/quizzes/ch21.yaml`)	Drill	Flashcard tag	Exercises
BURS theory (Pelegrí-Llopart–Graham)	`burs-state-count`, `burs-normalize`	`./course drill dp-tiling` (states are normalized labels)	`burs`	E4 ★
BURG table generation (Proebsting)	`burg-representers`, `burg-vs-iburg`	none: table generation is a whole-grammar computation; the lab's part B tests it on three grammars instead	`burg`	E4 ★

Normalizing too late

If you intern states before normalizing, every tree gets its own state, because absolute costs grow with tree size, and generation never terminates, even for Tessera. The normalization of Definition 21.3.2 is what makes the state set finite. Lemma 21.3.6 is what makes it correct to throw the absolute costs away.

References¶

See the chapter references.

Technique	Generation time	Table size	Labeling time	Justification
BURS theory, uncompressed tables	\(O(\lvert Q \rvert^{k_{\max}} \cdot (R + \lvert N \rvert R_c))\) per round, \(\le \lvert Q \rvert\) rounds	\(\sum_o \lvert Q \rvert^{\mathrm{ar}(o)}\) entries	\(\Theta(n)\) lookups, \(O(1)\) each	one `Transition` per tuple (Algorithm 21.3.4)
BURG with representers	\(O(\sum_o \prod_i \rho_{o,i} \cdot R)\) plus projecting each state	\(\sum_o \prod_i \rho_{o,i}\) plus index maps \(\sum_{o,i} \lvert Q \rvert\)	\(\Theta(n)\) lookups plus index-map reads	Algorithm 21.3.10 and Proposition 21.3.11

Technique	Power / precision	Speed (asymptotic · practical)	Output / error quality	Implementation effort	Typical use
BURS theory (Pelegrí-Llopart–Graham)	optimum tiling (Theorem 21.3.7) when the grammar is BURS-finite; no dynamic costs	labeling \(\Theta(n)\) with \(O(1)\) per node; generation up to exponential in the grammar	same code as DP; a non-finite grammar is rejected at build time	high: normal form, closure, state interning	the theory behind BURG; offline tables for fixed grammars
BURG table generation (Proebsting)	same, with representers and trimming	one lookup per node, no cost arithmetic; tables of \(\sum_o \prod_i \rho_{o,i}\) entries	same code as DP	high generator, trivial runtime	historical production back ends, embedded and JIT generators; the lab's part B

Lesson 21.3 — Bottom-up rewrite systems: BURS theory, BURG and table compression¶

1. Problem and motivation¶

BURS theory (Pelegrí-Llopart–Graham)¶

BURG table generation (Proebsting)¶

2. Definitions and algorithms¶

BURS theory (Pelegrí-Llopart–Graham)¶

BURG table generation (Proebsting)¶

3. Worked example¶

BURS theory (Pelegrí-Llopart–Graham)¶

BURG table generation (Proebsting)¶

4. Invariants and correctness¶

BURS theory (Pelegrí-Llopart–Graham)¶

BURG table generation (Proebsting)¶

5. Complexity¶

6. Variants and refinements¶

BURS theory (Pelegrí-Llopart–Graham)¶

BURG table generation (Proebsting)¶

7. In real compilers¶

BURS theory (Pelegrí-Llopart–Graham)¶

BURG table generation (Proebsting)¶

8. Comparison¶

9. Assessment¶

References¶