[GCC 4.8] Initial check-in of GCC 4.8.0

Change-Id: I0719d8a6d0f69b367a6ab6f10eb75622dbf12771

1 files changed, 3308 insertions, 0 deletions

diff --git a/gcc-4.8/gcc/java/verify-impl.c b/gcc-4.8/gcc/java/verify-impl.c
new file mode 100644
index 0000000..8838784
--- /dev/null
+++ b/gcc-4.8/gcc/java/verify-impl.c
@@ -0,0 +1,3308 @@
+/* Copyright (C) 2001-2013 Free Software Foundation, Inc.
+
+   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 "system.h"
+#include "coretypes.h"
+
+#include "verify.h"
+
+/* Hack to work around namespace pollution from java-tree.h.  */
+#undef current_class
+
+/* 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;
+  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);
+  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;
+}