kit

commit c3ab7c37ff8954e1c3a358f844e8871cf30d7b7c
parent 9f443e5fdf3521ad8fa83ca1f149b640d4580d3a
Author: Ryan Sepassi <rsepassi@gmail.com>
Date:   Thu, 14 May 2026 11:14:23 -0700

opt: prune unreachable blocks in CFG

Diffstat:
M
src/opt/pass_cfg.c
 | 
76
++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++
M
test/opt/opt_test.c
 | 
99
+++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++

2 files changed, 175 insertions(+), 0 deletions(-)
diff --git a/src/opt/pass_cfg.c b/src/opt/pass_cfg.c
@@ -48,6 +48,74 @@ static int is_terminator(const Inst* in) {
   }
 }
 
+static int scope_control_succ_count(const Block* bl, const Inst* in,
+                                    u8* nsucc_out) {
+  switch ((IROp)in->op) {
+    case IR_SCOPE_BEGIN: {
+      IRScopeAux* aux = (IRScopeAux*)in->extra.aux;
+      if (aux && aux->desc.kind == SCOPE_IF) {
+        *nsucc_out = 2;
+        return 1;
+      }
+      *nsucc_out = bl->nsucc;
+      return bl->nsucc != 0;
+    }
+    case IR_SCOPE_ELSE:
+      *nsucc_out = 1;
+      return 1;
+    case IR_SCOPE_END:
+      *nsucc_out = bl->nsucc;
+      return bl->nsucc != 0;
+    default:
+      return 0;
+  }
+}
+
+static u8* mark_reachable(Func* f) {
+  u8* reachable = arena_zarray(f->arena, u8, f->nblocks ? f->nblocks : 1u);
+  if (f->entry >= f->nblocks) return reachable;
+
+  u32* stack = arena_array(f->arena, u32, f->nblocks ? f->nblocks : 1u);
+  u32 sp = 0;
+  reachable[f->entry] = 1;
+  stack[sp++] = f->entry;
+  while (sp) {
+    u32 b = stack[--sp];
+    if (b >= f->nblocks) continue;
+    Block* bl = &f->blocks[b];
+    for (u32 s = 0; s < bl->nsucc; ++s) {
+      u32 t = bl->succ[s];
+      if (t < f->nblocks && !reachable[t]) {
+        reachable[t] = 1;
+        stack[sp++] = t;
+      }
+    }
+  }
+  return reachable;
+}
+
+static void prune_unreachable(Func* f, const u8* reachable) {
+  for (u32 b = 0; b < f->nblocks; ++b) {
+    if (reachable[b]) continue;
+    Block* bl = &f->blocks[b];
+    bl->insts = NULL;
+    bl->ninsts = 0;
+    bl->cap = 0;
+    bl->preds = NULL;
+    bl->npreds = 0;
+    bl->succ[0] = 0;
+    bl->succ[1] = 0;
+    bl->nsucc = 0;
+  }
+
+  u32 w = 0;
+  for (u32 i = 0; i < f->emit_order_n; ++i) {
+    u32 b = f->emit_order[i];
+    if (b < f->nblocks && reachable[b]) f->emit_order[w++] = b;
+  }
+  f->emit_order_n = w;
+}
+
 void opt_build_cfg(Func* f) {
   for (u32 b = 0; b < f->nblocks; ++b) {
     f->blocks[b].preds = NULL;
@@ -66,6 +134,11 @@ void opt_build_cfg(Func* f) {
     }
     const Inst* last = &bl->insts[bl->ninsts - 1];
     if (!is_terminator(last)) {
+      u8 nsucc = 0;
+      if (scope_control_succ_count(bl, last, &nsucc)) {
+        bl->nsucc = nsucc;
+        continue;
+      }
       bl->nsucc = 0;
       continue;
     }
@@ -90,6 +163,9 @@ void opt_build_cfg(Func* f) {
     }
   }
 
+  u8* reachable = mark_reachable(f);
+  prune_unreachable(f, reachable);
+
   /* Count predecessors. */
   u32* counts = arena_zarray(f->arena, u32, f->nblocks);
   for (u32 b = 0; b < f->nblocks; ++b) {
diff --git a/test/opt/opt_test.c b/test/opt/opt_test.c
@@ -363,6 +363,103 @@ static void opt_liveness_branch(void) {
   tc_fini(&tc);
 }
 
+static void opt_cfg_prunes_unreachable(void) {
+  TestCtx tc;
+  tc_init(&tc);
+  Func* f = new_func(&tc);
+  u32 b0 = f->entry;
+  u32 b1 = ir_block_new(f);
+  u32 dead = ir_block_new(f);
+  ir_note_emit(f, b1);
+  ir_note_emit(f, dead);
+
+  Val live = add_val(f, tc.i32);
+  Val dead_val = add_val(f, tc.i32);
+  Inst* br = ir_emit(f, b0, IR_BR);
+  (void)br;
+  f->blocks[b0].succ[0] = b1;
+  f->blocks[b0].nsucc = 1;
+  emit_load_imm(f, b1, live, tc.i32, 7);
+  emit_ret_val(f, b1, live, tc.i32);
+  emit_load_imm(f, dead, dead_val, tc.i32, 99);
+  emit_ret_val(f, dead, dead_val, tc.i32);
+
+  opt_build_cfg(f);
+  opt_live_info(f);
+
+  EXPECT(f->blocks[dead].ninsts == 0,
+         "unreachable block should have no instructions after cfg cleanup");
+  EXPECT(f->blocks[dead].nsucc == 0,
+         "unreachable block should have no successors after cfg cleanup");
+  EXPECT(f->emit_order_n == 2,
+         "emit_order should skip unreachable block, got %u",
+         (unsigned)f->emit_order_n);
+  EXPECT(f->val_info[dead_val].first_pos == 0,
+         "unreachable value should not get a live range");
+  tc_fini(&tc);
+}
+
+static void opt_cfg_preserves_scope_edges(void) {
+  TestCtx tc;
+  tc_init(&tc);
+  Func* f = new_func(&tc);
+  u32 b0 = f->entry;
+  u32 b_then = ir_block_new(f);
+  u32 b_else = ir_block_new(f);
+  u32 b_join = ir_block_new(f);
+  ir_note_emit(f, b_then);
+  ir_note_emit(f, b_else);
+  ir_note_emit(f, b_join);
+
+  Val v = add_val(f, tc.i32);
+  Val c = add_val(f, tc.i32);
+  Val tv = add_val(f, tc.i32);
+  Val ev = add_val(f, tc.i32);
+  emit_load_imm(f, b0, v, tc.i32, 7);
+  emit_load_imm(f, b0, c, tc.i32, 1);
+
+  Inst* begin = ir_emit(f, b0, IR_SCOPE_BEGIN);
+  IRScopeAux* begin_aux = arena_znew(f->arena, IRScopeAux);
+  begin_aux->desc.kind = SCOPE_IF;
+  begin_aux->desc.cond = op_reg_(c, tc.i32);
+  begin_aux->scope_id = 1;
+  begin_aux->if_then_block = b_then;
+  begin_aux->if_else_block = b_else;
+  begin_aux->if_end_block = b_join;
+  begin->extra.aux = begin_aux;
+  f->blocks[b0].succ[0] = b_then;
+  f->blocks[b0].succ[1] = b_else;
+  f->blocks[b0].nsucc = 2;
+
+  emit_copy(f, b_then, tv, v, tc.i32);
+  Inst* scope_else = ir_emit(f, b_then, IR_SCOPE_ELSE);
+  scope_else->extra.imm = 1;
+  f->blocks[b_then].succ[0] = b_join;
+  f->blocks[b_then].nsucc = 1;
+
+  emit_copy(f, b_else, ev, v, tc.i32);
+  Inst* scope_end = ir_emit(f, b_else, IR_SCOPE_END);
+  scope_end->extra.imm = 1;
+  f->blocks[b_else].succ[0] = b_join;
+  f->blocks[b_else].nsucc = 1;
+  emit_ret_val(f, b_join, v, tc.i32);
+
+  opt_build_cfg(f);
+  opt_live_info(f);
+
+  EXPECT(f->blocks[b0].nsucc == 2,
+         "scope_begin IF should preserve two CFG successors, got %u",
+         (unsigned)f->blocks[b0].nsucc);
+  EXPECT(f->blocks[b_join].npreds == 2,
+         "scope join should have then/else predecessors, got %u",
+         (unsigned)f->blocks[b_join].npreds);
+  EXPECT(bit_has(f->blocks[b_then].live_in, v),
+         "scope then block should remain reachable and see v%u live-in", v);
+  EXPECT(bit_has(f->blocks[b_else].live_in, v),
+         "scope else block should remain reachable and see v%u live-in", v);
+  tc_fini(&tc);
+}
+
 static void opt_regalloc_priority(void) {
   TestCtx tc;
   tc_init(&tc);
@@ -678,6 +775,8 @@ static void opt_emit_no_virtual_alloc(void) {
 }
 
 int main(void) {
+  opt_cfg_prunes_unreachable();
+  opt_cfg_preserves_scope_edges();
   opt_liveness_branch();
   opt_regalloc_priority();
   opt_rewrite_spill_use_def();