Hi,
this patch fixes off-by-one error in the testcase attached. The problem is that
dominance based test used by record_estimate to check whether the given
statement
must be executed at last iteration of the loop is wrong ignoring the side effect
of other statements that may terminate the program.
It also does not work for mulitple exits as excercised by cunroll-2.c testcase.
This patch makes simple approach of computing set of all statements that must
by executed last iteration first time record_estimate is executed this way.
The set is computed conservatively walking header BB and its signle successors
(possibly diving into nested loop) stopping on first BB with multiple exits.
Better result can be computed by
1) estimating what loops are known to be finite
2) inserting fake edges for all infinite loop and all statements with side
effect
that may terminate the execution
3) using the post dominance info.
But that seems too expensive for something that is executed several times per
function compilation. In fact I am thinking about making recrod-estimate to
happen
at ivcanon time only and then making the loop_max_iterations and
loop_estimated_iterations
to simply return the bound instead of trying to recompute it all the time.
Still I do not see us to care about very precise bound for loops having complex
control flow since we do not really want to completely unroll them and elsewhere
the off-by-one error in conservative direction for iteration estimate is not big
deal.
Bootstrapped/regtested x86_64-linux, seems sane?
Honza
PR middle-end/54937
* tree-ssa-loop-niter.c (compute_stmts_executed_last_iteration): New
function.
(record_estimate): Use it; remove confused dominance test.
(estimate_numbers_of_iterations_loop): Free
stmts_executed_last_iteration.
* gcc.c-torture/execute/pr54937.c: Ne wtestcase.
* testsuite/gcc.dg/tree-ssa/cunroll-2.c: Tighten.
Index: tree-ssa-loop-niter.c
===================================================================
*** tree-ssa-loop-niter.c (revision 192537)
--- tree-ssa-loop-niter.c (working copy)
*************** record_niter_bound (struct loop *loop, d
*** 2523,2528 ****
--- 2523,2580 ----
loop->nb_iterations_estimate = loop->nb_iterations_upper_bound;
}
+ /* Compute pointer set of statements in currently analyzed loop that are known
+ to be executed at last iteration and store it into AUX.
+ We do very simple job of recording statements in the superblock
+ starsting in loop header until reaching first statement with side effect.
+
+ We can compute post-dominance after inserting fake edges to CFG
+ for all statements possibly terminating CFG and for all possibly
+ infinite subloops, but we really care about precise estimates
+ of simple loops with little control flow in it. */
+ static void
+ compute_stmts_executed_last_iteration (struct loop *loop)
+ {
+ basic_block bb = loop->header;
+ pointer_set_t *visited = NULL;
+ gimple_stmt_iterator gsi;
+ pointer_set_t *stmts_executed_last_iteration;
+
+ loop->aux = stmts_executed_last_iteration = pointer_set_create ();
+ while (true)
+ {
+ for (gsi = gsi_start_bb (loop->header); !gsi_end_p (gsi); gsi_next
(&gsi))
+ {
+ if (gimple_has_side_effects (gsi_stmt (gsi)))
+ {
+ if (visited)
+ pointer_set_destroy (visited);
+ return;
+ }
+ pointer_set_insert (stmts_executed_last_iteration, gsi_stmt (gsi));
+ }
+ if (single_succ_p (bb))
+ {
+ /* Deal with the rare case that there is an infintie loop inside the
+ loop examined. */
+ if (!visited)
+ {
+ visited = pointer_set_create ();
+ pointer_set_insert (visited, bb);
+ }
+ bb = single_succ_edge (bb)->dest;
+ if (pointer_set_insert (visited, bb))
+ break;
+ }
+ else
+ break;
+ }
+ if (visited)
+ pointer_set_destroy (visited);
+ return;
+ }
+
+
/* Records that AT_STMT is executed at most BOUND + 1 times in LOOP. IS_EXIT
is true if the loop is exited immediately after STMT, and this exit
is taken at last when the STMT is executed BOUND + 1 times.
*************** record_estimate (struct loop *loop, tree
*** 2535,2541 ****
gimple at_stmt, bool is_exit, bool realistic, bool upper)
{
double_int delta;
- edge exit;
if (dump_file && (dump_flags & TDF_DETAILS))
{
--- 2587,2592 ----
*************** record_estimate (struct loop *loop, tree
*** 2573,2586 ****
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))))
delta = double_int_zero;
else
! delta = double_int_one;
i_bound += delta;
/* If an overflow occurred, ignore the result. */
--- 2624,2641 ----
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. */
! if (is_exit)
delta = double_int_zero;
else
! {
! if (!loop->aux)
! compute_stmts_executed_last_iteration (loop);
! if (pointer_set_contains ((pointer_set_t *)loop->aux,
! at_stmt))
! delta = double_int_zero;
! else
! delta = double_int_one;
! }
i_bound += delta;
/* If an overflow occurred, ignore the result. */
*************** estimate_numbers_of_iterations_loop (str
*** 2971,2976 ****
--- 3026,3033 ----
if (loop->estimate_state != EST_NOT_COMPUTED)
return;
+ gcc_assert (!loop->aux);
+
loop->estimate_state = EST_AVAILABLE;
/* Force estimate compuation but leave any existing upper bound in place.
*/
loop->any_estimate = false;
*************** estimate_numbers_of_iterations_loop (str
*** 3004,3009 ****
--- 3061,3071 ----
bound = gcov_type_to_double_int (nit);
record_niter_bound (loop, bound, true, false);
}
+ if (loop->aux)
+ {
+ pointer_set_destroy ((pointer_set_t *)loop->aux);
+ loop->aux = NULL;
+ }
}
/* Sets NIT to the estimated number of executions of the latch of the
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 192608)
+++ 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" } } */
