[Bug tree-optimization/45427] Number of iteration analysis bogus

[rakdver at kam dot mff dot cuni dot cz]

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