* PR 55875 (IV wrapping issue)
@ 2013-01-08 16:35 Jan Hubicka
2013-01-08 16:49 ` Jan Hubicka
0 siblings, 1 reply; 6+ messages in thread
From: Jan Hubicka @ 2013-01-08 16:35 UTC (permalink / raw)
To: gcc-patches, rguenther, jakub
Hi,
My patch to add bounds that are not dominating loop latch caused problem in
scev_probably_wraps_p that is trying to prove that given IV at given STMT is
not wrapping based on loop bounds. When I was extending loop bounds to contain
not only statements that dominate the loop latch, I verified the users that
they are valid after the change. In this case it is however not true. What I
missed is that it does two things
1) it tries to prove that STMT is bounded by given bound based on fact that
bound's STMT dominate the statement
2) it tries to prove the bound based on number of iterations of loop that it
derrives from the bounds
I saw the dominance test in there and was happy. Obviously however 2) needs to
be updated. It seems to me best to simply drop 2) that anyway is just
determining a bound on number of iterations and use the bound recorded in the
structure.
While doing that I also noticed older problem in the postdominance
test - we need to verify that loop is not terminated by a call or other side
ffect as demonstrated by the new C testcase I constructed. This testcase
probably fails in 4.7 and earlier releases.
Boostrapped/regtested x86_64-linux
Honza
* 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,37 @@ 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))
{
+ 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. */
bound += double_int_one;
if (bound.is_zero ()
|| !double_int_fits_to_tree_p (nit_type, bound))
@@ -3640,10 +3652,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 +3720,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 ();
^ permalink raw reply [flat|nested] 6+ messages in thread
* Re: PR 55875 (IV wrapping issue)
2013-01-08 16:35 PR 55875 (IV wrapping issue) Jan Hubicka
@ 2013-01-08 16:49 ` Jan Hubicka
2013-01-08 16:51 ` Jakub Jelinek
2013-01-08 20:28 ` Jan Hubicka
0 siblings, 2 replies; 6+ messages in thread
From: Jan Hubicka @ 2013-01-08 16:49 UTC (permalink / raw)
To: Jan Hubicka; +Cc: gcc-patches, rguenther, jakub
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 ();
^ permalink raw reply [flat|nested] 6+ messages in thread
* Re: PR 55875 (IV wrapping issue)
2013-01-08 16:49 ` Jan Hubicka
@ 2013-01-08 16:51 ` Jakub Jelinek
2013-01-08 20:28 ` Jan Hubicka
1 sibling, 0 replies; 6+ messages in thread
From: Jakub Jelinek @ 2013-01-08 16:51 UTC (permalink / raw)
To: Jan Hubicka; +Cc: gcc-patches, rguenther
On Tue, Jan 08, 2013 at 05:49:28PM +0100, Jan Hubicka wrote:
> --- testsuite/gcc.c-torture/execute/pr55875.c (revision 0)
> +++ testsuite/gcc.c-torture/execute/pr55875.c (revision 0)
> @@ -0,0 +1,17 @@
Please add
/* PR tree-optimization/55875 */
here.
> +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)
And
// PR tree-optimization/55875
// { dg-do run }
here, dg-do compile is the default.
> @@ -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;
There should be tabs on the 4 above lines, just bugzilla ate it.
Jakub
^ permalink raw reply [flat|nested] 6+ messages in thread
* Re: PR 55875 (IV wrapping issue)
2013-01-08 16:49 ` Jan Hubicka
2013-01-08 16:51 ` Jakub Jelinek
@ 2013-01-08 20:28 ` Jan Hubicka
2013-01-09 9:05 ` Richard Biener
1 sibling, 1 reply; 6+ messages in thread
From: Jan Hubicka @ 2013-01-08 20:28 UTC (permalink / raw)
To: Jan Hubicka; +Cc: gcc-patches, rguenther, jakub
Hi,
here is even more updated patch, this time really fixing the testcase, I hope ;)
It turns out there is one extra problem in tree-ssa-loop-niter.c triggered by
that code. Some bounds, like one based on inequality test or with wrapping
IVs are bounds only when they are executed every iteration.
Boostrapped/regtested x86_64-linux.
Honza
PR tree-optimiation/55875
* gcc.c-torture/execute/pr55875.c: New testcase.
* g++.dg/torture/pr55875.C: New testcase.
* tree-ssa-loop-niter.c (number_of_iterations_cond): Add
EVERY_ITERATION parameter.
(number_of_iterations_exit): Check if exit is executed every
iteration.
(idx_infer_loop_bounds): Similarly here.
(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: tree-ssa-loop-niter.c
===================================================================
*** tree-ssa-loop-niter.c (revision 194918)
--- tree-ssa-loop-niter.c (working copy)
*************** dump_affine_iv (FILE *file, affine_iv *i
*** 1208,1213 ****
--- 1208,1215 ----
-- in this case we can use the information whether the control induction
variables can overflow or not in a more efficient way.
+ if EVERY_ITERATION is true, we know the test is executed on every iteration.
+
The results (number of iterations and assumptions as described in
comments at struct tree_niter_desc in tree-flow.h) are stored to NITER.
Returns false if it fails to determine number of iterations, true if it
*************** static bool
*** 1217,1227 ****
number_of_iterations_cond (struct loop *loop,
tree type, affine_iv *iv0, enum tree_code code,
affine_iv *iv1, struct tree_niter_desc *niter,
! bool only_exit)
{
bool exit_must_be_taken = false, ret;
bounds bnds;
/* The meaning of these assumptions is this:
if !assumptions
then the rest of information does not have to be valid
--- 1219,1239 ----
number_of_iterations_cond (struct loop *loop,
tree type, affine_iv *iv0, enum tree_code code,
affine_iv *iv1, struct tree_niter_desc *niter,
! bool only_exit, bool every_iteration)
{
bool exit_must_be_taken = false, ret;
bounds bnds;
+ /* If the test is not executed every iteration, wrapping may make the test
+ to pass again.
+ TODO: the overflow case can be still used as unreliable estimate of upper
+ bound. But we have no API to pass it down to number of iterations code
+ and, at present, it will not use it anyway. */
+ if (!every_iteration
+ && (!iv0->no_overflow || !iv1->no_overflow
+ || code == NE_EXPR || code == EQ_EXPR))
+ return false;
+
/* The meaning of these assumptions is this:
if !assumptions
then the rest of information does not have to be valid
*************** number_of_iterations_exit (struct loop *
*** 1807,1815 ****
tree op0, op1;
enum tree_code code;
affine_iv iv0, iv1;
! if (every_iteration
! && !dominated_by_p (CDI_DOMINATORS, loop->latch, exit->src))
return false;
niter->assumptions = boolean_false_node;
--- 1819,1829 ----
tree op0, op1;
enum tree_code code;
affine_iv iv0, iv1;
+ bool safe;
! safe = dominated_by_p (CDI_DOMINATORS, loop->latch, exit->src);
!
! if (every_iteration && !safe)
return false;
niter->assumptions = boolean_false_node;
*************** number_of_iterations_exit (struct loop *
*** 1855,1861 ****
iv0.base = expand_simple_operations (iv0.base);
iv1.base = expand_simple_operations (iv1.base);
if (!number_of_iterations_cond (loop, type, &iv0, code, &iv1, niter,
! loop_only_exit_p (loop, exit)))
{
fold_undefer_and_ignore_overflow_warnings ();
return false;
--- 1869,1875 ----
iv0.base = expand_simple_operations (iv0.base);
iv1.base = expand_simple_operations (iv1.base);
if (!number_of_iterations_cond (loop, type, &iv0, code, &iv1, niter,
! loop_only_exit_p (loop, exit), safe))
{
fold_undefer_and_ignore_overflow_warnings ();
return false;
*************** idx_infer_loop_bounds (tree base, tree *
*** 2657,2662 ****
--- 2671,2677 ----
tree low, high, type, next;
bool sign, upper = true, at_end = false;
struct loop *loop = data->loop;
+ bool reliable = true;
if (TREE_CODE (base) != ARRAY_REF)
return true;
*************** idx_infer_loop_bounds (tree base, tree *
*** 2728,2734 ****
&& tree_int_cst_compare (next, high) <= 0)
return true;
! record_nonwrapping_iv (loop, init, step, data->stmt, low, high, true, upper);
return true;
}
--- 2743,2756 ----
&& tree_int_cst_compare (next, high) <= 0)
return true;
! /* If access is not executed on every iteration, we must ensure that overlow may
! not make the access valid later. */
! if (!dominated_by_p (CDI_DOMINATORS, loop->latch, gimple_bb (data->stmt))
! && scev_probably_wraps_p (initial_condition_in_loop_num (ev, loop->num),
! step, data->stmt, loop, true))
! reliable = false;
!
! record_nonwrapping_iv (loop, init, step, data->stmt, low, high, reliable, upper);
return true;
}
*************** stmt_dominates_stmt_p (gimple s1, gimple
*** 3549,3556 ****
/* 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. */
static bool
n_of_executions_at_most (gimple stmt,
--- 3571,3585 ----
/* 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 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,
*************** n_of_executions_at_most (gimple stmt,
*** 3571,3602 ****
/* 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 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. */
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;
}
else
{
! if (!stmt
! || (gimple_bb (stmt) != gimple_bb (niter_bound->stmt)
! && !stmt_dominates_stmt_p (niter_bound->stmt, stmt)))
{
bound += double_int_one;
if (bound.is_zero ()
|| !double_int_fits_to_tree_p (nit_type, bound))
--- 3600,3642 ----
/* 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 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 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 == niter_bound->stmt
! || !stmt_dominates_stmt_p (niter_bound->stmt, stmt))
! return false;
! cmp = GE_EXPR;
}
else
{
! 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))
*************** scev_probably_wraps_p (tree base, tree s
*** 3640,3649 ****
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);
/* FIXME: We really need something like
http://gcc.gnu.org/ml/gcc-patches/2005-06/msg02025.html.
--- 3680,3691 ----
gimple at_stmt, struct loop *loop,
bool use_overflow_semantics)
{
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.
*************** scev_probably_wraps_p (tree base, tree s
*** 3706,3719 ****
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 (n_of_executions_at_most (at_stmt, bound, valid_niter))
! {
! fold_undefer_and_ignore_overflow_warnings ();
! return false;
! }
}
fold_undefer_and_ignore_overflow_warnings ();
--- 3748,3773 ----
valid_niter = fold_build2 (FLOOR_DIV_EXPR, unsigned_type, delta, step_abs);
estimate_numbers_of_iterations_loop (loop);
!
! 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))
{
! 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 ();
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 ****
--- 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/20070621-1.C
===================================================================
*** testsuite/g++.dg/torture/20070621-1.C (revision 195032)
--- testsuite/g++.dg/torture/20070621-1.C (working copy)
***************
*** 1,3 ****
--- 1,4 ----
+ // { dg-do compile }
/* Reduced from libstdc++-v3/testsuite/25_algorithms/equal/1.cc
1.2.ii: In function 'void test1()':
Index: testsuite/g++.dg/torture/pr55875.C
===================================================================
*** testsuite/g++.dg/torture/pr55875.C (revision 0)
--- testsuite/g++.dg/torture/pr55875.C (revision 0)
***************
*** 0 ****
--- 1,55 ----
+ // { dg-do run }
+
+ 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;
+ }
+
^ permalink raw reply [flat|nested] 6+ messages in thread
* Re: PR 55875 (IV wrapping issue)
2013-01-08 20:28 ` Jan Hubicka
@ 2013-01-09 9:05 ` Richard Biener
2013-01-09 13:57 ` Jan Hubicka
0 siblings, 1 reply; 6+ messages in thread
From: Richard Biener @ 2013-01-09 9:05 UTC (permalink / raw)
To: Jan Hubicka; +Cc: gcc-patches, jakub
On Tue, 8 Jan 2013, Jan Hubicka wrote:
> Hi,
> here is even more updated patch, this time really fixing the testcase, I hope ;)
> It turns out there is one extra problem in tree-ssa-loop-niter.c triggered by
> that code. Some bounds, like one based on inequality test or with wrapping
> IVs are bounds only when they are executed every iteration.
>
> Boostrapped/regtested x86_64-linux.
>
> Honza
>
> PR tree-optimiation/55875
> * gcc.c-torture/execute/pr55875.c: New testcase.
> * g++.dg/torture/pr55875.C: New testcase.
>
> * tree-ssa-loop-niter.c (number_of_iterations_cond): Add
> EVERY_ITERATION parameter.
> (number_of_iterations_exit): Check if exit is executed every
> iteration.
> (idx_infer_loop_bounds): Similarly here.
> (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: tree-ssa-loop-niter.c
> ===================================================================
> *** tree-ssa-loop-niter.c (revision 194918)
> --- tree-ssa-loop-niter.c (working copy)
> *************** dump_affine_iv (FILE *file, affine_iv *i
> *** 1208,1213 ****
> --- 1208,1215 ----
> -- in this case we can use the information whether the control induction
> variables can overflow or not in a more efficient way.
>
> + if EVERY_ITERATION is true, we know the test is executed on every iteration.
> +
> The results (number of iterations and assumptions as described in
> comments at struct tree_niter_desc in tree-flow.h) are stored to NITER.
> Returns false if it fails to determine number of iterations, true if it
> *************** static bool
> *** 1217,1227 ****
> number_of_iterations_cond (struct loop *loop,
> tree type, affine_iv *iv0, enum tree_code code,
> affine_iv *iv1, struct tree_niter_desc *niter,
> ! bool only_exit)
> {
> bool exit_must_be_taken = false, ret;
> bounds bnds;
>
> /* The meaning of these assumptions is this:
> if !assumptions
> then the rest of information does not have to be valid
> --- 1219,1239 ----
> number_of_iterations_cond (struct loop *loop,
> tree type, affine_iv *iv0, enum tree_code code,
> affine_iv *iv1, struct tree_niter_desc *niter,
> ! bool only_exit, bool every_iteration)
> {
> bool exit_must_be_taken = false, ret;
> bounds bnds;
>
> + /* If the test is not executed every iteration, wrapping may make the test
> + to pass again.
> + TODO: the overflow case can be still used as unreliable estimate of upper
> + bound. But we have no API to pass it down to number of iterations code
> + and, at present, it will not use it anyway. */
> + if (!every_iteration
> + && (!iv0->no_overflow || !iv1->no_overflow
> + || code == NE_EXPR || code == EQ_EXPR))
> + return false;
> +
> /* The meaning of these assumptions is this:
> if !assumptions
> then the rest of information does not have to be valid
> *************** number_of_iterations_exit (struct loop *
> *** 1807,1815 ****
> tree op0, op1;
> enum tree_code code;
> affine_iv iv0, iv1;
>
> ! if (every_iteration
> ! && !dominated_by_p (CDI_DOMINATORS, loop->latch, exit->src))
> return false;
>
> niter->assumptions = boolean_false_node;
> --- 1819,1829 ----
> tree op0, op1;
> enum tree_code code;
> affine_iv iv0, iv1;
> + bool safe;
>
> ! safe = dominated_by_p (CDI_DOMINATORS, loop->latch, exit->src);
> !
> ! if (every_iteration && !safe)
> return false;
>
> niter->assumptions = boolean_false_node;
> *************** number_of_iterations_exit (struct loop *
> *** 1855,1861 ****
> iv0.base = expand_simple_operations (iv0.base);
> iv1.base = expand_simple_operations (iv1.base);
> if (!number_of_iterations_cond (loop, type, &iv0, code, &iv1, niter,
> ! loop_only_exit_p (loop, exit)))
> {
> fold_undefer_and_ignore_overflow_warnings ();
> return false;
> --- 1869,1875 ----
> iv0.base = expand_simple_operations (iv0.base);
> iv1.base = expand_simple_operations (iv1.base);
> if (!number_of_iterations_cond (loop, type, &iv0, code, &iv1, niter,
> ! loop_only_exit_p (loop, exit), safe))
> {
> fold_undefer_and_ignore_overflow_warnings ();
> return false;
> *************** idx_infer_loop_bounds (tree base, tree *
> *** 2657,2662 ****
> --- 2671,2677 ----
> tree low, high, type, next;
> bool sign, upper = true, at_end = false;
> struct loop *loop = data->loop;
> + bool reliable = true;
>
> if (TREE_CODE (base) != ARRAY_REF)
> return true;
> *************** idx_infer_loop_bounds (tree base, tree *
> *** 2728,2734 ****
> && tree_int_cst_compare (next, high) <= 0)
> return true;
>
> ! record_nonwrapping_iv (loop, init, step, data->stmt, low, high, true, upper);
> return true;
> }
>
> --- 2743,2756 ----
> && tree_int_cst_compare (next, high) <= 0)
> return true;
>
> ! /* If access is not executed on every iteration, we must ensure that overlow may
> ! not make the access valid later. */
> ! if (!dominated_by_p (CDI_DOMINATORS, loop->latch, gimple_bb (data->stmt))
> ! && scev_probably_wraps_p (initial_condition_in_loop_num (ev, loop->num),
> ! step, data->stmt, loop, true))
> ! reliable = false;
> !
> ! record_nonwrapping_iv (loop, init, step, data->stmt, low, high, reliable, upper);
> return true;
> }
>
> *************** stmt_dominates_stmt_p (gimple s1, gimple
> *** 3549,3556 ****
> /* 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. */
>
> static bool
> n_of_executions_at_most (gimple stmt,
> --- 3571,3585 ----
> /* 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 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,
> *************** n_of_executions_at_most (gimple stmt,
> *** 3571,3602 ****
> /* 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 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. */
>
> 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;
> }
> else
> {
> ! if (!stmt
> ! || (gimple_bb (stmt) != gimple_bb (niter_bound->stmt)
> ! && !stmt_dominates_stmt_p (niter_bound->stmt, stmt)))
> {
> bound += double_int_one;
> if (bound.is_zero ()
> || !double_int_fits_to_tree_p (nit_type, bound))
> --- 3600,3642 ----
> /* 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 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 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 == niter_bound->stmt
> ! || !stmt_dominates_stmt_p (niter_bound->stmt, stmt))
> ! return false;
> ! cmp = GE_EXPR;
> }
> else
> {
> ! 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;
Ugh. Both to stmt_dominates_stmt_p and to this (both use loops).
For stmt_dominates_stmt_p you'd simply use GIMPLE uids as other
passes do (and compute them, of course), for the above you'd
alongside of the UID store a sequence number that increments
at each stmt with side-effect. UID is 32bits, so you could
even store (stmt-number-in-bb << 8) | side-effect-nr in UID
(with the issue that if there are exactly 256 side-effect stmts
inbetween the two stmts you'd miss that fact ...).
Well. At least those loops are a real issue IMHO. Adding a
second doesn't make complexity worse I understand - still ...
I expected better from you ;)
Patch is ok, but think about this for a minute - eventually
you can come up with sth very clever.
Thanks,
Richard.
> bound += double_int_one;
> if (bound.is_zero ()
> || !double_int_fits_to_tree_p (nit_type, bound))
> *************** scev_probably_wraps_p (tree base, tree s
> *** 3640,3649 ****
> 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);
>
> /* FIXME: We really need something like
> http://gcc.gnu.org/ml/gcc-patches/2005-06/msg02025.html.
> --- 3680,3691 ----
> gimple at_stmt, struct loop *loop,
> bool use_overflow_semantics)
> {
> 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.
> *************** scev_probably_wraps_p (tree base, tree s
> *** 3706,3719 ****
> 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 (n_of_executions_at_most (at_stmt, bound, valid_niter))
> ! {
> ! fold_undefer_and_ignore_overflow_warnings ();
> ! return false;
> ! }
> }
>
> fold_undefer_and_ignore_overflow_warnings ();
>
> --- 3748,3773 ----
> valid_niter = fold_build2 (FLOOR_DIV_EXPR, unsigned_type, delta, step_abs);
>
> estimate_numbers_of_iterations_loop (loop);
> !
> ! 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))
> {
> ! 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 ();
>
> 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 ****
> --- 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/20070621-1.C
> ===================================================================
> *** testsuite/g++.dg/torture/20070621-1.C (revision 195032)
> --- testsuite/g++.dg/torture/20070621-1.C (working copy)
> ***************
> *** 1,3 ****
> --- 1,4 ----
> + // { dg-do compile }
> /* Reduced from libstdc++-v3/testsuite/25_algorithms/equal/1.cc
>
> 1.2.ii: In function 'void test1()':
> Index: testsuite/g++.dg/torture/pr55875.C
> ===================================================================
> *** testsuite/g++.dg/torture/pr55875.C (revision 0)
> --- testsuite/g++.dg/torture/pr55875.C (revision 0)
> ***************
> *** 0 ****
> --- 1,55 ----
> + // { dg-do run }
> +
> + 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;
> + }
> +
>
>
--
Richard Biener <rguenther@suse.de>
SUSE / SUSE Labs
SUSE LINUX Products GmbH - Nuernberg - AG Nuernberg - HRB 16746
GF: Jeff Hawn, Jennifer Guild, Felix Imend
^ permalink raw reply [flat|nested] 6+ messages in thread
* Re: PR 55875 (IV wrapping issue)
2013-01-09 9:05 ` Richard Biener
@ 2013-01-09 13:57 ` Jan Hubicka
0 siblings, 0 replies; 6+ messages in thread
From: Jan Hubicka @ 2013-01-09 13:57 UTC (permalink / raw)
To: Richard Biener; +Cc: Jan Hubicka, gcc-patches, jakub
>
> Ugh. Both to stmt_dominates_stmt_p and to this (both use loops).
> For stmt_dominates_stmt_p you'd simply use GIMPLE uids as other
> passes do (and compute them, of course), for the above you'd
> alongside of the UID store a sequence number that increments
> at each stmt with side-effect. UID is 32bits, so you could
> even store (stmt-number-in-bb << 8) | side-effect-nr in UID
> (with the issue that if there are exactly 256 side-effect stmts
> inbetween the two stmts you'd miss that fact ...).
>
> Well. At least those loops are a real issue IMHO. Adding a
> second doesn't make complexity worse I understand - still ...
> I expected better from you ;)
>
> Patch is ok, but think about this for a minute - eventually
> you can come up with sth very clever.
As I wrote in the comment above, I think it is best to precompute
the bounds in number of iterations in basic blocks by same
algorithm as discover_iteration_bound_by_body_walk.
We will then have O(nstmts+nbounds) algorithm.
The challenge is where to attach the data and how to keep it up to date.
The non-wrappingness is tested on random uses of SCEV across the compiler when
the loop body can be somewhat modified already (so thus also UIDs will run out
of sync). Moreover the non-wrappingness is used by niter logic itself when
bounds are being inserted (giving conservatively wrong answers)
So I think it is more of 4.9 material.
I would expect us to be actually slightly faster than before the patch,
because we skip the bound walk when iterations already give the info.
With constant time gsi_for_stmt the loop in stmt_dominates_stmt_p can probably
be changed to start walk on one statement and look for the second.
Honza
^ permalink raw reply [flat|nested] 6+ messages in thread
end of thread, other threads:[~2013-01-09 13:57 UTC | newest]
Thread overview: 6+ messages (download: mbox.gz / follow: Atom feed)
-- links below jump to the message on this page --
2013-01-08 16:35 PR 55875 (IV wrapping issue) Jan Hubicka
2013-01-08 16:49 ` Jan Hubicka
2013-01-08 16:51 ` Jakub Jelinek
2013-01-08 20:28 ` Jan Hubicka
2013-01-09 9:05 ` Richard Biener
2013-01-09 13:57 ` Jan Hubicka
This is a public inbox, see mirroring instructions
for how to clone and mirror all data and code used for this inbox;
as well as URLs for read-only IMAP folder(s) and NNTP newsgroup(s).