Use Link-Time Optimization (LTO) and Measure Effects

Topic Overview

Whole-Program Visibility at Link

Link-Time Optimization (LTO) stores LLVM bitcode or GCC GIMPLE in .o files and runs optimization when linking. Cross-module inlining and devirtualization become possible. Chrome and Rust release builds rely on thin LTO for large link times.

Enabling LTO

Clang: -flto=thin at compile and link. GCC: -flto plus use gcc driver for the final link. Static libraries must be built with LTO objects too.

bashCopy
Loading…

• Link step memory spikes on huge projects; thin LTO mitigates
• Debug symbols need -g at LTO link for usable stacks
• Compare nm symbol counts before/after cross-module inline
• PGO profiles still apply with LTO

Working Through the Exercise

Keep the relevant documentation open while you implement. When your output disagrees with the reference, trace one failing case by hand before changing random lines.

• Trace first: walk one failing input step by step
• Read the manual: skim the official doc for the mechanism named in this task
• Compare baselines: save measurements from the prior step so speedups are honest

Why for this exercise

You will build a two-file project with and without LTO and measure call overhead across translation units. This exercise asks you to show one function inlined only in the LTO build.

Your Task

Without link-time optimisation, each .c file is compiled on its own. The compiler can inline only functions whose bodies are in the same file, and it must keep every non-static function because some other object file might call it. With LTO, the whole program is optimised at once, so small functions inline across files, and anything main can no longer reach is deleted. Model both builds and compare code size and the number of call instructions left.

Input

cCopy
Loading…

Rules

• Name resolution. A call resolves to a static function of the same unit if one exists, otherwise to the non-static function with that name. An unresolved name prints undefined reference to NAME (from CALLER) and link failed, and so does a missing non-static main (undefined reference to main).
• Inlining.
  1. Process callees before callers (a function whose calls lead back to itself is never inlined along that edge).
  2. A call is inlined if the callee's current size is <= the threshold and, without LTO, the callee is in the same unit.
  3. Inlining replaces a 5-byte call with the callee's current body: caller += callee - 5.
• Keeping functions.
  • Roots are every non-static function (without LTO) or main alone (with LTO).
  • A function is kept if a remaining call instruction in a kept function targets it. The body of an inlined callee counts as part of the caller, including the calls it still makes.
  • Everything else is removed.

Output

cCopy
Loading…

Each kept function's call count includes the calls inside bodies inlined into it. Kept and removed functions are listed in definition order (removed: none if nothing was removed). A func before any unit prints func NAME: no unit.

Example

Input:

cCopy
Loading…

Output:

cCopy
Loading…

Requirements

1. Inline bottom-up, so a caller sees its callees' sizes after their own inlining.
2. Compute what is kept by reachability over the call instructions that remain after inlining. Do not use a list of names.

Hidden tests cover a static helper inlined within its own file, an inlined body that still calls a large function, recursion (never inlined), a raised and a zero threshold, an unreachable exported function (only LTO removes it), same-named static functions in two units, and undefined references.