Lesson 10.2 — Values, users, uses: def-use chains and RAUW¶

Techniques: use lists (Value/User/Use, def-use and use-def chains), operand layout (co-allocated vs hung-off operands), replace-all-uses-with (RAUW), value handles (WeakVH, WeakTrackingVH, AssertingVH, CallbackVH), metadata as value · Pebble uses: all five; every pass of Chapters 12–20 walks and rewrites def-use chains · Lab: Lab 10.2 (--def-use, RAUW in --rewrite-pow2) · Prerequisites: Lesson 10.1, Ch 9 SSA · Time: 3–4 hours

In the running example %b = mul i32 %a, %a and %c = sub i32 %b, %a. So %a has three uses: two in %b (operands 0 and 1) and one in %c (operand 1). An optimization that finds a cheaper value for %a must be able to reach all three and redirect them, in time proportional to three rather than to the size of the function. And the analyses that cached a pointer to %a must not be left pointing at a deleted object. LLVM keeps, for every value, a list of the places that use it. This lesson makes that list precise, proves the invariant every mutation must preserve, and shows what RAUW does to it.

1. Problem and motivation¶

SSA (Ch 9, Ch 16) gives each value one definition. Optimizations constantly need both directions of the def-use relation:

use-def: "what does this operand refer to?" This one is trivial: an operand is a pointer to its value.
def-use: "who uses this value?" This one needs an index.

Classic compilers built def-use chains on demand as a dataflow result. SSA-based compilers keep them up to date incrementally, so that a transformation which changes one operand pays \(O(1)\) to keep the index right [CFRWZ91, LA04].

Use lists¶

LLVM's answer is to reify each operand slot as a Use object that links into its value's list. Walking V->uses() visits every Use of V, and V->users() visits the users behind them [LLVM-PM, LLVM-Use]. Pebble's passes use this for everything: dead-code elimination asks "are there any users?", GVN redirects uses, and LICM moves instructions and asks where their users are.

Operand layout¶

Most instructions have a fixed number of operands, known when they are created. phi, switch and a few others grow. LLVM allocates fixed operands in the same block of memory as the instruction (co-allocated, just before the object) and stores growable operand arrays separately (hung off). This saves one allocation and one pointer per instruction for the common case [LLVM-PM, LLVM-User].

RAUW¶

"Replace all uses of \(X\) with \(Y\)" is the most common rewrite in an optimizer: constant folding, CSE, instruction simplification and SSA construction all end with it. With use lists it costs \(O(\lvert \mathrm{uses}(X) \rvert)\). It is correct only if \(Y\) is available wherever \(X\) was used, which is a dominance property this lesson proves [LLVM-Value].

Value handles¶

Analyses cache pointers to values in side tables, such as a DenseMap<Value *, Info>. When a value is deleted or replaced, those pointers go stale. Value handles are smart pointers that register themselves with the value, so they get notified of deletion and RAUW. They can then null themselves, follow the replacement, assert, or run a callback [LLVM-VH].

Metadata as value¶

Metadata (debug info, TBAA, loop hints) is not a Value and has no type. Some intrinsics still need metadata operands (for example, llvm.experimental.constrained.fadd takes a rounding mode), and some metadata needs to refer to SSA values. Two small wrappers bridge the gap: MetadataAsValue wraps metadata as a value of type metadata, and ValueAsMetadata wraps a value as metadata and follows RAUW [LLVM-Metadata].

2. Definitions and algorithms¶

Definition 10.2.1 (Value, user, use)

A value is any llvm::Value: an argument, a basic block, a constant, a global, an instruction, a MetadataAsValue. A user is a value with operands (llvm::User: constants with operands, globals with initializers, instructions). A use \(u\) is one operand slot of a user, with three fields:

\(\mathrm{val}(u)\): the value it currently refers to, or null;
\(\mathrm{user}(u)\): the user that contains it;
\(\mathrm{opno}(u) \in \{0, \dots, k-1\}\): its position among the user's \(k\) operands.

The operand list of a user \(U\) is \(\mathrm{ops}(U) = \langle u_0, \dots, u_{k-1} \rangle\) with \(\mathrm{user}(u_i) = U\) and \(\mathrm{opno}(u_i) = i\). A value \(v\) is tracked if it keeps a use list; in LLVM 23 every value except ConstantData (integer, FP and null-pointer literals, undef, poison, …) is tracked. For a tracked \(v\), \(\mathrm{uses}(v)\) is the use list, a sequence of uses (head first), and \(\mathrm{users}(v) = \langle \mathrm{user}(u) \mid u \in \mathrm{uses}(v) \rangle\) (a user appears once per use).

Definition 10.2.2 (Use-list links)

Each use \(u\) stores \(\mathrm{next}(u)\), the next use in the same list, and \(\mathrm{prev}(u)\), the address of the pointer that points to \(u\): either the list head field UseList of \(\mathrm{val}(u)\), or the Next field of the preceding use (Use **Prev in llvm/IR/Use.h). With this "pointer to the incoming pointer", unlinking is the same code whether or not \(u\) is first.

