verify-impl.c

/* Copyright (C) 2001, 2002, 2003, 2004, 2005, 2006, 2008, 2009
   Free Software Foundation

   This file is part of libgcj.

This software is copyrighted work licensed under the terms of the
Libgcj License.  Please consult the file "LIBGCJ_LICENSE" for
details.  */

/* Written by Tom Tromey <tromey@redhat.com>  */

/* Uncomment this to enable debugging output.  */
/* #define VERIFY_DEBUG */

#include "config.h"

#include "verify.h"

/* Hack to work around namespace pollution from java-tree.h.  */
#undef current_class

#ifdef VERIFY_DEBUG
#include <stdio.h>
#endif /* VERIFY_DEBUG */

/* This is used to mark states which are not scheduled for
   verification. */
#define INVALID_STATE ((state *) -1)

static void ATTRIBUTE_PRINTF_1
debug_print (const char *fmt ATTRIBUTE_UNUSED, ...)
{
#ifdef VERIFY_DEBUG
  va_list ap;
  va_start (ap, fmt);
  vfprintf (stderr, fmt, ap);
  va_end (ap);
#endif /* VERIFY_DEBUG */
}

/* This started as a fairly ordinary verifier, and for the most part
   it remains so.  It works in the obvious way, by modeling the effect
   of each opcode as it is encountered.  For most opcodes, this is a
   straightforward operation.

   This verifier does not do type merging.  It used to, but this
   results in difficulty verifying some relatively simple code
   involving interfaces, and it pushed some verification work into the
   interpreter.

   Instead of merging reference types, when we reach a point where two
   flows of control merge, we simply keep the union of reference types
   from each branch.  Then, when we need to verify a fact about a
   reference on the stack (e.g., that it is compatible with the
   argument type of a method), we check to ensure that all possible
   types satisfy the requirement.

   Another area this verifier differs from the norm is in its handling
   of subroutines.  The JVM specification has some confusing things to
   say about subroutines.  For instance, it makes claims about not
   allowing subroutines to merge and it rejects recursive subroutines.
   For the most part these are red herrings; we used to try to follow
   these things but they lead to problems.  For example, the notion of
   "being in a subroutine" is not well-defined: is an exception
   handler in a subroutine?  If you never execute the `ret' but
   instead `goto 1' do you remain in the subroutine?

   For clarity on what is really required for type safety, read
   "Simple Verification Technique for Complex Java Bytecode
   Subroutines" by Alessandro Coglio.  Among other things this paper
   shows that recursive subroutines are not harmful to type safety.
   We implement something similar to what he proposes.  Note that this
   means that this verifier will accept code that is rejected by some
   other verifiers.

   For those not wanting to read the paper, the basic observation is
   that we can maintain split states in subroutines.  We maintain one
   state for each calling `jsr'.  In other words, we re-verify a
   subroutine once for each caller, using the exact types held by the
   callers (as opposed to the old approach of merging types and
   keeping a bitmap registering what did or did not change).  This
   approach lets us continue to verify correctly even when a
   subroutine is exited via `goto' or `athrow' and not `ret'.

   In some other areas the JVM specification is (mildly) incorrect,
   so we diverge.  For instance, you cannot
   violate type safety by allocating an object with `new' and then
   failing to initialize it, no matter how one branches or where one
   stores the uninitialized reference.  See "Improving the official
   specification of Java bytecode verification" by Alessandro Coglio.

   Note that there's no real point in enforcing that padding bytes or
   the mystery byte of invokeinterface must be 0, but we do that
   regardless.

   The verifier is currently neither completely lazy nor eager when it
   comes to loading classes.  It tries to represent types by name when
   possible, and then loads them when it needs to verify a fact about
   the type.  Checking types by name is valid because we only use
   names which come from the current class' constant pool.  Since all
   such names are looked up using the same class loader, there is no
   danger that we might be fooled into comparing different types with
   the same name.

   In the future we plan to allow for a completely lazy mode of
   operation, where the verifier will construct a list of type
   assertions to be checked later.

   Some test cases for the verifier live in the "verify" module of the
   Mauve test suite.  However, some of these are presently
   (2004-01-20) believed to be incorrect.  (More precisely the notion
   of "correct" is not well-defined, and this verifier differs from
   others while remaining type-safe.)  Some other tests live in the
   libgcj test suite.

   This verifier is also written to be pluggable.  This means that it
   is intended for use in a variety of environments, not just libgcj.
   As a result the verifier expects a number of type and method
   declarations to be declared in "verify.h".  The intent is that you
   recompile the verifier for your particular environment.  This
   approach was chosen so that operations could be inlined in verify.h
   as much as possible.

   See the verify.h that accompanies this copy of the verifier to see
   what types, preprocessor defines, and functions must be declared.
   The interface is ad hoc, but was defined so that it could be
   implemented to connect to a pure C program.
*/

#define FLAG_INSN_START 1
#define FLAG_BRANCH_TARGET 2
#define FLAG_INSN_SEEN 4

struct state;
struct type;
struct ref_intersection;

typedef struct state state;
typedef struct type type;
typedef struct ref_intersection ref_intersection;

/*typedef struct state_list state_list;*/

typedef struct state_list
{
  state *val;
  struct state_list *next;
} state_list;

typedef struct vfy_string_list
{
  vfy_string val;
  struct vfy_string_list *next;
} vfy_string_list;

typedef struct verifier_context
{
  /* The current PC.  */
  int PC;
  /* The PC corresponding to the start of the current instruction.  */
  int start_PC;

  /* The current state of the stack, locals, etc.  */
  state *current_state;

  /* At each branch target we keep a linked list of all the states we
     can process at that point.  We'll only have multiple states at a
     given PC if they both have different return-address types in the
     same stack or local slot.  This array is indexed by PC and holds
     the list of all such states.  */
  state_list **states;

  /* We keep a linked list of all the states which we must reverify.
     This is the head of the list.  */
  state *next_verify_state;

  /* We keep some flags for each instruction.  The values are the
     FLAG_* constants defined above.  This is an array indexed by PC.  */
  char *flags;

  /* The bytecode itself.  */
  const unsigned char *bytecode;
  /* The exceptions.  */
  vfy_exception *exception;

  /* Defining class.  */
  vfy_jclass current_class;
  /* This method.  */
  vfy_method *current_method;

  /* A linked list of utf8 objects we allocate.  */
  vfy_string_list *utf8_list;

  /* A linked list of all ref_intersection objects we allocate.  */
  ref_intersection *isect_list;
} verifier_context;

/* The current verifier's state data. This is maintained by
   {push/pop}_verifier_context to provide a shorthand form to access
   the verification state. */
static GTY(()) verifier_context *vfr;

/* Local function declarations.  */
bool type_initialized (type *t);
int ref_count_dimensions (ref_intersection *ref);

static void
verify_fail_pc (const char *s, int pc)
{
  vfy_fail (s, pc, vfr->current_class, vfr->current_method);  
}

static void
verify_fail (const char *s)
{
  verify_fail_pc (s, vfr->PC);
}

/* This enum holds a list of tags for all the different types we
   need to handle.  Reference types are treated specially by the
   type class.  */
typedef enum type_val
{
  void_type,

  /* The values for primitive types are chosen to correspond to values
     specified to newarray. */
  boolean_type = 4,
  char_type = 5,
  float_type = 6,
  double_type = 7,
  byte_type = 8,
  short_type = 9,
  int_type = 10,
  long_type = 11,

  /* Used when overwriting second word of a double or long in the
     local variables.  Also used after merging local variable states
     to indicate an unusable value.  */
  unsuitable_type,
  return_address_type,
  /* This is the second word of a two-word value, i.e., a double or
     a long.  */
  continuation_type,

  /* Everything after `reference_type' must be a reference type.  */
  reference_type,
  null_type,
  uninitialized_reference_type
} type_val;

/* This represents a merged class type.  Some verifiers (including
   earlier versions of this one) will compute the intersection of
   two class types when merging states.  However, this loses
   critical information about interfaces implemented by the various
   classes.  So instead we keep track of all the actual classes that
   have been merged.  */
struct ref_intersection
{
  /* Whether or not this type has been resolved.  */
  bool is_resolved;

  /* Actual type data.  */
  union
  {
    /* For a resolved reference type, this is a pointer to the class.  */
    vfy_jclass klass;
    /* For other reference types, this it the name of the class.  */
    vfy_string name;
  } data;

  /* Link to the next reference in the intersection.  */
  ref_intersection *ref_next;

  /* This is used to keep track of all the allocated
     ref_intersection objects, so we can free them.
     FIXME: we should allocate these in chunks.  */
  ref_intersection *alloc_next;
};

static ref_intersection *
make_ref (void)
{
  ref_intersection *new_ref = 
    (ref_intersection *) vfy_alloc (sizeof (ref_intersection));

  new_ref->alloc_next = vfr->isect_list;
  vfr->isect_list = new_ref;
  return new_ref;
}

static ref_intersection *
clone_ref (ref_intersection *dup)
{
  ref_intersection *new_ref = make_ref ();

  new_ref->is_resolved = dup->is_resolved;
  new_ref->data = dup->data;
  return new_ref;
}

static void 
resolve_ref (ref_intersection *ref)
{
  if (ref->is_resolved)
    return;
  ref->data.klass = vfy_find_class (vfr->current_class, ref->data.name);
  ref->is_resolved = true;
}

static bool 
refs_equal (ref_intersection *ref1, ref_intersection *ref2)
{
  if (! ref1->is_resolved && ! ref2->is_resolved
      && vfy_strings_equal (ref1->data.name, ref2->data.name))
    return true;
  if (! ref1->is_resolved)
    resolve_ref (ref1);
  if (! ref2->is_resolved)
    resolve_ref (ref2);
  return ref1->data.klass == ref2->data.klass;
}

/* Merge REF1 type into REF2, returning the result.  This will
   return REF2 if all the classes in THIS already appear in
   REF2.  */
static ref_intersection *
merge_refs (ref_intersection *ref1, ref_intersection *ref2)
{
  ref_intersection *tail = ref2;
  for (; ref1 != NULL; ref1 = ref1->ref_next)
    {
      bool add = true;
      ref_intersection *iter;
      for (iter = ref2; iter != NULL; iter = iter->ref_next)
	{
	  if (refs_equal (ref1, iter))
	    {
	      add = false;
	      break;
	    }
	}

      if (add)
        {
	  ref_intersection *new_tail = clone_ref (ref1);
	  new_tail->ref_next = tail;
	  tail = new_tail;
	}
    }
  return tail;
}

/* See if an object of type SOURCE can be assigned to an object of
   type TARGET.  This might resolve classes in one chain or the other.  */
static bool 
ref_compatible (ref_intersection *target, ref_intersection *source)
{
  for (; target != NULL; target = target->ref_next)
    {
      ref_intersection *source_iter = source;

      for (; source_iter != NULL; source_iter = source_iter->ref_next)
	{
	  /* Avoid resolving if possible.  */
	  if (! target->is_resolved
	      && ! source_iter->is_resolved
	      && vfy_strings_equal (target->data.name,
				    source_iter->data.name))
	    continue;

	  if (! target->is_resolved)
	    resolve_ref (target);
	  if (! source_iter->is_resolved)
	    resolve_ref (source_iter);

	  if (! vfy_is_assignable_from (target->data.klass,
	  			        source_iter->data.klass))
	    return false;
	}
    }

  return true;
}

