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 5746 2006-10-12 10:10:06Z 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 #define ISBUILTIN(v)   (bte->fp == (functionptr) (v))
 512
 513
 514 /* verify_invocation ***********************************************************
 515
 516    Verify an ICMD_INVOKE* instruction.
 517
 518    IN:
 519        state............the current state of the verifier
 520
 521    RETURN VALUE:
 522        true.............successful verification,
 523            false............an exception has been thrown.
 524
 525 *******************************************************************************/
 526
 527 static bool
 528 verify_invocation(verifier_state *state)
 529 {
 530         jitdata *jd;
 531         varinfo *dv;
 532
 533         jd = state->jd;
 534         dv = VAROP(state->iptr->dst);
 535
 536 #include <typecheck-invoke.inc>
 537
 538         return true;
 539 }
 540
 541
 542 /* verify_builtin **************************************************************
 543
 544    Verify the call of a builtin method.
 545
 546    IN:
 547        state............the current state of the verifier
 548
 549    RETURN VALUE:
 550        true.............successful verification,
 551            false............an exception has been thrown.
 552
 553 *******************************************************************************/
 554
 555 static bool
 556 verify_builtin(verifier_state *state)
 557 {
 558         varinfo *dv;
 559         jitdata *jd;
 560
 561         jd = state->jd;
 562         dv = VAROP(state->iptr->dst);
 563
 564 #include <typecheck-builtins.inc>
 565
 566         return true;
 567 }
 568
 569
 570 /* verify_multianewarray *******************************************************
 571
 572    Verify a MULTIANEWARRAY instruction.
 573
 574    IN:
 575        state............the current state of the verifier
 576
 577    RETURN VALUE:
 578        true.............successful verification,
 579            false............an exception has been thrown.
 580
 581 *******************************************************************************/
 582
 583 static bool
 584 verify_multianewarray(verifier_state *state)
 585 {
 586         classinfo *arrayclass;
 587         arraydescriptor *desc;
 588         s4 i;
 589         jitdata *jd = state->jd;
 590
 591         /* check the array lengths on the stack */
 592         i = state->iptr->s1.argcount;
 593         if (i < 1)
 594                 TYPECHECK_VERIFYERROR_bool("Illegal dimension argument");
 595
 596         while (i--) {
 597                 TYPECHECK_INT(state->iptr->sx.s23.s2.args[i]);
 598         }
 599
 600         /* check array descriptor */
 601         if (INSTRUCTION_IS_RESOLVED(state->iptr)) {
 602                 /* the array class reference has already been resolved */
 603                 arrayclass = state->iptr->sx.s23.s3.c.cls;
 604                 if (!arrayclass)
 605                         TYPECHECK_VERIFYERROR_bool("MULTIANEWARRAY with unlinked class");
 606                 if ((desc = arrayclass->vftbl->arraydesc) == NULL)
 607                         TYPECHECK_VERIFYERROR_bool("MULTIANEWARRAY with non-array class");
 608                 if (desc->dimension < state->iptr->s1.argcount)
 609                         TYPECHECK_VERIFYERROR_bool("MULTIANEWARRAY dimension to high");
 610
 611                 /* set the array type of the result */
 612                 typeinfo_init_classinfo(&(VAROP(state->iptr->dst)->typeinfo), arrayclass);
 613         }
 614         else {
 615                 const char *p;
 616                 constant_classref *cr;
 617
 618                 /* the array class reference is still unresolved */
 619                 /* check that the reference indicates an array class of correct dimension */
 620                 cr = state->iptr->sx.s23.s3.c.ref;
 621                 i = 0;
 622                 p = cr->name->text;
 623                 while (p[i] == '[')
 624                         i++;
 625                 /* { the dimension of the array class == i } */
 626                 if (i < 1)
 627                         TYPECHECK_VERIFYERROR_bool("MULTIANEWARRAY with non-array class");
 628                 if (i < state->iptr->s1.argcount)
 629                         TYPECHECK_VERIFYERROR_bool("MULTIANEWARRAY dimension to high");
 630
 631                 /* set the array type of the result */
 632                 if (!typeinfo_init_class(&(VAROP(state->iptr->dst)->typeinfo),CLASSREF_OR_CLASSINFO(cr)))
 633                         return false;
 634         }
 635
 636         /* set return type */
 637
 638         VAROP(state->iptr->dst)->type = TYPE_ADR;
 639
 640         /* everything ok */
 641         return true;
 642 }
 643
 644
 645 /* typecheck_invalidate_locals *************************************************
 646
 647    Invalidate locals that are overwritten by writing to the given local.
 648
 649    IN:
 650        state............the current state of the verifier
 651            index............the index of the local that is written
 652            twoword..........true, if a two-word type is written
 653
 654 *******************************************************************************/
 655
 656 static void typecheck_invalidate_locals(verifier_state *state, s4 index, bool twoword)
 657 {
 658         s4 i;
 659         s4 t;
 660         s4 mapped;
 661         jitdata *jd = state->jd;
 662         s4 *localmap = jd->local_map;
 663         varinfo *vars = jd->var;
 664
 665         i = state->reverselocalmap[index];
 666
 667         /* invalidate locals of two-word type at index i-1 */
 668
 669         if (i > 0) {
 670                 localmap += 5 * (i-1);
 671                 for (t=0; t<5; ++t) {
 672                         mapped = *localmap++;
 673                         if (mapped >= 0 && IS_2_WORD_TYPE(vars[mapped].type)) {
 674                                 LOG1("invalidate local %d", mapped);
 675                                 vars[mapped].type = TYPE_VOID;
 676                         }
 677                 }
 678         }
 679         else {
 680                 localmap += 5 * i;
 681         }
 682
 683         /* invalidate locals at index i */
 684
 685         for (t=0; t<5; ++t) {
 686                 mapped = *localmap++;
 687                 if (mapped >= 0) {
 688                         LOG1("invalidate local %d", mapped);
 689                         vars[mapped].type = TYPE_VOID;
 690                 }
 691         }
 692
 693         /* if a two-word type is written, invalidate locals at index i+1 */
 694
 695         if (twoword) {
 696                 for (t=0; t<5; ++t) {
 697                         mapped = *localmap++;
 698                         if (mapped >= 0) {
 699                                 LOG1("invalidate local %d", mapped);
 700                                 vars[mapped].type = TYPE_VOID;
 701                         }
 702                 }
 703         }
 704 }
 705
 706
 707 /* verify_basic_block **********************************************************
 708
 709    Perform bytecode verification of a basic block.
 710
 711    IN:
 712        state............the current state of the verifier
 713
 714    RETURN VALUE:
 715        true.............successful verification,
 716            false............an exception has been thrown.
 717
 718 *******************************************************************************/
 719
 720 static bool
 721 verify_basic_block(verifier_state *state)
 722 {
 723     int opcode;                                      /* current opcode */
 724     int len;                        /* for counting instructions, etc. */
 725     bool superblockend;        /* true if no fallthrough to next block */
 726         instruction *iptr;                      /* the current instruction */
 727     basicblock *tbptr;                   /* temporary for target block */
 728     bool maythrow;               /* true if this instruction may throw */
 729         unresolved_field *uf;                        /* for field accesses */
 730         constant_FMIref *fieldref;                   /* for field accesses */
 731         s4 i;
 732         typecheck_result r;
 733         resolve_result_t result;
 734         branch_target_t *table;
 735         lookup_target_t *lookup;
 736         jitdata *jd = state->jd;
 737         varinfo *dv;
 738         exceptiontable *ex;
 739
 740         LOGSTR1("\n---- BLOCK %04d ------------------------------------------------\n",state->bptr->nr);
 741         LOGFLUSH;
 742         DOLOG(show_basicblock(jd, state->bptr, SHOW_STACK));
 743
 744         superblockend = false;
 745         state->bptr->flags = BBFINISHED;
 746
 747         /* prevent compiler warnings */
 748
 749         dv = NULL;
 750
 751         /* determine the active exception handlers for this block */
 752         /* XXX could use a faster algorithm with sorted lists or  */
 753         /* something?                                             */
 754         len = 0;
 755         for (ex = state->cd->exceptiontable; ex ; ex = ex->down) {
 756                 if ((ex->start->nr <= state->bptr->nr) && (ex->end->nr > state->bptr->nr)) {
 757                         LOG1("active handler L%03d", ex->handler->nr);
 758                         state->handlers[len++] = ex;
 759                 }
 760         }
 761         state->handlers[len] = NULL;
 762
 763         /* init variable types at the start of this block */
 764         typevector_copy_inplace(state->bptr->inlocals, jd->var, state->numlocals);
 765
 766         DOLOG(typecheck_print_vararray(stdout, jd, state->bptr->invars,
 767                                 state->bptr->indepth));
 768         DOLOG(typevector_print(stdout, jd->var, state->numlocals));
 769         LOGNL; LOGFLUSH;
 770
 771         /* loop over the instructions */
 772         len = state->bptr->icount;
 773         state->iptr = state->bptr->iinstr;
 774         while (--len >= 0)  {
 775                 TYPECHECK_COUNT(stat_ins);
 776
 777                 iptr = state->iptr;
 778
 779                 DOLOG(typevector_print(stdout, jd->var, state->numlocals));
 780                 LOGNL; LOGFLUSH;
 781                 DOLOG(show_icmd(jd, state->iptr, false, SHOW_STACK)); LOGNL; LOGFLUSH;
 782
 783                 opcode = iptr->opc;
 784                 dv = VAROP(iptr->dst);
 785                 maythrow = false;
 786
 787                 switch (opcode) {
 788
 789                         /****************************************/
 790                         /* STACK MANIPULATIONS                  */
 791
 792                         /* We just need to copy the typeinfo */
 793                         /* for slots containing addresses.   */
 794
 795                         case ICMD_MOVE:
 796                         case ICMD_COPY:
 797                                 TYPECHECK_COUNT(stat_ins_stack);
 798                                 COPYTYPE(iptr->s1, iptr->dst);
 799                                 dv->type = VAROP(iptr->s1)->type;
 800                                 break;
 801
 802                                 /****************************************/
 803                                 /* PRIMITIVE VARIABLE ACCESS            */
 804
 805                         case ICMD_ILOAD: if (!typevector_checktype(jd->var,state->iptr->s1.varindex,TYPE_INT))
 806                                                                  TYPECHECK_VERIFYERROR_bool("Local variable type mismatch");
 807                                                          dv->type = TYPE_INT;
 808                                                          break;
 809                         case ICMD_IINC:  if (!typevector_checktype(jd->var,state->iptr->s1.varindex,TYPE_INT))
 810                                                                  TYPECHECK_VERIFYERROR_bool("Local variable type mismatch");
 811                                                          dv->type = TYPE_INT;
 812                                                          break;
 813                         case ICMD_FLOAD: if (!typevector_checktype(jd->var,state->iptr->s1.varindex,TYPE_FLT))
 814                                                                  TYPECHECK_VERIFYERROR_bool("Local variable type mismatch");
 815                                                          dv->type = TYPE_FLT;
 816                                                          break;
 817                         case ICMD_LLOAD: if (!typevector_checktype(jd->var,state->iptr->s1.varindex,TYPE_LNG))
 818                                                                  TYPECHECK_VERIFYERROR_bool("Local variable type mismatch");
 819                                                          dv->type = TYPE_LNG;
 820                                                          break;
 821                         case ICMD_DLOAD: if (!typevector_checktype(jd->var,state->iptr->s1.varindex,TYPE_DBL))
 822                                                                  TYPECHECK_VERIFYERROR_bool("Local variable type mismatch");
 823                                                          dv->type = TYPE_DBL;
 824                                                          break;
 825
 826                         case ICMD_ISTORE:
 827                                                          typecheck_invalidate_locals(state, state->iptr->dst.varindex, false);
 828                                                          typevector_store(jd->var,state->iptr->dst.varindex,TYPE_INT,NULL);
 829                                                          break;
 830                         case ICMD_FSTORE:
 831                                                          typecheck_invalidate_locals(state, state->iptr->dst.varindex, false);
 832                                                          typevector_store(jd->var,state->iptr->dst.varindex,TYPE_FLT,NULL);
 833                                                          break;
 834                         case ICMD_LSTORE:
 835                                                          typecheck_invalidate_locals(state, state->iptr->dst.varindex, true);
 836                                                          typevector_store(jd->var,state->iptr->dst.varindex,TYPE_LNG,NULL);
 837                                                          break;
 838                         case ICMD_DSTORE:
 839                                                          typecheck_invalidate_locals(state, state->iptr->dst.varindex, true);
 840                                                          typevector_store(jd->var,state->iptr->dst.varindex,TYPE_DBL,NULL);
 841                                                          break;
 842
 843                                 /****************************************/
 844                                 /* LOADING ADDRESS FROM VARIABLE        */
 845
 846                         case ICMD_ALOAD:
 847                                 TYPECHECK_COUNT(stat_ins_aload);
 848
 849                                 /* loading a returnAddress is not allowed */
 850                                 if (!TYPEDESC_IS_REFERENCE(*VAROP(state->iptr->s1))) {
 851                                         TYPECHECK_VERIFYERROR_bool("illegal instruction: ALOAD loading non-reference");
 852                                 }
 853                                 TYPEINFO_COPY(VAROP(state->iptr->s1)->typeinfo,dv->typeinfo);
 854                                 dv->type = TYPE_ADR;
 855                                 break;
 856
 857                                 /****************************************/
 858                                 /* STORING ADDRESS TO VARIABLE          */
 859
 860                         case ICMD_ASTORE:
 861                                 typecheck_invalidate_locals(state, state->iptr->dst.varindex, false);
 862
 863                                 if (TYPEINFO_IS_PRIMITIVE(VAROP(state->iptr->s1)->typeinfo)) {
 864                                         typevector_store_retaddr(jd->var,state->iptr->dst.varindex,&(VAROP(state->iptr->s1)->typeinfo));
 865                                 }
 866                                 else {
 867                                         typevector_store(jd->var,state->iptr->dst.varindex,TYPE_ADR,
 868                                                         &(VAROP(state->iptr->s1)->typeinfo));
 869                                 }
 870                                 break;
 871
 872                                 /****************************************/
 873                                 /* LOADING ADDRESS FROM ARRAY           */
 874
 875                         case ICMD_AALOAD:
 876                                 if (!TYPEINFO_MAYBE_ARRAY_OF_REFS(VAROP(state->iptr->s1)->typeinfo))
 877                                         TYPECHECK_VERIFYERROR_bool("illegal instruction: AALOAD on non-reference array");
 878
 879                                 if (!typeinfo_init_component(&VAROP(state->iptr->s1)->typeinfo,&dv->typeinfo))
 880                                         return false;
 881                                 dv->type = TYPE_ADR;
 882                                 maythrow = true;
 883                                 break;
 884
 885                                 /****************************************/
 886                                 /* FIELD ACCESS                         */
 887
 888                         case ICMD_PUTFIELD:
 889                         case ICMD_PUTSTATIC:
 890                         case ICMD_PUTFIELDCONST:
 891                         case ICMD_PUTSTATICCONST:
 892                         case ICMD_GETFIELD:
 893                         case ICMD_GETSTATIC:
 894
 895 #include <typecheck-fields.inc>
 896
 897                                 maythrow = true;
 898                                 break;
 899
 900                                 /****************************************/
 901                                 /* PRIMITIVE ARRAY ACCESS               */
 902
 903                         case ICMD_ARRAYLENGTH:
 904                                 if (!TYPEINFO_MAYBE_ARRAY(VAROP(state->iptr->s1)->typeinfo)
 905                                                 && VAROP(state->iptr->s1)->typeinfo.typeclass.cls != pseudo_class_Arraystub)
 906                                         TYPECHECK_VERIFYERROR_bool("illegal instruction: ARRAYLENGTH on non-array");
 907                                 dv->type = TYPE_INT;
 908                                 maythrow = true;
 909                                 break;
 910
 911                         case ICMD_BALOAD:
 912                                 if (!TYPEINFO_MAYBE_PRIMITIVE_ARRAY(VAROP(state->iptr->s1)->typeinfo,ARRAYTYPE_BOOLEAN)
 913                                                 && !TYPEINFO_MAYBE_PRIMITIVE_ARRAY(VAROP(state->iptr->s1)->typeinfo,ARRAYTYPE_BYTE))
 914                                         TYPECHECK_VERIFYERROR_bool("Array type mismatch");
 915                                 dv->type = TYPE_INT;
 916                                 maythrow = true;
 917                                 break;
 918                         case ICMD_CALOAD:
 919                                 if (!TYPEINFO_MAYBE_PRIMITIVE_ARRAY(VAROP(state->iptr->s1)->typeinfo,ARRAYTYPE_CHAR))
 920                                         TYPECHECK_VERIFYERROR_bool("Array type mismatch");
 921                                 dv->type = TYPE_INT;
 922                                 maythrow = true;
 923                                 break;
 924                         case ICMD_DALOAD:
 925                                 if (!TYPEINFO_MAYBE_PRIMITIVE_ARRAY(VAROP(state->iptr->s1)->typeinfo,ARRAYTYPE_DOUBLE))
 926                                         TYPECHECK_VERIFYERROR_bool("Array type mismatch");
 927                                 dv->type = TYPE_DBL;
 928                                 maythrow = true;
 929                                 break;
 930                         case ICMD_FALOAD:
 931                                 if (!TYPEINFO_MAYBE_PRIMITIVE_ARRAY(VAROP(state->iptr->s1)->typeinfo,ARRAYTYPE_FLOAT))
 932                                         TYPECHECK_VERIFYERROR_bool("Array type mismatch");
 933                                 dv->type = TYPE_FLT;
 934                                 maythrow = true;
 935                                 break;
 936                         case ICMD_IALOAD:
 937                                 if (!TYPEINFO_MAYBE_PRIMITIVE_ARRAY(VAROP(state->iptr->s1)->typeinfo,ARRAYTYPE_INT))
 938                                         TYPECHECK_VERIFYERROR_bool("Array type mismatch");
 939                                 dv->type = TYPE_INT;
 940                                 maythrow = true;
 941                                 break;
 942                         case ICMD_SALOAD:
 943                                 if (!TYPEINFO_MAYBE_PRIMITIVE_ARRAY(VAROP(state->iptr->s1)->typeinfo,ARRAYTYPE_SHORT))
 944                                         TYPECHECK_VERIFYERROR_bool("Array type mismatch");
 945                                 dv->type = TYPE_INT;
 946                                 maythrow = true;
 947                                 break;
 948                         case ICMD_LALOAD:
 949                                 if (!TYPEINFO_MAYBE_PRIMITIVE_ARRAY(VAROP(state->iptr->s1)->typeinfo,ARRAYTYPE_LONG))
 950                                         TYPECHECK_VERIFYERROR_bool("Array type mismatch");
 951                                 dv->type = TYPE_LNG;
 952                                 maythrow = true;
 953                                 break;
 954
 955                         case ICMD_BASTORE:
 956                                 if (!TYPEINFO_MAYBE_PRIMITIVE_ARRAY(VAROP(state->iptr->s1)->typeinfo,ARRAYTYPE_BOOLEAN)
 957                                                 && !TYPEINFO_MAYBE_PRIMITIVE_ARRAY(VAROP(state->iptr->s1)->typeinfo,ARRAYTYPE_BYTE))
 958                                         TYPECHECK_VERIFYERROR_bool("Array type mismatch");
 959                                 maythrow = true;
 960                                 break;
 961                         case ICMD_CASTORE:
 962                                 if (!TYPEINFO_MAYBE_PRIMITIVE_ARRAY(VAROP(state->iptr->s1)->typeinfo,ARRAYTYPE_CHAR))
 963                                         TYPECHECK_VERIFYERROR_bool("Array type mismatch");
 964                                 maythrow = true;
 965                                 break;
 966                         case ICMD_DASTORE:
 967                                 if (!TYPEINFO_MAYBE_PRIMITIVE_ARRAY(VAROP(state->iptr->s1)->typeinfo,ARRAYTYPE_DOUBLE))
 968                                         TYPECHECK_VERIFYERROR_bool("Array type mismatch");
 969                                 maythrow = true;
 970                                 break;
 971                         case ICMD_FASTORE:
 972                                 if (!TYPEINFO_MAYBE_PRIMITIVE_ARRAY(VAROP(state->iptr->s1)->typeinfo,ARRAYTYPE_FLOAT))
 973                                         TYPECHECK_VERIFYERROR_bool("Array type mismatch");
 974                                 maythrow = true;
 975                                 break;
 976                         case ICMD_IASTORE:
 977                                 if (!TYPEINFO_MAYBE_PRIMITIVE_ARRAY(VAROP(state->iptr->s1)->typeinfo,ARRAYTYPE_INT))
 978                                         TYPECHECK_VERIFYERROR_bool("Array type mismatch");
 979                                 maythrow = true;
 980                                 break;
 981                         case ICMD_SASTORE:
 982                                 if (!TYPEINFO_MAYBE_PRIMITIVE_ARRAY(VAROP(state->iptr->s1)->typeinfo,ARRAYTYPE_SHORT))
 983                                         TYPECHECK_VERIFYERROR_bool("Array type mismatch");
 984                                 maythrow = true;
 985                                 break;
 986                         case ICMD_LASTORE:
 987                                 if (!TYPEINFO_MAYBE_PRIMITIVE_ARRAY(VAROP(state->iptr->s1)->typeinfo,ARRAYTYPE_LONG))
 988                                         TYPECHECK_VERIFYERROR_bool("Array type mismatch");
 989                                 maythrow = true;
 990                                 break;
 991
 992                         case ICMD_AASTORE:
 993                                 /* we just check the basic input types and that the           */
 994                                 /* destination is an array of references. Assignability to    */
 995                                 /* the actual array must be checked at runtime, each time the */
 996                                 /* instruction is performed. (See builtin_canstore.)          */
 997                                 TYPECHECK_ADR_OP(state->iptr->sx.s23.s3);
 998                                 TYPECHECK_INT_OP(state->iptr->sx.s23.s2);
 999                                 TYPECHECK_ADR_OP(state->iptr->s1);
1000                                 if (!TYPEINFO_MAYBE_ARRAY_OF_REFS(VAROP(state->iptr->s1)->typeinfo))
1001                                         TYPECHECK_VERIFYERROR_bool("illegal instruction: AASTORE to non-reference array");
1002                                 maythrow = true;
1003                                 break;
1004
1005                         case ICMD_IASTORECONST:
1006                                 if (!TYPEINFO_MAYBE_PRIMITIVE_ARRAY(VAROP(state->iptr->s1)->typeinfo, ARRAYTYPE_INT))
1007                                         TYPECHECK_VERIFYERROR_bool("Array type mismatch");
1008                                 maythrow = true;
1009                                 break;
1010
1011                         case ICMD_LASTORECONST:
1012                                 if (!TYPEINFO_MAYBE_PRIMITIVE_ARRAY(VAROP(state->iptr->s1)->typeinfo, ARRAYTYPE_LONG))
1013                                         TYPECHECK_VERIFYERROR_bool("Array type mismatch");
1014                                 maythrow = true;
1015                                 break;
1016
1017                         case ICMD_BASTORECONST:
1018                                 if (!TYPEINFO_MAYBE_PRIMITIVE_ARRAY(VAROP(state->iptr->s1)->typeinfo, ARRAYTYPE_BOOLEAN)
1019                                                 && !TYPEINFO_MAYBE_PRIMITIVE_ARRAY(VAROP(state->iptr->s1)->typeinfo, ARRAYTYPE_BYTE))
1020                                         TYPECHECK_VERIFYERROR_bool("Array type mismatch");
1021                                 maythrow = true;
1022                                 break;
1023
1024                         case ICMD_CASTORECONST:
1025                                 if (!TYPEINFO_MAYBE_PRIMITIVE_ARRAY(VAROP(state->iptr->s1)->typeinfo, ARRAYTYPE_CHAR))
1026                                         TYPECHECK_VERIFYERROR_bool("Array type mismatch");
1027                                 maythrow = true;
1028                                 break;
1029
1030                         case ICMD_SASTORECONST:
1031                                 if (!TYPEINFO_MAYBE_PRIMITIVE_ARRAY(VAROP(state->iptr->s1)->typeinfo, ARRAYTYPE_SHORT))
1032                                         TYPECHECK_VERIFYERROR_bool("Array type mismatch");
1033                                 maythrow = true;
1034                                 break;
1035
1036                                 /****************************************/
1037                                 /* ADDRESS CONSTANTS                    */
1038
1039                         case ICMD_ACONST:
1040                                 if (state->iptr->flags.bits & INS_FLAG_CLASS) {
1041                                         /* a java.lang.Class reference */
1042                                         TYPEINFO_INIT_JAVA_LANG_CLASS(dv->typeinfo,state->iptr->sx.val.c);
1043                                 }
1044                                 else {
1045                                         if (state->iptr->sx.val.anyptr == NULL)
1046                                                 TYPEINFO_INIT_NULLTYPE(dv->typeinfo);
1047                                         else {
1048                                                 /* string constant (or constant for builtin function) */
1049                                                 typeinfo_init_classinfo(&(dv->typeinfo),class_java_lang_String);
1050                                         }
1051                                 }
1052                                 dv->type = TYPE_ADR;
1053                                 break;
1054
1055                                 /****************************************/
1056                                 /* CHECKCAST AND INSTANCEOF             */
1057
1058                         case ICMD_CHECKCAST:
1059                                 TYPECHECK_ADR_OP(state->iptr->s1);
1060                                 /* returnAddress is not allowed */
1061                                 if (!TYPEINFO_IS_REFERENCE(VAROP(state->iptr->s1)->typeinfo))
1062                                         TYPECHECK_VERIFYERROR_bool("Illegal instruction: CHECKCAST on non-reference");
1063
1064                                 if (!typeinfo_init_class(&(dv->typeinfo),state->iptr->sx.s23.s3.c))
1065                                                 return false;
1066                                 dv->type = TYPE_ADR;
1067                                 maythrow = true;
1068                                 break;
1069
1070                         case ICMD_INSTANCEOF:
1071                                 TYPECHECK_ADR_OP(state->iptr->s1);
1072                                 /* returnAddress is not allowed */
1073                                 if (!TYPEINFO_IS_REFERENCE(VAROP(state->iptr->s1)->typeinfo))
1074                                         TYPECHECK_VERIFYERROR_bool("Illegal instruction: INSTANCEOF on non-reference");
1075                                 dv->type = TYPE_INT;
1076                                 break;
1077
1078                                 /****************************************/
1079                                 /* BRANCH INSTRUCTIONS                  */
1080
1081                         case ICMD_INLINE_GOTO:
1082                                 COPYTYPE(state->iptr->s1,state->iptr->dst);
1083                                 /* FALLTHROUGH! */
1084                         case ICMD_GOTO:
1085                                 superblockend = true;
1086                                 /* FALLTHROUGH! */
1087                         case ICMD_IFNULL:
1088                         case ICMD_IFNONNULL:
1089                         case ICMD_IFEQ:
1090                         case ICMD_IFNE:
1091                         case ICMD_IFLT:
1092                         case ICMD_IFGE:
1093                         case ICMD_IFGT:
1094                         case ICMD_IFLE:
1095                         case ICMD_IF_ICMPEQ:
1096                         case ICMD_IF_ICMPNE:
1097                         case ICMD_IF_ICMPLT:
1098                         case ICMD_IF_ICMPGE:
1099                         case ICMD_IF_ICMPGT:
1100                         case ICMD_IF_ICMPLE:
1101                         case ICMD_IF_ACMPEQ:
1102                         case ICMD_IF_ACMPNE:
1103
1104                         case ICMD_IF_LEQ:
1105                         case ICMD_IF_LNE:
1106                         case ICMD_IF_LLT:
1107                         case ICMD_IF_LGE:
1108                         case ICMD_IF_LGT:
1109                         case ICMD_IF_LLE:
1110
1111                         case ICMD_IF_LCMPEQ:
1112                         case ICMD_IF_LCMPNE:
1113                         case ICMD_IF_LCMPLT:
1114                         case ICMD_IF_LCMPGE:
1115                         case ICMD_IF_LCMPGT:
1116                         case ICMD_IF_LCMPLE:
1117
1118                         case ICMD_IF_FCMPEQ:
1119                         case ICMD_IF_FCMPNE:
1120
1121                         case ICMD_IF_FCMPL_LT:
1122                         case ICMD_IF_FCMPL_GE:
1123                         case ICMD_IF_FCMPL_GT:
1124                         case ICMD_IF_FCMPL_LE:
1125
1126                         case ICMD_IF_FCMPG_LT:
1127                         case ICMD_IF_FCMPG_GE:
1128                         case ICMD_IF_FCMPG_GT:
1129                         case ICMD_IF_FCMPG_LE:
1130
1131                         case ICMD_IF_DCMPEQ:
1132                         case ICMD_IF_DCMPNE:
1133
1134                         case ICMD_IF_DCMPL_LT:
1135                         case ICMD_IF_DCMPL_GE:
1136                         case ICMD_IF_DCMPL_GT:
1137                         case ICMD_IF_DCMPL_LE:
1138
1139                         case ICMD_IF_DCMPG_LT:
1140                         case ICMD_IF_DCMPG_GE:
1141                         case ICMD_IF_DCMPG_GT:
1142                         case ICMD_IF_DCMPG_LE:
1143                                 TYPECHECK_COUNT(stat_ins_branch);
1144
1145                                 /* propagate stack and variables to the target block */
1146                                 if (!typestate_reach(state, state->iptr->dst.block,
1147                                                                          state->bptr->outvars, jd->var,
1148                                                                          state->bptr->outdepth))
1149                                         return false;
1150                                 break;
1151
1152                                 /****************************************/
1153                                 /* SWITCHES                             */
1154
1155                         case ICMD_TABLESWITCH:
1156                                 TYPECHECK_COUNT(stat_ins_switch);
1157
1158                                 table = iptr->dst.table;
1159                                 i = iptr->sx.s23.s3.tablehigh
1160                                         - iptr->sx.s23.s2.tablelow + 1 + 1; /* plus default */
1161
1162                                 while (--i >= 0) {
1163                                         tbptr = (table++)->block;
1164                                         LOG2("target %d is block %04d",i,tbptr->nr);
1165                                         if (!typestate_reach(state, tbptr, state->bptr->outvars,
1166                                                                                  jd->var, state->bptr->outdepth))
1167                                                 return false;
1168                                 }
1169
1170                                 LOG("switch done");
1171                                 superblockend = true;
1172                                 break;
1173
1174                         case ICMD_LOOKUPSWITCH:
1175                                 TYPECHECK_COUNT(stat_ins_switch);
1176
1177                                 lookup = iptr->dst.lookup;
1178                                 i = iptr->sx.s23.s2.lookupcount;
1179
1180                                 if (!typestate_reach(state,iptr->sx.s23.s3.lookupdefault.block,
1181                                                                          state->bptr->outvars, jd->var,
1182                                                                          state->bptr->outdepth))
1183                                         return false;
1184
1185                                 while (--i >= 0) {
1186                                         tbptr = (lookup++)->target.block;
1187                                         LOG2("target %d is block %04d",i,tbptr->nr);
1188                                         if (!typestate_reach(state, tbptr, state->bptr->outvars,
1189                                                                 jd->var, state->bptr->outdepth))
1190                                                 return false;
1191                                 }
1192
1193                                 LOG("switch done");
1194                                 superblockend = true;
1195                                 break;
1196
1197
1198                                 /****************************************/
1199                                 /* ADDRESS RETURNS AND THROW            */
1200
1201                         case ICMD_ATHROW:
1202                                 TYPECHECK_COUNT(stat_ins_athrow);
1203                                 r = typeinfo_is_assignable_to_class(&VAROP(state->iptr->s1)->typeinfo,
1204                                                 CLASSREF_OR_CLASSINFO(class_java_lang_Throwable));
1205                                 if (r == typecheck_FALSE)
1206                                         TYPECHECK_VERIFYERROR_bool("illegal instruction: ATHROW on non-Throwable");
1207                                 if (r == typecheck_FAIL)
1208                                         return false;
1209                                 if (r == typecheck_MAYBE) {
1210                                         /* the check has to be postponed. we need a patcher */
1211                                         TYPECHECK_COUNT(stat_ins_athrow_unresolved);
1212                                         iptr->sx.s23.s2.uc = create_unresolved_class(
1213                                                         state->m,
1214                                                         /* XXX make this more efficient, use class_java_lang_Throwable
1215                                                          * directly */
1216                                                         class_get_classref(state->m->class,utf_java_lang_Throwable),
1217                                                         &VAROP(state->iptr->s1)->typeinfo);
1218                                         iptr->flags.bits |= INS_FLAG_UNRESOLVED;
1219                                 }
1220                                 superblockend = true;
1221                                 maythrow = true;
1222                                 break;
1223
1224                         case ICMD_ARETURN:
1225                                 TYPECHECK_COUNT(stat_ins_areturn);
1226                                 if (!TYPEINFO_IS_REFERENCE(VAROP(state->iptr->s1)->typeinfo))
1227                                         TYPECHECK_VERIFYERROR_bool("illegal instruction: ARETURN on non-reference");
1228
1229                                 if (state->returntype.type != TYPE_ADR
1230                                                 || (r = typeinfo_is_assignable(&VAROP(state->iptr->s1)->typeinfo,&(state->returntype.typeinfo)))
1231                                                                 == typecheck_FALSE)
1232                                         TYPECHECK_VERIFYERROR_bool("Return type mismatch");
1233                                 if (r == typecheck_FAIL)
1234                                         return false;
1235                                 if (r == typecheck_MAYBE) {
1236                                         /* the check has to be postponed, we need a patcher */
1237                                         TYPECHECK_COUNT(stat_ins_areturn_unresolved);
1238                                         iptr->sx.s23.s2.uc = create_unresolved_class(
1239                                                         state->m,
1240                                                         state->m->parseddesc->returntype.classref,
1241                                                         &VAROP(state->iptr->s1)->typeinfo);
1242                                         iptr->flags.bits |= INS_FLAG_UNRESOLVED;
1243                                 }
1244                                 goto return_tail;
1245
1246                                 /****************************************/
1247                                 /* PRIMITIVE RETURNS                    */
1248
1249                         case ICMD_IRETURN:
1250                                 if (state->returntype.type != TYPE_INT) TYPECHECK_VERIFYERROR_bool("Return type mismatch");
1251                                 goto return_tail;
1252
1253                         case ICMD_LRETURN:
1254                                 if (state->returntype.type != TYPE_LNG) TYPECHECK_VERIFYERROR_bool("Return type mismatch");
1255                                 goto return_tail;
1256
1257                         case ICMD_FRETURN:
1258                                 if (state->returntype.type != TYPE_FLT) TYPECHECK_VERIFYERROR_bool("Return type mismatch");
1259                                 goto return_tail;
1260
1261                         case ICMD_DRETURN:
1262                                 if (state->returntype.type != TYPE_DBL) TYPECHECK_VERIFYERROR_bool("Return type mismatch");
1263                                 goto return_tail;
1264
1265                         case ICMD_RETURN:
1266                                 if (state->returntype.type != TYPE_VOID) TYPECHECK_VERIFYERROR_bool("Return type mismatch");
1267 return_tail:
1268                                 TYPECHECK_COUNT(stat_ins_primitive_return);
1269
1270                                 if (state->initmethod && state->m->class != class_java_lang_Object) {
1271                                         /* Check if the 'this' instance has been initialized. */
1272                                         LOG("Checking <init> marker");
1273                                         if (!typevector_checktype(jd->var,state->numlocals-1,TYPE_INT))
1274                                                 TYPECHECK_VERIFYERROR_bool("<init> method does not initialize 'this'");
1275                                 }
1276
1277                                 superblockend = true;
1278                                 maythrow = true;
1279                                 break;
1280
1281                                 /****************************************/
1282                                 /* SUBROUTINE INSTRUCTIONS              */
1283
1284                         case ICMD_JSR:
1285                                 LOG("jsr");
1286
1287                                 tbptr = state->iptr->sx.s23.s3.jsrtarget.block;
1288                                 TYPEINFO_INIT_RETURNADDRESS(dv->typeinfo, state->bptr->next);
1289                                 if (!typestate_reach(state, tbptr, state->bptr->outvars, jd->var,
1290                                                         state->bptr->outdepth))
1291                                         return false;
1292
1293                                 superblockend = true;
1294                                 break;
1295
1296                         case ICMD_RET:
1297                                 /* check returnAddress variable */
1298                                 if (!typevector_checkretaddr(jd->var,state->iptr->s1.varindex))
1299                                         TYPECHECK_VERIFYERROR_bool("illegal instruction: RET using non-returnAddress variable");
1300
1301                                 if (!typestate_reach(state, iptr->dst.block, state->bptr->outvars, jd->var,
1302                                                         state->bptr->outdepth))
1303                                         return false;
1304
1305                                 superblockend = true;
1306                                 break;
1307
1308                                 /****************************************/
1309                                 /* INVOKATIONS                          */
1310
1311                         case ICMD_INVOKEVIRTUAL:
1312                         case ICMD_INVOKESPECIAL:
1313                         case ICMD_INVOKESTATIC:
1314                         case ICMD_INVOKEINTERFACE:
1315                                 TYPECHECK_COUNT(stat_ins_invoke);
1316                                 if (!verify_invocation(state))
1317                                         return false;
1318                                 TYPECHECK_COUNTIF(INSTRUCTION_IS_UNRESOLVED(iptr), stat_ins_invoke_unresolved);
1319                                 maythrow = true;
1320                                 break;
1321
1322                                 /****************************************/
1323                                 /* MULTIANEWARRAY                       */
1324
1325                         case ICMD_MULTIANEWARRAY:
1326                                 if (!verify_multianewarray(state))
1327                                         return false;
1328                                 maythrow = true;
1329                                 break;
1330
1331                                 /****************************************/
1332                                 /* BUILTINS                             */
1333
1334                         case ICMD_BUILTIN:
1335                                 TYPECHECK_COUNT(stat_ins_builtin);
1336                                 if (!verify_builtin(state))
1337                                         return false;
1338                                 maythrow = true;
1339                                 break;
1340
1341                                 /****************************************/
1342                                 /* SIMPLE EXCEPTION THROWING TESTS      */
1343
1344                         case ICMD_CHECKNULL:
1345                                 /* CHECKNULL just requires that the stack top
1346                                  * is an address. This is checked in stack.c */
1347                                 maythrow = true;
1348                                 break;
1349
1350                                 /****************************************/
1351                                 /* INSTRUCTIONS WHICH SHOULD HAVE BEEN  */
1352                                 /* REPLACED BY OTHER OPCODES            */
1353
1354 #ifdef TYPECHECK_DEBUG
1355                         case ICMD_NEW:
1356                         case ICMD_NEWARRAY:
1357                         case ICMD_ANEWARRAY:
1358                         case ICMD_MONITORENTER:
1359                         case ICMD_MONITOREXIT:
1360                                 LOG2("ICMD %d at %d\n", state->iptr->opc, (int)(state->iptr-state->bptr->iinstr));
1361                                 LOG("Should have been converted to builtin function call.");
1362                                 TYPECHECK_ASSERT(false);
1363                                 break;
1364 #endif
1365
1366                                 /****************************************/
1367                                 /* UNCHECKED OPERATIONS                 */
1368
1369                                 /*********************************************
1370                                  * Instructions below...
1371                                  *     *) don't operate on local variables,
1372                                  *     *) don't operate on references,
1373                                  *     *) don't operate on returnAddresses,
1374                                  *     *) don't affect control flow (except
1375                                  *        by throwing exceptions).
1376                                  *
1377                                  * (These instructions are typechecked in
1378                                  *  analyse_stack.)
1379                                  ********************************************/
1380
1381                                 /* Instructions which may throw a runtime exception: */
1382
1383                         case ICMD_IDIV:
1384                         case ICMD_IREM:
1385                                 dv->type = TYPE_INT;
1386                                 maythrow = true;
1387                                 break;
1388
1389                         case ICMD_LDIV:
1390                         case ICMD_LREM:
1391                                 dv->type = TYPE_LNG;
1392                                 maythrow = true;
1393                                 break;
1394
1395                                 /* Instructions which never throw a runtime exception: */
1396                         case ICMD_NOP:
1397                         case ICMD_POP:
1398                         case ICMD_POP2:
1399                                 break;
1400
1401                         case ICMD_ICONST:
1402                         case ICMD_IADD:
1403                         case ICMD_ISUB:
1404                         case ICMD_IMUL:
1405                         case ICMD_INEG:
1406                         case ICMD_IAND:
1407                         case ICMD_IOR:
1408                         case ICMD_IXOR:
1409                         case ICMD_ISHL:
1410                         case ICMD_ISHR:
1411                         case ICMD_IUSHR:
1412                         case ICMD_IMULPOW2:
1413                         case ICMD_IDIVPOW2:
1414                         case ICMD_IADDCONST:
1415                         case ICMD_ISUBCONST:
1416                         case ICMD_IMULCONST:
1417                         case ICMD_IANDCONST:
1418                         case ICMD_IORCONST:
1419                         case ICMD_IXORCONST:
1420                         case ICMD_ISHLCONST:
1421                         case ICMD_ISHRCONST:
1422                         case ICMD_IUSHRCONST:
1423                         case ICMD_IREMPOW2:
1424                         case ICMD_INT2BYTE:
1425                         case ICMD_INT2CHAR:
1426                         case ICMD_INT2SHORT:
1427                         case ICMD_L2I:
1428                         case ICMD_F2I:
1429                         case ICMD_D2I:
1430                         case ICMD_LCMP:
1431                         case ICMD_LCMPCONST:
1432                         case ICMD_FCMPL:
1433                         case ICMD_FCMPG:
1434                         case ICMD_DCMPL:
1435                         case ICMD_DCMPG:
1436                                 dv->type = TYPE_INT;
1437                                 break;
1438
1439                         case ICMD_LCONST:
1440                         case ICMD_LADD:
1441                         case ICMD_LSUB:
1442                         case ICMD_LMUL:
1443                         case ICMD_LNEG:
1444                         case ICMD_LAND:
1445                         case ICMD_LOR:
1446                         case ICMD_LXOR:
1447                         case ICMD_LSHL:
1448                         case ICMD_LSHR:
1449                         case ICMD_LUSHR:
1450                         case ICMD_LMULPOW2:
1451                         case ICMD_LDIVPOW2:
1452                         case ICMD_LADDCONST:
1453                         case ICMD_LSUBCONST:
1454                         case ICMD_LMULCONST:
1455                         case ICMD_LANDCONST:
1456                         case ICMD_LORCONST:
1457                         case ICMD_LXORCONST:
1458                         case ICMD_LSHLCONST:
1459                         case ICMD_LSHRCONST:
1460                         case ICMD_LUSHRCONST:
1461                         case ICMD_LREMPOW2:
1462                         case ICMD_I2L:
1463                         case ICMD_F2L:
1464                         case ICMD_D2L:
1465                                 dv->type = TYPE_LNG;
1466                                 break;
1467
1468                         case ICMD_FCONST:
1469                         case ICMD_I2F:
1470                         case ICMD_L2F:
1471                         case ICMD_D2F:
1472                         case ICMD_FADD:
1473                         case ICMD_FSUB:
1474                         case ICMD_FMUL:
1475                         case ICMD_FDIV:
1476                         case ICMD_FREM:
1477                         case ICMD_FNEG:
1478                                 dv->type = TYPE_FLT;
1479                                 break;
1480
1481                         case ICMD_DCONST:
1482                         case ICMD_I2D:
1483                         case ICMD_L2D:
1484                         case ICMD_F2D:
1485                         case ICMD_DADD:
1486                         case ICMD_DSUB:
1487                         case ICMD_DMUL:
1488                         case ICMD_DDIV:
1489                         case ICMD_DREM:
1490                         case ICMD_DNEG:
1491                                 dv->type = TYPE_DBL;
1492                                 break;
1493
1494                         case ICMD_INLINE_START:
1495                         case ICMD_INLINE_END:
1496                                 break;
1497
1498                                 /* XXX What shall we do with the following ?*/
1499                         case ICMD_AASTORECONST:
1500                                 TYPECHECK_COUNT(stat_ins_unchecked);
1501                                 break;
1502
1503                                 /****************************************/
1504
1505                         default:
1506                                 LOG2("ICMD %d at %d\n", state->iptr->opc, (int)(state->iptr-state->bptr->iinstr));
1507                                 TYPECHECK_VERIFYERROR_bool("Missing ICMD code during typecheck");
1508                 }
1509
1510                 /* reach exception handlers for this instruction */
1511
1512                 if (maythrow) {
1513                         TYPECHECK_COUNT(stat_ins_maythrow);
1514                         TYPECHECK_MARK(state->stat_maythrow);
1515                         LOG("reaching exception handlers");
1516                         i = 0;
1517                         while (state->handlers[i]) {
1518                                 TYPECHECK_COUNT(stat_handlers_reached);
1519                                 if (state->handlers[i]->catchtype.any)
1520                                         VAR(state->exinvars)->typeinfo.typeclass = state->handlers[i]->catchtype;
1521                                 else
1522                                         VAR(state->exinvars)->typeinfo.typeclass.cls = class_java_lang_Throwable;
1523                                 if (!typestate_reach(state,
1524                                                 state->handlers[i]->handler,
1525                                                 &(state->exinvars), jd->var, 1))
1526                                         return false;
1527                                 i++;
1528                         }
1529                 }
1530
1531                 LOG("\t\tnext instruction");
1532                 state->iptr++;
1533         } /* while instructions */
1534
1535         LOG("instructions done");
1536         LOGSTR("RESULT=> ");
1537         DOLOG(typecheck_print_vararray(stdout, jd, state->bptr->outvars,
1538                                 state->bptr->outdepth));
1539         DOLOG(typevector_print(stdout, jd->var, state->numlocals));
1540         LOGNL; LOGFLUSH;
1541
1542         /* propagate stack and variables to the following block */
1543         if (!superblockend) {
1544                 LOG("reaching following block");
1545                 tbptr = state->bptr->next;
1546                 while (tbptr->flags == BBDELETED) {
1547                         tbptr = tbptr->next;
1548 #ifdef TYPECHECK_DEBUG
1549                         /* this must be checked in parse.c */
1550                         if ((tbptr->nr) >= state->basicblockcount)
1551                                 TYPECHECK_VERIFYERROR_bool("Control flow falls off the last block");
1552 #endif
1553                 }
1554                 if (!typestate_reach(state,tbptr,state->bptr->outvars, jd->var,
1555                                         state->bptr->outdepth))
1556                         return false;
1557         }
1558
1559         /* We may have to restore the types of the instack slots. They
1560          * have been saved if an <init> call inside the block has
1561          * modified the instack types. (see INVOKESPECIAL) */
1562
1563         if (state->savedinvars)
1564                 typestate_restore_invars(state);
1565
1566         return true;
1567 }
1568
1569
1570 /* verify_init_locals **********************************************************
1571
1572    Initialize the local variables in the verifier state.
1573
1574    IN:
1575        state............the current state of the verifier
1576
1577    RETURN VALUE:
1578        true.............success,
1579            false............an exception has been thrown.
1580
1581 *******************************************************************************/
1582
1583 static bool
1584 verify_init_locals(verifier_state *state)
1585 {
1586         int i;
1587         int index;
1588         varinfo *locals;
1589         varinfo *v;
1590         jitdata *jd = state->jd;
1591         int skip = 0;
1592
1593         locals = state->basicblocks[0].inlocals;
1594
1595         /* allocate parameter descriptors if necessary */
1596
1597         if (!state->m->parseddesc->params)
1598                 if (!descriptor_params_from_paramtypes(state->m->parseddesc,state->m->flags))
1599                         return false;
1600
1601         /* pre-initialize variables as TYPE_VOID */
1602
1603         i = state->numlocals;
1604         v = locals;
1605         while (i--) {
1606                 v->type = TYPE_VOID;
1607                 v++;
1608         }
1609
1610     /* if this is an instance method initialize the "this" ref type */
1611
1612     if (!(state->m->flags & ACC_STATIC)) {
1613                 index = jd->local_map[5*0 + TYPE_ADR];
1614                 if (index != UNUSED) {
1615                         if (state->validlocals < 1)
1616                                 TYPECHECK_VERIFYERROR_bool("Not enough local variables for method arguments");
1617                         v = locals + index;
1618                         v->type = TYPE_ADR;
1619                         if (state->initmethod)
1620                                 TYPEINFO_INIT_NEWOBJECT(v->typeinfo, NULL);
1621                         else
1622                                 typeinfo_init_classinfo(&(v->typeinfo), state->m->class);
1623                 }
1624
1625                 skip = 1;
1626     }
1627
1628     LOG("'this' argument set.\n");
1629
1630     /* the rest of the arguments and the return type */
1631
1632     if (!typeinfo_init_varinfos_from_methoddesc(locals, state->m->parseddesc,
1633                                                                                           state->validlocals,
1634                                                                                           skip, /* skip 'this' pointer */
1635                                                                                           jd->local_map,
1636                                                                                           &state->returntype))
1637                 return false;
1638
1639     LOG("Arguments set.\n");
1640         return true;
1641 }
1642
1643
1644 /****************************************************************************/
1645 /* typecheck()                                                              */
1646 /* This is the main function of the bytecode verifier. It is called         */
1647 /* directly after analyse_stack.                                            */
1648 /*                                                                          */
1649 /* IN:                                                                      */
1650 /*    meth.............the method to verify                                 */
1651 /*    cdata............codegendata for the method                           */
1652 /*    rdata............registerdata for the method                          */
1653 /*                                                                          */
1654 /* RETURN VALUE:                                                            */
1655 /*     true.............successful verification                             */
1656 /*     false............an exception has been thrown                        */
1657 /*                                                                          */
1658 /****************************************************************************/
1659
1660 #define MAXPARAMS 255
1661
1662 bool typecheck(jitdata *jd)
1663 {
1664         methodinfo     *meth;
1665         codegendata    *cd;
1666         varinfo        *savedlocals;
1667         verifier_state  state;             /* current state of the verifier */
1668         s4              i;
1669         s4              t;
1670
1671         /* collect statistics */
1672
1673 #ifdef TYPECHECK_STATISTICS
1674         int count_iterations = 0;
1675         TYPECHECK_COUNT(stat_typechecked);
1676         TYPECHECK_COUNT_FREQ(stat_locals,cdata->maxlocals,STAT_LOCALS);
1677         TYPECHECK_COUNT_FREQ(stat_blocks,cdata->method->basicblockcount/10,STAT_BLOCKS);
1678         TYPECHECK_COUNTIF(cdata->method->exceptiontablelength != 0,stat_methods_with_handlers);
1679         state.stat_maythrow = false;
1680 #endif
1681
1682         /* get required compiler data */
1683
1684         meth = jd->m;
1685         cd   = jd->cd;
1686
1687         /* some logging on entry */
1688
1689
1690     LOGSTR("\n==============================================================================\n");
1691     DOLOG( show_method(jd, SHOW_STACK) );
1692     LOGSTR("\n==============================================================================\n");
1693     LOGMETHOD("Entering typecheck: ",cd->method);
1694
1695         /* initialize the verifier state */
1696
1697         state.m = meth;
1698         state.jd = jd;
1699         state.cd = cd;
1700         state.basicblockcount = jd->basicblockcount;
1701         state.basicblocks = jd->basicblocks;
1702         state.savedindices = NULL;
1703         state.savedinvars = NULL;
1704
1705         /* check if this method is an instance initializer method */
1706
1707     state.initmethod = (state.m->name == utf_init);
1708
1709         /* initialize the basic block flags for the following CFG traversal */
1710
1711         typecheck_init_flags(&state);
1712
1713     /* number of local variables */
1714
1715     /* In <init> methods we use an extra local variable to indicate whether */
1716     /* the 'this' reference has been initialized.                           */
1717         /*         TYPE_VOID...means 'this' has not been initialized,           */
1718         /*         TYPE_INT....means 'this' has been initialized.               */
1719
1720     state.numlocals = state.jd->localcount;
1721         state.validlocals = state.numlocals;
1722     if (state.initmethod)
1723                 state.numlocals++; /* VERIFIER_EXTRA_LOCALS */
1724
1725         state.reverselocalmap = DMNEW(s4, state.validlocals);
1726         for (i=0; i<jd->m->maxlocals; ++i)
1727                 for (t=0; t<5; ++t) {
1728                         s4 mapped = jd->local_map[5*i + t];
1729                         if (mapped >= 0)
1730                                 state.reverselocalmap[mapped] = i;
1731                 }
1732
1733         DOLOG(
1734                 LOG("reverselocalmap:");
1735                 for (i=0; i<state.validlocals; ++i) {
1736                         LOG2("    %i => javaindex %i", i, state.reverselocalmap[i]);
1737                 });
1738
1739     /* allocate the buffer of active exception handlers */
1740
1741     state.handlers = DMNEW(exceptiontable*, state.cd->exceptiontablelength + 1);
1742
1743         /* save local variables */
1744
1745         savedlocals = DMNEW(varinfo, state.numlocals);
1746         MCOPY(savedlocals, jd->var, varinfo, state.numlocals);
1747
1748         /* initialized local variables of first block */
1749
1750         if (!verify_init_locals(&state))
1751                 return false;
1752
1753     /* initialize invars of exception handlers */
1754
1755         state.exinvars = state.numlocals;
1756         VAR(state.exinvars)->type = TYPE_ADR;
1757         typeinfo_init_classinfo(&(VAR(state.exinvars)->typeinfo),
1758                                                         class_java_lang_Throwable); /* changed later */
1759
1760     LOG("Exception handler stacks set.\n");
1761
1762     /* loop while there are still blocks to be checked */
1763     do {
1764                 TYPECHECK_COUNT(count_iterations);
1765
1766         state.repeat = false;
1767
1768         state.bptr = state.basicblocks;
1769
1770         for (; state.bptr; state.bptr = state.bptr->next) {
1771             LOGSTR1("---- BLOCK %04d, ",state.bptr->nr);
1772             LOGSTR1("blockflags: %d\n",state.bptr->flags);
1773             LOGFLUSH;
1774
1775                     /* verify reached block */
1776             if (state.bptr->flags == BBTYPECHECK_REACHED) {
1777                 if (!verify_basic_block(&state))
1778                                         return false;
1779             }
1780         } /* for blocks */
1781
1782         LOGIF(state.repeat,"state.repeat == true");
1783     } while (state.repeat);
1784
1785         /* statistics */
1786
1787 #ifdef TYPECHECK_STATISTICS
1788         LOG1("Typechecker did %4d iterations",count_iterations);
1789         TYPECHECK_COUNT_FREQ(stat_iterations,count_iterations,STAT_ITERATIONS);
1790         TYPECHECK_COUNTIF(state.jsrencountered,stat_typechecked_jsr);
1791         TYPECHECK_COUNTIF(state.stat_maythrow,stat_methods_maythrow);
1792 #endif
1793
1794         /* reset the flags of blocks we haven't reached */
1795
1796         typecheck_reset_flags(&state);
1797
1798         /* restore locals */
1799
1800         MCOPY(jd->var, savedlocals, varinfo, state.numlocals);
1801
1802         /* everything's ok */
1803
1804     LOGimp("exiting typecheck");
1805         return true;
1806 }
1807 #endif /* ENABLE_VERIFIER */
1808
1809 /*
1810  * These are local overrides for various environment variables in Emacs.
1811  * Please do not remove this and leave it at the end of the file, where
1812  * Emacs will automagically detect them.
1813  * ---------------------------------------------------------------------
1814  * Local variables:
1815  * mode: c
1816  * indent-tabs-mode: t
1817  * c-basic-offset: 4
1818  * tab-width: 4
1819  * End:
1820  * vim:noexpandtab:sw=4:ts=4:
1821  */