74. Three-address code

Where did 2 * 3 go?

In chapter 47 the VM ran 1 + 2 * 3 like this:

CONSTANT 1
CONSTANT 2
CONSTANT 3
MULTIPLY
ADD

The 6 that MULTIPLY produced never had a name. It sat on the stack for one instruction and was gone. For running code that is perfect.

Now imagine an optimizer looking at it. It wants to say “the product is a constant, 6”, or “nobody uses this result, delete it”, or “this is the same product as three lines ago, reuse it”. Every one of those sentences needs to point at the product. On a stack, the only way to point is “whatever is on top right now”, and that changes with every instruction.

One operation per line

Three-address code is that page of working. The same expression:

t1 = 2 * 3
t2 = 1 + t1

Each line has at most one operator, at most two inputs, and one named result. t1 and t2 are names the compiler invented. You didn’t write them; they exist so that every intermediate value has an address.

Step through how lowering produces it for a function with three parameters. The walk is the same recursion as the tree-walker’s, but instead of computing values it emits instructions:

func h(%0, %1, %2):
  b0:
    %0 = param
    %1 = param
    %2 = param

Children are lowered before their parent, because an instruction can only be written once its inputs have names. Here is the real code, from packages/frontend-js/src/lower.ts, trimmed:

function expr(e: Node): ValueId {
  switch (e.type) {
    case 'Literal':
      return fb.constant(e.value);
    case 'Identifier':
      return read(binding(e), e);
    case 'BinaryExpression':
      return fb.emit('binop',
        [expr(e.left), expr(e.right)],
        { operator: e.operator });
    // ...
  }
}

expr returns a ValueId: the name of the result, not the result. fb.emit appends one instruction to the current block and hands back its fresh id.

Temporaries

t1, t2, and VIR’s %3, %4, %5 are temporaries. A compiler makes them freely, one for every result, because names cost it nothing at this stage. Deciding which temporaries share a machine register, or a stack slot, comes much later, if at all.

VIR goes one step further: every value is a temporary, even your own variables. Lower this:

function f(a) {
  let t = a;
  let u = t * 2;
  return u + t;
}

and you get:

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

t and u have disappeared. let t = a produced no instruction at all: the front end simply remembers that t now means %0. When the code reads t, it gets %0. (Chapter 77 shows why giving each value exactly one definition like this is so useful.) Notice also that the literal 2 is an instruction, %1 = const 2. Constants are values, so they get names too.

// Lower: let t = a; let u = t * 2;
//        return u + t;
const names = new Map();
const code = [];
let n = 0;
const emit = (text) => {
  const t = 't' + ++n;
  code.push(t + ' = ' + text);
  return t;
};
const get = (x) => names.get(x);

names.set('a', 'a');
// let t = a: no instruction
names.set('t', get('a'));
// let u = t * 2
names.set('u', emit(get('t') + ' * 2'));
// return u + t
const r =
  emit(get('u') + ' + ' + get('t'));
code.push('return ' + r);
console.log(code.join('\n'));

An instruction is a record

What does %2 = binop * %0, %1 look like in memory? It is one object, of the Inst interface in packages/core/src/vir.ts, trimmed:

interface Inst {
  id: ValueId;       // 2: its own name
  op: Op;            // 'binop'
  args: ValueId[];   // [0, 1]: inputs
  block: BlockId;    // 0: where it lives
  operator?: string; // '*'
  value?: number | string | boolean
    | null | undefined;  // for const
  field?: string;    // for field.get/set
}

The listing is just printFunc turning these records into text. And because inputs are names, the question an optimizer asks most, “who uses this value?”, is easy. Walk every instruction once and file it under each of its arguments. That is buildUses:

for (const b of f.blocks)
  for (const i of b.insts)
    for (const a of i.args)
      add(a, { inst: i });

For f above, %0 is used by %2 and %3, and %3 by the return. A value with no uses is dead, and can usually be deleted. Chapter 81 builds that pass on exactly this map.

Your turn

function toTac(e) {
  const out = [];
  return out;
}

function uses(code) {
  return {};
}

What you learned

• Three-address code: one operation per instruction, at most two inputs, one named result, x = y op z.
• Lowering an expression walks the tree children first, because an instruction needs names for its inputs.
• A temporary is a compiler-made name for an intermediate value. In VIR every value is a temporary, %n; even let t = a emits nothing.
• An instruction is a record: id, op, args, block. Named inputs make “who uses this?” a lookup (buildUses).

Next: straight runs of these instructions, and the jumps between them.