[Bug tree-optimization/27039] New: Unable to determine # of iterations for a simple loop

[Bug tree-optimization/27039] New: Unable to determine # of iterations for a simple loop

[rakdver at gcc dot gnu dot org]

With the fix for PR 26763, we are unable to determine # of iterations of the
following loop, more precisely, we are unable to determine that it rolls -- for
that, we would need to fold p_4 + 4B > p_4 + 8B.

int foo (int *p)
{
  int i = 0, *x;

  for (x = p; x < p + 2; x++)
    i++;

  return i;
}


-- 
           Summary: Unable to determine # of iterations for a simple loop
           Product: gcc
           Version: 4.2.0
            Status: UNCONFIRMED
          Keywords: missed-optimization
          Severity: normal
          Priority: P3
         Component: tree-optimization
        AssignedTo: unassigned at gcc dot gnu dot org
        ReportedBy: rakdver at gcc dot gnu dot org


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

[Bug tree-optimization/27039] Unable to determine # of iterations for a simple loop

[rguenth at gcc dot gnu dot org]

------- Comment #1 from rguenth at gcc dot gnu dot org  2006-04-05 09:57 -------
Confirmed.  That gives us a testcase at least.

Now, back to the folding problem of

  PTR +- CST  CMP  PTR +- CST

where all of PTR / CST are of pointer type naturally and unsigned usually.
The problem was that the frontends/middle-end introduce pointer overflow via
presenting us with PTR + (unsigned)-CST.  Now, we may argue that if (signed)CST
is positive, that this didn't happen, and we can do the comparison in either
signed or unsigned mode.  Of course this won't help for p - 4 < p + 4, because
this is exactly where the above condition would trigger.

Does this sound reasonable?  Can anyone punch a hole in this argument?


-- 

rguenth at gcc dot gnu dot org changed:

           What    |Removed                     |Added
----------------------------------------------------------------------------
             Status|UNCONFIRMED                 |NEW
     Ever Confirmed|0                           |1
   Last reconfirmed|0000-00-00 00:00:00         |2006-04-05 09:57:15
               date|                            |


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

[Bug tree-optimization/27039] [4.1/4.2 Regression] Unable to determine # of iterations for a simple loop

[rguenth at gcc dot gnu dot org]

-- 

rguenth at gcc dot gnu dot org changed:

           What    |Removed                     |Added
----------------------------------------------------------------------------
         AssignedTo|unassigned at gcc dot gnu   |rguenth at gcc dot gnu dot
                   |dot org                     |org
             Status|NEW                         |ASSIGNED
   Last reconfirmed|2006-04-05 09:57:15         |2006-04-05 09:58:10
               date|                            |
            Summary|Unable to determine # of    |[4.1/4.2 Regression] Unable
                   |iterations for a simple loop|to determine # of iterations
                   |                            |for a simple loop
   Target Milestone|---                         |4.1.1


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

[Bug tree-optimization/27039] [4.1/4.2 Regression] Unable to determine # of iterations for a simple loop

[rakdver at atrey dot karlin dot mff dot cuni dot cz]

------- Comment #2 from rakdver at atrey dot karlin dot mff dot cuni dot cz  2006-04-05 10:05 -------
Subject: Re:  Unable to determine # of iterations for a simple loop

> Confirmed.  That gives us a testcase at least.
> 
> Now, back to the folding problem of
> 
>   PTR +- CST  CMP  PTR +- CST
> 
> where all of PTR / CST are of pointer type naturally and unsigned usually.
> The problem was that the frontends/middle-end introduce pointer overflow via
> presenting us with PTR + (unsigned)-CST.  Now, we may argue that if (signed)CST
> is positive, that this didn't happen, and we can do the comparison in either
> signed or unsigned mode.

If p points to the end of the array whose size is more than range of
signed, then this would make you mistakenly consider p - size > p.


-- 


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

[Bug tree-optimization/27039] [4.1/4.2 Regression] Unable to determine # of iterations for a simple loop

[rguenther at suse dot de]

------- Comment #3 from rguenther at suse dot de  2006-04-05 10:13 -------
Subject: Re:  [4.1/4.2 Regression] Unable to
 determine # of iterations for a simple loop

On Wed, 5 Apr 2006, rakdver at atrey dot karlin dot mff dot cuni dot cz wrote:

