src/vm/jit/verify/typecheck-stackbased.c

   1 /* src/vm/jit/verify/typecheck-stackbased.c - stack-based verifier
   2
   3    Copyright (C) 1996-2005, 2006 R. Grafl, A. Krall, C. Kruegel,
   4    C. Oates, R. Obermaisser, M. Platter, M. Probst, S. Ring,
   5    E. Steiner, C. Thalinger, D. Thuernbeck, P. Tomsich, C. Ullrich,
   6    J. Wenninger, Institut f. Computersprachen - TU Wien
   7
   8    This file is part of CACAO.
   9
  10    This program is free software; you can redistribute it and/or
  11    modify it under the terms of the GNU General Public License as
  12    published by the Free Software Foundation; either version 2, or (at
  13    your option) any later version.
  14
  15    This program is distributed in the hope that it will be useful, but
  16    WITHOUT ANY WARRANTY; without even the implied warranty of
  17    MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU
  18    General Public License for more details.
  19
  20    You should have received a copy of the GNU General Public License
  21    along with this program; if not, write to the Free Software
  22    Foundation, Inc., 51 Franklin Street, Fifth Floor, Boston, MA
  23    02110-1301, USA.
  24
  25    Contact: cacao@cacaojvm.org
  26
  27    Authors: Edwin Steiner
  28
  29    Changes:
  30
  31    $Id$
  32
  33 */
  34
  35
  36 #include "config.h"
  37
  38 #include <assert.h>
  39
  40 #include "vm/types.h"
  41
  42 #include "mm/memory.h"
  43 #include "vm/global.h"
  44 #include "vm/jit/parse.h"
  45 #include "vm/jit/show.h"
  46 #include "vm/jit/stack.h"
  47 #include "vm/jit/verify/typecheck-common.h"
  48
  49
  50 /* this #if runs over the whole file: */
  51 #if defined(ENABLE_VERIFIER)
  52
  53 typedef typedescriptor verifier_slot_t;
  54
  55 #if defined(TYPECHECK_VERBOSE)
  56 static void typecheck_stackbased_show_state(verifier_state *state,
  57                                                                                         typedescriptor *stack,
  58                                                                                         typedescriptor *stackfloor,
  59                                                                                         bool showins);
  60 #endif
  61
  62
  63 #define CHECK_STACK_DEPTH(d)                                         \
  64     if (((u1*)stack - (u1*)stackfloor)                               \
  65             < (((d)-1) * (int)sizeof(verifier_slot_t)))              \
  66         goto throw_stack_underflow;
  67
  68 /* XXX don't need to check against ACONST for every ICMD */
  69 #define CHECK_STACK_SPACE(d)                                         \
  70     if (((u1*)STATE->stackceiling - (u1*)stack)                      \
  71             < (((d)+1) * (int)sizeof(verifier_slot_t)))              \
  72         if (STATE->iptr->opc != ICMD_ACONST                          \
  73                 || INSTRUCTION_MUST_CHECK(STATE->iptr))              \
  74             goto throw_stack_overflow;
  75
  76 #define CHECK_STACK_TYPE(s, t)                                       \
  77     if ((s).type != (t))                                             \
  78         goto throw_stack_type_error;
  79
  80 /* XXX inefficient */
  81 #define CHECK_LOCAL_TYPE(index, t)                                   \
  82     do {                                                             \
  83         if (state.locals[(index)].type != (t))                       \
  84             goto throw_local_type_error;                             \
  85         if (STATE->topjsr)                                           \
  86             STATE->topjsr->usedlocals[(index)] = 1;                  \
  87         if (STATE->topjsr && IS_2_WORD_TYPE(t))                      \
  88             STATE->topjsr->usedlocals[(index) + 1] = 1;              \
  89     } while(0)
  90
  91 /* XXX inefficient */
  92 #define STORE_LOCAL(t, index)                                        \
  93     do {                                                             \
  94         state.locals[(index)].type = (t);                            \
  95         if ((index) && IS_2_WORD_TYPE(state.locals[(index)-1].type)) \
  96             state.locals[(index-1)].type = TYPE_VOID;                \
  97         if (STATE->topjsr)                                           \
  98             STATE->topjsr->usedlocals[(index)] = 1;                  \
  99     } while (0)
 100
 101 /* XXX inefficient */
 102 #define STORE_LOCAL_2_WORD(t, index)                                 \
 103     do {                                                             \
 104         STORE_LOCAL(t, index);                                       \
 105         state.locals[(index)+1].type = TYPE_VOID;                    \
 106         if (STATE->topjsr)                                           \
 107             STATE->topjsr->usedlocals[(index)] = 1;                  \
 108     } while (0)
 109
 110 #define VERIFY_ERROR(msg)                                            \
 111     do {                                                             \
 112         LOG1("VerifyError: %s", msg);                                \
 113         exceptions_throw_verifyerror(STATE->m, msg);                 \
 114         return false;                                                \
 115     } while (0)
 116
 117 #define IS_CAT1(slot)                                                \
 118     ((slot).type != TYPE_VOID && !IS_2_WORD_TYPE((slot).type))
 119
 120 #define IS_CAT2(slot)                                                \
 121     ((slot).type != TYPE_VOID && IS_2_WORD_TYPE((slot).type))
 122
 123 #define CHECK_CAT1(slot)                                             \
 124     do {                                                             \
 125         if (!IS_CAT1(slot))                                          \
 126             goto throw_stack_category_error;                         \
 127     } while (0)
 128
 129 #define CHECK_CAT2(slot)                                             \
 130     do {                                                             \
 131         if (!IS_CAT2(slot))                                          \
 132             goto throw_stack_category_error;                         \
 133     } while (0)
 134
 135 #define COPY_SLOT(s, d)                                              \
 136     do { (d) = (s); } while (0)
 137
 138 #define REACH_BLOCK(target)                                          \
 139     do {                                                             \
 140         if (!typecheck_stackbased_reach(STATE, (target), stack,      \
 141                     (stack - stackfloor) + 1))                       \
 142             return false;                                            \
 143     } while (0)
 144
 145 #define REACH(target)                                                \
 146     do {                                                             \
 147         tbptr = BLOCK_OF((target).insindex);                         \
 148         REACH_BLOCK(tbptr);                                          \
 149     } while (0)
 150
 151 #undef TYPECHECK_INT
 152 #undef TYPECHECK_LNG
 153 #undef TYPECHECK_FLT
 154 #undef TYPECHECK_DBL
 155 #undef TYPECHECK_ADR
 156
 157 /* XXX should reuse typevector code */
 158 static typecheck_result typecheck_stackbased_merge_locals(methodinfo *m,
 159                                                                                                                   typedescriptor *dst,
 160                                                                                                                   typedescriptor *y,
 161                                                                                                                   int size)
 162 {
 163         bool changed = false;
 164         typecheck_result r;
 165
 166         typedescriptor *a = dst;
 167         typedescriptor *b = y;
 168         while (size--) {
 169                 if (a->type != TYPE_VOID && a->type != b->type) {
 170                         a->type = TYPE_VOID;
 171                         changed = true;
 172                 }
 173                 else if (a->type == TYPE_ADR) {
 174                         if (TYPEINFO_IS_PRIMITIVE(a->typeinfo)) {
 175                                 /* 'a' is a returnAddress */
 176                                 if (!TYPEINFO_IS_PRIMITIVE(b->typeinfo)
 177                                         || (TYPEINFO_RETURNADDRESS(a->typeinfo)
 178                                                 != TYPEINFO_RETURNADDRESS(b->typeinfo)))
 179                                 {
 180                                         a->type = TYPE_VOID;
 181                                         changed = true;
 182                                 }
 183                         }
 184                         else {
 185                                 /* 'a' is a reference */
 186                                 if (TYPEINFO_IS_PRIMITIVE(b->typeinfo)) {
 187                                         a->type = TYPE_VOID;
 188                                         changed = true;
 189                                 }
 190                                 else {
 191                                         /* two reference types are merged. There cannot be */
 192                                         /* a merge error. In the worst case we get j.l.O.  */
 193                                         r = typeinfo_merge(m,&(a->typeinfo),&(b->typeinfo));
 194                                         if (r == typecheck_FAIL)
 195                                                 return r;
 196                                         changed |= r;
 197                                 }
 198                         }
 199                 }
 200                 a++;
 201                 b++;
 202         }
 203         return changed;
 204 }
 205
 206 static typecheck_result typecheck_stackbased_merge(verifier_state *state,
 207                                                                                                    basicblock *destblock,
 208                                                                                                    typedescriptor *stack,
 209                                                                                                    s4 stackdepth)
 210 {
 211         s4 i;
 212         s4 destidx;
 213         typedescriptor *stackfloor;
 214         typedescriptor *sp;
 215         typedescriptor *dp;
 216         typecheck_result r;
 217         bool changed = false;
 218
 219         destidx = destblock->nr;
 220
 221         if (stackdepth != state->indepth[destidx]) {
 222                 exceptions_throw_verifyerror(state->m, "Stack depth mismatch");
 223                 return typecheck_FAIL;
 224         }
 225
 226         stackfloor = stack - (stackdepth - 1);
 227
 228         sp = stackfloor;
 229         dp = state->startstack + (destidx * state->m->maxstack);
 230
 231         for (i=0; i<stackdepth; ++i, ++sp, ++dp) {
 232                 if (sp->type != dp->type) {
 233                         exceptions_throw_verifyerror(state->m, "Mismatched stack types");
 234                         return typecheck_FAIL;
 235                 }
 236                 if (dp->type == TYPE_ADR) {
 237                         if (TYPEINFO_IS_PRIMITIVE(dp->typeinfo)) {
 238                                 /* dp has returnAddress type */
 239                                 if (TYPEINFO_IS_PRIMITIVE(sp->typeinfo)) {
 240                                         if (TYPEINFO_RETURNADDRESS(dp->typeinfo) != TYPEINFO_RETURNADDRESS(sp->typeinfo)) {
 241                                                 exceptions_throw_verifyerror(state->m, "Mismatched stack types");
 242                                                 return typecheck_FAIL;
 243                                         }
 244                                 }
 245                                 else {
 246                                         exceptions_throw_verifyerror(state->m,"Merging returnAddress with reference");
 247                                         return typecheck_FAIL;
 248                                 }
 249                         }
 250                         else {
 251                                 /* dp has reference type */
 252                                 if (TYPEINFO_IS_PRIMITIVE(sp->typeinfo)) {
 253                                         exceptions_throw_verifyerror(state->m,"Merging reference with returnAddress");
 254                                         return typecheck_FAIL;
 255                                 }
 256                                 r = typeinfo_merge(state->m,&(dp->typeinfo),&(sp->typeinfo));
 257                                 if (r == typecheck_FAIL)
 258                                         return r;
 259                                 changed |= r;
 260                         }
 261                 }
 262         }
 263
 264         dp = state->startlocals + (destidx * state->numlocals);
 265         r = typecheck_stackbased_merge_locals(state->m, dp, state->locals, state->numlocals);
 266         if (r == typecheck_FAIL)
 267                 return r;
 268         changed |= r;
 269
 270         return changed;
 271 }
 272
 273 static bool typecheck_stackbased_reach(verifier_state *state,
 274                                                                            basicblock *destblock,
 275                                                                            typedescriptor *stack,
 276                                                                            s4 stackdepth)
 277 {
 278         bool changed = false;
 279         typecheck_result r;
 280
 281         assert(destblock);
 282
 283         if (destblock->flags == BBTYPECHECK_UNDEF) {
 284                 /* The destblock has never been reached before */
 285
 286                 TYPECHECK_COUNT(stat_copied);
 287                 LOG1("block L%03d reached first time",destblock->nr); LOGSTR("\t");
 288                 DOLOG( typecheck_stackbased_show_state(state, stack, stack - (stackdepth - 1), false); );
 289
 290                 state->indepth[destblock->nr] = stackdepth;
 291
 292                 MCOPY(state->startstack + (destblock->nr * state->m->maxstack),
 293                           stack - (stackdepth - 1),
 294                           typedescriptor,
 295                           stackdepth);
 296
 297                 MCOPY(state->startlocals + (destblock->nr * state->numlocals),
 298                           state->locals,
 299                           typedescriptor,
 300                           state->numlocals);
 301
 302                 changed = true;
 303         }
 304         else {
 305                 /* The destblock has already been reached before */
 306
 307                 TYPECHECK_COUNT(stat_merged);
 308                 LOG1("block L%03d reached before", destblock->nr); LOGSTR("\t");
 309                 DOLOG( typecheck_stackbased_show_state(state, stack, stack - (stackdepth - 1), false); );
 310
 311                 r = typecheck_stackbased_merge(state, destblock, stack, stackdepth);
 312                 if (r == typecheck_FAIL)
 313                         return false;
 314                 changed = r;
 315
 316                 TYPECHECK_COUNTIF(changed,stat_merging_changed);
 317         }
 318
 319         if (changed) {
 320                 LOG("\tchanged!");
 321                 destblock->flags = BBTYPECHECK_REACHED;
 322                 /* XXX is this check ok? */
 323                 if (destblock->nr <= state->bptr->nr) {
 324                         LOG("\tREPEAT!");
 325                         state->repeat = true;
 326                 }
 327         }
 328         return true;
 329 }
 330
 331
 332 /* typecheck_stackbased_verify_fieldaccess *************************************
 333
 334    Verify an ICMD_{GET,PUT}{STATIC,FIELD}
 335
 336    IN:
 337        state............the current state of the verifier
 338            instance.........the instance slot, or NULL
 339            value............the value slot, or NULL
 340            stack............stack after popping the arguments
 341
 342    RETURN VALUE:
 343        stack pointer....successful verification,
 344            NULL.............an exception has been thrown.
 345
 346 *******************************************************************************/
 347
 348 static typedescriptor *typecheck_stackbased_verify_fieldaccess(
 349                 verifier_state *state,
 350                 typedescriptor *instance,
 351                 typedescriptor *value,
 352                 typedescriptor *stack)
 353 {
 354         jitdata *jd;
 355
 356         jd = state->jd;
 357
 358 #define TYPECHECK_STACKBASED
 359 #define EXCEPTION  do { return NULL; } while (0)
 360 #define STATE  state
 361 #include <typecheck-fields.inc>
 362 #undef  EXCEPTION
 363 #undef  STATE
 364 #undef  TYPECHECK_STACKBASED
 365
 366         return stack;
 367
 368 throw_stack_overflow:
 369         LOG("STACK OVERFLOW!");
 370         exceptions_throw_verifyerror(state->m, "Stack size too large");
 371         return NULL;
 372 }
 373
 374 static bool typecheck_stackbased_verify_invocation(verifier_state *state,
 375                                                                                                    typedescriptor *stack,
 376                                                                                                    typedescriptor *stackfloor)
 377 {
 378         s4 paramslots;
 379         methoddesc *md;
 380         typedescriptor *dv;
 381
 382         /* check stack depth */
 383
 384         /* XXX parse params */
 385
 386         INSTRUCTION_GET_METHODDESC(state->iptr, md);
 387
 388         paramslots = md->paramslots;
 389
 390         if ((stack - stackfloor) + 1 < paramslots) {
 391                 exceptions_throw_verifyerror(state->m,
 392                                 "Trying to pop operand of an empty stack");
 393                 return false;
 394         }
 395
 396         dv = stack - (paramslots - 1);
 397
 398 #define TYPECHECK_STACKBASED
 399 #define OP1   dv
 400 #include <typecheck-invoke.inc>
 401 #undef  OP1
 402 #undef  TYPECHECK_STACKBASED
 403
 404         return true;
 405 }
 406
 407 static bool typecheck_stackbased_verify_builtin(verifier_state *state,
 408                                                                                                 typedescriptor *stack,
 409                                                                                                 typedescriptor *stackfloor)
 410 {
 411         s4 paramslots;
 412         typedescriptor *dv;
 413
 414         /* check stack depth */
 415
 416         /* XXX parse params */
 417
 418         paramslots = state->iptr->sx.s23.s3.bte->md->paramslots;
 419
 420         if ((stack - stackfloor) + 1 < paramslots) {
 421                 exceptions_throw_verifyerror(state->m,
 422                                 "Trying to pop operand of an empty stack");
 423                 return false;
 424         }
 425
 426         dv = stack - (paramslots - 1);
 427
 428 #define TYPECHECK_STACKBASED
 429 #define OP1   dv
 430 #define TYPECHECK_INT(s)  CHECK_STACK_TYPE(*(s), TYPE_INT)
 431 #define TYPECHECK_ADR(s)  CHECK_STACK_TYPE(*(s), TYPE_ADR)
 432 #define TYPECHECK_LNG(s)  CHECK_STACK_TYPE(*(s), TYPE_LNG)
 433 #define TYPECHECK_FLT(s)  CHECK_STACK_TYPE(*(s), TYPE_FLT)
 434 #define TYPECHECK_DBL(s)  CHECK_STACK_TYPE(*(s), TYPE_DBL)
 435 #include <typecheck-builtins.inc>
 436 #undef  OP1
 437 #undef  TYPECHECK_STACKBASED
 438
 439         return true;
 440
 441 throw_stack_type_error:
 442         exceptions_throw_verifyerror(state->m, "Wrong type on stack"); /* XXX */
 443         return false;
 444 }
 445
 446 static bool typecheck_stackbased_multianewarray(verifier_state *state,
 447                                                                                                 typedescriptor *stack,
 448                                                                                                 typedescriptor *stackfloor)
 449 {
 450         /* XXX recombine with verify_multianewarray */
 451
 452         classinfo *arrayclass;
 453         arraydescriptor *desc;
 454         s4 i;
 455         typedescriptor *sp;
 456         typedescriptor *dst;
 457
 458         /* destination slot */
 459
 460         i = state->iptr->s1.argcount;
 461
 462         dst = stack - (i-1);
 463
 464         /* check the array lengths on the stack */
 465
 466         if ((stack - stackfloor) + 1 < i) {
 467                 exceptions_throw_verifyerror(state->m,
 468                                 "Trying to pop operand of an empty stack");
 469                 return false;
 470         }
 471
 472         if (i < 1)
 473                 TYPECHECK_VERIFYERROR_bool("Illegal dimension argument");
 474
 475         for (sp = dst; sp <= stack; ++sp) {
 476                 if (sp->type != TYPE_INT) {
 477                         exceptions_throw_verifyerror_for_stack(state->m, TYPE_INT);
 478                         return false;
 479                 }
 480         }
 481
 482         /* check array descriptor */
 483
 484         if (INSTRUCTION_IS_RESOLVED(state->iptr)) {
 485                 /* the array class reference has already been resolved */
 486                 arrayclass = state->iptr->sx.s23.s3.c.cls;
 487                 if (!arrayclass)
 488                         TYPECHECK_VERIFYERROR_bool("MULTIANEWARRAY with unlinked class");
 489                 if ((desc = arrayclass->vftbl->arraydesc) == NULL)
 490                         TYPECHECK_VERIFYERROR_bool("MULTIANEWARRAY with non-array class");
 491                 if (desc->dimension < state->iptr->s1.argcount)
 492                         TYPECHECK_VERIFYERROR_bool("MULTIANEWARRAY dimension to high");
 493
 494                 /* set the array type of the result */
 495                 typeinfo_init_classinfo(&(dst->typeinfo), arrayclass);
 496         }
 497         else {
 498                 const char *p;
 499                 constant_classref *cr;
 500
 501                 /* the array class reference is still unresolved */
 502                 /* check that the reference indicates an array class of correct dimension */
 503                 cr = state->iptr->sx.s23.s3.c.ref;
 504                 i = 0;
 505                 p = cr->name->text;
 506                 while (p[i] == '[')
 507                         i++;
 508                 /* { the dimension of the array class == i } */
 509                 if (i < 1)
 510                         TYPECHECK_VERIFYERROR_bool("MULTIANEWARRAY with non-array class");
 511                 if (i < state->iptr->s1.argcount)
 512                         TYPECHECK_VERIFYERROR_bool("MULTIANEWARRAY dimension to high");
 513
 514                 /* set the array type of the result */
 515                 if (!typeinfo_init_class(&(dst->typeinfo),CLASSREF_OR_CLASSINFO(cr)))
 516                         return false;
 517         }
 518
 519         /* everything ok */
 520         return true;
 521
 522 }
 523
 524 static void typecheck_stackbased_add_jsr_caller(typecheck_jsr_t *jsr,
 525                                                                                                 basicblock *bptr)
 526 {
 527         typecheck_jsr_caller_t *jc;
 528
 529         for (jc = jsr->callers; jc; jc = jc->next)
 530                 if (jc->callblock == bptr)
 531                         return;
 532
 533         jc = DNEW(typecheck_jsr_caller_t);
 534         jc->next = jsr->callers;
 535         jc->callblock = bptr;
 536         jsr->callers = jc;
 537 }
 538
 539 static typedescriptor *typecheck_stackbased_jsr(verifier_state *state,
 540                                                                                                 typedescriptor *stack,
 541                                                                                                 typedescriptor *stackfloor)
 542 {
 543         typecheck_jsr_t *jsr;
 544         basicblock *tbptr;
 545         jitdata *jd;
 546         s4 i;
 547
 548         jd = state->jd;
 549
 550         tbptr = BLOCK_OF(state->iptr->sx.s23.s3.jsrtarget.insindex);
 551         jsr = state->jsrinfos[tbptr->nr];
 552
 553         if (jsr && tbptr->flags == BBFINISHED) {
 554
 555                 LOG1("another JSR to analysed subroutine L%03d", tbptr->nr);
 556                 if (jsr->active) {
 557                         exceptions_throw_verifyerror(state->m, "Recursive JSR");
 558                         return NULL;
 559                 }
 560
 561                 assert(jsr->callers);
 562                 assert(jsr->callers->callblock);
 563
 564                 /* copy the stack of the RET edge */
 565
 566                 MCOPY(stackfloor, jsr->retstack, typedescriptor, jsr->retdepth);
 567                 stack = stackfloor + (jsr->retdepth - 1);
 568
 569                 /* copy variables that were used in the subroutine from the RET edge */
 570
 571                 for (i=0; i<state->numlocals; ++i)
 572                         if (jsr->usedlocals[i])
 573                                 state->locals[i] = jsr->retlocals[i];
 574
 575                 /* reach the following block */
 576
 577                 if (!typecheck_stackbased_reach(state, state->bptr->next, stack,
 578                                         (stack - stackfloor) + 1))
 579                         return NULL;
 580         }
 581         else {
 582                 if (!jsr) {
 583                         LOG1("first JSR to block L%03d", tbptr->nr);
 584
 585                         jsr = DNEW(typecheck_jsr_t);
 586                         state->jsrinfos[tbptr->nr] = jsr;
 587                         jsr->callers = NULL;
 588                         jsr->blockflags = DMNEW(char, state->basicblockcount);
 589                         jsr->retblock = NULL;
 590                         jsr->start = tbptr;
 591                         jsr->usedlocals = DMNEW(char, state->numlocals);
 592                         MZERO(jsr->usedlocals, char, state->numlocals);
 593                         jsr->retlocals = DMNEW(typedescriptor, state->numlocals);
 594                         jsr->retstack = DMNEW(typedescriptor, state->m->maxstack);
 595                         jsr->retdepth = 0;
 596                 }
 597                 else {
 598                         LOG1("re-analysing JSR to block L%03d", tbptr->nr);
 599                 }
 600
 601                 jsr->active = true;
 602                 jsr->next = state->topjsr;
 603                 state->topjsr = jsr;
 604
 605                 /* XXX ugly */
 606                 assert(BLOCK_OF(state->iptr->sx.s23.s3.jsrtarget.insindex)->flags == BBTYPECHECK_REACHED);
 607                 tbptr->flags = BBFINISHED;
 608                 for (tbptr = state->basicblocks; tbptr != NULL; tbptr = tbptr->next) {
 609                         jsr->blockflags[tbptr->nr] = tbptr->flags;
 610                         if (tbptr->flags == BBTYPECHECK_REACHED)
 611                                 tbptr->flags = BBFINISHED;
 612                 }
 613                 BLOCK_OF(state->iptr->sx.s23.s3.jsrtarget.insindex)->flags = BBTYPECHECK_REACHED;
 614         }
 615
 616         /* register this block as a caller, if not already done */
 617
 618         typecheck_stackbased_add_jsr_caller(jsr, state->bptr);
 619
 620         return stack;
 621 }
 622
 623 static bool typecheck_stackbased_ret(verifier_state *state,
 624                                                                          typedescriptor *stack,
 625                                                                          typedescriptor *stackfloor)
 626 {
 627         basicblock *tbptr;
 628         typecheck_jsr_caller_t *jsrcaller;
 629         typecheck_jsr_t *jsr;
 630         s4 i;
 631
 632         /* get the subroutine we are RETurning from */
 633
 634         tbptr = TYPEINFO_RETURNADDRESS(state->locals[state->iptr->s1.varindex].typeinfo);
 635         if (tbptr == NULL) {
 636                 exceptions_throw_verifyerror(state->m, "Illegal RET");
 637                 return false;
 638         }
 639
 640         LOG1("RET from subroutine L%03d", tbptr->nr);
 641         jsr = state->jsrinfos[tbptr->nr];
 642         assert(jsr);
 643
 644         /* check against recursion */
 645
 646         if (!jsr->active) {
 647                 exceptions_throw_verifyerror(state->m, "RET outside of local subroutine");
 648                 return false;
 649         }
 650
 651         /* check against multiple RETs for one subroutine */
 652
 653         if (jsr->retblock && jsr->retblock != state->bptr) {
 654                 exceptions_throw_verifyerror(state->m, "Multiple RETs from local subroutine");
 655                 return false;
 656         }
 657
 658         /* store data-flow of the RET edge */
 659
 660         jsr->retblock = state->bptr;
 661         jsr->retdepth = (stack - stackfloor) + 1;
 662         MCOPY(jsr->retstack, stackfloor, typedescriptor, jsr->retdepth);
 663         MCOPY(jsr->retlocals, state->locals, typedescriptor, state->numlocals);
 664
 665         /* invalidate the returnAddress used by this RET */
 666         /* XXX should we also invalidate the returnAddresses of JSRs that are skipped by this RET? */
 667
 668         for (i=0; i<state->numlocals; ++i) {
 669                 typedescriptor *lc = &(jsr->retlocals[i]);
 670                 if (TYPE_IS_RETURNADDRESS(lc->type, lc->typeinfo))
 671                         if (TYPEINFO_RETURNADDRESS(lc->typeinfo) == tbptr) {
 672                                 LOG1("invalidating returnAddress in local %d", i);
 673                                 TYPEINFO_INIT_RETURNADDRESS(lc->typeinfo, NULL);
 674                         }
 675         }
 676
 677         /* touch all callers of the subroutine, so they are analysed again */
 678
 679         for (jsrcaller = jsr->callers; jsrcaller != NULL; jsrcaller = jsrcaller->next) {
 680                 tbptr = jsrcaller->callblock;
 681                 LOG1("touching caller L%03d from RET", tbptr->nr);
 682                 assert(jsr->blockflags[tbptr->nr] >= BBFINISHED);
 683                 jsr->blockflags[tbptr->nr] = BBTYPECHECK_REACHED; /* XXX repeat? */
 684         }
 685
 686         return true;
 687 }
 688
 689 bool typecheck_stackbased(jitdata *jd)
 690 {
 691         register verifier_slot_t *stack;
 692         verifier_slot_t *stackfloor;
 693         s4 len;
 694         methoddesc *md;
 695         bool maythrow;
 696         bool superblockend;
 697         verifier_slot_t temp;
 698         branch_target_t *table;
 699         lookup_target_t *lookup;
 700         s4 i;
 701         typecheck_result r;
 702         verifier_slot_t *dst;
 703         verifier_state state;
 704         basicblock *tbptr;
 705         exception_entry *ex;
 706         typedescriptor exstack;
 707         s4 skip = 0;
 708
 709         DOLOG( show_method(jd, SHOW_PARSE); );
 710
 711         /* initialize verifier state */
 712
 713         state.jd = jd;
 714         state.m = jd->m;
 715         state.cd = jd->cd;
 716         state.basicblocks = jd->basicblocks;
 717         state.basicblockcount = jd->basicblockcount;
 718         state.topjsr = NULL;
 719 #   define STATE (&state)
 720
 721         /* check that the basicblock numbers are valid */
 722
 723 #if !defined(NDEBUG)
 724         jit_check_basicblock_numbers(jd);
 725 #endif
 726
 727         /* check if this method is an instance initializer method */
 728
 729     state.initmethod = (state.m->name == utf_init);
 730
 731         /* allocate parameter descriptors if necessary */
 732
 733         if (!state.m->parseddesc->params)
 734                 if (!descriptor_params_from_paramtypes(state.m->parseddesc,state.m->flags))
 735                         return false;
 736
 737         /* allocate the stack buffers */
 738
 739         stackfloor = DMNEW(verifier_slot_t, state.m->maxstack + 1);
 740         state.stackceiling = stackfloor + state.m->maxstack;
 741         stack = stackfloor - 1;
 742         state.indepth = DMNEW(s4, state.basicblockcount);
 743         state.startstack = DMNEW(verifier_slot_t, state.m->maxstack * state.basicblockcount);
 744
 745         /* allocate the local variables buffers */
 746
 747         state.numlocals = state.m->maxlocals;
 748         state.validlocals = state.m->maxlocals;
 749     if (state.initmethod)
 750                 state.numlocals++; /* extra marker variable */
 751
 752         state.locals = DMNEW(verifier_slot_t, state.numlocals);
 753         state.startlocals = DMNEW(verifier_slot_t, state.numlocals * state.basicblockcount);
 754
 755     /* allocate the buffer of active exception handlers */
 756
 757     state.handlers = DMNEW(exception_entry*, state.jd->exceptiontablelength + 1);
 758
 759     /* initialize instack of exception handlers */
 760
 761         exstack.type = TYPE_ADR;
 762         typeinfo_init_classinfo(&(exstack.typeinfo),
 763                                                         class_java_lang_Throwable); /* changed later */
 764
 765     LOG("Exception handler stacks set.\n");
 766
 767         /* initialize jsr info buffer */
 768
 769         state.jsrinfos = DMNEW(typecheck_jsr_t *, state.basicblockcount);
 770         MZERO(state.jsrinfos, typecheck_jsr_t *, state.basicblockcount);
 771
 772         /* initialize stack of first block */
 773
 774         state.indepth[0] = 0;
 775
 776         /* initialize locals of first block */
 777
 778     /* if this is an instance method initialize the "this" ref type */
 779
 780     if (!(state.m->flags & ACC_STATIC)) {
 781                 if (state.validlocals < 1)
 782                         VERIFY_ERROR("Not enough local variables for method arguments");
 783                 dst = state.startlocals;
 784                 dst->type = TYPE_ADR;
 785                 if (state.initmethod)
 786                         TYPEINFO_INIT_NEWOBJECT(dst->typeinfo, NULL);
 787                 else
 788                         typeinfo_init_classinfo(&(dst->typeinfo), state.m->class);
 789
 790                 skip = 1;
 791     }
 792
 793     LOG("'this' argument set.\n");
 794
 795         len = typedescriptors_init_from_methoddesc(state.startlocals + skip,
 796                         state.m->parseddesc,
 797                         state.validlocals, true, skip, &state.returntype);
 798         if (len < 0)
 799                 return false;
 800
 801         /* set remaining locals to void */
 802
 803         for (i = skip + len; i<state.numlocals; ++i)
 804                 state.startlocals[i].type = TYPE_VOID;
 805
 806         /* initialize block flags */
 807
 808         typecheck_init_flags(&state, BBUNDEF);
 809
 810         /* iterate until fixpoint reached */
 811
 812         do {
 813
 814                 state.repeat = false;
 815
 816                 /* iterate over the basic blocks */
 817
 818                 for (state.bptr = state.basicblocks; state.bptr != NULL; state.bptr = state.bptr->next) {
 819
 820                         if (state.bptr->flags != BBTYPECHECK_REACHED)
 821                                 continue;
 822
 823                         DOLOG( show_basicblock(jd, state.bptr, SHOW_PARSE); );
 824
 825                         /* mark this block as analysed */
 826
 827                         state.bptr->flags = BBFINISHED;
 828
 829                         /* determine the active exception handlers for this block */
 830                         /* XXX could use a faster algorithm with sorted lists or  */
 831                         /* something?                                             */
 832                         /* XXX reuse code from variables based verifer? */
 833                         len = 0;
 834                         for (ex = STATE->jd->exceptiontable; ex ; ex = ex->down) {
 835                                 if ((ex->start->nr <= STATE->bptr->nr) && (ex->end->nr > STATE->bptr->nr)) {
 836                                         LOG1("\tactive handler L%03d", ex->handler->nr);
 837                                         STATE->handlers[len++] = ex;
 838                                 }
 839                         }
 840                         STATE->handlers[len] = NULL;
 841
 842                         /* initialize the locals */
 843
 844                         MCOPY(state.locals,
 845                                   state.startlocals + (state.bptr->nr * state.numlocals),
 846                                   verifier_slot_t, state.numlocals);
 847
 848                         /* initialize the stack */
 849
 850                         len = state.indepth[state.bptr->nr];
 851
 852                         MCOPY(stackfloor,
 853                                   state.startstack + (state.bptr->nr * state.m->maxstack),
 854                                   verifier_slot_t, len);
 855
 856                         stack = stackfloor + (len - 1);
 857
 858                         /* iterate over the instructions in this block */
 859
 860                         state.iptr = state.bptr->iinstr;
 861                         len = state.bptr->icount;
 862
 863                         superblockend = false;
 864
 865                         for (; len--; state.iptr++) {
 866
 867                                 maythrow = false;
 868
 869                                 LOGNL;
 870                                 DOLOG( typecheck_stackbased_show_state(&state, stack, stackfloor, true); );
 871
 872                                 switch (state.iptr->opc) {
 873 #define TYPECHECK_STACKBASED 1
 874 #define STATE (&state)
 875 #define IPTR state.iptr
 876 #define BPTR state.bptr
 877 #define METHOD state.m
 878 #define LOCAL_SLOT(index)  (state.locals + (index))
 879 #define EXCEPTION                                                    \
 880     do {                                                             \
 881         LOG("EXCEPTION THROWN!\n");                                  \
 882         return false;                                                \
 883     } while (0)
 884
 885 #include <typecheck-stackbased-gen.inc>
 886 #undef  TYPECHECK_STACKBASED
 887                                 }
 888
 889                                 /* reach exception handlers for this instruction */
 890
 891                                 if (maythrow) {
 892                                         TYPECHECK_COUNT(stat_ins_maythrow);
 893                                         TYPECHECK_MARK(STATE->stat_maythrow);
 894                                         LOG("\treaching exception handlers");
 895                                         i = 0;
 896                                         while (STATE->handlers[i]) {
 897                                                 TYPECHECK_COUNT(stat_handlers_reached);
 898                                                 if (STATE->handlers[i]->catchtype.any)
 899                                                         exstack.typeinfo.typeclass = STATE->handlers[i]->catchtype;
 900                                                 else
 901                                                         exstack.typeinfo.typeclass.cls = class_java_lang_Throwable;
 902                                                 if (!typecheck_stackbased_reach(
 903                                                                 STATE,
 904                                                                 STATE->handlers[i]->handler,
 905                                                                 &exstack, 1))
 906                                                         EXCEPTION;
 907                                                 i++;
 908                                         }
 909                                 }
 910                         }
 911
 912                         /* propagate types to the following block */
 913
 914                         if (!superblockend) {
 915                                 if (!typecheck_stackbased_reach(&state, state.bptr->next,
 916                                                                                                 stack, stack - stackfloor + 1))
 917                                         EXCEPTION;
 918                         }
 919                 } /* end loop over blocks */
 920
 921                 while (!state.repeat && state.topjsr) {
 922                         LOG1("done analysing subroutine L%03d", state.topjsr->start->nr);
 923
 924                         /* propagate down used locals */
 925
 926                         if (state.topjsr->next) {
 927                                 for (i=0; i<state.numlocals; ++i)
 928                                         state.topjsr->next->usedlocals[i] |= state.topjsr->usedlocals[i];
 929                         }
 930
 931                         /* restore REACHED flags */
 932
 933                         for (tbptr = state.basicblocks; tbptr != NULL; tbptr = tbptr->next) {
 934                                 assert(tbptr->flags != BBTYPECHECK_REACHED);
 935                                 if (state.topjsr->blockflags[tbptr->nr] == BBTYPECHECK_REACHED) {
 936                                         tbptr->flags = BBTYPECHECK_REACHED;
 937                                         state.repeat = true;
 938                                 }
 939                         }
 940
 941                         /* dactivate the subroutine */
 942
 943                         state.topjsr->active = false;
 944                         state.topjsr = state.topjsr->next;
 945                 }
 946         } while (state.repeat);
 947
 948         /* reset block flags */
 949
 950         typecheck_reset_flags(&state);
 951
 952         LOG("typecheck_stackbased successful");
 953
 954         return true;
 955
 956 throw_stack_underflow:
 957         LOG("STACK UNDERFLOW!");
 958         exceptions_throw_verifyerror(state.m, "Unable to pop operand off an empty stack");
 959         return false;
 960
 961 throw_stack_overflow:
 962         LOG("STACK OVERFLOW!");
 963         exceptions_throw_verifyerror(state.m, "Stack size too large");
 964         return false;
 965
 966 throw_stack_type_error:
 967         LOG("STACK TYPE ERROR!");
 968         exceptions_throw_verifyerror(state.m, "Mismatched stack types");
 969         return false;
 970
 971 throw_local_type_error:
 972         LOG("LOCAL TYPE ERROR!");
 973         exceptions_throw_verifyerror(state.m, "Local variable type mismatch");
 974         return false;
 975
 976 throw_stack_category_error:
 977         LOG("STACK CATEGORY ERROR!");
 978         exceptions_throw_verifyerror(state.m, "Attempt to split long or double on the stack");
 979         return false;
 980 }
 981
 982
 983 #if defined(TYPECHECK_VERBOSE)
 984 static void typecheck_stackbased_show_state(verifier_state *state,
 985                                                                                         typedescriptor *stack,
 986                                                                                         typedescriptor *stackfloor,
 987                                                                                         bool showins)
 988 {
 989         typedescriptor *sp;
 990         s4 i;
 991
 992         LOGSTR1("stackdepth %d stack [", (stack - stackfloor) + 1);
 993         for (sp=stackfloor; sp <= stack; sp++) {
 994                 LOGSTR(" ");
 995                 DOLOG( typedescriptor_print(stdout, sp); );
 996         }
 997         LOGSTR(" ] locals [");
 998         for (i=0; i<state->numlocals; ++i) {
 999                 LOGSTR(" ");
1000                 DOLOG( typedescriptor_print(stdout, state->locals + i); );
1001         }
1002         LOGSTR(" ]");
1003         LOGNL;
1004         if (showins && state->iptr < (state->bptr->iinstr + state->bptr->icount)) {
1005                 LOGSTR("\t");
1006                 DOLOG( show_icmd(state->jd, state->iptr, false, SHOW_PARSE); );
1007                 LOGNL;
1008         }
1009 }
1010 #endif
1011
1012 #endif /* defined(ENABLE_VERIFIER) */
1013
1014
1015 /*
1016  * These are local overrides for various environment variables in Emacs.
1017  * Please do not remove this and leave it at the end of the file, where
1018  * Emacs will automagically detect them.
1019  * ---------------------------------------------------------------------
1020  * Local variables:
1021  * mode: c
1022  * indent-tabs-mode: t
1023  * c-basic-offset: 4
1024  * tab-width: 4
1025  * End:
1026  * vim:noexpandtab:sw=4:ts=4:
1027  */
1028