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

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