static bool 
ref_isarray (ref_intersection *ref)
{
  /* assert (ref_next == NULL);  */
  if (ref->is_resolved)
    return vfy_is_array (ref->data.klass);
  else
    return vfy_string_bytes (ref->data.name)[0] == '[';
}

static bool
ref_isinterface (ref_intersection *ref)
{
  /* assert (ref_next == NULL);  */
  if (! ref->is_resolved)
    resolve_ref (ref);
  return vfy_is_interface (ref->data.klass);
}

static bool
ref_isabstract (ref_intersection *ref)
{
  /* assert (ref_next == NULL); */
  if (! ref->is_resolved)
    resolve_ref (ref);
  return vfy_is_abstract (ref->data.klass);
}

static vfy_jclass 
ref_getclass (ref_intersection *ref)
{
  if (! ref->is_resolved)
    resolve_ref (ref);
  return ref->data.klass;
}

int
ref_count_dimensions (ref_intersection *ref)
{
  int ndims = 0;
  if (ref->is_resolved)
    {
      vfy_jclass k = ref->data.klass;
      while (vfy_is_array (k))
	{
 	  k = vfy_get_component_type (k);
	  ++ndims;
	}
    }
  else
    {
      const char *p = vfy_string_bytes (ref->data.name);
      while (*p++ == '[')
	++ndims;
    }
  return ndims;
}

/* Return the type_val corresponding to a primitive signature
   character.  For instance `I' returns `int.class'.  */
static type_val
get_type_val_for_signature (char sig)
{
  type_val rt;
  switch (sig)
    {
    case 'Z':
      rt = boolean_type;
      break;
    case 'B':
      rt = byte_type;
      break;
    case 'C':
      rt = char_type;
      break;
    case 'S':
      rt = short_type;
      break;
    case 'I':
      rt = int_type;
      break;
    case 'J':
      rt = long_type;
      break;
    case 'F':
      rt = float_type;
      break;
    case 'D':
      rt = double_type;
      break;
    case 'V':
      rt = void_type;
      break;
    default:
      verify_fail ("invalid signature");
      return null_type;
    }
  return rt;
}

/* Return the type_val corresponding to a primitive class.  */
static type_val
get_type_val_for_primtype (vfy_jclass k)
{
  return get_type_val_for_signature (vfy_get_primitive_char (k));
}

/* The `type' class is used to represent a single type in the verifier.  */
struct type
{
  /* The type key.  */
  type_val key;

  /* For reference types, the representation of the type.  */
  ref_intersection *klass;

  /* This is used in two situations.
  
     First, when constructing a new object, it is the PC of the
     `new' instruction which created the object.  We use the special
     value UNINIT to mean that this is uninitialized.  The special
     value SELF is used for the case where the current method is
     itself the <init> method.  the special value EITHER is used
     when we may optionally allow either an uninitialized or
     initialized reference to match.
  
     Second, when the key is return_address_type, this holds the PC
     of the instruction following the `jsr'.  */
  int pc;

#define UNINIT -2
#define SELF -1
#define EITHER -3
};

/* Make a new instance given the type tag.  We assume a generic
   `reference_type' means Object.  */
static void
init_type_from_tag (type *t, type_val k)
{
  t->key = k;
  /* For reference_type, if KLASS==NULL then that means we are
     looking for a generic object of any kind, including an
     uninitialized reference.  */
  t->klass = NULL;
  t->pc = UNINIT;
}

/* Make a type for the given type_val tag K.  */
static type
make_type (type_val k)
{
  type t;
  init_type_from_tag (&t, k);
  return t;
}

/* Make a new instance given a class.  */
static void
init_type_from_class (type *t, vfy_jclass k)
{
  t->key = reference_type;
  t->klass = make_ref ();
  t->klass->is_resolved = true;
  t->klass->data.klass = k;
  t->klass->ref_next = NULL;
  t->pc = UNINIT;
}

static type
make_type_from_class (vfy_jclass k)
{
  type t;
  init_type_from_class (&t, k);
  return t;
}

static void
init_type_from_string (type *t, vfy_string n)
{
  t->key = reference_type;
  t->klass = make_ref ();
  t->klass->is_resolved = false;
  t->klass->data.name = n;
  t->klass->ref_next = NULL;
  t->pc = UNINIT;
}

static type
make_type_from_string (vfy_string n)
{
  type t;
  init_type_from_string (&t, n);
  return t;
}

/* Promote a numeric type.  */
static void
vfy_promote_type (type *t)
{
  if (t->key == boolean_type || t->key == char_type
      || t->key == byte_type || t->key == short_type)
    t->key = int_type;
}
#define promote_type vfy_promote_type

/* Mark this type as the uninitialized result of `new'.  */
static void
type_set_uninitialized (type *t, int npc)
{
  if (t->key == reference_type)
    t->key = uninitialized_reference_type;
  else
    verify_fail ("internal error in type::uninitialized");
  t->pc = npc;
}

/* Mark this type as now initialized.  */
static void
type_set_initialized (type *t, int npc)
{
  if (npc != UNINIT && t->pc == npc && t->key == uninitialized_reference_type)
    {
      t->key = reference_type;
      t->pc = UNINIT;
    }
}

/* Mark this type as a particular return address.  */
static void type_set_return_address (type *t, int npc)
{
  t->pc = npc;
}

/* Return true if this type and type OTHER are considered
   mergeable for the purposes of state merging.  This is related
   to subroutine handling.  For this purpose two types are
   considered unmergeable if they are both return-addresses but
   have different PCs.  */
static bool
type_state_mergeable_p (type *t1, type *t2)
{
  return (t1->key != return_address_type
	  || t2->key != return_address_type
	  || t1->pc == t2->pc);
}

/* Return true if an object of type K can be assigned to a variable
   of type T.  Handle various special cases too.  Might modify
   T or K.  Note however that this does not perform numeric
   promotion.  */
static bool 
types_compatible (type *t, type *k)
{
  /* Any type is compatible with the unsuitable type.  */
  if (k->key == unsuitable_type)
    return true;

  if (t->key < reference_type || k->key < reference_type)
    return t->key == k->key;

  /* The `null' type is convertible to any initialized reference
     type.  */
  if (t->key == null_type)
    return k->key != uninitialized_reference_type;
  if (k->key == null_type)
    return t->key != uninitialized_reference_type;

  /* A special case for a generic reference.  */
  if (t->klass == NULL)
    return true;
  if (k->klass == NULL)
    verify_fail ("programmer error in type::compatible");

  /* Handle the special 'EITHER' case, which is only used in a
     special case of 'putfield'.  Note that we only need to handle
     this on the LHS of a check.  */
  if (! type_initialized (t) && t->pc == EITHER)
    {
      /* If the RHS is uninitialized, it must be an uninitialized
	 'this'.  */
      if (! type_initialized (k) && k->pc != SELF)
	return false;
    }
  else if (type_initialized (t) != type_initialized (k))
    {
      /* An initialized type and an uninitialized type are not
	 otherwise compatible.  */
      return false;
    }
  else
    {
      /* Two uninitialized objects are compatible if either:
       * The PCs are identical, or
       * One PC is UNINIT.  */
      if (type_initialized (t))
	{
	  if (t->pc != k->pc && t->pc != UNINIT && k->pc != UNINIT)
	    return false;
	}
    }

  return ref_compatible (t->klass, k->klass);
}

/* Return true if two types are equal.  Only valid for reference
   types.  */
static bool
types_equal (type *t1, type *t2)
{
  if ((t1->key != reference_type && t1->key != uninitialized_reference_type)
      || (t2->key != reference_type
	  && t2->key != uninitialized_reference_type))
    return false;
  /* Only single-ref types are allowed.  */
  if (t1->klass->ref_next || t2->klass->ref_next)
    return false;
  return refs_equal (t1->klass, t2->klass);
}

static bool
type_isvoid (type *t)
{
  return t->key == void_type;
}

static bool
type_iswide (type *t)
{
  return t->key == long_type || t->key == double_type;
}

/* Return number of stack or local variable slots taken by this type.  */  
static int
type_depth (type *t)
{
  return type_iswide (t) ? 2 : 1;
}

static bool
type_isarray (type *t)
{
  /* We treat null_type as not an array.  This is ok based on the
     current uses of this method.  */
  if (t->key == reference_type)
    return ref_isarray (t->klass);
  return false;
}

static bool
type_isnull (type *t)
{
  return t->key == null_type;
}

static bool
type_isinterface (type *t)
{
  if (t->key != reference_type)
    return false;
  return ref_isinterface (t->klass);
}

static bool
type_isabstract (type *t)
{
  if (t->key != reference_type)
    return false;
  return ref_isabstract (t->klass);
}

/* Return the element type of an array.  */
static type
type_array_element (type *t)
{
  type et;
  vfy_jclass k;

  if (t->key != reference_type)
    verify_fail ("programmer error in type::element_type()");

  k = vfy_get_component_type (ref_getclass (t->klass));
  if (vfy_is_primitive (k))
    init_type_from_tag (&et, get_type_val_for_primtype (k));
  else
    init_type_from_class (&et, k);
  return et;
}

/* Return the array type corresponding to an initialized
   reference.  We could expand this to work for other kinds of
   types, but currently we don't need to.  */
static type 
type_to_array (type *t)
{
  type at;
  vfy_jclass k;

  if (t->key != reference_type)
    verify_fail ("internal error in type::to_array()");

  k = ref_getclass (t->klass);
  init_type_from_class (&at, vfy_get_array_class (k));
  return at;
}

static bool
type_isreference (type *t)
{
  return t->key >= reference_type;
}

static int
type_get_pc (type *t)
{
  return t->pc;
}

bool
type_initialized (type *t)
{
  return t->key == reference_type || t->key == null_type;
}

static void
type_verify_dimensions (type *t, int ndims)
{
  /* The way this is written, we don't need to check isarray().  */
  if (t->key != reference_type)
    verify_fail ("internal error in verify_dimensions:"
			   " not a reference type");

  if (ref_count_dimensions (t->klass) < ndims)
    verify_fail ("array type has fewer dimensions"
			   " than required");
}

/* Merge OLD_TYPE into this.  On error throw exception.  Return
   true if the merge caused a type change.  */
static bool
merge_types (type *t, type *old_type, bool local_semantics)
{
  bool changed = false;
  bool refo = type_isreference (old_type);
  bool refn = type_isreference (t);
  if (refo && refn)
    {
      if (old_type->key == null_type)
	;
      else if (t->key == null_type)
	{
	  *t = *old_type;
	  changed = true;
	}
      else if (type_initialized (t) != type_initialized (old_type))
	verify_fail ("merging initialized and uninitialized types");
      else
	{
	  ref_intersection *merged;
	  if (! type_initialized (t))
	    {
	      if (t->pc == UNINIT)
		t->pc = old_type->pc;
	      else if (old_type->pc == UNINIT)
		;
	      else if (t->pc != old_type->pc)
		verify_fail ("merging different uninitialized types");
	    }

	  merged = merge_refs (old_type->klass, t->klass);
	  if (merged != t->klass)
	    {
	      t->klass = merged;
	      changed = true;
	    }
	}
    }
  else if (refo || refn || t->key != old_type->key)
    {
      if (local_semantics)
	{
	  /* If we already have an `unsuitable' type, then we
	     don't need to change again.  */
	  if (t->key != unsuitable_type)
	    {
	      t->key = unsuitable_type;
	      changed = true;
	    }
	}
      else
	verify_fail ("unmergeable type");
    }
  return changed;
}

