Lesson 9.4 — Memory and addresses: alloca, load, store, atomics, GEP and casts¶

Techniques: alloca, load and store (and when memory becomes registers); atomics, orderings and volatile; getelementptr in full (index semantics, inbounds/nusw/nuw, struct vs array indexing, the move to getelementptr i8); casts · Pebble uses: all of them (arrays and structs through GEP, locals through alloca until mem2reg) · Lab: E2, E3, E9 · Prerequisites: Lesson 9.2 (sizes, alignments, Theorem 9.2.14) · Time: 5 hours

Where is s[1].Z.B[5][13]? The LangRef's own example asks it for

struct RT { char A; int B[10][20]; char C; };
struct ST { int X; double Y; struct RT Z; };
int *foo(struct ST *s) { return &s[1].Z.B[5][13]; }

and clang answers, at -O0, with a chain of getelementptr instructions that follow the C expression, and at -O2 with a single one: getelementptr inbounds nuw i8, ptr %s, i64 1296. Both are right; the second is what the first means on x86-64. This lesson explains how 1296 follows from the data layout (Theorem 9.4.5), what inbounds and nuw promise, why LLVM 23 prefers the byte form, and the rest of LLVM's memory model: stack slots, loads and stores, atomics and casts.

1. Problem and motivation¶

LLVM IR keeps registers in SSA form (Lesson 9.1) and everything else in memory: a flat, byte-addressed space per address space, divided into allocated objects (globals, allocas, heap blocks) [LLVM-LangRef, §Allocated Objects]. Front ends lower every variable whose address matters, and often every variable, to memory, and let the optimizer promote what it can. Addresses are computed by one instruction, getelementptr (GEP), which is pure arithmetic: it never touches memory, which is what makes it easy to analyze and hoist [LA04, §2.2].

Alloca, load and store¶

alloca reserves a stack object in the current frame, load and store read and write memory through a pointer with an explicit type and alignment. Emitting every local through an alloca frees front ends from building SSA themselves: clang at -O0 does exactly that, and mem2reg/SROA turn the promotable slots into SSA values (Ch 16).

Atomics and volatile¶

Concurrent programs need loads and stores with ordering guarantees. LLVM adopted the C++11 memory model in 2011 (LLVM 3.0): atomic loads and stores with orderings, cmpxchg, atomicrmw and fence [LLVM-Atomics; BA08]. volatile is a different, older idea: accesses the optimizer may not add, remove or reorder among themselves, for memory-mapped I/O, not for threads.

GetElementPtr¶

Address arithmetic in C is typed: &s[1].Z.B[5][13] scales each index by an element size. LLVM's GEP carries the type and the indices so that analyses can see which subobject is addressed, not just a number. That design came with costs: the most-asked question about LLVM ("why does my GEP have a leading zero?", the reason the GEP FAQ exists [LLVM-GEP]) and redundant ways to write the same address. Since LLVM 19 the flags nusw and nuw join inbounds, and since then InstCombine rewrites GEPs toward a canonical byte-offset form getelementptr i8, ptr %p, i64 %off (a "ptradd"), because the type information turned out to be unused by analyses and in the way of canonicalization.

Casts¶

Values change type only through explicit casts: integer width changes (trunc, zext, sext), integer/float conversions, pointer/integer conversions (ptrtoint, inttoptr, and ptrtoaddr, new in LLVM 22), bitcast between same-sized types, and addrspacecast. Making them explicit keeps the typing rules of every other instruction trivial.

2. Definitions and algorithms¶

Alloca, load and store¶

Definition 9.4.1 (Memory, objects, load and store)

Memory in address space \(a\) is a map from addresses \([0, 2^{w_a})\) to bytes, where a byte is 8 bits each of which may also be poison (and a byte may carry pointer provenance). An allocated object is a contiguous range \([o, o + n)\) of addresses reserved by alloca, a global, or an allocation function; no object crosses the end of the address space and \(n\) fits in the signed index type. %p = alloca τ, align A creates a fresh object of \(\mathrm{alloc}(\tau)\) bytes in the current frame, aligned to \(A\) (or \(\mathrm{align}(\tau)\)), and returns its address. load τ, ptr %p, align A reads \(\mathrm{store}(\tau)\) bytes at \(p\) and interprets them as a \(\tau\); store τ %v, ptr %p, align A writes them. Loading or storing through a pointer that is not based on a live object containing the whole access, or that is misaligned for the stated align, is undefined behavior.

Algorithm 9.4.2 (Struct layout)

Input: a sized struct type \(S = \{\tau_0, \dots, \tau_{k-1}\}\) (or packed \(\langle\{\dots\}\rangle\)) and a data layout \(\mathit{DL}\).
Output: field offsets \(\mathrm{off}_S(0), \dots, \mathrm{off}_S(k-1)\), \(\mathrm{alloc}(S)\) and \(\mathrm{align}(S)\).
Precondition: every \(\tau_j\) is sized (Definition 9.2.2).
Postcondition: each field starts at a multiple of its alignment (1 if packed), fields do not overlap and appear in order, and \(\mathrm{alloc}(S)\) is the least multiple of \(\mathrm{align}(S)\) that covers them.
Invariant: before iteration \(j\), off is the first byte after field \(j - 1\) and A is the maximum alignment of fields \(0..j-1\).

function LayoutStruct(S = {τ0, …, τk-1}, packed, DL):
    off ← 0; A ← 1
    for j in 0..k-1:
        a ← 1 if packed else Align(τj)            # Algorithm 9.2.6
        off ← AlignTo(off, a)                      # padding before field j
        offset[j] ← off
        off ← off + AllocSize(τj)
        A ← max(A, a)
    if not packed: A ← max(A, DL[a].abi)           # the "a:" spec, 1 by default
    return offset, AlignTo(off, A), A              # tail padding up to the alignment

function AlignTo(x, a): return a · ceil(x / a)

GetElementPtr¶

Definition 9.4.3 (GEP index semantics)

Let %r = getelementptr [flags] T0, ptr %p, t0 %i0, t1 %i1, …, tk %ik in address space \(a\) with index width \(w\) (the idx of p[a] in the data layout). Define the indexed types: \(T_0\) is the source element type; \(T_1 = T_0\), because \(i_0\) steps over whole \(T_0\) objects and \(i_1\) indexes into \(T_0\); and, for \(j \ge 1\), \(T_{j+1}\) is field \(i_j\) of \(T_j\) if \(T_j\) is a struct (then \(i_j\) must be an i32 constant), or the element type of \(T_j\) if it is an array or vector. The offset of index \(j\) is

