On Mon, 22 Oct 2012, Jan Hubicka wrote:
> Hi,
> here is updated patch with the comments. The fortran failures turned out to
> be
> funny interaction in between this patch and my other change that hoped that
> loop closed SSA is closed on VOPs, but it is not.
>
> Regtested x86_64-linux, bootstrap in progress, OK?
Ok for trunk.
Thanks,
Richard.
> Honza
>
> * tree-ssa-loop-niter.c (record_estimate): Do not try to lower
> the bound of non-is_exit statements.
> (maybe_lower_iteration_bound): Do it here.
> (estimate_numbers_of_iterations_loop): Call it.
>
> * gcc.c-torture/execute/pr54937.c: New testcase.
> * gcc.dg/tree-ssa/cunroll-2.c: Update.
> Index: tree-ssa-loop-niter.c
> ===================================================================
> --- tree-ssa-loop-niter.c (revision 192632)
> +++ tree-ssa-loop-niter.c (working copy)
> @@ -2535,7 +2541,6 @@ record_estimate (struct loop *loop, tree
> gimple at_stmt, bool is_exit, bool realistic, bool upper)
> {
> double_int delta;
> - edge exit;
>
> if (dump_file && (dump_flags & TDF_DETAILS))
> {
> @@ -2570,14 +2577,10 @@ record_estimate (struct loop *loop, tree
> }
>
> /* Update the number of iteration estimates according to the bound.
> - If at_stmt is an exit or dominates the single exit from the loop,
> - then the loop latch is executed at most BOUND times, otherwise
> - it can be executed BOUND + 1 times. */
> - exit = single_exit (loop);
> - if (is_exit
> - || (exit != NULL
> - && dominated_by_p (CDI_DOMINATORS,
> - exit->src, gimple_bb (at_stmt))))
> + If at_stmt is an exit then the loop latch is executed at most BOUND
> times,
> + otherwise it can be executed BOUND + 1 times. We will lower the
> estimate
> + later if such statement must be executed on last iteration */
> + if (is_exit)
> delta = double_int_zero;
> else
> delta = double_int_one;
> @@ -2953,6 +2956,110 @@ gcov_type_to_double_int (gcov_type val)
> return ret;
> }
>
> +/* See if every path cross the loop goes through a statement that is known
> + to not execute at the last iteration. In that case we can decrese
> iteration
> + count by 1. */
> +
> +static void
> +maybe_lower_iteration_bound (struct loop *loop)
> +{
> + pointer_set_t *not_executed_last_iteration = pointer_set_create ();
> + struct nb_iter_bound *elt;
> + bool found_exit = false;
> + VEC (basic_block, heap) *queue = NULL;
> + bitmap visited;
> +
> + /* Collect all statements with interesting (i.e. lower than
> + nb_iterations_upper_bound) bound on them.
> +
> + TODO: Due to the way record_estimate choose estimates to store, the
> bounds
> + will be always nb_iterations_upper_bound-1. We can change this to
> record
> + also statements not dominating the loop latch and update the walk bellow
> + to the shortest path algorthm. */
> + for (elt = loop->bounds; elt; elt = elt->next)
> + {
> + if (!elt->is_exit
> + && elt->bound.ult (loop->nb_iterations_upper_bound))
> + {
> + if (!not_executed_last_iteration)
> + not_executed_last_iteration = pointer_set_create ();
> + pointer_set_insert (not_executed_last_iteration, elt->stmt);
> + }
> + }
> + if (!not_executed_last_iteration)
> + return;
> +
> + /* Start DFS walk in the loop header and see if we can reach the
> + loop latch or any of the exits (including statements with side
> + effects that may terminate the loop otherwise) without visiting
> + any of the statements known to have undefined effect on the last
> + iteration. */
> + VEC_safe_push (basic_block, heap, queue, loop->header);
> + visited = BITMAP_ALLOC (NULL);
> + bitmap_set_bit (visited, loop->header->index);
> + found_exit = false;
> +
> + do
> + {
> + basic_block bb = VEC_pop (basic_block, queue);
> + gimple_stmt_iterator gsi;
> + bool stmt_found = false;
> +
> + /* Loop for possible exits and statements bounding the execution. */
> + for (gsi = gsi_start_bb (bb); !gsi_end_p (gsi); gsi_next (&gsi))
> + {
> + gimple stmt = gsi_stmt (gsi);
> + if (pointer_set_contains (not_executed_last_iteration, stmt))
> + {
> + stmt_found = true;
> + break;
> + }
> + if (gimple_has_side_effects (stmt))
> + {
> + found_exit = true;
> + break;
> + }
> + }
> + if (found_exit)
> + break;
> +
> + /* If no bounding statement is found, continue the walk. */
> + if (!stmt_found)
> + {
> + edge e;
> + edge_iterator ei;
> +
> + FOR_EACH_EDGE (e, ei, bb->succs)
> + {
> + if (loop_exit_edge_p (loop, e)
> + || e == loop_latch_edge (loop))
> + {
> + found_exit = true;
> + break;
> + }
> + if (bitmap_set_bit (visited, e->dest->index))
> + VEC_safe_push (basic_block, heap, queue, e->dest);
> + }
> + }
> + }
> + while (VEC_length (basic_block, queue) && !found_exit);
> +
> + /* If every path through the loop reach bounding statement before exit,
> + then we know the last iteration of the loop will have undefined effect
> + and we can decrease number of iterations. */
> +
> + if (!found_exit)
> + {
> + if (dump_file && (dump_flags & TDF_DETAILS))
> + fprintf (dump_file, "Reducing loop iteration estimate by 1; "
> + "undefined statement must be executed at the last
> iteration.\n");
> + record_niter_bound (loop, loop->nb_iterations_upper_bound -
> double_int_one,
> + false, true);
> + }
> + BITMAP_FREE (visited);
> + VEC_free (basic_block, heap, queue);
> +}
> +
> /* Records estimates on numbers of iterations of LOOP. If USE_UNDEFINED_P
> is true also use estimates derived from undefined behavior. */
>
> @@ -2996,6 +3103,8 @@ estimate_numbers_of_iterations_loop (str
>
> infer_loop_bounds_from_undefined (loop);
>
> + maybe_lower_iteration_bound (loop);
> +
> /* If we have a measured profile, use it to estimate the number of
> iterations. */
> if (loop->header->count != 0)
> Index: testsuite/gcc.c-torture/execute/pr54937.c
> ===================================================================
> --- testsuite/gcc.c-torture/execute/pr54937.c (revision 0)
> +++ testsuite/gcc.c-torture/execute/pr54937.c (revision 0)
> @@ -0,0 +1,22 @@
> +
> +void exit (int);
> +void abort (void);
> +int a[1];
> +void (*terminate_me)(int);
> +
> +__attribute__((noinline,noclone))
> +t(int c)
> +{ int i;
> + for (i=0;i<c;i++)
> + {
> + if (i)
> + terminate_me(0);
> + a[i]=0;
> + }
> +}
> +main()
> +{
> + terminate_me = exit;
> + t(100);
> + abort();
> +}
> Index: testsuite/gcc.dg/tree-ssa/cunroll-2.c
> ===================================================================
> --- testsuite/gcc.dg/tree-ssa/cunroll-2.c (revision 192632)
> +++ testsuite/gcc.dg/tree-ssa/cunroll-2.c (working copy)
> @@ -12,5 +12,5 @@ test(int c)
> }
> }
> /* We are not able to get rid of the final conditional because the loop has
> two exits. */
> -/* { dg-final { scan-tree-dump "Unrolled loop 1 completely .duplicated 2
> times.." "cunroll"} } */
> +/* { dg-final { scan-tree-dump "Unrolled loop 1 completely .duplicated 1
> times.." "cunroll"} } */
> /* { dg-final { cleanup-tree-dump "cunroll" } } */
>
>
--
Richard Biener <[email protected]>
SUSE / SUSE Labs
SUSE LINUX Products GmbH - Nuernberg - AG Nuernberg - HRB 16746
GF: Jeff Hawn, Jennifer Guild, Felix Imend
