On Wed, 31 Oct 2012, Jan Hubicka wrote:
> 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.
> */
> -
Needs a comment.
> 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),
I'm not sure we should do different things for -Og here. In fact there
is no unrolling done for -Og at all, so just use 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)
I think we can have abnormal/eh exit edges. So I'm not sure you
can, without checking, assume the block ends in a GIMPLE_COND.
> + 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);
See above. Otherwise the overall idea sounds fine.
Richard.
> + 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" } } */
>
>
--
Richard Biener <rguent...@suse.de>
SUSE / SUSE Labs
SUSE LINUX Products GmbH - Nuernberg - AG Nuernberg - HRB 16746
GF: Jeff Hawn, Jennifer Guild, Felix Imend
