codegen.c

idel虚拟机源码

/*
 * Internal code generator.
 * Copyright (C) 2001-2002 Darius Bacon
 *
 * Read an object file and generate the internal form of threaded code
 * implementing it.
 */

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

#include "idel_private.h"


/* Equivalent to die() but more pertinent to object-file parsing.  */
static void
bad_input (const char *message, ...)
{
  va_list args;

  fprintf (stderr, "%s: Bad object file: ", program_name);
  va_start(args, message);
  vfprintf(stderr, message, args);
  va_end(args);
  fprintf(stderr, "\n");

  exit (128);
}


/* Like bad_input() but giving the current defn #. */
static void
bad_defn (const VM *vm, const char *message, ...)
{
  va_list args;

  fprintf (stderr, "%s: Bad object file in defn #%d: ", 
	   program_name, vm->defn_number);
  va_start(args, message);
  vfprintf(stderr, message, args);
  va_end(args);
  fprintf(stderr, "\n");

  exit (128);
}


/* Return a new vm with codegen-private fields initialized. */
VM *
vm_make (int stack_size, int data_size, int profiling)
{
  VM *vm = vm_sort_of_make (stack_size, data_size);

  assert (false == profiling || true == profiling);
  vm->profiling = profiling;
  vm->tallies_size = 0;
  vm->num_tallies = 0;
  vm->tallies = NULL;

  vm->ns_size = stack_size;
  vm->nesting = allot (stack_size * sizeof vm->nesting[0]);
  vm->nsp = vm->nesting;

  vm->height = vm->locals = vm->max_width = 0;
  vm->returning = 0;
  vm->at_jump_target = false;
  vm->bb_end = NULL;

  vm->defn_number = 0;
  vm->block_start = vm->block_end = 0;
  vm->entries_size = 256;
  vm->entries = allot (vm->entries_size * sizeof vm->entries[0]);

  vm->there = vm->chunks[0] + chunk_size;
  vm->data_ptr = 0;

  if (paranoid) vm_check (vm);
  return vm;
}


/* Add a new tally entry with a 0 count for the [start..end] code block.
   Return the index of the tally counter. */
static int
add_tally (VM *vm, int defn, i32 *start, i32 *end)
{
  int i = vm->num_tallies++;

  if (i == vm->tallies_size)
    {
      if (0 == i)
	{
	  vm->tallies_size = 1;
	  vm->tallies = allot (sizeof vm->tallies[0]);
	}
      else
	{
	  vm->tallies_size *= 2;
	  vm->tallies = 
	    reallot (vm->tallies, vm->tallies_size * sizeof vm->tallies[0]);
	}
    }

  vm->tallies[i].count = 0;
  vm->tallies[i].defn = defn;
  vm->tallies[i].start = start;
  vm->tallies[i].end = end;

  return i;
}


/* Write vm's profile data to `out'. */
void
vm_dump_profile (VM *vm, FILE *out)
{
  int i;
  for (i = 0; i < vm->num_tallies; ++i)
    {
      const Tally *t = &vm->tallies[i];
      const i32 *p = t->start;
      fprintf (out, "%10lu %3d", t->count, t->defn);
      while (p != t->end)
	{
	  int opcode = lookup_op (*p);
	  int operands = operand_count (opcode);
	  assert (0 <= opcode && 0 <= operands);
	  fprintf (out, " %s", format_opcode (opcode));
	  p += 1 + operands;
	}
      fprintf (out, "\n");
    }
}


/* Code emission */

/* Ensure that vm's data space can hold at least one word at its data_ptr. */
static void
ensure_data_space (VM *vm)
{
  if (vm->data_size <= vm->data_ptr)
    bad_input ("Out of data space");
}


/* Append b to vm's data space. */
static void
emit_data_byte (VM *vm, i8 b)
{
  ensure_data_space (vm);
  vm->data[endianness ^ vm->data_ptr] = b;
  vm->data_ptr += 1;
}


/* Append i to vm's data space. */
static void
emit_data_int (VM *vm, i32 i)
{
  vm->data_ptr = word_align (vm->data_ptr);
  ensure_data_space (vm);
  *(i32 *)(vm->data + vm->data_ptr) = i;
  vm->data_ptr += word_size;
}


