+ /* Important: get the preds first and then their copy. */
+ ir_node *upper_be_block = get_unroll_copy(topmost_be_block, c);
+ ir_node *new_jmp = new_r_Jmp(upper_be_block);
+ DB((dbg, LEVEL_5, " place_copies upper %N lower %N\n", upper, lower));
+
+ DB((dbg, LEVEL_5, "topmost be block %N \n", topmost_be_block));
+
+ if (loop_info.unroll_kind == constant) {
+ ir_node *ins[1];
+ ins[0] = new_jmp;
+ set_irn_in(lower, 1, ins);
+
+ for_each_phi(loophead, phi) {
+ ir_node *topmost_def = get_irn_n(phi, be_src_pos);
+ ir_node *upper_def = get_unroll_copy(topmost_def, c);
+ ir_node *lower_phi = get_unroll_copy(phi, c + 1);
+
+ /* It is possible, that the value used
+ * in the OWN backedge path is NOT defined in this loop. */
+ if (is_in_loop(topmost_def))
+ ins[0] = upper_def;
+ else
+ ins[0] = topmost_def;
+
+ set_irn_in(lower_phi, 1, ins);
+ /* Need to replace phis with 1 in later. */
+ }
+ } else {
+ /* Invariant case */
+ /* Every node has 2 ins. One from the duff blocks
+ * and one from the previously unrolled loop. */
+ ir_node *ins[2];
+ /* Calculate corresponding projection of mod result for this copy c */
+ ir_node *proj = new_Proj(loop_info.duff_cond, mode_X, unroll_nr - c - 1);
+ DB((dbg, LEVEL_4, "New duff proj %N\n" , proj));
+
+ ins[0] = new_jmp;
+ ins[1] = proj;
+ set_irn_in(lower, 2, ins);
+ DB((dbg, LEVEL_4, "Rewire ins of Block %N to pred %N and duffs entry %N \n" , lower, ins[0], ins[1]));
+
+ for_each_phi(loophead, phi) {
+ ir_node *topmost_phi_pred = get_irn_n(phi, be_src_pos);
+ ir_node *upper_phi_pred;
+ ir_node *lower_phi;
+ ir_node *duff_phi;
+
+ lower_phi = get_unroll_copy(phi, c + 1);
+ duff_phi = (ir_node*)get_irn_link(phi);
+ DB((dbg, LEVEL_4, "DD Link of %N is %N\n" , phi, duff_phi));
+
+ /* */
+ if (is_in_loop(topmost_phi_pred)) {
+ upper_phi_pred = get_unroll_copy(topmost_phi_pred, c);
+ } else {
+ upper_phi_pred = topmost_phi_pred;
+ }
+
+ ins[0] = upper_phi_pred;
+ ins[1] = duff_phi;
+ set_irn_in(lower_phi, 2, ins);
+ DB((dbg, LEVEL_4, "Rewire ins of %N to pred %N and duffs entry %N \n" , lower_phi, ins[0], ins[1]));
+ }
+ }
+ }
+
+ /* Reconnect last copy. */
+ for (i = 0; i < ARR_LEN(loop_entries); ++i) {
+ entry_edge edge = loop_entries[i];
+ /* Last copy is at the bottom */
+ ir_node *new_pred = get_unroll_copy(edge.pred, copies);
+ set_irn_n(edge.node, edge.pos, new_pred);
+ }
+
+ /* Fix original loops head.
+ * Done in the end, as ins and be info were needed before. */
+ if (loop_info.unroll_kind == constant) {
+ ir_node *phi;
+ ir_node *head_pred = get_irn_n(loop_head, be_src_pos);
+ ir_node *loop_condition = get_unroll_copy(head_pred, unroll_nr - 1);
+
+ set_irn_n(loop_head, loop_info.be_src_pos, loop_condition);
+
+ for_each_phi(loop_head, phi) {
+ ir_node *pred = get_irn_n(phi, be_src_pos);
+ ir_node *last_pred;
+
+ /* It is possible, that the value used
+ * in the OWN backedge path is NOT assigned in this loop. */
+ if (is_in_loop(pred))
+ last_pred = get_unroll_copy(pred, copies);
+ else
+ last_pred = pred;
+ set_irn_n(phi, be_src_pos, last_pred);
+ }
+
+ } else {
+ unrolling_fix_loop_head_inv();
+ }
+}
+
+/* Copies the cur_loop several times. */
+static void copy_loop(entry_edge *cur_loop_outs, int copies)
+{
+ int c;
+
+ ir_reserve_resources(current_ir_graph, IR_RESOURCE_IRN_VISITED);
+
+ for (c = 0; c < copies; ++c) {
+ size_t i;
+
+ inc_irg_visited(current_ir_graph);
+
+ DB((dbg, LEVEL_5, " ### Copy_loop copy nr: %d ###\n", c));
+ for (i = 0; i < ARR_LEN(cur_loop_outs); ++i) {
+ entry_edge entry = cur_loop_outs[i];
+ ir_node *pred = get_irn_n(entry.node, entry.pos);
+
+ copy_walk_n(pred, is_in_loop, c + 1);
+ }
+ }
+
+ ir_free_resources(current_ir_graph, IR_RESOURCE_IRN_VISITED);
+}
+
+
+/* Creates a new phi from the given phi node omitting own bes,
+ * using be_block as supplier of backedge informations. */
+static ir_node *clone_phis_sans_bes(ir_node *phi, ir_node *be_block, ir_node *dest_block)
+{
+ ir_node **ins;
+ int arity = get_irn_arity(phi);
+ int i, c = 0;
+ ir_node *newphi;
+
+ assert(get_irn_arity(phi) == get_irn_arity(be_block));
+ assert(is_Phi(phi));
+
+ ins = NEW_ARR_F(ir_node *, arity);
+ for (i = 0; i < arity; ++i) {
+ if (! is_own_backedge(be_block, i)) {
+ ins[c] = get_irn_n(phi, i);
+ ++c;
+ }
+ }
+
+ newphi = new_r_Phi(dest_block, c, ins, get_irn_mode(phi));
+
+ set_irn_link(phi, newphi);
+ DB((dbg, LEVEL_4, "Linking for duffs device %N to %N\n", phi, newphi));
+
+ return newphi;
+}
+
+/* Creates a new block from the given block node omitting own bes,
+ * using be_block as supplier of backedge informations. */
+static ir_node *clone_block_sans_bes(ir_node *node, ir_node *be_block)
+{
+ ir_node **ins;
+ int arity = get_irn_arity(node);
+ int i, c = 0;
+
+ assert(get_irn_arity(node) == get_irn_arity(be_block));
+ assert(is_Block(node));
+
+ NEW_ARR_A(ir_node *, ins, arity);
+ for (i = 0; i < arity; ++i) {
+ if (! is_own_backedge(be_block, i)) {
+ ins[c] = get_irn_n(node, i);
+ ++c;
+ }
+ }
+
+ return new_Block(c, ins);
+}
+
+/* Creates a structure to calculate absolute value of node op.
+ * Returns mux node with absolute value. */
+static ir_node *new_Abs(ir_node *op, ir_mode *mode)
+{
+ ir_graph *irg = get_irn_irg(op);
+ ir_node *block = get_nodes_block(op);
+ ir_node *zero = new_r_Const(irg, get_mode_null(mode));
+ ir_node *cmp = new_r_Cmp(block, op, zero, ir_relation_less);
+ ir_node *minus_op = new_r_Minus(block, op, mode);
+ ir_node *mux = new_r_Mux(block, cmp, op, minus_op, mode);
+
+ return mux;
+}
+
+
+/* Creates blocks for duffs device, using previously obtained
+ * informations about the iv.
+ * TODO split */
+static void create_duffs_block(void)
+{
+ ir_mode *mode;
+
+ ir_node *block1, *count_block, *duff_block;
+ ir_node *ems, *ems_mod, *ems_div, *ems_mod_proj, *cmp_null,
+ *ems_mode_cond, *x_true, *x_false, *const_null;
+ ir_node *true_val, *false_val;
+ ir_node *ins[2];
+
+ ir_node *duff_mod, *proj, *cond;
+
+ ir_node *count, *correction, *unroll_c;
+ ir_node *cmp_bad_count, *good_count, *bad_count, *count_phi, *bad_count_neg;
+ ir_node *phi;
+
+ mode = get_irn_mode(loop_info.end_val);
+ const_null = new_Const(get_mode_null(mode));
+
+ /* TODO naming
+ * 1. Calculate first approach to count.
+ * Condition: (end - start) % step == 0 */
+ block1 = clone_block_sans_bes(loop_head, loop_head);
+ DB((dbg, LEVEL_4, "Duff block 1 %N\n", block1));
+
+ /* Create loop entry phis in first duff block
+ * as it becomes the loops preheader */
+ for_each_phi(loop_head, phi) {
+ /* Returns phis pred if phi would have arity 1*/
+ ir_node *new_phi = clone_phis_sans_bes(phi, loop_head, block1);
+
+ DB((dbg, LEVEL_4, "HEAD %N phi %N\n", loop_head, phi));
+ DB((dbg, LEVEL_4, "BLOCK1 %N phi %N\n", block1, new_phi));
+ }
+
+ ems = new_r_Sub(block1, loop_info.end_val, loop_info.start_val,
+ get_irn_mode(loop_info.end_val));
+ DB((dbg, LEVEL_4, "BLOCK1 sub %N\n", ems));
+
+
+ ems = new_Sub(loop_info.end_val, loop_info.start_val,
+ get_irn_mode(loop_info.end_val));
+
+ DB((dbg, LEVEL_4, "mod ins %N %N\n", ems, loop_info.step));
+ ems_mod = new_r_Mod(block1,
+ new_NoMem(),
+ ems,
+ loop_info.step,
+ mode,
+ op_pin_state_pinned);
+ ems_div = new_r_Div(block1,
+ new_NoMem(),
+ ems,
+ loop_info.step,
+ mode,
+ op_pin_state_pinned);
+
+ DB((dbg, LEVEL_4, "New module node %N\n", ems_mod));
+
+ ems_mod_proj = new_r_Proj(ems_mod, mode_Iu, pn_Mod_res);
+ cmp_null = new_r_Cmp(block1, ems_mod_proj, const_null, ir_relation_less);
+ ems_mode_cond = new_r_Cond(block1, cmp_null);
+
+ /* ems % step == 0 */
+ x_true = new_r_Proj(ems_mode_cond, mode_X, pn_Cond_true);
+ /* ems % step != 0 */
+ x_false = new_r_Proj(ems_mode_cond, mode_X, pn_Cond_false);
+
+ /* 2. Second block.
+ * Assures, duffs device receives a valid count.
+ * Condition:
+ * decreasing: count < 0
+ * increasing: count > 0
+ */
+ ins[0] = x_true;
+ ins[1] = x_false;
+
+ count_block = new_Block(2, ins);
+ DB((dbg, LEVEL_4, "Duff block 2 %N\n", count_block));
+
+
+ /* Increase loop-taken-count depending on the loop condition
+ * uses the latest iv to compare to. */
+ if (loop_info.latest_value == 1) {
+ /* ems % step == 0 : +0 */
+ true_val = new_Const(get_mode_null(mode));
+ /* ems % step != 0 : +1 */
+ false_val = new_Const(get_mode_one(mode));
+ } else {
+ ir_tarval *tv_two = new_tarval_from_long(2, mode);
+ /* ems % step == 0 : +1 */
+ true_val = new_Const(get_mode_one(mode));
+ /* ems % step != 0 : +2 */
+ false_val = new_Const(tv_two);
+ }
+
+ ins[0] = true_val;
+ ins[1] = false_val;
+
+ correction = new_r_Phi(count_block, 2, ins, mode);
+
+ count = new_r_Proj(ems_div, mode, pn_Div_res);
+
+ /* (end - start) / step + correction */
+ count = new_Add(count, correction, mode);
+
+ /* We preconditioned the loop to be tail-controlled.
+ * So, if count is something 'wrong' like 0,
+ * negative/positive (depending on step direction),
+ * we may take the loop once (tail-contr.) and leave it
+ * to the existing condition, to break; */
+
+ /* Depending on step direction, we have to check for > or < 0 */
+ if (loop_info.decreasing == 1) {
+ cmp_bad_count = new_r_Cmp(count_block, count, const_null,
+ ir_relation_less);
+ } else {
+ cmp_bad_count = new_r_Cmp(count_block, count, const_null,
+ ir_relation_greater);
+ }
+
+ bad_count_neg = new_r_Cond(count_block, cmp_bad_count);
+ good_count = new_Proj(bad_count_neg, mode_X, pn_Cond_true);
+ bad_count = new_Proj(ems_mode_cond, mode_X, pn_Cond_false);
+
+ /* 3. Duff Block
+ * Contains module to decide which loop to start from. */
+
+ ins[0] = good_count;
+ ins[1] = bad_count;
+ duff_block = new_Block(2, ins);
+ DB((dbg, LEVEL_4, "Duff block 3 %N\n", duff_block));
+
+ /* Get absolute value */
+ ins[0] = new_Abs(count, mode);
+ /* Manually feed the aforementioned count = 1 (bad case)*/
+ ins[1] = new_Const(get_mode_one(mode));
+ count_phi = new_r_Phi(duff_block, 2, ins, mode);
+
+ unroll_c = new_Const(new_tarval_from_long((long)unroll_nr, mode));
+
+ /* count % unroll_nr */
+ duff_mod = new_r_Mod(duff_block,
+ new_NoMem(),
+ count_phi,
+ unroll_c,
+ mode,
+ op_pin_state_pinned);
+
+
+ proj = new_Proj(duff_mod, mode, pn_Mod_res);
+ /* condition does NOT create itself in the block of the proj! */
+ cond = new_r_Cond(duff_block, proj);
+
+ loop_info.duff_cond = cond;
+}
+
+/* Returns 1 if given node is not in loop,
+ * or if it is a phi of the loop head with only loop invariant defs.
+ */
+static unsigned is_loop_invariant_def(ir_node *node)