X-Git-Url: http://nsz.repo.hu/git/?a=blobdiff_plain;f=ir%2Fana%2Fcallgraph.c;h=c7a0137e0e71fb0372940439dd20d3f148f8f73f;hb=4bad1346ff2abc3923beea23e5ac949acc7ca514;hp=5b0a77aa1c74b07630c62efbcbe163699e543fe8;hpb=e9af905ab778ca0572283c69bfa050069115d5d8;p=libfirm diff --git a/ir/ana/callgraph.c b/ir/ana/callgraph.c index 5b0a77aa1..c7a0137e0 100644 --- a/ir/ana/callgraph.c +++ b/ir/ana/callgraph.c @@ -9,8 +9,16 @@ * Copyright: (c) 2004 Universität Karlsruhe * Licence: This file protected by GPL - GNU GENERAL PUBLIC LICENSE. */ - +#ifdef HAVE_CONFIG_H #include "config.h" +#endif + +#ifdef HAVE_STRING_H +#include +#endif + +#include + #include "callgraph.h" #include "irloop_t.h" @@ -18,11 +26,35 @@ #include "irgraph_t.h" #include "irnode_t.h" +#include "cgana.h" +#include "execution_frequency.h" + #include "array.h" #include "pmap.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; +}; + +typedef struct ana_entry ana_entry; + +static int master_cg_visited = 0; +static INLINE int cg_irg_visited (ir_graph *n); +static INLINE void mark_cg_irg_visited(ir_graph *n); +static INLINE void set_cg_irg_visited (ir_graph *n, int i); + +irp_callgraph_state get_irp_callgraph_state(void) { + return irp->callgraph_state; +} +void set_irp_callgraph_state(irp_callgraph_state s) { + irp->callgraph_state = s; +} + /* The functions that call irg. */ int get_irg_n_callers(ir_graph *irg) { if (irg->callers) return ARR_LEN(irg->callers); @@ -37,11 +69,49 @@ int is_irg_caller_backedge(ir_graph *irg, int pos) { assert (pos >= 0 && pos < get_irg_n_callers(irg)); return irg->caller_isbe[pos]; } -static void set_irg_caller_backedge(ir_graph *irg, int pos) { - assert (pos >= 0 && pos < get_irg_n_callers(irg)); - irg->caller_isbe[pos] = 1; + +static void set_irg_caller_backedge(ir_graph *irg, ir_graph *caller) { + int i, n_callers = get_irg_n_callers(irg); + for (i = 0; i < n_callers; ++i) { + if (get_irg_caller(irg, i) == caller) { + irg->caller_isbe[i] = 1; + break; + } + } } +int has_irg_caller_backedge(ir_graph *irg) { + int i, n_callers = get_irg_n_callers(irg); + for (i = 0; i < n_callers; ++i) + if (is_irg_caller_backedge(irg, i)) return 1; + return 0; +} + +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) == callee) { + pos_callee = i; + break; + } + } + + 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); +} + + /* The functions called by irg. */ int get_irg_n_callees(ir_graph *irg) { if (irg->callees) return ARR_LEN(irg->callees); @@ -49,19 +119,67 @@ int get_irg_n_callees(ir_graph *irg) { } ir_graph *get_irg_callee(ir_graph *irg, int pos) { assert (pos >= 0 && pos < get_irg_n_callees(irg)); - if (irg->callees) return irg->callees[pos]; + if (irg->callees) return ((ana_entry *)irg->callees[pos])->irg; return NULL; } int is_irg_callee_backedge(ir_graph *irg, int pos) { assert (pos >= 0 && pos < get_irg_n_callees(irg)); return irg->callee_isbe[pos]; } +int has_irg_callee_backedge(ir_graph *irg) { + int i, n_callees = get_irg_n_callees(irg); + for (i = 0; i < n_callees; ++i) + if (is_irg_callee_backedge(irg, i)) return 1; + return 0; +} void set_irg_callee_backedge(ir_graph *irg, int pos) { assert (pos >= 0 && pos < get_irg_n_callees(irg)); irg->callee_isbe[pos] = 1; } +int get_irg_callee_loop_depth(ir_graph *irg, int pos) { + assert (pos >= 0 && pos < get_irg_n_callees(irg)); + if (irg->callees) return ((ana_entry *)irg->callees[pos])->max_depth; + return -1; +} + + + +double get_irg_callee_execution_freqency(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_freqency(ir_graph *irg, int pos) { + double call_freq = get_irg_callee_execution_freqency(irg, pos); + double meth_freq = get_irg_method_execution_frequency(irg); + return call_freq * meth_freq; +} + + +double get_irg_caller_method_execution_freqency(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_freqency(caller, pos_callee); +} + + + +/* --------------------- Compute the callgraph ------------------------ */ + +/* Hash an address */ +#define HASH_ADDRESS(adr) (((unsigned)(adr)) >> 3) +/** + * Walker called by compute_callgraph() + */ static void ana_Call(ir_node *n, void *env) { int i, n_callees; ir_graph *irg; @@ -72,16 +190,41 @@ static void ana_Call(ir_node *n, void *env) { n_callees = get_Call_n_callees(n); for (i = 0; i < n_callees; ++i) { entity *callee_e = get_Call_callee(n, i); - if (callee_e) { - ir_graph *callee = get_entity_irg(callee_e); - pset_insert((pset *)irg->callees, callee, (unsigned)callee >> 3); - pset_insert((pset *)callee->callers, irg, (unsigned)irg >> 3); + ir_graph *callee = get_entity_irg(callee_e); + + if (callee) { + ana_entry buf = { callee, NULL, 0}; + ana_entry *found; + int depth; + + pset_insert((pset *)callee->callers, irg, (unsigned)irg >> 3); + found = pset_find((pset *)irg->callees, &buf, HASH_ADDRESS(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 = NEW_ARR_F(ir_node *, 1); + found->call_list[0] = n; + found->max_depth = 0; + pset_insert((pset *)irg->callees, found, HASH_ADDRESS(callee)); + } + depth = get_loop_depth(get_irn_loop(get_nodes_block(n))); + found->max_depth = (depth > found->max_depth) ? depth : found->max_depth; } } } +/** compare two ir graphs in a ana_entry */ +static int ana_entry_cmp(const void *elt, const void *key) { + const ana_entry *e1 = elt; + const ana_entry *e2 = key; + return e1->irg != e2->irg; +} -/* compare two ir graphs */ +/** compare two ir graphs */ static int graph_cmp(const void *elt, const void *key) { return elt != key; } @@ -91,20 +234,22 @@ static int graph_cmp(const void *elt, const void *key) { void compute_callgraph(void) { int i, n_irgs = get_irp_n_irgs(); - assert(interprocedural_view == 0); /* Else walking will not reach the Call nodes. */ + assert(! get_interprocedural_view()); /* Else walking will not reach the Call nodes. */ /* initialize */ free_callgraph(); for (i = 0; i < n_irgs; ++i) { ir_graph *irg = get_irp_irg(i); assert(get_irg_callee_info_state(irg) == irg_callee_info_consistent); - irg->callees = (ir_graph **)new_pset(graph_cmp, 8); + irg->callees = (ir_graph **)new_pset(ana_entry_cmp, 8); irg->callers = (ir_graph **)new_pset(graph_cmp, 8); + //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); // We also find the maximal loop depth of a call. irg_walk_graph(irg, ana_Call, NULL, NULL); } @@ -112,11 +257,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; @@ -125,10 +271,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; @@ -137,6 +283,7 @@ void compute_callgraph(void) { del_pset(caller_set); assert(c == NULL); } + set_irp_callgraph_state(irp_callgraph_consistent); } void free_callgraph(void) { @@ -145,28 +292,67 @@ void free_callgraph(void) { ir_graph *irg = get_irp_irg(i); if (irg->callees) DEL_ARR_F(irg->callees); if (irg->callers) DEL_ARR_F(irg->callers); - if (irg->callee_isbe) DEL_ARR_F(irg->callee_isbe); - if (irg->caller_isbe) DEL_ARR_F(irg->caller_isbe); + if (irg->callee_isbe) free(irg->callee_isbe); + if (irg->caller_isbe) free(irg->caller_isbe); irg->callees = NULL; irg->callers = NULL; irg->callee_isbe = NULL; irg->caller_isbe = NULL; } + 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) { + int i, n_callees; + + if (cg_irg_visited(irg)) return; + mark_cg_irg_visited(irg); + + pre(irg, env); + + n_callees = get_irg_n_callees(irg); + for (i = 0; i < n_callees; i++) { + ir_graph *m = get_irg_callee(irg, i); + do_walk(m, pre, post, env); + } + + post(irg, env); } +void callgraph_walk(callgraph_walk_func *pre, callgraph_walk_func *post, void *env) { + int i, n_irgs = get_irp_n_irgs(); + master_cg_visited++; + + do_walk(get_irp_main_irg(), pre, post, env); + for (i = 0; i < n_irgs; i++) { + ir_graph *irg = get_irp_irg(i); + if (!cg_irg_visited(irg) && get_irg_n_callers(irg) == 0) + do_walk(irg, pre, post, env); + } + for (i = 0; i < n_irgs; i++) { + ir_graph *irg = get_irp_irg(i); + if (!cg_irg_visited(irg)) + do_walk(irg, pre, post, env); + } +} /* ----------------------------------------------------------------------------------- */ /* 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. */ @@ -175,73 +361,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. */ + bool 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; + 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 = 1; + 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) { + 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 = true; } 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 = false; } static INLINE bool 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; } /**********************************************************************/ @@ -249,8 +454,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); @@ -260,7 +468,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) { @@ -272,6 +483,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) { @@ -280,21 +494,22 @@ 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) { ir_graph *m; - /*for (;;) {*/ do { m = pop(); loop_node_cnt++; set_irg_dfn(m, loop_node_cnt); add_loop_node(current_loop, (ir_node *)m); - set_irg_loop(m, current_loop); - /* if (m==n) break;*/ + m->l = current_loop; + //m->callgraph_loop_depth = current_loop->depth; } while(m != n); } @@ -325,8 +540,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) { @@ -339,34 +556,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; @@ -380,13 +599,20 @@ static ir_loop *new_loop (void) { /* Initialization steps. **********************************************/ static INLINE void -init_scc (ir_graph *irg) { +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()); + + 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; } } @@ -409,19 +635,22 @@ 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. */ + +/** + * 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 is_endless_head (ir_graph *n, ir_graph *root) { @@ -434,21 +663,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; } -/* Returns index of the predecessor with the smallest dfn number - greater-equal than limit. */ + +/** + * Check whether there is a parallel edge in the ip control flow. + * Only + */ +static bool +is_ip_head (ir_graph *n, ir_graph *pred) +{ + int is_be = 0; + 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); + + //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. + */ static int smallest_dfn_pred (ir_graph *n, int limit) { @@ -467,7 +734,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) { @@ -486,6 +753,7 @@ largest_dfn_pred (ir_graph *n) return index; } +#if 0 static ir_graph * find_tail (ir_graph *n) { ir_graph *m; @@ -498,7 +766,7 @@ find_tail (ir_graph *n) { if (is_head (m, n)) { res_index = smallest_dfn_pred(m, 0); if ((res_index == -2) && /* no smallest dfn pred found. */ - (n == m)) + (n == m)) return NULL; } else { if (m == n) return NULL; // Is this to catch Phi - self loops? @@ -506,21 +774,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; } } @@ -528,14 +796,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"); } @@ -546,7 +814,75 @@ find_tail (ir_graph *n) { set_irg_callee_backedge (m, res_index); return get_irg_callee(m, res_index); } +#else +static ir_graph * +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; + ir_graph *ip_only_in = NULL; + + //printf("find tail for "); DDMG(n); + + for (i = tos-1; i >= 0; --i) { + ir_graph *pred = (i < tos -1) ? stack[i+1] : n; + m = stack[i]; + + if (is_head (m, n)) { + //printf(" found 1a! "); DDM; + in_and_out = m; + if (is_ip_head(pred, 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; + } + } else if (is_ip_head(pred, m)) { + //printf(" found 3! "); DDM; This happens for self recursions in the second + //assert(0); scc iteration (the one to flip the loop.) + } + + if (ip_in_and_out) break; /* That's what we really want. */ + if (m == n) break; /* Don't walk past n on the stack! */ + } + + + if (!in_and_out && !only_in) + /* There is no loop */ + return NULL; + + + /* Is there a head in the callgraph without a head in the + ip cf graph? */ + assert(in_and_out || only_in); + + m = (ip_in_and_out) ? ip_in_and_out : ip_only_in; + + if (!m) + m = (in_and_out) ? in_and_out : only_in; + + //printf("*** head is "); DDMG(m); + + 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); + + set_irg_callee_backedge (m, res_index); + res = get_irg_callee(m, res_index); + //printf("*** tail is "); DDMG(res); + return res; +} +#endif /*-----------------------------------------------------------* @@ -555,7 +891,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); @@ -563,26 +899,24 @@ static void cgscc (ir_graph *n) { /* Initialize the node */ set_irg_dfn(n, current_dfn); /* Depth first number for this node */ set_irg_uplink(n, current_dfn); /* ... is default uplink. */ - set_irg_loop(n, NULL); 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; m = get_irg_callee(n, i); /** This marks the backedge, but does it guarantee a correct loop tree? */ - if (m == n) { set_irg_callee_backedge(n, i); continue; } + //if (m == n) { set_irg_callee_backedge(n, i); continue; } 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)); } } @@ -601,9 +935,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(); @@ -612,9 +946,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); @@ -627,7 +961,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(); @@ -639,6 +975,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; @@ -646,27 +983,228 @@ 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) { + int current_nesting = *(int *) env; + int old_nesting = irg->callgraph_loop_depth; + int old_visited = get_cg_irg_visited(irg); + int i, n_callees; + + //return ; + + if (cg_irg_visited(irg)) return; + + mark_cg_irg_visited(irg); + + //printf(" old: %d new %d master %d", old_visited, get_cg_irg_visited(irg), master_cg_visited); DDMG(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 */ + /* 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); + *(int *)env += get_irg_callee_loop_depth(irg, i); + compute_loop_depth(m, env); + *(int *)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 */ + int tos; /**< the top of stack entry */ + int 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) { + int i; + for (i = e->tos-1; i >= 0; --i) { + 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; + int depth, old_depth = irg->callgraph_recursion_depth; + int i, n_callees; + 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) { + /* 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 recursion nesting depth */ +/* Walk the callgraph. Ignore backedges. Use sum of execution freqencies 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; +} + +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 freqency. */ + 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_freqency(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(); - assert(get_irp_main_irg()); /* The outermost graph. We start here. Then we start at all - external visible functions in irg list, then at the remaining - unvisited ones. */ - outermost_ir_graph = get_irp_main_irg(); - - assert(!interprocedural_view && - "use construct_ip_backedges"); + /* -- compute the looptree. -- */ - init_scc(current_ir_graph); + /* 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. 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(); current_loop = NULL; new_loop(); /* sets current_loop */ + master_cg_visited++; cgscc(outermost_ir_graph); - for (i = 0; i < n_irgs; i++) { ir_graph *irg = get_irp_irg(i); if (!cg_irg_visited(irg) && get_irg_n_callers(irg) == 0) @@ -677,9 +1215,130 @@ void find_callgraph_recursions(void) { if (!cg_irg_visited(irg)) cgscc(irg); } + irp->outermost_cg_loop = current_loop; + + /* -- Reverse the backedge information. -- */ + for (i = 0; i < n_irgs; i++) { + ir_graph *irg = get_irp_irg(i); + int j, n_callees = get_irg_n_callees(irg); + for (j = 0; j < n_callees; ++j) { + if (is_irg_callee_backedge(irg, j)) + set_irg_caller_backedge(get_irg_callee(irg, j), irg); + } + } + + 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 -- */ + current_nesting = 0; + irp->max_callgraph_loop_depth = 0; + master_cg_visited += 2; + //printf (" ** starting at "); DDMG(get_irp_main_irg()); + 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); + //printf (" ** starting at "); DDMG(irg); + } + } + 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); + //printf (" ** starting at "); DDMG(irg); + } + } + + + /* -- 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); + //printf (" ++ starting at "); DDMG(get_irp_main_irg()); + 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); + //printf (" ++ starting at "); DDMG(irg); + } + } + 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); + //printf (" ++ starting at "); DDMG(irg); + } + } + + DEL_ARR_F(e.loop_stack); + + //dump_callgraph("-with_nesting"); + //dump_callgraph_loop_tree(current_loop, "-after_cons"); + + + /* -- 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 + this irg. */ +int get_irg_loop_depth(ir_graph *irg) { + assert(irp->callgraph_state == irp_callgraph_consistent || + irp->callgraph_state == irp_callgraph_and_calltree_consistent); + return irg->callgraph_loop_depth; +} + +/* Maximal recursion depth of all paths from an external visible method to + this irg. */ +int get_irg_recursion_depth(ir_graph *irg) { + assert(irp->callgraph_state == irp_callgraph_and_calltree_consistent); + return irg->callgraph_recursion_depth; +} + +void analyse_loop_nesting_depth(void) { + entity **free_methods = NULL; + int arr_len; + + /* establish preconditions. */ + if (get_irp_callee_info_state() != irg_callee_info_consistent) { + cgana(&arr_len, &free_methods); + } + + if (irp_callgraph_consistent != get_irp_callgraph_state()) { + compute_callgraph(); + } + + find_callgraph_recursions(); - /* We can not use the looptree -- it has no real meaning. - There is a working dumper, but commented out. - assert(current_loop && current_loop == get_loop_outer_loop(current_loop)); - dump_callgraph_loop_tree(current_loop, ""); */ + compute_performance_estimates(); }