73. What an IR is for

Too many ways to say one thing

Viscosity wants to turn your arrays of objects into struct-of-arrays storage, the layout that won in Part II. Before it can, it has to answer questions about your program. Which fields of a particle are read? Is any particle passed to code we can’t see? Is this loop hot?

Try answering the first one by looking at JavaScript source. All of these add vx to x:

p.x += p.vx;
p.x = p.x + p.vx;
p["x"] = p["x"] + p.vx;
const { vx } = p; p.x += vx;

An analysis written over source text, or even over the syntax tree, needs a case for every one of them, and for the next spelling someone invents. Each new question would need all those cases again. Compilers don’t do that. They translate the program, once, into a form with far fewer cases, and then ask every question there.

A form built for questions

Step through one small function in four forms. Watch what each form makes easy, and what it hides.

function dist(a, b) {
  if (a > b) return a - b;
  return b - a;
}

The source is for people. The tree is for the parser and the tree-walker: it keeps the program’s nesting. The IR listing and its graph are for the compiler. Each instruction does one small thing and gives its result a name, %2 or %3. And the control flow, which in the tree was implied by what an If node means, is now written down as jumps between labelled blocks.

Lowering

Turning the tree into that listing is called lowering: the program is translated into a lower-level form, closer to the machine and further from the syntax. Here is what Viscosity’s JavaScript front end makes of p.x += p.vx, inside function m(p):

func m(%0):
  b0:
    %0 = param
    %1 = field.get %0 .x
    %2 = field.get %0 .vx
    %3 = binop + %1, %2
    field.set %0, %3 .x
    return

The compound += is gone. It became a read, an add and a write, the same three steps that p.x = p.x + p.vx lowers to, instruction for instruction. Two spellings, one meaning, one form. (Not every spelling collapses this far: p["x"] becomes index.get with the constant "x", and the destructuring line is opaque, which you’ll meet below.) Try another pair: x = x + 1 and x += 1 lower to identical VIR, %2 = binop + %0, %1.

But x++ doesn’t. It lowers with one extra instruction:

%1 = unop + %0
%2 = const 1
%3 = binop + %1, %2

That unop + is not a mistake. x++ converts x to a number first, and x += 1 doesn’t, so with a string they really do differ:

let a = "5";
a += 1;
let b = "5";
b++;
console.log(a, b);

This is what lowering is for. It erases differences that don’t matter, and it makes the ones that do matter visible as instructions, so no analysis has to remember a corner of the language.

What VIR looks like inside

VIR’s instructions are a discriminated union, tagged by op. Here is a trimmed version of the list in packages/core/src/vir.ts:

type Op =
  | 'const' | 'param' | 'phi'
  | 'binop' | 'unop'
  | 'field.get' | 'field.set'
  | 'index.get' | 'index.set'
  | 'record.new' | 'push' | 'length'
  | 'call' | 'closure'
  | 'opaque';

Notice what is there: records, fields, indexing and push. Viscosity cares about arrays of objects, so they are first-class instructions instead of patterns an analysis would have to recognise. Notice too what is not there: nothing says “JavaScript”. The front end for a language does the lowering; every analysis after it only sees VIR. (A phi merges values where paths join. It gets a chapter of its own, 77.)

And the last op is the honest one. Anything the lowering doesn’t model, like delete o.x, becomes opaque, with every variable it mentions as an argument:

%1 = opaque(delete) %0

Opaque means “might do anything with these”. The analyses treat its arguments as lost to unknown code. That keeps them safe without understanding all of JavaScript: when in doubt, Viscosity leaves the program alone.

Your turn

function lower(node) {
  return node;
}

function lowerFor(node) {
  return [node];
}

What you learned

• An IR is the compiler’s working form of a program, designed for analysis: values are named, control flow is explicit, and there are few kinds of instruction.
• Source and trees are too varied, and stack bytecode hides where values come from. An IR sits in between.
• Lowering translates to a lower-level form. It erases spellings that mean the same (+= and = x +) and makes real differences visible (x++ converts to a number first).
• VIR is language-neutral, with records and arrays as first-class instructions, and opaque for anything it doesn’t model.

Next: the shape of a single VIR instruction, three-address code.