Maximal Munch and Dynamic-Programming Tiling

Consider a target with a three-operand add, a two-operand add, and an instruction that computes base + index*scale for a small set of scale factors. The expression (a + b) + (c + d) can be covered in several ways: two three-operand adds, four two-operand adds, or a mix. A selector that always takes the largest pattern available at the root will pick the three-operand add at the top, then recursively cover a+b and c+d, and produce two instructions. That happens to be optimal.

Change the machine so that the three-operand add requires its first operand in a register already, and the picture shifts. The same rule applied to a tree where the largest pattern at the root is a fused multiply-add may consume an operand that was needed twice, forcing a copy that the alternative cover would have avoided. Greedy matching has no way to see this, because it commits to the root before examining the subtrees.

The Greedy Rule and Where It Fails

The pattern set itself, and the legality checks that go with it, are described in Instruction Selection as Tree Tiling; this article is about how a set of patterns is searched. Maximal munch, as described in the Dragon Book, is: at each node, find the largest pattern that matches, emit it, and recurse on the unmatched children. The rule is attractive because it is linear in the size of the tree for fixed-size patterns, it needs no cost model beyond “bigger is better”, and it is easy to implement with a bottom-up rewrite system in which each pattern carries a state transition.

The failure mode is not rare. Maximal munch optimizes the root of each subtree in isolation, and the cost of a subtree’s cover is not always minimized by minimizing its root’s pattern. A large pattern at the root may force its operands into a specific register class, and satisfying that class may require a copy from a value that another use also reads. The copy is not part of the pattern’s nominal cost, so the greedy choice looks cheap and is not.

The canonical counterexample in the literature is a machine where a load can fold an address computation, and where the address computation’s result is also used as a value. Folding the address into the load saves an instruction for the load’s use but requires the address in a register for the other use, so the fold is neutral at best and loses if the other use is in a hotter path. The pattern matcher sees one tree; the decision depends on the whole function.

Greedy matching also interacts badly with constants. If the largest pattern at a node accepts an immediate, greedy will fold the constant into it. If the same constant appears in several places, the folded form may force each occurrence to be materialized separately where a single register holding the constant would have served all of them. This is the constant-pooling question, and it is decided globally, not per tree. The same fold appears from the other direction in Folding Address Computation into Memory Operands, where a large pattern is desirable precisely because it absorbs an address calculation.

The Dynamic-Programming Formulation

The optimal algorithm treats the tree as a set of subproblems. For each node n, compute the cheapest cover of the subtree rooted at n and record which pattern achieved it. The recurrence is:

cost(n) = min over patterns p matching at n of
            cost(p) + sum over children c of p that are internal nodes
                       of cost(c)

where cost(p) is the pattern’s own cost — one instruction, one cycle, one bundle slot — and the children of p that are leaves of the input tree contribute nothing. Because the subtrees of a tree are disjoint and there is no sharing, each node is solved once and its answer is reused by every pattern that could sit above it.

The result is a table indexed by node, holding the winning pattern and its cost. A second pass walks the table top-down and emits the instructions. The algorithm is optimal with respect to the cost model, which is a weaker statement than it sounds: it is optimal given the pattern set and the prices, and it is not optimal with respect to the final code, because the cost model does not know about register pressure, scheduling, or cache behaviour.

Complexity is linear in the tree size for a fixed pattern set. Each node is visited once and tested against every pattern that could match at it; if the pattern set has P patterns and each has bounded arity, the work per node is O(P) and the total is O(nP). In practice the per-node pattern test is organized as a table lookup on the node’s operator, so only patterns for that operator are considered, and P becomes a small constant per operator.

A minimal implementation makes the recurrence explicit:

/* Best cover of the subtree at node n, memoized in cost[] and rule[]. */
int tile(int n) {
    if (cost[n] >= 0) return cost[n];
    int best = INF, best_rule = -1;
    for (int r = first_rule[op[n]]; r >= 0; r = next_rule[r]) {
        int c = rule_cost[r];
        for (int k = 0; k < rule_arity[r]; k++) {
            int child = child_node(n, k);      /* -1 if rule leaf matches input leaf */
            if (child >= 0) c += tile(child);  /* recurse only into internal nodes */
        }
        if (c < best) { best = c; best_rule = r; }
    }
    cost[n] = best;
    rule[n] = best_rule;
    return best;
}

The recursion terminates because children are strictly deeper than their parent, and the memo table makes the cost linear rather than exponential in depth. Without memoization the same subtree would be re-solved once per enclosing pattern, which for a chain of n nodes is exponential in the worst case.

Cost Vectors and Tie-Breaking

A scalar cost is an oversimplification that shows up immediately on real machines. The usual fix is a small vector, compared lexicographically: instruction count first, then an estimate of execution cycles, then code size. Lexicographic comparison is not the same as a weighted sum, and the difference matters. With a weighted sum, a pattern that saves one instruction but adds three cycles can win if the weights are set that way. With lexicographic order, no amount of cycle savings can compensate for one extra instruction, which is the right rule for a target where fetch bandwidth dominates and the wrong rule for a latency-bound inner loop.

Some generators allow the cost to depend on context: the same pattern priced differently when its result feeds a branch, or when its operand is a constant, or when the pattern is the last use of a value. Context-sensitive cost turns the tree DP into something closer to a grammar problem, because the state at a node now includes what its parent expects. The standard technique is to split each nonterminal by the register class it must produce, which multiplies the table size by the number of classes and restores the simple recurrence at the cost of more states.

Ties are common and must be broken deterministically, or the compiler produces different code for the same input depending on hash iteration order. The usual rule is lowest pattern index, which makes the machine description’s ordering significant and therefore a thing maintainers must be careful about. A description that lists the general pattern before the specialized one will silently prefer the general one whenever the costs tie.

Bottom-Up Rewriting and the Generator

Writing a selector by hand for each target does not scale, so the pattern set is compiled into a matcher. The classical construction is a bottom-up rewrite system: each pattern is converted into a set of state transitions of the form “in state s, seeing operator op with children in states s1..sk, reduce to state s' with cost c”. The resulting matcher walks the tree once, maintaining a stack of states, and performs reductions when a pattern completes. The table is built offline, so matching at compile time is a table lookup rather than a tree walk.

The important property of this construction is that it computes the same optimum as the explicit DP while using a stack machine rather than a memo table. It also compresses well: states that behave identically for every operator can be merged, and the merged machine is much smaller than the naive table, which is what makes the technique practical to embed in a compiler.

The limitation of the pure bottom-up approach is that it commits to reductions as it goes. Patterns that span a node and its parent’s sibling, or that depend on facts outside the tree — an immediate that fits only because a preceding comparison guarantees a range — cannot be expressed. Those cases fall back to hand-written selection code, and in every production compiler the machine description is supplemented by target-specific C++ that pattern languages cannot express. The fraction of instructions covered declaratively is a decent measure of how regular the target is.

Choosing Between Them

Maximal munch remains in use because it is small, predictable, and fast, and because on regular RISC targets with a good pattern set its mistakes are rare and small. Dynamic programming costs more compile time and more generator machinery, and buys provable optimality against a cost model that is itself approximate.

The honest comparison is not optimal versus suboptimal. It is which approximation is cheaper to maintain. A DP selector with a bad cost model produces confidently wrong choices, and because the choice is made by an algorithm rather than by a rule a maintainer can read, the bad choices are harder to diagnose. A greedy selector with the same bad cost model produces the same wrong choices but at least they follow a rule that can be inspected. Both are then repaired by the passes that follow, which is why the difference between the two algorithms matters less in a full pipeline than it does in isolation.