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