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 size_t 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 size_t 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)
672 n_irgs = get_irp_n_irgs();
673 for (i = 0; i < n_irgs; ++i) {
674 ir_graph *irg = get_irp_irg(i);
675 set_irg_link(irg, new_scc_info(obst));
676 irg->callgraph_recursion_depth = 0;
677 irg->callgraph_loop_depth = 0;
681 /** Returns non-zero if n is a loop header, i.e., it is a Block node
682 * and has predecessors within the cfloop and out of the cfloop.
684 * @param root: only needed for assertion.
686 static int is_head(ir_graph *n, ir_graph *root)
689 int some_outof_loop = 0, some_in_loop = 0;
691 arity = get_irg_n_callees(n);
692 for (i = 0; i < arity; i++) {
693 ir_graph *pred = get_irg_callee(n, i);
694 if (is_irg_callee_backedge(n, i)) continue;
695 if (!irg_is_in_stack(pred)) {
698 if (get_irg_uplink(pred) < get_irg_uplink(root)) {
699 assert(get_irg_uplink(pred) >= get_irg_uplink(root));
705 return some_outof_loop && some_in_loop;
709 * Returns non-zero if n is possible loop head of an endless loop.
710 * I.e., it is a Block or Phi node and has only predecessors
712 * @arg root: only needed for assertion.
714 static int is_endless_head(ir_graph *n, ir_graph *root)
717 int some_outof_loop = 0, some_in_loop = 0;
719 arity = get_irg_n_callees(n);
720 for (i = 0; i < arity; i++) {
721 ir_graph *pred = get_irg_callee(n, i);
723 if (is_irg_callee_backedge(n, i))
725 if (!irg_is_in_stack(pred)) {
728 if (get_irg_uplink(pred) < get_irg_uplink(root)) {
729 assert(get_irg_uplink(pred) >= get_irg_uplink(root));
734 return !some_outof_loop && some_in_loop;
738 * Returns index of the predecessor with the smallest dfn number
739 * greater-equal than limit.
741 static int smallest_dfn_pred(ir_graph *n, int limit)
743 int i, index = -2, min = -1;
745 int arity = get_irg_n_callees(n);
746 for (i = 0; i < arity; i++) {
747 ir_graph *pred = get_irg_callee(n, i);
748 if (is_irg_callee_backedge(n, i) || !irg_is_in_stack(pred))
750 if (get_irg_dfn(pred) >= limit && (min == -1 || get_irg_dfn(pred) < min)) {
752 min = get_irg_dfn(pred);
759 /** Returns index of the predecessor with the largest dfn number. */
760 static int largest_dfn_pred(ir_graph *n)
762 int i, index = -2, max = -1;
764 int arity = get_irg_n_callees(n);
765 for (i = 0; i < arity; ++i) {
766 ir_graph *pred = get_irg_callee(n, i);
767 if (is_irg_callee_backedge (n, i) || !irg_is_in_stack(pred)) continue;
768 if (get_irg_dfn(pred) > max) {
770 max = get_irg_dfn(pred);
777 static ir_graph *find_tail(ir_graph *n)
780 int i, res_index = -2;
783 if (!icfg && rm_cyclic_phis && remove_cyclic_phis (n)) return NULL;
785 m = stack[tos-1]; /* tos = top of stack */
786 if (is_head (m, n)) {
787 res_index = smallest_dfn_pred(m, 0);
788 if ((res_index == -2) && /* no smallest dfn pred found. */
792 if (m == n) return NULL; // Is this to catch Phi - self loops?
793 for (i = tos-2; i >= 0; --i) {
797 res_index = smallest_dfn_pred(m, get_irg_dfn(m) + 1);
798 if (res_index == -2) /* no smallest dfn pred found. */
799 res_index = largest_dfn_pred(m);
801 if ((m == n) && (res_index == -2)) {
807 /* We should not walk past our selves on the stack: The upcoming nodes
808 are not in this loop. We assume a loop not reachable from Start. */
817 /* A dead loop not reachable from Start. */
818 for (i = tos-2; i >= 0; --i) {
820 if (is_endless_head(m, n)) {
821 res_index = smallest_dfn_pred(m, get_irg_dfn(m) + 1);
822 if (res_index == -2) /* no smallest dfn pred found. */
823 res_index = largest_dfn_pred(m);
826 if (m == n) { break; } /* It's not an unreachable loop, either. */
828 //assert(0 && "no head found on stack");
832 assert (res_index > -2);
834 set_irg_callee_backedge(m, res_index);
835 return get_irg_callee(m, res_index);
838 /*-----------------------------------------------------------*
839 * The core algorithm. *
840 *-----------------------------------------------------------*/
843 static void cgscc(ir_graph *n)
847 if (cg_irg_visited(n)) return;
848 mark_cg_irg_visited(n);
850 /* Initialize the node */
851 set_irg_dfn(n, current_dfn); /* Depth first number for this node */
852 set_irg_uplink(n, current_dfn); /* ... is default uplink. */
856 arity = get_irg_n_callees(n);
857 for (i = 0; i < arity; i++) {
859 if (is_irg_callee_backedge(n, i)) continue;
860 m = get_irg_callee(n, i);
862 /** This marks the backedge, but does it guarantee a correct loop tree? */
863 //if (m == n) { set_irg_callee_backedge(n, i); continue; }
866 if (irg_is_in_stack(m)) {
867 /* Uplink of m is smaller if n->m is a backedge.
868 Propagate the uplink to mark the cfloop. */
869 if (get_irg_uplink(m) < get_irg_uplink(n))
870 set_irg_uplink(n, get_irg_uplink(m));
874 if (get_irg_dfn(n) == get_irg_uplink(n)) {
875 /* This condition holds for
876 1) the node with the incoming backedge.
877 That is: We found a cfloop!
878 2) Straight line code, because no uplink has been propagated, so the
879 uplink still is the same as the dfn.
881 But n might not be a proper cfloop head for the analysis. Proper cfloop
882 heads are Block and Phi nodes. find_tail searches the stack for
883 Block's and Phi's and takes those nodes as cfloop heads for the current
884 cfloop instead and marks the incoming edge as backedge. */
886 ir_graph *tail = find_tail(n);
888 /* We have a cfloop, that is no straight line code,
889 because we found a cfloop head!
890 Next actions: Open a new cfloop on the cfloop tree and
891 try to find inner cfloops */
894 ir_loop *l = new_loop();
896 /* Remove the cfloop from the stack ... */
897 pop_scc_unmark_visit(n);
899 /* The current backedge has been marked, that is temporarily eliminated,
900 by find tail. Start the scc algorithm
901 anew on the subgraph thats left (the current cfloop without the backedge)
902 in order to find more inner cfloops. */
906 assert(cg_irg_visited(n));
916 * reset the backedge information for all callers in all irgs
918 static void reset_isbe(void)
920 size_t i, n_irgs = get_irp_n_irgs();
922 for (i = 0; i < n_irgs; ++i) {
923 ir_graph *irg = get_irp_irg(i);
925 if (irg->caller_isbe)
926 xfree(irg->caller_isbe);
927 irg->caller_isbe = NULL;
929 if (irg->callee_isbe)
930 xfree(irg->callee_isbe);
931 irg->callee_isbe = NULL;
935 /* ----------------------------------------------------------------------------------- */
936 /* Another algorithm to compute recursion nesting depth */
937 /* Walk the callgraph. For each crossed edge increase the loop depth by the edge */
938 /* weight. Assign graphs the maximal depth. */
939 /* ----------------------------------------------------------------------------------- */
941 static void compute_loop_depth(ir_graph *irg, void *env)
943 int current_nesting = *(int *) env;
944 int old_nesting = irg->callgraph_loop_depth;
945 ir_visited_t old_visited = get_cg_irg_visited(irg);
950 if (cg_irg_visited(irg)) return;
952 mark_cg_irg_visited(irg);
954 if (old_nesting < current_nesting)
955 irg->callgraph_loop_depth = current_nesting;
957 if (current_nesting > irp->max_callgraph_loop_depth)
958 irp->max_callgraph_loop_depth = current_nesting;
960 if ((old_visited +1 < get_cg_irg_visited(irg)) || /* not yet visited */
961 (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 *(int *)env += get_irg_callee_loop_depth(irg, i);
967 compute_loop_depth(m, env);
968 *(int *)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 int 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 int depth, old_depth = irg->callgraph_recursion_depth;
1031 if (cg_irg_visited(irg))
1033 mark_cg_irg_visited(irg);
1035 /* -- compute and set the new nesting value -- */
1036 if ((l != irp->outermost_cg_loop) && !in_stack(e, l)) {
1038 e->recursion_nesting++;
1041 depth = e->recursion_nesting;
1043 if (old_depth < depth)
1044 irg->callgraph_recursion_depth = depth;
1046 if (depth > irp->max_callgraph_recursion_depth)
1047 irp->max_callgraph_recursion_depth = depth;
1049 /* -- spread the nesting value -- */
1050 if (depth == 0 || old_depth < depth) {
1051 /* Don't walk the graph, but a tree that is an unfolded graph.
1052 Therefore we unset the visited flag at the end. */
1053 n_callees = get_irg_n_callees(irg);
1054 for (i = 0; i < n_callees; ++i) {
1055 ir_graph *m = get_irg_callee(irg, i);
1056 compute_rec_depth(m, env);
1060 /* -- clean up -- */
1063 e->recursion_nesting--;
1065 set_cg_irg_visited(irg, master_cg_visited-1);
1069 /* ----------------------------------------------------------------------------------- */
1070 /* Another algorithm to compute the execution frequency of methods ignoring recursions. */
1071 /* Walk the callgraph. Ignore backedges. Use sum of execution frequencies of Call */
1072 /* nodes to evaluate a callgraph edge. */
1073 /* ----------------------------------------------------------------------------------- */
1075 /* Returns the method execution frequency of a graph. */
1076 double get_irg_method_execution_frequency(const ir_graph *irg)
1078 return irg->method_execution_frequency;
1082 * Increase the method execution frequency to freq if its current value is
1083 * smaller then this.
1085 static void set_irg_method_execution_frequency(ir_graph *irg, double freq)
1087 irg->method_execution_frequency = freq;
1089 if (irp->max_method_execution_frequency < freq)
1090 irp->max_method_execution_frequency = freq;
1093 static void compute_method_execution_frequency(ir_graph *irg, void *env)
1101 if (cg_irg_visited(irg))
1104 /* We need the values of all predecessors (except backedges).
1105 So they must be marked. Else we will reach the node through
1106 one of the unmarked ones. */
1107 n_callers = get_irg_n_callers(irg);
1108 for (i = 0; i < n_callers; ++i) {
1109 ir_graph *m = get_irg_caller(irg, i);
1110 if (is_irg_caller_backedge(irg, i))
1112 if (!cg_irg_visited(m)) {
1116 mark_cg_irg_visited(irg);
1118 /* Compute the new frequency. */
1121 for (i = 0; i < n_callers; i++) {
1122 if (! is_irg_caller_backedge(irg, i)) {
1123 double edge_freq = get_irg_caller_method_execution_frequency(irg, i);
1124 assert(edge_freq >= 0);
1131 /* A starting point: method only called from outside,
1132 or only backedges as predecessors. */
1136 set_irg_method_execution_frequency(irg, freq);
1139 n_callees = get_irg_n_callees(irg);
1140 for (i = 0; i < n_callees; ++i) {
1141 compute_method_execution_frequency(get_irg_callee(irg, i), NULL);
1146 /* ----------------------------------------------------------------------------------- */
1147 /* The recursion stuff driver. */
1148 /* ----------------------------------------------------------------------------------- */
1150 /* Compute the backedges that represent recursions. */
1151 void find_callgraph_recursions(void)
1154 struct obstack temp;
1158 /* -- compute the looptree. -- */
1160 /* The outermost graph. We start here. Then we start at all
1161 functions in irg list that are never called, then at the remaining
1162 unvisited ones. The third step is needed for functions that are not
1163 reachable from the outermost graph, but call themselves in a cycle. */
1164 assert(get_irp_main_irg());
1165 outermost_ir_graph = get_irp_main_irg();
1166 obstack_init(&temp);
1169 current_loop = NULL;
1170 new_loop(); /* sets current_loop */
1172 ++master_cg_visited;
1173 cgscc(outermost_ir_graph);
1174 n_irgs = get_irp_n_irgs();
1175 for (i = 0; i < n_irgs; ++i) {
1176 ir_graph *irg = get_irp_irg(i);
1177 if (!cg_irg_visited(irg) && get_irg_n_callers(irg) == 0)
1180 for (i = 0; i < n_irgs; ++i) {
1181 ir_graph *irg = get_irp_irg(i);
1182 if (!cg_irg_visited(irg))
1185 obstack_free(&temp, NULL);
1187 irp->outermost_cg_loop = current_loop;
1188 mature_loops(current_loop, outermost_ir_graph->obst);
1190 /* -- Reverse the backedge information. -- */
1191 for (i = 0; i < n_irgs; ++i) {
1192 ir_graph *irg = get_irp_irg(i);
1193 int j, n_callees = get_irg_n_callees(irg);
1194 for (j = 0; j < n_callees; ++j) {
1195 if (is_irg_callee_backedge(irg, j))
1196 set_irg_caller_backedge(get_irg_callee(irg, j), irg);
1200 irp->callgraph_state = irp_callgraph_and_calltree_consistent;
1203 /* Compute interprocedural performance estimates. */
1204 void compute_performance_estimates(void)
1206 int i, n_irgs = get_irp_n_irgs();
1207 int current_nesting;
1210 assert(get_irp_exec_freq_state() != exec_freq_none && "execution frequency not calculated");
1212 /* -- compute the loop depth -- */
1213 current_nesting = 0;
1214 irp->max_callgraph_loop_depth = 0;
1215 master_cg_visited += 2;
1216 compute_loop_depth(get_irp_main_irg(), ¤t_nesting);
1217 for (i = 0; i < n_irgs; i++) {
1218 ir_graph *irg = get_irp_irg(i);
1219 if ((get_cg_irg_visited(irg) < master_cg_visited-1) &&
1220 get_irg_n_callers(irg) == 0) {
1221 compute_loop_depth(irg, ¤t_nesting);
1224 for (i = 0; i < n_irgs; i++) {
1225 ir_graph *irg = get_irp_irg(i);
1226 if (get_cg_irg_visited(irg) < master_cg_visited-1) {
1227 compute_loop_depth(irg, ¤t_nesting);
1232 /* -- compute the recursion depth -- */
1233 e.loop_stack = NEW_ARR_F(ir_loop *, 0);
1235 e.recursion_nesting = 0;
1237 irp->max_callgraph_recursion_depth = 0;
1239 master_cg_visited += 2;
1240 compute_rec_depth(get_irp_main_irg(), &e);
1241 for (i = 0; i < n_irgs; i++) {
1242 ir_graph *irg = get_irp_irg(i);
1243 if ((get_cg_irg_visited(irg) < master_cg_visited-1) &&
1244 get_irg_n_callers(irg) == 0) {
1245 compute_rec_depth(irg, &e);
1248 for (i = 0; i < n_irgs; i++) {
1249 ir_graph *irg = get_irp_irg(i);
1250 if (get_cg_irg_visited(irg) < master_cg_visited-1) {
1251 compute_rec_depth(irg, &e);
1255 DEL_ARR_F(e.loop_stack);
1257 /* -- compute the execution frequency -- */
1258 irp->max_method_execution_frequency = 0;
1259 master_cg_visited += 2;
1260 assert(get_irg_n_callers(get_irp_main_irg()) == 0);
1261 compute_method_execution_frequency(get_irp_main_irg(), NULL);
1262 for (i = 0; i < n_irgs; i++) {
1263 ir_graph *irg = get_irp_irg(i);
1264 if ((get_cg_irg_visited(irg) < master_cg_visited-1) &&
1265 get_irg_n_callers(irg) == 0) {
1266 compute_method_execution_frequency(irg, NULL);
1269 for (i = 0; i < n_irgs; i++) {
1270 ir_graph *irg = get_irp_irg(i);
1271 if (get_cg_irg_visited(irg) < master_cg_visited-1) {
1272 compute_method_execution_frequency(irg, NULL);
1277 /* Returns the maximal loop depth of all paths from an external visible method to
1279 int get_irg_loop_depth(const ir_graph *irg)
1281 assert(irp->callgraph_state == irp_callgraph_consistent ||
1282 irp->callgraph_state == irp_callgraph_and_calltree_consistent);
1283 return irg->callgraph_loop_depth;
1286 /* Returns the maximal recursion depth of all paths from an external visible method to
1288 int get_irg_recursion_depth(const ir_graph *irg)
1290 assert(irp->callgraph_state == irp_callgraph_and_calltree_consistent);
1291 return irg->callgraph_recursion_depth;
1294 /* Computes the interprocedural loop nesting information. */
1295 void analyse_loop_nesting_depth(void)
1297 /* establish preconditions. */
1298 if (get_irp_callee_info_state() != irg_callee_info_consistent) {
1299 ir_entity **free_methods = NULL;
1301 cgana(&free_methods);
1302 xfree(free_methods);
1305 if (irp_callgraph_consistent != get_irp_callgraph_state()) {
1306 compute_callgraph();
1309 find_callgraph_recursions();
1311 compute_performance_estimates();
1313 set_irp_loop_nesting_depth_state(loop_nesting_depth_consistent);
1316 loop_nesting_depth_state get_irp_loop_nesting_depth_state(void)
1318 return irp->lnd_state;
1320 void set_irp_loop_nesting_depth_state(loop_nesting_depth_state s)
1324 void set_irp_loop_nesting_depth_state_inconsistent(void)
1326 if (irp->lnd_state == loop_nesting_depth_consistent)
1327 irp->lnd_state = loop_nesting_depth_inconsistent;