Lesson 23.10 — Machine-level peepholes, code motion and post-link optimization

Techniques: machine peephole optimization and machine CSE (PeepholeOptimizer, MachineCSE); machine code motion (MachineLICM, MachineSink); post-link optimization (BOLT, Propeller) · Prerequisites: Ch 13 (peepholes, value numbering), Ch 17 (CSE, GVN), Ch 18 (LICM), Ch 20 (profiles, BOLT), Lesson 23.9 · Time: 3 hours

Instruction selection, legalization and the SSA passes on machine code leave redundancies that the IR optimizers could not see, because they did not exist at the IR level: the same 64-bit immediate materialized in two blocks, a test that recomputes flags a sub already set, an address computation inside a loop that became invariant after selection, a multiply computed on a path that never uses it. LLVM runs a small set of machine-level cleanups on SSA machine code, before scheduling and allocation. At the other end of the toolchain, post-link optimizers rewrite the final binary using profiles from production. This lesson covers both and closes the chapter where Ch 20 introduced BOLT.

1. Problem and motivation

Machine peephole optimization and machine CSE

The IR-level peephole optimizer (Ch 13) sees icmp eq i64 %d, 0 and sub i64 %a, %b as two instructions. Only on x86 machine code does it become visible that SUB64rr already sets the zero flag, so a following TEST64rr of its result is redundant. PeepholeOptimizer looks for such target-specific patterns through TargetInstrInfo hooks: compare elimination (optimizeCompareInstr), load folding into uses (optimizeLoadInstr), select optimization, and copy rewriting [LLVM-Peephole]. MachineCSE removes machine instructions that recompute a value available from a dominating one, typically constant materializations and address computations duplicated by selection, which works one block at a time [LLVM-MachineCSE].

Machine code motion (MachineLICM and MachineSink)

Selection can also create loop-invariant instructions: a 64-bit immediate that needs a movabs, a constant-pool address, a global address computation. MachineLICM hoists them into the preheader, before register allocation (the "early" instance, with register-pressure checks) and again after it (the post-RA instance, which hoists only when registers are free) [LLVM-MachineLICM]. MachineSink does the opposite for instructions whose results are used on only some paths: it moves them into the successor that needs them, so the other paths do not pay [LLVM-MachineSink]. Both are the machine versions of the LICM and sinking of Ch 18.

Post-link optimization (BOLT, Propeller)

A compiler lays out code one function (or one module, with LTO) at a time, using a profile that may not match production. Post-link optimizers work on the linked binary, with profiles sampled from the real workload (hardware branch records such as Intel LBR). They disassemble, rebuild each function's CFG, map the samples to it, and re-lay out blocks (ext-TSP, Lesson 23.9) and functions (hfsort/C³ [OM17]). They also split hot from cold code. BOLT does all of this by rewriting the binary [PAN+19]. Propeller does it by relinking: it turns the profile into basic-block cluster directives and asks the compiler and linker to regenerate the code with that layout [SPL+23]. Both report several percent speedups on large data-center applications.

2. Definitions and algorithms

Machine peephole optimization and machine CSE

Definition 23.10.1 (Machine peephole rule, available machine expression)

A machine peephole rule replaces a small group of MachineInstrs (usually a def and a use of one virtual register, or an instruction and the flags it defines) by an equivalent cheaper group, subject to a target check. A machine instruction \(I\) is available at a point \(p\) if an instruction \(I'\) with the same opcode and operands (identical, isIdenticalTo) dominates \(p\), and no instruction on any path from \(I'\) to \(p\) redefines a physical register or memory location that \(I\) reads.

Algorithm 23.10.2 (Compare elimination in PeepholeOptimizer)

• Input: a block in SSA machine code.
• Output: the block with redundant compares removed.
• Precondition: the target implements analyzeCompare and optimizeCompareInstr.
• Postcondition: each removed compare's flags are produced by an earlier instruction with the same flag semantics for all users (Proposition 23.10.4).
• Invariant: between the flag producer and the removed compare, nothing clobbers the flags.

for each compare C in the block (e.g. TEST64rr %r, %r; or CMP64ri %r, 0):
    (SrcReg, mask, value) ← analyzeCompare(C)
    D ← the definition of SrcReg, if in the same block
    if D sets the flags the users of C read (e.g. SUB, AND, ADD: ZF/SF for eq/ne/sign tests)
       and no instruction between D and C writes the flags
       and every user of C's flags uses only conditions D computes identically:
        make D define the flags (clear its "dead" flag); delete C