/* Move vm's new-code pointer into a freshly allocated chunk, leaving
   a JUMP to the former new-code location. */
static void
move_to_new_chunk (VM *vm)
{
  if (paranoid) vm_check (vm);

  /* Fill current chunk's unused space, just to make debugging easier */
  {
    i32 *p = vm->there - 1;
    for (; vm->chunks[vm->num_chunks - 1] <= p; --p)
      *p = -1;			/* garbage value */
  }

  /* Add another chunk to the chunks array */
  if (vm->num_chunks == vm->chunks_size)
    {
      vm->chunks_size *= 2;
      vm->chunks = reallot (vm->chunks, vm->chunks_size * sizeof vm->chunks[0]);
    }
  vm->chunks[vm->num_chunks] = 
    allot (chunk_size * sizeof vm->chunks[0][0]);

  /* Set the code allocation pointer and emit a jump to where we left off */
  {				
    i32 *continue_point = vm->there;
    vm->there = vm->chunks[vm->num_chunks] + chunk_size - 2;
    vm->there[0] = (i32) opcode_labels[JUMP];
    vm->there[1] = (i32) (continue_point);
  }

  vm->num_chunks++;
  if (paranoid) vm_check (vm);
}


/* Ensure that vm's current chunk has space for an n-operand instruction.
   Pre: 0 <= n < chunk_size */
static void
reserve (VM *vm, int n)
{
  if (vm->there <= vm->chunks[vm->num_chunks - 1] + n)
    move_to_new_chunk (vm);
}


/* Prepend w to vm's code space. */
static void 
emit_lit (VM *vm, i32 w)
{
  reserve (vm, 0);
  *--vm->there = w;
}


/* Pre: vm's current chunk has space for a 0-operand instruction.
   Prepend a no-operand instruction to vm's code space. */
static void 
really_emit (VM *vm, int opcode)
{
  int combined_opcode = -1;
  if (!vm->at_jump_target)
    switch (opcode)
      {
#include "peep.inc"
      }

  if (0 <= combined_opcode)
    vm->there[0] = (i32) opcode_labels[combined_opcode];
  else
    {
      *--vm->there = (i32) opcode_labels[opcode];
      vm->at_jump_target = false;
    }
}


/* Pre: vm's current chunk has space for a 1-operand instruction.
   Prepend a 1-operand instruction to vm's code space. */
static void
really_emit1 (VM *vm, int opcode, i32 operand)
{
  int combined_opcode = -1;
  if (!vm->at_jump_target)
    switch (opcode)
      {
#include "peep1.inc"
      }

  if (0 <= combined_opcode)
    {
      vm->there[-1] = (i32) opcode_labels[combined_opcode];
      vm->there[0] = operand;
      vm->there -= 1;
    }
  else
    {
      vm->there[-2] = (i32) opcode_labels[opcode];
      vm->there[-1] = operand;
      vm->there -= 2;
      vm->at_jump_target = false;
    }

}


/* Prepend a no-operand instruction to vm's code space. */
static void 
emit (VM *vm, int opcode)
{
  reserve (vm, 0);
  really_emit (vm, opcode);
}


/* Prepend a 1-operand instruction to vm's code space. */
static void
emit1 (VM *vm, int opcode, i32 operand)
{
  reserve (vm, 1);
  really_emit1 (vm, opcode, operand);
}


/* Code generation */

typedef struct Insn {
  u8 opcode;
  i32 operand;
} Insn;


/* Set up to generate a block of n defns. */
static void
start_defns (VM *vm, u32 n)
{
  int i;
  if (paranoid) vm_check (vm);

  vm->block_start = vm->defn_number;
  vm->block_end = vm->defn_number + n;
  if (vm->entries_size < vm->block_end)
    {
      do {
	vm->entries_size *= 2;
      } while (vm->entries_size < vm->block_end);
      vm->entries = reallot (vm->entries, 
			     vm->entries_size * sizeof vm->entries[0]);
    }
  for (i = vm->block_start; i < vm->block_end; ++i)
    {
      vm->entries[i].address = NULL;
      vm->entries[i].refs = NULL;
    }

  if (paranoid) vm_check (vm);
}


