X-Git-Url: http://nsz.repo.hu/git/?a=blobdiff_plain;f=ir%2Fana%2Fcallgraph.c;h=452e38d466597c2c043ba37a8e13fecec3264c70;hb=e98f2bd09ccc403c64e3ebe30f3b0183760bccc6;hp=b3c656f04584f8e4e69b9143d400441f654c2d75;hpb=5f05c97be1452a4fd611648879c1544a8af611c9;p=libfirm

diff --git a/ir/ana/callgraph.c b/ir/ana/callgraph.c
index b3c656f04..452e38d46 100644
--- a/ir/ana/callgraph.c
+++ b/ir/ana/callgraph.c
@@ -1,5 +1,5 @@
 /*
- * Copyright (C) 1995-2007 University of Karlsruhe.  All right reserved.
+ * Copyright (C) 1995-2008 University of Karlsruhe.  All right reserved.
  *
  * This file is part of libFirm.
  *
@@ -24,16 +24,10 @@
  * @date        21.7.2004
  * @version     $Id$
  */
-#ifdef HAVE_CONFIG_H
-# include "config.h"
-#endif
-
-#ifdef HAVE_STRING_H
-# include <string.h>
-#endif
-# ifdef HAVE_STDLIB_H
+#include "config.h"
+
+#include <string.h>
 #include <stdlib.h>
-#endif
 
 #include "callgraph.h"
 
@@ -52,42 +46,47 @@
 
 #include "irgwalk.h"
 
-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);
+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);
 
 /** Returns the callgraph state of the program representation. */
