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