No Queue At All: rustc's Dataflow Engine Uses a Bitset and a Rank

TL;DR: Every dataflow framework has a worklist: a queue of dirty blocks. rustc’s has none. The dirty set is a DenseBitSet indexed by reverse postorder rank, and the algorithm always processes the lowest-numbered dirty rank. When a back edge dirties an earlier block, the cursor rewinds. The result: loop-free MIR is analysed in a single pass, and the “queue” is a bit scan.

Dataflow analysis — liveness, maybe-initialization, borrow kills — is everywhere in a compiler. The textbook implementation is a worklist:

while worklist not empty:
    block = worklist.pop()
    new = transfer(block)
    for successor in successors(block):
        if join(successor, new) changed:
            worklist.push(successor)

It is simple, correct, and does a lot of redundant work: a block can be re-evaluated many times, each time re-running the transfer function over its whole body. And it allocates: a VecDeque per analysis, per body.

The algorithm rustc uses instead

// compiler/rustc_mir_dataflow/src/framework/mod.rs:307-325

// Forward analyses use a reverse postorder (`rpo`). Every reachable basic block has a
// *rank*: its position within `rpo`. Rank order is dataflow order: for every edge A -> B
// that is not a back edge, rank(A) < rank(B). This is independent of basic block numbering
// (which depends on the vagaries of CFG construction).
//
// The CFG traversal uses a "min-rank" algorithm. First, all reachable basic blocks are
// marked as dirty. The loop-head invariant is that `curr_rank` always points to the
// minimum-rank dirty block in `rpo`. Before processing that block we mark it as clean. If
// the processing dirties a block with a rank lower than or equal to `curr_rank` (via a
// back edge, which could be an edge-to-self) then `curr_rank` is set to that
// lower-or-equal rank. After the block is processed, if `curr_rank` doesn't point to a
// dirty block it is moved to the next dirty block, and we iterate again.
//
// This algorithm ensures each basic block is processed only after all its dirty
// predecessors (ignoring back edges). When a back edge dirties an earlier block we return
// to that earlier block immediately, which avoids processing later blocks with possibly
// soon-to-be-stale information. Loop-free code is processed in a single pass.

That comment is the algorithm specification, and it is unusually precise about the invariant. Let me restate it:

• Every reachable block has a rank: its position in reverse postorder.
• Rank order is dataflow order: for every non-back edge A→B, rank(A) < rank(B).
• curr_rank always points at the minimum-rank dirty block.
• When processing a block dirties a block of lower-or-equal rank (a back edge, including a self-loop), curr_rank rewinds to that rank.

The implementation

// compiler/rustc_mir_dataflow/src/framework/mod.rs:336-382

let rpo: &[BasicBlock] = body.basic_blocks.reverse_postorder();
let last = rpo.len() - 1;

let mut ranks: IndexVec<BasicBlock, Option<BasicBlockRank>> =
    IndexVec::from_elem_n(None, body.basic_blocks.len());
for (i, &bb) in rpo.iter().enumerate() {
    let rank = if Self::Direction::IS_FORWARD { i } else { last - i };
    ranks[bb] = Some(BasicBlockRank::new(rank));
}

let mut dirty: DenseBitSet<BasicBlockRank> = DenseBitSet::new_filled(rpo.len());
let mut curr_rank = BasicBlockRank::ZERO;

// `state` is not actually used between iterations; this is just an optimization to avoid
// reallocating every iteration.
let mut state = self.bottom_value(body);

loop {
    let i = curr_rank.as_usize();
    let bb = rpo[if Self::Direction::IS_FORWARD { i } else { last - i }];
    debug_assert!(dirty.contains(curr_rank)); // check invariant
    dirty.remove(curr_rank); // invariant temporarily broken

    state.clone_from(&entry_states[bb]);
    let prop = |target: BasicBlock, state: &Self::Domain| {
        ...
        let set_changed = entry_states[target].join(state);
        if set_changed {
            dirty.insert(target_rank);
            curr_rank = curr_rank.min(target_rank);
        }
    };
    Self::Direction::apply_effects_in_block(&self, body, &mut state, bb, &body[bb], prop);

    match dirty.first_set_at_or_after(curr_rank) {
        Some(rank) => curr_rank = rank, // broken invariant re-established
        None => break,                  // no more dirty blocks; finish
    }
}

Four things to notice:

1. The dirty set is a bit set, not a queue. dirty.insert(target_rank) is O(1) with no allocation. dirty.first_set_at_or_after(curr_rank) finds the next dirty block with a word scan and a trailing_zeros.

2. The rewind is one min. curr_rank = curr_rank.min(target_rank) is the entire back-edge handling. Because the cursor is always at the minimum dirty rank, a back edge that dirties an earlier block immediately sends the analysis back there — no stale states propagate forward.

