2 * Copyright (C) 1995-2007 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
38 #include "callgraph.h"
42 #include "irgraph_t.h"
46 #include "execution_frequency.h"
54 static int master_cg_visited = 0;
55 static INLINE int cg_irg_visited (ir_graph *n);
56 static INLINE void mark_cg_irg_visited(ir_graph *n);
57 static INLINE void set_cg_irg_visited (ir_graph *n, int i);
59 /** Returns the callgraph state of the program representation. */
60 irp_callgraph_state get_irp_callgraph_state(void) {
61 return irp->callgraph_state;
64 /* Sets the callgraph state of the program representation. */
65 void set_irp_callgraph_state(irp_callgraph_state s) {
66 irp->callgraph_state = s;
69 /* Returns the number of procedures that call the given irg. */
70 int get_irg_n_callers(ir_graph *irg) {
71 if (irg->callers) return ARR_LEN(irg->callers);
75 /* Returns the caller at position pos. */
76 ir_graph *get_irg_caller(ir_graph *irg, int pos) {
77 assert (pos >= 0 && pos < get_irg_n_callers(irg));
78 if (irg->callers) return irg->callers[pos];
82 /* Returns non-zero if the caller at position pos is "a backedge", i.e. a recursion. */
83 int is_irg_caller_backedge(ir_graph *irg, int pos) {
84 assert (pos >= 0 && pos < get_irg_n_callers(irg));
85 return irg->caller_isbe != NULL ? irg->caller_isbe[pos] : 0;
88 /** Search the caller in the list of all callers and set it's backedge property. */
89 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 = xcalloc(n_callers, sizeof(irg->caller_isbe[0]));
95 for (i = 0; i < n_callers; ++i) {
96 if (get_irg_caller(irg, i) == caller) {
97 irg->caller_isbe[i] = 1;
103 /* Returns non-zero if the irg has a backedge caller. */
104 int has_irg_caller_backedge(ir_graph *irg) {
105 int i, n_callers = get_irg_n_callers(irg);
107 if (irg->caller_isbe != NULL) {
108 for (i = 0; i < n_callers; ++i)
109 if (irg->caller_isbe[i]) return 1;
115 * Find the reversion position of a caller.
116 * Given the position pos_caller of an caller of irg, return
117 * irg's callee position on that caller.
119 static int reverse_pos(ir_graph *callee, int pos_caller) {
120 ir_graph *caller = get_irg_caller(callee, pos_caller);
121 /* search the other relation for the corresponding edge. */
123 int i, n_callees = get_irg_n_callees(caller);
124 for (i = 0; i < n_callees; ++i) {
125 if (get_irg_callee(caller, i) == callee) {
131 assert(pos_callee >= 0);
136 /* Returns the maximal loop depth of call nodes that call along this edge. */
137 int get_irg_caller_loop_depth(ir_graph *irg, int pos) {
138 ir_graph *caller = get_irg_caller(irg, pos);
139 int pos_callee = reverse_pos(irg, pos);
141 return get_irg_callee_loop_depth(caller, pos_callee);
145 /* Returns the number of procedures that are called by the given irg. */
146 int get_irg_n_callees(ir_graph *irg) {
147 if (irg->callees) return ARR_LEN(irg->callees);
151 /* Returns the callee at position pos. */
152 ir_graph *get_irg_callee(ir_graph *irg, int pos) {
153 assert (pos >= 0 && pos < get_irg_n_callees(irg));
154 if (irg->callees) return irg->callees[pos]->irg;
158 /* Returns non-zero if the callee at position pos is "a backedge", i.e. a recursion. */
159 int is_irg_callee_backedge(ir_graph *irg, int pos) {
160 assert (pos >= 0 && pos < get_irg_n_callees(irg));
161 return irg->callee_isbe != NULL ? irg->callee_isbe[pos] : 0;
164 /* Returns non-zero if the irg has a backedge callee. */
165 int has_irg_callee_backedge(ir_graph *irg) {
166 int i, n_callees = get_irg_n_callees(irg);
168 if (irg->callee_isbe != NULL) {
169 for (i = 0; i < n_callees; ++i)
170 if (irg->callee_isbe[i]) return 1;
176 * Mark the callee at position pos as a backedge.
178 static void set_irg_callee_backedge(ir_graph *irg, int pos) {
179 int n = get_irg_n_callees(irg);
181 assert (pos >= 0 && pos < n);
183 /* allocate a new array on demand */
184 if (irg->callee_isbe == NULL)
185 irg->callee_isbe = xcalloc(n, sizeof(irg->callee_isbe[0]));
186 irg->callee_isbe[pos] = 1;
189 /* Returns the maximal loop depth of call nodes that call along this edge. */
190 int get_irg_callee_loop_depth(ir_graph *irg, int pos) {
191 assert (pos >= 0 && pos < get_irg_n_callees(irg));
192 if (irg->callees) return irg->callees[pos]->max_depth;
197 double get_irg_callee_execution_frequency(ir_graph *irg, int pos) {
198 ir_node **arr = irg->callees[pos]->call_list;
199 int i, n_Calls = ARR_LEN(arr);
202 for (i = 0; i < n_Calls; ++i) {
203 freq += get_irn_exec_freq(arr[i]);
208 double get_irg_callee_method_execution_frequency(ir_graph *irg, int pos) {
209 double call_freq = get_irg_callee_execution_frequency(irg, pos);
210 double meth_freq = get_irg_method_execution_frequency(irg);
211 return call_freq * meth_freq;
215 double get_irg_caller_method_execution_frequency(ir_graph *irg, int pos) {
216 ir_graph *caller = get_irg_caller(irg, pos);
217 int pos_callee = reverse_pos(irg, pos);
219 return get_irg_callee_method_execution_frequency(caller, pos_callee);
224 /* --------------------- Compute the callgraph ------------------------ */
227 * Walker called by compute_callgraph(), analyses all Call nodes.
229 static void ana_Call(ir_node *n, void *env) {
233 if (! is_Call(n)) return;
235 irg = get_irn_irg(n);
236 n_callees = get_Call_n_callees(n);
237 for (i = 0; i < n_callees; ++i) {
238 ir_entity *callee_e = get_Call_callee(n, i);
239 ir_graph *callee = get_entity_irg(callee_e);
243 cg_callee_entry *found;
248 pset_insert((pset *)callee->callers, irg, HASH_PTR(irg));
249 found = pset_find((pset *)irg->callees, &buf, HASH_PTR(callee));
250 if (found) { /* add Call node to list, compute new nesting. */
251 ir_node **arr = found->call_list;
252 ARR_APP1(ir_node *, arr, n);
253 found->call_list = arr;
254 } else { /* New node, add Call node and init nesting. */
255 found = (cg_callee_entry *)obstack_alloc(irg->obst, sizeof(*found));
257 found->call_list = NEW_ARR_F(ir_node *, 1);
258 found->call_list[0] = n;
259 found->max_depth = 0;
260 pset_insert((pset *)irg->callees, found, HASH_PTR(callee));
262 depth = get_loop_depth(get_irn_loop(get_nodes_block(n)));
263 found->max_depth = (depth > found->max_depth) ? depth : found->max_depth;
268 /** compare two ir graphs in a cg_callee_entry */
269 static int cg_callee_entry_cmp(const void *elt, const void *key) {
270 const cg_callee_entry *e1 = elt;
271 const cg_callee_entry *e2 = key;
272 return e1->irg != e2->irg;
275 /** compare two ir graphs */
276 static int graph_cmp(const void *elt, const void *key) {
277 const ir_graph *e1 = elt;
278 const ir_graph *e2 = key;
283 /* Construct and destruct the callgraph. */
284 void compute_callgraph(void) {
287 assert(! get_interprocedural_view()); /* Else walking will not reach the Call nodes. */
292 n_irgs = get_irp_n_irgs();
293 for (i = 0; i < n_irgs; ++i) {
294 ir_graph *irg = get_irp_irg(i);
295 assert(get_irg_callee_info_state(irg) == irg_callee_info_consistent);
296 irg->callees = (cg_callee_entry **)new_pset(cg_callee_entry_cmp, 8);
297 irg->callers = (ir_graph **)new_pset(graph_cmp, 8);
298 //construct_cf_backedges(irg);
301 /* Compute the call graph */
302 for (i = 0; i < n_irgs; ++i) {
303 ir_graph *irg = get_irp_irg(i);
304 construct_cf_backedges(irg); // We also find the maximal loop depth of a call.
305 irg_walk_graph(irg, ana_Call, NULL, NULL);
308 /* Change the sets to arrays. */
309 for (i = 0; i < n_irgs; ++i) {
311 cg_callee_entry *callee;
312 ir_graph *c, *irg = get_irp_irg(i);
313 pset *callee_set, *caller_set;
315 callee_set = (pset *)irg->callees;
316 count = pset_count(callee_set);
317 irg->callees = NEW_ARR_F(cg_callee_entry *, count);
318 irg->callee_isbe = NULL;
319 callee = pset_first(callee_set);
320 for (j = 0; j < count; ++j) {
321 irg->callees[j] = callee;
322 callee = pset_next(callee_set);
324 del_pset(callee_set);
325 assert(callee == NULL);
327 caller_set = (pset *)irg->callers;
328 count = pset_count(caller_set);
329 irg->callers = NEW_ARR_F(ir_graph *, count);
330 irg->caller_isbe = NULL;
331 c = pset_first(caller_set);
332 for (j = 0; j < count; ++j) {
334 c = pset_next(caller_set);
336 del_pset(caller_set);
339 set_irp_callgraph_state(irp_callgraph_consistent);
342 /* Destruct the callgraph. */
343 void free_callgraph(void) {
344 int i, n_irgs = get_irp_n_irgs();
345 for (i = 0; i < n_irgs; ++i) {
346 ir_graph *irg = get_irp_irg(i);
347 if (irg->callees) DEL_ARR_F(irg->callees);
348 if (irg->callers) DEL_ARR_F(irg->callers);
349 if (irg->callee_isbe) free(irg->callee_isbe);
350 if (irg->caller_isbe) free(irg->caller_isbe);
353 irg->callee_isbe = NULL;
354 irg->caller_isbe = NULL;
356 set_irp_callgraph_state(irp_callgraph_none);
359 /* ----------------------------------------------------------------------------------- */
360 /* A walker for the callgraph */
361 /* ----------------------------------------------------------------------------------- */
364 static void do_walk(ir_graph *irg, callgraph_walk_func *pre, callgraph_walk_func *post, void *env) {
367 if (cg_irg_visited(irg)) return;
368 mark_cg_irg_visited(irg);
373 n_callees = get_irg_n_callees(irg);
374 for (i = 0; i < n_callees; i++) {
375 ir_graph *m = get_irg_callee(irg, i);
376 do_walk(m, pre, post, env);
383 void callgraph_walk(callgraph_walk_func *pre, callgraph_walk_func *post, void *env) {
384 int i, n_irgs = get_irp_n_irgs();
387 do_walk(get_irp_main_irg(), pre, post, env);
388 for (i = 0; i < n_irgs; i++) {
389 ir_graph *irg = get_irp_irg(i);
390 if (!cg_irg_visited(irg) && get_irg_n_callers(irg) == 0)
391 do_walk(irg, pre, post, env);
393 for (i = 0; i < n_irgs; i++) {
394 ir_graph *irg = get_irp_irg(i);
395 if (!cg_irg_visited(irg))
396 do_walk(irg, pre, post, env);
400 /* ----------------------------------------------------------------------------------- */
401 /* loop construction algorithm */
402 /* ----------------------------------------------------------------------------------- */
404 static ir_graph *outermost_ir_graph; /**< The outermost graph the scc is computed
406 static ir_loop *current_loop; /**< Current cfloop construction is working
408 static int loop_node_cnt = 0; /**< Counts the number of allocated cfloop nodes.
409 Each cfloop node gets a unique number.
410 What for? ev. remove. @@@ */
411 static int current_dfn = 1; /**< Counter to generate depth first numbering
415 /*-----------------*/
416 /* Node attributes */
417 /*-----------------*/
419 typedef struct scc_info {
420 int in_stack; /**< Marks whether node is on the stack. */
421 int dfn; /**< Depth first search number. */
422 int uplink; /**< dfn number of ancestor. */
427 * allocates a new scc_info of the obstack
429 static INLINE scc_info *new_scc_info(void) {
430 scc_info *info = obstack_alloc (outermost_ir_graph->obst, sizeof(*info));
431 memset(info, 0, sizeof(*info));
436 * Returns non-zero if a graph was already visited.
439 cg_irg_visited(ir_graph *irg) {
440 scc_info *info = get_irg_link(irg);
441 assert(info && "missing call to init_scc");
442 return (info->visited >= master_cg_visited);
446 * Marks a graph as visited.
449 mark_cg_irg_visited(ir_graph *irg) {
450 scc_info *info = get_irg_link(irg);
451 assert(info && "missing call to init_scc");
452 info->visited = master_cg_visited;
456 * Set a graphs visited flag to i.
459 set_cg_irg_visited(ir_graph *irg, int i) {
460 scc_info *info = get_irg_link(irg);
461 assert(info && "missing call to init_scc");
466 * Returns the visited flag of a graph.
469 get_cg_irg_visited(ir_graph *irg) {
470 scc_info *info = get_irg_link(irg);
471 assert(info && "missing call to init_scc");
472 return info->visited;
476 mark_irg_in_stack(ir_graph *irg) {
477 scc_info *info = get_irg_link(irg);
478 assert(info && "missing call to init_scc");
483 mark_irg_not_in_stack(ir_graph *irg) {
484 scc_info *info = get_irg_link(irg);
485 assert(info && "missing call to init_scc");
490 irg_is_in_stack(ir_graph *irg) {
491 scc_info *info = get_irg_link(irg);
492 assert(info && "missing call to init_scc");
493 return info->in_stack;
497 set_irg_uplink(ir_graph *irg, int uplink) {
498 scc_info *info = get_irg_link(irg);
499 assert(info && "missing call to init_scc");
500 info->uplink = uplink;
504 get_irg_uplink(ir_graph *irg) {
505 scc_info *info = get_irg_link(irg);
506 assert(info && "missing call to init_scc");
511 set_irg_dfn(ir_graph *irg, int dfn) {
512 scc_info *info = get_irg_link(irg);
513 assert(info && "missing call to init_scc");
518 get_irg_dfn(ir_graph *irg) {
519 scc_info *info = get_irg_link(irg);
520 assert(info && "missing call to init_scc");
524 /**********************************************************************/
526 /**********************************************************************/
528 static ir_graph **stack = NULL;
529 static int tos = 0; /**< top of stack */
532 * Initialize the irg stack.
534 static INLINE void init_stack(void) {
536 ARR_RESIZE (ir_graph *, stack, 1000);
538 stack = NEW_ARR_F (ir_graph *, 1000);
544 * push a graph on the irg stack
545 * @param n the graph to be pushed
547 static INLINE void push(ir_graph *irg) {
548 if (tos == ARR_LEN (stack)) {
549 int nlen = ARR_LEN (stack) * 2;
550 ARR_RESIZE (ir_node *, stack, nlen);
553 mark_irg_in_stack(irg);
557 * return the topmost graph on the stack and pop it
559 static INLINE ir_graph *pop(void) {
560 ir_graph *irg = stack[--tos];
561 mark_irg_not_in_stack(irg);
566 * The nodes up to irg belong to the current loop.
567 * Removes them from the stack and adds them to the current loop.
569 static INLINE void pop_scc_to_loop(ir_graph *irg) {
575 set_irg_dfn(m, loop_node_cnt);
576 add_loop_node(current_loop, (ir_node *)m);
578 //m->callgraph_loop_depth = current_loop->depth;
582 /* GL ??? my last son is my grandson??? Removes cfloops with no
583 ir_nodes in them. Such loops have only another loop as son. (Why
584 can't they have two loops as sons? Does it never get that far? ) */
585 static void close_loop(ir_loop *l) {
586 int last = get_loop_n_elements(l) - 1;
587 loop_element lelement = get_loop_element(l, last);
588 ir_loop *last_son = lelement.son;
590 if (get_kind(last_son) == k_ir_loop &&
591 get_loop_n_elements(last_son) == 1) {
594 lelement = get_loop_element(last_son, 0);
596 if(get_kind(gson) == k_ir_loop) {
597 loop_element new_last_son;
599 gson -> outer_loop = l;
600 new_last_son.son = gson;
601 l -> children[last] = new_last_son;
609 * Removes and unmarks all nodes up to n from the stack.
610 * The nodes must be visited once more to assign them to a scc.
612 static INLINE void pop_scc_unmark_visit(ir_graph *n) {
617 set_cg_irg_visited(m, 0);
621 /**********************************************************************/
622 /* The loop data structure. **/
623 /**********************************************************************/
626 * Allocates a new loop as son of current_loop. Sets current_loop
627 * to the new loop and returns the father.
629 static ir_loop *new_loop(void) {
630 ir_loop *father, *son;
632 father = current_loop;
634 son = obstack_alloc(outermost_ir_graph->obst, sizeof(*son));
635 memset(son, 0, sizeof(*son));
636 son->kind = k_ir_loop;
637 son->children = NEW_ARR_F (loop_element, 0);
641 son->outer_loop = father;
642 add_loop_son(father, son);
643 son->depth = father->depth + 1;
644 } else { /* The root loop */
645 son->outer_loop = son;
650 son->loop_nr = get_irp_new_node_nr();
658 /**********************************************************************/
659 /* Constructing and destructing the loop/backedge information. **/
660 /**********************************************************************/
662 /* Initialization steps. **********************************************/
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());
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.
688 is_head(ir_graph *n, ir_graph *root)
691 int some_outof_loop = 0, some_in_loop = 0;
693 arity = get_irg_n_callees(n);
694 for (i = 0; i < arity; i++) {
695 ir_graph *pred = get_irg_callee(n, i);
696 if (is_irg_callee_backedge(n, i)) continue;
697 if (!irg_is_in_stack(pred)) {
700 if (get_irg_uplink(pred) < get_irg_uplink(root)) {
701 assert(get_irg_uplink(pred) >= get_irg_uplink(root));
707 return some_outof_loop & some_in_loop;
711 * Returns non-zero if n is possible loop head of an endless loop.
712 * I.e., it is a Block, Phi or Filter node and has only predecessors
714 * @arg root: only needed for assertion.
717 is_endless_head(ir_graph *n, ir_graph *root)
720 int some_outof_loop = 0, some_in_loop = 0;
722 arity = get_irg_n_callees(n);
723 for (i = 0; i < arity; i++) {
724 ir_graph *pred = get_irg_callee(n, i);
726 if (is_irg_callee_backedge(n, i)) { continue; }
727 if (!irg_is_in_stack(pred)) {
730 if(get_irg_uplink(pred) < get_irg_uplink(root)) {
731 assert(get_irg_uplink(pred) >= get_irg_uplink(root));
737 return !some_outof_loop & some_in_loop;
742 * Check whether there is a parallel edge in the ip control flow.
746 is_ip_head(ir_graph *n, ir_graph *pred)
749 int iv_rem = get_interprocedural_view();
750 set_interprocedural_view(1);
752 ir_node *sblock = get_irg_start_block(n);
753 int i, arity = get_Block_n_cfgpreds(sblock);
755 //printf(" edge from "); DDMG(n);
756 //printf(" to pred "); DDMG(pred);
757 //printf(" sblock "); DDMN(sblock);
759 for (i = 0; i < arity; i++) {
760 ir_node *pred_cfop = skip_Proj(get_Block_cfgpred(sblock, i));
761 //printf(" "); DDMN(pred_cfop);
762 if (get_irn_op(pred_cfop) == op_CallBegin) { /* could be Unknown */
763 ir_graph *ip_pred = get_irn_irg(pred_cfop);
764 //printf(" "); DDMG(ip_pred);
765 if ((ip_pred == pred) && is_backedge(sblock, i)) {
766 //printf(" found\n");
772 set_interprocedural_view(iv_rem);
777 * Returns index of the predecessor with the smallest dfn number
778 * greater-equal than limit.
781 smallest_dfn_pred(ir_graph *n, int limit)
783 int i, index = -2, min = -1;
785 int arity = get_irg_n_callees(n);
786 for (i = 0; i < arity; i++) {
787 ir_graph *pred = get_irg_callee(n, i);
788 if (is_irg_callee_backedge(n, i) || !irg_is_in_stack(pred)) continue;
789 if (get_irg_dfn(pred) >= limit && (min == -1 || get_irg_dfn(pred) < min)) {
791 min = get_irg_dfn(pred);
798 /** Returns index of the predecessor with the largest dfn number. */
800 largest_dfn_pred(ir_graph *n)
802 int i, index = -2, max = -1;
804 int arity = get_irg_n_callees(n);
805 for (i = 0; i < arity; i++) {
806 ir_graph *pred = get_irg_callee(n, i);
807 if (is_irg_callee_backedge (n, i) || !irg_is_in_stack(pred)) continue;
808 if (get_irg_dfn(pred) > max) {
810 max = get_irg_dfn(pred);
819 find_tail(ir_graph *n) {
821 int i, res_index = -2;
824 if (!icfg && rm_cyclic_phis && remove_cyclic_phis (n)) return NULL;
826 m = stack[tos-1]; /* tos = top of stack */
827 if (is_head (m, n)) {
828 res_index = smallest_dfn_pred(m, 0);
829 if ((res_index == -2) && /* no smallest dfn pred found. */
833 if (m == n) return NULL; // Is this to catch Phi - self loops?
834 for (i = tos-2; i >= 0; --i) {
837 if (is_head (m, n)) {
838 res_index = smallest_dfn_pred (m, get_irg_dfn(m) + 1);
839 if (res_index == -2) /* no smallest dfn pred found. */
840 res_index = largest_dfn_pred (m);
842 if ((m == n) && (res_index == -2)) {
848 /* We should not walk past our selves on the stack: The upcoming nodes
849 are not in this loop. We assume a loop not reachable from Start. */
858 /* A dead loop not reachable from Start. */
859 for (i = tos-2; i >= 0; --i) {
861 if (is_endless_head (m, n)) {
862 res_index = smallest_dfn_pred (m, get_irg_dfn(m) + 1);
863 if (res_index == -2) /* no smallest dfn pred found. */
864 res_index = largest_dfn_pred (m);
867 if (m == n) { break; } /* It's not an unreachable loop, either. */
869 //assert(0 && "no head found on stack");
873 assert (res_index > -2);
875 set_irg_callee_backedge (m, res_index);
876 return get_irg_callee(m, res_index);
880 find_tail(ir_graph *n) {
882 int i, res_index = -2;
885 ir_graph *in_and_out = NULL;
886 ir_graph *only_in = NULL;
887 ir_graph *ip_in_and_out = NULL;
888 ir_graph *ip_only_in = NULL;
890 //printf("find tail for "); DDMG(n);
892 for (i = tos-1; i >= 0; --i) {
893 ir_graph *pred = (i < tos -1) ? stack[i+1] : n;
896 if (is_head (m, n)) {
897 //printf(" found 1a! "); DDM;
899 if (is_ip_head(pred, m)) {
900 //printf(" found 1b! "); DDM;
903 } else if (!ip_only_in && is_endless_head(m, n)) {
905 //printf(" found 2a! "); DDM;
906 if (is_ip_head(pred, m)) {
907 //printf(" found 2b! "); DDM;
910 } else if (is_ip_head(pred, m)) {
911 //printf(" found 3! "); DDM; This happens for self recursions in the second
912 //assert(0); scc iteration (the one to flip the loop.)
915 if (ip_in_and_out) break; /* That's what we really want. */
917 if (m == n) break; /* Don't walk past n on the stack! */
921 if (!in_and_out && !only_in)
922 /* There is no loop */
926 /* Is there a head in the callgraph without a head in the
928 assert(in_and_out || only_in);
930 m = (ip_in_and_out) ? ip_in_and_out : ip_only_in;
933 m = (in_and_out) ? in_and_out : only_in;
935 //printf("*** head is "); DDMG(m);
937 res_index = smallest_dfn_pred (m, get_irg_dfn(m) + 1);
938 if (res_index == -2) /* no smallest dfn pred found. */
939 res_index = largest_dfn_pred (m);
941 set_irg_callee_backedge (m, res_index);
942 res = get_irg_callee(m, res_index);
943 //printf("*** tail is "); DDMG(res);
949 /*-----------------------------------------------------------*
950 * The core algorithm. *
951 *-----------------------------------------------------------*/
954 static void cgscc(ir_graph *n) {
957 if (cg_irg_visited(n)) return;
958 mark_cg_irg_visited(n);
960 /* Initialize the node */
961 set_irg_dfn(n, current_dfn); /* Depth first number for this node */
962 set_irg_uplink(n, current_dfn); /* ... is default uplink. */
966 arity = get_irg_n_callees(n);
967 for (i = 0; i < arity; i++) {
969 if (is_irg_callee_backedge(n, i)) continue;
970 m = get_irg_callee(n, i);
972 /** This marks the backedge, but does it guarantee a correct loop tree? */
973 //if (m == n) { set_irg_callee_backedge(n, i); continue; }
976 if (irg_is_in_stack(m)) {
977 /* Uplink of m is smaller if n->m is a backedge.
978 Propagate the uplink to mark the cfloop. */
979 if (get_irg_uplink(m) < get_irg_uplink(n))
980 set_irg_uplink(n, get_irg_uplink(m));
984 if (get_irg_dfn(n) == get_irg_uplink(n)) {
985 /* This condition holds for
986 1) the node with the incoming backedge.
987 That is: We found a cfloop!
988 2) Straight line code, because no uplink has been propagated, so the
989 uplink still is the same as the dfn.
991 But n might not be a proper cfloop head for the analysis. Proper cfloop
992 heads are Block and Phi nodes. find_tail searches the stack for
993 Block's and Phi's and takes those nodes as cfloop heads for the current
994 cfloop instead and marks the incoming edge as backedge. */
996 ir_graph *tail = find_tail(n);
998 /* We have a cfloop, that is no straight line code,
999 because we found a cfloop head!
1000 Next actions: Open a new cfloop on the cfloop tree and
1001 try to find inner cfloops */
1004 ir_loop *l = new_loop();
1006 /* Remove the cfloop from the stack ... */
1007 pop_scc_unmark_visit (n);
1009 /* The current backedge has been marked, that is temporarily eliminated,
1010 by find tail. Start the scc algorithm
1011 anew on the subgraph thats left (the current cfloop without the backedge)
1012 in order to find more inner cfloops. */
1016 assert (cg_irg_visited(n));
1026 * reset the backedge information for all callers in all irgs
1028 static void reset_isbe(void) {
1029 int i, n_irgs = get_irp_n_irgs();
1031 for (i = 0; i < n_irgs; ++i) {
1032 ir_graph *irg = get_irp_irg(i);
1034 if (irg->caller_isbe)
1035 free(irg->caller_isbe);
1036 irg->caller_isbe = NULL;
1038 if (irg->callee_isbe)
1039 free(irg->callee_isbe);
1040 irg->callee_isbe = NULL;
1047 /* ----------------------------------------------------------------------------------- */
1048 /* Another algorithm to compute recursion nesting depth */
1049 /* Walk the callgraph. For each crossed edge increase the loop depth by the edge */
1050 /* weight. Assign graphs the maximal depth. */
1051 /* ----------------------------------------------------------------------------------- */
1053 static void compute_loop_depth (ir_graph *irg, void *env) {
1054 int current_nesting = *(int *) env;
1055 int old_nesting = irg->callgraph_loop_depth;
1056 int old_visited = get_cg_irg_visited(irg);
1061 if (cg_irg_visited(irg)) return;
1063 mark_cg_irg_visited(irg);
1065 //printf(" old: %d new %d master %d", old_visited, get_cg_irg_visited(irg), master_cg_visited); DDMG(irg);
1068 if (old_nesting < current_nesting)
1069 irg->callgraph_loop_depth = current_nesting;
1071 if (current_nesting > irp->max_callgraph_loop_depth)
1072 irp->max_callgraph_loop_depth = current_nesting;
1074 if ((old_visited +1 < get_cg_irg_visited(irg)) || /* not yet visited */
1075 (old_nesting < current_nesting)) { /* propagate larger nesting */
1076 /* Don't walk the graph, but a tree that is an unfolded graph. */
1077 n_callees = get_irg_n_callees(irg);
1078 for (i = 0; i < n_callees; i++) {
1079 ir_graph *m = get_irg_callee(irg, i);
1080 *(int *)env += get_irg_callee_loop_depth(irg, i);
1081 compute_loop_depth(m, env);
1082 *(int *)env -= get_irg_callee_loop_depth(irg, i);
1086 set_cg_irg_visited(irg, master_cg_visited-1);
1089 /* ------------------------------------------------------------------------------------ */
1090 /* Another algorithm to compute recursion nesting depth */
1091 /* Walk the callgraph. For each crossed loop increase the nesting depth by one. */
1092 /* Assign graphs the maximal nesting depth. Don't increase if passing loops more than */
1094 /* ------------------------------------------------------------------------------------ */
1097 /* For callees, we want to remember the Call nodes, too. */
1098 typedef struct ana_entry2 {
1099 ir_loop **loop_stack; /**< a stack of ir_loop entries */
1100 int tos; /**< the top of stack entry */
1101 int recursion_nesting;
1105 * push a loop entry on the stack
1107 static void push2(ana_entry2 *e, ir_loop *g) {
1108 if (ARR_LEN(e->loop_stack) == e->tos) {
1109 ARR_APP1(ir_loop *, e->loop_stack, g);
1111 e->loop_stack[e->tos] = g;
1117 * returns the top of stack and pop it
1119 static ir_loop *pop2(ana_entry2 *e) {
1120 return e->loop_stack[--e->tos];
1124 * check if a loop g in on the stack. Did not check the TOS.
1126 static int in_stack(ana_entry2 *e, ir_loop *g) {
1128 for (i = e->tos-1; i >= 0; --i) {
1129 if (e->loop_stack[i] == g) return 1;
1134 static void compute_rec_depth (ir_graph *irg, void *env) {
1135 ana_entry2 *e = (ana_entry2 *)env;
1136 ir_loop *l = irg->l;
1137 int depth, old_depth = irg->callgraph_recursion_depth;
1141 if (cg_irg_visited(irg)) return;
1142 mark_cg_irg_visited(irg);
1144 /* -- compute and set the new nesting value -- */
1145 if ((l != irp->outermost_cg_loop) && !in_stack(e, l)) {
1147 e->recursion_nesting++;
1150 depth = e->recursion_nesting;
1152 if (old_depth < depth)
1153 irg->callgraph_recursion_depth = depth;
1155 if (depth > irp->max_callgraph_recursion_depth)
1156 irp->max_callgraph_recursion_depth = depth;
1158 /* -- spread the nesting value -- */
1159 if (depth == 0 || old_depth < depth) {
1160 /* Don't walk the graph, but a tree that is an unfolded graph.
1161 Therefore we unset the visited flag at the end. */
1162 n_callees = get_irg_n_callees(irg);
1163 for (i = 0; i < n_callees; i++) {
1164 ir_graph *m = get_irg_callee(irg, i);
1165 compute_rec_depth(m, env);
1169 /* -- clean up -- */
1172 e->recursion_nesting--;
1174 set_cg_irg_visited(irg, master_cg_visited-1);
1178 /* ----------------------------------------------------------------------------------- */
1179 /* Another algorithm to compute the execution frequency of methods ignoring recursions. */
1180 /* Walk the callgraph. Ignore backedges. Use sum of execution frequencies of Call */
1181 /* nodes to evaluate a callgraph edge. */
1182 /* ----------------------------------------------------------------------------------- */
1184 /* Returns the method execution frequency of a graph. */
1185 double get_irg_method_execution_frequency (ir_graph *irg) {
1186 return irg->method_execution_frequency;
1190 * Increase the method execution frequency to freq if its current value is
1191 * smaller then this.
1193 static void set_irg_method_execution_frequency(ir_graph *irg, double freq) {
1194 irg->method_execution_frequency = freq;
1196 if (irp->max_method_execution_frequency < freq)
1197 irp->max_method_execution_frequency = freq;
1200 static void compute_method_execution_frequency(ir_graph *irg, void *env) {
1206 if (cg_irg_visited(irg)) return;
1208 /* We need the values of all predecessors (except backedges).
1209 So they must be marked. Else we will reach the node through
1210 one of the unmarked ones. */
1211 n_callers = get_irg_n_callers(irg);
1212 for (i = 0; i < n_callers; i++) {
1213 ir_graph *m = get_irg_caller(irg, i);
1214 if (is_irg_caller_backedge(irg, i)) continue;
1215 if (!cg_irg_visited(m)) {
1219 mark_cg_irg_visited(irg);
1221 /* Compute the new frequency. */
1224 for (i = 0; i < n_callers; i++) {
1225 if (! is_irg_caller_backedge(irg, i)) {
1226 double edge_freq = get_irg_caller_method_execution_frequency(irg, i);
1227 assert(edge_freq >= 0);
1234 /* A starting point: method only called from outside,
1235 or only backedges as predecessors. */
1239 set_irg_method_execution_frequency(irg, freq);
1242 n_callees = get_irg_n_callees(irg);
1243 for (i = 0; i < n_callees; i++) {
1244 compute_method_execution_frequency(get_irg_callee(irg, i), NULL);
1249 /* ----------------------------------------------------------------------------------- */
1250 /* The recursion stuff driver. */
1251 /* ----------------------------------------------------------------------------------- */
1253 /* Compute the backedges that represent recursions. */
1254 void find_callgraph_recursions(void) {
1255 int i, n_irgs = get_irp_n_irgs();
1259 /* -- compute the looptree. -- */
1261 /* The outermost graph. We start here. Then we start at all
1262 functions in irg list that are never called, then at the remaining
1263 unvisited ones. The third step is needed for functions that are not
1264 reachable from the outermost graph, but call themselves in a cycle. */
1265 assert(get_irp_main_irg());
1266 outermost_ir_graph = get_irp_main_irg();
1269 current_loop = NULL;
1270 new_loop(); /* sets current_loop */
1272 master_cg_visited++;
1273 cgscc(outermost_ir_graph);
1274 for (i = 0; i < n_irgs; i++) {
1275 ir_graph *irg = get_irp_irg(i);
1276 if (!cg_irg_visited(irg) && get_irg_n_callers(irg) == 0)
1279 for (i = 0; i < n_irgs; i++) {
1280 ir_graph *irg = get_irp_irg(i);
1281 if (!cg_irg_visited(irg))
1284 irp->outermost_cg_loop = current_loop;
1286 /* -- Reverse the backedge information. -- */
1287 for (i = 0; i < n_irgs; i++) {
1288 ir_graph *irg = get_irp_irg(i);
1289 int j, n_callees = get_irg_n_callees(irg);
1290 for (j = 0; j < n_callees; ++j) {
1291 if (is_irg_callee_backedge(irg, j))
1292 set_irg_caller_backedge(get_irg_callee(irg, j), irg);
1296 irp->callgraph_state = irp_callgraph_and_calltree_consistent;
1299 /* Compute interprocedural performance estimates. */
1300 void compute_performance_estimates(void) {
1301 int i, n_irgs = get_irp_n_irgs();
1302 int current_nesting;
1305 assert(get_irp_exec_freq_state() != exec_freq_none && "execution frequency not calculated");
1307 /* -- compute the loop depth -- */
1308 current_nesting = 0;
1309 irp->max_callgraph_loop_depth = 0;
1310 master_cg_visited += 2;
1311 //printf (" ** starting at "); DDMG(get_irp_main_irg());
1312 compute_loop_depth(get_irp_main_irg(), ¤t_nesting);
1313 for (i = 0; i < n_irgs; i++) {
1314 ir_graph *irg = get_irp_irg(i);
1315 if ((get_cg_irg_visited(irg) < master_cg_visited-1) &&
1316 get_irg_n_callers(irg) == 0) {
1317 compute_loop_depth(irg, ¤t_nesting);
1318 //printf (" ** starting at "); DDMG(irg);
1321 for (i = 0; i < n_irgs; i++) {
1322 ir_graph *irg = get_irp_irg(i);
1323 if (get_cg_irg_visited(irg) < master_cg_visited-1) {
1324 compute_loop_depth(irg, ¤t_nesting);
1325 //printf (" ** starting at "); DDMG(irg);
1330 /* -- compute the recursion depth -- */
1331 e.loop_stack = NEW_ARR_F(ir_loop *, 0);
1333 e.recursion_nesting = 0;
1335 irp->max_callgraph_recursion_depth = 0;
1337 master_cg_visited += 2;
1338 compute_rec_depth(get_irp_main_irg(), &e);
1339 //printf (" ++ starting at "); DDMG(get_irp_main_irg());
1340 for (i = 0; i < n_irgs; i++) {
1341 ir_graph *irg = get_irp_irg(i);
1342 if ((get_cg_irg_visited(irg) < master_cg_visited-1) &&
1343 get_irg_n_callers(irg) == 0) {
1344 compute_rec_depth(irg, &e);
1345 //printf (" ++ starting at "); DDMG(irg);
1348 for (i = 0; i < n_irgs; i++) {
1349 ir_graph *irg = get_irp_irg(i);
1350 if (get_cg_irg_visited(irg) < master_cg_visited-1) {
1351 compute_rec_depth(irg, &e);
1352 //printf (" ++ starting at "); DDMG(irg);
1356 DEL_ARR_F(e.loop_stack);
1358 /* -- compute the execution frequency -- */
1359 irp->max_method_execution_frequency = 0;
1360 master_cg_visited += 2;
1361 assert(get_irg_n_callers(get_irp_main_irg()) == 0);
1362 compute_method_execution_frequency(get_irp_main_irg(), NULL);
1363 for (i = 0; i < n_irgs; i++) {
1364 ir_graph *irg = get_irp_irg(i);
1365 if ((get_cg_irg_visited(irg) < master_cg_visited-1) &&
1366 get_irg_n_callers(irg) == 0) {
1367 compute_method_execution_frequency(irg, NULL);
1370 for (i = 0; i < n_irgs; i++) {
1371 ir_graph *irg = get_irp_irg(i);
1372 if (get_cg_irg_visited(irg) < master_cg_visited-1) {
1373 compute_method_execution_frequency(irg, NULL);
1378 /* Returns the maximal loop depth of all paths from an external visible method to
1380 int get_irg_loop_depth(ir_graph *irg) {
1381 assert(irp->callgraph_state == irp_callgraph_consistent ||
1382 irp->callgraph_state == irp_callgraph_and_calltree_consistent);
1383 return irg->callgraph_loop_depth;
1386 /* Returns the maximal recursion depth of all paths from an external visible method to
1388 int get_irg_recursion_depth(ir_graph *irg) {
1389 assert(irp->callgraph_state == irp_callgraph_and_calltree_consistent);
1390 return irg->callgraph_recursion_depth;
1393 /* Computes the interprocedural loop nesting information. */
1394 void analyse_loop_nesting_depth(void) {
1395 ir_entity **free_methods = NULL;
1398 /* establish preconditions. */
1399 if (get_irp_callee_info_state() != irg_callee_info_consistent) {
1400 cgana(&arr_len, &free_methods);
1403 if (irp_callgraph_consistent != get_irp_callgraph_state()) {
1404 compute_callgraph();
1407 find_callgraph_recursions();
1409 compute_performance_estimates();
1411 set_irp_loop_nesting_depth_state(loop_nesting_depth_consistent);
1415 loop_nesting_depth_state get_irp_loop_nesting_depth_state(void) {
1416 return irp->lnd_state;
1418 void set_irp_loop_nesting_depth_state(loop_nesting_depth_state s) {
1421 void set_irp_loop_nesting_depth_state_inconsistent(void) {
1422 if (irp->lnd_state == loop_nesting_depth_consistent)
1423 irp->lnd_state = loop_nesting_depth_inconsistent;