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 3359 2005-10-05 17:52:08Z 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         /* allocate parameters if necessary */
1133
1134         if (!md->params)
1135                 if (!descriptor_params_from_paramtypes(md,
1136                                         (opcode == ICMD_INVOKESTATIC) ? ACC_STATIC : ACC_NONE))
1137                         return false;
1138
1139         /* check parameter types */
1140
1141         stack = state->curstack;
1142         i = md->paramcount; /* number of parameters including 'this'*/
1143         while (--i >= 0) {
1144                 LOG1("param %d",i);
1145                 td = md->paramtypes + i;
1146                 if (stack->type != td->type)
1147                         TYPECHECK_VERIFYERROR_bool("Parameter type mismatch in method invocation");
1148                 if (stack->type == TYPE_ADR) {
1149                         LOGINFO(&(stack->typeinfo));
1150                         if (i==0 && callinginit)
1151                         {
1152                                 /* first argument to <init> method */
1153                                 if (!TYPEINFO_IS_NEWOBJECT(stack->typeinfo))
1154                                         TYPECHECK_VERIFYERROR_bool("Calling <init> on initialized object");
1155
1156                                 /* get the address of the NEW instruction */
1157                                 LOGINFO(&(stack->typeinfo));
1158                                 ins = (instruction*)TYPEINFO_NEWOBJECT_INSTRUCTION(stack->typeinfo);
1159                                 if (ins)
1160                                         initclass = CLASSREF_OR_CLASSINFO(ins[-1].val.a);
1161                                 else
1162                                         initclass.cls = state->m->class;
1163                                 LOGSTR("class: "); LOGNAME(initclass); LOGNL;
1164                         }
1165                 }
1166                 LOG("ok");
1167
1168                 if (i)
1169                         stack = stack->prev;
1170         }
1171
1172         LOG("checking return type");
1173         rtype = md->returntype.type;
1174         if (rtype != TYPE_VOID) {
1175                 if (rtype != dst->type)
1176                         TYPECHECK_VERIFYERROR_bool("Return type mismatch in method invocation");
1177                 if (!typeinfo_init_from_typedesc(&(md->returntype),NULL,&(dst->typeinfo)))
1178                         return false;
1179         }
1180
1181         if (callinginit) {
1182                 LOG("replacing uninitialized object");
1183                 /* replace uninitialized object type on stack */
1184                 stack = dst;
1185                 while (stack) {
1186                         if (stack->type == TYPE_ADR
1187                                         && TYPEINFO_IS_NEWOBJECT(stack->typeinfo)
1188                                         && TYPEINFO_NEWOBJECT_INSTRUCTION(stack->typeinfo) == ins)
1189                         {
1190                                 LOG("replacing uninitialized type on stack");
1191
1192                                 /* If this stackslot is in the instack of
1193                                  * this basic block we must save the type(s)
1194                                  * we are going to replace.
1195                                  */
1196                                 if (stack <= state->bptr->instack && !state->savedstack)
1197                                 {
1198                                         stackptr sp;
1199                                         stackptr copy;
1200                                         LOG("saving input stack types");
1201                                         if (!state->savedstackbuf) {
1202                                                 LOG("allocating savedstack buffer");
1203                                                 state->savedstackbuf = DMNEW(stackelement, state->cd->maxstack);
1204                                                 state->savedstackbuf->prev = NULL;
1205                                                 for (i = 1; i < state->cd->maxstack; ++i)
1206                                                         state->savedstackbuf[i].prev = state->savedstackbuf+(i-1);
1207                                         }
1208                                         sp = state->savedstack = state->bptr->instack;
1209                                         copy = state->bptr->instack = state->savedstackbuf + (state->bptr->indepth-1);
1210                                         TYPESTACK_COPY(sp,copy);
1211                                 }
1212
1213                                 if (!typeinfo_init_class(&(stack->typeinfo),initclass))
1214                                         return false;
1215                         }
1216                         stack = stack->prev;
1217                 }
1218                 /* replace uninitialized object type in locals */
1219                 if (!typevectorset_init_object(state->localset,ins,initclass,state->numlocals))
1220                         return false;
1221
1222                 /* initializing the 'this' reference? */
1223                 if (!ins) {
1224                         classinfo *cls;
1225                         TYPECHECK_ASSERT(state->initmethod);
1226                         /* { we are initializing the 'this' reference }                           */
1227                         /* must be <init> of current class or direct superclass                   */
1228                         /* the current class is linked, so must be its superclass. thus we can be */
1229                         /* sure that resolving will be trivial.                                   */
1230                         if (!resolve_classref(state->m,mref->classref,resolveLazy,false,true,&cls))
1231                                 return false; /* exception */
1232
1233                         /* if lazy resolving did not succeed, it's not one of the allowed classes */
1234                         /* otherwise we check it directly                                         */
1235                         if (cls == NULL || (cls != state->m->class && cls != state->m->class->super.cls)) {
1236                                 TYPECHECK_VERIFYERROR_bool("<init> calling <init> of the wrong class");
1237                         }
1238
1239                         /* set our marker variable to type int */
1240                         LOG("setting <init> marker");
1241                         typevectorset_store(state->localset,state->numlocals-1,TYPE_INT,NULL);
1242                 }
1243                 else {
1244                         /* { we are initializing an instance created with NEW } */
1245                         if ((IS_CLASSREF(initclass) ? initclass.ref->name : initclass.cls->name) != mref->classref->name) {
1246                                 TYPECHECK_VERIFYERROR_bool("wrong <init> called for uninitialized reference");
1247                         }
1248                 }
1249         }
1250
1251         return true;
1252 }
1253
1254 /* verify_builtin **************************************************************
1255
1256    Verify the call of a builtin function.
1257
1258    IN:
1259        state............the current state of the verifier
1260
1261    RETURN VALUE:
1262        true.............successful verification,
1263            false............an exception has been thrown.
1264
1265 *******************************************************************************/
1266
1267 static bool
1268 verify_builtin(verifier_state *state)
1269 {
1270         builtintable_entry *bte;
1271     classref_or_classinfo cls;
1272     stackptr dst;               /* output stack of current instruction */
1273
1274         bte = (builtintable_entry *) state->iptr[0].val.a;
1275         dst = state->iptr->dst;
1276
1277         if (ISBUILTIN(BUILTIN_new) || ISBUILTIN(PATCHER_builtin_new)) {
1278                 if (state->iptr[-1].opc != ICMD_ACONST)
1279                         TYPECHECK_VERIFYERROR_bool("illegal instruction: builtin_new without class");
1280                 cls.any = state->iptr[-1].val.a;
1281                 if (cls.any && !IS_CLASSREF(cls)) {
1282                         /* The following check also forbids array classes and interfaces: */
1283                         if ((cls.cls->flags & ACC_ABSTRACT) != 0)
1284                                 TYPECHECK_VERIFYERROR_bool("Invalid instruction: NEW creating instance of abstract class");
1285                 }
1286                 else {
1287                         /* in this case, the patcher will perform the non-abstract check */
1288                         TYPECHECK_ASSERT(ISBUILTIN(PATCHER_builtin_new));
1289                 }
1290                 TYPEINFO_INIT_NEWOBJECT(dst->typeinfo,state->iptr);
1291         }
1292         else if (ISBUILTIN(BUILTIN_newarray_boolean)) {
1293                 TYPECHECK_INT(state->curstack);
1294                 TYPEINFO_INIT_PRIMITIVE_ARRAY(dst->typeinfo,ARRAYTYPE_BOOLEAN);
1295         }
1296         else if (ISBUILTIN(BUILTIN_newarray_char)) {
1297                 TYPECHECK_INT(state->curstack);
1298                 TYPEINFO_INIT_PRIMITIVE_ARRAY(dst->typeinfo,ARRAYTYPE_CHAR);
1299         }
1300         else if (ISBUILTIN(BUILTIN_newarray_float)) {
1301                 TYPECHECK_INT(state->curstack);
1302                 TYPEINFO_INIT_PRIMITIVE_ARRAY(dst->typeinfo,ARRAYTYPE_FLOAT);
1303         }
1304         else if (ISBUILTIN(BUILTIN_newarray_double)) {
1305                 TYPECHECK_INT(state->curstack);
1306                 TYPEINFO_INIT_PRIMITIVE_ARRAY(dst->typeinfo,ARRAYTYPE_DOUBLE);
1307         }
1308         else if (ISBUILTIN(BUILTIN_newarray_byte)) {
1309                 TYPECHECK_INT(state->curstack);
1310                 TYPEINFO_INIT_PRIMITIVE_ARRAY(dst->typeinfo,ARRAYTYPE_BYTE);
1311         }
1312         else if (ISBUILTIN(BUILTIN_newarray_short)) {
1313                 TYPECHECK_INT(state->curstack);
1314                 TYPEINFO_INIT_PRIMITIVE_ARRAY(dst->typeinfo,ARRAYTYPE_SHORT);
1315         }
1316         else if (ISBUILTIN(BUILTIN_newarray_int)) {
1317                 TYPECHECK_INT(state->curstack);
1318                 TYPEINFO_INIT_PRIMITIVE_ARRAY(dst->typeinfo,ARRAYTYPE_INT);
1319         }
1320         else if (ISBUILTIN(BUILTIN_newarray_long)) {
1321                 TYPECHECK_INT(state->curstack);
1322                 TYPEINFO_INIT_PRIMITIVE_ARRAY(dst->typeinfo,ARRAYTYPE_LONG);
1323         }
1324         else if (ISBUILTIN(BUILTIN_newarray))
1325         {
1326                 vftbl_t *vft;
1327                 TYPECHECK_INT(state->curstack->prev);
1328                 if (state->iptr[-1].opc != ICMD_ACONST)
1329                         TYPECHECK_VERIFYERROR_bool("illegal instruction: builtin_newarray without classinfo");
1330                 vft = (vftbl_t *)state->iptr[-1].val.a;
1331                 if (!vft)
1332                         TYPECHECK_VERIFYERROR_bool("ANEWARRAY with unlinked class");
1333                 if (!vft->arraydesc)
1334                         TYPECHECK_VERIFYERROR_bool("ANEWARRAY with non-array class");
1335                 TYPEINFO_INIT_CLASSINFO(dst->typeinfo,vft->class);
1336         }
1337         else if (ISBUILTIN(PATCHER_builtin_newarray))
1338         {
1339                 TYPECHECK_INT(state->curstack->prev);
1340                 if (state->iptr[-1].opc != ICMD_ACONST)
1341                         TYPECHECK_VERIFYERROR_bool("illegal instruction: builtin_newarray without classinfo");
1342                 if (!typeinfo_init_class(&(dst->typeinfo),CLASSREF_OR_CLASSINFO(state->iptr[-1].val.a)))
1343                         return false;
1344         }
1345         else if (ISBUILTIN(BUILTIN_newarray))
1346         {
1347                 vftbl_t *vft;
1348                 TYPECHECK_INT(state->curstack->prev);
1349                 if (state->iptr[-1].opc != ICMD_ACONST)
1350                         TYPECHECK_VERIFYERROR_bool("illegal instruction: builtin_newarray without classinfo");
1351                 vft = (vftbl_t *)state->iptr[-1].val.a;
1352                 if (!vft)
1353                         TYPECHECK_VERIFYERROR_bool("ANEWARRAY with unlinked class");
1354                 if (!vft->arraydesc)
1355                         TYPECHECK_VERIFYERROR_bool("ANEWARRAY with non-array class");
1356                 TYPEINFO_INIT_CLASSINFO(dst->typeinfo,vft->class);
1357         }
1358         else if (ISBUILTIN(BUILTIN_arrayinstanceof))
1359         {
1360                 vftbl_t *vft;
1361                 TYPECHECK_ADR(state->curstack->prev);
1362                 if (state->iptr[-1].opc != ICMD_ACONST)
1363                         TYPECHECK_VERIFYERROR_bool("illegal instruction: builtin_arrayinstanceof without classinfo");
1364                 vft = (vftbl_t *)state->iptr[-1].val.a;
1365                 if (!vft)
1366                         TYPECHECK_VERIFYERROR_bool("INSTANCEOF with unlinked class");
1367                 if (!vft->arraydesc)
1368                         TYPECHECK_VERIFYERROR_bool("internal error: builtin_arrayinstanceof with non-array class");
1369         }
1370         else {
1371 #if 0
1372                 /* XXX put these checks in a function */
1373                 TYPECHECK_COUNT(stat_ins_builtin_gen);
1374                 builtindesc = builtin_desc;
1375                 while (builtindesc->opcode && builtindesc->builtin
1376                                 != state->iptr->val.fp) builtindesc++;
1377                 if (!builtindesc->opcode) {
1378                         dolog("Builtin not in table: %s",icmd_builtin_name(state->iptr->val.fp));
1379                         TYPECHECK_ASSERT(false);
1380                 }
1381                 TYPECHECK_ARGS3(builtindesc->type_s3,builtindesc->type_s2,builtindesc->type_s1);
1382 #endif
1383         }
1384         return true;
1385 }
1386
1387 /* verify_multianewarray *******************************************************
1388
1389    Verify a MULTIANEWARRAY instruction.
1390
1391    IN:
1392        state............the current state of the verifier
1393
1394    RETURN VALUE:
1395        true.............successful verification,
1396            false............an exception has been thrown.
1397
1398 *******************************************************************************/
1399
1400 static bool
1401 verify_multianewarray(verifier_state *state)
1402 {
1403     stackptr srcstack;         /* source stack for copying and merging */
1404         vftbl_t *arrayvftbl;
1405         arraydescriptor *desc;
1406         s4 i;
1407
1408         /* check the array lengths on the stack */
1409         i = state->iptr[0].op1;
1410         if (i < 1)
1411                 TYPECHECK_VERIFYERROR_bool("Illegal dimension argument");
1412
1413         srcstack = state->curstack;
1414         while (i--) {
1415                 if (!srcstack)
1416                         TYPECHECK_VERIFYERROR_bool("Unable to pop operand off an empty stack");
1417                 TYPECHECK_INT(srcstack);
1418                 srcstack = srcstack->prev;
1419         }
1420
1421         /* check array descriptor */
1422         if (state->iptr[0].target == NULL) {
1423                 arrayvftbl = (vftbl_t*) state->iptr[0].val.a;
1424                 if (!arrayvftbl)
1425                         TYPECHECK_VERIFYERROR_bool("MULTIANEWARRAY with unlinked class");
1426                 if ((desc = arrayvftbl->arraydesc) == NULL)
1427                         TYPECHECK_VERIFYERROR_bool("MULTIANEWARRAY with non-array class");
1428                 if (desc->dimension < state->iptr[0].op1)
1429                         TYPECHECK_VERIFYERROR_bool("MULTIANEWARRAY dimension to high");
1430
1431                 /* set the array type of the result */
1432                 TYPEINFO_INIT_CLASSINFO(state->iptr->dst->typeinfo,arrayvftbl->class);
1433         }
1434         else {
1435                 /* XXX do checks in patcher */
1436                 if (!typeinfo_init_class(&(state->iptr->dst->typeinfo),CLASSREF_OR_CLASSINFO(state->iptr[0].val.a)))
1437                         return false;
1438         }
1439
1440         /* everything ok */
1441         return true;
1442 }
1443
1444 /* verify_basic_block **********************************************************
1445
1446    Perform bytecode verification of a basic block.
1447
1448    IN:
1449        state............the current state of the verifier
1450
1451    RETURN VALUE:
1452        true.............successful verification,
1453            false............an exception has been thrown.
1454
1455 *******************************************************************************/
1456
1457 static bool
1458 verify_basic_block(verifier_state *state)
1459 {
1460     int opcode;                                      /* current opcode */
1461     int len;                        /* for counting instructions, etc. */
1462     bool superblockend;        /* true if no fallthrough to next block */
1463     basicblock *tbptr;                   /* temporary for target block */
1464     stackptr dst;               /* output stack of current instruction */
1465     basicblock **tptr;    /* pointer into target list of switch instr. */
1466     classinfo *cls;                                       /* temporary */
1467     bool maythrow;               /* true if this instruction may throw */
1468     classinfo *myclass;
1469         unresolved_field *uf;                        /* for field accesses */
1470         fieldinfo **fieldinfop;                      /* for field accesses */
1471         s4 i;
1472         s4 b_index;
1473         typecheck_result r;
1474
1475         LOGSTR1("\n---- BLOCK %04d ------------------------------------------------\n",state->bptr->debug_nr);
1476         LOGFLUSH;
1477
1478         superblockend = false;
1479         state->bptr->flags = BBFINISHED;
1480         b_index = state->bptr - state->m->basicblocks;
1481
1482         /* init stack at the start of this block */
1483         state->curstack = state->bptr->instack;
1484
1485         /* prevent compiler warnings */
1486
1487         dst = NULL;
1488
1489         /* determine the active exception handlers for this block */
1490         /* XXX could use a faster algorithm with sorted lists or  */
1491         /* something?                                             */
1492         len = 0;
1493         for (i = 0; i < state->cd->exceptiontablelength; ++i) {
1494                 if ((state->cd->exceptiontable[i].start <= state->bptr) && (state->cd->exceptiontable[i].end > state->bptr)) {
1495                         LOG1("active handler L%03d", state->cd->exceptiontable[i].handler->debug_nr);
1496                         state->handlers[len++] = state->cd->exceptiontable + i;
1497                 }
1498         }
1499         state->handlers[len] = NULL;
1500
1501         /* init variable types at the start of this block */
1502         COPY_TYPEVECTORSET(MGET_TYPEVECTOR(state->localbuf,b_index,state->numlocals),
1503                         state->localset,state->numlocals);
1504
1505         /* XXX FIXME FOR INLINING */
1506         if(!useinlining) {
1507                 if (state->handlers[0])
1508                         for (i=0; i<state->numlocals; ++i)
1509                                 if (state->localset->td[i].type == TYPE_ADR
1510                                                 && TYPEINFO_IS_NEWOBJECT(state->localset->td[i].info)) {
1511                                         /* XXX we do not check this for the uninitialized 'this' instance in */
1512                                         /* <init> methods. Otherwise there are problems with try blocks in   */
1513                                         /* <init>. The spec seems to indicate that we should perform the test*/
1514                                         /* in all cases, but this fails with real code.                      */
1515                                         /* Example: org/eclipse/ui/internal/PerspectiveBarNewContributionItem*/
1516                                         /* of eclipse 3.0.2                                                  */
1517                                         if (TYPEINFO_NEWOBJECT_INSTRUCTION(state->localset->td[i].info) != NULL) {
1518                                                 /*show_icmd_method(state->m, state->cd, state->rd);*/
1519                                                 printf("Uninitialized variale: %d, block: %d\n", i, state->bptr->debug_nr);
1520                                                 TYPECHECK_VERIFYERROR_bool("Uninitialized object in local variable inside try block");
1521                                         }
1522                                 }
1523         }
1524         DOLOG(typestate_print(get_logfile(),state->curstack,state->localset,state->numlocals));
1525         LOGNL; LOGFLUSH;
1526
1527         /* loop over the instructions */
1528         len = state->bptr->icount;
1529         state->iptr = state->bptr->iinstr;
1530         while (--len >= 0)  {
1531                 TYPECHECK_COUNT(stat_ins);
1532
1533                 DOLOG(typestate_print(get_logfile(),state->curstack,state->localset,state->numlocals));
1534                 LOGNL; LOGFLUSH;
1535
1536                 DOLOG(show_icmd(state->iptr,false)); LOGNL; LOGFLUSH;
1537
1538                 opcode = state->iptr->opc;
1539                 myclass = state->iptr->method->class;
1540                 dst = state->iptr->dst;
1541                 maythrow = false;
1542
1543                 switch (opcode) {
1544
1545                         /****************************************/
1546                         /* STACK MANIPULATIONS                  */
1547
1548                         /* We just need to copy the typeinfo */
1549                         /* for slots containing addresses.   */
1550
1551                         /* CAUTION: We assume that the destination stack
1552                          * slots were continuously allocated in
1553                          * memory!  (The current implementation in
1554                          * stack.c)
1555                          */
1556
1557                         case ICMD_DUP:
1558                                 COPYTYPE(state->curstack,dst);
1559                                 break;
1560
1561                         case ICMD_DUP_X1:
1562                                 COPYTYPE(state->curstack,dst);
1563                                 COPYTYPE(state->curstack,dst-2);
1564                                 COPYTYPE(state->curstack->prev,dst-1);
1565                                 break;
1566
1567                         case ICMD_DUP_X2:
1568                                 COPYTYPE(state->curstack,dst);
1569                                 COPYTYPE(state->curstack,dst-3);
1570                                 COPYTYPE(state->curstack->prev,dst-1);
1571                                 COPYTYPE(state->curstack->prev->prev,dst-2);
1572                                 break;
1573
1574                         case ICMD_DUP2:
1575                                 COPYTYPE(state->curstack,dst);
1576                                 COPYTYPE(state->curstack->prev,dst-1);
1577                                 break;
1578
1579                         case ICMD_DUP2_X1:
1580                                 COPYTYPE(state->curstack,dst);
1581                                 COPYTYPE(state->curstack->prev,dst-1);
1582                                 COPYTYPE(state->curstack,dst-3);
1583                                 COPYTYPE(state->curstack->prev,dst-4);
1584                                 COPYTYPE(state->curstack->prev->prev,dst-2);
1585                                 break;
1586
1587                         case ICMD_DUP2_X2:
1588                                 COPYTYPE(state->curstack,dst);
1589                                 COPYTYPE(state->curstack->prev,dst-1);
1590                                 COPYTYPE(state->curstack,dst-4);
1591                                 COPYTYPE(state->curstack->prev,dst-5);
1592                                 COPYTYPE(state->curstack->prev->prev,dst-2);
1593                                 COPYTYPE(state->curstack->prev->prev->prev,dst-3);
1594                                 break;
1595
1596                         case ICMD_SWAP:
1597                                 COPYTYPE(state->curstack,dst-1);
1598                                 COPYTYPE(state->curstack->prev,dst);
1599                                 break;
1600
1601                                 /****************************************/
1602                                 /* PRIMITIVE VARIABLE ACCESS            */
1603
1604                         case ICMD_ILOAD: CHECK_ONEWORD(state->iptr->op1,TYPE_INT); break;
1605                         case ICMD_FLOAD: CHECK_ONEWORD(state->iptr->op1,TYPE_FLOAT); break;
1606                         case ICMD_IINC:  CHECK_ONEWORD(state->iptr->op1,TYPE_INT); break;
1607                         case ICMD_LLOAD: CHECK_TWOWORD(state->iptr->op1,TYPE_LONG); break;
1608                         case ICMD_DLOAD: CHECK_TWOWORD(state->iptr->op1,TYPE_DOUBLE); break;
1609
1610                         case ICMD_FSTORE: STORE_ONEWORD(state->iptr->op1,TYPE_FLOAT); break;
1611                         case ICMD_ISTORE: STORE_ONEWORD(state->iptr->op1,TYPE_INT); break;
1612                         case ICMD_LSTORE: STORE_TWOWORD(state->iptr->op1,TYPE_LONG); break;
1613                         case ICMD_DSTORE: STORE_TWOWORD(state->iptr->op1,TYPE_DOUBLE); break;
1614
1615                                 /****************************************/
1616                                 /* LOADING ADDRESS FROM VARIABLE        */
1617
1618                         case ICMD_ALOAD:
1619                                 TYPECHECK_COUNT(stat_ins_aload);
1620
1621                                 /* loading a returnAddress is not allowed */
1622                                 if (state->jsrencountered) {
1623                                         if (!typevectorset_checkreference(state->localset,state->iptr->op1)) {
1624                                                 TYPECHECK_VERIFYERROR_bool("illegal instruction: ALOAD loading non-reference");
1625                                         }
1626                                         if (typevectorset_copymergedtype(state->m,state->localset,state->iptr->op1,&(dst->typeinfo)) == -1)
1627                                                 return false;
1628                                 }
1629                                 else {
1630                                         if (!TYPEDESC_IS_REFERENCE(state->localset->td[state->iptr->op1])) {
1631                                                 TYPECHECK_VERIFYERROR_bool("illegal instruction: ALOAD loading non-reference");
1632                                         }
1633                                         TYPEINFO_COPY(state->localset->td[state->iptr->op1].info,dst->typeinfo);
1634                                 }
1635                                 break;
1636
1637                                 /****************************************/
1638                                 /* STORING ADDRESS TO VARIABLE          */
1639
1640                         case ICMD_ASTORE:
1641                                 if (state->handlers[0] && TYPEINFO_IS_NEWOBJECT(state->curstack->typeinfo)) {
1642                                         TYPECHECK_VERIFYERROR_bool("Storing uninitialized object in local variable inside try block");
1643                                 }
1644
1645                                 if (TYPESTACK_IS_RETURNADDRESS(state->curstack)) {
1646                                         typevectorset_store_retaddr(state->localset,state->iptr->op1,&(state->curstack->typeinfo));
1647                                 }
1648                                 else {
1649                                         typevectorset_store(state->localset,state->iptr->op1,TYPE_ADDRESS,
1650                                                         &(state->curstack->typeinfo));
1651                                 }
1652                                 break;
1653
1654                                 /****************************************/
1655                                 /* LOADING ADDRESS FROM ARRAY           */
1656
1657                         case ICMD_AALOAD:
1658                                 if (!TYPEINFO_MAYBE_ARRAY_OF_REFS(state->curstack->prev->typeinfo))
1659                                         TYPECHECK_VERIFYERROR_bool("illegal instruction: AALOAD on non-reference array");
1660
1661                                 if (!typeinfo_init_component(&state->curstack->prev->typeinfo,&dst->typeinfo))
1662                                         return false;
1663                                 maythrow = true;
1664                                 break;
1665
1666                                 /****************************************/
1667                                 /* FIELD ACCESS                         */
1668
1669                         case ICMD_PUTFIELDCONST:
1670                         case ICMD_PUTSTATICCONST:
1671                                 TYPECHECK_COUNT(stat_ins_field);
1672
1673                                 uf = INSTRUCTION_PUTCONST_FIELDREF(state->iptr);
1674                                 fieldinfop = INSTRUCTION_PUTCONST_FIELDINFO_PTR(state->iptr);
1675
1676                                 goto fieldaccess_tail;
1677
1678                         case ICMD_PUTFIELD:
1679                         case ICMD_PUTSTATIC:
1680                                 TYPECHECK_COUNT(stat_ins_field);
1681
1682                                 uf = (unresolved_field *) state->iptr[0].target;
1683                                 fieldinfop = (fieldinfo **) &(state->iptr[0].val.a);
1684
1685                                 goto fieldaccess_tail;
1686
1687                         case ICMD_GETFIELD:
1688                         case ICMD_GETSTATIC:
1689                                 TYPECHECK_COUNT(stat_ins_field);
1690
1691                                 uf = (unresolved_field *) state->iptr[0].target;
1692                                 fieldinfop = (fieldinfo **) &(state->iptr[0].val.a);
1693
1694                                 /* the result is pushed on the stack */
1695                                 if (dst->type == TYPE_ADR) {
1696                                         if (!typeinfo_init_from_typedesc(uf->fieldref->parseddesc.fd,NULL,&(dst->typeinfo)))
1697                                                 return false;
1698                                 }
1699
1700 fieldaccess_tail:
1701                                 /* record the subtype constraints for this field access */
1702                                 if (!constrain_unresolved_field(uf,state->m->class,state->m,state->iptr,state->curstack))
1703                                         return false; /* XXX maybe wrap exception? */
1704
1705                                 /* try to resolve the field reference */
1706                                 if (!resolve_field(uf,resolveLazy,fieldinfop))
1707                                         return false;
1708
1709                                 /* we need a patcher, so this is not a leafmethod */
1710 #if defined(__MIPS__) || defined(__POWERPC__)
1711                                 if (!*fieldinfop || !(*fieldinfop)->class->initialized)
1712                                         state->cd->method->isleafmethod = false;
1713 #endif
1714
1715                                 maythrow = true;
1716                                 break;
1717
1718                                 /****************************************/
1719                                 /* PRIMITIVE ARRAY ACCESS               */
1720
1721                         case ICMD_ARRAYLENGTH:
1722                                 if (!TYPEINFO_MAYBE_ARRAY(state->curstack->typeinfo)
1723                                                 && state->curstack->typeinfo.typeclass.cls != pseudo_class_Arraystub)
1724                                         TYPECHECK_VERIFYERROR_bool("illegal instruction: ARRAYLENGTH on non-array");
1725                                 maythrow = true;
1726                                 break;
1727
1728                         case ICMD_BALOAD:
1729                                 if (!TYPEINFO_MAYBE_PRIMITIVE_ARRAY(state->curstack->prev->typeinfo,ARRAYTYPE_BOOLEAN)
1730                                                 && !TYPEINFO_MAYBE_PRIMITIVE_ARRAY(state->curstack->prev->typeinfo,ARRAYTYPE_BYTE))
1731                                         TYPECHECK_VERIFYERROR_bool("Array type mismatch");
1732                                 maythrow = true;
1733                                 break;
1734                         case ICMD_CALOAD:
1735                                 if (!TYPEINFO_MAYBE_PRIMITIVE_ARRAY(state->curstack->prev->typeinfo,ARRAYTYPE_CHAR))
1736                                         TYPECHECK_VERIFYERROR_bool("Array type mismatch");
1737                                 maythrow = true;
1738                                 break;
1739                         case ICMD_DALOAD:
1740                                 if (!TYPEINFO_MAYBE_PRIMITIVE_ARRAY(state->curstack->prev->typeinfo,ARRAYTYPE_DOUBLE))
1741                                         TYPECHECK_VERIFYERROR_bool("Array type mismatch");
1742                                 maythrow = true;
1743                                 break;
1744                         case ICMD_FALOAD:
1745                                 if (!TYPEINFO_MAYBE_PRIMITIVE_ARRAY(state->curstack->prev->typeinfo,ARRAYTYPE_FLOAT))
1746                                         TYPECHECK_VERIFYERROR_bool("Array type mismatch");
1747                                 maythrow = true;
1748                                 break;
1749                         case ICMD_IALOAD:
1750                                 if (!TYPEINFO_MAYBE_PRIMITIVE_ARRAY(state->curstack->prev->typeinfo,ARRAYTYPE_INT))
1751                                         TYPECHECK_VERIFYERROR_bool("Array type mismatch");
1752                                 maythrow = true;
1753                                 break;
1754                         case ICMD_SALOAD:
1755                                 if (!TYPEINFO_MAYBE_PRIMITIVE_ARRAY(state->curstack->prev->typeinfo,ARRAYTYPE_SHORT))
1756                                         TYPECHECK_VERIFYERROR_bool("Array type mismatch");
1757                                 maythrow = true;
1758                                 break;
1759                         case ICMD_LALOAD:
1760                                 if (!TYPEINFO_MAYBE_PRIMITIVE_ARRAY(state->curstack->prev->typeinfo,ARRAYTYPE_LONG))
1761                                         TYPECHECK_VERIFYERROR_bool("Array type mismatch");
1762                                 maythrow = true;
1763                                 break;
1764
1765                         case ICMD_BASTORE:
1766                                 if (!TYPEINFO_MAYBE_PRIMITIVE_ARRAY(state->curstack->prev->prev->typeinfo,ARRAYTYPE_BOOLEAN)
1767                                                 && !TYPEINFO_MAYBE_PRIMITIVE_ARRAY(state->curstack->prev->prev->typeinfo,ARRAYTYPE_BYTE))
1768                                         TYPECHECK_VERIFYERROR_bool("Array type mismatch");
1769                                 maythrow = true;
1770                                 break;
1771                         case ICMD_CASTORE:
1772                                 if (!TYPEINFO_MAYBE_PRIMITIVE_ARRAY(state->curstack->prev->prev->typeinfo,ARRAYTYPE_CHAR))
1773                                         TYPECHECK_VERIFYERROR_bool("Array type mismatch");
1774                                 maythrow = true;
1775                                 break;
1776                         case ICMD_DASTORE:
1777                                 if (!TYPEINFO_MAYBE_PRIMITIVE_ARRAY(state->curstack->prev->prev->typeinfo,ARRAYTYPE_DOUBLE))
1778                                         TYPECHECK_VERIFYERROR_bool("Array type mismatch");
1779                                 maythrow = true;
1780                                 break;
1781                         case ICMD_FASTORE:
1782                                 if (!TYPEINFO_MAYBE_PRIMITIVE_ARRAY(state->curstack->prev->prev->typeinfo,ARRAYTYPE_FLOAT))
1783                                         TYPECHECK_VERIFYERROR_bool("Array type mismatch");
1784                                 maythrow = true;
1785                                 break;
1786                         case ICMD_IASTORE:
1787                                 if (!TYPEINFO_MAYBE_PRIMITIVE_ARRAY(state->curstack->prev->prev->typeinfo,ARRAYTYPE_INT))
1788                                         TYPECHECK_VERIFYERROR_bool("Array type mismatch");
1789                                 maythrow = true;
1790                                 break;
1791                         case ICMD_SASTORE:
1792                                 if (!TYPEINFO_MAYBE_PRIMITIVE_ARRAY(state->curstack->prev->prev->typeinfo,ARRAYTYPE_SHORT))
1793                                         TYPECHECK_VERIFYERROR_bool("Array type mismatch");
1794                                 maythrow = true;
1795                                 break;
1796                         case ICMD_LASTORE:
1797                                 if (!TYPEINFO_MAYBE_PRIMITIVE_ARRAY(state->curstack->prev->prev->typeinfo,ARRAYTYPE_LONG))
1798                                         TYPECHECK_VERIFYERROR_bool("Array type mismatch");
1799                                 maythrow = true;
1800                                 break;
1801
1802                         case ICMD_AASTORE:
1803                                 /* we just check the basic input types and that the           */
1804                                 /* destination is an array of references. Assignability to    */
1805                                 /* the actual array must be checked at runtime, each time the */
1806                                 /* instruction is performed. (See builtin_canstore.)          */
1807                                 TYPECHECK_ADR(state->curstack);
1808                                 TYPECHECK_INT(state->curstack->prev);
1809                                 TYPECHECK_ADR(state->curstack->prev->prev);
1810                                 if (!TYPEINFO_MAYBE_ARRAY_OF_REFS(state->curstack->prev->prev->typeinfo))
1811                                         TYPECHECK_VERIFYERROR_bool("illegal instruction: AASTORE to non-reference array");
1812                                 maythrow = true;
1813                                 break;
1814
1815                         case ICMD_IASTORECONST:
1816                                 if (!TYPEINFO_MAYBE_PRIMITIVE_ARRAY(state->curstack->prev->typeinfo, ARRAYTYPE_INT))
1817                                         TYPECHECK_VERIFYERROR_bool("Array type mismatch");
1818                                 maythrow = true;
1819                                 break;
1820
1821                         case ICMD_LASTORECONST:
1822                                 if (!TYPEINFO_MAYBE_PRIMITIVE_ARRAY(state->curstack->prev->typeinfo, ARRAYTYPE_LONG))
1823                                         TYPECHECK_VERIFYERROR_bool("Array type mismatch");
1824                                 maythrow = true;
1825                                 break;
1826
1827                         case ICMD_BASTORECONST:
1828                                 if (!TYPEINFO_MAYBE_PRIMITIVE_ARRAY(state->curstack->prev->typeinfo, ARRAYTYPE_BOOLEAN)
1829                                                 && !TYPEINFO_MAYBE_PRIMITIVE_ARRAY(state->curstack->prev->typeinfo, ARRAYTYPE_BYTE))
1830                                         TYPECHECK_VERIFYERROR_bool("Array type mismatch");
1831                                 maythrow = true;
1832                                 break;
1833
1834                         case ICMD_CASTORECONST:
1835                                 if (!TYPEINFO_MAYBE_PRIMITIVE_ARRAY(state->curstack->prev->typeinfo, ARRAYTYPE_CHAR))
1836                                         TYPECHECK_VERIFYERROR_bool("Array type mismatch");
1837                                 maythrow = true;
1838                                 break;
1839
1840                         case ICMD_SASTORECONST:
1841                                 if (!TYPEINFO_MAYBE_PRIMITIVE_ARRAY(state->curstack->prev->typeinfo, ARRAYTYPE_SHORT))
1842                                         TYPECHECK_VERIFYERROR_bool("Array type mismatch");
1843                                 maythrow = true;
1844                                 break;
1845
1846                                 /****************************************/
1847                                 /* ADDRESS CONSTANTS                    */
1848
1849                         case ICMD_ACONST:
1850                                 if (state->iptr->val.a == NULL)
1851                                         TYPEINFO_INIT_NULLTYPE(dst->typeinfo);
1852                                 else
1853                                         /* string constant (or constant for builtin function) */
1854                                         TYPEINFO_INIT_CLASSINFO(dst->typeinfo,class_java_lang_String);
1855                                 break;
1856
1857                                 /****************************************/
1858                                 /* CHECKCAST AND INSTANCEOF             */
1859
1860                         case ICMD_CHECKCAST:
1861                                 TYPECHECK_ADR(state->curstack);
1862                                 /* returnAddress is not allowed */
1863                                 if (!TYPEINFO_IS_REFERENCE(state->curstack->typeinfo))
1864                                         TYPECHECK_VERIFYERROR_bool("Illegal instruction: CHECKCAST on non-reference");
1865
1866                                 cls = (classinfo *) state->iptr[0].val.a;
1867                                 if (cls)
1868                                         TYPEINFO_INIT_CLASSINFO(dst->typeinfo,cls);
1869                                 else
1870                                         if (!typeinfo_init_class(&(dst->typeinfo),CLASSREF_OR_CLASSINFO(state->iptr[0].target)))
1871                                                 return false;
1872                                 maythrow = true;
1873                                 break;
1874
1875                         case ICMD_ARRAYCHECKCAST:
1876                                 TYPECHECK_ADR(state->curstack);
1877                                 /* returnAddress is not allowed */
1878                                 if (!TYPEINFO_IS_REFERENCE(state->curstack->typeinfo))
1879                                         TYPECHECK_VERIFYERROR_bool("Illegal instruction: ARRAYCHECKCAST on non-reference");
1880
1881                                 if (state->iptr[0].op1) {
1882                                         /* a resolved array class */
1883                                         cls = ((vftbl_t *)state->iptr[0].target)->class;
1884                                         TYPEINFO_INIT_CLASSINFO(dst->typeinfo,cls);
1885                                 }
1886                                 else {
1887                                         /* an unresolved array class reference */
1888                                         if (!typeinfo_init_class(&(dst->typeinfo),CLASSREF_OR_CLASSINFO(state->iptr[0].target)))
1889                                                 return false;
1890                                 }
1891                                 maythrow = true;
1892                                 break;
1893
1894                         case ICMD_INSTANCEOF:
1895                                 TYPECHECK_ADR(state->curstack);
1896                                 /* returnAddress is not allowed */
1897                                 if (!TYPEINFO_IS_REFERENCE(state->curstack->typeinfo))
1898                                         TYPECHECK_VERIFYERROR_bool("Illegal instruction: INSTANCEOF on non-reference");
1899                                 break;
1900
1901                                 /****************************************/
1902                                 /* BRANCH INSTRUCTIONS                  */
1903
1904                         case ICMD_GOTO:
1905                                 superblockend = true;
1906                                 /* FALLTHROUGH! */
1907                         case ICMD_IFNULL:
1908                         case ICMD_IFNONNULL:
1909                         case ICMD_IFEQ:
1910                         case ICMD_IFNE:
1911                         case ICMD_IFLT:
1912                         case ICMD_IFGE:
1913                         case ICMD_IFGT:
1914                         case ICMD_IFLE:
1915                         case ICMD_IF_ICMPEQ:
1916                         case ICMD_IF_ICMPNE:
1917                         case ICMD_IF_ICMPLT:
1918                         case ICMD_IF_ICMPGE:
1919                         case ICMD_IF_ICMPGT:
1920                         case ICMD_IF_ICMPLE:
1921                         case ICMD_IF_ACMPEQ:
1922                         case ICMD_IF_ACMPNE:
1923                         case ICMD_IF_LEQ:
1924                         case ICMD_IF_LNE:
1925                         case ICMD_IF_LLT:
1926                         case ICMD_IF_LGE:
1927                         case ICMD_IF_LGT:
1928                         case ICMD_IF_LLE:
1929                         case ICMD_IF_LCMPEQ:
1930                         case ICMD_IF_LCMPNE:
1931                         case ICMD_IF_LCMPLT:
1932                         case ICMD_IF_LCMPGE:
1933                         case ICMD_IF_LCMPGT:
1934                         case ICMD_IF_LCMPLE:
1935                                 TYPECHECK_COUNT(stat_ins_branch);
1936                                 tbptr = (basicblock *) state->iptr->target;
1937
1938                                 /* propagate stack and variables to the target block */
1939                                 if (!typestate_reach(state,tbptr,dst,state->localset))
1940                                         return false;
1941                                 break;
1942
1943                                 /****************************************/
1944                                 /* SWITCHES                             */
1945
1946                         case ICMD_TABLESWITCH:
1947                                 TYPECHECK_COUNT(stat_ins_switch);
1948                                 {
1949                                         s4 *s4ptr = state->iptr->val.a;
1950                                         s4ptr++;              /* skip default */
1951                                         i = *s4ptr++;         /* low */
1952                                         i = *s4ptr++ - i + 2; /* +1 for default target */
1953                                 }
1954                                 goto switch_instruction_tail;
1955
1956                         case ICMD_LOOKUPSWITCH:
1957                                 TYPECHECK_COUNT(stat_ins_switch);
1958                                 {
1959                                         s4 *s4ptr = state->iptr->val.a;
1960                                         s4ptr++;              /* skip default */
1961                                         i = *s4ptr++ + 1;     /* count +1 for default */
1962                                 }
1963 switch_instruction_tail:
1964                                 tptr = (basicblock **)state->iptr->target;
1965
1966                                 while (--i >= 0) {
1967                                         tbptr = *tptr++;
1968                                         LOG2("target %d is block %04d",(tptr-(basicblock **)state->iptr->target)-1,tbptr->debug_nr);
1969                                         if (!typestate_reach(state,tbptr,dst,state->localset))
1970                                                 return false;
1971                                 }
1972                                 LOG("switch done");
1973                                 superblockend = true;
1974                                 break;
1975
1976                                 /****************************************/
1977                                 /* ADDRESS RETURNS AND THROW            */
1978
1979                         case ICMD_ATHROW:
1980                                 r = typeinfo_is_assignable_to_class(&state->curstack->typeinfo,
1981                                                 CLASSREF_OR_CLASSINFO(class_java_lang_Throwable));
1982                                 if (r == typecheck_FALSE)
1983                                         TYPECHECK_VERIFYERROR_bool("illegal instruction: ATHROW on non-Throwable");
1984                                 if (r == typecheck_FAIL)
1985                                         return false;
1986                                 /* XXX handle typecheck_MAYBE */
1987                                 superblockend = true;
1988                                 maythrow = true;
1989                                 break;
1990
1991                         case ICMD_ARETURN:
1992                                 if (!TYPEINFO_IS_REFERENCE(state->curstack->typeinfo))
1993                                         TYPECHECK_VERIFYERROR_bool("illegal instruction: ARETURN on non-reference");
1994
1995                                 if (state->returntype.type != TYPE_ADDRESS
1996                                                 || (r = typeinfo_is_assignable(&state->curstack->typeinfo,&(state->returntype.info)))
1997                                                                 == typecheck_FALSE)
1998                                         TYPECHECK_VERIFYERROR_bool("Return type mismatch");
1999                                 if (r == typecheck_FAIL)
2000                                         return false;
2001                                 /* XXX handle typecheck_MAYBE */
2002                                 goto return_tail;
2003
2004                                 /****************************************/
2005                                 /* PRIMITIVE RETURNS                    */
2006
2007                         case ICMD_IRETURN:
2008                                 if (state->returntype.type != TYPE_INT) TYPECHECK_VERIFYERROR_bool("Return type mismatch");
2009                                 goto return_tail;
2010
2011                         case ICMD_LRETURN:
2012                                 if (state->returntype.type != TYPE_LONG) TYPECHECK_VERIFYERROR_bool("Return type mismatch");
2013                                 goto return_tail;
2014
2015                         case ICMD_FRETURN:
2016                                 if (state->returntype.type != TYPE_FLOAT) TYPECHECK_VERIFYERROR_bool("Return type mismatch");
2017                                 goto return_tail;
2018
2019                         case ICMD_DRETURN:
2020                                 if (state->returntype.type != TYPE_DOUBLE) TYPECHECK_VERIFYERROR_bool("Return type mismatch");
2021                                 goto return_tail;
2022
2023                         case ICMD_RETURN:
2024                                 if (state->returntype.type != TYPE_VOID) TYPECHECK_VERIFYERROR_bool("Return type mismatch");
2025 return_tail:
2026                                 TYPECHECK_LEAVE;
2027                                 superblockend = true;
2028                                 maythrow = true;
2029                                 break;
2030
2031                                 /****************************************/
2032                                 /* SUBROUTINE INSTRUCTIONS              */
2033
2034                         case ICMD_JSR:
2035                                 LOG("jsr");
2036                                 state->jsrencountered = true;
2037
2038                                 /* This is a dirty hack. It is needed
2039                                  * because of the special handling of
2040                                  * ICMD_JSR in stack.c
2041                                  */
2042                                 dst = (stackptr) state->iptr->val.a;
2043
2044                                 tbptr = (basicblock *) state->iptr->target;
2045                                 if (state->bptr + 1 == (state->m->basicblocks + state->m->basicblockcount + 1))
2046                                         TYPECHECK_VERIFYERROR_bool("Illegal instruction: JSR at end of bytecode");
2047                                 typestack_put_retaddr(dst,state->bptr+1,state->localset);
2048                                 if (!typestate_reach(state,tbptr,dst,state->localset))
2049                                         return false;
2050
2051                                 superblockend = true;
2052                                 break;
2053
2054                         case ICMD_RET:
2055                                 /* check returnAddress variable */
2056                                 if (!typevectorset_checkretaddr(state->localset,state->iptr->op1))
2057                                         TYPECHECK_VERIFYERROR_bool("illegal instruction: RET using non-returnAddress variable");
2058
2059                                 if (!typestate_ret(state,state->iptr->op1))
2060                                         return false;
2061
2062                                 superblockend = true;
2063                                 break;
2064
2065                                 /****************************************/
2066                                 /* INVOKATIONS                          */
2067
2068                         case ICMD_INVOKEVIRTUAL:
2069                         case ICMD_INVOKESPECIAL:
2070                         case ICMD_INVOKESTATIC:
2071                         case ICMD_INVOKEINTERFACE:
2072                                 TYPECHECK_COUNT(stat_ins_invoke);
2073                                 if (!verify_invocation(state))
2074                                         return false;
2075                                 maythrow = true;
2076                                 break;
2077
2078                                 /****************************************/
2079                                 /* MULTIANEWARRAY                       */
2080
2081                         case ICMD_MULTIANEWARRAY:
2082                                 if (!verify_multianewarray(state))
2083                                         return false;
2084                                 maythrow = true;
2085                                 break;
2086
2087                                 /****************************************/
2088                                 /* BUILTINS                             */
2089
2090                         case ICMD_BUILTIN:
2091                                 TYPECHECK_COUNT(stat_ins_builtin);
2092                                 if (!verify_builtin(state))
2093                                         return false;
2094                                 maythrow = true;
2095                                 break;
2096
2097                                 /****************************************/
2098                                 /* SIMPLE EXCEPTION THROWING TESTS      */
2099
2100                         case ICMD_CHECKNULL:
2101                                 /* CHECKNULL just requires that the stack top
2102                                  * is an address. This is checked in stack.c */
2103                                 maythrow = true;
2104                                 break;
2105
2106                                 /****************************************/
2107                                 /* INSTRUCTIONS WHICH SHOULD HAVE BEEN  */
2108                                 /* REPLACED BY OTHER OPCODES            */
2109
2110 #ifdef TYPECHECK_DEBUG
2111                         case ICMD_NEW:
2112                         case ICMD_NEWARRAY:
2113                         case ICMD_ANEWARRAY:
2114                         case ICMD_MONITORENTER:
2115                         case ICMD_MONITOREXIT:
2116                                 LOG2("ICMD %d at %d\n", state->iptr->opc, (int)(state->iptr-state->bptr->iinstr));
2117                                 LOG("Should have been converted to builtin function call.");
2118                                 TYPECHECK_ASSERT(false);
2119                                 break;
2120
2121                         case ICMD_READONLY_ARG:
2122                         case ICMD_CLEAR_ARGREN:
2123                                 LOG2("ICMD %d at %d\n", state->iptr->opc, (int)(state->iptr-state->bptr->iinstr));
2124                                 LOG("Should have been replaced in stack.c.");
2125                                 TYPECHECK_ASSERT(false);
2126                                 break;
2127 #endif
2128
2129                                 /****************************************/
2130                                 /* UNCHECKED OPERATIONS                 */
2131
2132                                 /*********************************************
2133                                  * Instructions below...
2134                                  *     *) don't operate on local variables,
2135                                  *     *) don't operate on references,
2136                                  *     *) don't operate on returnAddresses.
2137                                  *
2138                                  * (These instructions are typechecked in
2139                                  *  analyse_stack.)
2140                                  ********************************************/
2141
2142                                 /* Instructions which may throw a runtime exception: */
2143
2144                         case ICMD_IDIV:
2145                         case ICMD_IREM:
2146                         case ICMD_LDIV:
2147                         case ICMD_LREM:
2148
2149                                 maythrow = true;
2150                                 break;
2151
2152                                 /* Instructions which never throw a runtime exception: */
2153 #if defined(TYPECHECK_DEBUG) || defined(TYPECHECK_STATISTICS)
2154                         case ICMD_NOP:
2155                         case ICMD_POP:
2156                         case ICMD_POP2:
2157
2158                         case ICMD_ICONST:
2159                         case ICMD_LCONST:
2160                         case ICMD_FCONST:
2161                         case ICMD_DCONST:
2162
2163                         case ICMD_IFEQ_ICONST:
2164                         case ICMD_IFNE_ICONST:
2165                         case ICMD_IFLT_ICONST:
2166                         case ICMD_IFGE_ICONST:
2167                         case ICMD_IFGT_ICONST:
2168                         case ICMD_IFLE_ICONST:
2169                         case ICMD_ELSE_ICONST:
2170
2171                         case ICMD_IADD:
2172                         case ICMD_ISUB:
2173                         case ICMD_IMUL:
2174                         case ICMD_INEG:
2175                         case ICMD_IAND:
2176                         case ICMD_IOR:
2177                         case ICMD_IXOR:
2178                         case ICMD_ISHL:
2179                         case ICMD_ISHR:
2180                         case ICMD_IUSHR:
2181                         case ICMD_LADD:
2182                         case ICMD_LSUB:
2183                         case ICMD_LMUL:
2184                         case ICMD_LNEG:
2185                         case ICMD_LAND:
2186                         case ICMD_LOR:
2187                         case ICMD_LXOR:
2188                         case ICMD_LSHL:
2189                         case ICMD_LSHR:
2190                         case ICMD_LUSHR:
2191 #if 0
2192                         case ICMD_IREM0X10001:
2193                         case ICMD_LREM0X10001:
2194 #endif
2195                         case ICMD_IMULPOW2:
2196                         case ICMD_LMULPOW2:
2197                         case ICMD_IDIVPOW2:
2198                         case ICMD_LDIVPOW2:
2199                         case ICMD_IADDCONST:
2200                         case ICMD_ISUBCONST:
2201                         case ICMD_IMULCONST:
2202                         case ICMD_IANDCONST:
2203                         case ICMD_IORCONST:
2204                         case ICMD_IXORCONST:
2205                         case ICMD_ISHLCONST:
2206                         case ICMD_ISHRCONST:
2207                         case ICMD_IUSHRCONST:
2208                         case ICMD_IREMPOW2:
2209                         case ICMD_LADDCONST:
2210                         case ICMD_LSUBCONST:
2211                         case ICMD_LMULCONST:
2212                         case ICMD_LANDCONST:
2213                         case ICMD_LORCONST:
2214                         case ICMD_LXORCONST:
2215                         case ICMD_LSHLCONST:
2216                         case ICMD_LSHRCONST:
2217                         case ICMD_LUSHRCONST:
2218                         case ICMD_LREMPOW2:
2219
2220                         case ICMD_I2L:
2221                         case ICMD_I2F:
2222                         case ICMD_I2D:
2223                         case ICMD_L2I:
2224                         case ICMD_L2F:
2225                         case ICMD_L2D:
2226                         case ICMD_F2I:
2227                         case ICMD_F2L:
2228                         case ICMD_F2D:
2229                         case ICMD_D2I:
2230                         case ICMD_D2L:
2231                         case ICMD_D2F:
2232                         case ICMD_INT2BYTE:
2233                         case ICMD_INT2CHAR:
2234                         case ICMD_INT2SHORT:
2235
2236                         case ICMD_LCMP:
2237                         case ICMD_LCMPCONST:
2238                         case ICMD_FCMPL:
2239                         case ICMD_FCMPG:
2240                         case ICMD_DCMPL:
2241                         case ICMD_DCMPG:
2242
2243                         case ICMD_FADD:
2244                         case ICMD_DADD:
2245                         case ICMD_FSUB:
2246                         case ICMD_DSUB:
2247                         case ICMD_FMUL:
2248                         case ICMD_DMUL:
2249                         case ICMD_FDIV:
2250                         case ICMD_DDIV:
2251                         case ICMD_FREM:
2252                         case ICMD_DREM:
2253                         case ICMD_FNEG:
2254                         case ICMD_DNEG:
2255
2256
2257                                 /*XXX What shall we do with the following ?*/
2258                         case ICMD_AASTORECONST:
2259                                 TYPECHECK_COUNT(stat_ins_unchecked);
2260                                 break;
2261
2262                                 /****************************************/
2263
2264                         default:
2265                                 LOG2("ICMD %d at %d\n", state->iptr->opc, (int)(state->iptr-state->bptr->iinstr));
2266                                 TYPECHECK_VERIFYERROR_bool("Missing ICMD code during typecheck");
2267 #endif
2268                 }
2269
2270                 /* the output of this instruction becomes the current stack */
2271                 state->curstack = dst;
2272
2273                 /* reach exception handlers for this instruction */
2274                 if (maythrow) {
2275                         LOG("reaching exception handlers");
2276                         i = 0;
2277                         while (state->handlers[i]) {
2278                                 TYPECHECK_COUNT(stat_handlers_reached);
2279                                 if (state->handlers[i]->catchtype.any)
2280                                         state->excstack.typeinfo.typeclass = state->handlers[i]->catchtype;
2281                                 else
2282                                         state->excstack.typeinfo.typeclass.cls = class_java_lang_Throwable;
2283                                 if (!typestate_reach(state,
2284                                                 state->handlers[i]->handler,
2285                                                 &(state->excstack),state->localset))
2286                                         return false;
2287                                 i++;
2288                         }
2289                 }
2290
2291                 LOG("next instruction");
2292                 state->iptr++;
2293         } /* while instructions */
2294
2295         LOG("instructions done");
2296         LOGSTR("RESULT=> ");
2297         DOLOG(typestate_print(get_logfile(),state->curstack,state->localset,state->numlocals));
2298         LOGNL; LOGFLUSH;
2299
2300         /* propagate stack and variables to the following block */
2301         if (!superblockend) {
2302                 LOG("reaching following block");
2303                 tbptr = state->bptr + 1;
2304                 while (tbptr->flags == BBDELETED) {
2305                         tbptr++;
2306 #ifdef TYPECHECK_DEBUG
2307                         /* this must be checked in parse.c */
2308                         if ((tbptr->debug_nr) >= state->m->basicblockcount)
2309                                 TYPECHECK_VERIFYERROR_bool("Control flow falls off the last block");
2310 #endif
2311                 }
2312                 if (!typestate_reach(state,tbptr,dst,state->localset))
2313                         return false;
2314         }
2315
2316         /* We may have to restore the types of the instack slots. They
2317          * have been saved if an <init> call inside the block has
2318          * modified the instack types. (see INVOKESPECIAL) */
2319
2320         if (state->savedstack) {
2321                 stackptr sp = state->bptr->instack;
2322                 stackptr copy = state->savedstack;
2323                 TYPECHECK_COUNT(stat_savedstack);
2324                 LOG("restoring saved instack");
2325                 TYPESTACK_COPY(sp,copy);
2326                 state->bptr->instack = state->savedstack;
2327                 state->savedstack = NULL;
2328         }
2329         return true;
2330 }
2331
2332 /* verify_init_locals **********************************************************
2333
2334    Initialize the local variables in the verifier state.
2335
2336    IN:
2337        state............the current state of the verifier
2338
2339    RETURN VALUE:
2340        true.............success,
2341            false............an exception has been thrown.
2342
2343 *******************************************************************************/
2344
2345 static bool
2346 verify_init_locals(verifier_state *state)
2347 {
2348         int i;
2349         typedescriptor *td;
2350         typevector *lset;
2351
2352     /* initialize the variable types of the first block */
2353     /* to the types of the arguments */
2354
2355         lset = MGET_TYPEVECTOR(state->localbuf,0,state->numlocals);
2356         lset->k = 0;
2357         lset->alt = NULL;
2358         td = lset->td;
2359         i = state->validlocals;
2360
2361         /* allocate parameter descriptors if necessary */
2362
2363         if (!state->m->parseddesc->params)
2364                 if (!descriptor_params_from_paramtypes(state->m->parseddesc,state->m->flags))
2365                         return false;
2366
2367     /* if this is an instance method initialize the "this" ref type */
2368
2369     if (!(state->m->flags & ACC_STATIC)) {
2370                 if (!i)
2371                         TYPECHECK_VERIFYERROR_bool("Not enough local variables for method arguments");
2372         td->type = TYPE_ADDRESS;
2373         if (state->initmethod)
2374             TYPEINFO_INIT_NEWOBJECT(td->info,NULL);
2375         else
2376             TYPEINFO_INIT_CLASSINFO(td->info, state->m->class);
2377         td++;
2378                 i--;
2379     }
2380
2381     LOG("'this' argument set.\n");
2382
2383     /* the rest of the arguments and the return type */
2384
2385     i = typedescriptors_init_from_methoddesc(td, state->m->parseddesc,
2386                                                                                           i,
2387                                                                                           true, /* two word types use two slots */
2388                                                                                           (td - lset->td), /* skip 'this' pointer */
2389                                                                                           &state->returntype);
2390         if (i == -1)
2391                 return false;
2392         td += i;
2393
2394         /* variables not used for arguments are initialized to TYPE_VOID */
2395
2396         i = state->numlocals - (td - lset->td);
2397         while (i--) {
2398                 td->type = TYPE_VOID;
2399                 td++;
2400         }
2401
2402     LOG("Arguments set.\n");
2403         return true;
2404 }
2405
2406 /* typecheck_reset_flags *******************************************************
2407
2408    Reset the flags of basic blocks we have not reached.
2409
2410    IN:
2411        state............the current state of the verifier
2412
2413 *******************************************************************************/
2414
2415 static void
2416 typecheck_reset_flags(verifier_state *state)
2417 {
2418         s4 i;
2419
2420         /* check for invalid flags at exit */
2421
2422 #ifdef TYPECHECK_DEBUG
2423         for (i=0; i<state->m->basicblockcount; ++i) {
2424                 if (state->m->basicblocks[i].flags != BBDELETED
2425                         && state->m->basicblocks[i].flags != BBUNDEF
2426                         && state->m->basicblocks[i].flags != BBFINISHED
2427                         && state->m->basicblocks[i].flags != BBTYPECHECK_UNDEF) /* typecheck may never reach
2428                                                                                                          * some exception handlers,
2429                                                                                                          * that's ok. */
2430                 {
2431                         LOG2("block L%03d has invalid flags after typecheck: %d",
2432                                  state->m->basicblocks[i].debug_nr,state->m->basicblocks[i].flags);
2433                         TYPECHECK_ASSERT(false);
2434                 }
2435         }
2436 #endif
2437
2438         /* Reset blocks we never reached */
2439
2440         for (i=0; i<state->m->basicblockcount; ++i) {
2441                 if (state->m->basicblocks[i].flags == BBTYPECHECK_UNDEF)
2442                         state->m->basicblocks[i].flags = BBFINISHED;
2443         }
2444 }
2445
2446 /****************************************************************************/
2447 /* typecheck()                                                              */
2448 /* This is the main function of the bytecode verifier. It is called         */
2449 /* directly after analyse_stack.                                            */
2450 /*                                                                          */
2451 /* IN:                                                                      */
2452 /*    meth.............the method to verify                                 */
2453 /*    cdata............codegendata for the method                           */
2454 /*    rdata............registerdata for the method                          */
2455 /*                                                                          */
2456 /* RETURN VALUE:                                                            */
2457 /*     m................successful verification                             */
2458 /*     NULL.............an exception has been thrown                        */
2459 /*                                                                          */
2460 /* XXX TODO:                                                                */
2461 /*     Bytecode verification has not been tested with inlining and          */
2462 /*     probably does not work correctly with inlining.                      */
2463 /****************************************************************************/
2464
2465 #define MAXPARAMS 255
2466
2467 methodinfo *typecheck(methodinfo *meth, codegendata *cdata, registerdata *rdata)
2468 {
2469         verifier_state state;             /* current state of the verifier */
2470     int i;                                        /* temporary counter */
2471
2472         /* collect statistics */
2473
2474 #ifdef TYPECHECK_STATISTICS
2475         int count_iterations = 0;
2476         TYPECHECK_COUNT(stat_typechecked);
2477         TYPECHECK_COUNT_FREQ(stat_locals,cdata->maxlocals,STAT_LOCALS);
2478         TYPECHECK_COUNT_FREQ(stat_blocks,meth->basicblockcount/10,STAT_BLOCKS);
2479 #endif
2480
2481         /* some logging on entry */
2482
2483     LOGSTR("\n==============================================================================\n");
2484     /*DOLOG( show_icmd_method(cdata->method,cdata,rdata));*/
2485     LOGSTR("\n==============================================================================\n");
2486     LOGimpSTR("Entering typecheck: ");
2487     LOGimpSTRu(cdata->method->name);
2488     LOGimpSTR("    ");
2489     LOGimpSTRu(cdata->method->descriptor);
2490     LOGimpSTR("    (class ");
2491     LOGimpSTRu(cdata->method->class->name);
2492     LOGimpSTR(")\n");
2493         LOGFLUSH;
2494
2495         /* initialize the verifier state */
2496
2497         state.savedstackbuf = NULL;
2498         state.savedstack = NULL;
2499         state.jsrencountered = false;
2500         state.m = meth;
2501         state.cd = cdata;
2502         state.rd = rdata;
2503
2504         /* check if this method is an instance initializer method */
2505
2506     state.initmethod = (state.m->name == utf_init);
2507
2508     /* reset all BBFINISHED blocks to BBTYPECHECK_UNDEF. */
2509
2510     i = state.m->basicblockcount;
2511     state.bptr = state.m->basicblocks;
2512     while (--i >= 0) {
2513 #ifdef TYPECHECK_DEBUG
2514         if (state.bptr->flags != BBFINISHED && state.bptr->flags != BBDELETED
2515             && state.bptr->flags != BBUNDEF)
2516         {
2517             /*show_icmd_method(state.cd->method,state.cd,state.rd);*/
2518             LOGSTR1("block flags: %d\n",state.bptr->flags); LOGFLUSH;
2519                         TYPECHECK_ASSERT(false);
2520         }
2521 #endif
2522         if (state.bptr->flags >= BBFINISHED) {
2523             state.bptr->flags = BBTYPECHECK_UNDEF;
2524         }
2525         state.bptr++;
2526     }
2527
2528     /* the first block is always reached */
2529
2530     if (state.m->basicblockcount && state.m->basicblocks[0].flags == BBTYPECHECK_UNDEF)
2531         state.m->basicblocks[0].flags = BBTYPECHECK_REACHED;
2532
2533     LOG("Blocks reset.\n");
2534
2535     /* number of local variables */
2536
2537     /* In <init> methods we use an extra local variable to indicate whether */
2538     /* the 'this' reference has been initialized.                           */
2539         /*         TYPE_VOID...means 'this' has not been initialized,           */
2540         /*         TYPE_INT....means 'this' has been initialized.               */
2541     state.numlocals = state.cd->maxlocals;
2542         state.validlocals = state.numlocals;
2543     if (state.initmethod) state.numlocals++;
2544
2545     /* allocate the buffers for local variables */
2546
2547         state.localbuf = DMNEW_TYPEVECTOR(state.m->basicblockcount+1, state.numlocals);
2548         state.localset = MGET_TYPEVECTOR(state.localbuf,state.m->basicblockcount,state.numlocals);
2549
2550     LOG("Variable buffer allocated.\n");
2551
2552     /* allocate the buffer of active exception handlers */
2553
2554     state.handlers = DMNEW(exceptiontable*, state.cd->exceptiontablelength + 1);
2555
2556         /* initialized local variables of first block */
2557
2558         if (!verify_init_locals(&state))
2559                 return NULL;
2560
2561     /* initialize the input stack of exception handlers */
2562
2563         state.excstack.prev = NULL;
2564         state.excstack.type = TYPE_ADR;
2565         TYPEINFO_INIT_CLASSINFO(state.excstack.typeinfo,
2566                                                         class_java_lang_Throwable); /* changed later */
2567
2568     LOG("Exception handler stacks set.\n");
2569
2570     /* loop while there are still blocks to be checked */
2571     do {
2572                 TYPECHECK_COUNT(count_iterations);
2573
2574         state.repeat = false;
2575
2576         i = state.m->basicblockcount;
2577         state.bptr = state.m->basicblocks;
2578
2579         while (--i >= 0) {
2580             LOGSTR1("---- BLOCK %04d, ",state.bptr->debug_nr);
2581             LOGSTR1("blockflags: %d\n",state.bptr->flags);
2582             LOGFLUSH;
2583
2584                     /* verify reached block */
2585             if (state.bptr->flags == BBTYPECHECK_REACHED) {
2586                 if (!verify_basic_block(&state))
2587                                         return NULL;
2588             }
2589             state.bptr++;
2590         } /* while blocks */
2591
2592         LOGIF(state.repeat,"state.repeat == true");
2593     } while (state.repeat);
2594
2595         /* statistics */
2596
2597 #ifdef TYPECHECK_STATISTICS
2598         LOG1("Typechecker did %4d iterations",count_iterations);
2599         TYPECHECK_COUNT_FREQ(stat_iterations,count_iterations,STAT_ITERATIONS);
2600         TYPECHECK_COUNTIF(state.jsrencountered,stat_typechecked_jsr);
2601 #endif
2602
2603         /* reset the flags of blocks we haven't reached */
2604
2605         typecheck_reset_flags(&state);
2606
2607         /* just return methodinfo* to indicate everything was ok */
2608     LOGimp("exiting typecheck");
2609         return state.m;
2610 }
2611
2612 #undef COPYTYPE
2613
2614 #endif /* CACAO_TYPECHECK */
2615
2616 /*
2617  * These are local overrides for various environment variables in Emacs.
2618  * Please do not remove this and leave it at the end of the file, where
2619  * Emacs will automagically detect them.
2620  * ---------------------------------------------------------------------
2621  * Local variables:
2622  * mode: c
2623  * indent-tabs-mode: t
2624  * c-basic-offset: 4
2625  * tab-width: 4
2626  * End:
2627  * vim:noexpandtab:sw=4:ts=4:
2628  */