commit 67344f35ae4b8850515b5741595103ef9bbdd65b
parent 104b3914e3d72c60eef8824d69b03f6ec726aa30
Author: Ryan Sepassi <rsepassi@gmail.com>
Date: Wed, 27 May 2026 11:38:29 -0700
wasm: de-rotate for-loop CFG blocks before structurization
The C frontend emits for-loops in a rotated layout: step block appears
before body in WIR, with the body's closing edge jumping backward to the
step. The structurizer misclassifies the step block as a loop header and
emits a spurious inner `loop`, causing the program to spin forever.
Add derotate_for_loops(), run before scope-depth analysis, that detects
the pattern (JUMP L_body; LABEL L_step; ...; JUMP L_top; LABEL L_body)
and moves the step block to after the body. This turns the body->step
edge into a forward edge so the sole back-edge is body/step -> L_top,
matching the wasm `loop` semantics. The pass re-scans to a fixed point
to handle nested for-loops.
Diffstat:
1 file changed, 108 insertions(+), 0 deletions(-)
diff --git a/src/arch/wasm/structure.c b/src/arch/wasm/structure.c
@@ -408,6 +408,113 @@ static void unroll_switch_islands(WSCtx* x) {
}
}
+/* For-loop de-rotation.
+ *
+ * The C frontend lowers `for (init; cond; step) body` in a single pass, so
+ * the step clause (which appears before the body in source) is emitted into
+ * a block placed BEFORE the body, with the body jumping back to it:
+ *
+ * LABEL L_top // header
+ * <cond>; CMP_BRANCH L_end // (cond optional)
+ * JUMP L_body // skip the step on entry
+ * LABEL L_step // continue target
+ * <step>
+ * JUMP L_top // genuine loop back-edge
+ * LABEL L_body
+ * <body>
+ * JUMP L_step // body -> step (continue path)
+ * LABEL L_end
+ *
+ * In WIR textual order the body's `JUMP L_step` is a backward edge, so the
+ * structurer misclassifies L_step as a loop header and emits a second,
+ * unintended `loop` — the program spins forever. The CFG is reducible; only
+ * the block layout is rotated. We restore a structure-compatible order by
+ * moving the step block to AFTER the body, mirroring how
+ * unroll_switch_islands reorders the switch shape:
+ *
+ * LABEL L_top
+ * <cond>; CMP_BRANCH L_end
+ * LABEL L_body // JUMP L_body dropped; falls through
+ * <body>
+ * JUMP L_step // now a forward edge
+ * LABEL L_step
+ * <step>
+ * JUMP L_top // sole back-edge -> L_top is the loop
+ * LABEL L_end
+ *
+ * The step block ends in an unconditional `JUMP L_top` (no fall-through out)
+ * and is entered only via `JUMP L_step`, so relocating it preserves
+ * semantics. Nested for-loops live entirely inside the body region and are
+ * handled by re-scanning to a fixed point. */
+static int derotate_one_for_loop(WSCtx* x) {
+ WTarget* t = x->t;
+ Heap* h = t->c->ctx->heap;
+ for (u32 j = 0; j < t->nwir; ++j) {
+ if (t->wir[j].op != WIR_JUMP) continue;
+ /* JUMP L_body, with L_body a forward label. */
+ Label xb = t->wir[j].labels[0];
+ if (xb == LABEL_NONE || xb - 1u >= t->nlabels) continue;
+ WLabel* lx = &t->labels[xb - 1u];
+ if (!lx->placed || lx->wir_index <= j) continue;
+ /* Immediately followed by LABEL L_step. */
+ if (j + 1u >= t->nwir || t->wir[j + 1u].op != WIR_LABEL) continue;
+ Label s = t->wir[j + 1u].labels[0];
+ if (s == LABEL_NONE || s == xb) continue;
+ /* Scan the step block for `JUMP L_top; LABEL L_body`, L_top backward. */
+ u32 jt = UINT32_MAX;
+ for (u32 m = j + 2u; m + 1u < t->nwir; ++m) {
+ u8 mop = t->wir[m].op;
+ if (mop == WIR_RET || mop == WIR_UNREACHABLE) break;
+ if (mop != WIR_JUMP) continue;
+ Label cand = t->wir[m].labels[0];
+ if (cand == LABEL_NONE || cand - 1u >= t->nlabels) continue;
+ WLabel* lc = &t->labels[cand - 1u];
+ if (lc->placed && lc->wir_index < j && t->wir[m + 1u].op == WIR_LABEL &&
+ t->wir[m + 1u].labels[0] == xb) {
+ jt = m;
+ break;
+ }
+ }
+ if (jt == UINT32_MAX) continue;
+ /* k = last `JUMP L_step` (the body's closing/continue edges all target
+ * L_step; the textually-last one closes the body, just before L_end). */
+ u32 k = UINT32_MAX;
+ for (u32 m = jt + 1u; m < t->nwir; ++m) {
+ if (t->wir[m].op == WIR_JUMP && t->wir[m].labels[0] == s) k = m;
+ }
+ if (k == UINT32_MAX || k <= jt) continue;
+
+ /* Rebuild: [0..j) drop JUMP at j, [jt+1..k] body, [j+1..jt] step,
+ * [k+1..nwir). */
+ WIR* nw = NULL;
+ u32 nn = 0, ncap = 0;
+ for (u32 m = 0; m < j; ++m) *wir_append(t, &nw, &nn, &ncap) = t->wir[m];
+ for (u32 m = jt + 1u; m <= k; ++m)
+ *wir_append(t, &nw, &nn, &ncap) = t->wir[m];
+ for (u32 m = j + 1u; m <= jt; ++m)
+ *wir_append(t, &nw, &nn, &ncap) = t->wir[m];
+ for (u32 m = k + 1u; m < t->nwir; ++m)
+ *wir_append(t, &nw, &nn, &ncap) = t->wir[m];
+
+ if (t->wir) h->free(h, t->wir, sizeof(WIR) * t->wir_cap);
+ t->wir = nw;
+ t->nwir = nn;
+ t->wir_cap = ncap;
+ for (u32 m = 0; m < t->nwir; ++m) {
+ if (t->wir[m].op != WIR_LABEL) continue;
+ Label l = t->wir[m].labels[0];
+ if (l != LABEL_NONE && l - 1u < t->nlabels)
+ t->labels[l - 1u].wir_index = m;
+ }
+ return 1;
+ }
+ return 0;
+}
+
+static void derotate_for_loops(WSCtx* x) {
+ while (derotate_one_for_loop(x)) { /* re-scan after each reorder */ }
+}
+
static void pass_preds(WSCtx* x) {
WTarget* t = x->t;
for (u32 i = 0; i < t->nwir; ++i) {
@@ -648,6 +755,7 @@ void wasm_structurize(WTarget* t) {
memset(&x, 0, sizeof x);
x.t = t;
unroll_switch_islands(&x);
+ derotate_for_loops(&x);
pass_scope_depth(&x);
pass_preds(&x);
pass_decide(&x);
