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