Lesson 21.8 — Describing targets: TableGen, GCC machine descriptions and tree grammars¶

Techniques: LLVM TableGen; GCC machine descriptions; tree-grammar and architecture-description files (lburg/iburg, HotSpot ADL) · Prerequisites: Lessons 21.1–21.5 · Time: 3–4 hours

A retargetable compiler keeps everything it knows about a machine in data: instructions and their encodings, the patterns they implement, registers and register classes, calling conventions and scheduling models. It generates the matching code from that data. The three families differ in what the data is. TableGen is a general record language from which LLVM's back ends generate matcher tables, encoders, register information and calling-convention code. GCC machine descriptions are Lisp-like RTL templates, compiled by the gen* programs into a recognizer (recog), an emitter and a splitter. Tree grammars (lburg, iburg, HotSpot's .ad files) describe instructions directly as the rules of Lesson 21.1. All three answer the same questions. This lesson shows how each one describes Tessera-like instructions and what the generator checks along the way.

1. Problem and motivation¶

The input is a description of a target machine written by a back-end author. The output is generated compiler code: selectors, encoders and register tables, correct by construction as far as the generator can check. Machine descriptions go back to the retargetable compilers of the 1970s and 1980s: Cattell's derivation of code generators from machine descriptions [Cat80], Graham–Glanville grammars [GG78], and the RTL descriptions of Davidson and Fraser's PO, which GCC adopted [DF80]. The problem they solve is scale. x86 alone has thousands of instruction forms, and without generation every selector, assembler and disassembler would repeat the same facts by hand.

LLVM TableGen¶

TableGen is a declarative language of classes and records with inheritance, template arguments, let overrides, multiclasses and a small functional expression language. It has no built-in meaning: separate back ends of the llvm-tblgen program interpret the records, for example -gen-dag-isel (the SelectionDAG matcher table), -gen-global-isel, -gen-instr-info, -gen-register-info, -gen-callingconv, -gen-asm-writer and -gen-emitter [LLVM-TableGenRef, Col25, Ch. 6].

GCC machine descriptions¶

A GCC .md file lists define_insn entries. Each is an RTL template with operand predicates and constraints (register classes and addressing forms per alternative), a condition, and an output template. define_expand entries generate RTL for named operations during expansion, and define_split/define_peephole2 entries rewrite sequences. genrecog compiles all templates into recog, a decision tree that recognizes whether an RTL expression is a valid instruction. combine uses exactly this recognizer (Lesson 21.1 §7) [GCC-MD].

Tree-grammar and ADL descriptions¶

Tree-grammar generators take the grammar of Lesson 21.1 directly: lcc's .md files for lburg (reg: ADDI4(reg, mrc) "?movl %0,%c\naddl %1,%c\n" 1), iburg's .brg files [FH95, Ch. 14], and HotSpot's ADL (.ad, "architecture description language") with instruct blocks that give a match rule, a cost, an encoding and a pipeline class [HS-ADLC].

2. Definitions and algorithms¶

LLVM TableGen¶

Definition 21.8.1 (TableGen classes, records and elaboration)

A class $C\langle a_1{:}\tau_1, \dots, a_k{:}\tau_k \rangle$ has template arguments and an ordered list of typed fields with initial values that may refer to the arguments. A record (def R : C_1<\dots>, \dots, C_m<\dots> \{ body \}) is elaborated as follows [LLVM-TableGenRef, §let]: (1) for each parent class in order, bind its template arguments and add its fields (later parents override earlier ones); (2) apply the record body's lets and field definitions; (3) apply the bindings of every enclosing top-level let … in, which override inherited fields but not fields defined in the record body; (4) resolve every reference (to fields, other records, ! operators) until no unresolved reference remains. A multiclass is a template for several records. defm N : M<\dots> instantiates it, prefixing each record name with N.

Definition 21.8.2 (Pattern and pattern typing)

An instruction's pattern is a DAG over selection operators (add, ld, st, target nodes) with typed leaves (GPR:$s, imm:$c). Each operator's type profile constrains its operands and results (SDTCisSameAs<0, 1>: result 0 and operand 1 have the same type; SDTCisInt<0>). Pattern typing assigns to each node a set of machine value types $T(v) \subseteq \mathrm{MVT}$ (one set per hardware mode) consistent with all profiles and leaves. A pattern is well typed if every set is non-empty. It is fully typed if every set has exactly one element.

