Skip to content

Lesson 21.10 — The MC layer: encoding, relaxation, relocations and object files

Techniques: instruction encoding (MCInst and MCCodeEmitter); assembly with fragments, fixups and relaxation; relocations and object formats (ELF, Mach-O, COFF) · Lab: labs/ch21-mir (task 9) · Prerequisites: Lesson 21.9 (the running function f), Ch 0 Lesson 0.6 (linkers, symbols and relocations from the tool user's side) · Time: 3–4 hours

After prologue/epilogue insertion the function is a list of MachineInstrs with physical registers and concrete stack offsets. What remains is to turn it into bytes. LLVM's MC layer ("machine code") does this. The AsmPrinter lowers each MachineInstr to an MCInst, a bare opcode and operand list, and hands it to an MCStreamer. The streamer either prints assembly text or, in the integrated assembler, encodes the instruction with the target's MCCodeEmitter, collects the bytes in fragments, lays the fragments out, relaxes instructions whose short form cannot reach their target, resolves the fixups it can, and turns the rest into relocations in an ELF, Mach-O or COFF object file [LLVM-CodeGenDoc, Section "The MC Layer"]. The standalone assembler llvm-mc is the same code behind a parser. The running example is Lesson 21.9's f(x, y) = g(x) + g(y) + x, a 39-byte function with two calls to an external g.

flowchart LR
  MI[MachineInstr] -->|AsmPrinter| MCI[MCInst]
  MCI -->|MCStreamer| T{text or object?}
  T -->|MCAsmStreamer| S[.s file]
  T -->|MCObjectStreamer| E[MCCodeEmitter<br/>bytes + fixups]
  E --> F[fragments]
  F --> L[layout + relaxation<br/>MCAssembler]
  L --> R[fixups: resolve<br/>or relocate]
  R --> W[ELF / Mach-O / COFF<br/>object writer]

1. Problem and motivation

The input is a sequence of instructions per section (text, data, read-only data, unwind tables) with symbolic operands: labels of basic blocks, names of functions and globals, and expressions over them. The output is an object file: section contents as bytes, a symbol table, and a list of relocations that tell the linker which bytes to patch once final addresses are known. Three problems stand between them.

Instruction encoding (MCInst and MCCodeEmitter)

Every instruction must become the exact byte sequence the processor decodes. On AArch64 that is a fixed 32-bit word with fields at fixed positions. On x86-64 it is a variable-length sequence of prefixes, opcode, ModRM, SIB, displacement and immediate bytes of 1 to 15 bytes, with irregular special cases: (%rsp) needs a SIB byte and (%rbp) needs a zero displacement [Intel-SDM, §2.1–2.2 of Vol. 2]. An operand that refers to a symbol cannot be encoded yet. The encoder writes placeholder bytes and records a fixup saying which bytes to fill in later and how.

Assembly with fragments, fixups and relaxation

Some instructions have several encodings of different lengths. An x86 jmp has a 2-byte form with an 8-bit displacement (eb rel8) and a 5-byte form with a 32-bit one (e9 rel32). The short form is valid only if the target is within −128..127 bytes, but the distance depends on the sizes of the instructions in between, some of which are also undecided. Szymanski called these span-dependent instructions and showed that minimizing program length is easy when their operands are labels and NP-complete when they may be general assembly-time expressions [Szy78].

Relocations and object formats (ELF, Mach-O, COFF)

A call to g, defined in another file, cannot be resolved by the assembler at all. The object file must say: "at offset 0xc of .text, write the 32-bit PC-relative distance to g, adjusted by −4". Each object format encodes this differently. ELF uses explicit addends (.rela sections) [ELF], COFF stores the addend in the patched bytes [PE-COFF], and Mach-O has its own relocation types and conventions [LLVM-MachO]. The relocation types themselves are defined by each processor's ABI [SysV-ABI].

2. Definitions and algorithms

Definition 21.10.1 (MCInst, encoding function, fixup)

An MCInst is a pair \((\mathit{op}, [o_1, \dots, o_k])\) of a target opcode and a list of operands, each a register, an immediate, or a symbolic expression \(e\) (an MCExpr: symbols, constants, +, −). Unlike a MachineInstr it has no basic block, no def/use flags and no implicit operands. An encoding function for a target maps each MCInst to a pair \((b, \Phi)\) of a byte string \(b\) and a set \(\Phi\) of fixups. A fixup \(\phi = (\mathit{off}, \kappa, e)\) says: bytes \(b[\mathit{off} ..]\) are to hold the value of \(e\) in the format of fixup kind \(\kappa\), which fixes the width, whether the value is PC-relative, and how it is placed (for example reloc_branch_4byte_pcrel: 4 little-endian bytes, value minus the address of the end of the field; fixup_aarch64_pcrel_call26: bits 0–25 of the word, value minus the instruction address, divided by 4).

Instruction encoding (MCInst and MCCodeEmitter)

Algorithm 21.10.2 (x86-64 encoding of a register/memory instruction)

  • Input: an MCInst whose opcode has the form "opcode byte(s) /r" with a register operand reg and either a register rm or a memory operand \((\mathit{base}, \mathit{index}, \mathit{scale}, \mathit{disp})\); each register has a 4-bit number \(n\) (rax = 0, …, rdi = 7, r8 = 8, …, r15 = 15).
  • Output: the bytes and at most one fixup (for a symbolic disp).
  • Precondition: no rsp as index; operands of the opcode's widths.
  • Postcondition: the processor decodes the bytes as the MCInst (Proposition 21.10.3).
  • Invariant: each field receives the low 3 bits of a register number; the fourth bit goes to the REX prefix.
function Encode(op, reg, operand):
    rex ← 0100 W R X B, with W = 1 for 64-bit operands, R = bit 3 of n(reg),
          X = bit 3 of n(index) (0 if none), B = bit 3 of n(base or rm)
    emit rex if it is not 0100 0000 (or if a byte register like sil needs it)
    emit the opcode byte(s) of op
    if operand is a register rm:
        emit ModRM(mod = 11, reg = n(reg) mod 8, rm = n(rm) mod 8)
        return
    # memory operand
    if base = rip:        emit ModRM(00, reg, 101); emit disp32 as a fixup; return
    needSIB ← index exists or n(base) mod 8 = 4           # rsp, r12
    mod ← 00 if disp = 0 and n(base) mod 8 ≠ 5             # rbp, r13 need a displacement
          01 if disp fits in 8 bits signed
          10 otherwise (or if disp is symbolic)
    emit ModRM(mod, n(reg) mod 8, rm = 100 if needSIB else n(base) mod 8)
    if needSIB: emit SIB(scale = log2(scale), index = n(index) mod 8 or 100 if none,
                         base = n(base) mod 8)
    emit disp as 0, 1 or 4 bytes according to mod (a fixup if symbolic)

Proposition 21.10.3 (The special cases are forced)

Algorithm 21.10.2's output decodes to its input. In particular (i) a base register with low bits 100 (rsp, r12) always gets a SIB byte, and (ii) a base with low bits 101 (rbp, r13) never uses mod = 00, so (%rbp) is encoded as 0(%rbp) with a 1-byte zero displacement.

Proof

The decoder reads ModRM and, for mod ≠ 11, interprets rm as follows [Intel-SDM, Table 2-2]: rm = 100 means "a SIB byte follows", and mod = 00, rm = 101 means "RIP-relative with a 32-bit displacement" in 64-bit mode (no base register). Every other combination means "base register rm with a displacement of 0, 1 or 4 bytes as mod says". (i) If the base has low bits 100 and the encoder put them in rm, the decoder would expect a SIB byte, so the encoder must emit one, with index = 100 (none) and the base in the SIB's base field. (ii) If the base has low bits 101 and mod = 00, the decoder would read RIP-relative addressing, so the encoder must use mod = 01 with a zero displacement byte. In all remaining cases the decoder's reading is exactly the case the encoder chose. The REX bits extend each 3-bit field to the 4-bit register number, and the special cases depend only on the low 3 bits, which is why r12 and r13 inherit the special cases of rsp and rbp.

Assembly with fragments, fixups and relaxation

Definition 21.10.4 (Fragments and layout)

A section is a sequence of fragments \(F_1, \dots, F_m\). A fragment holds bytes and fixups with a fixed part, and possibly a variable part whose size depends on the layout: a relaxable instruction (a span-dependent instruction), an alignment directive, a variable-length LEB128 value, a DWARF line-table advance. A layout assigns sizes \(s(F_i)\) and offsets \(o(F_1) = 0\), \(o(F_{i+1}) = o(F_i) + s(F_i)\). A label bound at position \(p\) of fragment \(F_i\) has address \(o(F_i) + p\).

Definition 21.10.5 (Span-dependent instructions, consistent assignments, monotonicity)

Let \(J = \{1, \dots, n\}\) index the span-dependent instructions. Instruction \(j\) has a short size \(s_j\) and a long size \(l_j > s_j\), and its short form reaches displacements in an interval \([\,\mathrm{lo}_j, \mathrm{hi}_j\,]\). An assignment is the set \(L \subseteq J\) of instructions that use the long form. It determines a layout and, for each \(j\), the span \(\sigma_j(L)\): the displacement \(j\) must encode (target address minus the address after \(j\)). \(L\) is consistent if every short instruction reaches its target: \(\sigma_j(L) \in [\mathrm{lo}_j, \mathrm{hi}_j]\) for all \(j \notin L\). The problem is monotone if \(L \subseteq L'\) implies \(|\sigma_j(L)| \le |\sigma_j(L')|\) for all \(j\). It is monotone when every span-dependent operand is a label and all other fragments have fixed size: then \(|\sigma_j(L)|\) is a sum of the sizes of the fragments between \(j\) and its target, and each size only grows when an instruction becomes long.