\[ o_0 = \mathrm{sext}_w(i_0) \cdot \mathrm{alloc}(T_0), \qquad o_j = \begin{cases} \mathrm{off}_{T_j}(i_j) & T_j \text{ a struct} \\ \mathrm{sext}_w(i_j) \cdot \mathrm{alloc}(T_{j+1}) & T_j \text{ an array or vector} \end{cases} \quad (j \ge 1), \]

where \(\mathrm{sext}_w\) sign-extends or truncates to \(w\) bits. The result is \(r = p \oplus_w \sum_{j=0}^{k} o_j\): the sum is taken modulo \(2^w\) and added to the low \(w\) bits of \(p\) (the other bits of \(p\) are unchanged). GEP never accesses memory.

Algorithm 9.4.4 (GEP byte offset)

Input: \(T_0\), constant indices \(i_0, \dots, i_k\), a data layout.
Output: \(\Delta = \sum_j o_j\) as a signed integer (before the reduction modulo \(2^w\)).
Precondition: the indices are valid for the types (struct indices in range).
Postcondition: \(\Delta\) is the byte distance from \(p\) to \(r\) when no wrapping occurs (Theorem 9.4.5).
Invariant: after processing index \(j\), cur \(= T_{j+1}\) and \(\Delta = \sum_{m \le j} o_m\).

function GepOffset(T0, [i0, i1, …, ik], DL):
    Δ ← i0 · AllocSize(T0)                  # the first index steps over whole T0 objects
    cur ← T0
    for j in 1..k:
        if cur is a struct:
            Δ ← Δ + LayoutStruct(cur).offset[ij]     # Algorithm 9.4.2
            cur ← field ij of cur
        else:                                          # array or vector
            cur ← element type of cur
            Δ ← Δ + ij · AllocSize(cur)
    return Δ

The drill gep-offset and the lab's E9 are this algorithm; its implementation is gep_offset in tools/course/lib/llvmir.py, checked against LLVM's constant folder.

Theorem 9.4.5 (The GEP byte-offset equation)

Let \(p\) point to the first byte of an array of objects of type \(T_0\) laid out by the data layout, and let the GEP of Definition 9.4.3 have indices that stay within their aggregates for \(j \ge 1\) (\(0 \le i_j < n_j\), where \(n_j\) is the number of fields or elements of \(T_j\)). If \(p + \Delta\) computed in the integers lies in \([0, 2^w)\), then \(r = p + \Delta\) with \(\Delta\) from Algorithm 9.4.4, and \(r\) is the address of the first byte of the subobject selected by the index path: element \(i_0\) of the array, then field or element \(i_1\) of it, and so on.

Proof

By induction on \(k\), the number of indices after the first. Write \(\mathrm{addr}(x)\) for the address of the first byte of subobject \(x\).

Base, \(k = 0\). Element \(i_0\) of an array of \(T_0\) starting at \(p\) is at \(p + i_0 \cdot \mathrm{alloc}(T_0)\), because consecutive elements are \(\mathrm{alloc}(T_0)\) bytes apart (Definition 9.2.7 and Theorem 9.2.14(b), which also covers negative \(i_0\) by symmetry of the arithmetic progression). This is \(p + o_0\).

