commit d35a2b355417977a3a289885fd43c89f1558ecfb
parent a35a48341c3cf53067fb777e0dd7ad3b36e4b92e
Author: Ryan Sepassi <rsepassi@gmail.com>
Date: Tue, 16 Jun 2026 08:37:46 -0700
opt: drop double-cset bool re-normalize at O1 (O1-PATTERNS L4)
An IR_CMP rOuter = (rInner <eq/ne> 0|1) whose source rInner is itself an
IR_CMP (a proven 0/1 bool) re-normalizes an already-0/1 value. When the
outer compares it against imm 0 or 1 with eq/ne, try_drop_double_cmp
rewrites the outer in place:
(t!=0)/(t==1): outer == inner -> IR_COPY rOuter, rInner
(t==0)/(t!=1): outer == !inner -> recompute the inner relation inverted
on the inner's OWN operands (combine_invert_cmp).
The inverted form is skipped when an inner operand was redefined since the
inner cmp OR aliases the inner cmp's own dst (a self-referencing
`cmp w8,#1` writing w8 leaves w8 holding the bool, not the compared
value) — that aliasing guard fixes an initial miscompile of yyjson/sqlite/
lua. Composes with L2: once the outer is a copy/inverted cmp, a branch
consuming it folds on a later fixpoint iteration.
yyjson.c -O1: cset;cmp#0/1;cset triples 573 -> 87 (the residual 87 are the
self-aliasing inner cmps correctly declined), cset 1780 -> 1129, __text
166296 -> 157228 (-5.5%). Battery + cjson/yyjson/sqlite/lua -O1
run-correct; all-relations inversion test O0==O1==clang; test-opt green.
Adds the L4 red-green section to test/opt/o1p_combine.sh (yyjson triple
count + copy/invert/double-not O0==O1 run).
Diffstat:
2 files changed, 162 insertions(+), 3 deletions(-)
diff --git a/src/opt/pass_combine.c b/src/opt/pass_combine.c
@@ -1438,6 +1438,89 @@ static int combine_invert_cmp(CmpOp op, CmpOp* out) {
return 0;
}
+/* ---- L4 (O1-PATTERNS): drop the double-cset bool re-normalize ----
+ *
+ * kit lowers `(a cc b)` to an IR_CMP producing a 0/1 bool in rInner, then a
+ * surrounding `bool != 0` / `if (bool)` context lowers to a SECOND IR_CMP
+ * `rOuter = (rInner <eq/ne> 0|1)` that re-normalizes an already-0/1 value
+ * (`cmp w8,#1; cset w8,eq; cmp w8,#0; cset w8,ne` — yyjson's 573-triple
+ * signature). The outer compare is redundant. When an IR_CMP's source register
+ * (opnds[1]) has its most-recent same-block def being another IR_CMP (so a
+ * proven 0/1 bool) and the outer compares it against imm 0 or 1 with eq/ne,
+ * rewrite the outer in place:
+ *
+ * (t != 0) / (t == 1): outer == inner -> IR_COPY rOuter, rInner
+ * (t == 0) / (t != 1): outer == !inner -> recompute the inner relation
+ * inverted on the inner's OWN operands:
+ * IR_CMP rOuter = (inner.a invert(inner.cc) inner.b)
+ *
+ * The copy form lets copy-prop + DCE retire it; the inverted form drops the
+ * dependency on rInner (so the inner cmp dies if single-use) and replaces two
+ * cmp+cset pairs with one. Both are same-block forward peepholes off the
+ * CombineCtx last-def map. Composes with L2: once the outer is a copy/inverted
+ * cmp, a branch consuming rOuter folds through copy-prop / the L2 fusion on a
+ * later fixpoint iteration. */
+static int try_drop_double_cmp(CombineCtx* ctx, Inst* in, i32 i) {
+ if ((IROp)in->op != IR_CMP || in->nopnds < 3) return 0;
+ if (in->opnds[0].kind != OPK_REG || in->opnds[1].kind != OPK_REG) return 0;
+ if (in->opnds[2].kind != OPK_IMM) return 0;
+ CmpOp outer = (CmpOp)in->extra.imm;
+ if (outer != CMP_EQ && outer != CMP_NE) return 0;
+ i64 k = in->opnds[2].v.imm;
+ if (k != 0 && k != 1) return 0;
+
+ Operand srcb = in->opnds[1];
+ i32 prod_idx = ctx_producer_of(ctx, srcb.cls, srcb.v.reg);
+ if (prod_idx < 0 || prod_idx >= i) return 0;
+ Inst* inner = &ctx->bl->insts[prod_idx];
+ if ((IROp)inner->op != IR_CMP || inner->nopnds < 3) return 0;
+ if (inner->opnds[0].kind != OPK_REG ||
+ !same_phys_reg(&inner->opnds[0], &srcb))
+ return 0;
+ /* The outer dst and the inner bool live in the same register class (both are
+ * 0/1 integer bools); a class crossing would need a real move, not a copy. */
+ if (in->opnds[0].cls != inner->opnds[0].cls) return 0;
+
+ /* Whether the outer result equals the inner bool or its negation:
+ * (t != 0) -> t ; (t == 1) -> t (non-inverted)
+ * (t == 0) -> !t; (t != 1) -> !t (inverted) */
+ int invert = (outer == CMP_EQ && k == 0) || (outer == CMP_NE && k == 1);
+
+ if (!invert) {
+ /* outer == inner: rewrite to a copy off rInner (copy-prop + DCE retire). */
+ in->op = (u16)IR_COPY;
+ in->opnds[1] = inner->opnds[0]; /* = srcb, already in place; keep explicit */
+ in->nopnds = 2;
+ in->extra.imm = 0;
+ ctx->block_change_p = 1;
+ return 1;
+ }
+
+ /* Inverted: recompute the inner relation negated on the inner's own operands.
+ * That requires the inner's operands to still hold their pre-cmp values: an
+ * operand must not have been redefined since the inner cmp AND must not alias
+ * the inner cmp's own destination (a self-referencing `cmp w8,#1` writing w8
+ * leaves w8 holding the bool, not the compared value — recomputing from it
+ * would be wrong). */
+ CmpOp inv;
+ if (!combine_invert_cmp((CmpOp)inner->extra.imm, &inv)) return 0;
+ for (u32 oi = 1; oi < 3; ++oi) {
+ const Operand* p = &inner->opnds[oi];
+ if (p->kind == OPK_REG) {
+ if (same_phys_reg(p, &inner->opnds[0])) return 0;
+ if (ctx_def_changed_since(ctx, p->cls, p->v.reg, prod_idx)) return 0;
+ }
+ }
+ /* Keep the outer's dst (opnds[0]); replace its inputs with the inner's and
+ * its CmpOp with the inverted inner relation. The dst type/class is the same
+ * bool the outer already produced. */
+ in->opnds[1] = inner->opnds[1];
+ in->opnds[2] = inner->opnds[2];
+ in->extra.imm = (i64)inv;
+ ctx->block_change_p = 1;
+ return 1;
+}
+
/* ---- 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
@@ -2039,9 +2122,12 @@ 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). */
+ /* L4: collapse a double-cset bool re-normalize (outer IR_CMP of an inner
+ * 0/1 bool against 0/1) before L2/substitution see the outer's consumer. */
+ try_drop_double_cmp(&ctx, in, i);
+ /* L2: fuse a same-block cmp feeding the IR_CMP_BRANCH terminator into a
+ * direct relational 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);
diff --git a/test/opt/o1p_combine.sh b/test/opt/o1p_combine.sh
@@ -256,4 +256,77 @@ EOF
[ "$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"
+# ============================================================================
+# L4 — drop the double-cset re-normalize (cset rD; cmp rD,#0|#1; cset rD)
+# ============================================================================
+# An IR_CMP `rOuter = (rInner <eq/ne> 0|1)` whose rInner is itself an IR_CMP
+# (a proven 0/1 bool) re-normalizes an already-0/1 value. try_drop_double_cmp
+# rewrites the outer to a COPY of rInner (t!=0 / t==1) or to the inner relation
+# INVERTED on the inner's own operands (t==0 / t!=1; skipped when an inner
+# operand aliases the inner dst). Signature: yyjson's 573 `cset;cmp#0/1;cset`
+# triples.
+echo "== L4 drop double-cset re-normalize =="
+count_triple() { # $1 = disasm file -> stdout count of cset;cmp#0|#1;cset triples
+python3 - "$1" <<'PY'
+import re, sys
+L = open(sys.argv[1]).read().splitlines()
+cset = re.compile(r'\bcset\s+([wx]\d+),')
+cmp01 = re.compile(r'\bcmp\s+([wx]\d+),\s*#[01]\b')
+n = 0
+for i in range(len(L)-2):
+ if cset.search(L[i]) and cmp01.search(L[i+1]) and cset.search(L[i+2]):
+ n += 1
+print(n)
+PY
+}
+if [ -n "${YY_SRC:-}" ] && [ -f "$YY_SRC/yyjson.c" ] && [ -n "$SYS" ]; then
+ CAND_TRIP="$(count_triple "$WORK/yy.cand.dis")"
+ if [ "$have_base" = 1 ]; then
+ BASE_TRIP="$(count_triple "$WORK/yy.base.dis")"
+ [ "$BASE_TRIP" -ge 100 ] || fail "L4 red precondition: expected baseline yyjson many double-cset triples (got $BASE_TRIP)"
+ [ "$CAND_TRIP" -le $((BASE_TRIP / 2)) ] || fail "L4: candidate did not drop enough triples (base=$BASE_TRIP cand=$CAND_TRIP)"
+ printf ' L4: yyjson cset;cmp#0/1;cset triples base=%s -> cand=%s (RED->GREEN)\n' "$BASE_TRIP" "$CAND_TRIP"
+ else
+ [ "$CAND_TRIP" -le 100 ] || fail "L4: candidate yyjson still has $CAND_TRIP triples"
+ printf ' L4: yyjson triples cand=%s (green-only)\n' "$CAND_TRIP"
+ fi
+else
+ printf ' L4: SKIP structural (yyjson.c not provisioned or no SDK)\n'
+fi
+
+# L4 correctness: double/triple bool normalization in both directions, O0==O1.
+cat > "$WORK/l4run.c" <<'EOF'
+static int use_count = 0;
+static void use(int x) { use_count += x; }
+/* Force the cset;cmp;cset re-normalize: a relational bool fed into further
+ * !=0 / ==0 / double-negation boolean contexts. */
+static long f(int a, int b) {
+ int t = (a < b);
+ int u = (t != 0); /* copy form */
+ int v = !(a == b); /* invert form */
+ int w = !!(a > b); /* double-not */
+ int x = ((a <= b) == 0); /* invert via ==0 */
+ if (u) use(1);
+ if (v) use(2);
+ if (w) use(4);
+ if (x) use(8);
+ if (((a >= b) != 1)) use(16);
+ unsigned ua=(unsigned)a, ub=(unsigned)b;
+ int y = !(ua < ub);
+ if (y) use(32);
+ return use_count + u + v + w + x + y;
+}
+int main(void) {
+ long acc = 0;
+ for (int a=-4;a<=4;a++) for (int b=-4;b<=4;b++) { use_count=0; acc=acc*131+f(a,b); }
+ return (int)(acc & 0x7f);
+}
+EOF
+"$KIT" cc -O0 -std=c11 "$WORK/l4run.c" -o "$WORK/l4run.o0" >"$WORK/l4run.o0.cc" 2>&1 || fail "L4 run -O0 compile" "$WORK/l4run.o0.cc"
+"$KIT" cc -O1 -std=c11 "$WORK/l4run.c" -o "$WORK/l4run.o1" >"$WORK/l4run.o1.cc" 2>&1 || fail "L4 run -O1 compile" "$WORK/l4run.o1.cc"
+"$WORK/l4run.o0"; L4_O0=$?
+"$WORK/l4run.o1"; L4_O1=$?
+[ "$L4_O0" = "$L4_O1" ] || fail "L4 run O0/O1 differ (mis-normalized bool?): $L4_O0 vs $L4_O1"
+printf ' L4: run rc=%s (O0==O1; copy + invert + double-not forms)\n' "$L4_O0"
+
echo "o1p_combine: OK"
