2 * Copyright (C) 1995-2008 University of Karlsruhe. All right reserved.
4 * This file is part of libFirm.
6 * This file may be distributed and/or modified under the terms of the
7 * GNU General Public License version 2 as published by the Free Software
8 * Foundation and appearing in the file LICENSE.GPL included in the
9 * packaging of this file.
11 * Licensees holding valid libFirm Professional Edition licenses may use
12 * this file in accordance with the libFirm Commercial License.
13 * Agreement provided with the Software.
15 * This file is provided AS IS with NO WARRANTY OF ANY KIND, INCLUDING THE
16 * WARRANTY OF DESIGN, MERCHANTABILITY AND FITNESS FOR A PARTICULAR
22 * @brief Representation and computation of the callgraph.
23 * @author Goetz Lindenmaier
32 #include "callgraph.h"
36 #include "irgraph_t.h"
40 #include "execution_frequency.h"
45 #include "raw_bitset.h"
49 static ir_visited_t master_cg_visited = 0;
50 static inline int cg_irg_visited (ir_graph *n);
51 static inline void mark_cg_irg_visited(ir_graph *n);
52 static inline void set_cg_irg_visited (ir_graph *n, ir_visited_t i);
54 /** Returns the callgraph state of the program representation. */
55 irp_callgraph_state get_irp_callgraph_state(void) {
56 return irp->callgraph_state;
59 /* Sets the callgraph state of the program representation. */
60 void set_irp_callgraph_state(irp_callgraph_state s) {
61 irp->callgraph_state = s;
64 /* Returns the number of procedures that call the given irg. */
65 int get_irg_n_callers(const ir_graph *irg) {
66 if (irg->callers) return ARR_LEN(irg->callers);
70 /* Returns the caller at position pos. */
71 ir_graph *get_irg_caller(const ir_graph *irg, int pos) {
72 assert(pos >= 0 && pos < get_irg_n_callers(irg));
73 if (irg->callers) return irg->callers[pos];
77 /* Returns non-zero if the caller at position pos is "a backedge", i.e. a recursion. */
78 int is_irg_caller_backedge(const ir_graph *irg, int pos) {
79 assert(pos >= 0 && pos < get_irg_n_callers(irg));
80 return irg->caller_isbe != NULL ? rbitset_is_set(irg->caller_isbe, pos) : 0;
83 /** Search the caller in the list of all callers and set it's backedge property. */
84 static void set_irg_caller_backedge(ir_graph *irg, ir_graph *caller) {
85 int i, n_callers = get_irg_n_callers(irg);
87 /* allocate a new array on demand */
88 if (irg->caller_isbe == NULL)
89 irg->caller_isbe = rbitset_malloc(n_callers);
90 for (i = 0; i < n_callers; ++i) {
91 if (get_irg_caller(irg, i) == caller) {
92 rbitset_set(irg->caller_isbe, i);
98 /* Returns non-zero if the irg has a backedge caller. */
99 int has_irg_caller_backedge(const ir_graph *irg) {
100 int i, n_callers = get_irg_n_callers(irg);
102 if (irg->caller_isbe != NULL) {
103 for (i = 0; i < n_callers; ++i)
104 if (rbitset_is_set(irg->caller_isbe, i))
111 * Find the reversion position of a caller.
112 * Given the position pos_caller of an caller of irg, return
113 * irg's callee position on that caller.
115 static int reverse_pos(const ir_graph *callee, int pos_caller) {
116 ir_graph *caller = get_irg_caller(callee, pos_caller);
117 /* search the other relation for the corresponding edge. */
119 int i, n_callees = get_irg_n_callees(caller);
120 for (i = 0; i < n_callees; ++i) {
121 if (get_irg_callee(caller, i) == callee) {
127 assert(pos_callee >= 0);
132 /* Returns the maximal loop depth of call nodes that call along this edge. */
133 int get_irg_caller_loop_depth(const ir_graph *irg, int pos) {
134 ir_graph *caller = get_irg_caller(irg, pos);
135 int pos_callee = reverse_pos(irg, pos);
137 return get_irg_callee_loop_depth(caller, pos_callee);
141 /* Returns the number of procedures that are called by the given irg. */
142 int get_irg_n_callees(const ir_graph *irg) {
143 if (irg->callees) return ARR_LEN(irg->callees);
147 /* Returns the callee at position pos. */
148 ir_graph *get_irg_callee(const ir_graph *irg, int pos) {
149 assert(pos >= 0 && pos < get_irg_n_callees(irg));
150 if (irg->callees) return irg->callees[pos]->irg;
154 /* Returns non-zero if the callee at position pos is "a backedge", i.e. a recursion. */
155 int is_irg_callee_backedge(const ir_graph *irg, int pos) {
156 assert(pos >= 0 && pos < get_irg_n_callees(irg));
157 return irg->callee_isbe != NULL ? rbitset_is_set(irg->callee_isbe, pos) : 0;
160 /* Returns non-zero if the irg has a backedge callee. */
161 int has_irg_callee_backedge(const ir_graph *irg) {
162 int i, n_callees = get_irg_n_callees(irg);
164 if (irg->callee_isbe != NULL) {
165 for (i = 0; i < n_callees; ++i)
166 if (rbitset_is_set(irg->callee_isbe, i))
173 * Mark the callee at position pos as a backedge.
175 static void set_irg_callee_backedge(ir_graph *irg, int pos) {
176 int n = get_irg_n_callees(irg);
178 /* allocate a new array on demand */
179 if (irg->callee_isbe == NULL)
180 irg->callee_isbe = rbitset_malloc(n);
181 assert(pos >= 0 && pos < n);
182 rbitset_set(irg->callee_isbe, pos);
185 /* Returns the maximal loop depth of call nodes that call along this edge. */
186 int get_irg_callee_loop_depth(const ir_graph *irg, int pos) {
187 assert(pos >= 0 && pos < get_irg_n_callees(irg));
188 if (irg->callees) return irg->callees[pos]->max_depth;
193 double get_irg_callee_execution_frequency(const ir_graph *irg, int pos) {
194 ir_node **arr = irg->callees[pos]->call_list;
195 int i, n_Calls = ARR_LEN(arr);
198 for (i = 0; i < n_Calls; ++i) {
199 freq += get_irn_exec_freq(arr[i]);
204 double get_irg_callee_method_execution_frequency(const ir_graph *irg, int pos) {
205 double call_freq = get_irg_callee_execution_frequency(irg, pos);
206 double meth_freq = get_irg_method_execution_frequency(irg);
207 return call_freq * meth_freq;
211 double get_irg_caller_method_execution_frequency(const ir_graph *irg, int pos) {
212 ir_graph *caller = get_irg_caller(irg, pos);
213 int pos_callee = reverse_pos(irg, pos);
215 return get_irg_callee_method_execution_frequency(caller, pos_callee);
220 /* --------------------- Compute the callgraph ------------------------ */
223 * Walker called by compute_callgraph(), analyses all Call nodes.
225 static void ana_Call(ir_node *n, void *env) {
230 if (! is_Call(n)) return;
232 irg = get_irn_irg(n);
233 n_callees = get_Call_n_callees(n);
234 for (i = 0; i < n_callees; ++i) {
235 ir_entity *callee_e = get_Call_callee(n, i);
236 ir_graph *callee = get_entity_irg(callee_e);
240 cg_callee_entry *found;
245 pset_insert((pset *)callee->callers, irg, HASH_PTR(irg));
246 found = pset_find((pset *)irg->callees, &buf, HASH_PTR(callee));
247 if (found) { /* add Call node to list, compute new nesting. */
248 ir_node **arr = found->call_list;
249 ARR_APP1(ir_node *, arr, n);
250 found->call_list = arr;
251 } else { /* New node, add Call node and init nesting. */
252 found = (cg_callee_entry *)obstack_alloc(irg->obst, sizeof(*found));
254 found->call_list = NEW_ARR_F(ir_node *, 1);
255 found->call_list[0] = n;
256 found->max_depth = 0;
257 pset_insert((pset *)irg->callees, found, HASH_PTR(callee));
259 depth = get_loop_depth(get_irn_loop(get_nodes_block(n)));
260 found->max_depth = (depth > found->max_depth) ? depth : found->max_depth;
265 /** compare two ir graphs in a cg_callee_entry */
266 static int cg_callee_entry_cmp(const void *elt, const void *key) {
267 const cg_callee_entry *e1 = elt;
268 const cg_callee_entry *e2 = key;
269 return e1->irg != e2->irg;
272 /** compare two ir graphs for pointer identity */
273 static int graph_cmp(const void *elt, const void *key) {
274 const ir_graph *e1 = elt;
275 const ir_graph *e2 = key;
280 /* Construct and destruct the callgraph. */
281 void compute_callgraph(void) {
284 #ifdef INTERPROCEDURAL_VIEW
285 assert(! get_interprocedural_view()); /* Else walking will not reach the Call nodes. */
291 n_irgs = get_irp_n_irgs();
292 for (i = 0; i < n_irgs; ++i) {
293 ir_graph *irg = get_irp_irg(i);
294 assert(get_irg_callee_info_state(irg) == irg_callee_info_consistent);
295 irg->callees = (cg_callee_entry **)new_pset(cg_callee_entry_cmp, 8);
296 irg->callers = (ir_graph **)new_pset(graph_cmp, 8);
297 //construct_cf_backedges(irg);
300 /* Compute the call graph */
301 for (i = 0; i < n_irgs; ++i) {
302 ir_graph *irg = get_irp_irg(i);
303 construct_cf_backedges(irg); // We also find the maximal loop depth of a call.
304 irg_walk_graph(irg, ana_Call, NULL, NULL);
307 /* Change the sets to arrays. */
308 for (i = 0; i < n_irgs; ++i) {
310 cg_callee_entry *callee;
311 ir_graph *c, *irg = get_irp_irg(i);
312 pset *callee_set, *caller_set;
314 callee_set = (pset *)irg->callees;
315 count = pset_count(callee_set);
316 irg->callees = NEW_ARR_F(cg_callee_entry *, count);
317 irg->callee_isbe = NULL;
318 callee = pset_first(callee_set);
319 for (j = 0; j < count; ++j) {
320 irg->callees[j] = callee;
321 callee = pset_next(callee_set);
323 del_pset(callee_set);
324 assert(callee == NULL);
326 caller_set = (pset *)irg->callers;
327 count = pset_count(caller_set);
328 irg->callers = NEW_ARR_F(ir_graph *, count);
329 irg->caller_isbe = NULL;
330 c = pset_first(caller_set);
331 for (j = 0; j < count; ++j) {
333 c = pset_next(caller_set);
335 del_pset(caller_set);
338 set_irp_callgraph_state(irp_callgraph_consistent);
341 /* Destruct the callgraph. */
342 void free_callgraph(void) {
343 int i, n_irgs = get_irp_n_irgs();
344 for (i = 0; i < n_irgs; ++i) {
345 ir_graph *irg = get_irp_irg(i);
346 if (irg->callees) DEL_ARR_F(irg->callees);
347 if (irg->callers) DEL_ARR_F(irg->callers);
348 if (irg->callee_isbe) free(irg->callee_isbe);
349 if (irg->caller_isbe) free(irg->caller_isbe);
352 irg->callee_isbe = NULL;
353 irg->caller_isbe = NULL;
355 set_irp_callgraph_state(irp_callgraph_none);
358 /* ----------------------------------------------------------------------------------- */
359 /* A walker for the callgraph */
360 /* ----------------------------------------------------------------------------------- */
363 static void do_walk(ir_graph *irg, callgraph_walk_func *pre, callgraph_walk_func *post, void *env) {
366 if (cg_irg_visited(irg))
368 mark_cg_irg_visited(irg);
373 n_callees = get_irg_n_callees(irg);
374 for (i = 0; i < n_callees; i++) {
375 ir_graph *m = get_irg_callee(irg, i);
376 do_walk(m, pre, post, env);
383 void callgraph_walk(callgraph_walk_func *pre, callgraph_walk_func *post, void *env) {
384 int i, n_irgs = get_irp_n_irgs();
387 /* roots are methods which have no callers in the current program */
388 for (i = 0; i < n_irgs; ++i) {
389 ir_graph *irg = get_irp_irg(i);
391 if (get_irg_n_callers(irg) == 0)
392 do_walk(irg, pre, post, env);
395 /* in case of unreachable call loops we haven't visited some irgs yet */
396 for (i = 0; i < n_irgs; i++) {
397 ir_graph *irg = get_irp_irg(i);
398 do_walk(irg, pre, post, env);
402 /* ----------------------------------------------------------------------------------- */
403 /* loop construction algorithm */
404 /* ----------------------------------------------------------------------------------- */
406 static ir_graph *outermost_ir_graph; /**< The outermost graph the scc is computed
408 static ir_loop *current_loop; /**< Current cfloop construction is working
410 static int loop_node_cnt = 0; /**< Counts the number of allocated cfloop nodes.
411 Each cfloop node gets a unique number.
412 What for? ev. remove. @@@ */
413 static int current_dfn = 1; /**< Counter to generate depth first numbering
416 /*-----------------*/
417 /* Node attributes */
418 /*-----------------*/
420 typedef struct scc_info {
421 int in_stack; /**< Marks whether node is on the stack. */
422 int dfn; /**< Depth first search number. */
423 int uplink; /**< dfn number of ancestor. */
428 * allocates a new scc_info on the obstack
430 static inline scc_info *new_scc_info(struct obstack *obst) {
431 scc_info *info = obstack_alloc(obst, sizeof(*info));
432 memset(info, 0, sizeof(*info));
437 * Returns non-zero if a graph was already visited.
439 static inline int cg_irg_visited(ir_graph *irg) {
440 return irg->self_visited >= master_cg_visited;
444 * Marks a graph as visited.
446 static inline void mark_cg_irg_visited(ir_graph *irg) {
447 irg->self_visited = master_cg_visited;
451 * Set a graphs visited flag to i.
453 static inline void set_cg_irg_visited(ir_graph *irg, ir_visited_t i) {
454 irg->self_visited = i;
458 * Returns the visited flag of a graph.
460 static inline ir_visited_t get_cg_irg_visited(ir_graph *irg) {
461 return irg->self_visited;
464 static inline void mark_irg_in_stack(ir_graph *irg) {
465 scc_info *info = get_irg_link(irg);
466 assert(info && "missing call to init_scc()");
470 static inline void mark_irg_not_in_stack(ir_graph *irg) {
471 scc_info *info = get_irg_link(irg);
472 assert(info && "missing call to init_scc()");
476 static inline int irg_is_in_stack(ir_graph *irg) {
477 scc_info *info = get_irg_link(irg);
478 assert(info && "missing call to init_scc()");
479 return info->in_stack;
482 static inline void 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;
488 static inline int get_irg_uplink(ir_graph *irg) {
489 scc_info *info = get_irg_link(irg);
490 assert(info && "missing call to init_scc()");
494 static inline void set_irg_dfn(ir_graph *irg, int dfn) {
495 scc_info *info = get_irg_link(irg);
496 assert(info && "missing call to init_scc()");
500 static inline int get_irg_dfn(ir_graph *irg) {
501 scc_info *info = get_irg_link(irg);
502 assert(info && "missing call to init_scc()");
506 /**********************************************************************/
508 /**********************************************************************/
510 static ir_graph **stack = NULL;
511 static int tos = 0; /**< top of stack */
514 * Initialize the irg stack.
516 static inline void init_stack(void) {
518 ARR_RESIZE(ir_graph *, stack, 1000);
520 stack = NEW_ARR_F(ir_graph *, 1000);
526 * push a graph on the irg stack
527 * @param n the graph to be pushed
529 static inline void push(ir_graph *irg) {
530 if (tos == ARR_LEN(stack)) {
531 int nlen = ARR_LEN(stack) * 2;
532 ARR_RESIZE(ir_node *, stack, nlen);
535 mark_irg_in_stack(irg);
539 * return the topmost graph on the stack and pop it
541 static inline ir_graph *pop(void) {
542 ir_graph *irg = stack[--tos];
543 mark_irg_not_in_stack(irg);
548 * The nodes up to irg belong to the current loop.
549 * Removes them from the stack and adds them to the current loop.
551 static inline void pop_scc_to_loop(ir_graph *irg) {
557 set_irg_dfn(m, loop_node_cnt);
558 add_loop_irg(current_loop, m);
560 //m->callgraph_loop_depth = current_loop->depth;
564 /* GL ??? my last son is my grandson??? Removes cfloops with no
565 ir_nodes in them. Such loops have only another loop as son. (Why
566 can't they have two loops as sons? Does it never get that far? ) */
567 static void close_loop(ir_loop *l) {
568 int last = get_loop_n_elements(l) - 1;
569 loop_element lelement = get_loop_element(l, last);
570 ir_loop *last_son = lelement.son;
572 if (get_kind(last_son) == k_ir_loop &&
573 get_loop_n_elements(last_son) == 1) {
576 lelement = get_loop_element(last_son, 0);
578 if (get_kind(gson) == k_ir_loop) {
579 loop_element new_last_son;
581 gson->outer_loop = l;
582 new_last_son.son = gson;
583 l->children[last] = new_last_son;
590 * Removes and unmarks all nodes up to n from the stack.
591 * The nodes must be visited once more to assign them to a scc.
593 static inline void pop_scc_unmark_visit(ir_graph *n) {
598 set_cg_irg_visited(m, 0);
602 /**********************************************************************/
603 /* The loop data structure. **/
604 /**********************************************************************/
607 * Allocates a new loop as son of current_loop. Sets current_loop
608 * to the new loop and returns the father.
610 static ir_loop *new_loop(void) {
611 ir_loop *father = current_loop;
612 ir_loop *son = alloc_loop(father, outermost_ir_graph->obst);
619 /**********************************************************************/
620 /* Constructing and destructing the loop/backedge information. **/
621 /**********************************************************************/
623 /* Initialization steps. **********************************************/
625 static void init_scc(struct obstack *obst) {
633 n_irgs = get_irp_n_irgs();
634 for (i = 0; i < n_irgs; ++i) {
635 ir_graph *irg = get_irp_irg(i);
636 set_irg_link(irg, new_scc_info(obst));
637 irg->callgraph_recursion_depth = 0;
638 irg->callgraph_loop_depth = 0;
642 /** Returns non-zero if n is a loop header, i.e., it is a Block node
643 * and has predecessors within the cfloop and out of the cfloop.
645 * @param root: only needed for assertion.
647 static int is_head(ir_graph *n, ir_graph *root) {
649 int some_outof_loop = 0, some_in_loop = 0;
651 arity = get_irg_n_callees(n);
652 for (i = 0; i < arity; i++) {
653 ir_graph *pred = get_irg_callee(n, i);
654 if (is_irg_callee_backedge(n, i)) continue;
655 if (!irg_is_in_stack(pred)) {
658 if (get_irg_uplink(pred) < get_irg_uplink(root)) {
659 assert(get_irg_uplink(pred) >= get_irg_uplink(root));
665 return some_outof_loop & some_in_loop;
669 * Returns non-zero if n is possible loop head of an endless loop.
670 * I.e., it is a Block, Phi or Filter node and has only predecessors
672 * @arg root: only needed for assertion.
674 static int is_endless_head(ir_graph *n, ir_graph *root)
677 int some_outof_loop = 0, some_in_loop = 0;
679 arity = get_irg_n_callees(n);
680 for (i = 0; i < arity; i++) {
681 ir_graph *pred = get_irg_callee(n, i);
683 if (is_irg_callee_backedge(n, i))
685 if (!irg_is_in_stack(pred)) {
688 if (get_irg_uplink(pred) < get_irg_uplink(root)) {
689 assert(get_irg_uplink(pred) >= get_irg_uplink(root));
694 return !some_outof_loop & some_in_loop;
697 #ifdef INTERPROCEDURAL_VIEW
699 * Check whether there is a parallel edge in the ip control flow.
702 static int is_ip_head(ir_graph *n, ir_graph *pred)
706 int iv_rem = get_interprocedural_view();
707 set_interprocedural_view(1);
709 ir_node *sblock = get_irg_start_block(n);
710 int i, arity = get_Block_n_cfgpreds(sblock);
712 //printf(" edge from "); DDMG(n);
713 //printf(" to pred "); DDMG(pred);
714 //printf(" sblock "); DDMN(sblock);
716 for (i = 0; i < arity; i++) {
717 ir_node *pred_cfop = skip_Proj(get_Block_cfgpred(sblock, i));
718 //printf(" "); DDMN(pred_cfop);
719 if (is_CallBegin(pred_cfop)) { /* could be Unknown */
720 ir_graph *ip_pred = get_irn_irg(pred_cfop);
721 //printf(" "); DDMG(ip_pred);
722 if ((ip_pred == pred) && is_backedge(sblock, i)) {
723 //printf(" found\n");
729 set_interprocedural_view(iv_rem);
732 #endif /* INTERPROCEDURAL_VIEW */
735 * Returns index of the predecessor with the smallest dfn number
736 * greater-equal than limit.
738 static int smallest_dfn_pred(ir_graph *n, int limit)
740 int i, index = -2, min = -1;
742 int arity = get_irg_n_callees(n);
743 for (i = 0; i < arity; i++) {
744 ir_graph *pred = get_irg_callee(n, i);
745 if (is_irg_callee_backedge(n, i) || !irg_is_in_stack(pred))
747 if (get_irg_dfn(pred) >= limit && (min == -1 || get_irg_dfn(pred) < min)) {
749 min = get_irg_dfn(pred);
756 /** Returns index of the predecessor with the largest dfn number. */
757 static int largest_dfn_pred(ir_graph *n) {
758 int i, index = -2, max = -1;
760 int arity = get_irg_n_callees(n);
761 for (i = 0; i < arity; ++i) {
762 ir_graph *pred = get_irg_callee(n, i);
763 if (is_irg_callee_backedge (n, i) || !irg_is_in_stack(pred)) continue;
764 if (get_irg_dfn(pred) > max) {
766 max = get_irg_dfn(pred);
773 #ifndef INTERPROCEDURAL_VIEW
774 static ir_graph *find_tail(ir_graph *n) {
776 int i, res_index = -2;
779 if (!icfg && rm_cyclic_phis && remove_cyclic_phis (n)) return NULL;
781 m = stack[tos-1]; /* tos = top of stack */
782 if (is_head (m, n)) {
783 res_index = smallest_dfn_pred(m, 0);
784 if ((res_index == -2) && /* no smallest dfn pred found. */
788 if (m == n) return NULL; // Is this to catch Phi - self loops?
789 for (i = tos-2; i >= 0; --i) {
793 res_index = smallest_dfn_pred(m, get_irg_dfn(m) + 1);
794 if (res_index == -2) /* no smallest dfn pred found. */
795 res_index = largest_dfn_pred(m);
797 if ((m == n) && (res_index == -2)) {
803 /* We should not walk past our selves on the stack: The upcoming nodes
804 are not in this loop. We assume a loop not reachable from Start. */
813 /* A dead loop not reachable from Start. */
814 for (i = tos-2; i >= 0; --i) {
816 if (is_endless_head(m, n)) {
817 res_index = smallest_dfn_pred(m, get_irg_dfn(m) + 1);
818 if (res_index == -2) /* no smallest dfn pred found. */
819 res_index = largest_dfn_pred(m);
822 if (m == n) { break; } /* It's not an unreachable loop, either. */
824 //assert(0 && "no head found on stack");
828 assert (res_index > -2);
830 set_irg_callee_backedge(m, res_index);
831 return get_irg_callee(m, res_index);
834 static ir_graph *find_tail(ir_graph *n) {
836 int i, res_index = -2;
839 ir_graph *in_and_out = NULL;
840 ir_graph *only_in = NULL;
841 ir_graph *ip_in_and_out = NULL;
842 ir_graph *ip_only_in = NULL;
844 //printf("find tail for "); DDMG(n);
846 for (i = tos-1; i >= 0; --i) {
847 ir_graph *pred = (i < tos -1) ? stack[i+1] : n;
851 //printf(" found 1a! "); DDM;
853 if (is_ip_head(pred, m)) {
854 //printf(" found 1b! "); DDM;
857 } else if (!ip_only_in && is_endless_head(m, n)) {
859 //printf(" found 2a! "); DDM;
860 if (is_ip_head(pred, m)) {
861 //printf(" found 2b! "); DDM;
864 } else if (is_ip_head(pred, m)) {
865 //printf(" found 3! "); DDM; This happens for self recursions in the second
866 //assert(0); scc iteration (the one to flip the loop.)
869 if (ip_in_and_out) break; /* That's what we really want. */
871 if (m == n) break; /* Don't walk past n on the stack! */
875 if (!in_and_out && !only_in)
876 /* There is no loop */
880 /* Is there a head in the callgraph without a head in the
882 assert(in_and_out || only_in);
884 m = (ip_in_and_out) ? ip_in_and_out : ip_only_in;
887 m = (in_and_out) ? in_and_out : only_in;
889 //printf("*** head is "); DDMG(m);
891 res_index = smallest_dfn_pred(m, get_irg_dfn(m) + 1);
892 if (res_index == -2) /* no smallest dfn pred found. */
893 res_index = largest_dfn_pred(m);
895 set_irg_callee_backedge(m, res_index);
896 res = get_irg_callee(m, res_index);
897 //printf("*** tail is "); DDMG(res);
900 #endif /* INTERPROCEDURAL_VIEW */
902 /*-----------------------------------------------------------*
903 * The core algorithm. *
904 *-----------------------------------------------------------*/
907 static void cgscc(ir_graph *n) {
910 if (cg_irg_visited(n)) return;
911 mark_cg_irg_visited(n);
913 /* Initialize the node */
914 set_irg_dfn(n, current_dfn); /* Depth first number for this node */
915 set_irg_uplink(n, current_dfn); /* ... is default uplink. */
919 arity = get_irg_n_callees(n);
920 for (i = 0; i < arity; i++) {
922 if (is_irg_callee_backedge(n, i)) continue;
923 m = get_irg_callee(n, i);
925 /** This marks the backedge, but does it guarantee a correct loop tree? */
926 //if (m == n) { set_irg_callee_backedge(n, i); continue; }
929 if (irg_is_in_stack(m)) {
930 /* Uplink of m is smaller if n->m is a backedge.
931 Propagate the uplink to mark the cfloop. */
932 if (get_irg_uplink(m) < get_irg_uplink(n))
933 set_irg_uplink(n, get_irg_uplink(m));
937 if (get_irg_dfn(n) == get_irg_uplink(n)) {
938 /* This condition holds for
939 1) the node with the incoming backedge.
940 That is: We found a cfloop!
941 2) Straight line code, because no uplink has been propagated, so the
942 uplink still is the same as the dfn.
944 But n might not be a proper cfloop head for the analysis. Proper cfloop
945 heads are Block and Phi nodes. find_tail searches the stack for
946 Block's and Phi's and takes those nodes as cfloop heads for the current
947 cfloop instead and marks the incoming edge as backedge. */
949 ir_graph *tail = find_tail(n);
951 /* We have a cfloop, that is no straight line code,
952 because we found a cfloop head!
953 Next actions: Open a new cfloop on the cfloop tree and
954 try to find inner cfloops */
957 ir_loop *l = new_loop();
959 /* Remove the cfloop from the stack ... */
960 pop_scc_unmark_visit(n);
962 /* The current backedge has been marked, that is temporarily eliminated,
963 by find tail. Start the scc algorithm
964 anew on the subgraph thats left (the current cfloop without the backedge)
965 in order to find more inner cfloops. */
969 assert(cg_irg_visited(n));
979 * reset the backedge information for all callers in all irgs
981 static void reset_isbe(void) {
982 int i, n_irgs = get_irp_n_irgs();
984 for (i = 0; i < n_irgs; ++i) {
985 ir_graph *irg = get_irp_irg(i);
987 if (irg->caller_isbe)
988 xfree(irg->caller_isbe);
989 irg->caller_isbe = NULL;
991 if (irg->callee_isbe)
992 xfree(irg->callee_isbe);
993 irg->callee_isbe = NULL;
997 /* ----------------------------------------------------------------------------------- */
998 /* Another algorithm to compute recursion nesting depth */
999 /* Walk the callgraph. For each crossed edge increase the loop depth by the edge */
1000 /* weight. Assign graphs the maximal depth. */
1001 /* ----------------------------------------------------------------------------------- */
1003 static void compute_loop_depth(ir_graph *irg, void *env) {
1004 int current_nesting = *(int *) env;
1005 int old_nesting = irg->callgraph_loop_depth;
1006 ir_visited_t old_visited = get_cg_irg_visited(irg);
1011 if (cg_irg_visited(irg)) return;
1013 mark_cg_irg_visited(irg);
1015 //printf(" old: %d new %d master %d", old_visited, get_cg_irg_visited(irg), master_cg_visited); DDMG(irg);
1018 if (old_nesting < current_nesting)
1019 irg->callgraph_loop_depth = current_nesting;
1021 if (current_nesting > irp->max_callgraph_loop_depth)
1022 irp->max_callgraph_loop_depth = current_nesting;
1024 if ((old_visited +1 < get_cg_irg_visited(irg)) || /* not yet visited */
1025 (old_nesting < current_nesting)) { /* propagate larger nesting */
1026 /* Don't walk the graph, but a tree that is an unfolded graph. */
1027 n_callees = get_irg_n_callees(irg);
1028 for (i = 0; i < n_callees; i++) {
1029 ir_graph *m = get_irg_callee(irg, i);
1030 *(int *)env += get_irg_callee_loop_depth(irg, i);
1031 compute_loop_depth(m, env);
1032 *(int *)env -= get_irg_callee_loop_depth(irg, i);
1036 set_cg_irg_visited(irg, master_cg_visited-1);
1039 /* ------------------------------------------------------------------------------------ */
1040 /* Another algorithm to compute recursion nesting depth */
1041 /* Walk the callgraph. For each crossed loop increase the nesting depth by one. */
1042 /* Assign graphs the maximal nesting depth. Don't increase if passing loops more than */
1044 /* ------------------------------------------------------------------------------------ */
1047 /* For callees, we want to remember the Call nodes, too. */
1048 typedef struct ana_entry2 {
1049 ir_loop **loop_stack; /**< a stack of ir_loop entries */
1050 int tos; /**< the top of stack entry */
1051 int recursion_nesting;
1055 * push a loop entry on the stack
1057 static void push2(ana_entry2 *e, ir_loop *g) {
1058 if (ARR_LEN(e->loop_stack) == e->tos) {
1059 ARR_APP1(ir_loop *, e->loop_stack, g);
1061 e->loop_stack[e->tos] = g;
1067 * returns the top of stack and pop it
1069 static ir_loop *pop2(ana_entry2 *e) {
1070 return e->loop_stack[--e->tos];
1074 * check if a loop g in on the stack. Did not check the TOS.
1076 static int in_stack(ana_entry2 *e, ir_loop *g) {
1078 for (i = e->tos-1; i >= 0; --i) {
1079 if (e->loop_stack[i] == g) return 1;
1084 static void compute_rec_depth(ir_graph *irg, void *env) {
1085 ana_entry2 *e = (ana_entry2 *)env;
1086 ir_loop *l = irg->l;
1087 int depth, old_depth = irg->callgraph_recursion_depth;
1091 if (cg_irg_visited(irg))
1093 mark_cg_irg_visited(irg);
1095 /* -- compute and set the new nesting value -- */
1096 if ((l != irp->outermost_cg_loop) && !in_stack(e, l)) {
1098 e->recursion_nesting++;
1101 depth = e->recursion_nesting;
1103 if (old_depth < depth)
1104 irg->callgraph_recursion_depth = depth;
1106 if (depth > irp->max_callgraph_recursion_depth)
1107 irp->max_callgraph_recursion_depth = depth;
1109 /* -- spread the nesting value -- */
1110 if (depth == 0 || old_depth < depth) {
1111 /* Don't walk the graph, but a tree that is an unfolded graph.
1112 Therefore we unset the visited flag at the end. */
1113 n_callees = get_irg_n_callees(irg);
1114 for (i = 0; i < n_callees; ++i) {
1115 ir_graph *m = get_irg_callee(irg, i);
1116 compute_rec_depth(m, env);
1120 /* -- clean up -- */
1123 e->recursion_nesting--;
1125 set_cg_irg_visited(irg, master_cg_visited-1);
1129 /* ----------------------------------------------------------------------------------- */
1130 /* Another algorithm to compute the execution frequency of methods ignoring recursions. */
1131 /* Walk the callgraph. Ignore backedges. Use sum of execution frequencies of Call */
1132 /* nodes to evaluate a callgraph edge. */
1133 /* ----------------------------------------------------------------------------------- */
1135 /* Returns the method execution frequency of a graph. */
1136 double get_irg_method_execution_frequency(const ir_graph *irg) {
1137 return irg->method_execution_frequency;
1141 * Increase the method execution frequency to freq if its current value is
1142 * smaller then this.
1144 static void set_irg_method_execution_frequency(ir_graph *irg, double freq) {
1145 irg->method_execution_frequency = freq;
1147 if (irp->max_method_execution_frequency < freq)
1148 irp->max_method_execution_frequency = freq;
1151 static void compute_method_execution_frequency(ir_graph *irg, void *env) {
1158 if (cg_irg_visited(irg))
1161 /* We need the values of all predecessors (except backedges).
1162 So they must be marked. Else we will reach the node through
1163 one of the unmarked ones. */
1164 n_callers = get_irg_n_callers(irg);
1165 for (i = 0; i < n_callers; ++i) {
1166 ir_graph *m = get_irg_caller(irg, i);
1167 if (is_irg_caller_backedge(irg, i))
1169 if (!cg_irg_visited(m)) {
1173 mark_cg_irg_visited(irg);
1175 /* Compute the new frequency. */
1178 for (i = 0; i < n_callers; i++) {
1179 if (! is_irg_caller_backedge(irg, i)) {
1180 double edge_freq = get_irg_caller_method_execution_frequency(irg, i);
1181 assert(edge_freq >= 0);
1188 /* A starting point: method only called from outside,
1189 or only backedges as predecessors. */
1193 set_irg_method_execution_frequency(irg, freq);
1196 n_callees = get_irg_n_callees(irg);
1197 for (i = 0; i < n_callees; ++i) {
1198 compute_method_execution_frequency(get_irg_callee(irg, i), NULL);
1203 /* ----------------------------------------------------------------------------------- */
1204 /* The recursion stuff driver. */
1205 /* ----------------------------------------------------------------------------------- */
1207 /* Compute the backedges that represent recursions. */
1208 void find_callgraph_recursions(void) {
1210 struct obstack temp;
1214 /* -- compute the looptree. -- */
1216 /* The outermost graph. We start here. Then we start at all
1217 functions in irg list that are never called, then at the remaining
1218 unvisited ones. The third step is needed for functions that are not
1219 reachable from the outermost graph, but call themselves in a cycle. */
1220 assert(get_irp_main_irg());
1221 outermost_ir_graph = get_irp_main_irg();
1222 obstack_init(&temp);
1225 current_loop = NULL;
1226 new_loop(); /* sets current_loop */
1228 ++master_cg_visited;
1229 cgscc(outermost_ir_graph);
1230 n_irgs = get_irp_n_irgs();
1231 for (i = 0; i < n_irgs; ++i) {
1232 ir_graph *irg = get_irp_irg(i);
1233 if (!cg_irg_visited(irg) && get_irg_n_callers(irg) == 0)
1236 for (i = 0; i < n_irgs; ++i) {
1237 ir_graph *irg = get_irp_irg(i);
1238 if (!cg_irg_visited(irg))
1241 obstack_free(&temp, NULL);
1243 irp->outermost_cg_loop = current_loop;
1244 mature_loops(current_loop, outermost_ir_graph->obst);
1246 /* -- Reverse the backedge information. -- */
1247 for (i = 0; i < n_irgs; ++i) {
1248 ir_graph *irg = get_irp_irg(i);
1249 int j, n_callees = get_irg_n_callees(irg);
1250 for (j = 0; j < n_callees; ++j) {
1251 if (is_irg_callee_backedge(irg, j))
1252 set_irg_caller_backedge(get_irg_callee(irg, j), irg);
1256 irp->callgraph_state = irp_callgraph_and_calltree_consistent;
1259 /* Compute interprocedural performance estimates. */
1260 void compute_performance_estimates(void) {
1261 int i, n_irgs = get_irp_n_irgs();
1262 int current_nesting;
1265 assert(get_irp_exec_freq_state() != exec_freq_none && "execution frequency not calculated");
1267 /* -- compute the loop depth -- */
1268 current_nesting = 0;
1269 irp->max_callgraph_loop_depth = 0;
1270 master_cg_visited += 2;
1271 //printf(" ** starting at "); DDMG(get_irp_main_irg());
1272 compute_loop_depth(get_irp_main_irg(), ¤t_nesting);
1273 for (i = 0; i < n_irgs; i++) {
1274 ir_graph *irg = get_irp_irg(i);
1275 if ((get_cg_irg_visited(irg) < master_cg_visited-1) &&
1276 get_irg_n_callers(irg) == 0) {
1277 compute_loop_depth(irg, ¤t_nesting);
1278 //printf(" ** starting at "); DDMG(irg);
1281 for (i = 0; i < n_irgs; i++) {
1282 ir_graph *irg = get_irp_irg(i);
1283 if (get_cg_irg_visited(irg) < master_cg_visited-1) {
1284 compute_loop_depth(irg, ¤t_nesting);
1285 //printf(" ** starting at "); DDMG(irg);
1290 /* -- compute the recursion depth -- */
1291 e.loop_stack = NEW_ARR_F(ir_loop *, 0);
1293 e.recursion_nesting = 0;
1295 irp->max_callgraph_recursion_depth = 0;
1297 master_cg_visited += 2;
1298 compute_rec_depth(get_irp_main_irg(), &e);
1299 //printf(" ++ starting at "); DDMG(get_irp_main_irg());
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_rec_depth(irg, &e);
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_rec_depth(irg, &e);
1312 //printf(" ++ starting at "); DDMG(irg);
1316 DEL_ARR_F(e.loop_stack);
1318 /* -- compute the execution frequency -- */
1319 irp->max_method_execution_frequency = 0;
1320 master_cg_visited += 2;
1321 assert(get_irg_n_callers(get_irp_main_irg()) == 0);
1322 compute_method_execution_frequency(get_irp_main_irg(), NULL);
1323 for (i = 0; i < n_irgs; i++) {
1324 ir_graph *irg = get_irp_irg(i);
1325 if ((get_cg_irg_visited(irg) < master_cg_visited-1) &&
1326 get_irg_n_callers(irg) == 0) {
1327 compute_method_execution_frequency(irg, NULL);
1330 for (i = 0; i < n_irgs; i++) {
1331 ir_graph *irg = get_irp_irg(i);
1332 if (get_cg_irg_visited(irg) < master_cg_visited-1) {
1333 compute_method_execution_frequency(irg, NULL);
1338 /* Returns the maximal loop depth of all paths from an external visible method to
1340 int get_irg_loop_depth(const ir_graph *irg) {
1341 assert(irp->callgraph_state == irp_callgraph_consistent ||
1342 irp->callgraph_state == irp_callgraph_and_calltree_consistent);
1343 return irg->callgraph_loop_depth;
1346 /* Returns the maximal recursion depth of all paths from an external visible method to
1348 int get_irg_recursion_depth(const ir_graph *irg) {
1349 assert(irp->callgraph_state == irp_callgraph_and_calltree_consistent);
1350 return irg->callgraph_recursion_depth;
1353 /* Computes the interprocedural loop nesting information. */
1354 void analyse_loop_nesting_depth(void) {
1355 ir_entity **free_methods = NULL;
1358 /* establish preconditions. */
1359 if (get_irp_callee_info_state() != irg_callee_info_consistent) {
1360 cgana(&arr_len, &free_methods);
1363 if (irp_callgraph_consistent != get_irp_callgraph_state()) {
1364 compute_callgraph();
1367 find_callgraph_recursions();
1369 compute_performance_estimates();
1371 set_irp_loop_nesting_depth_state(loop_nesting_depth_consistent);
1374 loop_nesting_depth_state get_irp_loop_nesting_depth_state(void) {
1375 return irp->lnd_state;
1377 void set_irp_loop_nesting_depth_state(loop_nesting_depth_state s) {
1380 void set_irp_loop_nesting_depth_state_inconsistent(void) {
1381 if (irp->lnd_state == loop_nesting_depth_consistent)
1382 irp->lnd_state = loop_nesting_depth_inconsistent;