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