#ifdef VERIFY_DEBUG
static void 
type_print (type *t)
{
  char c = '?';
  switch (t->key)
    {
    case boolean_type: c = 'Z'; break;
    case byte_type: c = 'B'; break;
    case char_type: c = 'C'; break;
    case short_type: c = 'S'; break;
    case int_type: c = 'I'; break;
    case long_type: c = 'J'; break;
    case float_type: c = 'F'; break;
    case double_type: c = 'D'; break;
    case void_type: c = 'V'; break;
    case unsuitable_type: c = '-'; break;
    case return_address_type: c = 'r'; break;
    case continuation_type: c = '+'; break;
    case reference_type: c = 'L'; break;
    case null_type: c = '@'; break;
    case uninitialized_reference_type: c = 'U'; break;
    }
  debug_print ("%c", c);
}
#endif /* VERIFY_DEBUG */

/* This class holds all the state information we need for a given
   location. */
struct state
{
  /* The current top of the stack, in terms of slots.  */
  int stacktop;
  /* The current depth of the stack.  This will be larger than
     STACKTOP when wide types are on the stack.  */
  int stackdepth;
  /* The stack.  */
  type *stack;
  /* The local variables.  */
  type *locals;
  /* We keep track of the type of `this' specially.  This is used to
     ensure that an instance initializer invokes another initializer
     on `this' before returning.  We must keep track of this
     specially because otherwise we might be confused by code which
     assigns to locals[0] (overwriting `this') and then returns
     without really initializing.  */
  type this_type;

  /* The PC for this state.  This is only valid on states which are
     permanently attached to a given PC.  For an object like
     `current_state', which is used transiently, this has no
     meaning.  */
  int pc;
  /* We keep a linked list of all states requiring reverification.
     If this is the special value INVALID_STATE then this state is
     not on the list.  NULL marks the end of the linked list.  */
  state *next;
};

/* NO_NEXT is the PC value meaning that a new state must be
   acquired from the verification list.  */
#define NO_NEXT -1

static void
init_state_with_stack (state *s, int max_stack, int max_locals)
{
  int i;
  s->stacktop = 0;
  s->stackdepth = 0;
  s->stack = (type *) vfy_alloc (max_stack * sizeof (type));
  for (i = 0; i < max_stack; ++i)
    init_type_from_tag (&s->stack[i], unsuitable_type);
  s->locals = (type *) vfy_alloc (max_locals * sizeof (type));
  for (i = 0; i < max_locals; ++i)
    init_type_from_tag (&s->locals[i], unsuitable_type);
  init_type_from_tag (&s->this_type, unsuitable_type);
  s->pc = NO_NEXT;
  s->next = INVALID_STATE;
}

static void
copy_state (state *s, state *copy, int max_stack, int max_locals)
{
  int i;
  s->stacktop = copy->stacktop;
  s->stackdepth = copy->stackdepth;
  for (i = 0; i < max_stack; ++i)
    s->stack[i] = copy->stack[i];
  for (i = 0; i < max_locals; ++i)
    s->locals[i] = copy->locals[i];

  s->this_type = copy->this_type;
  /* Don't modify `next' or `pc'. */
}

static void
copy_state_with_stack (state *s, state *orig, int max_stack, int max_locals)
{
  init_state_with_stack (s, max_stack, max_locals);
  copy_state (s, orig, max_stack, max_locals);
}

/* Allocate a new state, copying ORIG. */
static state *
make_state_copy (state *orig, int max_stack, int max_locals)
{
  state *s = (state *) vfy_alloc (sizeof (state));
  copy_state_with_stack (s, orig, max_stack, max_locals);
  return s;
}

static state *
make_state (int max_stack, int max_locals)
{
  state *s = (state *) vfy_alloc (sizeof (state));
  init_state_with_stack (s, max_stack, max_locals);
  return s;
}

static void
free_state (state *s)
{
  if (s->stack != NULL)
    vfy_free (s->stack);
  if (s->locals != NULL)
    vfy_free (s->locals);
}

/* Modify this state to reflect entry to an exception handler.  */
static void
state_set_exception (state *s, type *t, int max_stack)
{
  int i;
  s->stackdepth = 1;
  s->stacktop = 1;
  s->stack[0] = *t;
  for (i = s->stacktop; i < max_stack; ++i)
    init_type_from_tag (&s->stack[i], unsuitable_type);
}

/* Merge STATE_OLD into this state.  Destructively modifies this
   state.  Returns true if the new state was in fact changed.
   Will throw an exception if the states are not mergeable.  */
static bool
merge_states (state *s, state *state_old, int max_locals)
{
  int i;
  bool changed = false;

  /* Special handling for `this'.  If one or the other is
     uninitialized, then the merge is uninitialized.  */
  if (type_initialized (&s->this_type))
    s->this_type = state_old->this_type;

  /* Merge stacks.  */
  if (state_old->stacktop != s->stacktop)  /* FIXME stackdepth instead?  */
    verify_fail ("stack sizes differ");
  for (i = 0; i < state_old->stacktop; ++i)
    {
      if (merge_types (&s->stack[i], &state_old->stack[i], false))
	changed = true;
    }

  /* Merge local variables.  */
  for (i = 0; i < max_locals; ++i)
    {
      if (merge_types (&s->locals[i], &state_old->locals[i], true))
	changed = true;
    }

  return changed;
}

/* Ensure that `this' has been initialized.  */
static void
state_check_this_initialized (state *s)
{
  if (type_isreference (&s->this_type) && ! type_initialized (&s->this_type))
    verify_fail ("`this' is uninitialized");
}

/* Set type of `this'.  */
static void
state_set_this_type (state *s, type *k)
{
  s->this_type = *k;
}

/* Mark each `new'd object we know of that was allocated at PC as
   initialized.  */
static void
state_set_initialized (state *s, int pc, int max_locals)
{
  int i;
  for (i = 0; i < s->stacktop; ++i)
    type_set_initialized (&s->stack[i], pc);
  for (i = 0; i < max_locals; ++i)
    type_set_initialized (&s->locals[i], pc);
  type_set_initialized (&s->this_type, pc);
}

/* This tests to see whether two states can be considered "merge
   compatible".  If both states have a return-address in the same
   slot, and the return addresses are different, then they are not
   compatible and we must not try to merge them.  */
static bool
state_mergeable_p (state *s, state *other, int max_locals)

{
  int i;

  /* This is tricky: if the stack sizes differ, then not only are
     these not mergeable, but in fact we should give an error, as
     we've found two execution paths that reach a branch target
     with different stack depths.  FIXME stackdepth instead?  */
  if (s->stacktop != other->stacktop)
    verify_fail ("stack sizes differ");

  for (i = 0; i < s->stacktop; ++i)
    if (! type_state_mergeable_p (&s->stack[i], &other->stack[i]))
      return false;
  for (i = 0; i < max_locals; ++i)
    if (! type_state_mergeable_p (&s->locals[i], &other->locals[i]))
      return false;
  return true;
}

static void
state_reverify (state *s)
{
  if (s->next == INVALID_STATE)
    {
      s->next = vfr->next_verify_state;
      vfr->next_verify_state = s;
    }
}

#ifdef VERIFY_DEBUG
static void 
debug_print_state (state *s, const char *leader, int pc, int max_stack, 
		   int max_locals)
{
  int i;
  debug_print ("%s [%4d]:   [stack] ", leader, pc);
  for (i = 0; i < s->stacktop; ++i)
    type_print (&s->stack[i]);
  for (; i < max_stack; ++i)
    debug_print (".");
  debug_print ("    [local] ");
  for (i = 0; i < max_locals; ++i)
    type_print (&s->locals[i]);
  debug_print (" | %p\n", s);
}
#else
static void
debug_print_state (state *s ATTRIBUTE_UNUSED, 
		   const char *leader ATTRIBUTE_UNUSED, 
		   int pc ATTRIBUTE_UNUSED, int max_stack ATTRIBUTE_UNUSED, 
		   int max_locals ATTRIBUTE_UNUSED)
{
}
#endif /* VERIFY_DEBUG */

static type
pop_raw (void)
{
  type r;
  state *s = vfr->current_state;
  if (s->stacktop <= 0)
    verify_fail ("stack empty");
  r = s->stack[--s->stacktop];
  s->stackdepth -= type_depth (&r);
  if (s->stackdepth < 0)
    verify_fail_pc ("stack empty", vfr->start_PC);
  return r;
}

static type
pop32 (void)
{
  type r = pop_raw ();
  if (type_iswide (&r))
    verify_fail ("narrow pop of wide type");
  return r;
}

static type
vfy_pop_type_t (type match)
{
  type t;
  vfy_promote_type (&match);
  t = pop_raw ();
  if (! types_compatible (&match, &t))
    verify_fail ("incompatible type on stack");
  return t;
}

static type
vfy_pop_type (type_val match)
{
  type t = make_type (match);
  return vfy_pop_type_t (t);
}

#define pop_type vfy_pop_type
#define pop_type_t vfy_pop_type_t

/* Pop a reference which is guaranteed to be initialized.  MATCH
   doesn't have to be a reference type; in this case this acts like
   pop_type.  */
static type
pop_init_ref_t (type match)
{
  type t = pop_raw ();
  if (type_isreference (&t) && ! type_initialized (&t))
    verify_fail ("initialized reference required");
  else if (! types_compatible (&match, &t))
    verify_fail ("incompatible type on stack");
  return t;
}

static type
pop_init_ref (type_val match)
{
  type t = make_type (match);
  return pop_init_ref_t (t);
}

/* Pop a reference type or a return address.  */
static type
pop_ref_or_return (void)
{
  type t = pop_raw ();
  if (! type_isreference (&t) && t.key != return_address_type)
    verify_fail ("expected reference or return address on stack");
  return t;
}

static void
vfy_push_type_t (type t)
{
  int depth;
  state *s = vfr->current_state;
  /* If T is a numeric type like short, promote it to int.  */
  promote_type (&t);

  depth = type_depth (&t);

  if (s->stackdepth + depth > vfr->current_method->max_stack)
    verify_fail ("stack overflow");
  s->stack[s->stacktop++] = t;
  s->stackdepth += depth;
}

static void
vfy_push_type (type_val tval)
{
  type t = make_type (tval);
  vfy_push_type_t (t);
}

#define push_type vfy_push_type
#define push_type_t vfy_push_type_t

static void
set_variable (int index, type t)
{
  int depth;
  state *s = vfr->current_state;
  /* If T is a numeric type like short, promote it to int.  */
  promote_type (&t);

  depth = type_depth (&t);
  if (index > vfr->current_method->max_locals - depth)
    verify_fail ("invalid local variable");
  s->locals[index] = t;

  if (depth == 2)
    init_type_from_tag (&s->locals[index + 1], continuation_type);
  if (index > 0 && type_iswide (&s->locals[index - 1]))
    init_type_from_tag (&s->locals[index - 1], unsuitable_type);
}

