/* Induction variable canonicalization and loop peeling.
- Copyright (C) 2004-2017 Free Software Foundation, Inc.
+ Copyright (C) 2004-2020 Free Software Foundation, Inc.
This file is part of GCC.
#include "cfgloop.h"
#include "tree-chrec.h"
#include "tree-scalar-evolution.h"
-#include "params.h"
#include "tree-inline.h"
#include "tree-cfgcleanup.h"
#include "builtins.h"
+#include "tree-ssa-sccvn.h"
+#include "dbgcnt.h"
/* Specifies types of loops that may be unrolled. */
if they are not NULL. */
void
-create_canonical_iv (struct loop *loop, edge exit, tree niter,
+create_canonical_iv (class loop *loop, edge exit, tree niter,
tree *var_before = NULL, tree *var_after = NULL)
{
edge in;
/* Return true if OP in STMT will be constant after peeling LOOP. */
static bool
-constant_after_peeling (tree op, gimple *stmt, struct loop *loop)
+constant_after_peeling (tree op, gimple *stmt, class loop *loop)
{
- if (is_gimple_min_invariant (op))
+ if (CONSTANT_CLASS_P (op))
return true;
/* We can still fold accesses to constant arrays when index is known. */
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,
+tree_estimate_loop_size (class loop *loop, edge exit, edge edge_to_cancel,
struct loop_size *size, int upper_bound)
{
basic_block *body = get_loop_body (loop);
stmt, loop)
&& (gimple_assign_rhs_class (stmt) != GIMPLE_BINARY_RHS
|| constant_after_peeling (gimple_assign_rhs2 (stmt),
- stmt, loop)))
+ stmt, loop))
+ && gimple_assign_rhs_class (stmt) != GIMPLE_TERNARY_RHS)
{
size->constant_iv = true;
if (dump_file && (dump_flags & TDF_DETAILS))
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)))
+ || !constant_after_peeling (gimple_cond_rhs (stmt), stmt,
+ loop)))
|| (gimple_code (stmt) == GIMPLE_SWITCH
&& !constant_after_peeling (gimple_switch_index (
as_a <gswitch *> (stmt)),
The other cases are hopefully rare and will be cleaned up later. */
static edge
-loop_edge_to_cancel (struct loop *loop)
+loop_edge_to_cancel (class loop *loop)
{
vec<edge> exits;
unsigned i;
known to not be executed. */
static bool
-remove_exits_and_undefined_stmts (struct loop *loop, unsigned int npeeled)
+remove_exits_and_undefined_stmts (class loop *loop, unsigned int npeeled)
{
- struct nb_iter_bound *elt;
+ class nb_iter_bound *elt;
bool changed = false;
for (elt = loop->bounds; elt; elt = elt->next)
discovered. */
static bool
-remove_redundant_iv_tests (struct loop *loop)
+remove_redundant_iv_tests (class loop *loop)
{
- struct nb_iter_bound *elt;
+ class nb_iter_bound *elt;
bool changed = false;
if (!loop->any_upper_bound)
{
basic_block bb = gimple_bb (elt->stmt);
edge exit_edge = EDGE_SUCC (bb, 0);
- struct tree_niter_desc niter;
+ class tree_niter_desc niter;
if (!loop_exit_edge_p (loop, exit_edge))
exit_edge = EDGE_SUCC (bb, 1);
{
while (loops_to_unloop.length ())
{
- struct loop *loop = loops_to_unloop.pop ();
+ class 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);
loops_to_unloop.release ();
loops_to_unloop_nunroll.release ();
- /* Remove edges in peeled copies. */
+ /* Remove edges in peeled copies. Given remove_path removes dominated
+ regions we need to cope with removal of already removed paths. */
unsigned i;
edge e;
+ auto_vec<int, 20> src_bbs;
+ src_bbs.reserve_exact (edges_to_remove.length ());
FOR_EACH_VEC_ELT (edges_to_remove, i, e)
- {
- bool ok = remove_path (e, irred_invalidated, loop_closed_ssa_invalidated);
- gcc_assert (ok);
- }
+ src_bbs.quick_push (e->src->index);
+ FOR_EACH_VEC_ELT (edges_to_remove, i, e)
+ if (BASIC_BLOCK_FOR_FN (cfun, src_bbs[i]))
+ {
+ bool ok = remove_path (e, irred_invalidated,
+ loop_closed_ssa_invalidated);
+ gcc_assert (ok);
+ }
edges_to_remove.release ();
}
a summary of the unroll to the dump file. */
static bool
-try_unroll_loop_completely (struct loop *loop,
+try_unroll_loop_completely (class loop *loop,
edge exit, tree niter, bool may_be_zero,
enum unroll_level ul,
HOST_WIDE_INT maxiter,
- location_t locus, bool allow_peel)
+ dump_user_location_t locus, bool allow_peel)
{
unsigned HOST_WIDE_INT n_unroll = 0;
bool n_unroll_found = false;
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
+ /* We do not know the number of iterations and thus we cannot eliminate
the EXIT edge. */
else
exit = NULL;
{
n_unroll = maxiter;
n_unroll_found = true;
- /* Loop terminates before the IV variable test, so we can not
+ /* Loop terminates before the IV variable test, so we cannot
remove it in the last iteration. */
edge_to_cancel = NULL;
}
return false;
if (!loop->unroll
- && n_unroll > (unsigned) PARAM_VALUE (PARAM_MAX_COMPLETELY_PEEL_TIMES))
+ && n_unroll > (unsigned) param_max_completely_peel_times)
{
if (dump_file && (dump_flags & TDF_DETAILS))
fprintf (dump_file, "Not unrolling loop %d "
bool large
= tree_estimate_loop_size
(loop, remove_exit ? exit : NULL, edge_to_cancel, &size,
- PARAM_VALUE (PARAM_MAX_COMPLETELY_PEELED_INSNS));
+ param_max_completely_peeled_insns);
if (large)
{
if (dump_file && (dump_flags & TDF_DETAILS))
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))
+ > param_max_peel_branches)
{
if (dump_file && (dump_flags & TDF_DETAILS))
fprintf (dump_file, "Not unrolling loop %d: "
return false;
}
else if (unr_insns
- > (unsigned) PARAM_VALUE (PARAM_MAX_COMPLETELY_PEELED_INSNS))
+ > (unsigned) param_max_completely_peeled_insns)
{
if (dump_file && (dump_flags & TDF_DETAILS))
fprintf (dump_file, "Not unrolling loop %d: "
}
}
+ if (!dbg_cnt (gimple_unroll))
+ return false;
+
initialize_original_copy_tables ();
auto_sbitmap wont_exit (n_unroll + 1);
if (exit && niter
Parameters are the same as for try_unroll_loops_completely */
static bool
-try_peel_loop (struct loop *loop,
+try_peel_loop (class loop *loop,
edge exit, tree niter, bool may_be_zero,
HOST_WIDE_INT maxiter)
{
int peeled_size;
if (!flag_peel_loops
- || PARAM_VALUE (PARAM_MAX_PEEL_TIMES) <= 0
+ || param_max_peel_times <= 0
|| !peeled_loops)
return false;
/* We want to peel estimated number of iterations + 1 (so we never
enter the loop on quick path). Check against PARAM_MAX_PEEL_TIMES
and be sure to avoid overflows. */
- if (npeel > PARAM_VALUE (PARAM_MAX_PEEL_TIMES) - 1)
+ if (npeel > param_max_peel_times - 1)
{
if (dump_file)
fprintf (dump_file, "Not peeling: rolls too much "
/* Check peeled loops size. */
tree_estimate_loop_size (loop, exit, NULL, &size,
- PARAM_VALUE (PARAM_MAX_PEELED_INSNS));
+ param_max_peeled_insns);
if ((peeled_size = estimated_peeled_sequence_size (&size, (int) npeel))
- > PARAM_VALUE (PARAM_MAX_PEELED_INSNS))
+ > param_max_peeled_insns)
{
if (dump_file)
fprintf (dump_file, "Not peeling: peeled sequence size is too large "
return false;
}
+ if (!dbg_cnt (gimple_unroll))
+ return false;
+
/* Duplicate possibly eliminating the exits. */
initialize_original_copy_tables ();
auto_sbitmap wont_exit (npeel + 1);
if (e->src != loop->latch)
{
if (e->src->count.initialized_p ())
- entry_count = e->src->count + e->src->count;
+ entry_count += e->src->count;
gcc_assert (!flow_bb_inside_loop_p (loop, e->src));
}
- profile_probability p = profile_probability::very_unlikely ();
+ profile_probability p;
p = entry_count.probability_in (loop->header->count);
scale_loop_profile (loop, p, 0);
bitmap_set_bit (peeled_loops, loop->num);
Returns true if cfg is changed. */
static bool
-canonicalize_loop_induction_variables (struct loop *loop,
+canonicalize_loop_induction_variables (class loop *loop,
bool create_iv, enum unroll_level ul,
bool try_eval, bool allow_peel)
{
tree niter;
HOST_WIDE_INT maxiter;
bool modified = false;
- location_t locus = UNKNOWN_LOCATION;
- struct tree_niter_desc niter_desc;
+ dump_user_location_t locus;
+ class tree_niter_desc niter_desc;
bool may_be_zero = false;
/* For unrolling allow conditional constant or zero iterations, thus
= niter_desc.may_be_zero && !integer_zerop (niter_desc.may_be_zero);
}
if (TREE_CODE (niter) == INTEGER_CST)
- locus = gimple_location (last_stmt (exit->src));
+ locus = last_stmt (exit->src);
else
{
/* For non-constant niter fold may_be_zero into niter again. */
niter = find_loop_niter_by_eval (loop, &exit);
if (exit)
- locus = gimple_location (last_stmt (exit->src));
+ locus = last_stmt (exit->src);
if (TREE_CODE (niter) != INTEGER_CST)
exit = NULL;
by find_loop_niter_by_eval. Be sure to keep it for future. */
if (niter && TREE_CODE (niter) == INTEGER_CST)
{
+ vec<edge> exits = get_loop_exit_edges (loop);
record_niter_bound (loop, wi::to_widest (niter),
- exit == single_likely_exit (loop), true);
+ exit == single_likely_exit (loop, exits), true);
+ exits.release ();
}
/* Force re-computation of loop bounds so we can remove redundant exits. */
unsigned int
canonicalize_induction_variables (void)
{
- struct loop *loop;
+ class loop *loop;
bool changed = false;
bool irred_invalidated = false;
bitmap loop_closed_ssa_invalidated = BITMAP_ALLOC (NULL);
return 0;
}
-/* Propagate constant SSA_NAMEs defined in basic block BB. */
-
-static void
-propagate_constants_for_unrolling (basic_block bb)
-{
- /* Look for degenerate PHI nodes with constant argument. */
- for (gphi_iterator gsi = gsi_start_phis (bb); !gsi_end_p (gsi); )
- {
- gphi *phi = gsi.phi ();
- tree result = gimple_phi_result (phi);
- tree arg = gimple_phi_arg_def (phi, 0);
-
- if (! SSA_NAME_OCCURS_IN_ABNORMAL_PHI (result)
- && gimple_phi_num_args (phi) == 1
- && CONSTANT_CLASS_P (arg))
- {
- replace_uses_by (result, arg);
- gsi_remove (&gsi, true);
- release_ssa_name (result);
- }
- else
- gsi_next (&gsi);
- }
-
- /* Look for assignments to SSA names with constant RHS. */
- for (gimple_stmt_iterator gsi = gsi_start_bb (bb); !gsi_end_p (gsi); )
- {
- gimple *stmt = gsi_stmt (gsi);
- tree lhs;
-
- if (is_gimple_assign (stmt)
- && TREE_CODE_CLASS (gimple_assign_rhs_code (stmt)) == tcc_constant
- && (lhs = gimple_assign_lhs (stmt), TREE_CODE (lhs) == SSA_NAME)
- && !SSA_NAME_OCCURS_IN_ABNORMAL_PHI (lhs))
- {
- replace_uses_by (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,
- bitmap father_bbs, struct loop *loop)
+ bitmap father_bbs, class loop *loop)
{
- struct loop *loop_father;
+ class loop *loop_father;
bool changed = false;
- struct loop *inner;
+ class loop *inner;
enum unroll_level ul;
+ unsigned num = number_of_loops (cfun);
- /* Process inner loops first. */
+ /* Process inner loops first. Don't walk loops added by the recursive
+ calls because SSA form is not up-to-date. They can be handled in the
+ next iteration. */
+ bitmap child_father_bbs = NULL;
for (inner = loop->inner; inner != NULL; inner = inner->next)
- changed |= tree_unroll_loops_completely_1 (may_increase_size,
- unroll_outer, father_bbs,
- inner);
-
+ if ((unsigned) inner->num < num)
+ {
+ if (!child_father_bbs)
+ child_father_bbs = BITMAP_ALLOC (NULL);
+ if (tree_unroll_loops_completely_1 (may_increase_size, unroll_outer,
+ child_father_bbs, inner))
+ {
+ bitmap_ior_into (father_bbs, child_father_bbs);
+ bitmap_clear (child_father_bbs);
+ changed = true;
+ }
+ }
+ if (child_father_bbs)
+ BITMAP_FREE (child_father_bbs);
+
/* 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;
+ {
+ /* If we are recorded as father clear all other fathers that
+ are necessarily covered already to avoid redundant work. */
+ if (bitmap_bit_p (father_bbs, loop->header->index))
+ {
+ bitmap_clear (father_bbs);
+ bitmap_set_bit (father_bbs, loop->header->index);
+ }
+ return true;
+ }
/* Don't unroll #pragma omp simd loops until the vectorizer
attempts to vectorize those. */
computations; otherwise, the size might blow up before the
iteration is complete and the IR eventually cleaned up. */
if (loop_outer (loop_father))
- bitmap_set_bit (father_bbs, loop_father->header->index);
+ {
+ /* Once we process our father we will have processed
+ the fathers of our children as well, so avoid doing
+ redundant work and clear fathers we've gathered sofar. */
+ bitmap_clear (father_bbs);
+ bitmap_set_bit (father_bbs, loop_father->header->index);
+ }
return true;
}
unloop_loops (loop_closed_ssa_invalidated, &irred_invalidated);
- /* We can not use TODO_update_ssa_no_phi because VOPS gets confused. */
+ /* We cannot 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,
EXECUTE_IF_SET_IN_BITMAP (fathers, 0, i, bi)
{
loop_p father = get_loop (cfun, i);
- basic_block *body = get_loop_body_in_dom_order (father);
- for (unsigned j = 0; j < father->num_nodes; j++)
- propagate_constants_for_unrolling (body[j]);
- free (body);
+ bitmap exit_bbs = BITMAP_ALLOC (NULL);
+ loop_exit *exit = father->exits->next;
+ while (exit->e)
+ {
+ bitmap_set_bit (exit_bbs, exit->e->dest->index);
+ exit = exit->next;
+ }
+ do_rpo_vn (cfun, loop_preheader_edge (father), exit_bbs);
}
BITMAP_FREE (fathers);
BITMAP_FREE (loop_closed_ssa_invalidated);
}
while (changed
- && ++iteration <= PARAM_VALUE (PARAM_MAX_UNROLL_ITERATIONS));
+ && ++iteration <= param_max_unroll_iterations);
BITMAP_FREE (father_bbs);