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 # endif /* not defined TRUE */
37 # define BUF_SIZE 1024
40 # include "typalise.h"
46 /* static int verbose = 0; */
47 static int do_typalise = 0;
53 /* mapping from method graphs (callR) to method graphs (lset_ts of callEds) */
54 /* static pmap *calls; */
55 static pmap *graph_infos;
57 /** Counters for ecg_ecg and friends */
58 static long _graphs = 0;
59 static long _calls = 0;
60 static long _allocs = 0;
62 static int _depth = 0;
63 static int _max_depth = 0;
65 static int _max_callEds = 0;
66 static entity* _max_callEds_callR = NULL;
68 /* ====================
70 ==================== */
71 static void append_alloc (graph_info_t *ginfo, ir_node *alloc, type *tp)
73 alloc_info_t *ainfo = (alloc_info_t*) xmalloc (sizeof (alloc_info_t));
75 ainfo->graph = ginfo->graph;
79 ainfo->prev = ginfo->allocs;
80 ginfo->allocs = ainfo;
84 /* ====================
86 ==================== */
88 Append the given callEd to the given callEd info.
90 static callEd_info_t *append_callEd_info (callEd_info_t *ced, ir_graph *callEd)
92 callEd_info_t *nced = (callEd_info_t*) xmalloc (sizeof (sizeof (callEd_info_t)));
94 nced->callEd = callEd;
101 Append all callEd methods of the given (call) node to the given graph_info.
103 static void append_calls (graph_info_t *info, ir_node *call, lset_t *callEds)
105 call_info_t *cinfo = (call_info_t*) xmalloc (sizeof (call_info_t));
109 cinfo->prev = info->calls;
111 cinfo->callEds = NULL;
114 ir_graph *callEd = lset_first (callEds);
116 cinfo->callEds = append_callEd_info (cinfo->callEds, callEd);
118 callEd = lset_next (callEds);
123 Append the (single) callEd to the given (call) node of the given graph_info.
125 static void append_call (graph_info_t *info, ir_node *call, ir_graph *callEd)
127 call_info_t *cinfo = (call_info_t*) xmalloc (sizeof (call_info_t));
130 cinfo->prev = info->calls;
133 cinfo->callEds = append_callEd_info (cinfo->callEds, callEd);
137 Given a method, find the firm graph that implements that method.
138 Return NULL for abstract and native methods.
140 static ir_graph *_get_implementing_graph (entity *method)
142 ir_graph *graph = NULL;
144 /* What's up with the fenced out stuff in rta? */
145 if (peculiarity_existent == get_entity_peculiarity (method)) {
146 if (visibility_external_allocated == get_entity_visibility (method)) {
147 /* Todo: native implementation */
151 graph = get_entity_irg (get_SymConst_entity (get_atomic_ent_value (method)));
152 assert (graph && "no graph");
156 } else if (0 && (peculiarity_description == get_entity_peculiarity (method))) {
157 /* abstract --- can't find an implementation */
158 graph = get_entity_irg (method);
159 assert (!graph && "graph in abstract method");
162 } else if ((peculiarity_description == get_entity_peculiarity (method)) ||
163 (peculiarity_inherited == get_entity_peculiarity (method))) {
166 int n_over = get_entity_n_overwrites (method);
170 for (i = 0; (NULL == graph) && (i < n_over); i ++) {
171 entity *over = get_entity_overwrites (method, i);
173 graph = _get_implementing_graph (over);
176 assert (0 && "invalid peculiarity");
184 Collect all graphs of 'method' in the given set.
186 static void _collect_implementing_graphs (entity *method, lset_t *set)
188 /* search DOWN-wards in clazz hierarchy */
190 int n_over = get_entity_n_overwrittenby (method);
191 ir_graph *graph = get_entity_irg (method);
194 graph = _get_implementing_graph (method);
198 lset_insert (set, graph);
201 for (i = 0; i < n_over; i ++) {
202 entity *over = get_entity_overwrittenby (method, i);
204 _collect_implementing_graphs (over, set);
210 Collect all graphs that could possibly be executed when 'method' is called.
212 static lset_t *get_implementing_graphs (entity *method, ir_node *select)
214 lset_t *set = lset_create ();
216 ir_graph *impl = _get_implementing_graph (method);
219 lset_insert (set, impl);
221 /* actually, abstract OR native */
225 _collect_implementing_graphs (method, set);
227 if (lset_empty (set)) {
228 /* then it's a method which is only implemented natively, and we
229 don' bother to analyse anything */
233 /* void *tmp = lset_first (set); */
234 int n_graphs = lset_n_entries (set);
236 /* typalise select_in */
238 ir_node *select_in = get_Sel_ptr (select);
239 typalise_t *ta = typalise (select_in);
240 assert (ta && "typalise failed (go figure)");
242 /* const char *res = ta_name (ta); */
244 /* fprintf (stdout, "typalyse res = %s\n", res); */
247 set = filter_for_ta (set, ta);
249 int n_filtered_graphs = lset_n_entries (set);
252 fprintf (stdout, "%s: %02d %02d\n",
256 n_graphs - n_filtered_graphs);
258 n_graphs = n_filtered_graphs;
262 if (n_graphs > _max_callEds) {
263 _max_callEds = n_graphs;
264 _max_callEds_callR = method;
268 if (visibility_external_allocated != get_entity_visibility (method)) {
270 /* fprintf (stdout, "no graphs for method %s\n", get_entity_name (method)); */
271 assert (n_graphs && "no graphs for method");
279 Action for the graph.
281 static void ecg_calls_act (ir_node *node, void *env)
283 opcode op = get_irn_opcode (node);
284 graph_info_t *graph_info = (graph_info_t*) env;
286 if (iro_Call == op) { /* CALL */
288 ir_node *ptr = get_Call_ptr (node);
291 if (iro_Sel == get_irn_opcode (ptr)) {
292 ent = get_Sel_entity (ptr);
293 lset_t *graphs = get_implementing_graphs (ent, ptr);
295 append_calls (graph_info, node, graphs);
296 } else if (iro_SymConst == get_irn_opcode (ptr)) {
297 if (get_SymConst_kind (ptr) == symconst_addr_ent) {
298 ent = get_SymConst_entity (ptr);
299 ir_graph *graph = get_entity_irg (ent);
302 append_call (graph_info, node, graph);
304 /* it's an externally allocated thingy */
306 } else if (get_SymConst_kind (ptr) == symconst_addr_name) {
307 /* If this SymConst refers to a method the method is external_visible
308 and therefore must be considered live anyways. */
309 if (get_SymConst_name (ptr) != new_id_from_str ("iro_Catch")) {
310 assert (ent && "couldn't determine entity of call to symConst");
313 /* other symconst. */
314 assert (0 && "This SymConst can not be an address for a method call.");
317 /* STRANGE, no less ... */
320 assert (0 && "Unexpected address expression");
322 } else if (iro_Alloc == op) {
323 type *tp = get_Alloc_type (node);
324 /* const char *name = get_type_name (tp); */
326 append_alloc (graph_info, node, tp);
328 /* fprintf (stdout, "NEW \"%s\"\n", name); */
333 Collect called graphs for the given graph.
335 static void ecg_fill_graph_calls (ir_graph *graph)
337 graph_info_t *graph_info = (graph_info_t*) xmalloc (sizeof (graph_info_t));
339 graph_info->graph = graph;
340 graph_info->calls = NULL;
341 graph_info->ecg_seen = 0;
343 /* entity *method = get_irg_entity (graph); */
344 /* type *clazz = get_entity_owner (method); */
346 irg_walk_graph (graph, ecg_calls_act, NULL, graph_info);
348 pmap_insert (graph_infos, graph, graph_info);
352 For each graph, collect called graphs, and enter them into calls.
354 static void ecg_fill_calls (void)
358 for (i = 0; i < get_irp_n_irgs (); i++) {
359 ir_graph *graph = get_irp_irg (i);
361 ecg_fill_graph_calls (graph);
365 /* ====================
367 ==================== */
370 get the call infos for the given graph
372 graph_info_t *ecg_get_info (ir_graph *graph)
374 graph_info_t *ginfo = (graph_info_t*) pmap_get (graph_infos, graph);
376 assert (ginfo && "no info for graph");
384 Dump the given graph and it's calls and it's calls callEds to the given file.
386 static int ecg_ecg_graph (FILE *dot, ir_graph *graph)
388 const char *name = get_irg_entity (graph) ?
389 get_entity_name (get_irg_entity (graph)) : "noEntity";
391 (get_entity_stickyness
392 (get_irg_entity (graph)) == stickyness_sticky) ?
393 "red" : "lightyellow";
395 graph_info_t *ginfo = (graph_info_t*) pmap_get (graph_infos, graph);
397 if (0 != ginfo->ecg_seen) {
398 fprintf (dot, "\t/* recursive call to \"%s\" (%d) */\n",
399 name, (int) ginfo->ecg_seen);
401 fprintf (dot, "\t/* recursive call to \"%s\" (0x%08x) */\n",
404 return (ginfo->ecg_seen);
407 assert (0L <= _graphs);
409 const int graph_no = _graphs ++;
410 ginfo->ecg_seen = graph_no;
412 fprintf (dot, "\t/* Graph of \"%s.%s\" */\n",
413 get_type_name (get_entity_owner (get_irg_entity (graph))),
415 fprintf (dot, "\tgraph_%i [label=\"%s\\l%s\", color=\"%s\"];\n",
417 get_type_name (get_entity_owner (get_irg_entity (graph))),
422 if (visibility_external_allocated ==
423 get_entity_visibility (get_irg_entity (graph))) {
424 fprintf (dot, "\t/* graph \"%s\" is external */\n", name);
429 call_info_t *cinfo = ginfo->calls;
430 while (NULL != cinfo) {
431 ir_node *call = cinfo->call;
432 callEd_info_t *ced = cinfo->callEds;
433 const int call_no = _calls ++;
435 fprintf (dot, "\t/* Call 0x%08x */\n", (int) call);
436 fprintf (dot, "\tcall_%i [label=\"call\\l0x%08x\"];\n",
437 call_no, (int) call);
438 fprintf (dot, "\tgraph_%i -> call_%i [color=\"black\"];\n", graph_no, call_no);
440 while (NULL != ced) {
441 ir_graph *callEd_graph = ced->callEd;
442 const int callEd_no = ecg_ecg_graph (dot, callEd_graph);
443 const char *callEd_name = get_irg_entity (callEd_graph) ?
444 get_entity_name (get_irg_entity (callEd_graph)) : "noEntity";
445 const char *direction = (callEd_no <= graph_no) ? "forward" : "forward";
446 const char *callEd_color = (callEd_no <= graph_no) ? "red" : "black";
448 fprintf (dot, "\t/* Call from graph \"%s\" to graph \"%s\" */\n",
451 /* Check for recursive calls */
452 /* if (callEd_no > graph_no) */ { /* do recursive calls (for now) */
453 fprintf (dot, "\tcall_%i -> graph_%i [color=\"%s\", dir=\"%s\"];\n",
454 call_no, callEd_no, callEd_color, direction);
459 } /* done all calEds (call) */
462 } /* done all calls (graph) */
465 alloc_info_t *ainfo = ginfo->allocs;
467 fprintf (dot, "\t/* now the allocs */\n");
469 fprintf (dot, "\t/* no allocs */\n");
472 while (NULL != ainfo) {
473 ir_node *alloc = ainfo->alloc;
474 const char *name = get_type_name (ainfo->tp);
475 const char *color = "red1";
477 /* if (0 == ginfo->allocs_seen) { */
479 fprintf (dot, "\talloc_0x%08x_%i [label=\"%s\", color=\"%s\"]\n",
480 (int) alloc, graph_no, name, color);
483 fprintf (dot, "\tgraph_%i -> alloc_0x%08x_%i\n", graph_no, (int) alloc, graph_no);
488 if (0 == ginfo->allocs_seen) {
489 ginfo->allocs_seen = 1;
492 fprintf (dot, "\t/* done with graph of \"%s\" */\n\n", name);
501 Count how many nodes the ECG will have
503 static char spaces [BUF_SIZE];
505 static void ecg_ecg_count (ir_graph *graph)
507 graph_info_t *ginfo = (graph_info_t*) pmap_get (graph_infos, graph);
509 if (0 != ginfo->ecg_seen) {
514 if (_depth > _max_depth) {
518 fprintf (stdout, "_max_depth = %i\n", _max_depth);
519 fprintf (stdout, "\tn_graphs: %i\n", _graphs);
523 assert (0L <= _graphs);
526 if (0 == (_graphs % 1000000)) {
527 fprintf (stdout, "\tn_graphs: %i\n", _graphs);
528 fprintf (stdout, "_depth = %i\n", _depth);
532 const int graph_no = _graphs ++;
533 ginfo->ecg_seen = graph_no;
535 fprintf (stdout, "%sMethod \"%s.%s\"\n",
536 spaces + BUF_SIZE - _depth,
537 get_type_name (get_entity_owner (get_irg_entity (graph))),
538 get_entity_name (get_irg_entity (graph)));
540 call_info_t *cinfo = ginfo->calls;
541 while (NULL != cinfo) {
543 callEd_info_t *ced = cinfo->callEds;
545 fprintf (stdout, "%sCall \"0x%08x\"\n",
546 spaces + BUF_SIZE - _depth,
549 while (NULL != ced) {
550 ir_graph *callEd_graph = ced->callEd;
552 fprintf (stdout, "%sCall Target \"%s.%s\"\n",
553 spaces + BUF_SIZE - _depth,
554 get_type_name (get_entity_owner (get_irg_entity (callEd_graph))),
555 get_entity_name (get_irg_entity (callEd_graph)));
557 ecg_ecg_count (callEd_graph);
560 } /* done all calEds (call) */
562 } /* done all calls (graph) */
568 /* ====================
570 ==================== */
573 Initialise our data structures.
575 void ecg_init (int typalise)
577 do_typalise = typalise;
579 graph_infos = pmap_create ();
591 for (i = 0; i < get_irp_n_irgs (); i++) {
592 ir_graph *graph = get_irp_irg (i);
594 graph_info_t *info = pmap_get (graph_infos, graph);
595 call_info_t *cinfo = info->calls;
597 while (NULL != cinfo) {
598 free (cinfo->callEds);
601 callEd_info_t *ced = cinfo->callEds;
603 while (NULL != ced) {
604 callEd_info_t *nced = ced->prev;
611 /* Todo: delete callEds */
612 cinfo->callEds = NULL;
619 pmap_insert (graph_infos, graph, NULL);
623 pmap_destroy (graph_infos);
625 /* BEGIN mild paranoia mode */
627 /* END mild paranoia mode */
631 Show what we have found.
637 FILE *dot = fopen ("calls.dot", "w");
639 fprintf (dot, "digraph \"calls\" {\n");
640 fprintf (dot, "\tnode [shape = \"record\", style = \"filled\"];\n");
641 fprintf (dot, "\tedge [color = \"black\"];\n");
643 fprintf (dot, "\tsize = \"11, 7\";\n");
644 fprintf (dot, "\trotate = \"90\";\n");
645 fprintf (dot, "\tratio = \"fill\";\n");
646 fprintf (dot, "\trankdir = \"LR\";\n");
649 for (i = 0; i < get_irp_n_irgs (); i++) {
650 ir_graph *graph = get_irp_irg (i);
651 graph_info_t *info = (graph_info_t*) pmap_get (graph_infos, graph);
653 const char *name = get_irg_entity (graph) ?
654 get_entity_name (get_irg_entity (graph)) : "noEntity";
656 const char *oname = get_type_name
657 (get_entity_owner (get_irg_entity (graph)));
660 (get_entity_stickyness
661 (get_irg_entity (graph)) == stickyness_sticky) ?
662 "red3" : "lightyellow";
664 fprintf (dot, "\t/* graph_0x%08x (\"%s\") */\n", (int) graph, name);
666 "\tgraph_0x%08x [label=\"%s\\l%s\", color=\"%s\"];\n",
667 (int) graph, oname, name, color);
670 call_info_t *cinfo = info->calls;
672 fprintf (dot, "\t/* now the calls */\n");
674 fprintf (dot, "\t/* no calls, nothing to see, move along! */\n");
677 while (NULL != cinfo) {
678 ir_node *call = cinfo->call;
680 fprintf (dot, "\t/* call_0x%08x */\n", (int) call);
681 fprintf (dot, "\tcall_0x%08x [label=\"call\\l0x%08x\"];\n",
682 (int) call, (int) call);
683 fprintf (dot, "\tgraph_0x%08x -> call_0x%08x;\n",
684 (int) graph, (int) call);
686 callEd_info_t *ced = cinfo->callEds;
687 while (NULL != ced) {
688 fprintf (dot, "\tcall_0x%08x -> graph_0x%08x;\n",
689 (int) call, (int) ced->callEd);
698 alloc_info_t *ainfo = info->allocs;
700 fprintf (dot, "\t/* now the allocs */\n");
702 fprintf (dot, "\t/* no allocs */\n");
706 while (NULL != ainfo) {
707 ir_node *alloc = ainfo->alloc;
708 const char *name = get_type_name (ainfo->tp);
709 const char *color = "green3";
711 fprintf (dot, "\talloc_0x%08x [label=\"%s\", color=\"%s\"]\n",
712 (int) alloc, name, color);
713 fprintf (dot, "\tgraph_0x%08x -> alloc_0x%08x\n",
714 (int) graph, (int) alloc);
719 fprintf (dot, "}\n");
722 fprintf (stdout, " max_callEds: %i\n", _max_callEds);
723 fprintf (stdout, " max_callEds_callR: \"%s\"\n",
724 get_entity_name (_max_callEds_callR));
732 Experimental: Print the ecg
739 ir_graph *main_graph = get_irp_main_irg ();
742 memset (spaces, '.', BUF_SIZE);
743 spaces [BUF_SIZE-1] = '\0';
745 ecg_ecg_count (main_graph);
746 fprintf (stdout, "n_graphs: %i\n", _graphs);
747 fprintf (stdout, "max_depth = %i\n", _max_depth);
755 FILE *dot = fopen ("ecg.dot", "w");
757 fprintf (dot, "digraph \"ecg\" {\n");
758 fprintf (dot, "\tnode [shape = \"record\", style = \"filled\"];\n");
759 fprintf (dot, "\tedge [color = \"black\"];\n");
761 fprintf (dot, "\tsize = \"11, 7\";\n");
762 fprintf (dot, "\trotate = \"90\";\n");
763 fprintf (dot, "\tratio = \"fill\";\n");
764 fprintf (dot, "\trankdir = \"LR\";\n");
767 /* ir_graph *main_graph = get_irp_main_irg (); */
768 ecg_ecg_graph (dot, main_graph);
770 fprintf (dot, "\t/* Grand Total: */\n");
771 fprintf (dot, "\t/* calls: %i */\n", (int) _calls);
772 fprintf (dot, "\t/* graphs: %i */\n", (int) _graphs);
773 fprintf (dot, "\t/* allocs: %i */\n", (int) _allocs);
774 fprintf (dot, "\t/* (sales tax not included) */\n");
776 fprintf (dot, "}\n");
785 Revision 1.3 2004/11/04 14:54:44 liekweg
788 Revision 1.2 2004/10/21 11:09:37 liekweg
789 Moved memwalk stuf into irmemwalk
790 Moved lset stuff into lset
791 Moved typalise stuff into typalise
793 Revision 1.1 2004/10/20 14:59:41 liekweg
794 Added ana2, added ecg and pto
796 Revision 1.6 2004/10/18 12:47:19 liekweg
799 Revision 1.5 2004/10/14 11:31:28 liekweg
802 Revision 1.4 2004/10/12 11:02:01 liekweg