This is the mail archive of the gcc-patches@gcc.gnu.org mailing list for the GCC project.


Index Nav: [Date Index] [Subject Index] [Author Index] [Thread Index]
Message Nav: [Date Prev] [Date Next] [Thread Prev] [Thread Next]
Other format: [Raw text]

Java: [ABI]: New verifier


This patch is an initial attempt at replacing the bytecode verifier in the Java front end. I've checked it in to the gcj-abi-2-dev-branch (aka BC-ABI branch). The verifier is set up to build, but is not yet enabled. This is preliminary code - additional patches to follow. (I'm aware that the copyright notices need to be updated, etc).

This verifier is based on the verifier currently in libgcj, which was written by Tom Tromey, but converted to C. It would be nicer to keep the verifier in C++, but adding C++ code to the front end would require major build changes that are unlikely to be acceptable in the GCC 4.0 timeframe. Also, the requirements of the two verifiers are a little different in some cases - for example, the runtime verifier recursively loads referenced classes to check things like type compatibility, while for the compiler's verifier, we want to assume that types are correct at compile time and instead emit a type assertion that is evaluated at runtime. Doing this with a shared, generic verifier would be possible, but would require quite a bit of code to be moved to the "glue" layer between the verifier and its host environment.

Bryce


2004-10-05  Bryce McKinlay  <mckinlay@redhat.com>

        * verify-impl.c, verify-glue.c, verify.h: New files.
        * Make-lang.in: Add rules for verify-impl.o and verify-glue.o.