Algorithm 21.8.3 (Pattern type inference by constraint propagation)

Input: a pattern; the type profiles of its operators; the register classes and operand types of its leaves.
Output: type sets $T(v)$ for every node, or a "type contradiction" error.
Precondition: the sets of all MVTs are finite.
Postcondition: $T$ is the largest assignment of subsets such that every constraint is locally consistent (Proposition 21.8.4). An empty set means no typing exists.
Invariant: every concrete typing of the pattern that satisfies the constraints assigns each node a type in its current set.

function InferTypes(P):
    for each node v: T(v) ← the target's legal types, or the leaf's register-class types / operand type
    repeat:
        changed ← false
        for each node v and each constraint k of v's profile:
            T' ← Restrict(k, T)              # e.g. SameAs(a, b): T(a), T(b) ← T(a) ∩ T(b);
                                             #      IsInt(a):    T(a) ← T(a) ∩ integers
            if T' ≠ T: T ← T'; changed ← true
            if some T(u) = ∅: report "type contradiction at u"; stop
    until not changed

Proposition 21.8.4 (Type inference terminates and is exact for local constraints)

Algorithm 21.8.3 terminates after at most $\sum_v \lvert T_0(v) \rvert$ changes. Its result contains every typing that satisfies all constraints (soundness of the invariant). If it reports a contradiction, the pattern has no typing.

Proof

Each Restrict only intersects sets, so every change removes at least one type from some $T(v)$. The sum of the set sizes is a non-negative integer that strictly decreases with every change, which bounds the number of changes by its initial value. Invariant: initially every typing's types are in the sets, because the initial sets are all legal types or exactly what the leaves allow. Restrict removes a type from $T(v)$ only if no choice from the other nodes' sets satisfies constraint $k$ with it. By the invariant those sets contain every consistent typing's types, so the removed type occurs in no consistent typing. The invariant is maintained. Contradiction: an empty set means no typing assigns that node a type, so no typing exists. Exactness is local: arc consistency may leave sets with more than one element even when only one global typing works. TableGen then reports that the pattern is not fully typed and asks for an explicit type annotation.

GCC machine descriptions¶

Definition 21.8.5 (define_insn, constraints, alternatives)

A define_insn is a tuple (name, RTL template, condition, output template, attributes). The RTL template contains match_operand:M n "predicate" "constraints", which matches any operand of mode M satisfying the predicate function. The constraint string lists comma-separated alternatives ("=r,m" for operand 0 with "rm,r" for operand 1: register ← register-or-memory, or memory ← register). The instruction is recognized for an RTL expression if the template matches and the condition holds. Register allocation later picks one alternative per instruction.

Algorithm 21.8.6 (genrecog: from templates to a decision tree)

Input: all define_insn templates in file order (their index is the insn code).
Output: C code for recog(x), which returns the insn code of the first template in file order that matches $x$ and whose condition holds, or −1.
Precondition: templates are well formed and the predicates are pure functions.
Postcondition: recog behaves as sequential matching in file order (Proposition 21.8.7).
Invariant: each decision-tree node tests one position of the RTL (code, mode, vector length, or a predicate), and each leaf holds the templates consistent with all tests on its path, in file order.

function GenRecog(templates):
    root ← BuildTree(templates, positions = [the whole rtx])
    emit C code that walks the tree, calls predicates and conditions, and returns codes

function BuildTree(S, positions):
    if S is empty: return Fail
    choose a position p and a test (GET_CODE, GET_MODE, XVECLEN, ...) that distinguishes S
    for each outcome o of the test:
        child[o] ← BuildTree({ s ∈ S | s is consistent with outcome o at p }, next positions)
    # at a leaf: try the remaining templates' predicates/conditions in file order
    return node(p, test, child)

Proposition 21.8.7 (recog is first-match in file order)

For every RTL expression $x$, the code recog(x) returns the smallest insn code $i$ such that template $i$ matches $x$ and its condition holds, or −1 if none does.

Proof

By induction on the tree. A template $s$ that matches $x$ is consistent with the outcome of every test at $x$'s positions, so it reaches the leaf that $x$ reaches. A template that does not match fails some test on that path or some predicate or condition at the leaf. At the leaf, the remaining templates are tried in file order, and the first success is returned. Since every matching template is among them, the result is the smallest matching code.

Tree-grammar and ADL descriptions¶

Definition 21.8.8 (lburg rule and ADL instruct)

