commit dc4a6b86a9e69010438db1b6d5131b3432879320
parent 231ebcd6c7c16800a012415b42d1cabdf343d6bf
Author: Ryan Sepassi <rsepassi@gmail.com>
Date: Fri, 12 Jun 2026 11:00:39 -0700
perf(cg,abi): de-quadratic type-lowering caches (O(n^2)->O(1))
The derived-type dedup paths each scanned a growing table on every type use,
making type-heavy compilation O(n^2). On sqlite3.c (263k lines) this was ~70% of
frontend self-time, dominated by find_ptr_type_id.
- find_ptr_type_id / find_array_type_id: linear scan of all CG types -> packed
u64-keyed hashmaps (CgPtrMap/CgArrayMap on CgApiState).
- find_func_type_id: linear scan -> structural hashset of CgApiType* (CgFuncSet);
each entry now carries its self_id so the set can return the id. SEGVEC entries
have stable addresses, so storing pointers is sound.
- abi_cg_func_info / abi_cg_record_layout: linearly-scanned linked-list caches ->
type-id-keyed hashmaps (AbiFnInfoMap/AbiRecLayoutMap); values stay arena-backed.
Byte-identical object output on sqlite3.c. Whole-compile: 1.68x wall / 2.20x
cycles / 1.56x instructions vs before; the cycle win exceeds the instruction win
because the scans were cache-miss-heavy pointer chases.
Diffstat:
3 files changed, 115 insertions(+), 73 deletions(-)
diff --git a/src/abi/abi.c b/src/abi/abi.c
@@ -135,17 +135,14 @@ static ABIRecordLayout* compute_record_layout(TargetABI* a, KitCgTypeId id) {
const ABIRecordLayout* abi_cg_record_layout(TargetABI* a, KitCgTypeId id) {
const CgType* t = cg_type_get(a->c, id);
+ ABIRecordLayout** hit;
+ ABIRecordLayout* L;
if (!t || t->kind != KIT_CG_TYPE_RECORD) return NULL;
- for (RecordLayoutCacheEntry* e = a->rec_cache; e; e = e->next) {
- if (e->ty == id) return e->layout;
- }
- ABIRecordLayout* L = compute_record_layout(a, id);
+ hit = AbiRecLayoutMap_get(&a->rec_cache, id);
+ if (hit) return *hit;
+ L = compute_record_layout(a, id);
if (!L) return NULL;
- RecordLayoutCacheEntry* e = arena_new(a->c->tu, RecordLayoutCacheEntry);
- e->ty = id;
- e->layout = L;
- e->next = a->rec_cache;
- a->rec_cache = e;
+ AbiRecLayoutMap_set(&a->rec_cache, id, L);
return L;
}
@@ -240,17 +237,14 @@ ABIFuncInfo* abi_compute_func_info_generic(TargetABI* a, KitCgTypeId fn,
const ABIFuncInfo* abi_cg_func_info(TargetABI* a, KitCgTypeId fn_type) {
const CgType* fn = cg_type_get(a->c, fn_type);
+ ABIFuncInfo** hit;
+ ABIFuncInfo* info;
if (!fn || fn->kind != KIT_CG_TYPE_FUNC) return NULL;
- for (FuncInfoCacheEntry* e = a->fn_cache; e; e = e->next) {
- if (e->fn == fn_type) return e->info;
- }
- ABIFuncInfo* info = a->vt->compute_func_info(a, fn_type);
+ hit = AbiFnInfoMap_get(&a->fn_cache, fn_type);
+ if (hit) return *hit;
+ info = a->vt->compute_func_info(a, fn_type);
if (!info) return NULL;
- FuncInfoCacheEntry* e = arena_new(a->c->tu, FuncInfoCacheEntry);
- e->fn = fn_type;
- e->info = info;
- e->next = a->fn_cache;
- a->fn_cache = e;
+ AbiFnInfoMap_set(&a->fn_cache, fn_type, info);
return info;
}
@@ -287,13 +281,16 @@ void abi_init(TargetABI* a, Compiler* c) {
memset(a, 0, sizeof *a);
a->c = c;
a->vt = select_vtable(c);
+ /* The cached values stay on c->tu (per-TU arena); only the index lives on the
+ * compiler heap, freed in abi_fini. */
+ AbiFnInfoMap_init(&a->fn_cache, (Heap*)c->ctx->heap);
+ AbiRecLayoutMap_init(&a->rec_cache, (Heap*)c->ctx->heap);
}
void abi_fini(TargetABI* a) {
- /* Arena-backed; nothing to release. */
if (!a) return;
- a->fn_cache = NULL;
- a->rec_cache = NULL;
+ AbiFnInfoMap_fini(&a->fn_cache);
+ AbiRecLayoutMap_fini(&a->rec_cache);
a->vt = NULL;
a->c = NULL;
}
diff --git a/src/abi/abi_internal.h b/src/abi/abi_internal.h
@@ -2,6 +2,7 @@
#define KIT_ABI_INTERNAL_H
#include "abi/abi.h"
+#include "core/hashmap.h"
/* Internal: per-ABI dispatch table.
*
@@ -49,26 +50,21 @@ const ABIVtable* abi_vtable_lookup(KitArchKind arch, KitObjFmt obj);
* TU can reach into the per-TU caches via TargetABI*. abi.c owns the
* cache plumbing; the per-ABI TUs only allocate ABIFuncInfo / record
* builders out of c->tu. */
-typedef struct FuncInfoCacheEntry FuncInfoCacheEntry;
-typedef struct RecordLayoutCacheEntry RecordLayoutCacheEntry;
-struct FuncInfoCacheEntry {
- KitCgTypeId fn;
- ABIFuncInfo* info;
- FuncInfoCacheEntry* next;
-};
-
-struct RecordLayoutCacheEntry {
- KitCgTypeId ty;
- ABIRecordLayout* layout;
- RecordLayoutCacheEntry* next;
-};
+/* Per-(function/record) ABI-info caches, keyed by the CgTypeId. A type id is
+ * always nonzero for a real lookup (cg_type_get(0) fails before the cache), so
+ * 0 is a safe empty-slot sentinel. O(1) probe replaces what were linearly
+ * scanned linked lists — O(#distinct types) per query, i.e. O(n^2) over a
+ * type-heavy TU. The cached values stay arena-allocated (per-TU lifetime); only
+ * the index structure lives on the compiler heap and is freed at abi_fini. */
+KIT_HASHMAP_DEFINE(AbiFnInfoMap, u32, ABIFuncInfo*, hash_u32);
+KIT_HASHMAP_DEFINE(AbiRecLayoutMap, u32, ABIRecordLayout*, hash_u32);
struct TargetABI {
Compiler* c;
const ABIVtable* vt;
- FuncInfoCacheEntry* fn_cache;
- RecordLayoutCacheEntry* rec_cache;
+ AbiFnInfoMap fn_cache;
+ AbiRecLayoutMap rec_cache;
};
/* Shared classifier primitives implemented in abi.c. The byte-identical
diff --git a/src/cg/type.c b/src/cg/type.c
@@ -1,5 +1,6 @@
#include "arch/arch.h"
#include "cg/internal.h"
+#include "core/hashmap.h"
#include "obj/obj.h"
typedef enum CgApiTypeKind {
@@ -31,6 +32,9 @@ typedef struct CgApiType {
* the former pad, so the entry size is unchanged. */
u8 cached_class;
u8 pad[1];
+ /* This entry's own type id (set by type_alloc). Lets a structural hashset of
+ * CgApiType* recover the id without maintaining a reverse index. */
+ KitCgTypeId self_id;
} CgApiType;
/* High bit of CgApiType.cached_class: set once the class has been computed, so
@@ -39,9 +43,38 @@ typedef struct CgApiType {
SEGVEC_DEFINE(CgApiTypes, CgApiType, CG_API_TYPE_SEG_SHIFT);
+/* Structural dedup of derived ptr/array types, O(1) instead of a linear scan of
+ * the whole type table on every derivation (which made each derived-type use
+ * O(#types) — the dominant frontend hotspot on type-heavy input like sqlite).
+ * The key packs the structural identity into a u64: ptr = (pointee<<32)|addr_sp,
+ * array = (elem<<32)|count. Both component high halves (pointee/elem) are real
+ * type ids, never KIT_CG_TYPE_NONE (0), so the packed key is always nonzero and
+ * 0 is a safe empty-slot sentinel. Value is the interned KitCgTypeId. */
+static inline u64 cg_ptr_key(KitCgTypeId pointee, u32 address_space) {
+ return ((u64)pointee << 32) | (u64)address_space;
+}
+static inline u64 cg_array_key(KitCgTypeId elem, u64 count) {
+ return ((u64)elem << 32) | (count & 0xffffffffu);
+}
+KIT_HASHMAP_DEFINE(CgPtrMap, u64, KitCgTypeId, hash_u64);
+KIT_HASHMAP_DEFINE(CgArrayMap, u64, KitCgTypeId, hash_u64);
+
+/* Function types have a structural key (result + params + variadic + conv) that
+ * a scalar hashmap can't express, so dedup them through a structural hashset of
+ * the stored CgApiType* (SEGVEC entries have stable addresses). The callbacks
+ * are defined further down (after the shared result/param comparators); forward
+ * declarations let the set be defined here, before CgApiState embeds it. */
+static u32 cg_func_hash(CgApiType* const e);
+static int cg_func_eq(CgApiType* const a, CgApiType* const b);
+KIT_HASHSET_DEFINE(CgFuncSet, CgApiType*, cg_func_hash, cg_func_eq);
+
typedef struct CgApiState {
Heap* heap;
CgApiTypes types;
+ /* Structural dedup indexes for derived ptr/array/func types (see above). */
+ CgPtrMap ptr_index;
+ CgArrayMap array_index;
+ CgFuncSet func_index;
CgType builtins[KIT_CG_BUILTIN_COUNT];
/* Packed API_TYPE_CLASS_* per builtin, precomputed at init so the hottest
* operand types (i32/i64/f64/ptr/...) classify with a single indexed load. */
@@ -78,10 +111,6 @@ static KitCgTypeId user_id_from_index(u32 index) {
return type_id_from_tuple(raw_seg + CG_API_TYPE_USER_SEG_BIAS, off);
}
-static KitCgTypeId type_id_for_user_index(u32 index) {
- return user_id_from_index(index);
-}
-
static u64 cg_align_to(u64 n, u32 align) {
u64 a = align ? (u64)align : 1u;
return ((n + a - 1u) / a) * a;
@@ -288,6 +317,9 @@ static CgApiState* cg_api_get(Compiler* c) {
memset(s, 0, sizeof(*s));
s->heap = h;
CgApiTypes_init(&s->types, h);
+ CgPtrMap_init(&s->ptr_index, h);
+ CgArrayMap_init(&s->array_index, h);
+ CgFuncSet_init(&s->func_index, h);
c->cg_api = s;
c->cg_api_free = cg_api_fini;
cg_api_init_builtins(c, s);
@@ -421,39 +453,28 @@ static CgApiType* type_alloc(Compiler* c, KitCgTypeId* id_out) {
if (!e) return NULL;
*id_out = user_id_from_index(index);
if (*id_out == KIT_CG_TYPE_NONE) return NULL;
+ e->self_id = *id_out;
return e;
}
static KitCgTypeId find_ptr_type_id(Compiler* c, KitCgTypeId pointee,
u32 address_space) {
CgApiState* s;
- u32 n;
+ const KitCgTypeId* hit;
if (!c || !c->cg_api) return KIT_CG_TYPE_NONE;
s = (CgApiState*)c->cg_api;
- n = CgApiTypes_count(&s->types);
- for (u32 i = 0; i < n; ++i) {
- CgApiType* e = CgApiTypes_at(&s->types, i);
- if (e && e->kind == CG_API_TYPE_PTR && e->base == pointee &&
- e->address_space == address_space)
- return type_id_for_user_index(i);
- }
- return KIT_CG_TYPE_NONE;
+ hit = CgPtrMap_get(&s->ptr_index, cg_ptr_key(pointee, address_space));
+ return hit ? *hit : KIT_CG_TYPE_NONE;
}
static KitCgTypeId find_array_type_id(Compiler* c, KitCgTypeId elem,
u64 count) {
CgApiState* s;
- u32 n;
+ const KitCgTypeId* hit;
if (!c || !c->cg_api) return KIT_CG_TYPE_NONE;
s = (CgApiState*)c->cg_api;
- n = CgApiTypes_count(&s->types);
- for (u32 i = 0; i < n; ++i) {
- CgApiType* e = CgApiTypes_at(&s->types, i);
- if (e && e->kind == CG_API_TYPE_ARRAY && e->base == elem &&
- e->array_count == count)
- return type_id_for_user_index(i);
- }
- return KIT_CG_TYPE_NONE;
+ hit = CgArrayMap_get(&s->array_index, cg_array_key(elem, count));
+ return hit ? *hit : KIT_CG_TYPE_NONE;
}
static int cg_params_eq(const KitCgFuncParam* a, const KitCgFuncParam* b,
@@ -471,25 +492,45 @@ static int cg_result_eq(const KitCgFuncResult* a, const KitCgFuncResult* b) {
memcmp(&a->attrs, &b->attrs, sizeof(a->attrs)) == 0;
}
+/* Structural hash/eq over a function type's identity — the same fields the old
+ * linear scan compared. Only CG_API_TYPE_FUNC entries enter the set, so neither
+ * callback re-checks kind. The result/param attrs are compared (not hashed):
+ * fewer hash inputs just means eq resolves the (rare) collision. */
+static u32 cg_func_hash(CgApiType* const e) {
+ u32 h = 2166136261u;
+ h = (h ^ (u32)e->count) * 16777619u;
+ h = (h ^ (u32)e->abi_variadic) * 16777619u;
+ h = (h ^ (u32)e->call_conv) * 16777619u;
+ h = (h ^ (u32)e->result.type) * 16777619u;
+ for (u32 i = 0; i < e->count; ++i)
+ h = (h ^ (u32)e->params[i].type) * 16777619u;
+ return h;
+}
+
+static int cg_func_eq(CgApiType* const a, CgApiType* const b) {
+ if (a->count != b->count) return 0;
+ if (a->abi_variadic != b->abi_variadic) return 0;
+ if (a->call_conv != b->call_conv) return 0;
+ if (!cg_result_eq(&a->result, &b->result)) return 0;
+ if (a->count && !cg_params_eq(a->params, b->params, a->count)) return 0;
+ return 1;
+}
+
static KitCgTypeId find_func_type_id(Compiler* c, KitCgFuncSig sig) {
CgApiState* s;
- u32 n;
+ CgApiType probe;
+ CgApiType* hit;
if (!c || !c->cg_api) return KIT_CG_TYPE_NONE;
s = (CgApiState*)c->cg_api;
- n = CgApiTypes_count(&s->types);
- for (u32 i = 0; i < n; ++i) {
- CgApiType* e = CgApiTypes_at(&s->types, i);
- if (!e || e->kind != CG_API_TYPE_FUNC) continue;
- if (e->count != sig.nparams) continue;
- if (e->abi_variadic != (sig.abi_variadic != 0)) continue;
- if (e->call_conv != sig.call_conv) continue;
- if (!cg_result_eq(&e->result, &sig.result)) continue;
- if (sig.nparams && !cg_params_eq(e->params, sig.params, sig.nparams)) {
- continue;
- }
- return type_id_for_user_index(i);
- }
- return KIT_CG_TYPE_NONE;
+ memset(&probe, 0, sizeof probe);
+ probe.kind = CG_API_TYPE_FUNC;
+ probe.count = sig.nparams;
+ probe.abi_variadic = (u8)(sig.abi_variadic != 0);
+ probe.call_conv = sig.call_conv;
+ probe.result = sig.result;
+ probe.params = sig.params;
+ hit = CgFuncSet_find(&s->func_index, &probe);
+ return hit ? hit->self_id : KIT_CG_TYPE_NONE;
}
static CgApiType* api_type_from_id(Compiler* c, KitCgTypeId id) {
@@ -767,6 +808,8 @@ KitCgTypeId kit_cg_type_ptr(KitCompiler* c, KitCgTypeId pointee,
if (!cg_type_set_ptr(c, e, pointee, address_space)) {
return KIT_CG_TYPE_NONE;
}
+ CgPtrMap_set(&((CgApiState*)c->cg_api)->ptr_index,
+ cg_ptr_key(pointee, address_space), id);
return id;
}
@@ -785,6 +828,8 @@ KitCgTypeId kit_cg_type_array(KitCompiler* c, KitCgTypeId elem,
if (!cg_type_set_array(c, e, elem, count)) {
return KIT_CG_TYPE_NONE;
}
+ CgArrayMap_set(&((CgApiState*)c->cg_api)->array_index,
+ cg_array_key(elem, count), id);
return id;
}
@@ -895,6 +940,7 @@ KitCgTypeId kit_cg_type_func(KitCompiler* c, KitCgFuncSig sig) {
if (!cg_type_set_func(c, e, sig, copied)) {
return KIT_CG_TYPE_NONE;
}
+ CgFuncSet_add(&((CgApiState*)c->cg_api)->func_index, e);
return id;
}
@@ -1109,6 +1155,9 @@ void cg_api_fini(Compiler* c) {
if (!c || !c->cg_api) return;
s = (CgApiState*)c->cg_api;
CgApiTypes_fini(&s->types);
+ CgPtrMap_fini(&s->ptr_index);
+ CgArrayMap_fini(&s->array_index);
+ CgFuncSet_fini(&s->func_index);
s->heap->free(s->heap, s, sizeof(*s));
c->cg_api = NULL;
c->cg_api_free = NULL;
