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

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