1 /* src/vm/jit/verify/typecheck-common.c - shared verifier code
3 Copyright (C) 1996-2005, 2006 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
8 This file is part of CACAO.
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.
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.
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
25 Contact: cacao@cacaojvm.org
27 Authors: Edwin Steiner
38 #include "vm/global.h"
42 #include <vm/exceptions.h>
43 #include <vm/jit/show.h>
44 #include <typecheck-common.h>
46 /****************************************************************************/
48 /****************************************************************************/
50 #ifdef TYPECHECK_VERBOSE_OPT
51 bool opt_typecheckverbose = false;
54 #if defined(TYPECHECK_VERBOSE) || defined(TYPECHECK_VERBOSE_IMPORTANT)
56 void typecheck_print_var(FILE *file, jitdata *jd, s4 index)
60 assert(index >= 0 && index < jd->varcount);
62 typeinfo_print_type(file, var->type, &(var->typeinfo));
65 void typecheck_print_vararray(FILE *file, jitdata *jd, s4 *vars, int len)
69 for (i=0; i<len; ++i) {
72 typecheck_print_var(file, jd, *vars++);
76 #endif /* defined(TYPECHECK_VERBOSE) || defined(TYPECHECK_VERBOSE_IMPORTANT) */
79 /****************************************************************************/
81 /****************************************************************************/
83 #if defined(TYPECHECK_STATISTICS)
84 int stat_typechecked = 0;
85 int stat_methods_with_handlers = 0;
86 int stat_methods_maythrow = 0;
87 int stat_iterations[STAT_ITERATIONS+1] = { 0 };
91 int stat_merging_changed = 0;
92 int stat_blocks[STAT_BLOCKS+1] = { 0 };
93 int stat_locals[STAT_LOCALS+1] = { 0 };
95 int stat_ins_maythrow = 0;
96 int stat_ins_stack = 0;
97 int stat_ins_field = 0;
98 int stat_ins_field_unresolved = 0;
99 int stat_ins_field_uninitialized = 0;
100 int stat_ins_invoke = 0;
101 int stat_ins_invoke_unresolved = 0;
102 int stat_ins_primload = 0;
103 int stat_ins_aload = 0;
104 int stat_ins_builtin = 0;
105 int stat_ins_builtin_gen = 0;
106 int stat_ins_branch = 0;
107 int stat_ins_switch = 0;
108 int stat_ins_primitive_return = 0;
109 int stat_ins_areturn = 0;
110 int stat_ins_areturn_unresolved = 0;
111 int stat_ins_athrow = 0;
112 int stat_ins_athrow_unresolved = 0;
113 int stat_ins_unchecked = 0;
114 int stat_handlers_reached = 0;
115 int stat_savedstack = 0;
117 static void print_freq(FILE *file,int *array,int limit)
120 for (i=0; i<limit; ++i)
121 fprintf(file," %3d: %8d\n",i,array[i]);
122 fprintf(file," >=%3d: %8d\n",limit,array[limit]);
125 void typecheck_print_statistics(FILE *file) {
126 fprintf(file,"typechecked methods: %8d\n",stat_typechecked);
127 fprintf(file," with handler(s): %8d\n",stat_methods_with_handlers);
128 fprintf(file," with throw(s) : %8d\n",stat_methods_maythrow);
129 fprintf(file,"reached blocks : %8d\n",stat_reached);
130 fprintf(file,"copied states : %8d\n",stat_copied);
131 fprintf(file,"merged states : %8d\n",stat_merged);
132 fprintf(file,"merging changed : %8d\n",stat_merging_changed);
133 fprintf(file,"handlers reached : %8d\n",stat_handlers_reached);
134 fprintf(file,"saved stack (times): %8d\n",stat_savedstack);
135 fprintf(file,"instructions : %8d\n",stat_ins);
136 fprintf(file," stack : %8d\n",stat_ins_stack);
137 fprintf(file," field access : %8d\n",stat_ins_field);
138 fprintf(file," (unresolved) : %8d\n",stat_ins_field_unresolved);
139 fprintf(file," (uninit.) : %8d\n",stat_ins_field_uninitialized);
140 fprintf(file," invocations : %8d\n",stat_ins_invoke);
141 fprintf(file," (unresolved) : %8d\n",stat_ins_invoke_unresolved);
142 fprintf(file," load primitive : (currently not counted) %8d\n",stat_ins_primload);
143 fprintf(file," load address : %8d\n",stat_ins_aload);
144 fprintf(file," builtins : %8d\n",stat_ins_builtin);
145 fprintf(file," generic : %8d\n",stat_ins_builtin_gen);
146 fprintf(file," branches : %8d\n",stat_ins_branch);
147 fprintf(file," switches : %8d\n",stat_ins_switch);
148 fprintf(file," prim. return : %8d\n",stat_ins_primitive_return);
149 fprintf(file," areturn : %8d\n",stat_ins_areturn);
150 fprintf(file," (unresolved) : %8d\n",stat_ins_areturn_unresolved);
151 fprintf(file," athrow : %8d\n",stat_ins_athrow);
152 fprintf(file," (unresolved) : %8d\n",stat_ins_athrow_unresolved);
153 fprintf(file," unchecked : %8d\n",stat_ins_unchecked);
154 fprintf(file," maythrow : %8d\n",stat_ins_maythrow);
155 fprintf(file,"iterations used:\n");
156 print_freq(file,stat_iterations,STAT_ITERATIONS);
157 fprintf(file,"basic blocks per method / 10:\n");
158 print_freq(file,stat_blocks,STAT_BLOCKS);
159 fprintf(file,"locals:\n");
160 print_freq(file,stat_locals,STAT_LOCALS);
162 #endif /* defined(TYPECHECK_STATISTICS) */
165 /* typecheck_init_flags ********************************************************
167 Initialize the basic block flags for the following CFG traversal.
170 state............the current state of the verifier
171 minflags.........minimum flags value of blocks that should be
174 *******************************************************************************/
176 void typecheck_init_flags(verifier_state *state, s4 minflags)
180 /* set all BBFINISHED blocks to BBTYPECHECK_UNDEF. */
182 for (block = state->basicblocks; block; block = block->next) {
184 #ifdef TYPECHECK_DEBUG
185 /* check for invalid flags */
186 if (block->flags != BBFINISHED && block->flags != BBDELETED && block->flags != BBUNDEF)
188 LOGSTR1("block flags: %d\n",block->flags); LOGFLUSH;
189 TYPECHECK_ASSERT(false);
193 if (block->flags >= minflags) {
194 block->flags = BBTYPECHECK_UNDEF;
198 /* the first block is always reached */
200 if (state->basicblockcount && state->basicblocks[0].flags == BBTYPECHECK_UNDEF)
201 state->basicblocks[0].flags = BBTYPECHECK_REACHED;
205 /* typecheck_reset_flags *******************************************************
207 Reset the flags of basic blocks we have not reached.
210 state............the current state of the verifier
212 *******************************************************************************/
214 void typecheck_reset_flags(verifier_state *state)
218 /* check for invalid flags at exit */
220 #ifdef TYPECHECK_DEBUG
221 for (block = state->basicblocks; block; block = block->next) {
222 if (block->flags != BBDELETED
223 && block->flags != BBUNDEF
224 && block->flags != BBFINISHED
225 && block->flags != BBTYPECHECK_UNDEF) /* typecheck may never reach
226 * some exception handlers,
229 LOG2("block L%03d has invalid flags after typecheck: %d",
230 block->nr,block->flags);
231 TYPECHECK_ASSERT(false);
236 /* Delete blocks we never reached */
238 for (block = state->basicblocks; block; block = block->next) {
239 if (block->flags == BBTYPECHECK_UNDEF)
240 block->flags = BBDELETED;
245 /****************************************************************************/
246 /* TYPESTACK MACROS AND FUNCTIONS */
248 /* These macros and functions act on the 'type stack', which is a shorthand */
249 /* for the types of the stackslots of the current stack. The type of a */
250 /* stack slot is usually described by a TYPE_* constant and -- for TYPE_ADR */
251 /* -- by the typeinfo of the slot. The only thing that makes the type stack */
252 /* more complicated are returnAddresses of local subroutines, because a */
253 /* single stack slot may contain a set of more than one possible return */
254 /* address. This is handled by 'return address sets'. A return address set */
255 /* is kept as a linked list dangling off the typeinfo of the stack slot. */
256 /****************************************************************************/
258 /* typecheck_copy_types ********************************************************
260 Copy the types of the source variables to the destination variables.
263 state............current verifier state
264 srcvars..........array of variable indices to copy
265 dstvars..........array of the destination variables
266 n................number of variables to copy
269 true.............success
270 false............an exception has been thrown
272 *******************************************************************************/
274 bool typecheck_copy_types(verifier_state *state, s4 *srcvars, s4 *dstvars, s4 n)
279 jitdata *jd = state->jd;
281 for (i=0; i < n; ++i, ++srcvars, ++dstvars) {
286 if (dv->type == TYPE_ADR) {
287 TYPEINFO_CLONE(sv->typeinfo,dv->typeinfo);
294 /* typecheck_merge_types *******************************************************
296 Merge the types of the source variables into the destination variables.
299 state............current state of the verifier
300 srcvars..........source variable indices
301 dstvars..........destination variable indices
302 n................number of variables
305 typecheck_TRUE...the destination variables have been modified
306 typecheck_FALSE..the destination variables are unchanged
307 typecheck_FAIL...an exception has been thrown
309 *******************************************************************************/
311 typecheck_result typecheck_merge_types(verifier_state *state,
319 jitdata *jd = state->jd;
321 bool changed = false;
323 for (i=0; i < n; ++i, ++srcvars, ++dstvars) {
327 if (dv->type != sv->type) {
328 exceptions_throw_verifyerror(state->m,"Stack type mismatch");
329 return typecheck_FAIL;
331 if (dv->type == TYPE_ADR) {
332 if (TYPEINFO_IS_PRIMITIVE(dv->typeinfo)) {
333 /* dv has returnAddress type */
334 if (!TYPEINFO_IS_PRIMITIVE(sv->typeinfo)) {
335 exceptions_throw_verifyerror(state->m,"Merging returnAddress with reference");
336 return typecheck_FAIL;
340 /* dv has reference type */
341 if (TYPEINFO_IS_PRIMITIVE(sv->typeinfo)) {
342 exceptions_throw_verifyerror(state->m,"Merging reference with returnAddress");
343 return typecheck_FAIL;
345 r = typeinfo_merge(state->m,&(dv->typeinfo),&(sv->typeinfo));
346 if (r == typecheck_FAIL)
356 /* typestate_merge *************************************************************
358 Merge the types of one state into the destination state.
361 state............current state of the verifier
362 dstvars..........indices of the destinations invars
363 dstlocals........the destinations inlocals
364 srcvars..........indices of the source's outvars
365 srclocals........the source locals
366 n................number of invars (== number of outvars)
369 typecheck_TRUE...destination state has been modified
370 typecheck_FALSE..destination state has not been modified
371 typecheck_FAIL...an exception has been thrown
373 *******************************************************************************/
375 typecheck_result typestate_merge(verifier_state *state,
376 s4 *srcvars, varinfo *srclocals,
377 s4 *dstvars, varinfo *dstlocals,
380 bool changed = false;
383 /* The stack is always merged. If there are returnAddresses on
384 * the stack they are ignored in this step. */
386 r = typecheck_merge_types(state, srcvars, dstvars, n);
387 if (r == typecheck_FAIL)
391 /* merge the locals */
393 r = typevector_merge(state->m, dstlocals, srclocals, state->numlocals);
394 if (r == typecheck_FAIL)
400 /* typestate_reach *************************************************************
402 Reach a destination block and propagate stack and local variable types
405 state............current state of the verifier
406 destblock........destination basic block
407 srcvars..........variable indices of the outvars to propagate
408 srclocals........local variables to propagate
409 n................number of srcvars
412 state->repeat....set to true if the verifier must iterate again
413 over the basic blocks
416 true.............success
417 false............an exception has been thrown
419 *******************************************************************************/
421 bool typestate_reach(verifier_state *state,
422 basicblock *destblock,
423 s4 *srcvars, varinfo *srclocals, s4 n)
426 bool changed = false;
429 LOG1("reaching block L%03d",destblock->nr);
430 TYPECHECK_COUNT(stat_reached);
432 destloc = destblock->inlocals;
434 if (destblock->flags == BBTYPECHECK_UNDEF) {
435 /* The destblock has never been reached before */
437 TYPECHECK_COUNT(stat_copied);
438 LOG1("block L%03d reached first time",destblock->nr);
440 if (!typecheck_copy_types(state, srcvars, destblock->invars, n))
442 typevector_copy_inplace(srclocals, destloc, state->numlocals);
446 /* The destblock has already been reached before */
448 TYPECHECK_COUNT(stat_merged);
449 LOG1("block L%03d reached before", destblock->nr);
451 r = typestate_merge(state, srcvars, srclocals,
452 destblock->invars, destblock->inlocals, n);
453 if (r == typecheck_FAIL)
456 TYPECHECK_COUNTIF(changed,stat_merging_changed);
461 destblock->flags = BBTYPECHECK_REACHED;
462 if (destblock->nr <= state->bptr->nr) {
464 state->repeat = true;
471 /* typecheck_init_locals *******************************************************
473 Initialize the local variables in the verifier state.
476 state............the current state of the verifier
477 newthis..........if true, mark the instance in <init> methods as
478 uninitialized object.
481 true.............success,
482 false............an exception has been thrown.
484 *******************************************************************************/
486 bool typecheck_init_locals(verifier_state *state, bool newthis)
492 jitdata *jd = state->jd;
495 locals = state->basicblocks[0].inlocals;
497 /* allocate parameter descriptors if necessary */
499 if (!state->m->parseddesc->params)
500 if (!descriptor_params_from_paramtypes(state->m->parseddesc,state->m->flags))
503 /* pre-initialize variables as TYPE_VOID */
505 i = state->numlocals;
512 /* if this is an instance method initialize the "this" ref type */
514 if (!(state->m->flags & ACC_STATIC)) {
515 varindex = jd->local_map[5*0 + TYPE_ADR];
516 if (varindex != UNUSED) {
517 if (state->validlocals < 1)
518 TYPECHECK_VERIFYERROR_bool("Not enough local variables for method arguments");
519 v = locals + varindex;
521 if (state->initmethod && newthis)
522 TYPEINFO_INIT_NEWOBJECT(v->typeinfo, NULL);
524 typeinfo_init_classinfo(&(v->typeinfo), state->m->class);
530 LOG("'this' argument set.\n");
532 /* the rest of the arguments and the return type */
534 if (!typeinfo_init_varinfos_from_methoddesc(locals, state->m->parseddesc,
536 skip, /* skip 'this' pointer */
541 LOG("Arguments set.\n");
547 * These are local overrides for various environment variables in Emacs.
548 * Please do not remove this and leave it at the end of the file, where
549 * Emacs will automagically detect them.
550 * ---------------------------------------------------------------------
553 * indent-tabs-mode: t
557 * vim:noexpandtab:sw=4:ts=4: