[Bug tree-optimization/45427] Number of iteration analysis bogus
--- Comment #15 from rguenth at gcc dot gnu dot org 2010-09-03 11:32 --- Fixed. -- rguenth at gcc dot gnu dot org changed: What|Removed |Added Status|UNCONFIRMED |RESOLVED Resolution||FIXED http://gcc.gnu.org/bugzilla/show_bug.cgi?id=45427
[Bug tree-optimization/45427] Number of iteration analysis bogus
--- Comment #14 from rakdver at gcc dot gnu dot org 2010-08-30 19:50 --- Subject: Bug 45427 Author: rakdver Date: Mon Aug 30 19:50:05 2010 New Revision: 163659 URL: http://gcc.gnu.org/viewcvs?root=gccview=revrev=163659 Log: PR tree-optimization/45427 * tree-ssa-loop-niter.c (number_of_iterations_ne_max): Rewritten. Handle the case that the exit is never taken correctly. (number_of_iterations_ne): Pass exit_must_be_taken to number_of_iterations_ne_max. * gcc.dg/tree-ssa/pr45427.c: New test. Added: trunk/gcc/testsuite/gcc.dg/tree-ssa/pr45427.c Modified: trunk/gcc/ChangeLog trunk/gcc/testsuite/ChangeLog trunk/gcc/tree-ssa-loop-niter.c -- http://gcc.gnu.org/bugzilla/show_bug.cgi?id=45427
[Bug tree-optimization/45427] Number of iteration analysis bogus
--- Comment #10 from rakdver at gcc dot gnu dot org 2010-08-28 10:37 --- Created an attachment (id=21582) -- (http://gcc.gnu.org/bugzilla/attachment.cgi?id=21582action=view) proposed patch -- http://gcc.gnu.org/bugzilla/show_bug.cgi?id=45427
[Bug tree-optimization/45427] Number of iteration analysis bogus
--- Comment #11 from rakdver at gcc dot gnu dot org 2010-08-28 10:38 --- Does the patch fix your problem? -- http://gcc.gnu.org/bugzilla/show_bug.cgi?id=45427
[Bug tree-optimization/45427] Number of iteration analysis bogus
--- Comment #12 from rguenther at suse dot de 2010-08-28 11:09 --- Subject: Re: Number of iteration analysis bogus On Sat, 28 Aug 2010, rakdver at gcc dot gnu dot org wrote: --- Comment #11 from rakdver at gcc dot gnu dot org 2010-08-28 10:38 --- Does the patch fix your problem? Yes, that fixes it. Thanks! -- http://gcc.gnu.org/bugzilla/show_bug.cgi?id=45427
[Bug tree-optimization/45427] Number of iteration analysis bogus
--- Comment #13 from rakdver at gcc dot gnu dot org 2010-08-28 13:39 --- Created an attachment (id=21584) -- (http://gcc.gnu.org/bugzilla/attachment.cgi?id=21584action=view) a new version of the patch There were some problems with the previous patch (that could only manifest for some rather weird loops, but anyway). This one fixes them as well as extends the comments and restructures the function somewhat, which should hopefully make it clearer what's going on. -- rakdver at gcc dot gnu dot org changed: What|Removed |Added Attachment #21582|0 |1 is obsolete|| http://gcc.gnu.org/bugzilla/show_bug.cgi?id=45427
[Bug tree-optimization/45427] Number of iteration analysis bogus
--- Comment #1 from rguenth at gcc dot gnu dot org 2010-08-27 14:50 ---
C testcase:
extern void abort (void);
int __attribute__((noinline,noclone))
foo (char *p)
{
int h = 0;
do
{
if (*p == '\0')
break;
++h;
if (p == 0)
abort ();
++p;
}
while (1);
return h;
}
int main()
{
if (foo(a) != 1)
abort ();
return 0;
}
--
http://gcc.gnu.org/bugzilla/show_bug.cgi?id=45427
[Bug tree-optimization/45427] Number of iteration analysis bogus
--- Comment #2 from rguenth at gcc dot gnu dot org 2010-08-27 14:59 --- And here's the patch I'm talking about: http://gcc.gnu.org/ml/gcc-patches/2010-08/msg01981.html -- http://gcc.gnu.org/bugzilla/show_bug.cgi?id=45427
[Bug tree-optimization/45427] Number of iteration analysis bogus
--- Comment #4 from rakdver at kam dot mff dot cuni dot cz 2010-08-27
16:33 ---
Subject: Re: New: Number of iteration
analysis bogus
when looking at the exit 6-7 number_of_iterations_ne is present with
iv-base (cxb3014__test_block__char_pointers__element * {ref-all}) ref_4(D)
and final 0B, the step is 1. We then do
else
{
s = fold_convert (niter_type, iv-step);
c = fold_build2 (MINUS_EXPR, niter_type,
fold_convert (niter_type, final),
fold_convert (niter_type, iv-base));
}
which creates -(UNSIGNED_64) ref_4(D) for c, with no_overflow set as we
do for pointers (but note we now have unsigned_type_for, a non-pointer!)
This looks correct to me, as far as I can tell. The original induction
variable
has pointer type, and thus it cannot overflow without causing undefined
behavior.
I do not understand the problem; what would you expect the result of the
analysis to be?
--
http://gcc.gnu.org/bugzilla/show_bug.cgi?id=45427
[Bug tree-optimization/45427] Number of iteration analysis bogus
--- Comment #3 from rguenth at gcc dot gnu dot org 2010-08-27 16:12 --- I think the bug is that we assume the exit is taken at some point, which is not true if we assume the induction variable does not wrap (so we only can assume one of both those assumptions at the same time). -- http://gcc.gnu.org/bugzilla/show_bug.cgi?id=45427
[Bug tree-optimization/45427] Number of iteration analysis bogus
--- Comment #5 from rguenther at suse dot de 2010-08-27 17:23 ---
Subject: Re: Number of iteration analysis
bogus
On Fri, 27 Aug 2010, rakdver at kam dot mff dot cuni dot cz wrote:
--- Comment #4 from rakdver at kam dot mff dot cuni dot cz 2010-08-27
16:33 ---
Subject: Re: New: Number of iteration
analysis bogus
when looking at the exit 6-7 number_of_iterations_ne is present with
iv-base (cxb3014__test_block__char_pointers__element * {ref-all}) ref_4(D)
and final 0B, the step is 1. We then do
else
{
s = fold_convert (niter_type, iv-step);
c = fold_build2 (MINUS_EXPR, niter_type,
fold_convert (niter_type, final),
fold_convert (niter_type, iv-base));
}
which creates -(UNSIGNED_64) ref_4(D) for c, with no_overflow set as we
do for pointers (but note we now have unsigned_type_for, a non-pointer!)
This looks correct to me, as far as I can tell. The original induction
variable
has pointer type, and thus it cannot overflow without causing undefined
behavior.
I do not understand the problem; what would you expect the result of the
analysis to be?
At the moment we get (for the C testcase):
Analyzing # of iterations of loop 1
exit condition [p_4(D), + , 1](no_overflow) != 0B
bounds on difference of bases: -18446744073709551615 ... 0
result:
# of iterations -(long unsigned int) p_4(D), bounded by 0
Statement (exit)if (p_1 == 0B)
is executed at most -(long unsigned int) p_4(D) (bounded by 0) + 1 times
in loop 1.
thus, nb-iterations is bound by zero. But that's wrong, we're using
the estimate for an exit that isn't taken (or that estimate is wrong).
0 - (UNSIGNED_64) ref_4(D) is overflowing, so we shouldn't assess
that there's no overflow involved.
Richard.
--
http://gcc.gnu.org/bugzilla/show_bug.cgi?id=45427
[Bug tree-optimization/45427] Number of iteration analysis bogus
--- Comment #6 from rguenth at gcc dot gnu dot org 2010-08-27 17:26 --- You can see that analysis happening with the C testcase on unpatched trunk when looking at the cunrolli dump at -O2 for example. Analyzing # of iterations of loop 1 exit condition [p_4(D), + , 1](no_overflow) != 0B bounds on difference of bases: -18446744073709551615 ... 0 result: # of iterations -(long unsigned int) p_4(D), bounded by 0 -- http://gcc.gnu.org/bugzilla/show_bug.cgi?id=45427
[Bug tree-optimization/45427] Number of iteration analysis bogus
--- Comment #7 from rguenth at gcc dot gnu dot org 2010-08-27 17:27 --- Or in the cddce1 dump: Analyzing # of iterations of loop 1 exit condition [p_4(D), + , 1](no_overflow) != 0B bounds on difference of bases: -18446744073709551615 ... 0 result: # of iterations -(long unsigned int) p_4(D), bounded by 0 Found loop 1 to be finite: iterating -(long unsigned int) p_4(D) times where we might be able to construct a testcase with an infinite loop and no side-effects that CDCE will then remove. -- http://gcc.gnu.org/bugzilla/show_bug.cgi?id=45427
[Bug tree-optimization/45427] Number of iteration analysis bogus
--- Comment #8 from rakdver at kam dot mff dot cuni dot cz 2010-08-27
18:47 ---
Subject: Re: Number of iteration analysis
bogus
when looking at the exit 6-7 number_of_iterations_ne is present with
iv-base (cxb3014__test_block__char_pointers__element * {ref-all})
ref_4(D)
and final 0B, the step is 1. We then do
else
{
s = fold_convert (niter_type, iv-step);
c = fold_build2 (MINUS_EXPR, niter_type,
fold_convert (niter_type, final),
fold_convert (niter_type, iv-base));
}
which creates -(UNSIGNED_64) ref_4(D) for c, with no_overflow set as we
do for pointers (but note we now have unsigned_type_for, a non-pointer!)
This looks correct to me, as far as I can tell. The original induction
variable
has pointer type, and thus it cannot overflow without causing undefined
behavior.
I do not understand the problem; what would you expect the result of the
analysis to be?
At the moment we get (for the C testcase):
Analyzing # of iterations of loop 1
exit condition [p_4(D), + , 1](no_overflow) != 0B
bounds on difference of bases: -18446744073709551615 ... 0
result:
# of iterations -(long unsigned int) p_4(D), bounded by 0
Statement (exit)if (p_1 == 0B)
is executed at most -(long unsigned int) p_4(D) (bounded by 0) + 1 times
in loop 1.
thus, nb-iterations is bound by zero. But that's wrong, we're using
the estimate for an exit that isn't taken (or that estimate is wrong).
This is something I forgot to document in the comments for tree_niter_desc
(although it is mentioned in the comments of number_of_iterations_ne_max) --
niter-max is valid only under the assumption that the exit is taken.
Unfortunately, I must have forgotten about this assumption as well, since
even the (only current) use in estimate_numbers_of_iterations_loop
gets this wrong.
The solution is to use the current method for computing niter-max only if
exit_must_be_taken is true, and something more conservative otherwise. I will
fix that.
--
http://gcc.gnu.org/bugzilla/show_bug.cgi?id=45427
[Bug tree-optimization/45427] Number of iteration analysis bogus
--- Comment #9 from rguenther at suse dot de 2010-08-27 18:52 ---
Subject: Re: Number of iteration analysis
bogus
On Fri, 27 Aug 2010, rakdver at kam dot mff dot cuni dot cz wrote:
--- Comment #8 from rakdver at kam dot mff dot cuni dot cz 2010-08-27
18:47 ---
Subject: Re: Number of iteration analysis
bogus
when looking at the exit 6-7 number_of_iterations_ne is present with
iv-base (cxb3014__test_block__char_pointers__element * {ref-all})
ref_4(D)
and final 0B, the step is 1. We then do
else
{
s = fold_convert (niter_type, iv-step);
c = fold_build2 (MINUS_EXPR, niter_type,
fold_convert (niter_type, final),
fold_convert (niter_type, iv-base));
}
which creates -(UNSIGNED_64) ref_4(D) for c, with no_overflow set as we
do for pointers (but note we now have unsigned_type_for, a non-pointer!)
This looks correct to me, as far as I can tell. The original induction
variable
has pointer type, and thus it cannot overflow without causing undefined
behavior.
I do not understand the problem; what would you expect the result of the
analysis to be?
At the moment we get (for the C testcase):
Analyzing # of iterations of loop 1
exit condition [p_4(D), + , 1](no_overflow) != 0B
bounds on difference of bases: -18446744073709551615 ... 0
result:
# of iterations -(long unsigned int) p_4(D), bounded by 0
Statement (exit)if (p_1 == 0B)
is executed at most -(long unsigned int) p_4(D) (bounded by 0) + 1 times
in loop 1.
thus, nb-iterations is bound by zero. But that's wrong, we're using
the estimate for an exit that isn't taken (or that estimate is wrong).
This is something I forgot to document in the comments for tree_niter_desc
(although it is mentioned in the comments of number_of_iterations_ne_max) --
niter-max is valid only under the assumption that the exit is taken.
Unfortunately, I must have forgotten about this assumption as well, since
even the (only current) use in estimate_numbers_of_iterations_loop
gets this wrong.
The solution is to use the current method for computing niter-max only if
exit_must_be_taken is true, and something more conservative otherwise. I will
fix that.
Thanks!
--
http://gcc.gnu.org/bugzilla/show_bug.cgi?id=45427
