Dataflow analysis

Deep dive

How it works

Parts:

• lattice — a bitset of k facts; order is subset, merge is union (may) or intersection (must)
• gen/kill summary — per block, computed once by scanning its instructions
• transfer function — out = gen | (in & !kill), one per block
• IN/OUT sets — one bitset each per block, 2 x k/8 bytes
• worklist — blocks in reverse postorder (forward) or postorder (backward), re-queued when an output changes

Operations:

1. Pick the lattice: a bitset of k facts. Order is subset; merge is union (may: "on some path") or intersection (must: "on all paths").
2. Pick the direction. Forward: IN[b] = merge(OUT[p]) over predecessors; backward: OUT[b] = merge(IN[s]) over successors.
3. Transfer per block: out = gen | (in & !kill). Compute gen/kill once per block by scanning its instructions (liveness: gen = uses before any def in the block, kill = defs; reaching defs: gen = last def of each variable, kill = all other defs of those variables).
4. Initialise: boundary (entry, or exits for backward) = given set, usually empty. All other values = empty for may, top for must.
5. Worklist seeded with all blocks in reverse postorder (forward) or postorder (backward). Pop, recompute input and output; if output changed, push the flow-successors.
6. The result is the greatest (must) or least (may) fixed point. Per-instruction facts: re-apply the transfer inside a block from its IN/OUT on demand.

        B0: x = in; y = 0              live-in  B0 {}
         |                             live-in  B1 {x,y}
   +---> B1: if x > 0 ----> B3: ret y  live-in  B2 {x,y}
   |     |                             live-in  B3 {y}
   +-- B2: y += x; x -= 1

Code

One solver for all four shapes; the problem is data (direction, merge, gen/kill). Compiled and tested with liveness on the CFG above and available expressions on a loop.

use std::collections::BTreeSet;

pub type Bits = Vec<u64>;

pub struct Problem {
    pub nbits: usize,
    pub succs: Vec<Vec<usize>>, // CFG edges; block 0 is the entry
    pub gen: Vec<Bits>,
    pub kill: Vec<Bits>,
    pub forward: bool,
    pub must: bool,      // true: meet = intersection, start at top; false: union, start at empty
    pub boundary: Bits,  // value at the entry (forward) or at the exits (backward)
}

pub struct Solution {
    pub input: Vec<Bits>,  // forward: IN[b]; backward: OUT[b]
    pub output: Vec<Bits>, // forward: OUT[b]; backward: IN[b]
    pub visits: usize,
}

pub fn bits(nbits: usize, set: &[usize]) -> Bits {
    let mut v = vec![0u64; (nbits + 63) / 64];
    for &i in set { v[i / 64] |= 1 << (i % 64); }
    v
}

pub fn solve(p: &Problem) -> Solution {
    let n = p.succs.len();
    let mut preds = vec![vec![]; n];
    for (b, ss) in p.succs.iter().enumerate() { for &s in ss { preds[s].push(b); } }
    // flow predecessors / successors depend on the direction
    let (from, to) = if p.forward { (&preds, &p.succs) } else { (&p.succs, &preds) };

    // DFS postorder from the entry (iterative); unreachable blocks go last.
    let (mut post, mut seen) = (Vec::with_capacity(n), vec![false; n]);
    for root in std::iter::once(0).chain(0..n) {
        if seen[root] { continue; }
        seen[root] = true;
        let mut stack = vec![(root, 0usize)];
        while let Some(&mut (b, ref mut i)) = stack.last_mut() {
            if let Some(&s) = p.succs[b].get(*i) {
                *i += 1;
                if !seen[s] { seen[s] = true; stack.push((s, 0)); }
            } else { post.push(b); stack.pop(); }
        }
    }
    // forward: reverse postorder; backward: postorder (predecessors-first in flow order)
    let order: Vec<usize> = if p.forward { post.into_iter().rev().collect() } else { post };
    let mut rank = vec![0; n];
    for (r, &b) in order.iter().enumerate() { rank[b] = r; }

    let words = p.boundary.len();
    let init = if p.must { bits(p.nbits, &(0..p.nbits).collect::<Vec<_>>()) } else { vec![0; words] };
    let (mut input, mut output) = (vec![init.clone(); n], vec![init; n]);
    let mut work: BTreeSet<usize> = (0..n).collect(); // ranks; pop_first = earliest in order
    let mut visits = 0;
    while let Some(r) = work.pop_first() {
        let b = order[r];
        visits += 1;
        let inp = if from[b].is_empty() { p.boundary.clone() } else {
            let mut acc = output[from[b][0]].clone();
            for &q in &from[b][1..] {
                for (a, x) in acc.iter_mut().zip(&output[q]) { if p.must { *a &= *x } else { *a |= *x } }
            }
            acc
        };
        let out: Bits = (0..words).map(|i| p.gen[b][i] | (inp[i] & !p.kill[b][i])).collect();
        input[b] = inp;
        if out != output[b] {
            output[b] = out;
            for &s in &to[b] { work.insert(rank[s]); }
        }
    }
    Solution { input, output, visits }
}

Liveness for the diagram (x=0, y=1; gen = upward-exposed uses, kill = defs), checked by assert:

let p = Problem { nbits: 2, succs: vec![vec![1], vec![2, 3], vec![1], vec![]],
    forward: false, must: false, boundary: bits(2, &[]),
    gen:  [vec![], vec![0], vec![1, 0], vec![1]].iter().map(|s| bits(2, s)).collect(),
    kill: [vec![0, 1], vec![], vec![1, 0], vec![]].iter().map(|s| bits(2, s)).collect() };
