commit f97f2c08ba699563f1c112562e79ee6d6d1a93c1
parent c6baf36fafe141c1625be8f320347b9ab92b8b88
Author: Ryan Sepassi <rsepassi@gmail.com>
Date: Mon, 15 Jun 2026 23:20:52 -0700
opt: one-pass O1 branch cleanup + constant cmp_branch folding (O1.md W9+W10)
Diffstat:
5 files changed, 278 insertions(+), 1 deletion(-)
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: 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
$(OPT_TEST_BIN)
@@ -875,6 +875,12 @@ test-opt-redundant-copy-ext: bin
test-opt-redundant-frame-sub: bin
@KIT=$(abspath $(BIN)) bash test/opt/redundant_frame_sub.sh
+# Structural+behavioral check: the one-pass O1 branch cleanup + constant
+# cmp_branch folding (same-target collapse, x==x fold, computed-goto preserved).
+.PHONY: test-opt-o1-branch-cleanup
+test-opt-o1-branch-cleanup: bin
+ @KIT=$(abspath $(BIN)) bash test/opt/o1_branch_cleanup.sh
+
test-opt-tiny-inline: bin $(TINY_INLINE_TEST_BIN)
$(TINY_INLINE_TEST_BIN)
diff --git a/src/opt/opt.c b/src/opt/opt.c
@@ -169,6 +169,12 @@ static void opt_o1_native_prepare(OptImpl* o, Func* f) {
metrics_scope_begin(o->c, "opt.cfg.build_2");
opt_build_cfg(f);
metrics_scope_end(o->c, "opt.cfg.build_2");
+ /* O1.md W9+W10: one-pass branch cleanup (collapse same-target + forward
+ * pass-through blocks once) plus constant cmp_branch folding. Linear: a single
+ * memoized forwarding scan and at most one CFG rebuild (inside the helper).
+ * Folded into the build_2/simplify_local metric span; it is a single linear
+ * scan that does not move sqlite -O1 timing. */
+ opt_jump_cleanup_o1(f);
metrics_scope_begin(o->c, "opt.cfg.simplify_local");
opt_simplify_local(f);
metrics_scope_end(o->c, "opt.cfg.simplify_local");
diff --git a/src/opt/opt.h b/src/opt/opt.h
@@ -29,6 +29,10 @@ typedef enum OptJumpCleanupStage {
OPT_JUMP_CLEANUP_LAYOUT,
} OptJumpCleanupStage;
void opt_jump_cleanup(Func*, OptJumpCleanupStage);
+/* O1.md W9+W10: linear one-pass branch cleanup subset + constant cmp_branch
+ * folding for the no-SSA O1 prepare path (rebuilds the CFG only if it changed
+ * anything). */
+void opt_jump_cleanup_o1(Func*);
void opt_block_cloning(Func*);
void opt_build_reg_ssa(Func*);
void opt_build_ssa(Func*);
diff --git a/src/opt/pass_jump.c b/src/opt/pass_jump.c
@@ -1,5 +1,7 @@
+#include <kit/cg.h>
#include <string.h>
+#include "cg/ir_eval.h"
#include "opt/opt_internal.h"
#define BLOCK_NONE ((u32)~0u)
@@ -587,6 +589,120 @@ static int full_collapse_same_target_branches(Func* f) {
return changed;
}
+/* O1.md W10 — constant `cmp_branch` folding (no SSA).
+ *
+ * Fold an `IR_CMP_BRANCH` whose outcome is statically known by *local* facts
+ * only, then rewrite the terminator to a plain `IR_BR` at the selected
+ * successor (dropping the now-dead CFG edge). Two cases are decidable here:
+ *
+ * 1. both operands are immediates (`OPK_IMM`), or
+ * 2. an integer same-register identity (`x <cmp> x`).
+ *
+ * Both are evaluated through the shared `kit_ir_eval_cmp` integer evaluator,
+ * which masks/sign-extends to the operand type width and returns 0 for any FP
+ * predicate (`op >= CMP_OEQ_F`) — so floating compares (where NaN makes even
+ * `x == x` non-trivial) are never folded. The operand type width also gates the
+ * fold: if the width is unknown we skip. We deliberately do *not* chase
+ * `IR_LOAD_IMM` definitions: at O1 PRegs are mutable, so only direct operands
+ * and the same-reg identity are sound without SSA. */
+static u32 cmp_branch_operand_width(Func* f, const Operand* op) {
+ if (!op) return 0;
+ u32 w = kit_cg_type_int_width((KitCompiler*)f->c, op->type);
+ if (w && w <= 64u) return w;
+ if (kit_cg_type_kind((KitCompiler*)f->c, op->type) == KIT_CG_TYPE_PTR) {
+ u64 size = kit_cg_type_size((KitCompiler*)f->c, op->type);
+ if (size && size <= 8u) return (u32)(size * 8u);
+ }
+ return 0;
+}
+
+/* Returns 1 and writes *taken_out (the i1 compare result) when the branch
+ * condition is locally decidable; 0 to leave the branch alone. */
+static int cmp_branch_const_outcome(Func* f, const Inst* term, int* taken_out) {
+ if ((IROp)term->op != IR_CMP_BRANCH || term->nopnds < 2) return 0;
+ CmpOp op = (CmpOp)term->extra.imm;
+ if (op >= CMP_OEQ_F) return 0; /* never fold FP (NaN). */
+ const Operand* a = &term->opnds[0];
+ const Operand* b = &term->opnds[1];
+
+ /* Integer same-register identity: x <cmp> x. The width only needs to be
+ * known to be a real integer/pointer scalar; the value cancels out. */
+ if (a->kind == OPK_REG && b->kind == OPK_REG && a->v.reg == b->v.reg) {
+ u32 w = cmp_branch_operand_width(f, a);
+ if (!w) return 0;
+ i64 r;
+ if (!kit_ir_eval_cmp(op, w, 0, 0, &r)) return 0;
+ *taken_out = r != 0;
+ return 1;
+ }
+
+ /* Two immediates. */
+ if (a->kind == OPK_IMM && b->kind == OPK_IMM) {
+ u32 wa = cmp_branch_operand_width(f, a);
+ u32 wb = cmp_branch_operand_width(f, b);
+ u32 w = wa ? wa : wb;
+ if (!w) return 0;
+ i64 r;
+ if (!kit_ir_eval_cmp(op, w, a->v.imm, b->v.imm, &r)) return 0;
+ *taken_out = r != 0;
+ return 1;
+ }
+ return 0;
+}
+
+static int one_pass_fold_const_cmp_branch(Func* f) {
+ int changed = 0;
+ for (u32 b = 0; b < f->nblocks; ++b) {
+ Block* bl = &f->blocks[b];
+ if (!bl->ninsts || bl->nsucc != 2) continue;
+ Inst* term = &bl->insts[bl->ninsts - 1u];
+ int taken;
+ if (!cmp_branch_const_outcome(f, term, &taken)) continue;
+ /* succ[0] = taken target, succ[1] = fallthrough/false target. */
+ u32 keep = taken ? bl->succ[0] : bl->succ[1];
+ InstId id = term->id;
+ SrcLoc loc = term->loc;
+ memset(term, 0, sizeof *term);
+ term->op = IR_BR;
+ term->id = id;
+ term->loc = loc;
+ bl->succ[0] = keep;
+ bl->nsucc = 1;
+ changed = 1;
+ }
+ return changed;
+}
+
+/* O1.md W9 — one-pass branch cleanup subset (linear).
+ *
+ * The single-pass, obviously-linear core of `opt_jump_opt` with its
+ * fixed-point loop removed (the loop is intentionally not an O1 fit). Runs the
+ * W10 constant cmp_branch fold first (it can create same-target / pass-through
+ * blocks the W9 passes then clean up), then forwards branch targets through
+ * trivial pass-through blocks once and collapses same-target conditional
+ * branches once. The forwarding walk uses the memoized
+ * `forward_jump_target_ex`, so repeated target queries are amortized linear for
+ * the function; the label-address guard (`has_label_addr_ref`) keeps
+ * computed-goto-visible blocks from being bypassed. At most one CFG rebuild
+ * after the rewrites. */
+void opt_jump_cleanup_o1(Func* f) {
+ if (!f) return;
+ opt_analysis_invalidate(
+ f, OPT_ANALYSIS_DEF_USE | OPT_ANALYSIS_DOM | OPT_ANALYSIS_LOOP);
+
+ int changed = one_pass_fold_const_cmp_branch(f);
+
+ JumpCleanupCtx c = jump_cleanup_ctx(f);
+ changed |= full_forward_branch_targets(&c);
+ changed |= full_collapse_same_target_branches(f);
+
+ if (changed) {
+ opt_analysis_invalidate(
+ f, OPT_ANALYSIS_DEF_USE | OPT_ANALYSIS_DOM | OPT_ANALYSIS_LOOP);
+ opt_build_cfg(f);
+ }
+}
+
void opt_jump_cleanup(Func* f, OptJumpCleanupStage stage) {
if (!f) return;
opt_analysis_invalidate(
diff --git a/test/opt/o1_branch_cleanup.sh b/test/opt/o1_branch_cleanup.sh
@@ -0,0 +1,145 @@
+#!/usr/bin/env bash
+# Structural + behavioral checks for the -O1 one-pass branch cleanup (O1.md W9)
+# and constant cmp_branch folding (O1.md W10):
+#
+# A. W10 same-register integer compare: `if (x == x)` is statically true, so
+# the conditional `cmp wN, wN` + `b.<cc>` is folded away and the taken arm
+# runs unconditionally -- a same-target conditional branch becomes a single
+# unconditional flow.
+# B. W10 dead-arm fold: a `while (x == x)` loop condition is always true, so
+# the per-iteration `cmp wN, wN` / `b.eq` loop-header test disappears (only
+# the real `break` condition's branch survives).
+# C. W9 label-address guard: a computed-goto (`&&label`) program keeps every
+# label block defined (not bypassed by branch forwarding) AND runs
+# correctly through the in-process JIT.
+#
+# All folds are local, target-agnostic, and keep -O1 linear. The disasm checks
+# pin aarch64 (the reference backend) where the mnemonics are stable.
+set -euo pipefail
+
+ROOT="$(cd "$(dirname "$0")/../.." && pwd)"
+KIT="${KIT:-$ROOT/build/kit}"
+WORK="$ROOT/build/test/opt/o1_branch_cleanup"
+mkdir -p "$WORK"
+
+fail() {
+ printf 'o1_branch_cleanup 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 = dis file, $2 = symbol -> 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 + B: W10 constant cmp_branch folding (same-register integer compares).
+# ---------------------------------------------------------------------------
+SRC="$WORK/fold.c"
+cat > "$SRC" <<'EOF'
+/* A: a same-register compare is statically true; the dead else arm collapses
+ * and the taken value loads unconditionally. */
+int ifxx(int x) { if (x == x) return 7; return x; }
+/* B: a same-register loop condition is always true; the loop-header test
+ * folds away, leaving only the real break-condition branch. */
+int loop_xx(int x) { int s = 0; while (x == x) { s++; if (s > 3) break; } return s; }
+EOF
+
+OBJ="$WORK/fold.o"
+"$KIT" cc -target aarch64-linux-gnu -O1 -std=c11 -c "$SRC" \
+ -o "$OBJ" > "$WORK/fold.cc.out" 2>&1
+"$KIT" objdump -d "$OBJ" > "$WORK/fold.dis" 2>&1
+
+# A: ifxx must contain no `cmp wN, wN` (self compare) and no conditional branch
+# -- the always-true compare folded and the taken arm runs unconditionally.
+A="$(fn_body "$WORK/fold.dis" ifxx)"
+[ -n "$A" ] || A="$(fn_body "$WORK/fold.dis" _ifxx)"
+[ -n "$A" ] || fail "ifxx not found in disassembly" "$WORK/fold.dis"
+if printf '%s\n' "$A" | grep -Eq 'cmp\s+(w|x)([0-9]+), \1\2\b'; then
+ fail "ifxx kept a self-compare (W10 did not fold x==x)" "$WORK/fold.dis"
+fi
+if printf '%s\n' "$A" | grep -Eq '\bb\.(eq|ne|gt|ge|lt|le|hi|hs|lo|ls)\b|\bcbz\b|\bcbnz\b'; then
+ fail "ifxx kept a conditional branch (W10 did not fold the dead arm)" \
+ "$WORK/fold.dis"
+fi
+# And the unconditional value (7) must be present.
+printf '%s\n' "$A" | grep -Eq '\bmovz?\b.*0x7\b' \
+ || fail "ifxx lost its unconditional movz #7" "$WORK/fold.dis"
+
+# B: loop_xx must have NO self-compare; the only surviving compare is `cmp wN,#3`
+# (the break test). The folded loop condition would have been `cmp wN, wN`.
+B="$(fn_body "$WORK/fold.dis" loop_xx)"
+[ -n "$B" ] || B="$(fn_body "$WORK/fold.dis" _loop_xx)"
+[ -n "$B" ] || fail "loop_xx not found in disassembly" "$WORK/fold.dis"
+if printf '%s\n' "$B" | grep -Eq 'cmp\s+(w|x)([0-9]+), \1\2\b'; then
+ fail "loop_xx kept the x==x loop-condition self-compare (W10 missed it)" \
+ "$WORK/fold.dis"
+fi
+
+# ---------------------------------------------------------------------------
+# C: W9 label-address guard -- computed goto must keep its label blocks and run.
+# ---------------------------------------------------------------------------
+GSRC="$WORK/cgoto.c"
+cat > "$GSRC" <<'EOF'
+/* A computed-goto dispatch. The branch cleanup must NOT forward/bypass the
+ * &&label-referenced blocks; doing so would corrupt the jump table. p()
+ * returns 1+10+100+1000 == 1111 by walking the table L0 -> Ld via L1 -> L2. */
+int p(void) {
+ static const void *tab[] = { &&L0, &&L1, &&L2, &&Ld };
+ int acc = 0, n = 0;
+ goto *tab[n];
+L0: acc += 1; goto *tab[1];
+L1: acc += 10; goto *tab[2];
+L2: acc += 100; goto *tab[3];
+Ld: acc += 1000;
+ return acc;
+}
+EOF
+
+GOBJ="$WORK/cgoto.o"
+"$KIT" cc -target aarch64-linux-gnu -O1 -c "$GSRC" \
+ -o "$GOBJ" > "$WORK/cgoto.cc.out" 2>&1
+"$KIT" nm "$GOBJ" > "$WORK/cgoto.nm" 2>&1
+# The &&label control-flow-block symbols must be defined (a [dDrR] / text def),
+# never left undefined (U) -- an undefined .Lcfblk means a label target was
+# dropped/bypassed by forwarding.
+if grep -Eq '[[:space:]][uU][[:space:]]+\.Lcfblk' "$WORK/cgoto.nm"; then
+ fail "computed-goto label target is undefined (W9 bypassed a &&label block)" \
+ "$WORK/cgoto.nm"
+fi
+
+# Runtime correctness through the in-process JIT, using a small-total program so
+# the exit code is unambiguous (exit codes are u8; 1111 would wrap mod 256).
+SSRC="$WORK/cgoto_small.c"
+cat > "$SSRC" <<'EOF'
+int p(void) {
+ static const void *tab[] = { &&L0, &&L1, &&Ld };
+ int acc = 0, n = 0;
+ goto *tab[n];
+L0: acc += 2; goto *tab[1];
+L1: acc += 40; goto *tab[2];
+Ld: acc += 0;
+ return acc; /* 2 + 40 == 42 */
+}
+EOF
+for opt in -O0 -O1; do
+ if "$KIT" run "$opt" -e p "$SSRC" > "$WORK/cgoto_small_$opt.out" 2>&1; then
+ rc=0
+ else
+ rc=$?
+ fi
+ if [ "$rc" -ne 42 ]; then
+ fail "computed-goto runtime wrong at $opt: exit $rc (want 42)" \
+ "$WORK/cgoto_small_$opt.out"
+ fi
+done
+
+printf 'o1_branch_cleanup: OK (W10 x==x fold, W10 loop fold, W9 &&label guard)\n'