static type
get_variable_t (int index, type *t)
{
  state *s = vfr->current_state;
  int depth = type_depth (t);
  if (index > vfr->current_method->max_locals - depth)
    verify_fail ("invalid local variable");
  if (! types_compatible (t, &s->locals[index]))
    verify_fail ("incompatible type in local variable");
  if (depth == 2)
    {
      type cont = make_type (continuation_type);
      if (! types_compatible (&s->locals[index + 1], &cont))
	verify_fail ("invalid local variable");
    }
  return s->locals[index];
}

static type
get_variable (int index, type_val v)
{
  type t = make_type (v);
  return get_variable_t (index, &t);
}

/* Make sure ARRAY is an array type and that its elements are
   compatible with type ELEMENT.  Returns the actual element type.  */
static type
require_array_type_t (type array, type element)
{
  type t;
  /* An odd case.  Here we just pretend that everything went ok.  If
     the requested element type is some kind of reference, return
     the null type instead.  */
  if (type_isnull (&array))
    return type_isreference (&element) ? make_type (null_type) : element;

  if (! type_isarray (&array))
    verify_fail ("array required");

  t = type_array_element (&array);
  if (! types_compatible (&element, &t))
    {
      /* Special case for byte arrays, which must also be boolean
         arrays.  */
      bool ok = true;
      if (element.key == byte_type)
	{
	  type e2 = make_type (boolean_type);
	  ok = types_compatible (&e2, &t);
	}
      if (! ok)
	verify_fail ("incompatible array element type");
    }

  /* Return T and not ELEMENT, because T might be specialized.  */
  return t;
}

static type
require_array_type (type array, type_val element)
{
  type t = make_type (element);
  return require_array_type_t (array, t);
}

static jint
get_byte (void)
{
  if (vfr->PC >= vfr->current_method->code_length)
    verify_fail ("premature end of bytecode");
  return (jint) vfr->bytecode[vfr->PC++] & 0xff;
}

static jint
get_ushort (void)
{
  jint b1 = get_byte ();
  jint b2 = get_byte ();
  return (jint) ((b1 << 8) | b2) & 0xffff;
}

static jint
get_short (void)
{
  signed char b1 = (signed char) get_byte ();
  jint b2 = get_byte ();
  jshort s = (b1 << 8) | b2;
  return (jint) s;
}

static jint
get_int (void)
{
  jint b1 = get_byte ();
  jint b2 = get_byte ();
  jint b3 = get_byte ();
  jint b4 = get_byte ();
  jword result = (b1 << 24) | (b2 << 16) | (b3 << 8) | b4;
  /* In the compiler, 'jint' might have more than 32 bits, so we must
     sign extend.  */
  return WORD_TO_INT (result);
}

static int
compute_jump (int offset)
{
  int npc = vfr->start_PC + offset;
  if (npc < 0 || npc >= vfr->current_method->code_length)
    verify_fail_pc ("branch out of range", vfr->start_PC);
  return npc;
}

/* Add a new state to the state list at NPC.  */
static state *
add_new_state (int npc, state *old_state)
{
  state_list *nlink;
  vfy_method *current_method = vfr->current_method;
  state *new_state = make_state_copy (old_state, current_method->max_stack,
				      current_method->max_locals);
  debug_print ("== New state in add_new_state\n");
  debug_print_state (new_state, "New", npc, current_method->max_stack,
		    current_method->max_locals);

  nlink = (state_list *) vfy_alloc (sizeof (state_list));
  nlink->val = new_state;
  nlink->next = vfr->states[npc];
  vfr->states[npc] = nlink;
  new_state->pc = npc;
  return new_state;
}

/* Merge the indicated state into the state at the branch target and
   schedule a new PC if there is a change.  NPC is the PC of the
   branch target, and FROM_STATE is the state at the source of the
   branch.  This method returns true if the destination state
   changed and requires reverification, false otherwise.  */
static void
merge_into (int npc, state *from_state)
{
  /* Iterate over all target states and merge our state into each,
     if applicable.  FIXME one improvement we could make here is
     "state destruction".  Merging a new state into an existing one
     might cause a return_address_type to be merged to
     unsuitable_type.  In this case the resulting state may now be
     mergeable with other states currently held in parallel at this
     location.  So in this situation we could pairwise compare and
     reduce the number of parallel states.  */
  state_list *iter;
  bool applicable = false;
  for (iter = vfr->states[npc]; iter != NULL; iter = iter->next)
    {
      state *new_state = iter->val;
      vfy_method *current_method = vfr->current_method;

      if (state_mergeable_p (new_state, from_state,
					current_method->max_locals))
	{
	  bool changed;
	  applicable = true;

	  debug_print ("== Merge states in merge_into\n");
	  debug_print_state (from_state, "Frm", vfr->start_PC, current_method->max_stack,
			     current_method->max_locals);
	  debug_print_state (new_state, " To", npc, current_method->max_stack,
			    current_method->max_locals);
	  changed = merge_states (new_state, from_state,
				  current_method->max_locals);
	  debug_print_state (new_state, "New", npc, current_method->max_stack,
			    current_method->max_locals);

	  if (changed)
	    state_reverify (new_state);
	}
    }

  if (! applicable)
    {
      /* Either we don't yet have a state at NPC, or we have a
         return-address type that is in conflict with all existing
         state.  So, we need to create a new entry.  */
      state *new_state = add_new_state (npc, from_state);
      /* A new state added in this way must always be reverified.  */
      state_reverify (new_state);
    }
}

static void
push_jump (int offset)
{
  int npc = compute_jump (offset);
  /* According to the JVM Spec, we need to check for uninitialized
     objects here.  However, this does not actually affect type
     safety, and the Eclipse java compiler generates code that
     violates this constraint.  */
  merge_into (npc, vfr->current_state);
}

static void
push_exception_jump (type t, int pc)
{
  state s;
  /* According to the JVM Spec, we need to check for uninitialized
     objects here.  However, this does not actually affect type
     safety, and the Eclipse java compiler generates code that
     violates this constraint.  */
  copy_state_with_stack (&s, vfr->current_state, 
			 vfr->current_method->max_stack,
			 vfr->current_method->max_locals);
  if (vfr->current_method->max_stack < 1)
    verify_fail ("stack overflow at exception handler");
  state_set_exception (&s, &t, vfr->current_method->max_stack);
  merge_into (pc, &s);
  /* FIXME: leak.. need free_state or GC */
}

static state *
pop_jump (void)
{
  state *new_state = vfr->next_verify_state;
  if (new_state == INVALID_STATE)
    verify_fail ("programmer error in pop_jump");
  if (new_state != NULL)
    {
      vfr->next_verify_state = new_state->next;
      new_state->next = INVALID_STATE;
    }
  return new_state;
}

static void
invalidate_pc (void)
{
  vfr->PC = NO_NEXT;
}

static void
note_branch_target (int pc)
{
  /* Don't check `pc <= PC', because we've advanced PC after
     fetching the target and we haven't yet checked the next
     instruction.  */
  if (pc < vfr->PC && ! (vfr->flags[pc] & FLAG_INSN_START))
    verify_fail_pc ("branch not to instruction start", vfr->start_PC);
  vfr->flags[pc] |= FLAG_BRANCH_TARGET;
}

static void
skip_padding (void)
{
  while ((vfr->PC % 4) > 0)
    if (get_byte () != 0)
      verify_fail ("found nonzero padding byte");
}

/* Do the work for a `ret' instruction.  INDEX is the index into the
   local variables.  */
static void
handle_ret_insn (int index)
{
  type ret = make_type (return_address_type);
  type ret_addr = get_variable_t (index, &ret);
  /* It would be nice if we could do this.  However, the JVM Spec
     doesn't say that this is what happens.  It is implied that
     reusing a return address is invalid, but there's no actual
     prohibition against it.  */
  /* set_variable (index, unsuitable_type); */

  int npc = type_get_pc (&ret_addr);
  /* We might be returning to a `jsr' that is at the end of the
     bytecode.  This is ok if we never return from the called
     subroutine, but if we see this here it is an error.  */
  if (npc >= vfr->current_method->code_length)
    verify_fail ("fell off end");

  /* According to the JVM Spec, we need to check for uninitialized
     objects here.  However, this does not actually affect type
     safety, and the Eclipse java compiler generates code that
     violates this constraint.  */
  merge_into (npc, vfr->current_state);
  invalidate_pc ();
}

static void handle_jsr_insn (int offset)
{
  type ret_addr;
  int npc = compute_jump (offset);

  /* According to the JVM Spec, we need to check for uninitialized
     objects here.  However, this does not actually affect type
     safety, and the Eclipse java compiler generates code that
     violates this constraint.  */

  /* Modify our state as appropriate for entry into a subroutine.  */
  ret_addr = make_type (return_address_type);
  type_set_return_address (&ret_addr, vfr->PC);
  vfy_push_type_t (ret_addr);
  merge_into (npc, vfr->current_state);
  invalidate_pc ();
}

static vfy_jclass
construct_primitive_array_type (type_val prim)
{
  vfy_jclass k = NULL;
  switch (prim)
    {
    case boolean_type:
    case char_type:
    case float_type:
    case double_type:
    case byte_type:
    case short_type:
    case int_type:
    case long_type:
      k = vfy_get_primitive_type ((int) prim);
      break;

    /* These aren't used here but we call them out to avoid
       warnings.  */
    case void_type:
    case unsuitable_type:
    case return_address_type:
    case continuation_type:
    case reference_type:
    case null_type:
    case uninitialized_reference_type:
    default:
      verify_fail ("unknown type in construct_primitive_array_type");
    }
  k = vfy_get_array_class (k);
  return k;
}

/* This pass computes the location of branch targets and also
   instruction starts.  */
