Lesson 20.10 — Profile-guided optimization: instrumentation, sampling and post-link layout

Techniques: instrumentation PGO — counters on a spanning-tree complement, a training run, and counts attached to the IR as branch_weights, entry counts and value profiles (Knuth & Stevenson 1973; Ball & Larus 1994; LLVM IR PGO and context-sensitive CSPGO, GCC -fprofile-generate/-fprofile-use); sampling PGO — hardware samples mapped back to source lines through debug information (Chen, Li & Moseley 2016, AutoFDO; LLVM -fprofile-sample-use, GCC -fauto-profile); post-link optimization — rewrite the linked binary's code layout from a profile (Pettis & Hansen 1990; Panchenko et al. 2019, BOLT; Shen et al. 2023, Propeller) · Pebble implements: the profile=FILE mode of pebble-inline (hot and cold call sites, E2); the comparison lab measures it against the static modes · Prerequisites: counter placement on a spanning tree (Ch 12, Lesson 12.3); Lesson 20.3 (hot/cold thresholds) and Lesson 20.7 (indirect-call promotion); block layout inside a function is Ch 23's topic · Time: 4–6 hours

Every heuristic of this chapter guesses where a program spends its time: the inliner assumes that a call in a loop is worth more, function specialization assumes that a constant argument is common, the outliner assumes that a block guarded by an error test is cold. A profile replaces the guesses by measurements from a training run. This lesson covers how profiles are collected (counters or samples), how they are attached to the IR and survive interprocedural transformations (the hard part: inlining changes the program the profile was measured on), and how the final binary's layout is optimized after linking. The running example is the indirect-call loop of Lesson 20.7's box, now measured:

typedef long (*op_t)(long);
__attribute__((noinline)) long inc(long x) { return x + 1; }
__attribute__((noinline)) long dbl(long x) { return 2 * x; }
long apply(op_t f, long x) { return f(x); }
int main(int argc, char **argv) {
  op_t ops[2] = {inc, dbl};
  long s = 0;
  for (long i = 0; i < 1000000; i++)
    s = apply(ops[(i % 1000) == 999], s) % 1000003;   /* inc 99.9% of the time */
  printf("%ld\n", s);
  return 0;
}

1. Problem and motivation

Instrumentation PGO

Static frequency estimates (loop depth, branch heuristics) are often wrong by orders of magnitude, and interprocedural decisions multiply their errors: an inliner that believes a cold call is hot spends code size where it buys nothing. Instrumentation-based PGO compiles the program with counters, runs it on representative inputs, and recompiles with the counts. Counting every edge is wasteful; counting only the edges outside a spanning tree of the CFG suffices, because flow conservation determines the rest (Knuth & Stevenson [KS73]; Ball & Larus [BL94]; Lesson 12.3 builds this pass). LLVM's IR PGO instruments after a light pre-inliner, records indirect-call targets as value profiles, and on the use side attaches !prof metadata: function_entry_count, branch_weights, and VP records that indirect-call promotion reads [LLVM-PGO]. Context-sensitive PGO (CSPGO) adds a second instrumentation after inlining, because counts measured before inlining cannot say how a callee behaves at one particular call site (Theorem 20.10.4).

Sampling PGO (AutoFDO)

Instrumented binaries run slower — every non-tree edge updates a counter — and must be built and run separately from production. Sampling PGO instead profiles the optimized production binary with a hardware sampler (Linux perf, last-branch records), maps each sampled address back to a source line through debug information, and feeds the per-line counts to the next compilation [CLM16]. Precision is lower — samples are statistical and line information is lossy after optimization — but the profile comes from the real workload at negligible cost; Google introduced AutoFDO to run it continuously over its fleet [CLM16].

Post-link optimization (BOLT, Propeller)

Even with a profile, the compiler lays out code before it knows the final binary: function order is decided by the linker, and much of the code comes from libraries and other translation units. Post-link optimizers start from the linked binary and a sampled profile of it and reorder basic blocks and functions for instruction-cache and TLB locality — hot code together, cold code split away. Pettis and Hansen's profile-guided code positioning is the origin of both function ordering (by a weighted call graph, Algorithm 20.10.6) and block splitting [PH90]. BOLT rewrites the binary itself from a disassembled CFG [PAN+19]; Propeller moves the work back into the compiler and linker: the compiler emits each basic block in its own section, and a relink orders the sections from the profile [SPL+23].

