Whole Programimplementation

Profile-Guided Optimization

Compile once with counters, run a realistic workload, feed the counts back, compile again. The optimizer stops guessing which branch is taken and which function is hot — and the largest real win is usually not what people expect.

The question

How does a compiler find out which paths are hot, and what does it do differently once it knows?

Source→Lexing→Tokens→Parsing→AST→Semantics→Typed→IR→Optimize→Codegen→Machine code→Link→Execute
What the program is here

The program plus an *edge profile*: a count attached to every control-flow edge and every function entry, from which block frequencies and call counts are derived. This is the first representation in the pipeline that contains a fact about execution rather than a fact about the program text — everything the optimizer knew until now was true of all possible runs, and this is true of some particular ones.

What this phase may assume or do

A profile is evidence about frequency, never a proof about possibility, so it may only be used to *choose between* transformations that are already legal without it — which function to inline, where to place a block, which value to keep in a register. It may never license a transformation that would be wrong on an input the profile did not cover. Deleting a branch because the profile never took it is illegal in a static compiler for exactly this reason: the untaken path is still reachable, and removing it changes behavior for an input the workload did not exercise. Acting on a profile as though it were a proof requires a runtime guard and an undo path, which is what a JIT has and an ahead-of-time compiler does not.

Key points

  • The loop is instrument, run a realistic workload, merge the counts, recompile — and the profile is evidence about frequency, never proof about possibility.
  • A profile may only choose among transformations that are already legal; it may not license one that would be wrong on an unexercised input.
  • What changes: inlining budgets, block and function layout, branch arrangement, register allocation and spill placement, unroll thresholds and switch lowering.
  • Block layout and instruction-cache locality is usually the largest real win, not branch prediction, because modern predictors already learn the branches a profile would describe.
  • Cold code moved out of line makes hot cache lines and iTLB entries carry more useful instructions, which is a front-end effect no predictor can address.
  • PGO frequently improves speed and size at once, because cold call sites stop being inlined while hot ones inline harder.

The loop

The classic instrumented form is four steps and one non-negotiable requirement. The requirement is that the workload in step two resembles production, because everything downstream is a faithful optimization of whatever you actually ran.

Step one compiles with counters inserted: at function entries and at control-flow edges, enough to reconstruct every block frequency by solving the flow equations rather than by counting every block directly. Step two runs that binary — slowly, because the counters cost real time — against a workload. Step three merges the raw counter files into a single profile, which is a separate step because a realistic profile is usually the sum of many runs. Step four recompiles from the original sources, feeding the profile in, and the optimizer now annotates every block and edge with a frequency before it makes a single decision.

Note what does not change: the source, the language semantics, and the set of legal transformations. What changes is the ordering of decisions that were always available, and the budgets attached to them.

Instrumented PGO, end to endimplementation
  1. Instrumented buildbuild time
    The program plus counter increments on entries and edges.
    The ability to observe frequency at all.
    Speed — the instrumented binary is substantially slower and is not shippable.
  2. Training runrun time
    A running process writing raw counter files.
    Evidence about one particular workload.
    Nothing yet, but everything not exercised is now invisible.
  3. Mergebuild time
    One profile: counts per function, per edge, indexed by a hash of each function's structure.
    A single artifact combining many runs.
    Which run contributed what — a bimodal workload becomes an average of two behaviours.
  4. Optimizing rebuildbuild time
    IR with block frequencies attached, from the original sources.
    Frequency-aware inlining, layout, hinting and allocation priorities.
    Correspondence with the profile if the source has drifted since it was collected.
  5. Shipped binarybuild time
    Machine code laid out around the profiled hot path.
    Dense, contiguous hot code and cold code moved out of the way.
    Any advantage at all for a workload unlike the training one.

Read it asThe only stage that touches the real world is the training run, and every later stage is a faithful amplification of it. That is why the quality of the profile dominates every other consideration in this lesson — the mechanism has no way to be better than its evidence.

What the compiler actually does differently

typicalThe claim that layout dominates is a repeated empirical result on large server binaries, not a law. On a small numeric kernel that already fits in L1 instruction cache there is no layout win available, and the gain comes almost entirely from inlining and unrolling. The ranking follows the size and shape of the program's hot code, so measure rather than assume which effect you are getting.

Four decisions change, and it is worth ranking them by how much they matter in practice, because the popular ranking is wrong.

