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
36 #include "callgraph.h"
40 #include "irgraph_t.h"
44 #include "execution_frequency.h"
49 #include "raw_bitset.h"
53 static ir_visited_t master_cg_visited = 0;
54 static INLINE int cg_irg_visited (ir_graph *n);
55 static INLINE void mark_cg_irg_visited(ir_graph *n);
56 static INLINE void set_cg_irg_visited (ir_graph *n, ir_visited_t i);
58 /** Returns the callgraph state of the program representation. */
59 irp_callgraph_state get_irp_callgraph_state(void) {
60 return irp->callgraph_state;
63 /* Sets the callgraph state of the program representation. */
64 void set_irp_callgraph_state(irp_callgraph_state s) {
65 irp->callgraph_state = s;
68 /* Returns the number of procedures that call the given irg. */
69 int get_irg_n_callers(ir_graph *irg) {
70 if (irg->callers) return ARR_LEN(irg->callers);
74 /* Returns the caller at position pos. */
75 ir_graph *get_irg_caller(ir_graph *irg, int pos) {
76 assert(pos >= 0 && pos < get_irg_n_callers(irg));
77 if (irg->callers) return irg->callers[pos];
81 /* Returns non-zero if the caller at position pos is "a backedge", i.e. a recursion. */
82 int is_irg_caller_backedge(ir_graph *irg, int pos) {
83 assert(pos >= 0 && pos < get_irg_n_callers(irg));
84 return irg->caller_isbe != NULL ? rbitset_is_set(irg->caller_isbe, pos) : 0;
87 /** Search the caller in the list of all callers and set it's backedge property. */
88 static void set_irg_caller_backedge(ir_graph *irg, ir_graph *caller) {
89 int i, n_callers = get_irg_n_callers(irg);
91 /* allocate a new array on demand */
92 if (irg->caller_isbe == NULL)
93 irg->caller_isbe = rbitset_malloc(n_callers);
94 for (i = 0; i < n_callers; ++i) {
95 if (get_irg_caller(irg, i) == caller) {
96 rbitset_set(irg->caller_isbe, i);
102 /* Returns non-zero if the irg has a backedge caller. */
103 int has_irg_caller_backedge(ir_graph *irg) {
104 int i, n_callers = get_irg_n_callers(irg);
106 if (irg->caller_isbe != NULL) {
107 for (i = 0; i < n_callers; ++i)
108 if (rbitset_is_set(irg->caller_isbe, i))
115 * Find the reversion position of a caller.
116 * Given the position pos_caller of an caller of irg, return
117 * irg's callee position on that caller.
119 static int reverse_pos(ir_graph *callee, int pos_caller) {
120 ir_graph *caller = get_irg_caller(callee, pos_caller);
121 /* search the other relation for the corresponding edge. */
123 int i, n_callees = get_irg_n_callees(caller);
124 for (i = 0; i < n_callees; ++i) {
125 if (get_irg_callee(caller, i) == callee) {
131 assert(pos_callee >= 0);
136 /* Returns the maximal loop depth of call nodes that call along this edge. */
137 int get_irg_caller_loop_depth(ir_graph *irg, int pos) {
138 ir_graph *caller = get_irg_caller(irg, pos);
139 int pos_callee = reverse_pos(irg, pos);
141 return get_irg_callee_loop_depth(caller, pos_callee);
145 /* Returns the number of procedures that are called by the given irg. */
146 int get_irg_n_callees(ir_graph *irg) {
147 if (irg->callees) return ARR_LEN(irg->callees);
151 /* Returns the callee at position pos. */
152 ir_graph *get_irg_callee(ir_graph *irg, int pos) {
153 assert(pos >= 0 && pos < get_irg_n_callees(irg));
154 if (irg->callees) return irg->callees[pos]->irg;
158 /* Returns non-zero if the callee at position pos is "a backedge", i.e. a recursion. */
159 int is_irg_callee_backedge(ir_graph *irg, int pos) {
160 assert(pos >= 0 && pos < get_irg_n_callees(irg));
161 return irg->callee_isbe != NULL ? rbitset_is_set(irg->callee_isbe, pos) : 0;
164 /* Returns non-zero if the irg has a backedge callee. */
165 int has_irg_callee_backedge(ir_graph *irg) {
166 int i, n_callees = get_irg_n_callees(irg);
168 if (irg->callee_isbe != NULL) {
169 for (i = 0; i < n_callees; ++i)
170 if (rbitset_is_set(irg->callee_isbe, i))
177 * Mark the callee at position pos as a backedge.
179 static void set_irg_callee_backedge(ir_graph *irg, int pos) {
180 int n = get_irg_n_callees(irg);
182 /* allocate a new array on demand */
183 if (irg->callee_isbe == NULL)
184 irg->callee_isbe = rbitset_malloc(n);
185 assert(pos >= 0 && pos < n);
186 rbitset_set(irg->callee_isbe, pos);
189 /* Returns the maximal loop depth of call nodes that call along this edge. */
190 int get_irg_callee_loop_depth(ir_graph *irg, int pos) {
191 assert(pos >= 0 && pos < get_irg_n_callees(irg));
192 if (irg->callees) return irg->callees[pos]->max_depth;
197 double get_irg_callee_execution_frequency(ir_graph *irg, int pos) {
198 ir_node **arr = irg->callees[pos]->call_list;
199 int i, n_Calls = ARR_LEN(arr);
202 for (i = 0; i < n_Calls; ++i) {
203 freq += get_irn_exec_freq(arr[i]);
208 double get_irg_callee_method_execution_frequency(ir_graph *irg, int pos) {
209 double call_freq = get_irg_callee_execution_frequency(irg, pos);
210 double meth_freq = get_irg_method_execution_frequency(irg);
211 return call_freq * meth_freq;
215 double get_irg_caller_method_execution_frequency(ir_graph *irg, int pos) {
216 ir_graph *caller = get_irg_caller(irg, pos);
217 int pos_callee = reverse_pos(irg, pos);
219 return get_irg_callee_method_execution_frequency(caller, pos_callee);
224 /* --------------------- Compute the callgraph ------------------------ */
227 * Walker called by compute_callgraph(), analyses all Call nodes.
229 static void ana_Call(ir_node *n, void *env) {
234 if (! is_Call(n)) return;
236 irg = get_irn_irg(n);
237 n_callees = get_Call_n_callees(n);
238 for (i = 0; i < n_callees; ++i) {
239 ir_entity *callee_e = get_Call_callee(n, i);
240 ir_graph *callee = get_entity_irg(callee_e);
244 cg_callee_entry *found;
249 pset_insert((pset *)callee->callers, irg, HASH_PTR(irg));
250 found = pset_find((pset *)irg->callees, &buf, HASH_PTR(callee));
251 if (found) { /* add Call node to list, compute new nesting. */
252 ir_node **arr = found->call_list;
253 ARR_APP1(ir_node *, arr, n);
254 found->call_list = arr;
255 } else { /* New node, add Call node and init nesting. */
256 found = (cg_callee_entry *)obstack_alloc(irg->obst, sizeof(*found));
258 found->call_list = NEW_ARR_F(ir_node *, 1);
259 found->call_list[0] = n;
260 found->max_depth = 0;
261 pset_insert((pset *)irg->callees, found, HASH_PTR(callee));
263 depth = get_loop_depth(get_irn_loop(get_nodes_block(n)));
264 found->max_depth = (depth > found->max_depth) ? depth : found->max_depth;
269 /** compare two ir graphs in a cg_callee_entry */
270 static int cg_callee_entry_cmp(const void *elt, const void *key) {
271 const cg_callee_entry *e1 = elt;
272 const cg_callee_entry *e2 = key;
273 return e1->irg != e2->irg;
276 /** compare two ir graphs for pointer identity */
277 static int graph_cmp(const void *elt, const void *key) {
278 const ir_graph *e1 = elt;
279 const ir_graph *e2 = key;
284 /* Construct and destruct the callgraph. */
285 void compute_callgraph(void) {
288 #ifdef INTERPROCEDURAL_VIEW
289 assert(! get_interprocedural_view()); /* Else walking will not reach the Call nodes. */
295 n_irgs = get_irp_n_irgs();
296 for (i = 0; i < n_irgs; ++i) {
297 ir_graph *irg = get_irp_irg(i);
298 assert(get_irg_callee_info_state(irg) == irg_callee_info_consistent);
299 irg->callees = (cg_callee_entry **)new_pset(cg_callee_entry_cmp, 8);
300 irg->callers = (ir_graph **)new_pset(graph_cmp, 8);
301 //construct_cf_backedges(irg);
304 /* Compute the call graph */
305 for (i = 0; i < n_irgs; ++i) {
306 ir_graph *irg = get_irp_irg(i);
307 construct_cf_backedges(irg); // We also find the maximal loop depth of a call.
308 irg_walk_graph(irg, ana_Call, NULL, NULL);
311 /* Change the sets to arrays. */
312 for (i = 0; i < n_irgs; ++i) {
314 cg_callee_entry *callee;
315 ir_graph *c, *irg = get_irp_irg(i);
316 pset *callee_set, *caller_set;
318 callee_set = (pset *)irg->callees;
319 count = pset_count(callee_set);
320 irg->callees = NEW_ARR_F(cg_callee_entry *, count);
321 irg->callee_isbe = NULL;
322 callee = pset_first(callee_set);
323 for (j = 0; j < count; ++j) {
324 irg->callees[j] = callee;
325 callee = pset_next(callee_set);
327 del_pset(callee_set);
328 assert(callee == NULL);
330 caller_set = (pset *)irg->callers;
331 count = pset_count(caller_set);
332 irg->callers = NEW_ARR_F(ir_graph *, count);
333 irg->caller_isbe = NULL;
334 c = pset_first(caller_set);
335 for (j = 0; j < count; ++j) {
337 c = pset_next(caller_set);
339 del_pset(caller_set);
342 set_irp_callgraph_state(irp_callgraph_consistent);
345 /* Destruct the callgraph. */
346 void free_callgraph(void) {
347 int i, n_irgs = get_irp_n_irgs();
348 for (i = 0; i < n_irgs; ++i) {
349 ir_graph *irg = get_irp_irg(i);
350 if (irg->callees) DEL_ARR_F(irg->callees);
351 if (irg->callers) DEL_ARR_F(irg->callers);
352 if (irg->callee_isbe) free(irg->callee_isbe);
353 if (irg->caller_isbe) free(irg->caller_isbe);
356 irg->callee_isbe = NULL;
357 irg->caller_isbe = NULL;
359 set_irp_callgraph_state(irp_callgraph_none);
362 /* ----------------------------------------------------------------------------------- */
363 /* A walker for the callgraph */
364 /* ----------------------------------------------------------------------------------- */
367 static void do_walk(ir_graph *irg, callgraph_walk_func *pre, callgraph_walk_func *post, void *env) {
370 if (cg_irg_visited(irg))
372 mark_cg_irg_visited(irg);
377 n_callees = get_irg_n_callees(irg);
378 for (i = 0; i < n_callees; i++) {
379 ir_graph *m = get_irg_callee(irg, i);
380 do_walk(m, pre, post, env);
387 void callgraph_walk(callgraph_walk_func *pre, callgraph_walk_func *post, void *env) {
388 int i, n_irgs = get_irp_n_irgs();
391 /* roots are methods which have no callers in the current program */
392 for (i = 0; i < n_irgs; ++i) {
393 ir_graph *irg = get_irp_irg(i);
395 if (get_irg_n_callers(irg) == 0)
396 do_walk(irg, pre, post, env);
399 /* in case of unreachable call loops we haven't visited some irgs yet */
400 for (i = 0; i < n_irgs; i++) {
401 ir_graph *irg = get_irp_irg(i);
402 do_walk(irg, pre, post, env);
406 /* ----------------------------------------------------------------------------------- */
407 /* loop construction algorithm */
408 /* ----------------------------------------------------------------------------------- */
410 static ir_graph *outermost_ir_graph; /**< The outermost graph the scc is computed
412 static ir_loop *current_loop; /**< Current cfloop construction is working
414 static int loop_node_cnt = 0; /**< Counts the number of allocated cfloop nodes.
415 Each cfloop node gets a unique number.
416 What for? ev. remove. @@@ */
417 static int current_dfn = 1; /**< Counter to generate depth first numbering
420 /*-----------------*/
421 /* Node attributes */
422 /*-----------------*/
424 typedef struct scc_info {
425 int in_stack; /**< Marks whether node is on the stack. */
426 int dfn; /**< Depth first search number. */
427 int uplink; /**< dfn number of ancestor. */
432 * allocates a new scc_info on the obstack
434 static INLINE scc_info *new_scc_info(struct obstack *obst) {
435 scc_info *info = obstack_alloc(obst, sizeof(*info));
436 memset(info, 0, sizeof(*info));
441 * Returns non-zero if a graph was already visited.
443 static INLINE int cg_irg_visited(ir_graph *irg) {
444 return irg->self_visited >= master_cg_visited;
448 * Marks a graph as visited.
450 static INLINE void mark_cg_irg_visited(ir_graph *irg) {
451 irg->self_visited = master_cg_visited;
455 * Set a graphs visited flag to i.
457 static INLINE void set_cg_irg_visited(ir_graph *irg, ir_visited_t i) {
458 irg->self_visited = i;
462 * Returns the visited flag of a graph.
464 static INLINE ir_visited_t get_cg_irg_visited(ir_graph *irg) {
465 return irg->self_visited;
468 static INLINE void mark_irg_in_stack(ir_graph *irg) {
469 scc_info *info = get_irg_link(irg);
470 assert(info && "missing call to init_scc()");
474 static INLINE void mark_irg_not_in_stack(ir_graph *irg) {
475 scc_info *info = get_irg_link(irg);
476 assert(info && "missing call to init_scc()");
480 static INLINE int irg_is_in_stack(ir_graph *irg) {
481 scc_info *info = get_irg_link(irg);
482 assert(info && "missing call to init_scc()");
483 return info->in_stack;
486 static INLINE void set_irg_uplink(ir_graph *irg, int uplink) {
487 scc_info *info = get_irg_link(irg);
488 assert(info && "missing call to init_scc()");
489 info->uplink = uplink;
492 static INLINE int get_irg_uplink(ir_graph *irg) {
493 scc_info *info = get_irg_link(irg);
494 assert(info && "missing call to init_scc()");
498 static INLINE void set_irg_dfn(ir_graph *irg, int dfn) {
499 scc_info *info = get_irg_link(irg);
500 assert(info && "missing call to init_scc()");
504 static INLINE int get_irg_dfn(ir_graph *irg) {
505 scc_info *info = get_irg_link(irg);
506 assert(info && "missing call to init_scc()");
510 /**********************************************************************/
512 /**********************************************************************/
514 static ir_graph **stack = NULL;
515 static int tos = 0; /**< top of stack */
518 * Initialize the irg stack.
520 static INLINE void init_stack(void) {
522 ARR_RESIZE(ir_graph *, stack, 1000);
524 stack = NEW_ARR_F(ir_graph *, 1000);
530 * push a graph on the irg stack
531 * @param n the graph to be pushed
533 static INLINE void push(ir_graph *irg) {
534 if (tos == ARR_LEN(stack)) {
535 int nlen = ARR_LEN(stack) * 2;
536 ARR_RESIZE(ir_node *, stack, nlen);
539 mark_irg_in_stack(irg);
543 * return the topmost graph on the stack and pop it
545 static INLINE ir_graph *pop(void) {
546 ir_graph *irg = stack[--tos];
547 mark_irg_not_in_stack(irg);
552 * The nodes up to irg belong to the current loop.
553 * Removes them from the stack and adds them to the current loop.
555 static INLINE void pop_scc_to_loop(ir_graph *irg) {
561 set_irg_dfn(m, loop_node_cnt);
562 add_loop_irg(current_loop, m);
564 //m->callgraph_loop_depth = current_loop->depth;
568 /* GL ??? my last son is my grandson??? Removes cfloops with no
569 ir_nodes in them. Such loops have only another loop as son. (Why
570 can't they have two loops as sons? Does it never get that far? ) */
571 static void close_loop(ir_loop *l) {
572 int last = get_loop_n_elements(l) - 1;
573 loop_element lelement = get_loop_element(l, last);
574 ir_loop *last_son = lelement.son;
576 if (get_kind(last_son) == k_ir_loop &&
577 get_loop_n_elements(last_son) == 1) {
580 lelement = get_loop_element(last_son, 0);
582 if (get_kind(gson) == k_ir_loop) {
583 loop_element new_last_son;
585 gson->outer_loop = l;
586 new_last_son.son = gson;
587 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 = current_loop;
616 ir_loop *son = alloc_loop(father, outermost_ir_graph->obst);
623 /**********************************************************************/
624 /* Constructing and destructing the loop/backedge information. **/
625 /**********************************************************************/
627 /* Initialization steps. **********************************************/
629 static void init_scc(struct obstack *obst) {
637 n_irgs = get_irp_n_irgs();
638 for (i = 0; i < n_irgs; ++i) {
639 ir_graph *irg = get_irp_irg(i);
640 set_irg_link(irg, new_scc_info(obst));
641 irg->callgraph_recursion_depth = 0;
642 irg->callgraph_loop_depth = 0;
646 /** Returns non-zero if n is a loop header, i.e., it is a Block node
647 * and has predecessors within the cfloop and out of the cfloop.
649 * @param root: only needed for assertion.
651 static int is_head(ir_graph *n, ir_graph *root) {
653 int some_outof_loop = 0, some_in_loop = 0;
655 arity = get_irg_n_callees(n);
656 for (i = 0; i < arity; i++) {
657 ir_graph *pred = get_irg_callee(n, i);
658 if (is_irg_callee_backedge(n, i)) continue;
659 if (!irg_is_in_stack(pred)) {
662 if (get_irg_uplink(pred) < get_irg_uplink(root)) {
663 assert(get_irg_uplink(pred) >= get_irg_uplink(root));
669 return some_outof_loop & some_in_loop;
673 * Returns non-zero if n is possible loop head of an endless loop.
674 * I.e., it is a Block, Phi or Filter node and has only predecessors
676 * @arg root: only needed for assertion.
678 static int is_endless_head(ir_graph *n, ir_graph *root)
681 int some_outof_loop = 0, some_in_loop = 0;
683 arity = get_irg_n_callees(n);
684 for (i = 0; i < arity; i++) {
685 ir_graph *pred = get_irg_callee(n, i);
687 if (is_irg_callee_backedge(n, i))
689 if (!irg_is_in_stack(pred)) {
692 if (get_irg_uplink(pred) < get_irg_uplink(root)) {
693 assert(get_irg_uplink(pred) >= get_irg_uplink(root));
698 return !some_outof_loop & some_in_loop;
701 #ifdef INTERPROCEDURAL_VIEW
703 * Check whether there is a parallel edge in the ip control flow.
706 static int is_ip_head(ir_graph *n, ir_graph *pred)
710 int iv_rem = get_interprocedural_view();
711 set_interprocedural_view(1);
713 ir_node *sblock = get_irg_start_block(n);
714 int i, arity = get_Block_n_cfgpreds(sblock);
716 //printf(" edge from "); DDMG(n);
717 //printf(" to pred "); DDMG(pred);
718 //printf(" sblock "); DDMN(sblock);
720 for (i = 0; i < arity; i++) {
721 ir_node *pred_cfop = skip_Proj(get_Block_cfgpred(sblock, i));
722 //printf(" "); DDMN(pred_cfop);
723 if (is_CallBegin(pred_cfop)) { /* could be Unknown */
724 ir_graph *ip_pred = get_irn_irg(pred_cfop);
725 //printf(" "); DDMG(ip_pred);
726 if ((ip_pred == pred) && is_backedge(sblock, i)) {
727 //printf(" found\n");
733 set_interprocedural_view(iv_rem);
736 #endif /* INTERPROCEDURAL_VIEW */
739 * Returns index of the predecessor with the smallest dfn number
740 * greater-equal than limit.
742 static int smallest_dfn_pred(ir_graph *n, int limit)
744 int i, index = -2, min = -1;
746 int arity = get_irg_n_callees(n);
747 for (i = 0; i < arity; i++) {
748 ir_graph *pred = get_irg_callee(n, i);
749 if (is_irg_callee_backedge(n, i) || !irg_is_in_stack(pred))
751 if (get_irg_dfn(pred) >= limit && (min == -1 || get_irg_dfn(pred) < min)) {
753 min = get_irg_dfn(pred);
760 /** Returns index of the predecessor with the largest dfn number. */
761 static int largest_dfn_pred(ir_graph *n) {
762 int i, index = -2, max = -1;
764 int arity = get_irg_n_callees(n);
765 for (i = 0; i < arity; ++i) {
766 ir_graph *pred = get_irg_callee(n, i);
767 if (is_irg_callee_backedge (n, i) || !irg_is_in_stack(pred)) continue;
768 if (get_irg_dfn(pred) > max) {
770 max = get_irg_dfn(pred);
777 #ifndef INTERPROCEDURAL_VIEW
778 static ir_graph *find_tail(ir_graph *n) {
780 int i, res_index = -2;
783 if (!icfg && rm_cyclic_phis && remove_cyclic_phis (n)) return NULL;
785 m = stack[tos-1]; /* tos = top of stack */
786 if (is_head (m, n)) {
787 res_index = smallest_dfn_pred(m, 0);
788 if ((res_index == -2) && /* no smallest dfn pred found. */
792 if (m == n) return NULL; // Is this to catch Phi - self loops?
793 for (i = tos-2; i >= 0; --i) {
797 res_index = smallest_dfn_pred(m, get_irg_dfn(m) + 1);
798 if (res_index == -2) /* no smallest dfn pred found. */
799 res_index = largest_dfn_pred(m);
801 if ((m == n) && (res_index == -2)) {
807 /* We should not walk past our selves on the stack: The upcoming nodes
808 are not in this loop. We assume a loop not reachable from Start. */
817 /* A dead loop not reachable from Start. */
818 for (i = tos-2; i >= 0; --i) {
820 if (is_endless_head(m, n)) {
821 res_index = smallest_dfn_pred(m, get_irg_dfn(m) + 1);
822 if (res_index == -2) /* no smallest dfn pred found. */
823 res_index = largest_dfn_pred(m);
826 if (m == n) { break; } /* It's not an unreachable loop, either. */
828 //assert(0 && "no head found on stack");
832 assert (res_index > -2);
834 set_irg_callee_backedge(m, res_index);
835 return get_irg_callee(m, res_index);
838 static ir_graph *find_tail(ir_graph *n) {
840 int i, res_index = -2;
843 ir_graph *in_and_out = NULL;
844 ir_graph *only_in = NULL;
845 ir_graph *ip_in_and_out = NULL;
846 ir_graph *ip_only_in = NULL;
848 //printf("find tail for "); DDMG(n);
850 for (i = tos-1; i >= 0; --i) {
851 ir_graph *pred = (i < tos -1) ? stack[i+1] : n;
855 //printf(" found 1a! "); DDM;
857 if (is_ip_head(pred, m)) {
858 //printf(" found 1b! "); DDM;
861 } else if (!ip_only_in && is_endless_head(m, n)) {
863 //printf(" found 2a! "); DDM;
864 if (is_ip_head(pred, m)) {
865 //printf(" found 2b! "); DDM;
868 } else if (is_ip_head(pred, m)) {
869 //printf(" found 3! "); DDM; This happens for self recursions in the second
870 //assert(0); scc iteration (the one to flip the loop.)
873 if (ip_in_and_out) break; /* That's what we really want. */
875 if (m == n) break; /* Don't walk past n on the stack! */
879 if (!in_and_out && !only_in)
880 /* There is no loop */
884 /* Is there a head in the callgraph without a head in the
886 assert(in_and_out || only_in);
888 m = (ip_in_and_out) ? ip_in_and_out : ip_only_in;
891 m = (in_and_out) ? in_and_out : only_in;
893 //printf("*** head is "); DDMG(m);
895 res_index = smallest_dfn_pred(m, get_irg_dfn(m) + 1);
896 if (res_index == -2) /* no smallest dfn pred found. */
897 res_index = largest_dfn_pred(m);
899 set_irg_callee_backedge(m, res_index);
900 res = get_irg_callee(m, res_index);
901 //printf("*** tail is "); DDMG(res);
904 #endif /* INTERPROCEDURAL_VIEW */
906 /*-----------------------------------------------------------*
907 * The core algorithm. *
908 *-----------------------------------------------------------*/
911 static void cgscc(ir_graph *n) {
914 if (cg_irg_visited(n)) return;
915 mark_cg_irg_visited(n);
917 /* Initialize the node */
918 set_irg_dfn(n, current_dfn); /* Depth first number for this node */
919 set_irg_uplink(n, current_dfn); /* ... is default uplink. */
923 arity = get_irg_n_callees(n);
924 for (i = 0; i < arity; i++) {
926 if (is_irg_callee_backedge(n, i)) continue;
927 m = get_irg_callee(n, i);
929 /** This marks the backedge, but does it guarantee a correct loop tree? */
930 //if (m == n) { set_irg_callee_backedge(n, i); continue; }
933 if (irg_is_in_stack(m)) {
934 /* Uplink of m is smaller if n->m is a backedge.
935 Propagate the uplink to mark the cfloop. */
936 if (get_irg_uplink(m) < get_irg_uplink(n))
937 set_irg_uplink(n, get_irg_uplink(m));
941 if (get_irg_dfn(n) == get_irg_uplink(n)) {
942 /* This condition holds for
943 1) the node with the incoming backedge.
944 That is: We found a cfloop!
945 2) Straight line code, because no uplink has been propagated, so the
946 uplink still is the same as the dfn.
948 But n might not be a proper cfloop head for the analysis. Proper cfloop
949 heads are Block and Phi nodes. find_tail searches the stack for
950 Block's and Phi's and takes those nodes as cfloop heads for the current
951 cfloop instead and marks the incoming edge as backedge. */
953 ir_graph *tail = find_tail(n);
955 /* We have a cfloop, that is no straight line code,
956 because we found a cfloop head!
957 Next actions: Open a new cfloop on the cfloop tree and
958 try to find inner cfloops */
961 ir_loop *l = new_loop();
963 /* Remove the cfloop from the stack ... */
964 pop_scc_unmark_visit(n);
966 /* The current backedge has been marked, that is temporarily eliminated,
967 by find tail. Start the scc algorithm
968 anew on the subgraph thats left (the current cfloop without the backedge)
969 in order to find more inner cfloops. */
973 assert(cg_irg_visited(n));
983 * reset the backedge information for all callers in all irgs
985 static void reset_isbe(void) {
986 int i, n_irgs = get_irp_n_irgs();
988 for (i = 0; i < n_irgs; ++i) {
989 ir_graph *irg = get_irp_irg(i);
991 if (irg->caller_isbe)
992 xfree(irg->caller_isbe);
993 irg->caller_isbe = NULL;
995 if (irg->callee_isbe)
996 xfree(irg->callee_isbe);
997 irg->callee_isbe = NULL;
1001 /* ----------------------------------------------------------------------------------- */
1002 /* Another algorithm to compute recursion nesting depth */
1003 /* Walk the callgraph. For each crossed edge increase the loop depth by the edge */
1004 /* weight. Assign graphs the maximal depth. */
1005 /* ----------------------------------------------------------------------------------- */
1007 static void compute_loop_depth(ir_graph *irg, void *env) {
1008 int current_nesting = *(int *) env;
1009 int old_nesting = irg->callgraph_loop_depth;
1010 ir_visited_t old_visited = get_cg_irg_visited(irg);
1015 if (cg_irg_visited(irg)) return;
1017 mark_cg_irg_visited(irg);
1019 //printf(" old: %d new %d master %d", old_visited, get_cg_irg_visited(irg), master_cg_visited); DDMG(irg);
1022 if (old_nesting < current_nesting)
1023 irg->callgraph_loop_depth = current_nesting;
1025 if (current_nesting > irp->max_callgraph_loop_depth)
1026 irp->max_callgraph_loop_depth = current_nesting;
1028 if ((old_visited +1 < get_cg_irg_visited(irg)) || /* not yet visited */
1029 (old_nesting < current_nesting)) { /* propagate larger nesting */
1030 /* Don't walk the graph, but a tree that is an unfolded graph. */
1031 n_callees = get_irg_n_callees(irg);
1032 for (i = 0; i < n_callees; i++) {
1033 ir_graph *m = get_irg_callee(irg, i);
1034 *(int *)env += get_irg_callee_loop_depth(irg, i);
1035 compute_loop_depth(m, env);
1036 *(int *)env -= get_irg_callee_loop_depth(irg, i);
1040 set_cg_irg_visited(irg, master_cg_visited-1);
1043 /* ------------------------------------------------------------------------------------ */
1044 /* Another algorithm to compute recursion nesting depth */
1045 /* Walk the callgraph. For each crossed loop increase the nesting depth by one. */
1046 /* Assign graphs the maximal nesting depth. Don't increase if passing loops more than */
1048 /* ------------------------------------------------------------------------------------ */
1051 /* For callees, we want to remember the Call nodes, too. */
1052 typedef struct ana_entry2 {
1053 ir_loop **loop_stack; /**< a stack of ir_loop entries */
1054 int tos; /**< the top of stack entry */
1055 int recursion_nesting;
1059 * push a loop entry on the stack
1061 static void push2(ana_entry2 *e, ir_loop *g) {
1062 if (ARR_LEN(e->loop_stack) == e->tos) {
1063 ARR_APP1(ir_loop *, e->loop_stack, g);
1065 e->loop_stack[e->tos] = g;
1071 * returns the top of stack and pop it
1073 static ir_loop *pop2(ana_entry2 *e) {
1074 return e->loop_stack[--e->tos];
1078 * check if a loop g in on the stack. Did not check the TOS.
1080 static int in_stack(ana_entry2 *e, ir_loop *g) {
1082 for (i = e->tos-1; i >= 0; --i) {
1083 if (e->loop_stack[i] == g) return 1;
1088 static void compute_rec_depth(ir_graph *irg, void *env) {
1089 ana_entry2 *e = (ana_entry2 *)env;
1090 ir_loop *l = irg->l;
1091 int depth, old_depth = irg->callgraph_recursion_depth;
1095 if (cg_irg_visited(irg))
1097 mark_cg_irg_visited(irg);
1099 /* -- compute and set the new nesting value -- */
1100 if ((l != irp->outermost_cg_loop) && !in_stack(e, l)) {
1102 e->recursion_nesting++;
1105 depth = e->recursion_nesting;
1107 if (old_depth < depth)
1108 irg->callgraph_recursion_depth = depth;
1110 if (depth > irp->max_callgraph_recursion_depth)
1111 irp->max_callgraph_recursion_depth = depth;
1113 /* -- spread the nesting value -- */
1114 if (depth == 0 || old_depth < depth) {
1115 /* Don't walk the graph, but a tree that is an unfolded graph.
1116 Therefore we unset the visited flag at the end. */
1117 n_callees = get_irg_n_callees(irg);
1118 for (i = 0; i < n_callees; ++i) {
1119 ir_graph *m = get_irg_callee(irg, i);
1120 compute_rec_depth(m, env);
1124 /* -- clean up -- */
1127 e->recursion_nesting--;
1129 set_cg_irg_visited(irg, master_cg_visited-1);
1133 /* ----------------------------------------------------------------------------------- */
1134 /* Another algorithm to compute the execution frequency of methods ignoring recursions. */
1135 /* Walk the callgraph. Ignore backedges. Use sum of execution frequencies of Call */
1136 /* nodes to evaluate a callgraph edge. */
1137 /* ----------------------------------------------------------------------------------- */
1139 /* Returns the method execution frequency of a graph. */
1140 double get_irg_method_execution_frequency(ir_graph *irg) {
1141 return irg->method_execution_frequency;
1145 * Increase the method execution frequency to freq if its current value is
1146 * smaller then this.
1148 static void set_irg_method_execution_frequency(ir_graph *irg, double freq) {
1149 irg->method_execution_frequency = freq;
1151 if (irp->max_method_execution_frequency < freq)
1152 irp->max_method_execution_frequency = freq;
1155 static void compute_method_execution_frequency(ir_graph *irg, void *env) {
1162 if (cg_irg_visited(irg))
1165 /* We need the values of all predecessors (except backedges).
1166 So they must be marked. Else we will reach the node through
1167 one of the unmarked ones. */
1168 n_callers = get_irg_n_callers(irg);
1169 for (i = 0; i < n_callers; ++i) {
1170 ir_graph *m = get_irg_caller(irg, i);
1171 if (is_irg_caller_backedge(irg, i))
1173 if (!cg_irg_visited(m)) {
1177 mark_cg_irg_visited(irg);
1179 /* Compute the new frequency. */
1182 for (i = 0; i < n_callers; i++) {
1183 if (! is_irg_caller_backedge(irg, i)) {
1184 double edge_freq = get_irg_caller_method_execution_frequency(irg, i);
1185 assert(edge_freq >= 0);
1192 /* A starting point: method only called from outside,
1193 or only backedges as predecessors. */
1197 set_irg_method_execution_frequency(irg, freq);
1200 n_callees = get_irg_n_callees(irg);
1201 for (i = 0; i < n_callees; ++i) {
1202 compute_method_execution_frequency(get_irg_callee(irg, i), NULL);
1207 /* ----------------------------------------------------------------------------------- */
1208 /* The recursion stuff driver. */
1209 /* ----------------------------------------------------------------------------------- */
1211 /* Compute the backedges that represent recursions. */
1212 void find_callgraph_recursions(void) {
1213 int i, n_irgs = get_irp_n_irgs();
1214 struct obstack temp;
1218 /* -- compute the looptree. -- */
1220 /* The outermost graph. We start here. Then we start at all
1221 functions in irg list that are never called, then at the remaining
1222 unvisited ones. The third step is needed for functions that are not
1223 reachable from the outermost graph, but call themselves in a cycle. */
1224 assert(get_irp_main_irg());
1225 outermost_ir_graph = get_irp_main_irg();
1226 obstack_init(&temp);
1229 current_loop = NULL;
1230 new_loop(); /* sets current_loop */
1232 ++master_cg_visited;
1233 cgscc(outermost_ir_graph);
1234 for (i = 0; i < n_irgs; ++i) {
1235 ir_graph *irg = get_irp_irg(i);
1236 if (!cg_irg_visited(irg) && get_irg_n_callers(irg) == 0)
1239 for (i = 0; i < n_irgs; ++i) {
1240 ir_graph *irg = get_irp_irg(i);
1241 if (!cg_irg_visited(irg))
1244 obstack_free(&temp, NULL);
1246 irp->outermost_cg_loop = current_loop;
1247 mature_loops(current_loop, outermost_ir_graph->obst);
1249 /* -- Reverse the backedge information. -- */
1250 for (i = 0; i < n_irgs; ++i) {
1251 ir_graph *irg = get_irp_irg(i);
1252 int j, n_callees = get_irg_n_callees(irg);
1253 for (j = 0; j < n_callees; ++j) {
1254 if (is_irg_callee_backedge(irg, j))
1255 set_irg_caller_backedge(get_irg_callee(irg, j), irg);
1259 irp->callgraph_state = irp_callgraph_and_calltree_consistent;
1262 /* Compute interprocedural performance estimates. */
1263 void compute_performance_estimates(void) {
1264 int i, n_irgs = get_irp_n_irgs();
1265 int current_nesting;
1268 assert(get_irp_exec_freq_state() != exec_freq_none && "execution frequency not calculated");
1270 /* -- compute the loop depth -- */
1271 current_nesting = 0;
1272 irp->max_callgraph_loop_depth = 0;
1273 master_cg_visited += 2;
1274 //printf(" ** starting at "); DDMG(get_irp_main_irg());
1275 compute_loop_depth(get_irp_main_irg(), ¤t_nesting);
1276 for (i = 0; i < n_irgs; i++) {
1277 ir_graph *irg = get_irp_irg(i);
1278 if ((get_cg_irg_visited(irg) < master_cg_visited-1) &&
1279 get_irg_n_callers(irg) == 0) {
1280 compute_loop_depth(irg, ¤t_nesting);
1281 //printf(" ** starting at "); DDMG(irg);
1284 for (i = 0; i < n_irgs; i++) {
1285 ir_graph *irg = get_irp_irg(i);
1286 if (get_cg_irg_visited(irg) < master_cg_visited-1) {
1287 compute_loop_depth(irg, ¤t_nesting);
1288 //printf(" ** starting at "); DDMG(irg);
1293 /* -- compute the recursion depth -- */
1294 e.loop_stack = NEW_ARR_F(ir_loop *, 0);
1296 e.recursion_nesting = 0;
1298 irp->max_callgraph_recursion_depth = 0;
1300 master_cg_visited += 2;
1301 compute_rec_depth(get_irp_main_irg(), &e);
1302 //printf(" ++ starting at "); DDMG(get_irp_main_irg());
1303 for (i = 0; i < n_irgs; i++) {
1304 ir_graph *irg = get_irp_irg(i);
1305 if ((get_cg_irg_visited(irg) < master_cg_visited-1) &&
1306 get_irg_n_callers(irg) == 0) {
1307 compute_rec_depth(irg, &e);
1308 //printf(" ++ starting at "); DDMG(irg);
1311 for (i = 0; i < n_irgs; i++) {
1312 ir_graph *irg = get_irp_irg(i);
1313 if (get_cg_irg_visited(irg) < master_cg_visited-1) {
1314 compute_rec_depth(irg, &e);
1315 //printf(" ++ starting at "); DDMG(irg);
1319 DEL_ARR_F(e.loop_stack);
1321 /* -- compute the execution frequency -- */
1322 irp->max_method_execution_frequency = 0;
1323 master_cg_visited += 2;
1324 assert(get_irg_n_callers(get_irp_main_irg()) == 0);
1325 compute_method_execution_frequency(get_irp_main_irg(), NULL);
1326 for (i = 0; i < n_irgs; i++) {
1327 ir_graph *irg = get_irp_irg(i);
1328 if ((get_cg_irg_visited(irg) < master_cg_visited-1) &&
1329 get_irg_n_callers(irg) == 0) {
1330 compute_method_execution_frequency(irg, NULL);
1333 for (i = 0; i < n_irgs; i++) {
1334 ir_graph *irg = get_irp_irg(i);
1335 if (get_cg_irg_visited(irg) < master_cg_visited-1) {
1336 compute_method_execution_frequency(irg, NULL);
1341 /* Returns the maximal loop depth of all paths from an external visible method to
1343 int get_irg_loop_depth(ir_graph *irg) {
1344 assert(irp->callgraph_state == irp_callgraph_consistent ||
1345 irp->callgraph_state == irp_callgraph_and_calltree_consistent);
1346 return irg->callgraph_loop_depth;
1349 /* Returns the maximal recursion depth of all paths from an external visible method to
1351 int get_irg_recursion_depth(ir_graph *irg) {
1352 assert(irp->callgraph_state == irp_callgraph_and_calltree_consistent);
1353 return irg->callgraph_recursion_depth;
1356 /* Computes the interprocedural loop nesting information. */
1357 void analyse_loop_nesting_depth(void) {
1358 ir_entity **free_methods = NULL;
1361 /* establish preconditions. */
1362 if (get_irp_callee_info_state() != irg_callee_info_consistent) {
1363 cgana(&arr_len, &free_methods);
1366 if (irp_callgraph_consistent != get_irp_callgraph_state()) {
1367 compute_callgraph();
1370 find_callgraph_recursions();
1372 compute_performance_estimates();
1374 set_irp_loop_nesting_depth_state(loop_nesting_depth_consistent);
1377 loop_nesting_depth_state get_irp_loop_nesting_depth_state(void) {
1378 return irp->lnd_state;
1380 void set_irp_loop_nesting_depth_state(loop_nesting_depth_state s) {
1383 void set_irp_loop_nesting_depth_state_inconsistent(void) {
1384 if (irp->lnd_state == loop_nesting_depth_consistent)
1385 irp->lnd_state = loop_nesting_depth_inconsistent;