2 * This file is part of libFirm.
3 * Copyright (C) 2012 University of Karlsruhe.
8 * @brief Representation and computation of the callgraph.
9 * @author Goetz Lindenmaier
17 #include "callgraph.h"
21 #include "irgraph_t.h"
29 #include "raw_bitset.h"
33 static ir_visited_t master_cg_visited = 0;
34 static inline int cg_irg_visited (ir_graph *n);
35 static inline void mark_cg_irg_visited(ir_graph *n);
37 irp_callgraph_state get_irp_callgraph_state(void)
39 return irp->callgraph_state;
42 void set_irp_callgraph_state(irp_callgraph_state s)
44 irp->callgraph_state = s;
47 size_t get_irg_n_callers(const ir_graph *irg)
50 return irg->callers ? ARR_LEN(irg->callers) : 0;
53 ir_graph *get_irg_caller(const ir_graph *irg, size_t pos)
55 assert(pos < get_irg_n_callers(irg));
56 return irg->callers ? irg->callers[pos] : NULL;
59 int is_irg_caller_backedge(const ir_graph *irg, size_t pos)
61 assert(pos < get_irg_n_callers(irg));
62 return irg->caller_isbe != NULL ? rbitset_is_set(irg->caller_isbe, pos) : 0;
65 /** Search the caller in the list of all callers and set its backedge property. */
66 static void set_irg_caller_backedge(ir_graph *irg, const ir_graph *caller)
68 size_t i, n_callers = get_irg_n_callers(irg);
70 /* allocate a new array on demand */
71 if (irg->caller_isbe == NULL)
72 irg->caller_isbe = rbitset_malloc(n_callers);
73 for (i = 0; i < n_callers; ++i) {
74 if (get_irg_caller(irg, i) == caller) {
75 rbitset_set(irg->caller_isbe, i);
81 int has_irg_caller_backedge(const ir_graph *irg)
83 size_t i, n_callers = get_irg_n_callers(irg);
85 if (irg->caller_isbe != NULL) {
86 for (i = 0; i < n_callers; ++i)
87 if (rbitset_is_set(irg->caller_isbe, i))
94 * Find the reversion position of a caller.
95 * Given the position pos_caller of an caller of irg, return
96 * irg's callee position on that caller.
98 static size_t reverse_pos(const ir_graph *callee, size_t pos_caller)
100 ir_graph *caller = get_irg_caller(callee, pos_caller);
101 /* search the other relation for the corresponding edge. */
102 size_t i, n_callees = get_irg_n_callees(caller);
103 for (i = 0; i < n_callees; ++i) {
104 if (get_irg_callee(caller, i) == callee) {
109 assert(!"reverse_pos() did not find position");
114 size_t get_irg_caller_loop_depth(const ir_graph *irg, size_t pos)
116 ir_graph *caller = get_irg_caller(irg, pos);
117 size_t pos_callee = reverse_pos(irg, pos);
119 return get_irg_callee_loop_depth(caller, pos_callee);
122 size_t get_irg_n_callees(const ir_graph *irg)
124 assert(irg->callees);
125 return irg->callees ? ARR_LEN(irg->callees) : 0;
128 ir_graph *get_irg_callee(const ir_graph *irg, size_t pos)
130 assert(pos < get_irg_n_callees(irg));
131 return irg->callees ? irg->callees[pos]->irg : NULL;
134 int is_irg_callee_backedge(const ir_graph *irg, size_t pos)
136 assert(pos < get_irg_n_callees(irg));
137 return irg->callee_isbe != NULL ? rbitset_is_set(irg->callee_isbe, pos) : 0;
140 int has_irg_callee_backedge(const ir_graph *irg)
142 size_t i, n_callees = get_irg_n_callees(irg);
144 if (irg->callee_isbe != NULL) {
145 for (i = 0; i < n_callees; ++i)
146 if (rbitset_is_set(irg->callee_isbe, i))
153 * Mark the callee at position pos as a backedge.
155 static void set_irg_callee_backedge(ir_graph *irg, size_t pos)
157 size_t n = get_irg_n_callees(irg);
159 /* allocate a new array on demand */
160 if (irg->callee_isbe == NULL)
161 irg->callee_isbe = rbitset_malloc(n);
163 rbitset_set(irg->callee_isbe, pos);
166 size_t get_irg_callee_loop_depth(const ir_graph *irg, size_t pos)
168 assert(pos < get_irg_n_callees(irg));
169 return irg->callees ? irg->callees[pos]->max_depth : 0;
174 * Pre-Walker called by compute_callgraph(), analyses all Call nodes.
176 static void ana_Call(ir_node *n, void *env)
182 if (! is_Call(n)) return;
184 irg = get_irn_irg(n);
185 n_callees = get_Call_n_callees(n);
186 for (i = 0; i < n_callees; ++i) {
187 ir_entity *callee_e = get_Call_callee(n, i);
188 ir_graph *callee = get_entity_irg(callee_e);
192 cg_callee_entry *found;
197 pset_insert((pset *)callee->callers, irg, hash_ptr(irg));
198 found = (cg_callee_entry*) pset_find((pset *)irg->callees, &buf, hash_ptr(callee));
199 if (found) { /* add Call node to list, compute new nesting. */
200 ir_node **arr = found->call_list;
201 ARR_APP1(ir_node *, arr, n);
202 found->call_list = arr;
203 } else { /* New node, add Call node and init nesting. */
204 found = OALLOC(get_irg_obstack(irg), cg_callee_entry);
206 found->call_list = NEW_ARR_F(ir_node *, 1);
207 found->call_list[0] = n;
208 found->max_depth = 0;
209 pset_insert((pset *)irg->callees, found, hash_ptr(callee));
211 depth = get_loop_depth(get_irn_loop(get_nodes_block(n)));
212 found->max_depth = (depth > found->max_depth) ? depth : found->max_depth;
217 /** compare two ir graphs in a cg_callee_entry */
218 static int cg_callee_entry_cmp(const void *elt, const void *key)
220 const cg_callee_entry *e1 = (const cg_callee_entry*) elt;
221 const cg_callee_entry *e2 = (const cg_callee_entry*) key;
222 return e1->irg != e2->irg;
225 /** compare two ir graphs for pointer identity */
226 static int graph_cmp(const void *elt, const void *key)
228 const ir_graph *e1 = (const ir_graph*) elt;
229 const ir_graph *e2 = (const ir_graph*) key;
233 void compute_callgraph(void)
240 n_irgs = get_irp_n_irgs();
241 for (i = 0; i < n_irgs; ++i) {
242 ir_graph *irg = get_irp_irg(i);
243 assert(get_irg_callee_info_state(irg) == irg_callee_info_consistent);
244 irg->callees = (cg_callee_entry **)new_pset(cg_callee_entry_cmp, 8);
245 irg->callers = (ir_graph **)new_pset(graph_cmp, 8);
246 //construct_cf_backedges(irg);
249 /* Compute the call graph */
250 for (i = 0; i < n_irgs; ++i) {
251 ir_graph *irg = get_irp_irg(i);
252 construct_cf_backedges(irg); // We also find the maximal loop depth of a call.
253 irg_walk_graph(irg, ana_Call, NULL, NULL);
256 /* Change the sets to arrays. */
257 for (i = 0; i < n_irgs; ++i) {
259 ir_graph *irg = get_irp_irg(i);
260 pset *callee_set, *caller_set;
262 callee_set = (pset *)irg->callees;
263 count = pset_count(callee_set);
264 irg->callees = NEW_ARR_F(cg_callee_entry *, count);
265 irg->callee_isbe = NULL;
267 foreach_pset(callee_set, cg_callee_entry, callee) {
268 irg->callees[j++] = callee;
270 del_pset(callee_set);
273 caller_set = (pset *)irg->callers;
274 count = pset_count(caller_set);
275 irg->callers = NEW_ARR_F(ir_graph *, count);
276 irg->caller_isbe = NULL;
278 foreach_pset(caller_set, ir_graph, c) {
279 irg->callers[j++] = c;
281 del_pset(caller_set);
284 set_irp_callgraph_state(irp_callgraph_consistent);
287 void free_callgraph(void)
289 size_t i, n_irgs = get_irp_n_irgs();
290 for (i = 0; i < n_irgs; ++i) {
291 ir_graph *irg = get_irp_irg(i);
292 if (irg->callees) DEL_ARR_F(irg->callees);
293 if (irg->callers) DEL_ARR_F(irg->callers);
294 if (irg->callee_isbe) free(irg->callee_isbe);
295 if (irg->caller_isbe) free(irg->caller_isbe);
298 irg->callee_isbe = NULL;
299 irg->caller_isbe = NULL;
301 set_irp_callgraph_state(irp_callgraph_none);
305 static void do_walk(ir_graph *irg, callgraph_walk_func *pre, callgraph_walk_func *post, void *env)
309 if (cg_irg_visited(irg))
311 mark_cg_irg_visited(irg);
316 n_callees = get_irg_n_callees(irg);
317 for (i = 0; i < n_callees; i++) {
318 ir_graph *m = get_irg_callee(irg, i);
319 do_walk(m, pre, post, env);
326 void callgraph_walk(callgraph_walk_func *pre, callgraph_walk_func *post, void *env)
328 size_t i, n_irgs = get_irp_n_irgs();
331 /* roots are methods which have no callers in the current program */
332 for (i = 0; i < n_irgs; ++i) {
333 ir_graph *irg = get_irp_irg(i);
335 if (get_irg_n_callers(irg) == 0)
336 do_walk(irg, pre, post, env);
339 /* in case of unreachable call loops we haven't visited some irgs yet */
340 for (i = 0; i < n_irgs; i++) {
341 ir_graph *irg = get_irp_irg(i);
342 do_walk(irg, pre, post, env);
346 static ir_graph *outermost_ir_graph; /**< The outermost graph the scc is computed
348 static ir_loop *current_loop; /**< Current cfloop construction is working
350 static size_t loop_node_cnt = 0; /**< Counts the number of allocated cfloop nodes.
351 Each cfloop node gets a unique number.
352 What for? ev. remove. @@@ */
353 static size_t current_dfn = 1; /**< Counter to generate depth first numbering
356 typedef struct scc_info {
357 size_t dfn; /**< Depth first search number. */
358 size_t uplink; /**< dfn number of ancestor. */
359 ir_visited_t visited; /**< visited counter */
360 int in_stack; /**< Marks whether node is on the stack. */
364 * allocates a new scc_info on the obstack
366 static inline scc_info *new_scc_info(struct obstack *obst)
368 return OALLOCZ(obst, scc_info);
372 * Returns non-zero if a graph was already visited.
374 static inline int cg_irg_visited(ir_graph *irg)
376 return irg->self_visited >= master_cg_visited;
380 * Marks a graph as visited.
382 static inline void mark_cg_irg_visited(ir_graph *irg)
384 irg->self_visited = master_cg_visited;
388 * Set a graphs visited flag to i.
390 static inline void set_cg_irg_visited(ir_graph *irg, ir_visited_t i)
392 irg->self_visited = i;
396 * Returns the visited flag of a graph.
398 static inline ir_visited_t get_cg_irg_visited(const ir_graph *irg)
400 return irg->self_visited;
403 static inline void mark_irg_in_stack(ir_graph *irg)
405 scc_info *info = (scc_info*) get_irg_link(irg);
406 assert(info && "missing call to init_scc()");
410 static inline void mark_irg_not_in_stack(ir_graph *irg)
412 scc_info *info = (scc_info*) get_irg_link(irg);
413 assert(info && "missing call to init_scc()");
417 static inline int irg_is_in_stack(const ir_graph *irg)
419 scc_info *info = (scc_info*) get_irg_link(irg);
420 assert(info && "missing call to init_scc()");
421 return info->in_stack;
424 static inline void set_irg_uplink(ir_graph *irg, size_t uplink)
426 scc_info *info = (scc_info*) get_irg_link(irg);
427 assert(info && "missing call to init_scc()");
428 info->uplink = uplink;
431 static inline size_t get_irg_uplink(const ir_graph *irg)
433 const scc_info *info = (scc_info*) get_irg_link(irg);
434 assert(info && "missing call to init_scc()");
438 static inline void set_irg_dfn(ir_graph *irg, size_t dfn)
440 scc_info *info = (scc_info*) get_irg_link(irg);
441 assert(info && "missing call to init_scc()");
445 static inline size_t get_irg_dfn(const ir_graph *irg)
447 const scc_info *info = (scc_info*) get_irg_link(irg);
448 assert(info && "missing call to init_scc()");
452 static ir_graph **stack = NULL;
453 static size_t tos = 0; /**< top of stack */
456 * Initialize the irg stack.
458 static inline void init_stack(void)
461 ARR_RESIZE(ir_graph *, stack, 1000);
463 stack = NEW_ARR_F(ir_graph *, 1000);
469 * push a graph on the irg stack
470 * @param n the graph to be pushed
472 static inline void push(ir_graph *irg)
474 if (tos == ARR_LEN(stack)) {
475 size_t nlen = ARR_LEN(stack) * 2;
476 ARR_RESIZE(ir_graph*, stack, nlen);
479 mark_irg_in_stack(irg);
483 * return the topmost graph on the stack and pop it
485 static inline ir_graph *pop(void)
491 mark_irg_not_in_stack(irg);
496 * The nodes up to irg belong to the current loop.
497 * Removes them from the stack and adds them to the current loop.
499 static inline void pop_scc_to_loop(ir_graph *irg)
506 set_irg_dfn(m, loop_node_cnt);
507 add_loop_irg(current_loop, m);
509 //m->callgraph_loop_depth = current_loop->depth;
513 /* GL ??? my last son is my grandson??? Removes cfloops with no
514 ir_nodes in them. Such loops have only another loop as son. (Why
515 can't they have two loops as sons? Does it never get that far? ) */
516 static void close_loop(ir_loop *l)
518 size_t last = get_loop_n_elements(l) - 1;
519 loop_element lelement = get_loop_element(l, last);
520 ir_loop *last_son = lelement.son;
522 if (get_kind(last_son) == k_ir_loop &&
523 get_loop_n_elements(last_son) == 1) {
526 lelement = get_loop_element(last_son, 0);
528 if (get_kind(gson) == k_ir_loop) {
529 loop_element new_last_son;
531 gson->outer_loop = l;
532 new_last_son.son = gson;
533 l->children[last] = new_last_son;
540 * Removes and unmarks all nodes up to n from the stack.
541 * The nodes must be visited once more to assign them to a scc.
543 static inline void pop_scc_unmark_visit(ir_graph *n)
549 set_cg_irg_visited(m, 0);
554 * Allocates a new loop as son of current_loop. Sets current_loop
555 * to the new loop and returns the father.
557 static ir_loop *new_loop(void)
559 ir_loop *father = current_loop;
560 ir_loop *son = alloc_loop(father, get_irg_obstack(outermost_ir_graph));
567 static void init_scc(struct obstack *obst)
575 n_irgs = get_irp_n_irgs();
576 for (i = 0; i < n_irgs; ++i) {
577 ir_graph *irg = get_irp_irg(i);
578 set_irg_link(irg, new_scc_info(obst));
579 irg->callgraph_recursion_depth = 0;
580 irg->callgraph_loop_depth = 0;
584 /** Returns non-zero if n is a loop header, i.e., it is a Block node
585 * and has predecessors within the cfloop and out of the cfloop.
587 * @param root: only needed for assertion.
589 static int is_head(const ir_graph *n, const ir_graph *root)
592 int some_outof_loop = 0, some_in_loop = 0;
594 n_callees = get_irg_n_callees(n);
595 for (i = 0; i < n_callees; ++i) {
596 const ir_graph *pred = get_irg_callee(n, i);
597 if (is_irg_callee_backedge(n, i)) continue;
598 if (!irg_is_in_stack(pred)) {
601 if (get_irg_uplink(pred) < get_irg_uplink(root)) {
602 assert(get_irg_uplink(pred) >= get_irg_uplink(root));
608 return some_outof_loop && some_in_loop;
612 * Returns non-zero if n is possible loop head of an endless loop.
613 * I.e., it is a Block or Phi node and has only predecessors
615 * @arg root: only needed for assertion.
617 static int is_endless_head(const ir_graph *n, const ir_graph *root)
620 int some_outof_loop = 0, some_in_loop = 0;
622 n_calless = get_irg_n_callees(n);
623 for (i = 0; i < n_calless; ++i) {
624 const ir_graph *pred = get_irg_callee(n, i);
626 if (is_irg_callee_backedge(n, i))
628 if (!irg_is_in_stack(pred)) {
631 if (get_irg_uplink(pred) < get_irg_uplink(root)) {
632 assert(get_irg_uplink(pred) >= get_irg_uplink(root));
637 return !some_outof_loop && some_in_loop;
641 * Finds index of the predecessor with the smallest dfn number
642 * greater-equal than limit.
644 static bool smallest_dfn_pred(const ir_graph *n, size_t limit, size_t *result)
646 size_t index = 0, min = 0;
649 size_t i, n_callees = get_irg_n_callees(n);
650 for (i = 0; i < n_callees; ++i) {
651 const ir_graph *pred = get_irg_callee(n, i);
652 if (is_irg_callee_backedge(n, i) || !irg_is_in_stack(pred))
654 if (get_irg_dfn(pred) >= limit && (!found || get_irg_dfn(pred) < min)) {
656 min = get_irg_dfn(pred);
665 /** Finds index of the predecessor with the largest dfn number. */
666 static bool largest_dfn_pred(const ir_graph *n, size_t *result)
668 size_t index = 0, max = 0;
671 size_t i, n_callees = get_irg_n_callees(n);
672 for (i = 0; i < n_callees; ++i) {
673 const ir_graph *pred = get_irg_callee(n, i);
674 if (is_irg_callee_backedge (n, i) || !irg_is_in_stack(pred))
676 /* Note: dfn is always > 0 */
677 if (get_irg_dfn(pred) > max) {
679 max = get_irg_dfn(pred);
688 static ir_graph *find_tail(const ir_graph *n)
695 if (!icfg && rm_cyclic_phis && remove_cyclic_phis (n)) return NULL;
697 m = stack[tos - 1]; /* tos = top of stack */
699 found = smallest_dfn_pred(m, 0, &res_index);
700 if (!found && /* no smallest dfn pred found. */
704 if (m == n) return NULL; // Is this to catch Phi - self loops?
705 for (i = tos - 1; i > 0;) {
709 found = smallest_dfn_pred(m, get_irg_dfn(m) + 1, &res_index);
710 if (! found) /* no smallest dfn pred found. */
711 found = largest_dfn_pred(m, &res_index);
716 /* We should not walk past our selves on the stack: The upcoming nodes
717 are not in this loop. We assume a loop not reachable from Start. */
726 /* A dead loop not reachable from Start. */
727 for (i = tos-1; i > 0;) {
729 if (is_endless_head(m, n)) {
730 found = smallest_dfn_pred(m, get_irg_dfn(m) + 1, &res_index);
731 if (!found) /* no smallest dfn pred found. */
732 found = largest_dfn_pred(m, &res_index);
735 /* It's not an unreachable loop, either. */
739 //assert(0 && "no head found on stack");
745 set_irg_callee_backedge(m, res_index);
746 return get_irg_callee(m, res_index);
749 static void cgscc(ir_graph *n)
753 if (cg_irg_visited(n)) return;
754 mark_cg_irg_visited(n);
756 /* Initialize the node */
757 set_irg_dfn(n, current_dfn); /* Depth first number for this node */
758 set_irg_uplink(n, current_dfn); /* ... is default uplink. */
762 n_callees = get_irg_n_callees(n);
763 for (i = 0; i < n_callees; ++i) {
765 if (is_irg_callee_backedge(n, i)) continue;
766 m = get_irg_callee(n, i);
768 /** This marks the backedge, but does it guarantee a correct loop tree? */
769 //if (m == n) { set_irg_callee_backedge(n, i); continue; }
772 if (irg_is_in_stack(m)) {
773 /* Uplink of m is smaller if n->m is a backedge.
774 Propagate the uplink to mark the cfloop. */
775 if (get_irg_uplink(m) < get_irg_uplink(n))
776 set_irg_uplink(n, get_irg_uplink(m));
780 if (get_irg_dfn(n) == get_irg_uplink(n)) {
781 /* This condition holds for
782 1) the node with the incoming backedge.
783 That is: We found a cfloop!
784 2) Straight line code, because no uplink has been propagated, so the
785 uplink still is the same as the dfn.
787 But n might not be a proper cfloop head for the analysis. Proper cfloop
788 heads are Block and Phi nodes. find_tail searches the stack for
789 Block's and Phi's and takes those nodes as cfloop heads for the current
790 cfloop instead and marks the incoming edge as backedge. */
792 ir_graph *tail = find_tail(n);
794 /* We have a cfloop, that is no straight line code,
795 because we found a cfloop head!
796 Next actions: Open a new cfloop on the cfloop tree and
797 try to find inner cfloops */
800 ir_loop *l = new_loop();
802 /* Remove the cfloop from the stack ... */
803 pop_scc_unmark_visit(n);
805 /* The current backedge has been marked, that is temporarily eliminated,
806 by find tail. Start the scc algorithm
807 anew on the subgraph thats left (the current cfloop without the backedge)
808 in order to find more inner cfloops. */
812 assert(cg_irg_visited(n));
822 * reset the backedge information for all callers in all irgs
824 static void reset_isbe(void)
826 size_t i, n_irgs = get_irp_n_irgs();
828 for (i = 0; i < n_irgs; ++i) {
829 ir_graph *irg = get_irp_irg(i);
831 if (irg->caller_isbe)
832 xfree(irg->caller_isbe);
833 irg->caller_isbe = NULL;
835 if (irg->callee_isbe)
836 xfree(irg->callee_isbe);
837 irg->callee_isbe = NULL;
841 void find_callgraph_recursions(void)
848 /* -- compute the looptree. -- */
850 /* The outermost graph. We start here. Then we start at all
851 functions in irg list that are never called, then at the remaining
852 unvisited ones. The third step is needed for functions that are not
853 reachable from the outermost graph, but call themselves in a cycle. */
854 assert(get_irp_main_irg());
855 outermost_ir_graph = get_irp_main_irg();
860 new_loop(); /* sets current_loop */
863 cgscc(outermost_ir_graph);
864 n_irgs = get_irp_n_irgs();
865 for (i = 0; i < n_irgs; ++i) {
866 ir_graph *irg = get_irp_irg(i);
867 if (!cg_irg_visited(irg) && get_irg_n_callers(irg) == 0)
870 for (i = 0; i < n_irgs; ++i) {
871 ir_graph *irg = get_irp_irg(i);
872 if (!cg_irg_visited(irg))
875 obstack_free(&temp, NULL);
877 irp->outermost_cg_loop = current_loop;
878 mature_loops(current_loop, get_irg_obstack(outermost_ir_graph));
880 /* -- Reverse the backedge information. -- */
881 for (i = 0; i < n_irgs; ++i) {
882 ir_graph *irg = get_irp_irg(i);
883 size_t j, n_callees = get_irg_n_callees(irg);
884 for (j = 0; j < n_callees; ++j) {
885 if (is_irg_callee_backedge(irg, j))
886 set_irg_caller_backedge(get_irg_callee(irg, j), irg);
890 irp->callgraph_state = irp_callgraph_and_calltree_consistent;
893 size_t get_irg_loop_depth(const ir_graph *irg)
895 assert(irp->callgraph_state == irp_callgraph_consistent ||
896 irp->callgraph_state == irp_callgraph_and_calltree_consistent);
897 return irg->callgraph_loop_depth;
900 size_t get_irg_recursion_depth(const ir_graph *irg)
902 assert(irp->callgraph_state == irp_callgraph_and_calltree_consistent);
903 return irg->callgraph_recursion_depth;
906 void analyse_loop_nesting_depth(void)
908 /* establish preconditions. */
909 if (get_irp_callee_info_state() != irg_callee_info_consistent) {
910 ir_entity **free_methods = NULL;
912 cgana(&free_methods);
916 if (irp_callgraph_consistent != get_irp_callgraph_state()) {
920 find_callgraph_recursions();
922 set_irp_loop_nesting_depth_state(loop_nesting_depth_consistent);
925 loop_nesting_depth_state get_irp_loop_nesting_depth_state(void)
927 return irp->lnd_state;
929 void set_irp_loop_nesting_depth_state(loop_nesting_depth_state s)
933 void set_irp_loop_nesting_depth_state_inconsistent(void)
935 if (irp->lnd_state == loop_nesting_depth_consistent)
936 irp->lnd_state = loop_nesting_depth_inconsistent;