commit 235a72c755e77fd64a69c25dc8f38201f9f10776
parent a8d7f4c28bb7c82d09f317d3517c305bb4bee9f9
Author: Ryan Sepassi <rsepassi@gmail.com>
Date: Tue, 16 Jun 2026 01:58:15 -0700
opt: local same-block redundant-load + CSE elimination at O1 (O1.md W5)
Diffstat:
3 files changed, 482 insertions(+), 2 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-hot-slot-order test-opt-o1-remat test-opt-aa64-x29-bottom test-opt-o1-coalesce test-opt-o1-switch-imm test-opt-o1-inline-cap test-opt-rv64-far-slot test-opt-o1-cmp-imm test-opt-o1-stack-dse
+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 test-opt-o1-remat test-opt-aa64-x29-bottom test-opt-o1-coalesce test-opt-o1-switch-imm test-opt-o1-inline-cap test-opt-rv64-far-slot test-opt-o1-cmp-imm test-opt-o1-stack-dse test-opt-o1-local-cse
$(OPT_TEST_BIN)
@@ -937,6 +937,12 @@ test-opt-o1-cmp-imm: bin
test-opt-o1-stack-dse: bin
@KIT=$(abspath $(BIN)) bash test/opt/o1_stack_dse.sh
+# Behavioral+structural check: same-block redundant-load/expression CSE reuses
+# the last load/compute, but never across a may-alias store, call, or volatile.
+.PHONY: test-opt-o1-local-cse
+test-opt-o1-local-cse: bin
+ @KIT=$(abspath $(BIN)) bash test/opt/o1_local_cse.sh
+
test-opt-tiny-inline: bin $(TINY_INLINE_TEST_BIN)
$(TINY_INLINE_TEST_BIN)
diff --git a/src/opt/pass_combine.c b/src/opt/pass_combine.c
@@ -405,6 +405,49 @@ typedef struct AddrCseEntry {
Operand addr; /* the address operand (OPK_LOCAL / OPK_GLOBAL) */
} AddrCseEntry;
+/* W5 (O1.md): local (same-block) redundant-load + pure-compute CSE. Two small
+ * most-recent-wins rings:
+ *
+ * - LOAD ring: the most-recently-loaded `{address, size, addr_space}` and the
+ * register that received the value. A later plain (non-observable,
+ * non-bit-field) IR_LOAD of the IDENTICAL address+shape, with the producer
+ * register still live and NO intervening memory write, is rewritten to an
+ * IR_COPY off the producer. Aliasing is the whole game: ANY memory write
+ * (inst_writes_memory: store/aggregate/atomic/call/asm/intrinsic) forgets
+ * the entire load ring in O(1), so a may-aliasing store between the two
+ * loads always preserves the reload. Volatile/atomic loads
+ * (opt_mem_observable) are never recorded or reused.
+ *
+ * - COMPUTE ring: the most-recent pure IR_BINOP/IR_UNOP `{op, operands}` and
+ * its destination register. A later identical pure compute whose inputs are
+ * unchanged since (and whose producer is still live) is rewritten to an
+ * IR_COPY off the producer. Pure computes touch no memory, so only register
+ * redefinitions/clobbers invalidate them (tracked via ctx->last_def, which a
+ * clobber barrier bumps for every register).
+ *
+ * Both rings are bounded → O(1) per inst → the pass stays linear. Each rewrite
+ * is the broader, map-based same-block form distinct from the adjacent
+ * store/load pairs opt_combine_compact_block already coalesces. */
+enum { COMBINE_LOAD_CSE_SLOTS = 8 };
+enum { COMBINE_COMPUTE_CSE_SLOTS = 8 };
+
+typedef struct LoadCseEntry {
+ i32 inst_idx; /* producing IR_LOAD index in this BB, -1 if empty */
+ Operand dst; /* the register that received the loaded value (OPK_REG) */
+ Operand addr; /* the load's address operand (OPK_INDIRECT/LOCAL/GLOBAL) */
+ u32 size; /* MemAccess size */
+ u16 addr_space;
+} LoadCseEntry;
+
+typedef struct ComputeCseEntry {
+ i32 inst_idx; /* producing IR_BINOP/IR_UNOP index in this BB, -1 if empty */
+ Operand dst; /* the result register (OPK_REG) */
+ u16 op; /* IROp (IR_BINOP / IR_UNOP) */
+ i64 sub; /* extra.imm = BinOp/UnOp selector */
+ Operand a; /* operand 1 */
+ Operand b; /* operand 2 (kind == 0 sentinel for a unary compute) */
+} ComputeCseEntry;
+
typedef struct CombineCtx {
Func* f;
Block* bl;
@@ -417,6 +460,11 @@ typedef struct CombineCtx {
/* W1a addr-of CSE ring (most-recent-wins). */
AddrCseEntry addr_cse[COMBINE_ADDR_CSE_SLOTS];
u32 addr_cse_next;
+ /* W5 local same-block load + pure-compute CSE rings (most-recent-wins). */
+ LoadCseEntry load_cse[COMBINE_LOAD_CSE_SLOTS];
+ u32 load_cse_next;
+ ComputeCseEntry compute_cse[COMBINE_COMPUTE_CSE_SLOTS];
+ u32 compute_cse_next;
/* W6 cmp-immediate tracking: the constant currently held by each integer
* hard register, if known. const_valid is a per-RC_INT-reg bit set when a
* reaching IR_LOAD_IMM defined that register and nothing since has redefined
@@ -435,6 +483,12 @@ static void ctx_reset(CombineCtx* ctx) {
for (u32 k = 0; k < COMBINE_ADDR_CSE_SLOTS; ++k)
ctx->addr_cse[k].inst_idx = -1;
ctx->addr_cse_next = 0;
+ for (u32 k = 0; k < COMBINE_LOAD_CSE_SLOTS; ++k)
+ ctx->load_cse[k].inst_idx = -1;
+ ctx->load_cse_next = 0;
+ for (u32 k = 0; k < COMBINE_COMPUTE_CSE_SLOTS; ++k)
+ ctx->compute_cse[k].inst_idx = -1;
+ ctx->compute_cse_next = 0;
ctx->const_valid = 0;
ctx->block_change_p = 0;
}
@@ -1387,6 +1441,232 @@ static int try_addr_of_cse(CombineCtx* ctx, Inst* in, i32 i) {
return 0;
}
+/* ---- Rewrite 8 (W5): local same-block redundant-load elimination ---- */
+
+/* Two load-address operands name the same address iff identical kind+payload.
+ * For an OPK_INDIRECT both the base, index, scale, AND offset must match; the
+ * register-unchanged-since check is applied separately by the caller. */
+static int same_load_addr_operand(const Operand* a, const Operand* b) {
+ if (a->kind != b->kind) return 0;
+ switch (a->kind) {
+ case OPK_LOCAL:
+ return a->v.frame_slot == b->v.frame_slot;
+ case OPK_GLOBAL:
+ return a->v.global.sym == b->v.global.sym &&
+ a->v.global.addend == b->v.global.addend;
+ case OPK_INDIRECT:
+ return a->v.ind.base == b->v.ind.base &&
+ a->v.ind.index == b->v.ind.index &&
+ a->v.ind.log2_scale == b->v.ind.log2_scale &&
+ a->v.ind.ofs == b->v.ind.ofs;
+ default:
+ return 0;
+ }
+}
+
+/* A plain, CSE-eligible IR_LOAD: dst is a register, address is a
+ * direct/indirect memory operand, and the access is neither observable
+ * (volatile/atomic) nor a bit-field rider. */
+static int load_is_cseable(const Inst* in) {
+ if ((IROp)in->op != IR_LOAD || in->nopnds < 2) return 0;
+ if (in->opnds[0].kind != OPK_REG) return 0;
+ const Operand* addr = &in->opnds[1];
+ /* W5 owns pointer-deref (OPK_INDIRECT) and global (OPK_GLOBAL) loads — the
+ * `*p` / global-variable same-block reload. Direct frame-slot loads
+ * (OPK_LOCAL spill/local reloads) are deliberately EXCLUDED: that traffic is
+ * the domain of the adjacent spill compaction in opt_combine_compact_block
+ * (store/load, load/load, load/store, store/store pairs) and the linear-scan
+ * spill machinery, which the doc says to keep distinct from W5. Reusing a
+ * spill reload here both duplicates that machinery and is unsound against the
+ * way the spill/coalesce path may re-home a frame slot, so it stays out. */
+ if (addr->kind != OPK_INDIRECT && addr->kind != OPK_GLOBAL) return 0;
+ if (opt_mem_observable(&in->extra.mem)) return 0;
+ if (in->extra.mem.bf_width != 0) return 0; /* bit-field rider */
+ /* Self-clobbering load (`ldr x9, [x9, #k]`): the destination overwrites its
+ * own address base/index, so after the load the address register no longer
+ * holds the loaded-from pointer. The recorded `addr` operand would then match
+ * a syntactically-identical later load whose base now denotes a DIFFERENT
+ * address — an unsound reuse. Exclude these from both recording and reuse:
+ * the same-operand check (load_addr_regs_unchanged, ctx_def_changed_since)
+ * uses a strictly-greater index test and cannot see a redefinition that
+ * happened AT the recorded load's own index. */
+ if (in->opnds[0].cls == RC_INT && addr->kind == OPK_INDIRECT) {
+ Reg d = in->opnds[0].v.reg;
+ if (addr->v.ind.base == d) return 0;
+ if (addr->v.ind.index != (Reg)REG_NONE && addr->v.ind.index == d) return 0;
+ }
+ return 1;
+}
+
+/* The address registers (base/index of an OPK_INDIRECT) must not have been
+ * redefined since the earlier load produced `dst`. For a direct OPK_LOCAL /
+ * OPK_GLOBAL there is no register input — the address is immutable. */
+static int load_addr_regs_unchanged(const CombineCtx* ctx, const Operand* addr,
+ i32 since_idx) {
+ if (addr->kind != OPK_INDIRECT) return 1;
+ if (addr->v.ind.base != (Reg)REG_NONE &&
+ ctx_def_changed_since(ctx, RC_INT, addr->v.ind.base, since_idx))
+ return 0;
+ if (addr->v.ind.index != (Reg)REG_NONE &&
+ ctx_def_changed_since(ctx, RC_INT, addr->v.ind.index, since_idx))
+ return 0;
+ return 1;
+}
+
+static void load_cse_record(CombineCtx* ctx, const Inst* in, i32 i) {
+ if (!load_is_cseable(in)) return;
+ LoadCseEntry* e = &ctx->load_cse[ctx->load_cse_next];
+ e->inst_idx = i;
+ e->dst = in->opnds[0];
+ e->addr = in->opnds[1];
+ e->size = in->extra.mem.size;
+ e->addr_space = in->extra.mem.addr_space;
+ ctx->load_cse_next = (ctx->load_cse_next + 1u) % COMBINE_LOAD_CSE_SLOTS;
+}
+
+static int try_local_load_cse(CombineCtx* ctx, Inst* in, i32 i) {
+ if (!load_is_cseable(in)) return 0;
+ const Operand* addr = &in->opnds[1];
+ u32 size = in->extra.mem.size;
+ u16 as = in->extra.mem.addr_space;
+ for (u32 k = 0; k < COMBINE_LOAD_CSE_SLOTS; ++k) {
+ const LoadCseEntry* e = &ctx->load_cse[k];
+ if (e->inst_idx < 0 || e->inst_idx >= i) continue;
+ if (e->size != size || e->addr_space != as) continue;
+ if (!same_load_addr_operand(&e->addr, addr)) continue;
+ /* ALIASING: any memory write between the earlier load and now invalidates
+ * reuse. ctx->last_mem_def is the index of the most-recent memory writer
+ * (set by ctx_record for every inst_writes_memory inst, including the
+ * call/asm/intrinsic clobber barrier). If it occurred after the earlier
+ * load, the loaded value may have changed -> do not reuse. */
+ if (ctx->last_mem_def > e->inst_idx) continue;
+ /* The producer register must still hold the loaded value: it is this BB's
+ * live producer of (cls,reg) and was not redefined/clobbered since. */
+ if (ctx_producer_of(ctx, e->dst.cls, e->dst.v.reg) != e->inst_idx) continue;
+ if (ctx_def_changed_since(ctx, e->dst.cls, e->dst.v.reg, e->inst_idx))
+ continue;
+ /* The address-forming registers must be unchanged since the earlier load,
+ * else the two indirects compute different addresses. */
+ if (!load_addr_regs_unchanged(ctx, addr, e->inst_idx)) continue;
+ /* A copy of the producer reg into self is a no-op the dst already holds. */
+ if (same_phys_reg(&in->opnds[0], &e->dst)) continue;
+ /* Same-class reuse only (an int load into an FP reg, or vice versa, would
+ * need a cross-class move, not a same-class copy). */
+ if (in->opnds[0].cls != e->dst.cls) continue;
+ /* Never reuse a value that lives in a target scratch register: native emit
+ * repurposes the scratch regs to materialize OPK_LOCAL operands between MIR
+ * instructions (invisible to MIR-level liveness), so a new copy off such a
+ * register can read a clobbered value. */
+ if (is_target_scratch_reg(ctx->f, e->dst.cls, e->dst.v.reg)) continue;
+ /* Rewrite `load rD, [addr]` into `copy rD, rP`. */
+ in->op = (u16)IR_COPY;
+ in->opnds[1] = e->dst;
+ in->nopnds = 2;
+ ctx->block_change_p = 1;
+ return 1;
+ }
+ return 0;
+}
+
+/* ---- Rewrite 9 (W5): local same-block pure-compute CSE ---- */
+
+/* A pure compute eligible for same-block CSE: IR_BINOP or IR_UNOP with a
+ * register destination. (IR_CMP is excluded — its result feeds branch/flag
+ * lowering and is not a freely-copyable register value here.) */
+static int compute_is_cseable(const Inst* in) {
+ IROp op = (IROp)in->op;
+ if (op != IR_BINOP && op != IR_UNOP) return 0;
+ if (in->nopnds < 1 || in->opnds[0].kind != OPK_REG) return 0;
+ if (op == IR_BINOP && in->nopnds < 3) return 0;
+ if (op == IR_UNOP && in->nopnds < 2) return 0;
+ return 1;
+}
+
+/* Two compute operands match iff identical kind+payload. Only REG and IMM
+ * operands appear as binop/unop inputs at this stage; any other kind is treated
+ * as non-matching (conservative). */
+static int same_compute_operand(const Operand* a, const Operand* b) {
+ if (a->kind != b->kind) return 0;
+ switch (a->kind) {
+ case OPK_REG:
+ return a->cls == b->cls && a->v.reg == b->v.reg;
+ case OPK_IMM:
+ return a->v.imm == b->v.imm && a->type == b->type;
+ default:
+ return 0;
+ }
+}
+
+/* A compute input register must be unchanged since the earlier compute produced
+ * its result, else the recomputation would read different values. */
+static int compute_input_unchanged(const CombineCtx* ctx, const Operand* op,
+ i32 since_idx) {
+ if (op->kind != OPK_REG) return 1; /* immediates never change */
+ return !ctx_def_changed_since(ctx, op->cls, op->v.reg, since_idx);
+}
+
+static void compute_cse_record(CombineCtx* ctx, const Inst* in, i32 i) {
+ if (!compute_is_cseable(in)) return;
+ ComputeCseEntry* e = &ctx->compute_cse[ctx->compute_cse_next];
+ e->inst_idx = i;
+ e->dst = in->opnds[0];
+ e->op = in->op;
+ e->sub = in->extra.imm;
+ e->a = in->opnds[1];
+ if ((IROp)in->op == IR_BINOP)
+ e->b = in->opnds[2];
+ else
+ memset(&e->b, 0, sizeof e->b); /* unary sentinel: kind == 0 */
+ ctx->compute_cse_next =
+ (ctx->compute_cse_next + 1u) % COMBINE_COMPUTE_CSE_SLOTS;
+}
+
+static int try_local_compute_cse(CombineCtx* ctx, Inst* in, i32 i) {
+ if (!compute_is_cseable(in)) return 0;
+ IROp op = (IROp)in->op;
+ const Operand* a = &in->opnds[1];
+ const Operand* b = (op == IR_BINOP) ? &in->opnds[2] : NULL;
+ for (u32 k = 0; k < COMBINE_COMPUTE_CSE_SLOTS; ++k) {
+ const ComputeCseEntry* e = &ctx->compute_cse[k];
+ if (e->inst_idx < 0 || e->inst_idx >= i) continue;
+ if (e->op != in->op || e->sub != in->extra.imm) continue;
+ if (!same_compute_operand(&e->a, a)) continue;
+ if (op == IR_BINOP) {
+ if (!same_compute_operand(&e->b, b)) continue;
+ } else if (e->b.kind != 0) {
+ continue; /* recorded as binary; this is unary -> mismatch */
+ }
+ /* The producer's result register must still be its live producer and
+ * unchanged since (so the copy reads the same value). */
+ if (ctx_producer_of(ctx, e->dst.cls, e->dst.v.reg) != e->inst_idx) continue;
+ if (ctx_def_changed_since(ctx, e->dst.cls, e->dst.v.reg, e->inst_idx))
+ continue;
+ /* Inputs must be unchanged since the earlier compute, else its recorded
+ * result no longer equals recomputing here. */
+ if (!compute_input_unchanged(ctx, a, e->inst_idx)) continue;
+ if (op == IR_BINOP && !compute_input_unchanged(ctx, b, e->inst_idx))
+ continue;
+ /* Self-copy is a no-op; skip. Same class only. */
+ if (same_phys_reg(&in->opnds[0], &e->dst)) continue;
+ if (in->opnds[0].cls != e->dst.cls) continue;
+ /* Never reuse a value that lives in a target scratch register: the
+ * post-combine native emit repurposes the scratch regs to materialize
+ * OPK_LOCAL operands BETWEEN MIR instructions (invisible to MIR-level
+ * liveness), so extending such a register's live range to a new copy reads
+ * a clobbered value. (Same hazard the copy-prop path guards in
+ * try_substitute_for_reg.) */
+ if (is_target_scratch_reg(ctx->f, e->dst.cls, e->dst.v.reg)) continue;
+ /* Rewrite the recompute into `copy rD, rP`. */
+ in->op = (u16)IR_COPY;
+ in->opnds[1] = e->dst;
+ in->nopnds = 2;
+ in->extra.imm = 0;
+ ctx->block_change_p = 1;
+ return 1;
+ }
+ return 0;
+}
+
/* ---- Existing IR_RET retarget (kept; runs in the forward pass) ---- */
static int try_ret_retarget(Func* f, Block* bl, i32 i) {
@@ -1604,14 +1884,25 @@ static int opt_combine_fold_block(Func* f, Block* bl,
try_combine_exts(&ctx, in, i);
try_substitute(&ctx, in, i);
try_addr_synth(&ctx, in, i);
+ /* W5: same-block redundant-load + pure-compute reuse. Run after
+ * addr-synth so both the recorded entries and this lookup see the
+ * canonical (post-fold) address/operand shapes. Each turns the redundant
+ * inst into an IR_COPY off the still-live earlier producer; copy-prop +
+ * DCE then retire it (worst case: a same-cost register move). */
+ try_local_load_cse(&ctx, in, i);
+ try_local_compute_cse(&ctx, in, i);
/* W6: fold a register holding a known constant into a compare's inline
* immediate slot (reads the constant tracker maintained below). */
try_cmp_imm_fold(&ctx, in);
}
/* Track this inst as an addr-of producer for later W1a CSE (only when it is
- * still an addr-of: a prior rewrite may have turned it into a copy). */
+ * still an addr-of: a prior rewrite may have turned it into a copy). Same
+ * for the W5 load / pure-compute rings (recorded only when the inst is
+ * still a load / binop / unop after the rewrites above). */
addr_cse_record(&ctx, in, i);
+ load_cse_record(&ctx, in, i);
+ compute_cse_record(&ctx, in, i);
ctx_record(&ctx, in, i);
/* W6: update the per-register known-constant tracker for this inst (after
* rewrites, so a load_imm produced/rewritten here is recorded). */
diff --git a/test/opt/o1_local_cse.sh b/test/opt/o1_local_cse.sh
@@ -0,0 +1,183 @@
+#!/usr/bin/env bash
+# Structural + correctness checks for the -O1 W5 same-block redundant-load +
+# CSE elimination (O1.md W5), implemented in src/opt/pass_combine.c
+# (try_local_load_cse / try_local_compute_cse).
+#
+# W5 is a single forward pass per block that reuses the last load of an
+# address (and the last result of a pure expression) until a store / call /
+# memory barrier invalidates it. It is deliberately conservative: ALIASING is
+# the whole game -- a load is reused only when NO intervening store may alias
+# (and a write to memory is treated as a full barrier that forgets every
+# pending load), and a pure compute is reused only when its inputs are
+# unchanged since.
+#
+# This guard validates:
+# A. ELIMINATION: a same-block redundant load of the same address with no
+# intervening aliasing store between is eliminated (the second ldr is
+# reused from a register, not re-loaded).
+# B. ALIAS-HAZARD PRESERVATION: a load, then a store that MAY alias, then a
+# reload KEEPS the reload -- W5 must NOT delete a load that may see the
+# new value.
+# C. BARRIER PRESERVATION: a load across a call is not reused (the call is a
+# full barrier), and a volatile load is never reused.
+# D. RUNTIME CORRECTNESS: a function exercising same-block reload + recompute,
+# alias hazards, volatile, and a call barrier computes the identical,
+# correct result at -O0 and -O1.
+set -euo pipefail
+
+ROOT="$(cd "$(dirname "$0")/../.." && pwd)"
+KIT="${KIT:-$ROOT/build/kit}"
+WORK="$ROOT/build/test/opt/o1_local_cse"
+mkdir -p "$WORK"
+
+fail() {
+ printf 'o1_local_cse FAILED: %s\n' "$1" >&2
+ shift || true
+ for f in "$@"; do
+ printf ' --- %s ---\n' "$f" >&2
+ sed 's/^/ | /' "$f" >&2
+ done
+ exit 1
+}
+
+fn_body() { # $1 = file, $2 = symbol name -> stdout body
+ awk -v want="$2" '
+ $0 ~ ("^[0-9a-f]+ <_?" want ">:") { in_fn = 1; next }
+ /^[0-9a-f]+ </ { in_fn = 0 }
+ in_fn { print }
+ ' "$1"
+}
+
+# ---- A. elimination: redundant same-address load reused from a register ----
+# Two reads of the SAME global through the same pointer with no store between.
+# Both reads are of the SAME address with nothing in between that writes
+# memory, so W5 reuses the first load. We count the loads of the slot.
+SRC_A="$WORK/elim.c"
+cat > "$SRC_A" <<'EOF'
+/* Two dependent uses of *p with no intervening write: the second load of *p is
+ * redundant and W5 reuses the first. The address (p in x0) is unchanged and
+ * no store/call happens between the two loads. */
+long load_twice(long *p) {
+ long a = *p; /* ldr */
+ long b = *p + 1; /* redundant ldr -> reuse */
+ return a * b;
+}
+EOF
+OBJ_A="$WORK/elim.o"
+"$KIT" cc -target aarch64-linux-gnu -O1 -std=c11 -c "$SRC_A" \
+ -o "$OBJ_A" > "$WORK/elim.cc.out" 2>&1 || fail "elim compile failed" "$WORK/elim.cc.out"
+"$KIT" objdump -d "$OBJ_A" > "$WORK/elim.dis" 2>&1
+A="$(fn_body "$WORK/elim.dis" load_twice)"
+[ -n "$A" ] || fail "load_twice not found" "$WORK/elim.dis"
+# Exactly one ldr from the pointer should remain (the redundant second is reused).
+NLDR="$(printf '%s\n' "$A" | grep -cE '\bldr\b' || true)"
+[ "$NLDR" -le 1 ] || fail "expected <=1 ldr in load_twice (redundant load not reused, got $NLDR)" "$WORK/elim.dis"
+
+# ---- B. alias-hazard: store between two loads MUST keep the reload ----
+SRC_B="$WORK/alias.c"
+cat > "$SRC_B" <<'EOF'
+/* *p is read, then *q is written (q may alias p), then *p is read again. The
+ * reload of *p must NOT be eliminated: it may observe the value stored to *q. */
+long load_store_load(long *p, long *q, long v) {
+ long a = *p;
+ *q = v; /* may alias *p -- full barrier */
+ long b = *p; /* must reload */
+ return a + b;
+}
+EOF
+OBJ_B="$WORK/alias.o"
+"$KIT" cc -target aarch64-linux-gnu -O1 -std=c11 -c "$SRC_B" \
+ -o "$OBJ_B" > "$WORK/alias.cc.out" 2>&1 || fail "alias compile failed" "$WORK/alias.cc.out"
+"$KIT" objdump -d "$OBJ_B" > "$WORK/alias.dis" 2>&1
+B="$(fn_body "$WORK/alias.dis" load_store_load)"
+[ -n "$B" ] || fail "load_store_load not found" "$WORK/alias.dis"
+# Both loads of *p must survive (>=2 ldr): the store is a barrier.
+NLDR_B="$(printf '%s\n' "$B" | grep -cE '\bldr\b' || true)"
+[ "$NLDR_B" -ge 2 ] || fail "reload after may-alias store was wrongly eliminated (ldr=$NLDR_B)" "$WORK/alias.dis"
+# And a store must be present.
+printf '%s\n' "$B" | grep -qE '\bstr\b' || fail "store missing in load_store_load" "$WORK/alias.dis"
+
+# ---- C. barrier: load across a call + volatile load never reused ----
+SRC_C="$WORK/barrier.c"
+cat > "$SRC_C" <<'EOF'
+extern void sink(void);
+/* Load across a call: the call is a full memory barrier; the reload survives. */
+long load_call_load(long *p) {
+ long a = *p;
+ sink();
+ long b = *p;
+ return a + b;
+}
+/* Volatile load: never reused, each read must re-load. */
+long vol_twice(volatile long *p) {
+ long a = *p;
+ long b = *p;
+ return a + b;
+}
+EOF
+OBJ_C="$WORK/barrier.o"
+"$KIT" cc -target aarch64-linux-gnu -O1 -std=c11 -c "$SRC_C" \
+ -o "$OBJ_C" > "$WORK/barrier.cc.out" 2>&1 || fail "barrier compile failed" "$WORK/barrier.cc.out"
+"$KIT" objdump -d "$OBJ_C" > "$WORK/barrier.dis" 2>&1
+C1="$(fn_body "$WORK/barrier.dis" load_call_load)"
+[ -n "$C1" ] || fail "load_call_load not found" "$WORK/barrier.dis"
+NLDR_C1="$(printf '%s\n' "$C1" | grep -cE '\bldr\b' || true)"
+[ "$NLDR_C1" -ge 2 ] || fail "reload across a call was wrongly eliminated (ldr=$NLDR_C1)" "$WORK/barrier.dis"
+C2="$(fn_body "$WORK/barrier.dis" vol_twice)"
+[ -n "$C2" ] || fail "vol_twice not found" "$WORK/barrier.dis"
+NLDR_C2="$(printf '%s\n' "$C2" | grep -cE '\bldr\b' || true)"
+[ "$NLDR_C2" -ge 2 ] || fail "volatile load was wrongly reused (ldr=$NLDR_C2)" "$WORK/barrier.dis"
+
+# ---- D. runtime correctness at -O0 vs -O1 (native arch) ----
+SRC_D="$WORK/run.c"
+cat > "$SRC_D" <<'EOF'
+/* Freestanding (no libc): the result is reduced to a small exit code, so -O0
+ * and -O1 must produce identical exit status. Exercises same-block redundant
+ * loads + recompute + an alias hazard + a call barrier + a volatile read. */
+static long acc_calls = 0;
+long ext_call(long x) { acc_calls += x; return x * 2; }
+
+static long kern(long *p, long *q, volatile long *vp, long n) {
+ long s = 0;
+ for (long i = 0; i < n; ++i) {
+ long a = p[0]; /* load */
+ long b = p[0] + 7; /* redundant load -> reuse */
+ long c = (a * 3) + (a * 3); /* a*3 computed twice -> reuse one */
+ q[0] = i; /* may alias p[0]: later p[0] read must reload */
+ long d = p[0]; /* reload after the store (alias hazard) */
+ long w = vp[0] + vp[0]; /* volatile: never reused, two real reads */
+ s += a + b + c + d + w;
+ s += ext_call(i & 3); /* call barrier */
+ long e = p[1] + p[1]; /* p[1] redundant load -> reuse, after the call */
+ s += e;
+ }
+ return s + acc_calls;
+}
+
+int main(void) {
+ long arr[2] = {5, 9};
+ long other = 0;
+ volatile long vol = 2;
+ long r = 0;
+ for (long t = 0; t < 11; ++t) {
+ arr[0] = 3 + t; arr[1] = 100 - t; other = 0; acc_calls = 0; vol = t + 1;
+ r ^= kern(arr, &other, &vol, 17);
+ r ^= other; /* observe the aliasing store target */
+ }
+ return (int)(r & 0x7f);
+}
+EOF
+BIN_O0="$WORK/run_o0"
+BIN_O1="$WORK/run_o1"
+"$KIT" cc -O0 -std=c11 "$SRC_D" -o "$BIN_O0" > "$WORK/run.o0.cc.out" 2>&1 \
+ || fail "run -O0 compile failed" "$WORK/run.o0.cc.out"
+"$KIT" cc -O1 -std=c11 "$SRC_D" -o "$BIN_O1" > "$WORK/run.o1.cc.out" 2>&1 \
+ || fail "run -O1 compile failed" "$WORK/run.o1.cc.out"
+set +e
+"$BIN_O0"; EC_O0=$?
+"$BIN_O1"; EC_O1=$?
+set -e
+[ "$EC_O0" = "$EC_O1" ] || fail "O0/O1 exit codes differ: $EC_O0 vs $EC_O1"
+
+printf 'o1_local_cse: OK (elim=%s ldr; alias kept %s ldr; call kept %s; vol kept %s; run rc=%s)\n' \
+ "$NLDR" "$NLDR_B" "$NLDR_C1" "$NLDR_C2" "$EC_O0"
