Chapter 10 · The LLVM C++ API

Part 2 · Intermediate Representations & LLVM · about 2 weeks · Previous: Ch 9 · Next: Ch 11

The problem

Chapter 9 defined LLVM IR as a language. This chapter treats it as a C++ data structure that your code creates, inspects, rewrites and runs. The input is a program written against LLVM 23's headers and libraries; the output is IR built in memory, facts read from it, rewrites that keep it valid and meaning-preserving, and native code executed from it. Seven questions decide whether such a program is correct and fast:

• Who owns each object, and what does eraseFromParent free?
• How are the def-use edges kept, and what does replace-all-uses-with (RAUW) do to them?
• Where does IRBuilder put a new instruction, and when does it create none at all?
• How do you test an object's kind cheaply?
• How do you recognize a shape of IR?
• Which containers are fast, and what invalidates your references into them?
• How are errors reported without exceptions, and how is IR executed and LLVM linked?

Every later chapter depends on these answers. The Pebble code generator (Ch 11) is IRBuilder calls, and every pass from Ch 12 on walks and rewrites def-use chains while iterating over instruction lists.

What you will be able to do

• Trace the use lists of a function through RAUW, setOperand and eraseFromParent, predicting the exact order V->uses() visits, and prove that RAUW preserves SSA dominance when the replacement dominates the replaced value.
• Say for any loop over an ilist, a use list, a SmallVector or a DenseMap whether it is safe while mutating, and fix it with make_early_inc_range or a collect-then-mutate pass.
• Build functions with IRBuilder from a specification alone (loops with phis, memory, switch), choosing insertion points and folders deliberately (Lab 10.1).
• Evaluate isa/cast/dyn_cast/_if_present on LLVM's hierarchy, derive classof ranges from a preorder numbering, and explain why dynamic_cast on a Value does not compile.
• Write the same peephole analysis with raw casts, InstVisitor and PatternMatch, and explain where PatternMatch is incomplete (Lab 10.3).
• Place keys in LLVM 23's DenseMap (linear probing, Algorithm R) and in the pre-23 tombstone design, and state what each operation invalidates.
• Classify Error/Expected code as checked or unchecked, and choose between llvm::Expected, exceptions and std::expected.
• Run IR through the interpreter, LLJIT and LLLazyJIT, predict what each compiles and when, and link against LLVM from CMake with the right flags.

Prerequisites: Ch 9 (the IR itself: types, SSA, phis, poison), Ch 0 (interpreters vs JITs), and C++ at the level of templates, RAII and move semantics. Dominance (Ch 15) is used in one proof and is defined there.

How the real-world boxes compile. Each box's programs are in examples/ and compile with

clang++-23 $(llvm-config --cxxflags) -std=c++23 prog.cpp $(llvm-config --ldflags --libs) \
  -Wl,-rpath,$(llvm-config --libdir) -o prog

-std=c++23 must come after --cxxflags, which contains -std=c++17 (Lesson 10.8). The outputs were captured on Linux x86-64 with LLVM 23.1.2 from conda-forge. To run the same commands on your machine:

• macOS with Homebrew (the course's main platform). Put Homebrew's LLVM first on PATH. It installs unversioned drivers, so type clang++ and clang where a box says clang++-23 and clang-23:

  export PATH="$(brew --prefix llvm)/bin:$PATH"     # clang++, llvm-config, lli, opt
  cd chapters/10-llvm-cpp-api/examples
  clang++ $(llvm-config --cxxflags) -std=c++23 uniq.cpp $(llvm-config --ldflags --libs) \
    -Wl,-rpath,$(llvm-config --libdir) -o uniq && ./uniq
  # the ASan boxes (Lessons 10.1 and 10.6): the same line plus the box's sanitizer flags
  clang++ $(llvm-config --cxxflags) -std=c++23 -g -O0 -fsanitize=address erase.cpp \
    $(llvm-config --ldflags --libs) -Wl,-rpath,$(llvm-config --libdir) -o erase && ./erase dce.ll
  

  Homebrew's llvm ships compiler-rt, so -fsanitize=address needs nothing else. Addresses, paths and the frames inside libLLVM differ on macOS. Compare the error kind (heap-use-after-free, stack-use-after-scope), the access size and the frame in main.

• Linux with apt.llvm.org packages (clang-23, llvm-23-dev, libclang-rt-23-dev). clang++-23 exists as written. Put /usr/lib/llvm-23/bin first on PATH so that llvm-config, lli and opt are version 23.

• The course container (conda-forge LLVM in /opt/llvm-23, where these outputs were captured). Add --gcc-install-dir=/usr/lib/gcc/x86_64-linux-gnu/14 to every clang++-23 line (libstdc++ 14). This clang has no sanitizer runtimes. Either install conda-forge's compiler-rt23_linux-64 23.1.2 package into the LLVM prefix, which puts them under $(clang++-23 -print-resource-dir)/lib/linux, or build a resource directory elsewhere and point clang at it:

  RD=$HOME/clang-rd-23; mkdir -p $RD
  cp -r "$(clang++-23 -print-resource-dir)/include" $RD/   # clang's own headers
  # copy lib/clang/23/lib from the unpacked compiler-rt23_linux-64 package to $RD/lib, then add
  #   --gcc-install-dir=/usr/lib/gcc/x86_64-linux-gnu/14 -resource-dir=$RD
  # to the ASan boxes' clang++-23 lines
  

Notation

Shared notation follows the house notation: §1 (sets, functions, logic), §3 (graphs), §4 (dominance, used in Theorem 10.2.13) and §8 (complexity). In this chapter:

Symbol	Meaning
\(\mathrm{own}(o)\), \(\mathrm{sub}(p)\)	owner of an object; the subtree an owner deletes (Definition 10.1.1)
\(\kappa(v)\), \(T_k\)	structural key of a uniqued object; the uniquing table of kind \(k\) (Definition 10.1.3)
\(s\), \(\mathrm{next}(x)\), \(\mathrm{prev}(x)\)	list sentinel and links (Definition 10.1.6)
\(\mathrm{val}(u)\), \(\mathrm{user}(u)\), \(\mathrm{opno}(u)\)	value, user and operand number of a use \(u\) (Definition 10.2.1)
\(\mathrm{uses}(v)\), \(\mathrm{users}(v)\), \(\mathrm{ops}(U)\)	use list of a value (head first), its users, the operand list of a user
user[k]	the use in operand slot \(k\) of user (drills, worked examples)
\((B, p, \eta)\)	insertion point: block, position, head bit (Definition 10.3.1)
\(\phi\), \(\mathrm{dom}(\phi)\)	a folder and the inputs it folds (Definition 10.3.2)
\(\sigma\)	builder state (Definition 10.3.6)
\(C \sqsubseteq D\), \(\mathrm{dyn}(o)\)	subclass relation; dynamic class of an object (Definition 10.4.1)
\(S_D\), \([\mathit{first}_D, \mathit{last}_D]\)	kind numbers classof of \(D\) accepts; their interval (Definition 10.4.2, Theorem 10.4.10)
\(\mathsf{Value}(x)\), \(\mathsf{Deferred}(x)\), \(\mathsf{Bin}_o\), \(\mathsf{cBin}_o\)	pattern constructors (Definition 10.5.1)
\(\rho\), \(\ell \xrightarrow{\theta} r\)	variable bindings; a rewrite rule with side condition (Definitions 10.5.2, 10.5.5)
\(s, c, N\)	size, capacity, inline capacity of a SmallVector (Definition 10.6.1)
\(B\), \(n\), \(\alpha = n/B\), \(\mathrm{home}(k)\)	buckets, entries, load factor, home bucket of a hash table (Definition 10.6.3)
\(\mathrm{u}(a)\), \(\mathrm{s}(a)\), \(w\)	unsigned and signed reading of a \(w\)-bit pattern (Definition 10.6.12)
checked	the must-check bit of Error/Expected (Definition 10.7.2)
\(D\), link order	a JITDylib and its search order (Definition 10.8.4)
\(\overline{C}\)	closure of a set of LLVM components (Definition 10.8.7)
\(I\), \(K\), \(t_i\), \(t_c\)	executed instructions, JIT compile cost, per-instruction times (Proposition 10.8.12)

Numbered statements are N.k.m (chapter, lesson, counter), as in NOTATION.md §9.

Technique map

Family	Techniques (origin)	Lesson
Ownership and IR containers	Context uniquing / hash-consing (Ershov 1958; LLVM, Lattner & Adve 2004), the ownership tree (Lattner 2002), intrusive doubly linked lists with erase vs remove and early-increment iteration (Knuth 1968/1997; LLVM ilist), index-based entity arenas (Cranelift, rustc MIR)	10.1
Values, users, uses	Use lists and def-use chains (LLVM; SSA per Cytron et al. 1991), operand layout: co-allocated vs hung-off (LLVM User), replace-all-uses-with, value handles (WeakVH, WeakTrackingVH, AssertingVH, CallbackVH, …), metadata as value (MetadataAsValue, ValueAsMetadata)	10.2
Building IR	Direct construction with InsertPosition, insertion points and the debug-record head bit (LLVM 19+), folders (ConstantFolder, NoFolder, InstSimplifyFolder, TargetFolder), inserters (default, callback, Clang's CGBuilderInserter), builder state (fast-math, debug locations, constrained FP, guards)	10.3
Casting and dispatch	LLVM-style RTTI (classof, isa/cast/dyn_cast/dyn_cast_if_present, CastInfo), C++ RTTI (dynamic_cast, Itanium ABI; Stroustrup 1994), closed sum types (std::variant/std::visit, P0088 2016), static visitors (InstVisitor; the Visitor pattern, Gamma et al. 1994)	10.4
Pattern matching	Hand-written matching, PatternMatch combinators (m_Add, m_Value, m_Specific, m_Deferred, m_ConstantInt, m_c_*, m_OneUse), declarative rule DSLs (GCC match.pd 2014, GlobalISel TableGen combiner rules, Cranelift ISLE 2021)	10.5
ADTs	SmallVector, DenseMap (LLVM 23: linear probing + Knuth's Algorithm R; ≤ 22: quadratic probing + tombstones), SetVector, StringRef/ArrayRef/Twine, StringMap, BitVector/SparseBitVector, PointerIntPair/PointerUnion, APInt/APFloat (IEEE 754)	10.6
Error handling	Error/Expected with must-check semantics (LLVM 2016), C++ exceptions with zero-cost tables (Itanium ABI), std::expected (P0323, C++23)	10.7
Running IR and consuming LLVM	The IR interpreter (ExecutionEngine, lli -force-interpreter), MCJIT (2013), ORC LLJIT (Hames 2016/2018), ORC LLLazyJIT, llvm-config and LLVMConfig.cmake (dylib vs components, RTTI/EH flags)	10.8

flowchart LR
  CTX[Context uniquing] --> OWN[Ownership tree]
  OWN --> IL[Intrusive lists<br/>erase vs remove]
  ARENA[Index arenas<br/>Cranelift] -.alternative.-> OWN
  OWN --> UL[Use lists<br/>Value/User/Use]
  UL --> RAUW[RAUW]
  UL --> VH[Value handles]
  UL --> MAV[Metadata as value]
  IL --> IRB[IRBuilder<br/>insertion points]
  IRB --> FOLD[Folders]
  IRB --> INS[Inserters]
  RTTI[LLVM-style RTTI] --> VIS[InstVisitor]
  RTTI --> PM[PatternMatch]
  PM -->|scale up| DSL[Rule DSLs<br/>match.pd, GlobalISel, ISLE]
  CXX[C++ RTTI] -.slower alternative.-> RTTI
  VAR[std::variant] -.closed alternative.-> RTTI
  ADT[ADTs: SmallVector, DenseMap, views] --> UL
  ERR[Error/Expected] --> JIT[ORC LLJIT / LLLazyJIT]
  INT[Interpreter] -.slower, no codegen.-> JIT
  MCJIT[MCJIT] -->|superseded by| JIT

Who uses what

System	Technique	Notes
LLVM 23	all of the above; DenseMap switched to linear probing + Algorithm R in 23; BranchInst split into UncondBrInst/CondBrInst	lessons 10.1–10.8
Clang 23	IRBuilder<TargetFolder, CGBuilderInserter>; LLVM-style RTTI on its AST (Stmt::getStmtClass); StringMap<IdentifierInfo *>	10.3, 10.4, 10.6
MLIR (llvm-project 23)	intrusive op lists, use lists (UseDefLists.h), CastInfo for value-type handles, TypeSwitch	10.2, 10.4
Cranelift (Wasmtime 37)	entity arenas + Layout instead of an ownership tree; value aliases instead of use lists; ISLE rules	10.1, 10.2, 10.5
GCC 15	match.pd + genmatch; immediate-use lists for SSA names; auto_vec, sparse bitmap; wide_int	10.2, 10.5, 10.6
rustc 1.90	IndexVec arenas for MIR; SmallVec; FxIndexSet (insertion-ordered)	10.1, 10.6
clang-repl, Julia, PostgreSQL JIT	ORC LLJIT / lazy compilation	10.8

Comparison

The fixed columns follow docs/authoring/DEPTH_CONTRACT.md §3 item 8; each lesson repeats its rows.

Ownership and IR containers (lesson 10.1)

Technique	Power / precision	Speed	Output / error quality	Implementation effort	Typical use
Context uniquing	equality of types/constants is pointer equality (Theorem 10.1.11)	\(O(k)\) expected per get; equality \(O(1)\)	mixing contexts is a hard error (assert/verifier)	a hash table per kind	LLVM types, constants, uniqued metadata
Ownership tree	exact deletion, no leaks (Theorem 10.1.12)	\(O(L)\) teardown	use-after-erase is silent UB without ASan	parent pointers + destructors + dropAllReferences	LLVM, MLIR, GCC's IR
Intrusive lists	\(O(1)\) insert/erase anywhere, stable iterators to other nodes (Lemma 10.1.13)	\(O(1)\) edits; \(O(n)\) size()	erase-while-iterating is UB unless early-inc (Theorem 10.1.14)	small; the traits are the subtle part	instruction, block, function lists
Index-based arenas	no dangling memory (Proposition 10.1.15); stale refs undetected	\(O(1)\) access, 4-byte refs, cache-friendly	stale reference = silent wrong data	arena + layout + secondary maps	Cranelift, rustc MIR, many Rust compilers

Values, users, uses (lesson 10.2)

Technique	Power / precision	Speed	Output / error quality	Implementation effort	Typical use
Use lists	exact def-use chains, always current (Theorem 10.2.11)	\(O(1)\) per operand change; \(O(m)\) to walk	order is unspecified: never depend on it	Use objects + two-pointer links	every LLVM/MLIR/GCC SSA pass
Operand layout	co-allocated: fixed \(k\); hung-off: growable	one allocation vs two; \(O(1)\) access either way	stale Use * after hung-off growth	per-class operand traits	fixed instructions vs phi/switch
RAUW	rewrites all uses at once; dominance-safe under Theorem 10.2.13	\(\Theta(m)\)	verifier catches dominance/type mistakes	one call	folding, CSE, simplification, SSA construction
Value handles	caches survive deletion/RAUW (Proposition 10.2.15)	\(O(1)\) register, \(O(h)\) notify	AssertingVH checks only in assertion builds	pick the right kind	analysis caches, ValueMap
Metadata as value	metadata as operands; values inside metadata that follow RAUW	\(O(1)\) expected	—	two wrapper classes	constrained FP, debug info, type tests

Building IR (lesson 10.3)

Technique	Power / precision	Speed	Output / error quality	Implementation effort	Typical use
Direct construction	full control, no folding	\(O(k)\) per instruction	no help: you set flags, names, locations yourself	verbose	passes rewriting single instructions (Lab 10.2)
Insertion points	exact placement incl. debug-record side (Definition 10.3.1)	\(O(1)\)	wrong point = verifier error, or silently wrong debug info	remember to move it	every emitter
Folders	none / constants / InstSimplify identities (Proposition 10.3.8)	\(O(1)\) / \(O(s)\) / bounded recursion	less IR to clean up; NoFolder gives exact IR for tests	choose a template argument	ConstantFolder default; InstSimplifyFolder in passes; NoFolder in tests
Inserters	a hook per created instruction (Theorem 10.3.9)	\(O(1)\) + callback	—	subclass or lambda	Clang bookkeeping, worklists, instrumentation
Builder state	flags, locations, strict FP applied uniformly	\(O(1)\)	forgotten state is silent (missing !dbg, wrong fast-math)	setters + guards	front ends, FP-sensitive passes

Casting and dispatch (lesson 10.4)

Technique	Power / precision	Speed	Output / error quality	Implementation effort	Typical use
LLVM-style RTTI	single-inheritance hierarchies you control; exact (Theorem 10.4.10)	\(O(1)\), ~1 compare; fastest measured	wrong cast asserts only in debug builds	a kind enum + a classof per class	LLVM, Clang, MLIR, Pebble AST
C++ RTTI	any hierarchy incl. multiple/virtual inheritance, cross-casts	\(O(1)\)–\(O(b)\); 6.7× slower measured	failed cast → null; no per-class code to get wrong	none (compiler-generated)	general C++ code; not LLVM (-fno-rtti)
std::variant + visit	closed sets of value types; exhaustive at compile time (Theorem 10.4.13)	\(O(1)\) switch	a missing case is a compile error	small; clumsy for deep hierarchies	small ASTs, tokens, results
InstVisitor	per-opcode dispatch with class-level fallbacks (Theorem 10.4.14)	\(O(1)\) switch, delegation inlined	an unhandled case silently reaches the fallback	a class with overrides	interpreters, analyses over all instructions, Lab 10.3

Pattern matching (lesson 10.5)

Technique	Power / precision	Speed	Output / error quality	Implementation effort	Typical use
Hand-written	anything, including searches the others cannot express	fastest when structured as a switch (2.3 ms in Lab 10.3)	commuted cases are easy to forget	high; verbose	expression-tree passes (Reassociate), one-off checks
PatternMatch	sound (Theorem 10.5.6); complete when no m_Deferred depends on an inner m_c_ choice (Theorem 10.5.7)	\(O(\lvert P \rvert)\) per pattern, but patterns run one after another (11.5 ms in Lab 10.3)	compile errors are template-heavy; patterns read like the math	low per rule	InstCombine, InstSimplify, most modern LLVM peepholes
Rule DSL	declarative; alternatives explicit; verifiable as data	decision tree shared by all rules	the generator checks well-formedness (and, in ISLE, overlaps)	a generator to build and maintain	GlobalISel combiners, GCC match.pd, Cranelift ISLE

ADTs (lesson 10.6)

Technique	Power / precision	Speed	Output / error quality	Implementation effort	Typical use
SmallVector	a vector; inline up to \(N\)	amortized \(O(1)\), no allocation while \(\le N\)	growth invalidates everything	drop-in for std::vector	operand lists, worklists, temporary buffers
DenseMap	hash map for small, trivially copyable keys	expected \(O(1)\); \(< 2.5\) probes on success at \(\alpha < 3/4\)	LLVM 23: erase moves entries; iteration order is unspecified	provide DenseMapInfo for new key types	pointer-keyed side tables everywhere
SetVector	set with insertion-order iteration	\(O(1)\) expected insert/find, \(O(n)\) remove	deterministic output (Theorem 10.6.17)	none	worklists, ordered uniquing
StringRef/ArrayRef/Twine	free string/array parameters; lazy concatenation	\(O(1)\) to pass	dangling views are silent without ASan	discipline, not code	API parameters, names
StringMap	string-keyed map with stable keys	expected \(O(\lvert k \rvert)\)	keys stable (Proposition 10.6.19)	none	symbol tables, name interning
Bit sets	exact sets over integer universes	dense: \(O(U/64)\) ops; sparse: \(O(\#\text{elements})\)	—	none	dataflow (dense), points-to (sparse)
Pointer packing	a pointer plus \(\le a\) bits in one word	\(O(1)\)	wrong alignment assumptions assert	a traits specialization for new types	tagged pointers, QualType, PointerUnion operands
APInt/APFloat	exact integer and IEEE semantics at any width	\(O(w/64)\)–\(O((w/64)^2)\)	host-independent results	none	constant folding, known bits, ranges

Error handling (lesson 10.7)

Technique	Power / precision	Speed	Output / error quality	Implementation effort	Typical use
Error/Expected	typed, composable payloads; handler dispatch by type	one test per call; cheap failures	unhandled errors abort in checking builds (Theorem 10.7.8)	verbose (takeError, handlers)	LLVM libraries, tools, ORC, object/bitcode readers
C++ exceptions	non-local, cannot be ignored, automatic cleanup	free success path, very expensive throws	uncaught → std::terminate with a message	least code at call sites	general C++ outside LLVM
std::expected	value-or-error, monadic composition	one test per call	ignoring an error is not detected (only [[nodiscard]])	standard, concise	Pebble's APIs, modern C++ libraries

Running IR and consuming LLVM (lesson 10.8)

Technique	Power / precision	Speed	Output / error quality	Implementation effort	Typical use
Interpreter	IR semantics; few intrinsics, limited external calls	instant start; ~30–60× slower (measured)	unsupported features abort (report_fatal_error)	EngineBuilder + runFunction	quick checks of tiny functions, short runs below the crossover
MCJIT	full codegen; whole modules	codegen of whole modules at the first lookup	ExecutionEngine string errors	EngineBuilder	legacy code; superseded
ORC LLJIT	full codegen; JITDylibs, link order, concurrency, remote execution	per-module codegen at first lookup	Error/Expected everywhere	LLJITBuilder, ThreadSafeModule, lookup	test harnesses (Lab 10.1), REPLs, embedding
ORC LLLazyJIT	as LLJIT, compiling only executed functions (Theorem 10.8.10)	stubs up front; codegen on first call	as LLJIT	LLLazyJITBuilder, addLazyIRModule	large modules where little code runs
CMake integration	shared or static linking with the right flags	shared: fast links	configure-time errors are clear; flag mismatches are link errors	find_package + four lines	every out-of-tree LLVM client

Comparison-lab results (reproduce with build/<preset>/bin/ch10-apibench after ./course test 10 --solution):

• findPatterns over the corpus, 2 000 rounds: raw casts 2.3 ms, InstVisitor 2.9 ms, PatternMatch 11.5 ms.
• fib(1000000): interpreter 412.8 ms, LLJIT 13.3 ms.
• fibrec(24): interpreter 109.8 ms, LLJIT 12.1 ms.
• collatz(837799): interpreter 0.7 ms, LLJIT 12.0 ms.

Route through this chapter

Step	What	Techniques	How it is exercised
1	Lesson 10.1	uniquing, ownership tree, ilists, arenas	drill iterator-invalidation; quiz; flashcards
2	Lesson 10.2	use lists, operand layout, RAUW, handles, metadata as value	drill use-lists; quiz
3	Lesson 10.3	construction, insertion points, folders, inserters, state	drill irbuilder-fold; Lab 10.1
4	Lesson 10.4	LLVM RTTI, C++ RTTI, variant, InstVisitor	drill cast-semantics
5	Lesson 10.5	hand-written, PatternMatch, rule DSLs	drill pattern-match; Lab 10.3 (three styles)
6	Lesson 10.6	the ADTs	drills densemap-probe, adt-costs, view-lifetime; Lab 10.2
7	Lesson 10.7	Error/Expected, exceptions, std::expected	drill must-check; Labs 10.2–10.3 error paths
8	Lesson 10.8	interpreter, MCJIT, LLJIT, LLLazyJIT, CMake	drill jit-compile-set; Lab 10.3 (two engines)
9	Exercises	Labs 10.1–10.3	./course test 10
10	Theory test	all	./course quiz 10 (≥ 80 % to finish)

This chapter adds no Pebble compiler component. Its labs are standalone (labs/ch10-*), and the APIs they teach are the ones Ch 11 and every pass chapter use.

Practice and check

./course drill use-lists --difficulty easy      # warm up; --solution shows every step
./course drill densemap-probe --difficulty hard  # the LLVM 22 tombstone design
./course flash 10                                # daily, a few minutes
./course quiz 10                                 # after the lessons
./course test 10                                 # after the labs
./course status

References

The chapter's annotated bibliography (papers, textbook sections, pinned source files, docs and talks) is in references.md. Start with [LLVM-PM] (the Programmer's Manual, the chapter's backbone), [LLVM-IRB] and [LLVM-Casting] (the two headers you will read most), [LLVM-DenseMap] with [TAOCP3] (LLVM 23's hash table and its source), and [LLVM-ORC] (the JIT).