2. Definitions and algorithms

Definition 20.10.1 (Edge profile, flow conservation)

For a function with CFG \((V, E)\), entry \(s\) and exit \(t\), add a virtual edge \(t \to s\). An edge profile is a map \(c : E \to \mathbb{N}\) counting how often each edge was taken in the training run. It satisfies flow conservation: for every block \(b\), \(\sum_{(a,b) \in E} c(a,b) = \sum_{(b,d) \in E} c(b,d)\); the count of \(b\) is either side, and \(c(t \to s)\) is the number of calls of the function (its entry count). A value profile of an indirect call site \(k\) is a map from call targets to counts whose sum is the count of \(k\)'s block.

Definition 20.10.2 (Context-insensitive and context-sensitive profiles)

A profile is context-insensitive if it has one count vector per function, summed over all call sites. A context-sensitive profile keys the counts of a function by its calling context (a call-site string, as in Lesson 20.5): a function \(g\) inlined at call site \(k\) of \(f\) gets its own counts \(c_k\). CSPGO obtains them by instrumenting after inlining, so each inlined copy has its own counters; sampling PGO obtains them from the inline stacks recorded in the debug information of the profiled binary.

Definition 20.10.3 (Sample profile, block weight)

A sample profile of function \(f\) maps each source location \((\ell - \ell_f, d)\) — the line offset from \(f\)'s first line and a discriminator \(d\) that separates basic blocks on one line — to a sample count, plus \(f\)'s total and entry ("head") samples, plus a nested sample profile per inlined call site. The weight of a basic block \(B\) is \(w(B) = \max_{i \in B} \mathrm{samples}(\mathrm{loc}(i))\) over the instructions with a location (LLVM: SampleProfileLoaderBaseImpl::getBlockWeight); line offsets instead of absolute lines keep the profile valid when code above \(f\) moves.

Theorem 20.10.4 (Scaling a context-insensitive profile at inlining)

Let \(g\) have a context-insensitive edge profile \(c_g\) with entry count \(N_g > 0\), and let \(g\) be inlined at call site \(k\) executed \(n_k\) times. The inliner gives each edge \(e\) of the inlined copy the count \(\hat{c}_k(e) = c_g(e) \cdot n_k / N_g\). (a) The sum of the scaled counts over all inlined copies (one per call site, \(\sum_k n_k = N_g\)) is exactly \(c_g(e)\), and each \(\hat{c}_k\) satisfies flow conservation. (b) \(\hat{c}_k\) equals the true count \(c_k\) of the copy for every \(k\) and \(e\) iff the fraction \(c_k(e) / n_k\) is the same at every call site; otherwise the error \(\lvert \hat{c}_k(e) - c_k(e) \rvert\) can come arbitrarily close to \(n_k\).

Proof

(a) \(\sum_k \hat{c}_k(e) = c_g(e) \sum_k n_k / N_g = c_g(e)\). Scaling by the constant \(n_k / N_g\) preserves every conservation equation, and the entry count of the copy becomes \(N_g \cdot n_k / N_g = n_k\). (b) If \(c_k(e) / n_k = q_e\) for all \(k\), then \(c_g(e) = \sum_k c_k(e) = q_e N_g\), so \(\hat{c}_k(e) = q_e n_k = c_k(e)\). Conversely, if the fractions differ, some \(k\) has \(c_k(e)/n_k \neq c_g(e)/N_g\), i.e. \(\hat{c}_k(e) \neq c_k(e)\). For the bound, let $g(p) = $ if (p) A else B be called \(n\) times with p = 1 from site \(k_1\) and \(m\) times with p = 0 from site \(k_2\). Then \(c_g(\to B) = m\) and \(N_g = n + m\), so \(\hat{c}_{k_1}(\to B) = m n / (n + m)\) while \(c_{k_1}(\to B) = 0\); as \(m / n \to \infty\) the error tends to \(n = n_{k_1}\).