Algorithm 10.2.3 (Use::set)

Input: a use \(u\) and a value \(w\) (possibly null).
Output: \(\mathrm{val}(u) = w\).
Precondition: the def-use consistency invariant (Definition 10.2.4) holds.
Postcondition: the invariant holds; \(u\) is the head of \(\mathrm{uses}(w)\) if \(w\) is tracked; the relative order of all other uses in every list is unchanged.
Invariant: every list other than \(\mathrm{uses}(\mathrm{val}(u))\) and \(\mathrm{uses}(w)\) is untouched.

function RemoveFromList(u):                # Use::removeFromList
    if prev(u) ≠ null:
        *prev(u) ← next(u)                 # the incoming pointer skips u
        if next(u) ≠ null: prev(next(u)) ← prev(u)
        next(u) ← null; prev(u) ← null
function AddToList(u, head):               # Use::addToList(&V->UseList)
    next(u) ← *head
    if next(u) ≠ null: prev(next(u)) ← address of next(u)
    prev(u) ← head
    *head ← u                              # u becomes the first use
function Set(u, w):                        # Use::set
    RemoveFromList(u)
    val(u) ← w
    if w ≠ null and w is tracked: AddToList(u, address of w.UseList)

Definition 10.2.4 (Def-use consistency invariant)

The IR is def-use consistent if both of these hold:

For every live use \(u\): if \(\mathrm{val}(u) = v \ne \mathrm{null}\) and \(v\) is tracked, then \(u\) occurs exactly once in \(\mathrm{uses}(v)\). In every case, \(u \in \mathrm{ops}(\mathrm{user}(u))\) at position \(\mathrm{opno}(u)\) (the user owns \(u\)).
For every tracked value \(v\) and every \(u \in \mathrm{uses}(v)\): \(u\) is live and \(\mathrm{val}(u) = v\).

Equivalently, the use lists are exactly the inverse of the operand pointers, restricted to tracked values.

The running example is consistent

Built top to bottom, @f has \(\mathrm{uses}(\%a) = \langle (\%c, 1), (\%b, 1), (\%b, 0) \rangle\) and \(\mathrm{uses}(\%x) = \langle (\%d, 0), (\%a, 0) \rangle\) (head first; §3 derives them). Each listed pair is an operand of the named user that points back to the value, and every operand pointing to %a or %x is listed.

Use lists¶

Use lists of the running example, then RAUW and setOperand

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 uses.cpp $(llvm-config --ldflags --libs) \
  -Wl,-rpath,$(llvm-config --libdir) -o uses && ./uses

uses.cpp parses the running example, prints uses() of %a and %x, then runs %a->replaceAllUsesWith(%x), %c->setOperand(0, %y) and %a->eraseFromParent().

Output (complete):

%a: 3 uses: (%c, op 1) (%b, op 1) (%b, op 0)
%x: 2 uses: (%d, op 0) (%a, op 0)
-- RAUW %a -> %x
%a: 0 uses:
%x: 5 uses: (%b, op 0) (%b, op 1) (%c, op 1) (%d, op 0) (%a, op 0)
-- %c.setOperand(0, %y)
%b: 0 uses:
%y: 2 uses: (%c, op 0) (%a, op 1)
; ModuleID = '<string>'
source_filename = "<string>"

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

What to notice: the most recently created use comes first (Proposition 10.2.10). RAUW moved %a's three uses to the front of %x's list in reversed order (Theorem 10.2.12(c)). setOperand moved (%c, op 0) to the head of %y's list and left %b without uses. The (%a, op 0) entry left %x's list only when %a was erased.

Operand layout¶

Definition 10.2.5 (Co-allocated and hung-off operands)

A user with co-allocated (intrusive) operands is allocated as one block \([\,u_0, \dots, u_{k-1}, \text{object}\,]\), and \(u_i\) is found at address \(\&\text{object} - (k - i)\cdot\mathrm{sizeof}(\texttt{Use})\). A user with hung-off operands stores a pointer to a separately allocated array of \(\mathit{cap} \ge k\) uses, which can be reallocated when operands are added. In both layouts \(\mathrm{opno}(u)\) is computed, not stored: \(\mathrm{opno}(u) = u - \mathrm{ops}(\mathrm{user}(u))\), pointer arithmetic on Use *. (User::operator new(size_t, IntrusiveOperandsAllocMarker) vs HungOffOperandsAllocMarker in llvm/IR/User.h.)

Where the operands live

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 layout.cpp $(llvm-config --ldflags --libs) \
  -Wl,-rpath,$(llvm-config --libdir) -o layout && ./layout

Output (complete; the two hung-off offsets depend on the heap allocator):

sizeof(Use)=32 sizeof(Value)=24 sizeof(User)=24
add (co-allocated): operands=2, operand list starts at object-64 bytes
phi (hung off)    : operands=2, operand list starts at object+88 bytes
phi after growth  : operands=4, operand list starts at object-243288 bytes

