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"
30 #include "execution_frequency.h"
38 /* For callees, we want to remember the Call nodes, too. */
45 typedef struct ana_entry ana_entry;
47 static int master_cg_visited = 0;
48 static INLINE int cg_irg_visited (ir_graph *n);
49 static INLINE void mark_cg_irg_visited(ir_graph *n);
50 static INLINE void set_cg_irg_visited (ir_graph *n, int i);
52 irp_callgraph_state get_irp_callgraph_state(void) {
53 return irp->callgraph_state;
55 void set_irp_callgraph_state(irp_callgraph_state s) {
56 irp->callgraph_state = s;
59 /* The functions that call irg. */
60 int get_irg_n_callers(ir_graph *irg) {
61 if (irg->callers) return ARR_LEN(irg->callers);
64 ir_graph *get_irg_caller(ir_graph *irg, int pos) {
65 assert (pos >= 0 && pos < get_irg_n_callers(irg));
66 if (irg->callers) return irg->callers[pos];
69 int is_irg_caller_backedge(ir_graph *irg, int pos) {
70 assert (pos >= 0 && pos < get_irg_n_callers(irg));
71 return irg->caller_isbe[pos];
74 static void set_irg_caller_backedge(ir_graph *irg, ir_graph *caller) {
75 int i, n_callers = get_irg_n_callers(irg);
76 for (i = 0; i < n_callers; ++i) {
77 if (get_irg_caller(irg, i) == caller) {
78 irg->caller_isbe[i] = 1;
84 int has_irg_caller_backedge(ir_graph *irg) {
85 int i, n_callers = get_irg_n_callers(irg);
86 for (i = 0; i < n_callers; ++i)
87 if (is_irg_caller_backedge(irg, i)) return 1;
91 static int reverse_pos(ir_graph *callee, int pos_caller) {
92 ir_graph *caller = get_irg_caller(callee, pos_caller);
93 /* search the other relation for the corresponding edge. */
95 int i, n_callees = get_irg_n_callees(caller);
96 for (i = 0; i < n_callees; ++i) {
97 if (get_irg_callee(caller, i) == callee) {
103 assert(pos_callee >= 0);
108 int get_irg_caller_loop_depth(ir_graph *irg, int pos) {
109 ir_graph *caller = get_irg_caller(irg, pos);
110 int pos_callee = reverse_pos(irg, pos);
112 return get_irg_callee_loop_depth(caller, pos_callee);
116 /* The functions called by irg. */
117 int get_irg_n_callees(ir_graph *irg) {
118 if (irg->callees) return ARR_LEN(irg->callees);
121 ir_graph *get_irg_callee(ir_graph *irg, int pos) {
122 assert (pos >= 0 && pos < get_irg_n_callees(irg));
123 if (irg->callees) return ((ana_entry *)irg->callees[pos])->irg;
126 int is_irg_callee_backedge(ir_graph *irg, int pos) {
127 assert (pos >= 0 && pos < get_irg_n_callees(irg));
128 return irg->callee_isbe[pos];
130 int has_irg_callee_backedge(ir_graph *irg) {
131 int i, n_callees = get_irg_n_callees(irg);
132 for (i = 0; i < n_callees; ++i)
133 if (is_irg_callee_backedge(irg, i)) return 1;
136 void set_irg_callee_backedge(ir_graph *irg, int pos) {
137 assert (pos >= 0 && pos < get_irg_n_callees(irg));
138 irg->callee_isbe[pos] = 1;
141 int get_irg_callee_loop_depth(ir_graph *irg, int pos) {
142 assert (pos >= 0 && pos < get_irg_n_callees(irg));
143 if (irg->callees) return ((ana_entry *)irg->callees[pos])->max_depth;
149 double get_irg_callee_execution_frequency(ir_graph *irg, int pos) {
150 ir_node **arr = ((ana_entry *)irg->callees[pos])->call_list;
151 int i, n_Calls = ARR_LEN(arr);
154 for (i = 0; i < n_Calls; ++i) {
155 freq += get_irn_exec_freq(arr[i]);
160 double get_irg_callee_method_execution_frequency(ir_graph *irg, int pos) {
161 double call_freq = get_irg_callee_execution_frequency(irg, pos);
162 double meth_freq = get_irg_method_execution_frequency(irg);
163 return call_freq * meth_freq;
167 double get_irg_caller_method_execution_frequency(ir_graph *irg, int pos) {
168 ir_graph *caller = get_irg_caller(irg, pos);
169 int pos_callee = reverse_pos(irg, pos);
171 return get_irg_callee_method_execution_frequency(caller, pos_callee);
176 /* --------------------- Compute the callgraph ------------------------ */
179 * Walker called by compute_callgraph()
181 static void ana_Call(ir_node *n, void *env) {
185 if (get_irn_op(n) != op_Call) return;
187 irg = get_irn_irg(n);
188 n_callees = get_Call_n_callees(n);
189 for (i = 0; i < n_callees; ++i) {
190 entity *callee_e = get_Call_callee(n, i);
191 ir_graph *callee = get_entity_irg(callee_e);
194 ana_entry buf = { callee, NULL, 0};
198 pset_insert((pset *)callee->callers, irg, HASH_PTR(irg));
199 found = pset_find((pset *)irg->callees, &buf, HASH_PTR(callee));
200 if (found) { /* add Call node to list, compute new nesting. */
201 ir_node **arr = found->call_list;
202 ARR_APP1(ir_node *, arr, n);
203 found->call_list = arr;
204 } else { /* New node, add Call node and init nesting. */
205 found = (ana_entry *) obstack_alloc (irg->obst, sizeof (ana_entry));
207 found->call_list = NEW_ARR_F(ir_node *, 1);
208 found->call_list[0] = n;
209 found->max_depth = 0;
210 pset_insert((pset *)irg->callees, found, HASH_PTR(callee));
212 depth = get_loop_depth(get_irn_loop(get_nodes_block(n)));
213 found->max_depth = (depth > found->max_depth) ? depth : found->max_depth;
218 /** compare two ir graphs in a ana_entry */
219 static int ana_entry_cmp(const void *elt, const void *key) {
220 const ana_entry *e1 = elt;
221 const ana_entry *e2 = key;
222 return e1->irg != e2->irg;
225 /** compare two ir graphs */
226 static int graph_cmp(const void *elt, const void *key) {
231 /* Construct and destruct the callgraph. */
232 void compute_callgraph(void) {
233 int i, n_irgs = get_irp_n_irgs();
235 assert(! get_interprocedural_view()); /* Else walking will not reach the Call nodes. */
239 for (i = 0; i < n_irgs; ++i) {
240 ir_graph *irg = get_irp_irg(i);
241 assert(get_irg_callee_info_state(irg) == irg_callee_info_consistent);
242 irg->callees = (ir_graph **)new_pset(ana_entry_cmp, 8);
243 irg->callers = (ir_graph **)new_pset(graph_cmp, 8);
244 //construct_cf_backedges(irg);
247 /* Compute the call graph */
248 for (i = 0; i < n_irgs; ++i) {
249 ir_graph *irg = get_irp_irg(i);
250 construct_cf_backedges(irg); // We also find the maximal loop depth of a call.
251 irg_walk_graph(irg, ana_Call, NULL, NULL);
254 /* Change the sets to arrays. */
255 for (i = 0; i < n_irgs; ++i) {
257 ir_graph *c, *irg = get_irp_irg(i);
258 pset *callee_set, *caller_set;
260 callee_set = (pset *)irg->callees;
261 count = pset_count(callee_set);
262 irg->callees = NEW_ARR_F(ir_graph *, count);
263 irg->callee_isbe = xcalloc(count, sizeof(irg->callee_isbe[0]));
264 c = pset_first(callee_set);
265 for (j = 0; j < count; ++j) {
267 c = pset_next(callee_set);
269 del_pset(callee_set);
272 caller_set = (pset *)irg->callers;
273 count = pset_count(caller_set);
274 irg->callers = NEW_ARR_F(ir_graph *, count);
275 irg->caller_isbe = xcalloc(count, sizeof(irg->caller_isbe[0]));
276 c = pset_first(caller_set);
277 for (j = 0; j < count; ++j) {
279 c = pset_next(caller_set);
281 del_pset(caller_set);
284 set_irp_callgraph_state(irp_callgraph_consistent);
287 void free_callgraph(void) {
288 int i, n_irgs = get_irp_n_irgs();
289 for (i = 0; i < n_irgs; ++i) {
290 ir_graph *irg = get_irp_irg(i);
291 if (irg->callees) DEL_ARR_F(irg->callees);
292 if (irg->callers) DEL_ARR_F(irg->callers);
293 if (irg->callee_isbe) free(irg->callee_isbe);
294 if (irg->caller_isbe) free(irg->caller_isbe);
297 irg->callee_isbe = NULL;
298 irg->caller_isbe = NULL;
300 set_irp_callgraph_state(irp_callgraph_none);
303 /* ----------------------------------------------------------------------------------- */
304 /* A walker for the callgraph */
305 /* ----------------------------------------------------------------------------------- */
308 static void do_walk(ir_graph *irg, callgraph_walk_func *pre, callgraph_walk_func *post, void *env) {
311 if (cg_irg_visited(irg)) return;
312 mark_cg_irg_visited(irg);
316 n_callees = get_irg_n_callees(irg);
317 for (i = 0; i < n_callees; i++) {
318 ir_graph *m = get_irg_callee(irg, i);
319 do_walk(m, pre, post, env);
325 void callgraph_walk(callgraph_walk_func *pre, callgraph_walk_func *post, void *env) {
326 int i, n_irgs = get_irp_n_irgs();
329 do_walk(get_irp_main_irg(), pre, post, env);
330 for (i = 0; i < n_irgs; i++) {
331 ir_graph *irg = get_irp_irg(i);
332 if (!cg_irg_visited(irg) && get_irg_n_callers(irg) == 0)
333 do_walk(irg, pre, post, env);
335 for (i = 0; i < n_irgs; i++) {
336 ir_graph *irg = get_irp_irg(i);
337 if (!cg_irg_visited(irg))
338 do_walk(irg, pre, post, env);
342 /* ----------------------------------------------------------------------------------- */
343 /* loop construction algorithm */
344 /* ----------------------------------------------------------------------------------- */
346 static ir_graph *outermost_ir_graph; /**< The outermost graph the scc is computed
348 static ir_loop *current_loop; /**< Current cfloop construction is working
350 static int loop_node_cnt = 0; /**< Counts the number of allocated cfloop nodes.
351 Each cfloop node gets a unique number.
352 What for? ev. remove. @@@ */
353 static int current_dfn = 1; /**< Counter to generate depth first numbering
357 /**********************************************************************/
358 /* Node attributes **/
359 /**********************************************************************/
361 typedef struct scc_info {
362 bool in_stack; /**< Marks whether node is on the stack. */
363 int dfn; /**< Depth first search number. */
364 int uplink; /**< dfn number of ancestor. */
369 * allocates a new scc_info of the obstack
371 static INLINE scc_info *new_scc_info(void) {
372 scc_info *info = obstack_alloc (outermost_ir_graph->obst, sizeof(*info));
373 memset(info, 0, sizeof(*info));
378 cg_irg_visited(ir_graph *n) {
379 scc_info *info = get_irg_link(n);
380 return (info->visited >= master_cg_visited);
384 mark_cg_irg_visited(ir_graph *n) {
385 scc_info *info = get_irg_link(n);
386 info->visited = master_cg_visited;
390 set_cg_irg_visited(ir_graph *n, int i) {
391 scc_info *info = get_irg_link(n);
396 get_cg_irg_visited(ir_graph *n) {
397 scc_info *info = get_irg_link(n);
398 return info->visited;
402 mark_irg_in_stack (ir_graph *n) {
403 scc_info *info = get_irg_link(n);
405 info->in_stack = true;
409 mark_irg_not_in_stack (ir_graph *n) {
410 scc_info *info = get_irg_link(n);
412 info->in_stack = false;
416 irg_is_in_stack (ir_graph *n) {
417 scc_info *info = get_irg_link(n);
419 return info->in_stack;
423 set_irg_uplink (ir_graph *n, int uplink) {
424 scc_info *info = get_irg_link(n);
426 info->uplink = uplink;
430 get_irg_uplink (ir_graph *n) {
431 scc_info *info = get_irg_link(n);
437 set_irg_dfn (ir_graph *n, int dfn) {
438 scc_info *info = get_irg_link(n);
444 get_irg_dfn (ir_graph *n) {
445 scc_info *info = get_irg_link(n);
450 /**********************************************************************/
452 /**********************************************************************/
454 static ir_graph **stack = NULL;
455 static int tos = 0; /**< top of stack */
458 * initialize the irg stack
460 static INLINE void init_stack(void) {
462 ARR_RESIZE (ir_graph *, stack, 1000);
464 stack = NEW_ARR_F (ir_graph *, 1000);
470 * push a graph on the irg stack
471 * @param n the graph to be pushed
476 if (tos == ARR_LEN (stack)) {
477 int nlen = ARR_LEN (stack) * 2;
478 ARR_RESIZE (ir_node *, stack, nlen);
481 mark_irg_in_stack(n);
485 * return the topmost graph on the stack and pop it
487 static INLINE ir_graph *
490 ir_graph *n = stack[--tos];
491 mark_irg_not_in_stack(n);
496 * The nodes up to n belong to the current loop.
497 * Removes them from the stack and adds them to the current loop.
500 pop_scc_to_loop (ir_graph *n)
507 set_irg_dfn(m, loop_node_cnt);
508 add_loop_node(current_loop, (ir_node *)m);
510 //m->callgraph_loop_depth = current_loop->depth;
514 /* GL ??? my last son is my grandson??? Removes cfloops with no
515 ir_nodes in them. Such loops have only another loop as son. (Why
516 can't they have two loops as sons? Does it never get that far? ) */
517 static void close_loop (ir_loop *l)
519 int last = get_loop_n_elements(l) - 1;
520 loop_element lelement = get_loop_element(l, last);
521 ir_loop *last_son = lelement.son;
523 if (get_kind(last_son) == k_ir_loop &&
524 get_loop_n_elements(last_son) == 1) {
527 lelement = get_loop_element(last_son, 0);
529 if(get_kind(gson) == k_ir_loop) {
530 loop_element new_last_son;
532 gson -> outer_loop = l;
533 new_last_son.son = gson;
534 l -> children[last] = new_last_son;
542 * Removes and unmarks all nodes up to n from the stack.
543 * The nodes must be visited once more to assign them to a scc.
546 pop_scc_unmark_visit (ir_graph *n)
552 set_cg_irg_visited(m, 0);
556 /**********************************************************************/
557 /* The loop data structure. **/
558 /**********************************************************************/
561 * Allocates a new loop as son of current_loop. Sets current_loop
562 * to the new loop and returns the father.
564 static ir_loop *new_loop (void) {
565 ir_loop *father, *son;
567 father = current_loop;
569 son = obstack_alloc (outermost_ir_graph->obst, sizeof(*son));
570 memset (son, 0, sizeof(*son));
571 son->kind = k_ir_loop;
572 son->children = NEW_ARR_F (loop_element, 0);
576 son->outer_loop = father;
577 add_loop_son(father, son);
578 son->depth = father->depth + 1;
579 } else { /* The root loop */
580 son->outer_loop = son;
585 son->loop_nr = get_irp_new_node_nr();
593 /**********************************************************************/
594 /* Constructing and destructing the loop/backedge information. **/
595 /**********************************************************************/
597 /* Initialization steps. **********************************************/
608 n_irgs = get_irp_n_irgs();
609 for (i = 0; i < n_irgs; ++i) {
610 ir_graph *irg = get_irp_irg(i);
611 set_irg_link(irg, new_scc_info());
612 irg->callgraph_recursion_depth = 0;
613 irg->callgraph_loop_depth = 0;
617 /** Returns true if n is a loop header, i.e., it is a Block node
618 * and has predecessors within the cfloop and out of the cfloop.
620 * @param root: only needed for assertion.
623 is_head (ir_graph *n, ir_graph *root)
626 int some_outof_loop = 0, some_in_loop = 0;
628 arity = get_irg_n_callees(n);
629 for (i = 0; i < arity; i++) {
630 ir_graph *pred = get_irg_callee(n, i);
631 if (is_irg_callee_backedge(n, i)) continue;
632 if (!irg_is_in_stack(pred)) {
635 if (get_irg_uplink(pred) < get_irg_uplink(root)) {
636 DDMG(pred); DDMG(root);
637 assert(get_irg_uplink(pred) >= get_irg_uplink(root));
643 return some_outof_loop & some_in_loop;
647 * Returns true if n is possible loop head of an endless loop.
648 * I.e., it is a Block, Phi or Filter node and has only predecessors
650 * @arg root: only needed for assertion.
653 is_endless_head (ir_graph *n, ir_graph *root)
656 int some_outof_loop = 0, some_in_loop = 0;
658 arity = get_irg_n_callees(n);
659 for (i = 0; i < arity; i++) {
660 ir_graph *pred = get_irg_callee(n, i);
662 if (is_irg_callee_backedge(n, i)) { continue; }
663 if (!irg_is_in_stack(pred)) {
666 if(get_irg_uplink(pred) < get_irg_uplink(root)) {
667 DDMG(pred); DDMG(root);
668 assert(get_irg_uplink(pred) >= get_irg_uplink(root));
674 return !some_outof_loop & some_in_loop;
679 * Check whether there is a parallel edge in the ip control flow.
683 is_ip_head (ir_graph *n, ir_graph *pred)
686 int iv_rem = get_interprocedural_view();
687 set_interprocedural_view(true);
689 ir_node *sblock = get_irg_start_block(n);
690 int i, arity = get_Block_n_cfgpreds(sblock);
692 //printf(" edge from "); DDMG(n);
693 //printf(" to pred "); DDMG(pred);
694 //printf(" sblock "); DDMN(sblock);
696 for (i = 0; i < arity; i++) {
697 ir_node *pred_cfop = skip_Proj(get_Block_cfgpred(sblock, i));
698 //printf(" "); DDMN(pred_cfop);
699 if (get_irn_op(pred_cfop) == op_CallBegin) { /* could be Unknown */
700 ir_graph *ip_pred = get_irn_irg(pred_cfop);
701 //printf(" "); DDMG(ip_pred);
702 if ((ip_pred == pred) && is_backedge(sblock, i)) {
703 //printf(" found\n");
709 set_interprocedural_view(iv_rem);
714 * Returns index of the predecessor with the smallest dfn number
715 * greater-equal than limit.
718 smallest_dfn_pred (ir_graph *n, int limit)
720 int i, index = -2, min = -1;
722 int arity = get_irg_n_callees(n);
723 for (i = 0; i < arity; i++) {
724 ir_graph *pred = get_irg_callee(n, i);
725 if (is_irg_callee_backedge(n, i) || !irg_is_in_stack(pred)) continue;
726 if (get_irg_dfn(pred) >= limit && (min == -1 || get_irg_dfn(pred) < min)) {
728 min = get_irg_dfn(pred);
735 /** Returns index of the predecessor with the largest dfn number. */
737 largest_dfn_pred (ir_graph *n)
739 int i, index = -2, max = -1;
741 int arity = get_irg_n_callees(n);
742 for (i = 0; i < arity; i++) {
743 ir_graph *pred = get_irg_callee(n, i);
744 if (is_irg_callee_backedge (n, i) || !irg_is_in_stack(pred)) continue;
745 if (get_irg_dfn(pred) > max) {
747 max = get_irg_dfn(pred);
756 find_tail (ir_graph *n) {
758 int i, res_index = -2;
761 if (!icfg && rm_cyclic_phis && remove_cyclic_phis (n)) return NULL;
763 m = stack[tos-1]; /* tos = top of stack */
764 if (is_head (m, n)) {
765 res_index = smallest_dfn_pred(m, 0);
766 if ((res_index == -2) && /* no smallest dfn pred found. */
770 if (m == n) return NULL; // Is this to catch Phi - self loops?
771 for (i = tos-2; i >= 0; --i) {
774 if (is_head (m, n)) {
775 res_index = smallest_dfn_pred (m, get_irg_dfn(m) + 1);
776 if (res_index == -2) /* no smallest dfn pred found. */
777 res_index = largest_dfn_pred (m);
779 if ((m == n) && (res_index == -2)) {
785 /* We should not walk past our selves on the stack: The upcoming nodes
786 are not in this loop. We assume a loop not reachable from Start. */
795 /* A dead loop not reachable from Start. */
796 for (i = tos-2; i >= 0; --i) {
798 if (is_endless_head (m, n)) {
799 res_index = smallest_dfn_pred (m, get_irg_dfn(m) + 1);
800 if (res_index == -2) /* no smallest dfn pred found. */
801 res_index = largest_dfn_pred (m);
804 if (m == n) { break; } /* It's not an unreachable loop, either. */
806 //assert(0 && "no head found on stack");
810 assert (res_index > -2);
812 set_irg_callee_backedge (m, res_index);
813 return get_irg_callee(m, res_index);
817 find_tail (ir_graph *n) {
819 int i, res_index = -2;
822 ir_graph *in_and_out = NULL;
823 ir_graph *only_in = NULL;
824 ir_graph *ip_in_and_out = NULL;
825 ir_graph *ip_only_in = NULL;
827 //printf("find tail for "); DDMG(n);
829 for (i = tos-1; i >= 0; --i) {
830 ir_graph *pred = (i < tos -1) ? stack[i+1] : n;
833 if (is_head (m, n)) {
834 //printf(" found 1a! "); DDM;
836 if (is_ip_head(pred, m)) {
837 //printf(" found 1b! "); DDM;
840 } else if (!ip_only_in && is_endless_head(m, n)) {
842 //printf(" found 2a! "); DDM;
843 if (is_ip_head(pred, m)) {
844 //printf(" found 2b! "); DDM;
847 } else if (is_ip_head(pred, m)) {
848 //printf(" found 3! "); DDM; This happens for self recursions in the second
849 //assert(0); scc iteration (the one to flip the loop.)
852 if (ip_in_and_out) break; /* That's what we really want. */
854 if (m == n) break; /* Don't walk past n on the stack! */
858 if (!in_and_out && !only_in)
859 /* There is no loop */
863 /* Is there a head in the callgraph without a head in the
865 assert(in_and_out || only_in);
867 m = (ip_in_and_out) ? ip_in_and_out : ip_only_in;
870 m = (in_and_out) ? in_and_out : only_in;
872 //printf("*** head is "); DDMG(m);
874 res_index = smallest_dfn_pred (m, get_irg_dfn(m) + 1);
875 if (res_index == -2) /* no smallest dfn pred found. */
876 res_index = largest_dfn_pred (m);
878 set_irg_callee_backedge (m, res_index);
879 res = get_irg_callee(m, res_index);
880 //printf("*** tail is "); DDMG(res);
886 /*-----------------------------------------------------------*
887 * The core algorithm. *
888 *-----------------------------------------------------------*/
891 static void cgscc (ir_graph *n) {
894 if (cg_irg_visited(n)) return;
895 mark_cg_irg_visited(n);
897 /* Initialize the node */
898 set_irg_dfn(n, current_dfn); /* Depth first number for this node */
899 set_irg_uplink(n, current_dfn); /* ... is default uplink. */
903 arity = get_irg_n_callees(n);
904 for (i = 0; i < arity; i++) {
906 if (is_irg_callee_backedge(n, i)) continue;
907 m = get_irg_callee(n, i);
909 /** This marks the backedge, but does it guarantee a correct loop tree? */
910 //if (m == n) { set_irg_callee_backedge(n, i); continue; }
913 if (irg_is_in_stack(m)) {
914 /* Uplink of m is smaller if n->m is a backedge.
915 Propagate the uplink to mark the cfloop. */
916 if (get_irg_uplink(m) < get_irg_uplink(n))
917 set_irg_uplink(n, get_irg_uplink(m));
921 if (get_irg_dfn(n) == get_irg_uplink(n)) {
922 /* This condition holds for
923 1) the node with the incoming backedge.
924 That is: We found a cfloop!
925 2) Straight line code, because no uplink has been propagated, so the
926 uplink still is the same as the dfn.
928 But n might not be a proper cfloop head for the analysis. Proper cfloop
929 heads are Block and Phi nodes. find_tail searches the stack for
930 Block's and Phi's and takes those nodes as cfloop heads for the current
931 cfloop instead and marks the incoming edge as backedge. */
933 ir_graph *tail = find_tail(n);
935 /* We have a cfloop, that is no straight line code,
936 because we found a cfloop head!
937 Next actions: Open a new cfloop on the cfloop tree and
938 try to find inner cfloops */
941 ir_loop *l = new_loop();
943 /* Remove the cfloop from the stack ... */
944 pop_scc_unmark_visit (n);
946 /* The current backedge has been marked, that is temporarily eliminated,
947 by find tail. Start the scc algorithm
948 anew on the subgraph thats left (the current cfloop without the backedge)
949 in order to find more inner cfloops. */
953 assert (cg_irg_visited(n));
963 * reset the backedge information for all callers in all irgs
965 static void reset_isbe(void) {
966 int i, n_irgs = get_irp_n_irgs();
968 for (i = 0; i < n_irgs; ++i) {
970 ir_graph *irg = get_irp_irg(i);
972 n_cs = get_irg_n_callers(irg);
973 for (j = 0; j < n_cs; ++j) {
974 irg->caller_isbe[j] = 0;
977 n_cs = get_irg_n_callees(irg);
978 for (j = 0; j < n_cs; ++j) {
979 irg->callee_isbe[j] = 0;
987 /* ----------------------------------------------------------------------------------- */
988 /* Another algorithm to compute recursion nesting depth */
989 /* Walk the callgraph. For each crossed edge increase the loop depth by the edge */
990 /* weight. Assign graphs the maximal depth. */
991 /* ----------------------------------------------------------------------------------- */
993 static void compute_loop_depth (ir_graph *irg, void *env) {
994 int current_nesting = *(int *) env;
995 int old_nesting = irg->callgraph_loop_depth;
996 int old_visited = get_cg_irg_visited(irg);
1001 if (cg_irg_visited(irg)) return;
1003 mark_cg_irg_visited(irg);
1005 //printf(" old: %d new %d master %d", old_visited, get_cg_irg_visited(irg), master_cg_visited); DDMG(irg);
1008 if (old_nesting < current_nesting)
1009 irg->callgraph_loop_depth = current_nesting;
1011 if (current_nesting > irp->max_callgraph_loop_depth)
1012 irp->max_callgraph_loop_depth = current_nesting;
1014 if ((old_visited +1 < get_cg_irg_visited(irg)) || /* not yet visited */
1015 (old_nesting < current_nesting)) { /* propagate larger nesting */
1016 /* Don't walk the graph, but a tree that is an unfolded graph. */
1017 n_callees = get_irg_n_callees(irg);
1018 for (i = 0; i < n_callees; i++) {
1019 ir_graph *m = get_irg_callee(irg, i);
1020 *(int *)env += get_irg_callee_loop_depth(irg, i);
1021 compute_loop_depth(m, env);
1022 *(int *)env -= get_irg_callee_loop_depth(irg, i);
1026 set_cg_irg_visited(irg, master_cg_visited-1);
1029 /* ------------------------------------------------------------------------------------ */
1030 /* Another algorithm to compute recursion nesting depth */
1031 /* Walk the callgraph. For each crossed loop increase the nesting depth by one. */
1032 /* Assign graphs the maximal nesting depth. Don't increase if passing loops more than */
1034 /* ------------------------------------------------------------------------------------ */
1037 /* For callees, we want to remember the Call nodes, too. */
1038 typedef struct ana_entry2 {
1039 ir_loop **loop_stack; /**< a stack of ir_loop entries */
1040 int tos; /**< the top of stack entry */
1041 int recursion_nesting;
1045 * push a loop entry on the stack
1047 static void push2(ana_entry2 *e, ir_loop *g) {
1048 if (ARR_LEN(e->loop_stack) == e->tos) {
1049 ARR_APP1(ir_loop *, e->loop_stack, g);
1051 e->loop_stack[e->tos] = g;
1057 * returns the top of stack and pop it
1059 static ir_loop *pop2(ana_entry2 *e) {
1060 return e->loop_stack[--e->tos];
1064 * check if a loop g in on the stack. Did not check the TOS.
1066 static int in_stack(ana_entry2 *e, ir_loop *g) {
1068 for (i = e->tos-1; i >= 0; --i) {
1069 if (e->loop_stack[i] == g) return 1;
1074 static void compute_rec_depth (ir_graph *irg, void *env) {
1075 ana_entry2 *e = (ana_entry2 *)env;
1076 ir_loop *l = irg->l;
1077 int depth, old_depth = irg->callgraph_recursion_depth;
1081 if (cg_irg_visited(irg)) return;
1082 mark_cg_irg_visited(irg);
1084 /* -- compute and set the new nesting value -- */
1085 if ((l != irp->outermost_cg_loop) && !in_stack(e, l)) {
1087 e->recursion_nesting++;
1090 depth = e->recursion_nesting;
1092 if (old_depth < depth)
1093 irg->callgraph_recursion_depth = depth;
1095 if (depth > irp->max_callgraph_recursion_depth)
1096 irp->max_callgraph_recursion_depth = depth;
1098 /* -- spread the nesting value -- */
1099 if (depth == 0 || old_depth < depth) {
1100 /* Don't walk the graph, but a tree that is an unfolded graph.
1101 Therefore we unset the visited flag at the end. */
1102 n_callees = get_irg_n_callees(irg);
1103 for (i = 0; i < n_callees; i++) {
1104 ir_graph *m = get_irg_callee(irg, i);
1105 compute_rec_depth(m, env);
1109 /* -- clean up -- */
1112 e->recursion_nesting--;
1114 set_cg_irg_visited(irg, master_cg_visited-1);
1118 /* ----------------------------------------------------------------------------------- */
1119 /* Another algorithm to compute the execution frequency of methods ignoring recursions. */
1120 /* Walk the callgraph. Ignore backedges. Use sum of execution frequencies of Call */
1121 /* nodes to evaluate a callgraph edge. */
1122 /* ----------------------------------------------------------------------------------- */
1124 double get_irg_method_execution_frequency (ir_graph *irg) {
1125 return irg->method_execution_frequency;
1128 void set_irg_method_execution_frequency (ir_graph *irg, double freq) {
1129 irg->method_execution_frequency = freq;
1131 if (irp->max_method_execution_frequency < freq)
1132 irp->max_method_execution_frequency = freq;
1135 static void compute_method_execution_frequency (ir_graph *irg, void *env) {
1141 if (cg_irg_visited(irg)) return;
1143 /* We need the values of all predecessors (except backedges).
1144 So they must be marked. Else we will reach the node through
1145 one of the unmarked ones. */
1146 n_callers = get_irg_n_callers(irg);
1147 for (i = 0; i < n_callers; i++) {
1148 ir_graph *m = get_irg_caller(irg, i);
1149 if (is_irg_caller_backedge(irg, i)) continue;
1150 if (!cg_irg_visited(m)) {
1154 mark_cg_irg_visited(irg);
1156 /* Compute the new frequency. */
1159 for (i = 0; i < n_callers; i++) {
1160 if (! is_irg_caller_backedge(irg, i)) {
1161 double edge_freq = get_irg_caller_method_execution_frequency(irg, i);
1162 assert(edge_freq >= 0);
1169 /* A starting point: method only called from outside,
1170 or only backedges as predecessors. */
1174 set_irg_method_execution_frequency(irg, freq);
1177 n_callees = get_irg_n_callees(irg);
1178 for (i = 0; i < n_callees; i++) {
1179 compute_method_execution_frequency (get_irg_callee(irg, i), NULL);
1184 /* ----------------------------------------------------------------------------------- */
1185 /* The recursion stuff driver. */
1186 /* ----------------------------------------------------------------------------------- */
1188 /* Compute the backedges that represent recursions. */
1189 void find_callgraph_recursions(void) {
1190 int i, n_irgs = get_irp_n_irgs();
1194 /* -- compute the looptree. -- */
1196 /* The outermost graph. We start here. Then we start at all
1197 functions in irg list that are never called, then at the remaining
1198 unvisited ones. The third step is needed for functions that are not
1199 reachable from the outermost graph, but call themselves in a cycle. */
1200 assert(get_irp_main_irg());
1201 outermost_ir_graph = get_irp_main_irg();
1204 current_loop = NULL;
1205 new_loop(); /* sets current_loop */
1207 master_cg_visited++;
1208 cgscc(outermost_ir_graph);
1209 for (i = 0; i < n_irgs; i++) {
1210 ir_graph *irg = get_irp_irg(i);
1211 if (!cg_irg_visited(irg) && get_irg_n_callers(irg) == 0)
1214 for (i = 0; i < n_irgs; i++) {
1215 ir_graph *irg = get_irp_irg(i);
1216 if (!cg_irg_visited(irg))
1219 irp->outermost_cg_loop = current_loop;
1221 /* -- Reverse the backedge information. -- */
1222 for (i = 0; i < n_irgs; i++) {
1223 ir_graph *irg = get_irp_irg(i);
1224 int j, n_callees = get_irg_n_callees(irg);
1225 for (j = 0; j < n_callees; ++j) {
1226 if (is_irg_callee_backedge(irg, j))
1227 set_irg_caller_backedge(get_irg_callee(irg, j), irg);
1231 irp->callgraph_state = irp_callgraph_and_calltree_consistent;
1234 void compute_performance_estimates(void) {
1235 int i, n_irgs = get_irp_n_irgs();
1236 int current_nesting;
1239 /* -- compute the loop depth -- */
1240 current_nesting = 0;
1241 irp->max_callgraph_loop_depth = 0;
1242 master_cg_visited += 2;
1243 //printf (" ** starting at "); DDMG(get_irp_main_irg());
1244 compute_loop_depth(get_irp_main_irg(), ¤t_nesting);
1245 for (i = 0; i < n_irgs; i++) {
1246 ir_graph *irg = get_irp_irg(i);
1247 if ((get_cg_irg_visited(irg) < master_cg_visited-1) &&
1248 get_irg_n_callers(irg) == 0) {
1249 compute_loop_depth(irg, ¤t_nesting);
1250 //printf (" ** starting at "); DDMG(irg);
1253 for (i = 0; i < n_irgs; i++) {
1254 ir_graph *irg = get_irp_irg(i);
1255 if (get_cg_irg_visited(irg) < master_cg_visited-1) {
1256 compute_loop_depth(irg, ¤t_nesting);
1257 //printf (" ** starting at "); DDMG(irg);
1262 /* -- compute the recursion depth -- */
1263 e.loop_stack = NEW_ARR_F(ir_loop *, 0);
1265 e.recursion_nesting = 0;
1267 irp->max_callgraph_recursion_depth = 0;
1269 master_cg_visited += 2;
1270 compute_rec_depth(get_irp_main_irg(), &e);
1271 //printf (" ++ starting at "); DDMG(get_irp_main_irg());
1272 for (i = 0; i < n_irgs; i++) {
1273 ir_graph *irg = get_irp_irg(i);
1274 if ((get_cg_irg_visited(irg) < master_cg_visited-1) &&
1275 get_irg_n_callers(irg) == 0) {
1276 compute_rec_depth(irg, &e);
1277 //printf (" ++ starting at "); DDMG(irg);
1280 for (i = 0; i < n_irgs; i++) {
1281 ir_graph *irg = get_irp_irg(i);
1282 if (get_cg_irg_visited(irg) < master_cg_visited-1) {
1283 compute_rec_depth(irg, &e);
1284 //printf (" ++ starting at "); DDMG(irg);
1288 DEL_ARR_F(e.loop_stack);
1290 /* -- compute the execution frequency -- */
1291 irp->max_method_execution_frequency = 0;
1292 master_cg_visited += 2;
1293 assert(get_irg_n_callers(get_irp_main_irg()) == 0);
1294 compute_method_execution_frequency(get_irp_main_irg(), NULL);
1295 for (i = 0; i < n_irgs; i++) {
1296 ir_graph *irg = get_irp_irg(i);
1297 if ((get_cg_irg_visited(irg) < master_cg_visited-1) &&
1298 get_irg_n_callers(irg) == 0) {
1299 compute_method_execution_frequency(irg, NULL);
1302 for (i = 0; i < n_irgs; i++) {
1303 ir_graph *irg = get_irp_irg(i);
1304 if (get_cg_irg_visited(irg) < master_cg_visited-1) {
1305 compute_method_execution_frequency(irg, NULL);
1310 /* Maximal loop depth of all paths from an external visible method to
1312 int get_irg_loop_depth(ir_graph *irg) {
1313 assert(irp->callgraph_state == irp_callgraph_consistent ||
1314 irp->callgraph_state == irp_callgraph_and_calltree_consistent);
1315 return irg->callgraph_loop_depth;
1318 /* Maximal recursion depth of all paths from an external visible method to
1320 int get_irg_recursion_depth(ir_graph *irg) {
1321 assert(irp->callgraph_state == irp_callgraph_and_calltree_consistent);
1322 return irg->callgraph_recursion_depth;
1325 void analyse_loop_nesting_depth(void) {
1326 entity **free_methods = NULL;
1329 /* establish preconditions. */
1330 if (get_irp_callee_info_state() != irg_callee_info_consistent) {
1331 cgana(&arr_len, &free_methods);
1334 if (irp_callgraph_consistent != get_irp_callgraph_state()) {
1335 compute_callgraph();
1338 find_callgraph_recursions();
1340 compute_performance_estimates();
1342 set_irp_loop_nesting_depth_state(loop_nesting_depth_consistent);
1346 loop_nesting_depth_state get_irp_loop_nesting_depth_state(void) {
1347 return irp->lnd_state;
1349 void set_irp_loop_nesting_depth_state(loop_nesting_depth_state s) {
1352 void set_irp_loop_nesting_depth_state_inconsistent(void) {
1353 if (irp->lnd_state == loop_nesting_depth_consistent)
1354 irp->lnd_state = loop_nesting_depth_inconsistent;