Message ID | 20121022152240.GA13310@kam.mff.cuni.cz |
---|---|
State | New |
Headers | show |
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" } } */ > >
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" } } */