93. Lowering JavaScript to VIR

From a tree to a graph

Chapter 92 left you with an ESTree: a ForOfStatement holding a VariableDeclaration, an Identifier and an ExpressionStatement. That tree mirrors how the code was written. The analyses in the next chapters ask questions about how it runs: which values flow where, which loop reads which field, what can reach a call. Those questions need VIR, the SSA graph from chapter 91.

The front-end walks the tree once and builds that graph, in frontend-js/src/lower.ts, about 600 lines.

First, find out what every name means

Before emitting anything, resolve.ts walks the tree with a stack of scopes, as your Drip resolver did in chapter 42. It maps every Identifier node to the binding it refers to, and records three facts per binding:

interface JsBinding {
  name: string;
  kind: 'const' | 'let' | 'var'
    | 'param' | 'function' | /* … */;
  owner: Node;  // function that declares it
  usedIn: Set<Node>; // functions using it
  reassigned: boolean;
  assignedInTry: boolean;
  init: Node | null;
}

usedIn answers “is this captured?”: if any function in the set is not the owner, a closure reads or writes it. assignedInTry is set when an assignment sits inside a try block.

SSA value or binding?

Then comes the most important decision in the file. For each binding, lower.ts picks one of two representations (simplified):

const simple = kind is const, let, var,
  param or catch;
if (simple && !capturedElsewhere
    && !b.assignedInTry
    && !isArrayInit(b.init))
  ssa.add(b);

An SSA variable is never stored anywhere. Writing it just records “s is now %8”, and reading it asks Braun’s algorithm (chapter 78) for the current value, building phis at joins. Everything else is a binding, read and written with explicit load and store instructions. Here is the real VIR for a short program, from printFunc:

let s = 0;
let n = 0;
for (let i = 0; i < 3; i++) s = s + i;
const f = () => n;

b0:
  %0 = const 0
  %1 = const 0
  store n, %1
  %3 = const 0
  br b1
b1:  ; preds b0 b3
  %7 = phi %0, %8
  %4 = phi %3, %11
  …
b2:  ; preds b1
  %8 = binop + %7, %4

s and i vanished into values and phis. n is read by the arrow function, so it stays a binding with a real store. Captured variables must be bindings: the closure may read them at any time, long after any SSA value was current.

Two rules look odd at first. A variable assigned in a try is a binding because the lowering doesn’t model the edges an exception can take; with SSA, a catch block could see the wrong value. And a variable initialized with an array, such as const ps = [], is always a binding, even when it never changes. That is deliberate: the collection analysis in chapter 96 finds collections by scanning stores and loads, so every read of ps must show up as a load.

Expressions return values

The heart of the file is expr(e), one switch over ESTree node types. Each case lowers its children and returns the ValueId of the result. The cases that matter most for layouts make VIR’s first-class record and collection nodes:

case 'ObjectExpression':
  // plain { a: 1, b: x } only
  return fb.emit('record.new', values,
    { fields });
case 'ArrayExpression':
  if (e.elements.length === 0)
    return fb.emit('array.empty', []);
  return fb.emit('array.new', elems);

An object literal becomes record.new only if every property is a plain key: value with a name or string key, no computed keys, no methods, getters or spreads, and no duplicates. A call xs.push(v) becomes a push node, and Math.sqrt(x) an intrinsic, but only if Math resolves to the global (a local variable called Math could be anything). Other method calls become a field.get and a call with the receiver.

Assignments go through two helpers. assignTo handles =. readTarget handles += and ++: it lowers the object (and index) once, then returns a get and a set that share them, just as JavaScript evaluates p.x once in p.x += 1. For ps[0].x++ the real VIR is:

%13 = index.get %11, %12
%14 = field.get %13 .x
%15 = unop + %14
%16 = const 1
%17 = binop + %15, %16
field.set %13, %17 .x

The unop + is JavaScript’s ToNumber: x++ returns the old value as a number, even if x held the string "5".

Loops become blocks

Statements add blocks. A while or for loop gets four: head, body, continue and exit, the targets of continue and break. Before any statement, function declarations are hoisted: each is lowered into its own VIR function, and a closure is stored in its binding at the very top, so calling sq(3) above function sq(n) {…} works.

The interesting loop is for (const p of ps). In JavaScript it runs the iterator protocol^[3]. When the right side is a plain identifier, Viscosity lowers it to an index loop instead. For arrays that visits the same elements in the same order (as long as nobody replaces the built-in array iterator), and it makes element i an ordinary index.get that the analyses already understand. Step through it, with the real VIR:

If the right side is anything else, say for (const p of make()), the test and the element both become opaque, and no analysis can claim to know what p is.

Opaque: the escape hatch that keeps it sound

The front-end does not understand classes, template literals, destructuring, delete, optional chains, regular expressions or spread arguments. It doesn’t need to. Each of them becomes one instruction:

const opaque = (n, note) =>
  fb.emit('opaque', mentioned(n),
    { note, src: src(n) });

mentioned(n) walks the subtree and reads every variable it names: not property names, not object keys, and not globals. A spread makes an object literal opaque, so this is the real VIR for one:

let t = 0;
const d = Math.sqrt(t * t);
const o = { a: 1, ...d };

%0 = const 0
%1 = binop * %0, %0
%2 = Math.sqrt(%1)
%3 = opaque(object literal) %2

The 1 isn’t even lowered, but d (that is, %2) is an argument: whatever the spread does, it might do it to d.

This is how a 600-line front-end can face all of JavaScript. Missing a construct costs performance, not correctness, as long as nothing is ever dropped silently.

Your turn

function lower(stmts) {
  const out = [];
  // your code here
  return out;
}

console.log(lower([
  ['let', 'a', 1],
  ['set', 'a', ['+', 'a', 2]],
  ['log', 'a'],
]));

function mentioned(node) {
  const out = [];
  function visit(n) {
    if (!n) return;
    if (typeof n !== 'object') return;
    if (Array.isArray(n)) {
      n.forEach(visit);
      return;
    }
    if (n.type === 'Identifier') {
      out.push(n.name);
      return;
    }
    for (const k in n) visit(n[k]);
  }
  visit(node);
  return out;
}

What you learned

• AST-to-IR translation turns each expression into a value and each statement into instructions and blocks.
• Lowering resolves scopes first: usedIn, reassigned and assignedInTry decide how each variable is represented.
• Local, uncaptured variables become SSA values. Captured ones, ones assigned in try, and every array variable become bindings with explicit load/store.
• for (const p of ps) becomes an index loop: a phi for the index, a length test and an index.get.
• Unmodelled code becomes opaque, with every mentioned variable as an argument, so the analyses stay sound.