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