> Subject: Re:  Unable to determine # of iterations for a simple loop
> 
> > Confirmed.  That gives us a testcase at least.
> > 
> > Now, back to the folding problem of
> > 
> >   PTR +- CST  CMP  PTR +- CST
> > 
> > where all of PTR / CST are of pointer type naturally and unsigned usually.
> > The problem was that the frontends/middle-end introduce pointer overflow via
> > presenting us with PTR + (unsigned)-CST.  Now, we may argue that if (signed)CST
> > is positive, that this didn't happen, and we can do the comparison in either
> > signed or unsigned mode.
> 
> If p points to the end of the array whose size is more than range of
> signed, then this would make you mistakenly consider p - size > p.

Umm.  Correct :/  I guess the only way to "fix" the mess is to make the
frontends _not_ generate these spurious pointer overflows in the first 
place.  Like I asked for in

http://gcc.gnu.org/ml/gcc/2006-03/msg00866.html

where nobody commented.  :/


-- 


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

[Bug tree-optimization/27039] [4.1/4.2 Regression] Unable to determine # of iterations for a simple loop

[rakdver at atrey dot karlin dot mff dot cuni dot cz]

------- Comment #4 from rakdver at atrey dot karlin dot mff dot cuni dot cz  2006-04-05 10:20 -------
Subject: Re:  [4.1/4.2 Regression] Unable to determine # of iterations for a
simple loop

> > > Confirmed.  That gives us a testcase at least.
> > > 
> > > Now, back to the folding problem of
> > > 
> > >   PTR +- CST  CMP  PTR +- CST
> > > 
> > > where all of PTR / CST are of pointer type naturally and unsigned usually.
> > > The problem was that the frontends/middle-end introduce pointer overflow via
> > > presenting us with PTR + (unsigned)-CST.  Now, we may argue that if (signed)CST
> > > is positive, that this didn't happen, and we can do the comparison in either
> > > signed or unsigned mode.
> > 
> > If p points to the end of the array whose size is more than range of
> > signed, then this would make you mistakenly consider p - size > p.
> 
> Umm.  Correct :/  I guess the only way to "fix" the mess is to make the
> frontends _not_ generate these spurious pointer overflows in the first 
> place.  Like I asked for in
> 
> http://gcc.gnu.org/ml/gcc/2006-03/msg00866.html
> 
> where nobody commented.  :/

the problem is that it is a bit hard to avoid this.  What code should we
produce for 

signed i;
char *x;

x + i?

In order to avoid overflows when the addition is casted to an
unsigned type, we would have to translate it to
(i < 0) ? x - (char *) (-i) : x + (char *) i,
which would be really bad.


-- 


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

[Bug tree-optimization/27039] [4.1/4.2 Regression] Unable to determine # of iterations for a simple loop

[rguenther at suse dot de]

------- Comment #5 from rguenther at suse dot de  2006-04-05 10:28 -------
Subject: Re:  [4.1/4.2 Regression] Unable to
 determine # of iterations for a simple loop

On Wed, 5 Apr 2006, rakdver at atrey dot karlin dot mff dot cuni dot cz wrote:

> > Umm.  Correct :/  I guess the only way to "fix" the mess is to make the
> > frontends _not_ generate these spurious pointer overflows in the first 
> > place.  Like I asked for in
> > 
> > http://gcc.gnu.org/ml/gcc/2006-03/msg00866.html
> > 
> > where nobody commented.  :/
> 
> the problem is that it is a bit hard to avoid this.  What code should we
> produce for 
> 
> signed i;
> char *x;
> 
> x + i?
> 
> In order to avoid overflows when the addition is casted to an
> unsigned type, we would have to translate it to
> (i < 0) ? x - (char *) (-i) : x + (char *) i,
> which would be really bad.

At the moment the C frontend does in the x + i case

 x + (char *)(size_t)i

so, now this would be problematic for

 x + i < x

which would then become (effectively)

  (size_t)i < 0

which is false even for negative i.  Now, the frontend makes it worse,
because for constant offsets I believe we _can_ fold if we know the
constant didn't overflow.  I.e. at the moment for x - 1 we get

 x + (char *)(size_t)-1

which is bad, instead

 x - (char *)(size_t)1

would be much better here.  The question is of course, if the programmer
is allowed to write

 x + (size_t)-1

and expect the result to be defined.


-- 


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

[Bug tree-optimization/27039] [4.1/4.2 Regression] Unable to determine # of iterations for a simple loop

[rakdver at atrey dot karlin dot mff dot cuni dot cz]

------- Comment #6 from rakdver at atrey dot karlin dot mff dot cuni dot cz  2006-04-05 10:39 -------
Subject: Re:  [4.1/4.2 Regression] Unable to determine # of iterations for a
simple loop

> would be much better here.  The question is of course, if the programmer
> is allowed to write
> 
>  x + (size_t)-1
> 
> and expect the result to be defined.

