* @date 7.2002
* @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 <stdlib.h>
-#endif
+#include <string.h>
+#include <stdlib.h>
#include "irloop_t.h"
/**
* Allocates a new SCC info on the given obstack.
*/
-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;
+static inline scc_info *new_scc_info(struct obstack *obst) {
+ return OALLOCZ(obst, scc_info);
}
/**
* Mark node n being on the SCC stack.
*/
-static INLINE void mark_irn_in_stack(ir_node *n) {
+static inline void mark_irn_in_stack(ir_node *n) {
scc_info *scc = get_irn_link(n);
assert(scc);
scc->in_stack = 1;
/**
* Mark node n NOT being on the SCC stack.
*/
-static INLINE void mark_irn_not_in_stack(ir_node *n) {
+static inline void mark_irn_not_in_stack(ir_node *n) {
scc_info *scc = get_irn_link(n);
assert(scc);
scc->in_stack = 0;
/**
* Checks if a node is on the SCC stack.
*/
-static INLINE int irn_is_in_stack(ir_node *n) {
+static inline int irn_is_in_stack(ir_node *n) {
scc_info *scc = get_irn_link(n);
assert(scc);
return scc->in_stack;
/**
* Sets the uplink number for a node.
*/
-static INLINE void set_irn_uplink(ir_node *n, int uplink) {
+static inline void set_irn_uplink(ir_node *n, int uplink) {
scc_info *scc = get_irn_link(n);
assert(scc);
scc->uplink = uplink;
/**
* Sets the depth-first-search number for a node.
*/
-static INLINE void set_irn_dfn(ir_node *n, int dfn) {
+static inline void set_irn_dfn(ir_node *n, int dfn) {
scc_info *scc = get_irn_link(n);
assert(scc);
scc->dfn = dfn;
/**
* initializes the stack
*/
-static INLINE void init_stack(void) {
+static inline void init_stack(void) {
if (stack) {
ARR_RESIZE(ir_node *, stack, 1000);
} else {
tos = 0;
}
-#if 0
/**
* Frees the stack.
*/
-static INLINE void free_stack(void) {
- if (stack != NULL) {
- DEL_ARR_F(stack);
- stack = NULL;
- }
- tos = 0;
+static void finish_stack(void) {
+ DEL_ARR_F(stack);
+ stack = NULL;
}
-#endif
/**
* push a node onto the stack
*
* @param n The node to push
*/
-static INLINE void push(ir_node *n) {
+static inline void push(ir_node *n) {
if (tos == ARR_LEN(stack)) {
int nlen = ARR_LEN(stack) * 2;
ARR_RESIZE(ir_node *, stack, nlen);
*
* @return The topmost node
*/
-static INLINE ir_node *pop(void) {
+static inline ir_node *pop(void) {
ir_node *n = stack[--tos];
mark_irn_not_in_stack(n);
return n;
* 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_node *n) {
+static inline void pop_scc_to_loop(ir_node *n) {
ir_node *m;
int i = 0;
/* 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_node *n) {
+static inline void pop_scc_unmark_visit(ir_node *n) {
ir_node *m = NULL;
while (m != n) {
/* Initialization steps. **********************************************/
-static INLINE void init_node(ir_node *n, void *env) {
+static inline void init_node(ir_node *n, void *env) {
struct obstack *obst = env;
set_irn_link(n, new_scc_info(obst));
clear_backedges(n);
}
-static INLINE void init_scc_common(void) {
+static inline void init_scc_common(void) {
current_dfn = 1;
loop_node_cnt = 0;
init_stack();
}
-static INLINE void init_scc(ir_graph *irg, struct obstack *obst) {
+static inline void init_scc(ir_graph *irg, struct obstack *obst) {
init_scc_common();
irg_walk_graph(irg, init_node, NULL, obst);
/*
*/
}
+static inline void finish_scc(void)
+{
+ finish_stack();
+}
+
#ifdef INTERPROCEDURAL_VIEW
-static INLINE void init_ip_scc(struct obstack *obst) {
+static inline void init_ip_scc(struct obstack *obst) {
init_scc_common();
cg_walk(init_node, NULL, obst);
}
#endif
-/* Condition for breaking the recursion. */
+/**
+ * Check weather a given node represents the outer most Start
+ * block. In intra-procedural view this is the start block of the
+ * current graph, in interprocedural view it is the start block
+ * of the outer most graph.
+ *
+ * @param n the node to check
+ *
+ * This is the condition for breaking the scc recursion.
+ */
static int is_outermost_Start(ir_node *n) {
- /* Test whether this is the outermost Start node. If so
- recursion must end. */
- if ((get_irn_op(n) == op_Block) &&
- (get_Block_n_cfgpreds(n) == 1) &&
- (get_irn_op(skip_Proj(get_Block_cfgpred(n, 0))) == op_Start) &&
- (get_nodes_block(skip_Proj(get_Block_cfgpred(n, 0))) == n)) {
+ /* Test whether this is the outermost Start node. */
+ if (is_Block(n) && get_Block_n_cfgpreds(n) == 1) {
+ ir_node *pred = skip_Proj(get_Block_cfgpred(n, 0));
+ if (is_Start(pred) && get_nodes_block(pred) == n)
return 1;
}
-#if 0
- /* @@@ Bad condition:
- not possible in interprocedural view as outermost_graph is
- not necessarily the only with a dead-end start block.
- Besides current_ir_graph is not set properly. */
- if ((get_irn_op(n) == op_Block) &&
- (n == get_irg_start_block(current_ir_graph))) {
- if ((!get_interprocedural_view()) ||
- (current_ir_graph == outermost_ir_graph))
- return 1;
- }
-#endif
return 0;
}
/* When to walk from nodes to blocks. Only for Control flow operations? */
-static INLINE int get_start_index(ir_node *n) {
+static inline int get_start_index(ir_node *n) {
#undef BLOCK_BEFORE_NODE
#define BLOCK_BEFORE_NODE 1
not reachable.
I.e., with this code, the order on the loop tree is correct. But a (single)
test showed the loop tree is deeper. */
- if (get_irn_op(n) == op_Phi ||
- get_irn_op(n) == op_Block ||
- (get_irn_op(n) == op_Filter && get_interprocedural_view()) ||
- (get_irg_pinned(get_irn_irg(n)) == op_pin_state_floats &&
- get_irn_pinned(n) == op_pin_state_floats))
+ if (get_irn_op(n) == op_Phi ||
+ is_Block(n) ||
+ (is_Filter(n) && get_interprocedural_view()) || (
+ get_irg_pinned(get_irn_irg(n)) == op_pin_state_floats &&
+ get_irn_pinned(n) == op_pin_state_floats
+ ))
// Here we could test for backedge at -1 which is illegal
return 0;
else
But it guarantees that Blocks are analysed before nodes contained in the
block. If so, we can set the value to undef if the block is not \
executed. */
- if (is_cfop(n) || is_fragile_op(n) || get_irn_op(n) == op_Start)
+ if (is_cfop(n) || is_fragile_op(n) || is_Start(n))
return -1;
else
return 0;
#endif
}
-/* Test for legal loop header: Block, Phi, ... */
-static INLINE int is_possible_loop_head(ir_node *n) {
+/**
+ * Return non-zero if the given node is a legal loop header:
+ * Block, Phi, Filter.
+ *
+ * @param n the node to check
+ */
+static inline int is_possible_loop_head(ir_node *n) {
ir_op *op = get_irn_op(n);
return ((op == op_Block) ||
(op == op_Phi) ||
* Returns non-zero if n is a loop header, i.e., it is a Block, Phi
* or Filter node and has predecessors within the loop and out
* of the loop.
- * @param root: only needed for assertion.
+ *
+ * @param n the node to check
+ * @param root only needed for assertion.
*/
static int is_head(ir_node *n, ir_node *root) {
int i, arity;
return 0;
if (!is_outermost_Start(n)) {
+#ifndef NDEBUG
+ int uplink = get_irn_uplink(root);
+#else
+ (void) root;
+#endif
arity = get_irn_arity(n);
for (i = get_start_index(n); i < arity; i++) {
- ir_node *pred = get_irn_n(n, i);
- assert(pred);
+ ir_node *pred;
if (is_backedge(n, i))
continue;
- if (!irn_is_in_stack(pred)) {
+ pred = get_irn_n(n, i);
+ if (! irn_is_in_stack(pred)) {
some_outof_loop = 1;
} else {
- if (get_irn_uplink(pred) < get_irn_uplink(root)) {
- assert(get_irn_uplink(pred) >= get_irn_uplink(root));
- }
+ assert(get_irn_uplink(pred) >= uplink);
some_in_loop = 1;
}
}
}
- return some_outof_loop && some_in_loop;
+ return some_outof_loop & some_in_loop;
}
/**
* 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.
- * @param root: only needed for assertion.
+ *
+ * @param n the node to check
+ * @param root only needed for assertion.
*/
static int is_endless_head(ir_node *n, ir_node *root) {
int i, arity;
- int some_outof_loop = 0, some_in_loop = 0;
+ int none_outof_loop = 1, some_in_loop = 0;
/* Test for legal loop header: Block, Phi, ... */
if (!is_possible_loop_head(n))
return 0;
if (!is_outermost_Start(n)) {
+#ifndef NDEBUG
+ int uplink = get_irn_uplink(root);
+#else
+ (void) root;
+#endif
arity = get_irn_arity(n);
for (i = get_start_index(n); i < arity; i++) {
- ir_node *pred = get_irn_n(n, i);
- assert(pred);
- if (is_backedge(n, i)) { continue; }
+ ir_node *pred;
+ if (is_backedge(n, i))
+ continue;
+ pred = get_irn_n(n, i);
if (!irn_is_in_stack(pred)) {
- some_outof_loop = 1; //printf(" some out of loop ");
+ none_outof_loop = 0;
} else {
- if (get_irn_uplink(pred) < get_irn_uplink(root)) {
- assert(get_irn_uplink(pred) >= get_irn_uplink(root));
- }
+ assert(get_irn_uplink(pred) >= uplink);
some_in_loop = 1;
}
}
}
- return !some_outof_loop && some_in_loop;
+ return none_outof_loop & some_in_loop;
}
/** Returns index of the predecessor with the smallest dfn number
int arity = get_irn_arity(n);
for (i = get_start_index(n); i < arity; i++) {
ir_node *pred = get_irn_n(n, i);
- assert(pred);
- if (is_backedge(n, i) || !irn_is_in_stack(pred)) continue;
+ 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;
min = get_irn_dfn(pred);
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_node *n) {
int i, index = -2, max = -1;
int arity = get_irn_arity(n);
for (i = get_start_index(n); i < arity; i++) {
ir_node *pred = get_irn_n(n, i);
- if (is_backedge (n, i) || !irn_is_in_stack(pred)) continue;
+ if (is_backedge (n, i) || !irn_is_in_stack(pred))
+ continue;
if (get_irn_dfn(pred) > max) {
index = i;
max = get_irn_dfn(pred);
* If it finds no backedge returns NULL.
* ("disable_backedge" in fiasco)
*
- * @param n A node where uplink == dfn.
+ * @param n A node where uplink == dfn.
*/
static ir_node *find_tail(ir_node *n) {
ir_node *m;
if (!icfg && rm_cyclic_phis && remove_cyclic_phis (n)) return NULL;
*/
m = stack[tos-1]; /* tos = top of stack */
- if (is_head (m, n)) {
+ if (is_head(m, n)) {
res_index = smallest_dfn_pred(m, 0);
if ((res_index == -2) && /* no smallest dfn pred found. */
(n == m))
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 (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);
+ res_index = largest_dfn_pred(m);
if ((m == n) && (res_index == -2)) { /* don't walk past loop head. */
i = -1;
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 (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;
be a head. I.e., the code is "dying". We break the loop by
setting Bad nodes. */
int arity = get_irn_arity(n);
+ ir_node *bad = get_irg_bad(get_irn_irg(n));
for (i = -1; i < arity; ++i) {
- set_irn_n(n, i, get_irg_bad(get_irn_irg(n)));
+ set_irn_n(n, i, bad);
}
return NULL;
}
- assert (res_index > -2);
+ assert(res_index > -2);
set_backedge(m, res_index);
return is_outermost_Start(n) ? NULL : get_irn_n(m, res_index);
#endif
-static INLINE int is_outermost_loop(ir_loop *l) {
+static inline int is_outermost_loop(ir_loop *l) {
return l == get_loop_outer_loop(l);
}
* The core algorithm. *
*-----------------------------------------------------------*/
+/**
+ * The core algorithm: Find strongly coupled components.
+ *
+ * @param n node to start
+ */
static void scc(ir_node *n) {
- int i;
- if (irn_visited(n)) return;
- mark_irn_visited(n);
+ if (irn_visited_else_mark(n))
+ return;
/* Initialize the node */
set_irn_dfn(n, current_dfn); /* Depth first number for this node */
set_irn_uplink(n, current_dfn); /* ... is default uplink. */
set_irn_loop(n, NULL);
- current_dfn ++;
+ ++current_dfn;
push(n);
/* AS: get_start_index might return -1 for Control Flow Nodes, and thus a negative
so is_backedge does not access array[-1] but correctly returns false! */
if (!is_outermost_Start(n)) {
- int arity = get_irn_arity(n);
+ int i, arity = get_irn_arity(n);
- for (i = get_start_index(n); i < arity; i++) {
+ for (i = get_start_index(n); i < arity; ++i) {
ir_node *m;
- if (is_backedge(n, i)) continue;
- m = get_irn_n(n, i); /* get_irn_ip_pred(n, i); */
- /* if ((!m) || (get_irn_op(m) == op_Unknown)) continue; */
+ if (is_backedge(n, i))
+ continue;
+ m = get_irn_n(n, i);
scc(m);
if (irn_is_in_stack(m)) {
/* Uplink of m is smaller if n->m is a backedge.
uplink still is the same as the dfn.
But n might not be a proper loop head for the analysis. Proper loop
- heads are Block and Phi nodes. find_tail searches the stack for
+ heads are Block and Phi nodes. find_tail() searches the stack for
Block's and Phi's and takes those nodes as loop heads for the current
loop instead and marks the incoming edge as backedge. */
ir_node *tail = find_tail(n);
- if (tail) {
+ if (tail != NULL) {
/* We have a loop, that is no straight line code,
because we found a loop head!
Next actions: Open a new loop on the loop tree and
/* The current backedge has been marked, that is temporarily eliminated,
by find tail. Start the scc algorithm
- anew on the subgraph that is left (the current loop without the backedge)
+ again on the subgraph that is left (the current loop without the backedge)
in order to find more inner loops. */
scc(tail);
}
}
+#ifdef INTERPROCEDURAL_VIEW
static void my_scc(ir_node *n) {
int i;
- if (irn_visited(n))
+ if (irn_visited_else_mark(n))
return;
- mark_irn_visited(n);
/* Initialize the node */
set_irn_dfn(n, current_dfn); /* Depth first number for this node */
ir_node *m;
if (is_backedge(n, i)) continue;
m = get_irn_n(n, i); /* get_irn_ip_pred(n, i); */
- /* if ((!m) || (get_irn_op(m) == op_Unknown)) continue; */
+ /* if (!m || is_Unknown(m)) continue; */
my_scc(m);
if (irn_is_in_stack(m)) {
/* Uplink of m is smaller if n->m is a backedge.
}
}
}
+#endif /* INTERPROCEDURAL_VIEW */
/* Constructs backedge information for irg. In interprocedural view constructs
backedges for all methods called by irg, too. */
inc_irg_visited(irg);
scc(get_irg_end(irg));
+
+ finish_scc();
obstack_free(&temp, NULL);
assert(head_rem == current_loop);
*
* Returns non-zero, if the node n is not changed in the loop block
* belongs to or in inner loops of this blocks loop. */
-int is_loop_invariant(ir_node *n, ir_node *block) {
+int is_loop_invariant(const ir_node *n, const ir_node *block) {
ir_loop *l = get_irn_loop(block);
- ir_node *b = is_Block(n) ? n : get_nodes_block(n);
+ const ir_node *b = is_Block(n) ? n : get_nodes_block(n);
return !is_loop_variant(l, get_irn_loop(b));
}
projects / libfirm / blobdiff