Lesson 10.1 — Ownership and IR containers¶

Techniques: context uniquing (hash-consing), the ownership tree, intrusive lists (ilist) with erase vs remove and the iteration idioms, index-based arenas (the Cranelift/rustc alternative) · Pebble uses: the first three; every lab of the chapter creates, links and deletes IR through them · Lab: Lab 10.1 (building), Lab 10.2 (rewriting while iterating) · Prerequisites: Ch 9 (modules, functions, blocks, SSA values) · Time: 3–4 hours

Here is the chapter's running example, the function every lesson of Chapter 10 builds, inspects or rewrites:

define i32 @f(i32 %x, i32 %y) {
entry:
  %a = add i32 %x, %y
  %b = mul i32 %a, %a
  %c = sub i32 %b, %a
  %d = xor i32 %x, %c
  ret i32 %d
}

In memory there is one Module holding one Function, which holds two Arguments and one BasicBlock. The block holds five Instructions, and the type i32 exists exactly once, owned by the LLVMContext. When you call %b->eraseFromParent(), what gets freed, and what happens to the loop that was walking the block? When you ask for i32 a second time, do you get a new object? This lesson answers those questions. The next one follows the arrows between the objects (the uses).

1. Problem and motivation¶

A compiler's IR is millions of small, heavily cross-linked objects that are created and destroyed constantly, often while an optimization is walking over them. An IR library therefore has to fix three things up front:

Identity: when two objects denote the same type or constant, is that the same object?
Lifetime: who deletes what, and when?
Containers: how are instructions kept in order so that insertion and deletion in the middle are cheap and do not disturb a walk in progress?

LLVM answers with a context that hash-conses every type and constant, a strict ownership tree from Module down to Instruction, and intrusive doubly linked lists [LA04, Lat11, LLVM-PM]. Cranelift and rustc's MIR answer differently: they keep all entities in index-addressed arenas [CL-Entity]. Pebble's code generator (Ch 11) and every pass from Ch 12 on rely on these guarantees.

Context uniquing¶

The idea of storing each distinct expression once and referring to it by address goes back to Ershov's hashing of arithmetic expressions [Ers58]; in Lisp systems it is called hash-consing. LLVM applies it to every type and every constant: IntegerType::get(Ctx, 32) returns the same pointer every time, so type equality is pointer equality. The LLVMContext owns the uniquing tables, so two contexts share nothing, and that is what makes one-context-per-thread compilation safe [LLVM-PM].

Ownership tree¶

The objects that make up the program (globals, functions, arguments, blocks and instructions) form a tree. A Module owns its functions and globals, a Function owns its arguments and blocks, and a BasicBlock owns its instructions [LLVM-PM, Lat02]. Client code holds exactly one owning pointer, the std::unique_ptr<Module>. Everything below it is created into its parent (Function::Create(…, M), BasicBlock::Create(Ctx, "entry", F)) and deleted by its parent. Understanding this tree tells you what eraseFromParent frees, and why deleting a module needs a "drop all references" phase first.

Intrusive lists¶

The instructions of a block, the blocks of a function and the functions of a module are kept in intrusive doubly linked lists: the prev/next pointers live inside the element [TAOCP1, LLVM-PM]. From an Instruction * you can unlink it, erase it, or insert before it in $O(1)$ without searching, and erasing one element never moves another. The price is that a list does not know its length ($O(n)$ size()), and that deleting the element an iterator points to invalidates that iterator. That second fact is the source of the most common LLVM bug of all, deleting while iterating.

Index-based arenas¶

The alternative is to keep entities in growable arrays and refer to them by 32-bit indices. Cranelift's DataFlowGraph stores instructions in a PrimaryMap<Inst, InstructionData> and keeps program order in a separate Layout [CL-Entity, CL-DFG]. rustc's MIR does the same with IndexVec. Indices are half the size of pointers, serializable, and never dangle into freed memory. Their weaknesses are that a stale index silently refers to whatever now occupies the slot, and that every access needs the arena at hand.

2. Definitions and algorithms¶

Definition 10.1.1 (Ownership relation, ownership forest)

Let $O$ be the set of live objects of a program's IR. An ownership relation is a partial function $\mathrm{own} : O \rightharpoonup O$, where $\mathrm{own}(o) = p$ means that $p$ is responsible for deleting $o$. The objects on which $\mathrm{own}$ is undefined are the roots. $\mathrm{own}$ is an ownership forest if following it from any object reaches a root after finitely many steps (no cycles). The subtree $\mathrm{sub}(p)$ is $p$ together with every $o$ such that $\mathrm{own}^{k}(o) = p$ for some $k \ge 1$.

