2 * Copyright (C) 1995-2011 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 size_t get_irg_n_callers(const ir_graph *irg)
69 return irg->callers ? ARR_LEN(irg->callers) : 0;
72 /* Returns the caller at position pos. */
73 ir_graph *get_irg_caller(const ir_graph *irg, size_t pos)
75 assert(pos < get_irg_n_callers(irg));
76 return irg->callers ? irg->callers[pos] : NULL;
79 /* Returns non-zero if the caller at position pos is "a backedge", i.e. a recursion. */
80 int is_irg_caller_backedge(const ir_graph *irg, size_t pos)
82 assert(pos < get_irg_n_callers(irg));
83 return irg->caller_isbe != NULL ? rbitset_is_set(irg->caller_isbe, pos) : 0;
86 /** Search the caller in the list of all callers and set its backedge property. */
87 static void set_irg_caller_backedge(ir_graph *irg, const ir_graph *caller)
89 size_t i, n_callers = get_irg_n_callers(irg);
91 /* allocate a new array on demand */
92 if (irg->caller_isbe == NULL)
93 irg->caller_isbe = rbitset_malloc(n_callers);
94 for (i = 0; i < n_callers; ++i) {
95 if (get_irg_caller(irg, i) == caller) {
96 rbitset_set(irg->caller_isbe, i);
102 /* Returns non-zero if the irg has a backedge caller. */
103 int has_irg_caller_backedge(const ir_graph *irg)
105 size_t i, n_callers = get_irg_n_callers(irg);
107 if (irg->caller_isbe != NULL) {
108 for (i = 0; i < n_callers; ++i)
109 if (rbitset_is_set(irg->caller_isbe, i))
116 * Find the reversion position of a caller.
117 * Given the position pos_caller of an caller of irg, return
118 * irg's callee position on that caller.
120 static size_t reverse_pos(const ir_graph *callee, size_t pos_caller)
122 ir_graph *caller = get_irg_caller(callee, pos_caller);
123 /* search the other relation for the corresponding edge. */
124 size_t i, n_callees = get_irg_n_callees(caller);
125 for (i = 0; i < n_callees; ++i) {
126 if (get_irg_callee(caller, i) == callee) {
131 assert(!"reverse_pos() did not find position");
136 /* Returns the maximal loop depth of call nodes that call along this edge. */
137 size_t get_irg_caller_loop_depth(const ir_graph *irg, size_t pos)
139 ir_graph *caller = get_irg_caller(irg, pos);
140 size_t pos_callee = reverse_pos(irg, pos);
142 return get_irg_callee_loop_depth(caller, pos_callee);
146 /* Returns the number of procedures that are called by the given irg. */
147 size_t get_irg_n_callees(const ir_graph *irg)
149 assert(irg->callees);
150 return irg->callees ? ARR_LEN(irg->callees) : 0;
153 /* Returns the callee at position pos. */
154 ir_graph *get_irg_callee(const ir_graph *irg, size_t pos)
156 assert(pos < get_irg_n_callees(irg));
157 return irg->callees ? irg->callees[pos]->irg : NULL;
160 /* Returns non-zero if the callee at position pos is "a backedge", i.e. a recursion. */
161 int is_irg_callee_backedge(const ir_graph *irg, size_t pos)
163 assert(pos < get_irg_n_callees(irg));
164 return irg->callee_isbe != NULL ? rbitset_is_set(irg->callee_isbe, pos) : 0;
167 /* Returns non-zero if the irg has a backedge callee. */
168 int has_irg_callee_backedge(const ir_graph *irg)
170 size_t i, n_callees = get_irg_n_callees(irg);
172 if (irg->callee_isbe != NULL) {
173 for (i = 0; i < n_callees; ++i)
174 if (rbitset_is_set(irg->callee_isbe, i))
181 * Mark the callee at position pos as a backedge.
183 static void set_irg_callee_backedge(ir_graph *irg, size_t pos)
185 size_t n = get_irg_n_callees(irg);
187 /* allocate a new array on demand */
188 if (irg->callee_isbe == NULL)
189 irg->callee_isbe = rbitset_malloc(n);
191 rbitset_set(irg->callee_isbe, pos);
194 /* Returns the maximal loop depth of call nodes that call along this edge. */
195 size_t get_irg_callee_loop_depth(const ir_graph *irg, size_t pos)
197 assert(pos < get_irg_n_callees(irg));
198 return irg->callees ? irg->callees[pos]->max_depth : 0;
201 static double get_irg_callee_execution_frequency(const ir_graph *irg, size_t pos)
203 ir_node **arr = irg->callees[pos]->call_list;
204 size_t i, n_Calls = ARR_LEN(arr);
207 for (i = 0; i < n_Calls; ++i) {
208 freq += get_irn_exec_freq(arr[i]);
213 static double get_irg_callee_method_execution_frequency(const ir_graph *irg,
216 double call_freq = get_irg_callee_execution_frequency(irg, pos);
217 double meth_freq = get_irg_method_execution_frequency(irg);
218 return call_freq * meth_freq;
221 static double get_irg_caller_method_execution_frequency(const ir_graph *irg,
224 ir_graph *caller = get_irg_caller(irg, pos);
225 size_t pos_callee = reverse_pos(irg, pos);
227 return get_irg_callee_method_execution_frequency(caller, pos_callee);
231 /* --------------------- Compute the callgraph ------------------------ */
234 * Pre-Walker called by compute_callgraph(), analyses all Call nodes.
236 static void ana_Call(ir_node *n, void *env)
242 if (! is_Call(n)) return;
244 irg = get_irn_irg(n);
245 n_callees = get_Call_n_callees(n);
246 for (i = 0; i < n_callees; ++i) {
247 ir_entity *callee_e = get_Call_callee(n, i);
248 ir_graph *callee = get_entity_irg(callee_e);
252 cg_callee_entry *found;
257 pset_insert((pset *)callee->callers, irg, HASH_PTR(irg));
258 found = (cg_callee_entry*) pset_find((pset *)irg->callees, &buf, HASH_PTR(callee));
259 if (found) { /* add Call node to list, compute new nesting. */
260 ir_node **arr = found->call_list;
261 ARR_APP1(ir_node *, arr, n);
262 found->call_list = arr;
263 } else { /* New node, add Call node and init nesting. */
264 found = OALLOC(irg->obst, cg_callee_entry);
266 found->call_list = NEW_ARR_F(ir_node *, 1);
267 found->call_list[0] = n;
268 found->max_depth = 0;
269 pset_insert((pset *)irg->callees, found, HASH_PTR(callee));
271 depth = get_loop_depth(get_irn_loop(get_nodes_block(n)));
272 found->max_depth = (depth > found->max_depth) ? depth : found->max_depth;
277 /** compare two ir graphs in a cg_callee_entry */
278 static int cg_callee_entry_cmp(const void *elt, const void *key)
280 const cg_callee_entry *e1 = (const cg_callee_entry*) elt;
281 const cg_callee_entry *e2 = (const cg_callee_entry*) key;
282 return e1->irg != e2->irg;
285 /** compare two ir graphs for pointer identity */
286 static int graph_cmp(const void *elt, const void *key)
288 const ir_graph *e1 = (const ir_graph*) elt;
289 const ir_graph *e2 = (const ir_graph*) key;
294 /* Construct and destruct the callgraph. */
295 void compute_callgraph(void)
302 n_irgs = get_irp_n_irgs();
303 for (i = 0; i < n_irgs; ++i) {
304 ir_graph *irg = get_irp_irg(i);
305 assert(get_irg_callee_info_state(irg) == irg_callee_info_consistent);
306 irg->callees = (cg_callee_entry **)new_pset(cg_callee_entry_cmp, 8);
307 irg->callers = (ir_graph **)new_pset(graph_cmp, 8);
308 //construct_cf_backedges(irg);
311 /* Compute the call graph */
312 for (i = 0; i < n_irgs; ++i) {
313 ir_graph *irg = get_irp_irg(i);
314 construct_cf_backedges(irg); // We also find the maximal loop depth of a call.
315 irg_walk_graph(irg, ana_Call, NULL, NULL);
318 /* Change the sets to arrays. */
319 for (i = 0; i < n_irgs; ++i) {
321 cg_callee_entry *callee;
322 ir_graph *c, *irg = get_irp_irg(i);
323 pset *callee_set, *caller_set;
325 callee_set = (pset *)irg->callees;
326 count = pset_count(callee_set);
327 irg->callees = NEW_ARR_F(cg_callee_entry *, count);
328 irg->callee_isbe = NULL;
329 callee = (cg_callee_entry*) pset_first(callee_set);
330 for (j = 0; j < count; ++j) {
331 irg->callees[j] = callee;
332 callee = (cg_callee_entry*) pset_next(callee_set);
334 del_pset(callee_set);
335 assert(callee == NULL);
337 caller_set = (pset *)irg->callers;
338 count = pset_count(caller_set);
339 irg->callers = NEW_ARR_F(ir_graph *, count);
340 irg->caller_isbe = NULL;
341 c = (ir_graph*) pset_first(caller_set);
342 for (j = 0; j < count; ++j) {
344 c = (ir_graph*) pset_next(caller_set);
346 del_pset(caller_set);
349 set_irp_callgraph_state(irp_callgraph_consistent);
352 /* Destruct the callgraph. */
353 void free_callgraph(void)
355 size_t i, n_irgs = get_irp_n_irgs();
356 for (i = 0; i < n_irgs; ++i) {
357 ir_graph *irg = get_irp_irg(i);
358 if (irg->callees) DEL_ARR_F(irg->callees);
359 if (irg->callers) DEL_ARR_F(irg->callers);
360 if (irg->callee_isbe) free(irg->callee_isbe);
361 if (irg->caller_isbe) free(irg->caller_isbe);
364 irg->callee_isbe = NULL;
365 irg->caller_isbe = NULL;
367 set_irp_callgraph_state(irp_callgraph_none);
370 /* ----------------------------------------------------------------------------------- */
371 /* A walker for the callgraph */
372 /* ----------------------------------------------------------------------------------- */
375 static void do_walk(ir_graph *irg, callgraph_walk_func *pre, callgraph_walk_func *post, void *env)
379 if (cg_irg_visited(irg))
381 mark_cg_irg_visited(irg);
386 n_callees = get_irg_n_callees(irg);
387 for (i = 0; i < n_callees; i++) {
388 ir_graph *m = get_irg_callee(irg, i);
389 do_walk(m, pre, post, env);
396 void callgraph_walk(callgraph_walk_func *pre, callgraph_walk_func *post, void *env)
398 size_t i, n_irgs = get_irp_n_irgs();
401 /* roots are methods which have no callers in the current program */
402 for (i = 0; i < n_irgs; ++i) {
403 ir_graph *irg = get_irp_irg(i);
405 if (get_irg_n_callers(irg) == 0)
406 do_walk(irg, pre, post, env);
409 /* in case of unreachable call loops we haven't visited some irgs yet */
410 for (i = 0; i < n_irgs; i++) {
411 ir_graph *irg = get_irp_irg(i);
412 do_walk(irg, pre, post, env);
416 /* ----------------------------------------------------------------------------------- */
417 /* loop construction algorithm */
418 /* ----------------------------------------------------------------------------------- */
420 static ir_graph *outermost_ir_graph; /**< The outermost graph the scc is computed
422 static ir_loop *current_loop; /**< Current cfloop construction is working
424 static size_t loop_node_cnt = 0; /**< Counts the number of allocated cfloop nodes.
425 Each cfloop node gets a unique number.
426 What for? ev. remove. @@@ */
427 static size_t current_dfn = 1; /**< Counter to generate depth first numbering
430 /*-----------------*/
431 /* Node attributes */
432 /*-----------------*/
434 typedef struct scc_info {
435 size_t dfn; /**< Depth first search number. */
436 size_t uplink; /**< dfn number of ancestor. */
437 ir_visited_t visited; /**< visited counter */
438 int in_stack; /**< Marks whether node is on the stack. */
442 * allocates a new scc_info on the obstack
444 static inline scc_info *new_scc_info(struct obstack *obst)
446 return OALLOCZ(obst, scc_info);
450 * Returns non-zero if a graph was already visited.
452 static inline int cg_irg_visited(ir_graph *irg)
454 return irg->self_visited >= master_cg_visited;
458 * Marks a graph as visited.
460 static inline void mark_cg_irg_visited(ir_graph *irg)
462 irg->self_visited = master_cg_visited;
466 * Set a graphs visited flag to i.
468 static inline void set_cg_irg_visited(ir_graph *irg, ir_visited_t i)
470 irg->self_visited = i;
474 * Returns the visited flag of a graph.
476 static inline ir_visited_t get_cg_irg_visited(const ir_graph *irg)
478 return irg->self_visited;
481 static inline void mark_irg_in_stack(ir_graph *irg)
483 scc_info *info = (scc_info*) get_irg_link(irg);
484 assert(info && "missing call to init_scc()");
488 static inline void mark_irg_not_in_stack(ir_graph *irg)
490 scc_info *info = (scc_info*) get_irg_link(irg);
491 assert(info && "missing call to init_scc()");
495 static inline int irg_is_in_stack(const ir_graph *irg)
497 scc_info *info = (scc_info*) get_irg_link(irg);
498 assert(info && "missing call to init_scc()");
499 return info->in_stack;
502 static inline void set_irg_uplink(ir_graph *irg, size_t uplink)
504 scc_info *info = (scc_info*) get_irg_link(irg);
505 assert(info && "missing call to init_scc()");
506 info->uplink = uplink;
509 static inline size_t get_irg_uplink(const ir_graph *irg)
511 const scc_info *info = (scc_info*) get_irg_link(irg);
512 assert(info && "missing call to init_scc()");
516 static inline void set_irg_dfn(ir_graph *irg, size_t dfn)
518 scc_info *info = (scc_info*) get_irg_link(irg);
519 assert(info && "missing call to init_scc()");
523 static inline size_t get_irg_dfn(const ir_graph *irg)
525 const scc_info *info = (scc_info*) get_irg_link(irg);
526 assert(info && "missing call to init_scc()");
530 /**********************************************************************/
532 /**********************************************************************/
534 static ir_graph **stack = NULL;
535 static size_t tos = 0; /**< top of stack */
538 * Initialize the irg stack.
540 static inline void init_stack(void)
543 ARR_RESIZE(ir_graph *, stack, 1000);
545 stack = NEW_ARR_F(ir_graph *, 1000);
551 * push a graph on the irg stack
552 * @param n the graph to be pushed
554 static inline void push(ir_graph *irg)
556 if (tos == ARR_LEN(stack)) {
557 size_t nlen = ARR_LEN(stack) * 2;
558 ARR_RESIZE(ir_graph*, stack, nlen);
561 mark_irg_in_stack(irg);
565 * return the topmost graph on the stack and pop it
567 static inline ir_graph *pop(void)
573 mark_irg_not_in_stack(irg);
578 * The nodes up to irg belong to the current loop.
579 * Removes them from the stack and adds them to the current loop.
581 static inline void pop_scc_to_loop(ir_graph *irg)
588 set_irg_dfn(m, loop_node_cnt);
589 add_loop_irg(current_loop, m);
591 //m->callgraph_loop_depth = current_loop->depth;
595 /* GL ??? my last son is my grandson??? Removes cfloops with no
596 ir_nodes in them. Such loops have only another loop as son. (Why
597 can't they have two loops as sons? Does it never get that far? ) */
598 static void close_loop(ir_loop *l)
600 size_t last = get_loop_n_elements(l) - 1;
601 loop_element lelement = get_loop_element(l, last);
602 ir_loop *last_son = lelement.son;
604 if (get_kind(last_son) == k_ir_loop &&
605 get_loop_n_elements(last_son) == 1) {
608 lelement = get_loop_element(last_son, 0);
610 if (get_kind(gson) == k_ir_loop) {
611 loop_element new_last_son;
613 gson->outer_loop = l;
614 new_last_son.son = gson;
615 l->children[last] = new_last_son;
622 * Removes and unmarks all nodes up to n from the stack.
623 * The nodes must be visited once more to assign them to a scc.
625 static inline void pop_scc_unmark_visit(ir_graph *n)
631 set_cg_irg_visited(m, 0);
635 /**********************************************************************/
636 /* The loop data structure. **/
637 /**********************************************************************/
640 * Allocates a new loop as son of current_loop. Sets current_loop
641 * to the new loop and returns the father.
643 static ir_loop *new_loop(void)
645 ir_loop *father = current_loop;
646 ir_loop *son = alloc_loop(father, outermost_ir_graph->obst);
653 /**********************************************************************/
654 /* Constructing and destructing the loop/backedge information. **/
655 /**********************************************************************/
657 /* Initialization steps. **********************************************/
659 static void init_scc(struct obstack *obst)
667 n_irgs = get_irp_n_irgs();
668 for (i = 0; i < n_irgs; ++i) {
669 ir_graph *irg = get_irp_irg(i);
670 set_irg_link(irg, new_scc_info(obst));
671 irg->callgraph_recursion_depth = 0;
672 irg->callgraph_loop_depth = 0;
676 /** Returns non-zero if n is a loop header, i.e., it is a Block node
677 * and has predecessors within the cfloop and out of the cfloop.
679 * @param root: only needed for assertion.
681 static int is_head(const ir_graph *n, const ir_graph *root)
684 int some_outof_loop = 0, some_in_loop = 0;
686 n_callees = get_irg_n_callees(n);
687 for (i = 0; i < n_callees; ++i) {
688 const ir_graph *pred = get_irg_callee(n, i);
689 if (is_irg_callee_backedge(n, i)) continue;
690 if (!irg_is_in_stack(pred)) {
693 if (get_irg_uplink(pred) < get_irg_uplink(root)) {
694 assert(get_irg_uplink(pred) >= get_irg_uplink(root));
700 return some_outof_loop && some_in_loop;
704 * Returns non-zero if n is possible loop head of an endless loop.
705 * I.e., it is a Block or Phi node and has only predecessors
707 * @arg root: only needed for assertion.
709 static int is_endless_head(const ir_graph *n, const ir_graph *root)
712 int some_outof_loop = 0, some_in_loop = 0;
714 n_calless = get_irg_n_callees(n);
715 for (i = 0; i < n_calless; ++i) {
716 const ir_graph *pred = get_irg_callee(n, i);
718 if (is_irg_callee_backedge(n, i))
720 if (!irg_is_in_stack(pred)) {
723 if (get_irg_uplink(pred) < get_irg_uplink(root)) {
724 assert(get_irg_uplink(pred) >= get_irg_uplink(root));
729 return !some_outof_loop && some_in_loop;
733 * Finds index of the predecessor with the smallest dfn number
734 * greater-equal than limit.
736 static bool smallest_dfn_pred(const ir_graph *n, size_t limit, size_t *result)
738 size_t index = 0, min = 0;
741 size_t i, n_callees = get_irg_n_callees(n);
742 for (i = 0; i < n_callees; ++i) {
743 const ir_graph *pred = get_irg_callee(n, i);
744 if (is_irg_callee_backedge(n, i) || !irg_is_in_stack(pred))
746 if (get_irg_dfn(pred) >= limit && (!found || get_irg_dfn(pred) < min)) {
748 min = get_irg_dfn(pred);
757 /** Finds index of the predecessor with the largest dfn number. */
758 static bool largest_dfn_pred(const ir_graph *n, size_t *result)
760 size_t index = 0, max = 0;
763 size_t i, n_callees = get_irg_n_callees(n);
764 for (i = 0; i < n_callees; ++i) {
765 const ir_graph *pred = get_irg_callee(n, i);
766 if (is_irg_callee_backedge (n, i) || !irg_is_in_stack(pred))
768 /* Note: dfn is always > 0 */
769 if (get_irg_dfn(pred) > max) {
771 max = get_irg_dfn(pred);
780 static ir_graph *find_tail(const ir_graph *n)
787 if (!icfg && rm_cyclic_phis && remove_cyclic_phis (n)) return NULL;
789 m = stack[tos - 1]; /* tos = top of stack */
791 found = smallest_dfn_pred(m, 0, &res_index);
792 if (!found && /* no smallest dfn pred found. */
796 if (m == n) return NULL; // Is this to catch Phi - self loops?
797 for (i = tos - 1; i > 0;) {
801 found = smallest_dfn_pred(m, get_irg_dfn(m) + 1, &res_index);
802 if (! found) /* no smallest dfn pred found. */
803 found = largest_dfn_pred(m, &res_index);
808 /* We should not walk past our selves on the stack: The upcoming nodes
809 are not in this loop. We assume a loop not reachable from Start. */
818 /* A dead loop not reachable from Start. */
819 for (i = tos-1; i > 0;) {
821 if (is_endless_head(m, n)) {
822 found = smallest_dfn_pred(m, get_irg_dfn(m) + 1, &res_index);
823 if (!found) /* no smallest dfn pred found. */
824 found = largest_dfn_pred(m, &res_index);
827 if (m == n) { break; } /* It's not an unreachable loop, either. */
829 //assert(0 && "no head found on stack");
835 set_irg_callee_backedge(m, res_index);
836 return get_irg_callee(m, res_index);
839 /*-----------------------------------------------------------*
840 * The core algorithm. *
841 *-----------------------------------------------------------*/
844 static void cgscc(ir_graph *n)
848 if (cg_irg_visited(n)) return;
849 mark_cg_irg_visited(n);
851 /* Initialize the node */
852 set_irg_dfn(n, current_dfn); /* Depth first number for this node */
853 set_irg_uplink(n, current_dfn); /* ... is default uplink. */
857 n_callees = get_irg_n_callees(n);
858 for (i = 0; i < n_callees; ++i) {
860 if (is_irg_callee_backedge(n, i)) continue;
861 m = get_irg_callee(n, i);
863 /** This marks the backedge, but does it guarantee a correct loop tree? */
864 //if (m == n) { set_irg_callee_backedge(n, i); continue; }
867 if (irg_is_in_stack(m)) {
868 /* Uplink of m is smaller if n->m is a backedge.
869 Propagate the uplink to mark the cfloop. */
870 if (get_irg_uplink(m) < get_irg_uplink(n))
871 set_irg_uplink(n, get_irg_uplink(m));
875 if (get_irg_dfn(n) == get_irg_uplink(n)) {
876 /* This condition holds for
877 1) the node with the incoming backedge.
878 That is: We found a cfloop!
879 2) Straight line code, because no uplink has been propagated, so the
880 uplink still is the same as the dfn.
882 But n might not be a proper cfloop head for the analysis. Proper cfloop
883 heads are Block and Phi nodes. find_tail searches the stack for
884 Block's and Phi's and takes those nodes as cfloop heads for the current
885 cfloop instead and marks the incoming edge as backedge. */
887 ir_graph *tail = find_tail(n);
889 /* We have a cfloop, that is no straight line code,
890 because we found a cfloop head!
891 Next actions: Open a new cfloop on the cfloop tree and
892 try to find inner cfloops */
895 ir_loop *l = new_loop();
897 /* Remove the cfloop from the stack ... */
898 pop_scc_unmark_visit(n);
900 /* The current backedge has been marked, that is temporarily eliminated,
901 by find tail. Start the scc algorithm
902 anew on the subgraph thats left (the current cfloop without the backedge)
903 in order to find more inner cfloops. */
907 assert(cg_irg_visited(n));
917 * reset the backedge information for all callers in all irgs
919 static void reset_isbe(void)
921 size_t i, n_irgs = get_irp_n_irgs();
923 for (i = 0; i < n_irgs; ++i) {
924 ir_graph *irg = get_irp_irg(i);
926 if (irg->caller_isbe)
927 xfree(irg->caller_isbe);
928 irg->caller_isbe = NULL;
930 if (irg->callee_isbe)
931 xfree(irg->callee_isbe);
932 irg->callee_isbe = NULL;
936 /* ----------------------------------------------------------------------------------- */
937 /* Another algorithm to compute recursion nesting depth */
938 /* Walk the callgraph. For each crossed edge increase the loop depth by the edge */
939 /* weight. Assign graphs the maximal depth. */
940 /* ----------------------------------------------------------------------------------- */
942 static void compute_loop_depth(ir_graph *irg, void *env)
944 size_t current_nesting = *(size_t *) env;
945 size_t old_nesting = irg->callgraph_loop_depth;
946 ir_visited_t old_visited = get_cg_irg_visited(irg);
948 if (cg_irg_visited(irg)) return;
950 mark_cg_irg_visited(irg);
952 if (old_nesting < current_nesting)
953 irg->callgraph_loop_depth = current_nesting;
955 if (current_nesting > irp->max_callgraph_loop_depth)
956 irp->max_callgraph_loop_depth = current_nesting;
958 if ((old_visited +1 < get_cg_irg_visited(irg)) || /* not yet visited */
959 (old_nesting < current_nesting)) { /* propagate larger nesting */
962 /* Don't walk the graph, but a tree that is an unfolded graph. */
963 n_callees = get_irg_n_callees(irg);
964 for (i = 0; i < n_callees; ++i) {
965 ir_graph *m = get_irg_callee(irg, i);
966 *(size_t *)env += get_irg_callee_loop_depth(irg, i);
967 compute_loop_depth(m, env);
968 *(size_t *)env -= get_irg_callee_loop_depth(irg, i);
972 set_cg_irg_visited(irg, master_cg_visited-1);
975 /* ------------------------------------------------------------------------------------ */
976 /* Another algorithm to compute recursion nesting depth */
977 /* Walk the callgraph. For each crossed loop increase the nesting depth by one. */
978 /* Assign graphs the maximal nesting depth. Don't increase if passing loops more than */
980 /* ------------------------------------------------------------------------------------ */
983 /* For callees, we want to remember the Call nodes, too. */
984 typedef struct ana_entry2 {
985 ir_loop **loop_stack; /**< a stack of ir_loop entries */
986 size_t tos; /**< the top of stack entry */
987 size_t recursion_nesting;
991 * push a loop entry on the stack
993 static void push2(ana_entry2 *e, ir_loop *g)
995 if (ARR_LEN(e->loop_stack) == e->tos) {
996 ARR_APP1(ir_loop *, e->loop_stack, g);
998 e->loop_stack[e->tos] = g;
1004 * returns the top of stack and pop it
1006 static ir_loop *pop2(ana_entry2 *e)
1008 return e->loop_stack[--e->tos];
1012 * check if a loop g in on the stack. Did not check the TOS.
1014 static int in_stack(ana_entry2 *e, ir_loop *g)
1017 for (i = e->tos; i != 0;) {
1018 if (e->loop_stack[--i] == g) return 1;
1023 static void compute_rec_depth(ir_graph *irg, void *env)
1025 ana_entry2 *e = (ana_entry2 *)env;
1026 ir_loop *l = irg->l;
1027 size_t depth, old_depth = irg->callgraph_recursion_depth;
1030 if (cg_irg_visited(irg))
1032 mark_cg_irg_visited(irg);
1034 /* -- compute and set the new nesting value -- */
1035 if ((l != irp->outermost_cg_loop) && !in_stack(e, l)) {
1037 ++e->recursion_nesting;
1040 depth = e->recursion_nesting;
1042 if (old_depth < depth)
1043 irg->callgraph_recursion_depth = depth;
1045 if (depth > irp->max_callgraph_recursion_depth)
1046 irp->max_callgraph_recursion_depth = depth;
1048 /* -- spread the nesting value -- */
1049 if (depth == 0 || old_depth < depth) {
1050 size_t i, n_callees;
1052 /* Don't walk the graph, but a tree that is an unfolded graph.
1053 Therefore we unset the visited flag at the end. */
1054 n_callees = get_irg_n_callees(irg);
1055 for (i = 0; i < n_callees; ++i) {
1056 ir_graph *m = get_irg_callee(irg, i);
1057 compute_rec_depth(m, env);
1061 /* -- clean up -- */
1064 --e->recursion_nesting;
1066 set_cg_irg_visited(irg, master_cg_visited-1);
1070 /* ----------------------------------------------------------------------------------- */
1071 /* Another algorithm to compute the execution frequency of methods ignoring recursions. */
1072 /* Walk the callgraph. Ignore backedges. Use sum of execution frequencies of Call */
1073 /* nodes to evaluate a callgraph edge. */
1074 /* ----------------------------------------------------------------------------------- */
1076 /* Returns the method execution frequency of a graph. */
1077 double get_irg_method_execution_frequency(const ir_graph *irg)
1079 return irg->method_execution_frequency;
1083 * Increase the method execution frequency to freq if its current value is
1084 * smaller then this.
1086 static void set_irg_method_execution_frequency(ir_graph *irg, double freq)
1088 irg->method_execution_frequency = freq;
1090 if (irp->max_method_execution_frequency < freq)
1091 irp->max_method_execution_frequency = freq;
1094 static void compute_method_execution_frequency(ir_graph *irg, void *env)
1096 size_t i, n_callers;
1102 if (cg_irg_visited(irg))
1105 /* We need the values of all predecessors (except backedges).
1106 So they must be marked. Else we will reach the node through
1107 one of the unmarked ones. */
1108 n_callers = get_irg_n_callers(irg);
1109 for (i = 0; i < n_callers; ++i) {
1110 ir_graph *m = get_irg_caller(irg, i);
1111 if (is_irg_caller_backedge(irg, i))
1113 if (!cg_irg_visited(m)) {
1117 mark_cg_irg_visited(irg);
1119 /* Compute the new frequency. */
1122 for (i = 0; i < n_callers; ++i) {
1123 if (! is_irg_caller_backedge(irg, i)) {
1124 double edge_freq = get_irg_caller_method_execution_frequency(irg, i);
1125 assert(edge_freq >= 0);
1132 /* A starting point: method only called from outside,
1133 or only backedges as predecessors. */
1137 set_irg_method_execution_frequency(irg, freq);
1140 n_callees = get_irg_n_callees(irg);
1141 for (i = 0; i < n_callees; ++i) {
1142 compute_method_execution_frequency(get_irg_callee(irg, i), NULL);
1147 /* ----------------------------------------------------------------------------------- */
1148 /* The recursion stuff driver. */
1149 /* ----------------------------------------------------------------------------------- */
1151 /* Compute the backedges that represent recursions. */
1152 void find_callgraph_recursions(void)
1155 struct obstack temp;
1159 /* -- compute the looptree. -- */
1161 /* The outermost graph. We start here. Then we start at all
1162 functions in irg list that are never called, then at the remaining
1163 unvisited ones. The third step is needed for functions that are not
1164 reachable from the outermost graph, but call themselves in a cycle. */
1165 assert(get_irp_main_irg());
1166 outermost_ir_graph = get_irp_main_irg();
1167 obstack_init(&temp);
1170 current_loop = NULL;
1171 new_loop(); /* sets current_loop */
1173 ++master_cg_visited;
1174 cgscc(outermost_ir_graph);
1175 n_irgs = get_irp_n_irgs();
1176 for (i = 0; i < n_irgs; ++i) {
1177 ir_graph *irg = get_irp_irg(i);
1178 if (!cg_irg_visited(irg) && get_irg_n_callers(irg) == 0)
1181 for (i = 0; i < n_irgs; ++i) {
1182 ir_graph *irg = get_irp_irg(i);
1183 if (!cg_irg_visited(irg))
1186 obstack_free(&temp, NULL);
1188 irp->outermost_cg_loop = current_loop;
1189 mature_loops(current_loop, outermost_ir_graph->obst);
1191 /* -- Reverse the backedge information. -- */
1192 for (i = 0; i < n_irgs; ++i) {
1193 ir_graph *irg = get_irp_irg(i);
1194 size_t j, n_callees = get_irg_n_callees(irg);
1195 for (j = 0; j < n_callees; ++j) {
1196 if (is_irg_callee_backedge(irg, j))
1197 set_irg_caller_backedge(get_irg_callee(irg, j), irg);
1201 irp->callgraph_state = irp_callgraph_and_calltree_consistent;
1204 /* Compute interprocedural performance estimates. */
1205 void compute_performance_estimates(void)
1207 size_t i, n_irgs = get_irp_n_irgs();
1208 size_t current_nesting;
1211 assert(get_irp_exec_freq_state() != exec_freq_none && "execution frequency not calculated");
1213 /* -- compute the loop depth -- */
1214 current_nesting = 0;
1215 irp->max_callgraph_loop_depth = 0;
1216 master_cg_visited += 2;
1217 compute_loop_depth(get_irp_main_irg(), ¤t_nesting);
1218 for (i = 0; i < n_irgs; ++i) {
1219 ir_graph *irg = get_irp_irg(i);
1220 if ((get_cg_irg_visited(irg) < master_cg_visited-1) &&
1221 get_irg_n_callers(irg) == 0) {
1222 compute_loop_depth(irg, ¤t_nesting);
1225 for (i = 0; i < n_irgs; ++i) {
1226 ir_graph *irg = get_irp_irg(i);
1227 if (get_cg_irg_visited(irg) < master_cg_visited-1) {
1228 compute_loop_depth(irg, ¤t_nesting);
1233 /* -- compute the recursion depth -- */
1234 e.loop_stack = NEW_ARR_F(ir_loop *, 0);
1236 e.recursion_nesting = 0;
1238 irp->max_callgraph_recursion_depth = 0;
1240 master_cg_visited += 2;
1241 compute_rec_depth(get_irp_main_irg(), &e);
1242 for (i = 0; i < n_irgs; ++i) {
1243 ir_graph *irg = get_irp_irg(i);
1244 if ((get_cg_irg_visited(irg) < master_cg_visited-1) &&
1245 get_irg_n_callers(irg) == 0) {
1246 compute_rec_depth(irg, &e);
1249 for (i = 0; i < n_irgs; ++i) {
1250 ir_graph *irg = get_irp_irg(i);
1251 if (get_cg_irg_visited(irg) < master_cg_visited-1) {
1252 compute_rec_depth(irg, &e);
1256 DEL_ARR_F(e.loop_stack);
1258 /* -- compute the execution frequency -- */
1259 irp->max_method_execution_frequency = 0;
1260 master_cg_visited += 2;
1261 assert(get_irg_n_callers(get_irp_main_irg()) == 0);
1262 compute_method_execution_frequency(get_irp_main_irg(), NULL);
1263 for (i = 0; i < n_irgs; ++i) {
1264 ir_graph *irg = get_irp_irg(i);
1265 if ((get_cg_irg_visited(irg) < master_cg_visited-1) &&
1266 get_irg_n_callers(irg) == 0) {
1267 compute_method_execution_frequency(irg, NULL);
1270 for (i = 0; i < n_irgs; ++i) {
1271 ir_graph *irg = get_irp_irg(i);
1272 if (get_cg_irg_visited(irg) < master_cg_visited-1) {
1273 compute_method_execution_frequency(irg, NULL);
1278 /* Returns the maximal loop depth of all paths from an external visible method to
1280 size_t get_irg_loop_depth(const ir_graph *irg)
1282 assert(irp->callgraph_state == irp_callgraph_consistent ||
1283 irp->callgraph_state == irp_callgraph_and_calltree_consistent);
1284 return irg->callgraph_loop_depth;
1287 /* Returns the maximal recursion depth of all paths from an external visible method to
1289 size_t get_irg_recursion_depth(const ir_graph *irg)
1291 assert(irp->callgraph_state == irp_callgraph_and_calltree_consistent);
1292 return irg->callgraph_recursion_depth;
1295 /* Computes the interprocedural loop nesting information. */
1296 void analyse_loop_nesting_depth(void)
1298 /* establish preconditions. */
1299 if (get_irp_callee_info_state() != irg_callee_info_consistent) {
1300 ir_entity **free_methods = NULL;
1302 cgana(&free_methods);
1303 xfree(free_methods);
1306 if (irp_callgraph_consistent != get_irp_callgraph_state()) {
1307 compute_callgraph();
1310 find_callgraph_recursions();
1312 compute_performance_estimates();
1314 set_irp_loop_nesting_depth_state(loop_nesting_depth_consistent);
1317 loop_nesting_depth_state get_irp_loop_nesting_depth_state(void)
1319 return irp->lnd_state;
1321 void set_irp_loop_nesting_depth_state(loop_nesting_depth_state s)
1325 void set_irp_loop_nesting_depth_state_inconsistent(void)
1327 if (irp->lnd_state == loop_nesting_depth_consistent)
1328 irp->lnd_state = loop_nesting_depth_inconsistent;