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"
37 /* For callees, we want to remember the Call nodes, too. */
44 typedef struct ana_entry ana_entry;
46 static int master_cg_visited = 0;
47 static INLINE int cg_irg_visited (ir_graph *n);
48 static INLINE void mark_cg_irg_visited(ir_graph *n);
49 static INLINE void set_cg_irg_visited (ir_graph *n, int i);
51 irp_callgraph_state get_irp_callgraph_state(void) {
52 return irp->callgraph_state;
54 void set_irp_callgraph_state(irp_callgraph_state s) {
55 irp->callgraph_state = s;
58 /* The functions that call irg. */
59 int get_irg_n_callers(ir_graph *irg) {
60 if (irg->callers) return ARR_LEN(irg->callers);
63 ir_graph *get_irg_caller(ir_graph *irg, int pos) {
64 assert (pos >= 0 && pos < get_irg_n_callers(irg));
65 if (irg->callers) return irg->callers[pos];
68 int is_irg_caller_backedge(ir_graph *irg, int pos) {
69 assert (pos >= 0 && pos < get_irg_n_callers(irg));
70 return irg->caller_isbe[pos];
73 static void set_irg_caller_backedge(ir_graph *irg, ir_graph *caller) {
74 int i, n_callers = get_irg_n_callers(irg);
75 for (i = 0; i < n_callers; ++i) {
76 if (get_irg_caller(irg, i) == caller) {
77 irg->caller_isbe[i] = 1;
83 int has_irg_caller_backedge(ir_graph *irg) {
84 int i, n_callers = get_irg_n_callers(irg);
85 for (i = 0; i < n_callers; ++i)
86 if (is_irg_caller_backedge(irg, i)) return 1;
90 static int reverse_pos(ir_graph *callee, int pos_caller) {
91 ir_graph *caller = get_irg_caller(callee, pos_caller);
92 /* search the other relation for the corresponding edge. */
94 int i, n_callees = get_irg_n_callees(caller);
95 for (i = 0; i < n_callees; ++i) {
96 if (get_irg_callee(caller, i) == callee) {
102 assert(pos_callee >= 0);
107 int get_irg_caller_loop_depth(ir_graph *irg, int pos) {
108 ir_graph *caller = get_irg_caller(irg, pos);
109 int pos_callee = reverse_pos(irg, pos);
111 return get_irg_callee_loop_depth(caller, pos_callee);
115 /* The functions called by irg. */
116 int get_irg_n_callees(ir_graph *irg) {
117 if (irg->callees) return ARR_LEN(irg->callees);
120 ir_graph *get_irg_callee(ir_graph *irg, int pos) {
121 assert (pos >= 0 && pos < get_irg_n_callees(irg));
122 if (irg->callees) return ((ana_entry *)irg->callees[pos])->irg;
125 int is_irg_callee_backedge(ir_graph *irg, int pos) {
126 assert (pos >= 0 && pos < get_irg_n_callees(irg));
127 return irg->callee_isbe[pos];
129 int has_irg_callee_backedge(ir_graph *irg) {
130 int i, n_callees = get_irg_n_callees(irg);
131 for (i = 0; i < n_callees; ++i)
132 if (is_irg_callee_backedge(irg, i)) return 1;
135 void set_irg_callee_backedge(ir_graph *irg, int pos) {
136 assert (pos >= 0 && pos < get_irg_n_callees(irg));
137 irg->callee_isbe[pos] = 1;
140 int get_irg_callee_loop_depth(ir_graph *irg, int pos) {
141 assert (pos >= 0 && pos < get_irg_n_callees(irg));
142 if (irg->callees) return ((ana_entry *)irg->callees[pos])->max_depth;
148 double get_irg_callee_execution_freqency(ir_graph *irg, int pos) {
149 ir_node **arr = ((ana_entry *)irg->callees[pos])->call_list;
150 int i, n_Calls = ARR_LEN(arr);
153 for (i = 0; i < n_Calls; ++i) {
154 freq += get_irn_exec_freq(arr[i]);
159 double get_irg_callee_method_execution_freqency(ir_graph *irg, int pos) {
160 double call_freq = get_irg_callee_execution_freqency(irg, pos);
161 double meth_freq = get_irg_method_execution_frequency(irg);
162 return call_freq * meth_freq;
166 double get_irg_caller_method_execution_freqency(ir_graph *irg, int pos) {
167 ir_graph *caller = get_irg_caller(irg, pos);
168 int pos_callee = reverse_pos(irg, pos);
170 return get_irg_callee_method_execution_freqency(caller, pos_callee);
175 /* --------------------- Compute the callgraph ------------------------ */
177 /* Hash an address */
178 #define HASH_ADDRESS(adr) (((unsigned)(adr)) >> 3)
181 * Walker called by compute_callgraph()
183 static void ana_Call(ir_node *n, void *env) {
187 if (get_irn_op(n) != op_Call) return;
189 irg = get_irn_irg(n);
190 n_callees = get_Call_n_callees(n);
191 for (i = 0; i < n_callees; ++i) {
192 entity *callee_e = get_Call_callee(n, i);
193 ir_graph *callee = get_entity_irg(callee_e);
196 ana_entry buf = { callee, NULL, 0};
200 pset_insert((pset *)callee->callers, irg, (unsigned)irg >> 3);
201 found = pset_find((pset *)irg->callees, &buf, HASH_ADDRESS(callee));
202 if (found) { /* add Call node to list, compute new nesting. */
203 ir_node **arr = found->call_list;
204 ARR_APP1(ir_node *, arr, n);
205 found->call_list = arr;
206 } else { /* New node, add Call node and init nesting. */
207 found = (ana_entry *) obstack_alloc (irg->obst, sizeof (ana_entry));
209 found->call_list = NEW_ARR_F(ir_node *, 1);
210 found->call_list[0] = n;
211 found->max_depth = 0;
212 pset_insert((pset *)irg->callees, found, HASH_ADDRESS(callee));
214 depth = get_loop_depth(get_irn_loop(get_nodes_block(n)));
215 found->max_depth = (depth > found->max_depth) ? depth : found->max_depth;
220 /** compare two ir graphs in a ana_entry */
221 static int ana_entry_cmp(const void *elt, const void *key) {
222 const ana_entry *e1 = elt;
223 const ana_entry *e2 = key;
224 return e1->irg != e2->irg;
227 /** compare two ir graphs */
228 static int graph_cmp(const void *elt, const void *key) {
233 /* Construct and destruct the callgraph. */
234 void compute_callgraph(void) {
235 int i, n_irgs = get_irp_n_irgs();
237 assert(! get_interprocedural_view()); /* Else walking will not reach the Call nodes. */
241 for (i = 0; i < n_irgs; ++i) {
242 ir_graph *irg = get_irp_irg(i);
243 assert(get_irg_callee_info_state(irg) == irg_callee_info_consistent);
244 irg->callees = (ir_graph **)new_pset(ana_entry_cmp, 8);
245 irg->callers = (ir_graph **)new_pset(graph_cmp, 8);
246 //construct_cf_backedges(irg);
249 /* Compute the call graph */
250 for (i = 0; i < n_irgs; ++i) {
251 ir_graph *irg = get_irp_irg(i);
252 construct_cf_backedges(irg); // We also find the maximal loop depth of a call.
253 irg_walk_graph(irg, ana_Call, NULL, NULL);
256 /* Change the sets to arrays. */
257 for (i = 0; i < n_irgs; ++i) {
259 ir_graph *c, *irg = get_irp_irg(i);
260 pset *callee_set, *caller_set;
262 callee_set = (pset *)irg->callees;
263 count = pset_count(callee_set);
264 irg->callees = NEW_ARR_F(ir_graph *, count);
265 irg->callee_isbe = xcalloc(count, sizeof(irg->callee_isbe[0]));
266 c = pset_first(callee_set);
267 for (j = 0; j < count; ++j) {
269 c = pset_next(callee_set);
271 del_pset(callee_set);
274 caller_set = (pset *)irg->callers;
275 count = pset_count(caller_set);
276 irg->callers = NEW_ARR_F(ir_graph *, count);
277 irg->caller_isbe = xcalloc(count, sizeof(irg->caller_isbe[0]));
278 c = pset_first(caller_set);
279 for (j = 0; j < count; ++j) {
281 c = pset_next(caller_set);
283 del_pset(caller_set);
286 set_irp_callgraph_state(irp_callgraph_consistent);
289 void free_callgraph(void) {
290 int i, n_irgs = get_irp_n_irgs();
291 for (i = 0; i < n_irgs; ++i) {
292 ir_graph *irg = get_irp_irg(i);
293 if (irg->callees) DEL_ARR_F(irg->callees);
294 if (irg->callers) DEL_ARR_F(irg->callers);
295 if (irg->callee_isbe) free(irg->callee_isbe);
296 if (irg->caller_isbe) free(irg->caller_isbe);
299 irg->callee_isbe = NULL;
300 irg->caller_isbe = NULL;
302 set_irp_callgraph_state(irp_callgraph_none);
305 /* ----------------------------------------------------------------------------------- */
306 /* A walker for the callgraph */
307 /* ----------------------------------------------------------------------------------- */
310 static void do_walk(ir_graph *irg, callgraph_walk_func *pre, callgraph_walk_func *post, void *env) {
313 if (cg_irg_visited(irg)) return;
314 mark_cg_irg_visited(irg);
318 n_callees = get_irg_n_callees(irg);
319 for (i = 0; i < n_callees; i++) {
320 ir_graph *m = get_irg_callee(irg, i);
321 do_walk(m, pre, post, env);
327 void callgraph_walk(callgraph_walk_func *pre, callgraph_walk_func *post, void *env) {
328 int i, n_irgs = get_irp_n_irgs();
331 do_walk(get_irp_main_irg(), pre, post, env);
332 for (i = 0; i < n_irgs; i++) {
333 ir_graph *irg = get_irp_irg(i);
334 if (!cg_irg_visited(irg) && get_irg_n_callers(irg) == 0)
335 do_walk(irg, pre, post, env);
337 for (i = 0; i < n_irgs; i++) {
338 ir_graph *irg = get_irp_irg(i);
339 if (!cg_irg_visited(irg))
340 do_walk(irg, pre, post, env);
344 /* ----------------------------------------------------------------------------------- */
345 /* loop construction algorithm */
346 /* ----------------------------------------------------------------------------------- */
348 static ir_graph *outermost_ir_graph; /**< The outermost graph the scc is computed
350 static ir_loop *current_loop; /**< Current cfloop construction is working
352 static int loop_node_cnt = 0; /**< Counts the number of allocated cfloop nodes.
353 Each cfloop node gets a unique number.
354 What for? ev. remove. @@@ */
355 static int current_dfn = 1; /**< Counter to generate depth first numbering
359 /**********************************************************************/
360 /* Node attributes **/
361 /**********************************************************************/
363 typedef struct scc_info {
364 bool in_stack; /**< Marks whether node is on the stack. */
365 int dfn; /**< Depth first search number. */
366 int uplink; /**< dfn number of ancestor. */
371 * allocates a new scc_info of the obstack
373 static INLINE scc_info *new_scc_info(void) {
374 scc_info *info = obstack_alloc (outermost_ir_graph->obst, sizeof(*info));
375 memset(info, 0, sizeof(*info));
380 cg_irg_visited(ir_graph *n) {
381 scc_info *info = get_irg_link(n);
382 return (info->visited >= master_cg_visited);
386 mark_cg_irg_visited(ir_graph *n) {
387 scc_info *info = get_irg_link(n);
388 info->visited = master_cg_visited;
392 set_cg_irg_visited(ir_graph *n, int i) {
393 scc_info *info = get_irg_link(n);
398 get_cg_irg_visited(ir_graph *n) {
399 scc_info *info = get_irg_link(n);
400 return info->visited;
404 mark_irg_in_stack (ir_graph *n) {
405 scc_info *info = get_irg_link(n);
407 info->in_stack = true;
411 mark_irg_not_in_stack (ir_graph *n) {
412 scc_info *info = get_irg_link(n);
414 info->in_stack = false;
418 irg_is_in_stack (ir_graph *n) {
419 scc_info *info = get_irg_link(n);
421 return info->in_stack;
425 set_irg_uplink (ir_graph *n, int uplink) {
426 scc_info *info = get_irg_link(n);
428 info->uplink = uplink;
432 get_irg_uplink (ir_graph *n) {
433 scc_info *info = get_irg_link(n);
439 set_irg_dfn (ir_graph *n, int dfn) {
440 scc_info *info = get_irg_link(n);
446 get_irg_dfn (ir_graph *n) {
447 scc_info *info = get_irg_link(n);
452 /**********************************************************************/
454 /**********************************************************************/
456 static ir_graph **stack = NULL;
457 static int tos = 0; /**< top of stack */
460 * initialize the irg stack
462 static INLINE void init_stack(void) {
464 ARR_RESIZE (ir_graph *, stack, 1000);
466 stack = NEW_ARR_F (ir_graph *, 1000);
472 * push a graph on the irg stack
473 * @param n the graph to be pushed
478 if (tos == ARR_LEN (stack)) {
479 int nlen = ARR_LEN (stack) * 2;
480 ARR_RESIZE (ir_node *, stack, nlen);
483 mark_irg_in_stack(n);
487 * return the topmost graph on the stack and pop it
489 static INLINE ir_graph *
492 ir_graph *n = stack[--tos];
493 mark_irg_not_in_stack(n);
498 * The nodes up to n belong to the current loop.
499 * Removes them from the stack and adds them to the current loop.
502 pop_scc_to_loop (ir_graph *n)
509 set_irg_dfn(m, loop_node_cnt);
510 add_loop_node(current_loop, (ir_node *)m);
512 //m->callgraph_loop_depth = current_loop->depth;
516 /* GL ??? my last son is my grandson??? Removes cfloops with no
517 ir_nodes in them. Such loops have only another loop as son. (Why
518 can't they have two loops as sons? Does it never get that far? ) */
519 static void close_loop (ir_loop *l)
521 int last = get_loop_n_elements(l) - 1;
522 loop_element lelement = get_loop_element(l, last);
523 ir_loop *last_son = lelement.son;
525 if (get_kind(last_son) == k_ir_loop &&
526 get_loop_n_elements(last_son) == 1) {
529 lelement = get_loop_element(last_son, 0);
531 if(get_kind(gson) == k_ir_loop) {
532 loop_element new_last_son;
534 gson -> outer_loop = l;
535 new_last_son.son = gson;
536 l -> children[last] = new_last_son;
544 * Removes and unmarks all nodes up to n from the stack.
545 * The nodes must be visited once more to assign them to a scc.
548 pop_scc_unmark_visit (ir_graph *n)
554 set_cg_irg_visited(m, 0);
558 /**********************************************************************/
559 /* The loop data structure. **/
560 /**********************************************************************/
563 * Allocates a new loop as son of current_loop. Sets current_loop
564 * to the new loop and returns the father.
566 static ir_loop *new_loop (void) {
567 ir_loop *father, *son;
569 father = current_loop;
571 son = obstack_alloc (outermost_ir_graph->obst, sizeof(*son));
572 memset (son, 0, sizeof(*son));
573 son->kind = k_ir_loop;
574 son->children = NEW_ARR_F (loop_element, 0);
578 son->outer_loop = father;
579 add_loop_son(father, son);
580 son->depth = father->depth + 1;
581 } else { /* The root loop */
582 son->outer_loop = son;
587 son->loop_nr = get_irp_new_node_nr();
595 /**********************************************************************/
596 /* Constructing and destructing the loop/backedge information. **/
597 /**********************************************************************/
599 /* Initialization steps. **********************************************/
610 n_irgs = get_irp_n_irgs();
611 for (i = 0; i < n_irgs; ++i) {
612 ir_graph *irg = get_irp_irg(i);
613 set_irg_link(irg, new_scc_info());
614 irg->callgraph_recursion_depth = 0;
615 irg->callgraph_loop_depth = 0;
619 /** Returns true if n is a loop header, i.e., it is a Block node
620 * and has predecessors within the cfloop and out of the cfloop.
622 * @param root: only needed for assertion.
625 is_head (ir_graph *n, ir_graph *root)
628 int some_outof_loop = 0, some_in_loop = 0;
630 arity = get_irg_n_callees(n);
631 for (i = 0; i < arity; i++) {
632 ir_graph *pred = get_irg_callee(n, i);
633 if (is_irg_callee_backedge(n, i)) continue;
634 if (!irg_is_in_stack(pred)) {
637 if (get_irg_uplink(pred) < get_irg_uplink(root)) {
638 DDMG(pred); DDMG(root);
639 assert(get_irg_uplink(pred) >= get_irg_uplink(root));
645 return some_outof_loop & some_in_loop;
649 * Returns true if n is possible loop head of an endless loop.
650 * I.e., it is a Block, Phi or Filter node and has only predecessors
652 * @arg root: only needed for assertion.
655 is_endless_head (ir_graph *n, ir_graph *root)
658 int some_outof_loop = 0, some_in_loop = 0;
660 arity = get_irg_n_callees(n);
661 for (i = 0; i < arity; i++) {
662 ir_graph *pred = get_irg_callee(n, i);
664 if (is_irg_callee_backedge(n, i)) { continue; }
665 if (!irg_is_in_stack(pred)) {
668 if(get_irg_uplink(pred) < get_irg_uplink(root)) {
669 DDMG(pred); DDMG(root);
670 assert(get_irg_uplink(pred) >= get_irg_uplink(root));
676 return !some_outof_loop & some_in_loop;
681 * Check whether there is a parallel edge in the ip control flow.
685 is_ip_head (ir_graph *n, ir_graph *pred)
688 int iv_rem = get_interprocedural_view();
689 set_interprocedural_view(true);
691 ir_node *sblock = get_irg_start_block(n);
692 int i, arity = get_Block_n_cfgpreds(sblock);
694 //printf(" edge from "); DDMG(n);
695 //printf(" to pred "); DDMG(pred);
696 //printf(" sblock "); DDMN(sblock);
698 for (i = 0; i < arity; i++) {
699 ir_node *pred_cfop = skip_Proj(get_Block_cfgpred(sblock, i));
700 //printf(" "); DDMN(pred_cfop);
701 if (get_irn_op(pred_cfop) == op_CallBegin) { /* could be Unknown */
702 ir_graph *ip_pred = get_irn_irg(pred_cfop);
703 //printf(" "); DDMG(ip_pred);
704 if ((ip_pred == pred) && is_backedge(sblock, i)) {
705 //printf(" found\n");
711 set_interprocedural_view(iv_rem);
716 * Returns index of the predecessor with the smallest dfn number
717 * greater-equal than limit.
720 smallest_dfn_pred (ir_graph *n, int limit)
722 int i, index = -2, min = -1;
724 int arity = get_irg_n_callees(n);
725 for (i = 0; i < arity; i++) {
726 ir_graph *pred = get_irg_callee(n, i);
727 if (is_irg_callee_backedge(n, i) || !irg_is_in_stack(pred)) continue;
728 if (get_irg_dfn(pred) >= limit && (min == -1 || get_irg_dfn(pred) < min)) {
730 min = get_irg_dfn(pred);
737 /** Returns index of the predecessor with the largest dfn number. */
739 largest_dfn_pred (ir_graph *n)
741 int i, index = -2, max = -1;
743 int arity = get_irg_n_callees(n);
744 for (i = 0; i < arity; i++) {
745 ir_graph *pred = get_irg_callee(n, i);
746 if (is_irg_callee_backedge (n, i) || !irg_is_in_stack(pred)) continue;
747 if (get_irg_dfn(pred) > max) {
749 max = get_irg_dfn(pred);
758 find_tail (ir_graph *n) {
760 int i, res_index = -2;
763 if (!icfg && rm_cyclic_phis && remove_cyclic_phis (n)) return NULL;
765 m = stack[tos-1]; /* tos = top of stack */
766 if (is_head (m, n)) {
767 res_index = smallest_dfn_pred(m, 0);
768 if ((res_index == -2) && /* no smallest dfn pred found. */
772 if (m == n) return NULL; // Is this to catch Phi - self loops?
773 for (i = tos-2; i >= 0; --i) {
776 if (is_head (m, n)) {
777 res_index = smallest_dfn_pred (m, get_irg_dfn(m) + 1);
778 if (res_index == -2) /* no smallest dfn pred found. */
779 res_index = largest_dfn_pred (m);
781 if ((m == n) && (res_index == -2)) {
787 /* We should not walk past our selves on the stack: The upcoming nodes
788 are not in this loop. We assume a loop not reachable from Start. */
797 /* A dead loop not reachable from Start. */
798 for (i = tos-2; i >= 0; --i) {
800 if (is_endless_head (m, n)) {
801 res_index = smallest_dfn_pred (m, get_irg_dfn(m) + 1);
802 if (res_index == -2) /* no smallest dfn pred found. */
803 res_index = largest_dfn_pred (m);
806 if (m == n) { break; } /* It's not an unreachable loop, either. */
808 //assert(0 && "no head found on stack");
812 assert (res_index > -2);
814 set_irg_callee_backedge (m, res_index);
815 return get_irg_callee(m, res_index);
819 find_tail (ir_graph *n) {
821 int i, res_index = -2;
824 ir_graph *in_and_out = NULL;
825 ir_graph *only_in = NULL;
826 ir_graph *ip_in_and_out = NULL;
827 ir_graph *ip_only_in = NULL;
829 //printf("find tail for "); DDMG(n);
831 for (i = tos-1; i >= 0; --i) {
832 ir_graph *pred = (i < tos -1) ? stack[i+1] : n;
835 if (is_head (m, n)) {
836 //printf(" found 1a! "); DDM;
838 if (is_ip_head(pred, m)) {
839 //printf(" found 1b! "); DDM;
842 } else if (!ip_only_in && is_endless_head(m, n)) {
844 //printf(" found 2a! "); DDM;
845 if (is_ip_head(pred, m)) {
846 //printf(" found 2b! "); DDM;
849 } else if (is_ip_head(pred, m)) {
850 //printf(" found 3! "); DDM; This happens for self recursions in the second
851 //assert(0); scc iteration (the one to flip the loop.)
854 if (ip_in_and_out) break; /* That's what we really want. */
856 if (m == n) break; /* Don't walk past n on the stack! */
860 if (!in_and_out && !only_in)
861 /* There is no loop */
865 /* Is there a head in the callgraph without a head in the
867 assert(in_and_out || only_in);
869 m = (ip_in_and_out) ? ip_in_and_out : ip_only_in;
872 m = (in_and_out) ? in_and_out : only_in;
874 //printf("*** head is "); DDMG(m);
876 res_index = smallest_dfn_pred (m, get_irg_dfn(m) + 1);
877 if (res_index == -2) /* no smallest dfn pred found. */
878 res_index = largest_dfn_pred (m);
880 set_irg_callee_backedge (m, res_index);
881 res = get_irg_callee(m, res_index);
882 //printf("*** tail is "); DDMG(res);
888 /*-----------------------------------------------------------*
889 * The core algorithm. *
890 *-----------------------------------------------------------*/
893 static void cgscc (ir_graph *n) {
896 if (cg_irg_visited(n)) return;
897 mark_cg_irg_visited(n);
899 /* Initialize the node */
900 set_irg_dfn(n, current_dfn); /* Depth first number for this node */
901 set_irg_uplink(n, current_dfn); /* ... is default uplink. */
905 arity = get_irg_n_callees(n);
906 for (i = 0; i < arity; i++) {
908 if (is_irg_callee_backedge(n, i)) continue;
909 m = get_irg_callee(n, i);
911 /** This marks the backedge, but does it guarantee a correct loop tree? */
912 //if (m == n) { set_irg_callee_backedge(n, i); continue; }
915 if (irg_is_in_stack(m)) {
916 /* Uplink of m is smaller if n->m is a backedge.
917 Propagate the uplink to mark the cfloop. */
918 if (get_irg_uplink(m) < get_irg_uplink(n))
919 set_irg_uplink(n, get_irg_uplink(m));
923 if (get_irg_dfn(n) == get_irg_uplink(n)) {
924 /* This condition holds for
925 1) the node with the incoming backedge.
926 That is: We found a cfloop!
927 2) Straight line code, because no uplink has been propagated, so the
928 uplink still is the same as the dfn.
930 But n might not be a proper cfloop head for the analysis. Proper cfloop
931 heads are Block and Phi nodes. find_tail searches the stack for
932 Block's and Phi's and takes those nodes as cfloop heads for the current
933 cfloop instead and marks the incoming edge as backedge. */
935 ir_graph *tail = find_tail(n);
937 /* We have a cfloop, that is no straight line code,
938 because we found a cfloop head!
939 Next actions: Open a new cfloop on the cfloop tree and
940 try to find inner cfloops */
943 ir_loop *l = new_loop();
945 /* Remove the cfloop from the stack ... */
946 pop_scc_unmark_visit (n);
948 /* The current backedge has been marked, that is temporarily eliminated,
949 by find tail. Start the scc algorithm
950 anew on the subgraph thats left (the current cfloop without the backedge)
951 in order to find more inner cfloops. */
955 assert (cg_irg_visited(n));
965 * reset the backedge information for all callers in all irgs
967 static void reset_isbe(void) {
968 int i, n_irgs = get_irp_n_irgs();
970 for (i = 0; i < n_irgs; ++i) {
972 ir_graph *irg = get_irp_irg(i);
974 n_cs = get_irg_n_callers(irg);
975 for (j = 0; j < n_cs; ++j) {
976 irg->caller_isbe[j] = 0;
979 n_cs = get_irg_n_callees(irg);
980 for (j = 0; j < n_cs; ++j) {
981 irg->callee_isbe[j] = 0;
989 /* ----------------------------------------------------------------------------------- */
990 /* Another algorithm to compute recursion nesting depth */
991 /* Walk the callgraph. For each crossed edge increase the loop depth by the edge */
992 /* weight. Assign graphs the maximal depth. */
993 /* ----------------------------------------------------------------------------------- */
995 static void compute_loop_depth (ir_graph *irg, void *env) {
996 int current_nesting = *(int *) env;
997 int old_nesting = irg->callgraph_loop_depth;
998 int old_visited = get_cg_irg_visited(irg);
1003 if (cg_irg_visited(irg)) return;
1005 mark_cg_irg_visited(irg);
1007 //printf(" old: %d new %d master %d", old_visited, get_cg_irg_visited(irg), master_cg_visited); DDMG(irg);
1010 if (old_nesting < current_nesting)
1011 irg->callgraph_loop_depth = current_nesting;
1013 if (current_nesting > irp->max_callgraph_loop_depth)
1014 irp->max_callgraph_loop_depth = current_nesting;
1016 if ((old_visited +1 < get_cg_irg_visited(irg)) || /* not yet visited */
1017 (old_nesting < current_nesting)) { /* propagate larger nesting */
1018 /* Don't walk the graph, but a tree that is an unfolded graph. */
1019 n_callees = get_irg_n_callees(irg);
1020 for (i = 0; i < n_callees; i++) {
1021 ir_graph *m = get_irg_callee(irg, i);
1022 *(int *)env += get_irg_callee_loop_depth(irg, i);
1023 compute_loop_depth(m, env);
1024 *(int *)env -= get_irg_callee_loop_depth(irg, i);
1028 set_cg_irg_visited(irg, master_cg_visited-1);
1031 /* ------------------------------------------------------------------------------------ */
1032 /* Another algorithm to compute recursion nesting depth */
1033 /* Walk the callgraph. For each crossed loop increase the nesting depth by one. */
1034 /* Assign graphs the maximal nesting depth. Don't increase if passing loops more than */
1036 /* ------------------------------------------------------------------------------------ */
1039 /* For callees, we want to remember the Call nodes, too. */
1040 typedef struct ana_entry2 {
1041 ir_loop **loop_stack; /**< a stack of ir_loop entries */
1042 int tos; /**< the top of stack entry */
1043 int recursion_nesting;
1047 * push a loop entry on the stack
1049 static void push2(ana_entry2 *e, ir_loop *g) {
1050 if (ARR_LEN(e->loop_stack) == e->tos) {
1051 ARR_APP1(ir_loop *, e->loop_stack, g);
1053 e->loop_stack[e->tos] = g;
1059 * returns the top of stack and pop it
1061 static ir_loop *pop2(ana_entry2 *e) {
1062 return e->loop_stack[--e->tos];
1066 * check if a loop g in on the stack. Did not check the TOS.
1068 static int in_stack(ana_entry2 *e, ir_loop *g) {
1070 for (i = e->tos-1; i >= 0; --i) {
1071 if (e->loop_stack[i] == g) return 1;
1076 static void compute_rec_depth (ir_graph *irg, void *env) {
1077 ana_entry2 *e = (ana_entry2 *)env;
1078 ir_loop *l = irg->l;
1079 int depth, old_depth = irg->callgraph_recursion_depth;
1083 if (cg_irg_visited(irg)) return;
1084 mark_cg_irg_visited(irg);
1086 /* -- compute and set the new nesting value -- */
1087 if ((l != irp->outermost_cg_loop) && !in_stack(e, l)) {
1089 e->recursion_nesting++;
1092 depth = e->recursion_nesting;
1094 if (old_depth < depth)
1095 irg->callgraph_recursion_depth = depth;
1097 if (depth > irp->max_callgraph_recursion_depth)
1098 irp->max_callgraph_recursion_depth = depth;
1100 /* -- spread the nesting value -- */
1101 if (depth == 0 || old_depth < depth) {
1102 /* Don't walk the graph, but a tree that is an unfolded graph.
1103 Therefore we unset the visited flag at the end. */
1104 n_callees = get_irg_n_callees(irg);
1105 for (i = 0; i < n_callees; i++) {
1106 ir_graph *m = get_irg_callee(irg, i);
1107 compute_rec_depth(m, env);
1111 /* -- clean up -- */
1114 e->recursion_nesting--;
1116 set_cg_irg_visited(irg, master_cg_visited-1);
1120 /* ----------------------------------------------------------------------------------- */
1121 /* Another algorithm to compute the execution freqency of methods ignoring recursions. */
1122 /* Walk the callgraph. Ignore backedges. Use sum of execution freqencies of Call */
1123 /* nodes to evaluate a callgraph edge. */
1124 /* ----------------------------------------------------------------------------------- */
1126 double get_irg_method_execution_frequency (ir_graph *irg) {
1127 return irg->method_execution_frequency;
1130 void set_irg_method_execution_frequency (ir_graph *irg, double freq) {
1131 irg->method_execution_frequency = freq;
1133 if (irp->max_method_execution_frequency < freq)
1134 irp->max_method_execution_frequency = freq;
1137 static void compute_method_execution_frequency (ir_graph *irg, void *env) {
1143 if (cg_irg_visited(irg)) return;
1145 /* We need the values of all predecessors (except backedges).
1146 So they must be marked. Else we will reach the node through
1147 one of the unmarked ones. */
1148 n_callers = get_irg_n_callers(irg);
1149 for (i = 0; i < n_callers; i++) {
1150 ir_graph *m = get_irg_caller(irg, i);
1151 if (is_irg_caller_backedge(irg, i)) continue;
1152 if (!cg_irg_visited(m)) {
1156 mark_cg_irg_visited(irg);
1158 /* Compute the new freqency. */
1161 for (i = 0; i < n_callers; i++) {
1162 if (! is_irg_caller_backedge(irg, i)) {
1163 double edge_freq = get_irg_caller_method_execution_freqency(irg, i);
1164 assert(edge_freq >= 0);
1171 /* A starting point: method only called from outside,
1172 or only backedges as predecessors. */
1176 set_irg_method_execution_frequency(irg, freq);
1179 n_callees = get_irg_n_callees(irg);
1180 for (i = 0; i < n_callees; i++) {
1181 compute_method_execution_frequency (get_irg_callee(irg, i), NULL);
1186 /* ----------------------------------------------------------------------------------- */
1187 /* The recursion stuff driver. */
1188 /* ----------------------------------------------------------------------------------- */
1190 /* Compute the backedges that represent recursions. */
1191 void find_callgraph_recursions(void) {
1192 int i, n_irgs = get_irp_n_irgs();
1196 /* -- compute the looptree. -- */
1198 /* The outermost graph. We start here. Then we start at all
1199 functions in irg list that are never called, then at the remaining
1200 unvisited ones. The third step is needed for functions that are not
1201 reachable from the outermost graph, but call themselves in a cycle. */
1202 assert(get_irp_main_irg());
1203 outermost_ir_graph = get_irp_main_irg();
1206 current_loop = NULL;
1207 new_loop(); /* sets current_loop */
1209 master_cg_visited++;
1210 cgscc(outermost_ir_graph);
1211 for (i = 0; i < n_irgs; i++) {
1212 ir_graph *irg = get_irp_irg(i);
1213 if (!cg_irg_visited(irg) && get_irg_n_callers(irg) == 0)
1216 for (i = 0; i < n_irgs; i++) {
1217 ir_graph *irg = get_irp_irg(i);
1218 if (!cg_irg_visited(irg))
1221 irp->outermost_cg_loop = current_loop;
1223 /* -- Reverse the backedge information. -- */
1224 for (i = 0; i < n_irgs; i++) {
1225 ir_graph *irg = get_irp_irg(i);
1226 int j, n_callees = get_irg_n_callees(irg);
1227 for (j = 0; j < n_callees; ++j) {
1228 if (is_irg_callee_backedge(irg, j))
1229 set_irg_caller_backedge(get_irg_callee(irg, j), irg);
1233 irp->callgraph_state = irp_callgraph_and_calltree_consistent;
1236 void compute_performance_estimates(void) {
1237 int i, n_irgs = get_irp_n_irgs();
1238 int current_nesting;
1241 /* -- compute the loop depth -- */
1242 current_nesting = 0;
1243 irp->max_callgraph_loop_depth = 0;
1244 master_cg_visited += 2;
1245 //printf (" ** starting at "); DDMG(get_irp_main_irg());
1246 compute_loop_depth(get_irp_main_irg(), ¤t_nesting);
1247 for (i = 0; i < n_irgs; i++) {
1248 ir_graph *irg = get_irp_irg(i);
1249 if ((get_cg_irg_visited(irg) < master_cg_visited-1) &&
1250 get_irg_n_callers(irg) == 0) {
1251 compute_loop_depth(irg, ¤t_nesting);
1252 //printf (" ** starting at "); DDMG(irg);
1255 for (i = 0; i < n_irgs; i++) {
1256 ir_graph *irg = get_irp_irg(i);
1257 if (get_cg_irg_visited(irg) < master_cg_visited-1) {
1258 compute_loop_depth(irg, ¤t_nesting);
1259 //printf (" ** starting at "); DDMG(irg);
1264 /* -- compute the recursion depth -- */
1265 e.loop_stack = NEW_ARR_F(ir_loop *, 0);
1267 e.recursion_nesting = 0;
1269 irp->max_callgraph_recursion_depth = 0;
1271 master_cg_visited += 2;
1272 compute_rec_depth(get_irp_main_irg(), &e);
1273 //printf (" ++ starting at "); DDMG(get_irp_main_irg());
1274 for (i = 0; i < n_irgs; i++) {
1275 ir_graph *irg = get_irp_irg(i);
1276 if ((get_cg_irg_visited(irg) < master_cg_visited-1) &&
1277 get_irg_n_callers(irg) == 0) {
1278 compute_rec_depth(irg, &e);
1279 //printf (" ++ starting at "); DDMG(irg);
1282 for (i = 0; i < n_irgs; i++) {
1283 ir_graph *irg = get_irp_irg(i);
1284 if (get_cg_irg_visited(irg) < master_cg_visited-1) {
1285 compute_rec_depth(irg, &e);
1286 //printf (" ++ starting at "); DDMG(irg);
1290 DEL_ARR_F(e.loop_stack);
1292 /* -- compute the execution frequency -- */
1293 irp->max_method_execution_frequency = 0;
1294 master_cg_visited += 2;
1295 assert(get_irg_n_callers(get_irp_main_irg()) == 0);
1296 compute_method_execution_frequency(get_irp_main_irg(), NULL);
1297 for (i = 0; i < n_irgs; i++) {
1298 ir_graph *irg = get_irp_irg(i);
1299 if ((get_cg_irg_visited(irg) < master_cg_visited-1) &&
1300 get_irg_n_callers(irg) == 0) {
1301 compute_method_execution_frequency(irg, NULL);
1304 for (i = 0; i < n_irgs; i++) {
1305 ir_graph *irg = get_irp_irg(i);
1306 if (get_cg_irg_visited(irg) < master_cg_visited-1) {
1307 compute_method_execution_frequency(irg, NULL);
1312 /* Maximal loop depth of all paths from an external visible method to
1314 int get_irg_loop_depth(ir_graph *irg) {
1315 assert(irp->callgraph_state == irp_callgraph_consistent ||
1316 irp->callgraph_state == irp_callgraph_and_calltree_consistent);
1317 return irg->callgraph_loop_depth;
1320 /* Maximal recursion depth of all paths from an external visible method to
1322 int get_irg_recursion_depth(ir_graph *irg) {
1323 assert(irp->callgraph_state == irp_callgraph_and_calltree_consistent);
1324 return irg->callgraph_recursion_depth;
1327 void analyse_loop_nesting_depth(void) {
1328 entity **free_methods = NULL;
1331 /* establish preconditions. */
1332 if (get_irp_callee_info_state() != irg_callee_info_consistent) {
1333 cgana(&arr_len, &free_methods);
1336 if (irp_callgraph_consistent != get_irp_callgraph_state()) {
1337 compute_callgraph();
1340 find_callgraph_recursions();
1342 compute_performance_estimates();
1344 set_irp_loop_nesting_depth_state(loop_nesting_depth_consistent);
1348 loop_nesting_depth_state get_irp_loop_nesting_depth_state(void) {
1349 return irp->lnd_state;
1351 void set_irp_loop_nesting_depth_state(loop_nesting_depth_state s) {
1354 void set_irp_loop_nesting_depth_state_inconsistent(void) {
1355 if (irp->lnd_state == loop_nesting_depth_consistent)
1356 irp->lnd_state = loop_nesting_depth_inconsistent;