Non-dominating loop bounds in tree-ssa-loop-niter 3/4
Jan Hubicka
hubicka@ucw.cz
Wed Oct 31 10:46:00 GMT 2012
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" } } */
More information about the Gcc-patches
mailing list