Chapter 11 · Lowering & Code Generation: AST → PIR → LLVM IR¶

Part 2 · Intermediate Representations & LLVM · about 3 weeks · Previous: Ch 10 · Next: Ch 12

The problem¶

You are given a type-checked Pebble AST: the names are resolved (Ch 5) and every expression has its type in the side table from analyze() (Ch 6). Produce a native executable that does what the program means, with the same output, the same exit status and a trap at the same place (spec §8, §15), and do it through two IRs. First comes PIR (Ch 8), a CFG of basic blocks over mutable locals with explicit checks. Then comes LLVM IR in SSA form, which LLVM optimizes, turns into an object file and hands to the system linker together with Pebble's runtime. Along the way you choose between well-studied alternatives. SSA can come from syntax-directed temporaries, from allocas cleaned up by mem2reg, or from on-the-fly construction. Conditions can be jumping code or boolean values. A switch can become a jump table, a search tree, bit tests or LLVM's own switch. Places and values must be kept apart, and loops come top-tested or rotated. Aggregates cross calls by value, through sret, byval or C-ABI coercion. A failed check can trap, unwind or return an error. The chapter also surveys what Pebble leaves out: exception tables, setjmp/longjmp, closure conversion and lambda lifting. In LLVM and Clang these are IRBuilder + PromoteMemToReg, CodeGenFunction::EmitBranchOnBoolExpr, SelectionDAGBuilder::visitSwitch, clang/lib/CodeGen/Targets/X86.cpp, invoke/landingpad and TargetMachine::addPassesToEmitFile. In pebblec you write lowerToPIR and the PIR → LLVM code generator, and from then on pebblec hello.pbl -o hello && ./hello works.

What you will be able to do¶

Lower every Pebble construct to PIR by syntax-directed translation. That means expressions with checks, statements and control flow, places vs values with Pebble's evaluation order, aggregates, calls and output. Prove the translation preserves evaluation order (Theorem 11.4.5).
Generate SSA three ways and compare their output: temporaries (Lemma 11.1.4), allocas + mem2reg (pruned SSA), and ★ Braun et al.'s on-the-fly construction (minimal on reducible CFGs). Count the phis each one places.
Compile a short-circuit condition as jumping code or as boolean values, count the blocks and edges, and state when speculating the operands is legal (Theorem 11.2.7).
Lower a switch as a jump table, a balanced search tree or bit tests. Predict LLVM's cluster partition (density, range, bit-test suitability) and verify it with llc.
Pass and return aggregates by value, through sret or byval, or with a caller copy. Classify a C struct under the System V x86-64 ABI and write Clang's coerced LLVM type.
Choose a failure policy (trap, unwind, error return) and explain what each one lets the optimizer assume. Read invoke/landingpad, a call-site table and SjLj lowering; closure-convert and lambda-lift a nested function by hand.
Emit an object file with LLVM's TargetMachine, link it with a runtime library through cc, and debug undefined symbols with llvm-nm and archive order.
Find where LLVM 23, Clang, GCC, rustc, Go and Cranelift implement each technique, and reproduce their behavior with clang, opt, llc, gcc, rustc and go.

Prerequisites: Ch 5 and Ch 6 (your analyze() gives lowering its types; with a skeleton front end use -DPEBBLE_USE_SOLUTION=lexer,parser,names,types); Ch 8 (PIR, CFGs); Ch 9 (LLVM IR, alloca, phis, poison, intrinsics); Ch 10 (IRBuilder, the ORC JIT); Lesson 0.6 (objects and linking). Lesson 11.1 uses dominance frontiers, which Ch 16 covers in depth; it states what it needs.

Notation¶

Shared notation follows the house notation: §1 (sets, functions, logic), §3 (graphs and CFGs), §7 (dataflow, SSA, IR), §8 (complexity) and §9 (numbered statements). Numbered statements are 11.k.m (lesson $k$). In this chapter:

