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

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

[rguenth at gcc dot gnu dot org]

The analysis for nb_iterations_upper_bound is bogus when we derive bounds for
an exit check ptr == 0 (leading to an assert).  The testcase looks like
(subroutine cxb3014__test_block__char_pointers__value from acats CXB3014):

<bb 5>:
  # p_1 = PHI <ref_58(3), p_52(8)>
  # h_2 = PHI <0(3), h_10(8)>
  D.3266_7 = *p_1;
  if (D.3266_7 == terminator_9(D))
    goto <bb 9>;
  else
    goto <bb 6>;

<bb 6>:
  h_10 = h_2 + 1;
  if (p_1 == 0B)
    goto <bb 7>;
  else
    goto <bb 8>;

<bb 7>:
  D.3760.P_ARRAY = "i-cpoint.adb:59 instantiated at cxb3014.adb:114";
  D.3760.P_BOUNDS = &*.LC15;
  ada.exceptions.raise_exception_always (&char_pointers__pointer_error,
D.3760);

<bb 8>:
  left.84_50 = (cxb3014__test_block__char_pointers__addr) p_13;
  D.3762_51 = left.84_50 + 1;
  p_52 = (cxb3014__test_block__char_pointers__element * {ref-all}) D.3762_51;
  # DEBUG ref => p_52
  # DEBUG p => p_52
  goto <bb 5>;

<bb 9>:
  ...

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!)
we obviously can't reach zero with a step of 1 without overflowing
without the initial value being zero.

I have a patch in the works that uses number of iteration analysis for
value-range propagation and that miscompiles CXB3014 because of the
above bug.

Zdenek - any idea?


-- 
           Summary: Number of iteration analysis bogus
           Product: gcc
           Version: 4.6.0
            Status: UNCONFIRMED
          Keywords: wrong-code
          Severity: normal
          Priority: P3
         Component: tree-optimization
        AssignedTo: unassigned at gcc dot gnu dot org
        ReportedBy: rguenth at gcc dot gnu dot org


http://gcc.gnu.org/bugzilla/show_bug.cgi?id=45427

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

[rguenth at gcc dot gnu dot org]

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

[rguenth at gcc dot gnu dot org]

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

[rguenth at gcc dot gnu dot org]

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

[rakdver at kam dot mff dot cuni dot cz]

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

[rguenther at suse dot de]

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

[rguenth at gcc dot gnu dot org]

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

[rguenth at gcc dot gnu dot org]

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

[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

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

[rguenther at suse dot de]

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

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

[rakdver at gcc dot gnu dot org]

------- 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=21582&action=view)
proposed patch


-- 


http://gcc.gnu.org/bugzilla/show_bug.cgi?id=45427

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

[rakdver at gcc dot gnu dot org]

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

[rguenther at suse dot de]

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

[rakdver at gcc dot gnu dot org]

------- 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=21584&action=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

[rakdver at gcc dot gnu dot org]

------- 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=gcc&view=rev&rev=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

[rguenth at gcc dot gnu dot org]

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