X-Git-Url: http://nsz.repo.hu/git/?a=blobdiff_plain;f=ir%2Fana%2Fcallgraph.c;h=3e4df7158d3df08292c63dfb38f426158c3f1047;hb=220d7f081a34a73b9bd480151bd4ff2723043d2c;hp=6b5c6dd1d351b655a4f1f5111a3bfd6e1c734592;hpb=1a3b7d363474ab544c13093a2f0b578718d37c7a;p=libfirm diff --git a/ir/ana/callgraph.c b/ir/ana/callgraph.c index 6b5c6dd1d..3e4df7158 100644 --- a/ir/ana/callgraph.c +++ b/ir/ana/callgraph.c @@ -22,7 +22,6 @@ * @brief Representation and computation of the callgraph. * @author Goetz Lindenmaier * @date 21.7.2004 - * @version $Id$ */ #include "config.h" @@ -37,7 +36,6 @@ #include "irnode_t.h" #include "cgana.h" -#include "execution_frequency.h" #include "array.h" #include "pmap.h" @@ -50,33 +48,28 @@ static ir_visited_t master_cg_visited = 0; static inline int cg_irg_visited (ir_graph *n); static inline void mark_cg_irg_visited(ir_graph *n); -/** Returns the callgraph state of the program representation. */ irp_callgraph_state get_irp_callgraph_state(void) { return irp->callgraph_state; } -/* Sets the callgraph state of the program representation. */ void set_irp_callgraph_state(irp_callgraph_state s) { irp->callgraph_state = s; } -/* Returns the number of procedures that call the given irg. */ size_t get_irg_n_callers(const ir_graph *irg) { assert(irg->callers); return irg->callers ? ARR_LEN(irg->callers) : 0; } -/* Returns the caller at position pos. */ ir_graph *get_irg_caller(const ir_graph *irg, size_t pos) { assert(pos < get_irg_n_callers(irg)); return irg->callers ? irg->callers[pos] : NULL; } -/* Returns non-zero if the caller at position pos is "a backedge", i.e. a recursion. */ int is_irg_caller_backedge(const ir_graph *irg, size_t pos) { assert(pos < get_irg_n_callers(irg)); @@ -99,7 +92,6 @@ static void set_irg_caller_backedge(ir_graph *irg, const ir_graph *caller) } } -/* Returns non-zero if the irg has a backedge caller. */ int has_irg_caller_backedge(const ir_graph *irg) { size_t i, n_callers = get_irg_n_callers(irg); @@ -133,7 +125,6 @@ static size_t reverse_pos(const ir_graph *callee, size_t pos_caller) return 0; } -/* Returns the maximal loop depth of call nodes that call along this edge. */ size_t get_irg_caller_loop_depth(const ir_graph *irg, size_t pos) { ir_graph *caller = get_irg_caller(irg, pos); @@ -142,29 +133,24 @@ size_t get_irg_caller_loop_depth(const ir_graph *irg, size_t pos) return get_irg_callee_loop_depth(caller, pos_callee); } - -/* Returns the number of procedures that are called by the given irg. */ size_t get_irg_n_callees(const ir_graph *irg) { assert(irg->callees); return irg->callees ? ARR_LEN(irg->callees) : 0; } -/* Returns the callee at position pos. */ ir_graph *get_irg_callee(const ir_graph *irg, size_t pos) { assert(pos < get_irg_n_callees(irg)); return irg->callees ? irg->callees[pos]->irg : NULL; } -/* Returns non-zero if the callee at position pos is "a backedge", i.e. a recursion. */ int is_irg_callee_backedge(const ir_graph *irg, size_t pos) { assert(pos < get_irg_n_callees(irg)); return irg->callee_isbe != NULL ? rbitset_is_set(irg->callee_isbe, pos) : 0; } -/* Returns non-zero if the irg has a backedge callee. */ int has_irg_callee_backedge(const ir_graph *irg) { size_t i, n_callees = get_irg_n_callees(irg); @@ -191,44 +177,12 @@ static void set_irg_callee_backedge(ir_graph *irg, size_t pos) rbitset_set(irg->callee_isbe, pos); } -/* Returns the maximal loop depth of call nodes that call along this edge. */ size_t get_irg_callee_loop_depth(const ir_graph *irg, size_t pos) { assert(pos < get_irg_n_callees(irg)); return irg->callees ? irg->callees[pos]->max_depth : 0; } -static double get_irg_callee_execution_frequency(const ir_graph *irg, size_t pos) -{ - ir_node **arr = irg->callees[pos]->call_list; - size_t i, n_Calls = ARR_LEN(arr); - double freq = 0.0; - - for (i = 0; i < n_Calls; ++i) { - freq += get_irn_exec_freq(arr[i]); - } - return freq; -} - -static double get_irg_callee_method_execution_frequency(const ir_graph *irg, - size_t pos) -{ - double call_freq = get_irg_callee_execution_frequency(irg, pos); - double meth_freq = get_irg_method_execution_frequency(irg); - return call_freq * meth_freq; -} - -static double get_irg_caller_method_execution_frequency(const ir_graph *irg, - size_t pos) -{ - ir_graph *caller = get_irg_caller(irg, pos); - size_t pos_callee = reverse_pos(irg, pos); - - return get_irg_callee_method_execution_frequency(caller, pos_callee); -} - - -/* --------------------- Compute the callgraph ------------------------ */ /** * Pre-Walker called by compute_callgraph(), analyses all Call nodes. @@ -254,19 +208,19 @@ static void ana_Call(ir_node *n, void *env) buf.irg = callee; - pset_insert((pset *)callee->callers, irg, HASH_PTR(irg)); - found = (cg_callee_entry*) pset_find((pset *)irg->callees, &buf, HASH_PTR(callee)); + pset_insert((pset *)callee->callers, irg, hash_ptr(irg)); + found = (cg_callee_entry*) pset_find((pset *)irg->callees, &buf, hash_ptr(callee)); if (found) { /* add Call node to list, compute new nesting. */ ir_node **arr = found->call_list; ARR_APP1(ir_node *, arr, n); found->call_list = arr; } else { /* New node, add Call node and init nesting. */ - found = OALLOC(irg->obst, cg_callee_entry); + found = OALLOC(get_irg_obstack(irg), cg_callee_entry); found->irg = callee; found->call_list = NEW_ARR_F(ir_node *, 1); found->call_list[0] = n; found->max_depth = 0; - pset_insert((pset *)irg->callees, found, HASH_PTR(callee)); + pset_insert((pset *)irg->callees, found, hash_ptr(callee)); } depth = get_loop_depth(get_irn_loop(get_nodes_block(n))); found->max_depth = (depth > found->max_depth) ? depth : found->max_depth; @@ -290,8 +244,6 @@ static int graph_cmp(const void *elt, const void *key) return e1 != e2; } - -/* Construct and destruct the callgraph. */ void compute_callgraph(void) { size_t i, n_irgs; @@ -318,38 +270,34 @@ void compute_callgraph(void) /* Change the sets to arrays. */ for (i = 0; i < n_irgs; ++i) { size_t j, count; - cg_callee_entry *callee; - ir_graph *c, *irg = get_irp_irg(i); + ir_graph *irg = get_irp_irg(i); pset *callee_set, *caller_set; callee_set = (pset *)irg->callees; count = pset_count(callee_set); irg->callees = NEW_ARR_F(cg_callee_entry *, count); irg->callee_isbe = NULL; - callee = (cg_callee_entry*) pset_first(callee_set); - for (j = 0; j < count; ++j) { - irg->callees[j] = callee; - callee = (cg_callee_entry*) pset_next(callee_set); + j = 0; + foreach_pset(callee_set, cg_callee_entry, callee) { + irg->callees[j++] = callee; } del_pset(callee_set); - assert(callee == NULL); + assert(j == count); caller_set = (pset *)irg->callers; count = pset_count(caller_set); irg->callers = NEW_ARR_F(ir_graph *, count); irg->caller_isbe = NULL; - c = (ir_graph*) pset_first(caller_set); - for (j = 0; j < count; ++j) { - irg->callers[j] = c; - c = (ir_graph*) pset_next(caller_set); + j = 0; + foreach_pset(caller_set, ir_graph, c) { + irg->callers[j++] = c; } del_pset(caller_set); - assert(c == NULL); + assert(j == count); } set_irp_callgraph_state(irp_callgraph_consistent); } -/* Destruct the callgraph. */ void free_callgraph(void) { size_t i, n_irgs = get_irp_n_irgs(); @@ -367,10 +315,6 @@ void free_callgraph(void) set_irp_callgraph_state(irp_callgraph_none); } -/* ----------------------------------------------------------------------------------- */ -/* A walker for the callgraph */ -/* ----------------------------------------------------------------------------------- */ - static void do_walk(ir_graph *irg, callgraph_walk_func *pre, callgraph_walk_func *post, void *env) { @@ -413,10 +357,6 @@ void callgraph_walk(callgraph_walk_func *pre, callgraph_walk_func *post, void *e } } -/* ----------------------------------------------------------------------------------- */ -/* loop construction algorithm */ -/* ----------------------------------------------------------------------------------- */ - static ir_graph *outermost_ir_graph; /**< The outermost graph the scc is computed for */ static ir_loop *current_loop; /**< Current cfloop construction is working @@ -427,10 +367,6 @@ static size_t loop_node_cnt = 0; /**< Counts the number of allocated cfloop no static size_t current_dfn = 1; /**< Counter to generate depth first numbering of visited nodes. */ -/*-----------------*/ -/* Node attributes */ -/*-----------------*/ - typedef struct scc_info { size_t dfn; /**< Depth first search number. */ size_t uplink; /**< dfn number of ancestor. */ @@ -527,10 +463,6 @@ static inline size_t get_irg_dfn(const ir_graph *irg) return info->dfn; } -/**********************************************************************/ -/* A stack. **/ -/**********************************************************************/ - static ir_graph **stack = NULL; static size_t tos = 0; /**< top of stack */ @@ -632,10 +564,6 @@ static inline void pop_scc_unmark_visit(ir_graph *n) } } -/**********************************************************************/ -/* The loop data structure. **/ -/**********************************************************************/ - /** * Allocates a new loop as son of current_loop. Sets current_loop * to the new loop and returns the father. @@ -643,19 +571,13 @@ static inline void pop_scc_unmark_visit(ir_graph *n) static ir_loop *new_loop(void) { ir_loop *father = current_loop; - ir_loop *son = alloc_loop(father, outermost_ir_graph->obst); + ir_loop *son = alloc_loop(father, get_irg_obstack(outermost_ir_graph)); current_loop = son; return father; } -/**********************************************************************/ -/* Constructing and destructing the loop/backedge information. **/ -/**********************************************************************/ - -/* Initialization steps. **********************************************/ - static void init_scc(struct obstack *obst) { size_t i, n_irgs; @@ -824,7 +746,9 @@ static ir_graph *find_tail(const ir_graph *n) found = largest_dfn_pred(m, &res_index); break; } - if (m == n) { break; } /* It's not an unreachable loop, either. */ + /* It's not an unreachable loop, either. */ + if (m == n) + break; } //assert(0 && "no head found on stack"); } @@ -836,11 +760,6 @@ static ir_graph *find_tail(const ir_graph *n) return get_irg_callee(m, res_index); } -/*-----------------------------------------------------------* - * The core algorithm. * - *-----------------------------------------------------------*/ - - static void cgscc(ir_graph *n) { size_t i, n_callees; @@ -933,222 +852,6 @@ static void reset_isbe(void) } } -/* ----------------------------------------------------------------------------------- */ -/* Another algorithm to compute recursion nesting depth */ -/* Walk the callgraph. For each crossed edge increase the loop depth by the edge */ -/* weight. Assign graphs the maximal depth. */ -/* ----------------------------------------------------------------------------------- */ - -static void compute_loop_depth(ir_graph *irg, void *env) -{ - size_t current_nesting = *(size_t *) env; - size_t old_nesting = irg->callgraph_loop_depth; - ir_visited_t old_visited = get_cg_irg_visited(irg); - - if (cg_irg_visited(irg)) return; - - mark_cg_irg_visited(irg); - - if (old_nesting < current_nesting) - irg->callgraph_loop_depth = current_nesting; - - if (current_nesting > irp->max_callgraph_loop_depth) - irp->max_callgraph_loop_depth = current_nesting; - - if ((old_visited +1 < get_cg_irg_visited(irg)) || /* not yet visited */ - (old_nesting < current_nesting)) { /* propagate larger nesting */ - size_t i, n_callees; - - /* Don't walk the graph, but a tree that is an unfolded graph. */ - n_callees = get_irg_n_callees(irg); - for (i = 0; i < n_callees; ++i) { - ir_graph *m = get_irg_callee(irg, i); - *(size_t *)env += get_irg_callee_loop_depth(irg, i); - compute_loop_depth(m, env); - *(size_t *)env -= get_irg_callee_loop_depth(irg, i); - } - } - - set_cg_irg_visited(irg, master_cg_visited-1); -} - -/* ------------------------------------------------------------------------------------ */ -/* Another algorithm to compute recursion nesting depth */ -/* Walk the callgraph. For each crossed loop increase the nesting depth by one. */ -/* Assign graphs the maximal nesting depth. Don't increase if passing loops more than */ -/* once. */ -/* ------------------------------------------------------------------------------------ */ - - -/* For callees, we want to remember the Call nodes, too. */ -typedef struct ana_entry2 { - ir_loop **loop_stack; /**< a stack of ir_loop entries */ - size_t tos; /**< the top of stack entry */ - size_t recursion_nesting; -} ana_entry2; - -/** - * push a loop entry on the stack - */ -static void push2(ana_entry2 *e, ir_loop *g) -{ - if (ARR_LEN(e->loop_stack) == e->tos) { - ARR_APP1(ir_loop *, e->loop_stack, g); - } else { - e->loop_stack[e->tos] = g; - } - ++e->tos; -} - -/** - * returns the top of stack and pop it - */ -static ir_loop *pop2(ana_entry2 *e) -{ - return e->loop_stack[--e->tos]; -} - -/** - * check if a loop g in on the stack. Did not check the TOS. - */ -static int in_stack(ana_entry2 *e, ir_loop *g) -{ - size_t i; - for (i = e->tos; i != 0;) { - if (e->loop_stack[--i] == g) return 1; - } - return 0; -} - -static void compute_rec_depth(ir_graph *irg, void *env) -{ - ana_entry2 *e = (ana_entry2 *)env; - ir_loop *l = irg->l; - size_t depth, old_depth = irg->callgraph_recursion_depth; - int pushed = 0; - - if (cg_irg_visited(irg)) - return; - mark_cg_irg_visited(irg); - - /* -- compute and set the new nesting value -- */ - if ((l != irp->outermost_cg_loop) && !in_stack(e, l)) { - push2(e, l); - ++e->recursion_nesting; - pushed = 1; - } - depth = e->recursion_nesting; - - if (old_depth < depth) - irg->callgraph_recursion_depth = depth; - - if (depth > irp->max_callgraph_recursion_depth) - irp->max_callgraph_recursion_depth = depth; - - /* -- spread the nesting value -- */ - if (depth == 0 || old_depth < depth) { - size_t i, n_callees; - - /* Don't walk the graph, but a tree that is an unfolded graph. - Therefore we unset the visited flag at the end. */ - n_callees = get_irg_n_callees(irg); - for (i = 0; i < n_callees; ++i) { - ir_graph *m = get_irg_callee(irg, i); - compute_rec_depth(m, env); - } - } - - /* -- clean up -- */ - if (pushed) { - pop2(e); - --e->recursion_nesting; - } - set_cg_irg_visited(irg, master_cg_visited-1); -} - - -/* ----------------------------------------------------------------------------------- */ -/* Another algorithm to compute the execution frequency of methods ignoring recursions. */ -/* Walk the callgraph. Ignore backedges. Use sum of execution frequencies of Call */ -/* nodes to evaluate a callgraph edge. */ -/* ----------------------------------------------------------------------------------- */ - -/* Returns the method execution frequency of a graph. */ -double get_irg_method_execution_frequency(const ir_graph *irg) -{ - return irg->method_execution_frequency; -} - -/** - * Increase the method execution frequency to freq if its current value is - * smaller then this. - */ -static void set_irg_method_execution_frequency(ir_graph *irg, double freq) -{ - irg->method_execution_frequency = freq; - - if (irp->max_method_execution_frequency < freq) - irp->max_method_execution_frequency = freq; -} - -static void compute_method_execution_frequency(ir_graph *irg, void *env) -{ - size_t i, n_callers; - double freq; - int found_edge; - size_t n_callees; - (void) env; - - if (cg_irg_visited(irg)) - return; - - /* We need the values of all predecessors (except backedges). - So they must be marked. Else we will reach the node through - one of the unmarked ones. */ - n_callers = get_irg_n_callers(irg); - for (i = 0; i < n_callers; ++i) { - ir_graph *m = get_irg_caller(irg, i); - if (is_irg_caller_backedge(irg, i)) - continue; - if (!cg_irg_visited(m)) { - return; - } - } - mark_cg_irg_visited(irg); - - /* Compute the new frequency. */ - freq = 0; - found_edge = 0; - for (i = 0; i < n_callers; ++i) { - if (! is_irg_caller_backedge(irg, i)) { - double edge_freq = get_irg_caller_method_execution_frequency(irg, i); - assert(edge_freq >= 0); - freq += edge_freq; - found_edge = 1; - } - } - - if (!found_edge) { - /* A starting point: method only called from outside, - or only backedges as predecessors. */ - freq = 1; - } - - set_irg_method_execution_frequency(irg, freq); - - /* recur */ - n_callees = get_irg_n_callees(irg); - for (i = 0; i < n_callees; ++i) { - compute_method_execution_frequency(get_irg_callee(irg, i), NULL); - } -} - - -/* ----------------------------------------------------------------------------------- */ -/* The recursion stuff driver. */ -/* ----------------------------------------------------------------------------------- */ - -/* Compute the backedges that represent recursions. */ void find_callgraph_recursions(void) { size_t i, n_irgs; @@ -1186,7 +889,7 @@ void find_callgraph_recursions(void) obstack_free(&temp, NULL); irp->outermost_cg_loop = current_loop; - mature_loops(current_loop, outermost_ir_graph->obst); + mature_loops(current_loop, get_irg_obstack(outermost_ir_graph)); /* -- Reverse the backedge information. -- */ for (i = 0; i < n_irgs; ++i) { @@ -1201,82 +904,6 @@ void find_callgraph_recursions(void) irp->callgraph_state = irp_callgraph_and_calltree_consistent; } -/* Compute interprocedural performance estimates. */ -void compute_performance_estimates(void) -{ - size_t i, n_irgs = get_irp_n_irgs(); - size_t current_nesting; - ana_entry2 e; - - assert(get_irp_exec_freq_state() != exec_freq_none && "execution frequency not calculated"); - - /* -- compute the loop depth -- */ - current_nesting = 0; - irp->max_callgraph_loop_depth = 0; - master_cg_visited += 2; - compute_loop_depth(get_irp_main_irg(), ¤t_nesting); - for (i = 0; i < n_irgs; ++i) { - ir_graph *irg = get_irp_irg(i); - if ((get_cg_irg_visited(irg) < master_cg_visited-1) && - get_irg_n_callers(irg) == 0) { - compute_loop_depth(irg, ¤t_nesting); - } - } - for (i = 0; i < n_irgs; ++i) { - ir_graph *irg = get_irp_irg(i); - if (get_cg_irg_visited(irg) < master_cg_visited-1) { - compute_loop_depth(irg, ¤t_nesting); - } - } - - - /* -- compute the recursion depth -- */ - e.loop_stack = NEW_ARR_F(ir_loop *, 0); - e.tos = 0; - e.recursion_nesting = 0; - - irp->max_callgraph_recursion_depth = 0; - - master_cg_visited += 2; - compute_rec_depth(get_irp_main_irg(), &e); - for (i = 0; i < n_irgs; ++i) { - ir_graph *irg = get_irp_irg(i); - if ((get_cg_irg_visited(irg) < master_cg_visited-1) && - get_irg_n_callers(irg) == 0) { - compute_rec_depth(irg, &e); - } - } - for (i = 0; i < n_irgs; ++i) { - ir_graph *irg = get_irp_irg(i); - if (get_cg_irg_visited(irg) < master_cg_visited-1) { - compute_rec_depth(irg, &e); - } - } - - DEL_ARR_F(e.loop_stack); - - /* -- compute the execution frequency -- */ - irp->max_method_execution_frequency = 0; - master_cg_visited += 2; - assert(get_irg_n_callers(get_irp_main_irg()) == 0); - compute_method_execution_frequency(get_irp_main_irg(), NULL); - for (i = 0; i < n_irgs; ++i) { - ir_graph *irg = get_irp_irg(i); - if ((get_cg_irg_visited(irg) < master_cg_visited-1) && - get_irg_n_callers(irg) == 0) { - compute_method_execution_frequency(irg, NULL); - } - } - for (i = 0; i < n_irgs; ++i) { - ir_graph *irg = get_irp_irg(i); - if (get_cg_irg_visited(irg) < master_cg_visited-1) { - compute_method_execution_frequency(irg, NULL); - } - } -} - -/* Returns the maximal loop depth of all paths from an external visible method to - this irg. */ size_t get_irg_loop_depth(const ir_graph *irg) { assert(irp->callgraph_state == irp_callgraph_consistent || @@ -1284,15 +911,12 @@ size_t get_irg_loop_depth(const ir_graph *irg) return irg->callgraph_loop_depth; } -/* Returns the maximal recursion depth of all paths from an external visible method to - this irg. */ size_t get_irg_recursion_depth(const ir_graph *irg) { assert(irp->callgraph_state == irp_callgraph_and_calltree_consistent); return irg->callgraph_recursion_depth; } -/* Computes the interprocedural loop nesting information. */ void analyse_loop_nesting_depth(void) { /* establish preconditions. */ @@ -1309,8 +933,6 @@ void analyse_loop_nesting_depth(void) find_callgraph_recursions(); - compute_performance_estimates(); - set_irp_loop_nesting_depth_state(loop_nesting_depth_consistent); }