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*);
52 Ctors, Dtors for typalise_t-s
54 static typalise_t *ta_exact (type *tp)
56 typalise_t *ta = xmalloc (sizeof (typalise_t));
57 ta->kind = type_exact;
61 assert (is_Class_type (tp));
66 static typalise_t *ta_types (lset_t *set)
68 typalise_t *ta = xmalloc (sizeof (typalise_t));
69 ta->kind = type_types;
76 static typalise_t *ta_type (type *tp)
78 typalise_t *ta = xmalloc (sizeof (typalise_t));
83 assert (is_Class_type (tp));
88 static void ta_delete (typalise_t *ta)
90 if (type_types == ta->kind) {
91 lset_destroy (ta->res.types);
97 ta->kind = type_invalid;
103 Helpers for inheritance, overwriting and stuff
106 Find out whether otype is a subtype of stype.
107 Return non-zero iff otype is a subtype of stype.
109 static int is_subtype (type *otype, type *stype)
111 int n_sub = get_class_n_subtypes (stype);
115 if (otype == stype) {
119 for (i = 0; (!is_sub) && (i < n_sub); i ++) {
120 type *sub = get_class_subtype (stype, i);
122 is_sub |= is_subtype (otype, sub);
131 Compute the closure of all subtypes of otype (including otype
134 static void _collect_subtypes (type *otype, lset_t *set)
138 lset_insert (set, otype);
140 n_sub = get_class_n_subtypes (otype);
141 for (i = 0; i < n_sub; i ++) {
142 type *sub = get_class_subtype (otype, i);
144 _collect_subtypes (sub, set);
148 static lset_t *subtype_closure (type *otype)
150 lset_t *set = lset_create ();
152 _collect_subtypes (otype, set);
158 Helper method for get_owner_types
160 static void _collect_owner_types (entity *method, ir_graph *graph, lset_t *tps)
164 /* search DOWNwards in clazz hierarchy */
166 if ((peculiarity_description == get_entity_peculiarity (method)) ||
167 (peculiarity_inherited == get_entity_peculiarity (method))) {
168 lset_insert (tps, get_entity_owner (method));
169 } else if (peculiarity_existent == get_entity_peculiarity (method)) {
170 ir_graph *ex_graph = get_entity_irg (method);
172 if ((NULL == ex_graph) || (ex_graph == graph)) {
173 /* wtf? they define the same graph again? well, whatever: */
174 lset_insert (tps, get_entity_owner (method));
176 /* aha: they define a new graph. can't have that, so bail out */
181 n_over = get_entity_n_overwrittenby (method);
182 for (i = 0; i < n_over; i ++) {
183 entity *ometh = get_entity_overwrittenby (method, i);
185 _collect_owner_types (ometh, graph, tps);
191 Collect all classes that use the given implementation of a method.
193 static lset_t *get_owner_types (ir_graph *graph)
195 lset_t *tps = lset_create ();
196 entity *meth = get_irg_entity (graph);
198 _collect_owner_types (meth, graph, tps);
204 Return a list containing all types of 'set' which are a subtype of 'type'.
206 static lset_t *filter_for_type (lset_t *set, type *stype)
208 type *curs = (type*) lset_first (set);
209 lset_t *lset = lset_create ();
211 while (NULL != curs) {
212 if (is_subtype (curs, stype)) {
213 lset_insert (lset, curs);
216 curs = lset_next (set);
226 Join 'one' and 'two'; both args are deallocated, result is freshly
229 static typalise_t *ta_join (typalise_t *one, typalise_t *two)
231 typalise_t *res = NULL;
234 case (type_invalid): { /* shut up, gcc */ }
237 case (type_invalid): { /* shut up, gcc */ }
239 if (one->res.type == two->res.type) {
242 lset_t *set = lset_create ();
243 lset_insert (set, one->res.type);
244 lset_insert (set, two->res.type);
245 res = ta_types (set);
253 lset_insert (two->res.types, one->res.type);
259 if (is_subtype (one->res.type, two->res.type)) {
263 lset_t *closure = subtype_closure (two->res.type);
264 lset_insert (closure, one->res.type);
275 case (type_invalid): { /* shut up, gcc */ }
277 res = ta_join (two, one);
280 lset_insert_all (one->res.types, two->res.types);
286 lset_t *closure = subtype_closure (two->res.type);
287 lset_append (one->res.types, closure);
297 case (type_invalid): { /* shut up, gcc */ }
299 res = ta_join (two, one);
302 res = ta_join (two, one);
305 type *one_type = one->res.type;
306 type *two_type = two->res.type;
308 if (is_subtype (one_type, two_type)) {
311 } else if (is_subtype (two_type, one_type)) {
315 lset_t *one_closure = subtype_closure (one->res.type);
316 lset_t *two_closure = subtype_closure (two->res.type);
318 lset_append (one_closure, two_closure);
323 res = ta_types (one_closure);
330 assert (res && "no result");
337 static const char *ta_name (typalise_t *ta)
339 # define BUF_SIZE 1024
340 static char buf [BUF_SIZE];
342 int len = sprintf (buf, "[%d] ", ta->id);
345 case (type_invalid): { /* shut up, gcc */ }
347 len += sprintf (buf+len, "only ");
348 strncat (buf, get_type_name (ta->res.type), BUF_SIZE);
351 len += sprintf (buf+len, "one_of ");
353 type *iter = lset_first (ta->res.types);
355 int size = BUF_SIZE - len - 1;
356 while ((NULL != iter) && (0 < size)) {
357 char *dest = strncat (buf, get_type_name (iter), size);
360 iter = lset_next (ta->res.types);
364 len += sprintf (buf+len, "poly ");
365 strncat (buf, get_type_name (ta->res.type), BUF_SIZE);
370 /* # undef BUF_SIZE */
372 # endif /* SHUT_UP_GCC */
375 Find out whether the given clazz uses the given implementation of a
376 method. Presumably, this is because clazz inherits the graph as
377 the implementation for a method.
379 static int uses_graph (type *clazz, entity *meth, ir_graph *graph)
381 type *g_clazz = get_entity_owner (meth);
382 int i, n_over, use = FALSE;
384 if (g_clazz == clazz) {
388 if (peculiarity_existent == get_entity_peculiarity (meth)) {
389 ir_graph *g_graph = get_entity_irg (meth);
391 if (g_graph != graph) {
396 /* else inherited or description */
397 n_over = get_entity_n_overwrittenby (meth); /* DOWN-wards */
398 for (i = 0; (i < n_over) && (!use); i ++) {
399 entity *over = get_entity_overwrittenby (meth, i);
401 use |= uses_graph (clazz, over, graph);
408 Check whether the given typalise_t includes the given type.
410 static int ta_supports (typalise_t *ta, ir_graph *graph)
413 case (type_invalid): { /* shut up, gcc */ }
416 lset_t *tps = get_owner_types (graph);
418 if (lset_contains (tps, ta->res.type)) {
427 entity *meth = get_irg_entity (graph);
428 type *tp = get_entity_owner (meth);
429 int res = is_subtype (tp, ta->res.type);
434 res = uses_graph (ta->res.type, meth, graph);
440 type *tp = get_entity_owner (get_irg_entity (graph));
442 return (lset_contains (ta->res.types, tp));
446 assert (0 && "invalid ta");
451 /* =========== WHAT ELSE ? =========== */
454 Helper to typalise (ir_node*)
457 Find an approximation to the given proj node's value's types
459 static typalise_t *typalise_proj (ir_node *proj)
461 typalise_t *res = NULL;
462 ir_node *proj_in = get_Proj_pred (proj);
464 if (iro_Proj == get_irn_opcode (proj_in)) {
465 /* fprintf (stdout, "\tProj (Proj)\n"); */
467 proj_in = get_Proj_pred (proj_in);
468 if (iro_Start == get_irn_opcode (proj_in)) {
469 ir_graph *graph = get_irn_irg (proj);
470 entity *meth = get_irg_entity (graph);
472 long n = get_Proj_proj (proj);
476 type *tp = get_entity_owner (meth);
478 /* res = ta_exact (tp); */
479 res = ta_type (tp); /* TODO */
482 type *tp = get_method_param_type (get_entity_type (meth), n);
483 if (is_Pointer_type (tp)) {
484 tp = get_pointer_points_to_type (tp);
489 } else if (iro_Call == get_irn_opcode (proj_in)) {
490 /* call result ... 'whatever' */
491 /* hey, this is redundant (or the check for iro_Call further down) */
492 ir_node *call_ptr = get_Call_ptr (proj_in);
494 res = typalise (call_ptr);
496 fprintf (stdout, "\n Proj (Proj (%s)) not handled\n",
497 get_op_name (get_irn_op (proj_in)));
501 opcode op = get_irn_opcode (proj_in);
502 if ((iro_Load != op) && (iro_Alloc != op) && (iro_Call != op)) {
503 fprintf (stdout, "\n Proj (%s) not handled\n",
504 get_op_name (get_irn_op (proj_in)));
507 res = typalise (proj_in); /* everything else */
508 /* Proj (Load), Proj (New), Proj (Call) */
520 Given a set of graphs and a typalise_t, return the method (s) in
521 the set that are supported by the typalise_t. Also, deallocates
524 lset_t *filter_for_ta (lset_t *set, typalise_t *ta)
526 lset_t *res = lset_create ();
527 ir_graph *curs = (ir_graph*) lset_first (set);
529 while (NULL != curs) {
530 if (ta_supports (ta, curs)) {
531 lset_insert (res, curs);
534 curs = lset_next (set);
543 For the given ptr, do a quick check about what (class) types may be
546 typalise_t *typalise (ir_node *node)
548 opcode op = get_irn_opcode (node);
549 typalise_t *res = NULL;
553 /* casts always succeed */
554 typalise_t *ta = NULL;
555 type *tp = get_Cast_type (node);
557 if (is_Pointer_type (tp)) {
558 tp = get_pointer_points_to_type (tp);
560 assert (is_Class_type (tp));
562 ta = typalise (get_Cast_op (node));
564 if (NULL == ta) { /* no type found */
566 } else if (type_exact == ta->kind) { /* one type found */
567 /* nothing (maybe check cast? */
568 } else if (type_type == ta->kind) { /* some types found */
569 if (is_subtype (tp, ta->res.type)) {
570 ta->res.type = tp; /* assume cast is correct */
572 /* should assert (is_subtype (ta->res.type, tp)) */
574 } else if (type_types == ta->kind) {
575 lset_t *ftp = filter_for_type (ta->res.types, tp);
576 lset_destroy (ta->res.types);
584 res = typalise_proj (node);
588 ir_node *load_ptr = get_Load_ptr (node);
590 res = typalise (load_ptr);
595 /* it's call (sel (ptr)) or load (sel (ptr)) */
596 entity *ent = get_Sel_entity (node);
597 type *tp = get_entity_type (ent);
599 if (is_Method_type (tp)) {
600 tp = get_entity_type (ent);
601 tp = get_method_res_type (tp, 0);
603 if (is_Pointer_type (tp)) {
604 tp = get_pointer_points_to_type (tp);
608 } else if (is_Class_type (tp)) {
609 tp = get_entity_type (ent);
611 if (is_Pointer_type (tp)) {
612 tp = get_pointer_points_to_type (tp);
616 } else if (is_Pointer_type (tp)) {
617 tp = get_pointer_points_to_type (tp);
620 assert (0 && "select not handled");
625 int n_ins = get_irn_arity (node);
627 ir_node *phi_in = NULL;
628 typalise_t *ta = NULL;
629 /* assert (0 && "Do we ever get here?"); */ /* apparently, we do. */
631 for (i = 0; i < n_ins; i ++) {
632 phi_in = get_irn_n (node, i);
633 ta = (NULL == ta) ? typalise (phi_in) : ta_join (ta, typalise (phi_in));
640 type *type = get_Alloc_type (node);
641 res = ta_exact (type);
645 /* presumably call (sel (proj (call))) */
646 ir_node *ptr = get_Call_ptr (node);
648 if (iro_Sel == get_irn_opcode (ptr)) {
649 meth = get_Sel_entity (ptr);
650 } else if (iro_SymConst == get_irn_opcode (ptr)) {
651 if (get_SymConst_kind (ptr) == symconst_addr_ent) {
652 meth = get_SymConst_entity (ptr);
654 meth = NULL; /* WTF? */
659 type *tp = get_method_res_type ((type*) meth, 0);
662 /* could be anything */
663 /* fprintf (stdout, "meth= (null)"); */
667 fprintf (stdout, "]\n");
671 case (iro_SymConst): {
672 if (get_SymConst_kind (node) == symconst_type_tag) {
673 type *tp = get_SymConst_type (node);
676 } else if (get_SymConst_kind (node) == symconst_addr_ent) {
677 entity *ent = get_SymConst_entity (node);
678 type *tp = get_entity_type (ent);
679 tp = get_pointer_points_to_type (tp);
680 assert (is_Class_type (tp));
682 res = ta_type (tp); /* can't use ta_exact */
684 fprintf (stdout, "%s (%s:%i): can't handle SymConst %s?\n",
685 __FUNCTION__, __FILE__, __LINE__,
686 get_op_name (get_irn_op (node)));
697 fprintf (stdout, "what's with %s?\n", get_op_name (get_irn_op (node)));
711 Revision 1.8 2005/01/14 14:13:24 liekweg
714 Revision 1.7 2005/01/10 17:26:34 liekweg
715 fixup printfs, don't put environments on the stack
717 Revision 1.6 2005/01/05 14:25:54 beck
718 renames all is_x*_type() functions to is_X*_type() to prevent name clash with EDG fronten
720 Revision 1.5 2004/12/22 14:43:14 beck
721 made allocations C-like
723 Revision 1.4 2004/12/21 15:50:18 beck
724 removed C99 constructs
726 Revision 1.3 2004/12/02 16:17:51 beck
727 fixed config.h include
729 Revision 1.2 2004/10/22 09:53:10 liekweg
730 Correctly handle proj_args
732 Revision 1.1 2004/10/21 11:09:37 liekweg
733 Moved memwalk stuf into irmemwalk
734 Moved lset stuff into lset
735 Moved typalise stuff into typalise