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 5742 2006-10-11 23:37:32Z edwin $
  32
  33 */
  34
  35 /*
  36
  37 What's the purpose of the `typechecker`?
  38 ----------------------------------------
  39
  40 The typechecker analyses (the intermediate repr. of) the bytecode of
  41 each method and ensures that for each instruction the values on the
  42 stack and in local variables are of the correct type whenever the
  43 instruction is executed.
  44
  45 type checking is a mandatory part of bytecode verification.
  46
  47
  48 How does the typechecker work?
  49 ------------------------------
  50
  51 The JVM stack and the local variables are not statically typed, so the
  52 typechecker has to *infer* the static types of stack slots and local
  53 variables at each point of the method. The JVM spec imposes a lot of
  54 restrictions on the bytecode in order to guarantee that this is always
  55 possible.
  56
  57 Basically the typechecker solves the data flow equations of the method.
  58 This is done in the usual way for a forward data flow analysis: Starting
  59 from the entry point of the method the typechecker follows the CFG and
  60 records the type of each stack slot and local variable at each point[1].
  61 When two or more control flow paths merge at a point, the union of the
  62 types for each slot/variable is taken. The algorithm continues to follow
  63 all possible paths[2] until the recorded types do not change anymore (ie.
  64 the equations have been solved).
  65
  66 If the solution has been reached and the resulting types are valid for
  67 all instructions, then type checking terminates with success, otherwise
  68 an exception is thrown.
  69
  70
  71 Why is this code so damn complicated?
  72 -------------------------------------
  73
  74 Short answer: The devil's in the details.
  75
  76 While the basic operation of the typechecker is no big deal, there are
  77 many properties of Java bytecode which make type checking hard. Some of
  78 them are not even addressed in the JVM spec. Some problems and their
  79 solutions:
  80
  81 *) Finding a good representation of the union of two reference types is
  82 difficult because of multiple inheritance of interfaces.
  83
  84         Solution: The typeinfo system can represent such "merged" types by a
  85         list of proper subclasses of a class. Example:
  86
  87                 typeclass=java.lang.Object merged={ InterfaceA, InterfaceB }
  88
  89         represents the result of merging two interface types "InterfaceA"
  90         and "InterfaceB".
  91
  92 *) When the code of a method is verified, there may still be unresolved
  93 references to classes/methods/fields in the code, which we may not force
  94 to be resolved eagerly. (A similar problem arises because of the special
  95 checks for protected members.)
  96
  97         Solution: The typeinfo system knows how to deal with unresolved
  98         class references. Whenever a check has to be performed for an
  99         unresolved type, the type is annotated with constraints representing
 100         the check. Later, when the type is resolved, the constraints are
 101         checked. (See the constrain_unresolved_... and the resolve_...
 102         methods.)[3]
 103
 104 *) Checks for uninitialized object instances are hard because after the
 105 invocation of <init> on an uninitialized object *all* slots/variables
 106 referring to this object (and exactly those slots/variables) must be
 107 marked as initialized.
 108
 109         Solution: The JVM spec describes a solution, which has been
 110         implemented in this typechecker.
 111
 112 Note that some checks mentioned in the JVM spec are unnecessary[4] and
 113 not performed by either the reference implementation, or this implementation.
 114
 115
 116 --- Footnotes
 117
 118 [1] Actually only the types of slots/variables at the start of each
 119 basic block are remembered. Within a basic block the algorithm only keeps
 120 the types of the slots/variables for the "current" instruction which is
 121 being analysed.
 122
 123 [2] Actually the algorithm iterates through the basic block list until
 124 there are no more changes. Theoretically it would be wise to sort the
 125 basic blocks topologically beforehand, but the number of average/max
 126 iterations observed is so low, that this was not deemed necessary.
 127
 128 [3] This is similar to a method proposed by: Alessandro Coglio et al., A
 129 Formal Specification of Java Class Loading, Technical Report, Kestrel
 130 Institute April 2000, revised July 2000
 131 http://www.kestrel.edu/home/people/coglio/loading.pdf
 132 An important difference is that Coglio's subtype constraints are checked
 133 after loading, while our constraints are checked when the field/method
 134 is accessed for the first time, so we can guarantee lexically correct
 135 error reporting.
 136
 137 [4] Alessandro Coglio
 138     Improving the official specification of Java bytecode verification
 139     Proceedings of the 3rd ECOOP Workshop on Formal Techniques for Java Programs
 140     June 2001
 141     citeseer.ist.psu.edu/article/coglio03improving.html
 142 */
 143
 144 #include <assert.h>
 145 #include <string.h>
 146
 147 #include "config.h"
 148 #include "vm/types.h"
 149 #include "vm/global.h"
 150
 151 #ifdef ENABLE_VERIFIER
 152
 153 #include "mm/memory.h"
 154 #include "toolbox/logging.h"
 155 #include "native/native.h"
 156 #include "vm/builtin.h"
 157 #include "vm/jit/patcher.h"
 158 #include "vm/loader.h"
 159 #include "vm/options.h"
 160 #include "vm/jit/jit.h"
 161 #include "vm/jit/show.h"
 162 #include "vm/access.h"
 163 #include "vm/resolve.h"
 164 #include "vm/exceptions.h"
 165
 166 /****************************************************************************/
 167 /* DEBUG HELPERS                                                            */
 168 /****************************************************************************/
 169
 170 #ifdef TYPECHECK_DEBUG
 171 #define TYPECHECK_ASSERT(cond)  assert(cond)
 172 #else
 173 #define TYPECHECK_ASSERT(cond)
 174 #endif
 175
 176 #ifdef TYPECHECK_VERBOSE_OPT
 177 bool opt_typecheckverbose = false;
 178 #define DOLOG(action)  do { if (opt_typecheckverbose) {action;} } while(0)
 179 #else
 180 #define DOLOG(action)
 181 #endif
 182
 183 #ifdef TYPECHECK_VERBOSE
 184 #define TYPECHECK_VERBOSE_IMPORTANT
 185 #define LOGNL              DOLOG(puts(""))
 186 #define LOG(str)           DOLOG(puts(str);)
 187 #define LOG1(str,a)        DOLOG(printf(str,a); LOGNL)
 188 #define LOG2(str,a,b)      DOLOG(printf(str,a,b); LOGNL)
 189 #define LOG3(str,a,b,c)    DOLOG(printf(str,a,b,c); LOGNL)
 190 #define LOGIF(cond,str)    DOLOG(do {if (cond) { puts(str); }} while(0))
 191 #ifdef  TYPEINFO_DEBUG
 192 #define LOGINFO(info)      DOLOG(do {typeinfo_print_short(stdout,(info)); LOGNL;} while(0))
 193 #else
 194 #define LOGINFO(info)
 195 #define typevector_print(x,y,z)
 196 #endif
 197 #define LOGFLUSH           DOLOG(fflush(stdout))
 198 #define LOGSTR(str)        DOLOG(printf("%s", str))
 199 #define LOGSTR1(str,a)     DOLOG(printf(str,a))
 200 #define LOGSTR2(str,a,b)   DOLOG(printf(str,a,b))
 201 #define LOGSTR3(str,a,b,c) DOLOG(printf(str,a,b,c))
 202 #define LOGNAME(c)         DOLOG(class_classref_or_classinfo_print(c))
 203 #define LOGMETHOD(str,m)   DOLOG(printf("%s", str); method_println(m);)
 204 #else
 205 #define LOG(str)
 206 #define LOG1(str,a)
 207 #define LOG2(str,a,b)
 208 #define LOG3(str,a,b,c)
 209 #define LOGIF(cond,str)
 210 #define LOGINFO(info)
 211 #define LOGFLUSH
 212 #define LOGNL
 213 #define LOGSTR(str)
 214 #define LOGSTR1(str,a)
 215 #define LOGSTR2(str,a,b)
 216 #define LOGSTR3(str,a,b,c)
 217 #define LOGNAME(c)
 218 #define LOGMETHOD(str,m)
 219 #endif
 220
 221 #ifdef TYPECHECK_VERBOSE_IMPORTANT
 222 #define LOGimp(str)     DOLOG(puts(str);LOGNL)
 223 #define LOGimpSTR(str)  DOLOG(puts(str))
 224 #else
 225 #define LOGimp(str)
 226 #define LOGimpSTR(str)
 227 #endif
 228
 229 #if defined(TYPECHECK_VERBOSE) || defined(TYPECHECK_VERBOSE_IMPORTANT)
 230
 231 #include <stdio.h>
 232
 233 static void typecheck_print_var(FILE *file, jitdata *jd, s4 index)
 234 {
 235         varinfo *var;
 236
 237         assert(index >= 0 && index < jd->varcount);
 238         var = VAR(index);
 239         typeinfo_print_type(file, var->type, &(var->typeinfo));
 240 }
 241
 242 static void typecheck_print_vararray(FILE *file, jitdata *jd, s4 *vars, int len)
 243 {
 244         s4 i;
 245
 246         for (i=0; i<len; ++i) {
 247                 if (i)
 248                         fputc(' ', file);
 249                 typecheck_print_var(file, jd, *vars++);
 250         }
 251 }
 252
 253 #endif
 254
 255
 256 /****************************************************************************/
 257 /* STATISTICS                                                               */
 258 /****************************************************************************/
 259
 260 #ifdef TYPECHECK_DEBUG
 261 /*#define TYPECHECK_STATISTICS*/
 262 #endif
 263
 264 #ifdef TYPECHECK_STATISTICS
 265 #define STAT_ITERATIONS  10
 266 #define STAT_BLOCKS      10
 267 #define STAT_LOCALS      16
 268
 269 static int stat_typechecked = 0;
 270 static int stat_methods_with_handlers = 0;
 271 static int stat_methods_maythrow = 0;
 272 static int stat_iterations[STAT_ITERATIONS+1] = { 0 };
 273 static int stat_reached = 0;
 274 static int stat_copied = 0;
 275 static int stat_merged = 0;
 276 static int stat_merging_changed = 0;
 277 static int stat_blocks[STAT_BLOCKS+1] = { 0 };
 278 static int stat_locals[STAT_LOCALS+1] = { 0 };
 279 static int stat_ins = 0;
 280 static int stat_ins_maythrow = 0;
 281 static int stat_ins_stack = 0;
 282 static int stat_ins_field = 0;
 283 static int stat_ins_field_unresolved = 0;
 284 static int stat_ins_field_uninitialized = 0;
 285 static int stat_ins_invoke = 0;
 286 static int stat_ins_invoke_unresolved = 0;
 287 static int stat_ins_primload = 0;
 288 static int stat_ins_aload = 0;
 289 static int stat_ins_builtin = 0;
 290 static int stat_ins_builtin_gen = 0;
 291 static int stat_ins_branch = 0;
 292 static int stat_ins_switch = 0;
 293 static int stat_ins_primitive_return = 0;
 294 static int stat_ins_areturn = 0;
 295 static int stat_ins_areturn_unresolved = 0;
 296 static int stat_ins_athrow = 0;
 297 static int stat_ins_athrow_unresolved = 0;
 298 static int stat_ins_unchecked = 0;
 299 static int stat_handlers_reached = 0;
 300 static int stat_savedstack = 0;
 301
 302 #define TYPECHECK_MARK(var)   ((var) = true)
 303 #define TYPECHECK_COUNT(cnt)  (cnt)++
 304 #define TYPECHECK_COUNTIF(cond,cnt)  do{if(cond) (cnt)++;} while(0)
 305 #define TYPECHECK_COUNT_FREQ(array,val,limit) \
 306         do {                                                                      \
 307                 if ((val) < (limit)) (array)[val]++;  \
 308                 else (array)[limit]++;                            \
 309         } while (0)
 310
 311 static void print_freq(FILE *file,int *array,int limit)
 312 {
 313         int i;
 314         for (i=0; i<limit; ++i)
 315                 fprintf(file,"      %3d: %8d\n",i,array[i]);
 316         fprintf(file,"    >=%3d: %8d\n",limit,array[limit]);
 317 }
 318
 319 void typecheck_print_statistics(FILE *file) {
 320         fprintf(file,"typechecked methods: %8d\n",stat_typechecked);
 321         fprintf(file,"    with handler(s): %8d\n",stat_methods_with_handlers);
 322         fprintf(file,"    with throw(s)  : %8d\n",stat_methods_maythrow);
 323         fprintf(file,"reached blocks     : %8d\n",stat_reached);
 324         fprintf(file,"copied states      : %8d\n",stat_copied);
 325         fprintf(file,"merged states      : %8d\n",stat_merged);
 326         fprintf(file,"merging changed    : %8d\n",stat_merging_changed);
 327         fprintf(file,"handlers reached   : %8d\n",stat_handlers_reached);
 328         fprintf(file,"saved stack (times): %8d\n",stat_savedstack);
 329         fprintf(file,"instructions       : %8d\n",stat_ins);
 330         fprintf(file,"    stack          : %8d\n",stat_ins_stack);
 331         fprintf(file,"    field access   : %8d\n",stat_ins_field);
 332         fprintf(file,"      (unresolved) : %8d\n",stat_ins_field_unresolved);
 333         fprintf(file,"      (uninit.)    : %8d\n",stat_ins_field_uninitialized);
 334         fprintf(file,"    invocations    : %8d\n",stat_ins_invoke);
 335         fprintf(file,"      (unresolved) : %8d\n",stat_ins_invoke_unresolved);
 336         fprintf(file,"    load primitive : (currently not counted) %8d\n",stat_ins_primload);
 337         fprintf(file,"    load address   : %8d\n",stat_ins_aload);
 338         fprintf(file,"    builtins       : %8d\n",stat_ins_builtin);
 339         fprintf(file,"        generic    : %8d\n",stat_ins_builtin_gen);
 340         fprintf(file,"    branches       : %8d\n",stat_ins_branch);
 341         fprintf(file,"    switches       : %8d\n",stat_ins_switch);
 342         fprintf(file,"    prim. return   : %8d\n",stat_ins_primitive_return);
 343         fprintf(file,"    areturn        : %8d\n",stat_ins_areturn);
 344         fprintf(file,"      (unresolved) : %8d\n",stat_ins_areturn_unresolved);
 345         fprintf(file,"    athrow         : %8d\n",stat_ins_athrow);
 346         fprintf(file,"      (unresolved) : %8d\n",stat_ins_athrow_unresolved);
 347         fprintf(file,"    unchecked      : %8d\n",stat_ins_unchecked);
 348         fprintf(file,"    maythrow       : %8d\n",stat_ins_maythrow);
 349         fprintf(file,"iterations used:\n");
 350         print_freq(file,stat_iterations,STAT_ITERATIONS);
 351         fprintf(file,"basic blocks per method / 10:\n");
 352         print_freq(file,stat_blocks,STAT_BLOCKS);
 353         fprintf(file,"locals:\n");
 354         print_freq(file,stat_locals,STAT_LOCALS);
 355 }
 356
 357 #else
 358
 359 #define TYPECHECK_COUNT(cnt)
 360 #define TYPECHECK_MARK(var)
 361 #define TYPECHECK_COUNTIF(cond,cnt)
 362 #define TYPECHECK_COUNT_FREQ(array,val,limit)
 363 #endif
 364
 365
 366 /****************************************************************************/
 367 /* MACROS FOR THROWING EXCEPTIONS                                           */
 368 /****************************************************************************/
 369
 370 #define TYPECHECK_VERIFYERROR_ret(m,msg,retval)                      \
 371     do {                                                             \
 372         exceptions_throw_verifyerror((m), (msg));                    \
 373         return (retval);                                             \
 374     } while (0)
 375
 376 #define TYPECHECK_VERIFYERROR_main(msg)  TYPECHECK_VERIFYERROR_ret(state.m,(msg),NULL)
 377 #define TYPECHECK_VERIFYERROR_bool(msg)  TYPECHECK_VERIFYERROR_ret(state->m,(msg),false)
 378
 379
 380 /****************************************************************************/
 381 /* MACROS FOR VARIABLE TYPE CHECKING                                        */
 382 /****************************************************************************/
 383
 384 #define TYPECHECK_CHECK_TYPE(i,tp,msg)                               \
 385     do {                                                             \
 386         if (VAR(i)->type != (tp)) {                                  \
 387             exceptions_throw_verifyerror(state->m, (msg));           \
 388             return false;                                            \
 389         }                                                            \
 390     } while (0)
 391
 392 #define TYPECHECK_INT(i)                                             \
 393     TYPECHECK_CHECK_TYPE(i,TYPE_INT,"Expected to find integer value")
 394 #define TYPECHECK_LNG(i)                                             \
 395     TYPECHECK_CHECK_TYPE(i,TYPE_LNG,"Expected to find long value")
 396 #define TYPECHECK_FLT(i)                                             \
 397     TYPECHECK_CHECK_TYPE(i,TYPE_FLT,"Expected to find float value")
 398 #define TYPECHECK_DBL(i)                                             \
 399     TYPECHECK_CHECK_TYPE(i,TYPE_DBL,"Expected to find double value")
 400 #define TYPECHECK_ADR(i)                                             \
 401     TYPECHECK_CHECK_TYPE(i,TYPE_ADR,"Expected to find object value")
 402
 403 #define TYPECHECK_INT_OP(o)  TYPECHECK_INT((o).varindex)
 404 #define TYPECHECK_LNG_OP(o)  TYPECHECK_LNG((o).varindex)
 405 #define TYPECHECK_FLT_OP(o)  TYPECHECK_FLT((o).varindex)
 406 #define TYPECHECK_DBL_OP(o)  TYPECHECK_DBL((o).varindex)
 407 #define TYPECHECK_ADR_OP(o)  TYPECHECK_ADR((o).varindex)
 408
 409
 410 /****************************************************************************/
 411 /* VERIFIER STATE STRUCT                                                    */
 412 /****************************************************************************/
 413
 414 /* verifier_state - This structure keeps the current state of the      */
 415 /* bytecode verifier for passing it between verifier functions.        */
 416
 417 typedef struct verifier_state {
 418     instruction *iptr;               /* pointer to current instruction */
 419     basicblock *bptr;                /* pointer to current basic block */
 420
 421         methodinfo *m;                               /* the current method */
 422         jitdata *jd;                         /* jitdata for current method */
 423         codegendata *cd;                 /* codegendata for current method */
 424
 425         basicblock *basicblocks;
 426         s4 basicblockcount;
 427
 428         s4 numlocals;                         /* number of local variables */
 429         s4 validlocals;                /* number of Java-accessible locals */
 430         s4 *reverselocalmap;
 431
 432         typedescriptor returntype;    /* return type of the current method */
 433
 434         s4 *savedindices;
 435         s4 *savedinvars;                            /* saved invar pointer */
 436
 437         s4 exinvars;
 438
 439     exceptiontable **handlers;            /* active exception handlers */
 440
 441     bool repeat;            /* if true, blocks are iterated over again */
 442     bool initmethod;             /* true if this is an "<init>" method */
 443
 444 #ifdef TYPECHECK_STATISTICS
 445         bool stat_maythrow;          /* at least one instruction may throw */
 446 #endif
 447 } verifier_state;
 448
 449
 450 /****************************************************************************/
 451 /* TYPESTACK MACROS AND FUNCTIONS                                           */
 452 /*                                                                          */
 453 /* These macros and functions act on the 'type stack', which is a shorthand */
 454 /* for the types of the stackslots of the current stack. The type of a      */
 455 /* stack slot is usually described by a TYPE_* constant and -- for TYPE_ADR */
 456 /* -- by the typeinfo of the slot. The only thing that makes the type stack */
 457 /* more complicated are returnAddresses of local subroutines, because a     */
 458 /* single stack slot may contain a set of more than one possible return     */
 459 /* address. This is handled by 'return address sets'. A return address set  */
 460 /* is kept as a linked list dangling off the typeinfo of the stack slot.    */
 461 /****************************************************************************/
 462
 463 /* typecheck_copy_types ********************************************************
 464
 465    Copy the types of the source variables to the destination variables.
 466
 467    IN:
 468            state............current verifier state
 469            srcvars..........array of variable indices to copy
 470            dstvars..........array of the destination variables
 471            n................number of variables to copy
 472
 473    RETURN VALUE:
 474        true.............success
 475            false............an exception has been thrown
 476
 477 *******************************************************************************/
 478
 479 static bool
 480 typecheck_copy_types(verifier_state *state, s4 *srcvars, s4 *dstvars, s4 n)
 481 {
 482         s4 i;
 483         varinfo *sv;
 484         varinfo *dv;
 485         jitdata *jd = state->jd;
 486
 487         for (i=0; i < n; ++i, ++srcvars, ++dstvars) {
 488                 sv = VAR(*srcvars);
 489                 dv = VAR(*dstvars);
 490
 491                 dv->type = sv->type;
 492                 if (dv->type == TYPE_ADR) {
 493                         TYPEINFO_CLONE(sv->typeinfo,dv->typeinfo);
 494                 }
 495         }
 496         return true;
 497 }
 498
 499
 500 /* typecheck_merge_types *******************************************************
 501
 502    Merge the types of the source variables into the destination variables.
 503
 504    IN:
 505        state............current state of the verifier
 506            srcvars..........source variable indices
 507            dstvars..........destination variable indices
 508            n................number of variables
 509
 510    RETURN VALUE:
 511        typecheck_TRUE...the destination variables have been modified
 512            typecheck_FALSE..the destination variables are unchanged
 513            typecheck_FAIL...an exception has been thrown
 514
 515 *******************************************************************************/
 516
 517 static typecheck_result
 518 typecheck_merge_types(verifier_state *state,s4 *srcvars, s4 *dstvars, s4 n)
 519 {
 520         s4 i;
 521         varinfo *sv;
 522         varinfo *dv;
 523         jitdata *jd = state->jd;
 524         typecheck_result r;
 525         bool changed = false;
 526
 527         for (i=0; i < n; ++i, ++srcvars, ++dstvars) {
 528                 sv = VAR(*srcvars);
 529                 dv = VAR(*dstvars);
 530
 531                 if (dv->type != sv->type) {
 532                         exceptions_throw_verifyerror(state->m,"Stack type mismatch");
 533                         return typecheck_FAIL;
 534                 }
 535                 if (dv->type == TYPE_ADR) {
 536                         if (TYPEINFO_IS_PRIMITIVE(dv->typeinfo)) {
 537                                 /* dv has returnAddress type */
 538                                 if (!TYPEINFO_IS_PRIMITIVE(sv->typeinfo)) {
 539                                         exceptions_throw_verifyerror(state->m,"Merging returnAddress with reference");
 540                                         return typecheck_FAIL;
 541                                 }
 542                         }
 543                         else {
 544                                 /* dv has reference type */
 545                                 if (TYPEINFO_IS_PRIMITIVE(sv->typeinfo)) {
 546                                         exceptions_throw_verifyerror(state->m,"Merging reference with returnAddress");
 547                                         return typecheck_FAIL;
 548                                 }
 549                                 r = typeinfo_merge(state->m,&(dv->typeinfo),&(sv->typeinfo));
 550                                 if (r == typecheck_FAIL)
 551                                         return r;
 552                                 changed |= r;
 553                         }
 554                 }
 555         }
 556         return changed;
 557 }
 558
 559
 560 /* typestate_merge *************************************************************
 561
 562    Merge the types of one state into the destination state.
 563
 564    IN:
 565        state............current state of the verifier
 566            dstvars..........indices of the destinations invars
 567            dstlocals........the destinations inlocals
 568            srcvars..........indices of the source's outvars
 569            srclocals........the source locals
 570            n................number of invars (== number of outvars)
 571
 572    RETURN VALUE:
 573        typecheck_TRUE...destination state has been modified
 574            typecheck_FALSE..destination state has not been modified
 575            typecheck_FAIL...an exception has been thrown
 576
 577 *******************************************************************************/
 578
 579 static typecheck_result
 580 typestate_merge(verifier_state *state,
 581                                 s4 *srcvars, varinfo *srclocals,
 582                                 s4 *dstvars, varinfo *dstlocals,
 583                                 s4 n)
 584 {
 585         bool changed = false;
 586         typecheck_result r;
 587
 588         /* The stack is always merged. If there are returnAddresses on
 589          * the stack they are ignored in this step. */
 590
 591         r = typecheck_merge_types(state, srcvars, dstvars, n);
 592         if (r == typecheck_FAIL)
 593                 return r;
 594         changed |= r;
 595
 596         /* merge the locals */
 597
 598         r = typevector_merge(state->m, dstlocals, srclocals, state->numlocals);
 599         if (r == typecheck_FAIL)
 600                 return r;
 601         return changed | r;
 602 }
 603
 604
 605 /* typestate_reach *************************************************************
 606
 607    Reach a destination block and propagate stack and local variable types
 608
 609    IN:
 610        state............current state of the verifier
 611            destblock........destination basic block
 612            srcvars..........variable indices of the outvars to propagate
 613            srclocals........local variables to propagate
 614            n................number of srcvars
 615
 616    OUT:
 617        state->repeat....set to true if the verifier must iterate again
 618                             over the basic blocks
 619
 620    RETURN VALUE:
 621        true.............success
 622            false............an exception has been thrown
 623
 624 *******************************************************************************/
 625
 626 static bool
 627 typestate_reach(verifier_state *state,
 628                                 basicblock *destblock,
 629                                 s4 *srcvars, varinfo *srclocals, s4 n)
 630 {
 631         varinfo *destloc;
 632         bool changed = false;
 633         typecheck_result r;
 634
 635         LOG1("reaching block L%03d",destblock->nr);
 636         TYPECHECK_COUNT(stat_reached);
 637
 638         destloc = destblock->inlocals;
 639
 640         if (destblock->flags == BBTYPECHECK_UNDEF) {
 641                 /* The destblock has never been reached before */
 642
 643                 TYPECHECK_COUNT(stat_copied);
 644                 LOG1("block L%03d reached first time",destblock->nr);
 645
 646                 if (!typecheck_copy_types(state, srcvars, destblock->invars, n))
 647                         return false;
 648                 typevector_copy_inplace(srclocals, destloc, state->numlocals);
 649                 changed = true;
 650         }
 651         else {
 652                 /* The destblock has already been reached before */
 653
 654                 TYPECHECK_COUNT(stat_merged);
 655                 LOG1("block L%03d reached before", destblock->nr);
 656
 657                 r = typestate_merge(state, srcvars, srclocals,
 658                                 destblock->invars, destblock->inlocals, n);
 659                 if (r == typecheck_FAIL)
 660                         return false;
 661                 changed = r;
 662                 TYPECHECK_COUNTIF(changed,stat_merging_changed);
 663         }
 664
 665         if (changed) {
 666                 LOG("changed!");
 667                 destblock->flags = BBTYPECHECK_REACHED;
 668                 if (destblock <= state->bptr) {
 669                         LOG("REPEAT!");
 670                         state->repeat = true;
 671                 }
 672         }
 673         return true;
 674 }
 675
 676
 677 /* typestate_save_invars *******************************************************
 678
 679    Save the invars of the current basic block in the space reserved by
 680    parse.
 681
 682    This function must be called before an instruction modifies a variable
 683    that is an invar of the current block. In such cases the invars of the
 684    block must be saved, and restored at the end of the analysis of this
 685    basic block, so that the invars again reflect the *input* to this basic
 686    block (and do not randomly contain types that appear within the block).
 687
 688    IN:
 689        state............current state of the verifier
 690
 691 *******************************************************************************/
 692
 693 static void
 694 typestate_save_invars(verifier_state *state)
 695 {
 696         s4 i, index;
 697         s4 *pindex;
 698
 699         LOG("saving invars");
 700
 701         if (!state->savedindices) {
 702                 LOG("allocating savedindices buffer");
 703                 pindex = DMNEW(s4, state->m->maxstack);
 704                 state->savedindices = pindex;
 705                 index = state->numlocals + VERIFIER_EXTRA_VARS;
 706                 for (i=0; i<state->m->maxstack; ++i)
 707                         *pindex++ = index++;
 708         }
 709
 710         /* save types */
 711
 712         typecheck_copy_types(state, state->bptr->invars, state->savedindices,
 713                         state->bptr->indepth);
 714
 715         /* set the invars of the block to the saved variables */
 716         /* and remember the original invars                   */
 717
 718         state->savedinvars = state->bptr->invars;
 719         state->bptr->invars = state->savedindices;
 720 }
 721
 722
 723 /* typestate_restore_invars  ***************************************************
 724
 725    Restore the invars of the current basic block that have been previously
 726    saved by `typestate_save_invars`.
 727
 728    IN:
 729        state............current state of the verifier
 730
 731 *******************************************************************************/
 732
 733 static void
 734 typestate_restore_invars(verifier_state *state)
 735 {
 736         TYPECHECK_COUNT(stat_savedstack);
 737         LOG("restoring saved invars");
 738
 739         /* restore the invars pointer */
 740
 741         state->bptr->invars = state->savedinvars;
 742
 743         /* copy the types back */
 744
 745         typecheck_copy_types(state, state->savedindices, state->bptr->invars,
 746                         state->bptr->indepth);
 747
 748         /* mark that there are no saved invars currently */
 749
 750         state->savedinvars = NULL;
 751 }
 752
 753
 754 /****************************************************************************/
 755 /* MISC MACROS                                                              */
 756 /****************************************************************************/
 757
 758 #define COPYTYPE(source,dest)                                        \
 759     {if (VAROP(source)->type == TYPE_ADR)                            \
 760             TYPEINFO_COPY(VAROP(source)->typeinfo,VAROP(dest)->typeinfo);}
 761
 762 #define ISBUILTIN(v)   (bte->fp == (functionptr) (v))
 763
 764
 765 /* verify_invocation ***********************************************************
 766
 767    Verify an ICMD_INVOKE* instruction.
 768
 769    IN:
 770        state............the current state of the verifier
 771
 772    RETURN VALUE:
 773        true.............successful verification,
 774            false............an exception has been thrown.
 775
 776 *******************************************************************************/
 777
 778 static bool
 779 verify_invocation(verifier_state *state)
 780 {
 781         jitdata *jd;
 782         varinfo *dv;
 783
 784         jd = state->jd;
 785         dv = VAROP(state->iptr->dst);
 786
 787 #include <typecheck-invoke.inc>
 788
 789         return true;
 790 }
 791
 792
 793 /* verify_builtin **************************************************************
 794
 795    Verify the call of a builtin method.
 796
 797    IN:
 798        state............the current state of the verifier
 799
 800    RETURN VALUE:
 801        true.............successful verification,
 802            false............an exception has been thrown.
 803
 804 *******************************************************************************/
 805
 806 static bool
 807 verify_builtin(verifier_state *state)
 808 {
 809         varinfo *dv;
 810         jitdata *jd;
 811
 812         jd = state->jd;
 813         dv = VAROP(state->iptr->dst);
 814
 815 #include <typecheck-builtins.inc>
 816
 817         return true;
 818 }
 819
 820
 821 /* verify_multianewarray *******************************************************
 822
 823    Verify a MULTIANEWARRAY instruction.
 824
 825    IN:
 826        state............the current state of the verifier
 827
 828    RETURN VALUE:
 829        true.............successful verification,
 830            false............an exception has been thrown.
 831
 832 *******************************************************************************/
 833
 834 static bool
 835 verify_multianewarray(verifier_state *state)
 836 {
 837         classinfo *arrayclass;
 838         arraydescriptor *desc;
 839         s4 i;
 840         jitdata *jd = state->jd;
 841
 842         /* check the array lengths on the stack */
 843         i = state->iptr->s1.argcount;
 844         if (i < 1)
 845                 TYPECHECK_VERIFYERROR_bool("Illegal dimension argument");
 846
 847         while (i--) {
 848                 TYPECHECK_INT(state->iptr->sx.s23.s2.args[i]);
 849         }
 850
 851         /* check array descriptor */
 852         if (INSTRUCTION_IS_RESOLVED(state->iptr)) {
 853                 /* the array class reference has already been resolved */
 854                 arrayclass = state->iptr->sx.s23.s3.c.cls;
 855                 if (!arrayclass)
 856                         TYPECHECK_VERIFYERROR_bool("MULTIANEWARRAY with unlinked class");
 857                 if ((desc = arrayclass->vftbl->arraydesc) == NULL)
 858                         TYPECHECK_VERIFYERROR_bool("MULTIANEWARRAY with non-array class");
 859                 if (desc->dimension < state->iptr->s1.argcount)
 860                         TYPECHECK_VERIFYERROR_bool("MULTIANEWARRAY dimension to high");
 861
 862                 /* set the array type of the result */
 863                 typeinfo_init_classinfo(&(VAROP(state->iptr->dst)->typeinfo), arrayclass);
 864         }
 865         else {
 866                 const char *p;
 867                 constant_classref *cr;
 868
 869                 /* the array class reference is still unresolved */
 870                 /* check that the reference indicates an array class of correct dimension */
 871                 cr = state->iptr->sx.s23.s3.c.ref;
 872                 i = 0;
 873                 p = cr->name->text;
 874                 while (p[i] == '[')
 875                         i++;
 876                 /* { the dimension of the array class == i } */
 877                 if (i < 1)
 878                         TYPECHECK_VERIFYERROR_bool("MULTIANEWARRAY with non-array class");
 879                 if (i < state->iptr->s1.argcount)
 880                         TYPECHECK_VERIFYERROR_bool("MULTIANEWARRAY dimension to high");
 881
 882                 /* set the array type of the result */
 883                 if (!typeinfo_init_class(&(VAROP(state->iptr->dst)->typeinfo),CLASSREF_OR_CLASSINFO(cr)))
 884                         return false;
 885         }
 886
 887         /* set return type */
 888
 889         VAROP(state->iptr->dst)->type = TYPE_ADR;
 890
 891         /* everything ok */
 892         return true;
 893 }
 894
 895
 896 /* typecheck_invalidate_locals *************************************************
 897
 898    Invalidate locals that are overwritten by writing to the given local.
 899
 900    IN:
 901        state............the current state of the verifier
 902            index............the index of the local that is written
 903            twoword..........true, if a two-word type is written
 904
 905 *******************************************************************************/
 906
 907 static void typecheck_invalidate_locals(verifier_state *state, s4 index, bool twoword)
 908 {
 909         s4 i;
 910         s4 t;
 911         s4 mapped;
 912         jitdata *jd = state->jd;
 913         s4 *localmap = jd->local_map;
 914         varinfo *vars = jd->var;
 915
 916         i = state->reverselocalmap[index];
 917
 918         /* invalidate locals of two-word type at index i-1 */
 919
 920         if (i > 0) {
 921                 localmap += 5 * (i-1);
 922                 for (t=0; t<5; ++t) {
 923                         mapped = *localmap++;
 924                         if (mapped >= 0 && IS_2_WORD_TYPE(vars[mapped].type)) {
 925                                 LOG1("invalidate local %d", mapped);
 926                                 vars[mapped].type = TYPE_VOID;
 927                         }
 928                 }
 929         }
 930         else {
 931                 localmap += 5 * i;
 932         }
 933
 934         /* invalidate locals at index i */
 935
 936         for (t=0; t<5; ++t) {
 937                 mapped = *localmap++;
 938                 if (mapped >= 0) {
 939                         LOG1("invalidate local %d", mapped);
 940                         vars[mapped].type = TYPE_VOID;
 941                 }
 942         }
 943
 944         /* if a two-word type is written, invalidate locals at index i+1 */
 945
 946         if (twoword) {
 947                 for (t=0; t<5; ++t) {
 948                         mapped = *localmap++;
 949                         if (mapped >= 0) {
 950                                 LOG1("invalidate local %d", mapped);
 951                                 vars[mapped].type = TYPE_VOID;
 952                         }
 953                 }
 954         }
 955 }
 956
 957
 958 /* verify_basic_block **********************************************************
 959
 960    Perform bytecode verification of a basic block.
 961
 962    IN:
 963        state............the current state of the verifier
 964
 965    RETURN VALUE:
 966        true.............successful verification,
 967            false............an exception has been thrown.
 968
 969 *******************************************************************************/
 970
 971 static bool
 972 verify_basic_block(verifier_state *state)
 973 {
 974     int opcode;                                      /* current opcode */
 975     int len;                        /* for counting instructions, etc. */
 976     bool superblockend;        /* true if no fallthrough to next block */
 977         instruction *iptr;                      /* the current instruction */
 978     basicblock *tbptr;                   /* temporary for target block */
 979     bool maythrow;               /* true if this instruction may throw */
 980         unresolved_field *uf;                        /* for field accesses */
 981         constant_FMIref *fieldref;                   /* for field accesses */
 982         s4 i;
 983         typecheck_result r;
 984         resolve_result_t result;
 985         branch_target_t *table;
 986         lookup_target_t *lookup;
 987         jitdata *jd = state->jd;
 988         varinfo *dv;
 989         exceptiontable *ex;
 990
 991         LOGSTR1("\n---- BLOCK %04d ------------------------------------------------\n",state->bptr->nr);
 992         LOGFLUSH;
 993         DOLOG(show_basicblock(jd, state->bptr, SHOW_STACK));
 994
 995         superblockend = false;
 996         state->bptr->flags = BBFINISHED;
 997
 998         /* prevent compiler warnings */
 999
1000         dv = NULL;
1001
1002         /* determine the active exception handlers for this block */
1003         /* XXX could use a faster algorithm with sorted lists or  */
1004         /* something?                                             */
1005         len = 0;
1006         for (ex = state->cd->exceptiontable; ex ; ex = ex->down) {
1007                 if ((ex->start->nr <= state->bptr->nr) && (ex->end->nr > state->bptr->nr)) {
1008                         LOG1("active handler L%03d", ex->handler->nr);
1009                         state->handlers[len++] = ex;
1010                 }
1011         }
1012         state->handlers[len] = NULL;
1013
1014         /* init variable types at the start of this block */
1015         typevector_copy_inplace(state->bptr->inlocals, jd->var, state->numlocals);
1016
1017         DOLOG(typecheck_print_vararray(stdout, jd, state->bptr->invars,
1018                                 state->bptr->indepth));
1019         DOLOG(typevector_print(stdout, jd->var, state->numlocals));
1020         LOGNL; LOGFLUSH;
1021
1022         /* loop over the instructions */
1023         len = state->bptr->icount;
1024         state->iptr = state->bptr->iinstr;
1025         while (--len >= 0)  {
1026                 TYPECHECK_COUNT(stat_ins);
1027
1028                 iptr = state->iptr;
1029
1030                 DOLOG(typevector_print(stdout, jd->var, state->numlocals));
1031                 LOGNL; LOGFLUSH;
1032                 DOLOG(show_icmd(jd, state->iptr, false, SHOW_STACK)); LOGNL; LOGFLUSH;
1033
1034                 opcode = iptr->opc;
1035                 dv = VAROP(iptr->dst);
1036                 maythrow = false;
1037
1038                 switch (opcode) {
1039
1040                         /****************************************/
1041                         /* STACK MANIPULATIONS                  */
1042
1043                         /* We just need to copy the typeinfo */
1044                         /* for slots containing addresses.   */
1045
1046                         case ICMD_MOVE:
1047                         case ICMD_COPY:
1048                                 TYPECHECK_COUNT(stat_ins_stack);
1049                                 COPYTYPE(iptr->s1, iptr->dst);
1050                                 dv->type = VAROP(iptr->s1)->type;
1051                                 break;
1052
1053                                 /****************************************/
1054                                 /* PRIMITIVE VARIABLE ACCESS            */
1055
1056                         case ICMD_ILOAD: if (!typevector_checktype(jd->var,state->iptr->s1.varindex,TYPE_INT))
1057                                                                  TYPECHECK_VERIFYERROR_bool("Local variable type mismatch");
1058                                                          dv->type = TYPE_INT;
1059                                                          break;
1060                         case ICMD_IINC:  if (!typevector_checktype(jd->var,state->iptr->s1.varindex,TYPE_INT))
1061                                                                  TYPECHECK_VERIFYERROR_bool("Local variable type mismatch");
1062                                                          dv->type = TYPE_INT;
1063                                                          break;
1064                         case ICMD_FLOAD: if (!typevector_checktype(jd->var,state->iptr->s1.varindex,TYPE_FLT))
1065                                                                  TYPECHECK_VERIFYERROR_bool("Local variable type mismatch");
1066                                                          dv->type = TYPE_FLT;
1067                                                          break;
1068                         case ICMD_LLOAD: if (!typevector_checktype(jd->var,state->iptr->s1.varindex,TYPE_LNG))
1069                                                                  TYPECHECK_VERIFYERROR_bool("Local variable type mismatch");
1070                                                          dv->type = TYPE_LNG;
1071                                                          break;
1072                         case ICMD_DLOAD: if (!typevector_checktype(jd->var,state->iptr->s1.varindex,TYPE_DBL))
1073                                                                  TYPECHECK_VERIFYERROR_bool("Local variable type mismatch");
1074                                                          dv->type = TYPE_DBL;
1075                                                          break;
1076
1077                         case ICMD_ISTORE:
1078                                                          typecheck_invalidate_locals(state, state->iptr->dst.varindex, false);
1079                                                          typevector_store(jd->var,state->iptr->dst.varindex,TYPE_INT,NULL);
1080                                                          break;
1081                         case ICMD_FSTORE:
1082                                                          typecheck_invalidate_locals(state, state->iptr->dst.varindex, false);
1083                                                          typevector_store(jd->var,state->iptr->dst.varindex,TYPE_FLT,NULL);
1084                                                          break;
1085                         case ICMD_LSTORE:
1086                                                          typecheck_invalidate_locals(state, state->iptr->dst.varindex, true);
1087                                                          typevector_store(jd->var,state->iptr->dst.varindex,TYPE_LNG,NULL);
1088                                                          break;
1089                         case ICMD_DSTORE:
1090                                                          typecheck_invalidate_locals(state, state->iptr->dst.varindex, true);
1091                                                          typevector_store(jd->var,state->iptr->dst.varindex,TYPE_DBL,NULL);
1092                                                          break;
1093
1094                                 /****************************************/
1095                                 /* LOADING ADDRESS FROM VARIABLE        */
1096
1097                         case ICMD_ALOAD:
1098                                 TYPECHECK_COUNT(stat_ins_aload);
1099
1100                                 /* loading a returnAddress is not allowed */
1101                                 if (!TYPEDESC_IS_REFERENCE(*VAROP(state->iptr->s1))) {
1102                                         TYPECHECK_VERIFYERROR_bool("illegal instruction: ALOAD loading non-reference");
1103                                 }
1104                                 TYPEINFO_COPY(VAROP(state->iptr->s1)->typeinfo,dv->typeinfo);
1105                                 dv->type = TYPE_ADR;
1106                                 break;
1107
1108                                 /****************************************/
1109                                 /* STORING ADDRESS TO VARIABLE          */
1110
1111                         case ICMD_ASTORE:
1112                                 typecheck_invalidate_locals(state, state->iptr->dst.varindex, false);
1113
1114                                 if (TYPEINFO_IS_PRIMITIVE(VAROP(state->iptr->s1)->typeinfo)) {
1115                                         typevector_store_retaddr(jd->var,state->iptr->dst.varindex,&(VAROP(state->iptr->s1)->typeinfo));
1116                                 }
1117                                 else {
1118                                         typevector_store(jd->var,state->iptr->dst.varindex,TYPE_ADR,
1119                                                         &(VAROP(state->iptr->s1)->typeinfo));
1120                                 }
1121                                 break;
1122
1123                                 /****************************************/
1124                                 /* LOADING ADDRESS FROM ARRAY           */
1125
1126                         case ICMD_AALOAD:
1127                                 if (!TYPEINFO_MAYBE_ARRAY_OF_REFS(VAROP(state->iptr->s1)->typeinfo))
1128                                         TYPECHECK_VERIFYERROR_bool("illegal instruction: AALOAD on non-reference array");
1129
1130                                 if (!typeinfo_init_component(&VAROP(state->iptr->s1)->typeinfo,&dv->typeinfo))
1131                                         return false;
1132                                 dv->type = TYPE_ADR;
1133                                 maythrow = true;
1134                                 break;
1135
1136                                 /****************************************/
1137                                 /* FIELD ACCESS                         */
1138
1139                         case ICMD_PUTFIELD:
1140                         case ICMD_PUTSTATIC:
1141                         case ICMD_PUTFIELDCONST:
1142                         case ICMD_PUTSTATICCONST:
1143                         case ICMD_GETFIELD:
1144                         case ICMD_GETSTATIC:
1145
1146 #include <typecheck-fields.inc>
1147
1148                                 maythrow = true;
1149                                 break;
1150
1151                                 /****************************************/
1152                                 /* PRIMITIVE ARRAY ACCESS               */
1153
1154                         case ICMD_ARRAYLENGTH:
1155                                 if (!TYPEINFO_MAYBE_ARRAY(VAROP(state->iptr->s1)->typeinfo)
1156                                                 && VAROP(state->iptr->s1)->typeinfo.typeclass.cls != pseudo_class_Arraystub)
1157                                         TYPECHECK_VERIFYERROR_bool("illegal instruction: ARRAYLENGTH on non-array");
1158                                 dv->type = TYPE_INT;
1159                                 maythrow = true;
1160                                 break;
1161
1162                         case ICMD_BALOAD:
1163                                 if (!TYPEINFO_MAYBE_PRIMITIVE_ARRAY(VAROP(state->iptr->s1)->typeinfo,ARRAYTYPE_BOOLEAN)
1164                                                 && !TYPEINFO_MAYBE_PRIMITIVE_ARRAY(VAROP(state->iptr->s1)->typeinfo,ARRAYTYPE_BYTE))
1165                                         TYPECHECK_VERIFYERROR_bool("Array type mismatch");
1166                                 dv->type = TYPE_INT;
1167                                 maythrow = true;
1168                                 break;
1169                         case ICMD_CALOAD:
1170                                 if (!TYPEINFO_MAYBE_PRIMITIVE_ARRAY(VAROP(state->iptr->s1)->typeinfo,ARRAYTYPE_CHAR))
1171                                         TYPECHECK_VERIFYERROR_bool("Array type mismatch");
1172                                 dv->type = TYPE_INT;
1173                                 maythrow = true;
1174                                 break;
1175                         case ICMD_DALOAD:
1176                                 if (!TYPEINFO_MAYBE_PRIMITIVE_ARRAY(VAROP(state->iptr->s1)->typeinfo,ARRAYTYPE_DOUBLE))
1177                                         TYPECHECK_VERIFYERROR_bool("Array type mismatch");
1178                                 dv->type = TYPE_DBL;
1179                                 maythrow = true;
1180                                 break;
1181                         case ICMD_FALOAD:
1182                                 if (!TYPEINFO_MAYBE_PRIMITIVE_ARRAY(VAROP(state->iptr->s1)->typeinfo,ARRAYTYPE_FLOAT))
1183                                         TYPECHECK_VERIFYERROR_bool("Array type mismatch");
1184                                 dv->type = TYPE_FLT;
1185                                 maythrow = true;
1186                                 break;
1187                         case ICMD_IALOAD:
1188                                 if (!TYPEINFO_MAYBE_PRIMITIVE_ARRAY(VAROP(state->iptr->s1)->typeinfo,ARRAYTYPE_INT))
1189                                         TYPECHECK_VERIFYERROR_bool("Array type mismatch");
1190                                 dv->type = TYPE_INT;
1191                                 maythrow = true;
1192                                 break;
1193                         case ICMD_SALOAD:
1194                                 if (!TYPEINFO_MAYBE_PRIMITIVE_ARRAY(VAROP(state->iptr->s1)->typeinfo,ARRAYTYPE_SHORT))
1195                                         TYPECHECK_VERIFYERROR_bool("Array type mismatch");
1196                                 dv->type = TYPE_INT;
1197                                 maythrow = true;
1198                                 break;
1199                         case ICMD_LALOAD:
1200                                 if (!TYPEINFO_MAYBE_PRIMITIVE_ARRAY(VAROP(state->iptr->s1)->typeinfo,ARRAYTYPE_LONG))
1201                                         TYPECHECK_VERIFYERROR_bool("Array type mismatch");
1202                                 dv->type = TYPE_LNG;
1203                                 maythrow = true;
1204                                 break;
1205
1206                         case ICMD_BASTORE:
1207                                 if (!TYPEINFO_MAYBE_PRIMITIVE_ARRAY(VAROP(state->iptr->s1)->typeinfo,ARRAYTYPE_BOOLEAN)
1208                                                 && !TYPEINFO_MAYBE_PRIMITIVE_ARRAY(VAROP(state->iptr->s1)->typeinfo,ARRAYTYPE_BYTE))
1209                                         TYPECHECK_VERIFYERROR_bool("Array type mismatch");
1210                                 maythrow = true;
1211                                 break;
1212                         case ICMD_CASTORE:
1213                                 if (!TYPEINFO_MAYBE_PRIMITIVE_ARRAY(VAROP(state->iptr->s1)->typeinfo,ARRAYTYPE_CHAR))
1214                                         TYPECHECK_VERIFYERROR_bool("Array type mismatch");
1215                                 maythrow = true;
1216                                 break;
1217                         case ICMD_DASTORE:
1218                                 if (!TYPEINFO_MAYBE_PRIMITIVE_ARRAY(VAROP(state->iptr->s1)->typeinfo,ARRAYTYPE_DOUBLE))
1219                                         TYPECHECK_VERIFYERROR_bool("Array type mismatch");
1220                                 maythrow = true;
1221                                 break;
1222                         case ICMD_FASTORE:
1223                                 if (!TYPEINFO_MAYBE_PRIMITIVE_ARRAY(VAROP(state->iptr->s1)->typeinfo,ARRAYTYPE_FLOAT))
1224                                         TYPECHECK_VERIFYERROR_bool("Array type mismatch");
1225                                 maythrow = true;
1226                                 break;
1227                         case ICMD_IASTORE:
1228                                 if (!TYPEINFO_MAYBE_PRIMITIVE_ARRAY(VAROP(state->iptr->s1)->typeinfo,ARRAYTYPE_INT))
1229                                         TYPECHECK_VERIFYERROR_bool("Array type mismatch");
1230                                 maythrow = true;
1231                                 break;
1232                         case ICMD_SASTORE:
1233                                 if (!TYPEINFO_MAYBE_PRIMITIVE_ARRAY(VAROP(state->iptr->s1)->typeinfo,ARRAYTYPE_SHORT))
1234                                         TYPECHECK_VERIFYERROR_bool("Array type mismatch");
1235                                 maythrow = true;
1236                                 break;
1237                         case ICMD_LASTORE:
1238                                 if (!TYPEINFO_MAYBE_PRIMITIVE_ARRAY(VAROP(state->iptr->s1)->typeinfo,ARRAYTYPE_LONG))
1239                                         TYPECHECK_VERIFYERROR_bool("Array type mismatch");
1240                                 maythrow = true;
1241                                 break;
1242
1243                         case ICMD_AASTORE:
1244                                 /* we just check the basic input types and that the           */
1245                                 /* destination is an array of references. Assignability to    */
1246                                 /* the actual array must be checked at runtime, each time the */
1247                                 /* instruction is performed. (See builtin_canstore.)          */
1248                                 TYPECHECK_ADR_OP(state->iptr->sx.s23.s3);
1249                                 TYPECHECK_INT_OP(state->iptr->sx.s23.s2);
1250                                 TYPECHECK_ADR_OP(state->iptr->s1);
1251                                 if (!TYPEINFO_MAYBE_ARRAY_OF_REFS(VAROP(state->iptr->s1)->typeinfo))
1252                                         TYPECHECK_VERIFYERROR_bool("illegal instruction: AASTORE to non-reference array");
1253                                 maythrow = true;
1254                                 break;
1255
1256                         case ICMD_IASTORECONST:
1257                                 if (!TYPEINFO_MAYBE_PRIMITIVE_ARRAY(VAROP(state->iptr->s1)->typeinfo, ARRAYTYPE_INT))
1258                                         TYPECHECK_VERIFYERROR_bool("Array type mismatch");
1259                                 maythrow = true;
1260                                 break;
1261
1262                         case ICMD_LASTORECONST:
1263                                 if (!TYPEINFO_MAYBE_PRIMITIVE_ARRAY(VAROP(state->iptr->s1)->typeinfo, ARRAYTYPE_LONG))
1264                                         TYPECHECK_VERIFYERROR_bool("Array type mismatch");
1265                                 maythrow = true;
1266                                 break;
1267
1268                         case ICMD_BASTORECONST:
1269                                 if (!TYPEINFO_MAYBE_PRIMITIVE_ARRAY(VAROP(state->iptr->s1)->typeinfo, ARRAYTYPE_BOOLEAN)
1270                                                 && !TYPEINFO_MAYBE_PRIMITIVE_ARRAY(VAROP(state->iptr->s1)->typeinfo, ARRAYTYPE_BYTE))
1271                                         TYPECHECK_VERIFYERROR_bool("Array type mismatch");
1272                                 maythrow = true;
1273                                 break;
1274
1275                         case ICMD_CASTORECONST:
1276                                 if (!TYPEINFO_MAYBE_PRIMITIVE_ARRAY(VAROP(state->iptr->s1)->typeinfo, ARRAYTYPE_CHAR))
1277                                         TYPECHECK_VERIFYERROR_bool("Array type mismatch");
1278                                 maythrow = true;
1279                                 break;
1280
1281                         case ICMD_SASTORECONST:
1282                                 if (!TYPEINFO_MAYBE_PRIMITIVE_ARRAY(VAROP(state->iptr->s1)->typeinfo, ARRAYTYPE_SHORT))
1283                                         TYPECHECK_VERIFYERROR_bool("Array type mismatch");
1284                                 maythrow = true;
1285                                 break;
1286
1287                                 /****************************************/
1288                                 /* ADDRESS CONSTANTS                    */
1289
1290                         case ICMD_ACONST:
1291                                 if (state->iptr->flags.bits & INS_FLAG_CLASS) {
1292                                         /* a java.lang.Class reference */
1293                                         TYPEINFO_INIT_JAVA_LANG_CLASS(dv->typeinfo,state->iptr->sx.val.c);
1294                                 }
1295                                 else {
1296                                         if (state->iptr->sx.val.anyptr == NULL)
1297                                                 TYPEINFO_INIT_NULLTYPE(dv->typeinfo);
1298                                         else {
1299                                                 /* string constant (or constant for builtin function) */
1300                                                 typeinfo_init_classinfo(&(dv->typeinfo),class_java_lang_String);
1301                                         }
1302                                 }
1303                                 dv->type = TYPE_ADR;
1304                                 break;
1305
1306                                 /****************************************/
1307                                 /* CHECKCAST AND INSTANCEOF             */
1308
1309                         case ICMD_CHECKCAST:
1310                                 TYPECHECK_ADR_OP(state->iptr->s1);
1311                                 /* returnAddress is not allowed */
1312                                 if (!TYPEINFO_IS_REFERENCE(VAROP(state->iptr->s1)->typeinfo))
1313                                         TYPECHECK_VERIFYERROR_bool("Illegal instruction: CHECKCAST on non-reference");
1314
1315                                 if (!typeinfo_init_class(&(dv->typeinfo),state->iptr->sx.s23.s3.c))
1316                                                 return false;
1317                                 dv->type = TYPE_ADR;
1318                                 maythrow = true;
1319                                 break;
1320
1321                         case ICMD_INSTANCEOF:
1322                                 TYPECHECK_ADR_OP(state->iptr->s1);
1323                                 /* returnAddress is not allowed */
1324                                 if (!TYPEINFO_IS_REFERENCE(VAROP(state->iptr->s1)->typeinfo))
1325                                         TYPECHECK_VERIFYERROR_bool("Illegal instruction: INSTANCEOF on non-reference");
1326                                 dv->type = TYPE_INT;
1327                                 break;
1328
1329                                 /****************************************/
1330                                 /* BRANCH INSTRUCTIONS                  */
1331
1332                         case ICMD_INLINE_GOTO:
1333                                 COPYTYPE(state->iptr->s1,state->iptr->dst);
1334                                 /* FALLTHROUGH! */
1335                         case ICMD_GOTO:
1336                                 superblockend = true;
1337                                 /* FALLTHROUGH! */
1338                         case ICMD_IFNULL:
1339                         case ICMD_IFNONNULL:
1340                         case ICMD_IFEQ:
1341                         case ICMD_IFNE:
1342                         case ICMD_IFLT:
1343                         case ICMD_IFGE:
1344                         case ICMD_IFGT:
1345                         case ICMD_IFLE:
1346                         case ICMD_IF_ICMPEQ:
1347                         case ICMD_IF_ICMPNE:
1348                         case ICMD_IF_ICMPLT:
1349                         case ICMD_IF_ICMPGE:
1350                         case ICMD_IF_ICMPGT:
1351                         case ICMD_IF_ICMPLE:
1352                         case ICMD_IF_ACMPEQ:
1353                         case ICMD_IF_ACMPNE:
1354
1355                         case ICMD_IF_LEQ:
1356                         case ICMD_IF_LNE:
1357                         case ICMD_IF_LLT:
1358                         case ICMD_IF_LGE:
1359                         case ICMD_IF_LGT:
1360                         case ICMD_IF_LLE:
1361
1362                         case ICMD_IF_LCMPEQ:
1363                         case ICMD_IF_LCMPNE:
1364                         case ICMD_IF_LCMPLT:
1365                         case ICMD_IF_LCMPGE:
1366                         case ICMD_IF_LCMPGT:
1367                         case ICMD_IF_LCMPLE:
1368
1369                         case ICMD_IF_FCMPEQ:
1370                         case ICMD_IF_FCMPNE:
1371
1372                         case ICMD_IF_FCMPL_LT:
1373                         case ICMD_IF_FCMPL_GE:
1374                         case ICMD_IF_FCMPL_GT:
1375                         case ICMD_IF_FCMPL_LE:
1376
1377                         case ICMD_IF_FCMPG_LT:
1378                         case ICMD_IF_FCMPG_GE:
1379                         case ICMD_IF_FCMPG_GT:
1380                         case ICMD_IF_FCMPG_LE:
1381
1382                         case ICMD_IF_DCMPEQ:
1383                         case ICMD_IF_DCMPNE:
1384
1385                         case ICMD_IF_DCMPL_LT:
1386                         case ICMD_IF_DCMPL_GE:
1387                         case ICMD_IF_DCMPL_GT:
1388                         case ICMD_IF_DCMPL_LE:
1389
1390                         case ICMD_IF_DCMPG_LT:
1391                         case ICMD_IF_DCMPG_GE:
1392                         case ICMD_IF_DCMPG_GT:
1393                         case ICMD_IF_DCMPG_LE:
1394                                 TYPECHECK_COUNT(stat_ins_branch);
1395
1396                                 /* propagate stack and variables to the target block */
1397                                 if (!typestate_reach(state, state->iptr->dst.block,
1398                                                                          state->bptr->outvars, jd->var,
1399                                                                          state->bptr->outdepth))
1400                                         return false;
1401                                 break;
1402
1403                                 /****************************************/
1404                                 /* SWITCHES                             */
1405
1406                         case ICMD_TABLESWITCH:
1407                                 TYPECHECK_COUNT(stat_ins_switch);
1408
1409                                 table = iptr->dst.table;
1410                                 i = iptr->sx.s23.s3.tablehigh
1411                                         - iptr->sx.s23.s2.tablelow + 1 + 1; /* plus default */
1412
1413                                 while (--i >= 0) {
1414                                         tbptr = (table++)->block;
1415                                         LOG2("target %d is block %04d",i,tbptr->nr);
1416                                         if (!typestate_reach(state, tbptr, state->bptr->outvars,
1417                                                                                  jd->var, state->bptr->outdepth))
1418                                                 return false;
1419                                 }
1420
1421                                 LOG("switch done");
1422                                 superblockend = true;
1423                                 break;
1424
1425                         case ICMD_LOOKUPSWITCH:
1426                                 TYPECHECK_COUNT(stat_ins_switch);
1427
1428                                 lookup = iptr->dst.lookup;
1429                                 i = iptr->sx.s23.s2.lookupcount;
1430
1431                                 if (!typestate_reach(state,iptr->sx.s23.s3.lookupdefault.block,
1432                                                                          state->bptr->outvars, jd->var,
1433                                                                          state->bptr->outdepth))
1434                                         return false;
1435
1436                                 while (--i >= 0) {
1437                                         tbptr = (lookup++)->target.block;
1438                                         LOG2("target %d is block %04d",i,tbptr->nr);
1439                                         if (!typestate_reach(state, tbptr, state->bptr->outvars,
1440                                                                 jd->var, state->bptr->outdepth))
1441                                                 return false;
1442                                 }
1443
1444                                 LOG("switch done");
1445                                 superblockend = true;
1446                                 break;
1447
1448
1449                                 /****************************************/
1450                                 /* ADDRESS RETURNS AND THROW            */
1451
1452                         case ICMD_ATHROW:
1453                                 TYPECHECK_COUNT(stat_ins_athrow);
1454                                 r = typeinfo_is_assignable_to_class(&VAROP(state->iptr->s1)->typeinfo,
1455                                                 CLASSREF_OR_CLASSINFO(class_java_lang_Throwable));
1456                                 if (r == typecheck_FALSE)
1457                                         TYPECHECK_VERIFYERROR_bool("illegal instruction: ATHROW on non-Throwable");
1458                                 if (r == typecheck_FAIL)
1459                                         return false;
1460                                 if (r == typecheck_MAYBE) {
1461                                         /* the check has to be postponed. we need a patcher */
1462                                         TYPECHECK_COUNT(stat_ins_athrow_unresolved);
1463                                         iptr->sx.s23.s2.uc = create_unresolved_class(
1464                                                         state->m,
1465                                                         /* XXX make this more efficient, use class_java_lang_Throwable
1466                                                          * directly */
1467                                                         class_get_classref(state->m->class,utf_java_lang_Throwable),
1468                                                         &VAROP(state->iptr->s1)->typeinfo);
1469                                         iptr->flags.bits |= INS_FLAG_UNRESOLVED;
1470                                 }
1471                                 superblockend = true;
1472                                 maythrow = true;
1473                                 break;
1474
1475                         case ICMD_ARETURN:
1476                                 TYPECHECK_COUNT(stat_ins_areturn);
1477                                 if (!TYPEINFO_IS_REFERENCE(VAROP(state->iptr->s1)->typeinfo))
1478                                         TYPECHECK_VERIFYERROR_bool("illegal instruction: ARETURN on non-reference");
1479
1480                                 if (state->returntype.type != TYPE_ADR
1481                                                 || (r = typeinfo_is_assignable(&VAROP(state->iptr->s1)->typeinfo,&(state->returntype.typeinfo)))
1482                                                                 == typecheck_FALSE)
1483                                         TYPECHECK_VERIFYERROR_bool("Return type mismatch");
1484                                 if (r == typecheck_FAIL)
1485                                         return false;
1486                                 if (r == typecheck_MAYBE) {
1487                                         /* the check has to be postponed, we need a patcher */
1488                                         TYPECHECK_COUNT(stat_ins_areturn_unresolved);
1489                                         iptr->sx.s23.s2.uc = create_unresolved_class(
1490                                                         state->m,
1491                                                         state->m->parseddesc->returntype.classref,
1492                                                         &VAROP(state->iptr->s1)->typeinfo);
1493                                         iptr->flags.bits |= INS_FLAG_UNRESOLVED;
1494                                 }
1495                                 goto return_tail;
1496
1497                                 /****************************************/
1498                                 /* PRIMITIVE RETURNS                    */
1499
1500                         case ICMD_IRETURN:
1501                                 if (state->returntype.type != TYPE_INT) TYPECHECK_VERIFYERROR_bool("Return type mismatch");
1502                                 goto return_tail;
1503
1504                         case ICMD_LRETURN:
1505                                 if (state->returntype.type != TYPE_LNG) TYPECHECK_VERIFYERROR_bool("Return type mismatch");
1506                                 goto return_tail;
1507
1508                         case ICMD_FRETURN:
1509                                 if (state->returntype.type != TYPE_FLT) TYPECHECK_VERIFYERROR_bool("Return type mismatch");
1510                                 goto return_tail;
1511
1512                         case ICMD_DRETURN:
1513                                 if (state->returntype.type != TYPE_DBL) TYPECHECK_VERIFYERROR_bool("Return type mismatch");
1514                                 goto return_tail;
1515
1516                         case ICMD_RETURN:
1517                                 if (state->returntype.type != TYPE_VOID) TYPECHECK_VERIFYERROR_bool("Return type mismatch");
1518 return_tail:
1519                                 TYPECHECK_COUNT(stat_ins_primitive_return);
1520
1521                                 if (state->initmethod && state->m->class != class_java_lang_Object) {
1522                                         /* Check if the 'this' instance has been initialized. */
1523                                         LOG("Checking <init> marker");
1524                                         if (!typevector_checktype(jd->var,state->numlocals-1,TYPE_INT))
1525                                                 TYPECHECK_VERIFYERROR_bool("<init> method does not initialize 'this'");
1526                                 }
1527
1528                                 superblockend = true;
1529                                 maythrow = true;
1530                                 break;
1531
1532                                 /****************************************/
1533                                 /* SUBROUTINE INSTRUCTIONS              */
1534
1535                         case ICMD_JSR:
1536                                 LOG("jsr");
1537
1538                                 tbptr = state->iptr->sx.s23.s3.jsrtarget.block;
1539                                 TYPEINFO_INIT_RETURNADDRESS(dv->typeinfo, state->bptr->next);
1540                                 if (!typestate_reach(state, tbptr, state->bptr->outvars, jd->var,
1541                                                         state->bptr->outdepth))
1542                                         return false;
1543
1544                                 superblockend = true;
1545                                 break;
1546
1547                         case ICMD_RET:
1548                                 /* check returnAddress variable */
1549                                 if (!typevector_checkretaddr(jd->var,state->iptr->s1.varindex))
1550                                         TYPECHECK_VERIFYERROR_bool("illegal instruction: RET using non-returnAddress variable");
1551
1552                                 if (!typestate_reach(state, iptr->dst.block, state->bptr->outvars, jd->var,
1553                                                         state->bptr->outdepth))
1554                                         return false;
1555
1556                                 superblockend = true;
1557                                 break;
1558
1559                                 /****************************************/
1560                                 /* INVOKATIONS                          */
1561
1562                         case ICMD_INVOKEVIRTUAL:
1563                         case ICMD_INVOKESPECIAL:
1564                         case ICMD_INVOKESTATIC:
1565                         case ICMD_INVOKEINTERFACE:
1566                                 TYPECHECK_COUNT(stat_ins_invoke);
1567                                 if (!verify_invocation(state))
1568                                         return false;
1569                                 TYPECHECK_COUNTIF(INSTRUCTION_IS_UNRESOLVED(iptr), stat_ins_invoke_unresolved);
1570                                 maythrow = true;
1571                                 break;
1572
1573                                 /****************************************/
1574                                 /* MULTIANEWARRAY                       */
1575
1576                         case ICMD_MULTIANEWARRAY:
1577                                 if (!verify_multianewarray(state))
1578                                         return false;
1579                                 maythrow = true;
1580                                 break;
1581
1582                                 /****************************************/
1583                                 /* BUILTINS                             */
1584
1585                         case ICMD_BUILTIN:
1586                                 TYPECHECK_COUNT(stat_ins_builtin);
1587                                 if (!verify_builtin(state))
1588                                         return false;
1589                                 maythrow = true;
1590                                 break;
1591
1592                                 /****************************************/
1593                                 /* SIMPLE EXCEPTION THROWING TESTS      */
1594
1595                         case ICMD_CHECKNULL:
1596                                 /* CHECKNULL just requires that the stack top
1597                                  * is an address. This is checked in stack.c */
1598                                 maythrow = true;
1599                                 break;
1600
1601                                 /****************************************/
1602                                 /* INSTRUCTIONS WHICH SHOULD HAVE BEEN  */
1603                                 /* REPLACED BY OTHER OPCODES            */
1604
1605 #ifdef TYPECHECK_DEBUG
1606                         case ICMD_NEW:
1607                         case ICMD_NEWARRAY:
1608                         case ICMD_ANEWARRAY:
1609                         case ICMD_MONITORENTER:
1610                         case ICMD_MONITOREXIT:
1611                                 LOG2("ICMD %d at %d\n", state->iptr->opc, (int)(state->iptr-state->bptr->iinstr));
1612                                 LOG("Should have been converted to builtin function call.");
1613                                 TYPECHECK_ASSERT(false);
1614                                 break;
1615 #endif
1616
1617                                 /****************************************/
1618                                 /* UNCHECKED OPERATIONS                 */
1619
1620                                 /*********************************************
1621                                  * Instructions below...
1622                                  *     *) don't operate on local variables,
1623                                  *     *) don't operate on references,
1624                                  *     *) don't operate on returnAddresses,
1625                                  *     *) don't affect control flow (except
1626                                  *        by throwing exceptions).
1627                                  *
1628                                  * (These instructions are typechecked in
1629                                  *  analyse_stack.)
1630                                  ********************************************/
1631
1632                                 /* Instructions which may throw a runtime exception: */
1633
1634                         case ICMD_IDIV:
1635                         case ICMD_IREM:
1636                                 dv->type = TYPE_INT;
1637                                 maythrow = true;
1638                                 break;
1639
1640                         case ICMD_LDIV:
1641                         case ICMD_LREM:
1642                                 dv->type = TYPE_LNG;
1643                                 maythrow = true;
1644                                 break;
1645
1646                                 /* Instructions which never throw a runtime exception: */
1647                         case ICMD_NOP:
1648                         case ICMD_POP:
1649                         case ICMD_POP2:
1650                                 break;
1651
1652                         case ICMD_ICONST:
1653                         case ICMD_IADD:
1654                         case ICMD_ISUB:
1655                         case ICMD_IMUL:
1656                         case ICMD_INEG:
1657                         case ICMD_IAND:
1658                         case ICMD_IOR:
1659                         case ICMD_IXOR:
1660                         case ICMD_ISHL:
1661                         case ICMD_ISHR:
1662                         case ICMD_IUSHR:
1663                         case ICMD_IMULPOW2:
1664                         case ICMD_IDIVPOW2:
1665                         case ICMD_IADDCONST:
1666                         case ICMD_ISUBCONST:
1667                         case ICMD_IMULCONST:
1668                         case ICMD_IANDCONST:
1669                         case ICMD_IORCONST:
1670                         case ICMD_IXORCONST:
1671                         case ICMD_ISHLCONST:
1672                         case ICMD_ISHRCONST:
1673                         case ICMD_IUSHRCONST:
1674                         case ICMD_IREMPOW2:
1675                         case ICMD_INT2BYTE:
1676                         case ICMD_INT2CHAR:
1677                         case ICMD_INT2SHORT:
1678                         case ICMD_L2I:
1679                         case ICMD_F2I:
1680                         case ICMD_D2I:
1681                         case ICMD_LCMP:
1682                         case ICMD_LCMPCONST:
1683                         case ICMD_FCMPL:
1684                         case ICMD_FCMPG:
1685                         case ICMD_DCMPL:
1686                         case ICMD_DCMPG:
1687                                 dv->type = TYPE_INT;
1688                                 break;
1689
1690                         case ICMD_LCONST:
1691                         case ICMD_LADD:
1692                         case ICMD_LSUB:
1693                         case ICMD_LMUL:
1694                         case ICMD_LNEG:
1695                         case ICMD_LAND:
1696                         case ICMD_LOR:
1697                         case ICMD_LXOR:
1698                         case ICMD_LSHL:
1699                         case ICMD_LSHR:
1700                         case ICMD_LUSHR:
1701                         case ICMD_LMULPOW2:
1702                         case ICMD_LDIVPOW2:
1703                         case ICMD_LADDCONST:
1704                         case ICMD_LSUBCONST:
1705                         case ICMD_LMULCONST:
1706                         case ICMD_LANDCONST:
1707                         case ICMD_LORCONST:
1708                         case ICMD_LXORCONST:
1709                         case ICMD_LSHLCONST:
1710                         case ICMD_LSHRCONST:
1711                         case ICMD_LUSHRCONST:
1712                         case ICMD_LREMPOW2:
1713                         case ICMD_I2L:
1714                         case ICMD_F2L:
1715                         case ICMD_D2L:
1716                                 dv->type = TYPE_LNG;
1717                                 break;
1718
1719                         case ICMD_FCONST:
1720                         case ICMD_I2F:
1721                         case ICMD_L2F:
1722                         case ICMD_D2F:
1723                         case ICMD_FADD:
1724                         case ICMD_FSUB:
1725                         case ICMD_FMUL:
1726                         case ICMD_FDIV:
1727                         case ICMD_FREM:
1728                         case ICMD_FNEG:
1729                                 dv->type = TYPE_FLT;
1730                                 break;
1731
1732                         case ICMD_DCONST:
1733                         case ICMD_I2D:
1734                         case ICMD_L2D:
1735                         case ICMD_F2D:
1736                         case ICMD_DADD:
1737                         case ICMD_DSUB:
1738                         case ICMD_DMUL:
1739                         case ICMD_DDIV:
1740                         case ICMD_DREM:
1741                         case ICMD_DNEG:
1742                                 dv->type = TYPE_DBL;
1743                                 break;
1744
1745                         case ICMD_INLINE_START:
1746                         case ICMD_INLINE_END:
1747                                 break;
1748
1749                                 /* XXX What shall we do with the following ?*/
1750                         case ICMD_AASTORECONST:
1751                                 TYPECHECK_COUNT(stat_ins_unchecked);
1752                                 break;
1753
1754                                 /****************************************/
1755
1756                         default:
1757                                 LOG2("ICMD %d at %d\n", state->iptr->opc, (int)(state->iptr-state->bptr->iinstr));
1758                                 TYPECHECK_VERIFYERROR_bool("Missing ICMD code during typecheck");
1759                 }
1760
1761                 /* reach exception handlers for this instruction */
1762
1763                 if (maythrow) {
1764                         TYPECHECK_COUNT(stat_ins_maythrow);
1765                         TYPECHECK_MARK(state->stat_maythrow);
1766                         LOG("reaching exception handlers");
1767                         i = 0;
1768                         while (state->handlers[i]) {
1769                                 TYPECHECK_COUNT(stat_handlers_reached);
1770                                 if (state->handlers[i]->catchtype.any)
1771                                         VAR(state->exinvars)->typeinfo.typeclass = state->handlers[i]->catchtype;
1772                                 else
1773                                         VAR(state->exinvars)->typeinfo.typeclass.cls = class_java_lang_Throwable;
1774                                 if (!typestate_reach(state,
1775                                                 state->handlers[i]->handler,
1776                                                 &(state->exinvars), jd->var, 1))
1777                                         return false;
1778                                 i++;
1779                         }
1780                 }
1781
1782                 LOG("\t\tnext instruction");
1783                 state->iptr++;
1784         } /* while instructions */
1785
1786         LOG("instructions done");
1787         LOGSTR("RESULT=> ");
1788         DOLOG(typecheck_print_vararray(stdout, jd, state->bptr->outvars,
1789                                 state->bptr->outdepth));
1790         DOLOG(typevector_print(stdout, jd->var, state->numlocals));
1791         LOGNL; LOGFLUSH;
1792
1793         /* propagate stack and variables to the following block */
1794         if (!superblockend) {
1795                 LOG("reaching following block");
1796                 tbptr = state->bptr->next;
1797                 while (tbptr->flags == BBDELETED) {
1798                         tbptr = tbptr->next;
1799 #ifdef TYPECHECK_DEBUG
1800                         /* this must be checked in parse.c */
1801                         if ((tbptr->nr) >= state->basicblockcount)
1802                                 TYPECHECK_VERIFYERROR_bool("Control flow falls off the last block");
1803 #endif
1804                 }
1805                 if (!typestate_reach(state,tbptr,state->bptr->outvars, jd->var,
1806                                         state->bptr->outdepth))
1807                         return false;
1808         }
1809
1810         /* We may have to restore the types of the instack slots. They
1811          * have been saved if an <init> call inside the block has
1812          * modified the instack types. (see INVOKESPECIAL) */
1813
1814         if (state->savedinvars)
1815                 typestate_restore_invars(state);
1816
1817         return true;
1818 }
1819
1820
1821 /* verify_init_locals **********************************************************
1822
1823    Initialize the local variables in the verifier state.
1824
1825    IN:
1826        state............the current state of the verifier
1827
1828    RETURN VALUE:
1829        true.............success,
1830            false............an exception has been thrown.
1831
1832 *******************************************************************************/
1833
1834 static bool
1835 verify_init_locals(verifier_state *state)
1836 {
1837         int i;
1838         int index;
1839         varinfo *locals;
1840         varinfo *v;
1841         jitdata *jd = state->jd;
1842         int skip = 0;
1843
1844         locals = state->basicblocks[0].inlocals;
1845
1846         /* allocate parameter descriptors if necessary */
1847
1848         if (!state->m->parseddesc->params)
1849                 if (!descriptor_params_from_paramtypes(state->m->parseddesc,state->m->flags))
1850                         return false;
1851
1852         /* pre-initialize variables as TYPE_VOID */
1853
1854         i = state->numlocals;
1855         v = locals;
1856         while (i--) {
1857                 v->type = TYPE_VOID;
1858                 v++;
1859         }
1860
1861     /* if this is an instance method initialize the "this" ref type */
1862
1863     if (!(state->m->flags & ACC_STATIC)) {
1864                 index = jd->local_map[5*0 + TYPE_ADR];
1865                 if (index != UNUSED) {
1866                         if (state->validlocals < 1)
1867                                 TYPECHECK_VERIFYERROR_bool("Not enough local variables for method arguments");
1868                         v = locals + index;
1869                         v->type = TYPE_ADR;
1870                         if (state->initmethod)
1871                                 TYPEINFO_INIT_NEWOBJECT(v->typeinfo, NULL);
1872                         else
1873                                 typeinfo_init_classinfo(&(v->typeinfo), state->m->class);
1874                 }
1875
1876                 skip = 1;
1877     }
1878
1879     LOG("'this' argument set.\n");
1880
1881     /* the rest of the arguments and the return type */
1882
1883     if (!typeinfo_init_varinfos_from_methoddesc(locals, state->m->parseddesc,
1884                                                                                           state->validlocals,
1885                                                                                           skip, /* skip 'this' pointer */
1886                                                                                           jd->local_map,
1887                                                                                           &state->returntype))
1888                 return false;
1889
1890     LOG("Arguments set.\n");
1891         return true;
1892 }
1893
1894
1895 /* typecheck_init_flags ********************************************************
1896
1897    Initialize the basic block flags for the following CFG traversal.
1898
1899    IN:
1900        state............the current state of the verifier
1901
1902 *******************************************************************************/
1903
1904 static void
1905 typecheck_init_flags(verifier_state *state)
1906 {
1907         s4 i;
1908         basicblock *block;
1909
1910     /* set all BBFINISHED blocks to BBTYPECHECK_UNDEF. */
1911
1912     i = state->basicblockcount;
1913     for (block = state->basicblocks; block; block = block->next) {
1914
1915 #ifdef TYPECHECK_DEBUG
1916                 /* check for invalid flags */
1917         if (block->flags != BBFINISHED && block->flags != BBDELETED && block->flags != BBUNDEF)
1918         {
1919             LOGSTR1("block flags: %d\n",block->flags); LOGFLUSH;
1920                         TYPECHECK_ASSERT(false);
1921         }
1922 #endif
1923
1924         if (block->flags >= BBFINISHED) {
1925             block->flags = BBTYPECHECK_UNDEF;
1926         }
1927     }
1928
1929     /* the first block is always reached */
1930
1931     if (state->basicblockcount && state->basicblocks[0].flags == BBTYPECHECK_UNDEF)
1932         state->basicblocks[0].flags = BBTYPECHECK_REACHED;
1933 }
1934
1935
1936 /* typecheck_reset_flags *******************************************************
1937
1938    Reset the flags of basic blocks we have not reached.
1939
1940    IN:
1941        state............the current state of the verifier
1942
1943 *******************************************************************************/
1944
1945 static void
1946 typecheck_reset_flags(verifier_state *state)
1947 {
1948         basicblock *block;
1949
1950         /* check for invalid flags at exit */
1951
1952 #ifdef TYPECHECK_DEBUG
1953         for (block = state->basicblocks; block; block = block->next) {
1954                 if (block->flags != BBDELETED
1955                         && block->flags != BBUNDEF
1956                         && block->flags != BBFINISHED
1957                         && block->flags != BBTYPECHECK_UNDEF) /* typecheck may never reach
1958                                                                                                          * some exception handlers,
1959                                                                                                          * that's ok. */
1960                 {
1961                         LOG2("block L%03d has invalid flags after typecheck: %d",
1962                                  block->nr,block->flags);
1963                         TYPECHECK_ASSERT(false);
1964                 }
1965         }
1966 #endif
1967
1968         /* Delete blocks we never reached */
1969
1970         for (block = state->basicblocks; block; block = block->next) {
1971                 if (block->flags == BBTYPECHECK_UNDEF)
1972                         block->flags = BBDELETED;
1973         }
1974 }
1975
1976
1977 /****************************************************************************/
1978 /* typecheck()                                                              */
1979 /* This is the main function of the bytecode verifier. It is called         */
1980 /* directly after analyse_stack.                                            */
1981 /*                                                                          */
1982 /* IN:                                                                      */
1983 /*    meth.............the method to verify                                 */
1984 /*    cdata............codegendata for the method                           */
1985 /*    rdata............registerdata for the method                          */
1986 /*                                                                          */
1987 /* RETURN VALUE:                                                            */
1988 /*     true.............successful verification                             */
1989 /*     false............an exception has been thrown                        */
1990 /*                                                                          */
1991 /****************************************************************************/
1992
1993 #define MAXPARAMS 255
1994
1995 bool typecheck(jitdata *jd)
1996 {
1997         methodinfo     *meth;
1998         codegendata    *cd;
1999         varinfo        *savedlocals;
2000         verifier_state  state;             /* current state of the verifier */
2001         s4              i;
2002         s4              t;
2003
2004         /* collect statistics */
2005
2006 #ifdef TYPECHECK_STATISTICS
2007         int count_iterations = 0;
2008         TYPECHECK_COUNT(stat_typechecked);
2009         TYPECHECK_COUNT_FREQ(stat_locals,cdata->maxlocals,STAT_LOCALS);
2010         TYPECHECK_COUNT_FREQ(stat_blocks,cdata->method->basicblockcount/10,STAT_BLOCKS);
2011         TYPECHECK_COUNTIF(cdata->method->exceptiontablelength != 0,stat_methods_with_handlers);
2012         state.stat_maythrow = false;
2013 #endif
2014
2015         /* get required compiler data */
2016
2017         meth = jd->m;
2018         cd   = jd->cd;
2019
2020         /* some logging on entry */
2021
2022
2023     LOGSTR("\n==============================================================================\n");
2024     DOLOG( show_method(jd, SHOW_STACK) );
2025     LOGSTR("\n==============================================================================\n");
2026     LOGMETHOD("Entering typecheck: ",cd->method);
2027
2028         /* initialize the verifier state */
2029
2030         state.m = meth;
2031         state.jd = jd;
2032         state.cd = cd;
2033         state.basicblockcount = jd->basicblockcount;
2034         state.basicblocks = jd->basicblocks;
2035         state.savedindices = NULL;
2036         state.savedinvars = NULL;
2037
2038         /* check if this method is an instance initializer method */
2039
2040     state.initmethod = (state.m->name == utf_init);
2041
2042         /* initialize the basic block flags for the following CFG traversal */
2043
2044         typecheck_init_flags(&state);
2045
2046     /* number of local variables */
2047
2048     /* In <init> methods we use an extra local variable to indicate whether */
2049     /* the 'this' reference has been initialized.                           */
2050         /*         TYPE_VOID...means 'this' has not been initialized,           */
2051         /*         TYPE_INT....means 'this' has been initialized.               */
2052
2053     state.numlocals = state.jd->localcount;
2054         state.validlocals = state.numlocals;
2055     if (state.initmethod)
2056                 state.numlocals++; /* VERIFIER_EXTRA_LOCALS */
2057
2058         state.reverselocalmap = DMNEW(s4, state.validlocals);
2059         for (i=0; i<jd->m->maxlocals; ++i)
2060                 for (t=0; t<5; ++t) {
2061                         s4 mapped = jd->local_map[5*i + t];
2062                         if (mapped >= 0)
2063                                 state.reverselocalmap[mapped] = i;
2064                 }
2065
2066         DOLOG(
2067                 LOG("reverselocalmap:");
2068                 for (i=0; i<state.validlocals; ++i) {
2069                         LOG2("    %i => javaindex %i", i, state.reverselocalmap[i]);
2070                 });
2071
2072     /* allocate the buffer of active exception handlers */
2073
2074     state.handlers = DMNEW(exceptiontable*, state.cd->exceptiontablelength + 1);
2075
2076         /* save local variables */
2077
2078         savedlocals = DMNEW(varinfo, state.numlocals);
2079         MCOPY(savedlocals, jd->var, varinfo, state.numlocals);
2080
2081         /* initialized local variables of first block */
2082
2083         if (!verify_init_locals(&state))
2084                 return false;
2085
2086     /* initialize invars of exception handlers */
2087
2088         state.exinvars = state.numlocals;
2089         VAR(state.exinvars)->type = TYPE_ADR;
2090         typeinfo_init_classinfo(&(VAR(state.exinvars)->typeinfo),
2091                                                         class_java_lang_Throwable); /* changed later */
2092
2093     LOG("Exception handler stacks set.\n");
2094
2095     /* loop while there are still blocks to be checked */
2096     do {
2097                 TYPECHECK_COUNT(count_iterations);
2098
2099         state.repeat = false;
2100
2101         state.bptr = state.basicblocks;
2102
2103         for (; state.bptr; state.bptr = state.bptr->next) {
2104             LOGSTR1("---- BLOCK %04d, ",state.bptr->nr);
2105             LOGSTR1("blockflags: %d\n",state.bptr->flags);
2106             LOGFLUSH;
2107
2108                     /* verify reached block */
2109             if (state.bptr->flags == BBTYPECHECK_REACHED) {
2110                 if (!verify_basic_block(&state))
2111                                         return false;
2112             }
2113         } /* for blocks */
2114
2115         LOGIF(state.repeat,"state.repeat == true");
2116     } while (state.repeat);
2117
2118         /* statistics */
2119
2120 #ifdef TYPECHECK_STATISTICS
2121         LOG1("Typechecker did %4d iterations",count_iterations);
2122         TYPECHECK_COUNT_FREQ(stat_iterations,count_iterations,STAT_ITERATIONS);
2123         TYPECHECK_COUNTIF(state.jsrencountered,stat_typechecked_jsr);
2124         TYPECHECK_COUNTIF(state.stat_maythrow,stat_methods_maythrow);
2125 #endif
2126
2127         /* reset the flags of blocks we haven't reached */
2128
2129         typecheck_reset_flags(&state);
2130
2131         /* restore locals */
2132
2133         MCOPY(jd->var, savedlocals, varinfo, state.numlocals);
2134
2135         /* everything's ok */
2136
2137     LOGimp("exiting typecheck");
2138         return true;
2139 }
2140 #endif /* ENABLE_VERIFIER */
2141
2142 /*
2143  * These are local overrides for various environment variables in Emacs.
2144  * Please do not remove this and leave it at the end of the file, where
2145  * Emacs will automagically detect them.
2146  * ---------------------------------------------------------------------
2147  * Local variables:
2148  * mode: c
2149  * indent-tabs-mode: t
2150  * c-basic-offset: 4
2151  * tab-width: 4
2152  * End:
2153  * vim:noexpandtab:sw=4:ts=4:
2154  */