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