What to notice: a Use is 32 bytes (value, next, prev, user). The add's two operands sit immediately before the object: \(-64 = -2 \times 32\) (Definition 10.2.5). The phi's array is a separate allocation, which moved when two more incoming values were added (growHungoffUses). The operands were copied into the new array and the old uses destroyed, and the use lists stayed consistent because each copy is a Set (Theorem 10.2.11). The copies went to the heads of their values' use lists, so growth also reorders use lists.

RAUW¶

Algorithm 10.2.6 (Replace all uses with)

Input: a tracked value \(X\) and a value \(Y\) with \(\mathrm{type}(Y) = \mathrm{type}(X)\) and \(Y \ne X\).
Output: every former use of \(X\) now refers to \(Y\).
Precondition: def-use consistency; \(Y\) does not (transitively, through constant expressions) contain \(X\).
Postcondition: Theorem 10.2.12.
Invariant: after each iteration, the uses processed so far refer to \(Y\), the rest are still in \(\mathrm{uses}(X)\) in their original order, and consistency holds.

function RAUW(X, Y):
    notify value handles of X (Algorithm 10.2.8)
    if X is used by metadata: redirect the ValueAsMetadata wrapper (§ Metadata as value)
    while uses(X) ≠ ⟨⟩:
        u ← head of uses(X)
        if user(u) is a constant (not a global):
            re-unique that constant with Y in place of X   # handleOperandChange
        else:
            Set(u, Y)                                     # Algorithm 10.2.3
    if X is a basic block: also update phi entries naming X

LLVM: Value::doRAUW in llvm/lib/IR/Value.cpp, which asserts New->getType() == getType() and !contains(New, this) [LLVM-Value].

Value handles¶

Definition 10.2.7 (Value handle kinds)

A value handle \(h\) is a pointer to a value \(v\) that registers itself in a per-value handle list (the context's ValueHandles map, with the value's HasValueHandle bit set). On the two events delete(\(v\)) and RAUW(\(v\), \(w\)) it reacts according to its kind:

kind	on delete(\(v\))	on RAUW(\(v\), \(w\))
`WeakVH`	becomes null	keeps \(v\)
`WeakTrackingVH`	becomes null	becomes \(w\)
`AssertingVH`	assertion failure (debug builds)	keeps \(v\)
`TrackingVH` (a wrapper around a `WeakTrackingVH`)	becomes null; a later dereference asserts	becomes \(w\)
`CallbackVH`	calls `deleted()`	calls `allUsesReplacedWith(w)`
`PoisoningVH`	marks itself poisoned (assertion builds); a later dereference asserts	keeps the pointer to \(v\), but is poisoned too

Algorithm 10.2.8 (Handle notification)

Input: an event (delete \(v\), or RAUW \(v \to w\)).
Output: every handle registered on \(v\) has reacted as in Definition 10.2.7.
Precondition: every live handle on \(v\) is in \(v\)'s handle list.
Postcondition: no WeakVH/WeakTrackingVH points to a deleted value; tracking handles on \(v\) now sit in \(w\)'s list.
Invariant: handles already processed are removed from \(v\)'s list (or moved to \(w\)'s).

function NotifyDelete(v):
    for h in handles(v):                       # ValueHandleBase::ValueIsDeleted
        case kind(h):
            Weak, WeakTracking (and so TrackingVH): h.ptr ← null; unlink h
            Callback: h.deleted()              # must unlink or reset h
            Asserting: report an error (debug builds)
function NotifyRAUW(v, w):
    for h in handles(v):                       # ValueHandleBase::ValueIsRAUWd
        case kind(h):
            WeakTracking, Tracking: h.ptr ← w; move h to handles(w)
            Callback: h.allUsesReplacedWith(w)
            otherwise: nothing

Handles react to RAUW and erase

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

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

Output (complete):

RAUW %a -> %b
  CallbackVH::allUsesReplacedWith(%b)
  WeakVH         -> %a
  WeakTrackingVH -> %b
erase %a
  CallbackVH::deleted()
  WeakVH         -> null
  WeakTrackingVH -> %b
sizeof(WeakVH)=24 sizeof(AssertingVH<Value>)=8

What to notice: the table of Definition 10.2.7 line by line. WeakVH ignores RAUW and nulls on delete, WeakTrackingVH follows RAUW (so it survives the delete, since it no longer points to %a), and the callback sees both events. The last line: in a build without LLVM_ENABLE_ABI_BREAKING_CHECKS (this Release build), AssertingVH is a plain 8-byte pointer and checks nothing. Its protection exists only in assertion builds.

Metadata as value¶

Definition 10.2.9 (MetadataAsValue, ValueAsMetadata)

MetadataAsValue::get(Ctx, MD) is the unique value of type metadata that wraps the metadata node MD, uniqued per context like a constant. ValueAsMetadata::get(V) is the unique metadata wrapping the value V: a ConstantAsMetadata for constants, a LocalAsMetadata for function-local values (arguments, instructions). A value wrapped as metadata has isUsedByMetadata() set, and RAUW redirects the wrapper to the new value (ValueAsMetadata::handleRAUW), so metadata follows value replacement without use lists [LLVM-Metadata].

Metadata operands of an intrinsic

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 mav.cpp $(llvm-config --ldflags --libs) \
  -Wl,-rpath,$(llvm-config --libdir) -o mav && ./mav

Output (complete):

arg 0: type=double isa<MetadataAsValue>=0
arg 1: type=double isa<MetadataAsValue>=0
arg 2: type=metadata isa<MetadataAsValue>=1 MDString="round.dynamic"
arg 3: type=metadata isa<MetadataAsValue>=1 MDString="fpexcept.strict"
same wrapper object: 1
LocalAsMetadata wraps: %x

What to notice: the rounding-mode and exception arguments of llvm.experimental.constrained.fadd are ordinary call operands whose values are MetadataAsValues of type metadata, wrapping MDStrings. Asking for the same wrapper again returns the same object: wrappers are uniqued, as in Theorem 10.1.11.

3. Worked example¶

The running example, created top to bottom by the parser. Each constructor sets its operands in order \(0, 1\) (Algorithm 10.2.3, Set, head insertion). The mutations are RAUW(%a, %x), %c->setOperand(0, %y), and erase(%a). A use is written user[opno].

flowchart LR
  x([%x]) --> a[%a = add]
  y([%y]) --> a
  a --> b[%b = mul]
  a --> b
  b --> c[%c = sub]
  a --> c
  x --> d[%d = xor]
  c --> d
  d --> r[ret]

Use lists¶

step	action	list after the step
1	create `%a`: push `%a[0]` on `%x`	`%x`: `%a[0]`
2	create `%a`: push `%a[1]` on `%y`	`%y`: `%a[1]`
3	create `%b`: push `%b[0]` on `%a`	`%a`: `%b[0]`
4	create `%b`: push `%b[1]` on `%a`	`%a`: `%b[1]` `%b[0]`
5	create `%c`: push `%c[0]` on `%b`	`%b`: `%c[0]`
6	create `%c`: push `%c[1]` on `%a`	`%a`: `%c[1]` `%b[1]` `%b[0]`
7	create `%d`: push `%d[0]` on `%x`	`%x`: `%d[0]` `%a[0]`
8	create `%d`: push `%d[1]` on `%c`	`%c`: `%d[1]`
9	create `ret`: push `ret[0]` on `%d`	`%d`: `ret[0]`

After step 9 the lists are the first two lines of the real-world box.

Operand layout¶

%b = mul %a, %a is co-allocated with two uses. With %b at address \(p\), \(u_0\) is at \(p - 64\) and \(u_1\) at \(p - 32\). For \(u_1\): \(\mathrm{opno}(u_1) = (p - 32 - (p - 64)) / 32 = 1\) (Definition 10.2.5).

RAUW¶

RAUW(%a, %x), Algorithm 10.2.6, starting from %a: %c[1] %b[1] %b[0] and %x: %d[0] %a[0]:

iteration	head of uses(`%a`)	`Set(u, %x)`	uses(`%a`) after	uses(`%x`) after
1	`%c[1]`	unlink, push on `%x`	`%b[1]` `%b[0]`	`%c[1]` `%d[0]` `%a[0]`
2	`%b[1]`	unlink, push	`%b[0]`	`%b[1]` `%c[1]` `%d[0]` `%a[0]`
3	`%b[0]`	unlink, push	⟨⟩	`%b[0]` `%b[1]` `%c[1]` `%d[0]` `%a[0]`
4	— (empty: stop)		⟨⟩	unchanged

Then %c->setOperand(0, %y): unlink %c[0] from %b (which becomes ⟨⟩), and push it on %y, giving %c[0] %a[1]. Finally erase(%a): its destructor unlinks %a[0] from %x and %a[1] from %y. The result is %x: %b[0] %b[1] %c[1] %d[0] and %y: %c[0].

Value handles¶

With WeakVH w1(%a), WeakTrackingVH w2(%a) and a CallbackVH w3(%a) registered: RAUW(%a, %b) moves \(w_2\) to %b's handle list and calls \(w_3\).allUsesReplacedWith(%b), while \(w_1\) stays on %a. Erase(%a) then finds \(w_1\) and \(w_3\) in %a's list: \(w_1 \leftarrow\) null, and \(w_3\).deleted() runs. This is exactly the real-world box's output.

Metadata as value¶

%s = call double @llvm.experimental.constrained.fadd.f64(double %x, double %y, metadata !"round.dynamic", metadata !"fpexcept.strict") has four uses: %x, %y, and two MetadataAsValue wrappers. Because the wrappers are uniqued, every constrained call in the module that says round.dynamic uses the same wrapper, so uses(wrapper) lists all of them.

Try it

./course drill use-lists --seed 3 --difficulty hard gives a similar function with a RAUW, a setOperand and an erase; --solution prints this table.

4. Invariants and correctness¶

Use lists¶

Proposition 10.2.10 (Use-list order)

If the uses of \(v\) were created by constructors or Set calls \(s_1, s_2, \dots, s_m\) (in time order) and none of them has since been removed, then \(\mathrm{uses}(v) = \langle s_m, \dots, s_2, s_1 \rangle\): most recent first.