/* Finish generating the current defns block. */
static void
finish_defns (VM *vm)
{
  if (paranoid)
    {
      /* Check that all references were resolved. */
      int i;
      for (i = vm->block_start; i < vm->block_end; ++i)
	assert (vm->entries[i].address != NULL);

      vm_check (vm);
    }
}


/* Return the entry for defn #`defn'. */
static Entry *
defn_entry (const VM *vm, int defn)
{
  if ((unsigned) vm->block_end <= (unsigned) defn)
    bad_defn (vm, "Reference out of range");
  return vm->entries + defn;
}


/* Pre: where != NULL
   Record that the code for `defn' starts at `where'. */
static void
resolve (VM *vm, int defn, i32 *where)
{
  Entry *entry = defn_entry (vm, defn);
  assert (where != NULL);
  assert (entry->address == NULL);
  {
    Unresolved *u = entry->refs;
    while (u != NULL)
      {
	Unresolved *v = u->next;
	u->ref[0] = (i32) where;
	free (u);
	u = v;
      }
    entry->refs = NULL;
  }
  entry->address = where;
}


/* Pre: ref != NULL
   Record that the code word at `ref' should hold the starting address of 
   the defn that `entry' denotes.
   Return that address if known, else NULL. */
static const i32 *
reference (Entry *entry, i32 *ref)
{
  if (entry->address == NULL)
    {
      Unresolved *u = allot (sizeof *u);
      u->ref = ref;
      u->next = entry->refs;
      entry->refs = u;
    }
  return entry->address;
}


/* Pre: opcode is CALL or TAILCALL.
   Emit a call to the defn that `entry' denotes. */
static i32 *
emit_call (VM *vm, int opcode, Entry *entry)
{
  reserve (vm, 1);
  {
    i32 *after = vm->there;
    really_emit1 (vm, opcode, (i32) reference (entry, after - 1));
    return after;
  }
}


/* Emit a branch to `target'. */
static void
emit_branch (VM *vm, i32 *target)
{
  reserve (vm, 1);
  {
    int d = target - vm->there;
    if (2 <= d && d <= 9)
      really_emit (vm, BRANCH2 + d-2);
    else
      really_emit1 (vm, BRANCH, (i32) target);
  }
}


/* Emit a 1-operand instruction, possibly using a version of the
   instruction customized to the particular operand value (if the
   operand's in the range [lo..hi]). */
static void
emit_immediate (VM *vm, int opcode, i32 operand,
		int custom_base_opcode, i32 lo, i32 hi)
{
  if (lo <= operand && operand <= hi)
    emit (vm, custom_base_opcode + operand - lo);
  else
    emit1 (vm, opcode, operand);
}


static void
emit_drop (VM *vm, int count)
{
  emit_immediate (vm, DROP, count, DROP1, 1, 4);
}


/* Restore the validity of max_width after a change to height or locals
   that might have increased it. */
static void
update_width (VM *vm)
{
  if (vm->height + vm->locals > vm->max_width)
    vm->max_width = vm->height + vm->locals;
}


/* Update the static stack height for an instruction with `using' inputs
   off the stack and `delta' overall change in stack height.  (The old
   stack state holds for *after* the instruction executes, and the new
   state for *before* it.) */
static void
update_stack (VM *vm, int using, int delta)
{
  vm->height -= delta;
  if (vm->height < using)
    bad_defn (vm, "Inaccurate stack effect declaration (more results "
	       "are yielded than declared)");
}


/* Update the static locals depth for an instruction that changes it by
   `delta'.  (Used the same way as update_stack.  We don't need a `using'
   parameter because underflow can't happen.) */
static void
update_locals (VM *vm, int delta)
{
  vm->locals -= delta;
}


/* Record that `code' is an address that may go on the return stack,
   with `popping' as the number of stack elements the callee pops off.
   Pre: This must be done right after the responsible instruction is
   compiled, so the static stack state will be right.  (Ugh...) */
static void
note_frame_map (VM *vm, i32 *code, unsigned popping)
{
  if (vm->num_fms == vm->fm_size)
    {
      vm->fm_size *= 2;
      vm->fm = reallot (vm->fm, vm->fm_size * sizeof vm->fm[0]);
    }
  {
    Frame_map *m = vm->fm + vm->num_fms++;
    m->code = code;
    m->height = vm->height - popping;
    m->locals = vm->locals;
  }