+ if (!loops_state_satisfies_p (LOOPS_HAVE_SIMPLE_LATCHES))
+ return false;
+ if (!loops_state_satisfies_p (LOOPS_HAVE_PREHEADERS))
+ return false;
+
+#ifdef ENABLE_CHECKING
+ if (loops_state_satisfies_p (LOOP_CLOSED_SSA))
+ verify_loop_closed_ssa ();
+#endif
+
+ first_new_block = last_basic_block;
+ if (!duplicate_loop_to_header_edge (loop, e, ndupl, wont_exit,
+ orig, to_remove, flags))
+ return false;
+
+ /* Readd the removed phi args for e. */
+ flush_pending_stmts (e);
+
+ /* Copy the phi node arguments. */
+ copy_phi_node_args (first_new_block);
+
+ scev_reset ();
+
+ return true;
+}
+
+/* Returns true if we can unroll LOOP FACTOR times. Number
+ of iterations of the loop is returned in NITER. */
+
+bool
+can_unroll_loop_p (struct loop *loop, unsigned factor,
+ struct tree_niter_desc *niter)
+{
+ edge exit;
+
+ /* Check whether unrolling is possible. We only want to unroll loops
+ for that we are able to determine number of iterations. We also
+ want to split the extra iterations of the loop from its end,
+ therefore we require that the loop has precisely one
+ exit. */
+
+ exit = single_dom_exit (loop);
+ if (!exit)
+ return false;
+
+ if (!number_of_iterations_exit (loop, exit, niter, false)
+ || niter->cmp == ERROR_MARK
+ /* Scalar evolutions analysis might have copy propagated
+ the abnormal ssa names into these expressions, hence
+ emitting the computations based on them during loop
+ unrolling might create overlapping life ranges for
+ them, and failures in out-of-ssa. */
+ || contains_abnormal_ssa_name_p (niter->may_be_zero)
+ || contains_abnormal_ssa_name_p (niter->control.base)
+ || contains_abnormal_ssa_name_p (niter->control.step)
+ || contains_abnormal_ssa_name_p (niter->bound))
+ return false;
+
+ /* And of course, we must be able to duplicate the loop. */
+ if (!can_duplicate_loop_p (loop))
+ return false;
+
+ /* The final loop should be small enough. */
+ if (tree_num_loop_insns (loop, &eni_size_weights) * factor
+ > (unsigned) PARAM_VALUE (PARAM_MAX_UNROLLED_INSNS))
+ return false;
+
+ return true;
+}
+
+/* Determines the conditions that control execution of LOOP unrolled FACTOR
+ times. DESC is number of iterations of LOOP. ENTER_COND is set to
+ condition that must be true if the main loop can be entered.
+ EXIT_BASE, EXIT_STEP, EXIT_CMP and EXIT_BOUND are set to values describing
+ how the exit from the unrolled loop should be controlled. */
+
+static void
+determine_exit_conditions (struct loop *loop, struct tree_niter_desc *desc,
+ unsigned factor, tree *enter_cond,
+ tree *exit_base, tree *exit_step,
+ enum tree_code *exit_cmp, tree *exit_bound)
+{
+ gimple_seq stmts;
+ tree base = desc->control.base;
+ tree step = desc->control.step;
+ tree bound = desc->bound;
+ tree type = TREE_TYPE (step);
+ tree bigstep, delta;
+ tree min = lower_bound_in_type (type, type);
+ tree max = upper_bound_in_type (type, type);
+ enum tree_code cmp = desc->cmp;
+ tree cond = boolean_true_node, assum;
+
+ /* For pointers, do the arithmetics in the type of step (sizetype). */
+ base = fold_convert (type, base);
+ bound = fold_convert (type, bound);
+
+ *enter_cond = boolean_false_node;
+ *exit_base = NULL_TREE;
+ *exit_step = NULL_TREE;
+ *exit_cmp = ERROR_MARK;
+ *exit_bound = NULL_TREE;
+ gcc_assert (cmp != ERROR_MARK);
+
+ /* We only need to be correct when we answer question
+ "Do at least FACTOR more iterations remain?" in the unrolled loop.
+ Thus, transforming BASE + STEP * i <> BOUND to
+ BASE + STEP * i < BOUND is ok. */
+ if (cmp == NE_EXPR)