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 /* For callees, we want to remember the Call nodes, too. */
33 typedef struct ana_entry ana_entry;
35 static int master_cg_visited = 0;
36 static INLINE int cg_irg_visited (ir_graph *n);
37 static INLINE void mark_cg_irg_visited(ir_graph *n);
38 static INLINE void set_cg_irg_visited (ir_graph *n, int i);
40 irp_callgraph_state get_irp_callgraph_state(void) {
41 return irp->callgraph_state;
43 void set_irp_callgraph_state(irp_callgraph_state s) {
44 irp->callgraph_state = s;
47 /* The functions that call irg. */
48 int get_irg_n_callers(ir_graph *irg) {
49 if (irg->callers) return ARR_LEN(irg->callers);
52 ir_graph *get_irg_caller(ir_graph *irg, int pos) {
53 assert (pos >= 0 && pos < get_irg_n_callers(irg));
54 if (irg->callers) return irg->callers[pos];
57 int is_irg_caller_backedge(ir_graph *irg, int pos) {
58 assert (pos >= 0 && pos < get_irg_n_callers(irg));
59 return irg->caller_isbe[pos];
62 static void set_irg_caller_backedge(ir_graph *irg, ir_graph *caller) {
63 int i, n_callers = get_irg_n_callers(irg);
64 for (i = 0; i < n_callers; ++i) {
65 if (get_irg_caller(irg, i) == caller) {
66 irg->caller_isbe[i] = 1;
72 int has_irg_caller_backedge(ir_graph *irg) {
73 int i, n_callers = get_irg_n_callers(irg);
74 for (i = 0; i < n_callers; ++i)
75 if (is_irg_caller_backedge(irg, i)) return 1;
79 int get_irg_caller_loop_depth(ir_graph *irg, int pos) {
80 ir_graph *caller = get_irg_caller(irg, pos);
82 /* search the other relation for the corresponding edge. */
84 int i, n_callees = get_irg_n_callees(caller);
85 for (i = 0; i < n_callees; ++i) {
86 if (get_irg_callee(caller, i) == irg) {
92 assert(pos_callee >= 0);
94 return get_irg_callee_loop_depth(caller, pos_callee);
98 /* The functions called by irg. */
99 int get_irg_n_callees(ir_graph *irg) {
100 if (irg->callees) return ARR_LEN(irg->callees);
103 ir_graph *get_irg_callee(ir_graph *irg, int pos) {
104 assert (pos >= 0 && pos < get_irg_n_callees(irg));
105 if (irg->callees) return ((ana_entry *)irg->callees[pos])->irg;
108 int is_irg_callee_backedge(ir_graph *irg, int pos) {
109 assert (pos >= 0 && pos < get_irg_n_callees(irg));
110 return irg->callee_isbe[pos];
112 int has_irg_callee_backedge(ir_graph *irg) {
113 int i, n_callees = get_irg_n_callees(irg);
114 for (i = 0; i < n_callees; ++i)
115 if (is_irg_callee_backedge(irg, i)) return 1;
118 void set_irg_callee_backedge(ir_graph *irg, int pos) {
119 assert (pos >= 0 && pos < get_irg_n_callees(irg));
120 irg->callee_isbe[pos] = 1;
123 int get_irg_callee_loop_depth(ir_graph *irg, int pos) {
124 assert (pos >= 0 && pos < get_irg_n_callees(irg));
125 if (irg->callees) return ((ana_entry *)irg->callees[pos])->max_depth;
129 /* --------------------- Compute the callgraph ------------------------ */
132 static void ana_Call(ir_node *n, void *env) {
136 if (get_irn_op(n) != op_Call) return;
138 irg = get_irn_irg(n);
139 n_callees = get_Call_n_callees(n);
140 for (i = 0; i < n_callees; ++i) {
141 entity *callee_e = get_Call_callee(n, i);
142 if (callee_e) { /* Null for unknown caller */
143 ir_graph *callee = get_entity_irg(callee_e);
144 pset_insert((pset *)callee->callers, irg, (unsigned)irg >> 3);
146 ana_entry buf = { callee, NULL, 0};
147 ana_entry *found = pset_find((pset *)irg->callees, &buf, (unsigned)callee >> 3);
148 if (found) { /* add Call node to list, compute new nesting. */
149 } else { /* New node, add Call node and init nesting. */
150 found = (ana_entry *) obstack_alloc (irg->obst, sizeof (ana_entry));
152 found->call_list = NULL;
153 found->max_depth = 0;
154 pset_insert((pset *)irg->callees, found, (unsigned)callee >> 3);
156 int depth = get_loop_depth(get_irn_loop(get_nodes_block(n)));
157 found->max_depth = (depth > found->max_depth) ? depth : found->max_depth;
162 /* compare two ir graphs */
163 static int ana_entry_cmp(const void *elt, const void *key) {
164 ana_entry *e1 = (ana_entry *)elt;
165 ana_entry *e2 = (ana_entry *)key;
166 return e1->irg != e2->irg;
169 /* compare two ir graphs */
170 static int graph_cmp(const void *elt, const void *key) {
175 /* Construct and destruct the callgraph. */
176 void compute_callgraph(void) {
177 int i, n_irgs = get_irp_n_irgs();
179 assert(interprocedural_view == 0); /* Else walking will not reach the Call nodes. */
183 for (i = 0; i < n_irgs; ++i) {
184 ir_graph *irg = get_irp_irg(i);
185 assert(get_irg_callee_info_state(irg) == irg_callee_info_consistent);
186 irg->callees = (ir_graph **)new_pset(ana_entry_cmp, 8);
187 irg->callers = (ir_graph **)new_pset(graph_cmp, 8);
188 construct_cf_backedges(irg);
191 /* Compute the call graph */
192 for (i = 0; i < n_irgs; ++i) {
193 ir_graph *irg = get_irp_irg(i);
194 construct_cf_backedges(irg);
195 irg_walk_graph(irg, ana_Call, NULL, NULL);
198 /* Change the sets to arrays. */
199 for (i = 0; i < n_irgs; ++i) {
201 ir_graph *c, *irg = get_irp_irg(i);
203 pset *callee_set = (pset *)irg->callees;
204 count = pset_count(callee_set);
205 irg->callees = NEW_ARR_F(ir_graph *, count);
206 irg->callee_isbe = calloc(count, sizeof(int));
207 c = pset_first(callee_set);
208 for (j = 0; j < count; ++j) {
210 c = pset_next(callee_set);
212 del_pset(callee_set);
215 pset *caller_set = (pset *)irg->callers;
216 count = pset_count(caller_set);
217 irg->callers = NEW_ARR_F(ir_graph *, count);
218 irg->caller_isbe = calloc(count, sizeof(int));
219 c = pset_first(caller_set);
220 for (j = 0; j < count; ++j) {
222 c = pset_next(caller_set);
224 del_pset(caller_set);
227 set_irp_callgraph_state(irp_callgraph_consistent);
230 void free_callgraph(void) {
231 int i, n_irgs = get_irp_n_irgs();
232 for (i = 0; i < n_irgs; ++i) {
233 ir_graph *irg = get_irp_irg(i);
234 if (irg->callees) DEL_ARR_F(irg->callees);
235 if (irg->callers) DEL_ARR_F(irg->callers);
236 if (irg->callee_isbe) DEL_ARR_F(irg->callee_isbe);
237 if (irg->caller_isbe) DEL_ARR_F(irg->caller_isbe);
240 irg->callee_isbe = NULL;
241 irg->caller_isbe = NULL;
243 set_irp_callgraph_state(irp_callgraph_none);
246 /* ----------------------------------------------------------------------------------- */
247 /* A walker for the callgraph */
248 /* ----------------------------------------------------------------------------------- */
251 static void do_walk(ir_graph *irg, callgraph_walk_func *pre, callgraph_walk_func *post, void *env) {
254 if (cg_irg_visited(irg)) return;
255 mark_cg_irg_visited(irg);
259 n_callees = get_irg_n_callees(irg);
260 for (i = 0; i < n_callees; i++) {
261 ir_graph *m = get_irg_callee(irg, i);
262 do_walk(m, pre, post, env);
268 void callgraph_walk(callgraph_walk_func *pre, callgraph_walk_func *post, void *env) {
269 int i, n_irgs = get_irp_n_irgs();
272 do_walk(get_irp_main_irg(), pre, post, env);
273 for (i = 0; i < n_irgs; i++) {
274 ir_graph *irg = get_irp_irg(i);
275 if (!cg_irg_visited(irg) && get_irg_n_callers(irg) == 0)
276 do_walk(irg, pre, post, env);
278 for (i = 0; i < n_irgs; i++) {
279 ir_graph *irg = get_irp_irg(i);
280 if (!cg_irg_visited(irg))
281 do_walk(irg, pre, post, env);
285 /* ----------------------------------------------------------------------------------- */
286 /* loop construction algorithm */
287 /* ----------------------------------------------------------------------------------- */
289 static ir_graph *outermost_ir_graph; /* The outermost graph the scc is computed
291 static ir_loop *current_loop; /* Current cfloop construction is working
293 static int loop_node_cnt = 0; /* Counts the number of allocated cfloop nodes.
294 Each cfloop node gets a unique number.
295 What for? ev. remove. @@@ */
296 static int current_dfn = 1; /* Counter to generate depth first numbering
300 /**********************************************************************/
301 /* Node attributes **/
302 /**********************************************************************/
304 typedef struct scc_info {
305 bool in_stack; /* Marks whether node is on the stack. */
306 int dfn; /* Depth first search number. */
307 int uplink; /* dfn number of ancestor. */
311 static INLINE scc_info* new_scc_info(void) {
312 scc_info *info = obstack_alloc (outermost_ir_graph->obst, sizeof (scc_info));
313 memset (info, 0, sizeof (scc_info));
318 cg_irg_visited(ir_graph *n) {
319 return (((scc_info *)n->link)->visited >= master_cg_visited);
323 mark_cg_irg_visited(ir_graph *n) {
324 ((scc_info *)n->link)->visited = master_cg_visited;
328 set_cg_irg_visited(ir_graph *n, int i) {
329 ((scc_info *)n->link)->visited = i;
333 get_cg_irg_visited(ir_graph *n) {
334 return ((scc_info *)n->link)->visited;
338 mark_irg_in_stack (ir_graph *n) {
339 assert(get_irg_link(n));
340 ((scc_info *)n->link)->in_stack = true;
344 mark_irg_not_in_stack (ir_graph *n) {
345 assert(get_irg_link(n));
346 ((scc_info *)n->link)->in_stack = false;
350 irg_is_in_stack (ir_graph *n) {
351 assert(get_irg_link(n));
352 return ((scc_info *)n->link)->in_stack;
356 set_irg_uplink (ir_graph *n, int uplink) {
357 assert(get_irg_link(n));
358 ((scc_info *)n->link)->uplink = uplink;
362 get_irg_uplink (ir_graph *n) {
363 assert(get_irg_link(n));
364 return ((scc_info *)n->link)->uplink;
368 set_irg_dfn (ir_graph *n, int dfn) {
369 assert(get_irg_link(n));
370 ((scc_info *)n->link)->dfn = dfn;
374 get_irg_dfn (ir_graph *n) {
375 assert(get_irg_link(n));
376 return ((scc_info *)n->link)->dfn;
379 /**********************************************************************/
381 /**********************************************************************/
383 static ir_graph **stack = NULL;
384 static int tos = 0; /* top of stack */
386 static INLINE void init_stack(void) {
388 ARR_RESIZE (ir_graph *, stack, 1000);
390 stack = NEW_ARR_F (ir_graph *, 1000);
399 if (tos == ARR_LEN (stack)) {
400 int nlen = ARR_LEN (stack) * 2;
401 ARR_RESIZE (ir_node *, stack, nlen);
404 mark_irg_in_stack(n);
407 static INLINE ir_graph *
410 ir_graph *n = stack[--tos];
411 mark_irg_not_in_stack(n);
415 /* The nodes up to n belong to the current loop.
416 Removes them from the stack and adds them to the current loop. */
418 pop_scc_to_loop (ir_graph *n)
425 set_irg_dfn(m, loop_node_cnt);
426 add_loop_node(current_loop, (ir_node *)m);
428 //m->callgraph_loop_depth = current_loop->depth;
432 /* GL ??? my last son is my grandson??? Removes cfloops with no
433 ir_nodes in them. Such loops have only another loop as son. (Why
434 can't they have two loops as sons? Does it never get that far? ) */
435 static void close_loop (ir_loop *l)
437 int last = get_loop_n_elements(l) - 1;
438 loop_element lelement = get_loop_element(l, last);
439 ir_loop *last_son = lelement.son;
441 if (get_kind(last_son) == k_ir_loop &&
442 get_loop_n_elements(last_son) == 1) {
445 lelement = get_loop_element(last_son, 0);
447 if(get_kind(gson) == k_ir_loop) {
448 loop_element new_last_son;
450 gson -> outer_loop = l;
451 new_last_son.son = gson;
452 l -> children[last] = new_last_son;
459 /* Removes and unmarks all nodes up to n from the stack.
460 The nodes must be visited once more to assign them to a scc. */
462 pop_scc_unmark_visit (ir_graph *n)
468 set_cg_irg_visited(m, 0);
472 /**********************************************************************/
473 /* The loop datastructure. **/
474 /**********************************************************************/
476 /* Allocates a new loop as son of current_loop. Sets current_loop
477 to the new loop and returns the father. */
478 static ir_loop *new_loop (void) {
479 ir_loop *father, *son;
481 father = current_loop;
483 son = (ir_loop *) obstack_alloc (outermost_ir_graph->obst, sizeof (ir_loop));
484 memset (son, 0, sizeof (ir_loop));
485 son->kind = k_ir_loop;
486 son->children = NEW_ARR_F (loop_element, 0);
490 son->outer_loop = father;
491 add_loop_son(father, son);
492 son->depth = father->depth+1;
493 } else { /* The root loop */
494 son->outer_loop = son;
499 son->loop_nr = get_irp_new_node_nr();
507 /**********************************************************************/
508 /* Constructing and destructing the loop/backedge information. **/
509 /**********************************************************************/
511 /* Initialization steps. **********************************************/
519 for (i = 0; i < get_irp_n_irgs(); ++i) {
520 set_irg_link(get_irp_irg(i), new_scc_info());
521 get_irp_irg(i)->callgraph_recursion_depth = 0;
522 get_irp_irg(i)->callgraph_loop_depth = 0;
523 get_irp_irg(i)->callgraph_weighted_loop_depth = 0;
527 /** Returns true if n is a loop header, i.e., it is a Block node
528 * and has predecessors within the cfloop and out of the cfloop.
530 * @param root: only needed for assertion.
533 is_head (ir_graph *n, ir_graph *root)
536 int some_outof_loop = 0, some_in_loop = 0;
538 arity = get_irg_n_callees(n);
539 for (i = 0; i < arity; i++) {
540 ir_graph *pred = get_irg_callee(n, i);
541 if (is_irg_callee_backedge(n, i)) continue;
542 if (!irg_is_in_stack(pred)) {
545 if (get_irg_uplink(pred) < get_irg_uplink(root)) {
546 DDMG(pred); DDMG(root);
547 assert(get_irg_uplink(pred) >= get_irg_uplink(root));
553 return some_outof_loop && some_in_loop;
555 /* Returns true if n is possible loop head of an endless loop.
556 I.e., it is a Block, Phi or Filter node and has only predecessors
558 @arg root: only needed for assertion. */
560 is_endless_head (ir_graph *n, ir_graph *root)
563 int some_outof_loop = 0, some_in_loop = 0;
565 arity = get_irg_n_callees(n);
566 for (i = 0; i < arity; i++) {
567 ir_graph *pred = get_irg_callee(n, i);
569 if (is_irg_callee_backedge(n, i)) { continue; }
570 if (!irg_is_in_stack(pred)) {
573 if(get_irg_uplink(pred) < get_irg_uplink(root)) {
574 DDMG(pred); DDMG(root);
575 assert(get_irg_uplink(pred) >= get_irg_uplink(root));
581 return !some_outof_loop && some_in_loop;
585 /* Check whether there is a parallel edge in the ip control flow.
588 is_ip_head (ir_graph *n, ir_graph *pred)
590 int iv_rem = interprocedural_view;
591 interprocedural_view = 1;
592 ir_node *sblock = get_irg_start_block(n);
593 int i, arity = get_Block_n_cfgpreds(sblock);
596 //printf(" edge from "); DDMG(n);
597 //printf(" to pred "); DDMG(pred);
598 //printf(" sblock "); DDMN(sblock);
600 for (i = 0; i < arity; i++) {
601 ir_node *pred_cfop = skip_Proj(get_Block_cfgpred(sblock, i));
602 //printf(" "); DDMN(pred_cfop);
603 if (get_irn_op(pred_cfop) == op_CallBegin) { /* could be Unknown */
604 ir_graph *ip_pred = get_irn_irg(pred_cfop);
605 //printf(" "); DDMG(ip_pred);
606 if ((ip_pred == pred) && is_backedge(sblock, i)) {
607 //printf(" found\n");
613 interprocedural_view = iv_rem;
617 /* Returns index of the predecessor with the smallest dfn number
618 greater-equal than limit. */
620 smallest_dfn_pred (ir_graph *n, int limit)
622 int i, index = -2, min = -1;
624 int arity = get_irg_n_callees(n);
625 for (i = 0; i < arity; i++) {
626 ir_graph *pred = get_irg_callee(n, i);
627 if (is_irg_callee_backedge(n, i) || !irg_is_in_stack(pred)) continue;
628 if (get_irg_dfn(pred) >= limit && (min == -1 || get_irg_dfn(pred) < min)) {
630 min = get_irg_dfn(pred);
637 /* Returns index of the predecessor with the largest dfn number. */
639 largest_dfn_pred (ir_graph *n)
641 int i, index = -2, max = -1;
643 int arity = get_irg_n_callees(n);
644 for (i = 0; i < arity; i++) {
645 ir_graph *pred = get_irg_callee(n, i);
646 if (is_irg_callee_backedge (n, i) || !irg_is_in_stack(pred)) continue;
647 if (get_irg_dfn(pred) > max) {
649 max = get_irg_dfn(pred);
658 find_tail (ir_graph *n) {
660 int i, res_index = -2;
663 if (!icfg && rm_cyclic_phis && remove_cyclic_phis (n)) return NULL;
665 m = stack[tos-1]; /* tos = top of stack */
666 if (is_head (m, n)) {
667 res_index = smallest_dfn_pred(m, 0);
668 if ((res_index == -2) && /* no smallest dfn pred found. */
672 if (m == n) return NULL; // Is this to catch Phi - self loops?
673 for (i = tos-2; i >= 0; --i) {
676 if (is_head (m, n)) {
677 res_index = smallest_dfn_pred (m, get_irg_dfn(m) + 1);
678 if (res_index == -2) /* no smallest dfn pred found. */
679 res_index = largest_dfn_pred (m);
681 if ((m == n) && (res_index == -2)) {
687 /* We should not walk past our selves on the stack: The upcoming nodes
688 are not in this loop. We assume a loop not reachable from Start. */
697 /* A dead loop not reachable from Start. */
698 for (i = tos-2; i >= 0; --i) {
700 if (is_endless_head (m, n)) {
701 res_index = smallest_dfn_pred (m, get_irg_dfn(m) + 1);
702 if (res_index == -2) /* no smallest dfn pred found. */
703 res_index = largest_dfn_pred (m);
706 if (m == n) { break; } /* It's not an unreachable loop, either. */
708 //assert(0 && "no head found on stack");
712 assert (res_index > -2);
714 set_irg_callee_backedge (m, res_index);
715 return get_irg_callee(m, res_index);
719 find_tail (ir_graph *n) {
721 int i, res_index = -2;
723 ir_graph *in_and_out = NULL;
724 ir_graph *only_in = NULL;
725 ir_graph *ip_in_and_out = NULL;
726 ir_graph *ip_only_in = NULL;
728 //printf("find tail for "); DDMG(n);
730 for (i = tos-1; i >= 0; --i) {
731 ir_graph *pred = (i < tos -1) ? stack[i+1] : n;
734 if (is_head (m, n)) {
735 //printf(" found 1a! "); DDM;
737 if (is_ip_head(pred, m)) {
738 //printf(" found 1b! "); DDM;
741 } else if (!ip_only_in && is_endless_head(m, n)) {
743 //printf(" found 2a! "); DDM;
744 if (is_ip_head(pred, m)) {
745 //printf(" found 2b! "); DDM;
748 } else if (is_ip_head(pred, m)) {
749 //printf(" found 3! "); DDM; This happens for self recursions in the second
750 //assert(0); scc iteration (the one to flip the loop.)
753 if (ip_in_and_out) break; /* That's what we really want. */
755 if (m == n) break; /* Don't walk past n on the stack! */
759 if (!in_and_out && !only_in)
760 /* There is no loop */
764 /* Is there a head in the callgraph without a head in the
766 assert(in_and_out || only_in);
768 m = (ip_in_and_out) ? ip_in_and_out : ip_only_in;
771 m = (in_and_out) ? in_and_out : only_in;
773 //printf("*** head is "); DDMG(m);
775 res_index = smallest_dfn_pred (m, get_irg_dfn(m) + 1);
776 if (res_index == -2) /* no smallest dfn pred found. */
777 res_index = largest_dfn_pred (m);
779 set_irg_callee_backedge (m, res_index);
780 ir_graph *res = get_irg_callee(m, res_index);
781 //printf("*** tail is "); DDMG(res);
787 /*-----------------------------------------------------------*
788 * The core algorithm. *
789 *-----------------------------------------------------------*/
792 static void cgscc (ir_graph *n) {
795 if (cg_irg_visited(n)) return;
796 mark_cg_irg_visited(n);
798 /* Initialize the node */
799 set_irg_dfn(n, current_dfn); /* Depth first number for this node */
800 set_irg_uplink(n, current_dfn); /* ... is default uplink. */
804 int arity = get_irg_n_callees(n);
806 for (i = 0; i < arity; i++) {
808 if (is_irg_callee_backedge(n, i)) continue;
809 m = get_irg_callee(n, i);
811 /** This marks the backedge, but does it guarantee a correct loop tree? */
812 //if (m == n) { set_irg_callee_backedge(n, i); continue; }
815 if (irg_is_in_stack(m)) {
816 /* Uplink of m is smaller if n->m is a backedge.
817 Propagate the uplink to mark the cfloop. */
818 if (get_irg_uplink(m) < get_irg_uplink(n))
819 set_irg_uplink(n, get_irg_uplink(m));
823 if (get_irg_dfn(n) == get_irg_uplink(n)) {
824 /* This condition holds for
825 1) the node with the incoming backedge.
826 That is: We found a cfloop!
827 2) Straight line code, because no uplink has been propagated, so the
828 uplink still is the same as the dfn.
830 But n might not be a proper cfloop head for the analysis. Proper cfloop
831 heads are Block and Phi nodes. find_tail searches the stack for
832 Block's and Phi's and takes those nodes as cfloop heads for the current
833 cfloop instead and marks the incoming edge as backedge. */
835 ir_graph *tail = find_tail(n);
837 /* We have a cfloop, that is no straight line code,
838 because we found a cfloop head!
839 Next actions: Open a new cfloop on the cfloop tree and
840 try to find inner cfloops */
843 ir_loop *l = new_loop();
845 /* Remove the cfloop from the stack ... */
846 pop_scc_unmark_visit (n);
848 /* The current backedge has been marked, that is temporarily eliminated,
849 by find tail. Start the scc algorithm
850 anew on the subgraph thats left (the current cfloop without the backedge)
851 in order to find more inner cfloops. */
855 assert (cg_irg_visited(n));
865 static void reset_isbe(void) {
866 int i, n_irgs = get_irp_n_irgs();
868 for (i = 0; i < n_irgs; ++i) {
870 ir_graph *irg = get_irp_irg(i);
872 n_cs = get_irg_n_callers(irg);
873 for (j = 0; j < n_cs; ++j) {
874 irg->caller_isbe[j] = 0;
876 n_cs = get_irg_n_callees(irg);
877 for (j = 0; j < n_cs; ++j) {
878 irg->callee_isbe[j] = 0;
886 /* ----------------------------------------------------------------------------------- */
887 /* Another algorithm to compute recursion nesting depth */
888 /* Walk the callgraph. For each crossed edge increase the loop depth by the edge */
889 /* weight. Assign graphs the maximal depth. */
890 /* ----------------------------------------------------------------------------------- */
892 void compute_loop_depth (ir_graph *irg, void *env) {
893 int current_nesting = *(int *) env;
896 if (cg_irg_visited(irg)) return;
897 mark_cg_irg_visited(irg);
899 if (current_nesting == 0 || irg->callgraph_loop_depth < current_nesting) {
900 /* Don't walk the graph, but a tree that is an unfolded graph. */
901 n_callees = get_irg_n_callees(irg);
902 for (i = 0; i < n_callees; i++) {
903 ir_graph *m = get_irg_callee(irg, i);
904 *(int *)env += get_irg_callee_loop_depth(irg, i);
905 compute_loop_depth(m, env);
906 *(int *)env -= get_irg_callee_loop_depth(irg, i);
910 if (irg->callgraph_loop_depth < current_nesting)
911 irg->callgraph_loop_depth = current_nesting;
913 set_cg_irg_visited(irg, master_cg_visited-1);
917 /* ----------------------------------------------------------------------------------- */
918 /* Another algorithm to compute recursion nesting depth */
919 /* Walk the callgraph. For each crossed loop increase the nesting depth by one. */
920 /* Assign graphs the maximal nesting depth. Don't increas if passing loops more than */
922 /* ----------------------------------------------------------------------------------- */
925 /* For callees, we want to remember the Call nodes, too. */
927 ir_loop **loop_stack;
929 int recursion_nesting;
932 typedef struct ana_entry2 ana_entry2;
934 static void push2(ana_entry2 *e, ir_loop *g) {
935 if (ARR_LEN(e->loop_stack) == e->tos) {
936 ARR_APP1(ir_loop *, e->loop_stack, g);
938 e->loop_stack[e->tos] = g;
943 static ir_loop *pop2(ana_entry2 *e) {
945 return e->loop_stack[e->tos+1];
948 static int in_stack(ana_entry2 *e, ir_loop *g) {
950 for (i = e->tos-1; i >= 0; --i) {
951 if (e->loop_stack[i] == g) return 1;
956 void compute_rec_depth (ir_graph *irg, void *env) {
957 ana_entry2 *e = (ana_entry2 *)env;
963 if (cg_irg_visited(irg)) return;
964 mark_cg_irg_visited(irg);
966 if ((l != irp->outermost_cg_loop) && !in_stack(e, l)) {
968 e->recursion_nesting++;
971 depth = e->recursion_nesting;
973 if (depth == 0 || irg->callgraph_recursion_depth < depth) {
974 /* Don't walk the graph, but a tree that is an unfolded graph. */
975 n_callees = get_irg_n_callees(irg);
976 for (i = 0; i < n_callees; i++) {
977 ir_graph *m = get_irg_callee(irg, i);
978 compute_rec_depth(m, env);
982 if (irg->callgraph_recursion_depth < depth)
983 irg->callgraph_recursion_depth = depth;
987 e->recursion_nesting--;
989 set_cg_irg_visited(irg, master_cg_visited-1);
993 /* Compute the backedges that represent recursions. */
994 void find_callgraph_recursions(void) {
995 int i, n_irgs = get_irp_n_irgs();
999 /* -- Compute the looptree -- */
1001 /* The outermost graph. We start here. Then we start at all
1002 functions in irg list that are never called, then at the remaining
1004 assert(get_irp_main_irg());
1005 outermost_ir_graph = get_irp_main_irg();
1008 current_loop = NULL;
1009 new_loop(); /* sets current_loop */
1011 master_cg_visited++;
1012 cgscc(outermost_ir_graph);
1013 for (i = 0; i < n_irgs; i++) {
1014 ir_graph *irg = get_irp_irg(i);
1015 if (!cg_irg_visited(irg) && get_irg_n_callers(irg) == 0)
1018 for (i = 0; i < n_irgs; i++) {
1019 ir_graph *irg = get_irp_irg(i);
1020 if (!cg_irg_visited(irg))
1023 irp->outermost_cg_loop = current_loop;
1025 /* -- Reverse the backedge information. -- */
1026 for (i = 0; i < n_irgs; i++) {
1027 ir_graph *irg = get_irp_irg(i);
1028 int j, n_callees = get_irg_n_callees(irg);
1029 for (j = 0; j < n_callees; ++j) {
1030 if (is_irg_callee_backedge(irg, j))
1031 set_irg_caller_backedge(get_irg_callee(irg, j), irg);
1035 /* -- Schleifentiefe berechnen -- */
1036 int current_nesting = 0;
1037 master_cg_visited += 2;
1038 compute_loop_depth(get_irp_main_irg(), ¤t_nesting);
1039 for (i = 0; i < n_irgs; i++) {
1040 ir_graph *irg = get_irp_irg(i);
1041 if (!cg_irg_visited(irg) && get_irg_n_callers(irg) == 0)
1042 compute_loop_depth(irg, ¤t_nesting);
1044 for (i = 0; i < n_irgs; i++) {
1045 ir_graph *irg = get_irp_irg(i);
1046 if (get_cg_irg_visited(irg) < master_cg_visited-1)
1047 compute_loop_depth(irg, ¤t_nesting);
1050 /* -- Rekursionstiefe berechnen -- */
1052 e.loop_stack = NEW_ARR_F(ir_loop *, 0);
1054 e.recursion_nesting = 0;
1056 master_cg_visited += 2;
1057 compute_rec_depth(get_irp_main_irg(), &e);
1058 for (i = 0; i < n_irgs; i++) {
1059 ir_graph *irg = get_irp_irg(i);
1060 if (!cg_irg_visited(irg) && get_irg_n_callers(irg) == 0)
1061 compute_rec_depth(irg, &e);
1063 for (i = 0; i < n_irgs; i++) {
1064 ir_graph *irg = get_irp_irg(i);
1065 if (get_cg_irg_visited(irg) < master_cg_visited-1)
1066 compute_rec_depth(irg, &e);
1069 DEL_ARR_F(e.loop_stack);
1071 //dump_callgraph("-with_nesting");
1073 //dump_callgraph_loop_tree(current_loop, "-after_cons");
1074 irp->callgraph_state = irp_callgraph_and_calltree_consistent;
1077 /* Maximal loop depth of all paths from an external visible method to
1079 int get_irg_loop_depth(ir_graph *irg) {
1080 assert(irp->callgraph_state == irp_callgraph_consistent ||
1081 irp->callgraph_state == irp_callgraph_and_calltree_consistent);
1082 return irg->callgraph_loop_depth;
1085 /* Maximal recursion depth of all paths from an external visible method to
1087 int get_irg_recursion_depth(ir_graph *irg) {
1088 assert(irp->callgraph_state == irp_callgraph_and_calltree_consistent);
1089 return irg->callgraph_recursion_depth;