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