src/vm/jit/verify/typecheck.c

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