Lesson 20.9 — Whole-program compilation: monolithic LTO and ThinLTO¶

Techniques: monolithic link-time optimization — merge every module's IR at link time, internalize, optimize and generate code as one unit (Lattner & Adve 2004; LLVM's LTO with ld.lld, gold, ld64; GCC's -flto with WHOPR partitions); ThinLTO — per-module summaries, a thin link over the summary index (import and export decisions, dead-symbol elimination, internalization, promotion, index-based WPD) and parallel, incremental per-module backends (Johnson, Amini & Li 2017) · Pebble implements: nothing new — pebble-inline and pebble-funcattrs become whole-program passes when run on a merged module (llvm-link + opt), which is how the comparison lab treats its single-file benchmarks · Prerequisites: Lessons 20.3–20.7 (what LTO enables); linkage, visibility and symbol resolution (Ch 9) · Time: 5–7 hours

Every technique of this chapter works better when it sees more of the program: internal functions can lose dead arguments (Lesson 20.6), a whole class hierarchy can be devirtualized (Lesson 20.7), a function defined in another file can be inlined (Lesson 20.3). A C or C++ compiler, however, sees one translation unit at a time. Link-time optimization (LTO) postpones optimization until the linker has all the object files — which then contain IR instead of machine code. The running example has two files:

/* main.c */
int printf(const char *, ...);
int scale(int x, int k);
int unused_helper(int x);
int main(int argc, char **argv) { printf("%d\n", scale(argc, 4)); return 0; }

/* lib.c */
int scale(int x, int k) { return k == 0 ? -1 : x * k; }
int unused_helper(int x) { return x ^ 0x5a5a; }

Compiled separately, main must call scale through the object file interface; unused_helper must be kept because some other object might call it. Linked with LTO, scale is inlined into main, k == 0 folds, and unused_helper disappears.

1. Problem and motivation¶

Monolithic LTO¶

Lattner and Adve designed LLVM for "lifelong" optimization, with the IR preserved into link time so that the whole program can be optimized as one module [LA04]. In monolithic (full) LTO, clang -flto writes bitcode into the object files; at link time the linker's LTO plugin reads every bitcode file, resolves symbols (which definition prevails, which symbols are referenced by native objects or exported from the executable), merges all modules into one with the IR linker, internalizes every symbol nobody outside needs, runs the LTO pipeline (lto<O2>: IPSCCP with specialization, whole-program devirtualization, GlobalOpt, the inliner over the whole call graph, …) and generates code [LLVM-LTO]. The result is optimal as far as the passes go, but the merged module is serial: memory and time grow with the whole program, and any change relinks everything. GCC's -flto is monolithic in its analysis (WPA) and partitions the program for parallel code generation (WHOPR).

ThinLTO¶

Johnson, Amini and Li observed that the whole-program decisions need only a small summary of each module — its functions' sizes, calls with hotness, references to globals, flags — and that the transformations can run per module in parallel if each backend is given the few functions it needs to inline from other modules [JAL17]. ThinLTO therefore: (1) at compile time, writes a module summary next to each module's bitcode; (2) at link time, performs a thin link over the combined summary index — computes which functions each module should import, which symbols must be exported (and local symbols promoted to global with unique names, since an imported copy refers to them), which are dead, which can be internalized, whole-program devirtualization decisions and attribute propagation; (3) runs one backend per module, in parallel and cacheable, that imports the chosen functions as available_externally definitions and optimizes and generates code for that module alone [LLVM-ThinLTO]. Build time and memory scale like non-LTO builds; incremental builds reuse cached backends whose inputs did not change.

2. Definitions and algorithms¶

Definition 20.9.1 (LTO symbol resolution)

