Add irn_visited_else_mark(), which combines irn_visited() and mark_irn_visited().

[libfirm] / ir / ana / callgraph.c

diff --git a/ir/ana/callgraph.c b/ir/ana/callgraph.c
index d7e0715..dac267e 100644 (file)
--- 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.
  *
  *
  * This file is part of libFirm.
  *


@@ -48,13 +48,14 @@
 #include "array.h"
 #include "pmap.h"
 #include "hashptr.h"
 #include "array.h"
 #include "pmap.h"
 #include "hashptr.h"

+#include "raw_bitset.h"

 
 #include "irgwalk.h"
 
 
 #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 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) {
 
 /** Returns the callgraph state of the program representation. */
 irp_callgraph_state get_irp_callgraph_state(void) {


@@ -74,15 +75,15 @@ int get_irg_n_callers(ir_graph *irg) {
 
 /* Returns the caller at position pos. */
 ir_graph *get_irg_caller(ir_graph *irg, int pos) {
 
 /* Returns the caller at position pos. */
 ir_graph *get_irg_caller(ir_graph *irg, int pos) {

-       assert (pos >= 0 && pos < get_irg_n_callers(irg));
+       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) {
        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) {

-       assert (pos >= 0 && pos < get_irg_n_callers(irg));
-       return irg->caller_isbe != NULL ? irg->caller_isbe[pos] : 0;
+       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. */
 }
 
 /** Search the caller in the list of all callers and set it's backedge property. */


@@ -91,10 +92,10 @@ static void set_irg_caller_backedge(ir_graph *irg, ir_graph *caller) {
 
        /* allocate a new array on demand */
        if (irg->caller_isbe == NULL)
 
        /* allocate a new array on demand */
        if (irg->caller_isbe == NULL)

-               irg->caller_isbe = xcalloc(n_callers, sizeof(irg->caller_isbe[0]));
+               irg->caller_isbe = rbitset_malloc(n_callers);

        for (i = 0; i < n_callers; ++i) {
                if (get_irg_caller(irg, i) == caller) {
        for (i = 0; i < n_callers; ++i) {
                if (get_irg_caller(irg, i) == caller) {

-                       irg->caller_isbe[i] = 1;
+                       rbitset_set(irg->caller_isbe, i);

                        break;
                }
        }
                        break;
                }
        }


@@ -106,7 +107,8 @@ int has_irg_caller_backedge(ir_graph *irg) {
 
        if (irg->caller_isbe != NULL) {
                for (i = 0; i < n_callers; ++i)
 
        if (irg->caller_isbe != NULL) {
                for (i = 0; i < n_callers; ++i)

-                       if (irg->caller_isbe[i]) return 1;
+                       if (rbitset_is_set(irg->caller_isbe, i))
+                               return 1;

        }
        return 0;
 }
        }
        return 0;
 }


@@ -150,15 +152,15 @@ int get_irg_n_callees(ir_graph *irg) {
 
 /* Returns the callee at position pos. */
 ir_graph *get_irg_callee(ir_graph *irg, int pos) {
 
 /* Returns the callee at position pos. */
 ir_graph *get_irg_callee(ir_graph *irg, int pos) {

-       assert (pos >= 0 && pos < get_irg_n_callees(irg));
+       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) {
        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) {

-       assert (pos >= 0 && pos < get_irg_n_callees(irg));
-       return irg->callee_isbe != NULL ? irg->callee_isbe[pos] : 0;
+       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. */
 }
 
 /* Returns non-zero if the irg has a backedge callee. */


@@ -167,7 +169,8 @@ int has_irg_callee_backedge(ir_graph *irg) {
 
        if (irg->callee_isbe != NULL) {
                for (i = 0; i < n_callees; ++i)
 
        if (irg->callee_isbe != NULL) {
                for (i = 0; i < n_callees; ++i)

-                       if (irg->callee_isbe[i]) return 1;
+                       if (rbitset_is_set(irg->callee_isbe, i))
+                               return 1;

        }
        return 0;
 }
        }
        return 0;
 }


@@ -178,17 +181,16 @@ int has_irg_callee_backedge(ir_graph *irg) {
 static void set_irg_callee_backedge(ir_graph *irg, int pos) {
        int n = get_irg_n_callees(irg);
 
 static void set_irg_callee_backedge(ir_graph *irg, int pos) {
        int n = get_irg_n_callees(irg);
 

-       assert (pos >= 0 && pos < n);
-

        /* allocate a new array on demand */
        if (irg->callee_isbe == NULL)
        /* allocate a new array on demand */
        if (irg->callee_isbe == NULL)

-               irg->callee_isbe = xcalloc(n, sizeof(irg->callee_isbe[0]));
-       irg->callee_isbe[pos] = 1;
+               irg->callee_isbe = rbitset_malloc(n);
+       assert(pos >= 0 && pos < n);
+       rbitset_set(irg->callee_isbe, 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) {
 }
 
 /* Returns the maximal loop depth of call nodes that call along this edge. */
 int get_irg_callee_loop_depth(ir_graph *irg, int pos) {

-       assert (pos >= 0 && pos < get_irg_n_callees(irg));
+       assert(pos >= 0 && pos < get_irg_n_callees(irg));

        if (irg->callees) return irg->callees[pos]->max_depth;
        return -1;
 }
        if (irg->callees) return irg->callees[pos]->max_depth;
        return -1;
 }


@@ -229,6 +231,7 @@ double get_irg_caller_method_execution_frequency(ir_graph *irg, int pos) {
 static void ana_Call(ir_node *n, void *env) {
        int i, n_callees;
        ir_graph *irg;
 static void ana_Call(ir_node *n, void *env) {
        int i, n_callees;
        ir_graph *irg;

+       (void) env;

 
        if (! is_Call(n)) return;
 
 
        if (! is_Call(n)) return;
 


@@ -272,7 +275,7 @@ static int cg_callee_entry_cmp(const void *elt, const void *key) {
        return e1->irg != e2->irg;
 }
 
        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;
 static int graph_cmp(const void *elt, const void *key) {
        const ir_graph *e1 = elt;
        const ir_graph *e2 = key;


@@ -284,7 +287,9 @@ static int graph_cmp(const void *elt, const void *key) {
 void compute_callgraph(void) {
        int i, n_irgs;
 
 void compute_callgraph(void) {
        int i, n_irgs;
 

+#ifdef INTERPROCEDURAL_VIEW

        assert(! get_interprocedural_view());  /* Else walking will not reach the Call nodes. */
        assert(! get_interprocedural_view());  /* Else walking will not reach the Call nodes. */

+#endif

 
        /* initialize */
        free_callgraph();
 
        /* initialize */
        free_callgraph();


@@ -364,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;
 
 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)
        mark_cg_irg_visited(irg);
 
        if (pre)


@@ -382,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();
 
 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);
                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);
        }
                        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);
        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);

        }
 }
 
        }
 }
 


@@ -411,7 +419,6 @@ static int loop_node_cnt = 0;      /**< Counts the number of allocated cfloop no
 static int current_dfn = 1;        /**< Counter to generate depth first numbering
                                         of visited nodes.  */
 
 static int current_dfn = 1;        /**< Counter to generate depth first numbering
                                         of visited nodes.  */
 

-

 /*-----------------*/
 /* Node attributes */
 /*-----------------*/
 /*-----------------*/
 /* Node attributes */
 /*-----------------*/


@@ -424,10 +431,10 @@ typedef struct scc_info {
 } 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;
 }
        memset(info, 0, sizeof(*info));
        return info;
 }


@@ -435,89 +442,70 @@ static INLINE scc_info *new_scc_info(void) {
 /**
  * Returns non-zero if a graph was already visited.
  */
 /**
  * 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.
  */
 }
 
 /**
  * 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.
  */
 }
 
 /**
  * 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.
  */
 }
 
 /**
  * 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);
        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;
 }
 
        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);
        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;
 }
 
        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);
        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;
 }
 
        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);
        scc_info *info = get_irg_link(irg);

-       assert(info && "missing call to init_scc");
+       assert(info && "missing call to init_scc()");

        info->uplink = uplink;
 }
 
        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);
        scc_info *info = get_irg_link(irg);

-       assert(info && "missing call to init_scc");
+       assert(info && "missing call to init_scc()");

        return info->uplink;
 }
 
        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);
        scc_info *info = get_irg_link(irg);

-       assert(info && "missing call to init_scc");
+       assert(info && "missing call to init_scc()");

        info->dfn = dfn;
 }
 
        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);
        scc_info *info = get_irg_link(irg);

-       assert(info && "missing call to init_scc");
+       assert(info && "missing call to init_scc()");

        return info->dfn;
 }
 
        return info->dfn;
 }
 


@@ -533,9 +521,9 @@ static int tos = 0;                /**< top of stack */
  */
 static INLINE void init_stack(void) {
        if (stack) {
  */
 static INLINE void init_stack(void) {
        if (stack) {

-               ARR_RESIZE (ir_graph *, stack, 1000);
+               ARR_RESIZE(ir_graph *, stack, 1000);

        } else {
        } else {

-               stack = NEW_ARR_F (ir_graph *, 1000);
+               stack = NEW_ARR_F(ir_graph *, 1000);

        }
        tos = 0;
 }
        }
        tos = 0;
 }


@@ -545,9 +533,9 @@ static INLINE void init_stack(void) {
  * @param n the graph to be pushed
  */
 static INLINE void push(ir_graph *irg) {
  * @param n the graph to be pushed
  */
 static INLINE void push(ir_graph *irg) {

-       if (tos == ARR_LEN (stack)) {
-               int nlen = ARR_LEN (stack) * 2;
-               ARR_RESIZE (ir_node *, stack, nlen);
+       if (tos == ARR_LEN(stack)) {
+               int nlen = ARR_LEN(stack) * 2;
+               ARR_RESIZE(ir_node *, stack, nlen);

        }
        stack [tos++] = irg;
        mark_irg_in_stack(irg);
        }
        stack [tos++] = irg;
        mark_irg_in_stack(irg);


@@ -573,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);
                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);
                m->l = current_loop;
                //m->callgraph_loop_depth = current_loop->depth;
        } while(m != irg);


@@ -588,20 +576,19 @@ static void close_loop(ir_loop *l) {
        ir_loop *last_son = lelement.son;
 
        if (get_kind(last_son) == k_ir_loop &&
        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;
 }
 
        current_loop = l;
 }
 


@@ -627,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) {
  * 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;
-       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();
-       son->link    = NULL;
-#endif
+       ir_loop *father = current_loop;
+       ir_loop *son    = alloc_loop(father, outermost_ir_graph->obst);

 
        current_loop = son;
        return father;
 }
 
 
        current_loop = son;
        return father;
 }
 

+

 /**********************************************************************/
 /* Constructing and destructing the loop/backedge information.       **/
 /**********************************************************************/
 
 /* Initialization steps. **********************************************/
 
 /**********************************************************************/
 /* 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;
 
        int i;
        int n_irgs;
 


@@ -673,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);
        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;
        }
                irg->callgraph_recursion_depth = 0;
                irg->callgraph_loop_depth      = 0;
        }


@@ -684,9 +650,7 @@ init_scc(void) {
  *
  *  @param root: only needed for assertion.
  */
  *
  *  @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;
 
        int i, arity;
        int some_outof_loop = 0, some_in_loop = 0;
 


@@ -698,7 +662,6 @@ is_head(ir_graph *n, ir_graph *root)
                        some_outof_loop = 1;
                } else {
                        if (get_irg_uplink(pred) < get_irg_uplink(root))  {
                        some_outof_loop = 1;
                } else {
                        if (get_irg_uplink(pred) < get_irg_uplink(root))  {

-                               DDMG(pred); DDMG(root);

                                assert(get_irg_uplink(pred) >= get_irg_uplink(root));
                        }
                        some_in_loop = 1;
                                assert(get_irg_uplink(pred) >= get_irg_uplink(root));
                        }
                        some_in_loop = 1;


@@ -714,8 +677,7 @@ is_head(ir_graph *n, ir_graph *root)
  * within the loop.
  * @arg root: only needed for assertion.
  */
  * 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;
 {
        int i, arity;
        int some_outof_loop = 0, some_in_loop = 0;


@@ -724,30 +686,29 @@ is_endless_head(ir_graph *n, ir_graph *root)
        for (i = 0; i < arity; i++) {
                ir_graph *pred = get_irg_callee(n, i);
                assert(pred);
        for (i = 0; i < arity; i++) {
                ir_graph *pred = get_irg_callee(n, i);
                assert(pred);

-               if (is_irg_callee_backedge(n, i)) { continue; }
+               if (is_irg_callee_backedge(n, i))
+                       continue;

                if (!irg_is_in_stack(pred)) {
                        some_outof_loop = 1;
                } else {
                if (!irg_is_in_stack(pred)) {
                        some_outof_loop = 1;
                } else {

-                       if(get_irg_uplink(pred) < get_irg_uplink(root)) {
-                               DDMG(pred); DDMG(root);
+                       if (get_irg_uplink(pred) < get_irg_uplink(root)) {

                                assert(get_irg_uplink(pred) >= get_irg_uplink(root));
                        }
                        some_in_loop = 1;
                }
        }
                                assert(get_irg_uplink(pred) >= get_irg_uplink(root));
                        }
                        some_in_loop = 1;
                }
        }

-

        return !some_outof_loop & some_in_loop;
 }
 
        return !some_outof_loop & some_in_loop;
 }
 

