#include "irgraph_t.h"
#include "irnode_t.h"
+#include "cgana.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);
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);
}
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 ------------------------ */
+
+/* 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;
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) { /* For unknown caller */
+ pset_insert((pset *)callee->callers, irg, (unsigned)irg >> 3);
+ ana_entry buf = { callee, NULL, 0};
+ ana_entry *found = pset_find((pset *)irg->callees, &buf, HASH_ADDRESS(callee));
+ 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, HASH_ADDRESS(callee));
+ }
+ 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 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;
}
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);
irg_walk_graph(irg, ana_Call, NULL, NULL);
}
del_pset(caller_set);
assert(c == NULL);
}
+ set_irp_callgraph_state(irp_callgraph_consistent);
}
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 */
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
((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));
{
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);
}
/* 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;
}
}
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 = 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;
+ }
+ }
+ }
+
+ set_interprocedural_view(iv_rem);
+ return is_be;
+}
+
/* Returns index of the predecessor with the smallest dfn number
greater-equal than limit. */
static int
return index;
}
+#if 0
static ir_graph *
find_tail (ir_graph *n) {
ir_graph *m;
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?
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
/*-----------------------------------------------------------*
/* 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);
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)) {
}
}
+
+
+
+/* ----------------------------------------------------------------------------------- */
+/* 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 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 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, 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. */
+ 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);
+}
+
+
/* 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)
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);
+ }
+ }
+
+ /* -- compute the loop depth -- */
+ int 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 -- */
+ ana_entry2 e;
+ 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");
+ 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;
+}
+
+/* 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();
+ }
- /* 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, ""); */
+ find_callgraph_recursions();
}
projects / libfirm / blobdiff