4 * Copyright (C) 1995-2007 University of Karlsruhe. All right reserved.
6 * This file is part of libFirm.
8 * This file may be distributed and/or modified under the terms of the
9 * GNU General Public License version 2 as published by the Free Software
10 * Foundation and appearing in the file LICENSE.GPL included in the
11 * packaging of this file.
13 * Licensees holding valid libFirm Professional Edition licenses may use
14 * this file in accordance with the libFirm Commercial License.
15 * Agreement provided with the Software.
17 * This file is provided AS IS with NO WARRANTY OF ANY KIND, INCLUDING THE
18 * WARRANTY OF DESIGN, MERCHANTABILITY AND FITNESS FOR A PARTICULAR
26 * @date Mon 18 Oct 2004
33 # include "typalise.h"
38 # endif /* not defined TRUE */
46 # include "irnode_t.h"
51 # include "typewalk.h"
58 static long ta_id = 0;
63 static typalise_t *typalise_proj (ir_node*);
66 static void cough_and_die (ir_node *node)
68 ir_graph *graph = get_irn_irg (node);
70 fprintf (stdout, "%s: %s[%li]\n",
72 get_op_name (get_irn_op (node)),
73 get_irn_node_nr (node));
74 dump_ir_block_graph (graph, "-typealise");
81 static ir_type *java_lang_Throwable_tp = NULL;
83 static ir_type *get_java_lang_Throwable (void)
85 assert (NULL != java_lang_Throwable_tp);
87 return (java_lang_Throwable_tp);
90 static void find_java_lang_Throwable (ir_type *tp, void *_unused)
92 const char *name = get_type_name (tp);
94 if (0 == strcmp (name, "java/lang/Throwable")) {
95 assert (NULL == java_lang_Throwable_tp);
97 java_lang_Throwable_tp = tp;
103 Ctors, Dtors for typalise_t-s
105 static typalise_t *ta_exact (ir_type *tp)
107 typalise_t *ta = xmalloc (sizeof (typalise_t));
108 ta->kind = type_exact;
112 assert (is_Class_type (tp));
117 static typalise_t *ta_types (lset_t *set)
119 typalise_t *ta = xmalloc (sizeof (typalise_t));
120 ta->kind = type_types;
127 static typalise_t *ta_type (ir_type *tp)
129 typalise_t *ta = xmalloc (sizeof (typalise_t));
130 ta->kind = type_type;
134 assert (is_Class_type (tp));
139 static void ta_delete (typalise_t *ta)
141 if (type_types == ta->kind) {
142 lset_destroy (ta->res.types);
143 ta->res.types = NULL;
148 ta->kind = type_invalid;
154 Helpers for inheritance, overwriting and stuff
157 Find out whether otype is a subtype of stype.
158 Return non-zero iff otype is a subtype of stype.
160 static int is_subtype (ir_type *otype, ir_type *stype)
162 int n_sub = get_class_n_subtypes (stype);
166 if (otype == stype) {
170 for (i = 0; (!is_sub) && (i < n_sub); i ++) {
171 ir_type *sub = get_class_subtype (stype, i);
173 is_sub |= is_subtype (otype, sub);
182 Compute the closure of all subtypes of otype (including otype
185 static void _collect_subtypes (ir_type *otype, lset_t *set)
189 lset_insert (set, otype);
191 n_sub = get_class_n_subtypes (otype);
192 for (i = 0; i < n_sub; i ++) {
193 ir_type *sub = get_class_subtype (otype, i);
195 _collect_subtypes (sub, set);
199 static lset_t *subtype_closure (ir_type *otype)
201 lset_t *set = lset_create ();
203 _collect_subtypes (otype, set);
209 Helper method for get_owner_types
211 static void _collect_owner_types (ir_entity *method, ir_graph *graph, lset_t *tps)
215 /* search DOWNwards in clazz hierarchy */
217 if ((peculiarity_description == get_entity_peculiarity (method)) ||
218 (peculiarity_inherited == get_entity_peculiarity (method))) {
219 lset_insert (tps, get_entity_owner (method));
220 } else if (peculiarity_existent == get_entity_peculiarity (method)) {
221 ir_graph *ex_graph = get_entity_irg (method);
223 if ((NULL == ex_graph) || (ex_graph == graph)) {
224 /* wtf? they define the same graph again? well, whatever: */
225 lset_insert (tps, get_entity_owner (method));
227 /* aha: they define a new graph. can't have that, so bail out */
232 n_over = get_entity_n_overwrittenby (method);
233 for (i = 0; i < n_over; i ++) {
234 ir_entity *ometh = get_entity_overwrittenby (method, i);
236 _collect_owner_types (ometh, graph, tps);
242 Collect all classes that use the given implementation of a method.
244 static lset_t *get_owner_types (ir_graph *graph)
246 lset_t *tps = lset_create ();
247 ir_entity *meth = get_irg_entity (graph);
249 _collect_owner_types (meth, graph, tps);
255 Return a list containing all types of 'set' which are a subtype of 'type'.
257 static lset_t *filter_for_type (lset_t *set, ir_type *stype)
259 ir_type *curs = (ir_type*) lset_first (set);
260 lset_t *lset = lset_create ();
262 while (NULL != curs) {
263 if (is_subtype (curs, stype)) {
264 lset_insert (lset, curs);
267 curs = lset_next (set);
277 Join 'one' and 'two'; both args are deallocated, result is freshly
280 static typalise_t *ta_join (typalise_t *one, typalise_t *two)
282 typalise_t *res = NULL;
284 /* now, one==NULL or two==NULL cannot happen legitimately (if we hit a NULL pointer constant)
294 case (type_invalid): { /* shut up, gcc */ }
297 case (type_invalid): { /* shut up, gcc */ }
299 if (one->res.type == two->res.type) {
302 lset_t *set = lset_create ();
303 lset_insert (set, one->res.type);
304 lset_insert (set, two->res.type);
305 res = ta_types (set);
313 lset_insert (two->res.types, one->res.type);
319 if (is_subtype (one->res.type, two->res.type)) {
323 lset_t *closure = subtype_closure (two->res.type);
324 lset_insert (closure, one->res.type);
335 case (type_invalid): { /* shut up, gcc */ }
337 res = ta_join (two, one);
340 lset_insert_all (one->res.types, two->res.types);
346 lset_t *closure = subtype_closure (two->res.type);
347 lset_append (one->res.types, closure);
357 case (type_invalid): { /* shut up, gcc */ }
359 res = ta_join (two, one);
362 res = ta_join (two, one);
365 ir_type *one_type = one->res.type;
366 ir_type *two_type = two->res.type;
368 if (is_subtype (one_type, two_type)) {
371 } else if (is_subtype (two_type, one_type)) {
375 lset_t *one_closure = subtype_closure (one->res.type);
376 lset_t *two_closure = subtype_closure (two->res.type);
378 lset_append (one_closure, two_closure);
383 res = ta_types (one_closure);
390 assert (res && "no result");
397 static const char *ta_name (typalise_t *ta)
399 # define BUF_SIZE 1024
400 static char buf [BUF_SIZE];
402 int len = sprintf (buf, "[%d] ", ta->id);
405 case (type_invalid): { /* shut up, gcc */ }
407 len += sprintf (buf+len, "only ");
408 strncat (buf, get_type_name (ta->res.type), BUF_SIZE);
411 len += sprintf (buf+len, "one_of ");
413 ir_type *iter = lset_first (ta->res.types);
415 int size = BUF_SIZE - len - 1;
416 while ((NULL != iter) && (0 < size)) {
417 char *dest = strncat (buf, get_type_name (iter), size);
420 iter = lset_next (ta->res.types);
424 len += sprintf (buf+len, "poly ");
425 strncat (buf, get_type_name (ta->res.type), BUF_SIZE);
430 /* # undef BUF_SIZE */
432 # endif /* SHUT_UP_GCC */
435 Find out whether the given clazz uses the given implementation of a
436 method. Presumably, this is because clazz inherits the graph as
437 the implementation for a method.
439 static int uses_graph (ir_type *clazz, ir_entity *meth, ir_graph *graph)
441 ir_type *g_clazz = get_entity_owner (meth);
442 int i, n_over, use = FALSE;
444 if (g_clazz == clazz) {
448 if (peculiarity_existent == get_entity_peculiarity (meth)) {
449 ir_graph *g_graph = get_entity_irg (meth);
451 if (g_graph != graph) {
456 /* else inherited or description */
457 n_over = get_entity_n_overwrittenby (meth); /* DOWN-wards */
458 for (i = 0; (i < n_over) && (!use); i ++) {
459 ir_entity *over = get_entity_overwrittenby (meth, i);
461 use |= uses_graph (clazz, over, graph);
468 Check whether the given typalise_t includes the given type.
470 static int ta_supports (typalise_t *ta, ir_graph *graph)
473 case (type_invalid): { /* shut up, gcc */ }
476 lset_t *tps = get_owner_types (graph);
478 if (lset_contains (tps, ta->res.type)) {
487 ir_entity *meth = get_irg_entity (graph);
488 ir_type *tp = get_entity_owner (meth);
489 int res = is_subtype (tp, ta->res.type);
494 res = uses_graph (ta->res.type, meth, graph);
500 ir_type *tp = get_entity_owner (get_irg_entity (graph));
502 return (lset_contains (ta->res.types, tp));
506 assert (0 && "invalid ta");
511 /* =========== WHAT ELSE ? =========== */
514 Helpers to typalise (ir_node*)
517 Find an approximation to the given load node's value's types
519 static typalise_t *typalise_call (ir_node *call)
521 ir_entity *ent = NULL;
523 typalise_t *res = NULL;
524 ir_node *call_ptr = get_Call_ptr (call);
526 if (iro_Sel == get_irn_opcode (call_ptr)) {
527 ent = get_Sel_entity (call_ptr);
528 } else if (iro_SymConst == get_irn_opcode (call_ptr)) {
529 if (get_SymConst_kind (call_ptr) == symconst_addr_ent) {
530 ent = get_SymConst_entity (call_ptr);
531 } else if (get_SymConst_kind (call_ptr) == symconst_addr_name) {
532 ident *id = get_SymConst_name (call_ptr);
533 const char *name = get_id_str (id);
534 if (0 == strcmp (name, "iro_Catch")) {
535 res = ta_type (java_lang_Throwable_tp);
540 fprintf (stdout, "%s: cannot handle Call[%li] (symconst_addr_name=\"%s\")\n",
541 __FUNCTION__, get_irn_node_nr (call),
543 cough_and_die (call_ptr);
544 } else if (get_SymConst_kind (call_ptr) == symconst_type_tag) {
545 fprintf (stdout, "%s: cannot handle Call[%li] (symconst_type_tag)\n",
546 __FUNCTION__, get_irn_node_nr (call));
547 cough_and_die (call_ptr);
549 fprintf (stdout, "%s: cannot handle Call[%li] (%i)\n",
550 __FUNCTION__, get_irn_node_nr (call),
551 get_SymConst_kind (call_ptr));
552 cough_and_die (call_ptr);
556 tp = get_entity_type (ent);
557 assert (is_Method_type (tp));
559 tp = get_method_res_type (tp, 0);
561 while (is_Pointer_type (tp)) {
562 tp = get_pointer_points_to_type (tp);
572 Find an approximation to the given load node's value's types
574 static typalise_t *typalise_load (ir_node *load)
576 ir_entity *ent = NULL;
578 typalise_t *res = NULL;
579 ir_node *load_ptr = get_Load_ptr (load);
581 if (iro_Sel == get_irn_opcode (load_ptr)) {
582 ent = get_Sel_entity (load_ptr);
583 } else if (iro_SymConst == get_irn_opcode (load_ptr)) {
584 if (get_SymConst_kind (load_ptr) == symconst_addr_ent) {
585 ent = get_SymConst_entity (load_ptr);
586 } else if (get_SymConst_kind (load_ptr) == symconst_type_tag) {
587 tp = get_SymConst_type (load_ptr);
589 fprintf (stdout, "%s: cannot handle load (%s)\n",
590 __FUNCTION__, get_op_name (get_irn_op (load_ptr)));
592 cough_and_die (load_ptr);
595 fprintf (stdout, "%s: cannot handle load (%s)\n",
596 __FUNCTION__, get_op_name (get_irn_op (load_ptr)));
597 cough_and_die (load_ptr);
600 tp = get_entity_type (ent);
602 while (is_Pointer_type (tp)) {
603 tp = get_pointer_points_to_type (tp);
613 Find an approximation to the given proj node's value's types
615 static typalise_t *typalise_proj (ir_node *proj)
617 typalise_t *res = NULL;
618 ir_node *proj_in = get_Proj_pred (proj);
620 if (iro_Proj == get_irn_opcode (proj_in)) {
621 /* fprintf (stdout, "\tProj (Proj)\n"); */
623 proj_in = get_Proj_pred (proj_in);
624 if (iro_Start == get_irn_opcode (proj_in)) {
626 ir_graph *graph = get_irn_irg (proj);
627 ir_entity *meth = get_irg_entity (graph);
629 long n = get_Proj_proj (proj);
630 ir_type *tp = get_method_param_type (get_entity_type (meth), n);
631 if (is_Pointer_type (tp)) {
632 tp = get_pointer_points_to_type (tp);
637 } else if (iro_Call == get_irn_opcode (proj_in)) {
638 /* call result ... 'whatever' */
639 res = typalise_call (proj_in);
641 fprintf (stdout, "\n Proj (Proj (%s)) not handled\n",
642 get_op_name (get_irn_op (proj_in)));
643 cough_and_die (proj_in);
646 ir_opcode op = get_irn_opcode (proj_in);
647 if ((iro_Load != op) && (iro_Alloc != op) && (iro_Call != op)) {
648 fprintf (stdout, "\n Proj (%s) not handled\n",
649 get_op_name (get_irn_op (proj_in)));
650 cough_and_die (proj_in);
652 res = typalise (proj_in); /* everything else */
653 /* Proj (Load), Proj (New), Proj (Call) */
665 Given a set of graphs and a typalise_t, return the method (s) in
666 the set that are supported by the typalise_t. Also, deallocates
669 lset_t *filter_for_ta (lset_t *set, typalise_t *ta)
671 lset_t *res = lset_create ();
672 ir_graph *curs = (ir_graph*) lset_first (set);
674 while (NULL != curs) {
675 if (ta_supports (ta, curs)) {
676 lset_insert (res, curs);
679 curs = lset_next (set);
688 For the given ptr, do a quick check about what (class) types may be
691 typalise_t *typalise (ir_node *node)
693 ir_opcode op = get_irn_opcode (node);
694 typalise_t *res = NULL;
698 /* casts always succeed */
699 typalise_t *ta = NULL;
700 ir_type *tp = get_Cast_type (node);
702 if (is_Pointer_type (tp)) {
703 tp = get_pointer_points_to_type (tp);
705 assert (is_Class_type (tp));
707 ta = typalise (get_Cast_op (node));
709 if (NULL == ta) { /* no type found */
711 } else if (type_exact == ta->kind) { /* one type found */
712 /* nothing (maybe check cast? */
713 } else if (type_type == ta->kind) { /* some types found */
714 if (is_subtype (tp, ta->res.type)) {
715 ta->res.type = tp; /* assume cast is correct */
717 /* should assert (is_subtype (ta->res.type, tp)) */
719 } else if (type_types == ta->kind) {
720 lset_t *ftp = filter_for_type (ta->res.types, tp);
721 lset_destroy (ta->res.types);
729 res = typalise_proj (node);
733 res = typalise_load (node);
738 /* it's call (sel (ptr)) or load (sel (ptr)) */
739 ir_entity *ent = get_Sel_entity (node);
740 ir_type *tp = get_entity_type (ent);
742 if (is_Method_type (tp)) {
743 /* obsoleted by typalise_call */
745 tp = get_entity_type (ent);
746 tp = get_method_res_type (tp, 0);
748 if (is_Pointer_type (tp)) {
749 tp = get_pointer_points_to_type (tp);
753 } else if (is_Class_type (tp)) {
754 tp = get_entity_type (ent);
756 if (is_Pointer_type (tp)) {
757 tp = get_pointer_points_to_type (tp);
761 } else if (is_Pointer_type (tp)) {
762 tp = get_pointer_points_to_type (tp);
765 assert (0 && "select not handled");
770 int n_ins = get_irn_arity (node);
772 ir_node *phi_in = NULL;
773 typalise_t *ta = NULL;
775 for (i = 0; i < n_ins; i ++) {
778 phi_in = get_irn_n (node, i);
779 ta_in = typalise (phi_in);
782 ta = (NULL == ta) ? ta_in : ta_join (ta, ta_in);
790 ir_type *type = get_Alloc_type (node);
791 res = ta_exact (type);
795 /* presumably call (sel (proj (call))) */
796 ir_node *ptr = get_Call_ptr (node);
797 ir_entity *meth = NULL;
798 if (iro_Sel == get_irn_opcode (ptr)) {
799 meth = get_Sel_entity (ptr);
800 } else if (iro_SymConst == get_irn_opcode (ptr)) {
801 if (get_SymConst_kind (ptr) == symconst_addr_ent) {
802 meth = get_SymConst_entity (ptr);
804 meth = NULL; /* WTF? */
809 ir_type *tp = get_method_res_type ((ir_type*) meth, 0);
812 /* could be anything */
813 /* fprintf (stdout, "meth= (null)"); */
817 /* fprintf (stdout, "]\n"); */
821 case (iro_SymConst): {
822 if (get_SymConst_kind (node) == symconst_type_tag) {
823 ir_type *tp = get_SymConst_type (node);
826 } else if (get_SymConst_kind (node) == symconst_addr_ent) {
827 ir_entity *ent = get_SymConst_entity (node);
828 ir_type *tp = get_entity_owner (ent);
830 while (is_Pointer_type (tp)) {
831 tp = get_pointer_points_to_type (tp);
834 assert (is_Class_type (tp));
836 res = ta_type (tp); /* can't use ta_exact */
837 } else if (get_SymConst_kind (node) == symconst_addr_name) {
838 /* oh, this is not a real call but a placeholder (exception stuff) */
839 fprintf (stdout, "%s (%s:%i): can't handle pseudo-call %s\n",
840 __FUNCTION__, __FILE__, __LINE__,
841 get_op_name (get_irn_op (node)));
845 fprintf (stdout, "%s (%s:%i): can't handle SymConst %s\n",
846 __FUNCTION__, __FILE__, __LINE__,
847 get_op_name (get_irn_op (node)));
853 /* presumably a NULL constant */
854 /* this also means we cannot handle calls against a NULL pointer. */
864 fprintf (stdout, "what's with %s?\n", get_op_name (get_irn_op (node)));
865 cough_and_die (node);
873 Initialise the Typalise module
875 void typalise_init (void)
877 if (NULL == java_lang_Throwable_tp) {
878 class_walk_super2sub (find_java_lang_Throwable, NULL, NULL);
880 /* make sure we have found it */
881 get_java_lang_Throwable ();
890 Revision 1.14 2007/01/16 15:45:42 beck
891 renamed type opcode to ir_opcode
893 Revision 1.13 2006/12/13 19:46:47 beck
894 rename type entity into ir_entity
896 Revision 1.12 2006/01/13 21:54:02 beck
897 renamed all types 'type' to 'ir_type'
899 Revision 1.11 2005/05/13 16:35:14 beck
900 made (void) prototypes
901 removed unused fprintf arguments
903 Revision 1.10 2005/05/06 12:02:34 beck
904 added missing includes
907 Revision 1.9 2005/03/22 13:56:09 liekweg
908 "small" fix for exception b/d
910 Revision 1.8 2005/01/14 14:13:24 liekweg
913 Revision 1.7 2005/01/10 17:26:34 liekweg
914 fixup printfs, don't put environments on the stack
916 Revision 1.6 2005/01/05 14:25:54 beck
917 renames all is_x*_type() functions to is_X*_type() to prevent name clash with EDG fronten
919 Revision 1.5 2004/12/22 14:43:14 beck
920 made allocations C-like
922 Revision 1.4 2004/12/21 15:50:18 beck
923 removed C99 constructs
925 Revision 1.3 2004/12/02 16:17:51 beck
926 fixed config.h include
928 Revision 1.2 2004/10/22 09:53:10 liekweg
929 Correctly handle proj_args
931 Revision 1.1 2004/10/21 11:09:37 liekweg
932 Moved memwalk stuf into irmemwalk
933 Moved lset stuff into lset
934 Moved typalise stuff into typalise