-
+#ifdef INTERPROCEDURAL_VIEW

 /**
  * Check whether there is a parallel edge in the ip control flow.
  * Only
  */
 /**
  * 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;
 {
        int is_be = 0;

+

        int iv_rem = get_interprocedural_view();
        set_interprocedural_view(1);
        {
        int iv_rem = get_interprocedural_view();
        set_interprocedural_view(1);
        {


@@ -761,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);
                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)) {
                                ir_graph *ip_pred = get_irn_irg(pred_cfop);
                                //printf("   "); DDMG(ip_pred);
                                if ((ip_pred == pred) && is_backedge(sblock, i)) {


@@ -774,20 +735,21 @@ is_ip_head(ir_graph *n, ir_graph *pred)
        set_interprocedural_view(iv_rem);
        return is_be;
 }
        set_interprocedural_view(iv_rem);
        return is_be;
 }

+#endif /* INTERPROCEDURAL_VIEW */

 
 /**
  * Returns index of the predecessor with the smallest dfn number
  * greater-equal than limit.
  */
 
 /**
  * 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;
 
        int arity = get_irg_n_callees(n);
        for (i = 0; i < arity; i++) {
                ir_graph *pred = get_irg_callee(n, i);
 {
        int i, index = -2, min = -1;
 
        int arity = get_irg_n_callees(n);
        for (i = 0; i < arity; i++) {
                ir_graph *pred = get_irg_callee(n, i);

-               if (is_irg_callee_backedge(n, i) || !irg_is_in_stack(pred)) continue;
+               if (is_irg_callee_backedge(n, i) || !irg_is_in_stack(pred))
+                       continue;

                if (get_irg_dfn(pred) >= limit && (min == -1 || get_irg_dfn(pred) < min)) {
                        index = i;
                        min = get_irg_dfn(pred);
                if (get_irg_dfn(pred) >= limit && (min == -1 || get_irg_dfn(pred) < min)) {
                        index = i;
                        min = get_irg_dfn(pred);


@@ -798,13 +760,11 @@ smallest_dfn_pred(ir_graph *n, int limit)
 }
 
 /** Returns index of the predecessor with the largest dfn number. */
 }
 
 /** Returns index of the predecessor with the largest dfn number. */