if I understand the C standard correctly, no, this has undefined behavior.


-- 


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

[Bug tree-optimization/27039] [4.1/4.2 Regression] Unable to determine # of iterations for a simple loop

[rguenther at suse dot de]

------- Comment #7 from rguenther at suse dot de  2006-04-05 10:47 -------
Subject: Re:  [4.1/4.2 Regression] Unable to
 determine # of iterations for a simple loop

> > would be much better here.  The question is of course, if the programmer
> > is allowed to write
> > 
> >  x + (size_t)-1
> > 
> > and expect the result to be defined.
> 
> if I understand the C standard correctly, no, this has undefined behavior.

This is also my understanding, so we should try to avoid creating the
above in the frontends.  But of course, as discussed, this doesn't solve
the problem (does it, for constant offsets?).


-- 


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

[Bug tree-optimization/27039] [4.1/4.2 Regression] Unable to determine # of iterations for a simple loop

[mmitchel at gcc dot gnu dot org]

-- 

mmitchel at gcc dot gnu dot org changed:

           What    |Removed                     |Added
----------------------------------------------------------------------------
           Priority|P3                          |P2


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

[Bug tree-optimization/27039] [4.1/4.2 Regression] Unable to determine # of iterations for a simple loop

[rguenth at gcc dot gnu dot org]

------- Comment #8 from rguenth at gcc dot gnu dot org  2006-05-04 14:21 -------
Wording of 6.5.6/8 and /9 suggests that array objects larger than the maximum
value that fits in ptrdiff_t (which needs to be signed) invoke undefined
behavior,
not last because of "the expression ((Q)+1)-(P) has the same value as
((Q)-(P))+1 and as -((P)-((Q)+1))" and "The size of the result is
implementation-defined,
and its type (a signed integer type) is ptrdiff_t defined in the <stddef.h>
header.  If the result is not representable in an object of that type, the
behavior is undefined."

So for this reason I believe that folding

  PTR +- CST  CMP  PTR +- CST

(with CST being of pointer type, as represented by the middle-end) as

  +- (ptrdiff_t)CST  CMP  +- (ptrdiff_t)CST

is valid.  Now the intel compiler f.i. does _not_ do this.


-- 


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

[Bug tree-optimization/27039] [4.1/4.2 Regression] Unable to determine # of iterations for a simple loop

[rakdver at atrey dot karlin dot mff dot cuni dot cz]

------- Comment #9 from rakdver at atrey dot karlin dot mff dot cuni dot cz  2006-05-04 14:56 -------
Subject: Re:  [4.1/4.2 Regression] Unable to determine # of iterations for a
simple loop

> Wording of 6.5.6/8 and /9 suggests that array objects larger than the maximum
> value that fits in ptrdiff_t (which needs to be signed) invoke undefined
> behavior,
> not last because of "the expression ((Q)+1)-(P) has the same value as
> ((Q)-(P))+1 and as -((P)-((Q)+1))" and "The size of the result is
> implementation-defined,
> and its type (a signed integer type) is ptrdiff_t defined in the <stddef.h>
> header.  If the result is not representable in an object of that type, the
> behavior is undefined."

However, this only concerns difference of pointers.  In particular, the
way semantics of comparison of pointers is defined in 6.5.8/5 does make
no reference to the difference of pointers, and it is well defined even
for objects whose size does not fit into ptrdiff_t.

Gcc actually does not allow arrays whose size does not fit into
ptrdiff_t, so the problem might only appear for malloc-ated objects.
But perhaps it is allowed to actually not support such large objects; I
think we should just submit patch for the transformation as described
below, and let someone with better knowledge of the standards decide
whether this is correct or not.

> So for this reason I believe that folding
> 
>   PTR +- CST  CMP  PTR +- CST
> 
> (with CST being of pointer type, as represented by the middle-end) as
> 
>   +- (ptrdiff_t)CST  CMP  +- (ptrdiff_t)CST
> 
> is valid.  Now the intel compiler f.i. does _not_ do this.


-- 


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

[Bug tree-optimization/27039] [4.1/4.2 Regression] Unable to determine # of iterations for a simple loop

[rguenth at gcc dot gnu dot org]

------- Comment #10 from rguenth at gcc dot gnu dot org  2006-05-10 14:56 -------
I have a patch that needs PR27529 fixed first, that needs PR27532 fixed first.


-- 


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

[Bug tree-optimization/27039] [4.1/4.2 Regression] Unable to determine # of iterations for a simple loop

[patchapp at dberlin dot org]

