src/vm/jit/verify/typecheck-common.c

   1 /* src/vm/jit/verify/typecheck-common.c - shared verifier code
   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/exceptions.h>
  43 #include <vm/jit/show.h>
  44 #include <typecheck-common.h>
  45
  46 /****************************************************************************/
  47 /* DEBUG HELPERS                                                            */
  48 /****************************************************************************/
  49
  50 #ifdef TYPECHECK_VERBOSE_OPT
  51 bool opt_typecheckverbose = false;
  52 #endif
  53
  54 #if defined(TYPECHECK_VERBOSE) || defined(TYPECHECK_VERBOSE_IMPORTANT)
  55
  56 void typecheck_print_var(FILE *file, jitdata *jd, s4 index)
  57 {
  58         varinfo *var;
  59
  60         assert(index >= 0 && index < jd->varcount);
  61         var = VAR(index);
  62         typeinfo_print_type(file, var->type, &(var->typeinfo));
  63 }
  64
  65 void typecheck_print_vararray(FILE *file, jitdata *jd, s4 *vars, int len)
  66 {
  67         s4 i;
  68
  69         for (i=0; i<len; ++i) {
  70                 if (i)
  71                         fputc(' ', file);
  72                 typecheck_print_var(file, jd, *vars++);
  73         }
  74 }
  75
  76 #endif /* defined(TYPECHECK_VERBOSE) || defined(TYPECHECK_VERBOSE_IMPORTANT) */
  77
  78
  79 /****************************************************************************/
  80 /* STATISTICS                                                               */
  81 /****************************************************************************/
  82
  83 #if defined(TYPECHECK_STATISTICS)
  84 int stat_typechecked = 0;
  85 int stat_methods_with_handlers = 0;
  86 int stat_methods_maythrow = 0;
  87 int stat_iterations[STAT_ITERATIONS+1] = { 0 };
  88 int stat_reached = 0;
  89 int stat_copied = 0;
  90 int stat_merged = 0;
  91 int stat_merging_changed = 0;
  92 int stat_blocks[STAT_BLOCKS+1] = { 0 };
  93 int stat_locals[STAT_LOCALS+1] = { 0 };
  94 int stat_ins = 0;
  95 int stat_ins_maythrow = 0;
  96 int stat_ins_stack = 0;
  97 int stat_ins_field = 0;
  98 int stat_ins_field_unresolved = 0;
  99 int stat_ins_field_uninitialized = 0;
 100 int stat_ins_invoke = 0;
 101 int stat_ins_invoke_unresolved = 0;
 102 int stat_ins_primload = 0;
 103 int stat_ins_aload = 0;
 104 int stat_ins_builtin = 0;
 105 int stat_ins_builtin_gen = 0;
 106 int stat_ins_branch = 0;
 107 int stat_ins_switch = 0;
 108 int stat_ins_primitive_return = 0;
 109 int stat_ins_areturn = 0;
 110 int stat_ins_areturn_unresolved = 0;
 111 int stat_ins_athrow = 0;
 112 int stat_ins_athrow_unresolved = 0;
 113 int stat_ins_unchecked = 0;
 114 int stat_handlers_reached = 0;
 115 int stat_savedstack = 0;
 116
 117 static void print_freq(FILE *file,int *array,int limit)
 118 {
 119         int i;
 120         for (i=0; i<limit; ++i)
 121                 fprintf(file,"      %3d: %8d\n",i,array[i]);
 122         fprintf(file,"    >=%3d: %8d\n",limit,array[limit]);
 123 }
 124
 125 void typecheck_print_statistics(FILE *file) {
 126         fprintf(file,"typechecked methods: %8d\n",stat_typechecked);
 127         fprintf(file,"    with handler(s): %8d\n",stat_methods_with_handlers);
 128         fprintf(file,"    with throw(s)  : %8d\n",stat_methods_maythrow);
 129         fprintf(file,"reached blocks     : %8d\n",stat_reached);
 130         fprintf(file,"copied states      : %8d\n",stat_copied);
 131         fprintf(file,"merged states      : %8d\n",stat_merged);
 132         fprintf(file,"merging changed    : %8d\n",stat_merging_changed);
 133         fprintf(file,"handlers reached   : %8d\n",stat_handlers_reached);
 134         fprintf(file,"saved stack (times): %8d\n",stat_savedstack);
 135         fprintf(file,"instructions       : %8d\n",stat_ins);
 136         fprintf(file,"    stack          : %8d\n",stat_ins_stack);
 137         fprintf(file,"    field access   : %8d\n",stat_ins_field);
 138         fprintf(file,"      (unresolved) : %8d\n",stat_ins_field_unresolved);
 139         fprintf(file,"      (uninit.)    : %8d\n",stat_ins_field_uninitialized);
 140         fprintf(file,"    invocations    : %8d\n",stat_ins_invoke);
 141         fprintf(file,"      (unresolved) : %8d\n",stat_ins_invoke_unresolved);
 142         fprintf(file,"    load primitive : (currently not counted) %8d\n",stat_ins_primload);
 143         fprintf(file,"    load address   : %8d\n",stat_ins_aload);
 144         fprintf(file,"    builtins       : %8d\n",stat_ins_builtin);
 145         fprintf(file,"        generic    : %8d\n",stat_ins_builtin_gen);
 146         fprintf(file,"    branches       : %8d\n",stat_ins_branch);
 147         fprintf(file,"    switches       : %8d\n",stat_ins_switch);
 148         fprintf(file,"    prim. return   : %8d\n",stat_ins_primitive_return);
 149         fprintf(file,"    areturn        : %8d\n",stat_ins_areturn);
 150         fprintf(file,"      (unresolved) : %8d\n",stat_ins_areturn_unresolved);
 151         fprintf(file,"    athrow         : %8d\n",stat_ins_athrow);
 152         fprintf(file,"      (unresolved) : %8d\n",stat_ins_athrow_unresolved);
 153         fprintf(file,"    unchecked      : %8d\n",stat_ins_unchecked);
 154         fprintf(file,"    maythrow       : %8d\n",stat_ins_maythrow);
 155         fprintf(file,"iterations used:\n");
 156         print_freq(file,stat_iterations,STAT_ITERATIONS);
 157         fprintf(file,"basic blocks per method / 10:\n");
 158         print_freq(file,stat_blocks,STAT_BLOCKS);
 159         fprintf(file,"locals:\n");
 160         print_freq(file,stat_locals,STAT_LOCALS);
 161 }
 162 #endif /* defined(TYPECHECK_STATISTICS) */
 163
 164
 165 /* typecheck_init_flags ********************************************************
 166
 167    Initialize the basic block flags for the following CFG traversal.
 168
 169    IN:
 170        state............the current state of the verifier
 171        minflags.........minimum flags value of blocks that should be
 172                         considered
 173
 174 *******************************************************************************/
 175
 176 void typecheck_init_flags(verifier_state *state, s4 minflags)
 177 {
 178         basicblock *block;
 179
 180     /* set all BBFINISHED blocks to BBTYPECHECK_UNDEF. */
 181
 182     for (block = state->basicblocks; block; block = block->next) {
 183
 184 #ifdef TYPECHECK_DEBUG
 185                 /* check for invalid flags */
 186         if (block->flags != BBFINISHED && block->flags != BBDELETED && block->flags != BBUNDEF)
 187         {
 188             LOGSTR1("block flags: %d\n",block->flags); LOGFLUSH;
 189                         TYPECHECK_ASSERT(false);
 190         }
 191 #endif
 192
 193         if (block->flags >= minflags) {
 194             block->flags = BBTYPECHECK_UNDEF;
 195         }
 196     }
 197
 198     /* the first block is always reached */
 199
 200     if (state->basicblockcount && state->basicblocks[0].flags == BBTYPECHECK_UNDEF)
 201         state->basicblocks[0].flags = BBTYPECHECK_REACHED;
 202 }
 203
 204
 205 /* typecheck_reset_flags *******************************************************
 206
 207    Reset the flags of basic blocks we have not reached.
 208
 209    IN:
 210        state............the current state of the verifier
 211
 212 *******************************************************************************/
 213
 214 void typecheck_reset_flags(verifier_state *state)
 215 {
 216         basicblock *block;
 217
 218         /* check for invalid flags at exit */
 219
 220 #ifdef TYPECHECK_DEBUG
 221         for (block = state->basicblocks; block; block = block->next) {
 222                 if (block->flags != BBDELETED
 223                         && block->flags != BBUNDEF
 224                         && block->flags != BBFINISHED
 225                         && block->flags != BBTYPECHECK_UNDEF) /* typecheck may never reach
 226                                                                                                          * some exception handlers,
 227                                                                                                          * that's ok. */
 228                 {
 229                         LOG2("block L%03d has invalid flags after typecheck: %d",
 230                                  block->nr,block->flags);
 231                         TYPECHECK_ASSERT(false);
 232                 }
 233         }
 234 #endif
 235
 236         /* Delete blocks we never reached */
 237
 238         for (block = state->basicblocks; block; block = block->next) {
 239                 if (block->flags == BBTYPECHECK_UNDEF)
 240                         block->flags = BBDELETED;
 241         }
 242 }
 243
 244
 245 /****************************************************************************/
 246 /* TYPESTACK MACROS AND FUNCTIONS                                           */
 247 /*                                                                          */
 248 /* These macros and functions act on the 'type stack', which is a shorthand */
 249 /* for the types of the stackslots of the current stack. The type of a      */
 250 /* stack slot is usually described by a TYPE_* constant and -- for TYPE_ADR */
 251 /* -- by the typeinfo of the slot. The only thing that makes the type stack */
 252 /* more complicated are returnAddresses of local subroutines, because a     */
 253 /* single stack slot may contain a set of more than one possible return     */
 254 /* address. This is handled by 'return address sets'. A return address set  */
 255 /* is kept as a linked list dangling off the typeinfo of the stack slot.    */
 256 /****************************************************************************/
 257
 258 /* typecheck_copy_types ********************************************************
 259
 260    Copy the types of the source variables to the destination variables.
 261
 262    IN:
 263            state............current verifier state
 264            srcvars..........array of variable indices to copy
 265            dstvars..........array of the destination variables
 266            n................number of variables to copy
 267
 268    RETURN VALUE:
 269        true.............success
 270            false............an exception has been thrown
 271
 272 *******************************************************************************/
 273
 274 bool typecheck_copy_types(verifier_state *state, s4 *srcvars, s4 *dstvars, s4 n)
 275 {
 276         s4 i;
 277         varinfo *sv;
 278         varinfo *dv;
 279         jitdata *jd = state->jd;
 280
 281         for (i=0; i < n; ++i, ++srcvars, ++dstvars) {
 282                 sv = VAR(*srcvars);
 283                 dv = VAR(*dstvars);
 284
 285                 dv->type = sv->type;
 286                 if (dv->type == TYPE_ADR) {
 287                         TYPEINFO_CLONE(sv->typeinfo,dv->typeinfo);
 288                 }
 289         }
 290         return true;
 291 }
 292
 293
 294 /* typecheck_merge_types *******************************************************
 295
 296    Merge the types of the source variables into the destination variables.
 297
 298    IN:
 299        state............current state of the verifier
 300            srcvars..........source variable indices
 301            dstvars..........destination variable indices
 302            n................number of variables
 303
 304    RETURN VALUE:
 305        typecheck_TRUE...the destination variables have been modified
 306            typecheck_FALSE..the destination variables are unchanged
 307            typecheck_FAIL...an exception has been thrown
 308
 309 *******************************************************************************/
 310
 311 typecheck_result typecheck_merge_types(verifier_state *state,
 312                                                                            s4 *srcvars,
 313                                                                            s4 *dstvars,
 314                                                                            s4 n)
 315 {
 316         s4 i;
 317         varinfo *sv;
 318         varinfo *dv;
 319         jitdata *jd = state->jd;
 320         typecheck_result r;
 321         bool changed = false;
 322
 323         for (i=0; i < n; ++i, ++srcvars, ++dstvars) {
 324                 sv = VAR(*srcvars);
 325                 dv = VAR(*dstvars);
 326
 327                 if (dv->type != sv->type) {
 328                         exceptions_throw_verifyerror(state->m,"Stack type mismatch");
 329                         return typecheck_FAIL;
 330                 }
 331                 if (dv->type == TYPE_ADR) {
 332                         if (TYPEINFO_IS_PRIMITIVE(dv->typeinfo)) {
 333                                 /* dv has returnAddress type */
 334                                 if (!TYPEINFO_IS_PRIMITIVE(sv->typeinfo)) {
 335                                         exceptions_throw_verifyerror(state->m,"Merging returnAddress with reference");
 336                                         return typecheck_FAIL;
 337                                 }
 338                         }
 339                         else {
 340                                 /* dv has reference type */
 341                                 if (TYPEINFO_IS_PRIMITIVE(sv->typeinfo)) {
 342                                         exceptions_throw_verifyerror(state->m,"Merging reference with returnAddress");
 343                                         return typecheck_FAIL;
 344                                 }
 345                                 r = typeinfo_merge(state->m,&(dv->typeinfo),&(sv->typeinfo));
 346                                 if (r == typecheck_FAIL)
 347                                         return r;
 348                                 changed |= r;
 349                         }
 350                 }
 351         }
 352         return changed;
 353 }
 354
 355
 356 /* typestate_merge *************************************************************
 357
 358    Merge the types of one state into the destination state.
 359
 360    IN:
 361        state............current state of the verifier
 362            dstvars..........indices of the destinations invars
 363            dstlocals........the destinations inlocals
 364            srcvars..........indices of the source's outvars
 365            srclocals........the source locals
 366            n................number of invars (== number of outvars)
 367
 368    RETURN VALUE:
 369        typecheck_TRUE...destination state has been modified
 370            typecheck_FALSE..destination state has not been modified
 371            typecheck_FAIL...an exception has been thrown
 372
 373 *******************************************************************************/
 374
 375 typecheck_result typestate_merge(verifier_state *state,
 376                                                  s4 *srcvars, varinfo *srclocals,
 377                                                  s4 *dstvars, varinfo *dstlocals,
 378                                                  s4 n)
 379 {
 380         bool changed = false;
 381         typecheck_result r;
 382
 383         /* The stack is always merged. If there are returnAddresses on
 384          * the stack they are ignored in this step. */
 385
 386         r = typecheck_merge_types(state, srcvars, dstvars, n);
 387         if (r == typecheck_FAIL)
 388                 return r;
 389         changed |= r;
 390
 391         /* merge the locals */
 392
 393         r = typevector_merge(state->m, dstlocals, srclocals, state->numlocals);
 394         if (r == typecheck_FAIL)
 395                 return r;
 396         return changed | r;
 397 }
 398
 399
 400 /* typestate_reach *************************************************************
 401
 402    Reach a destination block and propagate stack and local variable types
 403
 404    IN:
 405        state............current state of the verifier
 406            destblock........destination basic block
 407            srcvars..........variable indices of the outvars to propagate
 408            srclocals........local variables to propagate
 409            n................number of srcvars
 410
 411    OUT:
 412        state->repeat....set to true if the verifier must iterate again
 413                             over the basic blocks
 414
 415    RETURN VALUE:
 416        true.............success
 417            false............an exception has been thrown
 418
 419 *******************************************************************************/
 420
 421 bool typestate_reach(verifier_state *state,
 422                                          basicblock *destblock,
 423                                          s4 *srcvars, varinfo *srclocals, s4 n)
 424 {
 425         varinfo *destloc;
 426         bool changed = false;
 427         typecheck_result r;
 428
 429         LOG1("reaching block L%03d",destblock->nr);
 430         TYPECHECK_COUNT(stat_reached);
 431
 432         destloc = destblock->inlocals;
 433
 434         if (destblock->flags == BBTYPECHECK_UNDEF) {
 435                 /* The destblock has never been reached before */
 436
 437                 TYPECHECK_COUNT(stat_copied);
 438                 LOG1("block L%03d reached first time",destblock->nr);
 439
 440                 if (!typecheck_copy_types(state, srcvars, destblock->invars, n))
 441                         return false;
 442                 typevector_copy_inplace(srclocals, destloc, state->numlocals);
 443                 changed = true;
 444         }
 445         else {
 446                 /* The destblock has already been reached before */
 447
 448                 TYPECHECK_COUNT(stat_merged);
 449                 LOG1("block L%03d reached before", destblock->nr);
 450
 451                 r = typestate_merge(state, srcvars, srclocals,
 452                                 destblock->invars, destblock->inlocals, n);
 453                 if (r == typecheck_FAIL)
 454                         return false;
 455                 changed = r;
 456                 TYPECHECK_COUNTIF(changed,stat_merging_changed);
 457         }
 458
 459         if (changed) {
 460                 LOG("changed!");
 461                 destblock->flags = BBTYPECHECK_REACHED;
 462                 if (destblock->nr <= state->bptr->nr) {
 463                         LOG("REPEAT!");
 464                         state->repeat = true;
 465                 }
 466         }
 467         return true;
 468 }
 469
 470
 471 /* typecheck_init_locals *******************************************************
 472
 473    Initialize the local variables in the verifier state.
 474
 475    IN:
 476        state............the current state of the verifier
 477            newthis..........if true, mark the instance in <init> methods as
 478                             uninitialized object.
 479
 480    RETURN VALUE:
 481        true.............success,
 482            false............an exception has been thrown.
 483
 484 *******************************************************************************/
 485
 486 bool typecheck_init_locals(verifier_state *state, bool newthis)
 487 {
 488         int i;
 489         int varindex;
 490         varinfo *locals;
 491         varinfo *v;
 492         jitdata *jd = state->jd;
 493         int skip = 0;
 494
 495         locals = state->basicblocks[0].inlocals;
 496
 497         /* allocate parameter descriptors if necessary */
 498
 499         if (!state->m->parseddesc->params)
 500                 if (!descriptor_params_from_paramtypes(state->m->parseddesc,state->m->flags))
 501                         return false;
 502
 503         /* pre-initialize variables as TYPE_VOID */
 504
 505         i = state->numlocals;
 506         v = locals;
 507         while (i--) {
 508                 v->type = TYPE_VOID;
 509                 v++;
 510         }
 511
 512     /* if this is an instance method initialize the "this" ref type */
 513
 514     if (!(state->m->flags & ACC_STATIC)) {
 515                 varindex = jd->local_map[5*0 + TYPE_ADR];
 516                 if (varindex != UNUSED) {
 517                         if (state->validlocals < 1)
 518                                 TYPECHECK_VERIFYERROR_bool("Not enough local variables for method arguments");
 519                         v = locals + varindex;
 520                         v->type = TYPE_ADR;
 521                         if (state->initmethod && newthis)
 522                                 TYPEINFO_INIT_NEWOBJECT(v->typeinfo, NULL);
 523                         else
 524                                 typeinfo_init_classinfo(&(v->typeinfo), state->m->class);
 525                 }
 526
 527                 skip = 1;
 528     }
 529
 530     LOG("'this' argument set.\n");
 531
 532     /* the rest of the arguments and the return type */
 533
 534     if (!typeinfo_init_varinfos_from_methoddesc(locals, state->m->parseddesc,
 535                                                                                           state->validlocals,
 536                                                                                           skip, /* skip 'this' pointer */
 537                                                                                           jd->local_map,
 538                                                                                           &state->returntype))
 539                 return false;
 540
 541     LOG("Arguments set.\n");
 542         return true;
 543 }
 544
 545
 546 /*
 547  * These are local overrides for various environment variables in Emacs.
 548  * Please do not remove this and leave it at the end of the file, where
 549  * Emacs will automagically detect them.
 550  * ---------------------------------------------------------------------
 551  * Local variables:
 552  * mode: c
 553  * indent-tabs-mode: t
 554  * c-basic-offset: 4
 555  * tab-width: 4
 556  * End:
 557  * vim:noexpandtab:sw=4:ts=4:
 558  */