#include "irprog_t.h"
#include "irdump.h"
-ir_graph *outermost_ir_graph; /* The outermost graph the scc is computed
+#define NO_CFLOOPS_WITHOUT_HEAD 1
+
+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. @@@ */
+ 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. */
+ of visited nodes. */
+
+static int max_loop_depth = 0;
void link_to_reg_end (ir_node *n, void *env);
-void set_projx_link(ir_node *cb_projx, ir_node *end_projx);
-ir_node *get_projx_link(ir_node *cb_projx);
/**********************************************************************/
/* Node attributes **/
/**********************************************************************/
-/* A map to get from irnodes to loop nodes. */
-static pmap *node_loop_map = NULL;
-
/**********************************************************************/
/* Node attributes needed for the construction. **/
/**********************************************************************/
son->outer_loop = father;
add_loop_son(father, son);
son->depth = father->depth+1;
+ if (son->depth > max_loop_depth) max_loop_depth = son->depth;
} else { /* The root loop */
son->outer_loop = son;
son->depth = 0;
init_scc_common (void) {
current_dfn = 1;
loop_node_cnt = 0;
- if (!node_loop_map) node_loop_map = pmap_create();
init_stack();
}
recursion must end. */
assert(is_Block(n));
if ((get_Block_n_cfgpreds(n) == 1) &&
- (intern_get_irn_op(skip_Proj(get_Block_cfgpred(n, 0))) == op_Start) &&
- (get_nodes_Block(skip_Proj(get_Block_cfgpred(n, 0))) == n)) {
+ (get_irn_op(skip_Proj(get_Block_cfgpred(n, 0))) == op_Start) &&
+ (get_nodes_block(skip_Proj(get_Block_cfgpred(n, 0))) == n)) {
return true;
}
return false;
assert(is_Block(n));
if (!is_outermost_StartBlock(n)) {
- arity = intern_get_irn_arity(n);
+ arity = get_irn_arity(n);
for (i = 0; i < arity; i++) {
- ir_node *pred = get_nodes_block(skip_Proj(intern_get_irn_n(n, i)));
+ ir_node *pred = get_nodes_block(skip_Proj(get_irn_n(n, i)));
if (is_backedge(n, i)) continue;
if (!irn_is_in_stack(pred)) {
some_outof_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_node *n, ir_node *root)
+{
+ int i, arity;
+ int some_outof_loop = 0, some_in_loop = 0;
+
+ assert(is_Block(n));
+ /* Test for legal loop header: Block, Phi, ... */
+ if (!is_outermost_StartBlock(n)) {
+ arity = get_irn_arity(n);
+ for (i = 0; i < arity; i++) {
+ ir_node *pred = get_nodes_block(skip_Proj(get_irn_n(n, i)));
+ assert(pred);
+ if (is_backedge(n, i)) { continue; }
+ if (!irn_is_in_stack(pred)) {
+ some_outof_loop = 1; //printf(" some out of loop ");
+ } else {
+ if(get_irn_uplink(pred) < get_irn_uplink(root)) {
+ DDMN(pred); DDMN(root);
+ assert(get_irn_uplink(pred) >= get_irn_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
int i, index = -2, min = -1;
if (!is_outermost_StartBlock(n)) {
- int arity = intern_get_irn_arity(n);
+ int arity = get_irn_arity(n);
for (i = 0; i < arity; i++) {
- ir_node *pred = get_nodes_block(skip_Proj(intern_get_irn_n(n, i)));
+ ir_node *pred = get_nodes_block(skip_Proj(get_irn_n(n, i)));
if (is_backedge(n, i) || !irn_is_in_stack(pred)) continue;
if (get_irn_dfn(pred) >= limit && (min == -1 || get_irn_dfn(pred) < min)) {
index = i;
int i, index = -2, max = -1;
if (!is_outermost_StartBlock(n)) {
- int arity = intern_get_irn_arity(n);
+ int arity = get_irn_arity(n);
for (i = 0; i < arity; i++) {
- ir_node *pred = get_nodes_block(skip_Proj(intern_get_irn_n(n, i)));
+ ir_node *pred = get_nodes_block(skip_Proj(get_irn_n(n, i)));
if (is_backedge (n, i) || !irn_is_in_stack(pred)) continue;
if (get_irn_dfn(pred) > max) {
index = i;
/* Searches the stack for possible loop heads. Tests these for backedges.
If it finds a head with an unmarked backedge it marks this edge and
returns the tail of the loop.
- If it finds no backedge returns NULL.
- ("disable_backedge" in fiasco) */
+ If it finds no backedge returns NULL. */
static ir_node *
find_tail (ir_node *n) {
ir_node *m;
return NULL;
} else {
if (m == n) return NULL;
- for (i = tos-2; ; --i) {
+ for (i = tos-2; i >= 0; --i) {
+
m = stack[i];
if (is_head (m, n)) {
res_index = smallest_dfn_pred (m, get_irn_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_irn_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");
+ }
+
}
assert (res_index > -2);
set_backedge (m, res_index);
- return is_outermost_StartBlock(n) ? NULL : get_nodes_block(skip_Proj(intern_get_irn_n(m, res_index)));
+ return is_outermost_StartBlock(n) ? NULL : get_nodes_block(skip_Proj(get_irn_n(m, res_index)));
+}
+
+INLINE static int
+is_outermost_loop(ir_loop *l) {
+ return l == get_loop_outer_loop(l);
}
/*-----------------------------------------------------------*
so is_backedge does not access array[-1] but correctly returns false! */
if (!is_outermost_StartBlock(n)) {
- int arity = intern_get_irn_arity(n);
+ int arity = get_irn_arity(n);
for (i = 0; i < arity; i++) {
ir_node *m;
if (is_backedge(n, i)) continue;
- m = get_nodes_block(skip_Proj(intern_get_irn_n(n, i)));
+ m = get_nodes_block(skip_Proj(get_irn_n(n, i)));
cfscc (m);
if (irn_is_in_stack(m)) {
Next actions: Open a new cfloop on the cfloop tree and
try to find inner cfloops */
-
-#define NO_CFLOOPS_WITHOUT_HEAD 1
#if NO_CFLOOPS_WITHOUT_HEAD
/* This is an adaption of the algorithm from fiasco / optscc to
ir_loop *l;
int close;
- if (get_loop_n_elements(current_loop) > 0) {
+ if ((get_loop_n_elements(current_loop) > 0) || (is_outermost_loop(current_loop))) {
l = new_loop();
close = 1;
} else {
}
/* Constructs backedge information for irg. */
-void construct_cf_backedges(ir_graph *irg) {
+int construct_cf_backedges(ir_graph *irg) {
ir_graph *rem = current_ir_graph;
ir_loop *head_rem;
ir_node *end = get_irg_end(irg);
assert(!interprocedural_view &&
"use construct_ip_backedges");
+ max_loop_depth = 0;
current_ir_graph = irg;
outermost_ir_graph = irg;
assert(get_irg_loop(current_ir_graph)->kind == k_ir_loop);
current_ir_graph = rem;
+ return max_loop_depth;
}
-void construct_ip_cf_backedges (void) {
+int construct_ip_cf_backedges (void) {
ir_graph *rem = current_ir_graph;
int rem_ipv = interprocedural_view;
int i;
assert(get_irp_ip_view_state() == ip_view_valid);
-
+ max_loop_depth = 0;
outermost_ir_graph = get_irp_main_irg();
init_ip_scc();
current_ir_graph = rem;
interprocedural_view = rem_ipv;
+ return max_loop_depth;
}
for (i = 0; i < get_irp_n_irgs(); i++) {
free_cfloop_information(get_irp_irg(i));
}
- pmap_destroy(node_loop_map);
- node_loop_map = NULL;
interprocedural_view = rem;
}