2 * Copyright (C) 1995-2008 University of Karlsruhe. All right reserved.
4 * This file is part of libFirm.
6 * This file may be distributed and/or modified under the terms of the
7 * GNU General Public License version 2 as published by the Free Software
8 * Foundation and appearing in the file LICENSE.GPL included in the
9 * packaging of this file.
11 * Licensees holding valid libFirm Professional Edition licenses may use
12 * this file in accordance with the libFirm Commercial License.
13 * Agreement provided with the Software.
15 * This file is provided AS IS with NO WARRANTY OF ANY KIND, INCLUDING THE
16 * WARRANTY OF DESIGN, MERCHANTABILITY AND FITNESS FOR A PARTICULAR
22 * @brief Representation and computation of the callgraph.
23 * @author Goetz Lindenmaier
32 #include "callgraph.h"
36 #include "irgraph_t.h"
40 #include "execution_frequency.h"
45 #include "raw_bitset.h"
49 static ir_visited_t master_cg_visited = 0;
50 static inline int cg_irg_visited (ir_graph *n);
51 static inline void mark_cg_irg_visited(ir_graph *n);
53 /** Returns the callgraph state of the program representation. */
54 irp_callgraph_state get_irp_callgraph_state(void)
56 return irp->callgraph_state;
59 /* Sets the callgraph state of the program representation. */
60 void set_irp_callgraph_state(irp_callgraph_state s)
62 irp->callgraph_state = s;
65 /* Returns the number of procedures that call the given irg. */
66 int get_irg_n_callers(const ir_graph *irg)
68 if (irg->callers) return ARR_LEN(irg->callers);
72 /* Returns the caller at position pos. */
73 ir_graph *get_irg_caller(const ir_graph *irg, int pos)
75 assert(pos >= 0 && pos < get_irg_n_callers(irg));
76 if (irg->callers) return irg->callers[pos];
80 /* Returns non-zero if the caller at position pos is "a backedge", i.e. a recursion. */
81 int is_irg_caller_backedge(const ir_graph *irg, int pos)
83 assert(pos >= 0 && pos < get_irg_n_callers(irg));
84 return irg->caller_isbe != NULL ? rbitset_is_set(irg->caller_isbe, pos) : 0;
87 /** Search the caller in the list of all callers and set it's backedge property. */
88 static void set_irg_caller_backedge(ir_graph *irg, ir_graph *caller)
90 int i, n_callers = get_irg_n_callers(irg);
92 /* allocate a new array on demand */
93 if (irg->caller_isbe == NULL)
94 irg->caller_isbe = rbitset_malloc(n_callers);
95 for (i = 0; i < n_callers; ++i) {
96 if (get_irg_caller(irg, i) == caller) {
97 rbitset_set(irg->caller_isbe, i);
103 /* Returns non-zero if the irg has a backedge caller. */
104 int has_irg_caller_backedge(const ir_graph *irg)
106 int i, n_callers = get_irg_n_callers(irg);
108 if (irg->caller_isbe != NULL) {
109 for (i = 0; i < n_callers; ++i)
110 if (rbitset_is_set(irg->caller_isbe, i))
117 * Find the reversion position of a caller.
118 * Given the position pos_caller of an caller of irg, return
119 * irg's callee position on that caller.
121 static int reverse_pos(const ir_graph *callee, int pos_caller)
123 ir_graph *caller = get_irg_caller(callee, pos_caller);
124 /* search the other relation for the corresponding edge. */
126 int i, n_callees = get_irg_n_callees(caller);
127 for (i = 0; i < n_callees; ++i) {
128 if (get_irg_callee(caller, i) == callee) {
134 assert(pos_callee >= 0);
139 /* Returns the maximal loop depth of call nodes that call along this edge. */
140 int get_irg_caller_loop_depth(const ir_graph *irg, int pos)
142 ir_graph *caller = get_irg_caller(irg, pos);
143 int pos_callee = reverse_pos(irg, pos);
145 return get_irg_callee_loop_depth(caller, pos_callee);
149 /* Returns the number of procedures that are called by the given irg. */
150 int get_irg_n_callees(const ir_graph *irg)
152 if (irg->callees) return ARR_LEN(irg->callees);
156 /* Returns the callee at position pos. */
157 ir_graph *get_irg_callee(const ir_graph *irg, int pos)
159 assert(pos >= 0 && pos < get_irg_n_callees(irg));
160 if (irg->callees) return irg->callees[pos]->irg;
164 /* Returns non-zero if the callee at position pos is "a backedge", i.e. a recursion. */
165 int is_irg_callee_backedge(const ir_graph *irg, int pos)
167 assert(pos >= 0 && pos < get_irg_n_callees(irg));
168 return irg->callee_isbe != NULL ? rbitset_is_set(irg->callee_isbe, pos) : 0;
171 /* Returns non-zero if the irg has a backedge callee. */
172 int has_irg_callee_backedge(const ir_graph *irg)
174 int i, n_callees = get_irg_n_callees(irg);
176 if (irg->callee_isbe != NULL) {
177 for (i = 0; i < n_callees; ++i)
178 if (rbitset_is_set(irg->callee_isbe, i))
185 * Mark the callee at position pos as a backedge.
187 static void set_irg_callee_backedge(ir_graph *irg, int pos)
189 int n = get_irg_n_callees(irg);
191 /* allocate a new array on demand */
192 if (irg->callee_isbe == NULL)
193 irg->callee_isbe = rbitset_malloc(n);
194 assert(pos >= 0 && pos < n);
195 rbitset_set(irg->callee_isbe, pos);
198 /* Returns the maximal loop depth of call nodes that call along this edge. */
199 int get_irg_callee_loop_depth(const ir_graph *irg, int pos)
201 assert(pos >= 0 && pos < get_irg_n_callees(irg));
202 if (irg->callees) return irg->callees[pos]->max_depth;
206 static double get_irg_callee_execution_frequency(const ir_graph *irg, int pos)
208 ir_node **arr = irg->callees[pos]->call_list;
209 int i, n_Calls = ARR_LEN(arr);
212 for (i = 0; i < n_Calls; ++i) {
213 freq += get_irn_exec_freq(arr[i]);
218 static double get_irg_callee_method_execution_frequency(const ir_graph *irg,
221 double call_freq = get_irg_callee_execution_frequency(irg, pos);
222 double meth_freq = get_irg_method_execution_frequency(irg);
223 return call_freq * meth_freq;
226 static double get_irg_caller_method_execution_frequency(const ir_graph *irg,
229 ir_graph *caller = get_irg_caller(irg, pos);
230 int pos_callee = reverse_pos(irg, pos);
232 return get_irg_callee_method_execution_frequency(caller, pos_callee);
236 /* --------------------- Compute the callgraph ------------------------ */
239 * Walker called by compute_callgraph(), analyses all Call nodes.
241 static void ana_Call(ir_node *n, void *env)
247 if (! is_Call(n)) return;
249 irg = get_irn_irg(n);
250 n_callees = get_Call_n_callees(n);
251 for (i = 0; i < n_callees; ++i) {
252 ir_entity *callee_e = get_Call_callee(n, i);
253 ir_graph *callee = get_entity_irg(callee_e);
257 cg_callee_entry *found;
262 pset_insert((pset *)callee->callers, irg, HASH_PTR(irg));
263 found = pset_find((pset *)irg->callees, &buf, HASH_PTR(callee));
264 if (found) { /* add Call node to list, compute new nesting. */
265 ir_node **arr = found->call_list;
266 ARR_APP1(ir_node *, arr, n);
267 found->call_list = arr;
268 } else { /* New node, add Call node and init nesting. */
269 found = OALLOC(irg->obst, cg_callee_entry);
271 found->call_list = NEW_ARR_F(ir_node *, 1);
272 found->call_list[0] = n;
273 found->max_depth = 0;
274 pset_insert((pset *)irg->callees, found, HASH_PTR(callee));
276 depth = get_loop_depth(get_irn_loop(get_nodes_block(n)));
277 found->max_depth = (depth > found->max_depth) ? depth : found->max_depth;
282 /** compare two ir graphs in a cg_callee_entry */
283 static int cg_callee_entry_cmp(const void *elt, const void *key)
285 const cg_callee_entry *e1 = elt;
286 const cg_callee_entry *e2 = key;
287 return e1->irg != e2->irg;
290 /** compare two ir graphs for pointer identity */
291 static int graph_cmp(const void *elt, const void *key)
293 const ir_graph *e1 = elt;
294 const ir_graph *e2 = key;
299 /* Construct and destruct the callgraph. */
300 void compute_callgraph(void)
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 = pset_first(callee_set);
335 for (j = 0; j < count; ++j) {
336 irg->callees[j] = callee;
337 callee = 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 = pset_first(caller_set);
347 for (j = 0; j < count; ++j) {
349 c = 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 = 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 = 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 = 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 = 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 = 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 = 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 = get_irg_link(irg);
531 assert(info && "missing call to init_scc()");
535 /**********************************************************************/
537 /**********************************************************************/
539 static ir_graph **stack = NULL;
540 static int 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 int nlen = ARR_LEN(stack) * 2;
563 ARR_RESIZE(ir_node *, 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)
574 ir_graph *irg = stack[--tos];
575 mark_irg_not_in_stack(irg);
580 * The nodes up to irg belong to the current loop.
581 * Removes them from the stack and adds them to the current loop.
583 static inline void pop_scc_to_loop(ir_graph *irg)
590 set_irg_dfn(m, loop_node_cnt);
591 add_loop_irg(current_loop, m);
593 //m->callgraph_loop_depth = current_loop->depth;
597 /* GL ??? my last son is my grandson??? Removes cfloops with no
598 ir_nodes in them. Such loops have only another loop as son. (Why
599 can't they have two loops as sons? Does it never get that far? ) */
600 static void close_loop(ir_loop *l)
602 int last = get_loop_n_elements(l) - 1;
603 loop_element lelement = get_loop_element(l, last);
604 ir_loop *last_son = lelement.son;
606 if (get_kind(last_son) == k_ir_loop &&
607 get_loop_n_elements(last_son) == 1) {
610 lelement = get_loop_element(last_son, 0);
612 if (get_kind(gson) == k_ir_loop) {
613 loop_element new_last_son;
615 gson->outer_loop = l;
616 new_last_son.son = gson;
617 l->children[last] = new_last_son;
624 * Removes and unmarks all nodes up to n from the stack.
625 * The nodes must be visited once more to assign them to a scc.
627 static inline void pop_scc_unmark_visit(ir_graph *n)
633 set_cg_irg_visited(m, 0);
637 /**********************************************************************/
638 /* The loop data structure. **/
639 /**********************************************************************/
642 * Allocates a new loop as son of current_loop. Sets current_loop
643 * to the new loop and returns the father.
645 static ir_loop *new_loop(void)
647 ir_loop *father = current_loop;
648 ir_loop *son = alloc_loop(father, outermost_ir_graph->obst);
655 /**********************************************************************/
656 /* Constructing and destructing the loop/backedge information. **/
657 /**********************************************************************/
659 /* Initialization steps. **********************************************/
661 static void init_scc(struct obstack *obst)
670 n_irgs = get_irp_n_irgs();
671 for (i = 0; i < n_irgs; ++i) {
672 ir_graph *irg = get_irp_irg(i);
673 set_irg_link(irg, new_scc_info(obst));
674 irg->callgraph_recursion_depth = 0;
675 irg->callgraph_loop_depth = 0;
679 /** Returns non-zero if n is a loop header, i.e., it is a Block node
680 * and has predecessors within the cfloop and out of the cfloop.
682 * @param root: only needed for assertion.
684 static int is_head(ir_graph *n, ir_graph *root)
687 int some_outof_loop = 0, some_in_loop = 0;
689 arity = get_irg_n_callees(n);
690 for (i = 0; i < arity; i++) {
691 ir_graph *pred = get_irg_callee(n, i);
692 if (is_irg_callee_backedge(n, i)) continue;
693 if (!irg_is_in_stack(pred)) {
696 if (get_irg_uplink(pred) < get_irg_uplink(root)) {
697 assert(get_irg_uplink(pred) >= get_irg_uplink(root));
703 return some_outof_loop && some_in_loop;
707 * Returns non-zero if n is possible loop head of an endless loop.
708 * I.e., it is a Block or Phi node and has only predecessors
710 * @arg root: only needed for assertion.
712 static int is_endless_head(ir_graph *n, ir_graph *root)
715 int some_outof_loop = 0, some_in_loop = 0;
717 arity = get_irg_n_callees(n);
718 for (i = 0; i < arity; i++) {
719 ir_graph *pred = get_irg_callee(n, i);
721 if (is_irg_callee_backedge(n, i))
723 if (!irg_is_in_stack(pred)) {
726 if (get_irg_uplink(pred) < get_irg_uplink(root)) {
727 assert(get_irg_uplink(pred) >= get_irg_uplink(root));
732 return !some_outof_loop && some_in_loop;
736 * Returns index of the predecessor with the smallest dfn number
737 * greater-equal than limit.
739 static int smallest_dfn_pred(ir_graph *n, int limit)
741 int i, index = -2, min = -1;
743 int arity = get_irg_n_callees(n);
744 for (i = 0; i < arity; i++) {
745 ir_graph *pred = get_irg_callee(n, i);
746 if (is_irg_callee_backedge(n, i) || !irg_is_in_stack(pred))
748 if (get_irg_dfn(pred) >= limit && (min == -1 || get_irg_dfn(pred) < min)) {
750 min = get_irg_dfn(pred);
757 /** Returns index of the predecessor with the largest dfn number. */
758 static int largest_dfn_pred(ir_graph *n)
760 int i, index = -2, max = -1;
762 int arity = get_irg_n_callees(n);
763 for (i = 0; i < arity; ++i) {
764 ir_graph *pred = get_irg_callee(n, i);
765 if (is_irg_callee_backedge (n, i) || !irg_is_in_stack(pred)) continue;
766 if (get_irg_dfn(pred) > max) {
768 max = get_irg_dfn(pred);
775 static ir_graph *find_tail(ir_graph *n)
778 int i, res_index = -2;
781 if (!icfg && rm_cyclic_phis && remove_cyclic_phis (n)) return NULL;
783 m = stack[tos-1]; /* tos = top of stack */
784 if (is_head (m, n)) {
785 res_index = smallest_dfn_pred(m, 0);
786 if ((res_index == -2) && /* no smallest dfn pred found. */
790 if (m == n) return NULL; // Is this to catch Phi - self loops?
791 for (i = tos-2; i >= 0; --i) {
795 res_index = smallest_dfn_pred(m, get_irg_dfn(m) + 1);
796 if (res_index == -2) /* no smallest dfn pred found. */
797 res_index = largest_dfn_pred(m);
799 if ((m == n) && (res_index == -2)) {
805 /* We should not walk past our selves on the stack: The upcoming nodes
806 are not in this loop. We assume a loop not reachable from Start. */
815 /* A dead loop not reachable from Start. */
816 for (i = tos-2; i >= 0; --i) {
818 if (is_endless_head(m, n)) {
819 res_index = smallest_dfn_pred(m, get_irg_dfn(m) + 1);
820 if (res_index == -2) /* no smallest dfn pred found. */
821 res_index = largest_dfn_pred(m);
824 if (m == n) { break; } /* It's not an unreachable loop, either. */
826 //assert(0 && "no head found on stack");
830 assert (res_index > -2);
832 set_irg_callee_backedge(m, res_index);
833 return get_irg_callee(m, res_index);
836 /*-----------------------------------------------------------*
837 * The core algorithm. *
838 *-----------------------------------------------------------*/
841 static void cgscc(ir_graph *n)
845 if (cg_irg_visited(n)) return;
846 mark_cg_irg_visited(n);
848 /* Initialize the node */
849 set_irg_dfn(n, current_dfn); /* Depth first number for this node */
850 set_irg_uplink(n, current_dfn); /* ... is default uplink. */
854 arity = get_irg_n_callees(n);
855 for (i = 0; i < arity; i++) {
857 if (is_irg_callee_backedge(n, i)) continue;
858 m = get_irg_callee(n, i);
860 /** This marks the backedge, but does it guarantee a correct loop tree? */
861 //if (m == n) { set_irg_callee_backedge(n, i); continue; }
864 if (irg_is_in_stack(m)) {
865 /* Uplink of m is smaller if n->m is a backedge.
866 Propagate the uplink to mark the cfloop. */
867 if (get_irg_uplink(m) < get_irg_uplink(n))
868 set_irg_uplink(n, get_irg_uplink(m));
872 if (get_irg_dfn(n) == get_irg_uplink(n)) {
873 /* This condition holds for
874 1) the node with the incoming backedge.
875 That is: We found a cfloop!
876 2) Straight line code, because no uplink has been propagated, so the
877 uplink still is the same as the dfn.
879 But n might not be a proper cfloop head for the analysis. Proper cfloop
880 heads are Block and Phi nodes. find_tail searches the stack for
881 Block's and Phi's and takes those nodes as cfloop heads for the current
882 cfloop instead and marks the incoming edge as backedge. */
884 ir_graph *tail = find_tail(n);
886 /* We have a cfloop, that is no straight line code,
887 because we found a cfloop head!
888 Next actions: Open a new cfloop on the cfloop tree and
889 try to find inner cfloops */
892 ir_loop *l = new_loop();
894 /* Remove the cfloop from the stack ... */
895 pop_scc_unmark_visit(n);
897 /* The current backedge has been marked, that is temporarily eliminated,
898 by find tail. Start the scc algorithm
899 anew on the subgraph thats left (the current cfloop without the backedge)
900 in order to find more inner cfloops. */
904 assert(cg_irg_visited(n));
914 * reset the backedge information for all callers in all irgs
916 static void reset_isbe(void)
918 int i, n_irgs = get_irp_n_irgs();
920 for (i = 0; i < n_irgs; ++i) {
921 ir_graph *irg = get_irp_irg(i);
923 if (irg->caller_isbe)
924 xfree(irg->caller_isbe);
925 irg->caller_isbe = NULL;
927 if (irg->callee_isbe)
928 xfree(irg->callee_isbe);
929 irg->callee_isbe = NULL;
933 /* ----------------------------------------------------------------------------------- */
934 /* Another algorithm to compute recursion nesting depth */
935 /* Walk the callgraph. For each crossed edge increase the loop depth by the edge */
936 /* weight. Assign graphs the maximal depth. */
937 /* ----------------------------------------------------------------------------------- */
939 static void compute_loop_depth(ir_graph *irg, void *env)
941 int current_nesting = *(int *) env;
942 int old_nesting = irg->callgraph_loop_depth;
943 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 */
960 /* Don't walk the graph, but a tree that is an unfolded graph. */
961 n_callees = get_irg_n_callees(irg);
962 for (i = 0; i < n_callees; i++) {
963 ir_graph *m = get_irg_callee(irg, i);
964 *(int *)env += get_irg_callee_loop_depth(irg, i);
965 compute_loop_depth(m, env);
966 *(int *)env -= get_irg_callee_loop_depth(irg, i);
970 set_cg_irg_visited(irg, master_cg_visited-1);
973 /* ------------------------------------------------------------------------------------ */
974 /* Another algorithm to compute recursion nesting depth */
975 /* Walk the callgraph. For each crossed loop increase the nesting depth by one. */
976 /* Assign graphs the maximal nesting depth. Don't increase if passing loops more than */
978 /* ------------------------------------------------------------------------------------ */
981 /* For callees, we want to remember the Call nodes, too. */
982 typedef struct ana_entry2 {
983 ir_loop **loop_stack; /**< a stack of ir_loop entries */
984 int tos; /**< the top of stack entry */
985 int recursion_nesting;
989 * push a loop entry on the stack
991 static void push2(ana_entry2 *e, ir_loop *g)
993 if (ARR_LEN(e->loop_stack) == e->tos) {
994 ARR_APP1(ir_loop *, e->loop_stack, g);
996 e->loop_stack[e->tos] = g;
1002 * returns the top of stack and pop it
1004 static ir_loop *pop2(ana_entry2 *e)
1006 return e->loop_stack[--e->tos];
1010 * check if a loop g in on the stack. Did not check the TOS.
1012 static int in_stack(ana_entry2 *e, ir_loop *g)
1015 for (i = e->tos-1; i >= 0; --i) {
1016 if (e->loop_stack[i] == g) return 1;
1021 static void compute_rec_depth(ir_graph *irg, void *env)
1023 ana_entry2 *e = (ana_entry2 *)env;
1024 ir_loop *l = irg->l;
1025 int depth, old_depth = irg->callgraph_recursion_depth;
1029 if (cg_irg_visited(irg))
1031 mark_cg_irg_visited(irg);
1033 /* -- compute and set the new nesting value -- */
1034 if ((l != irp->outermost_cg_loop) && !in_stack(e, l)) {
1036 e->recursion_nesting++;
1039 depth = e->recursion_nesting;
1041 if (old_depth < depth)
1042 irg->callgraph_recursion_depth = depth;
1044 if (depth > irp->max_callgraph_recursion_depth)
1045 irp->max_callgraph_recursion_depth = depth;
1047 /* -- spread the nesting value -- */
1048 if (depth == 0 || old_depth < depth) {
1049 /* Don't walk the graph, but a tree that is an unfolded graph.
1050 Therefore we unset the visited flag at the end. */
1051 n_callees = get_irg_n_callees(irg);
1052 for (i = 0; i < n_callees; ++i) {
1053 ir_graph *m = get_irg_callee(irg, i);
1054 compute_rec_depth(m, env);
1058 /* -- clean up -- */
1061 e->recursion_nesting--;
1063 set_cg_irg_visited(irg, master_cg_visited-1);
1067 /* ----------------------------------------------------------------------------------- */
1068 /* Another algorithm to compute the execution frequency of methods ignoring recursions. */
1069 /* Walk the callgraph. Ignore backedges. Use sum of execution frequencies of Call */
1070 /* nodes to evaluate a callgraph edge. */
1071 /* ----------------------------------------------------------------------------------- */
1073 /* Returns the method execution frequency of a graph. */
1074 double get_irg_method_execution_frequency(const ir_graph *irg)
1076 return irg->method_execution_frequency;
1080 * Increase the method execution frequency to freq if its current value is
1081 * smaller then this.
1083 static void set_irg_method_execution_frequency(ir_graph *irg, double freq)
1085 irg->method_execution_frequency = freq;
1087 if (irp->max_method_execution_frequency < freq)
1088 irp->max_method_execution_frequency = freq;
1091 static void compute_method_execution_frequency(ir_graph *irg, void *env)
1099 if (cg_irg_visited(irg))
1102 /* We need the values of all predecessors (except backedges).
1103 So they must be marked. Else we will reach the node through
1104 one of the unmarked ones. */
1105 n_callers = get_irg_n_callers(irg);
1106 for (i = 0; i < n_callers; ++i) {
1107 ir_graph *m = get_irg_caller(irg, i);
1108 if (is_irg_caller_backedge(irg, i))
1110 if (!cg_irg_visited(m)) {
1114 mark_cg_irg_visited(irg);
1116 /* Compute the new frequency. */
1119 for (i = 0; i < n_callers; i++) {
1120 if (! is_irg_caller_backedge(irg, i)) {
1121 double edge_freq = get_irg_caller_method_execution_frequency(irg, i);
1122 assert(edge_freq >= 0);
1129 /* A starting point: method only called from outside,
1130 or only backedges as predecessors. */
1134 set_irg_method_execution_frequency(irg, freq);
1137 n_callees = get_irg_n_callees(irg);
1138 for (i = 0; i < n_callees; ++i) {
1139 compute_method_execution_frequency(get_irg_callee(irg, i), NULL);
1144 /* ----------------------------------------------------------------------------------- */
1145 /* The recursion stuff driver. */
1146 /* ----------------------------------------------------------------------------------- */
1148 /* Compute the backedges that represent recursions. */
1149 void find_callgraph_recursions(void)
1152 struct obstack temp;
1156 /* -- compute the looptree. -- */
1158 /* The outermost graph. We start here. Then we start at all
1159 functions in irg list that are never called, then at the remaining
1160 unvisited ones. The third step is needed for functions that are not
1161 reachable from the outermost graph, but call themselves in a cycle. */
1162 assert(get_irp_main_irg());
1163 outermost_ir_graph = get_irp_main_irg();
1164 obstack_init(&temp);
1167 current_loop = NULL;
1168 new_loop(); /* sets current_loop */
1170 ++master_cg_visited;
1171 cgscc(outermost_ir_graph);
1172 n_irgs = get_irp_n_irgs();
1173 for (i = 0; i < n_irgs; ++i) {
1174 ir_graph *irg = get_irp_irg(i);
1175 if (!cg_irg_visited(irg) && get_irg_n_callers(irg) == 0)
1178 for (i = 0; i < n_irgs; ++i) {
1179 ir_graph *irg = get_irp_irg(i);
1180 if (!cg_irg_visited(irg))
1183 obstack_free(&temp, NULL);
1185 irp->outermost_cg_loop = current_loop;
1186 mature_loops(current_loop, outermost_ir_graph->obst);
1188 /* -- Reverse the backedge information. -- */
1189 for (i = 0; i < n_irgs; ++i) {
1190 ir_graph *irg = get_irp_irg(i);
1191 int j, n_callees = get_irg_n_callees(irg);
1192 for (j = 0; j < n_callees; ++j) {
1193 if (is_irg_callee_backedge(irg, j))
1194 set_irg_caller_backedge(get_irg_callee(irg, j), irg);
1198 irp->callgraph_state = irp_callgraph_and_calltree_consistent;
1201 /* Compute interprocedural performance estimates. */
1202 void compute_performance_estimates(void)
1204 int i, n_irgs = get_irp_n_irgs();
1205 int current_nesting;
1208 assert(get_irp_exec_freq_state() != exec_freq_none && "execution frequency not calculated");
1210 /* -- compute the loop depth -- */
1211 current_nesting = 0;
1212 irp->max_callgraph_loop_depth = 0;
1213 master_cg_visited += 2;
1214 compute_loop_depth(get_irp_main_irg(), ¤t_nesting);
1215 for (i = 0; i < n_irgs; i++) {
1216 ir_graph *irg = get_irp_irg(i);
1217 if ((get_cg_irg_visited(irg) < master_cg_visited-1) &&
1218 get_irg_n_callers(irg) == 0) {
1219 compute_loop_depth(irg, ¤t_nesting);
1222 for (i = 0; i < n_irgs; i++) {
1223 ir_graph *irg = get_irp_irg(i);
1224 if (get_cg_irg_visited(irg) < master_cg_visited-1) {
1225 compute_loop_depth(irg, ¤t_nesting);
1230 /* -- compute the recursion depth -- */
1231 e.loop_stack = NEW_ARR_F(ir_loop *, 0);
1233 e.recursion_nesting = 0;
1235 irp->max_callgraph_recursion_depth = 0;
1237 master_cg_visited += 2;
1238 compute_rec_depth(get_irp_main_irg(), &e);
1239 for (i = 0; i < n_irgs; i++) {
1240 ir_graph *irg = get_irp_irg(i);
1241 if ((get_cg_irg_visited(irg) < master_cg_visited-1) &&
1242 get_irg_n_callers(irg) == 0) {
1243 compute_rec_depth(irg, &e);
1246 for (i = 0; i < n_irgs; i++) {
1247 ir_graph *irg = get_irp_irg(i);
1248 if (get_cg_irg_visited(irg) < master_cg_visited-1) {
1249 compute_rec_depth(irg, &e);
1253 DEL_ARR_F(e.loop_stack);
1255 /* -- compute the execution frequency -- */
1256 irp->max_method_execution_frequency = 0;
1257 master_cg_visited += 2;
1258 assert(get_irg_n_callers(get_irp_main_irg()) == 0);
1259 compute_method_execution_frequency(get_irp_main_irg(), NULL);
1260 for (i = 0; i < n_irgs; i++) {
1261 ir_graph *irg = get_irp_irg(i);
1262 if ((get_cg_irg_visited(irg) < master_cg_visited-1) &&
1263 get_irg_n_callers(irg) == 0) {
1264 compute_method_execution_frequency(irg, NULL);
1267 for (i = 0; i < n_irgs; i++) {
1268 ir_graph *irg = get_irp_irg(i);
1269 if (get_cg_irg_visited(irg) < master_cg_visited-1) {
1270 compute_method_execution_frequency(irg, NULL);
1275 /* Returns the maximal loop depth of all paths from an external visible method to
1277 int get_irg_loop_depth(const ir_graph *irg)
1279 assert(irp->callgraph_state == irp_callgraph_consistent ||
1280 irp->callgraph_state == irp_callgraph_and_calltree_consistent);
1281 return irg->callgraph_loop_depth;
1284 /* Returns the maximal recursion depth of all paths from an external visible method to
1286 int get_irg_recursion_depth(const ir_graph *irg)
1288 assert(irp->callgraph_state == irp_callgraph_and_calltree_consistent);
1289 return irg->callgraph_recursion_depth;
1292 /* Computes the interprocedural loop nesting information. */
1293 void analyse_loop_nesting_depth(void)
1295 ir_entity **free_methods = NULL;
1298 /* establish preconditions. */
1299 if (get_irp_callee_info_state() != irg_callee_info_consistent) {
1300 cgana(&arr_len, &free_methods);
1303 if (irp_callgraph_consistent != get_irp_callgraph_state()) {
1304 compute_callgraph();
1307 find_callgraph_recursions();
1309 compute_performance_estimates();
1311 set_irp_loop_nesting_depth_state(loop_nesting_depth_consistent);
1314 loop_nesting_depth_state get_irp_loop_nesting_depth_state(void)
1316 return irp->lnd_state;
1318 void set_irp_loop_nesting_depth_state(loop_nesting_depth_state s)
1322 void set_irp_loop_nesting_depth_state_inconsistent(void)
1324 if (irp->lnd_state == loop_nesting_depth_consistent)
1325 irp->lnd_state = loop_nesting_depth_inconsistent;