commit 8e89fac12c3e6ef815053b98ab80f1d5420baabe
parent 70031256ffce48755c4e8aa0b17a3d4c110fa107
Author: Ryan Sepassi <rsepassi@gmail.com>
Date: Sat, 13 Jun 2026 21:28:07 -0700
doc(plan): FRONTEND-SHAPE.md — sequenced campaign to tcc frontend shape (§4.3)
Audit finding: §4.3 is mostly already landed. Pillar 2 (symbol cache) is done
(BindingTab/KIT_SYMTAB makes scope_lookup O(1)); Pillar 1 (shared token slot) is
~70% (one Tok, out-pointer relay, no-## pointer-replay); Pillar 3 (thin SValue)
is forked (two parallel value stacks kept in lockstep). Plan sequences the real
remaining work into 5 independently-landable, byte-identical-gated tiers.
Diffstat:
1 file changed, 297 insertions(+), 0 deletions(-)
diff --git a/doc/plan/FRONTEND-SHAPE.md b/doc/plan/FRONTEND-SHAPE.md
@@ -0,0 +1,297 @@
+# Frontend shape: closing the gap to tcc's frontend (PERF.md §4.3)
+
+**Goal.** Reach tcc's *frontend shape* — the structural end-state PERF.md §4.3
+names: a shared mutable token slot fed by both scanner and macro replayer,
+identifiers resolved through symbol pointers cached on the interned token, and a
+thin `SValue[]` the parser drives by calling emit directly. The `CgTarget` →
+`NativeTarget` vtable polymorphism **stays** (the two indirect calls per
+primitive are the price of the seven-backend modularity, per §4.3); this plan is
+about the *front half and the value-stack seam*, not the backend vtable collapse.
+
+This doc is the sequenced campaign. It is grounded in a code audit (2026-06-13)
+whose headline finding reframes the work: **most of §4.3 is already landed.** The
+"large refactor" is, in reality, one finished pillar, one ~70%-done pillar, and
+one genuine-but-bounded structural change. Each tier below is independently
+landable and individually gated.
+
+---
+
+## 0. Verified current state (what §4.3 already bought)
+
+### Pillar 2 — "symbol pointers cached on the interned token" — **DONE**
+
+PERF.md §4.1 #1 (the "highest-value front-half brick," describing `scope_lookup`
+as "an N-scope chain walk per identifier") is **stale**. Resolution is already
+one array load:
+
+```c
+// lang/c/parse/parse.c:388
+SymEntry* scope_lookup(Parser* p, Sym name) {
+ return name ? BindingTab_get(&p->bind, name) : NULL; // O(1)
+}
+```
+
+`BindingTab` (`KIT_SYMTAB_DEFINE`, a Sym-indexed dense array;
+`parse_priv.h:360`) is the kit-native form of tcc's `TokenSym.sym_identifier`.
+`SymEntry.shadowed` (`parse.c:363`) is the push/restore stack; `scope_pop`
+(`parse.c:308-321`) unwinds it. `kit/support/symtab.h`'s own header comment
+explains why kit's *per-consumer* table is **better** than tcc's field-on-the-
+token: the pp keeps `Sym→Macro*`, the parser keeps `Sym→SymEntry*`, with no
+shared per-symbol struct and no global state — the module boundary stays intact.
+**Nothing structural remains here.** (Action: correct §4.1 #1 / §4.3 — see Tier 0.)
+
+### Pillar 1 — "shared mutable token slot fed by scanner + replayer" — **~70%**
+
+- One 28-byte `Tok` (`lang/cpp/lex/lex.h:67`), **no per-stage variants**.
+- `src_next_raw_into(Pp*, Tok* out, …)` already writes `lex_next`'s sret straight
+ into the caller's slot (`pp.c:72`, see the out-pointer rationale comment at
+ `pp.c:61-71`).
+- No-`##` object macros already replay **by pointer** — `push_buf_replay`
+ (`pp.c:193`) const-casts the immutable body; the two read sites load by value
+ and never write back (`pp.c:187-192`).
+
+Three copy-sources remain (the Tier 1 / Tier 2 work):
+1. **Newlines** (~51 % of lexer outputs) are materialized as `TOK_NEWLINE` then
+ drained (`pp_expand.c:1040`). → Tier 1.
+2. **Function-macro args** still cost 3–4 copies/token (raw-collect →
+ pre-expand → phase-1 subst → phase-2 paste → read). → Tier 1.
+3. The **parser pulls tokens by value** into `p->cur`/`p->next`/`p->pending`
+ (`fetch_tok`/`advance`/`peek1`, `parse.c:165-210`). → Tier 2.
+
+### Pillar 3 — "thin SValue the parser drives by calling emit" — **partial / forked**
+
+`ApiSValue` is already 40 B (`src/cg/internal.h:99`, enforced < 64). The parser
+drives codegen inline (no AST). **But there are two parallel value stacks**, kept
+in lockstep:
+
+- Frontend: `PcgSlot cg_slot_stack[]` (`cg_adapter.h:73`, `parse_priv.h:250`) —
+ `{const Type*, PcgLvAux, KitCgTypeId cg_id, u8 flags}`.
+- CG API: `ApiSValue stack[]` inside `KitCg` (`internal.h:189`).
+
+tcc has *one* `SValue[]`. Unifying them is the Tier 3 work, using the user's
+design: **the CG API exposes an opaque per-entry aux slot the frontend tags**, so
+the language-neutral seam is preserved while the parallel stack disappears.
+
+> Note: `doc/FRONTENDS.md` is also stale here — it still describes three parallel
+> arrays `cg_type_stack` / `cg_value_flags` / `cg_lv_aux`; those were merged into
+> the single `PcgSlot` array. Fix in Tier 0.
+
+---
+
+## Tier 0 — re-baseline (prerequisite, ~½ day)
+
+Cheap, do first; everything else re-ranks off it.
+
+1. **Re-profile** per PERF.md §3 (`scripts/perf_callgrind.sh run shape-base`) and
+ `make perf-golden` for the byte-identity gate snapshot. Record the fresh
+ self-`Ir` table; the §2 numbers predate recent landings.
+2. **Correct the stale docs** (no code): PERF.md §4.1 #1 (mark symbol-binding
+ cache *landed*, point at `BindingTab`), §4.3 (note Pillar 2 done, Pillar 1
+ ~70 %), and `doc/FRONTENDS.md` §"Parser" (the `PcgSlot` single stack, not the
+ three-array description).
+
+Gate: docs only + golden snapshot exists. No behavior change.
+
+---
+
+## Tier 1 — finish the relay (seam-preserving copy elimination)
+
+Two levers, **byte-identical-gated** (`make perf-golden` → edit → `make perf-gate`,
+plus the line-splice battery for any lexer touch, §5). Order 1B before 1A (1B is
+lower-risk and de-risks the gate harness; 1A is the riskiest lever in the plan).
+
+### 1B — cut function-macro argument copies
+
+**Obstacle.** A function-macro invocation copies each argument token 3–4×:
+raw-collect (`read_invocation_args`, `pp_expand.c:566/586` `tv_push`), per-arg
+`memcpy` into a pre-expansion slice (`preexpand_args`, `pp_expand.c:648`),
+pre-expand output (`expand_arg_to_eof`, `pp_expand.c:475`), then phase-1 subst
+(`pp_expand.c:790…`) and phase-2 paste (`pp_expand.c:866`).
+
+**Change (incremental, each independently gated):**
+- Extend the no-`##` pointer-replay idea (already used for object bodies) to the
+ *substituted body*: when `m->has_paste == 0` **and** no argument needs both raw
+ and pre-expanded forms, build the result by **pushing argument slices by
+ reference** rather than copying each token into one flat buffer. The
+ `has_paste` flag is already set at definition time (`pp_expand.c:264`), so the
+ branch is free.
+- Where a copy is unavoidable (paste/stringize present), collapse the
+ phase-1→phase-2 hand-off so a token is written once, not staged then re-walked
+ (today phase 2 re-copies every non-`##` token, `pp_expand.c:870`).
+- The pre-expansion `memcpy` (`pp_expand.c:648`) exists to give
+ `expand_arg_to_eof` a stable buffer; check whether it can read the raw range
+ in place (the raw buffer outlives the pre-expand for that arg).
+
+**Gate:** byte-identical on the full pp corpus + sqlite `-E`/`-c`. Macro-heavy
+inputs (`#define` batteries, nested/variadic, `##`/`#`) must be in the diff set.
+**Payoff:** bounded by macro density; real on sqlite (declaration/macro-heavy).
+`pp_pull_into` 4.4 % + the arg machinery feed it. **Risk:** medium — argument
+lifetime + hideset (`s->hs`/`hs_uniform`) must ride along with by-reference
+slices; the Prosser rescan correctness is the thing to protect.
+
+### 1A — stop materializing non-directive newlines on the cc path
+
+**Obstacle.** The lexer emits a `TOK_NEWLINE` per physical line
+(`lex.c:704-717`) so the pp can (a) delimit directive lines (`collect_line`,
+`pp_directive.c:36-48`; the `do…while(kind!=TOK_NEWLINE)` scans,
+`pp_directive.c:533`) and (b) recognize `#`-at-BOL. But **`TF_AT_BOL` already
+carries the same signal** on the next real token (`pp.c:124-125`,
+`pp_directive.c:553`). The parser never sees newlines (drained, `pp_expand.c:1040`).
+So the newline token is redundant for cc *except* as a line-end sentinel inside
+directive parsing, and for `-E` (which reconstructs line structure,
+`pp_emit_text`, `pp.c:289-316`).
+
+**Change.** Make `TOK_NEWLINE` an `-E`-only product:
+- Add a lexer mode flag (cc vs `-E`). In cc mode, **do not emit `TOK_NEWLINE`**;
+ instead the first token of each line is tagged `TF_AT_BOL` (already happens) and
+ the lexer threads "saw a line boundary" into that flag.
+- Rewrite directive line-termination to **"read until the next `TF_AT_BOL`
+ token (or `TOK_EOF`)"** instead of "until `TOK_NEWLINE`." The `#if`/`#define`/
+ `#include`/`#line`/`#pragma`/`#error`/`#embed` collectors in `pp_directive.c`
+ all funnel through `collect_line`; convert that one helper and audit the few
+ direct `TOK_NEWLINE` checks (`pp_directive.c:533/1441`, `pp.c:243`,
+ `pp_expand.c:424/470/524` — macro-arg newline-as-whitespace, which simply
+ disappears in cc mode).
+- Keep `-E` exactly as today (emit newlines): the path already splits on
+ `skip_nl` / `pp_next_raw_into`, so this is a mode flag, not a fork of the
+ source.
+
+**Gate:** byte-identical on `-c` **and** `-E` (the `-E` path must be untouched);
+full pp/parse corpora; the line-splice battery + a diagnostic whose line number
+falls across a splice (line tracking must survive losing the newline token —
+verify `loc.line` still advances via `lex_catchup_splices`/`l->line`, not via the
+consumer counting newlines). **Payoff:** the largest Tier-1 instruction win —
+removes ~51 % of `lex_next` outputs (16.9 % self-`Ir`) and the cc drain loop.
+**Risk:** **high** — the directive-line contract is subtle (continuation,
+empty directives, `#` alone on a line, `_Pragma`). This is the one lever to land
+last and gate hardest.
+
+---
+
+## Tier 2 — single shared mutable token slot at the parser boundary
+
+**End-state.** The pp writes each preprocessed token **directly into the
+parser's current-token slot** (out-pointer all the way through), eliminating the
+by-value `pp_next` return and minimizing the lookahead shuffle — the literal
+"shared mutable slot fed by scanner and replayer," extended to the consumer.
+
+**Obstacles (what the slot must keep doing).**
+- **`pp_next` returns `Tok` by value** (`pp.h:31`); `fetch_tok` stores it into
+ `p->cur`/`p->next`/`p->pending` (`parse.c:165-210`). The by-value return is the
+ copy to kill — `pp_next_into(pp, Tok* out)` already exists (`pp_expand.c:1199`).
+- **LL(2) lookahead:** `peek1` needs one token ahead (`p->next`/`has_next`); a few
+ sites need two. The slot model keeps a tiny ring (`cur` + `next`), not a single
+ global like tcc — kit's grammar genuinely needs the second token.
+- **String-literal fusion:** `fetch_tok` collapses adjacent `TOK_STR` runs
+ (`parse.c:164-183`), using `p->pending` as a one-token pushback. Must survive.
+- **Replay sources:** `advance` already sources `p->cur` from *either* the replay
+ buffer *or* pp (`parse.c:186-198`). Replay backs initializer re-parse
+ (`parse_init.c:71-151`) and a `_Generic`/builtin save-restore
+ (`parse_expr.c:2785-2805`). The slot model must treat replay as just another
+ source feeding the slot (it already is).
+
+**Change.**
+1. Convert `fetch_tok`'s pp pull to the out-pointer form: pull straight into the
+ destination slot (`pp_next_into(p->pp, &slot)`), dropping the by-value return
+ and its 28-byte sret copy. Keep string fusion by fusing in place into the slot.
+2. Make the lookahead shuffle move *slots*, not re-pull: `advance` promotes
+ `next → cur` by struct move (unavoidable for LL(2)); ensure no redundant copy
+ beyond that one.
+3. Leave replay as a source that fills the same slot. No new buffering.
+
+This is **not** tcc's single global `tok` — kit's LL(2) + string fusion + replay
+make a one-word slot wrong. The faithful kit form is "one out-pointer relay from
+lexer through pp into a 2-slot parser ring." That is the achievable shape; pursue
+no further collapse here.
+
+**Gate:** byte-identical, full parse corpus + the string-fusion and replay cases
+(`_Generic`, designated/array-string initializers) explicitly in the diff set.
+**Payoff:** removes the per-token by-value copy on the hottest path (the whole
+parse cluster, ~37 % of `-c`); modest but uniform. **Risk:** medium — lookahead
+and pushback are easy to get subtly wrong; the replay save/restore
+(`parse_expr.c:2785`) must round-trip identically.
+
+---
+
+## Tier 3 — unify the value stacks via a CG-provided aux hook
+
+**End-state (user's design).** One value stack, owned by the CG API. The CG
+exposes an **opaque per-entry aux slot** that the C frontend tags with its
+ancillary info (`const Type*`, `PcgLvAux`, value flags). The frontend stops
+keeping `cg_slot_stack` in lockstep; structural ops (`dup`/`swap`/`drop`/`rot`)
+carry the aux **for free** because the CG owns the single stack. The seam stays
+intact: the CG never interprets the aux bytes.
+
+**Why it's worth doing.** It deletes an entire bug class (the two stacks
+"drifting") and the lockstep mirroring code in `cg_adapter.c`
+(`pcg_dup`/`pcg_swap`/`pcg_rot3`, `cg_adapter.c:113-142`), and turns
+`pcg_top_type` / `pcg_aux_top` (`cg_adapter.c:174-204`) into a direct read of the
+live entry instead of a parallel-array index. The instruction payoff is the
+removed mirroring; the larger payoff is structural cleanliness (the project's
+stated preference, `[[clean-structural-redesign-pref]]`).
+
+**API additions (new public CG surface, kept opaque):**
+```c
+// configured once at cg-open: the frontend declares its per-entry aux size.
+KitCg* kit_cg_open(..., uint32_t sv_aux_size, uint32_t sv_aux_align);
+// returns a pointer to the live aux bytes for the entry `depth` from TOS.
+void* kit_cg_sv_aux(KitCg*, uint32_t depth);
+```
+The CG widens its stack node to `{ApiSValue core; <aux stride>}` and `memcpy`s
+the aux on every structural op. The frontend reads/writes `*(PcgSlot_payload*)
+kit_cg_sv_aux(g, 0)`.
+
+**Key design decisions to settle during implementation:**
+- **Aux storage: inline stride vs `void*` cookie.** Inline (the node grows by the
+ ~40-byte C payload) keeps the stack contiguous and dup/swap a single `memcpy`,
+ but widens the hot `ApiSValue` node — measure against the < 64 B discipline
+ (the node is currently 40 B specifically to keep `delayed` off-node). A `void*`
+ cookie keeps the core node small but adds an indirection and per-push aux
+ allocation. **Recommendation:** inline stride, frontend-declared, because it
+ collapses two stacks (40 B + ~48 B) into one and removes the second growth/
+ allocation entirely; gate the node-size impact on the value-stack microbench.
+- **Suppressed-codegen mode.** The frontend runs sizeof/constant contexts with
+ emit disabled (`suppress_codegen`, `parse_priv.h:390`; `pcg_emit_enabled`)
+ while still tracking types on `cg_slot_stack`. With a unified stack the CG must
+ still maintain the *aux* layer (and a stack-depth counter) when codegen is
+ suppressed — i.e. push/pop the entry and its aux without emitting. Define a
+ "type-only" push on the CG stack, or have suppression gate emission only, never
+ the stack bookkeeping.
+- **lvalue-aux folding without an emit.** `pcg_lv_member`/`pcg_lv_subscript`
+ mutate the TOS aux *without* a CG op (`cg_adapter.c`, the `field`/`index`
+ folding). Under the unified stack these become in-place writes through
+ `kit_cg_sv_aux(g, 0)` — same effect, no parallel array.
+
+**Migration (mechanical, large surface):** rewrite every `pcg_*` helper to read/
+write aux through the hook instead of `cg_slot_stack`; delete `cg_slot_stack` /
+`cg_type_sp` and the mirroring. The pcg API to the parser is unchanged, so
+`parse_expr.c` / `parse_stmt.c` / etc. are untouched — the churn is confined to
+`cg_adapter.c` + the CG stack internals.
+
+**Gate:** **byte-identical** — this is a representational change, not an emitted-
+byte change, so the strict gate applies (it must not perturb output). Full
+suite + sqlite `-E`/`-c` identical to golden. Verify on **x64 and rv64**, not
+just aa64 (the value stack is shared NDT infrastructure; §5). **Risk:** medium-
+high plumbing, low semantic — the emitted code should be identical; the risk is a
+missed mirror site or an aux-not-carried-on-rot bug, which the byte gate catches.
+
+---
+
+## Sequencing & recommendation
+
+```
+Tier 0 re-baseline + doc fixes (½ day, no behavior change) ← do first
+Tier 1B macro-arg copy reduction (byte-identical) ← lowest risk
+Tier 1A newline → BOL flag, cc path (byte-identical, hard gate) ← riskiest; land last in T1
+Tier 2 single token slot at parser (byte-identical)
+Tier 3 unify value stacks via aux hook(byte-identical, x64+rv64) ← biggest structural payoff
+```
+
+Each tier is independently landable and revert-safe; re-profile and re-rank after
+each (§5 — the highest lever moves as work is removed). The honest expectation,
+consistent with PERF.md §2 (the frontend gap is ~uniform 3× with no single hot
+function): **no tier is a silver bullet.** Tier 1A is the largest single
+instruction win; Tier 3 is the largest *structural* win (deletes the dual-stack
+bug class) for a modest instruction gain. The ~2× headroom a full tcc-shape
+collapse *including the vtable* might reach stays out of scope by §4.3's standing
+decision — the seven-backend modularity is worth its two indirect calls.
