2 * Copyright (C) 1995-2008 University of Karlsruhe. All right reserved.
4 * This file is part of libFirm.
6 * This file may be distributed and/or modified under the terms of the
7 * GNU General Public License version 2 as published by the Free Software
8 * Foundation and appearing in the file LICENSE.GPL included in the
9 * packaging of this file.
11 * Licensees holding valid libFirm Professional Edition licenses may use
12 * this file in accordance with the libFirm Commercial License.
13 * Agreement provided with the Software.
15 * This file is provided AS IS with NO WARRANTY OF ANY KIND, INCLUDING THE
16 * WARRANTY OF DESIGN, MERCHANTABILITY AND FITNESS FOR A PARTICULAR
22 * @brief Representation and computation of the callgraph.
23 * @author Goetz Lindenmaier
38 #include "callgraph.h"
42 #include "irgraph_t.h"
46 #include "execution_frequency.h"
51 #include "raw_bitset.h"
55 static ir_visited_t master_cg_visited = 0;
56 static INLINE int cg_irg_visited (ir_graph *n);
57 static INLINE void mark_cg_irg_visited(ir_graph *n);
58 static INLINE void set_cg_irg_visited (ir_graph *n, ir_visited_t i);
60 /** Returns the callgraph state of the program representation. */
61 irp_callgraph_state get_irp_callgraph_state(void) {
62 return irp->callgraph_state;
65 /* Sets the callgraph state of the program representation. */
66 void set_irp_callgraph_state(irp_callgraph_state s) {
67 irp->callgraph_state = s;
70 /* Returns the number of procedures that call the given irg. */
71 int get_irg_n_callers(ir_graph *irg) {
72 if (irg->callers) return ARR_LEN(irg->callers);
76 /* Returns the caller at position pos. */
77 ir_graph *get_irg_caller(ir_graph *irg, int pos) {
78 assert(pos >= 0 && pos < get_irg_n_callers(irg));
79 if (irg->callers) return irg->callers[pos];
83 /* Returns non-zero if the caller at position pos is "a backedge", i.e. a recursion. */
84 int is_irg_caller_backedge(ir_graph *irg, int pos) {
85 assert(pos >= 0 && pos < get_irg_n_callers(irg));
86 return irg->caller_isbe != NULL ? rbitset_is_set(irg->caller_isbe, pos) : 0;
89 /** Search the caller in the list of all callers and set it's backedge property. */
90 static void set_irg_caller_backedge(ir_graph *irg, ir_graph *caller) {
91 int i, n_callers = get_irg_n_callers(irg);
93 /* allocate a new array on demand */
94 if (irg->caller_isbe == NULL)
95 irg->caller_isbe = rbitset_malloc(n_callers);
96 for (i = 0; i < n_callers; ++i) {
97 if (get_irg_caller(irg, i) == caller) {
98 rbitset_set(irg->caller_isbe, i);
104 /* Returns non-zero if the irg has a backedge caller. */
105 int has_irg_caller_backedge(ir_graph *irg) {
106 int i, n_callers = get_irg_n_callers(irg);
108 if (irg->caller_isbe != NULL) {
109 for (i = 0; i < n_callers; ++i)
110 if (rbitset_is_set(irg->caller_isbe, i))
117 * Find the reversion position of a caller.
118 * Given the position pos_caller of an caller of irg, return
119 * irg's callee position on that caller.
121 static int reverse_pos(ir_graph *callee, int pos_caller) {
122 ir_graph *caller = get_irg_caller(callee, pos_caller);
123 /* search the other relation for the corresponding edge. */
125 int i, n_callees = get_irg_n_callees(caller);
126 for (i = 0; i < n_callees; ++i) {
127 if (get_irg_callee(caller, i) == callee) {
133 assert(pos_callee >= 0);
138 /* Returns the maximal loop depth of call nodes that call along this edge. */
139 int get_irg_caller_loop_depth(ir_graph *irg, int pos) {
140 ir_graph *caller = get_irg_caller(irg, pos);
141 int pos_callee = reverse_pos(irg, pos);
143 return get_irg_callee_loop_depth(caller, pos_callee);
147 /* Returns the number of procedures that are called by the given irg. */
148 int get_irg_n_callees(ir_graph *irg) {
149 if (irg->callees) return ARR_LEN(irg->callees);
153 /* Returns the callee at position pos. */
154 ir_graph *get_irg_callee(ir_graph *irg, int pos) {
155 assert(pos >= 0 && pos < get_irg_n_callees(irg));
156 if (irg->callees) return irg->callees[pos]->irg;
160 /* Returns non-zero if the callee at position pos is "a backedge", i.e. a recursion. */
161 int is_irg_callee_backedge(ir_graph *irg, int pos) {
162 assert(pos >= 0 && pos < get_irg_n_callees(irg));
163 return irg->callee_isbe != NULL ? rbitset_is_set(irg->callee_isbe, pos) : 0;
166 /* Returns non-zero if the irg has a backedge callee. */
167 int has_irg_callee_backedge(ir_graph *irg) {
168 int i, n_callees = get_irg_n_callees(irg);
170 if (irg->callee_isbe != NULL) {
171 for (i = 0; i < n_callees; ++i)
172 if (rbitset_is_set(irg->callee_isbe, i))
179 * Mark the callee at position pos as a backedge.
181 static void set_irg_callee_backedge(ir_graph *irg, int pos) {
182 int n = get_irg_n_callees(irg);
184 /* allocate a new array on demand */
185 if (irg->callee_isbe == NULL)
186 irg->callee_isbe = rbitset_malloc(n);
187 assert(pos >= 0 && pos < n);
188 rbitset_set(irg->callee_isbe, pos);
191 /* Returns the maximal loop depth of call nodes that call along this edge. */
192 int get_irg_callee_loop_depth(ir_graph *irg, int pos) {
193 assert(pos >= 0 && pos < get_irg_n_callees(irg));
194 if (irg->callees) return irg->callees[pos]->max_depth;
199 double get_irg_callee_execution_frequency(ir_graph *irg, int pos) {
200 ir_node **arr = irg->callees[pos]->call_list;
201 int i, n_Calls = ARR_LEN(arr);
204 for (i = 0; i < n_Calls; ++i) {
205 freq += get_irn_exec_freq(arr[i]);
210 double get_irg_callee_method_execution_frequency(ir_graph *irg, int pos) {
211 double call_freq = get_irg_callee_execution_frequency(irg, pos);
212 double meth_freq = get_irg_method_execution_frequency(irg);
213 return call_freq * meth_freq;
217 double get_irg_caller_method_execution_frequency(ir_graph *irg, int pos) {
218 ir_graph *caller = get_irg_caller(irg, pos);
219 int pos_callee = reverse_pos(irg, pos);
221 return get_irg_callee_method_execution_frequency(caller, pos_callee);
226 /* --------------------- Compute the callgraph ------------------------ */
229 * Walker called by compute_callgraph(), analyses all Call nodes.
231 static void ana_Call(ir_node *n, void *env) {
236 if (! is_Call(n)) return;
238 irg = get_irn_irg(n);
239 n_callees = get_Call_n_callees(n);
240 for (i = 0; i < n_callees; ++i) {
241 ir_entity *callee_e = get_Call_callee(n, i);
242 ir_graph *callee = get_entity_irg(callee_e);
246 cg_callee_entry *found;
251 pset_insert((pset *)callee->callers, irg, HASH_PTR(irg));
252 found = pset_find((pset *)irg->callees, &buf, HASH_PTR(callee));
253 if (found) { /* add Call node to list, compute new nesting. */
254 ir_node **arr = found->call_list;
255 ARR_APP1(ir_node *, arr, n);
256 found->call_list = arr;
257 } else { /* New node, add Call node and init nesting. */
258 found = (cg_callee_entry *)obstack_alloc(irg->obst, sizeof(*found));
260 found->call_list = NEW_ARR_F(ir_node *, 1);
261 found->call_list[0] = n;
262 found->max_depth = 0;
263 pset_insert((pset *)irg->callees, found, HASH_PTR(callee));
265 depth = get_loop_depth(get_irn_loop(get_nodes_block(n)));
266 found->max_depth = (depth > found->max_depth) ? depth : found->max_depth;
271 /** compare two ir graphs in a cg_callee_entry */
272 static int cg_callee_entry_cmp(const void *elt, const void *key) {
273 const cg_callee_entry *e1 = elt;
274 const cg_callee_entry *e2 = key;
275 return e1->irg != e2->irg;
278 /** compare two ir graphs for pointer identity */
279 static int graph_cmp(const void *elt, const void *key) {
280 const ir_graph *e1 = elt;
281 const ir_graph *e2 = key;
286 /* Construct and destruct the callgraph. */
287 void compute_callgraph(void) {
290 #ifdef INTERPROCEDURAL_VIEW
291 assert(! get_interprocedural_view()); /* Else walking will not reach the Call nodes. */
297 n_irgs = get_irp_n_irgs();
298 for (i = 0; i < n_irgs; ++i) {
299 ir_graph *irg = get_irp_irg(i);
300 assert(get_irg_callee_info_state(irg) == irg_callee_info_consistent);
301 irg->callees = (cg_callee_entry **)new_pset(cg_callee_entry_cmp, 8);
302 irg->callers = (ir_graph **)new_pset(graph_cmp, 8);
303 //construct_cf_backedges(irg);
306 /* Compute the call graph */
307 for (i = 0; i < n_irgs; ++i) {
308 ir_graph *irg = get_irp_irg(i);
309 construct_cf_backedges(irg); // We also find the maximal loop depth of a call.
310 irg_walk_graph(irg, ana_Call, NULL, NULL);
313 /* Change the sets to arrays. */
314 for (i = 0; i < n_irgs; ++i) {
316 cg_callee_entry *callee;
317 ir_graph *c, *irg = get_irp_irg(i);
318 pset *callee_set, *caller_set;
320 callee_set = (pset *)irg->callees;
321 count = pset_count(callee_set);
322 irg->callees = NEW_ARR_F(cg_callee_entry *, count);
323 irg->callee_isbe = NULL;
324 callee = pset_first(callee_set);
325 for (j = 0; j < count; ++j) {
326 irg->callees[j] = callee;
327 callee = pset_next(callee_set);
329 del_pset(callee_set);
330 assert(callee == NULL);
332 caller_set = (pset *)irg->callers;
333 count = pset_count(caller_set);
334 irg->callers = NEW_ARR_F(ir_graph *, count);
335 irg->caller_isbe = NULL;
336 c = pset_first(caller_set);
337 for (j = 0; j < count; ++j) {
339 c = pset_next(caller_set);
341 del_pset(caller_set);
344 set_irp_callgraph_state(irp_callgraph_consistent);
347 /* Destruct the callgraph. */
348 void free_callgraph(void) {
349 int i, n_irgs = get_irp_n_irgs();
350 for (i = 0; i < n_irgs; ++i) {
351 ir_graph *irg = get_irp_irg(i);
352 if (irg->callees) DEL_ARR_F(irg->callees);
353 if (irg->callers) DEL_ARR_F(irg->callers);
354 if (irg->callee_isbe) free(irg->callee_isbe);
355 if (irg->caller_isbe) free(irg->caller_isbe);
358 irg->callee_isbe = NULL;
359 irg->caller_isbe = NULL;
361 set_irp_callgraph_state(irp_callgraph_none);
364 /* ----------------------------------------------------------------------------------- */
365 /* A walker for the callgraph */
366 /* ----------------------------------------------------------------------------------- */
369 static void do_walk(ir_graph *irg, callgraph_walk_func *pre, callgraph_walk_func *post, void *env) {
372 if (cg_irg_visited(irg))
374 mark_cg_irg_visited(irg);
379 n_callees = get_irg_n_callees(irg);
380 for (i = 0; i < n_callees; i++) {
381 ir_graph *m = get_irg_callee(irg, i);
382 do_walk(m, pre, post, env);
389 void callgraph_walk(callgraph_walk_func *pre, callgraph_walk_func *post, void *env) {
390 int i, n_irgs = get_irp_n_irgs();
393 /* roots are methods which have no callers in the current program */
394 for (i = 0; i < n_irgs; ++i) {
395 ir_graph *irg = get_irp_irg(i);
397 if (get_irg_n_callers(irg) == 0)
398 do_walk(irg, pre, post, env);
401 /* in case of unreachable call loops we haven't visited some irgs yet */
402 for (i = 0; i < n_irgs; i++) {
403 ir_graph *irg = get_irp_irg(i);
404 do_walk(irg, pre, post, env);
408 /* ----------------------------------------------------------------------------------- */
409 /* loop construction algorithm */
410 /* ----------------------------------------------------------------------------------- */
412 static ir_graph *outermost_ir_graph; /**< The outermost graph the scc is computed
414 static ir_loop *current_loop; /**< Current cfloop construction is working
416 static int loop_node_cnt = 0; /**< Counts the number of allocated cfloop nodes.
417 Each cfloop node gets a unique number.
418 What for? ev. remove. @@@ */
419 static int current_dfn = 1; /**< Counter to generate depth first numbering
422 /*-----------------*/
423 /* Node attributes */
424 /*-----------------*/
426 typedef struct scc_info {
427 int in_stack; /**< Marks whether node is on the stack. */
428 int dfn; /**< Depth first search number. */
429 int uplink; /**< dfn number of ancestor. */
434 * allocates a new scc_info on the obstack
436 static INLINE scc_info *new_scc_info(struct obstack *obst) {
437 scc_info *info = obstack_alloc(obst, sizeof(*info));
438 memset(info, 0, sizeof(*info));
443 * Returns non-zero if a graph was already visited.
445 static INLINE int cg_irg_visited(ir_graph *irg) {
446 return irg->self_visited >= master_cg_visited;
450 * Marks a graph as visited.
452 static INLINE void mark_cg_irg_visited(ir_graph *irg) {
453 irg->self_visited = master_cg_visited;
457 * Set a graphs visited flag to i.
459 static INLINE void set_cg_irg_visited(ir_graph *irg, ir_visited_t i) {
460 irg->self_visited = i;
464 * Returns the visited flag of a graph.
466 static INLINE ir_visited_t get_cg_irg_visited(ir_graph *irg) {
467 return irg->self_visited;
470 static INLINE void mark_irg_in_stack(ir_graph *irg) {
471 scc_info *info = get_irg_link(irg);
472 assert(info && "missing call to init_scc()");
476 static INLINE void mark_irg_not_in_stack(ir_graph *irg) {
477 scc_info *info = get_irg_link(irg);
478 assert(info && "missing call to init_scc()");
482 static INLINE int irg_is_in_stack(ir_graph *irg) {
483 scc_info *info = get_irg_link(irg);
484 assert(info && "missing call to init_scc()");
485 return info->in_stack;
488 static INLINE void set_irg_uplink(ir_graph *irg, int uplink) {
489 scc_info *info = get_irg_link(irg);
490 assert(info && "missing call to init_scc()");
491 info->uplink = uplink;
494 static INLINE int get_irg_uplink(ir_graph *irg) {
495 scc_info *info = get_irg_link(irg);
496 assert(info && "missing call to init_scc()");
500 static INLINE void set_irg_dfn(ir_graph *irg, int dfn) {
501 scc_info *info = get_irg_link(irg);
502 assert(info && "missing call to init_scc()");
506 static INLINE int get_irg_dfn(ir_graph *irg) {
507 scc_info *info = get_irg_link(irg);
508 assert(info && "missing call to init_scc()");
512 /**********************************************************************/
514 /**********************************************************************/
516 static ir_graph **stack = NULL;
517 static int tos = 0; /**< top of stack */
520 * Initialize the irg stack.
522 static INLINE void init_stack(void) {
524 ARR_RESIZE(ir_graph *, stack, 1000);
526 stack = NEW_ARR_F(ir_graph *, 1000);
532 * push a graph on the irg stack
533 * @param n the graph to be pushed
535 static INLINE void push(ir_graph *irg) {
536 if (tos == ARR_LEN(stack)) {
537 int nlen = ARR_LEN(stack) * 2;
538 ARR_RESIZE(ir_node *, stack, nlen);
541 mark_irg_in_stack(irg);
545 * return the topmost graph on the stack and pop it
547 static INLINE ir_graph *pop(void) {
548 ir_graph *irg = stack[--tos];
549 mark_irg_not_in_stack(irg);
554 * The nodes up to irg belong to the current loop.
555 * Removes them from the stack and adds them to the current loop.
557 static INLINE void pop_scc_to_loop(ir_graph *irg) {
563 set_irg_dfn(m, loop_node_cnt);
564 add_loop_irg(current_loop, m);
566 //m->callgraph_loop_depth = current_loop->depth;
570 /* GL ??? my last son is my grandson??? Removes cfloops with no
571 ir_nodes in them. Such loops have only another loop as son. (Why
572 can't they have two loops as sons? Does it never get that far? ) */
573 static void close_loop(ir_loop *l) {
574 int last = get_loop_n_elements(l) - 1;
575 loop_element lelement = get_loop_element(l, last);
576 ir_loop *last_son = lelement.son;
578 if (get_kind(last_son) == k_ir_loop &&
579 get_loop_n_elements(last_son) == 1) {
582 lelement = get_loop_element(last_son, 0);
584 if (get_kind(gson) == k_ir_loop) {
585 loop_element new_last_son;
587 gson->outer_loop = l;
588 new_last_son.son = gson;
589 l->children[last] = new_last_son;
596 * Removes and unmarks all nodes up to n from the stack.
597 * The nodes must be visited once more to assign them to a scc.
599 static INLINE void pop_scc_unmark_visit(ir_graph *n) {
604 set_cg_irg_visited(m, 0);
608 /**********************************************************************/
609 /* The loop data structure. **/
610 /**********************************************************************/
613 * Allocates a new loop as son of current_loop. Sets current_loop
614 * to the new loop and returns the father.
616 static ir_loop *new_loop(void) {
617 ir_loop *father = current_loop;
618 ir_loop *son = alloc_loop(father, outermost_ir_graph->obst);
625 /**********************************************************************/
626 /* Constructing and destructing the loop/backedge information. **/
627 /**********************************************************************/
629 /* Initialization steps. **********************************************/
631 static void init_scc(struct obstack *obst) {
639 n_irgs = get_irp_n_irgs();
640 for (i = 0; i < n_irgs; ++i) {
641 ir_graph *irg = get_irp_irg(i);
642 set_irg_link(irg, new_scc_info(obst));
643 irg->callgraph_recursion_depth = 0;
644 irg->callgraph_loop_depth = 0;
648 /** Returns non-zero if n is a loop header, i.e., it is a Block node
649 * and has predecessors within the cfloop and out of the cfloop.
651 * @param root: only needed for assertion.
653 static int is_head(ir_graph *n, ir_graph *root) {
655 int some_outof_loop = 0, some_in_loop = 0;
657 arity = get_irg_n_callees(n);
658 for (i = 0; i < arity; i++) {
659 ir_graph *pred = get_irg_callee(n, i);
660 if (is_irg_callee_backedge(n, i)) continue;
661 if (!irg_is_in_stack(pred)) {
664 if (get_irg_uplink(pred) < get_irg_uplink(root)) {
665 assert(get_irg_uplink(pred) >= get_irg_uplink(root));
671 return some_outof_loop & some_in_loop;
675 * Returns non-zero if n is possible loop head of an endless loop.
676 * I.e., it is a Block, Phi or Filter node and has only predecessors
678 * @arg root: only needed for assertion.
680 static int is_endless_head(ir_graph *n, ir_graph *root)
683 int some_outof_loop = 0, some_in_loop = 0;
685 arity = get_irg_n_callees(n);
686 for (i = 0; i < arity; i++) {
687 ir_graph *pred = get_irg_callee(n, i);
689 if (is_irg_callee_backedge(n, i))
691 if (!irg_is_in_stack(pred)) {
694 if (get_irg_uplink(pred) < get_irg_uplink(root)) {
695 assert(get_irg_uplink(pred) >= get_irg_uplink(root));
700 return !some_outof_loop & some_in_loop;
703 #ifdef INTERPROCEDURAL_VIEW
705 * Check whether there is a parallel edge in the ip control flow.
708 static int is_ip_head(ir_graph *n, ir_graph *pred)
712 int iv_rem = get_interprocedural_view();
713 set_interprocedural_view(1);
715 ir_node *sblock = get_irg_start_block(n);
716 int i, arity = get_Block_n_cfgpreds(sblock);
718 //printf(" edge from "); DDMG(n);
719 //printf(" to pred "); DDMG(pred);
720 //printf(" sblock "); DDMN(sblock);
722 for (i = 0; i < arity; i++) {
723 ir_node *pred_cfop = skip_Proj(get_Block_cfgpred(sblock, i));
724 //printf(" "); DDMN(pred_cfop);
725 if (is_CallBegin(pred_cfop)) { /* could be Unknown */
726 ir_graph *ip_pred = get_irn_irg(pred_cfop);
727 //printf(" "); DDMG(ip_pred);
728 if ((ip_pred == pred) && is_backedge(sblock, i)) {
729 //printf(" found\n");
735 set_interprocedural_view(iv_rem);
738 #endif /* INTERPROCEDURAL_VIEW */
741 * Returns index of the predecessor with the smallest dfn number
742 * greater-equal than limit.
744 static int smallest_dfn_pred(ir_graph *n, int limit)
746 int i, index = -2, min = -1;
748 int arity = get_irg_n_callees(n);
749 for (i = 0; i < arity; i++) {
750 ir_graph *pred = get_irg_callee(n, i);
751 if (is_irg_callee_backedge(n, i) || !irg_is_in_stack(pred))
753 if (get_irg_dfn(pred) >= limit && (min == -1 || get_irg_dfn(pred) < min)) {
755 min = get_irg_dfn(pred);
762 /** Returns index of the predecessor with the largest dfn number. */
763 static int largest_dfn_pred(ir_graph *n) {
764 int i, index = -2, max = -1;
766 int arity = get_irg_n_callees(n);
767 for (i = 0; i < arity; ++i) {
768 ir_graph *pred = get_irg_callee(n, i);
769 if (is_irg_callee_backedge (n, i) || !irg_is_in_stack(pred)) continue;
770 if (get_irg_dfn(pred) > max) {
772 max = get_irg_dfn(pred);
779 #ifndef INTERPROCEDURAL_VIEW
780 static ir_graph *find_tail(ir_graph *n) {
782 int i, res_index = -2;
785 if (!icfg && rm_cyclic_phis && remove_cyclic_phis (n)) return NULL;
787 m = stack[tos-1]; /* tos = top of stack */
788 if (is_head (m, n)) {
789 res_index = smallest_dfn_pred(m, 0);
790 if ((res_index == -2) && /* no smallest dfn pred found. */
794 if (m == n) return NULL; // Is this to catch Phi - self loops?
795 for (i = tos-2; i >= 0; --i) {
799 res_index = smallest_dfn_pred(m, get_irg_dfn(m) + 1);
800 if (res_index == -2) /* no smallest dfn pred found. */
801 res_index = largest_dfn_pred(m);
803 if ((m == n) && (res_index == -2)) {
809 /* We should not walk past our selves on the stack: The upcoming nodes
810 are not in this loop. We assume a loop not reachable from Start. */
819 /* A dead loop not reachable from Start. */
820 for (i = tos-2; i >= 0; --i) {
822 if (is_endless_head(m, n)) {
823 res_index = smallest_dfn_pred(m, get_irg_dfn(m) + 1);
824 if (res_index == -2) /* no smallest dfn pred found. */
825 res_index = largest_dfn_pred(m);
828 if (m == n) { break; } /* It's not an unreachable loop, either. */
830 //assert(0 && "no head found on stack");
834 assert (res_index > -2);
836 set_irg_callee_backedge(m, res_index);
837 return get_irg_callee(m, res_index);
840 static ir_graph *find_tail(ir_graph *n) {
842 int i, res_index = -2;
845 ir_graph *in_and_out = NULL;
846 ir_graph *only_in = NULL;
847 ir_graph *ip_in_and_out = NULL;
848 ir_graph *ip_only_in = NULL;
850 //printf("find tail for "); DDMG(n);
852 for (i = tos-1; i >= 0; --i) {
853 ir_graph *pred = (i < tos -1) ? stack[i+1] : n;
857 //printf(" found 1a! "); DDM;
859 if (is_ip_head(pred, m)) {
860 //printf(" found 1b! "); DDM;
863 } else if (!ip_only_in && is_endless_head(m, n)) {
865 //printf(" found 2a! "); DDM;
866 if (is_ip_head(pred, m)) {
867 //printf(" found 2b! "); DDM;
870 } else if (is_ip_head(pred, m)) {
871 //printf(" found 3! "); DDM; This happens for self recursions in the second
872 //assert(0); scc iteration (the one to flip the loop.)
875 if (ip_in_and_out) break; /* That's what we really want. */
877 if (m == n) break; /* Don't walk past n on the stack! */
881 if (!in_and_out && !only_in)
882 /* There is no loop */
886 /* Is there a head in the callgraph without a head in the
888 assert(in_and_out || only_in);
890 m = (ip_in_and_out) ? ip_in_and_out : ip_only_in;
893 m = (in_and_out) ? in_and_out : only_in;
895 //printf("*** head is "); DDMG(m);
897 res_index = smallest_dfn_pred(m, get_irg_dfn(m) + 1);
898 if (res_index == -2) /* no smallest dfn pred found. */
899 res_index = largest_dfn_pred(m);
901 set_irg_callee_backedge(m, res_index);
902 res = get_irg_callee(m, res_index);
903 //printf("*** tail is "); DDMG(res);
906 #endif /* INTERPROCEDURAL_VIEW */
908 /*-----------------------------------------------------------*
909 * The core algorithm. *
910 *-----------------------------------------------------------*/
913 static void cgscc(ir_graph *n) {
916 if (cg_irg_visited(n)) return;
917 mark_cg_irg_visited(n);
919 /* Initialize the node */
920 set_irg_dfn(n, current_dfn); /* Depth first number for this node */
921 set_irg_uplink(n, current_dfn); /* ... is default uplink. */
925 arity = get_irg_n_callees(n);
926 for (i = 0; i < arity; i++) {
928 if (is_irg_callee_backedge(n, i)) continue;
929 m = get_irg_callee(n, i);
931 /** This marks the backedge, but does it guarantee a correct loop tree? */
932 //if (m == n) { set_irg_callee_backedge(n, i); continue; }
935 if (irg_is_in_stack(m)) {
936 /* Uplink of m is smaller if n->m is a backedge.
937 Propagate the uplink to mark the cfloop. */
938 if (get_irg_uplink(m) < get_irg_uplink(n))
939 set_irg_uplink(n, get_irg_uplink(m));
943 if (get_irg_dfn(n) == get_irg_uplink(n)) {
944 /* This condition holds for
945 1) the node with the incoming backedge.
946 That is: We found a cfloop!
947 2) Straight line code, because no uplink has been propagated, so the
948 uplink still is the same as the dfn.
950 But n might not be a proper cfloop head for the analysis. Proper cfloop
951 heads are Block and Phi nodes. find_tail searches the stack for
952 Block's and Phi's and takes those nodes as cfloop heads for the current
953 cfloop instead and marks the incoming edge as backedge. */
955 ir_graph *tail = find_tail(n);
957 /* We have a cfloop, that is no straight line code,
958 because we found a cfloop head!
959 Next actions: Open a new cfloop on the cfloop tree and
960 try to find inner cfloops */
963 ir_loop *l = new_loop();
965 /* Remove the cfloop from the stack ... */
966 pop_scc_unmark_visit(n);
968 /* The current backedge has been marked, that is temporarily eliminated,
969 by find tail. Start the scc algorithm
970 anew on the subgraph thats left (the current cfloop without the backedge)
971 in order to find more inner cfloops. */
975 assert(cg_irg_visited(n));
985 * reset the backedge information for all callers in all irgs
987 static void reset_isbe(void) {
988 int i, n_irgs = get_irp_n_irgs();
990 for (i = 0; i < n_irgs; ++i) {
991 ir_graph *irg = get_irp_irg(i);
993 if (irg->caller_isbe)
994 xfree(irg->caller_isbe);
995 irg->caller_isbe = NULL;
997 if (irg->callee_isbe)
998 xfree(irg->callee_isbe);
999 irg->callee_isbe = NULL;
1003 /* ----------------------------------------------------------------------------------- */
1004 /* Another algorithm to compute recursion nesting depth */
1005 /* Walk the callgraph. For each crossed edge increase the loop depth by the edge */
1006 /* weight. Assign graphs the maximal depth. */
1007 /* ----------------------------------------------------------------------------------- */
1009 static void compute_loop_depth(ir_graph *irg, void *env) {
1010 int current_nesting = *(int *) env;
1011 int old_nesting = irg->callgraph_loop_depth;
1012 ir_visited_t old_visited = get_cg_irg_visited(irg);
1017 if (cg_irg_visited(irg)) return;
1019 mark_cg_irg_visited(irg);
1021 //printf(" old: %d new %d master %d", old_visited, get_cg_irg_visited(irg), master_cg_visited); DDMG(irg);
1024 if (old_nesting < current_nesting)
1025 irg->callgraph_loop_depth = current_nesting;
1027 if (current_nesting > irp->max_callgraph_loop_depth)
1028 irp->max_callgraph_loop_depth = current_nesting;
1030 if ((old_visited +1 < get_cg_irg_visited(irg)) || /* not yet visited */
1031 (old_nesting < current_nesting)) { /* propagate larger nesting */
1032 /* Don't walk the graph, but a tree that is an unfolded graph. */
1033 n_callees = get_irg_n_callees(irg);
1034 for (i = 0; i < n_callees; i++) {
1035 ir_graph *m = get_irg_callee(irg, i);
1036 *(int *)env += get_irg_callee_loop_depth(irg, i);
1037 compute_loop_depth(m, env);
1038 *(int *)env -= get_irg_callee_loop_depth(irg, i);
1042 set_cg_irg_visited(irg, master_cg_visited-1);
1045 /* ------------------------------------------------------------------------------------ */
1046 /* Another algorithm to compute recursion nesting depth */
1047 /* Walk the callgraph. For each crossed loop increase the nesting depth by one. */
1048 /* Assign graphs the maximal nesting depth. Don't increase if passing loops more than */
1050 /* ------------------------------------------------------------------------------------ */
1053 /* For callees, we want to remember the Call nodes, too. */
1054 typedef struct ana_entry2 {
1055 ir_loop **loop_stack; /**< a stack of ir_loop entries */
1056 int tos; /**< the top of stack entry */
1057 int recursion_nesting;
1061 * push a loop entry on the stack
1063 static void push2(ana_entry2 *e, ir_loop *g) {
1064 if (ARR_LEN(e->loop_stack) == e->tos) {
1065 ARR_APP1(ir_loop *, e->loop_stack, g);
1067 e->loop_stack[e->tos] = g;
1073 * returns the top of stack and pop it
1075 static ir_loop *pop2(ana_entry2 *e) {
1076 return e->loop_stack[--e->tos];
1080 * check if a loop g in on the stack. Did not check the TOS.
1082 static int in_stack(ana_entry2 *e, ir_loop *g) {
1084 for (i = e->tos-1; i >= 0; --i) {
1085 if (e->loop_stack[i] == g) return 1;
1090 static void compute_rec_depth(ir_graph *irg, void *env) {
1091 ana_entry2 *e = (ana_entry2 *)env;
1092 ir_loop *l = irg->l;
1093 int depth, old_depth = irg->callgraph_recursion_depth;
1097 if (cg_irg_visited(irg))
1099 mark_cg_irg_visited(irg);
1101 /* -- compute and set the new nesting value -- */
1102 if ((l != irp->outermost_cg_loop) && !in_stack(e, l)) {
1104 e->recursion_nesting++;
1107 depth = e->recursion_nesting;
1109 if (old_depth < depth)
1110 irg->callgraph_recursion_depth = depth;
1112 if (depth > irp->max_callgraph_recursion_depth)
1113 irp->max_callgraph_recursion_depth = depth;
1115 /* -- spread the nesting value -- */
1116 if (depth == 0 || old_depth < depth) {
1117 /* Don't walk the graph, but a tree that is an unfolded graph.
1118 Therefore we unset the visited flag at the end. */
1119 n_callees = get_irg_n_callees(irg);
1120 for (i = 0; i < n_callees; ++i) {
1121 ir_graph *m = get_irg_callee(irg, i);
1122 compute_rec_depth(m, env);
1126 /* -- clean up -- */
1129 e->recursion_nesting--;
1131 set_cg_irg_visited(irg, master_cg_visited-1);
1135 /* ----------------------------------------------------------------------------------- */
1136 /* Another algorithm to compute the execution frequency of methods ignoring recursions. */
1137 /* Walk the callgraph. Ignore backedges. Use sum of execution frequencies of Call */
1138 /* nodes to evaluate a callgraph edge. */
1139 /* ----------------------------------------------------------------------------------- */
1141 /* Returns the method execution frequency of a graph. */
1142 double get_irg_method_execution_frequency(ir_graph *irg) {
1143 return irg->method_execution_frequency;
1147 * Increase the method execution frequency to freq if its current value is
1148 * smaller then this.
1150 static void set_irg_method_execution_frequency(ir_graph *irg, double freq) {
1151 irg->method_execution_frequency = freq;
1153 if (irp->max_method_execution_frequency < freq)
1154 irp->max_method_execution_frequency = freq;
1157 static void compute_method_execution_frequency(ir_graph *irg, void *env) {
1164 if (cg_irg_visited(irg))
1167 /* We need the values of all predecessors (except backedges).
1168 So they must be marked. Else we will reach the node through
1169 one of the unmarked ones. */
1170 n_callers = get_irg_n_callers(irg);
1171 for (i = 0; i < n_callers; ++i) {
1172 ir_graph *m = get_irg_caller(irg, i);
1173 if (is_irg_caller_backedge(irg, i))
1175 if (!cg_irg_visited(m)) {
1179 mark_cg_irg_visited(irg);
1181 /* Compute the new frequency. */
1184 for (i = 0; i < n_callers; i++) {
1185 if (! is_irg_caller_backedge(irg, i)) {
1186 double edge_freq = get_irg_caller_method_execution_frequency(irg, i);
1187 assert(edge_freq >= 0);
1194 /* A starting point: method only called from outside,
1195 or only backedges as predecessors. */
1199 set_irg_method_execution_frequency(irg, freq);
1202 n_callees = get_irg_n_callees(irg);
1203 for (i = 0; i < n_callees; ++i) {
1204 compute_method_execution_frequency(get_irg_callee(irg, i), NULL);
1209 /* ----------------------------------------------------------------------------------- */
1210 /* The recursion stuff driver. */
1211 /* ----------------------------------------------------------------------------------- */
1213 /* Compute the backedges that represent recursions. */
1214 void find_callgraph_recursions(void) {
1215 int i, n_irgs = get_irp_n_irgs();
1216 struct obstack temp;
1220 /* -- compute the looptree. -- */
1222 /* The outermost graph. We start here. Then we start at all
1223 functions in irg list that are never called, then at the remaining
1224 unvisited ones. The third step is needed for functions that are not
1225 reachable from the outermost graph, but call themselves in a cycle. */
1226 assert(get_irp_main_irg());
1227 outermost_ir_graph = get_irp_main_irg();
1228 obstack_init(&temp);
1231 current_loop = NULL;
1232 new_loop(); /* sets current_loop */
1234 ++master_cg_visited;
1235 cgscc(outermost_ir_graph);
1236 for (i = 0; i < n_irgs; ++i) {
1237 ir_graph *irg = get_irp_irg(i);
1238 if (!cg_irg_visited(irg) && get_irg_n_callers(irg) == 0)
1241 for (i = 0; i < n_irgs; ++i) {
1242 ir_graph *irg = get_irp_irg(i);
1243 if (!cg_irg_visited(irg))
1246 obstack_free(&temp, NULL);
1248 irp->outermost_cg_loop = current_loop;
1249 mature_loops(current_loop, outermost_ir_graph->obst);
1251 /* -- Reverse the backedge information. -- */
1252 for (i = 0; i < n_irgs; ++i) {
1253 ir_graph *irg = get_irp_irg(i);
1254 int j, n_callees = get_irg_n_callees(irg);
1255 for (j = 0; j < n_callees; ++j) {
1256 if (is_irg_callee_backedge(irg, j))
1257 set_irg_caller_backedge(get_irg_callee(irg, j), irg);
1261 irp->callgraph_state = irp_callgraph_and_calltree_consistent;
1264 /* Compute interprocedural performance estimates. */
1265 void compute_performance_estimates(void) {
1266 int i, n_irgs = get_irp_n_irgs();
1267 int current_nesting;
1270 assert(get_irp_exec_freq_state() != exec_freq_none && "execution frequency not calculated");
1272 /* -- compute the loop depth -- */
1273 current_nesting = 0;
1274 irp->max_callgraph_loop_depth = 0;
1275 master_cg_visited += 2;
1276 //printf(" ** starting at "); DDMG(get_irp_main_irg());
1277 compute_loop_depth(get_irp_main_irg(), ¤t_nesting);
1278 for (i = 0; i < n_irgs; i++) {
1279 ir_graph *irg = get_irp_irg(i);
1280 if ((get_cg_irg_visited(irg) < master_cg_visited-1) &&
1281 get_irg_n_callers(irg) == 0) {
1282 compute_loop_depth(irg, ¤t_nesting);
1283 //printf(" ** starting at "); DDMG(irg);
1286 for (i = 0; i < n_irgs; i++) {
1287 ir_graph *irg = get_irp_irg(i);
1288 if (get_cg_irg_visited(irg) < master_cg_visited-1) {
1289 compute_loop_depth(irg, ¤t_nesting);
1290 //printf(" ** starting at "); DDMG(irg);
1295 /* -- compute the recursion depth -- */
1296 e.loop_stack = NEW_ARR_F(ir_loop *, 0);
1298 e.recursion_nesting = 0;
1300 irp->max_callgraph_recursion_depth = 0;
1302 master_cg_visited += 2;
1303 compute_rec_depth(get_irp_main_irg(), &e);
1304 //printf(" ++ starting at "); DDMG(get_irp_main_irg());
1305 for (i = 0; i < n_irgs; i++) {
1306 ir_graph *irg = get_irp_irg(i);
1307 if ((get_cg_irg_visited(irg) < master_cg_visited-1) &&
1308 get_irg_n_callers(irg) == 0) {
1309 compute_rec_depth(irg, &e);
1310 //printf(" ++ starting at "); DDMG(irg);
1313 for (i = 0; i < n_irgs; i++) {
1314 ir_graph *irg = get_irp_irg(i);
1315 if (get_cg_irg_visited(irg) < master_cg_visited-1) {
1316 compute_rec_depth(irg, &e);
1317 //printf(" ++ starting at "); DDMG(irg);
1321 DEL_ARR_F(e.loop_stack);
1323 /* -- compute the execution frequency -- */
1324 irp->max_method_execution_frequency = 0;
1325 master_cg_visited += 2;
1326 assert(get_irg_n_callers(get_irp_main_irg()) == 0);
1327 compute_method_execution_frequency(get_irp_main_irg(), NULL);
1328 for (i = 0; i < n_irgs; i++) {
1329 ir_graph *irg = get_irp_irg(i);
1330 if ((get_cg_irg_visited(irg) < master_cg_visited-1) &&
1331 get_irg_n_callers(irg) == 0) {
1332 compute_method_execution_frequency(irg, NULL);
1335 for (i = 0; i < n_irgs; i++) {
1336 ir_graph *irg = get_irp_irg(i);
1337 if (get_cg_irg_visited(irg) < master_cg_visited-1) {
1338 compute_method_execution_frequency(irg, NULL);
1343 /* Returns the maximal loop depth of all paths from an external visible method to
1345 int get_irg_loop_depth(ir_graph *irg) {
1346 assert(irp->callgraph_state == irp_callgraph_consistent ||
1347 irp->callgraph_state == irp_callgraph_and_calltree_consistent);
1348 return irg->callgraph_loop_depth;
1351 /* Returns the maximal recursion depth of all paths from an external visible method to
1353 int get_irg_recursion_depth(ir_graph *irg) {
1354 assert(irp->callgraph_state == irp_callgraph_and_calltree_consistent);
1355 return irg->callgraph_recursion_depth;
1358 /* Computes the interprocedural loop nesting information. */
1359 void analyse_loop_nesting_depth(void) {
1360 ir_entity **free_methods = NULL;
1363 /* establish preconditions. */
1364 if (get_irp_callee_info_state() != irg_callee_info_consistent) {
1365 cgana(&arr_len, &free_methods);
1368 if (irp_callgraph_consistent != get_irp_callgraph_state()) {
1369 compute_callgraph();
1372 find_callgraph_recursions();
1374 compute_performance_estimates();
1376 set_irp_loop_nesting_depth_state(loop_nesting_depth_consistent);
1379 loop_nesting_depth_state get_irp_loop_nesting_depth_state(void) {
1380 return irp->lnd_state;
1382 void set_irp_loop_nesting_depth_state(loop_nesting_depth_state s) {
1385 void set_irp_loop_nesting_depth_state_inconsistent(void) {
1386 if (irp->lnd_state == loop_nesting_depth_consistent)
1387 irp->lnd_state = loop_nesting_depth_inconsistent;