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 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 size_t 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 = (cg_callee_entry*) 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 = (const cg_callee_entry*) elt;
286 const cg_callee_entry *e2 = (const cg_callee_entry*) 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 = (const ir_graph*) elt;
294 const ir_graph *e2 = (const ir_graph*) key;
299 /* Construct and destruct the callgraph. */
300 void compute_callgraph(void)
307 n_irgs = get_irp_n_irgs();
308 for (i = 0; i < n_irgs; ++i) {
309 ir_graph *irg = get_irp_irg(i);
310 assert(get_irg_callee_info_state(irg) == irg_callee_info_consistent);
311 irg->callees = (cg_callee_entry **)new_pset(cg_callee_entry_cmp, 8);
312 irg->callers = (ir_graph **)new_pset(graph_cmp, 8);
313 //construct_cf_backedges(irg);
316 /* Compute the call graph */
317 for (i = 0; i < n_irgs; ++i) {
318 ir_graph *irg = get_irp_irg(i);
319 construct_cf_backedges(irg); // We also find the maximal loop depth of a call.
320 irg_walk_graph(irg, ana_Call, NULL, NULL);
323 /* Change the sets to arrays. */
324 for (i = 0; i < n_irgs; ++i) {
326 cg_callee_entry *callee;
327 ir_graph *c, *irg = get_irp_irg(i);
328 pset *callee_set, *caller_set;
330 callee_set = (pset *)irg->callees;
331 count = pset_count(callee_set);
332 irg->callees = NEW_ARR_F(cg_callee_entry *, count);
333 irg->callee_isbe = NULL;
334 callee = (cg_callee_entry*) pset_first(callee_set);
335 for (j = 0; j < count; ++j) {
336 irg->callees[j] = callee;
337 callee = (cg_callee_entry*) pset_next(callee_set);
339 del_pset(callee_set);
340 assert(callee == NULL);
342 caller_set = (pset *)irg->callers;
343 count = pset_count(caller_set);
344 irg->callers = NEW_ARR_F(ir_graph *, count);
345 irg->caller_isbe = NULL;
346 c = (ir_graph*) pset_first(caller_set);
347 for (j = 0; j < count; ++j) {
349 c = (ir_graph*) pset_next(caller_set);
351 del_pset(caller_set);
354 set_irp_callgraph_state(irp_callgraph_consistent);
357 /* Destruct the callgraph. */
358 void free_callgraph(void)
360 int i, n_irgs = get_irp_n_irgs();
361 for (i = 0; i < n_irgs; ++i) {
362 ir_graph *irg = get_irp_irg(i);
363 if (irg->callees) DEL_ARR_F(irg->callees);
364 if (irg->callers) DEL_ARR_F(irg->callers);
365 if (irg->callee_isbe) free(irg->callee_isbe);
366 if (irg->caller_isbe) free(irg->caller_isbe);
369 irg->callee_isbe = NULL;
370 irg->caller_isbe = NULL;
372 set_irp_callgraph_state(irp_callgraph_none);
375 /* ----------------------------------------------------------------------------------- */
376 /* A walker for the callgraph */
377 /* ----------------------------------------------------------------------------------- */
380 static void do_walk(ir_graph *irg, callgraph_walk_func *pre, callgraph_walk_func *post, void *env)
384 if (cg_irg_visited(irg))
386 mark_cg_irg_visited(irg);
391 n_callees = get_irg_n_callees(irg);
392 for (i = 0; i < n_callees; i++) {
393 ir_graph *m = get_irg_callee(irg, i);
394 do_walk(m, pre, post, env);
401 void callgraph_walk(callgraph_walk_func *pre, callgraph_walk_func *post, void *env)
403 int i, n_irgs = get_irp_n_irgs();
406 /* roots are methods which have no callers in the current program */
407 for (i = 0; i < n_irgs; ++i) {
408 ir_graph *irg = get_irp_irg(i);
410 if (get_irg_n_callers(irg) == 0)
411 do_walk(irg, pre, post, env);
414 /* in case of unreachable call loops we haven't visited some irgs yet */
415 for (i = 0; i < n_irgs; i++) {
416 ir_graph *irg = get_irp_irg(i);
417 do_walk(irg, pre, post, env);
421 /* ----------------------------------------------------------------------------------- */
422 /* loop construction algorithm */
423 /* ----------------------------------------------------------------------------------- */
425 static ir_graph *outermost_ir_graph; /**< The outermost graph the scc is computed
427 static ir_loop *current_loop; /**< Current cfloop construction is working
429 static int loop_node_cnt = 0; /**< Counts the number of allocated cfloop nodes.
430 Each cfloop node gets a unique number.
431 What for? ev. remove. @@@ */
432 static int current_dfn = 1; /**< Counter to generate depth first numbering
435 /*-----------------*/
436 /* Node attributes */
437 /*-----------------*/
439 typedef struct scc_info {
440 int in_stack; /**< Marks whether node is on the stack. */
441 int dfn; /**< Depth first search number. */
442 int uplink; /**< dfn number of ancestor. */
447 * allocates a new scc_info on the obstack
449 static inline scc_info *new_scc_info(struct obstack *obst)
451 return OALLOCZ(obst, scc_info);
455 * Returns non-zero if a graph was already visited.
457 static inline int cg_irg_visited(ir_graph *irg)
459 return irg->self_visited >= master_cg_visited;
463 * Marks a graph as visited.
465 static inline void mark_cg_irg_visited(ir_graph *irg)
467 irg->self_visited = master_cg_visited;
471 * Set a graphs visited flag to i.
473 static inline void set_cg_irg_visited(ir_graph *irg, ir_visited_t i)
475 irg->self_visited = i;
479 * Returns the visited flag of a graph.
481 static inline ir_visited_t get_cg_irg_visited(ir_graph *irg)
483 return irg->self_visited;
486 static inline void mark_irg_in_stack(ir_graph *irg)
488 scc_info *info = (scc_info*) get_irg_link(irg);
489 assert(info && "missing call to init_scc()");
493 static inline void mark_irg_not_in_stack(ir_graph *irg)
495 scc_info *info = (scc_info*) get_irg_link(irg);
496 assert(info && "missing call to init_scc()");
500 static inline int irg_is_in_stack(ir_graph *irg)
502 scc_info *info = (scc_info*) get_irg_link(irg);
503 assert(info && "missing call to init_scc()");
504 return info->in_stack;
507 static inline void set_irg_uplink(ir_graph *irg, int uplink)
509 scc_info *info = (scc_info*) get_irg_link(irg);
510 assert(info && "missing call to init_scc()");
511 info->uplink = uplink;
514 static inline int get_irg_uplink(ir_graph *irg)
516 scc_info *info = (scc_info*) get_irg_link(irg);
517 assert(info && "missing call to init_scc()");
521 static inline void set_irg_dfn(ir_graph *irg, int dfn)
523 scc_info *info = (scc_info*) get_irg_link(irg);
524 assert(info && "missing call to init_scc()");
528 static inline int get_irg_dfn(ir_graph *irg)
530 scc_info *info = (scc_info*) get_irg_link(irg);
531 assert(info && "missing call to init_scc()");
535 /**********************************************************************/
537 /**********************************************************************/
539 static ir_graph **stack = NULL;
540 static size_t tos = 0; /**< top of stack */
543 * Initialize the irg stack.
545 static inline void init_stack(void)
548 ARR_RESIZE(ir_graph *, stack, 1000);
550 stack = NEW_ARR_F(ir_graph *, 1000);
556 * push a graph on the irg stack
557 * @param n the graph to be pushed
559 static inline void push(ir_graph *irg)
561 if (tos == ARR_LEN(stack)) {
562 size_t nlen = ARR_LEN(stack) * 2;
563 ARR_RESIZE(ir_graph*, stack, nlen);
566 mark_irg_in_stack(irg);
570 * return the topmost graph on the stack and pop it
572 static inline ir_graph *pop(void)
578 mark_irg_not_in_stack(irg);
583 * The nodes up to irg belong to the current loop.
584 * Removes them from the stack and adds them to the current loop.
586 static inline void pop_scc_to_loop(ir_graph *irg)
593 set_irg_dfn(m, loop_node_cnt);
594 add_loop_irg(current_loop, m);
596 //m->callgraph_loop_depth = current_loop->depth;
600 /* GL ??? my last son is my grandson??? Removes cfloops with no
601 ir_nodes in them. Such loops have only another loop as son. (Why
602 can't they have two loops as sons? Does it never get that far? ) */
603 static void close_loop(ir_loop *l)
605 int last = get_loop_n_elements(l) - 1;
606 loop_element lelement = get_loop_element(l, last);
607 ir_loop *last_son = lelement.son;
609 if (get_kind(last_son) == k_ir_loop &&
610 get_loop_n_elements(last_son) == 1) {
613 lelement = get_loop_element(last_son, 0);
615 if (get_kind(gson) == k_ir_loop) {
616 loop_element new_last_son;
618 gson->outer_loop = l;
619 new_last_son.son = gson;
620 l->children[last] = new_last_son;
627 * Removes and unmarks all nodes up to n from the stack.
628 * The nodes must be visited once more to assign them to a scc.
630 static inline void pop_scc_unmark_visit(ir_graph *n)
636 set_cg_irg_visited(m, 0);
640 /**********************************************************************/
641 /* The loop data structure. **/
642 /**********************************************************************/
645 * Allocates a new loop as son of current_loop. Sets current_loop
646 * to the new loop and returns the father.
648 static ir_loop *new_loop(void)
650 ir_loop *father = current_loop;
651 ir_loop *son = alloc_loop(father, outermost_ir_graph->obst);
658 /**********************************************************************/
659 /* Constructing and destructing the loop/backedge information. **/
660 /**********************************************************************/
662 /* Initialization steps. **********************************************/
664 static void init_scc(struct obstack *obst)
673 n_irgs = get_irp_n_irgs();
674 for (i = 0; i < n_irgs; ++i) {
675 ir_graph *irg = get_irp_irg(i);
676 set_irg_link(irg, new_scc_info(obst));
677 irg->callgraph_recursion_depth = 0;
678 irg->callgraph_loop_depth = 0;
682 /** Returns non-zero if n is a loop header, i.e., it is a Block node
683 * and has predecessors within the cfloop and out of the cfloop.
685 * @param root: only needed for assertion.
687 static int is_head(ir_graph *n, ir_graph *root)
690 int some_outof_loop = 0, some_in_loop = 0;
692 arity = get_irg_n_callees(n);
693 for (i = 0; i < arity; i++) {
694 ir_graph *pred = get_irg_callee(n, i);
695 if (is_irg_callee_backedge(n, i)) continue;
696 if (!irg_is_in_stack(pred)) {
699 if (get_irg_uplink(pred) < get_irg_uplink(root)) {
700 assert(get_irg_uplink(pred) >= get_irg_uplink(root));
706 return some_outof_loop && some_in_loop;
710 * Returns non-zero if n is possible loop head of an endless loop.
711 * I.e., it is a Block or Phi node and has only predecessors
713 * @arg root: only needed for assertion.
715 static int is_endless_head(ir_graph *n, ir_graph *root)
718 int some_outof_loop = 0, some_in_loop = 0;
720 arity = get_irg_n_callees(n);
721 for (i = 0; i < arity; i++) {
722 ir_graph *pred = get_irg_callee(n, i);
724 if (is_irg_callee_backedge(n, i))
726 if (!irg_is_in_stack(pred)) {
729 if (get_irg_uplink(pred) < get_irg_uplink(root)) {
730 assert(get_irg_uplink(pred) >= get_irg_uplink(root));
735 return !some_outof_loop && some_in_loop;
739 * Returns index of the predecessor with the smallest dfn number
740 * greater-equal than limit.
742 static int smallest_dfn_pred(ir_graph *n, int limit)
744 int i, index = -2, min = -1;
746 int arity = get_irg_n_callees(n);
747 for (i = 0; i < arity; i++) {
748 ir_graph *pred = get_irg_callee(n, i);
749 if (is_irg_callee_backedge(n, i) || !irg_is_in_stack(pred))
751 if (get_irg_dfn(pred) >= limit && (min == -1 || get_irg_dfn(pred) < min)) {
753 min = get_irg_dfn(pred);
760 /** Returns index of the predecessor with the largest dfn number. */
761 static int largest_dfn_pred(ir_graph *n)
763 int i, index = -2, max = -1;
765 int arity = get_irg_n_callees(n);
766 for (i = 0; i < arity; ++i) {
767 ir_graph *pred = get_irg_callee(n, i);
768 if (is_irg_callee_backedge (n, i) || !irg_is_in_stack(pred)) continue;
769 if (get_irg_dfn(pred) > max) {
771 max = get_irg_dfn(pred);
778 static ir_graph *find_tail(ir_graph *n)
781 int i, res_index = -2;
784 if (!icfg && rm_cyclic_phis && remove_cyclic_phis (n)) return NULL;
786 m = stack[tos-1]; /* tos = top of stack */
787 if (is_head (m, n)) {
788 res_index = smallest_dfn_pred(m, 0);
789 if ((res_index == -2) && /* no smallest dfn pred found. */
793 if (m == n) return NULL; // Is this to catch Phi - self loops?
794 for (i = tos-2; i >= 0; --i) {
798 res_index = smallest_dfn_pred(m, get_irg_dfn(m) + 1);
799 if (res_index == -2) /* no smallest dfn pred found. */
800 res_index = largest_dfn_pred(m);
802 if ((m == n) && (res_index == -2)) {
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-2; i >= 0; --i) {
821 if (is_endless_head(m, n)) {
822 res_index = smallest_dfn_pred(m, get_irg_dfn(m) + 1);
823 if (res_index == -2) /* no smallest dfn pred found. */
824 res_index = largest_dfn_pred(m);
827 if (m == n) { break; } /* It's not an unreachable loop, either. */
829 //assert(0 && "no head found on stack");
833 assert (res_index > -2);
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 arity = get_irg_n_callees(n);
858 for (i = 0; i < arity; 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 int 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 int current_nesting = *(int *) env;
945 int old_nesting = irg->callgraph_loop_depth;
946 ir_visited_t old_visited = get_cg_irg_visited(irg);
951 if (cg_irg_visited(irg)) return;
953 mark_cg_irg_visited(irg);
955 if (old_nesting < current_nesting)
956 irg->callgraph_loop_depth = current_nesting;
958 if (current_nesting > irp->max_callgraph_loop_depth)
959 irp->max_callgraph_loop_depth = current_nesting;
961 if ((old_visited +1 < get_cg_irg_visited(irg)) || /* not yet visited */
962 (old_nesting < current_nesting)) { /* propagate larger nesting */
963 /* Don't walk the graph, but a tree that is an unfolded graph. */
964 n_callees = get_irg_n_callees(irg);
965 for (i = 0; i < n_callees; i++) {
966 ir_graph *m = get_irg_callee(irg, i);
967 *(int *)env += get_irg_callee_loop_depth(irg, i);
968 compute_loop_depth(m, env);
969 *(int *)env -= get_irg_callee_loop_depth(irg, i);
973 set_cg_irg_visited(irg, master_cg_visited-1);
976 /* ------------------------------------------------------------------------------------ */
977 /* Another algorithm to compute recursion nesting depth */
978 /* Walk the callgraph. For each crossed loop increase the nesting depth by one. */
979 /* Assign graphs the maximal nesting depth. Don't increase if passing loops more than */
981 /* ------------------------------------------------------------------------------------ */
984 /* For callees, we want to remember the Call nodes, too. */
985 typedef struct ana_entry2 {
986 ir_loop **loop_stack; /**< a stack of ir_loop entries */
987 size_t tos; /**< the top of stack entry */
988 int recursion_nesting;
992 * push a loop entry on the stack
994 static void push2(ana_entry2 *e, ir_loop *g)
996 if (ARR_LEN(e->loop_stack) == e->tos) {
997 ARR_APP1(ir_loop *, e->loop_stack, g);
999 e->loop_stack[e->tos] = g;
1005 * returns the top of stack and pop it
1007 static ir_loop *pop2(ana_entry2 *e)
1009 return e->loop_stack[--e->tos];
1013 * check if a loop g in on the stack. Did not check the TOS.
1015 static int in_stack(ana_entry2 *e, ir_loop *g)
1018 for (i = e->tos; i != 0;) {
1019 if (e->loop_stack[--i] == g) return 1;
1024 static void compute_rec_depth(ir_graph *irg, void *env)
1026 ana_entry2 *e = (ana_entry2 *)env;
1027 ir_loop *l = irg->l;
1028 int depth, old_depth = irg->callgraph_recursion_depth;
1032 if (cg_irg_visited(irg))
1034 mark_cg_irg_visited(irg);
1036 /* -- compute and set the new nesting value -- */
1037 if ((l != irp->outermost_cg_loop) && !in_stack(e, l)) {
1039 e->recursion_nesting++;
1042 depth = e->recursion_nesting;
1044 if (old_depth < depth)
1045 irg->callgraph_recursion_depth = depth;
1047 if (depth > irp->max_callgraph_recursion_depth)
1048 irp->max_callgraph_recursion_depth = depth;
1050 /* -- spread the nesting value -- */
1051 if (depth == 0 || old_depth < depth) {
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)
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 int 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 int i, n_irgs = get_irp_n_irgs();
1208 int 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 int 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 int 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;