codegen.c

idel虚拟机源码

}


/* Mark the beginning of the current basic block (at vm->there) and
   the end of a new one. */
static void
basic_block_boundary (VM *vm)
{
  if (vm->profiling)
    if (vm->bb_end != vm->there)
      {
	int counter = add_tally (vm, vm->defn_number, vm->there, vm->bb_end);
	emit1 (vm, TALLY, counter);
	vm->bb_end = vm->there;
      }
}


const struct {
  int arg_count, delta;
} op_effect[] = {
#include "effect.inc"
};


/* Prepend `insn' to the current defn. */
static void
translate_insn (VM *vm, Insn insn)
{
  switch (insn.opcode)
    {
    case BEGIN:
      if (vm->nsp == vm->nesting)
	bad_defn (vm, "Badly nested control flow at BEGIN");
      {
	const Nest *nest = --(vm->nsp);
	int pending = nest->opcode;
	switch (pending)
	  {
	  case ELSE:
	  case THEN:
	    basic_block_boundary (vm);
	    if (nest->height != vm->height)
	      bad_defn (vm, "Stack effects don't match across branches");
	    emit_branch (vm, nest->addr);
	    update_stack (vm, 1, -1);
	    update_width (vm);
	    break;
	  case DROP: 
	    {
	      i32 locals = nest->operand;
	      emit_immediate (vm, GRAB, locals, GRAB1, 1, 4);
	      update_stack (vm, locals, -locals);
	      update_locals (vm, locals);
	      break;
	    }
	  default:
	    unreachable ();
	  }
	vm->returning = -1;
      }
      break;

    case ELSE: 
      basic_block_boundary (vm);
      {
	int n;
	i32 *after = vm->there;
	Nest *nest = vm->nsp - 1;
	if (nest < vm->nesting || nest->opcode != THEN)
	  bad_defn (vm, "Badly nested control flow at ELSE");
	vm->at_jump_target = true;
	n = nest->returning;
	if (n == -1)
	  emit1 (vm, JUMP, (i32) nest->addr);
	else
	  {			/* optimize out jumps to RETURN */
	    emit (vm, RETURN);
	    if (0 < n) emit_drop (vm, n);
	  }
	{
	  int old_height = nest->height;

	  nest->opcode    = ELSE;
	  nest->addr      = after;
	  nest->height    = vm->height;
	  nest->returning = vm->returning;

	  vm->height    = old_height;
	  vm->returning = n;
	}
	break;
      }

    case THEN:
      basic_block_boundary (vm);
      {
	Nest *nest = vm->nsp++;
	/* FIXME: this isn't really bad input, it's a hard limit: */
	if (vm->nesting + vm->ns_size <= nest)
	  bad_defn (vm, "Too many levels of control-flow nesting at THEN");
	nest->opcode    = THEN;
	nest->addr      = vm->there;
	nest->height    = vm->height;
	nest->returning = vm->returning;
	vm->at_jump_target = true;
	break;
      }

    case CALL: 
      basic_block_boundary (vm);
      {
	Entry *entry = defn_entry (vm, vm->defn_number + insn.operand);
	int n = vm->returning;
	i32 *after;

	after = emit_call (vm, n == -1 ? CALL : TAILCALL, entry);
	if (0 < n) emit_drop (vm, n);

	update_stack (vm, entry->popping, entry->pushing - entry->popping);
	update_width (vm);
	note_frame_map (vm, after, entry->popping);
	vm->returning = -1;
	break;
      }

    case LOCAL: 
      if ((unsigned) vm->locals <= (unsigned) insn.operand)
	bad_defn (vm, "Reference to nonexistent local");
      emit_immediate (vm, LOCAL, insn.operand, LOCAL0, 0, 3);
      update_stack (vm, 0, 1);
      vm->returning = -1;
      break;

    case DROP:
      {
	int locals = insn.operand;
	if (locals < 0)
	  bad_defn (vm, "Can't DROP a negative amount");

	{
	  Nest *nest = vm->nsp++;
	  if (vm->nesting + vm->ns_size <= nest)
	    bad_defn (vm, "Too many levels of control-flow nesting at DROP");
	  nest->opcode = DROP;
	  nest->operand = locals;
	}

	emit_drop (vm, locals);
	update_locals (vm, -locals);
	update_width (vm);
	if (0 <= vm->returning)
	  vm->returning += locals;
	break;
      }

    case save:
      {
	i32 *after = vm->there;
	emit (vm, save);
	update_stack (vm, 0, 1);
	note_frame_map (vm, after, 0);
	vm->returning = -1;
	break;
      }

    case PUSH:
      {
	emit_immediate (vm, PUSH, insn.operand, PUSH_1, -1, 4);
	update_stack (vm, 0, 1);
	update_width (vm);
	vm->returning = -1;
	break;
      }

    /* We list all the primitive cases explicitly here so anything
       else causes an error */
#include "prims.inc"
      emit (vm, insn.opcode);
      update_stack (vm,
		    op_effect[insn.opcode].arg_count, 
		    op_effect[insn.opcode].delta);
      update_width (vm);
      vm->returning = -1;
      break;

    default:
      bad_defn (vm, "Invalid opcode");
    }
}


