177. A generic dataflow framework

The framework that isn’t there

Chapter 79 ended with a promise: facts on a lattice, a rule per instruction, a merge, and a worklist are the machinery under most of an optimizing compiler, one framework with many instances^[1]. So you might expect the Rust port to have a trait Lattice somewhere. Search engine/rust/crates for trait and you find exactly one: LanguagePlugin (chapter 171).

What it has instead is one fixpoint, written directly over its own state: numeric_inference in crates/core/src/analysis.rs, a port of the same loop in analysis.ts. The other analyses in that file (collections, escapes, bounds) are single passes over use lists, not lattice problems. One instance doesn’t justify a framework, and the parity guarantee (chapter 175) pins the exact order the loop visits things.

So this chapter does two things. It designs a generic framework in Rust: everything in the next three sections is this book’s design, not code in the repo. Then it lines the design up against the real loop.

A lattice is a trait

A lattice needs a starting point, a safe answer and a merge:

pub trait Lattice: Clone + PartialEq {
    // the optimistic start
    fn top() -> Self;
    // claims nothing: always safe
    fn bottom() -> Self;
    // the highest fact below both
    fn meet(&self, o: &Self) -> Self;
}

A problem says how many nodes there are, which nodes each one reads, and its rule. The fact type is an associated type, as Extra is in LanguagePlugin, because each problem has exactly one:

pub trait Problem {
    type Fact: Lattice;
    fn len(&self) -> usize;
    fn deps(&self, n: usize)
        -> Vec<usize>;
    fn transfer(&self, n: usize,
        f: &[Self::Fact]) -> Self::Fact;
}

Nodes are plain usizes, like the typed ids of chapter 170 without the newtype. For “is it a number?”, Fact = bool, top is true, and meet is &&. For chapter 80’s constants, Fact is an enum Top, K(i64) or Varies.

The solver

The worklist solver, from the design (the exercise asks you to write its loop):

pub fn solve<P: Problem>(p: &P)
    -> Vec<P::Fact>
{
    let us = users(p); // reverse deps
    let n = p.len();
    let mut f = vec![P::Fact::top(); n];
    let mut work: Vec<usize> =
        (0..n).rev().collect();
    let mut queued = vec![true; n];
    while let Some(v) = work.pop() {
        queued[v] = false;
        let new = p.transfer(v, &f)
            .meet(&f[v]);
        // if new != f[v]: store it, and
        // push v's users not yet queued
    }
    f
}

Two choices are worth naming. The solver stores transfer(..) met with the old fact, which clamps: a fact can only move down. With a lattice of finite height, each node changes a bounded number of times, so the stack must empty, whatever the transfer does. And it is generic, not &dyn Problem: it needs to build a Vec<P::Fact>, and monomorphization makes every transfer and meet a direct call that rustc can inline^[2].

Viscosity’s loop, as an instance

The real loop, trimmed from analysis.rs:

const MAX_ROUNDS: usize = 1000;
// ...in numeric_inference:
for v in &m.values {
    let optimistic = matches!(v.op,
        Op::Phi | Op::LoadBinding { .. }
        | Op::FieldGet { .. }
        | Op::Param { .. });
    self.num[v.id.index()] =
        optimistic || self.compute(v);
}
let mut converged = false;
for _round in 0..self.max_rounds {
    let mut changed = false;
    // every value, in id order, in
    // place: int, then num; then every
    // binding; then every field
    if !changed {
        converged = true;
        break;
    }
}
if !converged {
    self.num.fill(false);
    self.int.fill(false);
    // ...and every field fact
}

(Chapter 79’s TypeScript sketch was simplified: both engines cap at 1000 rounds and fail closed like this.) Read against the design:

The Python pair is a product lattice: “is a float” and “is an int”, side by side (the optional exercise builds it). The nodes are of three kinds, not one: a binding is numeric if every store to it is, and a field if every record and every write puts a number there.

Step through the same small problem both ways:

Two differences that matter

No clamp on values. Binding and field facts are old && ..., so once false they stay false: that part clamps. Value facts are recomputed from their rules every round, and the first pass reads values not yet computed as false (the code says so). So the loop counts changes in both directions and doesn’t lean on a height argument to stop. It caps the rounds instead.

It fails closed. If round 1000 still changes something, nothing is proven: every value, int and field fact is reset to false. A unit test in analysis.rs pins this with a budget of zero rounds:

let (m, s) = sum_module(); // 1 + 2
let a = Analyzer::new(&m, 0).run();
assert!(!a.is_number(s));

The runnable version below has the same three outcomes: a budget of 1000 is quiet in round 3; a budget of 2 reaches the right facts but never sees a quiet round, so it fails closed; a budget of 0 proves nothing.

trait Lattice: Clone + PartialEq {
    fn top() -> Self;
    fn bottom() -> Self;
    fn meet(&self, o: &Self) -> Self;
}

trait Problem {
    type Fact: Lattice;
    fn len(&self) -> usize;
    fn transfer(
        &self,
        n: usize,
        f: &[Self::Fact],
    ) -> Self::Fact;
}

