src/vm/jit/verify/typecheck.c

   1 /* src/vm/jit/verify/typecheck.c - typechecking (part of bytecode verification)
   2
   3    Copyright (C) 1996-2005, 2006 R. Grafl, A. Krall, C. Kruegel,
   4    C. Oates, R. Obermaisser, M. Platter, M. Probst, S. Ring,
   5    E. Steiner, C. Thalinger, D. Thuernbeck, P. Tomsich, C. Ullrich,
   6    J. Wenninger, Institut f. Computersprachen - TU Wien
   7
   8    This file is part of CACAO.
   9
  10    This program is free software; you can redistribute it and/or
  11    modify it under the terms of the GNU General Public License as
  12    published by the Free Software Foundation; either version 2, or (at
  13    your option) any later version.
  14
  15    This program is distributed in the hope that it will be useful, but
  16    WITHOUT ANY WARRANTY; without even the implied warranty of
  17    MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU
  18    General Public License for more details.
  19
  20    You should have received a copy of the GNU General Public License
  21    along with this program; if not, write to the Free Software
  22    Foundation, Inc., 51 Franklin Street, Fifth Floor, Boston, MA
  23    02110-1301, USA.
  24
  25    Contact: cacao@cacaojvm.org
  26
  27    Authors: Edwin Steiner
  28
  29    Changes: Christian Thalinger
  30
  31    $Id: typecheck.c 4456 2006-02-06 01:08:37Z edwin $
  32
  33 */
  34
  35 /*
  36
  37 What's the purpose of the `typechecker`?
  38 ----------------------------------------
  39
  40 The typechecker analyses (the intermediate repr. of) the bytecode of
  41 each method and ensures that for each instruction the values on the
  42 stack and in local variables are of the correct type whenever the
  43 instruction is executed.
  44
  45 type checking is a mandatory part of bytecode verification.
  46
  47
  48 How does the typechecker work?
  49 ------------------------------
  50
  51 The JVM stack and the local variables are not statically typed, so the
  52 typechecker has to *infer* the static types of stack slots and local
  53 variables at each point of the method. The JVM spec imposes a lot of
  54 restrictions on the bytecode in order to guarantee that this is always
  55 possible.
  56
  57 Basically the typechecker solves the data flow equations of the method.
  58 This is done in the usual way for a forward data flow analysis: Starting
  59 from the entry point of the method the typechecker follows the CFG and
  60 records the type of each stack slot and local variable at each point[1].
  61 When two or more control flow paths merge at a point, the union of the
  62 types for each slot/variable is taken. The algorithm continues to follow
  63 all possible paths[2] until the recorded types do not change anymore (ie.
  64 the equations have been solved).
  65
  66 If the solution has been reached and the resulting types are valid for
  67 all instructions, then type checking terminates with success, otherwise
  68 an exception is thrown.
  69
  70
  71 Why is this code so damn complicated?
  72 -------------------------------------
  73
  74 Short answer: The devil's in the details.
  75
  76 While the basic operation of the typechecker is no big deal, there are
  77 many properties of Java bytecode which make type checking hard. Some of
  78 them are not even addressed in the JVM spec. Some problems and their
  79 solutions:
  80
  81 *) Finding a good representation of the union of two reference types is
  82 difficult because of multiple inheritance of interfaces.
  83
  84         Solution: The typeinfo system can represent such "merged" types by a
  85         list of proper subclasses of a class. Example:
  86
  87                 typeclass=java.lang.Object merged={ InterfaceA, InterfaceB }
  88
  89         represents the result of merging two interface types "InterfaceA"
  90         and "InterfaceB".
  91
  92 *) When the code of a method is verified, there may still be unresolved
  93 references to classes/methods/fields in the code, which we may not force
  94 to be resolved eagerly. (A similar problem arises because of the special
  95 checks for protected members.)
  96
  97         Solution: The typeinfo system knows how to deal with unresolved
  98         class references. Whenever a check has to be performed for an
  99         unresolved type, the type is annotated with constraints representing
 100         the check. Later, when the type is resolved, the constraints are
 101         checked. (See the constrain_unresolved_... and the resolve_...
 102         methods.)[3]
 103
 104 *) The boundaries of jsr subroutines are not well-defined. For a given
 105 instruction it may be impossible to tell whether it is part of a
 106 subroutine, or to which subroutine it belongs.
 107
 108         Solution: The typechecker implements a method developed by
 109         Alessandro Coglio[4] which treats each returnAddress as a distinct
 110         type that is not merged with other returnAddresses. This way, when a
 111         RET instruction is reached, we know exactly which types to propagate
 112         to which return target among the possible targets of the RET. The
 113         downside of this method is, that for each slot/variable we must
 114         store not just one type, but one type *for each possible use of the
 115         returnAddresses* that currently are in a slot/variable.[5]
 116
 117 *) Checks for uninitialized object instances are hard because after the
 118 invocation of <init> on an uninitialized object *all* slots/variables
 119 referring to this object (and exactly those slots/variables) must be
 120 marked as initialized.
 121
 122         Solution: The JVM spec describes a solution, which has been
 123         implemented in this typechecker.
 124
 125
 126 --- Footnotes
 127
 128 [1] Actually only the types of slots/variables at the start of each
 129 basic block are remembered. Within a basic block the algorithm only keeps
 130 the types of the slots/variables for the "current" instruction which is
 131 being analysed.
 132
 133 [2] Actually the algorithm iterates through the basic block list until
 134 there are no more changes. Theoretically it would be wise to sort the
 135 basic blocks topologically beforehand, but the number of average/max
 136 iterations observed is so low, that this was not deemed necessary.
 137
 138 [3] This is similar to a method proposed by: Alessandro Coglio et al., A
 139 Formal Specification of Java Class Loading, Technical Report, Kestrel
 140 Institute April 2000, revised July 2000
 141 http://www.kestrel.edu/home/people/coglio/loading.pdf
 142 An important difference is that Coglio's subtype constraints are checked
 143 after loading, while our constraints are checked when the field/method
 144 is accessed for the first time, so we can guarantee lexically correct
 145 error reporting.
 146
 147 [4] Alessandro Coglio, Simple Verification Technique for Complex Java
 148 Bytecode Subroutines, 4th ECOOP Workshop on Formal Techniques for
 149 Java-like Programs, June 2002
 150 http://www.kestrel.edu/home/people/coglio/ftjp02.pdf
 151
 152 [5] This is a major source of code complexity. The main data structures
 153 dealing with this are the "typevector set" and the typestack. The
 154 "typevector set" is a set of alternative typevectors, such that each
 155 typevector specifies the types of the local variables for a single
 156 combination of returnAddresses used. Thus we support full polymorphism
 157 of subroutines over the types of local variables. The typestack,
 158 however, does not support polymorphism, both for historical and JVM-spec
 159 reasons. A slot of the typestack may, however, contain multiple
 160 alternative returnAddresses, which is realized by a linked list hanging
 161 of the typeinfo of the stack slot.
 162
 163 */
 164
 165 #include <assert.h>
 166 #include <string.h>
 167
 168 #include "config.h"
 169 #include "vm/types.h"
 170 #include "vm/global.h"
 171
 172 #ifdef ENABLE_VERIFIER
 173
 174 #include "mm/memory.h"
 175 #include "toolbox/logging.h"
 176 #include "native/native.h"
 177 #include "vm/builtin.h"
 178 #include "vm/jit/patcher.h"
 179 #include "vm/loader.h"
 180 #include "vm/options.h"
 181 #include "vm/jit/jit.h"
 182 #include "vm/jit/stack.h"
 183 #include "vm/access.h"
 184 #include "vm/resolve.h"
 185
 186
 187 /****************************************************************************/
 188 /* DEBUG HELPERS                                                            */
 189 /****************************************************************************/
 190
 191 #ifdef TYPECHECK_DEBUG
 192 #define TYPECHECK_ASSERT(cond)  assert(cond)
 193 #else
 194 #define TYPECHECK_ASSERT(cond)
 195 #endif
 196
 197 #ifdef TYPECHECK_VERBOSE_OPT
 198 bool typecheckverbose = false;
 199 FILE *typecheck_logfile;
 200 #define DOLOG(action)  do { if (typecheckverbose) {action;} } while(0)
 201 #else
 202 #define DOLOG(action)
 203 #endif
 204
 205 #ifdef TYPECHECK_VERBOSE
 206 #define TYPECHECK_VERBOSE_IMPORTANT
 207 #define LOG(str)           DOLOG(log_text(str))
 208 #define LOG1(str,a)        DOLOG(dolog(str,a))
 209 #define LOG2(str,a,b)      DOLOG(dolog(str,a,b))
 210 #define LOG3(str,a,b,c)    DOLOG(dolog(str,a,b,c))
 211 #define LOGIF(cond,str)    DOLOG(do {if (cond) log_text(str);} while(0))
 212 #ifdef  TYPEINFO_DEBUG
 213 #define LOGINFO(info)      DOLOG(do {typeinfo_print_short(typecheck_logfile,(info));log_finish();} while(0))
 214 #else
 215 #define LOGINFO(info)
 216 #define typevectorset_print(x,y,z)
 217 #endif
 218 #define LOGFLUSH           DOLOG(fflush(typecheck_logfile))
 219 #define LOGNL              DOLOG(log_finish())
 220 #define LOGSTR(str)        DOLOG(log_print(str))
 221 #define LOGSTR1(str,a)     DOLOG(log_print(str,a))
 222 #define LOGSTR2(str,a,b)   DOLOG(log_print(str,a,b))
 223 #define LOGSTR3(str,a,b,c) DOLOG(log_print(str,a,b,c))
 224 #define LOGNAME(c)         DOLOG(log_message_utf("class: ",(IS_CLASSREF(c) ? c.ref->name : c.cls->name)))
 225 #define LOGMETHOD(str,m)   DOLOG(log_message_method(str,m))
 226 #else
 227 #define LOG(str)
 228 #define LOG1(str,a)
 229 #define LOG2(str,a,b)
 230 #define LOG3(str,a,b,c)
 231 #define LOGIF(cond,str)
 232 #define LOGINFO(info)
 233 #define LOGFLUSH
 234 #define LOGNL
 235 #define LOGSTR(str)
 236 #define LOGSTR1(str,a)
 237 #define LOGSTR2(str,a,b)
 238 #define LOGSTR3(str,a,b,c)
 239 #define LOGNAME(c)
 240 #define LOGMETHOD(str,m)
 241 #endif
 242
 243 #ifdef TYPECHECK_VERBOSE_IMPORTANT
 244 #define LOGimp(str)     DOLOG(log_text(str))
 245 #define LOGimpSTR(str)  DOLOG(log_print(str))
 246 #else
 247 #define LOGimp(str)
 248 #define LOGimpSTR(str)
 249 #endif
 250
 251 #if defined(TYPECHECK_VERBOSE) || defined(TYPECHECK_VERBOSE_IMPORTANT)
 252
 253 #include <stdio.h>
 254
 255 static
 256 void
 257 typestack_print(FILE *file,stackptr stack)
 258 {
 259 #ifdef TYPEINFO_DEBUG
 260     while (stack) {
 261                 /*fprintf(file,"<%p>",stack);*/
 262         typeinfo_print_stacktype(file,stack->type,&(stack->typeinfo));
 263         stack = stack->prev;
 264         if (stack) fprintf(file," ");
 265     }
 266 #endif
 267 }
 268
 269 static
 270 void
 271 typestate_print(FILE *file,stackptr instack,typevector *localset,int size)
 272 {
 273     fprintf(file,"Stack: ");
 274     typestack_print(file,instack);
 275     fprintf(file," Locals:");
 276     typevectorset_print(file,localset,size);
 277 }
 278
 279 #endif
 280
 281 /****************************************************************************/
 282 /* STATISTICS                                                               */
 283 /****************************************************************************/
 284
 285 #ifdef TYPECHECK_DEBUG
 286 /*#define TYPECHECK_STATISTICS*/
 287 #endif
 288
 289 #ifdef TYPECHECK_STATISTICS
 290 #define STAT_ITERATIONS  10
 291 #define STAT_BLOCKS      10
 292 #define STAT_LOCALS      16
 293
 294 static int stat_typechecked = 0;
 295 static int stat_typechecked_jsr = 0;
 296 static int stat_methods_with_handlers = 0;
 297 static int stat_methods_maythrow = 0;
 298 static int stat_iterations[STAT_ITERATIONS+1] = { 0 };
 299 static int stat_reached = 0;
 300 static int stat_copied = 0;
 301 static int stat_merged = 0;
 302 static int stat_merging_changed = 0;
 303 static int stat_backwards = 0;
 304 static int stat_blocks[STAT_BLOCKS+1] = { 0 };
 305 static int stat_locals[STAT_LOCALS+1] = { 0 };
 306 static int stat_ins = 0;
 307 static int stat_ins_maythrow = 0;
 308 static int stat_ins_stack = 0;
 309 static int stat_ins_field = 0;
 310 static int stat_ins_field_unresolved = 0;
 311 static int stat_ins_field_uninitialized = 0;
 312 static int stat_ins_invoke = 0;
 313 static int stat_ins_invoke_unresolved = 0;
 314 static int stat_ins_primload = 0;
 315 static int stat_ins_aload = 0;
 316 static int stat_ins_builtin = 0;
 317 static int stat_ins_builtin_gen = 0;
 318 static int stat_ins_branch = 0;
 319 static int stat_ins_switch = 0;
 320 static int stat_ins_primitive_return = 0;
 321 static int stat_ins_areturn = 0;
 322 static int stat_ins_areturn_unresolved = 0;
 323 static int stat_ins_athrow = 0;
 324 static int stat_ins_athrow_unresolved = 0;
 325 static int stat_ins_unchecked = 0;
 326 static int stat_handlers_reached = 0;
 327 static int stat_savedstack = 0;
 328
 329 #define TYPECHECK_MARK(var)   ((var) = true)
 330 #define TYPECHECK_COUNT(cnt)  (cnt)++
 331 #define TYPECHECK_COUNTIF(cond,cnt)  do{if(cond) (cnt)++;} while(0)
 332 #define TYPECHECK_COUNT_FREQ(array,val,limit) \
 333         do {                                                                      \
 334                 if ((val) < (limit)) (array)[val]++;  \
 335                 else (array)[limit]++;                            \
 336         } while (0)
 337
 338 static void print_freq(FILE *file,int *array,int limit)
 339 {
 340         int i;
 341         for (i=0; i<limit; ++i)
 342                 fprintf(file,"      %3d: %8d\n",i,array[i]);
 343         fprintf(file,"    >=%3d: %8d\n",limit,array[limit]);
 344 }
 345
 346 void typecheck_print_statistics(FILE *file) {
 347         fprintf(file,"typechecked methods: %8d\n",stat_typechecked);
 348         fprintf(file,"    with JSR       : %8d\n",stat_typechecked_jsr);
 349         fprintf(file,"    with handler(s): %8d\n",stat_methods_with_handlers);
 350         fprintf(file,"    with throw(s)  : %8d\n",stat_methods_maythrow);
 351         fprintf(file,"reached blocks     : %8d\n",stat_reached);
 352         fprintf(file,"copied states      : %8d\n",stat_copied);
 353         fprintf(file,"merged states      : %8d\n",stat_merged);
 354         fprintf(file,"merging changed    : %8d\n",stat_merging_changed);
 355         fprintf(file,"backwards branches : %8d\n",stat_backwards);
 356         fprintf(file,"handlers reached   : %8d\n",stat_handlers_reached);
 357         fprintf(file,"saved stack (times): %8d\n",stat_savedstack);
 358         fprintf(file,"instructions       : %8d\n",stat_ins);
 359         fprintf(file,"    stack          : %8d\n",stat_ins_stack);
 360         fprintf(file,"    field access   : %8d\n",stat_ins_field);
 361         fprintf(file,"      (unresolved) : %8d\n",stat_ins_field_unresolved);
 362         fprintf(file,"      (uninit.)    : %8d\n",stat_ins_field_uninitialized);
 363         fprintf(file,"    invocations    : %8d\n",stat_ins_invoke);
 364         fprintf(file,"      (unresolved) : %8d\n",stat_ins_invoke_unresolved);
 365         fprintf(file,"    load primitive : (currently not counted) %8d\n",stat_ins_primload);
 366         fprintf(file,"    load address   : %8d\n",stat_ins_aload);
 367         fprintf(file,"    builtins       : %8d\n",stat_ins_builtin);
 368         fprintf(file,"        generic    : %8d\n",stat_ins_builtin_gen);
 369         fprintf(file,"    branches       : %8d\n",stat_ins_branch);
 370         fprintf(file,"    switches       : %8d\n",stat_ins_switch);
 371         fprintf(file,"    prim. return   : %8d\n",stat_ins_primitive_return);
 372         fprintf(file,"    areturn        : %8d\n",stat_ins_areturn);
 373         fprintf(file,"      (unresolved) : %8d\n",stat_ins_areturn_unresolved);
 374         fprintf(file,"    athrow         : %8d\n",stat_ins_athrow);
 375         fprintf(file,"      (unresolved) : %8d\n",stat_ins_athrow_unresolved);
 376         fprintf(file,"    unchecked      : %8d\n",stat_ins_unchecked);
 377         fprintf(file,"    maythrow       : %8d\n",stat_ins_maythrow);
 378         fprintf(file,"iterations used:\n");
 379         print_freq(file,stat_iterations,STAT_ITERATIONS);
 380         fprintf(file,"basic blocks per method / 10:\n");
 381         print_freq(file,stat_blocks,STAT_BLOCKS);
 382         fprintf(file,"locals:\n");
 383         print_freq(file,stat_locals,STAT_LOCALS);
 384 }
 385
 386 #else
 387
 388 #define TYPECHECK_COUNT(cnt)
 389 #define TYPECHECK_MARK(var)
 390 #define TYPECHECK_COUNTIF(cond,cnt)
 391 #define TYPECHECK_COUNT_FREQ(array,val,limit)
 392 #endif
 393
 394 /****************************************************************************/
 395 /* MACROS FOR THROWING EXCEPTIONS                                           */
 396 /****************************************************************************/
 397
 398 #define TYPECHECK_VERIFYERROR_ret(m,msg,retval) \
 399     do { \
 400         *exceptionptr = new_verifyerror((m), (msg)); \
 401         return (retval); \
 402     } while (0)
 403
 404 #define TYPECHECK_VERIFYERROR_main(msg)  TYPECHECK_VERIFYERROR_ret(state.m,(msg),NULL)
 405 #define TYPECHECK_VERIFYERROR_bool(msg)  TYPECHECK_VERIFYERROR_ret(state->m,(msg),false)
 406
 407 /****************************************************************************/
 408 /* MACROS FOR STACK SLOT TYPE CHECKING                                      */
 409 /****************************************************************************/
 410
 411 #define TYPECHECK_CHECK_TYPE(sp,tp,msg) \
 412     do { \
 413                 if ((sp)->type != (tp)) { \
 414                 *exceptionptr = new_verifyerror(state->m, (msg)); \
 415                 return false; \
 416                 } \
 417     } while (0)
 418
 419 #define TYPECHECK_INT(sp)  TYPECHECK_CHECK_TYPE(sp,TYPE_INT,"Expected to find integer on stack")
 420 #define TYPECHECK_LNG(sp)  TYPECHECK_CHECK_TYPE(sp,TYPE_LNG,"Expected to find long on stack")
 421 #define TYPECHECK_FLT(sp)  TYPECHECK_CHECK_TYPE(sp,TYPE_FLT,"Expected to find float on stack")
 422 #define TYPECHECK_DBL(sp)  TYPECHECK_CHECK_TYPE(sp,TYPE_DBL,"Expected to find double on stack")
 423 #define TYPECHECK_ADR(sp)  TYPECHECK_CHECK_TYPE(sp,TYPE_ADR,"Expected to find object on stack")
 424
 425 /****************************************************************************/
 426 /* VERIFIER STATE STRUCT                                                    */
 427 /****************************************************************************/
 428
 429 /* verifier_state - This structure keeps the current state of the      */
 430 /* bytecode verifier for passing it between verifier functions.        */
 431
 432 typedef struct verifier_state {
 433     stackptr curstack;      /* input stack top for current instruction */
 434     instruction *iptr;               /* pointer to current instruction */
 435     basicblock *bptr;                /* pointer to current basic block */
 436
 437         methodinfo *m;                               /* the current method */
 438         codegendata *cd;                 /* codegendata for current method */
 439         registerdata *rd;               /* registerdata for current method */
 440
 441         s4 numlocals;                         /* number of local variables */
 442         s4 validlocals;                /* number of Java-accessible locals */
 443         void *localbuf;       /* local variable types for each block start */
 444         typevector *localset;        /* typevector set for local variables */
 445         typedescriptor returntype;    /* return type of the current method */
 446
 447         stackptr savedstackbuf;             /* buffer for saving the stack */
 448         stackptr savedstack;             /* saved instack of current block */
 449
 450     exceptiontable **handlers;            /* active exception handlers */
 451         stackelement excstack;           /* instack for exception handlers */
 452
 453     bool repeat;            /* if true, blocks are iterated over again */
 454     bool initmethod;             /* true if this is an "<init>" method */
 455         bool jsrencountered;                 /* true if we there was a JSR */
 456
 457 #ifdef TYPECHECK_STATISTICS
 458         bool stat_maythrow;          /* at least one instruction may throw */
 459 #endif
 460 } verifier_state;
 461
 462 /****************************************************************************/
 463 /* TYPESTACK MACROS AND FUNCTIONS                                           */
 464 /*                                                                          */
 465 /* These macros and functions act on the 'type stack', which is a shorthand */
 466 /* for the types of the stackslots of the current stack. The type of a      */
 467 /* stack slot is usually described by a TYPE_* constant and -- for TYPE_ADR */
 468 /* -- by the typeinfo of the slot. The only thing that makes the type stack */
 469 /* more complicated are returnAddresses of local subroutines, because a     */
 470 /* single stack slot may contain a set of more than one possible return     */
 471 /* address. This is handled by 'return address sets'. A return address set  */
 472 /* is kept as a linked list dangling off the typeinfo of the stack slot.    */
 473 /****************************************************************************/
 474
 475 #define TYPESTACK_IS_RETURNADDRESS(sptr) \
 476             TYPE_IS_RETURNADDRESS((sptr)->type,(sptr)->typeinfo)
 477
 478 #define TYPESTACK_RETURNADDRESSSET(sptr) \
 479             ((typeinfo_retaddr_set*)TYPEINFO_RETURNADDRESS((sptr)->typeinfo))
 480
 481 #define RETURNADDRESSSET_SEEK(set,pos) \
 482             do {int i; for (i=pos;i--;) set=set->alt;} while(0)
 483
 484 /* typestack_copy **************************************************************
 485
 486    Copy the types on the given stack to the destination stack.
 487
 488    This function does a straight forward copy except for returnAddress types.
 489    For returnAddress slots only the return addresses corresponding to
 490    typevectors in the SELECTED set are copied.
 491
 492    IN:
 493            state............current verifier state
 494            y................stack with types to copy
 495            selected.........set of selected typevectors
 496
 497    OUT:
 498        *dst.............the destination stack
 499
 500    RETURN VALUE:
 501        true.............success
 502            false............an exception has been thrown
 503
 504 *******************************************************************************/
 505
 506 static bool
 507 typestack_copy(verifier_state *state,stackptr dst,stackptr y,typevector *selected)
 508 {
 509         typevector *sel;
 510         typeinfo_retaddr_set *sety;
 511         typeinfo_retaddr_set *new;
 512         typeinfo_retaddr_set **next;
 513         int k;
 514
 515         for (;dst; dst=dst->prev, y=y->prev) {
 516                 /* XXX only check the following two in debug mode? */
 517                 if (!y) {
 518                         *exceptionptr = new_verifyerror(state->m,"Stack depth mismatch");
 519                         return false;
 520                 }
 521                 if (dst->type != y->type) {
 522                         *exceptionptr = new_verifyerror(state->m,"Stack type mismatch");
 523                         return false;
 524                 }
 525                 LOG3("copy %p -> %p (type %d)",y,dst,dst->type);
 526                 if (dst->type == TYPE_ADDRESS) {
 527                         if (TYPEINFO_IS_PRIMITIVE(y->typeinfo)) {
 528                                 /* We copy the returnAddresses from the selected
 529                                  * states only. */
 530
 531                                 LOG("copying returnAddress");
 532                                 sety = TYPESTACK_RETURNADDRESSSET(y);
 533                                 next = &new;
 534                                 for (k=0,sel=selected; sel; sel=sel->alt) {
 535                                         LOG1("selected k=%d",sel->k);
 536                                         while (k<sel->k) {
 537                                                 sety = sety->alt;
 538                                                 k++;
 539                                         }
 540                                         *next = DNEW(typeinfo_retaddr_set);
 541                                         (*next)->addr = sety->addr;
 542                                         next = &((*next)->alt);
 543                                 }
 544                                 *next = NULL;
 545                                 TYPEINFO_INIT_RETURNADDRESS(dst->typeinfo,new);
 546                         }
 547                         else {
 548                                 TYPEINFO_CLONE(y->typeinfo,dst->typeinfo);
 549                         }
 550                 }
 551         }
 552         if (y) {
 553                 *exceptionptr = new_verifyerror(state->m,"Stack depth mismatch");
 554                 return false;
 555         }
 556         return true;
 557 }
 558
 559 /* typestack_put_retaddr *******************************************************
 560
 561    Put a returnAddress into a stack slot.
 562
 563    The stack slot receives a set of return addresses with as many members as
 564    there are typevectors in the local variable set.
 565
 566    IN:
 567            retaddr..........the returnAddress to set (a basicblock *)
 568            loc..............the local variable typevector set
 569
 570    OUT:
 571        *dst.............the destination stack slot
 572
 573 *******************************************************************************/
 574
 575 static void
 576 typestack_put_retaddr(stackptr dst,void *retaddr,typevector *loc)
 577 {
 578         TYPECHECK_ASSERT(dst->type == TYPE_ADDRESS);
 579
 580         TYPEINFO_INIT_RETURNADDRESS(dst->typeinfo,NULL);
 581         for (;loc; loc=loc->alt) {
 582                 typeinfo_retaddr_set *set = DNEW(typeinfo_retaddr_set);
 583                 set->addr = retaddr;
 584                 set->alt = TYPESTACK_RETURNADDRESSSET(dst);
 585                 TYPEINFO_INIT_RETURNADDRESS(dst->typeinfo,set);
 586         }
 587 }
 588
 589 /* typestack_collapse **********************************************************
 590
 591    Collapse the given stack by shortening all return address sets to a single
 592    member.
 593
 594    OUT:
 595        *dst.............the destination stack to collapse
 596
 597 *******************************************************************************/
 598
 599 static void
 600 typestack_collapse(stackptr dst)
 601 {
 602         for (; dst; dst = dst->prev) {
 603                 if (TYPESTACK_IS_RETURNADDRESS(dst))
 604                         TYPESTACK_RETURNADDRESSSET(dst)->alt = NULL;
 605         }
 606 }
 607
 608 /* typestack_merge *************************************************************
 609
 610    Merge the types on one stack into the destination stack.
 611
 612    IN:
 613        state............current state of the verifier
 614            dst..............the destination stack
 615            y................the second stack
 616
 617    OUT:
 618        *dst.............receives the result of the stack merge
 619
 620    RETURN VALUE:
 621        typecheck_TRUE...*dst has been modified
 622            typecheck_FALSE..*dst has not been modified
 623            typecheck_FAIL...an exception has been thrown
 624
 625 *******************************************************************************/
 626
 627 static typecheck_result
 628 typestack_merge(verifier_state *state,stackptr dst,stackptr y)
 629 {
 630         typecheck_result r;
 631         bool changed = false;
 632
 633         for (; dst; dst = dst->prev, y=y->prev) {
 634                 if (!y) {
 635                         *exceptionptr = new_verifyerror(state->m,"Stack depth mismatch");
 636                         return typecheck_FAIL;
 637                 }
 638                 if (dst->type != y->type) {
 639                         *exceptionptr = new_verifyerror(state->m,"Stack type mismatch");
 640                         return typecheck_FAIL;
 641                 }
 642                 if (dst->type == TYPE_ADDRESS) {
 643                         if (TYPEINFO_IS_PRIMITIVE(dst->typeinfo)) {
 644                                 /* dst has returnAddress type */
 645                                 if (!TYPEINFO_IS_PRIMITIVE(y->typeinfo)) {
 646                                         *exceptionptr = new_verifyerror(state->m,"Merging returnAddress with reference");
 647                                         return typecheck_FAIL;
 648                                 }
 649                         }
 650                         else {
 651                                 /* dst has reference type */
 652                                 if (TYPEINFO_IS_PRIMITIVE(y->typeinfo)) {
 653                                         *exceptionptr = new_verifyerror(state->m,"Merging reference with returnAddress");
 654                                         return typecheck_FAIL;
 655                                 }
 656                                 r = typeinfo_merge(state->m,&(dst->typeinfo),&(y->typeinfo));
 657                                 if (r == typecheck_FAIL)
 658                                         return r;
 659                                 changed |= r;
 660                         }
 661                 }
 662         }
 663         if (y) {
 664                 *exceptionptr = new_verifyerror(state->m,"Stack depth mismatch");
 665                 return typecheck_FAIL;
 666         }
 667         return changed;
 668 }
 669
 670 /* typestack_add ***************************************************************
 671
 672    Add the return addresses in the given stack at a given k-index to the
 673    corresponding return address sets in the destination stack.
 674
 675    IN:
 676            dst..............the destination stack
 677            y................the second stack
 678            ky...............the k-index which should be selected from the Y stack
 679
 680    OUT:
 681        *dst.............receives the result of adding the addresses
 682
 683 *******************************************************************************/
 684
 685 static void
 686 typestack_add(stackptr dst,stackptr y,int ky)
 687 {
 688         typeinfo_retaddr_set *setd;
 689         typeinfo_retaddr_set *sety;
 690
 691         for (; dst; dst = dst->prev, y=y->prev) {
 692                 if (TYPESTACK_IS_RETURNADDRESS(dst)) {
 693                         setd = TYPESTACK_RETURNADDRESSSET(dst);
 694                         sety = TYPESTACK_RETURNADDRESSSET(y);
 695                         RETURNADDRESSSET_SEEK(sety,ky);
 696                         while (setd->alt)
 697                                 setd=setd->alt;
 698                         setd->alt = DNEW(typeinfo_retaddr_set);
 699                         setd->alt->addr = sety->addr;
 700                         setd->alt->alt = NULL;
 701                 }
 702         }
 703 }
 704
 705 /* typestack_separable_with ****************************************************
 706
 707    This function answers the question: If variant 'kb' of typestack 'b' is
 708    added to typestack 'a', will the result be separable?
 709
 710    A typestack is called 'separable' if it has at least one slot of type
 711    returnAddress that contains at least two different return addresses.
 712    (ie. a RET using the value in this slot could go to more than one target)
 713
 714    IN:
 715            a................the first typestack
 716            b................the second typestack
 717            kb...............the k-index of the variant that should be selected
 718                             from typestack 'b'
 719
 720    OUT:
 721        true.............the result would be separable
 722            false............the result would not be separable
 723
 724    PRE-CONDITION:
 725        'a' and 'b' are assumed to have passed typestack_canmerge!
 726
 727 *******************************************************************************/
 728
 729 static bool
 730 typestack_separable_with(stackptr a,stackptr b,int kb)
 731 {
 732         typeinfo_retaddr_set *seta;
 733         typeinfo_retaddr_set *setb;
 734
 735         for (; a; a = a->prev, b = b->prev) {
 736                 TYPECHECK_ASSERT(b);
 737                 if (TYPESTACK_IS_RETURNADDRESS(a)) {
 738                         TYPECHECK_ASSERT(TYPESTACK_IS_RETURNADDRESS(b));
 739                         seta = TYPESTACK_RETURNADDRESSSET(a);
 740                         setb = TYPESTACK_RETURNADDRESSSET(b);
 741                         RETURNADDRESSSET_SEEK(setb,kb);
 742
 743                         for (;seta;seta=seta->alt)
 744                                 if (seta->addr != setb->addr) return true;
 745                 }
 746         }
 747         TYPECHECK_ASSERT(!b);
 748         return false;
 749 }
 750
 751 /* typestack_separable_from ****************************************************
 752
 753    This function answers the question: Is variant 'ka' of typestack 'a'
 754    separable from variant 'kb' of typestack 'b'?
 755
 756    Two variants of typestacks are called 'separable' from each other, if there
 757    is at least one slot for which the variants contain different return addresses.
 758    (ie. a RET using the value in this slot would go to one target in the first
 759    variant and to another target in the second variant)
 760
 761    IN:
 762            a................the first typestack
 763            ka...............the k-index of the variant that should be selected
 764                             from typestack 'a'
 765            b................the second typestack
 766            kb...............the k-index of the variant that should be selected
 767                             from typestack 'b'
 768
 769    OUT:
 770        true.............the variants are separable
 771            false............the variants are not separable
 772
 773    PRE-CONDITION:
 774        'a' and 'b' are assumed to have passed typestack_canmerge!
 775
 776 *******************************************************************************/
 777
 778 static bool
 779 typestack_separable_from(stackptr a,int ka,stackptr b,int kb)
 780 {
 781         typeinfo_retaddr_set *seta;
 782         typeinfo_retaddr_set *setb;
 783
 784         for (; a; a = a->prev, b = b->prev) {
 785                 TYPECHECK_ASSERT(b);
 786                 if (TYPESTACK_IS_RETURNADDRESS(a)) {
 787                         TYPECHECK_ASSERT(TYPESTACK_IS_RETURNADDRESS(b));
 788                         seta = TYPESTACK_RETURNADDRESSSET(a);
 789                         setb = TYPESTACK_RETURNADDRESSSET(b);
 790                         RETURNADDRESSSET_SEEK(seta,ka);
 791                         RETURNADDRESSSET_SEEK(setb,kb);
 792
 793                         if (seta->addr != setb->addr) return true;
 794                 }
 795         }
 796         TYPECHECK_ASSERT(!b);
 797         return false;
 798 }
 799
 800 /****************************************************************************/
 801 /* TYPESTATE FUNCTIONS                                                      */
 802 /*                                                                          */
 803 /* These functions act on the 'type state', which comprises:                */
 804 /*     - the types of the stack slots of the current stack                  */
 805 /*     - the set of type vectors describing the local variables             */
 806 /****************************************************************************/
 807
 808 /* typestate_merge *************************************************************
 809
 810    Merge the types of one state into the destination state.
 811
 812    IN:
 813        state............current state of the verifier
 814            deststack........the destination stack
 815            destloc..........the destination set of local variable typevectors
 816            ystack...........the second stack
 817            yloc.............the second set of local variable typevectors
 818
 819    OUT:
 820        *deststack.......receives the result of the stack merge
 821            *destloc.........receives the result of the local variable merge
 822
 823    RETURN VALUE:
 824        typecheck_TRUE...destination state has been modified
 825            typecheck_FALSE..destination state has not been modified
 826            typecheck_FAIL...an exception has been thrown
 827
 828 *******************************************************************************/
 829
 830 static typecheck_result
 831 typestate_merge(verifier_state *state,
 832                                 stackptr deststack,typevector *destloc,
 833                                 stackptr ystack,typevector *yloc)
 834 {
 835         typevector *dvec,*yvec;
 836         int kd,ky;
 837         bool changed = false;
 838         typecheck_result r;
 839
 840         LOG("merge:");
 841         LOGSTR("dstack: "); DOLOG(typestack_print(typecheck_logfile,deststack)); LOGNL;
 842         LOGSTR("ystack: "); DOLOG(typestack_print(typecheck_logfile,ystack)); LOGNL;
 843         LOGSTR("dloc  : "); DOLOG(typevectorset_print(typecheck_logfile,destloc,state->numlocals)); LOGNL;
 844         LOGSTR("yloc  : "); DOLOG(typevectorset_print(typecheck_logfile,yloc,state->numlocals)); LOGNL;
 845         LOGFLUSH;
 846
 847         /* The stack is always merged. If there are returnAddresses on
 848          * the stack they are ignored in this step. */
 849
 850         r = typestack_merge(state,deststack,ystack);
 851         if (r == typecheck_FAIL)
 852                 return r;
 853         changed |= r;
 854
 855         /* If there have not been any JSRs we just have a single typevector merge */
 856         if (!state->jsrencountered) {
 857                 r = typevector_merge(state->m,destloc,yloc,state->numlocals);
 858                 if (r == typecheck_FAIL)
 859                         return r;
 860                 return changed | r;
 861         }
 862
 863         for (yvec=yloc; yvec; yvec=yvec->alt) {
 864                 ky = yvec->k;
 865
 866                 /* Check if the typestates (deststack,destloc) will be
 867                  * separable when (ystack,yvec) is added. */
 868
 869                 if (!typestack_separable_with(deststack,ystack,ky)
 870                         && !typevectorset_separable_with(destloc,yvec,state->numlocals))
 871                 {
 872                         /* No, the resulting set won't be separable, thus we
 873                          * may merge all states in (deststack,destloc) and
 874                          * (ystack,yvec). */
 875
 876                         typestack_collapse(deststack);
 877                         if (typevectorset_collapse(state->m,destloc,state->numlocals) == typecheck_FAIL)
 878                                 return typecheck_FAIL;
 879                         if (typevector_merge(state->m,destloc,yvec,state->numlocals) == typecheck_FAIL)
 880                                 return typecheck_FAIL;
 881                 }
 882                 else {
 883                         /* Yes, the resulting set will be separable. Thus we check
 884                          * if we may merge (ystack,yvec) with a single state in
 885                          * (deststack,destloc). */
 886
 887                         for (dvec=destloc,kd=0; dvec; dvec=dvec->alt, kd++) {
 888                                 if (!typestack_separable_from(ystack,ky,deststack,kd)
 889                                         && !typevector_separable_from(yvec,dvec,state->numlocals))
 890                                 {
 891                                         /* The typestate (ystack,yvec) is not separable from
 892                                          * (deststack,dvec) by any returnAddress. Thus we may
 893                                          * merge the states. */
 894
 895                                         r = typevector_merge(state->m,dvec,yvec,state->numlocals);
 896                                         if (r == typecheck_FAIL)
 897                                                 return r;
 898                                         changed |= r;
 899
 900                                         goto merged;
 901                                 }
 902                         }
 903
 904                         /* The typestate (ystack,yvec) is separable from all typestates
 905                          * (deststack,destloc). Thus we must add this state to the
 906                          * result set. */
 907
 908                         typestack_add(deststack,ystack,ky);
 909                         typevectorset_add(destloc,yvec,state->numlocals);
 910                         changed = true;
 911                 }
 912
 913         merged:
 914                 ;
 915         }
 916
 917         LOG("result:");
 918         LOGSTR("dstack: "); DOLOG(typestack_print(typecheck_logfile,deststack)); LOGNL;
 919         LOGSTR("dloc  : "); DOLOG(typevectorset_print(typecheck_logfile,destloc,state->numlocals)); LOGNL;
 920         LOGFLUSH;
 921
 922         return changed;
 923 }
 924
 925 /* typestate_reach *************************************************************
 926
 927    Reach a destination block and propagate stack and local variable types
 928
 929    IN:
 930        state............current state of the verifier
 931            destblock........destination basic block
 932            ystack...........stack to propagate
 933            yloc.............set of local variable typevectors to propagate
 934
 935    OUT:
 936        state->repeat....set to true if the verifier must iterate again
 937                             over the basic blocks
 938
 939    RETURN VALUE:
 940        true.............success
 941            false............an exception has been thrown
 942
 943 *******************************************************************************/
 944
 945 static bool
 946 typestate_reach(verifier_state *state,
 947                                 basicblock *destblock,
 948                                 stackptr ystack,typevector *yloc)
 949 {
 950         typevector *destloc;
 951         int destidx;
 952         bool changed = false;
 953         typecheck_result r;
 954
 955         LOG1("reaching block L%03d",destblock->debug_nr);
 956         TYPECHECK_COUNT(stat_reached);
 957
 958         destidx = destblock - state->cd->method->basicblocks;
 959         destloc = MGET_TYPEVECTOR(state->localbuf,destidx,state->numlocals);
 960
 961         /* When branching backwards we have to check for uninitialized objects */
 962
 963         if (destblock <= state->bptr) {
 964                 stackptr sp;
 965                 int i;
 966
 967                 /* XXX FIXME FOR INLINING */
 968
 969                 if (!useinlining) {
 970                         TYPECHECK_COUNT(stat_backwards);
 971                         LOG("BACKWARDS!");
 972                         for (sp = ystack; sp; sp=sp->prev)
 973                                 if (sp->type == TYPE_ADR &&
 974                                 TYPEINFO_IS_NEWOBJECT(sp->typeinfo)) {
 975                                         /*printf("current: %d, dest: %d\n", state->bptr->debug_nr, destblock->debug_nr);*/
 976                                         *exceptionptr = new_verifyerror(state->m,"Branching backwards with uninitialized object on stack");
 977                                         return false;
 978                                 }
 979
 980                         for (i=0; i<state->numlocals; ++i)
 981                                 if (yloc->td[i].type == TYPE_ADR &&
 982                                         TYPEINFO_IS_NEWOBJECT(yloc->td[i].info)) {
 983                                         *exceptionptr = new_verifyerror(state->m,"Branching backwards with uninitialized object in local variable");
 984                                         return false;
 985                                 }
 986                 }
 987         }
 988
 989         if (destblock->flags == BBTYPECHECK_UNDEF) {
 990                 /* The destblock has never been reached before */
 991
 992                 TYPECHECK_COUNT(stat_copied);
 993                 LOG1("block (index %04d) reached first time",destidx);
 994
 995                 if (!typestack_copy(state,destblock->instack,ystack,yloc))
 996                         return false;
 997                 typevectorset_copy_inplace(yloc,destloc,state->numlocals);
 998                 changed = true;
 999         }
1000         else {
1001                 /* The destblock has already been reached before */
1002
1003                 TYPECHECK_COUNT(stat_merged);
1004                 LOG1("block (index %04d) reached before",destidx);
1005
1006                 r = typestate_merge(state,destblock->instack,destloc,ystack,yloc);
1007                 if (r == typecheck_FAIL)
1008                         return false;
1009                 changed = r;
1010                 TYPECHECK_COUNTIF(changed,stat_merging_changed);
1011         }
1012
1013         if (changed) {
1014                 LOG("changed!");
1015                 destblock->flags = BBTYPECHECK_REACHED;
1016                 if (destblock <= state->bptr) {
1017                         LOG("REPEAT!");
1018                         state->repeat = true;
1019                 }
1020         }
1021         return true;
1022 }
1023
1024 /* typestate_ret ***************************************************************
1025
1026    Reach the destinations of a RET instruction.
1027
1028    IN:
1029        state............current state of the verifier
1030            retindex.........index of local variable containing the returnAddress
1031
1032    OUT:
1033        state->repeat....set to true if the verifier must iterate again
1034                             over the basic blocks
1035
1036    RETURN VALUE:
1037        true.............success
1038            false............an exception has been thrown
1039
1040 *******************************************************************************/
1041
1042 static bool
1043 typestate_ret(verifier_state *state,int retindex)
1044 {
1045         typevector *yvec;
1046         typevector *selected;
1047         basicblock *destblock;
1048
1049         for (yvec=state->localset; yvec; ) {
1050                 if (!TYPEDESC_IS_RETURNADDRESS(yvec->td[retindex])) {
1051                         *exceptionptr = new_verifyerror(state->m,"Illegal instruction: RET on non-returnAddress");
1052                         return false;
1053                 }
1054
1055                 destblock = (basicblock*) TYPEINFO_RETURNADDRESS(yvec->td[retindex].info);
1056
1057                 selected = typevectorset_select(&yvec,retindex,destblock);
1058
1059                 if (!typestate_reach(state,destblock,state->curstack,selected))
1060                         return false;
1061         }
1062         return true;
1063 }
1064
1065 /* typestate_save_instack ******************************************************
1066
1067    Save the input stack of the current basic block in the "savedstackbuf"
1068    of the verifier state.
1069
1070    This function must be called before an instruction modifies a stack slot
1071    that happens to be part of the instack of the current block. In such
1072    cases the instack of the block must be saved, and restored at the end
1073    of the analysis of this basic block, so that the instack again reflects
1074    the *input* to this basic block (and does not randomly contain types
1075    that appear within the block).
1076
1077    IN:
1078        state............current state of the verifier
1079
1080 *******************************************************************************/
1081
1082 static void
1083 typestate_save_instack(verifier_state *state)
1084 {
1085         stackptr sp;
1086         stackptr dest;
1087         s4 i;
1088
1089         LOG("saving input stack types");
1090         if (!state->savedstackbuf) {
1091                 LOG("allocating savedstack buffer");
1092                 state->savedstackbuf = DMNEW(stackelement, state->cd->maxstack);
1093                 state->savedstackbuf->prev = NULL;
1094                 for (i = 1; i < state->cd->maxstack; ++i)
1095                         state->savedstackbuf[i].prev = state->savedstackbuf+(i-1);
1096         }
1097         sp = state->savedstack = state->bptr->instack;
1098         dest = state->bptr->instack = state->savedstackbuf + (state->bptr->indepth-1);
1099
1100         for(; sp; sp=sp->prev, dest=dest->prev) {
1101                 dest->type = sp->type;
1102                 TYPEINFO_COPY(sp->typeinfo,dest->typeinfo);
1103         }
1104 }
1105
1106 /* typestate_restore_instack ***************************************************
1107
1108    Restore the input stack of the current basic block that has been previously
1109    saved by `typestate_save_instack`.
1110
1111    IN:
1112        state............current state of the verifier
1113
1114 *******************************************************************************/
1115
1116 static void
1117 typestate_restore_instack(verifier_state *state)
1118 {
1119         stackptr sp;
1120         stackptr dest;
1121
1122         TYPECHECK_COUNT(stat_savedstack);
1123         LOG("restoring saved instack");
1124
1125         sp = state->bptr->instack;
1126         dest = state->savedstack;
1127         for(; sp; sp=sp->prev, dest=dest->prev) {
1128                 dest->type = sp->type;
1129                 TYPEINFO_COPY(sp->typeinfo,dest->typeinfo);
1130         }
1131
1132         state->bptr->instack = state->savedstack;
1133         state->savedstack = NULL;
1134 }
1135
1136 /****************************************************************************/
1137 /* MISC MACROS                                                              */
1138 /****************************************************************************/
1139
1140 #define COPYTYPE(source,dest)   \
1141         {if ((source)->type == TYPE_ADR)                                                                \
1142                         TYPEINFO_COPY((source)->typeinfo,(dest)->typeinfo);}
1143
1144 #define ISBUILTIN(v)   (bte->fp == (functionptr) (v))
1145
1146 /* verify_invocation ***********************************************************
1147
1148    Verify an ICMD_INVOKE* instruction.
1149
1150    IN:
1151        state............the current state of the verifier
1152
1153    RETURN VALUE:
1154        true.............successful verification,
1155            false............an exception has been thrown.
1156
1157 *******************************************************************************/
1158
1159 static bool
1160 verify_invocation(verifier_state *state)
1161 {
1162         unresolved_method *um;      /* struct describing the called method */
1163         constant_FMIref *mref;           /* reference to the called method */
1164         methoddesc *md;                 /* descriptor of the called method */
1165         bool specialmethod;            /* true if a <...> method is called */
1166         int opcode;                                   /* invocation opcode */
1167         bool callinginit;                      /* true if <init> is called */
1168         instruction *ins;
1169         classref_or_classinfo initclass;
1170         typedesc *td;
1171         stackelement *stack;                    /* temporary stack pointer */
1172         stackelement *dst;               /* result stack of the invocation */
1173         int i;                                                  /* counter */
1174     u1 rtype;                          /* return type of called method */
1175
1176         um = (unresolved_method *) state->iptr[0].target;
1177         mref = um->methodref;
1178         md = mref->parseddesc.md;
1179         specialmethod = (mref->name->text[0] == '<');
1180         opcode = state->iptr[0].opc;
1181         dst = state->iptr->dst;
1182
1183         /* prevent compiler warnings */
1184
1185         ins = NULL;
1186
1187         /* check whether we are calling <init> */
1188
1189         callinginit = (opcode == ICMD_INVOKESPECIAL && mref->name == utf_init);
1190         if (specialmethod && !callinginit)
1191                 TYPECHECK_VERIFYERROR_bool("Invalid invocation of special method");
1192
1193         /* allocate parameters if necessary */
1194
1195         if (!md->params)
1196                 if (!descriptor_params_from_paramtypes(md,
1197                                         (opcode == ICMD_INVOKESTATIC) ? ACC_STATIC : ACC_NONE))
1198                         return false;
1199
1200         /* check parameter types */
1201
1202         stack = state->curstack;
1203         i = md->paramcount; /* number of parameters including 'this'*/
1204         while (--i >= 0) {
1205                 LOG1("param %d",i);
1206                 td = md->paramtypes + i;
1207                 if (stack->type != td->type)
1208                         TYPECHECK_VERIFYERROR_bool("Parameter type mismatch in method invocation");
1209                 if (stack->type == TYPE_ADR) {
1210                         LOGINFO(&(stack->typeinfo));
1211                         if (i==0 && callinginit)
1212                         {
1213                                 /* first argument to <init> method */
1214                                 if (!TYPEINFO_IS_NEWOBJECT(stack->typeinfo))
1215                                         TYPECHECK_VERIFYERROR_bool("Calling <init> on initialized object");
1216
1217                                 /* get the address of the NEW instruction */
1218                                 LOGINFO(&(stack->typeinfo));
1219                                 ins = (instruction*)TYPEINFO_NEWOBJECT_INSTRUCTION(stack->typeinfo);
1220                                 if (ins)
1221                                         initclass = CLASSREF_OR_CLASSINFO(ins[-1].target);
1222                                 else
1223                                         initclass.cls = state->m->class;
1224                                 LOGSTR("class: "); LOGNAME(initclass); LOGNL;
1225                         }
1226                 }
1227                 else {
1228                         /* non-adress argument. if this is the first argument and we are */
1229                         /* invoking an instance method, this is an error.                */
1230                         if (i==0 && opcode != ICMD_INVOKESTATIC) {
1231                                 TYPECHECK_VERIFYERROR_bool("Parameter type mismatch for 'this' argument");
1232                         }
1233                 }
1234                 LOG("ok");
1235
1236                 if (i)
1237                         stack = stack->prev;
1238         }
1239
1240         LOG("checking return type");
1241         rtype = md->returntype.type;
1242         if (rtype != TYPE_VOID) {
1243                 if (rtype != dst->type)
1244                         TYPECHECK_VERIFYERROR_bool("Return type mismatch in method invocation");
1245                 if (!typeinfo_init_from_typedesc(&(md->returntype),NULL,&(dst->typeinfo)))
1246                         return false;
1247         }
1248
1249         if (callinginit) {
1250                 LOG("replacing uninitialized object");
1251                 /* replace uninitialized object type on stack */
1252                 stack = dst;
1253                 while (stack) {
1254                         if (stack->type == TYPE_ADR
1255                                         && TYPEINFO_IS_NEWOBJECT(stack->typeinfo)
1256                                         && TYPEINFO_NEWOBJECT_INSTRUCTION(stack->typeinfo) == ins)
1257                         {
1258                                 LOG("replacing uninitialized type on stack");
1259
1260                                 /* If this stackslot is in the instack of
1261                                  * this basic block we must save the type(s)
1262                                  * we are going to replace.
1263                                  */
1264                                 if (stack <= state->bptr->instack && !state->savedstack)
1265                                         typestate_save_instack(state);
1266
1267                                 if (!typeinfo_init_class(&(stack->typeinfo),initclass))
1268                                         return false;
1269                         }
1270                         stack = stack->prev;
1271                 }
1272                 /* replace uninitialized object type in locals */
1273                 if (!typevectorset_init_object(state->localset,ins,initclass,state->numlocals))
1274                         return false;
1275
1276                 /* initializing the 'this' reference? */
1277                 if (!ins) {
1278                         classinfo *cls;
1279                         TYPECHECK_ASSERT(state->initmethod);
1280                         /* { we are initializing the 'this' reference }                           */
1281                         /* must be <init> of current class or direct superclass                   */
1282                         /* the current class is linked, so must be its superclass. thus we can be */
1283                         /* sure that resolving will be trivial.                                   */
1284                         if (!resolve_classref(state->m,mref->classref,resolveLazy,false,true,&cls))
1285                                 return false; /* exception */
1286
1287                         /* if lazy resolving did not succeed, it's not one of the allowed classes */
1288                         /* otherwise we check it directly                                         */
1289                         if (cls == NULL || (cls != state->m->class && cls != state->m->class->super.cls)) {
1290                                 TYPECHECK_VERIFYERROR_bool("<init> calling <init> of the wrong class");
1291                         }
1292
1293                         /* set our marker variable to type int */
1294                         LOG("setting <init> marker");
1295                         typevectorset_store(state->localset,state->numlocals-1,TYPE_INT,NULL);
1296                 }
1297                 else {
1298                         /* { we are initializing an instance created with NEW } */
1299                         if ((IS_CLASSREF(initclass) ? initclass.ref->name : initclass.cls->name) != mref->classref->name) {
1300                                 TYPECHECK_VERIFYERROR_bool("wrong <init> called for uninitialized reference");
1301                         }
1302                 }
1303         }
1304
1305         /* record subtype constraints for parameters */
1306
1307         if (!constrain_unresolved_method(um,state->m->class,state->m,state->iptr,state->curstack))
1308                 return false; /* XXX maybe wrap exception */
1309
1310         /* try to resolve the method lazily */
1311
1312         if (!resolve_method(um,resolveLazy,(methodinfo **) &(state->iptr[0].val.a)))
1313                 return false;
1314
1315         return true;
1316 }
1317
1318 /* verify_generic_builtin ******************************************************
1319
1320    Verify the call of a generic builtin method.
1321
1322    IN:
1323        state............the current state of the verifier
1324
1325    RETURN VALUE:
1326        true.............successful verification,
1327            false............an exception has been thrown.
1328
1329 *******************************************************************************/
1330
1331 static bool
1332 verify_generic_builtin(verifier_state *state)
1333 {
1334         builtintable_entry *bte;
1335         s4 i;
1336         u1 rtype;
1337         methoddesc *md;
1338     stackptr sp;
1339
1340         TYPECHECK_COUNT(stat_ins_builtin_gen);
1341
1342         bte = (builtintable_entry *) state->iptr[0].val.a;
1343         md = bte->md;
1344         i = md->paramcount;
1345
1346         /* check the types of the arguments on the stack */
1347
1348         sp = state->curstack;
1349         for (i--; i >= 0; i--) {
1350                 if (sp->type != md->paramtypes[i].type) {
1351                         TYPECHECK_VERIFYERROR_bool("parameter type mismatch for builtin method");
1352                 }
1353
1354 #ifdef TYPECHECK_DEBUG
1355                 /* generic builtins may only take primitive types and java.lang.Object references */
1356                 if (sp->type == TYPE_ADR && md->paramtypes[i].classref->name != utf_java_lang_Object) {
1357                         *exceptionptr = new_internalerror("generic builtin method with non-generic reference parameter");
1358                         return false;
1359                 }
1360 #endif
1361
1362                 sp = sp->prev;
1363         }
1364
1365         /* check the return type */
1366
1367         rtype = md->returntype.type;
1368         if (rtype != TYPE_VOID) {
1369                 stackptr dst;
1370
1371                 dst = state->iptr->dst;
1372                 if (rtype != dst->type)
1373                         TYPECHECK_VERIFYERROR_bool("Return type mismatch in generic builtin invocation");
1374                 if (!typeinfo_init_from_typedesc(&(md->returntype),NULL,&(dst->typeinfo)))
1375                         return false;
1376         }
1377
1378         return true;
1379 }
1380
1381 /* verify_builtin **************************************************************
1382
1383    Verify the call of a builtin method.
1384
1385    IN:
1386        state............the current state of the verifier
1387
1388    RETURN VALUE:
1389        true.............successful verification,
1390            false............an exception has been thrown.
1391
1392 *******************************************************************************/
1393
1394 static bool
1395 verify_builtin(verifier_state *state)
1396 {
1397         builtintable_entry *bte;
1398     classref_or_classinfo cls;
1399     stackptr dst;               /* output stack of current instruction */
1400
1401         bte = (builtintable_entry *) state->iptr[0].val.a;
1402         dst = state->iptr->dst;
1403
1404         /* XXX this is an ugly if-chain but twisti did not want a function */
1405         /* pointer in builtintable_entry for this, so here you go.. ;)     */
1406
1407         if (ISBUILTIN(BUILTIN_new)) {
1408                 if (state->iptr[-1].opc != ICMD_ACONST)
1409                         TYPECHECK_VERIFYERROR_bool("illegal instruction: builtin_new without class");
1410                 cls.any = state->iptr[-1].target;
1411                 TYPEINFO_INIT_NEWOBJECT(dst->typeinfo,state->iptr);
1412         }
1413         else if (ISBUILTIN(BUILTIN_newarray_boolean)) {
1414                 TYPECHECK_INT(state->curstack);
1415                 TYPEINFO_INIT_PRIMITIVE_ARRAY(dst->typeinfo,ARRAYTYPE_BOOLEAN);
1416         }
1417         else if (ISBUILTIN(BUILTIN_newarray_char)) {
1418                 TYPECHECK_INT(state->curstack);
1419                 TYPEINFO_INIT_PRIMITIVE_ARRAY(dst->typeinfo,ARRAYTYPE_CHAR);
1420         }
1421         else if (ISBUILTIN(BUILTIN_newarray_float)) {
1422                 TYPECHECK_INT(state->curstack);
1423                 TYPEINFO_INIT_PRIMITIVE_ARRAY(dst->typeinfo,ARRAYTYPE_FLOAT);
1424         }
1425         else if (ISBUILTIN(BUILTIN_newarray_double)) {
1426                 TYPECHECK_INT(state->curstack);
1427                 TYPEINFO_INIT_PRIMITIVE_ARRAY(dst->typeinfo,ARRAYTYPE_DOUBLE);
1428         }
1429         else if (ISBUILTIN(BUILTIN_newarray_byte)) {
1430                 TYPECHECK_INT(state->curstack);
1431                 TYPEINFO_INIT_PRIMITIVE_ARRAY(dst->typeinfo,ARRAYTYPE_BYTE);
1432         }
1433         else if (ISBUILTIN(BUILTIN_newarray_short)) {
1434                 TYPECHECK_INT(state->curstack);
1435                 TYPEINFO_INIT_PRIMITIVE_ARRAY(dst->typeinfo,ARRAYTYPE_SHORT);
1436         }
1437         else if (ISBUILTIN(BUILTIN_newarray_int)) {
1438                 TYPECHECK_INT(state->curstack);
1439                 TYPEINFO_INIT_PRIMITIVE_ARRAY(dst->typeinfo,ARRAYTYPE_INT);
1440         }
1441         else if (ISBUILTIN(BUILTIN_newarray_long)) {
1442                 TYPECHECK_INT(state->curstack);
1443                 TYPEINFO_INIT_PRIMITIVE_ARRAY(dst->typeinfo,ARRAYTYPE_LONG);
1444         }
1445         else if (ISBUILTIN(BUILTIN_newarray))
1446         {
1447                 TYPECHECK_INT(state->curstack->prev);
1448                 if (state->iptr[-1].opc != ICMD_ACONST || !state->iptr[-1].target)
1449                         TYPECHECK_VERIFYERROR_bool("illegal instruction: builtin_newarray without class");
1450                 /* XXX check that it is an array class(ref) */
1451                 typeinfo_init_class(&(dst->typeinfo),CLASSREF_OR_CLASSINFO(state->iptr[-1].target));
1452         }
1453         else if (ISBUILTIN(BUILTIN_arrayinstanceof))
1454         {
1455                 TYPECHECK_ADR(state->curstack->prev);
1456                 if (state->iptr[-1].opc != ICMD_ACONST)
1457                         TYPECHECK_VERIFYERROR_bool("illegal instruction: builtin_arrayinstanceof without class");
1458                 /* XXX check that it is an array class(ref) */
1459         }
1460         else {
1461                 return verify_generic_builtin(state);
1462         }
1463         return true;
1464 }
1465
1466 /* verify_multianewarray *******************************************************
1467
1468    Verify a MULTIANEWARRAY instruction.
1469
1470    IN:
1471        state............the current state of the verifier
1472
1473    RETURN VALUE:
1474        true.............successful verification,
1475            false............an exception has been thrown.
1476
1477 *******************************************************************************/
1478
1479 static bool
1480 verify_multianewarray(verifier_state *state)
1481 {
1482     stackptr sp;
1483         classinfo *arrayclass;
1484         arraydescriptor *desc;
1485         s4 i;
1486
1487         /* check the array lengths on the stack */
1488         i = state->iptr[0].op1;
1489         if (i < 1)
1490                 TYPECHECK_VERIFYERROR_bool("Illegal dimension argument");
1491
1492         sp = state->curstack;
1493         while (i--) {
1494                 if (!sp)
1495                         TYPECHECK_VERIFYERROR_bool("Unable to pop operand off an empty stack");
1496                 TYPECHECK_INT(sp);
1497                 sp = sp->prev;
1498         }
1499
1500         /* check array descriptor */
1501         if (state->iptr[0].val.a != NULL) {
1502                 /* the array class reference has already been resolved */
1503                 arrayclass = (classinfo *) state->iptr[0].val.a;
1504                 if (!arrayclass)
1505                         TYPECHECK_VERIFYERROR_bool("MULTIANEWARRAY with unlinked class");
1506                 if ((desc = arrayclass->vftbl->arraydesc) == NULL)
1507                         TYPECHECK_VERIFYERROR_bool("MULTIANEWARRAY with non-array class");
1508                 if (desc->dimension < state->iptr[0].op1)
1509                         TYPECHECK_VERIFYERROR_bool("MULTIANEWARRAY dimension to high");
1510
1511                 /* set the array type of the result */
1512                 typeinfo_init_classinfo(&(state->iptr->dst->typeinfo), arrayclass);
1513         }
1514         else {
1515                 const char *p;
1516                 constant_classref *cr;
1517
1518                 /* the array class reference is still unresolved */
1519                 /* check that the reference indicates an array class of correct dimension */
1520                 cr = (constant_classref *) state->iptr[0].target;
1521                 i = 0;
1522                 p = cr->name->text;
1523                 while (p[i] == '[')
1524                         i++;
1525                 /* { the dimension of the array class == i } */
1526                 if (i < 1)
1527                         TYPECHECK_VERIFYERROR_bool("MULTIANEWARRAY with non-array class");
1528                 if (i < state->iptr[0].op1)
1529                         TYPECHECK_VERIFYERROR_bool("MULTIANEWARRAY dimension to high");
1530
1531                 /* set the array type of the result */
1532                 if (!typeinfo_init_class(&(state->iptr->dst->typeinfo),CLASSREF_OR_CLASSINFO(state->iptr[0].target)))
1533                         return false;
1534         }
1535
1536         /* everything ok */
1537         return true;
1538 }
1539
1540 /* verify_basic_block **********************************************************
1541
1542    Perform bytecode verification of a basic block.
1543
1544    IN:
1545        state............the current state of the verifier
1546
1547    RETURN VALUE:
1548        true.............successful verification,
1549            false............an exception has been thrown.
1550
1551 *******************************************************************************/
1552
1553 static bool
1554 verify_basic_block(verifier_state *state)
1555 {
1556     int opcode;                                      /* current opcode */
1557     int len;                        /* for counting instructions, etc. */
1558     bool superblockend;        /* true if no fallthrough to next block */
1559     basicblock *tbptr;                   /* temporary for target block */
1560     stackptr dst;               /* output stack of current instruction */
1561     basicblock **tptr;    /* pointer into target list of switch instr. */
1562     classinfo *cls;                                       /* temporary */
1563     bool maythrow;               /* true if this instruction may throw */
1564     classinfo *myclass;
1565         unresolved_field *uf;                        /* for field accesses */
1566         fieldinfo **fieldinfop;                      /* for field accesses */
1567         s4 i;
1568         s4 b_index;
1569         typecheck_result r;
1570
1571         LOGSTR1("\n---- BLOCK %04d ------------------------------------------------\n",state->bptr->debug_nr);
1572         LOGFLUSH;
1573
1574         superblockend = false;
1575         state->bptr->flags = BBFINISHED;
1576         b_index = state->bptr - state->m->basicblocks;
1577
1578         /* init stack at the start of this block */
1579         state->curstack = state->bptr->instack;
1580
1581         /* prevent compiler warnings */
1582
1583         dst = NULL;
1584
1585         /* determine the active exception handlers for this block */
1586         /* XXX could use a faster algorithm with sorted lists or  */
1587         /* something?                                             */
1588         len = 0;
1589         for (i = 0; i < state->cd->exceptiontablelength; ++i) {
1590                 if ((state->cd->exceptiontable[i].start <= state->bptr) && (state->cd->exceptiontable[i].end > state->bptr)) {
1591                         LOG1("active handler L%03d", state->cd->exceptiontable[i].handler->debug_nr);
1592                         state->handlers[len++] = state->cd->exceptiontable + i;
1593                 }
1594         }
1595         state->handlers[len] = NULL;
1596
1597         /* init variable types at the start of this block */
1598         typevectorset_copy_inplace(MGET_TYPEVECTOR(state->localbuf,b_index,state->numlocals),
1599                         state->localset,state->numlocals);
1600
1601         /* XXX FIXME FOR INLINING */
1602         if (!useinlining) {
1603                 if (state->handlers[0])
1604                         for (i=0; i<state->numlocals; ++i)
1605                                 if (state->localset->td[i].type == TYPE_ADR
1606                                                 && TYPEINFO_IS_NEWOBJECT(state->localset->td[i].info)) {
1607                                         /* XXX we do not check this for the uninitialized 'this' instance in */
1608                                         /* <init> methods. Otherwise there are problems with try blocks in   */
1609                                         /* <init>. The spec seems to indicate that we should perform the test*/
1610                                         /* in all cases, but this fails with real code.                      */
1611                                         /* Example: org/eclipse/ui/internal/PerspectiveBarNewContributionItem*/
1612                                         /* of eclipse 3.0.2                                                  */
1613                                         if (TYPEINFO_NEWOBJECT_INSTRUCTION(state->localset->td[i].info) != NULL) {
1614                                                 /*show_icmd_method(state->m, state->cd, state->rd);*/
1615                                                 printf("Uninitialized variable: %d, block: %d\n", i, state->bptr->debug_nr);
1616                                                 TYPECHECK_VERIFYERROR_bool("Uninitialized object in local variable inside try block");
1617                                         }
1618                                 }
1619         }
1620         DOLOG(typestate_print(typecheck_logfile,state->curstack,state->localset,state->numlocals));
1621         LOGNL; LOGFLUSH;
1622
1623         /* loop over the instructions */
1624         len = state->bptr->icount;
1625         state->iptr = state->bptr->iinstr;
1626         while (--len >= 0)  {
1627                 TYPECHECK_COUNT(stat_ins);
1628
1629                 DOLOG(typestate_print(typecheck_logfile,state->curstack,state->localset,state->numlocals));
1630                 LOGNL; LOGFLUSH;
1631
1632                 DOLOG(show_icmd(state->iptr,false)); LOGNL; LOGFLUSH;
1633
1634                 opcode = state->iptr->opc;
1635                 myclass = state->iptr->method->class;
1636                 dst = state->iptr->dst;
1637                 maythrow = false;
1638
1639                 switch (opcode) {
1640
1641                         /****************************************/
1642                         /* STACK MANIPULATIONS                  */
1643
1644                         /* We just need to copy the typeinfo */
1645                         /* for slots containing addresses.   */
1646
1647                         /* CAUTION: We assume that the destination stack
1648                          * slots were continuously allocated in
1649                          * memory!  (The current implementation in
1650                          * stack.c)
1651                          */
1652
1653                         case ICMD_DUP:
1654                                 TYPECHECK_COUNT(stat_ins_stack);
1655                                 COPYTYPE(state->curstack,dst);
1656                                 break;
1657
1658                         case ICMD_DUP_X1:
1659                                 TYPECHECK_COUNT(stat_ins_stack);
1660                                 COPYTYPE(state->curstack,dst);
1661                                 COPYTYPE(state->curstack,dst-2);
1662                                 COPYTYPE(state->curstack->prev,dst-1);
1663                                 break;
1664
1665                         case ICMD_DUP_X2:
1666                                 TYPECHECK_COUNT(stat_ins_stack);
1667                                 COPYTYPE(state->curstack,dst);
1668                                 COPYTYPE(state->curstack,dst-3);
1669                                 COPYTYPE(state->curstack->prev,dst-1);
1670                                 COPYTYPE(state->curstack->prev->prev,dst-2);
1671                                 break;
1672
1673                         case ICMD_DUP2:
1674                                 TYPECHECK_COUNT(stat_ins_stack);
1675                                 COPYTYPE(state->curstack,dst);
1676                                 COPYTYPE(state->curstack->prev,dst-1);
1677                                 break;
1678
1679                         case ICMD_DUP2_X1:
1680                                 TYPECHECK_COUNT(stat_ins_stack);
1681                                 COPYTYPE(state->curstack,dst);
1682                                 COPYTYPE(state->curstack->prev,dst-1);
1683                                 COPYTYPE(state->curstack,dst-3);
1684                                 COPYTYPE(state->curstack->prev,dst-4);
1685                                 COPYTYPE(state->curstack->prev->prev,dst-2);
1686                                 break;
1687
1688                         case ICMD_DUP2_X2:
1689                                 TYPECHECK_COUNT(stat_ins_stack);
1690                                 COPYTYPE(state->curstack,dst);
1691                                 COPYTYPE(state->curstack->prev,dst-1);
1692                                 COPYTYPE(state->curstack,dst-4);
1693                                 COPYTYPE(state->curstack->prev,dst-5);
1694                                 COPYTYPE(state->curstack->prev->prev,dst-2);
1695                                 COPYTYPE(state->curstack->prev->prev->prev,dst-3);
1696                                 break;
1697
1698                         case ICMD_SWAP:
1699                                 TYPECHECK_COUNT(stat_ins_stack);
1700                                 COPYTYPE(state->curstack,dst-1);
1701                                 COPYTYPE(state->curstack->prev,dst);
1702                                 break;
1703
1704                                 /****************************************/
1705                                 /* PRIMITIVE VARIABLE ACCESS            */
1706
1707                         case ICMD_ILOAD: if (!typevectorset_checktype(state->localset,state->iptr->op1,TYPE_INT))
1708                                                                  TYPECHECK_VERIFYERROR_bool("Local variable type mismatch");
1709                                                          break;
1710                         case ICMD_IINC:  if (!typevectorset_checktype(state->localset,state->iptr->op1,TYPE_INT))
1711                                                                  TYPECHECK_VERIFYERROR_bool("Local variable type mismatch");
1712                                                          break;
1713                         case ICMD_FLOAD: if (!typevectorset_checktype(state->localset,state->iptr->op1,TYPE_FLOAT))
1714                                                                  TYPECHECK_VERIFYERROR_bool("Local variable type mismatch");
1715                                                          break;
1716                         case ICMD_LLOAD: if (!typevectorset_checktype(state->localset,state->iptr->op1,TYPE_LONG))
1717                                                                  TYPECHECK_VERIFYERROR_bool("Local variable type mismatch");
1718                                                          break;
1719                         case ICMD_DLOAD: if (!typevectorset_checktype(state->localset,state->iptr->op1,TYPE_DOUBLE))
1720                                                                  TYPECHECK_VERIFYERROR_bool("Local variable type mismatch");
1721                                                          break;
1722
1723                         case ICMD_ISTORE: typevectorset_store(state->localset,state->iptr->op1,TYPE_INT,NULL); break;
1724                         case ICMD_FSTORE: typevectorset_store(state->localset,state->iptr->op1,TYPE_FLOAT,NULL); break;
1725                         case ICMD_LSTORE: typevectorset_store_twoword(state->localset,state->iptr->op1,TYPE_LONG); break;
1726                         case ICMD_DSTORE: typevectorset_store_twoword(state->localset,state->iptr->op1,TYPE_DOUBLE); break;
1727
1728                                 /****************************************/
1729                                 /* LOADING ADDRESS FROM VARIABLE        */
1730
1731                         case ICMD_ALOAD:
1732                                 TYPECHECK_COUNT(stat_ins_aload);
1733
1734                                 /* loading a returnAddress is not allowed */
1735                                 if (state->jsrencountered) {
1736                                         if (!typevectorset_checkreference(state->localset,state->iptr->op1)) {
1737                                                 TYPECHECK_VERIFYERROR_bool("illegal instruction: ALOAD loading non-reference");
1738                                         }
1739                                         if (typevectorset_copymergedtype(state->m,state->localset,state->iptr->op1,&(dst->typeinfo)) == -1)
1740                                                 return false;
1741                                 }
1742                                 else {
1743                                         if (!TYPEDESC_IS_REFERENCE(state->localset->td[state->iptr->op1])) {
1744                                                 TYPECHECK_VERIFYERROR_bool("illegal instruction: ALOAD loading non-reference");
1745                                         }
1746                                         TYPEINFO_COPY(state->localset->td[state->iptr->op1].info,dst->typeinfo);
1747                                 }
1748                                 break;
1749
1750                                 /****************************************/
1751                                 /* STORING ADDRESS TO VARIABLE          */
1752
1753                         case ICMD_ASTORE:
1754                                 if (state->handlers[0] && TYPEINFO_IS_NEWOBJECT(state->curstack->typeinfo)) {
1755                                         TYPECHECK_VERIFYERROR_bool("Storing uninitialized object in local variable inside try block");
1756                                 }
1757
1758                                 if (TYPESTACK_IS_RETURNADDRESS(state->curstack)) {
1759                                         typevectorset_store_retaddr(state->localset,state->iptr->op1,&(state->curstack->typeinfo));
1760                                 }
1761                                 else {
1762                                         typevectorset_store(state->localset,state->iptr->op1,TYPE_ADDRESS,
1763                                                         &(state->curstack->typeinfo));
1764                                 }
1765                                 break;
1766
1767                                 /****************************************/
1768                                 /* LOADING ADDRESS FROM ARRAY           */
1769
1770                         case ICMD_AALOAD:
1771                                 if (!TYPEINFO_MAYBE_ARRAY_OF_REFS(state->curstack->prev->typeinfo))
1772                                         TYPECHECK_VERIFYERROR_bool("illegal instruction: AALOAD on non-reference array");
1773
1774                                 if (!typeinfo_init_component(&state->curstack->prev->typeinfo,&dst->typeinfo))
1775                                         return false;
1776                                 maythrow = true;
1777                                 break;
1778
1779                                 /****************************************/
1780                                 /* FIELD ACCESS                         */
1781
1782                         case ICMD_PUTFIELDCONST:
1783                         case ICMD_PUTSTATICCONST:
1784                                 TYPECHECK_COUNT(stat_ins_field);
1785
1786                                 uf = INSTRUCTION_PUTCONST_FIELDREF(state->iptr);
1787                                 fieldinfop = INSTRUCTION_PUTCONST_FIELDINFO_PTR(state->iptr);
1788
1789                                 goto fieldaccess_tail;
1790
1791                         case ICMD_PUTFIELD:
1792                         case ICMD_PUTSTATIC:
1793                                 TYPECHECK_COUNT(stat_ins_field);
1794
1795                                 uf = (unresolved_field *) state->iptr[0].target;
1796                                 fieldinfop = (fieldinfo **) &(state->iptr[0].val.a);
1797
1798                                 goto fieldaccess_tail;
1799
1800                         case ICMD_GETFIELD:
1801                         case ICMD_GETSTATIC:
1802                                 TYPECHECK_COUNT(stat_ins_field);
1803
1804                                 uf = (unresolved_field *) state->iptr[0].target;
1805                                 fieldinfop = (fieldinfo **) &(state->iptr[0].val.a);
1806
1807                                 /* the result is pushed on the stack */
1808                                 if (dst->type == TYPE_ADR) {
1809                                         if (!typeinfo_init_from_typedesc(uf->fieldref->parseddesc.fd,NULL,&(dst->typeinfo)))
1810                                                 return false;
1811                                 }
1812
1813 fieldaccess_tail:
1814                                 /* record the subtype constraints for this field access */
1815                                 if (!constrain_unresolved_field(uf,state->m->class,state->m,state->iptr,state->curstack))
1816                                         return false; /* XXX maybe wrap exception? */
1817
1818                                 /* try to resolve the field reference */
1819                                 if (!resolve_field(uf,resolveLazy,fieldinfop))
1820                                         return false;
1821
1822                                 TYPECHECK_COUNTIF(!*fieldinfop,stat_ins_field_unresolved);
1823                                 TYPECHECK_COUNTIF(*fieldinfop && !(*fieldinfop)->class->initialized,stat_ins_field_uninitialized);
1824
1825                                 maythrow = true;
1826                                 break;
1827
1828                                 /****************************************/
1829                                 /* PRIMITIVE ARRAY ACCESS               */
1830
1831                         case ICMD_ARRAYLENGTH:
1832                                 if (!TYPEINFO_MAYBE_ARRAY(state->curstack->typeinfo)
1833                                                 && state->curstack->typeinfo.typeclass.cls != pseudo_class_Arraystub)
1834                                         TYPECHECK_VERIFYERROR_bool("illegal instruction: ARRAYLENGTH on non-array");
1835                                 maythrow = true;
1836                                 break;
1837
1838                         case ICMD_BALOAD:
1839                                 if (!TYPEINFO_MAYBE_PRIMITIVE_ARRAY(state->curstack->prev->typeinfo,ARRAYTYPE_BOOLEAN)
1840                                                 && !TYPEINFO_MAYBE_PRIMITIVE_ARRAY(state->curstack->prev->typeinfo,ARRAYTYPE_BYTE))
1841                                         TYPECHECK_VERIFYERROR_bool("Array type mismatch");
1842                                 maythrow = true;
1843                                 break;
1844                         case ICMD_CALOAD:
1845                                 if (!TYPEINFO_MAYBE_PRIMITIVE_ARRAY(state->curstack->prev->typeinfo,ARRAYTYPE_CHAR))
1846                                         TYPECHECK_VERIFYERROR_bool("Array type mismatch");
1847                                 maythrow = true;
1848                                 break;
1849                         case ICMD_DALOAD:
1850                                 if (!TYPEINFO_MAYBE_PRIMITIVE_ARRAY(state->curstack->prev->typeinfo,ARRAYTYPE_DOUBLE))
1851                                         TYPECHECK_VERIFYERROR_bool("Array type mismatch");
1852                                 maythrow = true;
1853                                 break;
1854                         case ICMD_FALOAD:
1855                                 if (!TYPEINFO_MAYBE_PRIMITIVE_ARRAY(state->curstack->prev->typeinfo,ARRAYTYPE_FLOAT))
1856                                         TYPECHECK_VERIFYERROR_bool("Array type mismatch");
1857                                 maythrow = true;
1858                                 break;
1859                         case ICMD_IALOAD:
1860                                 if (!TYPEINFO_MAYBE_PRIMITIVE_ARRAY(state->curstack->prev->typeinfo,ARRAYTYPE_INT))
1861                                         TYPECHECK_VERIFYERROR_bool("Array type mismatch");
1862                                 maythrow = true;
1863                                 break;
1864                         case ICMD_SALOAD:
1865                                 if (!TYPEINFO_MAYBE_PRIMITIVE_ARRAY(state->curstack->prev->typeinfo,ARRAYTYPE_SHORT))
1866                                         TYPECHECK_VERIFYERROR_bool("Array type mismatch");
1867                                 maythrow = true;
1868                                 break;
1869                         case ICMD_LALOAD:
1870                                 if (!TYPEINFO_MAYBE_PRIMITIVE_ARRAY(state->curstack->prev->typeinfo,ARRAYTYPE_LONG))
1871                                         TYPECHECK_VERIFYERROR_bool("Array type mismatch");
1872                                 maythrow = true;
1873                                 break;
1874
1875                         case ICMD_BASTORE:
1876                                 if (!TYPEINFO_MAYBE_PRIMITIVE_ARRAY(state->curstack->prev->prev->typeinfo,ARRAYTYPE_BOOLEAN)
1877                                                 && !TYPEINFO_MAYBE_PRIMITIVE_ARRAY(state->curstack->prev->prev->typeinfo,ARRAYTYPE_BYTE))
1878                                         TYPECHECK_VERIFYERROR_bool("Array type mismatch");
1879                                 maythrow = true;
1880                                 break;
1881                         case ICMD_CASTORE:
1882                                 if (!TYPEINFO_MAYBE_PRIMITIVE_ARRAY(state->curstack->prev->prev->typeinfo,ARRAYTYPE_CHAR))
1883                                         TYPECHECK_VERIFYERROR_bool("Array type mismatch");
1884                                 maythrow = true;
1885                                 break;
1886                         case ICMD_DASTORE:
1887                                 if (!TYPEINFO_MAYBE_PRIMITIVE_ARRAY(state->curstack->prev->prev->typeinfo,ARRAYTYPE_DOUBLE))
1888                                         TYPECHECK_VERIFYERROR_bool("Array type mismatch");
1889                                 maythrow = true;
1890                                 break;
1891                         case ICMD_FASTORE:
1892                                 if (!TYPEINFO_MAYBE_PRIMITIVE_ARRAY(state->curstack->prev->prev->typeinfo,ARRAYTYPE_FLOAT))
1893                                         TYPECHECK_VERIFYERROR_bool("Array type mismatch");
1894                                 maythrow = true;
1895                                 break;
1896                         case ICMD_IASTORE:
1897                                 if (!TYPEINFO_MAYBE_PRIMITIVE_ARRAY(state->curstack->prev->prev->typeinfo,ARRAYTYPE_INT))
1898                                         TYPECHECK_VERIFYERROR_bool("Array type mismatch");
1899                                 maythrow = true;
1900                                 break;
1901                         case ICMD_SASTORE:
1902                                 if (!TYPEINFO_MAYBE_PRIMITIVE_ARRAY(state->curstack->prev->prev->typeinfo,ARRAYTYPE_SHORT))
1903                                         TYPECHECK_VERIFYERROR_bool("Array type mismatch");
1904                                 maythrow = true;
1905                                 break;
1906                         case ICMD_LASTORE:
1907                                 if (!TYPEINFO_MAYBE_PRIMITIVE_ARRAY(state->curstack->prev->prev->typeinfo,ARRAYTYPE_LONG))
1908                                         TYPECHECK_VERIFYERROR_bool("Array type mismatch");
1909                                 maythrow = true;
1910                                 break;
1911
1912                         case ICMD_AASTORE:
1913                                 /* we just check the basic input types and that the           */
1914                                 /* destination is an array of references. Assignability to    */
1915                                 /* the actual array must be checked at runtime, each time the */
1916                                 /* instruction is performed. (See builtin_canstore.)          */
1917                                 TYPECHECK_ADR(state->curstack);
1918                                 TYPECHECK_INT(state->curstack->prev);
1919                                 TYPECHECK_ADR(state->curstack->prev->prev);
1920                                 if (!TYPEINFO_MAYBE_ARRAY_OF_REFS(state->curstack->prev->prev->typeinfo))
1921                                         TYPECHECK_VERIFYERROR_bool("illegal instruction: AASTORE to non-reference array");
1922                                 maythrow = true;
1923                                 break;
1924
1925                         case ICMD_IASTORECONST:
1926                                 if (!TYPEINFO_MAYBE_PRIMITIVE_ARRAY(state->curstack->prev->typeinfo, ARRAYTYPE_INT))
1927                                         TYPECHECK_VERIFYERROR_bool("Array type mismatch");
1928                                 maythrow = true;
1929                                 break;
1930
1931                         case ICMD_LASTORECONST:
1932                                 if (!TYPEINFO_MAYBE_PRIMITIVE_ARRAY(state->curstack->prev->typeinfo, ARRAYTYPE_LONG))
1933                                         TYPECHECK_VERIFYERROR_bool("Array type mismatch");
1934                                 maythrow = true;
1935                                 break;
1936
1937                         case ICMD_BASTORECONST:
1938                                 if (!TYPEINFO_MAYBE_PRIMITIVE_ARRAY(state->curstack->prev->typeinfo, ARRAYTYPE_BOOLEAN)
1939                                                 && !TYPEINFO_MAYBE_PRIMITIVE_ARRAY(state->curstack->prev->typeinfo, ARRAYTYPE_BYTE))
1940                                         TYPECHECK_VERIFYERROR_bool("Array type mismatch");
1941                                 maythrow = true;
1942                                 break;
1943
1944                         case ICMD_CASTORECONST:
1945                                 if (!TYPEINFO_MAYBE_PRIMITIVE_ARRAY(state->curstack->prev->typeinfo, ARRAYTYPE_CHAR))
1946                                         TYPECHECK_VERIFYERROR_bool("Array type mismatch");
1947                                 maythrow = true;
1948                                 break;
1949
1950                         case ICMD_SASTORECONST:
1951                                 if (!TYPEINFO_MAYBE_PRIMITIVE_ARRAY(state->curstack->prev->typeinfo, ARRAYTYPE_SHORT))
1952                                         TYPECHECK_VERIFYERROR_bool("Array type mismatch");
1953                                 maythrow = true;
1954                                 break;
1955
1956                                 /****************************************/
1957                                 /* ADDRESS CONSTANTS                    */
1958
1959                         case ICMD_ACONST:
1960                                 if (state->iptr->target) {
1961                                         /* a java.lang.Class reference */
1962                                         TYPEINFO_INIT_JAVA_LANG_CLASS(dst->typeinfo,(constant_classref *)state->iptr->target);
1963                                 }
1964                                 else {
1965                                         if (state->iptr->val.a == NULL)
1966                                                 TYPEINFO_INIT_NULLTYPE(dst->typeinfo);
1967                                         else {
1968                                                 /* string constant (or constant for builtin function) */
1969                                                 typeinfo_init_classinfo(&(dst->typeinfo),class_java_lang_String);
1970                                         }
1971                                 }
1972                                 break;
1973
1974                                 /****************************************/
1975                                 /* CHECKCAST AND INSTANCEOF             */
1976
1977                         case ICMD_CHECKCAST:
1978                                 TYPECHECK_ADR(state->curstack);
1979                                 /* returnAddress is not allowed */
1980                                 if (!TYPEINFO_IS_REFERENCE(state->curstack->typeinfo))
1981                                         TYPECHECK_VERIFYERROR_bool("Illegal instruction: CHECKCAST on non-reference");
1982
1983                                 cls = (classinfo *) state->iptr[0].val.a;
1984                                 if (cls)
1985                                         typeinfo_init_classinfo(&(dst->typeinfo),cls);
1986                                 else
1987                                         if (!typeinfo_init_class(&(dst->typeinfo),CLASSREF_OR_CLASSINFO(state->iptr[0].target)))
1988                                                 return false;
1989                                 maythrow = true;
1990                                 break;
1991
1992                         case ICMD_INSTANCEOF:
1993                                 TYPECHECK_ADR(state->curstack);
1994                                 /* returnAddress is not allowed */
1995                                 if (!TYPEINFO_IS_REFERENCE(state->curstack->typeinfo))
1996                                         TYPECHECK_VERIFYERROR_bool("Illegal instruction: INSTANCEOF on non-reference");
1997                                 break;
1998
1999                                 /****************************************/
2000                                 /* BRANCH INSTRUCTIONS                  */
2001
2002                         case ICMD_INLINE_GOTO:
2003                                 COPYTYPE(state->curstack,dst);
2004                                 /* FALLTHROUGH! */
2005                         case ICMD_GOTO:
2006                                 superblockend = true;
2007                                 /* FALLTHROUGH! */
2008                         case ICMD_IFNULL:
2009                         case ICMD_IFNONNULL:
2010                         case ICMD_IFEQ:
2011                         case ICMD_IFNE:
2012                         case ICMD_IFLT:
2013                         case ICMD_IFGE:
2014                         case ICMD_IFGT:
2015                         case ICMD_IFLE:
2016                         case ICMD_IF_ICMPEQ:
2017                         case ICMD_IF_ICMPNE:
2018                         case ICMD_IF_ICMPLT:
2019                         case ICMD_IF_ICMPGE:
2020                         case ICMD_IF_ICMPGT:
2021                         case ICMD_IF_ICMPLE:
2022                         case ICMD_IF_ACMPEQ:
2023                         case ICMD_IF_ACMPNE:
2024                         case ICMD_IF_LEQ:
2025                         case ICMD_IF_LNE:
2026                         case ICMD_IF_LLT:
2027                         case ICMD_IF_LGE:
2028                         case ICMD_IF_LGT:
2029                         case ICMD_IF_LLE:
2030                         case ICMD_IF_LCMPEQ:
2031                         case ICMD_IF_LCMPNE:
2032                         case ICMD_IF_LCMPLT:
2033                         case ICMD_IF_LCMPGE:
2034                         case ICMD_IF_LCMPGT:
2035                         case ICMD_IF_LCMPLE:
2036                                 TYPECHECK_COUNT(stat_ins_branch);
2037                                 tbptr = (basicblock *) state->iptr->target;
2038
2039                                 /* propagate stack and variables to the target block */
2040                                 if (!typestate_reach(state,tbptr,dst,state->localset))
2041                                         return false;
2042                                 break;
2043
2044                                 /****************************************/
2045                                 /* SWITCHES                             */
2046
2047                         case ICMD_TABLESWITCH:
2048                                 TYPECHECK_COUNT(stat_ins_switch);
2049                                 {
2050                                         s4 *s4ptr = state->iptr->val.a;
2051                                         s4ptr++;              /* skip default */
2052                                         i = *s4ptr++;         /* low */
2053                                         i = *s4ptr++ - i + 2; /* +1 for default target */
2054                                 }
2055                                 goto switch_instruction_tail;
2056
2057                         case ICMD_LOOKUPSWITCH:
2058                                 TYPECHECK_COUNT(stat_ins_switch);
2059                                 {
2060                                         s4 *s4ptr = state->iptr->val.a;
2061                                         s4ptr++;              /* skip default */
2062                                         i = *s4ptr++ + 1;     /* count +1 for default */
2063                                 }
2064 switch_instruction_tail:
2065                                 tptr = (basicblock **)state->iptr->target;
2066
2067                                 while (--i >= 0) {
2068                                         tbptr = *tptr++;
2069                                         LOG2("target %d is block %04d",(tptr-(basicblock **)state->iptr->target)-1,tbptr->debug_nr);
2070                                         if (!typestate_reach(state,tbptr,dst,state->localset))
2071                                                 return false;
2072                                 }
2073                                 LOG("switch done");
2074                                 superblockend = true;
2075                                 break;
2076
2077                                 /****************************************/
2078                                 /* ADDRESS RETURNS AND THROW            */
2079
2080                         case ICMD_ATHROW:
2081                                 TYPECHECK_COUNT(stat_ins_athrow);
2082                                 r = typeinfo_is_assignable_to_class(&state->curstack->typeinfo,
2083                                                 CLASSREF_OR_CLASSINFO(class_java_lang_Throwable));
2084                                 if (r == typecheck_FALSE)
2085                                         TYPECHECK_VERIFYERROR_bool("illegal instruction: ATHROW on non-Throwable");
2086                                 if (r == typecheck_FAIL)
2087                                         return false;
2088                                 if (r == typecheck_MAYBE) {
2089                                         /* the check has to be postponed. we need a patcher */
2090                                         TYPECHECK_COUNT(stat_ins_athrow_unresolved);
2091                                         state->iptr->val.a = create_unresolved_class(
2092                                                         state->m,
2093                                                         /* XXX make this more efficient, use class_java_lang_Throwable
2094                                                          * directly */
2095                                                         class_get_classref(state->m->class,utf_java_lang_Throwable),
2096                                                         &state->curstack->typeinfo);
2097                                 }
2098                                 superblockend = true;
2099                                 maythrow = true;
2100                                 break;
2101
2102                         case ICMD_ARETURN:
2103                                 TYPECHECK_COUNT(stat_ins_areturn);
2104                                 if (!TYPEINFO_IS_REFERENCE(state->curstack->typeinfo))
2105                                         TYPECHECK_VERIFYERROR_bool("illegal instruction: ARETURN on non-reference");
2106
2107                                 if (state->returntype.type != TYPE_ADDRESS
2108                                                 || (r = typeinfo_is_assignable(&state->curstack->typeinfo,&(state->returntype.info)))
2109                                                                 == typecheck_FALSE)
2110                                         TYPECHECK_VERIFYERROR_bool("Return type mismatch");
2111                                 if (r == typecheck_FAIL)
2112                                         return false;
2113                                 if (r == typecheck_MAYBE) {
2114                                         /* the check has to be postponed, we need a patcher */
2115                                         TYPECHECK_COUNT(stat_ins_areturn_unresolved);
2116                                         state->iptr->val.a = create_unresolved_class(
2117                                                         state->m,
2118                                                         state->m->parseddesc->returntype.classref,
2119                                                         &state->curstack->typeinfo);
2120                                 }
2121                                 goto return_tail;
2122
2123                                 /****************************************/
2124                                 /* PRIMITIVE RETURNS                    */
2125
2126                         case ICMD_IRETURN:
2127                                 if (state->returntype.type != TYPE_INT) TYPECHECK_VERIFYERROR_bool("Return type mismatch");
2128                                 goto return_tail;
2129
2130                         case ICMD_LRETURN:
2131                                 if (state->returntype.type != TYPE_LONG) TYPECHECK_VERIFYERROR_bool("Return type mismatch");
2132                                 goto return_tail;
2133
2134                         case ICMD_FRETURN:
2135                                 if (state->returntype.type != TYPE_FLOAT) TYPECHECK_VERIFYERROR_bool("Return type mismatch");
2136                                 goto return_tail;
2137
2138                         case ICMD_DRETURN:
2139                                 if (state->returntype.type != TYPE_DOUBLE) TYPECHECK_VERIFYERROR_bool("Return type mismatch");
2140                                 goto return_tail;
2141
2142                         case ICMD_RETURN:
2143                                 if (state->returntype.type != TYPE_VOID) TYPECHECK_VERIFYERROR_bool("Return type mismatch");
2144 return_tail:
2145                                 TYPECHECK_COUNT(stat_ins_primitive_return);
2146
2147                                 if (state->initmethod && state->m->class != class_java_lang_Object) {
2148                                         /* Check if the 'this' instance has been initialized. */
2149                                         LOG("Checking <init> marker");
2150                                         if (!typevectorset_checktype(state->localset,state->numlocals-1,TYPE_INT))
2151                                                 TYPECHECK_VERIFYERROR_bool("<init> method does not initialize 'this'");
2152                                 }
2153
2154                                 superblockend = true;
2155                                 maythrow = true;
2156                                 break;
2157
2158                                 /****************************************/
2159                                 /* SUBROUTINE INSTRUCTIONS              */
2160
2161                         case ICMD_JSR:
2162                                 LOG("jsr");
2163                                 state->jsrencountered = true;
2164
2165                                 /* This is a dirty hack. It is needed
2166                                  * because of the special handling of
2167                                  * ICMD_JSR in stack.c
2168                                  */
2169                                 dst = (stackptr) state->iptr->val.a;
2170
2171                                 tbptr = (basicblock *) state->iptr->target;
2172                                 if (state->bptr + 1 == (state->m->basicblocks + state->m->basicblockcount + 1))
2173                                         TYPECHECK_VERIFYERROR_bool("Illegal instruction: JSR at end of bytecode");
2174                                 typestack_put_retaddr(dst,state->bptr+1,state->localset);
2175                                 if (!typestate_reach(state,tbptr,dst,state->localset))
2176                                         return false;
2177
2178                                 superblockend = true;
2179                                 break;
2180
2181                         case ICMD_RET:
2182                                 /* check returnAddress variable */
2183                                 if (!typevectorset_checkretaddr(state->localset,state->iptr->op1))
2184                                         TYPECHECK_VERIFYERROR_bool("illegal instruction: RET using non-returnAddress variable");
2185
2186                                 if (!typestate_ret(state,state->iptr->op1))
2187                                         return false;
2188
2189                                 superblockend = true;
2190                                 break;
2191
2192                                 /****************************************/
2193                                 /* INVOKATIONS                          */
2194
2195                         case ICMD_INVOKEVIRTUAL:
2196                         case ICMD_INVOKESPECIAL:
2197                         case ICMD_INVOKESTATIC:
2198                         case ICMD_INVOKEINTERFACE:
2199                                 TYPECHECK_COUNT(stat_ins_invoke);
2200                                 if (!verify_invocation(state))
2201                                         return false;
2202                                 TYPECHECK_COUNTIF(!state->iptr[0].val.a,stat_ins_invoke_unresolved);
2203                                 maythrow = true;
2204                                 break;
2205
2206                                 /****************************************/
2207                                 /* MULTIANEWARRAY                       */
2208
2209                         case ICMD_MULTIANEWARRAY:
2210                                 if (!verify_multianewarray(state))
2211                                         return false;
2212                                 maythrow = true;
2213                                 break;
2214
2215                                 /****************************************/
2216                                 /* BUILTINS                             */
2217
2218                         case ICMD_BUILTIN:
2219                                 TYPECHECK_COUNT(stat_ins_builtin);
2220                                 if (!verify_builtin(state))
2221                                         return false;
2222                                 maythrow = true;
2223                                 break;
2224
2225                                 /****************************************/
2226                                 /* SIMPLE EXCEPTION THROWING TESTS      */
2227
2228                         case ICMD_CHECKNULL:
2229                                 /* CHECKNULL just requires that the stack top
2230                                  * is an address. This is checked in stack.c */
2231                                 maythrow = true;
2232                                 break;
2233
2234                                 /****************************************/
2235                                 /* INSTRUCTIONS WHICH SHOULD HAVE BEEN  */
2236                                 /* REPLACED BY OTHER OPCODES            */
2237
2238 #ifdef TYPECHECK_DEBUG
2239                         case ICMD_NEW:
2240                         case ICMD_NEWARRAY:
2241                         case ICMD_ANEWARRAY:
2242                         case ICMD_MONITORENTER:
2243                         case ICMD_MONITOREXIT:
2244                                 LOG2("ICMD %d at %d\n", state->iptr->opc, (int)(state->iptr-state->bptr->iinstr));
2245                                 LOG("Should have been converted to builtin function call.");
2246                                 TYPECHECK_ASSERT(false);
2247                                 break;
2248
2249                         case ICMD_READONLY_ARG:
2250                         case ICMD_CLEAR_ARGREN:
2251                                 LOG2("ICMD %d at %d\n", state->iptr->opc, (int)(state->iptr-state->bptr->iinstr));
2252                                 LOG("Should have been replaced in stack.c.");
2253                                 TYPECHECK_ASSERT(false);
2254                                 break;
2255 #endif
2256
2257                                 /****************************************/
2258                                 /* UNCHECKED OPERATIONS                 */
2259
2260                                 /*********************************************
2261                                  * Instructions below...
2262                                  *     *) don't operate on local variables,
2263                                  *     *) don't operate on references,
2264                                  *     *) don't operate on returnAddresses,
2265                                  *     *) don't affect control flow (except
2266                                  *        by throwing exceptions).
2267                                  *
2268                                  * (These instructions are typechecked in
2269                                  *  analyse_stack.)
2270                                  ********************************************/
2271
2272                                 /* Instructions which may throw a runtime exception: */
2273
2274                         case ICMD_IDIV:
2275                         case ICMD_IREM:
2276                         case ICMD_LDIV:
2277                         case ICMD_LREM:
2278
2279                                 maythrow = true;
2280                                 break;
2281
2282                                 /* Instructions which never throw a runtime exception: */
2283 #if defined(TYPECHECK_DEBUG) || defined(TYPECHECK_STATISTICS)
2284                         case ICMD_NOP:
2285                         case ICMD_POP:
2286                         case ICMD_POP2:
2287
2288                         case ICMD_ICONST:
2289                         case ICMD_LCONST:
2290                         case ICMD_FCONST:
2291                         case ICMD_DCONST:
2292
2293                         case ICMD_IFEQ_ICONST:
2294                         case ICMD_IFNE_ICONST:
2295                         case ICMD_IFLT_ICONST:
2296                         case ICMD_IFGE_ICONST:
2297                         case ICMD_IFGT_ICONST:
2298                         case ICMD_IFLE_ICONST:
2299                         case ICMD_ELSE_ICONST:
2300
2301                         case ICMD_IADD:
2302                         case ICMD_ISUB:
2303                         case ICMD_IMUL:
2304                         case ICMD_INEG:
2305                         case ICMD_IAND:
2306                         case ICMD_IOR:
2307                         case ICMD_IXOR:
2308                         case ICMD_ISHL:
2309                         case ICMD_ISHR:
2310                         case ICMD_IUSHR:
2311                         case ICMD_LADD:
2312                         case ICMD_LSUB:
2313                         case ICMD_LMUL:
2314                         case ICMD_LNEG:
2315                         case ICMD_LAND:
2316                         case ICMD_LOR:
2317                         case ICMD_LXOR:
2318                         case ICMD_LSHL:
2319                         case ICMD_LSHR:
2320                         case ICMD_LUSHR:
2321                         case ICMD_IMULPOW2:
2322                         case ICMD_LMULPOW2:
2323                         case ICMD_IDIVPOW2:
2324                         case ICMD_LDIVPOW2:
2325                         case ICMD_IADDCONST:
2326                         case ICMD_ISUBCONST:
2327                         case ICMD_IMULCONST:
2328                         case ICMD_IANDCONST:
2329                         case ICMD_IORCONST:
2330                         case ICMD_IXORCONST:
2331                         case ICMD_ISHLCONST:
2332                         case ICMD_ISHRCONST:
2333                         case ICMD_IUSHRCONST:
2334                         case ICMD_IREMPOW2:
2335                         case ICMD_LADDCONST:
2336                         case ICMD_LSUBCONST:
2337                         case ICMD_LMULCONST:
2338                         case ICMD_LANDCONST:
2339                         case ICMD_LORCONST:
2340                         case ICMD_LXORCONST:
2341                         case ICMD_LSHLCONST:
2342                         case ICMD_LSHRCONST:
2343                         case ICMD_LUSHRCONST:
2344                         case ICMD_LREMPOW2:
2345
2346                         case ICMD_I2L:
2347                         case ICMD_I2F:
2348                         case ICMD_I2D:
2349                         case ICMD_L2I:
2350                         case ICMD_L2F:
2351                         case ICMD_L2D:
2352                         case ICMD_F2I:
2353                         case ICMD_F2L:
2354                         case ICMD_F2D:
2355                         case ICMD_D2I:
2356                         case ICMD_D2L:
2357                         case ICMD_D2F:
2358                         case ICMD_INT2BYTE:
2359                         case ICMD_INT2CHAR:
2360                         case ICMD_INT2SHORT:
2361
2362                         case ICMD_LCMP:
2363                         case ICMD_LCMPCONST:
2364                         case ICMD_FCMPL:
2365                         case ICMD_FCMPG:
2366                         case ICMD_DCMPL:
2367                         case ICMD_DCMPG:
2368
2369                         case ICMD_FADD:
2370                         case ICMD_DADD:
2371                         case ICMD_FSUB:
2372                         case ICMD_DSUB:
2373                         case ICMD_FMUL:
2374                         case ICMD_DMUL:
2375                         case ICMD_FDIV:
2376                         case ICMD_DDIV:
2377                         case ICMD_FREM:
2378                         case ICMD_DREM:
2379                         case ICMD_FNEG:
2380                         case ICMD_DNEG:
2381
2382                         case ICMD_INLINE_START:
2383                         case ICMD_INLINE_END:
2384
2385                                 /*XXX What shall we do with the following ?*/
2386                         case ICMD_AASTORECONST:
2387                                 TYPECHECK_COUNT(stat_ins_unchecked);
2388                                 break;
2389
2390                                 /****************************************/
2391
2392                         default:
2393                                 LOG2("ICMD %d at %d\n", state->iptr->opc, (int)(state->iptr-state->bptr->iinstr));
2394                                 TYPECHECK_VERIFYERROR_bool("Missing ICMD code during typecheck");
2395 #endif
2396                 }
2397
2398                 /* the output of this instruction becomes the current stack */
2399                 state->curstack = dst;
2400
2401                 /* reach exception handlers for this instruction */
2402                 if (maythrow) {
2403                         TYPECHECK_COUNT(stat_ins_maythrow);
2404                         TYPECHECK_MARK(state->stat_maythrow);
2405                         LOG("reaching exception handlers");
2406                         i = 0;
2407                         while (state->handlers[i]) {
2408                                 TYPECHECK_COUNT(stat_handlers_reached);
2409                                 if (state->handlers[i]->catchtype.any)
2410                                         state->excstack.typeinfo.typeclass = state->handlers[i]->catchtype;
2411                                 else
2412                                         state->excstack.typeinfo.typeclass.cls = class_java_lang_Throwable;
2413                                 if (!typestate_reach(state,
2414                                                 state->handlers[i]->handler,
2415                                                 &(state->excstack),state->localset))
2416                                         return false;
2417                                 i++;
2418                         }
2419                 }
2420
2421                 LOG("next instruction");
2422                 state->iptr++;
2423         } /* while instructions */
2424
2425         LOG("instructions done");
2426         LOGSTR("RESULT=> ");
2427         DOLOG(typestate_print(typecheck_logfile,state->curstack,state->localset,state->numlocals));
2428         LOGNL; LOGFLUSH;
2429
2430         /* propagate stack and variables to the following block */
2431         if (!superblockend) {
2432                 LOG("reaching following block");
2433                 tbptr = state->bptr + 1;
2434                 while (tbptr->flags == BBDELETED) {
2435                         tbptr++;
2436 #ifdef TYPECHECK_DEBUG
2437                         /* this must be checked in parse.c */
2438                         if ((tbptr->debug_nr) >= state->m->basicblockcount)
2439                                 TYPECHECK_VERIFYERROR_bool("Control flow falls off the last block");
2440 #endif
2441                 }
2442                 if (!typestate_reach(state,tbptr,dst,state->localset))
2443                         return false;
2444         }
2445
2446         /* We may have to restore the types of the instack slots. They
2447          * have been saved if an <init> call inside the block has
2448          * modified the instack types. (see INVOKESPECIAL) */
2449
2450         if (state->savedstack)
2451                 typestate_restore_instack(state);
2452
2453         return true;
2454 }
2455
2456 /* verify_init_locals **********************************************************
2457
2458    Initialize the local variables in the verifier state.
2459
2460    IN:
2461        state............the current state of the verifier
2462
2463    RETURN VALUE:
2464        true.............success,
2465            false............an exception has been thrown.
2466
2467 *******************************************************************************/
2468
2469 static bool
2470 verify_init_locals(verifier_state *state)
2471 {
2472         int i;
2473         typedescriptor *td;
2474         typevector *lset;
2475
2476     /* initialize the variable types of the first block */
2477     /* to the types of the arguments */
2478
2479         lset = MGET_TYPEVECTOR(state->localbuf,0,state->numlocals);
2480         lset->k = 0;
2481         lset->alt = NULL;
2482         td = lset->td;
2483         i = state->validlocals;
2484
2485         /* allocate parameter descriptors if necessary */
2486
2487         if (!state->m->parseddesc->params)
2488                 if (!descriptor_params_from_paramtypes(state->m->parseddesc,state->m->flags))
2489                         return false;
2490
2491     /* if this is an instance method initialize the "this" ref type */
2492
2493     if (!(state->m->flags & ACC_STATIC)) {
2494                 if (!i)
2495                         TYPECHECK_VERIFYERROR_bool("Not enough local variables for method arguments");
2496         td->type = TYPE_ADDRESS;
2497         if (state->initmethod)
2498             TYPEINFO_INIT_NEWOBJECT(td->info,NULL);
2499         else
2500             typeinfo_init_classinfo(&(td->info), state->m->class);
2501         td++;
2502                 i--;
2503     }
2504
2505     LOG("'this' argument set.\n");
2506
2507     /* the rest of the arguments and the return type */
2508
2509     i = typedescriptors_init_from_methoddesc(td, state->m->parseddesc,
2510                                                                                           i,
2511                                                                                           true, /* two word types use two slots */
2512                                                                                           (td - lset->td), /* skip 'this' pointer */
2513                                                                                           &state->returntype);
2514         if (i == -1)
2515                 return false;
2516         td += i;
2517
2518         /* variables not used for arguments are initialized to TYPE_VOID */
2519
2520         i = state->numlocals - (td - lset->td);
2521         while (i--) {
2522                 td->type = TYPE_VOID;
2523                 td++;
2524         }
2525
2526     LOG("Arguments set.\n");
2527         return true;
2528 }
2529
2530 /* typecheck_init_flags ********************************************************
2531
2532    Initialize the basic block flags for the following CFG traversal.
2533
2534    IN:
2535        state............the current state of the verifier
2536
2537 *******************************************************************************/
2538
2539 static void
2540 typecheck_init_flags(verifier_state *state)
2541 {
2542         s4 i;
2543         basicblock *block;
2544
2545     /* set all BBFINISHED blocks to BBTYPECHECK_UNDEF. */
2546
2547     i = state->m->basicblockcount;
2548     block = state->m->basicblocks;
2549
2550     while (--i >= 0) {
2551
2552 #ifdef TYPECHECK_DEBUG
2553                 /* check for invalid flags */
2554         if (block->flags != BBFINISHED && block->flags != BBDELETED && block->flags != BBUNDEF)
2555         {
2556             /*show_icmd_method(state->cd->method,state->cd,state->rd);*/
2557             LOGSTR1("block flags: %d\n",block->flags); LOGFLUSH;
2558                         TYPECHECK_ASSERT(false);
2559         }
2560 #endif
2561
2562         if (block->flags >= BBFINISHED) {
2563             block->flags = BBTYPECHECK_UNDEF;
2564         }
2565         block++;
2566     }
2567
2568     /* the first block is always reached */
2569
2570     if (state->m->basicblockcount && state->m->basicblocks[0].flags == BBTYPECHECK_UNDEF)
2571         state->m->basicblocks[0].flags = BBTYPECHECK_REACHED;
2572 }
2573
2574 /* typecheck_reset_flags *******************************************************
2575
2576    Reset the flags of basic blocks we have not reached.
2577
2578    IN:
2579        state............the current state of the verifier
2580
2581 *******************************************************************************/
2582
2583 static void
2584 typecheck_reset_flags(verifier_state *state)
2585 {
2586         s4 i;
2587
2588         /* check for invalid flags at exit */
2589
2590 #ifdef TYPECHECK_DEBUG
2591         for (i=0; i<state->m->basicblockcount; ++i) {
2592                 if (state->m->basicblocks[i].flags != BBDELETED
2593                         && state->m->basicblocks[i].flags != BBUNDEF
2594                         && state->m->basicblocks[i].flags != BBFINISHED
2595                         && state->m->basicblocks[i].flags != BBTYPECHECK_UNDEF) /* typecheck may never reach
2596                                                                                                          * some exception handlers,
2597                                                                                                          * that's ok. */
2598                 {
2599                         LOG2("block L%03d has invalid flags after typecheck: %d",
2600                                  state->m->basicblocks[i].debug_nr,state->m->basicblocks[i].flags);
2601                         TYPECHECK_ASSERT(false);
2602                 }
2603         }
2604 #endif
2605
2606         /* Reset blocks we never reached */
2607
2608         for (i=0; i<state->m->basicblockcount; ++i) {
2609                 if (state->m->basicblocks[i].flags == BBTYPECHECK_UNDEF)
2610                         state->m->basicblocks[i].flags = BBFINISHED;
2611         }
2612 }
2613
2614 /****************************************************************************/
2615 /* typecheck()                                                              */
2616 /* This is the main function of the bytecode verifier. It is called         */
2617 /* directly after analyse_stack.                                            */
2618 /*                                                                          */
2619 /* IN:                                                                      */
2620 /*    meth.............the method to verify                                 */
2621 /*    cdata............codegendata for the method                           */
2622 /*    rdata............registerdata for the method                          */
2623 /*                                                                          */
2624 /* RETURN VALUE:                                                            */
2625 /*     m................successful verification                             */
2626 /*     NULL.............an exception has been thrown                        */
2627 /*                                                                          */
2628 /* XXX TODO:                                                                */
2629 /*     Bytecode verification has not been tested with inlining and          */
2630 /*     probably does not work correctly with inlining.                      */
2631 /****************************************************************************/
2632
2633 #define MAXPARAMS 255
2634
2635 methodinfo *typecheck(methodinfo *meth, codegendata *cdata, registerdata *rdata)
2636 {
2637         verifier_state state;             /* current state of the verifier */
2638     int i;                                        /* temporary counter */
2639
2640         /* collect statistics */
2641
2642 #ifdef TYPECHECK_STATISTICS
2643         int count_iterations = 0;
2644         TYPECHECK_COUNT(stat_typechecked);
2645         TYPECHECK_COUNT_FREQ(stat_locals,cdata->maxlocals,STAT_LOCALS);
2646         TYPECHECK_COUNT_FREQ(stat_blocks,cdata->method->basicblockcount/10,STAT_BLOCKS);
2647         TYPECHECK_COUNTIF(cdata->method->exceptiontablelength != 0,stat_methods_with_handlers);
2648         state.stat_maythrow = false;
2649 #endif
2650
2651         /* some logging on entry */
2652
2653         DOLOG(typecheck_logfile = stdout);
2654     LOGSTR("\n==============================================================================\n");
2655     /*DOLOG( show_icmd_method(cdata->method,cdata,rdata));*/
2656     LOGSTR("\n==============================================================================\n");
2657     LOGMETHOD("Entering typecheck: ",cdata->method);
2658
2659         /* initialize the verifier state */
2660
2661         state.savedstackbuf = NULL;
2662         state.savedstack = NULL;
2663         state.jsrencountered = false;
2664         state.m = meth;
2665         state.cd = cdata;
2666         state.rd = rdata;
2667
2668         /* check if this method is an instance initializer method */
2669
2670     state.initmethod = (state.m->name == utf_init);
2671
2672         /* initialize the basic block flags for the following CFG traversal */
2673
2674         typecheck_init_flags(&state);
2675
2676     /* number of local variables */
2677
2678     /* In <init> methods we use an extra local variable to indicate whether */
2679     /* the 'this' reference has been initialized.                           */
2680         /*         TYPE_VOID...means 'this' has not been initialized,           */
2681         /*         TYPE_INT....means 'this' has been initialized.               */
2682     state.numlocals = state.cd->maxlocals;
2683         state.validlocals = state.numlocals;
2684     if (state.initmethod) state.numlocals++;
2685
2686     /* allocate the buffers for local variables */
2687
2688         state.localbuf = DMNEW_TYPEVECTOR(state.m->basicblockcount+1, state.numlocals);
2689         state.localset = MGET_TYPEVECTOR(state.localbuf,state.m->basicblockcount,state.numlocals);
2690
2691     LOG("Variable buffer allocated.\n");
2692
2693     /* allocate the buffer of active exception handlers */
2694
2695     state.handlers = DMNEW(exceptiontable*, state.cd->exceptiontablelength + 1);
2696
2697         /* initialized local variables of first block */
2698
2699         if (!verify_init_locals(&state))
2700                 return NULL;
2701
2702     /* initialize the input stack of exception handlers */
2703
2704         state.excstack.prev = NULL;
2705         state.excstack.type = TYPE_ADR;
2706         typeinfo_init_classinfo(&(state.excstack.typeinfo),
2707                                                         class_java_lang_Throwable); /* changed later */
2708
2709     LOG("Exception handler stacks set.\n");
2710
2711     /* loop while there are still blocks to be checked */
2712     do {
2713                 TYPECHECK_COUNT(count_iterations);
2714
2715         state.repeat = false;
2716
2717         i = state.m->basicblockcount;
2718         state.bptr = state.m->basicblocks;
2719
2720         while (--i >= 0) {
2721             LOGSTR1("---- BLOCK %04d, ",state.bptr->debug_nr);
2722             LOGSTR1("blockflags: %d\n",state.bptr->flags);
2723             LOGFLUSH;
2724
2725                     /* verify reached block */
2726             if (state.bptr->flags == BBTYPECHECK_REACHED) {
2727                 if (!verify_basic_block(&state))
2728                                         return NULL;
2729             }
2730             state.bptr++;
2731         } /* while blocks */
2732
2733         LOGIF(state.repeat,"state.repeat == true");
2734     } while (state.repeat);
2735
2736         /* statistics */
2737
2738 #ifdef TYPECHECK_STATISTICS
2739         LOG1("Typechecker did %4d iterations",count_iterations);
2740         TYPECHECK_COUNT_FREQ(stat_iterations,count_iterations,STAT_ITERATIONS);
2741         TYPECHECK_COUNTIF(state.jsrencountered,stat_typechecked_jsr);
2742         TYPECHECK_COUNTIF(state.stat_maythrow,stat_methods_maythrow);
2743 #endif
2744
2745         /* reset the flags of blocks we haven't reached */
2746
2747         typecheck_reset_flags(&state);
2748
2749         /* just return methodinfo* to indicate everything was ok */
2750     LOGimp("exiting typecheck");
2751         return state.m;
2752 }
2753
2754 #endif /* ENABLE_VERIFIER */
2755
2756 /*
2757  * These are local overrides for various environment variables in Emacs.
2758  * Please do not remove this and leave it at the end of the file, where
2759  * Emacs will automagically detect them.
2760  * ---------------------------------------------------------------------
2761  * Local variables:
2762  * mode: c
2763  * indent-tabs-mode: t
2764  * c-basic-offset: 4
2765  * tab-width: 4
2766  * End:
2767  * vim:noexpandtab:sw=4:ts=4:
2768  */