170. VIR in Rust

The same listing

Chapter 91 printed VIR with printFunc. The Rust crate has a print_func. I lowered the same three-line particle program with both engines and compared the listings with diff: no difference. Here is the loop body from either one:

  b6:  ; preds b5
    %18 = index.get %13, %15
    %19 = field.get %18 .x
    %20 = field.get %18 .vx
    %21 = binop + %19, %20
    field.set %18, %21 .x
    br b7

Same blocks, same phis, same numbers. The analyses read the same graph in both engines, and that is what makes parity possible. But the data structures behind the text differ, and the difference is ownership.

Who owns an instruction?

In TypeScript, a block holds its instruction objects, and the module keeps a second list of the very same objects, by id:

interface Block {
  insts: Inst[];   // the objects
  term: Terminator;
  preds: BlockId[];
}
interface Module {
  values: Inst[];  // the same objects
}

Two references to one object are nothing in JavaScript. In Rust a value has one owner (chapter 124), so the port picks one: the module.

pub struct Block {
    pub id: BlockId,
    pub insts: Vec<ValueId>,
    pub term: Terminator,
    pub preds: Vec<BlockId>,
}
pub struct Module {
    pub functions: Vec<Func>,
    pub bindings: Vec<Binding>,
    pub values: Vec<Inst>,
    // language, source, main
}

(Adapted from crates/vir/src/lib.rs.) Every instruction of every function lives in values, and its id is its index. A block is a list of ids. Step through the real VIR of a small sum(n) function:

Four kinds of id

In the TypeScript VIR, type ValueId = number and type BlockId = number are only names for number. I checked with tsc --strict: a BlockId passes as a ValueId without a word. The Rust crate writes the newtype once, as a macro_rules! template (chapter 153), and stamps it out four times. Simplified:

macro_rules! id_type {
    ($name:ident, $prefix:literal) => {
        #[derive(Copy, Clone, PartialEq,
            Eq, PartialOrd, Ord, Hash)]
        pub struct $name(pub u32);
        // + index(), and Debug that
        // prints "%3", "b1", "f0", ...
    };
}
id_type!(ValueId, "%");
id_type!(BlockId, "b");

Each id is 4 bytes. Run it, then uncomment the marked line:

use std::fmt;
use std::mem::size_of;

#[derive(Copy, Clone, PartialEq)]
struct ValueId(u32);
#[derive(Copy, Clone, PartialEq)]
struct BlockId(u32);

impl fmt::Debug for ValueId {
    fn fmt(&self,
        f: &mut fmt::Formatter)
        -> fmt::Result {
        write!(f, "%{}", self.0)
    }
}

struct Inst {
    op: &'static str,
    args: Vec<ValueId>,
}

fn mk(op: &'static str, a: &[u32])
    -> Inst {
    let args =
        a.iter().map(|&n| ValueId(n));
    Inst { op, args: args.collect() }
}

struct Module {
    values: Vec<Inst>,
}

impl Module {
    fn inst(&self, v: ValueId)
        -> &Inst {
        &self.values[v.0 as usize]
    }
}

fn main() {
    let m = Module {
        values: vec![
            mk("param", &[]),
            mk("const 1", &[]),
            mk("binop +", &[0, 1]),
        ],
    };
    // block b1 lists ids, not Insts
    let b1 =
        vec![ValueId(1), ValueId(2)];
    for &v in &b1 {
        let i = m.inst(v);
        println!("{:?} = {} {:?}",
            v, i.op, i.args);
    }
    let b = BlockId(1);
    println!("block b{}", b.0);
    // m.inst(b); // try it: E0308
    let n = size_of::<ValueId>();
    println!("a ValueId is {n} bytes");
}

error[E0308]: mismatched types
   |     m.inst(b);
   |            ^ expected `ValueId`,
   |              found `BlockId`

That is rustc 1.97 on the program above (trimmed). It is chapter 138’s idea, applied to a compiler’s IR instead of a VM’s heap.

Optional fields become variants

A TypeScript Inst carries every possible payload as an optional field, value?, field?, binding?, fields? and more, and code that knows the op asserts the right one is there: m.bindings[i.binding!].name. The Rust Op is an enum whose 22 variants carry their own data:

pub enum Op {
    Const(Const),
    LoadBinding { binding: BindingId },
    FieldGet { field: String },
    IndexGet,
    // ... 22 in all
}

A match on Op::LoadBinding { binding } hands you the binding; there is nothing to assert. op.name() still returns the TypeScript spelling, "index.get", because explain text quotes it. The other types change the same way. Terminator is an enum whose CondBr has an else_ field (else is a keyword). A binding’s owner is Option<FuncId> where TypeScript used -1. And a use is Use::Inst(ValueId) or Use::Term { func, block }, ids again where TypeScript stored object references.

Numbers, the JavaScript way

Explain text puts numbers in sentences, and TypeScript formats them with JavaScript’s String(x). Rust’s {} agrees for everyday numbers and disagrees for large and tiny ones (chapter 149). So the port formats every number in its output with vir::js_number, the same algorithm as drip-rs’s format_number: take the shortest round-trip digits from Rust’s {:e}^[2], then place the point as ECMAScript does^[3]. One case differs from drip-rs: js_number(-0.0) is "0", as String(-0) is, where Drip prints -0.

To see it matter, I compiled the particle program with a minimum size of 1e21 through both engines’ compile. Both printed this line (wrapped here):

· about 100 elements: below the
  1e+21-element threshold, where
  the benefit is too small

With {}, Rust would have written 1000000000000000000000.

Your turn

#[derive(Copy, Clone, PartialEq, Debug)]
struct V(u32);

impl V {
    fn ix(self) -> usize {
        self.0 as usize
    }
}

struct Inst {
    args: Vec<V>,
}

struct Block {
    insts: Vec<V>,
}

struct Module {
    values: Vec<Inst>,
    blocks: Vec<Block>,
}

// uses(m)[v] = the instructions using
// value v, in program order

fn uses(m: &Module) -> Vec<Vec<V>> {
    todo!()
}

What you learned

• The TypeScript VIR shares instruction objects between blocks and values. The Rust IR arena gives them one owner, Module::values, and blocks list typed ids.
• ValueId, BlockId, FuncId and BindingId are u32 newtypes made by one macro; mixing them is E0308, where TypeScript’s number aliases mix silently.
• Ids never move: a removed phi keeps its slot, and walks go through blocks.
• Optional fields become enum variants with their data, and use lists hold ids.
• Numbers in the output go through js_number, so they print as JavaScript prints them.