91. VIR: Viscosity’s IR

One data structure

Chapter 73 showed you a VIR listing in passing. Every chapter from here to the end of Part VII reads or writes this IR, so now it is time to know it properly. All of it is in one file, packages/core/src/vir.ts, 176 lines long.

Modules, functions, blocks

A Module holds a list of Funcs (one per function, plus <module> for the top-level code), a list of Bindings, and every instruction by id. A Func is a control-flow graph: a list of Blocks and an entry block. Each block has instructions, its predecessors, and exactly one terminator that says where control goes next.

type Terminator =
  | { kind: 'br'; target: BlockId }
  | { kind: 'condbr'; cond: ValueId;
      then: BlockId; else: BlockId }
  | { kind: 'return';
      value: ValueId | null }
  | { kind: 'throw'; value: ValueId }
  | { kind: 'unreachable' };

An instruction is one record type for every op, a discriminated union in spirit, with optional fields that only some ops use:

interface Inst {
  id: ValueId;      // %7
  op: Op;           // 'field.get'
  args: ValueId[];  // operands
  block: BlockId;
  field?: string;   // for field ops
  fields?: string[]; // for record.new
  operator?: string; // for binop
  binding?: BindingId;
  note?: string;    // for opaque
  src?: SourceRef;  // where it came from
  // … value, name, func, index
}

src is the link back to your text: the plugin’s own syntax node, its start and end offsets, and its line. Emit uses it to know what to replace; explain uses it to say “line 4”.

Now step through a real listing:

const ps = [{ x: 1, vx: 2 }];
let t = 0;
for (let i = 0; i < ps.length; i++)
  t = t + ps[i].x * ps[i].vx;
console.log(t);

func <module>():
  b0:
    %0 = const 1
    %1 = const 2
    %2 = record {x, vx} %0, %1
    %3 = array.new %2
    store ps, %3
    %5 = const 0
    %6 = const 0
    br b1
  b1:  ; preds b0 b3
    %11 = phi %5, %19
    %7 = phi %6, %22
    %8 = load ps
    %9 = field.get %8 .length
    %10 = binop < %7, %9
    condbr %10, b2, b4
  b2:  ; preds b1
    %12 = load ps
    %13 = index.get %12, %7
    %14 = field.get %13 .x
    %15 = load ps
    %16 = index.get %15, %7
    %17 = field.get %16 .vx
    %18 = binop * %14, %17
    %19 = binop + %11, %18
    br b3
  b3:  ; preds b2
    %20 = unop + %7
    %21 = const 1
    %22 = binop + %20, %21
    br b1
  b4:  ; preds b1
    %23 = load console
    %24 = field.get %23 .log
    %25 = call %24, %23, %11
    return

Records and collections are first-class

Most of VIR’s 22 ops are what you would expect from three-address code: const, binop, unop, phi, call, closure. The unusual ones are about data:

• record.new builds a record, with its field names in order: record {x, vx} %0, %1.
• array.empty and array.new build arrays; push appends.
• index.get and index.set read and write an element.
• field.get and field.set read and write a named field.
• intrinsic is a known built-in numeric function, such as Math.sqrt: it returns a number and keeps no reference to its arguments.

Why give these their own instructions? Because they are exactly the questions the layout analyses ask. “Which fields does this loop touch?” becomes: find each index.get on the collection, then collect the field.get and field.set instructions whose object is that element. A lower-level IR, with only “call a function” and “load from an address”, would hide those facts behind patterns every analysis had to recognise again. First-class nodes also hide each language’s spelling: Python’s P(1.0, 2.0) for a dataclass and JavaScript’s { x: 1, vx: 2 } lower to the same record.new.

One detail: ps.length is lowered as field.get .length, in both plugins (Python’s len(ps) included). The analyses recognise that field on a collection. The op list also has a length op, which neither plugin produces today.

Opaque: an honest unknown

JavaScript is enormous: getters, proxies, with, tagged templates. Modelling all of it before shipping anything would take years. So the JavaScript plugin models the subset that matters for data layout, and turns everything else into opaque, with every variable it mentions as an argument. A template literal, for example:

const s = `${ps[0]}`;

lowers to

%15 = index.get %13, %14
%16 = opaque(template) %15

and viscosity explain says:

ps (line 1) {x, vx} → kept as array of
  objects
  · unsafe: line 4: an element is used
    by code Viscosity doesn't model
    (template)

Opaque means “might do anything with these arguments”. Every analysis treats it the worst way: its arguments escape, and its result is unknown. That is conservative soundness: being unsure never leads to a wrong rewrite, only to a missed one. And because the reason is printed, a missed one can be fixed by changing the code.

SSA values and bindings

Look again at the listing: t and i never appear by name. They are SSA values joined by phis. ps and console are bindings, with store and load. Here is why. This function has two counters:

function count(xs) {
  let n = 0;
  let k = 0;
  const bump = () => { n = n + 1; };
  for (const x of xs) {
    bump(); k = k + 1;
  }
  return n + k;
}

k becomes phis, as always. But n is changed inside bump, and a call to bump may happen anywhere. A phi can’t describe “whatever the closure did”, so n stays a binding, and the arrow’s body really contains load n and store n, %6. The JavaScript plugin also makes a binding of any variable that holds an array, so the analyses see every read and write of a candidate collection, as loads they can follow.

Your turn

function term(t) {
  if (t.kind === 'br')
    return 'br b' + t.target;
  if (t.kind === 'condbr')
    return 'condbr %' + t.cond + ', b' +
      t.then + ', b' + t.else;
  return t.value === null ? 'return'
    : 'return %' + t.value;
}

function printFunc(f) {
  // your code here
}

function fieldsTouched(insts, arr) {
  // your code here
  return [];
}

What you learned

• A VIR module has functions (CFGs of blocks), bindings, and every instruction by id. Each block ends in one terminator.
• VIR is language-neutral SSA: uncaptured locals are values joined by phis; captured, module-level and array-holding variables are bindings with load and store.
• Record and collection nodes (record.new, push, index.get, field.get, field.set, …) make the layout questions direct, and hide each language’s spelling.
• opaque stands for anything not modelled. Treating it as the worst case keeps every analysis sound.
• Every instruction keeps a source reference, for emit and explain.