X-Git-Url: http://nsz.repo.hu/git/?a=blobdiff_plain;f=ir%2Fana%2Fcallgraph.c;h=dac267e3afc5ac5e8d4d8b30745d31054f90d42e;hb=00894f1e0b6e74ca6c12d253dd30f7d873808977;hp=75fb29c1bd373f1b4cf122644c4014303a389a0b;hpb=1ce363f80e6a204d4011f85813362d9bd1d0e7e4;p=libfirm

diff --git a/ir/ana/callgraph.c b/ir/ana/callgraph.c
index 75fb29c1b..dac267e3a 100644
--- a/ir/ana/callgraph.c
+++ b/ir/ana/callgraph.c
@@ -52,10 +52,10 @@
 
 #include "irgwalk.h"
 
-static int master_cg_visited = 0;
-static INLINE int  cg_irg_visited     (ir_graph *n);
+static ir_visited_t master_cg_visited = 0;
+static INLINE int cg_irg_visited      (ir_graph *n);
 static INLINE void mark_cg_irg_visited(ir_graph *n);
-static INLINE void set_cg_irg_visited (ir_graph *n, int i);
+static INLINE void set_cg_irg_visited (ir_graph *n, ir_visited_t i);
 
 /** Returns the callgraph state of the program representation. */
 irp_callgraph_state get_irp_callgraph_state(void) {
@@ -275,7 +275,7 @@ static int cg_callee_entry_cmp(const void *elt, const void *key) {
 	return e1->irg != e2->irg;
 }
 
-/** compare two ir graphs */
+/** compare two ir graphs for pointer identity */
 static int graph_cmp(const void *elt, const void *key) {
 	const ir_graph *e1 = elt;
 	const ir_graph *e2 = key;
@@ -369,7 +369,8 @@ void free_callgraph(void) {
 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;
+	if (cg_irg_visited(irg))
+		return;
 	mark_cg_irg_visited(irg);
 
 	if (pre)
@@ -387,18 +388,20 @@ static void do_walk(ir_graph *irg, callgraph_walk_func *pre, callgraph_walk_func
 
 void callgraph_walk(callgraph_walk_func *pre, callgraph_walk_func *post, void *env) {
 	int i, n_irgs = get_irp_n_irgs();
-	master_cg_visited++;
+	++master_cg_visited;
 
-	do_walk(get_irp_main_irg(), pre, post, env);
-	for (i = 0; i < n_irgs; i++) {
+	/* roots are methods which have no callers in the current program */
+	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 (get_irg_n_callers(irg) == 0)
 			do_walk(irg, pre, post, env);
 	}
+
+	/* in case of unreachable call loops we haven't visited some irgs yet */
 	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);
+		do_walk(irg, pre, post, env);
 	}
 }
 
@@ -428,10 +431,10 @@ typedef struct scc_info {
 } scc_info;
 
 /**
- * allocates a new scc_info of the obstack
+ * allocates a new scc_info on the obstack
  */
-static INLINE scc_info *new_scc_info(void) {
-	scc_info *info = obstack_alloc(outermost_ir_graph->obst, sizeof(*info));
+static INLINE scc_info *new_scc_info(struct obstack *obst) {
+	scc_info *info = obstack_alloc(obst, sizeof(*info));
 	memset(info, 0, sizeof(*info));
 	return info;
 }
@@ -439,89 +442,70 @@ static INLINE scc_info *new_scc_info(void) {
 /**
  * Returns non-zero if a graph was already visited.
  */
-static INLINE int
-cg_irg_visited(ir_graph *irg) {
-	scc_info *info = get_irg_link(irg);
-	assert(info && "missing call to init_scc");
-	return info->visited >= master_cg_visited;
+static INLINE int cg_irg_visited(ir_graph *irg) {
+	return irg->self_visited >= master_cg_visited;
 }
 
 /**
  * Marks a graph as visited.
  */
-static INLINE void
-mark_cg_irg_visited(ir_graph *irg) {
-	scc_info *info = get_irg_link(irg);
-	assert(info && "missing call to init_scc");
-	info->visited = master_cg_visited;
+static INLINE void mark_cg_irg_visited(ir_graph *irg) {
+	irg->self_visited = master_cg_visited;
 }
 
 /**
  * Set a graphs visited flag to i.
  */
-static INLINE void
-set_cg_irg_visited(ir_graph *irg, int i) {
-	scc_info *info = get_irg_link(irg);
-	assert(info && "missing call to init_scc");
-	info->visited = i;
+static INLINE void set_cg_irg_visited(ir_graph *irg, ir_visited_t i) {
+	irg->self_visited = i;
 }
 
 /**
  * Returns the visited flag of a graph.
  */
-static INLINE int
-get_cg_irg_visited(ir_graph *irg) {
-	scc_info *info = get_irg_link(irg);
-	assert(info && "missing call to init_scc");
-	return info->visited;
+static INLINE ir_visited_t get_cg_irg_visited(ir_graph *irg) {
+	return irg->self_visited;
 }
 
-static INLINE void
-mark_irg_in_stack(ir_graph *irg) {
+static INLINE void mark_irg_in_stack(ir_graph *irg) {
 	scc_info *info = get_irg_link(irg);
-	assert(info && "missing call to init_scc");
+	assert(info && "missing call to init_scc()");
 	info->in_stack = 1;
 }
 
-static INLINE void
-mark_irg_not_in_stack(ir_graph *irg) {
+static INLINE void mark_irg_not_in_stack(ir_graph *irg) {
 	scc_info *info = get_irg_link(irg);
-	assert(info && "missing call to init_scc");
+	assert(info && "missing call to init_scc()");
 	info->in_stack = 0;
 }
 
-static INLINE int
-irg_is_in_stack(ir_graph *irg) {
+static INLINE int irg_is_in_stack(ir_graph *irg) {
 	scc_info *info = get_irg_link(irg);
-	assert(info && "missing call to init_scc");
+	assert(info && "missing call to init_scc()");
 	return info->in_stack;
 }
 
-static INLINE void
-set_irg_uplink(ir_graph *irg, int uplink) {
+static INLINE void set_irg_uplink(ir_graph *irg, int uplink) {
 	scc_info *info = get_irg_link(irg);
-	assert(info && "missing call to init_scc");
+	assert(info && "missing call to init_scc()");
 	info->uplink = uplink;
 }
 
-static INLINE int
-get_irg_uplink(ir_graph *irg) {
+static INLINE int get_irg_uplink(ir_graph *irg) {
 	scc_info *info = get_irg_link(irg);
-	assert(info && "missing call to init_scc");
+	assert(info && "missing call to init_scc()");
 	return info->uplink;
 }
 
-static INLINE void
-set_irg_dfn(ir_graph *irg, int dfn) {
+static INLINE void set_irg_dfn(ir_graph *irg, int dfn) {
 	scc_info *info = get_irg_link(irg);
-	assert(info && "missing call to init_scc");
+	assert(info && "missing call to init_scc()");
 	info->dfn = dfn;
 }
 
-static INLINE int
-get_irg_dfn(ir_graph *irg) {
+static INLINE int get_irg_dfn(ir_graph *irg) {
 	scc_info *info = get_irg_link(irg);
-	assert(info && "missing call to init_scc");
+	assert(info && "missing call to init_scc()");
 	return info->dfn;
 }
 
@@ -577,7 +561,7 @@ static INLINE void pop_scc_to_loop(ir_graph *irg) {
 		m = pop();
 		loop_node_cnt++;
 		set_irg_dfn(m, loop_node_cnt);
-		add_loop_node(current_loop, (ir_node *)m);
+		add_loop_irg(current_loop, m);
 		m->l = current_loop;
 		//m->callgraph_loop_depth = current_loop->depth;
 	} while(m != irg);
@@ -592,20 +576,19 @@ static void close_loop(ir_loop *l) {
 	ir_loop *last_son = lelement.son;
 
 	if (get_kind(last_son) == k_ir_loop &&
-		get_loop_n_elements(last_son) == 1) {
-			ir_loop *gson;
+	    get_loop_n_elements(last_son) == 1) {
+		ir_loop *gson;
 
-			lelement = get_loop_element(last_son, 0);
-			gson = lelement.son;
-			if(get_kind(gson) == k_ir_loop) {
-				loop_element new_last_son;
+		lelement = get_loop_element(last_son, 0);
+		gson = lelement.son;
+		if (get_kind(gson) == k_ir_loop) {
+			loop_element new_last_son;
 
-				gson -> outer_loop = l;
-				new_last_son.son = gson;
-				l -> children[last] = new_last_son;
-			}
+			gson->outer_loop = l;
+			new_last_son.son = gson;
+			l->children[last] = new_last_son;
+		}
 	}
-
 	current_loop = l;
 }
 
@@ -631,42 +614,21 @@ static INLINE void pop_scc_unmark_visit(ir_graph *n) {
  * to the new loop and returns the father.
  */
 static ir_loop *new_loop(void) {
-	ir_loop *father, *son;
-
-	father = current_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->link     = NULL;
-	if (father) {
-		son->outer_loop = father;
-		add_loop_son(father, son);
-		son->depth = father->depth + 1;
-	} else {  /* The root loop */
-		son->outer_loop = son;
-		son->depth      = 0;
-	}
-
-#ifdef DEBUG_libfirm
-	son->loop_nr = get_irp_new_node_nr();
-#endif
+	ir_loop *father = current_loop;
+	ir_loop *son    = alloc_loop(father, outermost_ir_graph->obst);
 
 	current_loop = son;
 	return father;
 }
 
+
 /**********************************************************************/
 /* Constructing and destructing the loop/backedge information.       **/
 /**********************************************************************/
 
 /* Initialization steps. **********************************************/
 
-static void
-init_scc(void) {
+static void init_scc(struct obstack *obst) {
 	int i;
 	int n_irgs;
 
@@ -677,7 +639,7 @@ init_scc(void) {
 	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());
+		set_irg_link(irg, new_scc_info(obst));
 		irg->callgraph_recursion_depth = 0;
 		irg->callgraph_loop_depth      = 0;
 	}
@@ -688,9 +650,7 @@ init_scc(void) {
  *
  *  @param root: only needed for assertion.
  */
-static int
-is_head(ir_graph *n, ir_graph *root)
-{
+static int is_head(ir_graph *n, ir_graph *root) {
 	int i, arity;
 	int some_outof_loop = 0, some_in_loop = 0;
 
@@ -717,8 +677,7 @@ is_head(ir_graph *n, ir_graph *root)
  * within the loop.
  * @arg root: only needed for assertion.
  */
-static int
-is_endless_head(ir_graph *n, ir_graph *root)
+static int is_endless_head(ir_graph *n, ir_graph *root)
 {
 	int i, arity;
 	int some_outof_loop = 0, some_in_loop = 0;
@@ -738,7 +697,6 @@ is_endless_head(ir_graph *n, ir_graph *root)
 			some_in_loop = 1;
 		}
 	}
-
 	return !some_outof_loop & some_in_loop;
 }
 
@@ -747,8 +705,7 @@ is_endless_head(ir_graph *n, ir_graph *root)
  * Check whether there is a parallel edge in the ip control flow.
  * Only
  */
-static int
-is_ip_head(ir_graph *n, ir_graph *pred)
+static int is_ip_head(ir_graph *n, ir_graph *pred)
 {
 	int is_be = 0;
 
@@ -765,7 +722,7 @@ is_ip_head(ir_graph *n, ir_graph *pred)
 		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 */
+			if (is_CallBegin(pred_cfop)) { /* could be Unknown */
 				ir_graph *ip_pred = get_irn_irg(pred_cfop);
 				//printf("   "); DDMG(ip_pred);
 				if ((ip_pred == pred) && is_backedge(sblock, i)) {
@@ -784,8 +741,7 @@ is_ip_head(ir_graph *n, ir_graph *pred)
  * Returns index of the predecessor with the smallest dfn number
  * greater-equal than limit.
  */
-static int
-smallest_dfn_pred(ir_graph *n, int limit)
+static int smallest_dfn_pred(ir_graph *n, int limit)
 {
 	int i, index = -2, min = -1;
 
@@ -804,9 +760,7 @@ smallest_dfn_pred(ir_graph *n, int limit)
 }
 
 /** Returns index of the predecessor with the largest dfn number. */
-static int
-largest_dfn_pred(ir_graph *n)
-{
+static int largest_dfn_pred(ir_graph *n) {
 	int i, index = -2, max = -1;
 
 	int arity = get_irg_n_callees(n);
@@ -823,8 +777,7 @@ largest_dfn_pred(ir_graph *n)
 }
 
 #ifndef INTERPROCEDURAL_VIEW
-static ir_graph *
-find_tail(ir_graph *n) {
+static ir_graph *find_tail(ir_graph *n) {
 	ir_graph *m;
 	int i, res_index = -2;
 
@@ -854,7 +807,7 @@ find_tail(ir_graph *n) {
 			}
 
 			/* 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. */
+			   are not in this loop. We assume a loop not reachable from Start. */
 			if (m == n) {
 				i = -1;
 				break;
@@ -884,8 +837,7 @@ find_tail(ir_graph *n) {
 	return get_irg_callee(m, res_index);
 }
 #else
-static ir_graph *
-find_tail(ir_graph *n) {
+static ir_graph *find_tail(ir_graph *n) {
 	ir_graph *m;
 	int i, res_index = -2;
 
@@ -1039,11 +991,11 @@ static void reset_isbe(void) {
 		ir_graph *irg = get_irp_irg(i);
 
 		if (irg->caller_isbe)
-			free(irg->caller_isbe);
+			xfree(irg->caller_isbe);
 		irg->caller_isbe = NULL;
 
 		if (irg->callee_isbe)
-			free(irg->callee_isbe);
+			xfree(irg->callee_isbe);
 		irg->callee_isbe = NULL;
 	}
 }
@@ -1057,7 +1009,7 @@ static void reset_isbe(void) {
 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);
+	ir_visited_t old_visited = get_cg_irg_visited(irg);
 	int i, n_callees;
 
 	//return ;
@@ -1142,7 +1094,8 @@ static void compute_rec_depth(ir_graph *irg, void *env) {
 	int i, n_callees;
 	int pushed = 0;
 
-	if (cg_irg_visited(irg)) return;
+	if (cg_irg_visited(irg))
+		return;
 	mark_cg_irg_visited(irg);
 
 	/* -- compute and set the new nesting value -- */
@@ -1208,7 +1161,8 @@ static void compute_method_execution_frequency(ir_graph *irg, void *env) {
 	int    n_callees;
 	(void) env;
 
-	if (cg_irg_visited(irg)) return;
+	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
@@ -1216,7 +1170,8 @@ static void compute_method_execution_frequency(ir_graph *irg, void *env) {
 	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 (is_irg_caller_backedge(irg, i))
+			continue;
 		if (!cg_irg_visited(m)) {
 			return;
 		}
@@ -1258,6 +1213,7 @@ static void compute_method_execution_frequency(ir_graph *irg, void *env) {
 /* Compute the backedges that represent recursions. */
 void find_callgraph_recursions(void) {
 	int i, n_irgs = get_irp_n_irgs();
+	struct obstack temp;
 
 	reset_isbe();
 
@@ -1269,12 +1225,13 @@ void find_callgraph_recursions(void) {
 	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();
+	obstack_init(&temp);
+	init_scc(&temp);
 
 	current_loop = NULL;
 	new_loop();  /* sets current_loop */
 
-	master_cg_visited++;
+	++master_cg_visited;
 	cgscc(outermost_ir_graph);
 	for (i = 0; i < n_irgs; ++i) {
 		ir_graph *irg = get_irp_irg(i);
@@ -1286,7 +1243,10 @@ void find_callgraph_recursions(void) {
 		if (!cg_irg_visited(irg))
 			cgscc(irg);
 	}
+	obstack_free(&temp, NULL);
+
 	irp->outermost_cg_loop = current_loop;
+	mature_loops(current_loop, outermost_ir_graph->obst);
 
 	/* -- Reverse the backedge information. -- */
 	for (i = 0; i < n_irgs; ++i) {