Branch predication

README

See main.c. Requires gcc or llvm-clang to compile.

    $ time ./a.out --fast 40
    fibo(40) = 102334155
    real    0m0.571s
    user    0m0.567s
    sys     0m0.002s
    
    $ time ./a.out --slow 40
    fibo(40) = 102334155
    real    0m1.028s
    user    0m1.024s
    sys     0m0.003s
    
    $ time ./a.out --native 40
    fibo(40) = 102334155
    real    0m0.499s
    user    0m0.496s
    sys     0m0.002s

main.c

#include <stdint.h>
#include <stdio.h>
#include <stdlib.h>
#include <string.h>

intptr_t runDirectThreading(intptr_t n, intptr_t *SP) {
  void *LR;
  intptr_t R0;

main:
  R0 = n;
  LR = &&main_call_ret;
  goto fibo;

fibo:
  if (R0 < 2) {
    goto *LR;
  }
  SP -= 2;
  SP[0] = R0;
  SP[1] = (intptr_t) LR;
  R0 -= 1;
  LR = &&fibo_call1_ret;
  goto fibo;

fibo_call1_ret:
  LR = (void **) R0;
  R0 = SP[0] - 2;
  SP[0] = (intptr_t) LR;
  LR = &&fibo_call2_ret;
  goto fibo;

fibo_call2_ret:
  R0 = SP[0] + R0;
  SP += 2;
  goto *(void **) SP[-1];
  // ^ Branch mispredication here.

main_call_ret:
  return R0;
}

intptr_t runWithPredictor(intptr_t n, intptr_t *SP) {
  void *LR;
  intptr_t R0;

main:
  R0 = n;
  LR = &&main_call_ret;
  goto fibo;

fibo:
  if (R0 < 2) {
    goto *LR;
  }
  SP -= 2;
  SP[0] = R0;
  SP[1] = (intptr_t) LR;
  R0 -= 1;
  LR = &&fibo_call1_ret;
  goto fibo;

fibo_call1_ret:
  LR = (void **) R0;
  R0 = SP[0] - 2;
  SP[0] = (intptr_t) LR;
  LR = &&fibo_call2_ret;
  goto fibo;

fibo_call2_ret:
  R0 = SP[0] + R0;
  SP += 2;
  {
    // | Manually predictes the branch destination.
    void **retAddr = (void **) SP[-1];
    if (retAddr == &&fibo_call1_ret) {
      goto fibo_call1_ret;
    }
    else if (retAddr == &&fibo_call2_ret) {
      goto fibo_call2_ret;
    }
    else {
      goto *retAddr;
    }
  }

main_call_ret:
  return R0;
}

intptr_t runNative(intptr_t n) {
  if (n < 2) {
    return n;
  }
  return runNative(n - 1) + runNative(n - 2);
  // ^ Return stack buffer suits best in this scenario.
}

int main(int argc, char **argv) {
  intptr_t (*f)(intptr_t, intptr_t *);
  intptr_t stack[1024];
  intptr_t n, res;

  if (argc == 3) {
    n = atoi(argv[2]);
    if (strcmp(argv[1], "--native") == 0) {
      res = runNative(n);
    }
    else {
      f = strcmp(argv[1], "--fast") == 0 ? runWithPredictor : runDirectThreading;
      res = f(n, stack + 1024);
    }
    printf("fibo(%ld) = %ld\n", n, res);
  }
  else {
    printf("usage: %s [--fast|--slow|--native] <number>\n", argv[0]);
  }
  return 0;
}