Block layout is usually the biggest win. With frequencies known, the compiler orders basic blocks so that the hot path falls through contiguously and cold blocks — error handling, rare branches, logging, the slow path of an inline cache — are moved out of line, sometimes into a separate .text.unlikely section. The effect is on the instruction cache and the front end: hot code becomes dense, so a cache line and an iTLB entry carry more useful instructions and fewer never-executed ones. On a large binary with a diffuse hot path, this is where most of the measured gain lives.

Inlining decisions change. A call executed a billion times justifies inlining a body that a call executed twice does not, and inlining is the transformation that exposes constants and types for everything else. Frequency turns a size heuristic into a cost-benefit calculation, and it works in both directions: cold callers stop inlining and the binary gets smaller where it does not matter.

Branch hints and layout of conditionals. The compiler arranges the condition so the common outcome is the fall-through, and on targets with static hint encodings it can emit them. This matters far less than it sounds — see below.

Register allocation priorities. When values compete for registers, the one live across the hot loop wins and the one live only on the cold path spills. Spill placement moves into cold blocks, so the cost of spilling is paid on paths that rarely execute — see [[spilling]].

Secondary effects follow from the same information: loop unrolling thresholds respond to trip counts, switch lowering picks a jump table or a comparison chain based on case frequency, and function ordering in the binary places callers next to callees so they share pages.

  • Block layout and function ordering — hot code contiguous, cold code out of line. Instruction-cache and iTLB locality. Usually the largest real effect.
  • Inlining — frequency-weighted budgets, so hot call sites inline aggressively and cold ones stop, which improves speed and size simultaneously.
  • Branch arrangement and hints — the common outcome becomes the fall-through.
  • Register allocation and spill placement — hot values win registers; spills are pushed onto cold paths.
  • Loop and switch shaping — unroll thresholds from trip counts, jump table versus comparison chain from case frequency.

Why layout beats branch prediction

The intuitive story is that PGO tells the CPU which way branches go. That story is largely obsolete, and understanding why is the most useful thing in this lesson.

Modern branch predictors are dynamic, history-based and very accurate on the predictable branches a static hint would have described — a branch that a profile says goes one way 99% of the time is a branch the hardware learns in a handful of executions and then predicts correctly on its own. Some architectures removed static hint encodings entirely because they were not earning their space. So the compiler telling the processor what a profile said is, on those branches, telling it something it already knows.

The front end is a different matter, because no amount of prediction accuracy fixes a fetch that misses in the instruction cache. Instruction fetch pulls whole cache lines; if a hot loop is interleaved with rarely executed error-handling code, every line fetched carries dead weight, the effective cache is smaller than its size suggests, and the same is true one level up for iTLB coverage. Rearranging blocks and functions so hot code is dense does not make any single branch more predictable — it makes the instructions already be there, which is a cost the predictor cannot address at all.

That is the mechanism behind the whole family of post-link layout tools, and it is why they can win on a binary that was already built with PGO: they are attacking the front end, not the predictor.

Block layout for a hot loop with a rare error path
Before
loop:
  r = step()
  if (r != OK) goto handle      ; taken ~0.01% of the time
  n = n + 1
  if (n < limit) goto loop
  goto done
handle:
  log_error(r)                  ; sits between the branch and its target
  cleanup()
  goto done
done:
After
; .text.hot
loop:
  r = step()
  if (r != OK) goto handle      ; forward branch out of line
  n = n + 1
  if (n < limit) goto loop      ; hot path is now contiguous
done:

; .text.unlikely  — a different part of the binary entirely
handle:
  log_error(r)
  cleanup()
  goto done
Legal only when

Reordering basic blocks preserves observable behavior for any input, because the control-flow graph is unchanged — only the addresses are. The profile is used purely to choose among orderings that are all correct, which is why layout is the safest possible use of profile data.

Illegal when

The rewrite stops being a reordering and starts being a removal. Deleting the handle block because the profile never reached it changes what the program does for an input the training workload did not cover. A static compiler may not do that; a JIT may, and only because it installs a guard and can deoptimize back — see [[guards]] and [[deoptimization]].

How it works

The steps, in the order the compiler takes them.

  • The compiler inserts counters at function entries and on control-flow edges, chosen so every block frequency can be reconstructed from the flow equations rather than counted directly.
  • The instrumented binary runs against a workload and writes raw counter files, one or many.
  • A merge tool combines the raw files into a single profile, keyed by function and by a hash of each function's control-flow structure.
  • The optimizing rebuild reads the profile and attaches a frequency to every block and edge before any decision is made.
  • Inlining runs with frequency-weighted budgets, so hot call sites get much larger allowances than cold ones.
  • Block placement orders the hot path for fall-through and moves cold blocks into a separate section; function ordering places callers near callees.
  • Register allocation prioritises values live on hot paths and places spill code in cold blocks.
  • A function whose structure hash no longer matches the profile is compiled without profile data, silently, because the counts can no longer be attributed to its blocks.

