src/vm/jit/verify/typecheck.c

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