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.
23 #include "callgraph.h"
27 #include "irgraph_t.h"
31 #include "execution_frequency.h"
39 /* For callees, we want to remember the Call nodes, too. */
46 typedef struct ana_entry ana_entry;
48 static int master_cg_visited = 0;
49 static INLINE int cg_irg_visited (ir_graph *n);
50 static INLINE void mark_cg_irg_visited(ir_graph *n);
51 static INLINE void set_cg_irg_visited (ir_graph *n, int i);
53 irp_callgraph_state get_irp_callgraph_state(void) {
54 return irp->callgraph_state;
56 void set_irp_callgraph_state(irp_callgraph_state s) {
57 irp->callgraph_state = s;
60 /* The functions that call irg. */
61 int get_irg_n_callers(ir_graph *irg) {
62 if (irg->callers) return ARR_LEN(irg->callers);
65 ir_graph *get_irg_caller(ir_graph *irg, int pos) {
66 assert (pos >= 0 && pos < get_irg_n_callers(irg));
67 if (irg->callers) return irg->callers[pos];
70 int is_irg_caller_backedge(ir_graph *irg, int pos) {
71 assert (pos >= 0 && pos < get_irg_n_callers(irg));
72 return irg->caller_isbe[pos];
75 static void set_irg_caller_backedge(ir_graph *irg, ir_graph *caller) {
76 int i, n_callers = get_irg_n_callers(irg);
77 for (i = 0; i < n_callers; ++i) {
78 if (get_irg_caller(irg, i) == caller) {
79 irg->caller_isbe[i] = 1;
85 int has_irg_caller_backedge(ir_graph *irg) {
86 int i, n_callers = get_irg_n_callers(irg);
87 for (i = 0; i < n_callers; ++i)
88 if (is_irg_caller_backedge(irg, i)) return 1;
92 static int reverse_pos(ir_graph *callee, int pos_caller) {
93 ir_graph *caller = get_irg_caller(callee, pos_caller);
94 /* search the other relation for the corresponding edge. */
96 int i, n_callees = get_irg_n_callees(caller);
97 for (i = 0; i < n_callees; ++i) {
98 if (get_irg_callee(caller, i) == callee) {
104 assert(pos_callee >= 0);
109 int get_irg_caller_loop_depth(ir_graph *irg, int pos) {
110 ir_graph *caller = get_irg_caller(irg, pos);
111 int pos_callee = reverse_pos(irg, pos);
113 return get_irg_callee_loop_depth(caller, pos_callee);
117 /* The functions called by irg. */
118 int get_irg_n_callees(ir_graph *irg) {
119 if (irg->callees) return ARR_LEN(irg->callees);
122 ir_graph *get_irg_callee(ir_graph *irg, int pos) {
123 assert (pos >= 0 && pos < get_irg_n_callees(irg));
124 if (irg->callees) return ((ana_entry *)irg->callees[pos])->irg;
127 int is_irg_callee_backedge(ir_graph *irg, int pos) {
128 assert (pos >= 0 && pos < get_irg_n_callees(irg));
129 return irg->callee_isbe[pos];
131 int has_irg_callee_backedge(ir_graph *irg) {
132 int i, n_callees = get_irg_n_callees(irg);
133 for (i = 0; i < n_callees; ++i)
134 if (is_irg_callee_backedge(irg, i)) return 1;
137 void set_irg_callee_backedge(ir_graph *irg, int pos) {
138 assert (pos >= 0 && pos < get_irg_n_callees(irg));
139 irg->callee_isbe[pos] = 1;
142 int get_irg_callee_loop_depth(ir_graph *irg, int pos) {
143 assert (pos >= 0 && pos < get_irg_n_callees(irg));
144 if (irg->callees) return ((ana_entry *)irg->callees[pos])->max_depth;
150 double get_irg_callee_execution_frequency(ir_graph *irg, int pos) {
151 ir_node **arr = ((ana_entry *)irg->callees[pos])->call_list;
152 int i, n_Calls = ARR_LEN(arr);
155 for (i = 0; i < n_Calls; ++i) {
156 freq += get_irn_exec_freq(arr[i]);
161 double get_irg_callee_method_execution_frequency(ir_graph *irg, int pos) {
162 double call_freq = get_irg_callee_execution_frequency(irg, pos);
163 double meth_freq = get_irg_method_execution_frequency(irg);
164 return call_freq * meth_freq;
168 double get_irg_caller_method_execution_frequency(ir_graph *irg, int pos) {
169 ir_graph *caller = get_irg_caller(irg, pos);
170 int pos_callee = reverse_pos(irg, pos);
172 return get_irg_callee_method_execution_frequency(caller, pos_callee);
177 /* --------------------- Compute the callgraph ------------------------ */
180 * Walker called by compute_callgraph()
182 static void ana_Call(ir_node *n, void *env) {
186 if (! is_Call(n)) return;
188 irg = get_irn_irg(n);
189 n_callees = get_Call_n_callees(n);
190 for (i = 0; i < n_callees; ++i) {
191 entity *callee_e = get_Call_callee(n, i);
192 ir_graph *callee = get_entity_irg(callee_e);
195 ana_entry buf = { NULL, NULL, 0};
201 pset_insert((pset *)callee->callers, irg, HASH_PTR(irg));
202 found = pset_find((pset *)irg->callees, &buf, HASH_PTR(callee));
203 if (found) { /* add Call node to list, compute new nesting. */
204 ir_node **arr = found->call_list;
205 ARR_APP1(ir_node *, arr, n);
206 found->call_list = arr;
207 } else { /* New node, add Call node and init nesting. */
208 found = (ana_entry *) obstack_alloc (irg->obst, sizeof (ana_entry));
210 found->call_list = NEW_ARR_F(ir_node *, 1);
211 found->call_list[0] = n;
212 found->max_depth = 0;
213 pset_insert((pset *)irg->callees, found, HASH_PTR(callee));
215 depth = get_loop_depth(get_irn_loop(get_nodes_block(n)));
216 found->max_depth = (depth > found->max_depth) ? depth : found->max_depth;
221 /** compare two ir graphs in a ana_entry */
222 static int ana_entry_cmp(const void *elt, const void *key) {
223 const ana_entry *e1 = elt;
224 const ana_entry *e2 = key;
225 return e1->irg != e2->irg;
228 /** compare two ir graphs */
229 static int graph_cmp(const void *elt, const void *key) {
234 /* Construct and destruct the callgraph. */
235 void compute_callgraph(void) {
236 int i, n_irgs = get_irp_n_irgs();
238 assert(! get_interprocedural_view()); /* Else walking will not reach the Call nodes. */
242 for (i = 0; i < n_irgs; ++i) {
243 ir_graph *irg = get_irp_irg(i);
244 assert(get_irg_callee_info_state(irg) == irg_callee_info_consistent);
245 irg->callees = (ir_graph **)new_pset(ana_entry_cmp, 8);
246 irg->callers = (ir_graph **)new_pset(graph_cmp, 8);
247 //construct_cf_backedges(irg);
250 /* Compute the call graph */
251 for (i = 0; i < n_irgs; ++i) {
252 ir_graph *irg = get_irp_irg(i);
253 construct_cf_backedges(irg); // We also find the maximal loop depth of a call.
254 irg_walk_graph(irg, ana_Call, NULL, NULL);
257 /* Change the sets to arrays. */
258 for (i = 0; i < n_irgs; ++i) {
260 ir_graph *c, *irg = get_irp_irg(i);
261 pset *callee_set, *caller_set;
263 callee_set = (pset *)irg->callees;
264 count = pset_count(callee_set);
265 irg->callees = NEW_ARR_F(ir_graph *, count);
266 irg->callee_isbe = xcalloc(count, sizeof(irg->callee_isbe[0]));
267 c = pset_first(callee_set);
268 for (j = 0; j < count; ++j) {
270 c = pset_next(callee_set);
272 del_pset(callee_set);
275 caller_set = (pset *)irg->callers;
276 count = pset_count(caller_set);
277 irg->callers = NEW_ARR_F(ir_graph *, count);
278 irg->caller_isbe = xcalloc(count, sizeof(irg->caller_isbe[0]));
279 c = pset_first(caller_set);
280 for (j = 0; j < count; ++j) {
282 c = pset_next(caller_set);
284 del_pset(caller_set);
287 set_irp_callgraph_state(irp_callgraph_consistent);
290 void free_callgraph(void) {
291 int i, n_irgs = get_irp_n_irgs();
292 for (i = 0; i < n_irgs; ++i) {
293 ir_graph *irg = get_irp_irg(i);
294 if (irg->callees) DEL_ARR_F(irg->callees);
295 if (irg->callers) DEL_ARR_F(irg->callers);
296 if (irg->callee_isbe) free(irg->callee_isbe);
297 if (irg->caller_isbe) free(irg->caller_isbe);
300 irg->callee_isbe = NULL;
301 irg->caller_isbe = NULL;
303 set_irp_callgraph_state(irp_callgraph_none);
306 /* ----------------------------------------------------------------------------------- */
307 /* A walker for the callgraph */
308 /* ----------------------------------------------------------------------------------- */
311 static void do_walk(ir_graph *irg, callgraph_walk_func *pre, callgraph_walk_func *post, void *env) {
314 if (cg_irg_visited(irg)) return;
315 mark_cg_irg_visited(irg);
319 n_callees = get_irg_n_callees(irg);
320 for (i = 0; i < n_callees; i++) {
321 ir_graph *m = get_irg_callee(irg, i);
322 do_walk(m, pre, post, env);
328 void callgraph_walk(callgraph_walk_func *pre, callgraph_walk_func *post, void *env) {
329 int i, n_irgs = get_irp_n_irgs();
332 do_walk(get_irp_main_irg(), pre, post, env);
333 for (i = 0; i < n_irgs; i++) {
334 ir_graph *irg = get_irp_irg(i);
335 if (!cg_irg_visited(irg) && get_irg_n_callers(irg) == 0)
336 do_walk(irg, pre, post, env);
338 for (i = 0; i < n_irgs; i++) {
339 ir_graph *irg = get_irp_irg(i);
340 if (!cg_irg_visited(irg))
341 do_walk(irg, pre, post, env);
345 /* ----------------------------------------------------------------------------------- */
346 /* loop construction algorithm */
347 /* ----------------------------------------------------------------------------------- */
349 static ir_graph *outermost_ir_graph; /**< The outermost graph the scc is computed
351 static ir_loop *current_loop; /**< Current cfloop construction is working
353 static int loop_node_cnt = 0; /**< Counts the number of allocated cfloop nodes.
354 Each cfloop node gets a unique number.
355 What for? ev. remove. @@@ */
356 static int current_dfn = 1; /**< Counter to generate depth first numbering
360 /**********************************************************************/
361 /* Node attributes **/
362 /**********************************************************************/
364 typedef struct scc_info {
365 int in_stack; /**< Marks whether node is on the stack. */
366 int dfn; /**< Depth first search number. */
367 int uplink; /**< dfn number of ancestor. */
372 * allocates a new scc_info of the obstack
374 static INLINE scc_info *new_scc_info(void) {
375 scc_info *info = obstack_alloc (outermost_ir_graph->obst, sizeof(*info));
376 memset(info, 0, sizeof(*info));
381 cg_irg_visited(ir_graph *n) {
382 scc_info *info = get_irg_link(n);
383 return (info->visited >= master_cg_visited);
387 mark_cg_irg_visited(ir_graph *n) {
388 scc_info *info = get_irg_link(n);
389 info->visited = master_cg_visited;
393 set_cg_irg_visited(ir_graph *n, int i) {
394 scc_info *info = get_irg_link(n);
399 get_cg_irg_visited(ir_graph *n) {
400 scc_info *info = get_irg_link(n);
401 return info->visited;
405 mark_irg_in_stack (ir_graph *n) {
406 scc_info *info = get_irg_link(n);
412 mark_irg_not_in_stack (ir_graph *n) {
413 scc_info *info = get_irg_link(n);
419 irg_is_in_stack (ir_graph *n) {
420 scc_info *info = get_irg_link(n);
422 return info->in_stack;
426 set_irg_uplink (ir_graph *n, int uplink) {
427 scc_info *info = get_irg_link(n);
429 info->uplink = uplink;
433 get_irg_uplink (ir_graph *n) {
434 scc_info *info = get_irg_link(n);
440 set_irg_dfn (ir_graph *n, int dfn) {
441 scc_info *info = get_irg_link(n);
447 get_irg_dfn (ir_graph *n) {
448 scc_info *info = get_irg_link(n);
453 /**********************************************************************/
455 /**********************************************************************/
457 static ir_graph **stack = NULL;
458 static int tos = 0; /**< top of stack */
461 * initialize the irg stack
463 static INLINE void init_stack(void) {
465 ARR_RESIZE (ir_graph *, stack, 1000);
467 stack = NEW_ARR_F (ir_graph *, 1000);
473 * push a graph on the irg stack
474 * @param n the graph to be pushed
479 if (tos == ARR_LEN (stack)) {
480 int nlen = ARR_LEN (stack) * 2;
481 ARR_RESIZE (ir_node *, stack, nlen);
484 mark_irg_in_stack(n);
488 * return the topmost graph on the stack and pop it
490 static INLINE ir_graph *
493 ir_graph *n = stack[--tos];
494 mark_irg_not_in_stack(n);
499 * The nodes up to n belong to the current loop.
500 * Removes them from the stack and adds them to the current loop.
503 pop_scc_to_loop (ir_graph *n)
510 set_irg_dfn(m, loop_node_cnt);
511 add_loop_node(current_loop, (ir_node *)m);
513 //m->callgraph_loop_depth = current_loop->depth;
517 /* GL ??? my last son is my grandson??? Removes cfloops with no
518 ir_nodes in them. Such loops have only another loop as son. (Why
519 can't they have two loops as sons? Does it never get that far? ) */
520 static void close_loop (ir_loop *l)
522 int last = get_loop_n_elements(l) - 1;
523 loop_element lelement = get_loop_element(l, last);
524 ir_loop *last_son = lelement.son;
526 if (get_kind(last_son) == k_ir_loop &&
527 get_loop_n_elements(last_son) == 1) {
530 lelement = get_loop_element(last_son, 0);
532 if(get_kind(gson) == k_ir_loop) {
533 loop_element new_last_son;
535 gson -> outer_loop = l;
536 new_last_son.son = gson;
537 l -> children[last] = new_last_son;
545 * Removes and unmarks all nodes up to n from the stack.
546 * The nodes must be visited once more to assign them to a scc.
549 pop_scc_unmark_visit (ir_graph *n)
555 set_cg_irg_visited(m, 0);
559 /**********************************************************************/
560 /* The loop data structure. **/
561 /**********************************************************************/
564 * Allocates a new loop as son of current_loop. Sets current_loop
565 * to the new loop and returns the father.
567 static ir_loop *new_loop (void) {
568 ir_loop *father, *son;
570 father = current_loop;
572 son = obstack_alloc (outermost_ir_graph->obst, sizeof(*son));
573 memset (son, 0, sizeof(*son));
574 son->kind = k_ir_loop;
575 son->children = NEW_ARR_F (loop_element, 0);
579 son->outer_loop = father;
580 add_loop_son(father, son);
581 son->depth = father->depth + 1;
582 } else { /* The root loop */
583 son->outer_loop = son;
588 son->loop_nr = get_irp_new_node_nr();
596 /**********************************************************************/
597 /* Constructing and destructing the loop/backedge information. **/
598 /**********************************************************************/
600 /* Initialization steps. **********************************************/
611 n_irgs = get_irp_n_irgs();
612 for (i = 0; i < n_irgs; ++i) {
613 ir_graph *irg = get_irp_irg(i);
614 set_irg_link(irg, new_scc_info());
615 irg->callgraph_recursion_depth = 0;
616 irg->callgraph_loop_depth = 0;
620 /** Returns non-zero if n is a loop header, i.e., it is a Block node
621 * and has predecessors within the cfloop and out of the cfloop.
623 * @param root: only needed for assertion.
626 is_head (ir_graph *n, ir_graph *root)
629 int some_outof_loop = 0, some_in_loop = 0;
631 arity = get_irg_n_callees(n);
632 for (i = 0; i < arity; i++) {
633 ir_graph *pred = get_irg_callee(n, i);
634 if (is_irg_callee_backedge(n, i)) continue;
635 if (!irg_is_in_stack(pred)) {
638 if (get_irg_uplink(pred) < get_irg_uplink(root)) {
639 DDMG(pred); DDMG(root);
640 assert(get_irg_uplink(pred) >= get_irg_uplink(root));
646 return some_outof_loop & some_in_loop;
650 * Returns non-zero if n is possible loop head of an endless loop.
651 * I.e., it is a Block, Phi or Filter node and has only predecessors
653 * @arg root: only needed for assertion.
656 is_endless_head (ir_graph *n, ir_graph *root)
659 int some_outof_loop = 0, some_in_loop = 0;
661 arity = get_irg_n_callees(n);
662 for (i = 0; i < arity; i++) {
663 ir_graph *pred = get_irg_callee(n, i);
665 if (is_irg_callee_backedge(n, i)) { continue; }
666 if (!irg_is_in_stack(pred)) {
669 if(get_irg_uplink(pred) < get_irg_uplink(root)) {
670 DDMG(pred); DDMG(root);
671 assert(get_irg_uplink(pred) >= get_irg_uplink(root));
677 return !some_outof_loop & some_in_loop;
682 * Check whether there is a parallel edge in the ip control flow.
686 is_ip_head (ir_graph *n, ir_graph *pred)
689 int iv_rem = get_interprocedural_view();
690 set_interprocedural_view(1);
692 ir_node *sblock = get_irg_start_block(n);
693 int i, arity = get_Block_n_cfgpreds(sblock);
695 //printf(" edge from "); DDMG(n);
696 //printf(" to pred "); DDMG(pred);
697 //printf(" sblock "); DDMN(sblock);
699 for (i = 0; i < arity; i++) {
700 ir_node *pred_cfop = skip_Proj(get_Block_cfgpred(sblock, i));
701 //printf(" "); DDMN(pred_cfop);
702 if (get_irn_op(pred_cfop) == op_CallBegin) { /* could be Unknown */
703 ir_graph *ip_pred = get_irn_irg(pred_cfop);
704 //printf(" "); DDMG(ip_pred);
705 if ((ip_pred == pred) && is_backedge(sblock, i)) {
706 //printf(" found\n");
712 set_interprocedural_view(iv_rem);
717 * Returns index of the predecessor with the smallest dfn number
718 * greater-equal than limit.
721 smallest_dfn_pred (ir_graph *n, int limit)
723 int i, index = -2, min = -1;
725 int arity = get_irg_n_callees(n);
726 for (i = 0; i < arity; i++) {
727 ir_graph *pred = get_irg_callee(n, i);
728 if (is_irg_callee_backedge(n, i) || !irg_is_in_stack(pred)) continue;
729 if (get_irg_dfn(pred) >= limit && (min == -1 || get_irg_dfn(pred) < min)) {
731 min = get_irg_dfn(pred);
738 /** Returns index of the predecessor with the largest dfn number. */
740 largest_dfn_pred (ir_graph *n)
742 int i, index = -2, max = -1;
744 int arity = get_irg_n_callees(n);
745 for (i = 0; i < arity; i++) {
746 ir_graph *pred = get_irg_callee(n, i);
747 if (is_irg_callee_backedge (n, i) || !irg_is_in_stack(pred)) continue;
748 if (get_irg_dfn(pred) > max) {
750 max = get_irg_dfn(pred);
759 find_tail (ir_graph *n) {
761 int i, res_index = -2;
764 if (!icfg && rm_cyclic_phis && remove_cyclic_phis (n)) return NULL;
766 m = stack[tos-1]; /* tos = top of stack */
767 if (is_head (m, n)) {
768 res_index = smallest_dfn_pred(m, 0);
769 if ((res_index == -2) && /* no smallest dfn pred found. */
773 if (m == n) return NULL; // Is this to catch Phi - self loops?
774 for (i = tos-2; i >= 0; --i) {
777 if (is_head (m, n)) {
778 res_index = smallest_dfn_pred (m, get_irg_dfn(m) + 1);
779 if (res_index == -2) /* no smallest dfn pred found. */
780 res_index = largest_dfn_pred (m);
782 if ((m == n) && (res_index == -2)) {
788 /* We should not walk past our selves on the stack: The upcoming nodes
789 are not in this loop. We assume a loop not reachable from Start. */
798 /* A dead loop not reachable from Start. */
799 for (i = tos-2; i >= 0; --i) {
801 if (is_endless_head (m, n)) {
802 res_index = smallest_dfn_pred (m, get_irg_dfn(m) + 1);
803 if (res_index == -2) /* no smallest dfn pred found. */
804 res_index = largest_dfn_pred (m);
807 if (m == n) { break; } /* It's not an unreachable loop, either. */
809 //assert(0 && "no head found on stack");
813 assert (res_index > -2);
815 set_irg_callee_backedge (m, res_index);
816 return get_irg_callee(m, res_index);
820 find_tail (ir_graph *n) {
822 int i, res_index = -2;
825 ir_graph *in_and_out = NULL;
826 ir_graph *only_in = NULL;
827 ir_graph *ip_in_and_out = NULL;
828 ir_graph *ip_only_in = NULL;
830 //printf("find tail for "); DDMG(n);
832 for (i = tos-1; i >= 0; --i) {
833 ir_graph *pred = (i < tos -1) ? stack[i+1] : n;
836 if (is_head (m, n)) {
837 //printf(" found 1a! "); DDM;
839 if (is_ip_head(pred, m)) {
840 //printf(" found 1b! "); DDM;
843 } else if (!ip_only_in && is_endless_head(m, n)) {
845 //printf(" found 2a! "); DDM;
846 if (is_ip_head(pred, m)) {
847 //printf(" found 2b! "); DDM;
850 } else if (is_ip_head(pred, m)) {
851 //printf(" found 3! "); DDM; This happens for self recursions in the second
852 //assert(0); scc iteration (the one to flip the loop.)
855 if (ip_in_and_out) break; /* That's what we really want. */
857 if (m == n) break; /* Don't walk past n on the stack! */
861 if (!in_and_out && !only_in)
862 /* There is no loop */
866 /* Is there a head in the callgraph without a head in the
868 assert(in_and_out || only_in);
870 m = (ip_in_and_out) ? ip_in_and_out : ip_only_in;
873 m = (in_and_out) ? in_and_out : only_in;
875 //printf("*** head is "); DDMG(m);
877 res_index = smallest_dfn_pred (m, get_irg_dfn(m) + 1);
878 if (res_index == -2) /* no smallest dfn pred found. */
879 res_index = largest_dfn_pred (m);
881 set_irg_callee_backedge (m, res_index);
882 res = get_irg_callee(m, res_index);
883 //printf("*** tail is "); DDMG(res);
889 /*-----------------------------------------------------------*
890 * The core algorithm. *
891 *-----------------------------------------------------------*/
894 static void cgscc (ir_graph *n) {
897 if (cg_irg_visited(n)) return;
898 mark_cg_irg_visited(n);
900 /* Initialize the node */
901 set_irg_dfn(n, current_dfn); /* Depth first number for this node */
902 set_irg_uplink(n, current_dfn); /* ... is default uplink. */
906 arity = get_irg_n_callees(n);
907 for (i = 0; i < arity; i++) {
909 if (is_irg_callee_backedge(n, i)) continue;
910 m = get_irg_callee(n, i);
912 /** This marks the backedge, but does it guarantee a correct loop tree? */
913 //if (m == n) { set_irg_callee_backedge(n, i); continue; }
916 if (irg_is_in_stack(m)) {
917 /* Uplink of m is smaller if n->m is a backedge.
918 Propagate the uplink to mark the cfloop. */
919 if (get_irg_uplink(m) < get_irg_uplink(n))
920 set_irg_uplink(n, get_irg_uplink(m));
924 if (get_irg_dfn(n) == get_irg_uplink(n)) {
925 /* This condition holds for
926 1) the node with the incoming backedge.
927 That is: We found a cfloop!
928 2) Straight line code, because no uplink has been propagated, so the
929 uplink still is the same as the dfn.
931 But n might not be a proper cfloop head for the analysis. Proper cfloop
932 heads are Block and Phi nodes. find_tail searches the stack for
933 Block's and Phi's and takes those nodes as cfloop heads for the current
934 cfloop instead and marks the incoming edge as backedge. */
936 ir_graph *tail = find_tail(n);
938 /* We have a cfloop, that is no straight line code,
939 because we found a cfloop head!
940 Next actions: Open a new cfloop on the cfloop tree and
941 try to find inner cfloops */
944 ir_loop *l = new_loop();
946 /* Remove the cfloop from the stack ... */
947 pop_scc_unmark_visit (n);
949 /* The current backedge has been marked, that is temporarily eliminated,
950 by find tail. Start the scc algorithm
951 anew on the subgraph thats left (the current cfloop without the backedge)
952 in order to find more inner cfloops. */
956 assert (cg_irg_visited(n));
966 * reset the backedge information for all callers in all irgs
968 static void reset_isbe(void) {
969 int i, n_irgs = get_irp_n_irgs();
971 for (i = 0; i < n_irgs; ++i) {
973 ir_graph *irg = get_irp_irg(i);
975 n_cs = get_irg_n_callers(irg);
976 for (j = 0; j < n_cs; ++j) {
977 irg->caller_isbe[j] = 0;
980 n_cs = get_irg_n_callees(irg);
981 for (j = 0; j < n_cs; ++j) {
982 irg->callee_isbe[j] = 0;
990 /* ----------------------------------------------------------------------------------- */
991 /* Another algorithm to compute recursion nesting depth */
992 /* Walk the callgraph. For each crossed edge increase the loop depth by the edge */
993 /* weight. Assign graphs the maximal depth. */
994 /* ----------------------------------------------------------------------------------- */
996 static void compute_loop_depth (ir_graph *irg, void *env) {
997 int current_nesting = *(int *) env;
998 int old_nesting = irg->callgraph_loop_depth;
999 int old_visited = get_cg_irg_visited(irg);
1004 if (cg_irg_visited(irg)) return;
1006 mark_cg_irg_visited(irg);
1008 //printf(" old: %d new %d master %d", old_visited, get_cg_irg_visited(irg), master_cg_visited); DDMG(irg);
1011 if (old_nesting < current_nesting)
1012 irg->callgraph_loop_depth = current_nesting;
1014 if (current_nesting > irp->max_callgraph_loop_depth)
1015 irp->max_callgraph_loop_depth = current_nesting;
1017 if ((old_visited +1 < get_cg_irg_visited(irg)) || /* not yet visited */
1018 (old_nesting < current_nesting)) { /* propagate larger nesting */
1019 /* Don't walk the graph, but a tree that is an unfolded graph. */
1020 n_callees = get_irg_n_callees(irg);
1021 for (i = 0; i < n_callees; i++) {
1022 ir_graph *m = get_irg_callee(irg, i);
1023 *(int *)env += get_irg_callee_loop_depth(irg, i);
1024 compute_loop_depth(m, env);
1025 *(int *)env -= get_irg_callee_loop_depth(irg, i);
1029 set_cg_irg_visited(irg, master_cg_visited-1);
1032 /* ------------------------------------------------------------------------------------ */
1033 /* Another algorithm to compute recursion nesting depth */
1034 /* Walk the callgraph. For each crossed loop increase the nesting depth by one. */
1035 /* Assign graphs the maximal nesting depth. Don't increase if passing loops more than */
1037 /* ------------------------------------------------------------------------------------ */
1040 /* For callees, we want to remember the Call nodes, too. */
1041 typedef struct ana_entry2 {
1042 ir_loop **loop_stack; /**< a stack of ir_loop entries */
1043 int tos; /**< the top of stack entry */
1044 int recursion_nesting;
1048 * push a loop entry on the stack
1050 static void push2(ana_entry2 *e, ir_loop *g) {
1051 if (ARR_LEN(e->loop_stack) == e->tos) {
1052 ARR_APP1(ir_loop *, e->loop_stack, g);
1054 e->loop_stack[e->tos] = g;
1060 * returns the top of stack and pop it
1062 static ir_loop *pop2(ana_entry2 *e) {
1063 return e->loop_stack[--e->tos];
1067 * check if a loop g in on the stack. Did not check the TOS.
1069 static int in_stack(ana_entry2 *e, ir_loop *g) {
1071 for (i = e->tos-1; i >= 0; --i) {
1072 if (e->loop_stack[i] == g) return 1;
1077 static void compute_rec_depth (ir_graph *irg, void *env) {
1078 ana_entry2 *e = (ana_entry2 *)env;
1079 ir_loop *l = irg->l;
1080 int depth, old_depth = irg->callgraph_recursion_depth;
1084 if (cg_irg_visited(irg)) return;
1085 mark_cg_irg_visited(irg);
1087 /* -- compute and set the new nesting value -- */
1088 if ((l != irp->outermost_cg_loop) && !in_stack(e, l)) {
1090 e->recursion_nesting++;
1093 depth = e->recursion_nesting;
1095 if (old_depth < depth)
1096 irg->callgraph_recursion_depth = depth;
1098 if (depth > irp->max_callgraph_recursion_depth)
1099 irp->max_callgraph_recursion_depth = depth;
1101 /* -- spread the nesting value -- */
1102 if (depth == 0 || old_depth < depth) {
1103 /* Don't walk the graph, but a tree that is an unfolded graph.
1104 Therefore we unset the visited flag at the end. */
1105 n_callees = get_irg_n_callees(irg);
1106 for (i = 0; i < n_callees; i++) {
1107 ir_graph *m = get_irg_callee(irg, i);
1108 compute_rec_depth(m, env);
1112 /* -- clean up -- */
1115 e->recursion_nesting--;
1117 set_cg_irg_visited(irg, master_cg_visited-1);
1121 /* ----------------------------------------------------------------------------------- */
1122 /* Another algorithm to compute the execution frequency of methods ignoring recursions. */
1123 /* Walk the callgraph. Ignore backedges. Use sum of execution frequencies of Call */
1124 /* nodes to evaluate a callgraph edge. */
1125 /* ----------------------------------------------------------------------------------- */
1127 double get_irg_method_execution_frequency (ir_graph *irg) {
1128 return irg->method_execution_frequency;
1131 void set_irg_method_execution_frequency (ir_graph *irg, double freq) {
1132 irg->method_execution_frequency = freq;
1134 if (irp->max_method_execution_frequency < freq)
1135 irp->max_method_execution_frequency = freq;
1138 static void compute_method_execution_frequency (ir_graph *irg, void *env) {
1144 if (cg_irg_visited(irg)) return;
1146 /* We need the values of all predecessors (except backedges).
1147 So they must be marked. Else we will reach the node through
1148 one of the unmarked ones. */
1149 n_callers = get_irg_n_callers(irg);
1150 for (i = 0; i < n_callers; i++) {
1151 ir_graph *m = get_irg_caller(irg, i);
1152 if (is_irg_caller_backedge(irg, i)) continue;
1153 if (!cg_irg_visited(m)) {
1157 mark_cg_irg_visited(irg);
1159 /* Compute the new frequency. */
1162 for (i = 0; i < n_callers; i++) {
1163 if (! is_irg_caller_backedge(irg, i)) {
1164 double edge_freq = get_irg_caller_method_execution_frequency(irg, i);
1165 assert(edge_freq >= 0);
1172 /* A starting point: method only called from outside,
1173 or only backedges as predecessors. */
1177 set_irg_method_execution_frequency(irg, freq);
1180 n_callees = get_irg_n_callees(irg);
1181 for (i = 0; i < n_callees; i++) {
1182 compute_method_execution_frequency (get_irg_callee(irg, i), NULL);
1187 /* ----------------------------------------------------------------------------------- */
1188 /* The recursion stuff driver. */
1189 /* ----------------------------------------------------------------------------------- */
1191 /* Compute the backedges that represent recursions. */
1192 void find_callgraph_recursions(void) {
1193 int i, n_irgs = get_irp_n_irgs();
1197 /* -- compute the looptree. -- */
1199 /* The outermost graph. We start here. Then we start at all
1200 functions in irg list that are never called, then at the remaining
1201 unvisited ones. The third step is needed for functions that are not
1202 reachable from the outermost graph, but call themselves in a cycle. */
1203 assert(get_irp_main_irg());
1204 outermost_ir_graph = get_irp_main_irg();
1207 current_loop = NULL;
1208 new_loop(); /* sets current_loop */
1210 master_cg_visited++;
1211 cgscc(outermost_ir_graph);
1212 for (i = 0; i < n_irgs; i++) {
1213 ir_graph *irg = get_irp_irg(i);
1214 if (!cg_irg_visited(irg) && get_irg_n_callers(irg) == 0)
1217 for (i = 0; i < n_irgs; i++) {
1218 ir_graph *irg = get_irp_irg(i);
1219 if (!cg_irg_visited(irg))
1222 irp->outermost_cg_loop = current_loop;
1224 /* -- Reverse the backedge information. -- */
1225 for (i = 0; i < n_irgs; i++) {
1226 ir_graph *irg = get_irp_irg(i);
1227 int j, n_callees = get_irg_n_callees(irg);
1228 for (j = 0; j < n_callees; ++j) {
1229 if (is_irg_callee_backedge(irg, j))
1230 set_irg_caller_backedge(get_irg_callee(irg, j), irg);
1234 irp->callgraph_state = irp_callgraph_and_calltree_consistent;
1237 void compute_performance_estimates(void) {
1238 int i, n_irgs = get_irp_n_irgs();
1239 int current_nesting;
1242 /* -- compute the loop depth -- */
1243 current_nesting = 0;
1244 irp->max_callgraph_loop_depth = 0;
1245 master_cg_visited += 2;
1246 //printf (" ** starting at "); DDMG(get_irp_main_irg());
1247 compute_loop_depth(get_irp_main_irg(), ¤t_nesting);
1248 for (i = 0; i < n_irgs; i++) {
1249 ir_graph *irg = get_irp_irg(i);
1250 if ((get_cg_irg_visited(irg) < master_cg_visited-1) &&
1251 get_irg_n_callers(irg) == 0) {
1252 compute_loop_depth(irg, ¤t_nesting);
1253 //printf (" ** starting at "); DDMG(irg);
1256 for (i = 0; i < n_irgs; i++) {
1257 ir_graph *irg = get_irp_irg(i);
1258 if (get_cg_irg_visited(irg) < master_cg_visited-1) {
1259 compute_loop_depth(irg, ¤t_nesting);
1260 //printf (" ** starting at "); DDMG(irg);
1265 /* -- compute the recursion depth -- */
1266 e.loop_stack = NEW_ARR_F(ir_loop *, 0);
1268 e.recursion_nesting = 0;
1270 irp->max_callgraph_recursion_depth = 0;
1272 master_cg_visited += 2;
1273 compute_rec_depth(get_irp_main_irg(), &e);
1274 //printf (" ++ starting at "); DDMG(get_irp_main_irg());
1275 for (i = 0; i < n_irgs; i++) {
1276 ir_graph *irg = get_irp_irg(i);
1277 if ((get_cg_irg_visited(irg) < master_cg_visited-1) &&
1278 get_irg_n_callers(irg) == 0) {
1279 compute_rec_depth(irg, &e);
1280 //printf (" ++ starting at "); DDMG(irg);
1283 for (i = 0; i < n_irgs; i++) {
1284 ir_graph *irg = get_irp_irg(i);
1285 if (get_cg_irg_visited(irg) < master_cg_visited-1) {
1286 compute_rec_depth(irg, &e);
1287 //printf (" ++ starting at "); DDMG(irg);
1291 DEL_ARR_F(e.loop_stack);
1293 /* -- compute the execution frequency -- */
1294 irp->max_method_execution_frequency = 0;
1295 master_cg_visited += 2;
1296 assert(get_irg_n_callers(get_irp_main_irg()) == 0);
1297 compute_method_execution_frequency(get_irp_main_irg(), NULL);
1298 for (i = 0; i < n_irgs; i++) {
1299 ir_graph *irg = get_irp_irg(i);
1300 if ((get_cg_irg_visited(irg) < master_cg_visited-1) &&
1301 get_irg_n_callers(irg) == 0) {
1302 compute_method_execution_frequency(irg, NULL);
1305 for (i = 0; i < n_irgs; i++) {
1306 ir_graph *irg = get_irp_irg(i);
1307 if (get_cg_irg_visited(irg) < master_cg_visited-1) {
1308 compute_method_execution_frequency(irg, NULL);
1313 /* Maximal loop depth of all paths from an external visible method to
1315 int get_irg_loop_depth(ir_graph *irg) {
1316 assert(irp->callgraph_state == irp_callgraph_consistent ||
1317 irp->callgraph_state == irp_callgraph_and_calltree_consistent);
1318 return irg->callgraph_loop_depth;
1321 /* Maximal recursion depth of all paths from an external visible method to
1323 int get_irg_recursion_depth(ir_graph *irg) {
1324 assert(irp->callgraph_state == irp_callgraph_and_calltree_consistent);
1325 return irg->callgraph_recursion_depth;
1328 void analyse_loop_nesting_depth(void) {
1329 entity **free_methods = NULL;
1332 /* establish preconditions. */
1333 if (get_irp_callee_info_state() != irg_callee_info_consistent) {
1334 cgana(&arr_len, &free_methods);
1337 if (irp_callgraph_consistent != get_irp_callgraph_state()) {
1338 compute_callgraph();
1341 find_callgraph_recursions();
1343 compute_performance_estimates();
1345 set_irp_loop_nesting_depth_state(loop_nesting_depth_consistent);
1349 loop_nesting_depth_state get_irp_loop_nesting_depth_state(void) {
1350 return irp->lnd_state;
1352 void set_irp_loop_nesting_depth_state(loop_nesting_depth_state s) {
1355 void set_irp_loop_nesting_depth_state_inconsistent(void) {
1356 if (irp->lnd_state == loop_nesting_depth_consistent)
1357 irp->lnd_state = loop_nesting_depth_inconsistent;