Seidl&Wilhelm Imperative VM (chapter 2, C-Machine)

c-machine.c

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

#define OP_Add 1
#define OP_And 2
#define OP_Alloc 3
#define OP_Call 4
#define OP_Div 5
#define OP_Dup 6
#define OP_Enter 8
#define OP_Eq 9
#define OP_Ge 11
#define OP_Gt 12
#define OP_Halt 13
#define OP_Jump 14
#define OP_JumpZ 15
#define OP_JumpI 16
#define OP_Le 17
#define OP_Lt 18
#define OP_Load 19
#define OP_LoadA 20
#define OP_LoadC 21
#define OP_LoadR 22
#define OP_LoadRC 23
#define OP_Malloc 24
#define OP_Mark 25
#define OP_Mul 26
#define OP_Neg 27
#define OP_Ne 28
#define OP_New 29
#define OP_Or 30
#define OP_Pop 31
#define OP_Return 32
#define OP_Slide 33
#define OP_Store 34
#define OP_StoreA 35
#define OP_StoreR 36
#define OP_Sub 37

#define NUM_MEMORY_SLOTS 66536
#define NUM_PROG_SLOTS 8196
#define NUM_ENV_SLOTS 2048

#define Instr                                                                 \
  struct                                                                      \
  {                                                                           \
    uint64_t opcode : 8;                                                      \
    uint64_t fld1 : 32;                                                       \
    uint64_t fld2 : 24;                                                       \
  }

typedef Instr Instr_t;

static long long *MEMORY = NULL;
static long long *STACK = NULL;
static long long *HEAP = NULL;
static Instr_t *PROG = NULL;
static unsigned *ENV = NULL;

static unsigned PC = 0;
static unsigned SP = 0;
static unsigned FP = 0;
static unsigned EP = 0;
static unsigned HP = 0;

static unsigned code_size = 0;
static unsigned next_global = 0;
static unsigned next_local = 0;
static signed param_offset = 0;

void
fatalf (const char *fmt, ...)
{
  va_list args;

  const char *ANSI_RED = "\033[31m";
  const char *ANSI_RESET = "\033[0m";

  fprintf (stderr, "%sFatal error:%s", ANSI_RED, ANSI_RESET);

  va_start (args, fmt);
  vfprintf (stderr, fmt, args);
  va_end (args);

  fputc ('\n', stderr);
  fflush (stderr);

  exit (EXIT_FAILURE);
}

static void
insert_code (uint8_t opcode, int fld1, int fld2)
{
  PROG[code_size].opcode = opcode;
  PROG[code_size].fld1 = fld1;
  PROG[code_size].fld2 = fld2;
  code_size++;
}

static inline unsigned short
slot_sym (const char *sym)
{
  unsigned short s = 5381;
  char c = 0;
  while ((c = *sym++))
    s = (s << 5) + s + c;
  return s % NUM_ENV_SLOTS;
}

static inline unsigned int
addr_sym (const char *sym)
{
  unsigned short slot = slot_sym (sym);
  return ENV[slot];
}

static void
decl_global (int tsz, const char *name)
{
  unsigned short slot = slot_sym (name);
  unsigned addr = next_global;
  ENV[slot] = addr;
  next_global += tsz;
}

static void
decl_local (int tsz, const char *name)
{
  unsigned short slot = slot_sym (name);
  next_local += tsz;
  unsigned addr = next_local + FP;
  ENV[slot] = addr;
}

static void
decl_formal (int tsz, const char *name)
{
  unsigned short slot = slot_sym (name);
  param_offset -= tsz;
  unsigned addr = FP + next_local + param_offset;
  ENV[slot] = addr;
}

static void
decl_return (int tsz, const char *name)
{
  unsigned short slot = slot_sym ("%ret");
  param_offset -= tsz - 3;
  unsigned addr = FP + param_offset;
  ENV[slot] = addr;
}

static void
clear_frame (void)
{
  next_local = 0;
  param_offset = 0;
}

void
cleanup (void)

{
  free (MEMORY);
  free (PROG);
  free (ENV);
  run_vm_epilogue ();
}

