+/* Returns 1 if one pred of node is invariant and the other is not.
+ * invar_pred and other are set analogously. */
+static unsigned get_invariant_pred(ir_node *node, ir_node **invar_pred, ir_node **other)
+{
+ ir_node *pred0 = get_irn_n(node, 0);
+ ir_node *pred1 = get_irn_n(node, 1);
+
+ *invar_pred = NULL;
+ *other = NULL;
+
+ if (is_loop_invariant_def(pred0)) {
+ DB((dbg, LEVEL_4, "pred0 invar %N\n", pred0));
+ *invar_pred = pred0;
+ *other = pred1;
+ }
+
+ if (is_loop_invariant_def(pred1)) {
+ DB((dbg, LEVEL_4, "pred1 invar %N\n", pred1));
+
+ if (*invar_pred != NULL) {
+ /* RETURN. We do not want both preds to be invariant. */
+ return 0;
+ }
+
+ *other = pred0;
+ *invar_pred = pred1;
+ return 1;
+ } else {
+ DB((dbg, LEVEL_4, "pred1 not invar %N\n", pred1));
+
+ if (*invar_pred != NULL)
+ return 1;
+ else
+ return 0;
+ }
+}
+
+/* Starts from a phi that may belong to an iv.
+ * If an add forms a loop with iteration_phi,
+ * and add uses a constant, 1 is returned
+ * and 'start' as well as 'add' are sane. */
+static unsigned get_start_and_add(ir_node *iteration_phi, unrolling_kind_flag role)
+{
+ int i;
+ ir_node *found_add = loop_info.add;
+ int arity = get_irn_arity(iteration_phi);
+
+ DB((dbg, LEVEL_4, "Find start and add from %N\n", iteration_phi));
+
+ for (i = 0; i < arity; ++i) {
+
+ /* Find start_val which needs to be pred of the iteration_phi.
+ * If start_val already known, sanity check. */
+ if (!is_backedge(get_nodes_block(loop_info.iteration_phi), i)) {
+ ir_node *found_start_val = get_irn_n(loop_info.iteration_phi, i);
+
+ DB((dbg, LEVEL_4, "found_start_val %N\n", found_start_val));
+
+ /* We already found a start_val it has to be always the same. */
+ if (loop_info.start_val && found_start_val != loop_info.start_val)
+ return 0;
+
+ if ((role == constant) && !(is_SymConst(found_start_val) || is_Const(found_start_val)))
+ return 0;
+ else if((role == constant) && !(is_loop_invariant_def(found_start_val)))
+ return 0;
+
+ loop_info.start_val = found_start_val;
+ }
+
+ /* The phi has to be in the loop head.
+ * Follow all own backedges. Every value supplied from these preds of the phi
+ * needs to origin from the same add. */
+ if (is_own_backedge(get_nodes_block(loop_info.iteration_phi), i)) {
+ ir_node *new_found = get_irn_n(loop_info.iteration_phi,i);
+
+ DB((dbg, LEVEL_4, "is add? %N\n", new_found));
+
+ if (! (is_Add(new_found) || is_Sub(new_found)) || (found_add && found_add != new_found))
+ return 0;
+ else
+ found_add = new_found;
+ }
+ }
+
+ loop_info.add = found_add;
+
+ return 1;
+}
+
+
+/* Returns 1 if one pred of node is a const value and the other is not.
+ * const_pred and other are set analogously. */
+static unsigned get_const_pred(ir_node *node, ir_node **const_pred, ir_node **other)
+{
+ ir_node *pred0 = get_irn_n(node, 0);
+ ir_node *pred1 = get_irn_n(node, 1);
+
+ DB((dbg, LEVEL_4, "Checking for constant pred of %N\n", node));
+
+ *const_pred = NULL;
+ *other = NULL;
+
+ /*DB((dbg, LEVEL_4, "is %N const\n", pred0));*/
+ if (is_Const(pred0) || is_SymConst(pred0)) {
+ *const_pred = pred0;
+ *other = pred1;
+ }
+
+ /*DB((dbg, LEVEL_4, "is %N const\n", pred1));*/
+ if (is_Const(pred1) || is_SymConst(pred1)) {
+ if (*const_pred != NULL) {
+ /* RETURN. We do not want both preds to be constant. */
+ return 0;
+ }
+
+ *other = pred0;
+ *const_pred = pred1;
+ }
+
+ if (*const_pred == NULL)
+ return 0;
+ else
+ return 1;
+}
+
+/* Returns 1 if loop exits within 2 steps of the iv.
+ * Norm_proj means we do not exit the loop.*/
+static unsigned simulate_next(ir_tarval **count_tar,
+ ir_tarval *stepped, ir_tarval *step_tar, ir_tarval *end_tar,
+ ir_relation norm_proj)
+{
+ ir_tarval *next;
+
+ DB((dbg, LEVEL_4, "Loop taken if (stepped)%ld %s (end)%ld ",
+ get_tarval_long(stepped),
+ get_relation_string((norm_proj)),
+ get_tarval_long(end_tar)));
+ DB((dbg, LEVEL_4, "comparing latest value %d\n", loop_info.latest_value));
+
+ /* If current iv does not stay in the loop,
+ * this run satisfied the exit condition. */
+ if (! (tarval_cmp(stepped, end_tar) & norm_proj))
+ return 1;
+
+ DB((dbg, LEVEL_4, "Result: (stepped)%ld IS %s (end)%ld\n",
+ get_tarval_long(stepped),
+ get_relation_string(tarval_cmp(stepped, end_tar)),
+ get_tarval_long(end_tar)));
+
+ /* next step */
+ if (is_Add(loop_info.add))
+ next = tarval_add(stepped, step_tar);
+ else
+ /* sub */
+ next = tarval_sub(stepped, step_tar, get_irn_mode(loop_info.end_val));
+
+ DB((dbg, LEVEL_4, "Loop taken if %ld %s %ld ",
+ get_tarval_long(next),
+ get_relation_string(norm_proj),
+ get_tarval_long(end_tar)));
+ DB((dbg, LEVEL_4, "comparing latest value %d\n", loop_info.latest_value));
+
+ /* Increase steps. */
+ *count_tar = tarval_add(*count_tar, get_tarval_one(get_tarval_mode(*count_tar)));
+
+ /* Next has to fail the loop condition, or we will never exit. */
+ if (! (tarval_cmp(next, end_tar) & norm_proj))
+ return 1;
+ else
+ return 0;
+}
+
+/* Check if loop meets requirements for a 'simple loop':
+ * - Exactly one cf out
+ * - Allowed calls
+ * - Max nodes after unrolling
+ * - tail-controlled
+ * - exactly one be
+ * - cmp
+ * Returns Projection of cmp node or NULL; */
+static ir_node *is_simple_loop(void)
+{
+ int arity, i;
+ ir_node *loop_block, *exit_block, *projx, *cond, *cmp;
+
+ /* Maximum of one condition, and no endless loops. */
+ if (loop_info.cf_outs != 1)
+ return NULL;
+
+ DB((dbg, LEVEL_4, "1 loop exit\n"));
+
+#if LOOP_IGNORE_NODE_LIMITS
+ /* Ignore loop size. Probably not wise in other than testcases. */
+ loop_info.max_unroll = 40;
+#else
+ /* Calculate maximum unroll_nr keeping node count below limit. */
+ loop_info.max_unroll = (int)((double)opt_params.max_unrolled_loop_size / (double)loop_info.nodes);
+ if (loop_info.max_unroll < 2) {
+ count_stats(stats.too_large);
+ return NULL;
+ }
+#endif
+
+
+ DB((dbg, LEVEL_4, "maximum unroll factor %u, to not exceed node limit \n",
+ opt_params.max_unrolled_loop_size));
+
+ arity = get_irn_arity(loop_head);
+ /* RETURN if we have more than 1 be. */
+ /* Get my backedges without alien bes. */
+ loop_block = NULL;
+ for (i = 0; i < arity; ++i) {
+ ir_node *pred = get_irn_n(loop_head, i);
+ if (is_own_backedge(loop_head, i)) {
+ if (loop_block)
+ /* Our simple loops may have only one backedge. */
+ return NULL;
+ else {
+ loop_block = get_nodes_block(pred);
+ loop_info.be_src_pos = i;
+ }
+ }
+ }
+
+ 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_Proj_proj(projx))));
+
+ 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, is_latest_val;
+ 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)) {
+
+ /* We test against the latest value of the iv. */
+ is_latest_val = 1;
+
+ 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;
+
+ /* 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 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;
+ }
+ }
+}
+
+/* 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;
+ }
+#endif
+
+ 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_2, " *** 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 (loop_info.unroll_kind == constant) {
+ if ((int)get_tarval_long(loop_info.count_tar) == unroll_nr)
+ loop_info.needs_backedge = 0;
+ else
+ loop_info.needs_backedge = 1;
+ } 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
+ * If there were no nested phis, this would not be necessary.
+ * Avoiding the creation in the first place
+ * leads to complex special cases. */
+ irg_walk_graph(current_ir_graph, correct_phis, NULL, NULL);
+
+ 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);
+ }
+
+}
+
+/* Analyzes the loop, and checks if size is within allowed range.
+ * Decides if loop will be processed. */
+static void init_analyze(ir_loop *loop)
+{
+ cur_loop = loop;
+
+ loop_head = NULL;
+ loop_head_valid = 1;
+
+ /* Reset loop info */
+ memset(&loop_info, 0, sizeof(loop_info_t));
+
+ DB((dbg, LEVEL_1, " >>>> current loop includes node %N <<<\n",
+ get_loop_node(loop, 0)));
+
+ /* Collect loop informations: head, node counts. */
+ irg_walk_graph(current_ir_graph, get_loop_info, NULL, NULL);
+
+ /* RETURN if there is no valid head */
+ if (!loop_head || !loop_head_valid) {
+ DB((dbg, LEVEL_1, "No valid loop head. Nothing done.\n"));
+ return;
+ } else {
+ DB((dbg, LEVEL_1, "Loophead: %N\n", loop_head));
+ }
+
+ if (loop_info.branches > opt_params.max_branches) {
+ DB((dbg, LEVEL_1, "Branches %d > allowed branches %d\n",
+ loop_info.branches, opt_params.max_branches));
+ count_stats(stats.calls_limit);
+ return;
+ }
+
+ switch (loop_op) {
+ case loop_op_inversion:
+ loop_inversion();
+ break;
+
+ case loop_op_unrolling:
+ unroll_loop();
+ break;
+
+ default:
+ panic("Loop optimization not implemented.");
+ }
+ DB((dbg, LEVEL_1, " <<<< end of loop with node %N >>>>\n",
+ get_loop_node(loop, 0)));
+}
+
+/* Find innermost loops and add them to loops. */
+static void find_innermost_loop(ir_loop *loop)
+{
+ /* descend into sons */
+ size_t sons = get_loop_n_sons(loop);
+
+ if (sons == 0) {
+ ARR_APP1(ir_loop *, loops, loop);
+ } else {
+ size_t s;
+ for (s = 0; s < sons; ++s) {
+ find_innermost_loop(get_loop_son(loop, s));
+ }
+ }
+}
+
+static void set_loop_params(void)
+{
+ opt_params.max_loop_size = 100;
+ opt_params.depth_adaption = -50;
+ opt_params.count_phi = 1;
+ opt_params.count_proj = 0;
+ opt_params.allowed_calls = 0;
+
+ opt_params.max_cc_size = 5;
+
+
+ opt_params.allow_const_unrolling = 1;
+ opt_params.allow_invar_unrolling = 0;
+
+ opt_params.invar_unrolling_min_size = 20;
+ opt_params.max_unrolled_loop_size = 400;
+ opt_params.max_branches = 9999;
+}
+
+/* Assure preconditions are met and go through all loops. */
+void loop_optimization(ir_graph *irg)
+{
+ ir_loop *loop;
+ size_t sons, nr;
+ size_t i;
+
+ set_loop_params();
+
+ /* Reset stats for this procedure */
+ reset_stats();
+
+ /* Preconditions */
+ set_current_ir_graph(irg);
+
+ edges_assure(irg);
+ assure_irg_outs(irg);
+
+ /* NOTE: sets only the loop attribute of blocks, not nodes */
+ /* NOTE: Kills links */
+ assure_cf_loop(irg);
+
+ ir_reserve_resources(irg, IR_RESOURCE_IRN_LINK | IR_RESOURCE_PHI_LIST);
+ collect_phiprojs(irg);
+ ir_free_resources(irg, IR_RESOURCE_IRN_LINK);
+
+ loop = get_irg_loop(irg);
+ sons = get_loop_n_sons(loop);
+
+ loops = NEW_ARR_F(ir_loop *, 0);
+ /* List all inner loops */
+ for (nr = 0; nr < sons; ++nr) {
+ find_innermost_loop(get_loop_son(loop, nr));
+ }
+
+ ir_reserve_resources(irg, IR_RESOURCE_IRN_LINK);
+ /* Set all links to NULL */
+ irg_walk_graph(current_ir_graph, reset_link, NULL, NULL);
+
+ for (i = 0; i < ARR_LEN(loops); ++i) {
+ ir_loop *loop = loops[i];
+
+ count_stats(stats.loops);
+
+ /* Analyze and handle loop */
+ init_analyze(loop);
+
+ /* Copied blocks do not have their phi list yet */
+ collect_phiprojs(irg);
+
+ /* Set links to NULL
+ * TODO Still necessary? */
+ irg_walk_graph(current_ir_graph, reset_link, NULL, NULL);
+ }
+
+ print_stats();
+
+ DEL_ARR_F(loops);
+ ir_free_resources(irg, IR_RESOURCE_IRN_LINK);
+ ir_free_resources(irg, IR_RESOURCE_PHI_LIST);
+}
+
+void do_loop_unrolling(ir_graph *irg)
+{
+ loop_op = loop_op_unrolling;
+
+ DB((dbg, LEVEL_1, " >>> unrolling (Startnode %N) <<<\n",
+ get_irg_start(irg)));
+
+ loop_optimization(irg);
+
+ DB((dbg, LEVEL_1, " >>> unrolling done (Startnode %N) <<<\n",
+ get_irg_start(irg)));
+}
+
+void do_loop_inversion(ir_graph *irg)
+{
+ loop_op = loop_op_inversion;
+
+ DB((dbg, LEVEL_1, " >>> inversion (Startnode %N) <<<\n",
+ get_irg_start(irg)));
+
+ loop_optimization(irg);
+
+ assure_cf_loop(irg);
+
+ DB((dbg, LEVEL_1, " >>> inversion done (Startnode %N) <<<\n",
+ get_irg_start(irg)));
+}
+
+void do_loop_peeling(ir_graph *irg)
+{
+ loop_op = loop_op_peeling;
+
+ DB((dbg, LEVEL_1, " >>> peeling (Startnode %N) <<<\n",
+ get_irg_start(irg)));
+
+ loop_optimization(irg);
+
+ DB((dbg, LEVEL_1, " >>> peeling done (Startnode %N) <<<\n",
+ get_irg_start(irg)));
+
+}
+
+ir_graph_pass_t *loop_inversion_pass(const char *name)
+{
+ return def_graph_pass(name ? name : "loop_inversion", do_loop_inversion);
+}
+
+ir_graph_pass_t *loop_unroll_pass(const char *name)
+{
+ return def_graph_pass(name ? name : "loop_unroll", do_loop_unrolling);
+}
+
+ir_graph_pass_t *loop_peeling_pass(const char *name)
+{
+ return def_graph_pass(name ? name : "loop_peeling", do_loop_peeling);
+}
+
+void firm_init_loop_opt(void)
+{