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