commit 8826982db37ad31cf01fc2249e1006f31a351daf
parent 6534211c24a035a000b0924e2c8fa3c17704da07
Author: Ryan Sepassi <rsepassi@gmail.com>
Date: Mon, 15 Jun 2026 20:06:29 -0700
opt: fold redundant copies/extensions at O1 (addr_of[base+0], same-width convert, zext-of-load)
A disassembly audit of the ecosystem -O1 output found three redundancies
recurring across every file: a register move per `&*p` deref, a move per
pointer cast, and a `uxtb`/`uxth` after every narrow unsigned load (C integer
promotions). All three are local, target-agnostic canonicalizations that keep
-O1 linear.
- simplify_local: fold `addr_of [base + 0]` (no index) to a copy. The frontend
records the `&*p` / `p+0` idiom as an explicit addr_of of a zero-offset
indirect; without this it lowered to `add base, #0`.
- convert_noop: a same-width, same-register-class convert (notably a pointer
bitcast `int* -> char*`) is a pure copy even when the named types differ.
Guard against cross-class int<->float bitcasts (a real fmov).
- try_combine_exts: a ZEXT of a plain (non-MF_SEXT_LOAD) narrow load reproduces
bits the load already zeroed; rewrite to a copy (worst case a same-cost mov).
The first two collapse at the source so copy-prop/DCE retire them; the third
runs in the existing per-block mir_combine. sqlite -O1 compile time is
unchanged (still linear).
Measured __TEXT reduction (aarch64/Darwin, -O1): sqlite -1.9%, lua VM -3.2%,
lua/lapi.c -9.1%, yyjson -4.3%, miniz/lz4 ~ -3.4%; ~ -2.4% summed over the
ecosystem corpus.
Correctness: test-opt (+ new test/opt/redundant_copy_ext.sh), test-toy (1392/0),
test-ecosystem golden+vs-clang at -O0/-O1 (28/0), test-smoke-x64/rv64 all green.
Diffstat:
5 files changed, 181 insertions(+), 8 deletions(-)
diff --git a/doc/OPT.md b/doc/OPT.md
@@ -240,7 +240,12 @@ IR at the matching stage (`entry` before any pass, `pre-emit` just before emit).
improve the code are exactly these, none of which needs SSA:
- **`simplify_local`** — local algebraic/addressing canonicalization (the
- no-SSA-required cleanup, also used by the interpreter tap).
+ no-SSA-required cleanup, also used by the interpreter tap). Besides the
+ arithmetic identities (`x+0`, `x*1`, …) it folds two address/cast idioms to
+ copies so they collapse instead of lowering to register moves: `addr_of
+ [base + 0]` (the `&*p` / `p + 0` the frontend records around derefs) and a
+ same-width, same-register-class convert (notably a pointer bitcast like
+ `int* -> char*`, where the named types differ but no bits move).
- **Cross-function inlining** — `try_tiny_inline` per function in this pipeline,
plus the whole-program `opt_inline` that runs once at finalize *before* this
pipeline (Section 1). This is the only interprocedural transform.
@@ -257,7 +262,11 @@ improve the code are exactly these, none of which needs SSA:
live-range splitting or move coalescing (the O2-only quality knobs stay off).
- **`mir_combine`** — post-RA peephole + addressing-mode synthesis (the same
`opt_combine` used in O2's SSA combine, here gated on physical-register
- liveness).
+ liveness). Its extension-folding also retires a ZEXT of a plain
+ (zero-extending) narrow load: kit's loads always zero-extend the destination
+ register — sign extension is a flagged load or a separate convert — so the
+ promotion `(int)p[0]` reproduces bits the `ldrb`/`movzbl`/`lbu` already
+ cleared, and the convert collapses to a copy.
- **`mir_dce`** — post-RA dead-code elimination.
- **`jump_cleanup` / `mir_jump_cleanup`** — unreachable-block drop, jump-chain
collapse, and (LAYOUT mode) block reordering for fallthrough + loop rotation.
@@ -358,13 +367,16 @@ transform or analysis; the file paths orient the reader.
`opt_combine` is a per-block forward-pass-with-fixpoint that propagates copies,
folds address-producing computations into a load/store's `OPK_INDIRECT`
base/index/scale/offset where the backend accepts the shape, sinks defs toward
- their sole use, and folds extension chains. It is used in two roles: directly
+ their sole use, and folds extension chains (including a ZEXT of a
+ zero-extending narrow load, which the load already performed). It is used in two roles: directly
in the O2 SSA combine (`opt_ssa_combine` wraps it) and as the post-RA MIR
combine (Section 6). When run over physical MIR it gates each rewrite on a
live-range safety check (Section 5).
- **Simplify** (`src/opt/pass_simplify.c`): `opt_simplify_local` is the
- no-SSA-required local algebraic/addressing canonicalizer used on every path;
- `opt_simplify` is the SSA-aware identity/constant cleanup used in O2.
+ no-SSA-required local algebraic/addressing canonicalizer used on every path
+ (arithmetic identities, `addr_of [base+0]` → copy, and same-width same-class
+ convert → copy); `opt_simplify` is the SSA-aware identity/constant cleanup
+ used in O2.
- **DCE** (`src/opt/pass_dce.c`): `opt_ssa_dce` removes unused SSA defs;
`opt_mir_dce` removes post-RA dead physical defs; both preserve side effects,
including the subtle case of a value-producing op whose destination is an
@@ -645,3 +657,19 @@ Most of the density comes from the cheap per-function transforms
linear-scan allocation) rather than from the inliner's 730 inlines. The `-O1`
object links and runs correctly: the ecosystem gate compiles and runs sqlite at
`-O0` and `-O1` against clang.
+
+The three copy/extension folds above (`addr_of [base+0]`, same-width convert,
+ZEXT-of-load) were added after a disassembly audit of the ecosystem `-O1`
+output found the same redundancies recurring: a register move per `&*p`, a move
+per pointer cast, and a `uxtb`/`uxth` after every narrow unsigned load (C's
+integer promotions). Each is a local, target-agnostic canonicalization, so they
+keep `-O1` linear (sqlite `-O1` compile time is unchanged); correctness is held
+by the ecosystem golden + vs-clang run at `-O0`/`-O1` and the toy/opt suites.
+Measured `__TEXT` reduction across the ecosystem corpus (aarch64/Darwin, `-O1`): sqlite −1.9%, lua VM −3.2%,
+`lua/lapi.c` −9.1%, yyjson −4.3%, miniz/lz4 ≈ −3.4%, ~−2.4% summed. The folds
+are not the whole story — `-O1` text is still several times clang's on
+inline-heavy files, because the wins clang gets from GVN / DSE / redundant-load
+elimination and post-inline cleanup are SSA-only and stay parked in the O2
+mid-end (Section 3). Within the no-SSA budget the remaining linear headroom is
+cross-block copy elimination (the per-block `mir_combine` cannot retire a copy
+whose result is live-out) and local rematerialized-constant CSE.
diff --git a/mk/test.mk b/mk/test.mk
@@ -859,10 +859,17 @@ 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: 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
$(OPT_TEST_BIN)
+# Structural disasm check: the -O1 redundant copy / extension folds
+# (addr_of[base+0] -> copy, same-width convert -> copy, zext-of-load -> copy).
+.PHONY: test-opt-redundant-copy-ext
+test-opt-redundant-copy-ext: bin
+ @KIT=$(abspath $(BIN)) bash test/opt/redundant_copy_ext.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
@@ -1180,6 +1180,25 @@ static int try_combine_exts(CombineCtx* ctx, Inst* in, i32 i) {
i32 prod_idx = ctx_producer_of(ctx, src_cls, src_reg);
if (prod_idx < 0 || prod_idx >= i) return 0;
Inst* prod = &ctx->bl->insts[prod_idx];
+
+ /* Redundant zero-extension of a zero-extending load. A narrow integer load
+ * with no MF_SEXT_LOAD rider zero-extends the whole destination register on
+ * every target (sign extension is always either a separate convert or a
+ * flagged sign-extending load). So a later ZEXT of that register reproduces
+ * bits that are already zero -- as long as the convert keeps at least the
+ * loaded bytes (`sb >= load size`), the result equals the source. Rewrite the
+ * convert to a copy and let copy-prop + DCE retire it; worst case the copy
+ * survives as a same-cost register move (it is never larger than the uxt). */
+ if (!outer_sign && src_cls == RC_INT && (IROp)prod->op == IR_LOAD &&
+ !(prod->extra.mem.flags & MF_SEXT_LOAD) && prod->extra.mem.size &&
+ prod->extra.mem.size <= sb && prod->nopnds >= 1 &&
+ same_reg_operand(&prod->opnds[0], &in->opnds[1])) {
+ in->op = IR_COPY;
+ in->nopnds = 2; /* opnds[0]=dst, opnds[1]=src already in place */
+ ctx->block_change_p = 1;
+ return 1;
+ }
+
u32 isb, idb;
int inner_sign;
if (!ext_params(prod, &isb, &idb, &inner_sign)) return 0;
diff --git a/src/opt/pass_simplify.c b/src/opt/pass_simplify.c
@@ -115,8 +115,19 @@ static int convert_noop(Func* f, const Inst* in) {
if (!in || (IROp)in->op != IR_CONVERT || in->nopnds < 2) return 0;
KitCgTypeId dst_ty = in->opnds[0].type;
KitCgTypeId src_ty = in->opnds[1].type;
- if (dst_ty != src_ty) return 0;
- if (simplify_width(f, dst_ty) != simplify_width(f, src_ty)) return 0;
+ u32 w = simplify_width(f, dst_ty);
+ if (!w || w != simplify_width(f, src_ty)) return 0;
+ /* A same-width int/zext/trunc/bitcast keeps every bit, so it is a pure copy
+ * even when the named types differ -- the common case being a pointer bitcast
+ * (`int* -> char*`) the frontend records around `&*p`-style casts, which would
+ * otherwise lower to a register move that copy-prop cannot then chase (the MIR
+ * combine only forwards a convert into another convert). The one same-width
+ * convert that is NOT a copy is a cross-class bitcast (int <-> float), which
+ * really moves between register files; reject it by requiring the operands to
+ * agree on float-ness. */
+ int dst_flt = kit_cg_type_kind((KitCompiler*)f->c, dst_ty) == KIT_CG_TYPE_FLOAT;
+ int src_flt = kit_cg_type_kind((KitCompiler*)f->c, src_ty) == KIT_CG_TYPE_FLOAT;
+ if (dst_flt != src_flt) return 0;
switch ((ConvKind)in->extra.imm) {
case CV_ZEXT:
case CV_SEXT:
@@ -275,6 +286,31 @@ static int simplify_binop(Func* f, Inst* in, int ssa) {
return 0;
}
+/* addr_of [base + 0] with no index == base. The frontend leaves the `&*p` /
+ * `p + 0` idiom as an explicit IR_ADDR_OF of a zero-offset indirect; without
+ * this fold it lowers to `add base, #0` (a register move that copy-prop must
+ * then chase). Folding it to a copy here collapses the address computation at
+ * the source, on every consumer of the pipeline (O1 native, O2, interp tap).
+ * Address-of-local (OPK_LOCAL) and global (OPK_GLOBAL) sources are untouched —
+ * only a zero-offset register indirect is a pure copy of its base. */
+static int simplify_addr_of(Func* f, Inst* in) {
+ (void)f;
+ if (!in || (IROp)in->op != IR_ADDR_OF || in->flags || in->nopnds < 2) return 0;
+ if (in->opnds[0].kind != OPK_REG) return 0;
+ const Operand* src = &in->opnds[1];
+ if (src->kind != OPK_INDIRECT) return 0;
+ if (src->v.ind.ofs != 0 || src->v.ind.index != (Reg)REG_NONE) return 0;
+ if (src->v.ind.base == (Reg)REG_NONE) return 0;
+ Operand base;
+ memset(&base, 0, sizeof base);
+ base.kind = OPK_REG;
+ base.cls = RC_INT;
+ base.type = in->opnds[0].type;
+ base.v.reg = src->v.ind.base;
+ make_copy(f, in, &base);
+ return 1;
+}
+
static int simplify_cmp(Func* f, Inst* in) {
if (!in || (IROp)in->op != IR_CMP || in->nopnds < 3) return 0;
if (!same_reg(&in->opnds[1], &in->opnds[2])) return 0;
@@ -344,6 +380,8 @@ static int simplify_one(Func* f, Inst* in, int ssa) {
return 1;
}
return ssa ? simplify_convert_chain_ssa(f, in) : 0;
+ case IR_ADDR_OF:
+ return simplify_addr_of(f, in);
case IR_UNOP:
return ssa ? simplify_unop_ssa(f, in) : 0;
default:
diff --git a/test/opt/redundant_copy_ext.sh b/test/opt/redundant_copy_ext.sh
@@ -0,0 +1,81 @@
+#!/usr/bin/env bash
+# Structural checks for the -O1 redundant copy / extension canonicalizations:
+#
+# A. simplify_addr_of: addr_of [base + 0] (the `&*p` / `p+0` idiom) folds to
+# a copy, so it no longer lowers to a `add base, #0` register move that
+# copy-prop must then chase.
+# B. convert_noop: a same-width, same-class convert (e.g. a pointer
+# bitcast `int* -> char*`) folds to a copy that propagates away.
+# C. try_combine_exts: a ZEXT of a plain (zero-extending) narrow load is
+# redundant -- the load already cleared the upper bits -- so it collapses
+# to a copy and usually disappears.
+#
+# All three are local, target-agnostic, and keep -O1 linear. The checks below
+# pin the resulting disassembly on aarch64 (the reference backend), where the
+# patterns have stable mnemonics (`add xN, xM, #0`, `uxtb wD, wS` after a
+# zero-extending `ldrb`).
+set -euo pipefail
+
+ROOT="$(cd "$(dirname "$0")/../.." && pwd)"
+KIT="${KIT:-$ROOT/build/kit}"
+WORK="$ROOT/build/test/opt/redundant_copy_ext"
+mkdir -p "$WORK"
+
+SRC="$WORK/case.c"
+cat > "$SRC" <<'EOF'
+struct T { long a, b; };
+/* A: struct copy through `&*p` -- the frontend records addr_of[base+0]. */
+void copy_struct(struct T *d, struct T *s) { *d = *s; }
+/* B: a pointer bitcast that records a same-width convert. */
+unsigned char *as_bytes(unsigned long *p) { return (unsigned char *)p; }
+/* C: integer promotion of a freshly loaded narrow unsigned value. */
+int low_nibble_is_four(const unsigned char *p) { return (p[0] & 0xf) == 4; }
+EOF
+
+OBJ="$WORK/case.o"
+"$KIT" cc -target aarch64-linux-gnu -O1 -std=c11 -c "$SRC" \
+ -o "$OBJ" > "$WORK/cc.out" 2>&1
+"$KIT" objdump -d "$OBJ" > "$WORK/dis.out" 2>&1
+
+fn_body() { # $1 = symbol name -> stdout body
+ awk -v want="$1" '
+ $0 ~ ("^[0-9a-f]+ <" want ">:") { in_fn = 1; next }
+ /^[0-9a-f]+ </ { in_fn = 0 }
+ in_fn { print }
+ ' "$WORK/dis.out"
+}
+
+fail() {
+ printf 'redundant_copy_ext FAILED: %s\n' "$1" >&2
+ printf ' --- disassembly ---\n' >&2
+ sed 's/^/ | /' "$WORK/dis.out" >&2
+ exit 1
+}
+
+# A: no `add xN, xM, #0` move-as-add anywhere (every copy_struct / as_bytes
+# address pass should be a real load/store or a copy that propagated away).
+if grep -Eq 'add\sx[0-9]+, x[0-9]+, #0$' "$WORK/dis.out"; then
+ fail "found 'add xN, xM, #0' (unfolded addr_of[base+0] copy)"
+fi
+
+# B: as_bytes is a pure pointer bitcast -- the whole body is prologue/epilogue
+# plus a single move of the argument into the return register; there must be
+# no convert/extend instruction for the cast.
+B="$(fn_body _as_bytes)"
+[ -n "$B" ] || B="$(fn_body as_bytes)"
+[ -n "$B" ] || fail "as_bytes not found in disassembly"
+if printf '%s\n' "$B" | grep -Eq '\b(uxtb|uxth|uxtw|sxtb|sxth|sxtw)\b'; then
+ fail "as_bytes pointer bitcast emitted an extension"
+fi
+
+# C: low_nibble_is_four loads a byte (zero-extending ldrb) and must NOT follow
+# it with a redundant uxtb -- the ZEXT collapsed into the load.
+C="$(fn_body _low_nibble_is_four)"
+[ -n "$C" ] || C="$(fn_body low_nibble_is_four)"
+[ -n "$C" ] || fail "low_nibble_is_four not found in disassembly"
+printf '%s\n' "$C" | grep -Eq '\bldrb\b' || fail "expected a ldrb in low_nibble_is_four"
+if printf '%s\n' "$C" | grep -Eq '\buxtb\b'; then
+ fail "redundant uxtb after zero-extending ldrb survived"
+fi
+
+printf 'redundant_copy_ext: OK (addr_of[base+0], pointer bitcast, zext-of-load)\n'