Symbol	Meaning
$\mathcal{P}[\![p]\!]$, $\mathcal{V}[\![e]\!]$	the PIR place of a place expression, the PIR operand of an expression (Definition 11.4.1)
$\mathrm{JC}(e, t, f)$	jumping code for condition $e$ with true target $t$ and false target $f$ (Algorithm 11.2.2)
$\mathrm{Val}(e)$	the boolean-value translation of $e$ (Algorithm 11.2.6)
$\mathrm{DF}(B)$, $\mathrm{DF}^+(S)$	dominance frontier of block $B$; iterated dominance frontier of a set $S$ (Algorithm 11.1.6)
sealed, incomplete, trivial phi	the states of on-the-fly SSA construction (Definition 11.1.8)
$(v_i, d_i)$, $d_0$	a switch case (value, destination), the default destination (Definition 11.3.1)
$n$, $R$, $n/R$	number of cases, range $\max - \min + 1$, density of a switch or cluster (Definition 11.3.1)
INTEGER, SSE, MEMORY, NO_CLASS	System V x86-64 classes of an eightbyte (Algorithm 11.5.4)
`sret`, `byval`, `noalias`, `nobuiltin`	LLVM parameter and call-site attributes (Lesson 11.5; Lesson 11.9 §4)
$\mathrm{FV}(e)$, $E_i$	free variables of $e$; extra parameters of a lifted function (Definitions 11.8.1, Algorithm 11.8.4)
$U$	the linker's set of undefined symbols (Algorithm 0.6.6, Theorem 11.9.6)
$e$, $b$	in cost tables: number of expression nodes and of basic blocks of a function

Technique map¶

Family	Techniques (origin)	Lesson
SSA generation	Syntax-directed translation (Irons 1961 [Iro61]; [ALSU07, §6.4]); allocas + `mem2reg` (Clang, Kaleidoscope [KAL7]; phi placement by iterated dominance frontiers, Cytron et al. 1991 [CFRWZ91]; [LLVM-Mem2Reg]); ★ on-the-fly SSA construction (Braun et al. 2013 [BBH+13]; Cranelift [CL-SSA], Go [GO-Phi])	11.1
Conditions	Jumping code for `&&`, `\\|\\|`, `!` (Arden, Galler & Graham 1962 [AGG62]; [ALSU07, §6.6]); boolean values with `and`/`or`/`select` (LLVM SimplifyCFG [LLVM-SimplifyCFG], speculation legality [LLVM-ValueTracking])	11.2
Switch lowering	Jump tables (Sale 1981 [Sal81]); binary search trees (Hennessy & Mendelsohn 1982 [HM82]; Bernstein 1985 [Ber85]); bit tests (LLVM, GCC [GCC-SwitchConv]); LLVM's `switch` + back-end clustering (Kannan & Proebsting 1994 [KP94]; [LLVM-SwitchLowering], [LLVM-SDB])	11.3
Places and loops	L-value/r-value evaluation (Strachey [Str00]; Clang `EmitLValue` [CLANG-CGExpr], rustc `as_place` [RUSTC-AsPlace]); top-tested vs rotated loops ([LLVM-LoopRotate], GCC `pass_ch` [GCC-LoopCH], [LLVM-LoopTerm])	11.4
Aggregates and the ABI	By value (direct), `sret`, `byval`, caller copy + pointer ([LLVM-LangRef]); ABI coercion (System V x86-64 [SysV-ABI], AAPCS64 [AAPCS64]; Clang [CLANG-X86ABI, CLANG-AArch64ABI], rustc [RUSTC-X86ABI], GCC [GCC-I386])	11.5
Safety checks	Trap (Swift `cond_fail` [SWIFT-CondFail]); unwind (Rust panics [RUSTC-Assert], Go [GO-Bounds]); error return (Rust `?` [RUSTC-Try])	11.6
Exception handling (overview)	Zero-cost tables (Itanium C++ ABI [ItaniumEH]; [LLVM-EH], [LLVM-EHStreamer]); setjmp/longjmp ([LLVM-SjLj]); explicit error returns (Swift `swifterror` [SWIFT-Error], [LLVM-SwiftError])	11.7
Closures (overview)	Closure conversion (Landin 1964 [Lan64]; Appel & Jim 1989 [AJ89]; Minamide, Morrisett & Harper 1996 [MMH96]; OCaml [OCAML-Closure]); lambda lifting (Johnsson 1985 [Joh85]; Danvy & Schultz [DS02]; javac [JAVAC-Lambda], Go [GO-Closure])	11.8
Runtime and linking	Runtime library design (compiler-rt builtins [COMPILERRT-Divti3], LLVM libcalls [LLVM-RuntimeLibcalls], Rust `std::rt` [RUST-Rt]); object emission and linking ([LLVM-CodeGenTM]; Levine [Lev00]; Clang driver [CLANG-GnuLink])	11.9

