------- 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
