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