Step. Assume the claim for the path \(i_0, \dots, i_{j-1}\): the subobject \(x\) of type \(T_j\) it selects starts at \(p + \sum_{m < j} o_m\). If \(T_j\) is a struct, Algorithm 9.4.2 places field \(i_j\) at \(\mathrm{addr}(x) + \mathrm{off}_{T_j}(i_j)\) (its postcondition: each field at its offset from the struct's start), so the new subobject starts at \(p + \sum_{m < j} o_m + o_j\). If \(T_j\) is an array \([n \times T_{j+1}]\) (or a vector), its element \(i_j\) is at \(\mathrm{addr}(x) + i_j \cdot \mathrm{alloc}(T_{j+1})\) by Theorem 9.2.14(b) (arrays have no padding between elements), again \(+ o_j\). Hence after the last index, \(\mathrm{addr} = p + \Delta\).

Wrapping. Definition 9.4.3 computes \(p \oplus_w \Delta\), i.e. \((p + \Delta) \bmod 2^w\) in the low bits. Under the hypothesis \(0 \le p + \Delta < 2^w\), the reduction is the identity, so \(r = p + \Delta\).

Definition 9.4.6 (GEP flags)

With \(o_j\) as in Definition 9.4.3, the partial sums \(S_j = \sum_{m \le j} o_m\) and the addresses \(A_j = p + S_j\):

nusw (no unsigned-signed wrap): every \(\mathrm{sext}\)/truncation of an index preserves its value, every multiplication \(i_j \cdot \mathrm{alloc}\) fits in \(w\)-bit signed range, every partial sum \(S_j\) fits in the signed range, and every \(A_j\) (unsigned \(p\) plus signed \(S_j\)) stays in \([0, 2^w)\).
nuw (no unsigned wrap): the same with all quantities read as unsigned: the multiplications and partial sums fit in \([0, 2^w)\) and so does every \(A_j\).
inbounds: nusw, and if some index is non-zero, \(p\) and every \(A_j\) are in bounds of the allocated object \(p\) is based on (inside it or one past its end).

If a flag's condition fails, the result is poison (Lesson 9.7), not undefined behavior. inbounds implies nusw and is printed without it.

Proposition 9.4.7 (When nuw follows from inbounds)

If a GEP is inbounds and all its offsets \(o_j\) are non-negative (for example, all indices are non-negative constants), then its nuw condition holds whenever its result is not poison.

Proof

Assume the inbounds conditions hold (otherwise the result is poison and there is nothing to show). Each \(o_j \ge 0\), so the partial sums are non-decreasing: \(0 \le S_0 \le S_1 \le \dots \le S_k\), and the addresses \(p \le A_0 \le \dots \le A_k\). By inbounds, \(p\) and \(A_k\) lie in or one past the end of one allocated object, and no object, including the address one past its end, crosses the unsigned end of the address space (Definition 9.4.1). Hence \(A_k < 2^w\) and every \(A_j\), and every \(S_j \le A_k - p < 2^w\), lie in the unsigned range; the multiplications produce the non-negative \(o_j \le S_k\), also in range. These are exactly the nuw conditions. This is why instcombine adds nuw to the constant-offset GEPs in the boxes below.

Definition 9.4.8 (Byte-offset form, 'ptradd')

A GEP is in byte-offset form if it has one index and its source element type is i8 (getelementptr [flags] i8, ptr %p, iW %off, meaning \(r = p \oplus_w \mathit{off}\)) or [n x i8] with one index (getelementptr [n x i8], ptr %p, i64 %i, meaning \(r = p \oplus_w n \cdot i\)). The proposed ptradd instruction (the LangRef already names ptradd among "standard pointer arithmetic" [LLVM-LangRef, §alloca]) is the first case as a separate opcode; in LLVM 23 it is spelled as a GEP.

Algorithm 9.4.9 (Canonicalizing GEPs to byte-offset form, as InstCombine does)

Input: %r = getelementptr flags T0, ptr %p, i0, …, ik.
Output: an equivalent sequence of GEPs in byte-offset form (or the unchanged GEP).
Precondition: \(T_0\) and the indexed types are sized with fixed sizes.
Postcondition: the final pointer equals \(r\) for all inputs, and each new GEP carries flags.
Invariant: after each emitted piece, the pieces emitted so far compute \(p \oplus_w \sum_{m \le j} o_m\) for the indices consumed so far.

function Canonicalize(gep):
    if T0 = i8 and k = 0: return gep                              # already canonical
    if all indices are constants:
        return getelementptr flags i8, ptr p, i64 GepOffset(T0, [i0..ik])       # one constant ptradd
    if k = 0:
        return getelementptr flags [AllocSize(T0) x i8], ptr p, i0              # scaled index
    # several indices, some variable: split at every variable index
    q ← p; pending ← 0
    for j in 0..k:
        if o_j is a constant (a struct field or a constant index): pending ← pending + o_j
        else:
            if pending ≠ 0: q ← getelementptr flags i8, ptr q, i64 pending; pending ← 0
            q ← getelementptr flags [AllocSize(T_{j+1}) x i8], ptr q, i_j   # (T0 for j = 0)
    if pending ≠ 0: q ← getelementptr flags i8, ptr q, i64 pending
    return q

Casts¶

Definition 9.4.10 (Casts)

cast	from → to	result
`trunc [nuw] [nsw]`	\(\texttt{i}N \to \texttt{i}M\), \(M < N\)	low \(M\) bits; poison if `nuw`/`nsw` and the value changes as unsigned/signed
`zext [nneg]`, `sext`	\(\texttt{i}N \to \texttt{i}M\), \(M > N\)	zero- or sign-extended; `zext nneg` is poison for a negative input
`fptrunc`, `fpext`	FP → narrower / wider FP	rounded / exact
`fptoui`, `fptosi`	FP → integer	truncated toward zero; poison if out of range
`uitofp [nneg]`, `sitofp`	integer → FP	rounded
`ptrtoint`	`ptr` → `iN`	the pointer's bits, zero-extended or truncated; captures address and provenance
`ptrtoaddr`	`ptr` → `iW` (index width)	the address bits only; captures the address but not provenance (LLVM 22)
`inttoptr`	`iN` → `ptr`	a pointer with that address (provenance: whatever the model assigns)
`bitcast`	same size, non-aggregate	the same bits reinterpreted (e.g. `float` ↔ `i32`, `<2 x i32>` ↔ `i64`)
`addrspacecast`	`ptr addrspace(a)` → `ptr addrspace(b)`	target-defined conversion

Atomics and volatile¶

Definition 9.4.11 (Atomic orderings and volatile)

An atomic load, store, atomicrmw, cmpxchg or fence carries an ordering from \(\texttt{unordered} \sqsubset \texttt{monotonic} \sqsubset \{\texttt{acquire}, \texttt{release}\} \sqsubset \texttt{acq\_rel} \sqsubset \texttt{seq\_cst}\) (loads may not be release/acq_rel, stores not acquire/acq_rel), and optionally a syncscope. monotonic is C++'s memory_order_relaxed: a single total order of modifications per address. A release store synchronizes-with an acquire load that reads its value, adding a happens-before edge. seq_cst operations additionally lie in one global total order. A volatile access may not be added, removed, or reordered relative to other volatile accesses; it implies nothing about atomicity or ordering with respect to other threads.

3. Worked example¶

The LangRef's GEP, traced (Algorithm 9.4.4). On x86-64, lay out the two structs first (Algorithm 9.4.2):

struct	field	type	align	alloc size	padding before	offset
`%struct.RT`	0	`i8`	1	1	0	0
	1	`[10 x [20 x i32]]`	4	800	3	4
	2	`i8`	1	1	0	804
	end		\(A = 4\)			805 → 808
`%struct.ST`	0	`i32`	4	4	0	0
	1	`double`	8	8	4	8
	2	`%struct.RT`	4	808	0	16
	end		\(A = 8\)			824 → 824

Then the GEP getelementptr %struct.ST, ptr %s, i64 1, i32 2, i32 1, i64 5, i64 13:

step	index	`cur` before	rule	\(o_j\)	\(\Delta\)
0	`i64 1`	`%struct.ST`	\(1 \cdot \mathrm{alloc}(\texttt{\%struct.ST})\)	824	824
1	`i32 2`	`%struct.ST`	field 2 offset	16	840
2	`i32 1`	`%struct.RT`	field 1 offset	4	844
3	`i64 5`	`[10 x [20 x i32]]`	\(5 \cdot \mathrm{alloc}([20 \times \texttt{i32}]) = 5 \cdot 80\)	400	1244
4	`i64 13`	`[20 x i32]`	\(13 \cdot \mathrm{alloc}(\texttt{i32}) = 13 \cdot 4\)	52	1296

That is the constant in clang's -O2 output (real-world box in the "GetElementPtr" section). Note the leading index: s[1] steps over one whole ST (824 bytes). Writing &s->Z needs index i64 0 first, which is the GEP FAQ's most common question [LLVM-GEP].

Canonicalization (Algorithm 9.4.9) on %q = getelementptr inbounds %struct.P, ptr %p, i64 %i, i32 2, i64 %j with %struct.P = type { i32, i64, [4 x i16] } on x86-64 (i32@0, i64@8, [4 x i16]@16, size 24):

step	index	constant?	action	emitted
0	`%i` over `%struct.P`	no	scaled ptradd, stride 24	`%q.split = getelementptr inbounds [24 x i8], ptr %p, i64 %i`
1	`i32 2`	yes: field offset 16	pending ← 16	—
2	`%j` over `[4 x i16]`	no	flush 16, then stride 2	`%q.split1 = getelementptr inbounds nuw i8, ptr %q.split, i64 16`, `%q = getelementptr inbounds [2 x i8], ptr %q.split1, i64 %j`

The real instcombine output below is exactly these three instructions; it also adds nuw to the constant piece (Proposition 9.4.7).

Memory to registers. In locals (box in "Alloca, load and store"), clang at -O0 gives x, y, z and buf stack slots. mem2reg promotes only the slots whose uses are all non-volatile loads and stores into the slot, all of one type (lifetime markers are also allowed; isAllocaPromotable does not even require that type to be the slot's): x.addr and y. z escapes into consume(&z); buf is accessed through GEPs. SROA then splits buf into scalars because every GEP index is constant.

Try it

./course drill gep-offset --seed 9 --difficulty hard --solution traces Algorithm 9.4.4 on packed structs and a negative first index; lab task E9 has you write the GEPs yourself.

4. Invariants and correctness¶

Alloca, load and store¶

Proposition 9.4.12 (When an alloca is promotable)

Let %a = alloca τ be used only as the pointer operand of load τ, ptr %a and store τ %v, ptr %a instructions that are not volatile, and never stored as a value, passed to a call, or used by a GEP or cast. Then every load of %a reads the value of the most recent store to %a on the execution path (or poison/undef if none), so the loads can be replaced by SSA values computed from the stores.

Proof

%a is a fresh object (Definition 9.4.1), so only pointers based on %a may access it. By hypothesis the only such pointer is %a itself, and it is used only by loads and stores of the full type \(\tau\) at offset 0; no other instruction, and no callee, can obtain a pointer to the object. Hence the object's contents change only at those stores, each overwriting all \(\mathrm{store}(\tau)\) bytes, and a load returns what the last executed store wrote (loading from uninitialized memory "produces an undefined value" [LLVM-LangRef, §alloca]). "The last store on the path" is a dataflow fact over the CFG that SSA construction materializes with phis at the iterated dominance frontier of the stores (Ch 16). isAllocaPromotable in llvm/lib/Transforms/Utils/PromoteMemoryToRegister.cpp checks these conditions, slightly relaxed: all accesses must use one type (not necessarily \(\tau\)), and lifetime markers and droppable uses are allowed.

Atomics and volatile¶

Proposition 9.4.13 (Hoisting a non-atomic load out of a loop)

Let a loop contain a non-atomic, non-volatile load from address \(x\) that executes whenever the loop is entered (for example, in the header), and no instruction that may write \(x\) or synchronize (no atomic operation stronger than monotonic, no fence, no call). Replacing the load by one load in the preheader, just before the loop, is a refinement.

Proof

The hoisted load executes exactly when the loop is entered, and then the original executes its load at least once, so the transformation adds no access (and hence no UB from an invalid address). Consider any execution of the transformed program and the loop's iterations in the original. Case 1: no other thread writes \(x\) during the loop. Then every original load sees the same last write (the one visible before the loop), so each returns the value the hoisted load returned. Case 2: another thread writes \(x\) while the loop runs. Nothing in the loop synchronizes, so that write is not ordered by happens-before with the loads that could see it; each such load may see both it and the earlier write. By the LangRef's rule for a non-atomic read that may see more than one write, the load returns undef [LLVM-LangRef, §Memory Model for Concurrent Operations], and undef may be refined to the hoisted value. In both cases every value the transformed program reads is allowed for the original, so the transformation is a refinement.

The real-world box in "Atomics and volatile" shows the consequence: while (!flag) {} on a plain int becomes an infinite loop after one load, while an acquire load stays inside the loop. The same model forbids the converse direction of transformation: introducing a store to a location that might not otherwise be written is not allowed, because another thread's load could then see two writes.

GetElementPtr¶

Theorem 9.4.5 is the correctness statement of Algorithm 9.4.4. Its companion for Algorithm 9.4.9:

Theorem 9.4.14 (Canonicalization preserves the address and the flags)

The GEP sequence produced by Algorithm 9.4.9 computes the same pointer as the original GEP for every input. If the original GEP is inbounds (respectively nuw) and its result is not poison, then no piece's result is poison.

Proof

Address. The pieces add, in order, constant offsets and scaled variable offsets whose sum is \(\sum_j o_j\): constant struct offsets and constant array steps are accumulated into pending exactly as Algorithm 9.4.4 accumulates them, and each variable index \(i_j\) is scaled by \(\mathrm{alloc}(T_{j+1})\) (or \(\mathrm{alloc}(T_0)\) for \(j = 0\)), which is what [n x i8] with \(n\) = that alloc size does. Addition modulo \(2^w\) is associative, so the final pointer is \(p \oplus_w \sum_j o_j\) (Definition 9.4.3).

Flags. Every piece ends at one of the original's intermediate addresses: a flushed constant piece ends at \(A_j\) for the last constant index \(j\) it absorbed, a scaled piece at \(A_j\) for its variable index \(j\). So each piece goes from some \(A_{j'}\) (or \(p\)) to some \(A_j\) with \(j' < j\), by the single offset \(A_j - A_{j'}\) (a scaled piece multiplies the same index by the same size as the original, so its multiplication is the original's). Case inbounds. Since the original is not poison, \(p\) and all \(A_j\) lie in (or one past) one allocated object. Then \(\lvert A_j - A_{j'} \rvert\) is at most the object's size, which fits in the signed index type (Definition 9.4.1), so the piece's offset does not wrap signed; the piece's address \(A_{j'} + (A_j - A_{j'}) = A_j\) is in bounds and in \([0, 2^w)\). These are the piece's nusw and inbounds conditions. Case nuw. The original's offsets, read as unsigned, never wrap when added, so its partial sums are non-decreasing; hence \(0 \le A_j - A_{j'} \le S_k < 2^w\) and \(A_j < 2^w\): the piece's nuw conditions hold. If the original was poison, pieces may be poison too, which is allowed (poison is refined by anything, Lesson 9.7).

