2 * Copyright (C) 1995-2008 University of Karlsruhe. All right reserved.
4 * This file is part of libFirm.
6 * This file may be distributed and/or modified under the terms of the
7 * GNU General Public License version 2 as published by the Free Software
8 * Foundation and appearing in the file LICENSE.GPL included in the
9 * packaging of this file.
11 * Licensees holding valid libFirm Professional Edition licenses may use
12 * this file in accordance with the libFirm Commercial License.
13 * Agreement provided with the Software.
15 * This file is provided AS IS with NO WARRANTY OF ANY KIND, INCLUDING THE
16 * WARRANTY OF DESIGN, MERCHANTABILITY AND FITNESS FOR A PARTICULAR
22 * @brief Representation and computation of the callgraph.
23 * @author Goetz Lindenmaier
32 #include "callgraph.h"
36 #include "irgraph_t.h"
40 #include "execution_frequency.h"
45 #include "raw_bitset.h"
49 static ir_visited_t master_cg_visited = 0;
50 static inline int cg_irg_visited (ir_graph *n);
51 static inline void mark_cg_irg_visited(ir_graph *n);
52 static inline void set_cg_irg_visited (ir_graph *n, ir_visited_t i);
54 /** Returns the callgraph state of the program representation. */
55 irp_callgraph_state get_irp_callgraph_state(void)
57 return irp->callgraph_state;
60 /* Sets the callgraph state of the program representation. */
61 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(const ir_graph *irg)
69 if (irg->callers) return ARR_LEN(irg->callers);
73 /* Returns the caller at position pos. */
74 ir_graph *get_irg_caller(const 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(const ir_graph *irg, int pos)
84 assert(pos >= 0 && pos < get_irg_n_callers(irg));
85 return irg->caller_isbe != NULL ? rbitset_is_set(irg->caller_isbe, pos) : 0;
88 /** Search the caller in the list of all callers and set it's backedge property. */
89 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(const ir_graph *irg)
107 int i, n_callers = get_irg_n_callers(irg);
109 if (irg->caller_isbe != NULL) {
110 for (i = 0; i < n_callers; ++i)
111 if (rbitset_is_set(irg->caller_isbe, i))
118 * Find the reversion position of a caller.
119 * Given the position pos_caller of an caller of irg, return
120 * irg's callee position on that caller.
122 static int reverse_pos(const ir_graph *callee, int pos_caller)
124 ir_graph *caller = get_irg_caller(callee, pos_caller);
125 /* search the other relation for the corresponding edge. */
127 int i, n_callees = get_irg_n_callees(caller);
128 for (i = 0; i < n_callees; ++i) {
129 if (get_irg_callee(caller, i) == callee) {
135 assert(pos_callee >= 0);
140 /* Returns the maximal loop depth of call nodes that call along this edge. */
141 int get_irg_caller_loop_depth(const ir_graph *irg, int pos)
143 ir_graph *caller = get_irg_caller(irg, pos);
144 int pos_callee = reverse_pos(irg, pos);
146 return get_irg_callee_loop_depth(caller, pos_callee);
150 /* Returns the number of procedures that are called by the given irg. */
151 int get_irg_n_callees(const ir_graph *irg)
153 if (irg->callees) return ARR_LEN(irg->callees);
157 /* Returns the callee at position pos. */
158 ir_graph *get_irg_callee(const ir_graph *irg, int pos)
160 assert(pos >= 0 && pos < get_irg_n_callees(irg));
161 if (irg->callees) return irg->callees[pos]->irg;
165 /* Returns non-zero if the callee at position pos is "a backedge", i.e. a recursion. */
166 int is_irg_callee_backedge(const ir_graph *irg, int pos)
168 assert(pos >= 0 && pos < get_irg_n_callees(irg));
169 return irg->callee_isbe != NULL ? rbitset_is_set(irg->callee_isbe, pos) : 0;
172 /* Returns non-zero if the irg has a backedge callee. */
173 int has_irg_callee_backedge(const ir_graph *irg)
175 int i, n_callees = get_irg_n_callees(irg);
177 if (irg->callee_isbe != NULL) {
178 for (i = 0; i < n_callees; ++i)
179 if (rbitset_is_set(irg->callee_isbe, i))
186 * Mark the callee at position pos as a backedge.
188 static void set_irg_callee_backedge(ir_graph *irg, int pos)
190 int n = get_irg_n_callees(irg);
192 /* allocate a new array on demand */
193 if (irg->callee_isbe == NULL)
194 irg->callee_isbe = rbitset_malloc(n);
195 assert(pos >= 0 && pos < n);
196 rbitset_set(irg->callee_isbe, pos);
199 /* Returns the maximal loop depth of call nodes that call along this edge. */
200 int get_irg_callee_loop_depth(const ir_graph *irg, int pos)
202 assert(pos >= 0 && pos < get_irg_n_callees(irg));
203 if (irg->callees) return irg->callees[pos]->max_depth;
207 static double get_irg_callee_execution_frequency(const ir_graph *irg, int pos)
209 ir_node **arr = irg->callees[pos]->call_list;
210 int i, n_Calls = ARR_LEN(arr);
213 for (i = 0; i < n_Calls; ++i) {
214 freq += get_irn_exec_freq(arr[i]);
219 static double get_irg_callee_method_execution_frequency(const ir_graph *irg,
222 double call_freq = get_irg_callee_execution_frequency(irg, pos);
223 double meth_freq = get_irg_method_execution_frequency(irg);
224 return call_freq * meth_freq;
227 static double get_irg_caller_method_execution_frequency(const ir_graph *irg,
230 ir_graph *caller = get_irg_caller(irg, pos);
231 int pos_callee = reverse_pos(irg, pos);
233 return get_irg_callee_method_execution_frequency(caller, pos_callee);
237 /* --------------------- Compute the callgraph ------------------------ */
240 * Walker called by compute_callgraph(), analyses all Call nodes.
242 static void ana_Call(ir_node *n, void *env)
248 if (! is_Call(n)) return;
250 irg = get_irn_irg(n);
251 n_callees = get_Call_n_callees(n);
252 for (i = 0; i < n_callees; ++i) {
253 ir_entity *callee_e = get_Call_callee(n, i);
254 ir_graph *callee = get_entity_irg(callee_e);
258 cg_callee_entry *found;
263 pset_insert((pset *)callee->callers, irg, HASH_PTR(irg));
264 found = pset_find((pset *)irg->callees, &buf, HASH_PTR(callee));
265 if (found) { /* add Call node to list, compute new nesting. */
266 ir_node **arr = found->call_list;
267 ARR_APP1(ir_node *, arr, n);
268 found->call_list = arr;
269 } else { /* New node, add Call node and init nesting. */
270 found = OALLOC(irg->obst, cg_callee_entry);
272 found->call_list = NEW_ARR_F(ir_node *, 1);
273 found->call_list[0] = n;
274 found->max_depth = 0;
275 pset_insert((pset *)irg->callees, found, HASH_PTR(callee));
277 depth = get_loop_depth(get_irn_loop(get_nodes_block(n)));
278 found->max_depth = (depth > found->max_depth) ? depth : found->max_depth;
283 /** compare two ir graphs in a cg_callee_entry */
284 static int cg_callee_entry_cmp(const void *elt, const void *key)
286 const cg_callee_entry *e1 = elt;
287 const cg_callee_entry *e2 = key;
288 return e1->irg != e2->irg;
291 /** compare two ir graphs for pointer identity */
292 static int graph_cmp(const void *elt, const void *key)
294 const ir_graph *e1 = elt;
295 const ir_graph *e2 = key;
300 /* Construct and destruct the callgraph. */
301 void compute_callgraph(void)
305 #ifdef INTERPROCEDURAL_VIEW
306 assert(! get_interprocedural_view()); /* Else walking will not reach the Call nodes. */
312 n_irgs = get_irp_n_irgs();
313 for (i = 0; i < n_irgs; ++i) {
314 ir_graph *irg = get_irp_irg(i);
315 assert(get_irg_callee_info_state(irg) == irg_callee_info_consistent);
316 irg->callees = (cg_callee_entry **)new_pset(cg_callee_entry_cmp, 8);
317 irg->callers = (ir_graph **)new_pset(graph_cmp, 8);
318 //construct_cf_backedges(irg);
321 /* Compute the call graph */
322 for (i = 0; i < n_irgs; ++i) {
323 ir_graph *irg = get_irp_irg(i);
324 construct_cf_backedges(irg); // We also find the maximal loop depth of a call.
325 irg_walk_graph(irg, ana_Call, NULL, NULL);
328 /* Change the sets to arrays. */
329 for (i = 0; i < n_irgs; ++i) {
331 cg_callee_entry *callee;
332 ir_graph *c, *irg = get_irp_irg(i);
333 pset *callee_set, *caller_set;
335 callee_set = (pset *)irg->callees;
336 count = pset_count(callee_set);
337 irg->callees = NEW_ARR_F(cg_callee_entry *, count);
338 irg->callee_isbe = NULL;
339 callee = pset_first(callee_set);
340 for (j = 0; j < count; ++j) {
341 irg->callees[j] = callee;
342 callee = pset_next(callee_set);
344 del_pset(callee_set);
345 assert(callee == NULL);
347 caller_set = (pset *)irg->callers;
348 count = pset_count(caller_set);
349 irg->callers = NEW_ARR_F(ir_graph *, count);
350 irg->caller_isbe = NULL;
351 c = pset_first(caller_set);
352 for (j = 0; j < count; ++j) {
354 c = pset_next(caller_set);
356 del_pset(caller_set);
359 set_irp_callgraph_state(irp_callgraph_consistent);
362 /* Destruct the callgraph. */
363 void free_callgraph(void)
365 int i, n_irgs = get_irp_n_irgs();
366 for (i = 0; i < n_irgs; ++i) {
367 ir_graph *irg = get_irp_irg(i);
368 if (irg->callees) DEL_ARR_F(irg->callees);
369 if (irg->callers) DEL_ARR_F(irg->callers);
370 if (irg->callee_isbe) free(irg->callee_isbe);
371 if (irg->caller_isbe) free(irg->caller_isbe);
374 irg->callee_isbe = NULL;
375 irg->caller_isbe = NULL;
377 set_irp_callgraph_state(irp_callgraph_none);
380 /* ----------------------------------------------------------------------------------- */
381 /* A walker for the callgraph */
382 /* ----------------------------------------------------------------------------------- */
385 static void do_walk(ir_graph *irg, callgraph_walk_func *pre, callgraph_walk_func *post, void *env)
389 if (cg_irg_visited(irg))
391 mark_cg_irg_visited(irg);
396 n_callees = get_irg_n_callees(irg);
397 for (i = 0; i < n_callees; i++) {
398 ir_graph *m = get_irg_callee(irg, i);
399 do_walk(m, pre, post, env);
406 void callgraph_walk(callgraph_walk_func *pre, callgraph_walk_func *post, void *env)
408 int i, n_irgs = get_irp_n_irgs();
411 /* roots are methods which have no callers in the current program */
412 for (i = 0; i < n_irgs; ++i) {
413 ir_graph *irg = get_irp_irg(i);
415 if (get_irg_n_callers(irg) == 0)
416 do_walk(irg, pre, post, env);
419 /* in case of unreachable call loops we haven't visited some irgs yet */
420 for (i = 0; i < n_irgs; i++) {
421 ir_graph *irg = get_irp_irg(i);
422 do_walk(irg, pre, post, env);
426 /* ----------------------------------------------------------------------------------- */
427 /* loop construction algorithm */
428 /* ----------------------------------------------------------------------------------- */
430 static ir_graph *outermost_ir_graph; /**< The outermost graph the scc is computed
432 static ir_loop *current_loop; /**< Current cfloop construction is working
434 static int loop_node_cnt = 0; /**< Counts the number of allocated cfloop nodes.
435 Each cfloop node gets a unique number.
436 What for? ev. remove. @@@ */
437 static int current_dfn = 1; /**< Counter to generate depth first numbering
440 /*-----------------*/
441 /* Node attributes */
442 /*-----------------*/
444 typedef struct scc_info {
445 int in_stack; /**< Marks whether node is on the stack. */
446 int dfn; /**< Depth first search number. */
447 int uplink; /**< dfn number of ancestor. */
452 * allocates a new scc_info on the obstack
454 static inline scc_info *new_scc_info(struct obstack *obst)
456 return OALLOCZ(obst, scc_info);
460 * Returns non-zero if a graph was already visited.
462 static inline int cg_irg_visited(ir_graph *irg)
464 return irg->self_visited >= master_cg_visited;
468 * Marks a graph as visited.
470 static inline void mark_cg_irg_visited(ir_graph *irg)
472 irg->self_visited = master_cg_visited;
476 * Set a graphs visited flag to i.
478 static inline void set_cg_irg_visited(ir_graph *irg, ir_visited_t i)
480 irg->self_visited = i;
484 * Returns the visited flag of a graph.
486 static inline ir_visited_t get_cg_irg_visited(ir_graph *irg)
488 return irg->self_visited;
491 static inline void mark_irg_in_stack(ir_graph *irg)
493 scc_info *info = get_irg_link(irg);
494 assert(info && "missing call to init_scc()");
498 static inline void mark_irg_not_in_stack(ir_graph *irg)
500 scc_info *info = get_irg_link(irg);
501 assert(info && "missing call to init_scc()");
505 static inline int irg_is_in_stack(ir_graph *irg)
507 scc_info *info = get_irg_link(irg);
508 assert(info && "missing call to init_scc()");
509 return info->in_stack;
512 static inline void set_irg_uplink(ir_graph *irg, int uplink)
514 scc_info *info = get_irg_link(irg);
515 assert(info && "missing call to init_scc()");
516 info->uplink = uplink;
519 static inline int get_irg_uplink(ir_graph *irg)
521 scc_info *info = get_irg_link(irg);
522 assert(info && "missing call to init_scc()");
526 static inline void set_irg_dfn(ir_graph *irg, int dfn)
528 scc_info *info = get_irg_link(irg);
529 assert(info && "missing call to init_scc()");
533 static inline int get_irg_dfn(ir_graph *irg)
535 scc_info *info = get_irg_link(irg);
536 assert(info && "missing call to init_scc()");
540 /**********************************************************************/
542 /**********************************************************************/
544 static ir_graph **stack = NULL;
545 static int tos = 0; /**< top of stack */
548 * Initialize the irg stack.
550 static inline void init_stack(void)
553 ARR_RESIZE(ir_graph *, stack, 1000);
555 stack = NEW_ARR_F(ir_graph *, 1000);
561 * push a graph on the irg stack
562 * @param n the graph to be pushed
564 static inline void push(ir_graph *irg)
566 if (tos == ARR_LEN(stack)) {
567 int nlen = ARR_LEN(stack) * 2;
568 ARR_RESIZE(ir_node *, stack, nlen);
571 mark_irg_in_stack(irg);
575 * return the topmost graph on the stack and pop it
577 static inline ir_graph *pop(void)
579 ir_graph *irg = stack[--tos];
580 mark_irg_not_in_stack(irg);
585 * The nodes up to irg belong to the current loop.
586 * Removes them from the stack and adds them to the current loop.
588 static inline void pop_scc_to_loop(ir_graph *irg)
595 set_irg_dfn(m, loop_node_cnt);
596 add_loop_irg(current_loop, m);
598 //m->callgraph_loop_depth = current_loop->depth;
602 /* GL ??? my last son is my grandson??? Removes cfloops with no
603 ir_nodes in them. Such loops have only another loop as son. (Why
604 can't they have two loops as sons? Does it never get that far? ) */
605 static void close_loop(ir_loop *l)
607 int last = get_loop_n_elements(l) - 1;
608 loop_element lelement = get_loop_element(l, last);
609 ir_loop *last_son = lelement.son;
611 if (get_kind(last_son) == k_ir_loop &&
612 get_loop_n_elements(last_son) == 1) {
615 lelement = get_loop_element(last_son, 0);
617 if (get_kind(gson) == k_ir_loop) {
618 loop_element new_last_son;
620 gson->outer_loop = l;
621 new_last_son.son = gson;
622 l->children[last] = new_last_son;
629 * Removes and unmarks all nodes up to n from the stack.
630 * The nodes must be visited once more to assign them to a scc.
632 static inline void pop_scc_unmark_visit(ir_graph *n)
638 set_cg_irg_visited(m, 0);
642 /**********************************************************************/
643 /* The loop data structure. **/
644 /**********************************************************************/
647 * Allocates a new loop as son of current_loop. Sets current_loop
648 * to the new loop and returns the father.
650 static ir_loop *new_loop(void)
652 ir_loop *father = current_loop;
653 ir_loop *son = alloc_loop(father, outermost_ir_graph->obst);
660 /**********************************************************************/
661 /* Constructing and destructing the loop/backedge information. **/
662 /**********************************************************************/
664 /* Initialization steps. **********************************************/
666 static void init_scc(struct obstack *obst)
675 n_irgs = get_irp_n_irgs();
676 for (i = 0; i < n_irgs; ++i) {
677 ir_graph *irg = get_irp_irg(i);
678 set_irg_link(irg, new_scc_info(obst));
679 irg->callgraph_recursion_depth = 0;
680 irg->callgraph_loop_depth = 0;
684 /** Returns non-zero if n is a loop header, i.e., it is a Block node
685 * and has predecessors within the cfloop and out of the cfloop.
687 * @param root: only needed for assertion.
689 static int is_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);
697 if (is_irg_callee_backedge(n, i)) continue;
698 if (!irg_is_in_stack(pred)) {
701 if (get_irg_uplink(pred) < get_irg_uplink(root)) {
702 assert(get_irg_uplink(pred) >= get_irg_uplink(root));
708 return some_outof_loop && some_in_loop;
712 * Returns non-zero if n is possible loop head of an endless loop.
713 * I.e., it is a Block, Phi or Filter node and has only predecessors
715 * @arg root: only needed for assertion.
717 static int is_endless_head(ir_graph *n, ir_graph *root)
720 int some_outof_loop = 0, some_in_loop = 0;
722 arity = get_irg_n_callees(n);
723 for (i = 0; i < arity; i++) {
724 ir_graph *pred = get_irg_callee(n, i);
726 if (is_irg_callee_backedge(n, i))
728 if (!irg_is_in_stack(pred)) {
731 if (get_irg_uplink(pred) < get_irg_uplink(root)) {
732 assert(get_irg_uplink(pred) >= get_irg_uplink(root));
737 return !some_outof_loop && some_in_loop;
740 #ifdef INTERPROCEDURAL_VIEW
742 * Check whether there is a parallel edge in the ip control flow.
745 static int is_ip_head(ir_graph *n, ir_graph *pred)
749 int iv_rem = get_interprocedural_view();
750 set_interprocedural_view(1);
752 ir_node *sblock = get_irg_start_block(n);
753 int i, arity = get_Block_n_cfgpreds(sblock);
755 //printf(" edge from "); DDMG(n);
756 //printf(" to pred "); DDMG(pred);
757 //printf(" sblock "); DDMN(sblock);
759 for (i = 0; i < arity; i++) {
760 ir_node *pred_cfop = skip_Proj(get_Block_cfgpred(sblock, i));
761 //printf(" "); DDMN(pred_cfop);
762 if (is_CallBegin(pred_cfop)) { /* could be Unknown */
763 ir_graph *ip_pred = get_irn_irg(pred_cfop);
764 //printf(" "); DDMG(ip_pred);
765 if ((ip_pred == pred) && is_backedge(sblock, i)) {
766 //printf(" found\n");
772 set_interprocedural_view(iv_rem);
775 #endif /* INTERPROCEDURAL_VIEW */
778 * Returns index of the predecessor with the smallest dfn number
779 * greater-equal than limit.
781 static int smallest_dfn_pred(ir_graph *n, int limit)
783 int i, index = -2, min = -1;
785 int arity = get_irg_n_callees(n);
786 for (i = 0; i < arity; i++) {
787 ir_graph *pred = get_irg_callee(n, i);
788 if (is_irg_callee_backedge(n, i) || !irg_is_in_stack(pred))
790 if (get_irg_dfn(pred) >= limit && (min == -1 || get_irg_dfn(pred) < min)) {
792 min = get_irg_dfn(pred);
799 /** Returns index of the predecessor with the largest dfn number. */
800 static int largest_dfn_pred(ir_graph *n)
802 int i, index = -2, max = -1;
804 int arity = get_irg_n_callees(n);
805 for (i = 0; i < arity; ++i) {
806 ir_graph *pred = get_irg_callee(n, i);
807 if (is_irg_callee_backedge (n, i) || !irg_is_in_stack(pred)) continue;
808 if (get_irg_dfn(pred) > max) {
810 max = get_irg_dfn(pred);
817 #ifndef INTERPROCEDURAL_VIEW
818 static ir_graph *find_tail(ir_graph *n)
821 int i, res_index = -2;
824 if (!icfg && rm_cyclic_phis && remove_cyclic_phis (n)) return NULL;
826 m = stack[tos-1]; /* tos = top of stack */
827 if (is_head (m, n)) {
828 res_index = smallest_dfn_pred(m, 0);
829 if ((res_index == -2) && /* no smallest dfn pred found. */
833 if (m == n) return NULL; // Is this to catch Phi - self loops?
834 for (i = tos-2; i >= 0; --i) {
838 res_index = smallest_dfn_pred(m, get_irg_dfn(m) + 1);
839 if (res_index == -2) /* no smallest dfn pred found. */
840 res_index = largest_dfn_pred(m);
842 if ((m == n) && (res_index == -2)) {
848 /* We should not walk past our selves on the stack: The upcoming nodes
849 are not in this loop. We assume a loop not reachable from Start. */
858 /* A dead loop not reachable from Start. */
859 for (i = tos-2; i >= 0; --i) {
861 if (is_endless_head(m, n)) {
862 res_index = smallest_dfn_pred(m, get_irg_dfn(m) + 1);
863 if (res_index == -2) /* no smallest dfn pred found. */
864 res_index = largest_dfn_pred(m);
867 if (m == n) { break; } /* It's not an unreachable loop, either. */
869 //assert(0 && "no head found on stack");
873 assert (res_index > -2);
875 set_irg_callee_backedge(m, res_index);
876 return get_irg_callee(m, res_index);
879 static ir_graph *find_tail(ir_graph *n)
882 int i, res_index = -2;
885 ir_graph *in_and_out = NULL;
886 ir_graph *only_in = NULL;
887 ir_graph *ip_in_and_out = NULL;
888 ir_graph *ip_only_in = NULL;
890 //printf("find tail for "); DDMG(n);
892 for (i = tos-1; i >= 0; --i) {
893 ir_graph *pred = (i < tos -1) ? stack[i+1] : n;
897 //printf(" found 1a! "); DDM;
899 if (is_ip_head(pred, m)) {
900 //printf(" found 1b! "); DDM;
903 } else if (!ip_only_in && is_endless_head(m, n)) {
905 //printf(" found 2a! "); DDM;
906 if (is_ip_head(pred, m)) {
907 //printf(" found 2b! "); DDM;
910 } else if (is_ip_head(pred, m)) {
911 //printf(" found 3! "); DDM; This happens for self recursions in the second
912 //assert(0); scc iteration (the one to flip the loop.)
915 if (ip_in_and_out) break; /* That's what we really want. */
917 if (m == n) break; /* Don't walk past n on the stack! */
921 if (!in_and_out && !only_in)
922 /* There is no loop */
926 /* Is there a head in the callgraph without a head in the
928 assert(in_and_out || only_in);
930 m = (ip_in_and_out) ? ip_in_and_out : ip_only_in;
933 m = (in_and_out) ? in_and_out : only_in;
935 //printf("*** head is "); DDMG(m);
937 res_index = smallest_dfn_pred(m, get_irg_dfn(m) + 1);
938 if (res_index == -2) /* no smallest dfn pred found. */
939 res_index = largest_dfn_pred(m);
941 set_irg_callee_backedge(m, res_index);
942 res = get_irg_callee(m, res_index);
943 //printf("*** tail is "); DDMG(res);
946 #endif /* INTERPROCEDURAL_VIEW */
948 /*-----------------------------------------------------------*
949 * The core algorithm. *
950 *-----------------------------------------------------------*/
953 static void cgscc(ir_graph *n)
957 if (cg_irg_visited(n)) return;
958 mark_cg_irg_visited(n);
960 /* Initialize the node */
961 set_irg_dfn(n, current_dfn); /* Depth first number for this node */
962 set_irg_uplink(n, current_dfn); /* ... is default uplink. */
966 arity = get_irg_n_callees(n);
967 for (i = 0; i < arity; i++) {
969 if (is_irg_callee_backedge(n, i)) continue;
970 m = get_irg_callee(n, i);
972 /** This marks the backedge, but does it guarantee a correct loop tree? */
973 //if (m == n) { set_irg_callee_backedge(n, i); continue; }
976 if (irg_is_in_stack(m)) {
977 /* Uplink of m is smaller if n->m is a backedge.
978 Propagate the uplink to mark the cfloop. */
979 if (get_irg_uplink(m) < get_irg_uplink(n))
980 set_irg_uplink(n, get_irg_uplink(m));
984 if (get_irg_dfn(n) == get_irg_uplink(n)) {
985 /* This condition holds for
986 1) the node with the incoming backedge.
987 That is: We found a cfloop!
988 2) Straight line code, because no uplink has been propagated, so the
989 uplink still is the same as the dfn.
991 But n might not be a proper cfloop head for the analysis. Proper cfloop
992 heads are Block and Phi nodes. find_tail searches the stack for
993 Block's and Phi's and takes those nodes as cfloop heads for the current
994 cfloop instead and marks the incoming edge as backedge. */
996 ir_graph *tail = find_tail(n);
998 /* We have a cfloop, that is no straight line code,
999 because we found a cfloop head!
1000 Next actions: Open a new cfloop on the cfloop tree and
1001 try to find inner cfloops */
1004 ir_loop *l = new_loop();
1006 /* Remove the cfloop from the stack ... */
1007 pop_scc_unmark_visit(n);
1009 /* The current backedge has been marked, that is temporarily eliminated,
1010 by find tail. Start the scc algorithm
1011 anew on the subgraph thats left (the current cfloop without the backedge)
1012 in order to find more inner cfloops. */
1016 assert(cg_irg_visited(n));
1026 * reset the backedge information for all callers in all irgs
1028 static void reset_isbe(void)
1030 int i, n_irgs = get_irp_n_irgs();
1032 for (i = 0; i < n_irgs; ++i) {
1033 ir_graph *irg = get_irp_irg(i);
1035 if (irg->caller_isbe)
1036 xfree(irg->caller_isbe);
1037 irg->caller_isbe = NULL;
1039 if (irg->callee_isbe)
1040 xfree(irg->callee_isbe);
1041 irg->callee_isbe = NULL;
1045 /* ----------------------------------------------------------------------------------- */
1046 /* Another algorithm to compute recursion nesting depth */
1047 /* Walk the callgraph. For each crossed edge increase the loop depth by the edge */
1048 /* weight. Assign graphs the maximal depth. */
1049 /* ----------------------------------------------------------------------------------- */
1051 static void compute_loop_depth(ir_graph *irg, void *env)
1053 int current_nesting = *(int *) env;
1054 int old_nesting = irg->callgraph_loop_depth;
1055 ir_visited_t old_visited = get_cg_irg_visited(irg);
1060 if (cg_irg_visited(irg)) return;
1062 mark_cg_irg_visited(irg);
1064 //printf(" old: %d new %d master %d", old_visited, get_cg_irg_visited(irg), master_cg_visited); DDMG(irg);
1067 if (old_nesting < current_nesting)
1068 irg->callgraph_loop_depth = current_nesting;
1070 if (current_nesting > irp->max_callgraph_loop_depth)
1071 irp->max_callgraph_loop_depth = current_nesting;
1073 if ((old_visited +1 < get_cg_irg_visited(irg)) || /* not yet visited */
1074 (old_nesting < current_nesting)) { /* propagate larger nesting */
1075 /* Don't walk the graph, but a tree that is an unfolded graph. */
1076 n_callees = get_irg_n_callees(irg);
1077 for (i = 0; i < n_callees; i++) {
1078 ir_graph *m = get_irg_callee(irg, i);
1079 *(int *)env += get_irg_callee_loop_depth(irg, i);
1080 compute_loop_depth(m, env);
1081 *(int *)env -= get_irg_callee_loop_depth(irg, i);
1085 set_cg_irg_visited(irg, master_cg_visited-1);
1088 /* ------------------------------------------------------------------------------------ */
1089 /* Another algorithm to compute recursion nesting depth */
1090 /* Walk the callgraph. For each crossed loop increase the nesting depth by one. */
1091 /* Assign graphs the maximal nesting depth. Don't increase if passing loops more than */
1093 /* ------------------------------------------------------------------------------------ */
1096 /* For callees, we want to remember the Call nodes, too. */
1097 typedef struct ana_entry2 {
1098 ir_loop **loop_stack; /**< a stack of ir_loop entries */
1099 int tos; /**< the top of stack entry */
1100 int recursion_nesting;
1104 * push a loop entry on the stack
1106 static void push2(ana_entry2 *e, ir_loop *g)
1108 if (ARR_LEN(e->loop_stack) == e->tos) {
1109 ARR_APP1(ir_loop *, e->loop_stack, g);
1111 e->loop_stack[e->tos] = g;
1117 * returns the top of stack and pop it
1119 static ir_loop *pop2(ana_entry2 *e)
1121 return e->loop_stack[--e->tos];
1125 * check if a loop g in on the stack. Did not check the TOS.
1127 static int in_stack(ana_entry2 *e, ir_loop *g)
1130 for (i = e->tos-1; i >= 0; --i) {
1131 if (e->loop_stack[i] == g) return 1;
1136 static void compute_rec_depth(ir_graph *irg, void *env)
1138 ana_entry2 *e = (ana_entry2 *)env;
1139 ir_loop *l = irg->l;
1140 int depth, old_depth = irg->callgraph_recursion_depth;
1144 if (cg_irg_visited(irg))
1146 mark_cg_irg_visited(irg);
1148 /* -- compute and set the new nesting value -- */
1149 if ((l != irp->outermost_cg_loop) && !in_stack(e, l)) {
1151 e->recursion_nesting++;
1154 depth = e->recursion_nesting;
1156 if (old_depth < depth)
1157 irg->callgraph_recursion_depth = depth;
1159 if (depth > irp->max_callgraph_recursion_depth)
1160 irp->max_callgraph_recursion_depth = depth;
1162 /* -- spread the nesting value -- */
1163 if (depth == 0 || old_depth < depth) {
1164 /* Don't walk the graph, but a tree that is an unfolded graph.
1165 Therefore we unset the visited flag at the end. */
1166 n_callees = get_irg_n_callees(irg);
1167 for (i = 0; i < n_callees; ++i) {
1168 ir_graph *m = get_irg_callee(irg, i);
1169 compute_rec_depth(m, env);
1173 /* -- clean up -- */
1176 e->recursion_nesting--;
1178 set_cg_irg_visited(irg, master_cg_visited-1);
1182 /* ----------------------------------------------------------------------------------- */
1183 /* Another algorithm to compute the execution frequency of methods ignoring recursions. */
1184 /* Walk the callgraph. Ignore backedges. Use sum of execution frequencies of Call */
1185 /* nodes to evaluate a callgraph edge. */
1186 /* ----------------------------------------------------------------------------------- */
1188 /* Returns the method execution frequency of a graph. */
1189 double get_irg_method_execution_frequency(const ir_graph *irg)
1191 return irg->method_execution_frequency;
1195 * Increase the method execution frequency to freq if its current value is
1196 * smaller then this.
1198 static void set_irg_method_execution_frequency(ir_graph *irg, double freq)
1200 irg->method_execution_frequency = freq;
1202 if (irp->max_method_execution_frequency < freq)
1203 irp->max_method_execution_frequency = freq;
1206 static void compute_method_execution_frequency(ir_graph *irg, void *env)
1214 if (cg_irg_visited(irg))
1217 /* We need the values of all predecessors (except backedges).
1218 So they must be marked. Else we will reach the node through
1219 one of the unmarked ones. */
1220 n_callers = get_irg_n_callers(irg);
1221 for (i = 0; i < n_callers; ++i) {
1222 ir_graph *m = get_irg_caller(irg, i);
1223 if (is_irg_caller_backedge(irg, i))
1225 if (!cg_irg_visited(m)) {
1229 mark_cg_irg_visited(irg);
1231 /* Compute the new frequency. */
1234 for (i = 0; i < n_callers; i++) {
1235 if (! is_irg_caller_backedge(irg, i)) {
1236 double edge_freq = get_irg_caller_method_execution_frequency(irg, i);
1237 assert(edge_freq >= 0);
1244 /* A starting point: method only called from outside,
1245 or only backedges as predecessors. */
1249 set_irg_method_execution_frequency(irg, freq);
1252 n_callees = get_irg_n_callees(irg);
1253 for (i = 0; i < n_callees; ++i) {
1254 compute_method_execution_frequency(get_irg_callee(irg, i), NULL);
1259 /* ----------------------------------------------------------------------------------- */
1260 /* The recursion stuff driver. */
1261 /* ----------------------------------------------------------------------------------- */
1263 /* Compute the backedges that represent recursions. */
1264 void find_callgraph_recursions(void)
1267 struct obstack temp;
1271 /* -- compute the looptree. -- */
1273 /* The outermost graph. We start here. Then we start at all
1274 functions in irg list that are never called, then at the remaining
1275 unvisited ones. The third step is needed for functions that are not
1276 reachable from the outermost graph, but call themselves in a cycle. */
1277 assert(get_irp_main_irg());
1278 outermost_ir_graph = get_irp_main_irg();
1279 obstack_init(&temp);
1282 current_loop = NULL;
1283 new_loop(); /* sets current_loop */
1285 ++master_cg_visited;
1286 cgscc(outermost_ir_graph);
1287 n_irgs = get_irp_n_irgs();
1288 for (i = 0; i < n_irgs; ++i) {
1289 ir_graph *irg = get_irp_irg(i);
1290 if (!cg_irg_visited(irg) && get_irg_n_callers(irg) == 0)
1293 for (i = 0; i < n_irgs; ++i) {
1294 ir_graph *irg = get_irp_irg(i);
1295 if (!cg_irg_visited(irg))
1298 obstack_free(&temp, NULL);
1300 irp->outermost_cg_loop = current_loop;
1301 mature_loops(current_loop, outermost_ir_graph->obst);
1303 /* -- Reverse the backedge information. -- */
1304 for (i = 0; i < n_irgs; ++i) {
1305 ir_graph *irg = get_irp_irg(i);
1306 int j, n_callees = get_irg_n_callees(irg);
1307 for (j = 0; j < n_callees; ++j) {
1308 if (is_irg_callee_backedge(irg, j))
1309 set_irg_caller_backedge(get_irg_callee(irg, j), irg);
1313 irp->callgraph_state = irp_callgraph_and_calltree_consistent;
1316 /* Compute interprocedural performance estimates. */
1317 void compute_performance_estimates(void)
1319 int i, n_irgs = get_irp_n_irgs();
1320 int current_nesting;
1323 assert(get_irp_exec_freq_state() != exec_freq_none && "execution frequency not calculated");
1325 /* -- compute the loop depth -- */
1326 current_nesting = 0;
1327 irp->max_callgraph_loop_depth = 0;
1328 master_cg_visited += 2;
1329 //printf(" ** starting at "); DDMG(get_irp_main_irg());
1330 compute_loop_depth(get_irp_main_irg(), ¤t_nesting);
1331 for (i = 0; i < n_irgs; i++) {
1332 ir_graph *irg = get_irp_irg(i);
1333 if ((get_cg_irg_visited(irg) < master_cg_visited-1) &&
1334 get_irg_n_callers(irg) == 0) {
1335 compute_loop_depth(irg, ¤t_nesting);
1336 //printf(" ** starting at "); DDMG(irg);
1339 for (i = 0; i < n_irgs; i++) {
1340 ir_graph *irg = get_irp_irg(i);
1341 if (get_cg_irg_visited(irg) < master_cg_visited-1) {
1342 compute_loop_depth(irg, ¤t_nesting);
1343 //printf(" ** starting at "); DDMG(irg);
1348 /* -- compute the recursion depth -- */
1349 e.loop_stack = NEW_ARR_F(ir_loop *, 0);
1351 e.recursion_nesting = 0;
1353 irp->max_callgraph_recursion_depth = 0;
1355 master_cg_visited += 2;
1356 compute_rec_depth(get_irp_main_irg(), &e);
1357 //printf(" ++ starting at "); DDMG(get_irp_main_irg());
1358 for (i = 0; i < n_irgs; i++) {
1359 ir_graph *irg = get_irp_irg(i);
1360 if ((get_cg_irg_visited(irg) < master_cg_visited-1) &&
1361 get_irg_n_callers(irg) == 0) {
1362 compute_rec_depth(irg, &e);
1363 //printf(" ++ starting at "); DDMG(irg);
1366 for (i = 0; i < n_irgs; i++) {
1367 ir_graph *irg = get_irp_irg(i);
1368 if (get_cg_irg_visited(irg) < master_cg_visited-1) {
1369 compute_rec_depth(irg, &e);
1370 //printf(" ++ starting at "); DDMG(irg);
1374 DEL_ARR_F(e.loop_stack);
1376 /* -- compute the execution frequency -- */
1377 irp->max_method_execution_frequency = 0;
1378 master_cg_visited += 2;
1379 assert(get_irg_n_callers(get_irp_main_irg()) == 0);
1380 compute_method_execution_frequency(get_irp_main_irg(), NULL);
1381 for (i = 0; i < n_irgs; i++) {
1382 ir_graph *irg = get_irp_irg(i);
1383 if ((get_cg_irg_visited(irg) < master_cg_visited-1) &&
1384 get_irg_n_callers(irg) == 0) {
1385 compute_method_execution_frequency(irg, NULL);
1388 for (i = 0; i < n_irgs; i++) {
1389 ir_graph *irg = get_irp_irg(i);
1390 if (get_cg_irg_visited(irg) < master_cg_visited-1) {
1391 compute_method_execution_frequency(irg, NULL);
1396 /* Returns the maximal loop depth of all paths from an external visible method to
1398 int get_irg_loop_depth(const ir_graph *irg)
1400 assert(irp->callgraph_state == irp_callgraph_consistent ||
1401 irp->callgraph_state == irp_callgraph_and_calltree_consistent);
1402 return irg->callgraph_loop_depth;
1405 /* Returns the maximal recursion depth of all paths from an external visible method to
1407 int get_irg_recursion_depth(const ir_graph *irg)
1409 assert(irp->callgraph_state == irp_callgraph_and_calltree_consistent);
1410 return irg->callgraph_recursion_depth;
1413 /* Computes the interprocedural loop nesting information. */
1414 void analyse_loop_nesting_depth(void)
1416 ir_entity **free_methods = NULL;
1419 /* establish preconditions. */
1420 if (get_irp_callee_info_state() != irg_callee_info_consistent) {
1421 cgana(&arr_len, &free_methods);
1424 if (irp_callgraph_consistent != get_irp_callgraph_state()) {
1425 compute_callgraph();
1428 find_callgraph_recursions();
1430 compute_performance_estimates();
1432 set_irp_loop_nesting_depth_state(loop_nesting_depth_consistent);
1435 loop_nesting_depth_state get_irp_loop_nesting_depth_state(void)
1437 return irp->lnd_state;
1439 void set_irp_loop_nesting_depth_state(loop_nesting_depth_state s)
1443 void set_irp_loop_nesting_depth_state_inconsistent(void)
1445 if (irp->lnd_state == loop_nesting_depth_consistent)
1446 irp->lnd_state = loop_nesting_depth_inconsistent;