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 (get_irn_op(n) != op_Call) 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 = { callee, NULL, 0};
199 pset_insert((pset *)callee->callers, irg, HASH_PTR(irg));
200 found = pset_find((pset *)irg->callees, &buf, HASH_PTR(callee));
201 if (found) { /* add Call node to list, compute new nesting. */
202 ir_node **arr = found->call_list;
203 ARR_APP1(ir_node *, arr, n);
204 found->call_list = arr;
205 } else { /* New node, add Call node and init nesting. */
206 found = (ana_entry *) obstack_alloc (irg->obst, sizeof (ana_entry));
208 found->call_list = NEW_ARR_F(ir_node *, 1);
209 found->call_list[0] = n;
210 found->max_depth = 0;
211 pset_insert((pset *)irg->callees, found, HASH_PTR(callee));
213 depth = get_loop_depth(get_irn_loop(get_nodes_block(n)));
214 found->max_depth = (depth > found->max_depth) ? depth : found->max_depth;
219 /** compare two ir graphs in a ana_entry */
220 static int ana_entry_cmp(const void *elt, const void *key) {
221 const ana_entry *e1 = elt;
222 const ana_entry *e2 = key;
223 return e1->irg != e2->irg;
226 /** compare two ir graphs */
227 static int graph_cmp(const void *elt, const void *key) {
232 /* Construct and destruct the callgraph. */
233 void compute_callgraph(void) {
234 int i, n_irgs = get_irp_n_irgs();
236 assert(! get_interprocedural_view()); /* Else walking will not reach the Call nodes. */
240 for (i = 0; i < n_irgs; ++i) {
241 ir_graph *irg = get_irp_irg(i);
242 assert(get_irg_callee_info_state(irg) == irg_callee_info_consistent);
243 irg->callees = (ir_graph **)new_pset(ana_entry_cmp, 8);
244 irg->callers = (ir_graph **)new_pset(graph_cmp, 8);
245 //construct_cf_backedges(irg);
248 /* Compute the call graph */
249 for (i = 0; i < n_irgs; ++i) {
250 ir_graph *irg = get_irp_irg(i);
251 construct_cf_backedges(irg); // We also find the maximal loop depth of a call.
252 irg_walk_graph(irg, ana_Call, NULL, NULL);
255 /* Change the sets to arrays. */
256 for (i = 0; i < n_irgs; ++i) {
258 ir_graph *c, *irg = get_irp_irg(i);
259 pset *callee_set, *caller_set;
261 callee_set = (pset *)irg->callees;
262 count = pset_count(callee_set);
263 irg->callees = NEW_ARR_F(ir_graph *, count);
264 irg->callee_isbe = xcalloc(count, sizeof(irg->callee_isbe[0]));
265 c = pset_first(callee_set);
266 for (j = 0; j < count; ++j) {
268 c = pset_next(callee_set);
270 del_pset(callee_set);
273 caller_set = (pset *)irg->callers;
274 count = pset_count(caller_set);
275 irg->callers = NEW_ARR_F(ir_graph *, count);
276 irg->caller_isbe = xcalloc(count, sizeof(irg->caller_isbe[0]));
277 c = pset_first(caller_set);
278 for (j = 0; j < count; ++j) {
280 c = pset_next(caller_set);
282 del_pset(caller_set);
285 set_irp_callgraph_state(irp_callgraph_consistent);
288 void free_callgraph(void) {
289 int i, n_irgs = get_irp_n_irgs();
290 for (i = 0; i < n_irgs; ++i) {
291 ir_graph *irg = get_irp_irg(i);
292 if (irg->callees) DEL_ARR_F(irg->callees);
293 if (irg->callers) DEL_ARR_F(irg->callers);
294 if (irg->callee_isbe) free(irg->callee_isbe);
295 if (irg->caller_isbe) free(irg->caller_isbe);
298 irg->callee_isbe = NULL;
299 irg->caller_isbe = NULL;
301 set_irp_callgraph_state(irp_callgraph_none);
304 /* ----------------------------------------------------------------------------------- */
305 /* A walker for the callgraph */
306 /* ----------------------------------------------------------------------------------- */
309 static void do_walk(ir_graph *irg, callgraph_walk_func *pre, callgraph_walk_func *post, void *env) {
312 if (cg_irg_visited(irg)) return;
313 mark_cg_irg_visited(irg);
317 n_callees = get_irg_n_callees(irg);
318 for (i = 0; i < n_callees; i++) {
319 ir_graph *m = get_irg_callee(irg, i);
320 do_walk(m, pre, post, env);
326 void callgraph_walk(callgraph_walk_func *pre, callgraph_walk_func *post, void *env) {
327 int i, n_irgs = get_irp_n_irgs();
330 do_walk(get_irp_main_irg(), pre, post, env);
331 for (i = 0; i < n_irgs; i++) {
332 ir_graph *irg = get_irp_irg(i);
333 if (!cg_irg_visited(irg) && get_irg_n_callers(irg) == 0)
334 do_walk(irg, pre, post, env);
336 for (i = 0; i < n_irgs; i++) {
337 ir_graph *irg = get_irp_irg(i);
338 if (!cg_irg_visited(irg))
339 do_walk(irg, pre, post, env);
343 /* ----------------------------------------------------------------------------------- */
344 /* loop construction algorithm */
345 /* ----------------------------------------------------------------------------------- */
347 static ir_graph *outermost_ir_graph; /**< The outermost graph the scc is computed
349 static ir_loop *current_loop; /**< Current cfloop construction is working
351 static int loop_node_cnt = 0; /**< Counts the number of allocated cfloop nodes.
352 Each cfloop node gets a unique number.
353 What for? ev. remove. @@@ */
354 static int current_dfn = 1; /**< Counter to generate depth first numbering
358 /**********************************************************************/
359 /* Node attributes **/
360 /**********************************************************************/
362 typedef struct scc_info {
363 int in_stack; /**< Marks whether node is on the stack. */
364 int dfn; /**< Depth first search number. */
365 int uplink; /**< dfn number of ancestor. */
370 * allocates a new scc_info of the obstack
372 static INLINE scc_info *new_scc_info(void) {
373 scc_info *info = obstack_alloc (outermost_ir_graph->obst, sizeof(*info));
374 memset(info, 0, sizeof(*info));
379 cg_irg_visited(ir_graph *n) {
380 scc_info *info = get_irg_link(n);
381 return (info->visited >= master_cg_visited);
385 mark_cg_irg_visited(ir_graph *n) {
386 scc_info *info = get_irg_link(n);
387 info->visited = master_cg_visited;
391 set_cg_irg_visited(ir_graph *n, int i) {
392 scc_info *info = get_irg_link(n);
397 get_cg_irg_visited(ir_graph *n) {
398 scc_info *info = get_irg_link(n);
399 return info->visited;
403 mark_irg_in_stack (ir_graph *n) {
404 scc_info *info = get_irg_link(n);
410 mark_irg_not_in_stack (ir_graph *n) {
411 scc_info *info = get_irg_link(n);
417 irg_is_in_stack (ir_graph *n) {
418 scc_info *info = get_irg_link(n);
420 return info->in_stack;
424 set_irg_uplink (ir_graph *n, int uplink) {
425 scc_info *info = get_irg_link(n);
427 info->uplink = uplink;
431 get_irg_uplink (ir_graph *n) {
432 scc_info *info = get_irg_link(n);
438 set_irg_dfn (ir_graph *n, int dfn) {
439 scc_info *info = get_irg_link(n);
445 get_irg_dfn (ir_graph *n) {
446 scc_info *info = get_irg_link(n);
451 /**********************************************************************/
453 /**********************************************************************/
455 static ir_graph **stack = NULL;
456 static int tos = 0; /**< top of stack */
459 * initialize the irg stack
461 static INLINE void init_stack(void) {
463 ARR_RESIZE (ir_graph *, stack, 1000);
465 stack = NEW_ARR_F (ir_graph *, 1000);
471 * push a graph on the irg stack
472 * @param n the graph to be pushed
477 if (tos == ARR_LEN (stack)) {
478 int nlen = ARR_LEN (stack) * 2;
479 ARR_RESIZE (ir_node *, stack, nlen);
482 mark_irg_in_stack(n);
486 * return the topmost graph on the stack and pop it
488 static INLINE ir_graph *
491 ir_graph *n = stack[--tos];
492 mark_irg_not_in_stack(n);
497 * The nodes up to n belong to the current loop.
498 * Removes them from the stack and adds them to the current loop.
501 pop_scc_to_loop (ir_graph *n)
508 set_irg_dfn(m, loop_node_cnt);
509 add_loop_node(current_loop, (ir_node *)m);
511 //m->callgraph_loop_depth = current_loop->depth;
515 /* GL ??? my last son is my grandson??? Removes cfloops with no
516 ir_nodes in them. Such loops have only another loop as son. (Why
517 can't they have two loops as sons? Does it never get that far? ) */
518 static void close_loop (ir_loop *l)
520 int last = get_loop_n_elements(l) - 1;
521 loop_element lelement = get_loop_element(l, last);
522 ir_loop *last_son = lelement.son;
524 if (get_kind(last_son) == k_ir_loop &&
525 get_loop_n_elements(last_son) == 1) {
528 lelement = get_loop_element(last_son, 0);
530 if(get_kind(gson) == k_ir_loop) {
531 loop_element new_last_son;
533 gson -> outer_loop = l;
534 new_last_son.son = gson;
535 l -> children[last] = new_last_son;
543 * Removes and unmarks all nodes up to n from the stack.
544 * The nodes must be visited once more to assign them to a scc.
547 pop_scc_unmark_visit (ir_graph *n)
553 set_cg_irg_visited(m, 0);
557 /**********************************************************************/
558 /* The loop data structure. **/
559 /**********************************************************************/
562 * Allocates a new loop as son of current_loop. Sets current_loop
563 * to the new loop and returns the father.
565 static ir_loop *new_loop (void) {
566 ir_loop *father, *son;
568 father = current_loop;
570 son = obstack_alloc (outermost_ir_graph->obst, sizeof(*son));
571 memset (son, 0, sizeof(*son));
572 son->kind = k_ir_loop;
573 son->children = NEW_ARR_F (loop_element, 0);
577 son->outer_loop = father;
578 add_loop_son(father, son);
579 son->depth = father->depth + 1;
580 } else { /* The root loop */
581 son->outer_loop = son;
586 son->loop_nr = get_irp_new_node_nr();
594 /**********************************************************************/
595 /* Constructing and destructing the loop/backedge information. **/
596 /**********************************************************************/
598 /* Initialization steps. **********************************************/
609 n_irgs = get_irp_n_irgs();
610 for (i = 0; i < n_irgs; ++i) {
611 ir_graph *irg = get_irp_irg(i);
612 set_irg_link(irg, new_scc_info());
613 irg->callgraph_recursion_depth = 0;
614 irg->callgraph_loop_depth = 0;
618 /** Returns non-zero if n is a loop header, i.e., it is a Block node
619 * and has predecessors within the cfloop and out of the cfloop.
621 * @param root: only needed for assertion.
624 is_head (ir_graph *n, ir_graph *root)
627 int some_outof_loop = 0, some_in_loop = 0;
629 arity = get_irg_n_callees(n);
630 for (i = 0; i < arity; i++) {
631 ir_graph *pred = get_irg_callee(n, i);
632 if (is_irg_callee_backedge(n, i)) continue;
633 if (!irg_is_in_stack(pred)) {
636 if (get_irg_uplink(pred) < get_irg_uplink(root)) {
637 DDMG(pred); DDMG(root);
638 assert(get_irg_uplink(pred) >= get_irg_uplink(root));
644 return some_outof_loop & some_in_loop;
648 * Returns non-zero if n is possible loop head of an endless loop.
649 * I.e., it is a Block, Phi or Filter node and has only predecessors
651 * @arg root: only needed for assertion.
654 is_endless_head (ir_graph *n, ir_graph *root)
657 int some_outof_loop = 0, some_in_loop = 0;
659 arity = get_irg_n_callees(n);
660 for (i = 0; i < arity; i++) {
661 ir_graph *pred = get_irg_callee(n, i);
663 if (is_irg_callee_backedge(n, i)) { continue; }
664 if (!irg_is_in_stack(pred)) {
667 if(get_irg_uplink(pred) < get_irg_uplink(root)) {
668 DDMG(pred); DDMG(root);
669 assert(get_irg_uplink(pred) >= get_irg_uplink(root));
675 return !some_outof_loop & some_in_loop;
680 * Check whether there is a parallel edge in the ip control flow.
684 is_ip_head (ir_graph *n, ir_graph *pred)
687 int iv_rem = get_interprocedural_view();
688 set_interprocedural_view(1);
690 ir_node *sblock = get_irg_start_block(n);
691 int i, arity = get_Block_n_cfgpreds(sblock);
693 //printf(" edge from "); DDMG(n);
694 //printf(" to pred "); DDMG(pred);
695 //printf(" sblock "); DDMN(sblock);
697 for (i = 0; i < arity; i++) {
698 ir_node *pred_cfop = skip_Proj(get_Block_cfgpred(sblock, i));
699 //printf(" "); DDMN(pred_cfop);
700 if (get_irn_op(pred_cfop) == op_CallBegin) { /* could be Unknown */
701 ir_graph *ip_pred = get_irn_irg(pred_cfop);
702 //printf(" "); DDMG(ip_pred);
703 if ((ip_pred == pred) && is_backedge(sblock, i)) {
704 //printf(" found\n");
710 set_interprocedural_view(iv_rem);
715 * Returns index of the predecessor with the smallest dfn number
716 * greater-equal than limit.
719 smallest_dfn_pred (ir_graph *n, int limit)
721 int i, index = -2, min = -1;
723 int arity = get_irg_n_callees(n);
724 for (i = 0; i < arity; i++) {
725 ir_graph *pred = get_irg_callee(n, i);
726 if (is_irg_callee_backedge(n, i) || !irg_is_in_stack(pred)) continue;
727 if (get_irg_dfn(pred) >= limit && (min == -1 || get_irg_dfn(pred) < min)) {
729 min = get_irg_dfn(pred);
736 /** Returns index of the predecessor with the largest dfn number. */
738 largest_dfn_pred (ir_graph *n)
740 int i, index = -2, max = -1;
742 int arity = get_irg_n_callees(n);
743 for (i = 0; i < arity; i++) {
744 ir_graph *pred = get_irg_callee(n, i);
745 if (is_irg_callee_backedge (n, i) || !irg_is_in_stack(pred)) continue;
746 if (get_irg_dfn(pred) > max) {
748 max = get_irg_dfn(pred);
757 find_tail (ir_graph *n) {
759 int i, res_index = -2;
762 if (!icfg && rm_cyclic_phis && remove_cyclic_phis (n)) return NULL;
764 m = stack[tos-1]; /* tos = top of stack */
765 if (is_head (m, n)) {
766 res_index = smallest_dfn_pred(m, 0);
767 if ((res_index == -2) && /* no smallest dfn pred found. */
771 if (m == n) return NULL; // Is this to catch Phi - self loops?
772 for (i = tos-2; i >= 0; --i) {
775 if (is_head (m, n)) {
776 res_index = smallest_dfn_pred (m, get_irg_dfn(m) + 1);
777 if (res_index == -2) /* no smallest dfn pred found. */
778 res_index = largest_dfn_pred (m);
780 if ((m == n) && (res_index == -2)) {
786 /* We should not walk past our selves on the stack: The upcoming nodes
787 are not in this loop. We assume a loop not reachable from Start. */
796 /* A dead loop not reachable from Start. */
797 for (i = tos-2; i >= 0; --i) {
799 if (is_endless_head (m, n)) {
800 res_index = smallest_dfn_pred (m, get_irg_dfn(m) + 1);
801 if (res_index == -2) /* no smallest dfn pred found. */
802 res_index = largest_dfn_pred (m);
805 if (m == n) { break; } /* It's not an unreachable loop, either. */
807 //assert(0 && "no head found on stack");
811 assert (res_index > -2);
813 set_irg_callee_backedge (m, res_index);
814 return get_irg_callee(m, res_index);
818 find_tail (ir_graph *n) {
820 int i, res_index = -2;
823 ir_graph *in_and_out = NULL;
824 ir_graph *only_in = NULL;
825 ir_graph *ip_in_and_out = NULL;
826 ir_graph *ip_only_in = NULL;
828 //printf("find tail for "); DDMG(n);
830 for (i = tos-1; i >= 0; --i) {
831 ir_graph *pred = (i < tos -1) ? stack[i+1] : n;
834 if (is_head (m, n)) {
835 //printf(" found 1a! "); DDM;
837 if (is_ip_head(pred, m)) {
838 //printf(" found 1b! "); DDM;
841 } else if (!ip_only_in && is_endless_head(m, n)) {
843 //printf(" found 2a! "); DDM;
844 if (is_ip_head(pred, m)) {
845 //printf(" found 2b! "); DDM;
848 } else if (is_ip_head(pred, m)) {
849 //printf(" found 3! "); DDM; This happens for self recursions in the second
850 //assert(0); scc iteration (the one to flip the loop.)
853 if (ip_in_and_out) break; /* That's what we really want. */
855 if (m == n) break; /* Don't walk past n on the stack! */
859 if (!in_and_out && !only_in)
860 /* There is no loop */
864 /* Is there a head in the callgraph without a head in the
866 assert(in_and_out || only_in);
868 m = (ip_in_and_out) ? ip_in_and_out : ip_only_in;
871 m = (in_and_out) ? in_and_out : only_in;
873 //printf("*** head is "); DDMG(m);
875 res_index = smallest_dfn_pred (m, get_irg_dfn(m) + 1);
876 if (res_index == -2) /* no smallest dfn pred found. */
877 res_index = largest_dfn_pred (m);
879 set_irg_callee_backedge (m, res_index);
880 res = get_irg_callee(m, res_index);
881 //printf("*** tail is "); DDMG(res);
887 /*-----------------------------------------------------------*
888 * The core algorithm. *
889 *-----------------------------------------------------------*/
892 static void cgscc (ir_graph *n) {
895 if (cg_irg_visited(n)) return;
896 mark_cg_irg_visited(n);
898 /* Initialize the node */
899 set_irg_dfn(n, current_dfn); /* Depth first number for this node */
900 set_irg_uplink(n, current_dfn); /* ... is default uplink. */
904 arity = get_irg_n_callees(n);
905 for (i = 0; i < arity; i++) {
907 if (is_irg_callee_backedge(n, i)) continue;
908 m = get_irg_callee(n, i);
910 /** This marks the backedge, but does it guarantee a correct loop tree? */
911 //if (m == n) { set_irg_callee_backedge(n, i); continue; }
914 if (irg_is_in_stack(m)) {
915 /* Uplink of m is smaller if n->m is a backedge.
916 Propagate the uplink to mark the cfloop. */
917 if (get_irg_uplink(m) < get_irg_uplink(n))
918 set_irg_uplink(n, get_irg_uplink(m));
922 if (get_irg_dfn(n) == get_irg_uplink(n)) {
923 /* This condition holds for
924 1) the node with the incoming backedge.
925 That is: We found a cfloop!
926 2) Straight line code, because no uplink has been propagated, so the
927 uplink still is the same as the dfn.
929 But n might not be a proper cfloop head for the analysis. Proper cfloop
930 heads are Block and Phi nodes. find_tail searches the stack for
931 Block's and Phi's and takes those nodes as cfloop heads for the current
932 cfloop instead and marks the incoming edge as backedge. */
934 ir_graph *tail = find_tail(n);
936 /* We have a cfloop, that is no straight line code,
937 because we found a cfloop head!
938 Next actions: Open a new cfloop on the cfloop tree and
939 try to find inner cfloops */
942 ir_loop *l = new_loop();
944 /* Remove the cfloop from the stack ... */
945 pop_scc_unmark_visit (n);
947 /* The current backedge has been marked, that is temporarily eliminated,
948 by find tail. Start the scc algorithm
949 anew on the subgraph thats left (the current cfloop without the backedge)
950 in order to find more inner cfloops. */
954 assert (cg_irg_visited(n));
964 * reset the backedge information for all callers in all irgs
966 static void reset_isbe(void) {
967 int i, n_irgs = get_irp_n_irgs();
969 for (i = 0; i < n_irgs; ++i) {
971 ir_graph *irg = get_irp_irg(i);
973 n_cs = get_irg_n_callers(irg);
974 for (j = 0; j < n_cs; ++j) {
975 irg->caller_isbe[j] = 0;
978 n_cs = get_irg_n_callees(irg);
979 for (j = 0; j < n_cs; ++j) {
980 irg->callee_isbe[j] = 0;
988 /* ----------------------------------------------------------------------------------- */
989 /* Another algorithm to compute recursion nesting depth */
990 /* Walk the callgraph. For each crossed edge increase the loop depth by the edge */
991 /* weight. Assign graphs the maximal depth. */
992 /* ----------------------------------------------------------------------------------- */
994 static void compute_loop_depth (ir_graph *irg, void *env) {
995 int current_nesting = *(int *) env;
996 int old_nesting = irg->callgraph_loop_depth;
997 int old_visited = get_cg_irg_visited(irg);
1002 if (cg_irg_visited(irg)) return;
1004 mark_cg_irg_visited(irg);
1006 //printf(" old: %d new %d master %d", old_visited, get_cg_irg_visited(irg), master_cg_visited); DDMG(irg);
1009 if (old_nesting < current_nesting)
1010 irg->callgraph_loop_depth = current_nesting;
1012 if (current_nesting > irp->max_callgraph_loop_depth)
1013 irp->max_callgraph_loop_depth = current_nesting;
1015 if ((old_visited +1 < get_cg_irg_visited(irg)) || /* not yet visited */
1016 (old_nesting < current_nesting)) { /* propagate larger nesting */
1017 /* Don't walk the graph, but a tree that is an unfolded graph. */
1018 n_callees = get_irg_n_callees(irg);
1019 for (i = 0; i < n_callees; i++) {
1020 ir_graph *m = get_irg_callee(irg, i);
1021 *(int *)env += get_irg_callee_loop_depth(irg, i);
1022 compute_loop_depth(m, env);
1023 *(int *)env -= get_irg_callee_loop_depth(irg, i);
1027 set_cg_irg_visited(irg, master_cg_visited-1);
1030 /* ------------------------------------------------------------------------------------ */
1031 /* Another algorithm to compute recursion nesting depth */
1032 /* Walk the callgraph. For each crossed loop increase the nesting depth by one. */
1033 /* Assign graphs the maximal nesting depth. Don't increase if passing loops more than */
1035 /* ------------------------------------------------------------------------------------ */
1038 /* For callees, we want to remember the Call nodes, too. */
1039 typedef struct ana_entry2 {
1040 ir_loop **loop_stack; /**< a stack of ir_loop entries */
1041 int tos; /**< the top of stack entry */
1042 int recursion_nesting;
1046 * push a loop entry on the stack
1048 static void push2(ana_entry2 *e, ir_loop *g) {
1049 if (ARR_LEN(e->loop_stack) == e->tos) {
1050 ARR_APP1(ir_loop *, e->loop_stack, g);
1052 e->loop_stack[e->tos] = g;
1058 * returns the top of stack and pop it
1060 static ir_loop *pop2(ana_entry2 *e) {
1061 return e->loop_stack[--e->tos];
1065 * check if a loop g in on the stack. Did not check the TOS.
1067 static int in_stack(ana_entry2 *e, ir_loop *g) {
1069 for (i = e->tos-1; i >= 0; --i) {
1070 if (e->loop_stack[i] == g) return 1;
1075 static void compute_rec_depth (ir_graph *irg, void *env) {
1076 ana_entry2 *e = (ana_entry2 *)env;
1077 ir_loop *l = irg->l;
1078 int depth, old_depth = irg->callgraph_recursion_depth;
1082 if (cg_irg_visited(irg)) return;
1083 mark_cg_irg_visited(irg);
1085 /* -- compute and set the new nesting value -- */
1086 if ((l != irp->outermost_cg_loop) && !in_stack(e, l)) {
1088 e->recursion_nesting++;
1091 depth = e->recursion_nesting;
1093 if (old_depth < depth)
1094 irg->callgraph_recursion_depth = depth;
1096 if (depth > irp->max_callgraph_recursion_depth)
1097 irp->max_callgraph_recursion_depth = depth;
1099 /* -- spread the nesting value -- */
1100 if (depth == 0 || old_depth < depth) {
1101 /* Don't walk the graph, but a tree that is an unfolded graph.
1102 Therefore we unset the visited flag at the end. */
1103 n_callees = get_irg_n_callees(irg);
1104 for (i = 0; i < n_callees; i++) {
1105 ir_graph *m = get_irg_callee(irg, i);
1106 compute_rec_depth(m, env);
1110 /* -- clean up -- */
1113 e->recursion_nesting--;
1115 set_cg_irg_visited(irg, master_cg_visited-1);
1119 /* ----------------------------------------------------------------------------------- */
1120 /* Another algorithm to compute the execution frequency of methods ignoring recursions. */
1121 /* Walk the callgraph. Ignore backedges. Use sum of execution frequencies of Call */
1122 /* nodes to evaluate a callgraph edge. */
1123 /* ----------------------------------------------------------------------------------- */
1125 double get_irg_method_execution_frequency (ir_graph *irg) {
1126 return irg->method_execution_frequency;
1129 void set_irg_method_execution_frequency (ir_graph *irg, double freq) {
1130 irg->method_execution_frequency = freq;
1132 if (irp->max_method_execution_frequency < freq)
1133 irp->max_method_execution_frequency = freq;
1136 static void compute_method_execution_frequency (ir_graph *irg, void *env) {
1142 if (cg_irg_visited(irg)) return;
1144 /* We need the values of all predecessors (except backedges).
1145 So they must be marked. Else we will reach the node through
1146 one of the unmarked ones. */
1147 n_callers = get_irg_n_callers(irg);
1148 for (i = 0; i < n_callers; i++) {
1149 ir_graph *m = get_irg_caller(irg, i);
1150 if (is_irg_caller_backedge(irg, i)) continue;
1151 if (!cg_irg_visited(m)) {
1155 mark_cg_irg_visited(irg);
1157 /* Compute the new frequency. */
1160 for (i = 0; i < n_callers; i++) {
1161 if (! is_irg_caller_backedge(irg, i)) {
1162 double edge_freq = get_irg_caller_method_execution_frequency(irg, i);
1163 assert(edge_freq >= 0);
1170 /* A starting point: method only called from outside,
1171 or only backedges as predecessors. */
1175 set_irg_method_execution_frequency(irg, freq);
1178 n_callees = get_irg_n_callees(irg);
1179 for (i = 0; i < n_callees; i++) {
1180 compute_method_execution_frequency (get_irg_callee(irg, i), NULL);
1185 /* ----------------------------------------------------------------------------------- */
1186 /* The recursion stuff driver. */
1187 /* ----------------------------------------------------------------------------------- */
1189 /* Compute the backedges that represent recursions. */
1190 void find_callgraph_recursions(void) {
1191 int i, n_irgs = get_irp_n_irgs();
1195 /* -- compute the looptree. -- */
1197 /* The outermost graph. We start here. Then we start at all
1198 functions in irg list that are never called, then at the remaining
1199 unvisited ones. The third step is needed for functions that are not
1200 reachable from the outermost graph, but call themselves in a cycle. */
1201 assert(get_irp_main_irg());
1202 outermost_ir_graph = get_irp_main_irg();
1205 current_loop = NULL;
1206 new_loop(); /* sets current_loop */
1208 master_cg_visited++;
1209 cgscc(outermost_ir_graph);
1210 for (i = 0; i < n_irgs; i++) {
1211 ir_graph *irg = get_irp_irg(i);
1212 if (!cg_irg_visited(irg) && get_irg_n_callers(irg) == 0)
1215 for (i = 0; i < n_irgs; i++) {
1216 ir_graph *irg = get_irp_irg(i);
1217 if (!cg_irg_visited(irg))
1220 irp->outermost_cg_loop = current_loop;
1222 /* -- Reverse the backedge information. -- */
1223 for (i = 0; i < n_irgs; i++) {
1224 ir_graph *irg = get_irp_irg(i);
1225 int j, n_callees = get_irg_n_callees(irg);
1226 for (j = 0; j < n_callees; ++j) {
1227 if (is_irg_callee_backedge(irg, j))
1228 set_irg_caller_backedge(get_irg_callee(irg, j), irg);
1232 irp->callgraph_state = irp_callgraph_and_calltree_consistent;
1235 void compute_performance_estimates(void) {
1236 int i, n_irgs = get_irp_n_irgs();
1237 int current_nesting;
1240 /* -- compute the loop depth -- */
1241 current_nesting = 0;
1242 irp->max_callgraph_loop_depth = 0;
1243 master_cg_visited += 2;
1244 //printf (" ** starting at "); DDMG(get_irp_main_irg());
1245 compute_loop_depth(get_irp_main_irg(), ¤t_nesting);
1246 for (i = 0; i < n_irgs; i++) {
1247 ir_graph *irg = get_irp_irg(i);
1248 if ((get_cg_irg_visited(irg) < master_cg_visited-1) &&
1249 get_irg_n_callers(irg) == 0) {
1250 compute_loop_depth(irg, ¤t_nesting);
1251 //printf (" ** starting at "); DDMG(irg);
1254 for (i = 0; i < n_irgs; i++) {
1255 ir_graph *irg = get_irp_irg(i);
1256 if (get_cg_irg_visited(irg) < master_cg_visited-1) {
1257 compute_loop_depth(irg, ¤t_nesting);
1258 //printf (" ** starting at "); DDMG(irg);
1263 /* -- compute the recursion depth -- */
1264 e.loop_stack = NEW_ARR_F(ir_loop *, 0);
1266 e.recursion_nesting = 0;
1268 irp->max_callgraph_recursion_depth = 0;
1270 master_cg_visited += 2;
1271 compute_rec_depth(get_irp_main_irg(), &e);
1272 //printf (" ++ starting at "); DDMG(get_irp_main_irg());
1273 for (i = 0; i < n_irgs; i++) {
1274 ir_graph *irg = get_irp_irg(i);
1275 if ((get_cg_irg_visited(irg) < master_cg_visited-1) &&
1276 get_irg_n_callers(irg) == 0) {
1277 compute_rec_depth(irg, &e);
1278 //printf (" ++ starting at "); DDMG(irg);
1281 for (i = 0; i < n_irgs; i++) {
1282 ir_graph *irg = get_irp_irg(i);
1283 if (get_cg_irg_visited(irg) < master_cg_visited-1) {
1284 compute_rec_depth(irg, &e);
1285 //printf (" ++ starting at "); DDMG(irg);
1289 DEL_ARR_F(e.loop_stack);
1291 /* -- compute the execution frequency -- */
1292 irp->max_method_execution_frequency = 0;
1293 master_cg_visited += 2;
1294 assert(get_irg_n_callers(get_irp_main_irg()) == 0);
1295 compute_method_execution_frequency(get_irp_main_irg(), NULL);
1296 for (i = 0; i < n_irgs; i++) {
1297 ir_graph *irg = get_irp_irg(i);
1298 if ((get_cg_irg_visited(irg) < master_cg_visited-1) &&
1299 get_irg_n_callers(irg) == 0) {
1300 compute_method_execution_frequency(irg, NULL);
1303 for (i = 0; i < n_irgs; i++) {
1304 ir_graph *irg = get_irp_irg(i);
1305 if (get_cg_irg_visited(irg) < master_cg_visited-1) {
1306 compute_method_execution_frequency(irg, NULL);
1311 /* Maximal loop depth of all paths from an external visible method to
1313 int get_irg_loop_depth(ir_graph *irg) {
1314 assert(irp->callgraph_state == irp_callgraph_consistent ||
1315 irp->callgraph_state == irp_callgraph_and_calltree_consistent);
1316 return irg->callgraph_loop_depth;
1319 /* Maximal recursion depth of all paths from an external visible method to
1321 int get_irg_recursion_depth(ir_graph *irg) {
1322 assert(irp->callgraph_state == irp_callgraph_and_calltree_consistent);
1323 return irg->callgraph_recursion_depth;
1326 void analyse_loop_nesting_depth(void) {
1327 entity **free_methods = NULL;
1330 /* establish preconditions. */
1331 if (get_irp_callee_info_state() != irg_callee_info_consistent) {
1332 cgana(&arr_len, &free_methods);
1335 if (irp_callgraph_consistent != get_irp_callgraph_state()) {
1336 compute_callgraph();
1339 find_callgraph_recursions();
1341 compute_performance_estimates();
1343 set_irp_loop_nesting_depth_state(loop_nesting_depth_consistent);
1347 loop_nesting_depth_state get_irp_loop_nesting_depth_state(void) {
1348 return irp->lnd_state;
1350 void set_irp_loop_nesting_depth_state(loop_nesting_depth_state s) {
1353 void set_irp_loop_nesting_depth_state_inconsistent(void) {
1354 if (irp->lnd_state == loop_nesting_depth_consistent)
1355 irp->lnd_state = loop_nesting_depth_inconsistent;