-static int
-largest_dfn_pred(ir_graph *n)
-{
+static int largest_dfn_pred(ir_graph *n) {

        int i, index = -2, max = -1;
 
        int arity = get_irg_n_callees(n);
        int i, index = -2, max = -1;
 
        int arity = get_irg_n_callees(n);

-       for (i = 0; i < arity; i++) {
+       for (i = 0; i < arity; ++i) {

                ir_graph *pred = get_irg_callee(n, i);
                if (is_irg_callee_backedge (n, i) || !irg_is_in_stack(pred)) continue;
                if (get_irg_dfn(pred) > max) {
                ir_graph *pred = get_irg_callee(n, i);
                if (is_irg_callee_backedge (n, i) || !irg_is_in_stack(pred)) continue;
                if (get_irg_dfn(pred) > max) {


@@ -816,9 +776,8 @@ largest_dfn_pred(ir_graph *n)
        return index;
 }
 
        return index;
 }
 

-#if 0
-static ir_graph *
-find_tail(ir_graph *n) {
+#ifndef INTERPROCEDURAL_VIEW
+static ir_graph *find_tail(ir_graph *n) {

        ir_graph *m;
        int i, res_index = -2;
 
        ir_graph *m;
        int i, res_index = -2;
 


@@ -836,10 +795,10 @@ find_tail(ir_graph *n) {
                for (i = tos-2; i >= 0; --i) {
                        m = stack[i];
 
                for (i = tos-2; i >= 0; --i) {
                        m = stack[i];
 

-                       if (is_head (m, n)) {
-                               res_index = smallest_dfn_pred (m, get_irg_dfn(m) + 1);
+                       if (is_head(m, n)) {
+                               res_index = smallest_dfn_pred(m, get_irg_dfn(m) + 1);

                                if (res_index == -2)  /* no smallest dfn pred found. */
                                if (res_index == -2)  /* no smallest dfn pred found. */

-                                       res_index = largest_dfn_pred (m);
+                                       res_index = largest_dfn_pred(m);

 
                                if ((m == n) && (res_index == -2)) {
                                        i = -1;
 
                                if ((m == n) && (res_index == -2)) {
                                        i = -1;


@@ -848,7 +807,7 @@ find_tail(ir_graph *n) {
                        }
 
                        /* We should not walk past our selves on the stack:  The upcoming nodes
                        }
 
                        /* 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;
                        if (m == n) {
                                i = -1;
                                break;


@@ -860,10 +819,10 @@ find_tail(ir_graph *n) {
                        /* A dead loop not reachable from Start. */
                        for (i = tos-2; i >= 0; --i) {
                                m = stack[i];
                        /* A dead loop not reachable from Start. */
                        for (i = tos-2; i >= 0; --i) {
                                m = stack[i];

-                               if (is_endless_head (m, n)) {
-                                       res_index = smallest_dfn_pred (m, get_irg_dfn(m) + 1);
+                               if (is_endless_head(m, n)) {
+                                       res_index = smallest_dfn_pred(m, get_irg_dfn(m) + 1);

                                        if (res_index == -2)  /* no smallest dfn pred found. */
                                        if (res_index == -2)  /* no smallest dfn pred found. */

-                                               res_index = largest_dfn_pred (m);
+                                               res_index = largest_dfn_pred(m);

                                        break;
                                }
                                if (m == n) { break; }  /* It's not an unreachable loop, either. */
                                        break;
                                }
                                if (m == n) { break; }  /* It's not an unreachable loop, either. */


@@ -874,12 +833,11 @@ find_tail(ir_graph *n) {
        }
        assert (res_index > -2);
 
        }
        assert (res_index > -2);
 

-       set_irg_callee_backedge (m, res_index);
+       set_irg_callee_backedge(m, res_index);

        return get_irg_callee(m, res_index);
 }
 #else
        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;
 
        ir_graph *m;
        int i, res_index = -2;
 


@@ -895,7 +853,7 @@ find_tail(ir_graph *n) {
                ir_graph *pred = (i < tos -1) ? stack[i+1] : n;
                m = stack[i];
 
                ir_graph *pred = (i < tos -1) ? stack[i+1] : n;
                m = stack[i];
 

-               if (is_head (m, n)) {
+               if (is_head(m, n)) {

                        //printf(" found 1a! "); DDM;
                        in_and_out = m;
                        if (is_ip_head(pred, m)) {
                        //printf(" found 1a! "); DDM;
                        in_and_out = m;
                        if (is_ip_head(pred, m)) {


@@ -936,17 +894,16 @@ find_tail(ir_graph *n) {
 
        //printf("*** head is "); DDMG(m);
 
 
        //printf("*** head is "); DDMG(m);
 

-       res_index = smallest_dfn_pred (m, get_irg_dfn(m) + 1);
+       res_index = smallest_dfn_pred(m, get_irg_dfn(m) + 1);

        if (res_index == -2)  /* no smallest dfn pred found. */
        if (res_index == -2)  /* no smallest dfn pred found. */

-               res_index = largest_dfn_pred (m);
+               res_index = largest_dfn_pred(m);

 
 

-       set_irg_callee_backedge (m, res_index);
+       set_irg_callee_backedge(m, res_index);

        res = get_irg_callee(m, res_index);
        //printf("*** tail is "); DDMG(res);
        return res;
 }
        res = get_irg_callee(m, res_index);
        //printf("*** tail is "); DDMG(res);
        return res;
 }

-#endif
-
+#endif /* INTERPROCEDURAL_VIEW */

 
 /*-----------------------------------------------------------*
  *                   The core algorithm.                     *
 
 /*-----------------------------------------------------------*
  *                   The core algorithm.                     *


@@ -1006,16 +963,16 @@ static void cgscc(ir_graph *n) {
                        ir_loop *l = new_loop();
 
                        /* Remove the cfloop from the stack ... */
                        ir_loop *l = new_loop();
 
                        /* Remove the cfloop from the stack ... */

-                       pop_scc_unmark_visit (n);
+                       pop_scc_unmark_visit(n);

 
                        /* The current backedge has been marked, that is temporarily eliminated,
                           by find tail. Start the scc algorithm
                           anew on the subgraph thats left (the current cfloop without the backedge)
                           in order to find more inner cfloops. */
 
 
                        /* The current backedge has been marked, that is temporarily eliminated,
                           by find tail. Start the scc algorithm
                           anew on the subgraph thats left (the current cfloop without the backedge)
                           in order to find more inner cfloops. */
 

-                       cgscc (tail);
+                       cgscc(tail);

 
 

-                       assert (cg_irg_visited(n));
+                       assert(cg_irg_visited(n));

                        close_loop(l);
                } else {
                        pop_scc_to_loop(n);
                        close_loop(l);
                } else {
                        pop_scc_to_loop(n);


@@ -1034,28 +991,25 @@ static void reset_isbe(void) {
                ir_graph *irg = get_irp_irg(i);
 
                if (irg->caller_isbe)
                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)
                irg->caller_isbe = NULL;
 
                if (irg->callee_isbe)

-                       free(irg->callee_isbe);
+                       xfree(irg->callee_isbe);

                irg->callee_isbe = NULL;
        }
 }
 
                irg->callee_isbe = NULL;
        }
 }
 

-
-
-

 /* ----------------------------------------------------------------------------------- */
 /* 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.                                            */
 /* ----------------------------------------------------------------------------------- */
 
 /* ----------------------------------------------------------------------------------- */
 /* Another algorithm to compute recursion nesting depth                                */
 /* Walk the callgraph.  For each crossed edge increase the loop depth by the edge      */
 /* weight. Assign graphs the maximal depth.                                            */
 /* ----------------------------------------------------------------------------------- */
 

-static void compute_loop_depth (ir_graph *irg, void *env) {
+static void compute_loop_depth(ir_graph *irg, void *env) {

        int current_nesting = *(int *) env;
        int old_nesting = irg->callgraph_loop_depth;
        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 ;
        int i, n_callees;
 
        //return ;


@@ -1133,14 +1087,15 @@ static int in_stack(ana_entry2 *e, ir_loop *g) {
        return 0;
 }
 
        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;
 
        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 -- */
        mark_cg_irg_visited(irg);
 
        /* -- compute and set the new nesting value -- */


@@ -1162,7 +1117,7 @@ static void compute_rec_depth (ir_graph *irg, void *env) {
                /* Don't walk the graph, but a tree that is an unfolded graph.
                   Therefore we unset the visited flag at the end. */
                n_callees = get_irg_n_callees(irg);
                /* Don't walk the graph, but a tree that is an unfolded graph.
                   Therefore we unset the visited flag at the end. */
                n_callees = get_irg_n_callees(irg);

-               for (i = 0; i < n_callees; i++) {
+               for (i = 0; i < n_callees; ++i) {

                        ir_graph *m = get_irg_callee(irg, i);
                        compute_rec_depth(m, env);
                }
                        ir_graph *m = get_irg_callee(irg, i);
                        compute_rec_depth(m, env);
                }


@@ -1184,7 +1139,7 @@ static void compute_rec_depth (ir_graph *irg, void *env) {
 /* ----------------------------------------------------------------------------------- */
 
 /* Returns the method execution frequency of a graph. */
 /* ----------------------------------------------------------------------------------- */
 
 /* Returns the method execution frequency of a graph. */

-double get_irg_method_execution_frequency (ir_graph *irg) {
+double get_irg_method_execution_frequency(ir_graph *irg) {

        return irg->method_execution_frequency;
 }
 
        return irg->method_execution_frequency;
 }
 


@@ -1204,16 +1159,19 @@ static void compute_method_execution_frequency(ir_graph *irg, void *env) {
        double freq;
        int    found_edge;
        int    n_callees;
        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
           one of the unmarked ones. */
        n_callers = get_irg_n_callers(irg);
 
        /* We need the values of all predecessors (except backedges).
           So they must be marked.  Else we will reach the node through
           one of the unmarked ones. */
        n_callers = get_irg_n_callers(irg);

-       for (i = 0; i < n_callers; i++) {
+       for (i = 0; i < n_callers; ++i) {

                ir_graph *m = get_irg_caller(irg, 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;
                }
                if (!cg_irg_visited(m)) {
                        return;
                }


@@ -1242,7 +1200,7 @@ static void compute_method_execution_frequency(ir_graph *irg, void *env) {
 
        /* recur */
        n_callees = get_irg_n_callees(irg);
 
        /* recur */
        n_callees = get_irg_n_callees(irg);

-       for (i = 0; i < n_callees; i++) {
+       for (i = 0; i < n_callees; ++i) {

                compute_method_execution_frequency(get_irg_callee(irg, i), NULL);
        }
 }
                compute_method_execution_frequency(get_irg_callee(irg, i), NULL);
        }
 }


@@ -1255,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();
 /* Compute the backedges that represent recursions. */
 void find_callgraph_recursions(void) {
        int i, n_irgs = get_irp_n_irgs();

+       struct obstack temp;

 
        reset_isbe();
 
 
        reset_isbe();
 


@@ -1266,27 +1225,31 @@ 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();
        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 */
 
 
        current_loop = NULL;
        new_loop();  /* sets current_loop */
 

-       master_cg_visited++;
+       ++master_cg_visited;

        cgscc(outermost_ir_graph);
        cgscc(outermost_ir_graph);

-       for (i = 0; i < n_irgs; i++) {
+       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)
                        cgscc(irg);
        }
                ir_graph *irg = get_irp_irg(i);
                if (!cg_irg_visited(irg) && get_irg_n_callers(irg) == 0)
                        cgscc(irg);
        }

-       for (i = 0; i < n_irgs; i++) {
+       for (i = 0; i < n_irgs; ++i) {

                ir_graph *irg = get_irp_irg(i);
                if (!cg_irg_visited(irg))
                        cgscc(irg);
        }
                ir_graph *irg = get_irp_irg(i);
                if (!cg_irg_visited(irg))
                        cgscc(irg);
        }

+       obstack_free(&temp, NULL);
+

        irp->outermost_cg_loop = current_loop;
        irp->outermost_cg_loop = current_loop;

+       mature_loops(current_loop, outermost_ir_graph->obst);

 
        /* -- Reverse the backedge information. -- */
 
        /* -- Reverse the backedge information. -- */

-       for (i = 0; i < n_irgs; i++) {
+       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) {
                ir_graph *irg = get_irp_irg(i);
                int j, n_callees = get_irg_n_callees(irg);
                for (j = 0; j < n_callees; ++j) {


@@ -1310,21 +1273,21 @@ void compute_performance_estimates(void) {
        current_nesting = 0;
        irp->max_callgraph_loop_depth = 0;
        master_cg_visited += 2;
        current_nesting = 0;
        irp->max_callgraph_loop_depth = 0;
        master_cg_visited += 2;

-       //printf (" ** starting at      "); DDMG(get_irp_main_irg());
+       //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);
        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);
+                               //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);
                }
        }
        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);
+                       //printf(" ** starting at      "); DDMG(irg);

                }
        }
 
                }
        }
 


@@ -1338,20 +1301,20 @@ void compute_performance_estimates(void) {
 
        master_cg_visited += 2;
        compute_rec_depth(get_irp_main_irg(), &e);
 
        master_cg_visited += 2;
        compute_rec_depth(get_irp_main_irg(), &e);

-       //printf (" ++ starting at "); DDMG(get_irp_main_irg());
+       //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);
        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);
+                               //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);
                }
        }
        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);
+                       //printf(" ++ starting at "); DDMG(irg);

                }
        }
 
                }
        }
 


@@ -1413,7 +1376,6 @@ void analyse_loop_nesting_depth(void) {
        set_irp_loop_nesting_depth_state(loop_nesting_depth_consistent);
 }
 
        set_irp_loop_nesting_depth_state(loop_nesting_depth_consistent);
 }
 

-

 loop_nesting_depth_state get_irp_loop_nesting_depth_state(void) {
        return irp->lnd_state;
 }
 loop_nesting_depth_state get_irp_loop_nesting_depth_state(void) {
        return irp->lnd_state;
 }