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);
53 /** Returns the callgraph state of the program representation. */
54 irp_callgraph_state get_irp_callgraph_state(void)
56 return irp->callgraph_state;
59 /* Sets the callgraph state of the program representation. */
60 void set_irp_callgraph_state(irp_callgraph_state s)
62 irp->callgraph_state = s;
65 /* Returns the number of procedures that call the given irg. */
66 int get_irg_n_callers(const ir_graph *irg)
68 if (irg->callers) return ARR_LEN(irg->callers);
72 /* Returns the caller at position pos. */
73 ir_graph *get_irg_caller(const ir_graph *irg, int pos)
75 assert(pos >= 0 && pos < get_irg_n_callers(irg));
76 if (irg->callers) return irg->callers[pos];
80 /* Returns non-zero if the caller at position pos is "a backedge", i.e. a recursion. */
81 int is_irg_caller_backedge(const ir_graph *irg, int pos)
83 assert(pos >= 0 && pos < get_irg_n_callers(irg));
84 return irg->caller_isbe != NULL ? rbitset_is_set(irg->caller_isbe, pos) : 0;
87 /** Search the caller in the list of all callers and set it's backedge property. */
88 static void set_irg_caller_backedge(ir_graph *irg, ir_graph *caller)
90 int i, n_callers = get_irg_n_callers(irg);
92 /* allocate a new array on demand */
93 if (irg->caller_isbe == NULL)
94 irg->caller_isbe = rbitset_malloc(n_callers);
95 for (i = 0; i < n_callers; ++i) {
96 if (get_irg_caller(irg, i) == caller) {
97 rbitset_set(irg->caller_isbe, i);
103 /* Returns non-zero if the irg has a backedge caller. */
104 int has_irg_caller_backedge(const 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(const ir_graph *callee, int pos_caller)
123 ir_graph *caller = get_irg_caller(callee, pos_caller);
124 /* search the other relation for the corresponding edge. */
126 int i, n_callees = get_irg_n_callees(caller);
127 for (i = 0; i < n_callees; ++i) {
128 if (get_irg_callee(caller, i) == callee) {
134 assert(pos_callee >= 0);
139 /* Returns the maximal loop depth of call nodes that call along this edge. */
140 int get_irg_caller_loop_depth(const ir_graph *irg, int pos)
142 ir_graph *caller = get_irg_caller(irg, pos);
143 int pos_callee = reverse_pos(irg, pos);
145 return get_irg_callee_loop_depth(caller, pos_callee);
149 /* Returns the number of procedures that are called by the given irg. */
150 int get_irg_n_callees(const ir_graph *irg)
152 if (irg->callees) return ARR_LEN(irg->callees);
156 /* Returns the callee at position pos. */
157 ir_graph *get_irg_callee(const ir_graph *irg, int pos)
159 assert(pos >= 0 && pos < get_irg_n_callees(irg));
160 if (irg->callees) return irg->callees[pos]->irg;
164 /* Returns non-zero if the callee at position pos is "a backedge", i.e. a recursion. */
165 int is_irg_callee_backedge(const ir_graph *irg, int pos)
167 assert(pos >= 0 && pos < get_irg_n_callees(irg));
168 return irg->callee_isbe != NULL ? rbitset_is_set(irg->callee_isbe, pos) : 0;
171 /* Returns non-zero if the irg has a backedge callee. */
172 int has_irg_callee_backedge(const ir_graph *irg)
174 int i, n_callees = get_irg_n_callees(irg);
176 if (irg->callee_isbe != NULL) {
177 for (i = 0; i < n_callees; ++i)
178 if (rbitset_is_set(irg->callee_isbe, i))
185 * Mark the callee at position pos as a backedge.
187 static void set_irg_callee_backedge(ir_graph *irg, int pos)
189 int n = get_irg_n_callees(irg);
191 /* allocate a new array on demand */
192 if (irg->callee_isbe == NULL)
193 irg->callee_isbe = rbitset_malloc(n);
194 assert(pos >= 0 && pos < n);
195 rbitset_set(irg->callee_isbe, pos);
198 /* Returns the maximal loop depth of call nodes that call along this edge. */
199 int get_irg_callee_loop_depth(const ir_graph *irg, int pos)
201 assert(pos >= 0 && pos < get_irg_n_callees(irg));
202 if (irg->callees) return irg->callees[pos]->max_depth;
206 static double get_irg_callee_execution_frequency(const ir_graph *irg, int pos)
208 ir_node **arr = irg->callees[pos]->call_list;
209 int i, n_Calls = ARR_LEN(arr);
212 for (i = 0; i < n_Calls; ++i) {
213 freq += get_irn_exec_freq(arr[i]);
218 static double get_irg_callee_method_execution_frequency(const ir_graph *irg,
221 double call_freq = get_irg_callee_execution_frequency(irg, pos);
222 double meth_freq = get_irg_method_execution_frequency(irg);
223 return call_freq * meth_freq;
226 static double get_irg_caller_method_execution_frequency(const ir_graph *irg,
229 ir_graph *caller = get_irg_caller(irg, pos);
230 int pos_callee = reverse_pos(irg, pos);
232 return get_irg_callee_method_execution_frequency(caller, pos_callee);
236 /* --------------------- Compute the callgraph ------------------------ */
239 * Walker called by compute_callgraph(), analyses all Call nodes.
241 static void ana_Call(ir_node *n, void *env)
247 if (! is_Call(n)) return;
249 irg = get_irn_irg(n);
250 n_callees = get_Call_n_callees(n);
251 for (i = 0; i < n_callees; ++i) {
252 ir_entity *callee_e = get_Call_callee(n, i);
253 ir_graph *callee = get_entity_irg(callee_e);
257 cg_callee_entry *found;
262 pset_insert((pset *)callee->callers, irg, HASH_PTR(irg));
263 found = pset_find((pset *)irg->callees, &buf, HASH_PTR(callee));
264 if (found) { /* add Call node to list, compute new nesting. */
265 ir_node **arr = found->call_list;
266 ARR_APP1(ir_node *, arr, n);
267 found->call_list = arr;
268 } else { /* New node, add Call node and init nesting. */
269 found = OALLOC(irg->obst, cg_callee_entry);
271 found->call_list = NEW_ARR_F(ir_node *, 1);
272 found->call_list[0] = n;
273 found->max_depth = 0;
274 pset_insert((pset *)irg->callees, found, HASH_PTR(callee));
276 depth = get_loop_depth(get_irn_loop(get_nodes_block(n)));
277 found->max_depth = (depth > found->max_depth) ? depth : found->max_depth;
282 /** compare two ir graphs in a cg_callee_entry */
283 static int cg_callee_entry_cmp(const void *elt, const void *key)
285 const cg_callee_entry *e1 = elt;
286 const cg_callee_entry *e2 = key;
287 return e1->irg != e2->irg;
290 /** compare two ir graphs for pointer identity */
291 static int graph_cmp(const void *elt, const void *key)
293 const ir_graph *e1 = elt;
294 const ir_graph *e2 = key;
299 /* Construct and destruct the callgraph. */
300 void compute_callgraph(void)
304 #ifdef INTERPROCEDURAL_VIEW
305 assert(! get_interprocedural_view()); /* Else walking will not reach the Call nodes. */
311 n_irgs = get_irp_n_irgs();
312 for (i = 0; i < n_irgs; ++i) {
313 ir_graph *irg = get_irp_irg(i);
314 assert(get_irg_callee_info_state(irg) == irg_callee_info_consistent);
315 irg->callees = (cg_callee_entry **)new_pset(cg_callee_entry_cmp, 8);
316 irg->callers = (ir_graph **)new_pset(graph_cmp, 8);
317 //construct_cf_backedges(irg);
320 /* Compute the call graph */
321 for (i = 0; i < n_irgs; ++i) {
322 ir_graph *irg = get_irp_irg(i);
323 construct_cf_backedges(irg); // We also find the maximal loop depth of a call.
324 irg_walk_graph(irg, ana_Call, NULL, NULL);
327 /* Change the sets to arrays. */
328 for (i = 0; i < n_irgs; ++i) {
330 cg_callee_entry *callee;
331 ir_graph *c, *irg = get_irp_irg(i);
332 pset *callee_set, *caller_set;
334 callee_set = (pset *)irg->callees;
335 count = pset_count(callee_set);
336 irg->callees = NEW_ARR_F(cg_callee_entry *, count);
337 irg->callee_isbe = NULL;
338 callee = pset_first(callee_set);
339 for (j = 0; j < count; ++j) {
340 irg->callees[j] = callee;
341 callee = pset_next(callee_set);
343 del_pset(callee_set);
344 assert(callee == NULL);
346 caller_set = (pset *)irg->callers;
347 count = pset_count(caller_set);
348 irg->callers = NEW_ARR_F(ir_graph *, count);
349 irg->caller_isbe = NULL;
350 c = pset_first(caller_set);
351 for (j = 0; j < count; ++j) {
353 c = pset_next(caller_set);
355 del_pset(caller_set);
358 set_irp_callgraph_state(irp_callgraph_consistent);
361 /* Destruct the callgraph. */
362 void free_callgraph(void)
364 int i, n_irgs = get_irp_n_irgs();
365 for (i = 0; i < n_irgs; ++i) {
366 ir_graph *irg = get_irp_irg(i);
367 if (irg->callees) DEL_ARR_F(irg->callees);
368 if (irg->callers) DEL_ARR_F(irg->callers);
369 if (irg->callee_isbe) free(irg->callee_isbe);
370 if (irg->caller_isbe) free(irg->caller_isbe);
373 irg->callee_isbe = NULL;
374 irg->caller_isbe = NULL;
376 set_irp_callgraph_state(irp_callgraph_none);
379 /* ----------------------------------------------------------------------------------- */
380 /* A walker for the callgraph */
381 /* ----------------------------------------------------------------------------------- */
384 static void do_walk(ir_graph *irg, callgraph_walk_func *pre, callgraph_walk_func *post, void *env)
388 if (cg_irg_visited(irg))
390 mark_cg_irg_visited(irg);
395 n_callees = get_irg_n_callees(irg);
396 for (i = 0; i < n_callees; i++) {
397 ir_graph *m = get_irg_callee(irg, i);
398 do_walk(m, pre, post, env);
405 void callgraph_walk(callgraph_walk_func *pre, callgraph_walk_func *post, void *env)
407 int i, n_irgs = get_irp_n_irgs();
410 /* roots are methods which have no callers in the current program */
411 for (i = 0; i < n_irgs; ++i) {
412 ir_graph *irg = get_irp_irg(i);
414 if (get_irg_n_callers(irg) == 0)
415 do_walk(irg, pre, post, env);
418 /* in case of unreachable call loops we haven't visited some irgs yet */
419 for (i = 0; i < n_irgs; i++) {
420 ir_graph *irg = get_irp_irg(i);
421 do_walk(irg, pre, post, env);
425 /* ----------------------------------------------------------------------------------- */
426 /* loop construction algorithm */
427 /* ----------------------------------------------------------------------------------- */
429 static ir_graph *outermost_ir_graph; /**< The outermost graph the scc is computed
431 static ir_loop *current_loop; /**< Current cfloop construction is working
433 static int loop_node_cnt = 0; /**< Counts the number of allocated cfloop nodes.
434 Each cfloop node gets a unique number.
435 What for? ev. remove. @@@ */
436 static int current_dfn = 1; /**< Counter to generate depth first numbering
439 /*-----------------*/
440 /* Node attributes */
441 /*-----------------*/
443 typedef struct scc_info {
444 int in_stack; /**< Marks whether node is on the stack. */
445 int dfn; /**< Depth first search number. */
446 int uplink; /**< dfn number of ancestor. */
451 * allocates a new scc_info on the obstack
453 static inline scc_info *new_scc_info(struct obstack *obst)
455 return OALLOCZ(obst, scc_info);
459 * Returns non-zero if a graph was already visited.
461 static inline int cg_irg_visited(ir_graph *irg)
463 return irg->self_visited >= master_cg_visited;
467 * Marks a graph as visited.
469 static inline void mark_cg_irg_visited(ir_graph *irg)
471 irg->self_visited = master_cg_visited;
475 * Set a graphs visited flag to i.
477 static inline void set_cg_irg_visited(ir_graph *irg, ir_visited_t i)
479 irg->self_visited = i;
483 * Returns the visited flag of a graph.
485 static inline ir_visited_t get_cg_irg_visited(ir_graph *irg)
487 return irg->self_visited;
490 static inline void mark_irg_in_stack(ir_graph *irg)
492 scc_info *info = get_irg_link(irg);
493 assert(info && "missing call to init_scc()");
497 static inline void mark_irg_not_in_stack(ir_graph *irg)
499 scc_info *info = get_irg_link(irg);
500 assert(info && "missing call to init_scc()");
504 static inline int irg_is_in_stack(ir_graph *irg)
506 scc_info *info = get_irg_link(irg);
507 assert(info && "missing call to init_scc()");
508 return info->in_stack;
511 static inline void set_irg_uplink(ir_graph *irg, int uplink)
513 scc_info *info = get_irg_link(irg);
514 assert(info && "missing call to init_scc()");
515 info->uplink = uplink;
518 static inline int get_irg_uplink(ir_graph *irg)
520 scc_info *info = get_irg_link(irg);
521 assert(info && "missing call to init_scc()");
525 static inline void set_irg_dfn(ir_graph *irg, int dfn)
527 scc_info *info = get_irg_link(irg);
528 assert(info && "missing call to init_scc()");
532 static inline int get_irg_dfn(ir_graph *irg)
534 scc_info *info = get_irg_link(irg);
535 assert(info && "missing call to init_scc()");
539 /**********************************************************************/
541 /**********************************************************************/
543 static ir_graph **stack = NULL;
544 static int tos = 0; /**< top of stack */
547 * Initialize the irg stack.
549 static inline void init_stack(void)
552 ARR_RESIZE(ir_graph *, stack, 1000);
554 stack = NEW_ARR_F(ir_graph *, 1000);
560 * push a graph on the irg stack
561 * @param n the graph to be pushed
563 static inline void push(ir_graph *irg)
565 if (tos == ARR_LEN(stack)) {
566 int nlen = ARR_LEN(stack) * 2;
567 ARR_RESIZE(ir_node *, stack, nlen);
570 mark_irg_in_stack(irg);
574 * return the topmost graph on the stack and pop it
576 static inline ir_graph *pop(void)
578 ir_graph *irg = stack[--tos];
579 mark_irg_not_in_stack(irg);
584 * The nodes up to irg belong to the current loop.
585 * Removes them from the stack and adds them to the current loop.
587 static inline void pop_scc_to_loop(ir_graph *irg)
594 set_irg_dfn(m, loop_node_cnt);
595 add_loop_irg(current_loop, m);
597 //m->callgraph_loop_depth = current_loop->depth;
601 /* GL ??? my last son is my grandson??? Removes cfloops with no
602 ir_nodes in them. Such loops have only another loop as son. (Why
603 can't they have two loops as sons? Does it never get that far? ) */
604 static void close_loop(ir_loop *l)
606 int last = get_loop_n_elements(l) - 1;
607 loop_element lelement = get_loop_element(l, last);
608 ir_loop *last_son = lelement.son;
610 if (get_kind(last_son) == k_ir_loop &&
611 get_loop_n_elements(last_son) == 1) {
614 lelement = get_loop_element(last_son, 0);
616 if (get_kind(gson) == k_ir_loop) {
617 loop_element new_last_son;
619 gson->outer_loop = l;
620 new_last_son.son = gson;
621 l->children[last] = new_last_son;
628 * Removes and unmarks all nodes up to n from the stack.
629 * The nodes must be visited once more to assign them to a scc.
631 static inline void pop_scc_unmark_visit(ir_graph *n)
637 set_cg_irg_visited(m, 0);
641 /**********************************************************************/
642 /* The loop data structure. **/
643 /**********************************************************************/
646 * Allocates a new loop as son of current_loop. Sets current_loop
647 * to the new loop and returns the father.
649 static ir_loop *new_loop(void)
651 ir_loop *father = current_loop;
652 ir_loop *son = alloc_loop(father, outermost_ir_graph->obst);
659 /**********************************************************************/
660 /* Constructing and destructing the loop/backedge information. **/
661 /**********************************************************************/
663 /* Initialization steps. **********************************************/
665 static void init_scc(struct obstack *obst)
674 n_irgs = get_irp_n_irgs();
675 for (i = 0; i < n_irgs; ++i) {
676 ir_graph *irg = get_irp_irg(i);
677 set_irg_link(irg, new_scc_info(obst));
678 irg->callgraph_recursion_depth = 0;
679 irg->callgraph_loop_depth = 0;
683 /** Returns non-zero if n is a loop header, i.e., it is a Block node
684 * and has predecessors within the cfloop and out of the cfloop.
686 * @param root: only needed for assertion.
688 static int is_head(ir_graph *n, ir_graph *root)
691 int some_outof_loop = 0, some_in_loop = 0;
693 arity = get_irg_n_callees(n);
694 for (i = 0; i < arity; i++) {
695 ir_graph *pred = get_irg_callee(n, i);
696 if (is_irg_callee_backedge(n, i)) continue;
697 if (!irg_is_in_stack(pred)) {
700 if (get_irg_uplink(pred) < get_irg_uplink(root)) {
701 assert(get_irg_uplink(pred) >= get_irg_uplink(root));
707 return some_outof_loop && some_in_loop;
711 * Returns non-zero if n is possible loop head of an endless loop.
712 * I.e., it is a Block, Phi or Filter node and has only predecessors
714 * @arg root: only needed for assertion.
716 static int is_endless_head(ir_graph *n, ir_graph *root)
719 int some_outof_loop = 0, some_in_loop = 0;
721 arity = get_irg_n_callees(n);
722 for (i = 0; i < arity; i++) {
723 ir_graph *pred = get_irg_callee(n, i);
725 if (is_irg_callee_backedge(n, i))
727 if (!irg_is_in_stack(pred)) {
730 if (get_irg_uplink(pred) < get_irg_uplink(root)) {
731 assert(get_irg_uplink(pred) >= get_irg_uplink(root));
736 return !some_outof_loop && some_in_loop;
739 #ifdef INTERPROCEDURAL_VIEW
741 * Check whether there is a parallel edge in the ip control flow.
744 static int is_ip_head(ir_graph *n, ir_graph *pred)
748 int iv_rem = get_interprocedural_view();
749 set_interprocedural_view(1);
751 ir_node *sblock = get_irg_start_block(n);
752 int i, arity = get_Block_n_cfgpreds(sblock);
754 //printf(" edge from "); DDMG(n);
755 //printf(" to pred "); DDMG(pred);
756 //printf(" sblock "); DDMN(sblock);
758 for (i = 0; i < arity; i++) {
759 ir_node *pred_cfop = skip_Proj(get_Block_cfgpred(sblock, i));
760 //printf(" "); DDMN(pred_cfop);
761 if (is_CallBegin(pred_cfop)) { /* could be Unknown */
762 ir_graph *ip_pred = get_irn_irg(pred_cfop);
763 //printf(" "); DDMG(ip_pred);
764 if ((ip_pred == pred) && is_backedge(sblock, i)) {
765 //printf(" found\n");
771 set_interprocedural_view(iv_rem);
774 #endif /* INTERPROCEDURAL_VIEW */
777 * Returns index of the predecessor with the smallest dfn number
778 * greater-equal than limit.
780 static int smallest_dfn_pred(ir_graph *n, int limit)
782 int i, index = -2, min = -1;
784 int arity = get_irg_n_callees(n);
785 for (i = 0; i < arity; i++) {
786 ir_graph *pred = get_irg_callee(n, i);
787 if (is_irg_callee_backedge(n, i) || !irg_is_in_stack(pred))
789 if (get_irg_dfn(pred) >= limit && (min == -1 || get_irg_dfn(pred) < min)) {
791 min = get_irg_dfn(pred);
798 /** Returns index of the predecessor with the largest dfn number. */
799 static int largest_dfn_pred(ir_graph *n)
801 int i, index = -2, max = -1;
803 int arity = get_irg_n_callees(n);
804 for (i = 0; i < arity; ++i) {
805 ir_graph *pred = get_irg_callee(n, i);
806 if (is_irg_callee_backedge (n, i) || !irg_is_in_stack(pred)) continue;
807 if (get_irg_dfn(pred) > max) {
809 max = get_irg_dfn(pred);
816 #ifndef INTERPROCEDURAL_VIEW
817 static ir_graph *find_tail(ir_graph *n)
820 int i, res_index = -2;
823 if (!icfg && rm_cyclic_phis && remove_cyclic_phis (n)) return NULL;
825 m = stack[tos-1]; /* tos = top of stack */
826 if (is_head (m, n)) {
827 res_index = smallest_dfn_pred(m, 0);
828 if ((res_index == -2) && /* no smallest dfn pred found. */
832 if (m == n) return NULL; // Is this to catch Phi - self loops?
833 for (i = tos-2; i >= 0; --i) {
837 res_index = smallest_dfn_pred(m, get_irg_dfn(m) + 1);
838 if (res_index == -2) /* no smallest dfn pred found. */
839 res_index = largest_dfn_pred(m);
841 if ((m == n) && (res_index == -2)) {
847 /* We should not walk past our selves on the stack: The upcoming nodes
848 are not in this loop. We assume a loop not reachable from Start. */
857 /* A dead loop not reachable from Start. */
858 for (i = tos-2; i >= 0; --i) {
860 if (is_endless_head(m, n)) {
861 res_index = smallest_dfn_pred(m, get_irg_dfn(m) + 1);
862 if (res_index == -2) /* no smallest dfn pred found. */
863 res_index = largest_dfn_pred(m);
866 if (m == n) { break; } /* It's not an unreachable loop, either. */
868 //assert(0 && "no head found on stack");
872 assert (res_index > -2);
874 set_irg_callee_backedge(m, res_index);
875 return get_irg_callee(m, res_index);
878 static ir_graph *find_tail(ir_graph *n)
881 int i, res_index = -2;
884 ir_graph *in_and_out = NULL;
885 ir_graph *only_in = NULL;
886 ir_graph *ip_in_and_out = NULL;
887 ir_graph *ip_only_in = NULL;
889 //printf("find tail for "); DDMG(n);
891 for (i = tos-1; i >= 0; --i) {
892 ir_graph *pred = (i < tos -1) ? stack[i+1] : n;
896 //printf(" found 1a! "); DDM;
898 if (is_ip_head(pred, m)) {
899 //printf(" found 1b! "); DDM;
902 } else if (!ip_only_in && is_endless_head(m, n)) {
904 //printf(" found 2a! "); DDM;
905 if (is_ip_head(pred, m)) {
906 //printf(" found 2b! "); DDM;
909 } else if (is_ip_head(pred, m)) {
910 //printf(" found 3! "); DDM; This happens for self recursions in the second
911 //assert(0); scc iteration (the one to flip the loop.)
914 if (ip_in_and_out) break; /* That's what we really want. */
916 if (m == n) break; /* Don't walk past n on the stack! */
920 if (!in_and_out && !only_in)
921 /* There is no loop */
925 /* Is there a head in the callgraph without a head in the
927 assert(in_and_out || only_in);
929 m = (ip_in_and_out) ? ip_in_and_out : ip_only_in;
932 m = (in_and_out) ? in_and_out : only_in;
934 //printf("*** head is "); DDMG(m);
936 res_index = smallest_dfn_pred(m, get_irg_dfn(m) + 1);
937 if (res_index == -2) /* no smallest dfn pred found. */
938 res_index = largest_dfn_pred(m);
940 set_irg_callee_backedge(m, res_index);
941 res = get_irg_callee(m, res_index);
942 //printf("*** tail is "); DDMG(res);
945 #endif /* INTERPROCEDURAL_VIEW */
947 /*-----------------------------------------------------------*
948 * The core algorithm. *
949 *-----------------------------------------------------------*/
952 static void cgscc(ir_graph *n)
956 if (cg_irg_visited(n)) return;
957 mark_cg_irg_visited(n);
959 /* Initialize the node */
960 set_irg_dfn(n, current_dfn); /* Depth first number for this node */
961 set_irg_uplink(n, current_dfn); /* ... is default uplink. */
965 arity = get_irg_n_callees(n);
966 for (i = 0; i < arity; i++) {
968 if (is_irg_callee_backedge(n, i)) continue;
969 m = get_irg_callee(n, i);
971 /** This marks the backedge, but does it guarantee a correct loop tree? */
972 //if (m == n) { set_irg_callee_backedge(n, i); continue; }
975 if (irg_is_in_stack(m)) {
976 /* Uplink of m is smaller if n->m is a backedge.
977 Propagate the uplink to mark the cfloop. */
978 if (get_irg_uplink(m) < get_irg_uplink(n))
979 set_irg_uplink(n, get_irg_uplink(m));
983 if (get_irg_dfn(n) == get_irg_uplink(n)) {
984 /* This condition holds for
985 1) the node with the incoming backedge.
986 That is: We found a cfloop!
987 2) Straight line code, because no uplink has been propagated, so the
988 uplink still is the same as the dfn.
990 But n might not be a proper cfloop head for the analysis. Proper cfloop
991 heads are Block and Phi nodes. find_tail searches the stack for
992 Block's and Phi's and takes those nodes as cfloop heads for the current
993 cfloop instead and marks the incoming edge as backedge. */
995 ir_graph *tail = find_tail(n);
997 /* We have a cfloop, that is no straight line code,
998 because we found a cfloop head!
999 Next actions: Open a new cfloop on the cfloop tree and
1000 try to find inner cfloops */
1003 ir_loop *l = new_loop();
1005 /* Remove the cfloop from the stack ... */
1006 pop_scc_unmark_visit(n);
1008 /* The current backedge has been marked, that is temporarily eliminated,
1009 by find tail. Start the scc algorithm
1010 anew on the subgraph thats left (the current cfloop without the backedge)
1011 in order to find more inner cfloops. */
1015 assert(cg_irg_visited(n));
1025 * reset the backedge information for all callers in all irgs
1027 static void reset_isbe(void)
1029 int i, n_irgs = get_irp_n_irgs();
1031 for (i = 0; i < n_irgs; ++i) {
1032 ir_graph *irg = get_irp_irg(i);
1034 if (irg->caller_isbe)
1035 xfree(irg->caller_isbe);
1036 irg->caller_isbe = NULL;
1038 if (irg->callee_isbe)
1039 xfree(irg->callee_isbe);
1040 irg->callee_isbe = NULL;
1044 /* ----------------------------------------------------------------------------------- */
1045 /* Another algorithm to compute recursion nesting depth */
1046 /* Walk the callgraph. For each crossed edge increase the loop depth by the edge */
1047 /* weight. Assign graphs the maximal depth. */
1048 /* ----------------------------------------------------------------------------------- */
1050 static void compute_loop_depth(ir_graph *irg, void *env)
1052 int current_nesting = *(int *) env;
1053 int old_nesting = irg->callgraph_loop_depth;
1054 ir_visited_t old_visited = get_cg_irg_visited(irg);
1059 if (cg_irg_visited(irg)) return;
1061 mark_cg_irg_visited(irg);
1063 //printf(" old: %d new %d master %d", old_visited, get_cg_irg_visited(irg), master_cg_visited); DDMG(irg);
1066 if (old_nesting < current_nesting)
1067 irg->callgraph_loop_depth = current_nesting;
1069 if (current_nesting > irp->max_callgraph_loop_depth)
1070 irp->max_callgraph_loop_depth = current_nesting;
1072 if ((old_visited +1 < get_cg_irg_visited(irg)) || /* not yet visited */
1073 (old_nesting < current_nesting)) { /* propagate larger nesting */
1074 /* Don't walk the graph, but a tree that is an unfolded graph. */
1075 n_callees = get_irg_n_callees(irg);
1076 for (i = 0; i < n_callees; i++) {
1077 ir_graph *m = get_irg_callee(irg, i);
1078 *(int *)env += get_irg_callee_loop_depth(irg, i);
1079 compute_loop_depth(m, env);
1080 *(int *)env -= get_irg_callee_loop_depth(irg, i);
1084 set_cg_irg_visited(irg, master_cg_visited-1);
1087 /* ------------------------------------------------------------------------------------ */
1088 /* Another algorithm to compute recursion nesting depth */
1089 /* Walk the callgraph. For each crossed loop increase the nesting depth by one. */
1090 /* Assign graphs the maximal nesting depth. Don't increase if passing loops more than */
1092 /* ------------------------------------------------------------------------------------ */
1095 /* For callees, we want to remember the Call nodes, too. */
1096 typedef struct ana_entry2 {
1097 ir_loop **loop_stack; /**< a stack of ir_loop entries */
1098 int tos; /**< the top of stack entry */
1099 int recursion_nesting;
1103 * push a loop entry on the stack
1105 static void push2(ana_entry2 *e, ir_loop *g)
1107 if (ARR_LEN(e->loop_stack) == e->tos) {
1108 ARR_APP1(ir_loop *, e->loop_stack, g);
1110 e->loop_stack[e->tos] = g;
1116 * returns the top of stack and pop it
1118 static ir_loop *pop2(ana_entry2 *e)
1120 return e->loop_stack[--e->tos];
1124 * check if a loop g in on the stack. Did not check the TOS.
1126 static int in_stack(ana_entry2 *e, ir_loop *g)
1129 for (i = e->tos-1; i >= 0; --i) {
1130 if (e->loop_stack[i] == g) return 1;
1135 static void compute_rec_depth(ir_graph *irg, void *env)
1137 ana_entry2 *e = (ana_entry2 *)env;
1138 ir_loop *l = irg->l;
1139 int depth, old_depth = irg->callgraph_recursion_depth;
1143 if (cg_irg_visited(irg))
1145 mark_cg_irg_visited(irg);
1147 /* -- compute and set the new nesting value -- */
1148 if ((l != irp->outermost_cg_loop) && !in_stack(e, l)) {
1150 e->recursion_nesting++;
1153 depth = e->recursion_nesting;
1155 if (old_depth < depth)
1156 irg->callgraph_recursion_depth = depth;
1158 if (depth > irp->max_callgraph_recursion_depth)
1159 irp->max_callgraph_recursion_depth = depth;
1161 /* -- spread the nesting value -- */
1162 if (depth == 0 || old_depth < depth) {
1163 /* Don't walk the graph, but a tree that is an unfolded graph.
1164 Therefore we unset the visited flag at the end. */
1165 n_callees = get_irg_n_callees(irg);
1166 for (i = 0; i < n_callees; ++i) {
1167 ir_graph *m = get_irg_callee(irg, i);
1168 compute_rec_depth(m, env);
1172 /* -- clean up -- */
1175 e->recursion_nesting--;
1177 set_cg_irg_visited(irg, master_cg_visited-1);
1181 /* ----------------------------------------------------------------------------------- */
1182 /* Another algorithm to compute the execution frequency of methods ignoring recursions. */
1183 /* Walk the callgraph. Ignore backedges. Use sum of execution frequencies of Call */
1184 /* nodes to evaluate a callgraph edge. */
1185 /* ----------------------------------------------------------------------------------- */
1187 /* Returns the method execution frequency of a graph. */
1188 double get_irg_method_execution_frequency(const ir_graph *irg)
1190 return irg->method_execution_frequency;
1194 * Increase the method execution frequency to freq if its current value is
1195 * smaller then this.
1197 static void set_irg_method_execution_frequency(ir_graph *irg, double freq)
1199 irg->method_execution_frequency = freq;
1201 if (irp->max_method_execution_frequency < freq)
1202 irp->max_method_execution_frequency = freq;
1205 static void compute_method_execution_frequency(ir_graph *irg, void *env)
1213 if (cg_irg_visited(irg))
1216 /* We need the values of all predecessors (except backedges).
1217 So they must be marked. Else we will reach the node through
1218 one of the unmarked ones. */
1219 n_callers = get_irg_n_callers(irg);
1220 for (i = 0; i < n_callers; ++i) {
1221 ir_graph *m = get_irg_caller(irg, i);
1222 if (is_irg_caller_backedge(irg, i))
1224 if (!cg_irg_visited(m)) {
1228 mark_cg_irg_visited(irg);
1230 /* Compute the new frequency. */
1233 for (i = 0; i < n_callers; i++) {
1234 if (! is_irg_caller_backedge(irg, i)) {
1235 double edge_freq = get_irg_caller_method_execution_frequency(irg, i);
1236 assert(edge_freq >= 0);
1243 /* A starting point: method only called from outside,
1244 or only backedges as predecessors. */
1248 set_irg_method_execution_frequency(irg, freq);
1251 n_callees = get_irg_n_callees(irg);
1252 for (i = 0; i < n_callees; ++i) {
1253 compute_method_execution_frequency(get_irg_callee(irg, i), NULL);
1258 /* ----------------------------------------------------------------------------------- */
1259 /* The recursion stuff driver. */
1260 /* ----------------------------------------------------------------------------------- */
1262 /* Compute the backedges that represent recursions. */
1263 void find_callgraph_recursions(void)
1266 struct obstack temp;
1270 /* -- compute the looptree. -- */
1272 /* The outermost graph. We start here. Then we start at all
1273 functions in irg list that are never called, then at the remaining
1274 unvisited ones. The third step is needed for functions that are not
1275 reachable from the outermost graph, but call themselves in a cycle. */
1276 assert(get_irp_main_irg());
1277 outermost_ir_graph = get_irp_main_irg();
1278 obstack_init(&temp);
1281 current_loop = NULL;
1282 new_loop(); /* sets current_loop */
1284 ++master_cg_visited;
1285 cgscc(outermost_ir_graph);
1286 n_irgs = get_irp_n_irgs();
1287 for (i = 0; i < n_irgs; ++i) {
1288 ir_graph *irg = get_irp_irg(i);
1289 if (!cg_irg_visited(irg) && get_irg_n_callers(irg) == 0)
1292 for (i = 0; i < n_irgs; ++i) {
1293 ir_graph *irg = get_irp_irg(i);
1294 if (!cg_irg_visited(irg))
1297 obstack_free(&temp, NULL);
1299 irp->outermost_cg_loop = current_loop;
1300 mature_loops(current_loop, outermost_ir_graph->obst);
1302 /* -- Reverse the backedge information. -- */
1303 for (i = 0; i < n_irgs; ++i) {
1304 ir_graph *irg = get_irp_irg(i);
1305 int j, n_callees = get_irg_n_callees(irg);
1306 for (j = 0; j < n_callees; ++j) {
1307 if (is_irg_callee_backedge(irg, j))
1308 set_irg_caller_backedge(get_irg_callee(irg, j), irg);
1312 irp->callgraph_state = irp_callgraph_and_calltree_consistent;
1315 /* Compute interprocedural performance estimates. */
1316 void compute_performance_estimates(void)
1318 int i, n_irgs = get_irp_n_irgs();
1319 int current_nesting;
1322 assert(get_irp_exec_freq_state() != exec_freq_none && "execution frequency not calculated");
1324 /* -- compute the loop depth -- */
1325 current_nesting = 0;
1326 irp->max_callgraph_loop_depth = 0;
1327 master_cg_visited += 2;
1328 //printf(" ** starting at "); DDMG(get_irp_main_irg());
1329 compute_loop_depth(get_irp_main_irg(), ¤t_nesting);
1330 for (i = 0; i < n_irgs; i++) {
1331 ir_graph *irg = get_irp_irg(i);
1332 if ((get_cg_irg_visited(irg) < master_cg_visited-1) &&
1333 get_irg_n_callers(irg) == 0) {
1334 compute_loop_depth(irg, ¤t_nesting);
1335 //printf(" ** starting at "); DDMG(irg);
1338 for (i = 0; i < n_irgs; i++) {
1339 ir_graph *irg = get_irp_irg(i);
1340 if (get_cg_irg_visited(irg) < master_cg_visited-1) {
1341 compute_loop_depth(irg, ¤t_nesting);
1342 //printf(" ** starting at "); DDMG(irg);
1347 /* -- compute the recursion depth -- */
1348 e.loop_stack = NEW_ARR_F(ir_loop *, 0);
1350 e.recursion_nesting = 0;
1352 irp->max_callgraph_recursion_depth = 0;
1354 master_cg_visited += 2;
1355 compute_rec_depth(get_irp_main_irg(), &e);
1356 //printf(" ++ starting at "); DDMG(get_irp_main_irg());
1357 for (i = 0; i < n_irgs; i++) {
1358 ir_graph *irg = get_irp_irg(i);
1359 if ((get_cg_irg_visited(irg) < master_cg_visited-1) &&
1360 get_irg_n_callers(irg) == 0) {
1361 compute_rec_depth(irg, &e);
1362 //printf(" ++ starting at "); DDMG(irg);
1365 for (i = 0; i < n_irgs; i++) {
1366 ir_graph *irg = get_irp_irg(i);
1367 if (get_cg_irg_visited(irg) < master_cg_visited-1) {
1368 compute_rec_depth(irg, &e);
1369 //printf(" ++ starting at "); DDMG(irg);
1373 DEL_ARR_F(e.loop_stack);
1375 /* -- compute the execution frequency -- */
1376 irp->max_method_execution_frequency = 0;
1377 master_cg_visited += 2;
1378 assert(get_irg_n_callers(get_irp_main_irg()) == 0);
1379 compute_method_execution_frequency(get_irp_main_irg(), NULL);
1380 for (i = 0; i < n_irgs; i++) {
1381 ir_graph *irg = get_irp_irg(i);
1382 if ((get_cg_irg_visited(irg) < master_cg_visited-1) &&
1383 get_irg_n_callers(irg) == 0) {
1384 compute_method_execution_frequency(irg, NULL);
1387 for (i = 0; i < n_irgs; i++) {
1388 ir_graph *irg = get_irp_irg(i);
1389 if (get_cg_irg_visited(irg) < master_cg_visited-1) {
1390 compute_method_execution_frequency(irg, NULL);
1395 /* Returns the maximal loop depth of all paths from an external visible method to
1397 int get_irg_loop_depth(const ir_graph *irg)
1399 assert(irp->callgraph_state == irp_callgraph_consistent ||
1400 irp->callgraph_state == irp_callgraph_and_calltree_consistent);
1401 return irg->callgraph_loop_depth;
1404 /* Returns the maximal recursion depth of all paths from an external visible method to
1406 int get_irg_recursion_depth(const ir_graph *irg)
1408 assert(irp->callgraph_state == irp_callgraph_and_calltree_consistent);
1409 return irg->callgraph_recursion_depth;
1412 /* Computes the interprocedural loop nesting information. */
1413 void analyse_loop_nesting_depth(void)
1415 ir_entity **free_methods = NULL;
1418 /* establish preconditions. */
1419 if (get_irp_callee_info_state() != irg_callee_info_consistent) {
1420 cgana(&arr_len, &free_methods);
1423 if (irp_callgraph_consistent != get_irp_callgraph_state()) {
1424 compute_callgraph();
1427 find_callgraph_recursions();
1429 compute_performance_estimates();
1431 set_irp_loop_nesting_depth_state(loop_nesting_depth_consistent);
1434 loop_nesting_depth_state get_irp_loop_nesting_depth_state(void)
1436 return irp->lnd_state;
1438 void set_irp_loop_nesting_depth_state(loop_nesting_depth_state s)
1442 void set_irp_loop_nesting_depth_state_inconsistent(void)
1444 if (irp->lnd_state == loop_nesting_depth_consistent)
1445 irp->lnd_state = loop_nesting_depth_inconsistent;