Proof

By induction on \(m\). For \(m = 0\) the list is empty. Each Set onto \(v\) calls AddToList, which makes the new use the head and leaves the old list behind it unchanged (Algorithm 10.2.3). So after \(s_m\) the list is \(s_m\) followed by the list after \(s_{m-1}\), which is \(\langle s_{m-1}, \dots, s_1 \rangle\) by the hypothesis.

This order is an implementation detail. Bitcode records it with uselistorder directives only so that tools can reproduce it exactly (-preserve-bc-uselistorder). Passes must not depend on it for correctness, which is why Lab 10.2 sorts uses by position.

Theorem 10.2.11 (Consistency is preserved)

If the IR is def-use consistent (Definition 10.2.4), it stays consistent after each of these operations:

creating a user (whose constructor calls Set on each operand);
Set;
RemoveFromList followed by destroying the use (erasing a user);
relocating a hung-off operand array (growHungoffUses, which assigns each old use to its slot in the new array and then destroys the old array).

Proof

Set(u, w). RemoveFromList makes the incoming pointer of \(u\) skip it and fixes the successor's back-pointer, so the old list is still a well-formed list without \(u\) (the same argument as Lemma 10.1.13, with prev as the address of the incoming pointer). \(u\) now occurs in no list. AddToList inserts \(u\) once at the head of \(\mathrm{uses}(w)\). Clause 1 holds for \(u\) with \(\mathrm{val}(u) = w\). Clause 2 holds for the old value (it no longer lists \(u\)) and for \(w\) (it lists \(u\), and \(\mathrm{val}(u) = w\)). No other use changed its value or its list membership. Creation. A new use starts unlinked with a null value, which is trivially consistent, and the constructor then performs Sets. Destruction. ~Use calls RemoveFromList first, so no list keeps a pointer to the freed use. Relocation. growHungoffUses (llvm/lib/IR/User.cpp) copies the old array into the new one with std::copy, and Use::operator=(const Use &) is Set(new, val(old)). It then destroys the old uses with Use::zap, and each ~Use is a RemoveFromList. Every step is one of the cases above, so consistency holds, and every operand keeps its value. The list order does change: each relocated use is pushed at the head of its value's list, which is one more reason never to depend on use-list order. Ownership clause. \(u \in \mathrm{ops}(\mathrm{user}(u))\) holds because uses are created only inside their user's operand array (co-allocated or hung-off) and \(\mathrm{user}(u)\) is set once, at allocation.

Operand layout¶

The layout is correct when getOperandNo returns the operand's position and the list stays valid when a hung-off array moves. The first follows from Definition 10.2.5, since the array is contiguous. The second is the relocation case of Theorem 10.2.11.

RAUW¶

Theorem 10.2.12 (RAUW postconditions)

Let \(\mathrm{uses}(X) = \langle u_1, \dots, u_m \rangle\) and \(\mathrm{uses}(Y) = \langle w_1, \dots, w_p \rangle\) before Algorithm 10.2.6, and let none of the \(u_i\) belong to a constant user. Then afterwards:

(a) \(\mathrm{uses}(X) = \langle\rangle\);
(b) \(\mathrm{val}(u_i) = Y\) for all \(i\), and every other use keeps its value;
(c) \(\mathrm{uses}(Y) = \langle u_m, \dots, u_1, w_1, \dots, w_p \rangle\);
(d) \(\lvert \mathrm{uses}(Y) \rvert = m + p\), and the IR is def-use consistent.

Proof

By induction on the iterations, with the loop invariant "after \(j\) iterations, \(u_1, \dots, u_j\) refer to \(Y\), \(\mathrm{uses}(X) = \langle u_{j+1}, \dots, u_m \rangle\) and \(\mathrm{uses}(Y) = \langle u_j, \dots, u_1, w_1, \dots, w_p \rangle\)". For \(j = 0\) this is the precondition. Iteration \(j + 1\) takes the head \(u_{j+1}\) and calls Set. By Algorithm 10.2.3, \(u_{j+1}\) leaves \(X\)'s list (the rest keep their order) and becomes the head of \(Y\)'s list, which re-establishes the invariant for \(j + 1\). The loop ends when \(X\)'s list is empty, after exactly \(m\) iterations because each one shortens it by one. That gives (a), (b) and (c). (d) follows from (c) and Theorem 10.2.11, since each step is a Set.

Theorem 10.2.13 (RAUW preserves SSA dominance)

Let \(F\) satisfy the SSA dominance property: every non-phi use of \(v\) in instruction \(I\) is dominated by \(v\)'s definition, and every phi use of \(v\) for incoming edge \(P \to B\) is dominated at the end of \(P\). Let \(X\) be an instruction and \(Y\) a value such that \(Y\) is a constant, an argument, or an instruction whose definition dominates the definition of \(X\). Then \(F\) still has the dominance property after RAUW(\(X\), \(Y\)).

Proof

