/*
- * 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-2007 Universität Karlsruhe
- * Licence: This file protected by GPL - GNU GENERAL PUBLIC LICENSE.
+ * Copyright (C) 1995-2008 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
+ * @version $Id$
*/
#ifdef HAVE_CONFIG_H
# include "config.h"
#include "array.h"
#include "pmap.h"
#include "hashptr.h"
+#include "raw_bitset.h"
#include "irgwalk.h"
/* 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) {
- 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. */
/* 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) {
- irg->caller_isbe[i] = 1;
+ rbitset_set(irg->caller_isbe, i);
break;
}
}
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;
}
/* 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) {
- 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. */
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;
}
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)
- 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) {
- 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;
}
static void ana_Call(ir_node *n, void *env) {
int i, n_callees;
ir_graph *irg;
+ (void) env;
if (! is_Call(n)) return;
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();
if (cg_irg_visited(irg)) return;
mark_cg_irg_visited(irg);
- pre(irg, env);
+ if (pre)
+ pre(irg, env);
n_callees = get_irg_n_callees(irg);
for (i = 0; i < n_callees; i++) {
do_walk(m, pre, post, env);
}
- post(irg, env);
+ if (post)
+ post(irg, env);
}
void callgraph_walk(callgraph_walk_func *pre, callgraph_walk_func *post, void *env) {
static int current_dfn = 1; /**< Counter to generate depth first numbering
of visited nodes. */
-
/*-----------------*/
/* Node attributes */
/*-----------------*/
* allocates a new scc_info of the obstack
*/
static INLINE scc_info *new_scc_info(void) {
- scc_info *info = obstack_alloc (outermost_ir_graph->obst, sizeof(*info));
+ scc_info *info = obstack_alloc(outermost_ir_graph->obst, sizeof(*info));
memset(info, 0, sizeof(*info));
return info;
}
static INLINE int
cg_irg_visited(ir_graph *irg) {
scc_info *info = get_irg_link(irg);
- return (info->visited >= master_cg_visited);
+ assert(info && "missing call to init_scc");
+ return info->visited >= master_cg_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
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 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 void
mark_irg_in_stack(ir_graph *irg) {
scc_info *info = get_irg_link(irg);
- assert(info);
+ 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);
+ 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);
+ 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);
+ 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);
+ 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);
+ 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);
+ assert(info && "missing call to init_scc");
return info->dfn;
}
*/
static INLINE void init_stack(void) {
if (stack) {
- ARR_RESIZE (ir_graph *, stack, 1000);
+ ARR_RESIZE(ir_graph *, stack, 1000);
} else {
- stack = NEW_ARR_F (ir_graph *, 1000);
+ stack = NEW_ARR_F(ir_graph *, 1000);
}
tos = 0;
}
* @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);
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->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);
#ifdef DEBUG_libfirm
son->loop_nr = get_irp_new_node_nr();
- son->link = NULL;
#endif
current_loop = son;
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;
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(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;
return !some_outof_loop & some_in_loop;
}
-
+#ifdef INTERPROCEDURAL_VIEW
/**
* Check whether there is a parallel edge in the ip control flow.
* Only
is_ip_head(ir_graph *n, ir_graph *pred)
{
int is_be = 0;
+
int iv_rem = get_interprocedural_view();
set_interprocedural_view(1);
{
set_interprocedural_view(iv_rem);
return is_be;
}
+#endif /* INTERPROCEDURAL_VIEW */
/**
* Returns index of the predecessor with the smallest dfn number
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);
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) {
return index;
}
-#if 0
+#ifndef INTERPROCEDURAL_VIEW
static ir_graph *
find_tail(ir_graph *n) {
ir_graph *m;
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. */
- res_index = largest_dfn_pred (m);
+ res_index = largest_dfn_pred(m);
if ((m == n) && (res_index == -2)) {
i = -1;
/* 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. */
- res_index = largest_dfn_pred (m);
+ res_index = largest_dfn_pred(m);
break;
}
if (m == n) { break; } /* It's not an unreachable loop, either. */
}
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
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("*** 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. */
- 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;
}
-#endif
-
+#endif /* INTERPROCEDURAL_VIEW */
/*-----------------------------------------------------------*
* The core algorithm. *
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. */
- cgscc (tail);
+ cgscc(tail);
- assert (cg_irg_visited(n));
+ assert(cg_irg_visited(n));
close_loop(l);
} else {
pop_scc_to_loop(n);
}
}
-
-
-
/* ----------------------------------------------------------------------------------- */
/* 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 old_visited = get_cg_irg_visited(irg);
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;
/* 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);
}
/* ----------------------------------------------------------------------------------- */
/* 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;
}
double freq;
int found_edge;
int n_callees;
+ (void) env;
if (cg_irg_visited(irg)) return;
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);
if (is_irg_caller_backedge(irg, i)) continue;
if (!cg_irg_visited(m)) {
/* 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);
}
}
master_cg_visited++;
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);
}
- 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);
irp->outermost_cg_loop = current_loop;
/* -- 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) {
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(), ¤t_nesting);
for (i = 0; i < n_irgs; i++) {
ir_graph *irg = get_irp_irg(i);
if ((get_cg_irg_visited(irg) < master_cg_visited-1) &&
get_irg_n_callers(irg) == 0) {
compute_loop_depth(irg, ¤t_nesting);
- //printf (" ** starting at "); DDMG(irg);
+ //printf(" ** starting at "); DDMG(irg);
}
}
for (i = 0; i < n_irgs; i++) {
ir_graph *irg = get_irp_irg(i);
if (get_cg_irg_visited(irg) < master_cg_visited-1) {
compute_loop_depth(irg, ¤t_nesting);
- //printf (" ** starting at "); DDMG(irg);
+ //printf(" ** starting at "); DDMG(irg);
}
}
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);
- //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);
- //printf (" ++ starting at "); DDMG(irg);
+ //printf(" ++ starting at "); DDMG(irg);
}
}
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;
}