commit a35a48341c3cf53067fb777e0dd7ad3b36e4b92e
parent 06bbc026b294d80cc9ed27fba745d9ed3220d922
Author: Ryan Sepassi <rsepassi@gmail.com>
Date: Tue, 16 Jun 2026 08:28:10 -0700
opt: fuse cmp;cset;cbnz/cbz into cmp_branch at O1 (O1-PATTERNS L2)
A relational whose 0/1 bool was materialized into a register and then
re-tested by the terminator lowers, at MIR, to IR_CMP rD followed by the
terminator IR_CMP_BRANCH(CMP_NE|CMP_EQ, rD, #0). When rD's most-recent
same-block def is a single-use IR_CMP, try_fuse_cmp_branch rewrites the
branch to test the cmp's own relation (inverting for the cbz/EQ-vs-0 case
via the full CmpOp invert table, correct for FP NaN too) and NOPs the
cmp. The inverse of the SSA fusion in pass_o2.c ssa_combine_fold_cmp_branch,
here over the no-SSA CombineCtx (last-def + hard-live single-use). No
condition inversion is needed for cbnz; cbz inverts the cmp op.
SAME-BLOCK SCOPE: at no-SSA O1 many s split the cmp and its branch
into different MIR blocks (a scope_begin/block boundary the prepare-time
jump cleanup does not concatenate), which a same-block peephole cannot
reach. L2 fuses the co-located subset (inlined predicates etc.): yyjson.c
-O1 cset 1780 -> 1704, lvm cset;cbr 19->15, lapi 27->13. The broad
cross-block residual the catalog counted from post-emit disasm adjacency
needs the SSA path / post-combine block merging and is out of scope here.
Inversion verified correct across every relation x both branch polarities
x FP NaN/inf (kit O0==O1==clang). Battery + cjson/yyjson/sqlite/lua -O1
run-correct; x64/rv64/aa64 cross-compile clean.
Adds the L2 red-green section to test/opt/o1p_combine.sh (yyjson cset
count + all-relations/both-polarities/FP O0==O1 inversion check).
Diffstat:
2 files changed, 187 insertions(+), 0 deletions(-)
diff --git a/src/opt/pass_combine.c b/src/opt/pass_combine.c
@@ -1405,6 +1405,128 @@ static int try_combine_exts(CombineCtx* ctx, Inst* in, i32 i) {
return 0;
}
+/* Invert a CmpOp (negate the relation). Returns 0 for an op outside the
+ * known total set. Kept byte-for-byte in sync with src/cg/fold.c
+ * api_invert_cmp and pass_jump.c invert_cmp — including the FP rule that
+ * negation flips ordered<->unordered (so the NaN outcome flips too): the
+ * negation of ordered `a<b` is *unordered* `a>=b`. */
+static int combine_invert_cmp(CmpOp op, CmpOp* out) {
+ switch (op) {
+ case CMP_EQ: *out = CMP_NE; return 1;
+ case CMP_NE: *out = CMP_EQ; return 1;
+ case CMP_LT_S: *out = CMP_GE_S; return 1;
+ case CMP_LE_S: *out = CMP_GT_S; return 1;
+ case CMP_GT_S: *out = CMP_LE_S; return 1;
+ case CMP_GE_S: *out = CMP_LT_S; return 1;
+ case CMP_LT_U: *out = CMP_GE_U; return 1;
+ case CMP_LE_U: *out = CMP_GT_U; return 1;
+ case CMP_GT_U: *out = CMP_LE_U; return 1;
+ case CMP_GE_U: *out = CMP_LT_U; return 1;
+ case CMP_OEQ_F: *out = CMP_UNE_F; return 1;
+ case CMP_ONE_F: *out = CMP_UEQ_F; return 1;
+ case CMP_OLT_F: *out = CMP_UGE_F; return 1;
+ case CMP_OLE_F: *out = CMP_UGT_F; return 1;
+ case CMP_OGT_F: *out = CMP_ULE_F; return 1;
+ case CMP_OGE_F: *out = CMP_ULT_F; return 1;
+ case CMP_UEQ_F: *out = CMP_ONE_F; return 1;
+ case CMP_UNE_F: *out = CMP_OEQ_F; return 1;
+ case CMP_ULT_F: *out = CMP_OGE_F; return 1;
+ case CMP_ULE_F: *out = CMP_OGT_F; return 1;
+ case CMP_UGT_F: *out = CMP_OLE_F; return 1;
+ case CMP_UGE_F: *out = CMP_OLT_F; return 1;
+ }
+ return 0;
+}
+
+/* ---- L2 (O1-PATTERNS): fuse cmp rD; cmp_branch(NE/EQ, rD, #0) -> cmp_branch
+ *
+ * A relational whose 0/1 bool was MATERIALIZED into a register (`cmp; cset
+ * rD,cc`) and then re-tested by the branch (`cbnz/cbz rD`) lowers, at this
+ * MIR level, to `IR_CMP rD = (a cc b)` followed by the terminator
+ * `IR_CMP_BRANCH(CMP_NE|CMP_EQ, rD, #0)` (control.c synthesizes cmp_branch of
+ * the bool against IMM_ZERO; cg's delayed-compare path already fuses the
+ * un-materialized `if (a<b)` form upstream, so only the materialized residual
+ * reaches here). The branch's NE/EQ-vs-0 just re-tests a bool the original cmp
+ * already computed in flags.
+ *
+ * When the terminator is `IR_CMP_BRANCH(NE|EQ, rD, #0)` whose rD's most-recent
+ * same-block def is a single-use IR_CMP, fuse into the cmp's own relation:
+ * cbnz (CMP_NE vs 0): branch-if-true -> cmp_branch(cmp.op, a, b)
+ * cbz (CMP_EQ vs 0): branch-if-false -> cmp_branch(invert(cmp.op), a, b)
+ * and NOP the now-dead cmp. This is the inverse of the SSA fusion in
+ * pass_o2.c (ssa_combine_fold_cmp_branch), here over the no-SSA CombineCtx
+ * (last-def map + hard-live single-use). Inversion uses the full CmpOp table
+ * (combine_invert_cmp), which is correct for FP too: the cset collapsed the
+ * comparison to a definite 0/1 even for NaN, and the inverse op reproduces the
+ * same NaN branch direction (e.g. !(a OEQ b) == a UNE b).
+ *
+ * Single-block, single forward pass, all guards from existing CombineCtx state
+ * -> linear. */
+static int try_fuse_cmp_branch(CombineCtx* ctx, Inst* in, i32 i) {
+ if ((IROp)in->op != IR_CMP_BRANCH || in->nopnds < 2) return 0;
+ /* Only the block terminator carries the two CFG successors. */
+ if (i != (i32)ctx->bl->ninsts - 1 || ctx->bl->nsucc < 2) return 0;
+ /* Branch must test a register bool against immediate 0 with EQ/NE. */
+ CmpOp brop = (CmpOp)in->extra.imm;
+ if (brop != CMP_EQ && brop != CMP_NE) return 0;
+ if (in->opnds[0].kind != OPK_REG) return 0;
+ if (in->opnds[1].kind != OPK_IMM || in->opnds[1].v.imm != 0) return 0;
+
+ Operand cond = in->opnds[0];
+ i32 prod_idx = ctx_producer_of(ctx, cond.cls, cond.v.reg);
+ if (prod_idx < 0 || prod_idx >= i) return 0;
+ Inst* cmp = &ctx->bl->insts[prod_idx];
+ if ((IROp)cmp->op != IR_CMP || cmp->nopnds < 3) return 0;
+ if (cmp->opnds[0].kind != OPK_REG || !same_phys_reg(&cmp->opnds[0], &cond))
+ return 0;
+
+ /* Resolve the fused relation (invert for the cbz / EQ-vs-0 case). */
+ CmpOp fused = (CmpOp)cmp->extra.imm;
+ if (brop == CMP_EQ && !combine_invert_cmp(fused, &fused)) return 0;
+
+ /* The cmp's input operands must be unchanged between the cmp and the branch
+ * (an intervening inst may have redefined a register the cmp reads). */
+ for (u32 oi = 1; oi < 3; ++oi) {
+ const Operand* p = &cmp->opnds[oi];
+ if (p->kind == OPK_REG &&
+ ctx_def_changed_since(ctx, p->cls, p->v.reg, prod_idx))
+ return 0;
+ }
+
+ /* The cmp's result must die at this branch: its sole use, not live-out. If it
+ * has other uses (or escapes the block) the cmp must stay and we cannot NOP
+ * it. */
+ Operand cmp_def = cmp->opnds[0];
+ int killed = 0;
+ if (count_uses_in_live_range(ctx->f, ctx->bl, prod_idx, &cmp_def, &killed) !=
+ 1)
+ return 0;
+ if (!killed && opt_block_live_out_has_phys_reg(ctx->f, ctx->hard_live,
+ ctx->bl->id, &cmp_def))
+ return 0;
+
+ /* Fuse: rewrite the branch to test the cmp's own relation directly; NOP the
+ * cmp. Successors are unchanged (succ[0]=taken, succ[1]=fallthrough). */
+ Operand* opnds = arena_array(ctx->f->arena, Operand, 2);
+ opnds[0] = cmp->opnds[1];
+ opnds[1] = cmp->opnds[2];
+ in->opnds = opnds;
+ in->nopnds = 2;
+ in->extra.imm = (i64)fused;
+
+ cmp->op = (u16)IR_NOP;
+ cmp->def = VAL_NONE;
+ cmp->ndefs = 0;
+ cmp->defs = NULL;
+ cmp->nopnds = 0;
+ cmp->opnds = NULL;
+ /* The cmp no longer defines cond's register; restore its prior reaching def
+ * so later same-block availability checks stay accurate. */
+ ctx_restore_removed_def(ctx, &cond, prod_idx);
+ ctx->block_change_p = 1;
+ return 1;
+}
+
/* ---- Rewrite 6 (W1a): local frame-address `sub`-CSE ----
*
* O1.md W1a. An `IR_ADDR_OF rD, <addr>` materializes a frame-slot or global
@@ -1917,6 +2039,10 @@ static int opt_combine_fold_block(Func* f, Block* bl,
try_addr_of_cse(&ctx, in, i);
try_fold_const_convert(&ctx, in, i);
try_combine_exts(&ctx, in, i);
+ /* L2: fuse a same-block cmp feeding the IR_CONDBR terminator into an
+ * IR_CMP_BRANCH (run before try_cmp_imm_fold so the cmp's immediate slot
+ * still folds on the fused branch). */
+ try_fuse_cmp_branch(&ctx, in, i);
try_substitute(&ctx, in, i);
try_addr_synth(&ctx, in, i);
/* W5: same-block redundant-load + pure-compute reuse. Run after
diff --git a/test/opt/o1p_combine.sh b/test/opt/o1p_combine.sh
@@ -195,4 +195,65 @@ EOF
[ "$L6_O0" = "$L6_O1" ] || fail "L6 run O0/O1 differ: $L6_O0 vs $L6_O1"
printf ' L6: run rc=%s (O0==O1)\n' "$L6_O0"
+# ============================================================================
+# L2 — fuse cmp rD; cmp_branch(NE/EQ, rD, #0) -> cmp_branch (boolean-into-branch)
+# ============================================================================
+# When a relational's 0/1 bool was materialized into a register (`cset rD`) and
+# then re-tested by the terminator (`cbnz/cbz rD`), and the cmp + branch land in
+# the SAME MIR block (single-use cmp), try_fuse_cmp_branch rewrites the branch to
+# test the cmp's own relation and NOPs the cmp. (Many `if`s split the cmp and
+# branch into different blocks at no-SSA O1 — those are out of reach for a
+# same-block peephole; L2 captures the co-located subset, e.g. inlined
+# predicates in yyjson.) Structural signal: fewer `cset` on yyjson.
+echo "== L2 cmp;cset;cbnz/cbz -> cmp_branch fusion =="
+if [ -n "${YY_SRC:-}" ] && [ -f "$YY_SRC/yyjson.c" ] && [ -n "$SYS" ]; then
+ # candidate yy.cand.dis was produced by the L6 section above.
+ CAND_CSET="$(grep -cE '\bcset\b' "$WORK/yy.cand.dis" || true)"
+ if [ "$have_base" = 1 ]; then
+ BASE_CSET="$(grep -cE '\bcset\b' "$WORK/yy.base.dis" || true)"
+ [ "$BASE_CSET" -ge 100 ] || fail "L2 red precondition: expected baseline yyjson many cset (got $BASE_CSET)"
+ [ "$CAND_CSET" -lt "$BASE_CSET" ] || fail "L2: candidate did not reduce cset (base=$BASE_CSET cand=$CAND_CSET)"
+ printf ' L2: yyjson cset base=%s -> cand=%s (RED->GREEN; L1/L6/L2 cumulative)\n' "$BASE_CSET" "$CAND_CSET"
+ else
+ printf ' L2: yyjson cset cand=%s (green-only)\n' "$CAND_CSET"
+ fi
+else
+ printf ' L2: SKIP structural (yyjson.c not provisioned or no SDK)\n'
+fi
+
+# L2 correctness — the critical trap is mis-inverting the condition. Exercise
+# every relation in BOTH branch polarities (if(t) and if(!t)) plus FP NaN/inf,
+# forcing materialization, and require kit -O0 == kit -O1.
+cat > "$WORK/l2run.c" <<'EOF'
+static int hits = 0;
+static void use(int x) { hits += x; }
+static long f(int a, int b, double x, double y) {
+ int lt=(a<b); if(lt)use(1); if(!lt)use(2);
+ int le=(a<=b); if(le)use(4); if(!le)use(8);
+ int gt=(a>b); if(gt)use(16); if(!gt)use(32);
+ int ge=(a>=b); if(ge)use(64); if(!ge)use(128);
+ int eq=(a==b); if(eq)use(256); if(!eq)use(512);
+ int ne=(a!=b); if(ne)use(1024); if(!ne)use(2048);
+ unsigned ua=(unsigned)a, ub=(unsigned)b;
+ int ult=(ua<ub); if(ult)use(4096); if(!ult)use(8192);
+ int uge=(ua>=ub); if(uge)use(16384); if(!uge)use(32768);
+ int feq=(x==y); if(feq)use(1<<16); if(!feq)use(1<<17);
+ int flt=(x<y); if(flt)use(1<<18); if(!flt)use(1<<19);
+ return hits;
+}
+int main(void) {
+ long acc = 0;
+ double ds[5] = {-1.0, 0.0, 1.0, 2.0, 3.0/(double)(0.0==1.0 ? 1.0 : 1e308*1e308)};
+ for (int a=-3;a<=3;a++) for (int b=-3;b<=3;b++)
+ for (int i=0;i<5;i++) for (int j=0;j<5;j++) { hits=0; acc=acc*131+f(a,b,ds[i],ds[j]); }
+ return (int)(acc & 0x7f);
+}
+EOF
+"$KIT" cc -O0 -std=c11 "$WORK/l2run.c" -o "$WORK/l2run.o0" >"$WORK/l2run.o0.cc" 2>&1 || fail "L2 run -O0 compile" "$WORK/l2run.o0.cc"
+"$KIT" cc -O1 -std=c11 "$WORK/l2run.c" -o "$WORK/l2run.o1" >"$WORK/l2run.o1.cc" 2>&1 || fail "L2 run -O1 compile" "$WORK/l2run.o1.cc"
+"$WORK/l2run.o0"; L2_O0=$?
+"$WORK/l2run.o1"; L2_O1=$?
+[ "$L2_O0" = "$L2_O1" ] || fail "L2 run O0/O1 differ (mis-inverted condition?): $L2_O0 vs $L2_O1"
+printf ' L2: run rc=%s (O0==O1; all relations x both polarities x FP)\n' "$L2_O0"
+
echo "o1p_combine: OK"
