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