int
main (int argc, char **argv)
{
  atexit (cleanup);

  MEMORY = calloc (NUM_MEMORY_SLOTS, sizeof (long long));
  PROG = calloc (NUM_PROG_SLOTS, sizeof (Instr_t));
  ENV = calloc (NUM_ENV_SLOTS, sizeof (unsigned));
  STACK = &MEMORY[0];
  HEAP = &MEMORY[NUM_MEMORY_SLOTS - 1];

  run_frontend (argc, argv);
  run_vm_prologue ();

  PC = 0;
  SP = 0;
  FP = 0;
  EP = 0;
  HP = NUM_MEMORY_SLOTS - 1;

  while (PC < code_size)
    {
      int opcode = PROG[PC].opcode;
      int fld1 = PROG[PC].fld1;
      int fld2 = PROG[PC].fld2;
      PC++;

      switch (opcode)
        {
        case OP_LoadC:
          SP++;
          STACK[SP] = fld1;
          continue;
        case OP_Load:
          for (ssize_t i = fld1 - 1; i >= 0; i--)
            STACK[SP + i] = STACK[STACK[SP] + i];
          SP = SP + fld1 - 1;
          continue;
        case OP_LoadA:
          SP++;
          STACK[SP] = fld1;
          for (ssize_t i = fld2 - 1; i >= 0; i--)
            STACK[SP + i] = STACK[STACK[SP] + i];
          SP = SP + fld2 - 1;
          continue;
        case OP_LoadRC:
          SP++;
          STACK[SP] = FP + fld1;
          continue;
        case OP_LoadR:
          SP++;
          STACK[SP] = FP + fld1;
          for (ssize_t i = fld2; i >= 0; i--)
            STACK[SP + i] = STACK[STACK[SP] + i];
          SP = SP + fld2 - 1;
          continue;
        case OP_Store:
          for (ssize_t i = 0; i < fld2; i++)
            STACK[STACK[SP] + i] = STACK[SP - fld2 + i];
          SP = SP + fld2 - 1;
          continue;
        case OP_StoreA:
          SP++;
          STACK[SP] = fld1;
          for (ssize_t i = 0; i < fld2; i++)
            STACK[STACK[SP] + i] = STACK[SP - fld2 + i];
          SP = SP + fld2 - 1;
          continue;
        case OP_StoreR:
          SP++;
          STACK[SP] = FP + fld1;
          for (ssize_t i = 0; i < fld2; i++)
            STACK[STACK[SP] + i] = STACK[SP - fld2 + i];
          SP = SP + fld2 - 1;
          continue;
        case OP_Pop:
          SP--;
          continue;
        case OP_Dup:
          STACK[SP + 1] = STACK[SP];
          SP++;
          continue;
        case OP_Halt:
          return EXIT_SUCCESS;
        case OP_Add:
          STACK[SP - 1] = STACK[SP - 1] + STACK[SP];
          SP--;
          continue;
        case OP_Mul:
          STACK[SP - 1] = STACK[SP - 1] * STACK[SP];
          SP--;
          continue;
        case OP_Sub:
          STACK[SP - 1] = STACK[SP - 1] - STACK[SP];
          SP--;
          continue;
        case OP_Div:
          if (STACK[SP] == 0)
            fatalf ("Division by zero attempted");
          STACK[SP - 1] = STACK[SP - 1] / STACK[SP];
          SP--;
          continue;
        case OP_Eq:
          STACK[SP - 1] = STACK[SP - 1] == STACK[SP];
          SP--;
          continue;
        case OP_Ne:
          STACK[SP - 1] = STACK[SP - 1] != STACK[SP];
          SP--;
          continue;
        case OP_Lt:
          STACK[SP - 1] = STACK[SP - 1] < STACK[SP];
          SP--;
          continue;
        case OP_Le:
          STACK[SP - 1] = STACK[SP - 1] <= STACK[SP];
          SP--;
          continue;
        case OP_Gt:
          STACK[SP - 1] = STACK[SP - 1] > STACK[SP];
          SP--;
          continue;
        case OP_Ge:
          STACK[SP - 1] = STACK[SP - 1] >= STACK[SP];
          SP--;
          continue;
        case OP_Neg:
          STACK[SP] = -STACK[SP];
          continue;
        case OP_And:
          STACK[SP - 1] = STACK[SP - 1] && STACK[SP];
          SP--;
          continue;
        case OP_Or:
          STACK[SP - 1] = STACK[SP - 1] || STACK[SP];
          SP--;
          continue;
        case OP_New:
          if (HP - STACK[SP] > EP)
            {
              HP = HP - STACK[SP];
              STACK[SP] = HP;
            }
          else
            STACK[SP] = 0;
          continue;
        case OP_Alloc:
          SP = SP + fld1;
          continue;
        case OP_Enter:
          EP = SP + fld1;
          if (EP >= HP)
            fatalf ("Stack overflow: %u >= %u", EP, HP);
          continue;
        case OP_Return:
          PC = STACK[FP];
          EP = STACK[FP - 2];
          if (EP >= HP)
            fatalf ("Stack overflow, %u >= %u", EP, HP);
          SP = FP - fld1;
          FP = STACK[FP - 1];
          continue;
        case OP_Mark:
          STACK[SP + 1] = EP;
          STACK[SP + 2] = FP;
          SP += 2;
          continue;
        case OP_Jump:
          PC = fld1;
          continue;
        case OP_JumpZ:
          if (STACK[SP] == 0)
            PC = fld1;
          SP--;
          continue;
        case OP_JumpI:
          PC = fld1 + STACK[SP];
          SP--;
          continue;
        case OP_Slide:
          if (fld1 > 0)
            {
              if (fld2 == 0)
                SP = SP - fld1;
              else
                {
                  SP = SP - fld1 - fld2;
                  for (ssize_t i = 0; i < fld2; i++)
                    {
                      SP++;
                      STACK[SP] = STACK[SP + fld1];
                    }
                }
            }
          continue;
        default:
          continue;
        }
    }
}