55. Jumps: if, while and for

No nesting to lean on

In chapter 38 the tree-walker ran an if with TypeScript’s own if. The syntax tree did the hard part: the branches were inside the if node.

Bytecode has no inside. A chunk is a flat row of bytes, and the dispatch loop of chapter 47 only ever does one thing: run the instruction at ip, then the next one. To skip a branch, or to go round a loop again, the VM must change ip itself.

Three jumps

Drip’s VM has three jump instructions. Each carries a 16-bit distance in two operand bytes, high byte first. From vm.ts:

case OP.JUMP:
  frame.ip += readShort();
  break;
case OP.JUMP_IF_FALSE: {
  const off = readShort();
  if (isFalsey(this.peek(0)))
    frame.ip += off;
  break;
}
case OP.LOOP:
  frame.ip -= readShort();
  break;

readShort reads the two bytes as (hi << 8) | lo and moves ip past them, so a distance is counted from the byte just after the instruction. LOOP jumps backwards: its distance is subtracted.

Notice that JUMP_IF_FALSE only peeks at the condition. It leaves the value on the stack, so the compiler must emit a POP on each path that continues. You’ll see why at the end of the chapter.

Jumping to code that doesn’t exist yet

Here is the problem with a single-pass compiler. When it reaches the ) of if (cond), it must emit the JUMP_IF_FALSE now, before the then-branch. But the jump’s distance is the size of the then-branch, which hasn’t been compiled. The answer: write a placeholder, remember where it is, and come back.

function emitJump(op: number) {
  emit(op, 0xff, 0xff);
  return chunk().code.length - 2;
}
function patchJump(offset: number) {
  const jump = chunk().code.length
    - offset - 2;
  if (jump > 0xffff) error(
    'Too much code to jump over.');
  chunk().code[offset] =
    (jump >> 8) & 0xff;
  chunk().code[offset + 1] =
    jump & 0xff;
}

patchJump is called when the compiler reaches the target: “the jump should land here”, where here is the next byte to be written. The - 2 accounts for the two operand bytes themselves. Here is ifStatement:

expression(); // the condition
const thenJump =
  emitJump(OP.JUMP_IF_FALSE);
emit(OP.POP);
statement();  // then-branch
const elseJump = emitJump(OP.JUMP);
patchJump(thenJump);
emit(OP.POP);
if (match('else')) statement();
patchJump(elseJump);

Step through it over the real bytes of a two-line program:

if (true) print 1;
print 2;

while: one jump back

A loop needs a jump backwards, and that one is easy. whileStatement records loopStart, the offset where the condition begins, compiles the condition and an exit JUMP_IF_FALSE, then the body, and ends with emitLoop(loopStart). The target has already been compiled, so the distance is known when LOOP is emitted. No patching. Only the exit jump is patched, after the LOOP.

The disassembler prints each jump as where it is -> where it lands, worked out from the stored distance. Here is the real output for while (i < 3) i = i + 1;, with i a global:

0004    2 OP_GET_GLOBAL       2 'i'
0006    | OP_CONSTANT         3 '3'
0008    | OP_LESS
0009    | OP_JUMP_IF_FALSE    9 -> 24
0012    | OP_POP
0013    | OP_GET_GLOBAL       5 'i'
0015    | OP_CONSTANT         6 '1'
0017    | OP_ADD
0018    | OP_SET_GLOBAL       4 'i'
0020    | OP_POP
0021    | OP_LOOP            21 -> 4
0024    | OP_POP

LOOP sends ip back to offset 4, the condition. When the condition finally fails, JUMP_IF_FALSE leaps past the LOOP to 24, where the last POP drops the false.

for: jumping around the increment

Chapter 38’s parser desugared for into a while. With no tree to rewrite, forStatement emits the jumps directly. The awkward part is the increment: it is written before the body but must run after it. So the compiler emits it where it appears, jumps over it on the way in, and points the body’s LOOP back at it. Here is for (let i = 0; i < 2; i = i + 1) print i;:

0000    1 OP_CONSTANT         0 '0'
0002    | OP_GET_LOCAL        1
0004    | OP_CONSTANT         1 '2'
0006    | OP_LESS
0007    | OP_JUMP_IF_FALSE    7 -> 31
0010    | OP_POP
0011    | OP_JUMP            11 -> 25
0014    | OP_GET_LOCAL        1
0016    | OP_CONSTANT         2 '1'
0018    | OP_ADD
0019    | OP_SET_LOCAL        1
0021    | OP_POP
0022    | OP_LOOP            22 -> 2
0025    2 OP_GET_LOCAL        1
0027    | OP_PRINT
0028    | OP_LOOP            28 -> 14
0031    | OP_POP
0032    | OP_POP

Follow it once: the condition (2–6), then JUMP over the increment to the body (25). The body’s LOOP goes back to the increment (14), whose own LOOP goes back to the condition (2). On exit, the first POP drops the condition, and the second is endScope freeing i: the whole loop is wrapped in a scope, so i is a local in slot 1.

and, or: jumps in disguise

and needs no new instruction. If the left side is falsey, that value is the answer, and the right side must be skipped:

const and_ = () => {
  const endJump =
    emitJump(OP.JUMP_IF_FALSE);
  emit(OP.POP);
  parsePrecedence(Prec.AND);
  patchJump(endJump);
};

This is why JUMP_IF_FALSE peeks: when it jumps, the left value is still on the stack as the result. or is the mirror image, built from a JUMP_IF_FALSE that hops over an unconditional JUMP.

let n = 0;
fn bump() {
  n = n + 1;
  return true;
}

print false and bump();
print true or bump();
print nil or "default";
print n;

Your turn

const BIG =
  'Too much code to jump over.';

// Push op and a 2-byte placeholder.
// Return where the placeholder starts.
function emitJump(code, op) {
  // your code here
}

// Fill the placeholder at code[at] so
// the jump lands at code.length.
function patchJump(code, at) {
  // your code here
}

// your code here

What you learned

• A jump changes ip. JUMP and LOOP always move (forward and back); JUMP_IF_FALSE moves only if the top of the stack is falsey, and doesn’t pop it.
• Distances are 16-bit and counted from just after the instruction.
• Backpatching: emitJump writes 0xff 0xff and returns its position; patchJump fills in the distance once the target is the current end of the code.
• if uses two forward jumps, while a forward exit plus a LOOP, and for jumps over its increment on the way in.
• and and or are jumps that skip the right operand, leaving the left value as the result.

Next: functions, calls and call frames.