Hi,
I actually attached not completely final version of the patch. This one has
the extra loop looking for side effect that cures the first testcase.
Sorry for the confussion.
Honza
PR tree-optimize/55875
* gcc.c-torture/execute/pr55875.c: New testcase.
* g++.dg/torture/pr55875.C: New testcase.
* tree-ssa-loop-niter.c (n_of_executions_at_most): Simplify
to only test for cases where statement is dominated by the
particular bound; handle correctly the "postdominance"
test.
(scev_probably_wraps_p): Use max loop iterations info
as a global bound first.
Index: testsuite/gcc.c-torture/execute/pr55875.c
===================================================================
--- testsuite/gcc.c-torture/execute/pr55875.c (revision 0)
+++ testsuite/gcc.c-torture/execute/pr55875.c (revision 0)
@@ -0,0 +1,17 @@
+int a[250];
+__attribute__ ((noinline))
+t(int i)
+{
+ if (i==0)
+ exit(0);
+ if (i>255)
+ abort ();
+}
+main()
+{
+ unsigned int i;
+ for (i=0;;i++)
+ {
+ a[i]=t((unsigned char)(i+5));
+ }
+}
Index: testsuite/g++.dg/torture/pr55875.C
===================================================================
--- testsuite/g++.dg/torture/pr55875.C (revision 0)
+++ testsuite/g++.dg/torture/pr55875.C (revision 0)
@@ -0,0 +1,53 @@
+struct A
+{
+ short int a1;
+ unsigned char a2;
+ unsigned int a3;
+};
+
+struct B
+{
+ unsigned short b1;
+ const A *b2;
+};
+
+B b;
+
+__attribute__((noinline, noclone))
+int foo (unsigned x)
+{
+ __asm volatile ("" : "+r" (x) : : "memory");
+ return x;
+}
+
+inline void
+bar (const int &)
+{
+}
+
+__attribute__((noinline)) void
+baz ()
+{
+ const A *a = b.b2;
+ unsigned int i;
+ unsigned short n = b.b1;
+ for (i = 0; i < n; ++i)
+ if (a[i].a1 == 11)
+ {
+ if (i > 0 && (a[i - 1].a2 & 1))
+ continue;
+ bar (foo (2));
+ return;
+ }
+}
+
+int
+main ()
+{
+ A a[4] = { { 10, 0, 0 }, { 11, 1, 0 }, { 11, 1, 0 }, { 11, 1, 0 } };
+ b.b1 = 4;
+ b.b2 = a;
+ baz ();
+ return 0;
+}
+
Index: tree-ssa-loop-niter.c
===================================================================
--- tree-ssa-loop-niter.c (revision 194918)
+++ tree-ssa-loop-niter.c (working copy)
@@ -3549,8 +3549,15 @@ stmt_dominates_stmt_p (gimple s1, gimple
/* Returns true when we can prove that the number of executions of
STMT in the loop is at most NITER, according to the bound on
the number of executions of the statement NITER_BOUND->stmt recorded in
- NITER_BOUND. If STMT is NULL, we must prove this bound for all
- statements in the loop. */
+ NITER_BOUND and fact that NITER_BOUND->stmt dominate STMT.
+
+ ??? This code can become quite a CPU hog - we can have many bounds,
+ and large basic block forcing stmt_dominates_stmt_p to be queried
+ many times on a large basic blocks, so the whole thing is O(n^2)
+ for scev_probably_wraps_p invocation (that can be done n times).
+
+ It would make more sense (and give better answers) to remember BB
+ bounds computed by discover_iteration_bound_by_body_walk. */
static bool
n_of_executions_at_most (gimple stmt,
@@ -3571,32 +3578,43 @@ n_of_executions_at_most (gimple stmt,
/* We know that NITER_BOUND->stmt is executed at most NITER_BOUND->bound + 1
times. This means that:
- -- if NITER_BOUND->is_exit is true, then everything before
- NITER_BOUND->stmt is executed at most NITER_BOUND->bound + 1
- times, and everything after it at most NITER_BOUND->bound times.
+ -- if NITER_BOUND->is_exit is true, then everything after
+ it at most NITER_BOUND->bound times.
-- If NITER_BOUND->is_exit is false, then if we can prove that when STMT
is executed, then NITER_BOUND->stmt is executed as well in the same
- iteration (we conclude that if both statements belong to the same
- basic block, or if STMT is after NITER_BOUND->stmt), then STMT
- is executed at most NITER_BOUND->bound + 1 times. Otherwise STMT is
- executed at most NITER_BOUND->bound + 2 times. */
+ iteration then STMT is executed at most NITER_BOUND->bound + 1 times.
+
+ If we can determine that NITER_BOUND->stmt is always executed
+ after STMT, then STMT is executed at most NITER_BOUND->bound + 2 times.
+ We conclude that if both statements belong to the same
+ basic block and STMT is before NITER_BOUND->stmt and there are no
+ statements with side effects in between. */
if (niter_bound->is_exit)
{
- if (stmt
- && stmt != niter_bound->stmt
- && stmt_dominates_stmt_p (niter_bound->stmt, stmt))
- cmp = GE_EXPR;
- else
- cmp = GT_EXPR;
+ if (stmt == niter_bound->stmt
+ || !stmt_dominates_stmt_p (niter_bound->stmt, stmt))
+ return false;
+ cmp = GE_EXPR;
}
else
{
- if (!stmt
- || (gimple_bb (stmt) != gimple_bb (niter_bound->stmt)
- && !stmt_dominates_stmt_p (niter_bound->stmt, stmt)))
+ if (!stmt_dominates_stmt_p (niter_bound->stmt, stmt))
{
+ gimple_stmt_iterator bsi;
+ if (gimple_bb (stmt) != gimple_bb (niter_bound->stmt)
+ || gimple_code (stmt) == GIMPLE_PHI
+ || gimple_code (niter_bound->stmt) == GIMPLE_PHI)
+ return false;
+
+ /* By stmt_dominates_stmt_p we already know that STMT appears
+ before NITER_BOUND->STMT. Still need to test that the loop
+ can not be terinated by a side effect in between. */
+ for (bsi = gsi_for_stmt (stmt); gsi_stmt (bsi) != niter_bound->stmt;
+ gsi_next (&bsi))
+ if (gimple_has_side_effects (gsi_stmt (bsi)))
+ return false;
bound += double_int_one;
if (bound.is_zero ()
|| !double_int_fits_to_tree_p (nit_type, bound))
@@ -3640,10 +3658,12 @@ scev_probably_wraps_p (tree base, tree s
gimple at_stmt, struct loop *loop,
bool use_overflow_semantics)
{
- struct nb_iter_bound *bound;
tree delta, step_abs;
tree unsigned_type, valid_niter;
tree type = TREE_TYPE (step);
+ tree e;
+ double_int niter;
+ struct nb_iter_bound *bound;
/* FIXME: We really need something like
http://gcc.gnu.org/ml/gcc-patches/2005-06/msg02025.html.
@@ -3706,14 +3726,26 @@ scev_probably_wraps_p (tree base, tree s
valid_niter = fold_build2 (FLOOR_DIV_EXPR, unsigned_type, delta, step_abs);
estimate_numbers_of_iterations_loop (loop);
- for (bound = loop->bounds; bound; bound = bound->next)
+
+ if (max_loop_iterations (loop, &niter)
+ && double_int_fits_to_tree_p (TREE_TYPE (valid_niter), niter)
+ && (e = fold_binary (GT_EXPR, boolean_type_node, valid_niter,
+ double_int_to_tree (TREE_TYPE (valid_niter),
+ niter))) != NULL
+ && integer_nonzerop (e))
{
- if (n_of_executions_at_most (at_stmt, bound, valid_niter))
- {
- fold_undefer_and_ignore_overflow_warnings ();
- return false;
- }
+ fold_undefer_and_ignore_overflow_warnings ();
+ return false;
}
+ if (at_stmt)
+ for (bound = loop->bounds; bound; bound = bound->next)
+ {
+ if (n_of_executions_at_most (at_stmt, bound, valid_niter))
+ {
+ fold_undefer_and_ignore_overflow_warnings ();
+ return false;
+ }
+ }
fold_undefer_and_ignore_overflow_warnings ();
