aboutsummaryrefslogtreecommitdiffstats
path: root/gcc-4.9/gcc/tree-ssa-loop-ivcanon.c
diff options
context:
space:
mode:
authorBen Cheng <bccheng@google.com>2014-03-26 05:37:19 (GMT)
committerBen Cheng <bccheng@google.com>2014-03-26 05:37:19 (GMT)
commit1bc5aee63eb72b341f506ad058502cd0361f0d10 (patch)
treec607e8252f3405424ff15bc2d00aa38dadbb2518 /gcc-4.9/gcc/tree-ssa-loop-ivcanon.c
parent283a0bf58fcf333c58a2a92c3ebbc41fb9eb1fdb (diff)
downloadtoolchain_gcc-1bc5aee63eb72b341f506ad058502cd0361f0d10.zip
toolchain_gcc-1bc5aee63eb72b341f506ad058502cd0361f0d10.tar.gz
toolchain_gcc-1bc5aee63eb72b341f506ad058502cd0361f0d10.tar.bz2
Initial checkin of GCC 4.9.0 from trunk (r208799).
Change-Id: I48a3c08bb98542aa215912a75f03c0890e497dba
Diffstat (limited to 'gcc-4.9/gcc/tree-ssa-loop-ivcanon.c')
-rw-r--r--gcc-4.9/gcc/tree-ssa-loop-ivcanon.c1434
1 files changed, 1434 insertions, 0 deletions
diff --git a/gcc-4.9/gcc/tree-ssa-loop-ivcanon.c b/gcc-4.9/gcc/tree-ssa-loop-ivcanon.c
new file mode 100644
index 0000000..b475b06
--- /dev/null
+++ b/gcc-4.9/gcc/tree-ssa-loop-ivcanon.c
@@ -0,0 +1,1434 @@
+/* Induction variable canonicalization and loop peeling.
+ Copyright (C) 2004-2014 Free Software Foundation, Inc.
+
+This file is part of GCC.
+
+GCC is free software; you can redistribute it and/or modify it
+under the terms of the GNU General Public License as published by the
+Free Software Foundation; either version 3, or (at your option) any
+later version.
+
+GCC is distributed in the hope that it will be useful, but WITHOUT
+ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or
+FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License
+for more details.
+
+You should have received a copy of the GNU General Public License
+along with GCC; see the file COPYING3. If not see
+<http://www.gnu.org/licenses/>. */
+
+/* This pass detects the loops that iterate a constant number of times,
+ adds a canonical induction variable (step -1, tested against 0)
+ and replaces the exit test. This enables the less powerful rtl
+ level analysis to use this information.
+
+ This might spoil the code in some cases (by increasing register pressure).
+ Note that in the case the new variable is not needed, ivopts will get rid
+ of it, so it might only be a problem when there are no other linear induction
+ variables. In that case the created optimization possibilities are likely
+ to pay up.
+
+ Additionally in case we detect that it is beneficial to unroll the
+ loop completely, we do it right here to expose the optimization
+ possibilities to the following passes. */
+
+#include "config.h"
+#include "system.h"
+#include "coretypes.h"
+#include "tm.h"
+#include "tree.h"
+#include "tm_p.h"
+#include "basic-block.h"
+#include "gimple-pretty-print.h"
+#include "tree-ssa-alias.h"
+#include "internal-fn.h"
+#include "gimple-fold.h"
+#include "tree-eh.h"
+#include "gimple-expr.h"
+#include "is-a.h"
+#include "gimple.h"
+#include "gimple-iterator.h"
+#include "gimple-ssa.h"
+#include "cgraph.h"
+#include "tree-cfg.h"
+#include "tree-phinodes.h"
+#include "ssa-iterators.h"
+#include "stringpool.h"
+#include "tree-ssanames.h"
+#include "tree-ssa-loop-manip.h"
+#include "tree-ssa-loop-niter.h"
+#include "tree-ssa-loop.h"
+#include "tree-into-ssa.h"
+#include "cfgloop.h"
+#include "tree-pass.h"
+#include "tree-chrec.h"
+#include "tree-scalar-evolution.h"
+#include "params.h"
+#include "flags.h"
+#include "tree-inline.h"
+#include "target.h"
+#include "tree-cfgcleanup.h"
+
+/* Specifies types of loops that may be unrolled. */
+
+enum unroll_level
+{
+ UL_SINGLE_ITER, /* Only loops that exit immediately in the first
+ iteration. */
+ UL_NO_GROWTH, /* Only loops whose unrolling will not cause increase
+ of code size. */
+ UL_ALL /* All suitable loops. */
+};
+
+/* Adds a canonical induction variable to LOOP iterating NITER times. EXIT
+ is the exit edge whose condition is replaced. */
+
+static void
+create_canonical_iv (struct loop *loop, edge exit, tree niter)
+{
+ edge in;
+ tree type, var;
+ gimple cond;
+ gimple_stmt_iterator incr_at;
+ enum tree_code cmp;
+
+ if (dump_file && (dump_flags & TDF_DETAILS))
+ {
+ fprintf (dump_file, "Added canonical iv to loop %d, ", loop->num);
+ print_generic_expr (dump_file, niter, TDF_SLIM);
+ fprintf (dump_file, " iterations.\n");
+ }
+
+ cond = last_stmt (exit->src);
+ in = EDGE_SUCC (exit->src, 0);
+ if (in == exit)
+ in = EDGE_SUCC (exit->src, 1);
+
+ /* Note that we do not need to worry about overflows, since
+ type of niter is always unsigned and all comparisons are
+ just for equality/nonequality -- i.e. everything works
+ with a modulo arithmetics. */
+
+ type = TREE_TYPE (niter);
+ niter = fold_build2 (PLUS_EXPR, type,
+ niter,
+ build_int_cst (type, 1));
+ incr_at = gsi_last_bb (in->src);
+ create_iv (niter,
+ build_int_cst (type, -1),
+ NULL_TREE, loop,
+ &incr_at, false, NULL, &var);
+
+ cmp = (exit->flags & EDGE_TRUE_VALUE) ? EQ_EXPR : NE_EXPR;
+ gimple_cond_set_code (cond, cmp);
+ gimple_cond_set_lhs (cond, var);
+ gimple_cond_set_rhs (cond, build_int_cst (type, 0));
+ update_stmt (cond);
+}
+
+/* Describe size of loop as detected by tree_estimate_loop_size. */
+struct loop_size
+{
+ /* Number of instructions in the loop. */
+ int overall;
+
+ /* Number of instructions that will be likely optimized out in
+ peeled iterations of loop (i.e. computation based on induction
+ variable where induction variable starts at known constant.) */
+ int eliminated_by_peeling;
+
+ /* Same statistics for last iteration of loop: it is smaller because
+ instructions after exit are not executed. */
+ int last_iteration;
+ int last_iteration_eliminated_by_peeling;
+
+ /* If some IV computation will become constant. */
+ bool constant_iv;
+
+ /* Number of call stmts that are not a builtin and are pure or const
+ present on the hot path. */
+ int num_pure_calls_on_hot_path;
+ /* Number of call stmts that are not a builtin and are not pure nor const
+ present on the hot path. */
+ int num_non_pure_calls_on_hot_path;
+ /* Number of statements other than calls in the loop. */
+ int non_call_stmts_on_hot_path;
+ /* Number of branches seen on the hot path. */
+ int num_branches_on_hot_path;
+};
+
+/* Return true if OP in STMT will be constant after peeling LOOP. */
+
+static bool
+constant_after_peeling (tree op, gimple stmt, struct loop *loop)
+{
+ affine_iv iv;
+
+ if (is_gimple_min_invariant (op))
+ return true;
+
+ /* We can still fold accesses to constant arrays when index is known. */
+ if (TREE_CODE (op) != SSA_NAME)
+ {
+ tree base = op;
+
+ /* First make fast look if we see constant array inside. */
+ while (handled_component_p (base))
+ base = TREE_OPERAND (base, 0);
+ if ((DECL_P (base)
+ && ctor_for_folding (base) != error_mark_node)
+ || CONSTANT_CLASS_P (base))
+ {
+ /* If so, see if we understand all the indices. */
+ base = op;
+ while (handled_component_p (base))
+ {
+ if (TREE_CODE (base) == ARRAY_REF
+ && !constant_after_peeling (TREE_OPERAND (base, 1), stmt, loop))
+ return false;
+ base = TREE_OPERAND (base, 0);
+ }
+ return true;
+ }
+ return false;
+ }
+
+ /* Induction variables are constants. */
+ if (!simple_iv (loop, loop_containing_stmt (stmt), op, &iv, false))
+ return false;
+ if (!is_gimple_min_invariant (iv.base))
+ return false;
+ if (!is_gimple_min_invariant (iv.step))
+ return false;
+ return true;
+}
+
+/* Computes an estimated number of insns in LOOP.
+ EXIT (if non-NULL) is an exite edge that will be eliminated in all but last
+ iteration of the loop.
+ EDGE_TO_CANCEL (if non-NULL) is an non-exit edge eliminated in the last iteration
+ of loop.
+ Return results in SIZE, estimate benefits for complete unrolling exiting by EXIT.
+ Stop estimating after UPPER_BOUND is met. Return true in this case. */
+
+static bool
+tree_estimate_loop_size (struct loop *loop, edge exit, edge edge_to_cancel, struct loop_size *size,
+ int upper_bound)
+{
+ basic_block *body = get_loop_body (loop);
+ gimple_stmt_iterator gsi;
+ unsigned int i;
+ bool after_exit;
+ vec<basic_block> path = get_loop_hot_path (loop);
+
+ size->overall = 0;
+ size->eliminated_by_peeling = 0;
+ size->last_iteration = 0;
+ size->last_iteration_eliminated_by_peeling = 0;
+ size->num_pure_calls_on_hot_path = 0;
+ size->num_non_pure_calls_on_hot_path = 0;
+ size->non_call_stmts_on_hot_path = 0;
+ size->num_branches_on_hot_path = 0;
+ size->constant_iv = 0;
+
+ if (dump_file && (dump_flags & TDF_DETAILS))
+ fprintf (dump_file, "Estimating sizes for loop %i\n", loop->num);
+ for (i = 0; i < loop->num_nodes; i++)
+ {
+ if (edge_to_cancel && body[i] != edge_to_cancel->src
+ && dominated_by_p (CDI_DOMINATORS, body[i], edge_to_cancel->src))
+ after_exit = true;
+ else
+ after_exit = false;
+ if (dump_file && (dump_flags & TDF_DETAILS))
+ fprintf (dump_file, " BB: %i, after_exit: %i\n", body[i]->index, after_exit);
+
+ for (gsi = gsi_start_bb (body[i]); !gsi_end_p (gsi); gsi_next (&gsi))
+ {
+ gimple stmt = gsi_stmt (gsi);
+ int num = estimate_num_insns (stmt, &eni_size_weights);
+ bool likely_eliminated = false;
+ bool likely_eliminated_last = false;
+ bool likely_eliminated_peeled = false;
+
+ if (dump_file && (dump_flags & TDF_DETAILS))
+ {
+ fprintf (dump_file, " size: %3i ", num);
+ print_gimple_stmt (dump_file, gsi_stmt (gsi), 0, 0);
+ }
+
+ /* Look for reasons why we might optimize this stmt away. */
+
+ if (gimple_has_side_effects (stmt))
+ ;
+ /* Exit conditional. */
+ else if (exit && body[i] == exit->src
+ && stmt == last_stmt (exit->src))
+ {
+ if (dump_file && (dump_flags & TDF_DETAILS))
+ fprintf (dump_file, " Exit condition will be eliminated "
+ "in peeled copies.\n");
+ likely_eliminated_peeled = true;
+ }
+ else if (edge_to_cancel && body[i] == edge_to_cancel->src
+ && stmt == last_stmt (edge_to_cancel->src))
+ {
+ if (dump_file && (dump_flags & TDF_DETAILS))
+ fprintf (dump_file, " Exit condition will be eliminated "
+ "in last copy.\n");
+ likely_eliminated_last = true;
+ }
+ /* Sets of IV variables */
+ else if (gimple_code (stmt) == GIMPLE_ASSIGN
+ && constant_after_peeling (gimple_assign_lhs (stmt), stmt, loop))
+ {
+ if (dump_file && (dump_flags & TDF_DETAILS))
+ fprintf (dump_file, " Induction variable computation will"
+ " be folded away.\n");
+ likely_eliminated = true;
+ }
+ /* Assignments of IV variables. */
+ else if (gimple_code (stmt) == GIMPLE_ASSIGN
+ && TREE_CODE (gimple_assign_lhs (stmt)) == SSA_NAME
+ && constant_after_peeling (gimple_assign_rhs1 (stmt), stmt, loop)
+ && (gimple_assign_rhs_class (stmt) != GIMPLE_BINARY_RHS
+ || constant_after_peeling (gimple_assign_rhs2 (stmt),
+ stmt, loop)))
+ {
+ size->constant_iv = true;
+ if (dump_file && (dump_flags & TDF_DETAILS))
+ fprintf (dump_file, " Constant expression will be folded away.\n");
+ likely_eliminated = true;
+ }
+ /* Conditionals. */
+ else if ((gimple_code (stmt) == GIMPLE_COND
+ && constant_after_peeling (gimple_cond_lhs (stmt), stmt, loop)
+ && constant_after_peeling (gimple_cond_rhs (stmt), stmt, loop))
+ || (gimple_code (stmt) == GIMPLE_SWITCH
+ && constant_after_peeling (gimple_switch_index (stmt), stmt, loop)))
+ {
+ if (dump_file && (dump_flags & TDF_DETAILS))
+ fprintf (dump_file, " Constant conditional.\n");
+ likely_eliminated = true;
+ }
+
+ size->overall += num;
+ if (likely_eliminated || likely_eliminated_peeled)
+ size->eliminated_by_peeling += num;
+ if (!after_exit)
+ {
+ size->last_iteration += num;
+ if (likely_eliminated || likely_eliminated_last)
+ size->last_iteration_eliminated_by_peeling += num;
+ }
+ if ((size->overall * 3 / 2 - size->eliminated_by_peeling
+ - size->last_iteration_eliminated_by_peeling) > upper_bound)
+ {
+ free (body);
+ path.release ();
+ return true;
+ }
+ }
+ }
+ while (path.length ())
+ {
+ basic_block bb = path.pop ();
+ for (gsi = gsi_start_bb (bb); !gsi_end_p (gsi); gsi_next (&gsi))
+ {
+ gimple stmt = gsi_stmt (gsi);
+ if (gimple_code (stmt) == GIMPLE_CALL)
+ {
+ int flags = gimple_call_flags (stmt);
+ tree decl = gimple_call_fndecl (stmt);
+
+ if (decl && DECL_IS_BUILTIN (decl)
+ && is_inexpensive_builtin (decl))
+ ;
+ else if (flags & (ECF_PURE | ECF_CONST))
+ size->num_pure_calls_on_hot_path++;
+ else
+ size->num_non_pure_calls_on_hot_path++;
+ size->num_branches_on_hot_path ++;
+ }
+ else if (gimple_code (stmt) != GIMPLE_CALL
+ && gimple_code (stmt) != GIMPLE_DEBUG)
+ size->non_call_stmts_on_hot_path++;
+ if (((gimple_code (stmt) == GIMPLE_COND
+ && (!constant_after_peeling (gimple_cond_lhs (stmt), stmt, loop)
+ || constant_after_peeling (gimple_cond_rhs (stmt), stmt, loop)))
+ || (gimple_code (stmt) == GIMPLE_SWITCH
+ && !constant_after_peeling (gimple_switch_index (stmt), stmt, loop)))
+ && (!exit || bb != exit->src))
+ size->num_branches_on_hot_path++;
+ }
+ }
+ path.release ();
+ if (dump_file && (dump_flags & TDF_DETAILS))
+ fprintf (dump_file, "size: %i-%i, last_iteration: %i-%i\n", size->overall,
+ size->eliminated_by_peeling, size->last_iteration,
+ size->last_iteration_eliminated_by_peeling);
+
+ free (body);
+ return false;
+}
+
+/* Estimate number of insns of completely unrolled loop.
+ It is (NUNROLL + 1) * size of loop body with taking into account
+ the fact that in last copy everything after exit conditional
+ is dead and that some instructions will be eliminated after
+ peeling.
+
+ Loop body is likely going to simplify further, this is difficult
+ to guess, we just decrease the result by 1/3. */
+
+static unsigned HOST_WIDE_INT
+estimated_unrolled_size (struct loop_size *size,
+ unsigned HOST_WIDE_INT nunroll)
+{
+ HOST_WIDE_INT unr_insns = ((nunroll)
+ * (HOST_WIDE_INT) (size->overall
+ - size->eliminated_by_peeling));
+ if (!nunroll)
+ unr_insns = 0;
+ unr_insns += size->last_iteration - size->last_iteration_eliminated_by_peeling;
+
+ unr_insns = unr_insns * 2 / 3;
+ if (unr_insns <= 0)
+ unr_insns = 1;
+
+ return unr_insns;
+}
+
+/* Loop LOOP is known to not loop. See if there is an edge in the loop
+ body that can be remove to make the loop to always exit and at
+ the same time it does not make any code potentially executed
+ during the last iteration dead.
+
+ After complette unrolling we still may get rid of the conditional
+ on the exit in the last copy even if we have no idea what it does.
+ This is quite common case for loops of form
+
+ int a[5];
+ for (i=0;i<b;i++)
+ a[i]=0;
+
+ Here we prove the loop to iterate 5 times but we do not know
+ it from induction variable.
+
+ For now we handle only simple case where there is exit condition
+ just before the latch block and the latch block contains no statements
+ with side effect that may otherwise terminate the execution of loop
+ (such as by EH or by terminating the program or longjmp).
+
+ In the general case we may want to cancel the paths leading to statements
+ loop-niter identified as having undefined effect in the last iteration.
+ The other cases are hopefully rare and will be cleaned up later. */
+
+static edge
+loop_edge_to_cancel (struct loop *loop)
+{
+ vec<edge> exits;
+ unsigned i;
+ edge edge_to_cancel;
+ gimple_stmt_iterator gsi;
+
+ /* We want only one predecestor of the loop. */
+ if (EDGE_COUNT (loop->latch->preds) > 1)
+ return NULL;
+
+ exits = get_loop_exit_edges (loop);
+
+ FOR_EACH_VEC_ELT (exits, i, edge_to_cancel)
+ {
+ /* Find the other edge than the loop exit
+ leaving the conditoinal. */
+ if (EDGE_COUNT (edge_to_cancel->src->succs) != 2)
+ continue;
+ if (EDGE_SUCC (edge_to_cancel->src, 0) == edge_to_cancel)
+ edge_to_cancel = EDGE_SUCC (edge_to_cancel->src, 1);
+ else
+ edge_to_cancel = EDGE_SUCC (edge_to_cancel->src, 0);
+
+ /* We only can handle conditionals. */
+ if (!(edge_to_cancel->flags & (EDGE_TRUE_VALUE | EDGE_FALSE_VALUE)))
+ continue;
+
+ /* We should never have conditionals in the loop latch. */
+ gcc_assert (edge_to_cancel->dest != loop->header);
+
+ /* Check that it leads to loop latch. */
+ if (edge_to_cancel->dest != loop->latch)
+ continue;
+
+ exits.release ();
+
+ /* Verify that the code in loop latch does nothing that may end program
+ execution without really reaching the exit. This may include
+ non-pure/const function calls, EH statements, volatile ASMs etc. */
+ for (gsi = gsi_start_bb (loop->latch); !gsi_end_p (gsi); gsi_next (&gsi))
+ if (gimple_has_side_effects (gsi_stmt (gsi)))
+ return NULL;
+ return edge_to_cancel;
+ }
+ exits.release ();
+ return NULL;
+}
+
+/* Remove all tests for exits that are known to be taken after LOOP was
+ peeled NPEELED times. Put gcc_unreachable before every statement
+ known to not be executed. */
+
+static bool
+remove_exits_and_undefined_stmts (struct loop *loop, unsigned int npeeled)
+{
+ struct nb_iter_bound *elt;
+ bool changed = false;
+
+ for (elt = loop->bounds; elt; elt = elt->next)
+ {
+ /* If statement is known to be undefined after peeling, turn it
+ into unreachable (or trap when debugging experience is supposed
+ to be good). */
+ if (!elt->is_exit
+ && elt->bound.ult (double_int::from_uhwi (npeeled)))
+ {
+ gimple_stmt_iterator gsi = gsi_for_stmt (elt->stmt);
+ gimple stmt = gimple_build_call
+ (builtin_decl_implicit (BUILT_IN_UNREACHABLE), 0);
+
+ gimple_set_location (stmt, gimple_location (elt->stmt));
+ gsi_insert_before (&gsi, stmt, GSI_NEW_STMT);
+ changed = true;
+ if (dump_file && (dump_flags & TDF_DETAILS))
+ {
+ fprintf (dump_file, "Forced statement unreachable: ");
+ print_gimple_stmt (dump_file, elt->stmt, 0, 0);
+ }
+ }
+ /* If we know the exit will be taken after peeling, update. */
+ else if (elt->is_exit
+ && elt->bound.ule (double_int::from_uhwi (npeeled)))
+ {
+ basic_block bb = gimple_bb (elt->stmt);
+ edge exit_edge = EDGE_SUCC (bb, 0);
+
+ if (dump_file && (dump_flags & TDF_DETAILS))
+ {
+ fprintf (dump_file, "Forced exit to be taken: ");
+ print_gimple_stmt (dump_file, elt->stmt, 0, 0);
+ }
+ if (!loop_exit_edge_p (loop, exit_edge))
+ exit_edge = EDGE_SUCC (bb, 1);
+ gcc_checking_assert (loop_exit_edge_p (loop, exit_edge));
+ if (exit_edge->flags & EDGE_TRUE_VALUE)
+ gimple_cond_make_true (elt->stmt);
+ else
+ gimple_cond_make_false (elt->stmt);
+ update_stmt (elt->stmt);
+ changed = true;
+ }
+ }
+ return changed;
+}
+
+/* Remove all exits that are known to be never taken because of the loop bound
+ discovered. */
+
+static bool
+remove_redundant_iv_tests (struct loop *loop)
+{
+ struct nb_iter_bound *elt;
+ bool changed = false;
+
+ if (!loop->any_upper_bound)
+ return false;
+ for (elt = loop->bounds; elt; elt = elt->next)
+ {
+ /* Exit is pointless if it won't be taken before loop reaches
+ upper bound. */
+ if (elt->is_exit && loop->any_upper_bound
+ && loop->nb_iterations_upper_bound.ult (elt->bound))
+ {
+ basic_block bb = gimple_bb (elt->stmt);
+ edge exit_edge = EDGE_SUCC (bb, 0);
+ struct tree_niter_desc niter;
+
+ if (!loop_exit_edge_p (loop, exit_edge))
+ exit_edge = EDGE_SUCC (bb, 1);
+
+ /* Only when we know the actual number of iterations, not
+ just a bound, we can remove the exit. */
+ if (!number_of_iterations_exit (loop, exit_edge,
+ &niter, false, false)
+ || !integer_onep (niter.assumptions)
+ || !integer_zerop (niter.may_be_zero)
+ || !niter.niter
+ || TREE_CODE (niter.niter) != INTEGER_CST
+ || !loop->nb_iterations_upper_bound.ult
+ (tree_to_double_int (niter.niter)))
+ continue;
+
+ if (dump_file && (dump_flags & TDF_DETAILS))
+ {
+ fprintf (dump_file, "Removed pointless exit: ");
+ print_gimple_stmt (dump_file, elt->stmt, 0, 0);
+ }
+ if (exit_edge->flags & EDGE_TRUE_VALUE)
+ gimple_cond_make_false (elt->stmt);
+ else
+ gimple_cond_make_true (elt->stmt);
+ update_stmt (elt->stmt);
+ changed = true;
+ }
+ }
+ return changed;
+}
+
+/* Stores loops that will be unlooped after we process whole loop tree. */
+static vec<loop_p> loops_to_unloop;
+static vec<int> loops_to_unloop_nunroll;
+
+/* Cancel all fully unrolled loops by putting __builtin_unreachable
+ on the latch edge.
+ We do it after all unrolling since unlooping moves basic blocks
+ across loop boundaries trashing loop closed SSA form as well
+ as SCEV info needed to be intact during unrolling.
+
+ IRRED_INVALIDATED is used to bookkeep if information about
+ irreducible regions may become invalid as a result
+ of the transformation.
+ LOOP_CLOSED_SSA_INVALIDATED is used to bookkepp the case
+ when we need to go into loop closed SSA form. */
+
+static void
+unloop_loops (bitmap loop_closed_ssa_invalidated,
+ bool *irred_invalidated)
+{
+ while (loops_to_unloop.length ())
+ {
+ struct loop *loop = loops_to_unloop.pop ();
+ int n_unroll = loops_to_unloop_nunroll.pop ();
+ basic_block latch = loop->latch;
+ edge latch_edge = loop_latch_edge (loop);
+ int flags = latch_edge->flags;
+ location_t locus = latch_edge->goto_locus;
+ gimple stmt;
+ gimple_stmt_iterator gsi;
+
+ remove_exits_and_undefined_stmts (loop, n_unroll);
+
+ /* Unloop destroys the latch edge. */
+ unloop (loop, irred_invalidated, loop_closed_ssa_invalidated);
+
+ /* Create new basic block for the latch edge destination and wire
+ it in. */
+ stmt = gimple_build_call (builtin_decl_implicit (BUILT_IN_UNREACHABLE), 0);
+ latch_edge = make_edge (latch, create_basic_block (NULL, NULL, latch), flags);
+ latch_edge->probability = 0;
+ latch_edge->count = 0;
+ latch_edge->flags |= flags;
+ latch_edge->goto_locus = locus;
+
+ latch_edge->dest->loop_father = current_loops->tree_root;
+ latch_edge->dest->count = 0;
+ latch_edge->dest->frequency = 0;
+ set_immediate_dominator (CDI_DOMINATORS, latch_edge->dest, latch_edge->src);
+
+ gsi = gsi_start_bb (latch_edge->dest);
+ gsi_insert_after (&gsi, stmt, GSI_NEW_STMT);
+ }
+ loops_to_unloop.release ();
+ loops_to_unloop_nunroll.release ();
+}
+
+/* Tries to unroll LOOP completely, i.e. NITER times.
+ UL determines which loops we are allowed to unroll.
+ EXIT is the exit of the loop that should be eliminated.
+ MAXITER specfy bound on number of iterations, -1 if it is
+ not known or too large for HOST_WIDE_INT. The location
+ LOCUS corresponding to the loop is used when emitting
+ a summary of the unroll to the dump file. */
+
+static bool
+try_unroll_loop_completely (struct loop *loop,
+ edge exit, tree niter,
+ enum unroll_level ul,
+ HOST_WIDE_INT maxiter,
+ location_t locus)
+{
+ unsigned HOST_WIDE_INT n_unroll, ninsns, max_unroll, unr_insns;
+ gimple cond;
+ struct loop_size size;
+ bool n_unroll_found = false;
+ edge edge_to_cancel = NULL;
+
+ /* See if we proved number of iterations to be low constant.
+
+ EXIT is an edge that will be removed in all but last iteration of
+ the loop.
+
+ EDGE_TO_CACNEL is an edge that will be removed from the last iteration
+ of the unrolled sequence and is expected to make the final loop not
+ rolling.
+
+ If the number of execution of loop is determined by standard induction
+ variable test, then EXIT and EDGE_TO_CANCEL are the two edges leaving
+ from the iv test. */
+ if (tree_fits_uhwi_p (niter))
+ {
+ n_unroll = tree_to_uhwi (niter);
+ n_unroll_found = true;
+ edge_to_cancel = EDGE_SUCC (exit->src, 0);
+ if (edge_to_cancel == exit)
+ edge_to_cancel = EDGE_SUCC (exit->src, 1);
+ }
+ /* We do not know the number of iterations and thus we can not eliminate
+ the EXIT edge. */
+ else
+ exit = NULL;
+
+ /* See if we can improve our estimate by using recorded loop bounds. */
+ if (maxiter >= 0
+ && (!n_unroll_found || (unsigned HOST_WIDE_INT)maxiter < n_unroll))
+ {
+ n_unroll = maxiter;
+ n_unroll_found = true;
+ /* Loop terminates before the IV variable test, so we can not
+ remove it in the last iteration. */
+ edge_to_cancel = NULL;
+ }
+
+ if (!n_unroll_found)
+ return false;
+
+ max_unroll = PARAM_VALUE (PARAM_MAX_COMPLETELY_PEEL_TIMES);
+ if (n_unroll > max_unroll)
+ return false;
+
+ if (!edge_to_cancel)
+ edge_to_cancel = loop_edge_to_cancel (loop);
+
+ if (n_unroll)
+ {
+ sbitmap wont_exit;
+ edge e;
+ unsigned i;
+ bool large;
+ vec<edge> to_remove = vNULL;
+ if (ul == UL_SINGLE_ITER)
+ return false;
+
+ large = tree_estimate_loop_size
+ (loop, exit, edge_to_cancel, &size,
+ PARAM_VALUE (PARAM_MAX_COMPLETELY_PEELED_INSNS));
+ ninsns = size.overall;
+ if (large)
+ {
+ if (dump_file && (dump_flags & TDF_DETAILS))
+ fprintf (dump_file, "Not unrolling loop %d: it is too large.\n",
+ loop->num);
+ return false;
+ }
+
+ unr_insns = estimated_unrolled_size (&size, n_unroll);
+ if (dump_file && (dump_flags & TDF_DETAILS))
+ {
+ fprintf (dump_file, " Loop size: %d\n", (int) ninsns);
+ fprintf (dump_file, " Estimated size after unrolling: %d\n",
+ (int) unr_insns);
+ }
+
+ /* If the code is going to shrink, we don't need to be extra cautious
+ on guessing if the unrolling is going to be profitable. */
+ if (unr_insns
+ /* If there is IV variable that will become constant, we save
+ one instruction in the loop prologue we do not account
+ otherwise. */
+ <= ninsns + (size.constant_iv != false))
+ ;
+ /* We unroll only inner loops, because we do not consider it profitable
+ otheriwse. We still can cancel loopback edge of not rolling loop;
+ this is always a good idea. */
+ else if (ul == UL_NO_GROWTH)
+ {
+ if (dump_file && (dump_flags & TDF_DETAILS))
+ fprintf (dump_file, "Not unrolling loop %d: size would grow.\n",
+ loop->num);
+ return false;
+ }
+ /* Outer loops tend to be less interesting candidates for complette
+ unrolling unless we can do a lot of propagation into the inner loop
+ body. For now we disable outer loop unrolling when the code would
+ grow. */
+ else if (loop->inner)
+ {
+ if (dump_file && (dump_flags & TDF_DETAILS))
+ fprintf (dump_file, "Not unrolling loop %d: "
+ "it is not innermost and code would grow.\n",
+ loop->num);
+ return false;
+ }
+ /* If there is call on a hot path through the loop, then
+ there is most probably not much to optimize. */
+ else if (size.num_non_pure_calls_on_hot_path)
+ {
+ if (dump_file && (dump_flags & TDF_DETAILS))
+ fprintf (dump_file, "Not unrolling loop %d: "
+ "contains call and code would grow.\n",
+ loop->num);
+ return false;
+ }
+ /* If there is pure/const call in the function, then we
+ can still optimize the unrolled loop body if it contains
+ some other interesting code than the calls and code
+ storing or cumulating the return value. */
+ else if (size.num_pure_calls_on_hot_path
+ /* One IV increment, one test, one ivtmp store
+ and one useful stmt. That is about minimal loop
+ doing pure call. */
+ && (size.non_call_stmts_on_hot_path
+ <= 3 + size.num_pure_calls_on_hot_path))
+ {
+ if (dump_file && (dump_flags & TDF_DETAILS))
+ fprintf (dump_file, "Not unrolling loop %d: "
+ "contains just pure calls and code would grow.\n",
+ loop->num);
+ return false;
+ }
+ /* Complette unrolling is major win when control flow is removed and
+ one big basic block is created. If the loop contains control flow
+ the optimization may still be a win because of eliminating the loop
+ overhead but it also may blow the branch predictor tables.
+ Limit number of branches on the hot path through the peeled
+ sequence. */
+ else if (size.num_branches_on_hot_path * (int)n_unroll
+ > PARAM_VALUE (PARAM_MAX_PEEL_BRANCHES))
+ {
+ if (dump_file && (dump_flags & TDF_DETAILS))
+ fprintf (dump_file, "Not unrolling loop %d: "
+ " number of branches on hot path in the unrolled sequence"
+ " reach --param max-peel-branches limit.\n",
+ loop->num);
+ return false;
+ }
+ else if (unr_insns
+ > (unsigned) PARAM_VALUE (PARAM_MAX_COMPLETELY_PEELED_INSNS))
+ {
+ if (dump_file && (dump_flags & TDF_DETAILS))
+ fprintf (dump_file, "Not unrolling loop %d: "
+ "(--param max-completely-peeled-insns limit reached).\n",
+ loop->num);
+ return false;
+ }
+
+ initialize_original_copy_tables ();
+ wont_exit = sbitmap_alloc (n_unroll + 1);
+ bitmap_ones (wont_exit);
+ bitmap_clear_bit (wont_exit, 0);
+
+ if (!gimple_duplicate_loop_to_header_edge (loop, loop_preheader_edge (loop),
+ n_unroll, wont_exit,
+ exit, &to_remove,
+ DLTHE_FLAG_UPDATE_FREQ
+ | DLTHE_FLAG_COMPLETTE_PEEL))
+ {
+ free_original_copy_tables ();
+ free (wont_exit);
+ if (dump_file && (dump_flags & TDF_DETAILS))
+ fprintf (dump_file, "Failed to duplicate the loop\n");
+ return false;
+ }
+
+ FOR_EACH_VEC_ELT (to_remove, i, e)
+ {
+ bool ok = remove_path (e);
+ gcc_assert (ok);
+ }
+
+ to_remove.release ();
+ free (wont_exit);
+ free_original_copy_tables ();
+ }
+
+
+ /* Remove the conditional from the last copy of the loop. */
+ if (edge_to_cancel)
+ {
+ cond = last_stmt (edge_to_cancel->src);
+ if (edge_to_cancel->flags & EDGE_TRUE_VALUE)
+ gimple_cond_make_false (cond);
+ else
+ gimple_cond_make_true (cond);
+ update_stmt (cond);
+ /* Do not remove the path. Doing so may remove outer loop
+ and confuse bookkeeping code in tree_unroll_loops_completelly. */
+ }
+
+ /* Store the loop for later unlooping and exit removal. */
+ loops_to_unloop.safe_push (loop);
+ loops_to_unloop_nunroll.safe_push (n_unroll);
+
+ if (dump_enabled_p ())
+ {
+ if (!n_unroll)
+ dump_printf_loc (MSG_OPTIMIZED_LOCATIONS | TDF_DETAILS, locus,
+ "loop turned into non-loop; it never loops\n");
+ else
+ {
+ dump_printf_loc (MSG_OPTIMIZED_LOCATIONS | TDF_DETAILS, locus,
+ "loop with %d iterations completely unrolled",
+ (int) (n_unroll + 1));
+ if (profile_info)
+ dump_printf (MSG_OPTIMIZED_LOCATIONS | TDF_DETAILS,
+ " (header execution count %d)",
+ (int)loop->header->count);
+ dump_printf (MSG_OPTIMIZED_LOCATIONS | TDF_DETAILS, "\n");
+ }
+ }
+
+ if (dump_file && (dump_flags & TDF_DETAILS))
+ {
+ if (exit)
+ fprintf (dump_file, "Exit condition of peeled iterations was "
+ "eliminated.\n");
+ if (edge_to_cancel)
+ fprintf (dump_file, "Last iteration exit edge was proved true.\n");
+ else
+ fprintf (dump_file, "Latch of last iteration was marked by "
+ "__builtin_unreachable ().\n");
+ }
+
+ return true;
+}
+
+/* Adds a canonical induction variable to LOOP if suitable.
+ CREATE_IV is true if we may create a new iv. UL determines
+ which loops we are allowed to completely unroll. If TRY_EVAL is true, we try
+ to determine the number of iterations of a loop by direct evaluation.
+ Returns true if cfg is changed. */
+
+static bool
+canonicalize_loop_induction_variables (struct loop *loop,
+ bool create_iv, enum unroll_level ul,
+ bool try_eval)
+{
+ edge exit = NULL;
+ tree niter;
+ HOST_WIDE_INT maxiter;
+ bool modified = false;
+ location_t locus = UNKNOWN_LOCATION;
+
+ niter = number_of_latch_executions (loop);
+ exit = single_exit (loop);
+ if (TREE_CODE (niter) == INTEGER_CST)
+ locus = gimple_location (last_stmt (exit->src));
+ else
+ {
+ /* If the loop has more than one exit, try checking all of them
+ for # of iterations determinable through scev. */
+ if (!exit)
+ niter = find_loop_niter (loop, &exit);
+
+ /* Finally if everything else fails, try brute force evaluation. */
+ if (try_eval
+ && (chrec_contains_undetermined (niter)
+ || TREE_CODE (niter) != INTEGER_CST))
+ niter = find_loop_niter_by_eval (loop, &exit);
+
+ if (exit)
+ locus = gimple_location (last_stmt (exit->src));
+
+ if (TREE_CODE (niter) != INTEGER_CST)
+ exit = NULL;
+ }
+
+ /* We work exceptionally hard here to estimate the bound
+ by find_loop_niter_by_eval. Be sure to keep it for future. */
+ if (niter && TREE_CODE (niter) == INTEGER_CST)
+ {
+ record_niter_bound (loop, tree_to_double_int (niter),
+ exit == single_likely_exit (loop), true);
+ }
+
+ /* Force re-computation of loop bounds so we can remove redundant exits. */
+ maxiter = max_loop_iterations_int (loop);
+
+ if (dump_file && (dump_flags & TDF_DETAILS)
+ && TREE_CODE (niter) == INTEGER_CST)
+ {
+ fprintf (dump_file, "Loop %d iterates ", loop->num);
+ print_generic_expr (dump_file, niter, TDF_SLIM);
+ fprintf (dump_file, " times.\n");
+ }
+ if (dump_file && (dump_flags & TDF_DETAILS)
+ && maxiter >= 0)
+ {
+ fprintf (dump_file, "Loop %d iterates at most %i times.\n", loop->num,
+ (int)maxiter);
+ }
+
+ /* Remove exits that are known to be never taken based on loop bound.
+ Needs to be called after compilation of max_loop_iterations_int that
+ populates the loop bounds. */
+ modified |= remove_redundant_iv_tests (loop);
+
+ if (try_unroll_loop_completely (loop, exit, niter, ul, maxiter, locus))
+ return true;
+
+ if (create_iv
+ && niter && !chrec_contains_undetermined (niter)
+ && exit && just_once_each_iteration_p (loop, exit->src))
+ create_canonical_iv (loop, exit, niter);
+
+ return modified;
+}
+
+/* The main entry point of the pass. Adds canonical induction variables
+ to the suitable loops. */
+
+unsigned int
+canonicalize_induction_variables (void)
+{
+ struct loop *loop;
+ bool changed = false;
+ bool irred_invalidated = false;
+ bitmap loop_closed_ssa_invalidated = BITMAP_ALLOC (NULL);
+
+ free_numbers_of_iterations_estimates ();
+ estimate_numbers_of_iterations ();
+
+ FOR_EACH_LOOP (loop, LI_FROM_INNERMOST)
+ {
+ changed |= canonicalize_loop_induction_variables (loop,
+ true, UL_SINGLE_ITER,
+ true);
+ }
+ gcc_assert (!need_ssa_update_p (cfun));
+
+ unloop_loops (loop_closed_ssa_invalidated, &irred_invalidated);
+ if (irred_invalidated
+ && loops_state_satisfies_p (LOOPS_HAVE_MARKED_IRREDUCIBLE_REGIONS))
+ mark_irreducible_loops ();
+
+ /* Clean up the information about numbers of iterations, since brute force
+ evaluation could reveal new information. */
+ scev_reset ();
+
+ if (!bitmap_empty_p (loop_closed_ssa_invalidated))
+ {
+ gcc_checking_assert (loops_state_satisfies_p (LOOP_CLOSED_SSA));
+ rewrite_into_loop_closed_ssa (NULL, TODO_update_ssa);
+ }
+ BITMAP_FREE (loop_closed_ssa_invalidated);
+
+ if (changed)
+ return TODO_cleanup_cfg;
+ return 0;
+}
+
+/* Propagate VAL into all uses of SSA_NAME. */
+
+static void
+propagate_into_all_uses (tree ssa_name, tree val)
+{
+ imm_use_iterator iter;
+ gimple use_stmt;
+
+ FOR_EACH_IMM_USE_STMT (use_stmt, iter, ssa_name)
+ {
+ gimple_stmt_iterator use_stmt_gsi = gsi_for_stmt (use_stmt);
+ use_operand_p use;
+
+ FOR_EACH_IMM_USE_ON_STMT (use, iter)
+ SET_USE (use, val);
+
+ if (is_gimple_assign (use_stmt)
+ && get_gimple_rhs_class (gimple_assign_rhs_code (use_stmt))
+ == GIMPLE_SINGLE_RHS)
+ {
+ tree rhs = gimple_assign_rhs1 (use_stmt);
+
+ if (TREE_CODE (rhs) == ADDR_EXPR)
+ recompute_tree_invariant_for_addr_expr (rhs);
+ }
+
+ fold_stmt_inplace (&use_stmt_gsi);
+ update_stmt (use_stmt);
+ maybe_clean_or_replace_eh_stmt (use_stmt, use_stmt);
+ }
+}
+
+/* Propagate constant SSA_NAMEs defined in basic block BB. */
+
+static void
+propagate_constants_for_unrolling (basic_block bb)
+{
+ gimple_stmt_iterator gsi;
+
+ /* Look for degenerate PHI nodes with constant argument. */
+ for (gsi = gsi_start_phis (bb); !gsi_end_p (gsi); )
+ {
+ gimple phi = gsi_stmt (gsi);
+ tree result = gimple_phi_result (phi);
+ tree arg = gimple_phi_arg_def (phi, 0);
+
+ if (gimple_phi_num_args (phi) == 1 && TREE_CODE (arg) == INTEGER_CST)
+ {
+ propagate_into_all_uses (result, arg);
+ gsi_remove (&gsi, true);
+ release_ssa_name (result);
+ }
+ else
+ gsi_next (&gsi);
+ }
+
+ /* Look for assignments to SSA names with constant RHS. */
+ for (gsi = gsi_start_bb (bb); !gsi_end_p (gsi); )
+ {
+ gimple stmt = gsi_stmt (gsi);
+ tree lhs;
+
+ if (is_gimple_assign (stmt)
+ && gimple_assign_rhs_code (stmt) == INTEGER_CST
+ && (lhs = gimple_assign_lhs (stmt), TREE_CODE (lhs) == SSA_NAME)
+ && !SSA_NAME_OCCURS_IN_ABNORMAL_PHI (lhs))
+ {
+ propagate_into_all_uses (lhs, gimple_assign_rhs1 (stmt));
+ gsi_remove (&gsi, true);
+ release_ssa_name (lhs);
+ }
+ else
+ gsi_next (&gsi);
+ }
+}
+
+/* Process loops from innermost to outer, stopping at the innermost
+ loop we unrolled. */
+
+static bool
+tree_unroll_loops_completely_1 (bool may_increase_size, bool unroll_outer,
+ vec<loop_p, va_heap>& father_stack,
+ struct loop *loop)
+{
+ struct loop *loop_father;
+ bool changed = false;
+ struct loop *inner;
+ enum unroll_level ul;
+
+ /* Process inner loops first. */
+ for (inner = loop->inner; inner != NULL; inner = inner->next)
+ changed |= tree_unroll_loops_completely_1 (may_increase_size,
+ unroll_outer, father_stack,
+ inner);
+
+ /* If we changed an inner loop we cannot process outer loops in this
+ iteration because SSA form is not up-to-date. Continue with
+ siblings of outer loops instead. */
+ if (changed)
+ return true;
+
+ /* Don't unroll #pragma omp simd loops until the vectorizer
+ attempts to vectorize those. */
+ if (loop->force_vect)
+ return false;
+
+ /* Try to unroll this loop. */
+ loop_father = loop_outer (loop);
+ if (!loop_father)
+ return false;
+
+ if (may_increase_size && optimize_loop_nest_for_speed_p (loop)
+ /* Unroll outermost loops only if asked to do so or they do
+ not cause code growth. */
+ && (unroll_outer || loop_outer (loop_father)))
+ ul = UL_ALL;
+ else
+ ul = UL_NO_GROWTH;
+
+ if (canonicalize_loop_induction_variables
+ (loop, false, ul, !flag_tree_loop_ivcanon))
+ {
+ /* If we'll continue unrolling, we need to propagate constants
+ within the new basic blocks to fold away induction variable
+ computations; otherwise, the size might blow up before the
+ iteration is complete and the IR eventually cleaned up. */
+ if (loop_outer (loop_father) && !loop_father->aux)
+ {
+ father_stack.safe_push (loop_father);
+ loop_father->aux = loop_father;
+ }
+
+ return true;
+ }
+
+ return false;
+}
+
+/* Unroll LOOPS completely if they iterate just few times. Unless
+ MAY_INCREASE_SIZE is true, perform the unrolling only if the
+ size of the code does not increase. */
+
+unsigned int
+tree_unroll_loops_completely (bool may_increase_size, bool unroll_outer)
+{
+ auto_vec<loop_p, 16> father_stack;
+ bool changed;
+ int iteration = 0;
+ bool irred_invalidated = false;
+
+ do
+ {
+ changed = false;
+ bitmap loop_closed_ssa_invalidated = NULL;
+
+ if (loops_state_satisfies_p (LOOP_CLOSED_SSA))
+ loop_closed_ssa_invalidated = BITMAP_ALLOC (NULL);
+
+ free_numbers_of_iterations_estimates ();
+ estimate_numbers_of_iterations ();
+
+ changed = tree_unroll_loops_completely_1 (may_increase_size,
+ unroll_outer, father_stack,
+ current_loops->tree_root);
+ if (changed)
+ {
+ struct loop **iter;
+ unsigned i;
+
+ /* Be sure to skip unlooped loops while procesing father_stack
+ array. */
+ FOR_EACH_VEC_ELT (loops_to_unloop, i, iter)
+ (*iter)->aux = NULL;
+ FOR_EACH_VEC_ELT (father_stack, i, iter)
+ if (!(*iter)->aux)
+ *iter = NULL;
+ unloop_loops (loop_closed_ssa_invalidated, &irred_invalidated);
+
+ /* We can not use TODO_update_ssa_no_phi because VOPS gets confused. */
+ if (loop_closed_ssa_invalidated
+ && !bitmap_empty_p (loop_closed_ssa_invalidated))
+ rewrite_into_loop_closed_ssa (loop_closed_ssa_invalidated,
+ TODO_update_ssa);
+ else
+ update_ssa (TODO_update_ssa);
+
+ /* Propagate the constants within the new basic blocks. */
+ FOR_EACH_VEC_ELT (father_stack, i, iter)
+ if (*iter)
+ {
+ unsigned j;
+ basic_block *body = get_loop_body_in_dom_order (*iter);
+ for (j = 0; j < (*iter)->num_nodes; j++)
+ propagate_constants_for_unrolling (body[j]);
+ free (body);
+ (*iter)->aux = NULL;
+ }
+ father_stack.truncate (0);
+
+ /* This will take care of removing completely unrolled loops
+ from the loop structures so we can continue unrolling now
+ innermost loops. */
+ if (cleanup_tree_cfg ())
+ update_ssa (TODO_update_ssa_only_virtuals);
+
+ /* Clean up the information about numbers of iterations, since
+ complete unrolling might have invalidated it. */
+ scev_reset ();
+#ifdef ENABLE_CHECKING
+ if (loops_state_satisfies_p (LOOP_CLOSED_SSA))
+ verify_loop_closed_ssa (true);
+#endif
+ }
+ if (loop_closed_ssa_invalidated)
+ BITMAP_FREE (loop_closed_ssa_invalidated);
+ }
+ while (changed
+ && ++iteration <= PARAM_VALUE (PARAM_MAX_UNROLL_ITERATIONS));
+
+ father_stack.release ();
+
+ if (irred_invalidated
+ && loops_state_satisfies_p (LOOPS_HAVE_MARKED_IRREDUCIBLE_REGIONS))
+ mark_irreducible_loops ();
+
+ return 0;
+}
+
+/* Canonical induction variable creation pass. */
+
+static unsigned int
+tree_ssa_loop_ivcanon (void)
+{
+ if (number_of_loops (cfun) <= 1)
+ return 0;
+
+ return canonicalize_induction_variables ();
+}
+
+static bool
+gate_tree_ssa_loop_ivcanon (void)
+{
+ return flag_tree_loop_ivcanon != 0;
+}
+
+namespace {
+
+const pass_data pass_data_iv_canon =
+{
+ GIMPLE_PASS, /* type */
+ "ivcanon", /* name */
+ OPTGROUP_LOOP, /* optinfo_flags */
+ true, /* has_gate */
+ true, /* has_execute */
+ TV_TREE_LOOP_IVCANON, /* tv_id */
+ ( PROP_cfg | PROP_ssa ), /* properties_required */
+ 0, /* properties_provided */
+ 0, /* properties_destroyed */
+ 0, /* todo_flags_start */
+ 0, /* todo_flags_finish */
+};
+
+class pass_iv_canon : public gimple_opt_pass
+{
+public:
+ pass_iv_canon (gcc::context *ctxt)
+ : gimple_opt_pass (pass_data_iv_canon, ctxt)
+ {}
+
+ /* opt_pass methods: */
+ bool gate () { return gate_tree_ssa_loop_ivcanon (); }
+ unsigned int execute () { return tree_ssa_loop_ivcanon (); }
+
+}; // class pass_iv_canon
+
+} // anon namespace
+
+gimple_opt_pass *
+make_pass_iv_canon (gcc::context *ctxt)
+{
+ return new pass_iv_canon (ctxt);
+}
+
+/* Complete unrolling of loops. */
+
+static unsigned int
+tree_complete_unroll (void)
+{
+ if (number_of_loops (cfun) <= 1)
+ return 0;
+
+ return tree_unroll_loops_completely (flag_unroll_loops
+ || flag_peel_loops
+ || optimize >= 3, true);
+}
+
+static bool
+gate_tree_complete_unroll (void)
+{
+ return true;
+}
+
+namespace {
+
+const pass_data pass_data_complete_unroll =
+{
+ GIMPLE_PASS, /* type */
+ "cunroll", /* name */
+ OPTGROUP_LOOP, /* optinfo_flags */
+ true, /* has_gate */
+ true, /* has_execute */
+ TV_COMPLETE_UNROLL, /* tv_id */
+ ( PROP_cfg | PROP_ssa ), /* properties_required */
+ 0, /* properties_provided */
+ 0, /* properties_destroyed */
+ 0, /* todo_flags_start */
+ 0, /* todo_flags_finish */
+};
+
+class pass_complete_unroll : public gimple_opt_pass
+{
+public:
+ pass_complete_unroll (gcc::context *ctxt)
+ : gimple_opt_pass (pass_data_complete_unroll, ctxt)
+ {}
+
+ /* opt_pass methods: */
+ bool gate () { return gate_tree_complete_unroll (); }
+ unsigned int execute () { return tree_complete_unroll (); }
+
+}; // class pass_complete_unroll
+
+} // anon namespace
+
+gimple_opt_pass *
+make_pass_complete_unroll (gcc::context *ctxt)
+{
+ return new pass_complete_unroll (ctxt);
+}
+
+/* Complete unrolling of inner loops. */
+
+static unsigned int
+tree_complete_unroll_inner (void)
+{
+ unsigned ret = 0;
+
+ loop_optimizer_init (LOOPS_NORMAL
+ | LOOPS_HAVE_RECORDED_EXITS);
+ if (number_of_loops (cfun) > 1)
+ {
+ scev_initialize ();
+ ret = tree_unroll_loops_completely (optimize >= 3, false);
+ free_numbers_of_iterations_estimates ();
+ scev_finalize ();
+ }
+ loop_optimizer_finalize ();
+
+ return ret;
+}
+
+static bool
+gate_tree_complete_unroll_inner (void)
+{
+ return optimize >= 2;
+}
+
+namespace {
+
+const pass_data pass_data_complete_unrolli =
+{
+ GIMPLE_PASS, /* type */
+ "cunrolli", /* name */
+ OPTGROUP_LOOP, /* optinfo_flags */
+ true, /* has_gate */
+ true, /* has_execute */
+ TV_COMPLETE_UNROLL, /* tv_id */
+ ( PROP_cfg | PROP_ssa ), /* properties_required */
+ 0, /* properties_provided */
+ 0, /* properties_destroyed */
+ 0, /* todo_flags_start */
+ TODO_verify_flow, /* todo_flags_finish */
+};
+
+class pass_complete_unrolli : public gimple_opt_pass
+{
+public:
+ pass_complete_unrolli (gcc::context *ctxt)
+ : gimple_opt_pass (pass_data_complete_unrolli, ctxt)
+ {}
+
+ /* opt_pass methods: */
+ bool gate () { return gate_tree_complete_unroll_inner (); }
+ unsigned int execute () { return tree_complete_unroll_inner (); }
+
+}; // class pass_complete_unrolli
+
+} // anon namespace
+
+gimple_opt_pass *
+make_pass_complete_unrolli (gcc::context *ctxt)
+{
+ return new pass_complete_unrolli (ctxt);
+}
+
+