src/vm/jit/verify/typecheck.c

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