+
+/* Split loop exit edge EXIT. The things are a bit complicated by a need to
+ preserve the loop closed ssa form. */
+
+void
+split_loop_exit_edge (edge exit)
+{
+ basic_block dest = exit->dest;
+ basic_block bb = split_edge (exit);
+ tree phi, new_phi, new_name, name;
+ use_operand_p op_p;
+
+ for (phi = phi_nodes (dest); phi; phi = PHI_CHAIN (phi))
+ {
+ op_p = PHI_ARG_DEF_PTR_FROM_EDGE (phi, single_succ_edge (bb));
+
+ name = USE_FROM_PTR (op_p);
+
+ /* If the argument of the PHI node is a constant, we do not need
+ to keep it inside loop. */
+ if (TREE_CODE (name) != SSA_NAME)
+ continue;
+
+ /* Otherwise create an auxiliary phi node that will copy the value
+ of the SSA name out of the loop. */
+ new_name = duplicate_ssa_name (name, NULL);
+ new_phi = create_phi_node (new_name, bb);
+ SSA_NAME_DEF_STMT (new_name) = new_phi;
+ add_phi_arg (new_phi, name, exit);
+ SET_USE (op_p, new_name);
+ }
+}
+
+/* Returns the basic block in that statements should be emitted for induction
+ variables incremented at the end of the LOOP. */
+
+basic_block
+ip_end_pos (struct loop *loop)
+{
+ return loop->latch;
+}
+
+/* Returns the basic block in that statements should be emitted for induction
+ variables incremented just before exit condition of a LOOP. */
+
+basic_block
+ip_normal_pos (struct loop *loop)
+{
+ tree last;
+ basic_block bb;
+ edge exit;
+
+ if (!single_pred_p (loop->latch))
+ return NULL;
+
+ bb = single_pred (loop->latch);
+ last = last_stmt (bb);
+ if (TREE_CODE (last) != COND_EXPR)
+ return NULL;
+
+ exit = EDGE_SUCC (bb, 0);
+ if (exit->dest == loop->latch)
+ exit = EDGE_SUCC (bb, 1);
+
+ if (flow_bb_inside_loop_p (loop, exit->dest))
+ return NULL;
+
+ return bb;
+}
+
+/* Stores the standard position for induction variable increment in LOOP
+ (just before the exit condition if it is available and latch block is empty,
+ end of the latch block otherwise) to BSI. INSERT_AFTER is set to true if
+ the increment should be inserted after *BSI. */
+
+void
+standard_iv_increment_position (struct loop *loop, block_stmt_iterator *bsi,
+ bool *insert_after)
+{
+ basic_block bb = ip_normal_pos (loop), latch = ip_end_pos (loop);
+ tree last = last_stmt (latch);
+
+ if (!bb
+ || (last && TREE_CODE (last) != LABEL_EXPR))
+ {
+ *bsi = bsi_last (latch);
+ *insert_after = true;
+ }
+ else
+ {
+ *bsi = bsi_last (bb);
+ *insert_after = false;
+ }
+}
+
+/* Copies phi node arguments for duplicated blocks. The index of the first
+ duplicated block is FIRST_NEW_BLOCK. */
+
+static void
+copy_phi_node_args (unsigned first_new_block)
+{
+ unsigned i;
+
+ for (i = first_new_block; i < (unsigned) last_basic_block; i++)
+ BASIC_BLOCK (i)->flags |= BB_DUPLICATED;
+
+ for (i = first_new_block; i < (unsigned) last_basic_block; i++)
+ add_phi_args_after_copy_bb (BASIC_BLOCK (i));
+
+ for (i = first_new_block; i < (unsigned) last_basic_block; i++)
+ BASIC_BLOCK (i)->flags &= ~BB_DUPLICATED;
+}
+
+
+/* The same as cfgloopmanip.c:duplicate_loop_to_header_edge, but also
+ updates the PHI nodes at start of the copied region. In order to
+ achieve this, only loops whose exits all lead to the same location
+ are handled.
+
+ Notice that we do not completely update the SSA web after
+ duplication. The caller is responsible for calling update_ssa
+ after the loop has been duplicated. */
+
+bool
+tree_duplicate_loop_to_header_edge (struct loop *loop, edge e,
+ unsigned int ndupl, sbitmap wont_exit,
+ edge orig, edge *to_remove,
+ unsigned int *n_to_remove, int flags)
+{
+ unsigned first_new_block;
+
+ if (!(current_loops->state & LOOPS_HAVE_SIMPLE_LATCHES))
+ return false;
+ if (!(current_loops->state & LOOPS_HAVE_PREHEADERS))
+ return false;
+
+#ifdef ENABLE_CHECKING
+ 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, n_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;
+}
+
+/* Build if (COND) goto THEN_LABEL; else goto ELSE_LABEL; */
+
+static tree
+build_if_stmt (tree cond, tree then_label, tree else_label)
+{
+ return build3 (COND_EXPR, void_type_node,
+ cond,
+ build1 (GOTO_EXPR, void_type_node, then_label),
+ build1 (GOTO_EXPR, void_type_node, else_label));
+}
+
+/* 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) * 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)
+{
+ tree stmts;
+ tree base = desc->control.base;
+ tree step = desc->control.step;
+ tree bound = desc->bound;
+ tree type = TREE_TYPE (base);
+ 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;
+
+ *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)
+ {
+ if (tree_int_cst_sign_bit (step))
+ cmp = GT_EXPR;
+ else
+ cmp = LT_EXPR;
+ }
+ else if (cmp == LT_EXPR)
+ {
+ gcc_assert (!tree_int_cst_sign_bit (step));
+ }
+ else if (cmp == GT_EXPR)
+ {
+ gcc_assert (tree_int_cst_sign_bit (step));
+ }
+ else
+ gcc_unreachable ();
+
+ /* The main body of the loop may be entered iff:
+
+ 1) desc->may_be_zero is false.
+ 2) it is possible to check that there are at least FACTOR iterations
+ of the loop, i.e., BOUND - step * FACTOR does not overflow.
+ 3) # of iterations is at least FACTOR */
+
+ if (!zero_p (desc->may_be_zero))
+ cond = fold_build2 (TRUTH_AND_EXPR, boolean_type_node,
+ invert_truthvalue (desc->may_be_zero),
+ cond);
+
+ bigstep = fold_build2 (MULT_EXPR, type, step,
+ build_int_cst_type (type, factor));
+ delta = fold_build2 (MINUS_EXPR, type, bigstep, step);
+ if (cmp == LT_EXPR)
+ assum = fold_build2 (GE_EXPR, boolean_type_node,
+ bound,
+ fold_build2 (PLUS_EXPR, type, min, delta));
+ else
+ assum = fold_build2 (LE_EXPR, boolean_type_node,
+ bound,
+ fold_build2 (PLUS_EXPR, type, max, delta));
+ cond = fold_build2 (TRUTH_AND_EXPR, boolean_type_node, assum, cond);
+
+ 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)
+ bsi_insert_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)
+ bsi_insert_on_edge_immediate (loop_preheader_edge (loop), stmts);
+ }
+ *enter_cond = cond;
+
+ base = force_gimple_operand (unshare_expr (base), &stmts, true, NULL_TREE);
+ if (stmts)
+ bsi_insert_on_edge_immediate (loop_preheader_edge (loop), stmts);
+ bound = force_gimple_operand (unshare_expr (bound), &stmts, true, NULL_TREE);
+ if (stmts)
+ bsi_insert_on_edge_immediate (loop_preheader_edge (loop), stmts);
+
+ *exit_base = base;
+ *exit_step = bigstep;
+ *exit_cmp = cmp;
+ *exit_bound = bound;
+}
+
+/* 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;
+ } */
+
+void
+tree_unroll_loop (struct loop *loop, unsigned factor,
+ edge exit, struct tree_niter_desc *desc)
+{
+ tree dont_exit, exit_if, ctr_before, ctr_after;
+ tree enter_main_cond, exit_base, exit_step, exit_bound;
+ enum tree_code exit_cmp;
+ tree phi_old_loop, phi_new_loop, phi_rest, 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 nonexit, new_nonexit;
+ block_stmt_iterator bsi;
+ use_operand_p op;
+ bool ok;
+ unsigned est_niter;
+ unsigned irr = loop_preheader_edge (loop)->flags & EDGE_IRREDUCIBLE_LOOP;
+ sbitmap wont_exit;
+
+ est_niter = expected_loop_iterations (loop);
+ determine_exit_conditions (loop, desc, factor,
+ &enter_main_cond, &exit_base, &exit_step,
+ &exit_cmp, &exit_bound);
+
+ new_loop = loop_version (loop, enter_main_cond, NULL, true);
+ gcc_assert (new_loop != NULL);
+ update_ssa (TODO_update_ssa);
+
+ /* Unroll the loop and remove the old exits. */
+ dont_exit = ((exit->flags & EDGE_TRUE_VALUE)
+ ? boolean_false_node
+ : boolean_true_node);
+ if (exit == EDGE_SUCC (exit->src, 0))
+ nonexit = EDGE_SUCC (exit->src, 1);
+ else
+ nonexit = EDGE_SUCC (exit->src, 0);
+ nonexit->probability = REG_BR_PROB_BASE;
+ exit->probability = 0;
+ nonexit->count += exit->count;
+ exit->count = 0;
+ exit_if = last_stmt (exit->src);
+ COND_EXPR_COND (exit_if) = dont_exit;
+ update_stmt (exit_if);
+
+ wont_exit = sbitmap_alloc (factor);
+ sbitmap_ones (wont_exit);
+ ok = tree_duplicate_loop_to_header_edge
+ (loop, loop_latch_edge (loop), factor - 1,
+ wont_exit, NULL, NULL, NULL, DLTHE_FLAG_UPDATE_FREQ);
+ free (wont_exit);
+ gcc_assert (ok);
+ update_ssa (TODO_update_ssa);
+
+ /* Prepare the cfg and update the phi nodes. */
+ rest = loop_preheader_edge (new_loop)->src;
+ precond_edge = single_pred_edge (rest);
+ split_edge (loop_latch_edge (loop));
+ exit_bb = single_pred (loop->latch);
+
+ new_exit = make_edge (exit_bb, rest, EDGE_FALSE_VALUE | irr);
+ new_exit->count = loop_preheader_edge (loop)->count;
+ est_niter = est_niter / factor + 1;
+ new_exit->probability = REG_BR_PROB_BASE / est_niter;
+
+ new_nonexit = single_pred_edge (loop->latch);
+ new_nonexit->flags = EDGE_TRUE_VALUE;
+ new_nonexit->probability = REG_BR_PROB_BASE - new_exit->probability;
+
+ old_entry = loop_preheader_edge (loop);
+ new_entry = loop_preheader_edge (new_loop);
+ old_latch = loop_latch_edge (loop);
+ for (phi_old_loop = phi_nodes (loop->header),
+ phi_new_loop = phi_nodes (new_loop->header);
+ phi_old_loop;
+ phi_old_loop = PHI_CHAIN (phi_old_loop),
+ phi_new_loop = PHI_CHAIN (phi_new_loop))
+ {
+ init = PHI_ARG_DEF_FROM_EDGE (phi_old_loop, old_entry);
+ op = PHI_ARG_DEF_PTR_FROM_EDGE (phi_new_loop, new_entry);
+ gcc_assert (operand_equal_for_phi_arg_p (init, USE_FROM_PTR (op)));
+ next = PHI_ARG_DEF_FROM_EDGE (phi_old_loop, old_latch);
+
+ /* Prefer using original variable as a base for the new ssa name.
+ This is necessary for virtual ops, and useful in order to avoid
+ losing debug info for real ops. */
+ if (TREE_CODE (next) == SSA_NAME)
+ var = SSA_NAME_VAR (next);
+ else if (TREE_CODE (init) == SSA_NAME)
+ var = SSA_NAME_VAR (init);
+ else
+ {
+ var = create_tmp_var (TREE_TYPE (init), "unrinittmp");
+ add_referenced_var (var);
+ }
+
+ new_init = make_ssa_name (var, NULL_TREE);
+ phi_rest = create_phi_node (new_init, rest);
+ SSA_NAME_DEF_STMT (new_init) = phi_rest;
+
+ add_phi_arg (phi_rest, init, precond_edge);
+ add_phi_arg (phi_rest, next, new_exit);
+ SET_USE (op, new_init);
+ }
+
+ /* Finally create the new counter for number of iterations and add the new
+ exit instruction. */
+ bsi = bsi_last (exit_bb);
+ create_iv (exit_base, exit_step, NULL_TREE, loop,
+ &bsi, true, &ctr_before, &ctr_after);
+ exit_if = build_if_stmt (build2 (exit_cmp, boolean_type_node, ctr_after,
+ exit_bound),
+ tree_block_label (loop->latch),
+ tree_block_label (rest));
+ bsi_insert_after (&bsi, exit_if, BSI_NEW_STMT);
+
+#ifdef ENABLE_CHECKING
+ verify_flow_info ();
+ verify_dominators (CDI_DOMINATORS);
+ verify_loop_structure ();
+ verify_loop_closed_ssa ();
+#endif
+}