commit 6534211c24a035a000b0924e2c8fa3c17704da07
parent 965e6ceb27de27a316c8a251786d8717317ff6e0
Author: Ryan Sepassi <rsepassi@gmail.com>
Date: Mon, 15 Jun 2026 19:20:17 -0700
doc/OPT.md: describe current O1 state, drop evolution narrative
Strip the before/after history from section 8 (the inliner's prior superlinear
cost and the fix story) and the scheduling/hint notes: state the design as it is
now -- whole-program finalize on every arch, an O(1) InlineIndex + SCC recursion
gate keeping the inliner linear, and the four inline policies -- without
recounting how it got there.
Diffstat:
| M | doc/OPT.md | | | 75 | ++++++++++++++++++++++++++++++--------------------------------------------- |
1 file changed, 30 insertions(+), 45 deletions(-)
diff --git a/doc/OPT.md b/doc/OPT.md
@@ -49,24 +49,21 @@ cache) used for streaming tiny-callee inline lookup.
### When each function is processed: finalization-time, all arches
At `opt_level >= 1` the optimizer runs in **whole-program mode**
-(`o->whole_program = (level >= 1)` in `opt_cgtarget_new`). In that mode the
-per-function callback only *registers* the recorded `CgIrFunc`; it does no
-lowering (`opt_on_func` returns early). All processing is deferred to module
-finalization (`opt_on_finalize` -> `opt_whole_module_finalize`), where a
-reachability sweep over the call/data-reloc graph computes the set of functions
-actually referenced from a root, prunes the rest, runs the cross-function
-inliner over the survivors, and only then lowers and processes each one. This is
-the single live regime today and it is identical on every architecture — the
-ARM_64-style finalize path generalized to all targets.
-
-A second regime exists in the code but is dormant: if whole-program mode were
-off, the per-function callback would lower and fully process each function
-eagerly as it is recorded (per-function streaming), leaving dead-static
-elimination to the linker. Because the recorder only exists at `level >= 1` and
-`level >= 1` always sets `whole_program`, no shipped configuration reaches the
-eager path; it is a fallback for a hypothetical non-whole-program build.
-
-Both regimes converge on the same lowering path and backend tail; they differ
+(`o->whole_program = (level >= 1)` in `opt_cgtarget_new`), identically on every
+architecture. The per-function callback only *registers* the recorded
+`CgIrFunc`; it does no lowering (`opt_on_func` returns early). All processing is
+deferred to module finalization (`opt_on_finalize` -> `opt_whole_module_finalize`),
+where a reachability sweep over the call/data-reloc graph computes the set of
+functions actually referenced from a root, prunes the rest, runs the
+cross-function inliner over the survivors, and only then lowers and processes
+each one.
+
+The per-function callback also carries a dormant eager path: with whole-program
+mode off it would lower and fully process each function as it is recorded
+(per-function streaming), leaving dead-static elimination to the linker. The
+recorder only exists at `level >= 1`, which always sets `whole_program`, so no
+configuration reaches the eager path; it is a fallback for a non-whole-program
+build. The two paths share the same lowering path and backend tail, differing
only in *when* a function is lowered, whether the cross-function inliner runs,
and whether dead local functions are dropped before lowering or left for the
linker (Section 3.1).
@@ -269,7 +266,7 @@ Everything else under §4 (`build_ssa`, `gvn`, `dse`, `licm`, `copy_prop`,
`simplify`, live-range splitting, coalescing) is O2-only and never runs.
The reachability decision lives *outside* this pipeline, in the finalize sweep
-(Section 1), and is now identical on every architecture. At module finalization
+(Section 1), identical on every architecture. At module finalization
(`opt_on_finalize`) file-scope asm blocks captured during recording are replayed
on every target, then the reachability sweep selects which functions are lowered
at all — so dead local functions/data are never lowered or emitted — and the
@@ -607,20 +604,11 @@ time, converging on the same slope as `-O0`:
| 3200 | 0.043 | 0.131 | 3.1× | 1.8× |
| 6400 | 0.062 | 0.264 | 4.3× | 2.0× |
-**This was not always so.** The whole-program inliner used to be superlinear
-(≈O(n^2.5–3): 9.6 s / 86 % of an 11.2 s `-O1` sqlite compile, exploding to 332×
-`-O0` at 1600 functions). The hot gates resolved callees and checked recursion
-with linear scans — `funcset_find`/`funcset_index` walked all functions on every
-call, and `recursive_or_scc` → `func_reaches` was a per-candidate reachability
-DFS whose every hop paid that O(n) lookup. The fix (in `pass_inline.c`) attaches
-an `InlineIndex` to the `FuncSet`: a symbol→index hash map (O(1) `funcset_find`)
-plus **per-function SCC ids computed once by iterative Tarjan**. The recursion
-gate is then a single observation — the inliner only asks "is this call
-recursive?" where a `caller→callee` edge exists, and there "callee reaches
-caller" is *exactly* "caller and callee share an SCC", so it reduces to an
-`scc[caller] == scc[callee]` compare. The verdicts are identical to the old DFS
-(the sqlite object stayed **byte-for-byte unchanged**, same 730 inlines); only
-the asymptotics changed. `opt.inline.total` dropped 9.6 s → ~0.24 s.
+No phase has a superlinear axis. The inliner stays linear in call sites because
+its hot gates are O(1) — the `InlineIndex` (Section 4) resolves callees through a
+symbol hash map and answers the recursion check with an `scc[caller] ==
+scc[callee]` compare over precomputed SCC ids — and per-function lowering plus the
+linear-scan allocator are linear in turn.
### Inline hints
@@ -634,13 +622,12 @@ frontend derives from declaration hints:
| `__attribute__((always_inline))` | ALWAYS | inline regardless of cost (recursion still blocks) |
| `__attribute__((noinline))` | NEVER | never inline |
-So a `static inline` body inlines at sizes a plain `static` one would not, and
-`always_inline` ignores the budget entirely, while `noinline` is always honored.
-(The `inline` *keyword* lives on the specifier flags, separate from the
-`__attribute__` flags; it has to be merged onto the declaration so the policy
-reaches codegen — a step that was missing, which had silently demoted every
-`static inline` to DEFAULT until corrected.) `test/opt/whole_program_inline.sh`
-guards all four policies on every arch.
+So a `static inline` body inlines at sizes a plain `static` one would not,
+`always_inline` ignores the budget entirely, and `noinline` is always honored.
+(The `inline` keyword is a declaration specifier, distinct from the
+`__attribute__` flags; the frontend merges it onto the declaration so the HINT
+policy reaches codegen.) `test/opt/whole_program_inline.sh` guards all four
+policies on every arch.
### Code quality
@@ -655,8 +642,6 @@ already smaller than tcc — the "reasonable code" half of the goal holds:
Most of the density comes from the cheap per-function transforms
(`promote_scalar_locals`, the address folds, `dead_def_elim`, `mir_combine`,
-linear-scan allocation), not from the inliner's 730 inlines — i.e. the bulk of
-the quality is bought by the ~1 s of work, not the ~9.6 s. The `-O1` object links
-and runs correctly (the ecosystem gate compiles + runs sqlite at `-O0` and `-O1`
-against clang; a spot link-and-query of the `-O1` object returns the right
-result).
+linear-scan allocation) rather than from the inliner's 730 inlines. The `-O1`
+object links and runs correctly: the ecosystem gate compiles and runs sqlite at
+`-O0` and `-O1` against clang.