Only the uses \(u_1, \dots, u_m\) changed (Theorem 10.2.12(b)). Take one. If it is a non-phi use in instruction \(I\), then \(X\)'s definition dominates \(I\) (the property before the rewrite), and \(Y\)'s definition dominates \(X\)'s by hypothesis. Dominance is transitive (Ch 15, Theorem 15.1.3), so \(Y\) dominates \(I\). If it is a phi use for edge \(P \to B\), then \(X\) dominates the end of \(P\), hence so does \(Y\). Constants and arguments are available everywhere in \(F\) (they dominate every instruction by convention), which covers the other two cases. All other uses are unchanged.

Corollary 10.2.14 (Simplify-and-replace is safe)

If \(X\) is not a phi and \(Y = \mathrm{simplify}(X)\) is a constant, an argument, or one of \(X\)'s operands (as InstSimplify returns: x + 0 → x, x - x → 0, x & x → x), then RAUW(\(X\), \(Y\)) preserves the dominance property.

Proof

An operand of a non-phi instruction \(X\) is defined before \(X\) and dominates it (the dominance property of \(X\)'s own uses), so Theorem 10.2.13 applies. Constants and arguments are covered by the theorem directly.

When it breaks: RAUW(\(X\), \(Y\)) with \(Y\) defined after \(X\) in the same block, or in a block that does not dominate all of \(X\)'s users, produces "Instruction does not dominate all uses!" (Lesson 10.3's verifier box shows the message). And RAUW with \(\mathrm{type}(Y) \ne \mathrm{type}(X)\) is rejected by an assertion.

Value handles¶

Proposition 10.2.15 (Weak handles never dangle)

If a WeakVH or WeakTrackingVH \(h\) is registered on \(v\) and every deletion of a value runs NotifyDelete (Algorithm 10.2.8) before freeing it, then \(h\) is never a non-null pointer to freed memory.

Proof

\(h\) is non-null only while it points to a value \(v\) in whose handle list it is registered. Registration happens at construction and whenever \(h\) is re-pointed (for tracking handles, by NotifyRAUW). Deleting \(v\) first runs NotifyDelete(v), which nulls \(h\) and unlinks it. So when \(v\)'s memory is freed, \(h\) is already null. A tracking handle that was moved to \(w\) is in \(w\)'s list and is nulled when \(w\) dies.

Metadata as value¶

ValueAsMetadata::handleRAUW(From, To) looks up the unique wrapper of From in the context's ValuesAsMetadata map and re-points it to To. If To already has a wrapper, the old wrapper's metadata uses are redirected to it and the old one is deleted. If a LocalAsMetadata would now wrap a constant, it is replaced by a ConstantAsMetadata. If the replacement would make a local wrapper refer to another function's value (or a constant wrapper refer to a local value), the metadata uses are set to null instead. In the normal case, every metadata operand that referred to From refers to To. This is the metadata analogue of Theorem 10.2.12(b), achieved with one map lookup instead of a use list.

5. Complexity¶

Variables: \(m = \lvert \mathrm{uses}(X) \rvert\), \(h\) = number of handles on a value, \(k\) = number of operands of a user.

Technique	Operation	Time (worst)	Time (typical)	Space
Use lists	`Set`, `addUse`, `removeFromList`	\(O(1)\)	\(O(1)\)	32 bytes per use
Use lists	`getNumUses()`, `hasNUses(N)`	\(O(m)\), \(O(\min(m, N))\)	same	—
Use lists	`hasOneUse()`, `use_empty()`	\(O(1)\)	\(O(1)\)	—
Operand layout	`getOperand(i)`, `getOperandNo()`	\(O(1)\)	\(O(1)\)	co-allocated: 0 extra pointers; hung-off: 1 pointer + capacity slack
Operand layout	`PHINode::addIncoming`	\(O(k)\) on growth	\(O(1)\) amortized (capacity grows geometrically)	—
RAUW	Algorithm 10.2.6	\(O(m + h)\) + re-uniquing constant users	\(O(m)\)	—
Value handles	register / notify	\(O(1)\) / \(O(h)\) + a DenseMap lookup	\(O(1)\)	3 words per handle
Metadata as value	wrap / RAUW redirect	\(O(1)\) expected (hash lookup)	\(O(1)\)	one wrapper per distinct value

Proposition 10.2.16 (Cost of RAUW)

Algorithm 10.2.6 performs exactly \(m\) calls of Set when no user is a constant, so it runs in \(\Theta(m)\) time plus \(O(h)\) for the handles.

Proof

Each iteration removes one use from \(X\)'s list (Theorem 10.2.12's invariant), and Set is \(O(1)\) (two constant-time list operations). The handle notification walks \(X\)'s handle list once.

Pathological input. if (V->getNumUses() == 1) inside a loop over all values costs \(\Theta(\sum_v \lvert \mathrm{uses}(v) \rvert)\) per sweep instead of \(O(1)\) per value. On a function where one value (say a frequently used global pointer) has \(10^5\) uses, a sweep that asks each of its users "does my operand have one use?" is \(\Theta(10^{10})\). Use hasOneUse(), which stops after two elements. Constants are the other trap. RAUW on a value used by a constant expression re-uniques that constant (a hash-table operation per constant user), and before LLVM made ConstantData untracked, the use list of i32 0 in a large module had millions of entries shared across functions. That hurt both speed and thread safety, which is why the lists were removed.

At scale: a Use is 32 bytes. A module with \(10^7\) operand slots spends 320 MB on uses alone, which is why co-allocation (no extra pointer, no extra allocation) matters.

Use lists¶

replaceUsesWithIf(New, Pred), replaceUsesOutsideBlock, User::replaceUsesOfWith: partial RAUW. They iterate with early increment over uses(), because each Set unlinks the current use (the iterator-invalidation drill has this case).
Use-list order preservation (uselistorder in textual IR, -preserve-bc-uselistorder): makes tools deterministic across a round trip, at the cost of extra records.
GCC's immediate uses (gcc/ssa-iterators.h, FOR_EACH_IMM_USE_FAST/FOR_EACH_IMM_USE_STMT): the same idea for SSA names, as a circular list per SSA_NAME.

Operand layout¶

Descriptors: CallBase can co-allocate an extra descriptor area (bundle-operand info) before the operands (IntrusiveOperandsAndDescriptorAllocMarker). This keeps one allocation even for calls with operand bundles.
Fixed vs variadic operand traits (FixedNumOperandTraits, VariadicOperandTraits, HungoffOperandTraits in llvm/IR/OperandTraits.h) choose the layout per class at compile time.

RAUW¶

Aliases instead of use lists (Cranelift): DataFlowGraph::change_to_alias(dest, src) turns dest into an alias of src, and uses are resolved lazily (resolve_aliases). There is no use list to maintain, but every reader must resolve [CL-DFG].
replaceNonMetadataUsesWith: RAUW that leaves metadata pointing to the old value. Used when debug info should keep describing the original.
MLIR Value::replaceAllUsesWith and replaceAllUsesExcept, over the same kind of intrusive use list (mlir/include/mlir/IR/UseDefLists.h).

Value handles¶

PoisoningVH for caches that must not be dereferenced after deletion but may still be compared or erased (ScalarEvolution keeps PoisoningVH<BasicBlock> for exiting blocks).
ValueMap<K, V> (llvm/IR/ValueMap.h): a DenseMap keyed by callback handles, whose entries follow RAUW or are erased on delete according to a config.
AssertingVH in Release builds is a plain pointer (see the real-world box): the protection is a debug-build tool, not a runtime guarantee.

Metadata as value¶

Debug records (LLVM 19+) replaced call void @llvm.dbg.value(metadata …), the heaviest user of MetadataAsValue, with #dbg_value records that refer to values through ValueAsMetadata directly [LLVM-DbgRecords].
DIArgList wraps several ValueAsMetadata for variadic debug locations.

7. In real compilers¶

Use lists¶

LLVM

llvm/include/llvm/IR/Use.h (Use::addToList, Use::removeFromList, Use **Prev), llvm/include/llvm/IR/Value.h (Value::addUse, hasUseList, uses(), users(), Use::set) [LLVM-Use, LLVM-ValueH].

GCC gcc/ssa-iterators.h (gcc-15), immediate-use lists of SSA names.
MLIR mlir/include/mlir/IR/UseDefLists.h (IROperand, IRObjectWithUseList), LLVM 23.1.2.

Find where LLVM does it. In Value.h, find Value::addUse. Question: which values do not get their use added to a list, and which predicate decides it? (Quiz llvm-where-hasuselist.)

Operand layout¶

LLVM

llvm/include/llvm/IR/User.h (User::operator new(size_t, IntrusiveOperandsAllocMarker), HungOffOperandsAllocMarker, getOperandList), llvm/lib/IR/User.cpp (User::growHungoffUses), llvm/include/llvm/IR/OperandTraits.h [LLVM-User].

MLIR Operation stores operands in a trailing array after the object (llvm::TrailingObjects): co-allocation again.

RAUW¶

LLVM

llvm/lib/IR/Value.cpp Value::doRAUW (the loop of Algorithm 10.2.6, handleOperandChange for constants), Value::replaceUsesWithIf [LLVM-Value].

Cranelift cranelift/codegen/src/ir/dfg.rs change_to_alias, resolve_aliases (Wasmtime v37.0.2) [CL-DFG].

Cranelift: aliases instead of use lists

Reproduce (Cranelift source at Wasmtime v37.0.2):

curl -s https://raw.githubusercontent.com/bytecodealliance/wasmtime/v37.0.2/cranelift/codegen/src/ir/dfg.rs \
  | grep -n "pub fn change_to_alias\|pub fn resolve_aliases\|pub fn replace_with_aliases" -B6 \
  | grep "///\|pub fn"

Output (complete):

