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