static void
branch_prepass (void)
{
  int i, pc;
  vfr->flags = (char *) vfy_alloc (vfr->current_method->code_length);

  for (i = 0; i < vfr->current_method->code_length; ++i)
    vfr->flags[i] = 0;

  vfr->PC = 0;
  while (vfr->PC < vfr->current_method->code_length)
    {
      java_opcode opcode;
      /* Set `start_PC' early so that error checking can have the
         correct value.  */
      vfr->start_PC = vfr->PC;
      vfr->flags[vfr->PC] |= FLAG_INSN_START;

      opcode = (java_opcode) vfr->bytecode[vfr->PC++];
      switch (opcode)
	{
	case op_nop:
	case op_aconst_null:
	case op_iconst_m1:
	case op_iconst_0:
	case op_iconst_1:
	case op_iconst_2:
	case op_iconst_3:
	case op_iconst_4:
	case op_iconst_5:
	case op_lconst_0:
	case op_lconst_1:
	case op_fconst_0:
	case op_fconst_1:
	case op_fconst_2:
	case op_dconst_0:
	case op_dconst_1:
	case op_iload_0:
	case op_iload_1:
	case op_iload_2:
	case op_iload_3:
	case op_lload_0:
	case op_lload_1:
	case op_lload_2:
	case op_lload_3:
	case op_fload_0:
	case op_fload_1:
	case op_fload_2:
	case op_fload_3:
	case op_dload_0:
	case op_dload_1:
	case op_dload_2:
	case op_dload_3:
	case op_aload_0:
	case op_aload_1:
	case op_aload_2:
	case op_aload_3:
	case op_iaload:
	case op_laload:
	case op_faload:
	case op_daload:
	case op_aaload:
	case op_baload:
	case op_caload:
	case op_saload:
	case op_istore_0:
	case op_istore_1:
	case op_istore_2:
	case op_istore_3:
	case op_lstore_0:
	case op_lstore_1:
	case op_lstore_2:
	case op_lstore_3:
	case op_fstore_0:
	case op_fstore_1:
	case op_fstore_2:
	case op_fstore_3:
	case op_dstore_0:
	case op_dstore_1:
	case op_dstore_2:
	case op_dstore_3:
	case op_astore_0:
	case op_astore_1:
	case op_astore_2:
	case op_astore_3:
	case op_iastore:
	case op_lastore:
	case op_fastore:
	case op_dastore:
	case op_aastore:
	case op_bastore:
	case op_castore:
	case op_sastore:
	case op_pop:
	case op_pop2:
	case op_dup:
	case op_dup_x1:
	case op_dup_x2:
	case op_dup2:
	case op_dup2_x1:
	case op_dup2_x2:
	case op_swap:
	case op_iadd:
	case op_isub:
	case op_imul:
	case op_idiv:
	case op_irem:
	case op_ishl:
	case op_ishr:
	case op_iushr:
	case op_iand:
	case op_ior:
	case op_ixor:
	case op_ladd:
	case op_lsub:
	case op_lmul:
	case op_ldiv:
	case op_lrem:
	case op_lshl:
	case op_lshr:
	case op_lushr:
	case op_land:
	case op_lor:
	case op_lxor:
	case op_fadd:
	case op_fsub:
	case op_fmul:
	case op_fdiv:
	case op_frem:
	case op_dadd:
	case op_dsub:
	case op_dmul:
	case op_ddiv:
	case op_drem:
	case op_ineg:
	case op_i2b:
	case op_i2c:
	case op_i2s:
	case op_lneg:
	case op_fneg:
	case op_dneg:
	case op_i2l:
	case op_i2f:
	case op_i2d:
	case op_l2i:
	case op_l2f:
	case op_l2d:
	case op_f2i:
	case op_f2l:
	case op_f2d:
	case op_d2i:
	case op_d2l:
	case op_d2f:
	case op_lcmp:
	case op_fcmpl:
	case op_fcmpg:
	case op_dcmpl:
	case op_dcmpg:
	case op_monitorenter:
	case op_monitorexit:
	case op_ireturn:
	case op_lreturn:
	case op_freturn:
	case op_dreturn:
	case op_areturn:
	case op_return:
	case op_athrow:
	case op_arraylength:
	  break;

	case op_bipush:
	case op_ldc:
	case op_iload:
	case op_lload:
	case op_fload:
	case op_dload:
	case op_aload:
	case op_istore:
	case op_lstore:
	case op_fstore:
	case op_dstore:
	case op_astore:
	case op_ret:
	case op_newarray:
	  get_byte ();
	  break;

	case op_iinc:
	case op_sipush:
	case op_ldc_w:
	case op_ldc2_w:
	case op_getstatic:
	case op_getfield:
	case op_putfield:
	case op_putstatic:
	case op_new:
	case op_anewarray:
	case op_instanceof:
	case op_checkcast:
	case op_invokespecial:
	case op_invokestatic:
	case op_invokevirtual:
	  get_short ();
	  break;

	case op_multianewarray:
	  get_short ();
	  get_byte ();
	  break;

	case op_jsr:
	case op_ifeq:
	case op_ifne:
	case op_iflt:
	case op_ifge:
	case op_ifgt:
	case op_ifle:
	case op_if_icmpeq:
	case op_if_icmpne:
	case op_if_icmplt:
	case op_if_icmpge:
	case op_if_icmpgt:
	case op_if_icmple:
	case op_if_acmpeq:
	case op_if_acmpne:
	case op_ifnull:
	case op_ifnonnull:
	case op_goto:
	  note_branch_target (compute_jump (get_short ()));
	  break;

	case op_tableswitch:
	  {
	    jint low, hi;
	    skip_padding ();
	    note_branch_target (compute_jump (get_int ()));
	    low = get_int ();
	    hi = get_int ();
	    if (low > hi)
	      verify_fail_pc ("invalid tableswitch", vfr->start_PC);
	    for (i = low; i <= hi; ++i)
	      note_branch_target (compute_jump (get_int ()));
	  }
	  break;

	case op_lookupswitch:
	  {
	    int npairs;
	    skip_padding ();
	    note_branch_target (compute_jump (get_int ()));
	    npairs = get_int ();
	    if (npairs < 0)
	      verify_fail_pc ("too few pairs in lookupswitch", vfr->start_PC);
	    while (npairs-- > 0)
	      {
		get_int ();
		note_branch_target (compute_jump (get_int ()));
	      }
	  }
	  break;

	case op_invokeinterface:
	  get_short ();
	  get_byte ();
	  get_byte ();
	  break;

	case op_wide:
	  {
	    opcode = (java_opcode) get_byte ();
	    get_short ();
	    if (opcode == op_iinc)
	      get_short ();
	  }
	  break;

	case op_jsr_w:
	case op_goto_w:
	  note_branch_target (compute_jump (get_int ()));
	  break;

#if 0
	/* These are unused here, but we call them out explicitly
	   so that -Wswitch-enum doesn't complain.  */
	case op_putfield_1:
	case op_putfield_2:
	case op_putfield_4:
	case op_putfield_8:
	case op_putfield_a:
	case op_putstatic_1:
	case op_putstatic_2:
	case op_putstatic_4:
	case op_putstatic_8:
	case op_putstatic_a:
	case op_getfield_1:
	case op_getfield_2s:
	case op_getfield_2u:
	case op_getfield_4:
	case op_getfield_8:
	case op_getfield_a:
	case op_getstatic_1:
	case op_getstatic_2s:
	case op_getstatic_2u:
	case op_getstatic_4:
	case op_getstatic_8:
	case op_getstatic_a:
#endif /* VFY_FAST_OPCODES  */
	default:
	  verify_fail_pc ("unrecognized instruction in branch_prepass",
			  vfr->start_PC);
	}

      /* See if any previous branch tried to branch to the middle of
         this instruction.  */
      for (pc = vfr->start_PC + 1; pc < vfr->PC; ++pc)
	{
	  if ((vfr->flags[pc] & FLAG_BRANCH_TARGET))
	    verify_fail_pc ("branch to middle of instruction", pc);
	}
    }

  /* Verify exception handlers.  */
  for (i = 0; i < vfr->current_method->exc_count; ++i)
    {
      int handler, start, end, htype;
      vfy_get_exception (vfr->exception, i, &handler, &start, &end, &htype);
      if (! (vfr->flags[handler] & FLAG_INSN_START))
	verify_fail_pc ("exception handler not at instruction start", 
			handler);
      if (! (vfr->flags[start] & FLAG_INSN_START))
	verify_fail_pc ("exception start not at instruction start", start);
      if (end != vfr->current_method->code_length
	  && ! (vfr->flags[end] & FLAG_INSN_START))
	verify_fail_pc ("exception end not at instruction start", end);

      vfr->flags[handler] |= FLAG_BRANCH_TARGET;
    }
}

static void
check_pool_index (int index)
{
  if (index < 0 || index >= vfy_get_constants_size (vfr->current_class))
    verify_fail_pc ("constant pool index out of range", vfr->start_PC);
}

static type
check_class_constant (int index)
{
  type t = { (type_val) 0, 0, 0 };
  vfy_constants *pool;

  check_pool_index (index);
  pool = vfy_get_constants (vfr->current_class);
  if (vfy_tag (pool, index) == JV_CONSTANT_ResolvedClass)
    init_type_from_class (&t, vfy_get_pool_class (pool, index));
  else if (vfy_tag (pool, index) == JV_CONSTANT_Class)
    init_type_from_string (&t, vfy_get_pool_string (pool, index));
  else
    verify_fail_pc ("expected class constant", vfr->start_PC);      
  return t;
}

static type
check_constant (int index)
{
  type t = { (type_val) 0, 0, 0 };
  vfy_constants *pool;

  check_pool_index (index);
  pool = vfy_get_constants (vfr->current_class);
  if (vfy_tag (pool, index) == JV_CONSTANT_ResolvedString
      || vfy_tag (pool, index) == JV_CONSTANT_String)
    init_type_from_class (&t, vfy_string_type ());
  else if (vfy_tag (pool, index) == JV_CONSTANT_Integer)
    init_type_from_tag (&t, int_type);
  else if (vfy_tag (pool, index) == JV_CONSTANT_Float)
    init_type_from_tag (&t, float_type);
  else if (vfy_tag (pool, index) == JV_CONSTANT_Class
	   || vfy_tag (pool, index) == JV_CONSTANT_ResolvedClass)
    /* FIXME: should only allow this for 1.5 bytecode.  */
    init_type_from_class (&t, vfy_class_type ());
  else
    verify_fail_pc ("String, int, or float constant expected", vfr->start_PC);
  return t;
}

static type
check_wide_constant (int index)
{
  type t = { (type_val) 0, 0, 0 };
  vfy_constants *pool;

  check_pool_index (index);
  pool = vfy_get_constants (vfr->current_class);
  if (vfy_tag (pool, index) == JV_CONSTANT_Long)
    init_type_from_tag (&t, long_type);
  else if (vfy_tag (pool, index) == JV_CONSTANT_Double)
    init_type_from_tag (&t, double_type);
  else
    verify_fail_pc ("long or double constant expected", vfr->start_PC);
  return t;
}

/* Helper for both field and method.  These are laid out the same in
   the constant pool.  */
static type
handle_field_or_method (int index, int expected,
			vfy_string *name, vfy_string *fmtype)
{
  vfy_uint_16 class_index, name_and_type_index;
  vfy_uint_16 name_index, desc_index;
  vfy_constants *pool;

  check_pool_index (index);
  pool = vfy_get_constants (vfr->current_class);
  if (vfy_tag (pool, index) != expected)
    verify_fail_pc ("didn't see expected constant", vfr->start_PC);
  /* Once we know we have a Fieldref or Methodref we assume that it
     is correctly laid out in the constant pool.  I think the code
     in defineclass.cc guarantees this.  */
  vfy_load_indexes (pool, index, &class_index, &name_and_type_index);
  vfy_load_indexes (pool, name_and_type_index, &name_index, &desc_index);

  *name = vfy_get_pool_string (pool, name_index);
  *fmtype = vfy_get_pool_string (pool, desc_index);

  return check_class_constant (class_index);
}

/* Return field's type, compute class' type if requested.  If
   PUTFIELD is true, use the special 'putfield' semantics.  */
static type
check_field_constant (int index, type *class_type, bool putfield)
{
  vfy_string name, field_type;
  const char *typec;
  int len;
  type t;

  type ct = handle_field_or_method (index,
				    JV_CONSTANT_Fieldref,
				    &name, &field_type);
  if (class_type)
    *class_type = ct;
  typec = vfy_string_bytes (field_type);
  len = vfy_string_length (field_type);
  if (typec[0] == '[' || typec[0] == 'L')
    init_type_from_string (&t, field_type);
  else
    init_type_from_tag (&t, get_type_val_for_signature (typec[0]));

  /* We have an obscure special case here: we can use `putfield' on a
     field declared in this class, even if `this' has not yet been
     initialized.  */
  if (putfield
      && ! type_initialized (&vfr->current_state->this_type)
      && vfr->current_state->this_type.pc == SELF
      && types_equal (&vfr->current_state->this_type, &ct)
      && vfy_class_has_field (vfr->current_class, name, field_type))
    /* Note that we don't actually know whether we're going to match
       against 'this' or some other object of the same type.  So,
       here we set things up so that it doesn't matter.  This relies
       on knowing what our caller is up to.  */
    type_set_uninitialized (class_type, EITHER);

  return t;
}