Index: verify-impl.c
===================================================================
RCS file: verify-impl.c
diff -N verify-impl.c
--- /dev/null	1 Jan 1970 00:00:00 -0000
+++ verify-impl.c	6 Oct 2004 23:14:18 -0000
@@ -0,0 +1,3336 @@
+/* Copyright (C) 2001, 2002, 2003, 2004  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"
+
+#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)
+
+#ifdef VERIFY_DEBUG
+static void
+debug_print (const char *fmt, ...)
+{
+  va_list ap;
+  va_start (ap, fmt);
+  vfprintf (stderr, fmt, ap);
+  va_end (ap);
+}
+#else
+static void
+debug_print (const char *fmt ATTRIBUTE_UNUSED, ...)
+{
+}    
+#endif /* VERIFY_DEBUG */
+
+#if 0
+static void debug_print (const char *fmt, ...)
+  __attribute__ ((format (printf, 1, 2)));
+
+static void
+debug_print (const char *fmt, ...)
+{
+#ifdef VERIFY_DEBUG
+  va_list ap;
+  va_start (ap, fmt);
+  vfprintf (stderr, fmt, ap);
+  va_end (ap);
+#endif /* VERIFY_DEBUG */
+}
+#endif
+
+/* 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,
+   but we still implement what is specified.  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.
+   Similarly, there's no real point in enforcing that padding bytes or
+   the mystery byte of invokeinterface must be 0, but we do that too.
+
+   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
+
+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.
+  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 is_assignable_from_slow (vfy_jclass target, vfy_jclass source);
+bool type_initialized (type *t);
+int ref_count_dimensions (ref_intersection *ref);
+
+#if 0
+  // Create a new Utf-8 constant and return it.  We do this to avoid
+  // having our Utf-8 constants prematurely collected.
+  static vfy_string
+  make_utf8_const (const char *s, int len)
+  {
+    vfy_string val = vfy_make_string (s, len);
+    vfy_string_list *lu = vfy_alloc (sizeof (vfy_string_list));
+    lu->val = val;
+    lu->next = vfr->utf8_list;
+    vfr->utf8_list = lu;
+
+    return val;
+  }
+#endif
+
+  static void
+  verify_fail_pc (const char *s, int pc)
+  {
+    if (pc == -1)
+      pc = vfr->start_PC;
+    vfy_fail (s, pc, vfr->current_class, vfr->current_method);  
+  }
+  
+  static void
+  verify_fail (const char *s)
+  {
+    verify_fail_pc (s, -1);
+  }
+
+  // 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, ref2))
+	    {
+	      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 OTHER can be assigned to an object of
+   type *THIS.  This might resolve classes in one chain or the other.  */
+static bool 
+ref_compatible (ref_intersection *ref1, ref_intersection *ref2)
+{
+  for (; ref1 != NULL; ref1 = ref1->ref_next)
+    {
+      ref_intersection *ref2_iter = ref2;
+
+      for (; ref2_iter != NULL; ref2_iter = ref2_iter->ref_next)
+	{
+	  // Avoid resolving if possible.
+	  if (! ref1->is_resolved
+	      && ! ref2_iter->is_resolved
+	      && vfy_strings_equal (ref1->data.name,
+				    ref2_iter->data.name))
+	    continue;
+
+	  if (! ref1->is_resolved)
+	    resolve_ref (ref1);
+	  if (! ref2_iter->is_resolved)
+	    resolve_ref (ref2_iter);
+
+	  if (! is_assignable_from_slow (ref1->data.klass,
+					 ref2_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));
+}
+
+// This is like _Jv_IsAssignableFrom, but it works even if SOURCE or
+// TARGET haven't been prepared.
+bool
+is_assignable_from_slow (vfy_jclass target, vfy_jclass source)
+{
+  // First, strip arrays.
+  while (vfy_is_array (target))
+    {
+      // If target is array, source must be as well.
+      if (! vfy_is_array (source))
+	return false;
+      target = vfy_get_component_type (target);
+      source = vfy_get_component_type (source);
+    }
+
+  // Quick success.
+  if (target == vfy_object_type ())
+    return true;
+
+  do
+    {
+      int i;
+      if (source == target)
+	return true;
+
+      if (vfy_is_primitive (target) || vfy_is_primitive (source))
+	return false;
+
+      if (vfy_is_interface (target))
+	{
+	  for (i = 0; i < vfy_get_interface_count (source); ++i)
+	    {
+	      // We use a recursive call because we also need to
+	      // check superinterfaces.
+	      if (is_assignable_from_slow (target,
+					   vfy_get_interface (source, i)))
+		return true;
+	    }
+	}
+      source = vfy_get_superclass (source);
+    }
+  while (source != NULL);
+
+  return false;
+}
+
+// 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, and the
+  // special value SELF for the case where the current method is
+  // itself the <init> method.
+  //
+  // 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
+};
+
+#if 0
+// Basic constructor.
+static void
+init_type (type *t)
+{
+  t->key = unsuitable_type;
+  t->klass = NULL;
+  t->pc = UNINIT;
+}
+#endif
+
+// 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->data.klass = k;
+  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->data.name = n;
+  t->pc = UNINIT;
+}
+
+static type
+make_type_from_string (vfy_string n)
+{
+  type t;
+  init_type_from_string (&t, n);
+  return t;
+}
+
+#if 0
+    // Make a new instance given the name of a class.
+    type (vfy_string n)
+    {
+      key = reference_type;
+      klass = new ref_intersection (n, verifier);
+      pc = UNINIT;
+    }
+
+    // Copy constructor.
+    static type copy_type (type *t)
+    {
+      type copy;
+      copy.key = t->key;
+      copy.klass = t->klass;
+      copy.pc = t->pc;
+      return copy;
+    }
+#endif
+
+/* 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");
+
+  // An initialized type and an uninitialized type are not
+  // compatible.
+  if (type_initialized (t) != type_initialized (k))
+    return false;
+
+  // 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);
+}
+
+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;
+
+  if (t->key != reference_type)
+    verify_fail ("programmer error in type::element_type()");
+
+  vfy_jclass 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;
+}
+
+#if 0
+static bool
+type_isresolved (type *t)
+{
+  return (t->key == reference_type
+	  || t->key == null_type
+	  || t->key == uninitialized_reference_type);
+}
+#endif
+
+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
+	{
+	  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");
+	    }
+
+	  ref_intersection *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
+void 
+print (void)
+{
+  char c = '?';
+  switch (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
+
+#if 0
+static void
+init_state (state *s)
+{
+  s->stack = NULL;
+  s->locals = NULL;
+  s->next = INVALID_STATE;  
+}
+#endif
+
+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);
+  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 = 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 = vfy_alloc (sizeof (state));
+  init_state_with_stack (s, max_stack, max_locals);
+  return s;
+}
+
+#if 0
+static void
+free_state (state *s)
+{
+  if (s->stack != NULL)
+    vfy_free (s->stack);
+  if (s->locals != NULL)
+    vfy_free (s->locals);
+}
+#endif
+
+#if 0
+    void *operator new[] (size_t bytes)
+    {
+      return vfy_alloc (bytes);
+    }
+
+    void operator delete[] (void *mem)
+    {
+      vfy_free (mem);
+    }
+
+    void *operator new (size_t bytes)
+    {
+      return vfy_alloc (bytes);
+    }
+
+    void operator delete (void *mem)
+    {
+      vfy_free (mem);
+    }
+#endif
+
+// 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);
+}
+
+static int
+state_get_pc (state *s)
+{
+  return s->pc;
+}
+
+#if 0
+static void
+set_pc (state *s, int npc)
+{
+  s->pc = npc;
+}
+#endif
+
+// 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");
+}
+
+// Throw an exception if there is an uninitialized object on the
+// stack or in a local variable.  EXCEPTION_SEMANTICS controls
+// whether we're using backwards-branch or exception-handing
+// semantics.
+static void 
+state_check_no_uninitialized_objects (state *s, int max_locals,
+				      bool exception_semantics)
+{
+  int i;
+  if (! exception_semantics)
+    {
+      for (i = 0; i < s->stacktop; ++i)
+	if (type_isreference (&s->stack[i]) 
+	    && ! type_initialized (&s->stack[i]))
+	  verify_fail ("uninitialized object on stack");
+    }
+
+  for (i = 0; i < max_locals; ++i)
+    if (type_isreference (&s->locals[i])
+	&& ! type_initialized (&s->locals[i]))
+      verify_fail ("uninitialized object in local variable");
+
+  state_check_this_initialized (s);
+}
+
+// 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)
+{
+  debug_print ("%s [%4d]:   [stack] ", leader, pc);
+  int i;
+  for (i = 0; i < s->stacktop; ++i)
+    s->stack[i].print ();
+  for (; i < max_stack; ++i)
+    debug_print (".");
+  debug_print ("    [local] ");
+  for (i = 0; i < max_locals; ++i)
+    s->locals[i].print ();
+  debug_print (" | %p\n", this);
+}
+#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)
+{
+  state *s = vfr->current_state;
+  if (s->stacktop <= 0)
+    verify_fail ("stack empty");
+  type 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)
+{
+  vfy_promote_type (&match);
+  type 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)
+{
+  state *s = vfr->current_state;
+  // If T is a numeric type like short, promote it to int.
+  promote_type (&t);
+
+  int 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);
+  return 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)
+{
+  state *s = vfr->current_state;
+  // If T is a numeric type like short, promote it to int.
+  promote_type (&t);
+
+  int 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)
+{
+  jint b1 = 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 ();
+  return (b1 << 24) | (b2 << 16) | (b3 << 8) | b4;
+}
+
+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)
+{
+  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);
+
+  state_list *nlink = 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))
+	{
+	  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);
+	  bool 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);
+  if (npc < vfr->PC)
+    state_check_no_uninitialized_objects (vfr->current_state, 
+				    vfr->current_method->max_locals, false);
+  merge_into (npc, vfr->current_state);
+}
+
+static void
+push_exception_jump (type t, int pc)
+{
+  state s;
+  state_check_no_uninitialized_objects (vfr->current_state,
+                          vfr->current_method->max_locals, true);
+  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");
+
+  if (npc < vfr->PC)
+    state_check_no_uninitialized_objects (vfr->current_state, 
+      vfr->current_method->max_locals, false);
+  merge_into (npc, vfr->current_state);
+  invalidate_pc ();
+}
+
+static void handle_jsr_insn (int offset)
+{
+  int npc = compute_jump (offset);
+
+  if (npc < vfr->PC)
+    state_check_no_uninitialized_objects (vfr->current_state,
+					  vfr->current_method->max_locals,
+					  false);
+
+  // Modify our state as appropriate for entry into a subroutine.
+  type 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)
+    {
+      // 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;
+
+      java_opcode 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:
+	  {
+	    skip_padding ();
+	    note_branch_target (compute_jump (get_int ()));
+	    jint low = get_int ();
+	    jint 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:
+	  {
+	    skip_padding ();
+	    note_branch_target (compute_jump (get_int ()));
+	    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;
+  check_pool_index (index);
+  vfy_constants *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;
+  check_pool_index (index);
+  vfy_constants *pool = vfy_get_constants (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
+    verify_fail_pc ("String, int, or float constant expected", vfr->start_PC);
+  return t;
+}
+
+static type
+check_wide_constant (int index)
+{
+  type t;
+  check_pool_index (index);
+  vfy_constants *pool = vfy_get_constants (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)
+{
+  check_pool_index (index);
+  vfy_constants *pool = vfy_get_constants (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_uint_16 class_index, name_and_type_index;
+  vfy_load_indexes (pool, index, &class_index, &name_and_type_index);
+  vfy_uint_16 name_index, desc_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.
+static type
+check_field_constant (int index, type *class_type)
+{
+  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[len - 1] == 'L')
+    init_type_from_string (&t, field_type);
+  else
+    init_type_from_tag (&t, get_type_val_for_signature (typec[0]));
+  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 type
+get_one_type (const char *p)
+{
+  const char *start = p;
+
+  int arraycount = 0;
+  while (*p == '[')
+    {
+      ++arraycount;
+      ++p;
+    }
+
+  char v = *p++;
+
+  if (v == 'L')
+    {
+      while (*p != ';')
+	++p;
+      ++p;
+      vfy_string name = vfy_get_string (start, p - start);
+      return make_type_from_string (name);
+    }
+
+  // Casting to jchar here is ok since we are looking at an ASCII
+  // character.
+  type_val 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 t = make_type (rt);
+      vfy_promote_type (&t);
+      return t;
+    }
+
+  vfy_jclass k = construct_primitive_array_type (rt);
+  while (--arraycount > 0)
+    k = vfy_get_array_class (k);
+  return make_type_from_class (k);
+}
+
+static void 
+compute_argument_types (vfy_string signature, type *types)
+{
+  char *p = (char *) vfy_string_bytes (signature);
+
+  // Skip `('.
+  ++p;
+
+  int i = 0;
+  while (*p != ')')
+    types[i++] = get_one_type (p);
+}
+
+static type
+compute_return_type (vfy_string signature)
+{
+  char *p = (char *) vfy_string_bytes (signature);
+  while (*p != ')')
+    ++p;
+  ++p;
+  return get_one_type (p);
+}
+
+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[arg_count];
+  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;
+    }
+
+  return is_init;
+}
+
+static void
+verify_instructions_0 (void)
+{
+  int i;
+
+  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.
+  bool 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)
+    {
+      // 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 = state_get_pc (new_state);
+	  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.
+	  if (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");
+
+      // 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.
+      if (vfr->states[vfr->PC] == NULL && (vfr->flags[vfr->PC] & FLAG_BRANCH_TARGET))
+	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);
+      java_opcode 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;
+	    pop_type (int_type);
+	    skip_padding ();
+	    push_jump (get_int ());
+	    jint low = get_int ();
+	    jint 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;
+	    pop_type (int_type);
+	    skip_padding ();
+	    push_jump (get_int ());
+	    jint npairs = get_int ();
+	    // Already checked NPAIRS >= 0.
+	    jint 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.
+	  if (this_is_init)
+	    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));
+	  break;
+	case op_putstatic:
+	  pop_type_t (check_field_constant (get_ushort (), NULL));
+	  break;
+	case op_getfield:
+	  {
+	    type klass;
+	    type field = check_field_constant (get_ushort (), &klass);
+	    pop_type_t (klass);
+	    push_type_t (field);
+	  }
+	  break;
+	case op_putfield:
+	  {
+	    type klass;
+	    type field = check_field_constant (get_ushort (), &klass);
+	    pop_type_t (field);
+
+	    // 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 (! type_initialized (&vfr->current_state->this_type)
+		&& vfr->current_state->this_type.pc == SELF)
+	      type_set_uninitialized (&klass, SELF);
+	    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;
+
+	    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");
+	      }
+
+	    bool is_init = false;
+	    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 `<'");
+
+	    // Pop arguments and check types.
+	    int arg_count = vfy_count_arguments (method_signature);
+	    type arg_types[arg_count];
+	    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]);
+	      }
+
+	    if (opcode == op_invokeinterface
+		&& nargs != 1)
+	      verify_fail ("wrong argument count for invokeinterface");
+
+	    if (opcode != op_invokestatic)
+	      {
+		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.
+		  }
+		type 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);
+	      }
+
+	    type 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 ();
+	    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);
+	    init_type_from_class (&t, construct_primitive_array_type (atype));
+	    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;
+
+#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
+	default:
+	  // Unrecognized opcode.
+	  verify_fail_pc ("unrecognized instruction in verify_instructions_0",
+		       vfr->start_PC);
+	}
+    }
+}
+
+static void verify_instructions (void)
+{
+  branch_prepass ();
+  verify_instructions_0 ();
+}
+
+#if 0
+_Jv_BytecodeVerifier (_Jv_InterpMethod *m)
+{
+  // We just print the text as utf-8.  This is just for debugging
+  // anyway.
+  debug_print ("--------------------------------\n");
+  debug_print ("-- Verifying method `%s'\n", m->self->name->chars());
+
+  vfr->current_method = m;
+  bytecode = m->bytecode ();
+  exception = m->exceptions ();
+  vfr->current_class = m->defining_class;
+
+  vfr->states = NULL;
+  vfr->flags = NULL;
+  vfr->utf8_list = NULL;
+  vfr->isect_list = NULL;
+}
+
+~_Jv_BytecodeVerifier ()
+{
+  if (flags)
+    _Jv_Free (flags);
+
+  while (utf8_list != NULL)
+    {
+      linked<_Jv_Utf8Const> *n = utf8_list->next;
+      _Jv_Free (utf8_list);
+      utf8_list = n;
+    }
+
+  while (isect_list != NULL)
+    {
+      ref_intersection *next = isect_list->alloc_next;
+      delete isect_list;
+      isect_list = next;
+    }
+
+  if (vfr->states)
+    {
+      for (int i = 0; i < vfr->current_method->code_length; ++i)
+	{
+	  linked<state *> *iter = vfr->states[i];
+	  while (iter != NULL)
+	    {
+	      linked<state *> *next = iter->next;
+	      delete iter->val;
+	      vfy_free (iter);
+	      iter = next;
+	    }
+	}
+      vfy_free (states);
+    }
+}
+
+#endif
+
+int
+verify_method (vfy_method *meth ATTRIBUTE_UNUSED)
+{
+  /* static verifier initialization .. init type_int etc */
+
+  /* push_verifier_context () */
+  /* _Jv_BytecodeVerifier v (meth); */
+  /* init_verifier_context () */
+  verify_instructions ();
+  /* pop_verifier_context () */
+  return 0;
+}
Index: verify-glue.c
===================================================================
RCS file: verify-glue.c
diff -N verify-glue.c
--- /dev/null	1 Jan 1970 00:00:00 -0000
+++ verify-glue.c	6 Oct 2004 23:14:18 -0000
@@ -0,0 +1,434 @@
+/* Glue to interface gcj with bytecode verifier.
+   Copyright (C) 2003 Free Software Foundation, Inc.
+
+This file is part of GCC.
+
+GCC is free software; you can redistribute it and/or modify
+it under the terms of the GNU General Public License as published by
+the Free Software Foundation; either version 2, or (at your option)
+any later version.
+
+GCC is distributed in the hope that it will be useful,
+but WITHOUT ANY WARRANTY; without even the implied warranty of
+MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
+GNU General Public License for more details.
+
+You should have received a copy of the GNU General Public License
+along with GCC; see the file COPYING.  If not, write to
+the Free Software Foundation, 59 Temple Place - Suite 330,
+Boston, MA 02111-1307, USA.
+
+Java and all Java-based marks are trademarks or registered trademarks
+of Sun Microsystems, Inc. in the United States and other countries.
+The Free Software Foundation is independent of Sun Microsystems, Inc.  */
+
+/* Written by Tom Tromey <tromey@redhat.com>.  */
+
+#include "config.h"
+
+#include "system.h"
+#include "coretypes.h"
+#include "tm.h"
+#include "tree.h"
+#include "errors.h"
+#include "parse.h"
+
+#include "verify.h"
+#include "java-tree.h"
+
+void *
+vfy_alloc (size_t bytes)
+{
+  return xmalloc (bytes);
+}
+
+void
+vfy_free (void *mem)
+{
+  free (mem);
+}
+
+bool
+vfy_strings_equal (vfy_string one, vfy_string two)
+{
+  return one == two;
+}
+
+const char *
+vfy_string_bytes (vfy_string str)
+{
+  return IDENTIFIER_POINTER (str);
+}
+
+int
+vfy_string_length (vfy_string str)
+{
+  return IDENTIFIER_LENGTH (str);
+}
+
+vfy_string
+vfy_init_name ()
+{
+  return init_identifier_node;
+}
+
+vfy_string
+vfy_clinit_name ()
+{
+  return clinit_identifier_node;
+}
+
+static const char*
+skip_one_type (const char* ptr)
+{
+  int ch = *ptr++;
+
+  while (ch == '[')
+    { 
+      ch = *ptr++;
+    }
+  
+  if (ch == 'L')
+    {
+      do { ch = *ptr++; } while (ch != ';');
+    }
+
+  return ptr;
+}
+
+int
+vfy_count_arguments (vfy_string signature)
+{
+  const char *ptr = IDENTIFIER_POINTER (signature);
+  int arg_count = 0;
+
+  /* Skip '('.  */
+  ptr++;
+
+  /* Count args.  */
+  while (*ptr != ')')
+    {
+      ptr = skip_one_type (ptr);
+      arg_count += 1;
+    }
+
+  return arg_count;
+}
+
+vfy_string
+vfy_get_string (const char *s, int len)
+{
+  return get_identifier_with_length (s, len);
+}
+
+vfy_string
+vfy_get_signature (vfy_method *method)
+{
+  return method->signature;
+}
+
+vfy_string
+vfy_get_method_name (vfy_method *method)
+{
+  return method->name;
+}
+
+bool
+vfy_is_static (vfy_method *method)
+{
+  return METHOD_STATIC (method->method);
+}
+
+const unsigned char *
+vfy_get_bytecode (vfy_method *method)
+{
+  return method->bytes;
+}
+
+vfy_exception *
+vfy_get_exceptions (vfy_method *method)
+{
+  return method->exceptions;
+}
+
+void
+vfy_get_exception (vfy_exception *exceptions, int index, int *handler,
+		   int *start, int *end, int *handler_type)
+{
+  *handler = exceptions[index].handler;
+  *start = exceptions[index].start;
+  *end = exceptions[index].end;
+  *handler_type = exceptions[index].type;
+}
+
+int
+vfy_tag (vfy_constants *pool, int index)
+{
+  return JPOOL_TAG (pool, index);
+}
+
+void
+vfy_load_indexes (vfy_constants *pool, int index,
+		  vfy_uint_16 *index0, vfy_uint_16 *index1)
+{
+  *index0 = JPOOL_USHORT1 (pool, index);
+  *index1 = JPOOL_USHORT2 (pool, index);
+}
+
+vfy_constants *
+vfy_get_constants (vfy_jclass klass)
+{
+  return TYPE_JCF (klass);
+}
+
+int
+vfy_get_constants_size (vfy_jclass klass)
+{
+  return JPOOL_SIZE (TYPE_JCF (klass));
+}
+
+vfy_string
+vfy_get_pool_string (vfy_constants *pool, int index)
+{
+  return get_name_constant (pool, index);
+}
+
+vfy_jclass
+vfy_get_pool_class (vfy_constants *pool, int index)
+{
+  vfy_jclass k;
+  k = get_class_constant (pool, index);
+  return k;
+}
+
+vfy_string
+vfy_make_string (const char *s, int len)
+{
+  tree result;
+  char *s2 = (char *) s;
+  char save = s2[len];
+  s2[len] = '\0';
+  result = get_identifier (s2);
+  s2[len] = save;
+  return result;  
+}
+
+vfy_string
+vfy_get_class_name (vfy_jclass klass)
+{
+  return TYPE_NAME (klass);
+}
+
+char
+vfy_get_primitive_char (vfy_jclass klass)
+{
+  tree sig;
+  if (! vfy_is_primitive (klass))
+    abort ();
+  sig = build_java_signature (klass);
+  return (IDENTIFIER_POINTER (sig))[0];
+}
+
+int
+vfy_get_interface_count (vfy_jclass klass ATTRIBUTE_UNUSED)
+{
+  /* FIXME: Need to merge from mainline to get this. */
+  #if 0
+  return BINFO_N_BASE_BINFOS (klass);
+  #endif
+  return -1;
+}
+
+vfy_jclass
+vfy_get_interface (vfy_jclass klass ATTRIBUTE_UNUSED, int index ATTRIBUTE_UNUSED)
+{
+  /* FIXME: Need to merge from mainline to get this. */
+  #if 0
+  vfy_jclass k;
+  k = BINFO_BASE_BINFO (klass, index);
+  return k;
+  #endif
+  return NULL;
+}
+
+bool
+vfy_is_array (vfy_jclass klass)
+{
+  return TYPE_ARRAY_P (klass);
+}
+
+bool
+vfy_is_interface (vfy_jclass klass)
+{
+  return CLASS_INTERFACE (TYPE_NAME (klass));
+}
+
+bool
+vfy_is_primitive (vfy_jclass klass)
+{
+  printf ("debug: vfy_is_primitive()\n");
+  return JPRIMITIVE_TYPE_P (klass);
+}
+
+vfy_jclass
+vfy_get_superclass (vfy_jclass klass)
+{
+  vfy_jclass k;
+  k = CLASSTYPE_SUPER (klass);
+  return k;
+}
+
+vfy_jclass
+vfy_get_array_class (vfy_jclass klass)
+{
+  vfy_jclass k;
+  k = build_java_array_type (klass, -1);
+  return k;
+}
+
+vfy_jclass
+vfy_get_component_type (vfy_jclass klass)
+{
+  vfy_jclass k;
+  if (! vfy_is_array (klass))
+    abort ();
+  k = TYPE_ARRAY_ELEMENT (klass);
+  return k;
+}
+
+bool
+vfy_is_abstract (vfy_jclass klass)
+{
+  return CLASS_ABSTRACT (TYPE_NAME (klass));
+}
+
+vfy_jclass
+vfy_find_class (vfy_jclass ignore ATTRIBUTE_UNUSED, vfy_string name)
+{
+  vfy_jclass k;
+  k = lookup_class (name);
+  return k;
+}
+
+vfy_jclass
+vfy_object_type ()
+{
+  vfy_jclass k;
+  k = object_type_node;
+  return k;
+}
+
+vfy_jclass
+vfy_string_type ()
+{
+  vfy_jclass k;
+  k = string_type_node;
+  return k;
+}
+
+vfy_jclass
+vfy_throwable_type ()
+{
+  vfy_jclass k;
+  k = throwable_type_node;
+  return k;
+}
+
+int
+vfy_fail (const char *message, int pc, vfy_jclass ignore1 ATTRIBUTE_UNUSED,
+	  vfy_method *ignore2 ATTRIBUTE_UNUSED)
+{
+  if (pc == -1)
+    error ("verification failed: %s", message);
+  else
+    error ("verification failed at PC=%d: %s", pc, message);
+  /* We have to return a value for the verifier to throw.  */
+  return 1;
+}
+
+void
+vfy_notify_verified (int pc)
+{
+  instruction_bits[pc] |= BCODE_VERIFIED;
+}
+
+vfy_jclass
+vfy_get_primitive_type (int type)
+{
+  vfy_jclass k;
+  k = decode_newarray_type (type);
+  return k;
+}
+
+void
+vfy_note_stack_depth (int pc, int depth)
+{
+  tree label = lookup_label (pc);
+  LABEL_TYPE_STATE (label) = make_tree_vec (depth);
+}
+
+void
+vfy_note_type (int pc, int slot, vfy_jclass type)
+{
+  tree label = lookup_label (pc);
+  tree vec = LABEL_TYPE_STATE (label);
+  TREE_VEC_ELT (vec, slot) = type;
+}
+
+
+/* Verify the bytecodes of the current method.
+   Return 1 on success, 0 on failure. */
+int
+verify_jvm_instructions_new (JCF *jcf, const unsigned char *byte_ops,
+			 long length)
+{
+  vfy_method method;
+  int i, result, eh_count;
+  vfy_exception *exceptions;
+
+  /*method_init_exceptions ();*/
+  JCF_SEEK (jcf, DECL_CODE_OFFSET (current_function_decl) + length);
+  eh_count = JCF_readu2 (jcf);
+
+  exceptions = (vfy_exception *) xmalloc (eh_count * sizeof (vfy_exception));
+  for (i = 0; i < eh_count; ++i)
+    {
+      int start_pc, end_pc, handler_pc, catch_type;
+      unsigned char *p = jcf->read_ptr + 8 * i;
+      start_pc = GET_u2 (p);
+      end_pc = GET_u2 (p+2);
+      handler_pc = GET_u2 (p+4);
+      catch_type = GET_u2 (p+6);
+
+      if (start_pc < 0 || start_pc >= length
+	  || end_pc < 0 || end_pc > length || start_pc >= end_pc
+	  || handler_pc < 0 || handler_pc >= length)
+	{
+	  error ("bad pc in exception_table");
+	  free (exceptions);
+	  return 0;
+	}
+
+      exceptions[i].handler = handler_pc;
+      exceptions[i].start = start_pc;
+      exceptions[i].end = end_pc;
+      exceptions[i].type = catch_type;
+    }
+
+  method.method = current_function_decl;
+  method.signature = build_java_signature (TREE_TYPE (current_function_decl));
+  method.name = DECL_NAME (current_function_decl);
+  method.bytes = byte_ops;
+  method.exceptions = exceptions;
+  method.defining_class = DECL_CONTEXT (current_function_decl);
+  method.max_stack = DECL_MAX_STACK (current_function_decl);
+  method.max_locals = DECL_MAX_LOCALS (current_function_decl);
+  method.code_length = length;
+  method.exc_count = eh_count;
+
+  result = verify_method (&method);
+
+  free (exceptions);
+
+  return result;
+}
Index: verify.h
===================================================================
RCS file: verify.h
diff -N verify.h
--- /dev/null	1 Jan 1970 00:00:00 -0000
+++ verify.h	6 Oct 2004 23:14:18 -0000
@@ -0,0 +1,155 @@
+/* Declarations to interface gcj with bytecode verifier.
+   Copyright (C) 2003 Free Software Foundation, Inc.
+
+This file is part of GCC.
+
+GCC is free software; you can redistribute it and/or modify
+it under the terms of the GNU General Public License as published by
+the Free Software Foundation; either version 2, or (at your option)
+any later version.
+
+GCC is distributed in the hope that it will be useful,
+but WITHOUT ANY WARRANTY; without even the implied warranty of
+MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
+GNU General Public License for more details.
+
+You should have received a copy of the GNU General Public License
+along with GCC; see the file COPYING.  If not, write to
+the Free Software Foundation, 59 Temple Place - Suite 330,
+Boston, MA 02111-1307, USA.
+
+Java and all Java-based marks are trademarks or registered trademarks
+of Sun Microsystems, Inc. in the United States and other countries.
+The Free Software Foundation is independent of Sun Microsystems, Inc.  */
+
+/* Written by Tom Tromey <tromey@redhat.com>.  */
+
+#ifndef GCC_VERIFY_H
+#define GCC_VERIFY_H
+
+#ifdef __cplusplus
+extern "C"
+{
+#endif
+
+#include "system.h"
+#include "coretypes.h"
+#include "jcf.h"
+#include "tree.h"
+#include "java-tree.h"
+
+#define VFY_IN_GCC
+#define VFY_WANT_TYPEMAP
+
+typedef JCF vfy_constants;
+
+/* For our purposes a string is the same as an identifier.  */
+typedef tree vfy_string;
+
+/* The TYPE_DECL for a class or primitive type.  */
+typedef tree vfy_jclass;
+
+/* An unsigned jshort.  */
+typedef uint16 vfy_uint_16;
+
+typedef struct
+{
+  int handler, start, end, type;
+} vfy_exception;
+
+typedef struct
+{
+  tree method;
+  vfy_string signature;
+  vfy_string name;
+  const unsigned char *bytes;
+  vfy_exception *exceptions;
+
+  /* These fields are referred to directly by the verifier.  */
+  vfy_jclass defining_class;
+  int max_stack;
+  int max_locals;
+  int code_length;
+  int exc_count;
+} vfy_method;
+
+/* Entry point to the verifier.  */
+int verify_jvm_instructions_new (JCF *jcf, const unsigned char *byte_ops,
+				 long length);
+
+void *vfy_alloc (size_t bytes);
+void vfy_free (void *mem);
+bool vfy_strings_equal (vfy_string one, vfy_string two);
+const char *vfy_string_bytes (vfy_string str);
+int vfy_string_length (vfy_string str);
+vfy_string vfy_get_string (const char *chars, int length);
+vfy_string vfy_init_name (void);
+vfy_string vfy_clinit_name (void);
+int vfy_count_arguments (vfy_string signature);
+vfy_string vfy_get_signature (vfy_method *method);
+vfy_string vfy_get_method_name (vfy_method *method);
+bool vfy_is_static (vfy_method *method);
+const unsigned char *vfy_get_bytecode (vfy_method *method);
+vfy_exception *vfy_get_exceptions (vfy_method *method);
+void vfy_get_exception (vfy_exception *, int index, int *handler,
+			int *start, int *end, int *handler_type);
+int vfy_tag (vfy_constants *pool, int index);
+void vfy_load_indexes (vfy_constants *pool, int index,
+		       vfy_uint_16 *index0, vfy_uint_16 *index1);
+vfy_constants *vfy_get_constants (vfy_jclass klass);
+int vfy_get_constants_size (vfy_jclass klass);
+vfy_string vfy_get_pool_string (vfy_constants *pool, int index);
+vfy_jclass vfy_get_pool_class (vfy_constants *pool, int index);
+vfy_string vfy_make_string (const char *s, int len);
+vfy_string vfy_get_class_name (vfy_jclass klass);
+char vfy_get_primitive_char (vfy_jclass klass);
+int vfy_get_interface_count (vfy_jclass klass);
+vfy_jclass vfy_get_interface (vfy_jclass klass, int index);
+bool vfy_is_array (vfy_jclass klass);
+bool vfy_is_interface (vfy_jclass klass);
+bool vfy_is_primitive (vfy_jclass klass);
+vfy_jclass vfy_get_superclass (vfy_jclass klass);
+vfy_jclass vfy_get_array_class (vfy_jclass klass);
+vfy_jclass vfy_get_component_type (vfy_jclass klass);
+bool vfy_is_abstract (vfy_jclass klass);
+vfy_jclass vfy_find_class (vfy_jclass klass, vfy_string name);
+vfy_jclass vfy_object_type (void);
+vfy_jclass vfy_string_type (void);
+vfy_jclass vfy_throwable_type (void);
+int vfy_fail (const char *message, int pc, vfy_jclass ignore1, vfy_method *method);
+void vfy_notify_verified (int pc);
+vfy_jclass vfy_get_primitive_type (int type);
+void vfy_note_stack_depth (int pc, int depth);
+void vfy_note_type (int pc, int slot, vfy_jclass type);
+
+#define GLOM(name, stuff) name ## stuff
+#define VFY_PRIMITIVE_CLASS(name) \
+  vfy_get_primitive_type ((int) (GLOM (name, _type)))
+
+typedef enum
+{
+#define JAVAOP(name, num, ignore1, ignore2, ignore3) \
+  GLOM (op_, name) = num,
+#include "javaop.def"
+} java_opcode;
+
+
+#define JV_CONSTANT_Class CONSTANT_Class
+#define JV_CONSTANT_ResolvedClass CONSTANT_ResolvedClass
+#define JV_CONSTANT_String CONSTANT_String
+#define JV_CONSTANT_ResolvedString CONSTANT_ResolvedString
+#define JV_CONSTANT_Integer CONSTANT_Integer
+#define JV_CONSTANT_Float CONSTANT_Float
+#define JV_CONSTANT_Long CONSTANT_Long
+#define JV_CONSTANT_Double CONSTANT_Double
+#define JV_CONSTANT_Fieldref CONSTANT_Fieldref
+#define JV_CONSTANT_InterfaceMethodref CONSTANT_InterfaceMethodref
+#define JV_CONSTANT_Methodref CONSTANT_Methodref
+
+int verify_method (vfy_method *meth);
+
+#ifdef __cplusplus
+}
+#endif
+
+#endif /* ! GCC_VERIFY_H */