flowchart LR
  SDT[Syntax-directed translation<br/>Irons 1961] --> TMP[SSA temporaries]
  SDT --> AL[Allocas + mem2reg<br/>Cytron et al. 1991]
  SDT -.->|★ variables too| BR[On-the-fly SSA<br/>Braun et al. 2013]
  SDT --> JC[Jumping code<br/>Arden–Galler–Graham 1962]
  JC <-->|SimplifyCFG speculation| BV[Boolean values / select]
  SDT --> SW[switch]
  SW --> JT[Jump table<br/>Sale 1981]
  SW --> BS[Binary search<br/>Hennessy–Mendelsohn 1982]
  SW --> BT[Bit tests]
  JT & BS & BT --> LS[LLVM clustering + tree<br/>Kannan–Proebsting 1994]
  SDT --> LV[Places vs values<br/>Strachey]
  LV --> AGG[Aggregates: direct, sret, byval]
  AGG --> ABI[C-ABI coercion<br/>SysV, AAPCS64]
  SDT --> CHK[Checks]
  CHK --> TR[Trap]
  CHK --> UW[Unwind]
  CHK --> ER[Error return]
  UW --> ZC[Zero-cost EH tables<br/>Itanium ABI]
  UW -.->|older| SJ[setjmp/longjmp EH]
  ER --> EX[Explicit error returns<br/>swifterror]
  NEST[Nested functions] --> CC[Closure conversion<br/>Landin 1964, Appel–Jim 1989]
  NEST --> LL[Lambda lifting<br/>Johnsson 1985]
  AL & TR & ABI --> OBJ[Object emission + linking<br/>TargetMachine, cc, runtime]

Who uses what¶

System	Technique	Notes
Clang 23	Allocas + `mem2reg`; jumping code (`EmitBranchOnBoolExpr`), `EmitLValue`; `switch` straight to LLVM; `sret`/`byval` and C-ABI coercion (`Targets/X86.cpp`, `AArch64.cpp`); traps for `-fsanitize-trap`; Itanium zero-cost EH (`invoke`/`landingpad`); lambdas as classes; links through the system linker	Lessons 11.1–11.7, 11.9
LLVM 23	`PromoteMemToReg`, SROA; SimplifyCFG speculation and `select`; switch clustering (`SwitchLoweringUtils.cpp`); LoopRotate; `DwarfEHPrepare`, `SjLjEHPrepare`, `swifterror`; libcalls (`RuntimeLibcalls.td`); `addPassesToEmitFile`	all lessons
rustc 1.94	MIR non-SSA locals → allocas, SSA for the rest; `LogicalOp` jumping code in MIR; scalar pairs + ABI adjustments; panics unwind by default, `Result` + `?`; closures as capture structs; `std::rt::lang_start`	Lessons 11.1, 11.2, 11.5, 11.6, 11.8, 11.9
GCC 15	Gimplification (temporaries, `shortcut_cond_expr`), `into-SSA` by dominance frontiers; switch conversion (jump tables, bit tests, decision trees); `pass_ch` loop header copying; `classify_argument`	Lessons 11.1–11.5
Go 1.24	On-the-fly-style phi insertion (`ssagen/phi.go`); binary search and jump tables in `walk/switch.go`; bounds checks that panic; direct closure calls	Lessons 11.1, 11.3, 11.6, 11.8
Cranelift	Braun-style `SSABuilder` with sealing	Lesson 11.1
Swift 6.1	`cond_fail` traps; typed error returns in the `swifterror` register	Lessons 11.6, 11.7
OCaml 4.14, javac 21	Flat closures (`closure.ml`); lambda bodies lifted to `lambda$…` methods	Lesson 11.8
`pebblec`	Syntax-directed lowering to PIR with jumping conditions and traps (E1–E4); allocas + `mem2reg` codegen (E5), ★ on-the-fly SSA (`--ssa=braun`, E6); direct/`sret`/caller-copy calls; C runtime linked through `cc`	this chapter's exercises

Comparison¶