Algorithm 21.10.6 (Start-short relaxation)

  • Input: fragments with span-dependent instructions \(J\).
  • Output: an assignment \(L\) and its layout.
  • Precondition: the problem is monotone (Definition 21.10.5).
  • Postcondition: \(L\) is the least consistent assignment (Theorem 21.10.7).
  • Invariant: \(L \subseteq L^\ast\) for every consistent \(L^\ast\): only instructions that must be long have been made long.
function Relax(section):
    L ← ∅                                   # every instruction starts short
    repeat:
        Layout(section, L)                  # offsets from the current sizes
        N ← { j ∉ L : σ_j(L) ∉ [lo_j, hi_j] }
        L ← L ∪ N
    until N = ∅
    return L

Theorem 21.10.7 (Start-short relaxation is optimal for monotone problems)

For a monotone problem, Algorithm 21.10.6 terminates after at most \(n + 1\) rounds and returns the least consistent assignment \(L_\omega\): \(L_\omega \subseteq L^\ast\) for every consistent \(L^\ast\). Consequently \(L_\omega\) minimizes the section size and every label address.

Proof

Let \(\mathit{Bad}(L) = \{ j : \sigma_j(L) \notin [\mathrm{lo}_j, \mathrm{hi}_j] \}\). Because the short interval contains 0 and spans only grow in absolute value (monotonicity), a \(j\) that is bad for \(L\) stays bad for every \(L' \supseteq L\), so \(\mathit{Bad}\) is monotone. \(L\) is consistent iff \(\mathit{Bad}(L) \subseteq L\). The algorithm computes \(L_0 = \emptyset\), \(L_{k+1} = L_k \cup \mathit{Bad}(L_k)\). Termination: the \(L_k\) grow, and each round that does not stop adds at least one of the \(n\) instructions, so there are at most \(n + 1\) rounds. At the end \(\mathit{Bad}(L_\omega) \subseteq L_\omega\): consistent. Leastness: let \(L^\ast\) be consistent. By induction \(L_k \subseteq L^\ast\): true for \(L_0\), and if \(L_k \subseteq L^\ast\) then \(\mathit{Bad}(L_k) \subseteq \mathit{Bad}(L^\ast) \subseteq L^\ast\), so \(L_{k+1} \subseteq L^\ast\). Minimality: the section size is the fixed size plus \(\sum_{j \in L} l_j + \sum_{j \notin L} s_j\), which grows with \(L\) since \(l_j > s_j\); likewise every label address is a sum of sizes of earlier fragments. So the least assignment gives the least size and the least addresses.

Proposition 21.10.8 (Start-long is not optimal; general expressions are hard)

(a) The dual strategy, starting with every instruction long and shortening any instruction whose short form would fit, can stop at a consistent assignment that is not minimal. (b) If span-dependent operands may be arbitrary assembly-time expressions, deciding whether a program fits in a given length is NP-complete [Szy78]. With alignment padding or expressions such as .space L2 - L1, spans need not be monotone and Theorem 21.10.7 does not apply.

Proof

(a) The mutual.s example of §3: two jumps that each lie inside the other's span. With both short both fit, but with both long, neither fits when shortened alone, so start-long stops with both long, 3 + 3 bytes larger than the least assignment. (b) is Szymanski's theorem; we do not reproduce the reduction. For the non-monotone part: an alignment fragment that pads to a multiple of 16 shrinks by 3 bytes when an instruction before it grows by 3, so a span across it can decrease when \(L\) grows.

Relocations and object formats (ELF, Mach-O, COFF)

Definition 21.10.9 (Relocation)

A relocation is a record \((P, \mathit{type}, S, A)\) attached to a section: the offset \(P\) of the field to patch, a processor-specific type that gives a formula and a field format, a symbol \(S\), and an addend \(A\). The linker evaluates the formula with the final addresses and writes the result into the field. For x86-64 [SysV-ABI, Section "Relocation Types"]: R_X86_64_64 is \(S + A\) (8 bytes), R_X86_64_PC32 is \(S + A - P\) (4 bytes, checked to fit in 32 bits signed), R_X86_64_PLT32 is \(L + A - P\) where \(L\) is the address of \(S\)'s procedure linkage table entry, or of \(S\) itself when \(S\) is defined in the output, and R_X86_64_REX_GOTPCRELX is \(G + \mathit{GOT} + A - P\), the distance to \(S\)'s global offset table slot, with permission for the linker to rewrite the movq into a direct leaq when \(S\) is local to the output. ELF SHT_RELA sections store \(A\) in the record [ELF]. COFF (and ELF SHT_REL) store it in the field itself, and the formula reads it from there [PE-COFF].

Algorithm 21.10.10 (Fixup resolution, after MCAssembler::evaluateFixup)

  • Input: a layout (Algorithm 21.10.6) and each fixup \((\mathit{off}, \kappa, e)\) of a fragment \(F\), with \(e\) of the form \(a - b + c\) (\(a\), \(b\) symbols or absent, \(c\) a constant).
  • Output: for each fixup, either the bytes written into \(F\) or a relocation.
  • Precondition: layout is final (no fragment will change size).
  • Postcondition: after linking, the field holds the value of \(e\) in format \(\kappa\) (Theorem 21.10.11).
  • Invariant: a fixup is resolved in the assembler only if its value cannot change when the linker moves sections or binds symbols.

In LLVM the first adjustment is split in two: X86AsmBackend::evaluateFixup subtracts the field size (4) for every PC-relative fixup, and for a RIP-relative operand followed by an immediate, X86MCCodeEmitter::emitMemModRMByte passes minus the immediate's size to emitImmediate, which adds it to the fixup's expression.

function ResolveFixup(F, off, κ, e = a − b + c):
    P ← o(F) + off                                              # the field's address
    if κ is PC-relative:
        c ← c − (end of the instruction − P)   # the CPU counts from the next instruction
    resolved ← (κ is PC-relative and a is defined in the same section as F
                  and a may not be preempted by another module)
               or (κ is absolute and a, b are both absent or both in one section)
    if resolved:
        v ← c + addr(a) − addr(b)            (absent symbols count as 0)
        if κ is PC-relative: v ← v − P
        write v into F at off in format κ                        # applyFixup
    else:
        choose type from (κ, the specifier of e, the format)     # getRelocType
        if a is local: S ← the section symbol of a's section; A ← c + offset of a in it
        else:          S ← a; A ← c
        emit relocation (P, type, S, A); write 0 (RELA) or A (REL) into the field

Theorem 21.10.11 (Resolution and relocation are equivalent)

For a PC-relative 4-byte fixup at field address \(P\) in an instruction that ends at \(P + 4\) with target symbol \(a\) and constant \(c\): whether the assembler resolves it or the linker applies the relocation \((P, \texttt{R\_X86\_64\_PC32}, a, c - 4)\), the field ends up holding \(\mathrm{addr}(a) + c - (P + 4)\), the displacement the processor adds to the address of the next instruction.

Proof

Resolved: both \(a\) and the field are in one section, so their distance does not depend on where the linker puts the section. Algorithm 21.10.10 first replaces \(c\) by \(c - 4\) and then writes \((c - 4) + \mathrm{addr}(a) - P = \mathrm{addr}(a) + c - (P + 4)\). Relocated: the linker writes \(S + A - P = \mathrm{addr}(a) + (c - 4) - P\), the same value. The −4 in the addend moves the reference point from the start of the field, which is what the ELF formula uses, to the end of the instruction, which is what the processor uses. For a local \(a\) replaced by its section symbol, \(S = \mathrm{addr}(\text{section})\) and \(A\) also includes \(a\)'s offset in the section, so \(S + A\) is again \(\mathrm{addr}(a) + c - 4\). (With an immediate after the field, the end of the instruction is later than \(P + 4\), and the addend subtracts that larger distance: the proof is the same.)

3. Worked example

Instruction encoding (MCInst and MCCodeEmitter)

The 39 bytes of f (the call.o box in §7), decoded with Algorithm 21.10.2:

offset bytes instruction how
0 41 57 pushq %r15 50+r opcode with r = 15 mod 8 = 7: 57; REX.B = 1 for bit 3: 41
2 41 56 pushq %r14 56, REX.B
4 53 pushq %rbx 50 + 3, no REX needed (push is 64-bit by default)
5 48 89 f3 movq %rsi, %rbx REX.W; 89 = MOV r/m64, r64; ModRM 11 110 011: reg = rsi (6), rm = rbx (3)
8 49 89 fe movq %rdi, %r14 REX.W+B; ModRM 11 111 110: reg = rdi (7), rm = r14 mod 8 = 6
b e8 00 00 00 00 callq g e8 + rel32, fixup at offset 1: reloc_branch_4byte_pcrel, value g
10 49 89 c7 movq %rax, %r15 ModRM 11 000 111
13 48 89 df movq %rbx, %rdi ModRM 11 011 111
16 e8 00 00 00 00 callq g second fixup
1b 4c 01 f8 addq %r15, %rax REX.W+R (0100 1100); 01 = ADD r/m64, r64; ModRM 11 111 000: reg = r15 mod 8, rm = rax
1e 4c 01 f0 addq %r14, %rax ModRM 11 110 000
21 5b / 41 5e / 41 5f pops 58+r, REX.B for r14, r15
26 c3 retq

A memory operand: movq 8(%rdi,%rsi,8), %rax is 48 8b 44 f7 08. 8b is MOV r64, r/m64. ModRM 01 000 100 has mod = 01 (8-bit displacement), reg = rax, rm = 100 (SIB follows). SIB 11 110 111 has scale = 8, index = rsi, base = rdi. The last byte is the displacement 8. The AArch64 add x0, x0, x1 is the word 0x8b010000: fixed opcode bits 10001011000 in bits 31–21 and \(R_m\) = 1 in bits 20–16. ldr x0, [x1, #8] stores the offset as 8/8 = 1 in the 12-bit scaled immediate field.

Assembly with fragments, fixups and relaxation

cascade.s: jmp .L1; jmp .L2; .space 123; .L1: .space 10; .L2: ret. The x86 short jump reaches −128..127 from its end.

round layout (\(L\)) \(\sigma_1\) (to .L1) \(\sigma_2\) (to .L2) newly long
1 \(L = \emptyset\): j1 at 0–2, j2 at 2–4, .L1 = 127, .L2 = 137 125 fits 133 does not fit j2
2 \(L = \{2\}\): j2 at 2–7, .L1 = 130, .L2 = 140 128 does not fit long j1
3 \(L = \{1, 2\}\): j1 at 0–5, j2 at 5–10, .L1 = 133, .L2 = 143 long long none: stop

The final code is e9 80 00 00 00 (0x80 = 128) and e9 85 00 00 00 (0x85 = 133, from 10 to 143 = 0x8f), exactly the llvm-mc output in §7. Relaxing j2 pushed .L1 out of j1's reach: a cascade, which is why one pass is not enough.

mutual.s: .La: jmp .Lb; .space 124; jmp .La; .Lb: ret. Start-short: \(\sigma_1 = 124 + 2 = 126\) and \(\sigma_2 = -(2 + 124 + 2) = -128\), both fit: 128 bytes of jumps and padding. Start-long: shortening j1 alone gives \(\sigma_1 = 124 + 5 = 129\), too far. Shortening j2 alone gives \(\sigma_2 = -(5 + 124 + 2) = -131\), too far. So start-long is stuck at 134 bytes (Proposition 21.10.8a), which is what --mc-relax-all (every relaxable instruction long) produces.

Relocations and object formats (ELF, Mach-O, COFF)

The two fixups of f refer to g, which is undefined, so Algorithm 21.10.10 emits relocations:

field \(P\) fixup relocation why
0xc (call at 0xb + 1) reloc_branch_4byte_pcrel, g R_X86_64_PLT32 g − 4 undefined symbol; a call may go through the PLT; −4 from the end of the field
0x17 same same

Suppose the linker places f at 0x1000 and g at 0x2000 in the same executable, so \(L = S\) = 0x2000. The first field at \(P\) = 0x100c gets \(L + A - P\) = 0x2000 − 4 − 0x100c = 0xff0. At run time the processor adds 0xff0 to the address of the next instruction, 0x1010, and lands on 0x2000, as Theorem 21.10.11 promises.

For glob.ll (get() reads an external counter and an internal global local, and @table stores the address of counter):

reference relocation what the linker computes
movq counter@GOTPCREL(%rip), %rax R_X86_64_REX_GOTPCRELX counter − 4 the distance to counter's GOT slot, or a rewrite to leaq if counter ends up local
addq local(%rip), %rax R_X86_64_PC32 .bss − 4 local is a local symbol, so the relocation uses the section symbol .bss, with local's offset (0) in the addend
.quad counter in .data R_X86_64_64 counter + 0 the absolute address

The same f for Mach-O arm64 gets ARM64_RELOC_BRANCH26 _g at each bl (no addend field: the linker writes (target − P)/4 into 26 bits), and for COFF x86-64 IMAGE_REL_AMD64_REL32 g, whose addend is the 0 already in the field and whose formula is relative to the end of the 4-byte field.

Try it

Lab task 9 (labs/ch21-mir/SPEC.md) asks for the relocation type, addend and offset of f's calls, the Mach-O type, and the size of the jump in relax.s.

4. Invariants and correctness

Instruction encoding (MCInst and MCCodeEmitter)

The invariant is round-tripping: disassembling the encoding gives back the MCInst (modulo aliases). LLVM tests every target's encoder this way: thousands of llvm-mc -show-encoding lines in llvm/test/MC/, and the disassembler tests run the other direction. Proposition 21.10.3 is the kind of irregularity those tests catch. A bug here produces an object that links and runs the wrong instruction.

Assembly with fragments, fixups and relaxation

Two invariants: after layout, every short instruction reaches its target (consistency), and the layout is a fixpoint (offsets agree with sizes). LLVM's relaxOnce never shrinks an instruction, so on a monotone section its iteration computes the \(L_k\) of Theorem 21.10.7. Because alignment fragments make the problem non-monotone, it also caps the number of iterations per section at the number of fragments plus one and stops there ("If the layout does not converge after N+1 iterations, bail out") [LLVM-MCAssembler].

Relocations and object formats (ELF, Mach-O, COFF)

Theorem 21.10.11: resolving and relocating give the same value. The subtle part is the resolved-or-not decision. Resolving a reference to a global symbol that another module may preempt (ELF default visibility in a shared library) would bind it too early. That is why isSymbolRefDifferenceFullyResolvedImpl and the target writer's needsRelocateWithSymbol are consulted, and why a reference to a local symbol may use the section symbol while one to a global may not.

5. Complexity

Variables: \(m\) fragments, \(n\) span-dependent instructions, \(r\) fixups.

Technique Time Space Justification
Instruction encoding \(O(1)\) per instruction (≤ 15 bytes on x86) \(O(1)\) table-driven: TSFlags from TableGen select the form
Relaxation (start-short) \(O(n \cdot m)\) worst case: \(\le n + 1\) rounds of an \(O(m)\) layout \(O(m)\) Theorem 21.10.7
Fixup resolution and relocation \(O(r)\) plus symbol-table construction \(O(\#\text{symbols} \log \#\text{symbols})\) \(O(r)\) one evaluation per fixup

A pathological family for relaxation. Chain \(n\) forward jumps so that jump \(k\) jumps over jump \(k + 1\) and fits in rel8 only while jump \(k + 1\) is short, and only the last jump is too far on its own. Each round of Algorithm 21.10.6 relaxes exactly one more jump, from the last to the first: \(n + 1\) rounds of \(O(m)\) work. cascade.s is this chain for \(n = 2\). LLVM's fused relaxOnce sweep sees a size change immediately for the fragments after the relaxed one (a backward jump over it gets the right span in the same sweep), but a forward jump before it, as in cascade.s, is only re-examined in the next sweep, so this family costs LLVM one sweep per link too.

Real-world scale. Each round is a linear sweep, and a third round needs a cascade like §3's, so relaxation is cheap next to the rest of the back end. On AArch64, whose instructions all have 4 bytes, the MC layer has nothing to relax; conditional branches that cannot reach their target are rewritten before the assembler by the MIR-level BranchRelaxation pass (llvm/lib/CodeGen/BranchRelaxation.cpp, -stop-after=branch-relaxation), and calls beyond ±128 MB are left to linker thunks.

6. Variants and refinements

Instruction encoding (MCInst and MCCodeEmitter)

  • Generated encoders. Most targets' getBinaryCodeForInstr is generated by TableGen (-gen-emitter) from the Inst{31-21} = … field assignments in the .td files; x86's irregular format is handwritten in X86MCCodeEmitter but still driven by TableGen TSFlags [LLVM-X86MCEmitter].
  • Instruction padding and alignment (-x86-align-branch, X86AsmBackend::padInstructionViaPrefix): lengthen earlier instructions with redundant prefixes instead of inserting nops, to keep branches from crossing 32-byte boundaries.
  • Compressed encodings (RISC-V C, Thumb-2): the assembler picks the 16-bit form when operands allow, a relaxation in the other direction.

Assembly with fragments, fixups and relaxation

  • Start-long with shrinking (the traditional Unix assembler approach Szymanski analyzed [Szy78]): simpler to implement, but not minimal (Proposition 21.10.8a).
  • Relax everything (--mc-relax-all): no iteration, deterministic sizes, larger code. Useful for debugging layout problems.
  • Single-pass emission with islands and veneers (Cranelift's MachBuffer): emit branches optimistically short, track a "deadline" where the first unresolved short reference goes out of range, and before the deadline emit an island of veneers, longer-range branches that the short branch can reach [CL-MachBuffer]. There is no global fixpoint, which suits a JIT.
  • Fragment representation. LLVM's recent rework gives each fragment a fixed byte part and a variable-size tail holding the span-dependent element (a relaxable instruction, an alignment, a LEB128 value); relaxInstruction rewrites only the tail (setVarContents, setVarFixups) [MR25, LLVM-MCAssembler].
  • Linker relaxation (RISC-V, LoongArch): the assembler keeps long sequences plus R_RISCV_RELAX markers and the linker shrinks them once addresses are final. The assembler must then not resolve differences across relaxable code.

Relocations and object formats (ELF, Mach-O, COFF)

  • REL vs RELA: implicit addends (COFF, Mach-O, 32-bit x86 ELF) save space; explicit addends (x86-64, AArch64 ELF) allow addends too large for the field.
  • Section symbols vs symbol references: relocating against .bss instead of local keeps local symbols out of the symbol table. Mach-O objects marked .subsections_via_symbols prefer symbol-relative relocations, so that the linker can split sections into one atom per symbol and dead-strip them.
  • Linker-optimizable relocations (R_X86_64_REX_GOTPCRELX, AArch64 adrp/ldr GOT pairs): the compiler emits the general sequence and the linker relaxes it when the symbol turns out to be local.

7. In real compilers

Instruction encoding (MCInst and MCCodeEmitter)

X86MCCodeEmitter::encodeInstruction in llvm/lib/Target/X86/MCTargetDesc/X86MCCodeEmitter.cpp emits the prefixes (emitPrefixImpl, emitREXPrefix), the opcode, and emitMemModRMByte/emitRegModRMByte/emitSIBByte, and emitImmediate records a fixup when an operand is an expression. AsmPrinter produces the MCInsts through each target's MCInstLower (LLVM 23.1.2) [LLVM-X86MCEmitter].

MCInsts, encodings and fixups from llvm-mc

Reproduce (llvm-mc 23.1.2):

cat > enc.s <<'X'
addq %r15, %rax
movq 8(%rdi,%rsi,8), %rax
movq (%rsp), %rax
movq (%rbp), %rax
movq (%r13), %rax
callq g
X
llvm-mc -triple=x86_64-linux-gnu -show-encoding enc.s | sed 's/^\t//'
llvm-mc -triple=x86_64-linux-gnu -show-inst enc.s | sed -n '/addq/,/R15>>/p' | sed 's/^\t//'
printf 'add x0, x0, x1\nldr x0, [x1, #8]\nbl g\n' \
  | llvm-mc -triple=aarch64-linux-gnu -show-encoding | sed 's/^\t//'

Output (complete):

addq    %r15, %rax                      # encoding: [0x4c,0x01,0xf8]
movq    8(%rdi,%rsi,8), %rax            # encoding: [0x48,0x8b,0x44,0xf7,0x08]
movq    (%rsp), %rax                    # encoding: [0x48,0x8b,0x04,0x24]
movq    (%rbp), %rax                    # encoding: [0x48,0x8b,0x45,0x00]
movq    (%r13), %rax                    # encoding: [0x49,0x8b,0x45,0x00]
callq   g                               # encoding: [0xe8,A,A,A,A]
                                        #   fixup A - offset: 1, value: g, kind: reloc_branch_4byte_pcrel
addq    %r15, %rax                      # <MCInst #684 ADD64rr
                                        #  <MCOperand Reg:RAX>
                                        #  <MCOperand Reg:RAX>
                                        #  <MCOperand Reg:R15>>
add x0, x0, x1                      // encoding: [0x00,0x00,0x01,0x8b]
ldr x0, [x1, #8]                    // encoding: [0x20,0x04,0x40,0xf9]
bl  g                               // encoding: [A,A,A,0b100101AA]
                                        //   fixup A - offset: 0, value: g, kind: fixup_aarch64_pcrel_call26

What to notice: the §3 decodings, byte for byte. (%rsp) gets the SIB byte 0x24 and (%rbp)/(%r13) the zero displacement 0x00 (Proposition 21.10.3); r13 differs from rbp only in REX.B (0x49 vs 0x48). The MCInst for addq is ADD64rr with the tied destination listed twice, the same opcode as in the MIR of Lesson 21.5. Symbolic operands become A placeholders plus a fixup with its kind; on AArch64 the placeholder is the low 26 bits of the word, and the 100101 of bl is already in place.

Assembly with fragments, fixups and relaxation

MCAssembler::layout in llvm/lib/MC/MCAssembler.cpp calls layoutSection and then repeats relaxOnce until no section changes. relaxOnce is a fused forward sweep that updates each fragment's offset before relaxing it; relaxInstruction asks the backend fixupNeedsRelaxation, and X86AsmBackend::fixupNeedsRelaxationAdvanced answers !isInt<8>(Value) for resolved fixups and "relax" for unresolved ones, after which X86AsmBackend::relaxInstruction turns JMP_1/JCC_1 into JMP_4/JCC_4 (LLVM 23.1.2) [LLVM-MCAssembler, LLVM-X86AsmBackend].

Relaxation at the 127/128 boundary, a cascade, and start-short vs relax-all

Reproduce (llvm-mc and llvm-objdump 23.1.2, in an empty directory):

jmpsize() {  # assemble $1 (extra llvm-mc flags in $2) and show the jumps
  llvm-mc -triple=x86_64-linux-gnu -filetype=obj $2 "$1" -o t.o
  llvm-objdump -d t.o | grep -E 'jmp|ret' | sed 's/^ *//'
}
for n in 127 128; do
  printf 'jmp .Lend\n.space %d, 0x90\n.Lend:\nret\n' $n > gap$n.s
  echo "== gap $n"; jmpsize gap$n.s
done
printf 'jmp .L1\njmp .L2\n.space 123, 0x90\n.L1:\n.space 10, 0x90\n.L2:\nret\n' > cascade.s
echo "== cascade"; jmpsize cascade.s
printf '.La:\njmp .Lb\n.space 124, 0x90\njmp .La\n.Lb:\nret\n' > mutual.s
echo "== mutual"; jmpsize mutual.s
echo "== mutual, --mc-relax-all"; jmpsize mutual.s --mc-relax-all

Output (complete):

== gap 127
0: eb 7f                            jmp 0x81 <.text+0x81>
81: c3                              retq
== gap 128
0: e9 80 00 00 00                   jmp 0x85 <.text+0x85>
85: c3                              retq
== cascade
0: e9 80 00 00 00                   jmp 0x85 <.text+0x85>
5: e9 85 00 00 00                   jmp 0x8f <.text+0x8f>
8f: c3                              retq
== mutual
0: eb 7e                            jmp 0x80 <.text+0x80>
7e: eb 80                           jmp 0x0 <.text>
80: c3                              retq
== mutual, --mc-relax-all
0: e9 81 00 00 00                   jmp 0x86 <.text+0x86>
81: e9 7a ff ff ff                  jmp 0x0 <.text>
86: c3                              retq

What to notice: 127 bytes fit in rel8 (0x7f), 128 do not, and the jump becomes the 5-byte e9 rel32. The cascade is §3's table: the second jump's relaxation pushed .L1 to 128 bytes from the first. In mutual.s the backward jump's 0x80 is −128, the most negative rel8: start-short finds the 129-byte layout, while relax-all (every jump long, the start-long fixpoint here) takes 135 bytes.

Relocations and object formats (ELF, Mach-O, COFF)

ELFObjectWriter::recordRelocation in llvm/lib/MC/ELFObjectWriter.cpp asks the target's getRelocType for the type and useSectionSymbol whether a local symbol can be replaced by its section; ELFWriter::writeObject then writes the header, sections, .rela sections and symbol table. Mach-O and COFF have their own MachObjectWriter and WinCOFFObjectWriter behind the same MCObjectWriter interface (LLVM 23.1.2) [LLVM-ELFWriter].

f as an ELF, Mach-O and COFF object, and a GOT reference

Reproduce (llc and tools 23.1.2; run from the repository root):

C=$PWD/labs/ch21-mir/inputs/call.ll; cd "$(mktemp -d)"
llc -O2 -mtriple=x86_64-linux-gnu -filetype=obj $C -o call.o
llvm-objdump -dr call.o | grep -E 'callq|R_X86'
llvm-readelf -r call.o | sed -n '/rela.text/,/^$/p'
llc -O2 -mtriple=x86_64-linux-gnu $C -o call.s
llvm-mc -triple=x86_64-linux-gnu -filetype=obj call.s -o call2.o
llvm-objdump -d call.o | tail -n +3 > d1.txt; llvm-objdump -d call2.o | tail -n +3 > d2.txt
cmp d1.txt d2.txt && echo "integrated = standalone"
llc -O2 -mtriple=arm64-apple-macos -filetype=obj $C -o call-macho.o
llvm-objdump -dr call-macho.o | grep -wE 'bl|ARM64_RELOC_BRANCH26'
llc -O2 -mtriple=x86_64-pc-windows-msvc -filetype=obj $C -o call-coff.o
llvm-objdump -dr call-coff.o | grep -E 'callq|REL32'
cat > glob.ll <<'X'
@counter = external global i64
@local = internal global i64 0
@table = global ptr @counter
define i64 @get() {
  %a = load i64, ptr @counter
  %b = load i64, ptr @local
  %s = add i64 %a, %b
  ret i64 %s
}
X
llc -O2 -mtriple=x86_64-linux-gnu -filetype=obj glob.ll -o glob.o
llvm-readelf -r glob.o | grep -E 'R_X86_64_(REX|PC32 .*bss|64 )'

Output (complete):

       b: e8 00 00 00 00                callq   0x10 <f+0x10>
        000000000000000c:  R_X86_64_PLT32   g-0x4
      16: e8 00 00 00 00                callq   0x1b <f+0x1b>
        0000000000000017:  R_X86_64_PLT32   g-0x4
Relocation section '.rela.text' at offset 0x128 contains 2 entries:
    Offset             Info             Type               Symbol's Value  Symbol's Name + Addend
000000000000000c  0000000400000004 R_X86_64_PLT32         0000000000000000 g - 4
0000000000000017  0000000400000004 R_X86_64_PLT32         0000000000000000 g - 4

integrated = standalone
      14: 94000000      bl  0x14 <ltmp0+0x14>
        0000000000000014:  ARM64_RELOC_BRANCH26 _g
      20: 94000000      bl  0x20 <ltmp0+0x20>
        0000000000000020:  ARM64_RELOC_BRANCH26 _g
       d: e8 00 00 00 00                callq   0x12 <f+0x12>
        000000000000000e:  IMAGE_REL_AMD64_REL32    g
      18: e8 00 00 00 00                callq   0x1d <f+0x1d>
        0000000000000019:  IMAGE_REL_AMD64_REL32    g
0000000000000003  000000060000002a R_X86_64_REX_GOTPCRELX 0000000000000000 counter - 4
000000000000000d  0000000400000002 R_X86_64_PC32          0000000000000000 .bss - 4
0000000000000000  0000000600000001 R_X86_64_64            0000000000000000 counter + 0

What to notice: §3's relocation table. The relocations point one byte past each e8, at the field, with the −4 addend of Theorem 21.10.11 stored in the ELF record while the field holds zeros. The integrated assembler and llvm-mc on the printed .s produce the same code: both are the same MCObjectStreamer. Mach-O names the symbol _g (a leading underscore) and records no addend. The Windows f has a different prologue (the Microsoft x64 convention: arguments in rcx/rdx, a 32-byte home area) and an implicit-addend REL32. In glob.o, the reference to local uses the section symbol .bss.

8. Comparison

Technique Power / precision Speed (asymptotic · practical) Output / error quality Implementation effort Typical use
Instruction encoding (MCInst and MCCodeEmitter) exact bytes for every instruction form; symbolic operands deferred as fixups \(O(1)\) per instruction · negligible wrong bytes are silent until run; round-trip tests catch them generated from TableGen on regular ISAs; handwritten special cases on x86 every object file; llvm-mc -show-encoding for inspection
Assembly with fragments, fixups and relaxation minimal size for label operands (Theorem 21.10.7); NP-complete in general [Szy78] \(\le n + 1\) layout rounds · usually 1–2 smallest consistent branches; relax-all trades size for simplicity moderate: fragments, fixpoint, per-target relaxation tables integrated assemblers (LLVM MC, GNU as); islands and veneers in JITs
Relocations and object formats (ELF, Mach-O, COFF) any cross-section or cross-module reference the ABI defines \(O(r)\) · negligible link-time errors for out-of-range relocations; wrong types are silent high: three formats, dozens of relocation types per processor every separately compiled program
  • Choose the integrated assembler when compiling: no text round trip, and the same code path as llvm-mc for hand-written assembly.
  • Choose relax-all or single-pass veneers when compile time matters more than a few bytes (JITs, debug builds).
  • Look at relocations when a link fails with "relocation out of range" or a symbol resolves to the wrong definition: llvm-readelf -r / llvm-objdump -r show what the compiler asked the linker to do.

9. Assessment

Technique Quiz ids (solutions/quizzes/ch21.yaml) Drill Flashcard tag Exercises
Instruction encoding (MCInst and MCCodeEmitter) mc-modrm-decode, mc-rbp-disp none: encodings are table lookups; the quiz decodes bytes by hand mc-encoding —
Assembly with fragments, fixups and relaxation relax-cascade, relax-least, llvm-where-relax none: one fixpoint per section; the quiz traces §3's tables relaxation E5 task 9
Relocations and object formats (ELF, Mach-O, COFF) reloc-addend, reloc-link-value none: relocation formulas are fixed per ABI relocations E5 task 9

Forgetting where PC-relative displacements are measured from

The processor adds a PC-relative displacement to the address of the next instruction, the ELF formula subtracts the address of the field (\(P\)), and the difference is the addend. For callq the field is the last 4 bytes, so the addend is −4. For cmpl $1, x(%rip) a 1-byte immediate follows the field, so the addend is −5. Reading g - 4 as "four bytes before g" is the classic misreading.

References

See the chapter references.