For every symbol \(s\) of every IR object, the linker provides a resolution: \(s\) is prevailing in the object whose definition the link selects (p), is visible to regular objects if a native object or the dynamic symbol table references it (x), and so on (llvm-lto2's -r=file,symbol,flags). A symbol is exported from the LTO unit if it is visible to regular objects or is used by another LTO module (the latter only in ThinLTO, where modules stay separate).

Definition 20.9.2 (Internalization)

Internalizing a prevailing definition \(s\) gives it local linkage (and deletes non-prevailing copies); it is allowed when \(s\) is not visible to regular objects and not exported — then no code outside the IR being optimized can name \(s\).

Algorithm 20.9.3 (Monolithic LTO)

Input: IR objects \(O_1, \dots, O_m\) and native objects; the linker's resolutions.
Output: one native object for the LTO part (or several, with parallel code generation).
Precondition: every IR object was compiled with the same assumptions it would have natively (ABI, target).
Postcondition: the linked program behaves as the separately compiled one (Theorem 20.9.6).
Invariant: only prevailing definitions are kept; a symbol is internalized only under Definition 20.9.2.

function MonolithicLTO(objects, resolutions):
    M ← empty module
    for O in objects: IRMove(O into M, keeping prevailing definitions only)
    for each global s in M:
        if s is prevailing and not visible to regular objects: make s internal       # Definition 20.9.2
    Optimize(M, "lto<O2>")         # IPSCCP + function specialization, WPD, GlobalOpt, inliner, …
    CodeGen(M)                     # optionally split into N partitions for parallel codegen

Definition 20.9.4 (Module summary index)

A function summary holds: the instruction count, flags (noinline, alwaysinline, readNone, norecurse, …), the list of calls (callee GUID, hotness from a profile: cold/none/hot/critical), the list of refs (globals referenced), linkage and visibility; a variable summary holds its refs and read-only / write-only flags. The combined index of a link maps each GUID (a hash of the global's name, qualified by the source file for local symbols) to its summaries in every module, plus the resolution flags. Each module's summary is written into its bitcode (^N = gv: (...) records in llvm-dis output).

Algorithm 20.9.5 (ThinLTO function import, one module)

Input: the combined index; module \(M\)'s defined functions; the limit \(L\) (import-instr-limit, 100), the evolution factor \(\alpha\) (0.7), multipliers for hot (10), critical (100) and cold (0) call edges.
Output: \(\mathrm{Imports}(M)\), a set of (function, source module) pairs; the corresponding exports of the source modules.
Precondition: the index is complete (every module of the link summarized).
Postcondition: every imported function has an instruction count \(\le\) the threshold of the edge through which it was reached; its definition is eligible (not noinline, not interposable, not referencing symbols that cannot be promoted).
Invariant: a function is (re)examined only with a threshold larger than any it was examined with before.

function ComputeImports(M):
    W ← [(f, L) for each function f defined in M]
    seen ← {}                                          # GUID ↦ best threshold examined
    while W ≠ []:
        (f, T) ← pop W
        for each call edge f → g with hotness h:
            if g is defined in M: continue
            T' ← T × multiplier(h)
            if seen[g] ≥ T': continue
            seen[g] ← T'
            s ← the prevailing, eligible summary of g
            if s = none or s.instCount > T' (and not alwaysinline): continue      # TooLarge
            Imports(M) ∪= {(g, module(s))};  Exports(module(s)) ∪= {g} ∪ refs(s)
            push (g, T' × (h hot ? 1.0 : α)) on W                               # next level: smaller budget
    return Imports(M)

Theorem 20.9.6 (Internalization and ThinLTO importing preserve behavior)

(a) Internalizing symbols under Definition 20.9.2 and running any behavior-preserving optimization on the merged module preserves the program's behavior. (b) Importing a function \(g\) into module \(M\) as an available_externally copy, together with promotion — renaming every local symbol \(g\) references to a unique global name in its source module and in the copy — preserves behavior, provided \(g\)'s prevailing definition is the one imported (the One-Definition Rule holds for linkonce_odr/weak_odr copies).

Proof

(a) A symbol that no native object and no dynamic lookup can reference is referenced only by IR in the merged module; giving it local linkage changes no reference's target. Local linkage is exactly the condition under which the passes of Lessons 20.3–20.6 may delete, clone, specialize or change the signature of a function, and those passes are behavior-preserving under that condition (Theorems 20.3.2, 20.4.4, 20.6.11).

(b) An available_externally definition means "this body is identical to the one that will be linked; you may inspect and inline it, but do not emit it". Inlining it is inlining the prevailing definition (Theorem 20.3.2); any remaining call binds to the real definition in the source module, which is still emitted there. The copy's references to local symbols of its source module would be dangling in \(M\); promotion gives each such local a unique external name (suffix .llvm.<hash of the module>) in the source module and makes the copy reference that name, so every reference still denotes the same object. The ODR proviso makes the choice of copy irrelevant for duplicated definitions.

The summary is only as good as its flags

The thin link decides from summaries, not IR: if a module's summary says a function is small but its body is large (e.g. the summary was computed before an earlier inlining in the pre-link pipeline), the import decision is wrong in cost, never in correctness — correctness only depends on (b)'s conditions, which the index records (notEligibleToImport, linkage, the refs that must be promotable).

3. Worked example¶

Monolithic LTO¶

Resolutions for the example (as the linker would give them for an executable): main.o: main prevailing and visible to regular objects (the C runtime calls it: px), printf and scale undefined; lib.o: scale and unused_helper prevailing, not visible (p). Algorithm 20.9.3:

step	module after the step
IR move	one module with `main`, `scale`, `unused_helper`, `declare printf`
internalize	`scale` and `unused_helper` become `internal`; `main` stays external
`lto<O2>`	`scale` inlined into `main` (last call of an internal function: Definition 20.3.7's bonus); `k = 4 ≠ 0` folds; `unused_helper` is internal and unused: deleted
codegen	one object defining `main` only

ThinLTO¶

Summaries (box in §7): main's summary records insts: 3, calls to scale and printf, a ref to the string .str; lib.o's records scale and unused_helper with their sizes. Thin link, Algorithm 20.9.5 for main.c: the only call edge into another module is main → scale (no profile: hotness none, multiplier 1): \(T' = 100\), scale's instruction count is far below: import it. For lib.c: no calls to other modules. Exports of lib.c: scale. Dead-symbol analysis: unused_helper is not reachable from any exported or visible root, so it is dead; scale is referenced from main.o and cannot be internalized in lib.o (it is exported), but it can be made available_externally in main.o. Backends (in parallel): main.o's backend sees define available_externally i32 @scale, inlines it and emits only main; lib.o's backend emits scale (still needed if any call remains; here none does, but the backend cannot know that) and drops unused_helper.

Import budget. For a longer chain the evolution factor matters. Let module A's main call f (40 instructions, in B), f call g (65, in C), g call h (50, in D), all edges without profile:

examined	threshold \(T'\)	instCount	decision	next-level threshold
f (from main)	100	40	import	70
g (from f)	70	65	import	49
h (from g)	49	50	too large: not imported	—

With a hot edge g → h (multiplier 10), \(T' = 490\) and h would be imported: profiles make ThinLTO import along hot paths (Lesson 20.10).

4. Invariants and correctness¶

Theorem 20.9.6 is the correctness of both forms. The complementary fact explains why ThinLTO's decisions are cheap:

Proposition 20.9.7 (Import computation terminates and bounds the imported code)

Algorithm 20.9.5 terminates. Without hot or critical edges, every function imported through a chain of \(j\) call edges has at most \(L \alpha^{j-1}\) instructions, so for \(\alpha < 1\) the depth of import chains is at most \(1 + \log_{1/\alpha} L\) (with \(L = 100\), \(\alpha = 0.7\): 13 levels).

Proof

Each push carries a threshold at most \(\alpha\) times its parent's (hot edges: at most the parent's times the hot multiplier times the hot evolution factor, which defaults to 1 — hence the "without hot edges" hypothesis). A function is pushed again only with a strictly larger threshold than any before (the seen test), and thresholds come from a finite set of products of \(L\) with the factors along edges of the finite index, so pushes are finite. The size bound follows by induction on \(j\); a function is imported only if its size is at most a threshold \(\ge 1\), i.e. only while \(L \alpha^{j-1} \ge 1\).

Visible to regular objects is a whole-program fact

Internalization is only as sound as the linker's resolutions. A symbol referenced from assembly, from dlsym, or from a shared library built separately must be reported as visible (or exported with --export-dynamic), or the LTO step will internalize and possibly delete it.

5. Complexity¶

\(P\) = size of the whole program, \(m\) = modules, \(\lvert I \rvert\) = index size, \(p\) = parallel jobs.

Technique	Time (worst)	Time (typical)	Space	Justification
Monolithic LTO	\(O(\text{passes}(P))\) serial for optimization; codegen can be split	minutes to hours for very large programs	\(O(P)\): the merged module in memory	one module; interprocedural passes are super-linear in the worst case (inlining, Lesson 20.3)
ThinLTO	thin link \(O(\lvert I \rvert)\) + \(\sum_M O(\text{passes}(\lvert M \rvert + \text{imports}))\) / \(p\)	close to a non-LTO build; incremental with a cache	index + one module per job	summaries are small (a few percent of the IR); backends are independent

Pathological family. For monolithic LTO: any program whose IR does not fit in memory, or where a one-line change must re-optimize everything — the reason ThinLTO exists. For ThinLTO: a "hub" function called from every module and itself calling small functions in many modules is imported into every backend, so its body (and its imports) are optimized \(m\) times; the evolution factor and import-instr-limit bound the damage per backend, not the total.

At scale. Johnson, Amini and Li report that ThinLTO achieves most of the run-time performance of full LTO on the SPEC CPU 2006 C/C++ benchmarks, with link times and memory close to a non-LTO build and much smaller than full LTO's on large programs such as Chromium [JAL17, §5].

GCC WHOPR (-flto -flto-partition=…): whole-program analysis on summaries (WPA), then parallel optimization of partitions — ThinLTO's idea with partitioning by the compiler instead of by source module.
Distributed ThinLTO (-thinlto-distributed-indexes, DTLTO): the thin link writes one small index per module, and the backends run on remote build machines (Bazel, Buck).
Incremental ThinLTO caches (--thinlto-cache-dir): a backend's output is keyed by a hash of its inputs, imports and options; unchanged modules are not recompiled.
Unified LTO (-funified-lto): one bitcode format usable by either full or thin LTO.
Split LTO units for WPD (-fsplit-lto-unit): vtables and type metadata go to a small full-LTO part so that ThinLTO can still devirtualize over the whole hierarchy (Lesson 20.7).
Post-link optimization (BOLT, Propeller; Lesson 20.10): after LTO, optimize the binary using profiles.

7. In real compilers¶

Monolithic LTO¶

LLVM: llvm/lib/LTO/LTO.cpp — LTO::run dispatches to LTO::runRegularLTO (merge with the IR mover, internalize, opt, codegen) and LTO::runThinLTO [LLVM-LTOSrc]; the pipelines are buildLTODefaultPipeline / buildThinLTODefaultPipeline in llvm/lib/Passes/PassBuilderPipelines.cpp [LLVM-Pipelines]; llvm/docs/LinkTimeOptimization.md documents the linker interface [LLVM-LTO]. GCC: lto/lto.cc and the WPA stage (-fdump-ipa-* at link time).

Full LTO with llvm-lto2: internalize, inline, drop dead code

Reproduce (clang 23.1.2, llvm-lto2 23.1.2, llvm-dis 23.1.2; the native link uses Ubuntu's LLD 18.1.3, which only reads the native object the LTO step produced — LLVM 23 bitcode needs an LLVM 23 linker plugin, which llvm-lto2 provides here):

cat > main.c <<'EOF'
int printf(const char *, ...);
int scale(int x, int k);
int unused_helper(int x);
int main(int argc, char **argv) { printf("%d\n", scale(argc, 4)); return 0; }
EOF
cat > lib.c <<'EOF'
int scale(int x, int k) { return k == 0 ? -1 : x * k; }
int unused_helper(int x) { return x ^ 0x5a5a; }
EOF
clang-23 -O2 -flto -c main.c -o main.o && clang-23 -O2 -flto -c lib.c -o lib.o
llvm-lto2 run main.o lib.o -o out -save-temps -r main.o,main,px -r main.o,printf, -r main.o,scale, -r lib.o,scale,p -r lib.o,unused_helper,p
llvm-dis out.0.2.internalize.bc -o - | grep -E '^define'
llvm-dis out.0.4.opt.bc -o - | grep -E '^define|call|ret '
clang-23 --gcc-install-dir=/usr/lib/gcc/x86_64-linux-gnu/14 -fuse-ld=lld out.0 -o prog && ./prog a b

Output:

define dso_local noundef i32 @main(i32 noundef %0, ptr nofree noundef readnone captures(none) %1) #0 !guid !12 {
define internal i32 @scale(i32 noundef %0, i32 noundef %1) #2 !guid !13 {
define dso_local noundef i32 @main(i32 noundef %0, ptr nofree noundef readnone captures(none) %1) local_unnamed_addr #0 !guid !12 {
  %4 = tail call i32 (ptr, ...) @printf(ptr noundef nonnull dereferenceable(1) @.str, i32 noundef %3)
  ret i32 0
12

What to notice: after internalization scale is internal and unused_helper is already gone (not visible, not used: Definition 20.9.2 and dead-symbol removal); after lto<O2> scale has been inlined into main and deleted — the native object defines main only. ./prog a b prints 3 × 4 = 12.

ThinLTO¶

LLVM: llvm/lib/Analysis/ModuleSummaryAnalysis.cpp — computeFunctionSummary builds the per-function summary (instruction count, calls with hotness, refs) [LLVM-Summary]; llvm/lib/Transforms/IPO/FunctionImport.cpp — ModuleImportsManager::computeImportForModule and computeImportForFunction (Algorithm 20.9.5, with selectCallee choosing an eligible summary), FunctionImporter::importFunctions in the backend [LLVM-FunctionImport]; clang/docs/ThinLTO.md [LLVM-ThinLTO].

ThinLTO: the summary, the import decision, the backend

Reproduce (clang 23.1.2, llvm-lto2 23.1.2, llvm-dis 23.1.2; main.c and lib.c from the previous box):

clang-23 -O2 -flto=thin -c main.c -o main.o && clang-23 -O2 -flto=thin -c lib.c -o lib.o
llvm-dis main.o -o - | grep -E '^\^4 ='
llvm-lto2 run main.o lib.o -o out -save-temps -print-imports -thinlto-threads=2 -r main.o,main,px -r main.o,printf, -r main.o,scale, -r lib.o,scale,p -r lib.o,unused_helper,p
llvm-dis out.1.3.import.bc -o - | grep -E '^define|^declare'
llvm-dis out.1.4.opt.bc -o - | grep -E '^define|call '
llvm-dis out.2.2.internalize.bc -o - | grep -E '^define'

Output:

^4 = gv: (name: "main", summaries: (function: (module: ^0, flags: (linkage: external, visibility: default, notEligibleToImport: 0, live: 0, dsoLocal: 1, canAutoHide: 0, importType: definition, noRenameOnPromotion: 0), insts: 3, funcFlags: (readNone: 0, readOnly: 0, noRecurse: 0, returnDoesNotAlias: 0, noInline: 0, alwaysInline: 0, noUnwind: 1, mayThrow: 0, hasUnknownCall: 0, mustBeUnreachable: 0), calls: ((callee: ^1, tail: 1), (callee: ^2, tail: 1)), refs: (^3)))) ; guid = 15822663052811949562
main.c: Import scale from lib.c
define dso_local noundef i32 @main(i32 noundef %0, ptr nofree noundef readnone captures(none) %1) local_unnamed_addr #0 !guid !11 {
declare noundef i32 @printf(ptr noundef readonly captures(none), ...) local_unnamed_addr #1
define available_externally dso_local i32 @scale(i32 noundef %0, i32 noundef %1) local_unnamed_addr #2 !guid !12 {
define dso_local noundef i32 @main(i32 noundef %0, ptr nofree noundef readnone captures(none) %1) local_unnamed_addr #0 !guid !11 {
  %4 = tail call i32 (ptr, ...) @printf(ptr noundef nonnull dereferenceable(1) @.str, i32 noundef %3)
define dso_local i32 @scale(i32 noundef %0, i32 noundef %1) local_unnamed_addr #0 !guid !10 {

What to notice: the summary record ^4 is Definition 20.9.4 (insts: 3, the two calls, the ref to the string). The thin link imports scale into main.c's backend (-print-imports), which sees it as available_externally, inlines it and emits only main (out.1); lib.c's backend (out.2) keeps scale — it is exported — and has already dropped the dead unused_helper. The two backends ran independently (-thinlto-threads=2).

Find where LLVM does it. Open llvm/lib/Transforms/IPO/FunctionImport.cpp and find the command-line option that multiplies the import threshold by 0.7 at each level of an import chain. What is its name? (Quiz llvm-where-import-factor.)

8. Comparison¶

Technique	Power / precision	Speed (asymptotic · practical)	Output / error quality	Implementation effort	Typical use
Monolithic LTO	Every interprocedural pass sees the whole program	serial, \(O(P)\) memory · slow for large programs, no incrementality	One module: `-save-temps` stages are easy to inspect	Low for the compiler (reuses the pipeline), high for linkers	Small and medium programs, release builds, when every percent counts
ThinLTO	Whole-program decisions on summaries; transformations per module with imports	thin link on the index + parallel, cached backends · near non-LTO build times	Import and export decisions are printable (`-print-imports`, index dumps)	High (summaries, promotion, index-based WPD)	Large C/C++ code bases (Chromium, Android, Linux kernel with Clang), default LTO mode in many toolchains

Choose monolithic LTO when the program fits comfortably in memory and build time is secondary: it is the most thorough. Choose ThinLTO when the program is large or built often: nearly the same run-time benefit, parallel and incremental.

9. Assessment¶

Quiz (./course quiz 20): lto-internalize, lto-resolution (tag lto); thinlto-import-chain, llvm-where-import-factor (tag thinlto).
Drill: none: LTO's decisions are symbol resolution and the import budget — the quiz question thinlto-import-chain computes an import chain like the table of §3, and lto-internalize a resolution.
Flashcards: tags lto, thinlto.
Exercises: optional: run the comparison lab on a two-file program merged with llvm-link to see pebble-inline inline across files.

References¶

See the chapter references.

Lesson 20.9 — Whole-program compilation: monolithic LTO and ThinLTO¶

1. Problem and motivation¶

Monolithic LTO¶

ThinLTO¶

2. Definitions and algorithms¶

3. Worked example¶

Monolithic LTO¶

ThinLTO¶

4. Invariants and correctness¶

5. Complexity¶

6. Variants and refinements¶

7. In real compilers¶

Monolithic LTO¶

ThinLTO¶

8. Comparison¶

9. Assessment¶

References¶