commit 8e9dc6c4c12726f18150535ec45a800b6659ee67
parent b073810bd67ba34a5f4f213fa3899d6df6f03429
Author: Ryan Sepassi <rsepassi@gmail.com>
Date: Wed, 10 Jun 2026 21:56:27 -0700
perf(types): memoize ABI facts + record layouts; share one hashmap facility
Two per-TU O(1) memos collapse hot repeated type queries:
- ABI info (size/align/scalar-kind/signedness) per Type* in c_abi_type_info, the
chokepoint behind every sizeof/alignof/scalar probe: body-size 2098->1971ms
(-6%); a 1M-statement TU issued 7M lowering round-trips, now ~all cache hits.
- Completed record layout ids keyed by tag id, replacing a per-lookup list scan
that was O(records^2): a 8000-distinct-struct TU 904ms->41ms (22x).
Consistency cleanup (per review): route everything through the shared hashmap
facility instead of bespoke open-addressed tables. Add KIT_HASHSET_DEFINE — an
open-addressed set with CUSTOM hash+eq — to kit/support/hashmap.h for the
structural type intern (whose identity is structural, not a scalar key, so the
existing scalar key->value KIT_HASHMAP_DEFINE can't express it). The ABI and
record memos are plain KIT_HASHMAP_DEFINE (Type* and tag-id keys). Give Pool a
single shared arena-heap facade (Pool.arena_heap) so all per-pool maps get arena
lifetime with no teardown; migrate the parser's scope/tag/extern indexes off
their duplicate local facade onto it.
A Pool is 1:1 with a compiler, so the former defensive (compiler, ...) keys are
dropped. Object output byte-identical across the toy/parse/derived/record
corpora; type-decl/body-size/recmemo wins all preserved. Verified: test-cg-api/
toy/parse/pp/libc/smoke-x64 all green.
Diffstat:
6 files changed, 253 insertions(+), 200 deletions(-)
diff --git a/include/kit/support/hashmap.h b/include/kit/support/hashmap.h
@@ -175,4 +175,88 @@ static inline uint32_t kit_hash_u64(uint64_t x) {
} \
struct NAME
+/* Open-addressed hash SET over a pointer/scalar element type, with CUSTOM hash
+ * and equality. Where KIT_HASHMAP_DEFINE is a scalar key -> value map with
+ * built-in `==` equality, this is for interning / hash-consing: the stored
+ * element IS the canonical result, and membership is decided by a structural
+ * predicate (e.g. two independently built `int*` Types compare equal). A
+ * zero/NULL element marks an empty slot, so ET must be a pointer (or a scalar
+ * whose 0 value is never a real member). HASH_FN(ET) and EQ_FN(ET a, ET b) are
+ * function (or function-like macro) names. Lookup hashes/compares a probe of
+ * the same type ET; on a miss the caller allocates the canonical element and
+ * NAME##_add()s it. Heap-backed like KIT_HASHMAP_DEFINE (pair with an
+ * arena-heap facade for arena lifetime). */
+#define KIT_HASHSET_DEFINE(NAME, ET, HASH_FN, EQ_FN) \
+ typedef struct NAME { \
+ KitHeap* heap; \
+ ET* slots; \
+ uint32_t cap; \
+ uint32_t used; \
+ } NAME; \
+ \
+ KIT_HASHMAP_UNUSED static void NAME##_resize(NAME* s, uint32_t new_cap) { \
+ ET* fresh; \
+ uint32_t i, mask; \
+ fresh = (ET*)s->heap->alloc(s->heap, sizeof(ET) * new_cap, _Alignof(ET)); \
+ if (!fresh) return; \
+ memset(fresh, 0, sizeof(ET) * new_cap); \
+ mask = new_cap - 1u; \
+ for (i = 0; i < s->cap; ++i) { \
+ ET e = s->slots[i]; \
+ uint32_t j; \
+ if (!(e)) continue; \
+ j = HASH_FN(e) & mask; \
+ while (fresh[j]) j = (j + 1u) & mask; \
+ fresh[j] = e; \
+ } \
+ if (s->slots) s->heap->free(s->heap, s->slots, sizeof(ET) * s->cap); \
+ s->slots = fresh; \
+ s->cap = new_cap; \
+ } \
+ \
+ KIT_HASHMAP_UNUSED static inline void NAME##_init_cap(NAME* s, KitHeap* h, \
+ uint32_t cap) { \
+ s->heap = h; \
+ s->slots = NULL; \
+ s->cap = 0; \
+ s->used = 0; \
+ if (cap) NAME##_resize(s, cap); \
+ } \
+ \
+ KIT_HASHMAP_UNUSED static inline void NAME##_init(NAME* s, KitHeap* h) { \
+ NAME##_init_cap(s, h, KIT_HASHMAP_INIT_CAP); \
+ } \
+ \
+ KIT_HASHMAP_UNUSED static inline void NAME##_fini(NAME* s) { \
+ if (s->slots) s->heap->free(s->heap, s->slots, sizeof(ET) * s->cap); \
+ s->slots = NULL; \
+ s->cap = s->used = 0; \
+ } \
+ \
+ KIT_HASHMAP_UNUSED static inline ET NAME##_find(const NAME* s, ET probe) { \
+ uint32_t mask, j; \
+ if (s->cap == 0) return (ET)0; \
+ mask = s->cap - 1u; \
+ j = HASH_FN(probe) & mask; \
+ while (s->slots[j]) { \
+ if (EQ_FN(s->slots[j], probe)) return s->slots[j]; \
+ j = (j + 1u) & mask; \
+ } \
+ return (ET)0; \
+ } \
+ \
+ KIT_HASHMAP_UNUSED static inline void NAME##_add(NAME* s, ET e) { \
+ uint32_t mask, j; \
+ if (s->cap == 0 || \
+ s->used * KIT_HASHMAP_LOAD_DEN >= s->cap * KIT_HASHMAP_LOAD_NUM) \
+ NAME##_resize(s, s->cap ? s->cap * 2u : KIT_HASHMAP_INIT_CAP); \
+ if (s->cap == 0) return; \
+ mask = s->cap - 1u; \
+ j = HASH_FN(e) & mask; \
+ while (s->slots[j]) j = (j + 1u) & mask; \
+ s->slots[j] = e; \
+ s->used++; \
+ } \
+ struct NAME
+
#endif
diff --git a/lang/c/abi/c_abi.c b/lang/c/abi/c_abi.c
@@ -2,10 +2,49 @@
#include <string.h>
+/* Type -> ABITypeInfo memo. ABI facts (size/align/scalar kind/signedness) are a
+ * pure function of the C type + the fixed target, so once computed they never
+ * change — except a struct/union still incomplete, which we therefore never
+ * cache. The Pool is 1:1 with a compiler, so a plain Type* key suffices.
+ * Arena-backed (the pool arena-heap), in the pool's abi_cache slot, reclaimed
+ * wholesale at teardown. Collapses the per-query type_cg lowering + cg-API
+ * round-trips — a hot path: every sizeof/alignof/scalar probe — to one lookup. */
+static int abi_info_cacheable(const Type* t) {
+ /* Incomplete records have no stable layout yet; everything else (scalars,
+ * pointers, arrays, functions, enums, complete records) is fixed. */
+ return !((t->kind == TY_STRUCT || t->kind == TY_UNION) && t->rec.incomplete);
+}
+
+static inline u32 abi_type_ptr_hash(const Type* t) {
+ return kit_hash_u64((uint64_t)(uintptr_t)t);
+}
+
+KIT_HASHMAP_DEFINE(AbiInfoMap, const Type*, ABITypeInfo, abi_type_ptr_hash);
+
+static AbiInfoMap* abi_cache_get(Pool* p) {
+ AbiInfoMap* m = (AbiInfoMap*)p->abi_cache;
+ if (m) return m;
+ m = arena_new(p->arena, AbiInfoMap);
+ if (!m) return NULL;
+ AbiInfoMap_init_cap(m, &p->arena_heap, 0); /* lazy: first insert allocates */
+ p->abi_cache = m;
+ return m;
+}
+
ABITypeInfo c_abi_type_info(KitCompiler* a, Pool* p, const Type* t) {
- KitCgTypeId id = type_cg_id_in_pool(a, p, t);
- KitCgTypeKind kind = kit_cg_type_kind(a, id);
+ AbiInfoMap* cache = NULL;
+ KitCgTypeId id;
+ KitCgTypeKind kind;
ABITypeInfo r;
+ if (abi_info_cacheable(t)) {
+ cache = abi_cache_get(p);
+ if (cache) {
+ ABITypeInfo* hit = AbiInfoMap_get(cache, t);
+ if (hit) return *hit;
+ }
+ }
+ id = type_cg_id_in_pool(a, p, t);
+ kind = kit_cg_type_kind(a, id);
memset(&r, 0, sizeof(r));
r.size = (u32)kit_cg_type_size(a, id);
r.align = kit_cg_type_align(a, id);
@@ -31,6 +70,7 @@ ABITypeInfo c_abi_type_info(KitCompiler* a, Pool* p, const Type* t) {
break;
}
r.signed_ = type_is_signed_integer(t);
+ if (cache) AbiInfoMap_set(cache, t, r);
return r;
}
diff --git a/lang/c/parse/parse.c b/lang/c/parse/parse.c
@@ -293,33 +293,6 @@ u32 count_recorded_top_level_items(const Tok* vec, u32 len) {
* O(1) per lookup. */
#define SCOPE_INDEX_THRESHOLD 12u
-/* KitHeap facade over the pool's arena: the scope/tag/external indexes allocate
- * through this so all their storage lives in the per-TU arena and is reclaimed
- * in bulk when the pool is freed. The file scope is never popped, so this also
- * removes any per-scope teardown bookkeeping. `free` is a no-op (the arena owns
- * the memory); resize orphans the old table in the arena, which is bounded by
- * the final table size and negligible against the rest of the TU's arena use.
- */
-static void* c_arena_heap_alloc(KitHeap* h, size_t n, size_t align) {
- return kit_arena_alloc((KitArena*)h->user, n, align);
-}
-static void* c_arena_heap_realloc(KitHeap* h, void* old, size_t old_n,
- size_t new_n, size_t align) {
- void* q = kit_arena_alloc((KitArena*)h->user, new_n, align);
- if (q && old && old_n) memcpy(q, old, old_n < new_n ? old_n : new_n);
- return q;
-}
-static void c_arena_heap_free(KitHeap* h, void* p, size_t n) {
- (void)h;
- (void)p;
- (void)n;
-}
-static void c_arena_heap_init(Parser* p) {
- p->arena_heap.alloc = c_arena_heap_alloc;
- p->arena_heap.realloc = c_arena_heap_realloc;
- p->arena_heap.free = c_arena_heap_free;
- p->arena_heap.user = p->pool->arena;
-}
Scope* scope_new(Parser* p, Scope* parent) {
Scope* s = arena_new(p->pool->arena, Scope);
@@ -344,7 +317,7 @@ void scope_pop(Parser* p) {
* current binding a linear scan would return — wins on shadowing. */
static void scope_entries_index_build(Parser* p, Scope* s) {
SymEntry* e;
- SymEntryMap_init_cap(&s->emap, &p->arena_heap, 64u);
+ SymEntryMap_init_cap(&s->emap, &p->pool->arena_heap, 64u);
for (e = s->entries; e; e = e->next)
if (e->name) (void)SymEntryMap_try_insert(&s->emap, e->name, e, NULL);
}
@@ -438,7 +411,7 @@ static void reject_same_scope_redefinition(Parser* p, Sym name,
static void tag_index_build(Parser* p, Scope* s) {
TagEntry* e;
- TagEntryMap_init_cap(&s->tmap, &p->arena_heap, 64u);
+ TagEntryMap_init_cap(&s->tmap, &p->pool->arena_heap, 64u);
for (e = s->tags; e; e = e->next)
if (e->name) (void)TagEntryMap_try_insert(&s->tmap, e->name, e, NULL);
}
@@ -1612,9 +1585,8 @@ void parse_c(Compiler* c, Pool* pool, Pp* pp, DeclTable* decls, CG* cg,
p.auto_var_init = (u8)auto_var_init;
/* Index storage for the scope/tag tables and the external-function table all
- * comes from the arena via this facade; the maps need it before first use. */
- c_arena_heap_init(&p);
- ExternalFuncMap_init(&p.external_funcs, &p.arena_heap);
+ * comes from the arena via the pool's shared arena-heap facade. */
+ ExternalFuncMap_init(&p.external_funcs, &p.pool->arena_heap);
for (i = (CKw)1; i < KW_COUNT; ++i) {
p.kw_sym[i] = kit_sym_intern(p.pool->c, kit_slice_cstr(kw_names[i]));
diff --git a/lang/c/parse/parse_priv.h b/lang/c/parse/parse_priv.h
@@ -159,8 +159,8 @@ struct TagEntry {
* SCOPE_INDEX_THRESHOLD, so the O(n^2) "scan the whole scope per declaration"
* cost (file scopes with thousands of globals/typedefs, functions with
* thousands of locals) collapses to O(1) average lookups while tiny block
- * scopes stay on the cheap linear list. The maps allocate through the parser's
- * arena-heap facade (see parse.c) so there is nothing to free. */
+ * scopes stay on the cheap linear list. The maps allocate through the pool's
+ * shared arena-heap facade (Pool.arena_heap) so there is nothing to free. */
KIT_HASHMAP_DEFINE(SymEntryMap, Sym, SymEntry*, kit_hash_u32);
KIT_HASHMAP_DEFINE(TagEntryMap, Sym, TagEntry*, kit_hash_u32);
KIT_HASHMAP_DEFINE(ExternalFuncMap, Sym, SymEntry*, kit_hash_u32);
@@ -319,10 +319,9 @@ typedef struct Parser {
Scope* scope;
/* name -> current file-scope function entry. Replaces what was an O(n) linear
- * list walked on every function declaration/reference. */
+ * list walked on every function declaration/reference. Storage comes from the
+ * pool's shared arena-heap facade (Pool.arena_heap). */
ExternalFuncMap external_funcs;
- /* KitHeap facade over pool->arena backing the scope/tag/external indexes. */
- KitHeap arena_heap;
CGLabel cur_break;
CGLabel cur_continue;
diff --git a/lang/c/type/type.c b/lang/c/type/type.c
@@ -29,71 +29,6 @@ struct TypeListNode {
Type ty;
};
-typedef struct CgRecordMemo CgRecordMemo;
-struct CgRecordMemo {
- CgRecordMemo* next;
- const KitCompiler* compiler;
- const Type* type;
- KitCgTypeId id;
-};
-
-/* Open-addressed structural intern table for derived types whose identity is
- * STRUCTURAL — pointer / array / function, and qualified variants of any
- * non-tagged type. Slots hold the canonical Type*; lookup hashes and compares
- * only the kind-specific identity fields (never a raw memcmp), so structural
- * nodes need no zeroing and their padding is irrelevant. Tagged types
- * (struct/union/enum) are interned by declaration identity instead and live on
- * `derived`. Replaces the former O(n) linear scan of the whole derived list —
- * that scan was O(types * derivations), catastrophic on type-population-heavy
- * TUs. The table backing array is arena-allocated; old arrays leak into the
- * arena and are reclaimed wholesale at pool teardown (no fini hook). */
-typedef struct TypeInternTable {
- const Type** slots; /* cap entries, power-of-two; NULL == empty */
- u32 cap;
- u32 used;
-} TypeInternTable;
-
-typedef struct PoolTypeCache {
- /* Direct slots for void + primitive kinds (TY_VOID..TY_LDOUBLE). */
- const Type* prim[NUM_PRIM_KINDS];
- /* Structurally-interned ptr/array/func + qualified non-tagged types. */
- TypeInternTable structural;
- /* Identity-interned tagged types (struct/union/enum, qualified or not) and
- * the throwaway record-builder results: a list, scanned only by the (rare)
- * tag-based type_qualified / type_unqual paths and never per derivation. */
- TypeListNode* derived;
- /* Completed record layout ids are compiler-local. */
- CgRecordMemo* cg_record_memos;
- /* Tag id allocator (1-based; TAG_NONE = 0). */
- u32 next_tag;
-} PoolTypeCache;
-
-static PoolTypeCache* cache_get(Pool* p) {
- PoolTypeCache* c = (PoolTypeCache*)p->type_cache;
- if (c) return c;
- c = arena_new(p->arena, PoolTypeCache);
- if (!c) return NULL;
- memset(c, 0, sizeof *c);
- c->next_tag = 1;
- p->type_cache = c;
- return c;
-}
-
-static Type* alloc_type_node(Pool* p, PoolTypeCache* c) {
- TypeListNode* n = arena_new(p->arena, TypeListNode);
- if (!n) return NULL;
- memset(n, 0, sizeof *n);
- n->next = c->derived;
- c->derived = n;
- return &n->ty;
-}
-
-/* Bare structural-type node: arena-allocated, NOT linked into `derived`, NOT
- * zeroed. Each constructor writes exactly the fields its kind reads; the
- * structural table 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 u32 type_fnv_ptr(u32 h, const void* q) {
u64 u = (u64)(uintptr_t)q;
h = (h ^ (u32)u) * 16777619u;
@@ -101,7 +36,11 @@ static u32 type_fnv_ptr(u32 h, const void* q) {
return h;
}
-/* Structural hash over a (non-tagged) derived type's identity fields. */
+/* Structural hash + equality over a (non-tagged) derived type's identity
+ * fields. These hash-cons TY_PTR / TY_ARRAY / TY_FUNC and qualified variants of
+ * non-tagged types: two independently built `int*` Types hash and compare equal
+ * and so collapse to one canonical node. They compare fields, never raw bytes,
+ * so a structural node's union tail and padding may stay uninitialized. */
static u32 type_struct_hash(const Type* t) {
u32 h = 2166136261u;
h = (h ^ (u32)t->kind) * 16777619u;
@@ -151,52 +90,69 @@ static int type_struct_eq(const Type* a, const Type* b) {
}
}
-static const Type* type_intern_find(const TypeInternTable* tab,
- const Type* probe, u32 h) {
- u32 mask, i;
- const Type* s;
- if (!tab->slots) return NULL;
- mask = tab->cap - 1u;
- i = h & mask;
- while ((s = tab->slots[i]) != NULL) {
- if (type_struct_eq(s, probe)) return s;
- i = (i + 1u) & mask;
- }
- return NULL;
-}
-
-/* Insert a freshly built canonical node. Best-effort under OOM: on a failed
- * grow the node is simply not interned (a later identical query allocates a
- * duplicate — correct, just unshared), matching the arena/buf failure policy. */
-static void type_intern_add(Pool* p, TypeInternTable* tab, const Type* t,
- u32 h) {
- u32 mask, i;
- if (!tab->slots || (tab->used + 1u) * 4u >= tab->cap * 3u) {
- u32 ncap = tab->cap ? tab->cap * 2u : 64u;
- const Type** ns = arena_zarray(p->arena, const Type*, ncap);
- if (!ns) return;
- if (tab->slots) {
- u32 nmask = ncap - 1u, k;
- for (k = 0; k < tab->cap; ++k) {
- const Type* s = tab->slots[k];
- u32 j;
- if (!s) continue;
- j = type_struct_hash(s) & nmask;
- while (ns[j]) j = (j + 1u) & nmask;
- ns[j] = s;
- }
- }
- tab->slots = ns;
- tab->cap = ncap;
- }
- if (!tab->slots) return;
- mask = tab->cap - 1u;
- i = h & mask;
- while (tab->slots[i]) i = (i + 1u) & mask;
- tab->slots[i] = t;
- tab->used++;
+/* Structural intern SET: the canonical Type* IS the stored element and
+ * membership is decided structurally (type_struct_eq) — which a scalar
+ * key->value map cannot express, hence KIT_HASHSET_DEFINE. Interns
+ * ptr/array/func + qualified non-tagged types; tagged types are interned by
+ * declaration identity on `derived` and never enter this set. Replaces the
+ * former O(types) linear scan of one flat derived list (which made each
+ * derivation O(types) → type construction O(types^2)). */
+KIT_HASHSET_DEFINE(TypeInternSet, const Type*, type_struct_hash, type_struct_eq);
+
+/* Completed record layout id, keyed by record identity. A record's identity is
+ * its tag id (same_record_type is tag-id equality), so a plain u32->id map
+ * captures it; the Pool is 1:1 with a compiler so no compiler key is needed.
+ * Replaces the former per-lookup list scan (O(records^2) for record-heavy TUs).
+ * Tag id 0 (TAG_NONE) never names a stored record, so it is safe as the empty
+ * key sentinel. */
+KIT_HASHMAP_DEFINE(CgRecordMap, u32, KitCgTypeId, kit_hash_u32);
+
+typedef struct PoolTypeCache {
+ /* Direct slots for void + primitive kinds (TY_VOID..TY_LDOUBLE). */
+ const Type* prim[NUM_PRIM_KINDS];
+ /* Structurally-interned ptr/array/func + qualified non-tagged types. */
+ TypeInternSet structural;
+ /* Identity-interned tagged types (struct/union/enum, qualified or not) and
+ * the throwaway record-builder results: a list, scanned only by the (rare)
+ * tag-based type_qualified / type_unqual paths and never per derivation. */
+ TypeListNode* derived;
+ /* Completed record layout ids, keyed by tag id. */
+ CgRecordMap cg_records;
+ /* Tag id allocator (1-based; TAG_NONE = 0). */
+ u32 next_tag;
+} PoolTypeCache;
+
+static PoolTypeCache* cache_get(Pool* p) {
+ PoolTypeCache* c = (PoolTypeCache*)p->type_cache;
+ if (c) return c;
+ c = arena_new(p->arena, PoolTypeCache);
+ if (!c) return NULL;
+ memset(c, 0, sizeof *c);
+ c->next_tag = 1;
+ /* Both tables run on the pool's arena-heap facade: a resize orphans the old
+ * array into the arena (reclaimed wholesale at teardown), so no fini hook is
+ * 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);
+ p->type_cache = c;
+ return c;
+}
+
+static Type* alloc_type_node(Pool* p, PoolTypeCache* c) {
+ TypeListNode* n = arena_new(p->arena, TypeListNode);
+ if (!n) return NULL;
+ memset(n, 0, sizeof *n);
+ n->next = c->derived;
+ c->derived = n;
+ return &n->ty;
}
+/* Bare structural-type node: arena-allocated, NOT linked into `derived`, NOT
+ * 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); }
+
const Type* type_void(Pool* p) { return type_prim(p, TY_VOID); }
const Type* type_prim(Pool* p, TypeKind kind) {
@@ -215,29 +171,26 @@ const Type* type_prim(Pool* p, TypeKind kind) {
const Type* type_ptr(Pool* p, const Type* pointee) {
PoolTypeCache* c = cache_get(p);
Type probe;
- u32 h;
const Type* found;
Type* t;
if (!c) return NULL;
probe.kind = TY_PTR;
probe.qual = 0;
probe.ptr.pointee = pointee;
- h = type_struct_hash(&probe);
- found = type_intern_find(&c->structural, &probe, h);
+ found = TypeInternSet_find(&c->structural, &probe);
if (found) return found;
t = alloc_struct_type(p);
if (!t) return NULL;
t->kind = TY_PTR;
t->qual = 0;
t->ptr.pointee = pointee;
- type_intern_add(p, &c->structural, t, h);
+ TypeInternSet_add(&c->structural, t);
return t;
}
const Type* type_array(Pool* p, const Type* elem, u32 count, int incomplete) {
PoolTypeCache* c = cache_get(p);
Type probe;
- u32 h;
const Type* found;
Type* t;
if (!c) return NULL;
@@ -246,8 +199,7 @@ const Type* type_array(Pool* p, const Type* elem, u32 count, int incomplete) {
probe.arr.elem = elem;
probe.arr.count = count;
probe.arr.incomplete = (u8)(incomplete ? 1 : 0);
- h = type_struct_hash(&probe);
- found = type_intern_find(&c->structural, &probe, h);
+ found = TypeInternSet_find(&c->structural, &probe);
if (found) return found;
t = alloc_struct_type(p);
if (!t) return NULL;
@@ -256,7 +208,7 @@ const Type* type_array(Pool* p, const Type* elem, u32 count, int incomplete) {
t->arr.elem = elem;
t->arr.count = count;
t->arr.incomplete = (u8)(incomplete ? 1 : 0);
- type_intern_add(p, &c->structural, t, h);
+ TypeInternSet_add(&c->structural, t);
return t;
}
@@ -264,7 +216,6 @@ const Type* type_func(Pool* p, const Type* ret, const Type** params, u16 n,
int variadic) {
PoolTypeCache* c = cache_get(p);
Type probe;
- u32 h;
const Type* found;
Type* t;
if (!c) return NULL;
@@ -276,8 +227,7 @@ const Type* type_func(Pool* p, const Type* ret, const Type** params, u16 n,
probe.fn.params = params;
probe.fn.nparams = n;
probe.fn.variadic = (u8)(variadic ? 1 : 0);
- h = type_struct_hash(&probe);
- found = type_intern_find(&c->structural, &probe, h);
+ found = TypeInternSet_find(&c->structural, &probe);
if (found) return found;
t = alloc_struct_type(p);
if (!t) return NULL;
@@ -294,7 +244,7 @@ const Type* type_func(Pool* p, const Type* ret, const Type** params, u16 n,
} else {
t->fn.params = NULL;
}
- type_intern_add(p, &c->structural, t, h);
+ TypeInternSet_add(&c->structural, t);
return t;
}
@@ -330,17 +280,15 @@ const Type* type_qualified(Pool* p, const Type* base, u16 qual) {
/* Non-tagged: structurally interned (qualified prim / ptr / array / func). */
{
Type probe = *base;
- u32 h;
const Type* found;
probe.qual = qual;
- h = type_struct_hash(&probe);
- found = type_intern_find(&c->structural, &probe, h);
+ found = TypeInternSet_find(&c->structural, &probe);
if (found) return found;
t = alloc_struct_type(p);
if (!t) return NULL;
*t = *base;
t->qual = qual;
- type_intern_add(p, &c->structural, t, h);
+ TypeInternSet_add(&c->structural, t);
return t;
}
}
@@ -491,17 +439,15 @@ const Type* type_unqual(Pool* p, const Type* t) {
* prim; here that leaves ptr / array / func). */
{
Type probe = *t;
- u32 h;
const Type* found;
probe.qual = 0;
- h = type_struct_hash(&probe);
- found = type_intern_find(&c->structural, &probe, h);
+ found = TypeInternSet_find(&c->structural, &probe);
if (found) return found;
nt = alloc_struct_type(p);
if (!nt) return NULL;
*nt = *t;
nt->qual = 0;
- type_intern_add(p, &c->structural, nt, h);
+ TypeInternSet_add(&c->structural, nt);
return nt;
}
}
@@ -740,14 +686,6 @@ static KitCgTypeId type_cg_builtin(KitCompiler* c, TypeKind kind) {
return KIT_CG_TYPE_NONE;
}
-static int same_record_type(const Type* a, const Type* b) {
- if (a == b) return 1;
- if (!a || !b) return 0;
- if (a->kind != b->kind) return 0;
- if (a->kind != TY_STRUCT && a->kind != TY_UNION) return 0;
- return a->rec.tag_id != TAG_NONE && a->rec.tag_id == b->rec.tag_id;
-}
-
typedef enum TypeCgMode {
TYPE_CG_VALUE,
TYPE_CG_RECORD_FIELD,
@@ -762,37 +700,28 @@ typedef struct TypeCgLower {
static KitCgTypeId type_cg_lower(TypeCgLower* l, const Type* t,
TypeCgMode mode);
+/* Record identity is its tag id (records are never structurally interned), so
+ * the memo is a plain tag-id -> layout-id map. Only ever called with STRUCT/
+ * UNION types, so t->rec is live; complete records always carry a non-zero tag,
+ * so tag 0 is free to serve as the map's empty-key sentinel. */
static KitCgTypeId type_cg_record_memo_get(PoolTypeCache* cache, KitCompiler* c,
const Type* t) {
+ const KitCgTypeId* hit;
+ (void)c;
if (!cache) return KIT_CG_TYPE_NONE;
- for (CgRecordMemo* m = cache->cg_record_memos; m; m = m->next) {
- if (m->compiler == c && (m->type == t || same_record_type(m->type, t))) {
- return m->id;
- }
- }
- return KIT_CG_TYPE_NONE;
+ hit = CgRecordMap_get(&cache->cg_records, t->rec.tag_id);
+ return hit ? *hit : KIT_CG_TYPE_NONE;
}
static void type_cg_record_memo_put(Pool* p, PoolTypeCache* cache,
KitCompiler* c, const Type* t,
KitCgTypeId id) {
- CgRecordMemo* m;
- if (!p || !cache || !c || !t || id == KIT_CG_TYPE_NONE) return;
+ (void)p;
+ (void)c;
+ if (!cache || !t || id == KIT_CG_TYPE_NONE) return;
if (t->kind != TY_STRUCT && t->kind != TY_UNION) return;
- if (t->rec.incomplete) return;
- for (m = cache->cg_record_memos; m; m = m->next) {
- if (m->compiler == c && (m->type == t || same_record_type(m->type, t))) {
- m->id = id;
- return;
- }
- }
- m = arena_new(p->arena, CgRecordMemo);
- if (!m) return;
- m->compiler = c;
- m->type = t;
- m->id = id;
- m->next = cache->cg_record_memos;
- cache->cg_record_memos = m;
+ if (t->rec.incomplete || t->rec.tag_id == TAG_NONE) return;
+ CgRecordMap_set(&cache->cg_records, t->rec.tag_id, id);
}
static KitCgTypeId type_cg_record_layout(TypeCgLower* l, const Type* t) {
diff --git a/lang/cpp/cpp_support.h b/lang/cpp/cpp_support.h
@@ -12,6 +12,7 @@
#include <stdarg.h>
#include <stddef.h>
#include <stdint.h>
+#include <string.h>
typedef int8_t i8;
typedef int16_t i16;
@@ -32,9 +33,32 @@ typedef u32 BytesId;
typedef struct Pool {
Compiler* c;
KitArena* arena;
- void* type_cache; /* opaque slot owned by the C frontend; unused by cpp */
+ /* A KitHeap facade over `arena`: alloc/realloc route to the arena (realloc
+ * copies into a fresh block), free is a no-op. Lets arena-lifetime hash maps
+ * (KIT_HASHMAP_DEFINE, which is otherwise heap-backed) avoid any teardown —
+ * resize orphans the old table into the arena, bounded by the final size and
+ * reclaimed wholesale at pool teardown. Shared by the parser scope indexes,
+ * the type-system record memo, and the ABI info cache. */
+ KitHeap arena_heap;
+ void* type_cache; /* opaque slot owned by the C type system; unused by cpp */
+ void* abi_cache; /* opaque slot owned by the C ABI layer; unused by cpp */
} Pool;
+static inline void* kit_pool_heap_alloc(KitHeap* h, size_t n, size_t align) {
+ return kit_arena_alloc((KitArena*)h->user, n, align);
+}
+static inline void* kit_pool_heap_realloc(KitHeap* h, void* old, size_t old_n,
+ size_t new_n, size_t align) {
+ void* q = kit_arena_alloc((KitArena*)h->user, new_n, align);
+ if (q && old && old_n) memcpy(q, old, old_n < new_n ? old_n : new_n);
+ return q;
+}
+static inline void kit_pool_heap_free(KitHeap* h, void* p, size_t n) {
+ (void)h;
+ (void)p;
+ (void)n;
+}
+
/* C data model for frontend-visible scalar spelling. kit currently uses LP64
* for 64-bit non-Windows targets, LLP64 for 64-bit Windows targets, and ILP32
* for 32-bit targets. The distinction is exactly sizeof(long): 8 for LP64,
@@ -51,10 +75,15 @@ static inline Pool* c_pool_new(Compiler* c) {
p->c = c;
p->arena = NULL;
p->type_cache = NULL;
+ p->abi_cache = NULL;
if (kit_arena_new(h, 0, &p->arena) != KIT_OK || !p->arena) {
h->free(h, p, sizeof(*p));
return NULL;
}
+ p->arena_heap.alloc = kit_pool_heap_alloc;
+ p->arena_heap.realloc = kit_pool_heap_realloc;
+ p->arena_heap.free = kit_pool_heap_free;
+ p->arena_heap.user = p->arena;
return p;
}
