On Fri, 19 Oct 2012, Jan Hubicka wrote:
> 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.
would using post-dom info even work? That only says that _if_ the
dominated stmt executed then it came through the dominator. It
doesn't deal with functions that may not return.
> 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;
> ! }
What about the conservative variant of simply
else
delta = double_int_one;
? I don't like all the code you add, nor the use of ->aux.
> i_bound += delta;
Another alternative would be to not use i_bound for the
strong upper bound but only the estimate (thus conservatively
use i_bound + 1 for the upper bound if !is_exit).
Richard.
> /* 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" } } */
>
>
--
Richard Biener <rguent...@suse.de>
SUSE / SUSE Labs
SUSE LINUX Products GmbH - Nuernberg - AG Nuernberg - HRB 16746
GF: Jeff Hawn, Jennifer Guild, Felix Imend
