1 /* src/vm/jit/verify/typecheck-common.c - shared verifier code
3 Copyright (C) 1996-2011
4 CACAOVM - Verein zur Foerderung der freien virtuellen Maschine CACAO
6 This file is part of CACAO.
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.
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.
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
28 #include "vm/global.h"
32 #include "vm/exceptions.hpp"
33 #include "vm/globals.hpp"
35 #include "vm/jit/show.hpp"
37 #include "typecheck-common.hpp"
39 #if defined(__cplusplus)
43 /****************************************************************************/
45 /****************************************************************************/
47 #ifdef TYPECHECK_VERBOSE_OPT
48 bool opt_typecheckverbose = false;
51 #if defined(TYPECHECK_VERBOSE) || defined(TYPECHECK_VERBOSE_IMPORTANT)
53 void typecheck_print_var(FILE *file, jitdata *jd, s4 index)
57 assert(index >= 0 && index < jd->varcount);
59 typeinfo_print_type(file, var->type, &(var->typeinfo));
62 void typecheck_print_vararray(FILE *file, jitdata *jd, s4 *vars, int len)
66 for (i=0; i<len; ++i) {
69 typecheck_print_var(file, jd, *vars++);
73 #endif /* defined(TYPECHECK_VERBOSE) || defined(TYPECHECK_VERBOSE_IMPORTANT) */
76 /****************************************************************************/
78 /****************************************************************************/
80 #if defined(TYPECHECK_STATISTICS)
81 int stat_typechecked = 0;
82 int stat_methods_with_handlers = 0;
83 int stat_methods_maythrow = 0;
84 int stat_iterations[STAT_ITERATIONS+1] = { 0 };
88 int stat_merging_changed = 0;
89 int stat_blocks[STAT_BLOCKS+1] = { 0 };
90 int stat_locals[STAT_LOCALS+1] = { 0 };
92 int stat_ins_maythrow = 0;
93 int stat_ins_stack = 0;
94 int stat_ins_field = 0;
95 int stat_ins_field_unresolved = 0;
96 int stat_ins_field_uninitialized = 0;
97 int stat_ins_invoke = 0;
98 int stat_ins_invoke_unresolved = 0;
99 int stat_ins_primload = 0;
100 int stat_ins_aload = 0;
101 int stat_ins_builtin = 0;
102 int stat_ins_builtin_gen = 0;
103 int stat_ins_branch = 0;
104 int stat_ins_switch = 0;
105 int stat_ins_primitive_return = 0;
106 int stat_ins_areturn = 0;
107 int stat_ins_areturn_unresolved = 0;
108 int stat_ins_athrow = 0;
109 int stat_ins_athrow_unresolved = 0;
110 int stat_ins_unchecked = 0;
111 int stat_handlers_reached = 0;
112 int stat_savedstack = 0;
114 static void print_freq(FILE *file,int *array,int limit)
117 for (i=0; i<limit; ++i)
118 fprintf(file," %3d: %8d\n",i,array[i]);
119 fprintf(file," >=%3d: %8d\n",limit,array[limit]);
122 void typecheck_print_statistics(FILE *file) {
123 fprintf(file,"typechecked methods: %8d\n",stat_typechecked);
124 fprintf(file," with handler(s): %8d\n",stat_methods_with_handlers);
125 fprintf(file," with throw(s) : %8d\n",stat_methods_maythrow);
126 fprintf(file,"reached blocks : %8d\n",stat_reached);
127 fprintf(file,"copied states : %8d\n",stat_copied);
128 fprintf(file,"merged states : %8d\n",stat_merged);
129 fprintf(file,"merging changed : %8d\n",stat_merging_changed);
130 fprintf(file,"handlers reached : %8d\n",stat_handlers_reached);
131 fprintf(file,"saved stack (times): %8d\n",stat_savedstack);
132 fprintf(file,"instructions : %8d\n",stat_ins);
133 fprintf(file," stack : %8d\n",stat_ins_stack);
134 fprintf(file," field access : %8d\n",stat_ins_field);
135 fprintf(file," (unresolved) : %8d\n",stat_ins_field_unresolved);
136 fprintf(file," (uninit.) : %8d\n",stat_ins_field_uninitialized);
137 fprintf(file," invocations : %8d\n",stat_ins_invoke);
138 fprintf(file," (unresolved) : %8d\n",stat_ins_invoke_unresolved);
139 fprintf(file," load primitive : (currently not counted) %8d\n",stat_ins_primload);
140 fprintf(file," load address : %8d\n",stat_ins_aload);
141 fprintf(file," builtins : %8d\n",stat_ins_builtin);
142 fprintf(file," generic : %8d\n",stat_ins_builtin_gen);
143 fprintf(file," branches : %8d\n",stat_ins_branch);
144 fprintf(file," switches : %8d\n",stat_ins_switch);
145 fprintf(file," prim. return : %8d\n",stat_ins_primitive_return);
146 fprintf(file," areturn : %8d\n",stat_ins_areturn);
147 fprintf(file," (unresolved) : %8d\n",stat_ins_areturn_unresolved);
148 fprintf(file," athrow : %8d\n",stat_ins_athrow);
149 fprintf(file," (unresolved) : %8d\n",stat_ins_athrow_unresolved);
150 fprintf(file," unchecked : %8d\n",stat_ins_unchecked);
151 fprintf(file," maythrow : %8d\n",stat_ins_maythrow);
152 fprintf(file,"iterations used:\n");
153 print_freq(file,stat_iterations,STAT_ITERATIONS);
154 fprintf(file,"basic blocks per method / 10:\n");
155 print_freq(file,stat_blocks,STAT_BLOCKS);
156 fprintf(file,"locals:\n");
157 print_freq(file,stat_locals,STAT_LOCALS);
159 #endif /* defined(TYPECHECK_STATISTICS) */
162 /* typecheck_init_flags ********************************************************
164 Initialize the basic block flags for the following CFG traversal.
167 state............the current state of the verifier
168 minflags.........minimum flags value of blocks that should be
171 *******************************************************************************/
173 void typecheck_init_flags(verifier_state *state, s4 minflags)
177 /* set all BBFINISHED blocks to BBTYPECHECK_UNDEF. */
179 for (block = state->basicblocks; block; block = block->next) {
181 #ifdef TYPECHECK_DEBUG
182 /* check for invalid flags */
183 if (block->flags != BBFINISHED && block->flags != BBDELETED && block->flags != BBUNDEF)
185 LOGSTR1("block flags: %d\n",block->flags); LOGFLUSH;
186 TYPECHECK_ASSERT(false);
190 if (block->flags >= minflags) {
191 block->flags = BBTYPECHECK_UNDEF;
195 /* the first block is always reached */
197 if (state->basicblockcount && state->basicblocks[0].flags == BBTYPECHECK_UNDEF)
198 state->basicblocks[0].flags = BBTYPECHECK_REACHED;
202 /* typecheck_reset_flags *******************************************************
204 Reset the flags of basic blocks we have not reached.
207 state............the current state of the verifier
209 *******************************************************************************/
211 void typecheck_reset_flags(verifier_state *state)
215 /* check for invalid flags at exit */
217 #ifdef TYPECHECK_DEBUG
218 for (block = state->basicblocks; block; block = block->next) {
219 if (block->flags != BBDELETED
220 && block->flags != BBUNDEF
221 && block->flags != BBFINISHED
222 && block->flags != BBTYPECHECK_UNDEF) /* typecheck may never reach
223 * some exception handlers,
226 LOG2("block L%03d has invalid flags after typecheck: %d",
227 block->nr,block->flags);
228 TYPECHECK_ASSERT(false);
233 /* Delete blocks we never reached */
235 for (block = state->basicblocks; block; block = block->next) {
236 if (block->flags == BBTYPECHECK_UNDEF)
237 block->flags = BBDELETED;
242 /****************************************************************************/
243 /* TYPESTACK MACROS AND FUNCTIONS */
245 /* These macros and functions act on the 'type stack', which is a shorthand */
246 /* for the types of the stackslots of the current stack. The type of a */
247 /* stack slot is usually described by a TYPE_* constant and -- for TYPE_ADR */
248 /* -- by the typeinfo of the slot. The only thing that makes the type stack */
249 /* more complicated are returnAddresses of local subroutines, because a */
250 /* single stack slot may contain a set of more than one possible return */
251 /* address. This is handled by 'return address sets'. A return address set */
252 /* is kept as a linked list dangling off the typeinfo of the stack slot. */
253 /****************************************************************************/
255 /* typecheck_copy_types ********************************************************
257 Copy the types of the source variables to the destination variables.
260 state............current verifier state
261 srcvars..........array of variable indices to copy
262 dstvars..........array of the destination variables
263 n................number of variables to copy
266 true.............success
267 false............an exception has been thrown
269 *******************************************************************************/
271 bool typecheck_copy_types(verifier_state *state, s4 *srcvars, s4 *dstvars, s4 n)
276 jitdata *jd = state->jd;
278 for (i=0; i < n; ++i, ++srcvars, ++dstvars) {
283 if (dv->type == TYPE_ADR) {
284 TYPEINFO_CLONE(sv->typeinfo,dv->typeinfo);
291 /* typecheck_merge_types *******************************************************
293 Merge the types of the source variables into the destination variables.
296 state............current state of the verifier
297 srcvars..........source variable indices
298 dstvars..........destination variable indices
299 n................number of variables
302 typecheck_TRUE...the destination variables have been modified
303 typecheck_FALSE..the destination variables are unchanged
304 typecheck_FAIL...an exception has been thrown
306 *******************************************************************************/
308 typecheck_result typecheck_merge_types(verifier_state *state,
316 jitdata *jd = state->jd;
318 bool changed = false;
320 for (i=0; i < n; ++i, ++srcvars, ++dstvars) {
324 if (dv->type != sv->type) {
325 exceptions_throw_verifyerror(state->m,"Stack type mismatch");
326 return typecheck_FAIL;
328 if (dv->type == TYPE_ADR) {
329 if (TYPEINFO_IS_PRIMITIVE(dv->typeinfo)) {
330 /* dv has returnAddress type */
331 if (!TYPEINFO_IS_PRIMITIVE(sv->typeinfo)) {
332 exceptions_throw_verifyerror(state->m,"Merging returnAddress with reference");
333 return typecheck_FAIL;
337 /* dv has reference type */
338 if (TYPEINFO_IS_PRIMITIVE(sv->typeinfo)) {
339 exceptions_throw_verifyerror(state->m,"Merging reference with returnAddress");
340 return typecheck_FAIL;
342 r = typeinfo_merge(state->m,&(dv->typeinfo),&(sv->typeinfo));
343 if (r == typecheck_FAIL)
349 return (typecheck_result) changed;
353 /* typestate_merge *************************************************************
355 Merge the types of one state into the destination state.
358 state............current state of the verifier
359 dstvars..........indices of the destinations invars
360 dstlocals........the destinations inlocals
361 srcvars..........indices of the source's outvars
362 srclocals........the source locals
363 n................number of invars (== number of outvars)
366 typecheck_TRUE...destination state has been modified
367 typecheck_FALSE..destination state has not been modified
368 typecheck_FAIL...an exception has been thrown
370 *******************************************************************************/
372 typecheck_result typestate_merge(verifier_state *state,
373 s4 *srcvars, varinfo *srclocals,
374 s4 *dstvars, varinfo *dstlocals,
377 bool changed = false;
380 /* The stack is always merged. If there are returnAddresses on
381 * the stack they are ignored in this step. */
383 r = typecheck_merge_types(state, srcvars, dstvars, n);
384 if (r == typecheck_FAIL)
388 /* merge the locals */
390 r = typevector_merge(state->m, dstlocals, srclocals, state->numlocals);
391 if (r == typecheck_FAIL)
393 return (typecheck_result) (changed | r);
397 /* typestate_reach *************************************************************
399 Reach a destination block and propagate stack and local variable types
402 state............current state of the verifier
403 destblock........destination basic block
404 srcvars..........variable indices of the outvars to propagate
405 srclocals........local variables to propagate
406 n................number of srcvars
409 state->repeat....set to true if the verifier must iterate again
410 over the basic blocks
413 true.............success
414 false............an exception has been thrown
416 *******************************************************************************/
418 bool typestate_reach(verifier_state *state,
419 basicblock *destblock,
420 s4 *srcvars, varinfo *srclocals, s4 n)
423 bool changed = false;
426 LOG1("reaching block L%03d",destblock->nr);
427 TYPECHECK_COUNT(stat_reached);
429 destloc = destblock->inlocals;
431 if (destblock->flags == BBTYPECHECK_UNDEF) {
432 /* The destblock has never been reached before */
434 TYPECHECK_COUNT(stat_copied);
435 LOG1("block L%03d reached first time",destblock->nr);
437 if (!typecheck_copy_types(state, srcvars, destblock->invars, n))
439 typevector_copy_inplace(srclocals, destloc, state->numlocals);
443 /* The destblock has already been reached before */
445 TYPECHECK_COUNT(stat_merged);
446 LOG1("block L%03d reached before", destblock->nr);
448 r = typestate_merge(state, srcvars, srclocals,
449 destblock->invars, destblock->inlocals, n);
450 if (r == typecheck_FAIL)
453 TYPECHECK_COUNTIF(changed,stat_merging_changed);
458 destblock->flags = BBTYPECHECK_REACHED;
459 if (destblock->nr <= state->bptr->nr) {
461 state->repeat = true;
468 /* typecheck_init_locals *******************************************************
470 Initialize the local variables in the verifier state.
473 state............the current state of the verifier
474 newthis..........if true, mark the instance in <init> methods as
475 uninitialized object.
478 true.............success,
479 false............an exception has been thrown.
481 *******************************************************************************/
483 bool typecheck_init_locals(verifier_state *state, bool newthis)
489 jitdata *jd = state->jd;
492 locals = state->basicblocks[0].inlocals;
494 /* allocate parameter descriptors if necessary */
496 if (!state->m->parseddesc->params)
497 descriptor_params_from_paramtypes(state->m->parseddesc,state->m->flags);
499 /* pre-initialize variables as TYPE_VOID */
501 i = state->numlocals;
508 /* if this is an instance method initialize the "this" ref type */
510 if (!(state->m->flags & ACC_STATIC)) {
511 varindex = jd->local_map[5*0 + TYPE_ADR];
512 if (varindex != UNUSED) {
513 if (state->validlocals < 1)
514 TYPECHECK_VERIFYERROR_bool("Not enough local variables for method arguments");
515 v = locals + varindex;
517 if (state->initmethod && newthis)
518 TYPEINFO_INIT_NEWOBJECT(v->typeinfo, NULL);
520 typeinfo_init_classinfo(&(v->typeinfo), state->m->clazz);
526 LOG("'this' argument set.\n");
528 /* the rest of the arguments and the return type */
530 if (!typeinfo_init_varinfos_from_methoddesc(locals, state->m->parseddesc,
532 skip, /* skip 'this' pointer */
537 LOG("Arguments set.\n");
541 #if defined(__cplusplus)
546 * These are local overrides for various environment variables in Emacs.
547 * Please do not remove this and leave it at the end of the file, where
548 * Emacs will automagically detect them.
549 * ---------------------------------------------------------------------
552 * indent-tabs-mode: t
556 * vim:noexpandtab:sw=4:ts=4: