Lesson 9.6 — Metadata, debug records, and the two representations of IR¶

Techniques: semantic metadata (TBAA, !range, !noundef, …); loop metadata; debug records; bitcode vs textual IR and the compatibility policy · Pebble uses: !range on loads of bool, loop metadata from for, debug records with -g (Ch 24) · Lab: stretch goal of E2 · Prerequisites: Lesson 9.1, Lesson 9.5 · Time: 3 hours

Compile int f(int *i, float *f) { *i = 1; *f = 2.0f; return *i; } with clang at -O1 and the function returns the constant 1: clang assumed that a store through a float * cannot change an int. The IR contains no C types, so where did that knowledge come from? From metadata: a !tbaa tag on each access naming the C type it uses. Metadata is how a front end tells the optimizer things the instructions cannot say (types for aliasing, value ranges, loop hints, source locations) without changing what the instructions compute. This lesson covers the metadata that matters for optimization, the new debug-record representation, and the second form every module has besides the text you have been reading: bitcode.

1. Problem and motivation¶

An IR needs a channel for information that is optional: facts that help optimization (and may be dropped), hints (unroll this loop), and data for other tools (debug info). Putting such information into instructions would force every pass to preserve it; LLVM instead attaches metadata to instructions, functions and the module, with the rule that a pass may drop metadata it does not understand [LLVM-LangRef, §Metadata; LLVM-DevPolicy]. The same concern, keeping old IR usable, shapes the binary format: LLVM promises that version 23 reads bitcode from every release since 3.0, while the textual format has no compatibility promise at all [LLVM-DevPolicy, §IR Backwards Compatibility].

Semantic metadata: TBAA, range and noundef¶

Type-based alias analysis (TBAA) uses the source language's typing rules: in C, an object of type int may not be accessed through an lvalue of type float (C11 §6.5p7), so the two accesses cannot overlap in a program without UB. LLVM encodes the type hierarchy as metadata trees so that the rule is language-neutral [LLVM-LangRef, §tbaa Metadata]. Value metadata on loads (!range, !nonnull, !noundef, !align, !dereferenceable) carries facts the front end knows (a bool in memory is 0 or 1) to places the optimizer cannot prove them.

Loop metadata¶

Pragmas like #pragma clang loop vectorize(enable) and language rules like C++'s forward-progress guarantee must reach the loop passes. LLVM attaches a node !llvm.loop to the loop's latch branch; loop passes read and update it [LLVM-LangRef, §llvm.loop].

Debug records¶

Debug information maps machine code back to source variables and lines. For fifteen years LLVM represented "variable s now holds value %x" as calls to llvm.dbg.value intrinsics interleaved with real instructions. That design cost compile time and, worse, made passes behave differently with -g whenever they counted or scanned instructions. LLVM 19 moved to debug records, non-instruction annotations attached to instructions and printed as #dbg_value(…) [LLVM-DbgRecords].

Bitcode, textual IR and compatibility¶

Tools exchange modules as bitcode: a dense, bit-level binary encoding designed for fast reading and for backward compatibility (LTO object files, Apple's app bitcode, rustc's crate metadata). The textual .ll form is for humans and tests. The two carry the same module; llvm-as and llvm-dis convert [LLVM-Bitcode].

2. Definitions and algorithms¶

Definition 9.6.1 (Metadata)

Metadata values are: strings (!"int"), constants wrapped as metadata (i64 0), and nodes !{m1, …, mk}, either uniqued (structurally identical nodes are the same node) or distinct. Specialized nodes (!DILocation(…), !DIExpression(…)) have named fields. Metadata is attached to an instruction as !kind !N, to a function or global as !kind !N after its signature, or collected at module level as named metadata (!llvm.module.flags = !{…}). Metadata is not a first-class value: it has type metadata and may appear as an operand only of calls to intrinsics (Lesson 9.2).

Semantic metadata: TBAA, range and noundef¶

Definition 9.6.2 (TBAA type tree and access tags)

A TBAA type descriptor is a node !{!"name", parent, i64 offset} (a scalar type with its parent) or a struct descriptor listing (member type, offset) pairs; a root is !{!"name"}. The scalar descriptors form a tree \(\mathcal{T}\) under "parent". An access tag is !{base, access, i64 off}: the access reads or writes a value of type access at offset off inside an object of type base (for a scalar access, base = access, off = 0). For scalar tags, write \(t \preceq t'\) if \(t'\) is an ancestor-or-self of \(t\) in \(\mathcal{T}\).

Algorithm 9.6.3 (TBAA alias query, scalar tags)

