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);
357 n_callees = get_irg_n_callees(irg);
358 for (i = 0; i < n_callees; i++) {
359 ir_graph *m = get_irg_callee(irg, i);
360 do_walk(m, pre, post, env);
366 void callgraph_walk(callgraph_walk_func *pre, callgraph_walk_func *post, void *env) {
367 int i, n_irgs = get_irp_n_irgs();
370 do_walk(get_irp_main_irg(), pre, post, env);
371 for (i = 0; i < n_irgs; i++) {
372 ir_graph *irg = get_irp_irg(i);
373 if (!cg_irg_visited(irg) && get_irg_n_callers(irg) == 0)
374 do_walk(irg, pre, post, env);
376 for (i = 0; i < n_irgs; i++) {
377 ir_graph *irg = get_irp_irg(i);
378 if (!cg_irg_visited(irg))
379 do_walk(irg, pre, post, env);
383 /* ----------------------------------------------------------------------------------- */
384 /* loop construction algorithm */
385 /* ----------------------------------------------------------------------------------- */
387 static ir_graph *outermost_ir_graph; /**< The outermost graph the scc is computed
389 static ir_loop *current_loop; /**< Current cfloop construction is working
391 static int loop_node_cnt = 0; /**< Counts the number of allocated cfloop nodes.
392 Each cfloop node gets a unique number.
393 What for? ev. remove. @@@ */
394 static int current_dfn = 1; /**< Counter to generate depth first numbering
398 /*-----------------*/
399 /* Node attributes */
400 /*-----------------*/
402 typedef struct scc_info {
403 int in_stack; /**< Marks whether node is on the stack. */
404 int dfn; /**< Depth first search number. */
405 int uplink; /**< dfn number of ancestor. */
410 * allocates a new scc_info of the obstack
412 static INLINE scc_info *new_scc_info(void) {
413 scc_info *info = obstack_alloc (outermost_ir_graph->obst, sizeof(*info));
414 memset(info, 0, sizeof(*info));
419 * Returns non-zero if a graph was already visited.
422 cg_irg_visited(ir_graph *irg) {
423 scc_info *info = get_irg_link(irg);
424 return (info->visited >= master_cg_visited);
428 * Marks a graph as visited.
431 mark_cg_irg_visited(ir_graph *irg) {
432 scc_info *info = get_irg_link(irg);
433 info->visited = master_cg_visited;
437 * Set a graphs visited flag to i.
440 set_cg_irg_visited(ir_graph *irg, int i) {
441 scc_info *info = get_irg_link(irg);
446 * Returns the visited flag of a graph.
449 get_cg_irg_visited(ir_graph *irg) {
450 scc_info *info = get_irg_link(irg);
451 return info->visited;
455 mark_irg_in_stack(ir_graph *irg) {
456 scc_info *info = get_irg_link(irg);
462 mark_irg_not_in_stack(ir_graph *irg) {
463 scc_info *info = get_irg_link(irg);
469 irg_is_in_stack(ir_graph *irg) {
470 scc_info *info = get_irg_link(irg);
472 return info->in_stack;
476 set_irg_uplink(ir_graph *irg, int uplink) {
477 scc_info *info = get_irg_link(irg);
479 info->uplink = uplink;
483 get_irg_uplink(ir_graph *irg) {
484 scc_info *info = get_irg_link(irg);
490 set_irg_dfn(ir_graph *irg, int dfn) {
491 scc_info *info = get_irg_link(irg);
497 get_irg_dfn(ir_graph *irg) {
498 scc_info *info = get_irg_link(irg);
503 /**********************************************************************/
505 /**********************************************************************/
507 static ir_graph **stack = NULL;
508 static int tos = 0; /**< top of stack */
511 * Initialize the irg stack.
513 static INLINE void init_stack(void) {
515 ARR_RESIZE (ir_graph *, stack, 1000);
517 stack = NEW_ARR_F (ir_graph *, 1000);
523 * push a graph on the irg stack
524 * @param n the graph to be pushed
526 static INLINE void push(ir_graph *irg) {
527 if (tos == ARR_LEN (stack)) {
528 int nlen = ARR_LEN (stack) * 2;
529 ARR_RESIZE (ir_node *, stack, nlen);
532 mark_irg_in_stack(irg);
536 * return the topmost graph on the stack and pop it
538 static INLINE ir_graph *pop(void) {
539 ir_graph *irg = stack[--tos];
540 mark_irg_not_in_stack(irg);
545 * The nodes up to irg belong to the current loop.
546 * Removes them from the stack and adds them to the current loop.
548 static INLINE void pop_scc_to_loop(ir_graph *irg) {
554 set_irg_dfn(m, loop_node_cnt);
555 add_loop_node(current_loop, (ir_node *)m);
557 //m->callgraph_loop_depth = current_loop->depth;
561 /* GL ??? my last son is my grandson??? Removes cfloops with no
562 ir_nodes in them. Such loops have only another loop as son. (Why
563 can't they have two loops as sons? Does it never get that far? ) */
564 static void close_loop(ir_loop *l) {
565 int last = get_loop_n_elements(l) - 1;
566 loop_element lelement = get_loop_element(l, last);
567 ir_loop *last_son = lelement.son;
569 if (get_kind(last_son) == k_ir_loop &&
570 get_loop_n_elements(last_son) == 1) {
573 lelement = get_loop_element(last_son, 0);
575 if(get_kind(gson) == k_ir_loop) {
576 loop_element new_last_son;
578 gson -> outer_loop = l;
579 new_last_son.son = gson;
580 l -> children[last] = new_last_son;
588 * Removes and unmarks all nodes up to n from the stack.
589 * The nodes must be visited once more to assign them to a scc.
591 static INLINE void pop_scc_unmark_visit(ir_graph *n) {
596 set_cg_irg_visited(m, 0);
600 /**********************************************************************/
601 /* The loop data structure. **/
602 /**********************************************************************/
605 * Allocates a new loop as son of current_loop. Sets current_loop
606 * to the new loop and returns the father.
608 static ir_loop *new_loop(void) {
609 ir_loop *father, *son;
611 father = current_loop;
613 son = obstack_alloc(outermost_ir_graph->obst, sizeof(*son));
614 memset(son, 0, sizeof(*son));
615 son->kind = k_ir_loop;
616 son->children = NEW_ARR_F (loop_element, 0);
620 son->outer_loop = father;
621 add_loop_son(father, son);
622 son->depth = father->depth + 1;
623 } else { /* The root loop */
624 son->outer_loop = son;
629 son->loop_nr = get_irp_new_node_nr();
637 /**********************************************************************/
638 /* Constructing and destructing the loop/backedge information. **/
639 /**********************************************************************/
641 /* Initialization steps. **********************************************/
652 n_irgs = get_irp_n_irgs();
653 for (i = 0; i < n_irgs; ++i) {
654 ir_graph *irg = get_irp_irg(i);
655 set_irg_link(irg, new_scc_info());
656 irg->callgraph_recursion_depth = 0;
657 irg->callgraph_loop_depth = 0;
661 /** Returns non-zero if n is a loop header, i.e., it is a Block node
662 * and has predecessors within the cfloop and out of the cfloop.
664 * @param root: only needed for assertion.
667 is_head(ir_graph *n, ir_graph *root)
670 int some_outof_loop = 0, some_in_loop = 0;
672 arity = get_irg_n_callees(n);
673 for (i = 0; i < arity; i++) {
674 ir_graph *pred = get_irg_callee(n, i);
675 if (is_irg_callee_backedge(n, i)) continue;
676 if (!irg_is_in_stack(pred)) {
679 if (get_irg_uplink(pred) < get_irg_uplink(root)) {
680 DDMG(pred); DDMG(root);
681 assert(get_irg_uplink(pred) >= get_irg_uplink(root));
687 return some_outof_loop & some_in_loop;
691 * Returns non-zero if n is possible loop head of an endless loop.
692 * I.e., it is a Block, Phi or Filter node and has only predecessors
694 * @arg root: only needed for assertion.
697 is_endless_head(ir_graph *n, ir_graph *root)
700 int some_outof_loop = 0, some_in_loop = 0;
702 arity = get_irg_n_callees(n);
703 for (i = 0; i < arity; i++) {
704 ir_graph *pred = get_irg_callee(n, i);
706 if (is_irg_callee_backedge(n, i)) { continue; }
707 if (!irg_is_in_stack(pred)) {
710 if(get_irg_uplink(pred) < get_irg_uplink(root)) {
711 DDMG(pred); DDMG(root);
712 assert(get_irg_uplink(pred) >= get_irg_uplink(root));
718 return !some_outof_loop & some_in_loop;
723 * Check whether there is a parallel edge in the ip control flow.
727 is_ip_head(ir_graph *n, ir_graph *pred)
730 int iv_rem = get_interprocedural_view();
731 set_interprocedural_view(1);
733 ir_node *sblock = get_irg_start_block(n);
734 int i, arity = get_Block_n_cfgpreds(sblock);
736 //printf(" edge from "); DDMG(n);
737 //printf(" to pred "); DDMG(pred);
738 //printf(" sblock "); DDMN(sblock);
740 for (i = 0; i < arity; i++) {
741 ir_node *pred_cfop = skip_Proj(get_Block_cfgpred(sblock, i));
742 //printf(" "); DDMN(pred_cfop);
743 if (get_irn_op(pred_cfop) == op_CallBegin) { /* could be Unknown */
744 ir_graph *ip_pred = get_irn_irg(pred_cfop);
745 //printf(" "); DDMG(ip_pred);
746 if ((ip_pred == pred) && is_backedge(sblock, i)) {
747 //printf(" found\n");
753 set_interprocedural_view(iv_rem);
758 * Returns index of the predecessor with the smallest dfn number
759 * greater-equal than limit.
762 smallest_dfn_pred(ir_graph *n, int limit)
764 int i, index = -2, min = -1;
766 int arity = get_irg_n_callees(n);
767 for (i = 0; i < arity; i++) {
768 ir_graph *pred = get_irg_callee(n, i);
769 if (is_irg_callee_backedge(n, i) || !irg_is_in_stack(pred)) continue;
770 if (get_irg_dfn(pred) >= limit && (min == -1 || get_irg_dfn(pred) < min)) {
772 min = get_irg_dfn(pred);
779 /** Returns index of the predecessor with the largest dfn number. */
781 largest_dfn_pred(ir_graph *n)
783 int i, index = -2, max = -1;
785 int arity = get_irg_n_callees(n);
786 for (i = 0; i < arity; i++) {
787 ir_graph *pred = get_irg_callee(n, i);
788 if (is_irg_callee_backedge (n, i) || !irg_is_in_stack(pred)) continue;
789 if (get_irg_dfn(pred) > max) {
791 max = get_irg_dfn(pred);
800 find_tail(ir_graph *n) {
802 int i, res_index = -2;
805 if (!icfg && rm_cyclic_phis && remove_cyclic_phis (n)) return NULL;
807 m = stack[tos-1]; /* tos = top of stack */
808 if (is_head (m, n)) {
809 res_index = smallest_dfn_pred(m, 0);
810 if ((res_index == -2) && /* no smallest dfn pred found. */
814 if (m == n) return NULL; // Is this to catch Phi - self loops?
815 for (i = tos-2; i >= 0; --i) {
818 if (is_head (m, n)) {
819 res_index = smallest_dfn_pred (m, get_irg_dfn(m) + 1);
820 if (res_index == -2) /* no smallest dfn pred found. */
821 res_index = largest_dfn_pred (m);
823 if ((m == n) && (res_index == -2)) {
829 /* We should not walk past our selves on the stack: The upcoming nodes
830 are not in this loop. We assume a loop not reachable from Start. */
839 /* A dead loop not reachable from Start. */
840 for (i = tos-2; i >= 0; --i) {
842 if (is_endless_head (m, n)) {
843 res_index = smallest_dfn_pred (m, get_irg_dfn(m) + 1);
844 if (res_index == -2) /* no smallest dfn pred found. */
845 res_index = largest_dfn_pred (m);
848 if (m == n) { break; } /* It's not an unreachable loop, either. */
850 //assert(0 && "no head found on stack");
854 assert (res_index > -2);
856 set_irg_callee_backedge (m, res_index);
857 return get_irg_callee(m, res_index);
861 find_tail(ir_graph *n) {
863 int i, res_index = -2;
866 ir_graph *in_and_out = NULL;
867 ir_graph *only_in = NULL;
868 ir_graph *ip_in_and_out = NULL;
869 ir_graph *ip_only_in = NULL;
871 //printf("find tail for "); DDMG(n);
873 for (i = tos-1; i >= 0; --i) {
874 ir_graph *pred = (i < tos -1) ? stack[i+1] : n;
877 if (is_head (m, n)) {
878 //printf(" found 1a! "); DDM;
880 if (is_ip_head(pred, m)) {
881 //printf(" found 1b! "); DDM;
884 } else if (!ip_only_in && is_endless_head(m, n)) {
886 //printf(" found 2a! "); DDM;
887 if (is_ip_head(pred, m)) {
888 //printf(" found 2b! "); DDM;
891 } else if (is_ip_head(pred, m)) {
892 //printf(" found 3! "); DDM; This happens for self recursions in the second
893 //assert(0); scc iteration (the one to flip the loop.)
896 if (ip_in_and_out) break; /* That's what we really want. */
898 if (m == n) break; /* Don't walk past n on the stack! */
902 if (!in_and_out && !only_in)
903 /* There is no loop */
907 /* Is there a head in the callgraph without a head in the
909 assert(in_and_out || only_in);
911 m = (ip_in_and_out) ? ip_in_and_out : ip_only_in;
914 m = (in_and_out) ? in_and_out : only_in;
916 //printf("*** head is "); DDMG(m);
918 res_index = smallest_dfn_pred (m, get_irg_dfn(m) + 1);
919 if (res_index == -2) /* no smallest dfn pred found. */
920 res_index = largest_dfn_pred (m);
922 set_irg_callee_backedge (m, res_index);
923 res = get_irg_callee(m, res_index);
924 //printf("*** tail is "); DDMG(res);
930 /*-----------------------------------------------------------*
931 * The core algorithm. *
932 *-----------------------------------------------------------*/
935 static void cgscc(ir_graph *n) {
938 if (cg_irg_visited(n)) return;
939 mark_cg_irg_visited(n);
941 /* Initialize the node */
942 set_irg_dfn(n, current_dfn); /* Depth first number for this node */
943 set_irg_uplink(n, current_dfn); /* ... is default uplink. */
947 arity = get_irg_n_callees(n);
948 for (i = 0; i < arity; i++) {
950 if (is_irg_callee_backedge(n, i)) continue;
951 m = get_irg_callee(n, i);
953 /** This marks the backedge, but does it guarantee a correct loop tree? */
954 //if (m == n) { set_irg_callee_backedge(n, i); continue; }
957 if (irg_is_in_stack(m)) {
958 /* Uplink of m is smaller if n->m is a backedge.
959 Propagate the uplink to mark the cfloop. */
960 if (get_irg_uplink(m) < get_irg_uplink(n))
961 set_irg_uplink(n, get_irg_uplink(m));
965 if (get_irg_dfn(n) == get_irg_uplink(n)) {
966 /* This condition holds for
967 1) the node with the incoming backedge.
968 That is: We found a cfloop!
969 2) Straight line code, because no uplink has been propagated, so the
970 uplink still is the same as the dfn.
972 But n might not be a proper cfloop head for the analysis. Proper cfloop
973 heads are Block and Phi nodes. find_tail searches the stack for
974 Block's and Phi's and takes those nodes as cfloop heads for the current
975 cfloop instead and marks the incoming edge as backedge. */
977 ir_graph *tail = find_tail(n);
979 /* We have a cfloop, that is no straight line code,
980 because we found a cfloop head!
981 Next actions: Open a new cfloop on the cfloop tree and
982 try to find inner cfloops */
985 ir_loop *l = new_loop();
987 /* Remove the cfloop from the stack ... */
988 pop_scc_unmark_visit (n);
990 /* The current backedge has been marked, that is temporarily eliminated,
991 by find tail. Start the scc algorithm
992 anew on the subgraph thats left (the current cfloop without the backedge)
993 in order to find more inner cfloops. */
997 assert (cg_irg_visited(n));
1007 * reset the backedge information for all callers in all irgs
1009 static void reset_isbe(void) {
1010 int i, n_irgs = get_irp_n_irgs();
1012 for (i = 0; i < n_irgs; ++i) {
1013 ir_graph *irg = get_irp_irg(i);
1015 if (irg->caller_isbe)
1016 free(irg->caller_isbe);
1017 irg->caller_isbe = NULL;
1019 if (irg->callee_isbe)
1020 free(irg->callee_isbe);
1021 irg->callee_isbe = NULL;
1028 /* ----------------------------------------------------------------------------------- */
1029 /* Another algorithm to compute recursion nesting depth */
1030 /* Walk the callgraph. For each crossed edge increase the loop depth by the edge */
1031 /* weight. Assign graphs the maximal depth. */
1032 /* ----------------------------------------------------------------------------------- */
1034 static void compute_loop_depth (ir_graph *irg, void *env) {
1035 int current_nesting = *(int *) env;
1036 int old_nesting = irg->callgraph_loop_depth;
1037 int old_visited = get_cg_irg_visited(irg);
1042 if (cg_irg_visited(irg)) return;
1044 mark_cg_irg_visited(irg);
1046 //printf(" old: %d new %d master %d", old_visited, get_cg_irg_visited(irg), master_cg_visited); DDMG(irg);
1049 if (old_nesting < current_nesting)
1050 irg->callgraph_loop_depth = current_nesting;
1052 if (current_nesting > irp->max_callgraph_loop_depth)
1053 irp->max_callgraph_loop_depth = current_nesting;
1055 if ((old_visited +1 < get_cg_irg_visited(irg)) || /* not yet visited */
1056 (old_nesting < current_nesting)) { /* propagate larger nesting */
1057 /* Don't walk the graph, but a tree that is an unfolded graph. */
1058 n_callees = get_irg_n_callees(irg);
1059 for (i = 0; i < n_callees; i++) {
1060 ir_graph *m = get_irg_callee(irg, i);
1061 *(int *)env += get_irg_callee_loop_depth(irg, i);
1062 compute_loop_depth(m, env);
1063 *(int *)env -= get_irg_callee_loop_depth(irg, i);
1067 set_cg_irg_visited(irg, master_cg_visited-1);
1070 /* ------------------------------------------------------------------------------------ */
1071 /* Another algorithm to compute recursion nesting depth */
1072 /* Walk the callgraph. For each crossed loop increase the nesting depth by one. */
1073 /* Assign graphs the maximal nesting depth. Don't increase if passing loops more than */
1075 /* ------------------------------------------------------------------------------------ */
1078 /* For callees, we want to remember the Call nodes, too. */
1079 typedef struct ana_entry2 {
1080 ir_loop **loop_stack; /**< a stack of ir_loop entries */
1081 int tos; /**< the top of stack entry */
1082 int recursion_nesting;
1086 * push a loop entry on the stack
1088 static void push2(ana_entry2 *e, ir_loop *g) {
1089 if (ARR_LEN(e->loop_stack) == e->tos) {
1090 ARR_APP1(ir_loop *, e->loop_stack, g);
1092 e->loop_stack[e->tos] = g;
1098 * returns the top of stack and pop it
1100 static ir_loop *pop2(ana_entry2 *e) {
1101 return e->loop_stack[--e->tos];
1105 * check if a loop g in on the stack. Did not check the TOS.
1107 static int in_stack(ana_entry2 *e, ir_loop *g) {
1109 for (i = e->tos-1; i >= 0; --i) {
1110 if (e->loop_stack[i] == g) return 1;
1115 static void compute_rec_depth (ir_graph *irg, void *env) {
1116 ana_entry2 *e = (ana_entry2 *)env;
1117 ir_loop *l = irg->l;
1118 int depth, old_depth = irg->callgraph_recursion_depth;
1122 if (cg_irg_visited(irg)) return;
1123 mark_cg_irg_visited(irg);
1125 /* -- compute and set the new nesting value -- */
1126 if ((l != irp->outermost_cg_loop) && !in_stack(e, l)) {
1128 e->recursion_nesting++;
1131 depth = e->recursion_nesting;
1133 if (old_depth < depth)
1134 irg->callgraph_recursion_depth = depth;
1136 if (depth > irp->max_callgraph_recursion_depth)
1137 irp->max_callgraph_recursion_depth = depth;
1139 /* -- spread the nesting value -- */
1140 if (depth == 0 || old_depth < depth) {
1141 /* Don't walk the graph, but a tree that is an unfolded graph.
1142 Therefore we unset the visited flag at the end. */
1143 n_callees = get_irg_n_callees(irg);
1144 for (i = 0; i < n_callees; i++) {
1145 ir_graph *m = get_irg_callee(irg, i);
1146 compute_rec_depth(m, env);
1150 /* -- clean up -- */
1153 e->recursion_nesting--;
1155 set_cg_irg_visited(irg, master_cg_visited-1);
1159 /* ----------------------------------------------------------------------------------- */
1160 /* Another algorithm to compute the execution frequency of methods ignoring recursions. */
1161 /* Walk the callgraph. Ignore backedges. Use sum of execution frequencies of Call */
1162 /* nodes to evaluate a callgraph edge. */
1163 /* ----------------------------------------------------------------------------------- */
1165 /* Returns the method execution frequency of a graph. */
1166 double get_irg_method_execution_frequency (ir_graph *irg) {
1167 return irg->method_execution_frequency;
1171 * Increase the method execution frequency to freq if its current value is
1172 * smaller then this.
1174 static void set_irg_method_execution_frequency(ir_graph *irg, double freq) {
1175 irg->method_execution_frequency = freq;
1177 if (irp->max_method_execution_frequency < freq)
1178 irp->max_method_execution_frequency = freq;
1181 static void compute_method_execution_frequency(ir_graph *irg, void *env) {
1187 if (cg_irg_visited(irg)) return;
1189 /* We need the values of all predecessors (except backedges).
1190 So they must be marked. Else we will reach the node through
1191 one of the unmarked ones. */
1192 n_callers = get_irg_n_callers(irg);
1193 for (i = 0; i < n_callers; i++) {
1194 ir_graph *m = get_irg_caller(irg, i);
1195 if (is_irg_caller_backedge(irg, i)) continue;
1196 if (!cg_irg_visited(m)) {
1200 mark_cg_irg_visited(irg);
1202 /* Compute the new frequency. */
1205 for (i = 0; i < n_callers; i++) {
1206 if (! is_irg_caller_backedge(irg, i)) {
1207 double edge_freq = get_irg_caller_method_execution_frequency(irg, i);
1208 assert(edge_freq >= 0);
1215 /* A starting point: method only called from outside,
1216 or only backedges as predecessors. */
1220 set_irg_method_execution_frequency(irg, freq);
1223 n_callees = get_irg_n_callees(irg);
1224 for (i = 0; i < n_callees; i++) {
1225 compute_method_execution_frequency(get_irg_callee(irg, i), NULL);
1230 /* ----------------------------------------------------------------------------------- */
1231 /* The recursion stuff driver. */
1232 /* ----------------------------------------------------------------------------------- */
1234 /* Compute the backedges that represent recursions. */
1235 void find_callgraph_recursions(void) {
1236 int i, n_irgs = get_irp_n_irgs();
1240 /* -- compute the looptree. -- */
1242 /* The outermost graph. We start here. Then we start at all
1243 functions in irg list that are never called, then at the remaining
1244 unvisited ones. The third step is needed for functions that are not
1245 reachable from the outermost graph, but call themselves in a cycle. */
1246 assert(get_irp_main_irg());
1247 outermost_ir_graph = get_irp_main_irg();
1250 current_loop = NULL;
1251 new_loop(); /* sets current_loop */
1253 master_cg_visited++;
1254 cgscc(outermost_ir_graph);
1255 for (i = 0; i < n_irgs; i++) {
1256 ir_graph *irg = get_irp_irg(i);
1257 if (!cg_irg_visited(irg) && get_irg_n_callers(irg) == 0)
1260 for (i = 0; i < n_irgs; i++) {
1261 ir_graph *irg = get_irp_irg(i);
1262 if (!cg_irg_visited(irg))
1265 irp->outermost_cg_loop = current_loop;
1267 /* -- Reverse the backedge information. -- */
1268 for (i = 0; i < n_irgs; i++) {
1269 ir_graph *irg = get_irp_irg(i);
1270 int j, n_callees = get_irg_n_callees(irg);
1271 for (j = 0; j < n_callees; ++j) {
1272 if (is_irg_callee_backedge(irg, j))
1273 set_irg_caller_backedge(get_irg_callee(irg, j), irg);
1277 irp->callgraph_state = irp_callgraph_and_calltree_consistent;
1280 /* Compute interprocedural performance estimates. */
1281 void compute_performance_estimates(void) {
1282 int i, n_irgs = get_irp_n_irgs();
1283 int current_nesting;
1286 assert(get_irp_exec_freq_state() != exec_freq_none && "execution frequency not calculated");
1288 /* -- compute the loop depth -- */
1289 current_nesting = 0;
1290 irp->max_callgraph_loop_depth = 0;
1291 master_cg_visited += 2;
1292 //printf (" ** starting at "); DDMG(get_irp_main_irg());
1293 compute_loop_depth(get_irp_main_irg(), ¤t_nesting);
1294 for (i = 0; i < n_irgs; i++) {
1295 ir_graph *irg = get_irp_irg(i);
1296 if ((get_cg_irg_visited(irg) < master_cg_visited-1) &&
1297 get_irg_n_callers(irg) == 0) {
1298 compute_loop_depth(irg, ¤t_nesting);
1299 //printf (" ** starting at "); DDMG(irg);
1302 for (i = 0; i < n_irgs; i++) {
1303 ir_graph *irg = get_irp_irg(i);
1304 if (get_cg_irg_visited(irg) < master_cg_visited-1) {
1305 compute_loop_depth(irg, ¤t_nesting);
1306 //printf (" ** starting at "); DDMG(irg);
1311 /* -- compute the recursion depth -- */
1312 e.loop_stack = NEW_ARR_F(ir_loop *, 0);
1314 e.recursion_nesting = 0;
1316 irp->max_callgraph_recursion_depth = 0;
1318 master_cg_visited += 2;
1319 compute_rec_depth(get_irp_main_irg(), &e);
1320 //printf (" ++ starting at "); DDMG(get_irp_main_irg());
1321 for (i = 0; i < n_irgs; i++) {
1322 ir_graph *irg = get_irp_irg(i);
1323 if ((get_cg_irg_visited(irg) < master_cg_visited-1) &&
1324 get_irg_n_callers(irg) == 0) {
1325 compute_rec_depth(irg, &e);
1326 //printf (" ++ starting at "); DDMG(irg);
1329 for (i = 0; i < n_irgs; i++) {
1330 ir_graph *irg = get_irp_irg(i);
1331 if (get_cg_irg_visited(irg) < master_cg_visited-1) {
1332 compute_rec_depth(irg, &e);
1333 //printf (" ++ starting at "); DDMG(irg);
1337 DEL_ARR_F(e.loop_stack);
1339 /* -- compute the execution frequency -- */
1340 irp->max_method_execution_frequency = 0;
1341 master_cg_visited += 2;
1342 assert(get_irg_n_callers(get_irp_main_irg()) == 0);
1343 compute_method_execution_frequency(get_irp_main_irg(), NULL);
1344 for (i = 0; i < n_irgs; i++) {
1345 ir_graph *irg = get_irp_irg(i);
1346 if ((get_cg_irg_visited(irg) < master_cg_visited-1) &&
1347 get_irg_n_callers(irg) == 0) {
1348 compute_method_execution_frequency(irg, NULL);
1351 for (i = 0; i < n_irgs; i++) {
1352 ir_graph *irg = get_irp_irg(i);
1353 if (get_cg_irg_visited(irg) < master_cg_visited-1) {
1354 compute_method_execution_frequency(irg, NULL);
1359 /* Returns the maximal loop depth of all paths from an external visible method to
1361 int get_irg_loop_depth(ir_graph *irg) {
1362 assert(irp->callgraph_state == irp_callgraph_consistent ||
1363 irp->callgraph_state == irp_callgraph_and_calltree_consistent);
1364 return irg->callgraph_loop_depth;
1367 /* Returns the maximal recursion depth of all paths from an external visible method to
1369 int get_irg_recursion_depth(ir_graph *irg) {
1370 assert(irp->callgraph_state == irp_callgraph_and_calltree_consistent);
1371 return irg->callgraph_recursion_depth;
1374 /* Computes the interprocedural loop nesting information. */
1375 void analyse_loop_nesting_depth(void) {
1376 ir_entity **free_methods = NULL;
1379 /* establish preconditions. */
1380 if (get_irp_callee_info_state() != irg_callee_info_consistent) {
1381 cgana(&arr_len, &free_methods);
1384 if (irp_callgraph_consistent != get_irp_callgraph_state()) {
1385 compute_callgraph();
1388 find_callgraph_recursions();
1390 compute_performance_estimates();
1392 set_irp_loop_nesting_depth_state(loop_nesting_depth_consistent);
1396 loop_nesting_depth_state get_irp_loop_nesting_depth_state(void) {
1397 return irp->lnd_state;
1399 void set_irp_loop_nesting_depth_state(loop_nesting_depth_state s) {
1402 void set_irp_loop_nesting_depth_state_inconsistent(void) {
1403 if (irp->lnd_state == loop_nesting_depth_consistent)
1404 irp->lnd_state = loop_nesting_depth_inconsistent;