87. Pass managers

Four lines

Here is the whole Viscosity pipeline, from packages/core/src/index.ts:

const lowered = plugin.lower(source);
const analysis = analyze(lowered.module);
const p = plan(analysis, opts);
const code = plugin.emit(source,
  lowered, p);

Lower the source to VIR, analyse it, plan a layout for each collection, and emit rewritten source. That’s all. Viscosity has no pass manager yet: it runs this one fixed sequence, and it gets away with it because nothing in the sequence changes the IR. The analyses only read it, and emit edits the original source text rather than the IR.

That won’t last. The optimizations of the last few chapters, constant propagation, dead code elimination, inlining and loop-invariant code motion, all change the IR, and each one needs analyses such as dominators, loops and def-use lists. Once you have a dozen of them, you need something to organise them.

Passes hiding in one function

analyze is one function, but its comment lists the stages inside it: numeric inference, finding collections, safety, bounds, access patterns and size. They depend on each other in a tangled way. The escape walk meets ps[i] before numeric inference has run, so it can’t yet check that i is a number. It writes the check down and does it later:

// during the escape walk
indexChecks.push({ c, i });

// after numeric inference
for (const { c, i } of indexChecks)
  if (!isNumber(i.args[1]))
    c.bailouts.push('indexes the array' +
      ' with something that may not' +
      ' be a number');

And there is one small cache already. Bounds checks and loop access patterns both need each function’s dominators and natural loops, so info(f) computes them once:

const loopsOf = new Map();
const info = (f) => {
  let x = loopsOf.get(f);
  if (!x) {
    const idom = dominators(f);
    x = { idom,
      loops: naturalLoops(f, idom) };
    loopsOf.set(f, x);
  }
  return x;
};

The cache is never cleared, and that is correct here: nothing changes the IR while analyze runs. Put a transformation between two of those stages and this cache becomes a bug.

Caching, then invalidating

A pass manager makes both problems general. Passes don’t call analyses directly; they ask the manager. It returns a cached result if it has a valid one, and otherwise computes, stores and returns it. After a transformation, it throws away whatever the change made wrong. Step through four passes:

The hard part is knowing what is still valid, and only the pass knows what it changed. So in LLVM’s new pass manager, every pass returns a PreservedAnalyses value: all() if it changed nothing, none() if it won’t vouch for anything, or a specific list, such as “all CFG analyses”, for a pass that edited instructions but not blocks or edges^[1]. The manager then invalidates everything not preserved. Much of the manager’s complexity comes from trying to invalidate as little as possible, because recomputing costs compile time^[1].

LLVM also nests managers. A module pass manager can run a function pass manager over every function, through an adaptor, and there is a separate analysis manager per IR level: module, call-graph SCC, function and loop^[1].

Viscosity as passes

Here is how Viscosity’s pipeline could be organised, with analyses registered by name and asking for each other through the manager:

pm.analysis('uses', buildUses);
pm.analysis('domtree', dominators);
pm.analysis('loops', (f, am) =>
  naturalLoops(f, am.get('domtree')));
pm.analysis('collections', find);
pm.analysis('numeric', (m, am) =>
  infer(m, am.get('collections')));
pm.analysis('safety', (m, am) =>
  check(am.get('collections'),
        am.get('numeric')));
pm.pass(constprop); // preserves CFG
pm.pass(dce);       // preserves CFG
pm.pass(planLayouts);

Two things improve at once. The order of the analyses is no longer written by hand: safety asks for numeric, so numeric inference runs first, and the deferred indexChecks trick disappears. And transforms can be added before the layout planning, because each one declares what it keeps. That’s design, not code that exists yet: Part VII builds Viscosity as it is today.

Your turn

function makePM(analyses) {
  const get = (name, ir) =>
    analyses[name](ir, get);
  const run = (pass, ir) => {
    pass(ir, get);
  };
  return { get, run };
}

function makePM(analyses) {
  const cache = new Map();
  const get = (name, ir) => {
    if (!cache.has(name)) {
      const r = analyses[name](ir, get);
      cache.set(name, r);
    }
    return cache.get(name);
  };
  const run = (pass, ir) => {
    const keep = pass(ir, get);
    if (keep === 'all') return;
    for (const k of [...cache.keys()]) {
      if (!keep.includes(k)) {
        cache.delete(k);
      }
    }
  };
  return { get, run };
}

What you learned

• A compiler pass is one analysis or transformation. Optimizers are built from many small ones.
• A pass manager runs passes in order and caches the analyses they ask for, computing each at most once while it stays valid.
• Analysis invalidation throws away cached facts after a change. Each pass reports what it preserved: all, none, or a set such as the CFG analyses.
• Viscosity runs a fixed pipeline, lower → analyze → plan → emit, with no pass manager. That is safe only because nothing changes the IR.
• Asking for analyses through a manager makes dependencies explicit, so their order follows automatically.