Input: two access tags with access types \(a\), \(b\) in the same tree.
Output: NoAlias or MayAlias.
Precondition: both tags come from the same root (tags from different roots, e.g. different front ends, give MayAlias).
Postcondition: NoAlias only if \(a \not\preceq b\) and \(b \not\preceq a\).
Invariant: while walking up from \(a\), every visited node is an ancestor-or-self of \(a\).

function TbaaAlias(a, b):
    if root(a) ≠ root(b): return MayAlias
    for t in AncestorsOrSelf(a):          # a, parent(a), …, root
        if t = b: return MayAlias          # b is an ancestor of a: a b-access may touch an a-object
    for t in AncestorsOrSelf(b):
        if t = a: return MayAlias
    return NoAlias

function AncestorsOrSelf(t):
    while t ≠ nil: yield t; t ← parent(t)

Definition 9.6.4 (Value metadata on loads)

On %v = load τ, ptr %p: !range !{τ lo1, τ hi1, …} — \(v\) lies in the union of the half-open ranges \([lo_i, hi_i)\), or else \(v\) is poison; !nonnull !{} — \(v \ne\) null, or else poison; !noundef !{} — \(v\) is neither undef nor poison, or else undefined behavior; !align !{i64 A} — \(v\) is \(A\)-aligned, or else poison; !dereferenceable !{i64 n} — \(v\) is dereferenceable for \(n\) bytes, or else UB.

Loop metadata¶

Definition 9.6.5 (Loop metadata)

A loop's properties are a distinct node \(L\) attached as !llvm.loop !L to the terminator of each of its latches, whose first operand is \(L\) itself and whose other operands are property nodes such as !{!"llvm.loop.mustprogress"}, !{!"llvm.loop.unroll.disable"} or !{!"llvm.loop.vectorize.width", i32 4}. Loop transformations read these properties and replace them in the loops they produce (llvm.loop.vectorize.followup_*).

Debug records¶

Definition 9.6.6 (Debug records)

A debug record is one of #dbg_value(value, !var, !expr, !loc), #dbg_declare(ptr, !var, !expr, !loc), #dbg_assign(…) or #dbg_label(!label, !loc), attached before an instruction (or at the end of a block). It states that from this point the source variable !var has the value value transformed by the DWARF expression !expr (for dbg_declare: lives at address ptr). Records are not instructions: they have no result, are not in the instruction list, and are not visited by instruction iteration.

Bitcode, textual IR and compatibility¶

Algorithm 9.6.7 (VBR-n encoding of an unsigned integer)

Input: an integer \(v \ge 0\) and a chunk width \(n \ge 2\) bits.
Output: a bit string of chunks of \(n\) bits.
Precondition: none (any \(v\)).
Postcondition: every chunk carries \(n - 1\) payload bits (least significant first) and a continuation bit, set in all chunks but the last; decoding gives \(v\) back.
Invariant: after emitting \(j\) chunks, the remaining value is \(\lfloor v / 2^{j(n-1)} \rfloor\).

function EmitVBR(v, n):
    threshold ← 2^(n-1)
    while v ≥ threshold:
        emit (v mod threshold) + threshold as n bits   # payload with the continuation bit set
        v ← floor(v / threshold)
    emit v as n bits                                   # last chunk: continuation bit clear

function ReadVBR(n):
    v ← 0; shift ← 0
    repeat
        c ← read n bits
        v ← v + (c mod 2^(n-1)) · 2^shift
        shift ← shift + (n - 1)
    until c < 2^(n-1)
    return v

Signed values are first mapped to \((\lvert v \rvert \ll 1) \mid \mathrm{sign}\). Instruction operands are written relative to the current value number (an operand defined \(k\) values earlier is written as \(k\)), so that most operands are small; forward references (phi operands) use the signed form [LLVM-Bitcode].

3. Worked example¶

TBAA on the introductory function. clang emits the C type tree for int and float (real-world box in "Semantic metadata"):

flowchart BT
  int["!6 int"] --> char["!7 omnipotent char"]
  float["!11 float"] --> char
  char --> root["!8 Simple C/C++ TBAA"]

The store *i = 1 has tag !9 = !{!6, !6, i64 0} (access type int), the store *f = 2.0f has !10 = !{!11, !11, i64 0} (access type float). The load *i after them asks whether the float store may have changed *i. Algorithm 9.6.3:

step	walk	nodes visited	meets the other type?
1	up from `int` (!6)	!6, !7, !8	`float` (!11)? no
2	up from `float` (!11)	!11, !7, !8	`int` (!6)? no
3	—	—	NoAlias

