Chapter 9 · LLVM IR in Depth¶

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

The problem¶

Given the textual or binary form of an LLVM module, say precisely what it means: which programs it can express, which texts are valid, what every instruction computes, and which transformations preserve that meaning. Concretely, for any .ll file you should be able to (1) name every construct in it (module, global with linkage and visibility, function, basic block, SSA value, type, terminator, phi, memory operation, GEP, cast, call, attribute, intrinsic, metadata, debug record), (2) decide whether it is well formed and, if not, which verifier rule it breaks, (3) compute what it does, including byte offsets from the data layout, poison propagation and undefined behavior, and (4) decide whether a rewrite of it is a refinement. LLVM IR is the interface between every front end in this course (pebblec lowers PIR to it in Ch 11) and every optimization and back-end chapter after it; the C++ API of Ch 10 manipulates exactly the objects this chapter defines.

What you will be able to do¶

Read any LLVM 23 .ll file and explain each construct: linkage and visibility, types, terminators, phis, GEPs, attributes, intrinsics, metadata and debug records.
Compute a GEP's byte offset and a struct's size and alignment from a data layout string by hand (Algorithm 9.4.4, Theorem 9.4.5), and check yourself with ./course drill gep-offset.
Decide whether a function is well formed and name the violated rule (W1–W7 of Definition 9.3.4), as opt -passes=verify does (./course drill ir-validity).
Evaluate straight-line IR with poison, select and freeze, and say when a branch is undefined behavior (./course drill poison-propagation).
Decide which poison-generating flags a rewritten instruction may keep, and justify it as a refinement (./course drill flags).
Write correct IR by hand: loops with phis, arrays and structs through GEP, switch, varargs calls, overflow intrinsics, invoke, and repairs of broken IR (lab).
Place LLVM IR among GIMPLE, SIL, Rust MIR, Cranelift IR, WebAssembly and PIR, and translate phis to block arguments and back.
Find where LLVM 23 implements each of these (the verifier, the data layout, GEP canonicalization, attribute inference, the bitcode writer) and read it.

Prerequisites: Ch 8 (three-address code, CFGs, SSA as a concept, traversal orders). Dominance (Ch 15) is used only through Definition 9.3.2, which is restated. The commands assume LLVM 23.1.2's bin/ directory first on PATH (clang-23 is clang's name in apt and conda installs; with Homebrew use alias clang-23=$(brew --prefix llvm)/bin/clang).

Notation¶

Shared notation follows the house notation (§1 sets and functions, §3 graphs, §4 dominance, §6 inference rules, §7 IR). In this chapter:

Symbol	Meaning
$M = (\mathit{DL}, \mathit{TT}, \mathcal{T}, \mathcal{G}, \mathcal{F}, \mathcal{A}, \mathcal{C}, \mathcal{M}\!d)$	a module (Definition 9.1.1): data layout, triple, identified types, globals, functions, aliases, comdats, named metadata
$\ell(g)$, $\sigma(g)$	the linkage of a global value, and its strength for linking (Definitions 9.1.2, 9.1.3)
$G_f = (B, E, b_0)$	the CFG of function $f$: blocks, edges from terminators (with multiplicity), entry block
$d \mathrel{\mathrm{dom}} b$, $d \mathrel{\mathrm{sdom}} b$	(strict) dominance in $G_f$, as in NOTATION.md §4; unreachable blocks are dominated by every block
W1–W7	the well-formedness rules of Definition 9.3.4
$\lvert\tau\rvert$	size of type $\tau$ in bits
$\mathrm{store}(\tau)$, $\mathrm{align}(\tau)$, $\mathrm{alloc}(\tau)$	store size, ABI alignment and alloc size in bytes under the module's data layout (Definition 9.2.7, Algorithm 9.2.6)
$\mathrm{off}_S(k)$	byte offset of field $k$ of struct $S$ (Algorithm 9.4.2)
$o_j$, $\Delta$, $A_j$	offset of GEP index $j$, their sum, and the intermediate addresses (Definitions 9.4.3, 9.4.6)
$p \oplus_w \Delta$, $\mathrm{sext}_w$	addition modulo $2^w$ in the low $w$ bits (the index width), sign-extension/truncation to $w$ bits
$e : \mathit{Loc} \to \mathit{Acc}$	a memory effect (Definition 9.5.4), ordered pointwise by $\sqsubseteq$ with join $\sqcup$
$t \preceq t'$	$t'$ is an ancestor-or-self of $t$ in a TBAA type tree (Definition 9.6.2)
$\mathbb{V}_N$, $\mathsf{P}$	integer values of width $N$ plus poison; $\mathsf{P}$ is poison (Definition 9.7.2)
$\mathrm{s}(x)$	the two's-complement signed reading of the bit pattern $x$
$e \Downarrow v$	instruction $e$ evaluates to $v$ (the rules of Definition 9.7.4)
$\mathcal{B}(P, \iota)$	the behaviors of program $P$ on input $\iota$ (Definition 9.7.7)
$S \sqsupseteq T$	$T$ refines $S$: $\mathcal{B}(T, \iota) \subseteq \mathcal{B}(S, \iota)$ for all $\iota$ (Definition 9.7.8). The symbol points from the less defined program to the more defined one, as in the Alive literature; it is unrelated to the dataflow order of NOTATION.md §2.

