Computed gotos, TCO, threaded interpreters: experiments and findings

9

Sorry, I didn’t explain that very well. Suppose we rewrite Eli’s computed goto example to look like this:

int
interp_cgoto2(unsigned char* code, int initval)
{
  static void* dispatch_table[] = { &&do_halt, &&do_inc,  &&do_dec, &&do_mul2,
                                    &&do_div2, &&do_add7, &&do_neg };
  int pc = 0;
  int val = initval;

  while (1) {
    goto* dispatch_table[code[pc++]];
  do_halt:
    return val;
  do_inc:
    val++;
    continue;
  do_dec:
    val--;
    continue;
  do_mul2:
    val *= 2;
    continue;
  do_div2:
    val /= 2;
    continue;
  do_add7:
    val += 7;
    continue;
  do_neg:
    val = -val;
    continue;
  }
}

And compare that to his normal switch code which goes like this:

    while (1) {
        switch (code[pc++]) {
            case OP_HALT:
                return val;
            case OP_INC:
                val++;
                break;
                ...

We should expect that to generate about the same machine code since a switch is translated to a jump table and an indirect branch if it is big and dense enough:

$ clang -O -o- -S interp_switch.c | grep jmpq
	jmpq	*%rcx

However, LLVM compiles the interp_cgoto2 function to almost the same code as the original interp_cgoto which has a computed goto at the end of each opcode:

$ clang -O -o- -S interp_cgoto2.c | grep jmpq
	jmpq	*(%rax,%rcx,8)
	jmpq	*(%rax,%rcx,8)
	jmpq	*(%rax,%rcx,8)
	jmpq	*(%rax,%rcx,8)
	jmpq	*(%rax,%rdx,8)
	jmpq	*(%rax,%rcx,8)
	jmpq	*(%rax,%rcx,8)

LLVM is effectively replacing the continue statements with copies of the indirect branch at the top of the loop. It could also do that with the indirect branch that is inherent in a switch; it chooses to not do that for code size reasons.

So, LLVM can transform back and forth between having a single indirect branch at the top of the loop, or having individual indirect branches at the end of each opcode handler. It can do this whether you write your source code using a normal switch statement or a computed goto.

6 Likes