So the load sees the stored 1 and folds. For same_type(int *i, int *j) both tags are !9: step 1 meets int immediately, MayAlias, and the load stays. An access through char * has access type !7, an ancestor of everything: char may alias any type, as C requires.

Value metadata. %v = load i8, ptr %p, !range !{i8 0, i8 5} followed by icmp ult i8 %v, 10: by Definition 9.6.4, \(v \in [0, 5)\) or \(v\) is poison. In the first case the comparison is true; in the second the comparison is poison, which may be refined to true (Lesson 9.7). So the comparison folds to true (box below).

VBR. Encode 30 as vbr4 (Algorithm 9.6.7): threshold \(2^3 = 8\).

step	\(v\)	chunk payload \(v \bmod 8\)	continuation	chunk bits	next \(v\)
1	30	6 (`110`)	1	`1110`	3
2	3	3 (`011`)	0	`0011`	done

Chunks are emitted low first, giving the 8 bits 0011 1110 = 62, exactly the example of the bitcode documentation [LLVM-Bitcode]. Decoding: \(6 + 3 \cdot 2^3 = 30\).

Try it

llvm-as any lab solution and run llvm-bcanalyzer -dump on it: find the INST_BINOP records and check that each operand is written relative to the instruction's own value number.

4. Invariants and correctness¶

Semantic metadata: TBAA, range and noundef¶

Theorem 9.6.8 (Dropping metadata is always correct)

Removing any !tbaa, !range, !nonnull, !noundef, !align, !dereferenceable or loop or debug metadata from a module yields a module whose every behavior is a behavior of the original (a refinement, Definition 9.7.8).

Proof

