181. Access patterns in Rust

Three facts per collection

Here is a small program:

const ps = [];
for (let i = 0; i < 500; i++)
  ps.push({ x: i, y: 0, vx: 1, vy: 2 });
for (let i = 0; i < ps.length; i++) {
  ps[i].x += ps[i].vx;
  ps[i].y += ps[i].vy;
}
let s = 0;
for (let i = 1; i < ps.length; i++)
  s += ps[i - 1].x;
console.log(s, ps[0].y);

and part of what the Rust engine says about it (viscosity explain, release build, rustc 1.97; wrapped):

  · loop at line 4 in <module>() touches 4
    of 4 fields (vy, y, vx, x)
  · loop at line 9 in <module>() touches 1
    of 4 fields (x)
  · about 500 elements
  · 4 of 6 element accesses proven in bounds

All four lines come from one function in crates/core/src/analysis.rs, bounds_loops_and_sizes. Chapter 98 told the story in TypeScript. This chapter reads the Rust, and explains two odd details: the order vy, y, vx, x, and why ps[i - 1] isn’t proven.

One table per loop

Each field access is filed under the loop it happens in, in a plain struct (comments shortened):

pub struct LoopAccess {
    pub func: String,
    pub line: u32,
    pub depth: u32, // 0: outside loops
    pub reads: IndexSet<String>,
    pub writes: IndexSet<String>,
    /// Iterations, if known.
    pub trips: Option<f64>,
}

An IndexMap groups them. Its iteration order is insertion order, like a JavaScript Map^[1]. The key is the function and the header of the innermost loop around the access, or None outside loops (adapted):

for a in &c.accesses {
    let ai = self.inst(a.inst);
    let f = self.func_of[ai.id.index()]
        .expect("live");
    let (loops, _) = &self.cfg[&f];
    let l = loop_of(loops, ai.block);
    let la = by_loop
        .entry((f, l.map(|l| l.header)))
        .or_insert_with(|| /* line, depth,
            trips; empty sets */);
    let set = match a.kind {
        AccessKind::Read => &mut la.reads,
        AccessKind::Write => &mut la.writes,
    };
    set.insert(a.field.clone());
}

or_insert_with builds a table only the first time a key is seen. Option<BlockId> makes “outside any loop” a real key, not a magic block number. Afterwards the tables are sorted by line, stably^[3]. Printed with {:?} (wrapped, func removed), the first two are:

LoopAccess { line: 4, depth: 1,
  reads: {"vy", "y", "vx", "x"},
  writes: {"y", "x"}, trips: None }
LoopAccess { line: 9, depth: 1,
  reads: {"x"}, writes: {}, trips: None }

A third table, depth 0, holds ps[0].y. Explain prints only loops.

Now the order. “First-access order” means the order the analysis visits accesses, not source order. The earlier pass that checks each use of the collection finds element reads with a worklist and work.pop(), which takes the last load of ps first. So line 11 is visited before line 10, and line 6 before line 5. The TypeScript reference pops too, so both engines print (vy, y, vx, x).

struct Table {
    line: u32,
    depth: u32,
    reads: Vec<&'static str>,
    writes: Vec<&'static str>,
}

// Insert once, keep first-seen order
// (what IndexSet does).
fn add(
    v: &mut Vec<&'static str>,
    f: &'static str,
) {
    if !v.contains(&f) {
        v.push(f);
    }
}

