* @date 21.7.2004
* @version $Id$
*/
-#ifdef HAVE_CONFIG_H
-# include "config.h"
-#endif
+#include "config.h"
-#ifdef HAVE_STRING_H
-# include <string.h>
-#endif
-# ifdef HAVE_STDLIB_H
+#include <string.h>
#include <stdlib.h>
-#endif
#include "callgraph.h"
#include "irgwalk.h"
-static int master_cg_visited = 0;
-static INLINE int cg_irg_visited (ir_graph *n);
-static INLINE void mark_cg_irg_visited(ir_graph *n);
-static INLINE void set_cg_irg_visited (ir_graph *n, int i);
+static ir_visited_t master_cg_visited = 0;
+static inline int cg_irg_visited (ir_graph *n);
+static inline void mark_cg_irg_visited(ir_graph *n);
+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 number of procedures that call the given irg. */
-int get_irg_n_callers(ir_graph *irg) {
+int get_irg_n_callers(const ir_graph *irg) {
if (irg->callers) return ARR_LEN(irg->callers);
return -1;
}
/* Returns the caller at position pos. */
-ir_graph *get_irg_caller(ir_graph *irg, int pos) {
+ir_graph *get_irg_caller(const ir_graph *irg, int pos) {
assert(pos >= 0 && pos < get_irg_n_callers(irg));
if (irg->callers) return irg->callers[pos];
return NULL;
}
/* Returns non-zero if the caller at position pos is "a backedge", i.e. a recursion. */
-int is_irg_caller_backedge(ir_graph *irg, int pos) {
+int is_irg_caller_backedge(const ir_graph *irg, int pos) {
assert(pos >= 0 && pos < get_irg_n_callers(irg));
return irg->caller_isbe != NULL ? rbitset_is_set(irg->caller_isbe, pos) : 0;
}
}
/* Returns non-zero if the irg has a backedge caller. */
-int has_irg_caller_backedge(ir_graph *irg) {
+int has_irg_caller_backedge(const ir_graph *irg) {
int i, n_callers = get_irg_n_callers(irg);
if (irg->caller_isbe != NULL) {
* Given the position pos_caller of an caller of irg, return
* irg's callee position on that caller.
*/
-static int reverse_pos(ir_graph *callee, int pos_caller) {
+static int reverse_pos(const ir_graph *callee, int pos_caller) {
ir_graph *caller = get_irg_caller(callee, pos_caller);
/* search the other relation for the corresponding edge. */
int pos_callee = -1;
}
/* Returns the maximal loop depth of call nodes that call along this edge. */
-int get_irg_caller_loop_depth(ir_graph *irg, int pos) {
+int get_irg_caller_loop_depth(const ir_graph *irg, int pos) {
ir_graph *caller = get_irg_caller(irg, pos);
int pos_callee = reverse_pos(irg, pos);
/* Returns the number of procedures that are called by the given irg. */
-int get_irg_n_callees(ir_graph *irg) {
+int get_irg_n_callees(const ir_graph *irg) {
if (irg->callees) return ARR_LEN(irg->callees);
return -1;
}
/* Returns the callee at position pos. */
-ir_graph *get_irg_callee(ir_graph *irg, int pos) {
+ir_graph *get_irg_callee(const ir_graph *irg, int pos) {
assert(pos >= 0 && pos < get_irg_n_callees(irg));
if (irg->callees) return irg->callees[pos]->irg;
return NULL;
}
/* Returns non-zero if the callee at position pos is "a backedge", i.e. a recursion. */
-int is_irg_callee_backedge(ir_graph *irg, int pos) {
+int is_irg_callee_backedge(const ir_graph *irg, int pos) {
assert(pos >= 0 && pos < get_irg_n_callees(irg));
return irg->callee_isbe != NULL ? rbitset_is_set(irg->callee_isbe, pos) : 0;
}
/* Returns non-zero if the irg has a backedge callee. */
-int has_irg_callee_backedge(ir_graph *irg) {
+int has_irg_callee_backedge(const ir_graph *irg) {
int i, n_callees = get_irg_n_callees(irg);
if (irg->callee_isbe != NULL) {
}
/* Returns the maximal loop depth of call nodes that call along this edge. */
-int get_irg_callee_loop_depth(ir_graph *irg, int pos) {
+int get_irg_callee_loop_depth(const ir_graph *irg, int pos) {
assert(pos >= 0 && pos < get_irg_n_callees(irg));
if (irg->callees) return irg->callees[pos]->max_depth;
return -1;
}
-double get_irg_callee_execution_frequency(ir_graph *irg, int pos) {
+double get_irg_callee_execution_frequency(const ir_graph *irg, int pos) {
ir_node **arr = irg->callees[pos]->call_list;
int i, n_Calls = ARR_LEN(arr);
double freq = 0.0;
return freq;
}
-double get_irg_callee_method_execution_frequency(ir_graph *irg, int pos) {
+double get_irg_callee_method_execution_frequency(const ir_graph *irg, int pos) {
double call_freq = get_irg_callee_execution_frequency(irg, pos);
double meth_freq = get_irg_method_execution_frequency(irg);
return call_freq * meth_freq;
}
-double get_irg_caller_method_execution_frequency(ir_graph *irg, int pos) {
+double get_irg_caller_method_execution_frequency(const ir_graph *irg, int pos) {
ir_graph *caller = get_irg_caller(irg, pos);
int pos_callee = reverse_pos(irg, pos);
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 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)
void callgraph_walk(callgraph_walk_func *pre, callgraph_walk_func *post, void *env) {
int i, n_irgs = get_irp_n_irgs();
- master_cg_visited++;
+ ++master_cg_visited;
- do_walk(get_irp_main_irg(), pre, post, env);
- for (i = 0; i < n_irgs; i++) {
+ /* roots are methods which have no callers in the current program */
+ for (i = 0; i < n_irgs; ++i) {
ir_graph *irg = get_irp_irg(i);
- if (!cg_irg_visited(irg) && get_irg_n_callers(irg) == 0)
+
+ if (get_irg_n_callers(irg) == 0)
do_walk(irg, pre, post, env);
}
+
+ /* in case of unreachable call loops we haven't visited some irgs yet */
for (i = 0; i < n_irgs; i++) {
ir_graph *irg = get_irp_irg(i);
- if (!cg_irg_visited(irg))
- do_walk(irg, pre, post, env);
+ do_walk(irg, pre, post, env);
}
}
} 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;
}
/**
* Returns non-zero if a graph was already visited.
*/
-static INLINE int
-cg_irg_visited(ir_graph *irg) {
- scc_info *info = get_irg_link(irg);
- assert(info && "missing call to init_scc");
- return info->visited >= master_cg_visited;
+static inline int cg_irg_visited(ir_graph *irg) {
+ return irg->self_visited >= master_cg_visited;
}
/**
* Marks a graph as visited.
*/
-static INLINE void
-mark_cg_irg_visited(ir_graph *irg) {
- scc_info *info = get_irg_link(irg);
- assert(info && "missing call to init_scc");
- info->visited = master_cg_visited;
+static inline void mark_cg_irg_visited(ir_graph *irg) {
+ irg->self_visited = master_cg_visited;
}
/**
* Set a graphs visited flag to i.
*/
-static INLINE void
-set_cg_irg_visited(ir_graph *irg, int i) {
- scc_info *info = get_irg_link(irg);
- assert(info && "missing call to init_scc");
- info->visited = i;
+static inline void set_cg_irg_visited(ir_graph *irg, ir_visited_t i) {
+ irg->self_visited = i;
}
/**
* Returns the visited flag of a graph.
*/
-static INLINE int
-get_cg_irg_visited(ir_graph *irg) {
- scc_info *info = get_irg_link(irg);
- assert(info && "missing call to init_scc");
- return info->visited;
+static inline ir_visited_t get_cg_irg_visited(ir_graph *irg) {
+ return irg->self_visited;
}
-static INLINE void
-mark_irg_in_stack(ir_graph *irg) {
+static inline void mark_irg_in_stack(ir_graph *irg) {
scc_info *info = get_irg_link(irg);
- assert(info && "missing call to init_scc");
+ assert(info && "missing call to init_scc()");
info->in_stack = 1;
}
-static INLINE void
-mark_irg_not_in_stack(ir_graph *irg) {
+static inline void mark_irg_not_in_stack(ir_graph *irg) {
scc_info *info = get_irg_link(irg);
- assert(info && "missing call to init_scc");
+ assert(info && "missing call to init_scc()");
info->in_stack = 0;
}
-static INLINE int
-irg_is_in_stack(ir_graph *irg) {
+static inline int irg_is_in_stack(ir_graph *irg) {
scc_info *info = get_irg_link(irg);
- assert(info && "missing call to init_scc");
+ assert(info && "missing call to init_scc()");
return info->in_stack;
}
-static INLINE void
-set_irg_uplink(ir_graph *irg, int uplink) {
+static inline void set_irg_uplink(ir_graph *irg, int uplink) {
scc_info *info = get_irg_link(irg);
- assert(info && "missing call to init_scc");
+ assert(info && "missing call to init_scc()");
info->uplink = uplink;
}
-static INLINE int
-get_irg_uplink(ir_graph *irg) {
+static inline int get_irg_uplink(ir_graph *irg) {
scc_info *info = get_irg_link(irg);
- assert(info && "missing call to init_scc");
+ assert(info && "missing call to init_scc()");
return info->uplink;
}
-static INLINE void
-set_irg_dfn(ir_graph *irg, int dfn) {
+static inline void set_irg_dfn(ir_graph *irg, int dfn) {
scc_info *info = get_irg_link(irg);
- assert(info && "missing call to init_scc");
+ assert(info && "missing call to init_scc()");
info->dfn = dfn;
}
-static INLINE int
-get_irg_dfn(ir_graph *irg) {
+static inline int get_irg_dfn(ir_graph *irg) {
scc_info *info = get_irg_link(irg);
- assert(info && "missing call to init_scc");
+ assert(info && "missing call to init_scc()");
return info->dfn;
}
/**
* Initialize the irg stack.
*/
-static INLINE void init_stack(void) {
+static inline void init_stack(void) {
if (stack) {
ARR_RESIZE(ir_graph *, stack, 1000);
} else {
* push a graph on the irg stack
* @param n the graph to be pushed
*/
-static INLINE void push(ir_graph *irg) {
+static inline void push(ir_graph *irg) {
if (tos == ARR_LEN(stack)) {
int nlen = ARR_LEN(stack) * 2;
ARR_RESIZE(ir_node *, stack, nlen);
/**
* return the topmost graph on the stack and pop it
*/
-static INLINE ir_graph *pop(void) {
+static inline ir_graph *pop(void) {
ir_graph *irg = stack[--tos];
mark_irg_not_in_stack(irg);
return irg;
* The nodes up to irg belong to the current loop.
* Removes them from the stack and adds them to the current loop.
*/
-static INLINE void pop_scc_to_loop(ir_graph *irg) {
+static inline void pop_scc_to_loop(ir_graph *irg) {
ir_graph *m;
do {
m = pop();
loop_node_cnt++;
set_irg_dfn(m, loop_node_cnt);
- add_loop_node(current_loop, (ir_node *)m);
+ add_loop_irg(current_loop, m);
m->l = current_loop;
//m->callgraph_loop_depth = current_loop->depth;
} while(m != irg);
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;
}
* Removes and unmarks all nodes up to n from the stack.
* The nodes must be visited once more to assign them to a scc.
*/
-static INLINE void pop_scc_unmark_visit(ir_graph *n) {
+static inline void pop_scc_unmark_visit(ir_graph *n) {
ir_graph *m = NULL;
while (m != n) {
* to the new loop and returns the father.
*/
static ir_loop *new_loop(void) {
- ir_loop *father, *son;
-
- father = current_loop;
-
- son = obstack_alloc(outermost_ir_graph->obst, sizeof(*son));
- memset(son, 0, sizeof(*son));
- son->kind = k_ir_loop;
- son->children = NEW_ARR_F(loop_element, 0);
- son->n_nodes = 0;
- son->n_sons = 0;
- son->link = NULL;
- if (father) {
- son->outer_loop = father;
- add_loop_son(father, son);
- son->depth = father->depth + 1;
- } else { /* The root loop */
- son->outer_loop = son;
- son->depth = 0;
- }
-
-#ifdef DEBUG_libfirm
- son->loop_nr = get_irp_new_node_nr();
-#endif
+ ir_loop *father = current_loop;
+ ir_loop *son = alloc_loop(father, outermost_ir_graph->obst);
current_loop = son;
return father;
}
+
/**********************************************************************/
/* Constructing and destructing the loop/backedge information. **/
/**********************************************************************/
/* Initialization steps. **********************************************/
-static void
-init_scc(void) {
+static void init_scc(struct obstack *obst) {
int i;
int n_irgs;
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;
}
*
* @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;
* 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;
some_in_loop = 1;
}
}
-
return !some_outof_loop & some_in_loop;
}
* 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;
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)) {
* 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;
}
/** 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);
}
#ifndef INTERPROCEDURAL_VIEW
-static ir_graph *
-find_tail(ir_graph *n) {
+static ir_graph *find_tail(ir_graph *n) {
ir_graph *m;
int i, res_index = -2;
}
/* 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;
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;
/** This marks the backedge, but does it guarantee a correct loop tree? */
//if (m == n) { set_irg_callee_backedge(n, i); continue; }
- cgscc (m);
+ cgscc(m);
if (irg_is_in_stack(m)) {
/* Uplink of m is smaller if n->m is a backedge.
Propagate the uplink to mark the cfloop. */
ir_graph *irg = get_irp_irg(i);
if (irg->caller_isbe)
- free(irg->caller_isbe);
+ xfree(irg->caller_isbe);
irg->caller_isbe = NULL;
if (irg->callee_isbe)
- free(irg->callee_isbe);
+ xfree(irg->callee_isbe);
irg->callee_isbe = NULL;
}
}
static void compute_loop_depth(ir_graph *irg, void *env) {
int current_nesting = *(int *) env;
int old_nesting = irg->callgraph_loop_depth;
- int old_visited = get_cg_irg_visited(irg);
+ ir_visited_t old_visited = get_cg_irg_visited(irg);
int i, n_callees;
//return ;
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 -- */
/* ----------------------------------------------------------------------------------- */
/* Returns the method execution frequency of a graph. */
-double get_irg_method_execution_frequency(ir_graph *irg) {
+double get_irg_method_execution_frequency(const ir_graph *irg) {
return irg->method_execution_frequency;
}
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
n_callers = get_irg_n_callers(irg);
for (i = 0; i < n_callers; ++i) {
ir_graph *m = get_irg_caller(irg, i);
- if (is_irg_caller_backedge(irg, i)) continue;
+ if (is_irg_caller_backedge(irg, i))
+ continue;
if (!cg_irg_visited(m)) {
return;
}
/* Compute the backedges that represent recursions. */
void find_callgraph_recursions(void) {
- int i, n_irgs = get_irp_n_irgs();
+ int i, n_irgs;
+ struct obstack temp;
reset_isbe();
reachable from the outermost graph, but call themselves in a cycle. */
assert(get_irp_main_irg());
outermost_ir_graph = get_irp_main_irg();
- init_scc();
+ obstack_init(&temp);
+ init_scc(&temp);
current_loop = NULL;
new_loop(); /* sets current_loop */
- master_cg_visited++;
+ ++master_cg_visited;
cgscc(outermost_ir_graph);
+ n_irgs = get_irp_n_irgs();
for (i = 0; i < n_irgs; ++i) {
ir_graph *irg = get_irp_irg(i);
if (!cg_irg_visited(irg) && get_irg_n_callers(irg) == 0)
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) {
/* Returns the maximal loop depth of all paths from an external visible method to
this irg. */
-int get_irg_loop_depth(ir_graph *irg) {
+int get_irg_loop_depth(const ir_graph *irg) {
assert(irp->callgraph_state == irp_callgraph_consistent ||
irp->callgraph_state == irp_callgraph_and_calltree_consistent);
return irg->callgraph_loop_depth;
/* Returns the maximal recursion depth of all paths from an external visible method to
this irg. */
-int get_irg_recursion_depth(ir_graph *irg) {
+int get_irg_recursion_depth(const ir_graph *irg) {
assert(irp->callgraph_state == irp_callgraph_and_calltree_consistent);
return irg->callgraph_recursion_depth;
}
projects / libfirm / blobdiff