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.
22 #include "callgraph.h"
26 #include "irgraph_t.h"
36 /* For callees, we want to remember the Call nodes, too. */
43 typedef struct ana_entry ana_entry;
45 static int master_cg_visited = 0;
46 static INLINE int cg_irg_visited (ir_graph *n);
47 static INLINE void mark_cg_irg_visited(ir_graph *n);
48 static INLINE void set_cg_irg_visited (ir_graph *n, int i);
50 irp_callgraph_state get_irp_callgraph_state(void) {
51 return irp->callgraph_state;
53 void set_irp_callgraph_state(irp_callgraph_state s) {
54 irp->callgraph_state = s;
57 /* The functions that call irg. */
58 int get_irg_n_callers(ir_graph *irg) {
59 if (irg->callers) return ARR_LEN(irg->callers);
62 ir_graph *get_irg_caller(ir_graph *irg, int pos) {
63 assert (pos >= 0 && pos < get_irg_n_callers(irg));
64 if (irg->callers) return irg->callers[pos];
67 int is_irg_caller_backedge(ir_graph *irg, int pos) {
68 assert (pos >= 0 && pos < get_irg_n_callers(irg));
69 return irg->caller_isbe[pos];
72 static void set_irg_caller_backedge(ir_graph *irg, ir_graph *caller) {
73 int i, n_callers = get_irg_n_callers(irg);
74 for (i = 0; i < n_callers; ++i) {
75 if (get_irg_caller(irg, i) == caller) {
76 irg->caller_isbe[i] = 1;
82 int has_irg_caller_backedge(ir_graph *irg) {
83 int i, n_callers = get_irg_n_callers(irg);
84 for (i = 0; i < n_callers; ++i)
85 if (is_irg_caller_backedge(irg, i)) return 1;
89 int get_irg_caller_loop_depth(ir_graph *irg, int pos) {
90 ir_graph *caller = get_irg_caller(irg, pos);
92 /* search the other relation for the corresponding edge. */
94 int i, n_callees = get_irg_n_callees(caller);
95 for (i = 0; i < n_callees; ++i) {
96 if (get_irg_callee(caller, i) == irg) {
102 assert(pos_callee >= 0);
104 return get_irg_callee_loop_depth(caller, pos_callee);
108 /* The functions called by irg. */
109 int get_irg_n_callees(ir_graph *irg) {
110 if (irg->callees) return ARR_LEN(irg->callees);
113 ir_graph *get_irg_callee(ir_graph *irg, int pos) {
114 assert (pos >= 0 && pos < get_irg_n_callees(irg));
115 if (irg->callees) return ((ana_entry *)irg->callees[pos])->irg;
118 int is_irg_callee_backedge(ir_graph *irg, int pos) {
119 assert (pos >= 0 && pos < get_irg_n_callees(irg));
120 return irg->callee_isbe[pos];
122 int has_irg_callee_backedge(ir_graph *irg) {
123 int i, n_callees = get_irg_n_callees(irg);
124 for (i = 0; i < n_callees; ++i)
125 if (is_irg_callee_backedge(irg, i)) return 1;
128 void set_irg_callee_backedge(ir_graph *irg, int pos) {
129 assert (pos >= 0 && pos < get_irg_n_callees(irg));
130 irg->callee_isbe[pos] = 1;
133 int get_irg_callee_loop_depth(ir_graph *irg, int pos) {
134 assert (pos >= 0 && pos < get_irg_n_callees(irg));
135 if (irg->callees) return ((ana_entry *)irg->callees[pos])->max_depth;
139 /* --------------------- Compute the callgraph ------------------------ */
141 /* Hash an address */
142 #define HASH_ADDRESS(adr) (((unsigned)(adr)) >> 3)
145 * Walker called by compute_callgraph()
147 static void ana_Call(ir_node *n, void *env) {
151 if (get_irn_op(n) != op_Call) return;
153 irg = get_irn_irg(n);
154 n_callees = get_Call_n_callees(n);
155 for (i = 0; i < n_callees; ++i) {
156 entity *callee_e = get_Call_callee(n, i);
157 ir_graph *callee = get_entity_irg(callee_e);
158 if (callee) { /* For unknown caller */
159 pset_insert((pset *)callee->callers, irg, (unsigned)irg >> 3);
160 ana_entry buf = { callee, NULL, 0};
161 ana_entry *found = pset_find((pset *)irg->callees, &buf, HASH_ADDRESS(callee));
162 if (found) { /* add Call node to list, compute new nesting. */
163 } else { /* New node, add Call node and init nesting. */
164 found = (ana_entry *) obstack_alloc (irg->obst, sizeof (ana_entry));
166 found->call_list = NULL;
167 found->max_depth = 0;
168 pset_insert((pset *)irg->callees, found, HASH_ADDRESS(callee));
170 int depth = get_loop_depth(get_irn_loop(get_nodes_block(n)));
171 found->max_depth = (depth > found->max_depth) ? depth : found->max_depth;
176 /** compare two ir graphs in a ana_entry */
177 static int ana_entry_cmp(const void *elt, const void *key) {
178 const ana_entry *e1 = elt;
179 const ana_entry *e2 = key;
180 return e1->irg != e2->irg;
183 /** compare two ir graphs */
184 static int graph_cmp(const void *elt, const void *key) {
189 /* Construct and destruct the callgraph. */
190 void compute_callgraph(void) {
191 int i, n_irgs = get_irp_n_irgs();
193 assert(! get_interprocedural_view()); /* Else walking will not reach the Call nodes. */
197 for (i = 0; i < n_irgs; ++i) {
198 ir_graph *irg = get_irp_irg(i);
199 assert(get_irg_callee_info_state(irg) == irg_callee_info_consistent);
200 irg->callees = (ir_graph **)new_pset(ana_entry_cmp, 8);
201 irg->callers = (ir_graph **)new_pset(graph_cmp, 8);
202 construct_cf_backedges(irg);
205 /* Compute the call graph */
206 for (i = 0; i < n_irgs; ++i) {
207 ir_graph *irg = get_irp_irg(i);
208 construct_cf_backedges(irg);
209 irg_walk_graph(irg, ana_Call, NULL, NULL);
212 /* Change the sets to arrays. */
213 for (i = 0; i < n_irgs; ++i) {
215 ir_graph *c, *irg = get_irp_irg(i);
217 pset *callee_set = (pset *)irg->callees;
218 count = pset_count(callee_set);
219 irg->callees = NEW_ARR_F(ir_graph *, count);
220 irg->callee_isbe = calloc(count, sizeof(int));
221 c = pset_first(callee_set);
222 for (j = 0; j < count; ++j) {
224 c = pset_next(callee_set);
226 del_pset(callee_set);
229 pset *caller_set = (pset *)irg->callers;
230 count = pset_count(caller_set);
231 irg->callers = NEW_ARR_F(ir_graph *, count);
232 irg->caller_isbe = calloc(count, sizeof(int));
233 c = pset_first(caller_set);
234 for (j = 0; j < count; ++j) {
236 c = pset_next(caller_set);
238 del_pset(caller_set);
241 set_irp_callgraph_state(irp_callgraph_consistent);
244 void free_callgraph(void) {
245 int i, n_irgs = get_irp_n_irgs();
246 for (i = 0; i < n_irgs; ++i) {
247 ir_graph *irg = get_irp_irg(i);
248 if (irg->callees) DEL_ARR_F(irg->callees);
249 if (irg->callers) DEL_ARR_F(irg->callers);
250 if (irg->callee_isbe) free(irg->callee_isbe);
251 if (irg->caller_isbe) free(irg->caller_isbe);
254 irg->callee_isbe = NULL;
255 irg->caller_isbe = NULL;
257 set_irp_callgraph_state(irp_callgraph_none);
260 /* ----------------------------------------------------------------------------------- */
261 /* A walker for the callgraph */
262 /* ----------------------------------------------------------------------------------- */
265 static void do_walk(ir_graph *irg, callgraph_walk_func *pre, callgraph_walk_func *post, void *env) {
268 if (cg_irg_visited(irg)) return;
269 mark_cg_irg_visited(irg);
273 n_callees = get_irg_n_callees(irg);
274 for (i = 0; i < n_callees; i++) {
275 ir_graph *m = get_irg_callee(irg, i);
276 do_walk(m, pre, post, env);
282 void callgraph_walk(callgraph_walk_func *pre, callgraph_walk_func *post, void *env) {
283 int i, n_irgs = get_irp_n_irgs();
286 do_walk(get_irp_main_irg(), pre, post, env);
287 for (i = 0; i < n_irgs; i++) {
288 ir_graph *irg = get_irp_irg(i);
289 if (!cg_irg_visited(irg) && get_irg_n_callers(irg) == 0)
290 do_walk(irg, pre, post, env);
292 for (i = 0; i < n_irgs; i++) {
293 ir_graph *irg = get_irp_irg(i);
294 if (!cg_irg_visited(irg))
295 do_walk(irg, pre, post, env);
299 /* ----------------------------------------------------------------------------------- */
300 /* loop construction algorithm */
301 /* ----------------------------------------------------------------------------------- */
303 static ir_graph *outermost_ir_graph; /* The outermost graph the scc is computed
305 static ir_loop *current_loop; /* Current cfloop construction is working
307 static int loop_node_cnt = 0; /* Counts the number of allocated cfloop nodes.
308 Each cfloop node gets a unique number.
309 What for? ev. remove. @@@ */
310 static int current_dfn = 1; /* Counter to generate depth first numbering
314 /**********************************************************************/
315 /* Node attributes **/
316 /**********************************************************************/
318 typedef struct scc_info {
319 bool in_stack; /* Marks whether node is on the stack. */
320 int dfn; /* Depth first search number. */
321 int uplink; /* dfn number of ancestor. */
325 static INLINE scc_info* new_scc_info(void) {
326 scc_info *info = obstack_alloc (outermost_ir_graph->obst, sizeof (scc_info));
327 memset (info, 0, sizeof (scc_info));
332 cg_irg_visited(ir_graph *n) {
333 return (((scc_info *)n->link)->visited >= master_cg_visited);
337 mark_cg_irg_visited(ir_graph *n) {
338 ((scc_info *)n->link)->visited = master_cg_visited;
342 set_cg_irg_visited(ir_graph *n, int i) {
343 ((scc_info *)n->link)->visited = i;
347 get_cg_irg_visited(ir_graph *n) {
348 return ((scc_info *)n->link)->visited;
352 mark_irg_in_stack (ir_graph *n) {
353 assert(get_irg_link(n));
354 ((scc_info *)n->link)->in_stack = true;
358 mark_irg_not_in_stack (ir_graph *n) {
359 assert(get_irg_link(n));
360 ((scc_info *)n->link)->in_stack = false;
364 irg_is_in_stack (ir_graph *n) {
365 assert(get_irg_link(n));
366 return ((scc_info *)n->link)->in_stack;
370 set_irg_uplink (ir_graph *n, int uplink) {
371 assert(get_irg_link(n));
372 ((scc_info *)n->link)->uplink = uplink;
376 get_irg_uplink (ir_graph *n) {
377 assert(get_irg_link(n));
378 return ((scc_info *)n->link)->uplink;
382 set_irg_dfn (ir_graph *n, int dfn) {
383 assert(get_irg_link(n));
384 ((scc_info *)n->link)->dfn = dfn;
388 get_irg_dfn (ir_graph *n) {
389 assert(get_irg_link(n));
390 return ((scc_info *)n->link)->dfn;
393 /**********************************************************************/
395 /**********************************************************************/
397 static ir_graph **stack = NULL;
398 static int tos = 0; /* top of stack */
400 static INLINE void init_stack(void) {
402 ARR_RESIZE (ir_graph *, stack, 1000);
404 stack = NEW_ARR_F (ir_graph *, 1000);
413 if (tos == ARR_LEN (stack)) {
414 int nlen = ARR_LEN (stack) * 2;
415 ARR_RESIZE (ir_node *, stack, nlen);
418 mark_irg_in_stack(n);
421 static INLINE ir_graph *
424 ir_graph *n = stack[--tos];
425 mark_irg_not_in_stack(n);
429 /* The nodes up to n belong to the current loop.
430 Removes them from the stack and adds them to the current loop. */
432 pop_scc_to_loop (ir_graph *n)
439 set_irg_dfn(m, loop_node_cnt);
440 add_loop_node(current_loop, (ir_node *)m);
442 //m->callgraph_loop_depth = current_loop->depth;
446 /* GL ??? my last son is my grandson??? Removes cfloops with no
447 ir_nodes in them. Such loops have only another loop as son. (Why
448 can't they have two loops as sons? Does it never get that far? ) */
449 static void close_loop (ir_loop *l)
451 int last = get_loop_n_elements(l) - 1;
452 loop_element lelement = get_loop_element(l, last);
453 ir_loop *last_son = lelement.son;
455 if (get_kind(last_son) == k_ir_loop &&
456 get_loop_n_elements(last_son) == 1) {
459 lelement = get_loop_element(last_son, 0);
461 if(get_kind(gson) == k_ir_loop) {
462 loop_element new_last_son;
464 gson -> outer_loop = l;
465 new_last_son.son = gson;
466 l -> children[last] = new_last_son;
473 /* Removes and unmarks all nodes up to n from the stack.
474 The nodes must be visited once more to assign them to a scc. */
476 pop_scc_unmark_visit (ir_graph *n)
482 set_cg_irg_visited(m, 0);
486 /**********************************************************************/
487 /* The loop datastructure. **/
488 /**********************************************************************/
490 /* Allocates a new loop as son of current_loop. Sets current_loop
491 to the new loop and returns the father. */
492 static ir_loop *new_loop (void) {
493 ir_loop *father, *son;
495 father = current_loop;
497 son = (ir_loop *) obstack_alloc (outermost_ir_graph->obst, sizeof (ir_loop));
498 memset (son, 0, sizeof (ir_loop));
499 son->kind = k_ir_loop;
500 son->children = NEW_ARR_F (loop_element, 0);
504 son->outer_loop = father;
505 add_loop_son(father, son);
506 son->depth = father->depth+1;
507 } else { /* The root loop */
508 son->outer_loop = son;
513 son->loop_nr = get_irp_new_node_nr();
521 /**********************************************************************/
522 /* Constructing and destructing the loop/backedge information. **/
523 /**********************************************************************/
525 /* Initialization steps. **********************************************/
533 for (i = 0; i < get_irp_n_irgs(); ++i) {
534 set_irg_link(get_irp_irg(i), new_scc_info());
535 get_irp_irg(i)->callgraph_recursion_depth = 0;
536 get_irp_irg(i)->callgraph_loop_depth = 0;
540 /** Returns true if n is a loop header, i.e., it is a Block node
541 * and has predecessors within the cfloop and out of the cfloop.
543 * @param root: only needed for assertion.
546 is_head (ir_graph *n, ir_graph *root)
549 int some_outof_loop = 0, some_in_loop = 0;
551 arity = get_irg_n_callees(n);
552 for (i = 0; i < arity; i++) {
553 ir_graph *pred = get_irg_callee(n, i);
554 if (is_irg_callee_backedge(n, i)) continue;
555 if (!irg_is_in_stack(pred)) {
558 if (get_irg_uplink(pred) < get_irg_uplink(root)) {
559 DDMG(pred); DDMG(root);
560 assert(get_irg_uplink(pred) >= get_irg_uplink(root));
566 return some_outof_loop && some_in_loop;
568 /* Returns true if n is possible loop head of an endless loop.
569 I.e., it is a Block, Phi or Filter node and has only predecessors
571 @arg root: only needed for assertion. */
573 is_endless_head (ir_graph *n, ir_graph *root)
576 int some_outof_loop = 0, some_in_loop = 0;
578 arity = get_irg_n_callees(n);
579 for (i = 0; i < arity; i++) {
580 ir_graph *pred = get_irg_callee(n, i);
582 if (is_irg_callee_backedge(n, i)) { continue; }
583 if (!irg_is_in_stack(pred)) {
586 if(get_irg_uplink(pred) < get_irg_uplink(root)) {
587 DDMG(pred); DDMG(root);
588 assert(get_irg_uplink(pred) >= get_irg_uplink(root));
594 return !some_outof_loop && some_in_loop;
598 /* Check whether there is a parallel edge in the ip control flow.
601 is_ip_head (ir_graph *n, ir_graph *pred)
603 int iv_rem = get_interprocedural_view();
604 set_interprocedural_view(true);
605 ir_node *sblock = get_irg_start_block(n);
606 int i, arity = get_Block_n_cfgpreds(sblock);
609 //printf(" edge from "); DDMG(n);
610 //printf(" to pred "); DDMG(pred);
611 //printf(" sblock "); DDMN(sblock);
613 for (i = 0; i < arity; i++) {
614 ir_node *pred_cfop = skip_Proj(get_Block_cfgpred(sblock, i));
615 //printf(" "); DDMN(pred_cfop);
616 if (get_irn_op(pred_cfop) == op_CallBegin) { /* could be Unknown */
617 ir_graph *ip_pred = get_irn_irg(pred_cfop);
618 //printf(" "); DDMG(ip_pred);
619 if ((ip_pred == pred) && is_backedge(sblock, i)) {
620 //printf(" found\n");
626 set_interprocedural_view(iv_rem);
630 /* Returns index of the predecessor with the smallest dfn number
631 greater-equal than limit. */
633 smallest_dfn_pred (ir_graph *n, int limit)
635 int i, index = -2, min = -1;
637 int arity = get_irg_n_callees(n);
638 for (i = 0; i < arity; i++) {
639 ir_graph *pred = get_irg_callee(n, i);
640 if (is_irg_callee_backedge(n, i) || !irg_is_in_stack(pred)) continue;
641 if (get_irg_dfn(pred) >= limit && (min == -1 || get_irg_dfn(pred) < min)) {
643 min = get_irg_dfn(pred);
650 /* Returns index of the predecessor with the largest dfn number. */
652 largest_dfn_pred (ir_graph *n)
654 int i, index = -2, max = -1;
656 int arity = get_irg_n_callees(n);
657 for (i = 0; i < arity; i++) {
658 ir_graph *pred = get_irg_callee(n, i);
659 if (is_irg_callee_backedge (n, i) || !irg_is_in_stack(pred)) continue;
660 if (get_irg_dfn(pred) > max) {
662 max = get_irg_dfn(pred);
671 find_tail (ir_graph *n) {
673 int i, res_index = -2;
676 if (!icfg && rm_cyclic_phis && remove_cyclic_phis (n)) return NULL;
678 m = stack[tos-1]; /* tos = top of stack */
679 if (is_head (m, n)) {
680 res_index = smallest_dfn_pred(m, 0);
681 if ((res_index == -2) && /* no smallest dfn pred found. */
685 if (m == n) return NULL; // Is this to catch Phi - self loops?
686 for (i = tos-2; i >= 0; --i) {
689 if (is_head (m, n)) {
690 res_index = smallest_dfn_pred (m, get_irg_dfn(m) + 1);
691 if (res_index == -2) /* no smallest dfn pred found. */
692 res_index = largest_dfn_pred (m);
694 if ((m == n) && (res_index == -2)) {
700 /* We should not walk past our selves on the stack: The upcoming nodes
701 are not in this loop. We assume a loop not reachable from Start. */
710 /* A dead loop not reachable from Start. */
711 for (i = tos-2; i >= 0; --i) {
713 if (is_endless_head (m, n)) {
714 res_index = smallest_dfn_pred (m, get_irg_dfn(m) + 1);
715 if (res_index == -2) /* no smallest dfn pred found. */
716 res_index = largest_dfn_pred (m);
719 if (m == n) { break; } /* It's not an unreachable loop, either. */
721 //assert(0 && "no head found on stack");
725 assert (res_index > -2);
727 set_irg_callee_backedge (m, res_index);
728 return get_irg_callee(m, res_index);
732 find_tail (ir_graph *n) {
734 int i, res_index = -2;
736 ir_graph *in_and_out = NULL;
737 ir_graph *only_in = NULL;
738 ir_graph *ip_in_and_out = NULL;
739 ir_graph *ip_only_in = NULL;
741 //printf("find tail for "); DDMG(n);
743 for (i = tos-1; i >= 0; --i) {
744 ir_graph *pred = (i < tos -1) ? stack[i+1] : n;
747 if (is_head (m, n)) {
748 //printf(" found 1a! "); DDM;
750 if (is_ip_head(pred, m)) {
751 //printf(" found 1b! "); DDM;
754 } else if (!ip_only_in && is_endless_head(m, n)) {
756 //printf(" found 2a! "); DDM;
757 if (is_ip_head(pred, m)) {
758 //printf(" found 2b! "); DDM;
761 } else if (is_ip_head(pred, m)) {
762 //printf(" found 3! "); DDM; This happens for self recursions in the second
763 //assert(0); scc iteration (the one to flip the loop.)
766 if (ip_in_and_out) break; /* That's what we really want. */
768 if (m == n) break; /* Don't walk past n on the stack! */
772 if (!in_and_out && !only_in)
773 /* There is no loop */
777 /* Is there a head in the callgraph without a head in the
779 assert(in_and_out || only_in);
781 m = (ip_in_and_out) ? ip_in_and_out : ip_only_in;
784 m = (in_and_out) ? in_and_out : only_in;
786 //printf("*** head is "); DDMG(m);
788 res_index = smallest_dfn_pred (m, get_irg_dfn(m) + 1);
789 if (res_index == -2) /* no smallest dfn pred found. */
790 res_index = largest_dfn_pred (m);
792 set_irg_callee_backedge (m, res_index);
793 ir_graph *res = get_irg_callee(m, res_index);
794 //printf("*** tail is "); DDMG(res);
800 /*-----------------------------------------------------------*
801 * The core algorithm. *
802 *-----------------------------------------------------------*/
805 static void cgscc (ir_graph *n) {
808 if (cg_irg_visited(n)) return;
809 mark_cg_irg_visited(n);
811 /* Initialize the node */
812 set_irg_dfn(n, current_dfn); /* Depth first number for this node */
813 set_irg_uplink(n, current_dfn); /* ... is default uplink. */
817 int arity = get_irg_n_callees(n);
819 for (i = 0; i < arity; i++) {
821 if (is_irg_callee_backedge(n, i)) continue;
822 m = get_irg_callee(n, i);
824 /** This marks the backedge, but does it guarantee a correct loop tree? */
825 //if (m == n) { set_irg_callee_backedge(n, i); continue; }
828 if (irg_is_in_stack(m)) {
829 /* Uplink of m is smaller if n->m is a backedge.
830 Propagate the uplink to mark the cfloop. */
831 if (get_irg_uplink(m) < get_irg_uplink(n))
832 set_irg_uplink(n, get_irg_uplink(m));
836 if (get_irg_dfn(n) == get_irg_uplink(n)) {
837 /* This condition holds for
838 1) the node with the incoming backedge.
839 That is: We found a cfloop!
840 2) Straight line code, because no uplink has been propagated, so the
841 uplink still is the same as the dfn.
843 But n might not be a proper cfloop head for the analysis. Proper cfloop
844 heads are Block and Phi nodes. find_tail searches the stack for
845 Block's and Phi's and takes those nodes as cfloop heads for the current
846 cfloop instead and marks the incoming edge as backedge. */
848 ir_graph *tail = find_tail(n);
850 /* We have a cfloop, that is no straight line code,
851 because we found a cfloop head!
852 Next actions: Open a new cfloop on the cfloop tree and
853 try to find inner cfloops */
856 ir_loop *l = new_loop();
858 /* Remove the cfloop from the stack ... */
859 pop_scc_unmark_visit (n);
861 /* The current backedge has been marked, that is temporarily eliminated,
862 by find tail. Start the scc algorithm
863 anew on the subgraph thats left (the current cfloop without the backedge)
864 in order to find more inner cfloops. */
868 assert (cg_irg_visited(n));
878 static void reset_isbe(void) {
879 int i, n_irgs = get_irp_n_irgs();
881 for (i = 0; i < n_irgs; ++i) {
883 ir_graph *irg = get_irp_irg(i);
885 n_cs = get_irg_n_callers(irg);
886 for (j = 0; j < n_cs; ++j) {
887 irg->caller_isbe[j] = 0;
889 n_cs = get_irg_n_callees(irg);
890 for (j = 0; j < n_cs; ++j) {
891 irg->callee_isbe[j] = 0;
899 /* ----------------------------------------------------------------------------------- */
900 /* Another algorithm to compute recursion nesting depth */
901 /* Walk the callgraph. For each crossed edge increase the loop depth by the edge */
902 /* weight. Assign graphs the maximal depth. */
903 /* ----------------------------------------------------------------------------------- */
905 void compute_loop_depth (ir_graph *irg, void *env) {
906 int current_nesting = *(int *) env;
907 int old_nesting = irg->callgraph_loop_depth;
908 int old_visited = get_cg_irg_visited(irg);
913 if (cg_irg_visited(irg)) return;
915 mark_cg_irg_visited(irg);
917 //printf(" old: %d new %d master %d", old_visited, get_cg_irg_visited(irg), master_cg_visited); DDMG(irg);
920 if (old_nesting < current_nesting)
921 irg->callgraph_loop_depth = current_nesting;
923 if (current_nesting > irp->max_callgraph_loop_depth)
924 irp->max_callgraph_loop_depth = current_nesting;
926 if ((old_visited +1 < get_cg_irg_visited(irg)) || /* not yet visited */
927 (old_nesting < current_nesting)) { /* propagate larger nesting */
928 /* Don't walk the graph, but a tree that is an unfolded graph. */
929 n_callees = get_irg_n_callees(irg);
930 for (i = 0; i < n_callees; i++) {
931 ir_graph *m = get_irg_callee(irg, i);
932 *(int *)env += get_irg_callee_loop_depth(irg, i);
933 compute_loop_depth(m, env);
934 *(int *)env -= get_irg_callee_loop_depth(irg, i);
938 set_cg_irg_visited(irg, master_cg_visited-1);
942 /* ----------------------------------------------------------------------------------- */
943 /* Another algorithm to compute recursion nesting depth */
944 /* Walk the callgraph. For each crossed loop increase the nesting depth by one. */
945 /* Assign graphs the maximal nesting depth. Don't increas if passing loops more than */
947 /* ----------------------------------------------------------------------------------- */
950 /* For callees, we want to remember the Call nodes, too. */
952 ir_loop **loop_stack;
954 int recursion_nesting;
957 typedef struct ana_entry2 ana_entry2;
959 static void push2(ana_entry2 *e, ir_loop *g) {
960 if (ARR_LEN(e->loop_stack) == e->tos) {
961 ARR_APP1(ir_loop *, e->loop_stack, g);
963 e->loop_stack[e->tos] = g;
968 static ir_loop *pop2(ana_entry2 *e) {
970 return e->loop_stack[e->tos+1];
973 static int in_stack(ana_entry2 *e, ir_loop *g) {
975 for (i = e->tos-1; i >= 0; --i) {
976 if (e->loop_stack[i] == g) return 1;
981 void compute_rec_depth (ir_graph *irg, void *env) {
982 ana_entry2 *e = (ana_entry2 *)env;
984 int depth, old_depth = irg->callgraph_recursion_depth;
988 if (cg_irg_visited(irg)) return;
989 mark_cg_irg_visited(irg);
991 /* -- compute and set the new nesting value -- */
992 if ((l != irp->outermost_cg_loop) && !in_stack(e, l)) {
994 e->recursion_nesting++;
997 depth = e->recursion_nesting;
999 if (old_depth < depth)
1000 irg->callgraph_recursion_depth = depth;
1002 if (depth > irp->max_callgraph_recursion_depth)
1003 irp->max_callgraph_recursion_depth = depth;
1005 /* -- spread the nesting value -- */
1006 if (depth == 0 || old_depth < depth) {
1007 /* Don't walk the graph, but a tree that is an unfolded graph. */
1008 n_callees = get_irg_n_callees(irg);
1009 for (i = 0; i < n_callees; i++) {
1010 ir_graph *m = get_irg_callee(irg, i);
1011 compute_rec_depth(m, env);
1015 /* -- clean up -- */
1018 e->recursion_nesting--;
1020 set_cg_irg_visited(irg, master_cg_visited-1);
1024 /* Compute the backedges that represent recursions. */
1025 void find_callgraph_recursions(void) {
1026 int i, n_irgs = get_irp_n_irgs();
1030 /* -- Compute the looptree -- */
1032 /* The outermost graph. We start here. Then we start at all
1033 functions in irg list that are never called, then at the remaining
1035 assert(get_irp_main_irg());
1036 outermost_ir_graph = get_irp_main_irg();
1039 current_loop = NULL;
1040 new_loop(); /* sets current_loop */
1042 master_cg_visited++;
1043 cgscc(outermost_ir_graph);
1044 for (i = 0; i < n_irgs; i++) {
1045 ir_graph *irg = get_irp_irg(i);
1046 if (!cg_irg_visited(irg) && get_irg_n_callers(irg) == 0)
1049 for (i = 0; i < n_irgs; i++) {
1050 ir_graph *irg = get_irp_irg(i);
1051 if (!cg_irg_visited(irg))
1054 irp->outermost_cg_loop = current_loop;
1056 /* -- Reverse the backedge information. -- */
1057 for (i = 0; i < n_irgs; i++) {
1058 ir_graph *irg = get_irp_irg(i);
1059 int j, n_callees = get_irg_n_callees(irg);
1060 for (j = 0; j < n_callees; ++j) {
1061 if (is_irg_callee_backedge(irg, j))
1062 set_irg_caller_backedge(get_irg_callee(irg, j), irg);
1066 /* -- compute the loop depth -- */
1067 int current_nesting = 0;
1068 irp->max_callgraph_loop_depth = 0;
1069 master_cg_visited += 2;
1070 //printf (" ** starting at "); DDMG(get_irp_main_irg());
1071 compute_loop_depth(get_irp_main_irg(), ¤t_nesting);
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 get_irg_n_callers(irg) == 0) {
1076 compute_loop_depth(irg, ¤t_nesting);
1077 //printf (" ** starting at "); DDMG(irg);
1080 for (i = 0; i < n_irgs; i++) {
1081 ir_graph *irg = get_irp_irg(i);
1082 if (get_cg_irg_visited(irg) < master_cg_visited-1) {
1083 compute_loop_depth(irg, ¤t_nesting);
1084 //printf (" ** starting at "); DDMG(irg);
1088 /* -- compute the recursion depth -- */
1090 e.loop_stack = NEW_ARR_F(ir_loop *, 0);
1092 e.recursion_nesting = 0;
1093 irp->max_callgraph_recursion_depth = 0;
1095 master_cg_visited += 2;
1096 compute_rec_depth(get_irp_main_irg(), &e);
1097 //printf (" ++ starting at "); DDMG(get_irp_main_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 get_irg_n_callers(irg) == 0) {
1102 compute_rec_depth(irg, &e);
1103 //printf (" ++ starting at "); DDMG(irg);
1106 for (i = 0; i < n_irgs; i++) {
1107 ir_graph *irg = get_irp_irg(i);
1108 if (get_cg_irg_visited(irg) < master_cg_visited-1) {
1109 compute_rec_depth(irg, &e);
1110 //printf (" ++ starting at "); DDMG(irg);
1114 DEL_ARR_F(e.loop_stack);
1116 //dump_callgraph("-with_nesting");
1118 //dump_callgraph_loop_tree(current_loop, "-after_cons");
1119 irp->callgraph_state = irp_callgraph_and_calltree_consistent;
1122 /* Maximal loop depth of all paths from an external visible method to
1124 int get_irg_loop_depth(ir_graph *irg) {
1125 assert(irp->callgraph_state == irp_callgraph_consistent ||
1126 irp->callgraph_state == irp_callgraph_and_calltree_consistent);
1127 return irg->callgraph_loop_depth;
1130 /* Maximal recursion depth of all paths from an external visible method to
1132 int get_irg_recursion_depth(ir_graph *irg) {
1133 assert(irp->callgraph_state == irp_callgraph_and_calltree_consistent);
1134 return irg->callgraph_recursion_depth;
1137 void analyse_loop_nesting_depth(void) {
1138 entity **free_methods = NULL;
1141 /* establish preconditions. */
1142 if (get_irp_callee_info_state() != irg_callee_info_consistent) {
1143 cgana(&arr_len, &free_methods);
1146 if (irp_callgraph_consistent != get_irp_callgraph_state()) {
1147 compute_callgraph();
1150 find_callgraph_recursions();