#include "config.h"
#endif
+#ifdef HAVE_STRING_H
#include <string.h>
+#endif
#include "irloop_t.h"
#include "irnode_t.h"
#include "irprog_t.h"
#include "irdump.h"
+#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);
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;
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
/* 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);
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);
+}
+
/*-----------------------------------------------------------*
* The core algorithm. *
*-----------------------------------------------------------*/
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);
int i;
- assert(!interprocedural_view &&
+ assert(!get_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 rem_ipv = get_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_loop = NULL;
new_loop(); /* sets current_loop */
- interprocedural_view = 1;
+ set_interprocedural_view(true);
inc_max_irg_visited();
for (i = 0; i < get_irp_n_irgs(); i++)
assert(get_irg_loop(outermost_ir_graph)->kind == k_ir_loop);
current_ir_graph = rem;
- interprocedural_view = rem_ipv;
+ set_interprocedural_view(rem_ipv);
+ return max_loop_depth;
}
static void reset_backedges(ir_node *n) {
+ int rem = get_interprocedural_view();
+
assert(is_Block(n));
- int rem = interprocedural_view;
- interprocedural_view = 1;
+ set_interprocedural_view(true);
clear_backedges(n);
- interprocedural_view = 0;
+ set_interprocedural_view(false);
clear_backedges(n);
- interprocedural_view = rem;
+ set_interprocedural_view(rem);
}
static void loop_reset_backedges(ir_loop *l) {
void free_all_cfloop_information (void) {
int i;
- int rem = interprocedural_view;
- interprocedural_view = 1; /* To visit all filter nodes */
+ int rem = get_interprocedural_view();
+ set_interprocedural_view(true); /* To visit all filter nodes */
for (i = 0; i < get_irp_n_irgs(); i++) {
free_cfloop_information(get_irp_irg(i));
}
- interprocedural_view = rem;
+ set_interprocedural_view(rem);
}
projects / libfirm / blobdiff