/**
* @file
- * @brief Loop peeling and unrolling
* @author Christian Helmer
+ * @brief
+ * Loop peeling, loop inversion and loop unrolling
+ * NOTE: Inversion creates abnormal looking loops because there is probably
+ * no head as single loop entry point. Therefore peeling
+ * will do nothing as it relies on the head as single loop entry point.
+ *
* @version $Id$
*/
#include "config.h"
#include "irtools.h"
#include "array_t.h" /* automatic array */
#include "beutil.h" /* get_block */
+#include "irloop_t.h" /*set_irn_loop*/
-// TODO during DBG
-//#include "irnode_t.h"
-#include "irdump.h"
+/* TODO during DBG */
+/*#include "irdump.h"*/
DEBUG_ONLY(static firm_dbg_module_t *dbg);
typedef struct out_edges {
ir_node *node;
int pred_irn_n;
-} out_edges;
+} out_edge;
/* access complex values through the nodes links */
typedef struct node_info {
ir_node *copy;
ir_node *link; /* temporary links for ssa creation */
ir_node **ins; /* ins for phi nodes, during rewiring of blocks */
+ unsigned done;
struct node_info *freelistnext; /* linked list to free all node_infos */
} node_info;
static node_info *link_node_state_list; /* head of the linked list to free all node_infos */
-static out_edges *cur_loop_outs; /* A walker may start visiting the current loop with these nodes. */
-static out_edges *cur_head_outs; /* A walker may start visiting the cur head with these nodes. */
+static out_edge *cur_loop_outs; /* A walker may start visiting the current loop with these nodes. */
+static out_edge *cur_head_outs; /* A walker may start visiting the cur head with these nodes. */
static ir_node *loop_cf_head = NULL; /* Loop head node */
static unsigned loop_cf_head_valid = 1; /* A loop may have one head, otherwise we do not touch it. */
+ir_node **loops;
+
/* Inverted head */
static ir_node *loop_inv_head = NULL;
/* Peeled head */
/* Loop analysis informations */
typedef struct loop_info_t {
- unsigned calls;
- unsigned loads;
- unsigned invariant_loads; /* number of load nodes */
+ unsigned calls; /* number of calls */
+ unsigned loads; /* number of load nodes */
+ unsigned invariant_loads;
unsigned stores; /* number of store nodes */
unsigned blocks; /* number of blocks in the loop */
- unsigned opnodes_n; /* nodes that should result in an instruction */
- unsigned opnodes_head;
+ unsigned opnodes_n; /* nodes that probably result in an instruction */
+ /* unsigned opnodes_head; */
+ unsigned outs; /* outs without keepalives */
} loop_info_t;
/* Information about the current loop */
static loop_info_t loop_info;
/* A walker may start visiting a condition chain with these nodes. */
-static out_edges *cond_chain_entries;
+static out_edge *cond_chain_entries;
static unsigned head_inversion_node_count;
static unsigned head_inversion_node_limit;
-//static unsigned head_inversion_block_count;
+static unsigned head_inversion_block_count;
+
+static unsigned enable_peeling;
+static unsigned enable_inversion;
/**
*
* ============= AUXILIARY FUNCTIONS =====================================
*/
+
/**
* Creates object on the heap, and adds it to a linked list to free it later.
*/
/* Allocates a node_info struct for the given node. For use with a walker. */
static void alloc_node_info(ir_node *node, void *env)
{
- node_info *state = new_node_info();
+ node_info *state;
(void) env;
+ state = new_node_info();
set_irn_link(node, (void *)state);
}
static void free_node_info(void)
{
- node_info *next;
- next = link_node_state_list;
- while(next->freelistnext) {
- node_info *cur = next;
- next = cur->freelistnext;
- xfree( cur );
+ int a = 0;
+ node_info *n;
+ n = link_node_state_list;
+ while(n) {
+ ++a;
+ node_info *next = n->freelistnext;
+ xfree(n);
+ n = next;
}
+ link_node_state_list = NULL;
}
/**
}
}
+
+
/* Returns the */
static ir_node *get_copy(ir_node *n)
{
((node_info *)get_irn_link(n) )->copy = copy;
}
-/* Returns 0 if the node or block is not in cur_loop */
+/* Returns 0 if the node or block is not in cur_loop
+ * NOTE: get_irn_loop returns the ir_node loop attribute.
+ * But it seems only to be set correctly to blocks!
+ * Thus, without get_block this function does not work.
+ */
static unsigned is_in_loop(ir_node *node)
{
+ /*DB((dbg, LEVEL_5, "node %ld inloop %d\n", node->node_nr, get_irn_loop(get_block(node)) == cur_loop));*/
+ /*DB((dbg, LEVEL_5, "node %ld loop of node %d loop %d\n", node->node_nr, get_irn_loop(get_block(node)), cur_loop)); */
return (get_irn_loop(get_block(node)) == cur_loop);
}
return(!is_in_loop(get_irn_n(n, i)));
}
-/* used for walker */
-static void unmark_block(ir_node *node, void * env)
+/* used for block walker */
+static void reset_block_mark(ir_node *node, void * env)
{
(void) env;
-// DB((dbg, LEVEL_1, "UNMARK %ld\n", node->node_nr));
- if(is_Block(node))
+ /*
+ DB((dbg, LEVEL_5, "UNMARK ..."));
+ DB((dbg, LEVEL_5, " UNMARK %ld\n", get_irn_node_nr(node)));
+ */
+ if (is_Block(node))
set_Block_mark(node, 0);
}
return (get_Block_mark(get_block(node)));
}
+/* Returns the number of blocks in a loop. */
+int get_loop_n_blocks(ir_loop *loop) {
+ int elements, e;
+ int blocks = 0;
+ elements = get_loop_n_elements(loop);
+
+ for(e=0; e<elements; e++) {
+ loop_element elem = get_loop_element(loop, e);
+ if (is_ir_node(elem.kind) && is_Block(elem.node)) {
+ /*DB((dbg, LEVEL_5, "%ld is block \n", elem.node->node_nr));*/
+ ++blocks;
+ }
+ }
+ return blocks;
+}
+
/**
* Add newpred at position pos to node and also add the corresponding value to the phis.
* Requires block phi list.
*/
-static void duplicate_preds(ir_node* node, unsigned pos, ir_node* newpred)
+static int duplicate_preds(ir_node* node, unsigned pos, ir_node* newpred)
{
ir_node** ins;
ir_node *phi;
assert(is_Block(node) && "duplicate_preds is only allowed for blocks");
- DB((dbg, LEVEL_5, "duplicate_preds(node %ld, pos %d, newpred %ld)\n", get_irn_node_nr(node), pos, get_irn_node_nr(newpred)));
+ DB((dbg, LEVEL_5, "duplicate_preds(node %ld, pos %d, newpred %ld)\n",
+ get_irn_node_nr(node), pos, get_irn_node_nr(newpred)));
block_arity = get_irn_arity(node);
- NEW_ARR_A(ir_node*, ins, block_arity + 1 );
+ NEW_ARR_A(ir_node*, ins, block_arity + 1);
for (i = 0; i < block_arity; ++i)
ins[i] = get_irn_n(node, i);
ins[block_arity] = newpred;
DB((dbg, LEVEL_5, "duplicate_preds: fixing phi %ld\n", get_irn_node_nr(phi)));
NEW_ARR_A(ir_node *, ins, block_arity + 1);
- for(i=0; i < phi_arity; ++i) {
+ for (i=0; i < phi_arity; ++i) {
DB((dbg, LEVEL_5, "in %ld\n", get_irn_node_nr(get_irn_n(phi, i))));
ins[i] = get_irn_n(phi, i);
}
ins[block_arity] = get_irn_n(phi, pos);
set_irn_in(phi, block_arity + 1, ins);
}
+ /* return new position */
+ return block_arity;
}
-/* Walks through all nodes of cur_loop */
-static unsigned loop_walker_rec(ir_node *node,
- irg_walk_func_abortable *pre,
- irg_walk_func_abortable *post, void * env)
-{
- int i;
- unsigned stop = 0;
- ir_graph *irg = get_current_ir_graph();
-
- /* RETURN if we walked out of the loop*/
- if (!is_in_loop(node))
- return 0;
-
- if (pre) {
- unsigned stop = pre(node, env);
- if (stop)
- return stop;
- }
-
- set_irn_visited(node, get_irg_visited(irg));
-
- if (get_irn_op(node) != op_Block) {
- ir_node *pred = get_irn_n(node, -1);
- if (get_irn_visited(pred) < get_irg_visited(irg))
- {
- stop = loop_walker_rec(pred, pre, post, env);
- if (stop)
- return stop;
- }
- }
-
- for (i = get_irn_arity(node) - 1; i >= 0; --i) {
- ir_node *pred = get_irn_n(node, i);
- if (get_irn_visited(pred) < get_irg_visited(irg)) {
- stop = loop_walker_rec(pred, pre, post, env);
- if (stop)
- return stop;
- }
- }
-
- if (post)
- return post(node, env);
- return 0;
-}
-
-/**
- * Walks through loop nodes.
- * The entries of the loop (all edges pointing into the loop) have to be given.
- */
-static unsigned loop_walker(out_edges *entries,
- irg_walk_func_abortable *pre, irg_walk_func_abortable *post, void * env)
-{
- int i;
- int stop = 0;
-
- for (i=0; !stop && i<ARR_LEN(entries); i++) {
- ir_node *pred;
- out_edges entry;
- entry = entries[i];
-
- pred = get_irn_n( entry.node , entry.pred_irn_n);
-
- stop = loop_walker_rec( pred, pre, post, env);
- }
- return stop;
-}
-
-
-/* Adds all nodes pointing into the loop to loop_entries and also finds the loops head */
-static void get_loop_outs_and_info(ir_node *node, void *env)
+/* Finds loop head and loop_info */
+static void get_loop_info(ir_node *node, void *env)
{
unsigned node_in_loop, pred_in_loop;
int i, arity;
(void) env;
+ /*DB((dbg, LEVEL_5, "node %+F\n", node));*/
+
+ get_node_info(node)->done = 1;
+
arity = get_irn_arity(node);
for (i = 0; i < arity; i++) {
ir_node *pred = get_irn_n(node, i);
/* collect some loop information */
if (node_in_loop) {
- if ( !is_Store(node) )
+ /*DB((dbg, LEVEL_1, "--------------------------------- inloop %+F\n", node));*/
+ if (is_Store(node))
++loop_info.stores;
- if ( !is_Load(node) )
+ if (is_Load(node))
++loop_info.loads;
- if ( !is_Call(node) )
+ if (is_Call(node))
++loop_info.calls;
- if ( !is_Block(node) && !is_Proj(node) && !is_Phi(node) )
+ if (!is_Block(node) && !is_Proj(node) && !is_Phi(node))
++loop_info.opnodes_n;
}
- //Find the loops head/the blocks with cfpred outside of the loop
+ /* Find the loops head/the blocks with cfpred outside of the loop */
if (is_Block(node) && node_in_loop && !pred_in_loop && loop_cf_head_valid) {
ir_node *cfgpred = get_Block_cfgpred(node, i);
- if ( !is_in_loop(cfgpred) ) {
- //DB((dbg, LEVEL_1, "potential head %+F\n", node));
+
+ if (!is_in_loop(cfgpred)) {
+ DB((dbg, LEVEL_1, "potential head %+F because inloop and pred %+F not inloop\n", node, pred));
/* another head? We do not touch this. */
if (loop_cf_head && loop_cf_head != node) {
loop_cf_head_valid = 0;
}
}
}
+ }
+}
- if ( pred_in_loop && !node_in_loop ) {
- out_edges entry;
+/* Adds all nodes pointing into the loop to loop_entries and also finds the loops head */
+static void get_loop_outs(ir_node *node, void *env)
+{
+ unsigned node_in_loop, pred_in_loop;
+ int i, arity;
+ (void) env;
+
+ arity = get_irn_arity(node);
+ for (i = 0; i < arity; i++) {
+ ir_node *pred = get_irn_n(node, i);
+
+ pred_in_loop = is_in_loop(pred);
+ node_in_loop = is_in_loop(node);
+
+ if (pred_in_loop && !node_in_loop) {
+ out_edge entry;
entry.node = node;
entry.pred_irn_n = i;
- ARR_APP1(out_edges, cur_loop_outs, entry);
+ ARR_APP1(out_edge, cur_loop_outs, entry);
+ if (node != get_irg_end(current_ir_graph))
+ ++loop_info.outs;
}
}
}
if (arity == 0) return 0;
if (is_Load(node)) {
- assert(arity>=2 && "expected load node to have in[1] (address)");
-
- ir_node *pred = get_irn_n(node, 1);
+ ir_node *pred = get_Load_ptr(node);
if ( (get_Load_volatility(node) == volatility_non_volatile) &
(!is_in_loop(pred)
|| is_Const(pred)
return 0;
}
-
static ir_node *ssa_second_def;
static ir_node *ssa_second_def_block;
ir_node *phi;
ir_node **in;
- DB((dbg, LEVEL_5, "ssa sdacp: block %ld\n", get_irn_node_nr(block)));
+ DB((dbg, LEVEL_5, "ssa search_def_and_create_phis: block %ld\n", get_irn_node_nr(block)));
/* Prevents creation of phi that would be bad anyway.
* Dead and bad blocks. */
DB((dbg, LEVEL_5, "ssa phi pred:phi %ld, pred %ld\n", get_irn_node_nr(phi), get_irn_node_nr(pred_val)));
set_irn_n(phi, i, pred_val);
}
-
return phi;
}
static void fix_backedge_info(ir_node *node)
{
int i;
- for (i = 0; i < get_irn_arity(node); ++i)
- {
+ for (i = 0; i < get_irn_arity(node); ++i) {
ir_node *pred = get_irn_n(node, i);
- if (get_node_info(pred)->link != NULL)
+ if (get_node_info(pred)->link != NULL) {
set_backedge(node, i);
- else
+ get_node_info(pred)->link = NULL;
+ DB((dbg, LEVEL_5, "fix backedge: node %ld pred %ld is backedge\n",
+ get_irn_node_nr(node), get_irn_node_nr(pred)));
+ } else {
set_not_backedge(node, i);
+ DB((dbg, LEVEL_5, "fix backedge: node %ld pred %ld is not backedge\n",
+ get_irn_node_nr(node), get_irn_node_nr(pred)));
+ }
}
}
* but phis pred i might not have a copy of itself.
*/
for_each_phi(loophead, phi) {
- //printf("normalbe phi %ld @ %d -> %ld\n", phi->node_nr, i, get_irn_n( get_copy_of(phi), i)->node_nr);
get_node_info( phi )->ins[lheadin_c] = get_irn_n( get_copy(phi), i) ;
}
++lheadin_c;
}
}/* for */
- //DBG
assert(pheadin_c == ARR_LEN(peelheadnins) &&
lheadin_c == ARR_LEN(loopheadnins) &&
"the constructed head arities do not match the predefined arities");
return cp;
}
-//int temp = 0;
-//
-///* This walker copies all walked nodes. The walk_condition determines the nodes to walk. */
-//static void keepalives_walk(ir_node *node, walker_condition *walk_condition)
-//{
-// int i;
-// int arity;
-// ir_graph *irg = current_ir_graph;
-//
-// /**
-// * break condition and cycle resolver, creating temporary node copies
-// */
-// if (get_irn_visited(node) >= get_irg_visited(irg)) {
-// return;
-// }
-//
-// /* Walk */
-// mark_irn_visited(node);
-//
-// if (!is_Block(node)) {
-// ir_node *pred = get_nodes_block(node);
-// if (walk_condition(pred))
-// keepalives_walk( pred, walk_condition );
-// }
-//
-// arity = get_irn_arity(node);
-//
-// for (i = get_irn_arity(node) - 1; i >= 0; --i) {
-// ir_node *pred = get_irn_n(node, i);
-//
-// if (walk_condition(pred))
-// keepalives_walk( pred, walk_condition );
-// }
-//
-// add_End_keepalive(get_irg_end(current_ir_graph), node);
-//}
-
-
/**
* This walker copies all walked nodes.
* If the walk_condition is true for a node, it is walked.
* All nodes node_info->copy attributes has to be NULL prior to every to every walk.
*/
-static void copy_walk(ir_node *node, walker_condition *walk_condition)
+static void copy_walk(ir_node *node, walker_condition *walk_condition, ir_loop *set_loop)
{
int i;
int arity;
/* Here we rely on nodestate's copy being initialized with NULL */
DB((dbg, LEVEL_5, "copy_walk: We have already visited %ld\n", get_irn_node_nr(node)));
if (node_info->copy == NULL) {
- if (!is_Const(node) && !is_SymConst(node)) {
+/* if (!is_Const(node) && !is_SymConst(node)) { */
cp = rawcopy_node(node);
- } else {
+/* } else {
cp = node;
node_info->copy = cp;
- }
+ }*/
DB((dbg, LEVEL_5, "The TEMP copy of %ld is created %ld\n", get_irn_node_nr(node), get_irn_node_nr(cp)));
}
return;
}
-// add_End_keepalive(get_irg_end(current_ir_graph), node);
-
/* Walk */
mark_irn_visited(node);
ir_node *pred = get_nodes_block(node);
if (walk_condition(pred))
DB((dbg, LEVEL_5, "walk block %ld\n", get_irn_node_nr(pred)));
- copy_walk( pred, walk_condition );
+ copy_walk(pred, walk_condition, set_loop);
}
arity = get_irn_arity(node);
if (walk_condition(pred)) {
DB((dbg, LEVEL_5, "walk node %ld\n", get_irn_node_nr(pred)));
- copy_walk( pred, walk_condition );
+ copy_walk(pred, walk_condition, set_loop);
cpin[i] = get_copy(pred);
DB((dbg, LEVEL_5, "copy of %ld gets new in %ld which is copy of %ld\n",
- get_irn_node_nr(node), get_irn_node_nr(get_copy(pred)), get_irn_node_nr(pred)));
+ get_irn_node_nr(node), get_irn_node_nr(get_copy(pred)), get_irn_node_nr(pred)));
} else {
cpin[i] = pred;
}
/* No temporary copy existent */
/* Do not copy constants TODO right? */
- if (!is_Const(node) && !is_SymConst(node)) {
+/* if (!is_Const(node) && !is_SymConst(node)) { */
cp = rawcopy_node(node);
- } else {
+/* } else {
cp = node;
node_info->copy = cp;
- }
+ }*/
DB((dbg, LEVEL_5, "The FINAL copy of %ld is CREATED %ld\n", get_irn_node_nr(node), get_irn_node_nr(cp)));
} else {
/* temporary copy is existent but without correct ins */
set_Block_MacroBlock(cp, cp);
}
+ set_irn_loop(cp, set_loop);
set_irn_in(cp, ARR_LEN(cpin), cpin);
}
/* Loop peeling, and fix the cf for the loop entry nodes, which have now more preds */
-static void peel(out_edges *loop_outs)
+static void peel(out_edge *loop_outs)
{
int i;
ir_node **entry_buffer;
NEW_ARR_A(ir_node *, entry_buffer, ARR_LEN(loop_outs));
/* duplicate loop walk */
-// cur_head = loop_cf_head;
inc_irg_visited(current_ir_graph);
for(i = 0; i < ARR_LEN(loop_outs); i++) {
- out_edges entry = loop_outs[i];
+ out_edge entry = loop_outs[i];
ir_node *node = entry.node;
ir_node *pred = get_irn_n(entry.node, entry.pred_irn_n);
if (is_Block(node)) {
- copy_walk( pred, is_in_loop );
+ copy_walk(pred, is_in_loop, NULL);
duplicate_preds(node, entry.pred_irn_n, get_copy(pred) );
} else {
- copy_walk( pred, is_in_loop );
+ copy_walk(pred, is_in_loop, NULL);
if (!is_End(node)) /* leave out keepalives */
/* Node is user of a value defined inside the loop.
* We'll need a phi since we duplicated the loop. */
* whereas the node's pred at pred_pos is in the head but not the node itself.
* Head and condition chain blocks must be marked.
*/
-static void get_head_entries(ir_node *node, void *env)
+static void get_head_outs(ir_node *node, void *env)
{
int i;
int arity = get_irn_arity(node);
(void) env;
+ DB((dbg, LEVEL_5, "get head entries %ld \n", get_irn_node_nr(node)));
+
for(i = 0; i < arity; ++i) {
/* node is not in the head, but the predecessor is.
* (head or loop chain nodes are marked) */
+
+
+ DB((dbg, LEVEL_5, "... "));
+ DB((dbg, LEVEL_5, "node %ld marked %d (0) pred %d marked %d (1) \n",
+ node->node_nr, is_nodesblock_marked(node),i, is_nodesblock_marked(get_irn_n(node, i))));
+
+
if (!is_nodesblock_marked(node) && is_nodesblock_marked(get_irn_n(node, i))) {
- out_edges entry;
+ out_edge entry;
entry.node = node;
entry.pred_irn_n = i;
DB((dbg, LEVEL_5,
- "Found head chain entry %ld @%d because !inloop %ld and inloop %ld\n",
- node->node_nr, i, node->node_nr, get_irn_n(node, i)->node_nr));
- ARR_APP1(out_edges, cur_head_outs, entry);
+ "Found head chain entry %ld @%d because !inloop %ld and inloop %ld\n",
+ get_irn_node_nr(node), i, get_irn_node_nr(node), get_irn_node_nr(get_irn_n(node, i))));
+ ARR_APP1(out_edge, cur_head_outs, entry);
}
}
}
* Find condition chains, and add them to be inverted, until the node count exceeds the limit.
* A block belongs to the chain if a condition branches out of the loop.
* Returns if the given block belongs to the condition chain.
- * FIXME prevent collecting ALL loop blocks (may happen if all blocks jump out of the loop)
+ * TODO do not (or do?) invert, if all blocks have loop outs.
*/
-static unsigned condition_chains(ir_node *block) {
+static unsigned find_condition_chains(ir_node *block) {
const ir_edge_t *edge;
unsigned mark = 0;
- //unsigned over_limit = 0;
-
int nodes_n = 0;
+ DB((dbg, LEVEL_1, "condition_chains for block %ld\n", get_irn_node_nr(block)));
+
/* we need all outs, including keeps (TODO firm function for that??) */
foreach_out_edge_kind(block, edge, EDGE_KIND_NORMAL) {
++nodes_n;
}
- /* We do not want to collect more nodes from condition chains, than the limit allows us to. */
- if (head_inversion_node_count + nodes_n > head_inversion_node_limit) {
- //over_limit = 1;
+ /* We do not want to collect more nodes from condition chains, than the limit allows us to.
+ * Also, leave at least one block as body. */
+ if (head_inversion_node_count + nodes_n > head_inversion_node_limit
+ || head_inversion_block_count + 1 == loop_info.blocks) {
set_Block_mark(block, 0);
-// printf(" %ld over limit\n", block->node_nr);
+ DB((dbg, LEVEL_1, "block %ld over limit or no blocks to invert\n",
+ get_irn_node_nr(block)));
return 0;
}
- ++loop_info.blocks;
-
/* First: check our successors, and add all succs that are outside of the loop to the list */
foreach_block_succ(block, edge) {
ir_node *src = get_edge_src_irn( edge );
int pos = get_edge_src_pos( edge );
if (!is_in_loop(src)) {
- //printf(" src %ld @ %d into block %ld \n", src->node_nr, pos, block->node_nr);
+ out_edge entry;
+ /*printf(" src %ld @ %d into block %ld \n", src->node_nr, pos, block->node_nr);*/
+
mark = 1;
- out_edges entry;
entry.node = src;
entry.pred_irn_n = pos;
- ARR_APP1(out_edges, cond_chain_entries, entry);
+ ARR_APP1(out_edge, cond_chain_entries, entry);
mark_irn_visited(src);
}
}
return 0;
} else {
set_Block_mark(block, 1);
- DB((dbg, LEVEL_5, "block %ld is part of condition chain\n", get_irn_node_nr(block)));
+ ++head_inversion_block_count;
+ DB((dbg, LEVEL_1, "block %ld is part of condition chain\n", get_irn_node_nr(block)));
head_inversion_node_count += nodes_n;
}
int pos = get_edge_src_pos( edge );
/* already done cases */
- if (!is_in_loop( src ) || (get_irn_visited(src) >= get_irg_visited(current_ir_graph)))
+ if (!is_in_loop( src ) || (get_irn_visited(src) >= get_irg_visited(current_ir_graph))) {
continue;
+ }
mark_irn_visited(src);
-
- inchain = condition_chains( src );
+ DB((dbg, LEVEL_5, "condition chain walk %ld\n", get_irn_node_nr(src)));
+ inchain = find_condition_chains( src );
/* if successor is not part of chain we need to collect its outs */
if ( !inchain ) {
- out_edges entry;
+ out_edge entry;
entry.node = src;
entry.pred_irn_n = pos;
- ARR_APP1(out_edges, cond_chain_entries, entry);
+ ARR_APP1(out_edge, cond_chain_entries, entry);
}
}
return mark;
}
/**
- *
+ * Loop optimization.
+ * Loop inversion, peeling, unrolling.
*/
static void inversion_fix_heads(void)
{
int iheadin_c = 0;
int backedges_n = get_backedge_n(loophead, 0);
- int lhead_arity = headarity - backedges_n;
- int ihead_arity = backedges_n;
+ int lhead_arity = backedges_n;
+ int ihead_arity = headarity - backedges_n;
/* new in arrays for all phis in the head blocks */
NEW_ARR_A(ir_node *, loopheadnins, lhead_arity);
* Rewire the head blocks ins and their phi ins.
* Requires phi list per block.
*/
- if ( is_backedge(loophead, i) ) {
- invheadnins[iheadin_c] = pred;
- for_each_phi(invhead, phi) {
- get_node_info( phi )->ins[iheadin_c] = get_irn_n( phi, i) ;
- }
- ++iheadin_c;
- } else {
+ if (is_backedge(loophead, i) && !is_alien_edge(loophead, i)) {
/* just copy these edges */
loopheadnins[lheadin_c] = pred;
+ get_node_info(pred)->link = NULL; /*(void *)is_backedge(loophead, i);*/
for_each_phi(loophead, phi) {
- get_node_info( phi )->ins[lheadin_c] = get_irn_n(phi, i);
+ get_node_info(phi)->ins[lheadin_c] = get_irn_n(phi, i);
}
++lheadin_c;
+ } else {
+ invheadnins[iheadin_c] = pred;
+ get_node_info(pred)->link = (void *)1;
+ for_each_phi(invhead, phi) {
+ get_node_info(phi)->ins[iheadin_c] = get_irn_n(phi, i) ;
+ }
+ ++iheadin_c;
}
- }/* for */
+ }
/* assign the ins to the head blocks */
set_irn_in(loophead, ARR_LEN(loopheadnins), loopheadnins);
set_irn_in(invhead, ARR_LEN(invheadnins), invheadnins);
+ /* FIX and set former be to normal edges */
+ fix_backedge_info(loophead);
+ fix_backedge_info(invhead);
+
/* assign the ins for the phis */
for_each_phi(loophead, phi) {
ir_node **ins = get_node_info(phi)->ins;
}
}
-
-static void loop_inversion_walk(out_edges *head_entries)
+static void inversion_walk(out_edge *head_entries)
{
int i;
ir_node *phi;
head_phi_assign = NEW_ARR_F(ir_node *, 0);
/* Find assignments in the condition chain, to construct_ssa for them after the loop inversion. */
- for_each_phi( loop_cf_head , phi) {
+ for_each_phi(loop_cf_head , phi) {
for(i=0; i<get_irn_arity(phi); ++i) {
ir_node *def = get_irn_n(phi, i);
- if ( is_nodesblock_marked(def) ) {
+ if (is_nodesblock_marked(def)) {
ARR_APP1(ir_node *, head_phi_assign, def);
}
}
ir_reserve_resources(current_ir_graph, IR_RESOURCE_IRN_VISITED);
- /* duplicate condition chain */
+ /**
+ * duplicate condition chain
+ **/
inc_irg_visited(current_ir_graph);
for(i = 0; i < ARR_LEN(head_entries); ++i) {
- out_edges entry = head_entries[i];
+ out_edge entry = head_entries[i];
ir_node *node = entry.node;
ir_node *pred = get_irn_n(entry.node, entry.pred_irn_n);
-// add_End_keepalive(get_irg_end(current_ir_graph), pred);
-
if (is_Block(node)) {
DB((dbg, LEVEL_5, "\nINIT walk block %ld\n", get_irn_node_nr(pred)));
- copy_walk(pred, is_nodesblock_marked);
+ copy_walk(pred, is_nodesblock_marked, cur_loop);
duplicate_preds(node, entry.pred_irn_n, get_copy(pred) );
} else {
DB((dbg, LEVEL_5, "\nInit walk node %ld\n", get_irn_node_nr(pred)));
- copy_walk( pred, is_nodesblock_marked );
+ copy_walk(pred, is_nodesblock_marked, cur_loop);
/* ignore keepalives */
if (!is_End(node))
/* Node is user of a value assigned inside the loop.
- * We'll need a phi since we duplicated the head. */
+ * We will need a phi since we duplicated the head. */
entry_buffer[entry_c++] = pred;
}
}
inversion_fix_heads();
- DEBUG_ONLY(dump_ir_block_graph(current_ir_graph, "-headsfixed"));
-
/* Generate phis for users of values assigned in the condition chain and read in the loops body */
for(i = 0; i < entry_c; i++) {
ir_node *cppred, *block, *cpblock, *pred;
block = get_nodes_block(pred);
cpblock = get_nodes_block(cppred);
DB((dbg, LEVEL_5,
- "construct_ssa (loop out value) original %ld and clone %ld\n",
- get_irn_node_nr(pred), get_irn_node_nr(cppred)));
+ "construct_ssa (loop out value) original %ld and clone %ld\n",
+ get_irn_node_nr(pred), get_irn_node_nr(cppred)));
construct_ssa(block, pred, cpblock, cppred);
-
-
-// char *res;
-// char *s = "-SSA_";
-// char *n = strdup(" ");
-// n[0] = 'a' + (char)i;
-// res = strdup(s);
-// strcat(res, n);
-// dump_ir_block_graph(current_ir_graph, res );
}
/* Generate phis for values that are assigned in the condition chain
*/
for(i = 0; i < ARR_LEN(head_phi_assign); ++i) {
ir_node *def_block, *inhead_phi_def, *inv_def_block, *inv_inhead_phi_def;
+
/* Note: construct_ssa only fixes the FIRST nodes usage. */
inhead_phi_def = head_phi_assign[i];
inv_inhead_phi_def = get_copy(inhead_phi_def);
def_block = get_nodes_block(inhead_phi_def);
inv_def_block = get_nodes_block(inv_inhead_phi_def);
DB((dbg, LEVEL_5,
- "construct_ssa (condition chain out values) original %ld and clone %ld\n",
- get_irn_node_nr(inv_inhead_phi_def), get_irn_node_nr(inhead_phi_def)));
- construct_ssa(inv_def_block, inv_inhead_phi_def, def_block, inhead_phi_def);
+ "construct_ssa (condition chain out values) original %ld and clone %ld\n",
+ get_irn_node_nr(inv_inhead_phi_def), get_irn_node_nr(inhead_phi_def)));
+ /*construct_ssa(inv_def_block, inv_inhead_phi_def, def_block, inhead_phi_def);*/
+ construct_ssa(def_block, inhead_phi_def, inv_def_block, inv_inhead_phi_def);
+
}
loop_cf_head = get_copy(loop_cf_head);
}
-/**
- * Decide if loop inversion, peeling or unrolling should be performed.
- * Inversion creates abnormal looking loops. Be careful with optimizations after that.
- */
-static void decision_maker(void)
-{
- unsigned do_peel = 0;
- unsigned do_inversion = 1;
- unsigned max_loop_opnodes = 200000;
-
- head_inversion_node_limit = 99910;
+/* Loop peeling */
+void loop_peeling(void)
+{
+ cur_loop_outs = NEW_ARR_F(out_edge, 0);
+ irg_walk_graph( current_ir_graph, get_loop_outs, NULL, NULL );
- cur_loop_outs = NEW_ARR_F(out_edges, 0);
+ DB((dbg, LEVEL_3, "is endless loop: %d (no outs but keepalives)\n", loop_info.outs == 0));
- /* Find loop entries walk, find head */
- inc_irg_visited( current_ir_graph );
- irg_walk_graph( current_ir_graph, get_loop_outs_and_info, NULL, NULL );
+ (void) get_invariants;
- /* RETURN if there is no valid head */
- if (!loop_cf_head || !loop_cf_head_valid) {
- DB((dbg, LEVEL_1, "No valid loop head. Nothing done.\n"));
- return;
- }
#if 0
- /* RETURN if there is a call in the loop */
- if (loop_info.calls)
- return;
-
- /* Loop complexity too high */
- if (loop_info.opnodes_n > max_loop_opnodes)
- return;
-
-// foreach_out_edge(loop_cf_head, edge) {
-// ir_node *node = get_edge_src_irn(edge);
-// if ( !is_Block(node) && !is_Proj(node) && !is_Phi(node) )
-// ++loop_info.opnodes_head;
-// }
-
- inc_irg_visited(current_ir_graph);
+ /*inc_irg_visited(current_ir_graph);*/
loop_walker( loop_outs, NULL, get_invariants, NULL );
/* This could be improved with knowledge about variable range. */
if (loop_info.stores == 0 && loop_info.invariant_loads > 0)
do_peel = 1;
-
#endif
+ peel(cur_loop_outs);
- do_peel = 1;
- do_inversion = 1;
+ /* DEBUG_ONLY(dump_ir_block_graph(current_ir_graph, "-peeled1"));*/
- /* Loop peeling */
- if (do_peel) {
- peel(cur_loop_outs);
- reset_node_infos();
- }
+ /* clean up */
+ reset_node_infos();
- DEBUG_ONLY(dump_ir_block_graph(current_ir_graph, "-peeled1"));
+ set_irg_doms_inconsistent(current_ir_graph);
+ /* TODO needed? */
+ set_irg_loopinfo_inconsistent(current_ir_graph);
+ /* TODO Are they really inconsistent (ins set with firm functions)? */
+ set_irg_outs_inconsistent(current_ir_graph);
DEL_ARR_F(cur_loop_outs);
+}
+
+/* Loop inversion */
+void loop_inversion(void)
+{
+ unsigned do_inversion = 1;
+
+ head_inversion_node_limit = 13371337;
+
+#if 0
+ /* unsigned max_loop_opnodes = 2000000; */
+ /*unsigned max_opnodes = 1337;*/
- /* Loop inversion */
- /* Search for condition chains. We may not do this before peeling, as peeling changes things. */
+ /* Loop complexity too high */
+ if (loop_info.opnodes_n > max_opnodes)
+ return;
+#endif
+
+
+ /* Search for condition chains. */
ir_reserve_resources(current_ir_graph, IR_RESOURCE_BLOCK_MARK);
- irg_walk_graph(current_ir_graph, unmark_block, NULL, NULL);
- cond_chain_entries = NEW_ARR_F(out_edges, 0);
+ /* Did not work as expected */
+ /* irg_block_walk_graph(current_ir_graph, reset_block_mark, NULL, NULL); */
+
+ irg_walk_graph(current_ir_graph, reset_block_mark, NULL, NULL);
+
+ loop_info.blocks = get_loop_n_blocks(cur_loop);
+ cond_chain_entries = NEW_ARR_F(out_edge, 0);
+
head_inversion_node_count = 0;
- inc_irg_visited(current_ir_graph);
+ head_inversion_block_count = 0;
+
set_Block_mark(loop_cf_head, 1);
mark_irn_visited(loop_cf_head);
- /* find condition chains */
- condition_chains(loop_cf_head);
+ inc_irg_visited(current_ir_graph);
+
+ find_condition_chains(loop_cf_head);
- // TODO assume number of phis to be created. prevent inversion...
+ /* TODO assume number of phis to be created. prevent inversion in case ...*/
- /* Loop inversion */
+ DB((dbg, LEVEL_1, "Loop contains %d blocks.\n", loop_info.blocks));
if (loop_info.blocks < 2) {
do_inversion = 0;
- DB((dbg, LEVEL_2, "Loop contains %d (less than 2) blocks => No Inversion done.\n", loop_info.blocks));
+ DB((dbg, LEVEL_1, "Loop contains %d (less than 2) blocks => No Inversion done.\n", loop_info.blocks));
+ }
+
+ /* We catch endless loops here too,
+ * because they do not have a condition chain. */
+ if (head_inversion_block_count < 1) {
+ do_inversion = 0;
+ DB((dbg, LEVEL_1, "Loop contains %d (less than 1) invertible blocks => No Inversion done.\n", head_inversion_block_count));
}
if (do_inversion) {
- cur_head_outs = NEW_ARR_F(out_edges, 0);
+ cur_head_outs = NEW_ARR_F(out_edge, 0);
/* get all edges pointing into the head or condition chain */
- irg_walk_graph(current_ir_graph, get_head_entries, NULL, NULL);
-
- loop_inversion_walk(cur_head_outs);
+ irg_walk_graph(current_ir_graph, get_head_outs, NULL, NULL);
+ inversion_walk(cur_head_outs);
DEL_ARR_F(cur_head_outs);
- }
- DEBUG_ONLY(dump_ir_block_graph(current_ir_graph, "-inversed2"));
+ set_irg_doms_inconsistent(current_ir_graph);
+ /* TODO needed? */
+ set_irg_loopinfo_inconsistent(current_ir_graph);
+ /* TODO Are they really inconsistent (ins set with firm functions)? */
+ set_irg_outs_inconsistent(current_ir_graph);
+ }
/* FREE */
DEL_ARR_F(cond_chain_entries);
}
/* */
-static void analyze_loop(ir_loop *loop)
+static void init_analyze(ir_loop *loop)
{
/* Init new for every loop */
cur_loop = loop;
loop_info.stores = 0;
loop_info.opnodes_n = 0;
loop_info.blocks = 0;
+ loop_info.outs = 0;
DB((dbg, LEVEL_1, " >>>> current loop includes node %ld <<<\n", get_irn_node_nr(get_loop_node(loop, 0))));
- decision_maker();
+ irg_walk_graph(current_ir_graph, get_loop_info, NULL, NULL);
- DB((dbg, LEVEL_1, " <<<< end of loop with node %ld >>>>\n", get_irn_node_nr(get_loop_node(loop, 0))));
+ /* RETURN if there is no valid head */
+ if (!loop_cf_head || !loop_cf_head_valid) {
+ DB((dbg, LEVEL_1, "\n**************************************************\n"));
+ DB((dbg, LEVEL_1, "* No valid loop head. Nothing done. *\n"));
+ DB((dbg, LEVEL_1, "**************************************************\n"));
+ return;
+ }
+
+ if (enable_peeling)
+ loop_peeling();
+ if (enable_inversion)
+ loop_inversion();
+
+ /* TODO uncomment lat0r */
+#if 0
+ /* RETURN if there is a call in the loop */
+ if (loop_info.calls)
+ return;
+#endif
+
+ DB((dbg, LEVEL_1, " <<<< end of loop with node %ld >>>>\n", get_irn_node_nr(get_loop_node(loop, 0))));
}
/* Find most inner loops and send them to analyze_loop */
-static void analyze_inner_loop(ir_loop *loop)
+static void find_most_inner_loop(ir_loop *loop)
{
/* descend into sons */
int sons = get_loop_n_sons(loop);
- if (sons==0) {
- analyze_loop(loop);
+ /*DBG((dbg, LEVEL_5, "current loop head %ld is done %d\n",
+ * get_loop_node(loop, 0)->node_nr, get_node_info(get_loop_node(loop, 0))->done );*/
+
+ if (sons == 0) {
+ loop_element elem;
+ int el_n, i;
+
+ el_n = get_loop_n_elements(loop);
+
+ for (i=0; i < el_n; ++i)
+ {
+ elem = get_loop_element(loop, i);
+ /* We can only rely on the blocks,
+ * as the loop attribute of the nodes seems not to be set. */
+ if (is_ir_node(elem.kind) && is_Block(elem.node)) {
+ ARR_APP1(ir_node *, loops, elem.node);
+ DB((dbg, LEVEL_1, "Found most inner loop (contains block %+F)\n", elem.node));
+ break;
+ }
+ }
+ /*init_analyze(loop);
+ return loop;*/
} else {
int s;
for(s=0; s<sons; s++) {
- analyze_inner_loop( get_loop_son(loop, s) );
+ find_most_inner_loop(get_loop_son(loop, s));
}
}
}
+
/**
*
*/
void loop_optimization(ir_graph *irg)
{
ir_loop *loop;
- int sons, nr;
-
- DB((dbg, LEVEL_1, " >>> loop optimization (Startnode %ld) <<<\n", get_irn_node_nr(get_irg_start(irg))));
+ int sons, nr;
/* Init */
link_node_state_list = NULL;
+ set_current_ir_graph(irg);
/* preconditions */
+ edges_assure(irg);
+ assure_irg_outs(irg);
+ /* NOTE: sets only the loop attribute of blocks, not nodes */
+ /* NOTE: Kills links */
+ assure_cf_loop(irg);
+
ir_reserve_resources(irg, IR_RESOURCE_IRN_LINK|IR_RESOURCE_PHI_LIST);
collect_phiprojs(irg);
ir_free_resources(irg, IR_RESOURCE_IRN_LINK);
- set_current_ir_graph(irg);
- assure_cf_loop(irg);
-
/* allocate node_info for additional information on nodes */
ir_reserve_resources(irg, IR_RESOURCE_IRN_LINK);
- irg_walk_graph(current_ir_graph, alloc_node_info, NULL, NULL);
+ /* irg_walk_graph(current_ir_graph, alloc_node_info, NULL, NULL); */
loop = get_irg_loop(irg);
sons = get_loop_n_sons(loop);
+ /**
+ * assure_cf_loop() creates a completely new loop tree every time.
+ * Thus we cannot optimize the loop, assure_cf_loop and continue with the next loop,
+ * as the next loop must be searched with a new search and is not distinguishable from the
+ * already done loop.
+ * The links of the loops are also not available anymore (to store a "loop done" flag).
+ * Therefore we save a block per loop.
+ * We rely on the loop optimizations not to remove any block from the loop.
+ * Later, we fetch the blocks loop attribute, as it is updated by assure_cf_loop.
+ * TODO Try to not destroy these informations.
+ */
+ loops = NEW_ARR_F(ir_node *, 0);
+
for (nr=0; nr<sons; nr++) {
- analyze_inner_loop(get_loop_son(loop, nr));
+ find_most_inner_loop(get_loop_son(loop, nr));
}
+ int i;
+ for(i=0; i< ARR_LEN(loops); ++i) {
+ ir_loop *loop;
+
+ /* not that efficient */
+ free_node_info();
+ ir_free_resources(irg, IR_RESOURCE_IRN_LINK);
+
+ /* TODO needed ? */
+ edges_assure(current_ir_graph);
+ assure_irg_outs(current_ir_graph);
+
+ /* NOTE: sets only the loop attribute of blocks */
+ /* NOTE: Kills links */
+ /* TODO Try not to destroy backedge info. */
+ assure_cf_loop(current_ir_graph);
+
+ /*construct_backedges(current_ir_graph);*/
+
+ /* not that efficient either... */
+ irg_walk_graph(current_ir_graph, alloc_node_info, NULL, NULL);
+ ir_reserve_resources(irg, IR_RESOURCE_IRN_LINK);
+
+ loop = get_irn_loop(loops[i]);
+ init_analyze(loop);
+ }
+
+ DEL_ARR_F(loops);
+
/* Free */
free_node_info();
- ir_free_resources(irg, IR_RESOURCE_PHI_LIST|IR_RESOURCE_IRN_LINK);
+ ir_free_resources(irg, IR_RESOURCE_IRN_LINK);
+ ir_free_resources(irg, IR_RESOURCE_PHI_LIST);
+}
- DB((dbg, LEVEL_1, " >>> loop optimization done (Startnode %ld)<<<\n", get_irn_node_nr(get_irg_start(irg))));
+void do_loop_inversion(ir_graph *irg)
+{
+ enable_peeling = 0;
+ enable_inversion = 1;
+
+ DB((dbg, LEVEL_1, " >>> inversion (Startnode %ld) <<<\n",
+ get_irn_node_nr(get_irg_start(irg))));
+
+ loop_optimization(irg);
+
+ DB((dbg, LEVEL_1, " >>> inversion done (Startnode %ld) <<<\n",
+ get_irn_node_nr(get_irg_start(irg))));
}
-void firm_init_loop(void) {
+void do_loop_peeling(ir_graph *irg)
+{
+ enable_peeling = 1;
+ enable_inversion = 0;
+
+ (void)irg;
+
+ DB((dbg, LEVEL_1, " >>> peeling is disabled atm. <<<\n"));
+
+ /*
+ DB((dbg, LEVEL_1, " >>> peeling (Startnode %ld) <<<\n",
+ get_irn_node_nr(get_irg_start(irg))));
+
+ loop_optimization(irg);
+
+ DB((dbg, LEVEL_1, " >>> peeling done (Startnode %ld) <<<\n",
+ get_irn_node_nr(get_irg_start(irg))));
+ */
+}
+
+void firm_init_loop_opt(void)
+{
FIRM_DBG_REGISTER(dbg, "firm.opt.loop");
}
projects / libfirm / blobdiff