src/vm/jit/verify/typecheck.c

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