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 ana_entry buf = { callee, NULL, 0};
163 pset_insert((pset *)callee->callers, irg, (unsigned)irg >> 3);
164 found = pset_find((pset *)irg->callees, &buf, HASH_ADDRESS(callee));
165 if (found) { /* add Call node to list, compute new nesting. */
166 } else { /* New node, add Call node and init nesting. */
167 found = (ana_entry *) obstack_alloc (irg->obst, sizeof (ana_entry));
169 found->call_list = NULL;
170 found->max_depth = 0;
171 pset_insert((pset *)irg->callees, found, HASH_ADDRESS(callee));
173 depth = get_loop_depth(get_irn_loop(get_nodes_block(n)));
174 found->max_depth = (depth > found->max_depth) ? depth : found->max_depth;
179 /** compare two ir graphs in a ana_entry */
180 static int ana_entry_cmp(const void *elt, const void *key) {
181 const ana_entry *e1 = elt;
182 const ana_entry *e2 = key;
183 return e1->irg != e2->irg;
186 /** compare two ir graphs */
187 static int graph_cmp(const void *elt, const void *key) {
192 /* Construct and destruct the callgraph. */
193 void compute_callgraph(void) {
194 int i, n_irgs = get_irp_n_irgs();
196 assert(! get_interprocedural_view()); /* Else walking will not reach the Call nodes. */
200 for (i = 0; i < n_irgs; ++i) {
201 ir_graph *irg = get_irp_irg(i);
202 assert(get_irg_callee_info_state(irg) == irg_callee_info_consistent);
203 irg->callees = (ir_graph **)new_pset(ana_entry_cmp, 8);
204 irg->callers = (ir_graph **)new_pset(graph_cmp, 8);
205 construct_cf_backedges(irg);
208 /* Compute the call graph */
209 for (i = 0; i < n_irgs; ++i) {
210 ir_graph *irg = get_irp_irg(i);
211 construct_cf_backedges(irg);
212 irg_walk_graph(irg, ana_Call, NULL, NULL);
215 /* Change the sets to arrays. */
216 for (i = 0; i < n_irgs; ++i) {
218 ir_graph *c, *irg = get_irp_irg(i);
219 pset *callee_set, *caller_set;
221 callee_set = (pset *)irg->callees;
222 count = pset_count(callee_set);
223 irg->callees = NEW_ARR_F(ir_graph *, count);
224 irg->callee_isbe = xcalloc(count, sizeof(irg->callee_isbe[0]));
225 c = pset_first(callee_set);
226 for (j = 0; j < count; ++j) {
228 c = pset_next(callee_set);
230 del_pset(callee_set);
233 caller_set = (pset *)irg->callers;
234 count = pset_count(caller_set);
235 irg->callers = NEW_ARR_F(ir_graph *, count);
236 irg->caller_isbe = xcalloc(count, sizeof(irg->caller_isbe[0]));
237 c = pset_first(caller_set);
238 for (j = 0; j < count; ++j) {
240 c = pset_next(caller_set);
242 del_pset(caller_set);
245 set_irp_callgraph_state(irp_callgraph_consistent);
248 void free_callgraph(void) {
249 int i, n_irgs = get_irp_n_irgs();
250 for (i = 0; i < n_irgs; ++i) {
251 ir_graph *irg = get_irp_irg(i);
252 if (irg->callees) DEL_ARR_F(irg->callees);
253 if (irg->callers) DEL_ARR_F(irg->callers);
254 if (irg->callee_isbe) free(irg->callee_isbe);
255 if (irg->caller_isbe) free(irg->caller_isbe);
258 irg->callee_isbe = NULL;
259 irg->caller_isbe = NULL;
261 set_irp_callgraph_state(irp_callgraph_none);
264 /* ----------------------------------------------------------------------------------- */
265 /* A walker for the callgraph */
266 /* ----------------------------------------------------------------------------------- */
269 static void do_walk(ir_graph *irg, callgraph_walk_func *pre, callgraph_walk_func *post, void *env) {
272 if (cg_irg_visited(irg)) return;
273 mark_cg_irg_visited(irg);
277 n_callees = get_irg_n_callees(irg);
278 for (i = 0; i < n_callees; i++) {
279 ir_graph *m = get_irg_callee(irg, i);
280 do_walk(m, pre, post, env);
286 void callgraph_walk(callgraph_walk_func *pre, callgraph_walk_func *post, void *env) {
287 int i, n_irgs = get_irp_n_irgs();
290 do_walk(get_irp_main_irg(), pre, post, env);
291 for (i = 0; i < n_irgs; i++) {
292 ir_graph *irg = get_irp_irg(i);
293 if (!cg_irg_visited(irg) && get_irg_n_callers(irg) == 0)
294 do_walk(irg, pre, post, env);
296 for (i = 0; i < n_irgs; i++) {
297 ir_graph *irg = get_irp_irg(i);
298 if (!cg_irg_visited(irg))
299 do_walk(irg, pre, post, env);
303 /* ----------------------------------------------------------------------------------- */
304 /* loop construction algorithm */
305 /* ----------------------------------------------------------------------------------- */
307 static ir_graph *outermost_ir_graph; /**< The outermost graph the scc is computed
309 static ir_loop *current_loop; /**< Current cfloop construction is working
311 static int loop_node_cnt = 0; /**< Counts the number of allocated cfloop nodes.
312 Each cfloop node gets a unique number.
313 What for? ev. remove. @@@ */
314 static int current_dfn = 1; /**< Counter to generate depth first numbering
318 /**********************************************************************/
319 /* Node attributes **/
320 /**********************************************************************/
322 typedef struct scc_info {
323 bool in_stack; /**< Marks whether node is on the stack. */
324 int dfn; /**< Depth first search number. */
325 int uplink; /**< dfn number of ancestor. */
330 * allocates a new scc_info of the obstack
332 static INLINE scc_info *new_scc_info(void) {
333 scc_info *info = obstack_alloc (outermost_ir_graph->obst, sizeof(*info));
334 memset(info, 0, sizeof(*info));
339 cg_irg_visited(ir_graph *n) {
340 scc_info *info = get_irg_link(n);
341 return (info->visited >= master_cg_visited);
345 mark_cg_irg_visited(ir_graph *n) {
346 scc_info *info = get_irg_link(n);
347 info->visited = master_cg_visited;
351 set_cg_irg_visited(ir_graph *n, int i) {
352 scc_info *info = get_irg_link(n);
357 get_cg_irg_visited(ir_graph *n) {
358 scc_info *info = get_irg_link(n);
359 return info->visited;
363 mark_irg_in_stack (ir_graph *n) {
364 scc_info *info = get_irg_link(n);
366 info->in_stack = true;
370 mark_irg_not_in_stack (ir_graph *n) {
371 scc_info *info = get_irg_link(n);
373 info->in_stack = false;
377 irg_is_in_stack (ir_graph *n) {
378 scc_info *info = get_irg_link(n);
380 return info->in_stack;
384 set_irg_uplink (ir_graph *n, int uplink) {
385 scc_info *info = get_irg_link(n);
387 info->uplink = uplink;
391 get_irg_uplink (ir_graph *n) {
392 scc_info *info = get_irg_link(n);
398 set_irg_dfn (ir_graph *n, int dfn) {
399 scc_info *info = get_irg_link(n);
405 get_irg_dfn (ir_graph *n) {
406 scc_info *info = get_irg_link(n);
411 /**********************************************************************/
413 /**********************************************************************/
415 static ir_graph **stack = NULL;
416 static int tos = 0; /**< top of stack */
419 * initialize the irg stack
421 static INLINE void init_stack(void) {
423 ARR_RESIZE (ir_graph *, stack, 1000);
425 stack = NEW_ARR_F (ir_graph *, 1000);
431 * push a graph on the irg stack
432 * @param n the graph to be pushed
437 if (tos == ARR_LEN (stack)) {
438 int nlen = ARR_LEN (stack) * 2;
439 ARR_RESIZE (ir_node *, stack, nlen);
442 mark_irg_in_stack(n);
446 * return the topmost graph on the stack and pop it
448 static INLINE ir_graph *
451 ir_graph *n = stack[--tos];
452 mark_irg_not_in_stack(n);
457 * The nodes up to n belong to the current loop.
458 * Removes them from the stack and adds them to the current loop.
461 pop_scc_to_loop (ir_graph *n)
468 set_irg_dfn(m, loop_node_cnt);
469 add_loop_node(current_loop, (ir_node *)m);
471 //m->callgraph_loop_depth = current_loop->depth;
475 /* GL ??? my last son is my grandson??? Removes cfloops with no
476 ir_nodes in them. Such loops have only another loop as son. (Why
477 can't they have two loops as sons? Does it never get that far? ) */
478 static void close_loop (ir_loop *l)
480 int last = get_loop_n_elements(l) - 1;
481 loop_element lelement = get_loop_element(l, last);
482 ir_loop *last_son = lelement.son;
484 if (get_kind(last_son) == k_ir_loop &&
485 get_loop_n_elements(last_son) == 1) {
488 lelement = get_loop_element(last_son, 0);
490 if(get_kind(gson) == k_ir_loop) {
491 loop_element new_last_son;
493 gson -> outer_loop = l;
494 new_last_son.son = gson;
495 l -> children[last] = new_last_son;
503 * Removes and unmarks all nodes up to n from the stack.
504 * The nodes must be visited once more to assign them to a scc.
507 pop_scc_unmark_visit (ir_graph *n)
513 set_cg_irg_visited(m, 0);
517 /**********************************************************************/
518 /* The loop data structure. **/
519 /**********************************************************************/
522 * Allocates a new loop as son of current_loop. Sets current_loop
523 * to the new loop and returns the father.
525 static ir_loop *new_loop (void) {
526 ir_loop *father, *son;
528 father = current_loop;
530 son = obstack_alloc (outermost_ir_graph->obst, sizeof(*son));
531 memset (son, 0, sizeof(*son));
532 son->kind = k_ir_loop;
533 son->children = NEW_ARR_F (loop_element, 0);
537 son->outer_loop = father;
538 add_loop_son(father, son);
539 son->depth = father->depth + 1;
540 } else { /* The root loop */
541 son->outer_loop = son;
546 son->loop_nr = get_irp_new_node_nr();
554 /**********************************************************************/
555 /* Constructing and destructing the loop/backedge information. **/
556 /**********************************************************************/
558 /* Initialization steps. **********************************************/
569 n_irgs = get_irp_n_irgs();
570 for (i = 0; i < n_irgs; ++i) {
571 ir_graph *irg = get_irp_irg(i);
572 set_irg_link(irg, new_scc_info());
573 irg->callgraph_recursion_depth = 0;
574 irg->callgraph_loop_depth = 0;
578 /** Returns true if n is a loop header, i.e., it is a Block node
579 * and has predecessors within the cfloop and out of the cfloop.
581 * @param root: only needed for assertion.
584 is_head (ir_graph *n, ir_graph *root)
587 int some_outof_loop = 0, some_in_loop = 0;
589 arity = get_irg_n_callees(n);
590 for (i = 0; i < arity; i++) {
591 ir_graph *pred = get_irg_callee(n, i);
592 if (is_irg_callee_backedge(n, i)) continue;
593 if (!irg_is_in_stack(pred)) {
596 if (get_irg_uplink(pred) < get_irg_uplink(root)) {
597 DDMG(pred); DDMG(root);
598 assert(get_irg_uplink(pred) >= get_irg_uplink(root));
604 return some_outof_loop & some_in_loop;
608 * Returns true if n is possible loop head of an endless loop.
609 * I.e., it is a Block, Phi or Filter node and has only predecessors
611 * @arg root: only needed for assertion.
614 is_endless_head (ir_graph *n, ir_graph *root)
617 int some_outof_loop = 0, some_in_loop = 0;
619 arity = get_irg_n_callees(n);
620 for (i = 0; i < arity; i++) {
621 ir_graph *pred = get_irg_callee(n, i);
623 if (is_irg_callee_backedge(n, i)) { continue; }
624 if (!irg_is_in_stack(pred)) {
627 if(get_irg_uplink(pred) < get_irg_uplink(root)) {
628 DDMG(pred); DDMG(root);
629 assert(get_irg_uplink(pred) >= get_irg_uplink(root));
635 return !some_outof_loop & some_in_loop;
640 * Check whether there is a parallel edge in the ip control flow.
644 is_ip_head (ir_graph *n, ir_graph *pred)
647 int iv_rem = get_interprocedural_view();
648 set_interprocedural_view(true);
650 ir_node *sblock = get_irg_start_block(n);
651 int i, arity = get_Block_n_cfgpreds(sblock);
653 //printf(" edge from "); DDMG(n);
654 //printf(" to pred "); DDMG(pred);
655 //printf(" sblock "); DDMN(sblock);
657 for (i = 0; i < arity; i++) {
658 ir_node *pred_cfop = skip_Proj(get_Block_cfgpred(sblock, i));
659 //printf(" "); DDMN(pred_cfop);
660 if (get_irn_op(pred_cfop) == op_CallBegin) { /* could be Unknown */
661 ir_graph *ip_pred = get_irn_irg(pred_cfop);
662 //printf(" "); DDMG(ip_pred);
663 if ((ip_pred == pred) && is_backedge(sblock, i)) {
664 //printf(" found\n");
670 set_interprocedural_view(iv_rem);
675 * Returns index of the predecessor with the smallest dfn number
676 * greater-equal than limit.
679 smallest_dfn_pred (ir_graph *n, int limit)
681 int i, index = -2, min = -1;
683 int arity = get_irg_n_callees(n);
684 for (i = 0; i < arity; i++) {
685 ir_graph *pred = get_irg_callee(n, i);
686 if (is_irg_callee_backedge(n, i) || !irg_is_in_stack(pred)) continue;
687 if (get_irg_dfn(pred) >= limit && (min == -1 || get_irg_dfn(pred) < min)) {
689 min = get_irg_dfn(pred);
696 /** Returns index of the predecessor with the largest dfn number. */
698 largest_dfn_pred (ir_graph *n)
700 int i, index = -2, max = -1;
702 int arity = get_irg_n_callees(n);
703 for (i = 0; i < arity; i++) {
704 ir_graph *pred = get_irg_callee(n, i);
705 if (is_irg_callee_backedge (n, i) || !irg_is_in_stack(pred)) continue;
706 if (get_irg_dfn(pred) > max) {
708 max = get_irg_dfn(pred);
717 find_tail (ir_graph *n) {
719 int i, res_index = -2;
722 if (!icfg && rm_cyclic_phis && remove_cyclic_phis (n)) return NULL;
724 m = stack[tos-1]; /* tos = top of stack */
725 if (is_head (m, n)) {
726 res_index = smallest_dfn_pred(m, 0);
727 if ((res_index == -2) && /* no smallest dfn pred found. */
731 if (m == n) return NULL; // Is this to catch Phi - self loops?
732 for (i = tos-2; i >= 0; --i) {
735 if (is_head (m, n)) {
736 res_index = smallest_dfn_pred (m, get_irg_dfn(m) + 1);
737 if (res_index == -2) /* no smallest dfn pred found. */
738 res_index = largest_dfn_pred (m);
740 if ((m == n) && (res_index == -2)) {
746 /* We should not walk past our selves on the stack: The upcoming nodes
747 are not in this loop. We assume a loop not reachable from Start. */
756 /* A dead loop not reachable from Start. */
757 for (i = tos-2; i >= 0; --i) {
759 if (is_endless_head (m, n)) {
760 res_index = smallest_dfn_pred (m, get_irg_dfn(m) + 1);
761 if (res_index == -2) /* no smallest dfn pred found. */
762 res_index = largest_dfn_pred (m);
765 if (m == n) { break; } /* It's not an unreachable loop, either. */
767 //assert(0 && "no head found on stack");
771 assert (res_index > -2);
773 set_irg_callee_backedge (m, res_index);
774 return get_irg_callee(m, res_index);
778 find_tail (ir_graph *n) {
780 int i, res_index = -2;
783 ir_graph *in_and_out = NULL;
784 ir_graph *only_in = NULL;
785 ir_graph *ip_in_and_out = NULL;
786 ir_graph *ip_only_in = NULL;
788 //printf("find tail for "); DDMG(n);
790 for (i = tos-1; i >= 0; --i) {
791 ir_graph *pred = (i < tos -1) ? stack[i+1] : n;
794 if (is_head (m, n)) {
795 //printf(" found 1a! "); DDM;
797 if (is_ip_head(pred, m)) {
798 //printf(" found 1b! "); DDM;
801 } else if (!ip_only_in && is_endless_head(m, n)) {
803 //printf(" found 2a! "); DDM;
804 if (is_ip_head(pred, m)) {
805 //printf(" found 2b! "); DDM;
808 } else if (is_ip_head(pred, m)) {
809 //printf(" found 3! "); DDM; This happens for self recursions in the second
810 //assert(0); scc iteration (the one to flip the loop.)
813 if (ip_in_and_out) break; /* That's what we really want. */
815 if (m == n) break; /* Don't walk past n on the stack! */
819 if (!in_and_out && !only_in)
820 /* There is no loop */
824 /* Is there a head in the callgraph without a head in the
826 assert(in_and_out || only_in);
828 m = (ip_in_and_out) ? ip_in_and_out : ip_only_in;
831 m = (in_and_out) ? in_and_out : only_in;
833 //printf("*** head is "); DDMG(m);
835 res_index = smallest_dfn_pred (m, get_irg_dfn(m) + 1);
836 if (res_index == -2) /* no smallest dfn pred found. */
837 res_index = largest_dfn_pred (m);
839 set_irg_callee_backedge (m, res_index);
840 res = get_irg_callee(m, res_index);
841 //printf("*** tail is "); DDMG(res);
847 /*-----------------------------------------------------------*
848 * The core algorithm. *
849 *-----------------------------------------------------------*/
852 static void cgscc (ir_graph *n) {
855 if (cg_irg_visited(n)) return;
856 mark_cg_irg_visited(n);
858 /* Initialize the node */
859 set_irg_dfn(n, current_dfn); /* Depth first number for this node */
860 set_irg_uplink(n, current_dfn); /* ... is default uplink. */
864 arity = get_irg_n_callees(n);
865 for (i = 0; i < arity; i++) {
867 if (is_irg_callee_backedge(n, i)) continue;
868 m = get_irg_callee(n, i);
870 /** This marks the backedge, but does it guarantee a correct loop tree? */
871 //if (m == n) { set_irg_callee_backedge(n, i); continue; }
874 if (irg_is_in_stack(m)) {
875 /* Uplink of m is smaller if n->m is a backedge.
876 Propagate the uplink to mark the cfloop. */
877 if (get_irg_uplink(m) < get_irg_uplink(n))
878 set_irg_uplink(n, get_irg_uplink(m));
882 if (get_irg_dfn(n) == get_irg_uplink(n)) {
883 /* This condition holds for
884 1) the node with the incoming backedge.
885 That is: We found a cfloop!
886 2) Straight line code, because no uplink has been propagated, so the
887 uplink still is the same as the dfn.
889 But n might not be a proper cfloop head for the analysis. Proper cfloop
890 heads are Block and Phi nodes. find_tail searches the stack for
891 Block's and Phi's and takes those nodes as cfloop heads for the current
892 cfloop instead and marks the incoming edge as backedge. */
894 ir_graph *tail = find_tail(n);
896 /* We have a cfloop, that is no straight line code,
897 because we found a cfloop head!
898 Next actions: Open a new cfloop on the cfloop tree and
899 try to find inner cfloops */
902 ir_loop *l = new_loop();
904 /* Remove the cfloop from the stack ... */
905 pop_scc_unmark_visit (n);
907 /* The current backedge has been marked, that is temporarily eliminated,
908 by find tail. Start the scc algorithm
909 anew on the subgraph thats left (the current cfloop without the backedge)
910 in order to find more inner cfloops. */
914 assert (cg_irg_visited(n));
924 * reset the backedge information for all callers in all irgs
926 static void reset_isbe(void) {
927 int i, n_irgs = get_irp_n_irgs();
929 for (i = 0; i < n_irgs; ++i) {
931 ir_graph *irg = get_irp_irg(i);
933 n_cs = get_irg_n_callers(irg);
934 for (j = 0; j < n_cs; ++j) {
935 irg->caller_isbe[j] = 0;
938 n_cs = get_irg_n_callees(irg);
939 for (j = 0; j < n_cs; ++j) {
940 irg->callee_isbe[j] = 0;
948 /* ----------------------------------------------------------------------------------- */
949 /* Another algorithm to compute recursion nesting depth */
950 /* Walk the callgraph. For each crossed edge increase the loop depth by the edge */
951 /* weight. Assign graphs the maximal depth. */
952 /* ----------------------------------------------------------------------------------- */
954 void compute_loop_depth (ir_graph *irg, void *env) {
955 int current_nesting = *(int *) env;
956 int old_nesting = irg->callgraph_loop_depth;
957 int old_visited = get_cg_irg_visited(irg);
962 if (cg_irg_visited(irg)) return;
964 mark_cg_irg_visited(irg);
966 //printf(" old: %d new %d master %d", old_visited, get_cg_irg_visited(irg), master_cg_visited); DDMG(irg);
969 if (old_nesting < current_nesting)
970 irg->callgraph_loop_depth = current_nesting;
972 if (current_nesting > irp->max_callgraph_loop_depth)
973 irp->max_callgraph_loop_depth = current_nesting;
975 if ((old_visited +1 < get_cg_irg_visited(irg)) || /* not yet visited */
976 (old_nesting < current_nesting)) { /* propagate larger nesting */
977 /* Don't walk the graph, but a tree that is an unfolded graph. */
978 n_callees = get_irg_n_callees(irg);
979 for (i = 0; i < n_callees; i++) {
980 ir_graph *m = get_irg_callee(irg, i);
981 *(int *)env += get_irg_callee_loop_depth(irg, i);
982 compute_loop_depth(m, env);
983 *(int *)env -= get_irg_callee_loop_depth(irg, i);
987 set_cg_irg_visited(irg, master_cg_visited-1);
991 /* ------------------------------------------------------------------------------------ */
992 /* Another algorithm to compute recursion nesting depth */
993 /* Walk the callgraph. For each crossed loop increase the nesting depth by one. */
994 /* Assign graphs the maximal nesting depth. Don't increase if passing loops more than */
996 /* ------------------------------------------------------------------------------------ */
999 /* For callees, we want to remember the Call nodes, too. */
1000 typedef struct ana_entry2 {
1001 ir_loop **loop_stack; /**< a stack of ir_loop entries */
1002 int tos; /**< the top of stack entry */
1003 int recursion_nesting;
1007 * push a loop entry on the stack
1009 static void push2(ana_entry2 *e, ir_loop *g) {
1010 if (ARR_LEN(e->loop_stack) == e->tos) {
1011 ARR_APP1(ir_loop *, e->loop_stack, g);
1013 e->loop_stack[e->tos] = g;
1019 * returns the top of stack and pop it
1021 static ir_loop *pop2(ana_entry2 *e) {
1022 return e->loop_stack[--e->tos];
1026 * check if a loop g in on the stack. Did not check the TOS.
1028 static int in_stack(ana_entry2 *e, ir_loop *g) {
1030 for (i = e->tos-1; i >= 0; --i) {
1031 if (e->loop_stack[i] == g) return 1;
1036 static void compute_rec_depth (ir_graph *irg, void *env) {
1037 ana_entry2 *e = (ana_entry2 *)env;
1038 ir_loop *l = irg->l;
1039 int depth, old_depth = irg->callgraph_recursion_depth;
1043 if (cg_irg_visited(irg)) return;
1044 mark_cg_irg_visited(irg);
1046 /* -- compute and set the new nesting value -- */
1047 if ((l != irp->outermost_cg_loop) && !in_stack(e, l)) {
1049 e->recursion_nesting++;
1052 depth = e->recursion_nesting;
1054 if (old_depth < depth)
1055 irg->callgraph_recursion_depth = depth;
1057 if (depth > irp->max_callgraph_recursion_depth)
1058 irp->max_callgraph_recursion_depth = depth;
1060 /* -- spread the nesting value -- */
1061 if (depth == 0 || old_depth < depth) {
1062 /* Don't walk the graph, but a tree that is an unfolded graph. */
1063 n_callees = get_irg_n_callees(irg);
1064 for (i = 0; i < n_callees; i++) {
1065 ir_graph *m = get_irg_callee(irg, i);
1066 compute_rec_depth(m, env);
1070 /* -- clean up -- */
1073 e->recursion_nesting--;
1075 set_cg_irg_visited(irg, master_cg_visited-1);
1079 /* Compute the backedges that represent recursions. */
1080 void find_callgraph_recursions(void) {
1081 int i, n_irgs = get_irp_n_irgs();
1082 int current_nesting;
1087 /* -- Compute the looptree -- */
1089 /* The outermost graph. We start here. Then we start at all
1090 functions in irg list that are never called, then at the remaining
1092 assert(get_irp_main_irg());
1093 outermost_ir_graph = get_irp_main_irg();
1096 current_loop = NULL;
1097 new_loop(); /* sets current_loop */
1099 master_cg_visited++;
1100 cgscc(outermost_ir_graph);
1101 for (i = 0; i < n_irgs; i++) {
1102 ir_graph *irg = get_irp_irg(i);
1103 if (!cg_irg_visited(irg) && get_irg_n_callers(irg) == 0)
1106 for (i = 0; i < n_irgs; i++) {
1107 ir_graph *irg = get_irp_irg(i);
1108 if (!cg_irg_visited(irg))
1111 irp->outermost_cg_loop = current_loop;
1113 /* -- Reverse the backedge information. -- */
1114 for (i = 0; i < n_irgs; i++) {
1115 ir_graph *irg = get_irp_irg(i);
1116 int j, n_callees = get_irg_n_callees(irg);
1117 for (j = 0; j < n_callees; ++j) {
1118 if (is_irg_callee_backedge(irg, j))
1119 set_irg_caller_backedge(get_irg_callee(irg, j), irg);
1123 /* -- compute the loop depth -- */
1124 current_nesting = 0;
1125 irp->max_callgraph_loop_depth = 0;
1126 master_cg_visited += 2;
1127 //printf (" ** starting at "); DDMG(get_irp_main_irg());
1128 compute_loop_depth(get_irp_main_irg(), ¤t_nesting);
1129 for (i = 0; i < n_irgs; i++) {
1130 ir_graph *irg = get_irp_irg(i);
1131 if ((get_cg_irg_visited(irg) < master_cg_visited-1) &&
1132 get_irg_n_callers(irg) == 0) {
1133 compute_loop_depth(irg, ¤t_nesting);
1134 //printf (" ** starting at "); DDMG(irg);
1137 for (i = 0; i < n_irgs; i++) {
1138 ir_graph *irg = get_irp_irg(i);
1139 if (get_cg_irg_visited(irg) < master_cg_visited-1) {
1140 compute_loop_depth(irg, ¤t_nesting);
1141 //printf (" ** starting at "); DDMG(irg);
1145 /* -- compute the recursion depth -- */
1146 e.loop_stack = NEW_ARR_F(ir_loop *, 0);
1148 e.recursion_nesting = 0;
1149 irp->max_callgraph_recursion_depth = 0;
1151 master_cg_visited += 2;
1152 compute_rec_depth(get_irp_main_irg(), &e);
1153 //printf (" ++ starting at "); DDMG(get_irp_main_irg());
1154 for (i = 0; i < n_irgs; i++) {
1155 ir_graph *irg = get_irp_irg(i);
1156 if ((get_cg_irg_visited(irg) < master_cg_visited-1) &&
1157 get_irg_n_callers(irg) == 0) {
1158 compute_rec_depth(irg, &e);
1159 //printf (" ++ starting at "); DDMG(irg);
1162 for (i = 0; i < n_irgs; i++) {
1163 ir_graph *irg = get_irp_irg(i);
1164 if (get_cg_irg_visited(irg) < master_cg_visited-1) {
1165 compute_rec_depth(irg, &e);
1166 //printf (" ++ starting at "); DDMG(irg);
1170 DEL_ARR_F(e.loop_stack);
1172 //dump_callgraph("-with_nesting");
1174 //dump_callgraph_loop_tree(current_loop, "-after_cons");
1175 irp->callgraph_state = irp_callgraph_and_calltree_consistent;
1178 /* Maximal loop depth of all paths from an external visible method to
1180 int get_irg_loop_depth(ir_graph *irg) {
1181 assert(irp->callgraph_state == irp_callgraph_consistent ||
1182 irp->callgraph_state == irp_callgraph_and_calltree_consistent);
1183 return irg->callgraph_loop_depth;
1186 /* Maximal recursion depth of all paths from an external visible method to
1188 int get_irg_recursion_depth(ir_graph *irg) {
1189 assert(irp->callgraph_state == irp_callgraph_and_calltree_consistent);
1190 return irg->callgraph_recursion_depth;
1193 void analyse_loop_nesting_depth(void) {
1194 entity **free_methods = NULL;
1197 /* establish preconditions. */
1198 if (get_irp_callee_info_state() != irg_callee_info_consistent) {
1199 cgana(&arr_len, &free_methods);
1202 if (irp_callgraph_consistent != get_irp_callgraph_state()) {
1203 compute_callgraph();
1206 find_callgraph_recursions();