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