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
38 #include "callgraph.h"
42 #include "irgraph_t.h"
46 #include "execution_frequency.h"
51 #include "raw_bitset.h"
55 static ir_visited_t master_cg_visited = 0;
56 static INLINE int cg_irg_visited (ir_graph *n);
57 static INLINE void mark_cg_irg_visited(ir_graph *n);
58 static INLINE void set_cg_irg_visited (ir_graph *n, ir_visited_t i);
60 /** Returns the callgraph state of the program representation. */
61 irp_callgraph_state get_irp_callgraph_state(void) {
62 return irp->callgraph_state;
65 /* Sets the callgraph state of the program representation. */
66 void set_irp_callgraph_state(irp_callgraph_state s) {
67 irp->callgraph_state = s;
70 /* Returns the number of procedures that call the given irg. */
71 int get_irg_n_callers(ir_graph *irg) {
72 if (irg->callers) return ARR_LEN(irg->callers);
76 /* Returns the caller at position pos. */
77 ir_graph *get_irg_caller(ir_graph *irg, int pos) {
78 assert(pos >= 0 && pos < get_irg_n_callers(irg));
79 if (irg->callers) return irg->callers[pos];
83 /* Returns non-zero if the caller at position pos is "a backedge", i.e. a recursion. */
84 int is_irg_caller_backedge(ir_graph *irg, int pos) {
85 assert(pos >= 0 && pos < get_irg_n_callers(irg));
86 return irg->caller_isbe != NULL ? rbitset_is_set(irg->caller_isbe, pos) : 0;
89 /** Search the caller in the list of all callers and set it's backedge property. */
90 static void set_irg_caller_backedge(ir_graph *irg, ir_graph *caller) {
91 int i, n_callers = get_irg_n_callers(irg);
93 /* allocate a new array on demand */
94 if (irg->caller_isbe == NULL)
95 irg->caller_isbe = rbitset_malloc(n_callers);
96 for (i = 0; i < n_callers; ++i) {
97 if (get_irg_caller(irg, i) == caller) {
98 rbitset_set(irg->caller_isbe, i);
104 /* Returns non-zero if the irg has a backedge caller. */
105 int has_irg_caller_backedge(ir_graph *irg) {
106 int i, n_callers = get_irg_n_callers(irg);
108 if (irg->caller_isbe != NULL) {
109 for (i = 0; i < n_callers; ++i)
110 if (rbitset_is_set(irg->caller_isbe, i))
117 * Find the reversion position of a caller.
118 * Given the position pos_caller of an caller of irg, return
119 * irg's callee position on that caller.
121 static int reverse_pos(ir_graph *callee, int pos_caller) {
122 ir_graph *caller = get_irg_caller(callee, pos_caller);
123 /* search the other relation for the corresponding edge. */
125 int i, n_callees = get_irg_n_callees(caller);
126 for (i = 0; i < n_callees; ++i) {
127 if (get_irg_callee(caller, i) == callee) {
133 assert(pos_callee >= 0);
138 /* Returns the maximal loop depth of call nodes that call along this edge. */
139 int get_irg_caller_loop_depth(ir_graph *irg, int pos) {
140 ir_graph *caller = get_irg_caller(irg, pos);
141 int pos_callee = reverse_pos(irg, pos);
143 return get_irg_callee_loop_depth(caller, pos_callee);
147 /* Returns the number of procedures that are called by the given irg. */
148 int get_irg_n_callees(ir_graph *irg) {
149 if (irg->callees) return ARR_LEN(irg->callees);
153 /* Returns the callee at position pos. */
154 ir_graph *get_irg_callee(ir_graph *irg, int pos) {
155 assert(pos >= 0 && pos < get_irg_n_callees(irg));
156 if (irg->callees) return irg->callees[pos]->irg;
160 /* Returns non-zero if the callee at position pos is "a backedge", i.e. a recursion. */
161 int is_irg_callee_backedge(ir_graph *irg, int pos) {
162 assert(pos >= 0 && pos < get_irg_n_callees(irg));
163 return irg->callee_isbe != NULL ? rbitset_is_set(irg->callee_isbe, pos) : 0;
166 /* Returns non-zero if the irg has a backedge callee. */
167 int has_irg_callee_backedge(ir_graph *irg) {
168 int i, n_callees = get_irg_n_callees(irg);
170 if (irg->callee_isbe != NULL) {
171 for (i = 0; i < n_callees; ++i)
172 if (rbitset_is_set(irg->callee_isbe, i))
179 * Mark the callee at position pos as a backedge.
181 static void set_irg_callee_backedge(ir_graph *irg, int pos) {
182 int n = get_irg_n_callees(irg);
184 /* allocate a new array on demand */
185 if (irg->callee_isbe == NULL)
186 irg->callee_isbe = rbitset_malloc(n);
187 assert(pos >= 0 && pos < n);
188 rbitset_set(irg->callee_isbe, pos);
191 /* Returns the maximal loop depth of call nodes that call along this edge. */
192 int get_irg_callee_loop_depth(ir_graph *irg, int pos) {
193 assert(pos >= 0 && pos < get_irg_n_callees(irg));
194 if (irg->callees) return irg->callees[pos]->max_depth;
199 double get_irg_callee_execution_frequency(ir_graph *irg, int pos) {
200 ir_node **arr = irg->callees[pos]->call_list;
201 int i, n_Calls = ARR_LEN(arr);
204 for (i = 0; i < n_Calls; ++i) {
205 freq += get_irn_exec_freq(arr[i]);
210 double get_irg_callee_method_execution_frequency(ir_graph *irg, int pos) {
211 double call_freq = get_irg_callee_execution_frequency(irg, pos);
212 double meth_freq = get_irg_method_execution_frequency(irg);
213 return call_freq * meth_freq;
217 double get_irg_caller_method_execution_frequency(ir_graph *irg, int pos) {
218 ir_graph *caller = get_irg_caller(irg, pos);
219 int pos_callee = reverse_pos(irg, pos);
221 return get_irg_callee_method_execution_frequency(caller, pos_callee);
226 /* --------------------- Compute the callgraph ------------------------ */
229 * Walker called by compute_callgraph(), analyses all Call nodes.
231 static void ana_Call(ir_node *n, void *env) {
236 if (! is_Call(n)) return;
238 irg = get_irn_irg(n);
239 n_callees = get_Call_n_callees(n);
240 for (i = 0; i < n_callees; ++i) {
241 ir_entity *callee_e = get_Call_callee(n, i);
242 ir_graph *callee = get_entity_irg(callee_e);
246 cg_callee_entry *found;
251 pset_insert((pset *)callee->callers, irg, HASH_PTR(irg));
252 found = pset_find((pset *)irg->callees, &buf, HASH_PTR(callee));
253 if (found) { /* add Call node to list, compute new nesting. */
254 ir_node **arr = found->call_list;
255 ARR_APP1(ir_node *, arr, n);
256 found->call_list = arr;
257 } else { /* New node, add Call node and init nesting. */
258 found = (cg_callee_entry *)obstack_alloc(irg->obst, sizeof(*found));
260 found->call_list = NEW_ARR_F(ir_node *, 1);
261 found->call_list[0] = n;
262 found->max_depth = 0;
263 pset_insert((pset *)irg->callees, found, HASH_PTR(callee));
265 depth = get_loop_depth(get_irn_loop(get_nodes_block(n)));
266 found->max_depth = (depth > found->max_depth) ? depth : found->max_depth;
271 /** compare two ir graphs in a cg_callee_entry */
272 static int cg_callee_entry_cmp(const void *elt, const void *key) {
273 const cg_callee_entry *e1 = elt;
274 const cg_callee_entry *e2 = key;
275 return e1->irg != e2->irg;
278 /** compare two ir graphs for pointer identity */
279 static int graph_cmp(const void *elt, const void *key) {
280 const ir_graph *e1 = elt;
281 const ir_graph *e2 = key;
286 /* Construct and destruct the callgraph. */
287 void compute_callgraph(void) {
290 #ifdef INTERPROCEDURAL_VIEW
291 assert(! get_interprocedural_view()); /* Else walking will not reach the Call nodes. */
297 n_irgs = get_irp_n_irgs();
298 for (i = 0; i < n_irgs; ++i) {
299 ir_graph *irg = get_irp_irg(i);
300 assert(get_irg_callee_info_state(irg) == irg_callee_info_consistent);
301 irg->callees = (cg_callee_entry **)new_pset(cg_callee_entry_cmp, 8);
302 irg->callers = (ir_graph **)new_pset(graph_cmp, 8);
303 //construct_cf_backedges(irg);
306 /* Compute the call graph */
307 for (i = 0; i < n_irgs; ++i) {
308 ir_graph *irg = get_irp_irg(i);
309 construct_cf_backedges(irg); // We also find the maximal loop depth of a call.
310 irg_walk_graph(irg, ana_Call, NULL, NULL);
313 /* Change the sets to arrays. */
314 for (i = 0; i < n_irgs; ++i) {
316 cg_callee_entry *callee;
317 ir_graph *c, *irg = get_irp_irg(i);
318 pset *callee_set, *caller_set;
320 callee_set = (pset *)irg->callees;
321 count = pset_count(callee_set);
322 irg->callees = NEW_ARR_F(cg_callee_entry *, count);
323 irg->callee_isbe = NULL;
324 callee = pset_first(callee_set);
325 for (j = 0; j < count; ++j) {
326 irg->callees[j] = callee;
327 callee = pset_next(callee_set);
329 del_pset(callee_set);
330 assert(callee == NULL);
332 caller_set = (pset *)irg->callers;
333 count = pset_count(caller_set);
334 irg->callers = NEW_ARR_F(ir_graph *, count);
335 irg->caller_isbe = NULL;
336 c = pset_first(caller_set);
337 for (j = 0; j < count; ++j) {
339 c = pset_next(caller_set);
341 del_pset(caller_set);
344 set_irp_callgraph_state(irp_callgraph_consistent);
347 /* Destruct the callgraph. */
348 void free_callgraph(void) {
349 int i, n_irgs = get_irp_n_irgs();
350 for (i = 0; i < n_irgs; ++i) {
351 ir_graph *irg = get_irp_irg(i);
352 if (irg->callees) DEL_ARR_F(irg->callees);
353 if (irg->callers) DEL_ARR_F(irg->callers);
354 if (irg->callee_isbe) free(irg->callee_isbe);
355 if (irg->caller_isbe) free(irg->caller_isbe);
358 irg->callee_isbe = NULL;
359 irg->caller_isbe = NULL;
361 set_irp_callgraph_state(irp_callgraph_none);
364 /* ----------------------------------------------------------------------------------- */
365 /* A walker for the callgraph */
366 /* ----------------------------------------------------------------------------------- */
369 static void do_walk(ir_graph *irg, callgraph_walk_func *pre, callgraph_walk_func *post, void *env) {
372 if (cg_irg_visited(irg))
374 mark_cg_irg_visited(irg);
379 n_callees = get_irg_n_callees(irg);
380 for (i = 0; i < n_callees; i++) {
381 ir_graph *m = get_irg_callee(irg, i);
382 do_walk(m, pre, post, env);
389 void callgraph_walk(ir_entity **roots, unsigned n_roots,
390 callgraph_walk_func *pre, callgraph_walk_func *post, void *env) {
391 //int i, n_irgs = get_irp_n_irgs();
395 for (r = 0; r < n_roots; ++r) {
396 ir_graph *irg = get_entity_irg(roots[r]);
400 do_walk(irg, pre, post, env);
404 for (i = 0; i < n_irgs; i++) {
405 ir_graph *irg = get_irp_irg(i);
406 if (!cg_irg_visited(irg) && get_irg_n_callers(irg) == 0)
407 do_walk(irg, pre, post, env);
409 for (i = 0; i < n_irgs; i++) {
410 ir_graph *irg = get_irp_irg(i);
411 if (!cg_irg_visited(irg))
412 do_walk(irg, pre, post, env);
417 /* ----------------------------------------------------------------------------------- */
418 /* loop construction algorithm */
419 /* ----------------------------------------------------------------------------------- */
421 static ir_graph *outermost_ir_graph; /**< The outermost graph the scc is computed
423 static ir_loop *current_loop; /**< Current cfloop construction is working
425 static int loop_node_cnt = 0; /**< Counts the number of allocated cfloop nodes.
426 Each cfloop node gets a unique number.
427 What for? ev. remove. @@@ */
428 static int current_dfn = 1; /**< Counter to generate depth first numbering
431 /*-----------------*/
432 /* Node attributes */
433 /*-----------------*/
435 typedef struct scc_info {
436 int in_stack; /**< Marks whether node is on the stack. */
437 int dfn; /**< Depth first search number. */
438 int uplink; /**< dfn number of ancestor. */
443 * allocates a new scc_info on the obstack
445 static INLINE scc_info *new_scc_info(struct obstack *obst) {
446 scc_info *info = obstack_alloc(obst, sizeof(*info));
447 memset(info, 0, sizeof(*info));
452 * Returns non-zero if a graph was already visited.
454 static INLINE int cg_irg_visited(ir_graph *irg) {
455 return irg->self_visited >= master_cg_visited;
459 * Marks a graph as visited.
461 static INLINE void mark_cg_irg_visited(ir_graph *irg) {
462 irg->self_visited = master_cg_visited;
466 * Set a graphs visited flag to i.
468 static INLINE void set_cg_irg_visited(ir_graph *irg, ir_visited_t i) {
469 irg->self_visited = i;
473 * Returns the visited flag of a graph.
475 static INLINE ir_visited_t get_cg_irg_visited(ir_graph *irg) {
476 return irg->self_visited;
479 static INLINE void mark_irg_in_stack(ir_graph *irg) {
480 scc_info *info = get_irg_link(irg);
481 assert(info && "missing call to init_scc()");
485 static INLINE void mark_irg_not_in_stack(ir_graph *irg) {
486 scc_info *info = get_irg_link(irg);
487 assert(info && "missing call to init_scc()");
491 static INLINE int irg_is_in_stack(ir_graph *irg) {
492 scc_info *info = get_irg_link(irg);
493 assert(info && "missing call to init_scc()");
494 return info->in_stack;
497 static INLINE void set_irg_uplink(ir_graph *irg, int uplink) {
498 scc_info *info = get_irg_link(irg);
499 assert(info && "missing call to init_scc()");
500 info->uplink = uplink;
503 static INLINE int get_irg_uplink(ir_graph *irg) {
504 scc_info *info = get_irg_link(irg);
505 assert(info && "missing call to init_scc()");
509 static INLINE void set_irg_dfn(ir_graph *irg, int dfn) {
510 scc_info *info = get_irg_link(irg);
511 assert(info && "missing call to init_scc()");
515 static INLINE int get_irg_dfn(ir_graph *irg) {
516 scc_info *info = get_irg_link(irg);
517 assert(info && "missing call to init_scc()");
521 /**********************************************************************/
523 /**********************************************************************/
525 static ir_graph **stack = NULL;
526 static int tos = 0; /**< top of stack */
529 * Initialize the irg stack.
531 static INLINE void init_stack(void) {
533 ARR_RESIZE(ir_graph *, stack, 1000);
535 stack = NEW_ARR_F(ir_graph *, 1000);
541 * push a graph on the irg stack
542 * @param n the graph to be pushed
544 static INLINE void push(ir_graph *irg) {
545 if (tos == ARR_LEN(stack)) {
546 int nlen = ARR_LEN(stack) * 2;
547 ARR_RESIZE(ir_node *, stack, nlen);
550 mark_irg_in_stack(irg);
554 * return the topmost graph on the stack and pop it
556 static INLINE ir_graph *pop(void) {
557 ir_graph *irg = stack[--tos];
558 mark_irg_not_in_stack(irg);
563 * The nodes up to irg belong to the current loop.
564 * Removes them from the stack and adds them to the current loop.
566 static INLINE void pop_scc_to_loop(ir_graph *irg) {
572 set_irg_dfn(m, loop_node_cnt);
573 add_loop_irg(current_loop, m);
575 //m->callgraph_loop_depth = current_loop->depth;
579 /* GL ??? my last son is my grandson??? Removes cfloops with no
580 ir_nodes in them. Such loops have only another loop as son. (Why
581 can't they have two loops as sons? Does it never get that far? ) */
582 static void close_loop(ir_loop *l) {
583 int last = get_loop_n_elements(l) - 1;
584 loop_element lelement = get_loop_element(l, last);
585 ir_loop *last_son = lelement.son;
587 if (get_kind(last_son) == k_ir_loop &&
588 get_loop_n_elements(last_son) == 1) {
591 lelement = get_loop_element(last_son, 0);
593 if (get_kind(gson) == k_ir_loop) {
594 loop_element new_last_son;
596 gson->outer_loop = l;
597 new_last_son.son = gson;
598 l->children[last] = new_last_son;
605 * Removes and unmarks all nodes up to n from the stack.
606 * The nodes must be visited once more to assign them to a scc.
608 static INLINE void pop_scc_unmark_visit(ir_graph *n) {
613 set_cg_irg_visited(m, 0);
617 /**********************************************************************/
618 /* The loop data structure. **/
619 /**********************************************************************/
622 * Allocates a new loop as son of current_loop. Sets current_loop
623 * to the new loop and returns the father.
625 static ir_loop *new_loop(void) {
626 ir_loop *father = current_loop;
627 ir_loop *son = alloc_loop(father, outermost_ir_graph->obst);
634 /**********************************************************************/
635 /* Constructing and destructing the loop/backedge information. **/
636 /**********************************************************************/
638 /* Initialization steps. **********************************************/
640 static void init_scc(struct obstack *obst) {
648 n_irgs = get_irp_n_irgs();
649 for (i = 0; i < n_irgs; ++i) {
650 ir_graph *irg = get_irp_irg(i);
651 set_irg_link(irg, new_scc_info(obst));
652 irg->callgraph_recursion_depth = 0;
653 irg->callgraph_loop_depth = 0;
657 /** Returns non-zero if n is a loop header, i.e., it is a Block node
658 * and has predecessors within the cfloop and out of the cfloop.
660 * @param root: only needed for assertion.
662 static int is_head(ir_graph *n, ir_graph *root) {
664 int some_outof_loop = 0, some_in_loop = 0;
666 arity = get_irg_n_callees(n);
667 for (i = 0; i < arity; i++) {
668 ir_graph *pred = get_irg_callee(n, i);
669 if (is_irg_callee_backedge(n, i)) continue;
670 if (!irg_is_in_stack(pred)) {
673 if (get_irg_uplink(pred) < get_irg_uplink(root)) {
674 assert(get_irg_uplink(pred) >= get_irg_uplink(root));
680 return some_outof_loop & some_in_loop;
684 * Returns non-zero if n is possible loop head of an endless loop.
685 * I.e., it is a Block, Phi or Filter node and has only predecessors
687 * @arg root: only needed for assertion.
689 static int is_endless_head(ir_graph *n, ir_graph *root)
692 int some_outof_loop = 0, some_in_loop = 0;
694 arity = get_irg_n_callees(n);
695 for (i = 0; i < arity; i++) {
696 ir_graph *pred = get_irg_callee(n, i);
698 if (is_irg_callee_backedge(n, i))
700 if (!irg_is_in_stack(pred)) {
703 if (get_irg_uplink(pred) < get_irg_uplink(root)) {
704 assert(get_irg_uplink(pred) >= get_irg_uplink(root));
709 return !some_outof_loop & some_in_loop;
712 #ifdef INTERPROCEDURAL_VIEW
714 * Check whether there is a parallel edge in the ip control flow.
717 static int is_ip_head(ir_graph *n, ir_graph *pred)
721 int iv_rem = get_interprocedural_view();
722 set_interprocedural_view(1);
724 ir_node *sblock = get_irg_start_block(n);
725 int i, arity = get_Block_n_cfgpreds(sblock);
727 //printf(" edge from "); DDMG(n);
728 //printf(" to pred "); DDMG(pred);
729 //printf(" sblock "); DDMN(sblock);
731 for (i = 0; i < arity; i++) {
732 ir_node *pred_cfop = skip_Proj(get_Block_cfgpred(sblock, i));
733 //printf(" "); DDMN(pred_cfop);
734 if (is_CallBegin(pred_cfop)) { /* could be Unknown */
735 ir_graph *ip_pred = get_irn_irg(pred_cfop);
736 //printf(" "); DDMG(ip_pred);
737 if ((ip_pred == pred) && is_backedge(sblock, i)) {
738 //printf(" found\n");
744 set_interprocedural_view(iv_rem);
747 #endif /* INTERPROCEDURAL_VIEW */
750 * Returns index of the predecessor with the smallest dfn number
751 * greater-equal than limit.
753 static int smallest_dfn_pred(ir_graph *n, int limit)
755 int i, index = -2, min = -1;
757 int arity = get_irg_n_callees(n);
758 for (i = 0; i < arity; i++) {
759 ir_graph *pred = get_irg_callee(n, i);
760 if (is_irg_callee_backedge(n, i) || !irg_is_in_stack(pred))
762 if (get_irg_dfn(pred) >= limit && (min == -1 || get_irg_dfn(pred) < min)) {
764 min = get_irg_dfn(pred);
771 /** Returns index of the predecessor with the largest dfn number. */
772 static int largest_dfn_pred(ir_graph *n) {
773 int i, index = -2, max = -1;
775 int arity = get_irg_n_callees(n);
776 for (i = 0; i < arity; ++i) {
777 ir_graph *pred = get_irg_callee(n, i);
778 if (is_irg_callee_backedge (n, i) || !irg_is_in_stack(pred)) continue;
779 if (get_irg_dfn(pred) > max) {
781 max = get_irg_dfn(pred);
788 #ifndef INTERPROCEDURAL_VIEW
789 static ir_graph *find_tail(ir_graph *n) {
791 int i, res_index = -2;
794 if (!icfg && rm_cyclic_phis && remove_cyclic_phis (n)) return NULL;
796 m = stack[tos-1]; /* tos = top of stack */
797 if (is_head (m, n)) {
798 res_index = smallest_dfn_pred(m, 0);
799 if ((res_index == -2) && /* no smallest dfn pred found. */
803 if (m == n) return NULL; // Is this to catch Phi - self loops?
804 for (i = tos-2; i >= 0; --i) {
808 res_index = smallest_dfn_pred(m, get_irg_dfn(m) + 1);
809 if (res_index == -2) /* no smallest dfn pred found. */
810 res_index = largest_dfn_pred(m);
812 if ((m == n) && (res_index == -2)) {
818 /* We should not walk past our selves on the stack: The upcoming nodes
819 are not in this loop. We assume a loop not reachable from Start. */
828 /* A dead loop not reachable from Start. */
829 for (i = tos-2; i >= 0; --i) {
831 if (is_endless_head(m, n)) {
832 res_index = smallest_dfn_pred(m, get_irg_dfn(m) + 1);
833 if (res_index == -2) /* no smallest dfn pred found. */
834 res_index = largest_dfn_pred(m);
837 if (m == n) { break; } /* It's not an unreachable loop, either. */
839 //assert(0 && "no head found on stack");
843 assert (res_index > -2);
845 set_irg_callee_backedge(m, res_index);
846 return get_irg_callee(m, res_index);
849 static ir_graph *find_tail(ir_graph *n) {
851 int i, res_index = -2;
854 ir_graph *in_and_out = NULL;
855 ir_graph *only_in = NULL;
856 ir_graph *ip_in_and_out = NULL;
857 ir_graph *ip_only_in = NULL;
859 //printf("find tail for "); DDMG(n);
861 for (i = tos-1; i >= 0; --i) {
862 ir_graph *pred = (i < tos -1) ? stack[i+1] : n;
866 //printf(" found 1a! "); DDM;
868 if (is_ip_head(pred, m)) {
869 //printf(" found 1b! "); DDM;
872 } else if (!ip_only_in && is_endless_head(m, n)) {
874 //printf(" found 2a! "); DDM;
875 if (is_ip_head(pred, m)) {
876 //printf(" found 2b! "); DDM;
879 } else if (is_ip_head(pred, m)) {
880 //printf(" found 3! "); DDM; This happens for self recursions in the second
881 //assert(0); scc iteration (the one to flip the loop.)
884 if (ip_in_and_out) break; /* That's what we really want. */
886 if (m == n) break; /* Don't walk past n on the stack! */
890 if (!in_and_out && !only_in)
891 /* There is no loop */
895 /* Is there a head in the callgraph without a head in the
897 assert(in_and_out || only_in);
899 m = (ip_in_and_out) ? ip_in_and_out : ip_only_in;
902 m = (in_and_out) ? in_and_out : only_in;
904 //printf("*** head is "); DDMG(m);
906 res_index = smallest_dfn_pred(m, get_irg_dfn(m) + 1);
907 if (res_index == -2) /* no smallest dfn pred found. */
908 res_index = largest_dfn_pred(m);
910 set_irg_callee_backedge(m, res_index);
911 res = get_irg_callee(m, res_index);
912 //printf("*** tail is "); DDMG(res);
915 #endif /* INTERPROCEDURAL_VIEW */
917 /*-----------------------------------------------------------*
918 * The core algorithm. *
919 *-----------------------------------------------------------*/
922 static void cgscc(ir_graph *n) {
925 if (cg_irg_visited(n)) return;
926 mark_cg_irg_visited(n);
928 /* Initialize the node */
929 set_irg_dfn(n, current_dfn); /* Depth first number for this node */
930 set_irg_uplink(n, current_dfn); /* ... is default uplink. */
934 arity = get_irg_n_callees(n);
935 for (i = 0; i < arity; i++) {
937 if (is_irg_callee_backedge(n, i)) continue;
938 m = get_irg_callee(n, i);
940 /** This marks the backedge, but does it guarantee a correct loop tree? */
941 //if (m == n) { set_irg_callee_backedge(n, i); continue; }
944 if (irg_is_in_stack(m)) {
945 /* Uplink of m is smaller if n->m is a backedge.
946 Propagate the uplink to mark the cfloop. */
947 if (get_irg_uplink(m) < get_irg_uplink(n))
948 set_irg_uplink(n, get_irg_uplink(m));
952 if (get_irg_dfn(n) == get_irg_uplink(n)) {
953 /* This condition holds for
954 1) the node with the incoming backedge.
955 That is: We found a cfloop!
956 2) Straight line code, because no uplink has been propagated, so the
957 uplink still is the same as the dfn.
959 But n might not be a proper cfloop head for the analysis. Proper cfloop
960 heads are Block and Phi nodes. find_tail searches the stack for
961 Block's and Phi's and takes those nodes as cfloop heads for the current
962 cfloop instead and marks the incoming edge as backedge. */
964 ir_graph *tail = find_tail(n);
966 /* We have a cfloop, that is no straight line code,
967 because we found a cfloop head!
968 Next actions: Open a new cfloop on the cfloop tree and
969 try to find inner cfloops */
972 ir_loop *l = new_loop();
974 /* Remove the cfloop from the stack ... */
975 pop_scc_unmark_visit(n);
977 /* The current backedge has been marked, that is temporarily eliminated,
978 by find tail. Start the scc algorithm
979 anew on the subgraph thats left (the current cfloop without the backedge)
980 in order to find more inner cfloops. */
984 assert(cg_irg_visited(n));
994 * reset the backedge information for all callers in all irgs
996 static void reset_isbe(void) {
997 int i, n_irgs = get_irp_n_irgs();
999 for (i = 0; i < n_irgs; ++i) {
1000 ir_graph *irg = get_irp_irg(i);
1002 if (irg->caller_isbe)
1003 xfree(irg->caller_isbe);
1004 irg->caller_isbe = NULL;
1006 if (irg->callee_isbe)
1007 xfree(irg->callee_isbe);
1008 irg->callee_isbe = NULL;
1012 /* ----------------------------------------------------------------------------------- */
1013 /* Another algorithm to compute recursion nesting depth */
1014 /* Walk the callgraph. For each crossed edge increase the loop depth by the edge */
1015 /* weight. Assign graphs the maximal depth. */
1016 /* ----------------------------------------------------------------------------------- */
1018 static void compute_loop_depth(ir_graph *irg, void *env) {
1019 int current_nesting = *(int *) env;
1020 int old_nesting = irg->callgraph_loop_depth;
1021 ir_visited_t old_visited = get_cg_irg_visited(irg);
1026 if (cg_irg_visited(irg)) return;
1028 mark_cg_irg_visited(irg);
1030 //printf(" old: %d new %d master %d", old_visited, get_cg_irg_visited(irg), master_cg_visited); DDMG(irg);
1033 if (old_nesting < current_nesting)
1034 irg->callgraph_loop_depth = current_nesting;
1036 if (current_nesting > irp->max_callgraph_loop_depth)
1037 irp->max_callgraph_loop_depth = current_nesting;
1039 if ((old_visited +1 < get_cg_irg_visited(irg)) || /* not yet visited */
1040 (old_nesting < current_nesting)) { /* propagate larger nesting */
1041 /* Don't walk the graph, but a tree that is an unfolded graph. */
1042 n_callees = get_irg_n_callees(irg);
1043 for (i = 0; i < n_callees; i++) {
1044 ir_graph *m = get_irg_callee(irg, i);
1045 *(int *)env += get_irg_callee_loop_depth(irg, i);
1046 compute_loop_depth(m, env);
1047 *(int *)env -= get_irg_callee_loop_depth(irg, i);
1051 set_cg_irg_visited(irg, master_cg_visited-1);
1054 /* ------------------------------------------------------------------------------------ */
1055 /* Another algorithm to compute recursion nesting depth */
1056 /* Walk the callgraph. For each crossed loop increase the nesting depth by one. */
1057 /* Assign graphs the maximal nesting depth. Don't increase if passing loops more than */
1059 /* ------------------------------------------------------------------------------------ */
1062 /* For callees, we want to remember the Call nodes, too. */
1063 typedef struct ana_entry2 {
1064 ir_loop **loop_stack; /**< a stack of ir_loop entries */
1065 int tos; /**< the top of stack entry */
1066 int recursion_nesting;
1070 * push a loop entry on the stack
1072 static void push2(ana_entry2 *e, ir_loop *g) {
1073 if (ARR_LEN(e->loop_stack) == e->tos) {
1074 ARR_APP1(ir_loop *, e->loop_stack, g);
1076 e->loop_stack[e->tos] = g;
1082 * returns the top of stack and pop it
1084 static ir_loop *pop2(ana_entry2 *e) {
1085 return e->loop_stack[--e->tos];
1089 * check if a loop g in on the stack. Did not check the TOS.
1091 static int in_stack(ana_entry2 *e, ir_loop *g) {
1093 for (i = e->tos-1; i >= 0; --i) {
1094 if (e->loop_stack[i] == g) return 1;
1099 static void compute_rec_depth(ir_graph *irg, void *env) {
1100 ana_entry2 *e = (ana_entry2 *)env;
1101 ir_loop *l = irg->l;
1102 int depth, old_depth = irg->callgraph_recursion_depth;
1106 if (cg_irg_visited(irg))
1108 mark_cg_irg_visited(irg);
1110 /* -- compute and set the new nesting value -- */
1111 if ((l != irp->outermost_cg_loop) && !in_stack(e, l)) {
1113 e->recursion_nesting++;
1116 depth = e->recursion_nesting;
1118 if (old_depth < depth)
1119 irg->callgraph_recursion_depth = depth;
1121 if (depth > irp->max_callgraph_recursion_depth)
1122 irp->max_callgraph_recursion_depth = depth;
1124 /* -- spread the nesting value -- */
1125 if (depth == 0 || old_depth < depth) {
1126 /* Don't walk the graph, but a tree that is an unfolded graph.
1127 Therefore we unset the visited flag at the end. */
1128 n_callees = get_irg_n_callees(irg);
1129 for (i = 0; i < n_callees; ++i) {
1130 ir_graph *m = get_irg_callee(irg, i);
1131 compute_rec_depth(m, env);
1135 /* -- clean up -- */
1138 e->recursion_nesting--;
1140 set_cg_irg_visited(irg, master_cg_visited-1);
1144 /* ----------------------------------------------------------------------------------- */
1145 /* Another algorithm to compute the execution frequency of methods ignoring recursions. */
1146 /* Walk the callgraph. Ignore backedges. Use sum of execution frequencies of Call */
1147 /* nodes to evaluate a callgraph edge. */
1148 /* ----------------------------------------------------------------------------------- */
1150 /* Returns the method execution frequency of a graph. */
1151 double get_irg_method_execution_frequency(ir_graph *irg) {
1152 return irg->method_execution_frequency;
1156 * Increase the method execution frequency to freq if its current value is
1157 * smaller then this.
1159 static void set_irg_method_execution_frequency(ir_graph *irg, double freq) {
1160 irg->method_execution_frequency = freq;
1162 if (irp->max_method_execution_frequency < freq)
1163 irp->max_method_execution_frequency = freq;
1166 static void compute_method_execution_frequency(ir_graph *irg, void *env) {
1173 if (cg_irg_visited(irg))
1176 /* We need the values of all predecessors (except backedges).
1177 So they must be marked. Else we will reach the node through
1178 one of the unmarked ones. */
1179 n_callers = get_irg_n_callers(irg);
1180 for (i = 0; i < n_callers; ++i) {
1181 ir_graph *m = get_irg_caller(irg, i);
1182 if (is_irg_caller_backedge(irg, i))
1184 if (!cg_irg_visited(m)) {
1188 mark_cg_irg_visited(irg);
1190 /* Compute the new frequency. */
1193 for (i = 0; i < n_callers; i++) {
1194 if (! is_irg_caller_backedge(irg, i)) {
1195 double edge_freq = get_irg_caller_method_execution_frequency(irg, i);
1196 assert(edge_freq >= 0);
1203 /* A starting point: method only called from outside,
1204 or only backedges as predecessors. */
1208 set_irg_method_execution_frequency(irg, freq);
1211 n_callees = get_irg_n_callees(irg);
1212 for (i = 0; i < n_callees; ++i) {
1213 compute_method_execution_frequency(get_irg_callee(irg, i), NULL);
1218 /* ----------------------------------------------------------------------------------- */
1219 /* The recursion stuff driver. */
1220 /* ----------------------------------------------------------------------------------- */
1222 /* Compute the backedges that represent recursions. */
1223 void find_callgraph_recursions(void) {
1224 int i, n_irgs = get_irp_n_irgs();
1225 struct obstack temp;
1229 /* -- compute the looptree. -- */
1231 /* The outermost graph. We start here. Then we start at all
1232 functions in irg list that are never called, then at the remaining
1233 unvisited ones. The third step is needed for functions that are not
1234 reachable from the outermost graph, but call themselves in a cycle. */
1235 assert(get_irp_main_irg());
1236 outermost_ir_graph = get_irp_main_irg();
1237 obstack_init(&temp);
1240 current_loop = NULL;
1241 new_loop(); /* sets current_loop */
1243 ++master_cg_visited;
1244 cgscc(outermost_ir_graph);
1245 for (i = 0; i < n_irgs; ++i) {
1246 ir_graph *irg = get_irp_irg(i);
1247 if (!cg_irg_visited(irg) && get_irg_n_callers(irg) == 0)
1250 for (i = 0; i < n_irgs; ++i) {
1251 ir_graph *irg = get_irp_irg(i);
1252 if (!cg_irg_visited(irg))
1255 obstack_free(&temp, NULL);
1257 irp->outermost_cg_loop = current_loop;
1258 mature_loops(current_loop, outermost_ir_graph->obst);
1260 /* -- Reverse the backedge information. -- */
1261 for (i = 0; i < n_irgs; ++i) {
1262 ir_graph *irg = get_irp_irg(i);
1263 int j, n_callees = get_irg_n_callees(irg);
1264 for (j = 0; j < n_callees; ++j) {
1265 if (is_irg_callee_backedge(irg, j))
1266 set_irg_caller_backedge(get_irg_callee(irg, j), irg);
1270 irp->callgraph_state = irp_callgraph_and_calltree_consistent;
1273 /* Compute interprocedural performance estimates. */
1274 void compute_performance_estimates(void) {
1275 int i, n_irgs = get_irp_n_irgs();
1276 int current_nesting;
1279 assert(get_irp_exec_freq_state() != exec_freq_none && "execution frequency not calculated");
1281 /* -- compute the loop depth -- */
1282 current_nesting = 0;
1283 irp->max_callgraph_loop_depth = 0;
1284 master_cg_visited += 2;
1285 //printf(" ** starting at "); DDMG(get_irp_main_irg());
1286 compute_loop_depth(get_irp_main_irg(), ¤t_nesting);
1287 for (i = 0; i < n_irgs; i++) {
1288 ir_graph *irg = get_irp_irg(i);
1289 if ((get_cg_irg_visited(irg) < master_cg_visited-1) &&
1290 get_irg_n_callers(irg) == 0) {
1291 compute_loop_depth(irg, ¤t_nesting);
1292 //printf(" ** starting at "); DDMG(irg);
1295 for (i = 0; i < n_irgs; i++) {
1296 ir_graph *irg = get_irp_irg(i);
1297 if (get_cg_irg_visited(irg) < master_cg_visited-1) {
1298 compute_loop_depth(irg, ¤t_nesting);
1299 //printf(" ** starting at "); DDMG(irg);
1304 /* -- compute the recursion depth -- */
1305 e.loop_stack = NEW_ARR_F(ir_loop *, 0);
1307 e.recursion_nesting = 0;
1309 irp->max_callgraph_recursion_depth = 0;
1311 master_cg_visited += 2;
1312 compute_rec_depth(get_irp_main_irg(), &e);
1313 //printf(" ++ starting at "); DDMG(get_irp_main_irg());
1314 for (i = 0; i < n_irgs; i++) {
1315 ir_graph *irg = get_irp_irg(i);
1316 if ((get_cg_irg_visited(irg) < master_cg_visited-1) &&
1317 get_irg_n_callers(irg) == 0) {
1318 compute_rec_depth(irg, &e);
1319 //printf(" ++ starting at "); DDMG(irg);
1322 for (i = 0; i < n_irgs; i++) {
1323 ir_graph *irg = get_irp_irg(i);
1324 if (get_cg_irg_visited(irg) < master_cg_visited-1) {
1325 compute_rec_depth(irg, &e);
1326 //printf(" ++ starting at "); DDMG(irg);
1330 DEL_ARR_F(e.loop_stack);
1332 /* -- compute the execution frequency -- */
1333 irp->max_method_execution_frequency = 0;
1334 master_cg_visited += 2;
1335 assert(get_irg_n_callers(get_irp_main_irg()) == 0);
1336 compute_method_execution_frequency(get_irp_main_irg(), NULL);
1337 for (i = 0; i < n_irgs; i++) {
1338 ir_graph *irg = get_irp_irg(i);
1339 if ((get_cg_irg_visited(irg) < master_cg_visited-1) &&
1340 get_irg_n_callers(irg) == 0) {
1341 compute_method_execution_frequency(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 compute_method_execution_frequency(irg, NULL);
1352 /* Returns the maximal loop depth of all paths from an external visible method to
1354 int get_irg_loop_depth(ir_graph *irg) {
1355 assert(irp->callgraph_state == irp_callgraph_consistent ||
1356 irp->callgraph_state == irp_callgraph_and_calltree_consistent);
1357 return irg->callgraph_loop_depth;
1360 /* Returns the maximal recursion depth of all paths from an external visible method to
1362 int get_irg_recursion_depth(ir_graph *irg) {
1363 assert(irp->callgraph_state == irp_callgraph_and_calltree_consistent);
1364 return irg->callgraph_recursion_depth;
1367 /* Computes the interprocedural loop nesting information. */
1368 void analyse_loop_nesting_depth(void) {
1369 ir_entity **free_methods = NULL;
1372 /* establish preconditions. */
1373 if (get_irp_callee_info_state() != irg_callee_info_consistent) {
1374 cgana(&arr_len, &free_methods);
1377 if (irp_callgraph_consistent != get_irp_callgraph_state()) {
1378 compute_callgraph();
1381 find_callgraph_recursions();
1383 compute_performance_estimates();
1385 set_irp_loop_nesting_depth_state(loop_nesting_depth_consistent);
1388 loop_nesting_depth_state get_irp_loop_nesting_depth_state(void) {
1389 return irp->lnd_state;
1391 void set_irp_loop_nesting_depth_state(loop_nesting_depth_state s) {
1394 void set_irp_loop_nesting_depth_state_inconsistent(void) {
1395 if (irp->lnd_state == loop_nesting_depth_consistent)
1396 irp->lnd_state = loop_nesting_depth_inconsistent;