When it breaks. Adding inbounds to a GEP that leaves its object makes the result poison, and poison flows into icmp and branch decisions (Lesson 9.7): comparing p + n with p + 4 to detect overflow is folded away when the GEPs are inbounds. C and C++ allow the front end to emit inbounds because pointer arithmetic outside an array is UB in those languages; a language with defined pointer wrap must not.

Casts¶

Proposition 9.4.15 (Round trips through casts)

For \(M > N\): (a) trunc of zext (or of sext) from \(\texttt{i}N\) to \(\texttt{i}M\) back to \(\texttt{i}N\) is the identity; (b) trunc nuw of a zext and trunc nsw of a sext are never poison; (c) sext of a trunc is the identity only on inputs that lie in the \(N\)-bit signed range.

Proof

(a) Extension keeps the low \(N\) bits and trunc returns them. (b) zext produces a value in \([0, 2^N)\), which trunc to \(N\) bits preserves as an unsigned number, so the nuw condition holds; similarly sext produces a value in \([-2^{N-1}, 2^{N-1})\), which is preserved as a signed number. (c) trunc keeps the low \(N\) bits; sext reproduces the original \(M\)-bit value iff bits \(N-1 \dots M-1\) were all equal, i.e. iff the value is in the \(N\)-bit signed range. The drill flags checks (b) by enumeration ("infer-trunc-flags").

