Line data Source code
1 : /* src/vm/jit/verify/typecheck-common.cpp - shared verifier code
2 :
3 : Copyright (C) 1996-2014
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 :
26 : #include "config.h"
27 : #include "vm/types.hpp"
28 : #include "vm/global.hpp"
29 :
30 : #include <assert.h>
31 :
32 : #include "vm/descriptor.hpp" // for typedesc, methoddesc, etc
33 : #include "vm/exceptions.hpp"
34 : #include "vm/globals.hpp"
35 : #include "vm/method.hpp"
36 :
37 : #include "vm/jit/show.hpp"
38 :
39 : #include "typecheck-common.hpp"
40 :
41 :
42 : /****************************************************************************/
43 : /* DEBUG HELPERS */
44 : /****************************************************************************/
45 :
46 : #ifdef TYPECHECK_VERBOSE_OPT
47 : bool opt_typecheckverbose = false;
48 : #endif
49 :
50 : #if defined(TYPECHECK_VERBOSE) || defined(TYPECHECK_VERBOSE_IMPORTANT)
51 :
52 : void typecheck_print_var(FILE *file, jitdata *jd, s4 index)
53 : {
54 : varinfo *var;
55 :
56 : assert(index >= 0 && index < jd->varcount);
57 : var = VAR(index);
58 : typeinfo_print_type(file, var->type, &(var->typeinfo));
59 : }
60 :
61 : void typecheck_print_vararray(FILE *file, jitdata *jd, s4 *vars, int len)
62 : {
63 : s4 i;
64 :
65 : for (i=0; i<len; ++i) {
66 : if (i)
67 : fputc(' ', file);
68 : typecheck_print_var(file, jd, *vars++);
69 : }
70 : }
71 :
72 : #endif /* defined(TYPECHECK_VERBOSE) || defined(TYPECHECK_VERBOSE_IMPORTANT) */
73 :
74 :
75 : /****************************************************************************/
76 : /* STATISTICS */
77 : /****************************************************************************/
78 :
79 : #if defined(TYPECHECK_STATISTICS)
80 : #warning port to new statistics framework
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 };
85 : int stat_reached = 0;
86 : int stat_copied = 0;
87 : int stat_merged = 0;
88 : int stat_merging_changed = 0;
89 : int stat_blocks[STAT_BLOCKS+1] = { 0 };
90 : int stat_locals[STAT_LOCALS+1] = { 0 };
91 : int stat_ins = 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;
113 :
114 : static void print_freq(FILE *file,int *array,int limit)
115 : {
116 : int i;
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]);
120 : }
121 :
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);
158 : }
159 : #endif /* defined(TYPECHECK_STATISTICS) */
160 :
161 :
162 : /* typecheck_init_state ********************************************************
163 :
164 : Initialize the basic block state for the following CFG traversal.
165 :
166 : IN:
167 : state............the current state of the verifier
168 : minflags.........minimum state value of blocks that should be
169 : considered
170 :
171 : *******************************************************************************/
172 :
173 86416 : void typecheck_init_state(verifier_state *state, basicblock::State minstate)
174 : {
175 : basicblock *block;
176 :
177 : // set all FINISHED blocks to TYPECHECK_UNDEF
178 :
179 492156 : for (block = state->basicblocks; block; block = block->next) {
180 :
181 : #ifdef TYPECHECK_DEBUG
182 : // check for invalid state
183 405740 : if (block->state != basicblock::FINISHED &&
184 : block->state != basicblock::DELETED &&
185 : block->state != basicblock::UNDEF)
186 : {
187 : OLD_LOGSTR1("block state: %d\n",block->state); OLD_LOGFLUSH;
188 0 : TYPECHECK_ASSERT(false);
189 : }
190 : #endif
191 :
192 405740 : if (block->state >= minstate) {
193 319321 : block->state = basicblock::TYPECHECK_UNDEF;
194 : }
195 : }
196 :
197 : // the first block is always reached
198 :
199 86416 : if (state->basicblockcount && state->basicblocks[0].state == basicblock::TYPECHECK_UNDEF)
200 86416 : state->basicblocks[0].state = basicblock::TYPECHECK_REACHED;
201 86416 : }
202 :
203 :
204 : /* typecheck_reset_state *******************************************************
205 :
206 : Reset the state of basic blocks we have not reached.
207 :
208 : IN:
209 : state............the current state of the verifier
210 :
211 : *******************************************************************************/
212 :
213 86399 : void typecheck_reset_state(verifier_state *state)
214 : {
215 : // check for invalid state at exit
216 :
217 : #ifdef TYPECHECK_DEBUG
218 492080 : for (basicblock *block = state->basicblocks; block; block = block->next) {
219 405681 : if (block->state != basicblock::DELETED &&
220 : block->state != basicblock::UNDEF &&
221 : block->state != basicblock::FINISHED &&
222 : block->state != basicblock::TYPECHECK_UNDEF) // typecheck may never reach
223 : // some exception handlers,
224 : // that's ok.
225 : {
226 : OLD_LOG2("block L%03d has invalid state after typecheck: %d",
227 : block->nr,block->state);
228 0 : TYPECHECK_ASSERT(false);
229 : }
230 : }
231 : #endif
232 :
233 : // Delete blocks we never reached
234 :
235 492080 : for (basicblock *block = state->basicblocks; block; block = block->next) {
236 405681 : if (block->state == basicblock::TYPECHECK_UNDEF)
237 0 : block->state = basicblock::DELETED;
238 : }
239 86399 : }
240 :
241 :
242 : /****************************************************************************/
243 : /* TYPESTACK MACROS AND FUNCTIONS */
244 : /* */
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 : /****************************************************************************/
254 :
255 : /* typecheck_copy_types ********************************************************
256 :
257 : Copy the types of the source variables to the destination variables.
258 :
259 : IN:
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
264 :
265 : RETURN VALUE:
266 : true.............success
267 : false............an exception has been thrown
268 :
269 : *******************************************************************************/
270 :
271 234346 : bool typecheck_copy_types(verifier_state *state, s4 *srcvars, s4 *dstvars, s4 n)
272 : {
273 : s4 i;
274 : varinfo *sv;
275 : varinfo *dv;
276 234346 : jitdata *jd = state->jd;
277 :
278 271157 : for (i=0; i < n; ++i, ++srcvars, ++dstvars) {
279 36811 : sv = VAR(*srcvars);
280 36811 : dv = VAR(*dstvars);
281 :
282 36811 : dv->type = sv->type;
283 36811 : if (dv->type == TYPE_ADR) {
284 29759 : typeinfo_t::clone(sv->typeinfo, dv->typeinfo);
285 : }
286 : }
287 234346 : return true;
288 : }
289 :
290 :
291 : /* typecheck_merge_types *******************************************************
292 :
293 : Merge the types of the source variables into the destination variables.
294 :
295 : IN:
296 : state............current state of the verifier
297 : srcvars..........source variable indices
298 : dstvars..........destination variable indices
299 : n................number of variables
300 :
301 : RETURN VALUE:
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
305 :
306 : *******************************************************************************/
307 :
308 191333 : typecheck_result typecheck_merge_types(verifier_state *state,
309 : s4 *srcvars,
310 : s4 *dstvars,
311 : s4 n)
312 : {
313 : s4 i;
314 : varinfo *sv;
315 : varinfo *dv;
316 191333 : jitdata *jd = state->jd;
317 : typecheck_result r;
318 191333 : bool changed = false;
319 :
320 298938 : for (i=0; i < n; ++i, ++srcvars, ++dstvars) {
321 107608 : sv = VAR(*srcvars);
322 107608 : dv = VAR(*dstvars);
323 :
324 107608 : if (dv->type != sv->type) {
325 0 : exceptions_throw_verifyerror(state->m,"Stack type mismatch");
326 0 : return typecheck_FAIL;
327 : }
328 107608 : if (dv->type == TYPE_ADR) {
329 102631 : if (dv->typeinfo.is_primitive()) {
330 : /* dv has returnAddress type */
331 0 : if (!sv->typeinfo.is_primitive()) {
332 0 : exceptions_throw_verifyerror(state->m,"Merging returnAddress with reference");
333 0 : return typecheck_FAIL;
334 : }
335 : }
336 : else {
337 : /* dv has reference type */
338 102631 : if (sv->typeinfo.is_primitive()) {
339 0 : exceptions_throw_verifyerror(state->m,"Merging reference with returnAddress");
340 0 : return typecheck_FAIL;
341 : }
342 102631 : r = dv->typeinfo.merge(state->m, &(sv->typeinfo));
343 102631 : if (r == typecheck_FAIL)
344 3 : return r;
345 102628 : changed |= r;
346 : }
347 : }
348 : }
349 191330 : return (typecheck_result) changed;
350 : }
351 :
352 :
353 : /* typestate_merge *************************************************************
354 :
355 : Merge the types of one state into the destination state.
356 :
357 : IN:
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)
364 :
365 : RETURN VALUE:
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
369 :
370 : *******************************************************************************/
371 :
372 191333 : typecheck_result typestate_merge(verifier_state *state,
373 : s4 *srcvars, varinfo *srclocals,
374 : s4 *dstvars, varinfo *dstlocals,
375 : s4 n)
376 : {
377 191333 : bool changed = false;
378 : typecheck_result r;
379 :
380 : /* The stack is always merged. If there are returnAddresses on
381 : * the stack they are ignored in this step. */
382 :
383 191333 : r = typecheck_merge_types(state, srcvars, dstvars, n);
384 191333 : if (r == typecheck_FAIL)
385 3 : return r;
386 191330 : changed |= r;
387 :
388 : /* merge the locals */
389 :
390 191330 : r = typevector_merge(state->m, dstlocals, srclocals, state->numlocals);
391 191330 : if (r == typecheck_FAIL)
392 0 : return r;
393 191330 : return (typecheck_result) (changed | r);
394 : }
395 :
396 :
397 : /* typestate_reach *************************************************************
398 :
399 : Reach a destination block and propagate stack and local variable types
400 :
401 : IN:
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
407 :
408 : OUT:
409 : state->repeat....set to true if the verifier must iterate again
410 : over the basic blocks
411 :
412 : RETURN VALUE:
413 : true.............success
414 : false............an exception has been thrown
415 :
416 : *******************************************************************************/
417 :
418 424237 : bool typestate_reach(verifier_state *state,
419 : basicblock *destblock,
420 : s4 *srcvars, varinfo *srclocals, s4 n)
421 : {
422 : varinfo *destloc;
423 424237 : bool changed = false;
424 : typecheck_result r;
425 :
426 : OLD_LOG1("reaching block L%03d",destblock->nr);
427 : TYPECHECK_COUNT(stat_reached);
428 :
429 424237 : destloc = destblock->inlocals;
430 :
431 424237 : if (destblock->state == basicblock::TYPECHECK_UNDEF) {
432 : /* The destblock has never been reached before */
433 :
434 : TYPECHECK_COUNT(stat_copied);
435 : OLD_LOG1("block L%03d reached first time",destblock->nr);
436 :
437 232904 : if (!typecheck_copy_types(state, srcvars, destblock->invars, n))
438 0 : return false;
439 232904 : typevector_copy_inplace(srclocals, destloc, state->numlocals);
440 232904 : changed = true;
441 : }
442 : else {
443 : /* The destblock has already been reached before */
444 :
445 : TYPECHECK_COUNT(stat_merged);
446 : OLD_LOG1("block L%03d reached before", destblock->nr);
447 :
448 : r = typestate_merge(state, srcvars, srclocals,
449 191333 : destblock->invars, destblock->inlocals, n);
450 191333 : if (r == typecheck_FAIL)
451 3 : return false;
452 191330 : changed = r;
453 : TYPECHECK_COUNTIF(changed,stat_merging_changed);
454 : }
455 :
456 424234 : if (changed) {
457 : OLD_LOG("changed!");
458 247448 : destblock->state = basicblock::TYPECHECK_REACHED;
459 247448 : if (destblock->nr <= state->bptr->nr) {
460 : OLD_LOG("REPEAT!");
461 10264 : state->repeat = true;
462 : }
463 : }
464 424234 : return true;
465 : }
466 :
467 :
468 : /* typecheck_init_locals *******************************************************
469 :
470 : Initialize the local variables in the verifier state.
471 :
472 : IN:
473 : state............the current state of the verifier
474 : newthis..........if true, mark the instance in <init> methods as
475 : uninitialized object.
476 :
477 : RETURN VALUE:
478 : true.............success,
479 : false............an exception has been thrown.
480 :
481 : *******************************************************************************/
482 :
483 86416 : bool typecheck_init_locals(verifier_state *state, bool newthis)
484 : {
485 : int i;
486 : int varindex;
487 : varinfo *locals;
488 : varinfo *v;
489 86416 : jitdata *jd = state->jd;
490 86416 : int skip = 0;
491 :
492 86416 : locals = state->basicblocks[0].inlocals;
493 :
494 : /* allocate parameter descriptors if necessary */
495 :
496 86416 : state->m->parseddesc->params_from_paramtypes(state->m->flags);
497 :
498 : /* pre-initialize variables as TYPE_VOID */
499 :
500 86416 : i = state->numlocals;
501 86416 : v = locals;
502 393775 : while (i--) {
503 220943 : v->type = TYPE_VOID;
504 220943 : v++;
505 : }
506 :
507 : /* if this is an instance method initialize the "this" ref type */
508 :
509 86416 : if (!(state->m->flags & ACC_STATIC)) {
510 67593 : varindex = jd->local_map[5*0 + TYPE_ADR];
511 67593 : if (varindex != jitdata::UNUSED) {
512 63512 : if (state->validlocals < 1)
513 0 : TYPECHECK_VERIFYERROR_bool("Not enough local variables for method arguments");
514 63512 : v = locals + varindex;
515 63512 : v->type = TYPE_ADR;
516 88881 : if (state->initmethod && newthis)
517 25369 : v->typeinfo.init_newobject(NULL);
518 : else
519 38143 : v->typeinfo.init_class(state->m->clazz);
520 : }
521 :
522 67593 : skip = 1;
523 : }
524 :
525 : OLD_LOG("'this' argument set.\n");
526 :
527 : /* the rest of the arguments and the return type */
528 :
529 86416 : if (!typeinfo_init_varinfos_from_methoddesc(locals, state->m->parseddesc,
530 : state->validlocals,
531 : skip, /* skip 'this' pointer */
532 : jd->local_map,
533 : &state->returntype))
534 0 : return false;
535 :
536 : OLD_LOG("Arguments set.\n");
537 86416 : return true;
538 : }
539 :
540 :
541 : /*
542 : * These are local overrides for various environment variables in Emacs.
543 : * Please do not remove this and leave it at the end of the file, where
544 : * Emacs will automagically detect them.
545 : * ---------------------------------------------------------------------
546 : * Local variables:
547 : * mode: c++
548 : * indent-tabs-mode: t
549 : * c-basic-offset: 4
550 : * tab-width: 4
551 : * End:
552 : * vim:noexpandtab:sw=4:ts=4:
553 : */
|
