libjava/verify.cc

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