Lesson 9.1 — Modules, globals, functions and SSA values¶
Techniques: the module as a unit of compilation; global values with linkage, visibility and preemption; functions, basic blocks and SSA values · Pebble uses: all of it (
pebblecemits one module per program) · Lab: E1, E2 (SPEC) · Prerequisites: Ch 8 (three-address code, CFGs, SSA as an idea) · Time: 3–4 hours
Compile this C function, the running example of the whole chapter, with clang and look at what comes out:
long long sum_pos(const long long *a, long long n) {
long long s = 0;
for (long long i = 0; i < n; i++)
if (a[i] > 0)
s += a[i];
return s;
}
The output is a module: a data layout string, a target triple, and one function definition @sum_pos with a global name, a linkage (dso_local, external), typed parameters (ptr %a, i64 %n), and a body of seven basic blocks, each a straight list of instructions ending in exactly one branch or return. Every instruction that produces something produces a new named value (%cmp, %arrayidx, %add), never updating an old one. This lesson defines those three layers precisely: what a module contains, what a global's linkage and visibility mean to the linker, and what "a function is a CFG of basic blocks over SSA values" means. Lesson 9.2 does the types, Lesson 9.3 the control flow and the verifier's rules.
1. Problem and motivation¶
A compiler IR has to answer three questions before it can say anything about instructions (for the general design space, see Ch 8 and [EaC3, Ch. 4]). What is the unit of compilation? (a file, a program, a crate). What does a name mean across units? (can two files define f, which one wins, can the definition be replaced at load time). How are values inside a function named and related? LLVM IR answers them with the module, the linkage model borrowed from object files, and static single assignment inside functions. Lattner and Adve designed it in 2002–2004 so that the same representation survives from the front end through link-time and even run-time optimization: that is why the linkage model of object files is part of the IR rather than an afterthought [Lat02, LA04]. pebblec produces one module per Pebble program (Ch 11); every pass in this course sees one module at a time.
Module structure¶
Before LLVM, most compilers kept their mid-level IR inside a single process run and dropped it once the object file was written. Lattner's thesis argues for an IR that is a persistent, self-contained program representation: complete enough to be written to disk, linked with other units, optimized again at link time and even at install time [Lat02]. The module is that unit. It carries everything needed to interpret its contents without the front end: the target's data layout (sizes, alignments, endianness, Lesson 9.2), the target triple, the types, the globals and functions, and metadata [LLVM-LangRef, §Module Structure].
Globals, linkage and visibility¶
A module is not a whole program: it refers to names defined elsewhere, and other modules refer to its names. Object files solved this in the 1970s with symbol tables whose entries are strong, weak or common, local or global. C++ added the one-definition rule (ODR), under which the many identical copies of an inline function or a template instance may be merged. LLVM IR keeps all of these distinctions in the IR as linkage types so that the IR linker (llvm-link, and LTO) can resolve names exactly as a system linker would, and so that optimizers know when a definition may be replaced (and therefore must not be inlined or used for constant propagation) [LA04, §3; LLVM-LangRef, §Linkage Types].
Functions, basic blocks and SSA values¶
Inside a function, LLVM IR is a control-flow graph (CFG) of basic blocks over values in static single assignment (SSA) form [CFRWZ91]. SSA was invented for analysis; LLVM made it the only form of register values, so that every analysis can read def-use information directly from the IR, with no separate reaching-definitions computation [LA04, §2.1]. Memory is the escape hatch: anything that is not in SSA form lives in memory and is accessed by load/store (Lesson 9.4). The front end may emit everything through memory; mem2reg then builds SSA (Ch 16).
2. Definitions and algorithms¶
Module structure¶
Definition 9.1.1 (Module)
A module is a tuple \(M = (\mathit{DL}, \mathit{TT}, \mathcal{T}, \mathcal{G}, \mathcal{F}, \mathcal{A}, \mathcal{C}, \mathcal{M}\!d)\) where \(\mathit{DL}\) is the data layout string and \(\mathit{TT}\) the target triple (Lesson 9.2), \(\mathcal{T}\) a finite set of identified struct types, \(\mathcal{G}\) the global variables, \(\mathcal{F}\) the functions, \(\mathcal{A}\) the aliases and ifuncs, \(\mathcal{C}\) the comdats and \(\mathcal{M}\!d\) the named metadata. The set of global values is \(\mathcal{GV}(M) = \mathcal{G} \cup \mathcal{F} \cup \mathcal{A}\); each has a name in the module's symbol table \(\mathrm{Sym}(M) : \mathit{Name} \rightharpoonup \mathcal{GV}(M)\), which is injective.
The running example as a module
clang -S -emit-llvm sum_pos.c gives \(\mathit{DL}\) = "e-m:e-p270:32:32-…-S128", \(\mathit{TT}\) = x86_64-unknown-linux-gnu, \(\mathcal{T} = \emptyset\), \(\mathcal{G} = \emptyset\), \(\mathcal{F} = \{\texttt{@sum\_pos}\}\), and named metadata !llvm.module.flags and !llvm.ident. \(\mathrm{Sym}(M) = \{\texttt{sum\_pos} \mapsto \texttt{@sum\_pos}\}\).
A global value is either a definition (a global variable with an initializer, a function with a body) or a declaration (no initializer, no body: @errno_like = external global i32, declare i32 @printf(ptr, ...)). A global variable is a region of memory allocated at load time; its name denotes its address, so @counter has type ptr and is read with load i32, ptr @counter.
Globals, linkage and visibility¶
Definition 9.1.2 (Linkage, visibility, preemption)
Every global value \(g\) has
- a linkage \(\ell(g)\) in \(L = \{\texttt{private}, \texttt{internal}, \texttt{available\_externally}, \texttt{linkonce}, \texttt{linkonce\_odr}, \texttt{weak}, \texttt{weak\_odr}, \texttt{common}, \texttt{appending}, \texttt{extern\_weak}, \texttt{external}\}\);
- a visibility in \(\{\texttt{default}, \texttt{hidden}, \texttt{protected}\}\) (local linkages require
default); - a preemption specifier in \(\{\texttt{dso\_local}, \texttt{dso\_preemptable}\}\) (the default).
The linkages are classified by four predicates:
- local: \(\ell \in \{\texttt{private}, \texttt{internal}\}\) — the name is invisible outside the module (
privatenot even in the object file's symbol table); - discardable: \(\ell \in \{\texttt{private}, \texttt{internal}, \texttt{linkonce}, \texttt{linkonce\_odr}, \texttt{available\_externally}\}\) — the definition may be deleted when nothing in the module uses it;
- interposable: \(\ell \in \{\texttt{linkonce}, \texttt{weak}, \texttt{common}, \texttt{extern\_weak}\}\), or \(g\) is
dso_preemptablewith non-local linkage in a module whoseSemanticInterpositionmodule flag is set (clang's-fsemantic-interposition; without the flag LLVM treatsexternaldefinitions as non-interposable) — the definition the program runs with may be a different one, so an optimizer may not use this body's contents; - ODR: \(\ell \in \{\texttt{linkonce\_odr}, \texttt{weak\_odr}\}\) (and
available_externally) — every definition of the name in the program is equivalent, so the body may be used for optimization even though it may be replaced.
The distinction between discardable and interposable is the heart of the model (LLVM's own comment on the ODR linkages is that they "cannot be overridden but can be de-refined": another module's copy is equivalent, but may be less optimized, so an optimizer may inline the body but not infer facts that only its optimized form shows): linkonce_odr (C++ inline functions, template instances) is discardable but not interposable, so it can be inlined and then deleted; weak (C __attribute__((weak))) is interposable, so it can be neither inlined nor deleted. dso_local is the front end's promise that the symbol resolves inside the same linked object (executable or shared library), which lets the back end use direct, PC-relative addressing instead of a GOT load.
Definition 9.1.3 (Strength of a definition)
For linking, rank a non-local global value by its strength \(\sigma\):
| linkage | declaration, extern_weak |
available_externally |
linkonce, linkonce_odr |
weak, weak_odr |
common |
external definition |
|---|---|---|---|---|---|---|
| \(\sigma\) | 0 | 1 | 2 | 3 | 4 | 5 |
Two definitions conflict if both have \(\sigma = 5\). (appending globals are concatenated instead; local linkages never take part.)
Algorithm 9.1.4 (Resolving one non-local name when linking modules)
- Input: the ordered list \(D = \langle d_1, \dots, d_k \rangle\) of global values named \(x\) with non-local, non-
appendinglinkage, one per module in link order. - Output: the single global value that \(x\) denotes in the linked module, or an error.
- Precondition: all \(d_i\) have compatible types (functions with functions, variables with variables).
- Postcondition: the chosen \(d\) has maximal strength among \(D\); if two members have strength 5, the result is the error "symbol multiply defined!".
- Invariant: after step \(i\),
curis a member of \(\langle d_1, \dots, d_i \rangle\) of maximal strength; among several of strength \(\le 3\) it is the first, among severalcommonones the largest.
function Resolve(D = ⟨d1, …, dk⟩):
cur ← d1
for i in 2..k:
if σ(di) = 5 and σ(cur) = 5:
error "Linking globals named 'x': symbol multiply defined!"
if σ(di) > σ(cur):
cur ← di # a stronger definition replaces a weaker one
else if σ(di) = 4 and σ(cur) = 4 and size(di) > size(cur):
cur ← di # common: the larger object wins
# otherwise keep cur: among equally strong weak/linkonce definitions the first wins
if cur is discardable and nothing references x:
delete cur # linkonce*, available_externally: dropped when unused
return cur
Local names (internal, private) never participate: the IR linker renames a clashing local (@k becomes @k.3) instead of resolving it.
Functions, basic blocks and SSA values¶
Definition 9.1.5 (Function, basic block, CFG)
A function definition is \(f = (\tau_{\mathrm{ret}}, \langle p_1 : \tau_1, \dots, p_n : \tau_n \rangle, \mathit{attrs}, B, b_0)\) with a return type, typed parameters, attributes (Lesson 9.5), a finite nonempty sequence of basic blocks \(B\), and the entry block \(b_0 = B[0]\). A basic block \(b\) is a label and a nonempty sequence of instructions \(\langle i_1, \dots, i_m \rangle\) in which \(i_m\) is a terminator (Lesson 9.3) and no \(i_j\) with \(j < m\) is. The CFG of \(f\) is \(G_f = (B, E, b_0)\) with \((b, b') \in E\) iff \(b'\) is a successor named by \(b\)'s terminator.
Definition 9.1.6 (Values, uses, SSA)
The values of a function are its parameters, its instructions of non-void type, its basic blocks (as label values), and the module's global values and constants. An instruction uses each value among its operands. The function is in static single assignment form if every local name (%x or a number) is defined by at most one parameter or instruction in the text of \(f\), and every use of a local name refers to that definition. The def-use chain of a value \(v\) is \(\mathrm{uses}(v) = \{\, (i, k) \mid \text{operand } k \text{ of } i \text{ is } v \,\}\).
Where a definition must sit relative to its uses (dominance) is part of well-formedness, Definition 9.3.4.
A value has no storage. %add = add nsw i64 %s.0, %1 does not say "store the sum into a register named add": it is the sum, and %add is just how the text refers to it. Unnamed values print as %0, %1, …; the numbering is a property of the text, not of the IR in memory, which links every use directly to its definition.
Algorithm 9.1.7 (Slot numbering of unnamed local values)
- Input: a function \(f\) in memory, some of whose parameters, blocks and instructions have no name.
- Output: a number \(\mathrm{slot}(v)\) for each unnamed local value, used by the printer as
%N. - Precondition: none.
- Postcondition: the unnamed values get \(0, 1, 2, \dots\) without gaps in textual order: parameters first, then for each block in order the block itself (if unnamed) followed by its unnamed non-
voidinstructions. - Invariant:
nextequals the number of unnamed values already visited.
function NumberSlots(f):
next ← 0
for p in params(f):
if p has no name: slot[p] ← next; next ← next + 1
for b in blocks(f): # in layout order
if b has no name: slot[b] ← next; next ← next + 1
for i in instructions(b):
if type(i) ≠ void and i has no name:
slot[i] ← next; next ← next + 1
return slot
The parser of LLVM 23 accepts any strictly increasing numbering in textual order (gaps allowed) and rejects a number smaller than the next free one; the printer always produces the gap-free numbering above.
3. Worked example¶
Take the memory form clang produces at -O0 for sum_pos and let mem2reg promote the four stack slots %a.addr, %n.addr, %s, %i (Ch 16 explains how). The result is the chapter's running example; every later lesson refers to its blocks by these names:
define dso_local i64 @sum_pos(ptr noundef %a, i64 noundef %n) #0 {
entry:
br label %for.cond
for.cond: ; preds = %for.inc, %entry
%s.0 = phi i64 [ 0, %entry ], [ %s.1, %for.inc ]
%i.0 = phi i64 [ 0, %entry ], [ %inc, %for.inc ]
%cmp = icmp slt i64 %i.0, %n
br i1 %cmp, label %for.body, label %for.end
for.body: ; preds = %for.cond
%arrayidx = getelementptr inbounds i64, ptr %a, i64 %i.0
%0 = load i64, ptr %arrayidx, align 8
%cmp1 = icmp sgt i64 %0, 0
br i1 %cmp1, label %if.then, label %if.end
if.then: ; preds = %for.body
%arrayidx2 = getelementptr inbounds i64, ptr %a, i64 %i.0
%1 = load i64, ptr %arrayidx2, align 8
%add = add nsw i64 %s.0, %1
br label %if.end
if.end: ; preds = %if.then, %for.body
%s.1 = phi i64 [ %add, %if.then ], [ %s.0, %for.body ]
br label %for.inc
for.inc: ; preds = %if.end
%inc = add nsw i64 %i.0, 1
br label %for.cond, !llvm.loop !5
for.end: ; preds = %for.cond
ret i64 %s.0
}
flowchart TD
entry([entry]) --> for.cond[for.cond]
for.cond --> for.body[for.body]
for.cond --> for.end[for.end]
for.body --> if.then[if.then]
for.body --> if.end[if.end]
if.then --> if.end
if.end --> for.inc[for.inc]
for.inc --> for.cond
classDef hl fill:#fde68a,stroke:#b45309;
class for.cond,if.end hl;The two highlighted blocks are the joins: for.cond (entry edge and back edge for.inc → for.cond) and if.end (the two arms of the if). They are exactly the blocks with phis.
Values and def-use chains. The table lists every local value, where it is defined and every use (Definition 9.1.6). Parameters are defined "at entry".
| value | defined in | kind | uses (instruction, operand) |
|---|---|---|---|
%a |
parameter | ptr |
%arrayidx op 0, %arrayidx2 op 0 |
%n |
parameter | i64 |
%cmp op 1 |
%s.0 |
for.cond |
phi | %add op 0, %s.1 (from %for.body), ret op 0 |
%i.0 |
for.cond |
phi | %cmp op 0, %arrayidx op 1, %arrayidx2 op 1, %inc op 0 |
%cmp |
for.cond |
icmp |
br in for.cond |
%arrayidx |
for.body |
GEP | %0 op 0 |
%0 |
for.body |
load |
%cmp1 op 0 |
%cmp1 |
for.body |
icmp |
br in for.body |
%arrayidx2 |
if.then |
GEP | %1 op 0 |
%1 |
if.then |
load |
%add op 1 |
%add |
if.then |
add |
%s.1 (from %if.then) |
%s.1 |
if.end |
phi | %s.0 (from %for.inc) |
%inc |
for.inc |
add |
%i.0 (from %for.inc) |
Every name appears once in the "defined in" column: the function is in SSA form. The variable s of the C program has become three values, %s.0, %add and %s.1, and the phis say which one flows along which edge.
Slot numbering (Algorithm 9.1.7). The parameters and blocks are named, so the unnamed values are the two loads. The trace:
| step | visited | unnamed? | next before | slot |
|---|---|---|---|---|
| 1 | %a, %n (params) |
no | 0 | — |
| 2 | block entry, its br |
no / void | 0 | — |
| 3 | block for.cond: %s.0, %i.0, %cmp, br |
no | 0 | — |
| 4 | block for.body: %arrayidx |
no | 0 | — |
| 5 | load i64, ptr %arrayidx |
yes | 0 | 0 |
| 6 | %cmp1, br |
no | 1 | — |
| 7 | block if.then: %arrayidx2 |
no | 1 | — |
| 8 | load i64, ptr %arrayidx2 |
yes | 1 | 1 |
| 9 | rest of the function | no | 2 | — (done) |
Hence %0 and %1 in the listing. At -O0 without -fno-discard-value-names, clang names nothing and the same algorithm numbers the parameters %0, %1, the entry block %2, and the first alloca %3.
Linking (Algorithm 9.1.4). Two modules define @x: a.ll has @x = weak global i32 1, b.ll has @x = global i32 2. Both also define @f as linkonce_odr, and b.ll defines @g as available_externally:
| step | module | candidate for x |
\(\sigma\) | cur |
why |
|---|---|---|---|---|---|
| 1 | a.ll |
weak @x = 1 |
3 | a:@x |
first definition |
| 2 | b.ll |
@x = 2 (external) |
5 | b:@x |
stronger replaces weaker |
| — | end | b:@x |
result: @x = global i32 2 |
For f: a:@f (\(\sigma\) = 2), then b:@f (\(\sigma\) = 2, not stronger): a:@f stays; nothing references @f, and linkonce_odr is discardable, so it is deleted. For g: one definition, \(\sigma\) = 1, referenced by @use_b: it stays, as available_externally, and will not be emitted into the object file. The real-world box below shows llvm-link doing exactly this.
Try it
./course drill ir-validity --seed 3 --difficulty easy asks you to decide whether a small function is well formed; the SSA rules of Definition 9.1.6 are its first checks.
4. Invariants and correctness¶
Module structure¶
Proposition 9.1.8 (A module is closed under references)
In a module accepted by the parser, every operand that names a global value @x refers to \(\mathrm{Sym}(M)(x)\), which is either a definition or a declaration in the same module; in particular a module never refers to a global value by any means other than its own symbol table.
Proof
The parser resolves every @x token against the module's symbol table. If @x is used before its definition in the text, it creates a forward reference placeholder and replaces all its uses when the definition is parsed; at the end of the module, any placeholder that is still unresolved is an error ("use of undefined value '@x'"). A declaration is a symbol-table entry without a body, so an external function is referenced through its declaration. Hence after a successful parse every global operand is a symbol-table entry of the same module. Links between modules exist only as equal names, resolved by Algorithm 9.1.4 when modules are linked.
Globals, linkage and visibility¶
Proposition 9.1.9 (Order independence of resolution)
Let \(D\) contain at most one definition of strength 5. Then the global value chosen by Algorithm 9.1.4 has strength \(\max_{d \in D} \sigma(d)\) for every order of \(D\); if exactly one member attains that maximum, it is chosen for every order.
Proof
We prove the invariant by induction on \(i\). Initialization: cur \(= d_1\) is of maximal strength in \(\langle d_1 \rangle\). Maintenance: in step \(i\), if \(\sigma(d_i) > \sigma(\mathit{cur})\), the new cur \(= d_i\) is of maximal strength among the first \(i\) members, because the old cur was maximal among the first \(i - 1\); otherwise \(\sigma(\mathit{cur}) \ge \sigma(d_i)\) and cur stays maximal (the common rule replaces a strength-4 value by another strength-4 value). The error branch needs two members of strength 5, which the hypothesis excludes. Termination: after \(i = k\), \(\sigma(\mathit{cur}) = \max_{d \in D} \sigma(d)\), a quantity that does not depend on the order. If a unique \(d^\ast\) attains the maximum, the result, which attains it, is \(d^\ast\).
When several weak definitions tie, the first in link order wins, so the program's meaning can depend on link order. That is exactly the case the ODR linkages exclude: for linkonce_odr and weak_odr all candidates are equivalent by the language's one-definition rule, so any choice is correct. This is why an optimizer may inline a linkonce_odr body but not a weak one.
When it breaks. A front end that marks a function linkonce_odr although two translation units define it differently (an ODR violation in C++, which is undefined behavior but not diagnosed) gets a program whose behavior depends on link order and on whether the optimizer inlined the local copy. LLVM cannot detect this.
Functions, basic blocks and SSA values¶
Lemma 9.1.10 (Slot numbering is a bijection)
Algorithm 9.1.7 assigns to the \(u\) unnamed local values of \(f\) the numbers \(0, \dots, u - 1\), each exactly once, in textual order.
Proof
By induction on the number of visited values, the invariant "next = number of unnamed values visited so far, and they received \(0, \dots, \mathit{next} - 1\) in order" holds: initially no value is visited and next = 0; visiting an unnamed value assigns it next and increments it; visiting a named value changes nothing. Every parameter, block and instruction is visited exactly once by the two loops, so at termination \(\mathit{next} = u\) and the assignment is the bijection \(\{\text{unnamed values}\} \to \{0, \dots, u - 1\}\) in textual order.
Corollary 9.1.11 (Print–parse round trip)
Printing a function with Algorithm 9.1.7 and parsing the text back yields a function with the same values and the same use–def links.
Proof
The printer writes named values under their names and unnamed ones as %slot. By Lemma 9.1.10 the slots are distinct and strictly increasing in textual order, which is what the parser requires, so parsing succeeds and binds each %N back to the value printed at position \(N\). Names are unique within a function (SSA, Definition 9.1.6), so every use in the text resolves to the definition it was printed from.
5. Complexity¶
| Technique | Time (worst) | Time (typical) | Space | Variables |
|---|---|---|---|---|
| Parsing a module | \(O(s)\) plus symbol-table hashing | linear in the text | \(O(s)\) | \(s\) = size of the text |
| Linking (Algorithm 9.1.4, all names) | \(O(g + r)\) expected | linear | \(O(g)\) | \(g\) = global values, \(r\) = references |
| Slot numbering (Algorithm 9.1.7) | \(\Theta(v)\) | \(\Theta(v)\) | \(O(v)\) | \(v\) = values in the function |
| Def-use chains | \(O(1)\) per edit | — | \(O(u)\) | \(u\) = uses (one Use object each) |
Proposition 9.1.12 (Cost of linking)
Resolving all names of \(m\) modules with \(g\) global values in total takes \(O(g + r)\) expected time, where \(r\) is the number of references that must be redirected to the chosen definitions.
Proof
Each module's symbol table is a hash map, so finding the current candidate for a name is \(O(1)\) expected; Algorithm 9.1.4 does \(O(1)\) work per candidate, so all names cost \(O(g)\). Replacing a losing definition redirects each of its uses to the winner once (replaceAllUsesWith walks the use list), \(O(r)\) in total. Renaming a clashing local appends a counter suffix, \(O(1)\) expected per clash.
Pathological input. Renaming is where the cost hides: linking \(m\) modules that each define an internal @k produces @k, @k.1, …; with a naive "try the next suffix until free" loop this is \(\Theta(m^2)\) probes. LLVM keeps a per-name counter in the symbol table so each rename is \(O(1)\) expected. Similarly, a module with \(10^6\) unnamed values prints slots in linear time because slots are computed once per function (SlotTracker), not per use.
At scale. The linked module of a large program (Chromium's LTO build) holds millions of global values; that is why ThinLTO (Ch 20) resolves linkage on summaries instead of linking whole modules.
6. Variants and refinements¶
Module structure¶
- Bitcode and summaries [LLVM-Bitcode]: the same module serialized in a compact binary form, optionally with a ThinLTO module summary so that cross-module decisions do not need the bodies (Lesson 9.6; trade-off: a second representation to keep in sync).
- Module-level inline assembly and flags [LLVM-LangRef]:
module asmand!llvm.module.flags(with merge behaviors such asError,Max) carry information the linker must merge; trade-off: they are opaque to most passes.
Globals, linkage and visibility¶
- Comdats [LLVM-LangRef, §Comdats]: a group of globals that the object-file linker keeps or discards together (C++ inline functions with their guard variables and static locals). Trade-off: needed for correctness on COFF and ELF, but it couples otherwise independent symbols.
- Aliases and ifuncs:
@a = alias i32, ptr @bgives a second name to the same object; anifuncpicks the implementation at load time (CPU dispatch). Trade-off: aliases cannot be interposed separately from their target. dso_localinference (-fno-semantic-interposition,-fvisibility=hidden): the front end marks more symbolsdso_local, which removes GOT indirection and allows inlining of default-visibility functions in shared libraries, at the price of ELF interposition semantics.
Functions, basic blocks and SSA values¶
- Block arguments instead of phis (MLIR, Swift SIL, Cranelift): a block takes parameters and every branch passes arguments. It is the same information as phis, with the edge made explicit (Lesson 9.8; [LAB+21]).
- Memory SSA and the memory form: LLVM keeps memory out of SSA and offers MemorySSA as an analysis over it (Ch 19); front ends emit the memory form and rely on
mem2reg, trading front-end simplicity for an extra pass.
7. In real compilers¶
Module structure¶
LLVM
llvm/include/llvm/IR/Module.h — class Module owns the lists of GlobalVariables, Functions, GlobalAliases and GlobalIFuncs and the ValueSymbolTable; the text format is written by llvm/lib/IR/AsmWriter.cpp and read by llvm/lib/AsmParser/LLParser.cpp (LLParser::Run) (LLVM 23.1.2) [LLVM-LLParser].
- GCC 15 keeps the whole-program symbol table in the symtab (
gcc/cgraph.h,symtab_nodeand its subclassescgraph_nodeandvarpool_node); a translation unit's functions are GIMPLE bodies attached to call-graph nodes rather than a separate module object. - rustc calls the unit a codegen unit and hands LLVM one module per CGU (
compiler/rustc_codegen_llvm/src/base.rs,compile_codegen_unit).
Find where LLVM does it. Open llvm/lib/AsmParser/LLParser.cpp and find where a use of an undefined global is reported at the end of parsing. Question: which message does the parser print for call void @nope() when @nope is never declared?
Anatomy of a module
Reproduce (clang 23.1.2):
cat > globals.c <<'EOF'
int counter; /* tentative definition */
static int hits = 3; /* file-local */
const char greeting[] = "hi"; /* read-only data */
extern int errno_like; /* declared, defined elsewhere */
__attribute__((weak)) int tunable = 7;
__attribute__((visibility("hidden"))) int internal_api = 1;
_Thread_local int per_thread;
static int helper(int x) { return x + hits; }
inline int twice(int x) { return 2 * x; }
extern int twice(int); /* emit twice() here too */
int bump(int x) { counter += helper(x) + errno_like; return twice(counter); }
EOF
clang-23 --target=x86_64-unknown-linux-gnu -O0 -fno-discard-value-names -S -emit-llvm globals.c -o - \
| grep -v "^!\|^attributes\|^$" | head -12
Output (abridged: the first 12 lines; the function bodies follow):
; ModuleID = 'globals.c'
source_filename = "globals.c"
target datalayout = "e-m:e-p270:32:32-p271:32:32-p272:64:64-i64:64-i128:128-f80:128-n8:16:32:64-S128"
target triple = "x86_64-unknown-linux-gnu"
@greeting = dso_local constant [3 x i8] c"hi\00", align 1
@tunable = weak dso_local global i32 7, align 4
@internal_api = hidden global i32 1, align 4
@errno_like = external global i32, align 4
@counter = dso_local global i32 0, align 4
@per_thread = dso_local thread_local global i32 0, align 4
@hits = internal global i32 3, align 4
; Function Attrs: noinline nounwind optnone uwtable
What to notice: every component of Definition 9.1.1 except types and aliases is here. Each C storage class became a linkage (Definition 9.1.2): static → internal, weak → weak, a plain definition → external (the default, not printed), extern → a declaration with external. const became constant, a property of the global, not of its type. hidden visibility makes the symbol dso_local implicitly, which is why clang does not print dso_local on @internal_api.
Globals, linkage and visibility¶
LLVM
llvm/lib/Linker/LinkModules.cpp — ModuleLinker::shouldLinkFromSource implements the strength comparison of Algorithm 9.1.4 pairwise, as a cascade of ifs on the destination and source linkages (declarations lose, common beats weak/linkonce and keeps the larger size, weak beats linkonce, external beats all, two externals give "symbol multiply defined!"); llvm/lib/Linker/IRMover.cpp moves the chosen bodies and renames clashing locals. Linkage predicates such as isDiscardableIfUnused and isInterposable live in llvm/include/llvm/IR/GlobalValue.h (LLVM 23.1.2).
- GCC 15 records the same facts as symbol flags:
TREE_PUBLIC,DECL_WEAK,DECL_COMDAT, visibility, and interposability as an availability level (symtab_node::get_availability,AVAIL_INTERPOSABLE, declared ingcc/cgraph.h); the dump below shows them. - rustc 1.94 keeps its own
Linkageenumeration and translates it withlinkage_to_llvm(compiler/rustc_codegen_llvm/src/base.rs), applied to every item incompiler/rustc_codegen_llvm/src/mono_item.rs(predefine_static,predefine_fn).
Find where LLVM does it. In llvm/include/llvm/IR/GlobalValue.h, find isDiscardableIfUnused. Question: which linkages does it list?
llvm-link resolving weak, linkonce_odr and available_externally
Reproduce (llvm-link 23.1.2):
cat > a.ll <<'EOF'
@x = weak global i32 1
@k = internal global i32 10
define linkonce_odr i32 @f() {
ret i32 1
}
define i32 @use_a() {
%v = load i32, ptr @k
ret i32 %v
}
EOF
cat > b.ll <<'EOF'
@x = global i32 2
@k = internal global i32 20
define linkonce_odr i32 @f() {
ret i32 1
}
define available_externally i32 @g() {
ret i32 5
}
define i32 @use_b() {
%v = load i32, ptr @k
%w = call i32 @g()
%s = add i32 %v, %w
ret i32 %s
}
EOF
printf 'define i32 @use_a() {\n ret i32 0\n}\n' > c.ll
llvm-link -S a.ll b.ll
llvm-link -S a.ll c.ll
Output (complete):
; ModuleID = 'llvm-link'
source_filename = "llvm-link"
@k = internal global i32 10
@x = global i32 2
@k.3 = internal global i32 20
define i32 @use_a() {
%v = load i32, ptr @k, align 4
ret i32 %v
}
define i32 @use_b() {
%v = load i32, ptr @k.3, align 4
%w = call i32 @g()
%s = add i32 %v, %w
ret i32 %s
}
define available_externally i32 @g() {
ret i32 5
}
error: Linking globals named 'use_a': symbol multiply defined!
What to notice: the strong @x = 2 replaced the weak one (step 2 of the Section 3 trace); both @ks survive because local names are renamed, not resolved (@k.3); the unused linkonce_odr @f vanished because it is discardable; the second command fails because two strong definitions conflict (Algorithm 9.1.4's error case).
GCC's view of the same linkage facts
Reproduce (gcc 14.2.0, Ubuntu 24.04):
cat > gl.c <<'EOF'
int counter;
static int hits = 3;
__attribute__((weak)) int tunable = 7;
__attribute__((visibility("hidden"))) int internal_api = 1;
static int helper(int x) { return x + hits; }
int bump(int x) { counter += helper(x) + tunable + internal_api; return counter; }
EOF
gcc-14 -O0 -fdump-ipa-cgraph=stdout -c gl.c -o /dev/null | grep -E "^[a-z_]+/[0-9]+ \(|Visibility" | head -12
Output (abridged: the first 12 lines):
bump/5 (bump)
Visibility: force_output semantic_interposition no_reorder public
helper/4 (helper)
Visibility: force_output semantic_interposition no_reorder
internal_api/3 (internal_api)
Visibility: force_output semantic_interposition no_reorder public visibility_specified visibility:hidden
tunable/2 (tunable)
Visibility: force_output semantic_interposition no_reorder public weak
hits/1 (hits)
Visibility: force_output semantic_interposition no_reorder
counter/0 (counter)
Visibility: force_output semantic_interposition no_reorder public
What to notice: GCC stores linkage as independent flags (public = non-local, weak, visibility:hidden) rather than one enumeration; static functions and variables simply lack public. semantic_interposition is GCC's default for ELF, the counterpart of LLVM's dso_preemptable.
Functions, basic blocks and SSA values¶
LLVM
llvm/include/llvm/IR/Value.h (Value, with its use list) and llvm/include/llvm/IR/Use.h implement Definition 9.1.6 directly: every operand is a Use object linked into its value's use list. The printer's numbering is class SlotTracker in llvm/lib/IR/AsmWriter.cpp (SlotTracker::processFunction), and the parser's check is LLParser::PerFunctionState::setInstName together with LLParser::checkValueID in llvm/lib/AsmParser/LLParser.cpp (LLVM 23.1.2) [LLVM-LLParser].
- GCC GIMPLE in SSA form names each SSA version
name_N(s_15,s_5in Lesson 9.8), stored asSSA_NAMEtrees with immediate-use lists (gcc/ssa-iterators.h). - Cranelift numbers values
v0, v1, …globally per function; block parameters replace phis (cranelift/codegen/src/ir/dfg.rs,DataFlowGraph).
Find where LLVM does it. In llvm/lib/AsmParser/LLParser.cpp, find the error message that contains "expected to be numbered". Question: after %5, what is the smallest number the parser accepts for the next unnamed instruction?
Slot numbers: gaps accepted, dense numbers printed
Reproduce (llvm-as and llvm-dis 23.1.2):
printf 'define i32 @f(i32, i32 %%b) {\n %%3 = add i32 %%0, %%b\n ret i32 %%3\n}\n' > gap.ll
llvm-as gap.ll -o - | llvm-dis -o - | tail -4
printf 'define i32 @f(i32) {\n %%5 = add i32 %%0, 1\n %%3 = add i32 %%5, 1\n ret i32 %%3\n}\n' > back.ll
llvm-as back.ll -o /dev/null
Output (complete):
define i32 @f(i32 %0, i32 %b) {
%2 = add i32 %0, %b
ret i32 %2
}
llvm-as: back.ll:3:3: error: instruction expected to be numbered '%6' or greater
%3 = add i32 %5, 1
^
What to notice: the entry block is unnamed and takes slot %1, so the first unnamed instruction is %2; the parser accepted the gap (%3) and the printer renumbered densely (Algorithm 9.1.7 and Corollary 9.1.11). A number that goes backwards is rejected, because the parser relies on increasing numbers to tell a new definition from a forward reference.
8. Comparison¶
| 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 |
Choose the module-as-unit design when the IR must outlive one compiler invocation (LTO, JIT, caching). Choose the full object-file linkage model when you compile C/C++ or anything that links with it; a closed-world language can get away with "exported or not", as WebAssembly does (Lesson 9.8). Choose phis over block arguments when you want LLVM's ecosystem; choose block arguments for a new IR, where they make CFG edits simpler (Lesson 9.8).
9. Assessment¶
| Technique | Quiz ids (solutions/quizzes/ch09.yaml) |
Drill | Flashcard tag | Exercises |
|---|---|---|---|---|
| Module structure | module-components, find-undefined-global |
./course drill ir-validity (undefined values) |
module |
E1 (SPEC) |
| Globals, linkage and visibility | linkage-resolution, linkage-discardable, find-discardable |
— (see below) | linkage |
— |
| Functions, basic blocks and SSA values | slot-numbering, ssa-def-count |
./course drill ir-validity --difficulty hard (redefinition, undefined values) |
ssa-values |
E1, E2, F5 |
Linkage resolution has no drill of its own: its algorithm has one decision per name and a quiz question traces it completely (linkage-resolution); the drill budget goes to GEP, poison and validity, where randomized practice pays off.
A global's name is its address
@counter has type ptr, not i32. add i32 @counter, 1 is a type error; you load i32, ptr @counter first. The same holds for functions: @sum_pos is a pointer to code, which is why a call can take any pointer value as its callee (Lesson 9.5).
References¶
See the chapter references.