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 5508 2006-09-15 11:02:50Z 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->nr <= state->bptr->nr) && (ex->end->nr > state->bptr->nr)) {
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                         case ICMD_GETFIELD:
1535                         case ICMD_GETSTATIC:
1536                                 TYPECHECK_COUNT(stat_ins_field);
1537
1538                                 if (INSTRUCTION_IS_UNRESOLVED(state->iptr)) {
1539                                         uf = state->iptr->sx.s23.s3.uf;
1540                                         fieldref = uf->fieldref;
1541                                 }
1542                                 else {
1543                                         uf = NULL;
1544                                         fieldref = state->iptr->sx.s23.s3.fmiref;
1545                                 }
1546
1547                                 /* try to resolve the field reference lazily */
1548                                 result = new_resolve_field_lazy(jd, state->iptr, state->m);
1549                                 if (result == resolveFailed)
1550                                         return false;
1551
1552                                 if (result != resolveSucceeded) {
1553                                         if (!uf) {
1554                                                 uf = new_create_unresolved_field(state->m->class, state->m, state->iptr);
1555                                                 if (!uf)
1556                                                         return false;
1557
1558                                                 state->iptr->sx.s23.s3.uf = uf;
1559                                                 state->iptr->flags.bits |= INS_FLAG_UNRESOLVED;
1560                                         }
1561
1562                                         /* record the subtype constraints for this field access */
1563                                         if (!new_constrain_unresolved_field(jd, uf,state->m->class,state->m,state->iptr))
1564                                                 return false; /* XXX maybe wrap exception? */
1565
1566                                         TYPECHECK_COUNTIF(INSTRUCTION_IS_UNRESOLVED(state->iptr),stat_ins_field_unresolved);
1567                                         TYPECHECK_COUNTIF(INSTRUCTION_IS_RESOLVED(state->iptr) && !state->iptr->sx.s23.s3.fmiref->p.field->class->initialized,stat_ins_field_uninitialized);
1568                                 }
1569
1570                                 if (iptr->opc == ICMD_GETFIELD || iptr->opc == ICMD_GETSTATIC) {
1571                                         /* write the result type */
1572                                         dv->type = fieldref->parseddesc.fd->type;
1573                                         if (dv->type == TYPE_ADR) {
1574                                                 if (!typeinfo_init_from_typedesc(fieldref->parseddesc.fd,NULL,&(dv->typeinfo)))
1575                                                         return false;
1576                                         }
1577                                 }
1578
1579                                 maythrow = true;
1580                                 break;
1581
1582                                 /****************************************/
1583                                 /* PRIMITIVE ARRAY ACCESS               */
1584
1585                         case ICMD_ARRAYLENGTH:
1586                                 if (!TYPEINFO_MAYBE_ARRAY(VAROP(state->iptr->s1)->typeinfo)
1587                                                 && VAROP(state->iptr->s1)->typeinfo.typeclass.cls != pseudo_class_Arraystub)
1588                                         TYPECHECK_VERIFYERROR_bool("illegal instruction: ARRAYLENGTH on non-array");
1589                                 dv->type = TYPE_INT;
1590                                 maythrow = true;
1591                                 break;
1592
1593                         case ICMD_BALOAD:
1594                                 if (!TYPEINFO_MAYBE_PRIMITIVE_ARRAY(VAROP(state->iptr->s1)->typeinfo,ARRAYTYPE_BOOLEAN)
1595                                                 && !TYPEINFO_MAYBE_PRIMITIVE_ARRAY(VAROP(state->iptr->s1)->typeinfo,ARRAYTYPE_BYTE))
1596                                         TYPECHECK_VERIFYERROR_bool("Array type mismatch");
1597                                 dv->type = TYPE_INT;
1598                                 maythrow = true;
1599                                 break;
1600                         case ICMD_CALOAD:
1601                                 if (!TYPEINFO_MAYBE_PRIMITIVE_ARRAY(VAROP(state->iptr->s1)->typeinfo,ARRAYTYPE_CHAR))
1602                                         TYPECHECK_VERIFYERROR_bool("Array type mismatch");
1603                                 dv->type = TYPE_INT;
1604                                 maythrow = true;
1605                                 break;
1606                         case ICMD_DALOAD:
1607                                 if (!TYPEINFO_MAYBE_PRIMITIVE_ARRAY(VAROP(state->iptr->s1)->typeinfo,ARRAYTYPE_DOUBLE))
1608                                         TYPECHECK_VERIFYERROR_bool("Array type mismatch");
1609                                 dv->type = TYPE_DBL;
1610                                 maythrow = true;
1611                                 break;
1612                         case ICMD_FALOAD:
1613                                 if (!TYPEINFO_MAYBE_PRIMITIVE_ARRAY(VAROP(state->iptr->s1)->typeinfo,ARRAYTYPE_FLOAT))
1614                                         TYPECHECK_VERIFYERROR_bool("Array type mismatch");
1615                                 dv->type = TYPE_FLT;
1616                                 maythrow = true;
1617                                 break;
1618                         case ICMD_IALOAD:
1619                                 if (!TYPEINFO_MAYBE_PRIMITIVE_ARRAY(VAROP(state->iptr->s1)->typeinfo,ARRAYTYPE_INT))
1620                                         TYPECHECK_VERIFYERROR_bool("Array type mismatch");
1621                                 dv->type = TYPE_INT;
1622                                 maythrow = true;
1623                                 break;
1624                         case ICMD_SALOAD:
1625                                 if (!TYPEINFO_MAYBE_PRIMITIVE_ARRAY(VAROP(state->iptr->s1)->typeinfo,ARRAYTYPE_SHORT))
1626                                         TYPECHECK_VERIFYERROR_bool("Array type mismatch");
1627                                 dv->type = TYPE_INT;
1628                                 maythrow = true;
1629                                 break;
1630                         case ICMD_LALOAD:
1631                                 if (!TYPEINFO_MAYBE_PRIMITIVE_ARRAY(VAROP(state->iptr->s1)->typeinfo,ARRAYTYPE_LONG))
1632                                         TYPECHECK_VERIFYERROR_bool("Array type mismatch");
1633                                 dv->type = TYPE_LNG;
1634                                 maythrow = true;
1635                                 break;
1636
1637                         case ICMD_BASTORE:
1638                                 if (!TYPEINFO_MAYBE_PRIMITIVE_ARRAY(VAROP(state->iptr->s1)->typeinfo,ARRAYTYPE_BOOLEAN)
1639                                                 && !TYPEINFO_MAYBE_PRIMITIVE_ARRAY(VAROP(state->iptr->s1)->typeinfo,ARRAYTYPE_BYTE))
1640                                         TYPECHECK_VERIFYERROR_bool("Array type mismatch");
1641                                 maythrow = true;
1642                                 break;
1643                         case ICMD_CASTORE:
1644                                 if (!TYPEINFO_MAYBE_PRIMITIVE_ARRAY(VAROP(state->iptr->s1)->typeinfo,ARRAYTYPE_CHAR))
1645                                         TYPECHECK_VERIFYERROR_bool("Array type mismatch");
1646                                 maythrow = true;
1647                                 break;
1648                         case ICMD_DASTORE:
1649                                 if (!TYPEINFO_MAYBE_PRIMITIVE_ARRAY(VAROP(state->iptr->s1)->typeinfo,ARRAYTYPE_DOUBLE))
1650                                         TYPECHECK_VERIFYERROR_bool("Array type mismatch");
1651                                 maythrow = true;
1652                                 break;
1653                         case ICMD_FASTORE:
1654                                 if (!TYPEINFO_MAYBE_PRIMITIVE_ARRAY(VAROP(state->iptr->s1)->typeinfo,ARRAYTYPE_FLOAT))
1655                                         TYPECHECK_VERIFYERROR_bool("Array type mismatch");
1656                                 maythrow = true;
1657                                 break;
1658                         case ICMD_IASTORE:
1659                                 if (!TYPEINFO_MAYBE_PRIMITIVE_ARRAY(VAROP(state->iptr->s1)->typeinfo,ARRAYTYPE_INT))
1660                                         TYPECHECK_VERIFYERROR_bool("Array type mismatch");
1661                                 maythrow = true;
1662                                 break;
1663                         case ICMD_SASTORE:
1664                                 if (!TYPEINFO_MAYBE_PRIMITIVE_ARRAY(VAROP(state->iptr->s1)->typeinfo,ARRAYTYPE_SHORT))
1665                                         TYPECHECK_VERIFYERROR_bool("Array type mismatch");
1666                                 maythrow = true;
1667                                 break;
1668                         case ICMD_LASTORE:
1669                                 if (!TYPEINFO_MAYBE_PRIMITIVE_ARRAY(VAROP(state->iptr->s1)->typeinfo,ARRAYTYPE_LONG))
1670                                         TYPECHECK_VERIFYERROR_bool("Array type mismatch");
1671                                 maythrow = true;
1672                                 break;
1673
1674                         case ICMD_AASTORE:
1675                                 /* we just check the basic input types and that the           */
1676                                 /* destination is an array of references. Assignability to    */
1677                                 /* the actual array must be checked at runtime, each time the */
1678                                 /* instruction is performed. (See builtin_canstore.)          */
1679                                 TYPECHECK_ADR_OP(state->iptr->sx.s23.s3);
1680                                 TYPECHECK_INT_OP(state->iptr->sx.s23.s2);
1681                                 TYPECHECK_ADR_OP(state->iptr->s1);
1682                                 if (!TYPEINFO_MAYBE_ARRAY_OF_REFS(VAROP(state->iptr->s1)->typeinfo))
1683                                         TYPECHECK_VERIFYERROR_bool("illegal instruction: AASTORE to non-reference array");
1684                                 maythrow = true;
1685                                 break;
1686
1687                         case ICMD_IASTORECONST:
1688                                 if (!TYPEINFO_MAYBE_PRIMITIVE_ARRAY(VAROP(state->iptr->s1)->typeinfo, ARRAYTYPE_INT))
1689                                         TYPECHECK_VERIFYERROR_bool("Array type mismatch");
1690                                 maythrow = true;
1691                                 break;
1692
1693                         case ICMD_LASTORECONST:
1694                                 if (!TYPEINFO_MAYBE_PRIMITIVE_ARRAY(VAROP(state->iptr->s1)->typeinfo, ARRAYTYPE_LONG))
1695                                         TYPECHECK_VERIFYERROR_bool("Array type mismatch");
1696                                 maythrow = true;
1697                                 break;
1698
1699                         case ICMD_BASTORECONST:
1700                                 if (!TYPEINFO_MAYBE_PRIMITIVE_ARRAY(VAROP(state->iptr->s1)->typeinfo, ARRAYTYPE_BOOLEAN)
1701                                                 && !TYPEINFO_MAYBE_PRIMITIVE_ARRAY(VAROP(state->iptr->s1)->typeinfo, ARRAYTYPE_BYTE))
1702                                         TYPECHECK_VERIFYERROR_bool("Array type mismatch");
1703                                 maythrow = true;
1704                                 break;
1705
1706                         case ICMD_CASTORECONST:
1707                                 if (!TYPEINFO_MAYBE_PRIMITIVE_ARRAY(VAROP(state->iptr->s1)->typeinfo, ARRAYTYPE_CHAR))
1708                                         TYPECHECK_VERIFYERROR_bool("Array type mismatch");
1709                                 maythrow = true;
1710                                 break;
1711
1712                         case ICMD_SASTORECONST:
1713                                 if (!TYPEINFO_MAYBE_PRIMITIVE_ARRAY(VAROP(state->iptr->s1)->typeinfo, ARRAYTYPE_SHORT))
1714                                         TYPECHECK_VERIFYERROR_bool("Array type mismatch");
1715                                 maythrow = true;
1716                                 break;
1717
1718                                 /****************************************/
1719                                 /* ADDRESS CONSTANTS                    */
1720
1721                         case ICMD_ACONST:
1722                                 if (state->iptr->flags.bits & INS_FLAG_CLASS) {
1723                                         /* a java.lang.Class reference */
1724                                         TYPEINFO_INIT_JAVA_LANG_CLASS(dv->typeinfo,state->iptr->sx.val.c);
1725                                 }
1726                                 else {
1727                                         if (state->iptr->sx.val.anyptr == NULL)
1728                                                 TYPEINFO_INIT_NULLTYPE(dv->typeinfo);
1729                                         else {
1730                                                 /* string constant (or constant for builtin function) */
1731                                                 typeinfo_init_classinfo(&(dv->typeinfo),class_java_lang_String);
1732                                         }
1733                                 }
1734                                 dv->type = TYPE_ADR;
1735                                 break;
1736
1737                                 /****************************************/
1738                                 /* CHECKCAST AND INSTANCEOF             */
1739
1740                         case ICMD_CHECKCAST:
1741                                 TYPECHECK_ADR_OP(state->iptr->s1);
1742                                 /* returnAddress is not allowed */
1743                                 if (!TYPEINFO_IS_REFERENCE(VAROP(state->iptr->s1)->typeinfo))
1744                                         TYPECHECK_VERIFYERROR_bool("Illegal instruction: CHECKCAST on non-reference");
1745
1746                                 if (!typeinfo_init_class(&(dv->typeinfo),state->iptr->sx.s23.s3.c))
1747                                                 return false;
1748                                 dv->type = TYPE_ADR;
1749                                 maythrow = true;
1750                                 break;
1751
1752                         case ICMD_INSTANCEOF:
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: INSTANCEOF on non-reference");
1757                                 dv->type = TYPE_INT;
1758                                 break;
1759
1760                                 /****************************************/
1761                                 /* BRANCH INSTRUCTIONS                  */
1762
1763                         case ICMD_INLINE_GOTO:
1764                                 COPYTYPE(state->iptr->s1,state->iptr->dst);
1765                                 /* FALLTHROUGH! */
1766                         case ICMD_GOTO:
1767                                 superblockend = true;
1768                                 /* FALLTHROUGH! */
1769                         case ICMD_IFNULL:
1770                         case ICMD_IFNONNULL:
1771                         case ICMD_IFEQ:
1772                         case ICMD_IFNE:
1773                         case ICMD_IFLT:
1774                         case ICMD_IFGE:
1775                         case ICMD_IFGT:
1776                         case ICMD_IFLE:
1777                         case ICMD_IF_ICMPEQ:
1778                         case ICMD_IF_ICMPNE:
1779                         case ICMD_IF_ICMPLT:
1780                         case ICMD_IF_ICMPGE:
1781                         case ICMD_IF_ICMPGT:
1782                         case ICMD_IF_ICMPLE:
1783                         case ICMD_IF_ACMPEQ:
1784                         case ICMD_IF_ACMPNE:
1785
1786                         case ICMD_IF_LEQ:
1787                         case ICMD_IF_LNE:
1788                         case ICMD_IF_LLT:
1789                         case ICMD_IF_LGE:
1790                         case ICMD_IF_LGT:
1791                         case ICMD_IF_LLE:
1792
1793                         case ICMD_IF_LCMPEQ:
1794                         case ICMD_IF_LCMPNE:
1795                         case ICMD_IF_LCMPLT:
1796                         case ICMD_IF_LCMPGE:
1797                         case ICMD_IF_LCMPGT:
1798                         case ICMD_IF_LCMPLE:
1799
1800                         case ICMD_IF_FCMPEQ:
1801                         case ICMD_IF_FCMPNE:
1802
1803                         case ICMD_IF_FCMPL_LT:
1804                         case ICMD_IF_FCMPL_GE:
1805                         case ICMD_IF_FCMPL_GT:
1806                         case ICMD_IF_FCMPL_LE:
1807
1808                         case ICMD_IF_FCMPG_LT:
1809                         case ICMD_IF_FCMPG_GE:
1810                         case ICMD_IF_FCMPG_GT:
1811                         case ICMD_IF_FCMPG_LE:
1812
1813                         case ICMD_IF_DCMPEQ:
1814                         case ICMD_IF_DCMPNE:
1815
1816                         case ICMD_IF_DCMPL_LT:
1817                         case ICMD_IF_DCMPL_GE:
1818                         case ICMD_IF_DCMPL_GT:
1819                         case ICMD_IF_DCMPL_LE:
1820
1821                         case ICMD_IF_DCMPG_LT:
1822                         case ICMD_IF_DCMPG_GE:
1823                         case ICMD_IF_DCMPG_GT:
1824                         case ICMD_IF_DCMPG_LE:
1825                                 TYPECHECK_COUNT(stat_ins_branch);
1826
1827                                 /* propagate stack and variables to the target block */
1828                                 if (!typestate_reach(state, state->iptr->dst.block,
1829                                                                          state->bptr->outvars, jd->var,
1830                                                                          state->bptr->outdepth))
1831                                         return false;
1832                                 break;
1833
1834                                 /****************************************/
1835                                 /* SWITCHES                             */
1836
1837                         case ICMD_TABLESWITCH:
1838                                 TYPECHECK_COUNT(stat_ins_switch);
1839
1840                                 table = iptr->dst.table;
1841                                 i = iptr->sx.s23.s3.tablehigh
1842                                         - iptr->sx.s23.s2.tablelow + 1 + 1; /* plus default */
1843
1844                                 while (--i >= 0) {
1845                                         tbptr = (table++)->block;
1846                                         LOG2("target %d is block %04d",i,tbptr->nr);
1847                                         if (!typestate_reach(state, tbptr, state->bptr->outvars,
1848                                                                                  jd->var, state->bptr->outdepth))
1849                                                 return false;
1850                                 }
1851
1852                                 LOG("switch done");
1853                                 superblockend = true;
1854                                 break;
1855
1856                         case ICMD_LOOKUPSWITCH:
1857                                 TYPECHECK_COUNT(stat_ins_switch);
1858
1859                                 lookup = iptr->dst.lookup;
1860                                 i = iptr->sx.s23.s2.lookupcount;
1861
1862                                 if (!typestate_reach(state,iptr->sx.s23.s3.lookupdefault.block,
1863                                                                          state->bptr->outvars, jd->var,
1864                                                                          state->bptr->outdepth))
1865                                         return false;
1866
1867                                 while (--i >= 0) {
1868                                         tbptr = (lookup++)->target.block;
1869                                         LOG2("target %d is block %04d",i,tbptr->nr);
1870                                         if (!typestate_reach(state, tbptr, state->bptr->outvars,
1871                                                                 jd->var, state->bptr->outdepth))
1872                                                 return false;
1873                                 }
1874
1875                                 LOG("switch done");
1876                                 superblockend = true;
1877                                 break;
1878
1879
1880                                 /****************************************/
1881                                 /* ADDRESS RETURNS AND THROW            */
1882
1883                         case ICMD_ATHROW:
1884                                 TYPECHECK_COUNT(stat_ins_athrow);
1885                                 r = typeinfo_is_assignable_to_class(&VAROP(state->iptr->s1)->typeinfo,
1886                                                 CLASSREF_OR_CLASSINFO(class_java_lang_Throwable));
1887                                 if (r == typecheck_FALSE)
1888                                         TYPECHECK_VERIFYERROR_bool("illegal instruction: ATHROW on non-Throwable");
1889                                 if (r == typecheck_FAIL)
1890                                         return false;
1891                                 if (r == typecheck_MAYBE) {
1892                                         /* the check has to be postponed. we need a patcher */
1893                                         TYPECHECK_COUNT(stat_ins_athrow_unresolved);
1894                                         iptr->sx.s23.s2.uc = create_unresolved_class(
1895                                                         state->m,
1896                                                         /* XXX make this more efficient, use class_java_lang_Throwable
1897                                                          * directly */
1898                                                         class_get_classref(state->m->class,utf_java_lang_Throwable),
1899                                                         &VAROP(state->iptr->s1)->typeinfo);
1900                                         iptr->flags.bits |= INS_FLAG_UNRESOLVED;
1901                                 }
1902                                 superblockend = true;
1903                                 maythrow = true;
1904                                 break;
1905
1906                         case ICMD_ARETURN:
1907                                 TYPECHECK_COUNT(stat_ins_areturn);
1908                                 if (!TYPEINFO_IS_REFERENCE(VAROP(state->iptr->s1)->typeinfo))
1909                                         TYPECHECK_VERIFYERROR_bool("illegal instruction: ARETURN on non-reference");
1910
1911                                 if (state->returntype.type != TYPE_ADR
1912                                                 || (r = typeinfo_is_assignable(&VAROP(state->iptr->s1)->typeinfo,&(state->returntype.typeinfo)))
1913                                                                 == typecheck_FALSE)
1914                                         TYPECHECK_VERIFYERROR_bool("Return type mismatch");
1915                                 if (r == typecheck_FAIL)
1916                                         return false;
1917                                 if (r == typecheck_MAYBE) {
1918                                         /* the check has to be postponed, we need a patcher */
1919                                         TYPECHECK_COUNT(stat_ins_areturn_unresolved);
1920                                         iptr->sx.s23.s2.uc = create_unresolved_class(
1921                                                         state->m,
1922                                                         state->m->parseddesc->returntype.classref,
1923                                                         &VAROP(state->iptr->s1)->typeinfo);
1924                                         iptr->flags.bits |= INS_FLAG_UNRESOLVED;
1925                                 }
1926                                 goto return_tail;
1927
1928                                 /****************************************/
1929                                 /* PRIMITIVE RETURNS                    */
1930
1931                         case ICMD_IRETURN:
1932                                 if (state->returntype.type != TYPE_INT) TYPECHECK_VERIFYERROR_bool("Return type mismatch");
1933                                 goto return_tail;
1934
1935                         case ICMD_LRETURN:
1936                                 if (state->returntype.type != TYPE_LNG) TYPECHECK_VERIFYERROR_bool("Return type mismatch");
1937                                 goto return_tail;
1938
1939                         case ICMD_FRETURN:
1940                                 if (state->returntype.type != TYPE_FLT) TYPECHECK_VERIFYERROR_bool("Return type mismatch");
1941                                 goto return_tail;
1942
1943                         case ICMD_DRETURN:
1944                                 if (state->returntype.type != TYPE_DBL) TYPECHECK_VERIFYERROR_bool("Return type mismatch");
1945                                 goto return_tail;
1946
1947                         case ICMD_RETURN:
1948                                 if (state->returntype.type != TYPE_VOID) TYPECHECK_VERIFYERROR_bool("Return type mismatch");
1949 return_tail:
1950                                 TYPECHECK_COUNT(stat_ins_primitive_return);
1951
1952                                 if (state->initmethod && state->m->class != class_java_lang_Object) {
1953                                         /* Check if the 'this' instance has been initialized. */
1954                                         LOG("Checking <init> marker");
1955                                         if (!typevector_checktype(jd->var,state->numlocals-1,TYPE_INT))
1956                                                 TYPECHECK_VERIFYERROR_bool("<init> method does not initialize 'this'");
1957                                 }
1958
1959                                 superblockend = true;
1960                                 maythrow = true;
1961                                 break;
1962
1963                                 /****************************************/
1964                                 /* SUBROUTINE INSTRUCTIONS              */
1965
1966                         case ICMD_JSR:
1967                                 LOG("jsr");
1968
1969                                 tbptr = state->iptr->sx.s23.s3.jsrtarget.block;
1970                                 TYPEINFO_INIT_RETURNADDRESS(dv->typeinfo, state->bptr->next);
1971                                 if (!typestate_reach(state, tbptr, state->bptr->outvars, jd->var,
1972                                                         state->bptr->outdepth))
1973                                         return false;
1974
1975                                 superblockend = true;
1976                                 break;
1977
1978                         case ICMD_RET:
1979                                 /* check returnAddress variable */
1980                                 if (!typevector_checkretaddr(jd->var,state->iptr->s1.varindex))
1981                                         TYPECHECK_VERIFYERROR_bool("illegal instruction: RET using non-returnAddress variable");
1982
1983                                 if (!typestate_reach(state, iptr->dst.block, state->bptr->outvars, jd->var,
1984                                                         state->bptr->outdepth))
1985                                         return false;
1986
1987                                 superblockend = true;
1988                                 break;
1989
1990                                 /****************************************/
1991                                 /* INVOKATIONS                          */
1992
1993                         case ICMD_INVOKEVIRTUAL:
1994                         case ICMD_INVOKESPECIAL:
1995                         case ICMD_INVOKESTATIC:
1996                         case ICMD_INVOKEINTERFACE:
1997                                 TYPECHECK_COUNT(stat_ins_invoke);
1998                                 if (!verify_invocation(state))
1999                                         return false;
2000                                 TYPECHECK_COUNTIF(INSTRUCTION_IS_UNRESOLVED(iptr), stat_ins_invoke_unresolved);
2001                                 maythrow = true;
2002                                 break;
2003
2004                                 /****************************************/
2005                                 /* MULTIANEWARRAY                       */
2006
2007                         case ICMD_MULTIANEWARRAY:
2008                                 if (!verify_multianewarray(state))
2009                                         return false;
2010                                 maythrow = true;
2011                                 break;
2012
2013                                 /****************************************/
2014                                 /* BUILTINS                             */
2015
2016                         case ICMD_BUILTIN:
2017                                 TYPECHECK_COUNT(stat_ins_builtin);
2018                                 if (!verify_builtin(state))
2019                                         return false;
2020                                 maythrow = true;
2021                                 break;
2022
2023                                 /****************************************/
2024                                 /* SIMPLE EXCEPTION THROWING TESTS      */
2025
2026                         case ICMD_CHECKNULL:
2027                                 /* CHECKNULL just requires that the stack top
2028                                  * is an address. This is checked in stack.c */
2029                                 maythrow = true;
2030                                 break;
2031
2032                                 /****************************************/
2033                                 /* INSTRUCTIONS WHICH SHOULD HAVE BEEN  */
2034                                 /* REPLACED BY OTHER OPCODES            */
2035
2036 #ifdef TYPECHECK_DEBUG
2037                         case ICMD_NEW:
2038                         case ICMD_NEWARRAY:
2039                         case ICMD_ANEWARRAY:
2040                         case ICMD_MONITORENTER:
2041                         case ICMD_MONITOREXIT:
2042                                 LOG2("ICMD %d at %d\n", state->iptr->opc, (int)(state->iptr-state->bptr->iinstr));
2043                                 LOG("Should have been converted to builtin function call.");
2044                                 TYPECHECK_ASSERT(false);
2045                                 break;
2046 #endif
2047
2048                                 /****************************************/
2049                                 /* UNCHECKED OPERATIONS                 */
2050
2051                                 /*********************************************
2052                                  * Instructions below...
2053                                  *     *) don't operate on local variables,
2054                                  *     *) don't operate on references,
2055                                  *     *) don't operate on returnAddresses,
2056                                  *     *) don't affect control flow (except
2057                                  *        by throwing exceptions).
2058                                  *
2059                                  * (These instructions are typechecked in
2060                                  *  analyse_stack.)
2061                                  ********************************************/
2062
2063                                 /* Instructions which may throw a runtime exception: */
2064
2065                         case ICMD_IDIV:
2066                         case ICMD_IREM:
2067                                 dv->type = TYPE_INT;
2068                                 maythrow = true;
2069                                 break;
2070
2071                         case ICMD_LDIV:
2072                         case ICMD_LREM:
2073                                 dv->type = TYPE_LNG;
2074                                 maythrow = true;
2075                                 break;
2076
2077                                 /* Instructions which never throw a runtime exception: */
2078                         case ICMD_NOP:
2079                         case ICMD_POP:
2080                         case ICMD_POP2:
2081                                 break;
2082
2083                         case ICMD_ICONST:
2084                         case ICMD_IADD:
2085                         case ICMD_ISUB:
2086                         case ICMD_IMUL:
2087                         case ICMD_INEG:
2088                         case ICMD_IAND:
2089                         case ICMD_IOR:
2090                         case ICMD_IXOR:
2091                         case ICMD_ISHL:
2092                         case ICMD_ISHR:
2093                         case ICMD_IUSHR:
2094                         case ICMD_IMULPOW2:
2095                         case ICMD_IDIVPOW2:
2096                         case ICMD_IADDCONST:
2097                         case ICMD_ISUBCONST:
2098                         case ICMD_IMULCONST:
2099                         case ICMD_IANDCONST:
2100                         case ICMD_IORCONST:
2101                         case ICMD_IXORCONST:
2102                         case ICMD_ISHLCONST:
2103                         case ICMD_ISHRCONST:
2104                         case ICMD_IUSHRCONST:
2105                         case ICMD_IREMPOW2:
2106                         case ICMD_INT2BYTE:
2107                         case ICMD_INT2CHAR:
2108                         case ICMD_INT2SHORT:
2109                         case ICMD_L2I:
2110                         case ICMD_F2I:
2111                         case ICMD_D2I:
2112                         case ICMD_LCMP:
2113                         case ICMD_LCMPCONST:
2114                         case ICMD_FCMPL:
2115                         case ICMD_FCMPG:
2116                         case ICMD_DCMPL:
2117                         case ICMD_DCMPG:
2118                                 dv->type = TYPE_INT;
2119                                 break;
2120
2121                         case ICMD_LCONST:
2122                         case ICMD_LADD:
2123                         case ICMD_LSUB:
2124                         case ICMD_LMUL:
2125                         case ICMD_LNEG:
2126                         case ICMD_LAND:
2127                         case ICMD_LOR:
2128                         case ICMD_LXOR:
2129                         case ICMD_LSHL:
2130                         case ICMD_LSHR:
2131                         case ICMD_LUSHR:
2132                         case ICMD_LMULPOW2:
2133                         case ICMD_LDIVPOW2:
2134                         case ICMD_LADDCONST:
2135                         case ICMD_LSUBCONST:
2136                         case ICMD_LMULCONST:
2137                         case ICMD_LANDCONST:
2138                         case ICMD_LORCONST:
2139                         case ICMD_LXORCONST:
2140                         case ICMD_LSHLCONST:
2141                         case ICMD_LSHRCONST:
2142                         case ICMD_LUSHRCONST:
2143                         case ICMD_LREMPOW2:
2144                         case ICMD_I2L:
2145                         case ICMD_F2L:
2146                         case ICMD_D2L:
2147                                 dv->type = TYPE_LNG;
2148                                 break;
2149
2150                         case ICMD_FCONST:
2151                         case ICMD_I2F:
2152                         case ICMD_L2F:
2153                         case ICMD_D2F:
2154                         case ICMD_FADD:
2155                         case ICMD_FSUB:
2156                         case ICMD_FMUL:
2157                         case ICMD_FDIV:
2158                         case ICMD_FREM:
2159                         case ICMD_FNEG:
2160                                 dv->type = TYPE_FLT;
2161                                 break;
2162
2163                         case ICMD_DCONST:
2164                         case ICMD_I2D:
2165                         case ICMD_L2D:
2166                         case ICMD_F2D:
2167                         case ICMD_DADD:
2168                         case ICMD_DSUB:
2169                         case ICMD_DMUL:
2170                         case ICMD_DDIV:
2171                         case ICMD_DREM:
2172                         case ICMD_DNEG:
2173                                 dv->type = TYPE_DBL;
2174                                 break;
2175
2176                         case ICMD_INLINE_START:
2177                         case ICMD_INLINE_END:
2178                                 break;
2179
2180                                 /* XXX What shall we do with the following ?*/
2181                         case ICMD_AASTORECONST:
2182                                 TYPECHECK_COUNT(stat_ins_unchecked);
2183                                 break;
2184
2185                                 /****************************************/
2186
2187                         default:
2188                                 LOG2("ICMD %d at %d\n", state->iptr->opc, (int)(state->iptr-state->bptr->iinstr));
2189                                 TYPECHECK_VERIFYERROR_bool("Missing ICMD code during typecheck");
2190                 }
2191
2192                 /* reach exception handlers for this instruction */
2193
2194                 if (maythrow) {
2195                         TYPECHECK_COUNT(stat_ins_maythrow);
2196                         TYPECHECK_MARK(state->stat_maythrow);
2197                         LOG("reaching exception handlers");
2198                         i = 0;
2199                         while (state->handlers[i]) {
2200                                 TYPECHECK_COUNT(stat_handlers_reached);
2201                                 if (state->handlers[i]->catchtype.any)
2202                                         VAR(state->exinvars)->typeinfo.typeclass = state->handlers[i]->catchtype;
2203                                 else
2204                                         VAR(state->exinvars)->typeinfo.typeclass.cls = class_java_lang_Throwable;
2205                                 if (!typestate_reach(state,
2206                                                 state->handlers[i]->handler,
2207                                                 &(state->exinvars), jd->var, 1))
2208                                         return false;
2209                                 i++;
2210                         }
2211                 }
2212
2213                 LOG("\t\tnext instruction");
2214                 state->iptr++;
2215         } /* while instructions */
2216
2217         LOG("instructions done");
2218         LOGSTR("RESULT=> ");
2219         DOLOG(typecheck_print_vararray(stdout, jd, state->bptr->outvars,
2220                                 state->bptr->outdepth));
2221         DOLOG(typevector_print(stdout, jd->var, state->numlocals));
2222         LOGNL; LOGFLUSH;
2223
2224         /* propagate stack and variables to the following block */
2225         if (!superblockend) {
2226                 LOG("reaching following block");
2227                 tbptr = state->bptr->next;
2228                 while (tbptr->flags == BBDELETED) {
2229                         tbptr = tbptr->next;
2230 #ifdef TYPECHECK_DEBUG
2231                         /* this must be checked in parse.c */
2232                         if ((tbptr->nr) >= state->basicblockcount)
2233                                 TYPECHECK_VERIFYERROR_bool("Control flow falls off the last block");
2234 #endif
2235                 }
2236                 if (!typestate_reach(state,tbptr,state->bptr->outvars, jd->var,
2237                                         state->bptr->outdepth))
2238                         return false;
2239         }
2240
2241         /* We may have to restore the types of the instack slots. They
2242          * have been saved if an <init> call inside the block has
2243          * modified the instack types. (see INVOKESPECIAL) */
2244
2245         if (state->savedinvars)
2246                 typestate_restore_invars(state);
2247
2248         return true;
2249 }
2250
2251
2252 /* verify_init_locals **********************************************************
2253
2254    Initialize the local variables in the verifier state.
2255
2256    IN:
2257        state............the current state of the verifier
2258
2259    RETURN VALUE:
2260        true.............success,
2261            false............an exception has been thrown.
2262
2263 *******************************************************************************/
2264
2265 static bool
2266 verify_init_locals(verifier_state *state)
2267 {
2268         int i;
2269         int index;
2270         varinfo *locals;
2271         varinfo *v;
2272         jitdata *jd = state->jd;
2273         int skip = 0;
2274
2275         locals = state->basicblocks[0].inlocals;
2276
2277         /* allocate parameter descriptors if necessary */
2278
2279         if (!state->m->parseddesc->params)
2280                 if (!descriptor_params_from_paramtypes(state->m->parseddesc,state->m->flags))
2281                         return false;
2282
2283         /* pre-initialize variables as TYPE_VOID */
2284
2285         i = state->numlocals;
2286         v = locals;
2287         while (i--) {
2288                 v->type = TYPE_VOID;
2289                 v++;
2290         }
2291
2292     /* if this is an instance method initialize the "this" ref type */
2293
2294     if (!(state->m->flags & ACC_STATIC)) {
2295                 index = jd->local_map[5*0 + TYPE_ADR];
2296                 if (index != UNUSED) {
2297                         if (state->validlocals < 1)
2298                                 TYPECHECK_VERIFYERROR_bool("Not enough local variables for method arguments");
2299                         v = locals + index;
2300                         v->type = TYPE_ADR;
2301                         if (state->initmethod)
2302                                 TYPEINFO_INIT_NEWOBJECT(v->typeinfo, NULL);
2303                         else
2304                                 typeinfo_init_classinfo(&(v->typeinfo), state->m->class);
2305                 }
2306
2307                 skip = 1;
2308     }
2309
2310     LOG("'this' argument set.\n");
2311
2312     /* the rest of the arguments and the return type */
2313
2314     if (!typeinfo_init_varinfos_from_methoddesc(locals, state->m->parseddesc,
2315                                                                                           state->validlocals,
2316                                                                                           skip, /* skip 'this' pointer */
2317                                                                                           jd->local_map,
2318                                                                                           &state->returntype))
2319                 return false;
2320
2321     LOG("Arguments set.\n");
2322         return true;
2323 }
2324
2325
2326 /* typecheck_init_flags ********************************************************
2327
2328    Initialize the basic block flags for the following CFG traversal.
2329
2330    IN:
2331        state............the current state of the verifier
2332
2333 *******************************************************************************/
2334
2335 static void
2336 typecheck_init_flags(verifier_state *state)
2337 {
2338         s4 i;
2339         basicblock *block;
2340
2341     /* set all BBFINISHED blocks to BBTYPECHECK_UNDEF. */
2342
2343     i = state->basicblockcount;
2344     for (block = state->basicblocks; block; block = block->next) {
2345
2346 #ifdef TYPECHECK_DEBUG
2347                 /* check for invalid flags */
2348         if (block->flags != BBFINISHED && block->flags != BBDELETED && block->flags != BBUNDEF)
2349         {
2350             /*show_icmd_method(state->m,state->cd,state->rd);*/
2351             LOGSTR1("block flags: %d\n",block->flags); LOGFLUSH;
2352                         TYPECHECK_ASSERT(false);
2353         }
2354 #endif
2355
2356         if (block->flags >= BBFINISHED) {
2357             block->flags = BBTYPECHECK_UNDEF;
2358         }
2359     }
2360
2361     /* the first block is always reached */
2362
2363     if (state->basicblockcount && state->basicblocks[0].flags == BBTYPECHECK_UNDEF)
2364         state->basicblocks[0].flags = BBTYPECHECK_REACHED;
2365 }
2366
2367
2368 /* typecheck_reset_flags *******************************************************
2369
2370    Reset the flags of basic blocks we have not reached.
2371
2372    IN:
2373        state............the current state of the verifier
2374
2375 *******************************************************************************/
2376
2377 static void
2378 typecheck_reset_flags(verifier_state *state)
2379 {
2380         basicblock *block;
2381
2382         /* check for invalid flags at exit */
2383
2384 #ifdef TYPECHECK_DEBUG
2385         for (block = state->basicblocks; block; block = block->next) {
2386                 if (block->flags != BBDELETED
2387                         && block->flags != BBUNDEF
2388                         && block->flags != BBFINISHED
2389                         && block->flags != BBTYPECHECK_UNDEF) /* typecheck may never reach
2390                                                                                                          * some exception handlers,
2391                                                                                                          * that's ok. */
2392                 {
2393                         LOG2("block L%03d has invalid flags after typecheck: %d",
2394                                  block->nr,block->flags);
2395                         TYPECHECK_ASSERT(false);
2396                 }
2397         }
2398 #endif
2399
2400         /* Reset blocks we never reached */
2401
2402         for (block = state->basicblocks; block; block = block->next) {
2403                 if (block->flags == BBTYPECHECK_UNDEF)
2404                         block->flags = BBFINISHED;
2405         }
2406 }
2407
2408
2409 /****************************************************************************/
2410 /* typecheck()                                                              */
2411 /* This is the main function of the bytecode verifier. It is called         */
2412 /* directly after analyse_stack.                                            */
2413 /*                                                                          */
2414 /* IN:                                                                      */
2415 /*    meth.............the method to verify                                 */
2416 /*    cdata............codegendata for the method                           */
2417 /*    rdata............registerdata for the method                          */
2418 /*                                                                          */
2419 /* RETURN VALUE:                                                            */
2420 /*     true.............successful verification                             */
2421 /*     false............an exception has been thrown                        */
2422 /*                                                                          */
2423 /****************************************************************************/
2424
2425 #define MAXPARAMS 255
2426
2427 bool typecheck(jitdata *jd)
2428 {
2429         methodinfo     *meth;
2430         codegendata    *cd;
2431         registerdata   *rd;
2432         varinfo        *savedlocals;
2433         verifier_state  state;             /* current state of the verifier */
2434         s4              i;
2435         s4              t;
2436
2437         /* collect statistics */
2438
2439 #ifdef TYPECHECK_STATISTICS
2440         int count_iterations = 0;
2441         TYPECHECK_COUNT(stat_typechecked);
2442         TYPECHECK_COUNT_FREQ(stat_locals,cdata->maxlocals,STAT_LOCALS);
2443         TYPECHECK_COUNT_FREQ(stat_blocks,cdata->method->basicblockcount/10,STAT_BLOCKS);
2444         TYPECHECK_COUNTIF(cdata->method->exceptiontablelength != 0,stat_methods_with_handlers);
2445         state.stat_maythrow = false;
2446 #endif
2447
2448         /* get required compiler data */
2449
2450         meth = jd->m;
2451         cd   = jd->cd;
2452         rd   = jd->rd;
2453
2454         /* some logging on entry */
2455
2456
2457     LOGSTR("\n==============================================================================\n");
2458     DOLOG( new_show_method(jd, SHOW_STACK) );
2459     LOGSTR("\n==============================================================================\n");
2460     LOGMETHOD("Entering typecheck: ",cd->method);
2461
2462         /* initialize the verifier state */
2463
2464         state.m = meth;
2465         state.jd = jd;
2466         state.cd = cd;
2467         state.rd = rd;
2468         state.basicblockcount = jd->new_basicblockcount;
2469         state.basicblocks = jd->new_basicblocks;
2470         state.savedindices = NULL;
2471         state.savedinvars = NULL;
2472
2473         /* check if this method is an instance initializer method */
2474
2475     state.initmethod = (state.m->name == utf_init);
2476
2477         /* initialize the basic block flags for the following CFG traversal */
2478
2479         typecheck_init_flags(&state);
2480
2481     /* number of local variables */
2482
2483     /* In <init> methods we use an extra local variable to indicate whether */
2484     /* the 'this' reference has been initialized.                           */
2485         /*         TYPE_VOID...means 'this' has not been initialized,           */
2486         /*         TYPE_INT....means 'this' has been initialized.               */
2487
2488     state.numlocals = state.jd->localcount;
2489         state.validlocals = state.numlocals;
2490     if (state.initmethod)
2491                 state.numlocals++; /* VERIFIER_EXTRA_LOCALS */
2492
2493         state.reverselocalmap = DMNEW(s4, state.validlocals);
2494         for (i=0; i<jd->m->maxlocals; ++i)
2495                 for (t=0; t<5; ++t) {
2496                         s4 mapped = jd->local_map[5*i + t];
2497                         if (mapped >= 0)
2498                                 state.reverselocalmap[mapped] = i;
2499                 }
2500
2501     /* allocate the buffer of active exception handlers */
2502
2503     state.handlers = DMNEW(exceptiontable*, state.cd->exceptiontablelength + 1);
2504
2505         /* save local variables */
2506
2507         savedlocals = DMNEW(varinfo, state.numlocals);
2508         MCOPY(savedlocals, jd->var, varinfo, state.numlocals);
2509
2510         /* initialized local variables of first block */
2511
2512         if (!verify_init_locals(&state))
2513                 return false;
2514
2515     /* initialize invars of exception handlers */
2516
2517         state.exinvars = state.numlocals;
2518         VAR(state.exinvars)->type = TYPE_ADR;
2519         typeinfo_init_classinfo(&(VAR(state.exinvars)->typeinfo),
2520                                                         class_java_lang_Throwable); /* changed later */
2521
2522     LOG("Exception handler stacks set.\n");
2523
2524     /* loop while there are still blocks to be checked */
2525     do {
2526                 TYPECHECK_COUNT(count_iterations);
2527
2528         state.repeat = false;
2529
2530         state.bptr = state.basicblocks;
2531
2532         for (; state.bptr; state.bptr = state.bptr->next) {
2533             LOGSTR1("---- BLOCK %04d, ",state.bptr->nr);
2534             LOGSTR1("blockflags: %d\n",state.bptr->flags);
2535             LOGFLUSH;
2536
2537                     /* verify reached block */
2538             if (state.bptr->flags == BBTYPECHECK_REACHED) {
2539                 if (!verify_basic_block(&state))
2540                                         return false;
2541             }
2542         } /* for blocks */
2543
2544         LOGIF(state.repeat,"state.repeat == true");
2545     } while (state.repeat);
2546
2547         /* statistics */
2548
2549 #ifdef TYPECHECK_STATISTICS
2550         LOG1("Typechecker did %4d iterations",count_iterations);
2551         TYPECHECK_COUNT_FREQ(stat_iterations,count_iterations,STAT_ITERATIONS);
2552         TYPECHECK_COUNTIF(state.jsrencountered,stat_typechecked_jsr);
2553         TYPECHECK_COUNTIF(state.stat_maythrow,stat_methods_maythrow);
2554 #endif
2555
2556         /* reset the flags of blocks we haven't reached */
2557
2558         typecheck_reset_flags(&state);
2559
2560         /* restore locals */
2561
2562         MCOPY(jd->var, savedlocals, varinfo, state.numlocals);
2563
2564         /* everything's ok */
2565
2566     LOGimp("exiting typecheck");
2567         return true;
2568 }
2569 #endif /* ENABLE_VERIFIER */
2570
2571 /*
2572  * These are local overrides for various environment variables in Emacs.
2573  * Please do not remove this and leave it at the end of the file, where
2574  * Emacs will automagically detect them.
2575  * ---------------------------------------------------------------------
2576  * Local variables:
2577  * mode: c
2578  * indent-tabs-mode: t
2579  * c-basic-offset: 4
2580  * tab-width: 4
2581  * End:
2582  * vim:noexpandtab:sw=4:ts=4:
2583  */