ptrtoint/inttoptr round trips are not the identity in LLVM's memory model: inttoptr (ptrtoint p) has the same address as p but its provenance is not guaranteed to be p's, which is why LLVM 22 added ptrtoaddr (address without capturing provenance) and why GEP, not integer arithmetic, is the way to compute addresses [LHJ+18].

5. Complexity¶

Technique	Time (worst)	Time (typical)	Space	Variables
Promotability test (Proposition 9.4.12)	\(O(\lvert\mathrm{uses}(a)\rvert)\) per alloca	linear	\(O(1)\)	uses of the alloca
Struct layout (Algorithm 9.4.2)	\(O(k)\), cached per type	\(O(1)\) after the first	\(O(k)\)	\(k\) = fields
GEP offset (Algorithm 9.4.4)	\(O(k)\)	\(O(k)\)	\(O(1)\)	\(k\) = indices
Canonicalization (Algorithm 9.4.9)	\(O(k)\), at most \(2k + 1\) new GEPs	1–3 pieces	\(O(k)\)	\(k\) = indices
Atomics	\(O(1)\) per instruction; the cost is in the back end (fences, `lock` prefixes)	—	—	—

Proposition 9.4.16 (Cost of Algorithm 9.4.4 and output size of Algorithm 9.4.9)

Algorithm 9.4.4 performs \(k\) constant-time steps after the struct layouts it needs are cached; Algorithm 9.4.9 emits at most \(2v + 1 \le 2k + 3\) GEPs for a GEP with \(v\) variable indices.

Proof

Each index is visited once in both algorithms; a struct index costs one lookup in the cached layout (Proposition 9.2.15), an array index one multiplication. In Algorithm 9.4.9 every variable index emits at most one flush of pending and one scaled GEP, and the end emits at most one more constant GEP: \(2v + 1\) pieces, with \(v \le k + 1\).

Pathological input. A struct nested \(d\) levels deep with all-constant indices yields one i8 GEP no matter how deep; a GEP whose \(k + 1\) indices are all variable becomes \(k + 1\) scaled pieces, the worst case for Algorithm 9.4.9, which is why later passes (SeparateConstOffsetFromGEP, LSR) re-associate them. For atomics, the cost at scale is not in the IR: on x86-64 a seq_cst store costs an xchg (a full barrier) while a release store is a plain mov (box below), a difference of tens of cycles per access in contended code.

Alloca, load and store¶

SROA (scalar replacement of aggregates): splits aggregate allocas accessed with constant GEPs into scalars, then promotes them; handles buf in the example, which mem2reg cannot.
!nonnull, !range, !noundef, !align on loads (Lesson 9.6): facts about the loaded value; trade-off: wrong metadata makes the load poison or UB.
llvm.lifetime.start/end: mark when a stack object is live so the back end can overlap slots; in LLVM 23 they take only the pointer (the size operand was removed).

Atomics and volatile¶

syncscope("…") (GPU memory models): an atomic that synchronizes only within a workgroup; trade-off: target-specific semantics.
Memory model relaxation annotations (!mmra metadata, [LLVM-LangRef]): per-instruction tags that let a target relax the model; experimental.
unordered (Java's rules): no tearing, no ordering; allows most optimizations of plain loads while forbidding the "load returns undef on a race" rule.

GetElementPtr¶

inrange(S, E) on constant GEPs: restricts which accesses the pointer may make (C++ vtables); enables splitting vtable globals.
Vector GEPs getelementptr i8, <4 x ptr> %ps, <4 x i64> %offs: per-lane addresses for gathers and scatters.
Reassociating a trailing constant (what instcombine 23.1.2 does beyond Algorithm 9.4.9): when a constant index follows a variable one, as in getelementptr inbounds %struct.Q, ptr %p, i64 %i, i32 1, i64 %j, i32 1 with %struct.Q = type { i64, [8 x { i16, i32 }] }, the output is [72 x i8] for %i, then shl nsw i64 %j, 3, then one getelementptr i8 by the combined constant 12 and one by the shifted index, and those last two pieces carry no flags. Trade-off: constants are grouped for addressing modes, at the price of the inbounds facts on the pieces.
ptradd as an opcode (proposed): the byte-offset form of Definition 9.4.8 as its own instruction, which would retire typed GEPs entirely. As of LLVM 23 the IR still spells it getelementptr i8 (background as extra reading: [Pop24]).

Casts¶

Flags on casts: zext nneg, uitofp nneg, trunc nuw/nsw (Lesson 9.7) record facts InstCombine proved, so that later passes can, for example, turn a zext nneg back into a sext.
ptrtoaddr (LLVM 22): the address of a pointer without capturing its provenance, for pointer comparisons and hashing that should not pessimize alias analysis.

7. In real compilers¶

Alloca, load and store¶

LLVM

llvm/include/llvm/IR/Instructions.h — AllocaInst, LoadInst, StoreInst; llvm/lib/Transforms/Utils/PromoteMemoryToRegister.cpp — isAllocaPromotable (Proposition 9.4.12) and PromoteMem2Reg::run; llvm/lib/Transforms/Scalar/SROA.cpp — SROA (LLVM 23.1.2) [LLVM-Mem2Reg].

GCC 15: locals are VAR_DECLs that become SSA names directly when they are "GIMPLE registers" (address not taken, is_gimple_reg); others stay in memory and are accessed through MEM_REFs. The "into SSA" pass is gcc/tree-into-ssa.cc.
rustc: MIR locals are lowered to allocas only if they are not "SSA-like" (compiler/rustc_codegen_ssa/src/mir/analyze.rs, non_ssa_locals); others go straight to LLVM values, so rustc's -O0 IR has fewer allocas than clang's.

Find where LLVM does it. Open llvm/lib/Transforms/Utils/PromoteMemoryToRegister.cpp and find isAllocaPromotable. Question: is a volatile load of the alloca allowed?

mem2reg and SROA on stack slots

Reproduce (clang 23.1.2, opt 23.1.2):

cat > mem.c <<'EOF'
void consume(int *p);
int locals(int x) {
  int y = x * 2;        /* scalar, address never taken: promotable      */
  int z = x + 1;        /* address escapes to consume(): stays in memory */
  int buf[4] = {x, y, z, 0};
  consume(&z);
  return y + z + buf[2];
}
EOF
clang-23 --target=x86_64-unknown-linux-gnu -O0 -Xclang -disable-O0-optnone -fno-discard-value-names \
  -S -emit-llvm mem.c -o mem.ll
opt -passes=mem2reg -S mem.ll | sed -n '/^define/,/^}/p' | grep -E "alloca|define"
opt -passes=sroa -S mem.ll | sed -n '/^define/,/^}/p'

Output (complete):

define dso_local i32 @locals(i32 noundef %x) #0 {
  %z = alloca i32, align 4
  %buf = alloca [4 x i32], align 16
define dso_local i32 @locals(i32 noundef %x) #0 {
entry:
  %z = alloca i32, align 4
  %mul = mul nsw i32 %x, 2
  %add = add nsw i32 %x, 1
  store i32 %add, ptr %z, align 4
  %0 = load i32, ptr %z, align 4
  call void @consume(ptr noundef %z)
  %1 = load i32, ptr %z, align 4
  %add3 = add nsw i32 %mul, %1
  %add4 = add nsw i32 %add3, %0
  ret i32 %add4
}

