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 5777 2006-10-13 18:25:21Z edwin $
  32
  33 */
  34
  35 /*
  36
  37 What's the purpose of the `typechecker`?
  38 ----------------------------------------
  39
  40 The typechecker analyses (the intermediate repr. of) the bytecode of
  41 each method and ensures that for each instruction the values on the
  42 stack and in local variables are of the correct type whenever the
  43 instruction is executed.
  44
  45 type checking is a mandatory part of bytecode verification.
  46
  47
  48 How does the typechecker work?
  49 ------------------------------
  50
  51 The JVM stack and the local variables are not statically typed, so the
  52 typechecker has to *infer* the static types of stack slots and local
  53 variables at each point of the method. The JVM spec imposes a lot of
  54 restrictions on the bytecode in order to guarantee that this is always
  55 possible.
  56
  57 Basically the typechecker solves the data flow equations of the method.
  58 This is done in the usual way for a forward data flow analysis: Starting
  59 from the entry point of the method the typechecker follows the CFG and
  60 records the type of each stack slot and local variable at each point[1].
  61 When two or more control flow paths merge at a point, the union of the
  62 types for each slot/variable is taken. The algorithm continues to follow
  63 all possible paths[2] until the recorded types do not change anymore (ie.
  64 the equations have been solved).
  65
  66 If the solution has been reached and the resulting types are valid for
  67 all instructions, then type checking terminates with success, otherwise
  68 an exception is thrown.
  69
  70
  71 Why is this code so damn complicated?
  72 -------------------------------------
  73
  74 Short answer: The devil's in the details.
  75
  76 While the basic operation of the typechecker is no big deal, there are
  77 many properties of Java bytecode which make type checking hard. Some of
  78 them are not even addressed in the JVM spec. Some problems and their
  79 solutions:
  80
  81 *) Finding a good representation of the union of two reference types is
  82 difficult because of multiple inheritance of interfaces.
  83
  84         Solution: The typeinfo system can represent such "merged" types by a
  85         list of proper subclasses of a class. Example:
  86
  87                 typeclass=java.lang.Object merged={ InterfaceA, InterfaceB }
  88
  89         represents the result of merging two interface types "InterfaceA"
  90         and "InterfaceB".
  91
  92 *) When the code of a method is verified, there may still be unresolved
  93 references to classes/methods/fields in the code, which we may not force
  94 to be resolved eagerly. (A similar problem arises because of the special
  95 checks for protected members.)
  96
  97         Solution: The typeinfo system knows how to deal with unresolved
  98         class references. Whenever a check has to be performed for an
  99         unresolved type, the type is annotated with constraints representing
 100         the check. Later, when the type is resolved, the constraints are
 101         checked. (See the constrain_unresolved_... and the resolve_...
 102         methods.)[3]
 103
 104 *) Checks for uninitialized object instances are hard because after the
 105 invocation of <init> on an uninitialized object *all* slots/variables
 106 referring to this object (and exactly those slots/variables) must be
 107 marked as initialized.
 108
 109         Solution: The JVM spec describes a solution, which has been
 110         implemented in this typechecker.
 111
 112 Note that some checks mentioned in the JVM spec are unnecessary[4] and
 113 not performed by either the reference implementation, or this implementation.
 114
 115
 116 --- Footnotes
 117
 118 [1] Actually only the types of slots/variables at the start of each
 119 basic block are remembered. Within a basic block the algorithm only keeps
 120 the types of the slots/variables for the "current" instruction which is
 121 being analysed.
 122
 123 [2] Actually the algorithm iterates through the basic block list until
 124 there are no more changes. Theoretically it would be wise to sort the
 125 basic blocks topologically beforehand, but the number of average/max
 126 iterations observed is so low, that this was not deemed necessary.
 127
 128 [3] This is similar to a method proposed by: Alessandro Coglio et al., A
 129 Formal Specification of Java Class Loading, Technical Report, Kestrel
 130 Institute April 2000, revised July 2000
 131 http://www.kestrel.edu/home/people/coglio/loading.pdf
 132 An important difference is that Coglio's subtype constraints are checked
 133 after loading, while our constraints are checked when the field/method
 134 is accessed for the first time, so we can guarantee lexically correct
 135 error reporting.
 136
 137 [4] Alessandro Coglio
 138     Improving the official specification of Java bytecode verification
 139     Proceedings of the 3rd ECOOP Workshop on Formal Techniques for Java Programs
 140     June 2001
 141     citeseer.ist.psu.edu/article/coglio03improving.html
 142 */
 143
 144 #include "config.h"
 145 #include "vm/types.h"
 146 #include "vm/global.h"
 147
 148 #include <assert.h>
 149 #include <string.h>
 150
 151 #ifdef ENABLE_VERIFIER
 152
 153 #include "mm/memory.h"
 154 #include "toolbox/logging.h"
 155 #include "native/native.h"
 156 #include "vm/builtin.h"
 157 #include "vm/jit/patcher.h"
 158 #include "vm/loader.h"
 159 #include "vm/options.h"
 160 #include "vm/jit/jit.h"
 161 #include "vm/jit/show.h"
 162 #include "vm/access.h"
 163 #include "vm/resolve.h"
 164 #include "vm/exceptions.h"
 165
 166 #include <typecheck-common.h>
 167
 168
 169 /****************************************************************************/
 170 /* MACROS FOR VARIABLE TYPE CHECKING                                        */
 171 /****************************************************************************/
 172
 173 #define TYPECHECK_CHECK_TYPE(i,tp,msg)                               \
 174     do {                                                             \
 175         if (VAR(i)->type != (tp)) {                                  \
 176             exceptions_throw_verifyerror(state->m, (msg));           \
 177             return false;                                            \
 178         }                                                            \
 179     } while (0)
 180
 181 #define TYPECHECK_INT(i)                                             \
 182     TYPECHECK_CHECK_TYPE(i,TYPE_INT,"Expected to find integer value")
 183 #define TYPECHECK_LNG(i)                                             \
 184     TYPECHECK_CHECK_TYPE(i,TYPE_LNG,"Expected to find long value")
 185 #define TYPECHECK_FLT(i)                                             \
 186     TYPECHECK_CHECK_TYPE(i,TYPE_FLT,"Expected to find float value")
 187 #define TYPECHECK_DBL(i)                                             \
 188     TYPECHECK_CHECK_TYPE(i,TYPE_DBL,"Expected to find double value")
 189 #define TYPECHECK_ADR(i)                                             \
 190     TYPECHECK_CHECK_TYPE(i,TYPE_ADR,"Expected to find object value")
 191
 192 #define TYPECHECK_INT_OP(o)  TYPECHECK_INT((o).varindex)
 193 #define TYPECHECK_LNG_OP(o)  TYPECHECK_LNG((o).varindex)
 194 #define TYPECHECK_FLT_OP(o)  TYPECHECK_FLT((o).varindex)
 195 #define TYPECHECK_DBL_OP(o)  TYPECHECK_DBL((o).varindex)
 196 #define TYPECHECK_ADR_OP(o)  TYPECHECK_ADR((o).varindex)
 197
 198
 199 /****************************************************************************/
 200 /* TYPESTACK MACROS AND FUNCTIONS                                           */
 201 /*                                                                          */
 202 /* These macros and functions act on the 'type stack', which is a shorthand */
 203 /* for the types of the stackslots of the current stack. The type of a      */
 204 /* stack slot is usually described by a TYPE_* constant and -- for TYPE_ADR */
 205 /* -- by the typeinfo of the slot. The only thing that makes the type stack */
 206 /* more complicated are returnAddresses of local subroutines, because a     */
 207 /* single stack slot may contain a set of more than one possible return     */
 208 /* address. This is handled by 'return address sets'. A return address set  */
 209 /* is kept as a linked list dangling off the typeinfo of the stack slot.    */
 210 /****************************************************************************/
 211
 212 /* typecheck_copy_types ********************************************************
 213
 214    Copy the types of the source variables to the destination variables.
 215
 216    IN:
 217            state............current verifier state
 218            srcvars..........array of variable indices to copy
 219            dstvars..........array of the destination variables
 220            n................number of variables to copy
 221
 222    RETURN VALUE:
 223        true.............success
 224            false............an exception has been thrown
 225
 226 *******************************************************************************/
 227
 228 static bool
 229 typecheck_copy_types(verifier_state *state, s4 *srcvars, s4 *dstvars, s4 n)
 230 {
 231         s4 i;
 232         varinfo *sv;
 233         varinfo *dv;
 234         jitdata *jd = state->jd;
 235
 236         for (i=0; i < n; ++i, ++srcvars, ++dstvars) {
 237                 sv = VAR(*srcvars);
 238                 dv = VAR(*dstvars);
 239
 240                 dv->type = sv->type;
 241                 if (dv->type == TYPE_ADR) {
 242                         TYPEINFO_CLONE(sv->typeinfo,dv->typeinfo);
 243                 }
 244         }
 245         return true;
 246 }
 247
 248
 249 /* typecheck_merge_types *******************************************************
 250
 251    Merge the types of the source variables into the destination variables.
 252
 253    IN:
 254        state............current state of the verifier
 255            srcvars..........source variable indices
 256            dstvars..........destination variable indices
 257            n................number of variables
 258
 259    RETURN VALUE:
 260        typecheck_TRUE...the destination variables have been modified
 261            typecheck_FALSE..the destination variables are unchanged
 262            typecheck_FAIL...an exception has been thrown
 263
 264 *******************************************************************************/
 265
 266 static typecheck_result
 267 typecheck_merge_types(verifier_state *state,s4 *srcvars, s4 *dstvars, s4 n)
 268 {
 269         s4 i;
 270         varinfo *sv;
 271         varinfo *dv;
 272         jitdata *jd = state->jd;
 273         typecheck_result r;
 274         bool changed = false;
 275
 276         for (i=0; i < n; ++i, ++srcvars, ++dstvars) {
 277                 sv = VAR(*srcvars);
 278                 dv = VAR(*dstvars);
 279
 280                 if (dv->type != sv->type) {
 281                         exceptions_throw_verifyerror(state->m,"Stack type mismatch");
 282                         return typecheck_FAIL;
 283                 }
 284                 if (dv->type == TYPE_ADR) {
 285                         if (TYPEINFO_IS_PRIMITIVE(dv->typeinfo)) {
 286                                 /* dv has returnAddress type */
 287                                 if (!TYPEINFO_IS_PRIMITIVE(sv->typeinfo)) {
 288                                         exceptions_throw_verifyerror(state->m,"Merging returnAddress with reference");
 289                                         return typecheck_FAIL;
 290                                 }
 291                         }
 292                         else {
 293                                 /* dv has reference type */
 294                                 if (TYPEINFO_IS_PRIMITIVE(sv->typeinfo)) {
 295                                         exceptions_throw_verifyerror(state->m,"Merging reference with returnAddress");
 296                                         return typecheck_FAIL;
 297                                 }
 298                                 r = typeinfo_merge(state->m,&(dv->typeinfo),&(sv->typeinfo));
 299                                 if (r == typecheck_FAIL)
 300                                         return r;
 301                                 changed |= r;
 302                         }
 303                 }
 304         }
 305         return changed;
 306 }
 307
 308
 309 /* typestate_merge *************************************************************
 310
 311    Merge the types of one state into the destination state.
 312
 313    IN:
 314        state............current state of the verifier
 315            dstvars..........indices of the destinations invars
 316            dstlocals........the destinations inlocals
 317            srcvars..........indices of the source's outvars
 318            srclocals........the source locals
 319            n................number of invars (== number of outvars)
 320
 321    RETURN VALUE:
 322        typecheck_TRUE...destination state has been modified
 323            typecheck_FALSE..destination state has not been modified
 324            typecheck_FAIL...an exception has been thrown
 325
 326 *******************************************************************************/
 327
 328 static typecheck_result
 329 typestate_merge(verifier_state *state,
 330                                 s4 *srcvars, varinfo *srclocals,
 331                                 s4 *dstvars, varinfo *dstlocals,
 332                                 s4 n)
 333 {
 334         bool changed = false;
 335         typecheck_result r;
 336
 337         /* The stack is always merged. If there are returnAddresses on
 338          * the stack they are ignored in this step. */
 339
 340         r = typecheck_merge_types(state, srcvars, dstvars, n);
 341         if (r == typecheck_FAIL)
 342                 return r;
 343         changed |= r;
 344
 345         /* merge the locals */
 346
 347         r = typevector_merge(state->m, dstlocals, srclocals, state->numlocals);
 348         if (r == typecheck_FAIL)
 349                 return r;
 350         return changed | r;
 351 }
 352
 353
 354 /* typestate_reach *************************************************************
 355
 356    Reach a destination block and propagate stack and local variable types
 357
 358    IN:
 359        state............current state of the verifier
 360            destblock........destination basic block
 361            srcvars..........variable indices of the outvars to propagate
 362            srclocals........local variables to propagate
 363            n................number of srcvars
 364
 365    OUT:
 366        state->repeat....set to true if the verifier must iterate again
 367                             over the basic blocks
 368
 369    RETURN VALUE:
 370        true.............success
 371            false............an exception has been thrown
 372
 373 *******************************************************************************/
 374
 375 static bool
 376 typestate_reach(verifier_state *state,
 377                                 basicblock *destblock,
 378                                 s4 *srcvars, varinfo *srclocals, s4 n)
 379 {
 380         varinfo *destloc;
 381         bool changed = false;
 382         typecheck_result r;
 383
 384         LOG1("reaching block L%03d",destblock->nr);
 385         TYPECHECK_COUNT(stat_reached);
 386
 387         destloc = destblock->inlocals;
 388
 389         if (destblock->flags == BBTYPECHECK_UNDEF) {
 390                 /* The destblock has never been reached before */
 391
 392                 TYPECHECK_COUNT(stat_copied);
 393                 LOG1("block L%03d reached first time",destblock->nr);
 394
 395                 if (!typecheck_copy_types(state, srcvars, destblock->invars, n))
 396                         return false;
 397                 typevector_copy_inplace(srclocals, destloc, state->numlocals);
 398                 changed = true;
 399         }
 400         else {
 401                 /* The destblock has already been reached before */
 402
 403                 TYPECHECK_COUNT(stat_merged);
 404                 LOG1("block L%03d reached before", destblock->nr);
 405
 406                 r = typestate_merge(state, srcvars, srclocals,
 407                                 destblock->invars, destblock->inlocals, n);
 408                 if (r == typecheck_FAIL)
 409                         return false;
 410                 changed = r;
 411                 TYPECHECK_COUNTIF(changed,stat_merging_changed);
 412         }
 413
 414         if (changed) {
 415                 LOG("changed!");
 416                 destblock->flags = BBTYPECHECK_REACHED;
 417                 if (destblock <= state->bptr) {
 418                         LOG("REPEAT!");
 419                         state->repeat = true;
 420                 }
 421         }
 422         return true;
 423 }
 424
 425
 426 /* typestate_save_invars *******************************************************
 427
 428    Save the invars of the current basic block in the space reserved by
 429    parse.
 430
 431    This function must be called before an instruction modifies a variable
 432    that is an invar of the current block. In such cases the invars of the
 433    block must be saved, and restored at the end of the analysis of this
 434    basic block, so that the invars again reflect the *input* to this basic
 435    block (and do not randomly contain types that appear within the block).
 436
 437    IN:
 438        state............current state of the verifier
 439
 440 *******************************************************************************/
 441
 442 static void
 443 typestate_save_invars(verifier_state *state)
 444 {
 445         s4 i, index;
 446         s4 *pindex;
 447
 448         LOG("saving invars");
 449
 450         if (!state->savedindices) {
 451                 LOG("allocating savedindices buffer");
 452                 pindex = DMNEW(s4, state->m->maxstack);
 453                 state->savedindices = pindex;
 454                 index = state->numlocals + VERIFIER_EXTRA_VARS;
 455                 for (i=0; i<state->m->maxstack; ++i)
 456                         *pindex++ = index++;
 457         }
 458
 459         /* save types */
 460
 461         typecheck_copy_types(state, state->bptr->invars, state->savedindices,
 462                         state->bptr->indepth);
 463
 464         /* set the invars of the block to the saved variables */
 465         /* and remember the original invars                   */
 466
 467         state->savedinvars = state->bptr->invars;
 468         state->bptr->invars = state->savedindices;
 469 }
 470
 471
 472 /* typestate_restore_invars  ***************************************************
 473
 474    Restore the invars of the current basic block that have been previously
 475    saved by `typestate_save_invars`.
 476
 477    IN:
 478        state............current state of the verifier
 479
 480 *******************************************************************************/
 481
 482 static void
 483 typestate_restore_invars(verifier_state *state)
 484 {
 485         TYPECHECK_COUNT(stat_savedstack);
 486         LOG("restoring saved invars");
 487
 488         /* restore the invars pointer */
 489
 490         state->bptr->invars = state->savedinvars;
 491
 492         /* copy the types back */
 493
 494         typecheck_copy_types(state, state->savedindices, state->bptr->invars,
 495                         state->bptr->indepth);
 496
 497         /* mark that there are no saved invars currently */
 498
 499         state->savedinvars = NULL;
 500 }
 501
 502
 503 /****************************************************************************/
 504 /* MISC MACROS                                                              */
 505 /****************************************************************************/
 506
 507 #define COPYTYPE(source,dest)                                        \
 508     {if (VAROP(source)->type == TYPE_ADR)                            \
 509             TYPEINFO_COPY(VAROP(source)->typeinfo,VAROP(dest)->typeinfo);}
 510
 511
 512 /* verify_fieldaccess **********************************************************
 513
 514    Verify an ICMD_{GET,PUT}{STATIC,FIELD}(CONST)?
 515
 516    IN:
 517        state............the current state of the verifier
 518
 519    RETURN VALUE:
 520        true.............successful verification,
 521            false............an exception has been thrown.
 522
 523 *******************************************************************************/
 524
 525 static bool
 526 verify_fieldaccess(verifier_state *state,
 527                                    varinfo *instance,
 528                                    varinfo *value)
 529 {
 530         jitdata *jd;
 531
 532         jd = state->jd;
 533
 534 #define TYPECHECK_VARIABLESBASED
 535 #define EXCEPTION  do { return false; } while (0)
 536 #define VERIFY_ERROR(msg)  TYPECHECK_VERIFYERROR_bool(msg)
 537 #include <typecheck-fields.inc>
 538 #undef  EXCEPTION
 539 #undef  VERIFY_ERROR
 540 #undef  TYPECHECK_VARIABLESBASED
 541
 542         return true;
 543 }
 544
 545
 546 /* verify_invocation ***********************************************************
 547
 548    Verify an ICMD_INVOKE* instruction.
 549
 550    IN:
 551        state............the current state of the verifier
 552
 553    RETURN VALUE:
 554        true.............successful verification,
 555            false............an exception has been thrown.
 556
 557 *******************************************************************************/
 558
 559 static bool
 560 verify_invocation(verifier_state *state)
 561 {
 562         jitdata *jd;
 563     varinfo *dv;               /* output variable of current instruction */
 564
 565         jd = state->jd;
 566         dv = VAROP(state->iptr->dst);
 567
 568 #define TYPECHECK_VARIABLESBASED
 569 #define OP1   VAR(state->iptr->sx.s23.s2.args[0])
 570 #include <typecheck-invoke.inc>
 571 #undef  OP1
 572 #undef  TYPECHECK_VARIABLESBASED
 573
 574         return true;
 575 }
 576
 577
 578 /* verify_builtin **************************************************************
 579
 580    Verify the call of a builtin method.
 581
 582    IN:
 583        state............the current state of the verifier
 584
 585    RETURN VALUE:
 586        true.............successful verification,
 587            false............an exception has been thrown.
 588
 589 *******************************************************************************/
 590
 591 static bool
 592 verify_builtin(verifier_state *state)
 593 {
 594         jitdata *jd;
 595     varinfo *dv;               /* output variable of current instruction */
 596
 597         jd = state->jd;
 598         dv = VAROP(state->iptr->dst);
 599
 600 #define TYPECHECK_VARIABLESBASED
 601 #define OP1   state->iptr->sx.s23.s2.args[0]
 602 #include <typecheck-builtins.inc>
 603 #undef  OP1
 604 #undef  TYPECHECK_VARIABLESBASED
 605
 606         return true;
 607 }
 608
 609 /* verify_multianewarray *******************************************************
 610
 611    Verify a MULTIANEWARRAY instruction.
 612
 613    IN:
 614        state............the current state of the verifier
 615
 616    RETURN VALUE:
 617        true.............successful verification,
 618            false............an exception has been thrown.
 619
 620 *******************************************************************************/
 621
 622 static bool
 623 verify_multianewarray(verifier_state *state)
 624 {
 625         classinfo *arrayclass;
 626         arraydescriptor *desc;
 627         s4 i;
 628         jitdata *jd = state->jd;
 629
 630         /* check the array lengths on the stack */
 631         i = state->iptr->s1.argcount;
 632         if (i < 1)
 633                 TYPECHECK_VERIFYERROR_bool("Illegal dimension argument");
 634
 635         while (i--) {
 636                 TYPECHECK_INT(state->iptr->sx.s23.s2.args[i]);
 637         }
 638
 639         /* check array descriptor */
 640         if (INSTRUCTION_IS_RESOLVED(state->iptr)) {
 641                 /* the array class reference has already been resolved */
 642                 arrayclass = state->iptr->sx.s23.s3.c.cls;
 643                 if (!arrayclass)
 644                         TYPECHECK_VERIFYERROR_bool("MULTIANEWARRAY with unlinked class");
 645                 if ((desc = arrayclass->vftbl->arraydesc) == NULL)
 646                         TYPECHECK_VERIFYERROR_bool("MULTIANEWARRAY with non-array class");
 647                 if (desc->dimension < state->iptr->s1.argcount)
 648                         TYPECHECK_VERIFYERROR_bool("MULTIANEWARRAY dimension to high");
 649
 650                 /* set the array type of the result */
 651                 typeinfo_init_classinfo(&(VAROP(state->iptr->dst)->typeinfo), arrayclass);
 652         }
 653         else {
 654                 const char *p;
 655                 constant_classref *cr;
 656
 657                 /* the array class reference is still unresolved */
 658                 /* check that the reference indicates an array class of correct dimension */
 659                 cr = state->iptr->sx.s23.s3.c.ref;
 660                 i = 0;
 661                 p = cr->name->text;
 662                 while (p[i] == '[')
 663                         i++;
 664                 /* { the dimension of the array class == i } */
 665                 if (i < 1)
 666                         TYPECHECK_VERIFYERROR_bool("MULTIANEWARRAY with non-array class");
 667                 if (i < state->iptr->s1.argcount)
 668                         TYPECHECK_VERIFYERROR_bool("MULTIANEWARRAY dimension to high");
 669
 670                 /* set the array type of the result */
 671                 if (!typeinfo_init_class(&(VAROP(state->iptr->dst)->typeinfo),CLASSREF_OR_CLASSINFO(cr)))
 672                         return false;
 673         }
 674
 675         /* set return type */
 676
 677         VAROP(state->iptr->dst)->type = TYPE_ADR;
 678
 679         /* everything ok */
 680         return true;
 681 }
 682
 683
 684 /* typecheck_invalidate_locals *************************************************
 685
 686    Invalidate locals that are overwritten by writing to the given local.
 687
 688    IN:
 689        state............the current state of the verifier
 690            index............the index of the local that is written
 691            twoword..........true, if a two-word type is written
 692
 693 *******************************************************************************/
 694
 695 static void typecheck_invalidate_locals(verifier_state *state, s4 index, bool twoword)
 696 {
 697         s4 i;
 698         s4 t;
 699         s4 mapped;
 700         jitdata *jd = state->jd;
 701         s4 *localmap = jd->local_map;
 702         varinfo *vars = jd->var;
 703
 704         i = state->reverselocalmap[index];
 705
 706         /* invalidate locals of two-word type at index i-1 */
 707
 708         if (i > 0) {
 709                 localmap += 5 * (i-1);
 710                 for (t=0; t<5; ++t) {
 711                         mapped = *localmap++;
 712                         if (mapped >= 0 && IS_2_WORD_TYPE(vars[mapped].type)) {
 713                                 LOG1("invalidate local %d", mapped);
 714                                 vars[mapped].type = TYPE_VOID;
 715                         }
 716                 }
 717         }
 718         else {
 719                 localmap += 5 * i;
 720         }
 721
 722         /* invalidate locals at index i */
 723
 724         for (t=0; t<5; ++t) {
 725                 mapped = *localmap++;
 726                 if (mapped >= 0) {
 727                         LOG1("invalidate local %d", mapped);
 728                         vars[mapped].type = TYPE_VOID;
 729                 }
 730         }
 731
 732         /* if a two-word type is written, invalidate locals at index i+1 */
 733
 734         if (twoword) {
 735                 for (t=0; t<5; ++t) {
 736                         mapped = *localmap++;
 737                         if (mapped >= 0) {
 738                                 LOG1("invalidate local %d", mapped);
 739                                 vars[mapped].type = TYPE_VOID;
 740                         }
 741                 }
 742         }
 743 }
 744
 745
 746 /* macros used by the generated code ******************************************/
 747
 748 #define EXCEPTION          do { return false; } while (0)
 749 #define VERIFY_ERROR(msg)  TYPECHECK_VERIFYERROR_bool(msg)
 750
 751 #define CHECK_LOCAL_TYPE(index, t)                                   \
 752     do {                                                             \
 753         if (!typevector_checktype(jd->var, (index), (t)))            \
 754              VERIFY_ERROR("Local variable type mismatch");           \
 755     } while (0)
 756
 757 #define STORE_LOCAL(t, index)                                        \
 758     do {                                                             \
 759          typecheck_invalidate_locals(state, (index), false);         \
 760          typevector_store(jd->var, (index), (t), NULL);              \
 761     } while (0)
 762
 763 #define STORE_LOCAL_2_WORD(t, index)                                 \
 764     do {                                                             \
 765          typecheck_invalidate_locals(state, (index), true);          \
 766          typevector_store(jd->var, (index), (t), NULL);              \
 767     } while (0)
 768
 769 #define REACH_BLOCK(target)                                          \
 770     do {                                                             \
 771         if (!typestate_reach(state, (target),                        \
 772                              state->bptr->outvars, jd->var,          \
 773                              state->bptr->outdepth))                 \
 774                 return false;                                        \
 775     } while (0)
 776
 777 #define REACH(target)   REACH_BLOCK((target).block)
 778
 779
 780 /* verify_basic_block **********************************************************
 781
 782    Perform bytecode verification of a basic block.
 783
 784    IN:
 785        state............the current state of the verifier
 786
 787    RETURN VALUE:
 788        true.............successful verification,
 789            false............an exception has been thrown.
 790
 791 *******************************************************************************/
 792
 793 static bool
 794 verify_basic_block(verifier_state *state)
 795 {
 796     int opcode;                                      /* current opcode */
 797     int len;                        /* for counting instructions, etc. */
 798     bool superblockend;        /* true if no fallthrough to next block */
 799         instruction *iptr;                      /* the current instruction */
 800     basicblock *tbptr;                   /* temporary for target block */
 801     bool maythrow;               /* true if this instruction may throw */
 802         s4 i;
 803         typecheck_result r;
 804         branch_target_t *table;
 805         lookup_target_t *lookup;
 806         jitdata *jd = state->jd;
 807         exceptiontable *ex;
 808         varinfo constvalue;                               /* for PUT*CONST */
 809         constant_FMIref *fieldref;
 810
 811         LOGSTR1("\n---- BLOCK %04d ------------------------------------------------\n",state->bptr->nr);
 812         LOGFLUSH;
 813         DOLOG(show_basicblock(jd, state->bptr, SHOW_STACK));
 814
 815         superblockend = false;
 816         state->bptr->flags = BBFINISHED;
 817
 818         /* prevent compiler warnings */
 819
 820
 821         /* determine the active exception handlers for this block */
 822         /* XXX could use a faster algorithm with sorted lists or  */
 823         /* something?                                             */
 824         len = 0;
 825         for (ex = state->cd->exceptiontable; ex ; ex = ex->down) {
 826                 if ((ex->start->nr <= state->bptr->nr) && (ex->end->nr > state->bptr->nr)) {
 827                         LOG1("active handler L%03d", ex->handler->nr);
 828                         state->handlers[len++] = ex;
 829                 }
 830         }
 831         state->handlers[len] = NULL;
 832
 833         /* init variable types at the start of this block */
 834         typevector_copy_inplace(state->bptr->inlocals, jd->var, state->numlocals);
 835
 836         DOLOG(typecheck_print_vararray(stdout, jd, state->bptr->invars,
 837                                 state->bptr->indepth));
 838         DOLOG(typevector_print(stdout, jd->var, state->numlocals));
 839         LOGNL; LOGFLUSH;
 840
 841         /* loop over the instructions */
 842         len = state->bptr->icount;
 843         state->iptr = state->bptr->iinstr;
 844         while (--len >= 0)  {
 845                 TYPECHECK_COUNT(stat_ins);
 846
 847                 iptr = state->iptr;
 848
 849                 DOLOG(typevector_print(stdout, jd->var, state->numlocals));
 850                 LOGNL; LOGFLUSH;
 851                 DOLOG(show_icmd(jd, state->iptr, false, SHOW_STACK)); LOGNL; LOGFLUSH;
 852
 853                 opcode = iptr->opc;
 854                 maythrow = false;
 855
 856                 switch (opcode) {
 857
 858                         /* include generated code for ICMDs verification */
 859
 860 #define TYPECHECK_VARIABLESBASED
 861 #define STATE  state
 862 #define METHOD (state->m)
 863 #define IPTR   iptr
 864 #define BPTR   (state->bptr)
 865 #include <typecheck-variablesbased-gen.inc>
 866 #undef  STATE
 867 #undef  METHOD
 868 #undef  IPTR
 869 #undef  BPTR
 870 #undef  TYPECHECK_VARIABLESBASED
 871
 872                         default:
 873                                 LOG1("ICMD %d\n", opcode);
 874                                 TYPECHECK_VERIFYERROR_bool("Missing ICMD code during typecheck");
 875                 }
 876
 877                 /* reach exception handlers for this instruction */
 878
 879                 if (maythrow) {
 880                         TYPECHECK_COUNT(stat_ins_maythrow);
 881                         TYPECHECK_MARK(state->stat_maythrow);
 882                         LOG("reaching exception handlers");
 883                         i = 0;
 884                         while (state->handlers[i]) {
 885                                 TYPECHECK_COUNT(stat_handlers_reached);
 886                                 if (state->handlers[i]->catchtype.any)
 887                                         VAR(state->exinvars)->typeinfo.typeclass = state->handlers[i]->catchtype;
 888                                 else
 889                                         VAR(state->exinvars)->typeinfo.typeclass.cls = class_java_lang_Throwable;
 890                                 if (!typestate_reach(state,
 891                                                 state->handlers[i]->handler,
 892                                                 &(state->exinvars), jd->var, 1))
 893                                         return false;
 894                                 i++;
 895                         }
 896                 }
 897
 898                 LOG("\t\tnext instruction");
 899                 state->iptr++;
 900         } /* while instructions */
 901
 902         LOG("instructions done");
 903         LOGSTR("RESULT=> ");
 904         DOLOG(typecheck_print_vararray(stdout, jd, state->bptr->outvars,
 905                                 state->bptr->outdepth));
 906         DOLOG(typevector_print(stdout, jd->var, state->numlocals));
 907         LOGNL; LOGFLUSH;
 908
 909         /* propagate stack and variables to the following block */
 910         if (!superblockend) {
 911                 LOG("reaching following block");
 912                 tbptr = state->bptr->next;
 913                 while (tbptr->flags == BBDELETED) {
 914                         tbptr = tbptr->next;
 915 #ifdef TYPECHECK_DEBUG
 916                         /* this must be checked in parse.c */
 917                         if ((tbptr->nr) >= state->basicblockcount)
 918                                 TYPECHECK_VERIFYERROR_bool("Control flow falls off the last block");
 919 #endif
 920                 }
 921                 if (!typestate_reach(state,tbptr,state->bptr->outvars, jd->var,
 922                                         state->bptr->outdepth))
 923                         return false;
 924         }
 925
 926         /* We may have to restore the types of the instack slots. They
 927          * have been saved if an <init> call inside the block has
 928          * modified the instack types. (see INVOKESPECIAL) */
 929
 930         if (state->savedinvars)
 931                 typestate_restore_invars(state);
 932
 933         return true;
 934 }
 935
 936
 937 /* verify_init_locals **********************************************************
 938
 939    Initialize the local variables in the verifier state.
 940
 941    IN:
 942        state............the current state of the verifier
 943
 944    RETURN VALUE:
 945        true.............success,
 946            false............an exception has been thrown.
 947
 948 *******************************************************************************/
 949
 950 static bool
 951 verify_init_locals(verifier_state *state)
 952 {
 953         int i;
 954         int index;
 955         varinfo *locals;
 956         varinfo *v;
 957         jitdata *jd = state->jd;
 958         int skip = 0;
 959
 960         locals = state->basicblocks[0].inlocals;
 961
 962         /* allocate parameter descriptors if necessary */
 963
 964         if (!state->m->parseddesc->params)
 965                 if (!descriptor_params_from_paramtypes(state->m->parseddesc,state->m->flags))
 966                         return false;
 967
 968         /* pre-initialize variables as TYPE_VOID */
 969
 970         i = state->numlocals;
 971         v = locals;
 972         while (i--) {
 973                 v->type = TYPE_VOID;
 974                 v++;
 975         }
 976
 977     /* if this is an instance method initialize the "this" ref type */
 978
 979     if (!(state->m->flags & ACC_STATIC)) {
 980                 index = jd->local_map[5*0 + TYPE_ADR];
 981                 if (index != UNUSED) {
 982                         if (state->validlocals < 1)
 983                                 TYPECHECK_VERIFYERROR_bool("Not enough local variables for method arguments");
 984                         v = locals + index;
 985                         v->type = TYPE_ADR;
 986                         if (state->initmethod)
 987                                 TYPEINFO_INIT_NEWOBJECT(v->typeinfo, NULL);
 988                         else
 989                                 typeinfo_init_classinfo(&(v->typeinfo), state->m->class);
 990                 }
 991
 992                 skip = 1;
 993     }
 994
 995     LOG("'this' argument set.\n");
 996
 997     /* the rest of the arguments and the return type */
 998
 999     if (!typeinfo_init_varinfos_from_methoddesc(locals, state->m->parseddesc,
1000                                                                                           state->validlocals,
1001                                                                                           skip, /* skip 'this' pointer */
1002                                                                                           jd->local_map,
1003                                                                                           &state->returntype))
1004                 return false;
1005
1006     LOG("Arguments set.\n");
1007         return true;
1008 }
1009
1010
1011 /****************************************************************************/
1012 /* typecheck()                                                              */
1013 /* This is the main function of the bytecode verifier. It is called         */
1014 /* directly after analyse_stack.                                            */
1015 /*                                                                          */
1016 /* IN:                                                                      */
1017 /*    meth.............the method to verify                                 */
1018 /*    cdata............codegendata for the method                           */
1019 /*    rdata............registerdata for the method                          */
1020 /*                                                                          */
1021 /* RETURN VALUE:                                                            */
1022 /*     true.............successful verification                             */
1023 /*     false............an exception has been thrown                        */
1024 /*                                                                          */
1025 /****************************************************************************/
1026
1027 #define MAXPARAMS 255
1028
1029 bool typecheck(jitdata *jd)
1030 {
1031         methodinfo     *meth;
1032         codegendata    *cd;
1033         varinfo        *savedlocals;
1034         verifier_state  state;             /* current state of the verifier */
1035         s4              i;
1036         s4              t;
1037
1038         /* collect statistics */
1039
1040 #ifdef TYPECHECK_STATISTICS
1041         int count_iterations = 0;
1042         TYPECHECK_COUNT(stat_typechecked);
1043         TYPECHECK_COUNT_FREQ(stat_locals,cdata->maxlocals,STAT_LOCALS);
1044         TYPECHECK_COUNT_FREQ(stat_blocks,cdata->method->basicblockcount/10,STAT_BLOCKS);
1045         TYPECHECK_COUNTIF(cdata->method->exceptiontablelength != 0,stat_methods_with_handlers);
1046         state.stat_maythrow = false;
1047 #endif
1048
1049         /* get required compiler data */
1050
1051         meth = jd->m;
1052         cd   = jd->cd;
1053
1054         /* some logging on entry */
1055
1056
1057     LOGSTR("\n==============================================================================\n");
1058     DOLOG( show_method(jd, SHOW_STACK) );
1059     LOGSTR("\n==============================================================================\n");
1060     LOGMETHOD("Entering typecheck: ",cd->method);
1061
1062         /* initialize the verifier state */
1063
1064         state.m = meth;
1065         state.jd = jd;
1066         state.cd = cd;
1067         state.basicblockcount = jd->basicblockcount;
1068         state.basicblocks = jd->basicblocks;
1069         state.savedindices = NULL;
1070         state.savedinvars = NULL;
1071
1072         /* check if this method is an instance initializer method */
1073
1074     state.initmethod = (state.m->name == utf_init);
1075
1076         /* initialize the basic block flags for the following CFG traversal */
1077
1078         typecheck_init_flags(&state, BBFINISHED);
1079
1080     /* number of local variables */
1081
1082     /* In <init> methods we use an extra local variable to indicate whether */
1083     /* the 'this' reference has been initialized.                           */
1084         /*         TYPE_VOID...means 'this' has not been initialized,           */
1085         /*         TYPE_INT....means 'this' has been initialized.               */
1086
1087     state.numlocals = state.jd->localcount;
1088         state.validlocals = state.numlocals;
1089     if (state.initmethod)
1090                 state.numlocals++; /* VERIFIER_EXTRA_LOCALS */
1091
1092         state.reverselocalmap = DMNEW(s4, state.validlocals);
1093         for (i=0; i<jd->m->maxlocals; ++i)
1094                 for (t=0; t<5; ++t) {
1095                         s4 mapped = jd->local_map[5*i + t];
1096                         if (mapped >= 0)
1097                                 state.reverselocalmap[mapped] = i;
1098                 }
1099
1100         DOLOG(
1101                 LOG("reverselocalmap:");
1102                 for (i=0; i<state.validlocals; ++i) {
1103                         LOG2("    %i => javaindex %i", i, state.reverselocalmap[i]);
1104                 });
1105
1106     /* allocate the buffer of active exception handlers */
1107
1108     state.handlers = DMNEW(exceptiontable*, state.cd->exceptiontablelength + 1);
1109
1110         /* save local variables */
1111
1112         savedlocals = DMNEW(varinfo, state.numlocals);
1113         MCOPY(savedlocals, jd->var, varinfo, state.numlocals);
1114
1115         /* initialized local variables of first block */
1116
1117         if (!verify_init_locals(&state))
1118                 return false;
1119
1120     /* initialize invars of exception handlers */
1121
1122         state.exinvars = state.numlocals;
1123         VAR(state.exinvars)->type = TYPE_ADR;
1124         typeinfo_init_classinfo(&(VAR(state.exinvars)->typeinfo),
1125                                                         class_java_lang_Throwable); /* changed later */
1126
1127     LOG("Exception handler stacks set.\n");
1128
1129     /* loop while there are still blocks to be checked */
1130     do {
1131                 TYPECHECK_COUNT(count_iterations);
1132
1133         state.repeat = false;
1134
1135         state.bptr = state.basicblocks;
1136
1137         for (; state.bptr; state.bptr = state.bptr->next) {
1138             LOGSTR1("---- BLOCK %04d, ",state.bptr->nr);
1139             LOGSTR1("blockflags: %d\n",state.bptr->flags);
1140             LOGFLUSH;
1141
1142                     /* verify reached block */
1143             if (state.bptr->flags == BBTYPECHECK_REACHED) {
1144                 if (!verify_basic_block(&state))
1145                                         return false;
1146             }
1147         } /* for blocks */
1148
1149         LOGIF(state.repeat,"state.repeat == true");
1150     } while (state.repeat);
1151
1152         /* statistics */
1153
1154 #ifdef TYPECHECK_STATISTICS
1155         LOG1("Typechecker did %4d iterations",count_iterations);
1156         TYPECHECK_COUNT_FREQ(stat_iterations,count_iterations,STAT_ITERATIONS);
1157         TYPECHECK_COUNTIF(state.jsrencountered,stat_typechecked_jsr);
1158         TYPECHECK_COUNTIF(state.stat_maythrow,stat_methods_maythrow);
1159 #endif
1160
1161         /* reset the flags of blocks we haven't reached */
1162
1163         typecheck_reset_flags(&state);
1164
1165         /* restore locals */
1166
1167         MCOPY(jd->var, savedlocals, varinfo, state.numlocals);
1168
1169         /* everything's ok */
1170
1171     LOGimp("exiting typecheck");
1172         return true;
1173 }
1174 #endif /* ENABLE_VERIFIER */
1175
1176 /*
1177  * These are local overrides for various environment variables in Emacs.
1178  * Please do not remove this and leave it at the end of the file, where
1179  * Emacs will automagically detect them.
1180  * ---------------------------------------------------------------------
1181  * Local variables:
1182  * mode: c
1183  * indent-tabs-mode: t
1184  * c-basic-offset: 4
1185  * tab-width: 4
1186  * End:
1187  * vim:noexpandtab:sw=4:ts=4:
1188  */