static type
check_method_constant (int index, bool is_interface,
			    vfy_string *method_name,
			    vfy_string *method_signature)
{
  return handle_field_or_method (index,
				 (is_interface
				  ? JV_CONSTANT_InterfaceMethodref
				  : JV_CONSTANT_Methodref),
				 method_name, method_signature);
}

static const char *
get_one_type (const char *p, type *t)
{
  const char *start = p;
  vfy_jclass k;
  type_val rt;
  char v;

  int arraycount = 0;
  while (*p == '[')
    {
      ++arraycount;
      ++p;
    }

  v = *p++;

  if (v == 'L')
    {
      vfy_string name;
      while (*p != ';')
	++p;
      ++p;
      name = vfy_get_string (start, p - start);
      *t = make_type_from_string (name);
      return p;
    }

  /* Casting to jchar here is ok since we are looking at an ASCII
     character.  */
  rt = get_type_val_for_signature (v);

  if (arraycount == 0)
    {
      /* Callers of this function eventually push their arguments on
         the stack.  So, promote them here.  */
      type new_t = make_type (rt);
      vfy_promote_type (&new_t);
      *t = new_t;
      return p;
    }

  k = construct_primitive_array_type (rt);
  while (--arraycount > 0)
    k = vfy_get_array_class (k);
  *t = make_type_from_class (k);
  return p;
}

static void 
compute_argument_types (vfy_string signature, type *types)
{
  int i;
  const char *p = vfy_string_bytes (signature);

  /* Skip `('.  */
  ++p;

  i = 0;
  while (*p != ')')
    p = get_one_type (p, &types[i++]);
}

static type
compute_return_type (vfy_string signature)
{
  const char *p = vfy_string_bytes (signature);
  type t;
  while (*p != ')')
    ++p;
  ++p;
  get_one_type (p, &t);
  return t;
}

static void
check_return_type (type onstack)
{
  type rt = compute_return_type (vfy_get_signature (vfr->current_method));
  if (! types_compatible (&rt, &onstack))
    verify_fail ("incompatible return type");
}

/* Initialize the stack for the new method.  Returns true if this
   method is an instance initializer.  */
static bool
initialize_stack (void)
{
  int arg_count, i;
  int var = 0;
  bool is_init = vfy_strings_equal (vfy_get_method_name (vfr->current_method),
				    vfy_init_name());
  bool is_clinit = vfy_strings_equal (vfy_get_method_name (vfr->current_method),
				      vfy_clinit_name());

  if (! vfy_is_static (vfr->current_method))
    {
      type kurr = make_type_from_class (vfr->current_class);
      if (is_init)
	{
	  type_set_uninitialized (&kurr, SELF);
	  is_init = true;
	}
      else if (is_clinit)
	verify_fail ("<clinit> method must be static");
      set_variable (0, kurr);
      state_set_this_type (vfr->current_state, &kurr);
      ++var;
    }
  else
    {
      if (is_init)
	verify_fail ("<init> method must be non-static");
    }

  /* We have to handle wide arguments specially here.  */
  arg_count = vfy_count_arguments (vfy_get_signature (vfr->current_method));
  {
    type *arg_types = (type *) vfy_alloc (arg_count * sizeof (type));
    compute_argument_types (vfy_get_signature (vfr->current_method), arg_types);
    for (i = 0; i < arg_count; ++i)
      {
	set_variable (var, arg_types[i]);
	++var;
	if (type_iswide (&arg_types[i]))
	  ++var;
      }
    vfy_free (arg_types);
  }

  return is_init;
}

