3 * File name: ir/ana/callgraph.c
4 * Purpose: Representation and computation of the callgraph.
5 * Author: Goetz Lindenmaier
9 * Copyright: (c) 2004 Universität Karlsruhe
10 * Licence: This file protected by GPL - GNU GENERAL PUBLIC LICENSE.
14 #include "callgraph.h"
18 #include "irgraph_t.h"
26 /* The functions that call irg. */
27 int get_irg_n_callers(ir_graph *irg) {
28 if (irg->callers) return ARR_LEN(irg->callers);
31 ir_graph *get_irg_caller(ir_graph *irg, int pos) {
32 assert (pos >= 0 && pos < get_irg_n_callers(irg));
33 if (irg->callers) return irg->callers[pos];
36 int is_irg_caller_backedge(ir_graph *irg, int pos) {
37 assert (pos >= 0 && pos < get_irg_n_callers(irg));
38 return irg->caller_isbe[pos];
40 static void set_irg_caller_backedge(ir_graph *irg, int pos) {
41 assert (pos >= 0 && pos < get_irg_n_callers(irg));
42 irg->caller_isbe[pos] = 1;
45 /* The functions called by irg. */
46 int get_irg_n_callees(ir_graph *irg) {
47 if (irg->callees) return ARR_LEN(irg->callees);
50 ir_graph *get_irg_callee(ir_graph *irg, int pos) {
51 assert (pos >= 0 && pos < get_irg_n_callees(irg));
52 if (irg->callees) return irg->callees[pos];
55 int is_irg_callee_backedge(ir_graph *irg, int pos) {
56 assert (pos >= 0 && pos < get_irg_n_callees(irg));
57 return irg->callee_isbe[pos];
59 void set_irg_callee_backedge(ir_graph *irg, int pos) {
60 assert (pos >= 0 && pos < get_irg_n_callees(irg));
61 irg->callee_isbe[pos] = 1;
65 static void ana_Call(ir_node *n, void *env) {
69 if (get_irn_op(n) != op_Call) return;
72 n_callees = get_Call_n_callees(n);
73 for (i = 0; i < n_callees; ++i) {
74 entity *callee_e = get_Call_callee(n, i);
76 ir_graph *callee = get_entity_irg(callee_e);
77 pset_insert((pset *)irg->callees, callee, (unsigned)callee >> 3);
78 pset_insert((pset *)callee->callers, irg, (unsigned)irg >> 3);
84 /* compare two ir graphs */
85 static int graph_cmp(const void *elt, const void *key) {
90 /* Construct and destruct the callgraph. */
91 void compute_callgraph(void) {
92 int i, n_irgs = get_irp_n_irgs();
94 assert(interprocedural_view == 0); /* Else walking will not reach the Call nodes. */
98 for (i = 0; i < n_irgs; ++i) {
99 ir_graph *irg = get_irp_irg(i);
100 assert(get_irg_callee_info_state(irg) == irg_callee_info_consistent);
101 irg->callees = (ir_graph **)new_pset(graph_cmp, 8);
102 irg->callers = (ir_graph **)new_pset(graph_cmp, 8);
105 /* Compute the call graph */
106 for (i = 0; i < n_irgs; ++i) {
107 ir_graph *irg = get_irp_irg(i);
108 irg_walk_graph(irg, ana_Call, NULL, NULL);
111 /* Change the sets to arrays. */
112 for (i = 0; i < n_irgs; ++i) {
114 ir_graph *c, *irg = get_irp_irg(i);
116 pset *callee_set = (pset *)irg->callees;
117 count = pset_count(callee_set);
118 irg->callees = NEW_ARR_F(ir_graph *, count);
119 irg->callee_isbe = calloc(count, sizeof(int));
120 c = pset_first(callee_set);
121 for (j = 0; j < count; ++j) {
123 c = pset_next(callee_set);
125 del_pset(callee_set);
128 pset *caller_set = (pset *)irg->callers;
129 count = pset_count(caller_set);
130 irg->callers = NEW_ARR_F(ir_graph *, count);
131 irg->caller_isbe = calloc(count, sizeof(int));
132 c = pset_first(caller_set);
133 for (j = 0; j < count; ++j) {
135 c = pset_next(caller_set);
137 del_pset(caller_set);
142 void free_callgraph(void) {
143 int i, n_irgs = get_irp_n_irgs();
144 for (i = 0; i < n_irgs; ++i) {
145 ir_graph *irg = get_irp_irg(i);
146 if (irg->callees) DEL_ARR_F(irg->callees);
147 if (irg->callers) DEL_ARR_F(irg->callers);
148 if (irg->callee_isbe) DEL_ARR_F(irg->callee_isbe);
149 if (irg->caller_isbe) DEL_ARR_F(irg->caller_isbe);
152 irg->callee_isbe = NULL;
153 irg->caller_isbe = NULL;
158 /* ----------------------------------------------------------------------------------- */
159 /* loop construction algorithm */
160 /* ----------------------------------------------------------------------------------- */
162 static ir_graph *outermost_ir_graph; /* The outermost graph the scc is computed
164 static ir_loop *current_loop; /* Current cfloop construction is working
166 static int loop_node_cnt = 0; /* Counts the number of allocated cfloop nodes.
167 Each cfloop node gets a unique number.
168 What for? ev. remove. @@@ */
169 static int current_dfn = 1; /* Counter to generate depth first numbering
173 /**********************************************************************/
174 /* Node attributes **/
175 /**********************************************************************/
177 typedef struct scc_info {
178 bool in_stack; /* Marks whether node is on the stack. */
179 int dfn; /* Depth first search number. */
180 int uplink; /* dfn number of ancestor. */
184 static INLINE scc_info* new_scc_info(void) {
185 scc_info *info = obstack_alloc (outermost_ir_graph->obst, sizeof (scc_info));
186 memset (info, 0, sizeof (scc_info));
191 cg_irg_visited(ir_graph *n) {
192 return ((scc_info *)n->link)->visited;
196 mark_cg_irg_visited(ir_graph *n) {
197 ((scc_info *)n->link)->visited = 1;
201 set_cg_irg_visited(ir_graph *n, int i) {
202 ((scc_info *)n->link)->visited = i;
206 mark_irg_in_stack (ir_graph *n) {
207 assert(get_irg_link(n));
208 ((scc_info *)n->link)->in_stack = true;
212 mark_irg_not_in_stack (ir_graph *n) {
213 assert(get_irg_link(n));
214 ((scc_info *)n->link)->in_stack = false;
218 irg_is_in_stack (ir_graph *n) {
219 assert(get_irg_link(n));
220 return ((scc_info *)n->link)->in_stack;
224 set_irg_uplink (ir_graph *n, int uplink) {
225 assert(get_irg_link(n));
226 ((scc_info *)n->link)->uplink = uplink;
230 get_irg_uplink (ir_graph *n) {
231 assert(get_irg_link(n));
232 return ((scc_info *)n->link)->uplink;
236 set_irg_dfn (ir_graph *n, int dfn) {
237 assert(get_irg_link(n));
238 ((scc_info *)n->link)->dfn = dfn;
242 get_irg_dfn (ir_graph *n) {
243 assert(get_irg_link(n));
244 return ((scc_info *)n->link)->dfn;
247 /**********************************************************************/
249 /**********************************************************************/
251 static ir_graph **stack = NULL;
252 static int tos = 0; /* top of stack */
254 static INLINE void init_stack(void) {
256 ARR_RESIZE (ir_graph *, stack, 1000);
258 stack = NEW_ARR_F (ir_graph *, 1000);
267 if (tos == ARR_LEN (stack)) {
268 int nlen = ARR_LEN (stack) * 2;
269 ARR_RESIZE (ir_node *, stack, nlen);
272 mark_irg_in_stack(n);
275 static INLINE ir_graph *
278 ir_graph *n = stack[--tos];
279 mark_irg_not_in_stack(n);
283 /* The nodes up to n belong to the current loop.
284 Removes them from the stack and adds them to the current loop. */
286 pop_scc_to_loop (ir_graph *n)
294 set_irg_dfn(m, loop_node_cnt);
295 add_loop_node(current_loop, (ir_node *)m);
296 set_irg_loop(m, current_loop);
297 /* if (m==n) break;*/
301 /* GL ??? my last son is my grandson??? Removes cfloops with no
302 ir_nodes in them. Such loops have only another loop as son. (Why
303 can't they have two loops as sons? Does it never get that far? ) */
304 static void close_loop (ir_loop *l)
306 int last = get_loop_n_elements(l) - 1;
307 loop_element lelement = get_loop_element(l, last);
308 ir_loop *last_son = lelement.son;
310 if (get_kind(last_son) == k_ir_loop &&
311 get_loop_n_elements(last_son) == 1) {
314 lelement = get_loop_element(last_son, 0);
316 if(get_kind(gson) == k_ir_loop) {
317 loop_element new_last_son;
319 gson -> outer_loop = l;
320 new_last_son.son = gson;
321 l -> children[last] = new_last_son;
328 /* Removes and unmarks all nodes up to n from the stack.
329 The nodes must be visited once more to assign them to a scc. */
331 pop_scc_unmark_visit (ir_graph *n)
337 set_cg_irg_visited(m, 0);
341 /**********************************************************************/
342 /* The loop datastructure. **/
343 /**********************************************************************/
345 /* Allocates a new loop as son of current_loop. Sets current_loop
346 to the new loop and returns the father. */
347 static ir_loop *new_loop (void) {
348 ir_loop *father, *son;
350 father = current_loop;
352 son = (ir_loop *) obstack_alloc (outermost_ir_graph->obst, sizeof (ir_loop));
353 memset (son, 0, sizeof (ir_loop));
354 son->kind = k_ir_loop;
355 son->children = NEW_ARR_F (loop_element, 0);
359 son->outer_loop = father;
360 add_loop_son(father, son);
361 son->depth = father->depth+1;
362 } else { /* The root loop */
363 son->outer_loop = son;
368 son->loop_nr = get_irp_new_node_nr();
376 /**********************************************************************/
377 /* Constructing and destructing the loop/backedge information. **/
378 /**********************************************************************/
380 /* Initialization steps. **********************************************/
383 init_scc (ir_graph *irg) {
388 for (i = 0; i < get_irp_n_irgs(); ++i) {
389 set_irg_link(get_irp_irg(i), new_scc_info());
393 /** Returns true if n is a loop header, i.e., it is a Block node
394 * and has predecessors within the cfloop and out of the cfloop.
396 * @param root: only needed for assertion.
399 is_head (ir_graph *n, ir_graph *root)
402 int some_outof_loop = 0, some_in_loop = 0;
404 arity = get_irg_n_callees(n);
405 for (i = 0; i < arity; i++) {
406 ir_graph *pred = get_irg_callee(n, i);
407 if (is_irg_callee_backedge(n, i)) continue;
408 if (!irg_is_in_stack(pred)) {
411 if (get_irg_uplink(pred) < get_irg_uplink(root)) {
412 DDMG(pred); DDMG(root);
413 assert(get_irg_uplink(pred) >= get_irg_uplink(root));
419 return some_outof_loop && some_in_loop;
421 /* Returns true if n is possible loop head of an endless loop.
422 I.e., it is a Block, Phi or Filter node and has only predecessors
424 @arg root: only needed for assertion. */
426 is_endless_head (ir_graph *n, ir_graph *root)
429 int some_outof_loop = 0, some_in_loop = 0;
431 arity = get_irg_n_callees(n);
432 for (i = 0; i < arity; i++) {
433 ir_graph *pred = get_irg_callee(n, i);
435 if (is_irg_callee_backedge(n, i)) { continue; }
436 if (!irg_is_in_stack(pred)) {
439 if(get_irg_uplink(pred) < get_irg_uplink(root)) {
440 DDMG(pred); DDMG(root);
441 assert(get_irg_uplink(pred) >= get_irg_uplink(root));
447 return !some_outof_loop && some_in_loop;
450 /* Returns index of the predecessor with the smallest dfn number
451 greater-equal than limit. */
453 smallest_dfn_pred (ir_graph *n, int limit)
455 int i, index = -2, min = -1;
457 int arity = get_irg_n_callees(n);
458 for (i = 0; i < arity; i++) {
459 ir_graph *pred = get_irg_callee(n, i);
460 if (is_irg_callee_backedge(n, i) || !irg_is_in_stack(pred)) continue;
461 if (get_irg_dfn(pred) >= limit && (min == -1 || get_irg_dfn(pred) < min)) {
463 min = get_irg_dfn(pred);
470 /* Returns index of the predecessor with the largest dfn number. */
472 largest_dfn_pred (ir_graph *n)
474 int i, index = -2, max = -1;
476 int arity = get_irg_n_callees(n);
477 for (i = 0; i < arity; i++) {
478 ir_graph *pred = get_irg_callee(n, i);
479 if (is_irg_callee_backedge (n, i) || !irg_is_in_stack(pred)) continue;
480 if (get_irg_dfn(pred) > max) {
482 max = get_irg_dfn(pred);
490 find_tail (ir_graph *n) {
492 int i, res_index = -2;
495 if (!icfg && rm_cyclic_phis && remove_cyclic_phis (n)) return NULL;
497 m = stack[tos-1]; /* tos = top of stack */
498 if (is_head (m, n)) {
499 res_index = smallest_dfn_pred(m, 0);
500 if ((res_index == -2) && /* no smallest dfn pred found. */
504 if (m == n) return NULL; // Is this to catch Phi - self loops?
505 for (i = tos-2; i >= 0; --i) {
508 if (is_head (m, n)) {
509 res_index = smallest_dfn_pred (m, get_irg_dfn(m) + 1);
510 if (res_index == -2) /* no smallest dfn pred found. */
511 res_index = largest_dfn_pred (m);
513 if ((m == n) && (res_index == -2)) {
519 /* We should not walk past our selves on the stack: The upcoming nodes
520 are not in this loop. We assume a loop not reachable from Start. */
529 /* A dead loop not reachable from Start. */
530 for (i = tos-2; i >= 0; --i) {
532 if (is_endless_head (m, n)) {
533 res_index = smallest_dfn_pred (m, get_irg_dfn(m) + 1);
534 if (res_index == -2) /* no smallest dfn pred found. */
535 res_index = largest_dfn_pred (m);
538 if (m == n) { break; } /* It's not an unreachable loop, either. */
540 //assert(0 && "no head found on stack");
544 assert (res_index > -2);
546 set_irg_callee_backedge (m, res_index);
547 return get_irg_callee(m, res_index);
552 /*-----------------------------------------------------------*
553 * The core algorithm. *
554 *-----------------------------------------------------------*/
557 static void cgscc (ir_graph *n) {
560 if (cg_irg_visited(n)) return;
561 mark_cg_irg_visited(n);
563 /* Initialize the node */
564 set_irg_dfn(n, current_dfn); /* Depth first number for this node */
565 set_irg_uplink(n, current_dfn); /* ... is default uplink. */
566 set_irg_loop(n, NULL);
570 int arity = get_irg_n_callees(n);
572 for (i = 0; i < arity; i++) {
574 if (is_irg_callee_backedge(n, i)) continue;
575 m = get_irg_callee(n, i);
577 /** This marks the backedge, but does it guarantee a correct loop tree? */
578 if (m == n) { set_irg_callee_backedge(n, i); continue; }
581 if (irg_is_in_stack(m)) {
582 /* Uplink of m is smaller if n->m is a backedge.
583 Propagate the uplink to mark the cfloop. */
584 if (get_irg_uplink(m) < get_irg_uplink(n))
585 set_irg_uplink(n, get_irg_uplink(m));
589 if (get_irg_dfn(n) == get_irg_uplink(n)) {
590 /* This condition holds for
591 1) the node with the incoming backedge.
592 That is: We found a cfloop!
593 2) Straight line code, because no uplink has been propagated, so the
594 uplink still is the same as the dfn.
596 But n might not be a proper cfloop head for the analysis. Proper cfloop
597 heads are Block and Phi nodes. find_tail searches the stack for
598 Block's and Phi's and takes those nodes as cfloop heads for the current
599 cfloop instead and marks the incoming edge as backedge. */
601 ir_graph *tail = find_tail(n);
603 /* We have a cfloop, that is no straight line code,
604 because we found a cfloop head!
605 Next actions: Open a new cfloop on the cfloop tree and
606 try to find inner cfloops */
609 ir_loop *l = new_loop();
611 /* Remove the cfloop from the stack ... */
612 pop_scc_unmark_visit (n);
614 /* The current backedge has been marked, that is temporarily eliminated,
615 by find tail. Start the scc algorithm
616 anew on the subgraph thats left (the current cfloop without the backedge)
617 in order to find more inner cfloops. */
621 assert (cg_irg_visited(n));
631 static void reset_isbe(void) {
632 int i, n_irgs = get_irp_n_irgs();
634 for (i = 0; i < n_irgs; ++i) {
636 ir_graph *irg = get_irp_irg(i);
638 n_cs = get_irg_n_callers(irg);
639 for (j = 0; j < n_cs; ++j) {
640 irg->caller_isbe[j] = 0;
642 n_cs = get_irg_n_callees(irg);
643 for (j = 0; j < n_cs; ++j) {
644 irg->callee_isbe[j] = 0;
649 /* Compute the backedges that represent recursions. */
650 void find_callgraph_recursions(void) {
651 int i, n_irgs = get_irp_n_irgs();
655 assert(get_irp_main_irg()); /* The outermost graph. We start here. Then we start at all
656 external visible functions in irg list, then at the remaining
658 outermost_ir_graph = get_irp_main_irg();
660 assert(!interprocedural_view &&
661 "use construct_ip_backedges");
663 init_scc(current_ir_graph);
666 new_loop(); /* sets current_loop */
668 cgscc(outermost_ir_graph);
670 for (i = 0; i < n_irgs; i++) {
671 ir_graph *irg = get_irp_irg(i);
672 if (!cg_irg_visited(irg) && get_irg_n_callers(irg) == 0)
675 for (i = 0; i < n_irgs; i++) {
676 ir_graph *irg = get_irp_irg(i);
677 if (!cg_irg_visited(irg))
681 /* We can not use the looptree -- it has no real meaning.
682 There is a working dumper, but commented out.
683 assert(current_loop && current_loop == get_loop_outer_loop(current_loop));
684 dump_callgraph_loop_tree(current_loop, ""); */