MAXIMAL MUNCH tile the IR tree with the biggest instruction that fits
The back-end’s first job: turn an IR tree into machine instructions. Each instruction is a tile that covers a sub-tree; maximal munch walks the tree top-down and, at every node, greedily takes the largest tile that matches, then recurses on the tile’s leaf operands. One CISC addressing-mode tile can swallow a load, an add and a multiply at once — three naive instructions become one.
THE TECHNIQUE greedy largest tile, top-down
The address computation load(base + idx*4) is a 3-operator tree. A simple ISA emits one instruction per operator (3); a CISC mov r,[base+idx*4] tile covers all three at once. Toggle the tile set and watch the instruction count collapse: live demo
HISTORY & CREDIT tree pattern matching; Cattell 1980
“Maximal munch is optimal.” — no. Greedy largest-tile is fast and usually good but not optimal; the global optimum needs dynamic programming or bottom-up rewriting (twig / BURS). Maximal munch trades optimality for a single linear pass. cited
1970s · Glanville & Graham (1978) — a table-driven, parsing-style approach to instruction selection. 1980 · R. G. G. Cattell — PhD “Automatic Derivation of Code Generators from Machine Descriptions”: instruction selection as tree pattern matching, the maximal-munch lineage. 1988 · Pelegri-Llopart & Graham — “Optimal Code Generation for Expression Trees: An Application of BURS Theory” (POPL): BURS (bottom-up rewrite), optimum covers. 1989 · Aho, Ganapathi & Tjiang — “twig” (TOPLAS): top-down tree pattern matching + dynamic programming, also optimum. Two distinct optimum-tiling frameworks — not the same technique.
Greedy munch is locally optimal (no two adjacent tiles merge into a cheaper one) but not the global optimum that DP/BURS reach. “Maximal munch” also names the longest-match rule in lexers (grab the longest valid token) — the same greedy idea in a different phase; do not conflate the two uses. Cattell 1980 / Glanville-Graham 1978
RECOMMEND FOR I-13 the tile count, computed
The instruction counts — naive one-per-node vs one addressing tile — run on the canonical compiler:
$ i13 run munch.i13 # load(add(base, mul(idx,4))): count operators, then apply one tile
naive = 3 -- load, add, mul as three instructions
tile_covers = 3 tiles = 1
munched = 1 -- one address-mode tile: naive - (covers-1)*tiles = 3 - 2 = 1
Recommend: instruction selection by maximal munch is LIT in its counting — verified on the canonical compiler that the 3-operator address tree costs 3 naive instructions and 1 under a single address-mode tile. For an I-13 back-end the tree is already there (the lowered IVM op array is close to a tile stream), and munch is the simplest selector to write: one top-down pass, largest match wins. When optimality matters, the same tree takes a BURS DP instead — the honest upgrade. Opens the back-end (batch 26); feeds register allocation (159, 161).