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