Re: [PATCH 3/3] tree-optimization/114052 - niter analysis from undefined behavior
On Mon, 8 Apr 2024, Richard Biener wrote: > On Fri, 5 Apr 2024, Jan Hubicka wrote: > > > > + /* When there's a call that might not return the last iteration > > > + is possibly partial. This matches what we check in invariant > > > + motion. > > > + ??? For the call argument evaluation it would be still OK. */ > > > + if (!may_have_exited > > > + && is_gimple_call (stmt) > > > + && gimple_has_side_effects (stmt)) > > > + may_have_exited = true; > > > > I think you are missing here non-call EH, volatile asms and traps. > > We have stmt_may_terminate_function_p which tests there. > > That returns true for all variable array accesses, I think we want > to catch traps explicitly here. I'm going to do > > if (!may_have_exited > && (gimple_has_side_effects (stmt) > || stmt_can_throw_external (cfun, stmt))) > may_have_exited = true; > > that should cover all but the generic trapping and not use IPA info > to prove no side-effects. Hum. Maybe I'm a bit confused but we seem to "properly" take things into account via maybe_lower_iteration_bound and are not directly using the recorded bounds? The function does a DFS walk though, not reliably finding exits via calls early enough (it also lacks external EH). Oddly enough it seems to handle(?) gcc.dg/tree-ssa/cunroll-9.c "correctly", but not gcc.dg/tree-ssa/cunroll-10.c which has the number of iterations wrongly computed. Maybe we should really record all the bounds properly but merge them to a loop upper bound at one place? gcc.dg/tree-ssa/cunroll-11.c needs to see the g_x[i] bound is enforced in all paths to the latch for example. I'm most definitely defering this to GCC 15 now, I wonder if you have any preferences here (and maybe want to pick this up also for cleanup - it's mostly your code). Richard. > Richard. > > > Honza > > > + > > > + infer_loop_bounds_from_array (loop, stmt, > > > + reliable && !may_have_exited); > > > > > > - if (reliable) > > > + if (reliable && !may_have_exited) > > > { > > >infer_loop_bounds_from_signedness (loop, stmt); > > >infer_loop_bounds_from_pointer_arith (loop, stmt); > > > } > > > } > > > - > > > } > > > } > > > > > > @@ -4832,7 +4855,7 @@ estimate_numbers_of_iterations (class loop *loop) > > > diagnose those loops with -Waggressive-loop-optimizations. */ > > >number_of_latch_executions (loop); > > > > > > - basic_block *body = get_loop_body (loop); > > > + basic_block *body = get_loop_body_in_rpo (cfun, loop); > > >auto_vec exits = get_loop_exit_edges (loop, body); > > >likely_exit = single_likely_exit (loop, exits); > > >FOR_EACH_VEC_ELT (exits, i, ex) > > > -- > > > 2.35.3 > > > > -- Richard Biener SUSE Software Solutions Germany GmbH, Frankenstrasse 146, 90461 Nuernberg, Germany; GF: Ivo Totev, Andrew McDonald, Werner Knoblich; (HRB 36809, AG Nuernberg)
Re: [PATCH 3/3] tree-optimization/114052 - niter analysis from undefined behavior
On Fri, 5 Apr 2024, Jan Hubicka wrote: > > + /* When there's a call that might not return the last iteration > > +is possibly partial. This matches what we check in invariant > > +motion. > > +??? For the call argument evaluation it would be still OK. */ > > + if (!may_have_exited > > + && is_gimple_call (stmt) > > + && gimple_has_side_effects (stmt)) > > + may_have_exited = true; > > I think you are missing here non-call EH, volatile asms and traps. > We have stmt_may_terminate_function_p which tests there. That returns true for all variable array accesses, I think we want to catch traps explicitly here. I'm going to do if (!may_have_exited && (gimple_has_side_effects (stmt) || stmt_can_throw_external (cfun, stmt))) may_have_exited = true; that should cover all but the generic trapping and not use IPA info to prove no side-effects. Richard. > Honza > > + > > + infer_loop_bounds_from_array (loop, stmt, > > + reliable && !may_have_exited); > > > > - if (reliable) > > + if (reliable && !may_have_exited) > > { > >infer_loop_bounds_from_signedness (loop, stmt); > >infer_loop_bounds_from_pointer_arith (loop, stmt); > > } > > } > > - > > } > > } > > > > @@ -4832,7 +4855,7 @@ estimate_numbers_of_iterations (class loop *loop) > > diagnose those loops with -Waggressive-loop-optimizations. */ > >number_of_latch_executions (loop); > > > > - basic_block *body = get_loop_body (loop); > > + basic_block *body = get_loop_body_in_rpo (cfun, loop); > >auto_vec exits = get_loop_exit_edges (loop, body); > >likely_exit = single_likely_exit (loop, exits); > >FOR_EACH_VEC_ELT (exits, i, ex) > > -- > > 2.35.3 > -- Richard Biener SUSE Software Solutions Germany GmbH, Frankenstrasse 146, 90461 Nuernberg, Germany; GF: Ivo Totev, Andrew McDonald, Werner Knoblich; (HRB 36809, AG Nuernberg)
Re: [PATCH 3/3] tree-optimization/114052 - niter analysis from undefined behavior
> + /* When there's a call that might not return the last iteration > + is possibly partial. This matches what we check in invariant > + motion. > + ??? For the call argument evaluation it would be still OK. */ > + if (!may_have_exited > + && is_gimple_call (stmt) > + && gimple_has_side_effects (stmt)) > + may_have_exited = true; I think you are missing here non-call EH, volatile asms and traps. We have stmt_may_terminate_function_p which tests there. Honza > + > + infer_loop_bounds_from_array (loop, stmt, > + reliable && !may_have_exited); > > - if (reliable) > + if (reliable && !may_have_exited) > { >infer_loop_bounds_from_signedness (loop, stmt); >infer_loop_bounds_from_pointer_arith (loop, stmt); > } > } > - > } > } > > @@ -4832,7 +4855,7 @@ estimate_numbers_of_iterations (class loop *loop) > diagnose those loops with -Waggressive-loop-optimizations. */ >number_of_latch_executions (loop); > > - basic_block *body = get_loop_body (loop); > + basic_block *body = get_loop_body_in_rpo (cfun, loop); >auto_vec exits = get_loop_exit_edges (loop, body); >likely_exit = single_likely_exit (loop, exits); >FOR_EACH_VEC_ELT (exits, i, ex) > -- > 2.35.3
Re: [PATCH 3/3] tree-optimization/114052 - niter analysis from undefined behavior
On Fri, 5 Apr 2024, Richard Biener wrote: > The following makes sure to only compute upper bounds for the number > of iterations of loops from undefined behavior invoked by stmts when > those are executed in each loop iteration, in particular also in the > last one. The latter cannot be guaranteed if there's possible > infinite loops or calls with side-effects possibly executed before > the stmt. Rather than adjusting the bound by one or using the bound as > estimate the following for now gives up. > > Bootstrapped on x86_64-unknown-linux-gnu, testing in progress. It FAILs FAIL: gcc.dg/pr53265.c at line 91 (test for warnings, line 90) FAIL: gcc.dg/pr53265.c at line 92 (test for warnings, line 90) for diagnostic purposes we'd need to treat the call as not terminating FAIL: gcc.dg/tree-ssa/cunroll-10.c scan-tree-dump-times cunroll "Forced statement unreachable" 2 FAIL: gcc.dg/tree-ssa/cunroll-11.c scan-tree-dump cunroll "Loop 1 iterates at most 3 times" FAIL: gcc.dg/tree-ssa/cunroll-9.c scan-tree-dump-times cunrolli "Removed pointless exit:" 1 FAIL: gcc.dg/tree-ssa/loop-38.c scan-tree-dump cunrolli "Loop 1 iterates at most 11 times" FAIL: gcc.dg/tree-ssa/pr68234.c scan-tree-dump vrp2 ">> 6" FAIL: c-c++-common/ubsan/unreachable-3.c -O0 scan-tree-dump optimized "__builtin___ubsan_handle_builtin_unreachable" ... FAIL: c-c++-common/ubsan/unreachable-3.c -Os scan-tree-dump optimized "__builtin___ubsan_handle_builtin_unreachable" > PR tree-optimization/114052 > * tree-ssa-loop-niter.cc (infer_loop_bounds_from_undefined): > When we enter a possibly infinite loop or when we come across > a call with side-effects record the last iteration might not > execute all stmts. Consider bounds as unreliable in that case. > > * gcc.dg/tree-ssa/pr114052-1.c: New testcase. > --- > gcc/testsuite/gcc.dg/tree-ssa/pr114052-1.c | 16 ++ > gcc/tree-ssa-loop-niter.cc | 35 ++ > 2 files changed, 45 insertions(+), 6 deletions(-) > create mode 100644 gcc/testsuite/gcc.dg/tree-ssa/pr114052-1.c > > diff --git a/gcc/testsuite/gcc.dg/tree-ssa/pr114052-1.c > b/gcc/testsuite/gcc.dg/tree-ssa/pr114052-1.c > new file mode 100644 > index 000..54a2181e67e > --- /dev/null > +++ b/gcc/testsuite/gcc.dg/tree-ssa/pr114052-1.c > @@ -0,0 +1,16 @@ > +/* { dg-do compile } */ > +/* { dg-options "-O2 -fdump-tree-optimized" } */ > + > +int foo(void) > +{ > + int counter = 0; > + while (1) > +{ > + if (counter >= 2) > + continue; > + __builtin_printf("%i\n", counter++); > +} > + return 0; > +} > + > +/* { dg-final { scan-tree-dump-not "unreachable" "optimized" } } */ > diff --git a/gcc/tree-ssa-loop-niter.cc b/gcc/tree-ssa-loop-niter.cc > index 0a77c1bb544..52a39eb3500 100644 > --- a/gcc/tree-ssa-loop-niter.cc > +++ b/gcc/tree-ssa-loop-niter.cc > @@ -4397,7 +4397,7 @@ infer_loop_bounds_from_undefined (class loop *loop, > basic_block *bbs) >unsigned i; >gimple_stmt_iterator bsi; >basic_block bb; > - bool reliable; > + bool may_have_exited = false; > >for (i = 0; i < loop->num_nodes; i++) > { > @@ -4407,21 +4407,44 @@ infer_loop_bounds_from_undefined (class loop *loop, > basic_block *bbs) >use the operations in it to infer reliable upper bound on the ># of iterations of the loop. However, we can use it as a guess. >Reliable guesses come only from array bounds. */ > - reliable = dominated_by_p (CDI_DOMINATORS, loop->latch, bb); > + bool reliable = dominated_by_p (CDI_DOMINATORS, loop->latch, bb); > + > + /* A possibly infinite inner loop makes further blocks not always > + executed. Key on the entry of such a loop as that avoids RPO > + issues with where the exits of that loop are. Any block > + inside an irreducible sub-region is problematic as well. > + ??? Note this technically only makes the last iteration > + possibly partially executed. */ > + if (!may_have_exited > + && bb != loop->header > + && (!loops_state_satisfies_p (LOOPS_HAVE_MARKED_IRREDUCIBLE_REGIONS) > + || bb->flags & BB_IRREDUCIBLE_LOOP > + || (bb->loop_father->header == bb > + && !finite_loop_p (bb->loop_father > + may_have_exited = true; > >for (bsi = gsi_start_bb (bb); !gsi_end_p (bsi); gsi_next ()) > { > gimple *stmt = gsi_stmt (bsi); > > - infer_loop_bounds_from_array (loop, stmt, reliable); > + /* When there's a call that might not return the last iteration > + is possibly partial. This matches what we check in invariant > + motion. > + ??? For the call argument evaluation it would be still OK. */ > + if (!may_have_exited > + && is_gimple_call (stmt) > + && gimple_has_side_effects (stmt)) > + may_have_exited = true; > + > +
[PATCH 3/3] tree-optimization/114052 - niter analysis from undefined behavior
The following makes sure to only compute upper bounds for the number of iterations of loops from undefined behavior invoked by stmts when those are executed in each loop iteration, in particular also in the last one. The latter cannot be guaranteed if there's possible infinite loops or calls with side-effects possibly executed before the stmt. Rather than adjusting the bound by one or using the bound as estimate the following for now gives up. Bootstrapped on x86_64-unknown-linux-gnu, testing in progress. PR tree-optimization/114052 * tree-ssa-loop-niter.cc (infer_loop_bounds_from_undefined): When we enter a possibly infinite loop or when we come across a call with side-effects record the last iteration might not execute all stmts. Consider bounds as unreliable in that case. * gcc.dg/tree-ssa/pr114052-1.c: New testcase. --- gcc/testsuite/gcc.dg/tree-ssa/pr114052-1.c | 16 ++ gcc/tree-ssa-loop-niter.cc | 35 ++ 2 files changed, 45 insertions(+), 6 deletions(-) create mode 100644 gcc/testsuite/gcc.dg/tree-ssa/pr114052-1.c diff --git a/gcc/testsuite/gcc.dg/tree-ssa/pr114052-1.c b/gcc/testsuite/gcc.dg/tree-ssa/pr114052-1.c new file mode 100644 index 000..54a2181e67e --- /dev/null +++ b/gcc/testsuite/gcc.dg/tree-ssa/pr114052-1.c @@ -0,0 +1,16 @@ +/* { dg-do compile } */ +/* { dg-options "-O2 -fdump-tree-optimized" } */ + +int foo(void) +{ + int counter = 0; + while (1) +{ + if (counter >= 2) + continue; + __builtin_printf("%i\n", counter++); +} + return 0; +} + +/* { dg-final { scan-tree-dump-not "unreachable" "optimized" } } */ diff --git a/gcc/tree-ssa-loop-niter.cc b/gcc/tree-ssa-loop-niter.cc index 0a77c1bb544..52a39eb3500 100644 --- a/gcc/tree-ssa-loop-niter.cc +++ b/gcc/tree-ssa-loop-niter.cc @@ -4397,7 +4397,7 @@ infer_loop_bounds_from_undefined (class loop *loop, basic_block *bbs) unsigned i; gimple_stmt_iterator bsi; basic_block bb; - bool reliable; + bool may_have_exited = false; for (i = 0; i < loop->num_nodes; i++) { @@ -4407,21 +4407,44 @@ infer_loop_bounds_from_undefined (class loop *loop, basic_block *bbs) use the operations in it to infer reliable upper bound on the # of iterations of the loop. However, we can use it as a guess. Reliable guesses come only from array bounds. */ - reliable = dominated_by_p (CDI_DOMINATORS, loop->latch, bb); + bool reliable = dominated_by_p (CDI_DOMINATORS, loop->latch, bb); + + /* A possibly infinite inner loop makes further blocks not always +executed. Key on the entry of such a loop as that avoids RPO +issues with where the exits of that loop are. Any block +inside an irreducible sub-region is problematic as well. +??? Note this technically only makes the last iteration +possibly partially executed. */ + if (!may_have_exited + && bb != loop->header + && (!loops_state_satisfies_p (LOOPS_HAVE_MARKED_IRREDUCIBLE_REGIONS) + || bb->flags & BB_IRREDUCIBLE_LOOP + || (bb->loop_father->header == bb + && !finite_loop_p (bb->loop_father + may_have_exited = true; for (bsi = gsi_start_bb (bb); !gsi_end_p (bsi); gsi_next ()) { gimple *stmt = gsi_stmt (bsi); - infer_loop_bounds_from_array (loop, stmt, reliable); + /* When there's a call that might not return the last iteration +is possibly partial. This matches what we check in invariant +motion. +??? For the call argument evaluation it would be still OK. */ + if (!may_have_exited + && is_gimple_call (stmt) + && gimple_has_side_effects (stmt)) + may_have_exited = true; + + infer_loop_bounds_from_array (loop, stmt, + reliable && !may_have_exited); - if (reliable) + if (reliable && !may_have_exited) { infer_loop_bounds_from_signedness (loop, stmt); infer_loop_bounds_from_pointer_arith (loop, stmt); } } - } } @@ -4832,7 +4855,7 @@ estimate_numbers_of_iterations (class loop *loop) diagnose those loops with -Waggressive-loop-optimizations. */ number_of_latch_executions (loop); - basic_block *body = get_loop_body (loop); + basic_block *body = get_loop_body_in_rpo (cfun, loop); auto_vec exits = get_loop_exit_edges (loop, body); likely_exit = single_likely_exit (loop, exits); FOR_EACH_VEC_ELT (exits, i, ex) -- 2.35.3