Structured control flow

Deep dive

How it works

Parts:

• CFG — at most two successors here (br_table covers more).
• Dominator tree and reverse-postorder (RPO) numbers — idom, num (iterative algorithm).
• Back edge — to a block not later in RPO (reducible graphs only); its target is a loop header.
• Merge node — two or more forward predecessors; needs a Block ending just before it.
• Label stack — open Block(y), Loop(h), If scopes; branch depth = distance from the top.

1. Compute RPO and idom; mark loop headers; count forward predecessors.
2. List each merge node under idom[y], in RPO order.
3. tree(x): open a Loop label if x is a header, then one Block(y) label per merge child, last child outermost.
4. Emit Visit(x) and its terminator. Two successors give an If (itself a label level) with a goto per arm.
5. goto(x, t): back edge gives Br to the Loop; merge node gives Br to its Block; else t has one forward predecessor and is emitted inline.
6. Close the innermost Block, emit the first merge child's tree, repeat; close the Loop last.

WebAssembly spec: label 0 is the innermost construct; a branch to a block or if is a break, to a loop a continue.

CFG: 0->1|2  1->3  2->3  3->4  4->5|7  5->6|4  6->4      Output (from the run, by hand):
Block { Visit 0; If [Visit 1; Br 1] [Visit 2; Br 1] }    Br 1 leaves the Block, to 3
Visit 3
Loop { Visit 4; If [Visit 5; If [Visit 6; Br 2] [Br 2]]  Br 2 = continue, through two Ifs
                   [Visit 7] }

Code

Two reducible graphs (diamond then while with a nested if; while with a diamond body), 1,024 decision patterns each: same block sequence in both forms, every executed Br depth below the label count.

// succ[b]: 0-2 successors; block 0 = entry; a decision bit picks succ[b][0] (1) or [1] (0)
enum Code { Visit(usize), Block(Vec<Code>), Loop(Vec<Code>), If(Vec<Code>, Vec<Code>), Br(usize) }
#[derive(Clone, Copy, PartialEq)] enum Label { Block(usize), Loop(usize), If }
fn postorder(succ: &[Vec<usize>], b: usize, seen: &mut Vec<bool>, post: &mut Vec<usize>) {
    seen[b] = true;
    for &s in &succ[b] { if !seen[s] { postorder(succ, s, seen, post); } }
    post.push(b);
}
// immediate dominators (Cooper-Harvey-Kennedy) and RPO numbers
fn dominators(succ: &[Vec<usize>]) -> (Vec<usize>, Vec<usize>) {
    let (n, mut post) = (succ.len(), vec![]);
    postorder(succ, 0, &mut vec![false; n], &mut post);
    post.reverse();
    let (mut num, mut preds) = (vec![usize::MAX; n], vec![vec![]; n]);
    for (i, &b) in post.iter().enumerate() { num[b] = i; for &s in &succ[b] { preds[s].push(b); } }
    let (mut idom, mut changed) = (vec![usize::MAX; n], true); idom[0] = 0;
    while changed {
        changed = false;
        for &b in &post[1..] {
            let new = preds[b].iter().copied().filter(|&p| idom[p] != usize::MAX).reduce(|mut a, mut c| {
                while a != c {
                    if num[a] > num[c] { a = idom[a] } else { c = idom[c] }
                }
                a
            }).unwrap();
            if idom[b] != new { idom[b] = new; changed = true; }
        }
    }
    (idom, num)
}
struct Ctx<'a> { succ: &'a [Vec<usize>], num: Vec<usize>, header: Vec<bool>, fwd: Vec<usize>, kids: Vec<Vec<usize>> }
impl Ctx<'_> {
    fn back(&self, from: usize, to: usize) -> bool { self.num[to] <= self.num[from] }
    fn depth(l: &[Label], want: Label) -> usize { l.iter().rev().position(|&x| x == want).unwrap() }
    fn tree(&self, x: usize, l: &mut Vec<Label>, out: &mut Vec<Code>) {
        let (ys, start) = (&self.kids[x], out.len());
        if self.header[x] { l.push(Label::Loop(x)); }
        l.extend(ys.iter().rev().map(|&y| Label::Block(y)));
        self.node(x, l, out);
        for &y in ys {
            l.pop();
            let inner = out.split_off(start);
            out.push(Code::Block(inner));
            self.tree(y, l, out);
        }
        if self.header[x] { l.pop(); let inner = out.split_off(start); out.push(Code::Loop(inner)); }
    }
    fn node(&self, x: usize, l: &mut Vec<Label>, out: &mut Vec<Code>) {
        out.push(Code::Visit(x));
        match self.succ[x][..] {
            [] => {}
            [t] => self.goto(x, t, l, out),
            [t, f] => {
                l.push(Label::If); // an If is a label level
                let (mut a, mut b) = (vec![], vec![]);
                self.goto(x, t, l, &mut a);
                self.goto(x, f, l, &mut b);
                l.pop();
                out.push(Code::If(a, b));
            }
            _ => panic!("at most 2 successors in this sketch"),
        }
    }
    fn goto(&self, from: usize, to: usize, l: &mut Vec<Label>, out: &mut Vec<Code>) {
        if self.back(from, to) { out.push(Code::Br(Self::depth(l, Label::Loop(to)))) }
        else if self.fwd[to] >= 2 { out.push(Code::Br(Self::depth(l, Label::Block(to)))) }
        else { self.tree(to, l, out) }
    }
}
fn structure(succ: &[Vec<usize>]) -> Vec<Code> {
    let (idom, num) = dominators(succ); let n = succ.len();
    let mut c = Ctx { succ, num, header: vec![false; n], fwd: vec![0; n], kids: vec![vec![]; n] };
    for p in (0..n).filter(|&p| c.num[p] != usize::MAX) {
        for &s in &succ[p] { if c.back(p, s) { c.header[s] = true } else { c.fwd[s] += 1 } }
    }
    let mut merges: Vec<usize> = (1..n).filter(|&y| c.num[y] != usize::MAX && c.fwd[y] >= 2).collect();
    merges.sort_by_key(|&y| c.num[y]);
    for y in merges { c.kids[idom[y]].push(y); }
    let mut out = vec![]; c.tree(0, &mut vec![], &mut out); out
}
fn bit(bits: u32, k: &mut u32) -> bool { *k += 1; bits >> (*k - 1) & 1 == 1 }
fn run_cfg(succ: &[Vec<usize>], bits: u32) -> Vec<usize> {
    let (mut b, mut k, mut trace) = (0, 0, vec![0]);
    while !succ[b].is_empty() {
        b = if succ[b].len() == 1 || bit(bits, &mut k) { succ[b][0] } else { succ[b][1] };
        trace.push(b);
    }
    trace
}
// Err(n) = branch n labels further out
fn exec(seq: &[Code], depth: usize, bits: u32, k: &mut u32, tr: &mut Vec<usize>) -> Result<(), usize> {
    for c in seq {
        let r = match c {
            Code::Visit(b) => { tr.push(*b); continue; }
            Code::Br(d) => { assert!(*d < depth); return Err(*d) }
            Code::Block(s) => exec(s, depth + 1, bits, k, tr),
            Code::If(t, f) => { let c = bit(bits, k); exec(if c { t } else { f }, depth + 1, bits, k, tr) }
            Code::Loop(s) => loop {
                match exec(s, depth + 1, bits, k, tr) { Err(0) => continue, other => break other }
            },
        };
        match r { Err(0) | Ok(()) => {} Err(n) => return Err(n - 1) }
    }
    Ok(())
}
fn main() {
    let graphs = [ // diamond then while with nested if; while whose body is a diamond
        vec![vec![1, 2], vec![3], vec![3], vec![4], vec![5, 7], vec![6, 4], vec![4], vec![]],
        vec![vec![1], vec![2, 6], vec![3, 4], vec![5], vec![5], vec![1], vec![]],
    ];
    for succ in &graphs {
        let code = structure(succ);
        for bits in 0..1024 {
            let mut tr = vec![]; exec(&code, 0, bits, &mut 0, &mut tr).unwrap();
            assert_eq!(tr, run_cfg(succ, bits), "bits={bits:b}");
        }
    }
}

