81. Dead code elimination

Work nobody asked for

Here is a function with a leftover line. Maybe p was used once, and then the code around it changed:

function area(w, h) {
  const p = w + h;
  const a = w * h;
  return a;
}
console.log(area(3, 4));

Nothing reads p. You met this situation from the other side in chapter 24, where an optimizing JIT could quietly delete a benchmark loop whose answer was never used. This chapter is about how a compiler finds such code, and when it is allowed to delete it.

Here is area in Viscosity’s real IR, printed by the engine’s printFunc:

func area(%0, %1):
  b0:
    %0 = param
    %1 = param
    %2 = binop + %0, %1
    %3 = binop * %0, %1
    return %3

%2 is p. Nobody uses it. Viscosity builds a use list for every value: the instructions (and branches and returns) that read it. When you ask the engine for values whose use list is empty, it names three:

no uses: %2   binop +
no uses: %5   storeBinding
no uses: %12  call

Only the first is junk. %5 stores the function area under its name, and %12 is the call to console.log. Nobody reads their results, but they do something: one updates a variable, the other prints. So “unused” isn’t the same as “dead”.

Garbage collection for instructions

That is the mark-and-sweep collector from chapter 58, applied to code. The roots are instructions whose effect the outside world can see: printing, storing somewhere another part of the program can read, calling code you can’t see into, returning, and branching. Mark the roots live. Whenever an instruction is live, its operands are live too. When marking stops, sweep away everything unmarked.

Notice the step where %3 uses %2, yet both are deleted. A value with a use can still be dead, if its users are dead. A simpler pass deletes instructions that have no uses at all, then looks again at their operands, which may have just lost their last use. LLVM ships both kinds: its dce pass rechecks the operands of removed instructions, and its adce (“aggressive” DCE) assumes values are dead until proven otherwise^[1], like the diagram does.

Is it really free of effects?

The whole method hinges on one judgement: does this instruction have an effect? For binop + in JavaScript, the honest answer is “it depends”. If w is an object, w + h converts it to a primitive by calling its valueOf method, and that method can do anything:

function area(w, h) {
  const p = w + h; // never used
  return w * h;
}

const o = {
  valueOf() {
    console.log('valueOf ran');
    return 3;
  },
};

console.log(area(o, 4));
// Delete the line with p: one
// "valueOf ran" disappears.

The “unused” w + h printed a line. Deleting it would change the output, so a JavaScript compiler may delete it only if it knows w and h are primitives. Property reads have the same problem (a getter is a hidden function call), and so do calls to functions the compiler can’t see.

This is where earlier analyses pay off. Viscosity’s numeric inference (a dataflow fixpoint, the kind you met in chapter 79) checks every place area is called. Both arguments are numbers at the only call site, so it proves %0 and %1 are numbers, and therefore %2 runs no user code. Add a second call, area("3", 4), and the fact for %0 turns false. (A string + happens to be harmless too, but Viscosity’s fact is only “is a number”, so a DCE built on it would keep the +. That is timid, and safe.)

Liveness: before SSA

SSA made the question easy: each value has exactly one definition, so “is this definition needed?” is “does a live instruction use this value?”. Ordinary variables are messier, because one name can be assigned many times:

x = 1
x = 2
y = x + 1
print y

The first assignment is dead. Its value is overwritten before anyone reads it. To see that mechanically, walk backwards and track which variables will still be read:

              live after
x = 1         { }       x = 1 is dead
x = 2         { x }
y = x + 1     { y }
print y       { }

Start at the bottom with nothing live. print y reads y, so y is live above it. y = x + 1 defines y (remove it) and reads x (add it). x = 2 defines x, so above it nothing is live. And x = 1 defines a variable that is not live afterwards: a dead store.

In straight-line code one backward walk is enough. With branches and loops you use the dataflow machinery from chapter 79, run in reverse.

Your turn

const EFFECTS = ['print', 'store',
  'return'];

function dce(code) {
  // your code here
  return code;
}

// I('p', '+', 'w', 'h') makes
// { id: 'p', op: '+',
//   args: ['w', 'h'] }
const I = (id, op, ...args) =>
  ({ id, op, args });
const code = [
  I('w', 'const'),
  I('h', 'const'),
  I('p', '+', 'w', 'h'),
  I('a', '*', 'w', 'h'),
  I('r', 'return', 'a'),
];
console.log(dce(code).map((i) => i.id));

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

const st = (def, uses = []) =>
  ({ def, uses, effect: false });
const code = [
  st('x'), // x = 1
  st('x'), // x = 2
  st('y', ['x']), // y = x + 1
  { def: null, uses: ['y'],
    effect: true }, // print y
];
console.log(deadStores(code)); // [0]

What you learned

• Dead code elimination (DCE) deletes instructions whose results can never affect what the program does.
• Mark-and-sweep DCE starts from the roots (instructions with observable effects), marks operands of live instructions, and deletes everything unmarked. A value whose only users are dead is dead too.
• “Unused” is not “dead”: a call or a store matters even if nobody reads its result.
• In JavaScript, +, property reads and calls can run user code, so deleting them needs type facts, such as Viscosity’s proof that a value is a number.
• Liveness says whether a variable may still be read. It flows backwards and merges by union; an assignment to a variable that isn’t live afterwards is a dead store. SSA makes the question nearly free.