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
34 #include "callgraph.h"
38 #include "irgraph_t.h"
42 #include "execution_frequency.h"
47 #include "raw_bitset.h"
51 static ir_visited_t master_cg_visited = 0;
52 static inline int cg_irg_visited (ir_graph *n);
53 static inline void mark_cg_irg_visited(ir_graph *n);
54 static inline void set_cg_irg_visited (ir_graph *n, ir_visited_t i);
56 /** Returns the callgraph state of the program representation. */
57 irp_callgraph_state get_irp_callgraph_state(void) {
58 return irp->callgraph_state;
61 /* Sets the callgraph state of the program representation. */
62 void set_irp_callgraph_state(irp_callgraph_state s) {
63 irp->callgraph_state = s;
66 /* Returns the number of procedures that call the given irg. */
67 int get_irg_n_callers(ir_graph *irg) {
68 if (irg->callers) return ARR_LEN(irg->callers);
72 /* Returns the caller at position pos. */
73 ir_graph *get_irg_caller(ir_graph *irg, int pos) {
74 assert(pos >= 0 && pos < get_irg_n_callers(irg));
75 if (irg->callers) return irg->callers[pos];
79 /* Returns non-zero if the caller at position pos is "a backedge", i.e. a recursion. */
80 int is_irg_caller_backedge(ir_graph *irg, int pos) {
81 assert(pos >= 0 && pos < get_irg_n_callers(irg));
82 return irg->caller_isbe != NULL ? rbitset_is_set(irg->caller_isbe, pos) : 0;
85 /** Search the caller in the list of all callers and set it's backedge property. */
86 static void set_irg_caller_backedge(ir_graph *irg, ir_graph *caller) {
87 int i, n_callers = get_irg_n_callers(irg);
89 /* allocate a new array on demand */
90 if (irg->caller_isbe == NULL)
91 irg->caller_isbe = rbitset_malloc(n_callers);
92 for (i = 0; i < n_callers; ++i) {
93 if (get_irg_caller(irg, i) == caller) {
94 rbitset_set(irg->caller_isbe, i);
100 /* Returns non-zero if the irg has a backedge caller. */
101 int has_irg_caller_backedge(ir_graph *irg) {
102 int i, n_callers = get_irg_n_callers(irg);
104 if (irg->caller_isbe != NULL) {
105 for (i = 0; i < n_callers; ++i)
106 if (rbitset_is_set(irg->caller_isbe, i))
113 * Find the reversion position of a caller.
114 * Given the position pos_caller of an caller of irg, return
115 * irg's callee position on that caller.
117 static int reverse_pos(ir_graph *callee, int pos_caller) {
118 ir_graph *caller = get_irg_caller(callee, pos_caller);
119 /* search the other relation for the corresponding edge. */
121 int i, n_callees = get_irg_n_callees(caller);
122 for (i = 0; i < n_callees; ++i) {
123 if (get_irg_callee(caller, i) == callee) {
129 assert(pos_callee >= 0);
134 /* Returns the maximal loop depth of call nodes that call along this edge. */
135 int get_irg_caller_loop_depth(ir_graph *irg, int pos) {
136 ir_graph *caller = get_irg_caller(irg, pos);
137 int pos_callee = reverse_pos(irg, pos);
139 return get_irg_callee_loop_depth(caller, pos_callee);
143 /* Returns the number of procedures that are called by the given irg. */
144 int get_irg_n_callees(ir_graph *irg) {
145 if (irg->callees) return ARR_LEN(irg->callees);
149 /* Returns the callee at position pos. */
150 ir_graph *get_irg_callee(ir_graph *irg, int pos) {
151 assert(pos >= 0 && pos < get_irg_n_callees(irg));
152 if (irg->callees) return irg->callees[pos]->irg;
156 /* Returns non-zero if the callee at position pos is "a backedge", i.e. a recursion. */
157 int is_irg_callee_backedge(ir_graph *irg, int pos) {
158 assert(pos >= 0 && pos < get_irg_n_callees(irg));
159 return irg->callee_isbe != NULL ? rbitset_is_set(irg->callee_isbe, pos) : 0;
162 /* Returns non-zero if the irg has a backedge callee. */
163 int has_irg_callee_backedge(ir_graph *irg) {
164 int i, n_callees = get_irg_n_callees(irg);
166 if (irg->callee_isbe != NULL) {
167 for (i = 0; i < n_callees; ++i)
168 if (rbitset_is_set(irg->callee_isbe, i))
175 * Mark the callee at position pos as a backedge.
177 static void set_irg_callee_backedge(ir_graph *irg, int pos) {
178 int n = get_irg_n_callees(irg);
180 /* allocate a new array on demand */
181 if (irg->callee_isbe == NULL)
182 irg->callee_isbe = rbitset_malloc(n);
183 assert(pos >= 0 && pos < n);
184 rbitset_set(irg->callee_isbe, pos);
187 /* Returns the maximal loop depth of call nodes that call along this edge. */
188 int get_irg_callee_loop_depth(ir_graph *irg, int pos) {
189 assert(pos >= 0 && pos < get_irg_n_callees(irg));
190 if (irg->callees) return irg->callees[pos]->max_depth;
195 double get_irg_callee_execution_frequency(ir_graph *irg, int pos) {
196 ir_node **arr = irg->callees[pos]->call_list;
197 int i, n_Calls = ARR_LEN(arr);
200 for (i = 0; i < n_Calls; ++i) {
201 freq += get_irn_exec_freq(arr[i]);
206 double get_irg_callee_method_execution_frequency(ir_graph *irg, int pos) {
207 double call_freq = get_irg_callee_execution_frequency(irg, pos);
208 double meth_freq = get_irg_method_execution_frequency(irg);
209 return call_freq * meth_freq;
213 double get_irg_caller_method_execution_frequency(ir_graph *irg, int pos) {
214 ir_graph *caller = get_irg_caller(irg, pos);
215 int pos_callee = reverse_pos(irg, pos);
217 return get_irg_callee_method_execution_frequency(caller, pos_callee);
222 /* --------------------- Compute the callgraph ------------------------ */
225 * Walker called by compute_callgraph(), analyses all Call nodes.
227 static void ana_Call(ir_node *n, void *env) {
232 if (! is_Call(n)) return;
234 irg = get_irn_irg(n);
235 n_callees = get_Call_n_callees(n);
236 for (i = 0; i < n_callees; ++i) {
237 ir_entity *callee_e = get_Call_callee(n, i);
238 ir_graph *callee = get_entity_irg(callee_e);
242 cg_callee_entry *found;
247 pset_insert((pset *)callee->callers, irg, HASH_PTR(irg));
248 found = pset_find((pset *)irg->callees, &buf, HASH_PTR(callee));
249 if (found) { /* add Call node to list, compute new nesting. */
250 ir_node **arr = found->call_list;
251 ARR_APP1(ir_node *, arr, n);
252 found->call_list = arr;
253 } else { /* New node, add Call node and init nesting. */
254 found = (cg_callee_entry *)obstack_alloc(irg->obst, sizeof(*found));
256 found->call_list = NEW_ARR_F(ir_node *, 1);
257 found->call_list[0] = n;
258 found->max_depth = 0;
259 pset_insert((pset *)irg->callees, found, HASH_PTR(callee));
261 depth = get_loop_depth(get_irn_loop(get_nodes_block(n)));
262 found->max_depth = (depth > found->max_depth) ? depth : found->max_depth;
267 /** compare two ir graphs in a cg_callee_entry */
268 static int cg_callee_entry_cmp(const void *elt, const void *key) {
269 const cg_callee_entry *e1 = elt;
270 const cg_callee_entry *e2 = key;
271 return e1->irg != e2->irg;
274 /** compare two ir graphs for pointer identity */
275 static int graph_cmp(const void *elt, const void *key) {
276 const ir_graph *e1 = elt;
277 const ir_graph *e2 = key;
282 /* Construct and destruct the callgraph. */
283 void compute_callgraph(void) {
286 #ifdef INTERPROCEDURAL_VIEW
287 assert(! get_interprocedural_view()); /* Else walking will not reach the Call nodes. */
293 n_irgs = get_irp_n_irgs();
294 for (i = 0; i < n_irgs; ++i) {
295 ir_graph *irg = get_irp_irg(i);
296 assert(get_irg_callee_info_state(irg) == irg_callee_info_consistent);
297 irg->callees = (cg_callee_entry **)new_pset(cg_callee_entry_cmp, 8);
298 irg->callers = (ir_graph **)new_pset(graph_cmp, 8);
299 //construct_cf_backedges(irg);
302 /* Compute the call graph */
303 for (i = 0; i < n_irgs; ++i) {
304 ir_graph *irg = get_irp_irg(i);
305 construct_cf_backedges(irg); // We also find the maximal loop depth of a call.
306 irg_walk_graph(irg, ana_Call, NULL, NULL);
309 /* Change the sets to arrays. */
310 for (i = 0; i < n_irgs; ++i) {
312 cg_callee_entry *callee;
313 ir_graph *c, *irg = get_irp_irg(i);
314 pset *callee_set, *caller_set;
316 callee_set = (pset *)irg->callees;
317 count = pset_count(callee_set);
318 irg->callees = NEW_ARR_F(cg_callee_entry *, count);
319 irg->callee_isbe = NULL;
320 callee = pset_first(callee_set);
321 for (j = 0; j < count; ++j) {
322 irg->callees[j] = callee;
323 callee = pset_next(callee_set);
325 del_pset(callee_set);
326 assert(callee == NULL);
328 caller_set = (pset *)irg->callers;
329 count = pset_count(caller_set);
330 irg->callers = NEW_ARR_F(ir_graph *, count);
331 irg->caller_isbe = NULL;
332 c = pset_first(caller_set);
333 for (j = 0; j < count; ++j) {
335 c = pset_next(caller_set);
337 del_pset(caller_set);
340 set_irp_callgraph_state(irp_callgraph_consistent);
343 /* Destruct the callgraph. */
344 void free_callgraph(void) {
345 int i, n_irgs = get_irp_n_irgs();
346 for (i = 0; i < n_irgs; ++i) {
347 ir_graph *irg = get_irp_irg(i);
348 if (irg->callees) DEL_ARR_F(irg->callees);
349 if (irg->callers) DEL_ARR_F(irg->callers);
350 if (irg->callee_isbe) free(irg->callee_isbe);
351 if (irg->caller_isbe) free(irg->caller_isbe);
354 irg->callee_isbe = NULL;
355 irg->caller_isbe = NULL;
357 set_irp_callgraph_state(irp_callgraph_none);
360 /* ----------------------------------------------------------------------------------- */
361 /* A walker for the callgraph */
362 /* ----------------------------------------------------------------------------------- */
365 static void do_walk(ir_graph *irg, callgraph_walk_func *pre, callgraph_walk_func *post, void *env) {
368 if (cg_irg_visited(irg))
370 mark_cg_irg_visited(irg);
375 n_callees = get_irg_n_callees(irg);
376 for (i = 0; i < n_callees; i++) {
377 ir_graph *m = get_irg_callee(irg, i);
378 do_walk(m, pre, post, env);
385 void callgraph_walk(callgraph_walk_func *pre, callgraph_walk_func *post, void *env) {
386 int i, n_irgs = get_irp_n_irgs();
389 /* roots are methods which have no callers in the current program */
390 for (i = 0; i < n_irgs; ++i) {
391 ir_graph *irg = get_irp_irg(i);
393 if (get_irg_n_callers(irg) == 0)
394 do_walk(irg, pre, post, env);
397 /* in case of unreachable call loops we haven't visited some irgs yet */
398 for (i = 0; i < n_irgs; i++) {
399 ir_graph *irg = get_irp_irg(i);
400 do_walk(irg, pre, post, env);
404 /* ----------------------------------------------------------------------------------- */
405 /* loop construction algorithm */
406 /* ----------------------------------------------------------------------------------- */
408 static ir_graph *outermost_ir_graph; /**< The outermost graph the scc is computed
410 static ir_loop *current_loop; /**< Current cfloop construction is working
412 static int loop_node_cnt = 0; /**< Counts the number of allocated cfloop nodes.
413 Each cfloop node gets a unique number.
414 What for? ev. remove. @@@ */
415 static int current_dfn = 1; /**< Counter to generate depth first numbering
418 /*-----------------*/
419 /* Node attributes */
420 /*-----------------*/
422 typedef struct scc_info {
423 int in_stack; /**< Marks whether node is on the stack. */
424 int dfn; /**< Depth first search number. */
425 int uplink; /**< dfn number of ancestor. */
430 * allocates a new scc_info on the obstack
432 static inline scc_info *new_scc_info(struct obstack *obst) {
433 scc_info *info = obstack_alloc(obst, sizeof(*info));
434 memset(info, 0, sizeof(*info));
439 * Returns non-zero if a graph was already visited.
441 static inline int cg_irg_visited(ir_graph *irg) {
442 return irg->self_visited >= master_cg_visited;
446 * Marks a graph as visited.
448 static inline void mark_cg_irg_visited(ir_graph *irg) {
449 irg->self_visited = master_cg_visited;
453 * Set a graphs visited flag to i.
455 static inline void set_cg_irg_visited(ir_graph *irg, ir_visited_t i) {
456 irg->self_visited = i;
460 * Returns the visited flag of a graph.
462 static inline ir_visited_t get_cg_irg_visited(ir_graph *irg) {
463 return irg->self_visited;
466 static inline void mark_irg_in_stack(ir_graph *irg) {
467 scc_info *info = get_irg_link(irg);
468 assert(info && "missing call to init_scc()");
472 static inline void mark_irg_not_in_stack(ir_graph *irg) {
473 scc_info *info = get_irg_link(irg);
474 assert(info && "missing call to init_scc()");
478 static inline int irg_is_in_stack(ir_graph *irg) {
479 scc_info *info = get_irg_link(irg);
480 assert(info && "missing call to init_scc()");
481 return info->in_stack;
484 static inline void set_irg_uplink(ir_graph *irg, int uplink) {
485 scc_info *info = get_irg_link(irg);
486 assert(info && "missing call to init_scc()");
487 info->uplink = uplink;
490 static inline int get_irg_uplink(ir_graph *irg) {
491 scc_info *info = get_irg_link(irg);
492 assert(info && "missing call to init_scc()");
496 static inline void set_irg_dfn(ir_graph *irg, int dfn) {
497 scc_info *info = get_irg_link(irg);
498 assert(info && "missing call to init_scc()");
502 static inline int get_irg_dfn(ir_graph *irg) {
503 scc_info *info = get_irg_link(irg);
504 assert(info && "missing call to init_scc()");
508 /**********************************************************************/
510 /**********************************************************************/
512 static ir_graph **stack = NULL;
513 static int tos = 0; /**< top of stack */
516 * Initialize the irg stack.
518 static inline void init_stack(void) {
520 ARR_RESIZE(ir_graph *, stack, 1000);
522 stack = NEW_ARR_F(ir_graph *, 1000);
528 * push a graph on the irg stack
529 * @param n the graph to be pushed
531 static inline void push(ir_graph *irg) {
532 if (tos == ARR_LEN(stack)) {
533 int nlen = ARR_LEN(stack) * 2;
534 ARR_RESIZE(ir_node *, stack, nlen);
537 mark_irg_in_stack(irg);
541 * return the topmost graph on the stack and pop it
543 static inline ir_graph *pop(void) {
544 ir_graph *irg = stack[--tos];
545 mark_irg_not_in_stack(irg);
550 * The nodes up to irg belong to the current loop.
551 * Removes them from the stack and adds them to the current loop.
553 static inline void pop_scc_to_loop(ir_graph *irg) {
559 set_irg_dfn(m, loop_node_cnt);
560 add_loop_irg(current_loop, m);
562 //m->callgraph_loop_depth = current_loop->depth;
566 /* GL ??? my last son is my grandson??? Removes cfloops with no
567 ir_nodes in them. Such loops have only another loop as son. (Why
568 can't they have two loops as sons? Does it never get that far? ) */
569 static void close_loop(ir_loop *l) {
570 int last = get_loop_n_elements(l) - 1;
571 loop_element lelement = get_loop_element(l, last);
572 ir_loop *last_son = lelement.son;
574 if (get_kind(last_son) == k_ir_loop &&
575 get_loop_n_elements(last_son) == 1) {
578 lelement = get_loop_element(last_son, 0);
580 if (get_kind(gson) == k_ir_loop) {
581 loop_element new_last_son;
583 gson->outer_loop = l;
584 new_last_son.son = gson;
585 l->children[last] = new_last_son;
592 * Removes and unmarks all nodes up to n from the stack.
593 * The nodes must be visited once more to assign them to a scc.
595 static inline void pop_scc_unmark_visit(ir_graph *n) {
600 set_cg_irg_visited(m, 0);
604 /**********************************************************************/
605 /* The loop data structure. **/
606 /**********************************************************************/
609 * Allocates a new loop as son of current_loop. Sets current_loop
610 * to the new loop and returns the father.
612 static ir_loop *new_loop(void) {
613 ir_loop *father = current_loop;
614 ir_loop *son = alloc_loop(father, outermost_ir_graph->obst);
621 /**********************************************************************/
622 /* Constructing and destructing the loop/backedge information. **/
623 /**********************************************************************/
625 /* Initialization steps. **********************************************/
627 static void init_scc(struct obstack *obst) {
635 n_irgs = get_irp_n_irgs();
636 for (i = 0; i < n_irgs; ++i) {
637 ir_graph *irg = get_irp_irg(i);
638 set_irg_link(irg, new_scc_info(obst));
639 irg->callgraph_recursion_depth = 0;
640 irg->callgraph_loop_depth = 0;
644 /** Returns non-zero if n is a loop header, i.e., it is a Block node
645 * and has predecessors within the cfloop and out of the cfloop.
647 * @param root: only needed for assertion.
649 static int is_head(ir_graph *n, ir_graph *root) {
651 int some_outof_loop = 0, some_in_loop = 0;
653 arity = get_irg_n_callees(n);
654 for (i = 0; i < arity; i++) {
655 ir_graph *pred = get_irg_callee(n, i);
656 if (is_irg_callee_backedge(n, i)) continue;
657 if (!irg_is_in_stack(pred)) {
660 if (get_irg_uplink(pred) < get_irg_uplink(root)) {
661 assert(get_irg_uplink(pred) >= get_irg_uplink(root));
667 return some_outof_loop & some_in_loop;
671 * Returns non-zero if n is possible loop head of an endless loop.
672 * I.e., it is a Block, Phi or Filter node and has only predecessors
674 * @arg root: only needed for assertion.
676 static int is_endless_head(ir_graph *n, ir_graph *root)
679 int some_outof_loop = 0, some_in_loop = 0;
681 arity = get_irg_n_callees(n);
682 for (i = 0; i < arity; i++) {
683 ir_graph *pred = get_irg_callee(n, i);
685 if (is_irg_callee_backedge(n, i))
687 if (!irg_is_in_stack(pred)) {
690 if (get_irg_uplink(pred) < get_irg_uplink(root)) {
691 assert(get_irg_uplink(pred) >= get_irg_uplink(root));
696 return !some_outof_loop & some_in_loop;
699 #ifdef INTERPROCEDURAL_VIEW
701 * Check whether there is a parallel edge in the ip control flow.
704 static int is_ip_head(ir_graph *n, ir_graph *pred)
708 int iv_rem = get_interprocedural_view();
709 set_interprocedural_view(1);
711 ir_node *sblock = get_irg_start_block(n);
712 int i, arity = get_Block_n_cfgpreds(sblock);
714 //printf(" edge from "); DDMG(n);
715 //printf(" to pred "); DDMG(pred);
716 //printf(" sblock "); DDMN(sblock);
718 for (i = 0; i < arity; i++) {
719 ir_node *pred_cfop = skip_Proj(get_Block_cfgpred(sblock, i));
720 //printf(" "); DDMN(pred_cfop);
721 if (is_CallBegin(pred_cfop)) { /* could be Unknown */
722 ir_graph *ip_pred = get_irn_irg(pred_cfop);
723 //printf(" "); DDMG(ip_pred);
724 if ((ip_pred == pred) && is_backedge(sblock, i)) {
725 //printf(" found\n");
731 set_interprocedural_view(iv_rem);
734 #endif /* INTERPROCEDURAL_VIEW */
737 * Returns index of the predecessor with the smallest dfn number
738 * greater-equal than limit.
740 static int smallest_dfn_pred(ir_graph *n, int limit)
742 int i, index = -2, min = -1;
744 int arity = get_irg_n_callees(n);
745 for (i = 0; i < arity; i++) {
746 ir_graph *pred = get_irg_callee(n, i);
747 if (is_irg_callee_backedge(n, i) || !irg_is_in_stack(pred))
749 if (get_irg_dfn(pred) >= limit && (min == -1 || get_irg_dfn(pred) < min)) {
751 min = get_irg_dfn(pred);
758 /** Returns index of the predecessor with the largest dfn number. */
759 static int largest_dfn_pred(ir_graph *n) {
760 int i, index = -2, max = -1;
762 int arity = get_irg_n_callees(n);
763 for (i = 0; i < arity; ++i) {
764 ir_graph *pred = get_irg_callee(n, i);
765 if (is_irg_callee_backedge (n, i) || !irg_is_in_stack(pred)) continue;
766 if (get_irg_dfn(pred) > max) {
768 max = get_irg_dfn(pred);
775 #ifndef INTERPROCEDURAL_VIEW
776 static ir_graph *find_tail(ir_graph *n) {
778 int i, res_index = -2;
781 if (!icfg && rm_cyclic_phis && remove_cyclic_phis (n)) return NULL;
783 m = stack[tos-1]; /* tos = top of stack */
784 if (is_head (m, n)) {
785 res_index = smallest_dfn_pred(m, 0);
786 if ((res_index == -2) && /* no smallest dfn pred found. */
790 if (m == n) return NULL; // Is this to catch Phi - self loops?
791 for (i = tos-2; i >= 0; --i) {
795 res_index = smallest_dfn_pred(m, get_irg_dfn(m) + 1);
796 if (res_index == -2) /* no smallest dfn pred found. */
797 res_index = largest_dfn_pred(m);
799 if ((m == n) && (res_index == -2)) {
805 /* We should not walk past our selves on the stack: The upcoming nodes
806 are not in this loop. We assume a loop not reachable from Start. */
815 /* A dead loop not reachable from Start. */
816 for (i = tos-2; i >= 0; --i) {
818 if (is_endless_head(m, n)) {
819 res_index = smallest_dfn_pred(m, get_irg_dfn(m) + 1);
820 if (res_index == -2) /* no smallest dfn pred found. */
821 res_index = largest_dfn_pred(m);
824 if (m == n) { break; } /* It's not an unreachable loop, either. */
826 //assert(0 && "no head found on stack");
830 assert (res_index > -2);
832 set_irg_callee_backedge(m, res_index);
833 return get_irg_callee(m, res_index);
836 static ir_graph *find_tail(ir_graph *n) {
838 int i, res_index = -2;
841 ir_graph *in_and_out = NULL;
842 ir_graph *only_in = NULL;
843 ir_graph *ip_in_and_out = NULL;
844 ir_graph *ip_only_in = NULL;
846 //printf("find tail for "); DDMG(n);
848 for (i = tos-1; i >= 0; --i) {
849 ir_graph *pred = (i < tos -1) ? stack[i+1] : n;
853 //printf(" found 1a! "); DDM;
855 if (is_ip_head(pred, m)) {
856 //printf(" found 1b! "); DDM;
859 } else if (!ip_only_in && is_endless_head(m, n)) {
861 //printf(" found 2a! "); DDM;
862 if (is_ip_head(pred, m)) {
863 //printf(" found 2b! "); DDM;
866 } else if (is_ip_head(pred, m)) {
867 //printf(" found 3! "); DDM; This happens for self recursions in the second
868 //assert(0); scc iteration (the one to flip the loop.)
871 if (ip_in_and_out) break; /* That's what we really want. */
873 if (m == n) break; /* Don't walk past n on the stack! */
877 if (!in_and_out && !only_in)
878 /* There is no loop */
882 /* Is there a head in the callgraph without a head in the
884 assert(in_and_out || only_in);
886 m = (ip_in_and_out) ? ip_in_and_out : ip_only_in;
889 m = (in_and_out) ? in_and_out : only_in;
891 //printf("*** head is "); DDMG(m);
893 res_index = smallest_dfn_pred(m, get_irg_dfn(m) + 1);
894 if (res_index == -2) /* no smallest dfn pred found. */
895 res_index = largest_dfn_pred(m);
897 set_irg_callee_backedge(m, res_index);
898 res = get_irg_callee(m, res_index);
899 //printf("*** tail is "); DDMG(res);
902 #endif /* INTERPROCEDURAL_VIEW */
904 /*-----------------------------------------------------------*
905 * The core algorithm. *
906 *-----------------------------------------------------------*/
909 static void cgscc(ir_graph *n) {
912 if (cg_irg_visited(n)) return;
913 mark_cg_irg_visited(n);
915 /* Initialize the node */
916 set_irg_dfn(n, current_dfn); /* Depth first number for this node */
917 set_irg_uplink(n, current_dfn); /* ... is default uplink. */
921 arity = get_irg_n_callees(n);
922 for (i = 0; i < arity; i++) {
924 if (is_irg_callee_backedge(n, i)) continue;
925 m = get_irg_callee(n, i);
927 /** This marks the backedge, but does it guarantee a correct loop tree? */
928 //if (m == n) { set_irg_callee_backedge(n, i); continue; }
931 if (irg_is_in_stack(m)) {
932 /* Uplink of m is smaller if n->m is a backedge.
933 Propagate the uplink to mark the cfloop. */
934 if (get_irg_uplink(m) < get_irg_uplink(n))
935 set_irg_uplink(n, get_irg_uplink(m));
939 if (get_irg_dfn(n) == get_irg_uplink(n)) {
940 /* This condition holds for
941 1) the node with the incoming backedge.
942 That is: We found a cfloop!
943 2) Straight line code, because no uplink has been propagated, so the
944 uplink still is the same as the dfn.
946 But n might not be a proper cfloop head for the analysis. Proper cfloop
947 heads are Block and Phi nodes. find_tail searches the stack for
948 Block's and Phi's and takes those nodes as cfloop heads for the current
949 cfloop instead and marks the incoming edge as backedge. */
951 ir_graph *tail = find_tail(n);
953 /* We have a cfloop, that is no straight line code,
954 because we found a cfloop head!
955 Next actions: Open a new cfloop on the cfloop tree and
956 try to find inner cfloops */
959 ir_loop *l = new_loop();
961 /* Remove the cfloop from the stack ... */
962 pop_scc_unmark_visit(n);
964 /* The current backedge has been marked, that is temporarily eliminated,
965 by find tail. Start the scc algorithm
966 anew on the subgraph thats left (the current cfloop without the backedge)
967 in order to find more inner cfloops. */
971 assert(cg_irg_visited(n));
981 * reset the backedge information for all callers in all irgs
983 static void reset_isbe(void) {
984 int i, n_irgs = get_irp_n_irgs();
986 for (i = 0; i < n_irgs; ++i) {
987 ir_graph *irg = get_irp_irg(i);
989 if (irg->caller_isbe)
990 xfree(irg->caller_isbe);
991 irg->caller_isbe = NULL;
993 if (irg->callee_isbe)
994 xfree(irg->callee_isbe);
995 irg->callee_isbe = NULL;
999 /* ----------------------------------------------------------------------------------- */
1000 /* Another algorithm to compute recursion nesting depth */
1001 /* Walk the callgraph. For each crossed edge increase the loop depth by the edge */
1002 /* weight. Assign graphs the maximal depth. */
1003 /* ----------------------------------------------------------------------------------- */
1005 static void compute_loop_depth(ir_graph *irg, void *env) {
1006 int current_nesting = *(int *) env;
1007 int old_nesting = irg->callgraph_loop_depth;
1008 ir_visited_t old_visited = get_cg_irg_visited(irg);
1013 if (cg_irg_visited(irg)) return;
1015 mark_cg_irg_visited(irg);
1017 //printf(" old: %d new %d master %d", old_visited, get_cg_irg_visited(irg), master_cg_visited); DDMG(irg);
1020 if (old_nesting < current_nesting)
1021 irg->callgraph_loop_depth = current_nesting;
1023 if (current_nesting > irp->max_callgraph_loop_depth)
1024 irp->max_callgraph_loop_depth = current_nesting;
1026 if ((old_visited +1 < get_cg_irg_visited(irg)) || /* not yet visited */
1027 (old_nesting < current_nesting)) { /* propagate larger nesting */
1028 /* Don't walk the graph, but a tree that is an unfolded graph. */
1029 n_callees = get_irg_n_callees(irg);
1030 for (i = 0; i < n_callees; i++) {
1031 ir_graph *m = get_irg_callee(irg, i);
1032 *(int *)env += get_irg_callee_loop_depth(irg, i);
1033 compute_loop_depth(m, env);
1034 *(int *)env -= get_irg_callee_loop_depth(irg, i);
1038 set_cg_irg_visited(irg, master_cg_visited-1);
1041 /* ------------------------------------------------------------------------------------ */
1042 /* Another algorithm to compute recursion nesting depth */
1043 /* Walk the callgraph. For each crossed loop increase the nesting depth by one. */
1044 /* Assign graphs the maximal nesting depth. Don't increase if passing loops more than */
1046 /* ------------------------------------------------------------------------------------ */
1049 /* For callees, we want to remember the Call nodes, too. */
1050 typedef struct ana_entry2 {
1051 ir_loop **loop_stack; /**< a stack of ir_loop entries */
1052 int tos; /**< the top of stack entry */
1053 int recursion_nesting;
1057 * push a loop entry on the stack
1059 static void push2(ana_entry2 *e, ir_loop *g) {
1060 if (ARR_LEN(e->loop_stack) == e->tos) {
1061 ARR_APP1(ir_loop *, e->loop_stack, g);
1063 e->loop_stack[e->tos] = g;
1069 * returns the top of stack and pop it
1071 static ir_loop *pop2(ana_entry2 *e) {
1072 return e->loop_stack[--e->tos];
1076 * check if a loop g in on the stack. Did not check the TOS.
1078 static int in_stack(ana_entry2 *e, ir_loop *g) {
1080 for (i = e->tos-1; i >= 0; --i) {
1081 if (e->loop_stack[i] == g) return 1;
1086 static void compute_rec_depth(ir_graph *irg, void *env) {
1087 ana_entry2 *e = (ana_entry2 *)env;
1088 ir_loop *l = irg->l;
1089 int depth, old_depth = irg->callgraph_recursion_depth;
1093 if (cg_irg_visited(irg))
1095 mark_cg_irg_visited(irg);
1097 /* -- compute and set the new nesting value -- */
1098 if ((l != irp->outermost_cg_loop) && !in_stack(e, l)) {
1100 e->recursion_nesting++;
1103 depth = e->recursion_nesting;
1105 if (old_depth < depth)
1106 irg->callgraph_recursion_depth = depth;
1108 if (depth > irp->max_callgraph_recursion_depth)
1109 irp->max_callgraph_recursion_depth = depth;
1111 /* -- spread the nesting value -- */
1112 if (depth == 0 || old_depth < depth) {
1113 /* Don't walk the graph, but a tree that is an unfolded graph.
1114 Therefore we unset the visited flag at the end. */
1115 n_callees = get_irg_n_callees(irg);
1116 for (i = 0; i < n_callees; ++i) {
1117 ir_graph *m = get_irg_callee(irg, i);
1118 compute_rec_depth(m, env);
1122 /* -- clean up -- */
1125 e->recursion_nesting--;
1127 set_cg_irg_visited(irg, master_cg_visited-1);
1131 /* ----------------------------------------------------------------------------------- */
1132 /* Another algorithm to compute the execution frequency of methods ignoring recursions. */
1133 /* Walk the callgraph. Ignore backedges. Use sum of execution frequencies of Call */
1134 /* nodes to evaluate a callgraph edge. */
1135 /* ----------------------------------------------------------------------------------- */
1137 /* Returns the method execution frequency of a graph. */
1138 double get_irg_method_execution_frequency(ir_graph *irg) {
1139 return irg->method_execution_frequency;
1143 * Increase the method execution frequency to freq if its current value is
1144 * smaller then this.
1146 static void set_irg_method_execution_frequency(ir_graph *irg, double freq) {
1147 irg->method_execution_frequency = freq;
1149 if (irp->max_method_execution_frequency < freq)
1150 irp->max_method_execution_frequency = freq;
1153 static void compute_method_execution_frequency(ir_graph *irg, void *env) {
1160 if (cg_irg_visited(irg))
1163 /* We need the values of all predecessors (except backedges).
1164 So they must be marked. Else we will reach the node through
1165 one of the unmarked ones. */
1166 n_callers = get_irg_n_callers(irg);
1167 for (i = 0; i < n_callers; ++i) {
1168 ir_graph *m = get_irg_caller(irg, i);
1169 if (is_irg_caller_backedge(irg, i))
1171 if (!cg_irg_visited(m)) {
1175 mark_cg_irg_visited(irg);
1177 /* Compute the new frequency. */
1180 for (i = 0; i < n_callers; i++) {
1181 if (! is_irg_caller_backedge(irg, i)) {
1182 double edge_freq = get_irg_caller_method_execution_frequency(irg, i);
1183 assert(edge_freq >= 0);
1190 /* A starting point: method only called from outside,
1191 or only backedges as predecessors. */
1195 set_irg_method_execution_frequency(irg, freq);
1198 n_callees = get_irg_n_callees(irg);
1199 for (i = 0; i < n_callees; ++i) {
1200 compute_method_execution_frequency(get_irg_callee(irg, i), NULL);
1205 /* ----------------------------------------------------------------------------------- */
1206 /* The recursion stuff driver. */
1207 /* ----------------------------------------------------------------------------------- */
1209 /* Compute the backedges that represent recursions. */
1210 void find_callgraph_recursions(void) {
1212 struct obstack temp;
1216 /* -- compute the looptree. -- */
1218 /* The outermost graph. We start here. Then we start at all
1219 functions in irg list that are never called, then at the remaining
1220 unvisited ones. The third step is needed for functions that are not
1221 reachable from the outermost graph, but call themselves in a cycle. */
1222 assert(get_irp_main_irg());
1223 outermost_ir_graph = get_irp_main_irg();
1224 obstack_init(&temp);
1227 current_loop = NULL;
1228 new_loop(); /* sets current_loop */
1230 ++master_cg_visited;
1231 cgscc(outermost_ir_graph);
1232 n_irgs = get_irp_n_irgs();
1233 for (i = 0; i < n_irgs; ++i) {
1234 ir_graph *irg = get_irp_irg(i);
1235 if (!cg_irg_visited(irg) && get_irg_n_callers(irg) == 0)
1238 for (i = 0; i < n_irgs; ++i) {
1239 ir_graph *irg = get_irp_irg(i);
1240 if (!cg_irg_visited(irg))
1243 obstack_free(&temp, NULL);
1245 irp->outermost_cg_loop = current_loop;
1246 mature_loops(current_loop, outermost_ir_graph->obst);
1248 /* -- Reverse the backedge information. -- */
1249 for (i = 0; i < n_irgs; ++i) {
1250 ir_graph *irg = get_irp_irg(i);
1251 int j, n_callees = get_irg_n_callees(irg);
1252 for (j = 0; j < n_callees; ++j) {
1253 if (is_irg_callee_backedge(irg, j))
1254 set_irg_caller_backedge(get_irg_callee(irg, j), irg);
1258 irp->callgraph_state = irp_callgraph_and_calltree_consistent;
1261 /* Compute interprocedural performance estimates. */
1262 void compute_performance_estimates(void) {
1263 int i, n_irgs = get_irp_n_irgs();
1264 int current_nesting;
1267 assert(get_irp_exec_freq_state() != exec_freq_none && "execution frequency not calculated");
1269 /* -- compute the loop depth -- */
1270 current_nesting = 0;
1271 irp->max_callgraph_loop_depth = 0;
1272 master_cg_visited += 2;
1273 //printf(" ** starting at "); DDMG(get_irp_main_irg());
1274 compute_loop_depth(get_irp_main_irg(), ¤t_nesting);
1275 for (i = 0; i < n_irgs; i++) {
1276 ir_graph *irg = get_irp_irg(i);
1277 if ((get_cg_irg_visited(irg) < master_cg_visited-1) &&
1278 get_irg_n_callers(irg) == 0) {
1279 compute_loop_depth(irg, ¤t_nesting);
1280 //printf(" ** starting at "); DDMG(irg);
1283 for (i = 0; i < n_irgs; i++) {
1284 ir_graph *irg = get_irp_irg(i);
1285 if (get_cg_irg_visited(irg) < master_cg_visited-1) {
1286 compute_loop_depth(irg, ¤t_nesting);
1287 //printf(" ** starting at "); DDMG(irg);
1292 /* -- compute the recursion depth -- */
1293 e.loop_stack = NEW_ARR_F(ir_loop *, 0);
1295 e.recursion_nesting = 0;
1297 irp->max_callgraph_recursion_depth = 0;
1299 master_cg_visited += 2;
1300 compute_rec_depth(get_irp_main_irg(), &e);
1301 //printf(" ++ starting at "); DDMG(get_irp_main_irg());
1302 for (i = 0; i < n_irgs; i++) {
1303 ir_graph *irg = get_irp_irg(i);
1304 if ((get_cg_irg_visited(irg) < master_cg_visited-1) &&
1305 get_irg_n_callers(irg) == 0) {
1306 compute_rec_depth(irg, &e);
1307 //printf(" ++ starting at "); DDMG(irg);
1310 for (i = 0; i < n_irgs; i++) {
1311 ir_graph *irg = get_irp_irg(i);
1312 if (get_cg_irg_visited(irg) < master_cg_visited-1) {
1313 compute_rec_depth(irg, &e);
1314 //printf(" ++ starting at "); DDMG(irg);
1318 DEL_ARR_F(e.loop_stack);
1320 /* -- compute the execution frequency -- */
1321 irp->max_method_execution_frequency = 0;
1322 master_cg_visited += 2;
1323 assert(get_irg_n_callers(get_irp_main_irg()) == 0);
1324 compute_method_execution_frequency(get_irp_main_irg(), NULL);
1325 for (i = 0; i < n_irgs; i++) {
1326 ir_graph *irg = get_irp_irg(i);
1327 if ((get_cg_irg_visited(irg) < master_cg_visited-1) &&
1328 get_irg_n_callers(irg) == 0) {
1329 compute_method_execution_frequency(irg, NULL);
1332 for (i = 0; i < n_irgs; i++) {
1333 ir_graph *irg = get_irp_irg(i);
1334 if (get_cg_irg_visited(irg) < master_cg_visited-1) {
1335 compute_method_execution_frequency(irg, NULL);
1340 /* Returns the maximal loop depth of all paths from an external visible method to
1342 int get_irg_loop_depth(ir_graph *irg) {
1343 assert(irp->callgraph_state == irp_callgraph_consistent ||
1344 irp->callgraph_state == irp_callgraph_and_calltree_consistent);
1345 return irg->callgraph_loop_depth;
1348 /* Returns the maximal recursion depth of all paths from an external visible method to
1350 int get_irg_recursion_depth(ir_graph *irg) {
1351 assert(irp->callgraph_state == irp_callgraph_and_calltree_consistent);
1352 return irg->callgraph_recursion_depth;
1355 /* Computes the interprocedural loop nesting information. */
1356 void analyse_loop_nesting_depth(void) {
1357 ir_entity **free_methods = NULL;
1360 /* establish preconditions. */
1361 if (get_irp_callee_info_state() != irg_callee_info_consistent) {
1362 cgana(&arr_len, &free_methods);
1365 if (irp_callgraph_consistent != get_irp_callgraph_state()) {
1366 compute_callgraph();
1369 find_callgraph_recursions();
1371 compute_performance_estimates();
1373 set_irp_loop_nesting_depth_state(loop_nesting_depth_consistent);
1376 loop_nesting_depth_state get_irp_loop_nesting_depth_state(void) {
1377 return irp->lnd_state;
1379 void set_irp_loop_nesting_depth_state(loop_nesting_depth_state s) {
1382 void set_irp_loop_nesting_depth_state_inconsistent(void) {
1383 if (irp->lnd_state == loop_nesting_depth_consistent)
1384 irp->lnd_state = loop_nesting_depth_inconsistent;