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

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