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