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