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