85. Escape analysis

Two suites, two verdicts

Chapter 23 ended on a puzzle. Two benchmark suites both turn struct of arrays back into objects, one per element. In this book’s benchmark run, one of them lost badly and the other didn’t lose at all:

The only difference is what happens to the object afterwards. In materialize it is stored in an array that outlives the loop. In get-objects, consume(p) reads six fields and drops it. Chapter 67 showed V8 noticing that and replacing the object with its fields (scalar replacement).

Viscosity faces the same question from the other side. Before it turns ps into columns, it must be sure no part of the program can tell.

Escaping

Picture a value as having an inside and an outside. Inside is the code the compiler is looking at and can rewrite. A value escapes when a reference to it reaches somewhere outside: a function the compiler can’t see into, a variable or property that someone else reads, the caller.

function f(ps) {
  const p = ps[0];
  let s = p.x + p.vx; // stays inside
  log(p);             // escapes: a call
  return p;           // escapes: a return
}

Tracing the uses

Viscosity works on its SSA IR, where every value has a list of the instructions that use it. To check a collection it starts from every load of the array and walks those lists. Some uses are fine because Viscosity knows how to rewrite them: push of a fresh object literal, .length, and ps[i]. But ps[i] produces a new value, the element, so its uses must be walked too. Step through it:

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

This is a worklist again, like the dataflow chapters: values to check go in, and checking one can add more. Here is the element part, from packages/core/src/analysis.ts, simplified:

for (const u of usesOf(el)) {
  const i = u.inst;
  const onEl = i && i.args[0] === el;
  if (onEl && i.op === 'field.get') {
    accesses.push(read(i));
    continue;
  }
  if (onEl && i.op === 'field.set') {
    accesses.push(write(i));
    continue;
  }
  bailouts.push(
    'an element is ' + describeUse(u));
}

Notice onEl. ps[i].x = 5 and box.last = ps[i] are both field.set. In the first, the element is the object being written to, which is fine. In the second, it is the value being stored, so it escapes into box.

Naming the escape site

A bailout that only said “unsafe” would be useless. describeUse turns each escaping use into a reason a person can act on. Simplified, with the line numbers left out:

switch (i.op) {
  case 'call':
    return 'passed to a function call';
  case 'storeBinding':
    return 'stored in another variable';
  case 'field.set':
    return 'stored into an object property';
  case 'index.set':
    return 'stored into an array';
  case 'record.new':
    return 'put inside another object';
  case 'binop':
    return 'compared or combined';
  case 'opaque':
    return 'used by code Viscosity ' +
      "doesn't model";
  case 'phi':
    return 'merged with other values';
}

Returns don’t appear here, because a return is a block terminator rather than an instruction; it gets its own message, “returned or branched on”. Here is what viscosity explain really prints for three small changes to the program in the diagram:

// return ps[0] from a function
· unsafe: line 5: an element is
  returned or branched on in first()

// box.last = ps[99];
· unsafe: line 7: an element is stored
  into an object property

// console.log(ps[1] === ps[2]);
· unsafe: line 6: an element is compared
  or combined with "==="

The comparison is the subtle one. Nothing is stored anywhere, but === asks about identity, and after the rewrite there are no element objects to be identical. Two more sites are there for safety. opaque is the IR’s name for anything Viscosity doesn’t model, so every argument must be assumed to escape. A phi merges an element with other values, as in best = ps[i] inside an if. Viscosity doesn’t track what flows out of a merge, so it counts the merge itself as an escape.

// Array of objects: real objects.
const aos = [{ x: 1 }, { x: 2 }];
const a = aos[0];
console.log(a === aos[0]);

// SoA: rebuilding gives a NEW object.
const soa = { x: [1, 2] };
function get(i) {
  return { x: soa.x[i] };
}
console.log(get(0) === get(0));
// Same data, a different answer. A
// program that compares elements can
// tell the layout changed.

Calls that aren’t escapes

A call is usually an escape, but not always. If step(qs) is a function declared once and only ever called directly, Viscosity knows every call site. When all of them pass ps, the parameter qs is ps, so it joins the worklist and its uses are checked inside step:

ps (line 1) {x, vx} → struct of arrays
  · loop at line 5 in step() touches
    2 of 2 fields (x, vx)

That is points-to reasoning from chapter 84 on a small scale: qs points to exactly one collection. Passing an element to a function, as in move(ps[i]), is still reported as an escape today. Try it, and then try removing the escape:

Your turn

function firstEscape(el, uses) {
  // your code here
  return null;
}

console.log(firstEscape('e', [
  { op: 'field.get',
    args: ['e'], line: 4 },
  { op: 'call',
    args: ['log', 'e'], line: 6 },
]));

function escapesVia(v, uses) {
  // your code here
}

const uses = {
  ps: [{ op: 'length' },
       { op: 'call', to: 'qs' }],
  qs: [{ op: 'field' }],
};
console.log(escapesVia('ps', uses));

What you learned

• Escape analysis decides whether a reference can leave a region of code. If it can’t, the compiler may change how the object is stored.
• The escape sites are calls, stores into variables, properties, arrays or other objects, and returns. Viscosity also counts identity comparisons, unmodelled (opaque) operations and phis.
• Checking is a worklist over def-use lists: an element produced by ps[i] adds its own uses to the list.
• Position matters: an element being written to is safe; an element being stored escapes.
• A known function whose every call passes the same collection is followed, not counted as an escape.
• V8 escapes less because it inlines first and can deoptimize. Viscosity must prove safety ahead of time, so it is more conservative.