* Copyright: (c) 2004 Universität Karlsruhe
* Licence: This file protected by GPL - GNU GENERAL PUBLIC LICENSE.
*/
+#ifdef HAVE_CONFIG_H
+# include "config.h"
+#endif
+
+#ifdef HAVE_STRING_H
+# include <string.h>
+#endif
+# ifdef HAVE_STDLIB_H
+#include <stdlib.h>
+#endif
-#include "config.h"
#include "callgraph.h"
#include "irloop_t.h"
#include "irnode_t.h"
#include "cgana.h"
+#include "execution_frequency.h"
#include "array.h"
#include "pmap.h"
+#include "hashptr.h"
#include "irgwalk.h"
/* For callees, we want to remember the Call nodes, too. */
struct ana_entry {
- ir_graph *irg;
- ir_node *call_list;
- int max_depth;
+ ir_graph *irg;
+ ir_node **call_list;
+ int max_depth;
};
typedef struct ana_entry ana_entry;
return 0;
}
-int get_irg_caller_loop_depth(ir_graph *irg, int pos) {
- ir_graph *caller = get_irg_caller(irg, pos);
-
+static int reverse_pos(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;
int i, n_callees = get_irg_n_callees(caller);
for (i = 0; i < n_callees; ++i) {
- if (get_irg_callee(caller, i) == irg) {
+ if (get_irg_callee(caller, i) == callee) {
pos_callee = i;
break;
}
assert(pos_callee >= 0);
+ return pos_callee;
+}
+
+int get_irg_caller_loop_depth(ir_graph *irg, int pos) {
+ ir_graph *caller = get_irg_caller(irg, pos);
+ int pos_callee = reverse_pos(irg, pos);
+
return get_irg_callee_loop_depth(caller, pos_callee);
}
return -1;
}
-/* --------------------- Compute the callgraph ------------------------ */
-/* Hash an address */
-#define HASH_ADDRESS(adr) (((unsigned)(adr)) >> 3)
+
+double get_irg_callee_execution_frequency(ir_graph *irg, int pos) {
+ ir_node **arr = ((ana_entry *)irg->callees[pos])->call_list;
+ int i, n_Calls = ARR_LEN(arr);
+ double freq = 0;
+
+ for (i = 0; i < n_Calls; ++i) {
+ freq += get_irn_exec_freq(arr[i]);
+ }
+ return freq;
+}
+
+double get_irg_callee_method_execution_frequency(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) {
+ ir_graph *caller = get_irg_caller(irg, pos);
+ int pos_callee = reverse_pos(irg, pos);
+
+ return get_irg_callee_method_execution_frequency(caller, pos_callee);
+}
+
+
+
+/* --------------------- Compute the callgraph ------------------------ */
/**
* Walker called by compute_callgraph()
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 != unknown_entity) { /* For unknown caller */
- ir_graph *callee = get_entity_irg(callee_e);
- pset_insert((pset *)callee->callers, irg, HASH_ADDRESS(irg));
+ ir_graph *callee = get_entity_irg(callee_e);
+ if (callee) {
ana_entry buf = { callee, NULL, 0};
- ana_entry *found = pset_find((pset *)irg->callees, &buf, HASH_ADDRESS(callee));
+ ana_entry *found;
+ int depth;
+
+ pset_insert((pset *)callee->callers, irg, HASH_PTR(irg));
+ found = 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 = (ana_entry *) obstack_alloc (irg->obst, sizeof (ana_entry));
found->irg = callee;
- found->call_list = NULL;
+ 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_ADDRESS(callee));
+ pset_insert((pset *)irg->callees, found, HASH_PTR(callee));
}
- int depth = get_loop_depth(get_irn_loop(get_nodes_block(n)));
+ depth = get_loop_depth(get_irn_loop(get_nodes_block(n)));
found->max_depth = (depth > found->max_depth) ? depth : found->max_depth;
}
}
assert(get_irg_callee_info_state(irg) == irg_callee_info_consistent);
irg->callees = (ir_graph **)new_pset(ana_entry_cmp, 8);
irg->callers = (ir_graph **)new_pset(graph_cmp, 8);
- construct_cf_backedges(irg);
+ //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);
+ construct_cf_backedges(irg); // We also find the maximal loop depth of a call.
irg_walk_graph(irg, ana_Call, NULL, NULL);
}
for (i = 0; i < n_irgs; ++i) {
int j, count;
ir_graph *c, *irg = get_irp_irg(i);
+ pset *callee_set, *caller_set;
- pset *callee_set = (pset *)irg->callees;
+ 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));
+ irg->callee_isbe = xcalloc(count, sizeof(irg->callee_isbe[0]));
c = pset_first(callee_set);
for (j = 0; j < count; ++j) {
irg->callees[j] = c;
del_pset(callee_set);
assert(c == NULL);
- pset *caller_set = (pset *)irg->callers;
+ 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));
+ irg->caller_isbe = xcalloc(count, sizeof(irg->caller_isbe[0]));
c = pset_first(caller_set);
for (j = 0; j < count; ++j) {
irg->callers[j] = c;
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);
+ 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;
/* loop construction algorithm */
/* ----------------------------------------------------------------------------------- */
-static ir_graph *outermost_ir_graph; /* The outermost graph the scc is computed
+static ir_graph *outermost_ir_graph; /**< The outermost graph the scc is computed
for */
-static ir_loop *current_loop; /* Current cfloop construction is working
+static ir_loop *current_loop; /**< Current cfloop construction is working
on. */
-static int loop_node_cnt = 0; /* Counts the number of allocated cfloop nodes.
+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
+static int current_dfn = 1; /**< Counter to generate depth first numbering
of visited nodes. */
/**********************************************************************/
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 in_stack; /**< Marks whether node is on the stack. */
+ int dfn; /**< Depth first search number. */
+ int uplink; /**< dfn number of ancestor. */
int visited;
} 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));
+/**
+ * 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));
+ memset(info, 0, sizeof(*info));
return info;
}
static INLINE int
cg_irg_visited(ir_graph *n) {
- return (((scc_info *)n->link)->visited >= master_cg_visited);
+ scc_info *info = get_irg_link(n);
+ return (info->visited >= master_cg_visited);
}
static INLINE void
mark_cg_irg_visited(ir_graph *n) {
- ((scc_info *)n->link)->visited = master_cg_visited;
+ scc_info *info = get_irg_link(n);
+ info->visited = master_cg_visited;
}
static INLINE void
set_cg_irg_visited(ir_graph *n, int i) {
- ((scc_info *)n->link)->visited = i;
+ scc_info *info = get_irg_link(n);
+ info->visited = i;
}
static INLINE int
get_cg_irg_visited(ir_graph *n) {
- return ((scc_info *)n->link)->visited;
+ scc_info *info = get_irg_link(n);
+ return info->visited;
}
static INLINE void
mark_irg_in_stack (ir_graph *n) {
- assert(get_irg_link(n));
- ((scc_info *)n->link)->in_stack = true;
+ scc_info *info = get_irg_link(n);
+ assert(info);
+ 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;
+ scc_info *info = get_irg_link(n);
+ assert(info);
+ info->in_stack = 0;
}
-static INLINE bool
+static INLINE int
irg_is_in_stack (ir_graph *n) {
- assert(get_irg_link(n));
- return ((scc_info *)n->link)->in_stack;
+ scc_info *info = get_irg_link(n);
+ assert(info);
+ 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;
+ scc_info *info = get_irg_link(n);
+ assert(info);
+ info->uplink = uplink;
}
static INLINE int
get_irg_uplink (ir_graph *n) {
- assert(get_irg_link(n));
- return ((scc_info *)n->link)->uplink;
+ scc_info *info = get_irg_link(n);
+ assert(info);
+ 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;
+ scc_info *info = get_irg_link(n);
+ assert(info);
+ info->dfn = dfn;
}
static INLINE int
get_irg_dfn (ir_graph *n) {
- assert(get_irg_link(n));
- return ((scc_info *)n->link)->dfn;
+ scc_info *info = get_irg_link(n);
+ assert(info);
+ return info->dfn;
}
/**********************************************************************/
/**********************************************************************/
static ir_graph **stack = NULL;
-static int tos = 0; /* top of stack */
+static int tos = 0; /**< top of stack */
+/**
+ * initialize the irg stack
+ */
static INLINE void init_stack(void) {
if (stack) {
ARR_RESIZE (ir_graph *, stack, 1000);
tos = 0;
}
-
+/**
+ * push a graph on the irg stack
+ * @param n the graph to be pushed
+ */
static INLINE void
push (ir_graph *n)
{
mark_irg_in_stack(n);
}
+/**
+ * return the topmost graph on the stack and pop it
+ */
static INLINE ir_graph *
pop (void)
{
return n;
}
-/* The nodes up to n belong to the current loop.
- Removes them from the stack and adds them to the current loop. */
+/**
+ * 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)
{
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. */
+/**
+ * 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)
{
}
/**********************************************************************/
-/* 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. */
+/**
+ * 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 = 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->n_nodes = 0;
+ son->n_sons = 0;
if (father) {
son->outer_loop = father;
add_loop_son(father, son);
- son->depth = father->depth+1;
+ son->depth = father->depth + 1;
} else { /* The root loop */
son->outer_loop = son;
- son->depth = 0;
+ son->depth = 0;
}
#ifdef DEBUG_libfirm
son->loop_nr = get_irp_new_node_nr();
- son->link = NULL;
+ son->link = NULL;
#endif
current_loop = son;
static INLINE void
init_scc (void) {
int i;
- current_dfn = 1;
+ int n_irgs;
+
+ 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());
- get_irp_irg(i)->callgraph_recursion_depth = 0;
- get_irp_irg(i)->callgraph_loop_depth = 0;
+
+ 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());
+ 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
+static int
is_head (ir_graph *n, ir_graph *root)
{
int i, arity;
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));
+ DDMG(pred); DDMG(root);
+ 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;
}
-/* 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
+
+/**
+ * Returns non-zero if n is possible loop head of an endless loop.
+ * I.e., it is a Block, Phi or Filter node and has only predecessors
+ * within the loop.
+ * @arg root: only needed for assertion.
+ */
+static int
is_endless_head (ir_graph *n, ir_graph *root)
{
int i, arity;
assert(pred);
if (is_irg_callee_backedge(n, i)) { continue; }
if (!irg_is_in_stack(pred)) {
- some_outof_loop = 1;
+ 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));
+ DDMG(pred); DDMG(root);
+ 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;
}
-/* Check whether there is a parallel edge in the ip control flow.
- Only */
-static bool
+/**
+ * Check whether there is a parallel edge in the ip control flow.
+ * Only
+ */
+static int
is_ip_head (ir_graph *n, ir_graph *pred)
{
- int iv_rem = get_interprocedural_view();
- set_interprocedural_view(true);
- ir_node *sblock = get_irg_start_block(n);
- int i, arity = get_Block_n_cfgpreds(sblock);
int is_be = 0;
-
- //printf(" edge from "); DDMG(n);
- //printf(" to pred "); DDMG(pred);
- //printf(" sblock "); DDMN(sblock);
-
- for (i = 0; i < arity; i++) {
- ir_node *pred_cfop = skip_Proj(get_Block_cfgpred(sblock, i));
- //printf(" "); DDMN(pred_cfop);
- if (get_irn_op(pred_cfop) == op_CallBegin) { /* could be Unknown */
- ir_graph *ip_pred = get_irn_irg(pred_cfop);
- //printf(" "); DDMG(ip_pred);
- if ((ip_pred == pred) && is_backedge(sblock, i)) {
- //printf(" found\n");
- is_be = 1;
+ int iv_rem = get_interprocedural_view();
+ set_interprocedural_view(1);
+ {
+ ir_node *sblock = get_irg_start_block(n);
+ int i, arity = get_Block_n_cfgpreds(sblock);
+
+ //printf(" edge from "); DDMG(n);
+ //printf(" to pred "); DDMG(pred);
+ //printf(" sblock "); DDMN(sblock);
+
+ for (i = 0; i < arity; i++) {
+ ir_node *pred_cfop = skip_Proj(get_Block_cfgpred(sblock, i));
+ //printf(" "); DDMN(pred_cfop);
+ if (get_irn_op(pred_cfop) == op_CallBegin) { /* could be Unknown */
+ ir_graph *ip_pred = get_irn_irg(pred_cfop);
+ //printf(" "); DDMG(ip_pred);
+ if ((ip_pred == pred) && is_backedge(sblock, i)) {
+ //printf(" found\n");
+ is_be = 1;
+ }
}
}
}
-
set_interprocedural_view(iv_rem);
return is_be;
}
-/* 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)
{
return index;
}
-/* 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)
{
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;
+ 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;
+ 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;
- }
- if (m == n) { break; } /* It's not an unreachable loop, either. */
+ 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;
+ }
+ if (m == n) { break; } /* It's not an unreachable loop, either. */
}
//assert(0 && "no head found on stack");
}
ir_graph *m;
int i, res_index = -2;
+ ir_graph *res;
ir_graph *in_and_out = NULL;
ir_graph *only_in = NULL;
ir_graph *ip_in_and_out = NULL;
//printf(" found 1a! "); DDM;
in_and_out = m;
if (is_ip_head(pred, m)) {
- //printf(" found 1b! "); DDM;
- ip_in_and_out = m;
+ //printf(" found 1b! "); DDM;
+ ip_in_and_out = m;
}
} else if (!ip_only_in && is_endless_head(m, n)) {
only_in = m;
//printf(" found 2a! "); DDM;
if (is_ip_head(pred, m)) {
- //printf(" found 2b! "); DDM;
- ip_only_in = m;
+ //printf(" found 2b! "); DDM;
+ ip_only_in = m;
}
} else if (is_ip_head(pred, m)) {
//printf(" found 3! "); DDM; This happens for self recursions in the second
res_index = largest_dfn_pred (m);
set_irg_callee_backedge (m, res_index);
- ir_graph *res = get_irg_callee(m, res_index);
+ res = get_irg_callee(m, res_index);
//printf("*** tail is "); DDMG(res);
return res;
}
static void cgscc (ir_graph *n) {
- int i;
+ int i, arity;
if (cg_irg_visited(n)) return;
mark_cg_irg_visited(n);
current_dfn ++;
push(n);
- int arity = get_irg_n_callees(n);
-
+ arity = get_irg_n_callees(n);
for (i = 0; i < arity; i++) {
ir_graph *m;
if (is_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. */
+ Propagate the uplink to mark the cfloop. */
if (get_irg_uplink(m) < get_irg_uplink(n))
- set_irg_uplink(n, get_irg_uplink(m));
+ set_irg_uplink(n, get_irg_uplink(m));
}
}
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 */
+ 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();
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. */
+ 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);
}
-
+/**
+ * reset the backedge information for all callers in all irgs
+ */
static void reset_isbe(void) {
int i, n_irgs = get_irp_n_irgs();
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;
/* weight. Assign graphs the maximal depth. */
/* ----------------------------------------------------------------------------------- */
-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);
set_cg_irg_visited(irg, master_cg_visited-1);
}
-
-/* ----------------------------------------------------------------------------------- */
-/* Another algorithm to compute recursion nesting depth */
-/* Walk the callgraph. For each crossed loop increase the nesting depth by one. */
-/* Assign graphs the maximal nesting depth. Don't increas if passing loops more than */
+/* ------------------------------------------------------------------------------------ */
+/* Another algorithm to compute recursion nesting depth */
+/* Walk the callgraph. For each crossed loop increase the nesting depth by one. */
+/* Assign graphs the maximal nesting depth. Don't increase if passing loops more than */
/* once. */
-/* ----------------------------------------------------------------------------------- */
+/* ------------------------------------------------------------------------------------ */
/* For callees, we want to remember the Call nodes, too. */
-struct ana_entry2 {
- ir_loop **loop_stack;
- int tos;
+typedef struct ana_entry2 {
+ ir_loop **loop_stack; /**< a stack of ir_loop entries */
+ int tos; /**< the top of stack entry */
int recursion_nesting;
-};
-
-typedef struct ana_entry2 ana_entry2;
+} ana_entry2;
+/**
+ * push a loop entry on the stack
+ */
static void push2(ana_entry2 *e, ir_loop *g) {
if (ARR_LEN(e->loop_stack) == e->tos) {
ARR_APP1(ir_loop *, e->loop_stack, g);
} else {
e->loop_stack[e->tos] = g;
}
- e->tos ++;
+ ++e->tos;
}
+/**
+ * returns the top of stack and pop it
+ */
static ir_loop *pop2(ana_entry2 *e) {
- e->tos --;
- return e->loop_stack[e->tos+1];
+ return e->loop_stack[--e->tos];
}
+/**
+ * check if a loop g in on the stack. Did not check the TOS.
+ */
static int in_stack(ana_entry2 *e, ir_loop *g) {
int i;
for (i = e->tos-1; i >= 0; --i) {
return 0;
}
-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;
/* -- spread the nesting value -- */
if (depth == 0 || old_depth < depth) {
- /* Don't walk the graph, but a tree that is an unfolded graph. */
+ /* 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++) {
ir_graph *m = get_irg_callee(irg, i);
}
+/* ----------------------------------------------------------------------------------- */
+/* Another algorithm to compute the execution frequency of methods ignoring recursions. */
+/* Walk the callgraph. Ignore backedges. Use sum of execution frequencies of Call */
+/* nodes to evaluate a callgraph edge. */
+/* ----------------------------------------------------------------------------------- */
+
+double get_irg_method_execution_frequency (ir_graph *irg) {
+ return irg->method_execution_frequency;
+}
+
+void set_irg_method_execution_frequency (ir_graph *irg, double freq) {
+ irg->method_execution_frequency = freq;
+
+ if (irp->max_method_execution_frequency < freq)
+ irp->max_method_execution_frequency = freq;
+}
+
+static void compute_method_execution_frequency (ir_graph *irg, void *env) {
+ int i, n_callers;
+ double freq;
+ int found_edge;
+ int n_callees;
+
+ 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);
+ 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)) {
+ return;
+ }
+ }
+ mark_cg_irg_visited(irg);
+
+ /* Compute the new frequency. */
+ freq = 0;
+ found_edge = 0;
+ for (i = 0; i < n_callers; i++) {
+ if (! is_irg_caller_backedge(irg, i)) {
+ double edge_freq = get_irg_caller_method_execution_frequency(irg, i);
+ assert(edge_freq >= 0);
+ freq += edge_freq;
+ found_edge = 1;
+ }
+ }
+
+ if (!found_edge) {
+ /* A starting point: method only called from outside,
+ or only backedges as predecessors. */
+ freq = 1;
+ }
+
+ set_irg_method_execution_frequency(irg, freq);
+
+ /* recur */
+ n_callees = get_irg_n_callees(irg);
+ for (i = 0; i < n_callees; i++) {
+ compute_method_execution_frequency (get_irg_callee(irg, i), NULL);
+ }
+}
+
+
+/* ----------------------------------------------------------------------------------- */
+/* The recursion stuff driver. */
+/* ----------------------------------------------------------------------------------- */
+
/* Compute the backedges that represent recursions. */
void find_callgraph_recursions(void) {
int i, n_irgs = get_irp_n_irgs();
reset_isbe();
- /* -- Compute the looptree -- */
+ /* -- 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. */
+ 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();
init_scc();
}
}
+ irp->callgraph_state = irp_callgraph_and_calltree_consistent;
+}
+
+void compute_performance_estimates(void) {
+ int i, n_irgs = get_irp_n_irgs();
+ int current_nesting;
+ ana_entry2 e;
+
/* -- compute the loop depth -- */
- int current_nesting = 0;
+ current_nesting = 0;
irp->max_callgraph_loop_depth = 0;
master_cg_visited += 2;
//printf (" ** starting at "); DDMG(get_irp_main_irg());
}
}
+
/* -- compute the recursion depth -- */
- ana_entry2 e;
- e.loop_stack = NEW_ARR_F(ir_loop *, 0);
- e.tos = 0;
+ e.loop_stack = NEW_ARR_F(ir_loop *, 0);
+ e.tos = 0;
e.recursion_nesting = 0;
+
irp->max_callgraph_recursion_depth = 0;
master_cg_visited += 2;
DEL_ARR_F(e.loop_stack);
- //dump_callgraph("-with_nesting");
-
- //dump_callgraph_loop_tree(current_loop, "-after_cons");
- irp->callgraph_state = irp_callgraph_and_calltree_consistent;
+ /* -- compute the execution frequency -- */
+ irp->max_method_execution_frequency = 0;
+ master_cg_visited += 2;
+ assert(get_irg_n_callers(get_irp_main_irg()) == 0);
+ compute_method_execution_frequency(get_irp_main_irg(), NULL);
+ 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_method_execution_frequency(irg, NULL);
+ }
+ }
+ 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_method_execution_frequency(irg, NULL);
+ }
+ }
}
/* Maximal loop depth of all paths from an external visible method to
}
find_callgraph_recursions();
+
+ compute_performance_estimates();
+
+ 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;
+}
+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;
}
projects / libfirm / blobdiff