libjava/verify.cc

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