+}
+
+/* Check if cur_loop is a simple counting loop.
+ * Start, step and end are constants.
+ * TODO The whole constant case should use procedures similar to
+ * the invariant case, as they are more versatile. */
+/* TODO split. */
+static unsigned get_unroll_decision_constant(void)
+{
+ ir_node *cmp, *iteration_path;
+ unsigned success, is_latest_val;
+ ir_tarval *start_tar, *end_tar, *step_tar, *diff_tar, *count_tar;
+ ir_tarval *stepped;
+ ir_relation proj_proj, norm_proj;
+ ir_mode *mode;
+
+ /* RETURN if loop is not 'simple' */
+ cmp = is_simple_loop();
+ if (cmp == 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
+ /\
+ */
+
+ success = get_const_pred(cmp, &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, "Case 2: 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, "Case 1: 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_4, "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_Cmp_relation(cmp);
+ /* Assure that norm_proj is the stay-in-loop case. */
+ if (loop_info.exit_cond == 1)
+ norm_proj = get_negated_relation(proj_proj);
+ else
+ norm_proj = proj_proj;
+
+ DB((dbg, LEVEL_4, "normalized projection %s\n", get_relation_string(norm_proj)));
+ /* Executed at most once (stay in counting loop if a Eq b) */
+ if (norm_proj == ir_relation_equal)
+ /* 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)
+{
+
+ if (! (loop_info.nodes > 0))
+ return;
+
+#if LOOP_IGNORE_NODE_LIMITS
+ DB((dbg, LEVEL_1, "WARNING: Loop node limitations ignored."));
+#else
+ if (loop_info.nodes > opt_params.max_unrolled_loop_size) {
+ DB((dbg, LEVEL_2, "Nodes %d > allowed nodes %d\n",
+ loop_info.nodes, opt_params.max_unrolled_loop_size));
+ count_stats(stats.too_large);
+ return;
+ }
+
+ if (loop_info.calls > 0) {
+ DB((dbg, LEVEL_2, "Calls %d > allowed calls 0\n",
+ loop_info.calls));
+ count_stats(stats.calls_limit);
+ return;
+ }