-irp_callgraph_state get_irp_callgraph_state(void) {
+irp_callgraph_state get_irp_callgraph_state(void)
+{
 	return irp->callgraph_state;
 }
 
 /* Sets the callgraph state of the program representation. */
-void set_irp_callgraph_state(irp_callgraph_state s) {
+void set_irp_callgraph_state(irp_callgraph_state s)
+{
 	irp->callgraph_state = s;
 }
 
 /* Returns the number of procedures that call the given irg. */
-int get_irg_n_callers(ir_graph *irg) {
+int get_irg_n_callers(const ir_graph *irg)
+{
 	if (irg->callers) return ARR_LEN(irg->callers);
 	return -1;
 }
 
 /* Returns the caller at position pos. */
-ir_graph *get_irg_caller(ir_graph *irg, int pos) {
+ir_graph *get_irg_caller(const ir_graph *irg, int pos)
+{
 	assert(pos >= 0 && pos < get_irg_n_callers(irg));
 	if (irg->callers) return irg->callers[pos];
 	return NULL;
 }
 
 /* Returns non-zero if the caller at position pos is "a backedge", i.e. a recursion. */
-int is_irg_caller_backedge(ir_graph *irg, int pos) {
+int is_irg_caller_backedge(const ir_graph *irg, int pos)
+{
 	assert(pos >= 0 && pos < get_irg_n_callers(irg));
 	return irg->caller_isbe != NULL ? rbitset_is_set(irg->caller_isbe, pos) : 0;
 }
 
 /** Search the caller in the list of all callers and set it's backedge property. */
-static void set_irg_caller_backedge(ir_graph *irg, ir_graph *caller) {
+static void set_irg_caller_backedge(ir_graph *irg, ir_graph *caller)
+{
 	int i, n_callers = get_irg_n_callers(irg);
 
 	/* allocate a new array on demand */
@@ -102,7 +101,8 @@ static void set_irg_caller_backedge(ir_graph *irg, ir_graph *caller) {
 }
 
 /* Returns non-zero if the irg has a backedge caller. */
-int has_irg_caller_backedge(ir_graph *irg) {
+int has_irg_caller_backedge(const ir_graph *irg)
+{
 	int i, n_callers = get_irg_n_callers(irg);
 
 	if (irg->caller_isbe != NULL) {
@@ -118,7 +118,8 @@ int has_irg_caller_backedge(ir_graph *irg) {
  * Given the position pos_caller of an caller of irg, return
  * irg's callee position on that caller.
  */
-static int reverse_pos(ir_graph *callee, int pos_caller) {
+static int reverse_pos(const 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;
@@ -136,7 +137,8 @@ static int reverse_pos(ir_graph *callee, int pos_caller) {
 }
 
 /* Returns the maximal loop depth of call nodes that call along this edge. */
-int get_irg_caller_loop_depth(ir_graph *irg, int pos) {
+int get_irg_caller_loop_depth(const ir_graph *irg, int pos)
+{
 	ir_graph *caller     = get_irg_caller(irg, pos);
 	int       pos_callee = reverse_pos(irg, pos);
 
@@ -145,26 +147,30 @@ int get_irg_caller_loop_depth(ir_graph *irg, int pos) {
 
 
 /* Returns the number of procedures that are called by the given irg. */
-int get_irg_n_callees(ir_graph *irg) {
+int get_irg_n_callees(const ir_graph *irg)
+{
 	if (irg->callees) return ARR_LEN(irg->callees);
 	return -1;
 }
 
 /* Returns the callee at position pos. */
-ir_graph *get_irg_callee(ir_graph *irg, int pos) {
+ir_graph *get_irg_callee(const ir_graph *irg, int pos)
+{
 	assert(pos >= 0 && pos < get_irg_n_callees(irg));
 	if (irg->callees) return irg->callees[pos]->irg;
 	return NULL;
 }
 
 /* Returns non-zero if the callee at position pos is "a backedge", i.e. a recursion. */
-int is_irg_callee_backedge(ir_graph *irg, int pos) {
+int is_irg_callee_backedge(const ir_graph *irg, int pos)
+{
 	assert(pos >= 0 && pos < get_irg_n_callees(irg));
 	return irg->callee_isbe != NULL ? rbitset_is_set(irg->callee_isbe, pos) : 0;
 }
 
 /* Returns non-zero if the irg has a backedge callee. */
-int has_irg_callee_backedge(ir_graph *irg) {
+int has_irg_callee_backedge(const ir_graph *irg)
+{
 	int i, n_callees = get_irg_n_callees(irg);
 
 	if (irg->callee_isbe != NULL) {
@@ -178,7 +184,8 @@ int has_irg_callee_backedge(ir_graph *irg) {
 /**
  * Mark the callee at position pos as a backedge.
  */
-static void set_irg_callee_backedge(ir_graph *irg, int pos) {
+static void set_irg_callee_backedge(ir_graph *irg, int pos)
+{
 	int n = get_irg_n_callees(irg);
 
 	/* allocate a new array on demand */
@@ -189,14 +196,15 @@ static void set_irg_callee_backedge(ir_graph *irg, int pos) {
 }
 
 /* Returns the maximal loop depth of call nodes that call along this edge. */
-int get_irg_callee_loop_depth(ir_graph *irg, int pos) {
+int get_irg_callee_loop_depth(const ir_graph *irg, int pos)
+{
 	assert(pos >= 0 && pos < get_irg_n_callees(irg));
 	if (irg->callees) return irg->callees[pos]->max_depth;
 	return -1;
 }
 
-
-double get_irg_callee_execution_frequency(ir_graph *irg, int pos) {
+static double get_irg_callee_execution_frequency(const ir_graph *irg, int pos)
+{
 	ir_node **arr = irg->callees[pos]->call_list;
 	int i, n_Calls = ARR_LEN(arr);
 	double freq = 0.0;
@@ -207,14 +215,17 @@ double get_irg_callee_execution_frequency(ir_graph *irg, int pos) {
 	return freq;
 }
 
-double get_irg_callee_method_execution_frequency(ir_graph *irg, int pos) {
+static double get_irg_callee_method_execution_frequency(const ir_graph *irg,
+                                                        int pos)
+{
 	double call_freq = get_irg_callee_execution_frequency(irg, pos);
 	double meth_freq = get_irg_method_execution_frequency(irg);
 	return call_freq * meth_freq;
 }
 
-
-double get_irg_caller_method_execution_frequency(ir_graph *irg, int pos) {
+static double get_irg_caller_method_execution_frequency(const ir_graph *irg,
+                                                        int pos)
+{
 	ir_graph *caller     = get_irg_caller(irg, pos);
 	int       pos_callee = reverse_pos(irg, pos);
 
@@ -222,13 +233,13 @@ double get_irg_caller_method_execution_frequency(ir_graph *irg, int pos) {
 }
 
 
-
 /* --------------------- Compute the callgraph ------------------------ */
 
 /**
  * Walker called by compute_callgraph(), analyses all Call nodes.
  */
-static void ana_Call(ir_node *n, void *env) {
+static void ana_Call(ir_node *n, void *env)
+{
 	int i, n_callees;
 	ir_graph *irg;
 	(void) env;
@@ -249,13 +260,13 @@ static void ana_Call(ir_node *n, void *env) {
 			buf.irg = callee;
 
 			pset_insert((pset *)callee->callers, irg, HASH_PTR(irg));
-			found = pset_find((pset *)irg->callees, &buf, HASH_PTR(callee));
+			found = (cg_callee_entry*) pset_find((pset *)irg->callees, &buf, HASH_PTR(callee));
 			if (found) {  /* add Call node to list, compute new nesting. */
 				ir_node **arr = found->call_list;
 				ARR_APP1(ir_node *, arr, n);
 				found->call_list = arr;
 			} else { /* New node, add Call node and init nesting. */
-				found = (cg_callee_entry *)obstack_alloc(irg->obst, sizeof(*found));
+				found = OALLOC(irg->obst, cg_callee_entry);
 				found->irg = callee;
 				found->call_list = NEW_ARR_F(ir_node *, 1);
 				found->call_list[0] = n;
@@ -269,28 +280,27 @@ static void ana_Call(ir_node *n, void *env) {
 }
 
 /** compare two ir graphs in a cg_callee_entry */
-static int cg_callee_entry_cmp(const void *elt, const void *key) {
-	const cg_callee_entry *e1 = elt;
-	const cg_callee_entry *e2 = key;
+static int cg_callee_entry_cmp(const void *elt, const void *key)
+{
+	const cg_callee_entry *e1 = (const cg_callee_entry*) elt;
+	const cg_callee_entry *e2 = (const cg_callee_entry*) key;
 	return e1->irg != e2->irg;
 }
 
-/** compare two ir graphs */
-static int graph_cmp(const void *elt, const void *key) {
-	const ir_graph *e1 = elt;
-	const ir_graph *e2 = key;
+/** compare two ir graphs for pointer identity */
+static int graph_cmp(const void *elt, const void *key)
+{
+	const ir_graph *e1 = (const ir_graph*) elt;
+	const ir_graph *e2 = (const ir_graph*) key;
 	return e1 != e2;
 }
 
 
 /* Construct and destruct the callgraph. */
-void compute_callgraph(void) {
+void compute_callgraph(void)
+{
 	int i, n_irgs;
 
-#ifdef INTERPROCEDURAL_VIEW
-	assert(! get_interprocedural_view());  /* Else walking will not reach the Call nodes. */
-#endif
-
 	/* initialize */
 	free_callgraph();
 
@@ -321,10 +331,10 @@ void compute_callgraph(void) {
 		count = pset_count(callee_set);
 		irg->callees = NEW_ARR_F(cg_callee_entry *, count);
 		irg->callee_isbe = NULL;
-		callee = pset_first(callee_set);
+		callee = (cg_callee_entry*) pset_first(callee_set);
 		for (j = 0; j < count; ++j) {
 			irg->callees[j] = callee;
-			callee = pset_next(callee_set);
+			callee = (cg_callee_entry*) pset_next(callee_set);
 		}
 		del_pset(callee_set);
 		assert(callee == NULL);
@@ -333,10 +343,10 @@ void compute_callgraph(void) {
 		count = pset_count(caller_set);
 		irg->callers = NEW_ARR_F(ir_graph *, count);
 		irg->caller_isbe =  NULL;
-		c = pset_first(caller_set);
+		c = (ir_graph*) pset_first(caller_set);
 		for (j = 0; j < count; ++j) {
 			irg->callers[j] = c;
-			c = pset_next(caller_set);
+			c = (ir_graph*) pset_next(caller_set);
 		}
 		del_pset(caller_set);
 		assert(c == NULL);
@@ -345,7 +355,8 @@ void compute_callgraph(void) {
 }
 
 /* Destruct the callgraph. */
-void free_callgraph(void) {
+void free_callgraph(void)
+{
 	int i, n_irgs = get_irp_n_irgs();
 	for (i = 0; i < n_irgs; ++i) {
 		ir_graph *irg = get_irp_irg(i);
@@ -366,10 +377,12 @@ void free_callgraph(void) {
 /* ----------------------------------------------------------------------------------- */
 
 
-static void do_walk(ir_graph *irg, callgraph_walk_func *pre, callgraph_walk_func *post, void *env) {
+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)
@@ -385,20 +398,23 @@ static void do_walk(ir_graph *irg, callgraph_walk_func *pre, callgraph_walk_func
 		post(irg, env);
 }
 
-void callgraph_walk(callgraph_walk_func *pre, callgraph_walk_func *post, void *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++;
+	++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,100 +444,91 @@ 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));
-	memset(info, 0, sizeof(*info));
-	return info;
+static inline scc_info *new_scc_info(struct obstack *obst)
+{
+	return OALLOCZ(obst, scc_info);
 }
 
 /**
  * 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) {
-	scc_info *info = get_irg_link(irg);
-	assert(info && "missing call to init_scc");
+static inline void mark_irg_in_stack(ir_graph *irg)
+{
+	scc_info *info = (scc_info*) get_irg_link(irg);
+	assert(info && "missing call to init_scc()");
 	info->in_stack = 1;
 }
 
-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");
+static inline void mark_irg_not_in_stack(ir_graph *irg)
+{
+	scc_info *info = (scc_info*) get_irg_link(irg);
+	assert(info && "missing call to init_scc()");
 	info->in_stack = 0;
 }
 
-static INLINE int
-irg_is_in_stack(ir_graph *irg) {
-	scc_info *info = get_irg_link(irg);
-	assert(info && "missing call to init_scc");
+static inline int irg_is_in_stack(ir_graph *irg)
+{
+	scc_info *info = (scc_info*) get_irg_link(irg);
+	assert(info && "missing call to init_scc()");
 	return info->in_stack;
 }
 
-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");
+static inline void set_irg_uplink(ir_graph *irg, int uplink)
+{
+	scc_info *info = (scc_info*) get_irg_link(irg);
+	assert(info && "missing call to init_scc()");
 	info->uplink = uplink;
 }
 
-static INLINE int
-get_irg_uplink(ir_graph *irg) {
-	scc_info *info = get_irg_link(irg);
-	assert(info && "missing call to init_scc");
+static inline int get_irg_uplink(ir_graph *irg)
+{
+	scc_info *info = (scc_info*) get_irg_link(irg);
+	assert(info && "missing call to init_scc()");
 	return info->uplink;
 }
 
-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");
+static inline void set_irg_dfn(ir_graph *irg, int dfn)
+{
+	scc_info *info = (scc_info*) get_irg_link(irg);
+	assert(info && "missing call to init_scc()");
 	info->dfn = dfn;
 }
 
-static INLINE int
-get_irg_dfn(ir_graph *irg) {
-	scc_info *info = get_irg_link(irg);
-	assert(info && "missing call to init_scc");
+static inline int get_irg_dfn(ir_graph *irg)
+{
+	scc_info *info = (scc_info*) get_irg_link(irg);
+	assert(info && "missing call to init_scc()");
 	return info->dfn;
 }
 
@@ -535,7 +542,8 @@ static int tos = 0;                /**< top of stack */
 /**
  * Initialize the irg stack.
  */
-static INLINE void init_stack(void) {
+static inline void init_stack(void)
+{
 	if (stack) {
 		ARR_RESIZE(ir_graph *, stack, 1000);
 	} else {
@@ -548,10 +556,11 @@ static INLINE void init_stack(void) {
  * push a graph on the irg stack
  * @param n the graph to be pushed
  */
-static INLINE void push(ir_graph *irg) {
+static inline void push(ir_graph *irg)
+{
 	if (tos == ARR_LEN(stack)) {
 		int nlen = ARR_LEN(stack) * 2;
-		ARR_RESIZE(ir_node *, stack, nlen);
+		ARR_RESIZE(ir_graph*, stack, nlen);
 	}
 	stack [tos++] = irg;
 	mark_irg_in_stack(irg);
@@ -560,7 +569,8 @@ static INLINE void push(ir_graph *irg) {
 /**
  * return the topmost graph on the stack and pop it
  */
-static INLINE ir_graph *pop(void) {
+static inline ir_graph *pop(void)
+{
 	ir_graph *irg = stack[--tos];
 	mark_irg_not_in_stack(irg);
 	return irg;
@@ -570,42 +580,43 @@ static INLINE ir_graph *pop(void) {
  * The nodes up to irg 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 *irg) {
+static inline void pop_scc_to_loop(ir_graph *irg)
+{
 	ir_graph *m;
 
 	do {
 		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);
+	} while (m != irg);
 }
 
 /* GL ??? my last son is my grandson???  Removes cfloops with no
    ir_nodes in them.  Such loops have only another loop as son. (Why
    can't they have two loops as sons? Does it never get that far? ) */
-static void close_loop(ir_loop *l) {
+static void close_loop(ir_loop *l)
+{
 	int last = get_loop_n_elements(l) - 1;
 	loop_element lelement = get_loop_element(l, last);
 	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;
 }
 
@@ -613,7 +624,8 @@ static void close_loop(ir_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.
  */
-static INLINE void pop_scc_unmark_visit(ir_graph *n) {
+static inline void pop_scc_unmark_visit(ir_graph *n)
+{
 	ir_graph *m = NULL;
 
 	while (m != n) {
@@ -630,43 +642,24 @@ static INLINE void pop_scc_unmark_visit(ir_graph *n) {
  * 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 = 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
+static ir_loop *new_loop(void)
+{
+	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 +670,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,8 +681,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;
@@ -708,17 +700,16 @@ is_head(ir_graph *n, ir_graph *root)
 		}
 	}
 
-	return some_outof_loop & some_in_loop;
+	return some_outof_loop && some_in_loop;
 }
 
 /**
  * Returns non-zero if n is possible loop head of an endless loop.
- * I.e., it is a Block, Phi or Filter node and has only predecessors
+ * I.e., it is a Block or Phi node and has only predecessors
  * within the loop.
  * @arg root: only needed for assertion.
  */
-static int
-is_endless_head(ir_graph *n, ir_graph *root)
+static int is_endless_head(ir_graph *n, ir_graph *root)
 {
 	int i, arity;
 	int some_outof_loop = 0, some_in_loop = 0;
@@ -738,54 +729,14 @@ is_endless_head(ir_graph *n, ir_graph *root)
 			some_in_loop = 1;
 		}
 	}
-
-	return !some_outof_loop & some_in_loop;
-}
-
-#ifdef INTERPROCEDURAL_VIEW
-/**
- * Check whether there is a parallel edge in the ip control flow.
- * Only
- */
-static int
-is_ip_head(ir_graph *n, ir_graph *pred)
-{
-	int is_be = 0;
-
-	int iv_rem = get_interprocedural_view();
-	set_interprocedural_view(1);
-	{
-		ir_node *sblock = get_irg_start_block(n);
-		int i, arity = get_Block_n_cfgpreds(sblock);
-
-		//printf(" edge from "); DDMG(n);
-		//printf(" to pred   "); DDMG(pred);
-		//printf(" sblock    "); DDMN(sblock);
-
-		for (i = 0; i < arity; i++) {
-			ir_node *pred_cfop = skip_Proj(get_Block_cfgpred(sblock, i));
-			//printf("  "); DDMN(pred_cfop);
-			if (get_irn_op(pred_cfop) == op_CallBegin) {  /* could be Unknown */
-				ir_graph *ip_pred = get_irn_irg(pred_cfop);
-				//printf("   "); DDMG(ip_pred);
-				if ((ip_pred == pred) && is_backedge(sblock, i)) {
-					//printf("   found\n");
-					is_be = 1;
-				}
-			}
-		}
-	}
-	set_interprocedural_view(iv_rem);
-	return is_be;
+	return !some_outof_loop && some_in_loop;
 }
-#endif /* INTERPROCEDURAL_VIEW */
 
 /**
  * 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,8 +755,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;
 
@@ -822,9 +772,8 @@ largest_dfn_pred(ir_graph *n)
 	return index;
 }
 
-#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 +803,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;
@@ -883,82 +832,14 @@ 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 /* INTERPROCEDURAL_VIEW */
 
 /*-----------------------------------------------------------*
  *                   The core algorithm.                     *
  *-----------------------------------------------------------*/
 
 
-static void cgscc(ir_graph *n) {
+static void cgscc(ir_graph *n)
+{
 	int i, arity;
 
 	if (cg_irg_visited(n)) return;
@@ -979,7 +860,7 @@ static void cgscc(ir_graph *n) {
 		/** This marks the backedge, but does it guarantee a correct loop tree? */
 		//if (m == n) { set_irg_callee_backedge(n, i); continue; }
 
-		cgscc (m);
+		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. */
@@ -1032,18 +913,19 @@ static void cgscc(ir_graph *n) {
 /**
  * reset the backedge information for all callers in all irgs
  */
-static void reset_isbe(void) {
+static void reset_isbe(void)
+{
 	int i, n_irgs = get_irp_n_irgs();
 
 	for (i = 0; i < n_irgs; ++i) {
 		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;
 	}
 }
@@ -1054,10 +936,11 @@ static void reset_isbe(void) {
 /* weight. Assign graphs the maximal depth.                                            */
 /* ----------------------------------------------------------------------------------- */
 
-static void compute_loop_depth(ir_graph *irg, void *env) {
+static void compute_loop_depth(ir_graph *irg, void *env)
+{
 	int current_nesting = *(int *) env;
 	int old_nesting = irg->callgraph_loop_depth;
-	int old_visited = get_cg_irg_visited(irg);
+	ir_visited_t old_visited = get_cg_irg_visited(irg);
 	int i, n_callees;
 
 	//return ;
@@ -1066,9 +949,6 @@ static void compute_loop_depth(ir_graph *irg, void *env) {
 
 	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;
 
@@ -1108,7 +988,8 @@ typedef struct ana_entry2 {
 /**
  * push a loop entry on the stack
  */
-static void push2(ana_entry2 *e, ir_loop *g) {
+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 {
@@ -1120,14 +1001,16 @@ static void push2(ana_entry2 *e, ir_loop *g) {
 /**
  * returns the top of stack and pop it
  */
-static ir_loop *pop2(ana_entry2 *e) {
+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) {
+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;
@@ -1135,14 +1018,16 @@ static int in_stack(ana_entry2 *e, ir_loop *g) {
 	return 0;
 }
 
-static void compute_rec_depth(ir_graph *irg, void *env) {
+static void compute_rec_depth(ir_graph *irg, void *env)
+{
 	ana_entry2 *e = (ana_entry2 *)env;
 	ir_loop *l = irg->l;
 	int depth, old_depth = irg->callgraph_recursion_depth;
 	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 -- */
@@ -1186,7 +1071,8 @@ static void compute_rec_depth(ir_graph *irg, void *env) {
 /* ----------------------------------------------------------------------------------- */
 
 /* Returns the method execution frequency of a graph. */
-double get_irg_method_execution_frequency(ir_graph *irg) {
+double get_irg_method_execution_frequency(const ir_graph *irg)
+{
 	return irg->method_execution_frequency;
 }
 
@@ -1194,21 +1080,24 @@ double get_irg_method_execution_frequency(ir_graph *irg) {
  * Increase the method execution frequency to freq if its current value is
  * smaller then this.
  */
-static void set_irg_method_execution_frequency(ir_graph *irg, double freq) {
+static void set_irg_method_execution_frequency(ir_graph *irg, double freq)
+{
 	irg->method_execution_frequency = freq;
 
 	if (irp->max_method_execution_frequency < freq)
 		irp->max_method_execution_frequency = freq;
 }
 
-static void compute_method_execution_frequency(ir_graph *irg, void *env) {
+static void compute_method_execution_frequency(ir_graph *irg, void *env)
+{
 	int i, n_callers;
 	double freq;
 	int    found_edge;
 	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 +1105,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;
 		}
@@ -1256,8 +1146,10 @@ 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();
+void find_callgraph_recursions(void)
+{
+	int i, n_irgs;
+	struct obstack temp;
 
 	reset_isbe();
 
@@ -1269,13 +1161,15 @@ 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);
+	n_irgs = get_irp_n_irgs();
 	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)
@@ -1286,7 +1180,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) {
@@ -1302,7 +1199,8 @@ void find_callgraph_recursions(void) {
 }
 
 /* Compute interprocedural performance estimates. */
-void compute_performance_estimates(void) {
+void compute_performance_estimates(void)
+{
 	int i, n_irgs = get_irp_n_irgs();
 	int current_nesting;
 	ana_entry2 e;
@@ -1313,21 +1211,18 @@ void compute_performance_estimates(void) {
 	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(), &current_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, &current_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, &current_nesting);
-			//printf(" ** starting at      "); DDMG(irg);
 		}
 	}
 
@@ -1341,20 +1236,17 @@ void compute_performance_estimates(void) {
 
 	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);
 		}
 	}
 
@@ -1382,7 +1274,8 @@ void compute_performance_estimates(void) {
 
 /* Returns the maximal loop depth of all paths from an external visible method to
    this irg. */
-int  get_irg_loop_depth(ir_graph *irg) {
+int  get_irg_loop_depth(const ir_graph *irg)
+{
 	assert(irp->callgraph_state == irp_callgraph_consistent ||
 		irp->callgraph_state == irp_callgraph_and_calltree_consistent);
 	return  irg->callgraph_loop_depth;
@@ -1390,13 +1283,15 @@ int  get_irg_loop_depth(ir_graph *irg) {
 
 /* Returns the maximal recursion depth of all paths from an external visible method to
    this irg. */
-int get_irg_recursion_depth(ir_graph *irg) {
+int get_irg_recursion_depth(const ir_graph *irg)
+{
 	assert(irp->callgraph_state == irp_callgraph_and_calltree_consistent);
 	return irg->callgraph_recursion_depth;
 }
 
 /* Computes the interprocedural loop nesting information. */
-void analyse_loop_nesting_depth(void) {
+void analyse_loop_nesting_depth(void)
+{
 	ir_entity **free_methods = NULL;
 	int arr_len;
 
@@ -1416,13 +1311,16 @@ void analyse_loop_nesting_depth(void) {
 	set_irp_loop_nesting_depth_state(loop_nesting_depth_consistent);
 }
 
-loop_nesting_depth_state get_irp_loop_nesting_depth_state(void) {
+loop_nesting_depth_state get_irp_loop_nesting_depth_state(void)
+{
 	return irp->lnd_state;
 }
-void set_irp_loop_nesting_depth_state(loop_nesting_depth_state s) {
+void set_irp_loop_nesting_depth_state(loop_nesting_depth_state s)
+{
 	irp->lnd_state = s;
 }
-void set_irp_loop_nesting_depth_state_inconsistent(void) {
+void set_irp_loop_nesting_depth_state_inconsistent(void)
+{
 	if (irp->lnd_state == loop_nesting_depth_consistent)
 		irp->lnd_state = loop_nesting_depth_inconsistent;
 }