+ /*
+ * 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. */
+ ir_nodemap_init(&map, irg);
+ obstack_init(&obst);
+
+ /* 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 */
+ clear_irg_properties(irg, IR_GRAPH_PROPERTY_CONSISTENT_DOMINANCE
+ | IR_GRAPH_PROPERTY_CONSISTENT_LOOPINFO);
+
+ ++stats.inverted;
+ }
+
+ /* free */
+ obstack_free(&obst, NULL);
+ ir_nodemap_destroy(&map);
+ 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];