Compiled and run (stable Rust): passes; adding 1 to a depth trips the assert.

Complexity and constants

• Dominators by iteration: O(n^2) worst case, few passes in practice. Structuring: each block and edge once; output is one node per block plus constructs.
• Measured (one Apple-silicon Mac, release, one run each, chain of n diamonds with 3n+1 blocks): n = 1,000 0.25 ms; n = 10,000 2.7 ms; n = 100,000 (300,001 blocks) 29.5 ms, about 100 ns per block.

Efficiency

• Cost: about 100 ns per block, allocation-bound (measured above); no syscalls or I/O.
• Levers:
  • Append into one output buffer — 29.5 ms vs 5.8 s at 300,001 blocks (measured: my first version returned a Vec per call and copied it up) — always.
  • Dispatch variable instead of node splitting — no code growth (LLVM pass header) — irreducible loops.
• Naive → standard → state of the art: loop { match pc } · any graph, no nesting, slow output; Relooper shapes · several passes, label variable; Ramsey's dominator translation · one pass, no variable on reducible graphs.

Implementation notes

• An If takes a label level in WebAssembly; forgetting it shifts every branch out of an arm.
• SPIR-V also wants each header to name its merge block, and loops a continue target with one back edge: see SPIR-V binary format and its spec rules.

Pitfalls

• Irreducible input: the sketch does not check it (test: each retreating edge's target dominates its source). Fix by node splitting or a dispatch loop: a Loop around a switch on a label local that each entry sets. Binaryen's Relooper and LLVM's WebAssembly pass use that label local.
• Recursion depth follows the dominator tree. The 100,000-diamond run used a 1 GiB-stack thread (default stack untested); use an explicit stack for untrusted input.
• split_off copies: a node with many merge children re-moves earlier output (not measured).

Variants and alternatives

In production

• Web: LLVM's WebAssembly backend inserts block and loop markers after rewriting multi-entry loops with a dispatch label; Binaryen has a ReReloop pass.
• Graphics: SPIR-V requires merge and continue blocks and a reducible structured graph; SPIRV-Cross turns SPIR-V into GLSL, MSL or HLSL (its README).
• Security: decompilers emit if and while, not goto (Yakdan et al.).
• JavaScript output: Emscripten's Relooper emitted JavaScript from LLVM IR.

Implementations

Sources

• Norman Ramsey, Beyond Relooper: recursive translation of unstructured control flow to structured control flow (functional pearl), Proc. ACM Program. Lang. 6 (ICFP), 2022. paper
• Alon Zakai, Emscripten: an LLVM-to-JavaScript compiler, SPLASH '11 Companion, 2011. paper
• Yakdan, Eschweiler, Gerhards-Padilla, Smith, No More Gotos: Decompilation Using Pattern-Independent Control-Flow Structuring and Semantics-Preserving Transformations, NDSS 2015. paper
• WebAssembly Core Specification, instructions. spec
• Khronos, SPIR-V Specification, section "Rules for Structured Control-flow Declarations". spec
• Cooper, Harvey, Kennedy, A Simple, Fast Dominance Algorithm, Rice tech. report, 2001.