+ DB((dbg, LEVEL_4, "loop has 1 own backedge.\n"));
+
+ exit_block = get_nodes_block(loop_info.cf_out.pred);
+ /* The loop has to be tail-controlled.
+ * This can be changed/improved,
+ * but we would need a duff iv. */
+ if (exit_block != loop_block)
+ return NULL;
+
+ DB((dbg, LEVEL_4, "tail-controlled loop.\n"));
+
+ /* find value on which loop exit depends */
+ projx = loop_info.cf_out.pred;
+ cond = get_irn_n(projx, 0);
+ cmp = get_irn_n(cond, 0);
+
+ if (!is_Cmp(cmp))
+ return NULL;
+
+ DB((dbg, LEVEL_5, "projection is %s\n", get_relation_string(get_Cmp_relation(cmp))));
+
+ switch(get_Proj_proj(projx)) {
+ case pn_Cond_false:
+ loop_info.exit_cond = 0;
+ break;
+ case pn_Cond_true:
+ loop_info.exit_cond = 1;
+ break;
+ default:
+ panic("Cond Proj_proj other than true/false");
+ }
+
+ DB((dbg, LEVEL_4, "Valid Cmp.\n"));
+ return cmp;
+}
+
+/* Returns 1 if all nodes are mode_Iu or mode_Is. */
+static unsigned are_mode_I(ir_node *n1, ir_node* n2, ir_node *n3)
+{
+ ir_mode *m1 = get_irn_mode(n1);
+ ir_mode *m2 = get_irn_mode(n2);
+ ir_mode *m3 = get_irn_mode(n3);
+
+ if ((m1 == mode_Iu && m2 == mode_Iu && m3 == mode_Iu) ||
+ (m1 == mode_Is && m2 == mode_Is && m3 == mode_Is))
+ return 1;
+ else
+ return 0;
+}
+
+/* Checks if cur_loop is a simple tail-controlled counting loop
+ * with start and end value loop invariant, step constant. */
+static unsigned get_unroll_decision_invariant(void)
+{
+
+ ir_node *projres, *loop_condition, *iteration_path;
+ unsigned success;
+ ir_tarval *step_tar;
+ ir_mode *mode;
+
+
+ /* RETURN if loop is not 'simple' */
+ projres = is_simple_loop();
+ if (projres == NULL)
+ return 0;
+
+ /* Use a minimal size for the invariant unrolled loop,
+ * as duffs device produces overhead */
+ if (loop_info.nodes < opt_params.invar_unrolling_min_size)
+ return 0;
+
+ loop_condition = get_irn_n(projres, 0);
+
+ success = get_invariant_pred(loop_condition, &loop_info.end_val, &iteration_path);
+ DB((dbg, LEVEL_4, "pred invar %d\n", success));
+
+ if (! success)
+ return 0;
+
+ DB((dbg, LEVEL_4, "Invariant 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)) {
+
+ loop_info.add = iteration_path;
+ DB((dbg, LEVEL_4, "Case 1: 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, invariant);
+ if (! success)
+ return 0;
+
+ DB((dbg, LEVEL_4, "Got start A %N\n", loop_info.start_val));
+
+ } else if (is_Phi(iteration_path)) {
+ ir_node *new_iteration_phi;
+
+ loop_info.iteration_phi = iteration_path;
+ DB((dbg, LEVEL_4, "Case 2: 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, invariant);
+ if (! success)
+ return 0;
+
+ DB((dbg, LEVEL_4, "Got start B %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 (B) %N\n", loop_info.step));
+
+ if (loop_info.iteration_phi != new_iteration_phi)
+ return 0;
+
+ } else {
+ 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"));
+
+ 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"));
+
+ create_duffs_block();
+
+ return loop_info.max_unroll;
+}
+
+/* Returns unroll factor,
+ * given maximum unroll factor and number of loop passes. */
+static unsigned get_preferred_factor_constant(ir_tarval *count_tar)
+{
+ ir_tarval *tar_6, *tar_5, *tar_4, *tar_3, *tar_2;
+ unsigned prefer;
+ ir_mode *mode = get_irn_mode(loop_info.end_val);
+
+ tar_6 = new_tarval_from_long(6, mode);
+ tar_5 = new_tarval_from_long(5, mode);
+ tar_4 = new_tarval_from_long(4, mode);
+ tar_3 = new_tarval_from_long(3, mode);
+ tar_2 = new_tarval_from_long(2, mode);
+
+ /* loop passes % {6, 5, 4, 3, 2} == 0 */
+ if (tarval_is_null(tarval_mod(count_tar, tar_6)))
+ prefer = 6;
+ else if (tarval_is_null(tarval_mod(count_tar, tar_5)))
+ prefer = 5;
+ else if (tarval_is_null(tarval_mod(count_tar, tar_4)))
+ prefer = 4;
+ else if (tarval_is_null(tarval_mod(count_tar, tar_3)))
+ prefer = 3;
+ else if (tarval_is_null(tarval_mod(count_tar, tar_2)))
+ prefer = 2;
+ else {
+ /* gcd(max_unroll, count_tar) */
+ int a = loop_info.max_unroll;
+ int b = (int)get_tarval_long(count_tar);
+ int c;
+
+ DB((dbg, LEVEL_4, "gcd of max_unroll %d and count_tar %d: ", a, b));
+
+ do {
+ c = a % b;
+ a = b; b = c;
+ } while( c != 0);
+
+ DB((dbg, LEVEL_4, "%d\n", a));
+ return a;
+ }
+
+ 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;