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 ? rbitset_is_set(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 = rbitset_malloc(n_callers);
98 for (i = 0; i < n_callers; ++i) {
99 if (get_irg_caller(irg, i) == caller) {
100 rbitset_set(irg->caller_isbe, i);
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 (rbitset_is_set(irg->caller_isbe, i))
120 * Find the reversion position of a caller.
121 * Given the position pos_caller of an caller of irg, return
122 * irg's callee position on that caller.
124 static int reverse_pos(ir_graph *callee, int pos_caller) {
125 ir_graph *caller = get_irg_caller(callee, pos_caller);
126 /* search the other relation for the corresponding edge. */
128 int i, n_callees = get_irg_n_callees(caller);
129 for (i = 0; i < n_callees; ++i) {
130 if (get_irg_callee(caller, i) == callee) {
136 assert(pos_callee >= 0);
141 /* Returns the maximal loop depth of call nodes that call along this edge. */
142 int get_irg_caller_loop_depth(ir_graph *irg, int pos) {
143 ir_graph *caller = get_irg_caller(irg, pos);
144 int pos_callee = reverse_pos(irg, pos);
146 return get_irg_callee_loop_depth(caller, pos_callee);
150 /* Returns the number of procedures that are called by the given irg. */
151 int get_irg_n_callees(ir_graph *irg) {
152 if (irg->callees) return ARR_LEN(irg->callees);
156 /* Returns the callee at position pos. */
157 ir_graph *get_irg_callee(ir_graph *irg, int pos) {
158 assert (pos >= 0 && pos < get_irg_n_callees(irg));
159 if (irg->callees) return irg->callees[pos]->irg;
163 /* Returns non-zero if the callee at position pos is "a backedge", i.e. a recursion. */
164 int is_irg_callee_backedge(ir_graph *irg, int pos) {
165 assert (pos >= 0 && pos < get_irg_n_callees(irg));
166 return irg->callee_isbe != NULL ? irg->callee_isbe[pos] : 0;
169 /* Returns non-zero if the irg has a backedge callee. */
170 int has_irg_callee_backedge(ir_graph *irg) {
171 int i, n_callees = get_irg_n_callees(irg);
173 if (irg->callee_isbe != NULL) {
174 for (i = 0; i < n_callees; ++i)
175 if (irg->callee_isbe[i]) return 1;
180 #ifdef INTERPROCEDURAL_VIEW
182 * Mark the callee at position pos as a backedge.
184 static void set_irg_callee_backedge(ir_graph *irg, int pos) {
185 int n = get_irg_n_callees(irg);
187 assert (pos >= 0 && pos < n);
189 /* allocate a new array on demand */
190 if (irg->callee_isbe == NULL)
191 irg->callee_isbe = xcalloc(n, sizeof(irg->callee_isbe[0]));
192 irg->callee_isbe[pos] = 1;
196 /* Returns the maximal loop depth of call nodes that call along this edge. */
197 int get_irg_callee_loop_depth(ir_graph *irg, int pos) {
198 assert (pos >= 0 && pos < get_irg_n_callees(irg));
199 if (irg->callees) return irg->callees[pos]->max_depth;
204 double get_irg_callee_execution_frequency(ir_graph *irg, int pos) {
205 ir_node **arr = irg->callees[pos]->call_list;
206 int i, n_Calls = ARR_LEN(arr);
209 for (i = 0; i < n_Calls; ++i) {
210 freq += get_irn_exec_freq(arr[i]);
215 double get_irg_callee_method_execution_frequency(ir_graph *irg, int pos) {
216 double call_freq = get_irg_callee_execution_frequency(irg, pos);
217 double meth_freq = get_irg_method_execution_frequency(irg);
218 return call_freq * meth_freq;
222 double get_irg_caller_method_execution_frequency(ir_graph *irg, int pos) {
223 ir_graph *caller = get_irg_caller(irg, pos);
224 int pos_callee = reverse_pos(irg, pos);
226 return get_irg_callee_method_execution_frequency(caller, pos_callee);
231 /* --------------------- Compute the callgraph ------------------------ */
234 * Walker called by compute_callgraph(), analyses all Call nodes.
236 static void ana_Call(ir_node *n, void *env) {
241 if (! is_Call(n)) return;
243 irg = get_irn_irg(n);
244 n_callees = get_Call_n_callees(n);
245 for (i = 0; i < n_callees; ++i) {
246 ir_entity *callee_e = get_Call_callee(n, i);
247 ir_graph *callee = get_entity_irg(callee_e);
251 cg_callee_entry *found;
256 pset_insert((pset *)callee->callers, irg, HASH_PTR(irg));
257 found = pset_find((pset *)irg->callees, &buf, HASH_PTR(callee));
258 if (found) { /* add Call node to list, compute new nesting. */
259 ir_node **arr = found->call_list;
260 ARR_APP1(ir_node *, arr, n);
261 found->call_list = arr;
262 } else { /* New node, add Call node and init nesting. */
263 found = (cg_callee_entry *)obstack_alloc(irg->obst, sizeof(*found));
265 found->call_list = NEW_ARR_F(ir_node *, 1);
266 found->call_list[0] = n;
267 found->max_depth = 0;
268 pset_insert((pset *)irg->callees, found, HASH_PTR(callee));
270 depth = get_loop_depth(get_irn_loop(get_nodes_block(n)));
271 found->max_depth = (depth > found->max_depth) ? depth : found->max_depth;
276 /** compare two ir graphs in a cg_callee_entry */
277 static int cg_callee_entry_cmp(const void *elt, const void *key) {
278 const cg_callee_entry *e1 = elt;
279 const cg_callee_entry *e2 = key;
280 return e1->irg != e2->irg;
283 /** compare two ir graphs */
284 static int graph_cmp(const void *elt, const void *key) {
285 const ir_graph *e1 = elt;
286 const ir_graph *e2 = key;
291 /* Construct and destruct the callgraph. */
292 void compute_callgraph(void) {
295 assert(! get_interprocedural_view()); /* Else walking will not reach the Call nodes. */
300 n_irgs = get_irp_n_irgs();
301 for (i = 0; i < n_irgs; ++i) {
302 ir_graph *irg = get_irp_irg(i);
303 assert(get_irg_callee_info_state(irg) == irg_callee_info_consistent);
304 irg->callees = (cg_callee_entry **)new_pset(cg_callee_entry_cmp, 8);
305 irg->callers = (ir_graph **)new_pset(graph_cmp, 8);
306 //construct_cf_backedges(irg);
309 /* Compute the call graph */
310 for (i = 0; i < n_irgs; ++i) {
311 ir_graph *irg = get_irp_irg(i);
312 construct_cf_backedges(irg); // We also find the maximal loop depth of a call.
313 irg_walk_graph(irg, ana_Call, NULL, NULL);
316 /* Change the sets to arrays. */
317 for (i = 0; i < n_irgs; ++i) {
319 cg_callee_entry *callee;
320 ir_graph *c, *irg = get_irp_irg(i);
321 pset *callee_set, *caller_set;
323 callee_set = (pset *)irg->callees;
324 count = pset_count(callee_set);
325 irg->callees = NEW_ARR_F(cg_callee_entry *, count);
326 irg->callee_isbe = NULL;
327 callee = pset_first(callee_set);
328 for (j = 0; j < count; ++j) {
329 irg->callees[j] = callee;
330 callee = pset_next(callee_set);
332 del_pset(callee_set);
333 assert(callee == NULL);
335 caller_set = (pset *)irg->callers;
336 count = pset_count(caller_set);
337 irg->callers = NEW_ARR_F(ir_graph *, count);
338 irg->caller_isbe = NULL;
339 c = pset_first(caller_set);
340 for (j = 0; j < count; ++j) {
342 c = pset_next(caller_set);
344 del_pset(caller_set);
347 set_irp_callgraph_state(irp_callgraph_consistent);
350 /* Destruct the callgraph. */
351 void free_callgraph(void) {
352 int i, n_irgs = get_irp_n_irgs();
353 for (i = 0; i < n_irgs; ++i) {
354 ir_graph *irg = get_irp_irg(i);
355 if (irg->callees) DEL_ARR_F(irg->callees);
356 if (irg->callers) DEL_ARR_F(irg->callers);
357 if (irg->callee_isbe) free(irg->callee_isbe);
358 if (irg->caller_isbe) free(irg->caller_isbe);
361 irg->callee_isbe = NULL;
362 irg->caller_isbe = NULL;
364 set_irp_callgraph_state(irp_callgraph_none);
367 /* ----------------------------------------------------------------------------------- */
368 /* A walker for the callgraph */
369 /* ----------------------------------------------------------------------------------- */
372 static void do_walk(ir_graph *irg, callgraph_walk_func *pre, callgraph_walk_func *post, void *env) {
375 if (cg_irg_visited(irg)) return;
376 mark_cg_irg_visited(irg);
381 n_callees = get_irg_n_callees(irg);
382 for (i = 0; i < n_callees; i++) {
383 ir_graph *m = get_irg_callee(irg, i);
384 do_walk(m, pre, post, env);
391 void callgraph_walk(callgraph_walk_func *pre, callgraph_walk_func *post, void *env) {
392 int i, n_irgs = get_irp_n_irgs();
395 do_walk(get_irp_main_irg(), pre, post, env);
396 for (i = 0; i < n_irgs; i++) {
397 ir_graph *irg = get_irp_irg(i);
398 if (!cg_irg_visited(irg) && get_irg_n_callers(irg) == 0)
399 do_walk(irg, pre, post, env);
401 for (i = 0; i < n_irgs; i++) {
402 ir_graph *irg = get_irp_irg(i);
403 if (!cg_irg_visited(irg))
404 do_walk(irg, pre, post, env);
408 /* ----------------------------------------------------------------------------------- */
409 /* loop construction algorithm */
410 /* ----------------------------------------------------------------------------------- */
412 static ir_graph *outermost_ir_graph; /**< The outermost graph the scc is computed
414 static ir_loop *current_loop; /**< Current cfloop construction is working
416 static int loop_node_cnt = 0; /**< Counts the number of allocated cfloop nodes.
417 Each cfloop node gets a unique number.
418 What for? ev. remove. @@@ */
419 #ifdef INTERPROCEDURAL_VIEW
420 static int current_dfn = 1; /**< Counter to generate depth first numbering
425 /*-----------------*/
426 /* Node attributes */
427 /*-----------------*/
429 typedef struct scc_info {
430 int in_stack; /**< Marks whether node is on the stack. */
431 int dfn; /**< Depth first search number. */
432 int uplink; /**< dfn number of ancestor. */
437 * allocates a new scc_info of the obstack
439 static INLINE scc_info *new_scc_info(void) {
440 scc_info *info = obstack_alloc (outermost_ir_graph->obst, sizeof(*info));
441 memset(info, 0, sizeof(*info));
446 * Returns non-zero if a graph was already visited.
449 cg_irg_visited(ir_graph *irg) {
450 scc_info *info = get_irg_link(irg);
451 assert(info && "missing call to init_scc");
452 return (info->visited >= master_cg_visited);
456 * Marks a graph as visited.
459 mark_cg_irg_visited(ir_graph *irg) {
460 scc_info *info = get_irg_link(irg);
461 assert(info && "missing call to init_scc");
462 info->visited = master_cg_visited;
466 * Set a graphs visited flag to i.
469 set_cg_irg_visited(ir_graph *irg, int i) {
470 scc_info *info = get_irg_link(irg);
471 assert(info && "missing call to init_scc");
476 * Returns the visited flag of a graph.
479 get_cg_irg_visited(ir_graph *irg) {
480 scc_info *info = get_irg_link(irg);
481 assert(info && "missing call to init_scc");
482 return info->visited;
486 mark_irg_in_stack(ir_graph *irg) {
487 scc_info *info = get_irg_link(irg);
488 assert(info && "missing call to init_scc");
493 mark_irg_not_in_stack(ir_graph *irg) {
494 scc_info *info = get_irg_link(irg);
495 assert(info && "missing call to init_scc");
500 irg_is_in_stack(ir_graph *irg) {
501 scc_info *info = get_irg_link(irg);
502 assert(info && "missing call to init_scc");
503 return info->in_stack;
507 set_irg_uplink(ir_graph *irg, int uplink) {
508 scc_info *info = get_irg_link(irg);
509 assert(info && "missing call to init_scc");
510 info->uplink = uplink;
514 get_irg_uplink(ir_graph *irg) {
515 scc_info *info = get_irg_link(irg);
516 assert(info && "missing call to init_scc");
521 set_irg_dfn(ir_graph *irg, int dfn) {
522 scc_info *info = get_irg_link(irg);
523 assert(info && "missing call to init_scc");
528 get_irg_dfn(ir_graph *irg) {
529 scc_info *info = get_irg_link(irg);
530 assert(info && "missing call to init_scc");
534 /**********************************************************************/
536 /**********************************************************************/
538 static ir_graph **stack = NULL;
539 static int tos = 0; /**< top of stack */
542 * Initialize the irg stack.
544 static INLINE void init_stack(void) {
546 ARR_RESIZE (ir_graph *, stack, 1000);
548 stack = NEW_ARR_F (ir_graph *, 1000);
554 * push a graph on the irg stack
555 * @param n the graph to be pushed
557 static INLINE void push(ir_graph *irg) {
558 if (tos == ARR_LEN (stack)) {
559 int nlen = ARR_LEN (stack) * 2;
560 ARR_RESIZE (ir_node *, stack, nlen);
563 mark_irg_in_stack(irg);
567 * return the topmost graph on the stack and pop it
569 static INLINE ir_graph *pop(void) {
570 ir_graph *irg = stack[--tos];
571 mark_irg_not_in_stack(irg);
576 * The nodes up to irg belong to the current loop.
577 * Removes them from the stack and adds them to the current loop.
579 static INLINE void pop_scc_to_loop(ir_graph *irg) {
585 set_irg_dfn(m, loop_node_cnt);
586 add_loop_node(current_loop, (ir_node *)m);
588 //m->callgraph_loop_depth = current_loop->depth;
592 #ifdef INTERPROCEDURAL_VIEW
593 /* GL ??? my last son is my grandson??? Removes cfloops with no
594 ir_nodes in them. Such loops have only another loop as son. (Why
595 can't they have two loops as sons? Does it never get that far? ) */
596 static void close_loop(ir_loop *l) {
597 int last = get_loop_n_elements(l) - 1;
598 loop_element lelement = get_loop_element(l, last);
599 ir_loop *last_son = lelement.son;
601 if (get_kind(last_son) == k_ir_loop &&
602 get_loop_n_elements(last_son) == 1) {
605 lelement = get_loop_element(last_son, 0);
607 if(get_kind(gson) == k_ir_loop) {
608 loop_element new_last_son;
610 gson -> outer_loop = l;
611 new_last_son.son = gson;
612 l -> children[last] = new_last_son;
621 * Removes and unmarks all nodes up to n from the stack.
622 * The nodes must be visited once more to assign them to a scc.
624 static INLINE void pop_scc_unmark_visit(ir_graph *n) {
629 set_cg_irg_visited(m, 0);
633 /**********************************************************************/
634 /* The loop data structure. **/
635 /**********************************************************************/
637 #ifdef INTERPROCEDURAL_VIEW
639 * Allocates a new loop as son of current_loop. Sets current_loop
640 * to the new loop and returns the father.
642 static ir_loop *new_loop(void) {
643 ir_loop *father, *son;
645 father = current_loop;
647 son = obstack_alloc(outermost_ir_graph->obst, sizeof(*son));
648 memset(son, 0, sizeof(*son));
649 son->kind = k_ir_loop;
650 son->children = NEW_ARR_F (loop_element, 0);
655 son->outer_loop = father;
656 add_loop_son(father, son);
657 son->depth = father->depth + 1;
658 } else { /* The root loop */
659 son->outer_loop = son;
664 son->loop_nr = get_irp_new_node_nr();
671 /**********************************************************************/
672 /* Constructing and destructing the loop/backedge information. **/
673 /**********************************************************************/
675 /* Initialization steps. **********************************************/
686 n_irgs = get_irp_n_irgs();
687 for (i = 0; i < n_irgs; ++i) {
688 ir_graph *irg = get_irp_irg(i);
689 set_irg_link(irg, new_scc_info());
690 irg->callgraph_recursion_depth = 0;
691 irg->callgraph_loop_depth = 0;
695 /** Returns non-zero if n is a loop header, i.e., it is a Block node
696 * and has predecessors within the cfloop and out of the cfloop.
698 * @param root: only needed for assertion.
701 is_head(ir_graph *n, ir_graph *root)
704 int some_outof_loop = 0, some_in_loop = 0;
706 arity = get_irg_n_callees(n);
707 for (i = 0; i < arity; i++) {
708 ir_graph *pred = get_irg_callee(n, i);
709 if (is_irg_callee_backedge(n, i)) continue;
710 if (!irg_is_in_stack(pred)) {
713 if (get_irg_uplink(pred) < get_irg_uplink(root)) {
714 assert(get_irg_uplink(pred) >= get_irg_uplink(root));
720 return some_outof_loop & some_in_loop;
724 * Returns non-zero if n is possible loop head of an endless loop.
725 * I.e., it is a Block, Phi or Filter node and has only predecessors
727 * @arg root: only needed for assertion.
730 is_endless_head(ir_graph *n, ir_graph *root)
733 int some_outof_loop = 0, some_in_loop = 0;
735 arity = get_irg_n_callees(n);
736 for (i = 0; i < arity; i++) {
737 ir_graph *pred = get_irg_callee(n, i);
739 if (is_irg_callee_backedge(n, i)) { continue; }
740 if (!irg_is_in_stack(pred)) {
743 if(get_irg_uplink(pred) < get_irg_uplink(root)) {
744 assert(get_irg_uplink(pred) >= get_irg_uplink(root));
750 return !some_outof_loop & some_in_loop;
754 * Check whether there is a parallel edge in the ip control flow.
758 is_ip_head(ir_graph *n, ir_graph *pred)
761 int iv_rem = get_interprocedural_view();
762 set_interprocedural_view(1);
764 ir_node *sblock = get_irg_start_block(n);
765 int i, arity = get_Block_n_cfgpreds(sblock);
767 //printf(" edge from "); DDMG(n);
768 //printf(" to pred "); DDMG(pred);
769 //printf(" sblock "); DDMN(sblock);
771 for (i = 0; i < arity; i++) {
772 ir_node *pred_cfop = skip_Proj(get_Block_cfgpred(sblock, i));
773 //printf(" "); DDMN(pred_cfop);
774 if (get_irn_op(pred_cfop) == op_CallBegin) { /* could be Unknown */
775 ir_graph *ip_pred = get_irn_irg(pred_cfop);
776 //printf(" "); DDMG(ip_pred);
777 if ((ip_pred == pred) && is_backedge(sblock, i)) {
778 //printf(" found\n");
784 set_interprocedural_view(iv_rem);
789 * Returns index of the predecessor with the smallest dfn number
790 * greater-equal than limit.
793 smallest_dfn_pred(ir_graph *n, int limit)
795 int i, index = -2, min = -1;
797 int arity = get_irg_n_callees(n);
798 for (i = 0; i < arity; i++) {
799 ir_graph *pred = get_irg_callee(n, i);
800 if (is_irg_callee_backedge(n, i) || !irg_is_in_stack(pred)) continue;
801 if (get_irg_dfn(pred) >= limit && (min == -1 || get_irg_dfn(pred) < min)) {
803 min = get_irg_dfn(pred);
810 /** Returns index of the predecessor with the largest dfn number. */
812 largest_dfn_pred(ir_graph *n)
814 int i, index = -2, max = -1;
816 int arity = get_irg_n_callees(n);
817 for (i = 0; i < arity; i++) {
818 ir_graph *pred = get_irg_callee(n, i);
819 if (is_irg_callee_backedge (n, i) || !irg_is_in_stack(pred)) continue;
820 if (get_irg_dfn(pred) > max) {
822 max = get_irg_dfn(pred);
831 find_tail(ir_graph *n) {
833 int i, res_index = -2;
836 if (!icfg && rm_cyclic_phis && remove_cyclic_phis (n)) return NULL;
838 m = stack[tos-1]; /* tos = top of stack */
839 if (is_head (m, n)) {
840 res_index = smallest_dfn_pred(m, 0);
841 if ((res_index == -2) && /* no smallest dfn pred found. */
845 if (m == n) return NULL; // Is this to catch Phi - self loops?
846 for (i = tos-2; i >= 0; --i) {
849 if (is_head (m, n)) {
850 res_index = smallest_dfn_pred (m, get_irg_dfn(m) + 1);
851 if (res_index == -2) /* no smallest dfn pred found. */
852 res_index = largest_dfn_pred (m);
854 if ((m == n) && (res_index == -2)) {
860 /* We should not walk past our selves on the stack: The upcoming nodes
861 are not in this loop. We assume a loop not reachable from Start. */
870 /* A dead loop not reachable from Start. */
871 for (i = tos-2; i >= 0; --i) {
873 if (is_endless_head (m, n)) {
874 res_index = smallest_dfn_pred (m, get_irg_dfn(m) + 1);
875 if (res_index == -2) /* no smallest dfn pred found. */
876 res_index = largest_dfn_pred (m);
879 if (m == n) { break; } /* It's not an unreachable loop, either. */
881 //assert(0 && "no head found on stack");
885 assert (res_index > -2);
887 set_irg_callee_backedge (m, res_index);
888 return get_irg_callee(m, res_index);
892 find_tail(ir_graph *n) {
894 int i, res_index = -2;
897 ir_graph *in_and_out = NULL;
898 ir_graph *only_in = NULL;
899 ir_graph *ip_in_and_out = NULL;
900 ir_graph *ip_only_in = NULL;
902 //printf("find tail for "); DDMG(n);
904 for (i = tos-1; i >= 0; --i) {
905 ir_graph *pred = (i < tos -1) ? stack[i+1] : n;
908 if (is_head (m, n)) {
909 //printf(" found 1a! "); DDM;
911 if (is_ip_head(pred, m)) {
912 //printf(" found 1b! "); DDM;
915 } else if (!ip_only_in && is_endless_head(m, n)) {
917 //printf(" found 2a! "); DDM;
918 if (is_ip_head(pred, m)) {
919 //printf(" found 2b! "); DDM;
922 } else if (is_ip_head(pred, m)) {
923 //printf(" found 3! "); DDM; This happens for self recursions in the second
924 //assert(0); scc iteration (the one to flip the loop.)
927 if (ip_in_and_out) break; /* That's what we really want. */
929 if (m == n) break; /* Don't walk past n on the stack! */
933 if (!in_and_out && !only_in)
934 /* There is no loop */
938 /* Is there a head in the callgraph without a head in the
940 assert(in_and_out || only_in);
942 m = (ip_in_and_out) ? ip_in_and_out : ip_only_in;
945 m = (in_and_out) ? in_and_out : only_in;
947 //printf("*** head is "); DDMG(m);
949 res_index = smallest_dfn_pred (m, get_irg_dfn(m) + 1);
950 if (res_index == -2) /* no smallest dfn pred found. */
951 res_index = largest_dfn_pred (m);
953 set_irg_callee_backedge (m, res_index);
954 res = get_irg_callee(m, res_index);
955 //printf("*** tail is "); DDMG(res);
960 /*-----------------------------------------------------------*
961 * The core algorithm. *
962 *-----------------------------------------------------------*/
965 static void cgscc(ir_graph *n) {
968 if (cg_irg_visited(n)) return;
969 mark_cg_irg_visited(n);
971 /* Initialize the node */
972 set_irg_dfn(n, current_dfn); /* Depth first number for this node */
973 set_irg_uplink(n, current_dfn); /* ... is default uplink. */
977 arity = get_irg_n_callees(n);
978 for (i = 0; i < arity; i++) {
980 if (is_irg_callee_backedge(n, i)) continue;
981 m = get_irg_callee(n, i);
983 /** This marks the backedge, but does it guarantee a correct loop tree? */
984 //if (m == n) { set_irg_callee_backedge(n, i); continue; }
987 if (irg_is_in_stack(m)) {
988 /* Uplink of m is smaller if n->m is a backedge.
989 Propagate the uplink to mark the cfloop. */
990 if (get_irg_uplink(m) < get_irg_uplink(n))
991 set_irg_uplink(n, get_irg_uplink(m));
995 if (get_irg_dfn(n) == get_irg_uplink(n)) {
996 /* This condition holds for
997 1) the node with the incoming backedge.
998 That is: We found a cfloop!
999 2) Straight line code, because no uplink has been propagated, so the
1000 uplink still is the same as the dfn.
1002 But n might not be a proper cfloop head for the analysis. Proper cfloop
1003 heads are Block and Phi nodes. find_tail searches the stack for
1004 Block's and Phi's and takes those nodes as cfloop heads for the current
1005 cfloop instead and marks the incoming edge as backedge. */
1007 ir_graph *tail = find_tail(n);
1009 /* We have a cfloop, that is no straight line code,
1010 because we found a cfloop head!
1011 Next actions: Open a new cfloop on the cfloop tree and
1012 try to find inner cfloops */
1015 ir_loop *l = new_loop();
1017 /* Remove the cfloop from the stack ... */
1018 pop_scc_unmark_visit (n);
1020 /* The current backedge has been marked, that is temporarily eliminated,
1021 by find tail. Start the scc algorithm
1022 anew on the subgraph thats left (the current cfloop without the backedge)
1023 in order to find more inner cfloops. */
1027 assert (cg_irg_visited(n));
1037 * reset the backedge information for all callers in all irgs
1039 static void reset_isbe(void) {
1040 int i, n_irgs = get_irp_n_irgs();
1042 for (i = 0; i < n_irgs; ++i) {
1043 ir_graph *irg = get_irp_irg(i);
1045 if (irg->caller_isbe)
1046 free(irg->caller_isbe);
1047 irg->caller_isbe = NULL;
1049 if (irg->callee_isbe)
1050 free(irg->callee_isbe);
1051 irg->callee_isbe = NULL;
1059 /* ----------------------------------------------------------------------------------- */
1060 /* Another algorithm to compute recursion nesting depth */
1061 /* Walk the callgraph. For each crossed edge increase the loop depth by the edge */
1062 /* weight. Assign graphs the maximal depth. */
1063 /* ----------------------------------------------------------------------------------- */
1065 static void compute_loop_depth (ir_graph *irg, void *env) {
1066 int current_nesting = *(int *) env;
1067 int old_nesting = irg->callgraph_loop_depth;
1068 int old_visited = get_cg_irg_visited(irg);
1073 if (cg_irg_visited(irg)) return;
1075 mark_cg_irg_visited(irg);
1077 //printf(" old: %d new %d master %d", old_visited, get_cg_irg_visited(irg), master_cg_visited); DDMG(irg);
1080 if (old_nesting < current_nesting)
1081 irg->callgraph_loop_depth = current_nesting;
1083 if (current_nesting > irp->max_callgraph_loop_depth)
1084 irp->max_callgraph_loop_depth = current_nesting;
1086 if ((old_visited +1 < get_cg_irg_visited(irg)) || /* not yet visited */
1087 (old_nesting < current_nesting)) { /* propagate larger nesting */
1088 /* Don't walk the graph, but a tree that is an unfolded graph. */
1089 n_callees = get_irg_n_callees(irg);
1090 for (i = 0; i < n_callees; i++) {
1091 ir_graph *m = get_irg_callee(irg, i);
1092 *(int *)env += get_irg_callee_loop_depth(irg, i);
1093 compute_loop_depth(m, env);
1094 *(int *)env -= get_irg_callee_loop_depth(irg, i);
1098 set_cg_irg_visited(irg, master_cg_visited-1);
1101 /* ------------------------------------------------------------------------------------ */
1102 /* Another algorithm to compute recursion nesting depth */
1103 /* Walk the callgraph. For each crossed loop increase the nesting depth by one. */
1104 /* Assign graphs the maximal nesting depth. Don't increase if passing loops more than */
1106 /* ------------------------------------------------------------------------------------ */
1109 /* For callees, we want to remember the Call nodes, too. */
1110 typedef struct ana_entry2 {
1111 ir_loop **loop_stack; /**< a stack of ir_loop entries */
1112 int tos; /**< the top of stack entry */
1113 int recursion_nesting;
1117 * push a loop entry on the stack
1119 static void push2(ana_entry2 *e, ir_loop *g) {
1120 if (ARR_LEN(e->loop_stack) == e->tos) {
1121 ARR_APP1(ir_loop *, e->loop_stack, g);
1123 e->loop_stack[e->tos] = g;
1129 * returns the top of stack and pop it
1131 static ir_loop *pop2(ana_entry2 *e) {
1132 return e->loop_stack[--e->tos];
1136 * check if a loop g in on the stack. Did not check the TOS.
1138 static int in_stack(ana_entry2 *e, ir_loop *g) {
1140 for (i = e->tos-1; i >= 0; --i) {
1141 if (e->loop_stack[i] == g) return 1;
1146 static void compute_rec_depth (ir_graph *irg, void *env) {
1147 ana_entry2 *e = (ana_entry2 *)env;
1148 ir_loop *l = irg->l;
1149 int depth, old_depth = irg->callgraph_recursion_depth;
1153 if (cg_irg_visited(irg)) return;
1154 mark_cg_irg_visited(irg);
1156 /* -- compute and set the new nesting value -- */
1157 if ((l != irp->outermost_cg_loop) && !in_stack(e, l)) {
1159 e->recursion_nesting++;
1162 depth = e->recursion_nesting;
1164 if (old_depth < depth)
1165 irg->callgraph_recursion_depth = depth;
1167 if (depth > irp->max_callgraph_recursion_depth)
1168 irp->max_callgraph_recursion_depth = depth;
1170 /* -- spread the nesting value -- */
1171 if (depth == 0 || old_depth < depth) {
1172 /* Don't walk the graph, but a tree that is an unfolded graph.
1173 Therefore we unset the visited flag at the end. */
1174 n_callees = get_irg_n_callees(irg);
1175 for (i = 0; i < n_callees; i++) {
1176 ir_graph *m = get_irg_callee(irg, i);
1177 compute_rec_depth(m, env);
1181 /* -- clean up -- */
1184 e->recursion_nesting--;
1186 set_cg_irg_visited(irg, master_cg_visited-1);
1190 /* ----------------------------------------------------------------------------------- */
1191 /* Another algorithm to compute the execution frequency of methods ignoring recursions. */
1192 /* Walk the callgraph. Ignore backedges. Use sum of execution frequencies of Call */
1193 /* nodes to evaluate a callgraph edge. */
1194 /* ----------------------------------------------------------------------------------- */
1196 #ifdef INTERPROCEDURAL_VIEW
1197 /* Returns the method execution frequency of a graph. */
1198 double get_irg_method_execution_frequency (ir_graph *irg) {
1199 return irg->method_execution_frequency;
1203 * Increase the method execution frequency to freq if its current value is
1204 * smaller then this.
1206 static void set_irg_method_execution_frequency(ir_graph *irg, double freq) {
1207 irg->method_execution_frequency = freq;
1209 if (irp->max_method_execution_frequency < freq)
1210 irp->max_method_execution_frequency = freq;
1213 static void compute_method_execution_frequency(ir_graph *irg, void *env) {
1220 if (cg_irg_visited(irg)) return;
1222 /* We need the values of all predecessors (except backedges).
1223 So they must be marked. Else we will reach the node through
1224 one of the unmarked ones. */
1225 n_callers = get_irg_n_callers(irg);
1226 for (i = 0; i < n_callers; i++) {
1227 ir_graph *m = get_irg_caller(irg, i);
1228 if (is_irg_caller_backedge(irg, i)) continue;
1229 if (!cg_irg_visited(m)) {
1233 mark_cg_irg_visited(irg);
1235 /* Compute the new frequency. */
1238 for (i = 0; i < n_callers; i++) {
1239 if (! is_irg_caller_backedge(irg, i)) {
1240 double edge_freq = get_irg_caller_method_execution_frequency(irg, i);
1241 assert(edge_freq >= 0);
1248 /* A starting point: method only called from outside,
1249 or only backedges as predecessors. */
1253 set_irg_method_execution_frequency(irg, freq);
1256 n_callees = get_irg_n_callees(irg);
1257 for (i = 0; i < n_callees; i++) {
1258 compute_method_execution_frequency(get_irg_callee(irg, i), NULL);
1263 /* ----------------------------------------------------------------------------------- */
1264 /* The recursion stuff driver. */
1265 /* ----------------------------------------------------------------------------------- */
1267 /* Compute the backedges that represent recursions. */
1268 void find_callgraph_recursions(void) {
1269 int i, n_irgs = get_irp_n_irgs();
1273 /* -- compute the looptree. -- */
1275 /* The outermost graph. We start here. Then we start at all
1276 functions in irg list that are never called, then at the remaining
1277 unvisited ones. The third step is needed for functions that are not
1278 reachable from the outermost graph, but call themselves in a cycle. */
1279 assert(get_irp_main_irg());
1280 outermost_ir_graph = get_irp_main_irg();
1283 current_loop = NULL;
1284 new_loop(); /* sets current_loop */
1286 master_cg_visited++;
1287 cgscc(outermost_ir_graph);
1288 for (i = 0; i < n_irgs; i++) {
1289 ir_graph *irg = get_irp_irg(i);
1290 if (!cg_irg_visited(irg) && get_irg_n_callers(irg) == 0)
1293 for (i = 0; i < n_irgs; i++) {
1294 ir_graph *irg = get_irp_irg(i);
1295 if (!cg_irg_visited(irg))
1298 irp->outermost_cg_loop = current_loop;
1300 /* -- Reverse the backedge information. -- */
1301 for (i = 0; i < n_irgs; i++) {
1302 ir_graph *irg = get_irp_irg(i);
1303 int j, n_callees = get_irg_n_callees(irg);
1304 for (j = 0; j < n_callees; ++j) {
1305 if (is_irg_callee_backedge(irg, j))
1306 set_irg_caller_backedge(get_irg_callee(irg, j), irg);
1310 irp->callgraph_state = irp_callgraph_and_calltree_consistent;
1313 /* Compute interprocedural performance estimates. */
1314 void compute_performance_estimates(void) {
1315 int i, n_irgs = get_irp_n_irgs();
1316 int current_nesting;
1319 assert(get_irp_exec_freq_state() != exec_freq_none && "execution frequency not calculated");
1321 /* -- compute the loop depth -- */
1322 current_nesting = 0;
1323 irp->max_callgraph_loop_depth = 0;
1324 master_cg_visited += 2;
1325 //printf (" ** starting at "); DDMG(get_irp_main_irg());
1326 compute_loop_depth(get_irp_main_irg(), ¤t_nesting);
1327 for (i = 0; i < n_irgs; i++) {
1328 ir_graph *irg = get_irp_irg(i);
1329 if ((get_cg_irg_visited(irg) < master_cg_visited-1) &&
1330 get_irg_n_callers(irg) == 0) {
1331 compute_loop_depth(irg, ¤t_nesting);
1332 //printf (" ** starting at "); DDMG(irg);
1335 for (i = 0; i < n_irgs; i++) {
1336 ir_graph *irg = get_irp_irg(i);
1337 if (get_cg_irg_visited(irg) < master_cg_visited-1) {
1338 compute_loop_depth(irg, ¤t_nesting);
1339 //printf (" ** starting at "); DDMG(irg);
1344 /* -- compute the recursion depth -- */
1345 e.loop_stack = NEW_ARR_F(ir_loop *, 0);
1347 e.recursion_nesting = 0;
1349 irp->max_callgraph_recursion_depth = 0;
1351 master_cg_visited += 2;
1352 compute_rec_depth(get_irp_main_irg(), &e);
1353 //printf (" ++ starting at "); DDMG(get_irp_main_irg());
1354 for (i = 0; i < n_irgs; i++) {
1355 ir_graph *irg = get_irp_irg(i);
1356 if ((get_cg_irg_visited(irg) < master_cg_visited-1) &&
1357 get_irg_n_callers(irg) == 0) {
1358 compute_rec_depth(irg, &e);
1359 //printf (" ++ starting at "); DDMG(irg);
1362 for (i = 0; i < n_irgs; i++) {
1363 ir_graph *irg = get_irp_irg(i);
1364 if (get_cg_irg_visited(irg) < master_cg_visited-1) {
1365 compute_rec_depth(irg, &e);
1366 //printf (" ++ starting at "); DDMG(irg);
1370 DEL_ARR_F(e.loop_stack);
1372 /* -- compute the execution frequency -- */
1373 irp->max_method_execution_frequency = 0;
1374 master_cg_visited += 2;
1375 assert(get_irg_n_callers(get_irp_main_irg()) == 0);
1376 compute_method_execution_frequency(get_irp_main_irg(), NULL);
1377 for (i = 0; i < n_irgs; i++) {
1378 ir_graph *irg = get_irp_irg(i);
1379 if ((get_cg_irg_visited(irg) < master_cg_visited-1) &&
1380 get_irg_n_callers(irg) == 0) {
1381 compute_method_execution_frequency(irg, NULL);
1384 for (i = 0; i < n_irgs; i++) {
1385 ir_graph *irg = get_irp_irg(i);
1386 if (get_cg_irg_visited(irg) < master_cg_visited-1) {
1387 compute_method_execution_frequency(irg, NULL);
1393 /* Returns the maximal loop depth of all paths from an external visible method to
1395 int get_irg_loop_depth(ir_graph *irg) {
1396 assert(irp->callgraph_state == irp_callgraph_consistent ||
1397 irp->callgraph_state == irp_callgraph_and_calltree_consistent);
1398 return irg->callgraph_loop_depth;
1401 /* Returns the maximal recursion depth of all paths from an external visible method to
1403 int get_irg_recursion_depth(ir_graph *irg) {
1404 assert(irp->callgraph_state == irp_callgraph_and_calltree_consistent);
1405 return irg->callgraph_recursion_depth;
1408 /* Computes the interprocedural loop nesting information. */
1409 void analyse_loop_nesting_depth(void) {
1410 ir_entity **free_methods = NULL;
1413 /* establish preconditions. */
1414 if (get_irp_callee_info_state() != irg_callee_info_consistent) {
1415 cgana(&arr_len, &free_methods);
1418 if (irp_callgraph_consistent != get_irp_callgraph_state()) {
1419 compute_callgraph();
1422 find_callgraph_recursions();
1424 compute_performance_estimates();
1426 set_irp_loop_nesting_depth_state(loop_nesting_depth_consistent);
1430 loop_nesting_depth_state get_irp_loop_nesting_depth_state(void) {
1431 return irp->lnd_state;
1433 void set_irp_loop_nesting_depth_state(loop_nesting_depth_state s) {
1436 void set_irp_loop_nesting_depth_state_inconsistent(void) {
1437 if (irp->lnd_state == loop_nesting_depth_consistent)
1438 irp->lnd_state = loop_nesting_depth_inconsistent;