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) {
234 if (! is_Call(n)) return;
236 irg = get_irn_irg(n);
237 n_callees = get_Call_n_callees(n);
238 for (i = 0; i < n_callees; ++i) {
239 ir_entity *callee_e = get_Call_callee(n, i);
240 ir_graph *callee = get_entity_irg(callee_e);
244 cg_callee_entry *found;
249 pset_insert((pset *)callee->callers, irg, HASH_PTR(irg));
250 found = pset_find((pset *)irg->callees, &buf, HASH_PTR(callee));
251 if (found) { /* add Call node to list, compute new nesting. */
252 ir_node **arr = found->call_list;
253 ARR_APP1(ir_node *, arr, n);
254 found->call_list = arr;
255 } else { /* New node, add Call node and init nesting. */
256 found = (cg_callee_entry *)obstack_alloc(irg->obst, sizeof(*found));
258 found->call_list = NEW_ARR_F(ir_node *, 1);
259 found->call_list[0] = n;
260 found->max_depth = 0;
261 pset_insert((pset *)irg->callees, found, HASH_PTR(callee));
263 depth = get_loop_depth(get_irn_loop(get_nodes_block(n)));
264 found->max_depth = (depth > found->max_depth) ? depth : found->max_depth;
269 /** compare two ir graphs in a cg_callee_entry */
270 static int cg_callee_entry_cmp(const void *elt, const void *key) {
271 const cg_callee_entry *e1 = elt;
272 const cg_callee_entry *e2 = key;
273 return e1->irg != e2->irg;
276 /** compare two ir graphs */
277 static int graph_cmp(const void *elt, const void *key) {
278 const ir_graph *e1 = elt;
279 const ir_graph *e2 = key;
284 /* Construct and destruct the callgraph. */
285 void compute_callgraph(void) {
288 assert(! get_interprocedural_view()); /* Else walking will not reach the Call nodes. */
293 n_irgs = get_irp_n_irgs();
294 for (i = 0; i < n_irgs; ++i) {
295 ir_graph *irg = get_irp_irg(i);
296 assert(get_irg_callee_info_state(irg) == irg_callee_info_consistent);
297 irg->callees = (cg_callee_entry **)new_pset(cg_callee_entry_cmp, 8);
298 irg->callers = (ir_graph **)new_pset(graph_cmp, 8);
299 //construct_cf_backedges(irg);
302 /* Compute the call graph */
303 for (i = 0; i < n_irgs; ++i) {
304 ir_graph *irg = get_irp_irg(i);
305 construct_cf_backedges(irg); // We also find the maximal loop depth of a call.
306 irg_walk_graph(irg, ana_Call, NULL, NULL);
309 /* Change the sets to arrays. */
310 for (i = 0; i < n_irgs; ++i) {
312 cg_callee_entry *callee;
313 ir_graph *c, *irg = get_irp_irg(i);
314 pset *callee_set, *caller_set;
316 callee_set = (pset *)irg->callees;
317 count = pset_count(callee_set);
318 irg->callees = NEW_ARR_F(cg_callee_entry *, count);
319 irg->callee_isbe = NULL;
320 callee = pset_first(callee_set);
321 for (j = 0; j < count; ++j) {
322 irg->callees[j] = callee;
323 callee = pset_next(callee_set);
325 del_pset(callee_set);
326 assert(callee == NULL);
328 caller_set = (pset *)irg->callers;
329 count = pset_count(caller_set);
330 irg->callers = NEW_ARR_F(ir_graph *, count);
331 irg->caller_isbe = NULL;
332 c = pset_first(caller_set);
333 for (j = 0; j < count; ++j) {
335 c = pset_next(caller_set);
337 del_pset(caller_set);
340 set_irp_callgraph_state(irp_callgraph_consistent);
343 /* Destruct the callgraph. */
344 void free_callgraph(void) {
345 int i, n_irgs = get_irp_n_irgs();
346 for (i = 0; i < n_irgs; ++i) {
347 ir_graph *irg = get_irp_irg(i);
348 if (irg->callees) DEL_ARR_F(irg->callees);
349 if (irg->callers) DEL_ARR_F(irg->callers);
350 if (irg->callee_isbe) free(irg->callee_isbe);
351 if (irg->caller_isbe) free(irg->caller_isbe);
354 irg->callee_isbe = NULL;
355 irg->caller_isbe = NULL;
357 set_irp_callgraph_state(irp_callgraph_none);
360 /* ----------------------------------------------------------------------------------- */
361 /* A walker for the callgraph */
362 /* ----------------------------------------------------------------------------------- */
365 static void do_walk(ir_graph *irg, callgraph_walk_func *pre, callgraph_walk_func *post, void *env) {
368 if (cg_irg_visited(irg)) return;
369 mark_cg_irg_visited(irg);
374 n_callees = get_irg_n_callees(irg);
375 for (i = 0; i < n_callees; i++) {
376 ir_graph *m = get_irg_callee(irg, i);
377 do_walk(m, pre, post, env);
384 void callgraph_walk(callgraph_walk_func *pre, callgraph_walk_func *post, void *env) {
385 int i, n_irgs = get_irp_n_irgs();
388 do_walk(get_irp_main_irg(), pre, post, env);
389 for (i = 0; i < n_irgs; i++) {
390 ir_graph *irg = get_irp_irg(i);
391 if (!cg_irg_visited(irg) && get_irg_n_callers(irg) == 0)
392 do_walk(irg, pre, post, env);
394 for (i = 0; i < n_irgs; i++) {
395 ir_graph *irg = get_irp_irg(i);
396 if (!cg_irg_visited(irg))
397 do_walk(irg, pre, post, env);
401 /* ----------------------------------------------------------------------------------- */
402 /* loop construction algorithm */
403 /* ----------------------------------------------------------------------------------- */
405 static ir_graph *outermost_ir_graph; /**< The outermost graph the scc is computed
407 static ir_loop *current_loop; /**< Current cfloop construction is working
409 static int loop_node_cnt = 0; /**< Counts the number of allocated cfloop nodes.
410 Each cfloop node gets a unique number.
411 What for? ev. remove. @@@ */
412 static int current_dfn = 1; /**< Counter to generate depth first numbering
416 /*-----------------*/
417 /* Node attributes */
418 /*-----------------*/
420 typedef struct scc_info {
421 int in_stack; /**< Marks whether node is on the stack. */
422 int dfn; /**< Depth first search number. */
423 int uplink; /**< dfn number of ancestor. */
428 * allocates a new scc_info of the obstack
430 static INLINE scc_info *new_scc_info(void) {
431 scc_info *info = obstack_alloc (outermost_ir_graph->obst, sizeof(*info));
432 memset(info, 0, sizeof(*info));
437 * Returns non-zero if a graph was already visited.
440 cg_irg_visited(ir_graph *irg) {
441 scc_info *info = get_irg_link(irg);
442 assert(info && "missing call to init_scc");
443 return (info->visited >= master_cg_visited);
447 * Marks a graph as visited.
450 mark_cg_irg_visited(ir_graph *irg) {
451 scc_info *info = get_irg_link(irg);
452 assert(info && "missing call to init_scc");
453 info->visited = master_cg_visited;
457 * Set a graphs visited flag to i.
460 set_cg_irg_visited(ir_graph *irg, int i) {
461 scc_info *info = get_irg_link(irg);
462 assert(info && "missing call to init_scc");
467 * Returns the visited flag of a graph.
470 get_cg_irg_visited(ir_graph *irg) {
471 scc_info *info = get_irg_link(irg);
472 assert(info && "missing call to init_scc");
473 return info->visited;
477 mark_irg_in_stack(ir_graph *irg) {
478 scc_info *info = get_irg_link(irg);
479 assert(info && "missing call to init_scc");
484 mark_irg_not_in_stack(ir_graph *irg) {
485 scc_info *info = get_irg_link(irg);
486 assert(info && "missing call to init_scc");
491 irg_is_in_stack(ir_graph *irg) {
492 scc_info *info = get_irg_link(irg);
493 assert(info && "missing call to init_scc");
494 return info->in_stack;
498 set_irg_uplink(ir_graph *irg, int uplink) {
499 scc_info *info = get_irg_link(irg);
500 assert(info && "missing call to init_scc");
501 info->uplink = uplink;
505 get_irg_uplink(ir_graph *irg) {
506 scc_info *info = get_irg_link(irg);
507 assert(info && "missing call to init_scc");
512 set_irg_dfn(ir_graph *irg, int dfn) {
513 scc_info *info = get_irg_link(irg);
514 assert(info && "missing call to init_scc");
519 get_irg_dfn(ir_graph *irg) {
520 scc_info *info = get_irg_link(irg);
521 assert(info && "missing call to init_scc");
525 /**********************************************************************/
527 /**********************************************************************/
529 static ir_graph **stack = NULL;
530 static int tos = 0; /**< top of stack */
533 * Initialize the irg stack.
535 static INLINE void init_stack(void) {
537 ARR_RESIZE (ir_graph *, stack, 1000);
539 stack = NEW_ARR_F (ir_graph *, 1000);
545 * push a graph on the irg stack
546 * @param n the graph to be pushed
548 static INLINE void push(ir_graph *irg) {
549 if (tos == ARR_LEN (stack)) {
550 int nlen = ARR_LEN (stack) * 2;
551 ARR_RESIZE (ir_node *, stack, nlen);
554 mark_irg_in_stack(irg);
558 * return the topmost graph on the stack and pop it
560 static INLINE ir_graph *pop(void) {
561 ir_graph *irg = stack[--tos];
562 mark_irg_not_in_stack(irg);
567 * The nodes up to irg belong to the current loop.
568 * Removes them from the stack and adds them to the current loop.
570 static INLINE void pop_scc_to_loop(ir_graph *irg) {
576 set_irg_dfn(m, loop_node_cnt);
577 add_loop_node(current_loop, (ir_node *)m);
579 //m->callgraph_loop_depth = current_loop->depth;
583 /* GL ??? my last son is my grandson??? Removes cfloops with no
584 ir_nodes in them. Such loops have only another loop as son. (Why
585 can't they have two loops as sons? Does it never get that far? ) */
586 static void close_loop(ir_loop *l) {
587 int last = get_loop_n_elements(l) - 1;
588 loop_element lelement = get_loop_element(l, last);
589 ir_loop *last_son = lelement.son;
591 if (get_kind(last_son) == k_ir_loop &&
592 get_loop_n_elements(last_son) == 1) {
595 lelement = get_loop_element(last_son, 0);
597 if(get_kind(gson) == k_ir_loop) {
598 loop_element new_last_son;
600 gson -> outer_loop = l;
601 new_last_son.son = gson;
602 l -> children[last] = new_last_son;
610 * Removes and unmarks all nodes up to n from the stack.
611 * The nodes must be visited once more to assign them to a scc.
613 static INLINE void pop_scc_unmark_visit(ir_graph *n) {
618 set_cg_irg_visited(m, 0);
622 /**********************************************************************/
623 /* The loop data structure. **/
624 /**********************************************************************/
627 * Allocates a new loop as son of current_loop. Sets current_loop
628 * to the new loop and returns the father.
630 static ir_loop *new_loop(void) {
631 ir_loop *father, *son;
633 father = current_loop;
635 son = obstack_alloc(outermost_ir_graph->obst, sizeof(*son));
636 memset(son, 0, sizeof(*son));
637 son->kind = k_ir_loop;
638 son->children = NEW_ARR_F (loop_element, 0);
642 son->outer_loop = father;
643 add_loop_son(father, son);
644 son->depth = father->depth + 1;
645 } else { /* The root loop */
646 son->outer_loop = son;
651 son->loop_nr = get_irp_new_node_nr();
659 /**********************************************************************/
660 /* Constructing and destructing the loop/backedge information. **/
661 /**********************************************************************/
663 /* Initialization steps. **********************************************/
674 n_irgs = get_irp_n_irgs();
675 for (i = 0; i < n_irgs; ++i) {
676 ir_graph *irg = get_irp_irg(i);
677 set_irg_link(irg, new_scc_info());
678 irg->callgraph_recursion_depth = 0;
679 irg->callgraph_loop_depth = 0;
683 /** Returns non-zero if n is a loop header, i.e., it is a Block node
684 * and has predecessors within the cfloop and out of the cfloop.
686 * @param root: only needed for assertion.
689 is_head(ir_graph *n, ir_graph *root)
692 int some_outof_loop = 0, some_in_loop = 0;
694 arity = get_irg_n_callees(n);
695 for (i = 0; i < arity; i++) {
696 ir_graph *pred = get_irg_callee(n, i);
697 if (is_irg_callee_backedge(n, i)) continue;
698 if (!irg_is_in_stack(pred)) {
701 if (get_irg_uplink(pred) < get_irg_uplink(root)) {
702 assert(get_irg_uplink(pred) >= get_irg_uplink(root));
708 return some_outof_loop & some_in_loop;
712 * Returns non-zero if n is possible loop head of an endless loop.
713 * I.e., it is a Block, Phi or Filter node and has only predecessors
715 * @arg root: only needed for assertion.
718 is_endless_head(ir_graph *n, ir_graph *root)
721 int some_outof_loop = 0, some_in_loop = 0;
723 arity = get_irg_n_callees(n);
724 for (i = 0; i < arity; i++) {
725 ir_graph *pred = get_irg_callee(n, i);
727 if (is_irg_callee_backedge(n, i)) { continue; }
728 if (!irg_is_in_stack(pred)) {
731 if(get_irg_uplink(pred) < get_irg_uplink(root)) {
732 assert(get_irg_uplink(pred) >= get_irg_uplink(root));
738 return !some_outof_loop & some_in_loop;
743 * Check whether there is a parallel edge in the ip control flow.
747 is_ip_head(ir_graph *n, ir_graph *pred)
750 int iv_rem = get_interprocedural_view();
751 set_interprocedural_view(1);
753 ir_node *sblock = get_irg_start_block(n);
754 int i, arity = get_Block_n_cfgpreds(sblock);
756 //printf(" edge from "); DDMG(n);
757 //printf(" to pred "); DDMG(pred);
758 //printf(" sblock "); DDMN(sblock);
760 for (i = 0; i < arity; i++) {
761 ir_node *pred_cfop = skip_Proj(get_Block_cfgpred(sblock, i));
762 //printf(" "); DDMN(pred_cfop);
763 if (get_irn_op(pred_cfop) == op_CallBegin) { /* could be Unknown */
764 ir_graph *ip_pred = get_irn_irg(pred_cfop);
765 //printf(" "); DDMG(ip_pred);
766 if ((ip_pred == pred) && is_backedge(sblock, i)) {
767 //printf(" found\n");
773 set_interprocedural_view(iv_rem);
778 * Returns index of the predecessor with the smallest dfn number
779 * greater-equal than limit.
782 smallest_dfn_pred(ir_graph *n, int limit)
784 int i, index = -2, min = -1;
786 int arity = get_irg_n_callees(n);
787 for (i = 0; i < arity; i++) {
788 ir_graph *pred = get_irg_callee(n, i);
789 if (is_irg_callee_backedge(n, i) || !irg_is_in_stack(pred)) continue;
790 if (get_irg_dfn(pred) >= limit && (min == -1 || get_irg_dfn(pred) < min)) {
792 min = get_irg_dfn(pred);
799 /** Returns index of the predecessor with the largest dfn number. */
801 largest_dfn_pred(ir_graph *n)
803 int i, index = -2, max = -1;
805 int arity = get_irg_n_callees(n);
806 for (i = 0; i < arity; i++) {
807 ir_graph *pred = get_irg_callee(n, i);
808 if (is_irg_callee_backedge (n, i) || !irg_is_in_stack(pred)) continue;
809 if (get_irg_dfn(pred) > max) {
811 max = get_irg_dfn(pred);
820 find_tail(ir_graph *n) {
822 int i, res_index = -2;
825 if (!icfg && rm_cyclic_phis && remove_cyclic_phis (n)) return NULL;
827 m = stack[tos-1]; /* tos = top of stack */
828 if (is_head (m, n)) {
829 res_index = smallest_dfn_pred(m, 0);
830 if ((res_index == -2) && /* no smallest dfn pred found. */
834 if (m == n) return NULL; // Is this to catch Phi - self loops?
835 for (i = tos-2; i >= 0; --i) {
838 if (is_head (m, n)) {
839 res_index = smallest_dfn_pred (m, get_irg_dfn(m) + 1);
840 if (res_index == -2) /* no smallest dfn pred found. */
841 res_index = largest_dfn_pred (m);
843 if ((m == n) && (res_index == -2)) {
849 /* We should not walk past our selves on the stack: The upcoming nodes
850 are not in this loop. We assume a loop not reachable from Start. */
859 /* A dead loop not reachable from Start. */
860 for (i = tos-2; i >= 0; --i) {
862 if (is_endless_head (m, n)) {
863 res_index = smallest_dfn_pred (m, get_irg_dfn(m) + 1);
864 if (res_index == -2) /* no smallest dfn pred found. */
865 res_index = largest_dfn_pred (m);
868 if (m == n) { break; } /* It's not an unreachable loop, either. */
870 //assert(0 && "no head found on stack");
874 assert (res_index > -2);
876 set_irg_callee_backedge (m, res_index);
877 return get_irg_callee(m, res_index);
881 find_tail(ir_graph *n) {
883 int i, res_index = -2;
886 ir_graph *in_and_out = NULL;
887 ir_graph *only_in = NULL;
888 ir_graph *ip_in_and_out = NULL;
889 ir_graph *ip_only_in = NULL;
891 //printf("find tail for "); DDMG(n);
893 for (i = tos-1; i >= 0; --i) {
894 ir_graph *pred = (i < tos -1) ? stack[i+1] : n;
897 if (is_head (m, n)) {
898 //printf(" found 1a! "); DDM;
900 if (is_ip_head(pred, m)) {
901 //printf(" found 1b! "); DDM;
904 } else if (!ip_only_in && is_endless_head(m, n)) {
906 //printf(" found 2a! "); DDM;
907 if (is_ip_head(pred, m)) {
908 //printf(" found 2b! "); DDM;
911 } else if (is_ip_head(pred, m)) {
912 //printf(" found 3! "); DDM; This happens for self recursions in the second
913 //assert(0); scc iteration (the one to flip the loop.)
916 if (ip_in_and_out) break; /* That's what we really want. */
918 if (m == n) break; /* Don't walk past n on the stack! */
922 if (!in_and_out && !only_in)
923 /* There is no loop */
927 /* Is there a head in the callgraph without a head in the
929 assert(in_and_out || only_in);
931 m = (ip_in_and_out) ? ip_in_and_out : ip_only_in;
934 m = (in_and_out) ? in_and_out : only_in;
936 //printf("*** head is "); DDMG(m);
938 res_index = smallest_dfn_pred (m, get_irg_dfn(m) + 1);
939 if (res_index == -2) /* no smallest dfn pred found. */
940 res_index = largest_dfn_pred (m);
942 set_irg_callee_backedge (m, res_index);
943 res = get_irg_callee(m, res_index);
944 //printf("*** tail is "); DDMG(res);
950 /*-----------------------------------------------------------*
951 * The core algorithm. *
952 *-----------------------------------------------------------*/
955 static void cgscc(ir_graph *n) {
958 if (cg_irg_visited(n)) return;
959 mark_cg_irg_visited(n);
961 /* Initialize the node */
962 set_irg_dfn(n, current_dfn); /* Depth first number for this node */
963 set_irg_uplink(n, current_dfn); /* ... is default uplink. */
967 arity = get_irg_n_callees(n);
968 for (i = 0; i < arity; i++) {
970 if (is_irg_callee_backedge(n, i)) continue;
971 m = get_irg_callee(n, i);
973 /** This marks the backedge, but does it guarantee a correct loop tree? */
974 //if (m == n) { set_irg_callee_backedge(n, i); continue; }
977 if (irg_is_in_stack(m)) {
978 /* Uplink of m is smaller if n->m is a backedge.
979 Propagate the uplink to mark the cfloop. */
980 if (get_irg_uplink(m) < get_irg_uplink(n))
981 set_irg_uplink(n, get_irg_uplink(m));
985 if (get_irg_dfn(n) == get_irg_uplink(n)) {
986 /* This condition holds for
987 1) the node with the incoming backedge.
988 That is: We found a cfloop!
989 2) Straight line code, because no uplink has been propagated, so the
990 uplink still is the same as the dfn.
992 But n might not be a proper cfloop head for the analysis. Proper cfloop
993 heads are Block and Phi nodes. find_tail searches the stack for
994 Block's and Phi's and takes those nodes as cfloop heads for the current
995 cfloop instead and marks the incoming edge as backedge. */
997 ir_graph *tail = find_tail(n);
999 /* We have a cfloop, that is no straight line code,
1000 because we found a cfloop head!
1001 Next actions: Open a new cfloop on the cfloop tree and
1002 try to find inner cfloops */
1005 ir_loop *l = new_loop();
1007 /* Remove the cfloop from the stack ... */
1008 pop_scc_unmark_visit (n);
1010 /* The current backedge has been marked, that is temporarily eliminated,
1011 by find tail. Start the scc algorithm
1012 anew on the subgraph thats left (the current cfloop without the backedge)
1013 in order to find more inner cfloops. */
1017 assert (cg_irg_visited(n));
1027 * reset the backedge information for all callers in all irgs
1029 static void reset_isbe(void) {
1030 int i, n_irgs = get_irp_n_irgs();
1032 for (i = 0; i < n_irgs; ++i) {
1033 ir_graph *irg = get_irp_irg(i);
1035 if (irg->caller_isbe)
1036 free(irg->caller_isbe);
1037 irg->caller_isbe = NULL;
1039 if (irg->callee_isbe)
1040 free(irg->callee_isbe);
1041 irg->callee_isbe = NULL;
1048 /* ----------------------------------------------------------------------------------- */
1049 /* Another algorithm to compute recursion nesting depth */
1050 /* Walk the callgraph. For each crossed edge increase the loop depth by the edge */
1051 /* weight. Assign graphs the maximal depth. */
1052 /* ----------------------------------------------------------------------------------- */
1054 static void compute_loop_depth (ir_graph *irg, void *env) {
1055 int current_nesting = *(int *) env;
1056 int old_nesting = irg->callgraph_loop_depth;
1057 int old_visited = get_cg_irg_visited(irg);
1062 if (cg_irg_visited(irg)) return;
1064 mark_cg_irg_visited(irg);
1066 //printf(" old: %d new %d master %d", old_visited, get_cg_irg_visited(irg), master_cg_visited); DDMG(irg);
1069 if (old_nesting < current_nesting)
1070 irg->callgraph_loop_depth = current_nesting;
1072 if (current_nesting > irp->max_callgraph_loop_depth)
1073 irp->max_callgraph_loop_depth = current_nesting;
1075 if ((old_visited +1 < get_cg_irg_visited(irg)) || /* not yet visited */
1076 (old_nesting < current_nesting)) { /* propagate larger nesting */
1077 /* Don't walk the graph, but a tree that is an unfolded graph. */
1078 n_callees = get_irg_n_callees(irg);
1079 for (i = 0; i < n_callees; i++) {
1080 ir_graph *m = get_irg_callee(irg, i);
1081 *(int *)env += get_irg_callee_loop_depth(irg, i);
1082 compute_loop_depth(m, env);
1083 *(int *)env -= get_irg_callee_loop_depth(irg, i);
1087 set_cg_irg_visited(irg, master_cg_visited-1);
1090 /* ------------------------------------------------------------------------------------ */
1091 /* Another algorithm to compute recursion nesting depth */
1092 /* Walk the callgraph. For each crossed loop increase the nesting depth by one. */
1093 /* Assign graphs the maximal nesting depth. Don't increase if passing loops more than */
1095 /* ------------------------------------------------------------------------------------ */
1098 /* For callees, we want to remember the Call nodes, too. */
1099 typedef struct ana_entry2 {
1100 ir_loop **loop_stack; /**< a stack of ir_loop entries */
1101 int tos; /**< the top of stack entry */
1102 int recursion_nesting;
1106 * push a loop entry on the stack
1108 static void push2(ana_entry2 *e, ir_loop *g) {
1109 if (ARR_LEN(e->loop_stack) == e->tos) {
1110 ARR_APP1(ir_loop *, e->loop_stack, g);
1112 e->loop_stack[e->tos] = g;
1118 * returns the top of stack and pop it
1120 static ir_loop *pop2(ana_entry2 *e) {
1121 return e->loop_stack[--e->tos];
1125 * check if a loop g in on the stack. Did not check the TOS.
1127 static int in_stack(ana_entry2 *e, ir_loop *g) {
1129 for (i = e->tos-1; i >= 0; --i) {
1130 if (e->loop_stack[i] == g) return 1;
1135 static void compute_rec_depth (ir_graph *irg, void *env) {
1136 ana_entry2 *e = (ana_entry2 *)env;
1137 ir_loop *l = irg->l;
1138 int depth, old_depth = irg->callgraph_recursion_depth;
1142 if (cg_irg_visited(irg)) return;
1143 mark_cg_irg_visited(irg);
1145 /* -- compute and set the new nesting value -- */
1146 if ((l != irp->outermost_cg_loop) && !in_stack(e, l)) {
1148 e->recursion_nesting++;
1151 depth = e->recursion_nesting;
1153 if (old_depth < depth)
1154 irg->callgraph_recursion_depth = depth;
1156 if (depth > irp->max_callgraph_recursion_depth)
1157 irp->max_callgraph_recursion_depth = depth;
1159 /* -- spread the nesting value -- */
1160 if (depth == 0 || old_depth < depth) {
1161 /* Don't walk the graph, but a tree that is an unfolded graph.
1162 Therefore we unset the visited flag at the end. */
1163 n_callees = get_irg_n_callees(irg);
1164 for (i = 0; i < n_callees; i++) {
1165 ir_graph *m = get_irg_callee(irg, i);
1166 compute_rec_depth(m, env);
1170 /* -- clean up -- */
1173 e->recursion_nesting--;
1175 set_cg_irg_visited(irg, master_cg_visited-1);
1179 /* ----------------------------------------------------------------------------------- */
1180 /* Another algorithm to compute the execution frequency of methods ignoring recursions. */
1181 /* Walk the callgraph. Ignore backedges. Use sum of execution frequencies of Call */
1182 /* nodes to evaluate a callgraph edge. */
1183 /* ----------------------------------------------------------------------------------- */
1185 /* Returns the method execution frequency of a graph. */
1186 double get_irg_method_execution_frequency (ir_graph *irg) {
1187 return irg->method_execution_frequency;
1191 * Increase the method execution frequency to freq if its current value is
1192 * smaller then this.
1194 static void set_irg_method_execution_frequency(ir_graph *irg, double freq) {
1195 irg->method_execution_frequency = freq;
1197 if (irp->max_method_execution_frequency < freq)
1198 irp->max_method_execution_frequency = freq;
1201 static void compute_method_execution_frequency(ir_graph *irg, void *env) {
1208 if (cg_irg_visited(irg)) return;
1210 /* We need the values of all predecessors (except backedges).
1211 So they must be marked. Else we will reach the node through
1212 one of the unmarked ones. */
1213 n_callers = get_irg_n_callers(irg);
1214 for (i = 0; i < n_callers; i++) {
1215 ir_graph *m = get_irg_caller(irg, i);
1216 if (is_irg_caller_backedge(irg, i)) continue;
1217 if (!cg_irg_visited(m)) {
1221 mark_cg_irg_visited(irg);
1223 /* Compute the new frequency. */
1226 for (i = 0; i < n_callers; i++) {
1227 if (! is_irg_caller_backedge(irg, i)) {
1228 double edge_freq = get_irg_caller_method_execution_frequency(irg, i);
1229 assert(edge_freq >= 0);
1236 /* A starting point: method only called from outside,
1237 or only backedges as predecessors. */
1241 set_irg_method_execution_frequency(irg, freq);
1244 n_callees = get_irg_n_callees(irg);
1245 for (i = 0; i < n_callees; i++) {
1246 compute_method_execution_frequency(get_irg_callee(irg, i), NULL);
1251 /* ----------------------------------------------------------------------------------- */
1252 /* The recursion stuff driver. */
1253 /* ----------------------------------------------------------------------------------- */
1255 /* Compute the backedges that represent recursions. */
1256 void find_callgraph_recursions(void) {
1257 int i, n_irgs = get_irp_n_irgs();
1261 /* -- compute the looptree. -- */
1263 /* The outermost graph. We start here. Then we start at all
1264 functions in irg list that are never called, then at the remaining
1265 unvisited ones. The third step is needed for functions that are not
1266 reachable from the outermost graph, but call themselves in a cycle. */
1267 assert(get_irp_main_irg());
1268 outermost_ir_graph = get_irp_main_irg();
1271 current_loop = NULL;
1272 new_loop(); /* sets current_loop */
1274 master_cg_visited++;
1275 cgscc(outermost_ir_graph);
1276 for (i = 0; i < n_irgs; i++) {
1277 ir_graph *irg = get_irp_irg(i);
1278 if (!cg_irg_visited(irg) && get_irg_n_callers(irg) == 0)
1281 for (i = 0; i < n_irgs; i++) {
1282 ir_graph *irg = get_irp_irg(i);
1283 if (!cg_irg_visited(irg))
1286 irp->outermost_cg_loop = current_loop;
1288 /* -- Reverse the backedge information. -- */
1289 for (i = 0; i < n_irgs; i++) {
1290 ir_graph *irg = get_irp_irg(i);
1291 int j, n_callees = get_irg_n_callees(irg);
1292 for (j = 0; j < n_callees; ++j) {
1293 if (is_irg_callee_backedge(irg, j))
1294 set_irg_caller_backedge(get_irg_callee(irg, j), irg);
1298 irp->callgraph_state = irp_callgraph_and_calltree_consistent;
1301 /* Compute interprocedural performance estimates. */
1302 void compute_performance_estimates(void) {
1303 int i, n_irgs = get_irp_n_irgs();
1304 int current_nesting;
1307 assert(get_irp_exec_freq_state() != exec_freq_none && "execution frequency not calculated");
1309 /* -- compute the loop depth -- */
1310 current_nesting = 0;
1311 irp->max_callgraph_loop_depth = 0;
1312 master_cg_visited += 2;
1313 //printf (" ** starting at "); DDMG(get_irp_main_irg());
1314 compute_loop_depth(get_irp_main_irg(), ¤t_nesting);
1315 for (i = 0; i < n_irgs; i++) {
1316 ir_graph *irg = get_irp_irg(i);
1317 if ((get_cg_irg_visited(irg) < master_cg_visited-1) &&
1318 get_irg_n_callers(irg) == 0) {
1319 compute_loop_depth(irg, ¤t_nesting);
1320 //printf (" ** starting at "); DDMG(irg);
1323 for (i = 0; i < n_irgs; i++) {
1324 ir_graph *irg = get_irp_irg(i);
1325 if (get_cg_irg_visited(irg) < master_cg_visited-1) {
1326 compute_loop_depth(irg, ¤t_nesting);
1327 //printf (" ** starting at "); DDMG(irg);
1332 /* -- compute the recursion depth -- */
1333 e.loop_stack = NEW_ARR_F(ir_loop *, 0);
1335 e.recursion_nesting = 0;
1337 irp->max_callgraph_recursion_depth = 0;
1339 master_cg_visited += 2;
1340 compute_rec_depth(get_irp_main_irg(), &e);
1341 //printf (" ++ starting at "); DDMG(get_irp_main_irg());
1342 for (i = 0; i < n_irgs; i++) {
1343 ir_graph *irg = get_irp_irg(i);
1344 if ((get_cg_irg_visited(irg) < master_cg_visited-1) &&
1345 get_irg_n_callers(irg) == 0) {
1346 compute_rec_depth(irg, &e);
1347 //printf (" ++ starting at "); DDMG(irg);
1350 for (i = 0; i < n_irgs; i++) {
1351 ir_graph *irg = get_irp_irg(i);
1352 if (get_cg_irg_visited(irg) < master_cg_visited-1) {
1353 compute_rec_depth(irg, &e);
1354 //printf (" ++ starting at "); DDMG(irg);
1358 DEL_ARR_F(e.loop_stack);
1360 /* -- compute the execution frequency -- */
1361 irp->max_method_execution_frequency = 0;
1362 master_cg_visited += 2;
1363 assert(get_irg_n_callers(get_irp_main_irg()) == 0);
1364 compute_method_execution_frequency(get_irp_main_irg(), NULL);
1365 for (i = 0; i < n_irgs; i++) {
1366 ir_graph *irg = get_irp_irg(i);
1367 if ((get_cg_irg_visited(irg) < master_cg_visited-1) &&
1368 get_irg_n_callers(irg) == 0) {
1369 compute_method_execution_frequency(irg, NULL);
1372 for (i = 0; i < n_irgs; i++) {
1373 ir_graph *irg = get_irp_irg(i);
1374 if (get_cg_irg_visited(irg) < master_cg_visited-1) {
1375 compute_method_execution_frequency(irg, NULL);
1380 /* Returns the maximal loop depth of all paths from an external visible method to
1382 int get_irg_loop_depth(ir_graph *irg) {
1383 assert(irp->callgraph_state == irp_callgraph_consistent ||
1384 irp->callgraph_state == irp_callgraph_and_calltree_consistent);
1385 return irg->callgraph_loop_depth;
1388 /* Returns the maximal recursion depth of all paths from an external visible method to
1390 int get_irg_recursion_depth(ir_graph *irg) {
1391 assert(irp->callgraph_state == irp_callgraph_and_calltree_consistent);
1392 return irg->callgraph_recursion_depth;
1395 /* Computes the interprocedural loop nesting information. */
1396 void analyse_loop_nesting_depth(void) {
1397 ir_entity **free_methods = NULL;
1400 /* establish preconditions. */
1401 if (get_irp_callee_info_state() != irg_callee_info_consistent) {
1402 cgana(&arr_len, &free_methods);
1405 if (irp_callgraph_consistent != get_irp_callgraph_state()) {
1406 compute_callgraph();
1409 find_callgraph_recursions();
1411 compute_performance_estimates();
1413 set_irp_loop_nesting_depth_state(loop_nesting_depth_consistent);
1417 loop_nesting_depth_state get_irp_loop_nesting_depth_state(void) {
1418 return irp->lnd_state;
1420 void set_irp_loop_nesting_depth_state(loop_nesting_depth_state s) {
1423 void set_irp_loop_nesting_depth_state_inconsistent(void) {
1424 if (irp->lnd_state == loop_nesting_depth_consistent)
1425 irp->lnd_state = loop_nesting_depth_inconsistent;