One row per technique, the same rows as the lessons' §8 tables (each lesson has the "Choose it when…" paragraphs).

Technique	Power / precision	Speed (asymptotic · practical)	Output / error quality	Implementation effort	Typical use
Syntax-directed translation	SSA for expression temporaries only; variables stay mutable	$O(\lvert\mathrm{AST}\rvert)$ · one walk	Output mirrors the source; easy to map back to locations	Low	Every front end's first step: GIMPLE, MIR, PIR, Clang's IR emission
Allocas + mem2reg	Pruned SSA for every promotable slot; escaping slots stay in memory automatically	$O(V(n + e))$ · a separate pass, plus the load/store IR it deletes	The front end's IR is verbose (a load per read) but trivially correct	Lowest for the front end (no phis); mem2reg is shared	Clang, rustc (for non-SSA locals), Swift (`SILMem2Reg`), Pebble E5
On-the-fly SSA	Minimal SSA on reducible CFGs (+ SCC removal: all CFGs); needs to know which variables are address-taken	$O(V(n + e) + U)$ · no intermediate memory IR	Compact IR from the start; phi names follow variables	Medium (sealing discipline, trivial-phi removal)	Cranelift frontends, Go (variant), libFirm, Pebble ★ E6
Jumping code	Exact short-circuit semantics for any atoms, including traps and side effects	$\le n$ atoms, $\le n$ branches · wins when branches are predictable or atoms expensive	CFG mirrors the source; each atom keeps its own location	Low (one recursive function with two targets)	Every front end's lowering of `&&`/`\\|\\|`/`!` (Clang, GCC, rustc, Pebble)
Boolean values	Only for speculatable atoms (Theorem 11.2.7)	exactly $n$ atoms, 0 branches · wins on unpredictable conditions of cheap atoms	Straight-line code; `select` needed for poison safety	Low, plus a speculation-safety analysis	The optimizer's rewrite of jumping code (SimplifyCFG), `setcc`/`cmov` in back ends, SIMD code
Jump table	Any dense switch; size grows with the range	$O(1)$ · one indirect branch (hard to predict when targets vary)	Compact code, data table in `.rodata`	Low (plus a range check)	Dense switches, interpreters' opcode dispatch, `dense16`
Binary search tree	Any switch	$O(\log n)$ · predictable when inputs are skewed	Code grows linearly with cases	Low	Sparse switches (`sparse`), and the glue between clusters
Bit tests	$\max - \min < 64$, few destinations	$O(D)$ · a few ALU ops, no memory	Tiny: $D$ 64-bit constants	Low	Character classes (`chars`), flag sets (`bits3`)
LLVM `switch` + back end	All of the above, chosen per cluster (Theorem 11.3.8)	$O(\log N)$ + cluster cost · matches the best hand lowering in the lab except on unpredictable dense switches	One IR instruction; the choice is visible in the assembly	None for the front end; the DP lives in LLVM	Every LLVM front end, including Pebble's code generator
L-value/r-value evaluation (places as operands + materialize rule)	Exact source evaluation order (Theorem 11.4.5); conservative copies	$O(\lvert e \rvert)$ · copies vanish after mem2reg	PIR keeps places visible (`(*_0)[_2]`), so later chapters see every access	Medium (two translation functions, the may-write rule)	Every front end (Clang, javac, rustc MIR, Pebble)
Top-tested loops	Any loop	$n$ extra jumps per $n$ iterations	Mirrors the source	Lowest	Front ends' output (Clang, rustc, Pebble)
Rotated loops	Loops with a duplicable header and one latch	saves $n$ jumps; gives a guaranteed-to-execute preheader	Guard + preheader + bottom test; LCSSA phis	Medium (header copy, SSA repair)	LLVM `loop-rotate`, GCC `ch` at `-O1`/`-O2`, before LICM and vectorization
By value (direct)	Small aggregates; both sides agree on the split	fastest: registers, no memory	Readable IR (fields as values)	Low within one language	rustc's Rust ABI, Swift, LLVM first-class aggregates
`sret`	Any result type	one pointer; callee writes memory directly	Explicit hidden argument	Low	Large results in every C ABI; Pebble's aggregate results
`byval`	Any argument, stack-passed copies	an unavoidable copy per call	Copy hidden in the call lowering	Low in IR; ABI knowledge needed	x86-64 MEMORY-class C arguments
Caller copy + pointer	Any argument	a `memcpy`, removable by the optimizer	Copy visible in IR	Low	AAPCS64 large composites, rustc, Pebble
ABI coercion	Exactly the platform C ABI	as direct	Types look odd (`{ i32, double }`) but match C	High (per-target classifiers)	Clang, rustc and Swift `extern "C"`, any FFI
Trap	Stops at the first failure; no recovery, no cleanups	1 test + predictable branch per check · the optimizer may assume success after the check	Precise location (Pebble) or a bare check kind (UBSan trap); fixed exit status	Lowest	Pebble, Swift, hardened C (`-fsanitize-trap`), Rust `panic=abort`, kernels
Unwind	Recoverable; runs cleanups; crosses frames	0 instructions on the normal path (zero-cost EH) · failure costs a table walk per frame	Panic message + backtrace; handlers can report	High (unwind tables, landing pads, personality)	Rust `panic=unwind`, Go run-time panics, Java/C++ exceptions
Error return	Failure is an ordinary value; caller must handle it	a test per propagation step, even on success	Typed: the compiler forces handling (`Option`, `Result`)	Low in the compiler, verbose in code (`?` helps)	Rust `checked_` and `Result`, Go `(v, err)`, C `__builtin__overflow`, Swift `throws` (in a register)
Zero-cost exception tables	Full unwinding with cleanups and typed catch	0 on the normal path · a throw costs a table walk per frame, microseconds	Tables and CFI make debuggers and profilers able to unwind too	High (CFI, LSDA, personality, runtime)	C++ and Rust on Unix-like systems, Java-to-native, Swift's C++ interop
setjmp/longjmp	The same semantics	register/unregister and a store per call site on the normal path · cheap throws	Needs no CFI	Medium (a lowering pass + small runtime)	Targets without an unwinder; old ARM ABIs; early WebAssembly
Explicit error returns	No cleanups by unwinding (cleanups are ordinary code on the return path); only direct callers see the error	a test per call · throws cost a return per frame	Every throwing call is visible in the source (`try`, `?`)	Low (a register convention or a sum type)	Swift `throws`, Rust `Result`, Go `(v, err)`
Closure conversion	Any function value, including escaping ones	one allocation per closure creation + indirect calls · escape analysis can stack-allocate	Explicit environments; debuggers show captured fields	Medium (FV, records, calling convention for code pointers)	OCaml, Rust/C++/Swift closures, Scheme, JavaScript engines
Lambda lifting	Only non-escaping local functions (or the code part of escaping ones)	no allocation; more arguments per call	First-order code; argument lists grow	Low–medium (a fixed point over the call graph)	javac lambda bodies, Go direct closure calls, GHC late lifting
Runtime library design	Anything expressible in the runtime's language; the ABI contract fixes names, types and `noreturn`	a call per use · fine for I/O and traps, costly for hot arithmetic (then expand inline)	one place to print messages and choose exit statuses (Pebble 101, Rust 101)	Low for a C runtime; high when the runtime has a GC or a scheduler (Go)	Pebble's C runtime, compiler-rt builtins, Rust `std::rt`, Go `runtime`
Object emission and linking	Any target LLVM supports; the system linker handles the platform	emission linear after codegen; link $O(s + r)$ · link time dominates large builds	linker errors ("undefined reference") name symbols, not source lines	Low with a `TargetMachine` and `cc`; high for an integrated linker	`pebblec`, rustc and Clang (via `cc`/`ld`), Zig and Go (own linkers)

Comparison-lab results (reproduce with build/<preset>/bin/ch11-lowerlab conditions and … switches, reference solutions, x86-64 container, LLVM 23.1.2; nanoseconds per call, IR as emitted; full tables in the lab SPEC). Jumping code for or-of-and (4 comparisons) has 6 blocks and 4 conditional branches, and costs 6.51 ns on random inputs against 2.19 ns for the one-block value version. On a repeated input both take about 1.5 ns: jumping code loses only to branch misprediction. At -O2, SimplifyCFG turns every jumping-code input into one block. For switches, the LLVM switch is best or close on three of four inputs (bits3 2.34, chars 2.85, sparse 3.84 ns; the hand-written search wins sparse at 3.25). On the dense 16-case dense16, hand-written bit tests (4.07 ns) beat LLVM's jump table (8.27 ns), because the indirect jump mispredicts on random values.

Route through this chapter¶

Step	What	Techniques	How it is exercised
1	Lesson 11.1	syntax-directed translation, allocas + mem2reg, ★ on-the-fly SSA	Pebble implements E1–E4 (syntax-directed lowering), E5 (allocas), ★ E6 (on-the-fly SSA); drills `phi-placement`, `ssa-renaming` (Ch 16)
2	Lesson 11.2	jumping code, boolean values	Pebble implements jumping code (E2); drill `jumping-code`; lab Part A
3	Lesson 11.3	jump tables, binary search, bit tests, LLVM `switch`	E5 (PIR `switch` → LLVM `switch`); drill `switch-lowering`; lab Part B
4	Lesson 11.4	l-value/r-value evaluation, loop shapes	Pebble implements places vs operands and top-tested loops (E1–E3); e2e `order-*`; drill `loop-forms` (Ch 15)
5	Lesson 11.5	by value, `sret`, `byval`, caller copy, ABI coercion	Pebble implements `sret` + caller copy (E5); drill `abi-classify`
6	Lesson 11.6	trap, unwind, error return	Pebble implements traps (E1, E5); e2e `trap-*`; quiz
7	Lesson 11.7	zero-cost EH, SjLj, explicit error returns	overview: quiz, flashcards, real-compiler boxes
8	Lesson 11.8	closure conversion, lambda lifting	overview: quiz, flashcards (Ch 24 extension "closures for Pebble")
9	Lesson 11.9	runtime library, object emission and linking	provided runtime and driver; E4 runs every program natively
10	Exercises	Pebble uses syntax-directed lowering, jumping code, traps, allocas + mem2reg, `sret`	`./course test 11`
11	Comparison lab `labs/ch11-lowering/`	jumping vs values; four switch lowerings	lab tests + measurement
12	Theory test	all	`./course quiz 11` (≥ 80 % to finish)

