commit d881c8d951041641ca7361921f94c9d11b06648a
parent d21ba7ec4b06541644f97ea0956b9cb355c10772
Author: Ryan Sepassi <rsepassi@gmail.com>
Date: Fri, 12 Jun 2026 12:23:11 -0700
perf(c): memoize CG type lowering + complete-record unqual on the pool
type_cg_lower re-derived ptr/array/func/enum into a KitCgTypeId on every
pcg_tid() call (per value-push, per load/store, per op); type_unqual
linear-scanned `derived` for every qualified tagged type. Add two
Type*-keyed side memos on PoolTypeCache, mirroring the existing cg_records
tag memo and c_abi.c's AbiInfoMap:
- cg_types: VALUE-mode lowered id per canonical Type*, populated only for
incomplete-free subtrees (new TypeCgLower.saw_incomplete, scoped per
node) so a pointer-to-incomplete-record is never cached as ptr-to-void
before the record completes in place via type_record_install.
- unqual: canonical unqualified node for the complete-tagged path (the
O(derived) scan); incomplete/enum answers stay uncached since they can
still change as a forward record completes.
A direct cg_id field on Type was rejected: type_qualified/type_unqual
intern tagged types via memcmp over sizeof(Type), so a mutable cache field
would corrupt interning (a lowered vs not-yet-lowered variant would
mismatch and duplicate).
Byte-identical: perf_identity_gate.sh (all categories), sqlite3.c
-O0/-O1/-g, and a forward-decl hazard battery. sqlite -O0 compile +6.9%.
test-{parse,cg-api,toy,opt,debug,dwarf,pp}: 5551 pass, 0 fail.
Diffstat:
| M | lang/c/type/type.c | | | 100 | +++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++---------- |
1 file changed, 88 insertions(+), 12 deletions(-)
diff --git a/lang/c/type/type.c b/lang/c/type/type.c
@@ -107,6 +107,27 @@ KIT_HASHSET_DEFINE(TypeInternSet, const Type*, type_struct_hash, type_struct_eq)
* key sentinel. */
KIT_HASHMAP_DEFINE(CgRecordMap, u32, KitCgTypeId, kit_hash_u32);
+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
+ * record's unqualified node never changes); incomplete/enum results are left
+ * uncached because they can still change as a forward record completes. */
+KIT_HASHMAP_DEFINE(CgUnqualMemo, const Type*, const Type*, type_ptr_hash);
+
typedef struct PoolTypeCache {
/* Direct slots for void + primitive kinds (TY_VOID..TY_LDOUBLE). */
const Type* prim[NUM_PRIM_KINDS];
@@ -118,6 +139,10 @@ 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). */
u32 next_tag;
} PoolTypeCache;
@@ -134,6 +159,8 @@ 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;
}
@@ -418,9 +445,18 @@ const Type* type_unqual(Pool* p, const Type* t) {
/* Tagged types are identity-interned on `derived`. */
if ((t->kind == TY_STRUCT || t->kind == TY_UNION) &&
t->rec.tag_id != TAG_NONE) {
+ /* The only memoized case: a complete record's unqualified node is fixed
+ * for the pool's lifetime, so this O(derived) scan can be skipped after
+ * the first hit. The memo holds only struct/union entries, so it is
+ * consulted here rather than taxing the (single-hash) non-tagged path. */
+ const Type* const* hit = CgUnqualMemo_get(&c->unqual, t);
+ if (hit) return *hit;
for (TypeListNode* n = c->derived; n; n = n->next) {
if (n->ty.kind == t->kind && n->ty.qual == 0 &&
n->ty.rec.tag_id == t->rec.tag_id && !n->ty.rec.incomplete) {
+ /* The incomplete/enum fall-throughs below stay uncached — their
+ * result can still change as a forward record completes. */
+ CgUnqualMemo_set(&c->unqual, t, &n->ty);
return &n->ty;
}
}
@@ -695,6 +731,10 @@ typedef struct TypeCgLower {
KitCompiler* c;
Pool* p;
PoolTypeCache* cache;
+ /* Raised whenever lowering passes through a still-incomplete record; scoped
+ * per subtree by type_cg_lower so a node is memoized only when its whole
+ * lowering was incomplete-free (and thus stable for the pool's lifetime). */
+ int saw_incomplete;
} TypeCgLower;
static KitCgTypeId type_cg_lower(TypeCgLower* l, const Type* t,
@@ -731,7 +771,13 @@ static KitCgTypeId type_cg_record_layout(TypeCgLower* l, const Type* t) {
if (!l || !t || (t->kind != TY_STRUCT && t->kind != TY_UNION)) {
return KIT_CG_TYPE_NONE;
}
- if (t->rec.incomplete) return type_cg_builtin(l->c, TY_VOID);
+ if (t->rec.incomplete) {
+ /* Lowers to void for now but to its real layout once the record is
+ * completed in place (type_record_install). Mark the lowering unstable so
+ * no enclosing node caches this transient result. */
+ l->saw_incomplete = 1;
+ return type_cg_builtin(l->c, TY_VOID);
+ }
id = type_cg_record_memo_get(l->cache, l->c, t);
if (id != KIT_CG_TYPE_NONE) return id;
if (t->rec.nfields) {
@@ -776,19 +822,36 @@ static KitCgTypeId type_cg_record_layout(TypeCgLower* l, const Type* t) {
static KitCgTypeId type_cg_lower(TypeCgLower* l, const Type* t,
TypeCgMode mode) {
KitCgTypeId id;
+ int cacheable;
+ int outer_incomplete;
if (!l || !t) return KIT_CG_TYPE_NONE;
id = type_cg_builtin(l->c, (TypeKind)t->kind);
if (id != KIT_CG_TYPE_NONE) return id;
+ /* 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 */
+ }
+ /* 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;
+ l->saw_incomplete = 0;
switch ((TypeKind)t->kind) {
case TY_PTR:
if (mode == TYPE_CG_RECORD_FIELD) {
- return kit_cg_type_ptr(l->c, type_cg_builtin(l->c, TY_VOID), 0);
+ id = kit_cg_type_ptr(l->c, type_cg_builtin(l->c, TY_VOID), 0);
+ } else {
+ id = kit_cg_type_ptr(l->c,
+ type_cg_lower(l, t->ptr.pointee, TYPE_CG_VALUE), 0);
}
- return kit_cg_type_ptr(
- l->c, type_cg_lower(l, t->ptr.pointee, TYPE_CG_VALUE), 0);
+ break;
case TY_ARRAY:
- return kit_cg_type_array(l->c, type_cg_lower(l, t->arr.elem, mode),
- t->arr.count);
+ id = kit_cg_type_array(l->c, type_cg_lower(l, t->arr.elem, mode),
+ t->arr.count);
+ break;
case TY_FUNC: {
KitCgFuncParam* params = NULL;
KitCgFuncSig sig;
@@ -800,24 +863,37 @@ static KitCgTypeId type_cg_lower(TypeCgLower* l, const Type* t,
sig.call_conv = KIT_CG_CC_TARGET_C;
if (t->fn.nparams) {
params = arena_zarray(l->p->arena, KitCgFuncParam, t->fn.nparams);
- if (!params) return KIT_CG_TYPE_NONE;
+ if (!params) {
+ id = KIT_CG_TYPE_NONE;
+ break;
+ }
for (u32 i = 0; i < t->fn.nparams; ++i) {
params[i].type =
type_cg_lower(l, t->fn.params[i], TYPE_CG_RECORD_FIELD);
}
}
sig.params = params;
- return kit_cg_type_func(l->c, sig);
+ id = kit_cg_type_func(l->c, sig);
+ break;
}
case TY_STRUCT:
case TY_UNION:
- return type_cg_record_layout(l, t);
+ id = type_cg_record_layout(l, t);
+ break;
case TY_ENUM:
- return kit_cg_type_enum(l->c, t->enm.tag,
- type_cg_lower(l, t->enm.base, mode), NULL, 0);
+ id = kit_cg_type_enum(l->c, t->enm.tag,
+ type_cg_lower(l, t->enm.base, mode), NULL, 0);
+ break;
default:
- return KIT_CG_TYPE_NONE;
+ id = KIT_CG_TYPE_NONE;
+ break;
+ }
+ if (cacheable && id != KIT_CG_TYPE_NONE && !l->saw_incomplete) {
+ CgTypeMemo_set(&l->cache->cg_types, t, id);
}
+ /* Propagate this subtree's incompleteness to the enclosing lowering. */
+ l->saw_incomplete |= outer_incomplete;
+ return id;
}
KitCgTypeId type_cg_id_in_pool(KitCompiler* c, Pool* p, const Type* t) {
