commit ecbd00dc995aefbe600af5bfd5494412f7a59245
parent c80d7eb9de3126085252647b5738adf8977cc63b
Author: Ryan Sepassi <rsepassi@gmail.com>
Date: Sat, 13 Jun 2026 01:35:40 -0700
perf(cg): -O0 transient liveness + lazy dup (copy-on-write)
Foundation for value-stack-driven copy/slot coalescing at -O0. The value stack is
a precise liveness oracle: a transient (api_alloc_temp_local) local is dead iff no
live stack entry references it. KitCg now keeps a per-handle live-reference count
(local_refs[], maintained at api_push/api_pop, with pointer-range-guarded
reseat helpers for in-place operand changes) stamped by a per-function generation
(local_temp_gen[] vs func_gen, so stale entries need no O(cap) clear). api_temp_dead
uses the count only as a fast reject and CONFIRMS with a bounded stack scan
(api_temp_scan_refs) when it reads 0 — so any reseat-accounting gap costs at most a
missed optimization, never a miscompile. The scan is also the bounded-scan A/B
baseline; KIT_NO_COALESCE disables the whole thing for measurement.
First consumer — lazy dup: kit_cg_dup of an already-materialized owned temp now
pushes a second reference to the same write-once temp instead of copying it into a
fresh one. Both entries only read the shared temp; the refcount (now 2) keeps the
upcoming finer-reclaim/adoption from recycling it while shared, and it is freed
once both references are gone (Fix A at the statement boundary). Eliminates the
common assignment-result dup whose value is stored once and discarded
(`a=b;`, `x=y=z`, `d=(arr[i]=v)`).
sqlite3.c -c, arm64-macOS: 565,388 -> 543,470 insns (-3.9%); reg-reg mov
60,684 -> 45,770 (-24.6%); object 2.66 -> 2.57MB. Running total this session:
831,078 -> 543,470 (-34.6%), ~1.59x tcc.
test-toy 1392/0, test-parse-ok 3920/0 (O0/O1 x D/R/J/E), test-parse-err 129/0,
test-smoke-x64/rv64 3/0; sqlite shell links+runs (84|2); s.a++ + ++s.b == 3 and
chained/nested assignment cases verified.
Diffstat:
4 files changed, 185 insertions(+), 1 deletion(-)
diff --git a/src/cg/internal.h b/src/cg/internal.h
@@ -205,6 +205,23 @@ struct KitCg {
u32 sp;
u32 cap;
+ /* -O0 transient liveness. local_refs[h] = number of live value-stack entries
+ * that reference CGLocal handle h (maintained at api_push/api_pop, plus a
+ * pointer-range-guarded reseat at in-place operand changes). local_is_temp[h]
+ * marks an api_alloc_temp_local transient — the only locals the single-pass
+ * backend recycles (Fix A) or coalesces. The count is used only as a
+ * fast-reject prefilter: a transient is treated as dead solely when the count
+ * reads 0 AND a confirming stack scan (api_temp_dead) agrees, so any reseat
+ * gap costs at most a missed optimization, never a miscompile. Sized on demand
+ * by handle; cleared per function. NULL/0 until first use. */
+ u32* local_refs; /* live value-stack reference count per handle */
+ u32* local_temp_gen; /* == func_gen iff the handle is this function's temp */
+ u32 local_track_cap;
+ u32 func_gen; /* bumped each function; stamps temps without O(cap) clears */
+ u8 coalesce; /* -O0 copy/dup coalescing + finer reclaim enabled */
+ u8 coalesce_known; /* coalesce resolved from env (once) */
+ u8 coalesce_pad[2];
+
/* Off-node pool for SV_CMP / SV_ARITH delayed payloads. The arena is reset
* per function (api_delayed_reset at func_begin, where the stack is also
* dropped); delayed_free is an intrusive freelist that reuses payloads within
@@ -509,6 +526,18 @@ void api_ensure_local(KitCg* g, ApiSValue* sv);
Operand api_force_local(KitCg* g, ApiSValue* v, KitCgTypeId ty);
Operand api_force_local_unless_imm(KitCg* g, ApiSValue* v, KitCgTypeId ty);
void api_release(KitCg* g, ApiSValue* sv);
+
+/* -O0 transient liveness (see KitCg.local_refs). api_coalesce_on returns whether
+ * the copy/dup coalescing + finer-reclaim mechanisms are enabled this run.
+ * api_temp_dead reports whether transient `local` is provably dead right now (no
+ * live value-stack entry references it): count==0 confirmed by a stack scan.
+ * api_reseat_{begin,end} bracket an in-place change to a stack entry's operand so
+ * its references are re-accounted. */
+int api_coalesce_on(KitCg* g);
+int api_temp_dead(KitCg* g, CGLocal local);
+void api_reseat_begin(KitCg* g, const ApiSValue* sv);
+void api_reseat_end(KitCg* g, const ApiSValue* sv);
+
BinOp api_map_int_binop(KitCgIntBinOp op);
BinOp api_map_fp_binop(KitCgFpBinOp op);
UnOp api_map_int_unop(KitCgIntUnOp op);
diff --git a/src/cg/memory.c b/src/cg/memory.c
@@ -577,6 +577,19 @@ void kit_cg_dup(KitCg* g) {
api_push(g, v);
return;
}
+ if (api_coalesce_on(g)) {
+ /* Lazy dup: push a second reference to the owned temp instead of copying it
+ * into a fresh one. Both entries only ever read the write-once value temp,
+ * so they can share it; the value-stack refcount (now 2) keeps finer-reclaim
+ * and copy-adoption from recycling the temp while it is still shared, and it
+ * is freed once both references are gone (Fix A at the statement boundary, or
+ * finer reclaim when the count returns to 0). Eliminates the common
+ * assignment-result dup whose value is stored once and then discarded. */
+ dup = v;
+ dup.pinned = 0;
+ api_push(g, dup);
+ return;
+ }
top->pinned = 1;
ty = api_owned_local_type(g, &v);
r = api_alloc_temp_local(g, ty);
diff --git a/src/cg/session.c b/src/cg/session.c
@@ -411,6 +411,9 @@ void kit_cg_func_begin_attrs(KitCg* g, KitCgSym cg_sym,
g->nlocals = 0;
g->const_head = KIT_CG_LOCAL_NONE;
g->sp = 0;
+ /* New generation: stale local_temp_gen entries from the previous function are
+ * now != func_gen, so its temp handles read as non-temp without any clear. */
+ g->func_gen++;
/* Drop the previous function's delayed cmp/arith payloads along with its
* value stack — neither outlives the function. */
api_delayed_reset(g);
diff --git a/src/cg/value.c b/src/cg/value.c
@@ -154,6 +154,10 @@ void api_stack_grow(KitCg* g, u32 want) {
g->cap = cap;
}
+/* -O0 transient liveness bookkeeping; defined below, used by push/pop/alloc. */
+static void api_sv_adjust_refs(KitCg* g, const ApiSValue* sv, int delta);
+static void api_track_temp(KitCg* g, CGLocal local);
+
void api_push(KitCg* g, ApiSValue v) {
KitCgTypeId ty = api_sv_type(&v);
/* One memoized fetch gives both the aggregate-place property and the
@@ -177,13 +181,17 @@ void api_push(KitCg* g, ApiSValue v) {
v.bitfield.wide_kind = cls & API_TYPE_CLASS_WIDE_MASK;
api_stack_grow(g, g->sp + 1);
g->stack[g->sp++] = v;
+ api_sv_adjust_refs(g, &v, +1);
}
ApiSValue api_pop(KitCg* g) {
+ ApiSValue r;
if (g->sp == 0) {
compiler_panic(g->c, g->cur_loc, "KitCg: stack underflow");
}
- return g->stack[--g->sp];
+ r = g->stack[--g->sp];
+ api_sv_adjust_refs(g, &r, -1);
+ return r;
}
/* ---- local helpers ---- */
@@ -237,6 +245,7 @@ CGLocal api_alloc_temp_local(KitCg* g, KitCgTypeId ty) {
compiler_panic(g->c, g->cur_loc,
"KitCg: target failed to allocate temporary local");
}
+ api_track_temp(g, local); /* register for -O0 transient liveness */
return local;
}
@@ -435,6 +444,136 @@ void api_release(KitCg* g, ApiSValue* sv) {
sv->res = RES_INHERENT;
}
+/* ---- -O0 transient liveness (refcount + confirming scan) ---- */
+
+int api_coalesce_on(KitCg* g) {
+ if (!g->coalesce_known) {
+ /* Default on; KIT_NO_COALESCE=1 disables for A/B measurement. */
+ g->coalesce = kit_debug_getenv("KIT_NO_COALESCE") ? 0u : 1u;
+ g->coalesce_known = 1u;
+ }
+ return g->coalesce;
+}
+
+/* Mark `local` (a fresh api_alloc_temp_local handle) as this function's temp and
+ * zero its live-reference count. */
+static void api_track_temp(KitCg* g, CGLocal local) {
+ Heap* h = g->c->ctx->heap;
+ u32 idx = (u32)local;
+ if (idx >= g->local_track_cap) {
+ u32 cap = g->local_track_cap ? g->local_track_cap : 64u;
+ u32* nr;
+ u32* ng;
+ while (cap <= idx) cap *= 2u;
+ nr = (u32*)h->alloc(h, sizeof(u32) * cap, _Alignof(u32));
+ ng = (u32*)h->alloc(h, sizeof(u32) * cap, _Alignof(u32));
+ memset(nr, 0, sizeof(u32) * cap);
+ memset(ng, 0, sizeof(u32) * cap);
+ if (g->local_refs) {
+ memcpy(nr, g->local_refs, sizeof(u32) * g->local_track_cap);
+ memcpy(ng, g->local_temp_gen, sizeof(u32) * g->local_track_cap);
+ h->free(h, g->local_refs, sizeof(u32) * g->local_track_cap);
+ h->free(h, g->local_temp_gen, sizeof(u32) * g->local_track_cap);
+ }
+ g->local_refs = nr;
+ g->local_temp_gen = ng;
+ g->local_track_cap = cap;
+ }
+ g->local_temp_gen[idx] = g->func_gen;
+ g->local_refs[idx] = 0u;
+}
+
+static int api_handle_is_temp(KitCg* g, CGLocal local) {
+ u32 idx = (u32)local;
+ return idx < g->local_track_cap && g->local_temp_gen[idx] == g->func_gen;
+}
+
+/* Visit each temp local an operand references (LOCAL, or INDIRECT base/index),
+ * adjusting its live-reference count by `delta` (clamped at 0 on decrement). */
+static void api_op_adjust_refs(KitCg* g, const Operand* op, int delta) {
+ CGLocal a = CG_LOCAL_NONE, b = CG_LOCAL_NONE;
+ if (op->kind == OPK_LOCAL) {
+ a = op->v.local;
+ } else if (op->kind == OPK_INDIRECT) {
+ a = op->v.ind.base;
+ b = op->v.ind.index;
+ }
+ if (a != CG_LOCAL_NONE && api_handle_is_temp(g, a)) {
+ if (delta > 0)
+ g->local_refs[a]++;
+ else if (g->local_refs[a])
+ g->local_refs[a]--;
+ }
+ if (b != CG_LOCAL_NONE && api_handle_is_temp(g, b)) {
+ if (delta > 0)
+ g->local_refs[b]++;
+ else if (g->local_refs[b])
+ g->local_refs[b]--;
+ }
+}
+
+/* All temp locals an SValue references: its operand plus, for a delayed
+ * cmp/arith, its pending operands. */
+static void api_sv_adjust_refs(KitCg* g, const ApiSValue* sv, int delta) {
+ if (sv->kind == SV_OPERAND) {
+ api_op_adjust_refs(g, &sv->op, delta);
+ } else if (sv->delayed) {
+ if (sv->kind == SV_CMP) {
+ api_op_adjust_refs(g, &sv->delayed->cmp.a, delta);
+ api_op_adjust_refs(g, &sv->delayed->cmp.b, delta);
+ } else if (sv->kind == SV_ARITH) {
+ api_op_adjust_refs(g, &sv->delayed->arith.a, delta);
+ if (sv->delayed->arith.kind == API_DELAYED_BINOP)
+ api_op_adjust_refs(g, &sv->delayed->arith.b, delta);
+ }
+ }
+}
+
+void api_reseat_begin(KitCg* g, const ApiSValue* sv) {
+ if (sv >= g->stack && sv < g->stack + g->sp) api_sv_adjust_refs(g, sv, -1);
+}
+void api_reseat_end(KitCg* g, const ApiSValue* sv) {
+ if (sv >= g->stack && sv < g->stack + g->sp) api_sv_adjust_refs(g, sv, +1);
+}
+
+/* Ground-truth scan: how many live value-stack entries reference temp `local`.
+ * The arbiter when the incremental count reads 0 (so a reseat-accounting gap can
+ * only cost a missed optimization, never a miscompile). */
+static u32 api_temp_scan_refs(KitCg* g, CGLocal local) {
+ u32 n = 0;
+ for (u32 i = 0; i < g->sp; ++i) {
+ const ApiSValue* sv = &g->stack[i];
+ const Operand* op = &sv->op;
+ if (sv->kind == SV_OPERAND) {
+ if (op->kind == OPK_LOCAL && op->v.local == local) n++;
+ else if (op->kind == OPK_INDIRECT &&
+ (op->v.ind.base == local || op->v.ind.index == local))
+ n++;
+ } else if (sv->delayed) {
+ const ApiDelayed* d = sv->delayed;
+ const Operand* a = sv->kind == SV_CMP ? &d->cmp.a : &d->arith.a;
+ const Operand* b = sv->kind == SV_CMP ? &d->cmp.b : &d->arith.b;
+ int has_b = sv->kind == SV_CMP || d->arith.kind == API_DELAYED_BINOP;
+ if ((a->kind == OPK_LOCAL && a->v.local == local) ||
+ (a->kind == OPK_INDIRECT &&
+ (a->v.ind.base == local || a->v.ind.index == local)))
+ n++;
+ if (has_b &&
+ ((b->kind == OPK_LOCAL && b->v.local == local) ||
+ (b->kind == OPK_INDIRECT &&
+ (b->v.ind.base == local || b->v.ind.index == local))))
+ n++;
+ }
+ }
+ return n;
+}
+
+int api_temp_dead(KitCg* g, CGLocal local) {
+ if (local == CG_LOCAL_NONE || !api_handle_is_temp(g, local)) return 0;
+ if (g->local_refs[(u32)local] > 0) return 0; /* fast reject: still referenced */
+ return api_temp_scan_refs(g, local) == 0; /* confirm before acting */
+}
+
/* ---- BinOp / UnOp / CmpOp mapping ---- */
BinOp api_map_int_binop(KitCgIntBinOp op) {