fn main() {
    // (loop line, depth, field, write?)
    // in the order the port visits
    // them in this chapter's program.
    let acc = [
        (11, 0, "y", false),
        (9, 1, "x", false),
        (4, 1, "vy", false),
        (4, 1, "y", false),
        (4, 1, "y", true),
        (4, 1, "vx", false),
        (4, 1, "x", false),
        (4, 1, "x", true),
    ];
    let mut ts: Vec<Table> = vec![];
    for (line, depth, f, w) in acc {
        // (The port keys by loop
        // header, not by line.)
        let i = ts
            .iter()
            .position(|t| {
                t.line == line
            });
        let i = match i {
            Some(i) => i,
            None => {
                ts.push(Table {
                    line,
                    depth,
                    reads: vec![],
                    writes: vec![],
                });
                ts.len() - 1
            }
        };
        let t = &mut ts[i];
        if w {
            add(&mut t.writes, f);
        } else {
            add(&mut t.reads, f);
        }
    }
    // Stable, like the port's sort.
    ts.sort_by_key(|t| t.line);
    for t in &ts {
        if t.depth == 0 {
            continue;
        }
        let mut all = t.reads.clone();
        for &f in &t.writes {
            add(&mut all, f);
        }
        println!(
            "line {}: {} of 4 ({})",
            t.line,
            all.len(),
            all.join(", ")
        );
    }
}

Proving an index in bounds

Chapter 104 explained why an unproven access needs __vsc_bc. The proof asks four questions about each index.get. Step through them on a program with four reads:

The second question is is_counting_phi: two operands, a start and a step that is the phi plus 1. SSA doesn’t say which operand comes from the latch, so it tries both orders (adapted):

for (s0, s1) in [(0, 1), (1, 0)] {
    let start = self.inst(phi.args[s0]);
    let step = self.inst(phi.args[s1]);
    // (skip unless step is `phi + 1`)
    let ok = if zero_start {
        is_zero(start)
    } else {
        let seen = &mut HashSet::default();
        self.non_neg_int(start, seen)
    };
    if ok { return true; }
}

Trip counts ask for a start of exactly 0. Bounds only need a non-negative integer, so j = i + 1 counts. non_neg_int accepts whole finite constants from 0 up, + and * of such values, and phis whose operands all are. It begins:

if !seen.insert(v.id) {
    return true;
}
match &v.op {
    Op::Phi => v.args.iter().all(|&a| {
        let a = self.inst(a);
        self.non_neg_int(a, seen)
    }),
    // constants, + and *, unary +

HashSet::insert returns false when the value was already there^[2]. That call does two jobs. It stops the recursion going round a loop (i is a phi of 0 and i + 1, which mentions i), and it answers yes for the repeated value: assume i is fine, and let the rest of the cycle decide.

One Rust detail. The proofs are pushed into a local Vec<bool>, and a second loop zips them into index_gets. The proving loop calls &self methods, which borrow all of self, so it can’t also hold a mutable borrow of the collection. Two phases keep the borrows apart.

About, at most, or unknown

The size is the number of literal elements, plus, for each push, the product of the trip counts of the loops around it. A loop without a constant bound makes it unknown. So does a push inside a function, whose count depends on the calls (f != m.main). The result is known.then_some(size), an Option<f64>.

A push that doesn’t run on every path makes the estimate a maximum. push_runs_on_every_path checks each region from the function down to the innermost loop: the next thing in (an inner header, or the push) must dominate every exit, its return and throw blocks for the function and its latches for a loop.

for (let i = 0; i < 100; i++) {
  if (i % 3 === 0) ps.push({ x: i });
}

Explain says at most 100 elements. The program pushes 34. The next chapter’s planner compares that maximum with its threshold as if it were the size.

Your turn

use std::collections::HashSet;

// One SSA value. Operands are indexes
// into the same slice (typed ids, kept
// as usize here).
enum Op {
    Num(f64),
    // a + b
    Add(usize, usize),
    Phi(Vec<usize>),
    Other,
}

fn non_neg(
    o: &[Op],
    v: usize,
    seen: &mut HashSet<usize>,
) -> bool {
    todo!()
}

fn counting(
    o: &[Op],
    v: usize,
) -> bool {
    todo!()
}

What you learned

• bounds_loops_and_sizes records access tables, bounds proofs and a size for each collection.
• Tables are keyed by function and Option of loop header in an IndexMap. Field order is visit order, in both engines.
• An index is proven when it is a counting phi with a non-negative integer start, guarded by < c.length on a dominating edge.
• non_neg_int handles cycles with seen.insert: a value seen twice is assumed fine.
• A size is about N, at most N (a push on some paths only), or unknown.