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