+ return;
+ }
+
+ /* Check if block only has a jmp instruction. */
+ foreach_out_edge(block, edge) {
+ ir_node *src = get_edge_src_irn(edge);
+
+ if (!is_Block(src) && !is_Jmp(src)) {
+ jmp_only = false;
+ }
+ }
+
+ /* Check cf outs if one is leaving the loop,
+ * or if this node has a backedge. */
+ 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))
+ mark = true;
+
+ /* Inverting blocks with backedge outs leads to a cf edge
+ * from the inverted head, into the inverted head (skipping the body).
+ * As the body becomes the new loop head,
+ * this would introduce another loop in the existing loop.
+ * This loop inversion cannot cope with this case. */
+ if (is_backedge(src, pos)) {
+ has_be = true;
+ break;
+ }
+ }
+
+ /* We need all predecessors to already belong to the condition chain.
+ * Example of wrong case: * == in cc
+ *
+ * Head* ,--.
+ * /| \ B |
+ * / A* B / |
+ * / /\ / ? |
+ * / C* => D |
+ * / D Head |
+ * / A \_|
+ * C
+ */
+ /* Collect blocks containing only a Jmp.
+ * Do not collect blocks with backedge outs. */
+ if ((jmp_only || mark) && !has_be) {
+ set_Block_mark(block, 1);
+ ++inversion_blocks_in_cc;
+ loop_info.cc_size += nodes_n;
+ DB((dbg, LEVEL_5, "block %N is part of condition chain\n", block));
+ ARR_APP1(ir_node *, cc_blocks, block);
+ } else {
+ set_Block_mark(block, 0);
+ }
+
+ foreach_block_succ(block, edge) {
+ ir_node *src = get_edge_src_irn( edge );
+
+ if (is_in_loop(src) && ! irn_visited(src))
+ find_condition_chain(src);
+ }
+}
+
+/**
+ * Rewires the copied condition chain. Removes backedges
+ * as this condition chain is prior to the loop.
+ * Copy of loop_head must have phi list and old (unfixed) backedge info of the loop head.
+ * (loop_head is already fixed, we cannot rely on it.)
+ */
+static void fix_copy_inversion(void)
+{
+ ir_node *new_head;
+ ir_node **ins;
+ ir_node **phis;
+ ir_node *phi, *next;
+ ir_node *head_cp = get_inversion_copy(loop_head);
+ ir_graph *irg = get_irn_irg(head_cp);
+ int arity = get_irn_arity(head_cp);
+ int backedges = get_backedge_n(head_cp, false);
+ int new_arity = arity - backedges;
+ int pos;
+ int i;
+
+ NEW_ARR_A(ir_node *, ins, new_arity);
+
+ pos = 0;
+ /* Remove block backedges */
+ for(i = 0; i < arity; ++i) {
+ if (!is_backedge(head_cp, i))
+ ins[pos++] = get_irn_n(head_cp, i);
+ }
+
+ new_head = new_r_Block(irg, new_arity, ins);
+
+ phis = NEW_ARR_F(ir_node *, 0);
+
+ for_each_phi_safe(get_Block_phis(head_cp), phi, next) {
+ ir_node *new_phi;
+ NEW_ARR_A(ir_node *, ins, new_arity);
+ pos = 0;
+ for(i = 0; i < arity; ++i) {
+ if (!is_backedge(head_cp, i))
+ ins[pos++] = get_irn_n(phi, i);
+ }
+ new_phi = new_rd_Phi(get_irn_dbg_info(phi),
+ new_head, new_arity, ins,
+ get_irn_mode(phi));
+ ARR_APP1(ir_node *, phis, new_phi);
+ }
+
+ pos = 0;
+ for_each_phi_safe(get_Block_phis(head_cp), phi, next) {
+ exchange(phi, phis[pos++]);
+ }
+
+ exchange(head_cp, new_head);
+
+ DEL_ARR_F(phis);
+}
+
+
+/* Puts the original condition chain at the end of the loop,
+ * subsequently to the body.
+ * Relies on block phi list and correct backedges.
+ */
+static void fix_head_inversion(void)
+{
+ ir_node *new_head;
+ ir_node **ins;
+ ir_node *phi, *next;
+ ir_node **phis;
+ ir_graph *irg = get_irn_irg(loop_head);
+ int arity = get_irn_arity(loop_head);
+ int backedges = get_backedge_n(loop_head, false);
+ int new_arity = backedges;
+ int pos;
+ int i;
+
+ NEW_ARR_A(ir_node *, ins, new_arity);
+
+ pos = 0;
+ /* Keep only backedges */
+ for(i = 0; i < arity; ++i) {
+ if (is_own_backedge(loop_head, i))
+ ins[pos++] = get_irn_n(loop_head, i);
+ }
+
+ new_head = new_r_Block(irg, new_arity, ins);
+
+ phis = NEW_ARR_F(ir_node *, 0);
+
+ for_each_phi(loop_head, phi) {
+ ir_node *new_phi;
+ DB((dbg, LEVEL_5, "Fixing phi %N of loop head\n", phi));
+
+ NEW_ARR_A(ir_node *, ins, new_arity);
+
+ pos = 0;
+ for (i = 0; i < arity; ++i) {
+ ir_node *pred = get_irn_n(phi, i);
+
+ if (is_own_backedge(loop_head, i)) {
+ /* If assignment is in the condition chain,
+ * we need to create a phi in the new loop head.
+ * This can only happen for df, not cf. See find_condition_chains. */
+ /*if (is_nodes_block_marked(pred)) {
+ ins[pos++] = pred;
+ } else {*/
+ ins[pos++] = pred;
+
+ }
+ }
+
+ new_phi = new_rd_Phi(get_irn_dbg_info(phi),
+ new_head, new_arity, ins,
+ get_irn_mode(phi));
+
+ ARR_APP1(ir_node *, phis, new_phi);
+
+ DB((dbg, LEVEL_5, "fix inverted head should exch %N by %N (pos %d)\n", phi, new_phi, pos ));
+ }
+
+ pos = 0;
+ for_each_phi_safe(get_Block_phis(loop_head), phi, next) {
+ DB((dbg, LEVEL_5, "fix inverted exch phi %N by %N\n", phi, phis[pos]));
+ if (phis[pos] != phi)
+ exchange(phi, phis[pos++]);
+ }
+
+ DEL_ARR_F(phis);
+
+ DB((dbg, LEVEL_5, "fix inverted head exch head block %N by %N\n", loop_head, new_head));
+ exchange(loop_head, new_head);
+}
+
+/* Does the loop inversion. */
+static void inversion_walk(ir_graph *irg, entry_edge *head_entries)
+{
+ size_t i;
+
+ /*
+ * The order of rewiring bottom-up is crucial.
+ * Any change of the order leads to lost information that would be needed later.
+ */
+
+ ir_reserve_resources(irg, IR_RESOURCE_IRN_VISITED);
+
+ /* 1. clone condition chain */
+ inc_irg_visited(irg);
+
+ for (i = 0; i < ARR_LEN(head_entries); ++i) {
+ entry_edge entry = head_entries[i];
+ ir_node *pred = get_irn_n(entry.node, entry.pos);
+
+ DB((dbg, LEVEL_5, "\nInit walk block %N\n", pred));
+
+ copy_walk(pred, is_nodes_block_marked, cur_loop);
+ }
+
+ ir_free_resources(irg, IR_RESOURCE_IRN_VISITED);
+
+ /* 2. Extends the head control flow successors ins
+ * with the definitions of the copied head node. */
+ for (i = 0; i < ARR_LEN(head_entries); ++i) {
+ entry_edge head_out = head_entries[i];
+
+ if (is_Block(head_out.node))
+ extend_ins_by_copy(head_out.node, head_out.pos);
+ }
+
+ /* 3. construct_ssa for users of definitions in the condition chain,
+ * as there is now a second definition. */
+ for (i = 0; i < ARR_LEN(head_entries); ++i) {
+ entry_edge head_out = head_entries[i];
+
+ /* Ignore keepalives */
+ if (is_End(head_out.node))
+ continue;
+
+ /* Construct ssa for assignments in the condition chain. */
+ if (!is_Block(head_out.node)) {
+ ir_node *pred, *cppred, *block, *cpblock;
+
+ pred = head_out.pred;
+ cppred = get_inversion_copy(pred);
+ block = get_nodes_block(pred);
+ cpblock = get_nodes_block(cppred);
+ construct_ssa(block, pred, cpblock, cppred);
+ }
+ }
+
+ /*
+ * If there is an assignment in the condition chain
+ * with a user also in the condition chain,
+ * the dominance frontier is in the new loop head.
+ * The dataflow loop is completely in the condition chain.
+ * Goal:
+ * To be wired: >|
+ *
+ * | ,--. |
+ * Phi_cp | | copied condition chain
+ * >| | | |
+ * >| ?__/ |
+ * >| ,-.
+ * Phi* | | new loop head with newly created phi.
+ * | |
+ * Phi | | original, inverted condition chain
+ * | | |
+ * ?__/ |
+ *
+ */
+ for (i = 0; i < ARR_LEN(head_df_loop); ++i) {
+ entry_edge head_out = head_df_loop[i];
+
+ /* Construct ssa for assignments in the condition chain. */
+ ir_node *pred, *cppred, *block, *cpblock;
+
+ pred = head_out.pred;
+ cppred = get_inversion_copy(pred);
+ assert(cppred && pred);
+ block = get_nodes_block(pred);
+ cpblock = get_nodes_block(cppred);
+ construct_ssa(block, pred, cpblock, cppred);
+ }
+
+ /* 4. Remove the ins which are no backedges from the original condition chain
+ * as the cc is now subsequent to the body. */
+ fix_head_inversion();
+
+ /* 5. Remove the backedges of the copied condition chain,
+ * because it is going to be the new 'head' in advance to the loop. */
+ fix_copy_inversion();
+
+}
+
+/* Performs loop inversion of cur_loop if possible and reasonable. */
+static void loop_inversion(ir_graph *irg)
+{
+ int loop_depth;
+ unsigned max_loop_nodes = opt_params.max_loop_size;
+ unsigned max_loop_nodes_adapted;
+ int depth_adaption = opt_params.depth_adaption;
+
+ bool do_inversion = true;
+
+ /* Depth of 0 is the procedure and 1 a topmost loop. */
+ loop_depth = get_loop_depth(cur_loop) - 1;
+
+ /* Calculating in per mil. */
+ max_loop_nodes_adapted = get_max_nodes_adapted(loop_depth);
+
+ DB((dbg, LEVEL_1, "max_nodes: %d\nmax_nodes_adapted %d at depth of %d (adaption %d)\n",
+ max_loop_nodes, max_loop_nodes_adapted, loop_depth, depth_adaption));
+
+ if (loop_info.nodes == 0)
+ return;
+
+ if (loop_info.nodes > max_loop_nodes) {
+ /* Only for stats */
+ DB((dbg, LEVEL_1, "Nodes %d > allowed nodes %d\n",
+ loop_info.nodes, loop_depth, max_loop_nodes));
+ ++stats.too_large;
+ /* no RETURN */
+ /* Adaption might change it */
+ }
+
+ /* Limit processing to loops smaller than given parameter. */
+ if (loop_info.nodes > max_loop_nodes_adapted) {
+ DB((dbg, LEVEL_1, "Nodes %d > allowed nodes (depth %d adapted) %d\n",
+ loop_info.nodes, loop_depth, max_loop_nodes_adapted));
+ ++stats.too_large_adapted;
+ return;
+ }
+
+ if (loop_info.calls > opt_params.allowed_calls) {
+ DB((dbg, LEVEL_1, "Calls %d > allowed calls %d\n",
+ loop_info.calls, opt_params.allowed_calls));
+ ++stats.calls_limit;
+ return;
+ }
+
+ /*inversion_head_node_limit = INT_MAX;*/
+ ir_reserve_resources(irg, IR_RESOURCE_BLOCK_MARK);
+
+ /* Reset block marks.
+ * We use block marks to flag blocks of the original condition chain. */
+ irg_walk_graph(irg, reset_block_mark, NULL, NULL);
+
+ /*loop_info.blocks = get_loop_n_blocks(cur_loop);*/
+ cond_chain_entries = NEW_ARR_F(entry_edge, 0);
+ head_df_loop = NEW_ARR_F(entry_edge, 0);
+
+ /*head_inversion_node_count = 0;*/
+ inversion_blocks_in_cc = 0;
+
+ /* Use phase to keep copy of nodes from the condition chain. */
+ phase = new_phase(irg, phase_irn_init_default);
+
+ /* Search for condition chains and temporarily save the blocks in an array. */
+ cc_blocks = NEW_ARR_F(ir_node *, 0);
+ inc_irg_visited(irg);
+ find_condition_chain(loop_head);
+
+ unmark_not_allowed_cc_blocks();
+ DEL_ARR_F(cc_blocks);
+
+ /* Condition chain too large.
+ * Loop should better be small enough to fit into the cache. */
+ /* TODO Of course, we should take a small enough cc in the first place,
+ * which is not that simple. (bin packing) */
+ if (loop_info.cc_size > opt_params.max_cc_size) {
+ ++stats.cc_limit_reached;
+
+ do_inversion = false;
+
+ /* Unmark cc blocks except the head.
+ * Invert head only for possible unrolling. */
+ unmark_cc_blocks();
+ }
+
+ /* We also catch endless loops here,
+ * because they do not have a condition chain. */
+ if (inversion_blocks_in_cc < 1) {
+ do_inversion = false;
+ DB((dbg, LEVEL_3,
+ "Loop contains %d (less than 1) invertible blocks => No Inversion done.\n",
+ inversion_blocks_in_cc));
+ }
+
+ if (do_inversion) {
+ cur_head_outs = NEW_ARR_F(entry_edge, 0);
+
+ /* Get all edges pointing into the condition chain. */
+ irg_walk_graph(irg, get_head_outs, NULL, NULL);
+
+ /* Do the inversion */
+ inversion_walk(irg, cur_head_outs);
+
+ DEL_ARR_F(cur_head_outs);
+
+ /* Duplicated blocks changed doms */
+ set_irg_doms_inconsistent(irg);
+ set_irg_loopinfo_state(irg, loopinfo_cf_inconsistent);
+
+ ++stats.inverted;
+ }
+
+ /* free */
+ phase_free(phase);
+ DEL_ARR_F(cond_chain_entries);
+ DEL_ARR_F(head_df_loop);
+
+ ir_free_resources(irg, IR_RESOURCE_BLOCK_MARK);
+}
+
+/* Fix the original loop_heads ins for invariant unrolling case. */
+static void unrolling_fix_loop_head_inv(void)
+{
+ ir_node *ins[2];
+ ir_node *phi;
+ ir_node *proj = new_Proj(loop_info.duff_cond, mode_X, 0);
+ ir_node *head_pred = get_irn_n(loop_head, loop_info.be_src_pos);
+ ir_node *loop_condition = get_unroll_copy(head_pred, unroll_nr - 1);
+
+ /* Original loop_heads ins are:
+ * duff block and the own backedge */
+
+ ins[0] = loop_condition;
+ ins[1] = proj;
+ set_irn_in(loop_head, 2, ins);
+ DB((dbg, LEVEL_4, "Rewire ins of block loophead %N to pred %N and duffs entry %N \n" , loop_head, ins[0], ins[1]));
+
+ for_each_phi(loop_head, phi) {
+ ir_node *pred = get_irn_n(phi, loop_info.be_src_pos);
+ /* TODO we think it is a phi, but for Mergesort it is not the case.*/
+
+ ir_node *last_pred = get_unroll_copy(pred, unroll_nr - 1);
+
+ ins[0] = last_pred;
+ ins[1] = (ir_node*)get_irn_link(phi);
+ set_irn_in(phi, 2, ins);
+ DB((dbg, LEVEL_4, "Rewire ins of loophead phi %N to pred %N and duffs entry %N \n" , phi, ins[0], ins[1]));
+ }
+}
+
+/* Removes previously created phis with only 1 in. */
+static void correct_phis(ir_node *node, void *env)
+{
+ (void)env;
+
+ if (is_Phi(node) && get_irn_arity(node) == 1) {
+ ir_node *exch;
+ ir_node *in[1];
+
+ in[0] = get_irn_n(node, 0);
+
+ exch = new_rd_Phi(get_irn_dbg_info(node),
+ get_nodes_block(node), 1, in,
+ get_irn_mode(node));
+
+ exchange(node, exch);
+ }
+}
+
+/* Unrolling: Rewire floating copies. */
+static void place_copies(int copies)
+{
+ ir_node *loophead = loop_head;
+ size_t i;
+ int c;
+ int be_src_pos = loop_info.be_src_pos;
+
+ /* Serialize loops by fixing their head ins.
+ * Processed are the copies.
+ * The original loop is done after that, to keep backedge infos. */
+ for (c = 0; c < copies; ++c) {
+ ir_node *upper = get_unroll_copy(loophead, c);
+ ir_node *lower = get_unroll_copy(loophead, c + 1);
+ ir_node *phi;
+ ir_node *topmost_be_block = get_nodes_block(get_irn_n(loophead, be_src_pos));
+
+ /* 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)
+{
+ int arity = get_irn_arity(node);
+ int i, c = 0;
+ ir_node **ins;
+
+ 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);