commit a66c55af01ab541d4e379ef57d1ab8becdcf26b3
parent ea7ea2bdedb2a918da1550a32e7362d9c21e3706
Author: Ryan Sepassi <rsepassi@gmail.com>
Date: Mon, 15 Jun 2026 18:35:47 -0700
driver+opt: surface O1 compile metrics via KIT_METRICS; document+profile the O1 path
Wire a process-wide KitProfiler into the AOT compile path (kit cc / kit
compile), gated by KIT_METRICS, unified with the existing heap-allocator
counters. The metrics_scope_*/metrics_count brackets already present throughout
opt_run_o1_native and the finalize sweep were previously only surfaced via
'kit run --time'; now KIT_METRICS=1 dumps every non-zero scope timer + counter
to stderr at exit for the path that produces shipped objects. Inert (single
NULL check) when KIT_METRICS is unset.
doc/OPT.md: enumerate the O1 optimization set (no-SSA framing), correct two
stale claims (whole-program mode is on for all arches at O1, so all funcs defer
to the finalize sweep; O2 is disabled because opt_cleanup has no caller, not via
o->level=1), document the KIT_METRICS surface, and add section 8 profiling the
O1 path: on sqlite, -O1 is ~70x slower than -O0 (11.2s vs 0.16s), 86% of which
is the whole-program inliner, which scales ~O(n^2.5-3) due to linear-scan
callee/SCC lookups in pass_inline.c. -O1 code is 10.6% denser than -O0 and
smaller than tcc; the density is bought by the cheap per-function passes, not
the inliner's 730 inlines.
Diffstat:
5 files changed, 244 insertions(+), 69 deletions(-)
diff --git a/doc/OPT.md b/doc/OPT.md
@@ -46,23 +46,30 @@ the resolved `NativeTarget*`, an optional dump writer, and a per-translation-
unit registry of recorded `CgIrFunc`s (with a parallel lazily-lowered-`Func`
cache) used for streaming tiny-callee inline lookup.
-### When each function is processed: streaming vs. finalization
-
-Two scheduling regimes exist, chosen by target architecture:
-
-- **Per-function streaming (x64, rv64).** As the recorder completes each
- function it fires the optimizer's per-function callback, which lowers and fully
- processes that one function immediately. Functions flow through the pipeline in
- recording order, one at a time, before the module is finalized.
-- **Finalization-time, reachability-driven (ARM_64).** The per-function callback
- registers the recorded `CgIrFunc` but does no lowering. All processing is
- deferred to module finalization, where a reachability sweep over the
- call/data-reloc graph computes the set of functions actually referenced from a
- root, prunes the rest, and only then lowers and processes the survivors.
+### 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
-only in *when* a function is lowered and whether dead local functions are dropped
-before lowering or left for the linker (Section 3.1).
+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).
### The recording/optimizing boundary
@@ -189,15 +196,17 @@ consumer choose how far down it the function travels.
### O1 native (`opt_run_o1_native`)
-This is the live optimized path for compiled output. `opt_run_o1_native`
-(`src/opt/opt.c`) is the per-function driver; how a function reaches it depends
-on the scheduling regime of Section 1. On x64/rv64 the per-function callback
-lowers the recorded function and calls `opt_run_o1_native` directly as each
-function is recorded. On ARM_64 the callback only registers the function;
-lowering and the call to `opt_run_o1_native` happen at finalization, once the
-reachability sweep has selected the function. Either way the function travels the
-same pipeline, entirely in the PReg namespace (`opt_reg_ssa == 0`) — no SSA
-construction, no value numbering. In source order:
+This is the live optimized path for compiled output, and (with O2 disabled,
+below) the *only* optimization pipeline any `-O1`/`-O2` compile runs. The
+per-function driver is the `opt_o1_native_prepare` + `opt_o1_native_finish` pair
+(`opt_run_o1_native` is the streaming wrapper around both; the finalize sweep
+calls the halves directly so the cross-function inliner can run between them).
+Every function is reached the same way today — through the finalize sweep of
+Section 1 — and travels the same pipeline entirely in the PReg namespace
+(`opt_reg_ssa == 0`): **no SSA construction, no value numbering, no
+dominance-frontier phi insertion.** That is the deliberate `-O1` design point —
+fast, reasonable code from local + linear-scan machinery, paying none of the SSA
+build/destroy cost. In source order:
```text
build_cfg -> jump_cleanup(CFG) -> build_cfg -> simplify_local
@@ -228,25 +237,57 @@ all handled here. Most stages are bracketed by an `opt_verify` /
`opt_mir_verify` checkpoint with a stage tag, and `KIT_DUMP=<tag>` dumps the
IR at the matching stage (`entry` before any pass, `pre-emit` just before emit).
-The reachability decision lives *outside* this pipeline and is per-architecture
-(Section 1). At module finalization (`opt_on_finalize`) file-scope asm blocks
-captured during recording are replayed on every target. On ARM_64, finalization
-additionally runs the reachability sweep that selects which functions are lowered
-at all, so dead local functions/data are never lowered or emitted; the survivors
-then each run the full pipeline above. On x64/rv64 every recorded function was
-already lowered and emitted during streaming, so dead-static elimination is left
-to the linker rather than performed here.
+**The O1 optimization set.** Stripping out the analyses (`build_cfg`,
+`build_loop_tree`, `live_blocks`), the verifiers, and pure lowering
+(`machinize_native`, `lower_to_mir`, `emit_native`), the transforms that actually
+improve the code are exactly these, none of which needs SSA:
+
+- **`simplify_local`** — local algebraic/addressing canonicalization (the
+ no-SSA-required cleanup, also used by the interpreter tap).
+- **Cross-function inlining** — `try_tiny_inline` per function in this pipeline,
+ plus the whole-program `opt_inline` that runs once at finalize *before* this
+ pipeline (Section 1). This is the only interprocedural transform.
+- **`addr_xform_pregs`** — fold `ADDR_OF(local)` into direct `OPK_LOCAL`
+ load/store operands and clear `FSF_ADDR_TAKEN` when every such def retires.
+- **`promote_scalar_locals`** — lift a non-escaped scalar frame slot into a
+ mutable PReg, turning its stores/loads into register copies.
+- **`addr_of_global_cse`** — hoist one `ADDR_OF(global)` compute to the entry
+ block and reuse it.
+- **`lower_loop_imm_operands` + `hoist_loop_consts`** — materialize
+ loop-invariant immediates once in the entry block instead of per iteration.
+- **`dead_def_elim_with_live`** — liveness-driven pre-RA dead-definition removal.
+- **`regalloc_locations`** — point-bitmap linear-scan allocation, **without**
+ live-range splitting or move coalescing (the O2-only quality knobs stay off).
+- **`mir_combine`** — post-RA peephole + addressing-mode synthesis (the same
+ `opt_combine` used in O2's SSA combine, here gated on physical-register
+ liveness).
+- **`mir_dce`** — post-RA dead-code elimination.
+- **`jump_cleanup` / `mir_jump_cleanup`** — unreachable-block drop, jump-chain
+ collapse, and (LAYOUT mode) block reordering for fallthrough + loop rotation.
+
+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
+(`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
+survivors each run the full pipeline above.
### O2 mid-end (`opt_cleanup` + shared lowering)
The O2 mid-end is the SSA-based optimization schedule defined in `opt_cleanup`
(`src/opt/pass_o2.c`). It is the intended mid-end architecture and is fully
-implemented, but it is not on the shipped code path: `opt_cgtarget_new` normalizes
-every requested `opt_level` to `1` (the line `o->level = 1` in `src/opt/opt.c`),
-so no compilation ever selects O2 and every `opt_level >= 1` request runs the O1
-native path.
-
-The rationale for this normalization is isolation. Keeping the O2 schedule
+implemented, but it is not on the shipped code path: **`opt_cleanup` has no
+caller.** The finalize sweep (`opt_whole_module_finalize`) always runs the O1
+native pipeline (`opt_o1_native_prepare`/`_finish`) regardless of the requested
+`opt_level`, so no compilation ever selects the SSA schedule and every
+`opt_level >= 1` request runs the O1 native path. (`-O2` therefore produces the
+same output as `-O1` today; the level is recorded on `OptImpl` but only gates
+whole-program mode, which `-O1` already enables.)
+
+The rationale for keeping it parked is isolation. Keeping the O2 schedule
defined and its passes maintained means the SSA representation and its
incremental def-use can stabilize against targeted optimizer tests independently,
without an SSA-construction or value-numbering bug affecting shipped output. The
@@ -502,5 +543,100 @@ relevant analysis.
Observability hooks: `KIT_DUMP=<tag>` dumps the optimizer IR at a named stage,
`KIT_DUMPCG=1` dumps the recorded semantic tape before lowering,
`KIT_DUMP_INTERP` dumps the interpreter-tap `Func`, and the optimizer emits
-scoped timing/count metrics (visible through `kit run --time`) for the
-frontend, each pass scope, allocation, and emit.
+scoped timing/count metrics for the frontend, each pass scope, allocation, and
+emit. Those metrics surface two ways: through `kit run --time` (the JIT path),
+and — for the AOT path that produces shipped objects (`kit cc` / `kit compile`)
+— by setting `KIT_METRICS=1` in the environment, which wires a process-wide
+`KitProfiler` into the compile and dumps every non-zero scope timer and counter
+to stderr at exit. Section 8 walks the output.
+
+## 8. Profiling the O1 path
+
+`KIT_METRICS=1` is the way to see where an `-O1` compile spends its time. Each
+`metrics_scope_*` bracket in `opt_run_o1_native` and the finalize sweep becomes
+one `<scope> <ticks> ticks (<calls> calls)` line; the counters (`opt.funcs`,
+`opt.blocks`, `opt.pregs`, the inliner refusal histogram, heap allocs, …) follow.
+Ticks are the raw host cycle counter (`cntvct_el0` on arm64 ≈ 24 MHz, so divide
+by `hw.tbfrequency` for wall-seconds); within one run the scopes are directly
+comparable. The named scopes nest — `opt.inline.total` and `opt.o1.total` are the
+two roots of the finalize sweep, and `compile.tu` covers only the frontend
+recording, *not* the finalize sweep that follows it.
+
+```
+$ KIT_METRICS=1 kit cc -O1 -c sqlite3.c --sysroot "$SDK" -o sqlite3.o
+kit metrics:
+ compile.tu 4.7M ticks (frontend: lex+pp+parse+CG recording)
+ opt.inline.total 230.6M ticks (whole-program inliner, 1 call)
+ opt.o1.total 25.7M ticks (per-function pipeline, summed over 2580 funcs)
+ opt.regalloc 11.5M ticks (biggest per-function pass)
+ ...
+ opt.funcs=2580 opt.blocks=122208 opt.tiny_inline.inlined=13 opt.inline.inlined=730
+```
+
+### Measured cost and scaling (sqlite amalgamation, arm64/Darwin)
+
+Compiling the ~263 K-line sqlite amalgamation (`-c`, release kit) the wall-clock
+split is stark — `-O1` is **~70× slower than `-O0`** (11.2 s vs 0.16 s; tcc does
+the whole file in 0.06 s):
+
+| phase (24 MHz ticks → s) | seconds | share |
+|-------------------------------------|----------:|------:|
+| frontend (`compile.tu`) | 0.20 | 2% |
+| CG→opt lowering (`cg_ir_lower`) | 0.23 | 2% |
+| **whole-program inliner** (`opt.inline.total`) | **9.61** | **86%** |
+| per-function pipeline (`opt.o1.total`) | 1.07 | 10% |
+| — of which regalloc + live-ranges | 0.64 | |
+
+The whole-program inliner dominates, and it is **superlinear**. A synthetic
+sweep (N small functions in a dense call graph, best-of-3) shows the `-O1` time
+exploding while `-O0` stays flat:
+
+| funcs | `-O0` | `-O1` | O1/O0 |
+|------:|------:|------:|------:|
+| 200 | 0.027 | 0.060 | 2.3× |
+| 400 | 0.027 | 0.240 | 8.8× |
+| 800 | 0.030 | 1.524 | 50.5× |
+| 1600 | 0.035 | 11.48 | 332× |
+
+Doubling the function count multiplies `-O1` time by ~6–8× — an exponent near
+2.5–3. The root cause is in `pass_inline.c`: the inliner runs up to four
+fixpoint iterations over the whole `FuncSet`, and its hot gates resolve callees
+and check for recursion/SCC membership with **linear scans** — `funcset_find`
+and `funcset_index` walk all functions on every call, and `recursive_or_scc` →
+`func_reaches` is a per-candidate DFS whose every hop pays that O(n) lookup. With
+2580 functions and ~24 K candidate call sites this is the textbook
+"superlinear axis = bug" trap (`doc/plan/PERF.md`). The payoff is also small:
+730 of 24 K candidates inline.
+
+By contrast the per-function pipeline is well-behaved (~1 s total, linear in
+function count); within it the linear-scan allocator + live-range construction
+are the largest line items, as expected for a no-SSA `-O1`.
+
+**Implication for the "fast O1" goal.** The non-SSA per-function pipeline already
+meets the bar — strip the inliner and `-O1` would be ~1.5 s on sqlite (linear,
+~10× `-O0`). The whole-program inliner is what breaks it. The fixes are
+self-contained and do not touch correctness: (1) index the `FuncSet` by symbol
+(hash map) so `funcset_find`/`funcset_index` are O(1); (2) memoize the
+reachability/SCC check instead of re-running `func_reaches` per candidate; and/or
+(3) reconsider whether whole-program inlining belongs at `-O1` at all versus
+behind `-O2`/`-flto`, leaving `-O1` with only the cheap streaming `try_tiny_inline`
+(0.28 s on sqlite). Any of these restores the linear, "fast" `-O1` design point.
+
+### Code quality
+
+`-O1` produces *denser* code than `-O0` despite doing no SSA optimization, and is
+already smaller than tcc — the "reasonable code" half of the goal holds:
+
+| metric (sqlite3.o) | `-O0` | `-O1` | Δ vs O0 |
+|---------------------------|--------:|--------:|--------:|
+| `__TEXT` (code) | 1.41 MB | 1.26 MB | −10.6% |
+| total object | 1.75 MB | 1.62 MB | −7.3% |
+| (tcc total object, ref) | — | 2.11 MB | — |
+
+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).
diff --git a/driver/env/common.c b/driver/env/common.c
@@ -47,47 +47,69 @@ static void driver_heap_metrics_define(KitProfiler* pr) {
"heap.frees");
}
-/* Process-wide heap metrics, opt-in via KIT_METRICS. The heap is global, so its
- * stats are too; this stays NULL/inert unless asked. When an external profiler
- * is already attached (e.g. a future `kit run --metrics` pointing KitHeap.user
- * at its per-run profiler), we leave it alone and merge into that instead. */
-static KitProfiler* g_heap_metrics_prof;
-static int g_heap_metrics_inited;
-
-static void driver_heap_metrics_dump(void) {
- KitProfiler* pr = g_heap_metrics_prof;
+/* Process-wide compile metrics, opt-in via KIT_METRICS. One KitProfiler backs
+ * both the heap-allocator counters (wired through KitHeap.user, below) and the
+ * libkit scope timers/counters (wired through DriverEnv.profiler ->
+ * KitContext.profiler, so the metrics_scope and metrics_count calls the
+ * optimizer, linker, and JIT already emit accumulate here). The heap is global,
+ * so its
+ * stats are too; this stays NULL/inert unless KIT_METRICS asks for it. */
+static KitProfiler* g_metrics_prof;
+static int g_metrics_inited;
+
+static void driver_metrics_dump(void) {
+ KitProfiler* pr = g_metrics_prof;
uint32_t id;
if (!pr) return;
- fprintf(stderr, "kit heap metrics:\n");
- for (id = KIT_PROFILE_COUNTER_EXTERNAL_FIRST; id <= (uint32_t)HEAP_C_FREES;
- ++id) {
- const char* name = kit_profiler_counter_name(pr, (KitProfileCounter)id);
- fprintf(stderr, " %s=%llu\n", name ? name : "heap.?",
- (unsigned long long)kit_profiler_counter_value(
- pr, (KitProfileCounter)id));
+ fprintf(stderr, "kit metrics:\n");
+ /* Scope timers first (raw host cycle-counter ticks + call count), in id order
+ * so the compile pipeline reads top-to-bottom. Names resolve through the
+ * kit-core scope table; unnamed scopes are skipped silently. */
+ for (id = 1; id < KIT_PROFILE_ID_COUNT; ++id) {
+ uint64_t count = kit_profiler_scope_count(pr, (KitProfileScope)id);
+ uint64_t ticks = kit_profiler_scope_ticks(pr, (KitProfileScope)id);
+ const char* name;
+ if (!count) continue;
+ name = kit_profiler_scope_name(pr, (KitProfileScope)id);
+ if (!name) continue;
+ fprintf(stderr, " %s %llu ticks (%llu calls)\n", name,
+ (unsigned long long)ticks, (unsigned long long)count);
+ }
+ /* Then every non-zero counter (heap.* in the external range, opt.* and link.*
+ * in the kit range). */
+ for (id = 1; id < KIT_PROFILE_ID_COUNT; ++id) {
+ uint64_t value = kit_profiler_counter_value(pr, (KitProfileCounter)id);
+ const char* name;
+ if (!value) continue;
+ name = kit_profiler_counter_name(pr, (KitProfileCounter)id);
+ if (!name) continue;
+ fprintf(stderr, " %s=%llu\n", name, (unsigned long long)value);
}
}
-static void driver_heap_metrics_maybe_begin(KitHeap* h) {
+KitProfiler* driver_metrics_profiler(void) {
const char* e;
- if (g_heap_metrics_inited) return;
- g_heap_metrics_inited = 1;
- if (!h || h->user) return; /* already wired to an external profiler */
+ if (g_metrics_inited) return g_metrics_prof;
+ g_metrics_inited = 1;
e = getenv("KIT_METRICS");
- if (!(e && e[0] && e[0] != '0')) return;
+ if (!(e && e[0] && e[0] != '0')) return NULL;
/* Raw libc alloc (not through the vtable) so the profiler storage itself is
* not counted and there is no reentrancy. */
- g_heap_metrics_prof = (KitProfiler*)calloc(1, sizeof(*g_heap_metrics_prof));
- if (!g_heap_metrics_prof) return;
- driver_heap_metrics_define(g_heap_metrics_prof);
- h->user = g_heap_metrics_prof;
- atexit(driver_heap_metrics_dump);
+ g_metrics_prof = (KitProfiler*)calloc(1, sizeof(*g_metrics_prof));
+ if (!g_metrics_prof) return NULL;
+ driver_heap_metrics_define(g_metrics_prof);
+ /* Wire the heap counter sink unless something already claimed it. */
+ if (!g_heap_libc.user) g_heap_libc.user = g_metrics_prof;
+ atexit(driver_metrics_dump);
+ return g_metrics_prof;
}
static void* heap_libc_alloc(KitHeap* h, size_t size, size_t align) {
KitProfiler* pr;
(void)align; /* malloc satisfies all max_align_t alignments */
- if (!g_heap_metrics_inited) driver_heap_metrics_maybe_begin(h);
+ /* Lazily arm metrics for any allocation that precedes driver_env_init (the
+ * usual arming site); idempotent and a single branch once inited. */
+ if (!g_metrics_inited) (void)driver_metrics_profiler();
pr = h ? (KitProfiler*)h->user : NULL;
if (pr && size) {
kit_profiler_count(pr, (KitProfileCounter)HEAP_C_ALLOCS, 1);
diff --git a/driver/env/env_internal.h b/driver/env/env_internal.h
@@ -33,6 +33,17 @@
extern KitHeap g_heap_libc;
extern KitDiagSink g_diag_stderr;
+/* ---- compile metrics (common.c) ----------------------------------------
+ * Process-wide KitProfiler storage, opt-in via the KIT_METRICS env var. The
+ * first call (from driver_env_init, before any compile runs) lazily allocates
+ * the profiler, wires the heap vtable's counter sink to it, and registers an
+ * atexit dump of every non-zero scope timer / counter. Returns NULL when
+ * KIT_METRICS is unset, so each host's driver_env_init can assign the result
+ * straight to DriverEnv.profiler (and thus KitContext.profiler) unconditionally
+ * -- libkit's metrics_scope and metrics_count hot path is a single NULL check
+ * when profiling is off. Idempotent: repeated calls return the same pointer. */
+KitProfiler* driver_metrics_profiler(void);
+
/* ---- icache (icache_<arch>.c) ------------------------------------------
* Arch-only, OS-neutral. The POSIX dbg path delegates here from
* os_dbg_flush_icache; Windows uses FlushInstructionCache directly and
diff --git a/driver/env/posix.c b/driver/env/posix.c
@@ -1456,7 +1456,10 @@ void driver_env_init(DriverEnv* e) {
e->execmem = &g_execmem_posix;
e->dbg_os = &g_dbg_os_posix;
- e->profiler = NULL;
+ /* Opt-in compile metrics (KIT_METRICS): one process-wide profiler backs both
+ * the heap counters and libkit's scope timers. NULL when unset -- the metrics
+ * hot path is then a single pointer check. */
+ e->profiler = driver_metrics_profiler();
{
const char* xdg = getenv("XDG_CACHE_HOME");
diff --git a/driver/env/windows.c b/driver/env/windows.c
@@ -2077,7 +2077,10 @@ void driver_env_init(DriverEnv* e) {
e->execmem = &g_execmem_win;
e->dbg_os = &g_dbg_os_win;
- e->profiler = NULL;
+ /* Opt-in compile metrics (KIT_METRICS): one process-wide profiler backs both
+ * the heap counters and libkit's scope timers. NULL when unset -- the metrics
+ * hot path is then a single pointer check. */
+ e->profiler = driver_metrics_profiler();
{
/* XDG_CACHE_HOME wins if set (cross-platform tooling convention),
