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