5 * File name: ir/ana/ecg.c
6 * Purpose: Extended Call Graph
11 * Copyright: (c) 1999-2004 Universität Karlsruhe
12 * Licence: This file is protected by GPL - GNU GENERAL PUBLIC LICENSE.
20 Erweiterter Aufrufgraph.
25 /* #include "eset.h" */
35 # define BUF_SIZE 1024
39 #include <string.h> /* need memset */
45 /* Lists, err, Sets */
46 typedef struct lset_entry
49 struct lset_entry *next;
55 lset_entry_t *last; /* useful for lset_append */
56 lset_entry_t *curs; /* for lset_first/lset_next */
61 typedef enum typalise_kind_enum {
62 type_invalid = 0, /* invalid (only set at deletion time) */
63 type_exact = 1, /* this and only this type (res.type) */
64 type_types = 2, /* these types (res.types) */
65 type_type = 3 /* this type and sub types (res.type) */
68 typedef struct typalise
73 type *type; /* for kind == kind_exact and kind == kind_type */
74 lset_t *types; /* for kind == kind_types */
82 /* static int verbose = 0; */
83 static int do_typalise = 0;
89 /* mapping from method graphs (callR) to method graphs (lset_ts of callEds) */
90 /* static pmap *calls; */
91 static pmap *graph_infos;
93 /** Counters for ecg_ecg and friends */
94 static long _graphs = 0;
95 static long _calls = 0;
96 static long _allocs = 0;
98 static int _depth = 0;
99 static int _max_depth = 0;
101 static int _max_callEds = 0;
102 static entity* _max_callEds_callR = NULL;
104 static long ta_id = 0;
111 /* create a new lset */
112 static lset_t *lset_create (void)
114 lset_t *lset = xmalloc (sizeof (lset_t));
119 /* check whether the lset contains an entry for the given data */
120 static int lset_contains (lset_t *lset, void *data)
122 lset_entry_t *entry = lset->first;
124 while (NULL != entry) {
125 if (data == entry->data) {
135 /* check whether the given lset is empty */
136 static int lset_empty (lset_t *lset)
138 return (NULL == lset->first);
142 /* insert the data into the lset (unless there's an entry for it
144 static void lset_insert (lset_t *lset, void *data)
146 if (! lset_contains (lset, data)) {
147 lset_entry_t *entry = xmalloc (sizeof (lset_entry_t));
149 entry->next = lset->first;
152 if (NULL == lset->last) {
160 /* insert all entries from src into tgt */
161 static void lset_insert_all (lset_t *tgt, lset_t *src)
163 lset_entry_t *curs = src->first;
165 while (NULL != curs) {
166 lset_insert (tgt, curs->data);
172 /* append src to tgt. src is deallocated. */
173 static void lset_append (lset_t *tgt, lset_t *src)
175 assert (! tgt->last->next);
177 tgt->last->next = src->first;
178 tgt->last = src->last;
179 tgt->n_entries += src->n_entries;
181 memset (src, 0x00, sizeof (lset_t));
185 /* remove the entry for the given data element from the lset. return
186 TRUE iff it was on the list in the first place, FALSE else */
188 static int lset_remove (lset_t *lset, void *data)
190 lset_entry_t *entry = lset->first;
191 lset_entry_t *prev = NULL;
193 while (NULL != entry) {
194 if (data == entry->data) {
195 /* ok, dike it out */
197 if (NULL == prev) { /* ok, it's lset->first that needs diking */
198 lset->first = entry->next;
200 prev->next = entry->next;
203 memset (entry, 0x00, sizeof (lset_entry_t));
217 # endif /* def SHUT_UP_GCC */
218 /* prepare the given lset for an iteration. return the first element. */
219 static void *lset_first (lset_t *lset)
221 lset->curs = lset->first;
224 return (lset->first->data);
230 /* after calling lset_first, get the next element, if applicable, or
232 static void *lset_next (lset_t *lset)
234 lset->curs = lset->curs->next;
237 return (lset->curs->data);
243 /* say how many entries there are in the given lset */
244 static int lset_n_entries (lset_t *lset)
246 return (lset->n_entries);
249 /* deallocate the lset and all of its entries */
250 static void lset_destroy (lset_t *lset)
252 lset_entry_t *curs = lset->first;
254 while (NULL != curs) {
255 lset_entry_t *tmp = curs->next;
257 memset (curs, 0x00, sizeof (lset_entry_t));
263 memset (lset, 0x00, sizeof (lset_t));
267 /* ====================
269 ==================== */
271 Find out whether the given clazz uses the given implementation of a
272 method. Presumably, this is because clazz inherits the graph as
273 the implementation for a method.
275 static int uses_graph (type *clazz, entity *meth, ir_graph *graph)
277 type *g_clazz = get_entity_owner (meth);
279 if (g_clazz == clazz) {
283 if (peculiarity_existent == get_entity_peculiarity (meth)) {
284 ir_graph *g_graph = get_entity_irg (meth);
286 if (g_graph != graph) {
291 /* else inherited or description */
294 int n_over = get_entity_n_overwrittenby (meth); /* DOWN-wards */
296 for (i = 0; (i < n_over) && (!use); i ++) {
297 entity *over = get_entity_overwrittenby (meth, i);
299 use |= uses_graph (clazz, over, graph);
307 Find out whether otype is a subtype of stype.
308 Return non-zero iff otype is a subtype of stype.
310 static int is_subtype (type *otype, type *stype)
312 int n_sub = get_class_n_subtypes (stype);
316 if (otype == stype) {
320 for (i = 0; (!is_sub) && (i < n_sub); i ++) {
321 type *sub = get_class_subtype (stype, i);
323 is_sub |= is_subtype (otype, sub);
331 Compute the closure of all subtypes of otype (including otype
334 static void _collect_subtypes (type *otype, lset_t *set)
336 lset_insert (set, otype);
338 int n_sub = get_class_n_subtypes (otype);
341 for (i = 0; i < n_sub; i ++) {
342 type *sub = get_class_subtype (otype, i);
344 _collect_subtypes (sub, set);
348 static lset_t *subtype_closure (type *otype)
350 lset_t *set = lset_create ();
352 _collect_subtypes (otype, set);
358 Helper method for get_owner_types
360 static void _collect_owner_types (entity *method, ir_graph *graph, lset_t *tps)
362 /* search DOWNwards in clazz hierarchy */
364 if ((peculiarity_description == get_entity_peculiarity (method)) ||
365 (peculiarity_inherited == get_entity_peculiarity (method))) {
366 lset_insert (tps, get_entity_owner (method));
367 } else if (peculiarity_existent == get_entity_peculiarity (method)) {
368 ir_graph *ex_graph = get_entity_irg (method);
370 if ((NULL == ex_graph) || (ex_graph == graph)) {
371 /* wtf? they define the same graph again? well, whatever: */
372 lset_insert (tps, get_entity_owner (method));
374 /* aha: they define a new graph. can't have that, so bail out */
379 int n_over = get_entity_n_overwrittenby (method);
382 for (i = 0; i < n_over; i ++) {
383 entity *ometh = get_entity_overwrittenby (method, i);
385 _collect_owner_types (ometh, graph, tps);
391 Collect all classes that use the given implementation of a method.
393 static lset_t *get_owner_types (ir_graph *graph)
395 lset_t *tps = lset_create ();
396 entity *meth = get_irg_entity (graph);
398 _collect_owner_types (meth, graph, tps);
405 Convenience funcs to create a typalise_t
407 static typalise_t *ta_exact (type *tp)
409 typalise_t *ta = (typalise_t*) xmalloc (sizeof (typalise_t));
410 ta->kind = type_exact;
414 assert (is_class_type (tp));
419 static typalise_t *ta_types (lset_t *set)
421 typalise_t *ta = (typalise_t*) xmalloc (sizeof (typalise_t));
422 ta->kind = type_types;
429 static typalise_t *ta_type (type *tp)
431 typalise_t *ta = (typalise_t*) xmalloc (sizeof (typalise_t));
432 ta->kind = type_type;
436 assert (is_class_type (tp));
441 static void ta_delete (typalise_t *ta)
443 if (type_types == ta->kind) {
444 lset_destroy (ta->res.types);
445 ta->res.types = NULL;
450 ta->kind = type_invalid;
456 Join 'one' and 'two'; both args are deallocated, result is freshly
459 static typalise_t *ta_join (typalise_t *one, typalise_t *two)
461 typalise_t *res = NULL;
464 case (type_invalid): { /* shut up, gcc */ }
467 case (type_invalid): { /* shut up, gcc */ }
469 if (one->res.type == two->res.type) {
472 lset_t *set = lset_create ();
473 lset_insert (set, one->res.type);
474 lset_insert (set, two->res.type);
475 res = ta_types (set);
483 lset_insert (two->res.types, one->res.type);
489 if (is_subtype (one->res.type, two->res.type)) {
493 lset_t *closure = subtype_closure (two->res.type);
494 lset_insert (closure, one->res.type);
505 case (type_invalid): { /* shut up, gcc */ }
507 res = ta_join (two, one);
510 lset_insert_all (one->res.types, two->res.types);
516 lset_t *closure = subtype_closure (two->res.type);
517 lset_append (one->res.types, closure);
527 case (type_invalid): { /* shut up, gcc */ }
529 res = ta_join (two, one);
532 res = ta_join (two, one);
535 type *one_type = one->res.type;
536 type *two_type = two->res.type;
538 if (is_subtype (one_type, two_type)) {
541 } else if (is_subtype (two_type, one_type)) {
545 lset_t *one_closure = subtype_closure (one->res.type);
546 lset_t *two_closure = subtype_closure (two->res.type);
548 lset_append (one_closure, two_closure);
553 res = ta_types (one_closure);
560 assert (res && "no result");
567 static const char *ta_name (typalise_t *ta)
569 /* # define BUF_SIZE 1024 */
570 static char buf [BUF_SIZE];
572 int len = sprintf (buf, "[%d] ", ta->id);
575 case (type_invalid): { /* shut up, gcc */ }
577 len += sprintf (buf+len, "only ");
578 strncat (buf, get_type_name (ta->res.type), BUF_SIZE);
581 len += sprintf (buf+len, "one_of ");
583 type *iter = lset_first (ta->res.types);
585 int size = BUF_SIZE - len - 1;
586 while ((NULL != iter) && (0 < size)) {
587 char *dest = strncat (buf, get_type_name (iter), size);
590 iter = lset_next (ta->res.types);
594 len += sprintf (buf+len, "poly ");
595 strncat (buf, get_type_name (ta->res.type), BUF_SIZE);
600 /* # undef BUF_SIZE */
602 # endif /* SHUT_UP_GCC */
605 Check whether the given typalise_t includes the given type.
607 static int ta_supports (typalise_t *ta, ir_graph *graph)
610 case (type_invalid): { /* shut up, gcc */ }
613 lset_t *tps = get_owner_types (graph);
615 if (lset_contains (tps, ta->res.type)) {
624 entity *meth = get_irg_entity (graph);
625 type *tp = get_entity_owner (meth);
626 int res = is_subtype (tp, ta->res.type);
631 res = uses_graph (ta->res.type, meth, graph);
637 type *tp = get_entity_owner (get_irg_entity (graph));
639 return (lset_contains (ta->res.types, tp));
643 assert (0 && "invalid ta");
648 Given a set of graphs and a typalise_t, return the method (s) in
649 the set that are supported by the typalise_t. Also, deallocates
652 static lset_t *filter_for_ta (lset_t *set, typalise_t *ta)
654 lset_t *res = lset_create ();
655 ir_graph *curs = (ir_graph*) lset_first (set);
657 while (NULL != curs) {
658 if (ta_supports (ta, curs)) {
659 lset_insert (res, curs);
662 curs = lset_next (set);
672 Return a list containing all types of 'set' which are a subtype of 'type'.
674 static lset_t *filter_for_type (lset_t *set, type *stype)
676 type *curs = (type*) lset_first (set);
677 lset_t *lset = lset_create ();
679 while (NULL != curs) {
680 if (is_subtype (curs, stype)) {
681 lset_insert (lset, curs);
684 curs = lset_next (set);
691 Find an approximation to the given node's value's types
693 static typalise_t *typalise (ir_node*);
696 Find an approximation to the given proj node's value's types
698 static typalise_t *typalise_proj (ir_node *proj)
700 typalise_t *res = NULL;
701 ir_node *proj_in = get_Proj_pred (proj);
703 if (iro_Proj == get_irn_opcode (proj_in)) {
704 /* fprintf (stdout, "\tProj (Proj)\n"); */
706 proj_in = get_Proj_pred (proj_in);
707 if (iro_Start == get_irn_opcode (proj_in)) {
708 long n = get_Proj_proj (proj);
711 ir_graph *graph = get_irn_irg (proj);
712 entity *meth = get_irg_entity (graph);
713 type *tp = get_entity_owner (meth);
715 /* res = ta_exact (tp); */
716 res = ta_type (tp); /* TODO */
719 /* hey, even 'filtering' this NULL by the select of the actual
720 call is probably as "precise" as anything: */
723 } else if (iro_Call == get_irn_opcode (proj_in)) {
724 /* call result ... 'whatever' */
725 ir_node *call_ptr = get_Call_ptr (proj_in);
727 res = typalise (call_ptr);
729 fprintf (stdout, "\n Proj (Proj (%s)) not handled\n",
730 get_op_name (get_irn_op (proj_in)));
734 opcode op = get_irn_opcode (proj_in);
735 if ((iro_Load != op) && (iro_Alloc != op) && (iro_Call != op)) {
736 fprintf (stdout, "\n Proj (%s) not handled\n",
737 get_op_name (get_irn_op (proj_in)));
740 res = typalise (proj_in); /* everything else */
741 /* Proj (Load), Proj (New), Proj (Call) */
749 For the given ptr, do a quick check about what (class) types may be
752 static typalise_t *typalise (ir_node *node)
754 opcode op = get_irn_opcode (node);
755 typalise_t *res = NULL;
759 /* casts always succeed */
760 typalise_t *ta = NULL;
761 type *tp = get_Cast_type (node);
763 if (is_pointer_type (tp)) {
764 tp = get_pointer_points_to_type (tp);
766 assert (is_class_type (tp));
768 ta = typalise (get_Cast_op (node));
770 if (NULL == ta) { /* no type found */
772 } else if (type_exact == ta->kind) { /* one type found */
773 /* nothing (maybe check cast? */
774 } else if (type_type == ta->kind) { /* some types found */
775 if (is_subtype (tp, ta->res.type)) {
776 ta->res.type = tp; /* assume cast is correct */
778 /* should assert (is_subtype (ta->res.type, tp)) */
780 } else if (type_types == ta->kind) {
781 lset_t *ftp = filter_for_type (ta->res.types, tp);
782 lset_destroy (ta->res.types);
790 res = typalise_proj (node);
794 /* presumably it's call (load (ptr)) we're analyzing. */
795 ir_node *load_ptr = get_Load_ptr (node);
797 res = typalise (load_ptr);
802 /* it's call (sel (ptr)) or load (sel (ptr)) */
803 entity *ent = get_Sel_entity (node);
804 type *tp = get_entity_type (ent);
806 if (is_method_type (tp)) {
807 tp = get_entity_type (ent);
808 tp = get_method_res_type (tp, 0);
810 if (is_pointer_type (tp)) {
811 tp = get_pointer_points_to_type (tp);
815 } else if (is_class_type (tp)) {
816 tp = get_entity_type (ent);
818 if (is_pointer_type (tp)) {
819 tp = get_pointer_points_to_type (tp);
823 } else if (is_pointer_type (tp)) {
824 tp = get_pointer_points_to_type (tp);
827 assert (0 && "select not handled");
832 int n_ins = get_irn_arity (node);
834 ir_node *phi_in = NULL;
835 typalise_t *ta = NULL;
836 /* assert (0 && "Do we ever get here?"); */ /* apparently, we do. */
838 for (i = 0; i < n_ins; i ++) {
839 phi_in = get_irn_n (node, i);
840 ta = (NULL == ta) ? typalise (phi_in) : ta_join (ta, typalise (phi_in));
847 type *type = get_Alloc_type (node);
848 res = ta_exact (type);
852 /* presumably call (sel (proj (call))) */
853 ir_node *ptr = get_Call_ptr (node);
855 if (iro_Sel == get_irn_opcode (ptr)) {
856 meth = get_Sel_entity (ptr);
857 } else if (iro_SymConst == get_irn_opcode (ptr)) {
858 if (get_SymConst_kind (ptr) == symconst_addr_ent) {
859 meth = get_SymConst_entity (ptr);
861 meth = NULL; /* WTF? */
866 type *tp = get_method_res_type ((type*) meth, 0);
869 /* could be anything */
870 /* fprintf (stdout, "meth= (null)"); */
874 fprintf (stdout, "]\n");
878 case (iro_SymConst): {
879 if (get_SymConst_kind (node) == symconst_type_tag) {
880 type *tp = get_SymConst_type (node);
883 } else if (get_SymConst_kind (node) == symconst_addr_ent) {
884 entity *ent = get_SymConst_entity (node);
885 type *tp = get_entity_type (ent);
886 tp = get_pointer_points_to_type (tp);
887 assert (is_class_type (tp));
889 res = ta_type (tp); /* can't use ta_exact */
891 fprintf (stdout, "can't handle SymConst %s?\n",
892 get_op_name (get_irn_op (node)));
903 fprintf (stdout, "what's with %s?\n", get_op_name (get_irn_op (node)));
912 /* ====================
914 ==================== */
915 static void append_alloc (graph_info_t *ginfo, ir_node *alloc, type *tp)
917 alloc_info_t *ainfo = (alloc_info_t*) xmalloc (sizeof (alloc_info_t));
919 ainfo->graph = ginfo->graph;
920 ainfo->alloc = alloc;
923 ainfo->prev = ginfo->allocs;
924 ginfo->allocs = ainfo;
928 /* ====================
930 ==================== */
932 Append the given callEd to the given callEd info.
934 static callEd_info_t *append_callEd_info (callEd_info_t *ced, ir_graph *callEd)
936 callEd_info_t *nced = (callEd_info_t*) xmalloc (sizeof (sizeof (callEd_info_t)));
938 nced->callEd = callEd;
945 Append all callEd methods of the given (call) node to the given graph_info.
947 static void append_calls (graph_info_t *info, ir_node *call, lset_t *callEds)
949 call_info_t *cinfo = (call_info_t*) xmalloc (sizeof (call_info_t));
953 cinfo->prev = info->calls;
955 cinfo->callEds = NULL;
958 ir_graph *callEd = lset_first (callEds);
960 cinfo->callEds = append_callEd_info (cinfo->callEds, callEd);
962 callEd = lset_next (callEds);
967 Append the (single) callEd to the given (call) node of the given graph_info.
969 static void append_call (graph_info_t *info, ir_node *call, ir_graph *callEd)
971 call_info_t *cinfo = (call_info_t*) xmalloc (sizeof (call_info_t));
974 cinfo->prev = info->calls;
977 cinfo->callEds = append_callEd_info (cinfo->callEds, callEd);
981 Given a method, find the firm graph that implements that method.
982 Return NULL for abstract and native methods.
984 static ir_graph *_get_implementing_graph (entity *method)
986 ir_graph *graph = NULL;
988 /* What's up with the fenced out stuff in rta? */
989 if (peculiarity_existent == get_entity_peculiarity (method)) {
990 if (visibility_external_allocated == get_entity_visibility (method)) {
991 /* Todo: native implementation */
995 graph = get_entity_irg (get_SymConst_entity (get_atomic_ent_value (method)));
996 assert (graph && "no graph");
1000 } else if (0 && (peculiarity_description == get_entity_peculiarity (method))) {
1001 /* abstract --- can't find an implementation */
1002 graph = get_entity_irg (method);
1003 assert (!graph && "graph in abstract method");
1006 } else if ((peculiarity_description == get_entity_peculiarity (method)) ||
1007 (peculiarity_inherited == get_entity_peculiarity (method))) {
1008 /* search UPWARDS */
1010 int n_over = get_entity_n_overwrites (method);
1014 for (i = 0; (NULL == graph) && (i < n_over); i ++) {
1015 entity *over = get_entity_overwrites (method, i);
1017 graph = _get_implementing_graph (over);
1020 assert (0 && "invalid peculiarity");
1028 Collect all graphs of 'method' in the given set.
1030 static void _collect_implementing_graphs (entity *method, lset_t *set)
1032 /* search DOWN-wards in clazz hierarchy */
1034 int n_over = get_entity_n_overwrittenby (method);
1035 ir_graph *graph = get_entity_irg (method);
1037 if (NULL == graph) {
1038 graph = _get_implementing_graph (method);
1042 lset_insert (set, graph);
1045 for (i = 0; i < n_over; i ++) {
1046 entity *over = get_entity_overwrittenby (method, i);
1048 _collect_implementing_graphs (over, set);
1054 Collect all graphs that could possibly be executed when 'method' is called.
1056 static lset_t *get_implementing_graphs (entity *method, ir_node *select)
1058 lset_t *set = lset_create ();
1060 ir_graph *impl = _get_implementing_graph (method);
1063 lset_insert (set, impl);
1065 /* actually, abstract OR native */
1069 _collect_implementing_graphs (method, set);
1071 if (lset_empty (set)) {
1072 /* then it's a method which is only implemented natively, and we
1073 don' bother to analyse anything */
1077 /* void *tmp = lset_first (set); */
1078 int n_graphs = lset_n_entries (set);
1080 /* typalise select_in */
1082 ir_node *select_in = get_Sel_ptr (select);
1083 typalise_t *ta = typalise (select_in);
1084 assert (ta && "typalise failed (go figure)");
1086 /* const char *res = ta_name (ta); */
1088 /* fprintf (stdout, "typalyse res = %s\n", res); */
1090 if (1 != n_graphs) {
1091 set = filter_for_ta (set, ta);
1093 int n_filtered_graphs = lset_n_entries (set);
1096 fprintf (stdout, "%s: %02d %02d\n",
1100 n_graphs - n_filtered_graphs);
1102 n_graphs = n_filtered_graphs;
1106 if (n_graphs > _max_callEds) {
1107 _max_callEds = n_graphs;
1108 _max_callEds_callR = method;
1112 if (visibility_external_allocated != get_entity_visibility (method)) {
1113 if (0 == n_graphs) {
1114 /* fprintf (stdout, "no graphs for method %s\n", get_entity_name (method)); */
1115 assert (n_graphs && "no graphs for method");
1123 Action for the graph.
1125 static void ecg_calls_act (ir_node *node, void *env)
1127 opcode op = get_irn_opcode (node);
1128 graph_info_t *graph_info = (graph_info_t*) env;
1130 if (iro_Call == op) { /* CALL */
1132 ir_node *ptr = get_Call_ptr (node);
1135 if (iro_Sel == get_irn_opcode (ptr)) {
1136 ent = get_Sel_entity (ptr);
1137 lset_t *graphs = get_implementing_graphs (ent, ptr);
1139 append_calls (graph_info, node, graphs);
1140 } else if (iro_SymConst == get_irn_opcode (ptr)) {
1141 if (get_SymConst_kind (ptr) == symconst_addr_ent) {
1142 ent = get_SymConst_entity (ptr);
1143 ir_graph *graph = get_entity_irg (ent);
1146 append_call (graph_info, node, graph);
1148 /* it's an externally allocated thingy */
1150 } else if (get_SymConst_kind (ptr) == symconst_addr_name) {
1151 /* If this SymConst refers to a method the method is external_visible
1152 and therefore must be considered live anyways. */
1153 if (get_SymConst_name (ptr) != new_id_from_str ("iro_Catch")) {
1154 assert (ent && "couldn't determine entity of call to symConst");
1157 /* other symconst. */
1158 assert (0 && "This SymConst can not be an address for a method call.");
1161 /* STRANGE, no less ... */
1164 assert (0 && "Unexpected address expression");
1166 } else if (iro_Alloc == op) {
1167 type *tp = get_Alloc_type (node);
1168 const char *name = get_type_name (tp);
1170 append_alloc (graph_info, node, tp);
1172 fprintf (stdout, "NEW \"%s\"\n", name);
1177 Collect called graphs for the given graph.
1179 static void ecg_fill_graph_calls (ir_graph *graph)
1181 graph_info_t *graph_info = (graph_info_t*) xmalloc (sizeof (graph_info_t));
1183 graph_info->graph = graph;
1184 graph_info->calls = NULL;
1185 graph_info->ecg_seen = 0;
1187 /* entity *method = get_irg_entity (graph); */
1188 /* type *clazz = get_entity_owner (method); */
1190 irg_walk_graph (graph, ecg_calls_act, NULL, graph_info);
1192 pmap_insert (graph_infos, graph, graph_info);
1196 For each graph, collect called graphs, and enter them into calls.
1198 static void ecg_fill_calls (void)
1202 for (i = 0; i < get_irp_n_irgs (); i++) {
1203 ir_graph *graph = get_irp_irg (i);
1205 ecg_fill_graph_calls (graph);
1209 /* ====================
1211 ==================== */
1214 get the call infos for the given graph
1216 graph_info_t *ecg_get_info (ir_graph *graph)
1218 graph_info_t *ginfo = (graph_info_t*) pmap_get (graph_infos, graph);
1220 assert (ginfo && "no info for graph");
1228 Dump the given graph and it's calls and it's calls callEds to the given file.
1230 static int ecg_ecg_graph (FILE *dot, ir_graph *graph)
1232 const char *name = get_irg_entity (graph) ?
1233 get_entity_name (get_irg_entity (graph)) : "noEntity";
1235 (get_entity_stickyness
1236 (get_irg_entity (graph)) == stickyness_sticky) ?
1237 "red" : "lightyellow";
1239 graph_info_t *ginfo = (graph_info_t*) pmap_get (graph_infos, graph);
1241 if (0 != ginfo->ecg_seen) {
1242 fprintf (dot, "\t/* recursive call to \"%s\" (%d) */\n",
1243 name, (int) ginfo->ecg_seen);
1245 fprintf (dot, "\t/* recursive call to \"%s\" (0x%08x) */\n",
1248 return (ginfo->ecg_seen);
1251 assert (0L <= _graphs);
1253 const int graph_no = _graphs ++;
1254 ginfo->ecg_seen = graph_no;
1256 fprintf (dot, "\t/* Graph of \"%s.%s\" */\n",
1257 get_type_name (get_entity_owner (get_irg_entity (graph))),
1259 fprintf (dot, "\tgraph_%i [label=\"%s\\l%s\", color=\"%s\"];\n",
1261 get_type_name (get_entity_owner (get_irg_entity (graph))),
1264 fprintf (dot, "\n");
1266 if (visibility_external_allocated ==
1267 get_entity_visibility (get_irg_entity (graph))) {
1268 fprintf (dot, "\t/* graph \"%s\" is external */\n", name);
1273 call_info_t *cinfo = ginfo->calls;
1274 while (NULL != cinfo) {
1275 ir_node *call = cinfo->call;
1276 callEd_info_t *ced = cinfo->callEds;
1277 const int call_no = _calls ++;
1279 fprintf (dot, "\t/* Call 0x%08x */\n", (int) call);
1280 fprintf (dot, "\tcall_%i [label=\"call\\l0x%08x\"];\n",
1281 call_no, (int) call);
1282 fprintf (dot, "\tgraph_%i -> call_%i [color=\"black\"];\n", graph_no, call_no);
1284 while (NULL != ced) {
1285 ir_graph *callEd_graph = ced->callEd;
1286 const int callEd_no = ecg_ecg_graph (dot, callEd_graph);
1287 const char *callEd_name = get_irg_entity (callEd_graph) ?
1288 get_entity_name (get_irg_entity (callEd_graph)) : "noEntity";
1289 const char *direction = (callEd_no <= graph_no) ? "forward" : "forward";
1290 const char *callEd_color = (callEd_no <= graph_no) ? "red" : "black";
1292 fprintf (dot, "\t/* Call from graph \"%s\" to graph \"%s\" */\n",
1295 /* Check for recursive calls */
1296 /* if (callEd_no > graph_no) */ { /* do recursive calls (for now) */
1297 fprintf (dot, "\tcall_%i -> graph_%i [color=\"%s\", dir=\"%s\"];\n",
1298 call_no, callEd_no, callEd_color, direction);
1303 } /* done all calEds (call) */
1305 cinfo = cinfo->prev;
1306 } /* done all calls (graph) */
1308 /* now the allocs */
1309 alloc_info_t *ainfo = ginfo->allocs;
1311 fprintf (dot, "\t/* now the allocs */\n");
1313 fprintf (dot, "\t/* no allocs */\n");
1316 while (NULL != ainfo) {
1317 ir_node *alloc = ainfo->alloc;
1318 const char *name = get_type_name (ainfo->tp);
1319 const char *color = "red1";
1321 /* if (0 == ginfo->allocs_seen) { */
1323 fprintf (dot, "\talloc_0x%08x_%i [label=\"%s\", color=\"%s\"]\n",
1324 (int) alloc, graph_no, name, color);
1327 fprintf (dot, "\tgraph_%i -> alloc_0x%08x_%i\n", graph_no, (int) alloc, graph_no);
1329 ainfo = ainfo->prev;
1332 if (0 == ginfo->allocs_seen) {
1333 ginfo->allocs_seen = 1;
1336 fprintf (dot, "\t/* done with graph of \"%s\" */\n\n", name);
1339 ginfo->ecg_seen = 0;
1345 Count how many nodes the ECG will have
1347 static char spaces [BUF_SIZE];
1349 static void ecg_ecg_count (ir_graph *graph)
1351 graph_info_t *ginfo = (graph_info_t*) pmap_get (graph_infos, graph);
1353 if (0 != ginfo->ecg_seen) {
1358 if (_depth > _max_depth) {
1359 _max_depth = _depth;
1362 fprintf (stdout, "_max_depth = %i\n", _max_depth);
1363 fprintf (stdout, "\tn_graphs: %i\n", _graphs);
1367 assert (0L <= _graphs);
1370 if (0 == (_graphs % 1000000)) {
1371 fprintf (stdout, "\tn_graphs: %i\n", _graphs);
1372 fprintf (stdout, "_depth = %i\n", _depth);
1376 const int graph_no = _graphs ++;
1377 ginfo->ecg_seen = graph_no;
1379 fprintf (stdout, "%sMethod \"%s.%s\"\n",
1380 spaces + BUF_SIZE - _depth,
1381 get_type_name (get_entity_owner (get_irg_entity (graph))),
1382 get_entity_name (get_irg_entity (graph)));
1384 call_info_t *cinfo = ginfo->calls;
1385 while (NULL != cinfo) {
1387 callEd_info_t *ced = cinfo->callEds;
1389 fprintf (stdout, "%sCall \"0x%08x\"\n",
1390 spaces + BUF_SIZE - _depth,
1393 while (NULL != ced) {
1394 ir_graph *callEd_graph = ced->callEd;
1396 fprintf (stdout, "%sCall Target \"%s.%s\"\n",
1397 spaces + BUF_SIZE - _depth,
1398 get_type_name (get_entity_owner (get_irg_entity (callEd_graph))),
1399 get_entity_name (get_irg_entity (callEd_graph)));
1401 ecg_ecg_count (callEd_graph);
1404 } /* done all calEds (call) */
1405 cinfo = cinfo->prev;
1406 } /* done all calls (graph) */
1408 ginfo->ecg_seen = 0;
1412 /* ====================
1414 ==================== */
1417 Initialise our data structures.
1419 void ecg_init (int typalise)
1421 do_typalise = typalise;
1423 graph_infos = pmap_create ();
1435 for (i = 0; i < get_irp_n_irgs (); i++) {
1436 ir_graph *graph = get_irp_irg (i);
1438 graph_info_t *info = pmap_get (graph_infos, graph);
1439 call_info_t *cinfo = info->calls;
1441 while (NULL != cinfo) {
1442 free (cinfo->callEds);
1445 callEd_info_t *ced = cinfo->callEds;
1447 while (NULL != ced) {
1448 callEd_info_t *nced = ced->prev;
1455 /* Todo: delete callEds */
1456 cinfo->callEds = NULL;
1459 cinfo = cinfo->prev;
1463 pmap_insert (graph_infos, graph, NULL);
1467 pmap_destroy (graph_infos);
1469 /* BEGIN mild paranoia mode */
1471 /* END mild paranoia mode */
1475 Show what we have found.
1481 FILE *dot = fopen ("calls.dot", "w");
1483 fprintf (dot, "digraph \"calls\" {\n");
1484 fprintf (dot, "\tnode [shape = \"record\", style = \"filled\"];\n");
1485 fprintf (dot, "\tedge [color = \"black\"];\n");
1486 fprintf (dot, "\n");
1487 fprintf (dot, "\tsize = \"11, 7\";\n");
1488 fprintf (dot, "\trotate = \"90\";\n");
1489 fprintf (dot, "\tratio = \"fill\";\n");
1490 fprintf (dot, "\trankdir = \"LR\";\n");
1491 fprintf (dot, "\n");
1493 for (i = 0; i < get_irp_n_irgs (); i++) {
1494 ir_graph *graph = get_irp_irg (i);
1495 graph_info_t *info = (graph_info_t*) pmap_get (graph_infos, graph);
1497 const char *name = get_irg_entity (graph) ?
1498 get_entity_name (get_irg_entity (graph)) : "noEntity";
1500 const char *oname = get_type_name
1501 (get_entity_owner (get_irg_entity (graph)));
1504 (get_entity_stickyness
1505 (get_irg_entity (graph)) == stickyness_sticky) ?
1506 "red3" : "lightyellow";
1508 fprintf (dot, "\t/* graph_0x%08x (\"%s\") */\n", (int) graph, name);
1510 "\tgraph_0x%08x [label=\"%s\\l%s\", color=\"%s\"];\n",
1511 (int) graph, oname, name, color);
1512 fprintf (dot, "\n");
1514 call_info_t *cinfo = info->calls;
1516 fprintf (dot, "\t/* now the calls */\n");
1518 fprintf (dot, "\t/* no calls, nothing to see, move along! */\n");
1521 while (NULL != cinfo) {
1522 ir_node *call = cinfo->call;
1524 fprintf (dot, "\t/* call_0x%08x */\n", (int) call);
1525 fprintf (dot, "\tcall_0x%08x [label=\"call\\l0x%08x\"];\n",
1526 (int) call, (int) call);
1527 fprintf (dot, "\tgraph_0x%08x -> call_0x%08x;\n",
1528 (int) graph, (int) call);
1530 callEd_info_t *ced = cinfo->callEds;
1531 while (NULL != ced) {
1532 fprintf (dot, "\tcall_0x%08x -> graph_0x%08x;\n",
1533 (int) call, (int) ced->callEd);
1536 fprintf (dot, "\n");
1538 cinfo = cinfo->prev;
1540 fprintf (dot, "\n");
1542 alloc_info_t *ainfo = info->allocs;
1544 fprintf (dot, "\t/* now the allocs */\n");
1546 fprintf (dot, "\t/* no allocs */\n");
1550 while (NULL != ainfo) {
1551 ir_node *alloc = ainfo->alloc;
1552 const char *name = get_type_name (ainfo->tp);
1553 const char *color = "red1";
1555 fprintf (dot, "\talloc_0x%08x [label=\"%s\", color=\"%s\"]\n",
1556 (int) alloc, name, color);
1557 fprintf (dot, "\tgraph_0x%08x -> alloc_0x%08x\n",
1558 (int) graph, (int) alloc);
1560 ainfo = ainfo->prev;
1563 fprintf (dot, "}\n");
1566 fprintf (stdout, " max_callEds: %i\n", _max_callEds);
1567 fprintf (stdout, " max_callEds_callR: \"%s\"\n",
1568 get_entity_name (_max_callEds_callR));
1576 Experimental: Print the ecg
1583 ir_graph *main_graph = get_irp_main_irg ();
1586 memset (spaces, '.', BUF_SIZE);
1587 spaces [BUF_SIZE-1] = '\0';
1589 ecg_ecg_count (main_graph);
1590 fprintf (stdout, "n_graphs: %i\n", _graphs);
1591 fprintf (stdout, "max_depth = %i\n", _max_depth);
1599 FILE *dot = fopen ("ecg.dot", "w");
1601 fprintf (dot, "digraph \"ecg\" {\n");
1602 fprintf (dot, "\tnode [shape = \"record\", style = \"filled\"];\n");
1603 fprintf (dot, "\tedge [color = \"black\"];\n");
1604 fprintf (dot, "\n");
1605 fprintf (dot, "\tsize = \"11, 7\";\n");
1606 fprintf (dot, "\trotate = \"90\";\n");
1607 fprintf (dot, "\tratio = \"fill\";\n");
1608 fprintf (dot, "\trankdir = \"LR\";\n");
1609 fprintf (dot, "\n");
1611 /* ir_graph *main_graph = get_irp_main_irg (); */
1612 ecg_ecg_graph (dot, main_graph);
1614 fprintf (dot, "\t/* Grand Total: */\n");
1615 fprintf (dot, "\t/* calls: %i */\n", (int) _calls);
1616 fprintf (dot, "\t/* graphs: %i */\n", (int) _graphs);
1617 fprintf (dot, "\t/* allocs: %i */\n", (int) _allocs);
1618 fprintf (dot, "\t/* (sales tax not included) */\n");
1620 fprintf (dot, "}\n");
1629 Revision 1.1 2004/10/20 14:59:41 liekweg
1630 Added ana2, added ecg and pto
1632 Revision 1.6 2004/10/18 12:47:19 liekweg
1635 Revision 1.5 2004/10/14 11:31:28 liekweg
1638 Revision 1.4 2004/10/12 11:02:01 liekweg