impl Lattice for bool {
    fn top() -> Self {
        true
    }
    fn bottom() -> Self {
        false
    }
    fn meet(&self, o: &Self) -> Self {
        *self && *o
    }
}

// Viscosity's strategy: whole rounds
// in id order, updating in place.
// Returns the facts and the number of
// the first round that changed nothing.
fn rounds<P: Problem>(
    p: &P,
    max_rounds: usize,
) -> Option<(Vec<P::Fact>, usize)> {
    let n = p.len();
    let mut f = vec![P::Fact::top(); n];
    for r in 1..=max_rounds {
        let mut changed = false;
        for v in 0..n {
            let new = p.transfer(v, &f);
            if new != f[v] {
                f[v] = new;
                changed = true;
            }
        }
        if !changed {
            return Some((f, r));
        }
    }
    None
}

// Fail closed: no fixpoint, no facts.
fn facts<P: Problem>(
    p: &P,
    max_rounds: usize,
) -> Vec<P::Fact> {
    match rounds(p, max_rounds) {
        Some((f, r)) => {
            println!("  quiet: {r}");
            f
        }
        None => {
            println!("  out of rounds");
            let b = P::Fact::bottom();
            vec![b; p.len()]
        }
    }
}

enum N {
    Num,
    Str,
    Add(usize, usize),
    Phi(usize, usize),
}

struct G(Vec<N>);

impl Problem for G {
    type Fact = bool;
    fn len(&self) -> usize {
        self.0.len()
    }
    fn transfer(
        &self,
        n: usize,
        f: &[bool],
    ) -> bool {
        match self.0[n] {
            N::Num => true,
            N::Str => false,
            N::Add(a, b) => {
                f[a] && f[b]
            }
            N::Phi(a, b) => {
                f[a].meet(&f[b])
            }
        }
    }
}

fn main() {
    // %0 = 0    %1 = phi %0, %3
    // %2 = "!"  %3 = %1 + %2
    let g = G(vec![
        N::Num,
        N::Phi(0, 3),
        N::Str,
        N::Add(1, 2),
    ]);
    for budget in [1000, 2, 0] {
        println!("budget {budget}:");
        let f = facts(&g, budget);
        println!("  {f:?}");
    }
}

Your turn

// Facts, ordered. top() is the
// optimistic start, bottom() claims
// nothing, and meet() is the highest
// fact below both.
pub trait Lattice: Clone + PartialEq {
    fn top() -> Self;
    fn bottom() -> Self;
    fn meet(&self, o: &Self) -> Self;
}

// A sparse problem: one fact per node.
pub trait Problem {
    type Fact: Lattice;
    fn len(&self) -> usize;
    // The nodes whose facts n reads.
    fn deps(&self, n: usize)
        -> Vec<usize>;
    // n's fact, from the facts so far.
    fn transfer(
        &self,
        n: usize,
        f: &[Self::Fact],
    ) -> Self::Fact;
}

// The users of each node: who reads it.
fn users<P: Problem>(
    p: &P,
) -> Vec<Vec<usize>> {
    let mut us = vec![vec![]; p.len()];
    for v in 0..p.len() {
        for d in p.deps(v) {
            us[d].push(v);
        }
    }
    us
}

pub fn solve<P: Problem>(
    p: &P,
) -> Vec<P::Fact> {
    let us = users(p);
    let n = p.len();
    let mut f = vec![P::Fact::top(); n];
    // A stack: pop takes node 0 first.
    let mut work: Vec<usize> =
        (0..n).rev().collect();
    let mut queued = vec![true; n];
    todo!()
}

// Facts, ordered. top() is the
// optimistic start, bottom() claims
// nothing, and meet() is the highest
// fact below both.
pub trait Lattice: Clone + PartialEq {
    fn top() -> Self;
    fn bottom() -> Self;
    fn meet(&self, o: &Self) -> Self;
}

// A sparse problem: one fact per node.
pub trait Problem {
    type Fact: Lattice;
    fn len(&self) -> usize;
    // The nodes whose facts n reads.
    fn deps(&self, n: usize)
        -> Vec<usize>;
    // n's fact, from the facts so far.
    fn transfer(
        &self,
        n: usize,
        f: &[Self::Fact],
    ) -> Self::Fact;
}

impl<A: Lattice, B: Lattice> Lattice
    for (A, B)
{
    fn top() -> Self {
        todo!()
    }
    fn bottom() -> Self {
        todo!()
    }
    fn meet(&self, o: &Self) -> Self {
        todo!()
    }
}

What you learned

• engine/rust has no generic dataflow framework: one fixpoint, numeric_inference, and one trait in the whole engine, LanguagePlugin.
• The design: Lattice (top, bottom, meet) and Problem (an associated Fact, deps, transfer) as traits, and a solver generic over P: Problem, monomorphized per problem.
• A clamped worklist only moves facts down, so it stops on a finite lattice.
• The real loop is an instance: nodes are values, bindings and fields; facts are bools (a pair for Python); the strategy is rounds in id order, capped at MAX_ROUNDS = 1000, and it fails closed.