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