commit e4616ec01a48407749c805c9995b0240c38c35b6
parent 840cf4000eb3cdfc1cf13448b8bed1e68c230018
Author: Ryan Sepassi <rsepassi@gmail.com>
Date: Tue, 16 Jun 2026 08:31:13 -0700
opt: fold constant-operand integer divide/multiply at O1 (O1-PATTERNS.md L9)
Add a same-block forward LOAD_IMM->known-value tracker to the local (pre-SSA)
simplify pass so the existing BO_UDIV/BO_SDIV/BO_IMUL identity folds and
simplify_cmp fire when an operand is a constant materialized into a register
rather than an inline OPK_IMM, plus a const-op-const fold that evaluates a fully
compile-time-constant binop to a single LOAD_IMM.
The tracker is a bounded per-PReg reg->value map, populated on IR_LOAD_IMM /
IR_CONST_I, invalidated on any redef, and reset at every block boundary -- a
single forward scan per block, no SSA, so -O1 stays linear. It is fed through
operand_const (NULL/def-use index in the SSA pass).
This folds the classic sizeof(X)/sizeof(Y) const divide to a movz of the
quotient and the Lua MAX_SIZET/sizeof(T) >= LIMIT growvector guard: the udiv
becomes a constant, then simplify_cmp decides the always-true compare and the
dead arm drops. Divide-by-1 (incl. the register-resident lparser shape) folds to
a copy.
Division by zero is NEVER folded -- simplify_divrem mirrors src/cg/const.c's
const_divrem64 exactly (b==0 returns 0, leaving the runtime udiv/sdiv so the
fault behavior is preserved) and reuses the shared kit_ir_eval core for the
wrapping ops and the signed/width/INT_MIN-over-(-1) semantics.
lparser udiv 22->0, sqlite __TEXT -0.18%, lapi unchanged (its 9 sdiv are all
runtime divisors). All ecosystem O0/O1 vs-clang + golden pass; sqlite -O1 timing
unchanged. New structural guard test/opt/o1p_const_divmul.sh (run via
KIT=build/kit bash; not wired into mk/test.mk, which is out of this item's
file-ownership scope).
Diffstat:
2 files changed, 308 insertions(+), 13 deletions(-)
diff --git a/src/opt/pass_simplify.c b/src/opt/pass_simplify.c
@@ -4,6 +4,25 @@
#include "cg/ir_eval.h"
#include "opt/opt_internal.h"
+/* O1.md / O1-PATTERNS.md L9: same-block forward LOAD_IMM -> known-value tracker
+ * for the local (pre-SSA) simplify pass. A bounded per-PReg `reg -> constant`
+ * map, populated when an instruction is an IR_LOAD_IMM / IR_CONST_I and
+ * invalidated whenever any later instruction in the block (re)defines that PReg.
+ * It is rebuilt from empty at every block boundary -- a single forward scan, no
+ * SSA, no cross-block reasoning, so -O1 stays linear. Feeding it into
+ * operand_const lets the existing BO_UDIV/BO_SDIV/BO_IMUL identity folds and
+ * simplify_cmp fire (and a const-op-const fold below) when the operand is a
+ * constant materialized into a register rather than an inline OPK_IMM -- the
+ * classic `sizeof(X)/sizeof(Y)` and the SIZE_MAX/sizeof(T) >= N growvector
+ * guard, which kit otherwise leaves as a runtime udiv + cmp.
+ *
+ * NULL in the SSA pass (opt_simplify), which uses the def-use index instead. */
+typedef struct LocalConst {
+ i64* val; /* val[r] is the constant in PReg r when known[r] */
+ u8* known; /* per-PReg validity bit */
+ u32 n; /* == f->npregs; PRegs >= n are never tracked */
+} LocalConst;
+
/* simplify's PTR-aware width derivation is its own type policy; the masking and
* commutativity below are the shared cg/ir_eval core (src/cg/ir_eval.h). */
static u32 simplify_width(Func* f, KitCgTypeId ty) {
@@ -40,10 +59,24 @@ static int val_load_imm(Func* f, Val v, i64* out) {
return 1;
}
-static int operand_const(Func* f, const Operand* op, u32 width, i64* out) {
+/* Same-block tracker lookup: is PReg `r` a currently-known constant? */
+static int local_const_lookup(const LocalConst* lc, Reg r, i64* out) {
+ if (!lc || r == (Reg)REG_NONE || (u32)r >= lc->n || !lc->known[r]) return 0;
+ *out = lc->val[r];
+ return 1;
+}
+
+static int operand_const(Func* f, const LocalConst* lc, const Operand* op,
+ u32 width, i64* out) {
if (imm_value(f, op, width, out)) return 1;
- if (!f->opt_reg_ssa || !op || op->kind != OPK_REG) return 0;
- if (!val_load_imm(f, (Val)op->v.reg, out)) return 0;
+ if (!op || op->kind != OPK_REG) return 0;
+ /* SSA pass: chase the unique def via the def-use index. Local pass: consult
+ * the bounded same-block forward tracker. Exactly one of the two is active. */
+ if (f->opt_reg_ssa) {
+ if (!val_load_imm(f, (Val)op->v.reg, out)) return 0;
+ } else {
+ if (!local_const_lookup(lc, op->v.reg, out)) return 0;
+ }
*out = (i64)kit_ir_mask_width((u64)*out, width);
return 1;
}
@@ -139,6 +172,65 @@ static int convert_noop(Func* f, const Inst* in) {
}
}
+/* Constant integer divide/remainder at `width` bits. Mirrors the authoritative
+ * constant-expression semantics in src/cg/const.c (const_divrem64) exactly:
+ *
+ * - DIVISION BY ZERO IS NEVER FOLDED (returns 0): leaving the runtime
+ * udiv/sdiv in place preserves the program's fault behavior, matching what
+ * the existing inline-immediate path does (kit_ir_eval_binop also declines
+ * div/rem, and the identity folds only fire for a non-zero divisor).
+ * - Unsigned ops mask to `width` and divide/modulo the masked values.
+ * - Signed ops compute on the magnitudes and reapply the sign, so INT_MIN/-1
+ * wraps to INT_MIN (an == bn, no negate) -- the defined two's-complement
+ * result the hardware sdiv also produces, so the fold is value-preserving.
+ *
+ * Returns 1 and stores the masked result, or 0 (b==0, or not a div/rem). */
+static int simplify_divrem(BinOp op, u32 width, i64 a64, i64 b64, i64* out) {
+ u64 mask = kit_ir_width_mask(width);
+ u64 a = (u64)a64 & mask;
+ u64 b = (u64)b64 & mask;
+ if (b == 0) return 0; /* preserve the runtime trap -- do NOT fold /0 */
+ switch (op) {
+ case BO_UDIV:
+ *out = (i64)((a / b) & mask);
+ return 1;
+ case BO_UREM:
+ *out = (i64)((a % b) & mask);
+ return 1;
+ case BO_SDIV:
+ case BO_SREM: {
+ int an = width && ((a >> (width - 1u)) & 1u) != 0;
+ int bn = width && ((b >> (width - 1u)) & 1u) != 0;
+ u64 aa = an ? (((~a) + 1u) & mask) : a;
+ u64 bb = bn ? (((~b) + 1u) & mask) : b;
+ u64 r;
+ if (bb == 0) return 0;
+ if (op == BO_SDIV) {
+ r = aa / bb;
+ if (an != bn) r = ((~r) + 1u) & mask;
+ } else {
+ r = aa % bb;
+ if (an) r = ((~r) + 1u) & mask;
+ }
+ *out = (i64)(r & mask);
+ return 1;
+ }
+ default:
+ return 0;
+ }
+}
+
+/* Fold a fully-constant integer binop to its value. Delegates the wrapping
+ * arithmetic/bitwise/shift ops to the shared cg/ir_eval core and the div/rem
+ * ops (which that core deliberately declines) to simplify_divrem above, so the
+ * /0 guard and signed/width semantics match the constant-expression evaluator
+ * exactly. Returns 1 (and stores the masked result) only when the op is
+ * genuinely constant-foldable; div-by-zero returns 0. */
+static int simplify_fold_const(BinOp op, u32 width, i64 a, i64 b, i64* out) {
+ if (kit_ir_eval_binop(op, width, a, b, out)) return 1;
+ return simplify_divrem(op, width, a, b, out);
+}
+
/* Commutative integer binops the canonicalizer below may swap operands of: the
* shared integer predicate (kit_ir_binop_is_commutative_int). Floating-point
* commutative ops are intentionally excluded here -- the shared predicate
@@ -147,7 +239,7 @@ static int convert_noop(Func* f, const Inst* in) {
* distinguish operand order for NaN payloads. Non-commutative ops (sub, shifts,
* div/rem) are skipped. */
-static int simplify_binop(Func* f, Inst* in, int ssa) {
+static int simplify_binop(Func* f, const LocalConst* lc, Inst* in) {
if (!in || (IROp)in->op != IR_BINOP || in->flags || in->nopnds < 3) return 0;
if (in->opnds[0].kind != OPK_REG) return 0;
u32 width = simplify_width(f, in->type ? in->type : in->opnds[0].type);
@@ -169,10 +261,26 @@ static int simplify_binop(Func* f, Inst* in, int ssa) {
Operand* b = &in->opnds[2];
i64 av = 0;
i64 bv = 0;
- int ac = ssa ? operand_const(f, a, width, &av) : imm_value(f, a, width, &av);
- int bc = ssa ? operand_const(f, b, width, &bv) : imm_value(f, b, width, &bv);
+ /* A constant operand is either an inline OPK_IMM or a register whose value is
+ * known -- via the def-use index (SSA pass) or the same-block forward tracker
+ * (local pass). operand_const handles both, masking to the op width. */
+ int ac = operand_const(f, lc, a, width, &av);
+ int bc = operand_const(f, lc, b, width, &bv);
u64 all = kit_ir_width_mask(width);
+ /* const op const -> the value. Folds the classic sizeof/sizeof and the
+ * SIZE_MAX/sizeof guard's udiv into a single LOAD_IMM; the resulting constant
+ * then lets simplify_cmp decide the always-true compare. simplify_fold_const
+ * declines div-by-zero (and the non-arithmetic ops), so the runtime trap and
+ * any non-foldable op fall through to the identity folds below unchanged. */
+ if (ac && bc) {
+ i64 r;
+ if (simplify_fold_const((BinOp)in->extra.imm, width, av, bv, &r)) {
+ make_load_imm(f, in, r);
+ return 1;
+ }
+ }
+
switch ((BinOp)in->extra.imm) {
case BO_IADD:
if (bc && bv == 0 && a->kind == OPK_REG) {
@@ -311,10 +419,29 @@ static int simplify_addr_of(Func* f, Inst* in) {
return 1;
}
-static int simplify_cmp(Func* f, Inst* in) {
+static int simplify_cmp(Func* f, const LocalConst* lc, Inst* in) {
if (!in || (IROp)in->op != IR_CMP || in->nopnds < 3) return 0;
+ u32 width = simplify_width(f, in->opnds[1].type);
+ if (!width) return 0;
+
+ /* const cmp const -> its boolean. This is what decides the always-true
+ * SIZE_MAX/sizeof(T) >= N growvector guard once the udiv above has folded its
+ * dividend/divisor into a known constant; the dead arm then drops via the
+ * existing branch/CFG cleanup. Mask/sign-extend handling lives in the shared
+ * kit_ir_eval_cmp (signed predicates compare the sign-extended values). */
+ {
+ i64 av;
+ i64 bv;
+ i64 r;
+ if (operand_const(f, lc, &in->opnds[1], width, &av) &&
+ operand_const(f, lc, &in->opnds[2], width, &bv) &&
+ kit_ir_eval_cmp((CmpOp)in->extra.imm, width, av, bv, &r)) {
+ make_load_imm(f, in, r);
+ return 1;
+ }
+ }
+
if (!same_reg(&in->opnds[1], &in->opnds[2])) return 0;
- if (!simplify_width(f, in->opnds[1].type)) return 0;
switch ((CmpOp)in->extra.imm) {
case CMP_EQ:
case CMP_LE_S:
@@ -368,12 +495,12 @@ static int simplify_convert_chain_ssa(Func* f, Inst* in) {
return 1;
}
-static int simplify_one(Func* f, Inst* in, int ssa) {
+static int simplify_one(Func* f, const LocalConst* lc, Inst* in, int ssa) {
switch ((IROp)in->op) {
case IR_BINOP:
- return simplify_binop(f, in, ssa);
+ return simplify_binop(f, lc, in);
case IR_CMP:
- return simplify_cmp(f, in);
+ return simplify_cmp(f, lc, in);
case IR_CONVERT:
if (convert_noop(f, in)) {
make_copy(f, in, &in->opnds[1]);
@@ -389,14 +516,54 @@ static int simplify_one(Func* f, Inst* in, int ssa) {
}
}
+/* Record the constant a (possibly just-rewritten) LOAD_IMM / CONST_I puts in its
+ * destination PReg, and invalidate the tracker entry for every other PReg the
+ * instruction defines. Both kinds carry the immediate in extra.imm and the dst
+ * PReg in opnds[0] (LOAD_IMM) -- the same shape make_load_imm produces, so a
+ * binop/cmp this pass just folded to a constant becomes visible to the next
+ * instruction in the same block (e.g. the SIZE_MAX/sizeof udiv feeding a cmp). */
+static void local_const_update(LocalConst* lc, Inst* in) {
+ Reg made = (Reg)REG_NONE;
+ if (((IROp)in->op == IR_LOAD_IMM || (IROp)in->op == IR_CONST_I) &&
+ in->nopnds >= 1 && in->opnds[0].kind == OPK_REG &&
+ in->opnds[0].cls == RC_INT) {
+ made = in->opnds[0].v.reg;
+ if (made != (Reg)REG_NONE && (u32)made < lc->n) {
+ lc->val[made] = in->extra.imm;
+ lc->known[made] = 1;
+ }
+ }
+ /* Any def that is not the freshly-recorded constant invalidates its slot. */
+ if (in->def != VAL_NONE && in->def != made && (u32)in->def < lc->n)
+ lc->known[in->def] = 0;
+ for (u32 i = 0; i < in->ndefs; ++i) {
+ Reg d = (Reg)in->defs[i];
+ if (d != made && d != (Reg)REG_NONE && (u32)d < lc->n) lc->known[d] = 0;
+ }
+}
+
static void simplify_run(Func* f, int ssa) {
if (!f || f->opt_rewritten) return;
if (ssa) opt_rebuild_def_use(f);
int changed = 0;
+ LocalConst lc;
+ LocalConst* lcp = NULL;
+ if (!ssa && f->npregs) {
+ lc.n = f->npregs;
+ lc.val = arena_array(f->arena, i64, lc.n);
+ lc.known = arena_array(f->arena, u8, lc.n);
+ lcp = &lc;
+ }
for (u32 b = 0; b < f->nblocks; ++b) {
Block* bl = &f->blocks[b];
- for (u32 i = 0; i < bl->ninsts; ++i)
- if (simplify_one(f, &bl->insts[i], ssa)) changed = 1;
+ /* The tracker is rebuilt from empty at each block boundary -- no cross-block
+ * reasoning, so the pass stays a single linear forward scan per block. */
+ if (lcp) memset(lcp->known, 0, sizeof(u8) * lcp->n);
+ for (u32 i = 0; i < bl->ninsts; ++i) {
+ Inst* in = &bl->insts[i];
+ if (simplify_one(f, lcp, in, ssa)) changed = 1;
+ if (lcp) local_const_update(lcp, in);
+ }
}
if (changed) opt_analysis_invalidate(f, OPT_ANALYSIS_DEF_USE);
if (ssa || changed) opt_rebuild_def_use(f);
diff --git a/test/opt/o1p_const_divmul.sh b/test/opt/o1p_const_divmul.sh
@@ -0,0 +1,128 @@
+#!/usr/bin/env bash
+# Structural checks for the -O1 constant-operand integer divide/multiply fold
+# (O1-PATTERNS.md L9), in src/opt/pass_simplify.c (opt_simplify_local):
+#
+# A. A `sizeof(X)/sizeof(Y)`-style const divide -- where kit materializes both
+# constants into registers (`movz`) and issues a runtime `udiv` -- folds at
+# compile time to a single `movz` of the quotient: NO `udiv`/`sdiv`.
+# B. The Lua growvector guard shape `(SIZE_MAX / sizeof(T)) >= N` (N also a
+# compile-time constant) folds the udiv to a constant, then the always-true
+# compare is decided too, collapsing the whole function to a `movz #1`.
+# C. A divide-by-1 whose `1` survives in a (callee-saved) register across a
+# call -- so it reaches the divide as a REGISTER operand, the lparser
+# udiv-by-1 shape -- folds away: no `udiv`.
+# D. NEGATIVE (the load-bearing guard): a divide whose divisor is a known
+# compile-time ZERO must NOT be folded; the runtime `sdiv`/`udiv` stays so
+# the program's division-fault behavior is preserved. Likewise a divide by a
+# genuinely runtime value keeps its div.
+#
+# The fold is a same-block forward LOAD_IMM->known-value tracker feeding the
+# existing identity folds + a const-op-const fold; it keeps -O1 linear (one
+# forward scan per block, no SSA). The checks pin the resulting disassembly on
+# aarch64 (the reference backend), where the patterns have stable mnemonics.
+set -euo pipefail
+
+ROOT="$(cd "$(dirname "$0")/../.." && pwd)"
+KIT="${KIT:-$ROOT/build/kit}"
+WORK="$ROOT/build/test/opt/o1p_const_divmul"
+mkdir -p "$WORK"
+
+SRC="$WORK/case.c"
+cat > "$SRC" <<'EOF'
+#include <stdint.h>
+struct Big { char a[40]; };
+struct Small { char a[8]; };
+extern void barrier(void);
+
+/* A: sizeof/sizeof const divide -> quotient (40/8 == 5). */
+unsigned long arr_count(void) {
+ return sizeof(struct Big) / sizeof(struct Small);
+}
+/* B: SIZE_MAX/sizeof(T) >= N growvector guard, N a constant -> always true. */
+int growvec_guard(void) {
+ return (SIZE_MAX / sizeof(struct Small)) >= 1000000;
+}
+/* C: divide-by-1 where the 1 reaches the udiv as a register (lives across a
+ * call), so the inline-immediate path can't see it -- still folds away. */
+unsigned long div_by_one_reg(unsigned long x) {
+ unsigned long one = 1;
+ barrier();
+ return x / one;
+}
+/* D-zero: divisor is a compile-time ZERO -> MUST keep the div (trap behavior). */
+int div_by_zero(int x) {
+ int z = 0;
+ return x / z;
+}
+/* D-runtime: divisor is a runtime value -> MUST keep the div. */
+int div_runtime(int x, int y) { return x / y; }
+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 'o1p_const_divmul FAILED: %s\n' "$1" >&2
+ printf ' --- disassembly ---\n' >&2
+ sed 's/^/ | /' "$WORK/dis.out" >&2
+ exit 1
+}
+
+# A: arr_count -- no div, and the quotient 5 is materialized (movz ...,0x5).
+A="$(fn_body _arr_count)"
+[ -n "$A" ] || A="$(fn_body arr_count)"
+[ -n "$A" ] || fail "arr_count not found"
+if printf '%s\n' "$A" | grep -Eq '\b[us]div\b'; then
+ fail "arr_count kept a div (const sizeof/sizeof divide not folded)"
+fi
+printf '%s\n' "$A" | grep -Eq 'movz[[:space:]]+x[0-9]+, 0x5\b' \
+ || fail "arr_count did not materialize the folded quotient 5 (movz xN,0x5)"
+
+# B: growvec_guard -- the udiv is gone, the always-true compare is decided, so
+# the whole function collapses to `movz wN,#1` (no div, no cmp, no cset).
+B="$(fn_body _growvec_guard)"
+[ -n "$B" ] || B="$(fn_body growvec_guard)"
+[ -n "$B" ] || fail "growvec_guard not found"
+if printf '%s\n' "$B" | grep -Eq '\b[us]div\b'; then
+ fail "growvec_guard kept a div (SIZE_MAX guard udiv not folded)"
+fi
+if printf '%s\n' "$B" | grep -Eq '\b(cmp|cset)\b'; then
+ fail "growvec_guard kept a compare (always-true guard not decided)"
+fi
+printf '%s\n' "$B" | grep -Eq 'movz[[:space:]]+w[0-9]+, 0x1\b' \
+ || fail "growvec_guard did not fold to a constant 1"
+
+# C: div_by_one_reg -- no div survives (divide-by-1 folded to a copy).
+C="$(fn_body _div_by_one_reg)"
+[ -n "$C" ] || C="$(fn_body div_by_one_reg)"
+[ -n "$C" ] || fail "div_by_one_reg not found"
+if printf '%s\n' "$C" | grep -Eq '\b[us]div\b'; then
+ fail "div_by_one_reg kept a udiv (register divide-by-1 not folded)"
+fi
+
+# D-zero NEGATIVE: div_by_zero MUST still emit the div -- folding /0 would
+# silently drop the fault. This is the critical correctness guard.
+DZ="$(fn_body _div_by_zero)"
+[ -n "$DZ" ] || DZ="$(fn_body div_by_zero)"
+[ -n "$DZ" ] || fail "div_by_zero not found"
+printf '%s\n' "$DZ" | grep -Eq '\b[us]div\b' \
+ || fail "div_by_zero lost its div -- /0 was folded (FAULT BEHAVIOR BROKEN)"
+
+# D-runtime NEGATIVE: div_runtime MUST still emit the div.
+DR="$(fn_body _div_runtime)"
+[ -n "$DR" ] || DR="$(fn_body div_runtime)"
+[ -n "$DR" ] || fail "div_runtime not found"
+printf '%s\n' "$DR" | grep -Eq '\b[us]div\b' \
+ || fail "div_runtime lost its div (a runtime divisor was wrongly folded)"
+
+printf 'o1p_const_divmul: OK (sizeof/sizeof fold, SIZE_MAX guard, reg div-by-1; /0 + runtime div kept)\n'
