Lab 8.L1 · One program, four IRs: stack bytecode, TAC, ANF and block-argument SSA

Chapter: 8 · The Design Space of IRs · Lessons: 8.1 (stack, TAC), 8.4 (SSA with block arguments), 8.6 (ANF) · Time: 8–14 hours · Tests: ./course test 8 (labels ch08)

Goal

Compile one small imperative language, Tiny (Chapter 0's lab language), into four intermediate representations: stack bytecode, three-address code (quadruples), A-normal form with join points, and SSA with block arguments. Each form is a documented text format. The provided interpreters run your output, a provided validator checks your SSA, and the tests compare every form with the reference evaluator on hand-written and random programs. A benchmark then counts instructions, statically and dynamically, so you can see what each design costs. The parser, the random-program generator, the four interpreters, the SSA validator and the reference evaluator are provided: everything between the syntax tree and the four texts is yours.

The Tiny language

Exactly the language of labs/ch00-exec/SPEC.md: 64-bit wrapping integers, all variables start at 0, x / 0 = 0, x % 0 = x, INT64_MIN / -1 = INT64_MIN, x % -1 = 0, comparisons and ! give 0 or 1, &&/|| short-circuit and give 0 or 1, while, if/else, and a final return e;. Its big-step semantics is Definition 0.2.2. The syntax tree is include/tiny/AST.h of the Chapter 0 lab (every variable already has a slot number and Program::Vars[slot] is its name).

The four forms

Common rules for all four texts:

• The first non-blank line is the form's name: stack, tac, anf or ssa.
• # starts a comment that runs to the end of the line. Blank lines and indentation are ignored (except that a line is one instruction in stack, tac and ssa).
• Names are [A-Za-z_][A-Za-z0-9_.]*. Tiny source names never contain ., so names such as t.3 or x.1 cannot clash with them.
• Integers are decimal, optionally negative, and must fit in 64 bits.
• The operators are add sub mul div rem lt le gt ge eq ne (binary) and neg not (unary), with exactly Tiny's semantics.

stack

Chapter 0's stack machine (Definition 0.2.4) with symbolic labels. One instruction per line:

push K | load X | store X | add … ne | neg | not | jmp L | jz L | jnz L | ret
L:                                # a label for the next instruction

Binary operators pop the right operand first. jz/jnz pop their test value. Variables start at 0. Running past the last instruction, stack underflow, and ret on an empty stack are run-time errors.

stack
  push 1
  store i
loop:
  load i
  push 10
  le
  jz done
  load s
  load i
  add
  store s
  load i
  push 1
  add
  store i
  jmp loop
done:
  load s
  ret

tac

Three-address code (Definition 8.1.2). One instruction per line; a, b are a name or an integer:

x = a                    # copy
x = OP a, b              # binary
x = neg a | x = not a    # unary
goto L
if a goto L              # jump when a != 0
ifz a goto L             # jump when a == 0
return a
L:                       # a label for the next instruction

Variables start at 0. Labels are unique, every jump names an existing label, and the last instruction must be goto or return: a listing that can fall off its end is rejected by the reader.

tac
  i = 1
loop:
  t = le i, 10
  ifz t goto done
  s = add s, i
  i = add i, 1
  goto loop
done:
  return s

anf

A-normal form with join points (Definition 8.6.4), free-form (line breaks do not matter):

M ::= let x = P in M
    | join j(x, …) = M in M        # j callable only from the `in` part
    | loop j(x, …) = M in M        # j callable from the `in` part and from its own body
    | if a then M else M           # then-branch when a != 0
    | jump j(a, …)
    | return a
P ::= a | neg a | not a | OP a, b

Scoping is lexical and checked when the text is read: every variable must be bound by an enclosing let or join-point parameter, and jump j must name a join point in scope with the right number of arguments. There are no implicit variables: a Tiny variable that is read before being assigned must be bound to 0 explicitly (or its value 0 passed as a constant). Variables and join points share one namespace, and an inner binding shadows an outer one.

anf
loop head(s, i) =
  let t = le i, 10 in
  if t then
    let s1 = add s, i in
    let i1 = add i, 1 in
    jump head(s1, i1)
  else
    return s
in
jump head(0, 1)

ssa

SSA with block arguments (Definition 8.4.4). Blocks, then instructions, then exactly one terminator per block:

NAME:  or  NAME(p1, p2, …):                  # block header; the first block is the entry
x = a | x = OP a, b | x = neg a | x = not a  # instructions
br B(a, …)                                   # B or B() when there are no arguments
cbr a, B1(a, …), B2(a, …)                    # to B1 when a != 0, else to B2
ret a

A branch evaluates all its arguments and then assigns them to the target's parameters (a parallel copy). The provided validator enforces:

Rule	Checks
S0	the text parses
S1	every name is defined once (as a parameter or an instruction result)
S2	every use is dominated by its definition: a parameter of B dominates all of B; an instruction dominates what follows it in its block (including branch arguments of the terminator); a definition in block D dominates a use in B iff D dominates B. Uses in unreachable blocks are exempt
S3	a branch to B passes exactly as many arguments as B has parameters
S4	block names are unique; targets exist; the entry block has no parameters and no branch targets it

ssa
entry:
  br head(0, 1)
head(s, i):
  t = le i, 10
  cbr t, body(), done()
body:
  s1 = add s, i
  i1 = add i, 1
  br head(s1, i1)
done:
  ret s

Counting rules

Form	Static size	Executed steps
stack	instructions (labels excluded)	instructions executed
tac	instructions (labels excluded)	instructions executed
anf	let, if, jump and return nodes (join/loop definitions excluded, like block headers)	those nodes evaluated
ssa	instructions + one terminator per block (headers excluded)	instructions and terminators executed

The four samples above all return 55. Their sizes are 17, 7, 7 and 7, and their step counts 138, 54, 54 and 54 (tests/ch08/lit/run-machines.test).

Requirements

• R1 (all forms). For every terminating Tiny program P and every form F, irforms::run(F, lower(P, F)) returns irforms::evaluate(P), including the wrapping and division edge cases.
• R2 (stack). The stack form uses the operand stack for expression evaluation: the code contains no more store instructions than the program has assignment statements. A translation that stores every intermediate in a variable is correct but defeats the comparison.
• R3 (tac). One quadruple per operator (Proposition 8.1.11): the listing has at most one instruction per operator, five per &&/||, one copy per assignment, two per while or if, plus the final return. && and || must short-circuit (in Tiny this is unobservable, so it is not tested).
• R4 (ssa). The SSA text passes the validator (S0–S4). Minimal SSA is not required: passing every variable at every join is fine (Algorithm 8.4.7).
• R5 (all forms, especially anf). The output's static size is linear in the program: a chain of 10 if/else statements lowers to at most 420 counted instructions in every form. For ANF this means join points for control-flow merges (Theorem 8.6.9); the text must also be well scoped (the reader checks it). Duplicating the code after an if is correct but blows up exponentially.
• R6 (determinism). lower is a function of its input: two calls return the same text.
• R7 (no evaluation at compile time). The translation is syntax-directed: it must not run the program. The tests require at least one executed instruction per evaluation of a while condition.

The contract

// labs/ch08-forms/include/irforms/Lower.h  (provided; do not change)
namespace irforms {
/// Translates P into form F; returns the program text (first line "stack", "tac", "anf" or "ssa").
/// Return an error only for a genuine internal failure: every valid Tiny program must lower.
std::expected<std::string, std::string> lower(const tiny::Program &P, Form F);
}

Form (Stack, TAC, ANF, SSA) and the provided functions are in include/irforms/Forms.h.

Command line

ch08-lower --form=stack|tac|anf|ssa (<file.tiny> | --random=SEED)     # your lower(), provided driver
ch08-lower --print-random=SEED                                         # the random program's source
ch08-run --form=tiny|stack|tac|anf|ssa [--stats] [--check] (<file> | -)  # provided
ch08-compare [--quick] [--seeds=N]                                      # provided benchmark

ch08-run prints the returned value (and with --stats, steps: N and size: M); --form=tiny runs the reference evaluator on Tiny source; --check only parses and validates, printing ok. Exit status: 0 success, 1 usage/parse/validation error, 2 run-time error. Messages go to stderr as error: …, for example error: S2: the definition of 't' in block 'then' does not dominate its use in block 'join' (instruction 0).

Provided infrastructure

File	What it gives you
../ch00-exec/include/tiny/{AST,Parser,Random}.h + provided/	the Tiny parser and the random terminating programs (shared with Chapter 0)
include/irforms/Forms.h, provided/Forms.cpp	readers and interpreters of the four forms (run, staticSize), validateSSA, evaluate, and the TAC listing type used by lab L2
tools/LowerMain.cpp, tools/RunMain.cpp, bench/Compare.cpp	ch08-lower, ch08-run, ch08-compare
inputs/*.tiny	euler1 (the chapter's running example), gcd, straight, logic, nested, collatz, answer
src/	yours: Stub.cpp defines lower with TODO(ch08); add any files

The Python oracle tools/course/lib/irforms.py implements the same formats and a reference lowering for each form; the tests' expected values come from it.

What the tests check

Test	Checks
ch08.Forms/LowerTest.Samples/<form>	R1 on inputs/*.tiny (expected values in tests/ch08/Inputs/samples.txt, computed by the Python oracle), R4 for ssa, R7
ch08.Forms/LowerTest.EdgeSemantics/<form>	R1 on 10 one-line programs: wrapping, division by 0 and −1, short-circuit values, empty bodies, reassignments, an unassigned variable
ch08.Forms/LowerTest.RandomPrograms/<form>	R1, R4 and R7 on 300 random programs (ch08-lower --print-random=SEED shows a failing one)
ch08.Forms/LowerTest.Deterministic/<form>	R6
ch08.Forms/LowerTest.Economy/<form>	R5 on a chain of 10 ifs (all forms); R2 (stack) and R3's size bound (tac) on 100 random programs
ch08.Machines.HandWritten	the provided interpreters and validator (passes before you start)
ch08.lit lower-*.test	the ch08-lower | ch08-run pipeline on the running example in all four forms; the header line; --random against --form=tiny; parse and usage errors
ch08.lit run-machines.test	the provided tool: counts of the four samples above, validator messages S1–S3, ANF scope errors, stack underflow (passes before you start)
ch08.lab.compare-smoke	ch08-compare --quick: all four forms agree with the evaluator (numbers informational)

Only R3's short-circuiting is not tested (it is unobservable in Tiny). The benchmark shows the cost of each design, and the reference solution in solutions/labs/ch08-forms/src/ is one way to meet the requirements.

Milestones

1. TAC (Algorithm 8.1.4): ctest --test-dir build/<preset> -R 'LowerTest.*/tac'.
2. Stack (Algorithm 8.1.7, Chapter 0's compiler with labels): -R 'LowerTest.*/stack'.
3. SSA with block arguments (Algorithm 8.4.7): -R 'LowerTest.*/ssa'. Start with straight-line programs, then if, then while, then &&/||.
4. ANF with join points (Algorithm 8.6.5): -R 'LowerTest.*/anf'.
5. Measure: run ch08-compare and fill in the table below.

Measurement

build/<preset>/bin/ch08-compare prints, for every sample and summed over 200 random programs, the static size and the executed steps of each form, plus the ratios relative to stack code. Fill in yours and compare with the reference:

	stack	TAC	ANF	SSA
euler1 static / steps (reference)	37 / 249	19 / 127	18 / 130	17 / 127
random ×200, ratio of steps to stack (reference)	1.00	0.52	0.51	0.50
yours

Questions to answer from your numbers: Why is ANF's step count larger than SSA's on euler1 (130 vs 127)? (Hint: count what a jump costs versus a cbr with arguments.) Why do copies (x = y) disappear entirely from your SSA and ANF but not from your TAC?

Hints

Hint 1 — where to start

Write TAC first: it is Algorithm 8.1.4 almost line by line, with a name supply for temporaries and labels. Stack code is the same traversal with push/load instead of returning atoms. Keep one small Emitter per form that appends lines to a string.

Hint 2 — the key idea for SSA and ANF

Keep an environment from each source variable to the atom that currently holds its value, instead of emitting copies. An assignment only updates the environment. At a join (loop header, the block after an if, the value of &&), create fresh parameters and pass the current environment as arguments from every predecessor. ANF is the same algorithm with a continuation: "what to emit after this statement, given the environment", which is where the join point's body comes from.

Hint 3 — a design sketch

SSA: Env = vector<string> indexed by slot; gen(expr, env) -> atom; stmts(list, env) -> env; blocks as a list of lines with a "current block" pointer; a while emits br head(env…), opens head(params), emits the test and cbr … body(), exit(), then the body ending in br head(env'…), and the exit block continues with the head's environment (it has one predecessor). ANF: using K = function<Lines(atom)> and using EnvK = function<Lines(Env)>. if creates join j(params) = <rest of the statements> in <test and branches that end in jump j(env…)>. while creates loop h(params) = <test; if then <body; jump h(…)> else <rest>> in jump h(env…). The bug the tests catch most often: using the environment of the branch after an if instead of the join's parameters.

Stretch goals ★

• Emit pruned SSA: pass only the variables that the loop or branch actually assigns and that are used afterwards (compare your parameter count with tac_to_ssa in the oracle, 4 phis for euler1).
• Emit register bytecode (Algorithm 8.1.9) from your stack code and count instructions again.
• Write an ANF → SSA flattener and check that validateSSA accepts its output on every random program (Theorem 8.6.12(b)).