How it breaks

What the engineer observes when it goes wrong — not what goes wrong internally.

  • The profile is collected from a benchmark rather than production, and the shipped binary is faster on the benchmark and unchanged or slower on the real workload.
  • A function is edited after the profile was collected, its structure hash stops matching, and it is quietly compiled with no profile at all — no error, just a hot function that lost its optimization.
  • The instrumented binary is two to three times slower, a load test built around it times out, and the profile ends up describing a degenerate run rather than a realistic one.
  • Counter updates in a heavily multithreaded program contend on shared cache lines, distorting the very timing the profile is meant to capture.
  • The build becomes two-phase, a CI job runs the second phase without the first, and a release ships with no profile applied while everyone believes PGO is on.
  • A binary with .text.unlikely populated confuses a symbolication or coverage tool that assumed one contiguous text section.

When it helps

  • Large binaries with a diffuse hot path — servers, browsers, compilers, databases — where instruction-cache locality is a first-order cost and layout has the most to fix.
  • Programs with a stable, well-understood workload that a training run can genuinely represent.
  • Code with abundant cold paths interleaved into hot ones: error handling, assertions, logging, rare fallbacks.
  • Interpreters and dispatch loops, where the hot path is small, extremely hot, and surrounded by rarely taken cases.
  • Situations where binary size matters as well as speed, since frequency-guided inlining improves both.

When it hurts

  • Small compute kernels that already fit in instruction cache, where there is no layout win and the machinery is not worth the build complexity.
  • Programs with no representative workload — a general-purpose library used differently by every consumer, or a tool whose inputs vary wildly.
  • Rapidly changing code, where the profile is stale before it is useful and most functions silently fall back to no profile.
  • Teams without the CI capacity to run the two-phase build reliably, where the failure mode is a release that silently skipped the profile.

What it costs

Every one of these is paid by something.

  • A profile buys frequency-aware decisions and pays with a two-phase build: two compiles, a training run in between, and a pipeline that can fail in the middle.
  • Instrumentation buys exact counts and pays in a binary too slow to ship and, on threaded programs, in counter contention that perturbs what is being measured.
  • Hot/cold splitting buys instruction-cache density and pays in a fragmented text section that complicates symbolication, coverage tooling and anything assuming contiguity.
  • Frequency-guided inlining buys speed on hot paths and pays in code size there, offset by savings on cold paths — a trade that has to be measured rather than assumed.
  • The whole mechanism buys performance and pays in reproducibility: the artifact now depends on a training run, which is an input that no source control system holds — see [[reproducible-compilation]].

What else you could do

What a different compiler or language does instead, and when that is better.

  • Sampling-based PGO — AutoFDO and its relatives — collects a profile from an ordinary optimized binary running in production, at very low overhead, avoiding the instrumented build entirely. The profile is coarser; the trade is the subject of [[pgo-tradeoffs]].
  • Post-link optimizers such as BOLT and Propeller apply layout to an already-linked binary using samples. They capture most of the layout win without a second compile, and are complementary to a PGO build rather than a replacement for it.
  • Manual annotations — C++'s likely and unlikely attributes, __builtin_expect, hot and cold function attributes — put a human's belief where a measurement would go. Cheap, never stale in the same way, and frequently wrong.
  • A JIT collects the profile continuously during the run it is optimizing, and can act on it speculatively because it can undo the assumption — [[jit-compilation]].
  • Ordering functions by a linker script from any source of hotness information, which captures part of the layout benefit with almost no build complexity.

See it for yourself

The flag, dump or tool that shows you this directly.

  • Clang: -fprofile-generate to build instrumented, run the workload, llvm-profdata merge -output=app.profdata *.profraw, then rebuild with -fprofile-use=app.profdata.
  • GCC: -fprofile-generate then -fprofile-use, plus -fprofile-partial-training to control how untrained functions are treated.
  • llvm-profdata show --all-functions app.profdata prints per-function counts — the fastest way to see whether the training run reached what you expected.
  • clang -fprofile-use=... -Rpass-missed=inline reports which hot call sites were still declined and why.
  • nm -S --size-sort and objdump -h show whether .text.unlikely exists and how much of the binary ended up there.
  • perf stat -e L1-icache-load-misses,iTLB-load-misses before and after: if PGO helped through layout, this is the counter that moves.

Plausible wrong readings

