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 5729 2006-10-09 23:53:42Z 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 && !invokestatic)
 990                 result = resolve_method_instance_type_checks(
 991                                 state->m, mi,
 992                                 &(VAR(state->iptr->sx.s23.s2.args[0])->typeinfo),
 993                                 invokespecial);
 994
 995         if (result == resolveSucceeded)
 996                 result = resolve_method_param_type_checks(
 997                                 jd, state->m, state->iptr,
 998                                 mi, invokestatic);
 999
1000         /* impose loading constraints */
1001
1002         if (result == resolveSucceeded) {
1003                 /* XXX state->m->class may have to be wrong when inlining */
1004                 if (!resolve_method_loading_constraints(state->m->class, mi))
1005                         return false;
1006         }
1007
1008         if (result == resolveFailed)
1009                 return false;
1010
1011         if (result == resolveSucceeded) {
1012                 /* if this call is monomorphic, turn it into an INVOKESPECIAL */
1013
1014                 if ((state->iptr->opc == ICMD_INVOKEVIRTUAL)
1015                         && (mi->flags & (ACC_FINAL | ACC_PRIVATE)))
1016                 {
1017                         state->iptr->opc = ICMD_INVOKESPECIAL;
1018                 }
1019         }
1020         else {
1021                 /* resolution must be deferred */
1022
1023                 if (!um) {
1024                         um = resolve_create_unresolved_method(state->m->class, state->m,
1025                                         mref,
1026                                         state->iptr->opc == ICMD_INVOKESTATIC,
1027                                         invokespecial);
1028
1029                         if (!um)
1030                                 return false;
1031                 }
1032
1033                 /* record subtype constraints for parameters */
1034
1035                 if (!constrain_unresolved_method(jd, um, state->m->class,
1036                                         state->m, state->iptr))
1037                         return false; /* XXX maybe wrap exception */
1038
1039                 /* store the unresolved_method pointer */
1040
1041                 state->iptr->sx.s23.s3.um = um;
1042                 state->iptr->flags.bits |= INS_FLAG_UNRESOLVED;
1043         }
1044
1045         rtype = md->returntype.type;
1046         if (rtype != TYPE_VOID) {
1047                 dv->type = rtype;
1048                 if (!typeinfo_init_from_typedesc(&(md->returntype),NULL,&(dv->typeinfo)))
1049                         return false;
1050         }
1051
1052         return true;
1053 }
1054
1055
1056 /* verify_generic_builtin ******************************************************
1057
1058    Verify the call of a generic builtin method.
1059
1060    IN:
1061        state............the current state of the verifier
1062
1063    RETURN VALUE:
1064        true.............successful verification,
1065            false............an exception has been thrown.
1066
1067 *******************************************************************************/
1068
1069 static bool
1070 verify_generic_builtin(verifier_state *state)
1071 {
1072         builtintable_entry *bte;
1073         s4 i;
1074         u1 rtype;
1075         methoddesc *md;
1076     varinfo *av;
1077         jitdata *jd = state->jd;
1078
1079         TYPECHECK_COUNT(stat_ins_builtin_gen);
1080
1081         bte = state->iptr->sx.s23.s3.bte;
1082         md = bte->md;
1083         i = md->paramcount;
1084
1085         /* check the types of the arguments on the stack */
1086
1087         for (i--; i >= 0; i--) {
1088                 av = VAR(state->iptr->sx.s23.s2.args[i]);
1089
1090                 if (av->type != md->paramtypes[i].type) {
1091                         TYPECHECK_VERIFYERROR_bool("parameter type mismatch for builtin method");
1092                 }
1093
1094 #ifdef TYPECHECK_DEBUG
1095                 /* generic builtins may only take primitive types and java.lang.Object references */
1096                 if (av->type == TYPE_ADR && md->paramtypes[i].classref->name != utf_java_lang_Object) {
1097                         *exceptionptr = new_internalerror("generic builtin method with non-generic reference parameter");
1098                         return false;
1099                 }
1100 #endif
1101         }
1102
1103         /* set the return type */
1104
1105         rtype = md->returntype.type;
1106         if (rtype != TYPE_VOID) {
1107                 varinfo *dv;
1108
1109                 dv = VAROP(state->iptr->dst);
1110                 dv->type = rtype;
1111                 if (!typeinfo_init_from_typedesc(&(md->returntype),NULL,&(dv->typeinfo)))
1112                         return false;
1113         }
1114
1115         return true;
1116 }
1117
1118
1119 /* verify_builtin **************************************************************
1120
1121    Verify the call of a builtin method.
1122
1123    IN:
1124        state............the current state of the verifier
1125
1126    RETURN VALUE:
1127        true.............successful verification,
1128            false............an exception has been thrown.
1129
1130 *******************************************************************************/
1131
1132 static bool
1133 verify_builtin(verifier_state *state)
1134 {
1135         builtintable_entry *bte;
1136     classref_or_classinfo cls;
1137     varinfo *dv;               /* output variable of current instruction */
1138         jitdata *jd = state->jd;
1139
1140         bte = state->iptr->sx.s23.s3.bte;
1141         dv = VAROP(state->iptr->dst);
1142
1143         /* XXX this is an ugly if-chain but twisti did not want a function */
1144         /* pointer in builtintable_entry for this, so here you go.. ;)     */
1145
1146         if (ISBUILTIN(BUILTIN_new)) {
1147                 if (state->iptr[-1].opc != ICMD_ACONST)
1148                         TYPECHECK_VERIFYERROR_bool("illegal instruction: builtin_new without class");
1149                 cls = state->iptr[-1].sx.val.c;
1150                 dv->type = TYPE_ADR;
1151                 TYPEINFO_INIT_NEWOBJECT(dv->typeinfo,state->iptr);
1152         }
1153         else if (ISBUILTIN(BUILTIN_newarray_boolean)) {
1154                 TYPECHECK_INT(state->iptr->sx.s23.s2.args[0]);
1155                 dv->type = TYPE_ADR;
1156                 TYPEINFO_INIT_PRIMITIVE_ARRAY(dv->typeinfo,ARRAYTYPE_BOOLEAN);
1157         }
1158         else if (ISBUILTIN(BUILTIN_newarray_char)) {
1159                 TYPECHECK_INT(state->iptr->sx.s23.s2.args[0]);
1160                 dv->type = TYPE_ADR;
1161                 TYPEINFO_INIT_PRIMITIVE_ARRAY(dv->typeinfo,ARRAYTYPE_CHAR);
1162         }
1163         else if (ISBUILTIN(BUILTIN_newarray_float)) {
1164                 TYPECHECK_INT(state->iptr->sx.s23.s2.args[0]);
1165                 dv->type = TYPE_ADR;
1166                 TYPEINFO_INIT_PRIMITIVE_ARRAY(dv->typeinfo,ARRAYTYPE_FLOAT);
1167         }
1168         else if (ISBUILTIN(BUILTIN_newarray_double)) {
1169                 TYPECHECK_INT(state->iptr->sx.s23.s2.args[0]);
1170                 dv->type = TYPE_ADR;
1171                 TYPEINFO_INIT_PRIMITIVE_ARRAY(dv->typeinfo,ARRAYTYPE_DOUBLE);
1172         }
1173         else if (ISBUILTIN(BUILTIN_newarray_byte)) {
1174                 TYPECHECK_INT(state->iptr->sx.s23.s2.args[0]);
1175                 dv->type = TYPE_ADR;
1176                 TYPEINFO_INIT_PRIMITIVE_ARRAY(dv->typeinfo,ARRAYTYPE_BYTE);
1177         }
1178         else if (ISBUILTIN(BUILTIN_newarray_short)) {
1179                 TYPECHECK_INT(state->iptr->sx.s23.s2.args[0]);
1180                 dv->type = TYPE_ADR;
1181                 TYPEINFO_INIT_PRIMITIVE_ARRAY(dv->typeinfo,ARRAYTYPE_SHORT);
1182         }
1183         else if (ISBUILTIN(BUILTIN_newarray_int)) {
1184                 TYPECHECK_INT(state->iptr->sx.s23.s2.args[0]);
1185                 dv->type = TYPE_ADR;
1186                 TYPEINFO_INIT_PRIMITIVE_ARRAY(dv->typeinfo,ARRAYTYPE_INT);
1187         }
1188         else if (ISBUILTIN(BUILTIN_newarray_long)) {
1189                 TYPECHECK_INT(state->iptr->sx.s23.s2.args[0]);
1190                 dv->type = TYPE_ADR;
1191                 TYPEINFO_INIT_PRIMITIVE_ARRAY(dv->typeinfo,ARRAYTYPE_LONG);
1192         }
1193         else if (ISBUILTIN(BUILTIN_newarray))
1194         {
1195                 TYPECHECK_INT(state->iptr->sx.s23.s2.args[0]);
1196                 if (state->iptr[-1].opc != ICMD_ACONST)
1197                         TYPECHECK_VERIFYERROR_bool("illegal instruction: builtin_newarray without class");
1198                 /* XXX check that it is an array class(ref) */
1199                 dv->type = TYPE_ADR;
1200                 typeinfo_init_class(&(dv->typeinfo),state->iptr[-1].sx.val.c);
1201         }
1202         else if (ISBUILTIN(BUILTIN_arrayinstanceof))
1203         {
1204                 TYPECHECK_ADR(state->iptr->sx.s23.s2.args[0]);
1205                 if (state->iptr[-1].opc != ICMD_ACONST)
1206                         TYPECHECK_VERIFYERROR_bool("illegal instruction: builtin_arrayinstanceof without class");
1207                 dv->type = TYPE_INT;
1208                 /* XXX check that it is an array class(ref) */
1209         }
1210         else {
1211                 return verify_generic_builtin(state);
1212         }
1213         return true;
1214 }
1215
1216
1217 /* verify_multianewarray *******************************************************
1218
1219    Verify a MULTIANEWARRAY instruction.
1220
1221    IN:
1222        state............the current state of the verifier
1223
1224    RETURN VALUE:
1225        true.............successful verification,
1226            false............an exception has been thrown.
1227
1228 *******************************************************************************/
1229
1230 static bool
1231 verify_multianewarray(verifier_state *state)
1232 {
1233         classinfo *arrayclass;
1234         arraydescriptor *desc;
1235         s4 i;
1236         jitdata *jd = state->jd;
1237
1238         /* check the array lengths on the stack */
1239         i = state->iptr->s1.argcount;
1240         if (i < 1)
1241                 TYPECHECK_VERIFYERROR_bool("Illegal dimension argument");
1242
1243         while (i--) {
1244                 TYPECHECK_INT(state->iptr->sx.s23.s2.args[i]);
1245         }
1246
1247         /* check array descriptor */
1248         if (INSTRUCTION_IS_RESOLVED(state->iptr)) {
1249                 /* the array class reference has already been resolved */
1250                 arrayclass = state->iptr->sx.s23.s3.c.cls;
1251                 if (!arrayclass)
1252                         TYPECHECK_VERIFYERROR_bool("MULTIANEWARRAY with unlinked class");
1253                 if ((desc = arrayclass->vftbl->arraydesc) == NULL)
1254                         TYPECHECK_VERIFYERROR_bool("MULTIANEWARRAY with non-array class");
1255                 if (desc->dimension < state->iptr->s1.argcount)
1256                         TYPECHECK_VERIFYERROR_bool("MULTIANEWARRAY dimension to high");
1257
1258                 /* set the array type of the result */
1259                 typeinfo_init_classinfo(&(VAROP(state->iptr->dst)->typeinfo), arrayclass);
1260         }
1261         else {
1262                 const char *p;
1263                 constant_classref *cr;
1264
1265                 /* the array class reference is still unresolved */
1266                 /* check that the reference indicates an array class of correct dimension */
1267                 cr = state->iptr->sx.s23.s3.c.ref;
1268                 i = 0;
1269                 p = cr->name->text;
1270                 while (p[i] == '[')
1271                         i++;
1272                 /* { the dimension of the array class == i } */
1273                 if (i < 1)
1274                         TYPECHECK_VERIFYERROR_bool("MULTIANEWARRAY with non-array class");
1275                 if (i < state->iptr->s1.argcount)
1276                         TYPECHECK_VERIFYERROR_bool("MULTIANEWARRAY dimension to high");
1277
1278                 /* set the array type of the result */
1279                 if (!typeinfo_init_class(&(VAROP(state->iptr->dst)->typeinfo),CLASSREF_OR_CLASSINFO(cr)))
1280                         return false;
1281         }
1282
1283         /* set return type */
1284
1285         VAROP(state->iptr->dst)->type = TYPE_ADR;
1286
1287         /* everything ok */
1288         return true;
1289 }
1290
1291
1292 /* typecheck_invalidate_locals *************************************************
1293
1294    Invalidate locals that are overwritten by writing to the given local.
1295
1296    IN:
1297        state............the current state of the verifier
1298            index............the index of the local that is written
1299            twoword..........true, if a two-word type is written
1300
1301 *******************************************************************************/
1302
1303 static void typecheck_invalidate_locals(verifier_state *state, s4 index, bool twoword)
1304 {
1305         s4 i;
1306         s4 t;
1307         s4 mapped;
1308         jitdata *jd = state->jd;
1309         s4 *localmap = jd->local_map;
1310         varinfo *vars = jd->var;
1311
1312         i = state->reverselocalmap[index];
1313
1314         /* invalidate locals of two-word type at index i-1 */
1315
1316         if (i > 0) {
1317                 localmap += 5 * (i-1);
1318                 for (t=0; t<5; ++t) {
1319                         mapped = *localmap++;
1320                         if (mapped >= 0 && IS_2_WORD_TYPE(vars[mapped].type)) {
1321                                 LOG1("invalidate local %d", mapped);
1322                                 vars[mapped].type = TYPE_VOID;
1323                         }
1324                 }
1325         }
1326         else {
1327                 localmap += 5 * i;
1328         }
1329
1330         /* invalidate locals at index i */
1331
1332         for (t=0; t<5; ++t) {
1333                 mapped = *localmap++;
1334                 if (mapped >= 0) {
1335                         LOG1("invalidate local %d", mapped);
1336                         vars[mapped].type = TYPE_VOID;
1337                 }
1338         }
1339
1340         /* if a two-word type is written, invalidate locals at index i+1 */
1341
1342         if (twoword) {
1343                 for (t=0; t<5; ++t) {
1344                         mapped = *localmap++;
1345                         if (mapped >= 0) {
1346                                 LOG1("invalidate local %d", mapped);
1347                                 vars[mapped].type = TYPE_VOID;
1348                         }
1349                 }
1350         }
1351 }
1352
1353
1354 /* verify_basic_block **********************************************************
1355
1356    Perform bytecode verification of a basic block.
1357
1358    IN:
1359        state............the current state of the verifier
1360
1361    RETURN VALUE:
1362        true.............successful verification,
1363            false............an exception has been thrown.
1364
1365 *******************************************************************************/
1366
1367 static bool
1368 verify_basic_block(verifier_state *state)
1369 {
1370     int opcode;                                      /* current opcode */
1371     int len;                        /* for counting instructions, etc. */
1372     bool superblockend;        /* true if no fallthrough to next block */
1373         instruction *iptr;                      /* the current instruction */
1374     basicblock *tbptr;                   /* temporary for target block */
1375     bool maythrow;               /* true if this instruction may throw */
1376         unresolved_field *uf;                        /* for field accesses */
1377         constant_FMIref *fieldref;                   /* for field accesses */
1378         s4 i;
1379         typecheck_result r;
1380         resolve_result_t result;
1381         branch_target_t *table;
1382         lookup_target_t *lookup;
1383         jitdata *jd = state->jd;
1384         varinfo *dv;
1385         exceptiontable *ex;
1386
1387         LOGSTR1("\n---- BLOCK %04d ------------------------------------------------\n",state->bptr->nr);
1388         LOGFLUSH;
1389         DOLOG(show_basicblock(jd, state->bptr, SHOW_STACK));
1390
1391         superblockend = false;
1392         state->bptr->flags = BBFINISHED;
1393
1394         /* prevent compiler warnings */
1395
1396         dv = NULL;
1397
1398         /* determine the active exception handlers for this block */
1399         /* XXX could use a faster algorithm with sorted lists or  */
1400         /* something?                                             */
1401         len = 0;
1402         for (ex = state->cd->exceptiontable; ex ; ex = ex->down) {
1403                 if ((ex->start->nr <= state->bptr->nr) && (ex->end->nr > state->bptr->nr)) {
1404                         LOG1("active handler L%03d", ex->handler->nr);
1405                         state->handlers[len++] = ex;
1406                 }
1407         }
1408         state->handlers[len] = NULL;
1409
1410         /* init variable types at the start of this block */
1411         typevector_copy_inplace(state->bptr->inlocals, jd->var, state->numlocals);
1412
1413         DOLOG(typecheck_print_vararray(stdout, jd, state->bptr->invars,
1414                                 state->bptr->indepth));
1415         DOLOG(typevector_print(stdout, jd->var, state->numlocals));
1416         LOGNL; LOGFLUSH;
1417
1418         /* loop over the instructions */
1419         len = state->bptr->icount;
1420         state->iptr = state->bptr->iinstr;
1421         while (--len >= 0)  {
1422                 TYPECHECK_COUNT(stat_ins);
1423
1424                 iptr = state->iptr;
1425
1426                 DOLOG(typevector_print(stdout, jd->var, state->numlocals));
1427                 LOGNL; LOGFLUSH;
1428                 DOLOG(show_icmd(jd, state->iptr, false, SHOW_STACK)); LOGNL; LOGFLUSH;
1429
1430                 opcode = iptr->opc;
1431                 dv = VAROP(iptr->dst);
1432                 maythrow = false;
1433
1434                 switch (opcode) {
1435
1436                         /****************************************/
1437                         /* STACK MANIPULATIONS                  */
1438
1439                         /* We just need to copy the typeinfo */
1440                         /* for slots containing addresses.   */
1441
1442                         case ICMD_MOVE:
1443                         case ICMD_COPY:
1444                                 TYPECHECK_COUNT(stat_ins_stack);
1445                                 COPYTYPE(iptr->s1, iptr->dst);
1446                                 dv->type = VAROP(iptr->s1)->type;
1447                                 break;
1448
1449                                 /****************************************/
1450                                 /* PRIMITIVE VARIABLE ACCESS            */
1451
1452                         case ICMD_ILOAD: 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_IINC:  if (!typevector_checktype(jd->var,state->iptr->s1.varindex,TYPE_INT))
1457                                                                  TYPECHECK_VERIFYERROR_bool("Local variable type mismatch");
1458                                                          dv->type = TYPE_INT;
1459                                                          break;
1460                         case ICMD_FLOAD: if (!typevector_checktype(jd->var,state->iptr->s1.varindex,TYPE_FLT))
1461                                                                  TYPECHECK_VERIFYERROR_bool("Local variable type mismatch");
1462                                                          dv->type = TYPE_FLT;
1463                                                          break;
1464                         case ICMD_LLOAD: if (!typevector_checktype(jd->var,state->iptr->s1.varindex,TYPE_LNG))
1465                                                                  TYPECHECK_VERIFYERROR_bool("Local variable type mismatch");
1466                                                          dv->type = TYPE_LNG;
1467                                                          break;
1468                         case ICMD_DLOAD: if (!typevector_checktype(jd->var,state->iptr->s1.varindex,TYPE_DBL))
1469                                                                  TYPECHECK_VERIFYERROR_bool("Local variable type mismatch");
1470                                                          dv->type = TYPE_DBL;
1471                                                          break;
1472
1473                         case ICMD_ISTORE:
1474                                                          typecheck_invalidate_locals(state, state->iptr->dst.varindex, false);
1475                                                          typevector_store(jd->var,state->iptr->dst.varindex,TYPE_INT,NULL);
1476                                                          break;
1477                         case ICMD_FSTORE:
1478                                                          typecheck_invalidate_locals(state, state->iptr->dst.varindex, false);
1479                                                          typevector_store(jd->var,state->iptr->dst.varindex,TYPE_FLT,NULL);
1480                                                          break;
1481                         case ICMD_LSTORE:
1482                                                          typecheck_invalidate_locals(state, state->iptr->dst.varindex, true);
1483                                                          typevector_store(jd->var,state->iptr->dst.varindex,TYPE_LNG,NULL);
1484                                                          break;
1485                         case ICMD_DSTORE:
1486                                                          typecheck_invalidate_locals(state, state->iptr->dst.varindex, true);
1487                                                          typevector_store(jd->var,state->iptr->dst.varindex,TYPE_DBL,NULL);
1488                                                          break;
1489
1490                                 /****************************************/
1491                                 /* LOADING ADDRESS FROM VARIABLE        */
1492
1493                         case ICMD_ALOAD:
1494                                 TYPECHECK_COUNT(stat_ins_aload);
1495
1496                                 /* loading a returnAddress is not allowed */
1497                                 if (!TYPEDESC_IS_REFERENCE(*VAROP(state->iptr->s1))) {
1498                                         TYPECHECK_VERIFYERROR_bool("illegal instruction: ALOAD loading non-reference");
1499                                 }
1500                                 TYPEINFO_COPY(VAROP(state->iptr->s1)->typeinfo,dv->typeinfo);
1501                                 dv->type = TYPE_ADR;
1502                                 break;
1503
1504                                 /****************************************/
1505                                 /* STORING ADDRESS TO VARIABLE          */
1506
1507                         case ICMD_ASTORE:
1508                                 typecheck_invalidate_locals(state, state->iptr->dst.varindex, false);
1509
1510                                 if (TYPEINFO_IS_PRIMITIVE(VAROP(state->iptr->s1)->typeinfo)) {
1511                                         typevector_store_retaddr(jd->var,state->iptr->dst.varindex,&(VAROP(state->iptr->s1)->typeinfo));
1512                                 }
1513                                 else {
1514                                         typevector_store(jd->var,state->iptr->dst.varindex,TYPE_ADR,
1515                                                         &(VAROP(state->iptr->s1)->typeinfo));
1516                                 }
1517                                 break;
1518
1519                                 /****************************************/
1520                                 /* LOADING ADDRESS FROM ARRAY           */
1521
1522                         case ICMD_AALOAD:
1523                                 if (!TYPEINFO_MAYBE_ARRAY_OF_REFS(VAROP(state->iptr->s1)->typeinfo))
1524                                         TYPECHECK_VERIFYERROR_bool("illegal instruction: AALOAD on non-reference array");
1525
1526                                 if (!typeinfo_init_component(&VAROP(state->iptr->s1)->typeinfo,&dv->typeinfo))
1527                                         return false;
1528                                 dv->type = TYPE_ADR;
1529                                 maythrow = true;
1530                                 break;
1531
1532                                 /****************************************/
1533                                 /* FIELD ACCESS                         */
1534
1535                         case ICMD_PUTFIELD:
1536                         case ICMD_PUTSTATIC:
1537                         case ICMD_PUTFIELDCONST:
1538                         case ICMD_PUTSTATICCONST:
1539                         case ICMD_GETFIELD:
1540                         case ICMD_GETSTATIC:
1541                                 {
1542                                         varinfo *valueslot = NULL;
1543                                         typeinfo *instanceti = NULL;
1544                                         typeinfo *valueti = NULL;
1545                                         bool isstatic = false;
1546                                         bool isput = false;
1547                                         typeinfo constti;
1548
1549                                         TYPECHECK_COUNT(stat_ins_field);
1550
1551                                         if (INSTRUCTION_IS_UNRESOLVED(state->iptr)) {
1552                                                 uf = state->iptr->sx.s23.s3.uf;
1553                                                 fieldref = uf->fieldref;
1554                                         }
1555                                         else {
1556                                                 uf = NULL;
1557                                                 fieldref = state->iptr->sx.s23.s3.fmiref;
1558                                         }
1559
1560                                         /* get opcode dependent values */
1561
1562                                         switch (state->iptr->opc) {
1563                                                 case ICMD_PUTFIELD:
1564                                                         isput = true;
1565                                                         valueslot = VAROP(state->iptr->sx.s23.s2);
1566                                                         instanceti = &(VAROP(state->iptr->s1)->typeinfo);
1567                                                         break;
1568
1569                                                 case ICMD_PUTFIELDCONST:
1570                                                         isput = true;
1571                                                         instanceti = &(VAROP(state->iptr->s1)->typeinfo);
1572 putfield_const_tail:
1573                                                         if (IS_ADR_TYPE(fieldref->parseddesc.fd->type)) {
1574                                                                 /* XXX check for java.lang.Class constant values? */
1575                                                                 if (state->iptr->sx.val.anyptr) {
1576                                                                         assert(class_java_lang_String);
1577                                                                         assert(class_java_lang_String->state & CLASS_LOADED);
1578                                                                         assert(class_java_lang_String->state & CLASS_LINKED);
1579                                                                         typeinfo_init_classinfo(&constti, class_java_lang_String);
1580                                                                 }
1581                                                                 else {
1582                                                                         TYPEINFO_INIT_NULLTYPE(constti);
1583                                                                 }
1584                                                                 valueti = &constti;
1585                                                         }
1586                                                         break;
1587
1588                                                 case ICMD_PUTSTATIC:
1589                                                         isput = true;
1590                                                         isstatic = true;
1591                                                         valueslot = VAROP(state->iptr->s1);
1592                                                         break;
1593
1594                                                 case ICMD_PUTSTATICCONST:
1595                                                         isput = true;
1596                                                         isstatic = true;
1597                                                         goto putfield_const_tail;
1598
1599                                                 case ICMD_GETFIELD:
1600                                                         instanceti = &(VAROP(state->iptr->s1)->typeinfo);
1601                                                         break;
1602
1603                                                 case ICMD_GETSTATIC:
1604                                                         isstatic = true;
1605                                                         break;
1606
1607                                                 default:
1608                                                         assert(false);
1609                                         }
1610
1611                                         if (valueslot && IS_ADR_TYPE(valueslot->type)) {
1612                                                 valueti = &(valueslot->typeinfo);
1613                                         }
1614
1615                                         /* try to resolve the field reference lazily */
1616
1617                                         result = resolve_field_lazy(state->m, fieldref);
1618
1619                                         if (result == resolveSucceeded) {
1620                                                 fieldinfo *fi;
1621
1622                                                 /* perform verification checks now */
1623
1624                                                 fi  = fieldref->p.field;
1625
1626                                                 result = resolve_field_verifier_checks(
1627                                                                 state->m, fieldref, fi->class, fi,
1628                                                                 instanceti, valueti, isstatic, isput);
1629                                         }
1630
1631                                         if (result == resolveFailed)
1632                                                 return false;
1633
1634                                         /* if not resolved, yet, create an unresolved field */
1635
1636                                         if (result != resolveSucceeded) {
1637                                                 if (!uf) {
1638                                                         uf = resolve_create_unresolved_field(state->m->class,
1639                                                                         state->m, state->iptr);
1640                                                         if (!uf)
1641                                                                 return false;
1642
1643                                                         state->iptr->sx.s23.s3.uf = uf;
1644                                                         state->iptr->flags.bits |= INS_FLAG_UNRESOLVED;
1645                                                 }
1646
1647                                                 /* record the subtype constraints for this field access */
1648
1649                                                 if (!resolve_constrain_unresolved_field(
1650                                                                         uf, state->m->class, state->m,
1651                                                                         instanceti, valueti))
1652                                                         return false; /* XXX maybe wrap exception? */
1653
1654                                                 TYPECHECK_COUNTIF(INSTRUCTION_IS_UNRESOLVED(state->iptr),stat_ins_field_unresolved);
1655                                                 TYPECHECK_COUNTIF(INSTRUCTION_IS_RESOLVED(state->iptr) &&
1656                                                                 !state->iptr->sx.s23.s3.fmiref->p.field->class->initialized,
1657                                                                 stat_ins_field_uninitialized);
1658                                         }
1659
1660                                         /* write the result type */
1661
1662                                         if (iptr->opc == ICMD_GETFIELD || iptr->opc == ICMD_GETSTATIC) {
1663                                                 dv->type = fieldref->parseddesc.fd->type;
1664                                                 if (dv->type == TYPE_ADR) {
1665                                                         if (!typeinfo_init_from_typedesc(fieldref->parseddesc.fd,
1666                                                                                 NULL, &(dv->typeinfo)))
1667                                                                 return false;
1668                                                 }
1669                                         }
1670
1671                                         maythrow = true;
1672                                 }
1673                                 break;
1674
1675                                 /****************************************/
1676                                 /* PRIMITIVE ARRAY ACCESS               */
1677
1678                         case ICMD_ARRAYLENGTH:
1679                                 if (!TYPEINFO_MAYBE_ARRAY(VAROP(state->iptr->s1)->typeinfo)
1680                                                 && VAROP(state->iptr->s1)->typeinfo.typeclass.cls != pseudo_class_Arraystub)
1681                                         TYPECHECK_VERIFYERROR_bool("illegal instruction: ARRAYLENGTH on non-array");
1682                                 dv->type = TYPE_INT;
1683                                 maythrow = true;
1684                                 break;
1685
1686                         case ICMD_BALOAD:
1687                                 if (!TYPEINFO_MAYBE_PRIMITIVE_ARRAY(VAROP(state->iptr->s1)->typeinfo,ARRAYTYPE_BOOLEAN)
1688                                                 && !TYPEINFO_MAYBE_PRIMITIVE_ARRAY(VAROP(state->iptr->s1)->typeinfo,ARRAYTYPE_BYTE))
1689                                         TYPECHECK_VERIFYERROR_bool("Array type mismatch");
1690                                 dv->type = TYPE_INT;
1691                                 maythrow = true;
1692                                 break;
1693                         case ICMD_CALOAD:
1694                                 if (!TYPEINFO_MAYBE_PRIMITIVE_ARRAY(VAROP(state->iptr->s1)->typeinfo,ARRAYTYPE_CHAR))
1695                                         TYPECHECK_VERIFYERROR_bool("Array type mismatch");
1696                                 dv->type = TYPE_INT;
1697                                 maythrow = true;
1698                                 break;
1699                         case ICMD_DALOAD:
1700                                 if (!TYPEINFO_MAYBE_PRIMITIVE_ARRAY(VAROP(state->iptr->s1)->typeinfo,ARRAYTYPE_DOUBLE))
1701                                         TYPECHECK_VERIFYERROR_bool("Array type mismatch");
1702                                 dv->type = TYPE_DBL;
1703                                 maythrow = true;
1704                                 break;
1705                         case ICMD_FALOAD:
1706                                 if (!TYPEINFO_MAYBE_PRIMITIVE_ARRAY(VAROP(state->iptr->s1)->typeinfo,ARRAYTYPE_FLOAT))
1707                                         TYPECHECK_VERIFYERROR_bool("Array type mismatch");
1708                                 dv->type = TYPE_FLT;
1709                                 maythrow = true;
1710                                 break;
1711                         case ICMD_IALOAD:
1712                                 if (!TYPEINFO_MAYBE_PRIMITIVE_ARRAY(VAROP(state->iptr->s1)->typeinfo,ARRAYTYPE_INT))
1713                                         TYPECHECK_VERIFYERROR_bool("Array type mismatch");
1714                                 dv->type = TYPE_INT;
1715                                 maythrow = true;
1716                                 break;
1717                         case ICMD_SALOAD:
1718                                 if (!TYPEINFO_MAYBE_PRIMITIVE_ARRAY(VAROP(state->iptr->s1)->typeinfo,ARRAYTYPE_SHORT))
1719                                         TYPECHECK_VERIFYERROR_bool("Array type mismatch");
1720                                 dv->type = TYPE_INT;
1721                                 maythrow = true;
1722                                 break;
1723                         case ICMD_LALOAD:
1724                                 if (!TYPEINFO_MAYBE_PRIMITIVE_ARRAY(VAROP(state->iptr->s1)->typeinfo,ARRAYTYPE_LONG))
1725                                         TYPECHECK_VERIFYERROR_bool("Array type mismatch");
1726                                 dv->type = TYPE_LNG;
1727                                 maythrow = true;
1728                                 break;
1729
1730                         case ICMD_BASTORE:
1731                                 if (!TYPEINFO_MAYBE_PRIMITIVE_ARRAY(VAROP(state->iptr->s1)->typeinfo,ARRAYTYPE_BOOLEAN)
1732                                                 && !TYPEINFO_MAYBE_PRIMITIVE_ARRAY(VAROP(state->iptr->s1)->typeinfo,ARRAYTYPE_BYTE))
1733                                         TYPECHECK_VERIFYERROR_bool("Array type mismatch");
1734                                 maythrow = true;
1735                                 break;
1736                         case ICMD_CASTORE:
1737                                 if (!TYPEINFO_MAYBE_PRIMITIVE_ARRAY(VAROP(state->iptr->s1)->typeinfo,ARRAYTYPE_CHAR))
1738                                         TYPECHECK_VERIFYERROR_bool("Array type mismatch");
1739                                 maythrow = true;
1740                                 break;
1741                         case ICMD_DASTORE:
1742                                 if (!TYPEINFO_MAYBE_PRIMITIVE_ARRAY(VAROP(state->iptr->s1)->typeinfo,ARRAYTYPE_DOUBLE))
1743                                         TYPECHECK_VERIFYERROR_bool("Array type mismatch");
1744                                 maythrow = true;
1745                                 break;
1746                         case ICMD_FASTORE:
1747                                 if (!TYPEINFO_MAYBE_PRIMITIVE_ARRAY(VAROP(state->iptr->s1)->typeinfo,ARRAYTYPE_FLOAT))
1748                                         TYPECHECK_VERIFYERROR_bool("Array type mismatch");
1749                                 maythrow = true;
1750                                 break;
1751                         case ICMD_IASTORE:
1752                                 if (!TYPEINFO_MAYBE_PRIMITIVE_ARRAY(VAROP(state->iptr->s1)->typeinfo,ARRAYTYPE_INT))
1753                                         TYPECHECK_VERIFYERROR_bool("Array type mismatch");
1754                                 maythrow = true;
1755                                 break;
1756                         case ICMD_SASTORE:
1757                                 if (!TYPEINFO_MAYBE_PRIMITIVE_ARRAY(VAROP(state->iptr->s1)->typeinfo,ARRAYTYPE_SHORT))
1758                                         TYPECHECK_VERIFYERROR_bool("Array type mismatch");
1759                                 maythrow = true;
1760                                 break;
1761                         case ICMD_LASTORE:
1762                                 if (!TYPEINFO_MAYBE_PRIMITIVE_ARRAY(VAROP(state->iptr->s1)->typeinfo,ARRAYTYPE_LONG))
1763                                         TYPECHECK_VERIFYERROR_bool("Array type mismatch");
1764                                 maythrow = true;
1765                                 break;
1766
1767                         case ICMD_AASTORE:
1768                                 /* we just check the basic input types and that the           */
1769                                 /* destination is an array of references. Assignability to    */
1770                                 /* the actual array must be checked at runtime, each time the */
1771                                 /* instruction is performed. (See builtin_canstore.)          */
1772                                 TYPECHECK_ADR_OP(state->iptr->sx.s23.s3);
1773                                 TYPECHECK_INT_OP(state->iptr->sx.s23.s2);
1774                                 TYPECHECK_ADR_OP(state->iptr->s1);
1775                                 if (!TYPEINFO_MAYBE_ARRAY_OF_REFS(VAROP(state->iptr->s1)->typeinfo))
1776                                         TYPECHECK_VERIFYERROR_bool("illegal instruction: AASTORE to non-reference array");
1777                                 maythrow = true;
1778                                 break;
1779
1780                         case ICMD_IASTORECONST:
1781                                 if (!TYPEINFO_MAYBE_PRIMITIVE_ARRAY(VAROP(state->iptr->s1)->typeinfo, ARRAYTYPE_INT))
1782                                         TYPECHECK_VERIFYERROR_bool("Array type mismatch");
1783                                 maythrow = true;
1784                                 break;
1785
1786                         case ICMD_LASTORECONST:
1787                                 if (!TYPEINFO_MAYBE_PRIMITIVE_ARRAY(VAROP(state->iptr->s1)->typeinfo, ARRAYTYPE_LONG))
1788                                         TYPECHECK_VERIFYERROR_bool("Array type mismatch");
1789                                 maythrow = true;
1790                                 break;
1791
1792                         case ICMD_BASTORECONST:
1793                                 if (!TYPEINFO_MAYBE_PRIMITIVE_ARRAY(VAROP(state->iptr->s1)->typeinfo, ARRAYTYPE_BOOLEAN)
1794                                                 && !TYPEINFO_MAYBE_PRIMITIVE_ARRAY(VAROP(state->iptr->s1)->typeinfo, ARRAYTYPE_BYTE))
1795                                         TYPECHECK_VERIFYERROR_bool("Array type mismatch");
1796                                 maythrow = true;
1797                                 break;
1798
1799                         case ICMD_CASTORECONST:
1800                                 if (!TYPEINFO_MAYBE_PRIMITIVE_ARRAY(VAROP(state->iptr->s1)->typeinfo, ARRAYTYPE_CHAR))
1801                                         TYPECHECK_VERIFYERROR_bool("Array type mismatch");
1802                                 maythrow = true;
1803                                 break;
1804
1805                         case ICMD_SASTORECONST:
1806                                 if (!TYPEINFO_MAYBE_PRIMITIVE_ARRAY(VAROP(state->iptr->s1)->typeinfo, ARRAYTYPE_SHORT))
1807                                         TYPECHECK_VERIFYERROR_bool("Array type mismatch");
1808                                 maythrow = true;
1809                                 break;
1810
1811                                 /****************************************/
1812                                 /* ADDRESS CONSTANTS                    */
1813
1814                         case ICMD_ACONST:
1815                                 if (state->iptr->flags.bits & INS_FLAG_CLASS) {
1816                                         /* a java.lang.Class reference */
1817                                         TYPEINFO_INIT_JAVA_LANG_CLASS(dv->typeinfo,state->iptr->sx.val.c);
1818                                 }
1819                                 else {
1820                                         if (state->iptr->sx.val.anyptr == NULL)
1821                                                 TYPEINFO_INIT_NULLTYPE(dv->typeinfo);
1822                                         else {
1823                                                 /* string constant (or constant for builtin function) */
1824                                                 typeinfo_init_classinfo(&(dv->typeinfo),class_java_lang_String);
1825                                         }
1826                                 }
1827                                 dv->type = TYPE_ADR;
1828                                 break;
1829
1830                                 /****************************************/
1831                                 /* CHECKCAST AND INSTANCEOF             */
1832
1833                         case ICMD_CHECKCAST:
1834                                 TYPECHECK_ADR_OP(state->iptr->s1);
1835                                 /* returnAddress is not allowed */
1836                                 if (!TYPEINFO_IS_REFERENCE(VAROP(state->iptr->s1)->typeinfo))
1837                                         TYPECHECK_VERIFYERROR_bool("Illegal instruction: CHECKCAST on non-reference");
1838
1839                                 if (!typeinfo_init_class(&(dv->typeinfo),state->iptr->sx.s23.s3.c))
1840                                                 return false;
1841                                 dv->type = TYPE_ADR;
1842                                 maythrow = true;
1843                                 break;
1844
1845                         case ICMD_INSTANCEOF:
1846                                 TYPECHECK_ADR_OP(state->iptr->s1);
1847                                 /* returnAddress is not allowed */
1848                                 if (!TYPEINFO_IS_REFERENCE(VAROP(state->iptr->s1)->typeinfo))
1849                                         TYPECHECK_VERIFYERROR_bool("Illegal instruction: INSTANCEOF on non-reference");
1850                                 dv->type = TYPE_INT;
1851                                 break;
1852
1853                                 /****************************************/
1854                                 /* BRANCH INSTRUCTIONS                  */
1855
1856                         case ICMD_INLINE_GOTO:
1857                                 COPYTYPE(state->iptr->s1,state->iptr->dst);
1858                                 /* FALLTHROUGH! */
1859                         case ICMD_GOTO:
1860                                 superblockend = true;
1861                                 /* FALLTHROUGH! */
1862                         case ICMD_IFNULL:
1863                         case ICMD_IFNONNULL:
1864                         case ICMD_IFEQ:
1865                         case ICMD_IFNE:
1866                         case ICMD_IFLT:
1867                         case ICMD_IFGE:
1868                         case ICMD_IFGT:
1869                         case ICMD_IFLE:
1870                         case ICMD_IF_ICMPEQ:
1871                         case ICMD_IF_ICMPNE:
1872                         case ICMD_IF_ICMPLT:
1873                         case ICMD_IF_ICMPGE:
1874                         case ICMD_IF_ICMPGT:
1875                         case ICMD_IF_ICMPLE:
1876                         case ICMD_IF_ACMPEQ:
1877                         case ICMD_IF_ACMPNE:
1878
1879                         case ICMD_IF_LEQ:
1880                         case ICMD_IF_LNE:
1881                         case ICMD_IF_LLT:
1882                         case ICMD_IF_LGE:
1883                         case ICMD_IF_LGT:
1884                         case ICMD_IF_LLE:
1885
1886                         case ICMD_IF_LCMPEQ:
1887                         case ICMD_IF_LCMPNE:
1888                         case ICMD_IF_LCMPLT:
1889                         case ICMD_IF_LCMPGE:
1890                         case ICMD_IF_LCMPGT:
1891                         case ICMD_IF_LCMPLE:
1892
1893                         case ICMD_IF_FCMPEQ:
1894                         case ICMD_IF_FCMPNE:
1895
1896                         case ICMD_IF_FCMPL_LT:
1897                         case ICMD_IF_FCMPL_GE:
1898                         case ICMD_IF_FCMPL_GT:
1899                         case ICMD_IF_FCMPL_LE:
1900
1901                         case ICMD_IF_FCMPG_LT:
1902                         case ICMD_IF_FCMPG_GE:
1903                         case ICMD_IF_FCMPG_GT:
1904                         case ICMD_IF_FCMPG_LE:
1905
1906                         case ICMD_IF_DCMPEQ:
1907                         case ICMD_IF_DCMPNE:
1908
1909                         case ICMD_IF_DCMPL_LT:
1910                         case ICMD_IF_DCMPL_GE:
1911                         case ICMD_IF_DCMPL_GT:
1912                         case ICMD_IF_DCMPL_LE:
1913
1914                         case ICMD_IF_DCMPG_LT:
1915                         case ICMD_IF_DCMPG_GE:
1916                         case ICMD_IF_DCMPG_GT:
1917                         case ICMD_IF_DCMPG_LE:
1918                                 TYPECHECK_COUNT(stat_ins_branch);
1919
1920                                 /* propagate stack and variables to the target block */
1921                                 if (!typestate_reach(state, state->iptr->dst.block,
1922                                                                          state->bptr->outvars, jd->var,
1923                                                                          state->bptr->outdepth))
1924                                         return false;
1925                                 break;
1926
1927                                 /****************************************/
1928                                 /* SWITCHES                             */
1929
1930                         case ICMD_TABLESWITCH:
1931                                 TYPECHECK_COUNT(stat_ins_switch);
1932
1933                                 table = iptr->dst.table;
1934                                 i = iptr->sx.s23.s3.tablehigh
1935                                         - iptr->sx.s23.s2.tablelow + 1 + 1; /* plus default */
1936
1937                                 while (--i >= 0) {
1938                                         tbptr = (table++)->block;
1939                                         LOG2("target %d is block %04d",i,tbptr->nr);
1940                                         if (!typestate_reach(state, tbptr, state->bptr->outvars,
1941                                                                                  jd->var, state->bptr->outdepth))
1942                                                 return false;
1943                                 }
1944
1945                                 LOG("switch done");
1946                                 superblockend = true;
1947                                 break;
1948
1949                         case ICMD_LOOKUPSWITCH:
1950                                 TYPECHECK_COUNT(stat_ins_switch);
1951
1952                                 lookup = iptr->dst.lookup;
1953                                 i = iptr->sx.s23.s2.lookupcount;
1954
1955                                 if (!typestate_reach(state,iptr->sx.s23.s3.lookupdefault.block,
1956                                                                          state->bptr->outvars, jd->var,
1957                                                                          state->bptr->outdepth))
1958                                         return false;
1959
1960                                 while (--i >= 0) {
1961                                         tbptr = (lookup++)->target.block;
1962                                         LOG2("target %d is block %04d",i,tbptr->nr);
1963                                         if (!typestate_reach(state, tbptr, state->bptr->outvars,
1964                                                                 jd->var, state->bptr->outdepth))
1965                                                 return false;
1966                                 }
1967
1968                                 LOG("switch done");
1969                                 superblockend = true;
1970                                 break;
1971
1972
1973                                 /****************************************/
1974                                 /* ADDRESS RETURNS AND THROW            */
1975
1976                         case ICMD_ATHROW:
1977                                 TYPECHECK_COUNT(stat_ins_athrow);
1978                                 r = typeinfo_is_assignable_to_class(&VAROP(state->iptr->s1)->typeinfo,
1979                                                 CLASSREF_OR_CLASSINFO(class_java_lang_Throwable));
1980                                 if (r == typecheck_FALSE)
1981                                         TYPECHECK_VERIFYERROR_bool("illegal instruction: ATHROW on non-Throwable");
1982                                 if (r == typecheck_FAIL)
1983                                         return false;
1984                                 if (r == typecheck_MAYBE) {
1985                                         /* the check has to be postponed. we need a patcher */
1986                                         TYPECHECK_COUNT(stat_ins_athrow_unresolved);
1987                                         iptr->sx.s23.s2.uc = create_unresolved_class(
1988                                                         state->m,
1989                                                         /* XXX make this more efficient, use class_java_lang_Throwable
1990                                                          * directly */
1991                                                         class_get_classref(state->m->class,utf_java_lang_Throwable),
1992                                                         &VAROP(state->iptr->s1)->typeinfo);
1993                                         iptr->flags.bits |= INS_FLAG_UNRESOLVED;
1994                                 }
1995                                 superblockend = true;
1996                                 maythrow = true;
1997                                 break;
1998
1999                         case ICMD_ARETURN:
2000                                 TYPECHECK_COUNT(stat_ins_areturn);
2001                                 if (!TYPEINFO_IS_REFERENCE(VAROP(state->iptr->s1)->typeinfo))
2002                                         TYPECHECK_VERIFYERROR_bool("illegal instruction: ARETURN on non-reference");
2003
2004                                 if (state->returntype.type != TYPE_ADR
2005                                                 || (r = typeinfo_is_assignable(&VAROP(state->iptr->s1)->typeinfo,&(state->returntype.typeinfo)))
2006                                                                 == typecheck_FALSE)
2007                                         TYPECHECK_VERIFYERROR_bool("Return type mismatch");
2008                                 if (r == typecheck_FAIL)
2009                                         return false;
2010                                 if (r == typecheck_MAYBE) {
2011                                         /* the check has to be postponed, we need a patcher */
2012                                         TYPECHECK_COUNT(stat_ins_areturn_unresolved);
2013                                         iptr->sx.s23.s2.uc = create_unresolved_class(
2014                                                         state->m,
2015                                                         state->m->parseddesc->returntype.classref,
2016                                                         &VAROP(state->iptr->s1)->typeinfo);
2017                                         iptr->flags.bits |= INS_FLAG_UNRESOLVED;
2018                                 }
2019                                 goto return_tail;
2020
2021                                 /****************************************/
2022                                 /* PRIMITIVE RETURNS                    */
2023
2024                         case ICMD_IRETURN:
2025                                 if (state->returntype.type != TYPE_INT) TYPECHECK_VERIFYERROR_bool("Return type mismatch");
2026                                 goto return_tail;
2027
2028                         case ICMD_LRETURN:
2029                                 if (state->returntype.type != TYPE_LNG) TYPECHECK_VERIFYERROR_bool("Return type mismatch");
2030                                 goto return_tail;
2031
2032                         case ICMD_FRETURN:
2033                                 if (state->returntype.type != TYPE_FLT) TYPECHECK_VERIFYERROR_bool("Return type mismatch");
2034                                 goto return_tail;
2035
2036                         case ICMD_DRETURN:
2037                                 if (state->returntype.type != TYPE_DBL) TYPECHECK_VERIFYERROR_bool("Return type mismatch");
2038                                 goto return_tail;
2039
2040                         case ICMD_RETURN:
2041                                 if (state->returntype.type != TYPE_VOID) TYPECHECK_VERIFYERROR_bool("Return type mismatch");
2042 return_tail:
2043                                 TYPECHECK_COUNT(stat_ins_primitive_return);
2044
2045                                 if (state->initmethod && state->m->class != class_java_lang_Object) {
2046                                         /* Check if the 'this' instance has been initialized. */
2047                                         LOG("Checking <init> marker");
2048                                         if (!typevector_checktype(jd->var,state->numlocals-1,TYPE_INT))
2049                                                 TYPECHECK_VERIFYERROR_bool("<init> method does not initialize 'this'");
2050                                 }
2051
2052                                 superblockend = true;
2053                                 maythrow = true;
2054                                 break;
2055
2056                                 /****************************************/
2057                                 /* SUBROUTINE INSTRUCTIONS              */
2058
2059                         case ICMD_JSR:
2060                                 LOG("jsr");
2061
2062                                 tbptr = state->iptr->sx.s23.s3.jsrtarget.block;
2063                                 TYPEINFO_INIT_RETURNADDRESS(dv->typeinfo, state->bptr->next);
2064                                 if (!typestate_reach(state, tbptr, state->bptr->outvars, jd->var,
2065                                                         state->bptr->outdepth))
2066                                         return false;
2067
2068                                 superblockend = true;
2069                                 break;
2070
2071                         case ICMD_RET:
2072                                 /* check returnAddress variable */
2073                                 if (!typevector_checkretaddr(jd->var,state->iptr->s1.varindex))
2074                                         TYPECHECK_VERIFYERROR_bool("illegal instruction: RET using non-returnAddress variable");
2075
2076                                 if (!typestate_reach(state, iptr->dst.block, state->bptr->outvars, jd->var,
2077                                                         state->bptr->outdepth))
2078                                         return false;
2079
2080                                 superblockend = true;
2081                                 break;
2082
2083                                 /****************************************/
2084                                 /* INVOKATIONS                          */
2085
2086                         case ICMD_INVOKEVIRTUAL:
2087                         case ICMD_INVOKESPECIAL:
2088                         case ICMD_INVOKESTATIC:
2089                         case ICMD_INVOKEINTERFACE:
2090                                 TYPECHECK_COUNT(stat_ins_invoke);
2091                                 if (!verify_invocation(state))
2092                                         return false;
2093                                 TYPECHECK_COUNTIF(INSTRUCTION_IS_UNRESOLVED(iptr), stat_ins_invoke_unresolved);
2094                                 maythrow = true;
2095                                 break;
2096
2097                                 /****************************************/
2098                                 /* MULTIANEWARRAY                       */
2099
2100                         case ICMD_MULTIANEWARRAY:
2101                                 if (!verify_multianewarray(state))
2102                                         return false;
2103                                 maythrow = true;
2104                                 break;
2105
2106                                 /****************************************/
2107                                 /* BUILTINS                             */
2108
2109                         case ICMD_BUILTIN:
2110                                 TYPECHECK_COUNT(stat_ins_builtin);
2111                                 if (!verify_builtin(state))
2112                                         return false;
2113                                 maythrow = true;
2114                                 break;
2115
2116                                 /****************************************/
2117                                 /* SIMPLE EXCEPTION THROWING TESTS      */
2118
2119                         case ICMD_CHECKNULL:
2120                                 /* CHECKNULL just requires that the stack top
2121                                  * is an address. This is checked in stack.c */
2122                                 maythrow = true;
2123                                 break;
2124
2125                                 /****************************************/
2126                                 /* INSTRUCTIONS WHICH SHOULD HAVE BEEN  */
2127                                 /* REPLACED BY OTHER OPCODES            */
2128
2129 #ifdef TYPECHECK_DEBUG
2130                         case ICMD_NEW:
2131                         case ICMD_NEWARRAY:
2132                         case ICMD_ANEWARRAY:
2133                         case ICMD_MONITORENTER:
2134                         case ICMD_MONITOREXIT:
2135                                 LOG2("ICMD %d at %d\n", state->iptr->opc, (int)(state->iptr-state->bptr->iinstr));
2136                                 LOG("Should have been converted to builtin function call.");
2137                                 TYPECHECK_ASSERT(false);
2138                                 break;
2139 #endif
2140
2141                                 /****************************************/
2142                                 /* UNCHECKED OPERATIONS                 */
2143
2144                                 /*********************************************
2145                                  * Instructions below...
2146                                  *     *) don't operate on local variables,
2147                                  *     *) don't operate on references,
2148                                  *     *) don't operate on returnAddresses,
2149                                  *     *) don't affect control flow (except
2150                                  *        by throwing exceptions).
2151                                  *
2152                                  * (These instructions are typechecked in
2153                                  *  analyse_stack.)
2154                                  ********************************************/
2155
2156                                 /* Instructions which may throw a runtime exception: */
2157
2158                         case ICMD_IDIV:
2159                         case ICMD_IREM:
2160                                 dv->type = TYPE_INT;
2161                                 maythrow = true;
2162                                 break;
2163
2164                         case ICMD_LDIV:
2165                         case ICMD_LREM:
2166                                 dv->type = TYPE_LNG;
2167                                 maythrow = true;
2168                                 break;
2169
2170                                 /* Instructions which never throw a runtime exception: */
2171                         case ICMD_NOP:
2172                         case ICMD_POP:
2173                         case ICMD_POP2:
2174                                 break;
2175
2176                         case ICMD_ICONST:
2177                         case ICMD_IADD:
2178                         case ICMD_ISUB:
2179                         case ICMD_IMUL:
2180                         case ICMD_INEG:
2181                         case ICMD_IAND:
2182                         case ICMD_IOR:
2183                         case ICMD_IXOR:
2184                         case ICMD_ISHL:
2185                         case ICMD_ISHR:
2186                         case ICMD_IUSHR:
2187                         case ICMD_IMULPOW2:
2188                         case ICMD_IDIVPOW2:
2189                         case ICMD_IADDCONST:
2190                         case ICMD_ISUBCONST:
2191                         case ICMD_IMULCONST:
2192                         case ICMD_IANDCONST:
2193                         case ICMD_IORCONST:
2194                         case ICMD_IXORCONST:
2195                         case ICMD_ISHLCONST:
2196                         case ICMD_ISHRCONST:
2197                         case ICMD_IUSHRCONST:
2198                         case ICMD_IREMPOW2:
2199                         case ICMD_INT2BYTE:
2200                         case ICMD_INT2CHAR:
2201                         case ICMD_INT2SHORT:
2202                         case ICMD_L2I:
2203                         case ICMD_F2I:
2204                         case ICMD_D2I:
2205                         case ICMD_LCMP:
2206                         case ICMD_LCMPCONST:
2207                         case ICMD_FCMPL:
2208                         case ICMD_FCMPG:
2209                         case ICMD_DCMPL:
2210                         case ICMD_DCMPG:
2211                                 dv->type = TYPE_INT;
2212                                 break;
2213
2214                         case ICMD_LCONST:
2215                         case ICMD_LADD:
2216                         case ICMD_LSUB:
2217                         case ICMD_LMUL:
2218                         case ICMD_LNEG:
2219                         case ICMD_LAND:
2220                         case ICMD_LOR:
2221                         case ICMD_LXOR:
2222                         case ICMD_LSHL:
2223                         case ICMD_LSHR:
2224                         case ICMD_LUSHR:
2225                         case ICMD_LMULPOW2:
2226                         case ICMD_LDIVPOW2:
2227                         case ICMD_LADDCONST:
2228                         case ICMD_LSUBCONST:
2229                         case ICMD_LMULCONST:
2230                         case ICMD_LANDCONST:
2231                         case ICMD_LORCONST:
2232                         case ICMD_LXORCONST:
2233                         case ICMD_LSHLCONST:
2234                         case ICMD_LSHRCONST:
2235                         case ICMD_LUSHRCONST:
2236                         case ICMD_LREMPOW2:
2237                         case ICMD_I2L:
2238                         case ICMD_F2L:
2239                         case ICMD_D2L:
2240                                 dv->type = TYPE_LNG;
2241                                 break;
2242
2243                         case ICMD_FCONST:
2244                         case ICMD_I2F:
2245                         case ICMD_L2F:
2246                         case ICMD_D2F:
2247                         case ICMD_FADD:
2248                         case ICMD_FSUB:
2249                         case ICMD_FMUL:
2250                         case ICMD_FDIV:
2251                         case ICMD_FREM:
2252                         case ICMD_FNEG:
2253                                 dv->type = TYPE_FLT;
2254                                 break;
2255
2256                         case ICMD_DCONST:
2257                         case ICMD_I2D:
2258                         case ICMD_L2D:
2259                         case ICMD_F2D:
2260                         case ICMD_DADD:
2261                         case ICMD_DSUB:
2262                         case ICMD_DMUL:
2263                         case ICMD_DDIV:
2264                         case ICMD_DREM:
2265                         case ICMD_DNEG:
2266                                 dv->type = TYPE_DBL;
2267                                 break;
2268
2269                         case ICMD_INLINE_START:
2270                         case ICMD_INLINE_END:
2271                                 break;
2272
2273                                 /* XXX What shall we do with the following ?*/
2274                         case ICMD_AASTORECONST:
2275                                 TYPECHECK_COUNT(stat_ins_unchecked);
2276                                 break;
2277
2278                                 /****************************************/
2279
2280                         default:
2281                                 LOG2("ICMD %d at %d\n", state->iptr->opc, (int)(state->iptr-state->bptr->iinstr));
2282                                 TYPECHECK_VERIFYERROR_bool("Missing ICMD code during typecheck");
2283                 }
2284
2285                 /* reach exception handlers for this instruction */
2286
2287                 if (maythrow) {
2288                         TYPECHECK_COUNT(stat_ins_maythrow);
2289                         TYPECHECK_MARK(state->stat_maythrow);
2290                         LOG("reaching exception handlers");
2291                         i = 0;
2292                         while (state->handlers[i]) {
2293                                 TYPECHECK_COUNT(stat_handlers_reached);
2294                                 if (state->handlers[i]->catchtype.any)
2295                                         VAR(state->exinvars)->typeinfo.typeclass = state->handlers[i]->catchtype;
2296                                 else
2297                                         VAR(state->exinvars)->typeinfo.typeclass.cls = class_java_lang_Throwable;
2298                                 if (!typestate_reach(state,
2299                                                 state->handlers[i]->handler,
2300                                                 &(state->exinvars), jd->var, 1))
2301                                         return false;
2302                                 i++;
2303                         }
2304                 }
2305
2306                 LOG("\t\tnext instruction");
2307                 state->iptr++;
2308         } /* while instructions */
2309
2310         LOG("instructions done");
2311         LOGSTR("RESULT=> ");
2312         DOLOG(typecheck_print_vararray(stdout, jd, state->bptr->outvars,
2313                                 state->bptr->outdepth));
2314         DOLOG(typevector_print(stdout, jd->var, state->numlocals));
2315         LOGNL; LOGFLUSH;
2316
2317         /* propagate stack and variables to the following block */
2318         if (!superblockend) {
2319                 LOG("reaching following block");
2320                 tbptr = state->bptr->next;
2321                 while (tbptr->flags == BBDELETED) {
2322                         tbptr = tbptr->next;
2323 #ifdef TYPECHECK_DEBUG
2324                         /* this must be checked in parse.c */
2325                         if ((tbptr->nr) >= state->basicblockcount)
2326                                 TYPECHECK_VERIFYERROR_bool("Control flow falls off the last block");
2327 #endif
2328                 }
2329                 if (!typestate_reach(state,tbptr,state->bptr->outvars, jd->var,
2330                                         state->bptr->outdepth))
2331                         return false;
2332         }
2333
2334         /* We may have to restore the types of the instack slots. They
2335          * have been saved if an <init> call inside the block has
2336          * modified the instack types. (see INVOKESPECIAL) */
2337
2338         if (state->savedinvars)
2339                 typestate_restore_invars(state);
2340
2341         return true;
2342 }
2343
2344
2345 /* verify_init_locals **********************************************************
2346
2347    Initialize the local variables in the verifier state.
2348
2349    IN:
2350        state............the current state of the verifier
2351
2352    RETURN VALUE:
2353        true.............success,
2354            false............an exception has been thrown.
2355
2356 *******************************************************************************/
2357
2358 static bool
2359 verify_init_locals(verifier_state *state)
2360 {
2361         int i;
2362         int index;
2363         varinfo *locals;
2364         varinfo *v;
2365         jitdata *jd = state->jd;
2366         int skip = 0;
2367
2368         locals = state->basicblocks[0].inlocals;
2369
2370         /* allocate parameter descriptors if necessary */
2371
2372         if (!state->m->parseddesc->params)
2373                 if (!descriptor_params_from_paramtypes(state->m->parseddesc,state->m->flags))
2374                         return false;
2375
2376         /* pre-initialize variables as TYPE_VOID */
2377
2378         i = state->numlocals;
2379         v = locals;
2380         while (i--) {
2381                 v->type = TYPE_VOID;
2382                 v++;
2383         }
2384
2385     /* if this is an instance method initialize the "this" ref type */
2386
2387     if (!(state->m->flags & ACC_STATIC)) {
2388                 index = jd->local_map[5*0 + TYPE_ADR];
2389                 if (index != UNUSED) {
2390                         if (state->validlocals < 1)
2391                                 TYPECHECK_VERIFYERROR_bool("Not enough local variables for method arguments");
2392                         v = locals + index;
2393                         v->type = TYPE_ADR;
2394                         if (state->initmethod)
2395                                 TYPEINFO_INIT_NEWOBJECT(v->typeinfo, NULL);
2396                         else
2397                                 typeinfo_init_classinfo(&(v->typeinfo), state->m->class);
2398                 }
2399
2400                 skip = 1;
2401     }
2402
2403     LOG("'this' argument set.\n");
2404
2405     /* the rest of the arguments and the return type */
2406
2407     if (!typeinfo_init_varinfos_from_methoddesc(locals, state->m->parseddesc,
2408                                                                                           state->validlocals,
2409                                                                                           skip, /* skip 'this' pointer */
2410                                                                                           jd->local_map,
2411                                                                                           &state->returntype))
2412                 return false;
2413
2414     LOG("Arguments set.\n");
2415         return true;
2416 }
2417
2418
2419 /* typecheck_init_flags ********************************************************
2420
2421    Initialize the basic block flags for the following CFG traversal.
2422
2423    IN:
2424        state............the current state of the verifier
2425
2426 *******************************************************************************/
2427
2428 static void
2429 typecheck_init_flags(verifier_state *state)
2430 {
2431         s4 i;
2432         basicblock *block;
2433
2434     /* set all BBFINISHED blocks to BBTYPECHECK_UNDEF. */
2435
2436     i = state->basicblockcount;
2437     for (block = state->basicblocks; block; block = block->next) {
2438
2439 #ifdef TYPECHECK_DEBUG
2440                 /* check for invalid flags */
2441         if (block->flags != BBFINISHED && block->flags != BBDELETED && block->flags != BBUNDEF)
2442         {
2443             LOGSTR1("block flags: %d\n",block->flags); LOGFLUSH;
2444                         TYPECHECK_ASSERT(false);
2445         }
2446 #endif
2447
2448         if (block->flags >= BBFINISHED) {
2449             block->flags = BBTYPECHECK_UNDEF;
2450         }
2451     }
2452
2453     /* the first block is always reached */
2454
2455     if (state->basicblockcount && state->basicblocks[0].flags == BBTYPECHECK_UNDEF)
2456         state->basicblocks[0].flags = BBTYPECHECK_REACHED;
2457 }
2458
2459
2460 /* typecheck_reset_flags *******************************************************
2461
2462    Reset the flags of basic blocks we have not reached.
2463
2464    IN:
2465        state............the current state of the verifier
2466
2467 *******************************************************************************/
2468
2469 static void
2470 typecheck_reset_flags(verifier_state *state)
2471 {
2472         basicblock *block;
2473
2474         /* check for invalid flags at exit */
2475
2476 #ifdef TYPECHECK_DEBUG
2477         for (block = state->basicblocks; block; block = block->next) {
2478                 if (block->flags != BBDELETED
2479                         && block->flags != BBUNDEF
2480                         && block->flags != BBFINISHED
2481                         && block->flags != BBTYPECHECK_UNDEF) /* typecheck may never reach
2482                                                                                                          * some exception handlers,
2483                                                                                                          * that's ok. */
2484                 {
2485                         LOG2("block L%03d has invalid flags after typecheck: %d",
2486                                  block->nr,block->flags);
2487                         TYPECHECK_ASSERT(false);
2488                 }
2489         }
2490 #endif
2491
2492         /* Delete blocks we never reached */
2493
2494         for (block = state->basicblocks; block; block = block->next) {
2495                 if (block->flags == BBTYPECHECK_UNDEF)
2496                         block->flags = BBDELETED;
2497         }
2498 }
2499
2500
2501 /****************************************************************************/
2502 /* typecheck()                                                              */
2503 /* This is the main function of the bytecode verifier. It is called         */
2504 /* directly after analyse_stack.                                            */
2505 /*                                                                          */
2506 /* IN:                                                                      */
2507 /*    meth.............the method to verify                                 */
2508 /*    cdata............codegendata for the method                           */
2509 /*    rdata............registerdata for the method                          */
2510 /*                                                                          */
2511 /* RETURN VALUE:                                                            */
2512 /*     true.............successful verification                             */
2513 /*     false............an exception has been thrown                        */
2514 /*                                                                          */
2515 /****************************************************************************/
2516
2517 #define MAXPARAMS 255
2518
2519 bool typecheck(jitdata *jd)
2520 {
2521         methodinfo     *meth;
2522         codegendata    *cd;
2523         varinfo        *savedlocals;
2524         verifier_state  state;             /* current state of the verifier */
2525         s4              i;
2526         s4              t;
2527
2528         /* collect statistics */
2529
2530 #ifdef TYPECHECK_STATISTICS
2531         int count_iterations = 0;
2532         TYPECHECK_COUNT(stat_typechecked);
2533         TYPECHECK_COUNT_FREQ(stat_locals,cdata->maxlocals,STAT_LOCALS);
2534         TYPECHECK_COUNT_FREQ(stat_blocks,cdata->method->basicblockcount/10,STAT_BLOCKS);
2535         TYPECHECK_COUNTIF(cdata->method->exceptiontablelength != 0,stat_methods_with_handlers);
2536         state.stat_maythrow = false;
2537 #endif
2538
2539         /* get required compiler data */
2540
2541         meth = jd->m;
2542         cd   = jd->cd;
2543
2544         /* some logging on entry */
2545
2546
2547     LOGSTR("\n==============================================================================\n");
2548     DOLOG( show_method(jd, SHOW_STACK) );
2549     LOGSTR("\n==============================================================================\n");
2550     LOGMETHOD("Entering typecheck: ",cd->method);
2551
2552         /* initialize the verifier state */
2553
2554         state.m = meth;
2555         state.jd = jd;
2556         state.cd = cd;
2557         state.basicblockcount = jd->basicblockcount;
2558         state.basicblocks = jd->basicblocks;
2559         state.savedindices = NULL;
2560         state.savedinvars = NULL;
2561
2562         /* check if this method is an instance initializer method */
2563
2564     state.initmethod = (state.m->name == utf_init);
2565
2566         /* initialize the basic block flags for the following CFG traversal */
2567
2568         typecheck_init_flags(&state);
2569
2570     /* number of local variables */
2571
2572     /* In <init> methods we use an extra local variable to indicate whether */
2573     /* the 'this' reference has been initialized.                           */
2574         /*         TYPE_VOID...means 'this' has not been initialized,           */
2575         /*         TYPE_INT....means 'this' has been initialized.               */
2576
2577     state.numlocals = state.jd->localcount;
2578         state.validlocals = state.numlocals;
2579     if (state.initmethod)
2580                 state.numlocals++; /* VERIFIER_EXTRA_LOCALS */
2581
2582         state.reverselocalmap = DMNEW(s4, state.validlocals);
2583         for (i=0; i<jd->m->maxlocals; ++i)
2584                 for (t=0; t<5; ++t) {
2585                         s4 mapped = jd->local_map[5*i + t];
2586                         if (mapped >= 0)
2587                                 state.reverselocalmap[mapped] = i;
2588                 }
2589
2590         DOLOG(
2591                 LOG("reverselocalmap:");
2592                 for (i=0; i<state.validlocals; ++i) {
2593                         LOG2("    %i => javaindex %i", i, state.reverselocalmap[i]);
2594                 });
2595
2596     /* allocate the buffer of active exception handlers */
2597
2598     state.handlers = DMNEW(exceptiontable*, state.cd->exceptiontablelength + 1);
2599
2600         /* save local variables */
2601
2602         savedlocals = DMNEW(varinfo, state.numlocals);
2603         MCOPY(savedlocals, jd->var, varinfo, state.numlocals);
2604
2605         /* initialized local variables of first block */
2606
2607         if (!verify_init_locals(&state))
2608                 return false;
2609
2610     /* initialize invars of exception handlers */
2611
2612         state.exinvars = state.numlocals;
2613         VAR(state.exinvars)->type = TYPE_ADR;
2614         typeinfo_init_classinfo(&(VAR(state.exinvars)->typeinfo),
2615                                                         class_java_lang_Throwable); /* changed later */
2616
2617     LOG("Exception handler stacks set.\n");
2618
2619     /* loop while there are still blocks to be checked */
2620     do {
2621                 TYPECHECK_COUNT(count_iterations);
2622
2623         state.repeat = false;
2624
2625         state.bptr = state.basicblocks;
2626
2627         for (; state.bptr; state.bptr = state.bptr->next) {
2628             LOGSTR1("---- BLOCK %04d, ",state.bptr->nr);
2629             LOGSTR1("blockflags: %d\n",state.bptr->flags);
2630             LOGFLUSH;
2631
2632                     /* verify reached block */
2633             if (state.bptr->flags == BBTYPECHECK_REACHED) {
2634                 if (!verify_basic_block(&state))
2635                                         return false;
2636             }
2637         } /* for blocks */
2638
2639         LOGIF(state.repeat,"state.repeat == true");
2640     } while (state.repeat);
2641
2642         /* statistics */
2643
2644 #ifdef TYPECHECK_STATISTICS
2645         LOG1("Typechecker did %4d iterations",count_iterations);
2646         TYPECHECK_COUNT_FREQ(stat_iterations,count_iterations,STAT_ITERATIONS);
2647         TYPECHECK_COUNTIF(state.jsrencountered,stat_typechecked_jsr);
2648         TYPECHECK_COUNTIF(state.stat_maythrow,stat_methods_maythrow);
2649 #endif
2650
2651         /* reset the flags of blocks we haven't reached */
2652
2653         typecheck_reset_flags(&state);
2654
2655         /* restore locals */
2656
2657         MCOPY(jd->var, savedlocals, varinfo, state.numlocals);
2658
2659         /* everything's ok */
2660
2661     LOGimp("exiting typecheck");
2662         return true;
2663 }
2664 #endif /* ENABLE_VERIFIER */
2665
2666 /*
2667  * These are local overrides for various environment variables in Emacs.
2668  * Please do not remove this and leave it at the end of the file, where
2669  * Emacs will automagically detect them.
2670  * ---------------------------------------------------------------------
2671  * Local variables:
2672  * mode: c
2673  * indent-tabs-mode: t
2674  * c-basic-offset: 4
2675  * tab-width: 4
2676  * End:
2677  * vim:noexpandtab:sw=4:ts=4:
2678  */