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 ir_graph *callee = get_entity_irg(callee_e);
150 if (callee) { /* For unknown caller */
151 pset_insert((pset *)callee->callers, irg, (unsigned)irg >> 3);
152 ana_entry buf = { callee, NULL, 0};
153 ana_entry *found = pset_find((pset *)irg->callees, &buf, HASH_ADDRESS(callee));
154 if (found) { /* add Call node to list, compute new nesting. */
155 } else { /* New node, add Call node and init nesting. */
156 found = (ana_entry *) obstack_alloc (irg->obst, sizeof (ana_entry));
158 found->call_list = NULL;
159 found->max_depth = 0;
160 pset_insert((pset *)irg->callees, found, HASH_ADDRESS(callee));
162 int depth = get_loop_depth(get_irn_loop(get_nodes_block(n)));
163 found->max_depth = (depth > found->max_depth) ? depth : found->max_depth;
168 /** compare two ir graphs in a ana_entry */
169 static int ana_entry_cmp(const void *elt, const void *key) {
170 const ana_entry *e1 = elt;
171 const ana_entry *e2 = key;
172 return e1->irg != e2->irg;
175 /** compare two ir graphs */
176 static int graph_cmp(const void *elt, const void *key) {
181 /* Construct and destruct the callgraph. */
182 void compute_callgraph(void) {
183 int i, n_irgs = get_irp_n_irgs();
185 assert(! get_interprocedural_view()); /* Else walking will not reach the Call nodes. */
189 for (i = 0; i < n_irgs; ++i) {
190 ir_graph *irg = get_irp_irg(i);
191 assert(get_irg_callee_info_state(irg) == irg_callee_info_consistent);
192 irg->callees = (ir_graph **)new_pset(ana_entry_cmp, 8);
193 irg->callers = (ir_graph **)new_pset(graph_cmp, 8);
194 construct_cf_backedges(irg);
197 /* Compute the call graph */
198 for (i = 0; i < n_irgs; ++i) {
199 ir_graph *irg = get_irp_irg(i);
200 construct_cf_backedges(irg);
201 irg_walk_graph(irg, ana_Call, NULL, NULL);
204 /* Change the sets to arrays. */
205 for (i = 0; i < n_irgs; ++i) {
207 ir_graph *c, *irg = get_irp_irg(i);
209 pset *callee_set = (pset *)irg->callees;
210 count = pset_count(callee_set);
211 irg->callees = NEW_ARR_F(ir_graph *, count);
212 irg->callee_isbe = calloc(count, sizeof(int));
213 c = pset_first(callee_set);
214 for (j = 0; j < count; ++j) {
216 c = pset_next(callee_set);
218 del_pset(callee_set);
221 pset *caller_set = (pset *)irg->callers;
222 count = pset_count(caller_set);
223 irg->callers = NEW_ARR_F(ir_graph *, count);
224 irg->caller_isbe = calloc(count, sizeof(int));
225 c = pset_first(caller_set);
226 for (j = 0; j < count; ++j) {
228 c = pset_next(caller_set);
230 del_pset(caller_set);
233 set_irp_callgraph_state(irp_callgraph_consistent);
236 void free_callgraph(void) {
237 int i, n_irgs = get_irp_n_irgs();
238 for (i = 0; i < n_irgs; ++i) {
239 ir_graph *irg = get_irp_irg(i);
240 if (irg->callees) DEL_ARR_F(irg->callees);
241 if (irg->callers) DEL_ARR_F(irg->callers);
242 if (irg->callee_isbe) DEL_ARR_F(irg->callee_isbe);
243 if (irg->caller_isbe) DEL_ARR_F(irg->caller_isbe);
246 irg->callee_isbe = NULL;
247 irg->caller_isbe = NULL;
249 set_irp_callgraph_state(irp_callgraph_none);
252 /* ----------------------------------------------------------------------------------- */
253 /* A walker for the callgraph */
254 /* ----------------------------------------------------------------------------------- */
257 static void do_walk(ir_graph *irg, callgraph_walk_func *pre, callgraph_walk_func *post, void *env) {
260 if (cg_irg_visited(irg)) return;
261 mark_cg_irg_visited(irg);
265 n_callees = get_irg_n_callees(irg);
266 for (i = 0; i < n_callees; i++) {
267 ir_graph *m = get_irg_callee(irg, i);
268 do_walk(m, pre, post, env);
274 void callgraph_walk(callgraph_walk_func *pre, callgraph_walk_func *post, void *env) {
275 int i, n_irgs = get_irp_n_irgs();
278 do_walk(get_irp_main_irg(), pre, post, env);
279 for (i = 0; i < n_irgs; i++) {
280 ir_graph *irg = get_irp_irg(i);
281 if (!cg_irg_visited(irg) && get_irg_n_callers(irg) == 0)
282 do_walk(irg, pre, post, env);
284 for (i = 0; i < n_irgs; i++) {
285 ir_graph *irg = get_irp_irg(i);
286 if (!cg_irg_visited(irg))
287 do_walk(irg, pre, post, env);
291 /* ----------------------------------------------------------------------------------- */
292 /* loop construction algorithm */
293 /* ----------------------------------------------------------------------------------- */
295 static ir_graph *outermost_ir_graph; /* The outermost graph the scc is computed
297 static ir_loop *current_loop; /* Current cfloop construction is working
299 static int loop_node_cnt = 0; /* Counts the number of allocated cfloop nodes.
300 Each cfloop node gets a unique number.
301 What for? ev. remove. @@@ */
302 static int current_dfn = 1; /* Counter to generate depth first numbering
306 /**********************************************************************/
307 /* Node attributes **/
308 /**********************************************************************/
310 typedef struct scc_info {
311 bool in_stack; /* Marks whether node is on the stack. */
312 int dfn; /* Depth first search number. */
313 int uplink; /* dfn number of ancestor. */
317 static INLINE scc_info* new_scc_info(void) {
318 scc_info *info = obstack_alloc (outermost_ir_graph->obst, sizeof (scc_info));
319 memset (info, 0, sizeof (scc_info));
324 cg_irg_visited(ir_graph *n) {
325 return (((scc_info *)n->link)->visited >= master_cg_visited);
329 mark_cg_irg_visited(ir_graph *n) {
330 ((scc_info *)n->link)->visited = master_cg_visited;
334 set_cg_irg_visited(ir_graph *n, int i) {
335 ((scc_info *)n->link)->visited = i;
339 get_cg_irg_visited(ir_graph *n) {
340 return ((scc_info *)n->link)->visited;
344 mark_irg_in_stack (ir_graph *n) {
345 assert(get_irg_link(n));
346 ((scc_info *)n->link)->in_stack = true;
350 mark_irg_not_in_stack (ir_graph *n) {
351 assert(get_irg_link(n));
352 ((scc_info *)n->link)->in_stack = false;
356 irg_is_in_stack (ir_graph *n) {
357 assert(get_irg_link(n));
358 return ((scc_info *)n->link)->in_stack;
362 set_irg_uplink (ir_graph *n, int uplink) {
363 assert(get_irg_link(n));
364 ((scc_info *)n->link)->uplink = uplink;
368 get_irg_uplink (ir_graph *n) {
369 assert(get_irg_link(n));
370 return ((scc_info *)n->link)->uplink;
374 set_irg_dfn (ir_graph *n, int dfn) {
375 assert(get_irg_link(n));
376 ((scc_info *)n->link)->dfn = dfn;
380 get_irg_dfn (ir_graph *n) {
381 assert(get_irg_link(n));
382 return ((scc_info *)n->link)->dfn;
385 /**********************************************************************/
387 /**********************************************************************/
389 static ir_graph **stack = NULL;
390 static int tos = 0; /* top of stack */
392 static INLINE void init_stack(void) {
394 ARR_RESIZE (ir_graph *, stack, 1000);
396 stack = NEW_ARR_F (ir_graph *, 1000);
405 if (tos == ARR_LEN (stack)) {
406 int nlen = ARR_LEN (stack) * 2;
407 ARR_RESIZE (ir_node *, stack, nlen);
410 mark_irg_in_stack(n);
413 static INLINE ir_graph *
416 ir_graph *n = stack[--tos];
417 mark_irg_not_in_stack(n);
421 /* The nodes up to n belong to the current loop.
422 Removes them from the stack and adds them to the current loop. */
424 pop_scc_to_loop (ir_graph *n)
431 set_irg_dfn(m, loop_node_cnt);
432 add_loop_node(current_loop, (ir_node *)m);
434 //m->callgraph_loop_depth = current_loop->depth;
438 /* GL ??? my last son is my grandson??? Removes cfloops with no
439 ir_nodes in them. Such loops have only another loop as son. (Why
440 can't they have two loops as sons? Does it never get that far? ) */
441 static void close_loop (ir_loop *l)
443 int last = get_loop_n_elements(l) - 1;
444 loop_element lelement = get_loop_element(l, last);
445 ir_loop *last_son = lelement.son;
447 if (get_kind(last_son) == k_ir_loop &&
448 get_loop_n_elements(last_son) == 1) {
451 lelement = get_loop_element(last_son, 0);
453 if(get_kind(gson) == k_ir_loop) {
454 loop_element new_last_son;
456 gson -> outer_loop = l;
457 new_last_son.son = gson;
458 l -> children[last] = new_last_son;
465 /* Removes and unmarks all nodes up to n from the stack.
466 The nodes must be visited once more to assign them to a scc. */
468 pop_scc_unmark_visit (ir_graph *n)
474 set_cg_irg_visited(m, 0);
478 /**********************************************************************/
479 /* The loop datastructure. **/
480 /**********************************************************************/
482 /* Allocates a new loop as son of current_loop. Sets current_loop
483 to the new loop and returns the father. */
484 static ir_loop *new_loop (void) {
485 ir_loop *father, *son;
487 father = current_loop;
489 son = (ir_loop *) obstack_alloc (outermost_ir_graph->obst, sizeof (ir_loop));
490 memset (son, 0, sizeof (ir_loop));
491 son->kind = k_ir_loop;
492 son->children = NEW_ARR_F (loop_element, 0);
496 son->outer_loop = father;
497 add_loop_son(father, son);
498 son->depth = father->depth+1;
499 } else { /* The root loop */
500 son->outer_loop = son;
505 son->loop_nr = get_irp_new_node_nr();
513 /**********************************************************************/
514 /* Constructing and destructing the loop/backedge information. **/
515 /**********************************************************************/
517 /* Initialization steps. **********************************************/
525 for (i = 0; i < get_irp_n_irgs(); ++i) {
526 set_irg_link(get_irp_irg(i), new_scc_info());
527 get_irp_irg(i)->callgraph_recursion_depth = 0;
528 get_irp_irg(i)->callgraph_loop_depth = 0;
532 /** Returns true if n is a loop header, i.e., it is a Block node
533 * and has predecessors within the cfloop and out of the cfloop.
535 * @param root: only needed for assertion.
538 is_head (ir_graph *n, ir_graph *root)
541 int some_outof_loop = 0, some_in_loop = 0;
543 arity = get_irg_n_callees(n);
544 for (i = 0; i < arity; i++) {
545 ir_graph *pred = get_irg_callee(n, i);
546 if (is_irg_callee_backedge(n, i)) continue;
547 if (!irg_is_in_stack(pred)) {
550 if (get_irg_uplink(pred) < get_irg_uplink(root)) {
551 DDMG(pred); DDMG(root);
552 assert(get_irg_uplink(pred) >= get_irg_uplink(root));
558 return some_outof_loop && some_in_loop;
560 /* Returns true if n is possible loop head of an endless loop.
561 I.e., it is a Block, Phi or Filter node and has only predecessors
563 @arg root: only needed for assertion. */
565 is_endless_head (ir_graph *n, ir_graph *root)
568 int some_outof_loop = 0, some_in_loop = 0;
570 arity = get_irg_n_callees(n);
571 for (i = 0; i < arity; i++) {
572 ir_graph *pred = get_irg_callee(n, i);
574 if (is_irg_callee_backedge(n, i)) { continue; }
575 if (!irg_is_in_stack(pred)) {
578 if(get_irg_uplink(pred) < get_irg_uplink(root)) {
579 DDMG(pred); DDMG(root);
580 assert(get_irg_uplink(pred) >= get_irg_uplink(root));
586 return !some_outof_loop && some_in_loop;
590 /* Check whether there is a parallel edge in the ip control flow.
593 is_ip_head (ir_graph *n, ir_graph *pred)
595 int iv_rem = get_interprocedural_view();
596 set_interprocedural_view(true);
597 ir_node *sblock = get_irg_start_block(n);
598 int i, arity = get_Block_n_cfgpreds(sblock);
601 //printf(" edge from "); DDMG(n);
602 //printf(" to pred "); DDMG(pred);
603 //printf(" sblock "); DDMN(sblock);
605 for (i = 0; i < arity; i++) {
606 ir_node *pred_cfop = skip_Proj(get_Block_cfgpred(sblock, i));
607 //printf(" "); DDMN(pred_cfop);
608 if (get_irn_op(pred_cfop) == op_CallBegin) { /* could be Unknown */
609 ir_graph *ip_pred = get_irn_irg(pred_cfop);
610 //printf(" "); DDMG(ip_pred);
611 if ((ip_pred == pred) && is_backedge(sblock, i)) {
612 //printf(" found\n");
618 set_interprocedural_view(iv_rem);
622 /* Returns index of the predecessor with the smallest dfn number
623 greater-equal than limit. */
625 smallest_dfn_pred (ir_graph *n, int limit)
627 int i, index = -2, min = -1;
629 int arity = get_irg_n_callees(n);
630 for (i = 0; i < arity; i++) {
631 ir_graph *pred = get_irg_callee(n, i);
632 if (is_irg_callee_backedge(n, i) || !irg_is_in_stack(pred)) continue;
633 if (get_irg_dfn(pred) >= limit && (min == -1 || get_irg_dfn(pred) < min)) {
635 min = get_irg_dfn(pred);
642 /* Returns index of the predecessor with the largest dfn number. */
644 largest_dfn_pred (ir_graph *n)
646 int i, index = -2, max = -1;
648 int arity = get_irg_n_callees(n);
649 for (i = 0; i < arity; i++) {
650 ir_graph *pred = get_irg_callee(n, i);
651 if (is_irg_callee_backedge (n, i) || !irg_is_in_stack(pred)) continue;
652 if (get_irg_dfn(pred) > max) {
654 max = get_irg_dfn(pred);
663 find_tail (ir_graph *n) {
665 int i, res_index = -2;
668 if (!icfg && rm_cyclic_phis && remove_cyclic_phis (n)) return NULL;
670 m = stack[tos-1]; /* tos = top of stack */
671 if (is_head (m, n)) {
672 res_index = smallest_dfn_pred(m, 0);
673 if ((res_index == -2) && /* no smallest dfn pred found. */
677 if (m == n) return NULL; // Is this to catch Phi - self loops?
678 for (i = tos-2; i >= 0; --i) {
681 if (is_head (m, n)) {
682 res_index = smallest_dfn_pred (m, get_irg_dfn(m) + 1);
683 if (res_index == -2) /* no smallest dfn pred found. */
684 res_index = largest_dfn_pred (m);
686 if ((m == n) && (res_index == -2)) {
692 /* We should not walk past our selves on the stack: The upcoming nodes
693 are not in this loop. We assume a loop not reachable from Start. */
702 /* A dead loop not reachable from Start. */
703 for (i = tos-2; i >= 0; --i) {
705 if (is_endless_head (m, n)) {
706 res_index = smallest_dfn_pred (m, get_irg_dfn(m) + 1);
707 if (res_index == -2) /* no smallest dfn pred found. */
708 res_index = largest_dfn_pred (m);
711 if (m == n) { break; } /* It's not an unreachable loop, either. */
713 //assert(0 && "no head found on stack");
717 assert (res_index > -2);
719 set_irg_callee_backedge (m, res_index);
720 return get_irg_callee(m, res_index);
724 find_tail (ir_graph *n) {
726 int i, res_index = -2;
728 ir_graph *in_and_out = NULL;
729 ir_graph *only_in = NULL;
730 ir_graph *ip_in_and_out = NULL;
731 ir_graph *ip_only_in = NULL;
733 //printf("find tail for "); DDMG(n);
735 for (i = tos-1; i >= 0; --i) {
736 ir_graph *pred = (i < tos -1) ? stack[i+1] : n;
739 if (is_head (m, n)) {
740 //printf(" found 1a! "); DDM;
742 if (is_ip_head(pred, m)) {
743 //printf(" found 1b! "); DDM;
746 } else if (!ip_only_in && is_endless_head(m, n)) {
748 //printf(" found 2a! "); DDM;
749 if (is_ip_head(pred, m)) {
750 //printf(" found 2b! "); DDM;
753 } else if (is_ip_head(pred, m)) {
754 //printf(" found 3! "); DDM; This happens for self recursions in the second
755 //assert(0); scc iteration (the one to flip the loop.)
758 if (ip_in_and_out) break; /* That's what we really want. */
760 if (m == n) break; /* Don't walk past n on the stack! */
764 if (!in_and_out && !only_in)
765 /* There is no loop */
769 /* Is there a head in the callgraph without a head in the
771 assert(in_and_out || only_in);
773 m = (ip_in_and_out) ? ip_in_and_out : ip_only_in;
776 m = (in_and_out) ? in_and_out : only_in;
778 //printf("*** head is "); DDMG(m);
780 res_index = smallest_dfn_pred (m, get_irg_dfn(m) + 1);
781 if (res_index == -2) /* no smallest dfn pred found. */
782 res_index = largest_dfn_pred (m);
784 set_irg_callee_backedge (m, res_index);
785 ir_graph *res = get_irg_callee(m, res_index);
786 //printf("*** tail is "); DDMG(res);
792 /*-----------------------------------------------------------*
793 * The core algorithm. *
794 *-----------------------------------------------------------*/
797 static void cgscc (ir_graph *n) {
800 if (cg_irg_visited(n)) return;
801 mark_cg_irg_visited(n);
803 /* Initialize the node */
804 set_irg_dfn(n, current_dfn); /* Depth first number for this node */
805 set_irg_uplink(n, current_dfn); /* ... is default uplink. */
809 int arity = get_irg_n_callees(n);
811 for (i = 0; i < arity; i++) {
813 if (is_irg_callee_backedge(n, i)) continue;
814 m = get_irg_callee(n, i);
816 /** This marks the backedge, but does it guarantee a correct loop tree? */
817 //if (m == n) { set_irg_callee_backedge(n, i); continue; }
820 if (irg_is_in_stack(m)) {
821 /* Uplink of m is smaller if n->m is a backedge.
822 Propagate the uplink to mark the cfloop. */
823 if (get_irg_uplink(m) < get_irg_uplink(n))
824 set_irg_uplink(n, get_irg_uplink(m));
828 if (get_irg_dfn(n) == get_irg_uplink(n)) {
829 /* This condition holds for
830 1) the node with the incoming backedge.
831 That is: We found a cfloop!
832 2) Straight line code, because no uplink has been propagated, so the
833 uplink still is the same as the dfn.
835 But n might not be a proper cfloop head for the analysis. Proper cfloop
836 heads are Block and Phi nodes. find_tail searches the stack for
837 Block's and Phi's and takes those nodes as cfloop heads for the current
838 cfloop instead and marks the incoming edge as backedge. */
840 ir_graph *tail = find_tail(n);
842 /* We have a cfloop, that is no straight line code,
843 because we found a cfloop head!
844 Next actions: Open a new cfloop on the cfloop tree and
845 try to find inner cfloops */
848 ir_loop *l = new_loop();
850 /* Remove the cfloop from the stack ... */
851 pop_scc_unmark_visit (n);
853 /* The current backedge has been marked, that is temporarily eliminated,
854 by find tail. Start the scc algorithm
855 anew on the subgraph thats left (the current cfloop without the backedge)
856 in order to find more inner cfloops. */
860 assert (cg_irg_visited(n));
870 static void reset_isbe(void) {
871 int i, n_irgs = get_irp_n_irgs();
873 for (i = 0; i < n_irgs; ++i) {
875 ir_graph *irg = get_irp_irg(i);
877 n_cs = get_irg_n_callers(irg);
878 for (j = 0; j < n_cs; ++j) {
879 irg->caller_isbe[j] = 0;
881 n_cs = get_irg_n_callees(irg);
882 for (j = 0; j < n_cs; ++j) {
883 irg->callee_isbe[j] = 0;
891 /* ----------------------------------------------------------------------------------- */
892 /* Another algorithm to compute recursion nesting depth */
893 /* Walk the callgraph. For each crossed edge increase the loop depth by the edge */
894 /* weight. Assign graphs the maximal depth. */
895 /* ----------------------------------------------------------------------------------- */
897 void compute_loop_depth (ir_graph *irg, void *env) {
898 int current_nesting = *(int *) env;
899 int old_nesting = irg->callgraph_loop_depth;
900 int old_visited = get_cg_irg_visited(irg);
905 if (cg_irg_visited(irg)) return;
907 mark_cg_irg_visited(irg);
909 //printf(" old: %d new %d master %d", old_visited, get_cg_irg_visited(irg), master_cg_visited); DDMG(irg);
912 if (old_nesting < current_nesting)
913 irg->callgraph_loop_depth = current_nesting;
915 if (current_nesting > irp->max_callgraph_loop_depth)
916 irp->max_callgraph_loop_depth = current_nesting;
918 if ((old_visited +1 < get_cg_irg_visited(irg)) || /* not yet visited */
919 (old_nesting < current_nesting)) { /* propagate larger nesting */
920 /* Don't walk the graph, but a tree that is an unfolded graph. */
921 n_callees = get_irg_n_callees(irg);
922 for (i = 0; i < n_callees; i++) {
923 ir_graph *m = get_irg_callee(irg, i);
924 *(int *)env += get_irg_callee_loop_depth(irg, i);
925 compute_loop_depth(m, env);
926 *(int *)env -= get_irg_callee_loop_depth(irg, i);
930 set_cg_irg_visited(irg, master_cg_visited-1);
934 /* ----------------------------------------------------------------------------------- */
935 /* Another algorithm to compute recursion nesting depth */
936 /* Walk the callgraph. For each crossed loop increase the nesting depth by one. */
937 /* Assign graphs the maximal nesting depth. Don't increas if passing loops more than */
939 /* ----------------------------------------------------------------------------------- */
942 /* For callees, we want to remember the Call nodes, too. */
944 ir_loop **loop_stack;
946 int recursion_nesting;
949 typedef struct ana_entry2 ana_entry2;
951 static void push2(ana_entry2 *e, ir_loop *g) {
952 if (ARR_LEN(e->loop_stack) == e->tos) {
953 ARR_APP1(ir_loop *, e->loop_stack, g);
955 e->loop_stack[e->tos] = g;
960 static ir_loop *pop2(ana_entry2 *e) {
962 return e->loop_stack[e->tos+1];
965 static int in_stack(ana_entry2 *e, ir_loop *g) {
967 for (i = e->tos-1; i >= 0; --i) {
968 if (e->loop_stack[i] == g) return 1;
973 void compute_rec_depth (ir_graph *irg, void *env) {
974 ana_entry2 *e = (ana_entry2 *)env;
976 int depth, old_depth = irg->callgraph_recursion_depth;
980 if (cg_irg_visited(irg)) return;
981 mark_cg_irg_visited(irg);
983 /* -- compute and set the new nesting value -- */
984 if ((l != irp->outermost_cg_loop) && !in_stack(e, l)) {
986 e->recursion_nesting++;
989 depth = e->recursion_nesting;
991 if (old_depth < depth)
992 irg->callgraph_recursion_depth = depth;
994 if (depth > irp->max_callgraph_recursion_depth)
995 irp->max_callgraph_recursion_depth = depth;
997 /* -- spread the nesting value -- */
998 if (depth == 0 || old_depth < depth) {
999 /* Don't walk the graph, but a tree that is an unfolded graph. */
1000 n_callees = get_irg_n_callees(irg);
1001 for (i = 0; i < n_callees; i++) {
1002 ir_graph *m = get_irg_callee(irg, i);
1003 compute_rec_depth(m, env);
1007 /* -- clean up -- */
1010 e->recursion_nesting--;
1012 set_cg_irg_visited(irg, master_cg_visited-1);
1016 /* Compute the backedges that represent recursions. */
1017 void find_callgraph_recursions(void) {
1018 int i, n_irgs = get_irp_n_irgs();
1022 /* -- Compute the looptree -- */
1024 /* The outermost graph. We start here. Then we start at all
1025 functions in irg list that are never called, then at the remaining
1027 assert(get_irp_main_irg());
1028 outermost_ir_graph = get_irp_main_irg();
1031 current_loop = NULL;
1032 new_loop(); /* sets current_loop */
1034 master_cg_visited++;
1035 cgscc(outermost_ir_graph);
1036 for (i = 0; i < n_irgs; i++) {
1037 ir_graph *irg = get_irp_irg(i);
1038 if (!cg_irg_visited(irg) && get_irg_n_callers(irg) == 0)
1041 for (i = 0; i < n_irgs; i++) {
1042 ir_graph *irg = get_irp_irg(i);
1043 if (!cg_irg_visited(irg))
1046 irp->outermost_cg_loop = current_loop;
1048 /* -- Reverse the backedge information. -- */
1049 for (i = 0; i < n_irgs; i++) {
1050 ir_graph *irg = get_irp_irg(i);
1051 int j, n_callees = get_irg_n_callees(irg);
1052 for (j = 0; j < n_callees; ++j) {
1053 if (is_irg_callee_backedge(irg, j))
1054 set_irg_caller_backedge(get_irg_callee(irg, j), irg);
1058 /* -- compute the loop depth -- */
1059 int current_nesting = 0;
1060 irp->max_callgraph_loop_depth = 0;
1061 master_cg_visited += 2;
1062 //printf (" ** starting at "); DDMG(get_irp_main_irg());
1063 compute_loop_depth(get_irp_main_irg(), ¤t_nesting);
1064 for (i = 0; i < n_irgs; i++) {
1065 ir_graph *irg = get_irp_irg(i);
1066 if ((get_cg_irg_visited(irg) < master_cg_visited-1) &&
1067 get_irg_n_callers(irg) == 0) {
1068 compute_loop_depth(irg, ¤t_nesting);
1069 //printf (" ** starting at "); DDMG(irg);
1072 for (i = 0; i < n_irgs; i++) {
1073 ir_graph *irg = get_irp_irg(i);
1074 if (get_cg_irg_visited(irg) < master_cg_visited-1) {
1075 compute_loop_depth(irg, ¤t_nesting);
1076 //printf (" ** starting at "); DDMG(irg);
1080 /* -- compute the recursion depth -- */
1082 e.loop_stack = NEW_ARR_F(ir_loop *, 0);
1084 e.recursion_nesting = 0;
1085 irp->max_callgraph_recursion_depth = 0;
1087 master_cg_visited += 2;
1088 compute_rec_depth(get_irp_main_irg(), &e);
1089 //printf (" ++ starting at "); DDMG(get_irp_main_irg());
1090 for (i = 0; i < n_irgs; i++) {
1091 ir_graph *irg = get_irp_irg(i);
1092 if ((get_cg_irg_visited(irg) < master_cg_visited-1) &&
1093 get_irg_n_callers(irg) == 0) {
1094 compute_rec_depth(irg, &e);
1095 //printf (" ++ starting at "); DDMG(irg);
1098 for (i = 0; i < n_irgs; i++) {
1099 ir_graph *irg = get_irp_irg(i);
1100 if (get_cg_irg_visited(irg) < master_cg_visited-1) {
1101 compute_rec_depth(irg, &e);
1102 //printf (" ++ starting at "); DDMG(irg);
1106 DEL_ARR_F(e.loop_stack);
1108 //dump_callgraph("-with_nesting");
1110 //dump_callgraph_loop_tree(current_loop, "-after_cons");
1111 irp->callgraph_state = irp_callgraph_and_calltree_consistent;
1114 /* Maximal loop depth of all paths from an external visible method to
1116 int get_irg_loop_depth(ir_graph *irg) {
1117 assert(irp->callgraph_state == irp_callgraph_consistent ||
1118 irp->callgraph_state == irp_callgraph_and_calltree_consistent);
1119 return irg->callgraph_loop_depth;
1122 /* Maximal recursion depth of all paths from an external visible method to
1124 int get_irg_recursion_depth(ir_graph *irg) {
1125 assert(irp->callgraph_state == irp_callgraph_and_calltree_consistent);
1126 return irg->callgraph_recursion_depth;
1129 void analyse_loop_nesting_depth(void) {
1130 entity **free_methods = NULL;
1133 /* establish preconditions. */
1134 if (get_irp_callee_info_state() != irg_callee_info_consistent) {
1135 cgana(&arr_len, &free_methods);
1138 if (irp_callgraph_consistent != get_irp_callgraph_state()) {
1139 compute_callgraph();
1142 find_callgraph_recursions();