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
43 /* Lists, err, Sets */
44 typedef struct lset_entry
47 struct lset_entry *next;
53 lset_entry_t *last; /* useful for lset_append */
54 lset_entry_t *curs; /* for lset_first/lset_next */
59 typedef enum typalise_kind_enum {
60 type_invalid = 0, /* invalid (only set at deletion time) */
61 type_exact = 1, /* this and only this type (res.type) */
62 type_types = 2, /* these types (res.types) */
63 type_type = 3 /* this type and sub types (res.type) */
66 typedef struct typalise
71 type *type; /* for kind == kind_exact and kind == kind_type */
72 lset_t *types; /* for kind == kind_types */
80 static int verbose = 0;
81 static int do_typalise = 0;
87 /* mapping from method graphs (callR) to method graphs (lset_ts of callEds) */
88 /* static pmap *calls; */
89 static pmap *graph_infos;
91 /** Counters for ecg_ecg and friends */
92 static long _graphs = 0;
93 static long _calls = 0;
95 static int _depth = 0;
96 static int _max_depth = 0;
98 static int _max_callEds = 0;
99 static entity* _max_callEds_callR = NULL;
101 static long ta_id = 0;
103 /* ====================
105 ==================== */
106 /* create a new lset */
107 static lset_t *lset_create ()
109 lset_t *lset = xmalloc (sizeof (lset_t));
114 /* check whether the lset contains an entry for the given data */
115 static int lset_contains (lset_t *lset, void *data)
117 lset_entry_t *entry = lset->first;
119 while (NULL != entry) {
120 if (data == entry->data) {
130 /* check whether the given lset is empty */
131 static int lset_empty (lset_t *lset)
133 return (NULL == lset->first);
137 /* insert the data into the lset (unless there's an entry for it
139 static void lset_insert (lset_t *lset, void *data)
141 if (! lset_contains (lset, data)) {
142 lset_entry_t *entry = xmalloc (sizeof (lset_entry_t));
144 entry->next = lset->first;
147 if (NULL == lset->last) {
155 /* insert all entries from src into tgt */
156 static void lset_insert_all (lset_t *tgt, lset_t *src)
158 lset_entry_t *curs = src->first;
160 while (NULL != curs) {
161 lset_insert (tgt, curs->data);
167 /* append src to tgt. src is deallocated. */
168 static void lset_append (lset_t *tgt, lset_t *src)
170 assert (! tgt->last->next);
172 tgt->last->next = src->first;
173 tgt->last = src->last;
174 tgt->n_entries += src->n_entries;
176 memset (src, 0x00, sizeof (lset_t));
180 /* remove the entry for the given data element from the lset. return
181 TRUE iff it was on the list in the first place, FALSE else */
182 static int lset_remove (lset_t *lset, void *data)
184 lset_entry_t *entry = lset->first;
185 lset_entry_t *prev = NULL;
187 while (NULL != entry) {
188 if (data == entry->data) {
189 /* ok, dike it out */
191 if (NULL == prev) { /* ok, it's lset->first that needs diking */
192 lset->first = entry->next;
194 prev->next = entry->next;
197 memset (entry, 0x00, sizeof (lset_entry_t));
212 /* prepare the given lset for an iteration. return the first element. */
213 static void *lset_first (lset_t *lset)
215 lset->curs = lset->first;
218 return (lset->first->data);
224 /* after calling lset_first, get the next element, if applicable, or
226 static void *lset_next (lset_t *lset)
228 lset->curs = lset->curs->next;
231 return (lset->curs->data);
237 /* say how many entries there are in the given lset */
238 static int lset_n_entries (lset_t *lset)
240 return (lset->n_entries);
243 /* deallocate the lset and all of its entries */
244 static void lset_destroy (lset_t *lset)
246 lset_entry_t *curs = lset->first;
248 while (NULL != curs) {
249 lset_entry_t *tmp = curs->next;
251 memset (curs, 0x00, sizeof (lset_entry_t));
257 memset (lset, 0x00, sizeof (lset_t));
261 /* ====================
263 ==================== */
265 Find out whether the given clazz uses the given implementation of a
266 method. Presumably, this is because clazz inherits the graph as
267 the implementation for a method.
269 static int uses_graph (type *clazz, entity *meth, ir_graph *graph)
271 type *g_clazz = get_entity_owner (meth);
273 if (g_clazz == clazz) {
277 if (peculiarity_existent == get_entity_peculiarity (meth)) {
278 ir_graph *g_graph = get_entity_irg (meth);
280 if (g_graph != graph) {
285 /* else inherited or description */
288 int n_over = get_entity_n_overwrittenby (meth); /* DOWN-wards */
290 for (i = 0; (i < n_over) && (!use); i ++) {
291 entity *over = get_entity_overwrittenby (meth, i);
293 use |= uses_graph (clazz, over, graph);
301 Find out whether otype is a subtype of stype.
302 Return non-zero iff otype is a subtype of stype.
304 static int is_subtype (type *otype, type *stype)
306 int n_sub = get_class_n_subtypes (stype);
310 if (otype == stype) {
314 for (i = 0; (!is_sub) && (i < n_sub); i ++) {
315 type *sub = get_class_subtype (stype, i);
317 is_sub |= is_subtype (otype, sub);
325 Compute the closure of all subtypes of otype (including otype
328 static void _collect_subtypes (type *otype, lset_t *set)
330 lset_insert (set, otype);
332 int n_sub = get_class_n_subtypes (otype);
335 for (i = 0; i < n_sub; i ++) {
336 type *sub = get_class_subtype (otype, i);
338 _collect_subtypes (sub, set);
342 static lset_t *subtype_closure (type *otype)
344 lset_t *set = lset_create ();
346 _collect_subtypes (otype, set);
352 Helper method for get_owner_types
354 static void _collect_owner_types (entity *method, ir_graph *graph, lset_t *tps)
356 /* search DOWNwards in clazz hierarchy */
358 if ((peculiarity_description == get_entity_peculiarity (method)) ||
359 (peculiarity_inherited == get_entity_peculiarity (method))) {
360 lset_insert (tps, get_entity_owner (method));
361 } else if (peculiarity_existent == get_entity_peculiarity (method)) {
362 ir_graph *ex_graph = get_entity_irg (method);
364 if ((NULL == ex_graph) || (ex_graph == graph)) {
365 /* wtf? they define the same graph again? well, whatever: */
366 lset_insert (tps, get_entity_owner (method));
368 /* aha: they define a new graph. can't have that, so bail out */
373 int n_over = get_entity_n_overwrittenby (method);
376 for (i = 0; i < n_over; i ++) {
377 entity *ometh = get_entity_overwrittenby (method, i);
379 _collect_owner_types (ometh, graph, tps);
385 Collect all classes that use the given implementation of a method.
387 static lset_t *get_owner_types (ir_graph *graph)
389 lset_t *tps = lset_create ();
390 entity *meth = get_irg_entity (graph);
392 _collect_owner_types (meth, graph, tps);
399 Convenience funcs to create a typalise_t
401 static typalise_t *ta_exact (type *tp)
403 typalise_t *ta = (typalise_t*) xmalloc (sizeof (typalise_t));
404 ta->kind = type_exact;
408 assert (is_class_type (tp));
413 static typalise_t *ta_types (lset_t *set)
415 typalise_t *ta = (typalise_t*) xmalloc (sizeof (typalise_t));
416 ta->kind = type_types;
423 static typalise_t *ta_type (type *tp)
425 typalise_t *ta = (typalise_t*) xmalloc (sizeof (typalise_t));
426 ta->kind = type_type;
430 assert (is_class_type (tp));
435 static void ta_delete (typalise_t *ta)
437 if (type_types == ta->kind) {
438 lset_destroy (ta->res.types);
439 ta->res.types = NULL;
444 ta->kind = type_invalid;
450 Join 'one' and 'two'; both args are deallocated, result is freshly
453 static typalise_t *ta_join (typalise_t *one, typalise_t *two)
455 typalise_t *res = NULL;
461 if (one->res.type == two->res.type) {
464 lset_t *set = lset_create ();
465 lset_insert (set, one->res.type);
466 lset_insert (set, two->res.type);
467 res = ta_types (set);
475 lset_insert (two->res.types, one->res.type);
481 if (is_subtype (one->res.type, two->res.type)) {
485 lset_t *closure = subtype_closure (two->res.type);
486 lset_insert (closure, one->res.type);
498 res = ta_join (two, one);
501 lset_insert_all (one->res.types, two->res.types);
507 lset_t *closure = subtype_closure (two->res.type);
508 lset_append (one->res.types, closure);
519 res = ta_join (two, one);
522 res = ta_join (two, one);
525 type *one_type = one->res.type;
526 type *two_type = two->res.type;
528 if (is_subtype (one_type, two_type)) {
531 } else if (is_subtype (two_type, one_type)) {
535 lset_t *one_closure = subtype_closure (one->res.type);
536 lset_t *two_closure = subtype_closure (two->res.type);
538 lset_append (one_closure, two_closure);
543 res = ta_types (one_closure);
550 assert (res && "no result");
556 static const char *ta_name (typalise_t *ta)
558 /* # define BUF_SIZE 1024 */
559 static char buf [BUF_SIZE];
561 int len = sprintf (buf, "[%d] ", ta->id);
565 len += sprintf (buf+len, "only ");
566 strncat (buf, get_type_name (ta->res.type), BUF_SIZE);
569 len += sprintf (buf+len, "one_of ");
571 type *iter = lset_first (ta->res.types);
573 int size = BUF_SIZE - len - 1;
574 while ((NULL != iter) && (0 < size)) {
575 char *dest = strncat (buf, get_type_name (iter), size);
578 iter = lset_next (ta->res.types);
582 len += sprintf (buf+len, "poly ");
583 strncat (buf, get_type_name (ta->res.type), BUF_SIZE);
588 /* # undef BUF_SIZE */
592 Check whether the given typalise_t includes the given type.
594 static int ta_supports (typalise_t *ta, ir_graph *graph)
599 lset_t *tps = get_owner_types (graph);
601 if (lset_contains (tps, ta->res.type)) {
610 entity *meth = get_irg_entity (graph);
611 type *tp = get_entity_owner (meth);
612 int res = is_subtype (tp, ta->res.type);
617 res = uses_graph (ta->res.type, meth, graph);
623 type *tp = get_entity_owner (get_irg_entity (graph));
625 return (lset_contains (ta->res.types, tp));
629 assert (0 && "invalid ta");
634 Given a set of graphs and a typalise_t, return the method(s) in
635 the set that are supported by the typalise_t. Also, deallocates
638 static lset_t *filter_for_ta (lset_t *set, typalise_t *ta)
640 lset_t *res = lset_create ();
641 ir_graph *curs = (ir_graph*) lset_first (set);
643 while (NULL != curs) {
644 if (ta_supports (ta, curs)) {
645 lset_insert (res, curs);
648 curs = lset_next (set);
658 Return a list containing all types of 'set' which are a subtype of 'type'.
660 static lset_t *filter_for_type (lset_t *set, type *stype)
662 type *curs = (type*) lset_first (set);
663 lset_t *lset = lset_create ();
665 while (NULL != curs) {
666 if (is_subtype (curs, stype)) {
667 lset_insert (lset, curs);
670 curs = lset_next (set);
677 Find an approximation to the given node's value's types
679 static typalise_t *typalise (ir_node*);
682 Find an approximation to the given proj node's value's types
684 static typalise_t *typalise_proj (ir_node *proj)
686 typalise_t *res = NULL;
687 ir_node *proj_in = get_Proj_pred (proj);
689 if (iro_Proj == get_irn_opcode (proj_in)) {
690 /* fprintf (stdout, "\tProj (Proj)\n"); */
692 proj_in = get_Proj_pred (proj_in);
693 if (iro_Start == get_irn_opcode (proj_in)) {
694 long n = get_Proj_proj (proj);
697 ir_graph *graph = get_irn_irg (proj);
698 entity *meth = get_irg_entity (graph);
699 type *tp = get_entity_owner (meth);
701 /* res = ta_exact (tp); */
702 res = ta_type (tp); /* TODO */
705 /* hey, even 'filtering' this NULL by the select of the actual
706 call is probably as "precise" as anything: */
709 } else if (iro_Call == get_irn_opcode (proj_in)) {
710 /* call result ... 'whatever' */
711 ir_node *call_ptr = get_Call_ptr (proj_in);
713 res = typalise (call_ptr);
715 fprintf (stdout, "\n Proj(Proj(%s)) not handled\n",
716 get_op_name (get_irn_op (proj_in)));
720 opcode op = get_irn_opcode (proj_in);
721 if ((iro_Load != op) && (iro_Alloc != op) && (iro_Call != op)) {
722 fprintf (stdout, "\n Proj(%s) not handled\n",
723 get_op_name (get_irn_op (proj_in)));
726 res = typalise (proj_in); /* everything else */
727 /* Proj(Load), Proj(New), Proj(Call) */
735 For the given ptr, do a quick check about what (class) types may be
738 static typalise_t *typalise (ir_node *node)
740 opcode op = get_irn_opcode (node);
741 typalise_t *res = NULL;
745 typalise_t *ta = NULL;
746 type *tp = get_Cast_type (node);
748 if (is_pointer_type (tp)) {
749 tp = get_pointer_points_to_type (tp);
751 assert (is_class_type (tp));
753 ta = typalise (get_Cast_op (node));
755 if (NULL == ta) { /* no type found */
757 } else if (type_exact == ta->kind) { /* one type found */
758 /* nothing (maybe check cast? */
759 } else if (type_type == ta->kind) { /* some types found */
760 if (is_subtype (tp, ta->res.type)) {
761 ta->res.type = tp; /* assume cast is correct */
763 /* should assert (is_subtype (ta->res.type, tp)) */
765 } else if (type_types == ta->kind) {
766 lset_t *ftp = filter_for_type (ta->res.types, tp);
767 lset_destroy (ta->res.types);
775 res = typalise_proj (node);
779 /* presumably it's call(load(ptr)) we're analyzing. */
780 ir_node *load_ptr = get_Load_ptr (node);
782 res = typalise (load_ptr);
787 /* it's call(sel(ptr)) or load(sel(ptr)) */
788 entity *ent = get_Sel_entity (node);
789 type *tp = get_entity_type (ent);
791 if (is_method_type (tp)) {
792 tp = get_entity_type (ent);
793 tp = get_method_res_type (tp, 0);
795 if (is_pointer_type (tp)) {
796 tp = get_pointer_points_to_type (tp);
800 } else if (is_class_type (tp)) {
801 tp = get_entity_type (ent);
803 if (is_pointer_type (tp)) {
804 tp = get_pointer_points_to_type (tp);
808 } else if (is_pointer_type (tp)) {
809 tp = get_pointer_points_to_type (tp);
812 assert (0 && "select not handled");
817 int n_ins = get_irn_arity (node);
819 ir_node *phi_in = NULL;
820 typalise_t *ta = NULL;
821 /* assert (0 && "Do we ever get here?"); */ /* apparently, we do. */
823 for (i = 0; i < n_ins; i ++) {
824 phi_in = get_irn_n (node, i);
825 ta = (NULL == ta) ? typalise (phi_in) : ta_join (ta, typalise (phi_in));
832 type *type = get_Alloc_type (node);
833 res = ta_exact (type);
837 /* presumably call(sel(proj(call))) */
838 ir_node *ptr = get_Call_ptr (node);
840 if (iro_Sel == get_irn_opcode (ptr)) {
841 meth = get_Sel_entity (ptr);
842 } else if (iro_SymConst == get_irn_opcode (ptr)) {
843 if (get_SymConst_kind(ptr) == symconst_addr_ent) {
844 meth = get_SymConst_entity (ptr);
846 meth = NULL; /* WTF? */
851 type *tp = get_method_res_type ((type*) meth, 0);
854 /* could be anything */
855 /* fprintf (stdout, "meth=(null)"); */
859 fprintf (stdout, "]\n");
863 case (iro_SymConst): {
864 if (get_SymConst_kind(node) == symconst_type_tag) {
865 type *tp = get_SymConst_type (node);
868 } else if (get_SymConst_kind (node) == symconst_addr_ent) {
869 entity *ent = get_SymConst_entity (node);
870 type *tp = get_entity_type (ent);
871 tp = get_pointer_points_to_type (tp);
872 assert (is_class_type (tp));
874 res = ta_type (tp); /* can't use ta_exact */
876 fprintf (stdout, "can't handle SymConst %s?\n",
877 get_op_name (get_irn_op (node)));
888 fprintf (stdout, "what's with %s?\n", get_op_name (get_irn_op (node)));
897 /* ====================
899 ==================== */
901 Append the given callEd to the given callEd info.
903 static callEd_info_t *append_callEd_info (callEd_info_t *ced, ir_graph *callEd)
905 callEd_info_t *nced = (callEd_info_t*) xmalloc (sizeof (sizeof (callEd_info_t)));
907 nced->callEd = callEd;
914 Append all callEd methods of the given (call) node to the given graph_info.
916 static void append_calls (graph_info_t *info, ir_node *call, lset_t *callEds)
920 call_info_t *cinfo = (call_info_t*) xmalloc (sizeof (call_info_t));
924 cinfo->prev = info->calls;
926 cinfo->callEds = NULL;
929 ir_graph *callEd = lset_first (callEds);
931 cinfo->callEds = append_callEd_info (cinfo->callEds, callEd);
933 callEd = lset_next (callEds);
938 Append the (single) callEd to the given (call) node of the given graph_info.
940 static void append_call (graph_info_t *info, ir_node *call, ir_graph *callEd)
942 call_info_t *cinfo = (call_info_t*) xmalloc (sizeof (call_info_t));
945 cinfo->prev = info->calls;
948 cinfo->callEds = append_callEd_info (cinfo->callEds, callEd);
952 Given a method, find the firm graph that implements that method.
953 Return NULL for abstract and native methods.
955 static ir_graph *_get_implementing_graph (entity *method)
957 ir_graph *graph = NULL;
959 /* What's up with the fenced out stuff in rta? */
960 if (peculiarity_existent == get_entity_peculiarity (method)) {
961 if (visibility_external_allocated == get_entity_visibility (method)) {
962 /* Todo: native implementation */
966 graph = get_entity_irg (get_SymConst_entity (get_atomic_ent_value (method)));
967 assert (graph && "no graph");
971 } else if (0 && (peculiarity_description == get_entity_peculiarity (method))) {
972 /* abstract --- can't find an implementation */
973 graph = get_entity_irg (method);
974 assert (!graph && "graph in abstract method");
977 } else if ((peculiarity_description == get_entity_peculiarity (method)) ||
978 (peculiarity_inherited == get_entity_peculiarity (method))) {
981 int n_over = get_entity_n_overwrites (method);
985 for (i = 0; (NULL == graph) && (i < n_over); i ++) {
986 entity *over = get_entity_overwrites (method, i);
988 graph = _get_implementing_graph (over);
991 assert (0 && "invalid peculiarity");
999 Collect all graphs of 'method' in the given set.
1001 static void _collect_implementing_graphs (entity *method, lset_t *set)
1003 /* search DOWN-wards in clazz hierarchy */
1005 int n_over = get_entity_n_overwrittenby (method);
1006 ir_graph *graph = get_entity_irg (method);
1008 if (NULL == graph) {
1009 graph = _get_implementing_graph (method);
1013 lset_insert (set, graph);
1016 for (i = 0; i < n_over; i ++) {
1017 entity *over = get_entity_overwrittenby (method, i);
1019 _collect_implementing_graphs (over, set);
1025 Collect all graphs that could possibly be executed when 'method' is called.
1027 static lset_t *get_implementing_graphs (entity *method, ir_node *select)
1029 lset_t *set = lset_create ();
1031 ir_graph *impl = _get_implementing_graph (method);
1034 lset_insert (set, impl);
1036 /* actually, abstract OR native */
1040 _collect_implementing_graphs (method, set);
1042 if (lset_empty (set)) {
1043 /* then it's a method which is only implemented natively, and we
1044 don' bother to analyse anything */
1048 void *tmp = lset_first (set);
1049 int n_graphs = lset_n_entries (set);
1051 /* typalise select_in */
1053 ir_node *select_in = get_Sel_ptr (select);
1054 typalise_t *ta = typalise (select_in);
1055 assert (ta && "typalise failed (go figure)");
1057 const char *res = ta_name (ta);
1059 /* fprintf (stdout, "typalyse res = %s\n", res); */
1061 if (1 != n_graphs) {
1062 set = filter_for_ta (set, ta);
1064 int n_filtered_graphs = lset_n_entries (set);
1066 fprintf (stdout, "%s: %02d %02d\n",
1070 n_graphs - n_filtered_graphs);
1071 n_graphs = n_filtered_graphs;
1075 if (n_graphs > _max_callEds) {
1076 _max_callEds = n_graphs;
1077 _max_callEds_callR = method;
1081 if (visibility_external_allocated != get_entity_visibility (method)) {
1082 if (0 == n_graphs) {
1083 /* fprintf (stdout, "no graphs for method %s\n", get_entity_name (method)); */
1084 assert (n_graphs && "no graphs for method");
1092 Action for the graph.
1094 static void ecg_calls_act (ir_node *node, void *env)
1096 opcode op = get_irn_opcode (node);
1098 if (iro_Call == op) { /* CALL */
1099 graph_info_t *graph_info = (graph_info_t*) env;
1102 ir_node *ptr = get_Call_ptr (node);
1105 if (iro_Sel == get_irn_opcode (ptr)) {
1106 ent = get_Sel_entity (ptr);
1107 lset_t *graphs = get_implementing_graphs (ent, ptr);
1109 append_calls (graph_info, node, graphs);
1110 } else if (iro_SymConst == get_irn_opcode (ptr)) {
1111 if (get_SymConst_kind(ptr) == symconst_addr_ent) {
1112 ent = get_SymConst_entity (ptr);
1113 ir_graph *graph = get_entity_irg (ent);
1116 append_call (graph_info, node, graph);
1118 /* it's an externally allocated thingy */
1120 } else if (get_SymConst_kind(ptr) == symconst_addr_name) {
1121 /* If this SymConst refers to a method the method is external_visible
1122 and therefore must be considered live anyways. */
1123 if (get_SymConst_name(ptr) != new_id_from_str("iro_Catch")) {
1124 assert (ent && "couldn't determine entity of call to symConst");
1127 /* other symconst. */
1128 assert (0 && "This SymConst can not be an address for a method call.");
1131 /* STRANGE, no less ... */
1134 assert(0 && "Unexpected address expression");
1140 Collect called graphs for the given graph.
1142 static void ecg_fill_graph_calls (ir_graph *graph)
1144 graph_info_t *graph_info = (graph_info_t*) xmalloc (sizeof (graph_info_t));
1146 graph_info->graph = graph;
1147 graph_info->calls = NULL;
1148 graph_info->ecg_seen = 0;
1150 entity *method = get_irg_entity (graph);
1151 type *clazz = get_entity_owner (method);
1153 irg_walk_graph (graph, ecg_calls_act, NULL, graph_info);
1155 pmap_insert (graph_infos, graph, graph_info);
1159 For each graph, collect called graphs, and enter them into calls.
1161 static void ecg_fill_calls ()
1165 for (i = 0; i < get_irp_n_irgs (); i++) {
1166 ir_graph *graph = get_irp_irg (i);
1168 ecg_fill_graph_calls (graph);
1172 /* ====================
1174 ==================== */
1177 get the call infos for the given graph
1179 graph_info_t *ecg_get_info (ir_graph *graph)
1181 graph_info_t *ginfo = (graph_info_t*) pmap_get (graph_infos, graph);
1183 assert (ginfo && "no info for graph");
1191 Dump the given graph and it's calls and it's calls callEds to the given file.
1193 static int ecg_ecg_graph (FILE *dot, ir_graph *graph)
1195 const char *name = get_irg_entity (graph) ?
1196 get_entity_name (get_irg_entity (graph)) : "noEntity";
1198 (get_entity_stickyness
1199 (get_irg_entity (graph)) == stickyness_sticky) ?
1200 "red" : "lightyellow";
1202 graph_info_t *ginfo = (graph_info_t*) pmap_get (graph_infos, graph);
1204 if (0 != ginfo->ecg_seen) {
1205 fprintf (dot, "\t/* recursive call to \"%s\" (%d) */\n", name, ginfo->ecg_seen);
1207 fprintf (dot, "\t/* recursive call to \"%s\" (0x%08x) */\n", name, graph);
1209 return (ginfo->ecg_seen);
1212 assert (0L <= _graphs);
1214 const int graph_no = _graphs ++;
1215 ginfo->ecg_seen = graph_no;
1217 fprintf (dot, "\t/* Graph of \"%s.%s\" */\n",
1218 get_type_name (get_entity_owner (get_irg_entity (graph))),
1220 fprintf (dot, "\tgraph_%i [label=\"%s\\l%s\", color=\"%s\"];\n",
1222 get_type_name (get_entity_owner (get_irg_entity (graph))),
1225 fprintf (dot, "\n");
1227 if (visibility_external_allocated ==
1228 get_entity_visibility (get_irg_entity (graph))) {
1229 fprintf (dot, "\t/* graph \"%s\" is external */\n", name);
1234 call_info_t *cinfo = ginfo->calls;
1235 while (NULL != cinfo) {
1236 ir_node *call = cinfo->call;
1237 callEd_info_t *ced = cinfo->callEds;
1238 const int call_no = _calls ++;
1240 fprintf (dot, "\t/* Call 0x%08x */\n", call);
1241 fprintf (dot, "\tcall_%i [label=\"call\\l0x%08x\"];\n",
1243 fprintf (dot, "\tgraph_%i -> call_%i [color=\"black\"];\n", graph_no, call_no);
1245 while (NULL != ced) {
1246 ir_graph *callEd_graph = ced->callEd;
1247 const int callEd_no = ecg_ecg_graph (dot, callEd_graph);
1248 const char *callEd_name = get_irg_entity (callEd_graph) ?
1249 get_entity_name (get_irg_entity (callEd_graph)) : "noEntity";
1250 const char *direction = (callEd_no <= graph_no) ? "forward" : "forward";
1251 const char *callEd_color = (callEd_no <= graph_no) ? "red" : "lightyellow";
1253 fprintf (dot, "\t/* Call from graph \"%s\" to graph \"%s\" */\n",
1256 /* Check for recursive calls */
1257 /* if (callEd_no > graph_no) */ { /* do recursive calls (for now) */
1258 fprintf (dot, "\tcall_%i -> graph_%i [color=\"%s\", dir=\"%s\"];\n",
1259 call_no, callEd_no, callEd_color, direction);
1264 } /* done all calEds(call) */
1266 cinfo = cinfo->prev;
1267 } /* done all calls(graph) */
1269 fprintf (dot, "\t/* done with graph of \"%s\" */\n\n", name);
1272 ginfo->ecg_seen = 0;
1278 Count how many nodes the ECG will have
1280 static char spaces [BUF_SIZE];
1282 static void ecg_ecg_count (ir_graph *graph)
1284 graph_info_t *ginfo = (graph_info_t*) pmap_get (graph_infos, graph);
1286 if (0 != ginfo->ecg_seen) {
1291 if (_depth > _max_depth) {
1292 _max_depth = _depth;
1295 fprintf (stdout, "_max_depth = %i\n", _max_depth);
1296 fprintf (stdout, "\tn_graphs: %i\n", _graphs);
1300 assert (0L <= _graphs);
1303 if (0 == (_graphs % 1000000)) {
1304 fprintf (stdout, "\tn_graphs: %i\n", _graphs);
1305 fprintf (stdout, "_depth = %i\n", _depth);
1309 const int graph_no = _graphs ++;
1310 ginfo->ecg_seen = graph_no;
1312 fprintf (stdout, "%sMethod \"%s.%s\"\n",
1313 spaces + BUF_SIZE - _depth,
1314 get_type_name (get_entity_owner (get_irg_entity (graph))),
1315 get_entity_name (get_irg_entity (graph)));
1317 call_info_t *cinfo = ginfo->calls;
1318 while (NULL != cinfo) {
1320 callEd_info_t *ced = cinfo->callEds;
1322 fprintf (stdout, "%sCall \"0x%08x\"\n",
1323 spaces + BUF_SIZE - _depth,
1326 while (NULL != ced) {
1327 ir_graph *callEd_graph = ced->callEd;
1329 fprintf (stdout, "%sCall Target \"%s.%s\"\n",
1330 spaces + BUF_SIZE - _depth,
1331 get_type_name (get_entity_owner (get_irg_entity (callEd_graph))),
1332 get_entity_name (get_irg_entity (callEd_graph)));
1334 ecg_ecg_count (callEd_graph);
1337 } /* done all calEds(call) */
1338 cinfo = cinfo->prev;
1339 } /* done all calls(graph) */
1341 ginfo->ecg_seen = 0;
1345 /* ====================
1347 ==================== */
1350 Initialise our data structures.
1352 void ecg_init (int typalise)
1354 do_typalise = typalise;
1356 graph_infos = pmap_create ();
1368 for (i = 0; i < get_irp_n_irgs (); i++) {
1369 ir_graph *graph = get_irp_irg (i);
1371 graph_info_t *info = pmap_get (graph_infos, graph);
1372 call_info_t *cinfo = info->calls;
1374 while (NULL != cinfo) {
1375 free (cinfo->callEds);
1378 callEd_info_t *ced = cinfo->callEds;
1380 while (NULL != ced) {
1381 callEd_info_t *nced = ced->prev;
1388 /* Todo: delete callEds */
1389 cinfo->callEds = NULL;
1392 cinfo = cinfo->prev;
1396 pmap_insert (graph_infos, graph, NULL);
1400 pmap_destroy (graph_infos);
1402 /* BEGIN mild paranoia mode */
1404 /* END mild paranoia mode */
1408 Show what we have found.
1414 FILE *dot = fopen ("calls.dot", "w");
1416 fprintf (dot, "digraph \"calls\" {\n");
1417 fprintf (dot, "\tnode [shape = \"record\", style = \"filled\"];\n");
1418 fprintf (dot, "\tedge [color = \"black\"];\n");
1419 fprintf (dot, "\n");
1420 fprintf (dot, "\tsize = \"11, 7\";\n");
1421 fprintf (dot, "\trotate = \"90\";\n");
1422 fprintf (dot, "\tratio = \"fill\";\n");
1423 fprintf (dot, "\trankdir = \"LR\";\n");
1424 fprintf (dot, "\n");
1426 for (i = 0; i < get_irp_n_irgs (); i++) {
1427 ir_graph *graph = get_irp_irg (i);
1428 graph_info_t *info = (graph_info_t*) pmap_get (graph_infos, graph);
1430 const char *name = get_irg_entity (graph) ?
1431 get_entity_name (get_irg_entity (graph)) : "noEntity";
1433 const char *oname = get_type_name
1434 (get_entity_owner (get_irg_entity (graph)));
1437 (get_entity_stickyness
1438 (get_irg_entity (graph)) == stickyness_sticky) ?
1439 "red" : "lightyellow";
1441 fprintf (dot, "\t/* graph_0x%08x (\"%s\") */\n", graph, name);
1443 "\tgraph_0x%08x [label=\"%s\\l%s\", color=\"%s\"];\n",
1444 graph, oname, name, color);
1445 fprintf (dot, "\n");
1446 fprintf (dot, "\t/* now the calls */\n");
1448 call_info_t *cinfo = info->calls;
1449 while (NULL != cinfo) {
1450 ir_node *call = cinfo->call;
1453 fprintf (dot, "\t/* call_0x%08x */\n", call);
1454 fprintf (dot, "\tcall_0x%08x [label=\"call\\l0x%08x\"];\n", call, call);
1455 fprintf (dot, "\tgraph_0x%08x -> call_0x%08x;\n", graph, call);
1457 callEd_info_t *ced = cinfo->callEds;
1458 while (NULL != ced) {
1459 fprintf (dot, "\tcall_0x%08x -> graph_0x%08x;\n", call, ced->callEd);
1462 fprintf (dot, "\n");
1464 cinfo = cinfo->prev;
1466 fprintf (dot, "\n");
1468 fprintf (dot, "}\n");
1470 fprintf (stdout, " max_callEds: %i\n", _max_callEds);
1471 fprintf (stdout, " max_callEds_callR: \"%s\"\n",
1472 get_entity_name (_max_callEds_callR));
1480 Experimental: Print the ecg
1487 ir_graph *main_graph = get_irp_main_irg ();
1490 memset (spaces, '.', BUF_SIZE);
1491 spaces [BUF_SIZE-1] = '\0';
1493 ecg_ecg_count (main_graph);
1494 fprintf (stdout, "n_graphs: %i\n", _graphs);
1495 fprintf (stdout, "max_depth = %i\n", _max_depth);
1503 FILE *dot = fopen ("ecg.dot", "w");
1505 fprintf (dot, "digraph \"ecg\" {\n");
1506 fprintf (dot, "\tnode [shape = \"record\", style = \"filled\"];\n");
1507 fprintf (dot, "\tedge [color = \"black\"];\n");
1508 fprintf (dot, "\n");
1509 fprintf (dot, "\tsize = \"11, 7\";\n");
1510 fprintf (dot, "\trotate = \"90\";\n");
1511 fprintf (dot, "\tratio = \"fill\";\n");
1512 fprintf (dot, "\trankdir = \"LR\";\n");
1513 fprintf (dot, "\n");
1515 /* ir_graph *main_graph = get_irp_main_irg (); */
1516 ecg_ecg_graph (dot, main_graph);
1518 fprintf (dot, "\t/* Grand Total: */\n");
1519 fprintf (dot, "\t/* calls: %ld */\n", _calls);
1520 fprintf (dot, "\t/* graphs: %ld */\n", _graphs);
1521 fprintf (dot, "\t/* (sales tax not included) */\n");
1523 fprintf (dot, "}\n");