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