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"
38 # include "typewalk.h"
45 static long ta_id = 0;
50 static typalise_t *typalise_proj (ir_node*);
53 static void cough_and_die (ir_node *node)
55 ir_graph *graph = get_irn_irg (node);
57 fprintf (stdout, "%s: %s[%li]\n",
59 get_op_name (get_irn_op (node)),
60 get_irn_node_nr (node));
61 dump_ir_block_graph (graph, "-typealise");
68 static ir_type *java_lang_Throwable_tp = NULL;
70 static ir_type *get_java_lang_Throwable (void)
72 assert (NULL != java_lang_Throwable_tp);
74 return (java_lang_Throwable_tp);
77 static void find_java_lang_Throwable (ir_type *tp, void *_unused)
79 const char *name = get_type_name (tp);
81 if (0 == strcmp (name, "java/lang/Throwable")) {
82 assert (NULL == java_lang_Throwable_tp);
84 java_lang_Throwable_tp = tp;
90 Ctors, Dtors for typalise_t-s
92 static typalise_t *ta_exact (ir_type *tp)
94 typalise_t *ta = xmalloc (sizeof (typalise_t));
95 ta->kind = type_exact;
99 assert (is_Class_type (tp));
104 static typalise_t *ta_types (lset_t *set)
106 typalise_t *ta = xmalloc (sizeof (typalise_t));
107 ta->kind = type_types;
114 static typalise_t *ta_type (ir_type *tp)
116 typalise_t *ta = xmalloc (sizeof (typalise_t));
117 ta->kind = type_type;
121 assert (is_Class_type (tp));
126 static void ta_delete (typalise_t *ta)
128 if (type_types == ta->kind) {
129 lset_destroy (ta->res.types);
130 ta->res.types = NULL;
135 ta->kind = type_invalid;
141 Helpers for inheritance, overwriting and stuff
144 Find out whether otype is a subtype of stype.
145 Return non-zero iff otype is a subtype of stype.
147 static int is_subtype (ir_type *otype, ir_type *stype)
149 int n_sub = get_class_n_subtypes (stype);
153 if (otype == stype) {
157 for (i = 0; (!is_sub) && (i < n_sub); i ++) {
158 ir_type *sub = get_class_subtype (stype, i);
160 is_sub |= is_subtype (otype, sub);
169 Compute the closure of all subtypes of otype (including otype
172 static void _collect_subtypes (ir_type *otype, lset_t *set)
176 lset_insert (set, otype);
178 n_sub = get_class_n_subtypes (otype);
179 for (i = 0; i < n_sub; i ++) {
180 ir_type *sub = get_class_subtype (otype, i);
182 _collect_subtypes (sub, set);
186 static lset_t *subtype_closure (ir_type *otype)
188 lset_t *set = lset_create ();
190 _collect_subtypes (otype, set);
196 Helper method for get_owner_types
198 static void _collect_owner_types (entity *method, ir_graph *graph, lset_t *tps)
202 /* search DOWNwards in clazz hierarchy */
204 if ((peculiarity_description == get_entity_peculiarity (method)) ||
205 (peculiarity_inherited == get_entity_peculiarity (method))) {
206 lset_insert (tps, get_entity_owner (method));
207 } else if (peculiarity_existent == get_entity_peculiarity (method)) {
208 ir_graph *ex_graph = get_entity_irg (method);
210 if ((NULL == ex_graph) || (ex_graph == graph)) {
211 /* wtf? they define the same graph again? well, whatever: */
212 lset_insert (tps, get_entity_owner (method));
214 /* aha: they define a new graph. can't have that, so bail out */
219 n_over = get_entity_n_overwrittenby (method);
220 for (i = 0; i < n_over; i ++) {
221 entity *ometh = get_entity_overwrittenby (method, i);
223 _collect_owner_types (ometh, graph, tps);
229 Collect all classes that use the given implementation of a method.
231 static lset_t *get_owner_types (ir_graph *graph)
233 lset_t *tps = lset_create ();
234 entity *meth = get_irg_entity (graph);
236 _collect_owner_types (meth, graph, tps);
242 Return a list containing all types of 'set' which are a subtype of 'type'.
244 static lset_t *filter_for_type (lset_t *set, ir_type *stype)
246 ir_type *curs = (ir_type*) lset_first (set);
247 lset_t *lset = lset_create ();
249 while (NULL != curs) {
250 if (is_subtype (curs, stype)) {
251 lset_insert (lset, curs);
254 curs = lset_next (set);
264 Join 'one' and 'two'; both args are deallocated, result is freshly
267 static typalise_t *ta_join (typalise_t *one, typalise_t *two)
269 typalise_t *res = NULL;
271 /* now, one==NULL or two==NULL cannot happen legitimately (if we hit a NULL pointer constant)
281 case (type_invalid): { /* shut up, gcc */ }
284 case (type_invalid): { /* shut up, gcc */ }
286 if (one->res.type == two->res.type) {
289 lset_t *set = lset_create ();
290 lset_insert (set, one->res.type);
291 lset_insert (set, two->res.type);
292 res = ta_types (set);
300 lset_insert (two->res.types, one->res.type);
306 if (is_subtype (one->res.type, two->res.type)) {
310 lset_t *closure = subtype_closure (two->res.type);
311 lset_insert (closure, one->res.type);
322 case (type_invalid): { /* shut up, gcc */ }
324 res = ta_join (two, one);
327 lset_insert_all (one->res.types, two->res.types);
333 lset_t *closure = subtype_closure (two->res.type);
334 lset_append (one->res.types, closure);
344 case (type_invalid): { /* shut up, gcc */ }
346 res = ta_join (two, one);
349 res = ta_join (two, one);
352 ir_type *one_type = one->res.type;
353 ir_type *two_type = two->res.type;
355 if (is_subtype (one_type, two_type)) {
358 } else if (is_subtype (two_type, one_type)) {
362 lset_t *one_closure = subtype_closure (one->res.type);
363 lset_t *two_closure = subtype_closure (two->res.type);
365 lset_append (one_closure, two_closure);
370 res = ta_types (one_closure);
377 assert (res && "no result");
384 static const char *ta_name (typalise_t *ta)
386 # define BUF_SIZE 1024
387 static char buf [BUF_SIZE];
389 int len = sprintf (buf, "[%d] ", ta->id);
392 case (type_invalid): { /* shut up, gcc */ }
394 len += sprintf (buf+len, "only ");
395 strncat (buf, get_type_name (ta->res.type), BUF_SIZE);
398 len += sprintf (buf+len, "one_of ");
400 ir_type *iter = lset_first (ta->res.types);
402 int size = BUF_SIZE - len - 1;
403 while ((NULL != iter) && (0 < size)) {
404 char *dest = strncat (buf, get_type_name (iter), size);
407 iter = lset_next (ta->res.types);
411 len += sprintf (buf+len, "poly ");
412 strncat (buf, get_type_name (ta->res.type), BUF_SIZE);
417 /* # undef BUF_SIZE */
419 # endif /* SHUT_UP_GCC */
422 Find out whether the given clazz uses the given implementation of a
423 method. Presumably, this is because clazz inherits the graph as
424 the implementation for a method.
426 static int uses_graph (ir_type *clazz, entity *meth, ir_graph *graph)
428 ir_type *g_clazz = get_entity_owner (meth);
429 int i, n_over, use = FALSE;
431 if (g_clazz == clazz) {
435 if (peculiarity_existent == get_entity_peculiarity (meth)) {
436 ir_graph *g_graph = get_entity_irg (meth);
438 if (g_graph != graph) {
443 /* else inherited or description */
444 n_over = get_entity_n_overwrittenby (meth); /* DOWN-wards */
445 for (i = 0; (i < n_over) && (!use); i ++) {
446 entity *over = get_entity_overwrittenby (meth, i);
448 use |= uses_graph (clazz, over, graph);
455 Check whether the given typalise_t includes the given type.
457 static int ta_supports (typalise_t *ta, ir_graph *graph)
460 case (type_invalid): { /* shut up, gcc */ }
463 lset_t *tps = get_owner_types (graph);
465 if (lset_contains (tps, ta->res.type)) {
474 entity *meth = get_irg_entity (graph);
475 ir_type *tp = get_entity_owner (meth);
476 int res = is_subtype (tp, ta->res.type);
481 res = uses_graph (ta->res.type, meth, graph);
487 ir_type *tp = get_entity_owner (get_irg_entity (graph));
489 return (lset_contains (ta->res.types, tp));
493 assert (0 && "invalid ta");
498 /* =========== WHAT ELSE ? =========== */
501 Helpers to typalise (ir_node*)
504 Find an approximation to the given load node's value's types
506 static typalise_t *typalise_call (ir_node *call)
510 typalise_t *res = NULL;
511 ir_node *call_ptr = get_Call_ptr (call);
513 if (iro_Sel == get_irn_opcode (call_ptr)) {
514 ent = get_Sel_entity (call_ptr);
515 } else if (iro_SymConst == get_irn_opcode (call_ptr)) {
516 if (get_SymConst_kind (call_ptr) == symconst_addr_ent) {
517 ent = get_SymConst_entity (call_ptr);
518 } else if (get_SymConst_kind (call_ptr) == symconst_addr_name) {
519 ident *id = get_SymConst_name (call_ptr);
520 const char *name = get_id_str (id);
521 if (0 == strcmp (name, "iro_Catch")) {
522 res = ta_type (java_lang_Throwable_tp);
527 fprintf (stdout, "%s: cannot handle Call[%li] (symconst_addr_name=\"%s\")\n",
528 __FUNCTION__, get_irn_node_nr (call),
530 cough_and_die (call_ptr);
531 } else if (get_SymConst_kind (call_ptr) == symconst_type_tag) {
532 fprintf (stdout, "%s: cannot handle Call[%li] (symconst_type_tag)\n",
533 __FUNCTION__, get_irn_node_nr (call));
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 ir_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 ir_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 ir_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 ++) {
765 phi_in = get_irn_n (node, i);
766 ta_in = typalise (phi_in);
769 ta = (NULL == ta) ? ta_in : ta_join (ta, ta_in);
777 ir_type *type = get_Alloc_type (node);
778 res = ta_exact (type);
782 /* presumably call (sel (proj (call))) */
783 ir_node *ptr = get_Call_ptr (node);
785 if (iro_Sel == get_irn_opcode (ptr)) {
786 meth = get_Sel_entity (ptr);
787 } else if (iro_SymConst == get_irn_opcode (ptr)) {
788 if (get_SymConst_kind (ptr) == symconst_addr_ent) {
789 meth = get_SymConst_entity (ptr);
791 meth = NULL; /* WTF? */
796 ir_type *tp = get_method_res_type ((ir_type*) meth, 0);
799 /* could be anything */
800 /* fprintf (stdout, "meth= (null)"); */
804 /* fprintf (stdout, "]\n"); */
808 case (iro_SymConst): {
809 if (get_SymConst_kind (node) == symconst_type_tag) {
810 ir_type *tp = get_SymConst_type (node);
813 } else if (get_SymConst_kind (node) == symconst_addr_ent) {
814 entity *ent = get_SymConst_entity (node);
815 ir_type *tp = get_entity_owner (ent);
817 while (is_Pointer_type (tp)) {
818 tp = get_pointer_points_to_type (tp);
821 assert (is_Class_type (tp));
823 res = ta_type (tp); /* can't use ta_exact */
824 } else if (get_SymConst_kind (node) == symconst_addr_name) {
825 /* oh, this is not a real call but a placeholder (exception stuff) */
826 fprintf (stdout, "%s (%s:%i): can't handle pseudo-call %s\n",
827 __FUNCTION__, __FILE__, __LINE__,
828 get_op_name (get_irn_op (node)));
832 fprintf (stdout, "%s (%s:%i): can't handle SymConst %s\n",
833 __FUNCTION__, __FILE__, __LINE__,
834 get_op_name (get_irn_op (node)));
840 /* presumably a NULL constant */
841 /* this also means we cannot handle calls against a NULL pointer. */
851 fprintf (stdout, "what's with %s?\n", get_op_name (get_irn_op (node)));
852 cough_and_die (node);
860 Initialise the Typalise module
862 void typalise_init (void)
864 if (NULL == java_lang_Throwable_tp) {
865 class_walk_super2sub (find_java_lang_Throwable, NULL, NULL);
867 /* make sure we have found it */
868 get_java_lang_Throwable ();
877 Revision 1.12 2006/01/13 21:54:02 beck
878 renamed all types 'type' to 'ir_type'
880 Revision 1.11 2005/05/13 16:35:14 beck
881 made (void) prototypes
882 removed unused fprintf arguments
884 Revision 1.10 2005/05/06 12:02:34 beck
885 added missing includes
888 Revision 1.9 2005/03/22 13:56:09 liekweg
889 "small" fix for exception b/d
891 Revision 1.8 2005/01/14 14:13:24 liekweg
894 Revision 1.7 2005/01/10 17:26:34 liekweg
895 fixup printfs, don't put environments on the stack
897 Revision 1.6 2005/01/05 14:25:54 beck
898 renames all is_x*_type() functions to is_X*_type() to prevent name clash with EDG fronten
900 Revision 1.5 2004/12/22 14:43:14 beck
901 made allocations C-like
903 Revision 1.4 2004/12/21 15:50:18 beck
904 removed C99 constructs
906 Revision 1.3 2004/12/02 16:17:51 beck
907 fixed config.h include
909 Revision 1.2 2004/10/22 09:53:10 liekweg
910 Correctly handle proj_args
912 Revision 1.1 2004/10/21 11:09:37 liekweg
913 Moved memwalk stuf into irmemwalk
914 Moved lset stuff into lset
915 Moved typalise stuff into typalise