Practice and check¶

./course drill jumping-code --difficulty medium   # targets of each comparison, blocks and edges
./course drill switch-lowering                    # clusters, density, LLVM's partition
./course drill abi-classify                       # SysV eightbyte classes and Clang's coerced type
./course flash 11                                 # daily, a few minutes
./course quiz 11                                  # after the lessons
./course test 11                                  # after the exercises and the lab
./course status                                   # done = quiz ≥ 80 % and tests pass

After E5, build/<preset>/bin/pebblec prog.pbl -o prog && ./prog builds native executables. --emit=ast|pir|llvm|obj|exe stops at any stage, and --from-pir/--from-llvm start later. -O1 runs the course pipeline, which is the steps that later chapters register (LLVM's default<O1> until one does), and -O2 runs LLVM's full default<O2> pipeline.

References¶

The chapter's annotated bibliography, with papers, textbook sections, pinned source files and docs, is in references.md. Start with [ALSU07, Ch. 6] (syntax-directed translation of expressions, conditions and switches), [CFRWZ91] and [BBH+13] (the two SSA constructions), [KP94] (switch clustering), the System V ABI [SysV-ABI], and the LLVM exception-handling guide [LLVM-EH].

Symbol	Meaning
\(\mathcal{P}[\![p]\!]\), \(\mathcal{V}[\![e]\!]\)	the PIR place of a place expression, the PIR operand of an expression (Definition 11.4.1)
\(\mathrm{JC}(e, t, f)\)	jumping code for condition \(e\) with true target \(t\) and false target \(f\) (Algorithm 11.2.2)
\(\mathrm{Val}(e)\)	the boolean-value translation of \(e\) (Algorithm 11.2.6)
\(\mathrm{DF}(B)\), \(\mathrm{DF}^+(S)\)	dominance frontier of block \(B\); iterated dominance frontier of a set \(S\) (Algorithm 11.1.6)
sealed, incomplete, trivial phi	the states of on-the-fly SSA construction (Definition 11.1.8)
\((v_i, d_i)\), \(d_0\)	a switch case (value, destination), the default destination (Definition 11.3.1)
\(n\), \(R\), \(n/R\)	number of cases, range \(\max - \min + 1\), density of a switch or cluster (Definition 11.3.1)
INTEGER, SSE, MEMORY, NO_CLASS	System V x86-64 classes of an eightbyte (Algorithm 11.5.4)
`sret`, `byval`, `noalias`, `nobuiltin`	LLVM parameter and call-site attributes (Lesson 11.5; Lesson 11.9 §4)
\(\mathrm{FV}(e)\), \(E_i\)	free variables of \(e\); extra parameters of a lifted function (Definitions 11.8.1, Algorithm 11.8.4)
\(U\)	the linker's set of undefined symbols (Algorithm 0.6.6, Theorem 11.9.6)
\(e\), \(b\)	in cost tables: number of expression nodes and of basic blocks of a function

Technique	Power / precision	Speed (asymptotic · practical)	Output / error quality	Implementation effort	Typical use
Syntax-directed translation	SSA for expression temporaries only; variables stay mutable	\(O(\lvert\mathrm{AST}\rvert)\) · one walk	Output mirrors the source; easy to map back to locations	Low	Every front end's first step: GIMPLE, MIR, PIR, Clang's IR emission
Allocas + mem2reg	Pruned SSA for every promotable slot; escaping slots stay in memory automatically	\(O(V(n + e))\) · a separate pass, plus the load/store IR it deletes	The front end's IR is verbose (a load per read) but trivially correct	Lowest for the front end (no phis); mem2reg is shared	Clang, rustc (for non-SSA locals), Swift (`SILMem2Reg`), Pebble E5
On-the-fly SSA	Minimal SSA on reducible CFGs (+ SCC removal: all CFGs); needs to know which variables are address-taken	\(O(V(n + e) + U)\) · no intermediate memory IR	Compact IR from the start; phi names follow variables	Medium (sealing discipline, trivial-phi removal)	Cranelift frontends, Go (variant), libFirm, Pebble ★ E6
Jumping code	Exact short-circuit semantics for any atoms, including traps and side effects	\(\le n\) atoms, \(\le n\) branches · wins when branches are predictable or atoms expensive	CFG mirrors the source; each atom keeps its own location	Low (one recursive function with two targets)	Every front end's lowering of `&&`/`\\|\\|`/`!` (Clang, GCC, rustc, Pebble)
Boolean values	Only for speculatable atoms (Theorem 11.2.7)	exactly \(n\) atoms, 0 branches · wins on unpredictable conditions of cheap atoms	Straight-line code; `select` needed for poison safety	Low, plus a speculation-safety analysis	The optimizer's rewrite of jumping code (SimplifyCFG), `setcc`/`cmov` in back ends, SIMD code
Jump table	Any dense switch; size grows with the range	\(O(1)\) · one indirect branch (hard to predict when targets vary)	Compact code, data table in `.rodata`	Low (plus a range check)	Dense switches, interpreters' opcode dispatch, `dense16`
Binary search tree	Any switch	\(O(\log n)\) · predictable when inputs are skewed	Code grows linearly with cases	Low	Sparse switches (`sparse`), and the glue between clusters
Bit tests	\(\max - \min < 64\), few destinations	\(O(D)\) · a few ALU ops, no memory	Tiny: \(D\) 64-bit constants	Low	Character classes (`chars`), flag sets (`bits3`)
LLVM `switch` + back end	All of the above, chosen per cluster (Theorem 11.3.8)	\(O(\log N)\) + cluster cost · matches the best hand lowering in the lab except on unpredictable dense switches	One IR instruction; the choice is visible in the assembly	None for the front end; the DP lives in LLVM	Every LLVM front end, including Pebble's code generator
L-value/r-value evaluation (places as operands + materialize rule)	Exact source evaluation order (Theorem 11.4.5); conservative copies	\(O(\lvert e \rvert)\) · copies vanish after mem2reg	PIR keeps places visible (`(*_0)[_2]`), so later chapters see every access	Medium (two translation functions, the may-write rule)	Every front end (Clang, javac, rustc MIR, Pebble)
Top-tested loops	Any loop	\(n\) extra jumps per \(n\) iterations	Mirrors the source	Lowest	Front ends' output (Clang, rustc, Pebble)
Rotated loops	Loops with a duplicable header and one latch	saves \(n\) jumps; gives a guaranteed-to-execute preheader	Guard + preheader + bottom test; LCSSA phis	Medium (header copy, SSA repair)	LLVM `loop-rotate`, GCC `ch` at `-O1`/`-O2`, before LICM and vectorization
By value (direct)	Small aggregates; both sides agree on the split	fastest: registers, no memory	Readable IR (fields as values)	Low within one language	rustc's Rust ABI, Swift, LLVM first-class aggregates
`sret`	Any result type	one pointer; callee writes memory directly	Explicit hidden argument	Low	Large results in every C ABI; Pebble's aggregate results
`byval`	Any argument, stack-passed copies	an unavoidable copy per call	Copy hidden in the call lowering	Low in IR; ABI knowledge needed	x86-64 MEMORY-class C arguments
Caller copy + pointer	Any argument	a `memcpy`, removable by the optimizer	Copy visible in IR	Low	AAPCS64 large composites, rustc, Pebble
ABI coercion	Exactly the platform C ABI	as direct	Types look odd (`{ i32, double }`) but match C	High (per-target classifiers)	Clang, rustc and Swift `extern "C"`, any FFI
Trap	Stops at the first failure; no recovery, no cleanups	1 test + predictable branch per check · the optimizer may assume success after the check	Precise location (Pebble) or a bare check kind (UBSan trap); fixed exit status	Lowest	Pebble, Swift, hardened C (`-fsanitize-trap`), Rust `panic=abort`, kernels
Unwind	Recoverable; runs cleanups; crosses frames	0 instructions on the normal path (zero-cost EH) · failure costs a table walk per frame	Panic message + backtrace; handlers can report	High (unwind tables, landing pads, personality)	Rust `panic=unwind`, Go run-time panics, Java/C++ exceptions
Error return	Failure is an ordinary value; caller must handle it	a test per propagation step, even on success	Typed: the compiler forces handling (`Option`, `Result`)	Low in the compiler, verbose in code (`?` helps)	Rust `checked_` and `Result`, Go `(v, err)`, C `__builtin__overflow`, Swift `throws` (in a register)
Zero-cost exception tables	Full unwinding with cleanups and typed catch	0 on the normal path · a throw costs a table walk per frame, microseconds	Tables and CFI make debuggers and profilers able to unwind too	High (CFI, LSDA, personality, runtime)	C++ and Rust on Unix-like systems, Java-to-native, Swift's C++ interop
setjmp/longjmp	The same semantics	register/unregister and a store per call site on the normal path · cheap throws	Needs no CFI	Medium (a lowering pass + small runtime)	Targets without an unwinder; old ARM ABIs; early WebAssembly
Explicit error returns	No cleanups by unwinding (cleanups are ordinary code on the return path); only direct callers see the error	a test per call · throws cost a return per frame	Every throwing call is visible in the source (`try`, `?`)	Low (a register convention or a sum type)	Swift `throws`, Rust `Result`, Go `(v, err)`
Closure conversion	Any function value, including escaping ones	one allocation per closure creation + indirect calls · escape analysis can stack-allocate	Explicit environments; debuggers show captured fields	Medium (FV, records, calling convention for code pointers)	OCaml, Rust/C++/Swift closures, Scheme, JavaScript engines
Lambda lifting	Only non-escaping local functions (or the code part of escaping ones)	no allocation; more arguments per call	First-order code; argument lists grow	Low–medium (a fixed point over the call graph)	javac lambda bodies, Go direct closure calls, GHC late lifting
Runtime library design	Anything expressible in the runtime's language; the ABI contract fixes names, types and `noreturn`	a call per use · fine for I/O and traps, costly for hot arithmetic (then expand inline)	one place to print messages and choose exit statuses (Pebble 101, Rust 101)	Low for a C runtime; high when the runtime has a GC or a scheduler (Go)	Pebble's C runtime, compiler-rt builtins, Rust `std::rt`, Go `runtime`
Object emission and linking	Any target LLVM supports; the system linker handles the platform	emission linear after codegen; link \(O(s + r)\) · link time dominates large builds	linker errors ("undefined reference") name symbols, not source lines	Low with a `TargetMachine` and `cc`; high for an integrated linker	`pebblec`, rustc and Clang (via `cc`/`ld`), Zig and Go (own linkers)