This is the mail archive of the
gcc-patches@gcc.gnu.org
mailing list for the GCC project.
Re: Fix array bound niter estimate (PR middle-end/54937)
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?
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" } } */