What to notice: after mem2reg, %x.addr and %y are gone (Proposition 9.4.12) but %z (escapes) and %buf (GEP users) remain. SROA splits %buf into its four elements, forwards the stored values, and deletes it; %z survives both passes, and the value of buf[2] is the load of %z before the call, while z itself is reloaded after it, because consume may have changed it.

Atomics and volatile¶

LLVM

llvm/include/llvm/IR/Instructions.h — AtomicRMWInst, AtomicCmpXchgInst, FenceInst, and the AtomicOrdering enum in llvm/include/llvm/Support/AtomicOrdering.h; llvm/lib/CodeGen/AtomicExpandPass.cpp expands atomics the target cannot do natively (LLVM 23.1.2) [LLVM-Atomics].

GCC 15: atomics are builtins (__atomic_load_4 …) carried through GIMPLE as calls with a memory-model argument (gcc/builtins.cc, expand_builtin_atomic_load), not as flagged loads.
Cranelift 37: atomic_load, atomic_store, atomic_rmw, atomic_cas instructions, all sequentially consistent (Wasm threads need no weaker orders).

Find where LLVM does it. In llvm/include/llvm/Support/AtomicOrdering.h, find the function that decides whether one ordering is stronger than another. Question: is acquire stronger than release?

Orderings in IR and in x86-64 code

Reproduce (clang 23.1.2, llc 23.1.2):

cat > atom.c <<'EOF'
int ready, data;
volatile int *mmio;
void publish(int v) {
  data = v;
  __atomic_store_n(&ready, 1, __ATOMIC_RELEASE);
}
int consume(void) {
  while (!__atomic_load_n(&ready, __ATOMIC_ACQUIRE)) {}
  return data;
}
int bump(void) { return __atomic_fetch_add(&ready, 1, __ATOMIC_SEQ_CST); }
void sc_store(void) { __atomic_store_n(&ready, 2, __ATOMIC_SEQ_CST); }
int cas(int expect) {
  return __atomic_compare_exchange_n(&ready, &expect, 7, 0, __ATOMIC_ACQ_REL, __ATOMIC_ACQUIRE);
}
int poll(void) { return *mmio + *mmio; }
EOF
clang-23 --target=x86_64-unknown-linux-gnu -O1 -S -emit-llvm atom.c -o atom.ll
grep -E "atomic|cmpxchg|volatile" atom.ll
llc -O1 atom.ll -o - | grep -E "xchg|lock|movl.*ready"

Output (complete):

  store atomic i32 1, ptr @ready release, align 4
  %2 = load atomic i32, ptr @ready acquire, align 4
  %1 = atomicrmw add ptr @ready, i32 1 seq_cst, align 4
  store atomic i32 2, ptr @ready seq_cst, align 4
  %2 = cmpxchg ptr @ready, i32 %0, i32 7 acq_rel acquire, align 4
  %2 = load volatile i32, ptr %1, align 4, !tbaa !9
  %3 = load volatile i32, ptr %1, align 4, !tbaa !9
    movl    $1, ready(%rip)
    movl    ready(%rip), %eax
    lock        xaddl   %eax, ready(%rip)
    xchgl   %eax, ready(%rip)
    lock        cmpxchgl    %edx, ready(%rip)

What to notice: every ordering of Definition 9.4.11 is part of the instruction. On x86-64 (a strong hardware model) release stores and acquire loads are ordinary movs, but a seq_cst store needs xchg. The two volatile loads of *mmio are both kept; two plain loads would be merged.

A plain load is hoisted out of a spin loop; an acquire load is not

Reproduce (clang 23.1.2):

cat > spin.c <<'EOF'
int plain_flag, atomic_flag;
void wait_plain(void)  { while (!plain_flag) {} }
void wait_atomic(void) { while (!__atomic_load_n(&atomic_flag, __ATOMIC_ACQUIRE)) {} }
EOF
clang-23 --target=x86_64-unknown-linux-gnu -O1 -fno-discard-value-names -S -emit-llvm spin.c -o - \
  | sed -n '/^define/,/^}/p'

Output (complete):

define dso_local void @wait_plain() local_unnamed_addr #0 {
entry:
  %0 = load i32, ptr @plain_flag, align 4, !tbaa !9
  %tobool.not = icmp eq i32 %0, 0
  br i1 %tobool.not, label %while.cond, label %while.end, !llvm.loop !10

while.cond:                                       ; preds = %entry, %while.cond
  br label %while.cond

while.end:                                        ; preds = %entry
  ret void
}
define dso_local void @wait_atomic() local_unnamed_addr #1 {
entry:
  br label %while.cond

while.cond:                                       ; preds = %while.cond, %entry
  %0 = load atomic i32, ptr @atomic_flag acquire, align 4
  %tobool.not = icmp eq i32 %0, 0
  br i1 %tobool.not, label %while.cond, label %while.end, !llvm.loop !13

while.end:                                        ; preds = %while.cond
  ret void
}

What to notice: Proposition 9.4.13 in action: the plain load was hoisted out of the loop, leaving while.cond: br label %while.cond, an infinite loop if the flag starts at 0. The acquire load synchronizes, so it stays in the loop.

GetElementPtr¶

LLVM