Case on the kind. Value metadata (Definition 9.6.4): with the metadata, a load whose value violates the fact returns poison or is UB; without it, the load returns the stored value. Where the original returned the value (fact satisfied), both agree; where the original returned poison or had UB, any result of the new program is allowed. TBAA: tags do not change what a load or store does; they only license alias analysis to assume that differently-typed accesses do not overlap, an assumption that holds in every execution without UB (a program with overlapping accesses of unrelated types violates the language's rule, which the front end promises by emitting the tags). Without tags, alias analysis assumes less, which only disables optimizations. Loop metadata is a set of hints and of properties such as mustprogress, whose violation is UB; dropping it removes the property. Debug records have no semantics. In each case the new program's behaviors are among the original's allowed behaviors.

This is the formal content of the compatibility policy's remark that "non-debug metadata is defined to be safe to drop" [LLVM-DevPolicy].

Theorem 9.6.9 (Soundness of Algorithm 9.6.3)

Assume the front end emits tags according to the C/C++ effective-type rule: an access tagged with type \(a\) reads or writes an object whose effective type is \(a\) or a type that may be accessed through \(a\), which in the tree means \(a\) is an ancestor-or-self of the object's type. If two accesses in an execution without UB overlap, then Algorithm 9.6.3 returns MayAlias for their tags.

Proof sketch (full rule: C11 §6.5p7 and [LLVM-LangRef, §tbaa Metadata])

Let the accesses have access types \(a\) and \(b\) and overlap on some byte of an object of effective type \(o\). By the rule, \(a\) and \(b\) are both ancestors-or-self of \(o\). The ancestors of a node in a tree form a chain (the path to the root), so \(a\) and \(b\) are comparable: one is an ancestor-or-self of the other. The first or second loop of Algorithm 9.6.3 then finds it and returns MayAlias. Contrapositive: NoAlias implies the accesses never overlap in an execution without UB. The struct-path extension (base type, offset) refines this by also comparing the paths from the base type to the accessed member; the full rule for it is in the LangRef section cited.

Loop metadata¶

Proposition 9.6.10 (Why the loop node refers to itself)

Two different loops with identical properties get different !llvm.loop nodes, even after uniquing.

Proof

Uniqued nodes with equal operands are identical (Definition 9.6.1), so two loops with nodes !{!"llvm.loop.unroll.disable"} would share one node, and a pass updating one loop's properties would change the other's. The node is therefore distinct and its first operand is itself; a distinct node is never merged with another, and the self-reference also keeps it from being uniqued by the printer and reader when the module is written and read back.

Debug records¶

Proposition 9.6.11 (Debug records cannot change code generation by counting)

For any function \(f\) and any pass whose decisions depend only on the sequence of instructions (their number, order and operands), running the pass on \(f\) with and without debug records gives the same result.

Proof

By Definition 9.6.6, the instruction sequence of \(f\) is the same with and without debug records: records are not instructions and are not visited by instruction iteration. A pass whose decisions are functions of that sequence therefore takes the same decisions. With the old intrinsics (call void @llvm.dbg.value(…)) the premise failed: the calls were instructions, so a size threshold or a "next instruction" scan saw a different sequence under -g unless every pass remembered to skip them. Passes that deliberately inspect records (to update them) are outside the hypothesis.

Bitcode, textual IR and compatibility¶

Theorem 9.6.12 (VBR is decodable, and its size)

For every \(v \ge 0\) and \(n \ge 2\), ReadVBR(n) applied to the output of EmitVBR(v, n) returns \(v\) and reads exactly the emitted bits; the encoding uses \(n \cdot \max(1, \lceil \mathrm{bits}(v)/(n - 1) \rceil)\) bits, where \(\mathrm{bits}(v)\) is the length of \(v\) in binary.

Proof

Decodability: by the invariant of Algorithm 9.6.7, chunk \(j\) (\(j \ge 0\)) carries the payload \(\lfloor v / 2^{j(n-1)} \rfloor \bmod 2^{n-1}\), i.e. bits \(j(n-1) \dots (j+1)(n-1) - 1\) of \(v\); ReadVBR adds payload \(j\) shifted by \(j(n-1)\), reassembling \(v\). All chunks but the last have the continuation bit (value \(\ge 2^{n-1}\)), the last does not, so the reader stops exactly after the last emitted chunk: the code is prefix-free. Size: the loop runs while \(v \ge 2^{n-1}\), i.e. once per additional \(n - 1\) bits beyond the first chunk; the number of chunks is the number of \((n-1)\)-bit groups needed for \(\mathrm{bits}(v)\) bits, at least one.

Proposition 9.6.13 (Relative operand numbering keeps operands small)

If an instruction with value number \(N\) uses a value defined \(k\) values earlier, its operand is written as \(k\) and costs \(n \cdot \lceil \mathrm{bits}(k)/(n-1) \rceil\) bits instead of the cost for \(N - k\); in straight-line code where most operands are defined a few instructions earlier, the cost per operand is independent of the function's size.

Proof

Immediate from the relative encoding (\(\text{operand} = N - \mathrm{id}\)) and Theorem 9.6.12: the cost depends on \(k\), not on \(N\).

5. Complexity¶

Technique	Time (worst)	Time (typical)	Space	Variables
TBAA query (Algorithm 9.6.3)	\(O(h)\)	\(O(1)\)–\(O(h)\), cached	\(O(1)\)	\(h\) = height of the type tree
Range / noundef facts	\(O(r)\) per query	\(O(1)\)	\(O(r)\)	\(r\) = ranges in the node
Debug records	\(O(1)\) per record; no effect on instruction iteration	—	one record object each	—
VBR write/read (Algorithm 9.6.7)	\(O(\mathrm{bits}(v)/(n-1))\)	1 chunk	\(n \lceil \mathrm{bits}(v)/(n-1) \rceil\) bits	\(v\), \(n\)
Reading a module (bitcode)	\(O(\lvert\text{file}\rvert)\), functions lazily	much faster than parsing text	—	—

Proposition 9.6.14 (Cost of Algorithm 9.6.3)

A TBAA query on scalar tags costs \(O(h)\) node visits, where \(h\) is the depth of the deeper of the two access types.

Proof

Each loop walks from a node to the root, visiting at most \(h + 1\) nodes, with an \(O(1)\) comparison per node. LLVM additionally caches results per pair of tags, so repeated queries are \(O(1)\) amortized.

Pathological input. A language with deep type hierarchies (class trees of depth 30) makes \(h\) large, but the real cost at scale is precision, not time: a front end that tags everything with omnipotent char (for example because it lowers memcpy of structs as char accesses) makes every query MayAlias. For bitcode, the pathological input is a function with thousands of phis referring forward: their operands are signed VBRs with large magnitudes, several chunks each.

At scale. The empty function of the bitcode box is 66 bytes of text and 1 920 bytes of bitcode: fixed overhead (identification, symbol and string tables, abbreviation definitions) dominates small modules, while for large modules bitcode is typically several times smaller than text and much faster to read, because functions can be materialized lazily.

Semantic metadata: TBAA, range and noundef¶

Struct-path TBAA (the {base, access, offset} tags, default in clang): distinguishes s.a from s.b when both are int; trade-off: bigger metadata, subtler rules.
!noalias and !alias.scope: C restrict and inlined noalias parameters become scope metadata, giving per-scope no-alias facts (Ch 19).
Rust emits no TBAA (Rust has no type-based aliasing rule) and relies on noalias instead; the metadata mechanism is optional per front end.

Loop metadata¶

llvm.loop.mustprogress (C++ forward progress): lets the optimizer delete a side-effect-free loop that might not terminate; C loops with non-constant conditions get it too (the box).
Follow-up properties (llvm.loop.vectorize.followup_vectorized): transformation pipelines expressed as metadata attached to the loops each transformation produces.

Debug records¶

#dbg_assign (assignment tracking): links debug records to stores so that variable locations survive SROA and dead-store elimination; trade-off: more metadata.
Intrinsic form: LLVM 23 still reads old IR with llvm.dbg.value calls and converts them to records on load (AutoUpgrade, Lesson 9.5).

Bitcode, textual IR and compatibility¶

Abbreviations (per-block record templates with fixed, VBR, array and char6 fields): shrink common records such as INST_BINOP; llvm-bcanalyzer shows which records use them.
ThinLTO summaries and the string table (bitcode version 2): per-module summaries read without loading bodies (Ch 20).
AutoUpgrade: the reader rewrites obsolete constructs (typed pointers, old intrinsic signatures such as the two-operand llvm.lifetime.start, debug intrinsics) into their current form; the text reader applies the same upgrades, but the text format itself carries no compatibility promise.

7. In real compilers¶

Semantic metadata: TBAA, range and noundef¶

LLVM

llvm/lib/Analysis/TypeBasedAliasAnalysis.cpp — TypeBasedAAResult::alias and the helper matchAccessTags (the ancestor walk of Algorithm 9.6.3, extended to struct paths); llvm/lib/Analysis/ValueTracking.cpp — computeKnownBits reads !range; clang/lib/CodeGen/CodeGenTBAA.cpp — CodeGenTBAA::getTypeInfo builds the tree under CodeGenTBAA::getChar ("omnipotent char") and CodeGenTBAA::getRoot (root "Simple C/C++ TBAA" when compiling C, "Simple C++ TBAA" for C++) (LLVM 23.1.2) [LLVM-TBAA].

GCC 15: type-based aliasing uses alias sets computed from tree types (get_alias_set, gcc/alias.cc) rather than metadata, because GCC's middle end still has the front end's types.
rustc: emits !noundef, !range and !nonnull on loads of bool, char, references and enum discriminants (compiler/rustc_codegen_llvm/src/builder.rs, range_metadata, nonnull_metadata), no TBAA.

Find where LLVM does it. In clang/lib/CodeGen/CodeGenTBAA.cpp, find where the root node is created. Question: what is the name of the node under the root from which every scalar C type descends?

TBAA lets clang fold a load; value metadata folds a compare and a freeze

Reproduce (clang 23.1.2, opt 23.1.2):

cat > tbaa.c <<'EOF'
int diff_types(int *i, float *f) { *i = 1; *f = 2.0f; return *i; }
int same_type(int *i, int *j)   { *i = 1; *j = 2;    return *i; }
EOF
clang-23 --target=x86_64-unknown-linux-gnu -O1 -S -emit-llvm tbaa.c -o - \
  | grep -E "^define|  store|  %3 = load|  ret|^!(6|7|8|9|10|11) "
clang-23 --target=x86_64-unknown-linux-gnu -O1 -fno-strict-aliasing -S -emit-llvm tbaa.c -o - | grep -E "  ret"
cat > range.ll <<'EOF'
define i1 @with_range(ptr %p) {
  %v = load i8, ptr %p, align 1, !range !0
  %c = icmp ult i8 %v, 10
  ret i1 %c
}
define i8 @frozen(ptr %p) {
  %v = load i8, ptr %p, align 1, !noundef !1
  %f = freeze i8 %v
  ret i8 %f
}
!0 = !{i8 0, i8 5}
!1 = !{}
EOF
opt -passes=instcombine -S range.ll | grep -E "^define|^  "

Output (complete):

define dso_local noundef i32 @diff_types(ptr nofree noundef writeonly captures(none) initializes((0, 4)) %0, ptr nofree noundef writeonly captures(none) initializes((0, 4)) %1) local_unnamed_addr #0 {
  store i32 1, ptr %0, align 4, !tbaa !9
  store float 2.000000e+00, ptr %1, align 4, !tbaa !10
  ret i32 1
define dso_local i32 @same_type(ptr nofree noundef captures(none) initializes((0, 4)) %0, ptr nofree noundef writeonly captures(none) initializes((0, 4)) %1) local_unnamed_addr #1 {
  store i32 1, ptr %0, align 4, !tbaa !9
  store i32 2, ptr %1, align 4, !tbaa !9
  %3 = load i32, ptr %0, align 4, !tbaa !9
  ret i32 %3
!6 = !{!"int", !7, i64 0}
!7 = !{!"omnipotent char", !8, i64 0}
!8 = !{!"Simple C/C++ TBAA"}
!9 = !{!6, !6, i64 0}
!10 = !{!11, !11, i64 0}
!11 = !{!"float", !7, i64 0}
  ret i32 %3
  ret i32 %3
define i1 @with_range(ptr %p) {
  ret i1 true
define i8 @frozen(ptr %p) {
  %v = load i8, ptr %p, align 1, !noundef !0
  ret i8 %v

What to notice: the tree and the tags of the Section 3 trace; diff_types returns the constant because the float tag and the int tag are unrelated (NoAlias), same_type keeps its load. With -fno-strict-aliasing clang emits no TBAA and both functions reload. !range folded the comparison, and !noundef made the freeze redundant (a value that is never poison needs no freezing, Lesson 9.7).

Loop metadata¶

LLVM

llvm/lib/Analysis/LoopInfo.cpp — Loop::getLoopID (returns the !llvm.loop node found on the latch terminators) and findStringMetadataForLoop; llvm/lib/Transforms/Utils/LoopUtils.cpp — getOptionalBoolLoopAttribute, makeFollowupLoopID (LLVM 23.1.2).

GCC 15: loop pragmas are stored on struct loop fields (safelen, unroll, force_vectorize) in gcc/cfgloop.h, not as metadata.
clang: clang/lib/CodeGen/CGLoopInfo.cpp (LoopInfo::createMetadata) turns #pragma clang loop and C++ forward-progress rules into these nodes.

Find where LLVM does it. In llvm/lib/Analysis/LoopInfo.cpp, find Loop::getLoopID. Question: from which instruction(s) of the loop is the node read, and what happens if two latches carry different nodes?

Loop pragmas become a self-referential distinct node

Reproduce (clang 23.1.2):

cat > loopmd.c <<'EOF'
void scale(float *x, int n) {
#pragma clang loop vectorize(enable) unroll(disable)
  for (int i = 0; i < n; i++) x[i] *= 2.0f;
}
EOF
clang-23 --target=x86_64-unknown-linux-gnu -O0 -S -emit-llvm loopmd.c -o - \
  | grep -E "llvm.loop|^![0-9]+ = distinct"

Output (complete):

  br label %6, !llvm.loop !5
!5 = distinct !{!5, !6, !7, !8}
!6 = !{!"llvm.loop.mustprogress"}
!7 = !{!"llvm.loop.unroll.disable"}
!8 = !{!"llvm.loop.vectorize.enable", i1 true}

What to notice: Definition 9.6.5 exactly: the node is distinct, its first operand is itself (Proposition 9.6.10), and it hangs on the latch's br. mustprogress was added although the source did not ask for it: C11 lets the compiler assume that such a loop terminates.

Debug records¶

LLVM

llvm/include/llvm/IR/DebugProgramInstruction.h — DbgRecord, DbgVariableRecord and DbgMarker (the per-instruction attachment point); llvm/include/llvm/IR/Instruction.h — Instruction::getDbgRecordRange; llvm/lib/IR/AutoUpgrade.cpp converts llvm.dbg.* calls in old IR (LLVM 23.1.2) [LLVM-DbgRecords].

GCC 15: GIMPLE_DEBUG statements (# DEBUG s => s_5), i.e. the design LLVM left: they are statements, and GCC maintains a -fcompare-debug mode to catch passes that behave differently with them.
rustc emits debug records through LLVM's DIBuilder (compiler/rustc_codegen_llvm/src/debuginfo/).

Find where LLVM does it. In llvm/include/llvm/IR/Instruction.h, find getDbgRecordRange. Question: why does a pass that only iterates over instructions(F) never see a #dbg_value?

Debug records in the running example at -O1 -g

Reproduce (clang 23.1.2):

cat > sum_pos.c <<'EOF'
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;
}
EOF
clang-23 --target=x86_64-unknown-linux-gnu -O1 -g -fno-discard-value-names -S -emit-llvm sum_pos.c -o - \
  | sed -n '/^for.body:/,/^}/p'

Output (complete):

for.body:                                         ; preds = %entry, %for.body
  %i.010 = phi i64 [ %inc, %for.body ], [ 0, %entry ]
  %s.09 = phi i64 [ %spec.select, %for.body ], [ 0, %entry ]
    #dbg_value(i64 %i.010, !24, !DIExpression(), !27)
    #dbg_value(i64 %s.09, !23, !DIExpression(), !26)
  %arrayidx = getelementptr inbounds nuw [8 x i8], ptr %a, i64 %i.010, !dbg !32
  %0 = load i64, ptr %arrayidx, align 8, !dbg !32, !tbaa !34
  %add = tail call i64 @llvm.smax.i64(i64 %0, i64 0), !dbg !36
  %spec.select = add nuw nsw i64 %add, %s.09, !dbg !36
    #dbg_value(i64 %spec.select, !23, !DIExpression(), !26)
  %inc = add nuw nsw i64 %i.010, 1, !dbg !37
    #dbg_value(i64 %inc, !24, !DIExpression(), !27)
  %exitcond.not = icmp eq i64 %inc, %n, !dbg !38
  br i1 %exitcond.not, label %for.cond.cleanup, label %for.body, !dbg !39, !llvm.loop !40
}

What to notice: the source variables s (!23) and i (!24) are tracked through the SSA values that hold them, one #dbg_value record after each definition; the records are indented differently because they are not instructions (Definition 9.6.6), and the instructions themselves are exactly those of the -O1 output without -g (Proposition 9.6.11). Every instruction also carries a !dbg location.

Bitcode, textual IR and compatibility¶

LLVM

llvm/lib/Bitcode/Writer/BitcodeWriter.cpp — ModuleBitcodeWriter::writeInstruction (relative operand IDs via pushValueAndType); llvm/include/llvm/Bitstream/BitstreamWriter.h — EmitVBR, EmitVBR64 (Algorithm 9.6.7); llvm/lib/Bitcode/Reader/BitcodeReader.cpp reads everything back to 3.0, calling into llvm/lib/IR/AutoUpgrade.cpp; the compatibility tests are llvm/test/Bitcode/compatibility-*.ll (LLVM 23.1.2) [LLVM-Bitcode, LLVM-DevPolicy].

GCC 15: LTO streams GIMPLE in its own format (gcc/lto-streamer-out.cc) with no cross-version compatibility: object files must be produced by the same GCC version.
rustc stores LLVM bitcode in .rlib files for cross-crate LTO and checks the LLVM version at use.

Find where LLVM does it. In llvm/include/llvm/Bitstream/BitstreamWriter.h, find EmitVBR. Question: what does the loop condition compare the value with?

Inside a bitcode file

Reproduce (llvm-as, llvm-bcanalyzer 23.1.2):

printf 'define i64 @inc(i64 %%x) {\n  %%y = add nsw i64 %%x, 1\n  ret i64 %%y\n}\n' > inc.ll
llvm-as inc.ll -o inc.bc
wc -c inc.ll inc.bc
od -A d -t x1 inc.bc | head -1
llvm-bcanalyzer -dump inc.bc | grep -A12 "<FUNCTION_BLOCK"

Output (complete):

  66 inc.ll
1920 inc.bc
1986 total
0000000 42 43 c0 de 35 14 00 00 05 00 00 00 62 0c 30 24
  <FUNCTION_BLOCK NumWords=10 BlockCodeSize=5>
    <DECLAREBLOCKS op0=1/>
    <CONSTANTS_BLOCK NumWords=1 BlockCodeSize=4>
      <SETTYPE abbrevid=4 op0=1/>
      <INTEGER abbrevid=5 op0=2/>
    </CONSTANTS_BLOCK>
    <INST_BINOP abbrevid=9 op0=2 op1=1 op2=0 op3=2/>
    <INST_RET abbrevid=13 op0=1/>
    <VALUE_SYMTAB NumWords=2 BlockCodeSize=4>
      <ENTRY abbrevid=6 op0=1 op1=120/> record string = 'x'
      <ENTRY abbrevid=6 op0=3 op1=121/> record string = 'y'
    </VALUE_SYMTAB>
  </FUNCTION_BLOCK>

What to notice: the file starts with the magic BC 0xC0DE. The constant 1 is stored as the signed VBR 2 (\(1 \ll 1\), sign bit 0). In INST_BINOP, op0=2 is %x written relative to the instruction (Proposition 9.6.13), op1=1 the constant, op2=0 the opcode (add) and op3=2 the flags (nsw is bit 1); INST_RET op0=1 returns the value defined one step earlier. A tiny module is mostly fixed overhead: 1 920 bytes against 66 of text.

LLVM 23 reads bitcode from LLVM 3.6 and upgrades old IR

Reproduce (llvm-dis 23.1.2, opt 23.1.2; needs network access to GitHub for the first command):

curl -sLo c36.bc https://raw.githubusercontent.com/llvm/llvm-project/llvmorg-23.1.2/llvm/test/Bitcode/compatibility-3.6.ll.bc
llvm-dis c36.bc -o - | grep -E "^target|^%pri.func.data"
cat > up.ll <<'EOF'
declare void @llvm.lifetime.start.p0(i64, ptr)
declare void @use(ptr)
define void @f() {
  %a = alloca [16 x i8]
  call void @llvm.lifetime.start.p0(i64 16, ptr %a)
  call void @use(ptr %a)
  ret void
}
EOF
opt -S up.ll | grep lifetime

Output (complete):

target datalayout = "E"
target triple = "x86_64-apple-macosx10.10.0"
%pri.func.data = type { i32, ptr, ptr }
  call void @llvm.lifetime.start.p0(ptr %a)
declare void @llvm.lifetime.start.p0(ptr captures(none)) #0

What to notice: a file written by LLVM 3.6 in 2015, when this struct was spelled with typed pointers, is read and printed with opaque ptrs: bitcode compatibility in action. The text file uses the old two-operand llvm.lifetime.start; the reader upgrades call and declaration to the current one-operand form. The same upgrade code serves both formats, but only bitcode has a promise behind it.

8. Comparison¶

Technique	Power / precision	Speed (asymptotic · practical)	Output / error quality	Implementation effort	Typical use
Semantic metadata: TBAA, range and noundef	TBAA: type-based no-alias under the language's rule; value facts on loads	\(O(h)\) per TBAA query, cached	wrong metadata = miscompile, silently	front end must build the tree	C/C++ strict aliasing; `bool`/enum ranges
Loop metadata	per-loop hints and properties, preserved through transformations	\(O(1)\) lookup	pragmas visible in the IR	small	`#pragma clang loop`, `mustprogress`
Debug records	source-variable locations without instructions	no effect on instruction iteration	`#dbg_value` in text	large migration, now done	`-g` builds
Bitcode, textual IR and compatibility	same module in two encodings; bitcode read back to 3.0	bitcode: fast, lazy reading; text: slow, readable	`llvm-bcanalyzer` for bitcode, the text for humans	writer/reader + AutoUpgrade	LTO, caches, archives (bitcode); tests, debugging (text)

Choose metadata for anything the optimizer may use but need not preserve; choose attributes (Lesson 9.5) when the fact belongs to a function or parameter; choose an instruction or intrinsic when the information changes semantics. Store bitcode whenever a later LLVM version must read the file; never ship .ll files as a stable interface.

9. Assessment¶

Technique	Quiz ids (`solutions/quizzes/ch09.yaml`)	Drill	Flashcard tag	Exercises
Semantic metadata: TBAA, range and noundef	`tbaa-noalias`, `range-fold`, `find-tbaa-root`	— (see below)	`metadata`	E2 ★ (`!range`)
Loop metadata	`loop-md-distinct`, `loop-mustprogress`	—	`metadata`	—
Debug records	`debug-records-not-instructions`, `debug-record-values`	—	`debug-records`	—
Bitcode, textual IR and compatibility	`vbr-encode`, `compat-policy`	—	`bitcode`	—

These techniques are about representation; their computational content (a VBR encoding, a TBAA walk) is small enough that the quiz covers it with worked instances (vbr-encode, tbaa-noalias), and there is no randomized drill.

Metadata is not a comment

A wrong !range, !nonnull or !noundef does not merely lose information: it makes loads poison or undefined, and the optimizer folds code on that basis. Only attach metadata you can guarantee; when in doubt, leave it out (Theorem 9.6.8 says that is always correct).

References¶

See the chapter references.

Lesson 9.6 — Metadata, debug records, and the two representations of IR¶

1. Problem and motivation¶

Semantic metadata: TBAA, range and noundef¶

Loop metadata¶

Debug records¶

Bitcode, textual IR and compatibility¶

2. Definitions and algorithms¶

Semantic metadata: TBAA, range and noundef¶

Loop metadata¶

Debug records¶

Bitcode, textual IR and compatibility¶

3. Worked example¶

4. Invariants and correctness¶

Semantic metadata: TBAA, range and noundef¶

Loop metadata¶

Debug records¶

Bitcode, textual IR and compatibility¶

5. Complexity¶

6. Variants and refinements¶

Semantic metadata: TBAA, range and noundef¶

Loop metadata¶

Debug records¶

Bitcode, textual IR and compatibility¶

7. In real compilers¶

Semantic metadata: TBAA, range and noundef¶

Loop metadata¶

Debug records¶

Bitcode, textual IR and compatibility¶

8. Comparison¶

9. Assessment¶

References¶