From 053223551fd7253097117744fcafccd28c8941c0 Mon Sep 17 00:00:00 2001 From: Jan Hubicka Date: Tue, 23 Oct 2012 12:00:19 +0200 Subject: [PATCH] re PR tree-optimization/54937 (Invalid loop bound estimate) PR middle-end/54937 * 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. From-SVN: r192710 --- gcc/ChangeLog | 8 ++ gcc/testsuite/ChangeLog | 6 ++ gcc/testsuite/gcc.c-torture/execute/pr54937.c | 22 +++++ gcc/testsuite/gcc.dg/tree-ssa/cunroll-2.c | 2 +- gcc/tree-ssa-loop-niter.c | 119 ++++++++++++++++++++++++-- 5 files changed, 147 insertions(+), 10 deletions(-) create mode 100644 gcc/testsuite/gcc.c-torture/execute/pr54937.c diff --git a/gcc/ChangeLog b/gcc/ChangeLog index d9c294e..815c5824 100644 --- a/gcc/ChangeLog +++ b/gcc/ChangeLog @@ -1,5 +1,13 @@ 2012-10-23 Jan Hubicka + PR middle-end/54937 + * 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. + +2012-10-23 Jan Hubicka + PR middle-end/54967 * cfgloopmanip.c (fix_bb_placements): Add loop_closed_ssa_invalidated; track basic blocks that moved out of their loops. diff --git a/gcc/testsuite/ChangeLog b/gcc/testsuite/ChangeLog index 7daf70e..7a6d258 100644 --- a/gcc/testsuite/ChangeLog +++ b/gcc/testsuite/ChangeLog @@ -1,5 +1,11 @@ 2012-10-23 Jan Hubicka + PR middle-end/54937 + * gcc.c-torture/execute/pr54937.c: New testcase. + * gcc.dg/tree-ssa/cunroll-2.c: Update. + +2012-10-23 Jan Hubicka + PR middle-end/54967 * gfortran.dg/pr54967.f90: New testcase. diff --git a/gcc/testsuite/gcc.c-torture/execute/pr54937.c b/gcc/testsuite/gcc.c-torture/execute/pr54937.c new file mode 100644 index 0000000..13dae60 --- /dev/null +++ b/gcc/testsuite/gcc.c-torture/execute/pr54937.c @@ -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;isrc, 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 +2948,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 +3095,8 @@ estimate_numbers_of_iterations_loop (struct loop *loop) 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) -- 2.7.4