commit 4ee57ded3d787ea29d4fa7528ae452c9a2ddc814
parent 3835e9d2503c407c83fc7f3195f01bd6ae033c92
Author: Ryan Sepassi <rsepassi@gmail.com>
Date: Wed, 10 Jun 2026 07:17:03 -0700
cleanup: I.5 — iterative order_dfs + drop dead CSemAssignContext
order_dfs: convert the recursive post-order block DFS (pass_analysis.c)
to an explicit-stack iterative walk so a deeply linear CFG cannot overflow
the C stack. Visit/mark/emit order is identical (successors first, then
label-addr targets in inst order, emit when children exhausted), so the
post-order and the dominance/RPO numbering derived from it are unchanged.
CSemAssignContext: the enum was threaded through c_sem_check_assignment's
7 call sites but the body just did (void)ctx — pure dead weight. Drop the
parameter and the enum.
test-opt, test-cg-api (211), test-parse (3880+128), test-pp, test-toy
(1394/0/33, identical to baseline) all green.
Diffstat:
8 files changed, 80 insertions(+), 42 deletions(-)
diff --git a/doc/plan/TODO.md b/doc/plan/TODO.md
@@ -124,9 +124,6 @@ Add new deferred fixes below as they are discovered.
retag-keep-flags op exists. Add the op. (Pairs with I.1.)
- **I.4 — opt passes re-hand-roll the centralized operand-walk.** (The `ranges_overlap`
trampoline part is fixed.)
-- **I.5 — misc confusing constructs:** the recursive `order_dfs` stack hazard, and the
- threaded-but-ignored `CSemAssignContext`. (The obfuscated `max()` and the dep-iter
- field conflation are tracked elsewhere — the latter is T1.12.)
## God-function decompositions (highest risk / lowest ROI — do when next touching)
diff --git a/lang/c/parse/parse.c b/lang/c/parse/parse.c
@@ -914,7 +914,7 @@ static void parse_init_declarator(Parser* p, const DeclSpecs* specs) {
{
const Type* rhs = pcg_top_type(p);
CSemCheck chk =
- c_sem_check_assignment(p->pool, var_ty, rhs, C_SEM_ASSIGN_INIT);
+ c_sem_check_assignment(p->pool, var_ty, rhs);
if (!chk.ok)
perr(p, "%.*s", KIT_SLICE_ARG(kit_slice_cstr(chk.message)));
}
diff --git a/lang/c/parse/parse_expr.c b/lang/c/parse/parse_expr.c
@@ -2290,8 +2290,8 @@ static void parse_postfix(Parser* p) {
parse_assign_expr(p);
to_rvalue(p);
if (param_ty) {
- CSemCheck chk = c_sem_check_assignment(
- p->pool, param_ty, pcg_top_type(p), C_SEM_ASSIGN_EXPR);
+ CSemCheck chk =
+ c_sem_check_assignment(p->pool, param_ty, pcg_top_type(p));
if (!chk.ok)
perr(p, "%.*s", KIT_SLICE_ARG(kit_slice_cstr(chk.message)));
coerce_top_to_type(p, param_ty);
@@ -3455,7 +3455,7 @@ void parse_assign_expr(Parser* p) {
{
const Type* rhs = pcg_top_type(p);
CSemCheck chk =
- c_sem_check_assignment(p->pool, lhs, rhs, C_SEM_ASSIGN_EXPR);
+ c_sem_check_assignment(p->pool, lhs, rhs);
if (!chk.ok) perr(p, "%.*s", KIT_SLICE_ARG(kit_slice_cstr(chk.message)));
}
coerce_top_to_lvalue(p);
diff --git a/lang/c/parse/parse_init.c b/lang/c/parse/parse_init.c
@@ -342,7 +342,7 @@ static void init_field_at(Parser* p, FrameSlot slot, const Type* arr_ty,
{
const Type* rhs = pcg_top_type(p);
CSemCheck chk =
- c_sem_check_assignment(p->pool, f->type, rhs, C_SEM_ASSIGN_INIT);
+ c_sem_check_assignment(p->pool, f->type, rhs);
if (!chk.ok) perr(p, "%.*s", KIT_SLICE_ARG(kit_slice_cstr(chk.message)));
}
coerce_top_to_lvalue(p);
@@ -764,7 +764,7 @@ void init_at(Parser* p, FrameSlot slot, const Type* arr_ty, u32 offset,
to_rvalue(p);
{
const Type* rhs = pcg_top_type(p);
- CSemCheck chk = c_sem_check_assignment(p->pool, ty, rhs, C_SEM_ASSIGN_INIT);
+ CSemCheck chk = c_sem_check_assignment(p->pool, ty, rhs);
if (!chk.ok) perr(p, "%.*s", KIT_SLICE_ARG(kit_slice_cstr(chk.message)));
}
coerce_top_to_lvalue(p);
diff --git a/lang/c/parse/parse_stmt.c b/lang/c/parse/parse_stmt.c
@@ -194,8 +194,7 @@ static void parse_return_stmt(Parser* p) {
to_rvalue(p);
{
const Type* rhs = pcg_top_type(p);
- CSemCheck chk = c_sem_check_assignment(p->pool, p->cur_func_ret, rhs,
- C_SEM_ASSIGN_RETURN);
+ CSemCheck chk = c_sem_check_assignment(p->pool, p->cur_func_ret, rhs);
if (!chk.ok) perr(p, "%.*s", KIT_SLICE_ARG(kit_slice_cstr(chk.message)));
}
/* Convert the value to the function return type, as `return` performs the
diff --git a/lang/c/sem/sem.c b/lang/c/sem/sem.c
@@ -43,11 +43,9 @@ static CSemCheck sem_bad(const char* msg) {
return c;
}
-CSemCheck c_sem_check_assignment(Pool* p, const Type* lhs, const Type* rhs,
- CSemAssignContext ctx) {
+CSemCheck c_sem_check_assignment(Pool* p, const Type* lhs, const Type* rhs) {
const Type* lu;
const Type* ru;
- (void)ctx;
if (!lhs || !rhs) return sem_ok();
lu = type_unqual(p, lhs);
ru = type_unqual(p, rhs);
diff --git a/lang/c/sem/sem.h b/lang/c/sem/sem.h
@@ -3,19 +3,12 @@
#include "type/type.h"
-typedef enum CSemAssignContext {
- C_SEM_ASSIGN_EXPR,
- C_SEM_ASSIGN_INIT,
- C_SEM_ASSIGN_RETURN,
-} CSemAssignContext;
-
typedef struct CSemCheck {
u8 ok;
const char* message;
} CSemCheck;
-CSemCheck c_sem_check_assignment(Pool*, const Type* lhs, const Type* rhs,
- CSemAssignContext);
+CSemCheck c_sem_check_assignment(Pool*, const Type* lhs, const Type* rhs);
CSemCheck c_sem_check_compound_assignment(Pool*, const Type* lhs,
const Type* rhs, int op);
CSemCheck c_sem_check_redeclaration(Pool*, const Type* old_type,
diff --git a/src/opt/pass_analysis.c b/src/opt/pass_analysis.c
@@ -217,34 +217,85 @@ static void block_list_add_unique(Arena* arena, OptBlockList* list, u32 block) {
block_list_add(arena, list, block);
}
-static void order_dfs(OptAnalysis* a, u32 block);
-
-static void order_label_addr_target(OptAnalysis* a, const Inst* in) {
+/* The label-addr target block reachable from one instruction, if any
+ * (computed gotos / local static-data label addresses keep their target block
+ * live). Returns 1 and sets *out when the inst names a target. */
+static int order_inst_label_target(const Inst* in, u32* out) {
switch ((IROp)in->op) {
case IR_LOAD_LABEL_ADDR:
- order_dfs(a, (u32)in->extra.imm);
- break;
+ *out = (u32)in->extra.imm;
+ return 1;
case IR_LOCAL_STATIC_DATA_LABEL_ADDR: {
- CgIrLocalStaticLabelAux* aux =
- (CgIrLocalStaticLabelAux*)in->extra.aux;
- if (aux) order_dfs(a, (u32)aux->target);
- break;
+ CgIrLocalStaticLabelAux* aux = (CgIrLocalStaticLabelAux*)in->extra.aux;
+ if (!aux) return 0;
+ *out = (u32)aux->target;
+ return 1;
}
default:
- break;
+ return 0;
}
}
-static void order_dfs(OptAnalysis* a, u32 block) {
- if (block >= a->nblocks || a->reachable[block]) return;
- a->reachable[block] = 1;
- Block* bl = &a->f->blocks[block];
- for (u32 i = 0; i < bl->nsucc; ++i) order_dfs(a, bl->succ[i]);
- for (u32 i = 0; i < bl->ninsts; ++i)
- order_label_addr_target(a, &bl->insts[i]);
- a->po[a->npo] = block;
- a->po_index[block] = a->npo;
- ++a->npo;
+/* One in-progress DFS frame: the block plus cursors into its successor list
+ * and instruction stream (the two child sources, walked in that order). */
+typedef struct OrderFrame {
+ u32 block;
+ u32 succ_i;
+ u32 inst_i;
+} OrderFrame;
+
+/* Iterative post-order DFS over the block graph: successors first, then the
+ * label-addr targets in instruction order, recording the block once its
+ * children are exhausted. An explicit stack replaces recursion so a deeply
+ * linear CFG cannot overflow the C stack; the visit/mark/emit sequence is
+ * identical to the former recursive walk, so the post-order (and the
+ * dominance/RPO numbering derived from it) is unchanged. */
+static void order_dfs(OptAnalysis* a, u32 entry) {
+ OrderFrame* stack;
+ u32 sp = 0;
+ if (entry >= a->nblocks || a->reachable[entry]) return;
+ stack = arena_array(a->arena, OrderFrame, a->nblocks);
+ a->reachable[entry] = 1;
+ stack[sp].block = entry;
+ stack[sp].succ_i = 0;
+ stack[sp].inst_i = 0;
+ ++sp;
+ while (sp > 0) {
+ OrderFrame* fr = &stack[sp - 1];
+ Block* bl = &a->f->blocks[fr->block];
+ int pushed = 0;
+ while (fr->succ_i < bl->nsucc) {
+ u32 c = bl->succ[fr->succ_i++];
+ if (c < a->nblocks && !a->reachable[c]) {
+ a->reachable[c] = 1;
+ stack[sp].block = c;
+ stack[sp].succ_i = 0;
+ stack[sp].inst_i = 0;
+ ++sp;
+ pushed = 1;
+ break;
+ }
+ }
+ if (pushed) continue;
+ while (fr->inst_i < bl->ninsts) {
+ u32 c;
+ if (order_inst_label_target(&bl->insts[fr->inst_i++], &c) &&
+ c < a->nblocks && !a->reachable[c]) {
+ a->reachable[c] = 1;
+ stack[sp].block = c;
+ stack[sp].succ_i = 0;
+ stack[sp].inst_i = 0;
+ ++sp;
+ pushed = 1;
+ break;
+ }
+ }
+ if (pushed) continue;
+ a->po[a->npo] = fr->block;
+ a->po_index[fr->block] = a->npo;
+ ++a->npo;
+ --sp;
+ }
}
void opt_analysis_build_order(Func* f, OptAnalysis* a) {