/* FIXME: note that preconditions like the next two below hold for
   most of the other functions here...  When some version of these
   functions becomes part of the public API we'll have to figure out
   which preconditions we can avoid and which will turn into checked
   error conditions. */

/* Start compiling a new defn.
   Pre: we're not already in a defn. */
static void
start_defn (VM *vm)
{
  vm->height = vm->entries[vm->defn_number].pushing;
  vm->locals = 0;
  vm->max_width = vm->height;
  vm->returning = 0;
  vm->bb_end = vm->there;
  emit (vm, RETURN);
}


/* Finish compiling a defn. 
   Pre: we're currently in a defn. */
static void
finish_defn (VM *vm)
{
  if (vm->nsp != vm->nesting)
    bad_defn (vm, "Badly nested control flow: unclosed");

  if (vm->height != vm->entries [vm->defn_number].popping)
    bad_defn (vm, "Inaccurate stack effect declaration "
	       "(inferred %d arguments, not %d)",
	       vm->height, vm->entries [vm->defn_number].popping);

  basic_block_boundary (vm);

  /* + 1 is for any return address on the return stack */
  emit_lit (vm, vm->max_width + 1);

  resolve (vm, vm->defn_number, vm->there);

  if (0 == vm->defn_number)
    {				/* The main entry point */
      Entry *e = &vm->entries[vm->defn_number];
      /* We check for these errors here rather than in set_initial_pc
	 so that the error message will include the right defn number. */
      if (e->popping != 0)
	bad_defn (vm, "Entry point must take no argument");
      if (e->pushing != 1)
	bad_defn (vm, "Entry point must return a status value");
    }

  vm->defn_number++;
}


/* Set the initial program counter for `vm', either from its first
   defn (if the return stack is empty), or from after a `save'
   instruction (otherwise). */
static void
set_initial_pc (VM *vm)
{
  if (vm->rp == vm->stack + vm->stack_size - 1)
    {
      /* TODO: give a better error message if the object file has no code. */
      Entry *e = defn_entry (vm, 0);
      /* We start off with a tail-call through the stub to avoid
         repeating that instruction's fuel- and stack-checking logic: */
      vm->pc = vm->stub;
      vm->stub[0] = (i32) opcode_labels[TAILCALL];
      vm->stub[1] = (i32) e->address;
    }
  else
    {
      if (!idel_development_enabled)
	die ("This input file has a pickled stack, which is an unsupported "
	     "still-unsafe feature");
      vm->pc = (i32 *) *(vm->rp)++;
      /* TODO: make sure we're guaranteed pc[-1] is not a segfault */
      /* (Actually, do we really care if it stopped at a `save'?
	 Only for the sake of pushing -1...) */
      if (vm->pc[-1] != (i32) opcode_labels[save])
	bad_input ("Restored program wasn't suspended at a `save' instruction");
      /* FIXME: check for stack overflow!  Or why not have the `save'
	 operation push this before pickling?  Well, that's no help in
	 general because in thawing out we'd still have to supply
	 values on the stack to whatever's pending... hm.  */
      *(vm->sp)++ = -1;
    }
}


static void
set_initial_data_size (VM *vm)
{
  vm->data_size = word_align (vm->data_ptr);
}


/* Input */

/* Return the next insn from `or'. */
static Insn
pop_insn (OR *or)
{
  Insn insn;

  insn.opcode = pop_u8 (or);
  switch (insn.opcode)
    {
    case DROP: 
    case LOCAL:
      insn.operand = pop_u32 (or);
      break;
    case PUSH: 
    case CALL:
      insn.operand = pop_i32 (or);
      break;
    default:
      insn.operand = 0;
      break;
    }
  return insn;
}


/* Compile the next defn from `or'. */
static void
pop_defn (OR *or, VM *vm)
{
  start_defn (vm);
  while (or->ptr < or->limit)
    translate_insn (vm, pop_insn (or));
  finish_defn (vm);
}


