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, 2007 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 */
  26
  27 /*
  28
  29 What's the purpose of the `typechecker`?
  30 ----------------------------------------
  31
  32 The typechecker analyses (the intermediate repr. of) the bytecode of
  33 each method and ensures that for each instruction the values on the
  34 stack and in local variables are of the correct type whenever the
  35 instruction is executed.
  36
  37 type checking is a mandatory part of bytecode verification.
  38
  39
  40 How does the typechecker work?
  41 ------------------------------
  42
  43 The JVM stack and the local variables are not statically typed, so the
  44 typechecker has to *infer* the static types of stack slots and local
  45 variables at each point of the method. The JVM spec imposes a lot of
  46 restrictions on the bytecode in order to guarantee that this is always
  47 possible.
  48
  49 Basically the typechecker solves the data flow equations of the method.
  50 This is done in the usual way for a forward data flow analysis: Starting
  51 from the entry point of the method the typechecker follows the CFG and
  52 records the type of each stack slot and local variable at each point[1].
  53 When two or more control flow paths merge at a point, the union of the
  54 types for each slot/variable is taken. The algorithm continues to follow
  55 all possible paths[2] until the recorded types do not change anymore (ie.
  56 the equations have been solved).
  57
  58 If the solution has been reached and the resulting types are valid for
  59 all instructions, then type checking terminates with success, otherwise
  60 an exception is thrown.
  61
  62
  63 Why is this code so damn complicated?
  64 -------------------------------------
  65
  66 Short answer: The devil's in the details.
  67
  68 While the basic operation of the typechecker is no big deal, there are
  69 many properties of Java bytecode which make type checking hard. Some of
  70 them are not even addressed in the JVM spec. Some problems and their
  71 solutions:
  72
  73 *) Finding a good representation of the union of two reference types is
  74 difficult because of multiple inheritance of interfaces.
  75
  76         Solution: The typeinfo system can represent such "merged" types by a
  77         list of proper subclasses of a class. Example:
  78
  79                 typeclass=java.lang.Object merged={ InterfaceA, InterfaceB }
  80
  81         represents the result of merging two interface types "InterfaceA"
  82         and "InterfaceB".
  83
  84 *) When the code of a method is verified, there may still be unresolved
  85 references to classes/methods/fields in the code, which we may not force
  86 to be resolved eagerly. (A similar problem arises because of the special
  87 checks for protected members.)
  88
  89         Solution: The typeinfo system knows how to deal with unresolved
  90         class references. Whenever a check has to be performed for an
  91         unresolved type, the type is annotated with constraints representing
  92         the check. Later, when the type is resolved, the constraints are
  93         checked. (See the constrain_unresolved_... and the resolve_...
  94         methods.)[3]
  95
  96 *) Checks for uninitialized object instances are hard because after the
  97 invocation of <init> on an uninitialized object *all* slots/variables
  98 referring to this object (and exactly those slots/variables) must be
  99 marked as initialized.
 100
 101         Solution: The JVM spec describes a solution, which has been
 102         implemented in this typechecker.
 103
 104 Note that some checks mentioned in the JVM spec are unnecessary[4] and
 105 not performed by either the reference implementation, or this implementation.
 106
 107
 108 --- Footnotes
 109
 110 [1] Actually only the types of slots/variables at the start of each
 111 basic block are remembered. Within a basic block the algorithm only keeps
 112 the types of the slots/variables for the "current" instruction which is
 113 being analysed.
 114
 115 [2] Actually the algorithm iterates through the basic block list until
 116 there are no more changes. Theoretically it would be wise to sort the
 117 basic blocks topologically beforehand, but the number of average/max
 118 iterations observed is so low, that this was not deemed necessary.
 119
 120 [3] This is similar to a method proposed by: Alessandro Coglio et al., A
 121 Formal Specification of Java Class Loading, Technical Report, Kestrel
 122 Institute April 2000, revised July 2000
 123 http://www.kestrel.edu/home/people/coglio/loading.pdf
 124 An important difference is that Coglio's subtype constraints are checked
 125 after loading, while our constraints are checked when the field/method
 126 is accessed for the first time, so we can guarantee lexically correct
 127 error reporting.
 128
 129 [4] Alessandro Coglio
 130     Improving the official specification of Java bytecode verification
 131     Proceedings of the 3rd ECOOP Workshop on Formal Techniques for Java Programs
 132     June 2001
 133     citeseer.ist.psu.edu/article/coglio03improving.html
 134 */
 135
 136
 137 #include "config.h"
 138
 139 #include <assert.h>
 140 #include <string.h>
 141
 142 #include "vm/types.h"
 143
 144 #ifdef ENABLE_VERIFIER
 145
 146 #include "mm/memory.h"
 147
 148 #include "native/native.h"
 149
 150 #include "toolbox/logging.h"
 151
 152 #include "vm/access.h"
 153 #include "vm/array.h"
 154 #include "vm/builtin.h"
 155 #include "vm/exceptions.h"
 156 #include "vm/global.h"
 157 #include "vm/primitive.h"
 158 #include "vm/resolve.h"
 159
 160 #include "vm/jit/jit.h"
 161 #include "vm/jit/parse.h"
 162 #include "vm/jit/show.h"
 163
 164 #include "vmcore/loader.h"
 165 #include "vmcore/options.h"
 166
 167 #include <typecheck-common.h>
 168
 169
 170 /****************************************************************************/
 171 /* MACROS FOR VARIABLE TYPE CHECKING                                        */
 172 /****************************************************************************/
 173
 174 #define TYPECHECK_CHECK_TYPE(i,tp,msg)                               \
 175     do {                                                             \
 176         if (VAR(i)->type != (tp)) {                                  \
 177             exceptions_throw_verifyerror(state->m, (msg));           \
 178             return false;                                            \
 179         }                                                            \
 180     } while (0)
 181
 182 #define TYPECHECK_INT(i)                                             \
 183     TYPECHECK_CHECK_TYPE(i,TYPE_INT,"Expected to find integer value")
 184 #define TYPECHECK_LNG(i)                                             \
 185     TYPECHECK_CHECK_TYPE(i,TYPE_LNG,"Expected to find long value")
 186 #define TYPECHECK_FLT(i)                                             \
 187     TYPECHECK_CHECK_TYPE(i,TYPE_FLT,"Expected to find float value")
 188 #define TYPECHECK_DBL(i)                                             \
 189     TYPECHECK_CHECK_TYPE(i,TYPE_DBL,"Expected to find double value")
 190 #define TYPECHECK_ADR(i)                                             \
 191     TYPECHECK_CHECK_TYPE(i,TYPE_ADR,"Expected to find object value")
 192
 193 #define TYPECHECK_INT_OP(o)  TYPECHECK_INT((o).varindex)
 194 #define TYPECHECK_LNG_OP(o)  TYPECHECK_LNG((o).varindex)
 195 #define TYPECHECK_FLT_OP(o)  TYPECHECK_FLT((o).varindex)
 196 #define TYPECHECK_DBL_OP(o)  TYPECHECK_DBL((o).varindex)
 197 #define TYPECHECK_ADR_OP(o)  TYPECHECK_ADR((o).varindex)
 198
 199
 200 /* typestate_save_invars *******************************************************
 201
 202    Save the invars of the current basic block in the space reserved by
 203    parse.
 204
 205    This function must be called before an instruction modifies a variable
 206    that is an invar of the current block. In such cases the invars of the
 207    block must be saved, and restored at the end of the analysis of this
 208    basic block, so that the invars again reflect the *input* to this basic
 209    block (and do not randomly contain types that appear within the block).
 210
 211    IN:
 212        state............current state of the verifier
 213
 214 *******************************************************************************/
 215
 216 static void
 217 typestate_save_invars(verifier_state *state)
 218 {
 219         s4 i, index;
 220         s4 *pindex;
 221
 222         LOG("saving invars");
 223
 224         if (!state->savedindices) {
 225                 LOG("allocating savedindices buffer");
 226                 pindex = DMNEW(s4, state->m->maxstack);
 227                 state->savedindices = pindex;
 228                 index = state->numlocals + VERIFIER_EXTRA_VARS;
 229                 for (i=0; i<state->m->maxstack; ++i)
 230                         *pindex++ = index++;
 231         }
 232
 233         /* save types */
 234
 235         typecheck_copy_types(state, state->bptr->invars, state->savedindices,
 236                         state->bptr->indepth);
 237
 238         /* set the invars of the block to the saved variables */
 239         /* and remember the original invars                   */
 240
 241         state->savedinvars = state->bptr->invars;
 242         state->bptr->invars = state->savedindices;
 243 }
 244
 245
 246 /* typestate_restore_invars  ***************************************************
 247
 248    Restore the invars of the current basic block that have been previously
 249    saved by `typestate_save_invars`.
 250
 251    IN:
 252        state............current state of the verifier
 253
 254 *******************************************************************************/
 255
 256 static void
 257 typestate_restore_invars(verifier_state *state)
 258 {
 259         TYPECHECK_COUNT(stat_savedstack);
 260         LOG("restoring saved invars");
 261
 262         /* restore the invars pointer */
 263
 264         state->bptr->invars = state->savedinvars;
 265
 266         /* copy the types back */
 267
 268         typecheck_copy_types(state, state->savedindices, state->bptr->invars,
 269                         state->bptr->indepth);
 270
 271         /* mark that there are no saved invars currently */
 272
 273         state->savedinvars = NULL;
 274 }
 275
 276
 277 /* handle_fieldaccess **********************************************************
 278
 279    Verify an ICMD_{GET,PUT}{STATIC,FIELD}(CONST)?
 280
 281    IN:
 282        state............the current state of the verifier
 283
 284    RETURN VALUE:
 285        true.............successful verification,
 286            false............an exception has been thrown.
 287
 288 *******************************************************************************/
 289
 290 static bool
 291 handle_fieldaccess(verifier_state *state,
 292                                    varinfo *instance,
 293                                    varinfo *value)
 294 {
 295         jitdata *jd;
 296
 297         jd = state->jd;
 298
 299 #define TYPECHECK_VARIABLESBASED
 300 #define EXCEPTION  do { return false; } while (0)
 301 #define VERIFY_ERROR(msg)  TYPECHECK_VERIFYERROR_bool(msg)
 302 #include <typecheck-fields.inc>
 303 #undef  EXCEPTION
 304 #undef  VERIFY_ERROR
 305 #undef  TYPECHECK_VARIABLESBASED
 306
 307         return true;
 308 }
 309
 310
 311 /* handle_invocation ***********************************************************
 312
 313    Verify an ICMD_INVOKE* instruction.
 314
 315    IN:
 316        state............the current state of the verifier
 317
 318    RETURN VALUE:
 319        true.............successful verification,
 320            false............an exception has been thrown.
 321
 322 *******************************************************************************/
 323
 324 static bool
 325 handle_invocation(verifier_state *state)
 326 {
 327         jitdata *jd;
 328     varinfo *dv;               /* output variable of current instruction */
 329
 330         jd = state->jd;
 331         dv = VAROP(state->iptr->dst);
 332
 333 #define TYPECHECK_VARIABLESBASED
 334 #define OP1   VAR(state->iptr->sx.s23.s2.args[0])
 335 #include <typecheck-invoke.inc>
 336 #undef  OP1
 337 #undef  TYPECHECK_VARIABLESBASED
 338
 339         return true;
 340 }
 341
 342
 343 /* handle_builtin **************************************************************
 344
 345    Verify the call of a builtin method.
 346
 347    IN:
 348        state............the current state of the verifier
 349
 350    RETURN VALUE:
 351        true.............successful verification,
 352            false............an exception has been thrown.
 353
 354 *******************************************************************************/
 355
 356 static bool
 357 handle_builtin(verifier_state *state)
 358 {
 359         jitdata *jd;
 360     varinfo *dv;               /* output variable of current instruction */
 361
 362         jd = state->jd;
 363         dv = VAROP(state->iptr->dst);
 364
 365 #define TYPECHECK_VARIABLESBASED
 366 #define OP1   state->iptr->sx.s23.s2.args[0]
 367 #include <typecheck-builtins.inc>
 368 #undef  OP1
 369 #undef  TYPECHECK_VARIABLESBASED
 370
 371         return true;
 372 }
 373
 374 /* handle_multianewarray *******************************************************
 375
 376    Verify a MULTIANEWARRAY instruction.
 377
 378    IN:
 379        state............the current state of the verifier
 380
 381    RETURN VALUE:
 382        true.............successful verification,
 383            false............an exception has been thrown.
 384
 385 *******************************************************************************/
 386
 387 static bool
 388 handle_multianewarray(verifier_state *state)
 389 {
 390         jitdata *jd;
 391     varinfo *dv;               /* output variable of current instruction */
 392
 393         jd = state->jd;
 394         dv = VAROP(state->iptr->dst);
 395
 396 #define TYPECHECK_VARIABLESBASED
 397 #define VERIFY_ERROR(msg)  TYPECHECK_VERIFYERROR_bool(msg)
 398 #include <typecheck-multianewarray.inc>
 399 #undef VERIFY_ERROR
 400 #undef  TYPECHECK_VARIABLESBASED
 401
 402         return true;
 403 }
 404
 405 /* typecheck_invalidate_locals *************************************************
 406
 407    Invalidate locals that are overwritten by writing to the given local.
 408
 409    IN:
 410        state............the current state of the verifier
 411            index............the index of the local that is written
 412            twoword..........true, if a two-word type is written
 413
 414 *******************************************************************************/
 415
 416 static void typecheck_invalidate_locals(verifier_state *state, s4 index, bool twoword)
 417 {
 418         s4 javaindex;
 419         s4 t;
 420         s4 varindex;
 421         jitdata *jd = state->jd;
 422         s4 *localmap = jd->local_map;
 423         varinfo *vars = jd->var;
 424
 425         javaindex = state->reverselocalmap[index];
 426
 427         /* invalidate locals of two-word type at index javaindex-1 */
 428
 429         if (javaindex > 0) {
 430                 localmap += 5 * (javaindex-1);
 431                 for (t=0; t<5; ++t) {
 432                         varindex = *localmap++;
 433                         if (varindex >= 0 && IS_2_WORD_TYPE(vars[varindex].type)) {
 434                                 LOG1("invalidate local %d", varindex);
 435                                 vars[varindex].type = TYPE_VOID;
 436                         }
 437                 }
 438         }
 439         else {
 440                 localmap += 5 * javaindex;
 441         }
 442
 443         /* invalidate locals at index javaindex */
 444
 445         for (t=0; t<5; ++t) {
 446                 varindex = *localmap++;
 447                 if (varindex >= 0) {
 448                         LOG1("invalidate local %d", varindex);
 449                         vars[varindex].type = TYPE_VOID;
 450                 }
 451         }
 452
 453         /* if a two-word type is written, invalidate locals at index javaindex+1 */
 454
 455         if (twoword) {
 456                 for (t=0; t<5; ++t) {
 457                         varindex = *localmap++;
 458                         if (varindex >= 0) {
 459                                 LOG1("invalidate local %d", varindex);
 460                                 vars[varindex].type = TYPE_VOID;
 461                         }
 462                 }
 463         }
 464 }
 465
 466
 467 /* macros used by the generated code ******************************************/
 468
 469 #define EXCEPTION          do { return false; } while (0)
 470 #define VERIFY_ERROR(msg)  TYPECHECK_VERIFYERROR_bool(msg)
 471
 472 #define CHECK_LOCAL_TYPE(index, t)                                   \
 473     do {                                                             \
 474         if (!typevector_checktype(jd->var, (index), (t)))            \
 475              VERIFY_ERROR("Local variable type mismatch");           \
 476     } while (0)
 477
 478 #define STORE_LOCAL(t, index)                                        \
 479     do {                                                             \
 480          s4 temp_t = (t);                                            \
 481          typecheck_invalidate_locals(state, (index), false);         \
 482          typevector_store(jd->var, (index), (temp_t), NULL);         \
 483     } while (0)
 484
 485 #define STORE_LOCAL_2_WORD(t, index)                                 \
 486     do {                                                             \
 487          s4 temp_t = (t);                                            \
 488          typecheck_invalidate_locals(state, (index), true);          \
 489          typevector_store(jd->var, (index), (temp_t), NULL);         \
 490     } while (0)
 491
 492 #define REACH_BLOCK(target)                                          \
 493     do {                                                             \
 494         if (!typestate_reach(state, (target),                        \
 495                              state->bptr->outvars, jd->var,          \
 496                              state->bptr->outdepth))                 \
 497                 return false;                                        \
 498     } while (0)
 499
 500 #define REACH(target)   REACH_BLOCK((target).block)
 501
 502
 503 /* handle_basic_block **********************************************************
 504
 505    Perform bytecode verification of a basic block.
 506
 507    IN:
 508        state............the current state of the verifier
 509
 510    RETURN VALUE:
 511        true.............successful verification,
 512            false............an exception has been thrown.
 513
 514 *******************************************************************************/
 515
 516 static bool
 517 handle_basic_block(verifier_state *state)
 518 {
 519     int opcode;                                      /* current opcode */
 520     int len;                        /* for counting instructions, etc. */
 521     bool superblockend;        /* true if no fallthrough to next block */
 522         instruction *iptr;                      /* the current instruction */
 523     basicblock *tbptr;                   /* temporary for target block */
 524     bool maythrow;               /* true if this instruction may throw */
 525         s4 i;
 526         typecheck_result r;
 527         branch_target_t *table;
 528         lookup_target_t *lookup;
 529         jitdata *jd = state->jd;
 530         exception_entry *ex;
 531         varinfo constvalue;                               /* for PUT*CONST */
 532         constant_FMIref *fieldref;
 533
 534         LOGSTR1("\n---- BLOCK %04d ------------------------------------------------\n",state->bptr->nr);
 535         LOGFLUSH;
 536
 537         superblockend = false;
 538         state->bptr->flags = BBFINISHED;
 539
 540         /* prevent compiler warnings */
 541
 542
 543         /* determine the active exception handlers for this block */
 544         /* XXX could use a faster algorithm with sorted lists or  */
 545         /* something?                                             */
 546         len = 0;
 547         for (ex = state->jd->exceptiontable; ex ; ex = ex->down) {
 548                 if ((ex->start->nr <= state->bptr->nr) && (ex->end->nr > state->bptr->nr)) {
 549                         LOG1("active handler L%03d", ex->handler->nr);
 550                         state->handlers[len++] = ex;
 551                 }
 552         }
 553         state->handlers[len] = NULL;
 554
 555         /* init variable types at the start of this block */
 556         typevector_copy_inplace(state->bptr->inlocals, jd->var, state->numlocals);
 557
 558         DOLOG(show_basicblock(jd, state->bptr, SHOW_STACK));
 559         DOLOG(typecheck_print_vararray(stdout, jd, state->bptr->invars,
 560                                 state->bptr->indepth));
 561         DOLOG(typevector_print(stdout, jd->var, state->numlocals));
 562         LOGNL; LOGFLUSH;
 563
 564         /* loop over the instructions */
 565         len = state->bptr->icount;
 566         state->iptr = state->bptr->iinstr;
 567         while (--len >= 0)  {
 568                 TYPECHECK_COUNT(stat_ins);
 569
 570                 iptr = state->iptr;
 571
 572                 DOLOG(typevector_print(stdout, jd->var, state->numlocals));
 573                 LOGNL; LOGFLUSH;
 574                 DOLOG(show_icmd(jd, state->iptr, false, SHOW_STACK)); LOGNL; LOGFLUSH;
 575
 576                 opcode = iptr->opc;
 577                 maythrow = false;
 578
 579                 switch (opcode) {
 580
 581                         /* include generated code for ICMDs verification */
 582
 583 #define TYPECHECK_VARIABLESBASED
 584 #define STATE  state
 585 #define METHOD (state->m)
 586 #define IPTR   iptr
 587 #define BPTR   (state->bptr)
 588 #include <typecheck-variablesbased-gen.inc>
 589 #undef  STATE
 590 #undef  METHOD
 591 #undef  IPTR
 592 #undef  BPTR
 593 #undef  TYPECHECK_VARIABLESBASED
 594
 595                         default:
 596                                 LOG1("ICMD %d\n", opcode);
 597                                 TYPECHECK_VERIFYERROR_bool("Missing ICMD code during typecheck");
 598                 }
 599
 600                 /* reach exception handlers for this instruction */
 601
 602                 if (maythrow) {
 603                         TYPECHECK_COUNT(stat_ins_maythrow);
 604                         TYPECHECK_MARK(state->stat_maythrow);
 605                         LOG("reaching exception handlers");
 606                         i = 0;
 607                         while (state->handlers[i]) {
 608                                 TYPECHECK_COUNT(stat_handlers_reached);
 609                                 if (state->handlers[i]->catchtype.any)
 610                                         VAR(state->exinvars)->typeinfo.typeclass = state->handlers[i]->catchtype;
 611                                 else
 612                                         VAR(state->exinvars)->typeinfo.typeclass.cls = class_java_lang_Throwable;
 613                                 if (!typestate_reach(state,
 614                                                 state->handlers[i]->handler,
 615                                                 &(state->exinvars), jd->var, 1))
 616                                         return false;
 617                                 i++;
 618                         }
 619                 }
 620
 621                 LOG("\t\tnext instruction");
 622                 state->iptr++;
 623         } /* while instructions */
 624
 625         LOG("instructions done");
 626         LOGSTR("RESULT=> ");
 627         DOLOG(typecheck_print_vararray(stdout, jd, state->bptr->outvars,
 628                                 state->bptr->outdepth));
 629         DOLOG(typevector_print(stdout, jd->var, state->numlocals));
 630         LOGNL; LOGFLUSH;
 631
 632         /* propagate stack and variables to the following block */
 633         if (!superblockend) {
 634                 LOG("reaching following block");
 635                 tbptr = state->bptr->next;
 636                 while (tbptr->flags == BBDELETED) {
 637                         tbptr = tbptr->next;
 638 #ifdef TYPECHECK_DEBUG
 639                         /* this must be checked in parse.c */
 640                         if ((tbptr->nr) >= state->basicblockcount)
 641                                 TYPECHECK_VERIFYERROR_bool("Control flow falls off the last block");
 642 #endif
 643                 }
 644                 if (!typestate_reach(state,tbptr,state->bptr->outvars, jd->var,
 645                                         state->bptr->outdepth))
 646                         return false;
 647         }
 648
 649         /* We may have to restore the types of the instack slots. They
 650          * have been saved if an <init> call inside the block has
 651          * modified the instack types. (see INVOKESPECIAL) */
 652
 653         if (state->savedinvars)
 654                 typestate_restore_invars(state);
 655
 656         return true;
 657 }
 658
 659
 660 /****************************************************************************/
 661 /* typecheck()                                                              */
 662 /* This is the main function of the bytecode verifier. It is called         */
 663 /* directly after analyse_stack.                                            */
 664 /*                                                                          */
 665 /* IN:                                                                      */
 666 /*    meth.............the method to verify                                 */
 667 /*    cdata............codegendata for the method                           */
 668 /*    rdata............registerdata for the method                          */
 669 /*                                                                          */
 670 /* RETURN VALUE:                                                            */
 671 /*     true.............successful verification                             */
 672 /*     false............an exception has been thrown                        */
 673 /*                                                                          */
 674 /****************************************************************************/
 675
 676 #define MAXPARAMS 255
 677
 678 bool typecheck(jitdata *jd)
 679 {
 680         methodinfo     *meth;
 681         codegendata    *cd;
 682         varinfo        *savedlocals;
 683         verifier_state  state;             /* current state of the verifier */
 684         s4              i;
 685         s4              t;
 686
 687         /* collect statistics */
 688
 689 #ifdef TYPECHECK_STATISTICS
 690         int count_iterations = 0;
 691         TYPECHECK_COUNT(stat_typechecked);
 692         TYPECHECK_COUNT_FREQ(stat_locals,jd->maxlocals,STAT_LOCALS);
 693         TYPECHECK_COUNT_FREQ(stat_blocks,cdata->method->basicblockcount/10,STAT_BLOCKS);
 694         TYPECHECK_COUNTIF(cdata->method->exceptiontablelength != 0,stat_methods_with_handlers);
 695         state.stat_maythrow = false;
 696 #endif
 697
 698         /* get required compiler data */
 699
 700         meth = jd->m;
 701         cd   = jd->cd;
 702
 703         /* some logging on entry */
 704
 705
 706     LOGSTR("\n==============================================================================\n");
 707     DOLOG( show_method(jd, SHOW_STACK) );
 708     LOGSTR("\n==============================================================================\n");
 709     LOGMETHOD("Entering typecheck: ",cd->method);
 710
 711         /* initialize the verifier state */
 712
 713         state.m = meth;
 714         state.jd = jd;
 715         state.cd = cd;
 716         state.basicblockcount = jd->basicblockcount;
 717         state.basicblocks = jd->basicblocks;
 718         state.savedindices = NULL;
 719         state.savedinvars = NULL;
 720
 721         /* check that the basicblock numbers are valid */
 722
 723 #if !defined(NDEBUG)
 724         jit_check_basicblock_numbers(jd);
 725 #endif
 726
 727         /* check if this method is an instance initializer method */
 728
 729     state.initmethod = (state.m->name == utf_init);
 730
 731         /* initialize the basic block flags for the following CFG traversal */
 732
 733         typecheck_init_flags(&state, BBFINISHED);
 734
 735     /* number of local variables */
 736
 737     /* In <init> methods we use an extra local variable to indicate whether */
 738     /* the 'this' reference has been initialized.                           */
 739         /*         TYPE_VOID...means 'this' has not been initialized,           */
 740         /*         TYPE_INT....means 'this' has been initialized.               */
 741
 742     state.numlocals = state.jd->localcount;
 743         state.validlocals = state.numlocals;
 744     if (state.initmethod)
 745                 state.numlocals++; /* VERIFIER_EXTRA_LOCALS */
 746
 747         state.reverselocalmap = DMNEW(s4, state.validlocals);
 748         for (i=0; i<jd->maxlocals; ++i)
 749                 for (t=0; t<5; ++t) {
 750                         s4 varindex = jd->local_map[5*i + t];
 751                         if (varindex >= 0)
 752                                 state.reverselocalmap[varindex] = i;
 753                 }
 754
 755         DOLOG(
 756                 LOG("reverselocalmap:");
 757                 for (i=0; i<state.validlocals; ++i) {
 758                         LOG2("    %i => javaindex %i", i, state.reverselocalmap[i]);
 759                 });
 760
 761     /* allocate the buffer of active exception handlers */
 762
 763     state.handlers = DMNEW(exception_entry*, state.jd->exceptiontablelength + 1);
 764
 765         /* save local variables */
 766
 767         savedlocals = DMNEW(varinfo, state.numlocals);
 768         MCOPY(savedlocals, jd->var, varinfo, state.numlocals);
 769
 770         /* initialized local variables of first block */
 771
 772         if (!typecheck_init_locals(&state, true))
 773                 return false;
 774
 775     /* initialize invars of exception handlers */
 776
 777         state.exinvars = state.numlocals;
 778         VAR(state.exinvars)->type = TYPE_ADR;
 779         typeinfo_init_classinfo(&(VAR(state.exinvars)->typeinfo),
 780                                                         class_java_lang_Throwable); /* changed later */
 781
 782     LOG("Exception handler stacks set.\n");
 783
 784     /* loop while there are still blocks to be checked */
 785     do {
 786                 TYPECHECK_COUNT(count_iterations);
 787
 788         state.repeat = false;
 789
 790         state.bptr = state.basicblocks;
 791
 792         for (; state.bptr; state.bptr = state.bptr->next) {
 793             LOGSTR1("---- BLOCK %04d, ",state.bptr->nr);
 794             LOGSTR1("blockflags: %d\n",state.bptr->flags);
 795             LOGFLUSH;
 796
 797                     /* verify reached block */
 798             if (state.bptr->flags == BBTYPECHECK_REACHED) {
 799                 if (!handle_basic_block(&state))
 800                                         return false;
 801             }
 802         } /* for blocks */
 803
 804         LOGIF(state.repeat,"state.repeat == true");
 805     } while (state.repeat);
 806
 807         /* statistics */
 808
 809 #ifdef TYPECHECK_STATISTICS
 810         LOG1("Typechecker did %4d iterations",count_iterations);
 811         TYPECHECK_COUNT_FREQ(stat_iterations,count_iterations,STAT_ITERATIONS);
 812         TYPECHECK_COUNTIF(state.jsrencountered,stat_typechecked_jsr);
 813         TYPECHECK_COUNTIF(state.stat_maythrow,stat_methods_maythrow);
 814 #endif
 815
 816         /* reset the flags of blocks we haven't reached */
 817
 818         typecheck_reset_flags(&state);
 819
 820         /* restore locals */
 821
 822         MCOPY(jd->var, savedlocals, varinfo, state.numlocals);
 823
 824         /* everything's ok */
 825
 826     LOGimp("exiting typecheck");
 827         return true;
 828 }
 829 #endif /* ENABLE_VERIFIER */
 830
 831 /*
 832  * These are local overrides for various environment variables in Emacs.
 833  * Please do not remove this and leave it at the end of the file, where
 834  * Emacs will automagically detect them.
 835  * ---------------------------------------------------------------------
 836  * Local variables:
 837  * mode: c
 838  * indent-tabs-mode: t
 839  * c-basic-offset: 4
 840  * tab-width: 4
 841  * End:
 842  * vim:noexpandtab:sw=4:ts=4:
 843  */