3 * File name: ir/ana/callgraph.c
4 * Purpose: Representation and computation of the callgraph.
5 * Author: Goetz Lindenmaier
9 * Copyright: (c) 2004-2007 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 static int master_cg_visited = 0;
40 static INLINE int cg_irg_visited (ir_graph *n);
41 static INLINE void mark_cg_irg_visited(ir_graph *n);
42 static INLINE void set_cg_irg_visited (ir_graph *n, int i);
44 /** Returns the callgraph state of the program representation. */
45 irp_callgraph_state get_irp_callgraph_state(void) {
46 return irp->callgraph_state;
49 /* Sets the callgraph state of the program representation. */
50 void set_irp_callgraph_state(irp_callgraph_state s) {
51 irp->callgraph_state = s;
54 /* Returns the number of procedures that call the given irg. */
55 int get_irg_n_callers(ir_graph *irg) {
56 if (irg->callers) return ARR_LEN(irg->callers);
60 /* Returns the caller at position pos. */
61 ir_graph *get_irg_caller(ir_graph *irg, int pos) {
62 assert (pos >= 0 && pos < get_irg_n_callers(irg));
63 if (irg->callers) return irg->callers[pos];
67 /* Returns non-zero if the caller at position pos is "a backedge", i.e. a recursion. */
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 != NULL ? irg->caller_isbe[pos] : 0;
73 /** Search the caller in the list of all callers and set it's backedge property. */
74 static void set_irg_caller_backedge(ir_graph *irg, ir_graph *caller) {
75 int i, n_callers = get_irg_n_callers(irg);
77 /* allocate a new array on demand */
78 if (irg->caller_isbe == NULL)
79 irg->caller_isbe = xcalloc(n_callers, sizeof(irg->caller_isbe[0]));
80 for (i = 0; i < n_callers; ++i) {
81 if (get_irg_caller(irg, i) == caller) {
82 irg->caller_isbe[i] = 1;
88 /* Returns non-zero if the irg has a backedge caller. */
89 int has_irg_caller_backedge(ir_graph *irg) {
90 int i, n_callers = get_irg_n_callers(irg);
92 if (irg->caller_isbe != NULL) {
93 for (i = 0; i < n_callers; ++i)
94 if (irg->caller_isbe[i]) return 1;
100 * Find the reversion position of a caller.
101 * Given the position pos_caller of an caller of irg, return
102 * irg's callee position on that caller.
104 static int reverse_pos(ir_graph *callee, int pos_caller) {
105 ir_graph *caller = get_irg_caller(callee, pos_caller);
106 /* search the other relation for the corresponding edge. */
108 int i, n_callees = get_irg_n_callees(caller);
109 for (i = 0; i < n_callees; ++i) {
110 if (get_irg_callee(caller, i) == callee) {
116 assert(pos_callee >= 0);
121 /* Returns the maximal loop depth of call nodes that call along this edge. */
122 int get_irg_caller_loop_depth(ir_graph *irg, int pos) {
123 ir_graph *caller = get_irg_caller(irg, pos);
124 int pos_callee = reverse_pos(irg, pos);
126 return get_irg_callee_loop_depth(caller, pos_callee);
130 /* Returns the number of procedures that are called by the given irg. */
131 int get_irg_n_callees(ir_graph *irg) {
132 if (irg->callees) return ARR_LEN(irg->callees);
136 /* Returns the callee at position pos. */
137 ir_graph *get_irg_callee(ir_graph *irg, int pos) {
138 assert (pos >= 0 && pos < get_irg_n_callees(irg));
139 if (irg->callees) return irg->callees[pos]->irg;
143 /* Returns non-zero if the callee at position pos is "a backedge", i.e. a recursion. */
144 int is_irg_callee_backedge(ir_graph *irg, int pos) {
145 assert (pos >= 0 && pos < get_irg_n_callees(irg));
146 return irg->callee_isbe != NULL ? irg->callee_isbe[pos] : 0;
149 /* Returns non-zero if the irg has a backedge callee. */
150 int has_irg_callee_backedge(ir_graph *irg) {
151 int i, n_callees = get_irg_n_callees(irg);
153 if (irg->callee_isbe != NULL) {
154 for (i = 0; i < n_callees; ++i)
155 if (irg->callee_isbe[i]) return 1;
161 * Mark the callee at position pos as a backedge.
163 static void set_irg_callee_backedge(ir_graph *irg, int pos) {
164 int n = get_irg_n_callees(irg);
166 assert (pos >= 0 && pos < n);
168 /* allocate a new array on demand */
169 if (irg->callee_isbe == NULL)
170 irg->callee_isbe = xcalloc(n, sizeof(irg->callee_isbe[0]));
171 irg->callee_isbe[pos] = 1;
174 /* Returns the maximal loop depth of call nodes that call along this edge. */
175 int get_irg_callee_loop_depth(ir_graph *irg, int pos) {
176 assert (pos >= 0 && pos < get_irg_n_callees(irg));
177 if (irg->callees) return irg->callees[pos]->max_depth;
182 double get_irg_callee_execution_frequency(ir_graph *irg, int pos) {
183 ir_node **arr = irg->callees[pos]->call_list;
184 int i, n_Calls = ARR_LEN(arr);
187 for (i = 0; i < n_Calls; ++i) {
188 freq += get_irn_exec_freq(arr[i]);
193 double get_irg_callee_method_execution_frequency(ir_graph *irg, int pos) {
194 double call_freq = get_irg_callee_execution_frequency(irg, pos);
195 double meth_freq = get_irg_method_execution_frequency(irg);
196 return call_freq * meth_freq;
200 double get_irg_caller_method_execution_frequency(ir_graph *irg, int pos) {
201 ir_graph *caller = get_irg_caller(irg, pos);
202 int pos_callee = reverse_pos(irg, pos);
204 return get_irg_callee_method_execution_frequency(caller, pos_callee);
209 /* --------------------- Compute the callgraph ------------------------ */
212 * Walker called by compute_callgraph(), analyses all Call nodes.
214 static void ana_Call(ir_node *n, void *env) {
218 if (! is_Call(n)) return;
220 irg = get_irn_irg(n);
221 n_callees = get_Call_n_callees(n);
222 for (i = 0; i < n_callees; ++i) {
223 ir_entity *callee_e = get_Call_callee(n, i);
224 ir_graph *callee = get_entity_irg(callee_e);
228 cg_callee_entry *found;
233 pset_insert((pset *)callee->callers, irg, HASH_PTR(irg));
234 found = pset_find((pset *)irg->callees, &buf, HASH_PTR(callee));
235 if (found) { /* add Call node to list, compute new nesting. */
236 ir_node **arr = found->call_list;
237 ARR_APP1(ir_node *, arr, n);
238 found->call_list = arr;
239 } else { /* New node, add Call node and init nesting. */
240 found = (cg_callee_entry *)obstack_alloc(irg->obst, sizeof(*found));
242 found->call_list = NEW_ARR_F(ir_node *, 1);
243 found->call_list[0] = n;
244 found->max_depth = 0;
245 pset_insert((pset *)irg->callees, found, HASH_PTR(callee));
247 depth = get_loop_depth(get_irn_loop(get_nodes_block(n)));
248 found->max_depth = (depth > found->max_depth) ? depth : found->max_depth;
253 /** compare two ir graphs in a cg_callee_entry */
254 static int cg_callee_entry_cmp(const void *elt, const void *key) {
255 const cg_callee_entry *e1 = elt;
256 const cg_callee_entry *e2 = key;
257 return e1->irg != e2->irg;
260 /** compare two ir graphs */
261 static int graph_cmp(const void *elt, const void *key) {
262 const ir_graph *e1 = elt;
263 const ir_graph *e2 = key;
268 /* Construct and destruct the callgraph. */
269 void compute_callgraph(void) {
272 assert(! get_interprocedural_view()); /* Else walking will not reach the Call nodes. */
277 n_irgs = get_irp_n_irgs();
278 for (i = 0; i < n_irgs; ++i) {
279 ir_graph *irg = get_irp_irg(i);
280 assert(get_irg_callee_info_state(irg) == irg_callee_info_consistent);
281 irg->callees = (cg_callee_entry **)new_pset(cg_callee_entry_cmp, 8);
282 irg->callers = (ir_graph **)new_pset(graph_cmp, 8);
283 //construct_cf_backedges(irg);
286 /* Compute the call graph */
287 for (i = 0; i < n_irgs; ++i) {
288 ir_graph *irg = get_irp_irg(i);
289 construct_cf_backedges(irg); // We also find the maximal loop depth of a call.
290 irg_walk_graph(irg, ana_Call, NULL, NULL);
293 /* Change the sets to arrays. */
294 for (i = 0; i < n_irgs; ++i) {
296 cg_callee_entry *callee;
297 ir_graph *c, *irg = get_irp_irg(i);
298 pset *callee_set, *caller_set;
300 callee_set = (pset *)irg->callees;
301 count = pset_count(callee_set);
302 irg->callees = NEW_ARR_F(cg_callee_entry *, count);
303 irg->callee_isbe = NULL;
304 callee = pset_first(callee_set);
305 for (j = 0; j < count; ++j) {
306 irg->callees[j] = callee;
307 callee = pset_next(callee_set);
309 del_pset(callee_set);
310 assert(callee == NULL);
312 caller_set = (pset *)irg->callers;
313 count = pset_count(caller_set);
314 irg->callers = NEW_ARR_F(ir_graph *, count);
315 irg->caller_isbe = NULL;
316 c = pset_first(caller_set);
317 for (j = 0; j < count; ++j) {
319 c = pset_next(caller_set);
321 del_pset(caller_set);
324 set_irp_callgraph_state(irp_callgraph_consistent);
327 /* Destruct the callgraph. */
328 void free_callgraph(void) {
329 int i, n_irgs = get_irp_n_irgs();
330 for (i = 0; i < n_irgs; ++i) {
331 ir_graph *irg = get_irp_irg(i);
332 if (irg->callees) DEL_ARR_F(irg->callees);
333 if (irg->callers) DEL_ARR_F(irg->callers);
334 if (irg->callee_isbe) free(irg->callee_isbe);
335 if (irg->caller_isbe) free(irg->caller_isbe);
338 irg->callee_isbe = NULL;
339 irg->caller_isbe = NULL;
341 set_irp_callgraph_state(irp_callgraph_none);
344 /* ----------------------------------------------------------------------------------- */
345 /* A walker for the callgraph */
346 /* ----------------------------------------------------------------------------------- */
349 static void do_walk(ir_graph *irg, callgraph_walk_func *pre, callgraph_walk_func *post, void *env) {
352 if (cg_irg_visited(irg)) return;
353 mark_cg_irg_visited(irg);
358 n_callees = get_irg_n_callees(irg);
359 for (i = 0; i < n_callees; i++) {
360 ir_graph *m = get_irg_callee(irg, i);
361 do_walk(m, pre, post, env);
368 void callgraph_walk(callgraph_walk_func *pre, callgraph_walk_func *post, void *env) {
369 int i, n_irgs = get_irp_n_irgs();
372 do_walk(get_irp_main_irg(), pre, post, env);
373 for (i = 0; i < n_irgs; i++) {
374 ir_graph *irg = get_irp_irg(i);
375 if (!cg_irg_visited(irg) && get_irg_n_callers(irg) == 0)
376 do_walk(irg, pre, post, env);
378 for (i = 0; i < n_irgs; i++) {
379 ir_graph *irg = get_irp_irg(i);
380 if (!cg_irg_visited(irg))
381 do_walk(irg, pre, post, env);
385 /* ----------------------------------------------------------------------------------- */
386 /* loop construction algorithm */
387 /* ----------------------------------------------------------------------------------- */
389 static ir_graph *outermost_ir_graph; /**< The outermost graph the scc is computed
391 static ir_loop *current_loop; /**< Current cfloop construction is working
393 static int loop_node_cnt = 0; /**< Counts the number of allocated cfloop nodes.
394 Each cfloop node gets a unique number.
395 What for? ev. remove. @@@ */
396 static int current_dfn = 1; /**< Counter to generate depth first numbering
400 /*-----------------*/
401 /* Node attributes */
402 /*-----------------*/
404 typedef struct scc_info {
405 int in_stack; /**< Marks whether node is on the stack. */
406 int dfn; /**< Depth first search number. */
407 int uplink; /**< dfn number of ancestor. */
412 * allocates a new scc_info of the obstack
414 static INLINE scc_info *new_scc_info(void) {
415 scc_info *info = obstack_alloc (outermost_ir_graph->obst, sizeof(*info));
416 memset(info, 0, sizeof(*info));
421 * Returns non-zero if a graph was already visited.
424 cg_irg_visited(ir_graph *irg) {
425 scc_info *info = get_irg_link(irg);
426 assert(info && "missing call to init_scc");
427 return (info->visited >= master_cg_visited);
431 * Marks a graph as visited.
434 mark_cg_irg_visited(ir_graph *irg) {
435 scc_info *info = get_irg_link(irg);
436 assert(info && "missing call to init_scc");
437 info->visited = master_cg_visited;
441 * Set a graphs visited flag to i.
444 set_cg_irg_visited(ir_graph *irg, int i) {
445 scc_info *info = get_irg_link(irg);
446 assert(info && "missing call to init_scc");
451 * Returns the visited flag of a graph.
454 get_cg_irg_visited(ir_graph *irg) {
455 scc_info *info = get_irg_link(irg);
456 assert(info && "missing call to init_scc");
457 return info->visited;
461 mark_irg_in_stack(ir_graph *irg) {
462 scc_info *info = get_irg_link(irg);
463 assert(info && "missing call to init_scc");
468 mark_irg_not_in_stack(ir_graph *irg) {
469 scc_info *info = get_irg_link(irg);
470 assert(info && "missing call to init_scc");
475 irg_is_in_stack(ir_graph *irg) {
476 scc_info *info = get_irg_link(irg);
477 assert(info && "missing call to init_scc");
478 return info->in_stack;
482 set_irg_uplink(ir_graph *irg, int uplink) {
483 scc_info *info = get_irg_link(irg);
484 assert(info && "missing call to init_scc");
485 info->uplink = uplink;
489 get_irg_uplink(ir_graph *irg) {
490 scc_info *info = get_irg_link(irg);
491 assert(info && "missing call to init_scc");
496 set_irg_dfn(ir_graph *irg, int dfn) {
497 scc_info *info = get_irg_link(irg);
498 assert(info && "missing call to init_scc");
503 get_irg_dfn(ir_graph *irg) {
504 scc_info *info = get_irg_link(irg);
505 assert(info && "missing call to init_scc");
509 /**********************************************************************/
511 /**********************************************************************/
513 static ir_graph **stack = NULL;
514 static int tos = 0; /**< top of stack */
517 * Initialize the irg stack.
519 static INLINE void init_stack(void) {
521 ARR_RESIZE (ir_graph *, stack, 1000);
523 stack = NEW_ARR_F (ir_graph *, 1000);
529 * push a graph on the irg stack
530 * @param n the graph to be pushed
532 static INLINE void push(ir_graph *irg) {
533 if (tos == ARR_LEN (stack)) {
534 int nlen = ARR_LEN (stack) * 2;
535 ARR_RESIZE (ir_node *, stack, nlen);
538 mark_irg_in_stack(irg);
542 * return the topmost graph on the stack and pop it
544 static INLINE ir_graph *pop(void) {
545 ir_graph *irg = stack[--tos];
546 mark_irg_not_in_stack(irg);
551 * The nodes up to irg belong to the current loop.
552 * Removes them from the stack and adds them to the current loop.
554 static INLINE void pop_scc_to_loop(ir_graph *irg) {
560 set_irg_dfn(m, loop_node_cnt);
561 add_loop_node(current_loop, (ir_node *)m);
563 //m->callgraph_loop_depth = current_loop->depth;
567 /* GL ??? my last son is my grandson??? Removes cfloops with no
568 ir_nodes in them. Such loops have only another loop as son. (Why
569 can't they have two loops as sons? Does it never get that far? ) */
570 static void close_loop(ir_loop *l) {
571 int last = get_loop_n_elements(l) - 1;
572 loop_element lelement = get_loop_element(l, last);
573 ir_loop *last_son = lelement.son;
575 if (get_kind(last_son) == k_ir_loop &&
576 get_loop_n_elements(last_son) == 1) {
579 lelement = get_loop_element(last_son, 0);
581 if(get_kind(gson) == k_ir_loop) {
582 loop_element new_last_son;
584 gson -> outer_loop = l;
585 new_last_son.son = gson;
586 l -> children[last] = new_last_son;
594 * Removes and unmarks all nodes up to n from the stack.
595 * The nodes must be visited once more to assign them to a scc.
597 static INLINE void pop_scc_unmark_visit(ir_graph *n) {
602 set_cg_irg_visited(m, 0);
606 /**********************************************************************/
607 /* The loop data structure. **/
608 /**********************************************************************/
611 * Allocates a new loop as son of current_loop. Sets current_loop
612 * to the new loop and returns the father.
614 static ir_loop *new_loop(void) {
615 ir_loop *father, *son;
617 father = current_loop;
619 son = obstack_alloc(outermost_ir_graph->obst, sizeof(*son));
620 memset(son, 0, sizeof(*son));
621 son->kind = k_ir_loop;
622 son->children = NEW_ARR_F (loop_element, 0);
626 son->outer_loop = father;
627 add_loop_son(father, son);
628 son->depth = father->depth + 1;
629 } else { /* The root loop */
630 son->outer_loop = son;
635 son->loop_nr = get_irp_new_node_nr();
643 /**********************************************************************/
644 /* Constructing and destructing the loop/backedge information. **/
645 /**********************************************************************/
647 /* Initialization steps. **********************************************/
658 n_irgs = get_irp_n_irgs();
659 for (i = 0; i < n_irgs; ++i) {
660 ir_graph *irg = get_irp_irg(i);
661 set_irg_link(irg, new_scc_info());
662 irg->callgraph_recursion_depth = 0;
663 irg->callgraph_loop_depth = 0;
667 /** Returns non-zero if n is a loop header, i.e., it is a Block node
668 * and has predecessors within the cfloop and out of the cfloop.
670 * @param root: only needed for assertion.
673 is_head(ir_graph *n, ir_graph *root)
676 int some_outof_loop = 0, some_in_loop = 0;
678 arity = get_irg_n_callees(n);
679 for (i = 0; i < arity; i++) {
680 ir_graph *pred = get_irg_callee(n, i);
681 if (is_irg_callee_backedge(n, i)) continue;
682 if (!irg_is_in_stack(pred)) {
685 if (get_irg_uplink(pred) < get_irg_uplink(root)) {
686 DDMG(pred); DDMG(root);
687 assert(get_irg_uplink(pred) >= get_irg_uplink(root));
693 return some_outof_loop & some_in_loop;
697 * Returns non-zero if n is possible loop head of an endless loop.
698 * I.e., it is a Block, Phi or Filter node and has only predecessors
700 * @arg root: only needed for assertion.
703 is_endless_head(ir_graph *n, ir_graph *root)
706 int some_outof_loop = 0, some_in_loop = 0;
708 arity = get_irg_n_callees(n);
709 for (i = 0; i < arity; i++) {
710 ir_graph *pred = get_irg_callee(n, i);
712 if (is_irg_callee_backedge(n, i)) { continue; }
713 if (!irg_is_in_stack(pred)) {
716 if(get_irg_uplink(pred) < get_irg_uplink(root)) {
717 DDMG(pred); DDMG(root);
718 assert(get_irg_uplink(pred) >= get_irg_uplink(root));
724 return !some_outof_loop & some_in_loop;
729 * Check whether there is a parallel edge in the ip control flow.
733 is_ip_head(ir_graph *n, ir_graph *pred)
736 int iv_rem = get_interprocedural_view();
737 set_interprocedural_view(1);
739 ir_node *sblock = get_irg_start_block(n);
740 int i, arity = get_Block_n_cfgpreds(sblock);
742 //printf(" edge from "); DDMG(n);
743 //printf(" to pred "); DDMG(pred);
744 //printf(" sblock "); DDMN(sblock);
746 for (i = 0; i < arity; i++) {
747 ir_node *pred_cfop = skip_Proj(get_Block_cfgpred(sblock, i));
748 //printf(" "); DDMN(pred_cfop);
749 if (get_irn_op(pred_cfop) == op_CallBegin) { /* could be Unknown */
750 ir_graph *ip_pred = get_irn_irg(pred_cfop);
751 //printf(" "); DDMG(ip_pred);
752 if ((ip_pred == pred) && is_backedge(sblock, i)) {
753 //printf(" found\n");
759 set_interprocedural_view(iv_rem);
764 * Returns index of the predecessor with the smallest dfn number
765 * greater-equal than limit.
768 smallest_dfn_pred(ir_graph *n, int limit)
770 int i, index = -2, min = -1;
772 int arity = get_irg_n_callees(n);
773 for (i = 0; i < arity; i++) {
774 ir_graph *pred = get_irg_callee(n, i);
775 if (is_irg_callee_backedge(n, i) || !irg_is_in_stack(pred)) continue;
776 if (get_irg_dfn(pred) >= limit && (min == -1 || get_irg_dfn(pred) < min)) {
778 min = get_irg_dfn(pred);
785 /** Returns index of the predecessor with the largest dfn number. */
787 largest_dfn_pred(ir_graph *n)
789 int i, index = -2, max = -1;
791 int arity = get_irg_n_callees(n);
792 for (i = 0; i < arity; i++) {
793 ir_graph *pred = get_irg_callee(n, i);
794 if (is_irg_callee_backedge (n, i) || !irg_is_in_stack(pred)) continue;
795 if (get_irg_dfn(pred) > max) {
797 max = get_irg_dfn(pred);
806 find_tail(ir_graph *n) {
808 int i, res_index = -2;
811 if (!icfg && rm_cyclic_phis && remove_cyclic_phis (n)) return NULL;
813 m = stack[tos-1]; /* tos = top of stack */
814 if (is_head (m, n)) {
815 res_index = smallest_dfn_pred(m, 0);
816 if ((res_index == -2) && /* no smallest dfn pred found. */
820 if (m == n) return NULL; // Is this to catch Phi - self loops?
821 for (i = tos-2; i >= 0; --i) {
824 if (is_head (m, n)) {
825 res_index = smallest_dfn_pred (m, get_irg_dfn(m) + 1);
826 if (res_index == -2) /* no smallest dfn pred found. */
827 res_index = largest_dfn_pred (m);
829 if ((m == n) && (res_index == -2)) {
835 /* We should not walk past our selves on the stack: The upcoming nodes
836 are not in this loop. We assume a loop not reachable from Start. */
845 /* A dead loop not reachable from Start. */
846 for (i = tos-2; i >= 0; --i) {
848 if (is_endless_head (m, n)) {
849 res_index = smallest_dfn_pred (m, get_irg_dfn(m) + 1);
850 if (res_index == -2) /* no smallest dfn pred found. */
851 res_index = largest_dfn_pred (m);
854 if (m == n) { break; } /* It's not an unreachable loop, either. */
856 //assert(0 && "no head found on stack");
860 assert (res_index > -2);
862 set_irg_callee_backedge (m, res_index);
863 return get_irg_callee(m, res_index);
867 find_tail(ir_graph *n) {
869 int i, res_index = -2;
872 ir_graph *in_and_out = NULL;
873 ir_graph *only_in = NULL;
874 ir_graph *ip_in_and_out = NULL;
875 ir_graph *ip_only_in = NULL;
877 //printf("find tail for "); DDMG(n);
879 for (i = tos-1; i >= 0; --i) {
880 ir_graph *pred = (i < tos -1) ? stack[i+1] : n;
883 if (is_head (m, n)) {
884 //printf(" found 1a! "); DDM;
886 if (is_ip_head(pred, m)) {
887 //printf(" found 1b! "); DDM;
890 } else if (!ip_only_in && is_endless_head(m, n)) {
892 //printf(" found 2a! "); DDM;
893 if (is_ip_head(pred, m)) {
894 //printf(" found 2b! "); DDM;
897 } else if (is_ip_head(pred, m)) {
898 //printf(" found 3! "); DDM; This happens for self recursions in the second
899 //assert(0); scc iteration (the one to flip the loop.)
902 if (ip_in_and_out) break; /* That's what we really want. */
904 if (m == n) break; /* Don't walk past n on the stack! */
908 if (!in_and_out && !only_in)
909 /* There is no loop */
913 /* Is there a head in the callgraph without a head in the
915 assert(in_and_out || only_in);
917 m = (ip_in_and_out) ? ip_in_and_out : ip_only_in;
920 m = (in_and_out) ? in_and_out : only_in;
922 //printf("*** head is "); DDMG(m);
924 res_index = smallest_dfn_pred (m, get_irg_dfn(m) + 1);
925 if (res_index == -2) /* no smallest dfn pred found. */
926 res_index = largest_dfn_pred (m);
928 set_irg_callee_backedge (m, res_index);
929 res = get_irg_callee(m, res_index);
930 //printf("*** tail is "); DDMG(res);
936 /*-----------------------------------------------------------*
937 * The core algorithm. *
938 *-----------------------------------------------------------*/
941 static void cgscc(ir_graph *n) {
944 if (cg_irg_visited(n)) return;
945 mark_cg_irg_visited(n);
947 /* Initialize the node */
948 set_irg_dfn(n, current_dfn); /* Depth first number for this node */
949 set_irg_uplink(n, current_dfn); /* ... is default uplink. */
953 arity = get_irg_n_callees(n);
954 for (i = 0; i < arity; i++) {
956 if (is_irg_callee_backedge(n, i)) continue;
957 m = get_irg_callee(n, i);
959 /** This marks the backedge, but does it guarantee a correct loop tree? */
960 //if (m == n) { set_irg_callee_backedge(n, i); continue; }
963 if (irg_is_in_stack(m)) {
964 /* Uplink of m is smaller if n->m is a backedge.
965 Propagate the uplink to mark the cfloop. */
966 if (get_irg_uplink(m) < get_irg_uplink(n))
967 set_irg_uplink(n, get_irg_uplink(m));
971 if (get_irg_dfn(n) == get_irg_uplink(n)) {
972 /* This condition holds for
973 1) the node with the incoming backedge.
974 That is: We found a cfloop!
975 2) Straight line code, because no uplink has been propagated, so the
976 uplink still is the same as the dfn.
978 But n might not be a proper cfloop head for the analysis. Proper cfloop
979 heads are Block and Phi nodes. find_tail searches the stack for
980 Block's and Phi's and takes those nodes as cfloop heads for the current
981 cfloop instead and marks the incoming edge as backedge. */
983 ir_graph *tail = find_tail(n);
985 /* We have a cfloop, that is no straight line code,
986 because we found a cfloop head!
987 Next actions: Open a new cfloop on the cfloop tree and
988 try to find inner cfloops */
991 ir_loop *l = new_loop();
993 /* Remove the cfloop from the stack ... */
994 pop_scc_unmark_visit (n);
996 /* The current backedge has been marked, that is temporarily eliminated,
997 by find tail. Start the scc algorithm
998 anew on the subgraph thats left (the current cfloop without the backedge)
999 in order to find more inner cfloops. */
1003 assert (cg_irg_visited(n));
1013 * reset the backedge information for all callers in all irgs
1015 static void reset_isbe(void) {
1016 int i, n_irgs = get_irp_n_irgs();
1018 for (i = 0; i < n_irgs; ++i) {
1019 ir_graph *irg = get_irp_irg(i);
1021 if (irg->caller_isbe)
1022 free(irg->caller_isbe);
1023 irg->caller_isbe = NULL;
1025 if (irg->callee_isbe)
1026 free(irg->callee_isbe);
1027 irg->callee_isbe = NULL;
1034 /* ----------------------------------------------------------------------------------- */
1035 /* Another algorithm to compute recursion nesting depth */
1036 /* Walk the callgraph. For each crossed edge increase the loop depth by the edge */
1037 /* weight. Assign graphs the maximal depth. */
1038 /* ----------------------------------------------------------------------------------- */
1040 static void compute_loop_depth (ir_graph *irg, void *env) {
1041 int current_nesting = *(int *) env;
1042 int old_nesting = irg->callgraph_loop_depth;
1043 int old_visited = get_cg_irg_visited(irg);
1048 if (cg_irg_visited(irg)) return;
1050 mark_cg_irg_visited(irg);
1052 //printf(" old: %d new %d master %d", old_visited, get_cg_irg_visited(irg), master_cg_visited); DDMG(irg);
1055 if (old_nesting < current_nesting)
1056 irg->callgraph_loop_depth = current_nesting;
1058 if (current_nesting > irp->max_callgraph_loop_depth)
1059 irp->max_callgraph_loop_depth = current_nesting;
1061 if ((old_visited +1 < get_cg_irg_visited(irg)) || /* not yet visited */
1062 (old_nesting < current_nesting)) { /* propagate larger nesting */
1063 /* Don't walk the graph, but a tree that is an unfolded graph. */
1064 n_callees = get_irg_n_callees(irg);
1065 for (i = 0; i < n_callees; i++) {
1066 ir_graph *m = get_irg_callee(irg, i);
1067 *(int *)env += get_irg_callee_loop_depth(irg, i);
1068 compute_loop_depth(m, env);
1069 *(int *)env -= get_irg_callee_loop_depth(irg, i);
1073 set_cg_irg_visited(irg, master_cg_visited-1);
1076 /* ------------------------------------------------------------------------------------ */
1077 /* Another algorithm to compute recursion nesting depth */
1078 /* Walk the callgraph. For each crossed loop increase the nesting depth by one. */
1079 /* Assign graphs the maximal nesting depth. Don't increase if passing loops more than */
1081 /* ------------------------------------------------------------------------------------ */
1084 /* For callees, we want to remember the Call nodes, too. */
1085 typedef struct ana_entry2 {
1086 ir_loop **loop_stack; /**< a stack of ir_loop entries */
1087 int tos; /**< the top of stack entry */
1088 int recursion_nesting;
1092 * push a loop entry on the stack
1094 static void push2(ana_entry2 *e, ir_loop *g) {
1095 if (ARR_LEN(e->loop_stack) == e->tos) {
1096 ARR_APP1(ir_loop *, e->loop_stack, g);
1098 e->loop_stack[e->tos] = g;
1104 * returns the top of stack and pop it
1106 static ir_loop *pop2(ana_entry2 *e) {
1107 return e->loop_stack[--e->tos];
1111 * check if a loop g in on the stack. Did not check the TOS.
1113 static int in_stack(ana_entry2 *e, ir_loop *g) {
1115 for (i = e->tos-1; i >= 0; --i) {
1116 if (e->loop_stack[i] == g) return 1;
1121 static void compute_rec_depth (ir_graph *irg, void *env) {
1122 ana_entry2 *e = (ana_entry2 *)env;
1123 ir_loop *l = irg->l;
1124 int depth, old_depth = irg->callgraph_recursion_depth;
1128 if (cg_irg_visited(irg)) return;
1129 mark_cg_irg_visited(irg);
1131 /* -- compute and set the new nesting value -- */
1132 if ((l != irp->outermost_cg_loop) && !in_stack(e, l)) {
1134 e->recursion_nesting++;
1137 depth = e->recursion_nesting;
1139 if (old_depth < depth)
1140 irg->callgraph_recursion_depth = depth;
1142 if (depth > irp->max_callgraph_recursion_depth)
1143 irp->max_callgraph_recursion_depth = depth;
1145 /* -- spread the nesting value -- */
1146 if (depth == 0 || old_depth < depth) {
1147 /* Don't walk the graph, but a tree that is an unfolded graph.
1148 Therefore we unset the visited flag at the end. */
1149 n_callees = get_irg_n_callees(irg);
1150 for (i = 0; i < n_callees; i++) {
1151 ir_graph *m = get_irg_callee(irg, i);
1152 compute_rec_depth(m, env);
1156 /* -- clean up -- */
1159 e->recursion_nesting--;
1161 set_cg_irg_visited(irg, master_cg_visited-1);
1165 /* ----------------------------------------------------------------------------------- */
1166 /* Another algorithm to compute the execution frequency of methods ignoring recursions. */
1167 /* Walk the callgraph. Ignore backedges. Use sum of execution frequencies of Call */
1168 /* nodes to evaluate a callgraph edge. */
1169 /* ----------------------------------------------------------------------------------- */
1171 /* Returns the method execution frequency of a graph. */
1172 double get_irg_method_execution_frequency (ir_graph *irg) {
1173 return irg->method_execution_frequency;
1177 * Increase the method execution frequency to freq if its current value is
1178 * smaller then this.
1180 static void set_irg_method_execution_frequency(ir_graph *irg, double freq) {
1181 irg->method_execution_frequency = freq;
1183 if (irp->max_method_execution_frequency < freq)
1184 irp->max_method_execution_frequency = freq;
1187 static void compute_method_execution_frequency(ir_graph *irg, void *env) {
1193 if (cg_irg_visited(irg)) return;
1195 /* We need the values of all predecessors (except backedges).
1196 So they must be marked. Else we will reach the node through
1197 one of the unmarked ones. */
1198 n_callers = get_irg_n_callers(irg);
1199 for (i = 0; i < n_callers; i++) {
1200 ir_graph *m = get_irg_caller(irg, i);
1201 if (is_irg_caller_backedge(irg, i)) continue;
1202 if (!cg_irg_visited(m)) {
1206 mark_cg_irg_visited(irg);
1208 /* Compute the new frequency. */
1211 for (i = 0; i < n_callers; i++) {
1212 if (! is_irg_caller_backedge(irg, i)) {
1213 double edge_freq = get_irg_caller_method_execution_frequency(irg, i);
1214 assert(edge_freq >= 0);
1221 /* A starting point: method only called from outside,
1222 or only backedges as predecessors. */
1226 set_irg_method_execution_frequency(irg, freq);
1229 n_callees = get_irg_n_callees(irg);
1230 for (i = 0; i < n_callees; i++) {
1231 compute_method_execution_frequency(get_irg_callee(irg, i), NULL);
1236 /* ----------------------------------------------------------------------------------- */
1237 /* The recursion stuff driver. */
1238 /* ----------------------------------------------------------------------------------- */
1240 /* Compute the backedges that represent recursions. */
1241 void find_callgraph_recursions(void) {
1242 int i, n_irgs = get_irp_n_irgs();
1246 /* -- compute the looptree. -- */
1248 /* The outermost graph. We start here. Then we start at all
1249 functions in irg list that are never called, then at the remaining
1250 unvisited ones. The third step is needed for functions that are not
1251 reachable from the outermost graph, but call themselves in a cycle. */
1252 assert(get_irp_main_irg());
1253 outermost_ir_graph = get_irp_main_irg();
1256 current_loop = NULL;
1257 new_loop(); /* sets current_loop */
1259 master_cg_visited++;
1260 cgscc(outermost_ir_graph);
1261 for (i = 0; i < n_irgs; i++) {
1262 ir_graph *irg = get_irp_irg(i);
1263 if (!cg_irg_visited(irg) && get_irg_n_callers(irg) == 0)
1266 for (i = 0; i < n_irgs; i++) {
1267 ir_graph *irg = get_irp_irg(i);
1268 if (!cg_irg_visited(irg))
1271 irp->outermost_cg_loop = current_loop;
1273 /* -- Reverse the backedge information. -- */
1274 for (i = 0; i < n_irgs; i++) {
1275 ir_graph *irg = get_irp_irg(i);
1276 int j, n_callees = get_irg_n_callees(irg);
1277 for (j = 0; j < n_callees; ++j) {
1278 if (is_irg_callee_backedge(irg, j))
1279 set_irg_caller_backedge(get_irg_callee(irg, j), irg);
1283 irp->callgraph_state = irp_callgraph_and_calltree_consistent;
1286 /* Compute interprocedural performance estimates. */
1287 void compute_performance_estimates(void) {
1288 int i, n_irgs = get_irp_n_irgs();
1289 int current_nesting;
1292 assert(get_irp_exec_freq_state() != exec_freq_none && "execution frequency not calculated");
1294 /* -- compute the loop depth -- */
1295 current_nesting = 0;
1296 irp->max_callgraph_loop_depth = 0;
1297 master_cg_visited += 2;
1298 //printf (" ** starting at "); DDMG(get_irp_main_irg());
1299 compute_loop_depth(get_irp_main_irg(), ¤t_nesting);
1300 for (i = 0; i < n_irgs; i++) {
1301 ir_graph *irg = get_irp_irg(i);
1302 if ((get_cg_irg_visited(irg) < master_cg_visited-1) &&
1303 get_irg_n_callers(irg) == 0) {
1304 compute_loop_depth(irg, ¤t_nesting);
1305 //printf (" ** starting at "); DDMG(irg);
1308 for (i = 0; i < n_irgs; i++) {
1309 ir_graph *irg = get_irp_irg(i);
1310 if (get_cg_irg_visited(irg) < master_cg_visited-1) {
1311 compute_loop_depth(irg, ¤t_nesting);
1312 //printf (" ** starting at "); DDMG(irg);
1317 /* -- compute the recursion depth -- */
1318 e.loop_stack = NEW_ARR_F(ir_loop *, 0);
1320 e.recursion_nesting = 0;
1322 irp->max_callgraph_recursion_depth = 0;
1324 master_cg_visited += 2;
1325 compute_rec_depth(get_irp_main_irg(), &e);
1326 //printf (" ++ starting at "); DDMG(get_irp_main_irg());
1327 for (i = 0; i < n_irgs; i++) {
1328 ir_graph *irg = get_irp_irg(i);
1329 if ((get_cg_irg_visited(irg) < master_cg_visited-1) &&
1330 get_irg_n_callers(irg) == 0) {
1331 compute_rec_depth(irg, &e);
1332 //printf (" ++ starting at "); DDMG(irg);
1335 for (i = 0; i < n_irgs; i++) {
1336 ir_graph *irg = get_irp_irg(i);
1337 if (get_cg_irg_visited(irg) < master_cg_visited-1) {
1338 compute_rec_depth(irg, &e);
1339 //printf (" ++ starting at "); DDMG(irg);
1343 DEL_ARR_F(e.loop_stack);
1345 /* -- compute the execution frequency -- */
1346 irp->max_method_execution_frequency = 0;
1347 master_cg_visited += 2;
1348 assert(get_irg_n_callers(get_irp_main_irg()) == 0);
1349 compute_method_execution_frequency(get_irp_main_irg(), NULL);
1350 for (i = 0; i < n_irgs; i++) {
1351 ir_graph *irg = get_irp_irg(i);
1352 if ((get_cg_irg_visited(irg) < master_cg_visited-1) &&
1353 get_irg_n_callers(irg) == 0) {
1354 compute_method_execution_frequency(irg, NULL);
1357 for (i = 0; i < n_irgs; i++) {
1358 ir_graph *irg = get_irp_irg(i);
1359 if (get_cg_irg_visited(irg) < master_cg_visited-1) {
1360 compute_method_execution_frequency(irg, NULL);
1365 /* Returns the maximal loop depth of all paths from an external visible method to
1367 int get_irg_loop_depth(ir_graph *irg) {
1368 assert(irp->callgraph_state == irp_callgraph_consistent ||
1369 irp->callgraph_state == irp_callgraph_and_calltree_consistent);
1370 return irg->callgraph_loop_depth;
1373 /* Returns the maximal recursion depth of all paths from an external visible method to
1375 int get_irg_recursion_depth(ir_graph *irg) {
1376 assert(irp->callgraph_state == irp_callgraph_and_calltree_consistent);
1377 return irg->callgraph_recursion_depth;
1380 /* Computes the interprocedural loop nesting information. */
1381 void analyse_loop_nesting_depth(void) {
1382 ir_entity **free_methods = NULL;
1385 /* establish preconditions. */
1386 if (get_irp_callee_info_state() != irg_callee_info_consistent) {
1387 cgana(&arr_len, &free_methods);
1390 if (irp_callgraph_consistent != get_irp_callgraph_state()) {
1391 compute_callgraph();
1394 find_callgraph_recursions();
1396 compute_performance_estimates();
1398 set_irp_loop_nesting_depth_state(loop_nesting_depth_consistent);
1402 loop_nesting_depth_state get_irp_loop_nesting_depth_state(void) {
1403 return irp->lnd_state;
1405 void set_irp_loop_nesting_depth_state(loop_nesting_depth_state s) {
1408 void set_irp_loop_nesting_depth_state_inconsistent(void) {
1409 if (irp->lnd_state == loop_nesting_depth_consistent)
1410 irp->lnd_state = loop_nesting_depth_inconsistent;