libjava/verify.cc

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