commit d3e8b7f09626f91da77683a4c532256088448400
parent 492813f8d4bc58c72af70327f281a08e832ca959
Author: Ryan Sepassi <rsepassi@gmail.com>
Date: Fri, 12 Jun 2026 14:00:51 -0700
refactor(c): semantic tagged-type interning; move CG-id cache onto the node
Replace the two memcmp(&n->ty, &tmpl, sizeof(Type)) interning probes in
type_qualified/type_unqual with a semantic type_tagged_eq (kind + qual +
the rec/enm identity payload). The memcmp only worked because every tagged
node carries zeroed padding (alloc_type_node memsets, struct assignment
propagates) — a latent footgun, and the thing that forced the just-added
lowered-id cache onto a side map. The swap is provably output-identical:
zeroed padding means memcmp and a field compare can never disagree.
With interning no longer a whole-struct compare, the lowered KitCgTypeId
moves from the CgTypeMemo side-table onto a cg_id field in Type — it fits
the alignment hole before the union (0 size growth) and is a field read
instead of a hash lookup. It is not part of type identity (neither the
structural intern set nor type_tagged_eq looks at it), and the
incomplete-free guard (TypeCgLower.saw_incomplete) is unchanged, so a
pointer-to-incomplete-record still isn't cached until the record completes.
Byte-identical: perf_identity_gate.sh (all categories incl. linked exe);
sqlite3.c -O0/-O1/-g; forward-decl + const-record hazard battery. sqlite
-O0 +1.3% vs the side-table (~+8% vs pre-Lever-3); side-table removed.
test-parse D/R/J 3069/0 + test-{cg-api,toy,opt,debug,dwarf,pp} clean
(the /E lane needs podman, unavailable from a /tmp worktree).
Diffstat:
2 files changed, 59 insertions(+), 40 deletions(-)
diff --git a/lang/c/type/type.c b/lang/c/type/type.c
@@ -111,16 +111,6 @@ static inline u32 type_ptr_hash(const Type* t) {
return kit_hash_u64((uint64_t)(uintptr_t)t);
}
-/* Lowered KitCgTypeId memo, keyed by the canonical (interned) Type*. type_cg_lower
- * re-derives ptr/array/func/enum on every pcg_tid() call (per value-push, per
- * load/store, per op); since types intern to one canonical node, the lowered id
- * can be cached directly against that node. Records keep their own tag-id memo
- * (cg_records) because one layout is shared across a tag's many Type nodes. Only
- * VALUE-mode results are cached (TYPE_CG_RECORD_FIELD collapses pointers to
- * void*), and only when the lowering touched no still-incomplete record — see
- * type_cg_lower. Pool is 1:1 with a compiler, so a bare Type* key suffices. */
-KIT_HASHMAP_DEFINE(CgTypeMemo, const Type*, KitCgTypeId, type_ptr_hash);
-
/* Canonical-unqualified Type* memo, keyed by the qualified Type*. Collapses the
* O(derived) linear scan type_unqual runs for a complete tagged type (the hot
* const-record path) to one lookup. Only stable answers are inserted (a complete
@@ -139,8 +129,6 @@ typedef struct PoolTypeCache {
TypeListNode* derived;
/* Completed record layout ids, keyed by tag id. */
CgRecordMap cg_records;
- /* Lowered KitCgTypeId per canonical Type* (VALUE-mode, incomplete-free). */
- CgTypeMemo cg_types;
/* Canonical-unqualified node per qualified Type* (stable answers only). */
CgUnqualMemo unqual;
/* Tag id allocator (1-based; TAG_NONE = 0). */
@@ -159,7 +147,6 @@ static PoolTypeCache* cache_get(Pool* p) {
* needed. Lazy (cap 0): the first insert allocates. */
TypeInternSet_init_cap(&c->structural, &p->arena_heap, 0);
CgRecordMap_init_cap(&c->cg_records, &p->arena_heap, 0);
- CgTypeMemo_init_cap(&c->cg_types, &p->arena_heap, 0);
CgUnqualMemo_init_cap(&c->unqual, &p->arena_heap, 0);
p->type_cache = c;
return c;
@@ -178,7 +165,15 @@ static Type* alloc_type_node(Pool* p, PoolTypeCache* c) {
* zeroed. Each constructor writes exactly the fields its kind reads; the
* structural set compares those fields (not raw bytes), so the union tail and
* padding may stay uninitialized. */
-static Type* alloc_struct_type(Pool* p) { return arena_new(p->arena, Type); }
+static Type* alloc_struct_type(Pool* p) {
+ Type* t = arena_new(p->arena, Type);
+ /* cg_id is read by the on-node lowering cache, so it must be initialized even
+ * though the union tail is intentionally left undefined (see the header). The
+ * qualified/unqual paths that do `*t = *base` then inherit base's cached id,
+ * which is correct since lowering ignores qualifiers. */
+ if (t) t->cg_id = KIT_CG_TYPE_NONE;
+ return t;
+}
const Type* type_void(Pool* p) { return type_prim(p, TY_VOID); }
@@ -275,33 +270,52 @@ const Type* type_func(Pool* p, const Type* ret, const Type** params, u16 n,
return t;
}
+/* Semantic identity of a tagged type for interning: kind + qual + the rec/enm
+ * identity payload. Replaces a memcmp over sizeof(Type) — which worked only
+ * because every tagged node carries zeroed padding (alloc_type_node memsets and
+ * struct assignment propagates it), a latent footgun that also forced the
+ * lowered-id cache off the node onto a side map. `incomplete` is part of the
+ * key (unlike type_compatible) because the qualified-snapshot model keeps an
+ * incomplete and a later-completed `const struct S` as distinct nodes. `n` is
+ * an interned node; `base` + the wanted `qual` describe the target (the payload
+ * is base's). */
+static int type_tagged_eq(const Type* n, const Type* base, u16 qual) {
+ if (n->kind != base->kind || n->qual != qual) return 0;
+ switch ((TypeKind)base->kind) {
+ case TY_STRUCT:
+ case TY_UNION:
+ return n->rec.tag_id == base->rec.tag_id && n->rec.tag == base->rec.tag &&
+ n->rec.fields == base->rec.fields &&
+ n->rec.nfields == base->rec.nfields &&
+ n->rec.incomplete == base->rec.incomplete &&
+ n->rec.packed == base->rec.packed &&
+ n->rec.max_align == base->rec.max_align &&
+ n->rec.align_override == base->rec.align_override;
+ case TY_ENUM:
+ return n->enm.tag_id == base->enm.tag_id &&
+ n->enm.tag == base->enm.tag && n->enm.base == base->enm.base;
+ default:
+ return 0;
+ }
+}
+
const Type* type_qualified(Pool* p, const Type* base, u16 qual) {
PoolTypeCache* c;
- Type tmpl;
Type* t;
if (!base || qual == 0) return base;
c = cache_get(p);
if (!c) return NULL;
if (base->kind == TY_STRUCT || base->kind == TY_UNION ||
base->kind == TY_ENUM) {
- /* Tagged types are identity-interned on `derived`. Build the comparison
- * template via assignment (not aggregate initialization). Struct assignment
- * copies the full object representation, including padding bytes, so the
- * memcmp below is byte-stable against the interned nodes (which are likewise
- * produced by `*t = tmpl`). An aggregate *initializer* (`Type tmpl =
- * *base;`) is lowered as a field-by-field copy that leaves padding
- * unspecified, which would make this memcmp miss and intern a duplicate. */
- tmpl = *base;
- tmpl.qual = qual;
+ /* Tagged types are identity-interned on `derived` by semantic payload
+ * (type_tagged_eq), not a raw-byte compare. */
for (TypeListNode* n = c->derived; n; n = n->next) {
- if (n->ty.kind == base->kind && n->ty.qual == qual &&
- memcmp(&n->ty, &tmpl, sizeof(Type)) == 0) {
- return &n->ty;
- }
+ if (type_tagged_eq(&n->ty, base, qual)) return &n->ty;
}
t = alloc_type_node(p, c);
if (!t) return NULL;
- *t = tmpl;
+ *t = *base;
+ t->qual = qual;
return t;
}
/* Non-tagged: structurally interned (qualified prim / ptr / array / func). */
@@ -434,7 +448,6 @@ const Type* type_enum(Pool* p, TagId tag_id, Sym tag, const Type* base) {
const Type* type_unqual(Pool* p, const Type* t) {
PoolTypeCache* c;
- Type tmpl;
Type* nt;
if (!t || t->qual == 0) return t;
if ((unsigned)t->kind < NUM_PRIM_KINDS)
@@ -461,14 +474,13 @@ const Type* type_unqual(Pool* p, const Type* t) {
}
}
}
- tmpl = *t;
- tmpl.qual = 0;
for (TypeListNode* n = c->derived; n; n = n->next) {
- if (memcmp(&n->ty, &tmpl, sizeof(Type)) == 0) return &n->ty;
+ if (type_tagged_eq(&n->ty, t, 0)) return &n->ty;
}
nt = alloc_type_node(p, c);
if (!nt) return NULL;
- *nt = tmpl;
+ *nt = *t;
+ nt->qual = 0;
return nt;
}
/* Non-tagged: structurally interned (qualified prim is handled above as a
@@ -830,11 +842,9 @@ static KitCgTypeId type_cg_lower(TypeCgLower* l, const Type* t,
/* Only VALUE-mode lowering is memoized on the node: TYPE_CG_RECORD_FIELD
* collapses pointers to void*, so the same Type* lowers differently there
* (and that mode is used only transiently for record fields / func params). */
- cacheable = (mode == TYPE_CG_VALUE && l->cache != NULL);
- if (cacheable) {
- const KitCgTypeId* hit = CgTypeMemo_get(&l->cache->cg_types, t);
- if (hit) return *hit; /* cached => was incomplete-free => still stable */
- }
+ cacheable = (mode == TYPE_CG_VALUE);
+ if (cacheable && t->cg_id != KIT_CG_TYPE_NONE)
+ return t->cg_id; /* cached => was incomplete-free => still stable */
/* Scope saw_incomplete to this subtree so the post-recursion check reflects
* only whether *this* node's lowering touched an incomplete record. */
outer_incomplete = l->saw_incomplete;
@@ -889,7 +899,10 @@ static KitCgTypeId type_cg_lower(TypeCgLower* l, const Type* t,
break;
}
if (cacheable && id != KIT_CG_TYPE_NONE && !l->saw_incomplete) {
- CgTypeMemo_set(&l->cache->cg_types, t, id);
+ /* The node is the canonical interned type and we own its storage (arena);
+ * the const is only the public contract. Stashing the stable lowering here
+ * is exactly what dropping the memcmp interning bought us. */
+ ((Type*)t)->cg_id = id;
}
/* Propagate this subtree's incompleteness to the enclosing lowering. */
l->saw_incomplete |= outer_incomplete;
diff --git a/lang/c/type/type.h b/lang/c/type/type.h
@@ -86,6 +86,12 @@ typedef struct Field {
struct Type {
u16 kind;
u16 qual;
+ /* Memoized VALUE-mode CG lowering of this canonical node (0 = not yet
+ * lowered). Sits in the alignment hole before the 8-aligned union, so the
+ * node stays the same size. NOT part of type identity: the structural intern
+ * set compares named fields and type_tagged_eq compares the rec/enm payload,
+ * so this mutable cache never participates in interning. See type_cg_lower. */
+ KitCgTypeId cg_id;
union {
struct {
const Type* pointee;