let s = solve(&p);
assert_eq!(s.output[1], bits(2, &[0, 1])); // IN[B1] = {x, y}
assert_eq!(s.output[0], bits(2, &[]));     // nothing live before B0

Complexity and constants

• Each block's output grows (or shrinks) at most k times, so total re-queues are at most k times the number of edges E; visits at most n + k*E. Round-robin in reverse postorder needs only a few passes for bit-vector problems, about d+3 with d the loop depth (Kam and Ullman).
• Measured (Apple-silicon Mac, release build, the code above): random CFG, 100 000 blocks, 128 facts, forward may problem: 282 728 visits (2.83 per block), order of 30 ms. Same graph in the wrong order (postorder, forward): 10.3 M visits (103 per block), about 0.9 s.
• Memory: 2 x k/8 bytes per block for IN and OUT, plus gen/kill. Here 2 x 16 B x 100k = 3.2 MB for IN and OUT. A visit costs about k/64 word ops per predecessor plus the transfer.
• Cost drivers: number of visits (order), words per set (k), predecessors per block, and allocations (the reference code clones sets per visit; update in place to cut this).

Efficiency

• Cost: on the synthetic graph above (random CFG, 100,000 blocks, 128 facts, Apple-silicon Mac, release build): 2.83 visits per block and order of 30 ms in the right order; 103 visits per block and about 0.9 s in the wrong one. A visit costs about k/64 word operations per predecessor plus the transfer; IN and OUT take 3.2 MB here. Bound: number of visits, then memory bandwidth over the sets.
• Levers:
  • reverse postorder (forward) or postorder (backward) — 103 to 2.8 visits per block, measured above; rustc's MIR engine does the same — every iterative solver
  • bit parallelism — one u64 AND/OR handles 64 facts — gen/kill problems with k in the hundreds
  • per-block gen/kill summaries — iterations never rescan instructions — any block-level framework
  • fewer facts — track only variables that cross a block boundary or have their address taken — shrinks k
  • sparse propagation on SSA — each value visited about once instead of per block — constants and types
• Naive → standard → state of the art:
  • round-robin in arbitrary block order, sets cloned per visit · 103 visits per block, about 0.9 s (measured)
  • worklist in reverse postorder, bitsets updated in place · 2.83 visits per block, order of 30 ms (measured)
  • sparse analysis on SSA, or Datalog engines for interprocedural analyses · work proportional to def-use edges or derived facts (design claim, not measured)

Implementation notes

• Dense bitsets (Vec<u64>) for small k; a chunked or sparse bitset when k is large and blocks touch few facts.
• Dedupe the worklist: a BTreeSet of ranks (as above) or a priority queue with an in-queue flag keeps order and avoids duplicates. A plain FIFO also works but visits more.
• Block IDs in reverse postorder make the order implicit and allow a flat array of states.
• Compute postorder with an explicit stack: recursive DFS overflows on long straight-line CFGs.
• Keep IN/OUT only at block boundaries; materialise per-instruction facts lazily.
• Model exception and switch edges as ordinary CFG edges.

Pitfalls

• Wrong initial value for must analyses: starting at empty makes loops pessimistic (a fixed point, but not the greatest); start at top.
• Entry with predecessors: a jump back to the entry mixes the boundary with the back edge; add a synthetic entry block.
• Several exits: every block without successors gets the boundary value in a backward analysis; do not assume one exit block.
• gen/kill order inside a block: x = x + 1 uses x before defining it; liveness gen must contain x. Mixing the order is the most common liveness bug.
• Non-monotone transfer or infinite-height lattice: may not terminate; use widening (abstract interpretation).
• Non-distributive problems (constant propagation of x + y): the iterative result is a safe over-approximation, not the meet over paths.
• Unreachable blocks: in must analyses they keep top; delete them first.

Variants and alternatives

In production

• Compilers: LLVM has LiveVariables in CodeGen; rustc's borrow and move checkers run on the MIR dataflow framework (rustc_mir_dataflow: maybe-initialized places, live locals, borrows in scope); Cranelift's regalloc2 computes live-in and live-out bitsets per block with a worklist before building live ranges for register allocation.
• Static-analysis and security tools: Clang's flow-sensitive dataflow framework, introduced with an unchecked std::optional access example (docs); CodeQL data-flow and taint queries (docs); Semgrep taint mode (docs).
• Bytecode analysis frameworks: Soot and WALA expose dataflow solvers for JVM bytecode.

Implementations

Sources

• Gary Kildall, A Unified Approach to Global Program Optimization, POPL 1973. paper
• John Kam, Jeffrey Ullman, Global Data Flow Analysis and Iterative Algorithms, JACM 23(1), 1976. paper
• Patrick Cousot, Radhia Cousot, Abstract Interpretation: A Unified Lattice Model for Static Analysis of Programs by Construction or Approximation of Fixpoints, POPL 1977. paper
• Thomas Reps, Susan Horwitz, Mooly Sagiv, Precise Interprocedural Dataflow Analysis via Graph Reachability, POPL 1995. paper
• Anders Moller, Michael Schwartzbach, Static Program Analysis, Aarhus University lecture notes. read
• Keith Cooper, Linda Torczon, Engineering a Compiler, 3rd ed., Morgan Kaufmann 2022 (chapter 9, data-flow analysis).
• rustc dev guide / source, rustc_mir_dataflow framework. code
• Clang, Data flow analysis: an informal introduction. docs