From ce28074968c562c2b3570e01ac8745f519c381f2 Mon Sep 17 00:00:00 2001 From: =?utf8?q?G=C3=B6tz=20Lindenmaier?= Date: Tue, 31 Aug 2004 14:11:31 +0000 Subject: [PATCH] mode loop analyses [r3795] --- ir/ana/callgraph.c | 531 ++++++++++++++++++++++++++++++++++++++++++--- ir/ana/callgraph.h | 69 ++++-- ir/ana/cgana.c | 2 +- ir/ana/ircfscc.c | 80 ++++++- ir/ana/irscc.c | 42 ++-- 5 files changed, 652 insertions(+), 72 deletions(-) diff --git a/ir/ana/callgraph.c b/ir/ana/callgraph.c index 5b0a77aa1..695a8cbff 100644 --- a/ir/ana/callgraph.c +++ b/ir/ana/callgraph.c @@ -23,6 +23,27 @@ #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 +58,43 @@ 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; +} + +int get_irg_caller_loop_depth(ir_graph *irg, int pos) { + ir_graph *caller = get_irg_caller(irg, pos); + + /* 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) { + pos_callee = i; + break; + } + } + + assert(pos_callee >= 0); + + 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,18 +102,32 @@ 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; +} + +/* --------------------- Compute the callgraph ------------------------ */ + static void ana_Call(ir_node *n, void *env) { int i, n_callees; @@ -72,14 +139,32 @@ 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) { + if (callee_e) { /* Null for unknown caller */ 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); + pset_insert((pset *)callee->callers, irg, (unsigned)irg >> 3); + + ana_entry buf = { callee, NULL, 0}; + ana_entry *found = pset_find((pset *)irg->callees, &buf, (unsigned)callee >> 3); + if (found) { /* add Call node to list, compute new nesting. */ + } 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->max_depth = 0; + pset_insert((pset *)irg->callees, found, (unsigned)callee >> 3); + } + int 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 */ +static int ana_entry_cmp(const void *elt, const void *key) { + ana_entry *e1 = (ana_entry *)elt; + ana_entry *e2 = (ana_entry *)key; + return e1->irg != e2->irg; +} /* compare two ir graphs */ static int graph_cmp(const void *elt, const void *key) { @@ -98,13 +183,15 @@ void compute_callgraph(void) { 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); irg_walk_graph(irg, ana_Call, NULL, NULL); } @@ -137,6 +224,7 @@ void compute_callgraph(void) { del_pset(caller_set); assert(c == NULL); } + set_irp_callgraph_state(irp_callgraph_consistent); } void free_callgraph(void) { @@ -152,8 +240,47 @@ void free_callgraph(void) { 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 */ @@ -189,12 +316,12 @@ static INLINE scc_info* new_scc_info(void) { static INLINE int cg_irg_visited(ir_graph *n) { - return ((scc_info *)n->link)->visited; + return (((scc_info *)n->link)->visited >= master_cg_visited); } static INLINE void mark_cg_irg_visited(ir_graph *n) { - ((scc_info *)n->link)->visited = 1; + ((scc_info *)n->link)->visited = master_cg_visited; } static INLINE void @@ -202,6 +329,11 @@ set_cg_irg_visited(ir_graph *n, int i) { ((scc_info *)n->link)->visited = i; } +static INLINE int +get_cg_irg_visited(ir_graph *n) { + return ((scc_info *)n->link)->visited; +} + static INLINE void mark_irg_in_stack (ir_graph *n) { assert(get_irg_link(n)); @@ -287,14 +419,13 @@ 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); } @@ -380,13 +511,16 @@ static ir_loop *new_loop (void) { /* Initialization steps. **********************************************/ static INLINE void -init_scc (ir_graph *irg) { +init_scc (void) { int i; 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; + get_irp_irg(i)->callgraph_weighted_loop_depth = 0; } } @@ -447,6 +581,39 @@ is_endless_head (ir_graph *n, ir_graph *root) return !some_outof_loop && some_in_loop; } + +/* 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 iv_rem = interprocedural_view; + interprocedural_view = 1; + 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; + } + } + } + + interprocedural_view = iv_rem; + return is_be; +} + /* Returns index of the predecessor with the smallest dfn number greater-equal than limit. */ static int @@ -486,6 +653,7 @@ largest_dfn_pred (ir_graph *n) return index; } +#if 0 static ir_graph * find_tail (ir_graph *n) { ir_graph *m; @@ -498,7 +666,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? @@ -546,7 +714,74 @@ 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 *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); + ir_graph *res = get_irg_callee(m, res_index); + //printf("*** tail is "); DDMG(res); + return res; +} +#endif /*-----------------------------------------------------------* @@ -563,7 +798,6 @@ 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); @@ -575,7 +809,7 @@ static void cgscc (ir_graph *n) { 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)) { @@ -646,27 +880,202 @@ static void reset_isbe(void) { } } +static int in_same_loop(ir_graph *irg1, ir_graph *irg2) { + return irg1->l == irg2->l; +} + +/* Returns true if loop depth of low < high and low on + a path from high to tree root. */ +static int in_lower_loop(ir_graph *high, ir_graph *low) { + ir_loop *highl = high->l; + ir_loop *lowl = low->l; + if (get_loop_depth(lowl) < get_loop_depth(highl)) { + while (get_loop_outer_loop(highl) != highl) { + highl = get_loop_outer_loop(highl); + if (highl == lowl) return 1; + } + } + return 0; +} + + +/* compute nesting depth */ +static void cnd(ir_loop *loop) { + int i, n_elems = get_loop_n_elements(loop); + + int same_sum = 0; + int max_lower_edge_max = 0; + + + /* Compute the value for this loop. Deeper loops use this value. */ + for (i = 0; i < n_elems; i++) { + loop_element le = get_loop_element(loop, i); + if (*le.kind == k_ir_graph) { + ir_graph *irg = (ir_graph *)le.node; + int j, n_callers = get_irg_n_callers(irg); + int same_edge_max = 0; + int loop_entry_max = 0; + + for (j = 0; j < n_callers; ++j) { + ir_graph *caller = get_irg_caller(irg, j); + int caller_loop_depth = get_irg_caller_loop_depth(irg, j); + + + if (in_same_loop(irg, caller)) + same_edge_max = (same_edge_max < caller_loop_depth) ? caller_loop_depth + : same_edge_max; + if (in_lower_loop(irg, caller)) { + int loop_entry_this = caller_loop_depth + caller->l->weighted_depth; + loop_entry_max = (loop_entry_max < loop_entry_this) ? loop_entry_this + : loop_entry_max; + } + } + + max_lower_edge_max = (max_lower_edge_max < loop_entry_max) ? max_lower_edge_max + : loop_entry_max; + same_sum += same_edge_max; + } + + /* This loop is as expensive as the most expensive entry edge + the count of the cycle. */ + loop->weighted_depth = max_lower_edge_max + same_sum + 1; /* 1 for the recursion itself */ + } + + /* Recur. */ + for (i = 0; i < n_elems; i++) { + loop_element le = get_loop_element(loop, i); + if (*le.kind == k_ir_loop) + cnd(le.son); + } +} + + +/* ----------------------------------------------------------------------------------- */ +/* 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. */ +/* ----------------------------------------------------------------------------------- */ + +void compute_loop_depth (ir_graph *irg, void *env) { + int current_nesting = *(int *) env; + int i, n_callees; + + if (cg_irg_visited(irg)) return; + mark_cg_irg_visited(irg); + + if (current_nesting == 0 || irg->callgraph_loop_depth < current_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); + } + } + + if (irg->callgraph_loop_depth < current_nesting) + irg->callgraph_loop_depth = current_nesting; + + 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 */ +/* once. */ +/* ----------------------------------------------------------------------------------- */ + + +/* For callees, we want to remember the Call nodes, too. */ +struct ana_entry2 { + ir_loop **loop_stack; + int tos; + int recursion_nesting; +}; + +typedef struct ana_entry2 ana_entry2; + +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 ++; +} + +static ir_loop *pop2(ana_entry2 *e) { + e->tos --; + return e->loop_stack[e->tos+1]; +} + +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; +} + +void compute_rec_depth (ir_graph *irg, void *env) { + ana_entry2 *e = (ana_entry2 *)env; + ir_loop *l = irg->l; + int depth; + int i, n_callees; + int pushed = 0; + + if (cg_irg_visited(irg)) return; + mark_cg_irg_visited(irg); + + if ((l != irp->outermost_cg_loop) && !in_stack(e, l)) { + push2(e, l); + e->recursion_nesting++; + pushed = 1; + } + depth = e->recursion_nesting; + + if (depth == 0 || irg->callgraph_recursion_depth < depth) { + /* 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); + compute_rec_depth(m, env); + } + } + + if (irg->callgraph_recursion_depth < depth) + irg->callgraph_recursion_depth = depth; + + if (pushed) { + pop2(e); + e->recursion_nesting--; + } + set_cg_irg_visited(irg, master_cg_visited-1); +} + + /* 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. */ + 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 +1086,71 @@ 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); + } + } + + /* -- Schleifentiefe berechnen -- */ + int current_nesting = 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 (!cg_irg_visited(irg) && 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); + } + + /* -- Rekursionstiefe berechnen -- */ + ana_entry2 e; + e.loop_stack = NEW_ARR_F(ir_loop *, 0); + e.tos = 0; + e.recursion_nesting = 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 (!cg_irg_visited(irg) && 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); + + //dump_callgraph("-with_nesting"); + + //dump_callgraph_loop_tree(current_loop, "-after_cons"); + irp->callgraph_state = irp_callgraph_and_calltree_consistent; +} + +/* 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; +} - /* 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, ""); */ +/* 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; } diff --git a/ir/ana/callgraph.h b/ir/ana/callgraph.h index 89fd0f1bf..03ed3ab4d 100644 --- a/ir/ana/callgraph.h +++ b/ir/ana/callgraph.h @@ -14,42 +14,77 @@ #define _CALLGRAPH_H_ /** -* @file callgraph.h -* -* This file contains defines the representation of the callgraph. -* The nodes of the call graph are ir_graphs. The edges between -* The nodes are calling relation. I.e., if method a calls method -* b at some point, there is an edge between a and b. -* -* Further this file contains an algorithm to construct the call -* graph. The construction of the callgraph uses the callee -* information in Call nodes to determine which methods are called. -* -* Finally this file contains an algorithm that computes backedges -* in the callgraph, i.e., the algorithm finds possibly recursive calls. -* The algorithm computes an upper bound of all recursive calls. -* -*/ + * @file callgraph.h + * + * This file contains the representation of the callgraph. + * The nodes of the call graph are ir_graphs. The edges between + * ghe nodes are calling relations. I.e., if method a calls method + * b at some point, there is an edge between a and b. + * + * Further this file contains an algorithm to construct the call + * graph. The construction of the callgraph uses the callee + * information in Call nodes to determine which methods are called. + * + * Finally this file contains an algorithm that computes backedges + * in the callgraph, i.e., the algorithm finds possibly recursive calls. + * The algorithm computes an upper bound of all recursive calls. + * + */ #include "irgraph.h" +/** Flag to indicate state of callgraph. */ +typedef enum { + irp_callgraph_none, + irp_callgraph_consistent, /* calltree is inconsistent */ + irp_callgraph_inconsistent, + irp_callgraph_and_calltree_consistent +} irp_callgraph_state; +irp_callgraph_state get_irp_callgraph_state(void); +void set_irp_callgraph_state(irp_callgraph_state s); + /** The functions that call irg. */ int get_irg_n_callers(ir_graph *irg); ir_graph *get_irg_caller(ir_graph *irg, int pos); -/* int is_irg_caller_backedge(ir_graph *irg, int pos); not implemented */ + +int is_irg_caller_backedge(ir_graph *irg, int pos); +int has_irg_caller_backedge(ir_graph *irg); + +/** maximal loop depth of call nodes that call along this edge. */ +int get_irg_caller_loop_depth(ir_graph *irg, int pos); /** The functions called by irg. */ int get_irg_n_callees(ir_graph *irg); ir_graph *get_irg_callee(ir_graph *irg, int pos); + int is_irg_callee_backedge(ir_graph *irg, int pos); +int has_irg_callee_backedge(ir_graph *irg); + +/** maximal loop depth of call nodes that call along this edge. */ +int get_irg_callee_loop_depth(ir_graph *irg, int pos); + +/** Maximal loop depth of all paths from an external visible method to + this irg. */ +int get_irg_loop_depth(ir_graph *irg); +/** Maximal recursion depth of all paths from an external visible method to + this irg. */ +int get_irg_recursion_depth(ir_graph *irg); /** Construct and destruct the callgraph. */ void compute_callgraph(void); void free_callgraph(void); + +/** A function type for fuctions passed to the callgraph walker. */ +typedef void callgraph_walk_func(ir_graph *g, void *env); + +void callgraph_walk(callgraph_walk_func *pre, callgraph_walk_func *post, void *env); + /** Compute the backedges that represent recursions. */ void find_callgraph_recursions(void); + + #endif /* _CALLGRAPH_H_ */ diff --git a/ir/ana/cgana.c b/ir/ana/cgana.c index 9ea174e3b..71e588999 100644 --- a/ir/ana/cgana.c +++ b/ir/ana/cgana.c @@ -568,7 +568,7 @@ static void callee_ana(void) { irg_walk_graph(get_irp_irg(i), callee_walker, remove_Tuples, NULL); set_irg_callee_info_state(get_irp_irg(i), irg_callee_info_consistent); } - //set_irp_callee_info_state(irg_callee_info_consistent); + set_irp_callee_info_state(irg_callee_info_consistent); } diff --git a/ir/ana/ircfscc.c b/ir/ana/ircfscc.c index bc1d7121e..0c9135a28 100644 --- a/ir/ana/ircfscc.c +++ b/ir/ana/ircfscc.c @@ -28,6 +28,8 @@ #include "irprog_t.h" #include "irdump.h" +#define NO_CFLOOPS_WITHOUT_HEAD 1 + static ir_graph *outermost_ir_graph; /* The outermost graph the scc is computed for */ static ir_loop *current_loop; /* Current cfloop construction is working @@ -312,6 +314,39 @@ is_head (ir_node *n, ir_node *root) 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 +is_endless_head (ir_node *n, ir_node *root) +{ + int i, arity; + int some_outof_loop = 0, some_in_loop = 0; + + assert(is_Block(n)); + /* Test for legal loop header: Block, Phi, ... */ + if (!is_outermost_StartBlock(n)) { + arity = get_irn_arity(n); + for (i = 0; i < arity; i++) { + ir_node *pred = get_nodes_block(skip_Proj(get_irn_n(n, i))); + assert(pred); + if (is_backedge(n, i)) { continue; } + if (!irn_is_in_stack(pred)) { + some_outof_loop = 1; //printf(" some out of loop "); + } else { + if(get_irn_uplink(pred) < get_irn_uplink(root)) { + DDMN(pred); DDMN(root); + assert(get_irn_uplink(pred) >= get_irn_uplink(root)); + } + some_in_loop = 1; + } + } + } + return !some_outof_loop && some_in_loop; +} + /* Returns index of the predecessor with the smallest dfn number greater-equal than limit. */ static int @@ -356,8 +391,7 @@ largest_dfn_pred (ir_node *n) /* Searches the stack for possible loop heads. Tests these for backedges. If it finds a head with an unmarked backedge it marks this edge and returns the tail of the loop. - If it finds no backedge returns NULL. - ("disable_backedge" in fiasco) */ + If it finds no backedge returns NULL. */ static ir_node * find_tail (ir_node *n) { ir_node *m; @@ -371,15 +405,46 @@ find_tail (ir_node *n) { return NULL; } else { if (m == n) return NULL; - for (i = tos-2; ; --i) { + for (i = tos-2; i >= 0; --i) { + m = stack[i]; if (is_head (m, n)) { res_index = smallest_dfn_pred (m, get_irn_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; + } + } + + + 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_irn_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"); + } + } assert (res_index > -2); @@ -387,6 +452,11 @@ find_tail (ir_node *n) { return is_outermost_StartBlock(n) ? NULL : get_nodes_block(skip_Proj(get_irn_n(m, res_index))); } +INLINE static int +is_outermost_loop(ir_loop *l) { + return l == get_loop_outer_loop(l); +} + /*-----------------------------------------------------------* * The core algorithm. * *-----------------------------------------------------------*/ @@ -448,8 +518,6 @@ static void cfscc (ir_node *n) { Next actions: Open a new cfloop on the cfloop tree and try to find inner cfloops */ - -#define NO_CFLOOPS_WITHOUT_HEAD 1 #if NO_CFLOOPS_WITHOUT_HEAD /* This is an adaption of the algorithm from fiasco / optscc to @@ -461,7 +529,7 @@ static void cfscc (ir_node *n) { ir_loop *l; int close; - if (get_loop_n_elements(current_loop) > 0) { + if ((get_loop_n_elements(current_loop) > 0) || (is_outermost_loop(current_loop))) { l = new_loop(); close = 1; } else { diff --git a/ir/ana/irscc.c b/ir/ana/irscc.c index dd591015b..b9add05da 100644 --- a/ir/ana/irscc.c +++ b/ir/ana/irscc.c @@ -30,6 +30,11 @@ #include "irdump.h" +/* A variant of the loop tree that avoids loops without head. + This reduces the depth of the loop tree. */ +#define NO_LOOPS_WITHOUT_HEAD 1 + + INLINE void add_loop_son(ir_loop *loop, ir_loop *son); INLINE void add_loop_node(ir_loop *loop, ir_node *n); @@ -788,7 +793,7 @@ find_tail (ir_node *n) { if (res_index == -2) /* no smallest dfn pred found. */ res_index = largest_dfn_pred (m); - if ((m == n) && (res_index == -2)) { + if ((m == n) && (res_index == -2)) { /* dont walk past loop head. */ i = -1; } break; @@ -867,7 +872,8 @@ int search_endproj_in_stack(ir_node *start_block) int arity = get_irn_arity(start_block); for(j = 0; j < arity; j++) { - ir_node *begin_projx = get_Block_cfgpred(get_irg_start_block(get_irn_irg(end_projx)), get_Proj_proj(end_projx)); + ir_node *begin_projx = get_Block_cfgpred(get_irg_start_block(get_irn_irg(end_projx)), + get_Proj_proj(end_projx)); DDMN(begin_projx); if(get_irn_n(start_block, j) == begin_projx) { @@ -884,11 +890,13 @@ int search_endproj_in_stack(ir_node *start_block) static pmap *projx_link = NULL; void link_to_reg_end (ir_node *n, void *env) { - if(get_irn_op(n) == op_Proj && get_irn_mode(n) == mode_X && get_irn_op(get_irn_n(n, 0)) == op_EndReg) - { + if(get_irn_op(n) == op_Proj && + get_irn_mode(n) == mode_X && + get_irn_op(get_irn_n(n, 0)) == op_EndReg) { /* Reg End Projx -> Find the CallBegin Projx and hash it */ ir_node *end_projx = n; - ir_node *begin_projx = get_Block_cfgpred(get_irg_start_block(get_irn_irg(end_projx)), get_Proj_proj(end_projx)); + ir_node *begin_projx = get_Block_cfgpred(get_irg_start_block(get_irn_irg(end_projx)), + get_Proj_proj(end_projx)); printf("Linked the following ProjxNodes:\n"); DDMN(begin_projx); DDMN(end_projx); @@ -910,6 +918,10 @@ ir_node *get_projx_link(ir_node *cb_projx) #endif +INLINE static int +is_outermost_loop(ir_loop *l) { + return l == get_loop_outer_loop(l); +} /*-----------------------------------------------------------* @@ -970,18 +982,20 @@ static void scc (ir_node *n) { Next actions: Open a new loop on the loop tree and try to find inner loops */ -#define NO_LOOPS_WITHOUT_HEAD 1 #if NO_LOOPS_WITHOUT_HEAD /* This is an adaption of the algorithm from fiasco / optscc to * avoid loops without Block or Phi as first node. This should * severely reduce the number of evaluations of nodes to detect * a fixpoint in the heap analysis. * Further it avoids loops without firm nodes that cause errors - * in the heap analyses. */ + * in the heap analyses. + * But attention: don't do it for the outermost loop: This loop + * is not iterated. A first block can be a loop head in case of + * an endless recursion. */ ir_loop *l; int close; - if (get_loop_n_elements(current_loop) > 0) { + if ((get_loop_n_elements(current_loop) > 0) || (is_outermost_loop(current_loop))) { l = new_loop(); close = 1; } else { @@ -1069,7 +1083,6 @@ static void my_scc (ir_node *n) { Next actions: Open a new loop on the loop tree and try to find inner loops */ -#define NO_LOOPS_WITHOUT_HEAD 1 #if NO_LOOPS_WITHOUT_HEAD /* This is an adaption of the algorithm from fiasco / optscc to * avoid loops without Block or Phi as first node. This should @@ -1080,7 +1093,7 @@ static void my_scc (ir_node *n) { ir_loop *l; int close; - if (get_loop_n_elements(current_loop) > 0) { + if ((get_loop_n_elements(current_loop) > 0) || (is_outermost_loop(current_loop))) { l = new_loop(); close = 1; } else { @@ -1133,17 +1146,10 @@ void construct_backedges(ir_graph *irg) { new_loop(); /* sets current_loop */ head_rem = current_loop; /* Just for assertion */ - if (interprocedural_view) { - set_irg_visited(current_ir_graph, inc_max_irg_visited()); - init_ip_walk (); - } else { - inc_irg_visited(current_ir_graph); - } + inc_irg_visited(current_ir_graph); scc(get_irg_end(current_ir_graph)); - if (interprocedural_view) finish_ip_walk(); - assert(head_rem == current_loop); set_irg_loop(current_ir_graph, current_loop); set_irg_loopinfo_state(current_ir_graph, loopinfo_consistent); -- 2.20.1