llvm/lib/IR/Operator.cpp — GEPOperator::accumulateConstantOffset implements Algorithm 9.4.4 for constant indices; llvm/lib/IR/DataLayout.cpp — StructLayout::StructLayout implements Algorithm 9.4.2; llvm/lib/Transforms/InstCombine/InstructionCombining.cpp — InstCombinerImpl::visitGetElementPtrInst implements Algorithm 9.4.9 ("Canonicalize constant GEPs to i8 type", shouldCanonicalizeGEPToPtrAdd, "Canonicalize gep %T to gep [sizeof(%T) x i8]") (LLVM 23.1.2) [LLVM-InstCombine, LLVM-DataLayout].

GCC 15: address arithmetic is POINTER_PLUS_EXPR (a byte offset, like ptradd) plus MEM_REF/ARRAY_REF/COMPONENT_REF in memory references; the IVOPTS pass rewrites them to TARGET_MEM_REFs (the ivtmp.9_6 + 8 in Lesson 9.8's GIMPLE).
Cranelift 37: no GEP; address arithmetic is iadd on integers, plus load/store with a constant offset operand (Lesson 9.8's CLIF).

Find where LLVM does it. In llvm/lib/Transforms/InstCombine/InstructionCombining.cpp, find shouldCanonicalizeGEPToPtrAdd. Question: for which type of source element does it always return true, so that such GEPs become an explicit llvm.vscale multiplication?

The LangRef's GEP at -O0 and -O2

Reproduce (clang 23.1.2):

cat > gepfaq.c <<'EOF'
struct RT { char A; int B[10][20]; char C; };
struct ST { int X; double Y; struct RT Z; };
int *foo(struct ST *s) { return &s[1].Z.B[5][13]; }
int *bar(struct ST *s, long i, long j) { return &s->Z.B[i][j]; }
EOF
for O in 0 2; do
  clang-23 --target=x86_64-unknown-linux-gnu -O$O -fno-discard-value-names -S -emit-llvm gepfaq.c -o - \
    | grep -E "^%struct|getelementptr"
done

Output (complete):

%struct.ST = type { i32, double, %struct.RT }
%struct.RT = type { i8, [10 x [20 x i32]], i8 }
  %arrayidx = getelementptr inbounds %struct.ST, ptr %0, i64 1
  %Z = getelementptr inbounds nuw %struct.ST, ptr %arrayidx, i32 0, i32 2
  %B = getelementptr inbounds nuw %struct.RT, ptr %Z, i32 0, i32 1
  %arrayidx1 = getelementptr inbounds [10 x [20 x i32]], ptr %B, i64 0, i64 5
  %arrayidx2 = getelementptr inbounds [20 x i32], ptr %arrayidx1, i64 0, i64 13
  %Z = getelementptr inbounds nuw %struct.ST, ptr %0, i32 0, i32 2
  %B = getelementptr inbounds nuw %struct.RT, ptr %Z, i32 0, i32 1
  %arrayidx = getelementptr inbounds [10 x [20 x i32]], ptr %B, i64 0, i64 %1
  %arrayidx1 = getelementptr inbounds [20 x i32], ptr %arrayidx, i64 0, i64 %2
  %arrayidx2 = getelementptr inbounds nuw i8, ptr %s, i64 1296
  %B = getelementptr inbounds nuw i8, ptr %s, i64 20
  %arrayidx = getelementptr inbounds [80 x i8], ptr %B, i64 %i
  %arrayidx1 = getelementptr inbounds [4 x i8], ptr %arrayidx, i64 %j

What to notice: at -O0 clang emits one GEP per C operator, with the leading i32 0 / i64 0 for "the object %p points to"; field GEPs get nuw from clang (non-negative field offsets, Proposition 9.4.7), array GEPs do not (C indices may be negative). At -O2 the constant path folds to the 1296 of the Section 3 trace, and the variable one becomes the byte-offset form: 20 (field Z at 16 plus B at 4), then strides of 80 bytes ([20 x i32]) and 4 bytes.

instcombine: constant GEPs to i8, variable GEPs to [n x i8], and flag-based folds

Reproduce (opt 23.1.2):

cat > canon.ll <<'EOF'
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"
%struct.P = type { i32, i64, [4 x i16] }
define ptr @field(ptr %p) {
  %q = getelementptr inbounds %struct.P, ptr %p, i64 0, i32 1
  ret ptr %q
}
define ptr @elem(ptr %p, i64 %i) {
  %q = getelementptr inbounds i64, ptr %p, i64 %i
  ret ptr %q
}
define ptr @nested(ptr %p, i64 %i, i64 %j) {
  %q = getelementptr inbounds %struct.P, ptr %p, i64 %i, i32 2, i64 %j
  ret ptr %q
}
define i1 @inb(ptr %p) {
  %q = getelementptr inbounds i8, ptr %p, i64 4
  %c = icmp eq ptr %q, null
  ret i1 %c
}
define i1 @plain(ptr %p) {
  %q = getelementptr i8, ptr %p, i64 4
  %c = icmp eq ptr %q, null
  ret i1 %c
}
define i1 @nuw_ult(ptr %p, i64 %x) {
  %q = getelementptr nuw i8, ptr %p, i64 %x
  %c = icmp ult ptr %q, %p
  ret i1 %c
}
EOF
opt -passes=instcombine -S canon.ll | grep -E "^define|^  "

Output (complete):

define ptr @field(ptr %p) {
  %q = getelementptr inbounds nuw i8, ptr %p, i64 8
  ret ptr %q
define ptr @elem(ptr %p, i64 %i) {
  %q = getelementptr inbounds [8 x i8], ptr %p, i64 %i
  ret ptr %q
define ptr @nested(ptr %p, i64 %i, i64 %j) {
  %q.split = getelementptr inbounds [24 x i8], ptr %p, i64 %i
  %q.split1 = getelementptr inbounds nuw i8, ptr %q.split, i64 16
  %q = getelementptr inbounds [2 x i8], ptr %q.split1, i64 %j
  ret ptr %q
define i1 @inb(ptr %p) {
  ret i1 false
define i1 @plain(ptr %p) {
  %q = getelementptr i8, ptr %p, i64 4
  %c = icmp eq ptr %q, null
  ret i1 %c
define i1 @nuw_ult(ptr %p, i64 %x) {
  ret i1 false

What to notice: the three shapes of Algorithm 9.4.9, and nuw added to the non-negative constant pieces (Proposition 9.4.7). The flags then pay off: an inbounds GEP with a non-zero offset cannot be null (only null is in bounds of null), and a nuw GEP cannot be below its base; without flags neither fold is valid, because the addition may wrap.

Casts¶

LLVM

llvm/include/llvm/IR/InstrTypes.h — CastInst and its opcode list; llvm/lib/IR/Instructions.cpp — CastInst::castIsValid (which casts are legal between which types); llvm/lib/Transforms/InstCombine/InstCombineCasts.cpp — InstCombinerImpl::visitZExt infers nneg (LLVM 23.1.2).

GCC 15: NOP_EXPR/CONVERT_EXPR for integer conversions (sign or zero extension decided by the source type's signedness), FLOAT_EXPR, FIX_TRUNC_EXPR, VIEW_CONVERT_EXPR for bit reinterpretation.
rustc MIR: Rvalue::Cast(CastKind, …) with kinds such as IntToInt, FloatToInt, PtrToPtr, Transmute (compiler/rustc_middle/src/mir/syntax.rs); Rust's as from float to int saturates, so rustc emits llvm.fptosi.sat, not fptosi.

Find where LLVM does it. In llvm/lib/IR/Instructions.cpp, find CastInst::castIsValid. Question: is bitcast from ptr to i64 valid?

C conversions and the casts they become

Reproduce (clang 23.1.2):

cat > casts.c <<'EOF'
long widen_s(int x) { return x; }
unsigned long widen_u(unsigned x) { return x; }
short narrow(long x) { return (short)x; }
double to_d(int x) { return x; }
int from_d(double d) { return (int)d; }
float shrink(double d) { return (float)d; }
unsigned long addr(int *p) { return (unsigned long)p; }
int *back(unsigned long a) { return (int *)a; }
unsigned bits(float f) { unsigned u; __builtin_memcpy(&u, &f, 4); return u; }
long index_of(unsigned char c, const long *t) { return t[c]; }
EOF
clang-23 --target=x86_64-unknown-linux-gnu -O1 -S -emit-llvm casts.c -o - \
  | grep -E "^define|^  %[0-9]+ = (sext|zext|trunc|sitofp|fptosi|fptrunc|ptrtoint|inttoptr|bitcast|getelementptr)" \
  | sed 's/ local_unnamed_addr #[0-9]* {//'

Output (complete):

define dso_local range(i64 -2147483648, 2147483648) i64 @widen_s(i32 noundef %0)
  %2 = sext i32 %0 to i64
define dso_local range(i64 0, 4294967296) i64 @widen_u(i32 noundef %0)
  %2 = zext i32 %0 to i64
define dso_local noundef signext i16 @narrow(i64 noundef %0)
  %2 = trunc i64 %0 to i16
define dso_local noundef double @to_d(i32 noundef %0)
  %2 = sitofp i32 %0 to double
define dso_local i32 @from_d(double noundef %0)
  %2 = fptosi double %0 to i32
define dso_local noundef float @shrink(double noundef %0)
  %2 = fptrunc double %0 to float
define dso_local noundef i64 @addr(ptr noundef %0)
  %2 = ptrtoint ptr %0 to i64
define dso_local noundef ptr @back(i64 noundef %0)
  %2 = inttoptr i64 %0 to ptr
define dso_local noundef i32 @bits(float noundef %0)
  %2 = bitcast float %0 to i32
define dso_local i64 @index_of(i8 noundef zeroext %0, ptr nofree noundef readonly captures(none) %1)
  %3 = zext i8 %0 to i64
  %4 = getelementptr inbounds nuw [8 x i8], ptr %1, i64 %3

What to notice: C's signedness becomes the choice of cast (sext for int, zext for unsigned). from_d is the only function whose result lacks noundef: fptosi of an out-of-range double is poison (Definition 9.4.10), so clang cannot promise a well-defined result. The type pun through memcpy became one bitcast. The table lookup's GEP is already in [8 x i8] form with nuw, because a zext index is non-negative.

8. Comparison¶

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

Measured in the lab (Section "Measurement" of SPEC, reference solution, x86-64): the memory-form Collatz loop is 110 bytes at llc -O0 and 77 at llc -O2, the register form 83 and 43; after opt -O2 both are the same code, because mem2reg turns one into the other.

Choose the memory form in a front end (it is what clang and pebblec emit) and let mem2reg/SROA build SSA. Choose atomics, never volatile, for cross-thread communication, and the weakest ordering that is correct. Choose inbounds whenever the source language makes out-of-object pointer arithmetic undefined; choose the byte-offset form when you generate IR from a layout you already computed (it is the canonical form anyway). Choose GEP over ptrtoint arithmetic always: it keeps provenance.

9. Assessment¶

Technique	Quiz ids (`solutions/quizzes/ch09.yaml`)	Drill	Flashcard tag	Exercises
Alloca, load and store	`promotable-alloca`, `find-promotable-volatile`	— (see below)	`memory`	E1 (`@collatz_steps_mem`), E2
Atomics and volatile	`hoist-plain-load`, `seqcst-store-x86`	— (see below)	`atomics`	—
GetElementPtr	`gep-offset-langref`, `gep-leading-zero`, `gep-canonical-form`, `gep-inbounds-null`	`./course drill gep-offset`	`gep`	E3, E9
Casts	`fptosi-poison`, `trunc-zext-roundtrip`	`./course drill flags` (cast flags)	`casts`	E5 (`fpext`, `sext`), E6

Promotability and memory orderings get quiz questions and lab work rather than a randomized drill: their instances are small and qualitative (does this alloca escape? which ordering synchronizes?), which a handful of well-chosen questions covers better than random generation.

GEP does not dereference, so it cannot 'follow' a pointer field

getelementptr %struct.Node, ptr %n, i64 0, i32 1 is the address of the next field. To reach n->next->key, you must load ptr the field and start a new GEP from the loaded pointer. A single GEP can never step through a pointer, because the pointee is in some other object.

References¶

See the chapter references.

Lesson 9.4 — Memory and addresses: alloca, load, store, atomics, GEP and casts¶

1. Problem and motivation¶

Alloca, load and store¶

Atomics and volatile¶

GetElementPtr¶

Casts¶

2. Definitions and algorithms¶

Alloca, load and store¶

GetElementPtr¶

Casts¶

Atomics and volatile¶

3. Worked example¶

4. Invariants and correctness¶

Alloca, load and store¶

Atomics and volatile¶

GetElementPtr¶

Casts¶

5. Complexity¶

6. Variants and refinements¶

Alloca, load and store¶

Atomics and volatile¶

GetElementPtr¶

Casts¶

7. In real compilers¶

Alloca, load and store¶

Atomics and volatile¶

GetElementPtr¶

Casts¶

8. Comparison¶

9. Assessment¶

References¶