/*
- * Project: libFIRM
- * File name: ir/ana/callgraph.c
- * Purpose: Representation and computation of the callgraph.
- * Author: Goetz Lindenmaier
- * Modified by:
- * Created: 21.7.2004
- * CVS-ID: $Id$
- * Copyright: (c) 2004 Universität Karlsruhe
- * Licence: This file protected by GPL - GNU GENERAL PUBLIC LICENSE.
+ * Copyright (C) 1995-2011 University of Karlsruhe. All right reserved.
+ *
+ * This file is part of libFirm.
+ *
+ * This file may be distributed and/or modified under the terms of the
+ * GNU General Public License version 2 as published by the Free Software
+ * Foundation and appearing in the file LICENSE.GPL included in the
+ * packaging of this file.
+ *
+ * Licensees holding valid libFirm Professional Edition licenses may use
+ * this file in accordance with the libFirm Commercial License.
+ * Agreement provided with the Software.
+ *
+ * This file is provided AS IS with NO WARRANTY OF ANY KIND, INCLUDING THE
+ * WARRANTY OF DESIGN, MERCHANTABILITY AND FITNESS FOR A PARTICULAR
+ * PURPOSE.
*/
+/**
+ * @file
+ * @brief Representation and computation of the callgraph.
+ * @author Goetz Lindenmaier
+ * @date 21.7.2004
+ */
#include "config.h"
+
+#include <string.h>
+#include <stdlib.h>
+
#include "callgraph.h"
#include "irloop_t.h"
#include "irgraph_t.h"
#include "irnode_t.h"
+#include "cgana.h"
+
#include "array.h"
#include "pmap.h"
+#include "hashptr.h"
+#include "raw_bitset.h"
#include "irgwalk.h"
-/* The functions that call irg. */
-int get_irg_n_callers(ir_graph *irg) {
- if (irg->callers) return ARR_LEN(irg->callers);
- return -1;
+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)
+{
+ return irp->callgraph_state;
}
-ir_graph *get_irg_caller(ir_graph *irg, int pos) {
- assert (pos >= 0 && pos < get_irg_n_callers(irg));
- if (irg->callers) return irg->callers[pos];
- return NULL;
+
+/* Sets the callgraph state of the program representation. */
+void set_irp_callgraph_state(irp_callgraph_state s)
+{
+ irp->callgraph_state = s;
}
-int is_irg_caller_backedge(ir_graph *irg, int pos) {
- assert (pos >= 0 && pos < get_irg_n_callers(irg));
- return irg->caller_isbe[pos];
+
+/* Returns the number of procedures that call the given irg. */
+size_t get_irg_n_callers(const ir_graph *irg)
+{
+ assert(irg->callers);
+ return irg->callers ? ARR_LEN(irg->callers) : 0;
}
-static void set_irg_caller_backedge(ir_graph *irg, int pos) {
- assert (pos >= 0 && pos < get_irg_n_callers(irg));
- irg->caller_isbe[pos] = 1;
+
+/* Returns the caller at position pos. */
+ir_graph *get_irg_caller(const ir_graph *irg, size_t pos)
+{
+ assert(pos < get_irg_n_callers(irg));
+ return irg->callers ? irg->callers[pos] : NULL;
}
-/* The functions called by irg. */
-int get_irg_n_callees(ir_graph *irg) {
- if (irg->callees) return ARR_LEN(irg->callees);
- return -1;
+/* Returns non-zero if the caller at position pos is "a backedge", i.e. a recursion. */
+int is_irg_caller_backedge(const ir_graph *irg, size_t pos)
+{
+ assert(pos < get_irg_n_callers(irg));
+ return irg->caller_isbe != NULL ? rbitset_is_set(irg->caller_isbe, pos) : 0;
}
-ir_graph *get_irg_callee(ir_graph *irg, int pos) {
- assert (pos >= 0 && pos < get_irg_n_callees(irg));
- if (irg->callees) return irg->callees[pos];
- return NULL;
+
+/** Search the caller in the list of all callers and set its backedge property. */
+static void set_irg_caller_backedge(ir_graph *irg, const ir_graph *caller)
+{
+ size_t i, n_callers = get_irg_n_callers(irg);
+
+ /* allocate a new array on demand */
+ if (irg->caller_isbe == NULL)
+ irg->caller_isbe = rbitset_malloc(n_callers);
+ for (i = 0; i < n_callers; ++i) {
+ if (get_irg_caller(irg, i) == caller) {
+ rbitset_set(irg->caller_isbe, i);
+ break;
+ }
+ }
}
-int is_irg_callee_backedge(ir_graph *irg, int pos) {
- assert (pos >= 0 && pos < get_irg_n_callees(irg));
- return irg->callee_isbe[pos];
+
+/* Returns non-zero if the irg has a backedge caller. */
+int has_irg_caller_backedge(const ir_graph *irg)
+{
+ size_t i, n_callers = get_irg_n_callers(irg);
+
+ if (irg->caller_isbe != NULL) {
+ for (i = 0; i < n_callers; ++i)
+ if (rbitset_is_set(irg->caller_isbe, i))
+ return 1;
+ }
+ return 0;
}
-void set_irg_callee_backedge(ir_graph *irg, int pos) {
- assert (pos >= 0 && pos < get_irg_n_callees(irg));
- irg->callee_isbe[pos] = 1;
+
+/**
+ * Find the reversion position of a caller.
+ * Given the position pos_caller of an caller of irg, return
+ * irg's callee position on that caller.
+ */
+static size_t reverse_pos(const ir_graph *callee, size_t pos_caller)
+{
+ ir_graph *caller = get_irg_caller(callee, pos_caller);
+ /* search the other relation for the corresponding edge. */
+ size_t i, n_callees = get_irg_n_callees(caller);
+ for (i = 0; i < n_callees; ++i) {
+ if (get_irg_callee(caller, i) == callee) {
+ return i;
+ }
+ }
+
+ assert(!"reverse_pos() did not find position");
+
+ return 0;
}
+/* Returns the maximal loop depth of call nodes that call along this edge. */
+size_t get_irg_caller_loop_depth(const ir_graph *irg, size_t pos)
+{
+ ir_graph *caller = get_irg_caller(irg, pos);
+ size_t pos_callee = reverse_pos(irg, pos);
-static void ana_Call(ir_node *n, void *env) {
- int i, n_callees;
- ir_graph *irg;
+ return get_irg_callee_loop_depth(caller, pos_callee);
+}
- if (get_irn_op(n) != op_Call) return;
- irg = get_irn_irg(n);
- n_callees = get_Call_n_callees(n);
- for (i = 0; i < n_callees; ++i) {
- entity *callee_e = get_Call_callee(n, i);
- if (callee_e) {
- ir_graph *callee = get_entity_irg(callee_e);
- pset_insert((pset *)irg->callees, callee, (unsigned)callee >> 3);
- pset_insert((pset *)callee->callers, irg, (unsigned)irg >> 3);
- }
- }
+/* Returns the number of procedures that are called by the given irg. */
+size_t get_irg_n_callees(const ir_graph *irg)
+{
+ assert(irg->callees);
+ return irg->callees ? ARR_LEN(irg->callees) : 0;
}
+/* Returns the callee at position pos. */
+ir_graph *get_irg_callee(const ir_graph *irg, size_t pos)
+{
+ assert(pos < get_irg_n_callees(irg));
+ return irg->callees ? irg->callees[pos]->irg : NULL;
+}
-/* compare two ir graphs */
-static int graph_cmp(const void *elt, const void *key) {
- return elt != key;
+/* Returns non-zero if the callee at position pos is "a backedge", i.e. a recursion. */
+int is_irg_callee_backedge(const ir_graph *irg, size_t pos)
+{
+ assert(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(const ir_graph *irg)
+{
+ size_t i, n_callees = get_irg_n_callees(irg);
+
+ if (irg->callee_isbe != NULL) {
+ for (i = 0; i < n_callees; ++i)
+ if (rbitset_is_set(irg->callee_isbe, i))
+ return 1;
+ }
+ return 0;
+}
+
+/**
+ * Mark the callee at position pos as a backedge.
+ */
+static void set_irg_callee_backedge(ir_graph *irg, size_t pos)
+{
+ size_t n = get_irg_n_callees(irg);
+
+ /* allocate a new array on demand */
+ if (irg->callee_isbe == NULL)
+ irg->callee_isbe = rbitset_malloc(n);
+ assert(pos < n);
+ rbitset_set(irg->callee_isbe, pos);
+}
+
+/* Returns the maximal loop depth of call nodes that call along this edge. */
+size_t get_irg_callee_loop_depth(const ir_graph *irg, size_t pos)
+{
+ assert(pos < get_irg_n_callees(irg));
+ return irg->callees ? irg->callees[pos]->max_depth : 0;
+}
+
+
+/* --------------------- Compute the callgraph ------------------------ */
+
+/**
+ * Pre-Walker called by compute_callgraph(), analyses all Call nodes.
+ */
+static void ana_Call(ir_node *n, void *env)
+{
+ size_t i, n_callees;
+ ir_graph *irg;
+ (void) env;
+
+ if (! is_Call(n)) return;
+
+ irg = get_irn_irg(n);
+ n_callees = get_Call_n_callees(n);
+ for (i = 0; i < n_callees; ++i) {
+ ir_entity *callee_e = get_Call_callee(n, i);
+ ir_graph *callee = get_entity_irg(callee_e);
+
+ if (callee) {
+ cg_callee_entry buf;
+ cg_callee_entry *found;
+ unsigned depth;
+
+ buf.irg = callee;
+
+ pset_insert((pset *)callee->callers, irg, HASH_PTR(irg));
+ 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 = OALLOC(irg->obst, cg_callee_entry);
+ found->irg = callee;
+ found->call_list = NEW_ARR_F(ir_node *, 1);
+ found->call_list[0] = n;
+ found->max_depth = 0;
+ pset_insert((pset *)irg->callees, found, HASH_PTR(callee));
+ }
+ depth = get_loop_depth(get_irn_loop(get_nodes_block(n)));
+ found->max_depth = (depth > found->max_depth) ? depth : found->max_depth;
+ }
+ }
+}
+
+/** compare two ir graphs in a cg_callee_entry */
+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 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) {
- int i, n_irgs = get_irp_n_irgs();
-
- assert(interprocedural_view == 0); /* Else walking will not reach the Call nodes. */
-
- /* initialize */
- free_callgraph();
- for (i = 0; i < n_irgs; ++i) {
- ir_graph *irg = get_irp_irg(i);
- assert(get_irg_callee_info_state(irg) == irg_callee_info_consistent);
- irg->callees = (ir_graph **)new_pset(graph_cmp, 8);
- irg->callers = (ir_graph **)new_pset(graph_cmp, 8);
- }
-
- /* Compute the call graph */
- for (i = 0; i < n_irgs; ++i) {
- ir_graph *irg = get_irp_irg(i);
- irg_walk_graph(irg, ana_Call, NULL, NULL);
- }
-
- /* Change the sets to arrays. */
- for (i = 0; i < n_irgs; ++i) {
- int j, count;
- ir_graph *c, *irg = get_irp_irg(i);
-
- pset *callee_set = (pset *)irg->callees;
- count = pset_count(callee_set);
- irg->callees = NEW_ARR_F(ir_graph *, count);
- irg->callee_isbe = calloc(count, sizeof(int));
- c = pset_first(callee_set);
- for (j = 0; j < count; ++j) {
- irg->callees[j] = c;
- c = pset_next(callee_set);
- }
- del_pset(callee_set);
- assert(c == NULL);
-
- pset *caller_set = (pset *)irg->callers;
- count = pset_count(caller_set);
- irg->callers = NEW_ARR_F(ir_graph *, count);
- irg->caller_isbe = calloc(count, sizeof(int));
- c = pset_first(caller_set);
- for (j = 0; j < count; ++j) {
- irg->callers[j] = c;
- c = pset_next(caller_set);
- }
- del_pset(caller_set);
- assert(c == NULL);
- }
-}
-
-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);
- if (irg->callees) DEL_ARR_F(irg->callees);
- if (irg->callers) DEL_ARR_F(irg->callers);
- if (irg->callee_isbe) DEL_ARR_F(irg->callee_isbe);
- if (irg->caller_isbe) DEL_ARR_F(irg->caller_isbe);
- irg->callees = NULL;
- irg->callers = NULL;
- irg->callee_isbe = NULL;
- irg->caller_isbe = NULL;
- }
+void compute_callgraph(void)
+{
+ size_t i, n_irgs;
+
+ /* initialize */
+ free_callgraph();
+
+ n_irgs = get_irp_n_irgs();
+ for (i = 0; i < n_irgs; ++i) {
+ ir_graph *irg = get_irp_irg(i);
+ assert(get_irg_callee_info_state(irg) == irg_callee_info_consistent);
+ irg->callees = (cg_callee_entry **)new_pset(cg_callee_entry_cmp, 8);
+ irg->callers = (ir_graph **)new_pset(graph_cmp, 8);
+ //construct_cf_backedges(irg);
+ }
+
+ /* Compute the call graph */
+ for (i = 0; i < n_irgs; ++i) {
+ ir_graph *irg = get_irp_irg(i);
+ construct_cf_backedges(irg); // We also find the maximal loop depth of a call.
+ irg_walk_graph(irg, ana_Call, NULL, NULL);
+ }
+
+ /* Change the sets to arrays. */
+ for (i = 0; i < n_irgs; ++i) {
+ size_t j, count;
+ cg_callee_entry *callee;
+ ir_graph *c, *irg = get_irp_irg(i);
+ pset *callee_set, *caller_set;
+
+ callee_set = (pset *)irg->callees;
+ count = pset_count(callee_set);
+ irg->callees = NEW_ARR_F(cg_callee_entry *, count);
+ irg->callee_isbe = NULL;
+ callee = (cg_callee_entry*) pset_first(callee_set);
+ for (j = 0; j < count; ++j) {
+ irg->callees[j] = callee;
+ callee = (cg_callee_entry*) pset_next(callee_set);
+ }
+ del_pset(callee_set);
+ assert(callee == NULL);
+
+ caller_set = (pset *)irg->callers;
+ count = pset_count(caller_set);
+ irg->callers = NEW_ARR_F(ir_graph *, count);
+ irg->caller_isbe = NULL;
+ c = (ir_graph*) pset_first(caller_set);
+ for (j = 0; j < count; ++j) {
+ irg->callers[j] = c;
+ c = (ir_graph*) pset_next(caller_set);
+ }
+ del_pset(caller_set);
+ assert(c == NULL);
+ }
+ set_irp_callgraph_state(irp_callgraph_consistent);
}
+/* Destruct the callgraph. */
+void free_callgraph(void)
+{
+ size_t i, n_irgs = get_irp_n_irgs();
+ for (i = 0; i < n_irgs; ++i) {
+ ir_graph *irg = get_irp_irg(i);
+ if (irg->callees) DEL_ARR_F(irg->callees);
+ if (irg->callers) DEL_ARR_F(irg->callers);
+ if (irg->callee_isbe) free(irg->callee_isbe);
+ if (irg->caller_isbe) free(irg->caller_isbe);
+ irg->callees = NULL;
+ irg->callers = NULL;
+ irg->callee_isbe = NULL;
+ irg->caller_isbe = NULL;
+ }
+ set_irp_callgraph_state(irp_callgraph_none);
+}
/* ----------------------------------------------------------------------------------- */
-/* loop construction algorithm */
+/* A walker for the callgraph */
/* ----------------------------------------------------------------------------------- */
-static ir_graph *outermost_ir_graph; /* The outermost graph the scc is computed
- for */
-static ir_loop *current_loop; /* Current cfloop construction is working
- on. */
-static int loop_node_cnt = 0; /* Counts the number of allocated cfloop nodes.
- Each cfloop node gets a unique number.
- What for? ev. remove. @@@ */
-static int current_dfn = 1; /* Counter to generate depth first numbering
- of visited nodes. */
+static void do_walk(ir_graph *irg, callgraph_walk_func *pre, callgraph_walk_func *post, void *env)
+{
+ size_t i, n_callees;
+
+ if (cg_irg_visited(irg))
+ return;
+ mark_cg_irg_visited(irg);
-/**********************************************************************/
-/* Node attributes **/
-/**********************************************************************/
+ if (pre)
+ pre(irg, env);
+
+ n_callees = get_irg_n_callees(irg);
+ for (i = 0; i < n_callees; i++) {
+ ir_graph *m = get_irg_callee(irg, i);
+ do_walk(m, pre, post, env);
+ }
+
+ if (post)
+ post(irg, env);
+}
+
+void callgraph_walk(callgraph_walk_func *pre, callgraph_walk_func *post, void *env)
+{
+ size_t i, n_irgs = get_irp_n_irgs();
+ ++master_cg_visited;
+
+ /* 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 (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);
+ do_walk(irg, pre, post, env);
+ }
+}
+
+/* ----------------------------------------------------------------------------------- */
+/* loop construction algorithm */
+/* ----------------------------------------------------------------------------------- */
+
+static ir_graph *outermost_ir_graph; /**< The outermost graph the scc is computed
+ for */
+static ir_loop *current_loop; /**< Current cfloop construction is working
+ on. */
+static size_t loop_node_cnt = 0; /**< Counts the number of allocated cfloop nodes.
+ Each cfloop node gets a unique number.
+ What for? ev. remove. @@@ */
+static size_t current_dfn = 1; /**< Counter to generate depth first numbering
+ of visited nodes. */
+
+/*-----------------*/
+/* Node attributes */
+/*-----------------*/
typedef struct scc_info {
- bool in_stack; /* Marks whether node is on the stack. */
- int dfn; /* Depth first search number. */
- int uplink; /* dfn number of ancestor. */
- int visited;
+ size_t dfn; /**< Depth first search number. */
+ size_t uplink; /**< dfn number of ancestor. */
+ ir_visited_t visited; /**< visited counter */
+ int in_stack; /**< Marks whether node is on the stack. */
} scc_info;
-static INLINE scc_info* new_scc_info(void) {
- scc_info *info = obstack_alloc (outermost_ir_graph->obst, sizeof (scc_info));
- memset (info, 0, sizeof (scc_info));
- return info;
+/**
+ * allocates a new scc_info on the obstack
+ */
+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)
+{
+ return irg->self_visited >= master_cg_visited;
}
-static INLINE int
-cg_irg_visited(ir_graph *n) {
- return ((scc_info *)n->link)->visited;
+/**
+ * Marks a graph as visited.
+ */
+static inline void mark_cg_irg_visited(ir_graph *irg)
+{
+ irg->self_visited = master_cg_visited;
}
-static INLINE void
-mark_cg_irg_visited(ir_graph *n) {
- ((scc_info *)n->link)->visited = 1;
+/**
+ * Set a graphs visited flag to i.
+ */
+static inline void set_cg_irg_visited(ir_graph *irg, ir_visited_t i)
+{
+ irg->self_visited = i;
}
-static INLINE void
-set_cg_irg_visited(ir_graph *n, int i) {
- ((scc_info *)n->link)->visited = i;
+/**
+ * Returns the visited flag of a graph.
+ */
+static inline ir_visited_t get_cg_irg_visited(const ir_graph *irg)
+{
+ return irg->self_visited;
}
-static INLINE void
-mark_irg_in_stack (ir_graph *n) {
- assert(get_irg_link(n));
- ((scc_info *)n->link)->in_stack = true;
+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 *n) {
- assert(get_irg_link(n));
- ((scc_info *)n->link)->in_stack = false;
+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 bool
-irg_is_in_stack (ir_graph *n) {
- assert(get_irg_link(n));
- return ((scc_info *)n->link)->in_stack;
+static inline int irg_is_in_stack(const 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 *n, int uplink) {
- assert(get_irg_link(n));
- ((scc_info *)n->link)->uplink = uplink;
+static inline void set_irg_uplink(ir_graph *irg, size_t 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 *n) {
- assert(get_irg_link(n));
- return ((scc_info *)n->link)->uplink;
+static inline size_t get_irg_uplink(const ir_graph *irg)
+{
+ const 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 *n, int dfn) {
- assert(get_irg_link(n));
- ((scc_info *)n->link)->dfn = dfn;
+static inline void set_irg_dfn(ir_graph *irg, size_t 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 *n) {
- assert(get_irg_link(n));
- return ((scc_info *)n->link)->dfn;
+static inline size_t get_irg_dfn(const ir_graph *irg)
+{
+ const scc_info *info = (scc_info*) get_irg_link(irg);
+ assert(info && "missing call to init_scc()");
+ return info->dfn;
}
/**********************************************************************/
/**********************************************************************/
static ir_graph **stack = NULL;
-static int tos = 0; /* top of stack */
+static size_t tos = 0; /**< top of stack */
-static INLINE void init_stack(void) {
- if (stack) {
- ARR_RESIZE (ir_graph *, stack, 1000);
- } else {
- stack = NEW_ARR_F (ir_graph *, 1000);
- }
- tos = 0;
+/**
+ * Initialize the irg stack.
+ */
+static inline void init_stack(void)
+{
+ if (stack) {
+ ARR_RESIZE(ir_graph *, stack, 1000);
+ } else {
+ stack = NEW_ARR_F(ir_graph *, 1000);
+ }
+ tos = 0;
}
-
-static INLINE void
-push (ir_graph *n)
+/**
+ * push a graph on the irg stack
+ * @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);
- }
- stack [tos++] = n;
- mark_irg_in_stack(n);
+ if (tos == ARR_LEN(stack)) {
+ size_t nlen = ARR_LEN(stack) * 2;
+ ARR_RESIZE(ir_graph*, stack, nlen);
+ }
+ stack [tos++] = irg;
+ mark_irg_in_stack(irg);
}
-static INLINE ir_graph *
-pop (void)
+/**
+ * return the topmost graph on the stack and pop it
+ */
+static inline ir_graph *pop(void)
{
- ir_graph *n = stack[--tos];
- mark_irg_not_in_stack(n);
- return n;
+ ir_graph *irg;
+
+ assert(tos > 0);
+ irg = stack[--tos];
+ mark_irg_not_in_stack(irg);
+ return irg;
}
-/* The nodes up to n 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 *n)
+/**
+ * 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)
{
- ir_graph *m;
+ ir_graph *m;
- /*for (;;) {*/
- do {
- m = pop();
- loop_node_cnt++;
- set_irg_dfn(m, loop_node_cnt);
- add_loop_node(current_loop, (ir_node *)m);
- set_irg_loop(m, current_loop);
- /* if (m==n) break;*/
- } while(m != n);
+ do {
+ m = pop();
+ ++loop_node_cnt;
+ set_irg_dfn(m, loop_node_cnt);
+ add_loop_irg(current_loop, m);
+ m->l = current_loop;
+ //m->callgraph_loop_depth = current_loop->depth;
+ } 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;
-
- 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;
- }
- }
-
- current_loop = l;
+ size_t 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;
+
+ 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;
+ }
+ }
+ current_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)
+/**
+ * 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)
{
- ir_graph *m = NULL;
+ ir_graph *m = NULL;
- while (m != n) {
- m = pop();
- set_cg_irg_visited(m, 0);
- }
+ while (m != n) {
+ m = pop();
+ set_cg_irg_visited(m, 0);
+ }
}
/**********************************************************************/
-/* The loop datastructure. **/
+/* The loop data structure. **/
/**********************************************************************/
-/* 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 = (ir_loop *) obstack_alloc (outermost_ir_graph->obst, sizeof (ir_loop));
- memset (son, 0, sizeof (ir_loop));
- 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
-
- current_loop = son;
- return father;
+/**
+ * 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 = 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 INLINE void
-init_scc (ir_graph *irg) {
- int i;
- current_dfn = 1;
- loop_node_cnt = 0;
- init_stack();
- for (i = 0; i < get_irp_n_irgs(); ++i) {
- set_irg_link(get_irp_irg(i), new_scc_info());
- }
+static void init_scc(struct obstack *obst)
+{
+ size_t i, n_irgs;
+
+ current_dfn = 1;
+ loop_node_cnt = 0;
+ init_stack();
+
+ 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(obst));
+ irg->callgraph_recursion_depth = 0;
+ irg->callgraph_loop_depth = 0;
+ }
}
-/** Returns true if n is a loop header, i.e., it is a Block node
+/** Returns non-zero if n is a loop header, i.e., it is a Block node
* and has predecessors within the cfloop and out of the cfloop.
*
* @param root: only needed for assertion.
*/
-static bool
-is_head (ir_graph *n, ir_graph *root)
-{
- int i, arity;
- int some_outof_loop = 0, some_in_loop = 0;
-
- 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)) continue;
- if (!irg_is_in_stack(pred)) {
- 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;
- }
- }
-
- return some_outof_loop && some_in_loop;
-}
-/* Returns true if n is possible loop head of an endless loop.
- I.e., it is a Block, Phi or Filter node and has only predecessors
- within the loop.
- @arg root: only needed for assertion. */
-static bool
-is_endless_head (ir_graph *n, ir_graph *root)
-{
- int i, arity;
- int some_outof_loop = 0, some_in_loop = 0;
-
- arity = get_irg_n_callees(n);
- 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 (!irg_is_in_stack(pred)) {
- 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;
- }
- }
-
- return !some_outof_loop && some_in_loop;
-}
-
-/* Returns index of the predecessor with the smallest dfn number
- greater-equal than 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);
- 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);
- }
- }
-
- return index;
-}
-
-/* Returns index of the predecessor with the largest dfn number. */
-static int
-largest_dfn_pred (ir_graph *n)
-{
- int i, index = -2, max = -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 (get_irg_dfn(pred) > max) {
- index = i;
- max = get_irg_dfn(pred);
- }
- }
-
- return index;
-}
-
-static ir_graph *
-find_tail (ir_graph *n) {
- ir_graph *m;
- int i, res_index = -2;
-
- /*
- if (!icfg && rm_cyclic_phis && remove_cyclic_phis (n)) return NULL;
- */
- m = stack[tos-1]; /* tos = top of stack */
- if (is_head (m, n)) {
- res_index = smallest_dfn_pred(m, 0);
- if ((res_index == -2) && /* no smallest dfn pred found. */
- (n == m))
- return NULL;
- } else {
- if (m == n) return NULL; // Is this to catch Phi - self loops?
- 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 (res_index == -2) /* no smallest dfn pred found. */
- res_index = largest_dfn_pred (m);
-
- if ((m == n) && (res_index == -2)) {
- i = -1;
- }
- break;
- }
-
- /* We should not walk past our selves on the stack: The upcoming nodes
- are not in this loop. We assume a loop not reachable from Start. */
- if (m == n) {
- i = -1;
- break;
- }
-
- }
-
- if (i < 0) {
- /* A dead loop not reachable from Start. */
- for (i = tos-2; i >= 0; --i) {
- m = stack[i];
- if (is_endless_head (m, n)) {
- res_index = smallest_dfn_pred (m, get_irg_dfn(m) + 1);
- if (res_index == -2) /* no smallest dfn pred found. */
- res_index = largest_dfn_pred (m);
- break;
+static int is_head(const ir_graph *n, const ir_graph *root)
+{
+ size_t i, n_callees;
+ int some_outof_loop = 0, some_in_loop = 0;
+
+ n_callees = get_irg_n_callees(n);
+ for (i = 0; i < n_callees; ++i) {
+ const ir_graph *pred = get_irg_callee(n, i);
+ if (is_irg_callee_backedge(n, i)) continue;
+ if (!irg_is_in_stack(pred)) {
+ some_outof_loop = 1;
+ } else {
+ if (get_irg_uplink(pred) < get_irg_uplink(root)) {
+ assert(get_irg_uplink(pred) >= get_irg_uplink(root));
+ }
+ some_in_loop = 1;
+ }
}
- if (m == n) { break; } /* It's not an unreachable loop, either. */
- }
- //assert(0 && "no head found on stack");
- }
-
- }
- assert (res_index > -2);
- set_irg_callee_backedge (m, res_index);
- return get_irg_callee(m, res_index);
+ 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 or Phi node and has only predecessors
+ * within the loop.
+ * @arg root: only needed for assertion.
+ */
+static int is_endless_head(const ir_graph *n, const ir_graph *root)
+{
+ size_t i, n_calless;
+ int some_outof_loop = 0, some_in_loop = 0;
+
+ n_calless = get_irg_n_callees(n);
+ for (i = 0; i < n_calless; ++i) {
+ const ir_graph *pred = get_irg_callee(n, i);
+ assert(pred);
+ if (is_irg_callee_backedge(n, i))
+ continue;
+ if (!irg_is_in_stack(pred)) {
+ some_outof_loop = 1;
+ } else {
+ if (get_irg_uplink(pred) < get_irg_uplink(root)) {
+ assert(get_irg_uplink(pred) >= get_irg_uplink(root));
+ }
+ some_in_loop = 1;
+ }
+ }
+ return !some_outof_loop && some_in_loop;
+}
+/**
+ * Finds index of the predecessor with the smallest dfn number
+ * greater-equal than limit.
+ */
+static bool smallest_dfn_pred(const ir_graph *n, size_t limit, size_t *result)
+{
+ size_t index = 0, min = 0;
+ bool found = false;
+
+ size_t i, n_callees = get_irg_n_callees(n);
+ for (i = 0; i < n_callees; ++i) {
+ const 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) >= limit && (!found || get_irg_dfn(pred) < min)) {
+ index = i;
+ min = get_irg_dfn(pred);
+ found = true;
+ }
+ }
-/*-----------------------------------------------------------*
- * The core algorithm. *
- *-----------------------------------------------------------*/
+ *result = index;
+ return found;
+}
+/** Finds index of the predecessor with the largest dfn number. */
+static bool largest_dfn_pred(const ir_graph *n, size_t *result)
+{
+ size_t index = 0, max = 0;
+ bool found = false;
+
+ size_t i, n_callees = get_irg_n_callees(n);
+ for (i = 0; i < n_callees; ++i) {
+ const ir_graph *pred = get_irg_callee(n, i);
+ if (is_irg_callee_backedge (n, i) || !irg_is_in_stack(pred))
+ continue;
+ /* Note: dfn is always > 0 */
+ if (get_irg_dfn(pred) > max) {
+ index = i;
+ max = get_irg_dfn(pred);
+ found = true;
+ }
+ }
-static void cgscc (ir_graph *n) {
- int i;
+ *result = index;
+ return found;
+}
- if (cg_irg_visited(n)) return;
- mark_cg_irg_visited(n);
+static ir_graph *find_tail(const ir_graph *n)
+{
+ bool found = false;
+ ir_graph *m;
+ size_t i, res_index;
+
+ /*
+ if (!icfg && rm_cyclic_phis && remove_cyclic_phis (n)) return NULL;
+ */
+ m = stack[tos - 1]; /* tos = top of stack */
+ if (is_head(m, n)) {
+ found = smallest_dfn_pred(m, 0, &res_index);
+ if (!found && /* no smallest dfn pred found. */
+ n == m)
+ return NULL;
+ } else {
+ if (m == n) return NULL; // Is this to catch Phi - self loops?
+ for (i = tos - 1; i > 0;) {
+ m = stack[--i];
+
+ if (is_head(m, n)) {
+ found = smallest_dfn_pred(m, get_irg_dfn(m) + 1, &res_index);
+ if (! found) /* no smallest dfn pred found. */
+ found = largest_dfn_pred(m, &res_index);
+
+ break;
+ }
+
+ /* We should not walk past our selves on the stack: The upcoming nodes
+ are not in this loop. We assume a loop not reachable from Start. */
+ if (m == n) {
+ found = false;
+ break;
+ }
+
+ }
+
+ if (! found) {
+ /* A dead loop not reachable from Start. */
+ for (i = tos-1; i > 0;) {
+ m = stack[--i];
+ if (is_endless_head(m, n)) {
+ found = smallest_dfn_pred(m, get_irg_dfn(m) + 1, &res_index);
+ if (!found) /* no smallest dfn pred found. */
+ found = largest_dfn_pred(m, &res_index);
+ break;
+ }
+ /* It's not an unreachable loop, either. */
+ if (m == n)
+ break;
+ }
+ //assert(0 && "no head found on stack");
+ }
- /* Initialize the node */
- set_irg_dfn(n, current_dfn); /* Depth first number for this node */
- set_irg_uplink(n, current_dfn); /* ... is default uplink. */
- set_irg_loop(n, NULL);
- current_dfn ++;
- push(n);
+ }
+ assert(found);
- int arity = get_irg_n_callees(n);
+ set_irg_callee_backedge(m, res_index);
+ return get_irg_callee(m, res_index);
+}
- for (i = 0; i < arity; i++) {
- ir_graph *m;
- if (is_irg_callee_backedge(n, i)) continue;
- m = get_irg_callee(n, i);
+/*-----------------------------------------------------------*
+ * The core algorithm. *
+ *-----------------------------------------------------------*/
- /** This marks the backedge, but does it guarantee a correct loop tree? */
- if (m == n) { set_irg_callee_backedge(n, i); continue; }
- 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. */
- if (get_irg_uplink(m) < get_irg_uplink(n))
- set_irg_uplink(n, get_irg_uplink(m));
- }
- }
+static void cgscc(ir_graph *n)
+{
+ size_t i, n_callees;
+
+ if (cg_irg_visited(n)) return;
+ mark_cg_irg_visited(n);
+
+ /* Initialize the node */
+ set_irg_dfn(n, current_dfn); /* Depth first number for this node */
+ set_irg_uplink(n, current_dfn); /* ... is default uplink. */
+ ++current_dfn;
+ push(n);
+
+ n_callees = get_irg_n_callees(n);
+ for (i = 0; i < n_callees; ++i) {
+ ir_graph *m;
+ if (is_irg_callee_backedge(n, i)) continue;
+ m = get_irg_callee(n, i);
+
+ /** This marks the backedge, but does it guarantee a correct loop tree? */
+ //if (m == n) { set_irg_callee_backedge(n, i); continue; }
+
+ 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. */
+ if (get_irg_uplink(m) < get_irg_uplink(n))
+ set_irg_uplink(n, get_irg_uplink(m));
+ }
+ }
- if (get_irg_dfn(n) == get_irg_uplink(n)) {
- /* This condition holds for
- 1) the node with the incoming backedge.
- That is: We found a cfloop!
- 2) Straight line code, because no uplink has been propagated, so the
- uplink still is the same as the dfn.
+ if (get_irg_dfn(n) == get_irg_uplink(n)) {
+ /* This condition holds for
+ 1) the node with the incoming backedge.
+ That is: We found a cfloop!
+ 2) Straight line code, because no uplink has been propagated, so the
+ uplink still is the same as the dfn.
- But n might not be a proper cfloop head for the analysis. Proper cfloop
- heads are Block and Phi nodes. find_tail searches the stack for
- Block's and Phi's and takes those nodes as cfloop heads for the current
- cfloop instead and marks the incoming edge as backedge. */
+ But n might not be a proper cfloop head for the analysis. Proper cfloop
+ heads are Block and Phi nodes. find_tail searches the stack for
+ Block's and Phi's and takes those nodes as cfloop heads for the current
+ cfloop instead and marks the incoming edge as backedge. */
- ir_graph *tail = find_tail(n);
- if (tail) {
- /* We have a cfloop, that is no straight line code,
- because we found a cfloop head!
- Next actions: Open a new cfloop on the cfloop tree and
- try to find inner cfloops */
+ ir_graph *tail = find_tail(n);
+ if (tail) {
+ /* We have a cfloop, that is no straight line code,
+ because we found a cfloop head!
+ Next actions: Open a new cfloop on the cfloop tree and
+ try to find inner cfloops */
- ir_loop *l = new_loop();
+ ir_loop *l = new_loop();
- /* Remove the cfloop from the stack ... */
- pop_scc_unmark_visit (n);
+ /* Remove the cfloop from the stack ... */
+ 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));
- close_loop(l);
- } else {
- pop_scc_to_loop(n);
- }
- }
+ assert(cg_irg_visited(n));
+ close_loop(l);
+ } else {
+ pop_scc_to_loop(n);
+ }
+ }
}
+/**
+ * reset the backedge information for all callers in all irgs
+ */
+static void reset_isbe(void)
+{
+ size_t i, n_irgs = get_irp_n_irgs();
-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);
- for (i = 0; i < n_irgs; ++i) {
- int j, n_cs;
- ir_graph *irg = get_irp_irg(i);
+ if (irg->caller_isbe)
+ xfree(irg->caller_isbe);
+ irg->caller_isbe = NULL;
- n_cs = get_irg_n_callers(irg);
- for (j = 0; j < n_cs; ++j) {
- irg->caller_isbe[j] = 0;
- }
- n_cs = get_irg_n_callees(irg);
- for (j = 0; j < n_cs; ++j) {
- irg->callee_isbe[j] = 0;
- }
- }
+ if (irg->callee_isbe)
+ xfree(irg->callee_isbe);
+ irg->callee_isbe = NULL;
+ }
}
+/* ----------------------------------------------------------------------------------- */
+/* The recursion stuff driver. */
+/* ----------------------------------------------------------------------------------- */
+
/* Compute the backedges that represent recursions. */
-void find_callgraph_recursions(void) {
- int i, n_irgs = get_irp_n_irgs();
+void find_callgraph_recursions(void)
+{
+ size_t i, n_irgs;
+ struct obstack temp;
+
+ reset_isbe();
+
+ /* -- compute the looptree. -- */
+
+ /* The outermost graph. We start here. Then we start at all
+ functions in irg list that are never called, then at the remaining
+ unvisited ones. The third step is needed for functions that are not
+ reachable from the outermost graph, but call themselves in a cycle. */
+ assert(get_irp_main_irg());
+ outermost_ir_graph = get_irp_main_irg();
+ obstack_init(&temp);
+ init_scc(&temp);
+
+ current_loop = NULL;
+ new_loop(); /* sets current_loop */
+
+ ++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)
+ cgscc(irg);
+ }
+ for (i = 0; i < n_irgs; ++i) {
+ ir_graph *irg = get_irp_irg(i);
+ 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) {
+ ir_graph *irg = get_irp_irg(i);
+ size_t j, n_callees = get_irg_n_callees(irg);
+ for (j = 0; j < n_callees; ++j) {
+ if (is_irg_callee_backedge(irg, j))
+ set_irg_caller_backedge(get_irg_callee(irg, j), irg);
+ }
+ }
- reset_isbe();
+ irp->callgraph_state = irp_callgraph_and_calltree_consistent;
+}
- assert(get_irp_main_irg()); /* The outermost graph. We start here. Then we start at all
- external visible functions in irg list, then at the remaining
- unvisited ones. */
- outermost_ir_graph = get_irp_main_irg();
+/* Returns the maximal loop depth of all paths from an external visible method to
+ this irg. */
+size_t 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;
+}
- assert(!interprocedural_view &&
- "use construct_ip_backedges");
+/* Returns the maximal recursion depth of all paths from an external visible method to
+ this irg. */
+size_t 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)
+{
+ /* establish preconditions. */
+ if (get_irp_callee_info_state() != irg_callee_info_consistent) {
+ ir_entity **free_methods = NULL;
- init_scc(current_ir_graph);
+ cgana(&free_methods);
+ xfree(free_methods);
+ }
- current_loop = NULL;
- new_loop(); /* sets current_loop */
+ if (irp_callgraph_consistent != get_irp_callgraph_state()) {
+ compute_callgraph();
+ }
- cgscc(outermost_ir_graph);
+ find_callgraph_recursions();
- 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);
- }
- for (i = 0; i < n_irgs; i++) {
- ir_graph *irg = get_irp_irg(i);
- if (!cg_irg_visited(irg))
- cgscc(irg);
- }
+ set_irp_loop_nesting_depth_state(loop_nesting_depth_consistent);
+}
- /* We can not use the looptree -- it has no real meaning.
- There is a working dumper, but commented out.
- assert(current_loop && current_loop == get_loop_outer_loop(current_loop));
- dump_callgraph_loop_tree(current_loop, ""); */
+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)
+{
+ irp->lnd_state = s;
+}
+void set_irp_loop_nesting_depth_state_inconsistent(void)
+{
+ if (irp->lnd_state == loop_nesting_depth_consistent)
+ irp->lnd_state = loop_nesting_depth_inconsistent;
}