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