===================================================================
RCS file: /cvs/gcc/gcc/gcc/java/Make-lang.in,v
retrieving revision 1.136.4.1
retrieving revision 1.136.4.2
diff -u -r1.136.4.1 -r1.136.4.2
--- gcc/gcc/java/Make-lang.in	2004/05/20 23:32:49	1.136.4.1
+++ gcc/gcc/java/Make-lang.in	2004/10/06 02:59:11	1.136.4.2
@@ -101,7 +101,8 @@
 
 # Executables built by this Makefile:
 JAVA_OBJS = java/parse.o java/class.o java/decl.o java/expr.o \
-  java/constants.o java/lang.o java/typeck.o java/except.o java/verify.o \
+  java/constants.o java/lang.o java/typeck.o java/except.o \
+  java/verify-glue.o java/verify-impl.o \
   java/zextract.o java/jcf-io.o java/win32-host.o java/jcf-parse.o java/mangle.o \
   java/mangle_name.o java/builtins.o java/resource.o \
   java/jcf-write.o java/buffer.o java/check-init.o java/jcf-depend.o \
@@ -326,9 +327,10 @@
 java/typeck.o: java/typeck.c $(CONFIG_H) $(JAVA_TREE_H) java/jcf.h \
   java/convert.h toplev.h $(SYSTEM_H) coretypes.h $(TM_H) $(GGC_H) real.h
 java/win32-host.o: java/win32-host.c $(CONFIG_H) $(SYSTEM_H) java/jcf.h
-java/verify.o: java/verify.c $(CONFIG_H) $(JAVA_TREE_H) java/jcf.h \
-  java/javaop.h java/java-opcodes.h java/java-except.h toplev.h $(SYSTEM_H) \
-  coretypes.h $(TM_H)
+java/verify-glue.o: java/verify-glue.c $(CONFIG_H) $(SYSTEM_H) $(JAVA_TREE_H) \
+  coretypes.h $(TM_H) java/verify.h
+java/verify-impl.o: java/verify-impl.c $(CONFIG_H) java/verify.h $(SYSTEM_H) \
+  coretypes.h  java/jcf.h $(JAVA_TREE_H)
 java/xref.o: java/xref.c java/xref.h $(CONFIG_H) $(JAVA_TREE_H) toplev.h \
   $(SYSTEM_H) coretypes.h $(TM_H)
 java/zextract.o: java/zextract.c $(CONFIG_H) $(SYSTEM_H) coretypes.h $(TM_H) \


Index Nav: [Date Index] [Subject Index] [Author Index] [Thread Index]
Message Nav: [Date Prev] [Date Next] [Thread Prev] [Thread Next]