5 * File name: ir/ana2/pto.c
9 * Created: Mon 18 Oct 2004
11 * Copyright: (c) 1999-2004 Universität Karlsruhe
12 * Licence: This file is protected by GPL - GNU GENERAL PUBLIC LICENSE.
20 # include "typalise.h"
25 # endif /* not defined TRUE */
33 # include "irnode_t.h"
43 static long ta_id = 0;
48 static typalise_t *typalise_proj (ir_node*);
51 static void cough_and_die (ir_node *node)
53 ir_graph *graph = get_irn_irg (node);
55 fprintf (stdout, "%s: %s[%li]\n",
57 get_op_name (get_irn_op (node)),
58 get_irn_node_nr (node));
59 dump_ir_block_graph (graph, "-typealise");
66 static type *java_lang_Throwable_tp = NULL;
68 static type *get_java_lang_Throwable ()
70 assert (NULL != java_lang_Throwable_tp);
72 return (java_lang_Throwable_tp);
75 static void find_java_lang_Throwable (type *tp, void *_unused)
77 const char *name = get_type_name (tp);
79 if (0 == strcmp (name, "java/lang/Throwable")) {
80 assert (NULL == java_lang_Throwable_tp);
82 java_lang_Throwable_tp = tp;
88 Ctors, Dtors for typalise_t-s
90 static typalise_t *ta_exact (type *tp)
92 typalise_t *ta = xmalloc (sizeof (typalise_t));
93 ta->kind = type_exact;
97 assert (is_Class_type (tp));
102 static typalise_t *ta_types (lset_t *set)
104 typalise_t *ta = xmalloc (sizeof (typalise_t));
105 ta->kind = type_types;
112 static typalise_t *ta_type (type *tp)
114 typalise_t *ta = xmalloc (sizeof (typalise_t));
115 ta->kind = type_type;
119 assert (is_Class_type (tp));
124 static void ta_delete (typalise_t *ta)
126 if (type_types == ta->kind) {
127 lset_destroy (ta->res.types);
128 ta->res.types = NULL;
133 ta->kind = type_invalid;
139 Helpers for inheritance, overwriting and stuff
142 Find out whether otype is a subtype of stype.
143 Return non-zero iff otype is a subtype of stype.
145 static int is_subtype (type *otype, type *stype)
147 int n_sub = get_class_n_subtypes (stype);
151 if (otype == stype) {
155 for (i = 0; (!is_sub) && (i < n_sub); i ++) {
156 type *sub = get_class_subtype (stype, i);
158 is_sub |= is_subtype (otype, sub);
167 Compute the closure of all subtypes of otype (including otype
170 static void _collect_subtypes (type *otype, lset_t *set)
174 lset_insert (set, otype);
176 n_sub = get_class_n_subtypes (otype);
177 for (i = 0; i < n_sub; i ++) {
178 type *sub = get_class_subtype (otype, i);
180 _collect_subtypes (sub, set);
184 static lset_t *subtype_closure (type *otype)
186 lset_t *set = lset_create ();
188 _collect_subtypes (otype, set);
194 Helper method for get_owner_types
196 static void _collect_owner_types (entity *method, ir_graph *graph, lset_t *tps)
200 /* search DOWNwards in clazz hierarchy */
202 if ((peculiarity_description == get_entity_peculiarity (method)) ||
203 (peculiarity_inherited == get_entity_peculiarity (method))) {
204 lset_insert (tps, get_entity_owner (method));
205 } else if (peculiarity_existent == get_entity_peculiarity (method)) {
206 ir_graph *ex_graph = get_entity_irg (method);
208 if ((NULL == ex_graph) || (ex_graph == graph)) {
209 /* wtf? they define the same graph again? well, whatever: */
210 lset_insert (tps, get_entity_owner (method));
212 /* aha: they define a new graph. can't have that, so bail out */
217 n_over = get_entity_n_overwrittenby (method);
218 for (i = 0; i < n_over; i ++) {
219 entity *ometh = get_entity_overwrittenby (method, i);
221 _collect_owner_types (ometh, graph, tps);
227 Collect all classes that use the given implementation of a method.
229 static lset_t *get_owner_types (ir_graph *graph)
231 lset_t *tps = lset_create ();
232 entity *meth = get_irg_entity (graph);
234 _collect_owner_types (meth, graph, tps);
240 Return a list containing all types of 'set' which are a subtype of 'type'.
242 static lset_t *filter_for_type (lset_t *set, type *stype)
244 type *curs = (type*) lset_first (set);
245 lset_t *lset = lset_create ();
247 while (NULL != curs) {
248 if (is_subtype (curs, stype)) {
249 lset_insert (lset, curs);
252 curs = lset_next (set);
262 Join 'one' and 'two'; both args are deallocated, result is freshly
265 static typalise_t *ta_join (typalise_t *one, typalise_t *two)
267 typalise_t *res = NULL;
269 /* now, one==NULL or two==NULL cannot happen legitimately (if we hit a NULL pointer constant)
279 case (type_invalid): { /* shut up, gcc */ }
282 case (type_invalid): { /* shut up, gcc */ }
284 if (one->res.type == two->res.type) {
287 lset_t *set = lset_create ();
288 lset_insert (set, one->res.type);
289 lset_insert (set, two->res.type);
290 res = ta_types (set);
298 lset_insert (two->res.types, one->res.type);
304 if (is_subtype (one->res.type, two->res.type)) {
308 lset_t *closure = subtype_closure (two->res.type);
309 lset_insert (closure, one->res.type);
320 case (type_invalid): { /* shut up, gcc */ }
322 res = ta_join (two, one);
325 lset_insert_all (one->res.types, two->res.types);
331 lset_t *closure = subtype_closure (two->res.type);
332 lset_append (one->res.types, closure);
342 case (type_invalid): { /* shut up, gcc */ }
344 res = ta_join (two, one);
347 res = ta_join (two, one);
350 type *one_type = one->res.type;
351 type *two_type = two->res.type;
353 if (is_subtype (one_type, two_type)) {
356 } else if (is_subtype (two_type, one_type)) {
360 lset_t *one_closure = subtype_closure (one->res.type);
361 lset_t *two_closure = subtype_closure (two->res.type);
363 lset_append (one_closure, two_closure);
368 res = ta_types (one_closure);
375 assert (res && "no result");
382 static const char *ta_name (typalise_t *ta)
384 # define BUF_SIZE 1024
385 static char buf [BUF_SIZE];
387 int len = sprintf (buf, "[%d] ", ta->id);
390 case (type_invalid): { /* shut up, gcc */ }
392 len += sprintf (buf+len, "only ");
393 strncat (buf, get_type_name (ta->res.type), BUF_SIZE);
396 len += sprintf (buf+len, "one_of ");
398 type *iter = lset_first (ta->res.types);
400 int size = BUF_SIZE - len - 1;
401 while ((NULL != iter) && (0 < size)) {
402 char *dest = strncat (buf, get_type_name (iter), size);
405 iter = lset_next (ta->res.types);
409 len += sprintf (buf+len, "poly ");
410 strncat (buf, get_type_name (ta->res.type), BUF_SIZE);
415 /* # undef BUF_SIZE */
417 # endif /* SHUT_UP_GCC */
420 Find out whether the given clazz uses the given implementation of a
421 method. Presumably, this is because clazz inherits the graph as
422 the implementation for a method.
424 static int uses_graph (type *clazz, entity *meth, ir_graph *graph)
426 type *g_clazz = get_entity_owner (meth);
427 int i, n_over, use = FALSE;
429 if (g_clazz == clazz) {
433 if (peculiarity_existent == get_entity_peculiarity (meth)) {
434 ir_graph *g_graph = get_entity_irg (meth);
436 if (g_graph != graph) {
441 /* else inherited or description */
442 n_over = get_entity_n_overwrittenby (meth); /* DOWN-wards */
443 for (i = 0; (i < n_over) && (!use); i ++) {
444 entity *over = get_entity_overwrittenby (meth, i);
446 use |= uses_graph (clazz, over, graph);
453 Check whether the given typalise_t includes the given type.
455 static int ta_supports (typalise_t *ta, ir_graph *graph)
458 case (type_invalid): { /* shut up, gcc */ }
461 lset_t *tps = get_owner_types (graph);
463 if (lset_contains (tps, ta->res.type)) {
472 entity *meth = get_irg_entity (graph);
473 type *tp = get_entity_owner (meth);
474 int res = is_subtype (tp, ta->res.type);
479 res = uses_graph (ta->res.type, meth, graph);
485 type *tp = get_entity_owner (get_irg_entity (graph));
487 return (lset_contains (ta->res.types, tp));
491 assert (0 && "invalid ta");
496 /* =========== WHAT ELSE ? =========== */
499 Helpers to typalise (ir_node*)
502 Find an approximation to the given load node's value's types
504 static typalise_t *typalise_call (ir_node *call)
508 typalise_t *res = NULL;
509 ir_node *call_ptr = get_Call_ptr (call);
511 if (iro_Sel == get_irn_opcode (call_ptr)) {
512 ent = get_Sel_entity (call_ptr);
513 } else if (iro_SymConst == get_irn_opcode (call_ptr)) {
514 if (get_SymConst_kind (call_ptr) == symconst_addr_ent) {
515 ent = get_SymConst_entity (call_ptr);
516 } else if (get_SymConst_kind (call_ptr) == symconst_addr_name) {
517 ident *id = get_SymConst_name (call_ptr);
518 const char *name = get_id_str (id);
519 if (0 == strcmp (name, "iro_Catch")) {
520 res = ta_type (java_lang_Throwable_tp);
525 fprintf (stdout, "%s: cannot handle Call[%li] (symconst_addr_name=\"%s\")\n",
526 __FUNCTION__, get_irn_node_nr (call),
527 get_op_name (get_irn_op (call_ptr)),
529 cough_and_die (call_ptr);
530 } else if (get_SymConst_kind (call_ptr) == symconst_type_tag) {
531 fprintf (stdout, "%s: cannot handle Call[%li] (symconst_type_tag)\n",
532 __FUNCTION__, get_irn_node_nr (call),
533 get_op_name (get_irn_op (call_ptr)));
534 cough_and_die (call_ptr);
536 fprintf (stdout, "%s: cannot handle Call[%li] (%i)\n",
537 __FUNCTION__, get_irn_node_nr (call),
538 get_SymConst_kind (call_ptr));
539 cough_and_die (call_ptr);
543 tp = get_entity_type (ent);
544 assert (is_Method_type (tp));
546 tp = get_method_res_type (tp, 0);
548 while (is_Pointer_type (tp)) {
549 tp = get_pointer_points_to_type (tp);
559 Find an approximation to the given load node's value's types
561 static typalise_t *typalise_load (ir_node *load)
565 typalise_t *res = NULL;
566 ir_node *load_ptr = get_Load_ptr (load);
568 if (iro_Sel == get_irn_opcode (load_ptr)) {
569 ent = get_Sel_entity (load_ptr);
570 } else if (iro_SymConst == get_irn_opcode (load_ptr)) {
571 if (get_SymConst_kind (load_ptr) == symconst_addr_ent) {
572 ent = get_SymConst_entity (load_ptr);
573 } else if (get_SymConst_kind (load_ptr) == symconst_type_tag) {
574 tp = get_SymConst_type (load_ptr);
576 fprintf (stdout, "%s: cannot handle load (%s)\n",
577 __FUNCTION__, get_op_name (get_irn_op (load_ptr)));
579 cough_and_die (load_ptr);
582 fprintf (stdout, "%s: cannot handle load (%s)\n",
583 __FUNCTION__, get_op_name (get_irn_op (load_ptr)));
584 cough_and_die (load_ptr);
587 tp = get_entity_type (ent);
589 while (is_Pointer_type (tp)) {
590 tp = get_pointer_points_to_type (tp);
600 Find an approximation to the given proj node's value's types
602 static typalise_t *typalise_proj (ir_node *proj)
604 typalise_t *res = NULL;
605 ir_node *proj_in = get_Proj_pred (proj);
607 if (iro_Proj == get_irn_opcode (proj_in)) {
608 /* fprintf (stdout, "\tProj (Proj)\n"); */
610 proj_in = get_Proj_pred (proj_in);
611 if (iro_Start == get_irn_opcode (proj_in)) {
613 ir_graph *graph = get_irn_irg (proj);
614 entity *meth = get_irg_entity (graph);
616 long n = get_Proj_proj (proj);
617 type *tp = get_method_param_type (get_entity_type (meth), n);
618 if (is_Pointer_type (tp)) {
619 tp = get_pointer_points_to_type (tp);
624 } else if (iro_Call == get_irn_opcode (proj_in)) {
625 /* call result ... 'whatever' */
626 res = typalise_call (proj_in);
628 fprintf (stdout, "\n Proj (Proj (%s)) not handled\n",
629 get_op_name (get_irn_op (proj_in)));
630 cough_and_die (proj_in);
633 opcode op = get_irn_opcode (proj_in);
634 if ((iro_Load != op) && (iro_Alloc != op) && (iro_Call != op)) {
635 fprintf (stdout, "\n Proj (%s) not handled\n",
636 get_op_name (get_irn_op (proj_in)));
637 cough_and_die (proj_in);
639 res = typalise (proj_in); /* everything else */
640 /* Proj (Load), Proj (New), Proj (Call) */
652 Given a set of graphs and a typalise_t, return the method (s) in
653 the set that are supported by the typalise_t. Also, deallocates
656 lset_t *filter_for_ta (lset_t *set, typalise_t *ta)
658 lset_t *res = lset_create ();
659 ir_graph *curs = (ir_graph*) lset_first (set);
661 while (NULL != curs) {
662 if (ta_supports (ta, curs)) {
663 lset_insert (res, curs);
666 curs = lset_next (set);
675 For the given ptr, do a quick check about what (class) types may be
678 typalise_t *typalise (ir_node *node)
680 opcode op = get_irn_opcode (node);
681 typalise_t *res = NULL;
685 /* casts always succeed */
686 typalise_t *ta = NULL;
687 type *tp = get_Cast_type (node);
689 if (is_Pointer_type (tp)) {
690 tp = get_pointer_points_to_type (tp);
692 assert (is_Class_type (tp));
694 ta = typalise (get_Cast_op (node));
696 if (NULL == ta) { /* no type found */
698 } else if (type_exact == ta->kind) { /* one type found */
699 /* nothing (maybe check cast? */
700 } else if (type_type == ta->kind) { /* some types found */
701 if (is_subtype (tp, ta->res.type)) {
702 ta->res.type = tp; /* assume cast is correct */
704 /* should assert (is_subtype (ta->res.type, tp)) */
706 } else if (type_types == ta->kind) {
707 lset_t *ftp = filter_for_type (ta->res.types, tp);
708 lset_destroy (ta->res.types);
716 res = typalise_proj (node);
720 res = typalise_load (node);
725 /* it's call (sel (ptr)) or load (sel (ptr)) */
726 entity *ent = get_Sel_entity (node);
727 type *tp = get_entity_type (ent);
729 if (is_Method_type (tp)) {
730 /* obsoleted by typalise_call */
732 tp = get_entity_type (ent);
733 tp = get_method_res_type (tp, 0);
735 if (is_Pointer_type (tp)) {
736 tp = get_pointer_points_to_type (tp);
740 } else if (is_Class_type (tp)) {
741 tp = get_entity_type (ent);
743 if (is_Pointer_type (tp)) {
744 tp = get_pointer_points_to_type (tp);
748 } else if (is_Pointer_type (tp)) {
749 tp = get_pointer_points_to_type (tp);
752 assert (0 && "select not handled");
757 int n_ins = get_irn_arity (node);
759 ir_node *phi_in = NULL;
760 typalise_t *ta = NULL;
762 for (i = 0; i < n_ins; i ++) {
763 phi_in = get_irn_n (node, i);
764 typalise_t *ta_in = typalise (phi_in);
767 ta = (NULL == ta) ? ta_in : ta_join (ta, ta_in);
775 type *type = get_Alloc_type (node);
776 res = ta_exact (type);
780 /* presumably call (sel (proj (call))) */
781 ir_node *ptr = get_Call_ptr (node);
783 if (iro_Sel == get_irn_opcode (ptr)) {
784 meth = get_Sel_entity (ptr);
785 } else if (iro_SymConst == get_irn_opcode (ptr)) {
786 if (get_SymConst_kind (ptr) == symconst_addr_ent) {
787 meth = get_SymConst_entity (ptr);
789 meth = NULL; /* WTF? */
794 type *tp = get_method_res_type ((type*) meth, 0);
797 /* could be anything */
798 /* fprintf (stdout, "meth= (null)"); */
802 /* fprintf (stdout, "]\n"); */
806 case (iro_SymConst): {
807 if (get_SymConst_kind (node) == symconst_type_tag) {
808 type *tp = get_SymConst_type (node);
811 } else if (get_SymConst_kind (node) == symconst_addr_ent) {
812 entity *ent = get_SymConst_entity (node);
813 type *tp = get_entity_owner (ent);
815 while (is_Pointer_type (tp)) {
816 tp = get_pointer_points_to_type (tp);
819 assert (is_Class_type (tp));
821 res = ta_type (tp); /* can't use ta_exact */
822 } else if (get_SymConst_kind (node) == symconst_addr_name) {
823 /* oh, this is not a real call but a placeholder (exception stuff) */
824 fprintf (stdout, "%s (%s:%i): can't handle pseudo-call %s\n",
825 __FUNCTION__, __FILE__, __LINE__,
826 get_op_name (get_irn_op (node)));
830 fprintf (stdout, "%s (%s:%i): can't handle SymConst %s\n",
831 __FUNCTION__, __FILE__, __LINE__,
832 get_op_name (get_irn_op (node)));
838 /* presumably a NULL constant */
839 /* this also means we cannot handle calls against a NULL pointer. */
849 fprintf (stdout, "what's with %s?\n", get_op_name (get_irn_op (node)));
850 cough_and_die (node);
858 Initialise the Typalise module
860 void typalise_init ()
862 if (NULL == java_lang_Throwable_tp) {
863 class_walk_super2sub (find_java_lang_Throwable, NULL, NULL);
865 /* make sure we have found it */
866 get_java_lang_Throwable ();
875 Revision 1.9 2005/03/22 13:56:09 liekweg
876 "small" fix for exception b/d
878 Revision 1.8 2005/01/14 14:13:24 liekweg
881 Revision 1.7 2005/01/10 17:26:34 liekweg
882 fixup printfs, don't put environments on the stack
884 Revision 1.6 2005/01/05 14:25:54 beck
885 renames all is_x*_type() functions to is_X*_type() to prevent name clash with EDG fronten
887 Revision 1.5 2004/12/22 14:43:14 beck
888 made allocations C-like
890 Revision 1.4 2004/12/21 15:50:18 beck
891 removed C99 constructs
893 Revision 1.3 2004/12/02 16:17:51 beck
894 fixed config.h include
896 Revision 1.2 2004/10/22 09:53:10 liekweg
897 Correctly handle proj_args
899 Revision 1.1 2004/10/21 11:09:37 liekweg
900 Moved memwalk stuf into irmemwalk
901 Moved lset stuff into lset
902 Moved typalise stuff into typalise