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

   1 /* src/vm/jit/verify/typecheck-typeinferer.c - type inference pass
   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    $Id$
  30
  31 */
  32
  33 #include "config.h"
  34 #include "vm/types.h"
  35 #include "vm/global.h"
  36
  37 #include <assert.h>
  38 #include <string.h>
  39
  40 #include "mm/memory.h"
  41 #include "toolbox/logging.h"
  42 #include "native/native.h"
  43 #include "vm/builtin.h"
  44 #include "vm/jit/patcher.h"
  45 #include "vm/loader.h"
  46 #include "vm/options.h"
  47 #include "vm/jit/jit.h"
  48 #include "vm/jit/show.h"
  49 #include "vm/jit/parse.h"
  50 #include "vm/access.h"
  51 #include "vm/resolve.h"
  52 #include "vm/exceptions.h"
  53 #include "vm/vm.h"
  54 #include "vm/jit/verify/typecheck-typeinferer.h"
  55
  56 #define TYPECHECK_NO_STATISTICS
  57 #include <typecheck-common.h>
  58
  59
  60 /* macros used by the generated code ******************************************/
  61
  62 #define EXCEPTION          do { return false; } while (0)
  63 #define VERIFY_ERROR(msg)  assert(false)
  64
  65 #define CHECK_LOCAL_TYPE(index, t)                                   \
  66         assert(jd->var[(index)].type == (t));
  67
  68 #define STORE_LOCAL(t, index)                                        \
  69     do {                                                             \
  70          typevector_store(jd->var, (index), (t), NULL);              \
  71     } while (0)
  72
  73 #define STORE_LOCAL_2_WORD(t, index)                                 \
  74     do {                                                             \
  75          typevector_store(jd->var, (index), (t), NULL);              \
  76     } while (0)
  77
  78 #define REACH_BLOCK(target)                                          \
  79     do {                                                             \
  80         if (!typestate_reach(state, (target),                        \
  81                              state->bptr->outvars, jd->var,          \
  82                              state->bptr->outdepth))                 \
  83                 return false;                                        \
  84     } while (0)
  85
  86 #define REACH(target)   REACH_BLOCK((target).block)
  87
  88 #define TYPECHECK_INT(v)  assert(jd->var[(v)].type == TYPE_INT)
  89 #define TYPECHECK_ADR(v)  assert(jd->var[(v)].type == TYPE_ADR)
  90
  91
  92 /* handle_fieldaccess **********************************************************
  93
  94    Verify an ICMD_{GET,PUT}{STATIC,FIELD}(CONST)?
  95
  96    IN:
  97        state............the current state of the verifier
  98
  99    RETURN VALUE:
 100        true.............successful verification,
 101            false............an exception has been thrown.
 102
 103 *******************************************************************************/
 104
 105 static bool
 106 handle_fieldaccess(verifier_state *state,
 107                                    varinfo *instance,
 108                                    varinfo *value)
 109 {
 110         jitdata *jd;
 111
 112         jd = state->jd;
 113
 114 #define TYPECHECK_TYPEINFERER
 115 #include <typecheck-fields.inc>
 116 #undef  TYPECHECK_TYPEINFERER
 117
 118         return true;
 119 }
 120
 121
 122 /* handle_invocation ***********************************************************
 123
 124    Verify an ICMD_INVOKE* instruction.
 125
 126    IN:
 127        state............the current state of the verifier
 128
 129    RETURN VALUE:
 130        true.............successful verification,
 131            false............an exception has been thrown.
 132
 133 *******************************************************************************/
 134
 135 static bool
 136 handle_invocation(verifier_state *state)
 137 {
 138         jitdata *jd;
 139     varinfo *dv;               /* output variable of current instruction */
 140
 141         jd = state->jd;
 142         dv = VAROP(state->iptr->dst);
 143
 144 #define TYPECHECK_TYPEINFERER
 145 #define OP1   VAR(state->iptr->sx.s23.s2.args[0])
 146 #include <typecheck-invoke.inc>
 147 #undef  OP1
 148 #undef  TYPECHECK_TYPEINFERER
 149
 150         return true;
 151 }
 152
 153
 154 /* handle_builtin **************************************************************
 155
 156    Verify the call of a builtin method.
 157
 158    IN:
 159        state............the current state of the verifier
 160
 161    RETURN VALUE:
 162        true.............successful verification,
 163            false............an exception has been thrown.
 164
 165 *******************************************************************************/
 166
 167 static bool
 168 handle_builtin(verifier_state *state)
 169 {
 170         jitdata *jd;
 171     varinfo *dv;               /* output variable of current instruction */
 172
 173         jd = state->jd;
 174         dv = VAROP(state->iptr->dst);
 175
 176 #define TYPECHECK_TYPEINFERER
 177 #define OP1   state->iptr->sx.s23.s2.args[0]
 178 #include <typecheck-builtins.inc>
 179 #undef  OP1
 180 #undef  TYPECHECK_TYPEINFERER
 181
 182         return true;
 183 }
 184
 185 /* handle_multianewarray *******************************************************
 186
 187    Verify a MULTIANEWARRAY instruction.
 188
 189    IN:
 190        state............the current state of the verifier
 191
 192    RETURN VALUE:
 193        true.............successful verification,
 194            false............an exception has been thrown.
 195
 196 *******************************************************************************/
 197
 198 static bool
 199 handle_multianewarray(verifier_state *state)
 200 {
 201         jitdata *jd;
 202     varinfo *dv;               /* output variable of current instruction */
 203
 204         jd = state->jd;
 205         dv = VAROP(state->iptr->dst);
 206
 207 #define TYPECHECK_TYPEINFERER
 208 #include <typecheck-multianewarray.inc>
 209 #undef  TYPECHECK_TYPEINFERER
 210
 211         return true;
 212 }
 213
 214
 215 /* handle_basic_block **********************************************************
 216
 217    Perform bytecode verification of a basic block.
 218
 219    IN:
 220        state............the current state of the verifier
 221
 222    RETURN VALUE:
 223        true.............successful verification,
 224            false............an exception has been thrown.
 225
 226 *******************************************************************************/
 227
 228 static bool
 229 handle_basic_block(verifier_state *state)
 230 {
 231     int opcode;                                      /* current opcode */
 232     int len;                        /* for counting instructions, etc. */
 233     bool superblockend;        /* true if no fallthrough to next block */
 234         instruction *iptr;                      /* the current instruction */
 235     basicblock *tbptr;                   /* temporary for target block */
 236     bool maythrow;               /* true if this instruction may throw */
 237         s4 i;
 238         branch_target_t *table;
 239         lookup_target_t *lookup;
 240         jitdata *jd = state->jd;
 241         exception_entry *ex;
 242
 243         LOGSTR1("\n---- BLOCK %04d ------------------------------------------------\n",state->bptr->nr);
 244         LOGFLUSH;
 245         DOLOG(show_basicblock(jd, state->bptr, SHOW_STACK));
 246
 247         superblockend = false;
 248         state->bptr->flags = BBFINISHED;
 249
 250         /* prevent compiler warnings */
 251
 252
 253         /* determine the active exception handlers for this block */
 254         /* XXX could use a faster algorithm with sorted lists or  */
 255         /* something?                                             */
 256         len = 0;
 257         for (ex = state->jd->exceptiontable; ex ; ex = ex->down) {
 258                 if ((ex->start->nr <= state->bptr->nr) && (ex->end->nr > state->bptr->nr)) {
 259                         LOG1("active handler L%03d", ex->handler->nr);
 260                         state->handlers[len++] = ex;
 261                 }
 262         }
 263         state->handlers[len] = NULL;
 264
 265         /* init variable types at the start of this block */
 266         typevector_copy_inplace(state->bptr->inlocals, jd->var, state->numlocals);
 267
 268         DOLOG(typecheck_print_vararray(stdout, jd, state->bptr->invars,
 269                                 state->bptr->indepth));
 270         DOLOG(typevector_print(stdout, jd->var, state->numlocals));
 271         LOGNL; LOGFLUSH;
 272
 273         /* loop over the instructions */
 274         len = state->bptr->icount;
 275         state->iptr = state->bptr->iinstr;
 276         while (--len >= 0)  {
 277                 TYPECHECK_COUNT(stat_ins);
 278
 279                 iptr = state->iptr;
 280
 281                 DOLOG(typevector_print(stdout, jd->var, state->numlocals));
 282                 LOGNL; LOGFLUSH;
 283                 DOLOG(show_icmd(jd, state->iptr, false, SHOW_STACK)); LOGNL; LOGFLUSH;
 284
 285                 opcode = iptr->opc;
 286                 maythrow = false;
 287
 288                 switch (opcode) {
 289
 290                         /* include generated code for ICMDs verification */
 291
 292 #define TYPECHECK_TYPEINFERER
 293 #define STATE  state
 294 #define METHOD (state->m)
 295 #define IPTR   iptr
 296 #define BPTR   (state->bptr)
 297 #include <typecheck-typeinferer-gen.inc>
 298 #undef  STATE
 299 #undef  METHOD
 300 #undef  IPTR
 301 #undef  BPTR
 302 #undef  TYPECHECK_TYPEINFERER
 303
 304                         default:
 305                                 vm_abort("missing ICMD in type inferer: %d\n", opcode);
 306                 }
 307
 308                 /* reach exception handlers for this instruction */
 309
 310                 if (maythrow) {
 311                         TYPECHECK_COUNT(stat_ins_maythrow);
 312                         TYPECHECK_MARK(state->stat_maythrow);
 313                         LOG("reaching exception handlers");
 314                         i = 0;
 315                         while (state->handlers[i]) {
 316                                 TYPECHECK_COUNT(stat_handlers_reached);
 317                                 if (state->handlers[i]->catchtype.any)
 318                                         VAR(state->exinvars)->typeinfo.typeclass = state->handlers[i]->catchtype;
 319                                 else
 320                                         VAR(state->exinvars)->typeinfo.typeclass.cls = class_java_lang_Throwable;
 321                                 if (!typestate_reach(state,
 322                                                 state->handlers[i]->handler,
 323                                                 &(state->exinvars), jd->var, 1))
 324                                         return false;
 325                                 i++;
 326                         }
 327                 }
 328
 329                 LOG("\t\tnext instruction");
 330                 state->iptr++;
 331         } /* while instructions */
 332
 333         LOG("instructions done");
 334         LOGSTR("RESULT=> ");
 335         DOLOG(typecheck_print_vararray(stdout, jd, state->bptr->outvars,
 336                                 state->bptr->outdepth));
 337         DOLOG(typevector_print(stdout, jd->var, state->numlocals));
 338         LOGNL; LOGFLUSH;
 339
 340         /* propagate stack and variables to the following block */
 341         if (!superblockend) {
 342                 LOG("reaching following block");
 343                 tbptr = state->bptr->next;
 344                 while (tbptr->flags == BBDELETED) {
 345                         tbptr = tbptr->next;
 346                 }
 347                 if (!typestate_reach(state,tbptr,state->bptr->outvars, jd->var,
 348                                         state->bptr->outdepth))
 349                         return false;
 350         }
 351
 352         return true;
 353 }
 354
 355
 356 bool typecheck_infer_types(jitdata *jd)
 357 {
 358         methodinfo     *meth;
 359         codegendata    *cd;
 360         varinfo        *savedlocals;
 361         verifier_state  state;             /* current state of the verifier */
 362
 363         /* get required compiler data */
 364
 365         meth = jd->m;
 366         cd   = jd->cd;
 367
 368         /* some logging on entry */
 369
 370
 371     LOGSTR("\n==============================================================================\n");
 372     DOLOG( show_method(jd, SHOW_STACK) );
 373     LOGSTR("\n==============================================================================\n");
 374     LOGMETHOD("Entering type inference: ",cd->method);
 375
 376         /* initialize the verifier state */
 377
 378         state.m = meth;
 379         state.jd = jd;
 380         state.cd = cd;
 381         state.basicblockcount = jd->basicblockcount;
 382         state.basicblocks = jd->basicblocks;
 383         state.savedindices = NULL;
 384         state.savedinvars = NULL;
 385
 386         /* check that the basicblock numbers are valid */
 387
 388 #if !defined(NDEBUG)
 389         jit_check_basicblock_numbers(jd);
 390 #endif
 391
 392         /* check if this method is an instance initializer method */
 393
 394     state.initmethod = (state.m->name == utf_init);
 395
 396         /* initialize the basic block flags for the following CFG traversal */
 397
 398         typecheck_init_flags(&state, BBFINISHED);
 399
 400     /* number of local variables */
 401
 402     /* In <init> methods we use an extra local variable to indicate whether */
 403     /* the 'this' reference has been initialized.                           */
 404         /*         TYPE_VOID...means 'this' has not been initialized,           */
 405         /*         TYPE_INT....means 'this' has been initialized.               */
 406
 407     state.numlocals = state.jd->localcount;
 408         state.validlocals = state.numlocals;
 409     if (state.initmethod)
 410                 state.numlocals++; /* VERIFIER_EXTRA_LOCALS */
 411
 412     /* allocate the buffer of active exception handlers */
 413
 414     state.handlers = DMNEW(exception_entry*, state.jd->exceptiontablelength + 1);
 415
 416         /* save local variables */
 417
 418         savedlocals = DMNEW(varinfo, state.numlocals);
 419         MCOPY(savedlocals, jd->var, varinfo, state.numlocals);
 420
 421         /* initialized local variables of first block */
 422
 423         if (!typecheck_init_locals(&state, false))
 424                 return false;
 425
 426     /* initialize invars of exception handlers */
 427
 428         state.exinvars = state.numlocals;
 429         VAR(state.exinvars)->type = TYPE_ADR;
 430         typeinfo_init_classinfo(&(VAR(state.exinvars)->typeinfo),
 431                                                         class_java_lang_Throwable); /* changed later */
 432
 433     LOG("Exception handler stacks set.\n");
 434
 435     /* loop while there are still blocks to be checked */
 436     do {
 437                 TYPECHECK_COUNT(count_iterations);
 438
 439         state.repeat = false;
 440
 441         state.bptr = state.basicblocks;
 442
 443         for (; state.bptr; state.bptr = state.bptr->next) {
 444             LOGSTR1("---- BLOCK %04d, ",state.bptr->nr);
 445             LOGSTR1("blockflags: %d\n",state.bptr->flags);
 446             LOGFLUSH;
 447
 448                     /* verify reached block */
 449             if (state.bptr->flags == BBTYPECHECK_REACHED) {
 450                 if (!handle_basic_block(&state))
 451                                         return false;
 452             }
 453         } /* for blocks */
 454
 455         LOGIF(state.repeat,"state.repeat == true");
 456     } while (state.repeat);
 457
 458         /* statistics */
 459
 460         /* reset the flags of blocks we haven't reached */
 461
 462         typecheck_reset_flags(&state);
 463
 464         /* restore locals */
 465
 466         MCOPY(jd->var, savedlocals, varinfo, state.numlocals);
 467
 468         /* everything's ok */
 469
 470     LOGimp("exiting type inference");
 471         return true;
 472 }
 473
 474 /*
 475  * These are local overrides for various environment variables in Emacs.
 476  * Please do not remove this and leave it at the end of the file, where
 477  * Emacs will automagically detect them.
 478  * ---------------------------------------------------------------------
 479  * Local variables:
 480  * mode: c
 481  * indent-tabs-mode: t
 482  * c-basic-offset: 4
 483  * tab-width: 4
 484  * End:
 485  * vim:noexpandtab:sw=4:ts=4:
 486  */