commit 54c8a075d684c8901b0dd5e69625569d0a3f8137
parent 652fef0cc277f799a66c21f463aa6a56fd1e8d93
Author: Ryan Sepassi <rsepassi@gmail.com>
Date: Thu, 14 May 2026 17:33:36 -0700
link: make section grouping linear
Diffstat:
1 file changed, 66 insertions(+), 22 deletions(-)
diff --git a/src/link/link_layout.c b/src/link/link_layout.c
@@ -95,6 +95,8 @@ typedef struct SecRef {
LinkSectionId link_sec_id;
} SecRef;
+#define PLACE_NONE ((u32)~0u)
+
/* Within a bucket, input sections sharing a name are placed contiguously
* — the standard "merge sections by name" rule. Without this the .init
* prologue from crti.o and the matching epilogue from crtn.o (both in
@@ -103,22 +105,38 @@ typedef struct SecRef {
*
* 1. Build a flat list of (input_idx, obj_sec_id) for kept+live
* sections.
- * 2. For each bucket, do a stable group-by-name pass over the list:
- * take the first ungrouped section in input order, claim every
- * later same-name+same-bucket section in input order, lay out the
- * whole group adjacent. Then move to the next ungrouped section.
- * 3. Different-name groups appear in first-occurrence order.
- *
- * O(N²) on section count, fine for our N. */
+ * 2. While collecting, append each section to an O(1)-expected lookup
+ * keyed by (bucket, name). The group array is append-only, so group
+ * order is still first occurrence; each group's linked list preserves
+ * input order.
+ * 3. Lay out groups in first-occurrence order.
+ */
typedef struct PlaceEntry {
u32 input_idx;
ObjSecId obj_sec_id;
Sym name;
SegBucket bucket;
- u8 placed;
- u8 pad[3];
+ u32 next;
} PlaceEntry;
+typedef struct PlaceGroup {
+ u32 head;
+ u32 tail;
+} PlaceGroup;
+
+static inline u32 place_group_hash_(u64 key) { return hash_u64(key); }
+HASHMAP_DEFINE(PlaceGroupHash, u64, u32, place_group_hash_);
+
+static u64 place_group_key(Sym name, SegBucket bucket) {
+ return (((u64)name + 1u) << 3) | ((u64)bucket + 1u);
+}
+
+static u32 place_group_hash_cap(u32 n) {
+ u32 cap = CFREE_HASHMAP_INIT_CAP;
+ while (cap < 0x80000000u && (cap - cap / 4u) < n) cap <<= 1;
+ return cap;
+}
+
static void link_layout_sections_scripted(Linker* l, LinkImage* img,
const GcLive* g);
@@ -152,21 +170,54 @@ void link_layout_sections(Linker* l, LinkImage* img, const GcLive* g) {
total_kept ? (PlaceEntry*)h->alloc(h, sizeof(*entries) * total_kept,
_Alignof(PlaceEntry))
: NULL;
+ PlaceGroup* groups =
+ total_kept ? (PlaceGroup*)h->alloc(h, sizeof(*groups) * total_kept,
+ _Alignof(PlaceGroup))
+ : NULL;
+ PlaceGroupHash group_map;
+ u32 ngroups = 0;
if (total_kept && !entries)
compiler_panic(img->c, no_loc(), "link: oom on placement entries");
+ if (total_kept && !groups)
+ compiler_panic(img->c, no_loc(), "link: oom on placement groups");
+ if (total_kept) {
+ PlaceGroupHash_init_cap(&group_map, h, place_group_hash_cap(total_kept));
+ if (!group_map.slots)
+ compiler_panic(img->c, no_loc(), "link: oom on placement group map");
+ }
{
u32 e = 0;
for (ii = 0; ii < LinkInputs_count(&l->inputs); ++ii) {
ObjBuilder* ob = LinkInputs_at(&l->inputs, ii)->obj;
for (j = 1; j < obj_section_count(ob); ++j) {
const Section* s = obj_section_get(ob, j);
+ u64 key;
+ u32* hit;
+ u32 group_idx;
if (!s || !link_section_kept(s) || !link_gc_live_get(g, ii, j))
continue;
entries[e].input_idx = ii;
entries[e].obj_sec_id = j;
entries[e].name = s->name;
entries[e].bucket = link_bucket_for(s->flags);
- entries[e].placed = 0;
+ entries[e].next = PLACE_NONE;
+
+ key = place_group_key(entries[e].name, entries[e].bucket);
+ hit = PlaceGroupHash_get(&group_map, key);
+ if (hit) {
+ group_idx = *hit - 1u;
+ } else {
+ group_idx = ngroups++;
+ groups[group_idx].head = PLACE_NONE;
+ groups[group_idx].tail = PLACE_NONE;
+ PlaceGroupHash_set(&group_map, key, group_idx + 1u);
+ }
+ if (groups[group_idx].tail == PLACE_NONE) {
+ groups[group_idx].head = e;
+ } else {
+ entries[groups[group_idx].tail].next = e;
+ }
+ groups[group_idx].tail = e;
++e;
}
}
@@ -183,18 +234,10 @@ void link_layout_sections(Linker* l, LinkImage* img, const GcLive* g) {
/* Pass 2: place sections, grouped by name within each bucket and
* in first-occurrence order across groups. */
- for (u32 i = 0; i < total_kept; ++i) {
- if (entries[i].placed) continue;
-
- Sym group_name = entries[i].name;
- SegBucket bucket = entries[i].bucket;
-
- /* Walk the remaining list in input order; each match in the
- * same bucket+name lays out adjacent. */
- for (u32 k = i; k < total_kept; ++k) {
+ for (u32 gi = 0; gi < ngroups; ++gi) {
+ for (u32 k = groups[gi].head; k != PLACE_NONE; k = entries[k].next) {
PlaceEntry* pe = &entries[k];
- if (pe->placed) continue;
- if (pe->bucket != bucket || pe->name != group_name) continue;
+ SegBucket bucket = pe->bucket;
ObjBuilder* ob = LinkInputs_at(&l->inputs, pe->input_idx)->obj;
InputMap* m = &img->input_maps[pe->input_idx];
@@ -236,10 +279,11 @@ void link_layout_sections(Linker* l, LinkImage* img, const GcLive* g) {
ls->sem = s->sem;
ls->segment_id = (LinkSegmentId)(bucket + 1u); /* 1..3 sentinel */
m->section[pe->obj_sec_id] = lsid;
- pe->placed = 1;
}
}
+ if (total_kept) PlaceGroupHash_fini(&group_map);
+ if (groups) h->free(h, groups, sizeof(*groups) * total_kept);
if (entries) h->free(h, entries, sizeof(*entries) * total_kept);
/* Materialize one LinkSegment per non-empty bucket, then assign
