* 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
+#ifdef HAVE_MALLOC_H
+#include <malloc.h>
+#endif
+#ifdef HAVE_ALLOCA_H
+#include <alloca.h>
+#endif
# include "loop_unrolling.h"
# include "irgopt_t.h"
# include "irnode_t.h"
# include "irouts.h"
+# include "trouts.h"
# include "hashptr.h"
# include "pset.h"
# include "strength_red.h"
/* We will unroll maximal 4-times. */
#define MAX_UNROLL 4
-/*We will know if the head of the loop to be copy.
+/* We will know if the head of the loop to be copy.
* Default "0" don't copy.*/
static int copy_loop_head;
/**
* Remember the new node in the old node by using a field all nodes have.
*/
-
static INLINE void
set_new_node (ir_node *old, ir_node *new)
{
* @param n The node to be copied
* @param env if non-NULL, the node number attribute will be copied to the new node
*/
-
static void
copy_node (ir_node *n, void *env)
{
- ir_node *nn, *block;
+ ir_node *nn;
int new_arity;
- opcode op = get_irn_opcode(n);
+ ir_op *op = get_irn_op(n);
int copy_node_nr = false;
/* The end node looses it's flexible in array. This doesn't matter,
as dead node elimination builds End by hand, inlineing doesn't use
the End node. */
- /* assert(n->op == op_End || ((_ARR_DESCR(n->in))->cookie != ARR_F_MAGIC)); */
+ /* assert(op == op_End || ((_ARR_DESCR(n->in))->cookie != ARR_F_MAGIC)); */
- if (op == iro_Bad)
+ if (op == op_Bad)
/* node copied already */
return;
nn = new_ir_node(get_irn_dbg_info(n),
current_ir_graph,
- block,
- get_irn_op(n),
+ NULL, /* no block yet, will be set later */
+ op,
get_irn_mode(n),
new_arity,
get_irn_in(n));
}
/*Check if phi in the loop head is.
*
- * @param *phi Muss to be a phi node from the loop.
- * @param *loop_head The loop head .
+ * @param phi Must be a phi node from the loop.
+ * @param loop_head The loop head .
*/
static int is_Phi_in_loop_head(ir_node *phi, ir_node *loop_head) {
assert(is_Block(loop_head));
* If the predecessor is a loop invariant, then the copy get it
* as predecessor, else the copy of the predecessor.
*
- * @param *l_n A set, where the node of the loop are saved.
- * @param *value A element of the set.
- * @param *info Contains information about the induction variable.
- * @param *unroll_factor A integer 2 <= unroll_factor <= 4.
- * @param *env Free environment pointer.
+ * @param l_n A set, where the node of the loop are saved.
+ * @param value A element of the set.
+ * @param info Contains information about the induction variable.
+ * @param unroll_factor A integer 2 <= unroll_factor <= 4.
+ * @param env Free environment pointer.
*/
static void
set_preds (set *l_n, copies_t *value, induct_var_info *info, int unroll_factor, void *env)
if (value->irn != loop_head && !is_Phi_in_loop_head(value->irn, loop_head)) {
if (value_pred == NULL) {
- /* Is loop invariant. */
- for(p = 0; p < unroll_factor -1; p++)
- set_irn_n (value->copy[p], i, pred);
- // pred is a loop invariant. The copies of the successors get it as predecessor.
-
- } else
- for(p = 0; p < unroll_factor -1; p++)
- set_irn_n (value->copy[p], i, value_pred->copy[p]);
- /* value_pred->irn is a node from the unrolling loop. The copies of the successors get the
- copies of value_pred as predecessor.*/
+ /* Is loop invariant. */
+ for (p = 0; p < unroll_factor - 1; p++)
+ set_irn_n(value->copy[p], i, pred);
+ /* pred is a loop invariant. The copies of the successors get it as predecessor. */
+ }
+ else {
+ for (p = 0; p < unroll_factor - 1; p++)
+ set_irn_n(value->copy[p], i, value_pred->copy[p]);
+ /* value_pred->irn is a node from the unrolling loop.
+ * The copies of the successors get the
+ * copies of value_pred as predecessor.
+ */
+ }
}
}
}
/* Set the backedge of phi in the loop head.The backedge of phis in the loop head
* must now point to the value defined
- * in the last copie of the loop body.
+ * in the last copy of the loop body.
*
- * @param *l_n A set, where the node of the loop are saved.
- * @param *value A phi in the loop head.
- * @param *info Contains information about the induction variable.
- * @param *unroll_factor A integer 2 <= unroll_factor <= 4.
+ * @param l_n A set, where the node of the loop are saved.
+ * @param value A phi in the loop head.
+ * @param info Contains information about the induction variable.
+ * @param unroll_factor A integer 2 <= unroll_factor <= 4.
*/
static void
set_phi_backedge(set *l_n, copies_t *value, induct_var_info *info, int unroll_factor)
{
copies_t key, *value_pred;
- /*info->op_pred_pos is the backedge position. */
+
+ /* info->op_pred_pos is the backedge position. */
key.irn = get_irn_n(value->irn, info->op_pred_pos);
value_pred = set_find(l_n, &key, sizeof(key), HASH_PTR(key.irn));
- /*value->copy[unroll_factor - 2] is the last copie. */
+ /* value->copy[unroll_factor - 2] is the last copy. */
set_Phi_pred(value->irn, info->op_pred_pos, value_pred->copy[unroll_factor - 2]);
}
-/** Test for a loop head.
+/**
+ * Test for a loop head.
*
- * Returns true if the node has predecessors in the loop _and_ out of
- * the loop. Then it is a loop head: The loop can be entered through
- * this node.
+ * Returns true if the node has predecessors in the loop _and_ out of
+ * the loop. Then it is a loop head: The loop can be entered through
+ * this node.
*
- * @param *n The node to be tested. Muss be a block.
- * @param *info Contains the loop information.
+ * @param n The node to be tested. Must be a block.
+ * @param info Contains the loop information.
*/
static int
is_loop_head(ir_node *n, induct_var_info *info)
}
-/** Test wether the passed loop is a natural loop.
+/**
+ * Test whether the passed loop is a natural loop.
*
* Returns true if the loop has only one loop header and only a single
* back edge.
*
- * @param *info Contains the loop information.
+ * @param info Contains the loop information.
*/
static int
-is_natural_loop ( induct_var_info *info)
+is_natural_loop(induct_var_info *info)
{
ir_node *l_node;
int l_n_node = 0, i;
+
l_n_node = get_loop_n_nodes (info->l_itervar_phi);
for (i = 1; i < (l_n_node); i ++) {
return 1;
}
-/** Serch for all nodes of a loop.
+/**
+ * Search for all nodes of a loop.
*
- * @param *node The induction variable of the loop.
- * @param *loop_head The head of the loop.
- * @param *l_n A set, where the node of the loop are saved.
+ * @param node The induction variable of the loop.
+ * @param loop_head The head of the loop.
+ * @param l_n A set, where the node of the loop are saved.
*/
static void
find_loop_nodes(ir_node *node, ir_node *loop_head, set *l_n)
/* Add this node to the list. */
key.irn = node;
- for(i = 0; i < 4 ;i++)
- /* Initialize all copies of the added node with NULL.*/
+
+ /* Initialize all copies of the added node with NULL.*/
+ for (i = 0; i < 4; ++i)
key.copy[i] = NULL;
value = set_insert(l_n, &key, sizeof(key), HASH_PTR(key.irn));
/* Add all outs of this node to the list, if they are within the loop. */
- for (i = get_irn_n_outs(node) - 1; i >= 0; i--) {
+ for (i = get_irn_n_outs(node) - 1; i >= 0; --i) {
ir_node *pred = get_irn_out(node, i);
+
key.irn = pred;
if (!is_loop_invariant(pred, loop_head) &&
- set_find( l_n, &key, sizeof(key), HASH_PTR(key.irn)) == NULL ) {
+ set_find( l_n, &key, sizeof(key), HASH_PTR(key.irn)) == NULL ) {
find_loop_nodes(pred, loop_head, l_n);
}
}
/* Add all ins if they are within the loop. */
- for(i = get_irn_arity(node) -1; i >=0; i--) {
+ for (i = get_irn_arity(node) - 1; i >=0; --i) {
ir_node *pred = get_irn_n(node, i);
+
key.irn = pred;
if (!is_loop_invariant(pred, loop_head) &&
- set_find( l_n, &key, sizeof(key), HASH_PTR(key.irn)) == NULL ){
+ set_find( l_n, &key, sizeof(key), HASH_PTR(key.irn)) == NULL ) {
find_loop_nodes(pred, loop_head, l_n);
}
}
}
-/* Make a new loop head if copy_loop_head = 1.
+/**
+ * Make a new loop head if copy_head = 1.
*
- * @param *l_n A set, where the node of the loop are saved.
- * @param *info Contains the loop information.
- * @param *value A element of the set.
- * @param *unroll_factor A integer 2 <= unroll_factor <= 4.
+ * @param l_n A set, where the node of the loop are saved.
+ * @param info Contains the loop information.
+ * @param value A element of the set.
+ * @param unroll_factor A integer 2 <= unroll_factor <= 4.
+ * @param copy_head if non-zero, the loop head will be copied
*
*/
static void
-new_loop_head (set *l_n, induct_var_info *info, copies_t *value, int unroll_factor)
+new_loop_head(set *l_n, induct_var_info *info, copies_t *value, int unroll_factor, int copy_head)
{
int i;
copies_t block, *value_backedge_jmp, *backedge_jmp_block;
- /* The predecessor of the loop head in the backedge position*/
+ /* The predecessor of the loop head in the backedge position */
ir_node *backedge_jmp = get_Block_cfgpred(value->irn, info->op_pred_pos);
- block.irn = backedge_jmp;
- value_backedge_jmp = set_find( l_n, &block, sizeof(block), HASH_PTR(block.irn));
+ block.irn = backedge_jmp;
+ value_backedge_jmp = set_find(l_n, &block, sizeof(block), HASH_PTR(block.irn));
- if(copy_loop_head){
- /* The first copy of the loop head muss point to the loop head.*/
- ir_node *new_loop_head = new_Block(1, &backedge_jmp);
- value->copy[0] = new_loop_head;
+ if (copy_head) {
+ /* The first copy of the loop head must point to the loop head.*/
+ value->copy[0] = new_Block(1, &backedge_jmp);
- for(i = 1; i<unroll_factor - 1; i++){
- /* The another copies muss point to the copy befor it in the array. */
- ir_node *new_loop_head = new_Block(1, &value_backedge_jmp->copy[i-1]);
- value->copy[i] = new_loop_head;
+ for (i = 1; i < unroll_factor - 1; ++i) {
+ /* all other copies must point to the copy before it in the array. */
+ value->copy[i] = new_Block(1, &value_backedge_jmp->copy[i-1]);
}
- }else{
- /* If the loop haed muss't be copy. block.irn is the successor of the loop head.*/
- block.irn = get_nodes_block(backedge_jmp);
- backedge_jmp_block = set_find( l_n, &block, sizeof(block), HASH_PTR(block.irn));
- /*The first copy of block.irn point to it.
- The another copies muss point to the copy befor it in the array.*/
+ }
+ else {
+ /* If the loop head must not be copy. block.irn is the successor of the loop head.*/
+ block.irn = get_nodes_block(backedge_jmp);
+ backedge_jmp_block = set_find(l_n, &block, sizeof(block), HASH_PTR(block.irn));
+
+ /* The first copy of block.irn point to it.
+ The another copies muss point to the copy before it in the array.*/
set_irn_n(backedge_jmp_block->copy[0], 0, value_backedge_jmp->irn) ;
- for(i = 1; i<unroll_factor - 1; i++)
+ for (i = 1; i < unroll_factor - 1; ++i)
set_irn_n(backedge_jmp_block->copy[i], 0, value_backedge_jmp->copy[i - 1]);
}
-
}
/* Set all copies of the induction variable.
*
- * @param *phi A phi node in the loop head block.
- * @param *phi_pred The predecessor of the phi along the backedge.
- * @param *unroll_factor A integer 2 <= unroll_factor <= 4.
- *
+ * @param phi A phi node in the loop head block.
+ * @param phi_pred The predecessor of the phi along the backedge.
+ * @param unroll_factor A integer 2 <= unroll_factor <= 4.
*/
static void
set_Phi_copies(copies_t *phi, copies_t *phi_pred, int unroll_factor)
{
int p;
+
/* The first copy of Phi node get the node along the backedge as predecessor. The next copies
the copies of this node.*/
phi->copy[0] = phi_pred->irn;
- for(p = 1; p < unroll_factor -1; p++){
- // If two phi nodes are in cycle.
- if(phi_pred->copy[p - 1] == NULL && get_irn_op(phi_pred->irn) == op_Phi){
- if(p % 2 != 0)
- phi->copy[p] = phi->irn;
+ for (p = 1; p < unroll_factor - 1; ++p) {
+ /* If two phi nodes are in cycle. */
+ if (phi_pred->copy[p - 1] == NULL && get_irn_op(phi_pred->irn) == op_Phi) {
+ if (p & 1)
+ phi->copy[p] = phi->irn;
else
- phi->copy[p] = phi_pred->irn;
- }else
- phi->copy[p] = phi_pred->copy[p -1];
+ phi->copy[p] = phi_pred->irn;
+ } else
+ phi->copy[p] = phi_pred->copy[p - 1];
}
}
-/* Decide if the loop head to be copy. A head with important nodes
- * muss be copy.
+/**
+ * Decide if the loop head must be copied. A head with important nodes
+ * must be copied.
*
- * @param *l_n A set, where the node of the loop are saved.
- * @param *info Contains information about the induction variable.
+ * @param l_n A set, where the node of the loop are saved.
+ * @param info Contains information about the induction variable.
+ *
+ * @return non-zero if the loop head must be copied
*/
-static void
+static int
loop_head_nodes(set *l_n, induct_var_info *info)
{
+ int must_copy = 0;
copies_t *value;
ir_node *loop_head = get_loop_node(info->l_itervar_phi, 0);
for (value = set_first(l_n); value != NULL; value = set_next(l_n))
- if(value->irn->op != op_Block &&
- get_nodes_block(value->irn) == loop_head)
- /* If the loop head contains just this nodes, than muss't be copy. */
- switch(get_irn_opcode(value->irn)) {
+ if (is_no_Block(value->irn) && get_nodes_block(value->irn) == loop_head)
+ /* If the loop head contains just this nodes, than must not be copy. */
+ switch (get_irn_opcode(value->irn)) {
case iro_Cond:
- break;
+ break;
case iro_Phi:
- break;
+ break;
case iro_Proj:
- break;
+ break;
case iro_Const:
- break;
+ break;
case iro_Cmp:
- break;
+ break;
default:
- copy_loop_head = 1;
+ must_copy = 1;
}
+ return must_copy;
}
/** Copy all loop nodes.
*
- * @param *l_n Contains all nodes of the loop.
- * @param *info Contains the loop information.
- * @param *unroll_factor A integer 2 <= unroll_factor <= 4.
+ * @param l_n Contains all nodes of the loop.
+ * @param info Contains the loop information.
+ * @param unroll_factor A integer 2 <= unroll_factor <= 4.
*/
static void
copy_loop_body(set *l_n, induct_var_info *info, int unroll_factor)
{
int i;
- copies_t *value, *info_op, *phi, *loop_h, key, *value_block;
+ copies_t *value, *info_op, *phi, *loop_h = NULL, key, *value_block;
ir_node *loop_head = get_loop_node(info->l_itervar_phi, 0);
-
for (value = set_first(l_n); value != NULL; value = set_next(l_n)) {
if(value->irn == loop_head)
loop_h = value;
else if (is_Phi_in_loop_head(value->irn, loop_head))
phi = value;
- else if(copy_loop_head){
- /* If the loop head muss be copy. */
+ else if (copy_loop_head){
+ /* The loop head must be copied. */
for (i = 0; i < unroll_factor - 1; i++){
- copy_node(value->irn, NULL);
- value->copy[i] = get_irn_link(value->irn);
+ copy_node(value->irn, NULL);
+ value->copy[i] = get_irn_link(value->irn);
}
} else {
- /* If the loop head and its nodes muss't be copy. */
+ /* The loop head and its nodes must not be copied. */
if((value->irn->op == op_Block &&
- value->irn != loop_head) ||
- (value->irn->op != op_Block &&
- get_nodes_block(value->irn) != loop_head))
- for (i = 0; i<unroll_factor -1; i++){
- copy_node(value->irn, NULL);
- value->copy[i] = get_irn_link(value->irn);
- }
+ value->irn != loop_head) ||
+ (value->irn->op != op_Block &&
+ get_nodes_block(value->irn) != loop_head)) {
+ for (i = 0; i<unroll_factor -1; i++){
+ copy_node(value->irn, NULL);
+ value->copy[i] = get_irn_link(value->irn);
+ }
+ }
}
}
/* Treat the loop head block */
- new_loop_head (l_n, info, loop_h, unroll_factor);
+ new_loop_head(l_n, info, loop_h, unroll_factor, copy_loop_head);
- /* Similarily treat the Phis in the loop head block. info->op is the node
- along the backadge.*/
+ /* Similarly treat the Phis in the loop head block. info->op is the node
+ along the backedges. */
key.irn = info->op;
info_op = set_find( l_n, &key, sizeof(key), HASH_PTR(key.irn));
assert(info_op->irn == get_Phi_pred(info->itervar_phi, info->op_pred_pos));
ir_node *phi = get_irn_out(loop_head, i);
if (is_Phi(phi)) {
- key.irn = get_Phi_pred(phi, info->op_pred_pos); // info->op;
- copies_t *phi_pred = set_find(l_n, &key, sizeof(key), HASH_PTR(key.irn));
- key.irn = phi;
- copies_t *phi_op = set_find(l_n, &key, sizeof(key), HASH_PTR(key.irn));
+ copies_t *phi_pred, *phi_op;
+
+ key.irn = get_Phi_pred(phi, info->op_pred_pos); // info->op;
+ phi_pred = set_find(l_n, &key, sizeof(key), HASH_PTR(key.irn));
+ key.irn = phi;
+ phi_op = set_find(l_n, &key, sizeof(key), HASH_PTR(key.irn));
set_Phi_copies(phi_op, phi_pred, unroll_factor);
}
}
-
for (value = set_first(l_n); value != NULL; value = set_next(l_n)) {
/* Set the predecessors of the copies. */
- if(copy_loop_head)
+ if (copy_loop_head)
set_preds(l_n, value, info, unroll_factor, NULL);
- else if((value->irn->op != op_Block) && get_nodes_block(value->irn) != loop_head)
+ else if ((value->irn->op != op_Block) && get_nodes_block(value->irn) != loop_head)
set_preds(l_n, value, info, unroll_factor, NULL);
if (is_Phi_in_loop_head(value->irn, loop_head))
if ((value->irn->op != op_Block) && !is_Phi_in_loop_head(value->irn, loop_head)) {
ir_node *nodes_block = get_nodes_block(value->irn);
- if(!copy_loop_head && nodes_block == loop_head)
- continue;
+ if (!copy_loop_head && nodes_block == loop_head)
+ continue;
key.irn = nodes_block;
value_block = set_find( l_n, &key, sizeof(key), HASH_PTR(key.irn));
/* Set the copy of the node in the accordant copy of its block. */
for(i = 0; i < unroll_factor - 1; i++){
- set_nodes_block(value->copy[i], value_block->copy[i]);
- //add_End_keepalive(get_irg_end(current_ir_graph), value->copy[p]);
+ set_nodes_block(value->copy[i], value_block->copy[i]);
+ //add_End_keepalive(get_irg_end(current_ir_graph), value->copy[p]);
}
}
}
}
-/** is_exception_possible
+/**
+ * Returns non-zero if a Proj node from the loop has a predecessor that
+ * can throw an exception.
*
- * If a Proj node from the loop have as predecessor a Call, Div or Load node, then is a
- * exception possible.
+ * @param node A Proj node from the loop.
*
- * @param *node A Proj node form the loop.
+ * @return non-zero if the predecessor of the Proj node can throw an exception
*/
-static int
-is_exception_possible(ir_node *node)
+static int is_exception_possible(ir_node *node)
{
- int possible = 1;
ir_node *pred = get_Proj_pred(node);
- switch(get_irn_opcode(pred)){
- case iro_Call:
- break;
- case iro_Div:
- break;
- case iro_Load:
- break;
- default:
- possible = 0;
- }
+ /* only fragile ops can throw an exception */
+ if (! is_fragile_op(pred))
+ return 0;
- return possible;
+ /*
+ * fragile ops that are known NOT to throw
+ * an exception if their pin_state is op_pin_state_floats
+ */
+ return get_irn_pinned(pred) != op_pin_state_floats;
}
-
-/** new_end_block
- *
- * If a node from the loop is predecessor of the end block,then muss have the end block all copies
- * of this node as predecessors.This is possible with funktions calls in the unrolling loop.
+/**
+ * If a node from the loop is predecessor of the end block, then the end block must get all copies
+ * of this node as predecessors. This is possible with function calls in the unrolling loop.
*
- * @param *end_block The end block.
- * @param *loop_head The head of the unrolling loop.
- * @param *l_n Contains all nodes of the loop.
- * @param *loop_endblock_outs The set loop_endblock_outs contains all predecessors
- * of the end block from the unrolling loop.
- * @param *unroll_factor A integer 2 <= unroll_factor <= 4.
+ * @param end_block The end block.
+ * @param loop_head The head of the unrolling loop.
+ * @param l_n Contains all nodes of the loop.
+ * @param loop_endblock_outs The set loop_endblock_outs contains all predecessors
+ * of the end block from the unrolling loop.
+ * @param unroll_factor A integer 2 <= unroll_factor <= 4.
*/
-
static void
-new_end_block (ir_node* end_block,ir_node *loop_head, set *l_n, set *loop_endblock_outs, int unroll_factor)
+new_end_block(ir_node *end_block, ir_node *loop_head, set *l_n, set *loop_endblock_outs, int unroll_factor)
{
-
copies_t key, *value;
int set_el, new_preds, all_new_preds, i, q;
- int old_preds = get_Block_n_cfgpreds(end_block); // All old predecessors of the end block.
+ int old_preds = get_Block_n_cfgpreds(end_block); /* All old predecessors of the end block. */
+ ir_node **all_in;
- for(int i = 0; i < old_preds; i++){
+ for (i = 0; i < old_preds; i++) {
ir_node *pred = get_Block_cfgpred(end_block, i);
key.irn = pred;
value = NULL;
value = set_find( l_n, &key, sizeof(key), HASH_PTR(key.irn));
- // If a predecessor of the end block is a Proj from the unrolling loop (for funktion calls) .
- if( get_irn_op(pred) == op_Proj && is_exception_possible(pred) && value != NULL &&
- !(!copy_loop_head && get_nodes_block(pred) == loop_head))
- value = set_insert(loop_endblock_outs, &key, sizeof(key), HASH_PTR(key.irn));
+
+ /* If a predecessor of the end block is a Proj from the unrolling loop (for function calls) .*/
+ if (get_irn_op(pred) == op_Proj && is_exception_possible(pred) && value != NULL &&
+ !(!copy_loop_head && get_nodes_block(pred) == loop_head))
+ value = set_insert(loop_endblock_outs, &key, sizeof(key), HASH_PTR(key.irn));
}
- /* The set loop_endblock_outs contains all predecessors of the end block from the unrolling loop.
- set_el their number.*/
- set_el = set_count (loop_endblock_outs);
- // If the end block haven't such predecessors.Nothing muss be do.
+
+ /* The set loop_endblock_outs contains all predecessors of the end block from the unrolling loop,
+ * set_el the amount of such nodes.
+ */
+ set_el = set_count (loop_endblock_outs);
+
+ /* If the end block haven't such predecessors, we are finished. */
if (!set_el) return;
- new_preds = (unroll_factor - 1) * set_el; //All new predecessors of the end block.
- all_new_preds = old_preds + new_preds; //All predecessors of this block.
- ir_node *all_in[all_new_preds]; //A array with size for all predecessors of this block.
+ new_preds = (unroll_factor - 1) * set_el; /* All new predecessors of the end block */
+ all_new_preds = old_preds + new_preds; /* All predecessors of this block. */
+ all_in = alloca(sizeof(*all_in) * all_new_preds); /* A array with size for all predecessors of this block. */
for (i = 0; i < old_preds; i++)
- all_in[i] = get_Block_cfgpred(end_block, i); // The old predecessors.
+ all_in[i] = get_Block_cfgpred(end_block, i); /* The old predecessors. */
value = set_first(loop_endblock_outs);
- for( ; value != NULL; value = set_next(loop_endblock_outs)){
+ for (; value != NULL; value = set_next(loop_endblock_outs)) {
key.irn = value->irn;
value = set_find( l_n, &key, sizeof(key), HASH_PTR(key.irn));
- for(q = 0; q < unroll_factor - 1 ; q++){
- all_in[i] = value->copy[q];
- i++; // The new predecessors.
+ for (q = 0; q < unroll_factor - 1 ; q++) {
+ all_in[i++] = value->copy[q]; /* The new predecessors. */
}
}
- /* Replace the old predecessors of the end block whit the new one. */
+
+ /* Replace the old predecessors of the end block wit´h the new ones. */
set_irn_in(end_block, all_new_preds, all_in);
}
/** new_after_loop_block
*
- * This after loop block muss examine the possible exceptions in the loop.If a (Proj) node from the loop
- * is predecessor of this block,then muss have the after loop block as well all copies
- * of this node as predecessors.
+ * The after loop block must examine the possible exceptions in the loop.
+ * If a (Proj) node from the loop is predecessor of this block, then the
+ * after loop block must have as well all copies of this node as predecessors.
*
- * @param *l_n Contains all nodes of the loop.
- * @block *block A block afte the loop.
- * @param *loop_in A node from the loop, that is predecessor of the end block.
- * @param *unroll_factor A integer 2 <= unroll_factor <= 4.
+ * @param l_n Contains all nodes of the loop.
+ * @block block A block after the loop.
+ * @param loop_in A node from the loop, that is predecessor of the end block.
+ * @param unroll_factor An integer 2 <= unroll_factor <= 4.
*/
-
static void
new_after_loop_block (set *l_n, ir_node* block, copies_t *loop_in, int unroll_factor)
{
copies_t key, *value;
int i, p, q, s, old_preds, new_preds, all_new_preds ;
+ ir_node **all_in;
- // The node from the unrolling loop muss be a Proj.
- if(loop_in->irn->op != op_Proj) return;
+ /* The node from the unrolling loop must be a Proj. */
+ if (loop_in->irn->op != op_Proj) return;
- old_preds = get_Block_n_cfgpreds(block); // All old predecessors of this block.
- new_preds = old_preds * (unroll_factor - 1); //All new predecessors of this block.
- all_new_preds = old_preds + new_preds; //All predecessors of this block.
+ old_preds = get_Block_n_cfgpreds(block); /* All old predecessors of this block. */
+ new_preds = old_preds * (unroll_factor - 1); /* All new predecessors of this block. */
+ all_new_preds = old_preds + new_preds; /* All predecessors of this block. */
- ir_node *all_in[all_new_preds]; //A array with size for all predecessors of this block.
+ all_in = alloca(sizeof(*all_in) * all_new_preds); /* An array with size for all predecessors of this block. */
for (i = 0 ; i < old_preds; i++)
- all_in[i] = get_Block_cfgpred(block, i); //The old predecessors.
+ all_in[i] = get_Block_cfgpred(block, i); /* The old predecessors. */
q = old_preds;
- for(i = 0; i < old_preds; i++){
+ for (i = 0; i < old_preds; i++){
key.irn = all_in[i];
value = set_find( l_n, &key, sizeof(key), HASH_PTR(key.irn));
p = 0;
- for(s = 0; s < (unroll_factor - 1); s++){
- all_in[q] = value->copy[p]; //The new predecessors.
- p++;
- q++;
+ for (s = 0; s < (unroll_factor - 1); s++) {
+ all_in[q++] = value->copy[p++]; /* The new predecessors. */
}
-
}
/* Replace the old predecessors of the end block whit the new one. */
set_irn_in(block, all_new_preds, all_in);
/** new_after_loop_node
*
- * This after loop node (phi or call) muss examine the possible exceptions in the loop.If a (Proj) node
- * from the loop is predecessor of this node,then muss have the after loop node as well all copies
- * of this node as predecessors.
+ * An after loop node (phi or call) must examine the possible exceptions in the loop.
+ * If a (Proj) node from the loop is predecessor of this node, then the after loop
+ * node must have as well all copies of this node as predecessors.
*
- * @param *l_n Contains all nodes of the loop.
- * @param *loop_outs Contains nodes after the loop,that have as predecessor a node from the loop.
- * @block *node A node afte the loop.
- * @param *loop_in A node (Proj) from the loop, that is predecessor of *node.
- * @param *unroll_factor A integer 2 <= unroll_factor <= 4.
+ * @param l_n Contains all nodes of the loop.
+ * @param loop_outs Contains nodes after the loop,that have as predecessor a node from the loop.
+ * @block node A node after the loop.
+ * @param loop_in A node (Proj) from the loop, that is predecessor of *node.
+ * @param unroll_factor An integer 2 <= unroll_factor <= 4.
*/
-
static void
new_after_loop_node(set *l_n, set *loop_outs, ir_node *node, copies_t *loop_in, int unroll_factor)
{
- ir_node *pred, *block_pred, *node_block, *new_phi;
+ ir_node *pred, *block_pred = NULL, *node_block, *new_phi;
int phi = 0, old_preds, new_preds, all_new_preds, p, q, i, s;
copies_t key, *value = NULL;
-
- old_preds = get_irn_arity(node); // All old predecessors of this node.
- new_preds =old_preds * (unroll_factor - 1); //All new predecessors of this block.
- all_new_preds = old_preds + new_preds; //All predecessors of this block.
- ir_node *all_in [all_new_preds]; //A array with size for all predecessors of this block.
-
-
- // Verification Predecessors, successors and operation of node and loop_in.
- //loop_in muss be a Proj node.
- if(loop_in->irn->op != op_Proj) return;
- // Node muss be operation Phi with mode memory or a Call node.
- if(get_irn_op(node) == op_Phi &&
- get_irn_mode(node) == mode_M){
- // If node is a Phi node,then muss have a Call node as successor.
+ ir_node **all_in;
+
+ old_preds = get_irn_arity(node); /* All old predecessors of this node. */
+ new_preds =old_preds * (unroll_factor - 1); /* All new predecessors of this block. */
+ all_new_preds = old_preds + new_preds; /* All predecessors of this block. */
+
+ all_in = alloca(sizeof(*all_in) * all_new_preds); /* An array with size for all predecessors of this block. */
+
+ /* Verification Predecessors, successors and operation of node and loop_in.
+ * loop_in must be a Proj node.
+ */
+ if (loop_in->irn->op != op_Proj) return;
+ /* Node must be operation Phi with mode memory or a Call node. */
+ if (get_irn_op(node) == op_Phi &&
+ get_irn_mode(node) == mode_M){
+ /* If node is a Phi node,then must have a Call node as successor. */
for (i = 0; i < get_irn_n_outs(node); i++)
- if(get_irn_opcode(get_irn_out(node, i)) == iro_Call)
- phi = 1;
+ if (get_irn_op(get_irn_out(node, i)) == op_Call) {
+ phi = 1;
+ break;
+ }
if (!phi) return;
}
- // The predecessor of loop_in muss't be a loop invariant.
+
+ /* The predecessor of loop_in must not be a loop invariant. */
pred = get_Proj_pred(loop_in->irn);
key.irn = pred;
value = set_find( l_n, &key, sizeof(key), HASH_PTR(key.irn));
- if(value == NULL)return;
+ if (! value) return;
node_block = get_nodes_block(node);
- // The block of node muss have too a (Proj) predecessor from the unrolling loop.
- for(i = 0; i < get_Block_n_cfgpreds(node_block); i++){
- block_pred = get_Block_cfgpred( node_block, i);
+ /* The block of node must also have a (Proj) predecessor from the unrolling loop. */
+ for (i = 0; i < get_Block_n_cfgpreds(node_block); i++) {
+ block_pred = get_Block_cfgpred(node_block, i);
- if(get_irn_op(block_pred) == op_Proj){
- if(get_Proj_pred(block_pred) == pred)
+ if (get_irn_op(block_pred) == op_Proj) {
+ if (get_Proj_pred(block_pred) == pred)
break;
- }else
+ }
+ else {
block_pred = NULL;
+ }
}
- if(block_pred == NULL) return;
+ if (! block_pred) return;
key.irn = block_pred;
- value = set_find( l_n, &key, sizeof(key), HASH_PTR(key.irn));
+ value = set_find(l_n, &key, sizeof(key), HASH_PTR(key.irn));
- if (value == NULL)
+ if (! value)
return;
- else{
+ else
new_after_loop_block(l_n, node_block, value, unroll_factor);
- }
- i = 0, p = 0;
- for ( ; i < old_preds; i++)
- all_in[i] = get_irn_n(node, i); //The old predecessors.
+ for (i = 0; i < old_preds; ++i)
+ all_in[i] = get_irn_n(node, i); /* The old predecessors. */
- i = 0;
q = old_preds;
- for(; i < old_preds; i++){
+ for (i = 0; i < old_preds; ++i) {
key.irn = all_in[i];
value = set_find( l_n, &key, sizeof(key), HASH_PTR(key.irn));
p = 0;
- for(s = 0; s < (unroll_factor - 1); s++){
- all_in[q] = value->copy[p]; //The new predecessors.
+ for (s = 0; s < (unroll_factor - 1); ++s) {
+ all_in[q] = value->copy[p]; /* The new predecessors. */
p++;
q++;
}
}
- // A new phi node with the new predecessors.
- new_phi = new_r_Phi(current_ir_graph, get_nodes_block(node), all_new_preds,all_in,
+ /* A new phi node with the new predecessors. */
+ new_phi = new_r_Phi(current_ir_graph, get_nodes_block(node), all_new_preds,all_in,
get_irn_mode(node));
- if(phi){
+ if (phi)
exchange(node, new_phi);
- }else{
- i = 0;
- for( ; i < get_irn_arity(node) ; i++)
+ else{
+ for (i = 0; i < get_irn_arity(node); ++i)
if (get_irn_n(node, i) == pred)
- set_irn_n(node, i, new_phi);
+ set_irn_n(node, i, new_phi);
}
- // The set loop_outs contains the visited nodes and their blocks.
+
+ /* The set loop_outs contains the visited nodes and their blocks. */
key.irn = node;
value = set_insert(loop_outs, &key, sizeof(key), HASH_PTR(key.irn));
key.irn = get_nodes_block(node);
* point to the last copy of it. Just phi nodes in the loop head and proj
* nodes save it outs. The all copies of some Projs have too outs.
*
- * @param *l_n Contains all nodes of the loop.
- * @param *loop_outs The set contains the visited and changed loop outs.
- * @param *loop_endblock_outs The set loop_endblock_outs contains all predecessors
- * of the end block from the unrolling loop.
- * @param *info Contains the loop information.
- * @param *unroll_factor A integer 2 <= unroll_factor <= 4.
+ * @param l_n Contains all nodes of the loop.
+ * @param loop_outs The set contains the visited and changed loop outs.
+ * @param loop_endblock_outs The set loop_endblock_outs contains all predecessors
+ * of the end block from the unrolling loop.
+ * @param info Contains the loop information.
+ * @param unroll_factor A integer 2 <= unroll_factor <= 4.
*/
static void
-set_loop_outs(set *l_n,set * loop_outs, set *loop_endblock_outs,induct_var_info *info, int unroll_factor)
+set_loop_outs(set *l_n, set *loop_outs, set *loop_endblock_outs, induct_var_info *info, int unroll_factor)
{
copies_t *value, key;
int i, p;
ir_node *loop_head = get_loop_node(info->l_itervar_phi, 0);
ir_node *end_block = get_irg_end_block(current_ir_graph);
- value = set_first(l_n);
-
- for( ; value != NULL; value = set_next(l_n))
- if(!is_Phi_in_loop_head(value->irn, loop_head) &&
- (get_irn_opcode(value->irn) == iro_Proj && value->copy[0] != NULL))
- for(i = 0; i < get_irn_n_outs(value->irn); i++){
- key.irn = get_irn_out(value->irn, i);
- // Search for loop outs.
- if(set_find( l_n, &key, sizeof(key), HASH_PTR(key.irn)) == NULL)
- if((key.irn->op == op_Block && get_Block_dom_depth(key.irn) >
- get_Block_dom_depth(loop_head)) ||
- (key.irn->op != op_Block && get_Block_dom_depth(get_nodes_block(key.irn)) >
- get_Block_dom_depth(loop_head))){
-
- for(p = 0; p < get_irn_arity(key.irn); p++)
- if(value->irn == get_irn_n(key.irn, p)){
- if(get_irn_opcode(value->irn) == iro_Proj && is_exception_possible(value->irn)){
- if(set_find( loop_outs, &key, sizeof(key), HASH_PTR(key.irn)) == NULL){
- // If the loop out is for exceptions in the loop.
- if((key.irn->op == op_Phi && get_irn_mode(key.irn) == mode_M) ||
- get_irn_opcode(key.irn) == iro_Call)
- new_after_loop_node(l_n,loop_outs, key.irn, value, unroll_factor);
- else
- continue;
- }else
- continue;
- }else
- set_irn_n (key.irn, p, value->copy[unroll_factor-2]);
- }
- }
+
+ for (value = set_first(l_n); value != NULL; value = set_next(l_n))
+ if (! is_Phi_in_loop_head(value->irn, loop_head) &&
+ (get_irn_opcode(value->irn) == iro_Proj && value->copy[0] != NULL))
+ for (i = 0; i < get_irn_n_outs(value->irn); ++i) {
+ key.irn = get_irn_out(value->irn, i);
+
+ /* Search for loop outs. */
+ if (set_find( l_n, &key, sizeof(key), HASH_PTR(key.irn)) == NULL)
+ if ((key.irn->op == op_Block && get_Block_dom_depth(key.irn) >
+ get_Block_dom_depth(loop_head)) ||
+ (key.irn->op != op_Block && get_Block_dom_depth(get_nodes_block(key.irn)) >
+ get_Block_dom_depth(loop_head))) {
+
+ for (p = 0; p < get_irn_arity(key.irn); p++)
+ if (value->irn == get_irn_n(key.irn, p)) {
+ if (get_irn_op(value->irn) == op_Proj && is_exception_possible(value->irn)) {
+ if (set_find(loop_outs, &key, sizeof(key), HASH_PTR(key.irn)) == NULL) {
+ /* If the loop out is for exceptions in the loop. */
+ if ((get_irn_op(key.irn) == op_Phi && get_irn_mode(key.irn) == mode_M) ||
+ get_irn_op(key.irn) == op_Call)
+ new_after_loop_node(l_n,loop_outs, key.irn, value, unroll_factor);
+ else
+ continue;
+ } else
+ continue;
+ } else
+ set_irn_n(key.irn, p, value->copy[unroll_factor-2]);
+ }
+ }
}
- // The funktion search for loop outs associated with funktion call in the unrolling loop.
+ /* This function searches for loop outs associated with function call in the unrolling loop. */
new_end_block (end_block, loop_head, l_n, loop_endblock_outs, unroll_factor);
}
-/** Unroll the loop boby with a factor that must be power of two.
+
+/**
+ * Unroll the loop body with a factor that must be power of two.
+ * Called from a post walker.
*
- * @param *n A ir node.
- * @param *env Free environment pointer.
+ * @param n An IR node.
+ * @param env points to a result
*/
-static void do_loop_unroll(ir_node *n, void *env){
-
+static void do_loop_unroll(ir_node *n, void *env)
+{
+ int *unroll_done = env;
induct_var_info info;
- info.itervar_phi = n;
+ copies_t *value;
+ set *loop_nodes, *loop_outs, *loop_endblock_outs;
+ ir_node *cmp_out, *phi_init, *loop_head;
+ ir_node *backedge_jmp;
int l_sons = 0, unroll_factor = 0;
- copy_loop_head = 0;
+ int cmp_typ, init, iter_end, iter_increment, diff, iter_number;
+ int backedge_pos;
- /* The ir node must be a induction varible. */
+ copy_loop_head = 0;
+ info.itervar_phi = n;
- if (get_irn_op (n) == op_Phi) {
- if (is_induction_variable (&info) == NULL) return;
- } else return;
+ /* The IR node must be a induction variable. */
+ if (get_irn_op(n) == op_Phi) {
+ if (is_induction_variable (&info) == NULL)
+ return;
+ }
+ else
+ return;
/* Brute force limiting of loop body size. */
if (get_loop_n_nodes(info.l_itervar_phi) > 2 ) return;
if (info.cmp == NULL) return;
/* We only want to unroll innermost loops. */
- l_sons = get_loop_n_sons (info.l_itervar_phi);
+ l_sons = get_loop_n_sons(info.l_itervar_phi);
if ( l_sons != 0)
return;
- ir_node* cmp_out = get_irn_out(info.cmp, 0);
- ir_node *phi_init = get_Phi_pred(info.itervar_phi, info.init_pred_pos);
+ cmp_out = get_irn_out(info.cmp, 0);
+ phi_init = get_Phi_pred(info.itervar_phi, info.init_pred_pos);
- if(!is_Proj(cmp_out)) return;
- if(get_irn_op(info.increment) != op_Const ||
- get_irn_op(phi_init) != op_Const ||
- get_irn_op(info.cmp_const) != op_Const) return;
+ if (! is_Proj(cmp_out)) return;
+ if (get_irn_op(info.increment) != op_Const ||
+ get_irn_op(phi_init) != op_Const ||
+ get_irn_op(info.cmp_const) != op_Const) return;
- int cmp_typ = get_Proj_proj(cmp_out);
- int init = get_tarval_long(get_Const_tarval(phi_init));
- int iter_end = get_tarval_long(get_Const_tarval(info.cmp_const));
- int iter_increment = get_tarval_long(get_Const_tarval(info.increment));
- int diff, iter_number;
+ cmp_typ = get_Proj_proj(cmp_out);
+ init = get_tarval_long(get_Const_tarval(phi_init));
+ iter_end = get_tarval_long(get_Const_tarval(info.cmp_const));
+ iter_increment = get_tarval_long(get_Const_tarval(info.increment));
- if(iter_end < init){
+ if (iter_end < init){
int p = iter_end;
iter_end = init;
init = p;
diff = iter_end - init;
if (diff == 0 || iter_increment == 0) return;
- /*Test for the value of unroll factor. */
+ /* Test for the value of unroll factor. */
iter_number = diff/iter_increment;
- if((cmp_typ == 3 || cmp_typ == 5) && (iter_end % iter_increment == 0))
+ if ((cmp_typ == pn_Cmp_Le || cmp_typ == pn_Cmp_Ge) && (iter_end % iter_increment == 0))
iter_number ++;
- if(iter_number % 4 == 0)
+ if ((iter_number & 3) == 0)
unroll_factor = 4;
- else if(iter_number % 3 == 0)
+ else if ((iter_number % 3) == 0)
unroll_factor = 3;
- else if(iter_number % 2 == 0)
+ else if ((iter_number & 1) == 0)
unroll_factor = 2;
else return;
+ if (get_firm_verbosity())
+ printf("\nloop unrolling with factor %d \n", unroll_factor);
- printf("\nloop unrolling with factor %d \n", unroll_factor);
+ /* ok, we will do unrolling */
+ *unroll_done += 1;
- DDMG(get_irn_irg(n));
- // The unrollfactor muss less than 4.
+ /* The unroll factor must be less than 4. */
assert(unroll_factor <= MAX_UNROLL);
- ir_node *loop_head;
-
loop_head = (is_natural_loop(&info)) ? get_loop_node(info.l_itervar_phi, 0) : NULL;
assert(loop_head != NULL && is_Block(loop_head));
- /* We assume, the loop head has exactly one backedge. The position of
- the backedge is in the following variable: */
- int backedge_pos ;
+ /* We assume, the loop head has exactly one backedge. The position of
+ the backedge is in the following variable: */
backedge_pos = (is_backedge(loop_head, 0)) ? 0:1;
-
- set *loop_nodes, *loop_outs, *loop_endblock_outs;
/* A set with the nodes to copy. */
loop_nodes = new_set(set_cmp, 8);
- // A set with the loop outs for exceptions.
+ /* A set with the loop outs for exceptions. */
loop_outs = new_set(set_cmp, 8);
- /* The set contains all predecessors
- of the end block from the unrolling loop.*/
+
+ /* A set containing all predecessors
+ of the end block from the unrolling loop. */
loop_endblock_outs = new_set(set_cmp, 8);
/* Find all nodes of the unrolling loop. */
find_loop_nodes(info.itervar_phi, get_loop_node(info.l_itervar_phi, 0), loop_nodes);
+
/* Decide if the loop head to be copy.*/
- loop_head_nodes(loop_nodes, &info);
+ copy_loop_head = loop_head_nodes(loop_nodes, &info);
+
/* Copy all nodes of the unrolling loop, that muss be copy. */
copy_loop_body(loop_nodes, &info, unroll_factor);
- ir_node *backedge_jmp = get_Block_cfgpred(loop_head, backedge_pos);
- copies_t *value;
+ backedge_jmp = get_Block_cfgpred(loop_head, backedge_pos);
+
/* Set the backedge of the loop head. */
for (value = set_first(loop_nodes); value != NULL; value = set_next(loop_nodes)) {
- if(value->irn == backedge_jmp){
-
+ if (value->irn == backedge_jmp)
set_Block_cfgpred(loop_head, backedge_pos, value->copy[unroll_factor-2]);
- }
}
set_loop_outs(loop_nodes, loop_outs, loop_endblock_outs, &info, unroll_factor);
-
}
/* Performs loop unrolling for the passed graph. */
-void optimize_loop_unrolling(ir_graph *irg /* unroll factor, max body size */) {
- ir_graph *rem = current_ir_graph;
- current_ir_graph = irg;
+void optimize_loop_unrolling(ir_graph *irg /* unroll factor, max body size */)
+{
+ ir_graph *rem;
+ int unroll_done = 0;
if ( !get_opt_loop_unrolling()) return;
+ rem = current_ir_graph;
+ current_ir_graph = irg;
+
/* -- Precompute some information -- */
+
/* Call algorithm that computes the backedges */
construct_cf_backedges(irg);
- /* Call algorithm that computes the dominator trees. */
+
+ /* Call algorithm that computes the dominator trees. */
compute_doms(irg);
+
/* Call algorithm that computes the out edges */
compute_outs(irg);
+
collect_phiprojs(irg);
/* -- Search expressions that can be optimized -- */
- irg_walk_graph(irg, NULL, do_loop_unroll, NULL);
+ irg_walk_graph(irg, NULL, do_loop_unroll, &unroll_done);
+
+ if (unroll_done) {
+ /* unrolling was done, all info is invalid */
+ set_irg_dom_inconsistent(irg);
+ set_irg_outs_inconsistent(irg);
+ set_irg_loopinfo_state(current_ir_graph, loopinfo_cf_inconsistent);
+ set_trouts_inconsistent();
+ set_irg_callee_info_state(irg, irg_callee_info_inconsistent);
+ }
current_ir_graph = rem;
}
projects / libfirm / blobdiff