3. state is reused. The comment says it plainly: the state is not used between iterations, so it is clone_from’d rather than reallocated. The domain’s allocation is reused across the whole analysis.

4. Backward analyses fake a postorder. mir::basic_blocks::Cache only stores reverse postorder, because that is what the forward analyses need. Rather than adding a postorder field, the rank map is flipped (last - i). One line, and it gives backward analyses exactly the ordering they need.

Why this beats a worklist

A worklist has two problems. It re-evaluates blocks whose predecessors have not all been processed yet, which means re-running the transfer function over the whole block — and the transfer function is the expensive part (it usually walks statements and updates a bitset domain). And it has no ordering guarantee at all, so it can process a block, then its successor, then discover the block changed, and go back.

The min-rank scheme fixes the ordering: a block is only processed when all of its dirty predecessors (ignoring back edges) have been processed. For loop-free code, that means exactly one pass — every block is visited once, and every transfer function runs once per block. For code with loops, the number of passes is bounded by the loop nesting structure rather than by the convergence of a fixpoint.

The cost is that a DenseBitSet is allocated per analysis (size = number of blocks), where a worklist would have been allocated lazily. But it is one allocation, and it replaces the worklist’s allocation plus its push/pop churn.

The other half of the trick: direction as a type

// compiler/rustc_mir_dataflow/src/framework/direction.rs:7-40

pub trait Direction {
    const IS_FORWARD: bool;
    const IS_BACKWARD: bool = !Self::IS_FORWARD;

    /// Returns the first statement index for this direction. (0 when going forward and
    /// `statements.len()` when going backward.)
    fn first_index(block_data: &mir::BasicBlockData<'_>) -> EffectIndex;

    /// Returns the next index for this direction.
    fn next_index(idx: EffectIndex) -> EffectIndex;
    ...
}

Analysis::Direction is an associated type, so if Self::Direction::IS_FORWARD in the hot loop is a compile-time constant, not a runtime branch. Forward and backward analyses are separate monomorphizations of the entire engine.

And the “two effects per statement” trick — early and primary — is encoded as a two-variant Ord enum:

// compiler/rustc_mir_dataflow/src/framework/mod.rs:466-486

// NOTE: DO NOT CHANGE VARIANT ORDER. The derived `Ord` impls rely on the current order.
#[derive(Clone, Copy, Debug, PartialEq, Eq, PartialOrd, Ord)]
enum Effect {
    /// The "early" effect (e.g., `apply_early_statement_effect`) for a statement/terminator.
    Early,

    /// The "primary" effect (e.g., `apply_primary_statement_effect`) for a statement/terminator.
    Primary,
}

so the cursor can walk either direction over a statement’s two effects with one next_index:

// compiler/rustc_mir_dataflow/src/framework/direction.rs:52-58

fn next_index(idx: EffectIndex) -> EffectIndex {
    match idx.effect {
        Effect::Early => Effect::Primary.at_index(idx.statement_index),
        Effect::Primary => Effect::Early.at_index(idx.statement_index - 1),
    }
}

The early/primary split is exactly what lets the borrow checker implement two-phase borrows without a separate analysis: the reservation is the early effect, the activation is the primary effect.

Results are stored per block, not per point

// compiler/rustc_mir_dataflow/src/framework/results.rs:8-20

/// The results of a dataflow analysis that has converged to fixpoint. It holds the domain values
/// (states) at the entry of each basic block. Domain values in other parts of the block are
/// recomputed on the fly by visitors (i.e. `ResultsCursor`, or `ResultsVisitor` impls).
pub struct Results<'tcx, A>
where
    A: Analysis<'tcx>,
{
    pub analysis: A,
    pub entry_states: EntryStates<A::Domain>,
}

Only block entry states are stored. Everything inside a block is recomputed on demand by re-running the transfer function from the block entry. Memory is O(blocks × domain), not O(points × domain) — for a MixedBitSet<MovePathIndex> domain with 20 000 move paths, that is the difference between megabytes and tens of megabytes.

Where it lives

• compiler/rustc_mir_dataflow/src/framework/mod.rs — iterate_to_fixpoint.
• compiler/rustc_mir_dataflow/src/framework/direction.rs — the Direction trait and the effect index.
• compiler/rustc_mir_dataflow/src/framework/results.rs — the per-block storage.
• compiler/rustc_index/src/bit_set.rs — DenseBitSet and first_set_at_or_after.

Takeaway

A dataflow worklist is a priority queue you did not need. If your graph has a natural order in which information flows — reverse postorder is the standard one — then “process the lowest dirty rank” is both simpler and strictly less work than an unordered worklist, and it gives you the single-pass property for acyclic code for free.