Algorithm 23.10.3 (Dominator-scoped machine CSE)

• Input: a function in SSA machine code; its dominator tree.
• Output: the function with available instructions replaced by earlier definitions.
• Precondition: SSA form (each virtual register defined once).
• Postcondition: every removed instruction's result is available (Definition 23.10.1) from the definition that replaces it.
• Invariant: the scoped hash table holds exactly the side-effect-free instructions of the blocks on the current dominator-tree path, with no clobber since their definition.

function MachineCSE(F):
    Visit(entry)
function Visit(B):
    open a scope
    for I in B:
        if I has side effects, is a copy, or reads memory that may change: continue
        if I clobbers a physical register: invalidate table entries that read it
        if an identical instruction I' is in the table and profitable (not raising pressure too much):
            replace uses of I's result by I'''s result; delete I
        else: insert I
    for each dominator-tree child C of B: Visit(C)
    close the scope

Proposition 23.10.4 (Compare elimination and machine CSE preserve semantics)

Under their preconditions, Algorithms 23.10.2 and 23.10.3 change no value read by any instruction.

Proof

Compare elimination: the users of \(C\)'s flags read, after the change, the flags written by \(D\). Nothing writes the flags in between (the invariant), and \(D\)'s flags agree with \(C\)'s on every condition the users test (the target check: for TEST r, r after SUB producing \(r\), ZF and SF describe \(r\) in both cases). CSE: an identical instruction \(I'\) that dominates \(I\) executes before \(I\) on every path, computes the same function of the same operands (SSA: the operands are the same values), and nothing in between changed a physical register or memory it reads (the invariant maintained by invalidation). So the result of \(I'\) equals the result \(I\) would compute, and replacing the uses is sound.

Machine code motion (MachineLICM and MachineSink)

Definition 23.10.5 (Loop-invariant machine instruction)

In a natural loop \(L\) (Ch 15) with preheader \(P\), a MachineInstr \(I\) is invariant if it has no side effects, is not a load from memory that \(L\) may write (or is an invariant load), and every virtual-register operand is defined outside \(L\) or by an invariant instruction, and it reads no physical register that \(L\) defines.

Algorithm 23.10.6 (Early MachineLICM)

• Input: SSA machine code; the machine loop forest.
• Output: invariant instructions moved to preheaders.
• Precondition: every loop has a preheader (created on demand, which the §7 box shows).
• Postcondition: hoisted instructions compute the same value as in every iteration (Proposition 23.10.8).
• Invariant: an instruction is hoisted only after all its operands' definitions are outside the loop.

for each loop L, innermost first:
    P ← preheader(L)
    for each block B of L in dominator-tree preorder:
        for each I in B:
            if IsInvariant(I, L) and IsSafeToMove(I) and IsProfitable(I, L):
                move I to the end of P (before P's terminator)
IsProfitable: cheap-to-rematerialize constants are hoisted unless register pressure in L
              would exceed the class limit; expensive instructions are hoisted when not
              increasing pressure beyond the limit

Algorithm 23.10.7 (MachineSink)

• Input: SSA machine code; dominators; block frequencies.
• Output: instructions moved down to successors.
• Precondition: the instruction has no side effects and does not read memory written on the way.
• Postcondition: every use is still dominated by the definition (Proposition 23.10.8).
• Invariant: only blocks dominated by the original block and dominating all uses are targets.

for each block B, for each I in B from the bottom up:
    if I is safe to move:
        S ← the successor of B that dominates every use of I's result, if any;
            if the only such target is across a critical edge, split the edge
        if S exists, is not in a deeper loop, and is colder than B (or equally hot): move I to the top of S

Proposition 23.10.8 (Machine code motion preserves semantics)

Hoisting an invariant, safe instruction to the preheader, or sinking a safe instruction to a block that dominates all its uses, changes no value that any instruction reads.

Proof

Hoisting: the preheader dominates the loop, so the hoisted definition dominates all former uses. Its operands are defined outside the loop (or by instructions hoisted before it), so they have the same values at the preheader as in every iteration, and the instruction computes the same value. It has no side effect, so executing it once, even when the loop runs zero times, has no observable effect other than defining a register. Sinking: the target dominates every use, so every use is still reached through the definition. The operands are not redefined between the old and the new position (SSA for virtual registers; the safety check for memory and physical registers). Paths that no longer execute the instruction had no use of its result.

Post-link optimization (BOLT, Propeller)

Definition 23.10.9 (Post-link profile-guided layout)

A post-link optimizer takes a linked binary \(B\) (with relocations or a basic-block address map) and a sampled profile of branch records \((\mathit{from}, \mathit{to}, \mathit{count})\). It reconstructs the CFG of each function, maps each record to an edge (a taken branch) or to a range of fall-throughs, and computes new block orders (Lesson 23.9), hot/cold splits and a function order.

Algorithm 23.10.10 (BOLT's pipeline, simplified)

• Input: a binary linked with --emit-relocs (or without, in a restricted mode); a profile.
• Output: a rewritten binary.
• Precondition: every code address the program can compute is known (relocations, jump tables, landing pads); functions BOLT cannot fully analyze are left in place.
• Postcondition: the new binary computes the same results (Theorem 23.10.11).
• Invariant: each rewritten function's CFG and every reference into it are consistent.

disassemble every function; build its CFG (identify jump tables, landing pads)
attach profile counts to edges and blocks (from LBR or sampled addresses)
run optimization passes: block reordering (ext-TSP), function splitting (hot/cold),
    function reordering (hfsort / C³ / CDSort), peephole and simplifications, ICF, …
emit new code for the optimized functions into a new text section (or in place, when it fits)
patch every reference: relocations, jump tables, exception tables, debug info

Theorem 23.10.11 (Relayout preserves semantics when all references are known)

If every instruction and data reference to code in the rewritten functions is known and patched, and each function's reconstructed CFG is exact, then reordering and splitting its blocks, with branches fixed up, yields a binary that computes the same results.

Proof sketch (full discussion: [PAN+19])

Block reordering is Lesson 23.9's layout change: with every non-fall-through edge given an explicit branch, each execution runs the same instruction sequence up to added or removed unconditional jumps. Splitting is the same with the jump crossing into another section. Moving code changes addresses, so every value that denotes a code address (call targets, jump tables, function pointers, return addresses in unwind tables) must be updated. That is exactly the "all references known" hypothesis, which relocations provide. Functions whose references cannot be established (for example, computed jumps that could not be resolved) are not moved, which keeps the hypothesis true for the rest.

Algorithm 23.10.12 (Propeller: relink with basic-block clusters)

• Input: source code; a profile collected on a binary built with -fbasic-block-address-map.
• Output: a new binary built with -fbasic-block-sections=list=<clusters>.
• Precondition: the profiled binary's address map identifies each machine basic block by a stable ID.
• Postcondition: the compiler and the linker produce the chosen layout; correctness follows from normal compilation (Proposition 23.10.13).
• Invariant: block IDs in the cluster file refer to the same machine blocks in both builds (same source, same flags otherwise).

build 1: compile with -fbasic-block-address-map; link; run and sample branch records
map sampled addresses to (function, block ID) through the .llvm_bb_addr_map section
compute a per-function cluster order (ext-TSP) and a global function/cluster order
write the cluster file:  v1 / "f <function>" / "c <id> <id> ..."  (one "c" line per hot cluster)
build 2: compile with -fbasic-block-sections=list=<file> (listed blocks form hot clusters in
         .text.hot.<fn>, the rest go to .text.split.<fn>); link with a symbol order file

Proposition 23.10.13 (Propeller's layout is correct by construction)

The second build is an ordinary compilation whose only change is the block order and the section placement of blocks, so it is correct whenever the compiler is.

Proof

The cluster file does not change any instruction selection or optimization decision. It only tells BasicBlockSections which blocks to emit together and in which order. The code generator repairs terminators for the new order (Lesson 23.9, §4) and emits cross-section branches with relocations that the linker resolves. No binary rewriting takes place, so no reference can be missed.

3. Worked examples

Machine peephole optimization and machine CSE

The MIR of the §7 box (x86-64, SSA) contains, in the entry block, %4 = SUB64rr %3, %1, implicit-def dead $eflags followed by TEST64rr %4, %4 and a je. Algorithm 23.10.2: analyzeCompare(TEST64rr %4, %4) gives source %4 and a zero test. Its definition SUB64rr sets ZF from the same result, and nothing in between writes EFLAGS. So the TEST64rr goes and the SUB64rr now defines $eflags (no longer dead). In a successor block, %5 = MOV64ri 12345678901 repeats %2 = MOV64ri 12345678901 from the entry block, which dominates it. Algorithm 23.10.3 finds %2 in the scoped table while visiting the successor, replaces %5 by %2 in the IMUL64rr, and deletes the MOV64ri.

Machine code motion (MachineLICM and MachineSink)

In the §7 box's loop, %7 = MOV64ri 12345678901 has no operands at all, so it is invariant and cheap. Early MachineLICM creates a preheader (bb.4, because the loop had none) and hoists it there. In the entry block, %4 = IMUL64rr %2, %2 is used only after the loop, not on the other path out of the entry (the early return). MachineSink splits the critical edge from the entry to the loop, creating bb.4, and moves the multiply there, so the early-return path no longer executes it.

Post-link optimization (BOLT, Propeller)

f in the §7 box has three machine blocks. The address map records block 0 at offset 0 (18 bytes, ending with a call at 8), block 2 (the likely else, the return path) at offset 0x12, and block 1 (the unlikely then) at 0x18. A profile that shows block 1 cold yields the cluster line c 0 2. The relink emits blocks 0 and 2 in .text.hot.f and block 1 as f.cold in .text.split.f, which the linker can place far from the hot code (Algorithm 23.10.12).

4. Invariants and correctness

Machine peephole optimization and machine CSE

Proposition 23.10.4 covers both passes. The fragile parts are the target hooks. Compare elimination must know exactly which flags each opcode defines and which condition codes each user reads. For example, SUB sets the carry flag differently from TEST, so an unsigned jb user blocks the transformation. LLVM's x86 hook checks the users' condition codes.

Identical is not the same as equivalent

MachineCSE only merges identical instructions (same opcode, same operands). Two sequences that compute the same value differently (lea (%rdi,%rdi), %rax vs addq %rdi, %rdi) are not merged, and neither is an instruction that reads memory or a physical register that may have changed. This is why IR-level GVN (Ch 17) does most of the work, and MachineCSE only cleans up what selection duplicated.

Machine code motion (MachineLICM and MachineSink)

Proposition 23.10.8. After register allocation, the post-RA MachineLICM must also check that no physical register it would keep live across the loop is clobbered in the loop. That is why the post-RA instance hoists much less, and why it does not run on SSA code (running -run-pass=machinelicm, the post-RA instance, on SSA MIR crashes llc 23.1.2, as the pass assumes allocated registers).

Post-link optimization (BOLT, Propeller)

Theorem 23.10.11 and Proposition 23.10.13. The practical difference is in the hypotheses: BOLT must prove its CFG and references from the binary, and gives up on functions it cannot analyze. Propeller relies on the compiler, but needs a second compilation, and the block IDs must be stable between the two builds.

5. Complexity

Let \(n\) be the machine instructions, \(b\) the blocks, \(\ell\) the loop nesting depth, and \(s\) the profile samples.

Technique	Time	Notes
PeepholeOptimizer	\(O(n)\) plus the target hooks per candidate	local, one pass per block
MachineCSE (Alg. 23.10.3)	\(O(n)\) expected with hashing, over a dominator-tree walk	invalidation on physical-register clobbers
Early MachineLICM (Alg. 23.10.6)	\(O(n \cdot \ell)\) (each loop level visits its instructions) plus pressure estimates	innermost-first
MachineSink (Alg. 23.10.7)	\(O(n \cdot \text{uses})\) to find a common dominator, plus edge splitting
BOLT	disassembly and CFG \(O(\text{binary size})\); mapping \(O(s)\); layout per function (ext-TSP)	memory grows with the binary; the paper processes binaries of hundreds of MB [PAN+19]
Propeller	profile conversion \(O(s)\); a full second compilation and link	trades BOLT's rewriting for rebuild time [SPL+23]

Justification. Each peephole and CSE step inspects an instruction and a bounded number of neighbors or table entries. LICM visits each instruction once per enclosing loop. The post-link costs are dominated by reading the binary and the profile, and by the layout algorithm of Lesson 23.9.

Pathological family. MachineCSE on a function with \(k\) nested diamonds where every block redefines the same physical register (for example, every block contains a call): each call invalidates the table entries that read a caller-saved physical register, so no CSE across calls happens, whatever the dominance. The "work" is linear, but the pass finds nothing. That is the machine-level form of the pitfall above.

6. Variants and refinements

Machine peephole optimization and machine CSE

• MachineCombiner (MachineCombiner.cpp): reassociates and fuses instruction sequences when MachineTraceMetrics says the critical path shrinks, for example (a + b) + c into a + (b + c) for more ILP, or multiply-add formation. Latency-aware, unlike the peephole pass.
• Target peephole passes (X86FixupLEAs, AArch64LoadStoreOptimizer pairing ldr into ldp, as in Lesson 23.3's boxes).

Machine code motion (MachineLICM and MachineSink)

• Rematerialization during allocation (Ch 22): the inverse trade-off of hoisting cheap constants. The allocator re-creates them near their uses instead of keeping them in a register across the loop.
• Post-RA sinking (PostRAMachineSinking): sink copies after allocation to shrink live ranges in hot blocks.

Post-link optimization (BOLT, Propeller)

• Link-time layout from compiler profiles (symbol ordering files; -fprofile-use with function sections): no rewriting and no relinking of blocks, only functions.
• Hot/cold splitting in the compiler (MachineFunctionSplitter, hot-cold-split): the in-compiler version of splitting, with less accurate profiles.

7. In real compilers

Machine peephole optimization and machine CSE

PeepholeOptimizer::optimizeCmpInstr and isLoadFoldable in llvm/lib/CodeGen/PeepholeOptimizer.cpp call TargetInstrInfo::analyzeCompare and optimizeCompareInstr (x86: X86InstrInfo::optimizeCompareInstr) [LLVM-Peephole]. MachineCSEImpl::PerformCSE and ProcessBlockCSE in llvm/lib/CodeGen/MachineCSE.cpp walk the dominator tree with a ScopedHashTable [LLVM-MachineCSE]. GCC's counterparts are its RTL cse.cc/gcse.cc and the compare-elim.cc pass.

Compare elimination and machine CSE, one pass at a time

Reproduce (llc 23.1.2; -run-pass runs exactly one machine pass on MIR):

cat > ph.mir <<'EOF'
---
name:            f
tracksRegLiveness: true
body:             |
  bb.0:
    successors: %bb.1, %bb.2
    liveins: $rdi, $rsi
    %0:gr64 = COPY $rdi
    %1:gr64 = COPY $rsi
    %2:gr64 = MOV64ri 12345678901
    %3:gr64 = IMUL64rr %0, %2, implicit-def dead $eflags
    %4:gr64 = SUB64rr %3, %1, implicit-def dead $eflags
    TEST64rr %4, %4, implicit-def $eflags
    JCC_1 %bb.2, 4, implicit $eflags
    JMP_1 %bb.1
  bb.1:
    %5:gr64 = MOV64ri 12345678901
    %6:gr64 = IMUL64rr %1, %5, implicit-def dead $eflags
    $rax = COPY %6
    RET 0, $rax
  bb.2:
    $rax = COPY %4
    RET 0, $rax
...
EOF
for p in machine-cse peephole-opt; do echo "== -run-pass=$p"
  llc -mtriple=x86_64-linux-gnu -run-pass=$p ph.mir -o - | sed -n '/^body:/,/^\.\.\./p' \
    | grep -E 'MOV64ri|SUB64rr|TEST64rr|IMUL64rr'
done

Output (complete):

== -run-pass=machine-cse
    %2:gr64 = MOV64ri 12345678901
    %3:gr64 = IMUL64rr %0, %2, implicit-def dead $eflags
    %4:gr64 = SUB64rr %3, %1, implicit-def dead $eflags
    TEST64rr %4, %4, implicit-def $eflags
    %6:gr64 = IMUL64rr %1, %2, implicit-def dead $eflags
== -run-pass=peephole-opt
    %2:gr64 = MOV64ri 12345678901
    %3:gr64 = IMUL64rr %0, %2, implicit-def dead $eflags
    %4:gr64 = SUB64rr %3, %1, implicit-def $eflags
    %5:gr64 = MOV64ri 12345678901
    %6:gr64 = IMUL64rr %1, %5, implicit-def dead $eflags

What to notice: MachineCSE removed %5 (the repeated 64-bit immediate in bb.1, dominated by %2 in bb.0), and the second multiply now reads %2 (Algorithm 23.10.3). The peephole optimizer removed TEST64rr %4, %4, and SUB64rr now defines $eflags instead of marking them dead (Algorithm 23.10.2). In a normal llc run these redundancies are usually already gone, because IR constant hoisting and SelectionDAG's own compare folding handle the single-block cases.

Machine code motion (MachineLICM and MachineSink)

EarlyMachineLICM and MachineLICM (post-RA) are two instances of MachineLICMImpl in llvm/lib/CodeGen/MachineLICM.cpp (HoistRegionPostRA, HoistOutOfLoop, IsProfitableToHoist) [LLVM-MachineLICM]. MachineSinking::SinkInstruction and FindSuccToSinkTo are in llvm/lib/CodeGen/MachineSink.cpp [LLVM-MachineSink].

Hoisting into a new preheader, sinking off a cold path

Reproduce (llc 23.1.2):

cat > cm.mir <<'EOF'
---
name:            g
tracksRegLiveness: true
body:             |
  bb.0:
    successors: %bb.1, %bb.3
    liveins: $rdi, $rsi, $rdx
    %0:gr64 = COPY $rdi
    %1:gr64 = COPY $rsi
    %2:gr64 = COPY $rdx
    %3:gr64 = MOV64ri 0
    %4:gr64 = IMUL64rr %2, %2, implicit-def dead $eflags
    TEST64rr %0, %0, implicit-def $eflags
    JCC_1 %bb.3, 4, implicit $eflags
    JMP_1 %bb.1
  bb.1:
    successors: %bb.1, %bb.2
    %5:gr64 = PHI %3, %bb.0, %8, %bb.1
    %6:gr64 = MOV64ri 12345678901
    %7:gr64 = IMUL64rr %5, %6, implicit-def dead $eflags
    MOV64mr %1, 1, $noreg, 0, $noreg, %7
    %8:gr64 = ADD64ri32 %5, 1, implicit-def dead $eflags
    CMP64rr %8, %0, implicit-def $eflags
    JCC_1 %bb.1, 5, implicit $eflags
    JMP_1 %bb.2
  bb.2:
    $rax = COPY %4
    RET 0, $rax
  bb.3:
    $rax = COPY %3
    RET 0, $rax
...
EOF
for p in early-machinelicm machine-sink; do echo "== -run-pass=$p"
  llc -mtriple=x86_64-linux-gnu -run-pass=$p cm.mir -o - | sed -n '/^body:/,/^\.\.\./p' \
    | grep -E '^  bb\.|MOV64ri|IMUL64rr'
done

Output (complete):

== -run-pass=early-machinelicm
  bb.0:
    %3:gr64 = MOV64ri 0
    %4:gr64 = IMUL64rr %2, %2, implicit-def dead $eflags
  bb.4:
    %7:gr64 = MOV64ri 12345678901
  bb.1:
    %8:gr64 = IMUL64rr %5, %7, implicit-def dead $eflags
  bb.2:
  bb.3:
== -run-pass=machine-sink
  bb.0:
    %3:gr64 = MOV64ri 0
  bb.4:
    %4:gr64 = IMUL64rr %2, %2, implicit-def dead $eflags
  bb.1:
    %7:gr64 = MOV64ri 12345678901
    %8:gr64 = IMUL64rr %5, %7, implicit-def dead $eflags
  bb.2:
  bb.3:

What to notice: the passes renumber virtual registers when they print (%6 became %7). Early MachineLICM created a preheader bb.4 and hoisted the invariant 64-bit constant into it (Algorithm 23.10.6). MachineSink split the edge from bb.0 to the loop, creating its own bb.4, and moved IMUL64rr %2, %2, whose result is used only after the loop, onto that path, so the early return through bb.3 no longer computes it (Algorithm 23.10.7).

Post-link optimization (BOLT, Propeller)

BOLT lives in the LLVM monorepo (bolt/lib/Passes/ReorderAlgorithm.cpp, bolt/lib/Passes/SplitFunctions.cpp, bolt/lib/Rewrite/RewriteInstance.cpp) [LLVM-BOLT]. It is not part of the toolchain in this course's container, so this lesson shows no BOLT output. Propeller's compiler side is in LLVM: -fbasic-block-address-map emits the .llvm_bb_addr_map section (AsmPrinter::emitBBAddrMapSection), and -fbasic-block-sections=list= reads cluster files in llvm/lib/CodeGen/BasicBlockSections.cpp [LLVM-BBSections]. The profile converter is in the separate Propeller repository [SPL+23].

Propeller's two builds: the address map, then a relink with clusters

Reproduce (clang 23.1.2, llvm-readobj 23.1.2):

cat > pl.c <<'EOF'
int work(int);
int f(int x) {
  int s = work(x);
  if (__builtin_expect(x > 100, 0))
    s += work(s);
  else
    s -= 3;
  return s;
}
EOF
clang-23 --target=x86_64-linux-gnu -O2 -fbasic-block-address-map -c pl.c -o pl.o
llvm-readobj --bb-addr-map pl.o | grep -E '^\s+(ID|Offset|Size):'
printf 'v1\nf f\nc 0 2\n' > clusters.txt
clang-23 --target=x86_64-linux-gnu -O2 -fbasic-block-sections=list=clusters.txt -S pl.c -o - \
  | grep -vE '^\s*\.(cfi|p2align|file|ident|addrsig|type|globl|size|prefalign|att_syntax)|^\s*#|^\s*$|note.GNU'

Output (complete):

            ID: 0
            Offset: 0x0
            Size: 0x12
            ID: 2
            Offset: 0x12
            Size: 0x6
            ID: 1
            Offset: 0x18
            Size: 0xF
    .section    .text.hot.f,"ax",@progbits
f:                                      # @f
    pushq   %rbx
    movl    %edi, %ebx
    callq   work@PLT
    movl    $-3, %ecx
    cmpl    $101, %ebx
    jge f.cold
.LBB0_1:
    addl    %eax, %ecx
    movl    %ecx, %eax
    popq    %rbx
    retq
.LBB_END0_1:
    .section    .text.split.f,"ax",@progbits
f.cold:
    movl    %eax, %edi
    movl    %eax, %ebx
    callq   work@PLT
    movl    %eax, %ecx
    movl    %ebx, %eax
    jmp .LBB0_1
.LBB_END0_2:
    .section    .text.hot.f,"ax",@progbits
.Lfunc_end0:

What to notice: the first build records, per machine basic block, a stable ID with its offset and size, which is what a profiler needs to map sampled addresses back to blocks (Algorithm 23.10.12). The cluster file says "blocks 0 and 2 are hot, in that order". The relink emits them in .text.hot.f, and the unlisted block 1 becomes f.cold in .text.split.f, reached by jge f.cold and jumping back to .LBB0_1. This is hot/cold splitting done by the compiler from a post-link profile (Proposition 23.10.13). BOLT reaches the same layout by rewriting the binary instead.

8. Comparison

Technique	Power / precision	Speed (asymptotic · practical)	Output / error quality	Implementation effort	Typical use
Machine peephole optimization and machine CSE	target-specific local rewrites; identical-instruction CSE over dominance (Proposition 23.10.4)	linear	small, reliable wins where selection duplicated work	low per rule; target hooks	every LLVM target, pre-RA; GCC compare-elim, RTL CSE
Machine code motion (MachineLICM and MachineSink)	hoist invariant and sink partially dead MachineInstrs (Proposition 23.10.8)	\(O(n\ell)\)	fewer instructions in loops and on cold paths; pressure-limited	moderate	early (SSA) and post-RA instances in LLVM
Post-link optimization (BOLT, Propeller)	whole-binary layout from production profiles (Theorem 23.10.11, Proposition 23.10.13)	reading the binary and the profile; Propeller: a rebuild	several percent on large data-center binaries [PAN+19, SPL+23]	high (BOLT: a binary rewriter); moderate for Propeller users	Meta (BOLT), Google (Propeller), Linux kernel and large services

Choose the machine peepholes and code motion passes always. They are cheap and on by default. Choose BOLT when you can relink with --emit-relocs but cannot easily rebuild with a new profile, or when you want its other binary-level passes. Choose Propeller when you control the build and want layout decisions to go through the compiler, with no binary rewriting.

9. Assessment

• Quiz: cmp-elim-flags (single), peephole-deleted (number), licm-hoistable (set), sink-target (single), bolt-vs-propeller (multi), propeller-cluster (sequence), find-bbsections (text: BasicBlockSections.cpp). Tags machine-peephole, machine-code-motion, post-link.
• Drills: none of their own: these passes are best learned by running them one at a time on MIR (the §7 boxes are ready-made exercises: change the MIR and predict the output). The layout decisions of post-link tools are practiced with ./course drill code-layout (Lesson 23.9).
• Flashcards: tags machine-peephole, machine-code-motion, post-link.

References

See the chapter references.