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
38 #include "callgraph.h"
42 #include "irgraph_t.h"
46 #include "execution_frequency.h"
51 #include "raw_bitset.h"
55 static int master_cg_visited = 0;
56 static INLINE int cg_irg_visited (ir_graph *n);
57 static INLINE void mark_cg_irg_visited(ir_graph *n);
58 static INLINE void set_cg_irg_visited (ir_graph *n, int i);
60 /** Returns the callgraph state of the program representation. */
61 irp_callgraph_state get_irp_callgraph_state(void) {
62 return irp->callgraph_state;
65 /* Sets the callgraph state of the program representation. */
66 void set_irp_callgraph_state(irp_callgraph_state s) {
67 irp->callgraph_state = s;
70 /* Returns the number of procedures that call the given irg. */
71 int get_irg_n_callers(ir_graph *irg) {
72 if (irg->callers) return ARR_LEN(irg->callers);
76 /* Returns the caller at position pos. */
77 ir_graph *get_irg_caller(ir_graph *irg, int pos) {
78 assert(pos >= 0 && pos < get_irg_n_callers(irg));
79 if (irg->callers) return irg->callers[pos];
83 /* Returns non-zero if the caller at position pos is "a backedge", i.e. a recursion. */
84 int is_irg_caller_backedge(ir_graph *irg, int pos) {
85 assert(pos >= 0 && pos < get_irg_n_callers(irg));
86 return irg->caller_isbe != NULL ? rbitset_is_set(irg->caller_isbe, pos) : 0;
89 /** Search the caller in the list of all callers and set it's backedge property. */
90 static void set_irg_caller_backedge(ir_graph *irg, ir_graph *caller) {
91 int i, n_callers = get_irg_n_callers(irg);
93 /* allocate a new array on demand */
94 if (irg->caller_isbe == NULL)
95 irg->caller_isbe = rbitset_malloc(n_callers);
96 for (i = 0; i < n_callers; ++i) {
97 if (get_irg_caller(irg, i) == caller) {
98 rbitset_set(irg->caller_isbe, i);
104 /* Returns non-zero if the irg has a backedge caller. */
105 int has_irg_caller_backedge(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(ir_graph *callee, int pos_caller) {
122 ir_graph *caller = get_irg_caller(callee, pos_caller);
123 /* search the other relation for the corresponding edge. */
125 int i, n_callees = get_irg_n_callees(caller);
126 for (i = 0; i < n_callees; ++i) {
127 if (get_irg_callee(caller, i) == callee) {
133 assert(pos_callee >= 0);
138 /* Returns the maximal loop depth of call nodes that call along this edge. */
139 int get_irg_caller_loop_depth(ir_graph *irg, int pos) {
140 ir_graph *caller = get_irg_caller(irg, pos);
141 int pos_callee = reverse_pos(irg, pos);
143 return get_irg_callee_loop_depth(caller, pos_callee);
147 /* Returns the number of procedures that are called by the given irg. */
148 int get_irg_n_callees(ir_graph *irg) {
149 if (irg->callees) return ARR_LEN(irg->callees);
153 /* Returns the callee at position pos. */
154 ir_graph *get_irg_callee(ir_graph *irg, int pos) {
155 assert(pos >= 0 && pos < get_irg_n_callees(irg));
156 if (irg->callees) return irg->callees[pos]->irg;
160 /* Returns non-zero if the callee at position pos is "a backedge", i.e. a recursion. */
161 int is_irg_callee_backedge(ir_graph *irg, int pos) {
162 assert(pos >= 0 && pos < get_irg_n_callees(irg));
163 return irg->callee_isbe != NULL ? rbitset_is_set(irg->callee_isbe, pos) : 0;
166 /* Returns non-zero if the irg has a backedge callee. */
167 int has_irg_callee_backedge(ir_graph *irg) {
168 int i, n_callees = get_irg_n_callees(irg);
170 if (irg->callee_isbe != NULL) {
171 for (i = 0; i < n_callees; ++i)
172 if (rbitset_is_set(irg->callee_isbe, i))
179 * Mark the callee at position pos as a backedge.
181 static void set_irg_callee_backedge(ir_graph *irg, int pos) {
182 int n = get_irg_n_callees(irg);
184 /* allocate a new array on demand */
185 if (irg->callee_isbe == NULL)
186 irg->callee_isbe = rbitset_malloc(n);
187 assert(pos >= 0 && pos < n);
188 rbitset_set(irg->callee_isbe, pos);
191 /* Returns the maximal loop depth of call nodes that call along this edge. */
192 int get_irg_callee_loop_depth(ir_graph *irg, int pos) {
193 assert(pos >= 0 && pos < get_irg_n_callees(irg));
194 if (irg->callees) return irg->callees[pos]->max_depth;
199 double get_irg_callee_execution_frequency(ir_graph *irg, int pos) {
200 ir_node **arr = irg->callees[pos]->call_list;
201 int i, n_Calls = ARR_LEN(arr);
204 for (i = 0; i < n_Calls; ++i) {
205 freq += get_irn_exec_freq(arr[i]);
210 double get_irg_callee_method_execution_frequency(ir_graph *irg, int pos) {
211 double call_freq = get_irg_callee_execution_frequency(irg, pos);
212 double meth_freq = get_irg_method_execution_frequency(irg);
213 return call_freq * meth_freq;
217 double get_irg_caller_method_execution_frequency(ir_graph *irg, int pos) {
218 ir_graph *caller = get_irg_caller(irg, pos);
219 int pos_callee = reverse_pos(irg, pos);
221 return get_irg_callee_method_execution_frequency(caller, pos_callee);
226 /* --------------------- Compute the callgraph ------------------------ */
229 * Walker called by compute_callgraph(), analyses all Call nodes.
231 static void ana_Call(ir_node *n, void *env) {
236 if (! is_Call(n)) return;
238 irg = get_irn_irg(n);
239 n_callees = get_Call_n_callees(n);
240 for (i = 0; i < n_callees; ++i) {
241 ir_entity *callee_e = get_Call_callee(n, i);
242 ir_graph *callee = get_entity_irg(callee_e);
246 cg_callee_entry *found;
251 pset_insert((pset *)callee->callers, irg, HASH_PTR(irg));
252 found = pset_find((pset *)irg->callees, &buf, HASH_PTR(callee));
253 if (found) { /* add Call node to list, compute new nesting. */
254 ir_node **arr = found->call_list;
255 ARR_APP1(ir_node *, arr, n);
256 found->call_list = arr;
257 } else { /* New node, add Call node and init nesting. */
258 found = (cg_callee_entry *)obstack_alloc(irg->obst, sizeof(*found));
260 found->call_list = NEW_ARR_F(ir_node *, 1);
261 found->call_list[0] = n;
262 found->max_depth = 0;
263 pset_insert((pset *)irg->callees, found, HASH_PTR(callee));
265 depth = get_loop_depth(get_irn_loop(get_nodes_block(n)));
266 found->max_depth = (depth > found->max_depth) ? depth : found->max_depth;
271 /** compare two ir graphs in a cg_callee_entry */
272 static int cg_callee_entry_cmp(const void *elt, const void *key) {
273 const cg_callee_entry *e1 = elt;
274 const cg_callee_entry *e2 = key;
275 return e1->irg != e2->irg;
278 /** compare two ir graphs for pointer identity */
279 static int graph_cmp(const void *elt, const void *key) {
280 const ir_graph *e1 = elt;
281 const ir_graph *e2 = key;
286 /* Construct and destruct the callgraph. */
287 void compute_callgraph(void) {
290 #ifdef INTERPROCEDURAL_VIEW
291 assert(! get_interprocedural_view()); /* Else walking will not reach the Call nodes. */
297 n_irgs = get_irp_n_irgs();
298 for (i = 0; i < n_irgs; ++i) {
299 ir_graph *irg = get_irp_irg(i);
300 assert(get_irg_callee_info_state(irg) == irg_callee_info_consistent);
301 irg->callees = (cg_callee_entry **)new_pset(cg_callee_entry_cmp, 8);
302 irg->callers = (ir_graph **)new_pset(graph_cmp, 8);
303 //construct_cf_backedges(irg);
306 /* Compute the call graph */
307 for (i = 0; i < n_irgs; ++i) {
308 ir_graph *irg = get_irp_irg(i);
309 construct_cf_backedges(irg); // We also find the maximal loop depth of a call.
310 irg_walk_graph(irg, ana_Call, NULL, NULL);
313 /* Change the sets to arrays. */
314 for (i = 0; i < n_irgs; ++i) {
316 cg_callee_entry *callee;
317 ir_graph *c, *irg = get_irp_irg(i);
318 pset *callee_set, *caller_set;
320 callee_set = (pset *)irg->callees;
321 count = pset_count(callee_set);
322 irg->callees = NEW_ARR_F(cg_callee_entry *, count);
323 irg->callee_isbe = NULL;
324 callee = pset_first(callee_set);
325 for (j = 0; j < count; ++j) {
326 irg->callees[j] = callee;
327 callee = pset_next(callee_set);
329 del_pset(callee_set);
330 assert(callee == NULL);
332 caller_set = (pset *)irg->callers;
333 count = pset_count(caller_set);
334 irg->callers = NEW_ARR_F(ir_graph *, count);
335 irg->caller_isbe = NULL;
336 c = pset_first(caller_set);
337 for (j = 0; j < count; ++j) {
339 c = pset_next(caller_set);
341 del_pset(caller_set);
344 set_irp_callgraph_state(irp_callgraph_consistent);
347 /* Destruct the callgraph. */
348 void free_callgraph(void) {
349 int i, n_irgs = get_irp_n_irgs();
350 for (i = 0; i < n_irgs; ++i) {
351 ir_graph *irg = get_irp_irg(i);
352 if (irg->callees) DEL_ARR_F(irg->callees);
353 if (irg->callers) DEL_ARR_F(irg->callers);
354 if (irg->callee_isbe) free(irg->callee_isbe);
355 if (irg->caller_isbe) free(irg->caller_isbe);
358 irg->callee_isbe = NULL;
359 irg->caller_isbe = NULL;
361 set_irp_callgraph_state(irp_callgraph_none);
364 /* ----------------------------------------------------------------------------------- */
365 /* A walker for the callgraph */
366 /* ----------------------------------------------------------------------------------- */
369 static void do_walk(ir_graph *irg, callgraph_walk_func *pre, callgraph_walk_func *post, void *env) {
372 if (cg_irg_visited(irg))
374 mark_cg_irg_visited(irg);
379 n_callees = get_irg_n_callees(irg);
380 for (i = 0; i < n_callees; i++) {
381 ir_graph *m = get_irg_callee(irg, i);
382 do_walk(m, pre, post, env);
389 void callgraph_walk(callgraph_walk_func *pre, callgraph_walk_func *post, void *env) {
390 int i, n_irgs = get_irp_n_irgs();
393 do_walk(get_irp_main_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) && get_irg_n_callers(irg) == 0)
397 do_walk(irg, pre, post, env);
399 for (i = 0; i < n_irgs; i++) {
400 ir_graph *irg = get_irp_irg(i);
401 if (!cg_irg_visited(irg))
402 do_walk(irg, pre, post, env);
406 /* ----------------------------------------------------------------------------------- */
407 /* loop construction algorithm */
408 /* ----------------------------------------------------------------------------------- */
410 static ir_graph *outermost_ir_graph; /**< The outermost graph the scc is computed
412 static ir_loop *current_loop; /**< Current cfloop construction is working
414 static int loop_node_cnt = 0; /**< Counts the number of allocated cfloop nodes.
415 Each cfloop node gets a unique number.
416 What for? ev. remove. @@@ */
417 static int current_dfn = 1; /**< Counter to generate depth first numbering
420 /*-----------------*/
421 /* Node attributes */
422 /*-----------------*/
424 typedef struct scc_info {
425 int in_stack; /**< Marks whether node is on the stack. */
426 int dfn; /**< Depth first search number. */
427 int uplink; /**< dfn number of ancestor. */
432 * allocates a new scc_info on the obstack
434 static INLINE scc_info *new_scc_info(struct obstack *obst) {
435 scc_info *info = obstack_alloc(obst, sizeof(*info));
436 memset(info, 0, sizeof(*info));
441 * Returns non-zero if a graph was already visited.
443 static INLINE int cg_irg_visited(ir_graph *irg) {
444 scc_info *info = get_irg_link(irg);
445 assert(info && "missing call to init_scc()");
446 return info->visited >= master_cg_visited;
450 * Marks a graph as visited.
452 static INLINE void mark_cg_irg_visited(ir_graph *irg) {
453 scc_info *info = get_irg_link(irg);
454 assert(info && "missing call to init_scc()");
455 info->visited = master_cg_visited;
459 * Set a graphs visited flag to i.
461 static INLINE void set_cg_irg_visited(ir_graph *irg, int i) {
462 scc_info *info = get_irg_link(irg);
463 assert(info && "missing call to init_scc()");
468 * Returns the visited flag of a graph.
470 static INLINE int 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;
476 static INLINE void mark_irg_in_stack(ir_graph *irg) {
477 scc_info *info = get_irg_link(irg);
478 assert(info && "missing call to init_scc()");
482 static INLINE void mark_irg_not_in_stack(ir_graph *irg) {
483 scc_info *info = get_irg_link(irg);
484 assert(info && "missing call to init_scc()");
488 static INLINE int irg_is_in_stack(ir_graph *irg) {
489 scc_info *info = get_irg_link(irg);
490 assert(info && "missing call to init_scc()");
491 return info->in_stack;
494 static INLINE void set_irg_uplink(ir_graph *irg, int uplink) {
495 scc_info *info = get_irg_link(irg);
496 assert(info && "missing call to init_scc()");
497 info->uplink = uplink;
500 static INLINE int get_irg_uplink(ir_graph *irg) {
501 scc_info *info = get_irg_link(irg);
502 assert(info && "missing call to init_scc()");
506 static INLINE void set_irg_dfn(ir_graph *irg, int dfn) {
507 scc_info *info = get_irg_link(irg);
508 assert(info && "missing call to init_scc()");
512 static INLINE int get_irg_dfn(ir_graph *irg) {
513 scc_info *info = get_irg_link(irg);
514 assert(info && "missing call to init_scc()");
518 /**********************************************************************/
520 /**********************************************************************/
522 static ir_graph **stack = NULL;
523 static int tos = 0; /**< top of stack */
526 * Initialize the irg stack.
528 static INLINE void init_stack(void) {
530 ARR_RESIZE(ir_graph *, stack, 1000);
532 stack = NEW_ARR_F(ir_graph *, 1000);
538 * push a graph on the irg stack
539 * @param n the graph to be pushed
541 static INLINE void push(ir_graph *irg) {
542 if (tos == ARR_LEN(stack)) {
543 int nlen = ARR_LEN(stack) * 2;
544 ARR_RESIZE(ir_node *, stack, nlen);
547 mark_irg_in_stack(irg);
551 * return the topmost graph on the stack and pop it
553 static INLINE ir_graph *pop(void) {
554 ir_graph *irg = stack[--tos];
555 mark_irg_not_in_stack(irg);
560 * The nodes up to irg belong to the current loop.
561 * Removes them from the stack and adds them to the current loop.
563 static INLINE void pop_scc_to_loop(ir_graph *irg) {
569 set_irg_dfn(m, loop_node_cnt);
570 add_loop_irg(current_loop, m);
572 //m->callgraph_loop_depth = current_loop->depth;
576 /* GL ??? my last son is my grandson??? Removes cfloops with no
577 ir_nodes in them. Such loops have only another loop as son. (Why
578 can't they have two loops as sons? Does it never get that far? ) */
579 static void close_loop(ir_loop *l) {
580 int last = get_loop_n_elements(l) - 1;
581 loop_element lelement = get_loop_element(l, last);
582 ir_loop *last_son = lelement.son;
584 if (get_kind(last_son) == k_ir_loop &&
585 get_loop_n_elements(last_son) == 1) {
588 lelement = get_loop_element(last_son, 0);
590 if (get_kind(gson) == k_ir_loop) {
591 loop_element new_last_son;
593 gson->outer_loop = l;
594 new_last_son.son = gson;
595 l->children[last] = new_last_son;
602 * Removes and unmarks all nodes up to n from the stack.
603 * The nodes must be visited once more to assign them to a scc.
605 static INLINE void pop_scc_unmark_visit(ir_graph *n) {
610 set_cg_irg_visited(m, 0);
614 /**********************************************************************/
615 /* The loop data structure. **/
616 /**********************************************************************/
619 * Allocates a new loop as son of current_loop. Sets current_loop
620 * to the new loop and returns the father.
622 static ir_loop *new_loop(void) {
623 ir_loop *father = current_loop;
624 ir_loop *son = alloc_loop(father, outermost_ir_graph->obst);
631 /**********************************************************************/
632 /* Constructing and destructing the loop/backedge information. **/
633 /**********************************************************************/
635 /* Initialization steps. **********************************************/
637 static void init_scc(struct obstack *obst) {
645 n_irgs = get_irp_n_irgs();
646 for (i = 0; i < n_irgs; ++i) {
647 ir_graph *irg = get_irp_irg(i);
648 set_irg_link(irg, new_scc_info(obst));
649 irg->callgraph_recursion_depth = 0;
650 irg->callgraph_loop_depth = 0;
654 /** Returns non-zero if n is a loop header, i.e., it is a Block node
655 * and has predecessors within the cfloop and out of the cfloop.
657 * @param root: only needed for assertion.
659 static int is_head(ir_graph *n, ir_graph *root) {
661 int some_outof_loop = 0, some_in_loop = 0;
663 arity = get_irg_n_callees(n);
664 for (i = 0; i < arity; i++) {
665 ir_graph *pred = get_irg_callee(n, i);
666 if (is_irg_callee_backedge(n, i)) continue;
667 if (!irg_is_in_stack(pred)) {
670 if (get_irg_uplink(pred) < get_irg_uplink(root)) {
671 assert(get_irg_uplink(pred) >= get_irg_uplink(root));
677 return some_outof_loop & some_in_loop;
681 * Returns non-zero if n is possible loop head of an endless loop.
682 * I.e., it is a Block, Phi or Filter node and has only predecessors
684 * @arg root: only needed for assertion.
686 static int is_endless_head(ir_graph *n, ir_graph *root)
689 int some_outof_loop = 0, some_in_loop = 0;
691 arity = get_irg_n_callees(n);
692 for (i = 0; i < arity; i++) {
693 ir_graph *pred = get_irg_callee(n, i);
695 if (is_irg_callee_backedge(n, i))
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));
706 return !some_outof_loop & some_in_loop;
709 #ifdef INTERPROCEDURAL_VIEW
711 * Check whether there is a parallel edge in the ip control flow.
714 static int is_ip_head(ir_graph *n, ir_graph *pred)
718 int iv_rem = get_interprocedural_view();
719 set_interprocedural_view(1);
721 ir_node *sblock = get_irg_start_block(n);
722 int i, arity = get_Block_n_cfgpreds(sblock);
724 //printf(" edge from "); DDMG(n);
725 //printf(" to pred "); DDMG(pred);
726 //printf(" sblock "); DDMN(sblock);
728 for (i = 0; i < arity; i++) {
729 ir_node *pred_cfop = skip_Proj(get_Block_cfgpred(sblock, i));
730 //printf(" "); DDMN(pred_cfop);
731 if (get_irn_op(pred_cfop) == op_CallBegin) { /* could be Unknown */
732 ir_graph *ip_pred = get_irn_irg(pred_cfop);
733 //printf(" "); DDMG(ip_pred);
734 if ((ip_pred == pred) && is_backedge(sblock, i)) {
735 //printf(" found\n");
741 set_interprocedural_view(iv_rem);
744 #endif /* INTERPROCEDURAL_VIEW */
747 * Returns index of the predecessor with the smallest dfn number
748 * greater-equal than limit.
750 static int smallest_dfn_pred(ir_graph *n, int limit)
752 int i, index = -2, min = -1;
754 int arity = get_irg_n_callees(n);
755 for (i = 0; i < arity; i++) {
756 ir_graph *pred = get_irg_callee(n, i);
757 if (is_irg_callee_backedge(n, i) || !irg_is_in_stack(pred))
759 if (get_irg_dfn(pred) >= limit && (min == -1 || get_irg_dfn(pred) < min)) {
761 min = get_irg_dfn(pred);
768 /** Returns index of the predecessor with the largest dfn number. */
769 static int largest_dfn_pred(ir_graph *n) {
770 int i, index = -2, max = -1;
772 int arity = get_irg_n_callees(n);
773 for (i = 0; i < arity; ++i) {
774 ir_graph *pred = get_irg_callee(n, i);
775 if (is_irg_callee_backedge (n, i) || !irg_is_in_stack(pred)) continue;
776 if (get_irg_dfn(pred) > max) {
778 max = get_irg_dfn(pred);
785 #ifndef INTERPROCEDURAL_VIEW
786 static ir_graph *find_tail(ir_graph *n) {
788 int i, res_index = -2;
791 if (!icfg && rm_cyclic_phis && remove_cyclic_phis (n)) return NULL;
793 m = stack[tos-1]; /* tos = top of stack */
794 if (is_head (m, n)) {
795 res_index = smallest_dfn_pred(m, 0);
796 if ((res_index == -2) && /* no smallest dfn pred found. */
800 if (m == n) return NULL; // Is this to catch Phi - self loops?
801 for (i = tos-2; i >= 0; --i) {
805 res_index = smallest_dfn_pred(m, get_irg_dfn(m) + 1);
806 if (res_index == -2) /* no smallest dfn pred found. */
807 res_index = largest_dfn_pred(m);
809 if ((m == n) && (res_index == -2)) {
815 /* We should not walk past our selves on the stack: The upcoming nodes
816 are not in this loop. We assume a loop not reachable from Start. */
825 /* A dead loop not reachable from Start. */
826 for (i = tos-2; i >= 0; --i) {
828 if (is_endless_head(m, n)) {
829 res_index = smallest_dfn_pred(m, get_irg_dfn(m) + 1);
830 if (res_index == -2) /* no smallest dfn pred found. */
831 res_index = largest_dfn_pred(m);
834 if (m == n) { break; } /* It's not an unreachable loop, either. */
836 //assert(0 && "no head found on stack");
840 assert (res_index > -2);
842 set_irg_callee_backedge(m, res_index);
843 return get_irg_callee(m, res_index);
846 static ir_graph *find_tail(ir_graph *n) {
848 int i, res_index = -2;
851 ir_graph *in_and_out = NULL;
852 ir_graph *only_in = NULL;
853 ir_graph *ip_in_and_out = NULL;
854 ir_graph *ip_only_in = NULL;
856 //printf("find tail for "); DDMG(n);
858 for (i = tos-1; i >= 0; --i) {
859 ir_graph *pred = (i < tos -1) ? stack[i+1] : n;
863 //printf(" found 1a! "); DDM;
865 if (is_ip_head(pred, m)) {
866 //printf(" found 1b! "); DDM;
869 } else if (!ip_only_in && is_endless_head(m, n)) {
871 //printf(" found 2a! "); DDM;
872 if (is_ip_head(pred, m)) {
873 //printf(" found 2b! "); DDM;
876 } else if (is_ip_head(pred, m)) {
877 //printf(" found 3! "); DDM; This happens for self recursions in the second
878 //assert(0); scc iteration (the one to flip the loop.)
881 if (ip_in_and_out) break; /* That's what we really want. */
883 if (m == n) break; /* Don't walk past n on the stack! */
887 if (!in_and_out && !only_in)
888 /* There is no loop */
892 /* Is there a head in the callgraph without a head in the
894 assert(in_and_out || only_in);
896 m = (ip_in_and_out) ? ip_in_and_out : ip_only_in;
899 m = (in_and_out) ? in_and_out : only_in;
901 //printf("*** head is "); DDMG(m);
903 res_index = smallest_dfn_pred(m, get_irg_dfn(m) + 1);
904 if (res_index == -2) /* no smallest dfn pred found. */
905 res_index = largest_dfn_pred(m);
907 set_irg_callee_backedge(m, res_index);
908 res = get_irg_callee(m, res_index);
909 //printf("*** tail is "); DDMG(res);
912 #endif /* INTERPROCEDURAL_VIEW */
914 /*-----------------------------------------------------------*
915 * The core algorithm. *
916 *-----------------------------------------------------------*/
919 static void cgscc(ir_graph *n) {
922 if (cg_irg_visited(n)) return;
923 mark_cg_irg_visited(n);
925 /* Initialize the node */
926 set_irg_dfn(n, current_dfn); /* Depth first number for this node */
927 set_irg_uplink(n, current_dfn); /* ... is default uplink. */
931 arity = get_irg_n_callees(n);
932 for (i = 0; i < arity; i++) {
934 if (is_irg_callee_backedge(n, i)) continue;
935 m = get_irg_callee(n, i);
937 /** This marks the backedge, but does it guarantee a correct loop tree? */
938 //if (m == n) { set_irg_callee_backedge(n, i); continue; }
941 if (irg_is_in_stack(m)) {
942 /* Uplink of m is smaller if n->m is a backedge.
943 Propagate the uplink to mark the cfloop. */
944 if (get_irg_uplink(m) < get_irg_uplink(n))
945 set_irg_uplink(n, get_irg_uplink(m));
949 if (get_irg_dfn(n) == get_irg_uplink(n)) {
950 /* This condition holds for
951 1) the node with the incoming backedge.
952 That is: We found a cfloop!
953 2) Straight line code, because no uplink has been propagated, so the
954 uplink still is the same as the dfn.
956 But n might not be a proper cfloop head for the analysis. Proper cfloop
957 heads are Block and Phi nodes. find_tail searches the stack for
958 Block's and Phi's and takes those nodes as cfloop heads for the current
959 cfloop instead and marks the incoming edge as backedge. */
961 ir_graph *tail = find_tail(n);
963 /* We have a cfloop, that is no straight line code,
964 because we found a cfloop head!
965 Next actions: Open a new cfloop on the cfloop tree and
966 try to find inner cfloops */
969 ir_loop *l = new_loop();
971 /* Remove the cfloop from the stack ... */
972 pop_scc_unmark_visit(n);
974 /* The current backedge has been marked, that is temporarily eliminated,
975 by find tail. Start the scc algorithm
976 anew on the subgraph thats left (the current cfloop without the backedge)
977 in order to find more inner cfloops. */
981 assert(cg_irg_visited(n));
991 * reset the backedge information for all callers in all irgs
993 static void reset_isbe(void) {
994 int i, n_irgs = get_irp_n_irgs();
996 for (i = 0; i < n_irgs; ++i) {
997 ir_graph *irg = get_irp_irg(i);
999 if (irg->caller_isbe)
1000 xfree(irg->caller_isbe);
1001 irg->caller_isbe = NULL;
1003 if (irg->callee_isbe)
1004 xfree(irg->callee_isbe);
1005 irg->callee_isbe = NULL;
1009 /* ----------------------------------------------------------------------------------- */
1010 /* Another algorithm to compute recursion nesting depth */
1011 /* Walk the callgraph. For each crossed edge increase the loop depth by the edge */
1012 /* weight. Assign graphs the maximal depth. */
1013 /* ----------------------------------------------------------------------------------- */
1015 static void compute_loop_depth(ir_graph *irg, void *env) {
1016 int current_nesting = *(int *) env;
1017 int old_nesting = irg->callgraph_loop_depth;
1018 int old_visited = get_cg_irg_visited(irg);
1023 if (cg_irg_visited(irg)) return;
1025 mark_cg_irg_visited(irg);
1027 //printf(" old: %d new %d master %d", old_visited, get_cg_irg_visited(irg), master_cg_visited); DDMG(irg);
1030 if (old_nesting < current_nesting)
1031 irg->callgraph_loop_depth = current_nesting;
1033 if (current_nesting > irp->max_callgraph_loop_depth)
1034 irp->max_callgraph_loop_depth = current_nesting;
1036 if ((old_visited +1 < get_cg_irg_visited(irg)) || /* not yet visited */
1037 (old_nesting < current_nesting)) { /* propagate larger nesting */
1038 /* Don't walk the graph, but a tree that is an unfolded graph. */
1039 n_callees = get_irg_n_callees(irg);
1040 for (i = 0; i < n_callees; i++) {
1041 ir_graph *m = get_irg_callee(irg, i);
1042 *(int *)env += get_irg_callee_loop_depth(irg, i);
1043 compute_loop_depth(m, env);
1044 *(int *)env -= get_irg_callee_loop_depth(irg, i);
1048 set_cg_irg_visited(irg, master_cg_visited-1);
1051 /* ------------------------------------------------------------------------------------ */
1052 /* Another algorithm to compute recursion nesting depth */
1053 /* Walk the callgraph. For each crossed loop increase the nesting depth by one. */
1054 /* Assign graphs the maximal nesting depth. Don't increase if passing loops more than */
1056 /* ------------------------------------------------------------------------------------ */
1059 /* For callees, we want to remember the Call nodes, too. */
1060 typedef struct ana_entry2 {
1061 ir_loop **loop_stack; /**< a stack of ir_loop entries */
1062 int tos; /**< the top of stack entry */
1063 int recursion_nesting;
1067 * push a loop entry on the stack
1069 static void push2(ana_entry2 *e, ir_loop *g) {
1070 if (ARR_LEN(e->loop_stack) == e->tos) {
1071 ARR_APP1(ir_loop *, e->loop_stack, g);
1073 e->loop_stack[e->tos] = g;
1079 * returns the top of stack and pop it
1081 static ir_loop *pop2(ana_entry2 *e) {
1082 return e->loop_stack[--e->tos];
1086 * check if a loop g in on the stack. Did not check the TOS.
1088 static int in_stack(ana_entry2 *e, ir_loop *g) {
1090 for (i = e->tos-1; i >= 0; --i) {
1091 if (e->loop_stack[i] == g) return 1;
1096 static void compute_rec_depth(ir_graph *irg, void *env) {
1097 ana_entry2 *e = (ana_entry2 *)env;
1098 ir_loop *l = irg->l;
1099 int depth, old_depth = irg->callgraph_recursion_depth;
1103 if (cg_irg_visited(irg))
1105 mark_cg_irg_visited(irg);
1107 /* -- compute and set the new nesting value -- */
1108 if ((l != irp->outermost_cg_loop) && !in_stack(e, l)) {
1110 e->recursion_nesting++;
1113 depth = e->recursion_nesting;
1115 if (old_depth < depth)
1116 irg->callgraph_recursion_depth = depth;
1118 if (depth > irp->max_callgraph_recursion_depth)
1119 irp->max_callgraph_recursion_depth = depth;
1121 /* -- spread the nesting value -- */
1122 if (depth == 0 || old_depth < depth) {
1123 /* Don't walk the graph, but a tree that is an unfolded graph.
1124 Therefore we unset the visited flag at the end. */
1125 n_callees = get_irg_n_callees(irg);
1126 for (i = 0; i < n_callees; ++i) {
1127 ir_graph *m = get_irg_callee(irg, i);
1128 compute_rec_depth(m, env);
1132 /* -- clean up -- */
1135 e->recursion_nesting--;
1137 set_cg_irg_visited(irg, master_cg_visited-1);
1141 /* ----------------------------------------------------------------------------------- */
1142 /* Another algorithm to compute the execution frequency of methods ignoring recursions. */
1143 /* Walk the callgraph. Ignore backedges. Use sum of execution frequencies of Call */
1144 /* nodes to evaluate a callgraph edge. */
1145 /* ----------------------------------------------------------------------------------- */
1147 /* Returns the method execution frequency of a graph. */
1148 double get_irg_method_execution_frequency(ir_graph *irg) {
1149 return irg->method_execution_frequency;
1153 * Increase the method execution frequency to freq if its current value is
1154 * smaller then this.
1156 static void set_irg_method_execution_frequency(ir_graph *irg, double freq) {
1157 irg->method_execution_frequency = freq;
1159 if (irp->max_method_execution_frequency < freq)
1160 irp->max_method_execution_frequency = freq;
1163 static void compute_method_execution_frequency(ir_graph *irg, void *env) {
1170 if (cg_irg_visited(irg))
1173 /* We need the values of all predecessors (except backedges).
1174 So they must be marked. Else we will reach the node through
1175 one of the unmarked ones. */
1176 n_callers = get_irg_n_callers(irg);
1177 for (i = 0; i < n_callers; ++i) {
1178 ir_graph *m = get_irg_caller(irg, i);
1179 if (is_irg_caller_backedge(irg, i))
1181 if (!cg_irg_visited(m)) {
1185 mark_cg_irg_visited(irg);
1187 /* Compute the new frequency. */
1190 for (i = 0; i < n_callers; i++) {
1191 if (! is_irg_caller_backedge(irg, i)) {
1192 double edge_freq = get_irg_caller_method_execution_frequency(irg, i);
1193 assert(edge_freq >= 0);
1200 /* A starting point: method only called from outside,
1201 or only backedges as predecessors. */
1205 set_irg_method_execution_frequency(irg, freq);
1208 n_callees = get_irg_n_callees(irg);
1209 for (i = 0; i < n_callees; ++i) {
1210 compute_method_execution_frequency(get_irg_callee(irg, i), NULL);
1215 /* ----------------------------------------------------------------------------------- */
1216 /* The recursion stuff driver. */
1217 /* ----------------------------------------------------------------------------------- */
1219 /* Compute the backedges that represent recursions. */
1220 void find_callgraph_recursions(void) {
1221 int i, n_irgs = get_irp_n_irgs();
1222 struct obstack temp;
1226 /* -- compute the looptree. -- */
1228 /* The outermost graph. We start here. Then we start at all
1229 functions in irg list that are never called, then at the remaining
1230 unvisited ones. The third step is needed for functions that are not
1231 reachable from the outermost graph, but call themselves in a cycle. */
1232 assert(get_irp_main_irg());
1233 outermost_ir_graph = get_irp_main_irg();
1234 obstack_init(&temp);
1237 current_loop = NULL;
1238 new_loop(); /* sets current_loop */
1240 ++master_cg_visited;
1241 cgscc(outermost_ir_graph);
1242 for (i = 0; i < n_irgs; ++i) {
1243 ir_graph *irg = get_irp_irg(i);
1244 if (!cg_irg_visited(irg) && get_irg_n_callers(irg) == 0)
1247 for (i = 0; i < n_irgs; ++i) {
1248 ir_graph *irg = get_irp_irg(i);
1249 if (!cg_irg_visited(irg))
1252 obstack_free(&temp, NULL);
1254 irp->outermost_cg_loop = current_loop;
1255 mature_loops(current_loop, outermost_ir_graph->obst);
1257 /* -- Reverse the backedge information. -- */
1258 for (i = 0; i < n_irgs; ++i) {
1259 ir_graph *irg = get_irp_irg(i);
1260 int j, n_callees = get_irg_n_callees(irg);
1261 for (j = 0; j < n_callees; ++j) {
1262 if (is_irg_callee_backedge(irg, j))
1263 set_irg_caller_backedge(get_irg_callee(irg, j), irg);
1267 irp->callgraph_state = irp_callgraph_and_calltree_consistent;
1270 /* Compute interprocedural performance estimates. */
1271 void compute_performance_estimates(void) {
1272 int i, n_irgs = get_irp_n_irgs();
1273 int current_nesting;
1276 assert(get_irp_exec_freq_state() != exec_freq_none && "execution frequency not calculated");
1278 /* -- compute the loop depth -- */
1279 current_nesting = 0;
1280 irp->max_callgraph_loop_depth = 0;
1281 master_cg_visited += 2;
1282 //printf(" ** starting at "); DDMG(get_irp_main_irg());
1283 compute_loop_depth(get_irp_main_irg(), ¤t_nesting);
1284 for (i = 0; i < n_irgs; i++) {
1285 ir_graph *irg = get_irp_irg(i);
1286 if ((get_cg_irg_visited(irg) < master_cg_visited-1) &&
1287 get_irg_n_callers(irg) == 0) {
1288 compute_loop_depth(irg, ¤t_nesting);
1289 //printf(" ** starting at "); DDMG(irg);
1292 for (i = 0; i < n_irgs; i++) {
1293 ir_graph *irg = get_irp_irg(i);
1294 if (get_cg_irg_visited(irg) < master_cg_visited-1) {
1295 compute_loop_depth(irg, ¤t_nesting);
1296 //printf(" ** starting at "); DDMG(irg);
1301 /* -- compute the recursion depth -- */
1302 e.loop_stack = NEW_ARR_F(ir_loop *, 0);
1304 e.recursion_nesting = 0;
1306 irp->max_callgraph_recursion_depth = 0;
1308 master_cg_visited += 2;
1309 compute_rec_depth(get_irp_main_irg(), &e);
1310 //printf(" ++ starting at "); DDMG(get_irp_main_irg());
1311 for (i = 0; i < n_irgs; i++) {
1312 ir_graph *irg = get_irp_irg(i);
1313 if ((get_cg_irg_visited(irg) < master_cg_visited-1) &&
1314 get_irg_n_callers(irg) == 0) {
1315 compute_rec_depth(irg, &e);
1316 //printf(" ++ starting at "); DDMG(irg);
1319 for (i = 0; i < n_irgs; i++) {
1320 ir_graph *irg = get_irp_irg(i);
1321 if (get_cg_irg_visited(irg) < master_cg_visited-1) {
1322 compute_rec_depth(irg, &e);
1323 //printf(" ++ starting at "); DDMG(irg);
1327 DEL_ARR_F(e.loop_stack);
1329 /* -- compute the execution frequency -- */
1330 irp->max_method_execution_frequency = 0;
1331 master_cg_visited += 2;
1332 assert(get_irg_n_callers(get_irp_main_irg()) == 0);
1333 compute_method_execution_frequency(get_irp_main_irg(), NULL);
1334 for (i = 0; i < n_irgs; i++) {
1335 ir_graph *irg = get_irp_irg(i);
1336 if ((get_cg_irg_visited(irg) < master_cg_visited-1) &&
1337 get_irg_n_callers(irg) == 0) {
1338 compute_method_execution_frequency(irg, NULL);
1341 for (i = 0; i < n_irgs; i++) {
1342 ir_graph *irg = get_irp_irg(i);
1343 if (get_cg_irg_visited(irg) < master_cg_visited-1) {
1344 compute_method_execution_frequency(irg, NULL);
1349 /* Returns the maximal loop depth of all paths from an external visible method to
1351 int get_irg_loop_depth(ir_graph *irg) {
1352 assert(irp->callgraph_state == irp_callgraph_consistent ||
1353 irp->callgraph_state == irp_callgraph_and_calltree_consistent);
1354 return irg->callgraph_loop_depth;
1357 /* Returns the maximal recursion depth of all paths from an external visible method to
1359 int get_irg_recursion_depth(ir_graph *irg) {
1360 assert(irp->callgraph_state == irp_callgraph_and_calltree_consistent);
1361 return irg->callgraph_recursion_depth;
1364 /* Computes the interprocedural loop nesting information. */
1365 void analyse_loop_nesting_depth(void) {
1366 ir_entity **free_methods = NULL;
1369 /* establish preconditions. */
1370 if (get_irp_callee_info_state() != irg_callee_info_consistent) {
1371 cgana(&arr_len, &free_methods);
1374 if (irp_callgraph_consistent != get_irp_callgraph_state()) {
1375 compute_callgraph();
1378 find_callgraph_recursions();
1380 compute_performance_estimates();
1382 set_irp_loop_nesting_depth_state(loop_nesting_depth_consistent);
1385 loop_nesting_depth_state get_irp_loop_nesting_depth_state(void) {
1386 return irp->lnd_state;
1388 void set_irp_loop_nesting_depth_state(loop_nesting_depth_state s) {
1391 void set_irp_loop_nesting_depth_state_inconsistent(void) {
1392 if (irp->lnd_state == loop_nesting_depth_consistent)
1393 irp->lnd_state = loop_nesting_depth_inconsistent;