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 ------------------------ */
134 static void ana_Call(ir_node *n, void *env) {
138 if (get_irn_op(n) != op_Call) return;
140 irg = get_irn_irg(n);
141 n_callees = get_Call_n_callees(n);
142 for (i = 0; i < n_callees; ++i) {
143 entity *callee_e = get_Call_callee(n, i);
144 if (callee_e != unknown_entity) { /* For unknown caller */
145 ir_graph *callee = get_entity_irg(callee_e);
146 pset_insert((pset *)callee->callers, irg, (unsigned)irg >> 3);
148 ana_entry buf = { callee, NULL, 0};
149 ana_entry *found = pset_find((pset *)irg->callees, &buf, (unsigned)callee >> 3);
150 if (found) { /* add Call node to list, compute new nesting. */
151 } else { /* New node, add Call node and init nesting. */
152 found = (ana_entry *) obstack_alloc (irg->obst, sizeof (ana_entry));
154 found->call_list = NULL;
155 found->max_depth = 0;
156 pset_insert((pset *)irg->callees, found, (unsigned)callee >> 3);
158 int depth = get_loop_depth(get_irn_loop(get_nodes_block(n)));
159 found->max_depth = (depth > found->max_depth) ? depth : found->max_depth;
164 /* compare two ir graphs */
165 static int ana_entry_cmp(const void *elt, const void *key) {
166 ana_entry *e1 = (ana_entry *)elt;
167 ana_entry *e2 = (ana_entry *)key;
168 return e1->irg != e2->irg;
171 /* compare two ir graphs */
172 static int graph_cmp(const void *elt, const void *key) {
177 /* Construct and destruct the callgraph. */
178 void compute_callgraph(void) {
179 int i, n_irgs = get_irp_n_irgs();
181 assert(! get_interprocedural_view()); /* Else walking will not reach the Call nodes. */
185 for (i = 0; i < n_irgs; ++i) {
186 ir_graph *irg = get_irp_irg(i);
187 assert(get_irg_callee_info_state(irg) == irg_callee_info_consistent);
188 irg->callees = (ir_graph **)new_pset(ana_entry_cmp, 8);
189 irg->callers = (ir_graph **)new_pset(graph_cmp, 8);
190 construct_cf_backedges(irg);
193 /* Compute the call graph */
194 for (i = 0; i < n_irgs; ++i) {
195 ir_graph *irg = get_irp_irg(i);
196 construct_cf_backedges(irg);
197 irg_walk_graph(irg, ana_Call, NULL, NULL);
200 /* Change the sets to arrays. */
201 for (i = 0; i < n_irgs; ++i) {
203 ir_graph *c, *irg = get_irp_irg(i);
205 pset *callee_set = (pset *)irg->callees;
206 count = pset_count(callee_set);
207 irg->callees = NEW_ARR_F(ir_graph *, count);
208 irg->callee_isbe = calloc(count, sizeof(int));
209 c = pset_first(callee_set);
210 for (j = 0; j < count; ++j) {
212 c = pset_next(callee_set);
214 del_pset(callee_set);
217 pset *caller_set = (pset *)irg->callers;
218 count = pset_count(caller_set);
219 irg->callers = NEW_ARR_F(ir_graph *, count);
220 irg->caller_isbe = calloc(count, sizeof(int));
221 c = pset_first(caller_set);
222 for (j = 0; j < count; ++j) {
224 c = pset_next(caller_set);
226 del_pset(caller_set);
229 set_irp_callgraph_state(irp_callgraph_consistent);
232 void free_callgraph(void) {
233 int i, n_irgs = get_irp_n_irgs();
234 for (i = 0; i < n_irgs; ++i) {
235 ir_graph *irg = get_irp_irg(i);
236 if (irg->callees) DEL_ARR_F(irg->callees);
237 if (irg->callers) DEL_ARR_F(irg->callers);
238 if (irg->callee_isbe) DEL_ARR_F(irg->callee_isbe);
239 if (irg->caller_isbe) DEL_ARR_F(irg->caller_isbe);
242 irg->callee_isbe = NULL;
243 irg->caller_isbe = NULL;
245 set_irp_callgraph_state(irp_callgraph_none);
248 /* ----------------------------------------------------------------------------------- */
249 /* A walker for the callgraph */
250 /* ----------------------------------------------------------------------------------- */
253 static void do_walk(ir_graph *irg, callgraph_walk_func *pre, callgraph_walk_func *post, void *env) {
256 if (cg_irg_visited(irg)) return;
257 mark_cg_irg_visited(irg);
261 n_callees = get_irg_n_callees(irg);
262 for (i = 0; i < n_callees; i++) {
263 ir_graph *m = get_irg_callee(irg, i);
264 do_walk(m, pre, post, env);
270 void callgraph_walk(callgraph_walk_func *pre, callgraph_walk_func *post, void *env) {
271 int i, n_irgs = get_irp_n_irgs();
274 do_walk(get_irp_main_irg(), pre, post, env);
275 for (i = 0; i < n_irgs; i++) {
276 ir_graph *irg = get_irp_irg(i);
277 if (!cg_irg_visited(irg) && get_irg_n_callers(irg) == 0)
278 do_walk(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))
283 do_walk(irg, pre, post, env);
287 /* ----------------------------------------------------------------------------------- */
288 /* loop construction algorithm */
289 /* ----------------------------------------------------------------------------------- */
291 static ir_graph *outermost_ir_graph; /* The outermost graph the scc is computed
293 static ir_loop *current_loop; /* Current cfloop construction is working
295 static int loop_node_cnt = 0; /* Counts the number of allocated cfloop nodes.
296 Each cfloop node gets a unique number.
297 What for? ev. remove. @@@ */
298 static int current_dfn = 1; /* Counter to generate depth first numbering
302 /**********************************************************************/
303 /* Node attributes **/
304 /**********************************************************************/
306 typedef struct scc_info {
307 bool in_stack; /* Marks whether node is on the stack. */
308 int dfn; /* Depth first search number. */
309 int uplink; /* dfn number of ancestor. */
313 static INLINE scc_info* new_scc_info(void) {
314 scc_info *info = obstack_alloc (outermost_ir_graph->obst, sizeof (scc_info));
315 memset (info, 0, sizeof (scc_info));
320 cg_irg_visited(ir_graph *n) {
321 return (((scc_info *)n->link)->visited >= master_cg_visited);
325 mark_cg_irg_visited(ir_graph *n) {
326 ((scc_info *)n->link)->visited = master_cg_visited;
330 set_cg_irg_visited(ir_graph *n, int i) {
331 ((scc_info *)n->link)->visited = i;
335 get_cg_irg_visited(ir_graph *n) {
336 return ((scc_info *)n->link)->visited;
340 mark_irg_in_stack (ir_graph *n) {
341 assert(get_irg_link(n));
342 ((scc_info *)n->link)->in_stack = true;
346 mark_irg_not_in_stack (ir_graph *n) {
347 assert(get_irg_link(n));
348 ((scc_info *)n->link)->in_stack = false;
352 irg_is_in_stack (ir_graph *n) {
353 assert(get_irg_link(n));
354 return ((scc_info *)n->link)->in_stack;
358 set_irg_uplink (ir_graph *n, int uplink) {
359 assert(get_irg_link(n));
360 ((scc_info *)n->link)->uplink = uplink;
364 get_irg_uplink (ir_graph *n) {
365 assert(get_irg_link(n));
366 return ((scc_info *)n->link)->uplink;
370 set_irg_dfn (ir_graph *n, int dfn) {
371 assert(get_irg_link(n));
372 ((scc_info *)n->link)->dfn = dfn;
376 get_irg_dfn (ir_graph *n) {
377 assert(get_irg_link(n));
378 return ((scc_info *)n->link)->dfn;
381 /**********************************************************************/
383 /**********************************************************************/
385 static ir_graph **stack = NULL;
386 static int tos = 0; /* top of stack */
388 static INLINE void init_stack(void) {
390 ARR_RESIZE (ir_graph *, stack, 1000);
392 stack = NEW_ARR_F (ir_graph *, 1000);
401 if (tos == ARR_LEN (stack)) {
402 int nlen = ARR_LEN (stack) * 2;
403 ARR_RESIZE (ir_node *, stack, nlen);
406 mark_irg_in_stack(n);
409 static INLINE ir_graph *
412 ir_graph *n = stack[--tos];
413 mark_irg_not_in_stack(n);
417 /* The nodes up to n belong to the current loop.
418 Removes them from the stack and adds them to the current loop. */
420 pop_scc_to_loop (ir_graph *n)
427 set_irg_dfn(m, loop_node_cnt);
428 add_loop_node(current_loop, (ir_node *)m);
430 //m->callgraph_loop_depth = current_loop->depth;
434 /* GL ??? my last son is my grandson??? Removes cfloops with no
435 ir_nodes in them. Such loops have only another loop as son. (Why
436 can't they have two loops as sons? Does it never get that far? ) */
437 static void close_loop (ir_loop *l)
439 int last = get_loop_n_elements(l) - 1;
440 loop_element lelement = get_loop_element(l, last);
441 ir_loop *last_son = lelement.son;
443 if (get_kind(last_son) == k_ir_loop &&
444 get_loop_n_elements(last_son) == 1) {
447 lelement = get_loop_element(last_son, 0);
449 if(get_kind(gson) == k_ir_loop) {
450 loop_element new_last_son;
452 gson -> outer_loop = l;
453 new_last_son.son = gson;
454 l -> children[last] = new_last_son;
461 /* Removes and unmarks all nodes up to n from the stack.
462 The nodes must be visited once more to assign them to a scc. */
464 pop_scc_unmark_visit (ir_graph *n)
470 set_cg_irg_visited(m, 0);
474 /**********************************************************************/
475 /* The loop datastructure. **/
476 /**********************************************************************/
478 /* Allocates a new loop as son of current_loop. Sets current_loop
479 to the new loop and returns the father. */
480 static ir_loop *new_loop (void) {
481 ir_loop *father, *son;
483 father = current_loop;
485 son = (ir_loop *) obstack_alloc (outermost_ir_graph->obst, sizeof (ir_loop));
486 memset (son, 0, sizeof (ir_loop));
487 son->kind = k_ir_loop;
488 son->children = NEW_ARR_F (loop_element, 0);
492 son->outer_loop = father;
493 add_loop_son(father, son);
494 son->depth = father->depth+1;
495 } else { /* The root loop */
496 son->outer_loop = son;
501 son->loop_nr = get_irp_new_node_nr();
509 /**********************************************************************/
510 /* Constructing and destructing the loop/backedge information. **/
511 /**********************************************************************/
513 /* Initialization steps. **********************************************/
521 for (i = 0; i < get_irp_n_irgs(); ++i) {
522 set_irg_link(get_irp_irg(i), new_scc_info());
523 get_irp_irg(i)->callgraph_recursion_depth = 0;
524 get_irp_irg(i)->callgraph_loop_depth = 0;
528 /** Returns true if n is a loop header, i.e., it is a Block node
529 * and has predecessors within the cfloop and out of the cfloop.
531 * @param root: only needed for assertion.
534 is_head (ir_graph *n, ir_graph *root)
537 int some_outof_loop = 0, some_in_loop = 0;
539 arity = get_irg_n_callees(n);
540 for (i = 0; i < arity; i++) {
541 ir_graph *pred = get_irg_callee(n, i);
542 if (is_irg_callee_backedge(n, i)) continue;
543 if (!irg_is_in_stack(pred)) {
546 if (get_irg_uplink(pred) < get_irg_uplink(root)) {
547 DDMG(pred); DDMG(root);
548 assert(get_irg_uplink(pred) >= get_irg_uplink(root));
554 return some_outof_loop && some_in_loop;
556 /* Returns true if n is possible loop head of an endless loop.
557 I.e., it is a Block, Phi or Filter node and has only predecessors
559 @arg root: only needed for assertion. */
561 is_endless_head (ir_graph *n, ir_graph *root)
564 int some_outof_loop = 0, some_in_loop = 0;
566 arity = get_irg_n_callees(n);
567 for (i = 0; i < arity; i++) {
568 ir_graph *pred = get_irg_callee(n, i);
570 if (is_irg_callee_backedge(n, i)) { continue; }
571 if (!irg_is_in_stack(pred)) {
574 if(get_irg_uplink(pred) < get_irg_uplink(root)) {
575 DDMG(pred); DDMG(root);
576 assert(get_irg_uplink(pred) >= get_irg_uplink(root));
582 return !some_outof_loop && some_in_loop;
586 /* Check whether there is a parallel edge in the ip control flow.
589 is_ip_head (ir_graph *n, ir_graph *pred)
591 int iv_rem = get_interprocedural_view();
592 set_interprocedural_view(true);
593 ir_node *sblock = get_irg_start_block(n);
594 int i, arity = get_Block_n_cfgpreds(sblock);
597 //printf(" edge from "); DDMG(n);
598 //printf(" to pred "); DDMG(pred);
599 //printf(" sblock "); DDMN(sblock);
601 for (i = 0; i < arity; i++) {
602 ir_node *pred_cfop = skip_Proj(get_Block_cfgpred(sblock, i));
603 //printf(" "); DDMN(pred_cfop);
604 if (get_irn_op(pred_cfop) == op_CallBegin) { /* could be Unknown */
605 ir_graph *ip_pred = get_irn_irg(pred_cfop);
606 //printf(" "); DDMG(ip_pred);
607 if ((ip_pred == pred) && is_backedge(sblock, i)) {
608 //printf(" found\n");
614 set_interprocedural_view(iv_rem);
618 /* Returns index of the predecessor with the smallest dfn number
619 greater-equal than limit. */
621 smallest_dfn_pred (ir_graph *n, int limit)
623 int i, index = -2, min = -1;
625 int arity = get_irg_n_callees(n);
626 for (i = 0; i < arity; i++) {
627 ir_graph *pred = get_irg_callee(n, i);
628 if (is_irg_callee_backedge(n, i) || !irg_is_in_stack(pred)) continue;
629 if (get_irg_dfn(pred) >= limit && (min == -1 || get_irg_dfn(pred) < min)) {
631 min = get_irg_dfn(pred);
638 /* Returns index of the predecessor with the largest dfn number. */
640 largest_dfn_pred (ir_graph *n)
642 int i, index = -2, max = -1;
644 int arity = get_irg_n_callees(n);
645 for (i = 0; i < arity; i++) {
646 ir_graph *pred = get_irg_callee(n, i);
647 if (is_irg_callee_backedge (n, i) || !irg_is_in_stack(pred)) continue;
648 if (get_irg_dfn(pred) > max) {
650 max = get_irg_dfn(pred);
659 find_tail (ir_graph *n) {
661 int i, res_index = -2;
664 if (!icfg && rm_cyclic_phis && remove_cyclic_phis (n)) return NULL;
666 m = stack[tos-1]; /* tos = top of stack */
667 if (is_head (m, n)) {
668 res_index = smallest_dfn_pred(m, 0);
669 if ((res_index == -2) && /* no smallest dfn pred found. */
673 if (m == n) return NULL; // Is this to catch Phi - self loops?
674 for (i = tos-2; i >= 0; --i) {
677 if (is_head (m, n)) {
678 res_index = smallest_dfn_pred (m, get_irg_dfn(m) + 1);
679 if (res_index == -2) /* no smallest dfn pred found. */
680 res_index = largest_dfn_pred (m);
682 if ((m == n) && (res_index == -2)) {
688 /* We should not walk past our selves on the stack: The upcoming nodes
689 are not in this loop. We assume a loop not reachable from Start. */
698 /* A dead loop not reachable from Start. */
699 for (i = tos-2; i >= 0; --i) {
701 if (is_endless_head (m, n)) {
702 res_index = smallest_dfn_pred (m, get_irg_dfn(m) + 1);
703 if (res_index == -2) /* no smallest dfn pred found. */
704 res_index = largest_dfn_pred (m);
707 if (m == n) { break; } /* It's not an unreachable loop, either. */
709 //assert(0 && "no head found on stack");
713 assert (res_index > -2);
715 set_irg_callee_backedge (m, res_index);
716 return get_irg_callee(m, res_index);
720 find_tail (ir_graph *n) {
722 int i, res_index = -2;
724 ir_graph *in_and_out = NULL;
725 ir_graph *only_in = NULL;
726 ir_graph *ip_in_and_out = NULL;
727 ir_graph *ip_only_in = NULL;
729 //printf("find tail for "); DDMG(n);
731 for (i = tos-1; i >= 0; --i) {
732 ir_graph *pred = (i < tos -1) ? stack[i+1] : n;
735 if (is_head (m, n)) {
736 //printf(" found 1a! "); DDM;
738 if (is_ip_head(pred, m)) {
739 //printf(" found 1b! "); DDM;
742 } else if (!ip_only_in && is_endless_head(m, n)) {
744 //printf(" found 2a! "); DDM;
745 if (is_ip_head(pred, m)) {
746 //printf(" found 2b! "); DDM;
749 } else if (is_ip_head(pred, m)) {
750 //printf(" found 3! "); DDM; This happens for self recursions in the second
751 //assert(0); scc iteration (the one to flip the loop.)
754 if (ip_in_and_out) break; /* That's what we really want. */
756 if (m == n) break; /* Don't walk past n on the stack! */
760 if (!in_and_out && !only_in)
761 /* There is no loop */
765 /* Is there a head in the callgraph without a head in the
767 assert(in_and_out || only_in);
769 m = (ip_in_and_out) ? ip_in_and_out : ip_only_in;
772 m = (in_and_out) ? in_and_out : only_in;
774 //printf("*** head is "); DDMG(m);
776 res_index = smallest_dfn_pred (m, get_irg_dfn(m) + 1);
777 if (res_index == -2) /* no smallest dfn pred found. */
778 res_index = largest_dfn_pred (m);
780 set_irg_callee_backedge (m, res_index);
781 ir_graph *res = get_irg_callee(m, res_index);
782 //printf("*** tail is "); DDMG(res);
788 /*-----------------------------------------------------------*
789 * The core algorithm. *
790 *-----------------------------------------------------------*/
793 static void cgscc (ir_graph *n) {
796 if (cg_irg_visited(n)) return;
797 mark_cg_irg_visited(n);
799 /* Initialize the node */
800 set_irg_dfn(n, current_dfn); /* Depth first number for this node */
801 set_irg_uplink(n, current_dfn); /* ... is default uplink. */
805 int arity = get_irg_n_callees(n);
807 for (i = 0; i < arity; i++) {
809 if (is_irg_callee_backedge(n, i)) continue;
810 m = get_irg_callee(n, i);
812 /** This marks the backedge, but does it guarantee a correct loop tree? */
813 //if (m == n) { set_irg_callee_backedge(n, i); continue; }
816 if (irg_is_in_stack(m)) {
817 /* Uplink of m is smaller if n->m is a backedge.
818 Propagate the uplink to mark the cfloop. */
819 if (get_irg_uplink(m) < get_irg_uplink(n))
820 set_irg_uplink(n, get_irg_uplink(m));
824 if (get_irg_dfn(n) == get_irg_uplink(n)) {
825 /* This condition holds for
826 1) the node with the incoming backedge.
827 That is: We found a cfloop!
828 2) Straight line code, because no uplink has been propagated, so the
829 uplink still is the same as the dfn.
831 But n might not be a proper cfloop head for the analysis. Proper cfloop
832 heads are Block and Phi nodes. find_tail searches the stack for
833 Block's and Phi's and takes those nodes as cfloop heads for the current
834 cfloop instead and marks the incoming edge as backedge. */
836 ir_graph *tail = find_tail(n);
838 /* We have a cfloop, that is no straight line code,
839 because we found a cfloop head!
840 Next actions: Open a new cfloop on the cfloop tree and
841 try to find inner cfloops */
844 ir_loop *l = new_loop();
846 /* Remove the cfloop from the stack ... */
847 pop_scc_unmark_visit (n);
849 /* The current backedge has been marked, that is temporarily eliminated,
850 by find tail. Start the scc algorithm
851 anew on the subgraph thats left (the current cfloop without the backedge)
852 in order to find more inner cfloops. */
856 assert (cg_irg_visited(n));
866 static void reset_isbe(void) {
867 int i, n_irgs = get_irp_n_irgs();
869 for (i = 0; i < n_irgs; ++i) {
871 ir_graph *irg = get_irp_irg(i);
873 n_cs = get_irg_n_callers(irg);
874 for (j = 0; j < n_cs; ++j) {
875 irg->caller_isbe[j] = 0;
877 n_cs = get_irg_n_callees(irg);
878 for (j = 0; j < n_cs; ++j) {
879 irg->callee_isbe[j] = 0;
887 /* ----------------------------------------------------------------------------------- */
888 /* Another algorithm to compute recursion nesting depth */
889 /* Walk the callgraph. For each crossed edge increase the loop depth by the edge */
890 /* weight. Assign graphs the maximal depth. */
891 /* ----------------------------------------------------------------------------------- */
893 void compute_loop_depth (ir_graph *irg, void *env) {
894 int current_nesting = *(int *) env;
895 int old_nesting = irg->callgraph_loop_depth;
896 int old_visited = get_cg_irg_visited(irg);
901 if (cg_irg_visited(irg)) return;
903 mark_cg_irg_visited(irg);
905 //printf(" old: %d new %d master %d", old_visited, get_cg_irg_visited(irg), master_cg_visited); DDMG(irg);
908 if (old_nesting < current_nesting)
909 irg->callgraph_loop_depth = current_nesting;
911 if (current_nesting > irp->max_callgraph_loop_depth)
912 irp->max_callgraph_loop_depth = current_nesting;
914 if ((old_visited +1 < get_cg_irg_visited(irg)) || /* not yet visited */
915 (old_nesting < current_nesting)) { /* propagate larger nesting */
916 /* Don't walk the graph, but a tree that is an unfolded graph. */
917 n_callees = get_irg_n_callees(irg);
918 for (i = 0; i < n_callees; i++) {
919 ir_graph *m = get_irg_callee(irg, i);
920 *(int *)env += get_irg_callee_loop_depth(irg, i);
921 compute_loop_depth(m, env);
922 *(int *)env -= get_irg_callee_loop_depth(irg, i);
926 set_cg_irg_visited(irg, master_cg_visited-1);
930 /* ----------------------------------------------------------------------------------- */
931 /* Another algorithm to compute recursion nesting depth */
932 /* Walk the callgraph. For each crossed loop increase the nesting depth by one. */
933 /* Assign graphs the maximal nesting depth. Don't increas if passing loops more than */
935 /* ----------------------------------------------------------------------------------- */
938 /* For callees, we want to remember the Call nodes, too. */
940 ir_loop **loop_stack;
942 int recursion_nesting;
945 typedef struct ana_entry2 ana_entry2;
947 static void push2(ana_entry2 *e, ir_loop *g) {
948 if (ARR_LEN(e->loop_stack) == e->tos) {
949 ARR_APP1(ir_loop *, e->loop_stack, g);
951 e->loop_stack[e->tos] = g;
956 static ir_loop *pop2(ana_entry2 *e) {
958 return e->loop_stack[e->tos+1];
961 static int in_stack(ana_entry2 *e, ir_loop *g) {
963 for (i = e->tos-1; i >= 0; --i) {
964 if (e->loop_stack[i] == g) return 1;
969 void compute_rec_depth (ir_graph *irg, void *env) {
970 ana_entry2 *e = (ana_entry2 *)env;
972 int depth, old_depth = irg->callgraph_recursion_depth;
976 if (cg_irg_visited(irg)) return;
977 mark_cg_irg_visited(irg);
979 /* -- compute and set the new nesting value -- */
980 if ((l != irp->outermost_cg_loop) && !in_stack(e, l)) {
982 e->recursion_nesting++;
985 depth = e->recursion_nesting;
987 if (old_depth < depth)
988 irg->callgraph_recursion_depth = depth;
990 if (depth > irp->max_callgraph_recursion_depth)
991 irp->max_callgraph_recursion_depth = depth;
993 /* -- spread the nesting value -- */
994 if (depth == 0 || old_depth < depth) {
995 /* Don't walk the graph, but a tree that is an unfolded graph. */
996 n_callees = get_irg_n_callees(irg);
997 for (i = 0; i < n_callees; i++) {
998 ir_graph *m = get_irg_callee(irg, i);
999 compute_rec_depth(m, env);
1003 /* -- clean up -- */
1006 e->recursion_nesting--;
1008 set_cg_irg_visited(irg, master_cg_visited-1);
1012 /* Compute the backedges that represent recursions. */
1013 void find_callgraph_recursions(void) {
1014 int i, n_irgs = get_irp_n_irgs();
1018 /* -- Compute the looptree -- */
1020 /* The outermost graph. We start here. Then we start at all
1021 functions in irg list that are never called, then at the remaining
1023 assert(get_irp_main_irg());
1024 outermost_ir_graph = get_irp_main_irg();
1027 current_loop = NULL;
1028 new_loop(); /* sets current_loop */
1030 master_cg_visited++;
1031 cgscc(outermost_ir_graph);
1032 for (i = 0; i < n_irgs; i++) {
1033 ir_graph *irg = get_irp_irg(i);
1034 if (!cg_irg_visited(irg) && get_irg_n_callers(irg) == 0)
1037 for (i = 0; i < n_irgs; i++) {
1038 ir_graph *irg = get_irp_irg(i);
1039 if (!cg_irg_visited(irg))
1042 irp->outermost_cg_loop = current_loop;
1044 /* -- Reverse the backedge information. -- */
1045 for (i = 0; i < n_irgs; i++) {
1046 ir_graph *irg = get_irp_irg(i);
1047 int j, n_callees = get_irg_n_callees(irg);
1048 for (j = 0; j < n_callees; ++j) {
1049 if (is_irg_callee_backedge(irg, j))
1050 set_irg_caller_backedge(get_irg_callee(irg, j), irg);
1054 /* -- compute the loop depth -- */
1055 int current_nesting = 0;
1056 irp->max_callgraph_loop_depth = 0;
1057 master_cg_visited += 2;
1058 //printf (" ** starting at "); DDMG(get_irp_main_irg());
1059 compute_loop_depth(get_irp_main_irg(), ¤t_nesting);
1060 for (i = 0; i < n_irgs; i++) {
1061 ir_graph *irg = get_irp_irg(i);
1062 if ((get_cg_irg_visited(irg) < master_cg_visited-1) &&
1063 get_irg_n_callers(irg) == 0) {
1064 compute_loop_depth(irg, ¤t_nesting);
1065 //printf (" ** starting at "); DDMG(irg);
1068 for (i = 0; i < n_irgs; i++) {
1069 ir_graph *irg = get_irp_irg(i);
1070 if (get_cg_irg_visited(irg) < master_cg_visited-1) {
1071 compute_loop_depth(irg, ¤t_nesting);
1072 //printf (" ** starting at "); DDMG(irg);
1076 /* -- compute the recursion depth -- */
1078 e.loop_stack = NEW_ARR_F(ir_loop *, 0);
1080 e.recursion_nesting = 0;
1081 irp->max_callgraph_recursion_depth = 0;
1083 master_cg_visited += 2;
1084 compute_rec_depth(get_irp_main_irg(), &e);
1085 //printf (" ++ starting at "); DDMG(get_irp_main_irg());
1086 for (i = 0; i < n_irgs; i++) {
1087 ir_graph *irg = get_irp_irg(i);
1088 if ((get_cg_irg_visited(irg) < master_cg_visited-1) &&
1089 get_irg_n_callers(irg) == 0) {
1090 compute_rec_depth(irg, &e);
1091 //printf (" ++ starting at "); DDMG(irg);
1094 for (i = 0; i < n_irgs; i++) {
1095 ir_graph *irg = get_irp_irg(i);
1096 if (get_cg_irg_visited(irg) < master_cg_visited-1) {
1097 compute_rec_depth(irg, &e);
1098 //printf (" ++ starting at "); DDMG(irg);
1102 DEL_ARR_F(e.loop_stack);
1104 //dump_callgraph("-with_nesting");
1106 //dump_callgraph_loop_tree(current_loop, "-after_cons");
1107 irp->callgraph_state = irp_callgraph_and_calltree_consistent;
1110 /* Maximal loop depth of all paths from an external visible method to
1112 int get_irg_loop_depth(ir_graph *irg) {
1113 assert(irp->callgraph_state == irp_callgraph_consistent ||
1114 irp->callgraph_state == irp_callgraph_and_calltree_consistent);
1115 return irg->callgraph_loop_depth;
1118 /* Maximal recursion depth of all paths from an external visible method to
1120 int get_irg_recursion_depth(ir_graph *irg) {
1121 assert(irp->callgraph_state == irp_callgraph_and_calltree_consistent);
1122 return irg->callgraph_recursion_depth;
1125 void analyse_loop_nesting_depth(void) {
1126 entity **free_methods = NULL;
1129 /* establish preconditions. */
1130 if (get_irp_callee_info_state() != irg_callee_info_consistent) {
1131 cgana(&arr_len, &free_methods);
1134 if (irp_callgraph_consistent != get_irp_callgraph_state()) {
1135 compute_callgraph();
1138 find_callgraph_recursions();