Technique map¶

Family	Techniques (origin)	Lesson
Modules, globals, functions and SSA values	Module as a persistent, self-contained unit (Lattner 2002; Lattner & Adve 2004); object-file linkage model with ODR linkages, visibility and preemption (ELF/COFF practice; LLVM LangRef); functions as CFGs of basic blocks over SSA values (Cytron et al. 1991; LLVM 2004), slot numbering	9.1
The type system, data layout and target triples	Signless integers `iN`, IEEE/legacy FP, pointers with address spaces, opaque pointers (LLVM 15–17), the byte type `bN` (LLVM 23); arrays, literal vs identified and packed structs; fixed and scalable vectors (2019, Arm SVE); target extension types (LLVM 16), `label`, `token`, `metadata`; data layout strings and target triples (Lattner & Adve 2004)	9.2
Control flow, phi and select, the verifier	Terminators `ret`/`br`/`switch`/`indirectbr`/`invoke`/`callbr`/`resume`/`unreachable` (LLVM; zero-cost EH after Itanium C++ ABI); phi functions (Cytron et al. 1991) and `select`; well-formedness and the SSA dominance property (Cytron et al. 1991; Zhao et al. 2012)	9.3
Memory and addresses	`alloca`/`load`/`store` and promotability; atomics and orderings from the C++11 model (Boehm & Adve 2008; LLVM 3.0), `volatile`; `getelementptr` with `inbounds`/`nusw`/`nuw` (LLVM 19) and byte-offset canonicalization; casts including `ptrtoaddr` (LLVM 22)	9.4
Calls, attributes and intrinsics	Calls and calling conventions, varargs, tail calls; parameter/return/function attributes and memory effects (`memory(…)`, `captures(…)` in LLVM 21), attribute inference over SCCs; intrinsics with type-overloaded names	9.5
Metadata and representation	TBAA (after C's effective-type rule), `!range`/`!noundef`; loop metadata; debug records (LLVM 19); bitcode with VBR encoding and the IR compatibility policy	9.6
Semantics: UB, poison, undef, freeze, refinement	Immediate UB; poison and `freeze` (Lee et al. 2017; LLVM 10); `undef` and its deprecation; poison-generating flags `nsw`/`nuw`/`exact`/`disjoint`/`samesign`/`nneg`; refinement and its automated checking (Lopes et al. 2015, 2021)	9.7
One function in seven IRs	LLVM IR; GIMPLE (Merrill 2003); Swift SIL; Rust MIR; Cranelift IR; WebAssembly (Haas et al. 2017); PIR (this course); phi ⇄ block-argument translation; structured control flow (Ramsey 2022)	9.8

flowchart LR
  M[Module 9.1] --> G[Globals and linkage 9.1]
  M --> F[Functions, blocks, SSA values 9.1]
  M --> DL[Data layout and triple 9.2]
  T[Types 9.2] --> DL
  F --> C[Terminators, phi, select 9.3]
  C --> V[Verifier invariants 9.3]
  DL --> MEM[Memory and GEP 9.4]
  T --> MEM
  F --> CALL[Calls, attributes, intrinsics 9.5]
  MEM --> SEM[Poison, UB, flags, refinement 9.7]
  C --> SEM
  CALL --> SEM
  MD[Metadata, debug records 9.6] -.optional facts.-> SEM
  BC[Bitcode 9.6] -.same module.-> M
  V --> CMP[Seven IRs 9.8]
  SEM --> CMP

Who uses what¶

System	What it does with LLVM IR (or its own IR)	Notes
clang 23	emits LLVM IR for C, C++, Objective-C; lowers the C ABI (`zeroext`, `byval`, varargs); emits TBAA, loop metadata, debug records	every real-world box; 9.4, 9.5, 9.6
rustc 1.94	MIR → LLVM IR; `noalias`/`noundef`/`range` from Rust's type system, no TBAA; checked arithmetic with overflow intrinsics	9.5, 9.8
swiftc 6	SIL (block arguments, ownership) → LLVM IR	9.8
GCC 15	GIMPLE in SSA form instead of LLVM IR; symbol flags instead of linkage enumeration	9.1, 9.8
Cranelift (Wasmtime 37)	CLIF with block parameters, no poison, integer addresses	9.8
LLVM's WebAssembly back end	LLVM IR → structured Wasm (CFG stackification)	9.8
`pebblec`	PIR → LLVM IR in the memory form, then `mem2reg` and the course's passes	9.8, Ch 11
Alive2, `llubi`	refinement checking; UB-aware interpretation of LLVM IR	9.7

Comparison¶

The fixed columns follow docs/authoring/DEPTH_CONTRACT.md §3 item 8; each lesson's §8 has the same rows. $s$ = text size, $g$ = global values, $r$ = references, $v$ = values, $i$ = instructions, $u$ = uses, $f$ = struct fields, $k$ = GEP indices, $h$ = TBAA tree height, $T_{\mathrm{dom}}$ = dominator-tree construction time.

Modules, globals, functions and SSA values (lesson 9.1)

Technique	Power / precision	Speed (asymptotic · practical)	Output / error quality	Implementation effort	Typical use
Module structure	self-contained: layout, triple, types, globals, metadata; linkable and serializable	parse/print $O(s)$; linking $O(g + r)$	textual `.ll` for humans, bitcode for tools	moderate: symbol table, forward references	every LLVM client; LTO links modules
Globals, linkage and visibility	11 linkages × 3 visibilities × `dso_local`: exactly what ELF, Mach-O and COFF can express	$O(1)$ per symbol decision	"symbol multiply defined!" at IR link time	high: must mirror three object formats	C, C++ (ODR), Rust generics, Swift
Globals, linkage and visibility (GCC's flag-based variant)	same facts as independent flags	same	dumps (`-fdump-ipa-cgraph`)	high	GCC's symtab
Functions, basic blocks and SSA values	every register value has one definition; def-use explicit	numbering $\Theta(v)$; RAUW $O(\lvert\mathrm{uses}\rvert)$	verifier checks dominance (Lesson 9.3)	front end may emit memory form and use `mem2reg`	LLVM, GCC (SSA names), V8
Functions, basic blocks and SSA values (block-argument variant)	same information, edges explicit	same	same	simpler edge updates, no phi-entry bookkeeping	MLIR, SIL, Cranelift

Types, data layout and triples (lesson 9.2)

Technique	Power / precision	Speed (asymptotic · practical)	Output / error quality	Implementation effort	Typical use
Integer, byte, floating-point and pointer types	any width `iN`; IEEE + 2 legacy FP formats; `ptr` + address space; `bN` for raw memory	uniqued, $O(1)$ equality	signedness must be read from instructions and ABI attributes	small	every value
Aggregate types: arrays and structs	literal (structural) and identified (nominal) structs, packed, opaque	uniqued; layout $O(f)$ cached	readable names via identified structs	moderate (layout, renaming on link)	memory layout, multi-value returns
Vector types: fixed and scalable	SIMD of fixed or `vscale`-multiple width	sizes as `TypeSize`; scalable comparisons need care	clear lane types	high for scalable (every size query)	vectorizers, SIMD intrinsics
Special types: target extension, label, token, metadata	values the optimizer may pass but not inspect or merge	no cost	verifier states the forbidden operation	small per type	GPUs, EH, coroutines, convergence, debug info
Data layout strings and target triples	exact sizes/alignments without target code in the optimizer	$O(\log s)$ lookup, cached layouts	mismatch refused by the back end	small, but every front end must emit the right string	constant folding of `sizeof`, GEP offsets, alignment

Control flow, phi and select, the verifier (lesson 9.3)

Technique	Power / precision	Speed (asymptotic · practical)	Output / error quality	Implementation effort	Typical use
Terminators	exact CFG, including computed jumps (`indirectbr`), unwinding (`invoke`) and asm goto (`callbr`)	successor lists $O(1)$ per block	explicit edges; `unreachable` enables deletion	moderate; EH adds several instructions	every function; `invoke` for C++/Rust unwinding
Phi and select	phi: merges at joins, one entry per edge; select: branch-free choice that ignores unchosen poison	phi check $O(\text{operands})$; select is one instruction	phi entries must match predecessors exactly	phi bookkeeping on every CFG edit	phis at joins; selects after if-conversion, `cmov`
The verifier's invariants	W1–W7, with the SSA dominance property	$O(i + u + T_{\mathrm{dom}})$	the offending instruction printed with a message	~8 000 lines (`Verifier.cpp`)	parser, `opt`, every pass in debug builds

Memory and addresses (lesson 9.4)

Technique	Power / precision	Speed (asymptotic · practical)	Output / error quality	Implementation effort	Typical use
Alloca, load and store	any memory access with explicit type and alignment; locals as stack objects	$O(1)$ each; `mem2reg`/SROA remove most allocas	memory form is verbose (clang `-O0`) but trivially correct	easiest for front ends	locals before SSA construction, escaping objects
Atomics and volatile	C++11 orderings on individual instructions; volatile for I/O	back end cost: `seq_cst` store = `xchg` on x86-64	orderings visible in the IR text	moderate (per-target expansion)	concurrency (C, C++, Rust), MMIO
GetElementPtr	typed or byte-offset address arithmetic with no-wrap and in-bounds facts	$O(k)$ offset; canonicalization $\le 2k + 3$ pieces	flags make folds provable; poison if violated	the FAQ exists for a reason	every address computation
Casts	explicit, total set of width, float, pointer and bit conversions	$O(1)$	signedness visible as `sext`/`zext`; poison cases documented	small	every type change

Calls, attributes and intrinsics (lesson 9.5)

Technique	Power / precision	Speed (asymptotic · practical)	Output / error quality	Implementation effort	Typical use
Calls and calling conventions	any callee pointer; per-call convention; varargs with caller-chosen types; guaranteed tail calls	$O(1)$ per call in the IR; ABI lowering in front and back ends	mismatches are UB, not errors	high (ABI lowering is the front end's job)	every call; `fastcc` for internal functions
Parameter and function attributes	precise facts per parameter, return and function; memory effects per location kind	uniqued lists, $O(1)$; inference linear per SCC	wrong attributes are UB or poison, silently	moderate (inference), low (use)	ABI (`zeroext`), alias info (`noalias`), IPO facts
Intrinsics	new operations without new instructions; exact semantics; overloading by type	lowered to 1–few machine instructions or libcalls	verifier checks declarations; reader remangles names	low per intrinsic (TableGen)	overflow, bit manipulation, `memcpy`, SIMD, target ops

Metadata and representation (lesson 9.6)

Technique	Power / precision	Speed (asymptotic · practical)	Output / error quality	Implementation effort	Typical use
Semantic metadata: TBAA, range and noundef	TBAA: type-based no-alias under the language's rule; value facts on loads	$O(h)$ per TBAA query, cached	wrong metadata = miscompile, silently	front end must build the tree	C/C++ strict aliasing; `bool`/enum ranges
Loop metadata	per-loop hints and properties, preserved through transformations	$O(1)$ lookup	pragmas visible in the IR	small	`#pragma clang loop`, `mustprogress`
Debug records	source-variable locations without instructions	no effect on instruction iteration	`#dbg_value` in text	large migration, now done	`-g` builds
Bitcode, textual IR and compatibility	same module in two encodings; bitcode read back to 3.0	bitcode: fast, lazy reading; text: slow, readable	`llvm-bcanalyzer` for bitcode, the text for humans	writer/reader + AutoUpgrade	LTO, caches, archives (bitcode); tests, debugging (text)

Semantics: UB, poison, undef, flags, refinement (lesson 9.7)

Technique	Power / precision	Speed (asymptotic · practical)	Output / error quality	Implementation effort	Typical use
Undefined behavior	lets the optimizer assume impossible situations away (null checks, overflow)	free at compile time	silent miscompile of UB programs; `llubi`/sanitizers to detect	low for the compiler, high for users	C/C++ semantics; `unreachable`
Poison and freeze	deferred UB: speculation is safe; `freeze` pins a value	propagation $O(1)$ per instruction	`llubi --verbose` shows poison per value	moderate: every pass must respect `select`/`freeze` rules	flags, speculation, branch↔select
Undef and why it is deprecated	"any value per use": weaker than poison	—	breaks use-duplicating rewrites (Proposition 9.7.14)	high (hard to reason about)	legacy; uninitialized memory
Poison-generating flags	precise per-instruction facts (overflow, exactness, disjointness, sign)	$O(1)$ checks; inference by known bits	flags visible in IR; dropped when unjustified	moderate (must drop on every rewrite)	C signed arithmetic, canonical forms
Refinement	the correctness criterion for all transformations	exponential by enumeration; SMT for all widths	counterexamples	Alive2 or proofs	validating InstCombine rules, drills

One function in seven IRs (lesson 9.8)

Technique	Power / precision	Speed (asymptotic · practical)	Output / error quality	Implementation effort	Typical use
LLVM IR	SSA + phis, poison/UB semantics, GEP, full linkage model	verification $O(i + u + T_{\mathrm{dom}})$; heavy per-instruction objects	readable `.ll`, precise verifier messages	very large ecosystem	clang, rustc, swiftc, most AOT compilers
GIMPLE	SSA names + PHI over C-like types; UB from types	comparable to LLVM	dumps per pass (`-fdump-tree-*`)	tied to GCC	GCC's middle end
Swift SIL	block arguments, Swift types, ownership	linear verification	`-emit-sil`, ownership diagnostics	Swift-specific	Swift's mandatory and performance passes
Rust MIR	typed locals and places, explicit checks and unwinding, borrowck	borrowck may be superlinear	`--emit=mir`, borrow errors	Rust-specific	borrow checking, const eval, Miri
Cranelift IR	SSA + block parameters, wrap-or-trap, integer addresses	fast: built for JIT compile speed	`--emit-clif`, verifier	small, focused	Wasmtime, rustc's Cranelift backend
WebAssembly	stack machine, structured control, validated, sandboxed memory	one-pass linear validation	`.wat`/assembly text	spec-defined	portable distribution, browsers, sandboxes
PIR	MIR-like locals/places/asserts, versioned text	linear verification	`pir-opt`, `pir-run`	small (course)	Pebble front ends → LLVM back end

Lab measurements (reproduce with the commands in SPEC.md, "Measurement"; reference solution, x86-64): the memory-form Collatz loop is 110 bytes at llc -O0 and 77 bytes at llc -O2, the register (phi) form 83 and 43 bytes; after opt -O2 both compile to the same code, because mem2reg turns one into the other (Lesson 9.4, §8).

Route through this chapter¶

Step	What	Techniques	How it is exercised
1	Lesson 9.1	modules, linkage, functions, SSA values	quiz; lab E1
2	Lesson 9.2	types, data layout, triples	drill `gep-offset` (layouts); lab E3
3	Lesson 9.3	terminators, phi/select, verifier	drill `ir-validity`; lab E1, E4, E7, F1–F5
4	Lesson 9.4	memory, atomics, GEP, casts	drill `gep-offset`; lab E2, E3, E9
5	Lesson 9.5	calls, attributes, memory effects, intrinsics	lab E5, E6, E8, F6
6	Lesson 9.6	metadata, debug records, bitcode	quiz; lab stretch goal
7	Lesson 9.7	UB, poison, freeze, undef, flags, refinement	drills `poison-propagation`, `flags`; lab R1 (`-O2`)
8	Lesson 9.8	seven IRs side by side	quiz
9	Exercises and the lab `labs/ch09-ir/`	hand-written IR (E1–E9) and repairs (F1–F7); memory form vs register form, typed GEP vs byte-offset GEP	`./course test 9`
10	Theory test	all	`./course quiz 9` (≥ 80 % to finish)

What Pebble uses. pebblec emits exactly the constructs of Lessons 9.1–9.5 (one module, internal/external functions, i64/i1/double/ptr, arrays and identified structs, the memory form, GEPs with inbounds, overflow intrinsics, calls to the runtime); the lab is where you write them by hand first. Nothing in this chapter is implemented in C++: the C++ API is Ch 10.

Practice and check¶

./course drill gep-offset --difficulty easy            # struct layout and GEP offsets; --solution shows every step
./course drill ir-validity --difficulty medium         # which verifier rule is broken?
./course drill poison-propagation --difficulty medium  # follow poison through select and freeze
./course drill flags --difficulty hard                 # which flags survive a rewrite?
./course flash 9                                       # daily, a few minutes
./course quiz 9                                        # after the lessons
./course test 9                                        # after the lab
./course status                                        # done = quiz ≥ 80 % and tests pass

References¶

The chapter's annotated bibliography (papers, textbook sections, pinned LLVM/GCC/rustc/Swift/Cranelift sources, specifications) is in references.md. Start with: [LLVM-LangRef] (the definition of everything in this chapter), [LA04] (why LLVM IR looks the way it does), [LLVM-GEP] (the GEP FAQ, alongside Lesson 9.4), [LHK+17] (poison, undef and freeze, alongside Lesson 9.7) and [LLM+21] (Alive2 and refinement).

Symbol	Meaning
\(M = (\mathit{DL}, \mathit{TT}, \mathcal{T}, \mathcal{G}, \mathcal{F}, \mathcal{A}, \mathcal{C}, \mathcal{M}\!d)\)	a module (Definition 9.1.1): data layout, triple, identified types, globals, functions, aliases, comdats, named metadata
\(\ell(g)\), \(\sigma(g)\)	the linkage of a global value, and its strength for linking (Definitions 9.1.2, 9.1.3)
\(G_f = (B, E, b_0)\)	the CFG of function \(f\): blocks, edges from terminators (with multiplicity), entry block
\(d \mathrel{\mathrm{dom}} b\), \(d \mathrel{\mathrm{sdom}} b\)	(strict) dominance in \(G_f\), as in NOTATION.md §4; unreachable blocks are dominated by every block
W1–W7	the well-formedness rules of Definition 9.3.4
\(\lvert\tau\rvert\)	size of type \(\tau\) in bits
\(\mathrm{store}(\tau)\), \(\mathrm{align}(\tau)\), \(\mathrm{alloc}(\tau)\)	store size, ABI alignment and alloc size in bytes under the module's data layout (Definition 9.2.7, Algorithm 9.2.6)
\(\mathrm{off}_S(k)\)	byte offset of field \(k\) of struct \(S\) (Algorithm 9.4.2)
\(o_j\), \(\Delta\), \(A_j\)	offset of GEP index \(j\), their sum, and the intermediate addresses (Definitions 9.4.3, 9.4.6)
\(p \oplus_w \Delta\), \(\mathrm{sext}_w\)	addition modulo \(2^w\) in the low \(w\) bits (the index width), sign-extension/truncation to \(w\) bits
\(e : \mathit{Loc} \to \mathit{Acc}\)	a memory effect (Definition 9.5.4), ordered pointwise by \(\sqsubseteq\) with join \(\sqcup\)
\(t \preceq t'\)	\(t'\) is an ancestor-or-self of \(t\) in a TBAA type tree (Definition 9.6.2)
\(\mathbb{V}_N\), \(\mathsf{P}\)	integer values of width \(N\) plus poison; \(\mathsf{P}\) is poison (Definition 9.7.2)
\(\mathrm{s}(x)\)	the two's-complement signed reading of the bit pattern \(x\)
\(e \Downarrow v\)	instruction \(e\) evaluates to \(v\) (the rules of Definition 9.7.4)
\(\mathcal{B}(P, \iota)\)	the behaviors of program \(P\) on input \(\iota\) (Definition 9.7.7)
\(S \sqsupseteq T\)	\(T\) refines \(S\): \(\mathcal{B}(T, \iota) \subseteq \mathcal{B}(S, \iota)\) for all \(\iota\) (Definition 9.7.8). The symbol points from the less defined program to the more defined one, as in the Alive literature; it is unrelated to the dataflow order of NOTATION.md §2.

Technique	Power / precision	Speed (asymptotic · practical)	Output / error quality	Implementation effort	Typical use
Module structure	self-contained: layout, triple, types, globals, metadata; linkable and serializable	parse/print \(O(s)\); linking \(O(g + r)\)	textual `.ll` for humans, bitcode for tools	moderate: symbol table, forward references	every LLVM client; LTO links modules
Globals, linkage and visibility	11 linkages × 3 visibilities × `dso_local`: exactly what ELF, Mach-O and COFF can express	\(O(1)\) per symbol decision	"symbol multiply defined!" at IR link time	high: must mirror three object formats	C, C++ (ODR), Rust generics, Swift
Globals, linkage and visibility (GCC's flag-based variant)	same facts as independent flags	same	dumps (`-fdump-ipa-cgraph`)	high	GCC's symtab
Functions, basic blocks and SSA values	every register value has one definition; def-use explicit	numbering \(\Theta(v)\); RAUW \(O(\lvert\mathrm{uses}\rvert)\)	verifier checks dominance (Lesson 9.3)	front end may emit memory form and use `mem2reg`	LLVM, GCC (SSA names), V8
Functions, basic blocks and SSA values (block-argument variant)	same information, edges explicit	same	same	simpler edge updates, no phi-entry bookkeeping	MLIR, SIL, Cranelift

Technique	Power / precision	Speed (asymptotic · practical)	Output / error quality	Implementation effort	Typical use
Integer, byte, floating-point and pointer types	any width `iN`; IEEE + 2 legacy FP formats; `ptr` + address space; `bN` for raw memory	uniqued, \(O(1)\) equality	signedness must be read from instructions and ABI attributes	small	every value
Aggregate types: arrays and structs	literal (structural) and identified (nominal) structs, packed, opaque	uniqued; layout \(O(f)\) cached	readable names via identified structs	moderate (layout, renaming on link)	memory layout, multi-value returns
Vector types: fixed and scalable	SIMD of fixed or `vscale`-multiple width	sizes as `TypeSize`; scalable comparisons need care	clear lane types	high for scalable (every size query)	vectorizers, SIMD intrinsics
Special types: target extension, label, token, metadata	values the optimizer may pass but not inspect or merge	no cost	verifier states the forbidden operation	small per type	GPUs, EH, coroutines, convergence, debug info
Data layout strings and target triples	exact sizes/alignments without target code in the optimizer	\(O(\log s)\) lookup, cached layouts	mismatch refused by the back end	small, but every front end must emit the right string	constant folding of `sizeof`, GEP offsets, alignment

Technique	Power / precision	Speed (asymptotic · practical)	Output / error quality	Implementation effort	Typical use
Terminators	exact CFG, including computed jumps (`indirectbr`), unwinding (`invoke`) and asm goto (`callbr`)	successor lists \(O(1)\) per block	explicit edges; `unreachable` enables deletion	moderate; EH adds several instructions	every function; `invoke` for C++/Rust unwinding
Phi and select	phi: merges at joins, one entry per edge; select: branch-free choice that ignores unchosen poison	phi check \(O(\text{operands})\); select is one instruction	phi entries must match predecessors exactly	phi bookkeeping on every CFG edit	phis at joins; selects after if-conversion, `cmov`
The verifier's invariants	W1–W7, with the SSA dominance property	\(O(i + u + T_{\mathrm{dom}})\)	the offending instruction printed with a message	~8 000 lines (`Verifier.cpp`)	parser, `opt`, every pass in debug builds

Technique	Power / precision	Speed (asymptotic · practical)	Output / error quality	Implementation effort	Typical use
Alloca, load and store	any memory access with explicit type and alignment; locals as stack objects	\(O(1)\) each; `mem2reg`/SROA remove most allocas	memory form is verbose (clang `-O0`) but trivially correct	easiest for front ends	locals before SSA construction, escaping objects
Atomics and volatile	C++11 orderings on individual instructions; volatile for I/O	back end cost: `seq_cst` store = `xchg` on x86-64	orderings visible in the IR text	moderate (per-target expansion)	concurrency (C, C++, Rust), MMIO
GetElementPtr	typed or byte-offset address arithmetic with no-wrap and in-bounds facts	\(O(k)\) offset; canonicalization \(\le 2k + 3\) pieces	flags make folds provable; poison if violated	the FAQ exists for a reason	every address computation
Casts	explicit, total set of width, float, pointer and bit conversions	\(O(1)\)	signedness visible as `sext`/`zext`; poison cases documented	small	every type change

Technique	Power / precision	Speed (asymptotic · practical)	Output / error quality	Implementation effort	Typical use
Calls and calling conventions	any callee pointer; per-call convention; varargs with caller-chosen types; guaranteed tail calls	\(O(1)\) per call in the IR; ABI lowering in front and back ends	mismatches are UB, not errors	high (ABI lowering is the front end's job)	every call; `fastcc` for internal functions
Parameter and function attributes	precise facts per parameter, return and function; memory effects per location kind	uniqued lists, \(O(1)\); inference linear per SCC	wrong attributes are UB or poison, silently	moderate (inference), low (use)	ABI (`zeroext`), alias info (`noalias`), IPO facts
Intrinsics	new operations without new instructions; exact semantics; overloading by type	lowered to 1–few machine instructions or libcalls	verifier checks declarations; reader remangles names	low per intrinsic (TableGen)	overflow, bit manipulation, `memcpy`, SIMD, target ops

Technique	Power / precision	Speed (asymptotic · practical)	Output / error quality	Implementation effort	Typical use
Semantic metadata: TBAA, range and noundef	TBAA: type-based no-alias under the language's rule; value facts on loads	\(O(h)\) per TBAA query, cached	wrong metadata = miscompile, silently	front end must build the tree	C/C++ strict aliasing; `bool`/enum ranges
Loop metadata	per-loop hints and properties, preserved through transformations	\(O(1)\) lookup	pragmas visible in the IR	small	`#pragma clang loop`, `mustprogress`
Debug records	source-variable locations without instructions	no effect on instruction iteration	`#dbg_value` in text	large migration, now done	`-g` builds
Bitcode, textual IR and compatibility	same module in two encodings; bitcode read back to 3.0	bitcode: fast, lazy reading; text: slow, readable	`llvm-bcanalyzer` for bitcode, the text for humans	writer/reader + AutoUpgrade	LTO, caches, archives (bitcode); tests, debugging (text)

Technique	Power / precision	Speed (asymptotic · practical)	Output / error quality	Implementation effort	Typical use
LLVM IR	SSA + phis, poison/UB semantics, GEP, full linkage model	verification \(O(i + u + T_{\mathrm{dom}})\); heavy per-instruction objects	readable `.ll`, precise verifier messages	very large ecosystem	clang, rustc, swiftc, most AOT compilers
GIMPLE	SSA names + PHI over C-like types; UB from types	comparable to LLVM	dumps per pass (`-fdump-tree-*`)	tied to GCC	GCC's middle end
Swift SIL	block arguments, Swift types, ownership	linear verification	`-emit-sil`, ownership diagnostics	Swift-specific	Swift's mandatory and performance passes
Rust MIR	typed locals and places, explicit checks and unwinding, borrowck	borrowck may be superlinear	`--emit=mir`, borrow errors	Rust-specific	borrow checking, const eval, Miri
Cranelift IR	SSA + block parameters, wrap-or-trap, integer addresses	fast: built for JIT compile speed	`--emit-clif`, verifier	small, focused	Wasmtime, rustc's Cranelift backend
WebAssembly	stack machine, structured control, validated, sandboxed memory	one-pass linear validation	`.wat`/assembly text	spec-defined	portable distribution, browsers, sandboxes
PIR	MIR-like locals/places/asserts, versioned text	linear verification	`pir-opt`, `pir-run`	small (course)	Pebble front ends → LLVM back end