+ DB((dbg, LEVEL_4, "preferred unroll factor %d\n", prefer));
+
+ /*
+ * If our preference is greater than the allowed unroll factor
+ * we either might reduce the preferred factor and prevent a duffs device block,
+ * or create a duffs device block, from which in this case (constants only)
+ * we know the startloop at compiletime.
+ * The latter yields the following graphs.
+ * but for code generation we would want to use graph A.
+ * The graphs are equivalent. So, we can only reduce the preferred factor.
+ * A) B)
+ * PreHead PreHead
+ * | ,--. | ,--.
+ * \ Loop1 \ Loop2 \
+ * \ | | / | |
+ * Loop2 / / Loop1 /
+ * | `--' | `--'
+ */
+
+ if (prefer <= loop_info.max_unroll)
+ return prefer;
+ else {
+ switch(prefer) {
+ case 6:
+ if (loop_info.max_unroll >= 3)
+ return 3;
+ else if (loop_info.max_unroll >= 2)
+ return 2;
+ else
+ return 0;
+
+ case 4:
+ if (loop_info.max_unroll >= 2)
+ return 2;
+ else
+ return 0;
+
+ default:
+ return 0;
+ }
+ }
+}
+
+/* Check if cur_loop is a simple counting loop.
+ * Start, step and end are constants. */
+/* TODO split. */
+static unsigned get_unroll_decision_constant(void)
+{
+ ir_node *projres, *loop_condition, *iteration_path;
+ unsigned success, is_latest_val;
+ tarval *start_tar, *end_tar, *step_tar, *diff_tar, *count_tar, *stepped;
+ pn_Cmp proj_proj, norm_proj;
+ ir_mode *mode;
+
+ /* RETURN if loop is not 'simple' */
+ projres = is_simple_loop();
+ if (projres == NULL)
+ return 0;
+
+ /* One in of the loop condition needs to be loop invariant. => end_val
+ * The other in is assigned by an add. => add
+ * The add uses a loop invariant value => step
+ * and a phi with a loop invariant start_val and the add node as ins.
+
+ ^ ^
+ | | .-,
+ | Phi |
+ \ | |
+ ^ Add |
+ \ | \__|
+ cond
+ /\
+ */
+
+ loop_condition = get_irn_n(projres, 0);
+
+ success = get_const_pred(loop_condition, &loop_info.end_val, &iteration_path);
+ if (! success)
+ return 0;
+
+ DB((dbg, LEVEL_4, "End_val %N, other %N\n", loop_info.end_val, iteration_path));
+
+ /* We may find the add or the phi first.
+ * Until now we only have end_val. */
+ if (is_Add(iteration_path) || is_Sub(iteration_path)) {
+
+ /* We test against the latest value of the iv. */
+ is_latest_val = 1;
+
+ loop_info.add = iteration_path;
+ DB((dbg, LEVEL_4, "Got add %N (maybe not sane)\n", loop_info.add));
+
+ /* Preds of the add should be step and the iteration_phi */
+ success = get_const_pred(loop_info.add, &loop_info.step, &loop_info.iteration_phi);
+ if (! success)
+ return 0;
+
+ DB((dbg, LEVEL_4, "Got step %N\n", loop_info.step));
+
+ if (! is_Phi(loop_info.iteration_phi))
+ return 0;
+
+ DB((dbg, LEVEL_4, "Got phi %N\n", loop_info.iteration_phi));
+
+ /* Find start_val.
+ * Does necessary sanity check of add, if it is already set. */
+ success = get_start_and_add(loop_info.iteration_phi, constant);
+ if (! success)
+ return 0;
+
+ DB((dbg, LEVEL_4, "Got start %N\n", loop_info.start_val));
+
+ } else if (is_Phi(iteration_path)) {
+ ir_node *new_iteration_phi;
+
+ /* We compare with the value the iv had entering this run. */
+ is_latest_val = 0;
+
+ loop_info.iteration_phi = iteration_path;
+ DB((dbg, LEVEL_4, "Got phi %N\n", loop_info.iteration_phi));
+
+ /* Find start_val and add-node.
+ * Does necessary sanity check of add, if it is already set. */
+ success = get_start_and_add(loop_info.iteration_phi, constant);
+ if (! success)
+ return 0;
+
+ DB((dbg, LEVEL_4, "Got start %N\n", loop_info.start_val));
+ DB((dbg, LEVEL_4, "Got add or sub %N\n", loop_info.add));
+
+ success = get_const_pred(loop_info.add, &loop_info.step, &new_iteration_phi);
+ if (! success)
+ return 0;
+
+ DB((dbg, LEVEL_4, "Got step %N\n", loop_info.step));
+
+ if (loop_info.iteration_phi != new_iteration_phi)
+ return 0;
+
+ } else {
+ /* RETURN */
+ return 0;
+ }
+
+ mode = get_irn_mode(loop_info.end_val);
+
+ DB((dbg, LEVEL_4, "start %N, end %N, step %N\n",
+ loop_info.start_val, loop_info.end_val, loop_info.step));
+
+ if (mode != mode_Is && mode != mode_Iu)
+ return 0;
+
+ /* TODO necessary? */
+ if (!are_mode_I(loop_info.start_val, loop_info.step, loop_info.end_val))
+ return 0;
+
+ DB((dbg, LEVEL_4, "mode integer\n"));
+
+ end_tar = get_Const_tarval(loop_info.end_val);
+ start_tar = get_Const_tarval(loop_info.start_val);
+ step_tar = get_Const_tarval(loop_info.step);
+
+ if (tarval_is_null(step_tar))
+ /* TODO Might be worth a warning. */
+ return 0;
+
+ DB((dbg, LEVEL_4, "step is not 0\n"));
+
+ if ((!tarval_is_negative(step_tar)) ^ (!is_Sub(loop_info.add)))
+ loop_info.decreasing = 1;
+
+ diff_tar = tarval_sub(end_tar, start_tar, mode);
+
+ /* We need at least count_tar steps to be close to end_val, maybe more.
+ * No way, that we have gone too many steps.
+ * This represents the 'latest value'.
+ * (If condition checks against latest value, is checked later) */
+ count_tar = tarval_div(diff_tar, step_tar);
+
+ /* Iv will not pass end_val (except overflows).
+ * Nothing done, as it would yield to no advantage. */
+ if (tarval_is_negative(count_tar)) {
+ DB((dbg, LEVEL_1, "Loop is endless or never taken."));
+ /* TODO Might be worth a warning. */
+ return 0;
+ }
+
+ count_stats(stats.u_simple_counting_loop);
+
+ loop_info.latest_value = is_latest_val;
+
+ /* TODO split here
+ if (! is_simple_counting_loop(&count_tar))
+ return 0;
+ */
+
+ /* stepped can be negative, if step < 0 */
+ stepped = tarval_mul(count_tar, step_tar);
+
+ /* step as close to end_val as possible, */
+ /* |stepped| <= |end_tar|, and dist(stepped, end_tar) is smaller than a step. */
+ if (is_Sub(loop_info.add))
+ stepped = tarval_sub(start_tar, stepped, mode_Is);
+ else
+ stepped = tarval_add(start_tar, stepped);
+
+ DB((dbg, LEVEL_4, "stepped to %ld\n", get_tarval_long(stepped)));
+
+ proj_proj = get_Proj_proj(projres);
+ /* Assure that norm_proj is the stay-in-loop case. */
+ if (loop_info.exit_cond == 1)
+ norm_proj = get_math_inverted_case(proj_proj);
+ else
+ norm_proj = proj_proj;
+
+ DB((dbg, LEVEL_4, "normalized projection %s\n", get_pnc_string(norm_proj)));
+
+ /* Executed at most once (stay in counting loop if a Eq b) */
+ if (norm_proj == pn_Cmp_Eq)
+ /* TODO Might be worth a warning. */
+ return 0;
+
+ /* calculates next values and increases count_tar according to it */
+ success = simulate_next(&count_tar, stepped, step_tar, end_tar, norm_proj);
+ if (! success)
+ return 0;
+
+ /* We run loop once more, if we compare to the
+ * not yet in-/decreased iv. */
+ if (is_latest_val == 0) {
+ DB((dbg, LEVEL_4, "condition uses not latest iv value\n"));
+ count_tar = tarval_add(count_tar, get_tarval_one(mode));
+ }
+
+ DB((dbg, LEVEL_4, "loop taken %ld times\n", get_tarval_long(count_tar)));
+
+ /* Assure the loop is taken at least 1 time. */
+ if (tarval_is_null(count_tar)) {
+ /* TODO Might be worth a warning. */
+ return 0;
+ }
+
+ loop_info.count_tar = count_tar;
+ return get_preferred_factor_constant(count_tar);
+}
+
+/**
+ * Loop unrolling
+ */
+static void unroll_loop(void)
+{
+ unroll_nr = 0;
+
+ /* get_unroll_decision_constant and invariant are completely
+ * independent for flexibility.
+ * Some checks may be performed twice. */
+
+ /* constant case? */
+ if (opt_params.allow_const_unrolling)
+ unroll_nr = get_unroll_decision_constant();
+ if (unroll_nr > 1) {
+ loop_info.unroll_kind = constant;
+
+ } else {
+ /* invariant case? */
+ if (opt_params.allow_invar_unrolling)
+ unroll_nr = get_unroll_decision_invariant();
+ if (unroll_nr > 1)
+ loop_info.unroll_kind = invariant;
+ }
+
+ DB((dbg, LEVEL_1, " *** Unrolling %d times ***\n", unroll_nr));
+
+ if (unroll_nr > 1) {
+ loop_entries = NEW_ARR_F(entry_edge, 0);
+
+ /* Get loop outs */
+ irg_walk_graph(current_ir_graph, get_loop_entries, NULL, NULL);
+
+ if ((int)get_tarval_long(loop_info.count_tar) == unroll_nr)
+ loop_info.needs_backedge = 0;
+ else
+ loop_info.needs_backedge = 1;
+
+ /* Use phase to keep copy of nodes from the condition chain. */
+ phase = new_phase(current_ir_graph, phase_irn_init_default);
+
+ /* Copies the loop */
+ copy_loop(loop_entries, unroll_nr - 1);
+
+ /* Line up the floating copies. */
+ place_copies(unroll_nr - 1);
+
+ /* Remove phis with 1 in*/
+ irg_walk_graph(current_ir_graph, correct_phis, NULL, NULL);
+
+ /* dump_ir_block_graph(current_ir_graph, "-DONE"); */
+
+ if (loop_info.unroll_kind == constant)
+ count_stats(stats.constant_unroll);
+ else
+ count_stats(stats.invariant_unroll);
+
+ set_irg_doms_inconsistent(current_ir_graph);
+ set_irg_loopinfo_inconsistent(current_ir_graph);
+ /* TODO is it? */
+ set_irg_outs_inconsistent(current_ir_graph);
+
+ DEL_ARR_F(loop_entries);
+ }