commit d9902a7ea9f62a06393ee58db352fe8f635e88de
parent f97f2c08ba699563f1c112562e79ee6d6d1a93c1
Author: Ryan Sepassi <rsepassi@gmail.com>
Date: Mon, 15 Jun 2026 23:32:49 -0700
opt: hot-slot-low frame ordering at O1 (O1.md W1.0)
Diffstat:
6 files changed, 236 insertions(+), 5 deletions(-)
diff --git a/mk/test.mk b/mk/test.mk
@@ -859,7 +859,7 @@ test-macho: lib $(TEST_RT_DEP) $(ROUNDTRIP_BIN_MACHO) $(LINK_EXE_RUNNER) $(JIT_R
OPT_TEST_BIN = build/test/cg_ir_lower_test
TINY_INLINE_TEST_BIN = build/test/tiny_inline_test
-test-opt: bin $(OPT_TEST_BIN) test-opt-tiny-inline test-opt-inline test-opt-zero-arg test-opt-static-prune-aa64 test-opt-aa64-tail test-opt-x64-win-tail-sret test-opt-prologue-tier test-opt-whole-program-inline test-opt-lto-phase1 test-opt-redundant-copy-ext test-opt-redundant-frame-sub test-opt-o1-branch-cleanup
+test-opt: bin $(OPT_TEST_BIN) test-opt-tiny-inline test-opt-inline test-opt-zero-arg test-opt-static-prune-aa64 test-opt-aa64-tail test-opt-x64-win-tail-sret test-opt-prologue-tier test-opt-whole-program-inline test-opt-lto-phase1 test-opt-redundant-copy-ext test-opt-redundant-frame-sub test-opt-o1-branch-cleanup test-opt-hot-slot-order
$(OPT_TEST_BIN)
@@ -881,6 +881,12 @@ test-opt-redundant-frame-sub: bin
test-opt-o1-branch-cleanup: bin
@KIT=$(abspath $(BIN)) bash test/opt/o1_branch_cleanup.sh
+# Structural disasm check: hot-slot-low frame ordering keeps the hottest spill
+# slots in cheap displacement range (x64 disp8, rv64 imm12 single-instruction).
+.PHONY: test-opt-hot-slot-order
+test-opt-hot-slot-order: bin
+ @KIT=$(abspath $(BIN)) bash test/opt/hot_slot_order.sh
+
test-opt-tiny-inline: bin $(TINY_INLINE_TEST_BIN)
$(TINY_INLINE_TEST_BIN)
diff --git a/src/arch/native_target.h b/src/arch/native_target.h
@@ -45,6 +45,12 @@ typedef struct NativeFrameSlotDesc {
u32 size;
u32 align;
i32 fixed_offset;
+ /* Spill-traffic priority (O1.md W1.0), copied from IRFrameSlot.priority. The
+ * known-frame emitter (opt_emit_native) presents slot descs to the backend in
+ * descending-priority order, so the bump allocator (native_frame_slot_alloc)
+ * gives the hottest spills the smallest final displacement. The backend itself
+ * ignores this field — it is purely an ordering signal for the emitter. */
+ u32 priority;
u8 kind; /* NativeFrameSlotKind */
u8 pad;
u16 flags; /* NativeFrameSlotFlag */
diff --git a/src/opt/ir.h b/src/opt/ir.h
@@ -474,6 +474,15 @@ typedef struct IRFrameSlot {
SrcLoc loc;
u32 size;
u32 align;
+ /* Spill-traffic priority (O1.md W1.0). Aggregated from the allocator's final
+ * spill-slot assignment: the saturating sum of the spill cost of every
+ * coalesce group assigned to this (possibly reused) slot, where the per-group
+ * cost is `2*use_freq + def_freq + live_across_call_freq + live_block_freq`
+ * (pass_live.c). The known-frame emitter presents slots to the backend in
+ * descending-priority order so the hottest spills get the smallest final frame
+ * displacement (disp8 on x64, inside the scaled reach on aa64, inside the
+ * +/-2KB imm12 window on rv64). 0 for homed/address-taken locals (v1). */
+ u32 priority;
u8 kind; /* FrameSlotKind */
u8 pad;
u16 flags; /* FrameSlotFlag */
diff --git a/src/opt/pass_lower.c b/src/opt/pass_lower.c
@@ -588,6 +588,21 @@ static FrameSlot spill_slot_for(Func* f, PReg v) {
return f->preg_info[v].spill_slot;
}
+/* Aggregate one coalesce group's spill-traffic cost onto its final spill slot's
+ * IRFrameSlot.priority (O1.md W1.0). Called from the allocator's final
+ * assignment, including the slot-reuse path, so a slot shared by several
+ * non-overlapping groups accumulates the traffic of all of them. Saturating sum:
+ * priority is purely an ordering key for the known-frame emitter (hot slot ->
+ * smallest displacement), so wrap-free saturation at u32 max is sufficient and
+ * keeps the hottest slots ordered ahead of cold ones. Slots outside [1,
+ * nframe_slots] (none today) are ignored defensively. */
+static void spill_slot_add_priority(Func* f, FrameSlot slot, u32 cost) {
+ if (slot == FRAME_SLOT_NONE || slot > f->nframe_slots || cost == 0) return;
+ IRFrameSlot* s = &f->frame_slots[slot - 1u];
+ u32 sum = s->priority + cost;
+ s->priority = sum < s->priority ? 0xffffffffu : sum; /* saturate on overflow */
+}
+
static u32 hard_loc_bit(u8 cls, Reg r) { return ((u32)cls * 32u) + (u32)r; }
typedef struct OptAllocGroupInfo {
@@ -990,7 +1005,8 @@ static void alloc_assign_group_hard(Func* f, OptAllocator* a,
}
static void alloc_assign_group_stack(Func* f, OptAllocator* a,
- const OptLiveRangeSet* ranges, PReg root) {
+ const OptLiveRangeSet* ranges, PReg root,
+ u32 group_priority) {
/* Try to reuse an existing stack slot whose bit is clear in conflict_locs
* and whose frame slot is compatible. The conflict_locs scratch must
* already be populated for `root` by the caller. */
@@ -1009,6 +1025,11 @@ static void alloc_assign_group_stack(Func* f, OptAllocator* a,
* conflict_locs (callers don't reuse it after this). */
}
FrameSlot slot = a->stack_slots[stack_idx];
+ /* W1.0: accumulate this group's spill-traffic onto the slot's priority. This
+ * is the FINAL assignment, and a slot reused for several non-overlapping
+ * groups sums all of their traffic — so the emitter's hot-slot-low ordering
+ * sees the slot's total demand, not just the first group that created it. */
+ spill_slot_add_priority(f, slot, group_priority);
for (PReg v = 1; v < opt_reg_count(f); ++v) {
if (ranges->first_range_by_preg[v] == OPT_RANGE_NONE) continue;
if (!alloc_group_member(f, root, v)) continue;
@@ -1227,7 +1248,10 @@ static void opt_assign_ranges(Func* f, const OptLiveRangeSet* ranges,
compiler_panic(f->c, loc,
"opt regalloc: no hard register satisfies asm constraint");
} else {
- alloc_assign_group_stack(f, a, ranges, v);
+ /* gi.spill_cost is the group's aggregated spill-traffic metric
+ * (alloc_group_info sums each member's frequency/spill_cost). Thread it to
+ * the slot so the known-frame emitter can order hot slots low (W1.0). */
+ alloc_assign_group_stack(f, a, ranges, v, gi.spill_cost);
}
}
diff --git a/src/opt/pass_native_emit.c b/src/opt/pass_native_emit.c
@@ -1524,10 +1524,65 @@ static void plan_frame(NativeEmitCtx* e, const CGFuncDesc* fd) {
d->loc = s->loc;
d->size = s->size;
d->align = s->align;
+ d->priority = s->priority;
d->kind = s->kind;
d->flags = s->flags;
}
}
+ /* W1.0 hot-slot-low ordering. The backend's known-frame path bump-allocates
+ * each body slot in the order it is presented (cum_off is monotonic, see
+ * native_frame_slot_alloc), so slots presented first get the smallest final
+ * frame displacement. Present the body slots in DESCENDING priority order so
+ * the hottest spills land low: disp8 on x64 (-4 bytes/access), inside the
+ * scaled reach on aa64, inside the +/-2KB imm12 window on rv64.
+ *
+ * `order[k]` is the original slot index now presented at position k. Fixed-
+ * offset slots keep their original positions (their displacement is not
+ * order-derived); the remaining slots are stable-sorted by descending priority
+ * with an original-index tie-break (so the sort is deterministic and, among
+ * equal priorities, byte-stable). The native slot the backend returns for
+ * position k therefore belongs to original IR slot `order[k]`, and the slot_map
+ * is written back through `order` so e->slot_map[ir_id] stays exact -- a
+ * transposed map silently miscompiles every spill, so it is asserted below. */
+ u32 nfs = e->f->nframe_slots;
+ u32* slot_order = NULL; /* slot_order[k] = original IR slot index at position k */
+ if (nfs > 1u) {
+ u32* order = arena_array(e->f->arena, u32, nfs);
+ u32* movable = arena_array(e->f->arena, u32, nfs);
+ u32 nmovable = 0;
+ for (u32 i = 0; i < nfs; ++i) {
+ order[i] = i; /* fixed slots stay pinned at their original index */
+ if (!(slots[i].flags & NATIVE_FRAME_SLOT_FIXED_OFFSET))
+ movable[nmovable++] = i;
+ }
+ /* Stable descending-priority sort of the movable indices (insertion sort:
+ * nslots is small per function and this is off the per-instruction path; if
+ * a profile shows it material, swap in a radix over the integer priority --
+ * see O1.md W1.0 "Linear?"). Insertion sort is naturally stable, preserving
+ * original order among equal priorities. */
+ for (u32 i = 1; i < nmovable; ++i) {
+ u32 cur = movable[i];
+ u32 cur_pri = slots[cur].priority;
+ u32 j = i;
+ while (j > 0 && slots[movable[j - 1]].priority < cur_pri) {
+ movable[j] = movable[j - 1];
+ --j;
+ }
+ movable[j] = cur;
+ }
+ /* Drop the sorted movable indices back into the non-fixed positions. */
+ u32 mi = 0;
+ for (u32 k = 0; k < nfs; ++k)
+ if (!(slots[k].flags & NATIVE_FRAME_SLOT_FIXED_OFFSET))
+ order[k] = movable[mi++];
+ /* Reorder the desc array in place via a scratch copy so frame.slots is the
+ * contiguous, permuted view the backend iterates. */
+ NativeFrameSlotDesc* ordered =
+ arena_array(e->f->arena, NativeFrameSlotDesc, nfs);
+ for (u32 k = 0; k < nfs; ++k) ordered[k] = slots[order[k]];
+ slot_order = order;
+ slots = ordered;
+ }
frame.slots = slots;
frame.nslots = e->f->nframe_slots;
frame.max_outgoing = max_outgoing;
@@ -1542,8 +1597,40 @@ static void plan_frame(NativeEmitCtx* e, const CGFuncDesc* fd) {
frame.nasm_clobbers = nasm_clob;
frame.asm_clobber_abi_sets = asm_clobber_abi_sets;
t->func_begin_known_frame(t, fd, &frame, out_slots);
- for (u32 i = 0; i < e->f->nframe_slots; ++i)
- e->slot_map[e->f->frame_slots[i].id] = out_slots[i];
+ /* Map each backend native slot (returned for presentation position k) back to
+ * its original IR frame slot id. With ordering, position k holds IR slot
+ * order[k]; without it (nfs<=1 or no reorder), position k == IR slot k. */
+ for (u32 k = 0; k < e->f->nframe_slots; ++k) {
+ u32 ir_idx = slot_order ? slot_order[k] : k;
+ e->slot_map[e->f->frame_slots[ir_idx].id] = out_slots[k];
+ }
+#ifndef NDEBUG
+ /* The slot_map must stay an exact 1:1 of IR frame slots to the native slots
+ * the backend returned -- a transposed/dropped map silently miscompiles every
+ * spill. The actual native slot ids are NOT bounded by nframe_slots (the
+ * backend reserves callee-saves / entry-saves / scratch around the body slots,
+ * so body native ids are an arbitrary distinct block), so verify the real
+ * correctness condition instead: `order` is a permutation of [0, nfs) -- i.e.
+ * every IR frame slot is presented exactly once -- and each presented position
+ * received a non-NONE native slot. Both are O(nslots) (seen array sized by the
+ * IR index domain), off the per-instruction path. With identity ordering this
+ * is vacuously the original code's invariant. */
+ if (nfs) {
+ u8* seen = arena_zarray(e->f->arena, u8, nfs);
+ for (u32 k = 0; k < nfs; ++k) {
+ u32 ir_idx = slot_order ? slot_order[k] : k;
+ if (ir_idx >= nfs || seen[ir_idx])
+ compiler_panic(e->c, (SrcLoc){0, 0, 0},
+ "opt W1.0: slot order is not a permutation at pos %u",
+ (unsigned)k);
+ seen[ir_idx] = 1u;
+ if (out_slots[k] == NATIVE_FRAME_SLOT_NONE)
+ compiler_panic(e->c, (SrcLoc){0, 0, 0},
+ "opt W1.0: backend returned no native slot for pos %u",
+ (unsigned)k);
+ }
+ }
+#endif
}
void opt_emit_native(Compiler* c, Func* f, NativeTarget* target) {
diff --git a/test/opt/hot_slot_order.sh b/test/opt/hot_slot_order.sh
@@ -0,0 +1,99 @@
+#!/usr/bin/env bash
+# Structural check for W1.0 hot-slot-low frame ordering (doc/plan/O1.md #### W1.0).
+#
+# At -O1 the frame is fully known before the body is emitted, so the optimizer
+# presents the body spill slots to the backend in DESCENDING spill-traffic
+# priority order (pass_native_emit.c). The bump allocator (native_frame_slot_alloc)
+# then gives the hottest spills the smallest final displacement -- which is the
+# cheapest to encode on every arch:
+#
+# x64 : disp8 [rbp - k] (1 disp byte, -128..127) vs disp32 (4 disp bytes).
+# rv64 : single-instruction `ld/sd off(s0)` while off fits the +/-2KB imm12
+# window; a far slot needs a 3-instruction `lui; addiw; add; ld 0(t)`
+# build.
+#
+# The probe is a function with 16 hot accumulators updated EVERY loop iteration
+# (so several must spill to the frame and they carry by far the highest spill
+# cost) plus ~280 cold scalars that survive to the end. The cold pile pushes the
+# total frame WELL past x64 disp8 (128B) and past rv64's imm12 window (2KB), so
+# the layout MUST choose which slots get the cheap low offsets. W1.0 makes that
+# choice the hot accumulators: the hot loop body then addresses them with the
+# short/single-instruction form while the cold tail takes the far offsets.
+#
+# Gate is correctness, not byte-identity (W1.0 deliberately reorders slots); this
+# guard pins the resulting addressing shape on x64 + rv64 (the arches where the
+# doc expects a measurable win; aa64 is mostly subsumed by W1.1).
+set -euo pipefail
+
+ROOT="$(cd "$(dirname "$0")/../.." && pwd)"
+KIT="${KIT:-$ROOT/build/kit}"
+WORK="$ROOT/build/test/opt/hot_slot_order"
+mkdir -p "$WORK"
+
+SRC="$WORK/case.c"
+{
+ echo 'typedef unsigned long long u64;'
+ echo 'extern u64 sink(u64 *);'
+ echo 'u64 hot_loop(const u64 *in, int n) {'
+ # 16 hot accumulators (more than the GP register file) -> the allocator must
+ # spill several; all carry the highest spill cost (touched every iteration).
+ for i in $(seq 0 15); do echo " u64 h$i = in[$i];"; done
+ # ~280 cold scalars -> inflates the frame past disp8 (128B) and imm12 (2KB).
+ for i in $(seq 0 279); do echo " u64 k$i = in[$((i % 64))] + ${i}u;"; done
+ echo ' for (int i = 0; i < n; i++) {'
+ echo ' u64 x = in[i & 63];'
+ for i in $(seq 0 15); do echo " h$i = (h$i ^ x) + h$(((i + 1) % 16));"; done
+ echo ' }'
+ # Keep the cold scalars live across the loop (low priority, far offsets).
+ echo " u64 ks[280];"
+ for i in $(seq 0 279); do echo " ks[$i] = k$i;"; done
+ echo ' sink(ks);'
+ printf ' return'
+ for i in $(seq 0 15); do printf ' h%d ^' "$i"; done
+ echo ' 0;'
+ echo '}'
+} > "$SRC"
+
+dump_for() { # $1 = -target triple, $2 = out tag
+ local triple="$1" tag="$2"
+ "$KIT" cc -target "$triple" -O1 -std=c11 -ffreestanding -nostdinc \
+ -I"$ROOT/rt/include" -c "$SRC" -o "$WORK/$tag.o" > "$WORK/$tag.cc.out" 2>&1 \
+ || { printf 'hot_slot_order FAILED: %s cc failed\n' "$tag" >&2
+ sed 's/^/ | /' "$WORK/$tag.cc.out" >&2; exit 1; }
+ "$KIT" objdump -d "$WORK/$tag.o" > "$WORK/$tag.dis" 2>&1
+}
+
+fail() {
+ printf 'hot_slot_order FAILED: %s\n' "$1" >&2
+ printf ' --- %s disassembly (head) ---\n' "${2:-}" >&2
+ [ -n "${2:-}" ] && sed -n '1,80p' "$WORK/$2.dis" | sed 's/^/ | /' >&2
+ exit 1
+}
+
+# ---- x64: hot accumulators must land in disp8 range -----------------------
+# Count frame accesses by displacement magnitude: disp8 = |off| <= 127, disp32
+# otherwise. A large frame (cold tail) guarantees disp32 accesses exist; W1.0
+# must also produce a healthy block of disp8 accesses -- the hot accumulators
+# the loop touches every iteration. (Without ordering the hot slots could be
+# pushed entirely into disp32, so a substantial disp8 count is the signal.)
+dump_for x86_64-macos x64
+x64_d8="$(grep -oE '\-?[0-9]+\(%rbp\)' "$WORK/x64.dis" | sed -E 's/\(%rbp\)//' \
+ | awk '{v=$1<0?-$1:$1} v<=127{n++} END{print n+0}')"
+x64_d32="$(grep -oE '\-?[0-9]+\(%rbp\)' "$WORK/x64.dis" | sed -E 's/\(%rbp\)//' \
+ | awk '{v=$1<0?-$1:$1} v>127{n++} END{print n+0}')"
+[ "$x64_d32" -gt 0 ] || fail "x64 frame not large enough (no disp32 access -- probe too small)" x64
+[ "$x64_d8" -ge 8 ] || fail "x64 hot slots not in disp8 range (disp8=$x64_d8 disp32=$x64_d32)" x64
+
+# ---- rv64: hot slots must stay single-instruction (inside imm12) ----------
+# A single-instruction frame access is `ld/sd reg, off(s0)`; a far slot needs a
+# `lui; addiw; add; ld 0(t)` build. The big frame guarantees `lui` far-slot
+# builds exist (cold tail past +/-2KB); W1.0 must keep the hot accumulators
+# single-instruction, so the count of direct `(s0)` accesses must dominate.
+dump_for riscv64-linux-gnu rv64
+rv_single="$(grep -cE '(ld|sd) [a-z0-9]+, -?[0-9]+\(s0\)' "$WORK/rv64.dis" || true)"
+rv_lui="$(grep -cE ' lui ' "$WORK/rv64.dis" || true)"
+[ "${rv_lui:-0}" -gt 0 ] || fail "rv64 frame not large enough (no lui far-slot build -- probe too small)" rv64
+[ "${rv_single:-0}" -ge 16 ] || fail "rv64 hot slots not single-instruction (single=$rv_single lui=$rv_lui)" rv64
+
+printf 'hot_slot_order: OK (x64 disp8=%s/disp32=%s, rv64 single=%s/lui=%s)\n' \
+ "$x64_d8" "$x64_d32" "$rv_single" "$rv_lui"
