libjava/verify.cc

   1 // defineclass.cc - defining a class from .class format.
   2
   3 /* Copyright (C) 2001  Free Software Foundation
   4
   5    This file is part of libgcj.
   6
   7 This software is copyrighted work licensed under the terms of the
   8 Libgcj License.  Please consult the file "LIBGCJ_LICENSE" for
   9 details.  */
  10
  11 // Written by Tom Tromey <tromey@redhat.com>
  12
  13 // Define VERIFY_DEBUG to enable debugging output.
  14
  15 #include <config.h>
  16
  17 #include <jvm.h>
  18 #include <gcj/cni.h>
  19 #include <java-insns.h>
  20 #include <java-interp.h>
  21
  22 #ifdef INTERPRETER
  23
  24 #include <java/lang/Class.h>
  25 #include <java/lang/VerifyError.h>
  26 #include <java/lang/Throwable.h>
  27 #include <java/lang/reflect/Modifier.h>
  28 #include <java/lang/StringBuffer.h>
  29
  30 #ifdef VERIFY_DEBUG
  31 #include <stdio.h>
  32 #endif /* VERIFY_DEBUG */
  33
  34 // TO DO
  35 // * read more about when classes must be loaded
  36 // * class loader madness
  37 // * Lots and lots of debugging and testing
  38 // * type representation is still ugly.  look for the big switches
  39 // * at least one GC problem :-(
  40
  41
  42 // This is global because __attribute__ doesn't seem to work on static
  43 // methods.
  44 static void verify_fail (char *msg, jint pc = -1)
  45   __attribute__ ((__noreturn__));
  46
  47 static void debug_print (const char *fmt, ...)
  48   __attribute__ ((format (printf, 1, 2)));
  49
  50 static inline void
  51 debug_print (const char *fmt, ...)
  52 {
  53 #ifdef VERIFY_DEBUG
  54   va_list ap;
  55   va_start (ap, fmt);
  56   vfprintf (stderr, fmt, ap);
  57   va_end (ap);
  58 #endif /* VERIFY_DEBUG */
  59 }
  60
  61 class _Jv_BytecodeVerifier
  62 {
  63 private:
  64
  65   static const int FLAG_INSN_START = 1;
  66   static const int FLAG_BRANCH_TARGET = 2;
  67   static const int FLAG_JSR_TARGET = 4;
  68
  69   struct state;
  70   struct type;
  71   struct subr_info;
  72   struct linked_utf8;
  73
  74   // The current PC.
  75   int PC;
  76   // The PC corresponding to the start of the current instruction.
  77   int start_PC;
  78
  79   // The current state of the stack, locals, etc.
  80   state *current_state;
  81
  82   // We store the state at branch targets, for merging.  This holds
  83   // such states.
  84   state **states;
  85
  86   // We keep a linked list of all the PCs which we must reverify.
  87   // The link is done using the PC values.  This is the head of the
  88   // list.
  89   int next_verify_pc;
  90
  91   // We keep some flags for each instruction.  The values are the
  92   // FLAG_* constants defined above.
  93   char *flags;
  94
  95   // We need to keep track of which instructions can call a given
  96   // subroutine.  FIXME: this is inefficient.  We keep a linked list
  97   // of all calling `jsr's at at each jsr target.
  98   subr_info **jsr_ptrs;
  99
 100   // The current top of the stack, in terms of slots.
 101   int stacktop;
 102   // The current depth of the stack.  This will be larger than
 103   // STACKTOP when wide types are on the stack.
 104   int stackdepth;
 105
 106   // The bytecode itself.
 107   unsigned char *bytecode;
 108   // The exceptions.
 109   _Jv_InterpException *exception;
 110
 111   // Defining class.
 112   jclass current_class;
 113   // This method.
 114   _Jv_InterpMethod *current_method;
 115
 116   // A linked list of utf8 objects we allocate.  This is really ugly,
 117   // but without this our utf8 objects would be collected.
 118   linked_utf8 *utf8_list;
 119
 120   struct linked_utf8
 121   {
 122     _Jv_Utf8Const *val;
 123     linked_utf8 *next;
 124   };
 125
 126   _Jv_Utf8Const *make_utf8_const (char *s, int len)
 127   {
 128     _Jv_Utf8Const *val = _Jv_makeUtf8Const (s, len);
 129     _Jv_Utf8Const *r = (_Jv_Utf8Const *) _Jv_Malloc (sizeof (_Jv_Utf8Const)
 130                                                      + val->length
 131                                                      + 1);
 132     r->length = val->length;
 133     r->hash = val->hash;
 134     memcpy (r->data, val->data, val->length + 1);
 135
 136     linked_utf8 *lu = (linked_utf8 *) _Jv_Malloc (sizeof (linked_utf8));
 137     lu->val = r;
 138     lu->next = utf8_list;
 139     utf8_list = lu;
 140
 141     return r;
 142   }
 143
 144   // This enum holds a list of tags for all the different types we
 145   // need to handle.  Reference types are treated specially by the
 146   // type class.
 147   enum type_val
 148   {
 149     void_type,
 150
 151     // The values for primitive types are chosen to correspond to values
 152     // specified to newarray.
 153     boolean_type = 4,
 154     char_type = 5,
 155     float_type = 6,
 156     double_type = 7,
 157     byte_type = 8,
 158     short_type = 9,
 159     int_type = 10,
 160     long_type = 11,
 161
 162     // Used when overwriting second word of a double or long in the
 163     // local variables.  Also used after merging local variable states
 164     // to indicate an unusable value.
 165     unsuitable_type,
 166     return_address_type,
 167     continuation_type,
 168
 169     // There is an obscure special case which requires us to note when
 170     // a local variable has not been used by a subroutine.  See
 171     // push_jump_merge for more information.
 172     unused_by_subroutine_type,
 173
 174     // Everything after `reference_type' must be a reference type.
 175     reference_type,
 176     null_type,
 177     unresolved_reference_type,
 178     uninitialized_reference_type,
 179     uninitialized_unresolved_reference_type
 180   };
 181
 182   // Return the type_val corresponding to a primitive signature
 183   // character.  For instance `I' returns `int.class'.
 184   static type_val get_type_val_for_signature (jchar sig)
 185   {
 186     type_val rt;
 187     switch (sig)
 188       {
 189       case 'Z':
 190         rt = boolean_type;
 191         break;
 192       case 'B':
 193         rt = byte_type;
 194         break;
 195       case 'C':
 196         rt = char_type;
 197         break;
 198       case 'S':
 199         rt = short_type;
 200         break;
 201       case 'I':
 202         rt = int_type;
 203         break;
 204       case 'J':
 205         rt = long_type;
 206         break;
 207       case 'F':
 208         rt = float_type;
 209         break;
 210       case 'D':
 211         rt = double_type;
 212         break;
 213       case 'V':
 214         rt = void_type;
 215         break;
 216       default:
 217         verify_fail ("invalid signature");
 218       }
 219     return rt;
 220   }
 221
 222   // Return the type_val corresponding to a primitive class.
 223   static type_val get_type_val_for_signature (jclass k)
 224   {
 225     return get_type_val_for_signature ((jchar) k->method_count);
 226   }
 227
 228   // This is like _Jv_IsAssignableFrom, but it works even if SOURCE or
 229   // TARGET haven't been prepared.
 230   static bool is_assignable_from_slow (jclass target, jclass source)
 231   {
 232     // This will terminate when SOURCE==Object.
 233     while (true)
 234       {
 235         if (source == target)
 236           return true;
 237
 238         if (target->isPrimitive () || source->isPrimitive ())
 239           return false;
 240
 241         // _Jv_IsAssignableFrom can handle a target which is an
 242         // interface even if it hasn't been prepared.
 243         if ((target->state > JV_STATE_LINKED || target->isInterface ())
 244             && source->state > JV_STATE_LINKED)
 245           return _Jv_IsAssignableFrom (target, source);
 246
 247         if (target->isArray ())
 248           {
 249             if (! source->isArray ())
 250               return false;
 251             target = target->getComponentType ();
 252             source = source->getComponentType ();
 253           }
 254         else if (target->isInterface ())
 255           {
 256             for (int i = 0; i < source->interface_count; ++i)
 257               {
 258                 // We use a recursive call because we also need to
 259                 // check superinterfaces.
 260                 if (is_assignable_from_slow (target, source->interfaces[i]))
 261                     return true;
 262               }
 263             return false;
 264           }
 265         else if (target == &java::lang::Object::class$)
 266           return true;
 267         else if (source->isInterface ()
 268                  || source == &java::lang::Object::class$)
 269           return false;
 270         else
 271           source = source->getSuperclass ();
 272       }
 273   }
 274
 275   // This is used to keep track of which `jsr's correspond to a given
 276   // jsr target.
 277   struct subr_info
 278   {
 279     // PC of the instruction just after the jsr.
 280     int pc;
 281     // Link.
 282     subr_info *next;
 283   };
 284
 285   // The `type' class is used to represent a single type in the
 286   // verifier.
 287   struct type
 288   {
 289     // The type.
 290     type_val key;
 291     // Some associated data.
 292     union
 293     {
 294       // For a resolved reference type, this is a pointer to the class.
 295       jclass klass;
 296       // For other reference types, this it the name of the class.
 297       _Jv_Utf8Const *name;
 298     } data;
 299     // This is used when constructing a new object.  It is the PC of the
 300     // `new' instruction which created the object.  We use the special
 301     // value -2 to mean that this is uninitialized, and the special
 302     // value -1 for the case where the current method is itself the
 303     // <init> method.
 304     int pc;
 305
 306     static const int UNINIT = -2;
 307     static const int SELF = -1;
 308
 309     // Basic constructor.
 310     type ()
 311     {
 312       key = unsuitable_type;
 313       data.klass = NULL;
 314       pc = UNINIT;
 315     }
 316
 317     // Make a new instance given the type tag.  We assume a generic
 318     // `reference_type' means Object.
 319     type (type_val k)
 320     {
 321       key = k;
 322       data.klass = NULL;
 323       if (key == reference_type)
 324         data.klass = &java::lang::Object::class$;
 325       pc = UNINIT;
 326     }
 327
 328     // Make a new instance given a class.
 329     type (jclass klass)
 330     {
 331       key = reference_type;
 332       data.klass = klass;
 333       pc = UNINIT;
 334     }
 335
 336     // Make a new instance given the name of a class.
 337     type (_Jv_Utf8Const *n)
 338     {
 339       key = unresolved_reference_type;
 340       data.name = n;
 341       pc = UNINIT;
 342     }
 343
 344     // Copy constructor.
 345     type (const type &t)
 346     {
 347       key = t.key;
 348       data = t.data;
 349       pc = t.pc;
 350     }
 351
 352     // These operators are required because libgcj can't link in
 353     // -lstdc++.
 354     void *operator new[] (size_t bytes)
 355     {
 356       return _Jv_Malloc (bytes);
 357     }
 358
 359     void operator delete[] (void *mem)
 360     {
 361       _Jv_Free (mem);
 362     }
 363
 364     type& operator= (type_val k)
 365     {
 366       key = k;
 367       data.klass = NULL;
 368       pc = UNINIT;
 369       return *this;
 370     }
 371
 372     type& operator= (const type& t)
 373     {
 374       key = t.key;
 375       data = t.data;
 376       pc = t.pc;
 377       return *this;
 378     }
 379
 380     // Promote a numeric type.
 381     type &promote ()
 382     {
 383       if (key == boolean_type || key == char_type
 384           || key == byte_type || key == short_type)
 385         key = int_type;
 386       return *this;
 387     }
 388
 389     // If *THIS is an unresolved reference type, resolve it.
 390     void resolve ()
 391     {
 392       if (key != unresolved_reference_type
 393           && key != uninitialized_unresolved_reference_type)
 394         return;
 395
 396       // FIXME: class loader
 397       using namespace java::lang;
 398       // We might see either kind of name.  Sigh.
 399       if (data.name->data[0] == 'L'
 400           && data.name->data[data.name->length - 1] == ';')
 401         data.klass = _Jv_FindClassFromSignature (data.name->data, NULL);
 402       else
 403         data.klass = Class::forName (_Jv_NewStringUtf8Const (data.name),
 404                                      false, NULL);
 405       key = (key == unresolved_reference_type
 406              ? reference_type
 407              : uninitialized_reference_type);
 408     }
 409
 410     // Mark this type as the uninitialized result of `new'.
 411     void set_uninitialized (int npc)
 412     {
 413       if (key == reference_type)
 414         key = uninitialized_reference_type;
 415       else if (key == unresolved_reference_type)
 416         key = uninitialized_unresolved_reference_type;
 417       else
 418         verify_fail ("internal error in type::uninitialized");
 419       pc = npc;
 420     }
 421
 422     // Mark this type as now initialized.
 423     void set_initialized (int npc)
 424     {
 425       if (npc != UNINIT && pc == npc
 426           && (key == uninitialized_reference_type
 427               || key == uninitialized_unresolved_reference_type))
 428         {
 429           key = (key == uninitialized_reference_type
 430                  ? reference_type
 431                  : unresolved_reference_type);
 432           pc = UNINIT;
 433         }
 434     }
 435
 436
 437     // Return true if an object of type K can be assigned to a variable
 438     // of type *THIS.  Handle various special cases too.  Might modify
 439     // *THIS or K.  Note however that this does not perform numeric
 440     // promotion.
 441     bool compatible (type &k)
 442     {
 443       // Any type is compatible with the unsuitable type.
 444       if (key == unsuitable_type)
 445         return true;
 446
 447       if (key < reference_type || k.key < reference_type)
 448         return key == k.key;
 449
 450       // The `null' type is convertible to any reference type.
 451       // FIXME: is this correct for THIS?
 452       if (key == null_type || k.key == null_type)
 453         return true;
 454
 455       // Any reference type is convertible to Object.  This is a special
 456       // case so we don't need to unnecessarily resolve a class.
 457       if (key == reference_type
 458           && data.klass == &java::lang::Object::class$)
 459         return true;
 460
 461       // An initialized type and an uninitialized type are not
 462       // compatible.
 463       if (isinitialized () != k.isinitialized ())
 464         return false;
 465
 466       // Two uninitialized objects are compatible if either:
 467       // * The PCs are identical, or
 468       // * One PC is UNINIT.
 469       if (! isinitialized ())
 470         {
 471           if (pc != k.pc && pc != UNINIT && k.pc != UNINIT)
 472             return false;
 473         }
 474
 475       // Two unresolved types are equal if their names are the same.
 476       if (! isresolved ()
 477           && ! k.isresolved ()
 478           && _Jv_equalUtf8Consts (data.name, k.data.name))
 479         return true;
 480
 481       // We must resolve both types and check assignability.
 482       resolve ();
 483       k.resolve ();
 484       return is_assignable_from_slow (data.klass, k.data.klass);
 485     }
 486
 487     bool isvoid () const
 488     {
 489       return key == void_type;
 490     }
 491
 492     bool iswide () const
 493     {
 494       return key == long_type || key == double_type;
 495     }
 496
 497     // Return number of stack or local variable slots taken by this
 498     // type.
 499     int depth () const
 500     {
 501       return iswide () ? 2 : 1;
 502     }
 503
 504     bool isarray () const
 505     {
 506       // We treat null_type as not an array.  This is ok based on the
 507       // current uses of this method.
 508       if (key == reference_type)
 509         return data.klass->isArray ();
 510       else if (key == unresolved_reference_type)
 511         return data.name->data[0] == '[';
 512       return false;
 513     }
 514
 515     bool isinterface ()
 516     {
 517       resolve ();
 518       if (key != reference_type)
 519         return false;
 520       return data.klass->isInterface ();
 521     }
 522
 523     bool isabstract ()
 524     {
 525       resolve ();
 526       if (key != reference_type)
 527         return false;
 528       using namespace java::lang::reflect;
 529       return Modifier::isAbstract (data.klass->getModifiers ());
 530     }
 531
 532     // Return the element type of an array.
 533     type element_type ()
 534     {
 535       // FIXME: maybe should do string manipulation here.
 536       resolve ();
 537       if (key != reference_type)
 538         verify_fail ("programmer error in type::element_type()");
 539
 540       jclass k = data.klass->getComponentType ();
 541       if (k->isPrimitive ())
 542         return type (get_type_val_for_signature (k));
 543       return type (k);
 544     }
 545
 546     // Return the array type corresponding to an initialized
 547     // reference.  We could expand this to work for other kinds of
 548     // types, but currently we don't need to.
 549     type to_array ()
 550     {
 551       // Resolving isn't ideal, because it might force us to load
 552       // another class, but it's easy.  FIXME?
 553       if (key == unresolved_reference_type)
 554         resolve ();
 555
 556       if (key == reference_type)
 557         return type (_Jv_GetArrayClass (data.klass,
 558                                         data.klass->getClassLoader ()));
 559       else
 560         verify_fail ("internal error in type::to_array()");
 561     }
 562
 563     bool isreference () const
 564     {
 565       return key >= reference_type;
 566     }
 567
 568     int get_pc () const
 569     {
 570       return pc;
 571     }
 572
 573     bool isinitialized () const
 574     {
 575       return (key == reference_type
 576               || key == null_type
 577               || key == unresolved_reference_type);
 578     }
 579
 580     bool isresolved () const
 581     {
 582       return (key == reference_type
 583               || key == null_type
 584               || key == uninitialized_reference_type);
 585     }
 586
 587     void verify_dimensions (int ndims)
 588     {
 589       // The way this is written, we don't need to check isarray().
 590       if (key == reference_type)
 591         {
 592           jclass k = data.klass;
 593           while (k->isArray () && ndims > 0)
 594             {
 595               k = k->getComponentType ();
 596               --ndims;
 597             }
 598         }
 599       else
 600         {
 601           // We know KEY == unresolved_reference_type.
 602           char *p = data.name->data;
 603           while (*p++ == '[' && ndims-- > 0)
 604             ;
 605         }
 606
 607       if (ndims > 0)
 608         verify_fail ("array type has fewer dimensions than required");
 609     }
 610
 611     // Merge OLD_TYPE into this.  On error throw exception.
 612     bool merge (type& old_type, bool local_semantics = false)
 613     {
 614       bool changed = false;
 615       bool refo = old_type.isreference ();
 616       bool refn = isreference ();
 617       if (refo && refn)
 618         {
 619           if (old_type.key == null_type)
 620             ;
 621           else if (key == null_type)
 622             {
 623               *this = old_type;
 624               changed = true;
 625             }
 626           else if (isinitialized () != old_type.isinitialized ())
 627             verify_fail ("merging initialized and uninitialized types");
 628           else
 629             {
 630               if (! isinitialized ())
 631                 {
 632                   if (pc == UNINIT)
 633                     pc = old_type.pc;
 634                   else if (old_type.pc == UNINIT)
 635                     ;
 636                   else if (pc != old_type.pc)
 637                     verify_fail ("merging different uninitialized types");
 638                 }
 639
 640               if (! isresolved ()
 641                   && ! old_type.isresolved ()
 642                   && _Jv_equalUtf8Consts (data.name, old_type.data.name))
 643                 {
 644                   // Types are identical.
 645                 }
 646               else
 647                 {
 648                   resolve ();
 649                   old_type.resolve ();
 650
 651                   jclass k = data.klass;
 652                   jclass oldk = old_type.data.klass;
 653
 654                   int arraycount = 0;
 655                   while (k->isArray () && oldk->isArray ())
 656                     {
 657                       ++arraycount;
 658                       k = k->getComponentType ();
 659                       oldk = oldk->getComponentType ();
 660                     }
 661
 662                   // This loop will end when we hit Object.
 663                   while (true)
 664                     {
 665                       if (is_assignable_from_slow (k, oldk))
 666                         break;
 667                       k = k->getSuperclass ();
 668                       changed = true;
 669                     }
 670
 671                   if (changed)
 672                     {
 673                       while (arraycount > 0)
 674                         {
 675                           // FIXME: Class loader.
 676                           k = _Jv_GetArrayClass (k, NULL);
 677                           --arraycount;
 678                         }
 679                       data.klass = k;
 680                     }
 681                 }
 682             }
 683         }
 684       else if (refo || refn || key != old_type.key)
 685         {
 686           if (local_semantics)
 687             {
 688               // If we're merging into an "unused" slot, then we
 689               // simply accept whatever we're merging from.
 690               if (key == unused_by_subroutine_type)
 691                 {
 692                   *this = old_type;
 693                   changed = true;
 694                 }
 695               else if (old_type.key == unused_by_subroutine_type)
 696                 {
 697                   // Do nothing.
 698                 }
 699               // If we already have an `unsuitable' type, then we
 700               // don't need to change again.
 701               else if (key != unsuitable_type)
 702                 {
 703                   key = unsuitable_type;
 704                   changed = true;
 705                 }
 706             }
 707           else
 708             verify_fail ("unmergeable type");
 709         }
 710       return changed;
 711     }
 712
 713 #ifdef VERIFY_DEBUG
 714     void print (void) const
 715     {
 716       char c = '?';
 717       switch (key)
 718         {
 719         case boolean_type: c = 'Z'; break;
 720         case byte_type: c = 'B'; break;
 721         case char_type: c = 'C'; break;
 722         case short_type: c = 'S'; break;
 723         case int_type: c = 'I'; break;
 724         case long_type: c = 'J'; break;
 725         case float_type: c = 'F'; break;
 726         case double_type: c = 'D'; break;
 727         case void_type: c = 'V'; break;
 728         case unsuitable_type: c = '-'; break;
 729         case return_address_type: c = 'r'; break;
 730         case continuation_type: c = '+'; break;
 731         case unused_by_subroutine_type: c = '_'; break;
 732         case reference_type: c = 'L'; break;
 733         case null_type: c = '@'; break;
 734         case unresolved_reference_type: c = 'l'; break;
 735         case uninitialized_reference_type: c = 'U'; break;
 736         case uninitialized_unresolved_reference_type: c = 'u'; break;
 737         }
 738       debug_print ("%c", c);
 739     }
 740 #endif /* VERIFY_DEBUG */
 741   };
 742
 743   // This class holds all the state information we need for a given
 744   // location.
 745   struct state
 746   {
 747     // Current top of stack.
 748     int stacktop;
 749     // Current stack depth.  This is like the top of stack but it
 750     // includes wide variable information.
 751     int stackdepth;
 752     // The stack.
 753     type *stack;
 754     // The local variables.
 755     type *locals;
 756     // This is used in subroutines to keep track of which local
 757     // variables have been accessed.
 758     bool *local_changed;
 759     // If not 0, then we are in a subroutine.  The value is the PC of
 760     // the subroutine's entry point.  We can use 0 as an exceptional
 761     // value because PC=0 can never be a subroutine.
 762     int subroutine;
 763     // This is used to keep a linked list of all the states which
 764     // require re-verification.  We use the PC to keep track.
 765     int next;
 766
 767     // INVALID marks a state which is not on the linked list of states
 768     // requiring reverification.
 769     static const int INVALID = -1;
 770     // NO_NEXT marks the state at the end of the reverification list.
 771     static const int NO_NEXT = -2;
 772
 773     state ()
 774     {
 775       stack = NULL;
 776       locals = NULL;
 777       local_changed = NULL;
 778     }
 779
 780     state (int max_stack, int max_locals)
 781     {
 782       stacktop = 0;
 783       stackdepth = 0;
 784       stack = new type[max_stack];
 785       for (int i = 0; i < max_stack; ++i)
 786         stack[i] = unsuitable_type;
 787       locals = new type[max_locals];
 788       local_changed = (bool *) _Jv_Malloc (sizeof (bool) * max_locals);
 789       for (int i = 0; i < max_locals; ++i)
 790         {
 791           locals[i] = unsuitable_type;
 792           local_changed[i] = false;
 793         }
 794       next = INVALID;
 795       subroutine = 0;
 796     }
 797
 798     state (const state *orig, int max_stack, int max_locals,
 799            bool ret_semantics = false)
 800     {
 801       stack = new type[max_stack];
 802       locals = new type[max_locals];
 803       local_changed = (bool *) _Jv_Malloc (sizeof (bool) * max_locals);
 804       copy (orig, max_stack, max_locals, ret_semantics);
 805       next = INVALID;
 806     }
 807
 808     ~state ()
 809     {
 810       if (stack)
 811         delete[] stack;
 812       if (locals)
 813         delete[] locals;
 814       if (local_changed)
 815         _Jv_Free (local_changed);
 816     }
 817
 818     void *operator new[] (size_t bytes)
 819     {
 820       return _Jv_Malloc (bytes);
 821     }
 822
 823     void operator delete[] (void *mem)
 824     {
 825       _Jv_Free (mem);
 826     }
 827
 828     void *operator new (size_t bytes)
 829     {
 830       return _Jv_Malloc (bytes);
 831     }
 832
 833     void operator delete (void *mem)
 834     {
 835       _Jv_Free (mem);
 836     }
 837
 838     void copy (const state *copy, int max_stack, int max_locals,
 839                bool ret_semantics = false)
 840     {
 841       stacktop = copy->stacktop;
 842       stackdepth = copy->stackdepth;
 843       subroutine = copy->subroutine;
 844       for (int i = 0; i < max_stack; ++i)
 845         stack[i] = copy->stack[i];
 846       for (int i = 0; i < max_locals; ++i)
 847         {
 848           // See push_jump_merge to understand this case.
 849           if (ret_semantics)
 850             locals[i] = type (copy->local_changed[i]
 851                               ? unsuitable_type
 852                               : unused_by_subroutine_type);
 853           else
 854             locals[i] = copy->locals[i];
 855           local_changed[i] = copy->local_changed[i];
 856         }
 857       // Don't modify `next'.
 858     }
 859
 860     // Modify this state to reflect entry to an exception handler.
 861     void set_exception (type t, int max_stack)
 862     {
 863       stackdepth = 1;
 864       stacktop = 1;
 865       stack[0] = t;
 866       for (int i = stacktop; i < max_stack; ++i)
 867         stack[i] = unsuitable_type;
 868
 869       // FIXME: subroutine handling?
 870     }
 871
 872     // Merge STATE into this state.  Destructively modifies this state.
 873     // Returns true if the new state was in fact changed.  Will throw an
 874     // exception if the states are not mergeable.
 875     bool merge (state *state_old, bool ret_semantics,
 876                 int max_locals)
 877     {
 878       bool changed = false;
 879
 880       // Merge subroutine states.  *THIS and *STATE_OLD must be in the
 881       // same subroutine.  Also, recursive subroutine calls must be
 882       // avoided.
 883       if (subroutine == state_old->subroutine)
 884         {
 885           // Nothing.
 886         }
 887       else if (subroutine == 0)
 888         {
 889           subroutine = state_old->subroutine;
 890           changed = true;
 891         }
 892       else
 893         verify_fail ("subroutines merged");
 894
 895       // Merge stacks.
 896       if (state_old->stacktop != stacktop)
 897         verify_fail ("stack sizes differ");
 898       for (int i = 0; i < state_old->stacktop; ++i)
 899         {
 900           if (stack[i].merge (state_old->stack[i]))
 901             changed = true;
 902         }
 903
 904       // Merge local variables.
 905       for (int i = 0; i < max_locals; ++i)
 906         {
 907           if (! ret_semantics || local_changed[i])
 908             {
 909               if (locals[i].merge (state_old->locals[i], true))
 910                 {
 911                   changed = true;
 912                   note_variable (i);
 913                 }
 914             }
 915
 916           // If we're in a subroutine, we must compute the union of
 917           // all the changed local variables.
 918           if (state_old->local_changed[i])
 919             note_variable (i);
 920         }
 921
 922       return changed;
 923     }
 924
 925     // Throw an exception if there is an uninitialized object on the
 926     // stack or in a local variable.  EXCEPTION_SEMANTICS controls
 927     // whether we're using backwards-branch or exception-handing
 928     // semantics.
 929     void check_no_uninitialized_objects (int max_locals,
 930                                          bool exception_semantics = false)
 931     {
 932       if (! exception_semantics)
 933         {
 934           for (int i = 0; i < stacktop; ++i)
 935             if (stack[i].isreference () && ! stack[i].isinitialized ())
 936               verify_fail ("uninitialized object on stack");
 937         }
 938
 939       for (int i = 0; i < max_locals; ++i)
 940         if (locals[i].isreference () && ! locals[i].isinitialized ())
 941           verify_fail ("uninitialized object in local variable");
 942     }
 943
 944     // Note that a local variable was modified.
 945     void note_variable (int index)
 946     {
 947       if (subroutine > 0)
 948         local_changed[index] = true;
 949     }
 950
 951     // Mark each `new'd object we know of that was allocated at PC as
 952     // initialized.
 953     void set_initialized (int pc, int max_locals)
 954     {
 955       for (int i = 0; i < stacktop; ++i)
 956         stack[i].set_initialized (pc);
 957       for (int i = 0; i < max_locals; ++i)
 958         locals[i].set_initialized (pc);
 959     }
 960
 961     // Return true if this state is the unmerged result of a `ret'.
 962     bool is_unmerged_ret_state (int max_locals) const
 963     {
 964       for (int i = 0; i < max_locals; ++i)
 965         {
 966           if (locals[i].key == unused_by_subroutine_type)
 967             return true;
 968         }
 969       return false;
 970     }
 971
 972 #ifdef VERIFY_DEBUG
 973     void print (const char *leader, int pc,
 974                 int max_stack, int max_locals) const
 975     {
 976       debug_print ("%s [%4d]:   [stack] ", leader, pc);
 977       int i;
 978       for (i = 0; i < stacktop; ++i)
 979         stack[i].print ();
 980       for (; i < max_stack; ++i)
 981         debug_print (".");
 982       debug_print ("    [local] ");
 983       for (i = 0; i < max_locals; ++i)
 984         locals[i].print ();
 985       debug_print ("   | %p\n", this);
 986     }
 987 #else
 988     inline void print (const char *, int, int, int) const
 989     {
 990     }
 991 #endif /* VERIFY_DEBUG */
 992   };
 993
 994   type pop_raw ()
 995   {
 996     if (current_state->stacktop <= 0)
 997       verify_fail ("stack empty", start_PC);
 998     type r = current_state->stack[--current_state->stacktop];
 999     current_state->stackdepth -= r.depth ();
1000     if (current_state->stackdepth < 0)
1001       verify_fail ("stack empty", start_PC);
1002     return r;
1003   }
1004
1005   type pop32 ()
1006   {
1007     type r = pop_raw ();
1008     if (r.iswide ())
1009       verify_fail ("narrow pop of wide type", start_PC);
1010     return r;
1011   }
1012
1013   type pop64 ()
1014   {
1015     type r = pop_raw ();
1016     if (! r.iswide ())
1017       verify_fail ("wide pop of narrow type", start_PC);
1018     return r;
1019   }
1020
1021   type pop_type (type match)
1022   {
1023     match.promote ();
1024     type t = pop_raw ();
1025     if (! match.compatible (t))
1026       verify_fail ("incompatible type on stack", start_PC);
1027     return t;
1028   }
1029
1030   // Pop a reference type or a return address.
1031   type pop_ref_or_return ()
1032   {
1033     type t = pop_raw ();
1034     if (! t.isreference () && t.key != return_address_type)
1035       verify_fail ("expected reference or return address on stack", start_PC);
1036     return t;
1037   }
1038
1039   void push_type (type t)
1040   {
1041     // If T is a numeric type like short, promote it to int.
1042     t.promote ();
1043
1044     int depth = t.depth ();
1045     if (current_state->stackdepth + depth > current_method->max_stack)
1046       verify_fail ("stack overflow");
1047     current_state->stack[current_state->stacktop++] = t;
1048     current_state->stackdepth += depth;
1049   }
1050
1051   void set_variable (int index, type t)
1052   {
1053     // If T is a numeric type like short, promote it to int.
1054     t.promote ();
1055
1056     int depth = t.depth ();
1057     if (index > current_method->max_locals - depth)
1058       verify_fail ("invalid local variable");
1059     current_state->locals[index] = t;
1060     current_state->note_variable (index);
1061
1062     if (depth == 2)
1063       {
1064         current_state->locals[index + 1] = continuation_type;
1065         current_state->note_variable (index + 1);
1066       }
1067     if (index > 0 && current_state->locals[index - 1].iswide ())
1068       {
1069         current_state->locals[index - 1] = unsuitable_type;
1070         // There's no need to call note_variable here.
1071       }
1072   }
1073
1074   type get_variable (int index, type t)
1075   {
1076     int depth = t.depth ();
1077     if (index > current_method->max_locals - depth)
1078       verify_fail ("invalid local variable", start_PC);
1079     if (! t.compatible (current_state->locals[index]))
1080       verify_fail ("incompatible type in local variable", start_PC);
1081     if (depth == 2)
1082       {
1083         type t (continuation_type);
1084         if (! current_state->locals[index + 1].compatible (t))
1085           verify_fail ("invalid local variable", start_PC);
1086       }
1087     return current_state->locals[index];
1088   }
1089
1090   // Make sure ARRAY is an array type and that its elements are
1091   // compatible with type ELEMENT.  Returns the actual element type.
1092   type require_array_type (type array, type element)
1093   {
1094     if (! array.isarray ())
1095       verify_fail ("array required");
1096
1097     type t = array.element_type ();
1098     if (! element.compatible (t))
1099       {
1100         // Special case for byte arrays, which must also be boolean
1101         // arrays.
1102         bool ok = true;
1103         if (element.key == byte_type)
1104           {
1105             type e2 (boolean_type);
1106             ok = e2.compatible (t);
1107           }
1108         if (! ok)
1109           verify_fail ("incompatible array element type");
1110       }
1111
1112     // Return T and not ELEMENT, because T might be specialized.
1113     return t;
1114   }
1115
1116   jint get_byte ()
1117   {
1118     if (PC >= current_method->code_length)
1119       verify_fail ("premature end of bytecode");
1120     return (jint) bytecode[PC++] & 0xff;
1121   }
1122
1123   jint get_ushort ()
1124   {
1125     jint b1 = get_byte ();
1126     jint b2 = get_byte ();
1127     return (jint) ((b1 << 8) | b2) & 0xffff;
1128   }
1129
1130   jint get_short ()
1131   {
1132     jint b1 = get_byte ();
1133     jint b2 = get_byte ();
1134     jshort s = (b1 << 8) | b2;
1135     return (jint) s;
1136   }
1137
1138   jint get_int ()
1139   {
1140     jint b1 = get_byte ();
1141     jint b2 = get_byte ();
1142     jint b3 = get_byte ();
1143     jint b4 = get_byte ();
1144     return (b1 << 24) | (b2 << 16) | (b3 << 8) | b4;
1145   }
1146
1147   int compute_jump (int offset)
1148   {
1149     int npc = start_PC + offset;
1150     if (npc < 0 || npc >= current_method->code_length)
1151       verify_fail ("branch out of range", start_PC);
1152     return npc;
1153   }
1154
1155   // Merge the indicated state into the state at the branch target and
1156   // schedule a new PC if there is a change.  If RET_SEMANTICS is
1157   // true, then we are merging from a `ret' instruction into the
1158   // instruction after a `jsr'.  This is a special case with its own
1159   // modified semantics.
1160   void push_jump_merge (int npc, state *nstate, bool ret_semantics = false)
1161   {
1162     bool changed = true;
1163     if (states[npc] == NULL)
1164       {
1165         // There's a weird situation here.  If are examining the
1166         // branch that results from a `ret', and there is not yet a
1167         // state available at the branch target (the instruction just
1168         // after the `jsr'), then we have to construct a special kind
1169         // of state at that point for future merging.  This special
1170         // state has the type `unused_by_subroutine_type' in each slot
1171         // which was not modified by the subroutine.
1172         states[npc] = new state (nstate, current_method->max_stack,
1173                                  current_method->max_locals, ret_semantics);
1174         debug_print ("== New state in push_jump_merge\n");
1175         states[npc]->print ("New", npc, current_method->max_stack,
1176                             current_method->max_locals);
1177       }
1178     else
1179       {
1180         debug_print ("== Merge states in push_jump_merge\n");
1181         nstate->print ("Frm", start_PC, current_method->max_stack,
1182                        current_method->max_locals);
1183         states[npc]->print (" To", npc, current_method->max_stack,
1184                             current_method->max_locals);
1185         changed = states[npc]->merge (nstate, ret_semantics,
1186                                       current_method->max_locals);
1187         states[npc]->print ("New", npc, current_method->max_stack,
1188                             current_method->max_locals);
1189       }
1190
1191     if (changed && states[npc]->next == state::INVALID)
1192       {
1193         // The merge changed the state, and the new PC isn't yet on our
1194         // list of PCs to re-verify.
1195         states[npc]->next = next_verify_pc;
1196         next_verify_pc = npc;
1197       }
1198   }
1199
1200   void push_jump (int offset)
1201   {
1202     int npc = compute_jump (offset);
1203     if (npc < PC)
1204       current_state->check_no_uninitialized_objects (current_method->max_locals);
1205     push_jump_merge (npc, current_state);
1206   }
1207
1208   void push_exception_jump (type t, int pc)
1209   {
1210     current_state->check_no_uninitialized_objects (current_method->max_locals,
1211                                                   true);
1212     state s (current_state, current_method->max_stack,
1213              current_method->max_locals);
1214     s.set_exception (t, current_method->max_stack);
1215     push_jump_merge (pc, &s);
1216   }
1217
1218   int pop_jump ()
1219   {
1220     int *prev_loc = &next_verify_pc;
1221     int npc = next_verify_pc;
1222     bool skipped = false;
1223
1224     while (npc != state::NO_NEXT)
1225       {
1226         // If the next available PC is an unmerged `ret' state, then
1227         // we aren't yet ready to handle it.  That's because we would
1228         // need all kind of special cases to do so.  So instead we
1229         // defer this jump until after we've processed it via a
1230         // fall-through.  This has to happen because the instruction
1231         // before this one must be a `jsr'.
1232         if (! states[npc]->is_unmerged_ret_state (current_method->max_locals))
1233           {
1234             *prev_loc = states[npc]->next;
1235             states[npc]->next = state::INVALID;
1236             return npc;
1237           }
1238
1239         skipped = true;
1240         prev_loc = &states[npc]->next;
1241         npc = states[npc]->next;
1242       }
1243
1244     // If we've skipped states and there is nothing else, that's a
1245     // bug.
1246     if (skipped)
1247       verify_fail ("pop_jump: can't happen");
1248     return state::NO_NEXT;
1249   }
1250
1251   void invalidate_pc ()
1252   {
1253     PC = state::NO_NEXT;
1254   }
1255
1256   void note_branch_target (int pc, bool is_jsr_target = false)
1257   {
1258     if (pc <= PC && ! (flags[pc] & FLAG_INSN_START))
1259       verify_fail ("branch not to instruction start");
1260     flags[pc] |= FLAG_BRANCH_TARGET;
1261     if (is_jsr_target)
1262       {
1263         // Record the jsr which called this instruction.
1264         subr_info *info = (subr_info *) _Jv_Malloc (sizeof (subr_info));
1265         info->pc = PC;
1266         info->next = jsr_ptrs[pc];
1267         jsr_ptrs[pc] = info;
1268         flags[pc] |= FLAG_JSR_TARGET;
1269       }
1270   }
1271
1272   void skip_padding ()
1273   {
1274     while ((PC % 4) > 0)
1275       if (get_byte () != 0)
1276         verify_fail ("found nonzero padding byte");
1277   }
1278
1279   // Return the subroutine to which the instruction at PC belongs.
1280   int get_subroutine (int pc)
1281   {
1282     if (states[pc] == NULL)
1283       return 0;
1284     return states[pc]->subroutine;
1285   }
1286
1287   // Do the work for a `ret' instruction.  INDEX is the index into the
1288   // local variables.
1289   void handle_ret_insn (int index)
1290   {
1291     get_variable (index, return_address_type);
1292
1293     int csub = current_state->subroutine;
1294     if (csub == 0)
1295       verify_fail ("no subroutine");
1296
1297     for (subr_info *subr = jsr_ptrs[csub]; subr != NULL; subr = subr->next)
1298       {
1299         // Temporarily modify the current state so it looks like we're
1300         // in the enclosing context.
1301         current_state->subroutine = get_subroutine (subr->pc);
1302         if (subr->pc < PC)
1303           current_state->check_no_uninitialized_objects (current_method->max_locals);
1304         push_jump_merge (subr->pc, current_state, true);
1305       }
1306
1307     current_state->subroutine = csub;
1308     invalidate_pc ();
1309   }
1310
1311   // We're in the subroutine SUB, calling a subroutine at DEST.  Make
1312   // sure this subroutine isn't already on the stack.
1313   void check_nonrecursive_call (int sub, int dest)
1314   {
1315     if (sub == 0)
1316       return;
1317     if (sub == dest)
1318       verify_fail ("recursive subroutine call");
1319     for (subr_info *info = jsr_ptrs[sub]; info != NULL; info = info->next)
1320       check_nonrecursive_call (get_subroutine (info->pc), dest);
1321   }
1322
1323   void handle_jsr_insn (int offset)
1324   {
1325     int npc = compute_jump (offset);
1326
1327     if (npc < PC)
1328       current_state->check_no_uninitialized_objects (current_method->max_locals);
1329     check_nonrecursive_call (current_state->subroutine, npc);
1330
1331     // Temporarily modify the current state so that it looks like we are
1332     // in the subroutine.
1333     push_type (return_address_type);
1334     int save = current_state->subroutine;
1335     current_state->subroutine = npc;
1336
1337     // Merge into the subroutine.
1338     push_jump_merge (npc, current_state);
1339
1340     // Undo our modifications.
1341     current_state->subroutine = save;
1342     pop_type (return_address_type);
1343   }
1344
1345   jclass construct_primitive_array_type (type_val prim)
1346   {
1347     jclass k = NULL;
1348     switch (prim)
1349       {
1350       case boolean_type:
1351         k = JvPrimClass (boolean);
1352         break;
1353       case char_type:
1354         k = JvPrimClass (char);
1355         break;
1356       case float_type:
1357         k = JvPrimClass (float);
1358         break;
1359       case double_type:
1360         k = JvPrimClass (double);
1361         break;
1362       case byte_type:
1363         k = JvPrimClass (byte);
1364         break;
1365       case short_type:
1366         k = JvPrimClass (short);
1367         break;
1368       case int_type:
1369         k = JvPrimClass (int);
1370         break;
1371       case long_type:
1372         k = JvPrimClass (long);
1373         break;
1374       default:
1375         verify_fail ("unknown type in construct_primitive_array_type");
1376       }
1377     k = _Jv_GetArrayClass (k, NULL);
1378     return k;
1379   }
1380
1381   // This pass computes the location of branch targets and also
1382   // instruction starts.
1383   void branch_prepass ()
1384   {
1385     flags = (char *) _Jv_Malloc (current_method->code_length);
1386     jsr_ptrs = (subr_info **) _Jv_Malloc (sizeof (subr_info *)
1387                                           * current_method->code_length);
1388
1389     for (int i = 0; i < current_method->code_length; ++i)
1390       {
1391         flags[i] = 0;
1392         jsr_ptrs[i] = NULL;
1393       }
1394
1395     bool last_was_jsr = false;
1396
1397     PC = 0;
1398     while (PC < current_method->code_length)
1399       {
1400         flags[PC] |= FLAG_INSN_START;
1401
1402         // If the previous instruction was a jsr, then the next
1403         // instruction is a branch target -- the branch being the
1404         // corresponding `ret'.
1405         if (last_was_jsr)
1406           note_branch_target (PC);
1407         last_was_jsr = false;
1408
1409         start_PC = PC;
1410         java_opcode opcode = (java_opcode) bytecode[PC++];
1411         switch (opcode)
1412           {
1413           case op_nop:
1414           case op_aconst_null:
1415           case op_iconst_m1:
1416           case op_iconst_0:
1417           case op_iconst_1:
1418           case op_iconst_2:
1419           case op_iconst_3:
1420           case op_iconst_4:
1421           case op_iconst_5:
1422           case op_lconst_0:
1423           case op_lconst_1:
1424           case op_fconst_0:
1425           case op_fconst_1:
1426           case op_fconst_2:
1427           case op_dconst_0:
1428           case op_dconst_1:
1429           case op_iload_0:
1430           case op_iload_1:
1431           case op_iload_2:
1432           case op_iload_3:
1433           case op_lload_0:
1434           case op_lload_1:
1435           case op_lload_2:
1436           case op_lload_3:
1437           case op_fload_0:
1438           case op_fload_1:
1439           case op_fload_2:
1440           case op_fload_3:
1441           case op_dload_0:
1442           case op_dload_1:
1443           case op_dload_2:
1444           case op_dload_3:
1445           case op_aload_0:
1446           case op_aload_1:
1447           case op_aload_2:
1448           case op_aload_3:
1449           case op_iaload:
1450           case op_laload:
1451           case op_faload:
1452           case op_daload:
1453           case op_aaload:
1454           case op_baload:
1455           case op_caload:
1456           case op_saload:
1457           case op_istore_0:
1458           case op_istore_1:
1459           case op_istore_2:
1460           case op_istore_3:
1461           case op_lstore_0:
1462           case op_lstore_1:
1463           case op_lstore_2:
1464           case op_lstore_3:
1465           case op_fstore_0:
1466           case op_fstore_1:
1467           case op_fstore_2:
1468           case op_fstore_3:
1469           case op_dstore_0:
1470           case op_dstore_1:
1471           case op_dstore_2:
1472           case op_dstore_3:
1473           case op_astore_0:
1474           case op_astore_1:
1475           case op_astore_2:
1476           case op_astore_3:
1477           case op_iastore:
1478           case op_lastore:
1479           case op_fastore:
1480           case op_dastore:
1481           case op_aastore:
1482           case op_bastore:
1483           case op_castore:
1484           case op_sastore:
1485           case op_pop:
1486           case op_pop2:
1487           case op_dup:
1488           case op_dup_x1:
1489           case op_dup_x2:
1490           case op_dup2:
1491           case op_dup2_x1:
1492           case op_dup2_x2:
1493           case op_swap:
1494           case op_iadd:
1495           case op_isub:
1496           case op_imul:
1497           case op_idiv:
1498           case op_irem:
1499           case op_ishl:
1500           case op_ishr:
1501           case op_iushr:
1502           case op_iand:
1503           case op_ior:
1504           case op_ixor:
1505           case op_ladd:
1506           case op_lsub:
1507           case op_lmul:
1508           case op_ldiv:
1509           case op_lrem:
1510           case op_lshl:
1511           case op_lshr:
1512           case op_lushr:
1513           case op_land:
1514           case op_lor:
1515           case op_lxor:
1516           case op_fadd:
1517           case op_fsub:
1518           case op_fmul:
1519           case op_fdiv:
1520           case op_frem:
1521           case op_dadd:
1522           case op_dsub:
1523           case op_dmul:
1524           case op_ddiv:
1525           case op_drem:
1526           case op_ineg:
1527           case op_i2b:
1528           case op_i2c:
1529           case op_i2s:
1530           case op_lneg:
1531           case op_fneg:
1532           case op_dneg:
1533           case op_i2l:
1534           case op_i2f:
1535           case op_i2d:
1536           case op_l2i:
1537           case op_l2f:
1538           case op_l2d:
1539           case op_f2i:
1540           case op_f2l:
1541           case op_f2d:
1542           case op_d2i:
1543           case op_d2l:
1544           case op_d2f:
1545           case op_lcmp:
1546           case op_fcmpl:
1547           case op_fcmpg:
1548           case op_dcmpl:
1549           case op_dcmpg:
1550           case op_monitorenter:
1551           case op_monitorexit:
1552           case op_ireturn:
1553           case op_lreturn:
1554           case op_freturn:
1555           case op_dreturn:
1556           case op_areturn:
1557           case op_return:
1558           case op_athrow:
1559           case op_arraylength:
1560             break;
1561
1562           case op_bipush:
1563           case op_ldc:
1564           case op_iload:
1565           case op_lload:
1566           case op_fload:
1567           case op_dload:
1568           case op_aload:
1569           case op_istore:
1570           case op_lstore:
1571           case op_fstore:
1572           case op_dstore:
1573           case op_astore:
1574           case op_ret:
1575           case op_newarray:
1576             get_byte ();
1577             break;
1578
1579           case op_iinc:
1580           case op_sipush:
1581           case op_ldc_w:
1582           case op_ldc2_w:
1583           case op_getstatic:
1584           case op_getfield:
1585           case op_putfield:
1586           case op_putstatic:
1587           case op_new:
1588           case op_anewarray:
1589           case op_instanceof:
1590           case op_checkcast:
1591           case op_invokespecial:
1592           case op_invokestatic:
1593           case op_invokevirtual:
1594             get_short ();
1595             break;
1596
1597           case op_multianewarray:
1598             get_short ();
1599             get_byte ();
1600             break;
1601
1602           case op_jsr:
1603             last_was_jsr = true;
1604             // Fall through.
1605           case op_ifeq:
1606           case op_ifne:
1607           case op_iflt:
1608           case op_ifge:
1609           case op_ifgt:
1610           case op_ifle:
1611           case op_if_icmpeq:
1612           case op_if_icmpne:
1613           case op_if_icmplt:
1614           case op_if_icmpge:
1615           case op_if_icmpgt:
1616           case op_if_icmple:
1617           case op_if_acmpeq:
1618           case op_if_acmpne:
1619           case op_ifnull:
1620           case op_ifnonnull:
1621           case op_goto:
1622             note_branch_target (compute_jump (get_short ()), last_was_jsr);
1623             break;
1624
1625           case op_tableswitch:
1626             {
1627               skip_padding ();
1628               note_branch_target (compute_jump (get_int ()));
1629               jint low = get_int ();
1630               jint hi = get_int ();
1631               if (low > hi)
1632                 verify_fail ("invalid tableswitch", start_PC);
1633               for (int i = low; i <= hi; ++i)
1634                 note_branch_target (compute_jump (get_int ()));
1635             }
1636             break;
1637
1638           case op_lookupswitch:
1639             {
1640               skip_padding ();
1641               note_branch_target (compute_jump (get_int ()));
1642               int npairs = get_int ();
1643               if (npairs < 0)
1644                 verify_fail ("too few pairs in lookupswitch", start_PC);
1645               while (npairs-- > 0)
1646                 {
1647                   get_int ();
1648                   note_branch_target (compute_jump (get_int ()));
1649                 }
1650             }
1651             break;
1652
1653           case op_invokeinterface:
1654             get_short ();
1655             get_byte ();
1656             get_byte ();
1657             break;
1658
1659           case op_wide:
1660             {
1661               opcode = (java_opcode) get_byte ();
1662               get_short ();
1663               if (opcode == op_iinc)
1664                 get_short ();
1665             }
1666             break;
1667
1668           case op_jsr_w:
1669             last_was_jsr = true;
1670             // Fall through.
1671           case op_goto_w:
1672             note_branch_target (compute_jump (get_int ()), last_was_jsr);
1673             break;
1674
1675           default:
1676             verify_fail ("unrecognized instruction in branch_prepass",
1677                          start_PC);
1678           }
1679
1680         // See if any previous branch tried to branch to the middle of
1681         // this instruction.
1682         for (int pc = start_PC + 1; pc < PC; ++pc)
1683           {
1684             if ((flags[pc] & FLAG_BRANCH_TARGET))
1685               verify_fail ("branch to middle of instruction", pc);
1686           }
1687       }
1688
1689     // Verify exception handlers.
1690     for (int i = 0; i < current_method->exc_count; ++i)
1691       {
1692         if (! (flags[exception[i].handler_pc] & FLAG_INSN_START))
1693           verify_fail ("exception handler not at instruction start",
1694                        exception[i].handler_pc);
1695         if (! (flags[exception[i].start_pc] & FLAG_INSN_START))
1696           verify_fail ("exception start not at instruction start",
1697                        exception[i].start_pc);
1698         if (exception[i].end_pc != current_method->code_length
1699             && ! (flags[exception[i].end_pc] & FLAG_INSN_START))
1700           verify_fail ("exception end not at instruction start",
1701                        exception[i].end_pc);
1702
1703         flags[exception[i].handler_pc] |= FLAG_BRANCH_TARGET;
1704       }
1705   }
1706
1707   void check_pool_index (int index)
1708   {
1709     if (index < 0 || index >= current_class->constants.size)
1710       verify_fail ("constant pool index out of range", start_PC);
1711   }
1712
1713   type check_class_constant (int index)
1714   {
1715     check_pool_index (index);
1716     _Jv_Constants *pool = &current_class->constants;
1717     if (pool->tags[index] == JV_CONSTANT_ResolvedClass)
1718       return type (pool->data[index].clazz);
1719     else if (pool->tags[index] == JV_CONSTANT_Class)
1720       return type (pool->data[index].utf8);
1721     verify_fail ("expected class constant", start_PC);
1722   }
1723
1724   type check_constant (int index)
1725   {
1726     check_pool_index (index);
1727     _Jv_Constants *pool = &current_class->constants;
1728     if (pool->tags[index] == JV_CONSTANT_ResolvedString
1729         || pool->tags[index] == JV_CONSTANT_String)
1730       return type (&java::lang::String::class$);
1731     else if (pool->tags[index] == JV_CONSTANT_Integer)
1732       return type (int_type);
1733     else if (pool->tags[index] == JV_CONSTANT_Float)
1734       return type (float_type);
1735     verify_fail ("String, int, or float constant expected", start_PC);
1736   }
1737
1738   type check_wide_constant (int index)
1739   {
1740     check_pool_index (index);
1741     _Jv_Constants *pool = &current_class->constants;
1742     if (pool->tags[index] == JV_CONSTANT_Long)
1743       return type (long_type);
1744     else if (pool->tags[index] == JV_CONSTANT_Double)
1745       return type (double_type);
1746     verify_fail ("long or double constant expected", start_PC);
1747   }
1748
1749   // Helper for both field and method.  These are laid out the same in
1750   // the constant pool.
1751   type handle_field_or_method (int index, int expected,
1752                                _Jv_Utf8Const **name,
1753                                _Jv_Utf8Const **fmtype)
1754   {
1755     check_pool_index (index);
1756     _Jv_Constants *pool = &current_class->constants;
1757     if (pool->tags[index] != expected)
1758       verify_fail ("didn't see expected constant", start_PC);
1759     // Once we know we have a Fieldref or Methodref we assume that it
1760     // is correctly laid out in the constant pool.  I think the code
1761     // in defineclass.cc guarantees this.
1762     _Jv_ushort class_index, name_and_type_index;
1763     _Jv_loadIndexes (&pool->data[index],
1764                      class_index,
1765                      name_and_type_index);
1766     _Jv_ushort name_index, desc_index;
1767     _Jv_loadIndexes (&pool->data[name_and_type_index],
1768                      name_index, desc_index);
1769
1770     *name = pool->data[name_index].utf8;
1771     *fmtype = pool->data[desc_index].utf8;
1772
1773     return check_class_constant (class_index);
1774   }
1775
1776   // Return field's type, compute class' type if requested.
1777   type check_field_constant (int index, type *class_type = NULL)
1778   {
1779     _Jv_Utf8Const *name, *field_type;
1780     type ct = handle_field_or_method (index,
1781                                       JV_CONSTANT_Fieldref,
1782                                       &name, &field_type);
1783     if (class_type)
1784       *class_type = ct;
1785     if (field_type->data[0] == '[' || field_type->data[0] == 'L')
1786       return type (field_type);
1787     return get_type_val_for_signature (field_type->data[0]);
1788   }
1789
1790   type check_method_constant (int index, bool is_interface,
1791                               _Jv_Utf8Const **method_name,
1792                               _Jv_Utf8Const **method_signature)
1793   {
1794     return handle_field_or_method (index,
1795                                    (is_interface
1796                                     ? JV_CONSTANT_InterfaceMethodref
1797                                     : JV_CONSTANT_Methodref),
1798                                    method_name, method_signature);
1799   }
1800
1801   type get_one_type (char *&p)
1802   {
1803     char *start = p;
1804
1805     int arraycount = 0;
1806     while (*p == '[')
1807       {
1808         ++arraycount;
1809         ++p;
1810       }
1811
1812     char v = *p++;
1813
1814     if (v == 'L')
1815       {
1816         while (*p != ';')
1817           ++p;
1818         ++p;
1819         _Jv_Utf8Const *name = make_utf8_const (start, p - start);
1820         return type (name);
1821       }
1822
1823     // Casting to jchar here is ok since we are looking at an ASCII
1824     // character.
1825     type_val rt = get_type_val_for_signature (jchar (v));
1826
1827     if (arraycount == 0)
1828       {
1829         // Callers of this function eventually push their arguments on
1830         // the stack.  So, promote them here.
1831         return type (rt).promote ();
1832       }
1833
1834     jclass k = construct_primitive_array_type (rt);
1835     while (--arraycount > 0)
1836       k = _Jv_GetArrayClass (k, NULL);
1837     return type (k);
1838   }
1839
1840   void compute_argument_types (_Jv_Utf8Const *signature,
1841                                type *types)
1842   {
1843     char *p = signature->data;
1844     // Skip `('.
1845     ++p;
1846
1847     int i = 0;
1848     while (*p != ')')
1849       types[i++] = get_one_type (p);
1850   }
1851
1852   type compute_return_type (_Jv_Utf8Const *signature)
1853   {
1854     char *p = signature->data;
1855     while (*p != ')')
1856       ++p;
1857     ++p;
1858     return get_one_type (p);
1859   }
1860
1861   void check_return_type (type onstack)
1862   {
1863     type rt = compute_return_type (current_method->self->signature);
1864     if (! rt.compatible (onstack))
1865       verify_fail ("incompatible return type", start_PC);
1866   }
1867
1868   void verify_instructions_0 ()
1869   {
1870     current_state = new state (current_method->max_stack,
1871                                current_method->max_locals);
1872
1873     PC = 0;
1874     start_PC = 0;
1875
1876     {
1877       int var = 0;
1878
1879       using namespace java::lang::reflect;
1880       if (! Modifier::isStatic (current_method->self->accflags))
1881         {
1882           type kurr (current_class);
1883           if (_Jv_equalUtf8Consts (current_method->self->name, gcj::init_name))
1884             kurr.set_uninitialized (type::SELF);
1885           set_variable (0, kurr);
1886           ++var;
1887         }
1888
1889       // We have to handle wide arguments specially here.
1890       int arg_count = _Jv_count_arguments (current_method->self->signature);
1891       type arg_types[arg_count];
1892       compute_argument_types (current_method->self->signature, arg_types);
1893       for (int i = 0; i < arg_count; ++i)
1894         {
1895           set_variable (var, arg_types[i]);
1896           ++var;
1897           if (arg_types[i].iswide ())
1898             ++var;
1899         }
1900     }
1901
1902     states = (state **) _Jv_Malloc (sizeof (state *)
1903                                     * current_method->code_length);
1904     for (int i = 0; i < current_method->code_length; ++i)
1905       states[i] = NULL;
1906
1907     next_verify_pc = state::NO_NEXT;
1908
1909     while (true)
1910       {
1911         // If the PC was invalidated, get a new one from the work list.
1912         if (PC == state::NO_NEXT)
1913           {
1914             PC = pop_jump ();
1915             if (PC == state::INVALID)
1916               verify_fail ("can't happen: saw state::INVALID");
1917             if (PC == state::NO_NEXT)
1918               break;
1919             // Set up the current state.
1920             current_state->copy (states[PC], current_method->max_stack,
1921                                  current_method->max_locals);
1922           }
1923         else
1924           {
1925             // Control can't fall off the end of the bytecode.  We
1926             // only need to check this in the fall-through case,
1927             // because branch bounds are checked when they are
1928             // pushed.
1929             if (PC >= current_method->code_length)
1930               verify_fail ("fell off end");
1931
1932             // We only have to do this checking in the situation where
1933             // control flow falls through from the previous
1934             // instruction.  Otherwise merging is done at the time we
1935             // push the branch.
1936             if (states[PC] != NULL)
1937               {
1938                 // We've already visited this instruction.  So merge
1939                 // the states together.  If this yields no change then
1940                 // we don't have to re-verify.  However, if the new
1941                 // state is an the result of an unmerged `ret', we
1942                 // must continue through it.
1943                 debug_print ("== Fall through merge\n");
1944                 states[PC]->print ("Old", PC, current_method->max_stack,
1945                                    current_method->max_locals);
1946                 current_state->print ("Cur", PC, current_method->max_stack,
1947                                       current_method->max_locals);
1948                 if (! current_state->merge (states[PC], false,
1949                                             current_method->max_locals)
1950                     && ! states[PC]->is_unmerged_ret_state (current_method->max_locals))
1951                   {
1952                     debug_print ("== Fall through optimization\n");
1953                     invalidate_pc ();
1954                     continue;
1955                   }
1956                 // Save a copy of it for later.
1957                 states[PC]->copy (current_state, current_method->max_stack,
1958                                   current_method->max_locals);
1959                 current_state->print ("New", PC, current_method->max_stack,
1960                                       current_method->max_locals);
1961               }
1962           }
1963
1964         // We only have to keep saved state at branch targets.  If
1965         // we're at a branch target and the state here hasn't been set
1966         // yet, we set it now.
1967         if (states[PC] == NULL && (flags[PC] & FLAG_BRANCH_TARGET))
1968           {
1969             states[PC] = new state (current_state, current_method->max_stack,
1970                                     current_method->max_locals);
1971           }
1972
1973         // Set this before handling exceptions so that debug output is
1974         // sane.
1975         start_PC = PC;
1976
1977         // Update states for all active exception handlers.  Ordinarily
1978         // there are not many exception handlers.  So we simply run
1979         // through them all.
1980         for (int i = 0; i < current_method->exc_count; ++i)
1981           {
1982             if (PC >= exception[i].start_pc && PC < exception[i].end_pc)
1983               {
1984                 type handler (&java::lang::Throwable::class$);
1985                 if (exception[i].handler_type != 0)
1986                   handler = check_class_constant (exception[i].handler_type);
1987                 push_exception_jump (handler, exception[i].handler_pc);
1988               }
1989           }
1990
1991         current_state->print ("   ", PC, current_method->max_stack,
1992                               current_method->max_locals);
1993         java_opcode opcode = (java_opcode) bytecode[PC++];
1994         switch (opcode)
1995           {
1996           case op_nop:
1997             break;
1998
1999           case op_aconst_null:
2000             push_type (null_type);
2001             break;
2002
2003           case op_iconst_m1:
2004           case op_iconst_0:
2005           case op_iconst_1:
2006           case op_iconst_2:
2007           case op_iconst_3:
2008           case op_iconst_4:
2009           case op_iconst_5:
2010             push_type (int_type);
2011             break;
2012
2013           case op_lconst_0:
2014           case op_lconst_1:
2015             push_type (long_type);
2016             break;
2017
2018           case op_fconst_0:
2019           case op_fconst_1:
2020           case op_fconst_2:
2021             push_type (float_type);
2022             break;
2023
2024           case op_dconst_0:
2025           case op_dconst_1:
2026             push_type (double_type);
2027             break;
2028
2029           case op_bipush:
2030             get_byte ();
2031             push_type (int_type);
2032             break;
2033
2034           case op_sipush:
2035             get_short ();
2036             push_type (int_type);
2037             break;
2038
2039           case op_ldc:
2040             push_type (check_constant (get_byte ()));
2041             break;
2042           case op_ldc_w:
2043             push_type (check_constant (get_ushort ()));
2044             break;
2045           case op_ldc2_w:
2046             push_type (check_wide_constant (get_ushort ()));
2047             break;
2048
2049           case op_iload:
2050             push_type (get_variable (get_byte (), int_type));
2051             break;
2052           case op_lload:
2053             push_type (get_variable (get_byte (), long_type));
2054             break;
2055           case op_fload:
2056             push_type (get_variable (get_byte (), float_type));
2057             break;
2058           case op_dload:
2059             push_type (get_variable (get_byte (), double_type));
2060             break;
2061           case op_aload:
2062             push_type (get_variable (get_byte (), reference_type));
2063             break;
2064
2065           case op_iload_0:
2066           case op_iload_1:
2067           case op_iload_2:
2068           case op_iload_3:
2069             push_type (get_variable (opcode - op_iload_0, int_type));
2070             break;
2071           case op_lload_0:
2072           case op_lload_1:
2073           case op_lload_2:
2074           case op_lload_3:
2075             push_type (get_variable (opcode - op_lload_0, long_type));
2076             break;
2077           case op_fload_0:
2078           case op_fload_1:
2079           case op_fload_2:
2080           case op_fload_3:
2081             push_type (get_variable (opcode - op_fload_0, float_type));
2082             break;
2083           case op_dload_0:
2084           case op_dload_1:
2085           case op_dload_2:
2086           case op_dload_3:
2087             push_type (get_variable (opcode - op_dload_0, double_type));
2088             break;
2089           case op_aload_0:
2090           case op_aload_1:
2091           case op_aload_2:
2092           case op_aload_3:
2093             push_type (get_variable (opcode - op_aload_0, reference_type));
2094             break;
2095           case op_iaload:
2096             pop_type (int_type);
2097             push_type (require_array_type (pop_type (reference_type),
2098                                            int_type));
2099             break;
2100           case op_laload:
2101             pop_type (int_type);
2102             push_type (require_array_type (pop_type (reference_type),
2103                                            long_type));
2104             break;
2105           case op_faload:
2106             pop_type (int_type);
2107             push_type (require_array_type (pop_type (reference_type),
2108                                            float_type));
2109             break;
2110           case op_daload:
2111             pop_type (int_type);
2112             push_type (require_array_type (pop_type (reference_type),
2113                                            double_type));
2114             break;
2115           case op_aaload:
2116             pop_type (int_type);
2117             push_type (require_array_type (pop_type (reference_type),
2118                                            reference_type));
2119             break;
2120           case op_baload:
2121             pop_type (int_type);
2122             require_array_type (pop_type (reference_type), byte_type);
2123             push_type (int_type);
2124             break;
2125           case op_caload:
2126             pop_type (int_type);
2127             require_array_type (pop_type (reference_type), char_type);
2128             push_type (int_type);
2129             break;
2130           case op_saload:
2131             pop_type (int_type);
2132             require_array_type (pop_type (reference_type), short_type);
2133             push_type (int_type);
2134             break;
2135           case op_istore:
2136             set_variable (get_byte (), pop_type (int_type));
2137             break;
2138           case op_lstore:
2139             set_variable (get_byte (), pop_type (long_type));
2140             break;
2141           case op_fstore:
2142             set_variable (get_byte (), pop_type (float_type));
2143             break;
2144           case op_dstore:
2145             set_variable (get_byte (), pop_type (double_type));
2146             break;
2147           case op_astore:
2148             set_variable (get_byte (), pop_ref_or_return ());
2149             break;
2150           case op_istore_0:
2151           case op_istore_1:
2152           case op_istore_2:
2153           case op_istore_3:
2154             set_variable (opcode - op_istore_0, pop_type (int_type));
2155             break;
2156           case op_lstore_0:
2157           case op_lstore_1:
2158           case op_lstore_2:
2159           case op_lstore_3:
2160             set_variable (opcode - op_lstore_0, pop_type (long_type));
2161             break;
2162           case op_fstore_0:
2163           case op_fstore_1:
2164           case op_fstore_2:
2165           case op_fstore_3:
2166             set_variable (opcode - op_fstore_0, pop_type (float_type));
2167             break;
2168           case op_dstore_0:
2169           case op_dstore_1:
2170           case op_dstore_2:
2171           case op_dstore_3:
2172             set_variable (opcode - op_dstore_0, pop_type (double_type));
2173             break;
2174           case op_astore_0:
2175           case op_astore_1:
2176           case op_astore_2:
2177           case op_astore_3:
2178             set_variable (opcode - op_astore_0, pop_ref_or_return ());
2179             break;
2180           case op_iastore:
2181             pop_type (int_type);
2182             pop_type (int_type);
2183             require_array_type (pop_type (reference_type), int_type);
2184             break;
2185           case op_lastore:
2186             pop_type (long_type);
2187             pop_type (int_type);
2188             require_array_type (pop_type (reference_type), long_type);
2189             break;
2190           case op_fastore:
2191             pop_type (float_type);
2192             pop_type (int_type);
2193             require_array_type (pop_type (reference_type), float_type);
2194             break;
2195           case op_dastore:
2196             pop_type (double_type);
2197             pop_type (int_type);
2198             require_array_type (pop_type (reference_type), double_type);
2199             break;
2200           case op_aastore:
2201             pop_type (reference_type);
2202             pop_type (int_type);
2203             require_array_type (pop_type (reference_type), reference_type);
2204             break;
2205           case op_bastore:
2206             pop_type (int_type);
2207             pop_type (int_type);
2208             require_array_type (pop_type (reference_type), byte_type);
2209             break;
2210           case op_castore:
2211             pop_type (int_type);
2212             pop_type (int_type);
2213             require_array_type (pop_type (reference_type), char_type);
2214             break;
2215           case op_sastore:
2216             pop_type (int_type);
2217             pop_type (int_type);
2218             require_array_type (pop_type (reference_type), short_type);
2219             break;
2220           case op_pop:
2221             pop32 ();
2222             break;
2223           case op_pop2:
2224             pop64 ();
2225             break;
2226           case op_dup:
2227             {
2228               type t = pop32 ();
2229               push_type (t);
2230               push_type (t);
2231             }
2232             break;
2233           case op_dup_x1:
2234             {
2235               type t1 = pop32 ();
2236               type t2 = pop32 ();
2237               push_type (t1);
2238               push_type (t2);
2239               push_type (t1);
2240             }
2241             break;
2242           case op_dup_x2:
2243             {
2244               type t1 = pop32 ();
2245               type t2 = pop_raw ();
2246               if (! t2.iswide ())
2247                 {
2248                   type t3 = pop32 ();
2249                   push_type (t1);
2250                   push_type (t3);
2251                 }
2252               else
2253                 push_type (t1);
2254               push_type (t2);
2255               push_type (t1);
2256             }
2257             break;
2258           case op_dup2:
2259             {
2260               type t = pop_raw ();
2261               if (! t.iswide ())
2262                 {
2263                   type t2 = pop32 ();
2264                   push_type (t2);
2265                   push_type (t);
2266                   push_type (t2);
2267                 }
2268               push_type (t);
2269             }
2270             break;
2271           case op_dup2_x1:
2272             {
2273               type t1 = pop_raw ();
2274               type t2 = pop32 ();
2275               if (! t1.iswide ())
2276                 {
2277                   type t3 = pop32 ();
2278                   push_type (t2);
2279                   push_type (t1);
2280                   push_type (t3);
2281                 }
2282               else
2283                 push_type (t1);
2284               push_type (t2);
2285               push_type (t1);
2286             }
2287             break;
2288           case op_dup2_x2:
2289             {
2290               // FIXME
2291               type t1 = pop_raw ();
2292               if (t1.iswide ())
2293                 {
2294                   type t2 = pop_raw ();
2295                   if (t2.iswide ())
2296                     {
2297                       push_type (t1);
2298                       push_type (t2);
2299                     }
2300                   else
2301                     {
2302                       type t3 = pop32 ();
2303                       push_type (t1);
2304                       push_type (t3);
2305                       push_type (t2);
2306                     }
2307                   push_type (t1);
2308                 }
2309               else
2310                 {
2311                   type t2 = pop32 ();
2312                   type t3 = pop_raw ();
2313                   if (t3.iswide ())
2314                     {
2315                       push_type (t2);
2316                       push_type (t1);
2317                     }
2318                   else
2319                     {
2320                       type t4 = pop32 ();
2321                       push_type (t2);
2322                       push_type (t1);
2323                       push_type (t4);
2324                     }
2325                   push_type (t3);
2326                   push_type (t2);
2327                   push_type (t1);
2328                 }
2329             }
2330             break;
2331           case op_swap:
2332             {
2333               type t1 = pop32 ();
2334               type t2 = pop32 ();
2335               push_type (t1);
2336               push_type (t2);
2337             }
2338             break;
2339           case op_iadd:
2340           case op_isub:
2341           case op_imul:
2342           case op_idiv:
2343           case op_irem:
2344           case op_ishl:
2345           case op_ishr:
2346           case op_iushr:
2347           case op_iand:
2348           case op_ior:
2349           case op_ixor:
2350             pop_type (int_type);
2351             push_type (pop_type (int_type));
2352             break;
2353           case op_ladd:
2354           case op_lsub:
2355           case op_lmul:
2356           case op_ldiv:
2357           case op_lrem:
2358           case op_land:
2359           case op_lor:
2360           case op_lxor:
2361             pop_type (long_type);
2362             push_type (pop_type (long_type));
2363             break;
2364           case op_lshl:
2365           case op_lshr:
2366           case op_lushr:
2367             pop_type (int_type);
2368             push_type (pop_type (long_type));
2369             break;
2370           case op_fadd:
2371           case op_fsub:
2372           case op_fmul:
2373           case op_fdiv:
2374           case op_frem:
2375             pop_type (float_type);
2376             push_type (pop_type (float_type));
2377             break;
2378           case op_dadd:
2379           case op_dsub:
2380           case op_dmul:
2381           case op_ddiv:
2382           case op_drem:
2383             pop_type (double_type);
2384             push_type (pop_type (double_type));
2385             break;
2386           case op_ineg:
2387           case op_i2b:
2388           case op_i2c:
2389           case op_i2s:
2390             push_type (pop_type (int_type));
2391             break;
2392           case op_lneg:
2393             push_type (pop_type (long_type));
2394             break;
2395           case op_fneg:
2396             push_type (pop_type (float_type));
2397             break;
2398           case op_dneg:
2399             push_type (pop_type (double_type));
2400             break;
2401           case op_iinc:
2402             get_variable (get_byte (), int_type);
2403             get_byte ();
2404             break;
2405           case op_i2l:
2406             pop_type (int_type);
2407             push_type (long_type);
2408             break;
2409           case op_i2f:
2410             pop_type (int_type);
2411             push_type (float_type);
2412             break;
2413           case op_i2d:
2414             pop_type (int_type);
2415             push_type (double_type);
2416             break;
2417           case op_l2i:
2418             pop_type (long_type);
2419             push_type (int_type);
2420             break;
2421           case op_l2f:
2422             pop_type (long_type);
2423             push_type (float_type);
2424             break;
2425           case op_l2d:
2426             pop_type (long_type);
2427             push_type (double_type);
2428             break;
2429           case op_f2i:
2430             pop_type (float_type);
2431             push_type (int_type);
2432             break;
2433           case op_f2l:
2434             pop_type (float_type);
2435             push_type (long_type);
2436             break;
2437           case op_f2d:
2438             pop_type (float_type);
2439             push_type (double_type);
2440             break;
2441           case op_d2i:
2442             pop_type (double_type);
2443             push_type (int_type);
2444             break;
2445           case op_d2l:
2446             pop_type (double_type);
2447             push_type (long_type);
2448             break;
2449           case op_d2f:
2450             pop_type (double_type);
2451             push_type (float_type);
2452             break;
2453           case op_lcmp:
2454             pop_type (long_type);
2455             pop_type (long_type);
2456             push_type (int_type);
2457             break;
2458           case op_fcmpl:
2459           case op_fcmpg:
2460             pop_type (float_type);
2461             pop_type (float_type);
2462             push_type (int_type);
2463             break;
2464           case op_dcmpl:
2465           case op_dcmpg:
2466             pop_type (double_type);
2467             pop_type (double_type);
2468             push_type (int_type);
2469             break;
2470           case op_ifeq:
2471           case op_ifne:
2472           case op_iflt:
2473           case op_ifge:
2474           case op_ifgt:
2475           case op_ifle:
2476             pop_type (int_type);
2477             push_jump (get_short ());
2478             break;
2479           case op_if_icmpeq:
2480           case op_if_icmpne:
2481           case op_if_icmplt:
2482           case op_if_icmpge:
2483           case op_if_icmpgt:
2484           case op_if_icmple:
2485             pop_type (int_type);
2486             pop_type (int_type);
2487             push_jump (get_short ());
2488             break;
2489           case op_if_acmpeq:
2490           case op_if_acmpne:
2491             pop_type (reference_type);
2492             pop_type (reference_type);
2493             push_jump (get_short ());
2494             break;
2495           case op_goto:
2496             push_jump (get_short ());
2497             invalidate_pc ();
2498             break;
2499           case op_jsr:
2500             handle_jsr_insn (get_short ());
2501             break;
2502           case op_ret:
2503             handle_ret_insn (get_byte ());
2504             break;
2505           case op_tableswitch:
2506             {
2507               pop_type (int_type);
2508               skip_padding ();
2509               push_jump (get_int ());
2510               jint low = get_int ();
2511               jint high = get_int ();
2512               // Already checked LOW -vs- HIGH.
2513               for (int i = low; i <= high; ++i)
2514                 push_jump (get_int ());
2515               invalidate_pc ();
2516             }
2517             break;
2518
2519           case op_lookupswitch:
2520             {
2521               pop_type (int_type);
2522               skip_padding ();
2523               push_jump (get_int ());
2524               jint npairs = get_int ();
2525               // Already checked NPAIRS >= 0.
2526               jint lastkey = 0;
2527               for (int i = 0; i < npairs; ++i)
2528                 {
2529                   jint key = get_int ();
2530                   if (i > 0 && key <= lastkey)
2531                     verify_fail ("lookupswitch pairs unsorted", start_PC);
2532                   lastkey = key;
2533                   push_jump (get_int ());
2534                 }
2535               invalidate_pc ();
2536             }
2537             break;
2538           case op_ireturn:
2539             check_return_type (pop_type (int_type));
2540             invalidate_pc ();
2541             break;
2542           case op_lreturn:
2543             check_return_type (pop_type (long_type));
2544             invalidate_pc ();
2545             break;
2546           case op_freturn:
2547             check_return_type (pop_type (float_type));
2548             invalidate_pc ();
2549             break;
2550           case op_dreturn:
2551             check_return_type (pop_type (double_type));
2552             invalidate_pc ();
2553             break;
2554           case op_areturn:
2555             check_return_type (pop_type (reference_type));
2556             invalidate_pc ();
2557             break;
2558           case op_return:
2559             check_return_type (void_type);
2560             invalidate_pc ();
2561             break;
2562           case op_getstatic:
2563             push_type (check_field_constant (get_ushort ()));
2564             break;
2565           case op_putstatic:
2566             pop_type (check_field_constant (get_ushort ()));
2567             break;
2568           case op_getfield:
2569             {
2570               type klass;
2571               type field = check_field_constant (get_ushort (), &klass);
2572               pop_type (klass);
2573               push_type (field);
2574             }
2575             break;
2576           case op_putfield:
2577             {
2578               type klass;
2579               type field = check_field_constant (get_ushort (), &klass);
2580               pop_type (field);
2581               pop_type (klass);
2582             }
2583             break;
2584
2585           case op_invokevirtual:
2586           case op_invokespecial:
2587           case op_invokestatic:
2588           case op_invokeinterface:
2589             {
2590               _Jv_Utf8Const *method_name, *method_signature;
2591               type class_type
2592                 = check_method_constant (get_ushort (),
2593                                          opcode == op_invokeinterface,
2594                                          &method_name,
2595                                          &method_signature);
2596               int arg_count = _Jv_count_arguments (method_signature);
2597               if (opcode == op_invokeinterface)
2598                 {
2599                   int nargs = get_byte ();
2600                   if (nargs == 0)
2601                     verify_fail ("too few arguments to invokeinterface",
2602                                  start_PC);
2603                   if (get_byte () != 0)
2604                     verify_fail ("invokeinterface dummy byte is wrong",
2605                                  start_PC);
2606                   if (nargs - 1 != arg_count)
2607                     verify_fail ("wrong argument count for invokeinterface",
2608                                  start_PC);
2609                 }
2610
2611               bool is_init = false;
2612               if (_Jv_equalUtf8Consts (method_name, gcj::init_name))
2613                 {
2614                   is_init = true;
2615                   if (opcode != op_invokespecial)
2616                     verify_fail ("can't invoke <init>", start_PC);
2617                 }
2618               else if (method_name->data[0] == '<')
2619                 verify_fail ("can't invoke method starting with `<'",
2620                              start_PC);
2621
2622               // Pop arguments and check types.
2623               type arg_types[arg_count];
2624               compute_argument_types (method_signature, arg_types);
2625               for (int i = arg_count - 1; i >= 0; --i)
2626                 pop_type (arg_types[i]);
2627
2628               if (opcode != op_invokestatic)
2629                 {
2630                   type t = class_type;
2631                   if (is_init)
2632                     {
2633                       // In this case the PC doesn't matter.
2634                       t.set_uninitialized (type::UNINIT);
2635                     }
2636                   t = pop_type (t);
2637                   if (is_init)
2638                     current_state->set_initialized (t.get_pc (),
2639                                                     current_method->max_locals);
2640                 }
2641
2642               type rt = compute_return_type (method_signature);
2643               if (! rt.isvoid ())
2644                 push_type (rt);
2645             }
2646             break;
2647
2648           case op_new:
2649             {
2650               type t = check_class_constant (get_ushort ());
2651               if (t.isarray () || t.isinterface () || t.isabstract ())
2652                 verify_fail ("type is array, interface, or abstract",
2653                              start_PC);
2654               t.set_uninitialized (start_PC);
2655               push_type (t);
2656             }
2657             break;
2658
2659           case op_newarray:
2660             {
2661               int atype = get_byte ();
2662               // We intentionally have chosen constants to make this
2663               // valid.
2664               if (atype < boolean_type || atype > long_type)
2665                 verify_fail ("type not primitive", start_PC);
2666               pop_type (int_type);
2667               push_type (construct_primitive_array_type (type_val (atype)));
2668             }
2669             break;
2670           case op_anewarray:
2671             pop_type (int_type);
2672             push_type (check_class_constant (get_ushort ()).to_array ());
2673             break;
2674           case op_arraylength:
2675             {
2676               type t = pop_type (reference_type);
2677               if (! t.isarray ())
2678                 verify_fail ("array type expected", start_PC);
2679               push_type (int_type);
2680             }
2681             break;
2682           case op_athrow:
2683             pop_type (type (&java::lang::Throwable::class$));
2684             invalidate_pc ();
2685             break;
2686           case op_checkcast:
2687             pop_type (reference_type);
2688             push_type (check_class_constant (get_ushort ()));
2689             break;
2690           case op_instanceof:
2691             pop_type (reference_type);
2692             check_class_constant (get_ushort ());
2693             push_type (int_type);
2694             break;
2695           case op_monitorenter:
2696             pop_type (reference_type);
2697             break;
2698           case op_monitorexit:
2699             pop_type (reference_type);
2700             break;
2701           case op_wide:
2702             {
2703               switch (get_byte ())
2704                 {
2705                 case op_iload:
2706                   push_type (get_variable (get_ushort (), int_type));
2707                   break;
2708                 case op_lload:
2709                   push_type (get_variable (get_ushort (), long_type));
2710                   break;
2711                 case op_fload:
2712                   push_type (get_variable (get_ushort (), float_type));
2713                   break;
2714                 case op_dload:
2715                   push_type (get_variable (get_ushort (), double_type));
2716                   break;
2717                 case op_aload:
2718                   push_type (get_variable (get_ushort (), reference_type));
2719                   break;
2720                 case op_istore:
2721                   set_variable (get_ushort (), pop_type (int_type));
2722                   break;
2723                 case op_lstore:
2724                   set_variable (get_ushort (), pop_type (long_type));
2725                   break;
2726                 case op_fstore:
2727                   set_variable (get_ushort (), pop_type (float_type));
2728                   break;
2729                 case op_dstore:
2730                   set_variable (get_ushort (), pop_type (double_type));
2731                   break;
2732                 case op_astore:
2733                   set_variable (get_ushort (), pop_type (reference_type));
2734                   break;
2735                 case op_ret:
2736                   handle_ret_insn (get_short ());
2737                   break;
2738                 case op_iinc:
2739                   get_variable (get_ushort (), int_type);
2740                   get_short ();
2741                   break;
2742                 default:
2743                   verify_fail ("unrecognized wide instruction", start_PC);
2744                 }
2745             }
2746             break;
2747           case op_multianewarray:
2748             {
2749               type atype = check_class_constant (get_ushort ());
2750               int dim = get_byte ();
2751               if (dim < 1)
2752                 verify_fail ("too few dimensions to multianewarray", start_PC);
2753               atype.verify_dimensions (dim);
2754               for (int i = 0; i < dim; ++i)
2755                 pop_type (int_type);
2756               push_type (atype);
2757             }
2758             break;
2759           case op_ifnull:
2760           case op_ifnonnull:
2761             pop_type (reference_type);
2762             push_jump (get_short ());
2763             break;
2764           case op_goto_w:
2765             push_jump (get_int ());
2766             invalidate_pc ();
2767             break;
2768           case op_jsr_w:
2769             handle_jsr_insn (get_int ());
2770             break;
2771
2772           default:
2773             // Unrecognized opcode.
2774             verify_fail ("unrecognized instruction in verify_instructions_0",
2775                          start_PC);
2776           }
2777       }
2778   }
2779
2780 public:
2781
2782   void verify_instructions ()
2783   {
2784     branch_prepass ();
2785     verify_instructions_0 ();
2786   }
2787
2788   _Jv_BytecodeVerifier (_Jv_InterpMethod *m)
2789   {
2790     // We just print the text as utf-8.  This is just for debugging
2791     // anyway.
2792     debug_print ("--------------------------------\n");
2793     debug_print ("-- Verifying method `%s'\n", m->self->name->data);
2794
2795     current_method = m;
2796     bytecode = m->bytecode ();
2797     exception = m->exceptions ();
2798     current_class = m->defining_class;
2799
2800     states = NULL;
2801     flags = NULL;
2802     jsr_ptrs = NULL;
2803     utf8_list = NULL;
2804   }
2805
2806   ~_Jv_BytecodeVerifier ()
2807   {
2808     if (states)
2809       _Jv_Free (states);
2810     if (flags)
2811       _Jv_Free (flags);
2812     if (jsr_ptrs)
2813       _Jv_Free (jsr_ptrs);
2814     while (utf8_list != NULL)
2815       {
2816         linked_utf8 *n = utf8_list->next;
2817         _Jv_Free (utf8_list->val);
2818         _Jv_Free (utf8_list);
2819         utf8_list = n;
2820       }
2821   }
2822 };
2823
2824 void
2825 _Jv_VerifyMethod (_Jv_InterpMethod *meth)
2826 {
2827   _Jv_BytecodeVerifier v (meth);
2828   v.verify_instructions ();
2829 }
2830
2831 // FIXME: add more info, like PC, when required.
2832 static void
2833 verify_fail (char *s, jint pc)
2834 {
2835   using namespace java::lang;
2836   StringBuffer *buf = new StringBuffer ();
2837
2838   buf->append (JvNewStringLatin1 ("verification failed"));
2839   if (pc != -1)
2840     {
2841       buf->append (JvNewStringLatin1 (" at PC "));
2842       buf->append (pc);
2843     }
2844   buf->append (JvNewStringLatin1 (": "));
2845   buf->append (JvNewStringLatin1 (s));
2846   throw new java::lang::VerifyError (buf->toString ());
2847 }
2848
2849 #endif  /* INTERPRETER */