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;
208 double get_irg_callee_execution_frequency(const ir_graph *irg, int pos)
210 ir_node **arr = irg->callees[pos]->call_list;
211 int i, n_Calls = ARR_LEN(arr);
214 for (i = 0; i < n_Calls; ++i) {
215 freq += get_irn_exec_freq(arr[i]);
220 double get_irg_callee_method_execution_frequency(const ir_graph *irg, int pos)
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;
228 double get_irg_caller_method_execution_frequency(const ir_graph *irg, int pos)
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);
238 /* --------------------- Compute the callgraph ------------------------ */
241 * Walker called by compute_callgraph(), analyses all Call nodes.
243 static void ana_Call(ir_node *n, void *env)
249 if (! is_Call(n)) return;
251 irg = get_irn_irg(n);
252 n_callees = get_Call_n_callees(n);
253 for (i = 0; i < n_callees; ++i) {
254 ir_entity *callee_e = get_Call_callee(n, i);
255 ir_graph *callee = get_entity_irg(callee_e);
259 cg_callee_entry *found;
264 pset_insert((pset *)callee->callers, irg, HASH_PTR(irg));
265 found = pset_find((pset *)irg->callees, &buf, HASH_PTR(callee));
266 if (found) { /* add Call node to list, compute new nesting. */
267 ir_node **arr = found->call_list;
268 ARR_APP1(ir_node *, arr, n);
269 found->call_list = arr;
270 } else { /* New node, add Call node and init nesting. */
271 found = OALLOC(irg->obst, cg_callee_entry);
273 found->call_list = NEW_ARR_F(ir_node *, 1);
274 found->call_list[0] = n;
275 found->max_depth = 0;
276 pset_insert((pset *)irg->callees, found, HASH_PTR(callee));
278 depth = get_loop_depth(get_irn_loop(get_nodes_block(n)));
279 found->max_depth = (depth > found->max_depth) ? depth : found->max_depth;
284 /** compare two ir graphs in a cg_callee_entry */
285 static int cg_callee_entry_cmp(const void *elt, const void *key)
287 const cg_callee_entry *e1 = elt;
288 const cg_callee_entry *e2 = key;
289 return e1->irg != e2->irg;
292 /** compare two ir graphs for pointer identity */
293 static int graph_cmp(const void *elt, const void *key)
295 const ir_graph *e1 = elt;
296 const ir_graph *e2 = key;
301 /* Construct and destruct the callgraph. */
302 void compute_callgraph(void)
306 #ifdef INTERPROCEDURAL_VIEW
307 assert(! get_interprocedural_view()); /* Else walking will not reach the Call nodes. */
313 n_irgs = get_irp_n_irgs();
314 for (i = 0; i < n_irgs; ++i) {
315 ir_graph *irg = get_irp_irg(i);
316 assert(get_irg_callee_info_state(irg) == irg_callee_info_consistent);
317 irg->callees = (cg_callee_entry **)new_pset(cg_callee_entry_cmp, 8);
318 irg->callers = (ir_graph **)new_pset(graph_cmp, 8);
319 //construct_cf_backedges(irg);
322 /* Compute the call graph */
323 for (i = 0; i < n_irgs; ++i) {
324 ir_graph *irg = get_irp_irg(i);
325 construct_cf_backedges(irg); // We also find the maximal loop depth of a call.
326 irg_walk_graph(irg, ana_Call, NULL, NULL);
329 /* Change the sets to arrays. */
330 for (i = 0; i < n_irgs; ++i) {
332 cg_callee_entry *callee;
333 ir_graph *c, *irg = get_irp_irg(i);
334 pset *callee_set, *caller_set;
336 callee_set = (pset *)irg->callees;
337 count = pset_count(callee_set);
338 irg->callees = NEW_ARR_F(cg_callee_entry *, count);
339 irg->callee_isbe = NULL;
340 callee = pset_first(callee_set);
341 for (j = 0; j < count; ++j) {
342 irg->callees[j] = callee;
343 callee = pset_next(callee_set);
345 del_pset(callee_set);
346 assert(callee == NULL);
348 caller_set = (pset *)irg->callers;
349 count = pset_count(caller_set);
350 irg->callers = NEW_ARR_F(ir_graph *, count);
351 irg->caller_isbe = NULL;
352 c = pset_first(caller_set);
353 for (j = 0; j < count; ++j) {
355 c = pset_next(caller_set);
357 del_pset(caller_set);
360 set_irp_callgraph_state(irp_callgraph_consistent);
363 /* Destruct the callgraph. */
364 void free_callgraph(void)
366 int i, n_irgs = get_irp_n_irgs();
367 for (i = 0; i < n_irgs; ++i) {
368 ir_graph *irg = get_irp_irg(i);
369 if (irg->callees) DEL_ARR_F(irg->callees);
370 if (irg->callers) DEL_ARR_F(irg->callers);
371 if (irg->callee_isbe) free(irg->callee_isbe);
372 if (irg->caller_isbe) free(irg->caller_isbe);
375 irg->callee_isbe = NULL;
376 irg->caller_isbe = NULL;
378 set_irp_callgraph_state(irp_callgraph_none);
381 /* ----------------------------------------------------------------------------------- */
382 /* A walker for the callgraph */
383 /* ----------------------------------------------------------------------------------- */
386 static void do_walk(ir_graph *irg, callgraph_walk_func *pre, callgraph_walk_func *post, void *env)
390 if (cg_irg_visited(irg))
392 mark_cg_irg_visited(irg);
397 n_callees = get_irg_n_callees(irg);
398 for (i = 0; i < n_callees; i++) {
399 ir_graph *m = get_irg_callee(irg, i);
400 do_walk(m, pre, post, env);
407 void callgraph_walk(callgraph_walk_func *pre, callgraph_walk_func *post, void *env)
409 int i, n_irgs = get_irp_n_irgs();
412 /* roots are methods which have no callers in the current program */
413 for (i = 0; i < n_irgs; ++i) {
414 ir_graph *irg = get_irp_irg(i);
416 if (get_irg_n_callers(irg) == 0)
417 do_walk(irg, pre, post, env);
420 /* in case of unreachable call loops we haven't visited some irgs yet */
421 for (i = 0; i < n_irgs; i++) {
422 ir_graph *irg = get_irp_irg(i);
423 do_walk(irg, pre, post, env);
427 /* ----------------------------------------------------------------------------------- */
428 /* loop construction algorithm */
429 /* ----------------------------------------------------------------------------------- */
431 static ir_graph *outermost_ir_graph; /**< The outermost graph the scc is computed
433 static ir_loop *current_loop; /**< Current cfloop construction is working
435 static int loop_node_cnt = 0; /**< Counts the number of allocated cfloop nodes.
436 Each cfloop node gets a unique number.
437 What for? ev. remove. @@@ */
438 static int current_dfn = 1; /**< Counter to generate depth first numbering
441 /*-----------------*/
442 /* Node attributes */
443 /*-----------------*/
445 typedef struct scc_info {
446 int in_stack; /**< Marks whether node is on the stack. */
447 int dfn; /**< Depth first search number. */
448 int uplink; /**< dfn number of ancestor. */
453 * allocates a new scc_info on the obstack
455 static inline scc_info *new_scc_info(struct obstack *obst)
457 return OALLOCZ(obst, scc_info);
461 * Returns non-zero if a graph was already visited.
463 static inline int cg_irg_visited(ir_graph *irg)
465 return irg->self_visited >= master_cg_visited;
469 * Marks a graph as visited.
471 static inline void mark_cg_irg_visited(ir_graph *irg)
473 irg->self_visited = master_cg_visited;
477 * Set a graphs visited flag to i.
479 static inline void set_cg_irg_visited(ir_graph *irg, ir_visited_t i)
481 irg->self_visited = i;
485 * Returns the visited flag of a graph.
487 static inline ir_visited_t get_cg_irg_visited(ir_graph *irg)
489 return irg->self_visited;
492 static inline void mark_irg_in_stack(ir_graph *irg)
494 scc_info *info = get_irg_link(irg);
495 assert(info && "missing call to init_scc()");
499 static inline void mark_irg_not_in_stack(ir_graph *irg)
501 scc_info *info = get_irg_link(irg);
502 assert(info && "missing call to init_scc()");
506 static inline int irg_is_in_stack(ir_graph *irg)
508 scc_info *info = get_irg_link(irg);
509 assert(info && "missing call to init_scc()");
510 return info->in_stack;
513 static inline void set_irg_uplink(ir_graph *irg, int uplink)
515 scc_info *info = get_irg_link(irg);
516 assert(info && "missing call to init_scc()");
517 info->uplink = uplink;
520 static inline int get_irg_uplink(ir_graph *irg)
522 scc_info *info = get_irg_link(irg);
523 assert(info && "missing call to init_scc()");
527 static inline void set_irg_dfn(ir_graph *irg, int dfn)
529 scc_info *info = get_irg_link(irg);
530 assert(info && "missing call to init_scc()");
534 static inline int get_irg_dfn(ir_graph *irg)
536 scc_info *info = get_irg_link(irg);
537 assert(info && "missing call to init_scc()");
541 /**********************************************************************/
543 /**********************************************************************/
545 static ir_graph **stack = NULL;
546 static int tos = 0; /**< top of stack */
549 * Initialize the irg stack.
551 static inline void init_stack(void)
554 ARR_RESIZE(ir_graph *, stack, 1000);
556 stack = NEW_ARR_F(ir_graph *, 1000);
562 * push a graph on the irg stack
563 * @param n the graph to be pushed
565 static inline void push(ir_graph *irg)
567 if (tos == ARR_LEN(stack)) {
568 int nlen = ARR_LEN(stack) * 2;
569 ARR_RESIZE(ir_node *, stack, nlen);
572 mark_irg_in_stack(irg);
576 * return the topmost graph on the stack and pop it
578 static inline ir_graph *pop(void)
580 ir_graph *irg = stack[--tos];
581 mark_irg_not_in_stack(irg);
586 * The nodes up to irg belong to the current loop.
587 * Removes them from the stack and adds them to the current loop.
589 static inline void pop_scc_to_loop(ir_graph *irg)
596 set_irg_dfn(m, loop_node_cnt);
597 add_loop_irg(current_loop, m);
599 //m->callgraph_loop_depth = current_loop->depth;
603 /* GL ??? my last son is my grandson??? Removes cfloops with no
604 ir_nodes in them. Such loops have only another loop as son. (Why
605 can't they have two loops as sons? Does it never get that far? ) */
606 static void close_loop(ir_loop *l)
608 int last = get_loop_n_elements(l) - 1;
609 loop_element lelement = get_loop_element(l, last);
610 ir_loop *last_son = lelement.son;
612 if (get_kind(last_son) == k_ir_loop &&
613 get_loop_n_elements(last_son) == 1) {
616 lelement = get_loop_element(last_son, 0);
618 if (get_kind(gson) == k_ir_loop) {
619 loop_element new_last_son;
621 gson->outer_loop = l;
622 new_last_son.son = gson;
623 l->children[last] = new_last_son;
630 * Removes and unmarks all nodes up to n from the stack.
631 * The nodes must be visited once more to assign them to a scc.
633 static inline void pop_scc_unmark_visit(ir_graph *n)
639 set_cg_irg_visited(m, 0);
643 /**********************************************************************/
644 /* The loop data structure. **/
645 /**********************************************************************/
648 * Allocates a new loop as son of current_loop. Sets current_loop
649 * to the new loop and returns the father.
651 static ir_loop *new_loop(void)
653 ir_loop *father = current_loop;
654 ir_loop *son = alloc_loop(father, outermost_ir_graph->obst);
661 /**********************************************************************/
662 /* Constructing and destructing the loop/backedge information. **/
663 /**********************************************************************/
665 /* Initialization steps. **********************************************/
667 static void init_scc(struct obstack *obst)
676 n_irgs = get_irp_n_irgs();
677 for (i = 0; i < n_irgs; ++i) {
678 ir_graph *irg = get_irp_irg(i);
679 set_irg_link(irg, new_scc_info(obst));
680 irg->callgraph_recursion_depth = 0;
681 irg->callgraph_loop_depth = 0;
685 /** Returns non-zero if n is a loop header, i.e., it is a Block node
686 * and has predecessors within the cfloop and out of the cfloop.
688 * @param root: only needed for assertion.
690 static int is_head(ir_graph *n, ir_graph *root)
693 int some_outof_loop = 0, some_in_loop = 0;
695 arity = get_irg_n_callees(n);
696 for (i = 0; i < arity; i++) {
697 ir_graph *pred = get_irg_callee(n, i);
698 if (is_irg_callee_backedge(n, i)) continue;
699 if (!irg_is_in_stack(pred)) {
702 if (get_irg_uplink(pred) < get_irg_uplink(root)) {
703 assert(get_irg_uplink(pred) >= get_irg_uplink(root));
709 return some_outof_loop && some_in_loop;
713 * Returns non-zero if n is possible loop head of an endless loop.
714 * I.e., it is a Block, Phi or Filter node and has only predecessors
716 * @arg root: only needed for assertion.
718 static int is_endless_head(ir_graph *n, ir_graph *root)
721 int some_outof_loop = 0, some_in_loop = 0;
723 arity = get_irg_n_callees(n);
724 for (i = 0; i < arity; i++) {
725 ir_graph *pred = get_irg_callee(n, i);
727 if (is_irg_callee_backedge(n, i))
729 if (!irg_is_in_stack(pred)) {
732 if (get_irg_uplink(pred) < get_irg_uplink(root)) {
733 assert(get_irg_uplink(pred) >= get_irg_uplink(root));
738 return !some_outof_loop && some_in_loop;
741 #ifdef INTERPROCEDURAL_VIEW
743 * Check whether there is a parallel edge in the ip control flow.
746 static int is_ip_head(ir_graph *n, ir_graph *pred)
750 int iv_rem = get_interprocedural_view();
751 set_interprocedural_view(1);
753 ir_node *sblock = get_irg_start_block(n);
754 int i, arity = get_Block_n_cfgpreds(sblock);
756 //printf(" edge from "); DDMG(n);
757 //printf(" to pred "); DDMG(pred);
758 //printf(" sblock "); DDMN(sblock);
760 for (i = 0; i < arity; i++) {
761 ir_node *pred_cfop = skip_Proj(get_Block_cfgpred(sblock, i));
762 //printf(" "); DDMN(pred_cfop);
763 if (is_CallBegin(pred_cfop)) { /* could be Unknown */
764 ir_graph *ip_pred = get_irn_irg(pred_cfop);
765 //printf(" "); DDMG(ip_pred);
766 if ((ip_pred == pred) && is_backedge(sblock, i)) {
767 //printf(" found\n");
773 set_interprocedural_view(iv_rem);
776 #endif /* INTERPROCEDURAL_VIEW */
779 * Returns index of the predecessor with the smallest dfn number
780 * greater-equal than limit.
782 static int smallest_dfn_pred(ir_graph *n, int limit)
784 int i, index = -2, min = -1;
786 int arity = get_irg_n_callees(n);
787 for (i = 0; i < arity; i++) {
788 ir_graph *pred = get_irg_callee(n, i);
789 if (is_irg_callee_backedge(n, i) || !irg_is_in_stack(pred))
791 if (get_irg_dfn(pred) >= limit && (min == -1 || get_irg_dfn(pred) < min)) {
793 min = get_irg_dfn(pred);
800 /** Returns index of the predecessor with the largest dfn number. */
801 static int largest_dfn_pred(ir_graph *n)
803 int i, index = -2, max = -1;
805 int arity = get_irg_n_callees(n);
806 for (i = 0; i < arity; ++i) {
807 ir_graph *pred = get_irg_callee(n, i);
808 if (is_irg_callee_backedge (n, i) || !irg_is_in_stack(pred)) continue;
809 if (get_irg_dfn(pred) > max) {
811 max = get_irg_dfn(pred);
818 #ifndef INTERPROCEDURAL_VIEW
819 static ir_graph *find_tail(ir_graph *n)
822 int i, res_index = -2;
825 if (!icfg && rm_cyclic_phis && remove_cyclic_phis (n)) return NULL;
827 m = stack[tos-1]; /* tos = top of stack */
828 if (is_head (m, n)) {
829 res_index = smallest_dfn_pred(m, 0);
830 if ((res_index == -2) && /* no smallest dfn pred found. */
834 if (m == n) return NULL; // Is this to catch Phi - self loops?
835 for (i = tos-2; i >= 0; --i) {
839 res_index = smallest_dfn_pred(m, get_irg_dfn(m) + 1);
840 if (res_index == -2) /* no smallest dfn pred found. */
841 res_index = largest_dfn_pred(m);
843 if ((m == n) && (res_index == -2)) {
849 /* We should not walk past our selves on the stack: The upcoming nodes
850 are not in this loop. We assume a loop not reachable from Start. */
859 /* A dead loop not reachable from Start. */
860 for (i = tos-2; i >= 0; --i) {
862 if (is_endless_head(m, n)) {
863 res_index = smallest_dfn_pred(m, get_irg_dfn(m) + 1);
864 if (res_index == -2) /* no smallest dfn pred found. */
865 res_index = largest_dfn_pred(m);
868 if (m == n) { break; } /* It's not an unreachable loop, either. */
870 //assert(0 && "no head found on stack");
874 assert (res_index > -2);
876 set_irg_callee_backedge(m, res_index);
877 return get_irg_callee(m, res_index);
880 static ir_graph *find_tail(ir_graph *n)
883 int i, res_index = -2;
886 ir_graph *in_and_out = NULL;
887 ir_graph *only_in = NULL;
888 ir_graph *ip_in_and_out = NULL;
889 ir_graph *ip_only_in = NULL;
891 //printf("find tail for "); DDMG(n);
893 for (i = tos-1; i >= 0; --i) {
894 ir_graph *pred = (i < tos -1) ? stack[i+1] : n;
898 //printf(" found 1a! "); DDM;
900 if (is_ip_head(pred, m)) {
901 //printf(" found 1b! "); DDM;
904 } else if (!ip_only_in && is_endless_head(m, n)) {
906 //printf(" found 2a! "); DDM;
907 if (is_ip_head(pred, m)) {
908 //printf(" found 2b! "); DDM;
911 } else if (is_ip_head(pred, m)) {
912 //printf(" found 3! "); DDM; This happens for self recursions in the second
913 //assert(0); scc iteration (the one to flip the loop.)
916 if (ip_in_and_out) break; /* That's what we really want. */
918 if (m == n) break; /* Don't walk past n on the stack! */
922 if (!in_and_out && !only_in)
923 /* There is no loop */
927 /* Is there a head in the callgraph without a head in the
929 assert(in_and_out || only_in);
931 m = (ip_in_and_out) ? ip_in_and_out : ip_only_in;
934 m = (in_and_out) ? in_and_out : only_in;
936 //printf("*** head is "); DDMG(m);
938 res_index = smallest_dfn_pred(m, get_irg_dfn(m) + 1);
939 if (res_index == -2) /* no smallest dfn pred found. */
940 res_index = largest_dfn_pred(m);
942 set_irg_callee_backedge(m, res_index);
943 res = get_irg_callee(m, res_index);
944 //printf("*** tail is "); DDMG(res);
947 #endif /* INTERPROCEDURAL_VIEW */
949 /*-----------------------------------------------------------*
950 * The core algorithm. *
951 *-----------------------------------------------------------*/
954 static void cgscc(ir_graph *n)
958 if (cg_irg_visited(n)) return;
959 mark_cg_irg_visited(n);
961 /* Initialize the node */
962 set_irg_dfn(n, current_dfn); /* Depth first number for this node */
963 set_irg_uplink(n, current_dfn); /* ... is default uplink. */
967 arity = get_irg_n_callees(n);
968 for (i = 0; i < arity; i++) {
970 if (is_irg_callee_backedge(n, i)) continue;
971 m = get_irg_callee(n, i);
973 /** This marks the backedge, but does it guarantee a correct loop tree? */
974 //if (m == n) { set_irg_callee_backedge(n, i); continue; }
977 if (irg_is_in_stack(m)) {
978 /* Uplink of m is smaller if n->m is a backedge.
979 Propagate the uplink to mark the cfloop. */
980 if (get_irg_uplink(m) < get_irg_uplink(n))
981 set_irg_uplink(n, get_irg_uplink(m));
985 if (get_irg_dfn(n) == get_irg_uplink(n)) {
986 /* This condition holds for
987 1) the node with the incoming backedge.
988 That is: We found a cfloop!
989 2) Straight line code, because no uplink has been propagated, so the
990 uplink still is the same as the dfn.
992 But n might not be a proper cfloop head for the analysis. Proper cfloop
993 heads are Block and Phi nodes. find_tail searches the stack for
994 Block's and Phi's and takes those nodes as cfloop heads for the current
995 cfloop instead and marks the incoming edge as backedge. */
997 ir_graph *tail = find_tail(n);
999 /* We have a cfloop, that is no straight line code,
1000 because we found a cfloop head!
1001 Next actions: Open a new cfloop on the cfloop tree and
1002 try to find inner cfloops */
1005 ir_loop *l = new_loop();
1007 /* Remove the cfloop from the stack ... */
1008 pop_scc_unmark_visit(n);
1010 /* The current backedge has been marked, that is temporarily eliminated,
1011 by find tail. Start the scc algorithm
1012 anew on the subgraph thats left (the current cfloop without the backedge)
1013 in order to find more inner cfloops. */
1017 assert(cg_irg_visited(n));
1027 * reset the backedge information for all callers in all irgs
1029 static void reset_isbe(void)
1031 int i, n_irgs = get_irp_n_irgs();
1033 for (i = 0; i < n_irgs; ++i) {
1034 ir_graph *irg = get_irp_irg(i);
1036 if (irg->caller_isbe)
1037 xfree(irg->caller_isbe);
1038 irg->caller_isbe = NULL;
1040 if (irg->callee_isbe)
1041 xfree(irg->callee_isbe);
1042 irg->callee_isbe = NULL;
1046 /* ----------------------------------------------------------------------------------- */
1047 /* Another algorithm to compute recursion nesting depth */
1048 /* Walk the callgraph. For each crossed edge increase the loop depth by the edge */
1049 /* weight. Assign graphs the maximal depth. */
1050 /* ----------------------------------------------------------------------------------- */
1052 static void compute_loop_depth(ir_graph *irg, void *env)
1054 int current_nesting = *(int *) env;
1055 int old_nesting = irg->callgraph_loop_depth;
1056 ir_visited_t old_visited = get_cg_irg_visited(irg);
1061 if (cg_irg_visited(irg)) return;
1063 mark_cg_irg_visited(irg);
1065 //printf(" old: %d new %d master %d", old_visited, get_cg_irg_visited(irg), master_cg_visited); DDMG(irg);
1068 if (old_nesting < current_nesting)
1069 irg->callgraph_loop_depth = current_nesting;
1071 if (current_nesting > irp->max_callgraph_loop_depth)
1072 irp->max_callgraph_loop_depth = current_nesting;
1074 if ((old_visited +1 < get_cg_irg_visited(irg)) || /* not yet visited */
1075 (old_nesting < current_nesting)) { /* propagate larger nesting */
1076 /* Don't walk the graph, but a tree that is an unfolded graph. */
1077 n_callees = get_irg_n_callees(irg);
1078 for (i = 0; i < n_callees; i++) {
1079 ir_graph *m = get_irg_callee(irg, i);
1080 *(int *)env += get_irg_callee_loop_depth(irg, i);
1081 compute_loop_depth(m, env);
1082 *(int *)env -= get_irg_callee_loop_depth(irg, i);
1086 set_cg_irg_visited(irg, master_cg_visited-1);
1089 /* ------------------------------------------------------------------------------------ */
1090 /* Another algorithm to compute recursion nesting depth */
1091 /* Walk the callgraph. For each crossed loop increase the nesting depth by one. */
1092 /* Assign graphs the maximal nesting depth. Don't increase if passing loops more than */
1094 /* ------------------------------------------------------------------------------------ */
1097 /* For callees, we want to remember the Call nodes, too. */
1098 typedef struct ana_entry2 {
1099 ir_loop **loop_stack; /**< a stack of ir_loop entries */
1100 int tos; /**< the top of stack entry */
1101 int recursion_nesting;
1105 * push a loop entry on the stack
1107 static void push2(ana_entry2 *e, ir_loop *g)
1109 if (ARR_LEN(e->loop_stack) == e->tos) {
1110 ARR_APP1(ir_loop *, e->loop_stack, g);
1112 e->loop_stack[e->tos] = g;
1118 * returns the top of stack and pop it
1120 static ir_loop *pop2(ana_entry2 *e)
1122 return e->loop_stack[--e->tos];
1126 * check if a loop g in on the stack. Did not check the TOS.
1128 static int in_stack(ana_entry2 *e, ir_loop *g)
1131 for (i = e->tos-1; i >= 0; --i) {
1132 if (e->loop_stack[i] == g) return 1;
1137 static void compute_rec_depth(ir_graph *irg, void *env)
1139 ana_entry2 *e = (ana_entry2 *)env;
1140 ir_loop *l = irg->l;
1141 int depth, old_depth = irg->callgraph_recursion_depth;
1145 if (cg_irg_visited(irg))
1147 mark_cg_irg_visited(irg);
1149 /* -- compute and set the new nesting value -- */
1150 if ((l != irp->outermost_cg_loop) && !in_stack(e, l)) {
1152 e->recursion_nesting++;
1155 depth = e->recursion_nesting;
1157 if (old_depth < depth)
1158 irg->callgraph_recursion_depth = depth;
1160 if (depth > irp->max_callgraph_recursion_depth)
1161 irp->max_callgraph_recursion_depth = depth;
1163 /* -- spread the nesting value -- */
1164 if (depth == 0 || old_depth < depth) {
1165 /* Don't walk the graph, but a tree that is an unfolded graph.
1166 Therefore we unset the visited flag at the end. */
1167 n_callees = get_irg_n_callees(irg);
1168 for (i = 0; i < n_callees; ++i) {
1169 ir_graph *m = get_irg_callee(irg, i);
1170 compute_rec_depth(m, env);
1174 /* -- clean up -- */
1177 e->recursion_nesting--;
1179 set_cg_irg_visited(irg, master_cg_visited-1);
1183 /* ----------------------------------------------------------------------------------- */
1184 /* Another algorithm to compute the execution frequency of methods ignoring recursions. */
1185 /* Walk the callgraph. Ignore backedges. Use sum of execution frequencies of Call */
1186 /* nodes to evaluate a callgraph edge. */
1187 /* ----------------------------------------------------------------------------------- */
1189 /* Returns the method execution frequency of a graph. */
1190 double get_irg_method_execution_frequency(const ir_graph *irg)
1192 return irg->method_execution_frequency;
1196 * Increase the method execution frequency to freq if its current value is
1197 * smaller then this.
1199 static void set_irg_method_execution_frequency(ir_graph *irg, double freq)
1201 irg->method_execution_frequency = freq;
1203 if (irp->max_method_execution_frequency < freq)
1204 irp->max_method_execution_frequency = freq;
1207 static void compute_method_execution_frequency(ir_graph *irg, void *env)
1215 if (cg_irg_visited(irg))
1218 /* We need the values of all predecessors (except backedges).
1219 So they must be marked. Else we will reach the node through
1220 one of the unmarked ones. */
1221 n_callers = get_irg_n_callers(irg);
1222 for (i = 0; i < n_callers; ++i) {
1223 ir_graph *m = get_irg_caller(irg, i);
1224 if (is_irg_caller_backedge(irg, i))
1226 if (!cg_irg_visited(m)) {
1230 mark_cg_irg_visited(irg);
1232 /* Compute the new frequency. */
1235 for (i = 0; i < n_callers; i++) {
1236 if (! is_irg_caller_backedge(irg, i)) {
1237 double edge_freq = get_irg_caller_method_execution_frequency(irg, i);
1238 assert(edge_freq >= 0);
1245 /* A starting point: method only called from outside,
1246 or only backedges as predecessors. */
1250 set_irg_method_execution_frequency(irg, freq);
1253 n_callees = get_irg_n_callees(irg);
1254 for (i = 0; i < n_callees; ++i) {
1255 compute_method_execution_frequency(get_irg_callee(irg, i), NULL);
1260 /* ----------------------------------------------------------------------------------- */
1261 /* The recursion stuff driver. */
1262 /* ----------------------------------------------------------------------------------- */
1264 /* Compute the backedges that represent recursions. */
1265 void find_callgraph_recursions(void)
1268 struct obstack temp;
1272 /* -- compute the looptree. -- */
1274 /* The outermost graph. We start here. Then we start at all
1275 functions in irg list that are never called, then at the remaining
1276 unvisited ones. The third step is needed for functions that are not
1277 reachable from the outermost graph, but call themselves in a cycle. */
1278 assert(get_irp_main_irg());
1279 outermost_ir_graph = get_irp_main_irg();
1280 obstack_init(&temp);
1283 current_loop = NULL;
1284 new_loop(); /* sets current_loop */
1286 ++master_cg_visited;
1287 cgscc(outermost_ir_graph);
1288 n_irgs = get_irp_n_irgs();
1289 for (i = 0; i < n_irgs; ++i) {
1290 ir_graph *irg = get_irp_irg(i);
1291 if (!cg_irg_visited(irg) && get_irg_n_callers(irg) == 0)
1294 for (i = 0; i < n_irgs; ++i) {
1295 ir_graph *irg = get_irp_irg(i);
1296 if (!cg_irg_visited(irg))
1299 obstack_free(&temp, NULL);
1301 irp->outermost_cg_loop = current_loop;
1302 mature_loops(current_loop, outermost_ir_graph->obst);
1304 /* -- Reverse the backedge information. -- */
1305 for (i = 0; i < n_irgs; ++i) {
1306 ir_graph *irg = get_irp_irg(i);
1307 int j, n_callees = get_irg_n_callees(irg);
1308 for (j = 0; j < n_callees; ++j) {
1309 if (is_irg_callee_backedge(irg, j))
1310 set_irg_caller_backedge(get_irg_callee(irg, j), irg);
1314 irp->callgraph_state = irp_callgraph_and_calltree_consistent;
1317 /* Compute interprocedural performance estimates. */
1318 void compute_performance_estimates(void)
1320 int i, n_irgs = get_irp_n_irgs();
1321 int current_nesting;
1324 assert(get_irp_exec_freq_state() != exec_freq_none && "execution frequency not calculated");
1326 /* -- compute the loop depth -- */
1327 current_nesting = 0;
1328 irp->max_callgraph_loop_depth = 0;
1329 master_cg_visited += 2;
1330 //printf(" ** starting at "); DDMG(get_irp_main_irg());
1331 compute_loop_depth(get_irp_main_irg(), ¤t_nesting);
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 get_irg_n_callers(irg) == 0) {
1336 compute_loop_depth(irg, ¤t_nesting);
1337 //printf(" ** starting at "); DDMG(irg);
1340 for (i = 0; i < n_irgs; i++) {
1341 ir_graph *irg = get_irp_irg(i);
1342 if (get_cg_irg_visited(irg) < master_cg_visited-1) {
1343 compute_loop_depth(irg, ¤t_nesting);
1344 //printf(" ** starting at "); DDMG(irg);
1349 /* -- compute the recursion depth -- */
1350 e.loop_stack = NEW_ARR_F(ir_loop *, 0);
1352 e.recursion_nesting = 0;
1354 irp->max_callgraph_recursion_depth = 0;
1356 master_cg_visited += 2;
1357 compute_rec_depth(get_irp_main_irg(), &e);
1358 //printf(" ++ starting at "); DDMG(get_irp_main_irg());
1359 for (i = 0; i < n_irgs; i++) {
1360 ir_graph *irg = get_irp_irg(i);
1361 if ((get_cg_irg_visited(irg) < master_cg_visited-1) &&
1362 get_irg_n_callers(irg) == 0) {
1363 compute_rec_depth(irg, &e);
1364 //printf(" ++ starting at "); DDMG(irg);
1367 for (i = 0; i < n_irgs; i++) {
1368 ir_graph *irg = get_irp_irg(i);
1369 if (get_cg_irg_visited(irg) < master_cg_visited-1) {
1370 compute_rec_depth(irg, &e);
1371 //printf(" ++ starting at "); DDMG(irg);
1375 DEL_ARR_F(e.loop_stack);
1377 /* -- compute the execution frequency -- */
1378 irp->max_method_execution_frequency = 0;
1379 master_cg_visited += 2;
1380 assert(get_irg_n_callers(get_irp_main_irg()) == 0);
1381 compute_method_execution_frequency(get_irp_main_irg(), NULL);
1382 for (i = 0; i < n_irgs; i++) {
1383 ir_graph *irg = get_irp_irg(i);
1384 if ((get_cg_irg_visited(irg) < master_cg_visited-1) &&
1385 get_irg_n_callers(irg) == 0) {
1386 compute_method_execution_frequency(irg, NULL);
1389 for (i = 0; i < n_irgs; i++) {
1390 ir_graph *irg = get_irp_irg(i);
1391 if (get_cg_irg_visited(irg) < master_cg_visited-1) {
1392 compute_method_execution_frequency(irg, NULL);
1397 /* Returns the maximal loop depth of all paths from an external visible method to
1399 int get_irg_loop_depth(const ir_graph *irg)
1401 assert(irp->callgraph_state == irp_callgraph_consistent ||
1402 irp->callgraph_state == irp_callgraph_and_calltree_consistent);
1403 return irg->callgraph_loop_depth;
1406 /* Returns the maximal recursion depth of all paths from an external visible method to
1408 int get_irg_recursion_depth(const ir_graph *irg)
1410 assert(irp->callgraph_state == irp_callgraph_and_calltree_consistent);
1411 return irg->callgraph_recursion_depth;
1414 /* Computes the interprocedural loop nesting information. */
1415 void analyse_loop_nesting_depth(void)
1417 ir_entity **free_methods = NULL;
1420 /* establish preconditions. */
1421 if (get_irp_callee_info_state() != irg_callee_info_consistent) {
1422 cgana(&arr_len, &free_methods);
1425 if (irp_callgraph_consistent != get_irp_callgraph_state()) {
1426 compute_callgraph();
1429 find_callgraph_recursions();
1431 compute_performance_estimates();
1433 set_irp_loop_nesting_depth_state(loop_nesting_depth_consistent);
1436 loop_nesting_depth_state get_irp_loop_nesting_depth_state(void)
1438 return irp->lnd_state;
1440 void set_irp_loop_nesting_depth_state(loop_nesting_depth_state s)
1444 void set_irp_loop_nesting_depth_state_inconsistent(void)
1446 if (irp->lnd_state == loop_nesting_depth_consistent)
1447 irp->lnd_state = loop_nesting_depth_inconsistent;