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