gcc/java/verify-impl.c

   1 /* Copyright (C) 2001, 2002, 2003, 2004, 2005, 2006  Free Software Foundation
   2
   3    This file is part of libgcj.
   4
   5 This software is copyrighted work licensed under the terms of the
   6 Libgcj License.  Please consult the file "LIBGCJ_LICENSE" for
   7 details.  */
   8
   9 /* Written by Tom Tromey <tromey@redhat.com>  */
  10
  11 /* Uncomment this to enable debugging output.  */
  12 /* #define VERIFY_DEBUG */
  13
  14 #include "config.h"
  15
  16 #include "verify.h"
  17
  18 /* Hack to work around namespace pollution from java-tree.h.  */
  19 #undef current_class
  20
  21 #ifdef VERIFY_DEBUG
  22 #include <stdio.h>
  23 #endif /* VERIFY_DEBUG */
  24
  25 /* This is used to mark states which are not scheduled for
  26    verification. */
  27 #define INVALID_STATE ((state *) -1)
  28
  29 static void ATTRIBUTE_PRINTF_1
  30 debug_print (const char *fmt ATTRIBUTE_UNUSED, ...)
  31 {
  32 #ifdef VERIFY_DEBUG
  33   va_list ap;
  34   va_start (ap, fmt);
  35   vfprintf (stderr, fmt, ap);
  36   va_end (ap);
  37 #endif /* VERIFY_DEBUG */
  38 }
  39
  40 /* This started as a fairly ordinary verifier, and for the most part
  41    it remains so.  It works in the obvious way, by modeling the effect
  42    of each opcode as it is encountered.  For most opcodes, this is a
  43    straightforward operation.
  44
  45    This verifier does not do type merging.  It used to, but this
  46    results in difficulty verifying some relatively simple code
  47    involving interfaces, and it pushed some verification work into the
  48    interpreter.
  49
  50    Instead of merging reference types, when we reach a point where two
  51    flows of control merge, we simply keep the union of reference types
  52    from each branch.  Then, when we need to verify a fact about a
  53    reference on the stack (e.g., that it is compatible with the
  54    argument type of a method), we check to ensure that all possible
  55    types satisfy the requirement.
  56
  57    Another area this verifier differs from the norm is in its handling
  58    of subroutines.  The JVM specification has some confusing things to
  59    say about subroutines.  For instance, it makes claims about not
  60    allowing subroutines to merge and it rejects recursive subroutines.
  61    For the most part these are red herrings; we used to try to follow
  62    these things but they lead to problems.  For example, the notion of
  63    "being in a subroutine" is not well-defined: is an exception
  64    handler in a subroutine?  If you never execute the `ret' but
  65    instead `goto 1' do you remain in the subroutine?
  66
  67    For clarity on what is really required for type safety, read
  68    "Simple Verification Technique for Complex Java Bytecode
  69    Subroutines" by Alessandro Coglio.  Among other things this paper
  70    shows that recursive subroutines are not harmful to type safety.
  71    We implement something similar to what he proposes.  Note that this
  72    means that this verifier will accept code that is rejected by some
  73    other verifiers.
  74
  75    For those not wanting to read the paper, the basic observation is
  76    that we can maintain split states in subroutines.  We maintain one
  77    state for each calling `jsr'.  In other words, we re-verify a
  78    subroutine once for each caller, using the exact types held by the
  79    callers (as opposed to the old approach of merging types and
  80    keeping a bitmap registering what did or did not change).  This
  81    approach lets us continue to verify correctly even when a
  82    subroutine is exited via `goto' or `athrow' and not `ret'.
  83
  84    In some other areas the JVM specification is (mildly) incorrect,
  85    so we diverge.  For instance, you cannot
  86    violate type safety by allocating an object with `new' and then
  87    failing to initialize it, no matter how one branches or where one
  88    stores the uninitialized reference.  See "Improving the official
  89    specification of Java bytecode verification" by Alessandro Coglio.
  90
  91    Note that there's no real point in enforcing that padding bytes or
  92    the mystery byte of invokeinterface must be 0, but we do that
  93    regardless.
  94
  95    The verifier is currently neither completely lazy nor eager when it
  96    comes to loading classes.  It tries to represent types by name when
  97    possible, and then loads them when it needs to verify a fact about
  98    the type.  Checking types by name is valid because we only use
  99    names which come from the current class' constant pool.  Since all
 100    such names are looked up using the same class loader, there is no
 101    danger that we might be fooled into comparing different types with
 102    the same name.
 103
 104    In the future we plan to allow for a completely lazy mode of
 105    operation, where the verifier will construct a list of type
 106    assertions to be checked later.
 107
 108    Some test cases for the verifier live in the "verify" module of the
 109    Mauve test suite.  However, some of these are presently
 110    (2004-01-20) believed to be incorrect.  (More precisely the notion
 111    of "correct" is not well-defined, and this verifier differs from
 112    others while remaining type-safe.)  Some other tests live in the
 113    libgcj test suite.
 114
 115    This verifier is also written to be pluggable.  This means that it
 116    is intended for use in a variety of environments, not just libgcj.
 117    As a result the verifier expects a number of type and method
 118    declarations to be declared in "verify.h".  The intent is that you
 119    recompile the verifier for your particular environment.  This
 120    approach was chosen so that operations could be inlined in verify.h
 121    as much as possible.
 122
 123    See the verify.h that accompanies this copy of the verifier to see
 124    what types, preprocessor defines, and functions must be declared.
 125    The interface is ad hoc, but was defined so that it could be
 126    implemented to connect to a pure C program.
 127 */
 128
 129 #define FLAG_INSN_START 1
 130 #define FLAG_BRANCH_TARGET 2
 131 #define FLAG_INSN_SEEN 4
 132
 133 struct state;
 134 struct type;
 135 struct ref_intersection;
 136
 137 typedef struct state state;
 138 typedef struct type type;
 139 typedef struct ref_intersection ref_intersection;
 140
 141 /*typedef struct state_list state_list;*/
 142
 143 typedef struct state_list
 144 {
 145   state *val;
 146   struct state_list *next;
 147 } state_list;
 148
 149 typedef struct vfy_string_list
 150 {
 151   vfy_string val;
 152   struct vfy_string_list *next;
 153 } vfy_string_list;
 154
 155 typedef struct verifier_context
 156 {
 157   /* The current PC.  */
 158   int PC;
 159   /* The PC corresponding to the start of the current instruction.  */
 160   int start_PC;
 161
 162   /* The current state of the stack, locals, etc.  */
 163   state *current_state;
 164
 165   /* At each branch target we keep a linked list of all the states we
 166      can process at that point.  We'll only have multiple states at a
 167      given PC if they both have different return-address types in the
 168      same stack or local slot.  This array is indexed by PC and holds
 169      the list of all such states.  */
 170   state_list **states;
 171
 172   /* We keep a linked list of all the states which we must reverify.
 173      This is the head of the list.  */
 174   state *next_verify_state;
 175
 176   /* We keep some flags for each instruction.  The values are the
 177      FLAG_* constants defined above.  This is an array indexed by PC.  */
 178   char *flags;
 179
 180   /* The bytecode itself.  */
 181   const unsigned char *bytecode;
 182   /* The exceptions.  */
 183   vfy_exception *exception;
 184
 185   /* Defining class.  */
 186   vfy_jclass current_class;
 187   /* This method.  */
 188   vfy_method *current_method;
 189
 190   /* A linked list of utf8 objects we allocate.  */
 191   vfy_string_list *utf8_list;
 192
 193   /* A linked list of all ref_intersection objects we allocate.  */
 194   ref_intersection *isect_list;
 195 } verifier_context;
 196
 197 /* The current verifier's state data. This is maintained by
 198    {push/pop}_verifier_context to provide a shorthand form to access
 199    the verification state. */
 200 static GTY(()) verifier_context *vfr;
 201
 202 /* Local function declarations.  */
 203 bool type_initialized (type *t);
 204 int ref_count_dimensions (ref_intersection *ref);
 205
 206 static void
 207 verify_fail_pc (const char *s, int pc)
 208 {
 209   vfy_fail (s, pc, vfr->current_class, vfr->current_method);
 210 }
 211
 212 static void
 213 verify_fail (const char *s)
 214 {
 215   verify_fail_pc (s, vfr->PC);
 216 }
 217
 218 /* This enum holds a list of tags for all the different types we
 219    need to handle.  Reference types are treated specially by the
 220    type class.  */
 221 typedef enum type_val
 222 {
 223   void_type,
 224
 225   /* The values for primitive types are chosen to correspond to values
 226      specified to newarray. */
 227   boolean_type = 4,
 228   char_type = 5,
 229   float_type = 6,
 230   double_type = 7,
 231   byte_type = 8,
 232   short_type = 9,
 233   int_type = 10,
 234   long_type = 11,
 235
 236   /* Used when overwriting second word of a double or long in the
 237      local variables.  Also used after merging local variable states
 238      to indicate an unusable value.  */
 239   unsuitable_type,
 240   return_address_type,
 241   /* This is the second word of a two-word value, i.e., a double or
 242      a long.  */
 243   continuation_type,
 244
 245   /* Everything after `reference_type' must be a reference type.  */
 246   reference_type,
 247   null_type,
 248   uninitialized_reference_type
 249 } type_val;
 250
 251 /* This represents a merged class type.  Some verifiers (including
 252    earlier versions of this one) will compute the intersection of
 253    two class types when merging states.  However, this loses
 254    critical information about interfaces implemented by the various
 255    classes.  So instead we keep track of all the actual classes that
 256    have been merged.  */
 257 struct ref_intersection
 258 {
 259   /* Whether or not this type has been resolved.  */
 260   bool is_resolved;
 261
 262   /* Actual type data.  */
 263   union
 264   {
 265     /* For a resolved reference type, this is a pointer to the class.  */
 266     vfy_jclass klass;
 267     /* For other reference types, this it the name of the class.  */
 268     vfy_string name;
 269   } data;
 270
 271   /* Link to the next reference in the intersection.  */
 272   ref_intersection *ref_next;
 273
 274   /* This is used to keep track of all the allocated
 275      ref_intersection objects, so we can free them.
 276      FIXME: we should allocate these in chunks.  */
 277   ref_intersection *alloc_next;
 278 };
 279
 280 static ref_intersection *
 281 make_ref (void)
 282 {
 283   ref_intersection *new_ref =
 284     (ref_intersection *) vfy_alloc (sizeof (ref_intersection));
 285
 286   new_ref->alloc_next = vfr->isect_list;
 287   vfr->isect_list = new_ref;
 288   return new_ref;
 289 }
 290
 291 static ref_intersection *
 292 clone_ref (ref_intersection *dup)
 293 {
 294   ref_intersection *new_ref = make_ref ();
 295
 296   new_ref->is_resolved = dup->is_resolved;
 297   new_ref->data = dup->data;
 298   return new_ref;
 299 }
 300
 301 static void
 302 resolve_ref (ref_intersection *ref)
 303 {
 304   if (ref->is_resolved)
 305     return;
 306   ref->data.klass = vfy_find_class (vfr->current_class, ref->data.name);
 307   ref->is_resolved = true;
 308 }
 309
 310 static bool
 311 refs_equal (ref_intersection *ref1, ref_intersection *ref2)
 312 {
 313   if (! ref1->is_resolved && ! ref2->is_resolved
 314       && vfy_strings_equal (ref1->data.name, ref2->data.name))
 315     return true;
 316   if (! ref1->is_resolved)
 317     resolve_ref (ref1);
 318   if (! ref2->is_resolved)
 319     resolve_ref (ref2);
 320   return ref1->data.klass == ref2->data.klass;
 321 }
 322
 323 /* Merge REF1 type into REF2, returning the result.  This will
 324    return REF2 if all the classes in THIS already appear in
 325    REF2.  */
 326 static ref_intersection *
 327 merge_refs (ref_intersection *ref1, ref_intersection *ref2)
 328 {
 329   ref_intersection *tail = ref2;
 330   for (; ref1 != NULL; ref1 = ref1->ref_next)
 331     {
 332       bool add = true;
 333       ref_intersection *iter;
 334       for (iter = ref2; iter != NULL; iter = iter->ref_next)
 335         {
 336           if (refs_equal (ref1, iter))
 337             {
 338               add = false;
 339               break;
 340             }
 341         }
 342
 343       if (add)
 344         {
 345           ref_intersection *new_tail = clone_ref (ref1);
 346           new_tail->ref_next = tail;
 347           tail = new_tail;
 348         }
 349     }
 350   return tail;
 351 }
 352
 353 /* See if an object of type SOURCE can be assigned to an object of
 354    type TARGET.  This might resolve classes in one chain or the other.  */
 355 static bool
 356 ref_compatible (ref_intersection *target, ref_intersection *source)
 357 {
 358   for (; target != NULL; target = target->ref_next)
 359     {
 360       ref_intersection *source_iter = source;
 361
 362       for (; source_iter != NULL; source_iter = source_iter->ref_next)
 363         {
 364           /* Avoid resolving if possible.  */
 365           if (! target->is_resolved
 366               && ! source_iter->is_resolved
 367               && vfy_strings_equal (target->data.name,
 368                                     source_iter->data.name))
 369             continue;
 370
 371           if (! target->is_resolved)
 372             resolve_ref (target);
 373           if (! source_iter->is_resolved)
 374             resolve_ref (source_iter);
 375
 376           if (! vfy_is_assignable_from (target->data.klass,
 377                                         source_iter->data.klass))
 378             return false;
 379         }
 380     }
 381
 382   return true;
 383 }
 384
 385 static bool
 386 ref_isarray (ref_intersection *ref)
 387 {
 388   /* assert (ref_next == NULL);  */
 389   if (ref->is_resolved)
 390     return vfy_is_array (ref->data.klass);
 391   else
 392     return vfy_string_bytes (ref->data.name)[0] == '[';
 393 }
 394
 395 static bool
 396 ref_isinterface (ref_intersection *ref)
 397 {
 398   /* assert (ref_next == NULL);  */
 399   if (! ref->is_resolved)
 400     resolve_ref (ref);
 401   return vfy_is_interface (ref->data.klass);
 402 }
 403
 404 static bool
 405 ref_isabstract (ref_intersection *ref)
 406 {
 407   /* assert (ref_next == NULL); */
 408   if (! ref->is_resolved)
 409     resolve_ref (ref);
 410   return vfy_is_abstract (ref->data.klass);
 411 }
 412
 413 static vfy_jclass
 414 ref_getclass (ref_intersection *ref)
 415 {
 416   if (! ref->is_resolved)
 417     resolve_ref (ref);
 418   return ref->data.klass;
 419 }
 420
 421 int
 422 ref_count_dimensions (ref_intersection *ref)
 423 {
 424   int ndims = 0;
 425   if (ref->is_resolved)
 426     {
 427       vfy_jclass k = ref->data.klass;
 428       while (vfy_is_array (k))
 429         {
 430           k = vfy_get_component_type (k);
 431           ++ndims;
 432         }
 433     }
 434   else
 435     {
 436       const char *p = vfy_string_bytes (ref->data.name);
 437       while (*p++ == '[')
 438         ++ndims;
 439     }
 440   return ndims;
 441 }
 442
 443 /* Return the type_val corresponding to a primitive signature
 444    character.  For instance `I' returns `int.class'.  */
 445 static type_val
 446 get_type_val_for_signature (char sig)
 447 {
 448   type_val rt;
 449   switch (sig)
 450     {
 451     case 'Z':
 452       rt = boolean_type;
 453       break;
 454     case 'B':
 455       rt = byte_type;
 456       break;
 457     case 'C':
 458       rt = char_type;
 459       break;
 460     case 'S':
 461       rt = short_type;
 462       break;
 463     case 'I':
 464       rt = int_type;
 465       break;
 466     case 'J':
 467       rt = long_type;
 468       break;
 469     case 'F':
 470       rt = float_type;
 471       break;
 472     case 'D':
 473       rt = double_type;
 474       break;
 475     case 'V':
 476       rt = void_type;
 477       break;
 478     default:
 479       verify_fail ("invalid signature");
 480       return null_type;
 481     }
 482   return rt;
 483 }
 484
 485 /* Return the type_val corresponding to a primitive class.  */
 486 static type_val
 487 get_type_val_for_primtype (vfy_jclass k)
 488 {
 489   return get_type_val_for_signature (vfy_get_primitive_char (k));
 490 }
 491
 492 /* The `type' class is used to represent a single type in the verifier.  */
 493 struct type
 494 {
 495   /* The type key.  */
 496   type_val key;
 497
 498   /* For reference types, the representation of the type.  */
 499   ref_intersection *klass;
 500
 501   /* This is used in two situations.
 502
 503      First, when constructing a new object, it is the PC of the
 504      `new' instruction which created the object.  We use the special
 505      value UNINIT to mean that this is uninitialized.  The special
 506      value SELF is used for the case where the current method is
 507      itself the <init> method.  the special value EITHER is used
 508      when we may optionally allow either an uninitialized or
 509      initialized reference to match.
 510
 511      Second, when the key is return_address_type, this holds the PC
 512      of the instruction following the `jsr'.  */
 513   int pc;
 514
 515 #define UNINIT -2
 516 #define SELF -1
 517 #define EITHER -3
 518 };
 519
 520 /* Make a new instance given the type tag.  We assume a generic
 521    `reference_type' means Object.  */
 522 static void
 523 init_type_from_tag (type *t, type_val k)
 524 {
 525   t->key = k;
 526   /* For reference_type, if KLASS==NULL then that means we are
 527      looking for a generic object of any kind, including an
 528      uninitialized reference.  */
 529   t->klass = NULL;
 530   t->pc = UNINIT;
 531 }
 532
 533 /* Make a type for the given type_val tag K.  */
 534 static type
 535 make_type (type_val k)
 536 {
 537   type t;
 538   init_type_from_tag (&t, k);
 539   return t;
 540 }
 541
 542 /* Make a new instance given a class.  */
 543 static void
 544 init_type_from_class (type *t, vfy_jclass k)
 545 {
 546   t->key = reference_type;
 547   t->klass = make_ref ();
 548   t->klass->is_resolved = true;
 549   t->klass->data.klass = k;
 550   t->klass->ref_next = NULL;
 551   t->pc = UNINIT;
 552 }
 553
 554 static type
 555 make_type_from_class (vfy_jclass k)
 556 {
 557   type t;
 558   init_type_from_class (&t, k);
 559   return t;
 560 }
 561
 562 static void
 563 init_type_from_string (type *t, vfy_string n)
 564 {
 565   t->key = reference_type;
 566   t->klass = make_ref ();
 567   t->klass->is_resolved = false;
 568   t->klass->data.name = n;
 569   t->klass->ref_next = NULL;
 570   t->pc = UNINIT;
 571 }
 572
 573 static type
 574 make_type_from_string (vfy_string n)
 575 {
 576   type t;
 577   init_type_from_string (&t, n);
 578   return t;
 579 }
 580
 581 /* Promote a numeric type.  */
 582 static void
 583 vfy_promote_type (type *t)
 584 {
 585   if (t->key == boolean_type || t->key == char_type
 586       || t->key == byte_type || t->key == short_type)
 587     t->key = int_type;
 588 }
 589 #define promote_type vfy_promote_type
 590
 591 /* Mark this type as the uninitialized result of `new'.  */
 592 static void
 593 type_set_uninitialized (type *t, int npc)
 594 {
 595   if (t->key == reference_type)
 596     t->key = uninitialized_reference_type;
 597   else
 598     verify_fail ("internal error in type::uninitialized");
 599   t->pc = npc;
 600 }
 601
 602 /* Mark this type as now initialized.  */
 603 static void
 604 type_set_initialized (type *t, int npc)
 605 {
 606   if (npc != UNINIT && t->pc == npc && t->key == uninitialized_reference_type)
 607     {
 608       t->key = reference_type;
 609       t->pc = UNINIT;
 610     }
 611 }
 612
 613 /* Mark this type as a particular return address.  */
 614 static void type_set_return_address (type *t, int npc)
 615 {
 616   t->pc = npc;
 617 }
 618
 619 /* Return true if this type and type OTHER are considered
 620    mergeable for the purposes of state merging.  This is related
 621    to subroutine handling.  For this purpose two types are
 622    considered unmergeable if they are both return-addresses but
 623    have different PCs.  */
 624 static bool
 625 type_state_mergeable_p (type *t1, type *t2)
 626 {
 627   return (t1->key != return_address_type
 628           || t2->key != return_address_type
 629           || t1->pc == t2->pc);
 630 }
 631
 632 /* Return true if an object of type K can be assigned to a variable
 633    of type T.  Handle various special cases too.  Might modify
 634    T or K.  Note however that this does not perform numeric
 635    promotion.  */
 636 static bool
 637 types_compatible (type *t, type *k)
 638 {
 639   /* Any type is compatible with the unsuitable type.  */
 640   if (k->key == unsuitable_type)
 641     return true;
 642
 643   if (t->key < reference_type || k->key < reference_type)
 644     return t->key == k->key;
 645
 646   /* The `null' type is convertible to any initialized reference
 647      type.  */
 648   if (t->key == null_type)
 649     return k->key != uninitialized_reference_type;
 650   if (k->key == null_type)
 651     return t->key != uninitialized_reference_type;
 652
 653   /* A special case for a generic reference.  */
 654   if (t->klass == NULL)
 655     return true;
 656   if (k->klass == NULL)
 657     verify_fail ("programmer error in type::compatible");
 658
 659   /* Handle the special 'EITHER' case, which is only used in a
 660      special case of 'putfield'.  Note that we only need to handle
 661      this on the LHS of a check.  */
 662   if (! type_initialized (t) && t->pc == EITHER)
 663     {
 664       /* If the RHS is uninitialized, it must be an uninitialized
 665          'this'.  */
 666       if (! type_initialized (k) && k->pc != SELF)
 667         return false;
 668     }
 669   else if (type_initialized (t) != type_initialized (k))
 670     {
 671       /* An initialized type and an uninitialized type are not
 672          otherwise compatible.  */
 673       return false;
 674     }
 675   else
 676     {
 677       /* Two uninitialized objects are compatible if either:
 678        * The PCs are identical, or
 679        * One PC is UNINIT.  */
 680       if (type_initialized (t))
 681         {
 682           if (t->pc != k->pc && t->pc != UNINIT && k->pc != UNINIT)
 683             return false;
 684         }
 685     }
 686
 687   return ref_compatible (t->klass, k->klass);
 688 }
 689
 690 /* Return true if two types are equal.  Only valid for reference
 691    types.  */
 692 static bool
 693 types_equal (type *t1, type *t2)
 694 {
 695   if ((t1->key != reference_type && t1->key != uninitialized_reference_type)
 696       || (t2->key != reference_type
 697           && t2->key != uninitialized_reference_type))
 698     return false;
 699   /* Only single-ref types are allowed.  */
 700   if (t1->klass->ref_next || t2->klass->ref_next)
 701     return false;
 702   return refs_equal (t1->klass, t2->klass);
 703 }
 704
 705 static bool
 706 type_isvoid (type *t)
 707 {
 708   return t->key == void_type;
 709 }
 710
 711 static bool
 712 type_iswide (type *t)
 713 {
 714   return t->key == long_type || t->key == double_type;
 715 }
 716
 717 /* Return number of stack or local variable slots taken by this type.  */
 718 static int
 719 type_depth (type *t)
 720 {
 721   return type_iswide (t) ? 2 : 1;
 722 }
 723
 724 static bool
 725 type_isarray (type *t)
 726 {
 727   /* We treat null_type as not an array.  This is ok based on the
 728      current uses of this method.  */
 729   if (t->key == reference_type)
 730     return ref_isarray (t->klass);
 731   return false;
 732 }
 733
 734 static bool
 735 type_isnull (type *t)
 736 {
 737   return t->key == null_type;
 738 }
 739
 740 static bool
 741 type_isinterface (type *t)
 742 {
 743   if (t->key != reference_type)
 744     return false;
 745   return ref_isinterface (t->klass);
 746 }
 747
 748 static bool
 749 type_isabstract (type *t)
 750 {
 751   if (t->key != reference_type)
 752     return false;
 753   return ref_isabstract (t->klass);
 754 }
 755
 756 /* Return the element type of an array.  */
 757 static type
 758 type_array_element (type *t)
 759 {
 760   type et;
 761   vfy_jclass k;
 762
 763   if (t->key != reference_type)
 764     verify_fail ("programmer error in type::element_type()");
 765
 766   k = vfy_get_component_type (ref_getclass (t->klass));
 767   if (vfy_is_primitive (k))
 768     init_type_from_tag (&et, get_type_val_for_primtype (k));
 769   else
 770     init_type_from_class (&et, k);
 771   return et;
 772 }
 773
 774 /* Return the array type corresponding to an initialized
 775    reference.  We could expand this to work for other kinds of
 776    types, but currently we don't need to.  */
 777 static type
 778 type_to_array (type *t)
 779 {
 780   type at;
 781   vfy_jclass k;
 782
 783   if (t->key != reference_type)
 784     verify_fail ("internal error in type::to_array()");
 785
 786   k = ref_getclass (t->klass);
 787   init_type_from_class (&at, vfy_get_array_class (k));
 788   return at;
 789 }
 790
 791 static bool
 792 type_isreference (type *t)
 793 {
 794   return t->key >= reference_type;
 795 }
 796
 797 static int
 798 type_get_pc (type *t)
 799 {
 800   return t->pc;
 801 }
 802
 803 bool
 804 type_initialized (type *t)
 805 {
 806   return t->key == reference_type || t->key == null_type;
 807 }
 808
 809 static void
 810 type_verify_dimensions (type *t, int ndims)
 811 {
 812   /* The way this is written, we don't need to check isarray().  */
 813   if (t->key != reference_type)
 814     verify_fail ("internal error in verify_dimensions:"
 815                            " not a reference type");
 816
 817   if (ref_count_dimensions (t->klass) < ndims)
 818     verify_fail ("array type has fewer dimensions"
 819                            " than required");
 820 }
 821
 822 /* Merge OLD_TYPE into this.  On error throw exception.  Return
 823    true if the merge caused a type change.  */
 824 static bool
 825 merge_types (type *t, type *old_type, bool local_semantics)
 826 {
 827   bool changed = false;
 828   bool refo = type_isreference (old_type);
 829   bool refn = type_isreference (t);
 830   if (refo && refn)
 831     {
 832       if (old_type->key == null_type)
 833         ;
 834       else if (t->key == null_type)
 835         {
 836           *t = *old_type;
 837           changed = true;
 838         }
 839       else if (type_initialized (t) != type_initialized (old_type))
 840         verify_fail ("merging initialized and uninitialized types");
 841       else
 842         {
 843           ref_intersection *merged;
 844           if (! type_initialized (t))
 845             {
 846               if (t->pc == UNINIT)
 847                 t->pc = old_type->pc;
 848               else if (old_type->pc == UNINIT)
 849                 ;
 850               else if (t->pc != old_type->pc)
 851                 verify_fail ("merging different uninitialized types");
 852             }
 853
 854           merged = merge_refs (old_type->klass, t->klass);
 855           if (merged != t->klass)
 856             {
 857               t->klass = merged;
 858               changed = true;
 859             }
 860         }
 861     }
 862   else if (refo || refn || t->key != old_type->key)
 863     {
 864       if (local_semantics)
 865         {
 866           /* If we already have an `unsuitable' type, then we
 867              don't need to change again.  */
 868           if (t->key != unsuitable_type)
 869             {
 870               t->key = unsuitable_type;
 871               changed = true;
 872             }
 873         }
 874       else
 875         verify_fail ("unmergeable type");
 876     }
 877   return changed;
 878 }
 879
 880 #ifdef VERIFY_DEBUG
 881 static void
 882 type_print (type *t)
 883 {
 884   char c = '?';
 885   switch (t->key)
 886     {
 887     case boolean_type: c = 'Z'; break;
 888     case byte_type: c = 'B'; break;
 889     case char_type: c = 'C'; break;
 890     case short_type: c = 'S'; break;
 891     case int_type: c = 'I'; break;
 892     case long_type: c = 'J'; break;
 893     case float_type: c = 'F'; break;
 894     case double_type: c = 'D'; break;
 895     case void_type: c = 'V'; break;
 896     case unsuitable_type: c = '-'; break;
 897     case return_address_type: c = 'r'; break;
 898     case continuation_type: c = '+'; break;
 899     case reference_type: c = 'L'; break;
 900     case null_type: c = '@'; break;
 901     case uninitialized_reference_type: c = 'U'; break;
 902     }
 903   debug_print ("%c", c);
 904 }
 905 #endif /* VERIFY_DEBUG */
 906
 907 /* This class holds all the state information we need for a given
 908    location. */
 909 struct state
 910 {
 911   /* The current top of the stack, in terms of slots.  */
 912   int stacktop;
 913   /* The current depth of the stack.  This will be larger than
 914      STACKTOP when wide types are on the stack.  */
 915   int stackdepth;
 916   /* The stack.  */
 917   type *stack;
 918   /* The local variables.  */
 919   type *locals;
 920   /* We keep track of the type of `this' specially.  This is used to
 921      ensure that an instance initializer invokes another initializer
 922      on `this' before returning.  We must keep track of this
 923      specially because otherwise we might be confused by code which
 924      assigns to locals[0] (overwriting `this') and then returns
 925      without really initializing.  */
 926   type this_type;
 927
 928   /* The PC for this state.  This is only valid on states which are
 929      permanently attached to a given PC.  For an object like
 930      `current_state', which is used transiently, this has no
 931      meaning.  */
 932   int pc;
 933   /* We keep a linked list of all states requiring reverification.
 934      If this is the special value INVALID_STATE then this state is
 935      not on the list.  NULL marks the end of the linked list.  */
 936   state *next;
 937 };
 938
 939 /* NO_NEXT is the PC value meaning that a new state must be
 940    acquired from the verification list.  */
 941 #define NO_NEXT -1
 942
 943 static void
 944 init_state_with_stack (state *s, int max_stack, int max_locals)
 945 {
 946   int i;
 947   s->stacktop = 0;
 948   s->stackdepth = 0;
 949   s->stack = (type *) vfy_alloc (max_stack * sizeof (type));
 950   for (i = 0; i < max_stack; ++i)
 951     init_type_from_tag (&s->stack[i], unsuitable_type);
 952   s->locals = (type *) vfy_alloc (max_locals * sizeof (type));
 953   for (i = 0; i < max_locals; ++i)
 954     init_type_from_tag (&s->locals[i], unsuitable_type);
 955   init_type_from_tag (&s->this_type, unsuitable_type);
 956   s->pc = NO_NEXT;
 957   s->next = INVALID_STATE;
 958 }
 959
 960 static void
 961 copy_state (state *s, state *copy, int max_stack, int max_locals)
 962 {
 963   int i;
 964   s->stacktop = copy->stacktop;
 965   s->stackdepth = copy->stackdepth;
 966   for (i = 0; i < max_stack; ++i)
 967     s->stack[i] = copy->stack[i];
 968   for (i = 0; i < max_locals; ++i)
 969     s->locals[i] = copy->locals[i];
 970
 971   s->this_type = copy->this_type;
 972   /* Don't modify `next' or `pc'. */
 973 }
 974
 975 static void
 976 copy_state_with_stack (state *s, state *orig, int max_stack, int max_locals)
 977 {
 978   init_state_with_stack (s, max_stack, max_locals);
 979   copy_state (s, orig, max_stack, max_locals);
 980 }
 981
 982 /* Allocate a new state, copying ORIG. */
 983 static state *
 984 make_state_copy (state *orig, int max_stack, int max_locals)
 985 {
 986   state *s = vfy_alloc (sizeof (state));
 987   copy_state_with_stack (s, orig, max_stack, max_locals);
 988   return s;
 989 }
 990
 991 static state *
 992 make_state (int max_stack, int max_locals)
 993 {
 994   state *s = vfy_alloc (sizeof (state));
 995   init_state_with_stack (s, max_stack, max_locals);
 996   return s;
 997 }
 998
 999 static void
