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