X-Git-Url: http://nsz.repo.hu/git/?a=blobdiff_plain;f=ir%2Fana%2Fcallgraph.c;h=a4df9f3fa137ac2cc2adefa86f64f901e0211a12;hb=5ea9d0c93d64963b085ff10cde05f739e1c2606b;hp=ed0b2792a87fe81e3c1cb0d5fca8bfaa7abd689e;hpb=49ad2542b4cc755e005cf7cd0f3fe76240130dba;p=libfirm diff --git a/ir/ana/callgraph.c b/ir/ana/callgraph.c index ed0b2792a..a4df9f3fa 100644 --- a/ir/ana/callgraph.c +++ b/ir/ana/callgraph.c @@ -10,14 +10,15 @@ * Licence: This file protected by GPL - GNU GENERAL PUBLIC LICENSE. */ #ifdef HAVE_CONFIG_H -#include "config.h" +# include "config.h" #endif #ifdef HAVE_STRING_H -#include +# include #endif - +# ifdef HAVE_STDLIB_H #include +#endif #include "callgraph.h" @@ -27,17 +28,19 @@ #include "irnode_t.h" #include "cgana.h" +#include "execution_frequency.h" #include "array.h" #include "pmap.h" +#include "hashptr.h" #include "irgwalk.h" /* For callees, we want to remember the Call nodes, too. */ struct ana_entry { - ir_graph *irg; - ir_node *call_list; - int max_depth; + ir_graph *irg; + ir_node **call_list; + int max_depth; }; typedef struct ana_entry ana_entry; @@ -86,14 +89,13 @@ int has_irg_caller_backedge(ir_graph *irg) { return 0; } -int get_irg_caller_loop_depth(ir_graph *irg, int pos) { - ir_graph *caller = get_irg_caller(irg, pos); - +static int reverse_pos(ir_graph *callee, int pos_caller) { + ir_graph *caller = get_irg_caller(callee, pos_caller); /* search the other relation for the corresponding edge. */ int pos_callee = -1; int i, n_callees = get_irg_n_callees(caller); for (i = 0; i < n_callees; ++i) { - if (get_irg_callee(caller, i) == irg) { + if (get_irg_callee(caller, i) == callee) { pos_callee = i; break; } @@ -101,6 +103,13 @@ int get_irg_caller_loop_depth(ir_graph *irg, int pos) { assert(pos_callee >= 0); + return pos_callee; +} + +int get_irg_caller_loop_depth(ir_graph *irg, int pos) { + ir_graph *caller = get_irg_caller(irg, pos); + int pos_callee = reverse_pos(irg, pos); + return get_irg_callee_loop_depth(caller, pos_callee); } @@ -136,10 +145,36 @@ int get_irg_callee_loop_depth(ir_graph *irg, int pos) { return -1; } -/* --------------------- Compute the callgraph ------------------------ */ -/* Hash an address */ -#define HASH_ADDRESS(adr) (((unsigned)(adr)) >> 3) + +double get_irg_callee_execution_frequency(ir_graph *irg, int pos) { + ir_node **arr = ((ana_entry *)irg->callees[pos])->call_list; + int i, n_Calls = ARR_LEN(arr); + double freq = 0; + + for (i = 0; i < n_Calls; ++i) { + freq += get_irn_exec_freq(arr[i]); + } + return freq; +} + +double get_irg_callee_method_execution_frequency(ir_graph *irg, int 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; +} + + +double get_irg_caller_method_execution_frequency(ir_graph *irg, int pos) { + ir_graph *caller = get_irg_caller(irg, pos); + int pos_callee = reverse_pos(irg, pos); + + return get_irg_callee_method_execution_frequency(caller, pos_callee); +} + + + +/* --------------------- Compute the callgraph ------------------------ */ /** * Walker called by compute_callgraph() @@ -155,19 +190,27 @@ static void ana_Call(ir_node *n, void *env) { for (i = 0; i < n_callees; ++i) { entity *callee_e = get_Call_callee(n, i); ir_graph *callee = get_entity_irg(callee_e); - if (callee) { /* For unknown caller */ - pset_insert((pset *)callee->callers, irg, (unsigned)irg >> 3); + + if (callee) { ana_entry buf = { callee, NULL, 0}; - ana_entry *found = pset_find((pset *)irg->callees, &buf, HASH_ADDRESS(callee)); + ana_entry *found; + int depth; + + pset_insert((pset *)callee->callers, irg, HASH_PTR(irg)); + found = 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 = (ana_entry *) obstack_alloc (irg->obst, sizeof (ana_entry)); found->irg = callee; - found->call_list = NULL; + 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_ADDRESS(callee)); + pset_insert((pset *)irg->callees, found, HASH_PTR(callee)); } - int depth = get_loop_depth(get_irn_loop(get_nodes_block(n))); + depth = get_loop_depth(get_irn_loop(get_nodes_block(n))); found->max_depth = (depth > found->max_depth) ? depth : found->max_depth; } } @@ -199,13 +242,13 @@ void compute_callgraph(void) { assert(get_irg_callee_info_state(irg) == irg_callee_info_consistent); irg->callees = (ir_graph **)new_pset(ana_entry_cmp, 8); irg->callers = (ir_graph **)new_pset(graph_cmp, 8); - construct_cf_backedges(irg); + //construct_cf_backedges(irg); } /* Compute the call graph */ for (i = 0; i < n_irgs; ++i) { ir_graph *irg = get_irp_irg(i); - construct_cf_backedges(irg); + construct_cf_backedges(irg); // We also find the maximal loop depth of a call. irg_walk_graph(irg, ana_Call, NULL, NULL); } @@ -213,11 +256,12 @@ void compute_callgraph(void) { for (i = 0; i < n_irgs; ++i) { int j, count; ir_graph *c, *irg = get_irp_irg(i); + pset *callee_set, *caller_set; - pset *callee_set = (pset *)irg->callees; + callee_set = (pset *)irg->callees; count = pset_count(callee_set); irg->callees = NEW_ARR_F(ir_graph *, count); - irg->callee_isbe = calloc(count, sizeof(int)); + irg->callee_isbe = xcalloc(count, sizeof(irg->callee_isbe[0])); c = pset_first(callee_set); for (j = 0; j < count; ++j) { irg->callees[j] = c; @@ -226,10 +270,10 @@ void compute_callgraph(void) { del_pset(callee_set); assert(c == NULL); - pset *caller_set = (pset *)irg->callers; + caller_set = (pset *)irg->callers; count = pset_count(caller_set); irg->callers = NEW_ARR_F(ir_graph *, count); - irg->caller_isbe = calloc(count, sizeof(int)); + irg->caller_isbe = xcalloc(count, sizeof(irg->caller_isbe[0])); c = pset_first(caller_set); for (j = 0; j < count; ++j) { irg->callers[j] = c; @@ -300,14 +344,14 @@ 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 +static ir_graph *outermost_ir_graph; /**< The outermost graph the scc is computed for */ -static ir_loop *current_loop; /* Current cfloop construction is working +static ir_loop *current_loop; /**< Current cfloop construction is working on. */ -static int loop_node_cnt = 0; /* Counts the number of allocated cfloop nodes. +static int loop_node_cnt = 0; /**< Counts the number of allocated cfloop nodes. Each cfloop node gets a unique number. What for? ev. remove. @@@ */ -static int current_dfn = 1; /* Counter to generate depth first numbering +static int current_dfn = 1; /**< Counter to generate depth first numbering of visited nodes. */ @@ -316,78 +360,92 @@ static int current_dfn = 1; /* Counter to generate depth first numbering /**********************************************************************/ typedef struct scc_info { - bool in_stack; /* Marks whether node is on the stack. */ - int dfn; /* Depth first search number. */ - int uplink; /* dfn number of ancestor. */ + int in_stack; /**< Marks whether node is on the stack. */ + int dfn; /**< Depth first search number. */ + int uplink; /**< dfn number of ancestor. */ int visited; } scc_info; -static INLINE scc_info* new_scc_info(void) { - scc_info *info = obstack_alloc (outermost_ir_graph->obst, sizeof (scc_info)); - memset (info, 0, sizeof (scc_info)); +/** + * allocates a new scc_info of the obstack + */ +static INLINE scc_info *new_scc_info(void) { + scc_info *info = obstack_alloc (outermost_ir_graph->obst, sizeof(*info)); + memset(info, 0, sizeof(*info)); return info; } static INLINE int cg_irg_visited(ir_graph *n) { - return (((scc_info *)n->link)->visited >= master_cg_visited); + scc_info *info = get_irg_link(n); + return (info->visited >= master_cg_visited); } static INLINE void mark_cg_irg_visited(ir_graph *n) { - ((scc_info *)n->link)->visited = master_cg_visited; + scc_info *info = get_irg_link(n); + info->visited = master_cg_visited; } static INLINE void set_cg_irg_visited(ir_graph *n, int i) { - ((scc_info *)n->link)->visited = i; + scc_info *info = get_irg_link(n); + info->visited = i; } static INLINE int get_cg_irg_visited(ir_graph *n) { - return ((scc_info *)n->link)->visited; + scc_info *info = get_irg_link(n); + return info->visited; } static INLINE void mark_irg_in_stack (ir_graph *n) { - assert(get_irg_link(n)); - ((scc_info *)n->link)->in_stack = true; + scc_info *info = get_irg_link(n); + assert(info); + info->in_stack = 1; } static INLINE void mark_irg_not_in_stack (ir_graph *n) { - assert(get_irg_link(n)); - ((scc_info *)n->link)->in_stack = false; + scc_info *info = get_irg_link(n); + assert(info); + info->in_stack = 0; } -static INLINE bool +static INLINE int irg_is_in_stack (ir_graph *n) { - assert(get_irg_link(n)); - return ((scc_info *)n->link)->in_stack; + scc_info *info = get_irg_link(n); + assert(info); + return info->in_stack; } static INLINE void set_irg_uplink (ir_graph *n, int uplink) { - assert(get_irg_link(n)); - ((scc_info *)n->link)->uplink = uplink; + scc_info *info = get_irg_link(n); + assert(info); + info->uplink = uplink; } static INLINE int get_irg_uplink (ir_graph *n) { - assert(get_irg_link(n)); - return ((scc_info *)n->link)->uplink; + scc_info *info = get_irg_link(n); + assert(info); + return info->uplink; } static INLINE void set_irg_dfn (ir_graph *n, int dfn) { - assert(get_irg_link(n)); - ((scc_info *)n->link)->dfn = dfn; + scc_info *info = get_irg_link(n); + assert(info); + info->dfn = dfn; } static INLINE int get_irg_dfn (ir_graph *n) { - assert(get_irg_link(n)); - return ((scc_info *)n->link)->dfn; + scc_info *info = get_irg_link(n); + assert(info); + return info->dfn; } /**********************************************************************/ @@ -395,8 +453,11 @@ get_irg_dfn (ir_graph *n) { /**********************************************************************/ static ir_graph **stack = NULL; -static int tos = 0; /* top of stack */ +static int tos = 0; /**< top of stack */ +/** + * initialize the irg stack + */ static INLINE void init_stack(void) { if (stack) { ARR_RESIZE (ir_graph *, stack, 1000); @@ -406,7 +467,10 @@ static INLINE void init_stack(void) { tos = 0; } - +/** + * push a graph on the irg stack + * @param n the graph to be pushed + */ static INLINE void push (ir_graph *n) { @@ -418,6 +482,9 @@ push (ir_graph *n) mark_irg_in_stack(n); } +/** + * return the topmost graph on the stack and pop it + */ static INLINE ir_graph * pop (void) { @@ -426,8 +493,10 @@ pop (void) return n; } -/* The nodes up to n belong to the current loop. - Removes them from the stack and adds them to the current loop. */ +/** + * The nodes up to n belong to the current loop. + * Removes them from the stack and adds them to the current loop. + */ static INLINE void pop_scc_to_loop (ir_graph *n) { @@ -470,8 +539,10 @@ static void close_loop (ir_loop *l) current_loop = l; } -/* Removes and unmarks all nodes up to n from the stack. - The nodes must be visited once more to assign them to a scc. */ +/** + * Removes and unmarks all nodes up to n from the stack. + * The nodes must be visited once more to assign them to a scc. + */ static INLINE void pop_scc_unmark_visit (ir_graph *n) { @@ -484,34 +555,36 @@ pop_scc_unmark_visit (ir_graph *n) } /**********************************************************************/ -/* The loop datastructure. **/ +/* The loop data structure. **/ /**********************************************************************/ -/* Allocates a new loop as son of current_loop. Sets current_loop - to the new loop and returns the father. */ +/** + * Allocates a new loop as son of current_loop. Sets current_loop + * to the new loop and returns the father. + */ static ir_loop *new_loop (void) { ir_loop *father, *son; father = current_loop; - son = (ir_loop *) obstack_alloc (outermost_ir_graph->obst, sizeof (ir_loop)); - memset (son, 0, sizeof (ir_loop)); - son->kind = k_ir_loop; + son = obstack_alloc (outermost_ir_graph->obst, sizeof(*son)); + memset (son, 0, sizeof(*son)); + son->kind = k_ir_loop; son->children = NEW_ARR_F (loop_element, 0); - son->n_nodes = 0; - son->n_sons = 0; + son->n_nodes = 0; + son->n_sons = 0; if (father) { son->outer_loop = father; add_loop_son(father, son); - son->depth = father->depth+1; + son->depth = father->depth + 1; } else { /* The root loop */ son->outer_loop = son; - son->depth = 0; + son->depth = 0; } #ifdef DEBUG_libfirm son->loop_nr = get_irp_new_node_nr(); - son->link = NULL; + son->link = NULL; #endif current_loop = son; @@ -527,22 +600,27 @@ static ir_loop *new_loop (void) { static INLINE void init_scc (void) { int i; - current_dfn = 1; + int n_irgs; + + current_dfn = 1; loop_node_cnt = 0; init_stack(); - for (i = 0; i < get_irp_n_irgs(); ++i) { - set_irg_link(get_irp_irg(i), new_scc_info()); - get_irp_irg(i)->callgraph_recursion_depth = 0; - get_irp_irg(i)->callgraph_loop_depth = 0; + + n_irgs = get_irp_n_irgs(); + for (i = 0; i < n_irgs; ++i) { + ir_graph *irg = get_irp_irg(i); + set_irg_link(irg, new_scc_info()); + irg->callgraph_recursion_depth = 0; + irg->callgraph_loop_depth = 0; } } -/** Returns true if n is a loop header, i.e., it is a Block node +/** Returns non-zero if n is a loop header, i.e., it is a Block node * and has predecessors within the cfloop and out of the cfloop. * * @param root: only needed for assertion. */ -static bool +static int is_head (ir_graph *n, ir_graph *root) { int i, arity; @@ -556,20 +634,23 @@ is_head (ir_graph *n, ir_graph *root) some_outof_loop = 1; } else { if (get_irg_uplink(pred) < get_irg_uplink(root)) { - DDMG(pred); DDMG(root); - assert(get_irg_uplink(pred) >= get_irg_uplink(root)); + DDMG(pred); DDMG(root); + assert(get_irg_uplink(pred) >= get_irg_uplink(root)); } some_in_loop = 1; } } - return some_outof_loop && some_in_loop; + return some_outof_loop & some_in_loop; } -/* Returns true if n is possible loop head of an endless loop. - I.e., it is a Block, Phi or Filter node and has only predecessors - within the loop. - @arg root: only needed for assertion. */ -static bool + +/** + * Returns non-zero if n is possible loop head of an endless loop. + * I.e., it is a Block, Phi or Filter node and has only predecessors + * within the loop. + * @arg root: only needed for assertion. + */ +static int is_endless_head (ir_graph *n, ir_graph *root) { int i, arity; @@ -581,54 +662,59 @@ is_endless_head (ir_graph *n, ir_graph *root) assert(pred); if (is_irg_callee_backedge(n, i)) { continue; } if (!irg_is_in_stack(pred)) { - some_outof_loop = 1; + some_outof_loop = 1; } else { if(get_irg_uplink(pred) < get_irg_uplink(root)) { - DDMG(pred); DDMG(root); - assert(get_irg_uplink(pred) >= get_irg_uplink(root)); + DDMG(pred); DDMG(root); + assert(get_irg_uplink(pred) >= get_irg_uplink(root)); } some_in_loop = 1; } } - return !some_outof_loop && some_in_loop; + return !some_outof_loop & some_in_loop; } -/* Check whether there is a parallel edge in the ip control flow. - Only */ -static bool +/** + * Check whether there is a parallel edge in the ip control flow. + * Only + */ +static int is_ip_head (ir_graph *n, ir_graph *pred) { - int iv_rem = get_interprocedural_view(); - set_interprocedural_view(true); - ir_node *sblock = get_irg_start_block(n); - int i, arity = get_Block_n_cfgpreds(sblock); int is_be = 0; - - //printf(" edge from "); DDMG(n); - //printf(" to pred "); DDMG(pred); - //printf(" sblock "); DDMN(sblock); - - for (i = 0; i < arity; i++) { - ir_node *pred_cfop = skip_Proj(get_Block_cfgpred(sblock, i)); - //printf(" "); DDMN(pred_cfop); - if (get_irn_op(pred_cfop) == op_CallBegin) { /* could be Unknown */ - ir_graph *ip_pred = get_irn_irg(pred_cfop); - //printf(" "); DDMG(ip_pred); - if ((ip_pred == pred) && is_backedge(sblock, i)) { - //printf(" found\n"); - is_be = 1; + int iv_rem = get_interprocedural_view(); + set_interprocedural_view(1); + { + ir_node *sblock = get_irg_start_block(n); + int i, arity = get_Block_n_cfgpreds(sblock); + + //printf(" edge from "); DDMG(n); + //printf(" to pred "); DDMG(pred); + //printf(" sblock "); DDMN(sblock); + + for (i = 0; i < arity; i++) { + ir_node *pred_cfop = skip_Proj(get_Block_cfgpred(sblock, i)); + //printf(" "); DDMN(pred_cfop); + if (get_irn_op(pred_cfop) == op_CallBegin) { /* could be Unknown */ + ir_graph *ip_pred = get_irn_irg(pred_cfop); + //printf(" "); DDMG(ip_pred); + if ((ip_pred == pred) && is_backedge(sblock, i)) { + //printf(" found\n"); + is_be = 1; + } } } } - set_interprocedural_view(iv_rem); return is_be; } -/* Returns index of the predecessor with the smallest dfn number - greater-equal than limit. */ +/** + * Returns index of the predecessor with the smallest dfn number + * greater-equal than limit. + */ static int smallest_dfn_pred (ir_graph *n, int limit) { @@ -647,7 +733,7 @@ smallest_dfn_pred (ir_graph *n, int limit) return index; } -/* Returns index of the predecessor with the largest dfn number. */ +/** Returns index of the predecessor with the largest dfn number. */ static int largest_dfn_pred (ir_graph *n) { @@ -687,21 +773,21 @@ find_tail (ir_graph *n) { m = stack[i]; if (is_head (m, n)) { - res_index = smallest_dfn_pred (m, get_irg_dfn(m) + 1); - if (res_index == -2) /* no smallest dfn pred found. */ - res_index = largest_dfn_pred (m); - - if ((m == n) && (res_index == -2)) { - i = -1; - } - break; + res_index = smallest_dfn_pred (m, get_irg_dfn(m) + 1); + if (res_index == -2) /* no smallest dfn pred found. */ + res_index = largest_dfn_pred (m); + + if ((m == n) && (res_index == -2)) { + i = -1; + } + break; } /* We should not walk past our selves on the stack: The upcoming nodes are not in this loop. We assume a loop not reachable from Start. */ if (m == n) { - i = -1; - break; + i = -1; + break; } } @@ -709,14 +795,14 @@ find_tail (ir_graph *n) { if (i < 0) { /* A dead loop not reachable from Start. */ for (i = tos-2; i >= 0; --i) { - m = stack[i]; - if (is_endless_head (m, n)) { - res_index = smallest_dfn_pred (m, get_irg_dfn(m) + 1); - if (res_index == -2) /* no smallest dfn pred found. */ - res_index = largest_dfn_pred (m); - break; - } - if (m == n) { break; } /* It's not an unreachable loop, either. */ + m = stack[i]; + if (is_endless_head (m, n)) { + res_index = smallest_dfn_pred (m, get_irg_dfn(m) + 1); + if (res_index == -2) /* no smallest dfn pred found. */ + res_index = largest_dfn_pred (m); + break; + } + if (m == n) { break; } /* It's not an unreachable loop, either. */ } //assert(0 && "no head found on stack"); } @@ -733,6 +819,7 @@ find_tail (ir_graph *n) { ir_graph *m; int i, res_index = -2; + ir_graph *res; ir_graph *in_and_out = NULL; ir_graph *only_in = NULL; ir_graph *ip_in_and_out = NULL; @@ -748,15 +835,15 @@ find_tail (ir_graph *n) { //printf(" found 1a! "); DDM; in_and_out = m; if (is_ip_head(pred, m)) { - //printf(" found 1b! "); DDM; - ip_in_and_out = m; + //printf(" found 1b! "); DDM; + ip_in_and_out = m; } } else if (!ip_only_in && is_endless_head(m, n)) { only_in = m; //printf(" found 2a! "); DDM; if (is_ip_head(pred, m)) { - //printf(" found 2b! "); DDM; - ip_only_in = m; + //printf(" found 2b! "); DDM; + ip_only_in = m; } } else if (is_ip_head(pred, m)) { //printf(" found 3! "); DDM; This happens for self recursions in the second @@ -790,7 +877,7 @@ find_tail (ir_graph *n) { res_index = largest_dfn_pred (m); set_irg_callee_backedge (m, res_index); - ir_graph *res = get_irg_callee(m, res_index); + res = get_irg_callee(m, res_index); //printf("*** tail is "); DDMG(res); return res; } @@ -803,7 +890,7 @@ find_tail (ir_graph *n) { static void cgscc (ir_graph *n) { - int i; + int i, arity; if (cg_irg_visited(n)) return; mark_cg_irg_visited(n); @@ -814,8 +901,7 @@ static void cgscc (ir_graph *n) { current_dfn ++; push(n); - int arity = get_irg_n_callees(n); - + arity = get_irg_n_callees(n); for (i = 0; i < arity; i++) { ir_graph *m; if (is_irg_callee_backedge(n, i)) continue; @@ -827,9 +913,9 @@ static void cgscc (ir_graph *n) { cgscc (m); if (irg_is_in_stack(m)) { /* Uplink of m is smaller if n->m is a backedge. - Propagate the uplink to mark the cfloop. */ + Propagate the uplink to mark the cfloop. */ if (get_irg_uplink(m) < get_irg_uplink(n)) - set_irg_uplink(n, get_irg_uplink(m)); + set_irg_uplink(n, get_irg_uplink(m)); } } @@ -848,9 +934,9 @@ static void cgscc (ir_graph *n) { ir_graph *tail = find_tail(n); if (tail) { /* We have a cfloop, that is no straight line code, - because we found a cfloop head! - Next actions: Open a new cfloop on the cfloop tree and - try to find inner cfloops */ + because we found a cfloop head! + Next actions: Open a new cfloop on the cfloop tree and + try to find inner cfloops */ ir_loop *l = new_loop(); @@ -859,9 +945,9 @@ static void cgscc (ir_graph *n) { pop_scc_unmark_visit (n); /* The current backedge has been marked, that is temporarily eliminated, - by find tail. Start the scc algorithm - anew on the subgraph thats left (the current cfloop without the backedge) - in order to find more inner cfloops. */ + by find tail. Start the scc algorithm + anew on the subgraph thats left (the current cfloop without the backedge) + in order to find more inner cfloops. */ cgscc (tail); @@ -874,7 +960,9 @@ static void cgscc (ir_graph *n) { } - +/** + * reset the backedge information for all callers in all irgs + */ static void reset_isbe(void) { int i, n_irgs = get_irp_n_irgs(); @@ -886,6 +974,7 @@ static void reset_isbe(void) { for (j = 0; j < n_cs; ++j) { irg->caller_isbe[j] = 0; } + n_cs = get_irg_n_callees(irg); for (j = 0; j < n_cs; ++j) { irg->callee_isbe[j] = 0; @@ -902,7 +991,7 @@ static void reset_isbe(void) { /* weight. Assign graphs the maximal depth. */ /* ----------------------------------------------------------------------------------- */ -void compute_loop_depth (ir_graph *irg, void *env) { +static void compute_loop_depth (ir_graph *irg, void *env) { int current_nesting = *(int *) env; int old_nesting = irg->callgraph_loop_depth; int old_visited = get_cg_irg_visited(irg); @@ -938,38 +1027,43 @@ void compute_loop_depth (ir_graph *irg, void *env) { 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 increas if passing loops more than */ +/* ------------------------------------------------------------------------------------ */ +/* 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. */ -struct ana_entry2 { - ir_loop **loop_stack; - int tos; +typedef struct ana_entry2 { + ir_loop **loop_stack; /**< a stack of ir_loop entries */ + int tos; /**< the top of stack entry */ int recursion_nesting; -}; - -typedef struct ana_entry2 ana_entry2; +} 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 ++; + ++e->tos; } +/** + * returns the top of stack and pop it + */ static ir_loop *pop2(ana_entry2 *e) { - e->tos --; - return e->loop_stack[e->tos+1]; + 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) { int i; for (i = e->tos-1; i >= 0; --i) { @@ -978,7 +1072,7 @@ static int in_stack(ana_entry2 *e, ir_loop *g) { return 0; } -void compute_rec_depth (ir_graph *irg, void *env) { +static void compute_rec_depth (ir_graph *irg, void *env) { ana_entry2 *e = (ana_entry2 *)env; ir_loop *l = irg->l; int depth, old_depth = irg->callgraph_recursion_depth; @@ -1004,7 +1098,8 @@ void compute_rec_depth (ir_graph *irg, void *env) { /* -- spread the nesting value -- */ if (depth == 0 || old_depth < depth) { - /* Don't walk the graph, but a tree that is an unfolded graph. */ + /* 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); @@ -1021,17 +1116,88 @@ void compute_rec_depth (ir_graph *irg, void *env) { } +/* ----------------------------------------------------------------------------------- */ +/* 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. */ +/* ----------------------------------------------------------------------------------- */ + +double get_irg_method_execution_frequency (ir_graph *irg) { + return irg->method_execution_frequency; +} + +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) { + int i, n_callers; + double freq; + int found_edge; + int n_callees; + + 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) { int i, n_irgs = get_irp_n_irgs(); reset_isbe(); - /* -- Compute the looptree -- */ + /* -- compute the looptree. -- */ /* The outermost graph. We start here. Then we start at all functions in irg list that are never called, then at the remaining - unvisited ones. */ + unvisited ones. The third step is needed for functions that are not + reachable from the outermost graph, but call themselves in a cycle. */ assert(get_irp_main_irg()); outermost_ir_graph = get_irp_main_irg(); init_scc(); @@ -1063,8 +1229,16 @@ void find_callgraph_recursions(void) { } } + irp->callgraph_state = irp_callgraph_and_calltree_consistent; +} + +void compute_performance_estimates(void) { + int i, n_irgs = get_irp_n_irgs(); + int current_nesting; + ana_entry2 e; + /* -- compute the loop depth -- */ - int current_nesting = 0; + current_nesting = 0; irp->max_callgraph_loop_depth = 0; master_cg_visited += 2; //printf (" ** starting at "); DDMG(get_irp_main_irg()); @@ -1085,11 +1259,12 @@ void find_callgraph_recursions(void) { } } + /* -- compute the recursion depth -- */ - ana_entry2 e; - e.loop_stack = NEW_ARR_F(ir_loop *, 0); - e.tos = 0; + 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; @@ -1113,10 +1288,24 @@ void find_callgraph_recursions(void) { DEL_ARR_F(e.loop_stack); - //dump_callgraph("-with_nesting"); - - //dump_callgraph_loop_tree(current_loop, "-after_cons"); - irp->callgraph_state = irp_callgraph_and_calltree_consistent; + /* -- 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); + } + } } /* Maximal loop depth of all paths from an external visible method to @@ -1148,4 +1337,20 @@ void analyse_loop_nesting_depth(void) { } find_callgraph_recursions(); + + compute_performance_estimates(); + + set_irp_loop_nesting_depth_state(loop_nesting_depth_consistent); +} + + +loop_nesting_depth_state get_irp_loop_nesting_depth_state(void) { + return irp->lnd_state; +} +void set_irp_loop_nesting_depth_state(loop_nesting_depth_state s) { + irp->lnd_state = s; +} +void set_irp_loop_nesting_depth_state_inconsistent(void) { + if (irp->lnd_state == loop_nesting_depth_consistent) + irp->lnd_state = loop_nesting_depth_inconsistent; }