Theorem 20.10.4 is why PGO pipelines inline before instrumenting (LLVM's pre-inliner) and why CSPGO exists: after the pre-inliner, apply of the running example is part of main, and its indirect call site is counted per context.

Algorithm 20.10.5 (Profile-guided interprocedural decisions)

• Input: a module annotated with entry counts, branch_weights and value profiles; the program's profile summary (the count above which a block is hot: the smallest count such that blocks at least that hot cover 99% of all counts, and a cold count at or below which blocks together make up only the last 0.0001%; LLVM: -profile-summary-cutoff-hot=990000, -profile-summary-cutoff-cold=999999, in millionths).
• Output: the decisions of this chapter's passes, driven by counts instead of guesses.
• Precondition: the profile matches the IR it annotates (per-function CFG checksums agree); records that do not match were dropped when the profile was read.
• Postcondition: every transformation applied satisfies the static legality conditions of its own lesson (Theorem 20.10.7); only the choice among legal transformations depends on the counts.
• Invariant: every decision changes only cost. A wrong or stale profile can make the program slower, never wrong.

function ProfileGuidedIPO(M, profile):
    (hot, cold) ← thresholds from the profile summary
    for each indirect call c with value profile {(t_i, n_i)}, total n, in decreasing n_i:     # Lesson 20.7
        while n_i passes the promotion thresholds and fewer than MaxProm promoted:
            SpeculativeCall(c, t_i) with branch weights (n_i, n − n_i); n ← n − n_i
    for each call site c in bottom-up order:                                                # Lesson 20.3
        T ← 3000 if count(c) ≥ hot; min(T, 45) and no bonuses if count(c) ≤ cold; else T
        if cost(c) < T: inline c; scale the callee's counts by count(c) / entry(callee)    # Theorem 20.10.4
    split or specialize using the hot/cold classes of blocks and call sites                 # Lesson 20.4
    ThinLTO import threshold × {hot: 10, critical: 100, cold: 0}                            # Lesson 20.9
    order functions by call counts (Algorithm 20.10.6); order and split blocks by counts   # Ch 23

Algorithm 20.10.6 (Profile-guided function ordering, after Pettis & Hansen)

• Input: an undirected weighted call graph: \(w(u,v)\) = number of calls between \(u\) and \(v\) in either direction.
• Output: a linear order of the functions.
• Objective (the course's formulation): minimize \(\Phi = \sum_{\{u,v\}} w(u,v) \cdot \lvert \mathrm{pos}(u) - \mathrm{pos}(v) \rvert\) (unit-size functions), a proxy for keeping caller and callee on the same cache lines and pages.
• Precondition: weights come from a profile of a representative run; functions without calls have weight 0 on every edge.
• Postcondition: the output is a permutation of the functions; each merge placed the endpoints of its edge as close as the four concatenations allow ("closest is best" [PH90]). It does not minimize \(\Phi\) in general (Proposition 20.10.8).
• Invariant: each chain is a contiguous run of the final order; edges are merged heaviest first.

function OrderFunctions(F, w):
    chain(f) ← [f] for every f
    for (u, v) in edges sorted by w(u, v), descending:
        A ← chain(u);  B ← chain(v)
        if A = B: continue
        L ← the first of A·B, A·rev(B), rev(A)·B, rev(A)·rev(B) that minimizes |pos_L(u) − pos_L(v)|
        chain(x) ← L for every x in L
    return the distinct chains, in order of their first function, concatenated

3. Worked example

Instrumentation PGO

Counts. The training run of the running example (box in §7) executes the loop \(10^6\) times: inc is called 999,000 times, dbl 1,000 times. The value profile of the indirect call site (in main, after the pre-inliner put apply there) is {inc: 999000, dbl: 1000}.

Use. Algorithm 20.10.5 step 1: inc has \(999000 / 1000000 = 99.9\%\) of the site's count, above the promotion threshold; dbl has 0.1%, below it:

%15 = icmp eq ptr %14, @inc
br i1 %15, label %16, label %18, !prof !45      ; weights 999000 : 1000
%17 = call i64 @inc(i64 %4)                     ; direct: can be inlined, specialized
%19 = call i64 %14(i64 %4), !prof !47           ; fallback keeps the remaining VP record

Afterwards the optimizer sees the selection ops[(i % 1000) == 999] and folds the guard with it: the final code branches on i % 1000 == 999 directly, with branch_weights 1000, 999000.

Scaling (Theorem 20.10.4). Suppose instead that apply were not pre-inlined and had two callers, run_inc calling apply(inc, …) \(10^6\) times and run_dbl calling apply(dbl, …) \(10^3\) times. apply's context-insensitive value profile is {inc: 1000000, dbl: 1000}. After inlining apply into run_dbl, the scaled profile of that copy is \(\{inc: 10^6 \cdot 10^3/1001000 \approx 999,\ dbl: \approx 1\}\) — it would promote inc in run_dbl, where inc is never called. The true context-sensitive counts are {dbl: 1000}; CSPGO measures them.

Sampling PGO (AutoFDO)

Take step from collatz.c (lines 1–5; line offsets relative to line 1) and the sample profile step:40000:10000 (40,000 total samples, 10,000 head samples) with the per-offset counts in the table. Definition 20.10.3 per instruction and block:

offset	source	samples	instructions (at -O2)
0	long step(long x) {	10000	entry
1	if (x & 1)	10000	and, icmp
2	return 3 * x + 1;	1500	mul, add
3	return x / 2;	8500	ashr

After -O2 the whole function is one block with a select; the loader annotates the select with branch_weights 8500, 1500 (even : odd) and the function with function_entry_count 10000 (box in §7). Had the two returns stayed separate blocks, their weights would be \(\max = 1500\) and \(8500\), and flow conservation would give the branch's edges.

Post-link optimization (BOLT, Propeller)

Algorithm 20.10.6 on a call graph with \(w(\mathit{parse},\mathit{lex}) = 900\), \(w(\mathit{main},\mathit{eval}) = 300\), \(w(\mathit{main},\mathit{parse}) = 100\), \(w(\mathit{lex},\mathit{error}) = 2\), \(w(\mathit{eval},\mathit{error}) = 1\):

edge (weight)	chains before	result
parse–lex (900)	singletons	parse lex
main–eval (300)	parse lex, singletons	main eval
main–parse (100)	parse lex, main eval	candidates: main eval parse lex (distance 2), main eval lex parse (3), eval main parse lex (1), eval main lex parse (2): eval main parse lex
lex–error (2)	eval main parse lex, error	eval main parse lex error (distance 1)
eval–error (1)	one chain	skipped

\(\Phi = 900 \cdot 1 + 300 \cdot 1 + 100 \cdot 1 + 2 \cdot 1 + 1 \cdot 4 = 1306\), which is optimal here (exhaustive search over the \(5! = 120\) orders); Proposition 20.10.8 shows it is not optimal in general.

4. Invariants and correctness

Theorem 20.10.7 (Profiles cannot change semantics)

Let every transformation \(T\) of the pipeline be correct under its static preconditions for every assignment of profile metadata (counts are hints; LangRef makes !prof droppable). Then the program compiled with any profile — accurate, stale, or adversarial — is equivalent to the program compiled without one.

Proof

By induction on the pipeline. Profile metadata never appears in a correctness condition of the chapter's transformations: indirect-call promotion is guarded by a pointer comparison (Lesson 20.7), inlining and cloning preserve semantics for every call site (Lessons 20.3–20.4), splitting and reordering blocks or functions only change code addresses, and the relative placement of code is unspecified in C and C++ (and in LLVM IR), so no program whose behavior is defined can depend on it. Each step therefore maps a program to an equivalent one regardless of the counts it read, and equivalence composes.

The practical consequence is the design of profile matching: a profile record carries a CFG checksum (the Hash in llvm-profdata show), and a record whose checksum does not match the function's current CFG is dropped with a warning rather than applied to the wrong edges — a performance measure, not a correctness one.

Proposition 20.10.8 (Greedy ordering is not optimal)

Algorithm 20.10.6 does not minimize \(\Phi\) in general, whatever tie-breaking it uses; minimizing \(\Phi\) is the weighted minimum linear arrangement problem, which is NP-hard [GJ79].

Proof

Take \(w(a,b) = 6\), \(w(b,d) = 4\), \(w(b,c) = 3\), \(w(a,d) = 2\). The algorithm forms a b, then a b d (distance 1 between \(b\) and \(d\)). For \(b\)–\(c\) every one of the four concatenations of a b d and c puts \(c\) at distance 2 from \(b\) (a b d c, d b a c, c a b d, c d b a), so any tie-breaking yields \(\Phi = 6 + 4 + 3 \cdot 2 + 2 \cdot 2 = 20\) (the last two are the first two reversed). The order c b a d has \(\Phi = 3 + 6 + 4 \cdot 2 + 2 \cdot 1 = 19\). (Checked by exhaustive search over all 24 orders.)

Training inputs are part of the program

A profile describes the training run. If production behaves differently (another input mix, a feature flag), the optimizations are tuned for the wrong program: hot code may be split into the cold section and paid for with an extra jump on every call. Theorem 20.10.7 guarantees correctness, not speed — keep training inputs representative and profiles fresh.

5. Complexity

\(n\) = instructions, \(\lvert E \rvert\), \(\lvert V \rvert\) = CFG edges and blocks per function, \(s\) = samples, \(F\), \(C\) = functions and call-graph edges.

Technique	Time (worst)	Time (typical)	Space	Justification
Instrumentation PGO	\(O(\lvert E \rvert \log \lvert E \rvert)\) per function for the spanning tree; counts: \(O(\lvert E \rvert)\)	instrumented run slower by the counter updates (workload dependent); compile time ≈ normal	one counter per non-tree edge and per value site	Kruskal on \(E\); reconstruction solves the conservation equations in one pass over the tree (Lesson 12.3)
Sampling PGO	profile conversion \(O(s)\); annotation \(O(n)\) plus count inference per function	production overhead of the sampler only (sampling rate); annotation linear	profile \(\propto\) distinct sampled locations	weights are per-location maxima; inference (profi) solves a min-cost flow per function
Post-link (ordering)	Algorithm 20.10.6: \(O(C \log C + C \cdot F)\) naive, \(O(C \log C)\) with union-find and linked chains	seconds for large binaries (BOLT processes whole data-center binaries [PAN+19])	the call graph	edges sorted once; each merge concatenates two chains

Pathological family. For Algorithm 20.10.6, the family of Proposition 20.10.8 generalized (a heavy edge fixing a hub between two neighbours early) gives orders whose \(\Phi\) exceeds the optimum; exact minimization is NP-hard. For PGO: a function whose per-call-site behaviour differs (Theorem 20.10.4(b)) gets counts wrong by up to the full call-site count at every level of inlining, so a deep inline tree compounds the error — the case CSPGO targets.

At scale. Chen, Li and Moseley report that AutoFDO reaches most of the benefit of instrumentation FDO on Google's workloads at a fraction of the deployment cost [CLM16]; Panchenko et al. report that BOLT speeds up large data-center applications even when they were already built with PGO and LTO [PAN+19]; Shen et al. report that Propeller achieves comparable gains with a relinking design that fits distributed builds [SPL+23]. The papers' benchmark numbers are workload-specific; the course did not reproduce them.

6. Variants and refinements

• CSPGO (-fcs-profile-generate, -fprofile-use with a merged profile): a second instrumentation after inlining; the context-sensitive counts are merged with the first profile (box in §7).
• Temporal profiling / function ordering by first execution for start-up time (e.g. mobile apps): order functions by when they are first called, not by call counts.
• Pseudo-probe profiles (CSSPGO): the compiler inserts probe markers into the IR so that sample profiles attach to blocks and inline contexts without relying on line numbers; LLVM then enables profile inference (profi) and ext-TSP block placement by default.
• Profile inference (profi): fit block and edge counts to noisy samples by a minimum-cost flow that satisfies conservation while changing the samples as little as possible (llvm/lib/Transforms/Utils/SampleProfileInference.cpp).
• Ext-TSP layout (Newell & Pupyrev): scores fall-throughs and short forward/backward jumps, and merges chains by splitting one of them (llvm/lib/Transforms/Utils/CodeLayout.cpp); used by BOLT and by LLVM's block placement. Details in Ch 23.
• Machine function splitting (-fsplit-machine-functions): with a profile, the code generator moves cold blocks of a function to .text.split.* — the hot/cold splitting of Lesson 20.4 at the machine level.

7. In real compilers

Instrumentation PGO

LLVM: llvm/lib/Transforms/Instrumentation/PGOInstrumentation.cpp — PGOInstrumentationGen::run and instrumentOneFunc place counters using the spanning tree of CFGMST (llvm/include/llvm/Transforms/Instrumentation/CFGMST.h), PGOUseFunc::populateCounters reconstructs all counts and PGOUseFunc::setBranchWeights attaches them [LLVM-PGOSrc]; PassBuilder::addPGOInstrPasses and addPreInlinerPasses in llvm/lib/Passes/PassBuilderPipelines.cpp place instrumentation after a pre-inliner, and a second, context-sensitive instrumentation later in the pipeline [LLVM-Pipelines]; indirect-call promotion from value profiles is llvm/lib/Transforms/Instrumentation/IndirectCallPromotion.cpp [LLVM-ICP]. GCC: -fprofile-generate / -fprofile-use (gcc/profile.cc, gcc/value-prof.cc).

IR PGO: counters, value profile, promotion, and CSPGO

Reproduce (clang 23.1.2 and llvm-profdata 23.1.2; the course image has no compiler-rt, so the profile runtime libclang_rt.profile comes from conda-forge's compiler-rt23_linux-64 23.1.2 package, unpacked by the first three lines; pgo.c is the running example with int printf(const char *, ...); on top; a toolchain that ships compiler-rt needs neither $RD nor -resource-dir):

curl -sSLO https://conda.anaconda.org/conda-forge/noarch/compiler-rt23_linux-64-23.1.2-h0e38de2_0.conda
mkdir crt && (cd crt && unzip -q ../compiler-rt23_linux-64-23.1.2-h0e38de2_0.conda && tar --zstd -xf pkg-*.tar.zst)
RD=$PWD/crt/lib/clang/23
G=--gcc-install-dir=/usr/lib/gcc/x86_64-linux-gnu/14
clang-23 $G -resource-dir=$RD -O2 -fprofile-generate=. pgo.c -o pgo.instr && ./pgo.instr
llvm-profdata merge -o pgo.profdata *.profraw
llvm-profdata show --all-functions --counts --ic-targets pgo.profdata | sed -n '2,10p'
clang-23 -O2 -fprofile-use=pgo.profdata -Rpass=pgo-icall-prom -c pgo.c -o /dev/null
clang-23 -O2 -fprofile-use=pgo.profdata -mllvm -print-after=pgo-icall-prom -mllvm -filter-print-funcs=main \
  -c pgo.c -o /dev/null 2>&1 | grep -E 'icmp eq ptr|call i64'
clang-23 $G -resource-dir=$RD -O2 -fprofile-use=pgo.profdata -fcs-profile-generate=cs pgo.c -o pgo.cs && ./pgo.cs
llvm-profdata merge -o cs.profdata cs/*.profraw pgo.profdata
llvm-profdata show --showcs --all-functions --counts cs.profdata | sed -n '2,5p'

Output:

265650
  main:
    Hash: 0x0a1bfc6fed398548
    Counters: 2
    Indirect Call Site Count: 1
    Block counts: [1000000, 1]
    Indirect Target Results:
    [  0, inc,     999000 ] (99.90%)
    [  0, dbl,       1000 ] (0.10%)
  apply:
pgo.c:5:37: remark: Promote indirect call to inc with count 999000 out of 1000000 [-Rpass=pgo-icall-prom]
    5 | long apply(op_t f, long x) { return f(x); }
      |                                     ^
  %15 = icmp eq ptr %14, @inc
  %17 = call i64 @inc(i64 noundef %4) #5, !inline_history !46
  %19 = call i64 %14(i64 noundef %4) #5, !prof !47, !inline_history !46
265650
  main:
    Hash: 0x1f9bab1836423f00
    Counters: 3
    Block counts: [999000, 1000, 1]

What to notice: two counters suffice for main's loop (the edges outside the spanning tree; flow conservation gives the rest); apply has count 0 because the pre-inliner already put it into main, so the value profile is per context. The use compile promotes inc (99.9%) behind a pointer guard and keeps the indirect call as fallback. The CSPGO run instruments the post-inline main: its three counts (999 000, 1 000, 1) are those of the inc path, the dbl path and the loop exit — per-context counts the first profile could not provide.

Sampling PGO (AutoFDO)

LLVM: llvm/lib/Transforms/IPO/SampleProfile.cpp — SampleProfileLoader with getInstWeight, inlineHotFunctions (replays the profiled binary's hot inlining before annotating) and emitAnnotations [LLVM-SampleSrc]; block weights and propagation in SampleProfileLoaderBaseImpl::getBlockWeight / propagateWeights (llvm/include/llvm/Transforms/Utils/SampleProfileLoaderBaseImpl.h); the profile formats and the create_llvm_prof converter (from perf.data) are documented in Clang's Users Manual [LLVM-PGO]. GCC: -fauto-profile (gcc/auto-profile.cc).

A text sample profile annotates step

Reproduce (clang 23.1.2; the profile is written by hand in the text format that create_llvm_prof would produce from perf samples — the course container has no perf):

cat > collatz.c <<'EOF'
long step(long x) {
  if (x & 1)
    return 3 * x + 1;
  return x / 2;
}
EOF
printf 'step:40000:10000\n 0: 10000\n 1: 10000\n 2: 1500\n 3: 8500\n' > collatz.prof
clang-23 -O2 -fprofile-sample-use=collatz.prof -S -emit-llvm collatz.c -o collatz.ll
grep -E 'select|function_entry|branch_weights' collatz.ll | sed 's/, !dbg ![0-9]*//'

Output:

  %7 = select i1 %3, i64 %6, i64 %5, !prof !46
!44 = !{!"function_entry_count", i64 10000}
!46 = !{!"branch_weights", i32 8500, i32 1500}

What to notice: %3 is x & 1 == 0, so the select's true side (x / 2, offset 3) gets 8500 and the false side 1500 — the per-line counts of the profile, as the worked example computed; the head samples become the entry count. -fprofile-sample-use turns on line-table debug information by itself, since the profile is keyed by line offsets.

Post-link optimization (BOLT, Propeller)

LLVM: BOLT lives in bolt/ of llvm-project (llvm-bolt, perf2bolt) [LLVM-BOLT]; Propeller's compiler side is basic-block sections, llvm/lib/CodeGen/BasicBlockSections.cpp (BasicBlockSections::runOnMachineFunction, assignSections) reading cluster profiles in BasicBlockSectionsProfileReader.cpp, and the block address map (-fbasic-block-address-map) that lets a profile of the binary be mapped back to block IDs [LLVM-BBSections]; layout algorithms (ext-TSP, cache-directed sort) in llvm/lib/Transforms/Utils/CodeLayout.cpp [LLVM-CodeLayout].

Basic-block sections: mapping blocks and splitting the cold one

Reproduce (clang 23.1.2, llvm-readobj 23.1.2, llvm-objdump 23.1.2; llvm-bolt and perf are not available in the course image, so the cluster file is written by hand where Propeller's profile converter would produce it):

cat > work.c <<'EOF'
long report(long v);
long work(const long *a, long n) {
  long s = 0;
  for (long i = 0; i < n; i++) {
    if (a[i] < 0)
      s -= report(a[i]);   /* rare */
    else
      s += a[i];
  }
  return s;
}
EOF
clang-23 -O1 -fbasic-block-address-map -c work.c -o work.o
llvm-readobj --bb-addr-map work.o | grep -E '^ +(ID|Size):' | paste - -
printf 'v1\nf work\nc 0 1 3 6 7 2\n' > work.prop
clang-23 -O1 -fbasic-block-sections=list=work.prop -c work.c -o work.split.o
llvm-readelf -S work.split.o | grep -E ' \.text\.(hot|split)'
llvm-objdump -d --no-show-raw-insn work.split.o | grep -E '>:|call'

Output:

            ID: 0               Size: 0xD
            ID: 1               Size: 0xD
            ID: 5               Size: 0x3
            ID: 6               Size: 0x8
            ID: 3               Size: 0x9
            ID: 4               Size: 0xA
            ID: 7               Size: 0x2
            ID: 2               Size: 0xF
  [ 3] .text.hot.work    PROGBITS        0000000000000000 000040 000045 00  AX  0   0 16
  [ 5] .text.split.work  PROGBITS        0000000000000000 000090 000015 00  AX  0   0 16
0000000000000000 <work>:
0000000000000000 <work.cold>:
       8:       callq   0xd <work.cold+0xd>

What to notice: the address map gives every machine block an ID and a size — the key a sampled profile of the binary is mapped through. The cluster 0 1 3 6 7 2 lists the hot blocks; the unlisted ones (block 4 with the report call — 10 bytes: call, sub, jmp — and block 5, the n <= 0 path) go to work.cold in .text.split.work, which the linker can place far from hot code. BOLT's documented flow does the same on the binary: perf record -e cycles:u -j any,u, perf2bolt -p perf.data -o perf.fdata <exe>, then llvm-bolt <exe> -o <exe>.bolt -data=perf.fdata -reorder-blocks=ext-tsp -reorder-functions=cdsort -split-functions -split-all-cold -split-eh -dyno-stats (quoted from bolt/README.md at llvmorg-23.1.2 [LLVM-BOLT]; not run here).

Find where LLVM does it. Open llvm/lib/Transforms/Instrumentation/PGOInstrumentation.cpp: its header cites the paper whose spanning-tree method the pass uses to place the minimum number of counters. Who are the authors, and which class implements the spanning tree? (Quiz llvm-where-pgo-mst.)

8. Comparison

Technique	Power / precision	Speed (asymptotic · practical)	Output / error quality	Implementation effort	Typical use
Instrumentation PGO	Exact counts for the training run; value profiles; CSPGO adds post-inline contexts	linear instrumentation · instrumented run markedly slower, separate training build	Stale profiles are detected by CFG checksums and dropped with a warning	Moderate (spanning tree, runtime, profile format)	Release builds of compilers, browsers, databases; with LTO/ThinLTO
Sampling PGO (AutoFDO)	Statistical, per source line; loses precision where optimization blurs line info	linear annotation · no training build, negligible production overhead	Staleness tolerated by line offsets; mismatches degrade silently	High (debug-info mapping, inference, converters)	Continuous FDO of data-center fleets, kernels
Post-link (BOLT, Propeller)	Layout only (blocks, functions, splitting) but for the whole final binary including libraries	near linear in binary size · BOLT: one rewrite; Propeller: relink	Works on the binary actually shipped; BOLT needs relocations (--emit-relocs)	Very high (binary rewriting; or compiler + linker co-design)	Large, front-end-bound server binaries, compilers (on top of PGO+LTO)

Choose instrumentation PGO when you can run a representative training workload in the build: it is the most precise and drives every decision of this chapter. Choose sampling PGO when the real workload is only observable in production. Choose post-link optimization when the binary is large and front-end bound (instruction-cache and TLB misses), usually in addition to PGO and LTO.

9. Assessment

• Quiz (./course quiz 20): ipgo-counters, ipgo-context-scaling, llvm-where-pgo-mst (tag ipgo); autofdo-block-weight, autofdo-line-offsets (tag autofdo); bolt-ph-order, bolt-ph-not-optimal, postlink-why (tag bolt).
• Drill: none: the counter placement drill belongs to Ch 12, and Algorithm 20.10.6's ordering is asked for a fresh graph in the quiz (bolt-ph-order).
• Flashcards: tags ipgo, autofdo, bolt.
• Exercises: E2 pebble-inline, profile= mode, and the inlining lab.

References

See the chapter references.