An lburg rule is nonterm: tree template [cost], where the cost is a constant or a C expression (a dynamic cost, Definition 21.2.10), and the template is the assembly text with %0, %1, … for the kids and %c for the result register. A leading ? marks a template whose first instruction can be omitted if source and destination registers coincide. An ADL instruct declares operands (typed by operand classes such as rRegL, memory, immL32), a match expression over C2's ideal nodes, an optional predicate, an ins_cost, an ins_encode block and an ins_pipe class. Operand classes are themselves defined by operand blocks with match and op_cost, which makes them the grammar's nonterminals.

Algorithm 21.8.9 (From a grammar description to a labeler)

Input: an lburg .md, iburg .brg or ADL .ad file.
Output: a labeler (Algorithm 21.2.11) plus a reducer or emitter per rule.
Precondition: chain rules have constant costs (lburg); every nonterminal used as a leaf has at least one rule.
Postcondition: the generated labeler computes the DP labels of Lesson 21.2 for the grammar the file denotes.
Invariant: each rule appears once in the generated _label (in its root operator's case) and once in the tables that map rule numbers to templates and kid patterns.

function GenerateFromGrammar(file):
    G ← parse the rules; number them in file order
    check: every nonterminal has a rule; the start symbol derives something; chain rules
           have constant costs
    emit the configuration section and the state record (Algorithm 21.2.11)
    emit _label with one case per operator, one guarded cost computation per rule
    emit _rule(state, goal), _kids(node, rule, kids[]) and the template string table
    (ADLC additionally emits operand classes, encodings and pipeline data)

3. Worked example¶

The same three Tessera instructions in each description.

LLVM TableGen¶

ADD, ADDI and SHADD are the TInst records of Tessera.td (Lesson 21.1 §7). Elaborating def SHADD : TInst<(outs GPR:$d), (ins GPR:$s, GPR:$t, simm64:$k), "shadd $d, $s, $t, $k", [(set GPR:$d, (add GPR:$s, (shl GPR:$t, imm:$k)))]>:

step (Definition 21.8.1)	fields after the step
(1) inherit `Instruction` (from `Target.td`), then `TInst`	the `Instruction` defaults (`Namespace = ""`, `Size = 0`, `isCommutable = 0`, …), then `Namespace = "Tessera"`, `OutOperandList`, `InOperandList`, `AsmString`, `Pattern` from the template arguments, `Size = 4`
(2) record body	empty
(3) enclosing `let`	none
(4) resolve	template arguments substituted

Type inference on its pattern (Algorithm 21.8.3), one hardware mode. TableGen starts every unconstrained node at the target's legal types (the types of its register classes), which for Tessera is just i64:

node	initial $T$	after `GPR` leaves	after `add`: SameAs(0,1), SameAs(0,2)	after `shl`: SameAs(0,1), IsInt	final
`$s`	{i64} (GPR)	{i64}	{i64}	{i64}	i64
`$t`	{i64}	{i64}	{i64}	{i64}	i64
`shl`	legal types	legal types	∩ {i64} = {i64} (as operand 2 of `add`, `SDTIntBinOp`)	{i64} (`SameAs<0, 1>` with `$t`)	i64
`$k` (`imm`)	integer types ∩ legal types =	{i64}	{i64}	`SDTIntShiftOp` only requires `IsInt<2>`: still	i64
`add`	legal types	legal types	{i64}	{i64}	i64

The pattern is fully typed. For contrast, bad.td in §7 makes add's operands a GPR (i64) and an FPR (f32). SameAs then intersects {i64} with {f32}, and the set becomes empty: "Type set is empty".

GCC machine descriptions¶

On x86-64, movq 24(%rdx), %rax; movq %rax, (%rdi,%rsi,8) are both recognized as *movdi_internal (insn code 82 in GCC 13.3), alternatives 3 and 5 (§7). Alternative 3 has constraints "r" ← "rem" (a register from a register, immediate or memory), and alternative 5 has "m" ← "re". The template's condition !(MEM_P (operands[0]) && MEM_P (operands[1])) is exactly why the memory-to-memory movm of the running example does not exist on x86, and why combine failed on "8 → 9" in Lesson 21.1.

Tree-grammar and ADL descriptions¶

In lcc's x86 description the addressing modes are nonterminals (base, index, addr), so the address a + i*8 of the running example is derived as addr: ADDI4(index, reg) with index: LSHI4(reg, con3), the tree-grammar analogue of TableGen's ComplexPattern. In HotSpot's ADL the same role is played by operand classes such as indIndexScaleOffset (base + index·scale + offset), which appear as the memory operand of instructs like addL_rReg_mem (Lesson 21.2 §7).

Try it

Write Tessera.td from Lesson 21.1 yourself, add SUB, SLLI and a MUL by a register, and check with llvm-tblgen -gen-dag-isel that the complexities come out as you expect (3 per node). Then introduce a type error on purpose and read the diagnostic.

4. Invariants and correctness¶

LLVM TableGen¶

Proposition 21.8.4 guarantees that type inference terminates and that its contradictions are real. What TableGen does not check is semantic correctness: a pattern (set GPR:$d, (sub GPR:$s, GPR:$t)) attached to an add instruction type-checks perfectly. Elaboration (Definition 21.8.1) is deterministic but order-sensitive: which of two parents' fields wins, and whether a top-level let applies, follow fixed rules that surprise newcomers. The -print-records box in §7 shows a top-level let overriding an inherited field.

GCC machine descriptions¶

Proposition 21.8.7: file order is semantics. Moving a more general define_insn above a special one silently changes which instruction is recognized, since insn codes are assigned in file order. Constraints must agree with the predicates. A template whose predicate accepts memory but whose constraints offer no memory alternative is a latent register-allocation failure ("impossible constraint").

Tree-grammar and ADL descriptions¶

The generators check reachability (every nonterminal derives something, every leaf nonterminal has rules) and, for lburg, that chain costs are constant. Neither checks that a template implements its pattern. Totality (every IR tree has a cover) is not checked either, so a missing rule shows up as "no cover" at compile time, like LLVM's "Cannot select".

5. Complexity¶

Variables: $r$ records or rules in the description, $t$ the total size of patterns, $M$ the number of machine value types.

Technique	Generation time	Size of generated code	Compile-time cost of the result	Justification
LLVM TableGen	elaboration $O(r \cdot \text{fields})$; type inference $O(t \cdot M)$ per pattern (Proposition 21.8.4); matcher construction $O(r \log r)$ for sorting plus factoring	x86: 27,595 patterns, a 627 KB matcher table (Lesson 21.5 §7)	see Lesson 21.5	set sizes bound the propagation steps
GCC machine descriptions	decision-tree construction, near linear in the templates with factoring	`insn-recog.cc` of hundreds of thousands of lines for i386	`recog` walks one tree path plus predicates	Proposition 21.8.7
Tree grammars and ADL	linear in the rules (Algorithm 21.8.9)	lcc's x86: 7048 lines of C generated from `x86linux.md`	the DP of Lesson 21.2	one guarded block per rule

A pathological family for TableGen's type inference. A pattern with $n$ nested polymorphic operators (add of add of … of a leaf with unconstrained type) starts with $M$ types per node, and each propagation round may remove only one type from one node. So $\Theta(n M)$ changes can be needed, each costing a pass over the pattern. TableGen's hardware-mode sets multiply this by the number of modes.

Real-world scale. The i386 .md of GCC 15 is 30,221 lines. LLVM's x86 target has 65 .td files, and generating its DAG matcher takes about 10 seconds with a release llvm-tblgen on the course container.

LLVM TableGen¶

Multiclasses and foreach: generate instruction families (rr, ri, rm, mr) from one description. Less text, more indirection when reading.
HwModes: one pattern set for several register widths (RISC-V RV32/RV64). Type sets become per-mode vectors.
GlobalISel import (-gen-global-isel): reuses SelectionDAG patterns for GlobalISel, skipping those that use features it cannot import (Lesson 21.6).

GCC machine descriptions¶

Iterators (<mode>, SWI48): expand one template for many modes, GCC's analogue of multiclasses.
define_insn_and_split: recognize a pseudo-instruction early and split it after register allocation. This keeps early passes simple and late code precise.

Tree-grammar and ADL descriptions¶

Dynamic costs and predicates (lburg range, memop; ADL predicate): express immediate ranges and same-address conditions. The DP must evaluate them at compile time (Lesson 21.2).
ISLE as a description language (Lesson 21.7): typed rewrite rules with extractors instead of grammar rules.

7. In real compilers¶

LLVM TableGen¶

The language is implemented in llvm/lib/TableGen/ (TGParser.cpp, Record.cpp). Pattern typing is TreePatternNode::ApplyTypeConstraints and the type-set machinery in llvm/utils/TableGen/Common/CodeGenDAGPatterns.cpp. The x86 description lives in llvm/lib/Target/X86/*.td, for example X86InstrArithmetic.td and X86CallingConv.td (LLVM 23.1.2) [LLVM-TableGenRef, LLVM-DAGISelEmitter].

Record elaboration and a type contradiction, from llvm-tblgen itself

Reproduce (llvm-tblgen 23.1.2):

cat > records.td <<'EOF'
class Inst<string mnemonic, int cost> {
  string Mnemonic = mnemonic;
  int Cost = cost;
  bit HasImm = 0;
}
multiclass ALU<string name, int cost> {
  def rr : Inst<name, cost>;
  def ri : Inst<name # "i", cost> { let HasImm = 1; }
}
defm ADD : ALU<"add", 1>;
let Cost = 3 in
defm MUL : ALU<"mul", 0>;
EOF
llvm-tblgen -print-records records.td
cat > bad.td <<'EOF'
include "llvm/Target/Target.td"
def R0 : Register<"r0">; def F0 : Register<"f0">;
def GPR : RegisterClass<"T", [i64], 64, (add R0)>;
def FPR : RegisterClass<"T", [f32], 32, (add F0)>;
def BADADD : Instruction {
  let OutOperandList = (outs GPR:$d); let InOperandList = (ins GPR:$s, FPR:$t);
  let AsmString = "add $d, $s, $t";
  let Pattern = [(set GPR:$d, (add GPR:$s, FPR:$t))];
}
def TII : InstrInfo; def T : Target { let InstructionSet = TII; }
EOF
llvm-tblgen -gen-dag-isel -I "$(llvm-config --includedir)" bad.td -o /dev/null 2>&1 | head -3

Output (complete):

------------- Classes -----------------
class Inst<string Inst:mnemonic = ?, int Inst:cost = ?> {
  string Mnemonic = Inst:mnemonic;
  int Cost = Inst:cost;
  bit HasImm = 0;
}
------------- Defs -----------------
def ADDri { // Inst
  string Mnemonic = "addi";
  int Cost = 1;
  bit HasImm = 1;
}
def ADDrr { // Inst
  string Mnemonic = "add";
  int Cost = 1;
  bit HasImm = 0;
}
def MULri { // Inst
  string Mnemonic = "muli";
  int Cost = 3;
  bit HasImm = 1;
}
def MULrr { // Inst
  string Mnemonic = "mul";
  int Cost = 3;
  bit HasImm = 0;
}
Type set is empty for each HW mode:
possible type contradiction in the pattern below (use -print-records with llvm-tblgen to see all expanded records).
BADADD:     (add:{ *:[] } GPR:{ *:[i64] }:$s, FPR:{ *:[f32] }:$t)

What to notice: Definition 21.8.1 at work. defm ADD produced ADDrr and ADDri (the multiclass's records, prefixed). ri's body let set HasImm = 1. The top-level let Cost = 3 in overrode the inherited Cost of both MUL records, even though the template argument said 0. In bad.td, Algorithm 21.8.3 intersected add's SameAs sets {i64} and {f32} and got the empty set, printed as { *:[] } next to the add.

GCC machine descriptions¶

The descriptions are gcc/config/<target>/<target>.md (for x86-64 gcc/config/i386/i386.md, plus constraints.md and predicates.md). genrecog (gcc/genrecog.cc) builds recog, and genemit and genoutput build the emitters and output templates (gcc-15 branch) [GCC-MD].

GCC names the pattern and alternative it recognized

Reproduce (GCC 13.3.0; -dP annotates the assembly with the RTL of each insn and {pattern-name}; store.c from Lesson 21.1 §7; the second command needs network access to GitHub):

gcc -O2 -S -dP store.c -o - | grep -E 'movq|\{\*movdi_internal\}'
curl -sL https://raw.githubusercontent.com/gcc-mirror/gcc/releases/gcc-15/gcc/config/i386/i386.md \
  | sed -n '/^(define_insn "\*movdi_internal"/,/ix86_hardreg_mov_ok/p'

Output (complete):

#                (const_int 24 [0x18])) [1 MEM[(long int *)p_8(D) + 24B]+0 S8 A64])) "store.c":1:45 82 {*movdi_internal}
    movq    24(%rdx), %rax  # 8 [c=9 l=4]  *movdi_internal/3
#        (reg:DI 0 ax [orig:85 _4 ] [85])) "store.c":1:45 82 {*movdi_internal}
    movq    %rax, (%rdi,%rsi,8) # 9 [c=4 l=4]  *movdi_internal/5
(define_insn "*movdi_internal"
  [(set (match_operand:DI 0 "nonimmediate_operand"
    "=r  ,o  ,r,r  ,r,m ,*y,*y,?*y,?m,?r,?*y,?Yv,?v,?v,m ,m,?jc,?*Yd,?r,?v,?*y,?*x,*k,*k  ,*r,*m,*k")
    (match_operand:DI 1 "general_operand"
    "riFo,riF,Z,rem,i,re,C ,*y,Bk ,*y,*y,r  ,C  ,?v,Bk,?v,v,*Yd,jc  ,?v,r ,*x ,*y ,*r,*kBk,*k,*k,CBC"))]
  "!(MEM_P (operands[0]) && MEM_P (operands[1]))
   && ix86_hardreg_mov_ok (operands[0], operands[1])"

What to notice: both moves were recognized as insn code 82, *movdi_internal (Proposition 21.8.7), with alternatives 3 (r ← rem, a load) and 5 (m ← re, a store), counting from 0. The condition string forbids memory on both sides, the reason for the failed memory-to-memory combination in Lesson 21.1 §7. The constraint letters are register classes (r, v, k) and operand forms (m memory, e 32-bit sign-extended immediate). c=9 and c=4 are the insn costs combine compared. (The GitHub file is the gcc-15 branch. The template shown matches the one GCC 13.3 used here.)

Tree-grammar and ADL descriptions¶

lcc's descriptions are src/x86linux.md, src/mips.md, src/sparc.md and src/alpha.md, processed by lburg/lburg.c (commit 2b5cf358) [LCC-Src]. HotSpot's are src/hotspot/cpu/<arch>/<arch>.ad, processed by the ADLC sources in src/hotspot/share/adlc/ (archDesc.cpp, dfa.cpp, output_c.cpp) (JDK 21) [HS-ADLC].

lcc's x86 addressing modes as grammar nonterminals

Reproduce (lcc at commit 2b5cf358d9aa6759923dd7461f2df7f7f2a28471; needs network access to GitHub):

curl -sL https://raw.githubusercontent.com/drh/lcc/2b5cf358d9aa6759923dd7461f2df7f7f2a28471/src/x86linux.md \
  | sed -n '366,380p;391,405p'

Output (complete):

baseaddr: ADDRGP4       "%a"
base: reg               "(%0)"
base: ADDI4(reg,acon)   "%1(%0)"
base: ADDP4(reg,acon)   "%1(%0)"
base: ADDU4(reg,acon)   "%1(%0)"
base: ADDRFP4           "%a(%%ebp)"
base: ADDRLP4           "%a(%%ebp)"

index: reg              "%0"
index: LSHI4(reg,con1)  "%0,2"
index: LSHI4(reg,con2)  "%0,4"
index: LSHI4(reg,con3)  "%0,8"
index: LSHU4(reg,con1)  "%0,2"
index: LSHU4(reg,con2)  "%0,4"
index: LSHU4(reg,con3)  "%0,8"
addr: base                      "%0"
addr: baseaddr                  "%0"
addr: ADDI4(index,baseaddr)     "%1(,%0)"
addr: ADDP4(index,baseaddr)     "%1(,%0)"
addr: ADDU4(index,baseaddr)     "%1(,%0)"

addr: ADDI4(reg,baseaddr)       "%1(%0)"
addr: ADDP4(reg,baseaddr)       "%1(%0)"
addr: ADDU4(reg,baseaddr)       "%1(%0)"

addr: ADDI4(index,reg)          "(%1,%0)"
addr: ADDP4(index,reg)          "(%1,%0)"
addr: ADDU4(index,reg)          "(%1,%0)"

addr: index  "(,%0)"

What to notice: the x86 addressing mode is not one pattern but a small grammar: index covers a register shifted by 1, 2 or 3 (scales 2, 4, 8), base covers a register plus a constant or a frame slot, and addr combines them. con3 is a nonterminal whose dynamic cost range(a, 3, 3) accepts only the constant 3 (Definition 21.2.10). The templates build the AT&T operand text ("%1(,%0)" → disp(,index,scale)) as the reducer walks the derivation. This is how Tessera's r16 and r18 would look in a grammar with addressing-mode nonterminals, as in labs/ch21-isel/rules/tessera-chain.rules.

8. Comparison¶

Technique	Power / precision	Speed (asymptotic · practical)	Output / error quality	Implementation effort	Typical use
LLVM TableGen	general records; many generated artifacts (selectors, encoders, registers, CC, scheduling); typed patterns (Proposition 21.8.4)	x86 matcher generated in about 10 s; elaboration linear	type contradictions reported with the offending pattern; semantics unchecked	high learning curve; very high reuse	every LLVM back end
GCC machine descriptions	RTL templates with constraints and alternatives; conditions in C	`recog` decision tree generated at build time	first match in file order (Proposition 21.8.7); order-dependent surprises	moderate per pattern; large files (i386.md: 30,221 lines)	every GCC back end
Tree-grammar and ADL descriptions	exactly the tile grammars of Lesson 21.1, with dynamic costs (lburg) or operand classes and encodings (ADL)	labelers generated in linear time	"no cover" at compile time for missing rules	low for lburg (one line per rule); moderate for ADL (encodings included)	lcc, iburg users, HotSpot C2

Choose TableGen when you work in LLVM. Nothing else is an option there, and its checks (types, operand lists) catch many errors early.
Choose a tree grammar when you want to see and reason about the selector as the grammar it is, as in teaching compilers, small retargetable compilers, or the lab.

9. Assessment¶

Technique	Quiz ids (`solutions/quizzes/ch21.yaml`)	Drill	Flashcard tag	Exercises
LLVM TableGen	`tblgen-let-override`, `tblgen-complexity`	none: record elaboration is quizzed on fixed files	`tablegen`	Try it above (Tessera.td)
GCC machine descriptions	`gcc-recog-order`, `gcc-no-mem-mem`	none (the quiz uses the `-dP` output)	`gcc-md`	—
Tree-grammar and ADL descriptions	`lburg-addr-nonterminals`, `adl-instruct-parts`	`./course drill dp-tiling` (the labels such a grammar yields)	`grammar-desc`	E4 ★ reads rules files

Believing a pattern because it type-checks

TableGen, genrecog and lburg all check form: types, operand counts, reachability. None of them checks that the instruction's semantics equal its pattern's. A swapped operand order in a non-commutative pattern ((sub $t, $s) for sub $d, $s, $t) generates, compiles and passes every generator check, and then miscompiles every subtraction. Test selectors end to end on running code (the lab's simulator), or verify rules against semantics (Crocus, Lesson 21.7).

References¶

See the chapter references.

Technique	Generation time	Size of generated code	Compile-time cost of the result	Justification
LLVM TableGen	elaboration \(O(r \cdot \text{fields})\); type inference \(O(t \cdot M)\) per pattern (Proposition 21.8.4); matcher construction \(O(r \log r)\) for sorting plus factoring	x86: 27,595 patterns, a 627 KB matcher table (Lesson 21.5 §7)	see Lesson 21.5	set sizes bound the propagation steps
GCC machine descriptions	decision-tree construction, near linear in the templates with factoring	`insn-recog.cc` of hundreds of thousands of lines for i386	`recog` walks one tree path plus predicates	Proposition 21.8.7
Tree grammars and ADL	linear in the rules (Algorithm 21.8.9)	lcc's x86: 7048 lines of C generated from `x86linux.md`	the DP of Lesson 21.2	one guarded block per rule

Lesson 21.8 — Describing targets: TableGen, GCC machine descriptions and tree grammars¶

1. Problem and motivation¶

LLVM TableGen¶

GCC machine descriptions¶

Tree-grammar and ADL descriptions¶

2. Definitions and algorithms¶

LLVM TableGen¶

GCC machine descriptions¶

Tree-grammar and ADL descriptions¶

3. Worked example¶

LLVM TableGen¶

GCC machine descriptions¶

Tree-grammar and ADL descriptions¶

4. Invariants and correctness¶

LLVM TableGen¶

GCC machine descriptions¶

Tree-grammar and ADL descriptions¶

5. Complexity¶

6. Variants and refinements¶

LLVM TableGen¶

GCC machine descriptions¶

Tree-grammar and ADL descriptions¶

7. In real compilers¶

LLVM TableGen¶

GCC machine descriptions¶

Tree-grammar and ADL descriptions¶

8. Comparison¶

9. Assessment¶

References¶