/* Compile a block of defns from `or'. */
static void
pop_defns (OR *or, VM *vm)
{
  u32 n = pop_u32 (or);
  u32 i;
  int j;

  start_defns (vm, n);
  for (j = vm->block_start; j < vm->block_end; ++j)
    {
      u32 stack_effect = pop_u32 (or);
      uninterleave_bits (&vm->entries[j].popping, 
			 &vm->entries[j].pushing, 
			 stack_effect);
    }

  for (i = 0; i < n; ++i)
    {
      i8 *L = start_subfile_in (or);
      pop_defn (or, vm);
      end_subfile_in (or, L);
    }
  if (or->limit != or->ptr)
    bad_defn (vm, "Code left over in block");
  finish_defns (vm);
}


/* Compile a block of literal ints from `or'. */
static void
pop_ints (OR *or, VM *vm)
{
  while (or->ptr < or->limit)
    emit_data_int (vm, pop_i32 (or));
}


/* Compile a block of literal bytes from `or'. */
static void
pop_bytes (OR *or, VM *vm)
{
  while (or->ptr < or->limit)
    emit_data_byte (vm, (i8) pop_u8 (or));
}


/* Compile a block of zero bytes from `or'. */
static void
pop_zeroes (OR *or, VM *vm)
{
  i32 count = pop_i32 (or);
  if (or->limit != or->ptr)
    bad_input ("Overlong Zeroes block");

  if (vm->data_size < vm->data_ptr + count ||
      vm->data_ptr + count < vm->data_ptr)
    bad_input ("Data count out of range in Zeroes");

  vm->data_ptr += count;
}


/* Return a new OR containing the bytes between [start..end)
   (by reference, not by copy). */
static OR *
or_subfile (i8 *start, i8 *end)
{
  OR *or = allot (sizeof *or);
  or->buffer = start;
  or->ptr = start;
  or->limit = end;
  return or;
}


/* Add to vm's data and return stacks the next stack frame from `or'. */
static void
pop_frame (OR *or, VM *vm)
{
  u32 fm_index = pop_u32 (or);
  if ((u32)(vm->num_fms) <= fm_index)
    bad_input ("Nonsensical frame label");
  {
    int i;
    const Frame_map *m = vm->fm + fm_index;
    if (vm->rp - vm->sp < m->locals + m->height + 1)
      die ("Out of stack space");

    for (i = m->locals - 1; 0 <= i; --i)
      *--(vm->rp) = pop_i32 (or);
    *--(vm->rp) = (i32) m->code;
    for (i = m->height - 1; 0 <= i; --i)
      *(vm->sp)++ = pop_i32 (or);
  }
}


/* Fill vm's stacks from a stack section in `or'. */
static void
pop_stack (OR *or, VM *vm)
{
  if (vm->rp != vm->stack + vm->stack_size - 1)
    bad_input ("Object file with more than one stack section");

  while (or->ptr < or->limit)
    pop_frame (or, vm);

  /* FIXME: need to check that the bottommost frame yields exactly one
   value.  Do that by checking the signature of the defn that the
   return address of the bottommost frame is in.  To do that, modify
   pop_frame to return the frame map or something.  Then how do we get
   from return address to defn?  Ugh.  Actually, you need to work out
   exactly what a valid pickled stack can look like, before writing
   any more code.  Otherwise you'll get badly embarrassed. 
   
   So we need two extra pieces of info in the frame map: how many
   return values we're expecting at this return point, and how many
   values we will return to our caller.  But couldn't tail calls
   produce situations with stack values belonging to nobody?  I guess
   we have to calculate how many of those there will be, by comparing
   the signatures of caller and returner, as we pop each frame. 

   Also the stack pickling needs to be fixed in the same way.  Whee.
   */
}


/* Load the object file `or' into `vm'. */
void
vm_load (VM *vm, OR *or)
{
  pop_header (or);
  while (or->ptr < or->limit)
    {
      i8 *p = or->ptr;
      int tag = pop_tag (or);
      i8 *L = start_subfile_in (or);
      switch (tag)
	{
	case tag_defns: 
	  /* TODO: remember multiple DEFNS blocks.  FIXME: until then,
	     we should raise an error if there are > 1 of them */
	  vm->obj_code = or_subfile (p, or->limit); 
	  pop_defns (or, vm); 
	  break;
	case tag_bytes: 
	  pop_bytes (or, vm); 
	  break;
	case tag_ints: 
	  pop_ints (or, vm); 
	  break;
	case tag_zeroes: 
	  pop_zeroes (or, vm); 
	  break;
	case tag_stack:
	  pop_stack (or, vm);
	  break;
	default: 
	  bad_input ("Unknown block tag");
	}
      end_subfile_in (or, L);
    }

  set_initial_data_size (vm);
  set_initial_pc (vm);
}