src/vm/jit/verify/typecheck.c

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