Definition 10.1.2 (LLVM's ownership)

In LLVM 23:

The roots are LLVMContext objects and the Modules held by client unique_ptrs.
$\mathrm{own}(t) = $ the context, for every type $t$, every constant and every uniqued metadata node.
$\mathrm{own}(F) = M$ and $\mathrm{own}(G) = M$ for the functions and globals in module $M$'s lists.
$\mathrm{own}(a) = F$ and $\mathrm{own}(B) = F$ for $F$'s arguments and blocks.
$\mathrm{own}(I) = B$ for every instruction $I$ linked into block $B$.

An instruction that has been unlinked with removeFromParent (or created without an insertion point) is a root owned by the client code until it is inserted again or deleted.

The running example's tree

unique_ptr<Module> → @f → {%x, %y, entry} and entry → {%a, %b, %c, %d, ret}. The type i32 and the context-owned constants hang off the context, not the tree. The use edges (%b uses %a twice) are not ownership. They form a graph that may even be cyclic, because a phi in a loop can use itself.

Context uniquing¶

Definition 10.1.3 (Structural key, uniquing table)

A structural key of a type or constant $v$ is the tuple $\kappa(v)$ of its kind and the addresses of its components. For example, $\kappa(\texttt{i32}) = (\mathit{Integer}, 32)$, $\kappa(\texttt{ptr}) = (\mathit{Pointer}, \mathit{addrspace})$, $\kappa(\{\,t_1, t_2\,\}) = (\mathit{AnonStruct}, \&t_1, \&t_2, \mathit{packed})$ and $\kappa(\texttt{i32 42}) = (\mathit{ConstantInt}, 32, 42)$. A context keeps one uniquing table $T_k$ per kind, a finite map from keys to objects.

Algorithm 10.1.4 (Get-or-create a uniqued object)

Input: a context $C$ and the components of a would-be object $v$ (all of them already uniqued in $C$).
Output: the unique object of $C$ with key $\kappa(v)$.
Precondition: every component belongs to $C$.
Postcondition: $T_k$ maps $\kappa(v)$ to the returned object, and no two entries of $T_k$ map to objects with equal keys.
Invariant: $T_k$ is injective on keys, and every object of kind $k$ in $C$ is the image of its own key.

function GetOrCreate(C, k, components):
    key ← (k, components)                  # components are pointers or integers
    if key ∈ C.T[k]:
        return C.T[k][key]                  # the existing object
    obj ← new object of kind k built from components, owned by C
    C.T[k][key] ← obj
    return obj

LLVM: IntegerType::get looks up LLVMContextImpl::IntegerTypes (a DenseMap<unsigned, IntegerType *>), and ConstantInt::get looks up IntConstants, a DenseMap<APInt, unique_ptr<ConstantInt>> with separate slots for 0 and 1 [LLVM-CtxImpl].

Uniquing: one object per type or constant per context

Reproduce (clang 23.1.2, LLVM 23.1.2, Linux x86-64; llvm-config from the same install):

cd chapters/10-llvm-cpp-api/examples
clang++-23 $(llvm-config --cxxflags) -std=c++23 uniq.cpp $(llvm-config --ldflags --libs) \
  -Wl,-rpath,$(llvm-config --libdir) -o uniq && ./uniq

Output (complete):

i32 in A twice, same pointer:   1
i32 in A vs i32 in B:           0
i32 42 twice, same pointer:     1
{ i32 42, i1 true } twice:      1
C1 has a use list:              0
S1 has a use list:              1

What to notice: equal keys give the same pointer within a context (Theorem 10.1.11), and never across contexts. The last two lines are an LLVM 23 detail you meet again in Lesson 10.2: ConstantInt and the other ConstantData subclasses keep no use list (hasUseList() is false), because the millions of uses of i32 0 were a scalability and threading hazard. A ConstantStruct still has one.

Ownership tree¶

Algorithm 10.1.5 (Delete a module)

Input: a module $M$ (a root of Definition 10.1.2).
Output: none. Every object of $\mathrm{sub}(M)$ is deleted exactly once.
Precondition: no object outside $\mathrm{sub}(M)$ uses a value in $\mathrm{sub}(M)$ (functions are not referenced from another module).
Postcondition: every object of $\mathrm{sub}(M)$ has been freed, and no surviving Use points to freed memory.
Invariant: after phase 1, no operand of any object in $\mathrm{sub}(M)$ refers to a value in $\mathrm{sub}(M)$.

function DeleteModule(M):
    # phase 1: dropAllReferences — cut every use edge inside the tree
    for F in M.functions:
        for B in F.blocks:
            for I in B.instructions:
                for each operand slot u of I:
                    SetOperand(u, null)          # unlinks u from its value's use list
    for G in M.globals: clear G's initializer operand
    # phase 2: delete the ownership tree bottom-up
    for F in M.functions:
        for B in F.blocks:
            for I in B.instructions: delete I
            delete B
        delete F.arguments; delete F
    delete the globals; delete M

LLVM: Module::~Module calls dropAllReferences() and then clears its function, global, alias and ifunc lists. Function::~Function calls dropAllReferences() with the comment "After this it is safe to delete instructions" [LLVM-Module, LLVM-Function].

remove vs erase, and destruction by the root

Reproduce (clang 23.1.2, LLVM 23.1.2, Linux x86-64):

cd chapters/10-llvm-cpp-api/examples
clang++-23 $(llvm-config --cxxflags) -std=c++23 own.cpp $(llvm-config --ldflags --libs) \
  -Wl,-rpath,$(llvm-config --libdir) -o own && ./own

The program builds @f with %sum = add and a dead %dead = mul in entry, then calls Sum->removeFromParent(), Sum->insertInto(Exit, Exit->begin()) and Dead->eraseFromParent().

Output (complete):

after remove: parent is null? 1
blocks=2 insts(entry)=1 insts(exit)=2
verifier: ok
; ModuleID = 'own'
source_filename = "own"

define i32 @f(i32 %0, i32 %1) {
entry:
  br label %exit

exit:                                             ; preds = %entry
  %sum = add i32 %0, %1
  ret i32 %sum
}

What to notice: removeFromParent unlinks without deleting: the object survives with a null parent, owned by the caller (Definition 10.1.2), and its uses are intact, which is why re-inserting it keeps ret i32 %sum valid. eraseFromParent unlinks and deletes. Nothing in main frees anything explicitly: the unique_ptr<Module> does it at the closing brace (Algorithm 10.1.5).

Intrusive lists¶

Definition 10.1.6 (Intrusive doubly linked list with sentinel)

An intrusive list is a sentinel node $s$ together with a set of element nodes $X$. Every node $x \in X \cup \{s\}$ carries $\mathrm{next}(x)$ and $\mathrm{prev}(x)$. The list is well formed when:

following $\mathrm{next}$ from $s$ visits every element of $X$ exactly once and returns to $s$;
$\mathrm{prev}(\mathrm{next}(x)) = x$ for every node $x$.

The order of the list is the sequence of elements visited. An iterator is a pointer to a node, and end() is $s$. A node is linked when it is in some $X$ and unlinked otherwise. LLVM's ilist_node stores the two links (and, for instructions, a parent pointer) inside each Instruction, BasicBlock, Function and GlobalVariable [LLVM-ilist].

Algorithm 10.1.7 (Insert, remove, erase on an intrusive list)

Input: a well-formed list, a node $n$, a position $p$ (a linked node or $s$).
Output: the modified list; erase also frees $n$ and returns the iterator to its successor.
Precondition: insert: $n$ is unlinked. remove/erase: $n \in X$.
Postcondition: the list is well formed. insert(p, n) puts $n$ immediately before $p$, remove(n) deletes $n$ from the order, and every other element keeps its relative order.
Invariant: only $n$ and its (at most two) neighbours have their links changed.

function Insert(p, n):                     # before p
    q ← prev(p)
    next(q) ← n; prev(n) ← q
    next(n) ← p; prev(p) ← n
function Remove(n):                        # unlink; n stays alive
    q ← prev(n); r ← next(n)
    next(q) ← r; prev(r) ← q
    prev(n) ← null; next(n) ← null        # (LLVM clears the links)
    return n
function Erase(n):                         # unlink and delete
    r ← next(n)
    Remove(n)
    delete n                               # the node's memory is freed
    return r

Algorithm 10.1.8 (Early-increment iteration)

Input: a list $L$ and a body $\beta$ that may erase the element it is given.
Output: $\beta$ has been applied to elements of $L$.
Precondition: $\beta(x)$ does not erase or move any element other than $x$.
Postcondition: $\beta$ ran exactly once on each element that was in $L$ at the start, in order, except for elements inserted during the loop (visited if and only if they were inserted after the current position).
Invariant: at the start of each iteration, $\mathit{it}$ points to a linked node or to $s$, and every element before $\mathit{it}$ has been processed.

function ForEachEarlyInc(L, β):
    it ← next(s)
    while it ≠ s:
        x ← it
        it ← next(it)          # advance BEFORE running the body
        β(x)                   # may erase x: `it` does not point to x

This is make_early_inc_range (llvm/ADT/STLExtras.h): its operator* returns *I++, so the wrapped iterator has already moved on when the body sees the element [LLVM-STLExtras].

The idioms you will use daily are range-based for loops over these containers:

for (BasicBlock &BB : F) and for (Instruction &I : BB) walk the lists; instructions(F) (llvm/IR/InstIterator.h) flattens both levels.
reverse(BB) walks a block backwards.
predecessors(BB) and successors(BB) walk the CFG edges, which come from the terminator's operands and from the uses of BB.
users() and uses() walk the def-use chains of Lesson 10.2.

Each of them is a view over a container: the invalidation rules that follow apply to all of them.

Deleting while iterating, under AddressSanitizer

Reproduce (clang 23.1.2 with compiler-rt 23.1.2, LLVM 23.1.2, Linux x86-64):

cd chapters/10-llvm-cpp-api/examples
clang++-23 $(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 --safe      # for (Instruction &I : make_early_inc_range(BB)) ...
./erase dce.ll             # for (Instruction &I : BB) ...   (erases I inside the loop)

Output (abridged: the stack below frame #3 and the allocation stack are cut; paths shortened to …/):

; ModuleID = 'dce.ll'
source_filename = "dce.ll"

define i32 @f(i32 %x) {
entry:
  ret i32 %x
}
=================================================================
==ERROR: AddressSanitizer: heap-use-after-free on address 0x7bf1ac5e44e0 …
READ of size 8 at 0x7bf1ac5e44e0 thread T0
    #0 … in llvm::ilist_detail::node_base_prevnext<llvm::ilist_node_base<false, llvm::BasicBlock>, false>::getNext() const …/include/llvm/ADT/ilist_node_base.h:28:38
    #1 … in llvm::ilist_node_impl<…>::getNext() …/include/llvm/ADT/ilist_node.h:108:59
    #2 … in llvm::ilist_iterator_w_bits<…>::operator++() …/include/llvm/ADT/ilist_iterator.h:345:57
    #3 … in main …/examples/erase.cpp:17:27
0x7bf1ac5e44e0 is located 96 bytes inside of 136-byte region [0x7bf1ac5e4480,0x7bf1ac5e4508)
freed by thread T0 here:
    #0 … in operator delete(void*) …/compiler-rt/lib/asan/asan_new_delete.cpp:176:44
    #1 … in llvm::Instruction::eraseFromParent() (…/libLLVM.so.23.1+0xd8966c)

What to notice: the safe loop deletes the three dead instructions. The naive loop crashes in ilist_iterator::operator++, which reads the next pointer 96 bytes inside the 136-byte Instruction that eraseFromParent just freed: the intrusive links live inside the element (Definition 10.1.6). Without ASan the same program usually "works", because freed memory often still holds the old links. That is why this bug survives code review.

Index-based arenas¶

Definition 10.1.9 (Entity arena)

An arena of kind $K$ is a vector $A_K = \langle d_0, d_1, \dots \rangle$ of entity data. An entity reference is an index $i \in \mathbb{N}$ wrapped in a type specific to $K$ (Cranelift's Inst, Value, Block: a u32). Program order is a separate structure (Cranelift's Layout: a doubly linked list of indices with the links in secondary arrays). Secondary information is a secondary map: a vector indexed by the same references, where unknown indices map to a default.

Algorithm 10.1.10 (Arena allocation and layout insertion)

Input: an arena $A$, a layout (arrays $\mathrm{next}[\,]$, $\mathrm{prev}[\,]$ indexed by reference), entity data $d$, a position $p$.
Output: a fresh reference $i$ placed before $p$ in the layout.
Precondition: $p$ is in the layout (or is the block's end marker).
Postcondition: $A[i] = d$, $i = \lvert A \rvert - 1$, the layout is well formed (Definition 10.1.6 with indices for pointers), and no other reference changed meaning.
Invariant: references are never reused while the function exists, so a reference to a removed entity still names the (now unlinked) data, never a different entity.

function MakeInst(A, d):
    A.push(d)                   # amortized O(1); may reallocate A's buffer
    return |A| − 1
function InsertInst(layout, i, p):
    q ← layout.prev[p]
    layout.next[q] ← i; layout.prev[i] ← q
    layout.next[i] ← p; layout.prev[p] ← i

Cranelift keeps instructions in arenas, not linked objects

Reproduce (Cranelift in Wasmtime v37.0.2 source; curl and grep):

curl -s https://raw.githubusercontent.com/bytecodealliance/wasmtime/v37.0.2/cranelift/codegen/src/ir/dfg.rs \
  | grep -n "pub struct DataFlowGraph" -A 21 | grep -v -- "-\s*$"

Output (the first fields of the struct):

111:pub struct DataFlowGraph {
112-    /// Data about all of the instructions in the function, including opcodes and operands.
113-    /// The instructions in this map are not in program order. That is tracked by `Layout`, along
114-    /// with the block containing each instruction.
115-    pub insts: Insts,
117-    /// List of result values for each instruction.
118-    ///
119-    /// This map gets resized automatically by `make_inst()` so it is always in sync with the
120-    /// primary `insts` map.
121-    results: SecondaryMap<Inst, ValueList>,
123-    /// User-defined stack maps.
124-    user_stack_maps: alloc::collections::BTreeMap<Inst, UserStackMapEntryVec>,
126-    /// basic blocks in the function and their parameters.
127-    ///
128-    /// This map is not in program order. That is handled by `Layout`, and so is the sequence of
129-    /// instructions contained in each block.
130-    pub blocks: Blocks,

What to notice: the instructions live in a primary map indexed by Inst, their results in a SecondaryMap keyed by the same index, and program order is kept elsewhere (Layout). That is Definition 10.1.9 and Algorithm 10.1.10 in production. Instructions are not objects with owners: the whole function is one arena.

3. Worked example¶

We delete the dead instructions of

define i32 @g(i32 %x) {
entry:
  %a = add i32 %x, 1      ; dead
  %b = mul i32 %x, 2      ; dead
  %c = sub i32 %x, 3      ; dead
  ret i32 %x
}

(examples/dce.ll) with the two loops of the ASan box. The nodes are $s$ (sentinel), $A$, $B$, $C$, $R$ (the ret). Initially $\mathrm{next} = \{s \mapsto A, A \mapsto B, B \mapsto C, C \mapsto R, R \mapsto s\}$.

flowchart LR
  S([s]) --> A[A: %a] --> B[B: %b] --> C[C: %c] --> R[R: ret] --> S

Context uniquing¶

Building @g with an IRBuilder asks for i32 four times (the return type, the argument type, and once per constant) and for the constants i32 1, i32 2, i32 3. Algorithm 10.1.4 on the table $T_{\mathit{Int}}$ (width → type) and $T_{\mathit{CInt}}$ (value → constant):

step	request	key	table hit?	tables after
1	`getInt32Ty` (return type)	$(\mathit{Int}, 32)$	no → create $t$	$T_{\mathit{Int}} = \{32 \mapsto t\}$
2	`getInt32Ty` (argument)	$(\mathit{Int}, 32)$	yes → $t$	unchanged
3	`getInt32(1)`	$(\mathit{CInt}, 32, 1)$	no → create $c_1$ (the "one" slot)	$T_{\mathit{CInt}} = \{1 \mapsto c_1\}$
4	`getInt32(2)`	$(\mathit{CInt}, 32, 2)$	no → create $c_2$	$+\{2 \mapsto c_2\}$
5	`getInt32(3)`	$(\mathit{CInt}, 32, 3)$	no → create $c_3$	$+\{3 \mapsto c_3\}$
6	`getInt32(1)` again (e.g. from a later pass)	$(\mathit{CInt}, 32, 1)$	yes → $c_1$	unchanged

Ownership tree¶

Erasing $A$ (Algorithm 10.1.7 Erase) removes one leaf of the tree Module → @g → entry → {A, B, C, R}. Its operand uses (of %x) are unlinked by its destructor. Nothing else is freed, and the module destructor later frees $B$, $C$, $R$, entry, @g exactly once (Theorem 10.1.12).

Intrusive lists¶

Naive loop for (Instruction &I : BB) if (dead(I)) I.eraseFromParent();. The range-for keeps an iterator it, runs the body on *it, then does it ← next(it).

step	`it` before body	body	links changed	`it ← next(it)` reads
1	$A$	erase $A$: $\mathrm{next}(s) \leftarrow B$, $\mathrm{prev}(B) \leftarrow s$, free $A$	$s$, $B$	$\mathrm{next}(A)$: freed memory

The iteration is over at step 1 as far as correctness goes: what it reads next is whatever the allocator left in $A$'s memory (ASan stops here).

Early-increment loop for (Instruction &I : make_early_inc_range(BB)) … (Algorithm 10.1.8):

step	`x`	`it` after advance	body	list after
1	$A$	$B$	erase $A$	$s, B, C, R$
2	$B$	$C$	erase $B$	$s, C, R$
3	$C$	$R$	erase $C$	$s, R$
4	$R$	$s$	`ret` is a terminator: keep	$s, R$
5	—	$\mathit{it} = s$: stop	—	final: `ret i32 %x`

Index-based arenas¶

The same deletion in an arena (Algorithm 10.1.10): the arena is $\langle A, B, C, R \rangle$ with references 0–3, and the layout is $0 \to 1 \to 2 \to 3$. Removing reference 0 from the layout sets $\mathrm{first} \leftarrow 1$. The data $A[0]$ stays in the arena (Cranelift never shrinks it during a function), so a loop that saved reference 0 still reads valid but stale data instead of freed memory. It cannot crash, and it cannot notice either.

Try it

./course drill iterator-invalidation --seed 2 --difficulty easy gives four loops like these to classify; --solution explains each verdict.

4. Invariants and correctness¶

Context uniquing¶

Theorem 10.1.11 (Pointer equality is structural equality)

If every uniqued object of a context $C$ is created only through Algorithm 10.1.4, then for all uniqued objects $u, v$ of $C$: $u = v$ (same address) $\iff$ $\kappa(u) = \kappa(v)$.

Proof

($\Rightarrow$) One object has one key. ($\Leftarrow$) By the invariant of Algorithm 10.1.4, $T_k$ is injective and every object of kind $k$ is the image of its own key. If $\kappa(u) = \kappa(v)$, then $u$ and $v$ are both the image of that key under the single map $T_k$, so $u = v$. The invariant holds initially (empty tables). The algorithm only adds an entry when the key is absent, so it stays injective, and each new object is registered under its own key.

Because keys contain addresses of components, Theorem 10.1.11 gives deep structural equality by induction on the nesting depth. Two struct types with equal element types have equal keys (the element pointers are equal by the induction hypothesis), so they are the same object. When it breaks: named (identified) struct types are deliberately not uniqued by structure, since %T = type { i32 } and %U = type { i32 } are different types. Objects from two contexts have unrelated tables, so comparing a type of $C_1$ with one of $C_2$ is meaningless (and mixing contexts in one module trips the verifier's assertions).

Ownership tree¶

Theorem 10.1.12 (Tree deletion is exact and leaves no dangling use)

If $\mathrm{own}$ is an ownership forest (Definition 10.1.1) and each object's destructor deletes exactly the objects it owns, then deleting a root $r$ deletes every object of $\mathrm{sub}(r)$ exactly once. If, in addition, the precondition of Algorithm 10.1.5 holds, then after phase 1 no Use anywhere refers to an object of $\mathrm{sub}(r)$, so phase 2 frees nothing that is still referenced.

Proof

Exactly once, by induction on the height $h$ of $\mathrm{sub}(r)$ (the longest $\mathrm{own}$-chain ending in $r$). For $h = 0$, $r$ owns nothing and is deleted once. For $h > 0$, $r$'s destructor deletes each child $c$ once. The subtrees $\mathrm{sub}(c)$ are disjoint, because $\mathrm{own}$ is a function and each object has one owner, and each has height below $h$, so by the induction hypothesis each of their objects is deleted exactly once. No object outside $\mathrm{sub}(r)$ is touched. No dangling use. The values of $\mathrm{sub}(r)$ can only be used by objects of $\mathrm{sub}(r)$ (the precondition). Phase 1 sets every operand of every such object to null, which unlinks it from the use list of its value (Lesson 10.2, Algorithm 10.2.3). After phase 1, therefore, no use list of a value in $\mathrm{sub}(r)$ has an entry, and no operand in $\mathrm{sub}(r)$ points into $\mathrm{sub}(r)$. Freeing in any order in phase 2 cannot leave a pointer to freed memory.

Phase 1 is needed because use edges can form cycles (%i = phi [ %i.next, … ], %i.next = add %i, 1): no deletion order of the instructions alone would free every value after all its users.

Intrusive lists¶

Lemma 10.1.13 (Locality of list operations)

Insert, Remove and Erase (Algorithm 10.1.7) preserve well-formedness, and they change the links of at most three nodes: $n$ and its neighbours. Consequently an iterator pointing to any node $x \ne n$ remains valid and denotes the same element, with the same successor unless $x$ is a neighbour of $n$.

Proof

For Insert(p, n): before the operation $\mathrm{next}(q) = p$ and $\mathrm{prev}(p) = q$. Afterwards the order is $\dots, q, n, p, \dots$ and both link equations hold for $q$, $n$, $p$. No other node's links were written. Remove is the inverse. Every node other than $n$, $q = \mathrm{prev}(n)$, $r = \mathrm{next}(n)$ keeps both links, and $q$, $r$ satisfy $\mathrm{next}(q) = r$ and $\mathrm{prev}(r) = q$. An iterator is a node pointer, so it stays valid while its node is alive, and only Erase(n) frees a node, namely $n$.

Theorem 10.1.14 (Early increment is safe; the plain loop is not)

Under the precondition of Algorithm 10.1.8, the early-increment loop never dereferences a freed node and runs $\beta$ once per element present at the start. The plain loop for x in L: β(x), which advances after the body, dereferences freed memory whenever $\beta$ erases $x$ and the loop continues.

Proof

Invariant. Initially $\mathit{it} = \mathrm{next}(s)$ is linked and nothing is processed. In an iteration, $x \leftarrow \mathit{it}$ and $\mathit{it} \leftarrow \mathrm{next}(x)$ are read while $x$ is linked. Then $\beta(x)$ may erase only $x$. By Lemma 10.1.13 the node $\mathit{it}$ (which is not $x$) stays linked and valid, and its links may change only because $x$, its predecessor, was removed. So at the next test $\mathit{it}$ is linked or is $s$, and $x$ has been processed. Termination and coverage. Each iteration processes the element at $\mathit{it}$ and moves $\mathit{it}$ one step along the current order. The body never re-links nodes behind $\mathit{it}$ ahead of it (it may only erase $x$), so every original element is visited once, in order, and $\mathit{it}$ reaches $s$ after $\lvert L \rvert$ iterations. Plain loop. After $\beta$ erases $x$ the loop computes $\mathrm{next}(x)$, a read of the freed node: undefined behavior (the ASan box shows the read).

When it breaks: if $\beta$ erases the next node (I.getNextNode()->eraseFromParent()), the early-increment iterator itself dangles. The precondition "only $x$" is essential, and the iterator-invalidation drill includes that case.

Index-based arenas¶

Proposition 10.1.15 (References never dangle into freed memory)

If entities are only ever appended to an arena and removed from the layout (never from the arena) while the function lives, then every reference $i < \lvert A \rvert$ obtained during the function's lifetime indexes live memory, and denotes the same entity data it denoted when it was created.

Proof

The arena only grows, so $\lvert A \rvert$ never decreases and $A[i]$ exists for every issued $i$. A reallocation of $A$'s buffer moves the data, but a reference is an index, not an address, so $A[i]$ still finds it. The slot $i$ is never overwritten by MakeInst (which only writes $A[\lvert A \rvert]$), so it keeps its data.

The flip side is the stale reference. A pass that removed instruction $i$ from the layout can still read $A[i]$, and nothing tells it the instruction is dead. Cranelift therefore checks layout membership where it matters (layout.inst_block(i) returns None for a removed instruction).

5. Complexity¶

Variables: $n$ = number of elements in the list or arena, $k$ = number of components of a uniqued object, $L$ = total size of the IR (objects plus uses).

Technique	Operation	Time (worst)	Time (typical)	Space
Context uniquing	get-or-create	$O(k)$ hash + $O(k)$ compare, plus rehash	$O(k)$ expected	one table entry per distinct object
Ownership tree	delete a module	$O(L)$	$O(L)$	no extra
Intrusive list	insert/remove/erase at a known node	$O(1)$	$O(1)$	2 pointers per element (+ parent for instructions)
Intrusive list	`size()`, `std::distance`	$O(n)$	$O(n)$	—
Intrusive list	`a->comesBefore(b)`	$O(n)$ to renumber a block	$O(1)$ amortized (cached order numbers)	one integer per instruction
Index arena	append; access by reference	$O(n)$ on reallocation; $O(1)$	$O(1)$ amortized; $O(1)$	4-byte references; data never freed until the function dies

Proposition 10.1.16 (Cost of the tree deletion)

Algorithm 10.1.5 runs in $O(L)$ time, where $L$ counts IR objects and operand slots.

Proof

Phase 1 visits each operand slot once and unlinks it in $O(1)$ (Algorithm 10.2.3 of Lesson 10.2). Phase 2 visits each owned object once (Theorem 10.1.12) and frees it in $O(1)$ (each object's operand array is freed with it). The total is linear in the number of slots plus objects.

Pathological input. for (Instruction &I : BB) if (BB.size() > Limit) … looks linear but is $\Theta(n^2)$, because size() walks the list (simple_ilist::size is std::distance(begin(), end())). On a 100 000-instruction block (possible after full unrolling) that is $5 \times 10^9$ steps. In the same way, calling comesBefore after every insertion into a long block renumbers the block each time, giving $\Theta(n^2)$ over $n$ insertions. LLVM invalidates the cached order lazily and renumbers only on the next query, so interleaving queries and insertions is what triggers it.

At scale: uniquing makes isIntegerTy(32) and type equality single comparisons. The price is that a context's tables only grow. A long-running JIT that creates a fresh LLVMContext per module (as ORC's ThreadSafeModule encourages, Lesson 10.8) gets that memory back when the context dies.

Context uniquing¶

Uniquing metadata too [LLVM-Metadata]: MDNode::get uniques nodes by operands, while MDNode::getDistinct creates nodes that are deliberately unique. The trade-off is sharing against the ability to mutate a node (distinct nodes can be changed in place).
Per-thread contexts vs a global table [LLVM-ORC]: LLVM chose per-context tables and no locks. A global, thread-safe table (as some hash-consing libraries use) would share more, at the cost of synchronization on every get.
Weak hash-consing (entries collected when unreferenced), as in functional-language runtimes: bounded memory, but a pointer's identity can change over time. LLVM's tables are strong: objects live until the context dies.

Ownership tree¶

removeFromParent + insertInto/moveBefore move a subtree without re-creating it. BasicBlock::splice moves a whole range of instructions in $O(1)$ list operations plus parent updates.
dropAllReferences before bulk deletion (Algorithm 10.1.5) is also what DeleteDeadBlocks does for sets of blocks that use each other.
Materializers (lazy bitcode loading): function bodies are owned but not yet materialized, and the ownership tree is completed on demand.

Intrusive lists¶

Debug records ride on the list [LLVM-DbgRecords]: since LLVM 19, debug-info records are attached to instructions through DbgMarkers instead of being instructions, and BasicBlock::iterator carries a "head bit" that says whether an insertion goes before or after the records at a position (Lesson 10.3 §2).
simple_ilist vs iplist: simple_ilist owns nothing and never allocates. iplist with SymbolTableListTraits additionally updates parent pointers and the function's symbol table on insert/remove (the "traits" callbacks).
Order numbers for comesBefore: $O(1)$ amortized dominance queries within a block, at the cost of one integer per instruction and lazy renumbering.

Index-based arenas¶

Generational indices (slot maps): store a generation counter with each slot and in the reference, so that a stale reference is detected after the slot is reused. This allows reuse at 4 more bytes per reference.
rustc's IndexVec and MIR: arenas per body plus newtype_index! types. The borrow checker enforces that the arena outlives the references.
MLIR keeps LLVM's intrusive lists (operations in blocks, blocks in regions). It is not an arena design.

7. In real compilers¶

Context uniquing¶

LLVM

llvm/lib/IR/LLVMContextImpl.h, class LLVMContextImpl: IntegerTypes, FunctionTypes, AnonStructTypes, IntConstants, FPConstants, ArrayConstants, StructConstants [LLVM-CtxImpl]. llvm/lib/IR/Constants.cpp, ConstantInt::get(LLVMContext &, const APInt &) shows the zero/one fast slots (LLVM 23.1.2).

GCC: types are hash-consed through type_hash_canon (gcc/tree.cc), and small integer constants are shared per type through the TYPE_CACHED_VALUES vector (cache_wide_int_in_type_cache in the same file, gcc-15).
Cranelift: types are small Copy values (pub struct Type(u16) in cranelift/codegen/src/ir/types.rs), so equality is by value and there is nothing to unique; vector constants live in a per-function ConstantPool (ir/constant.rs).

Find where LLVM does it. Open llvm/lib/IR/Constants.cpp at llvmorg-23.1.2 and read ConstantInt::get(LLVMContext &Context, const APInt &V). Question: which two values of an integer width do not go through the general IntConstants map, and where are they stored instead? (Quiz llvm-where-zero-one-slots.)

Ownership tree¶

LLVM

llvm/lib/IR/Module.cpp Module::~Module, llvm/lib/IR/Function.cpp Function::~Function and Function::deleteBodyImpl (which the inline Function::dropAllReferences in Function.h calls), llvm/lib/IR/BasicBlock.cpp BasicBlock::dropAllReferences, llvm/include/llvm/IR/Instruction.h removeFromParent/eraseFromParent/insertInto [LLVM-Module, LLVM-Function].

Clang owns its AST in an ASTContext arena (bump-pointer allocation, no individual deletes), a different ownership model for a structure that is never mutated after Sema.
MLIR Operation::erase / Operation::remove mirror LLVM's pair, and a Region owns its blocks.

Intrusive lists¶

LLVM

llvm/include/llvm/ADT/ilist.h (iplist_impl::erase, remove), llvm/include/llvm/ADT/simple_ilist.h (size() is linear, with a comment saying so), llvm/include/llvm/ADT/ilist_node.h [LLVM-ilist]. llvm/include/llvm/ADT/STLExtras.h early_inc_iterator_impl / make_early_inc_range [LLVM-STLExtras].

Linux kernel include/linux/list.h (v6.12): list_for_each_entry_safe, the same "fetch next first" idea as early increment.
GCC RTL insns and GIMPLE statements are also intrusive (NEXT_INSN, gimple_seq).

Find where LLVM does it. In STLExtras.h, find early_inc_iterator_impl::operator*. Question: in which operator is the underlying iterator advanced, operator* or operator++? (Quiz early-inc-where.)

Index-based arenas¶

Cranelift

cranelift/entity/src/lib.rs (PrimaryMap, SecondaryMap, EntityList) and cranelift/codegen/src/ir/dfg.rs DataFlowGraph, cranelift/codegen/src/ir/layout.rs Layout (Wasmtime v37.0.2) [CL-Entity, CL-DFG].

rustc compiler/rustc_index/src/vec.rs IndexVec; MIR's BasicBlocks (compiler/rustc_middle/src/mir/basic_blocks.rs) wraps an IndexVec<BasicBlock, BasicBlockData> (rustc 1.90.0).
LLVM uses indices where objects are not the point: ValueNumbering tables, and per-block numbers (BasicBlock::getNumber in llvm/include/llvm/IR/BasicBlock.h) that let analyses such as DominatorTree use dense vectors as side tables.

8. Comparison¶

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

Choose uniquing whenever equality of immutable values is frequent. That is almost always true for types. Choose the ownership tree with intrusive lists when the IR is mutated in place by many independent passes and object identity (pointers held in side tables) matters, as in LLVM. Choose an arena when you want compact, serializable IR without per-object allocation and can tolerate that "deleted" means "unlinked", as in Cranelift and rustc.

9. Assessment¶

Technique	Quiz ids (`solutions/quizzes/ch10.yaml`)	Drill	Flashcard tag	Exercises
Context uniquing	`uniquing-pointer-eq`, `llvm-where-zero-one-slots`	— (see note)	`uniquing`	Lab 10.1 (every `getInt64Ty` call)
Ownership tree	`erase-vs-remove`, `ownership-subtree`	`./course drill iterator-invalidation`	`ownership`	Lab 10.1, Lab 10.2 R6
Intrusive lists	`early-inc-trace`, `ilist-size-cost`, `early-inc-where`	`./course drill iterator-invalidation`	`ilist`	Lab 10.2 R8
Index-based arenas	`arena-stale-ref`, `arena-layout-trace`	— (see note)	`arena`	— (theory)

A drill does not fit uniquing or arenas well. Both have one decisive property each (Theorem 10.1.11, Proposition 10.1.15), and the quiz tests it with a computed trace (uniquing-pointer-eq) and a scenario (arena-stale-ref), so random instances would repeat the same question.

Pitfall

removeFromParent is not a delete, and eraseFromParent is not a remove. The first leaks the instruction if you forget to re-insert or delete it (the verifier will not tell you). The second leaves every Instruction * you kept pointing to freed memory. And with either one, a plain for (Instruction &I : BB) loop around it is undefined behavior.

References¶

See the chapter references.

step	request	key	table hit?	tables after
1	`getInt32Ty` (return type)	\((\mathit{Int}, 32)\)	no → create \(t\)	\(T_{\mathit{Int}} = \{32 \mapsto t\}\)
2	`getInt32Ty` (argument)	\((\mathit{Int}, 32)\)	yes → \(t\)	unchanged
3	`getInt32(1)`	\((\mathit{CInt}, 32, 1)\)	no → create \(c_1\) (the "one" slot)	\(T_{\mathit{CInt}} = \{1 \mapsto c_1\}\)
4	`getInt32(2)`	\((\mathit{CInt}, 32, 2)\)	no → create \(c_2\)	\(+\{2 \mapsto c_2\}\)
5	`getInt32(3)`	\((\mathit{CInt}, 32, 3)\)	no → create \(c_3\)	\(+\{3 \mapsto c_3\}\)
6	`getInt32(1)` again (e.g. from a later pass)	\((\mathit{CInt}, 32, 1)\)	yes → \(c_1\)	unchanged

step	`x`	`it` after advance	body	list after
1	\(A\)	\(B\)	erase \(A\)	\(s, B, C, R\)
2	\(B\)	\(C\)	erase \(B\)	\(s, C, R\)
3	\(C\)	\(R\)	erase \(C\)	\(s, R\)
4	\(R\)	\(s\)	`ret` is a terminator: keep	\(s, R\)
5	—	\(\mathit{it} = s\): stop	—	final: `ret i32 %x`

Technique	Operation	Time (worst)	Time (typical)	Space
Context uniquing	get-or-create	\(O(k)\) hash + \(O(k)\) compare, plus rehash	\(O(k)\) expected	one table entry per distinct object
Ownership tree	delete a module	\(O(L)\)	\(O(L)\)	no extra
Intrusive list	insert/remove/erase at a known node	\(O(1)\)	\(O(1)\)	2 pointers per element (+ parent for instructions)
Intrusive list	`size()`, `std::distance`	\(O(n)\)	\(O(n)\)	—
Intrusive list	`a->comesBefore(b)`	\(O(n)\) to renumber a block	\(O(1)\) amortized (cached order numbers)	one integer per instruction
Index arena	append; access by reference	\(O(n)\) on reallocation; \(O(1)\)	\(O(1)\) amortized; \(O(1)\)	4-byte references; data never freed until the function dies

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

Lesson 10.1 — Ownership and IR containers¶

1. Problem and motivation¶

Context uniquing¶

Ownership tree¶

Intrusive lists¶

Index-based arenas¶

2. Definitions and algorithms¶

Context uniquing¶

Ownership tree¶

Intrusive lists¶

Index-based arenas¶

3. Worked example¶

Context uniquing¶

Ownership tree¶

Intrusive lists¶

Index-based arenas¶

4. Invariants and correctness¶

Context uniquing¶

Ownership tree¶

Intrusive lists¶

Index-based arenas¶

5. Complexity¶

6. Variants and refinements¶

Context uniquing¶

Ownership tree¶

Intrusive lists¶

Index-based arenas¶

7. In real compilers¶

Context uniquing¶

Ownership tree¶

Intrusive lists¶

Index-based arenas¶

8. Comparison¶

9. Assessment¶

References¶