Lesson 8.1 — Linear IRs: three-address code, stack bytecode and register bytecode¶
Techniques: three-address code (quadruples, triples, indirect triples), stack bytecode (JVM, WebAssembly, CPython), register bytecode (Lua 5, Dalvik, V8 Ignition) · Pebble uses: PIR is a three-address IR over typed locals; the lab lowers Tiny to stack code and to quadruples · Lab: labs/ch08-forms · Prerequisites: Lesson 0.2 (stack machines, Tiny) · Time: 5–7 hours
Here is the chapter's running example, the sum of the multiples of 3 or 5 up to 10, written in Tiny (labs/ch08-forms/inputs/euler1.tiny):
n = 10;
s = 0;
i = 1;
while i <= n {
if i % 3 == 0 || i % 5 == 0 { s = s + i; }
i = i + 1;
}
return s;
It returns 33. Every lesson of this chapter shows this program in a different intermediate representation (IR). This lesson covers the three linear designs: a list of instructions with jumps, differing in how an instruction names its operands.
1. Problem and motivation¶
The problem. A compiler needs a representation between source and machine code that is (a) easy to generate from a syntax tree, (b) easy to analyze and transform, and (c) easy to execute or translate further. A linear IR is a sequence of instructions with explicit jumps, like assembly for an abstract machine. The designs differ in where operands live: in named variables (three-address code), on an implicit operand stack (stack bytecode), or in numbered registers of a frame (register bytecode).
Three-address code¶
Three-address code (TAC) gives every intermediate result a name: t1 = a + b has at most three addresses, two operands and a result. It dates from the first optimizing compilers (FORTRAN I's intermediate "quadruples") and is the textbook IR of [Dragon2, §6.2] and [EaC3, Ch. 4]. Because every value has a name, an optimizer can refer to "the value computed by instruction 7". This is what dataflow analysis (Ch 14) and SSA (Lesson 8.4) need. GCC's GIMPLE is TAC, LLVM IR is TAC in SSA form, and PIR's statements (_4 = saddo _1, _2) are TAC over typed locals.
Stack bytecode¶
Stack code leaves operand names implicit: iload 1; iload 2; iadd pushes two values and adds the top two. Instructions are short (often one byte), and the code generator is a postorder walk. This made stack code the choice for distribution formats: Pascal P-code, the JVM [JVMS], .NET CIL, CPython's bytecode, and WebAssembly [HRS+17]. A distribution format must be checked before it runs, so the JVM and Wasm specify a verifier. The verifier proves that the stack has a statically known shape at every instruction. That property is the central theorem of this technique (Theorem 8.1.12).
Register bytecode¶
Register bytecode names its operands explicitly, like TAC, but the names are small numbers of slots in the current frame: Lua's ADD A B C means R[A] := R[B] + R[C]. Lua 5.0 switched from a stack VM to a register VM [IdFC05]. Shi, Gregg, Beatty and Ertl translated JVM stack code into register code and report that more than 47 % of executed VM instructions disappear while the code grows by about 25 % [SGBE05]. Dalvik (Android's original VM) and V8's Ignition interpreter (a register machine with an accumulator) are register designs too [Dalvik, V8-Ignition]. Register bytecode is TAC with bounded, numbered names. The translation from stack code (Algorithm 8.1.9) shows how close the two are.
2. Definitions and algorithms¶
Definition 8.1.1 (Intermediate representation)
An intermediate representation is a triple \((\mathcal{L}, \mathrm{WF}, [\![\cdot]\!])\): a set \(\mathcal{L}\) of programs (its syntax), a well-formedness predicate \(\mathrm{WF} \subseteq \mathcal{L}\) (the invariants every pass may assume and must re-establish: verifier rules, typing, SSA dominance), and a semantics \([\![\cdot]\!]\) that maps each well-formed program to its set of behaviors (Definition 0.1.1). A lowering \(T\) from IR \(A\) to IR \(B\) is correct if it maps \(\mathrm{WF}_A\) into \(\mathrm{WF}_B\) and \(T(p)\) refines \(p\) for every well-formed \(p\) (Definition 0.1.2).
The four IRs of the lab
The lab (SPEC) defines four IRs in this sense.
stack: WF = "labels defined, jumps resolved" (heights are checked at run time).
tac: WF = "labels defined, the last instruction cannot fall through".
ssa: WF = rules S0–S4 (Definition 8.4.4). anf: WF = "every name in scope" (Definition 8.6.4).
All four have the same semantics: the integer returned by the program.
Three-address code¶
Definition 8.1.2 (Three-address code; quadruple)
Let \(\mathrm{Var}\) be a set of variables, \(\mathbb{Z}_{64}\) the 64-bit integers, and the atoms \(a, b \in \mathrm{Var} \cup \mathbb{Z}_{64}\). A three-address instruction is one of: \(x = a\) (copy); \(x = \mathit{op}\ a, b\) (binary, \(\mathit{op} \in \{\mathsf{add}, \mathsf{sub}, \mathsf{mul}, \mathsf{div}, \mathsf{rem}, \mathsf{lt}, \mathsf{le}, \mathsf{gt}, \mathsf{ge}, \mathsf{eq}, \mathsf{ne}\}\)); \(x = \mathit{op}\ a\) (unary: \(\mathsf{neg}, \mathsf{not}\)); \(\mathsf{goto}\ L\); \(\mathsf{if}\ a\ \mathsf{goto}\ L\) (jump iff \(a \ne 0\)); \(\mathsf{ifz}\ a\ \mathsf{goto}\ L\) (jump iff \(a = 0\)); \(\mathsf{return}\ a\). A listing is a sequence \(c_0 c_1 \dots c_{n-1}\) of instructions with labels attached to some of them. Written as a record, an instruction is a quadruple \((\mathit{op}, \mathit{arg}_1, \mathit{arg}_2, \mathit{result})\). Execution starts at \(c_0\) with every variable \(0\); the operators are Tiny's total operators (Definition 0.2.2).
Definition 8.1.3 (Triples and indirect triples)
A triple is \((\mathit{op}, \mathit{arg}_1, \mathit{arg}_2)\) where each argument is an atom or a reference \((k)\) to the triple at position \(k\). The result has no name: it is the position. An assignment to a source variable is the triple \((=, x, \mathit{arg})\). Indirect triples add an array \(\pi\) of positions: the program executes \(\mathit{triple}[\pi(0)], \mathit{triple}[\pi(1)], \dots\), and references still name positions in the triple table, not in \(\pi\).
Algorithm 8.1.4 (Syntax-directed TAC generation)
- Input: a Tiny program \(p\) (Definition 0.2.1) as a syntax tree.
- Output: a TAC listing (Definition 8.1.2).
- Precondition: temporaries \(t.0, t.1, \dots\) and labels \(L.0, L.1, \dots\) do not occur in \(p\) (source names contain no
.). - Postcondition: running the listing returns the value of \(p\) (Theorem 8.1.10), and every operator of \(p\) except
&&/||becomes exactly one instruction (Proposition 8.1.11). - Invariant: after
Gen(e, d)the atom it returns holds \([\![e]\!]\sigma\), where \(\sigma\) is the source state before the code of \(e\); no source variable other than \(d\) has changed.
function Gen(e, d = none): # returns an atom holding the value of e
case e of
k or x: if d = none: return the atom k or x
Emit(d = e); return d
op1 e1: a ← Gen(e1); t ← d or NewTemp(); Emit(t = op(op1) a); return t
e1 && e2: t ← d or NewTemp(); Lf ← NewLabel(); Ld ← NewLabel()
a ← Gen(e1); Emit(ifz a goto Lf)
b ← Gen(e2); Emit(ifz b goto Lf)
Emit(t = 1); Emit(goto Ld); Label(Lf); Emit(t = 0); Label(Ld)
return t
e1 || e2: the same with `if` for `ifz` and the constants 1 and 0 swapped
e1 ⊕ e2: a ← Gen(e1); b ← Gen(e2); t ← d or NewTemp()
Emit(t = op(⊕) a, b); return t
function GenStmts(ss):
for s in ss:
case s of
x = e: GenInto ← Gen(e, x) # computes straight into x
while c { b }: Lh ← NewLabel(); Lx ← NewLabel()
Label(Lh); a ← Gen(c); Emit(ifz a goto Lx)
GenStmts(b); Emit(goto Lh); Label(Lx)
if c { b1 } else { b0 }:
Le ← NewLabel(); Ld ← NewLabel(); a ← Gen(c)
if b0 is empty: Emit(ifz a goto Ld); GenStmts(b1); Label(Ld)
else: Emit(ifz a goto Le); GenStmts(b1); Emit(goto Ld)
Label(Le); GenStmts(b0); Label(Ld)
function Translate(ss return e): GenStmts(ss); a ← Gen(e); Emit(return a)
# Emit appends an instruction; Label(L) attaches L to the next instruction emitted;
# NewTemp/NewLabel return t.k / L.k with a fresh k.
Computing into the destination is only safe because operands are read first
x = x + 1 becomes the single quadruple x = add x, 1, and s = s + i becomes s = add s, i.
This is correct because a quadruple reads its operands before it writes its result. It would
be wrong for x = (x = 1) + x in a language with assignment expressions. Tiny has none.
Stack bytecode¶
Definition 8.1.5 (Stack code, stack effect, height consistency)
Stack code is the machine of Definition 0.2.4 with labels instead of numeric targets:
push k, load x, store x, the binary and unary operators, jmp L, jz L, jnz L,
ret. The stack effect \(\delta(c)\) is \(+1\) for push and load, \(-1\) for store,
binary operators, jz, jnz and ret, and \(0\) for unary operators and jmp. Each
instruction also has a requirement \(\rho(c)\), the number of values it pops: \(2\) for
binary operators, \(1\) for store, unary operators, jz, jnz and ret, else \(0\). The
control-flow successors \(\mathrm{succ}(i)\) of instruction \(i\) are \(i+1\) (unless \(c_i\)
is jmp or ret) and the target of a jump. A height assignment is a map
\(h : \{0, \dots, n-1\} \to \mathbb{N}\). It is consistent if \(h(0) = 0\),
\(h(i) \ge \rho(c_i)\) for every reachable \(i\), and \(h(j) = h(i) + \delta(c_i)\) for every
reachable \(i\) and every \(j \in \mathrm{succ}(i)\).
Algorithm 8.1.6 (Stack-height verification)
- Input: stack code \(c_0 \dots c_{n-1}\) (Definition 8.1.5).
- Output: the consistent height assignment on the reachable instructions, or "reject" with the offending instruction.
- Precondition: every jump target is a defined label.
- Postcondition: "accept" iff a consistent assignment exists, and then \(h\) is it (Theorem 8.1.13).
- Invariant: every instruction in the worklist \(W\) has \(h\) defined; for every processed \(i\), every successor \(j\) has \(h(j) = h(i) + \delta(c_i)\).
function VerifyHeights(c[0..n)):
h ← empty map; h[0] ← 0; W ← [0]
while W is not empty:
i ← pop(W)
if h[i] < ρ(c[i]): reject("stack underflow at", i)
out ← h[i] + δ(c[i])
for j in succ(i):
if j ≥ n: reject("falls off the end at", i)
if h[j] is undefined: h[j] ← out; push(W, j)
else if h[j] ≠ out: reject("inconsistent height at", j)
return h
Algorithm 8.1.7 (Stack code generation with labels)
- Input: a Tiny program as a syntax tree.
- Output: stack code (Definition 8.1.5).
- Precondition: labels \(L.k\) are fresh.
- Postcondition: the code computes the program's value (Theorem 0.2.12) and passes Algorithm 8.1.6 (Theorem 8.1.12).
- Invariant:
CodeE(e)leaves exactly one value above the stack it started with;CodeS(s)leaves the stack as it found it.
function CodeE(e):
case e of
k: Emit(push k)
x: Emit(load x)
op1 e1: CodeE(e1); Emit(op(op1))
e1 ⊕ e2: CodeE(e1); CodeE(e2); Emit(op(⊕)) # postorder
e1 && e2: Ls ← NewLabel(); Ld ← NewLabel()
CodeE(e1); Emit(jz Ls); CodeE(e2); Emit(jz Ls)
Emit(push 1); Emit(jmp Ld); Label(Ls); Emit(push 0); Label(Ld)
e1 || e2: the same with jnz, and push 0 / push 1 swapped
function CodeS(ss):
for s in ss:
case s of
x = e: CodeE(e); Emit(store x)
while c { b }: Label(Lh); CodeE(c); Emit(jz Lx); CodeS(b); Emit(jmp Lh); Label(Lx)
if c { b1 } else { b0 }:
CodeE(c); Emit(jz Le); CodeS(b1); Emit(jmp Ld)
Label(Le); CodeS(b0); Label(Ld) # b0 empty: jz Ld, no jmp
function Compile(ss return e): CodeS(ss); CodeE(e); Emit(ret)
Register bytecode¶
Definition 8.1.8 (Register bytecode)
A register machine has a frame of \(R\) registers \(r_0, \dots, r_{R-1}\) and a constant
table \(K\). An instruction names its operands by register or constant index:
\(\mathsf{OP}\ A\ B\ C\) means \(r_A := r_B \oplus \mathit{RK}(C)\), where \(\mathit{RK}(C)\) is
\(r_C\) or a constant \(K[C]\). Jumps are relative offsets. Register bytecode is TAC whose
variables are drawn from the finite set \(\{r_0, \dots, r_{R-1}\}\), fixed per function.
Lua 5.4's ADD A B C and MODK A B C (R[A] := R[B] % K[C]) are two instances
[LUA-Opcodes].
Algorithm 8.1.9 (Stack-to-register translation)
- Input: stack code \(c\) accepted by Algorithm 8.1.6, with its heights \(h\).
- Output: register code over registers \(s_0, \dots, s_{H-1}\) plus the program variables, where \(H = \max h + 1\).
- Precondition: \(h\) is consistent (Definition 8.1.5).
- Postcondition: the output computes the same value (Theorem 8.1.15), with at most one instruction per stack instruction.
- Invariant: before instruction \(i\) executes, the stack \(\langle v_0, \dots, v_{h(i)-1} \rangle\) of the stack machine equals \(\langle s_0, \dots, s_{h(i)-1} \rangle\) in the register machine.
function StackToRegister(c, h):
for i in 0 .. n-1 (unreachable i: skip), with k ← h[i]:
keep the labels of c[i]
case c[i] of
push v: Emit(s_k = v)
load x: Emit(s_k = x)
store x: Emit(x = s_{k-1})
binop: Emit(s_{k-2} = binop s_{k-2}, s_{k-1})
unop: Emit(s_{k-1} = unop s_{k-1})
jmp L: Emit(goto L)
jz L: Emit(ifz s_{k-1} goto L)
jnz L: Emit(if s_{k-1} goto L)
ret: Emit(return s_{k-1})
# Followed, inside each basic block (Lesson 8.2), by copy propagation: a copy s_k = v
# whose s_k is read once before being overwritten, with v not assigned in between,
# is substituted into that read.
3. Worked example¶
Three-address code of the running example¶
Algorithm 8.1.4 turns the running example into this listing (ch08-lower --form=tac, reference solution; the oracle tools/course/lib/irforms.py prints the same). Instruction numbers are on the left:
0 n = 10 10 if t.5 goto L.4
1 s = 0 11 t.1 = 0
2 i = 1 12 goto L.5
L.0: L.4:
3 t.0 = le i, n 13 t.1 = 1
4 ifz t.0 goto L.1 L.5:
5 t.2 = rem i, 3 14 ifz t.1 goto L.3
6 t.3 = eq t.2, 0 15 s = add s, i
7 if t.3 goto L.4 L.3:
8 t.4 = rem i, 5 16 i = add i, 1
9 t.5 = eq t.4, 0 17 goto L.0
L.1:
18 return s
Nineteen instructions. The || became jumping code (lines 7–13) that materializes its value into t.1, and line 14 tests it. GCC does better for a condition: its gimplifier jumps straight to the then block (the GIMPLE box in §7). That is the jumping-code lowering of Ch 11.
Quadruples, triples and indirect triples¶
Take the first two statements of straight.tiny after a = 7; b = 5: x = (a + b) * (a - b); y = (b + a) * (a - b) + x.
| # | quadruple (op, arg1, arg2, result) | triple (op, arg1, arg2) |
|---|---|---|
| 0 | (add, a, b, t.0) | (add, a, b) |
| 1 | (sub, a, b, t.1) | (sub, a, b) |
| 2 | (mul, t.0, t.1, x) | (mul, (0), (1)) |
| 3 | (add, b, a, t.2) | (=, x, (2)) |
| 4 | (sub, a, b, t.3) | (add, b, a) |
| 5 | (mul, t.2, t.3, t.4) | (sub, a, b) |
| 6 | (add, t.4, x, y) | (mul, (4), (5)) |
| 7 | (add, (6), x) | |
| 8 | (=, y, (7)) |
The triples need two extra entries for the assignments to x and y, because a triple has no result field. Suppose an optimizer hoists triple 5 above triple 4. In the triple table every reference to positions 4 and 5 must be renumbered: (6) becomes (mul, (5), (4)). With indirect triples the table stays as it is and only \(\pi\) changes, from \(\langle 0,1,\dots,8 \rangle\) to \(\langle 0,1,2,3,5,4,6,7,8 \rangle\). Proposition 8.1.11 makes this precise.
Stack code and its heights¶
Algorithm 8.1.7 produces 37 instructions (ch08-lower --form=stack). Algorithm 8.1.6 assigns these heights. The table lists \(h\) at instruction entry, in program order. Every reachable instruction receives its height once and is never contradicted:
| pc | label | instr | \(h\) | pc | label | instr | \(h\) |
|---|---|---|---|---|---|---|---|
| 0 | push 10 | 0 | 19 | push 0 | 1 | ||
| 1 | store n | 1 | 20 | eq | 2 | ||
| 2 | push 0 | 0 | 21 | jnz L.4 | 1 | ||
| 3 | store s | 1 | 22 | push 0 | 0 | ||
| 4 | push 1 | 0 | 23 | jmp L.5 | 1 | ||
| 5 | store i | 1 | 24 | L.4 | push 1 | 0 | |
| 6 | L.0 | load i | 0 | 25 | L.5 | jz L.3 | 1 |
| 7 | load n | 1 | 26 | load s | 0 | ||
| 8 | le | 2 | 27 | load i | 1 | ||
| 9 | jz L.1 | 1 | 28 | add | 2 | ||
| 10 | load i | 0 | 29 | store s | 1 | ||
| 11 | push 3 | 1 | 30 | L.3 | load i | 0 | |
| 12 | rem | 2 | 31 | push 1 | 1 | ||
| 13 | push 0 | 1 | 32 | add | 2 | ||
| 14 | eq | 2 | 33 | store i | 1 | ||
| 15 | jnz L.4 | 1 | 34 | jmp L.0 | 0 | ||
| 16 | load i | 0 | 35 | L.1 | load s | 0 | |
| 17 | push 5 | 1 | 36 | ret | 1 | ||
| 18 | rem | 2 |
Instruction 25 is reached from 23 (jmp, height \(1 + 0\)) and by falling through from 24 (push 1, height \(0 + 1\)). Both give 1, so the check succeeds. The single stack slot at 25 holds 0 on one path and 1 on the other: a stack slot at a join point is an implicit phi (Lesson 8.4). The maximum height is 2, so the JVM would record max_stack = 2 for this method.
Stack to registers¶
Algorithm 8.1.9 on instructions 10–15 (heights 0, 1, 2, 1, 2, 1):
| pc | stack instr | \(k = h\) | register instr | after copy propagation |
|---|---|---|---|---|
| 10 | load i | 0 | \(s_0\) = i | (folded into 12) |
| 11 | push 3 | 1 | \(s_1\) = 3 | (folded into 12) |
| 12 | rem | 2 | \(s_0\) = rem \(s_0\), \(s_1\) | \(s_0\) = rem i, 3 |
| 13 | push 0 | 1 | \(s_1\) = 0 | (folded into 14) |
| 14 | eq | 2 | \(s_0\) = eq \(s_0\), \(s_1\) | \(s_0\) = eq \(s_0\), 0 |
| 15 | jnz L.4 | 1 | if \(s_0\) goto L.4 | if \(s_0\) goto L.4 |
Six stack instructions become three register instructions. These are exactly TAC lines 5–7 with \(s_0\) in place of t.2/t.3. At pc 25 the translation writes \(s_0 = 0\) on one path and \(s_0 = 1\) on the other; \(s_0\) is assigned twice, like t.1 in the TAC.
Try it
./course drill stack-code --seed 4 --difficulty medium --solution (Chapter 0's drill): stack code, its depth,
and the register code of an expression. For the whole program:
ch08-lower --form=stack labs/ch08-forms/inputs/euler1.tiny | ch08-run --form=stack --stats -.
4. Invariants and correctness¶
Three-address code¶
Theorem 8.1.10 (Algorithm 8.1.4 is correct)
Let \(\sigma\) be a state and let \(\sigma'\) agree with \(\sigma\) on the source variables.
Running the code emitted by Gen(e, d) from \(\sigma'\) terminates in a state \(\sigma''\)
whose returned atom holds \(v\) with \(\langle e, \sigma \rangle \Downarrow v\), and
\(\sigma''\) agrees with \(\sigma'\) on every source variable except \(d\). For statements,
running GenStmts(ss) from \(\sigma'\) reaches the end with source state \(\sigma_1\)
iff \(\langle ss, \sigma \rangle \Downarrow \sigma_1\). Hence Translate(p) returns the
value of \(p\) whenever \(p\) terminates.
Proof
By structural induction on \(e\). Atoms emit nothing (or one copy into \(d\)), and the
atom's value in \(\sigma'\) equals its value in \(\sigma\) because the two agree on source
variables. Unary and binary operators: by induction Gen(e1) yields an atom \(a\)
holding \(v_1\) and changes no source variable (it was called with $d = $ none). Then
Gen(e2) yields \(b\) holding \(v_2\). It cannot have overwritten \(a\): \(a\) is a constant, a
source variable (unchanged), or a temporary created before Gen(e2) ran, and
Gen(e2) writes only temporaries created during it. The final instruction computes
\(v_1 \mathbin{\hat{\oplus}} v_2\) into \(t\), and only \(t = d\) may be a source variable. Short
circuit (&&): if \(v_1 = 0\) control jumps to \(L_f\) and \(t = 0\), matching the first
rule for && in Definition 0.2.2. Otherwise Gen(e2) runs, and \(t\) becomes \([v_2 \ne 0]\),
matching the second rule. || is dual. Statements, by induction on the derivation of
\(\langle ss, \sigma \rangle \Downarrow \sigma_1\). An assignment \(x = e\) calls Gen(e, x),
which by the expression case sets \(x\) to \(v\) and nothing else. while: the code at \(L_h\)
evaluates \(c\); if it is \(0\) it jumps to \(L_x\) (the rule with \(\Downarrow 0\)). Otherwise it
runs the body, which by induction reaches the goto with state \(\sigma_1\), and the
derivation continues from \(L_h\) with \(\sigma_1\) (the unrolling rule). if is similar.
The two directions of "iff" follow because the code is deterministic and each rule of
Definition 0.2.2 corresponds to exactly one path through the emitted code.
Proposition 8.1.11 (Sizes and reordering cost of the three encodings)
(a) For an expression with \(o\) operators other than &&/|| and \(q\) occurrences of
&&/||, Gen emits exactly \(o + 5q\) instructions when it is called with $d = $ none.
With \(d \neq\) none, an expression that is a leaf costs one copy, and otherwise the count
does not change (the last instruction writes \(d\)). (b) Moving one instruction from
position \(i\) to position \(j\) costs \(O(1)\) list operations for quadruples (names do not
depend on positions) and for indirect triples (one move in \(\pi\)). For triples it costs
\(\Theta(r)\) updates, where \(r\) is the number of references into positions between \(i\)
and \(j\), and \(r\) is \(\Theta(n)\) in the worst case.
Proof
(a) By induction on \(e\): leaves emit nothing when \(d\) is none, each unary or binary
operator emits one instruction after its operands, and a short-circuit node emits its two
tests, the two constant assignments and one goto: \(2 + 2 + 1 = 5\) instructions after
its operands. With a
destination, the last instruction of an operator node writes \(d\) instead of a new
temporary, so the count is unchanged, and a leaf needs the copy d = a. (b) Quadruples
refer to results by name, so the order of the list is free. An indirect-triple
reference \((k)\) names a slot of the triple table, which a move does not touch, so only
\(\pi\) changes. A triple reference names the execution position itself. Moving an
instruction shifts every position between \(i\) and \(j\) by one, and every reference to a
shifted position must be rewritten. Each triple holds at most two references, so
\(r \le 2n\). The family "triple \(k\) refers to triple \(k - 1\)" makes \(r = \lvert i - j \rvert\).
Stack bytecode¶
Theorem 8.1.12 (Generated stack code is height-consistent)
For every Tiny program, the code of Algorithm 8.1.7 has a consistent height assignment (Definition 8.1.5) with \(h = 0\) at the first instruction of every statement, and \(\max_i h(i) = \max_{e} D(e)\) over the expressions \(e\) of the program, where \(D\) is the stack depth of Theorem 0.2.13.
Proof
Define \(h\) by the invariant of Algorithm 8.1.7. The code of a statement starts at height
\(0\). The code of an expression starts at the height \(m\) at which CodeE is called and
ends at \(m + 1\). We check \(h(j) = h(i) + \delta(c_i)\) for every edge \(i \to j\), by
structural induction. Straight-line parts follow from the stack effects: push/load
add one, a binary operator consumes two and produces one (\(-1\)), store removes one.
Jumps: in while, jz Lx is at height \(1\) (after the condition) and pops it, so
\(L_x\) has height \(0\), which is also the height after the loop body's closing jmp
(height \(0\), effect \(0\)). The back edge jmp Lh goes from height 0 to \(L_h\), which has
height 0. if is the same. In e1 && e2 called at height \(m\): both jz Ls are at
height \(m+1\) and pop, so \(L_s\) is entered at height \(m\) by both jumps. push 0 then
reaches \(m + 1\) at \(L_d\), and the fall-through path push 1; jmp Ld also arrives at \(L_d\)
with \(m + 1\). Every edge agrees, so \(h\) is consistent, and \(\rho(c_i) \le h(i)\)
because each operator executes after its operands have been pushed. The maximum is
reached inside some expression, where it equals \(D(e)\) by Theorem 0.2.13.
Theorem 8.1.13 (Algorithm 8.1.6 decides height consistency in linear time)
Algorithm 8.1.6 terminates after at most \(n\) iterations. It accepts iff the code has a consistent height assignment (Definition 8.1.5), and on acceptance its \(h\) is the unique one on the reachable instructions.
Proof
Termination: an instruction enters \(W\) only when \(h\) becomes defined for it, which happens at most once. So there are at most \(n\) iterations, each doing \(O(1)\) work per successor (at most 2). Uniqueness: on the reachable part, a consistent \(h\) is forced by induction on the length of a shortest path from \(0\): \(h(0) = 0\), and \(h(j) = h(i) + \delta(c_i)\) for the predecessor \(i\) on that path. Soundness of accept: by the invariant, when \(W\) empties every edge out of every processed instruction satisfies the equation (checked, or used to set \(h(j)\)), every processed instruction had \(h(i) \ge \rho(c_i)\), and the processed instructions are exactly the reachable ones. So \(h\) is consistent. Soundness of reject: underflow at \(i\) means the forced value \(h(i)\) is below \(\rho(c_i)\). An inconsistent height at \(j\) means two edges force two different values. Either way, by uniqueness, no consistent assignment exists.
Corollary 8.1.14 (Verified stack code runs without dynamic checks)
If Algorithm 8.1.6 accepts \(c\), then no execution of \(c\) underflows the stack, and the
stack never holds more than \(\max h\) values. An interpreter may therefore omit underflow
checks and allocate a fixed operand array of size \(\max h\) per frame. This is the JVM's
max_stack.
Proof
By induction on the number of executed steps: the stack height before instruction \(i\) is exactly \(h(i)\), because it is \(0\) at instruction \(0\) and every step from \(i\) to \(j\) adds \(\delta(c_i)\), which is \(h(j) - h(i)\) by consistency. Underflow at \(i\) would need a height below \(\rho(c_i) \le h(i)\).
Register bytecode¶
Theorem 8.1.15 (Algorithm 8.1.9 is correct)
Let \(c\) be stack code with consistent heights \(h\), and \(r\) its register translation. For every execution of \(c\) and every step count \(t\): if \(c\) is at instruction \(i\) with stack \(\langle v_0, \dots, v_{k-1} \rangle\) and variable state \(\sigma\) after \(t\) steps, then \(r\) is at the translation of instruction \(i\) after \(t\) steps, with \(s_m = v_m\) for \(m < k = h(i)\) and the same \(\sigma\). In particular, both return the same value.
Proof
By induction on \(t\), using the invariant of the algorithm. At \(t = 0\) both are at
instruction 0 with empty stack and \(k = 0\). Step: the stack instruction at \(i\) uses the top
\(\rho(c_i)\) values, which are at positions \(k-\rho(c_i), \dots, k-1\). The translation
reads exactly the registers \(s_{k-\rho}, \dots, s_{k-1}\), which hold them by hypothesis.
It writes its result to \(s_{k + \delta(c_i) - 1}\), the new top position (for push:
\(s_k\); binary: \(s_{k-2}\); unary: \(s_{k-1}\)), and leaves the registers below untouched.
store x writes \(x\) from \(s_{k-1}\). Jumps test the same value and go to the translated
label. The next instruction \(j\) has \(h(j) = k + \delta(c_i)\) by consistency, so the
invariant holds at \(j\). Registers \(s_m\) with \(m \ge h(j)\) may hold stale values, but the
invariant says nothing about them. Copy propagation inside a block preserves the
semantics, because each substituted copy's target is read exactly once before it is
redefined, and its source \(v\) is not assigned between the copy and that read, so the read
sees the same value.
Proposition 8.1.16 (Instruction counts: stack versus register)
For an expression tree with \(\ell\) leaves and \(o \geq 1\) operators (no &&/||), stack
code has \(\ell + o\) instructions. Register code has \(o\) instructions when leaves can be
operands (registers or constants, as in Lua's RK operands) and \(\ell + o\) when they
must be loaded first. The ratio \(o / (\ell + o)\) is at most \(1/2\) for binary operators,
since \(\ell = o + 1\).
Proof
Algorithm 8.1.7 emits one push/load per leaf and one instruction per operator. The
register form of Algorithm 8.1.9 after copy propagation removes each leaf's copy by
substituting the leaf into its single consumer, leaving one instruction per operator.
A tree with only binary operators has \(\ell = o + 1\), so the register code has
\(o/(2o + 1) < 1/2\) of the stack instructions. That the measured saving is "only" 47 % on
real Java programs [SGBE05] reflects statements, calls and loads that are not pure
expression trees.
5. Complexity¶
Variables: \(n\) = number of instructions, \(\lvert e \rvert\) = size of the syntax tree, \(D\) = maximum stack depth.
| Technique | Time (worst) | Time (typical) | Space | Justification |
|---|---|---|---|---|
| TAC generation (Alg. 8.1.4) | \(O(\lvert e \rvert)\) | same | \(O(\lvert e \rvert)\) instructions | Proposition 8.1.11(a): at most 5 instructions per node |
| Triples: move one instruction | \(\Theta(n)\) | \(O(\text{uses})\) | none extra | Proposition 8.1.11(b) |
| Indirect triples: move | \(O(1)\) (linked list) or \(O(n)\) (array) | same | \(\pi\): \(n\) words | only \(\pi\) changes |
| Stack generation (Alg. 8.1.7) | \(O(\lvert e \rvert)\) | same | stack of depth \(D\) at run time | one instruction per leaf or operator |
| Height verification (Alg. 8.1.6) | \(O(n)\) | same | \(O(n)\) | Theorem 8.1.13 |
| Stack to register (Alg. 8.1.9) | \(O(n)\) | same | \(D\) registers | one instruction per instruction |
Pathological family. Right-nested subtraction \(e_m = a_1 - (a_2 - (\cdots - a_m))\) has stack depth \(D(e_m) = m\) with postorder code (Theorem 0.2.13), so a verifier records max_stack \(= m\) and the register translation uses \(m\) registers \(s_0 \dots s_{m-1}\). The left-nested form needs depth 2. Code size is identical (\(2m - 1\) instructions), but frame size grows linearly. Register allocation (Ch 22) and Ershov-number ordering (Theorem 0.2.14) exist for this case.
Verification at scale. The JVM's original verifier inferred types by iterating to a fixed point over the lattice of stack and local types. With the jsr/ret subroutine instructions, its precision and cost became problematic [Ler03]. Since class-file version 50, compilers emit StackMapTable frames at every branch target, so verification is a single linear check of the kind in Algorithm 8.1.6 rather than an inference [JVMS, §4.10.1]. WebAssembly was designed so that validation is one linear pass over structured code [HRS+17; WasmSpec].
6. Variants and refinements¶
Three-address code¶
- Tuple-based GIMPLE stores each statement's operands in a fixed array and allows only one operator per statement, which is TAC [GCC-Int]. The trade-off: dumps are easy to read, but an IR with C types still needs a separate, lower-level RTL for machine details.
- SSA-form TAC (LLVM IR) makes every name single-assignment (Lesson 8.4). Def-use chains become implicit, at the cost of phi functions at joins.
- Operand kinds. LLVM lets constants appear as operands (
add i64 %x, 1). GIMPLE requires "GIMPLE values" (a variable or an invariant) as operands. The same choice appears in Lua'sRKoperands.
Stack bytecode¶
- Structured stack code (WebAssembly):
block/loop/ifwith typed results replace arbitrary jumps. Validation is a single pass and the CFG is reducible by construction [HRS+17]. The trade-off: producers must structure their control flow (the Relooper/Stackifier problem). - Stack maps (JVM class files ≥ 50): the producer supplies the types at join points, and the verifier only checks them [JVMS, §4.10.1]. This trades class-file size for a linear verifier.
- Quickening and superinstructions (CPython 3.11's specializing adaptive interpreter, PEP 659) rewrite generic instructions into type-specialized ones at run time. They speed up dispatch without changing the IR's stack discipline.
Register bytecode¶
- Accumulator machines (V8 Ignition): one implicit accumulator plus explicit registers.
Add r0meansacc = acc + r0, which keeps instructions short [V8-Ignition]. The price is extraLda/Stamoves (the V8 box in §7 has several). - Wide register numbers (Dalvik): 4-, 8- and 16-bit register fields in 16-bit code units trade code density for large frames [Dalvik].
- Registers as stack slots (Lua): the compiler allocates temporaries in stack order, so the register file is still a stack, but instructions name the slots directly [IdFC05, §7].
7. In real compilers¶
Three-address code¶
GCC turns GENERIC trees into GIMPLE, three-address code with labels and gotos: gimplify_function_tree in gcc/gimplify.cc (gcc 15.1) [GCC-Gimplify]; the statement class gassign is declared in gcc/gimple.h [GCC-GimpleH]. LLVM IR is TAC in SSA form (llvm/include/llvm/IR/Instructions.h) [LLVM-LangRef]. PIR statements are TAC over locals (pir-spec §10).
GCC's GIMPLE is three-address code with labels
Reproduce (gcc 14.2.0, Ubuntu 24.04; any recent GCC gives the same shape):
cat > euler1.c <<'EOF'
long euler1(long n) {
long s = 0;
for (long i = 1; i <= n; i++)
if (i % 3 == 0 || i % 5 == 0)
s += i;
return s;
}
EOF
gcc-14 -O0 -c -fdump-tree-gimple=stdout euler1.c -o /dev/null
Output (complete):
long int euler1 (long int n)
{
long int D.2781;
long int s;
s = 0;
{
long int i;
i = 1;
goto <D.2776>;
<D.2775>:
_1 = i % 3;
if (_1 == 0) goto <D.2778>; else goto <D.2780>;
<D.2780>:
_2 = i % 5;
if (_2 == 0) goto <D.2778>; else goto <D.2779>;
<D.2778>:
s = s + i;
<D.2779>:
i = i + 1;
<D.2776>:
if (i <= n) goto <D.2775>; else goto <D.2773>;
<D.2773>:
}
D.2781 = s;
return D.2781;
}
What to notice: every statement has at most one operator (Definition 8.1.2). The
temporaries _1, _2 play the role of t.2, t.4 in our listing. Two differences from
Algorithm 8.1.4: GCC tests the loop condition at the bottom (goto <D.2776> enters
it), and its conditional jump has two targets, so || needs no materialized value. The
label numbers (D.2775) are GCC's internal declaration UIDs.
Stack bytecode¶
HotSpot interprets JVM bytecode and verifies it first (ClassVerifier in src/hotspot/share/classfile/verifier.cpp, OpenJDK) [JVMS, §4.10]. CPython compiles to stack bytecode in Python/compile.c and runs it in Python/ceval.c (v3.11.15) [CPY-Compile]. WebAssembly engines validate modules with the algorithm in the specification's appendix [WasmSpec].
JVM bytecode and its stack map frames
Reproduce (OpenJDK 21.0.10 javac and javap):
cat > Euler1.java <<'EOF'
class Euler1 {
static long euler1(long n) {
long s = 0;
for (long i = 1; i <= n; i++)
if (i % 3 == 0 || i % 5 == 0)
s += i;
return s;
}
}
EOF
javac Euler1.java
javap -c Euler1 | sed -n '/static long euler1/,/^$/p'
javap -v Euler1 | sed -n '/static long euler1/,/^}/p' | sed -n '/stack=/p;/StackMapTable/,/^$/p'
Output (complete; the JAVA_TOOL_OPTIONS notice some environments print is omitted):
static long euler1(long);
Code:
0: lconst_0
1: lstore_2
2: lconst_1
3: lstore 4
5: lload 4
7: lload_0
8: lcmp
9: ifgt 48
12: lload 4
14: ldc2_w #7 // long 3l
17: lrem
18: lconst_0
19: lcmp
20: ifeq 34
23: lload 4
25: ldc2_w #9 // long 5l
28: lrem
29: lconst_0
30: lcmp
31: ifne 39
34: lload_2
35: lload 4
37: ladd
38: lstore_2
39: lload 4
41: lconst_1
42: ladd
43: lstore 4
45: goto 5
48: lload_2
49: lreturn
}
stack=4, locals=6, args_size=1
StackMapTable: number_of_entries = 4
frame_type = 253 /* append */
offset_delta = 5
locals = [ long, long ]
frame_type = 28 /* same */
frame_type = 4 /* same */
frame_type = 250 /* chop */
offset_delta = 8
}
What to notice: 31 instructions in 50 bytes. stack=4 is \(\max h\) of Corollary 8.1.14
(a long takes two slots). The four frames sit at offsets \(5\), \(5+28+1 = 34\),
\(34+4+1 = 39\) and \(39+8+1 = 48\): exactly the jump targets. They are the join points
where Algorithm 8.1.6 would compare heights (and the JVM compares types), and the
leaders of Lesson 8.2 that are jump targets.
WebAssembly: structured stack code, validated in one pass
Reproduce (wabt 1.0.34 wat2wasm/wasm2wat; Wasmtime 37.0.2 to run it):
cat > euler1.wat <<'EOF'
(module
(func (export "euler1") (param $n i64) (result i64)
(local $s i64) (local $i i64)
(local.set $i (i64.const 1))
(block $exit
(loop $head
(br_if $exit (i64.gt_s (local.get $i) (local.get $n)))
(if (i32.or (i64.eqz (i64.rem_s (local.get $i) (i64.const 3)))
(i64.eqz (i64.rem_s (local.get $i) (i64.const 5))))
(then (local.set $s (i64.add (local.get $s) (local.get $i)))))
(local.set $i (i64.add (local.get $i) (i64.const 1)))
(br $head)))
(local.get $s)))
EOF
wat2wasm euler1.wat -o euler1.wasm && wasm2wat euler1.wasm
wasmtime --invoke euler1 euler1.wasm 10
cat > bad.wat <<'EOF'
(module
(func (param $c i32) (result i64)
(if (result i64) (local.get $c)
(then (i64.const 1))
(else (i32.const 0)))))
EOF
wat2wasm bad.wat -o bad.wasm
Output (complete; the two "experimental" warnings of --invoke omitted):
(module
(type (;0;) (func (param i64) (result i64)))
(func (;0;) (type 0) (param i64) (result i64)
(local i64 i64)
i64.const 1
local.set 2
block ;; label = @1
loop ;; label = @2
local.get 2
local.get 0
i64.gt_s
br_if 1 (;@1;)
local.get 2
i64.const 3
i64.rem_s
i64.eqz
local.get 2
i64.const 5
i64.rem_s
i64.eqz
i32.or
if ;; label = @3
local.get 1
local.get 2
i64.add
local.set 1
end
local.get 2
i64.const 1
i64.add
local.set 2
br 0 (;@2;)
end
end
local.get 1)
(export "euler1" (func 0)))
33
bad.wat:5:27: error: type mismatch in `if false` branch, expected [i64] but got [i32]
(else (i32.const 0)))))
^
What to notice: no jump targets, only block/loop/if and branches to enclosing
labels by depth (br_if 1). The validator checks types, not just heights: both arms of
an if must leave the declared [i64]. This is Definition 8.1.5 with a type per slot,
and the error is the typed version of "inconsistent height at a join point".
CPython 3.11 bytecode
Reproduce (CPython 3.11.15):
cat > euler1.py <<'EOF'
import dis
def euler1(n):
s = 0
i = 1
while i <= n:
if i % 3 == 0 or i % 5 == 0:
s += i
i += 1
return s
dis.dis(euler1)
EOF
python3 euler1.py
Output (complete):
3 0 RESUME 0
4 2 LOAD_CONST 1 (0)
4 STORE_FAST 1 (s)
5 6 LOAD_CONST 2 (1)
8 STORE_FAST 2 (i)
6 10 LOAD_FAST 2 (i)
12 LOAD_FAST 0 (n)
14 COMPARE_OP 1 (<=)
20 POP_JUMP_FORWARD_IF_FALSE 34 (to 90)
7 >> 22 LOAD_FAST 2 (i)
24 LOAD_CONST 3 (3)
26 BINARY_OP 6 (%)
30 LOAD_CONST 1 (0)
32 COMPARE_OP 2 (==)
38 POP_JUMP_FORWARD_IF_TRUE 9 (to 58)
40 LOAD_FAST 2 (i)
42 LOAD_CONST 4 (5)
44 BINARY_OP 6 (%)
48 LOAD_CONST 1 (0)
50 COMPARE_OP 2 (==)
56 POP_JUMP_FORWARD_IF_FALSE 5 (to 68)
8 >> 58 LOAD_FAST 1 (s)
60 LOAD_FAST 2 (i)
62 BINARY_OP 13 (+=)
66 STORE_FAST 1 (s)
9 >> 68 LOAD_FAST 2 (i)
70 LOAD_CONST 2 (1)
72 BINARY_OP 13 (+=)
76 STORE_FAST 2 (i)
6 78 LOAD_FAST 2 (i)
80 LOAD_FAST 0 (n)
82 COMPARE_OP 1 (<=)
88 POP_JUMP_BACKWARD_IF_TRUE 34 (to 22)
10 >> 90 LOAD_FAST 1 (s)
92 RETURN_VALUE
What to notice: the same postorder shape as Algorithm 8.1.7: LOAD_FAST i,
LOAD_CONST 3, BINARY_OP %. Offsets jump by more than 2 after COMPARE_OP and
BINARY_OP because 3.11 reserves inline cache entries there for its specializing
interpreter. >> marks jump targets. Like GCC, CPython duplicates the loop test at the
bottom.
Register bytecode¶
Lua 5.4 defines its register instructions in lopcodes.h (OP_ADD, OP_MODK; tag v5.4.6) and allocates registers in stack order in lcode.c [LUA-Opcodes]. V8's Ignition is a register machine with an accumulator (src/interpreter/bytecodes.h in V8) [V8-Ignition]. Dalvik executables use 16-bit code units with 4-, 8- or 16-bit register fields; Android's documentation specifies the instruction formats [Dalvik]. No Dalvik tool runs in the course container, so this lesson shows Lua and V8.
Lua 5.4: the running example in 19 register instructions
Reproduce (Lua 5.4.6, luac5.4 from Ubuntu's lua5.4 package):
cat > euler1.lua <<'EOF'
local function euler1(n)
local s = 0
local i = 1
while i <= n do
if i % 3 == 0 or i % 5 == 0 then s = s + i end
i = i + 1
end
return s
end
return euler1(10)
EOF
luac5.4 -l -l -p euler1.lua | sed -n '/^function <euler1.lua:1/,/^upvalues/p'
Output (complete; the hexadecimal addresses vary from run to run):
function <euler1.lua:1,9> (19 instructions at 0x562988d89000)
1 param, 4 slots, 0 upvalues, 3 locals, 2 constants, 0 functions
1 [2] LOADI 1 0
2 [3] LOADI 2 1
3 [4] LE 2 0 0
4 [4] JMP 13 ; to 18
5 [5] MODK 3 2 0 ; 3
6 [5] MMBINK 2 0 9 0 ; __mod 3
7 [5] EQI 3 0 1
8 [5] JMP 4 ; to 13
9 [5] MODK 3 2 1 ; 5
10 [5] MMBINK 2 1 9 0 ; __mod 5
11 [5] EQI 3 0 0
12 [5] JMP 2 ; to 15
13 [5] ADD 1 1 2
14 [5] MMBIN 1 2 6 ; __add
15 [6] ADDI 2 2 1
16 [6] MMBINI 2 1 6 0 ; __add
17 [6] JMP -15 ; to 3
18 [8] RETURN1 1
19 [9] RETURN0
constants (2) for 0x562988d89000:
0 I 3
1 I 5
locals (3) for 0x562988d89000:
0 n 1 20
1 s 2 20
2 i 3 20
upvalues (0) for 0x562988d89000:
What to notice: n, s, i live in registers 0, 1, 2 and the temporary in register 3
("4 slots" is the frame size \(R\) of Definition 8.1.8). MODK 3 2 0 is
R[3] := R[2] % K[0], one instruction where the stack code needs three
(load i; push 3; rem). Proposition 8.1.16 at work. The MMBIN* lines are the
slow paths for metamethods: an arithmetic instruction that succeeds on numbers skips the
MMBIN* that follows it.
V8 Ignition: registers plus an accumulator
Reproduce (Node.js 22.22.2, V8 12.4.254.21-node.39; sed removes the run-dependent addresses):
cat > euler1.js <<'EOF'
function euler1(n) {
let s = 0;
for (let i = 1; i <= n; i++)
if (i % 3 === 0 || i % 5 === 0) s += i;
return s;
}
console.log(euler1(10));
EOF
node --print-bytecode --print-bytecode-filter=euler1 euler1.js | sed -E 's/0x[0-9a-f]+ //g' | sed -n '1,34p'
Output (the first 33 lines; the source-position table and the printed 33 follow):
[generated bytecode for function: euler1 (<SharedFunctionInfo euler1>)]
Bytecode length: 57
Parameter count 2
Register count 3
Frame size 24
31 S> @ 0 : 0c LdaZero
@ 1 : c9 Star0
49 S> @ 2 : 0d 01 LdaSmi [1]
@ 4 : c8 Star1
54 S> @ 5 : 0b 03 Ldar a0
54 E> @ 7 : 73 f8 00 TestLessThanOrEqual r1, [0]
@ 10 : 9e 2c JumpIfFalse [44] (@ 54)
69 S> @ 12 : 0b f8 Ldar r1
75 E> @ 14 : 4b 03 01 ModSmi [3], [1]
@ 17 : c7 Star2
@ 18 : 0c LdaZero
79 E> @ 19 : 70 f7 02 TestEqualStrict r2, [2]
@ 22 : 9d 0e JumpIfTrue [14] (@ 36)
@ 24 : 0b f8 Ldar r1
90 E> @ 26 : 4b 05 03 ModSmi [5], [3]
@ 29 : c7 Star2
@ 30 : 0c LdaZero
94 E> @ 31 : 70 f7 04 TestEqualStrict r2, [4]
@ 34 : 9e 0b JumpIfFalse [11] (@ 45)
101 S> @ 36 : 0b f8 Ldar r1
106 E> @ 38 : 3b f9 05 Add r0, [5]
@ 41 : 19 f9 f7 Mov r0, r2
@ 44 : c9 Star0
61 S> @ 45 : 0b f8 Ldar r1
@ 47 : 53 06 Inc [6]
@ 49 : c8 Star1
36 E> @ 50 : 8e 2d 00 07 JumpLoop [45], [0], [7] (@ 5)
111 S> @ 54 : 0b f9 Ldar r0
120 S> @ 56 : ae Return
What to notice: ModSmi [3] computes acc = acc % 3: the accumulator is an
implicit operand and destination (§6), so values move with Ldar/Star. The bracketed
last operands ([1], [2], …) are feedback-vector slots where the interpreter records
types for the optimizing tiers (Lesson 8.5), which a pure IR would not need.
8. Comparison¶
| Technique | Power / precision | Speed (asymptotic · practical) | Output / error quality | Implementation effort | Typical use |
|---|---|---|---|---|---|
| Three-address code | every value named; any analysis or transformation; order free with quadruples | \(O(\lvert e \rvert)\) generation · 19 instructions / 127 executed steps on the running example | readable dumps (GIMPLE, PIR); names map to source variables | low (Algorithm 8.1.4) | optimizer IRs: GIMPLE, LLVM IR (SSA), PIR, Cranelift |
| Stack bytecode | implicit operands; needs verification (heights, types) before trust | \(O(\lvert e \rvert)\) generation, \(O(n)\) verification · 37 instructions / 249 steps (about 2× TAC) | compact (1-byte opcodes); verifier errors name the join point | lowest to generate; verifier moderate | distribution and interpretation: JVM, Wasm, CPython, CIL |
| Register bytecode | explicit operands in a bounded frame | \(O(n)\) from stack code · Lua: 19 instructions, about 47 % fewer executed instructions than stack code [SGBE05] | larger instructions (3 operands); register numbers less readable | moderate (register allocation of temporaries) | interpreters that care about dispatch count: Lua, Dalvik, V8 Ignition |
Comparison-lab results (reproduce with build/<preset>/bin/ch08-compare after the lab; reference solution, 200 random programs + samples): static size relative to stack code is 0.55 for TAC, and executed steps 0.52 for TAC (SPEC, Measurement).
Choose TAC when you will analyze and transform the code: names make def-use relations explicit, and quadruples can be reordered freely. Choose stack bytecode when the IR is shipped to an untrusted consumer or interpreted by a small VM: it is compact, trivial to generate, and verifiable in one pass. Choose register bytecode when you interpret and want fewer, heavier instructions per operation, and can afford a slightly smarter compiler.
9. Assessment¶
| Technique | Quiz ids (solutions/quizzes/ch08.yaml) |
Drill | Flashcard tag | Exercises |
|---|---|---|---|---|
| Three-address code | tac-count-quads, triples-reorder |
./course drill stack-code (register part) |
tac |
L1 (TAC form) |
| Stack bytecode | stack-heights, verify-reject |
./course drill stack-code |
stack-bytecode |
L1 (stack form) |
| Register bytecode | stack-to-register-count, lua-rk |
./course drill stack-code --difficulty hard |
register-bytecode |
Ch 0 lab (stack VM) |
Stack code is not simpler to analyze
Stack code is simpler to generate and to interpret, but an optimizer must first recover names. That is Algorithm 8.1.9, and every JIT for stack bytecode (HotSpot's C1/C2, V8's Liftoff/TurboFan for Wasm, Cranelift for Wasm) starts with it. Do not choose stack code as an optimizer's IR.
References¶
See the chapter references.