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