82. Inlining

One small function

Here is a particle update, written the way most people would write it, with the per-particle work in its own function:

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

Ask Viscosity what it makes of this, and it refuses to change the layout (explain output, wrapped to fit):

ps (line 1) {x, vx}
  → kept as array of objects
  · unsafe: line 9: an element is passed to
    a function call

Now paste the body of move into the loop yourself:

for (let i = 0; i < ps.length; i++) {
  const p = ps[i];
  p.x += p.vx;
}

Same program, same output. This time:

ps (line 1) {x, vx} → struct of arrays
  · loop at line 5 in <module>() touches
    2 of 2 fields (x, vx)
  · typed Float64Array columns for all 2
    fields
  · about 100 elements
  · 1 of 2 element accesses proven in bounds

Nothing about the work changed. What changed is what the compiler could see. Inside one function, every use of the element is visible. Across a call, the element disappears into code the analysis doesn’t follow.

Pasting a function in

Doing it by hand looks easy. Doing it mechanically, for every call, has two traps, both about names. Step through it:

The renaming really must happen all at once. Inline sub(b, a), where sub(a, b) returns a - b, by replacing one parameter at a time: first a → b gives b - b, then b → a gives a - a. Wrong. Done simultaneously, every parameter is replaced in the original body, and you get the correct b - a.

The price of a copy

If inlining is so useful, why not inline every call?

• Size. Every inlined call duplicates the body. Inline a 50-line function at 20 call sites and you have compiled 1,000 lines. A JIT pays for that in compile time and memory, while the program is running.
• Recursion. Inlining fact into itself produces another call to fact, forever. A compiler can unroll a few levels at most.
• Not knowing the callee. In JavaScript, f(x) calls whatever f holds right now. xs.map(g) calls g from inside map. o.m() calls whatever m the object’s prototype chain finds. A compiler can only paste in code it is sure about.

A JIT has one advantage here: it can guess the callee from what it has seen at run time, speculate, and deoptimize (chapter 66) if the guess ever turns out wrong. An ahead-of-time tool like Viscosity has to prove it instead.

The call graph

To decide what to inline, a compiler needs a map of who calls whom:

main ──► step ──► move ──► clamp
           │
           └────► clamp

Inliners often work bottom-up: first inline the leaves (clamp into move), then the now-bigger move into step, so each function is already optimized when it is copied into its callers. LLVM describes its inline pass this way^[4].

Viscosity follows calls instead

Viscosity does not inline. It is a source-to-source tool, and pasting function bodies all over your program would rewrite far more than the collection code it means to touch. Instead, it gets the view that matters by following a collection into the function it is passed to.

First it finds known functions: functions declared once, whose name is never used for anything but a direct call. Not passed as a callback, not called as a method, not reassigned. For those, it knows every call site, which is a small, exact piece of the call graph. Simplified from analysis.ts:

for (const l of loads.get(f.declaredAs)) {
  for (const u of usesOf(l.id)) {
    const i = u.inst;
    if (i && i.op === 'call' &&
        i.args[0] === l.id &&
        i.note !== 'method') sites.push(i);
    else ok = false;
  }
}
if (ok) callSites.set(f, sites);

Then, when the collection is passed to a known function, the parameter counts as another name for the collection, but only if every call site passes that same collection in that position:

const allSame = sites.every((site) => {
  const a = site.args[k + 1]; // 0 = callee
  return collectionOfLoad.get(a) === c;
});

If so, the analysis keeps going inside the callee as if the code were inline. That is why drift(bodies, 0.5) in the test corpus works: the loop in drift shows up in the explain output as a loop over bodies. If not, it stops. In the corpus program interproc_mixed.js, total is called with two different arrays:

a (line 2) {x} → kept as array of objects
  · unsafe: line 10: passed to total(),
    which is also called with other values

Viscosity doesn’t clone total into a copy for a and a copy for b, which is what inlining would effectively do. And it follows only whole collections into calls, not single elements, which is why move(ps[i]) failed. Try it: inline move by hand below and watch the decision flip.

Your turn

function inline(e, fns) {
  // your code here
  return e;
}

const fns = {
  sq: {
    params: ['a'],
    body: { op: '*', l: { v: 'a' },
      r: { v: 'a' } },
  },
};
const e = { call: 'sq',
  args: [{ v: 'x' }] };
const out = inline(e, fns);
console.log(JSON.stringify(out));

function recursive(fns) {
  // your code here
  return [];
}

const fns = {
  f: { params: ['a'],
    body: { call: 'f',
      args: [{ v: 'a' }] } },
  g: { params: [], body: { n: 1 } },
};
console.log(recursive(fns)); // ['f']

What you learned

• Inlining replaces a call with the callee’s body: parameters bound to arguments simultaneously, locals renamed to fresh names, return turned into the call’s value.
• Its main benefit is visibility: constant propagation, DCE and layout decisions can now see caller and callee together.
• Its costs are code size and compile time, and it is limited by recursion and by not knowing the callee.
• The call graph records who may call whom. JavaScript makes it hard to build, because callees are values.
• Viscosity doesn’t inline. It follows a collection into known functions whose every call site passes that same collection, and bails out when a function sees two different arrays, or when a single element is passed to a call.