Lesson 21.4 — Beyond trees: DAG covering, NP-completeness and near-optimal selection¶

Techniques: tree decomposition and greedy DAG matching; NOLTIS (Koes–Goldstein); PBQP and ILP formulations (Eckstein–König–Scholz, Ebner et al.) · Prerequisites: Lesson 21.2 (dynamic programming), Lesson 8.3 (expression DAGs) · Time: 4–6 hours

Real IR is not a forest of trees. In x = a*b + c; y = a*b + d the product has two users, and in a load/store pair on p + 8 the address has two users. The value-numbered DAG of a block (Lesson 8.3), LLVM's SelectionDAG and SSA use–def graphs are all DAGs. A shared node can be computed once into a register, which saves recomputation but stops any tile from covering it. Or it can be recomputed inside each user's tile, which duplicates work but lets both users use big instructions. Which is better depends on the costs. On the toy ISA of this chapter, sharing wins for a multiplication (cost 7 instead of 8) and duplication wins for an address (cost 5 instead of 6). Finding the best mix is NP-complete (Theorem 21.4.4). Real selectors therefore use heuristics: cut the DAG into trees (the classic approach and lcc's), fold greedily with a single-use rule (LLVM), or run the DP twice with a cost model for sharing (NOLTIS). Optimum solvers exist for smaller problems: PBQP and integer linear programming.

1. Problem and motivation¶

The input is a DAG $D$ (a basic block's expression DAG, or LLVM's SelectionDAG) with root nodes that must be computed (stores, the block's live-out values), and a tile grammar $G$. The output is a set of tile instances that computes all roots, where every value a tile needs is produced by another chosen tile, and whose total cost is minimum. Unlike on trees, one node can be covered by several tiles. Lesson 21.5 shows LLVM's version: the SelectionDAG selector matches patterns on a DAG and decides greedily, node by node, whether an operand may be folded.

Tree decomposition and greedy DAG matching¶

The oldest answer is to avoid the problem. Split the DAG at every node with more than one user, compute that node into a register (a temporary), and tile each resulting tree optimally with the DP of Lesson 21.2. The Dragon book presents code generation for basic blocks this way [Dragon2, §8.5, §8.9], and lcc does it with undag [LCC-Src]. The greedy DAG matchers of production compilers are a refinement of the same idea: match patterns directly on the DAG, but allow a pattern to swallow a shared node only in special cases, such as cheap address arithmetic.

NOLTIS¶

Koes and Goldstein asked how close a linear-time algorithm can get to the optimum on DAGs. Their NOLTIS ("near-optimal linear-time instruction selection") runs the tree DP on the DAG as if shared nodes could be duplicated freely. Where that leads to recomputing a shared node, it compares the cost of the recomputation with the cost of computing the node once, fixes the nodes where sharing is cheaper, and runs the DP again [KG08]. They report that on their benchmarks NOLTIS finds an optimal tiling (checked against an integer-programming optimum) in 99.7 % of the cases.

PBQP and ILP formulations¶

Eckstein, König and Scholz formulated instruction selection on the SSA graph of a whole function as a partitioned Boolean quadratic problem (PBQP): every node chooses one rule, and edge cost matrices charge for incompatible choices [EKS03]. Ebner et al. generalized it to patterns with several results (DAG patterns) and implemented it in LLVM, reporting code quality close to optimal with acceptable compile times [EBSKWK08]. Integer linear programming (ILP) and constraint programming formulations give true optima at a higher price. Blindell's universal instruction selection models selection, global code motion and block placement together as one constraint problem [Bli16, Ch. 4–5].

2. Definitions and algorithms¶

Definition 21.4.1 (Expression DAG)

An expression DAG is a finite directed acyclic graph $D = (V, E)$ whose nodes are labelled with operators of $\Sigma$ (Definition 21.1.1), with ordered children $\mathrm{child}_1(v), \dots, \mathrm{child}_{\mathrm{ar}(v)}(v)$, together with a set $\mathrm{Roots} \subseteq V$ of nodes that must be computed. A node is shared if it has more than one parent. A tree is a DAG without shared nodes and with one root.

Definition 21.4.2 (DAG cover)

A tile instance is a pair $(v, r)$ of a node and a rule $r = A \to \pi$ whose pattern matches at $v$ (Definition 21.1.3, reading the children of the DAG); it produces $A$ at $v$. A set $X$ of tile instances is a cover of $D$ if (i) for every root $v$ there is an instance $(v, r) \in X$ producing the start nonterminal (or the nonterminal the root requires), and (ii) for every instance $(v, r) \in X$ and every operand $(u, B)$ of $r$ at $v$, there is an instance $(u, r') \in X$ producing $B$ (for a chain rule $A \to B$, an instance producing $B$ at $v$ itself). The cost is $\sum_{(v, r) \in X} c(r)$: every instance is paid once, however many tiles use its value. Nodes may lie inside several instances' patterns (overlap, which means recomputation). $\mathrm{OPT}(D)$ is the minimum cost of a cover.

Definition 21.4.3 (The DAG covering problem)

DAG-COVER: given a grammar $G$, a DAG $D$ and an integer $K$, is there a cover of $D$ of cost at most $K$?

Theorem 21.4.4 (DAG covering is NP-complete)

DAG-COVER is NP-complete, even for one fixed grammar whose rule costs are 0 and 1.

Proof

Membership in NP. A cover contains at most $\lvert V \rvert \cdot \lvert R \rvert$ instances, so it is a certificate of polynomial size. Conditions (i) and (ii) and the cost can be checked in polynomial time.

Hardness, by reduction from 3-SAT. Fix the grammar $G_{\mathrm{SAT}}$ with operators $\mathsf{X}/0$ and $\mathsf{C}_s/3$ for each sign pattern $s \in \{+, -\}^3$ (eight operators), nonterminals $T, F, A, \mathsf{stmt}$, and rules $T \to \mathsf{X}$ (cost 1), $F \to \mathsf{X}$ (cost 1), $A \to T$ (0), $A \to F$ (0), and, for every $s$ and every position $i \in \{1, 2, 3\}$, a rule $\mathsf{stmt} \to \mathsf{C}_s(Y_1, Y_2, Y_3)$ (cost 0) with $Y_i = T$ if $s_i = +$, $Y_i = F$ if $s_i = -$, and $Y_j = A$ for $j \ne i$. (That is $4 + 24 = 28$ rules, fixed once and for all.) Given a formula with variables $x_1, \dots, x_m$ and clauses $c_1, \dots, c_\ell$, where each clause has three distinct variables and every variable occurs in some clause, build $D$ with one node $\mathsf{X}_j$ per variable and one root $\mathsf{C}_{s(c)}(\mathsf{X}_{j_1}, \mathsf{X}_{j_2}, \mathsf{X}_{j_3})$ per clause, where $s(c)$ records the signs of $c$'s literals. Set $K = m$.

(⇒) Given a satisfying assignment $\alpha$, take the instance $(\mathsf{X}_j, T \to \mathsf{X})$ if $\alpha(x_j)$ is true and $(\mathsf{X}_j, F \to \mathsf{X})$ otherwise, the matching chain instance $A \to T$ or $A \to F$ at every $\mathsf{X}_j$, and at each clause root the rule for a position $i$ whose literal $\alpha$ makes true. Its operand $Y_i$ is exactly the nonterminal produced at that variable, and the others are $A$, which is produced everywhere. This is a cover of cost $m$.

(⇐) Every variable node is an operand of some clause root, so any cover contains at least one of $(\mathsf{X}_j, T \to \mathsf{X})$ and $(\mathsf{X}_j, F \to \mathsf{X})$ for every $j$ ($A$ can only be produced through $T$ or $F$). So its cost is at least $m$, and a cover of cost $\le m$ contains exactly one of them per variable. Define $\alpha(x_j) = $ true iff the $T$ instance is chosen. Each clause root has some instance $\mathsf{stmt} \to \mathsf{C}_s(\dots)$ in the cover, whose position $i$ requires $T$ (or $F$) at that variable, and that is the variable's only choice, so the literal at position $i$ is true under $\alpha$. Every clause is satisfied.

The construction is polynomial, so 3-SAT $\le_p$ DAG-COVER. Proebsting gives a similar reduction [Pro98]. For costs that include register pressure, the problem was already known to be NP-complete for one-register machines [BS76] and for DAGs with common subexpressions [AJU77].

The reduction on a two-clause formula

$(x_1 \lor \lnot x_2 \lor x_3) \land (\lnot x_1 \lor x_2 \lor x_3)$ gives variable nodes $\mathsf{X}_1, \mathsf{X}_2, \mathsf{X}_3$ and roots $\mathsf{C}_{+-+}(\mathsf{X}_1, \mathsf{X}_2, \mathsf{X}_3)$ and $\mathsf{C}_{-++}(\mathsf{X}_1, \mathsf{X}_2, \mathsf{X}_3)$, with $K = 3$. The assignment $x_1 = x_2 = $ true, $x_3 = $ false gives the cover $\{(\mathsf{X}_1, T), (\mathsf{X}_2, T), (\mathsf{X}_3, F)\}$ plus chains to $A$, the first root using position 1 ($T$ at $\mathsf{X}_1$) and the second position 2 ($T$ at $\mathsf{X}_2$). Its cost is 3.

Tree decomposition and greedy DAG matching¶

Algorithm 21.4.5 (Tree decomposition)

Input: an expression DAG $D$; a grammar $G$ in which a value in a register can be read as the leaf nonterminal (Tessera: reg: TEMP).
Output: a cover of $D$ (and its code).
Precondition: $G$ derives every node of every resulting tree.
Postcondition: every cut node is the root of a tile instance and lies strictly inside no instance (its users read its register), and the cover is optimum among covers with that property (Proposition 21.4.7).
Invariant: the trees are processed in a topological order of the DAG, so a shared node's register is written before any tree reads it.

function TreeDecomposition(D):
    cut ← Roots ∪ { v | v has more than one parent }
    for each v in cut, in topological order (children before parents):
        T_v ← the tree rooted at v obtained by stopping at every other node of cut
              (a stopped node u becomes the leaf  TEMP t_u)
        goal ← (v ∈ Roots and v is a statement) ? S : reg
        Label(T_v); Reduce(T_v, goal)                  # Algorithms 21.2.3 and 21.2.4
        if v is not a statement: record that t_u names the register of the result

Algorithm 21.4.6 (Greedy DAG matching with a fold rule)

Input: an expression DAG $D$; patterns ordered by priority (Algorithm 21.1.8's size, or LLVM's complexity).
Output: a cover.
Precondition: every node has a matching single-operator pattern.
Postcondition: every node is either a tile root or covered by a tile of one of its users. A shared node lies inside a tile only if the target's Foldable allows it.
Invariant: nodes are selected from the roots downwards (reverse topological order). When a node is selected, all its users are already selected.

function GreedyDAG(D):
    for each node v in reverse topological order:
        if v is inside a tile already chosen for all of its users: continue
        for each pattern π in priority order:
            if MatchesDAG(π, v): choose (v, π); break

function MatchesDAG(π, v):              # like Matches, but an inner pattern node may
    ...                                 # swallow a DAG node u only if Foldable(u, v):
function Foldable(u, v):
    return u has a single use                      # LLVM: IsProfitableToFold
           and folding u into v creates no cycle   # LLVM: IsLegalToFold
           or u is cheap address arithmetic the target duplicates on purpose

Proposition 21.4.7 (What tree decomposition guarantees)

Algorithm 21.4.5 returns a valid cover. Among all covers in which every shared node is the root of an instance producing reg and lies strictly inside no instance (every user reads the shared value from its register), it is optimum. In general it is not optimum: there are DAGs where recomputing a shared node is strictly cheaper.

Proof

Validity. Each tree $T_v$ is covered by a derivation (Theorem 21.2.7), whose leaves are either real leaves or the registers of cut nodes. Every cut node is itself a root of some $T_u$ covered for reg. So condition (ii) of Definition 21.4.2 holds, and condition (i) holds for the roots. Restricted optimality. In a cover of the restricted kind, no instance crosses a cut node, so the instances split into independent covers of the trees $T_v$ (a shared node appears in its users' trees only as the leaf TEMP t_u). The minimum of the sum is the sum of the minima, which the DP computes for each tree. Not optimum in general: Example D1 in §3 has a cover of cost 5, while decomposition costs 6.

NOLTIS¶

Definition 21.4.8 (Overlap and CSE costs, as used in this course)

Run the tree DP (Algorithm 21.2.3) on $D$ as if every node had its own copy for each parent, and let $\Phi$ be the tiles chosen top-down from the roots. For a shared node $n$ that lies strictly inside tiles $T_1, \dots, T_q$ of $\Phi$ and is the root of none of them:

the overlap cost $\omega(n) = \sum_{i} \bigl(c(T_i) - c(T_i \setminus n)\bigr)$, where $c(T_i)$ is the tile's cost at its root and $c(T_i \setminus n)$ is the cheapest cost at the same root and goal if $n$ were a register leaf of cost 0 (the extra work each tile does by recomputing $n$);
the CSE cost $\kappa(n) = C(n, \mathsf{reg})$, the cost of computing $n$ once.

Koes and Goldstein's definitions differ in detail (they also account for tiles that overlap $n$ only partially), but they make the same comparison [KG08].

Algorithm 21.4.9 (NOLTIS, after [KG08])

Input: an expression DAG $D$ and a grammar $G$.
Output: a cover of $D$.
Precondition: as for the tree DP. The DAG is given with parent lists.
Postcondition: a valid cover (Proposition 21.4.10) in which every shared node $n$ with $\kappa(n) < \omega(n)$ in the first pass is a tile root.
Invariant: in the second DP, no pattern may place a fixed node strictly inside a tile.

function NOLTIS(D):
    fixed ← {}
    DAGLabel(D, fixed)                            # tree DP on the DAG, sharing ignored
    Φ ← TopDownSelect(D)                          # tiles reachable from the roots
    for each shared node n covered only strictly inside tiles of Φ:
        if κ(n) < ω(n): fixed ← fixed ∪ {n}       # Definition 21.4.8
    DAGLabel(D, fixed)
    return TopDownSelect(D)

function DAGLabel(D, fixed):
    for each node v in topological order (children first):
        Label(v) as in Algorithm 21.2.3, except that a pattern whose inner node would map to
        a node of fixed does not match, and a fixed node's label is read as 0 by its parents
        (its cost is paid once, at its own tile)

function TopDownSelect(D):
    work ← [(v, goal of v) for v in Roots] + [(n, reg) for n in fixed]; chosen ← {}
    while work is not empty:
        (v, A) ← pop(work)
        if (v, A) already handled: continue
        r ← rule[v][A]; chosen ← chosen ∪ {(v, r)}
        push every operand (u, B) of r at v onto work
    return chosen

Proposition 21.4.10 (NOLTIS is valid and linear)

Algorithm 21.4.9 returns a cover of $D$ in time $O(\lvert V \rvert + \lvert E \rvert)$ for a fixed grammar.

Proof

Validity. TopDownSelect starts from every root with its required goal and, for every chosen instance, pushes every operand with the nonterminal it needs. A pair is handled once and receives the rule that DAGLabel found for it, which exists because labels are computed for every node (the grammar derives every node, as for trees). So conditions (i) and (ii) of Definition 21.4.2 hold when the work list empties. Time. Each of the two labeling passes visits every node once and tries $O(R)$ rules of size $O(p)$, a constant for a fixed grammar. TopDownSelect handles each (node, nonterminal) pair at most once, and there are $O(\lvert V \rvert \cdot \lvert N \rvert)$ of them. Computing $\omega$ for all shared nodes re-labels each covering tile's root once with $n$ cut, $O(1)$ per (tile, node) incidence, and the incidences are bounded by $O(\lvert V \rvert p)$.

PBQP and ILP formulations¶

Definition 21.4.11 (PBQP for instruction selection)

Put $G$ in normal form, sharing identical helper nonterminals (Definition 21.3.1). A PBQP instance has one variable $x_v$ per DAG node, ranging over the normal-form rules whose operator is $v$'s operator, a cost vector $\vec{c}_v[r] = c(r)$, and for every edge $(v, u)$, where $u$ is the $i$-th child of $v$, a cost matrix $M_{vu}[r][r'] = $ the cheapest chain-rule cost from the nonterminal $r'$ produces to the nonterminal $r$ expects at position $i$ (0 if equal, $\infty$ if impossible). A solution assigns a rule to every variable and costs $\sum_v \vec{c}_v[x_v] + \sum_{(v, u)} M_{vu}[x_v][x_u]$.

Algorithm 21.4.12 (PBQP by reduction, after Scholz–Eckstein)

Input: a PBQP instance (a graph with vectors on nodes and matrices on edges).
Output: an assignment $x$.
Precondition: vector and matrix entries are in $\mathbb{N} \cup \{\infty\}$.
Postcondition: if only R0, R1 and R2 were needed, $x$ is optimum (Theorem 21.4.13). Otherwise it is a heuristic solution.
Invariant: the instance on the remaining nodes, with the folded vectors and matrices, has the same optimum as the original restricted to those nodes.

function SolvePBQP(G):
    stack ← []
    while G has nodes:
        if some node y has degree 0:  push (R0, y); remove y
        elif some node y has degree 1 (neighbor z):                    # R1
            for each choice j of z: c_z[j] += min_i (c_y[i] + M_yz[i][j])
            push (R1, y); remove y
        elif some node y has degree 2 (neighbors z, w):                # R2
            for each j, k: M_zw[j][k] += min_i (c_y[i] + M_yz[i][j] + M_yw[i][k])
            push (R2, y); remove y
        else:                                                          # RN: heuristic
            y ← a node of highest degree; fix x_y ← argmin_i (c_y[i] + Σ_z min_j M_yz[i][j])
            fold x_y into its neighbors' vectors; push (RN, y); remove y
    while stack is not empty:                                          # back-propagation
        (rule, y) ← pop(stack)
        if rule ≠ RN: x_y ← the i minimizing y's term given the already chosen neighbors
    return x

Theorem 21.4.13 (R0, R1 and R2 preserve the optimum)

Removing a node of degree at most 2 with the updates of Algorithm 21.4.12 gives an instance whose optimum equals the original optimum. Back-propagation reconstructs an optimum assignment of the removed node. Hence if the graph can be reduced with R0–R2 alone (every series-parallel graph can), the solution is optimum.

Proof

The objective is a sum of terms, and the removed node $y$ appears only in its own vector and in the matrices of its at most two edges. For fixed choices of the neighbors, the best choice of $y$ is $\min_i$ of exactly those terms. So $\min_{x} \mathrm{cost}(x) = \min_{x_{-y}} \bigl( \mathrm{cost}_{-y}(x_{-y}) + \min_{i} (c_y[i] + M_{yz}[i][x_z] + M_{yw}[i][x_w]) \bigr)$. R1 adds this inner minimum (with one neighbor) to $z$'s vector, and R2 adds it (with two neighbors) to the $z$–$w$ matrix, creating the edge if needed. R0 adds the constant $\min_i c_y[i]$. In each case the reduced instance's objective equals the inner minimization of the original, so the optima agree. Back-propagation picks, given the neighbors' final values, an $i$ attaining that inner minimum, which yields an optimum of the original. By induction over the stack, all removed nodes are assigned optimally.

Definition 21.4.14 (ILP formulation)

Binary variables $y_{v,r}$ for every node $v$ and matching rule $r$. Minimize $\sum_{v,r} c(r)\, y_{v,r}$ subject to: $\sum_{r \text{ produces the required goal}} y_{v,r} \ge 1$ for every root $v$; and for every $(v, r)$ and every operand $(u, B)$ of $r$ at $v$, $y_{v,r} \le \sum_{r' \text{ produces } B \text{ at } u} y_{u,r'}$. The feasible 0/1 points are exactly the covers of Definition 21.4.2, so the ILP optimum is $\mathrm{OPT}(D)$.

3. Worked example¶

Two small DAGs over Tessera (Table 21.1.1), each a basic block with two statements.

D1 (a shared address): STORE(q, TEMP z) then MOVE(TEMP x, MEM(q)) with the shared node $q = $ ADD(TEMP p, CONST 8).
D2 (a shared product): MOVE(TEMP x, ADD(m, TEMP c)) and MOVE(TEMP y, ADD(m, TEMP d)) with the shared node $m = $ MUL(TEMP a, TEMP b).

flowchart TD
  s1([s1: STORE]) --> q[q: ADD]
  s1 --> z[TEMP z]
  s2([s2: MOVE x]) --> mm[MEM]
  mm --> q
  q --> p[TEMP p]
  q --> c8[CONST 8]
  classDef hl fill:#fde68a,stroke:#b45309;
  class q hl;

Tree decomposition and greedy DAG matching¶

D1. Cut at $q$, so $T_q = $ ADD(p, 8) → addi r1, p, 8 (1). Then $T_{s1} = $ STORE(t_q, z) → r2 st z, 0(r1) (2), and $T_{s2} = $ MOVE(x, MEM(t_q)) → r17 ld r2, 0(r1) (2) + r1 mv x, r2 (1). Total 6.

D2. Cut at $m$: mul r1, a, b (3). Then add r2, r1, c, mv x, r2, add r3, r1, d, mv y, r3 (1 each). Total 7.

Greedy matching with LLVM's single-use rule gives the same result on both. $q$ and $m$ have two uses, so no pattern may swallow them, and every tree is then tiled greedily (munch finds the optimum on these small trees). A target that duplicates address arithmetic on purpose (§7) folds $q$ into both memory operands instead and gets 5 on D1.

NOLTIS¶

D1, first pass (tree DP, sharing ignored). The labels are $C(q, \mathsf{reg}) = 1$ (r9), $C(s1) = 2$ (r3 STORE(ADD(reg, CONST), reg), which covers $q$ and 8), $C(\mathsf{MEM}) = 2$ (r18, which also covers $q$), and $C(s2) = 3$ (r1). TopDownSelect chooses r3, r1 and r18. $q$ lies inside two tiles and is the root of none.

shared node	tiles containing it	$c(T_i)$	$c(T_i \setminus n)$	overlap $\omega$	CSE $\kappa = C(n, \mathsf{reg})$	decision
$q$ (D1)	r3 at s1; r18 at `MEM`	2; 2	r2: 2; r17: 2	0 + 0 = 0	1 (`addi`)	keep the overlap
$m$ (D2)	r13 at the first `ADD`; r13 at the second	3; 3	r8: 1; r8: 1	2 + 2 = 4	3 (`mul`)	fix $m$

D1. Recomputing $q$ inside the addressing modes is free, and sharing costs one addi. The second pass is not needed. The code is st z, 8(p) (2), ld r1, 8(p) (2), mv x, r1 (1). Total 5, which is optimum: the store and the load cost at least 2 each (every Tessera rule with a STORE or MEM root costs 2 or more), and the MOVE at least 1.
D2. Each madd recomputes the product, which costs 2 more than an add that reads it from a register, 4 in total. Computing $m$ once costs 3. So $m$ is fixed. In the second pass the ADDs can no longer use r13, and the result is mul (3) + 2 add + 2 mv. Total 7. The first pass alone would have produced two madds and two mvs, total 8.

PBQP and ILP formulations¶

PBQP on D2. The variables are $m$ ∈ {r12 (produces reg, cost 3), $h$ (the helper MUL(reg, reg) inside r13, cost 0)}, $a_1, a_2$ ∈ {r8 (cost 1, wants reg at position 1), r13 (cost 3, wants $h$ at position 1)}. The MOVEs and leaves have one choice each, which contributes a constant 2 (the two mv) plus 0. The edge matrices $M_{a_i m}$ are 0 on (r8, r12) and (r13, $h$) and $\infty$ elsewhere. The graph is the path $a_1 - m - a_2$.

step	rule	node removed	update	vectors after the step
1	R1	$a_1$	$c_m[\text{r12}] \mathrel{+}= \min(1 + 0,\ 3 + \infty) = 1$; $c_m[h] \mathrel{+}= \min(1 + \infty,\ 3 + 0) = 3$	$c_m = (4, 3)$
2	R1	$a_2$	same increments	$c_m = (5, 6)$
3	R0	$m$	choose r12	constant 5
4	back-propagate	$a_2$, $a_1$	given $m = $ r12, choose r8 (1 + 0)	—

Optimum: $5 + 2 = 7$, the same as NOLTIS. On D1 the same construction lets $q$ choose the shared helper d: ADD(reg, c) that both r3 and r18 use (Definition 21.3.1). Both parents are then satisfied by one choice, and PBQP finds 5.

ILP on D1. The variables include $y_{q,\text{r8}}$, $y_{q,\text{r9}}$, $y_{q,d}$ (the helper), $y_{s1,\text{r2}}$, $y_{s1,\text{r3}}$, $y_{M,\text{r17}}$, $y_{M,\text{r18}}$ and $y_{s2,\text{r1}}$, plus the leaves. Two of the constraints are $y_{s1,\text{r2}} + y_{s1,\text{r3}} \ge 1$ and $y_{M,\text{r17}} \le y_{q,\text{r8}} + y_{q,\text{r9}}$ (r17 needs reg at $q$, which r8 or r9 can produce). The minimum, 5, sets $y_{s1,\text{r3}} = y_{M,\text{r18}} = y_{s2,\text{r1}} = 1$ and uses no instance producing reg at $q$.

Try it

The drills stay on trees, where these methods coincide with the DP: ./course drill dp-tiling --seed 7 --difficulty hard --solution. To see LLVM's greedy DAG matcher decide between folding and sharing, run the boxes of §7 on your own IR.

4. Invariants and correctness¶

Tree decomposition and greedy DAG matching¶

Proposition 21.4.7 covers decomposition. For greedy DAG matching the invariant that matters is acyclicity. Folding a node $u$ into a tile rooted at $v$ turns the tile into one machine instruction. If some other path leads from $v$ back to $u$ (through a third node $x$ that uses $u$ and is used by $v$), the folded instruction would need its own result before it runs, which is a cycle. LLVM's IsLegalToFold rejects exactly this by searching for such a path (findNonImmUse). A fold that passes it keeps the selected graph a DAG, so a schedule exists. Without the check the selector would produce unschedulable code, which is why it is a correctness condition, not a heuristic.

NOLTIS¶

Proposition 21.4.10 gives validity and linear time. NOLTIS is not optimum. Theorem 21.4.4 says no polynomial algorithm is, unless P = NP. Its decisions are local: whether to fix $n$ is decided per node from costs computed in a pass that assumed all other shared nodes were duplicated. A pair of shared nodes whose best decisions depend on each other can mislead it. The 99.7 % figure is empirical [KG08].

PBQP and ILP formulations¶

Theorem 21.4.13 proves the reductions exact, and Definition 21.4.14 makes the ILP exact by construction. The PBQP formulation of Definition 21.4.11 forces one rule per node. A shared node that two parents want as different nonterminals (one reg, one inside a pattern that needs a different helper) cannot be both. Sharing identical helpers solves the common cases, and Ebner et al. add extra constraints for patterns with several roots [EBSKWK08]. When RN fires, optimality is lost. On SSA graphs of real programs most nodes reduce with R1/R2, which is why PBQP is close to optimal in practice.

5. Complexity¶

Variables: $\lvert V \rvert$ nodes, $\lvert E \rvert$ edges, $R$ rules, $p$ pattern size, $d$ the largest number of alternatives per PBQP variable, $\lvert N \rvert$ nonterminals.

Technique	Time (worst)	Time (typical)	Space	Justification
Tree decomposition	$O(\lvert V \rvert R p)$	linear	$O(\lvert V \rvert \lvert N \rvert)$	one tree DP per piece; the pieces partition $V$
Greedy DAG matching	$O(\lvert V \rvert R p \cdot \mathrm{fold})$, where the cycle check `findNonImmUse` may walk $O(\lvert V \rvert)$	near linear	$O(\lvert V \rvert)$	a pattern match per node plus a legality search per fold
NOLTIS	$O(\lvert V \rvert + \lvert E \rvert)$	linear	$O(\lvert V \rvert \lvert N \rvert)$	Proposition 21.4.10
PBQP (R0–R2 only)	$O(\lvert V \rvert d^3 + \lvert E \rvert d^2)$	near linear	$O(\lvert E \rvert d^2)$	R2 builds a $d \times d$ matrix, minimizing over $d$ for each entry
ILP / exact	exponential (Theorem 21.4.4)	seconds to minutes per function	$O(\lvert V \rvert R)$ variables	NP-hard

A pathological family for greedy matching's cycle check. A long chain $u \to x_1 \to \dots \to x_k \to v$ plus a direct edge $v \to u$ with a foldable $u$ makes findNonImmUse walk the whole chain for every attempted fold. SDNode::hasPredecessorHelper accepts a MaxSteps bound, but the fold check passes 0 (unbounded) and relies on topological node ids to prune the search (TopologicalPrune), so the walk stops at nodes that are topologically too early to reach the folded node.

A pathological family for decomposition's quality. A DAG in which one shared address $q$ is used by $k$ memory operations costs decomposition $1 + 2k$ (one addi plus $k$ accesses through a register) against $2k$ for folding $q$ everywhere. The absolute gap is 1. Make $q$ an expensive shared subtree that every user can fold for free, for example the address p + (i << 3) under a scaled addressing mode. Then decomposition pays the subtree once while the optimum pays nothing, and the ratio grows with the subtree's cost.

Real-world scale. Koes and Goldstein report that NOLTIS found the optimum in 99.7 % of their cases, where the optimum was computed with an ILP solver [KG08]. Ebner et al. report compile-time overheads for PBQP selection in LLVM that were acceptable for an optimizing compiler [EBSKWK08].

Tree decomposition and greedy DAG matching¶

Split only non-duplicable nodes. Treat loads, stores and calls as shared (never duplicated) but let arithmetic be recomputed. This is LLVM's practice for addressing modes (§7). It gets much of NOLTIS's benefit with no second pass.
DAG-optimal grammars. Ertl shows that for grammars with a certain structural property the bottom-up DP is already optimal on DAGs. He gives a check for the property, which lets a generator certify that a grammar can be used on DAGs [Ert99].
Rematerialize later. Keep the shared value in a register at selection time and let the register allocator recompute it if it would otherwise spill (Ch 22).

NOLTIS¶

Iterate the improvement. Recompute $\omega$ and $\kappa$ after the second pass and repeat. This can fix more nodes at the price of more passes. Koes and Goldstein found one improvement round sufficient [KG08].
Integrate with register pressure. Charge $\kappa(n)$ for the register a shared value occupies. This is closer to Aho–Johnson's register-bounded costs (Lesson 21.2).

PBQP and ILP formulations¶

SSA graphs across blocks [EKS03, EBSKWK08]: select for a whole function at once. Patterns may span blocks, which matters for DSPs with complex instructions.
Constraint programming, universal selection [Bli16]: add global code motion and block ordering to the model, at the price of solver time.
Superoptimization-style exact selection: Denali searches e-graphs of equivalent programs with a SAT solver for the shortest sequence [JNR02] (Lesson 21.7).

7. In real compilers¶

Tree decomposition and greedy DAG matching¶

LLVM's SelectionDAG matcher is greedy DAG matching. A load may be folded into its user only if SelectionDAGISel::IsProfitableToFold (by default N.hasOneUse()) and SelectionDAGISel::IsLegalToFold (the cycle check with findNonImmUse) agree, both in llvm/lib/CodeGen/SelectionDAG/SelectionDAGISel.cpp. Addressing modes are matched separately by target code (X86DAGToDAGISel::matchAddress and selectAddr in llvm/lib/Target/X86/X86ISelDAGToDAG.cpp), which deliberately duplicates shared address arithmetic (LLVM 23.1.2) [LLVM-SDISel, LLVM-X86ISelDAG]. lcc cuts DAGs into trees in undag (src/dag.c), assigning a temporary to every value with several uses unless the target sets wants_dag [LCC-Src].

LLVM folds a single-use load, but not a shared one

Reproduce (llc 23.1.2):

cat > share.ll <<'EOF'
define i64 @one_use(ptr %p, i64 %x) {
  %v = load i64, ptr %p, align 8
  %a = add i64 %v, %x
  ret i64 %a
}
define i64 @two_uses(ptr %p, i64 %x, i64 %y) {
  %v = load i64, ptr %p, align 8
  %a = add i64 %v, %x
  %b = mul i64 %v, %y
  %r = xor i64 %a, %b
  ret i64 %r
}
EOF
llc -O2 -mtriple=x86_64-linux-gnu share.ll -o - | grep -vE '^\s*\.|^#|^$|# -- '

Output (complete after the filter):

one_use:                                # @one_use
    movq    %rsi, %rax
    addq    (%rdi), %rax
    retq
two_uses:                               # @two_uses
    movq    (%rdi), %rax
    leaq    (%rsi,%rax), %rcx
    imulq   %rdx, %rax
    xorq    %rcx, %rax
    retq

What to notice: with one use, the load becomes the memory operand of addq (a tile covering load + add). With two uses, IsProfitableToFold refuses. Folding into both users would read memory twice, and folding into one would still need a separate load for the other. The load becomes its own tile, as in tree decomposition.

NOLTIS¶

NOLTIS itself was prototyped in LLVM by its authors but is not part of upstream LLVM. Its central decision, duplicate a shared node when that is cheaper than sharing it, is what LLVM's address-mode matchers do for shared address arithmetic: matchAddress folds a base+index·scale+offset computation into every memory operand that uses it, whatever its number of uses [LLVM-X86ISelDAG].

A shared address computation is duplicated into both addressing modes

Reproduce (llc 23.1.2):

cat > dup.ll <<'EOF'
define i64 @swap_in(ptr %p, i64 %i, i64 %z) {
  %q = getelementptr inbounds i64, ptr %p, i64 %i
  %v = load i64, ptr %q, align 8
  store i64 %z, ptr %q, align 8
  ret i64 %v
}
EOF
llc -O2 -mtriple=x86_64-linux-gnu -stop-after=finalize-isel dup.ll -o - | sed -n '/^body/,$p' | sed 's/[[:space:]]*$//'
llc -O2 -mtriple=aarch64-linux-gnu dup.ll -o - | grep -vE '^\s*\.|^#|^$|// -- '

Output (complete after the filters):

body:             |
  bb.0 (%ir-block.0):
    liveins: $rdi, $rsi, $rdx

    %2:gr64 = COPY $rdx
    %1:gr64_nosp = COPY $rsi
    %0:gr64 = COPY $rdi
    %3:gr64 = MOV64rm %0, 8, %1, 0, $noreg :: (load (s64) from %ir.q)
    MOV64mr %0, 8, %1, 0, $noreg, %2 :: (store (s64) into %ir.q)
    $rax = COPY %3
    RET 0, $rax
...
swap_in:                                // @swap_in
// %bb.0:
    mov x8, x0
    ldr x0, [x0, x1, lsl #3]
    str x2, [x8, x1, lsl #3]
    ret

What to notice: %q has two users, yet no instruction computes it. Both MOV64rm and MOV64mr carry the whole address %0 + 8·%1 in their operands, and on AArch64 both ldr and str use [base, index, lsl #3]. This is example D1: the overlap cost of the shared address is 0 (addressing modes are free), so recomputing it inside each memory tile beats computing it once, which is the choice NOLTIS makes with $\omega(q) = 0 < \kappa(q)$.

PBQP and ILP formulations¶

LLVM's PBQP solver is in llvm/include/llvm/CodeGen/PBQP/ (Graph.h, ReductionRules.h with applyR1, applyR2 and backpropagate). Upstream it serves the PBQP register allocator (llc -regalloc=pbqp, llvm/lib/CodeGen/RegAllocPBQP.cpp). Ebner et al.'s PBQP instruction selector used the same kind of solver in their LLVM prototype but was not merged (LLVM 23.1.2) [LLVM-PBQP, EBSKWK08].

The R1 reduction in LLVM's PBQP solver

Reproduce (LLVM source at tag llvmorg-23.1.2; needs network access to GitHub):

curl -sL https://raw.githubusercontent.com/llvm/llvm-project/llvmorg-23.1.2/llvm/include/llvm/CodeGen/PBQP/ReductionRules.h \
  | sed -n '/void applyR1(/,/^  }/p'

Output (complete):

  void applyR1(GraphT &G, typename GraphT::NodeId NId) {
    using NodeId = typename GraphT::NodeId;
    using EdgeId = typename GraphT::EdgeId;
    using Vector = typename GraphT::Vector;
    using Matrix = typename GraphT::Matrix;
    using RawVector = typename GraphT::RawVector;

    assert(G.getNodeDegree(NId) == 1 &&
           "R1 applied to node with degree != 1.");

    EdgeId EId = *G.adjEdgeIds(NId).begin();
    NodeId MId = G.getEdgeOtherNodeId(EId, NId);

    const Matrix &ECosts = G.getEdgeCosts(EId);
    const Vector &XCosts = G.getNodeCosts(NId);
    RawVector YCosts = G.getNodeCosts(MId);

    // Duplicate a little to avoid transposing matrices.
    if (NId == G.getEdgeNode1Id(EId)) {
      for (unsigned j = 0; j < YCosts.getLength(); ++j) {
        PBQPNum Min = ECosts[0][j] + XCosts[0];
        for (unsigned i = 1; i < XCosts.getLength(); ++i) {
          PBQPNum C = ECosts[i][j] + XCosts[i];
          if (C < Min)
            Min = C;
        }
        YCosts[j] += Min;
      }
    } else {
      for (unsigned i = 0; i < YCosts.getLength(); ++i) {
        PBQPNum Min = ECosts[i][0] + XCosts[0];
        for (unsigned j = 1; j < XCosts.getLength(); ++j) {
          PBQPNum C = ECosts[i][j] + XCosts[j];
          if (C < Min)
            Min = C;
        }
        YCosts[i] += Min;
      }
    }
    G.setNodeCosts(MId, YCosts);
    G.disconnectEdge(EId, MId);
  }

What to notice: this is step 1 of the D2 trace, line for line. For every choice j of the neighbor, add $\min_i$ (node cost + edge cost) to the neighbor's vector, then disconnect the degree-1 node. The proof of Theorem 21.4.13 is the comment "the reduced instance's objective equals the inner minimization", and this loop computes that inner minimization.

8. Comparison¶

Technique	Power / precision	Speed (asymptotic · practical)	Output / error quality	Implementation effort	Typical use
Tree decomposition and greedy DAG matching	optimum only among covers that never duplicate (Proposition 21.4.7); greedy folds follow fixed rules	linear · the default in production	D1: 6, D2: 7 (optimum 5 and 7)	low: reuse the tree selector; fold legality checks	LLVM SelectionDAG (single-use fold + address-mode duplication), lcc (`undag`), the Dragon book
NOLTIS	near-optimal: optimum on 99.7 % of cases [KG08]; D1: 5, D2: 7	linear, two DP passes	usually optimal; local decisions can mislead it	moderate: DP twice plus overlap/CSE costs	research prototype in LLVM; the idea is in address-mode duplication
PBQP and ILP formulations	PBQP optimum when R0–R2 suffice (Theorem 21.4.13); ILP always optimum	PBQP near linear with RN; ILP exponential	best available; PBQP degrades gracefully	high: formulation, solver, DAG-pattern constraints	DSP compilers, research (Ebner et al. in LLVM), universal selection with CP

Choose tree decomposition or greedy matching when compile time matters and your costs make recomputation rarely worthwhile, except for addressing modes, which you special-case.
Choose NOLTIS when you have a tree DP already and want most of the DAG benefit at linear cost.
Choose PBQP or ILP when instructions are irregular (DSPs, SIMD with odd constraints), code quality justifies solver time, or you need a baseline to measure heuristics against.

9. Assessment¶

Technique	Quiz ids (`solutions/quizzes/ch21.yaml`)	Drill	Flashcard tag	Exercises
Tree decomposition and greedy DAG matching	`dag-decomposition-cost`, `dag-np-complete`	none: DAG covering is NP-complete in general, and small instances are better done in the quiz with the lesson's D1/D2	`dag-decomposition`	—
NOLTIS	`noltis-fix`, `noltis-overlap`	none (as above); the per-tree DP inside it is `./course drill dp-tiling`	`noltis`	—
PBQP and ILP formulations	`pbqp-r1`, `pbqp-optimal-when`	none: reductions are quizzed on a fixed instance	`pbqp-ilp`	—

Charging a shared value twice

Running the tree DP on a DAG and adding the labels of a shared child into each parent counts its cost once per parent. The DP then prefers duplication even when sharing is cheaper, because sharing looks twice as expensive as it is. In the DAG cost model (Definition 21.4.2) an instance is paid once, however many tiles read its register. NOLTIS's second pass reads a fixed node's label as 0 for exactly this reason.

References¶

See the chapter references.

shared node	tiles containing it	\(c(T_i)\)	\(c(T_i \setminus n)\)	overlap \(\omega\)	CSE \(\kappa = C(n, \mathsf{reg})\)	decision
\(q\) (D1)	r3 at s1; r18 at `MEM`	2; 2	r2: 2; r17: 2	0 + 0 = 0	1 (`addi`)	keep the overlap
\(m\) (D2)	r13 at the first `ADD`; r13 at the second	3; 3	r8: 1; r8: 1	2 + 2 = 4	3 (`mul`)	fix \(m\)

step	rule	node removed	update	vectors after the step
1	R1	\(a_1\)	\(c_m[\text{r12}] \mathrel{+}= \min(1 + 0,\ 3 + \infty) = 1\); \(c_m[h] \mathrel{+}= \min(1 + \infty,\ 3 + 0) = 3\)	\(c_m = (4, 3)\)
2	R1	\(a_2\)	same increments	\(c_m = (5, 6)\)
3	R0	\(m\)	choose r12	constant 5
4	back-propagate	\(a_2\), \(a_1\)	given $m = $ r12, choose r8 (1 + 0)	—

Technique	Time (worst)	Time (typical)	Space	Justification
Tree decomposition	\(O(\lvert V \rvert R p)\)	linear	\(O(\lvert V \rvert \lvert N \rvert)\)	one tree DP per piece; the pieces partition \(V\)
Greedy DAG matching	\(O(\lvert V \rvert R p \cdot \mathrm{fold})\), where the cycle check `findNonImmUse` may walk \(O(\lvert V \rvert)\)	near linear	\(O(\lvert V \rvert)\)	a pattern match per node plus a legality search per fold
NOLTIS	\(O(\lvert V \rvert + \lvert E \rvert)\)	linear	\(O(\lvert V \rvert \lvert N \rvert)\)	Proposition 21.4.10
PBQP (R0–R2 only)	\(O(\lvert V \rvert d^3 + \lvert E \rvert d^2)\)	near linear	\(O(\lvert E \rvert d^2)\)	R2 builds a \(d \times d\) matrix, minimizing over \(d\) for each entry
ILP / exact	exponential (Theorem 21.4.4)	seconds to minutes per function	\(O(\lvert V \rvert R)\) variables	NP-hard

Lesson 21.4 — Beyond trees: DAG covering, NP-completeness and near-optimal selection¶

1. Problem and motivation¶

Tree decomposition and greedy DAG matching¶

NOLTIS¶

PBQP and ILP formulations¶

2. Definitions and algorithms¶

Tree decomposition and greedy DAG matching¶

NOLTIS¶

PBQP and ILP formulations¶

3. Worked example¶

Tree decomposition and greedy DAG matching¶

NOLTIS¶

PBQP and ILP formulations¶

4. Invariants and correctness¶

Tree decomposition and greedy DAG matching¶

NOLTIS¶

PBQP and ILP formulations¶

5. Complexity¶

6. Variants and refinements¶

Tree decomposition and greedy DAG matching¶

NOLTIS¶

PBQP and ILP formulations¶

7. In real compilers¶

Tree decomposition and greedy DAG matching¶

NOLTIS¶

PBQP and ILP formulations¶

8. Comparison¶

9. Assessment¶

References¶