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"
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 */
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)) return;
373 mark_cg_irg_visited(irg);
378 n_callees = get_irg_n_callees(irg);
379 for (i = 0; i < n_callees; i++) {
380 ir_graph *m = get_irg_callee(irg, i);
381 do_walk(m, pre, post, env);
388 void callgraph_walk(callgraph_walk_func *pre, callgraph_walk_func *post, void *env) {
389 int i, n_irgs = get_irp_n_irgs();
392 do_walk(get_irp_main_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) && get_irg_n_callers(irg) == 0)
396 do_walk(irg, pre, post, env);
398 for (i = 0; i < n_irgs; i++) {
399 ir_graph *irg = get_irp_irg(i);
400 if (!cg_irg_visited(irg))
401 do_walk(irg, pre, post, env);
405 /* ----------------------------------------------------------------------------------- */
406 /* loop construction algorithm */
407 /* ----------------------------------------------------------------------------------- */
409 static ir_graph *outermost_ir_graph; /**< The outermost graph the scc is computed
411 static ir_loop *current_loop; /**< Current cfloop construction is working
413 static int loop_node_cnt = 0; /**< Counts the number of allocated cfloop nodes.
414 Each cfloop node gets a unique number.
415 What for? ev. remove. @@@ */
416 static int current_dfn = 1; /**< Counter to generate depth first numbering
419 /*-----------------*/
420 /* Node attributes */
421 /*-----------------*/
423 typedef struct scc_info {
424 int in_stack; /**< Marks whether node is on the stack. */
425 int dfn; /**< Depth first search number. */
426 int uplink; /**< dfn number of ancestor. */
431 * allocates a new scc_info of the obstack
433 static INLINE scc_info *new_scc_info(void) {
434 scc_info *info = obstack_alloc(outermost_ir_graph->obst, sizeof(*info));
435 memset(info, 0, sizeof(*info));
440 * Returns non-zero if a graph was already visited.
443 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.
453 mark_cg_irg_visited(ir_graph *irg) {
454 scc_info *info = get_irg_link(irg);
455 assert(info && "missing call to init_scc");
456 info->visited = master_cg_visited;
460 * Set a graphs visited flag to i.
463 set_cg_irg_visited(ir_graph *irg, int i) {
464 scc_info *info = get_irg_link(irg);
465 assert(info && "missing call to init_scc");
470 * Returns the visited flag of a graph.
473 get_cg_irg_visited(ir_graph *irg) {
474 scc_info *info = get_irg_link(irg);
475 assert(info && "missing call to init_scc");
476 return info->visited;
480 mark_irg_in_stack(ir_graph *irg) {
481 scc_info *info = get_irg_link(irg);
482 assert(info && "missing call to init_scc");
487 mark_irg_not_in_stack(ir_graph *irg) {
488 scc_info *info = get_irg_link(irg);
489 assert(info && "missing call to init_scc");
494 irg_is_in_stack(ir_graph *irg) {
495 scc_info *info = get_irg_link(irg);
496 assert(info && "missing call to init_scc");
497 return info->in_stack;
501 set_irg_uplink(ir_graph *irg, int uplink) {
502 scc_info *info = get_irg_link(irg);
503 assert(info && "missing call to init_scc");
504 info->uplink = uplink;
508 get_irg_uplink(ir_graph *irg) {
509 scc_info *info = get_irg_link(irg);
510 assert(info && "missing call to init_scc");
515 set_irg_dfn(ir_graph *irg, int dfn) {
516 scc_info *info = get_irg_link(irg);
517 assert(info && "missing call to init_scc");
522 get_irg_dfn(ir_graph *irg) {
523 scc_info *info = get_irg_link(irg);
524 assert(info && "missing call to init_scc");
528 /**********************************************************************/
530 /**********************************************************************/
532 static ir_graph **stack = NULL;
533 static int tos = 0; /**< top of stack */
536 * Initialize the irg stack.
538 static INLINE void init_stack(void) {
540 ARR_RESIZE(ir_graph *, stack, 1000);
542 stack = NEW_ARR_F(ir_graph *, 1000);
548 * push a graph on the irg stack
549 * @param n the graph to be pushed
551 static INLINE void push(ir_graph *irg) {
552 if (tos == ARR_LEN(stack)) {
553 int nlen = ARR_LEN(stack) * 2;
554 ARR_RESIZE(ir_node *, stack, nlen);
557 mark_irg_in_stack(irg);
561 * return the topmost graph on the stack and pop it
563 static INLINE ir_graph *pop(void) {
564 ir_graph *irg = stack[--tos];
565 mark_irg_not_in_stack(irg);
570 * The nodes up to irg belong to the current loop.
571 * Removes them from the stack and adds them to the current loop.
573 static INLINE void pop_scc_to_loop(ir_graph *irg) {
579 set_irg_dfn(m, loop_node_cnt);
580 add_loop_node(current_loop, (ir_node *)m);
582 //m->callgraph_loop_depth = current_loop->depth;
586 /* GL ??? my last son is my grandson??? Removes cfloops with no
587 ir_nodes in them. Such loops have only another loop as son. (Why
588 can't they have two loops as sons? Does it never get that far? ) */
589 static void close_loop(ir_loop *l) {
590 int last = get_loop_n_elements(l) - 1;
591 loop_element lelement = get_loop_element(l, last);
592 ir_loop *last_son = lelement.son;
594 if (get_kind(last_son) == k_ir_loop &&
595 get_loop_n_elements(last_son) == 1) {
598 lelement = get_loop_element(last_son, 0);
600 if(get_kind(gson) == k_ir_loop) {
601 loop_element new_last_son;
603 gson -> outer_loop = l;
604 new_last_son.son = gson;
605 l -> children[last] = new_last_son;
613 * Removes and unmarks all nodes up to n from the stack.
614 * The nodes must be visited once more to assign them to a scc.
616 static INLINE void pop_scc_unmark_visit(ir_graph *n) {
621 set_cg_irg_visited(m, 0);
625 /**********************************************************************/
626 /* The loop data structure. **/
627 /**********************************************************************/
630 * Allocates a new loop as son of current_loop. Sets current_loop
631 * to the new loop and returns the father.
633 static ir_loop *new_loop(void) {
634 ir_loop *father, *son;
636 father = current_loop;
638 son = obstack_alloc(outermost_ir_graph->obst, sizeof(*son));
639 memset(son, 0, sizeof(*son));
640 son->kind = k_ir_loop;
641 son->children = NEW_ARR_F(loop_element, 0);
646 son->outer_loop = father;
647 add_loop_son(father, son);
648 son->depth = father->depth + 1;
649 } else { /* The root loop */
650 son->outer_loop = son;
655 son->loop_nr = get_irp_new_node_nr();
662 /**********************************************************************/
663 /* Constructing and destructing the loop/backedge information. **/
664 /**********************************************************************/
666 /* Initialization steps. **********************************************/
677 n_irgs = get_irp_n_irgs();
678 for (i = 0; i < n_irgs; ++i) {
679 ir_graph *irg = get_irp_irg(i);
680 set_irg_link(irg, new_scc_info());
681 irg->callgraph_recursion_depth = 0;
682 irg->callgraph_loop_depth = 0;
686 /** Returns non-zero if n is a loop header, i.e., it is a Block node
687 * and has predecessors within the cfloop and out of the cfloop.
689 * @param root: only needed for assertion.
692 is_head(ir_graph *n, ir_graph *root)
695 int some_outof_loop = 0, some_in_loop = 0;
697 arity = get_irg_n_callees(n);
698 for (i = 0; i < arity; i++) {
699 ir_graph *pred = get_irg_callee(n, i);
700 if (is_irg_callee_backedge(n, i)) continue;
701 if (!irg_is_in_stack(pred)) {
704 if (get_irg_uplink(pred) < get_irg_uplink(root)) {
705 assert(get_irg_uplink(pred) >= get_irg_uplink(root));
711 return some_outof_loop & some_in_loop;
715 * Returns non-zero if n is possible loop head of an endless loop.
716 * I.e., it is a Block, Phi or Filter node and has only predecessors
718 * @arg root: only needed for assertion.
721 is_endless_head(ir_graph *n, ir_graph *root)
724 int some_outof_loop = 0, some_in_loop = 0;
726 arity = get_irg_n_callees(n);
727 for (i = 0; i < arity; i++) {
728 ir_graph *pred = get_irg_callee(n, i);
730 if (is_irg_callee_backedge(n, i))
732 if (!irg_is_in_stack(pred)) {
735 if (get_irg_uplink(pred) < get_irg_uplink(root)) {
736 assert(get_irg_uplink(pred) >= get_irg_uplink(root));
742 return !some_outof_loop & some_in_loop;
745 #ifdef INTERPROCEDURAL_VIEW
747 * Check whether there is a parallel edge in the ip control flow.
751 is_ip_head(ir_graph *n, ir_graph *pred)
755 int iv_rem = get_interprocedural_view();
756 set_interprocedural_view(1);
758 ir_node *sblock = get_irg_start_block(n);
759 int i, arity = get_Block_n_cfgpreds(sblock);
761 //printf(" edge from "); DDMG(n);
762 //printf(" to pred "); DDMG(pred);
763 //printf(" sblock "); DDMN(sblock);
765 for (i = 0; i < arity; i++) {
766 ir_node *pred_cfop = skip_Proj(get_Block_cfgpred(sblock, i));
767 //printf(" "); DDMN(pred_cfop);
768 if (get_irn_op(pred_cfop) == op_CallBegin) { /* could be Unknown */
769 ir_graph *ip_pred = get_irn_irg(pred_cfop);
770 //printf(" "); DDMG(ip_pred);
771 if ((ip_pred == pred) && is_backedge(sblock, i)) {
772 //printf(" found\n");
778 set_interprocedural_view(iv_rem);
781 #endif /* INTERPROCEDURAL_VIEW */
784 * Returns index of the predecessor with the smallest dfn number
785 * greater-equal than limit.
788 smallest_dfn_pred(ir_graph *n, int limit)
790 int i, index = -2, min = -1;
792 int arity = get_irg_n_callees(n);
793 for (i = 0; i < arity; i++) {
794 ir_graph *pred = get_irg_callee(n, i);
795 if (is_irg_callee_backedge(n, i) || !irg_is_in_stack(pred))
797 if (get_irg_dfn(pred) >= limit && (min == -1 || get_irg_dfn(pred) < min)) {
799 min = get_irg_dfn(pred);
806 /** Returns index of the predecessor with the largest dfn number. */
808 largest_dfn_pred(ir_graph *n)
810 int i, index = -2, max = -1;
812 int arity = get_irg_n_callees(n);
813 for (i = 0; i < arity; ++i) {
814 ir_graph *pred = get_irg_callee(n, i);
815 if (is_irg_callee_backedge (n, i) || !irg_is_in_stack(pred)) continue;
816 if (get_irg_dfn(pred) > max) {
818 max = get_irg_dfn(pred);
825 #ifndef INTERPROCEDURAL_VIEW
827 find_tail(ir_graph *n) {
829 int i, res_index = -2;
832 if (!icfg && rm_cyclic_phis && remove_cyclic_phis (n)) return NULL;
834 m = stack[tos-1]; /* tos = top of stack */
835 if (is_head (m, n)) {
836 res_index = smallest_dfn_pred(m, 0);
837 if ((res_index == -2) && /* no smallest dfn pred found. */
841 if (m == n) return NULL; // Is this to catch Phi - self loops?
842 for (i = tos-2; i >= 0; --i) {
846 res_index = smallest_dfn_pred(m, get_irg_dfn(m) + 1);
847 if (res_index == -2) /* no smallest dfn pred found. */
848 res_index = largest_dfn_pred(m);
850 if ((m == n) && (res_index == -2)) {
856 /* We should not walk past our selves on the stack: The upcoming nodes
857 are not in this loop. We assume a loop not reachable from Start. */
866 /* A dead loop not reachable from Start. */
867 for (i = tos-2; i >= 0; --i) {
869 if (is_endless_head(m, n)) {
870 res_index = smallest_dfn_pred(m, get_irg_dfn(m) + 1);
871 if (res_index == -2) /* no smallest dfn pred found. */
872 res_index = largest_dfn_pred(m);
875 if (m == n) { break; } /* It's not an unreachable loop, either. */
877 //assert(0 && "no head found on stack");
881 assert (res_index > -2);
883 set_irg_callee_backedge(m, res_index);
884 return get_irg_callee(m, res_index);
888 find_tail(ir_graph *n) {
890 int i, res_index = -2;
893 ir_graph *in_and_out = NULL;
894 ir_graph *only_in = NULL;
895 ir_graph *ip_in_and_out = NULL;
896 ir_graph *ip_only_in = NULL;
898 //printf("find tail for "); DDMG(n);
900 for (i = tos-1; i >= 0; --i) {
901 ir_graph *pred = (i < tos -1) ? stack[i+1] : n;
905 //printf(" found 1a! "); DDM;
907 if (is_ip_head(pred, m)) {
908 //printf(" found 1b! "); DDM;
911 } else if (!ip_only_in && is_endless_head(m, n)) {
913 //printf(" found 2a! "); DDM;
914 if (is_ip_head(pred, m)) {
915 //printf(" found 2b! "); DDM;
918 } else if (is_ip_head(pred, m)) {
919 //printf(" found 3! "); DDM; This happens for self recursions in the second
920 //assert(0); scc iteration (the one to flip the loop.)
923 if (ip_in_and_out) break; /* That's what we really want. */
925 if (m == n) break; /* Don't walk past n on the stack! */
929 if (!in_and_out && !only_in)
930 /* There is no loop */
934 /* Is there a head in the callgraph without a head in the
936 assert(in_and_out || only_in);
938 m = (ip_in_and_out) ? ip_in_and_out : ip_only_in;
941 m = (in_and_out) ? in_and_out : only_in;
943 //printf("*** head is "); DDMG(m);
945 res_index = smallest_dfn_pred(m, get_irg_dfn(m) + 1);
946 if (res_index == -2) /* no smallest dfn pred found. */
947 res_index = largest_dfn_pred(m);
949 set_irg_callee_backedge(m, res_index);
950 res = get_irg_callee(m, res_index);
951 //printf("*** tail is "); DDMG(res);
954 #endif /* INTERPROCEDURAL_VIEW */
956 /*-----------------------------------------------------------*
957 * The core algorithm. *
958 *-----------------------------------------------------------*/
961 static void cgscc(ir_graph *n) {
964 if (cg_irg_visited(n)) return;
965 mark_cg_irg_visited(n);
967 /* Initialize the node */
968 set_irg_dfn(n, current_dfn); /* Depth first number for this node */
969 set_irg_uplink(n, current_dfn); /* ... is default uplink. */
973 arity = get_irg_n_callees(n);
974 for (i = 0; i < arity; i++) {
976 if (is_irg_callee_backedge(n, i)) continue;
977 m = get_irg_callee(n, i);
979 /** This marks the backedge, but does it guarantee a correct loop tree? */
980 //if (m == n) { set_irg_callee_backedge(n, i); continue; }
983 if (irg_is_in_stack(m)) {
984 /* Uplink of m is smaller if n->m is a backedge.
985 Propagate the uplink to mark the cfloop. */
986 if (get_irg_uplink(m) < get_irg_uplink(n))
987 set_irg_uplink(n, get_irg_uplink(m));
991 if (get_irg_dfn(n) == get_irg_uplink(n)) {
992 /* This condition holds for
993 1) the node with the incoming backedge.
994 That is: We found a cfloop!
995 2) Straight line code, because no uplink has been propagated, so the
996 uplink still is the same as the dfn.
998 But n might not be a proper cfloop head for the analysis. Proper cfloop
999 heads are Block and Phi nodes. find_tail searches the stack for
1000 Block's and Phi's and takes those nodes as cfloop heads for the current
1001 cfloop instead and marks the incoming edge as backedge. */
1003 ir_graph *tail = find_tail(n);
1005 /* We have a cfloop, that is no straight line code,
1006 because we found a cfloop head!
1007 Next actions: Open a new cfloop on the cfloop tree and
1008 try to find inner cfloops */
1011 ir_loop *l = new_loop();
1013 /* Remove the cfloop from the stack ... */
1014 pop_scc_unmark_visit(n);
1016 /* The current backedge has been marked, that is temporarily eliminated,
1017 by find tail. Start the scc algorithm
1018 anew on the subgraph thats left (the current cfloop without the backedge)
1019 in order to find more inner cfloops. */
1023 assert(cg_irg_visited(n));
1033 * reset the backedge information for all callers in all irgs
1035 static void reset_isbe(void) {
1036 int i, n_irgs = get_irp_n_irgs();
1038 for (i = 0; i < n_irgs; ++i) {
1039 ir_graph *irg = get_irp_irg(i);
1041 if (irg->caller_isbe)
1042 free(irg->caller_isbe);
1043 irg->caller_isbe = NULL;
1045 if (irg->callee_isbe)
1046 free(irg->callee_isbe);
1047 irg->callee_isbe = NULL;
1051 /* ----------------------------------------------------------------------------------- */
1052 /* Another algorithm to compute recursion nesting depth */
1053 /* Walk the callgraph. For each crossed edge increase the loop depth by the edge */
1054 /* weight. Assign graphs the maximal depth. */
1055 /* ----------------------------------------------------------------------------------- */
1057 static void compute_loop_depth(ir_graph *irg, void *env) {
1058 int current_nesting = *(int *) env;
1059 int old_nesting = irg->callgraph_loop_depth;
1060 int old_visited = get_cg_irg_visited(irg);
1065 if (cg_irg_visited(irg)) return;
1067 mark_cg_irg_visited(irg);
1069 //printf(" old: %d new %d master %d", old_visited, get_cg_irg_visited(irg), master_cg_visited); DDMG(irg);
1072 if (old_nesting < current_nesting)
1073 irg->callgraph_loop_depth = current_nesting;
1075 if (current_nesting > irp->max_callgraph_loop_depth)
1076 irp->max_callgraph_loop_depth = current_nesting;
1078 if ((old_visited +1 < get_cg_irg_visited(irg)) || /* not yet visited */
1079 (old_nesting < current_nesting)) { /* propagate larger nesting */
1080 /* Don't walk the graph, but a tree that is an unfolded graph. */
1081 n_callees = get_irg_n_callees(irg);
1082 for (i = 0; i < n_callees; i++) {
1083 ir_graph *m = get_irg_callee(irg, i);
1084 *(int *)env += get_irg_callee_loop_depth(irg, i);
1085 compute_loop_depth(m, env);
1086 *(int *)env -= get_irg_callee_loop_depth(irg, i);
1090 set_cg_irg_visited(irg, master_cg_visited-1);
1093 /* ------------------------------------------------------------------------------------ */
1094 /* Another algorithm to compute recursion nesting depth */
1095 /* Walk the callgraph. For each crossed loop increase the nesting depth by one. */
1096 /* Assign graphs the maximal nesting depth. Don't increase if passing loops more than */
1098 /* ------------------------------------------------------------------------------------ */
1101 /* For callees, we want to remember the Call nodes, too. */
1102 typedef struct ana_entry2 {
1103 ir_loop **loop_stack; /**< a stack of ir_loop entries */
1104 int tos; /**< the top of stack entry */
1105 int recursion_nesting;
1109 * push a loop entry on the stack
1111 static void push2(ana_entry2 *e, ir_loop *g) {
1112 if (ARR_LEN(e->loop_stack) == e->tos) {
1113 ARR_APP1(ir_loop *, e->loop_stack, g);
1115 e->loop_stack[e->tos] = g;
1121 * returns the top of stack and pop it
1123 static ir_loop *pop2(ana_entry2 *e) {
1124 return e->loop_stack[--e->tos];
1128 * check if a loop g in on the stack. Did not check the TOS.
1130 static int in_stack(ana_entry2 *e, ir_loop *g) {
1132 for (i = e->tos-1; i >= 0; --i) {
1133 if (e->loop_stack[i] == g) return 1;
1138 static void compute_rec_depth(ir_graph *irg, void *env) {
1139 ana_entry2 *e = (ana_entry2 *)env;
1140 ir_loop *l = irg->l;
1141 int depth, old_depth = irg->callgraph_recursion_depth;
1145 if (cg_irg_visited(irg)) return;
1146 mark_cg_irg_visited(irg);
1148 /* -- compute and set the new nesting value -- */
1149 if ((l != irp->outermost_cg_loop) && !in_stack(e, l)) {
1151 e->recursion_nesting++;
1154 depth = e->recursion_nesting;
1156 if (old_depth < depth)
1157 irg->callgraph_recursion_depth = depth;
1159 if (depth > irp->max_callgraph_recursion_depth)
1160 irp->max_callgraph_recursion_depth = depth;
1162 /* -- spread the nesting value -- */
1163 if (depth == 0 || old_depth < depth) {
1164 /* Don't walk the graph, but a tree that is an unfolded graph.
1165 Therefore we unset the visited flag at the end. */
1166 n_callees = get_irg_n_callees(irg);
1167 for (i = 0; i < n_callees; ++i) {
1168 ir_graph *m = get_irg_callee(irg, i);
1169 compute_rec_depth(m, env);
1173 /* -- clean up -- */
1176 e->recursion_nesting--;
1178 set_cg_irg_visited(irg, master_cg_visited-1);
1182 /* ----------------------------------------------------------------------------------- */
1183 /* Another algorithm to compute the execution frequency of methods ignoring recursions. */
1184 /* Walk the callgraph. Ignore backedges. Use sum of execution frequencies of Call */
1185 /* nodes to evaluate a callgraph edge. */
1186 /* ----------------------------------------------------------------------------------- */
1188 /* Returns the method execution frequency of a graph. */
1189 double get_irg_method_execution_frequency(ir_graph *irg) {
1190 return irg->method_execution_frequency;
1194 * Increase the method execution frequency to freq if its current value is
1195 * smaller then this.
1197 static void set_irg_method_execution_frequency(ir_graph *irg, double freq) {
1198 irg->method_execution_frequency = freq;
1200 if (irp->max_method_execution_frequency < freq)
1201 irp->max_method_execution_frequency = freq;
1204 static void compute_method_execution_frequency(ir_graph *irg, void *env) {
1211 if (cg_irg_visited(irg)) return;
1213 /* We need the values of all predecessors (except backedges).
1214 So they must be marked. Else we will reach the node through
1215 one of the unmarked ones. */
1216 n_callers = get_irg_n_callers(irg);
1217 for (i = 0; i < n_callers; ++i) {
1218 ir_graph *m = get_irg_caller(irg, i);
1219 if (is_irg_caller_backedge(irg, i)) continue;
1220 if (!cg_irg_visited(m)) {
1224 mark_cg_irg_visited(irg);
1226 /* Compute the new frequency. */
1229 for (i = 0; i < n_callers; i++) {
1230 if (! is_irg_caller_backedge(irg, i)) {
1231 double edge_freq = get_irg_caller_method_execution_frequency(irg, i);
1232 assert(edge_freq >= 0);
1239 /* A starting point: method only called from outside,
1240 or only backedges as predecessors. */
1244 set_irg_method_execution_frequency(irg, freq);
1247 n_callees = get_irg_n_callees(irg);
1248 for (i = 0; i < n_callees; ++i) {
1249 compute_method_execution_frequency(get_irg_callee(irg, i), NULL);
1254 /* ----------------------------------------------------------------------------------- */
1255 /* The recursion stuff driver. */
1256 /* ----------------------------------------------------------------------------------- */
1258 /* Compute the backedges that represent recursions. */
1259 void find_callgraph_recursions(void) {
1260 int i, n_irgs = get_irp_n_irgs();
1264 /* -- compute the looptree. -- */
1266 /* The outermost graph. We start here. Then we start at all
1267 functions in irg list that are never called, then at the remaining
1268 unvisited ones. The third step is needed for functions that are not
1269 reachable from the outermost graph, but call themselves in a cycle. */
1270 assert(get_irp_main_irg());
1271 outermost_ir_graph = get_irp_main_irg();
1274 current_loop = NULL;
1275 new_loop(); /* sets current_loop */
1277 master_cg_visited++;
1278 cgscc(outermost_ir_graph);
1279 for (i = 0; i < n_irgs; ++i) {
1280 ir_graph *irg = get_irp_irg(i);
1281 if (!cg_irg_visited(irg) && get_irg_n_callers(irg) == 0)
1284 for (i = 0; i < n_irgs; ++i) {
1285 ir_graph *irg = get_irp_irg(i);
1286 if (!cg_irg_visited(irg))
1289 irp->outermost_cg_loop = current_loop;
1291 /* -- Reverse the backedge information. -- */
1292 for (i = 0; i < n_irgs; ++i) {
1293 ir_graph *irg = get_irp_irg(i);
1294 int j, n_callees = get_irg_n_callees(irg);
1295 for (j = 0; j < n_callees; ++j) {
1296 if (is_irg_callee_backedge(irg, j))
1297 set_irg_caller_backedge(get_irg_callee(irg, j), irg);
1301 irp->callgraph_state = irp_callgraph_and_calltree_consistent;
1304 /* Compute interprocedural performance estimates. */
1305 void compute_performance_estimates(void) {
1306 int i, n_irgs = get_irp_n_irgs();
1307 int current_nesting;
1310 assert(get_irp_exec_freq_state() != exec_freq_none && "execution frequency not calculated");
1312 /* -- compute the loop depth -- */
1313 current_nesting = 0;
1314 irp->max_callgraph_loop_depth = 0;
1315 master_cg_visited += 2;
1316 //printf(" ** starting at "); DDMG(get_irp_main_irg());
1317 compute_loop_depth(get_irp_main_irg(), ¤t_nesting);
1318 for (i = 0; i < n_irgs; i++) {
1319 ir_graph *irg = get_irp_irg(i);
1320 if ((get_cg_irg_visited(irg) < master_cg_visited-1) &&
1321 get_irg_n_callers(irg) == 0) {
1322 compute_loop_depth(irg, ¤t_nesting);
1323 //printf(" ** starting at "); DDMG(irg);
1326 for (i = 0; i < n_irgs; i++) {
1327 ir_graph *irg = get_irp_irg(i);
1328 if (get_cg_irg_visited(irg) < master_cg_visited-1) {
1329 compute_loop_depth(irg, ¤t_nesting);
1330 //printf(" ** starting at "); DDMG(irg);
1335 /* -- compute the recursion depth -- */
1336 e.loop_stack = NEW_ARR_F(ir_loop *, 0);
1338 e.recursion_nesting = 0;
1340 irp->max_callgraph_recursion_depth = 0;
1342 master_cg_visited += 2;
1343 compute_rec_depth(get_irp_main_irg(), &e);
1344 //printf(" ++ starting at "); DDMG(get_irp_main_irg());
1345 for (i = 0; i < n_irgs; i++) {
1346 ir_graph *irg = get_irp_irg(i);
1347 if ((get_cg_irg_visited(irg) < master_cg_visited-1) &&
1348 get_irg_n_callers(irg) == 0) {
1349 compute_rec_depth(irg, &e);
1350 //printf(" ++ starting at "); DDMG(irg);
1353 for (i = 0; i < n_irgs; i++) {
1354 ir_graph *irg = get_irp_irg(i);
1355 if (get_cg_irg_visited(irg) < master_cg_visited-1) {
1356 compute_rec_depth(irg, &e);
1357 //printf(" ++ starting at "); DDMG(irg);
1361 DEL_ARR_F(e.loop_stack);
1363 /* -- compute the execution frequency -- */
1364 irp->max_method_execution_frequency = 0;
1365 master_cg_visited += 2;
1366 assert(get_irg_n_callers(get_irp_main_irg()) == 0);
1367 compute_method_execution_frequency(get_irp_main_irg(), NULL);
1368 for (i = 0; i < n_irgs; i++) {
1369 ir_graph *irg = get_irp_irg(i);
1370 if ((get_cg_irg_visited(irg) < master_cg_visited-1) &&
1371 get_irg_n_callers(irg) == 0) {
1372 compute_method_execution_frequency(irg, NULL);
1375 for (i = 0; i < n_irgs; i++) {
1376 ir_graph *irg = get_irp_irg(i);
1377 if (get_cg_irg_visited(irg) < master_cg_visited-1) {
1378 compute_method_execution_frequency(irg, NULL);
1383 /* Returns the maximal loop depth of all paths from an external visible method to
1385 int get_irg_loop_depth(ir_graph *irg) {
1386 assert(irp->callgraph_state == irp_callgraph_consistent ||
1387 irp->callgraph_state == irp_callgraph_and_calltree_consistent);
1388 return irg->callgraph_loop_depth;
1391 /* Returns the maximal recursion depth of all paths from an external visible method to
1393 int get_irg_recursion_depth(ir_graph *irg) {
1394 assert(irp->callgraph_state == irp_callgraph_and_calltree_consistent);
1395 return irg->callgraph_recursion_depth;
1398 /* Computes the interprocedural loop nesting information. */
1399 void analyse_loop_nesting_depth(void) {
1400 ir_entity **free_methods = NULL;
1403 /* establish preconditions. */
1404 if (get_irp_callee_info_state() != irg_callee_info_consistent) {
1405 cgana(&arr_len, &free_methods);
1408 if (irp_callgraph_consistent != get_irp_callgraph_state()) {
1409 compute_callgraph();
1412 find_callgraph_recursions();
1414 compute_performance_estimates();
1416 set_irp_loop_nesting_depth_state(loop_nesting_depth_consistent);
1419 loop_nesting_depth_state get_irp_loop_nesting_depth_state(void) {
1420 return irp->lnd_state;
1422 void set_irp_loop_nesting_depth_state(loop_nesting_depth_state s) {
1425 void set_irp_loop_nesting_depth_state_inconsistent(void) {
1426 if (irp->lnd_state == loop_nesting_depth_consistent)
1427 irp->lnd_state = loop_nesting_depth_inconsistent;