419-    /// Resolve value aliases.
420-    ///
421-    /// Find the original SSA value that `value` aliases.
422:    pub fn resolve_aliases(&self, value: Value) -> Value {
536-    /// Turn a value into an alias of another.
537-    ///
538-    /// Change the `dest` value to behave as an alias of `src`. This means that all uses of `dest`
539-    /// will behave as if they used that value `src`.
540-    ///
541-    /// The `dest` value can't be attached to an instruction or block.
542:    pub fn change_to_alias(&mut self, dest: Value, src: Value) {
569-    /// corresponding results of `src_inst`, as if calling change_to_alias for
570-    /// each.
571-    ///
572-    /// After calling this instruction, `dest_inst` will have had its results
573-    /// cleared, so it likely needs to be removed from the graph.
574-    ///
575:    pub fn replace_with_aliases(&mut self, dest_inst: Inst, original_inst: Inst) {

What to notice: Cranelift gets the effect of RAUW in \(O(1)\) (one alias edge) with no use lists at all. It pays at every read, because operands must be passed through resolve_aliases, and it cannot answer "who uses this value?" without a full scan. That is the opposite trade-off from Algorithm 10.2.6.

Value handles¶

LLVM

llvm/include/llvm/IR/ValueHandle.h (WeakVH, WeakTrackingVH, AssertingVH, TrackingVH, CallbackVH, PoisoningVH), llvm/lib/IR/Value.cpp ValueHandleBase::ValueIsDeleted and ValueIsRAUWd [LLVM-VH].

LLVM's own users: AssumptionCache (AffectedValueCallbackVH in llvm/include/llvm/Analysis/AssumptionCache.h), ScalarEvolution (SCEVCallbackVH, and PoisoningVH<BasicBlock> in its exit-count cache), GlobalsModRef and PhiValues (callback handles).

Find where LLVM does it. In Value.cpp, read ValueHandleBase::ValueIsRAUWd. Question: which handle kinds does it move to the new value? (Quiz vh-after-rauw.)

Metadata as value¶

LLVM

llvm/include/llvm/IR/Metadata.h (MetadataAsValue, ValueAsMetadata, LocalAsMetadata, ConstantAsMetadata), llvm/lib/IR/Metadata.cpp ValueAsMetadata::handleRAUW [LLVM-Metadata].

Clang attaches TBAA and loop metadata with Instruction::setMetadata. Constrained FP intrinsics emitted under #pragma STDC FENV_ACCESS ON carry MetadataAsValue operands like the box above.

8. Comparison¶

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

Choose use lists (you do not really choose: LLVM keeps them) and walk them with uses() when you need operand numbers and users() when you need the instructions. Choose RAUW over a manual loop of setOperand, because it also updates handles and metadata. Choose a tracking handle when a cache should follow replacements, a weak handle when it should only avoid dangling, and AssertingVH to find bugs in debug builds. Choose Cranelift-style aliases only in your own IR, when RAUW is far more frequent than def-use queries.

9. Assessment¶

Technique	Quiz ids (`solutions/quizzes/ch10.yaml`)	Drill	Flashcard tag	Exercises
Use lists	`uselist-order-trace`, `llvm-where-hasuselist`, `rauw-result-trace`	`./course drill use-lists`	`use-lists`	Lab 10.2 R3
Operand layout	`operand-layout-offset`, `operand-layout-kinds`	`./course drill adt-costs` (sizes); justification below	`operand-layout`	—
RAUW	`rauw-result-trace`, `rauw-dominance`	`./course drill use-lists`	`rauw`	Lab 10.2 R6
Value handles	`vh-after-rauw`, `vh-kinds`	`./course drill use-lists --difficulty hard` (erase + RAUW); the handle table is in the quiz	`value-handles`	—
Metadata as value	`mav-type`, `mav-uniquing`	— (see note)	`metadata-as-value`	—

The operand layout and metadata wrappers have no randomizable computation beyond the offsets in operand-layout-offset, so they are assessed by the quiz and flashcards rather than by a drill.

Pitfall

Do not rely on use-list order, and do not modify a use list while walking it with a plain for (Use &U : V->uses()). U.set(W) moves U into W's list, and the loop wanders off into W's uses (Theorem 10.2.11 explains why: Set rewrites exactly the links the iterator follows). Use make_early_inc_range(V->uses()) or replaceUsesWithIf.

References¶

See the chapter references.

Lesson 10.2 — Values, users, uses: def-use chains and RAUW¶

1. Problem and motivation¶

Use lists¶

Operand layout¶

RAUW¶

Value handles¶

Metadata as value¶

2. Definitions and algorithms¶

Use lists¶

Operand layout¶

RAUW¶

Value handles¶

Metadata as value¶

3. Worked example¶

Use lists¶

Operand layout¶

RAUW¶

Value handles¶

Metadata as value¶

4. Invariants and correctness¶

Use lists¶

Operand layout¶

RAUW¶

Value handles¶

Metadata as value¶

5. Complexity¶

6. Variants and refinements¶

Use lists¶

Operand layout¶

RAUW¶

Value handles¶

Metadata as value¶

7. In real compilers¶

Use lists¶

Operand layout¶

RAUW¶

Value handles¶

Metadata as value¶

8. Comparison¶

9. Assessment¶

References¶