------- Comment #11 from patchapp at dberlin dot org  2006-05-15 14:44 -------
Subject: Bug number PR27039

A patch for this bug has been added to the patch tracker.
The mailing list url for the patch is
http://gcc.gnu.org/ml/gcc-patches/2006-05/msg00452.html


-- 


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

[Bug tree-optimization/27039] [4.1/4.2 Regression] Unable to determine # of iterations for a simple loop

[mmitchel at gcc dot gnu dot org]

------- Comment #12 from mmitchel at gcc dot gnu dot org  2006-05-25 02:34 -------
Will not be fixed in 4.1.1; adjust target milestone to 4.1.2.


-- 

mmitchel at gcc dot gnu dot org changed:

           What    |Removed                     |Added
----------------------------------------------------------------------------
   Target Milestone|4.1.1                       |4.1.2


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

[Bug tree-optimization/27039] [4.1/4.2 Regression] Unable to determine # of iterations for a simple loop

[rguenth at gcc dot gnu dot org]

------- Comment #13 from rguenth at gcc dot gnu dot org  2006-06-04 12:59 -------
Subject: Bug 27039

Author: rguenth
Date: Sun Jun  4 12:59:40 2006
New Revision: 114357

URL: http://gcc.gnu.org/viewcvs?root=gcc&view=rev&rev=114357
Log:
2006-06-04  Richard Guenther  <rguenther@suse.de>

        PR tree-optimization/27039
        * fold-const.c (fold_comparison): Handle pointer comparison
        again for all comparison codes.  Compare offsets in signed
        size type.
        (fold_binary): Move code from here.

        * gcc.dg/tree-ssa/loop-17.c: New testcase.

Added:
    trunk/gcc/testsuite/gcc.dg/tree-ssa/loop-17.c
Modified:
    trunk/gcc/ChangeLog
    trunk/gcc/fold-const.c
    trunk/gcc/testsuite/ChangeLog


-- 


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

[Bug tree-optimization/27039] [4.1 Regression] Unable to determine # of iterations for a simple loop

[rguenth at gcc dot gnu dot org]

------- Comment #14 from rguenth at gcc dot gnu dot org  2006-06-04 13:16 -------
Fixed on the mainline.


-- 

rguenth at gcc dot gnu dot org changed:

           What    |Removed                     |Added
----------------------------------------------------------------------------
            Summary|[4.1/4.2 Regression] Unable |[4.1 Regression] Unable to
                   |to determine # of iterations|determine # of iterations
                   |for a simple loop           |for a simple loop


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

[Bug tree-optimization/27039] [4.1 Regression] Unable to determine # of iterations for a simple loop

[rguenth at gcc dot gnu dot org]

-- 

rguenth at gcc dot gnu dot org changed:

           What    |Removed                     |Added
----------------------------------------------------------------------------
         AssignedTo|rguenth at gcc dot gnu dot  |unassigned at gcc dot gnu
                   |org                         |dot org
             Status|ASSIGNED                    |NEW


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

[Bug tree-optimization/27039] [4.1 Regression] Unable to determine # of iterations for a simple loop

[mmitchel at gcc dot gnu dot org]

-- 

mmitchel at gcc dot gnu dot org changed:

           What    |Removed                     |Added
----------------------------------------------------------------------------
   Target Milestone|4.1.2                       |4.1.3


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

[Bug tree-optimization/27039] [4.1 Regression] Unable to determine # of iterations for a simple loop

[jsm28 at gcc dot gnu dot org]

------- Comment #15 from jsm28 at gcc dot gnu dot org  2008-07-04 15:27 -------
Closing 4.1 branch.


-- 

jsm28 at gcc dot gnu dot org changed:

           What    |Removed                     |Added
----------------------------------------------------------------------------
             Status|NEW                         |RESOLVED
      Known to fail|                            |4.1.3
      Known to work|                            |4.2.0
         Resolution|                            |FIXED
   Target Milestone|4.1.3                       |4.2.0


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

[Bug tree-optimization/27039] [4.1 Regression] Unable to determine # of iterations for a simple loop

[rguenth at gcc dot gnu.org]

https://gcc.gnu.org/bugzilla/show_bug.cgi?id=27039
Bug 27039 depends on bug 27214, which changed state.

Bug 27214 Summary: The C frontend introduces undefined pointer overflow
https://gcc.gnu.org/bugzilla/show_bug.cgi?id=27214

           What    |Removed                     |Added
----------------------------------------------------------------------------
             Status|ASSIGNED                    |RESOLVED
         Resolution|---                         |FIXED