1000 free_state (state *s)
1001 {
1002   if (s->stack != NULL)
1003     vfy_free (s->stack);
1004   if (s->locals != NULL)
1005     vfy_free (s->locals);
1006 }
1007
1008 /* Modify this state to reflect entry to an exception handler.  */
1009 static void
1010 state_set_exception (state *s, type *t, int max_stack)
1011 {
1012   int i;
1013   s->stackdepth = 1;
1014   s->stacktop = 1;
1015   s->stack[0] = *t;
1016   for (i = s->stacktop; i < max_stack; ++i)
1017     init_type_from_tag (&s->stack[i], unsuitable_type);
1018 }
1019
1020 /* Merge STATE_OLD into this state.  Destructively modifies this
1021    state.  Returns true if the new state was in fact changed.
1022    Will throw an exception if the states are not mergeable.  */
1023 static bool
1024 merge_states (state *s, state *state_old, int max_locals)
1025 {
1026   int i;
1027   bool changed = false;
1028
1029   /* Special handling for `this'.  If one or the other is
1030      uninitialized, then the merge is uninitialized.  */
1031   if (type_initialized (&s->this_type))
1032     s->this_type = state_old->this_type;
1033
1034   /* Merge stacks.  */
1035   if (state_old->stacktop != s->stacktop)  /* FIXME stackdepth instead?  */
1036     verify_fail ("stack sizes differ");
1037   for (i = 0; i < state_old->stacktop; ++i)
1038     {
1039       if (merge_types (&s->stack[i], &state_old->stack[i], false))
1040         changed = true;
1041     }
1042
1043   /* Merge local variables.  */
1044   for (i = 0; i < max_locals; ++i)
1045     {
1046       if (merge_types (&s->locals[i], &state_old->locals[i], true))
1047         changed = true;
1048     }
1049
1050   return changed;
1051 }
1052
1053 /* Ensure that `this' has been initialized.  */
1054 static void
1055 state_check_this_initialized (state *s)
1056 {
1057   if (type_isreference (&s->this_type) && ! type_initialized (&s->this_type))
1058     verify_fail ("`this' is uninitialized");
1059 }
1060
1061 /* Set type of `this'.  */
1062 static void
1063 state_set_this_type (state *s, type *k)
1064 {
1065   s->this_type = *k;
1066 }
1067
1068 /* Mark each `new'd object we know of that was allocated at PC as
1069    initialized.  */
1070 static void
1071 state_set_initialized (state *s, int pc, int max_locals)
1072 {
1073   int i;
1074   for (i = 0; i < s->stacktop; ++i)
1075     type_set_initialized (&s->stack[i], pc);
1076   for (i = 0; i < max_locals; ++i)
1077     type_set_initialized (&s->locals[i], pc);
1078   type_set_initialized (&s->this_type, pc);
1079 }
1080
1081 /* This tests to see whether two states can be considered "merge
1082    compatible".  If both states have a return-address in the same
1083    slot, and the return addresses are different, then they are not
1084    compatible and we must not try to merge them.  */
1085 static bool
1086 state_mergeable_p (state *s, state *other, int max_locals)
1087
1088 {
1089   int i;
1090
1091   /* This is tricky: if the stack sizes differ, then not only are
1092      these not mergeable, but in fact we should give an error, as
1093      we've found two execution paths that reach a branch target
1094      with different stack depths.  FIXME stackdepth instead?  */
1095   if (s->stacktop != other->stacktop)
1096     verify_fail ("stack sizes differ");
1097
1098   for (i = 0; i < s->stacktop; ++i)
1099     if (! type_state_mergeable_p (&s->stack[i], &other->stack[i]))
1100       return false;
1101   for (i = 0; i < max_locals; ++i)
1102     if (! type_state_mergeable_p (&s->locals[i], &other->locals[i]))
1103       return false;
1104   return true;
1105 }
1106
1107 static void
1108 state_reverify (state *s)
1109 {
1110   if (s->next == INVALID_STATE)
1111     {
1112       s->next = vfr->next_verify_state;
1113       vfr->next_verify_state = s;
1114     }
1115 }
1116
1117 #ifdef VERIFY_DEBUG
1118 static void
1119 debug_print_state (state *s, const char *leader, int pc, int max_stack,
1120                    int max_locals)
1121 {
1122   int i;
1123   debug_print ("%s [%4d]:   [stack] ", leader, pc);
1124   for (i = 0; i < s->stacktop; ++i)
1125     type_print (&s->stack[i]);
1126   for (; i < max_stack; ++i)
1127     debug_print (".");
1128   debug_print ("    [local] ");
1129   for (i = 0; i < max_locals; ++i)
1130     type_print (&s->locals[i]);
1131   debug_print (" | %p\n", s);
1132 }
1133 #else
1134 static void
1135 debug_print_state (state *s ATTRIBUTE_UNUSED,
1136                    const char *leader ATTRIBUTE_UNUSED,
1137                    int pc ATTRIBUTE_UNUSED, int max_stack ATTRIBUTE_UNUSED,
1138                    int max_locals ATTRIBUTE_UNUSED)
1139 {
1140 }
1141 #endif /* VERIFY_DEBUG */
1142
1143 static type
1144 pop_raw (void)
1145 {
1146   type r;
1147   state *s = vfr->current_state;
1148   if (s->stacktop <= 0)
1149     verify_fail ("stack empty");
1150   r = s->stack[--s->stacktop];
1151   s->stackdepth -= type_depth (&r);
1152   if (s->stackdepth < 0)
1153     verify_fail_pc ("stack empty", vfr->start_PC);
1154   return r;
1155 }
1156
1157 static type
1158 pop32 (void)
1159 {
1160   type r = pop_raw ();
1161   if (type_iswide (&r))
1162     verify_fail ("narrow pop of wide type");
1163   return r;
1164 }
1165
1166 static type
1167 vfy_pop_type_t (type match)
1168 {
1169   type t;
1170   vfy_promote_type (&match);
1171   t = pop_raw ();
1172   if (! types_compatible (&match, &t))
1173     verify_fail ("incompatible type on stack");
1174   return t;
1175 }
1176
1177 static type
1178 vfy_pop_type (type_val match)
1179 {
1180   type t = make_type (match);
1181   return vfy_pop_type_t (t);
1182 }
1183
1184 #define pop_type vfy_pop_type
1185 #define pop_type_t vfy_pop_type_t
1186
1187 /* Pop a reference which is guaranteed to be initialized.  MATCH
1188    doesn't have to be a reference type; in this case this acts like
1189    pop_type.  */
1190 static type
1191 pop_init_ref_t (type match)
1192 {
1193   type t = pop_raw ();
1194   if (type_isreference (&t) && ! type_initialized (&t))
1195     verify_fail ("initialized reference required");
1196   else if (! types_compatible (&match, &t))
1197     verify_fail ("incompatible type on stack");
1198   return t;
1199 }
1200
1201 static type
1202 pop_init_ref (type_val match)
1203 {
1204   type t = make_type (match);
1205   return pop_init_ref_t (t);
1206 }
1207
1208 /* Pop a reference type or a return address.  */
1209 static type
1210 pop_ref_or_return (void)
1211 {
1212   type t = pop_raw ();
1213   if (! type_isreference (&t) && t.key != return_address_type)
1214     verify_fail ("expected reference or return address on stack");
1215   return t;
1216 }
1217
1218 static void
1219 vfy_push_type_t (type t)
1220 {
1221   int depth;
1222   state *s = vfr->current_state;
1223   /* If T is a numeric type like short, promote it to int.  */
1224   promote_type (&t);
1225
1226   depth = type_depth (&t);
1227
1228   if (s->stackdepth + depth > vfr->current_method->max_stack)
1229     verify_fail ("stack overflow");
1230   s->stack[s->stacktop++] = t;
1231   s->stackdepth += depth;
1232 }
1233
1234 static void
1235 vfy_push_type (type_val tval)
1236 {
1237   type t = make_type (tval);
1238   vfy_push_type_t (t);
1239 }
1240
1241 #define push_type vfy_push_type
1242 #define push_type_t vfy_push_type_t
1243
1244 static void
1245 set_variable (int index, type t)
1246 {
1247   int depth;
1248   state *s = vfr->current_state;
1249   /* If T is a numeric type like short, promote it to int.  */
1250   promote_type (&t);
1251
1252   depth = type_depth (&t);
1253   if (index > vfr->current_method->max_locals - depth)
1254     verify_fail ("invalid local variable");
1255   s->locals[index] = t;
1256
1257   if (depth == 2)
1258     init_type_from_tag (&s->locals[index + 1], continuation_type);
1259   if (index > 0 && type_iswide (&s->locals[index - 1]))
1260     init_type_from_tag (&s->locals[index - 1], unsuitable_type);
1261 }
1262
1263 static type
1264 get_variable_t (int index, type *t)
1265 {
1266   state *s = vfr->current_state;
1267   int depth = type_depth (t);
1268   if (index > vfr->current_method->max_locals - depth)
1269     verify_fail ("invalid local variable");
1270   if (! types_compatible (t, &s->locals[index]))
1271     verify_fail ("incompatible type in local variable");
1272   if (depth == 2)
1273     {
1274       type cont = make_type (continuation_type);
1275       if (! types_compatible (&s->locals[index + 1], &cont))
1276         verify_fail ("invalid local variable");
1277     }
1278   return s->locals[index];
1279 }
1280
1281 static type
1282 get_variable (int index, type_val v)
1283 {
1284   type t = make_type (v);
1285   return get_variable_t (index, &t);
1286 }
1287
1288 /* Make sure ARRAY is an array type and that its elements are
1289    compatible with type ELEMENT.  Returns the actual element type.  */
1290 static type
1291 require_array_type_t (type array, type element)
1292 {
1293   type t;
1294   /* An odd case.  Here we just pretend that everything went ok.  If
1295      the requested element type is some kind of reference, return
1296      the null type instead.  */
1297   if (type_isnull (&array))
1298     return type_isreference (&element) ? make_type (null_type) : element;
1299
1300   if (! type_isarray (&array))
1301     verify_fail ("array required");
1302
1303   t = type_array_element (&array);
1304   if (! types_compatible (&element, &t))
1305     {
1306       /* Special case for byte arrays, which must also be boolean
1307          arrays.  */
1308       bool ok = true;
1309       if (element.key == byte_type)
1310         {
1311           type e2 = make_type (boolean_type);
1312           ok = types_compatible (&e2, &t);
1313         }
1314       if (! ok)
1315         verify_fail ("incompatible array element type");
1316     }
1317
1318   /* Return T and not ELEMENT, because T might be specialized.  */
1319   return t;
1320 }
1321
1322 static type
1323 require_array_type (type array, type_val element)
1324 {
1325   type t = make_type (element);
1326   return require_array_type_t (array, t);
1327 }
1328
1329 static jint
1330 get_byte (void)
1331 {
1332   if (vfr->PC >= vfr->current_method->code_length)
1333     verify_fail ("premature end of bytecode");
1334   return (jint) vfr->bytecode[vfr->PC++] & 0xff;
1335 }
1336
1337 static jint
1338 get_ushort (void)
1339 {
1340   jint b1 = get_byte ();
1341   jint b2 = get_byte ();
1342   return (jint) ((b1 << 8) | b2) & 0xffff;
1343 }
1344
1345 static jint
1346 get_short (void)
1347 {
1348   signed char b1 = (signed char) get_byte ();
1349   jint b2 = get_byte ();
1350   jshort s = (b1 << 8) | b2;
1351   return (jint) s;
1352 }
1353
1354 static jint
1355 get_int (void)
1356 {
1357   jint b1 = get_byte ();
1358   jint b2 = get_byte ();
1359   jint b3 = get_byte ();
1360   jint b4 = get_byte ();
1361   jword result = (b1 << 24) | (b2 << 16) | (b3 << 8) | b4;
1362   /* In the compiler, 'jint' might have more than 32 bits, so we must
1363      sign extend.  */
1364   return WORD_TO_INT (result);
1365 }
1366
1367 static int
1368 compute_jump (int offset)
1369 {
1370   int npc = vfr->start_PC + offset;
1371   if (npc < 0 || npc >= vfr->current_method->code_length)
1372     verify_fail_pc ("branch out of range", vfr->start_PC);
1373   return npc;
1374 }
1375
1376 /* Add a new state to the state list at NPC.  */
1377 static state *
1378 add_new_state (int npc, state *old_state)
1379 {
1380   state_list *nlink;
1381   vfy_method *current_method = vfr->current_method;
1382   state *new_state = make_state_copy (old_state, current_method->max_stack,
1383                                       current_method->max_locals);
1384   debug_print ("== New state in add_new_state\n");
1385   debug_print_state (new_state, "New", npc, current_method->max_stack,
1386                     current_method->max_locals);
1387
1388   nlink = vfy_alloc (sizeof (state_list));
1389   nlink->val = new_state;
1390   nlink->next = vfr->states[npc];
1391   vfr->states[npc] = nlink;
1392   new_state->pc = npc;
1393   return new_state;
1394 }
1395
1396 /* Merge the indicated state into the state at the branch target and
1397    schedule a new PC if there is a change.  NPC is the PC of the
1398    branch target, and FROM_STATE is the state at the source of the
1399    branch.  This method returns true if the destination state
1400    changed and requires reverification, false otherwise.  */
1401 static void
1402 merge_into (int npc, state *from_state)
1403 {
1404   /* Iterate over all target states and merge our state into each,
1405      if applicable.  FIXME one improvement we could make here is
1406      "state destruction".  Merging a new state into an existing one
1407      might cause a return_address_type to be merged to
1408      unsuitable_type.  In this case the resulting state may now be
1409      mergeable with other states currently held in parallel at this
1410      location.  So in this situation we could pairwise compare and
1411      reduce the number of parallel states.  */
1412   state_list *iter;
1413   bool applicable = false;
1414   for (iter = vfr->states[npc]; iter != NULL; iter = iter->next)
1415     {
1416       state *new_state = iter->val;
1417       vfy_method *current_method = vfr->current_method;
1418
1419       if (state_mergeable_p (new_state, from_state,
1420                                         current_method->max_locals))
1421         {
1422           bool changed;
1423           applicable = true;
1424
1425           debug_print ("== Merge states in merge_into\n");
1426           debug_print_state (from_state, "Frm", vfr->start_PC, current_method->max_stack,
1427                              current_method->max_locals);
1428           debug_print_state (new_state, " To", npc, current_method->max_stack,
1429                             current_method->max_locals);
1430           changed = merge_states (new_state, from_state,
1431                                   current_method->max_locals);
1432           debug_print_state (new_state, "New", npc, current_method->max_stack,
1433                             current_method->max_locals);
1434
1435           if (changed)
1436             state_reverify (new_state);
1437         }
1438     }
1439
1440   if (! applicable)
1441     {
1442       /* Either we don't yet have a state at NPC, or we have a
1443          return-address type that is in conflict with all existing
1444          state.  So, we need to create a new entry.  */
1445       state *new_state = add_new_state (npc, from_state);
1446       /* A new state added in this way must always be reverified.  */
1447       state_reverify (new_state);
1448     }
1449 }
1450
1451 static void
1452 push_jump (int offset)
1453 {
1454   int npc = compute_jump (offset);
1455   /* According to the JVM Spec, we need to check for uninitialized
1456      objects here.  However, this does not actually affect type
1457      safety, and the Eclipse java compiler generates code that
1458      violates this constraint.  */
1459   merge_into (npc, vfr->current_state);
1460 }
1461
1462 static void
1463 push_exception_jump (type t, int pc)
1464 {
1465   state s;
1466   /* According to the JVM Spec, we need to check for uninitialized
1467      objects here.  However, this does not actually affect type
1468      safety, and the Eclipse java compiler generates code that
1469      violates this constraint.  */
1470   copy_state_with_stack (&s, vfr->current_state,
1471                          vfr->current_method->max_stack,
1472                          vfr->current_method->max_locals);
1473   if (vfr->current_method->max_stack < 1)
1474     verify_fail ("stack overflow at exception handler");
1475   state_set_exception (&s, &t, vfr->current_method->max_stack);
1476   merge_into (pc, &s);
1477   /* FIXME: leak.. need free_state or GC */
1478 }
1479
1480 static state *
1481 pop_jump (void)
1482 {
1483   state *new_state = vfr->next_verify_state;
1484   if (new_state == INVALID_STATE)
1485     verify_fail ("programmer error in pop_jump");
1486   if (new_state != NULL)
1487     {
1488       vfr->next_verify_state = new_state->next;
1489       new_state->next = INVALID_STATE;
1490     }
1491   return new_state;
1492 }
1493
1494 static void
1495 invalidate_pc (void)
1496 {
1497   vfr->PC = NO_NEXT;
1498 }
1499
1500 static void
1501 note_branch_target (int pc)
1502 {
1503   /* Don't check `pc <= PC', because we've advanced PC after
1504      fetching the target and we haven't yet checked the next
1505      instruction.  */
1506   if (pc < vfr->PC && ! (vfr->flags[pc] & FLAG_INSN_START))
1507     verify_fail_pc ("branch not to instruction start", vfr->start_PC);
1508   vfr->flags[pc] |= FLAG_BRANCH_TARGET;
1509 }
1510
1511 static void
1512 skip_padding (void)
1513 {
1514   while ((vfr->PC % 4) > 0)
1515     if (get_byte () != 0)
1516       verify_fail ("found nonzero padding byte");
1517 }
1518
1519 /* Do the work for a `ret' instruction.  INDEX is the index into the
1520    local variables.  */
1521 static void
1522 handle_ret_insn (int index)
1523 {
1524   type ret = make_type (return_address_type);
1525   type ret_addr = get_variable_t (index, &ret);
1526   /* It would be nice if we could do this.  However, the JVM Spec
1527      doesn't say that this is what happens.  It is implied that
1528      reusing a return address is invalid, but there's no actual
1529      prohibition against it.  */
1530   /* set_variable (index, unsuitable_type); */
1531
1532   int npc = type_get_pc (&ret_addr);
1533   /* We might be returning to a `jsr' that is at the end of the
1534      bytecode.  This is ok if we never return from the called
1535      subroutine, but if we see this here it is an error.  */
1536   if (npc >= vfr->current_method->code_length)
1537     verify_fail ("fell off end");
1538
1539   /* According to the JVM Spec, we need to check for uninitialized
1540      objects here.  However, this does not actually affect type
1541      safety, and the Eclipse java compiler generates code that
1542      violates this constraint.  */
1543   merge_into (npc, vfr->current_state);
1544   invalidate_pc ();
1545 }
1546
1547 static void handle_jsr_insn (int offset)
1548 {
1549   type ret_addr;
1550   int npc = compute_jump (offset);
1551
1552   /* According to the JVM Spec, we need to check for uninitialized
1553      objects here.  However, this does not actually affect type
1554      safety, and the Eclipse java compiler generates code that
1555      violates this constraint.  */
1556
1557   /* Modify our state as appropriate for entry into a subroutine.  */
1558   ret_addr = make_type (return_address_type);
1559   type_set_return_address (&ret_addr, vfr->PC);
1560   vfy_push_type_t (ret_addr);
1561   merge_into (npc, vfr->current_state);
1562   invalidate_pc ();
1563 }
1564
1565 static vfy_jclass
1566 construct_primitive_array_type (type_val prim)
1567 {
1568   vfy_jclass k = NULL;
1569   switch (prim)
1570     {
1571     case boolean_type:
1572     case char_type:
1573     case float_type:
1574     case double_type:
1575     case byte_type:
1576     case short_type:
1577     case int_type:
1578     case long_type:
1579       k = vfy_get_primitive_type ((int) prim);
1580       break;
1581
1582     /* These aren't used here but we call them out to avoid
1583        warnings.  */
1584     case void_type:
1585     case unsuitable_type:
1586     case return_address_type:
1587     case continuation_type:
1588     case reference_type:
1589     case null_type:
1590     case uninitialized_reference_type:
1591     default:
1592       verify_fail ("unknown type in construct_primitive_array_type");
1593     }
1594   k = vfy_get_array_class (k);
1595   return k;
1596 }
1597
1598 /* This pass computes the location of branch targets and also
1599    instruction starts.  */
1600 static void
1601 branch_prepass (void)
1602 {
1603   int i, pc;
1604   vfr->flags = (char *) vfy_alloc (vfr->current_method->code_length);
1605
1606   for (i = 0; i < vfr->current_method->code_length; ++i)
1607     vfr->flags[i] = 0;
1608
1609   vfr->PC = 0;
1610   while (vfr->PC < vfr->current_method->code_length)
1611     {
1612       java_opcode opcode;
1613       /* Set `start_PC' early so that error checking can have the
1614          correct value.  */
1615       vfr->start_PC = vfr->PC;
1616       vfr->flags[vfr->PC] |= FLAG_INSN_START;
1617
1618       opcode = (java_opcode) vfr->bytecode[vfr->PC++];
1619       switch (opcode)
1620         {
1621         case op_nop:
1622         case op_aconst_null:
1623         case op_iconst_m1:
1624         case op_iconst_0:
1625         case op_iconst_1:
1626         case op_iconst_2:
1627         case op_iconst_3:
1628         case op_iconst_4:
1629         case op_iconst_5:
1630         case op_lconst_0:
1631         case op_lconst_1:
1632         case op_fconst_0:
1633         case op_fconst_1:
1634         case op_fconst_2:
1635         case op_dconst_0:
1636         case op_dconst_1:
1637         case op_iload_0:
1638         case op_iload_1:
1639         case op_iload_2:
1640         case op_iload_3:
1641         case op_lload_0:
1642         case op_lload_1:
1643         case op_lload_2:
1644         case op_lload_3:
1645         case op_fload_0:
1646         case op_fload_1:
1647         case op_fload_2:
1648         case op_fload_3:
1649         case op_dload_0:
1650         case op_dload_1:
1651         case op_dload_2:
1652         case op_dload_3:
1653         case op_aload_0:
1654         case op_aload_1:
1655         case op_aload_2:
1656         case op_aload_3:
1657         case op_iaload:
1658         case op_laload:
1659         case op_faload:
1660         case op_daload:
1661         case op_aaload:
1662         case op_baload:
1663         case op_caload:
1664         case op_saload:
1665         case op_istore_0:
1666         case op_istore_1:
1667         case op_istore_2:
1668         case op_istore_3:
1669         case op_lstore_0:
1670         case op_lstore_1:
1671         case op_lstore_2:
1672         case op_lstore_3:
1673         case op_fstore_0:
1674         case op_fstore_1:
1675         case op_fstore_2:
1676         case op_fstore_3:
1677         case op_dstore_0:
1678         case op_dstore_1:
1679         case op_dstore_2:
1680         case op_dstore_3:
1681         case op_astore_0:
1682         case op_astore_1:
1683         case op_astore_2:
1684         case op_astore_3:
1685         case op_iastore:
1686         case op_lastore:
1687         case op_fastore:
1688         case op_dastore:
1689         case op_aastore:
1690         case op_bastore:
1691         case op_castore:
1692         case op_sastore:
1693         case op_pop:
1694         case op_pop2:
1695         case op_dup:
1696         case op_dup_x1:
1697         case op_dup_x2:
1698         case op_dup2:
1699         case op_dup2_x1:
1700         case op_dup2_x2:
1701         case op_swap:
1702         case op_iadd:
1703         case op_isub:
1704         case op_imul:
1705         case op_idiv:
1706         case op_irem:
1707         case op_ishl:
1708         case op_ishr:
1709         case op_iushr:
1710         case op_iand:
1711         case op_ior:
1712         case op_ixor:
1713         case op_ladd:
1714         case op_lsub:
1715         case op_lmul:
1716         case op_ldiv:
1717         case op_lrem:
1718         case op_lshl:
1719         case op_lshr:
1720         case op_lushr:
1721         case op_land:
1722         case op_lor:
1723         case op_lxor:
1724         case op_fadd:
1725         case op_fsub:
1726         case op_fmul:
1727         case op_fdiv:
1728         case op_frem:
1729         case op_dadd:
1730         case op_dsub:
1731         case op_dmul:
1732         case op_ddiv:
1733         case op_drem:
1734         case op_ineg:
1735         case op_i2b:
1736         case op_i2c:
1737         case op_i2s:
1738         case op_lneg:
1739         case op_fneg:
1740         case op_dneg:
1741         case op_i2l:
1742         case op_i2f:
1743         case op_i2d:
1744         case op_l2i:
1745         case op_l2f:
1746         case op_l2d:
1747         case op_f2i:
1748         case op_f2l:
1749         case op_f2d:
1750         case op_d2i:
1751         case op_d2l:
1752         case op_d2f:
1753         case op_lcmp:
1754         case op_fcmpl:
1755         case op_fcmpg:
1756         case op_dcmpl:
1757         case op_dcmpg:
1758         case op_monitorenter:
1759         case op_monitorexit:
1760         case op_ireturn:
1761         case op_lreturn:
1762         case op_freturn:
1763         case op_dreturn:
1764         case op_areturn:
1765         case op_return:
1766         case op_athrow:
1767         case op_arraylength:
1768           break;
1769
1770         case op_bipush:
1771         case op_ldc:
1772         case op_iload:
1773         case op_lload:
1774         case op_fload:
1775         case op_dload:
1776         case op_aload:
1777         case op_istore:
1778         case op_lstore:
1779         case op_fstore:
1780         case op_dstore:
1781         case op_astore:
1782         case op_ret:
1783         case op_newarray:
1784           get_byte ();
1785           break;
1786
1787         case op_iinc:
1788         case op_sipush:
1789         case op_ldc_w:
1790         case op_ldc2_w:
1791         case op_getstatic:
1792         case op_getfield:
1793         case op_putfield:
1794         case op_putstatic:
1795         case op_new:
1796         case op_anewarray:
1797         case op_instanceof:
1798         case op_checkcast:
1799         case op_invokespecial:
1800         case op_invokestatic:
1801         case op_invokevirtual:
1802           get_short ();
1803           break;
1804
1805         case op_multianewarray:
1806           get_short ();
1807           get_byte ();
1808           break;
1809
1810         case op_jsr:
1811         case op_ifeq:
1812         case op_ifne:
1813         case op_iflt:
1814         case op_ifge:
1815         case op_ifgt:
1816         case op_ifle:
1817         case op_if_icmpeq:
1818         case op_if_icmpne:
1819         case op_if_icmplt:
1820         case op_if_icmpge:
1821         case op_if_icmpgt:
1822         case op_if_icmple:
1823         case op_if_acmpeq:
1824         case op_if_acmpne:
1825         case op_ifnull:
1826         case op_ifnonnull:
1827         case op_goto:
1828           note_branch_target (compute_jump (get_short ()));
1829           break;
1830
1831         case op_tableswitch:
1832           {
1833             jint low, hi;
1834             skip_padding ();
1835             note_branch_target (compute_jump (get_int ()));
1836             low = get_int ();
1837             hi = get_int ();
1838             if (low > hi)
1839               verify_fail_pc ("invalid tableswitch", vfr->start_PC);
1840             for (i = low; i <= hi; ++i)
1841               note_branch_target (compute_jump (get_int ()));
1842           }
1843           break;
1844
1845         case op_lookupswitch:
1846           {
1847             int npairs;
1848             skip_padding ();
1849             note_branch_target (compute_jump (get_int ()));
1850             npairs = get_int ();
1851             if (npairs < 0)
1852               verify_fail_pc ("too few pairs in lookupswitch", vfr->start_PC);
1853             while (npairs-- > 0)
1854               {
1855                 get_int ();
1856                 note_branch_target (compute_jump (get_int ()));
1857               }
1858           }
1859           break;
1860
1861         case op_invokeinterface:
1862           get_short ();
1863           get_byte ();
1864           get_byte ();
1865           break;
1866
1867         case op_wide:
1868           {
1869             opcode = (java_opcode) get_byte ();
1870             get_short ();
1871             if (opcode == op_iinc)
1872               get_short ();
1873           }
1874           break;
1875
1876         case op_jsr_w:
1877         case op_goto_w:
1878           note_branch_target (compute_jump (get_int ()));
1879           break;
1880
1881 #if 0
1882         /* These are unused here, but we call them out explicitly
1883            so that -Wswitch-enum doesn't complain.  */
1884         case op_putfield_1:
1885         case op_putfield_2:
1886         case op_putfield_4:
1887         case op_putfield_8:
1888         case op_putfield_a:
1889         case op_putstatic_1:
1890         case op_putstatic_2:
1891         case op_putstatic_4:
1892         case op_putstatic_8:
1893         case op_putstatic_a:
1894         case op_getfield_1:
1895         case op_getfield_2s:
1896         case op_getfield_2u:
1897         case op_getfield_4:
1898         case op_getfield_8:
1899         case op_getfield_a:
1900         case op_getstatic_1:
1901         case op_getstatic_2s:
1902         case op_getstatic_2u:
1903         case op_getstatic_4:
1904         case op_getstatic_8:
1905         case op_getstatic_a:
1906 #endif /* VFY_FAST_OPCODES  */
1907         default:
1908           verify_fail_pc ("unrecognized instruction in branch_prepass",
1909                           vfr->start_PC);
1910         }
1911
1912       /* See if any previous branch tried to branch to the middle of
1913          this instruction.  */
1914       for (pc = vfr->start_PC + 1; pc < vfr->PC; ++pc)
1915         {
1916           if ((vfr->flags[pc] & FLAG_BRANCH_TARGET))
1917             verify_fail_pc ("branch to middle of instruction", pc);
1918         }
1919     }
1920
1921   /* Verify exception handlers.  */
1922   for (i = 0; i < vfr->current_method->exc_count; ++i)
1923     {
1924       int handler, start, end, htype;
1925       vfy_get_exception (vfr->exception, i, &handler, &start, &end, &htype);
1926       if (! (vfr->flags[handler] & FLAG_INSN_START))
1927         verify_fail_pc ("exception handler not at instruction start",
1928                         handler);
1929       if (! (vfr->flags[start] & FLAG_INSN_START))
1930         verify_fail_pc ("exception start not at instruction start", start);
1931       if (end != vfr->current_method->code_length
1932           && ! (vfr->flags[end] & FLAG_INSN_START))
1933         verify_fail_pc ("exception end not at instruction start", end);
1934
1935       vfr->flags[handler] |= FLAG_BRANCH_TARGET;
1936     }
1937 }
1938
1939 static void
1940 check_pool_index (int index)
1941 {
1942   if (index < 0 || index >= vfy_get_constants_size (vfr->current_class))
1943     verify_fail_pc ("constant pool index out of range", vfr->start_PC);
1944 }
1945
1946 static type
1947 check_class_constant (int index)
1948 {
1949   type t = { 0, 0, 0 };
1950   vfy_constants *pool;
1951
1952   check_pool_index (index);
1953   pool = vfy_get_constants (vfr->current_class);
1954   if (vfy_tag (pool, index) == JV_CONSTANT_ResolvedClass)
1955     init_type_from_class (&t, vfy_get_pool_class (pool, index));
1956   else if (vfy_tag (pool, index) == JV_CONSTANT_Class)
1957     init_type_from_string (&t, vfy_get_pool_string (pool, index));
1958   else
1959     verify_fail_pc ("expected class constant", vfr->start_PC);
1960   return t;
1961 }
1962
1963 static type
1964 check_constant (int index)
1965 {
1966   type t = { 0, 0, 0 };
1967   vfy_constants *pool;
1968
1969   check_pool_index (index);
1970   pool = vfy_get_constants (vfr->current_class);
1971   if (vfy_tag (pool, index) == JV_CONSTANT_ResolvedString
1972       || vfy_tag (pool, index) == JV_CONSTANT_String)
1973     init_type_from_class (&t, vfy_string_type ());
1974   else if (vfy_tag (pool, index) == JV_CONSTANT_Integer)
1975     init_type_from_tag (&t, int_type);
1976   else if (vfy_tag (pool, index) == JV_CONSTANT_Float)
1977     init_type_from_tag (&t, float_type);
1978   else
1979     verify_fail_pc ("String, int, or float constant expected", vfr->start_PC);
1980   return t;
1981 }
1982
1983 static type
1984 check_wide_constant (int index)
1985 {
1986   type t = { 0, 0, 0 };
1987   vfy_constants *pool;
1988
1989   check_pool_index (index);
1990   pool = vfy_get_constants (vfr->current_class);
1991   if (vfy_tag (pool, index) == JV_CONSTANT_Long)
1992     init_type_from_tag (&t, long_type);
1993   else if (vfy_tag (pool, index) == JV_CONSTANT_Double)
1994     init_type_from_tag (&t, double_type);
1995   else
1996     verify_fail_pc ("long or double constant expected", vfr->start_PC);
1997   return t;
1998 }
1999
2000 /* Helper for both field and method.  These are laid out the same in
2001    the constant pool.  */
2002 static type
2003 handle_field_or_method (int index, int expected,
2004                         vfy_string *name, vfy_string *fmtype)
2005 {
2006   vfy_uint_16 class_index, name_and_type_index;
2007   vfy_uint_16 name_index, desc_index;
2008   vfy_constants *pool;
2009
2010   check_pool_index (index);
2011   pool = vfy_get_constants (vfr->current_class);
2012   if (vfy_tag (pool, index) != expected)
2013     verify_fail_pc ("didn't see expected constant", vfr->start_PC);
2014   /* Once we know we have a Fieldref or Methodref we assume that it
2015      is correctly laid out in the constant pool.  I think the code
2016      in defineclass.cc guarantees this.  */
2017   vfy_load_indexes (pool, index, &class_index, &name_and_type_index);
2018   vfy_load_indexes (pool, name_and_type_index, &name_index, &desc_index);
2019
2020   *name = vfy_get_pool_string (pool, name_index);
2021   *fmtype = vfy_get_pool_string (pool, desc_index);
2022
2023   return check_class_constant (class_index);
2024 }
2025
2026 /* Return field's type, compute class' type if requested.  If
2027    PUTFIELD is true, use the special 'putfield' semantics.  */
2028 static type
2029 check_field_constant (int index, type *class_type, bool putfield)
2030 {
2031   vfy_string name, field_type;
2032   const char *typec;
2033   int len;
2034   type t;
2035
2036   type ct = handle_field_or_method (index,
2037                                     JV_CONSTANT_Fieldref,
2038                                     &name, &field_type);
2039   if (class_type)
2040     *class_type = ct;
2041   typec = vfy_string_bytes (field_type);
2042   len = vfy_string_length (field_type);
2043   if (typec[0] == '[' || typec[0] == 'L')
2044     init_type_from_string (&t, field_type);
2045   else
2046     init_type_from_tag (&t, get_type_val_for_signature (typec[0]));
2047
2048   /* We have an obscure special case here: we can use `putfield' on a
2049      field declared in this class, even if `this' has not yet been
2050      initialized.  */
2051   if (putfield
2052       && ! type_initialized (&vfr->current_state->this_type)
2053       && vfr->current_state->this_type.pc == SELF
2054       && types_equal (&vfr->current_state->this_type, &ct)
2055       && vfy_class_has_field (vfr->current_class, name, field_type))
2056     /* Note that we don't actually know whether we're going to match
2057        against 'this' or some other object of the same type.  So,
2058        here we set things up so that it doesn't matter.  This relies
2059        on knowing what our caller is up to.  */
2060     type_set_uninitialized (class_type, EITHER);
2061
2062   return t;
2063 }
2064
2065 static type
2066 check_method_constant (int index, bool is_interface,
2067                             vfy_string *method_name,
2068                             vfy_string *method_signature)
2069 {
2070   return handle_field_or_method (index,
2071                                  (is_interface
2072                                   ? JV_CONSTANT_InterfaceMethodref
2073                                   : JV_CONSTANT_Methodref),
2074                                  method_name, method_signature);
2075 }
2076
2077 static char *
2078 get_one_type (char *p, type *t)
2079 {
2080   const char *start = p;
2081   vfy_jclass k;
2082   type_val rt;
2083   char v;
2084
2085   int arraycount = 0;
2086   while (*p == '[')
2087     {
2088       ++arraycount;
2089       ++p;
2090     }
2091
2092   v = *p++;
2093
2094   if (v == 'L')
2095     {
2096       vfy_string name;
2097       while (*p != ';')
2098         ++p;
2099       ++p;
2100       name = vfy_get_string (start, p - start);
2101       *t = make_type_from_string (name);
2102       return p;
2103     }
2104
2105   /* Casting to jchar here is ok since we are looking at an ASCII
2106      character.  */
2107   rt = get_type_val_for_signature (v);
2108
2109   if (arraycount == 0)
2110     {
2111       /* Callers of this function eventually push their arguments on
2112          the stack.  So, promote them here.  */
2113       type new_t = make_type (rt);
2114       vfy_promote_type (&new_t);
2115       *t = new_t;
2116       return p;
2117     }
2118
2119   k = construct_primitive_array_type (rt);
2120   while (--arraycount > 0)
2121     k = vfy_get_array_class (k);
2122   *t = make_type_from_class (k);
2123   return p;
2124 }
2125
2126 static void
2127 compute_argument_types (vfy_string signature, type *types)
2128 {
2129   int i;
2130   char *p = (char *) vfy_string_bytes (signature);
2131
2132   /* Skip `('.  */
2133   ++p;
2134
2135   i = 0;
2136   while (*p != ')')
2137     p = get_one_type (p, &types[i++]);
2138 }
2139
2140 static type
2141 compute_return_type (vfy_string signature)
2142 {
2143   char *p = (char *) vfy_string_bytes (signature);
2144   type t;
2145   while (*p != ')')
2146     ++p;
2147   ++p;
2148   get_one_type (p, &t);
2149   return t;
2150 }
2151
2152 static void
2153 check_return_type (type onstack)
2154 {
2155   type rt = compute_return_type (vfy_get_signature (vfr->current_method));
2156   if (! types_compatible (&rt, &onstack))
2157     verify_fail ("incompatible return type");
2158 }
2159
2160 /* Initialize the stack for the new method.  Returns true if this
2161    method is an instance initializer.  */
2162 static bool
2163 initialize_stack (void)
2164 {
2165   int arg_count, i;
2166   int var = 0;
2167   bool is_init = vfy_strings_equal (vfy_get_method_name (vfr->current_method),
2168                                     vfy_init_name());
2169   bool is_clinit = vfy_strings_equal (vfy_get_method_name (vfr->current_method),
2170                                       vfy_clinit_name());
2171
2172   if (! vfy_is_static (vfr->current_method))
2173     {
2174       type kurr = make_type_from_class (vfr->current_class);
2175       if (is_init)
2176         {
2177           type_set_uninitialized (&kurr, SELF);
2178           is_init = true;
2179         }
2180       else if (is_clinit)
2181         verify_fail ("<clinit> method must be static");
2182       set_variable (0, kurr);
2183       state_set_this_type (vfr->current_state, &kurr);
2184       ++var;
2185     }
2186   else
2187     {
2188       if (is_init)
2189         verify_fail ("<init> method must be non-static");
2190     }
2191
2192   /* We have to handle wide arguments specially here.  */
2193   arg_count = vfy_count_arguments (vfy_get_signature (vfr->current_method));
2194   {
2195     type *arg_types = (type *) vfy_alloc (arg_count * sizeof (type));
2196     compute_argument_types (vfy_get_signature (vfr->current_method), arg_types);
2197     for (i = 0; i < arg_count; ++i)
2198       {
2199         set_variable (var, arg_types[i]);
2200         ++var;
2201         if (type_iswide (&arg_types[i]))
2202           ++var;
2203       }
2204     vfy_free (arg_types);
2205   }
2206
2207   return is_init;
2208 }
2209
2210 static void
2211 verify_instructions_0 (void)
2212 {
2213   int i;
2214   bool this_is_init;
2215
2216   vfr->current_state = make_state (vfr->current_method->max_stack,
2217                                    vfr->current_method->max_locals);
2218
2219   vfr->PC = 0;
2220   vfr->start_PC = 0;
2221
2222   /*  True if we are verifying an instance initializer.  */
2223   this_is_init = initialize_stack ();
2224
2225   vfr->states = (state_list **) vfy_alloc (sizeof (state_list *)
2226                                       * vfr->current_method->code_length);
2227
2228   for (i = 0; i < vfr->current_method->code_length; ++i)
2229     vfr->states[i] = NULL;
2230
2231   vfr->next_verify_state = NULL;
2232
2233   while (true)
2234     {
2235       java_opcode opcode;
2236
2237       /* If the PC was invalidated, get a new one from the work list.  */
2238       if (vfr->PC == NO_NEXT)
2239         {
2240           state *new_state = pop_jump ();
2241           /* If it is null, we're done.  */
2242           if (new_state == NULL)
2243             break;
2244
2245           vfr->PC = new_state->pc;
2246           debug_print ("== State pop from pending list\n");
2247           /* Set up the current state.  */
2248           copy_state (vfr->current_state, new_state,
2249             vfr->current_method->max_stack, vfr->current_method->max_locals);
2250         }
2251       else
2252         {
2253           /* We only have to do this checking in the situation where
2254              control flow falls through from the previous instruction.
2255              Otherwise merging is done at the time we push the branch.
2256              Note that we'll catch the off-the-end problem just
2257              below.  */
2258           if (vfr->PC < vfr->current_method->code_length
2259               && vfr->states[vfr->PC] != NULL)
2260             {
2261               /* We've already visited this instruction.  So merge
2262                  the states together.  It is simplest, but not most
2263                  efficient, to just always invalidate the PC here.  */
2264               merge_into (vfr->PC, vfr->current_state);
2265               invalidate_pc ();
2266               continue;
2267             }
2268         }
2269
2270       /* Control can't fall off the end of the bytecode.  We need to
2271          check this in both cases, not just the fall-through case,
2272          because we don't check to see whether a `jsr' appears at
2273          the end of the bytecode until we process a `ret'.  */
2274       if (vfr->PC >= vfr->current_method->code_length)
2275         verify_fail ("fell off end");
2276       vfr->flags[vfr->PC] |= FLAG_INSN_SEEN;
2277
2278       /* We only have to keep saved state at branch targets.  If
2279          we're at a branch target and the state here hasn't been set
2280          yet, we set it now.  You might notice that `ret' targets
2281          won't necessarily have FLAG_BRANCH_TARGET set.  This
2282          doesn't matter, since those states will be filled in by
2283          merge_into.  */
2284       /* Note that other parts of the compiler assume that there is a
2285          label with a type map at PC=0.  */
2286       if (vfr->states[vfr->PC] == NULL
2287           && (vfr->PC == 0 || (vfr->flags[vfr->PC] & FLAG_BRANCH_TARGET) != 0))
2288         add_new_state (vfr->PC, vfr->current_state);
2289
2290       /* Set this before handling exceptions so that debug output is
2291          sane.  */
2292       vfr->start_PC = vfr->PC;
2293
2294       /* Update states for all active exception handlers.  Ordinarily
2295          there are not many exception handlers.  So we simply run
2296          through them all.  */
2297       for (i = 0; i < vfr->current_method->exc_count; ++i)
2298         {
2299           int hpc, start, end, htype;
2300           vfy_get_exception (vfr->exception, i, &hpc, &start, &end, &htype);
2301           if (vfr->PC >= start && vfr->PC < end)
2302             {
2303               type handler = make_type_from_class (vfy_throwable_type ());
2304               if (htype != 0)
2305                 handler = check_class_constant (htype);
2306               push_exception_jump (handler, hpc);
2307             }
2308         }
2309
2310
2311       debug_print_state (vfr->current_state, "   ", vfr->PC,
2312                          vfr->current_method->max_stack,
2313                          vfr->current_method->max_locals);
2314       opcode = (java_opcode) vfr->bytecode[vfr->PC++];
2315       switch (opcode)
2316         {
2317         case op_nop:
2318           break;
2319
2320         case op_aconst_null:
2321           push_type (null_type);
2322           break;
2323
2324         case op_iconst_m1:
2325         case op_iconst_0:
2326         case op_iconst_1:
2327         case op_iconst_2:
2328         case op_iconst_3:
2329         case op_iconst_4:
2330         case op_iconst_5:
2331           push_type (int_type);
2332           break;
2333
2334         case op_lconst_0:
2335         case op_lconst_1:
2336           push_type (long_type);
2337           break;
2338
2339         case op_fconst_0:
2340         case op_fconst_1:
2341         case op_fconst_2:
2342           push_type (float_type);
2343           break;
2344
2345         case op_dconst_0:
2346         case op_dconst_1:
2347           push_type (double_type);
2348           break;
2349
2350         case op_bipush:
2351           get_byte ();
2352           push_type (int_type);
2353           break;
2354
2355         case op_sipush:
2356           get_short ();
2357           push_type (int_type);
2358           break;
2359
2360         case op_ldc:
2361           push_type_t (check_constant (get_byte ()));
2362           break;
2363         case op_ldc_w:
2364           push_type_t (check_constant (get_ushort ()));
2365           break;
2366         case op_ldc2_w:
2367           push_type_t (check_wide_constant (get_ushort ()));
2368           break;
2369
2370         case op_iload:
2371           push_type_t (get_variable (get_byte (), int_type));
2372           break;
2373         case op_lload:
2374           push_type_t (get_variable (get_byte (), long_type));
2375           break;
2376         case op_fload:
2377           push_type_t (get_variable (get_byte (), float_type));
2378           break;
2379         case op_dload:
2380           push_type_t (get_variable (get_byte (), double_type));
2381           break;
2382         case op_aload:
2383           push_type_t (get_variable (get_byte (), reference_type));
2384           break;
2385
2386         case op_iload_0:
2387         case op_iload_1:
2388         case op_iload_2:
2389         case op_iload_3:
2390           push_type_t (get_variable (opcode - op_iload_0, int_type));
2391           break;
2392         case op_lload_0:
2393         case op_lload_1:
2394         case op_lload_2:
2395         case op_lload_3:
2396           push_type_t (get_variable (opcode - op_lload_0, long_type));
2397           break;
2398         case op_fload_0:
2399         case op_fload_1:
2400         case op_fload_2:
2401         case op_fload_3:
2402           push_type_t (get_variable (opcode - op_fload_0, float_type));
2403           break;
2404         case op_dload_0:
2405         case op_dload_1:
2406         case op_dload_2:
2407         case op_dload_3:
2408           push_type_t (get_variable (opcode - op_dload_0, double_type));
2409           break;
2410         case op_aload_0:
2411         case op_aload_1:
2412         case op_aload_2:
2413         case op_aload_3:
2414           push_type_t (get_variable (opcode - op_aload_0, reference_type));
2415           break;
2416         case op_iaload:
2417           pop_type (int_type);
2418           push_type_t (require_array_type (pop_init_ref (reference_type),
2419                                          int_type));
2420           break;
2421         case op_laload:
2422           pop_type (int_type);
2423           push_type_t (require_array_type (pop_init_ref (reference_type),
2424                                          long_type));
2425           break;
2426         case op_faload:
2427           pop_type (int_type);
2428           push_type_t (require_array_type (pop_init_ref (reference_type),
2429                                          float_type));
2430           break;
2431         case op_daload:
2432           pop_type (int_type);
2433           push_type_t (require_array_type (pop_init_ref (reference_type),
2434                                          double_type));
2435           break;
2436         case op_aaload:
2437           pop_type (int_type);
2438           push_type_t (require_array_type (pop_init_ref (reference_type),
2439                                          reference_type));
2440           break;
2441         case op_baload:
2442           pop_type (int_type);
2443           require_array_type (pop_init_ref (reference_type), byte_type);
2444           push_type (int_type);
2445           break;
2446         case op_caload:
2447           pop_type (int_type);
2448           require_array_type (pop_init_ref (reference_type), char_type);
2449           push_type (int_type);
2450           break;
2451         case op_saload:
2452           pop_type (int_type);
2453           require_array_type (pop_init_ref (reference_type), short_type);
2454           push_type (int_type);
2455           break;
2456         case op_istore:
2457           set_variable (get_byte (), pop_type (int_type));
2458           break;
2459         case op_lstore:
2460           set_variable (get_byte (), pop_type (long_type));
2461           break;
2462         case op_fstore:
2463           set_variable (get_byte (), pop_type (float_type));
2464           break;
2465         case op_dstore:
2466           set_variable (get_byte (), pop_type (double_type));
2467           break;
2468         case op_astore:
2469           set_variable (get_byte (), pop_ref_or_return ());
2470           break;
2471         case op_istore_0:
2472         case op_istore_1:
2473         case op_istore_2:
2474         case op_istore_3:
2475           set_variable (opcode - op_istore_0, pop_type (int_type));
2476           break;
2477         case op_lstore_0:
2478         case op_lstore_1:
2479         case op_lstore_2:
2480         case op_lstore_3:
2481           set_variable (opcode - op_lstore_0, pop_type (long_type));
2482           break;
2483         case op_fstore_0:
2484         case op_fstore_1:
2485         case op_fstore_2:
2486         case op_fstore_3:
2487           set_variable (opcode - op_fstore_0, pop_type (float_type));
2488           break;
2489         case op_dstore_0:
2490         case op_dstore_1:
2491         case op_dstore_2:
2492         case op_dstore_3:
2493           set_variable (opcode - op_dstore_0, pop_type (double_type));
2494           break;
2495         case op_astore_0:
2496         case op_astore_1:
2497         case op_astore_2:
2498         case op_astore_3:
2499           set_variable (opcode - op_astore_0, pop_ref_or_return ());
2500           break;
2501         case op_iastore:
2502           pop_type (int_type);
2503           pop_type (int_type);
2504           require_array_type (pop_init_ref (reference_type), int_type);
2505           break;
2506         case op_lastore:
2507           pop_type (long_type);
2508           pop_type (int_type);
2509           require_array_type (pop_init_ref (reference_type), long_type);
2510           break;
2511         case op_fastore:
2512           pop_type (float_type);
2513           pop_type (int_type);
2514           require_array_type (pop_init_ref (reference_type), float_type);
2515           break;
2516         case op_dastore:
2517           pop_type (double_type);
2518           pop_type (int_type);
2519           require_array_type (pop_init_ref (reference_type), double_type);
2520           break;
2521         case op_aastore:
2522           pop_type (reference_type);
2523           pop_type (int_type);
2524           require_array_type (pop_init_ref (reference_type), reference_type);
2525           break;
2526         case op_bastore:
2527           pop_type (int_type);
2528           pop_type (int_type);
2529           require_array_type (pop_init_ref (reference_type), byte_type);
2530           break;
2531         case op_castore:
2532           pop_type (int_type);
2533           pop_type (int_type);
2534           require_array_type (pop_init_ref (reference_type), char_type);
2535           break;
2536         case op_sastore:
2537           pop_type (int_type);
2538           pop_type (int_type);
2539           require_array_type (pop_init_ref (reference_type), short_type);
2540           break;
2541         case op_pop:
2542           pop32 ();
2543           break;
2544         case op_pop2:
2545           {
2546             type t = pop_raw ();
2547             if (! type_iswide (&t))
2548               pop32 ();
2549           }
2550           break;
2551         case op_dup:
2552           {
2553             type t = pop32 ();
2554             push_type_t (t);
2555             push_type_t (t);
2556           }
2557           break;
2558         case op_dup_x1:
2559           {
2560             type t1 = pop32 ();
2561             type t2 = pop32 ();
2562             push_type_t (t1);
2563             push_type_t (t2);
2564             push_type_t (t1);
2565           }
2566           break;
2567         case op_dup_x2:
2568           {
2569             type t1 = pop32 ();
2570             type t2 = pop_raw ();
2571             if (! type_iswide (&t2))
2572               {
2573                 type t3 = pop32 ();
2574                 push_type_t (t1);
2575                 push_type_t (t3);
2576               }
2577             else
2578               push_type_t (t1);
2579             push_type_t (t2);
2580             push_type_t (t1);
2581           }
2582           break;
2583         case op_dup2:
2584           {
2585             type t = pop_raw ();
2586             if (! type_iswide (&t))
2587               {
2588                 type t2 = pop32 ();
2589                 push_type_t (t2);
2590                 push_type_t (t);
2591                 push_type_t (t2);
2592               }
2593             else
2594               push_type_t (t);
2595             push_type_t (t);
2596           }
2597           break;
2598         case op_dup2_x1:
2599           {
2600             type t1 = pop_raw ();
2601             type t2 = pop32 ();
2602             if (! type_iswide (&t1))
2603               {
2604                 type t3 = pop32 ();
2605                 push_type_t (t2);
2606                 push_type_t (t1);
2607                 push_type_t (t3);
2608               }
2609             else
2610               push_type_t (t1);
2611             push_type_t (t2);
2612             push_type_t (t1);
2613           }
2614           break;
2615         case op_dup2_x2:
2616           {
2617             type t1 = pop_raw ();
2618             if (type_iswide (&t1))
2619               {
2620                 type t2 = pop_raw ();
2621                 if (type_iswide (&t2))
2622                   {
2623                     push_type_t (t1);
2624                     push_type_t (t2);
2625                   }
2626                 else
2627                   {
2628                     type t3 = pop32 ();
2629                     push_type_t (t1);
2630                     push_type_t (t3);
2631                     push_type_t (t2);
2632                   }
2633                 push_type_t (t1);
2634               }
2635             else
2636               {
2637                 type t2 = pop32 ();
2638                 type t3 = pop_raw ();
2639                 if (type_iswide (&t3))
2640                   {
2641                     push_type_t (t2);
2642                     push_type_t (t1);
2643                   }
2644                 else
2645                   {
2646                     type t4 = pop32 ();
2647                     push_type_t (t2);
2648                     push_type_t (t1);
2649                     push_type_t (t4);
2650                   }
2651                 push_type_t (t3);
2652                 push_type_t (t2);
2653                 push_type_t (t1);
2654               }
2655           }
2656           break;
2657         case op_swap:
2658           {
2659             type t1 = pop32 ();
2660             type t2 = pop32 ();
2661             push_type_t (t1);
2662             push_type_t (t2);
2663           }
2664           break;
2665         case op_iadd:
2666         case op_isub:
2667         case op_imul:
2668         case op_idiv:
2669         case op_irem:
2670         case op_ishl:
2671         case op_ishr:
2672         case op_iushr:
2673         case op_iand:
2674         case op_ior:
2675         case op_ixor:
2676           pop_type (int_type);
2677           push_type_t (pop_type (int_type));
2678           break;
2679         case op_ladd:
2680         case op_lsub:
2681         case op_lmul:
2682         case op_ldiv:
2683         case op_lrem:
2684         case op_land:
2685         case op_lor:
2686         case op_lxor:
2687           pop_type (long_type);
2688           push_type_t (pop_type (long_type));
2689           break;
2690         case op_lshl:
2691         case op_lshr:
2692         case op_lushr:
2693           pop_type (int_type);
2694           push_type_t (pop_type (long_type));
2695           break;
2696         case op_fadd:
2697         case op_fsub:
2698         case op_fmul:
2699         case op_fdiv:
2700         case op_frem:
2701           pop_type (float_type);
2702           push_type_t (pop_type (float_type));
2703           break;
2704         case op_dadd:
2705         case op_dsub:
2706         case op_dmul:
2707         case op_ddiv:
2708         case op_drem:
2709           pop_type (double_type);
2710           push_type_t (pop_type (double_type));
2711           break;
2712         case op_ineg:
2713         case op_i2b:
2714         case op_i2c:
2715         case op_i2s:
2716           push_type_t (pop_type (int_type));
2717           break;
2718         case op_lneg:
2719           push_type_t (pop_type (long_type));
2720           break;
2721         case op_fneg:
2722           push_type_t (pop_type (float_type));
2723           break;
2724         case op_dneg:
2725           push_type_t (pop_type (double_type));
2726           break;
2727         case op_iinc:
2728           get_variable (get_byte (), int_type);
2729           get_byte ();
2730           break;
2731         case op_i2l:
2732           pop_type (int_type);
2733           push_type (long_type);
2734           break;
2735         case op_i2f:
2736           pop_type (int_type);
2737           push_type (float_type);
2738           break;
2739         case op_i2d:
2740           pop_type (int_type);
2741           push_type (double_type);
2742           break;
2743         case op_l2i:
2744           pop_type (long_type);
2745           push_type (int_type);
2746           break;
2747         case op_l2f:
2748           pop_type (long_type);
2749           push_type (float_type);
2750           break;
2751         case op_l2d:
2752           pop_type (long_type);
2753           push_type (double_type);
2754           break;
2755         case op_f2i:
2756           pop_type (float_type);
2757           push_type (int_type);
2758           break;
2759         case op_f2l:
2760           pop_type (float_type);
2761           push_type (long_type);
2762           break;
2763         case op_f2d:
2764           pop_type (float_type);
2765           push_type (double_type);
2766           break;
2767         case op_d2i:
2768           pop_type (double_type);
2769           push_type (int_type);
2770           break;
2771         case op_d2l:
2772           pop_type (double_type);
2773           push_type (long_type);
2774           break;
2775         case op_d2f:
2776           pop_type (double_type);
2777           push_type (float_type);
2778           break;
2779         case op_lcmp:
2780           pop_type (long_type);
2781           pop_type (long_type);
2782           push_type (int_type);
2783           break;
2784         case op_fcmpl:
2785         case op_fcmpg:
2786           pop_type (float_type);
2787           pop_type (float_type);
2788           push_type (int_type);
2789           break;
2790         case op_dcmpl:
2791         case op_dcmpg:
2792           pop_type (double_type);
2793           pop_type (double_type);
2794           push_type (int_type);
2795           break;
2796         case op_ifeq:
2797         case op_ifne:
2798         case op_iflt:
2799         case op_ifge:
2800         case op_ifgt:
2801         case op_ifle:
2802           pop_type (int_type);
2803           push_jump (get_short ());
2804           break;
2805         case op_if_icmpeq:
2806         case op_if_icmpne:
2807         case op_if_icmplt:
2808         case op_if_icmpge:
2809         case op_if_icmpgt:
2810         case op_if_icmple:
2811           pop_type (int_type);
2812           pop_type (int_type);
2813           push_jump (get_short ());
2814           break;
2815         case op_if_acmpeq:
2816         case op_if_acmpne:
2817           pop_type (reference_type);
2818           pop_type (reference_type);
2819           push_jump (get_short ());
2820           break;
2821         case op_goto:
2822           push_jump (get_short ());
2823           invalidate_pc ();
2824           break;
2825         case op_jsr:
2826           handle_jsr_insn (get_short ());
2827           break;
2828         case op_ret:
2829           handle_ret_insn (get_byte ());
2830           break;
2831         case op_tableswitch:
2832           {
2833             int i;
2834             jint low, high;
2835             pop_type (int_type);
2836             skip_padding ();
2837             push_jump (get_int ());
2838             low = get_int ();
2839             high = get_int ();
2840             /* Already checked LOW -vs- HIGH.  */
2841             for (i = low; i <= high; ++i)
2842               push_jump (get_int ());
2843             invalidate_pc ();
2844           }
2845           break;
2846
2847         case op_lookupswitch:
2848           {
2849             int i;
2850             jint npairs, lastkey;
2851
2852             pop_type (int_type);
2853             skip_padding ();
2854             push_jump (get_int ());
2855             npairs = get_int ();
2856             /* Already checked NPAIRS >= 0.  */
2857             lastkey = 0;
2858             for (i = 0; i < npairs; ++i)
2859               {
2860                 jint key = get_int ();
2861                 if (i > 0 && key <= lastkey)
2862                   verify_fail_pc ("lookupswitch pairs unsorted", vfr->start_PC);
2863                 lastkey = key;
2864                 push_jump (get_int ());
2865               }
2866             invalidate_pc ();
2867           }
2868           break;
2869         case op_ireturn:
2870           check_return_type (pop_type (int_type));
2871           invalidate_pc ();
2872           break;
2873         case op_lreturn:
2874           check_return_type (pop_type (long_type));
2875           invalidate_pc ();
2876           break;
2877         case op_freturn:
2878           check_return_type (pop_type (float_type));
2879           invalidate_pc ();
2880           break;
2881         case op_dreturn:
2882           check_return_type (pop_type (double_type));
2883           invalidate_pc ();
2884           break;
2885         case op_areturn:
2886           check_return_type (pop_init_ref (reference_type));
2887           invalidate_pc ();
2888           break;
2889         case op_return:
2890           /* We only need to check this when the return type is void,
2891              because all instance initializers return void.  We also
2892              need to special-case Object constructors, as they can't
2893              call a superclass <init>.  */
2894           if (this_is_init && vfr->current_class != vfy_object_type ())
2895             state_check_this_initialized (vfr->current_state);
2896           check_return_type (make_type (void_type));
2897           invalidate_pc ();
2898           break;
2899         case op_getstatic:
2900           push_type_t (check_field_constant (get_ushort (), NULL, false));
2901           break;
2902         case op_putstatic:
2903           pop_type_t (check_field_constant (get_ushort (), NULL, false));
2904           break;
2905         case op_getfield:
2906           {
2907             type klass;
2908             type field = check_field_constant (get_ushort (), &klass, false);
2909             pop_type_t (klass);
2910             push_type_t (field);
2911           }
2912           break;
2913         case op_putfield:
2914           {
2915             type klass;
2916             type field = check_field_constant (get_ushort (), &klass, true);
2917             pop_type_t (field);
2918             pop_type_t (klass);
2919           }
2920           break;
2921
2922         case op_invokevirtual:
2923         case op_invokespecial:
2924         case op_invokestatic:
2925         case op_invokeinterface:
2926           {
2927             vfy_string method_name, method_signature;
2928             const char *namec;
2929             int i, arg_count;
2930             type rt;
2931             bool is_init = false;
2932
2933             type class_type
2934               = check_method_constant (get_ushort (),
2935                                        opcode == op_invokeinterface,
2936                                        &method_name,
2937                                        &method_signature);
2938             /* NARGS is only used when we're processing
2939                invokeinterface.  It is simplest for us to compute it
2940                here and then verify it later.  */
2941             int nargs = 0;
2942             if (opcode == op_invokeinterface)
2943               {
2944                 nargs = get_byte ();
2945                 if (get_byte () != 0)
2946                   verify_fail ("invokeinterface dummy byte is wrong");
2947               }
2948
2949             namec = vfy_string_bytes (method_name);
2950
2951             if (vfy_strings_equal (method_name, vfy_init_name()))
2952               {
2953                 is_init = true;
2954                 if (opcode != op_invokespecial)
2955                   verify_fail ("can't invoke <init>");
2956               }
2957             else if (namec[0] == '<')
2958               verify_fail ("can't invoke method starting with `<'");
2959
2960             arg_count = vfy_count_arguments (method_signature);
2961             {
2962               /* Pop arguments and check types.  */
2963               type *arg_types = (type *) vfy_alloc (arg_count * sizeof (type));
2964
2965               compute_argument_types (method_signature, arg_types);
2966               for (i = arg_count - 1; i >= 0; --i)
2967                 {
2968                   /* This is only used for verifying the byte for
2969                      invokeinterface.  */
2970                   nargs -= type_depth (&arg_types[i]);
2971                   pop_init_ref_t (arg_types[i]);
2972                 }
2973
2974               vfy_free (arg_types);
2975             }
2976
2977             if (opcode == op_invokeinterface
2978                 && nargs != 1)
2979               verify_fail ("wrong argument count for invokeinterface");
2980
2981             if (opcode != op_invokestatic)
2982               {
2983                 type raw;
2984                 type t = class_type;
2985                 if (is_init)
2986                   {
2987                     /* In this case the PC doesn't matter.  */
2988                     type_set_uninitialized (&t, UNINIT);
2989                     /* FIXME: check to make sure that the <init>
2990                        call is to the right class.
2991                        It must either be super or an exact class
2992                        match.  */
2993                   }
2994                 raw = pop_raw ();
2995                 if (! types_compatible (&t, &raw))
2996                   verify_fail ("incompatible type on stack");
2997
2998                 if (is_init)
2999                   state_set_initialized (vfr->current_state,
3000                     type_get_pc (&raw), vfr->current_method->max_locals);
3001               }
3002
3003             rt = compute_return_type (method_signature);
3004             if (! type_isvoid (&rt))
3005               push_type_t (rt);
3006           }
3007           break;
3008
3009         case op_new:
3010           {
3011             type t = check_class_constant (get_ushort ());
3012             if (type_isarray (&t) || type_isinterface (&t)
3013                 || type_isabstract (&t))
3014               verify_fail ("type is array, interface, or abstract");
3015             type_set_uninitialized (&t, vfr->start_PC);
3016             push_type_t (t);
3017           }
3018           break;
3019
3020         case op_newarray:
3021           {
3022             int atype = get_byte ();
3023             type t;
3024             /* We intentionally have chosen constants to make this
3025                valid.  */
3026             if (atype < boolean_type || atype > long_type)
3027               verify_fail_pc ("type not primitive", vfr->start_PC);
3028             pop_type (int_type);
3029             init_type_from_class (&t, construct_primitive_array_type (atype));
3030             push_type_t (t);
3031           }
3032           break;
3033         case op_anewarray:
3034           {
3035             type t;
3036             pop_type (int_type);
3037             t = check_class_constant (get_ushort ());
3038             push_type_t (type_to_array (&t));
3039           }
3040           break;
3041         case op_arraylength:
3042           {
3043             type t = pop_init_ref (reference_type);
3044             if (! type_isarray (&t) && ! type_isnull (&t))
3045               verify_fail ("array type expected");
3046             push_type (int_type);
3047           }
3048           break;
3049         case op_athrow:
3050           pop_type_t (make_type_from_class (vfy_throwable_type ()));
3051           invalidate_pc ();
3052           break;
3053         case op_checkcast:
3054           pop_init_ref (reference_type);
3055           push_type_t (check_class_constant (get_ushort ()));
3056           break;
3057         case op_instanceof:
3058           pop_init_ref (reference_type);
3059           check_class_constant (get_ushort ());
3060           push_type (int_type);
3061           break;
3062         case op_monitorenter:
3063           pop_init_ref (reference_type);
3064           break;
3065         case op_monitorexit:
3066           pop_init_ref (reference_type);
3067           break;
3068         case op_wide:
3069           {
3070             switch (get_byte ())
3071               {
3072               case op_iload:
3073                 push_type_t (get_variable (get_ushort (), int_type));
3074                 break;
3075               case op_lload:
3076                 push_type_t (get_variable (get_ushort (), long_type));
3077                 break;
3078               case op_fload:
3079                 push_type_t (get_variable (get_ushort (), float_type));
3080                 break;
3081               case op_dload:
3082                 push_type_t (get_variable (get_ushort (), double_type));
3083                 break;
3084               case op_aload:
3085                 push_type_t (get_variable (get_ushort (), reference_type));
3086                 break;
3087               case op_istore:
3088                 set_variable (get_ushort (), pop_type (int_type));
3089                 break;
3090               case op_lstore:
3091                 set_variable (get_ushort (), pop_type (long_type));
3092                 break;
3093               case op_fstore:
3094                 set_variable (get_ushort (), pop_type (float_type));
3095                 break;
3096               case op_dstore:
3097                 set_variable (get_ushort (), pop_type (double_type));
3098                 break;
3099               case op_astore:
3100                 set_variable (get_ushort (), pop_init_ref (reference_type));
3101                 break;
3102               case op_ret:
3103                 handle_ret_insn (get_short ());
3104                 break;
3105               case op_iinc:
3106                 get_variable (get_ushort (), int_type);
3107                 get_short ();
3108                 break;
3109               default:
3110                 verify_fail_pc ("unrecognized wide instruction", vfr->start_PC);
3111               }
3112           }
3113           break;
3114         case op_multianewarray:
3115           {
3116             int i;
3117             type atype = check_class_constant (get_ushort ());
3118             int dim = get_byte ();
3119             if (dim < 1)
3120               verify_fail_pc ("too few dimensions to multianewarray", vfr->start_PC);
3121             type_verify_dimensions (&atype, dim);
3122             for (i = 0; i < dim; ++i)
3123               pop_type (int_type);
3124             push_type_t (atype);
3125           }
3126           break;
3127         case op_ifnull:
3128         case op_ifnonnull:
3129           pop_type (reference_type);
3130           push_jump (get_short ());
3131           break;
3132         case op_goto_w:
3133           push_jump (get_int ());
3134           invalidate_pc ();
3135           break;
3136         case op_jsr_w:
3137           handle_jsr_insn (get_int ());
3138           break;
3139
3140         default:
3141           /* Unrecognized opcode.  */
3142           verify_fail_pc ("unrecognized instruction in verify_instructions_0",
3143                        vfr->start_PC);
3144         }
3145     }
3146 }
3147
3148 /* This turns a `type' into something suitable for use by the type map
3149    in the other parts of the compiler.  In particular, reference types
3150    are mapped to Object, primitive types are unchanged, and other
3151    types are mapped using special functions declared in verify.h.  */
3152 static vfy_jclass
3153 collapse_type (type *t)
3154 {
3155   switch (t->key)
3156     {
3157     case void_type:
3158     case boolean_type:
3159     case char_type:
3160     case float_type:
3161     case double_type:
3162     case byte_type:
3163     case short_type:
3164     case int_type:
3165     case long_type:
3166       return vfy_get_primitive_type (t->key);
3167
3168     case unsuitable_type:
3169     case continuation_type:
3170       return vfy_unsuitable_type ();
3171
3172     case return_address_type:
3173       return vfy_return_address_type ();
3174
3175     case null_type:
3176       return vfy_null_type ();
3177
3178     case reference_type:
3179     case uninitialized_reference_type:
3180       return vfy_object_type ();
3181     }
3182
3183   gcc_unreachable ();
3184 }
3185
3186 static void
3187 verify_instructions (void)
3188 {
3189   int i;
3190
3191   branch_prepass ();
3192   verify_instructions_0 ();
3193
3194   /* Now tell the rest of the compiler about the types we've found.  */
3195   for (i = 0; i < vfr->current_method->code_length; ++i)
3196     {
3197       int j, slot;
3198       struct state *curr;
3199
3200       if ((vfr->flags[i] & FLAG_INSN_SEEN) != 0)
3201         vfy_note_instruction_seen (i);
3202
3203       if (! vfr->states[i])
3204         continue;
3205
3206       curr = vfr->states[i]->val;
3207       vfy_note_stack_depth (vfr->current_method, i, curr->stackdepth);
3208
3209       /* Tell the compiler about each local variable.  */
3210       for (j = 0; j < vfr->current_method->max_locals; ++j)
3211         vfy_note_local_type (vfr->current_method, i, j,
3212                              collapse_type (&curr->locals[j]));
3213       /* Tell the compiler about each stack slot.  */
3214       for (slot = j = 0; j < curr->stacktop; ++j, ++slot)
3215         {
3216           vfy_note_stack_type (vfr->current_method, i, slot,
3217                                collapse_type (&curr->stack[j]));
3218           if (type_iswide (&curr->stack[j]))
3219             {
3220               ++slot;
3221               vfy_note_stack_type (vfr->current_method, i, slot,
3222                                    vfy_unsuitable_type ());
3223             }
3224         }
3225       gcc_assert (slot == curr->stackdepth);
3226     }
3227 }
3228
3229 static void
3230 make_verifier_context (vfy_method *m)
3231 {
3232   vfr = (verifier_context *) vfy_alloc (sizeof (struct verifier_context));
3233
3234   vfr->current_method = m;
3235   vfr->bytecode = vfy_get_bytecode (m);
3236   vfr->exception = vfy_get_exceptions (m);
3237   vfr->current_class = m->defining_class;
3238
3239   vfr->states = NULL;
3240   vfr->flags = NULL;
3241   vfr->utf8_list = NULL;
3242   vfr->isect_list = NULL;
3243 }
3244
3245 static void
3246 free_verifier_context (void)
3247 {
3248   vfy_string_list *utf8_list;
3249   ref_intersection *isect_list;
3250
3251   if (vfr->flags)
3252     vfy_free (vfr->flags);
3253
3254   utf8_list = vfr->utf8_list;
3255   while (utf8_list != NULL)
3256     {
3257       vfy_string_list *n = utf8_list->next;
3258       vfy_free (utf8_list);
3259       utf8_list = n;
3260     }
3261
3262   isect_list = vfr->isect_list;
3263   while (isect_list != NULL)
3264     {
3265       ref_intersection *next = isect_list->alloc_next;
3266       vfy_free (isect_list);
3267       isect_list = next;
3268     }
3269
3270   if (vfr->states != NULL)
3271     {
3272       int i;
3273       for (i = 0; i < vfr->current_method->code_length; ++i)
3274         {
3275           state_list *iter = vfr->states[i];
3276           while (iter != NULL)
3277             {
3278               state_list *next = iter->next;
3279               free_state (iter->val);
3280               vfy_free (iter->val);
3281               vfy_free (iter);
3282               iter = next;
3283             }
3284         }
3285       vfy_free (vfr->states);
3286     }
3287
3288   vfy_free (vfr);
3289 }
3290
3291 int
3292 verify_method (vfy_method *meth)
3293 {
3294   debug_print ("verify_method (%s) %i\n", vfy_string_bytes (meth->name),
3295                meth->code_length);
3296
3297   if (vfr != NULL)
3298     verify_fail ("verifier re-entered");
3299
3300   make_verifier_context (meth);
3301   verify_instructions ();
3302   free_verifier_context ();
3303   vfr = NULL;
3304
3305   return 1;
3306 }