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
31 #ifdef INTERPROCEDURAL_VIEW
40 #include "callgraph.h"
44 #include "irgraph_t.h"
48 #include "execution_frequency.h"
56 static int master_cg_visited = 0;
57 static INLINE int cg_irg_visited (ir_graph *n);
58 static INLINE void mark_cg_irg_visited(ir_graph *n);
59 static INLINE void set_cg_irg_visited (ir_graph *n, int i);
61 /** Returns the callgraph state of the program representation. */
62 irp_callgraph_state get_irp_callgraph_state(void) {
63 return irp->callgraph_state;
66 /* Sets the callgraph state of the program representation. */
67 void set_irp_callgraph_state(irp_callgraph_state s) {
68 irp->callgraph_state = s;
71 /* Returns the number of procedures that call the given irg. */
72 int get_irg_n_callers(ir_graph *irg) {
73 if (irg->callers) return ARR_LEN(irg->callers);
77 /* Returns the caller at position pos. */
78 ir_graph *get_irg_caller(ir_graph *irg, int pos) {
79 assert (pos >= 0 && pos < get_irg_n_callers(irg));
80 if (irg->callers) return irg->callers[pos];
84 #ifdef INTERPROCEDURAL_VIEW
85 /* Returns non-zero if the caller at position pos is "a backedge", i.e. a recursion. */
86 int is_irg_caller_backedge(ir_graph *irg, int pos) {
87 assert (pos >= 0 && pos < get_irg_n_callers(irg));
88 return irg->caller_isbe != NULL ? irg->caller_isbe[pos] : 0;
91 /** Search the caller in the list of all callers and set it's backedge property. */
92 static void set_irg_caller_backedge(ir_graph *irg, ir_graph *caller) {
93 int i, n_callers = get_irg_n_callers(irg);
95 /* allocate a new array on demand */
96 if (irg->caller_isbe == NULL)
97 irg->caller_isbe = xcalloc(n_callers, sizeof(irg->caller_isbe[0]));
98 for (i = 0; i < n_callers; ++i) {
99 if (get_irg_caller(irg, i) == caller) {
100 irg->caller_isbe[i] = 1;
106 /* Returns non-zero if the irg has a backedge caller. */
107 int has_irg_caller_backedge(ir_graph *irg) {
108 int i, n_callers = get_irg_n_callers(irg);
110 if (irg->caller_isbe != NULL) {
111 for (i = 0; i < n_callers; ++i)
112 if (irg->caller_isbe[i]) return 1;
119 * Find the reversion position of a caller.
120 * Given the position pos_caller of an caller of irg, return
121 * irg's callee position on that caller.
123 static int reverse_pos(ir_graph *callee, int pos_caller) {
124 ir_graph *caller = get_irg_caller(callee, pos_caller);
125 /* search the other relation for the corresponding edge. */
127 int i, n_callees = get_irg_n_callees(caller);
128 for (i = 0; i < n_callees; ++i) {
129 if (get_irg_callee(caller, i) == callee) {
135 assert(pos_callee >= 0);
140 /* Returns the maximal loop depth of call nodes that call along this edge. */
141 int get_irg_caller_loop_depth(ir_graph *irg, int pos) {
142 ir_graph *caller = get_irg_caller(irg, pos);
143 int pos_callee = reverse_pos(irg, pos);
145 return get_irg_callee_loop_depth(caller, pos_callee);
149 /* Returns the number of procedures that are called by the given irg. */
150 int get_irg_n_callees(ir_graph *irg) {
151 if (irg->callees) return ARR_LEN(irg->callees);
155 /* Returns the callee at position pos. */
156 ir_graph *get_irg_callee(ir_graph *irg, int pos) {
157 assert (pos >= 0 && pos < get_irg_n_callees(irg));
158 if (irg->callees) return irg->callees[pos]->irg;
162 /* Returns non-zero if the callee at position pos is "a backedge", i.e. a recursion. */
163 int is_irg_callee_backedge(ir_graph *irg, int pos) {
164 assert (pos >= 0 && pos < get_irg_n_callees(irg));
165 return irg->callee_isbe != NULL ? irg->callee_isbe[pos] : 0;
168 /* Returns non-zero if the irg has a backedge callee. */
169 int has_irg_callee_backedge(ir_graph *irg) {
170 int i, n_callees = get_irg_n_callees(irg);
172 if (irg->callee_isbe != NULL) {
173 for (i = 0; i < n_callees; ++i)
174 if (irg->callee_isbe[i]) return 1;
179 #ifdef INTERPROCEDURAL_VIEW
181 * Mark the callee at position pos as a backedge.
183 static void set_irg_callee_backedge(ir_graph *irg, int pos) {
184 int n = get_irg_n_callees(irg);
186 assert (pos >= 0 && pos < n);
188 /* allocate a new array on demand */
189 if (irg->callee_isbe == NULL)
190 irg->callee_isbe = xcalloc(n, sizeof(irg->callee_isbe[0]));
191 irg->callee_isbe[pos] = 1;
195 /* Returns the maximal loop depth of call nodes that call along this edge. */
196 int get_irg_callee_loop_depth(ir_graph *irg, int pos) {
197 assert (pos >= 0 && pos < get_irg_n_callees(irg));
198 if (irg->callees) return irg->callees[pos]->max_depth;
203 double get_irg_callee_execution_frequency(ir_graph *irg, int pos) {
204 ir_node **arr = irg->callees[pos]->call_list;
205 int i, n_Calls = ARR_LEN(arr);
208 for (i = 0; i < n_Calls; ++i) {
209 freq += get_irn_exec_freq(arr[i]);
214 double get_irg_callee_method_execution_frequency(ir_graph *irg, int pos) {
215 double call_freq = get_irg_callee_execution_frequency(irg, pos);
216 double meth_freq = get_irg_method_execution_frequency(irg);
217 return call_freq * meth_freq;
221 double get_irg_caller_method_execution_frequency(ir_graph *irg, int pos) {
222 ir_graph *caller = get_irg_caller(irg, pos);
223 int pos_callee = reverse_pos(irg, pos);
225 return get_irg_callee_method_execution_frequency(caller, pos_callee);
230 /* --------------------- Compute the callgraph ------------------------ */
233 * Walker called by compute_callgraph(), analyses all Call nodes.
235 static void ana_Call(ir_node *n, void *env) {
240 if (! is_Call(n)) return;
242 irg = get_irn_irg(n);
243 n_callees = get_Call_n_callees(n);
244 for (i = 0; i < n_callees; ++i) {
245 ir_entity *callee_e = get_Call_callee(n, i);
246 ir_graph *callee = get_entity_irg(callee_e);
250 cg_callee_entry *found;
255 pset_insert((pset *)callee->callers, irg, HASH_PTR(irg));
256 found = pset_find((pset *)irg->callees, &buf, HASH_PTR(callee));
257 if (found) { /* add Call node to list, compute new nesting. */
258 ir_node **arr = found->call_list;
259 ARR_APP1(ir_node *, arr, n);
260 found->call_list = arr;
261 } else { /* New node, add Call node and init nesting. */
262 found = (cg_callee_entry *)obstack_alloc(irg->obst, sizeof(*found));
264 found->call_list = NEW_ARR_F(ir_node *, 1);
265 found->call_list[0] = n;
266 found->max_depth = 0;
267 pset_insert((pset *)irg->callees, found, HASH_PTR(callee));
269 depth = get_loop_depth(get_irn_loop(get_nodes_block(n)));
270 found->max_depth = (depth > found->max_depth) ? depth : found->max_depth;
275 /** compare two ir graphs in a cg_callee_entry */
276 static int cg_callee_entry_cmp(const void *elt, const void *key) {
277 const cg_callee_entry *e1 = elt;
278 const cg_callee_entry *e2 = key;
279 return e1->irg != e2->irg;
282 /** compare two ir graphs */
283 static int graph_cmp(const void *elt, const void *key) {
284 const ir_graph *e1 = elt;
285 const ir_graph *e2 = key;
290 /* Construct and destruct the callgraph. */
291 void compute_callgraph(void) {
294 assert(! get_interprocedural_view()); /* Else walking will not reach the Call nodes. */
299 n_irgs = get_irp_n_irgs();
300 for (i = 0; i < n_irgs; ++i) {
301 ir_graph *irg = get_irp_irg(i);
302 assert(get_irg_callee_info_state(irg) == irg_callee_info_consistent);
303 irg->callees = (cg_callee_entry **)new_pset(cg_callee_entry_cmp, 8);
304 irg->callers = (ir_graph **)new_pset(graph_cmp, 8);
305 //construct_cf_backedges(irg);
308 /* Compute the call graph */
309 for (i = 0; i < n_irgs; ++i) {
310 ir_graph *irg = get_irp_irg(i);
311 construct_cf_backedges(irg); // We also find the maximal loop depth of a call.
312 irg_walk_graph(irg, ana_Call, NULL, NULL);
315 /* Change the sets to arrays. */
316 for (i = 0; i < n_irgs; ++i) {
318 cg_callee_entry *callee;
319 ir_graph *c, *irg = get_irp_irg(i);
320 pset *callee_set, *caller_set;
322 callee_set = (pset *)irg->callees;
323 count = pset_count(callee_set);
324 irg->callees = NEW_ARR_F(cg_callee_entry *, count);
325 irg->callee_isbe = NULL;
326 callee = pset_first(callee_set);
327 for (j = 0; j < count; ++j) {
328 irg->callees[j] = callee;
329 callee = pset_next(callee_set);
331 del_pset(callee_set);
332 assert(callee == NULL);
334 caller_set = (pset *)irg->callers;
335 count = pset_count(caller_set);
336 irg->callers = NEW_ARR_F(ir_graph *, count);
337 irg->caller_isbe = NULL;
338 c = pset_first(caller_set);
339 for (j = 0; j < count; ++j) {
341 c = pset_next(caller_set);
343 del_pset(caller_set);
346 set_irp_callgraph_state(irp_callgraph_consistent);
349 /* Destruct the callgraph. */
350 void free_callgraph(void) {
351 int i, n_irgs = get_irp_n_irgs();
352 for (i = 0; i < n_irgs; ++i) {
353 ir_graph *irg = get_irp_irg(i);
354 if (irg->callees) DEL_ARR_F(irg->callees);
355 if (irg->callers) DEL_ARR_F(irg->callers);
356 if (irg->callee_isbe) free(irg->callee_isbe);
357 if (irg->caller_isbe) free(irg->caller_isbe);
360 irg->callee_isbe = NULL;
361 irg->caller_isbe = NULL;
363 set_irp_callgraph_state(irp_callgraph_none);
366 /* ----------------------------------------------------------------------------------- */
367 /* A walker for the callgraph */
368 /* ----------------------------------------------------------------------------------- */
371 static void do_walk(ir_graph *irg, callgraph_walk_func *pre, callgraph_walk_func *post, void *env) {
374 if (cg_irg_visited(irg)) return;
375 mark_cg_irg_visited(irg);
380 n_callees = get_irg_n_callees(irg);
381 for (i = 0; i < n_callees; i++) {
382 ir_graph *m = get_irg_callee(irg, i);
383 do_walk(m, pre, post, env);
390 void callgraph_walk(callgraph_walk_func *pre, callgraph_walk_func *post, void *env) {
391 int i, n_irgs = get_irp_n_irgs();
394 do_walk(get_irp_main_irg(), pre, post, env);
395 for (i = 0; i < n_irgs; i++) {
396 ir_graph *irg = get_irp_irg(i);
397 if (!cg_irg_visited(irg) && get_irg_n_callers(irg) == 0)
398 do_walk(irg, pre, post, env);
400 for (i = 0; i < n_irgs; i++) {
401 ir_graph *irg = get_irp_irg(i);
402 if (!cg_irg_visited(irg))
403 do_walk(irg, pre, post, env);
407 /* ----------------------------------------------------------------------------------- */
408 /* loop construction algorithm */
409 /* ----------------------------------------------------------------------------------- */
411 static ir_graph *outermost_ir_graph; /**< The outermost graph the scc is computed
413 static ir_loop *current_loop; /**< Current cfloop construction is working
415 static int loop_node_cnt = 0; /**< Counts the number of allocated cfloop nodes.
416 Each cfloop node gets a unique number.
417 What for? ev. remove. @@@ */
418 #ifdef INTERPROCEDURAL_VIEW
419 static int current_dfn = 1; /**< Counter to generate depth first numbering
424 /*-----------------*/
425 /* Node attributes */
426 /*-----------------*/
428 typedef struct scc_info {
429 int in_stack; /**< Marks whether node is on the stack. */
430 int dfn; /**< Depth first search number. */
431 int uplink; /**< dfn number of ancestor. */
436 * allocates a new scc_info of the obstack
438 static INLINE scc_info *new_scc_info(void) {
439 scc_info *info = obstack_alloc (outermost_ir_graph->obst, sizeof(*info));
440 memset(info, 0, sizeof(*info));
445 * Returns non-zero if a graph was already visited.
448 cg_irg_visited(ir_graph *irg) {
449 scc_info *info = get_irg_link(irg);
450 assert(info && "missing call to init_scc");
451 return (info->visited >= master_cg_visited);
455 * Marks a graph as visited.
458 mark_cg_irg_visited(ir_graph *irg) {
459 scc_info *info = get_irg_link(irg);
460 assert(info && "missing call to init_scc");
461 info->visited = master_cg_visited;
465 * Set a graphs visited flag to i.
468 set_cg_irg_visited(ir_graph *irg, int i) {
469 scc_info *info = get_irg_link(irg);
470 assert(info && "missing call to init_scc");
475 * Returns the visited flag of a graph.
478 get_cg_irg_visited(ir_graph *irg) {
479 scc_info *info = get_irg_link(irg);
480 assert(info && "missing call to init_scc");
481 return info->visited;
485 mark_irg_in_stack(ir_graph *irg) {
486 scc_info *info = get_irg_link(irg);
487 assert(info && "missing call to init_scc");
492 mark_irg_not_in_stack(ir_graph *irg) {
493 scc_info *info = get_irg_link(irg);
494 assert(info && "missing call to init_scc");
499 irg_is_in_stack(ir_graph *irg) {
500 scc_info *info = get_irg_link(irg);
501 assert(info && "missing call to init_scc");
502 return info->in_stack;
506 set_irg_uplink(ir_graph *irg, int uplink) {
507 scc_info *info = get_irg_link(irg);
508 assert(info && "missing call to init_scc");
509 info->uplink = uplink;
513 get_irg_uplink(ir_graph *irg) {
514 scc_info *info = get_irg_link(irg);
515 assert(info && "missing call to init_scc");
520 set_irg_dfn(ir_graph *irg, int dfn) {
521 scc_info *info = get_irg_link(irg);
522 assert(info && "missing call to init_scc");
527 get_irg_dfn(ir_graph *irg) {
528 scc_info *info = get_irg_link(irg);
529 assert(info && "missing call to init_scc");
533 /**********************************************************************/
535 /**********************************************************************/
537 static ir_graph **stack = NULL;
538 static int tos = 0; /**< top of stack */
541 * Initialize the irg stack.
543 static INLINE void init_stack(void) {
545 ARR_RESIZE (ir_graph *, stack, 1000);
547 stack = NEW_ARR_F (ir_graph *, 1000);
553 * push a graph on the irg stack
554 * @param n the graph to be pushed
556 static INLINE void push(ir_graph *irg) {
557 if (tos == ARR_LEN (stack)) {
558 int nlen = ARR_LEN (stack) * 2;
559 ARR_RESIZE (ir_node *, stack, nlen);
562 mark_irg_in_stack(irg);
566 * return the topmost graph on the stack and pop it
568 static INLINE ir_graph *pop(void) {
569 ir_graph *irg = stack[--tos];
570 mark_irg_not_in_stack(irg);
575 * The nodes up to irg belong to the current loop.
576 * Removes them from the stack and adds them to the current loop.
578 static INLINE void pop_scc_to_loop(ir_graph *irg) {
584 set_irg_dfn(m, loop_node_cnt);
585 add_loop_node(current_loop, (ir_node *)m);
587 //m->callgraph_loop_depth = current_loop->depth;
591 #ifdef INTERPROCEDURAL_VIEW
592 /* GL ??? my last son is my grandson??? Removes cfloops with no
593 ir_nodes in them. Such loops have only another loop as son. (Why
594 can't they have two loops as sons? Does it never get that far? ) */
595 static void close_loop(ir_loop *l) {
596 int last = get_loop_n_elements(l) - 1;
597 loop_element lelement = get_loop_element(l, last);
598 ir_loop *last_son = lelement.son;
600 if (get_kind(last_son) == k_ir_loop &&
601 get_loop_n_elements(last_son) == 1) {
604 lelement = get_loop_element(last_son, 0);
606 if(get_kind(gson) == k_ir_loop) {
607 loop_element new_last_son;
609 gson -> outer_loop = l;
610 new_last_son.son = gson;
611 l -> children[last] = new_last_son;
620 * Removes and unmarks all nodes up to n from the stack.
621 * The nodes must be visited once more to assign them to a scc.
623 static INLINE void pop_scc_unmark_visit(ir_graph *n) {
628 set_cg_irg_visited(m, 0);
632 /**********************************************************************/
633 /* The loop data structure. **/
634 /**********************************************************************/
636 #ifdef INTERPROCEDURAL_VIEW
638 * Allocates a new loop as son of current_loop. Sets current_loop
639 * to the new loop and returns the father.
641 static ir_loop *new_loop(void) {
642 ir_loop *father, *son;
644 father = current_loop;
646 son = obstack_alloc(outermost_ir_graph->obst, sizeof(*son));
647 memset(son, 0, sizeof(*son));
648 son->kind = k_ir_loop;
649 son->children = NEW_ARR_F (loop_element, 0);
654 son->outer_loop = father;
655 add_loop_son(father, son);
656 son->depth = father->depth + 1;
657 } else { /* The root loop */
658 son->outer_loop = son;
663 son->loop_nr = get_irp_new_node_nr();
670 /**********************************************************************/
671 /* Constructing and destructing the loop/backedge information. **/
672 /**********************************************************************/
674 /* Initialization steps. **********************************************/
685 n_irgs = get_irp_n_irgs();
686 for (i = 0; i < n_irgs; ++i) {
687 ir_graph *irg = get_irp_irg(i);
688 set_irg_link(irg, new_scc_info());
689 irg->callgraph_recursion_depth = 0;
690 irg->callgraph_loop_depth = 0;
694 /** Returns non-zero if n is a loop header, i.e., it is a Block node
695 * and has predecessors within the cfloop and out of the cfloop.
697 * @param root: only needed for assertion.
700 is_head(ir_graph *n, ir_graph *root)
703 int some_outof_loop = 0, some_in_loop = 0;
705 arity = get_irg_n_callees(n);
706 for (i = 0; i < arity; i++) {
707 ir_graph *pred = get_irg_callee(n, i);
708 if (is_irg_callee_backedge(n, i)) continue;
709 if (!irg_is_in_stack(pred)) {
712 if (get_irg_uplink(pred) < get_irg_uplink(root)) {
713 assert(get_irg_uplink(pred) >= get_irg_uplink(root));
719 return some_outof_loop & some_in_loop;
723 * Returns non-zero if n is possible loop head of an endless loop.
724 * I.e., it is a Block, Phi or Filter node and has only predecessors
726 * @arg root: only needed for assertion.
729 is_endless_head(ir_graph *n, ir_graph *root)
732 int some_outof_loop = 0, some_in_loop = 0;
734 arity = get_irg_n_callees(n);
735 for (i = 0; i < arity; i++) {
736 ir_graph *pred = get_irg_callee(n, i);
738 if (is_irg_callee_backedge(n, i)) { continue; }
739 if (!irg_is_in_stack(pred)) {
742 if(get_irg_uplink(pred) < get_irg_uplink(root)) {
743 assert(get_irg_uplink(pred) >= get_irg_uplink(root));
749 return !some_outof_loop & some_in_loop;
753 * Check whether there is a parallel edge in the ip control flow.
757 is_ip_head(ir_graph *n, ir_graph *pred)
760 int iv_rem = get_interprocedural_view();
761 set_interprocedural_view(1);
763 ir_node *sblock = get_irg_start_block(n);
764 int i, arity = get_Block_n_cfgpreds(sblock);
766 //printf(" edge from "); DDMG(n);
767 //printf(" to pred "); DDMG(pred);
768 //printf(" sblock "); DDMN(sblock);
770 for (i = 0; i < arity; i++) {
771 ir_node *pred_cfop = skip_Proj(get_Block_cfgpred(sblock, i));
772 //printf(" "); DDMN(pred_cfop);
773 if (get_irn_op(pred_cfop) == op_CallBegin) { /* could be Unknown */
774 ir_graph *ip_pred = get_irn_irg(pred_cfop);
775 //printf(" "); DDMG(ip_pred);
776 if ((ip_pred == pred) && is_backedge(sblock, i)) {
777 //printf(" found\n");
783 set_interprocedural_view(iv_rem);
788 * Returns index of the predecessor with the smallest dfn number
789 * greater-equal than limit.
792 smallest_dfn_pred(ir_graph *n, int limit)
794 int i, index = -2, min = -1;
796 int arity = get_irg_n_callees(n);
797 for (i = 0; i < arity; i++) {
798 ir_graph *pred = get_irg_callee(n, i);
799 if (is_irg_callee_backedge(n, i) || !irg_is_in_stack(pred)) continue;
800 if (get_irg_dfn(pred) >= limit && (min == -1 || get_irg_dfn(pred) < min)) {
802 min = get_irg_dfn(pred);
809 /** Returns index of the predecessor with the largest dfn number. */
811 largest_dfn_pred(ir_graph *n)
813 int i, index = -2, max = -1;
815 int arity = get_irg_n_callees(n);
816 for (i = 0; i < arity; i++) {
817 ir_graph *pred = get_irg_callee(n, i);
818 if (is_irg_callee_backedge (n, i) || !irg_is_in_stack(pred)) continue;
819 if (get_irg_dfn(pred) > max) {
821 max = get_irg_dfn(pred);
830 find_tail(ir_graph *n) {
832 int i, res_index = -2;
835 if (!icfg && rm_cyclic_phis && remove_cyclic_phis (n)) return NULL;
837 m = stack[tos-1]; /* tos = top of stack */
838 if (is_head (m, n)) {
839 res_index = smallest_dfn_pred(m, 0);
840 if ((res_index == -2) && /* no smallest dfn pred found. */
844 if (m == n) return NULL; // Is this to catch Phi - self loops?
845 for (i = tos-2; i >= 0; --i) {
848 if (is_head (m, n)) {
849 res_index = smallest_dfn_pred (m, get_irg_dfn(m) + 1);
850 if (res_index == -2) /* no smallest dfn pred found. */
851 res_index = largest_dfn_pred (m);
853 if ((m == n) && (res_index == -2)) {
859 /* We should not walk past our selves on the stack: The upcoming nodes
860 are not in this loop. We assume a loop not reachable from Start. */
869 /* A dead loop not reachable from Start. */
870 for (i = tos-2; i >= 0; --i) {
872 if (is_endless_head (m, n)) {
873 res_index = smallest_dfn_pred (m, get_irg_dfn(m) + 1);
874 if (res_index == -2) /* no smallest dfn pred found. */
875 res_index = largest_dfn_pred (m);
878 if (m == n) { break; } /* It's not an unreachable loop, either. */
880 //assert(0 && "no head found on stack");
884 assert (res_index > -2);
886 set_irg_callee_backedge (m, res_index);
887 return get_irg_callee(m, res_index);
891 find_tail(ir_graph *n) {
893 int i, res_index = -2;
896 ir_graph *in_and_out = NULL;
897 ir_graph *only_in = NULL;
898 ir_graph *ip_in_and_out = NULL;
899 ir_graph *ip_only_in = NULL;
901 //printf("find tail for "); DDMG(n);
903 for (i = tos-1; i >= 0; --i) {
904 ir_graph *pred = (i < tos -1) ? stack[i+1] : n;
907 if (is_head (m, n)) {
908 //printf(" found 1a! "); DDM;
910 if (is_ip_head(pred, m)) {
911 //printf(" found 1b! "); DDM;
914 } else if (!ip_only_in && is_endless_head(m, n)) {
916 //printf(" found 2a! "); DDM;
917 if (is_ip_head(pred, m)) {
918 //printf(" found 2b! "); DDM;
921 } else if (is_ip_head(pred, m)) {
922 //printf(" found 3! "); DDM; This happens for self recursions in the second
923 //assert(0); scc iteration (the one to flip the loop.)
926 if (ip_in_and_out) break; /* That's what we really want. */
928 if (m == n) break; /* Don't walk past n on the stack! */
932 if (!in_and_out && !only_in)
933 /* There is no loop */
937 /* Is there a head in the callgraph without a head in the
939 assert(in_and_out || only_in);
941 m = (ip_in_and_out) ? ip_in_and_out : ip_only_in;
944 m = (in_and_out) ? in_and_out : only_in;
946 //printf("*** head is "); DDMG(m);
948 res_index = smallest_dfn_pred (m, get_irg_dfn(m) + 1);
949 if (res_index == -2) /* no smallest dfn pred found. */
950 res_index = largest_dfn_pred (m);
952 set_irg_callee_backedge (m, res_index);
953 res = get_irg_callee(m, res_index);
954 //printf("*** tail is "); DDMG(res);
959 /*-----------------------------------------------------------*
960 * The core algorithm. *
961 *-----------------------------------------------------------*/
964 static void cgscc(ir_graph *n) {
967 if (cg_irg_visited(n)) return;
968 mark_cg_irg_visited(n);
970 /* Initialize the node */
971 set_irg_dfn(n, current_dfn); /* Depth first number for this node */
972 set_irg_uplink(n, current_dfn); /* ... is default uplink. */
976 arity = get_irg_n_callees(n);
977 for (i = 0; i < arity; i++) {
979 if (is_irg_callee_backedge(n, i)) continue;
980 m = get_irg_callee(n, i);
982 /** This marks the backedge, but does it guarantee a correct loop tree? */
983 //if (m == n) { set_irg_callee_backedge(n, i); continue; }
986 if (irg_is_in_stack(m)) {
987 /* Uplink of m is smaller if n->m is a backedge.
988 Propagate the uplink to mark the cfloop. */
989 if (get_irg_uplink(m) < get_irg_uplink(n))
990 set_irg_uplink(n, get_irg_uplink(m));
994 if (get_irg_dfn(n) == get_irg_uplink(n)) {
995 /* This condition holds for
996 1) the node with the incoming backedge.
997 That is: We found a cfloop!
998 2) Straight line code, because no uplink has been propagated, so the
999 uplink still is the same as the dfn.
1001 But n might not be a proper cfloop head for the analysis. Proper cfloop
1002 heads are Block and Phi nodes. find_tail searches the stack for
1003 Block's and Phi's and takes those nodes as cfloop heads for the current
1004 cfloop instead and marks the incoming edge as backedge. */
1006 ir_graph *tail = find_tail(n);
1008 /* We have a cfloop, that is no straight line code,
1009 because we found a cfloop head!
1010 Next actions: Open a new cfloop on the cfloop tree and
1011 try to find inner cfloops */
1014 ir_loop *l = new_loop();
1016 /* Remove the cfloop from the stack ... */
1017 pop_scc_unmark_visit (n);
1019 /* The current backedge has been marked, that is temporarily eliminated,
1020 by find tail. Start the scc algorithm
1021 anew on the subgraph thats left (the current cfloop without the backedge)
1022 in order to find more inner cfloops. */
1026 assert (cg_irg_visited(n));
1036 * reset the backedge information for all callers in all irgs
1038 static void reset_isbe(void) {
1039 int i, n_irgs = get_irp_n_irgs();
1041 for (i = 0; i < n_irgs; ++i) {
1042 ir_graph *irg = get_irp_irg(i);
1044 if (irg->caller_isbe)
1045 free(irg->caller_isbe);
1046 irg->caller_isbe = NULL;
1048 if (irg->callee_isbe)
1049 free(irg->callee_isbe);
1050 irg->callee_isbe = NULL;
1058 /* ----------------------------------------------------------------------------------- */
1059 /* Another algorithm to compute recursion nesting depth */
1060 /* Walk the callgraph. For each crossed edge increase the loop depth by the edge */
1061 /* weight. Assign graphs the maximal depth. */
1062 /* ----------------------------------------------------------------------------------- */
1064 static void compute_loop_depth (ir_graph *irg, void *env) {
1065 int current_nesting = *(int *) env;
1066 int old_nesting = irg->callgraph_loop_depth;
1067 int old_visited = get_cg_irg_visited(irg);
1072 if (cg_irg_visited(irg)) return;
1074 mark_cg_irg_visited(irg);
1076 //printf(" old: %d new %d master %d", old_visited, get_cg_irg_visited(irg), master_cg_visited); DDMG(irg);
1079 if (old_nesting < current_nesting)
1080 irg->callgraph_loop_depth = current_nesting;
1082 if (current_nesting > irp->max_callgraph_loop_depth)
1083 irp->max_callgraph_loop_depth = current_nesting;
1085 if ((old_visited +1 < get_cg_irg_visited(irg)) || /* not yet visited */
1086 (old_nesting < current_nesting)) { /* propagate larger nesting */
1087 /* Don't walk the graph, but a tree that is an unfolded graph. */
1088 n_callees = get_irg_n_callees(irg);
1089 for (i = 0; i < n_callees; i++) {
1090 ir_graph *m = get_irg_callee(irg, i);
1091 *(int *)env += get_irg_callee_loop_depth(irg, i);
1092 compute_loop_depth(m, env);
1093 *(int *)env -= get_irg_callee_loop_depth(irg, i);
1097 set_cg_irg_visited(irg, master_cg_visited-1);
1100 /* ------------------------------------------------------------------------------------ */
1101 /* Another algorithm to compute recursion nesting depth */
1102 /* Walk the callgraph. For each crossed loop increase the nesting depth by one. */
1103 /* Assign graphs the maximal nesting depth. Don't increase if passing loops more than */
1105 /* ------------------------------------------------------------------------------------ */
1108 /* For callees, we want to remember the Call nodes, too. */
1109 typedef struct ana_entry2 {
1110 ir_loop **loop_stack; /**< a stack of ir_loop entries */
1111 int tos; /**< the top of stack entry */
1112 int recursion_nesting;
1116 * push a loop entry on the stack
1118 static void push2(ana_entry2 *e, ir_loop *g) {
1119 if (ARR_LEN(e->loop_stack) == e->tos) {
1120 ARR_APP1(ir_loop *, e->loop_stack, g);
1122 e->loop_stack[e->tos] = g;
1128 * returns the top of stack and pop it
1130 static ir_loop *pop2(ana_entry2 *e) {
1131 return e->loop_stack[--e->tos];
1135 * check if a loop g in on the stack. Did not check the TOS.
1137 static int in_stack(ana_entry2 *e, ir_loop *g) {
1139 for (i = e->tos-1; i >= 0; --i) {
1140 if (e->loop_stack[i] == g) return 1;
1145 static void compute_rec_depth (ir_graph *irg, void *env) {
1146 ana_entry2 *e = (ana_entry2 *)env;
1147 ir_loop *l = irg->l;
1148 int depth, old_depth = irg->callgraph_recursion_depth;
1152 if (cg_irg_visited(irg)) return;
1153 mark_cg_irg_visited(irg);
1155 /* -- compute and set the new nesting value -- */
1156 if ((l != irp->outermost_cg_loop) && !in_stack(e, l)) {
1158 e->recursion_nesting++;
1161 depth = e->recursion_nesting;
1163 if (old_depth < depth)
1164 irg->callgraph_recursion_depth = depth;
1166 if (depth > irp->max_callgraph_recursion_depth)
1167 irp->max_callgraph_recursion_depth = depth;
1169 /* -- spread the nesting value -- */
1170 if (depth == 0 || old_depth < depth) {
1171 /* Don't walk the graph, but a tree that is an unfolded graph.
1172 Therefore we unset the visited flag at the end. */
1173 n_callees = get_irg_n_callees(irg);
1174 for (i = 0; i < n_callees; i++) {
1175 ir_graph *m = get_irg_callee(irg, i);
1176 compute_rec_depth(m, env);
1180 /* -- clean up -- */
1183 e->recursion_nesting--;
1185 set_cg_irg_visited(irg, master_cg_visited-1);
1189 /* ----------------------------------------------------------------------------------- */
1190 /* Another algorithm to compute the execution frequency of methods ignoring recursions. */
1191 /* Walk the callgraph. Ignore backedges. Use sum of execution frequencies of Call */
1192 /* nodes to evaluate a callgraph edge. */
1193 /* ----------------------------------------------------------------------------------- */
1195 #ifdef INTERPROCEDURAL_VIEW
1196 /* Returns the method execution frequency of a graph. */
1197 double get_irg_method_execution_frequency (ir_graph *irg) {
1198 return irg->method_execution_frequency;
1202 * Increase the method execution frequency to freq if its current value is
1203 * smaller then this.
1205 static void set_irg_method_execution_frequency(ir_graph *irg, double freq) {
1206 irg->method_execution_frequency = freq;
1208 if (irp->max_method_execution_frequency < freq)
1209 irp->max_method_execution_frequency = freq;
1212 static void compute_method_execution_frequency(ir_graph *irg, void *env) {
1219 if (cg_irg_visited(irg)) return;
1221 /* We need the values of all predecessors (except backedges).
1222 So they must be marked. Else we will reach the node through
1223 one of the unmarked ones. */
1224 n_callers = get_irg_n_callers(irg);
1225 for (i = 0; i < n_callers; i++) {
1226 ir_graph *m = get_irg_caller(irg, i);
1227 if (is_irg_caller_backedge(irg, i)) continue;
1228 if (!cg_irg_visited(m)) {
1232 mark_cg_irg_visited(irg);
1234 /* Compute the new frequency. */
1237 for (i = 0; i < n_callers; i++) {
1238 if (! is_irg_caller_backedge(irg, i)) {
1239 double edge_freq = get_irg_caller_method_execution_frequency(irg, i);
1240 assert(edge_freq >= 0);
1247 /* A starting point: method only called from outside,
1248 or only backedges as predecessors. */
1252 set_irg_method_execution_frequency(irg, freq);
1255 n_callees = get_irg_n_callees(irg);
1256 for (i = 0; i < n_callees; i++) {
1257 compute_method_execution_frequency(get_irg_callee(irg, i), NULL);
1262 /* ----------------------------------------------------------------------------------- */
1263 /* The recursion stuff driver. */
1264 /* ----------------------------------------------------------------------------------- */
1266 /* Compute the backedges that represent recursions. */
1267 void find_callgraph_recursions(void) {
1268 int i, n_irgs = get_irp_n_irgs();
1272 /* -- compute the looptree. -- */
1274 /* The outermost graph. We start here. Then we start at all
1275 functions in irg list that are never called, then at the remaining
1276 unvisited ones. The third step is needed for functions that are not
1277 reachable from the outermost graph, but call themselves in a cycle. */
1278 assert(get_irp_main_irg());
1279 outermost_ir_graph = get_irp_main_irg();
1282 current_loop = NULL;
1283 new_loop(); /* sets current_loop */
1285 master_cg_visited++;
1286 cgscc(outermost_ir_graph);
1287 for (i = 0; i < n_irgs; i++) {
1288 ir_graph *irg = get_irp_irg(i);
1289 if (!cg_irg_visited(irg) && get_irg_n_callers(irg) == 0)
1292 for (i = 0; i < n_irgs; i++) {
1293 ir_graph *irg = get_irp_irg(i);
1294 if (!cg_irg_visited(irg))
1297 irp->outermost_cg_loop = current_loop;
1299 /* -- Reverse the backedge information. -- */
1300 for (i = 0; i < n_irgs; i++) {
1301 ir_graph *irg = get_irp_irg(i);
1302 int j, n_callees = get_irg_n_callees(irg);
1303 for (j = 0; j < n_callees; ++j) {
1304 if (is_irg_callee_backedge(irg, j))
1305 set_irg_caller_backedge(get_irg_callee(irg, j), irg);
1309 irp->callgraph_state = irp_callgraph_and_calltree_consistent;
1312 /* Compute interprocedural performance estimates. */
1313 void compute_performance_estimates(void) {
1314 int i, n_irgs = get_irp_n_irgs();
1315 int current_nesting;
1318 assert(get_irp_exec_freq_state() != exec_freq_none && "execution frequency not calculated");
1320 /* -- compute the loop depth -- */
1321 current_nesting = 0;
1322 irp->max_callgraph_loop_depth = 0;
1323 master_cg_visited += 2;
1324 //printf (" ** starting at "); DDMG(get_irp_main_irg());
1325 compute_loop_depth(get_irp_main_irg(), ¤t_nesting);
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 get_irg_n_callers(irg) == 0) {
1330 compute_loop_depth(irg, ¤t_nesting);
1331 //printf (" ** starting at "); DDMG(irg);
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 compute_loop_depth(irg, ¤t_nesting);
1338 //printf (" ** starting at "); DDMG(irg);
1343 /* -- compute the recursion depth -- */
1344 e.loop_stack = NEW_ARR_F(ir_loop *, 0);
1346 e.recursion_nesting = 0;
1348 irp->max_callgraph_recursion_depth = 0;
1350 master_cg_visited += 2;
1351 compute_rec_depth(get_irp_main_irg(), &e);
1352 //printf (" ++ starting at "); DDMG(get_irp_main_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 get_irg_n_callers(irg) == 0) {
1357 compute_rec_depth(irg, &e);
1358 //printf (" ++ starting at "); DDMG(irg);
1361 for (i = 0; i < n_irgs; i++) {
1362 ir_graph *irg = get_irp_irg(i);
1363 if (get_cg_irg_visited(irg) < master_cg_visited-1) {
1364 compute_rec_depth(irg, &e);
1365 //printf (" ++ starting at "); DDMG(irg);
1369 DEL_ARR_F(e.loop_stack);
1371 /* -- compute the execution frequency -- */
1372 irp->max_method_execution_frequency = 0;
1373 master_cg_visited += 2;
1374 assert(get_irg_n_callers(get_irp_main_irg()) == 0);
1375 compute_method_execution_frequency(get_irp_main_irg(), NULL);
1376 for (i = 0; i < n_irgs; i++) {
1377 ir_graph *irg = get_irp_irg(i);
1378 if ((get_cg_irg_visited(irg) < master_cg_visited-1) &&
1379 get_irg_n_callers(irg) == 0) {
1380 compute_method_execution_frequency(irg, NULL);
1383 for (i = 0; i < n_irgs; i++) {
1384 ir_graph *irg = get_irp_irg(i);
1385 if (get_cg_irg_visited(irg) < master_cg_visited-1) {
1386 compute_method_execution_frequency(irg, NULL);
1392 /* Returns the maximal loop depth of all paths from an external visible method to
1394 int get_irg_loop_depth(ir_graph *irg) {
1395 assert(irp->callgraph_state == irp_callgraph_consistent ||
1396 irp->callgraph_state == irp_callgraph_and_calltree_consistent);
1397 return irg->callgraph_loop_depth;
1400 /* Returns the maximal recursion depth of all paths from an external visible method to
1402 int get_irg_recursion_depth(ir_graph *irg) {
1403 assert(irp->callgraph_state == irp_callgraph_and_calltree_consistent);
1404 return irg->callgraph_recursion_depth;
1407 /* Computes the interprocedural loop nesting information. */
1408 void analyse_loop_nesting_depth(void) {
1409 ir_entity **free_methods = NULL;
1412 /* establish preconditions. */
1413 if (get_irp_callee_info_state() != irg_callee_info_consistent) {
1414 cgana(&arr_len, &free_methods);
1417 if (irp_callgraph_consistent != get_irp_callgraph_state()) {
1418 compute_callgraph();
1421 find_callgraph_recursions();
1423 compute_performance_estimates();
1425 set_irp_loop_nesting_depth_state(loop_nesting_depth_consistent);
1429 loop_nesting_depth_state get_irp_loop_nesting_depth_state(void) {
1430 return irp->lnd_state;
1432 void set_irp_loop_nesting_depth_state(loop_nesting_depth_state s) {
1435 void set_irp_loop_nesting_depth_state_inconsistent(void) {
1436 if (irp->lnd_state == loop_nesting_depth_consistent)
1437 irp->lnd_state = loop_nesting_depth_inconsistent;