1 /* src/vm/jit/verify/typecheck.c - typechecking (part of bytecode verification)
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
29 Changes: Christian Thalinger
31 $Id: typecheck.c 5214 2006-08-07 15:30:19Z twisti $
37 What's the purpose of the `typechecker`?
38 ----------------------------------------
40 The typechecker analyses (the intermediate repr. of) the bytecode of
41 each method and ensures that for each instruction the values on the
42 stack and in local variables are of the correct type whenever the
43 instruction is executed.
45 type checking is a mandatory part of bytecode verification.
48 How does the typechecker work?
49 ------------------------------
51 The JVM stack and the local variables are not statically typed, so the
52 typechecker has to *infer* the static types of stack slots and local
53 variables at each point of the method. The JVM spec imposes a lot of
54 restrictions on the bytecode in order to guarantee that this is always
57 Basically the typechecker solves the data flow equations of the method.
58 This is done in the usual way for a forward data flow analysis: Starting
59 from the entry point of the method the typechecker follows the CFG and
60 records the type of each stack slot and local variable at each point[1].
61 When two or more control flow paths merge at a point, the union of the
62 types for each slot/variable is taken. The algorithm continues to follow
63 all possible paths[2] until the recorded types do not change anymore (ie.
64 the equations have been solved).
66 If the solution has been reached and the resulting types are valid for
67 all instructions, then type checking terminates with success, otherwise
68 an exception is thrown.
71 Why is this code so damn complicated?
72 -------------------------------------
74 Short answer: The devil's in the details.
76 While the basic operation of the typechecker is no big deal, there are
77 many properties of Java bytecode which make type checking hard. Some of
78 them are not even addressed in the JVM spec. Some problems and their
81 *) Finding a good representation of the union of two reference types is
82 difficult because of multiple inheritance of interfaces.
84 Solution: The typeinfo system can represent such "merged" types by a
85 list of proper subclasses of a class. Example:
87 typeclass=java.lang.Object merged={ InterfaceA, InterfaceB }
89 represents the result of merging two interface types "InterfaceA"
92 *) When the code of a method is verified, there may still be unresolved
93 references to classes/methods/fields in the code, which we may not force
94 to be resolved eagerly. (A similar problem arises because of the special
95 checks for protected members.)
97 Solution: The typeinfo system knows how to deal with unresolved
98 class references. Whenever a check has to be performed for an
99 unresolved type, the type is annotated with constraints representing
100 the check. Later, when the type is resolved, the constraints are
101 checked. (See the constrain_unresolved_... and the resolve_...
104 *) The boundaries of jsr subroutines are not well-defined. For a given
105 instruction it may be impossible to tell whether it is part of a
106 subroutine, or to which subroutine it belongs.
108 Solution: The typechecker implements a method developed by
109 Alessandro Coglio[4] which treats each returnAddress as a distinct
110 type that is not merged with other returnAddresses. This way, when a
111 RET instruction is reached, we know exactly which types to propagate
112 to which return target among the possible targets of the RET. The
113 downside of this method is, that for each slot/variable we must
114 store not just one type, but one type *for each possible use of the
115 returnAddresses* that currently are in a slot/variable.[5]
117 *) Checks for uninitialized object instances are hard because after the
118 invocation of <init> on an uninitialized object *all* slots/variables
119 referring to this object (and exactly those slots/variables) must be
120 marked as initialized.
122 Solution: The JVM spec describes a solution, which has been
123 implemented in this typechecker.
128 [1] Actually only the types of slots/variables at the start of each
129 basic block are remembered. Within a basic block the algorithm only keeps
130 the types of the slots/variables for the "current" instruction which is
133 [2] Actually the algorithm iterates through the basic block list until
134 there are no more changes. Theoretically it would be wise to sort the
135 basic blocks topologically beforehand, but the number of average/max
136 iterations observed is so low, that this was not deemed necessary.
138 [3] This is similar to a method proposed by: Alessandro Coglio et al., A
139 Formal Specification of Java Class Loading, Technical Report, Kestrel
140 Institute April 2000, revised July 2000
141 http://www.kestrel.edu/home/people/coglio/loading.pdf
142 An important difference is that Coglio's subtype constraints are checked
143 after loading, while our constraints are checked when the field/method
144 is accessed for the first time, so we can guarantee lexically correct
147 [4] Alessandro Coglio, Simple Verification Technique for Complex Java
148 Bytecode Subroutines, 4th ECOOP Workshop on Formal Techniques for
149 Java-like Programs, June 2002
150 http://www.kestrel.edu/home/people/coglio/ftjp02.pdf
152 [5] This is a major source of code complexity. The main data structures
153 dealing with this are the "typevector set" and the typestack. The
154 "typevector set" is a set of alternative typevectors, such that each
155 typevector specifies the types of the local variables for a single
156 combination of returnAddresses used. Thus we support full polymorphism
157 of subroutines over the types of local variables. The typestack,
158 however, does not support polymorphism, both for historical and JVM-spec
159 reasons. A slot of the typestack may, however, contain multiple
160 alternative returnAddresses, which is realized by a linked list hanging
161 of the typeinfo of the stack slot.
169 #include "vm/types.h"
170 #include "vm/global.h"
172 #ifdef ENABLE_VERIFIER
174 #include "mm/memory.h"
175 #include "toolbox/logging.h"
176 #include "native/native.h"
177 #include "vm/builtin.h"
178 #include "vm/jit/patcher.h"
179 #include "vm/loader.h"
180 #include "vm/options.h"
181 #include "vm/jit/jit.h"
182 #include "vm/jit/show.h"
183 #include "vm/access.h"
184 #include "vm/resolve.h"
185 #include "vm/exceptions.h"
188 /****************************************************************************/
190 /****************************************************************************/
192 #ifdef TYPECHECK_DEBUG
193 #define TYPECHECK_ASSERT(cond) assert(cond)
195 #define TYPECHECK_ASSERT(cond)
198 #ifdef TYPECHECK_VERBOSE_OPT
199 bool opt_typecheckverbose = false;
200 FILE *typecheck_logfile;
201 #define DOLOG(action) do { if (opt_typecheckverbose) {action;} } while(0)
203 #define DOLOG(action)
206 #ifdef TYPECHECK_VERBOSE
207 #define TYPECHECK_VERBOSE_IMPORTANT
208 #define LOG(str) DOLOG(log_text(str))
209 #define LOG1(str,a) DOLOG(dolog(str,a))
210 #define LOG2(str,a,b) DOLOG(dolog(str,a,b))
211 #define LOG3(str,a,b,c) DOLOG(dolog(str,a,b,c))
212 #define LOGIF(cond,str) DOLOG(do {if (cond) log_text(str);} while(0))
213 #ifdef TYPEINFO_DEBUG
214 #define LOGINFO(info) DOLOG(do {typeinfo_print_short(typecheck_logfile,(info));log_finish();} while(0))
216 #define LOGINFO(info)
217 #define typevectorset_print(x,y,z)
219 #define LOGFLUSH DOLOG(fflush(typecheck_logfile))
220 #define LOGNL DOLOG(log_finish())
221 #define LOGSTR(str) DOLOG(log_print(str))
222 #define LOGSTR1(str,a) DOLOG(log_print(str,a))
223 #define LOGSTR2(str,a,b) DOLOG(log_print(str,a,b))
224 #define LOGSTR3(str,a,b,c) DOLOG(log_print(str,a,b,c))
225 #define LOGNAME(c) DOLOG(log_message_utf("class: ",(IS_CLASSREF(c) ? c.ref->name : c.cls->name)))
226 #define LOGMETHOD(str,m) DOLOG(log_message_method(str,m))
230 #define LOG2(str,a,b)
231 #define LOG3(str,a,b,c)
232 #define LOGIF(cond,str)
233 #define LOGINFO(info)
237 #define LOGSTR1(str,a)
238 #define LOGSTR2(str,a,b)
239 #define LOGSTR3(str,a,b,c)
241 #define LOGMETHOD(str,m)
244 #ifdef TYPECHECK_VERBOSE_IMPORTANT
245 #define LOGimp(str) DOLOG(log_text(str))
246 #define LOGimpSTR(str) DOLOG(log_print(str))
249 #define LOGimpSTR(str)
252 #if defined(TYPECHECK_VERBOSE) || defined(TYPECHECK_VERBOSE_IMPORTANT)
258 typestack_print(FILE *file,stackptr stack)
260 #ifdef TYPEINFO_DEBUG
262 /*fprintf(file,"<%p>",stack);*/
263 typeinfo_print_stacktype(file,stack->type,&(stack->typeinfo));
265 if (stack) fprintf(file," ");
272 typestate_print(FILE *file,stackptr instack,typevector *localset,int size)
274 fprintf(file,"Stack: ");
275 typestack_print(file,instack);
276 fprintf(file," Locals:");
277 typevectorset_print(file,localset,size);
282 /****************************************************************************/
284 /****************************************************************************/
286 #ifdef TYPECHECK_DEBUG
287 /*#define TYPECHECK_STATISTICS*/
290 #ifdef TYPECHECK_STATISTICS
291 #define STAT_ITERATIONS 10
292 #define STAT_BLOCKS 10
293 #define STAT_LOCALS 16
295 static int stat_typechecked = 0;
296 static int stat_typechecked_jsr = 0;
297 static int stat_methods_with_handlers = 0;
298 static int stat_methods_maythrow = 0;
299 static int stat_iterations[STAT_ITERATIONS+1] = { 0 };
300 static int stat_reached = 0;
301 static int stat_copied = 0;
302 static int stat_merged = 0;
303 static int stat_merging_changed = 0;
304 static int stat_backwards = 0;
305 static int stat_blocks[STAT_BLOCKS+1] = { 0 };
306 static int stat_locals[STAT_LOCALS+1] = { 0 };
307 static int stat_ins = 0;
308 static int stat_ins_maythrow = 0;
309 static int stat_ins_stack = 0;
310 static int stat_ins_field = 0;
311 static int stat_ins_field_unresolved = 0;
312 static int stat_ins_field_uninitialized = 0;
313 static int stat_ins_invoke = 0;
314 static int stat_ins_invoke_unresolved = 0;
315 static int stat_ins_primload = 0;
316 static int stat_ins_aload = 0;
317 static int stat_ins_builtin = 0;
318 static int stat_ins_builtin_gen = 0;
319 static int stat_ins_branch = 0;
320 static int stat_ins_switch = 0;
321 static int stat_ins_primitive_return = 0;
322 static int stat_ins_areturn = 0;
323 static int stat_ins_areturn_unresolved = 0;
324 static int stat_ins_athrow = 0;
325 static int stat_ins_athrow_unresolved = 0;
326 static int stat_ins_unchecked = 0;
327 static int stat_handlers_reached = 0;
328 static int stat_savedstack = 0;
330 #define TYPECHECK_MARK(var) ((var) = true)
331 #define TYPECHECK_COUNT(cnt) (cnt)++
332 #define TYPECHECK_COUNTIF(cond,cnt) do{if(cond) (cnt)++;} while(0)
333 #define TYPECHECK_COUNT_FREQ(array,val,limit) \
335 if ((val) < (limit)) (array)[val]++; \
336 else (array)[limit]++; \
339 static void print_freq(FILE *file,int *array,int limit)
342 for (i=0; i<limit; ++i)
343 fprintf(file," %3d: %8d\n",i,array[i]);
344 fprintf(file," >=%3d: %8d\n",limit,array[limit]);
347 void typecheck_print_statistics(FILE *file) {
348 fprintf(file,"typechecked methods: %8d\n",stat_typechecked);
349 fprintf(file," with JSR : %8d\n",stat_typechecked_jsr);
350 fprintf(file," with handler(s): %8d\n",stat_methods_with_handlers);
351 fprintf(file," with throw(s) : %8d\n",stat_methods_maythrow);
352 fprintf(file,"reached blocks : %8d\n",stat_reached);
353 fprintf(file,"copied states : %8d\n",stat_copied);
354 fprintf(file,"merged states : %8d\n",stat_merged);
355 fprintf(file,"merging changed : %8d\n",stat_merging_changed);
356 fprintf(file,"backwards branches : %8d\n",stat_backwards);
357 fprintf(file,"handlers reached : %8d\n",stat_handlers_reached);
358 fprintf(file,"saved stack (times): %8d\n",stat_savedstack);
359 fprintf(file,"instructions : %8d\n",stat_ins);
360 fprintf(file," stack : %8d\n",stat_ins_stack);
361 fprintf(file," field access : %8d\n",stat_ins_field);
362 fprintf(file," (unresolved) : %8d\n",stat_ins_field_unresolved);
363 fprintf(file," (uninit.) : %8d\n",stat_ins_field_uninitialized);
364 fprintf(file," invocations : %8d\n",stat_ins_invoke);
365 fprintf(file," (unresolved) : %8d\n",stat_ins_invoke_unresolved);
366 fprintf(file," load primitive : (currently not counted) %8d\n",stat_ins_primload);
367 fprintf(file," load address : %8d\n",stat_ins_aload);
368 fprintf(file," builtins : %8d\n",stat_ins_builtin);
369 fprintf(file," generic : %8d\n",stat_ins_builtin_gen);
370 fprintf(file," branches : %8d\n",stat_ins_branch);
371 fprintf(file," switches : %8d\n",stat_ins_switch);
372 fprintf(file," prim. return : %8d\n",stat_ins_primitive_return);
373 fprintf(file," areturn : %8d\n",stat_ins_areturn);
374 fprintf(file," (unresolved) : %8d\n",stat_ins_areturn_unresolved);
375 fprintf(file," athrow : %8d\n",stat_ins_athrow);
376 fprintf(file," (unresolved) : %8d\n",stat_ins_athrow_unresolved);
377 fprintf(file," unchecked : %8d\n",stat_ins_unchecked);
378 fprintf(file," maythrow : %8d\n",stat_ins_maythrow);
379 fprintf(file,"iterations used:\n");
380 print_freq(file,stat_iterations,STAT_ITERATIONS);
381 fprintf(file,"basic blocks per method / 10:\n");
382 print_freq(file,stat_blocks,STAT_BLOCKS);
383 fprintf(file,"locals:\n");
384 print_freq(file,stat_locals,STAT_LOCALS);
389 #define TYPECHECK_COUNT(cnt)
390 #define TYPECHECK_MARK(var)
391 #define TYPECHECK_COUNTIF(cond,cnt)
392 #define TYPECHECK_COUNT_FREQ(array,val,limit)
395 /****************************************************************************/
396 /* MACROS FOR THROWING EXCEPTIONS */
397 /****************************************************************************/
399 #define TYPECHECK_VERIFYERROR_ret(m,msg,retval) \
401 exceptions_throw_verifyerror((m), (msg)); \
405 #define TYPECHECK_VERIFYERROR_main(msg) TYPECHECK_VERIFYERROR_ret(state.m,(msg),NULL)
406 #define TYPECHECK_VERIFYERROR_bool(msg) TYPECHECK_VERIFYERROR_ret(state->m,(msg),false)
408 /****************************************************************************/
409 /* MACROS FOR STACK SLOT TYPE CHECKING */
410 /****************************************************************************/
412 #define TYPECHECK_CHECK_TYPE(sp,tp,msg) \
414 if ((sp)->type != (tp)) { \
415 exceptions_throw_verifyerror(state->m, (msg)); \
420 #define TYPECHECK_INT(sp) TYPECHECK_CHECK_TYPE(sp,TYPE_INT,"Expected to find integer on stack")
421 #define TYPECHECK_LNG(sp) TYPECHECK_CHECK_TYPE(sp,TYPE_LNG,"Expected to find long on stack")
422 #define TYPECHECK_FLT(sp) TYPECHECK_CHECK_TYPE(sp,TYPE_FLT,"Expected to find float on stack")
423 #define TYPECHECK_DBL(sp) TYPECHECK_CHECK_TYPE(sp,TYPE_DBL,"Expected to find double on stack")
424 #define TYPECHECK_ADR(sp) TYPECHECK_CHECK_TYPE(sp,TYPE_ADR,"Expected to find object on stack")
426 /****************************************************************************/
427 /* VERIFIER STATE STRUCT */
428 /****************************************************************************/
430 /* verifier_state - This structure keeps the current state of the */
431 /* bytecode verifier for passing it between verifier functions. */
433 typedef struct verifier_state {
434 stackptr curstack; /* input stack top for current instruction */
435 instruction *iptr; /* pointer to current instruction */
436 basicblock *bptr; /* pointer to current basic block */
438 methodinfo *m; /* the current method */
439 codegendata *cd; /* codegendata for current method */
440 registerdata *rd; /* registerdata for current method */
442 s4 numlocals; /* number of local variables */
443 s4 validlocals; /* number of Java-accessible locals */
444 void *localbuf; /* local variable types for each block start */
445 typevector *localset; /* typevector set for local variables */
446 typedescriptor returntype; /* return type of the current method */
448 stackptr savedstackbuf; /* buffer for saving the stack */
449 stackptr savedstack; /* saved instack of current block */
451 exceptiontable **handlers; /* active exception handlers */
452 stackelement excstack; /* instack for exception handlers */
454 bool repeat; /* if true, blocks are iterated over again */
455 bool initmethod; /* true if this is an "<init>" method */
456 bool jsrencountered; /* true if we there was a JSR */
458 #ifdef TYPECHECK_STATISTICS
459 bool stat_maythrow; /* at least one instruction may throw */
463 /****************************************************************************/
464 /* TYPESTACK MACROS AND FUNCTIONS */
466 /* These macros and functions act on the 'type stack', which is a shorthand */
467 /* for the types of the stackslots of the current stack. The type of a */
468 /* stack slot is usually described by a TYPE_* constant and -- for TYPE_ADR */
469 /* -- by the typeinfo of the slot. The only thing that makes the type stack */
470 /* more complicated are returnAddresses of local subroutines, because a */
471 /* single stack slot may contain a set of more than one possible return */
472 /* address. This is handled by 'return address sets'. A return address set */
473 /* is kept as a linked list dangling off the typeinfo of the stack slot. */
474 /****************************************************************************/
476 #define TYPESTACK_IS_RETURNADDRESS(sptr) \
477 TYPE_IS_RETURNADDRESS((sptr)->type,(sptr)->typeinfo)
479 #define TYPESTACK_RETURNADDRESSSET(sptr) \
480 ((typeinfo_retaddr_set*)TYPEINFO_RETURNADDRESS((sptr)->typeinfo))
482 #define RETURNADDRESSSET_SEEK(set,pos) \
483 do {int i; for (i=pos;i--;) set=set->alt;} while(0)
485 /* typestack_copy **************************************************************
487 Copy the types on the given stack to the destination stack.
489 This function does a straight forward copy except for returnAddress types.
490 For returnAddress slots only the return addresses corresponding to
491 typevectors in the SELECTED set are copied.
494 state............current verifier state
495 y................stack with types to copy
496 selected.........set of selected typevectors
499 *dst.............the destination stack
502 true.............success
503 false............an exception has been thrown
505 *******************************************************************************/
508 typestack_copy(verifier_state *state,stackptr dst,stackptr y,typevector *selected)
511 typeinfo_retaddr_set *sety;
512 typeinfo_retaddr_set *new;
513 typeinfo_retaddr_set **next;
516 for (;dst; dst=dst->prev, y=y->prev) {
517 /* XXX only check the following two in debug mode? */
519 exceptions_throw_verifyerror(state->m,"Stack depth mismatch");
522 if (dst->type != y->type) {
523 exceptions_throw_verifyerror(state->m,"Stack type mismatch");
526 LOG3("copy %p -> %p (type %d)",y,dst,dst->type);
527 if (dst->type == TYPE_ADR) {
528 if (TYPEINFO_IS_PRIMITIVE(y->typeinfo)) {
529 /* We copy the returnAddresses from the selected
532 LOG("copying returnAddress");
533 sety = TYPESTACK_RETURNADDRESSSET(y);
535 for (k=0,sel=selected; sel; sel=sel->alt) {
536 LOG1("selected k=%d",sel->k);
541 *next = DNEW(typeinfo_retaddr_set);
542 (*next)->addr = sety->addr;
543 next = &((*next)->alt);
546 TYPEINFO_INIT_RETURNADDRESS(dst->typeinfo,new);
549 TYPEINFO_CLONE(y->typeinfo,dst->typeinfo);
554 exceptions_throw_verifyerror(state->m,"Stack depth mismatch");
560 /* typestack_put_retaddr *******************************************************
562 Put a returnAddress into a stack slot.
564 The stack slot receives a set of return addresses with as many members as
565 there are typevectors in the local variable set.
568 retaddr..........the returnAddress to set (a basicblock *)
569 loc..............the local variable typevector set
572 *dst.............the destination stack slot
574 *******************************************************************************/
577 typestack_put_retaddr(stackptr dst,void *retaddr,typevector *loc)
579 TYPECHECK_ASSERT(dst->type == TYPE_ADR);
581 TYPEINFO_INIT_RETURNADDRESS(dst->typeinfo,NULL);
582 for (;loc; loc=loc->alt) {
583 typeinfo_retaddr_set *set = DNEW(typeinfo_retaddr_set);
585 set->alt = TYPESTACK_RETURNADDRESSSET(dst);
586 TYPEINFO_INIT_RETURNADDRESS(dst->typeinfo,set);
590 /* typestack_collapse **********************************************************
592 Collapse the given stack by shortening all return address sets to a single
596 *dst.............the destination stack to collapse
598 *******************************************************************************/
601 typestack_collapse(stackptr dst)
603 for (; dst; dst = dst->prev) {
604 if (TYPESTACK_IS_RETURNADDRESS(dst))
605 TYPESTACK_RETURNADDRESSSET(dst)->alt = NULL;
609 /* typestack_merge *************************************************************
611 Merge the types on one stack into the destination stack.
614 state............current state of the verifier
615 dst..............the destination stack
616 y................the second stack
619 *dst.............receives the result of the stack merge
622 typecheck_TRUE...*dst has been modified
623 typecheck_FALSE..*dst has not been modified
624 typecheck_FAIL...an exception has been thrown
626 *******************************************************************************/
628 static typecheck_result
629 typestack_merge(verifier_state *state,stackptr dst,stackptr y)
632 bool changed = false;
634 for (; dst; dst = dst->prev, y=y->prev) {
636 exceptions_throw_verifyerror(state->m,"Stack depth mismatch");
637 return typecheck_FAIL;
639 if (dst->type != y->type) {
640 exceptions_throw_verifyerror(state->m,"Stack type mismatch");
641 return typecheck_FAIL;
643 if (dst->type == TYPE_ADR) {
644 if (TYPEINFO_IS_PRIMITIVE(dst->typeinfo)) {
645 /* dst has returnAddress type */
646 if (!TYPEINFO_IS_PRIMITIVE(y->typeinfo)) {
647 exceptions_throw_verifyerror(state->m,"Merging returnAddress with reference");
648 return typecheck_FAIL;
652 /* dst has reference type */
653 if (TYPEINFO_IS_PRIMITIVE(y->typeinfo)) {
654 exceptions_throw_verifyerror(state->m,"Merging reference with returnAddress");
655 return typecheck_FAIL;
657 r = typeinfo_merge(state->m,&(dst->typeinfo),&(y->typeinfo));
658 if (r == typecheck_FAIL)
665 exceptions_throw_verifyerror(state->m,"Stack depth mismatch");
666 return typecheck_FAIL;
671 /* typestack_add ***************************************************************
673 Add the return addresses in the given stack at a given k-index to the
674 corresponding return address sets in the destination stack.
677 dst..............the destination stack
678 y................the second stack
679 ky...............the k-index which should be selected from the Y stack
682 *dst.............receives the result of adding the addresses
684 *******************************************************************************/
687 typestack_add(stackptr dst,stackptr y,int ky)
689 typeinfo_retaddr_set *setd;
690 typeinfo_retaddr_set *sety;
692 for (; dst; dst = dst->prev, y=y->prev) {
693 if (TYPESTACK_IS_RETURNADDRESS(dst)) {
694 setd = TYPESTACK_RETURNADDRESSSET(dst);
695 sety = TYPESTACK_RETURNADDRESSSET(y);
696 RETURNADDRESSSET_SEEK(sety,ky);
699 setd->alt = DNEW(typeinfo_retaddr_set);
700 setd->alt->addr = sety->addr;
701 setd->alt->alt = NULL;
706 /* typestack_separable_with ****************************************************
708 This function answers the question: If variant 'kb' of typestack 'b' is
709 added to typestack 'a', will the result be separable?
711 A typestack is called 'separable' if it has at least one slot of type
712 returnAddress that contains at least two different return addresses.
713 (ie. a RET using the value in this slot could go to more than one target)
716 a................the first typestack
717 b................the second typestack
718 kb...............the k-index of the variant that should be selected
722 true.............the result would be separable
723 false............the result would not be separable
726 'a' and 'b' are assumed to have passed typestack_canmerge!
728 *******************************************************************************/
731 typestack_separable_with(stackptr a,stackptr b,int kb)
733 typeinfo_retaddr_set *seta;
734 typeinfo_retaddr_set *setb;
736 for (; a; a = a->prev, b = b->prev) {
738 if (TYPESTACK_IS_RETURNADDRESS(a)) {
739 TYPECHECK_ASSERT(TYPESTACK_IS_RETURNADDRESS(b));
740 seta = TYPESTACK_RETURNADDRESSSET(a);
741 setb = TYPESTACK_RETURNADDRESSSET(b);
742 RETURNADDRESSSET_SEEK(setb,kb);
744 for (;seta;seta=seta->alt)
745 if (seta->addr != setb->addr) return true;
748 TYPECHECK_ASSERT(!b);
752 /* typestack_separable_from ****************************************************
754 This function answers the question: Is variant 'ka' of typestack 'a'
755 separable from variant 'kb' of typestack 'b'?
757 Two variants of typestacks are called 'separable' from each other, if there
758 is at least one slot for which the variants contain different return addresses.
759 (ie. a RET using the value in this slot would go to one target in the first
760 variant and to another target in the second variant)
763 a................the first typestack
764 ka...............the k-index of the variant that should be selected
766 b................the second typestack
767 kb...............the k-index of the variant that should be selected
771 true.............the variants are separable
772 false............the variants are not separable
775 'a' and 'b' are assumed to have passed typestack_canmerge!
777 *******************************************************************************/
780 typestack_separable_from(stackptr a,int ka,stackptr b,int kb)
782 typeinfo_retaddr_set *seta;
783 typeinfo_retaddr_set *setb;
785 for (; a; a = a->prev, b = b->prev) {
787 if (TYPESTACK_IS_RETURNADDRESS(a)) {
788 TYPECHECK_ASSERT(TYPESTACK_IS_RETURNADDRESS(b));
789 seta = TYPESTACK_RETURNADDRESSSET(a);
790 setb = TYPESTACK_RETURNADDRESSSET(b);
791 RETURNADDRESSSET_SEEK(seta,ka);
792 RETURNADDRESSSET_SEEK(setb,kb);
794 if (seta->addr != setb->addr) return true;
797 TYPECHECK_ASSERT(!b);
801 /****************************************************************************/
802 /* TYPESTATE FUNCTIONS */
804 /* These functions act on the 'type state', which comprises: */
805 /* - the types of the stack slots of the current stack */
806 /* - the set of type vectors describing the local variables */
807 /****************************************************************************/
809 /* typestate_merge *************************************************************
811 Merge the types of one state into the destination state.
814 state............current state of the verifier
815 deststack........the destination stack
816 destloc..........the destination set of local variable typevectors
817 ystack...........the second stack
818 yloc.............the second set of local variable typevectors
821 *deststack.......receives the result of the stack merge
822 *destloc.........receives the result of the local variable merge
825 typecheck_TRUE...destination state has been modified
826 typecheck_FALSE..destination state has not been modified
827 typecheck_FAIL...an exception has been thrown
829 *******************************************************************************/
831 static typecheck_result
832 typestate_merge(verifier_state *state,
833 stackptr deststack,typevector *destloc,
834 stackptr ystack,typevector *yloc)
836 typevector *dvec,*yvec;
838 bool changed = false;
842 LOGSTR("dstack: "); DOLOG(typestack_print(typecheck_logfile,deststack)); LOGNL;
843 LOGSTR("ystack: "); DOLOG(typestack_print(typecheck_logfile,ystack)); LOGNL;
844 LOGSTR("dloc : "); DOLOG(typevectorset_print(typecheck_logfile,destloc,state->numlocals)); LOGNL;
845 LOGSTR("yloc : "); DOLOG(typevectorset_print(typecheck_logfile,yloc,state->numlocals)); LOGNL;
848 /* The stack is always merged. If there are returnAddresses on
849 * the stack they are ignored in this step. */
851 r = typestack_merge(state,deststack,ystack);
852 if (r == typecheck_FAIL)
856 /* If there have not been any JSRs we just have a single typevector merge */
857 if (!state->jsrencountered) {
858 r = typevector_merge(state->m,destloc,yloc,state->numlocals);
859 if (r == typecheck_FAIL)
864 for (yvec=yloc; yvec; yvec=yvec->alt) {
867 /* Check if the typestates (deststack,destloc) will be
868 * separable when (ystack,yvec) is added. */
870 if (!typestack_separable_with(deststack,ystack,ky)
871 && !typevectorset_separable_with(destloc,yvec,state->numlocals))
873 /* No, the resulting set won't be separable, thus we
874 * may merge all states in (deststack,destloc) and
877 typestack_collapse(deststack);
878 if (typevectorset_collapse(state->m,destloc,state->numlocals) == typecheck_FAIL)
879 return typecheck_FAIL;
880 if (typevector_merge(state->m,destloc,yvec,state->numlocals) == typecheck_FAIL)
881 return typecheck_FAIL;
884 /* Yes, the resulting set will be separable. Thus we check
885 * if we may merge (ystack,yvec) with a single state in
886 * (deststack,destloc). */
888 for (dvec=destloc,kd=0; dvec; dvec=dvec->alt, kd++) {
889 if (!typestack_separable_from(ystack,ky,deststack,kd)
890 && !typevector_separable_from(yvec,dvec,state->numlocals))
892 /* The typestate (ystack,yvec) is not separable from
893 * (deststack,dvec) by any returnAddress. Thus we may
894 * merge the states. */
896 r = typevector_merge(state->m,dvec,yvec,state->numlocals);
897 if (r == typecheck_FAIL)
905 /* The typestate (ystack,yvec) is separable from all typestates
906 * (deststack,destloc). Thus we must add this state to the
909 typestack_add(deststack,ystack,ky);
910 typevectorset_add(destloc,yvec,state->numlocals);
919 LOGSTR("dstack: "); DOLOG(typestack_print(typecheck_logfile,deststack)); LOGNL;
920 LOGSTR("dloc : "); DOLOG(typevectorset_print(typecheck_logfile,destloc,state->numlocals)); LOGNL;
926 /* typestate_reach *************************************************************
928 Reach a destination block and propagate stack and local variable types
931 state............current state of the verifier
932 destblock........destination basic block
933 ystack...........stack to propagate
934 yloc.............set of local variable typevectors to propagate
937 state->repeat....set to true if the verifier must iterate again
938 over the basic blocks
941 true.............success
942 false............an exception has been thrown
944 *******************************************************************************/
947 typestate_reach(verifier_state *state,
948 basicblock *destblock,
949 stackptr ystack,typevector *yloc)
953 bool changed = false;
956 LOG1("reaching block L%03d",destblock->debug_nr);
957 TYPECHECK_COUNT(stat_reached);
959 destidx = destblock - state->cd->method->basicblocks;
960 destloc = MGET_TYPEVECTOR(state->localbuf,destidx,state->numlocals);
962 /* When branching backwards we have to check for uninitialized objects */
964 if (destblock <= state->bptr) {
969 TYPECHECK_COUNT(stat_backwards);
971 for (sp = ystack; sp; sp=sp->prev)
972 if (sp->type == TYPE_ADR &&
973 TYPEINFO_IS_NEWOBJECT(sp->typeinfo)) {
974 /*printf("current: %d, dest: %d\n", state->bptr->debug_nr, destblock->debug_nr);*/
975 exceptions_throw_verifyerror(state->m,"Branching backwards with uninitialized object on stack");
979 for (i=0; i<state->numlocals; ++i)
980 if (yloc->td[i].type == TYPE_ADR &&
981 TYPEINFO_IS_NEWOBJECT(yloc->td[i].info)) {
982 exceptions_throw_verifyerror(state->m,"Branching backwards with uninitialized object in local variable");
988 if (destblock->flags == BBTYPECHECK_UNDEF) {
989 /* The destblock has never been reached before */
991 TYPECHECK_COUNT(stat_copied);
992 LOG1("block (index %04d) reached first time",destidx);
994 if (!typestack_copy(state,destblock->instack,ystack,yloc))
996 typevectorset_copy_inplace(yloc,destloc,state->numlocals);
1000 /* The destblock has already been reached before */
1002 TYPECHECK_COUNT(stat_merged);
1003 LOG1("block (index %04d) reached before",destidx);
1005 r = typestate_merge(state,destblock->instack,destloc,ystack,yloc);
1006 if (r == typecheck_FAIL)
1009 TYPECHECK_COUNTIF(changed,stat_merging_changed);
1014 destblock->flags = BBTYPECHECK_REACHED;
1015 if (destblock <= state->bptr) {
1017 state->repeat = true;
1023 /* typestate_ret ***************************************************************
1025 Reach the destinations of a RET instruction.
1028 state............current state of the verifier
1029 retindex.........index of local variable containing the returnAddress
1032 state->repeat....set to true if the verifier must iterate again
1033 over the basic blocks
1036 true.............success
1037 false............an exception has been thrown
1039 *******************************************************************************/
1042 typestate_ret(verifier_state *state,int retindex)
1045 typevector *selected;
1046 basicblock *destblock;
1048 for (yvec=state->localset; yvec; ) {
1049 if (!TYPEDESC_IS_RETURNADDRESS(yvec->td[retindex])) {
1050 exceptions_throw_verifyerror(state->m,"Illegal instruction: RET on non-returnAddress");
1054 destblock = (basicblock*) TYPEINFO_RETURNADDRESS(yvec->td[retindex].info);
1056 selected = typevectorset_select(&yvec,retindex,destblock);
1058 if (!typestate_reach(state,destblock,state->curstack,selected))
1064 /* typestate_save_instack ******************************************************
1066 Save the input stack of the current basic block in the "savedstackbuf"
1067 of the verifier state.
1069 This function must be called before an instruction modifies a stack slot
1070 that happens to be part of the instack of the current block. In such
1071 cases the instack of the block must be saved, and restored at the end
1072 of the analysis of this basic block, so that the instack again reflects
1073 the *input* to this basic block (and does not randomly contain types
1074 that appear within the block).
1077 state............current state of the verifier
1079 *******************************************************************************/
1082 typestate_save_instack(verifier_state *state)
1088 LOG("saving input stack types");
1089 if (!state->savedstackbuf) {
1090 LOG("allocating savedstack buffer");
1091 state->savedstackbuf = DMNEW(stackelement, state->cd->maxstack);
1092 state->savedstackbuf->prev = NULL;
1093 for (i = 1; i < state->cd->maxstack; ++i)
1094 state->savedstackbuf[i].prev = state->savedstackbuf+(i-1);
1096 sp = state->savedstack = state->bptr->instack;
1097 dest = state->bptr->instack = state->savedstackbuf + (state->bptr->indepth-1);
1099 for(; sp; sp=sp->prev, dest=dest->prev) {
1100 dest->type = sp->type;
1101 TYPEINFO_COPY(sp->typeinfo,dest->typeinfo);
1105 /* typestate_restore_instack ***************************************************
1107 Restore the input stack of the current basic block that has been previously
1108 saved by `typestate_save_instack`.
1111 state............current state of the verifier
1113 *******************************************************************************/
1116 typestate_restore_instack(verifier_state *state)
1121 TYPECHECK_COUNT(stat_savedstack);
1122 LOG("restoring saved instack");
1124 sp = state->bptr->instack;
1125 dest = state->savedstack;
1126 for(; sp; sp=sp->prev, dest=dest->prev) {
1127 dest->type = sp->type;
1128 TYPEINFO_COPY(sp->typeinfo,dest->typeinfo);
1131 state->bptr->instack = state->savedstack;
1132 state->savedstack = NULL;
1135 /****************************************************************************/
1137 /****************************************************************************/
1139 #define COPYTYPE(source,dest) \
1140 {if ((source)->type == TYPE_ADR) \
1141 TYPEINFO_COPY((source)->typeinfo,(dest)->typeinfo);}
1143 #define ISBUILTIN(v) (bte->fp == (functionptr) (v))
1145 /* verify_invocation ***********************************************************
1147 Verify an ICMD_INVOKE* instruction.
1150 state............the current state of the verifier
1153 true.............successful verification,
1154 false............an exception has been thrown.
1156 *******************************************************************************/
1159 verify_invocation(verifier_state *state)
1161 unresolved_method *um; /* struct describing the called method */
1162 constant_FMIref *mref; /* reference to the called method */
1163 methodinfo *mi; /* resolved method (if any) */
1164 methoddesc *md; /* descriptor of the called method */
1165 utf *mname; /* method name */
1166 utf *mclassname; /* name of the method's class */
1167 bool specialmethod; /* true if a <...> method is called */
1168 int opcode; /* invocation opcode */
1169 bool callinginit; /* true if <init> is called */
1171 classref_or_classinfo initclass;
1173 stackelement *stack; /* temporary stack pointer */
1174 stackelement *dst; /* result stack of the invocation */
1175 int i; /* counter */
1176 u1 rtype; /* return type of called method */
1177 resolve_result_t result;
1179 if (INSTRUCTION_IS_UNRESOLVED(state->iptr)) {
1180 /* unresolved method */
1181 um = INSTRUCTION_UNRESOLVED_METHOD(state->iptr);
1182 mref = um->methodref;
1186 mref = INSTRUCTION_RESOLVED_FMIREF(state->iptr);
1189 md = mref->parseddesc.md;
1192 if (IS_FMIREF_RESOLVED(mref)) {
1193 mi = mref->p.method;
1194 mclassname = mi->class->name;
1198 mclassname = mref->p.classref->name;
1201 specialmethod = (mname->text[0] == '<');
1202 opcode = state->iptr[0].opc;
1203 dst = state->iptr->dst;
1205 /* prevent compiler warnings */
1209 /* check whether we are calling <init> */
1211 callinginit = (opcode == ICMD_INVOKESPECIAL && mname == utf_init);
1212 if (specialmethod && !callinginit)
1213 TYPECHECK_VERIFYERROR_bool("Invalid invocation of special method");
1215 /* allocate parameters if necessary */
1218 if (!descriptor_params_from_paramtypes(md,
1219 (opcode == ICMD_INVOKESTATIC) ? ACC_STATIC : ACC_NONE))
1222 /* check parameter types */
1224 stack = state->curstack;
1225 i = md->paramcount; /* number of parameters including 'this'*/
1228 td = md->paramtypes + i;
1229 if (stack->type != td->type)
1230 TYPECHECK_VERIFYERROR_bool("Parameter type mismatch in method invocation");
1231 if (stack->type == TYPE_ADR) {
1232 LOGINFO(&(stack->typeinfo));
1233 if (i==0 && callinginit)
1235 /* first argument to <init> method */
1236 if (!TYPEINFO_IS_NEWOBJECT(stack->typeinfo))
1237 TYPECHECK_VERIFYERROR_bool("Calling <init> on initialized object");
1239 /* get the address of the NEW instruction */
1240 LOGINFO(&(stack->typeinfo));
1241 ins = (instruction*)TYPEINFO_NEWOBJECT_INSTRUCTION(stack->typeinfo);
1243 initclass = ICMD_ACONST_CLASSREF_OR_CLASSINFO(ins-1);
1245 initclass.cls = state->m->class;
1246 LOGSTR("class: "); LOGNAME(initclass); LOGNL;
1250 /* non-adress argument. if this is the first argument and we are */
1251 /* invoking an instance method, this is an error. */
1252 if (i==0 && opcode != ICMD_INVOKESTATIC) {
1253 TYPECHECK_VERIFYERROR_bool("Parameter type mismatch for 'this' argument");
1259 stack = stack->prev;
1262 LOG("checking return type");
1263 rtype = md->returntype.type;
1264 if (rtype != TYPE_VOID) {
1265 if (rtype != dst->type)
1266 TYPECHECK_VERIFYERROR_bool("Return type mismatch in method invocation");
1267 if (!typeinfo_init_from_typedesc(&(md->returntype),NULL,&(dst->typeinfo)))
1272 LOG("replacing uninitialized object");
1273 /* replace uninitialized object type on stack */
1276 if (stack->type == TYPE_ADR
1277 && TYPEINFO_IS_NEWOBJECT(stack->typeinfo)
1278 && TYPEINFO_NEWOBJECT_INSTRUCTION(stack->typeinfo) == ins)
1280 LOG("replacing uninitialized type on stack");
1282 /* If this stackslot is in the instack of
1283 * this basic block we must save the type(s)
1284 * we are going to replace.
1286 if (stack <= state->bptr->instack && !state->savedstack)
1287 typestate_save_instack(state);
1289 if (!typeinfo_init_class(&(stack->typeinfo),initclass))
1292 stack = stack->prev;
1294 /* replace uninitialized object type in locals */
1295 if (!typevectorset_init_object(state->localset,ins,initclass,state->numlocals))
1298 /* initializing the 'this' reference? */
1301 TYPECHECK_ASSERT(state->initmethod);
1302 /* { we are initializing the 'this' reference } */
1303 /* must be <init> of current class or direct superclass */
1304 /* the current class is linked, so must be its superclass. thus we can be */
1305 /* sure that resolving will be trivial. */
1310 if (!resolve_classref(state->m,mref->p.classref,resolveLazy,false,true,&cls))
1311 return false; /* exception */
1314 /* if lazy resolving did not succeed, it's not one of the allowed classes */
1315 /* otherwise we check it directly */
1316 if (cls == NULL || (cls != state->m->class && cls != state->m->class->super.cls)) {
1317 TYPECHECK_VERIFYERROR_bool("<init> calling <init> of the wrong class");
1320 /* set our marker variable to type int */
1321 LOG("setting <init> marker");
1322 typevectorset_store(state->localset,state->numlocals-1,TYPE_INT,NULL);
1325 /* { we are initializing an instance created with NEW } */
1326 if ((IS_CLASSREF(initclass) ? initclass.ref->name : initclass.cls->name) != mclassname) {
1327 TYPECHECK_VERIFYERROR_bool("wrong <init> called for uninitialized reference");
1332 /* try to resolve the method lazily */
1334 result = resolve_method_lazy(state->iptr,state->curstack,state->m);
1335 if (result == resolveFailed)
1338 if (result != resolveSucceeded) {
1340 um = create_unresolved_method(state->m->class,
1341 state->m, state->iptr);
1347 /* record subtype constraints for parameters */
1349 if (!constrain_unresolved_method(um,state->m->class,state->m,state->iptr,state->curstack))
1350 return false; /* XXX maybe wrap exception */
1352 /* store the unresolved_method pointer */
1354 /* XXX this will be changed */
1355 state->iptr->val.a = um;
1356 state->iptr->target = (void*) 0x01; /* XXX used temporarily as flag */
1362 /* verify_generic_builtin ******************************************************
1364 Verify the call of a generic builtin method.
1367 state............the current state of the verifier
1370 true.............successful verification,
1371 false............an exception has been thrown.
1373 *******************************************************************************/
1376 verify_generic_builtin(verifier_state *state)
1378 builtintable_entry *bte;
1384 TYPECHECK_COUNT(stat_ins_builtin_gen);
1386 bte = (builtintable_entry *) state->iptr[0].val.a;
1390 /* check the types of the arguments on the stack */
1392 sp = state->curstack;
1393 for (i--; i >= 0; i--) {
1394 if (sp->type != md->paramtypes[i].type) {
1395 TYPECHECK_VERIFYERROR_bool("parameter type mismatch for builtin method");
1398 #ifdef TYPECHECK_DEBUG
1399 /* generic builtins may only take primitive types and java.lang.Object references */
1400 if (sp->type == TYPE_ADR && md->paramtypes[i].classref->name != utf_java_lang_Object) {
1401 *exceptionptr = new_internalerror("generic builtin method with non-generic reference parameter");
1409 /* check the return type */
1411 rtype = md->returntype.type;
1412 if (rtype != TYPE_VOID) {
1415 dst = state->iptr->dst;
1416 if (rtype != dst->type)
1417 TYPECHECK_VERIFYERROR_bool("Return type mismatch in generic builtin invocation");
1418 if (!typeinfo_init_from_typedesc(&(md->returntype),NULL,&(dst->typeinfo)))
1425 /* verify_builtin **************************************************************
1427 Verify the call of a builtin method.
1430 state............the current state of the verifier
1433 true.............successful verification,
1434 false............an exception has been thrown.
1436 *******************************************************************************/
1439 verify_builtin(verifier_state *state)
1441 builtintable_entry *bte;
1442 classref_or_classinfo cls;
1443 stackptr dst; /* output stack of current instruction */
1445 bte = (builtintable_entry *) state->iptr[0].val.a;
1446 dst = state->iptr->dst;
1448 /* XXX this is an ugly if-chain but twisti did not want a function */
1449 /* pointer in builtintable_entry for this, so here you go.. ;) */
1451 if (ISBUILTIN(BUILTIN_new)) {
1452 if (state->iptr[-1].opc != ICMD_ACONST)
1453 TYPECHECK_VERIFYERROR_bool("illegal instruction: builtin_new without class");
1454 cls = ICMD_ACONST_CLASSREF_OR_CLASSINFO(state->iptr - 1);
1455 TYPEINFO_INIT_NEWOBJECT(dst->typeinfo,state->iptr);
1457 else if (ISBUILTIN(BUILTIN_newarray_boolean)) {
1458 TYPECHECK_INT(state->curstack);
1459 TYPEINFO_INIT_PRIMITIVE_ARRAY(dst->typeinfo,ARRAYTYPE_BOOLEAN);
1461 else if (ISBUILTIN(BUILTIN_newarray_char)) {
1462 TYPECHECK_INT(state->curstack);
1463 TYPEINFO_INIT_PRIMITIVE_ARRAY(dst->typeinfo,ARRAYTYPE_CHAR);
1465 else if (ISBUILTIN(BUILTIN_newarray_float)) {
1466 TYPECHECK_INT(state->curstack);
1467 TYPEINFO_INIT_PRIMITIVE_ARRAY(dst->typeinfo,ARRAYTYPE_FLOAT);
1469 else if (ISBUILTIN(BUILTIN_newarray_double)) {
1470 TYPECHECK_INT(state->curstack);
1471 TYPEINFO_INIT_PRIMITIVE_ARRAY(dst->typeinfo,ARRAYTYPE_DOUBLE);
1473 else if (ISBUILTIN(BUILTIN_newarray_byte)) {
1474 TYPECHECK_INT(state->curstack);
1475 TYPEINFO_INIT_PRIMITIVE_ARRAY(dst->typeinfo,ARRAYTYPE_BYTE);
1477 else if (ISBUILTIN(BUILTIN_newarray_short)) {
1478 TYPECHECK_INT(state->curstack);
1479 TYPEINFO_INIT_PRIMITIVE_ARRAY(dst->typeinfo,ARRAYTYPE_SHORT);
1481 else if (ISBUILTIN(BUILTIN_newarray_int)) {
1482 TYPECHECK_INT(state->curstack);
1483 TYPEINFO_INIT_PRIMITIVE_ARRAY(dst->typeinfo,ARRAYTYPE_INT);
1485 else if (ISBUILTIN(BUILTIN_newarray_long)) {
1486 TYPECHECK_INT(state->curstack);
1487 TYPEINFO_INIT_PRIMITIVE_ARRAY(dst->typeinfo,ARRAYTYPE_LONG);
1489 else if (ISBUILTIN(BUILTIN_newarray))
1491 TYPECHECK_INT(state->curstack->prev);
1492 if (state->iptr[-1].opc != ICMD_ACONST)
1493 TYPECHECK_VERIFYERROR_bool("illegal instruction: builtin_newarray without class");
1494 /* XXX check that it is an array class(ref) */
1495 typeinfo_init_class(&(dst->typeinfo),ICMD_ACONST_CLASSREF_OR_CLASSINFO(state->iptr - 1));
1497 else if (ISBUILTIN(BUILTIN_arrayinstanceof))
1499 TYPECHECK_ADR(state->curstack->prev);
1500 if (state->iptr[-1].opc != ICMD_ACONST)
1501 TYPECHECK_VERIFYERROR_bool("illegal instruction: builtin_arrayinstanceof without class");
1502 /* XXX check that it is an array class(ref) */
1505 return verify_generic_builtin(state);
1510 /* verify_multianewarray *******************************************************
1512 Verify a MULTIANEWARRAY instruction.
1515 state............the current state of the verifier
1518 true.............successful verification,
1519 false............an exception has been thrown.
1521 *******************************************************************************/
1524 verify_multianewarray(verifier_state *state)
1527 classinfo *arrayclass;
1528 arraydescriptor *desc;
1531 /* check the array lengths on the stack */
1532 i = state->iptr[0].op1;
1534 TYPECHECK_VERIFYERROR_bool("Illegal dimension argument");
1536 sp = state->curstack;
1539 TYPECHECK_VERIFYERROR_bool("Unable to pop operand off an empty stack");
1544 /* check array descriptor */
1545 if (state->iptr[0].val.a != NULL) {
1546 /* the array class reference has already been resolved */
1547 arrayclass = (classinfo *) state->iptr[0].val.a;
1549 TYPECHECK_VERIFYERROR_bool("MULTIANEWARRAY with unlinked class");
1550 if ((desc = arrayclass->vftbl->arraydesc) == NULL)
1551 TYPECHECK_VERIFYERROR_bool("MULTIANEWARRAY with non-array class");
1552 if (desc->dimension < state->iptr[0].op1)
1553 TYPECHECK_VERIFYERROR_bool("MULTIANEWARRAY dimension to high");
1555 /* set the array type of the result */
1556 typeinfo_init_classinfo(&(state->iptr->dst->typeinfo), arrayclass);
1560 constant_classref *cr;
1562 /* the array class reference is still unresolved */
1563 /* check that the reference indicates an array class of correct dimension */
1564 cr = (constant_classref *) state->iptr[0].target; /* XXX new instruction format */
1569 /* { the dimension of the array class == i } */
1571 TYPECHECK_VERIFYERROR_bool("MULTIANEWARRAY with non-array class");
1572 if (i < state->iptr[0].op1)
1573 TYPECHECK_VERIFYERROR_bool("MULTIANEWARRAY dimension to high");
1575 /* set the array type of the result */
1576 if (!typeinfo_init_class(&(state->iptr->dst->typeinfo),CLASSREF_OR_CLASSINFO(state->iptr[0].target))) /* XXX new instruction format */
1584 /* verify_basic_block **********************************************************
1586 Perform bytecode verification of a basic block.
1589 state............the current state of the verifier
1592 true.............successful verification,
1593 false............an exception has been thrown.
1595 *******************************************************************************/
1598 verify_basic_block(verifier_state *state)
1600 int opcode; /* current opcode */
1601 int len; /* for counting instructions, etc. */
1602 bool superblockend; /* true if no fallthrough to next block */
1603 basicblock *tbptr; /* temporary for target block */
1604 stackptr dst; /* output stack of current instruction */
1605 basicblock **tptr; /* pointer into target list of switch instr. */
1606 classinfo *cls; /* temporary */
1607 bool maythrow; /* true if this instruction may throw */
1608 unresolved_field *uf; /* for field accesses */
1609 constant_FMIref *fieldref; /* for field accesses */
1613 resolve_result_t result;
1615 LOGSTR1("\n---- BLOCK %04d ------------------------------------------------\n",state->bptr->debug_nr);
1618 superblockend = false;
1619 state->bptr->flags = BBFINISHED;
1620 b_index = state->bptr - state->m->basicblocks;
1622 /* init stack at the start of this block */
1623 state->curstack = state->bptr->instack;
1625 /* prevent compiler warnings */
1629 /* determine the active exception handlers for this block */
1630 /* XXX could use a faster algorithm with sorted lists or */
1633 for (i = 0; i < state->cd->exceptiontablelength; ++i) {
1634 if ((state->cd->exceptiontable[i].start <= state->bptr) && (state->cd->exceptiontable[i].end > state->bptr)) {
1635 LOG1("active handler L%03d", state->cd->exceptiontable[i].handler->debug_nr);
1636 state->handlers[len++] = state->cd->exceptiontable + i;
1639 state->handlers[len] = NULL;
1641 /* init variable types at the start of this block */
1642 typevectorset_copy_inplace(MGET_TYPEVECTOR(state->localbuf,b_index,state->numlocals),
1643 state->localset,state->numlocals);
1645 if (state->handlers[0])
1646 for (i=0; i<state->numlocals; ++i)
1647 if (state->localset->td[i].type == TYPE_ADR
1648 && TYPEINFO_IS_NEWOBJECT(state->localset->td[i].info)) {
1649 /* XXX we do not check this for the uninitialized 'this' instance in */
1650 /* <init> methods. Otherwise there are problems with try blocks in */
1651 /* <init>. The spec seems to indicate that we should perform the test*/
1652 /* in all cases, but this fails with real code. */
1653 /* Example: org/eclipse/ui/internal/PerspectiveBarNewContributionItem*/
1654 /* of eclipse 3.0.2 */
1655 if (TYPEINFO_NEWOBJECT_INSTRUCTION(state->localset->td[i].info) != NULL) {
1656 /*show_icmd_method(state->m, state->cd, state->rd);*/
1657 printf("Uninitialized variable: %d, block: %d\n", i, state->bptr->nr);
1658 TYPECHECK_VERIFYERROR_bool("Uninitialized object in local variable inside try block");
1661 DOLOG(typestate_print(typecheck_logfile,state->curstack,state->localset,state->numlocals));
1664 /* loop over the instructions */
1665 len = state->bptr->icount;
1666 state->iptr = state->bptr->iinstr;
1667 while (--len >= 0) {
1668 TYPECHECK_COUNT(stat_ins);
1670 DOLOG(typestate_print(typecheck_logfile,state->curstack,state->localset,state->numlocals));
1673 DOLOG(show_icmd(state->iptr,false)); LOGNL; LOGFLUSH;
1675 opcode = state->iptr->opc;
1676 dst = state->iptr->dst;
1681 /****************************************/
1682 /* STACK MANIPULATIONS */
1684 /* We just need to copy the typeinfo */
1685 /* for slots containing addresses. */
1687 /* CAUTION: We assume that the destination stack
1688 * slots were continuously allocated in
1689 * memory! (The current implementation in
1694 TYPECHECK_COUNT(stat_ins_stack);
1695 COPYTYPE(state->curstack,dst);
1699 TYPECHECK_COUNT(stat_ins_stack);
1700 COPYTYPE(state->curstack,dst);
1701 COPYTYPE(state->curstack,dst-2);
1702 COPYTYPE(state->curstack->prev,dst-1);
1706 TYPECHECK_COUNT(stat_ins_stack);
1707 COPYTYPE(state->curstack,dst);
1708 COPYTYPE(state->curstack,dst-3);
1709 COPYTYPE(state->curstack->prev,dst-1);
1710 COPYTYPE(state->curstack->prev->prev,dst-2);
1714 TYPECHECK_COUNT(stat_ins_stack);
1715 COPYTYPE(state->curstack,dst);
1716 COPYTYPE(state->curstack->prev,dst-1);
1720 TYPECHECK_COUNT(stat_ins_stack);
1721 COPYTYPE(state->curstack,dst);
1722 COPYTYPE(state->curstack->prev,dst-1);
1723 COPYTYPE(state->curstack,dst-3);
1724 COPYTYPE(state->curstack->prev,dst-4);
1725 COPYTYPE(state->curstack->prev->prev,dst-2);
1729 TYPECHECK_COUNT(stat_ins_stack);
1730 COPYTYPE(state->curstack,dst);
1731 COPYTYPE(state->curstack->prev,dst-1);
1732 COPYTYPE(state->curstack,dst-4);
1733 COPYTYPE(state->curstack->prev,dst-5);
1734 COPYTYPE(state->curstack->prev->prev,dst-2);
1735 COPYTYPE(state->curstack->prev->prev->prev,dst-3);
1739 TYPECHECK_COUNT(stat_ins_stack);
1740 COPYTYPE(state->curstack,dst-1);
1741 COPYTYPE(state->curstack->prev,dst);
1744 /****************************************/
1745 /* PRIMITIVE VARIABLE ACCESS */
1747 case ICMD_ILOAD: if (!typevectorset_checktype(state->localset,state->iptr->op1,TYPE_INT))
1748 TYPECHECK_VERIFYERROR_bool("Local variable type mismatch");
1750 case ICMD_IINC: if (!typevectorset_checktype(state->localset,state->iptr->op1,TYPE_INT))
1751 TYPECHECK_VERIFYERROR_bool("Local variable type mismatch");
1753 case ICMD_FLOAD: if (!typevectorset_checktype(state->localset,state->iptr->op1,TYPE_FLT))
1754 TYPECHECK_VERIFYERROR_bool("Local variable type mismatch");
1756 case ICMD_LLOAD: if (!typevectorset_checktype(state->localset,state->iptr->op1,TYPE_LNG))
1757 TYPECHECK_VERIFYERROR_bool("Local variable type mismatch");
1759 case ICMD_DLOAD: if (!typevectorset_checktype(state->localset,state->iptr->op1,TYPE_DBL))
1760 TYPECHECK_VERIFYERROR_bool("Local variable type mismatch");
1763 case ICMD_ISTORE: typevectorset_store(state->localset,state->iptr->op1,TYPE_INT,NULL); break;
1764 case ICMD_FSTORE: typevectorset_store(state->localset,state->iptr->op1,TYPE_FLT,NULL); break;
1765 case ICMD_LSTORE: typevectorset_store_twoword(state->localset,state->iptr->op1,TYPE_LNG); break;
1766 case ICMD_DSTORE: typevectorset_store_twoword(state->localset,state->iptr->op1,TYPE_DBL); break;
1768 /****************************************/
1769 /* LOADING ADDRESS FROM VARIABLE */
1772 TYPECHECK_COUNT(stat_ins_aload);
1774 /* loading a returnAddress is not allowed */
1775 if (state->jsrencountered) {
1776 if (!typevectorset_checkreference(state->localset,state->iptr->op1)) {
1777 TYPECHECK_VERIFYERROR_bool("illegal instruction: ALOAD loading non-reference");
1779 if (typevectorset_copymergedtype(state->m,state->localset,state->iptr->op1,&(dst->typeinfo)) == -1)
1783 if (!TYPEDESC_IS_REFERENCE(state->localset->td[state->iptr->op1])) {
1784 TYPECHECK_VERIFYERROR_bool("illegal instruction: ALOAD loading non-reference");
1786 TYPEINFO_COPY(state->localset->td[state->iptr->op1].info,dst->typeinfo);
1790 /****************************************/
1791 /* STORING ADDRESS TO VARIABLE */
1794 if (state->handlers[0] && TYPEINFO_IS_NEWOBJECT(state->curstack->typeinfo)) {
1795 TYPECHECK_VERIFYERROR_bool("Storing uninitialized object in local variable inside try block");
1798 if (TYPESTACK_IS_RETURNADDRESS(state->curstack)) {
1799 typevectorset_store_retaddr(state->localset,state->iptr->op1,&(state->curstack->typeinfo));
1802 typevectorset_store(state->localset,state->iptr->op1,TYPE_ADR,
1803 &(state->curstack->typeinfo));
1807 /****************************************/
1808 /* LOADING ADDRESS FROM ARRAY */
1811 if (!TYPEINFO_MAYBE_ARRAY_OF_REFS(state->curstack->prev->typeinfo))
1812 TYPECHECK_VERIFYERROR_bool("illegal instruction: AALOAD on non-reference array");
1814 if (!typeinfo_init_component(&state->curstack->prev->typeinfo,&dst->typeinfo))
1819 /****************************************/
1822 case ICMD_PUTFIELDCONST:
1823 case ICMD_PUTSTATICCONST:
1824 TYPECHECK_COUNT(stat_ins_field);
1826 if (INSTRUCTION_IS_UNRESOLVED(state->iptr + 1)) {
1827 uf = INSTRUCTION_UNRESOLVED_FIELD(state->iptr + 1);
1828 fieldref = uf->fieldref;
1832 fieldref = INSTRUCTION_RESOLVED_FMIREF(state->iptr + 1);
1835 goto fieldaccess_tail;
1838 case ICMD_PUTSTATIC:
1839 TYPECHECK_COUNT(stat_ins_field);
1841 if (INSTRUCTION_IS_UNRESOLVED(state->iptr)) {
1842 uf = INSTRUCTION_UNRESOLVED_FIELD(state->iptr);
1843 fieldref = uf->fieldref;
1847 fieldref = INSTRUCTION_RESOLVED_FMIREF(state->iptr);
1850 goto fieldaccess_tail;
1853 case ICMD_GETSTATIC:
1854 TYPECHECK_COUNT(stat_ins_field);
1856 if (INSTRUCTION_IS_UNRESOLVED(state->iptr)) {
1857 uf = INSTRUCTION_UNRESOLVED_FIELD(state->iptr);
1858 fieldref = uf->fieldref;
1862 fieldref = INSTRUCTION_RESOLVED_FMIREF(state->iptr);
1865 /* the result is pushed on the stack */
1866 if (dst->type == TYPE_ADR) {
1867 if (!typeinfo_init_from_typedesc(fieldref->parseddesc.fd,NULL,&(dst->typeinfo)))
1872 /* try to resolve the field reference lazily */
1873 result = resolve_field_lazy(state->iptr, state->curstack, state->m);
1874 if (result == resolveFailed)
1877 if (result != resolveSucceeded) {
1879 uf = create_unresolved_field(state->m->class, state->m, state->iptr);
1883 if (opcode == ICMD_PUTSTATICCONST || opcode == ICMD_PUTFIELDCONST) {
1884 state->iptr[1].val.a = uf;
1885 state->iptr[1].target = (void*) 0x01; /* XXX target used temporarily as flag */
1888 state->iptr[0].val.a = uf;
1889 state->iptr[0].target = (void*) 0x01; /* XXX target used temporarily as flag */
1893 /* record the subtype constraints for this field access */
1894 if (!constrain_unresolved_field(uf,state->m->class,state->m,state->iptr,state->curstack))
1895 return false; /* XXX maybe wrap exception? */
1897 TYPECHECK_COUNTIF(INSTRUCTION_IS_UNRESOLVED(state->iptr),stat_ins_field_unresolved);
1898 TYPECHECK_COUNTIF(INSTRUCTION_IS_RESOLVED(state->iptr) && !INSTRUCTION_RESOLVED_FIELDINFO(state->iptr)->class->initialized,stat_ins_field_uninitialized);
1904 /****************************************/
1905 /* PRIMITIVE ARRAY ACCESS */
1907 case ICMD_ARRAYLENGTH:
1908 if (!TYPEINFO_MAYBE_ARRAY(state->curstack->typeinfo)
1909 && state->curstack->typeinfo.typeclass.cls != pseudo_class_Arraystub)
1910 TYPECHECK_VERIFYERROR_bool("illegal instruction: ARRAYLENGTH on non-array");
1915 if (!TYPEINFO_MAYBE_PRIMITIVE_ARRAY(state->curstack->prev->typeinfo,ARRAYTYPE_BOOLEAN)
1916 && !TYPEINFO_MAYBE_PRIMITIVE_ARRAY(state->curstack->prev->typeinfo,ARRAYTYPE_BYTE))
1917 TYPECHECK_VERIFYERROR_bool("Array type mismatch");
1921 if (!TYPEINFO_MAYBE_PRIMITIVE_ARRAY(state->curstack->prev->typeinfo,ARRAYTYPE_CHAR))
1922 TYPECHECK_VERIFYERROR_bool("Array type mismatch");
1926 if (!TYPEINFO_MAYBE_PRIMITIVE_ARRAY(state->curstack->prev->typeinfo,ARRAYTYPE_DOUBLE))
1927 TYPECHECK_VERIFYERROR_bool("Array type mismatch");
1931 if (!TYPEINFO_MAYBE_PRIMITIVE_ARRAY(state->curstack->prev->typeinfo,ARRAYTYPE_FLOAT))
1932 TYPECHECK_VERIFYERROR_bool("Array type mismatch");
1936 if (!TYPEINFO_MAYBE_PRIMITIVE_ARRAY(state->curstack->prev->typeinfo,ARRAYTYPE_INT))
1937 TYPECHECK_VERIFYERROR_bool("Array type mismatch");
1941 if (!TYPEINFO_MAYBE_PRIMITIVE_ARRAY(state->curstack->prev->typeinfo,ARRAYTYPE_SHORT))
1942 TYPECHECK_VERIFYERROR_bool("Array type mismatch");
1946 if (!TYPEINFO_MAYBE_PRIMITIVE_ARRAY(state->curstack->prev->typeinfo,ARRAYTYPE_LONG))
1947 TYPECHECK_VERIFYERROR_bool("Array type mismatch");
1952 if (!TYPEINFO_MAYBE_PRIMITIVE_ARRAY(state->curstack->prev->prev->typeinfo,ARRAYTYPE_BOOLEAN)
1953 && !TYPEINFO_MAYBE_PRIMITIVE_ARRAY(state->curstack->prev->prev->typeinfo,ARRAYTYPE_BYTE))
1954 TYPECHECK_VERIFYERROR_bool("Array type mismatch");
1958 if (!TYPEINFO_MAYBE_PRIMITIVE_ARRAY(state->curstack->prev->prev->typeinfo,ARRAYTYPE_CHAR))
1959 TYPECHECK_VERIFYERROR_bool("Array type mismatch");
1963 if (!TYPEINFO_MAYBE_PRIMITIVE_ARRAY(state->curstack->prev->prev->typeinfo,ARRAYTYPE_DOUBLE))
1964 TYPECHECK_VERIFYERROR_bool("Array type mismatch");
1968 if (!TYPEINFO_MAYBE_PRIMITIVE_ARRAY(state->curstack->prev->prev->typeinfo,ARRAYTYPE_FLOAT))
1969 TYPECHECK_VERIFYERROR_bool("Array type mismatch");
1973 if (!TYPEINFO_MAYBE_PRIMITIVE_ARRAY(state->curstack->prev->prev->typeinfo,ARRAYTYPE_INT))
1974 TYPECHECK_VERIFYERROR_bool("Array type mismatch");
1978 if (!TYPEINFO_MAYBE_PRIMITIVE_ARRAY(state->curstack->prev->prev->typeinfo,ARRAYTYPE_SHORT))
1979 TYPECHECK_VERIFYERROR_bool("Array type mismatch");
1983 if (!TYPEINFO_MAYBE_PRIMITIVE_ARRAY(state->curstack->prev->prev->typeinfo,ARRAYTYPE_LONG))
1984 TYPECHECK_VERIFYERROR_bool("Array type mismatch");
1989 /* we just check the basic input types and that the */
1990 /* destination is an array of references. Assignability to */
1991 /* the actual array must be checked at runtime, each time the */
1992 /* instruction is performed. (See builtin_canstore.) */
1993 TYPECHECK_ADR(state->curstack);
1994 TYPECHECK_INT(state->curstack->prev);
1995 TYPECHECK_ADR(state->curstack->prev->prev);
1996 if (!TYPEINFO_MAYBE_ARRAY_OF_REFS(state->curstack->prev->prev->typeinfo))
1997 TYPECHECK_VERIFYERROR_bool("illegal instruction: AASTORE to non-reference array");
2001 case ICMD_IASTORECONST:
2002 if (!TYPEINFO_MAYBE_PRIMITIVE_ARRAY(state->curstack->prev->typeinfo, ARRAYTYPE_INT))
2003 TYPECHECK_VERIFYERROR_bool("Array type mismatch");
2007 case ICMD_LASTORECONST:
2008 if (!TYPEINFO_MAYBE_PRIMITIVE_ARRAY(state->curstack->prev->typeinfo, ARRAYTYPE_LONG))
2009 TYPECHECK_VERIFYERROR_bool("Array type mismatch");
2013 case ICMD_BASTORECONST:
2014 if (!TYPEINFO_MAYBE_PRIMITIVE_ARRAY(state->curstack->prev->typeinfo, ARRAYTYPE_BOOLEAN)
2015 && !TYPEINFO_MAYBE_PRIMITIVE_ARRAY(state->curstack->prev->typeinfo, ARRAYTYPE_BYTE))
2016 TYPECHECK_VERIFYERROR_bool("Array type mismatch");
2020 case ICMD_CASTORECONST:
2021 if (!TYPEINFO_MAYBE_PRIMITIVE_ARRAY(state->curstack->prev->typeinfo, ARRAYTYPE_CHAR))
2022 TYPECHECK_VERIFYERROR_bool("Array type mismatch");
2026 case ICMD_SASTORECONST:
2027 if (!TYPEINFO_MAYBE_PRIMITIVE_ARRAY(state->curstack->prev->typeinfo, ARRAYTYPE_SHORT))
2028 TYPECHECK_VERIFYERROR_bool("Array type mismatch");
2032 /****************************************/
2033 /* ADDRESS CONSTANTS */
2036 if (ICMD_ACONST_IS_CLASS(state->iptr)) {
2037 /* a java.lang.Class reference */
2038 TYPEINFO_INIT_JAVA_LANG_CLASS(dst->typeinfo,
2039 ICMD_ACONST_CLASSREF_OR_CLASSINFO(state->iptr));
2042 if (state->iptr->val.a == NULL)
2043 TYPEINFO_INIT_NULLTYPE(dst->typeinfo);
2045 /* string constant (or constant for builtin function) */
2046 typeinfo_init_classinfo(&(dst->typeinfo),class_java_lang_String);
2051 /****************************************/
2052 /* CHECKCAST AND INSTANCEOF */
2054 case ICMD_CHECKCAST:
2055 TYPECHECK_ADR(state->curstack);
2056 /* returnAddress is not allowed */
2057 if (!TYPEINFO_IS_REFERENCE(state->curstack->typeinfo))
2058 TYPECHECK_VERIFYERROR_bool("Illegal instruction: CHECKCAST on non-reference");
2060 cls = (classinfo *) state->iptr[0].val.a;
2062 typeinfo_init_classinfo(&(dst->typeinfo),cls);
2064 if (!typeinfo_init_class(&(dst->typeinfo),CLASSREF_OR_CLASSINFO(state->iptr[0].target))) /* XXX new instruction format */
2069 case ICMD_INSTANCEOF:
2070 TYPECHECK_ADR(state->curstack);
2071 /* returnAddress is not allowed */
2072 if (!TYPEINFO_IS_REFERENCE(state->curstack->typeinfo))
2073 TYPECHECK_VERIFYERROR_bool("Illegal instruction: INSTANCEOF on non-reference");
2076 /****************************************/
2077 /* BRANCH INSTRUCTIONS */
2079 case ICMD_INLINE_GOTO:
2080 COPYTYPE(state->curstack,dst);
2083 superblockend = true;
2086 case ICMD_IFNONNULL:
2093 case ICMD_IF_ICMPEQ:
2094 case ICMD_IF_ICMPNE:
2095 case ICMD_IF_ICMPLT:
2096 case ICMD_IF_ICMPGE:
2097 case ICMD_IF_ICMPGT:
2098 case ICMD_IF_ICMPLE:
2099 case ICMD_IF_ACMPEQ:
2100 case ICMD_IF_ACMPNE:
2109 case ICMD_IF_LCMPEQ:
2110 case ICMD_IF_LCMPNE:
2111 case ICMD_IF_LCMPLT:
2112 case ICMD_IF_LCMPGE:
2113 case ICMD_IF_LCMPGT:
2114 case ICMD_IF_LCMPLE:
2116 case ICMD_IF_FCMPEQ:
2117 case ICMD_IF_FCMPNE:
2119 case ICMD_IF_FCMPL_LT:
2120 case ICMD_IF_FCMPL_GE:
2121 case ICMD_IF_FCMPL_GT:
2122 case ICMD_IF_FCMPL_LE:
2124 case ICMD_IF_FCMPG_LT:
2125 case ICMD_IF_FCMPG_GE:
2126 case ICMD_IF_FCMPG_GT:
2127 case ICMD_IF_FCMPG_LE:
2129 case ICMD_IF_DCMPEQ:
2130 case ICMD_IF_DCMPNE:
2132 case ICMD_IF_DCMPL_LT:
2133 case ICMD_IF_DCMPL_GE:
2134 case ICMD_IF_DCMPL_GT:
2135 case ICMD_IF_DCMPL_LE:
2137 case ICMD_IF_DCMPG_LT:
2138 case ICMD_IF_DCMPG_GE:
2139 case ICMD_IF_DCMPG_GT:
2140 case ICMD_IF_DCMPG_LE:
2141 TYPECHECK_COUNT(stat_ins_branch);
2142 tbptr = (basicblock *) state->iptr->target;
2144 /* propagate stack and variables to the target block */
2145 if (!typestate_reach(state,tbptr,dst,state->localset))
2149 /****************************************/
2152 case ICMD_TABLESWITCH:
2153 TYPECHECK_COUNT(stat_ins_switch);
2155 s4 *s4ptr = state->iptr->val.a;
2156 s4ptr++; /* skip default */
2157 i = *s4ptr++; /* low */
2158 i = *s4ptr++ - i + 2; /* +1 for default target */
2160 goto switch_instruction_tail;
2162 case ICMD_LOOKUPSWITCH:
2163 TYPECHECK_COUNT(stat_ins_switch);
2165 s4 *s4ptr = state->iptr->val.a;
2166 s4ptr++; /* skip default */
2167 i = *s4ptr++ + 1; /* count +1 for default */
2169 switch_instruction_tail:
2170 tptr = (basicblock **)state->iptr->target;
2174 LOG2("target %d is block %04d",(tptr-(basicblock **)state->iptr->target)-1,tbptr->nr);
2175 if (!typestate_reach(state,tbptr,dst,state->localset))
2179 superblockend = true;
2182 /****************************************/
2183 /* ADDRESS RETURNS AND THROW */
2186 TYPECHECK_COUNT(stat_ins_athrow);
2187 r = typeinfo_is_assignable_to_class(&state->curstack->typeinfo,
2188 CLASSREF_OR_CLASSINFO(class_java_lang_Throwable));
2189 if (r == typecheck_FALSE)
2190 TYPECHECK_VERIFYERROR_bool("illegal instruction: ATHROW on non-Throwable");
2191 if (r == typecheck_FAIL)
2193 if (r == typecheck_MAYBE) {
2194 /* the check has to be postponed. we need a patcher */
2195 TYPECHECK_COUNT(stat_ins_athrow_unresolved);
2196 state->iptr->val.a = create_unresolved_class(
2198 /* XXX make this more efficient, use class_java_lang_Throwable
2200 class_get_classref(state->m->class,utf_java_lang_Throwable),
2201 &state->curstack->typeinfo);
2203 superblockend = true;
2208 TYPECHECK_COUNT(stat_ins_areturn);
2209 if (!TYPEINFO_IS_REFERENCE(state->curstack->typeinfo))
2210 TYPECHECK_VERIFYERROR_bool("illegal instruction: ARETURN on non-reference");
2212 if (state->returntype.type != TYPE_ADR
2213 || (r = typeinfo_is_assignable(&state->curstack->typeinfo,&(state->returntype.info)))
2215 TYPECHECK_VERIFYERROR_bool("Return type mismatch");
2216 if (r == typecheck_FAIL)
2218 if (r == typecheck_MAYBE) {
2219 /* the check has to be postponed, we need a patcher */
2220 TYPECHECK_COUNT(stat_ins_areturn_unresolved);
2221 state->iptr->val.a = create_unresolved_class(
2223 state->m->parseddesc->returntype.classref,
2224 &state->curstack->typeinfo);
2228 /****************************************/
2229 /* PRIMITIVE RETURNS */
2232 if (state->returntype.type != TYPE_INT) TYPECHECK_VERIFYERROR_bool("Return type mismatch");
2236 if (state->returntype.type != TYPE_LNG) TYPECHECK_VERIFYERROR_bool("Return type mismatch");
2240 if (state->returntype.type != TYPE_FLT) TYPECHECK_VERIFYERROR_bool("Return type mismatch");
2244 if (state->returntype.type != TYPE_DBL) TYPECHECK_VERIFYERROR_bool("Return type mismatch");
2248 if (state->returntype.type != TYPE_VOID) TYPECHECK_VERIFYERROR_bool("Return type mismatch");
2250 TYPECHECK_COUNT(stat_ins_primitive_return);
2252 if (state->initmethod && state->m->class != class_java_lang_Object) {
2253 /* Check if the 'this' instance has been initialized. */
2254 LOG("Checking <init> marker");
2255 if (!typevectorset_checktype(state->localset,state->numlocals-1,TYPE_INT))
2256 TYPECHECK_VERIFYERROR_bool("<init> method does not initialize 'this'");
2259 superblockend = true;
2263 /****************************************/
2264 /* SUBROUTINE INSTRUCTIONS */
2268 state->jsrencountered = true;
2270 /* This is a dirty hack. It is needed
2271 * because of the special handling of
2272 * ICMD_JSR in stack.c
2274 dst = (stackptr) state->iptr->val.a;
2276 tbptr = (basicblock *) state->iptr->target;
2277 if (state->bptr + 1 == (state->m->basicblocks + state->m->basicblockcount + 1))
2278 TYPECHECK_VERIFYERROR_bool("Illegal instruction: JSR at end of bytecode");
2279 typestack_put_retaddr(dst,state->bptr+1,state->localset);
2280 if (!typestate_reach(state,tbptr,dst,state->localset))
2283 superblockend = true;
2287 /* check returnAddress variable */
2288 if (!typevectorset_checkretaddr(state->localset,state->iptr->op1))
2289 TYPECHECK_VERIFYERROR_bool("illegal instruction: RET using non-returnAddress variable");
2291 if (!typestate_ret(state,state->iptr->op1))
2294 superblockend = true;
2297 /****************************************/
2300 case ICMD_INVOKEVIRTUAL:
2301 case ICMD_INVOKESPECIAL:
2302 case ICMD_INVOKESTATIC:
2303 case ICMD_INVOKEINTERFACE:
2304 TYPECHECK_COUNT(stat_ins_invoke);
2305 if (!verify_invocation(state))
2307 TYPECHECK_COUNTIF(!state->iptr[0].val.a,stat_ins_invoke_unresolved);
2311 /****************************************/
2312 /* MULTIANEWARRAY */
2314 case ICMD_MULTIANEWARRAY:
2315 if (!verify_multianewarray(state))
2320 /****************************************/
2324 TYPECHECK_COUNT(stat_ins_builtin);
2325 if (!verify_builtin(state))
2330 /****************************************/
2331 /* SIMPLE EXCEPTION THROWING TESTS */
2333 case ICMD_CHECKNULL:
2334 /* CHECKNULL just requires that the stack top
2335 * is an address. This is checked in stack.c */
2339 /****************************************/
2340 /* INSTRUCTIONS WHICH SHOULD HAVE BEEN */
2341 /* REPLACED BY OTHER OPCODES */
2343 #ifdef TYPECHECK_DEBUG
2346 case ICMD_ANEWARRAY:
2347 case ICMD_MONITORENTER:
2348 case ICMD_MONITOREXIT:
2349 LOG2("ICMD %d at %d\n", state->iptr->opc, (int)(state->iptr-state->bptr->iinstr));
2350 LOG("Should have been converted to builtin function call.");
2351 TYPECHECK_ASSERT(false);
2355 /****************************************/
2356 /* UNCHECKED OPERATIONS */
2358 /*********************************************
2359 * Instructions below...
2360 * *) don't operate on local variables,
2361 * *) don't operate on references,
2362 * *) don't operate on returnAddresses,
2363 * *) don't affect control flow (except
2364 * by throwing exceptions).
2366 * (These instructions are typechecked in
2368 ********************************************/
2370 /* Instructions which may throw a runtime exception: */
2380 /* Instructions which never throw a runtime exception: */
2381 #if defined(TYPECHECK_DEBUG) || defined(TYPECHECK_STATISTICS)
2415 case ICMD_IADDCONST:
2416 case ICMD_ISUBCONST:
2417 case ICMD_IMULCONST:
2418 case ICMD_IANDCONST:
2420 case ICMD_IXORCONST:
2421 case ICMD_ISHLCONST:
2422 case ICMD_ISHRCONST:
2423 case ICMD_IUSHRCONST:
2425 case ICMD_LADDCONST:
2426 case ICMD_LSUBCONST:
2427 case ICMD_LMULCONST:
2428 case ICMD_LANDCONST:
2430 case ICMD_LXORCONST:
2431 case ICMD_LSHLCONST:
2432 case ICMD_LSHRCONST:
2433 case ICMD_LUSHRCONST:
2450 case ICMD_INT2SHORT:
2453 case ICMD_LCMPCONST:
2472 case ICMD_INLINE_START:
2473 case ICMD_INLINE_END:
2475 /*XXX What shall we do with the following ?*/
2476 case ICMD_AASTORECONST:
2477 TYPECHECK_COUNT(stat_ins_unchecked);
2480 /****************************************/
2483 LOG2("ICMD %d at %d\n", state->iptr->opc, (int)(state->iptr-state->bptr->iinstr));
2484 TYPECHECK_VERIFYERROR_bool("Missing ICMD code during typecheck");
2488 /* the output of this instruction becomes the current stack */
2489 state->curstack = dst;
2491 /* reach exception handlers for this instruction */
2493 TYPECHECK_COUNT(stat_ins_maythrow);
2494 TYPECHECK_MARK(state->stat_maythrow);
2495 LOG("reaching exception handlers");
2497 while (state->handlers[i]) {
2498 TYPECHECK_COUNT(stat_handlers_reached);
2499 if (state->handlers[i]->catchtype.any)
2500 state->excstack.typeinfo.typeclass = state->handlers[i]->catchtype;
2502 state->excstack.typeinfo.typeclass.cls = class_java_lang_Throwable;
2503 if (!typestate_reach(state,
2504 state->handlers[i]->handler,
2505 &(state->excstack),state->localset))
2511 LOG("next instruction");
2513 } /* while instructions */
2515 LOG("instructions done");
2516 LOGSTR("RESULT=> ");
2517 DOLOG(typestate_print(typecheck_logfile,state->curstack,state->localset,state->numlocals));
2520 /* propagate stack and variables to the following block */
2521 if (!superblockend) {
2522 LOG("reaching following block");
2523 tbptr = state->bptr + 1;
2524 while (tbptr->flags == BBDELETED) {
2526 #ifdef TYPECHECK_DEBUG
2527 /* this must be checked in parse.c */
2528 if ((tbptr->nr) >= state->m->basicblockcount)
2529 TYPECHECK_VERIFYERROR_bool("Control flow falls off the last block");
2532 if (!typestate_reach(state,tbptr,dst,state->localset))
2536 /* We may have to restore the types of the instack slots. They
2537 * have been saved if an <init> call inside the block has
2538 * modified the instack types. (see INVOKESPECIAL) */
2540 if (state->savedstack)
2541 typestate_restore_instack(state);
2546 /* verify_init_locals **********************************************************
2548 Initialize the local variables in the verifier state.
2551 state............the current state of the verifier
2554 true.............success,
2555 false............an exception has been thrown.
2557 *******************************************************************************/
2560 verify_init_locals(verifier_state *state)
2566 /* initialize the variable types of the first block */
2567 /* to the types of the arguments */
2569 lset = MGET_TYPEVECTOR(state->localbuf,0,state->numlocals);
2573 i = state->validlocals;
2575 /* allocate parameter descriptors if necessary */
2577 if (!state->m->parseddesc->params)
2578 if (!descriptor_params_from_paramtypes(state->m->parseddesc,state->m->flags))
2581 /* if this is an instance method initialize the "this" ref type */
2583 if (!(state->m->flags & ACC_STATIC)) {
2585 TYPECHECK_VERIFYERROR_bool("Not enough local variables for method arguments");
2586 td->type = TYPE_ADR;
2587 if (state->initmethod)
2588 TYPEINFO_INIT_NEWOBJECT(td->info,NULL);
2590 typeinfo_init_classinfo(&(td->info), state->m->class);
2595 LOG("'this' argument set.\n");
2597 /* the rest of the arguments and the return type */
2599 i = typedescriptors_init_from_methoddesc(td, state->m->parseddesc,
2601 true, /* two word types use two slots */
2602 (td - lset->td), /* skip 'this' pointer */
2603 &state->returntype);
2608 /* variables not used for arguments are initialized to TYPE_VOID */
2610 i = state->numlocals - (td - lset->td);
2612 td->type = TYPE_VOID;
2616 LOG("Arguments set.\n");
2620 /* typecheck_init_flags ********************************************************
2622 Initialize the basic block flags for the following CFG traversal.
2625 state............the current state of the verifier
2627 *******************************************************************************/
2630 typecheck_init_flags(verifier_state *state)
2635 /* set all BBFINISHED blocks to BBTYPECHECK_UNDEF. */
2637 i = state->m->basicblockcount;
2638 block = state->m->basicblocks;
2642 #ifdef TYPECHECK_DEBUG
2643 /* check for invalid flags */
2644 if (block->flags != BBFINISHED && block->flags != BBDELETED && block->flags != BBUNDEF)
2646 /*show_icmd_method(state->cd->method,state->cd,state->rd);*/
2647 LOGSTR1("block flags: %d\n",block->flags); LOGFLUSH;
2648 TYPECHECK_ASSERT(false);
2652 if (block->flags >= BBFINISHED) {
2653 block->flags = BBTYPECHECK_UNDEF;
2658 /* the first block is always reached */
2660 if (state->m->basicblockcount && state->m->basicblocks[0].flags == BBTYPECHECK_UNDEF)
2661 state->m->basicblocks[0].flags = BBTYPECHECK_REACHED;
2664 /* typecheck_reset_flags *******************************************************
2666 Reset the flags of basic blocks we have not reached.
2669 state............the current state of the verifier
2671 *******************************************************************************/
2674 typecheck_reset_flags(verifier_state *state)
2678 /* check for invalid flags at exit */
2680 #ifdef TYPECHECK_DEBUG
2681 for (i=0; i<state->m->basicblockcount; ++i) {
2682 if (state->m->basicblocks[i].flags != BBDELETED
2683 && state->m->basicblocks[i].flags != BBUNDEF
2684 && state->m->basicblocks[i].flags != BBFINISHED
2685 && state->m->basicblocks[i].flags != BBTYPECHECK_UNDEF) /* typecheck may never reach
2686 * some exception handlers,
2689 LOG2("block L%03d has invalid flags after typecheck: %d",
2690 state->m->basicblocks[i].nr,state->m->basicblocks[i].flags);
2691 TYPECHECK_ASSERT(false);
2696 /* Reset blocks we never reached */
2698 for (i=0; i<state->m->basicblockcount; ++i) {
2699 if (state->m->basicblocks[i].flags == BBTYPECHECK_UNDEF)
2700 state->m->basicblocks[i].flags = BBFINISHED;
2704 /****************************************************************************/
2706 /* This is the main function of the bytecode verifier. It is called */
2707 /* directly after analyse_stack. */
2710 /* meth.............the method to verify */
2711 /* cdata............codegendata for the method */
2712 /* rdata............registerdata for the method */
2715 /* true.............successful verification */
2716 /* false............an exception has been thrown */
2718 /****************************************************************************/
2720 #define MAXPARAMS 255
2722 bool typecheck(jitdata *jd)
2727 verifier_state state; /* current state of the verifier */
2728 int i; /* temporary counter */
2730 /* collect statistics */
2732 #ifdef TYPECHECK_STATISTICS
2733 int count_iterations = 0;
2734 TYPECHECK_COUNT(stat_typechecked);
2735 TYPECHECK_COUNT_FREQ(stat_locals,cdata->maxlocals,STAT_LOCALS);
2736 TYPECHECK_COUNT_FREQ(stat_blocks,cdata->method->basicblockcount/10,STAT_BLOCKS);
2737 TYPECHECK_COUNTIF(cdata->method->exceptiontablelength != 0,stat_methods_with_handlers);
2738 state.stat_maythrow = false;
2741 /* get required compiler data */
2747 /* some logging on entry */
2749 DOLOG(typecheck_logfile = stdout);
2750 LOGSTR("\n==============================================================================\n");
2751 /*DOLOG( show_icmd_method(cdata->method,cdata,rdata));*/
2752 LOGSTR("\n==============================================================================\n");
2753 LOGMETHOD("Entering typecheck: ",cdata->method);
2755 /* initialize the verifier state */
2757 state.savedstackbuf = NULL;
2758 state.savedstack = NULL;
2759 state.jsrencountered = false;
2764 /* check if this method is an instance initializer method */
2766 state.initmethod = (state.m->name == utf_init);
2768 /* initialize the basic block flags for the following CFG traversal */
2770 typecheck_init_flags(&state);
2772 /* number of local variables */
2774 /* In <init> methods we use an extra local variable to indicate whether */
2775 /* the 'this' reference has been initialized. */
2776 /* TYPE_VOID...means 'this' has not been initialized, */
2777 /* TYPE_INT....means 'this' has been initialized. */
2778 state.numlocals = state.cd->maxlocals;
2779 state.validlocals = state.numlocals;
2780 if (state.initmethod) state.numlocals++;
2782 /* allocate the buffers for local variables */
2784 state.localbuf = DMNEW_TYPEVECTOR(state.m->basicblockcount+1, state.numlocals);
2785 state.localset = MGET_TYPEVECTOR(state.localbuf,state.m->basicblockcount,state.numlocals);
2787 LOG("Variable buffer allocated.\n");
2789 /* allocate the buffer of active exception handlers */
2791 state.handlers = DMNEW(exceptiontable*, state.cd->exceptiontablelength + 1);
2793 /* initialized local variables of first block */
2795 if (!verify_init_locals(&state))
2798 /* initialize the input stack of exception handlers */
2800 state.excstack.prev = NULL;
2801 state.excstack.type = TYPE_ADR;
2802 typeinfo_init_classinfo(&(state.excstack.typeinfo),
2803 class_java_lang_Throwable); /* changed later */
2805 LOG("Exception handler stacks set.\n");
2807 /* loop while there are still blocks to be checked */
2809 TYPECHECK_COUNT(count_iterations);
2811 state.repeat = false;
2813 i = state.m->basicblockcount;
2814 state.bptr = state.m->basicblocks;
2817 LOGSTR1("---- BLOCK %04d, ",state.bptr->nr);
2818 LOGSTR1("blockflags: %d\n",state.bptr->flags);
2821 /* verify reached block */
2822 if (state.bptr->flags == BBTYPECHECK_REACHED) {
2823 if (!verify_basic_block(&state))
2827 } /* while blocks */
2829 LOGIF(state.repeat,"state.repeat == true");
2830 } while (state.repeat);
2834 #ifdef TYPECHECK_STATISTICS
2835 LOG1("Typechecker did %4d iterations",count_iterations);
2836 TYPECHECK_COUNT_FREQ(stat_iterations,count_iterations,STAT_ITERATIONS);
2837 TYPECHECK_COUNTIF(state.jsrencountered,stat_typechecked_jsr);
2838 TYPECHECK_COUNTIF(state.stat_maythrow,stat_methods_maythrow);
2841 /* reset the flags of blocks we haven't reached */
2843 typecheck_reset_flags(&state);
2845 /* everything's ok */
2847 LOGimp("exiting typecheck");
2851 #endif /* ENABLE_VERIFIER */
2854 * These are local overrides for various environment variables in Emacs.
2855 * Please do not remove this and leave it at the end of the file, where
2856 * Emacs will automagically detect them.
2857 * ---------------------------------------------------------------------
2860 * indent-tabs-mode: t
2864 * vim:noexpandtab:sw=4:ts=4: