* 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
+
+#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"
/* --------------------- Compute the callgraph ------------------------ */
+/* Hash an address */
+#define HASH_ADDRESS(adr) (((unsigned)(adr)) >> 3)
+/**
+ * Walker called by compute_callgraph()
+ */
static void ana_Call(ir_node *n, void *env) {
int i, n_callees;
ir_graph *irg;
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) { /* Null for unknown caller */
- ir_graph *callee = get_entity_irg(callee_e);
- pset_insert((pset *)callee->callers, irg, (unsigned)irg >> 3);
-
+ ir_graph *callee = get_entity_irg(callee_e);
+ if (callee) { /* For unknown caller */
ana_entry buf = { callee, NULL, 0};
- ana_entry *found = pset_find((pset *)irg->callees, &buf, (unsigned)callee >> 3);
+ ana_entry *found;
+ int depth;
+
+ pset_insert((pset *)callee->callers, irg, (unsigned)irg >> 3);
+ found = pset_find((pset *)irg->callees, &buf, HASH_ADDRESS(callee));
if (found) { /* add Call node to list, compute new nesting. */
} 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->max_depth = 0;
- pset_insert((pset *)irg->callees, found, (unsigned)callee >> 3);
+ found = (ana_entry *) obstack_alloc (irg->obst, sizeof (ana_entry));
+ found->irg = callee;
+ found->call_list = NULL;
+ found->max_depth = 0;
+ pset_insert((pset *)irg->callees, found, HASH_ADDRESS(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;
}
}
}
-/* compare two ir graphs */
+/** compare two ir graphs in a ana_entry */
static int ana_entry_cmp(const void *elt, const void *key) {
- ana_entry *e1 = (ana_entry *)elt;
- ana_entry *e2 = (ana_entry *)key;
+ const ana_entry *e1 = elt;
+ const ana_entry *e2 = key;
return e1->irg != e2->irg;
}
-/* compare two ir graphs */
+/** compare two ir graphs */
static int graph_cmp(const void *elt, const void *key) {
return elt != key;
}
void compute_callgraph(void) {
int i, n_irgs = get_irp_n_irgs();
- assert(interprocedural_view == 0); /* Else walking will not reach the Call nodes. */
+ assert(! get_interprocedural_view()); /* Else walking will not reach the Call nodes. */
/* initialize */
free_callgraph();
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));
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));
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;
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;
- get_irp_irg(i)->callgraph_weighted_loop_depth = 0;
}
}
static bool
is_ip_head (ir_graph *n, ir_graph *pred)
{
- int iv_rem = interprocedural_view;
- interprocedural_view = 1;
- 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(true);
+ {
+ 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;
+ }
}
}
}
-
- interprocedural_view = iv_rem;
+ set_interprocedural_view(iv_rem);
return is_be;
}
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;
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);
}
}
-static int in_same_loop(ir_graph *irg1, ir_graph *irg2) {
- return irg1->l == irg2->l;
-}
-
-/* Returns true if loop depth of low < high and low on
- a path from high to tree root. */
-static int in_lower_loop(ir_graph *high, ir_graph *low) {
- ir_loop *highl = high->l;
- ir_loop *lowl = low->l;
- if (get_loop_depth(lowl) < get_loop_depth(highl)) {
- while (get_loop_outer_loop(highl) != highl) {
- highl = get_loop_outer_loop(highl);
- if (highl == lowl) return 1;
- }
- }
- return 0;
-}
-
-
-/* compute nesting depth */
-static void cnd(ir_loop *loop) {
- int i, n_elems = get_loop_n_elements(loop);
-
- int same_sum = 0;
- int max_lower_edge_max = 0;
-
-
- /* Compute the value for this loop. Deeper loops use this value. */
- for (i = 0; i < n_elems; i++) {
- loop_element le = get_loop_element(loop, i);
- if (*le.kind == k_ir_graph) {
- ir_graph *irg = (ir_graph *)le.node;
- int j, n_callers = get_irg_n_callers(irg);
- int same_edge_max = 0;
- int loop_entry_max = 0;
-
- for (j = 0; j < n_callers; ++j) {
- ir_graph *caller = get_irg_caller(irg, j);
- int caller_loop_depth = get_irg_caller_loop_depth(irg, j);
-
-
- if (in_same_loop(irg, caller))
- same_edge_max = (same_edge_max < caller_loop_depth) ? caller_loop_depth
- : same_edge_max;
- if (in_lower_loop(irg, caller)) {
- int loop_entry_this = caller_loop_depth + caller->l->weighted_depth;
- loop_entry_max = (loop_entry_max < loop_entry_this) ? loop_entry_this
- : loop_entry_max;
- }
- }
-
- max_lower_edge_max = (max_lower_edge_max < loop_entry_max) ? max_lower_edge_max
- : loop_entry_max;
- same_sum += same_edge_max;
- }
- /* This loop is as expensive as the most expensive entry edge + the count of the cycle. */
- loop->weighted_depth = max_lower_edge_max + same_sum + 1; /* 1 for the recursion itself */
- }
-
- /* Recur. */
- for (i = 0; i < n_elems; i++) {
- loop_element le = get_loop_element(loop, i);
- if (*le.kind == k_ir_loop)
- cnd(le.son);
- }
-}
/* ----------------------------------------------------------------------------------- */
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);
int i, n_callees;
+ //return ;
+
if (cg_irg_visited(irg)) return;
+
mark_cg_irg_visited(irg);
- if (current_nesting == 0 || irg->callgraph_loop_depth < current_nesting) {
+ //printf(" old: %d new %d master %d", old_visited, get_cg_irg_visited(irg), master_cg_visited); DDMG(irg);
+
+
+ if (old_nesting < current_nesting)
+ irg->callgraph_loop_depth = current_nesting;
+
+ if (current_nesting > irp->max_callgraph_loop_depth)
+ irp->max_callgraph_loop_depth = current_nesting;
+
+ if ((old_visited +1 < get_cg_irg_visited(irg)) || /* not yet visited */
+ (old_nesting < current_nesting)) { /* propagate larger nesting */
/* Don't walk the graph, but a tree that is an unfolded graph. */
n_callees = get_irg_n_callees(irg);
for (i = 0; i < n_callees; i++) {
}
}
- if (irg->callgraph_loop_depth < current_nesting)
- irg->callgraph_loop_depth = current_nesting;
-
set_cg_irg_visited(irg, master_cg_visited-1);
}
void compute_rec_depth (ir_graph *irg, void *env) {
ana_entry2 *e = (ana_entry2 *)env;
ir_loop *l = irg->l;
- int depth;
+ int depth, old_depth = irg->callgraph_recursion_depth;
int i, n_callees;
int pushed = 0;
if (cg_irg_visited(irg)) return;
mark_cg_irg_visited(irg);
+ /* -- compute and set the new nesting value -- */
if ((l != irp->outermost_cg_loop) && !in_stack(e, l)) {
push2(e, l);
e->recursion_nesting++;
}
depth = e->recursion_nesting;
- if (depth == 0 || irg->callgraph_recursion_depth < depth) {
+ if (old_depth < depth)
+ irg->callgraph_recursion_depth = depth;
+
+ if (depth > irp->max_callgraph_recursion_depth)
+ irp->max_callgraph_recursion_depth = depth;
+
+ /* -- spread the nesting value -- */
+ if (depth == 0 || old_depth < depth) {
/* Don't walk the graph, but a tree that is an unfolded graph. */
n_callees = get_irg_n_callees(irg);
for (i = 0; i < n_callees; i++) {
}
}
- if (irg->callgraph_recursion_depth < depth)
- irg->callgraph_recursion_depth = depth;
-
+ /* -- clean up -- */
if (pushed) {
pop2(e);
e->recursion_nesting--;
/* Compute the backedges that represent recursions. */
void find_callgraph_recursions(void) {
int i, n_irgs = get_irp_n_irgs();
+ int current_nesting;
+ ana_entry2 e;
reset_isbe();
}
}
- /* -- Schleifentiefe berechnen -- */
- int current_nesting = 0;
+ /* -- compute the loop depth -- */
+ current_nesting = 0;
+ irp->max_callgraph_loop_depth = 0;
master_cg_visited += 2;
+ //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 (!cg_irg_visited(irg) && get_irg_n_callers(irg) == 0)
+ 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);
+ }
}
for (i = 0; i < n_irgs; i++) {
ir_graph *irg = get_irp_irg(i);
- if (get_cg_irg_visited(irg) < master_cg_visited-1)
+ if (get_cg_irg_visited(irg) < master_cg_visited-1) {
compute_loop_depth(irg, ¤t_nesting);
+ //printf (" ** starting at "); DDMG(irg);
+ }
}
- /* -- Rekursionstiefe berechnen -- */
- ana_entry2 e;
+ /* -- compute the recursion depth -- */
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;
compute_rec_depth(get_irp_main_irg(), &e);
+ //printf (" ++ starting at "); DDMG(get_irp_main_irg());
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_cg_irg_visited(irg) < master_cg_visited-1) &&
+ get_irg_n_callers(irg) == 0) {
compute_rec_depth(irg, &e);
+ //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)
+ if (get_cg_irg_visited(irg) < master_cg_visited-1) {
compute_rec_depth(irg, &e);
+ //printf (" ++ starting at "); DDMG(irg);
+ }
}
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;
+ irp->callgraph_state = irp_callgraph_and_calltree_consistent;
}
/* Maximal loop depth of all paths from an external visible method to
assert(irp->callgraph_state == irp_callgraph_and_calltree_consistent);
return irg->callgraph_recursion_depth;
}
+
+void analyse_loop_nesting_depth(void) {
+ entity **free_methods = NULL;
+ int arr_len;
+
+ /* establish preconditions. */
+ if (get_irp_callee_info_state() != irg_callee_info_consistent) {
+ cgana(&arr_len, &free_methods);
+ }
+
+ if (irp_callgraph_consistent != get_irp_callgraph_state()) {
+ compute_callgraph();
+ }
+
+ find_callgraph_recursions();
+}
projects / libfirm / blobdiff