+/* We will unroll maximal 4-times. */
+#define MAX_UNROLL 4
+
+/* We will know if the head of the loop to be copy.
+ * Default "0" don't copy.*/
+static int copy_loop_head;
+
+typedef struct {
+ ir_node *irn ; /* Node of the loop to be unrolling*/
+ ir_node *copy[MAX_UNROLL] ; /* The copy of the node */
+} copies_t;
+
+/**
+ * Compare two elements of the copies_t set
+ */
+static int set_cmp(const void *elt, const void *key, size_t size)
+{
+ const copies_t *c1 = elt;
+ const copies_t *c2 = key;
+
+ return c1->irn != c2->irn;
+}
+
+/**
+ * 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)
+{
+ old->link = new;
+}
+
+/*Check if phi in the loop head is.
+ *
+ * @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));
+ return is_Phi(phi) && (get_nodes_block(phi) == loop_head);
+}
+
+/**
+ * Copies predecessors of node to copies of node.
+ * 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.
+ */
+static void
+set_preds (set *l_n, copies_t *value, induct_var_info *info, int unroll_factor, void *env)
+{
+ ir_node *loop_head;
+ int i, p, irn_arity;
+ copies_t key, *value_pred;
+ if(value->copy[0] == NULL ||
+ get_irn_op(value->irn) != get_irn_op(value->copy[0]))
+ return;
+
+ /* The head of the unrolling loop. */
+ loop_head = get_loop_node(info->l_itervar_phi, 0);
+ irn_arity = get_irn_arity(value->irn);
+
+ for (i = 0; i < irn_arity; i++) {
+ ir_node *pred = get_irn_n(value->irn, i);
+
+ key.irn = pred;
+ value_pred = set_find(l_n, &key, sizeof(key), HASH_PTR(pred));
+
+ 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.
+ */
+ }
+ }
+ }
+}
+
+/* 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 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.
+ */
+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. */
+ 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 copy. */
+ set_Phi_pred(value->irn, info->op_pred_pos, value_pred->copy[unroll_factor - 2]);
+}
+
+/**
+ * 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.
+ *
+ * @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)
+{
+ int i, arity;
+ int some_outof_loop = 0, some_in_loop = 0;
+
+ assert(get_irn_op(n) == op_Block);
+ arity = get_Block_n_cfgpreds(n);
+
+ for (i = 0; i < arity; i++) {
+ ir_node *pred = get_Block_cfgpred(n, i);
+ assert(pred);
+ if (is_loop_invariant(pred, get_loop_node(info->l_itervar_phi, 0))) {
+ some_outof_loop = 1;
+ } else
+ some_in_loop = 1;
+ }
+
+ return some_outof_loop && some_in_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.
+ */
+static int
+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 ++) {
+ l_node = get_loop_node (info->l_itervar_phi, i);
+ if (is_loop_head(l_node, info)) return 0;
+
+ if (has_backedges(l_node) && i != l_n_node-1) return 0;
+ }
+
+ return 1;
+}
+
+/**
+ * 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.
+ */
+static void
+find_loop_nodes(ir_node *node, ir_node *loop_head, set *l_n)
+{
+ int i;
+ copies_t key, *value;
+
+ /* Add this node to the list. */
+ key.irn = node;
+
+ /* 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) {
+ 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 ) {
+ 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) {
+ 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 ) {
+ find_loop_nodes(pred, loop_head, l_n);
+ }
+ }
+}
+
+/**
+ * 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 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, int copy_head)
+{
+ int i;
+ copies_t block, *value_backedge_jmp, *backedge_jmp_block;
+ /* 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));
+
+ if (copy_head) {
+ /* The first copy of the loop head must point to the loop head.*/
+ value->copy[0] = new_Block(1, &backedge_jmp);
+ if(info->l_itervar_phi->flags & do_loop){
+ value_backedge_jmp->copy[0] = new_r_Jmp(current_ir_graph, value->copy[0]);
+ 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, &backedge_jmp);
+ value_backedge_jmp->copy[i] = new_r_Jmp(current_ir_graph, value->copy[i]);
+ }
+ for (i = 1; i < unroll_factor - 1; ++i){
+ set_nodes_block(value_backedge_jmp->copy[i-1], get_nodes_block(backedge_jmp));
+ set_Block_cfgpred (value->copy[i], 0, value_backedge_jmp->copy[i-1]);
+ }
+ }else
+ for (i = 1; i < unroll_factor - 1; ++i) {
+ /* all other copies must point to the copy before it in the array. */
+ set_nodes_block(value_backedge_jmp->copy[i-1], get_nodes_block(backedge_jmp));
+ value->copy[i] = new_Block(1, &value_backedge_jmp->copy[i-1]);
+ }
+ }
+ 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)
+ 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.
+ */
+static void
+set_Phi_copies(copies_t *phi, copies_t *phi_pred, int unroll_factor)
+{
+ int p;
+
+ if(phi_pred != NULL){
+ /* 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 & 1)
+ phi->copy[p] = phi->irn;
+ else
+ phi->copy[p] = phi_pred->irn;
+ } else
+ phi->copy[p] = phi_pred->copy[p - 1];
+ }
+ }else
+ /* The predecessors of phi are loop invariant and the copies von phi
+ must be phi it self.*/
+ for(p = 0; p < unroll_factor - 1; ++p)
+ phi->copy[p] = phi->irn;
+}
+
+/**
+ * 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.
+ *
+ * @return non-zero if the loop head must be copied
+ */
+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 (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;
+ case iro_Phi:
+ break;
+ case iro_Proj:
+ break;
+ case iro_Const:
+ break;
+ case iro_Cmp:
+ break;
+ default:
+ 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.
+ */
+static void
+copy_loop_body(set *l_n, induct_var_info *info, int unroll_factor)
+{
+ int i, opt;
+ copies_t *value, *info_op, *phi, *loop_h = NULL, key, *value_block;
+ ir_node *proj_b, *cond, *proj_1, *proj_0, *loop_head;
+ proj_b = get_irn_out(info->cmp, 0);
+ cond = get_irn_out(proj_b, 0);
+ proj_0 = get_irn_out(cond, 0);
+ proj_1 = get_irn_out(cond, 1);
+
+ loop_head = get_loop_node(info->l_itervar_phi, 0);
+ /* I will create some nodes and need the optimization to
+ be set off.*/
+ opt = get_optimize();
+ set_optimize(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(value->irn == proj_0){
+ for (i = 0; i < unroll_factor - 1; i++)
+ /* In the copies of the loop head we replace the cmp branche with a jmp node.
+ This is just for "for" loops."do" loops are handled in function
+ new_loop_head().*/
+ value->copy[i] = new_r_Jmp(current_ir_graph, get_nodes_block(value->irn));
+ }else if(value->irn != proj_b && value->irn != cond &&
+ value->irn != proj_1)
+ /* The loop head must be copied. */
+ for (i = 0; i < unroll_factor - 1; i++){
+ copy_irn_to_irg(value->irn, current_ir_graph);
+ value->copy[i] = get_irn_link(value->irn);
+ }
+ } else {
+ /* 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_irn_to_irg(value->irn, current_ir_graph);
+ value->copy[i] = get_irn_link(value->irn);
+ }
+ }
+ }
+ }
+
+ /* Treat the loop head block */
+ new_loop_head(l_n, info, loop_h, unroll_factor, copy_loop_head);
+ /* I have created the nodes and I set the optimization
+ to it old value.*/
+ set_optimize(opt);
+
+ /* 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));
+ for (i = 0; i < get_irn_n_outs(loop_head); ++i) {
+ ir_node *phi = get_irn_out(loop_head, i);
+
+ if (is_Phi(phi)) {
+ 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){
+ set_preds(l_n, value, info, unroll_factor, NULL);
+ }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) &&
+ has_backedges(value->irn))
+ /* Set the backedge of phis in the loop head. */
+ set_phi_backedge(l_n, value, info, unroll_factor);
+
+ if ((value->irn->op != op_Block) && !is_Phi_in_loop_head(value->irn, loop_head) &&
+ value->copy[0] != NULL ) {
+ ir_node *nodes_block = get_nodes_block(value->irn);
+
+ 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]);
+ }
+ }
+ }
+ /* I must repair some control flow edges, when the loop head
+ have been copied.*/
+ if (copy_loop_head && !(info->l_itervar_phi->flags & do_loop)){
+ key.irn = proj_0;
+ value = set_find( l_n, &key, sizeof(key), HASH_PTR(key.irn));
+ key.irn = get_irn_out(proj_0, 0);
+ info_op = set_find( l_n, &key, sizeof(key), HASH_PTR(key.irn));
+ for (i = 0; i < unroll_factor - 1; i++){
+ set_Block_cfgpred(info_op->copy[i], 0, value->copy[i]);
+ }
+ }
+}
+
+/**
+ * Returns non-zero if a Proj node from the loop has a predecessor that
+ * can throw an exception.
+ *
+ * @param node A Proj node from the loop.
+ *
+ * @return non-zero if the predecessor of the Proj node can throw an exception
+ */
+static int is_exception_possible(ir_node *node)
+{
+ ir_node *pred = get_Proj_pred(node);
+
+ /* only fragile ops can throw an exception */
+ if (! is_fragile_op(pred))
+ return 0;
+
+ /*
+ * 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;
+}
+
+/**
+ * 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.
+ */
+static void
+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. */
+ ir_node **all_in;
+
+ 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 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 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. */
+ 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. */
+
+ value = set_first(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]; /* The new predecessors. */
+ }
+
+ }
+
+ /* 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
+ *
+ * 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.
+ * @param 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 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. */
+
+ 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. */
+
+ q = old_preds;
+ 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. */
+ }
+ }
+ /* Replace the old predecessors of the end block whit the new one. */
+ set_irn_in(block, all_new_preds, all_in);