Hi,
this patch implements the logic to remove statements that are known to be
undefined and thus expected to not be executed after unrolling. It also
removes redundant exits that I originally tried to do at once, but it
does not fly, since the peeling confuse number_of_iterations_exit
and it no longer understands the ivs.
So now we
1) always remove exits that are known to be redundant by the bounds found
2) try to peel/unroll
3) if success remove statemnts from the last iteration
This silence the array-bounds warnings in my testcase and many cases of
-O3 bootstrap (I am running it now).
Still if one construct testcase touching out of bound in more than one
iteration we will produce false warning, I will do that incrementally
by similar logic in loop copying.
Bootstrapped/regtested x86_64-linux, OK?
Honza
* tree-ssa-loop-niter.c (free_loop_bounds): Break out from ...
(free_numbers_of_iterations_estimates_loop): ... here.
* tree-ssa-loop-ivcanon.c (remove_exits_and_undefined_stmts): New
function.
(remove_redundant_iv_test): New function.
(try_unroll_loop_completely): Pass in MAXITER; use
remove_exits_and_undefined_stmts
(canonicalize_loop_induction_variables): Compute MAXITER;
use remove_redundant_iv_test.
* cfgloop.h (free_loop_bounds): New function.
* gcc.dg/tree-ssa/cunroll-10.c: New testcase.
* gcc.dg/tree-ssa/cunroll-9.c: New testcase.
Index: tree-ssa-loop-niter.c
===================================================================
--- tree-ssa-loop-niter.c (revision 192989)
@@ -3505,15 +3737,11 @@ scev_probably_wraps_p (tree base, tree s
return true;
}
-/* Frees the information on upper bounds on numbers of iterations of LOOP. */
-
void
-free_numbers_of_iterations_estimates_loop (struct loop *loop)
+free_loop_bounds (struct loop *loop)
{
struct nb_iter_bound *bound, *next;
- loop->nb_iterations = NULL;
- loop->estimate_state = EST_NOT_COMPUTED;
for (bound = loop->bounds; bound; bound = next)
{
next = bound->next;
@@ -3523,6 +3751,16 @@ free_numbers_of_iterations_estimates_loo
loop->bounds = NULL;
}
+/* Frees the information on upper bounds on numbers of iterations of LOOP. */
+
+void
+free_numbers_of_iterations_estimates_loop (struct loop *loop)
+{
+ loop->nb_iterations = NULL;
+ loop->estimate_state = EST_NOT_COMPUTED;
+ free_loop_bounds (loop);
+}
+
/* Frees the information on upper bounds on numbers of iterations of loops. */
void
Index: tree-ssa-loop-ivcanon.c
===================================================================
--- tree-ssa-loop-ivcanon.c (revision 192989)
+++ tree-ssa-loop-ivcanon.c (working copy)
@@ -389,6 +389,116 @@ loop_edge_to_cancel (struct loop *loop)
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.ule (double_int::from_uhwi (npeeled)))
+ {
+ gimple_stmt_iterator gsi = gsi_for_stmt (elt->stmt);
+ gimple stmt = gimple_build_call
+ (builtin_decl_implicit (optimize_debug
+ ? BUILT_IN_TRAP : 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);
+ 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_test (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))
+ gcc_unreachable ();
+ if (!integer_onep (niter.assumptions)
+ || !integer_zerop (niter.may_be_zero)
+ || !niter.niter
+ || TREE_CODE (niter.niter) != INTEGER_CST)
+ 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;
+}
+
/* 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.
@@ -396,20 +511,22 @@ loop_edge_to_cancel (struct loop *loop)
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. */
+ when we need to go into loop closed SSA form.
+ MAXITER specfy bound on number of iterations, -1 if it is
+ not known or too large for HOST_WIDE_INT. */
static bool
try_unroll_loop_completely (struct loop *loop,
edge exit, tree niter,
enum unroll_level ul,
bool *irred_invalidated,
- bitmap loop_closed_ssa_invalidated)
+ bitmap loop_closed_ssa_invalidated,
+ HOST_WIDE_INT maxiter)
{
unsigned HOST_WIDE_INT n_unroll, ninsns, max_unroll, unr_insns;
gimple cond;
struct loop_size size;
bool n_unroll_found = false;
- HOST_WIDE_INT maxiter;
basic_block latch;
edge latch_edge;
location_t locus;
@@ -445,7 +562,6 @@ try_unroll_loop_completely (struct loop
exit = NULL;
/* See if we can improve our estimate by using recorded loop bounds. */
- maxiter = max_loop_iterations_int (loop);
if (maxiter >= 0
&& (!n_unroll_found || (unsigned HOST_WIDE_INT)maxiter < n_unroll))
{
@@ -545,6 +661,8 @@ try_unroll_loop_completely (struct loop
free_original_copy_tables ();
}
+ remove_exits_and_undefined_stmts (loop, n_unroll);
+
/* Remove the conditional from the last copy of the loop. */
if (edge_to_cancel)
{
@@ -627,6 +745,8 @@ canonicalize_loop_induction_variables (s
{
edge exit = NULL;
tree niter;
+ HOST_WIDE_INT maxiter;
+ bool modified = false;
niter = number_of_latch_executions (loop);
if (TREE_CODE (niter) == INTEGER_CST)
@@ -657,6 +777,8 @@ canonicalize_loop_induction_variables (s
if (niter && TREE_CODE (niter) == INTEGER_CST)
record_niter_bound (loop, tree_to_double_int (niter), false, true);
+ maxiter = max_loop_iterations_int (loop);
+
if (dump_file && (dump_flags & TDF_DETAILS)
&& TREE_CODE (niter) == INTEGER_CST)
{
@@ -665,21 +787,28 @@ canonicalize_loop_induction_variables (s
fprintf (dump_file, " times.\n");
}
if (dump_file && (dump_flags & TDF_DETAILS)
- && max_loop_iterations_int (loop) >= 0)
+ && maxiter >= 0)
{
fprintf (dump_file, "Loop %d iterates at most %i times.\n", loop->num,
- (int)max_loop_iterations_int (loop));
+ (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_test (loop);
+
if (try_unroll_loop_completely (loop, exit, niter, ul, irred_invalidated,
- loop_closed_ssa_invalidated))
+ loop_closed_ssa_invalidated, maxiter))
return true;
if (create_iv
&& niter && !chrec_contains_undetermined (niter))
create_canonical_iv (loop, exit, niter);
- return false;
+ if (modified)
+ free_loop_bounds (loop);
+ return modified;
}
/* The main entry point of the pass. Adds canonical induction variables
Index: cfgloop.h
===================================================================
--- cfgloop.h (revision 192989)
+++ cfgloop.h (working copy)
@@ -286,6 +286,7 @@ extern unsigned expected_loop_iterations
extern rtx doloop_condition_get (rtx);
void estimate_numbers_of_iterations_loop (struct loop *);
+void free_loop_bounds (struct loop *);
void record_niter_bound (struct loop *, double_int, bool, bool);
bool estimated_loop_iterations (struct loop *, double_int *);
bool max_loop_iterations (struct loop *, double_int *);
Index: testsuite/gcc.dg/tree-ssa/cunroll-10.c
===================================================================
--- testsuite/gcc.dg/tree-ssa/cunroll-10.c (revision 0)
+++ testsuite/gcc.dg/tree-ssa/cunroll-10.c (revision 0)
@@ -0,0 +1,13 @@
+/* { dg-do compile } */
+/* { dg-options "-O3 -Warray-bounds -fdump-tree-cunroll" } */
+int a[3];
+int b[4];
+main()
+{
+ int i;
+ for (i=0;i<4;i++)
+ if (b[i]==2)
+ a[i]++;
+}
+/* { dg-final { scan-tree-dump-times 2 "Forced statement unreachable:"
"cunroll" } } */
+/* { dg-final { cleanup-tree-dump "cunroll" } } */
Index: testsuite/gcc.dg/tree-ssa/cunroll-9.c
===================================================================
--- testsuite/gcc.dg/tree-ssa/cunroll-9.c (revision 0)
+++ testsuite/gcc.dg/tree-ssa/cunroll-9.c (revision 0)
@@ -0,0 +1,21 @@
+/* { dg-do compile } */
+/* { dg-options "-O2 -fdump-tree-cunrolli" } */
+int a[10];
+int b[11];
+t (int n)
+{
+ int i;
+ int sum = 0;
+ for (i = 0; i < n; i++)
+ {
+ if (i > 1000)
+ abort ();
+ if (q ())
+ sum += a[i];
+ else
+ sum += b[i];
+ }
+ return sum;
+}
+/* { dg-final { scan-tree-dump-times 1 "Removed pointless exit:" "cunroli" } }
*/
+/* { dg-final { cleanup-tree-dump "cunroli" } } */