Stated the way a confident engineer states them.

  • "PGO tells the CPU which way branches go." Mostly the hardware already knows. The gain is dominated by where the instructions physically sit, which the predictor cannot help with.
  • "The profile lets the compiler remove paths that never run." Never, in a static compiler. An unexecuted path is still reachable; removing it needs a runtime guard, which is a JIT's mechanism.
  • "Any profile is better than none." An unrepresentative profile is worse than none, because it optimizes confidently for the wrong path — the subject of the next lesson.
  • "PGO makes the binary bigger." It commonly makes it smaller, because cold call sites stop being inlined while hot ones inline harder.

Misconceptions

The claim, and what is actually true.

PGO is an optimization.
It is an input. Every transformation it influences existed already; the profile changes which of them are chosen and with what budget.
A profile proves a branch is never taken.
It proves that branch was not taken during the training run. The path is still reachable, and a static compiler must keep it.
You need production traffic to benefit.
You need a workload that resembles production. A load test that exercises the right paths in the right proportions is enough, and is how most projects do it.
PGO and LTO compete.
They supply different information — scope and frequency — and are routinely used together, with the profile guiding the cross-module inlining decisions LTO made possible.

Go deeper

The same idea at increasing depth. Stop wherever it stops being useful.

overview

The compiler does not know which branch your program usually takes or which functions run constantly, so it guesses from heuristics. PGO replaces the guess with a measurement: build a version that counts, run it on realistic work, then rebuild using the counts. The compiler then inlines what is actually hot and physically arranges the binary so the code that runs constantly sits together.

practical

Get the workload right; nothing else in the mechanism matters as much. Collect from something that resembles production — a load test with the right mix, not a microbenchmark. Check llvm-profdata show to confirm the training run actually reached the code you care about. Expect the instrumented binary to be badly slow and plan the training run around that. Measure both speed and binary size afterwards, and if you want to know whether the win came from layout, watch instruction-cache miss counters rather than branch mispredictions. And build the two-phase pipeline so that a missing profile fails the build rather than silently producing an unoptimized release.

advanced

The design tension is that a profile is per-function evidence being applied to a program whose source has moved. Profiles are keyed by a hash of each function's control-flow structure precisely so that a stale profile is *dropped* rather than misapplied — attributing counts to the wrong blocks would be worse than having none. That makes staleness a silent, per-function degradation rather than a build error, which is why large deployments treat profile freshness as an operational metric and not a build artifact. It also explains why sampling-based approaches are attractive despite being coarser: a profile continuously harvested from production is never more than a day stale, and staleness turns out to cost more than resolution does. The generalisation is worth holding onto — in feedback-directed systems, the recency of the evidence usually dominates its precision.

How much this depends on

Nothing in this domain is true of every compiler. These say how much.

implementationFlags, profile formats and merge tools are per-toolchain and not interchangeable: Clang uses -fprofile-generate/-fprofile-use with llvm-profdata, GCC uses .gcda files and its own semantics for untrained functions, MSVC uses /GENPROFILE and /USEPROFILE, and Go's PGO consumes a pprof CPU profile placed in the package directory. A profile produced by one toolchain is meaningless to another, and formats change across major versions of the same one.
typicalThat layout dominates the gain is characteristic of large binaries with poor instruction-cache locality — servers, browsers, compilers. It is not universal: on a small hot kernel there is no layout problem to fix and the benefit comes from inlining and unrolling instead. Which effect you got is a measurement, not a category.
targetStatic branch hint encodings exist on some instruction sets and were removed from others precisely because dynamic predictors made them redundant, so the "branch hint" component of PGO is worth roughly nothing on some targets and non-trivial on others. Instruction-cache and iTLB sizes also differ enough between cores that a layout win measured on one machine can be materially smaller on another.

If you were asked this in an interview

  • Walk me through the PGO build loop, and say what makes it a legal use of a profile.
  • PGO improved your binary by 12%. Which of the transformations it enabled most likely produced that, and how would you confirm it?
  • Why can a JIT delete a branch a profile never took, and a static compiler cannot?

Connections

Computer Architectureinstruction-cachebranch-predictionbranch-mispredictionspatial-localityperformance-counterstlb-misses
Performancecpu-profilingflame-graphscontinuous-profilingmeasure-before-optimizingbenchmarkingload-test-shapes
Domains that do not exist yet
  • Programming Languages & Runtime Internals — Continuous in-process profiling and the runtime structures a JIT keeps to act on it
    PGO stops where the runtime begins: it collects evidence beforehand and can only choose among legal transformations. A runtime that profiles continuously can also speculate, because it owns the guard and the undo path, and those structures are that domain's subject.