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"
28 /* For callees, we want to remember the Call nodes, too. */
35 typedef struct ana_entry ana_entry;
37 static int master_cg_visited = 0;
38 static INLINE int cg_irg_visited (ir_graph *n);
39 static INLINE void mark_cg_irg_visited(ir_graph *n);
40 static INLINE void set_cg_irg_visited (ir_graph *n, int i);
42 irp_callgraph_state get_irp_callgraph_state(void) {
43 return irp->callgraph_state;
45 void set_irp_callgraph_state(irp_callgraph_state s) {
46 irp->callgraph_state = s;
49 /* The functions that call irg. */
50 int get_irg_n_callers(ir_graph *irg) {
51 if (irg->callers) return ARR_LEN(irg->callers);
54 ir_graph *get_irg_caller(ir_graph *irg, int pos) {
55 assert (pos >= 0 && pos < get_irg_n_callers(irg));
56 if (irg->callers) return irg->callers[pos];
59 int is_irg_caller_backedge(ir_graph *irg, int pos) {
60 assert (pos >= 0 && pos < get_irg_n_callers(irg));
61 return irg->caller_isbe[pos];
64 static void set_irg_caller_backedge(ir_graph *irg, ir_graph *caller) {
65 int i, n_callers = get_irg_n_callers(irg);
66 for (i = 0; i < n_callers; ++i) {
67 if (get_irg_caller(irg, i) == caller) {
68 irg->caller_isbe[i] = 1;
74 int has_irg_caller_backedge(ir_graph *irg) {
75 int i, n_callers = get_irg_n_callers(irg);
76 for (i = 0; i < n_callers; ++i)
77 if (is_irg_caller_backedge(irg, i)) return 1;
81 int get_irg_caller_loop_depth(ir_graph *irg, int pos) {
82 ir_graph *caller = get_irg_caller(irg, pos);
84 /* search the other relation for the corresponding edge. */
86 int i, n_callees = get_irg_n_callees(caller);
87 for (i = 0; i < n_callees; ++i) {
88 if (get_irg_callee(caller, i) == irg) {
94 assert(pos_callee >= 0);
96 return get_irg_callee_loop_depth(caller, pos_callee);
100 /* The functions called by irg. */
101 int get_irg_n_callees(ir_graph *irg) {
102 if (irg->callees) return ARR_LEN(irg->callees);
105 ir_graph *get_irg_callee(ir_graph *irg, int pos) {
106 assert (pos >= 0 && pos < get_irg_n_callees(irg));
107 if (irg->callees) return ((ana_entry *)irg->callees[pos])->irg;
110 int is_irg_callee_backedge(ir_graph *irg, int pos) {
111 assert (pos >= 0 && pos < get_irg_n_callees(irg));
112 return irg->callee_isbe[pos];
114 int has_irg_callee_backedge(ir_graph *irg) {
115 int i, n_callees = get_irg_n_callees(irg);
116 for (i = 0; i < n_callees; ++i)
117 if (is_irg_callee_backedge(irg, i)) return 1;
120 void set_irg_callee_backedge(ir_graph *irg, int pos) {
121 assert (pos >= 0 && pos < get_irg_n_callees(irg));
122 irg->callee_isbe[pos] = 1;
125 int get_irg_callee_loop_depth(ir_graph *irg, int pos) {
126 assert (pos >= 0 && pos < get_irg_n_callees(irg));
127 if (irg->callees) return ((ana_entry *)irg->callees[pos])->max_depth;
131 /* --------------------- Compute the callgraph ------------------------ */
133 /* Hash an address */
134 #define HASH_ADDRESS(adr) (((unsigned)(adr)) >> 3)
137 * Walker called by compute_callgraph()
139 static void ana_Call(ir_node *n, void *env) {
143 if (get_irn_op(n) != op_Call) return;
145 irg = get_irn_irg(n);
146 n_callees = get_Call_n_callees(n);
147 for (i = 0; i < n_callees; ++i) {
148 entity *callee_e = get_Call_callee(n, i);
149 if (callee_e != unknown_entity) { /* For unknown caller */
150 ir_graph *callee = get_entity_irg(callee_e);
151 pset_insert((pset *)callee->callers, irg, HASH_ADDRESS(irg));
153 ana_entry buf = { callee, NULL, 0};
154 ana_entry *found = pset_find((pset *)irg->callees, &buf, HASH_ADDRESS(callee));
155 if (found) { /* add Call node to list, compute new nesting. */
156 } else { /* New node, add Call node and init nesting. */
157 found = (ana_entry *) obstack_alloc (irg->obst, sizeof (ana_entry));
159 found->call_list = NULL;
160 found->max_depth = 0;
161 pset_insert((pset *)irg->callees, found, HASH_ADDRESS(callee));
163 int depth = get_loop_depth(get_irn_loop(get_nodes_block(n)));
164 found->max_depth = (depth > found->max_depth) ? depth : found->max_depth;
169 /** compare two ir graphs in a ana_entry */
170 static int ana_entry_cmp(const void *elt, const void *key) {
171 const ana_entry *e1 = elt;
172 const ana_entry *e2 = key;
173 return e1->irg != e2->irg;
176 /** compare two ir graphs */
177 static int graph_cmp(const void *elt, const void *key) {
182 /* Construct and destruct the callgraph. */
183 void compute_callgraph(void) {
184 int i, n_irgs = get_irp_n_irgs();
186 assert(! get_interprocedural_view()); /* Else walking will not reach the Call nodes. */
190 for (i = 0; i < n_irgs; ++i) {
191 ir_graph *irg = get_irp_irg(i);
192 assert(get_irg_callee_info_state(irg) == irg_callee_info_consistent);
193 irg->callees = (ir_graph **)new_pset(ana_entry_cmp, 8);
194 irg->callers = (ir_graph **)new_pset(graph_cmp, 8);
195 construct_cf_backedges(irg);
198 /* Compute the call graph */
199 for (i = 0; i < n_irgs; ++i) {
200 ir_graph *irg = get_irp_irg(i);
201 construct_cf_backedges(irg);
202 irg_walk_graph(irg, ana_Call, NULL, NULL);
205 /* Change the sets to arrays. */
206 for (i = 0; i < n_irgs; ++i) {
208 ir_graph *c, *irg = get_irp_irg(i);
210 pset *callee_set = (pset *)irg->callees;
211 count = pset_count(callee_set);
212 irg->callees = NEW_ARR_F(ir_graph *, count);
213 irg->callee_isbe = calloc(count, sizeof(int));
214 c = pset_first(callee_set);
215 for (j = 0; j < count; ++j) {
217 c = pset_next(callee_set);
219 del_pset(callee_set);
222 pset *caller_set = (pset *)irg->callers;
223 count = pset_count(caller_set);
224 irg->callers = NEW_ARR_F(ir_graph *, count);
225 irg->caller_isbe = calloc(count, sizeof(int));
226 c = pset_first(caller_set);
227 for (j = 0; j < count; ++j) {
229 c = pset_next(caller_set);
231 del_pset(caller_set);
234 set_irp_callgraph_state(irp_callgraph_consistent);
237 void free_callgraph(void) {
238 int i, n_irgs = get_irp_n_irgs();
239 for (i = 0; i < n_irgs; ++i) {
240 ir_graph *irg = get_irp_irg(i);
241 if (irg->callees) DEL_ARR_F(irg->callees);
242 if (irg->callers) DEL_ARR_F(irg->callers);
243 if (irg->callee_isbe) DEL_ARR_F(irg->callee_isbe);
244 if (irg->caller_isbe) DEL_ARR_F(irg->caller_isbe);
247 irg->callee_isbe = NULL;
248 irg->caller_isbe = NULL;
250 set_irp_callgraph_state(irp_callgraph_none);
253 /* ----------------------------------------------------------------------------------- */
254 /* A walker for the callgraph */
255 /* ----------------------------------------------------------------------------------- */
258 static void do_walk(ir_graph *irg, callgraph_walk_func *pre, callgraph_walk_func *post, void *env) {
261 if (cg_irg_visited(irg)) return;
262 mark_cg_irg_visited(irg);
266 n_callees = get_irg_n_callees(irg);
267 for (i = 0; i < n_callees; i++) {
268 ir_graph *m = get_irg_callee(irg, i);
269 do_walk(m, pre, post, env);
275 void callgraph_walk(callgraph_walk_func *pre, callgraph_walk_func *post, void *env) {
276 int i, n_irgs = get_irp_n_irgs();
279 do_walk(get_irp_main_irg(), pre, post, env);
280 for (i = 0; i < n_irgs; i++) {
281 ir_graph *irg = get_irp_irg(i);
282 if (!cg_irg_visited(irg) && get_irg_n_callers(irg) == 0)
283 do_walk(irg, pre, post, env);
285 for (i = 0; i < n_irgs; i++) {
286 ir_graph *irg = get_irp_irg(i);
287 if (!cg_irg_visited(irg))
288 do_walk(irg, pre, post, env);
292 /* ----------------------------------------------------------------------------------- */
293 /* loop construction algorithm */
294 /* ----------------------------------------------------------------------------------- */
296 static ir_graph *outermost_ir_graph; /* The outermost graph the scc is computed
298 static ir_loop *current_loop; /* Current cfloop construction is working
300 static int loop_node_cnt = 0; /* Counts the number of allocated cfloop nodes.
301 Each cfloop node gets a unique number.
302 What for? ev. remove. @@@ */
303 static int current_dfn = 1; /* Counter to generate depth first numbering
307 /**********************************************************************/
308 /* Node attributes **/
309 /**********************************************************************/
311 typedef struct scc_info {
312 bool in_stack; /* Marks whether node is on the stack. */
313 int dfn; /* Depth first search number. */
314 int uplink; /* dfn number of ancestor. */
318 static INLINE scc_info* new_scc_info(void) {
319 scc_info *info = obstack_alloc (outermost_ir_graph->obst, sizeof (scc_info));
320 memset (info, 0, sizeof (scc_info));
325 cg_irg_visited(ir_graph *n) {
326 return (((scc_info *)n->link)->visited >= master_cg_visited);
330 mark_cg_irg_visited(ir_graph *n) {
331 ((scc_info *)n->link)->visited = master_cg_visited;
335 set_cg_irg_visited(ir_graph *n, int i) {
336 ((scc_info *)n->link)->visited = i;
340 get_cg_irg_visited(ir_graph *n) {
341 return ((scc_info *)n->link)->visited;
345 mark_irg_in_stack (ir_graph *n) {
346 assert(get_irg_link(n));
347 ((scc_info *)n->link)->in_stack = true;
351 mark_irg_not_in_stack (ir_graph *n) {
352 assert(get_irg_link(n));
353 ((scc_info *)n->link)->in_stack = false;
357 irg_is_in_stack (ir_graph *n) {
358 assert(get_irg_link(n));
359 return ((scc_info *)n->link)->in_stack;
363 set_irg_uplink (ir_graph *n, int uplink) {
364 assert(get_irg_link(n));
365 ((scc_info *)n->link)->uplink = uplink;
369 get_irg_uplink (ir_graph *n) {
370 assert(get_irg_link(n));
371 return ((scc_info *)n->link)->uplink;
375 set_irg_dfn (ir_graph *n, int dfn) {
376 assert(get_irg_link(n));
377 ((scc_info *)n->link)->dfn = dfn;
381 get_irg_dfn (ir_graph *n) {
382 assert(get_irg_link(n));
383 return ((scc_info *)n->link)->dfn;
386 /**********************************************************************/
388 /**********************************************************************/
390 static ir_graph **stack = NULL;
391 static int tos = 0; /* top of stack */
393 static INLINE void init_stack(void) {
395 ARR_RESIZE (ir_graph *, stack, 1000);
397 stack = NEW_ARR_F (ir_graph *, 1000);
406 if (tos == ARR_LEN (stack)) {
407 int nlen = ARR_LEN (stack) * 2;
408 ARR_RESIZE (ir_node *, stack, nlen);
411 mark_irg_in_stack(n);
414 static INLINE ir_graph *
417 ir_graph *n = stack[--tos];
418 mark_irg_not_in_stack(n);
422 /* The nodes up to n belong to the current loop.
423 Removes them from the stack and adds them to the current loop. */
425 pop_scc_to_loop (ir_graph *n)
432 set_irg_dfn(m, loop_node_cnt);
433 add_loop_node(current_loop, (ir_node *)m);
435 //m->callgraph_loop_depth = current_loop->depth;
439 /* GL ??? my last son is my grandson??? Removes cfloops with no
440 ir_nodes in them. Such loops have only another loop as son. (Why
441 can't they have two loops as sons? Does it never get that far? ) */
442 static void close_loop (ir_loop *l)
444 int last = get_loop_n_elements(l) - 1;
445 loop_element lelement = get_loop_element(l, last);
446 ir_loop *last_son = lelement.son;
448 if (get_kind(last_son) == k_ir_loop &&
449 get_loop_n_elements(last_son) == 1) {
452 lelement = get_loop_element(last_son, 0);
454 if(get_kind(gson) == k_ir_loop) {
455 loop_element new_last_son;
457 gson -> outer_loop = l;
458 new_last_son.son = gson;
459 l -> children[last] = new_last_son;
466 /* Removes and unmarks all nodes up to n from the stack.
467 The nodes must be visited once more to assign them to a scc. */
469 pop_scc_unmark_visit (ir_graph *n)
475 set_cg_irg_visited(m, 0);
479 /**********************************************************************/
480 /* The loop datastructure. **/
481 /**********************************************************************/
483 /* Allocates a new loop as son of current_loop. Sets current_loop
484 to the new loop and returns the father. */
485 static ir_loop *new_loop (void) {
486 ir_loop *father, *son;
488 father = current_loop;
490 son = (ir_loop *) obstack_alloc (outermost_ir_graph->obst, sizeof (ir_loop));
491 memset (son, 0, sizeof (ir_loop));
492 son->kind = k_ir_loop;
493 son->children = NEW_ARR_F (loop_element, 0);
497 son->outer_loop = father;
498 add_loop_son(father, son);
499 son->depth = father->depth+1;
500 } else { /* The root loop */
501 son->outer_loop = son;
506 son->loop_nr = get_irp_new_node_nr();
514 /**********************************************************************/
515 /* Constructing and destructing the loop/backedge information. **/
516 /**********************************************************************/
518 /* Initialization steps. **********************************************/
526 for (i = 0; i < get_irp_n_irgs(); ++i) {
527 set_irg_link(get_irp_irg(i), new_scc_info());
528 get_irp_irg(i)->callgraph_recursion_depth = 0;
529 get_irp_irg(i)->callgraph_loop_depth = 0;
533 /** Returns true if n is a loop header, i.e., it is a Block node
534 * and has predecessors within the cfloop and out of the cfloop.
536 * @param root: only needed for assertion.
539 is_head (ir_graph *n, ir_graph *root)
542 int some_outof_loop = 0, some_in_loop = 0;
544 arity = get_irg_n_callees(n);
545 for (i = 0; i < arity; i++) {
546 ir_graph *pred = get_irg_callee(n, i);
547 if (is_irg_callee_backedge(n, i)) continue;
548 if (!irg_is_in_stack(pred)) {
551 if (get_irg_uplink(pred) < get_irg_uplink(root)) {
552 DDMG(pred); DDMG(root);
553 assert(get_irg_uplink(pred) >= get_irg_uplink(root));
559 return some_outof_loop && some_in_loop;
561 /* Returns true if n is possible loop head of an endless loop.
562 I.e., it is a Block, Phi or Filter node and has only predecessors
564 @arg root: only needed for assertion. */
566 is_endless_head (ir_graph *n, ir_graph *root)
569 int some_outof_loop = 0, some_in_loop = 0;
571 arity = get_irg_n_callees(n);
572 for (i = 0; i < arity; i++) {
573 ir_graph *pred = get_irg_callee(n, i);
575 if (is_irg_callee_backedge(n, i)) { continue; }
576 if (!irg_is_in_stack(pred)) {
579 if(get_irg_uplink(pred) < get_irg_uplink(root)) {
580 DDMG(pred); DDMG(root);
581 assert(get_irg_uplink(pred) >= get_irg_uplink(root));
587 return !some_outof_loop && some_in_loop;
591 /* Check whether there is a parallel edge in the ip control flow.
594 is_ip_head (ir_graph *n, ir_graph *pred)
596 int iv_rem = get_interprocedural_view();
597 set_interprocedural_view(true);
598 ir_node *sblock = get_irg_start_block(n);
599 int i, arity = get_Block_n_cfgpreds(sblock);
602 //printf(" edge from "); DDMG(n);
603 //printf(" to pred "); DDMG(pred);
604 //printf(" sblock "); DDMN(sblock);
606 for (i = 0; i < arity; i++) {
607 ir_node *pred_cfop = skip_Proj(get_Block_cfgpred(sblock, i));
608 //printf(" "); DDMN(pred_cfop);
609 if (get_irn_op(pred_cfop) == op_CallBegin) { /* could be Unknown */
610 ir_graph *ip_pred = get_irn_irg(pred_cfop);
611 //printf(" "); DDMG(ip_pred);
612 if ((ip_pred == pred) && is_backedge(sblock, i)) {
613 //printf(" found\n");
619 set_interprocedural_view(iv_rem);
623 /* Returns index of the predecessor with the smallest dfn number
624 greater-equal than limit. */
626 smallest_dfn_pred (ir_graph *n, int limit)
628 int i, index = -2, min = -1;
630 int arity = get_irg_n_callees(n);
631 for (i = 0; i < arity; i++) {
632 ir_graph *pred = get_irg_callee(n, i);
633 if (is_irg_callee_backedge(n, i) || !irg_is_in_stack(pred)) continue;
634 if (get_irg_dfn(pred) >= limit && (min == -1 || get_irg_dfn(pred) < min)) {
636 min = get_irg_dfn(pred);
643 /* Returns index of the predecessor with the largest dfn number. */
645 largest_dfn_pred (ir_graph *n)
647 int i, index = -2, max = -1;
649 int arity = get_irg_n_callees(n);
650 for (i = 0; i < arity; i++) {
651 ir_graph *pred = get_irg_callee(n, i);
652 if (is_irg_callee_backedge (n, i) || !irg_is_in_stack(pred)) continue;
653 if (get_irg_dfn(pred) > max) {
655 max = get_irg_dfn(pred);
664 find_tail (ir_graph *n) {
666 int i, res_index = -2;
669 if (!icfg && rm_cyclic_phis && remove_cyclic_phis (n)) return NULL;
671 m = stack[tos-1]; /* tos = top of stack */
672 if (is_head (m, n)) {
673 res_index = smallest_dfn_pred(m, 0);
674 if ((res_index == -2) && /* no smallest dfn pred found. */
678 if (m == n) return NULL; // Is this to catch Phi - self loops?
679 for (i = tos-2; i >= 0; --i) {
682 if (is_head (m, n)) {
683 res_index = smallest_dfn_pred (m, get_irg_dfn(m) + 1);
684 if (res_index == -2) /* no smallest dfn pred found. */
685 res_index = largest_dfn_pred (m);
687 if ((m == n) && (res_index == -2)) {
693 /* We should not walk past our selves on the stack: The upcoming nodes
694 are not in this loop. We assume a loop not reachable from Start. */
703 /* A dead loop not reachable from Start. */
704 for (i = tos-2; i >= 0; --i) {
706 if (is_endless_head (m, n)) {
707 res_index = smallest_dfn_pred (m, get_irg_dfn(m) + 1);
708 if (res_index == -2) /* no smallest dfn pred found. */
709 res_index = largest_dfn_pred (m);
712 if (m == n) { break; } /* It's not an unreachable loop, either. */
714 //assert(0 && "no head found on stack");
718 assert (res_index > -2);
720 set_irg_callee_backedge (m, res_index);
721 return get_irg_callee(m, res_index);
725 find_tail (ir_graph *n) {
727 int i, res_index = -2;
729 ir_graph *in_and_out = NULL;
730 ir_graph *only_in = NULL;
731 ir_graph *ip_in_and_out = NULL;
732 ir_graph *ip_only_in = NULL;
734 //printf("find tail for "); DDMG(n);
736 for (i = tos-1; i >= 0; --i) {
737 ir_graph *pred = (i < tos -1) ? stack[i+1] : n;
740 if (is_head (m, n)) {
741 //printf(" found 1a! "); DDM;
743 if (is_ip_head(pred, m)) {
744 //printf(" found 1b! "); DDM;
747 } else if (!ip_only_in && is_endless_head(m, n)) {
749 //printf(" found 2a! "); DDM;
750 if (is_ip_head(pred, m)) {
751 //printf(" found 2b! "); DDM;
754 } else if (is_ip_head(pred, m)) {
755 //printf(" found 3! "); DDM; This happens for self recursions in the second
756 //assert(0); scc iteration (the one to flip the loop.)
759 if (ip_in_and_out) break; /* That's what we really want. */
761 if (m == n) break; /* Don't walk past n on the stack! */
765 if (!in_and_out && !only_in)
766 /* There is no loop */
770 /* Is there a head in the callgraph without a head in the
772 assert(in_and_out || only_in);
774 m = (ip_in_and_out) ? ip_in_and_out : ip_only_in;
777 m = (in_and_out) ? in_and_out : only_in;
779 //printf("*** head is "); DDMG(m);
781 res_index = smallest_dfn_pred (m, get_irg_dfn(m) + 1);
782 if (res_index == -2) /* no smallest dfn pred found. */
783 res_index = largest_dfn_pred (m);
785 set_irg_callee_backedge (m, res_index);
786 ir_graph *res = get_irg_callee(m, res_index);
787 //printf("*** tail is "); DDMG(res);
793 /*-----------------------------------------------------------*
794 * The core algorithm. *
795 *-----------------------------------------------------------*/
798 static void cgscc (ir_graph *n) {
801 if (cg_irg_visited(n)) return;
802 mark_cg_irg_visited(n);
804 /* Initialize the node */
805 set_irg_dfn(n, current_dfn); /* Depth first number for this node */
806 set_irg_uplink(n, current_dfn); /* ... is default uplink. */
810 int arity = get_irg_n_callees(n);
812 for (i = 0; i < arity; i++) {
814 if (is_irg_callee_backedge(n, i)) continue;
815 m = get_irg_callee(n, i);
817 /** This marks the backedge, but does it guarantee a correct loop tree? */
818 //if (m == n) { set_irg_callee_backedge(n, i); continue; }
821 if (irg_is_in_stack(m)) {
822 /* Uplink of m is smaller if n->m is a backedge.
823 Propagate the uplink to mark the cfloop. */
824 if (get_irg_uplink(m) < get_irg_uplink(n))
825 set_irg_uplink(n, get_irg_uplink(m));
829 if (get_irg_dfn(n) == get_irg_uplink(n)) {
830 /* This condition holds for
831 1) the node with the incoming backedge.
832 That is: We found a cfloop!
833 2) Straight line code, because no uplink has been propagated, so the
834 uplink still is the same as the dfn.
836 But n might not be a proper cfloop head for the analysis. Proper cfloop
837 heads are Block and Phi nodes. find_tail searches the stack for
838 Block's and Phi's and takes those nodes as cfloop heads for the current
839 cfloop instead and marks the incoming edge as backedge. */
841 ir_graph *tail = find_tail(n);
843 /* We have a cfloop, that is no straight line code,
844 because we found a cfloop head!
845 Next actions: Open a new cfloop on the cfloop tree and
846 try to find inner cfloops */
849 ir_loop *l = new_loop();
851 /* Remove the cfloop from the stack ... */
852 pop_scc_unmark_visit (n);
854 /* The current backedge has been marked, that is temporarily eliminated,
855 by find tail. Start the scc algorithm
856 anew on the subgraph thats left (the current cfloop without the backedge)
857 in order to find more inner cfloops. */
861 assert (cg_irg_visited(n));
871 static void reset_isbe(void) {
872 int i, n_irgs = get_irp_n_irgs();
874 for (i = 0; i < n_irgs; ++i) {
876 ir_graph *irg = get_irp_irg(i);
878 n_cs = get_irg_n_callers(irg);
879 for (j = 0; j < n_cs; ++j) {
880 irg->caller_isbe[j] = 0;
882 n_cs = get_irg_n_callees(irg);
883 for (j = 0; j < n_cs; ++j) {
884 irg->callee_isbe[j] = 0;
892 /* ----------------------------------------------------------------------------------- */
893 /* Another algorithm to compute recursion nesting depth */
894 /* Walk the callgraph. For each crossed edge increase the loop depth by the edge */
895 /* weight. Assign graphs the maximal depth. */
896 /* ----------------------------------------------------------------------------------- */
898 void compute_loop_depth (ir_graph *irg, void *env) {
899 int current_nesting = *(int *) env;
900 int old_nesting = irg->callgraph_loop_depth;
901 int old_visited = get_cg_irg_visited(irg);
906 if (cg_irg_visited(irg)) return;
908 mark_cg_irg_visited(irg);
910 //printf(" old: %d new %d master %d", old_visited, get_cg_irg_visited(irg), master_cg_visited); DDMG(irg);
913 if (old_nesting < current_nesting)
914 irg->callgraph_loop_depth = current_nesting;
916 if (current_nesting > irp->max_callgraph_loop_depth)
917 irp->max_callgraph_loop_depth = current_nesting;
919 if ((old_visited +1 < get_cg_irg_visited(irg)) || /* not yet visited */
920 (old_nesting < current_nesting)) { /* propagate larger nesting */
921 /* Don't walk the graph, but a tree that is an unfolded graph. */
922 n_callees = get_irg_n_callees(irg);
923 for (i = 0; i < n_callees; i++) {
924 ir_graph *m = get_irg_callee(irg, i);
925 *(int *)env += get_irg_callee_loop_depth(irg, i);
926 compute_loop_depth(m, env);
927 *(int *)env -= get_irg_callee_loop_depth(irg, i);
931 set_cg_irg_visited(irg, master_cg_visited-1);
935 /* ----------------------------------------------------------------------------------- */
936 /* Another algorithm to compute recursion nesting depth */
937 /* Walk the callgraph. For each crossed loop increase the nesting depth by one. */
938 /* Assign graphs the maximal nesting depth. Don't increas if passing loops more than */
940 /* ----------------------------------------------------------------------------------- */
943 /* For callees, we want to remember the Call nodes, too. */
945 ir_loop **loop_stack;
947 int recursion_nesting;
950 typedef struct ana_entry2 ana_entry2;
952 static void push2(ana_entry2 *e, ir_loop *g) {
953 if (ARR_LEN(e->loop_stack) == e->tos) {
954 ARR_APP1(ir_loop *, e->loop_stack, g);
956 e->loop_stack[e->tos] = g;
961 static ir_loop *pop2(ana_entry2 *e) {
963 return e->loop_stack[e->tos+1];
966 static int in_stack(ana_entry2 *e, ir_loop *g) {
968 for (i = e->tos-1; i >= 0; --i) {
969 if (e->loop_stack[i] == g) return 1;
974 void compute_rec_depth (ir_graph *irg, void *env) {
975 ana_entry2 *e = (ana_entry2 *)env;
977 int depth, old_depth = irg->callgraph_recursion_depth;
981 if (cg_irg_visited(irg)) return;
982 mark_cg_irg_visited(irg);
984 /* -- compute and set the new nesting value -- */
985 if ((l != irp->outermost_cg_loop) && !in_stack(e, l)) {
987 e->recursion_nesting++;
990 depth = e->recursion_nesting;
992 if (old_depth < depth)
993 irg->callgraph_recursion_depth = depth;
995 if (depth > irp->max_callgraph_recursion_depth)
996 irp->max_callgraph_recursion_depth = depth;
998 /* -- spread the nesting value -- */
999 if (depth == 0 || old_depth < depth) {
1000 /* Don't walk the graph, but a tree that is an unfolded graph. */
1001 n_callees = get_irg_n_callees(irg);
1002 for (i = 0; i < n_callees; i++) {
1003 ir_graph *m = get_irg_callee(irg, i);
1004 compute_rec_depth(m, env);
1008 /* -- clean up -- */
1011 e->recursion_nesting--;
1013 set_cg_irg_visited(irg, master_cg_visited-1);
1017 /* Compute the backedges that represent recursions. */
1018 void find_callgraph_recursions(void) {
1019 int i, n_irgs = get_irp_n_irgs();
1023 /* -- Compute the looptree -- */
1025 /* The outermost graph. We start here. Then we start at all
1026 functions in irg list that are never called, then at the remaining
1028 assert(get_irp_main_irg());
1029 outermost_ir_graph = get_irp_main_irg();
1032 current_loop = NULL;
1033 new_loop(); /* sets current_loop */
1035 master_cg_visited++;
1036 cgscc(outermost_ir_graph);
1037 for (i = 0; i < n_irgs; i++) {
1038 ir_graph *irg = get_irp_irg(i);
1039 if (!cg_irg_visited(irg) && get_irg_n_callers(irg) == 0)
1042 for (i = 0; i < n_irgs; i++) {
1043 ir_graph *irg = get_irp_irg(i);
1044 if (!cg_irg_visited(irg))
1047 irp->outermost_cg_loop = current_loop;
1049 /* -- Reverse the backedge information. -- */
1050 for (i = 0; i < n_irgs; i++) {
1051 ir_graph *irg = get_irp_irg(i);
1052 int j, n_callees = get_irg_n_callees(irg);
1053 for (j = 0; j < n_callees; ++j) {
1054 if (is_irg_callee_backedge(irg, j))
1055 set_irg_caller_backedge(get_irg_callee(irg, j), irg);
1059 /* -- compute the loop depth -- */
1060 int current_nesting = 0;
1061 irp->max_callgraph_loop_depth = 0;
1062 master_cg_visited += 2;
1063 //printf (" ** starting at "); DDMG(get_irp_main_irg());
1064 compute_loop_depth(get_irp_main_irg(), ¤t_nesting);
1065 for (i = 0; i < n_irgs; i++) {
1066 ir_graph *irg = get_irp_irg(i);
1067 if ((get_cg_irg_visited(irg) < master_cg_visited-1) &&
1068 get_irg_n_callers(irg) == 0) {
1069 compute_loop_depth(irg, ¤t_nesting);
1070 //printf (" ** starting at "); DDMG(irg);
1073 for (i = 0; i < n_irgs; i++) {
1074 ir_graph *irg = get_irp_irg(i);
1075 if (get_cg_irg_visited(irg) < master_cg_visited-1) {
1076 compute_loop_depth(irg, ¤t_nesting);
1077 //printf (" ** starting at "); DDMG(irg);
1081 /* -- compute the recursion depth -- */
1083 e.loop_stack = NEW_ARR_F(ir_loop *, 0);
1085 e.recursion_nesting = 0;
1086 irp->max_callgraph_recursion_depth = 0;
1088 master_cg_visited += 2;
1089 compute_rec_depth(get_irp_main_irg(), &e);
1090 //printf (" ++ starting at "); DDMG(get_irp_main_irg());
1091 for (i = 0; i < n_irgs; i++) {
1092 ir_graph *irg = get_irp_irg(i);
1093 if ((get_cg_irg_visited(irg) < master_cg_visited-1) &&
1094 get_irg_n_callers(irg) == 0) {
1095 compute_rec_depth(irg, &e);
1096 //printf (" ++ starting at "); DDMG(irg);
1099 for (i = 0; i < n_irgs; i++) {
1100 ir_graph *irg = get_irp_irg(i);
1101 if (get_cg_irg_visited(irg) < master_cg_visited-1) {
1102 compute_rec_depth(irg, &e);
1103 //printf (" ++ starting at "); DDMG(irg);
1107 DEL_ARR_F(e.loop_stack);
1109 //dump_callgraph("-with_nesting");
1111 //dump_callgraph_loop_tree(current_loop, "-after_cons");
1112 irp->callgraph_state = irp_callgraph_and_calltree_consistent;
1115 /* Maximal loop depth of all paths from an external visible method to
1117 int get_irg_loop_depth(ir_graph *irg) {
1118 assert(irp->callgraph_state == irp_callgraph_consistent ||
1119 irp->callgraph_state == irp_callgraph_and_calltree_consistent);
1120 return irg->callgraph_loop_depth;
1123 /* Maximal recursion depth of all paths from an external visible method to
1125 int get_irg_recursion_depth(ir_graph *irg) {
1126 assert(irp->callgraph_state == irp_callgraph_and_calltree_consistent);
1127 return irg->callgraph_recursion_depth;
1130 void analyse_loop_nesting_depth(void) {
1131 entity **free_methods = NULL;
1134 /* establish preconditions. */
1135 if (get_irp_callee_info_state() != irg_callee_info_consistent) {
1136 cgana(&arr_len, &free_methods);
1139 if (irp_callgraph_consistent != get_irp_callgraph_state()) {
1140 compute_callgraph();
1143 find_callgraph_recursions();