+ bound = fold_build2 (MINUS_EXPR, type, bound, delta);
+ assum = fold_build2 (cmp, boolean_type_node, base, bound);
+ cond = fold_build2 (TRUTH_AND_EXPR, boolean_type_node, assum, cond);
+
+ cond = force_gimple_operand (unshare_expr (cond), &stmts, false, NULL_TREE);
+ if (stmts)
+ gsi_insert_seq_on_edge_immediate (loop_preheader_edge (loop), stmts);
+ /* cond now may be a gimple comparison, which would be OK, but also any
+ other gimple rhs (say a && b). In this case we need to force it to
+ operand. */
+ if (!is_gimple_condexpr (cond))
+ {
+ cond = force_gimple_operand (cond, &stmts, true, NULL_TREE);
+ if (stmts)
+ gsi_insert_seq_on_edge_immediate (loop_preheader_edge (loop), stmts);
+ }
+ *enter_cond = cond;
+
+ base = force_gimple_operand (unshare_expr (base), &stmts, true, NULL_TREE);
+ if (stmts)
+ gsi_insert_seq_on_edge_immediate (loop_preheader_edge (loop), stmts);
+ bound = force_gimple_operand (unshare_expr (bound), &stmts, true, NULL_TREE);
+ if (stmts)
+ gsi_insert_seq_on_edge_immediate (loop_preheader_edge (loop), stmts);
+
+ *exit_base = base;
+ *exit_step = bigstep;
+ *exit_cmp = cmp;
+ *exit_bound = bound;
+}
+
+/* Scales the frequencies of all basic blocks in LOOP that are strictly
+ dominated by BB by NUM/DEN. */
+
+static void
+scale_dominated_blocks_in_loop (struct loop *loop, basic_block bb,
+ int num, int den)
+{
+ basic_block son;
+
+ if (den == 0)
+ return;
+
+ for (son = first_dom_son (CDI_DOMINATORS, bb);
+ son;
+ son = next_dom_son (CDI_DOMINATORS, son))
+ {
+ if (!flow_bb_inside_loop_p (loop, son))
+ continue;
+ scale_bbs_frequencies_int (&son, 1, num, den);
+ scale_dominated_blocks_in_loop (loop, son, num, den);
+ }
+}
+
+/* Unroll LOOP FACTOR times. DESC describes number of iterations of LOOP.
+ EXIT is the exit of the loop to that DESC corresponds.
+
+ If N is number of iterations of the loop and MAY_BE_ZERO is the condition
+ under that loop exits in the first iteration even if N != 0,
+
+ while (1)
+ {
+ x = phi (init, next);
+
+ pre;
+ if (st)
+ break;
+ post;
+ }
+
+ becomes (with possibly the exit conditions formulated a bit differently,
+ avoiding the need to create a new iv):
+
+ if (MAY_BE_ZERO || N < FACTOR)
+ goto rest;
+
+ do
+ {
+ x = phi (init, next);
+
+ pre;
+ post;
+ pre;
+ post;
+ ...
+ pre;
+ post;
+ N -= FACTOR;
+
+ } while (N >= FACTOR);
+
+ rest:
+ init' = phi (init, x);
+
+ while (1)
+ {
+ x = phi (init', next);
+
+ pre;
+ if (st)
+ break;
+ post;
+ }
+
+ Before the loop is unrolled, TRANSFORM is called for it (only for the
+ unrolled loop, but not for its versioned copy). DATA is passed to
+ TRANSFORM. */
+
+/* Probability in % that the unrolled loop is entered. Just a guess. */
+#define PROB_UNROLLED_LOOP_ENTERED 90
+
+void
+tree_transform_and_unroll_loop (struct loop *loop, unsigned factor,
+ edge exit, struct tree_niter_desc *desc,
+ transform_callback transform,
+ void *data)
+{
+ gimple exit_if;
+ tree ctr_before, ctr_after;
+ tree enter_main_cond, exit_base, exit_step, exit_bound;
+ enum tree_code exit_cmp;
+ gimple phi_old_loop, phi_new_loop, phi_rest;
+ gimple_stmt_iterator psi_old_loop, psi_new_loop;
+ tree init, next, new_init, var;
+ struct loop *new_loop;
+ basic_block rest, exit_bb;
+ edge old_entry, new_entry, old_latch, precond_edge, new_exit;
+ edge new_nonexit, e;
+ gimple_stmt_iterator bsi;
+ use_operand_p op;
+ bool ok;
+ unsigned est_niter, prob_entry, scale_unrolled, scale_rest, freq_e, freq_h;
+ unsigned new_est_niter, i, prob;
+ unsigned irr = loop_preheader_edge (loop)->flags & EDGE_IRREDUCIBLE_LOOP;
+ sbitmap wont_exit;
+ VEC (edge, heap) *to_remove = NULL;
+
+ est_niter = expected_loop_iterations (loop);
+ determine_exit_conditions (loop, desc, factor,
+ &enter_main_cond, &exit_base, &exit_step,
+ &exit_cmp, &exit_bound);
+
+ /* Let us assume that the unrolled loop is quite likely to be entered. */
+ if (integer_nonzerop (enter_main_cond))
+ prob_entry = REG_BR_PROB_BASE;
+ else
+ prob_entry = PROB_UNROLLED_LOOP_ENTERED * REG_BR_PROB_BASE / 100;
+
+ /* The values for scales should keep profile consistent, and somewhat close
+ to correct.
+
+ TODO: The current value of SCALE_REST makes it appear that the loop that
+ is created by splitting the remaining iterations of the unrolled loop is
+ executed the same number of times as the original loop, and with the same
+ frequencies, which is obviously wrong. This does not appear to cause
+ problems, so we do not bother with fixing it for now. To make the profile
+ correct, we would need to change the probability of the exit edge of the
+ loop, and recompute the distribution of frequencies in its body because
+ of this change (scale the frequencies of blocks before and after the exit
+ by appropriate factors). */
+ scale_unrolled = prob_entry;
+ scale_rest = REG_BR_PROB_BASE;
+
+ new_loop = loop_version (loop, enter_main_cond, NULL,
+ prob_entry, scale_unrolled, scale_rest, true);
+ gcc_assert (new_loop != NULL);
+ update_ssa (TODO_update_ssa);
+
+ /* Determine the probability of the exit edge of the unrolled loop. */
+ new_est_niter = est_niter / factor;
+
+ /* Without profile feedback, loops for that we do not know a better estimate
+ are assumed to roll 10 times. When we unroll such loop, it appears to
+ roll too little, and it may even seem to be cold. To avoid this, we
+ ensure that the created loop appears to roll at least 5 times (but at
+ most as many times as before unrolling). */
+ if (new_est_niter < 5)