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