static void
verify_instructions_0 (void)
{
  int i;
  bool this_is_init;

  vfr->current_state = make_state (vfr->current_method->max_stack,
				   vfr->current_method->max_locals);

  vfr->PC = 0;
  vfr->start_PC = 0;

  /*  True if we are verifying an instance initializer.  */
  this_is_init = initialize_stack ();

  vfr->states = (state_list **) vfy_alloc (sizeof (state_list *)
				      * vfr->current_method->code_length);

  for (i = 0; i < vfr->current_method->code_length; ++i)
    vfr->states[i] = NULL;

  vfr->next_verify_state = NULL;

  while (true)
    {
      java_opcode opcode;

      /* If the PC was invalidated, get a new one from the work list.  */
      if (vfr->PC == NO_NEXT)
	{
	  state *new_state = pop_jump ();
	  /* If it is null, we're done.  */
	  if (new_state == NULL)
	    break;

	  vfr->PC = new_state->pc;
	  debug_print ("== State pop from pending list\n");
	  /* Set up the current state.  */
	  copy_state (vfr->current_state, new_state, 
	    vfr->current_method->max_stack, vfr->current_method->max_locals);
	}
      else
	{
	  /* We only have to do this checking in the situation where
	     control flow falls through from the previous instruction.
	     Otherwise merging is done at the time we push the branch.
	     Note that we'll catch the off-the-end problem just
	     below.  */
	  if (vfr->PC < vfr->current_method->code_length
	      && vfr->states[vfr->PC] != NULL)
	    {
	      /* We've already visited this instruction.  So merge
	         the states together.  It is simplest, but not most
	         efficient, to just always invalidate the PC here.  */
	      merge_into (vfr->PC, vfr->current_state);
	      invalidate_pc ();
	      continue;
	    }
	}

      /* Control can't fall off the end of the bytecode.  We need to
         check this in both cases, not just the fall-through case,
         because we don't check to see whether a `jsr' appears at
         the end of the bytecode until we process a `ret'.  */
      if (vfr->PC >= vfr->current_method->code_length)
	verify_fail ("fell off end");
      vfr->flags[vfr->PC] |= FLAG_INSN_SEEN;

      /* We only have to keep saved state at branch targets.  If
         we're at a branch target and the state here hasn't been set
         yet, we set it now.  You might notice that `ret' targets
         won't necessarily have FLAG_BRANCH_TARGET set.  This
         doesn't matter, since those states will be filled in by
         merge_into.  */
      /* Note that other parts of the compiler assume that there is a
	 label with a type map at PC=0.  */
      if (vfr->states[vfr->PC] == NULL
	  && (vfr->PC == 0 || (vfr->flags[vfr->PC] & FLAG_BRANCH_TARGET) != 0))
	add_new_state (vfr->PC, vfr->current_state);

      /* Set this before handling exceptions so that debug output is
         sane.  */
      vfr->start_PC = vfr->PC;

      /* Update states for all active exception handlers.  Ordinarily
         there are not many exception handlers.  So we simply run
         through them all.  */
      for (i = 0; i < vfr->current_method->exc_count; ++i)
	{
	  int hpc, start, end, htype;
	  vfy_get_exception (vfr->exception, i, &hpc, &start, &end, &htype);
	  if (vfr->PC >= start && vfr->PC < end)
	    {
	      type handler = make_type_from_class (vfy_throwable_type ());
	      if (htype != 0)
		handler = check_class_constant (htype);
	      push_exception_jump (handler, hpc);
	    }
	}


      debug_print_state (vfr->current_state, "   ", vfr->PC, 
			 vfr->current_method->max_stack,
			 vfr->current_method->max_locals);
      opcode = (java_opcode) vfr->bytecode[vfr->PC++];
      switch (opcode)
	{
	case op_nop:
	  break;

	case op_aconst_null:
	  push_type (null_type);
	  break;

	case op_iconst_m1:
	case op_iconst_0:
	case op_iconst_1:
	case op_iconst_2:
	case op_iconst_3:
	case op_iconst_4:
	case op_iconst_5:
	  push_type (int_type);
	  break;

	case op_lconst_0:
	case op_lconst_1:
	  push_type (long_type);
	  break;

	case op_fconst_0:
	case op_fconst_1:
	case op_fconst_2:
	  push_type (float_type);
	  break;

	case op_dconst_0:
	case op_dconst_1:
	  push_type (double_type);
	  break;

	case op_bipush:
	  get_byte ();
	  push_type (int_type);
	  break;

	case op_sipush:
	  get_short ();
	  push_type (int_type);
	  break;

	case op_ldc:
	  push_type_t (check_constant (get_byte ()));
	  break;
	case op_ldc_w:
	  push_type_t (check_constant (get_ushort ()));
	  break;
	case op_ldc2_w:
	  push_type_t (check_wide_constant (get_ushort ()));
	  break;

	case op_iload:
	  push_type_t (get_variable (get_byte (), int_type));
	  break;
	case op_lload:
	  push_type_t (get_variable (get_byte (), long_type));
	  break;
	case op_fload:
	  push_type_t (get_variable (get_byte (), float_type));
	  break;
	case op_dload:
	  push_type_t (get_variable (get_byte (), double_type));
	  break;
	case op_aload:
	  push_type_t (get_variable (get_byte (), reference_type));
	  break;

	case op_iload_0:
	case op_iload_1:
	case op_iload_2:
	case op_iload_3:
	  push_type_t (get_variable (opcode - op_iload_0, int_type));
	  break;
	case op_lload_0:
	case op_lload_1:
	case op_lload_2:
	case op_lload_3:
	  push_type_t (get_variable (opcode - op_lload_0, long_type));
	  break;
	case op_fload_0:
	case op_fload_1:
	case op_fload_2:
	case op_fload_3:
	  push_type_t (get_variable (opcode - op_fload_0, float_type));
	  break;
	case op_dload_0:
	case op_dload_1:
	case op_dload_2:
	case op_dload_3:
	  push_type_t (get_variable (opcode - op_dload_0, double_type));
	  break;
	case op_aload_0:
	case op_aload_1:
	case op_aload_2:
	case op_aload_3:
	  push_type_t (get_variable (opcode - op_aload_0, reference_type));
	  break;
	case op_iaload:
	  pop_type (int_type);
	  push_type_t (require_array_type (pop_init_ref (reference_type),
					 int_type));
	  break;
	case op_laload:
	  pop_type (int_type);
	  push_type_t (require_array_type (pop_init_ref (reference_type),
					 long_type));
	  break;
	case op_faload:
	  pop_type (int_type);
	  push_type_t (require_array_type (pop_init_ref (reference_type),
					 float_type));
	  break;
	case op_daload:
	  pop_type (int_type);
	  push_type_t (require_array_type (pop_init_ref (reference_type),
					 double_type));
	  break;
	case op_aaload:
	  pop_type (int_type);
	  push_type_t (require_array_type (pop_init_ref (reference_type),
					 reference_type));
	  break;
	case op_baload:
	  pop_type (int_type);
	  require_array_type (pop_init_ref (reference_type), byte_type);
	  push_type (int_type);
	  break;
	case op_caload:
	  pop_type (int_type);
	  require_array_type (pop_init_ref (reference_type), char_type);
	  push_type (int_type);
	  break;
	case op_saload:
	  pop_type (int_type);
	  require_array_type (pop_init_ref (reference_type), short_type);
	  push_type (int_type);
	  break;
	case op_istore:
	  set_variable (get_byte (), pop_type (int_type));
	  break;
	case op_lstore:
	  set_variable (get_byte (), pop_type (long_type));
	  break;
	case op_fstore:
	  set_variable (get_byte (), pop_type (float_type));
	  break;
	case op_dstore:
	  set_variable (get_byte (), pop_type (double_type));
	  break;
	case op_astore:
	  set_variable (get_byte (), pop_ref_or_return ());
	  break;
	case op_istore_0:
	case op_istore_1:
	case op_istore_2:
	case op_istore_3:
	  set_variable (opcode - op_istore_0, pop_type (int_type));
	  break;
	case op_lstore_0:
	case op_lstore_1:
	case op_lstore_2:
	case op_lstore_3:
	  set_variable (opcode - op_lstore_0, pop_type (long_type));
	  break;
	case op_fstore_0:
	case op_fstore_1:
	case op_fstore_2:
	case op_fstore_3:
	  set_variable (opcode - op_fstore_0, pop_type (float_type));
	  break;
	case op_dstore_0:
	case op_dstore_1:
	case op_dstore_2:
	case op_dstore_3:
	  set_variable (opcode - op_dstore_0, pop_type (double_type));
	  break;
	case op_astore_0:
	case op_astore_1:
	case op_astore_2:
	case op_astore_3:
	  set_variable (opcode - op_astore_0, pop_ref_or_return ());
	  break;
	case op_iastore:
	  pop_type (int_type);
	  pop_type (int_type);
	  require_array_type (pop_init_ref (reference_type), int_type);
	  break;
	case op_lastore:
	  pop_type (long_type);
	  pop_type (int_type);
	  require_array_type (pop_init_ref (reference_type), long_type);
	  break;
	case op_fastore:
	  pop_type (float_type);
	  pop_type (int_type);
	  require_array_type (pop_init_ref (reference_type), float_type);
	  break;
	case op_dastore:
	  pop_type (double_type);
	  pop_type (int_type);
	  require_array_type (pop_init_ref (reference_type), double_type);
	  break;
	case op_aastore:
	  pop_type (reference_type);
	  pop_type (int_type);
	  require_array_type (pop_init_ref (reference_type), reference_type);
	  break;
	case op_bastore:
	  pop_type (int_type);
	  pop_type (int_type);
	  require_array_type (pop_init_ref (reference_type), byte_type);
	  break;
	case op_castore:
	  pop_type (int_type);
	  pop_type (int_type);
	  require_array_type (pop_init_ref (reference_type), char_type);
	  break;
	case op_sastore:
	  pop_type (int_type);
	  pop_type (int_type);
	  require_array_type (pop_init_ref (reference_type), short_type);
	  break;
	case op_pop:
	  pop32 ();
	  break;
	case op_pop2:
	  {
	    type t = pop_raw ();
	    if (! type_iswide (&t))
	      pop32 ();
	  }
	  break;
	case op_dup:
	  {
	    type t = pop32 ();
	    push_type_t (t);
	    push_type_t (t);
	  }
	  break;
	case op_dup_x1:
	  {
	    type t1 = pop32 ();
	    type t2 = pop32 ();
	    push_type_t (t1);
	    push_type_t (t2);
	    push_type_t (t1);
	  }
	  break;
	case op_dup_x2:
	  {
	    type t1 = pop32 ();
	    type t2 = pop_raw ();
	    if (! type_iswide (&t2))
	      {
		type t3 = pop32 ();
		push_type_t (t1);
		push_type_t (t3);
	      }
	    else
	      push_type_t (t1);
	    push_type_t (t2);
	    push_type_t (t1);
	  }
	  break;
	case op_dup2:
	  {
	    type t = pop_raw ();
	    if (! type_iswide (&t))
	      {
		type t2 = pop32 ();
		push_type_t (t2);
		push_type_t (t);
		push_type_t (t2);
	      }
	    else
	      push_type_t (t);
	    push_type_t (t);
	  }
	  break;
	case op_dup2_x1:
	  {
	    type t1 = pop_raw ();
	    type t2 = pop32 ();
	    if (! type_iswide (&t1))
	      {
		type t3 = pop32 ();
		push_type_t (t2);
		push_type_t (t1);
		push_type_t (t3);
	      }
	    else
	      push_type_t (t1);
	    push_type_t (t2);
	    push_type_t (t1);
	  }
	  break;
	case op_dup2_x2:
	  {
	    type t1 = pop_raw ();
	    if (type_iswide (&t1))
	      {
		type t2 = pop_raw ();
		if (type_iswide (&t2))
		  {
		    push_type_t (t1);
		    push_type_t (t2);
		  }
		else
		  {
		    type t3 = pop32 ();
		    push_type_t (t1);
		    push_type_t (t3);
		    push_type_t (t2);
		  }
		push_type_t (t1);
	      }
	    else
	      {
		type t2 = pop32 ();
		type t3 = pop_raw ();
		if (type_iswide (&t3))
		  {
		    push_type_t (t2);
		    push_type_t (t1);
		  }
		else
		  {
		    type t4 = pop32 ();
		    push_type_t (t2);
		    push_type_t (t1);
		    push_type_t (t4);
		  }
		push_type_t (t3);
		push_type_t (t2);
		push_type_t (t1);
	      }
	  }
	  break;
	case op_swap:
	  {
	    type t1 = pop32 ();
	    type t2 = pop32 ();
	    push_type_t (t1);
	    push_type_t (t2);
	  }
	  break;
	case op_iadd:
	case op_isub:
	case op_imul:
	case op_idiv:
	case op_irem:
	case op_ishl:
	case op_ishr:
	case op_iushr:
	case op_iand:
	case op_ior:
	case op_ixor:
	  pop_type (int_type);
	  push_type_t (pop_type (int_type));
	  break;
	case op_ladd:
	case op_lsub:
	case op_lmul:
	case op_ldiv:
	case op_lrem:
	case op_land:
	case op_lor:
	case op_lxor:
	  pop_type (long_type);
	  push_type_t (pop_type (long_type));
	  break;
	case op_lshl:
	case op_lshr:
	case op_lushr:
	  pop_type (int_type);
	  push_type_t (pop_type (long_type));
	  break;
	case op_fadd:
	case op_fsub:
	case op_fmul:
	case op_fdiv:
	case op_frem:
	  pop_type (float_type);
	  push_type_t (pop_type (float_type));
	  break;
	case op_dadd:
	case op_dsub:
	case op_dmul:
	case op_ddiv:
	case op_drem:
	  pop_type (double_type);
	  push_type_t (pop_type (double_type));
	  break;
	case op_ineg:
	case op_i2b:
	case op_i2c:
	case op_i2s:
	  push_type_t (pop_type (int_type));
	  break;
	case op_lneg:
	  push_type_t (pop_type (long_type));
	  break;
	case op_fneg:
	  push_type_t (pop_type (float_type));
	  break;
	case op_dneg:
	  push_type_t (pop_type (double_type));
	  break;
	case op_iinc:
	  get_variable (get_byte (), int_type);
	  get_byte ();
	  break;
	case op_i2l:
	  pop_type (int_type);
	  push_type (long_type);
	  break;
	case op_i2f:
	  pop_type (int_type);
	  push_type (float_type);
	  break;
	case op_i2d:
	  pop_type (int_type);
	  push_type (double_type);
	  break;
	case op_l2i:
	  pop_type (long_type);
	  push_type (int_type);
	  break;
	case op_l2f:
	  pop_type (long_type);
	  push_type (float_type);
	  break;
	case op_l2d:
	  pop_type (long_type);
	  push_type (double_type);
	  break;
	case op_f2i:
	  pop_type (float_type);
	  push_type (int_type);
	  break;
	case op_f2l:
	  pop_type (float_type);
	  push_type (long_type);
	  break;
	case op_f2d:
	  pop_type (float_type);
	  push_type (double_type);
	  break;
	case op_d2i:
	  pop_type (double_type);
	  push_type (int_type);
	  break;
	case op_d2l:
	  pop_type (double_type);
	  push_type (long_type);
	  break;
	case op_d2f:
	  pop_type (double_type);
	  push_type (float_type);
	  break;
	case op_lcmp:
	  pop_type (long_type);
	  pop_type (long_type);
	  push_type (int_type);
	  break;
	case op_fcmpl:
	case op_fcmpg:
	  pop_type (float_type);
	  pop_type (float_type);
	  push_type (int_type);
	  break;
	case op_dcmpl:
	case op_dcmpg:
	  pop_type (double_type);
	  pop_type (double_type);
	  push_type (int_type);
	  break;
	case op_ifeq:
	case op_ifne:
	case op_iflt:
	case op_ifge:
	case op_ifgt:
	case op_ifle:
	  pop_type (int_type);
	  push_jump (get_short ());
	  break;
	case op_if_icmpeq:
	case op_if_icmpne:
	case op_if_icmplt:
	case op_if_icmpge:
	case op_if_icmpgt:
	case op_if_icmple:
	  pop_type (int_type);
	  pop_type (int_type);
	  push_jump (get_short ());
	  break;
	case op_if_acmpeq:
	case op_if_acmpne:
	  pop_type (reference_type);
	  pop_type (reference_type);
	  push_jump (get_short ());
	  break;
	case op_goto:
	  push_jump (get_short ());
	  invalidate_pc ();
	  break;
	case op_jsr:
	  handle_jsr_insn (get_short ());
	  break;
	case op_ret:
	  handle_ret_insn (get_byte ());
	  break;
	case op_tableswitch:
	  {
	    int i;
	    jint low, high;
	    pop_type (int_type);
	    skip_padding ();
	    push_jump (get_int ());
	    low = get_int ();
	    high = get_int ();
	    /* Already checked LOW -vs- HIGH.  */
	    for (i = low; i <= high; ++i)
	      push_jump (get_int ());
	    invalidate_pc ();
	  }
	  break;

	case op_lookupswitch:
	  {
	    int i;
	    jint npairs, lastkey;

	    pop_type (int_type);
	    skip_padding ();
	    push_jump (get_int ());
	    npairs = get_int ();
	    /* Already checked NPAIRS >= 0.  */
	    lastkey = 0;
	    for (i = 0; i < npairs; ++i)
	      {
		jint key = get_int ();
		if (i > 0 && key <= lastkey)
		  verify_fail_pc ("lookupswitch pairs unsorted", vfr->start_PC);
		lastkey = key;
		push_jump (get_int ());
	      }
	    invalidate_pc ();
	  }
	  break;
	case op_ireturn:
	  check_return_type (pop_type (int_type));
	  invalidate_pc ();
	  break;
	case op_lreturn:
	  check_return_type (pop_type (long_type));
	  invalidate_pc ();
	  break;
	case op_freturn:
	  check_return_type (pop_type (float_type));
	  invalidate_pc ();
	  break;
	case op_dreturn:
	  check_return_type (pop_type (double_type));
	  invalidate_pc ();
	  break;
	case op_areturn:
	  check_return_type (pop_init_ref (reference_type));
	  invalidate_pc ();
	  break;
	case op_return:
	  /* We only need to check this when the return type is void,
	     because all instance initializers return void.  We also
	     need to special-case Object constructors, as they can't
	     call a superclass <init>.  */
	  if (this_is_init && vfr->current_class != vfy_object_type ())
	    state_check_this_initialized (vfr->current_state);
	  check_return_type (make_type (void_type));
	  invalidate_pc ();
	  break;
	case op_getstatic:
	  push_type_t (check_field_constant (get_ushort (), NULL, false));
	  break;
	case op_putstatic:
	  pop_type_t (check_field_constant (get_ushort (), NULL, false));
	  break;
	case op_getfield:
	  {
	    type klass;
	    type field = check_field_constant (get_ushort (), &klass, false);
	    pop_type_t (klass);
	    push_type_t (field);
	  }
	  break;
	case op_putfield:
	  {
	    type klass;
	    type field = check_field_constant (get_ushort (), &klass, true);
	    pop_type_t (field);
	    pop_type_t (klass);
	  }
	  break;

	case op_invokevirtual:
	case op_invokespecial:
	case op_invokestatic:
	case op_invokeinterface:
	  {
	    vfy_string method_name, method_signature;
	    const char *namec;
	    int i, arg_count;
	    type rt;
	    bool is_init = false;

	    type class_type
	      = check_method_constant (get_ushort (),
				       opcode == op_invokeinterface,
				       &method_name,
				       &method_signature);
	    /* NARGS is only used when we're processing
	       invokeinterface.  It is simplest for us to compute it
	       here and then verify it later.  */
	    int nargs = 0;
	    if (opcode == op_invokeinterface)
	      {
		nargs = get_byte ();
		if (get_byte () != 0)
		  verify_fail ("invokeinterface dummy byte is wrong");
	      }

	    namec = vfy_string_bytes (method_name);

	    if (vfy_strings_equal (method_name, vfy_init_name()))
	      {
		is_init = true;
		if (opcode != op_invokespecial)
		  verify_fail ("can't invoke <init>");
	      }
	    else if (namec[0] == '<')
	      verify_fail ("can't invoke method starting with `<'");

	    arg_count = vfy_count_arguments (method_signature);
            {
	      /* Pop arguments and check types.  */
	      type *arg_types = (type *) vfy_alloc (arg_count * sizeof (type));

	      compute_argument_types (method_signature, arg_types);
	      for (i = arg_count - 1; i >= 0; --i)
		{
		  /* This is only used for verifying the byte for
		     invokeinterface.  */
		  nargs -= type_depth (&arg_types[i]);
		  pop_init_ref_t (arg_types[i]);
		}

	      vfy_free (arg_types);
	    }

	    if (opcode == op_invokeinterface
		&& nargs != 1)
	      verify_fail ("wrong argument count for invokeinterface");

	    if (opcode != op_invokestatic)
	      {
	        type raw;
		type t = class_type;
		if (is_init)
		  {
		    /* In this case the PC doesn't matter.  */
		    type_set_uninitialized (&t, UNINIT);
		    /* FIXME: check to make sure that the <init>
		       call is to the right class.
		       It must either be super or an exact class
		       match.  */
		  }
		raw = pop_raw ();
		if (! types_compatible (&t, &raw))
		  verify_fail ("incompatible type on stack");

		if (is_init)		  
		  state_set_initialized (vfr->current_state, 
		    type_get_pc (&raw), vfr->current_method->max_locals);
	      }

	    rt = compute_return_type (method_signature);
	    if (! type_isvoid (&rt))
	      push_type_t (rt);
	  }
	  break;

	case op_new:
	  {
	    type t = check_class_constant (get_ushort ());
	    if (type_isarray (&t) || type_isinterface (&t)
		|| type_isabstract (&t))
	      verify_fail ("type is array, interface, or abstract");
	    type_set_uninitialized (&t, vfr->start_PC);
	    push_type_t (t);
	  }
	  break;

	case op_newarray:
	  {
	    int atype = get_byte ();
	    vfy_jclass k;
	    type t;
	    /* We intentionally have chosen constants to make this
	       valid.  */
	    if (atype < boolean_type || atype > long_type)
	      verify_fail_pc ("type not primitive", vfr->start_PC);
	    pop_type (int_type);
	    k = construct_primitive_array_type ((type_val) atype);
	    init_type_from_class (&t, k);
	    push_type_t (t);
	  }
	  break;
	case op_anewarray:
	  {
	    type t;
	    pop_type (int_type);
	    t = check_class_constant (get_ushort ());
	    push_type_t (type_to_array (&t));
	  }
	  break;
	case op_arraylength:
	  {
	    type t = pop_init_ref (reference_type);
	    if (! type_isarray (&t) && ! type_isnull (&t))
	      verify_fail ("array type expected");
	    push_type (int_type);
	  }
	  break;
	case op_athrow:
	  pop_type_t (make_type_from_class (vfy_throwable_type ()));
	  invalidate_pc ();
	  break;
	case op_checkcast:
	  pop_init_ref (reference_type);
	  push_type_t (check_class_constant (get_ushort ()));
	  break;
	case op_instanceof:
	  pop_init_ref (reference_type);
	  check_class_constant (get_ushort ());
	  push_type (int_type);
	  break;
	case op_monitorenter:
	  pop_init_ref (reference_type);
	  break;
	case op_monitorexit:
	  pop_init_ref (reference_type);
	  break;
	case op_wide:
	  {
	    switch (get_byte ())
	      {
	      case op_iload:
		push_type_t (get_variable (get_ushort (), int_type));
		break;
	      case op_lload:
		push_type_t (get_variable (get_ushort (), long_type));
		break;
	      case op_fload:
		push_type_t (get_variable (get_ushort (), float_type));
		break;
	      case op_dload:
		push_type_t (get_variable (get_ushort (), double_type));
		break;
	      case op_aload:
		push_type_t (get_variable (get_ushort (), reference_type));
		break;
	      case op_istore:
		set_variable (get_ushort (), pop_type (int_type));
		break;
	      case op_lstore:
		set_variable (get_ushort (), pop_type (long_type));
		break;
	      case op_fstore:
		set_variable (get_ushort (), pop_type (float_type));
		break;
	      case op_dstore:
		set_variable (get_ushort (), pop_type (double_type));
		break;
	      case op_astore:
		set_variable (get_ushort (), pop_init_ref (reference_type));
		break;
	      case op_ret:
		handle_ret_insn (get_short ());
		break;
	      case op_iinc:
		get_variable (get_ushort (), int_type);
		get_short ();
		break;
	      default:
		verify_fail_pc ("unrecognized wide instruction", vfr->start_PC);
	      }
	  }
	  break;
	case op_multianewarray:
	  {
	    int i;
	    type atype = check_class_constant (get_ushort ());
	    int dim = get_byte ();
	    if (dim < 1)
	      verify_fail_pc ("too few dimensions to multianewarray", vfr->start_PC);
            type_verify_dimensions (&atype, dim);
	    for (i = 0; i < dim; ++i)
	      pop_type (int_type);
	    push_type_t (atype);
	  }
	  break;
	case op_ifnull:
	case op_ifnonnull:
	  pop_type (reference_type);
	  push_jump (get_short ());
	  break;
	case op_goto_w:
	  push_jump (get_int ());
	  invalidate_pc ();
	  break;
	case op_jsr_w:
	  handle_jsr_insn (get_int ());
	  break;

	default:
	  /* Unrecognized opcode.  */
	  verify_fail_pc ("unrecognized instruction in verify_instructions_0",
		       vfr->start_PC);
	}
    }
}

/* This turns a `type' into something suitable for use by the type map
   in the other parts of the compiler.  In particular, reference types
   are mapped to Object, primitive types are unchanged, and other
   types are mapped using special functions declared in verify.h.  */
static vfy_jclass
collapse_type (type *t)
{
  switch (t->key)
    {
    case void_type:
    case boolean_type:
    case char_type:
    case float_type:
    case double_type:
    case byte_type:
    case short_type:
    case int_type:
    case long_type:
      return vfy_get_primitive_type (t->key);

    case unsuitable_type:
    case continuation_type:
      return vfy_unsuitable_type ();

    case return_address_type:
      return vfy_return_address_type ();

    case null_type:
      return vfy_null_type ();

    case reference_type:
    case uninitialized_reference_type:
      return vfy_object_type ();
    }

  gcc_unreachable ();
}

static void
verify_instructions (void)
{
  int i;

  branch_prepass ();
  verify_instructions_0 ();

  /* Now tell the rest of the compiler about the types we've found.  */
  for (i = 0; i < vfr->current_method->code_length; ++i)
    {
      int j, slot;
      struct state *curr;

      if ((vfr->flags[i] & FLAG_INSN_SEEN) != 0)
	vfy_note_instruction_seen (i);

      if (! vfr->states[i])
	continue;

      curr = vfr->states[i]->val;
      vfy_note_stack_depth (vfr->current_method, i, curr->stackdepth);

      /* Tell the compiler about each local variable.  */
      for (j = 0; j < vfr->current_method->max_locals; ++j)
	vfy_note_local_type (vfr->current_method, i, j,
			     collapse_type (&curr->locals[j]));
      /* Tell the compiler about each stack slot.  */
      for (slot = j = 0; j < curr->stacktop; ++j, ++slot)
	{
	  vfy_note_stack_type (vfr->current_method, i, slot,
			       collapse_type (&curr->stack[j]));
	  if (type_iswide (&curr->stack[j]))
	    {
	      ++slot;
	      vfy_note_stack_type (vfr->current_method, i, slot,
				   vfy_unsuitable_type ());
	    }
	}
      gcc_assert (slot == curr->stackdepth);
    }
}

static void
make_verifier_context (vfy_method *m)
{
  vfr = (verifier_context *) vfy_alloc (sizeof (struct verifier_context));

  vfr->current_method = m;
  vfr->bytecode = vfy_get_bytecode (m);
  vfr->exception = vfy_get_exceptions (m);
  vfr->current_class = m->defining_class;

  vfr->states = NULL;
  vfr->flags = NULL;
  vfr->utf8_list = NULL;
  vfr->isect_list = NULL;
}

static void
free_verifier_context (void)
{
  vfy_string_list *utf8_list;
  ref_intersection *isect_list;

  if (vfr->flags)
    vfy_free (vfr->flags);

  utf8_list = vfr->utf8_list;
  while (utf8_list != NULL)
    {
      vfy_string_list *n = utf8_list->next;
      vfy_free (utf8_list);
      utf8_list = n;
    }

  isect_list = vfr->isect_list;
  while (isect_list != NULL)
    {
      ref_intersection *next = isect_list->alloc_next;
      vfy_free (isect_list);
      isect_list = next;
    }

  if (vfr->states != NULL)
    {
      int i;
      for (i = 0; i < vfr->current_method->code_length; ++i)
	{
	  state_list *iter = vfr->states[i];
	  while (iter != NULL)
	    {
	      state_list *next = iter->next;
	      free_state (iter->val);
	      vfy_free (iter->val);
	      vfy_free (iter);
	      iter = next;
	    }
	}
      vfy_free (vfr->states);
    }
  
  vfy_free (vfr);
}

int
verify_method (vfy_method *meth)
{
  debug_print ("verify_method (%s) %i\n", vfy_string_bytes (meth->name),
	       meth->code_length);
  
  if (vfr != NULL)
    verify_fail ("verifier re-entered");

  make_verifier_context (meth);
  verify_instructions ();
  free_verifier_context ();
  vfr = NULL;

  return 1;
}