public inbox for gcc@gcc.gnu.org
 help / color / mirror / Atom feed
* Re: Bug in loop optimize (invalid postinc to preinc transformation)
@ 2000-12-31  8:30 dewar
  2001-01-03  0:52 ` Jamie Lokier
  0 siblings, 1 reply; 21+ messages in thread
From: dewar @ 2000-12-31  8:30 UTC (permalink / raw)
  To: egcs, schwab; +Cc: aoliva, denisc, dkorn, gcc, peter.osterlund

<<Comparing pointers that don't point to the same (part of) object is
undefined.
>>

Indeed. The important thing to remember in C is that the semantic
model of a pointer is a pair (pointer-to-object, offset). Address
arithmetic just modifies the offset, comparison compares only the
offsets (and is undefined if the pointer-to-object values are
different).

Of course in practice the implementation is typically a single pointer
from a flat space, representing the sum of the two components, but the
proper semantic model needs to be kept in mind, and code that does not
respect this semantic model has undefined effects.

As C compilers get more clever, they are likely to be less permissive
to abuses of the semantics :-)

^ permalink raw reply	[flat|nested] 21+ messages in thread

* Re: Bug in loop optimize (invalid postinc to preinc transformation)
  2000-12-31  8:30 Bug in loop optimize (invalid postinc to preinc transformation) dewar
@ 2001-01-03  0:52 ` Jamie Lokier
  0 siblings, 0 replies; 21+ messages in thread
From: Jamie Lokier @ 2001-01-03  0:52 UTC (permalink / raw)
  To: dewar; +Cc: schwab, aoliva, denisc, dkorn, gcc, peter.osterlund

dewar@gnat.com wrote:
> Indeed. The important thing to remember in C is that the semantic
> model of a pointer is a pair (pointer-to-object, offset). Address
> arithmetic just modifies the offset, comparison compares only the
> offsets (and is undefined if the pointer-to-object values are
> different).
> 
> Of course in practice the implementation is typically a single pointer
> from a flat space, representing the sum of the two components, but the
> proper semantic model needs to be kept in mind, and code that does not
> respect this semantic model has undefined effects.

The point (no pun intended) is that the problematic example code
includes a constant-valued pointer (unsigned char *) 0xffffffff.  Such a
pointer does not refer to any object unless your semantic model is a
flat space, in which all objects are sub-objects of a single "all of
memory" object.

> As C compilers get more clever, they are likely to be less permissive
> to abuses of the semantics :-)

Indeed.  As with strict type aliasing, as the compilers get more clever,
the programmers need clear definitions of which semantics they may rely
on from a particular compiler.  Many, many programs have a small part
that depends on traditional behaviour that's not defined in the ISO
standard.

-- Jamie

^ permalink raw reply	[flat|nested] 21+ messages in thread

* Re: Bug in loop optimize (invalid postinc to preinc transformation)
  2000-12-27 22:24     ` Jamie Lokier
@ 2000-12-31  8:25       ` Andreas Schwab
  0 siblings, 0 replies; 21+ messages in thread
From: Andreas Schwab @ 2000-12-31  8:25 UTC (permalink / raw)
  To: Jamie Lokier
  Cc: Alexandre Oliva, Peter Osterlund, David Korn,
	'Denis Chertykov',
	gcc

[-- Warning: decoded text below may be mangled, UTF-8 assumed --]
[-- Attachment #1: Type: text/plain, Size: 923 bytes --]

Jamie Lokier <egcs@tantalophile.demon.co.uk> writes:

|> Alexandre Oliva wrote:
|> > > Compiling without optimization indicates that the compiler is
|> > > transforming (p++ < x) into (++p < (x+1)), even when not optimizing.
|> > > This transformation is incorrect because x+1 wraps around.
|> > 
|> > Overflow invokes undefined behavior.  Since incrementing p in this
|> > case involves overflow, I think the transformation is ok, as far as
|> > undefined behavior goes.
|> 
|> Overflow of unsigned integers has defined behaviour -- they wrap.  The
|> question is, what rule applies to pointer comparisons?

Comparing pointers that don't point to the same (part of) object is
undefined.

Andreas.

-- 
Andreas Schwab                                  "And now for something
SuSE Labs                                        completely different."
Andreas.Schwab@suse.de
SuSE GmbH, Schanzäckerstr. 10, D-90443 Nürnberg

^ permalink raw reply	[flat|nested] 21+ messages in thread

* Re: Bug in loop optimize (invalid postinc to preinc transformation)
  2000-12-29 18:43 dewar
@ 2000-12-30 15:18 ` Toon Moene
  0 siblings, 0 replies; 21+ messages in thread
From: Toon Moene @ 2000-12-30 15:18 UTC (permalink / raw)
  To: dewar; +Cc: egcs, aoliva, denisc, dkorn, gcc, peter.osterlund

dewar@gnat.com wrote:

> <<Quite.  There's a pointer constant in the offending code.  It's not in
> any array.  Do we offer implementation defined behaviour for numerical
> pointer constants or not?  They do come in useful occasionally.
> >>

> It is hard NOT to offer implementation defined behavior :-)

Robert has spent too many hours in Standardization Committees.

Sorry, couldn't resist :-)

-- 
Toon Moene - mailto:toon@moene.indiv.nluug.nl - phoneto: +31 346 214290
Saturnushof 14, 3738 XG  Maartensdijk, The Netherlands
Maintainer, GNU Fortran 77: http://gcc.gnu.org/onlinedocs/g77_news.html
Join GNU Fortran 95: http://g95.sourceforge.net/ (under construction)

^ permalink raw reply	[flat|nested] 21+ messages in thread

* Re: Bug in loop optimize (invalid postinc to preinc transformation)
@ 2000-12-29 18:43 dewar
  2000-12-30 15:18 ` Toon Moene
  0 siblings, 1 reply; 21+ messages in thread
From: dewar @ 2000-12-29 18:43 UTC (permalink / raw)
  To: dewar, egcs; +Cc: aoliva, denisc, dkorn, gcc, peter.osterlund

<<Quite.  There's a pointer constant in the offending code.  It's not in
any array.  Do we offer implementation defined behaviour for numerical
pointer constants or not?  They do come in useful occasionally.
>>

It is hard NOT to offer implementation defined behavior :-)

I think you are asking if we provide easily defined useful behavior??

^ permalink raw reply	[flat|nested] 21+ messages in thread

* Re: Bug in loop optimize (invalid postinc to preinc transformation)
  2000-12-27 22:40 Robert Dewar
@ 2000-12-29 18:36 ` Jamie Lokier
  0 siblings, 0 replies; 21+ messages in thread
From: Jamie Lokier @ 2000-12-29 18:36 UTC (permalink / raw)
  To: Robert Dewar; +Cc: aoliva, denisc, dkorn, gcc, peter.osterlund

Robert Dewar wrote:
> <<Overflow of unsigned integers has defined behaviour -- they wrap.  The
> question is, what rule applies to pointer comparisons?
> >>
> 
> This is a malformed question. Any pointer increment is constrained 
> to require that the resulting pointer be valid. Wrapping is simply
> not an issue.
> 
> If p points to a valid address in an allocated array, then P+1 is also
> valid, and there is no question of wrap. But P+2 may be beyond the
> array and therefore ill-defined, and this has nothing to do with wrapping.

Quite.  There's a pointer constant in the offending code.  It's not in
any array.  Do we offer implementation defined behaviour for numerical
pointer constants or not?  They do come in useful occasionally.

-- Jamie

^ permalink raw reply	[flat|nested] 21+ messages in thread

* Re: Bug in loop optimize (invalid postinc to preinc transformation)
  2000-12-28 22:20       ` Dave Korn
  2000-12-29  0:52         ` Richard Henderson
@ 2000-12-29  1:51         ` Tim Hollebeek
  1 sibling, 0 replies; 21+ messages in thread
From: Tim Hollebeek @ 2000-12-29  1:51 UTC (permalink / raw)
  To: Dave Korn
  Cc: Tim Hollebeek, Geoff Keating, Alexandre Oliva, kenner, gcc, Robert Dewar

Dave Korn writes ...
> 
> ----- Original Message -----
> From: "Tim Hollebeek" <tim@hollebeek.com>
> Sent: Thursday, December 28, 2000 11:42 PM
> 
> > If pointers are implementation as unsigned offsets into a flat memory

s/implementation/implemented/

> > model, one of two things is true:
> 
>  Nope. Pointers are abstract types. The mere fact that the underlying
> implementation uses what are effectively 32 bit unsigned ints (which isn't
> even the case on segmented architectures) isn't relevant.

Read "If ..." as "Assuming ...".  So "Nope" isn't really a possible
response.  I intentionally restricted my post to an ISO C compiler on
a particular type of architecture and that implements pointers in a
particular way, in an attempt to point out that *even if* pointers are
(essentially) unsigned integers, the standard is written in such a way
that wrapping *still* isn't relevant.

Sorry if that wasn't clear.

(discussion of the abstract semantics deleted; you're preaching to the
choir here)

^ permalink raw reply	[flat|nested] 21+ messages in thread

* Re: Bug in loop optimize (invalid postinc to preinc transformation)
  2000-12-28 22:20       ` Dave Korn
@ 2000-12-29  0:52         ` Richard Henderson
  2000-12-29  1:51         ` Tim Hollebeek
  1 sibling, 0 replies; 21+ messages in thread
From: Richard Henderson @ 2000-12-29  0:52 UTC (permalink / raw)
  To: Dave Korn
  Cc: Tim Hollebeek, Geoff Keating, Alexandre Oliva, kenner, gcc, Robert Dewar

On Fri, Dec 29, 2000 at 06:18:26AM -0000, Dave Korn wrote:
> >int main(void) {
> >   do {
> >  i++;
> >  } while(p++<(unsigned char *)0xffffffff);
[...]
>   Now, what follows is from the n869 draft of the C9X standard....

All this is well and good, except that I don't believe
that it was ever claimed that this program was supposed
to be strictly conforming.

What is being lost sight of is that GCC is also used to 
develop programs in non-hosted situations.  In these
situations it is Known how the address space is shaped,
and we often do Very Nonconforming Things with addresses.

I don't see any particular reason why GCC should fail
this test.  It just makes things less useful.


r~

^ permalink raw reply	[flat|nested] 21+ messages in thread

* Re: Bug in loop optimize (invalid postinc to preinc transformation)
  2000-12-28 15:22     ` Tim Hollebeek
@ 2000-12-28 22:20       ` Dave Korn
  2000-12-29  0:52         ` Richard Henderson
  2000-12-29  1:51         ` Tim Hollebeek
  0 siblings, 2 replies; 21+ messages in thread
From: Dave Korn @ 2000-12-28 22:20 UTC (permalink / raw)
  To: Tim Hollebeek, Geoff Keating; +Cc: Alexandre Oliva, kenner, gcc, Robert Dewar

----- Original Message -----
From: "Tim Hollebeek" <tim@hollebeek.com>
Sent: Thursday, December 28, 2000 11:42 PM

> If pointers are implementation as unsigned offsets into a flat memory
> model, one of two things is true:

 Nope. Pointers are abstract types. The mere fact that the underlying
implementation uses what are effectively 32 bit unsigned ints (which isn't
even the case on segmented architectures) isn't relevant. A pointer is an
abstract type with semantics and behaviour defined by the C language
standard, and just because a 32 bit int works one way, a pointer doesn't
have to, even though it may be implemented using them.

> Case 1:
> 0x00000000 is the null pointer.  Therefore it isn't within a valid
> object, and is not immediately following a valid array.
>
> >>>THEREFORE WRAPPING IS IRRELEVANT<<< since no valid pointer
> increment or operation can cross the boundary.
>
> Case 2:
>
> 0x00000000 is within a valid object, or immediately follows an array.
> In this case, 0x00000000 cannot be the null pointer, so some other
> value (__null) is.  Overflow isn't an issue since if all computations
> on unsigned pointer values involve first subtracting __null (using
> unsigned arithmetic; wrapping is well defined here) from each pointer,
> than adding it back in when necessary, we reduce to case 1.

  The unstated assumption here is that pointers, like ints, have a well
defined behaviour (wrapping round, in the case of ints) when adding 1.
However pointer arithmetic is not integer arithmetic. Remember that
(((char *)(arbitraryvalue)) + 1) != (((double *)(arbitraryvalue) + 1), so
I think that you first have to show that IF ptr == (T *)0xffffffff  THEN
(ptr+1) == (T *)0. And I don't think you can assume that.

  Anyway, let's look at the original source code again:

>volatile unsigned char *p;
>volatile unsigned char i;

  Ok, I accept that these variables are indeed init'ed to zero! There's
always an 'if' or 'but' in the c spec somewhere that I forget about!

>int main(void) {
>   do {
>  i++;
>  } while(p++<(unsigned char *)0xffffffff);
> /* if 0xffffffff change to 0xfffffffe then no bug */
>  return 0;
>}

  Now, what follows is from the n869 draft of the C9X standard. Let's see
in just how many ways the behaviour of this program may be undefined or
unspecified. The first thing I'm going to attack is the comparison
operation.  From section 6.5.8: Relational operators:

>    4 For the purposes of these operators, a pointer to a nonarray object
behaves the same as a pointer to the first element of an array of length
one with the type of the object as its
element type.

>    5 When two pointers are compared, the result depends on the relative
locations in the address space of the objects pointed to. If two pointers
to object or incomplete types both point to the same object, or both point
one past the last element of the same array object, they compare equal. If
the objects pointed to are members of the same aggregate object, pointers
to structure members declared later compare greater than pointers to
members declared earlier in the structure, and pointers to array elements
with larger subscript values compare greater than pointers to elements of
the same array with lower subscript values. All pointers to members of the
same union object compare equal. If the expression P points to an element
of an array object and the expression Q points to the last element of the
same array object, the pointer expression Q+1 compares greater than P. In
all other cases, the behavior is undefined.

  And from 6.3.2.3: Pointers, we have -

>    3 An integer constant expression with the value 0, or such an
expression cast to type void *, is called a null pointer constant. If a
null pointer constant is converted to a pointer type, the resulting
pointer, called a null pointer, is guaranteed to compare unequal to a
pointer to any object or function.

  Now, it seems to me that when this loop first executes, p is the NULL
pointer: I believe it is guaranteed that the zero-initialisation of static
storage class variables will provide correctly zero values for both floats
and pointers, n'est-ce pas? (6.7.8 #10, I won't quote it now.) And the
pointer derived from the cast operation behaves as a pointer to an array
of one char, mais oui? So: do they both point to the same object? Clearly
not: NULL points to no object at all. Do they both point one past the last
element of the same array? Nope, they don't: otherwise there would be a
valid pointer that compared equal to NULL. Do they point to members of the
same aggregate, array or union? Nope, to be brief. Does one point to an
array and the other to one past the last entry in that same array? Also,
nope. So there you have it: undefined behaviour. The only way in which
NULL may be used in a pointer comparison is with != or ==, which
specifically allow it.

  OK, what about that postincrement? Let's check 6.5.6: Additive
operators.

>    7 For the purposes of these operators, a pointer to a nonarray object
behaves the same as a pointer to the first element of an array of length
one with the type of the object as its element type.

>    8 When an expression that has integer type is added to or subtracted
from a pointer, the result has the type of the pointer operand. If the
pointer operand points to an element of an array object, and the array is
large enough, the result points to an element offset from the original
element such that the difference of the subscripts of the resulting and
original array elements equals the integer expression. In other words, if
the expression P points to the i-th element of an array object, the
expressions (P)+N (equivalently, N+(P)) and (P)-N (where N has the value
n) point to, respectively, the i+n-th and i?n-th elements of the array
object, provided they exist. Moreover, if the expression P points to the
last element of an array object, the expression (P)+1 points one past the
last element of the array object, and if the expression Q points one past
the last element of an array object, the expression (Q)-1 points to the
last element of the array object. If both the pointer operand and the
result point to elements of the same array object, or one past the last
element of the array object, the evaluation shall not produce an overflow;
otherwise, the behavior is undefined. If the result points one past the
last element of the array object, it shall not be used as the operand of a
unary * operator that is evaluated.

  Let us consider, since after all it could happen (undefined behaviour is
a bit like that) that the comparison operator does indeed work exactly as
if it treated the two pointers as unsigned ints of the same bitsize. Then
the loop would run round and round until eventually we get to the top of
the loop with p == (char *)0xffffffff. It increments i and then tries to
evaluate the do ... while () condition. Is it legal to apply post
increment to the pointer at this stage? p is a char *, so under #7 it is
effectively pointing to the first element of an array of length one. So
the first part of #8 fails; since the array is of size 1, it's not big
enough to point at another element 1 past the first. (Hold it! I haven't
forgotten about "one past" yet, I'm just saying that pointers to
one-past-the-array-end don't point to an element of the array, even though
they are valid pointers. To support this thesis, I point out that such
pointers are valid for comparisons and arithmetic, but invalid to
dereference.) In the second part of the clause, we certainly have to
accept that the pointer P points to the last element of the array object,
since the array is of size 1 according to #7. So apparently the expression
(P)+1 must point one past the last element. If the maths is done by
integer maths rules, the expression (P+1) is evaluated to have the same
value (and representation) as NULL, and so cannot be a valid pointer.

  I think we should conclude from all this that a) the original code
exhibits undefined behaviour b) to be ANSI conforming, a compiler that
works with pointers based on 32 bit integer arithmetic must be sure never
to allocate any array or object that occupies address 0xFFFFFFFF.

> Either way, wrapping is well-defined/irrelevant.  Optimization must
> just preserve the correct semantics.  If an optimization causes values
> to be used which might overflow or cause other problems when the
> original values would not, then that's a bad optimization.  But this
> has nothing to do with "pointer wrapping" or "pointers being unsigned"
> or any other such nonsense.  It's just a bad optimization.

  Ah, but this is the whole point of undefined behaviour: it's not defined
because it's accepted that the compiler can't practically be expected to
produce correct code for all the possible dodgy constructs. There is NO
onus on a compiler to produce valid code for a program which invokes
undefined behaviour. In pracise, this means that people writing
optimization code don't need to worry about taking care of cases that
could only occur if the program has invalid behaviour. That's why the
optimization doesn't need to worry about the danger of wrapping round the
constant when it increments it, because the only time this could make a
difference is when we've done something wrong already.

           DaveK



^ permalink raw reply	[flat|nested] 21+ messages in thread

* Re: Bug in loop optimize (invalid postinc to preinc transformation)
@ 2000-12-28 20:33 dewar
  0 siblings, 0 replies; 21+ messages in thread
From: dewar @ 2000-12-28 20:33 UTC (permalink / raw)
  To: aoliva, dewar; +Cc: gcc, kenner

<<Only if the compiler guarantees that no array will ever be placed
across the wrapping boundary.
>>

I don't understand, pointer incrementation must work through an array
regardless. Wrapping is simply not a semantically relevant notion when
it comes to pointers.

^ permalink raw reply	[flat|nested] 21+ messages in thread

* Re: Bug in loop optimize (invalid postinc to preinc transformation)
  2000-12-28 14:32   ` Geoff Keating
@ 2000-12-28 15:22     ` Tim Hollebeek
  2000-12-28 22:20       ` Dave Korn
  0 siblings, 1 reply; 21+ messages in thread
From: Tim Hollebeek @ 2000-12-28 15:22 UTC (permalink / raw)
  To: Geoff Keating; +Cc: Alexandre Oliva, kenner, gcc, Robert Dewar

Geoff Keating writes ...
> 
> Since 0 is not a valid pointer---that is, no pointer to an object
> should ever compare equal to 0---

Please, everyone, be careful with your language.

0 is not a valid pointer because it isn't a pointer.  It's an integral
constant.

Another possible interpretation is that you meant a pointer with
representation all bits zero.  If the null pointer has that
representation, then no valid pointer can have it.  So you're saying
(essentially) is "the all bits zero pointer is the null pointer, which
points to nothing --- no pointer to an object can ever have that
representation".  True, given the assumption that the all bits zero
pointer is the null pointer.

Yet another possible interpretation of '0' in both halves is that
you meant a null pointer constant which is what the integral constant
0 becomes when converted to a pointer.

If that's what you meant then what you said is "a null pointer isn't
non-null --- that is, no non-null pointer should ever compare equal to
a null pointer constant".  True in all cases, but rather unprofound.

No "valid" pointer can compare equal to a null pointer, but this says
nothing about the representation of pointers.  The null pointer need
not be represented by "all bits zero", and all bits zero may be a
valid pointer on some architectures.

> this makes pointers a case of unsigned integers for which overflow
is not permitted.

This doesn't follow at all.

If pointers are implementation as unsigned offsets into a flat memory
model, one of two things is true:

Case 1:
0x00000000 is the null pointer.  Therefore it isn't within a valid
object, and is not immediately following a valid array.  

>>>THEREFORE WRAPPING IS IRRELEVANT<<< since no valid pointer
increment or operation can cross the boundary.

Case 2: 

0x00000000 is within a valid object, or immediately follows an array.
In this case, 0x00000000 cannot be the null pointer, so some other
value (__null) is.  Overflow isn't an issue since if all computations
on unsigned pointer values involve first subtracting __null (using
unsigned arithmetic; wrapping is well defined here) from each pointer,
than adding it back in when necessary, we reduce to case 1.

Either way, wrapping is well-defined/irrelevant.  Optimization must
just preserve the correct semantics.  If an optimization causes values
to be used which might overflow or cause other problems when the
original values would not, then that's a bad optimization.  But this
has nothing to do with "pointer wrapping" or "pointers being unsigned"
or any other such nonsense.  It's just a bad optimization.

^ permalink raw reply	[flat|nested] 21+ messages in thread

* Re: Bug in loop optimize (invalid postinc to preinc transformation)
  2000-12-28 12:21 ` Alexandre Oliva
@ 2000-12-28 14:32   ` Geoff Keating
  2000-12-28 15:22     ` Tim Hollebeek
  0 siblings, 1 reply; 21+ messages in thread
From: Geoff Keating @ 2000-12-28 14:32 UTC (permalink / raw)
  To: Alexandre Oliva; +Cc: Robert Dewar

Alexandre Oliva <aoliva@redhat.com> writes:

> On Dec 28, 2000, dewar@gnat.com (Robert Dewar) wrote:
> 
> > then this is defined only if the resulting pointer remains within the
> > same object, or in the csae of arrays it can go just past the end. Overflow
> > per se does not arise with pointers because of this stricter rule.
> 
> Only if the compiler guarantees that no array will ever be placed
> across the wrapping boundary.

Since 0 is not a valid pointer---that is, no pointer to an object
should ever compare equal to 0---this makes pointers a case of
unsigned integers for which overflow is not permitted.

I know that there are 32-bit architectures on which GCC runs in which
it's perfectly possible that an array will be placed across
0x80000000.

-- 
- Geoffrey Keating <geoffk@geoffk.org>

^ permalink raw reply	[flat|nested] 21+ messages in thread

* Re: Bug in loop optimize (invalid postinc to preinc transformation)
  2000-12-28  5:40 Robert Dewar
@ 2000-12-28 12:21 ` Alexandre Oliva
  2000-12-28 14:32   ` Geoff Keating
  0 siblings, 1 reply; 21+ messages in thread
From: Alexandre Oliva @ 2000-12-28 12:21 UTC (permalink / raw)
  To: Robert Dewar; +Cc: kenner, gcc

On Dec 28, 2000, dewar@gnat.com (Robert Dewar) wrote:

> then this is defined only if the resulting pointer remains within the
> same object, or in the csae of arrays it can go just past the end. Overflow
> per se does not arise with pointers because of this stricter rule.

Only if the compiler guarantees that no array will ever be placed
across the wrapping boundary.

-- 
Alexandre Oliva   Enjoy Guarana', see http://www.ic.unicamp.br/~oliva/
Red Hat GCC Developer                  aoliva@{cygnus.com, redhat.com}
CS PhD student at IC-Unicamp        oliva@{lsd.ic.unicamp.br, gnu.org}
Free Software Evangelist    *Please* write to mailing lists, not to me

^ permalink raw reply	[flat|nested] 21+ messages in thread

* Re: Bug in loop optimize (invalid postinc to preinc transformation)
@ 2000-12-28  5:40 Robert Dewar
  2000-12-28 12:21 ` Alexandre Oliva
  0 siblings, 1 reply; 21+ messages in thread
From: Robert Dewar @ 2000-12-28  5:40 UTC (permalink / raw)
  To: aoliva, kenner; +Cc: gcc

<<The implementation of pointers is indeed unsigned on most machines,but
they are not "unsigned types", which would mean integral unsigned types.
So overflow is indeed undefined.
>>

Once again, this is confused.

If you increment a pointer

p++;

then this is defined only if the resulting pointer remains within the
same object, or in the csae of arrays it can go just past the end. Overflow
per se does not arise with pointers because of this stricter rule.

No optimization of pointer arithmetic can possibly be correct if it does
not preserve this fundamental semantic appearence.

^ permalink raw reply	[flat|nested] 21+ messages in thread

* Re: Bug in loop optimize (invalid postinc to preinc transformation)
@ 2000-12-28  1:14 Richard Kenner
  0 siblings, 0 replies; 21+ messages in thread
From: Richard Kenner @ 2000-12-28  1:14 UTC (permalink / raw)
  To: aoliva; +Cc: gcc

    > Overflow of *unsigned* types is well-defined.  

    Indeed.  But I don't think pointers are unsigned by default, are they?

The implementation of pointers is indeed unsigned on most machines,but
they are not "unsigned types", which would mean integral unsigned types.
So overflow is indeed undefined.

^ permalink raw reply	[flat|nested] 21+ messages in thread

* Re: Bug in loop optimize (invalid postinc to preinc transformation)
@ 2000-12-27 22:40 Robert Dewar
  2000-12-29 18:36 ` Jamie Lokier
  0 siblings, 1 reply; 21+ messages in thread
From: Robert Dewar @ 2000-12-27 22:40 UTC (permalink / raw)
  To: aoliva, egcs; +Cc: denisc, dkorn, gcc, peter.osterlund

<<Overflow of unsigned integers has defined behaviour -- they wrap.  The
question is, what rule applies to pointer comparisons?
>>

This is a malformed question. Any pointer increment is constrained 
to require that the resulting pointer be valid. Wrapping is simply
not an issue.

If p points to a valid address in an allocated array, then P+1 is also
valid, and there is no question of wrap. But P+2 may be beyond the
array and therefore ill-defined, and this has nothing to do with wrapping.

^ permalink raw reply	[flat|nested] 21+ messages in thread

* Re: Bug in loop optimize (invalid postinc to preinc transformation)
  2000-12-27 19:55   ` Alexandre Oliva
  2000-12-27 21:09     ` Torbjorn Granlund
@ 2000-12-27 22:24     ` Jamie Lokier
  2000-12-31  8:25       ` Andreas Schwab
  1 sibling, 1 reply; 21+ messages in thread
From: Jamie Lokier @ 2000-12-27 22:24 UTC (permalink / raw)
  To: Alexandre Oliva
  Cc: Peter Osterlund, David Korn, 'Denis Chertykov', gcc

Alexandre Oliva wrote:
> > Compiling without optimization indicates that the compiler is
> > transforming (p++ < x) into (++p < (x+1)), even when not optimizing.
> > This transformation is incorrect because x+1 wraps around.
> 
> Overflow invokes undefined behavior.  Since incrementing p in this
> case involves overflow, I think the transformation is ok, as far as
> undefined behavior goes.

Overflow of unsigned integers has defined behaviour -- they wrap.  The
question is, what rule applies to pointer comparisons?

-- Jamie

^ permalink raw reply	[flat|nested] 21+ messages in thread

* Re: Bug in loop optimize (invalid postinc to preinc transformation)
  2000-12-27 21:09     ` Torbjorn Granlund
@ 2000-12-27 21:20       ` Alexandre Oliva
  0 siblings, 0 replies; 21+ messages in thread
From: Alexandre Oliva @ 2000-12-27 21:20 UTC (permalink / raw)
  To: Torbjorn Granlund
  Cc: Peter Osterlund, David Korn, 'Denis Chertykov', gcc

On Dec 28, 2000, Torbjorn Granlund <tege@swox.com> wrote:

> Alexandre Oliva <aoliva@redhat.com> writes:
>   On Dec 27, 2000, Peter Osterlund <peter.osterlund@mailbox.swipnet.se> wrote:
  
>> Compiling without optimization indicates that the compiler is
>> transforming (p++ < x) into (++p < (x+1)), even when not optimizing.
>> This transformation is incorrect because x+1 wraps around.
  
>   Overflow invokes undefined behavior.  Since incrementing p in this
>   case involves overflow, I think the transformation is ok, as far as
>   undefined behavior goes.
  
> Overflow of *unsigned* types is well-defined.  

Indeed.  But I don't think pointers are unsigned by default, are they?

-- 
Alexandre Oliva   Enjoy Guarana', see http://www.ic.unicamp.br/~oliva/
Red Hat GCC Developer                  aoliva@{cygnus.com, redhat.com}
CS PhD student at IC-Unicamp        oliva@{lsd.ic.unicamp.br, gnu.org}
Free Software Evangelist    *Please* write to mailing lists, not to me

^ permalink raw reply	[flat|nested] 21+ messages in thread

* Re: Bug in loop optimize (invalid postinc to preinc transformation)
  2000-12-27 19:55   ` Alexandre Oliva
@ 2000-12-27 21:09     ` Torbjorn Granlund
  2000-12-27 21:20       ` Alexandre Oliva
  2000-12-27 22:24     ` Jamie Lokier
  1 sibling, 1 reply; 21+ messages in thread
From: Torbjorn Granlund @ 2000-12-27 21:09 UTC (permalink / raw)
  To: Alexandre Oliva
  Cc: Peter Osterlund, David Korn, 'Denis Chertykov', gcc

[-- Warning: decoded text below may be mangled, UTF-8 assumed --]
[-- Attachment #1: Type: text/plain, Size: 566 bytes --]

Alexandre Oliva <aoliva@redhat.com> writes:

  On Dec 27, 2000, Peter Osterlund <peter.osterlund@mailbox.swipnet.se> wrote:
  
  > Compiling without optimization indicates that the compiler is
  > transforming (p++ < x) into (++p < (x+1)), even when not optimizing.
  > This transformation is incorrect because x+1 wraps around.
  
  Overflow invokes undefined behavior.  Since incrementing p in this
  case involves overflow, I think the transformation is ok, as far as
  undefined behavior goes.
  
Overflow of *unsigned* types is well-defined.  

-- 
Torbjörn

^ permalink raw reply	[flat|nested] 21+ messages in thread

* Re: Bug in loop optimize (invalid postinc to preinc transformation)
  2000-12-27 15:42 ` Bug in loop optimize (invalid postinc to preinc transformation) Peter Osterlund
@ 2000-12-27 19:55   ` Alexandre Oliva
  2000-12-27 21:09     ` Torbjorn Granlund
  2000-12-27 22:24     ` Jamie Lokier
  0 siblings, 2 replies; 21+ messages in thread
From: Alexandre Oliva @ 2000-12-27 19:55 UTC (permalink / raw)
  To: Peter Osterlund; +Cc: David Korn, 'Denis Chertykov', gcc

On Dec 27, 2000, Peter Osterlund <peter.osterlund@mailbox.swipnet.se> wrote:

> Compiling without optimization indicates that the compiler is
> transforming (p++ < x) into (++p < (x+1)), even when not optimizing.
> This transformation is incorrect because x+1 wraps around.

Overflow invokes undefined behavior.  Since incrementing p in this
case involves overflow, I think the transformation is ok, as far as
undefined behavior goes.

-- 
Alexandre Oliva   Enjoy Guarana', see http://www.ic.unicamp.br/~oliva/
Red Hat GCC Developer                  aoliva@{cygnus.com, redhat.com}
CS PhD student at IC-Unicamp        oliva@{lsd.ic.unicamp.br, gnu.org}
Free Software Evangelist    *Please* write to mailing lists, not to me

^ permalink raw reply	[flat|nested] 21+ messages in thread

* Re: Bug in loop optimize (invalid postinc to preinc transformation)
  2000-12-27  3:04 Bug in loop optimize (TREE stage) David Korn
@ 2000-12-27 15:42 ` Peter Osterlund
  2000-12-27 19:55   ` Alexandre Oliva
  0 siblings, 1 reply; 21+ messages in thread
From: Peter Osterlund @ 2000-12-27 15:42 UTC (permalink / raw)
  To: David Korn; +Cc: 'Denis Chertykov', gcc

[-- Warning: decoded text below may be mangled, UTF-8 assumed --]
[-- Attachment #1: Type: text/plain, Size: 1741 bytes --]

David Korn <dkorn@pixelpower.com> writes:

> >-----Original Message-----
> >From: Denis Chertykov [ mailto:denisc@overta.ru ]
> >Sent: 26 December 2000 20:06
> 
> >"Alexander Popov" <sasho@vip.orbitel.bg> have founded a bug in generic
> >GCC code.
> >I have tried  avr and x86 ports.
> >
> >The XXX.rtl file already have a bug.
> >
> >
> >volatile unsigned char *p;
> >volatile unsigned char i;
> >
> >int main(void) {
> >
> >   do {
> >   	i++;
> >   } while(p++<(unsigned char *)0xffffffff);
> >  /* if 0xffffffff change to 0xfffffffe then no bug */
> >   return 0;
> >}
> 
>   This is undefined behaviour. Since you haven't initialised variable p,
> the compiler is free to implement whatever it likes here. In particular,

No it is not. The p and i variables have static storage, so they are
implicitly initialized to 0. (As expected, even if you explicitly
initialize the variables, the bug doesn't go away.)

Compiling without optimization indicates that the compiler is
transforming (p++ < x) into (++p < (x+1)), even when not optimizing.
This transformation is incorrect because x+1 wraps around. At -O1 the
compiler realizes that testing for <0 will always fail and therefore
the test is removed, resulting in the assembly code below.

(This bug also exists in gcc 2.95 and egcs 1.1.2)

> >.globl main
> >	.type	main,@function
> >main:
> >	movb	i, %al
> >	pushl	%ebp
> >	incl	%eax
> >	movl	%esp, %ebp
> >	incl	p
> >	movb	%al, i
> >	xorl	%eax, %eax
> >	popl	%ebp
> >	ret

-- 
Peter Österlund          Email:     peter.osterlund@mailbox.swipnet.se
Sköndalsvägen 35                    f90-pos@nada.kth.se
S-128 66 Sköndal         Home page: http://home1.swipnet.se/~w-15919
Sweden                   Phone:     +46 8 942647

^ permalink raw reply	[flat|nested] 21+ messages in thread

end of thread, other threads:[~2001-01-03  0:52 UTC | newest]

Thread overview: 21+ messages (download: mbox.gz / follow: Atom feed)
-- links below jump to the message on this page --
2000-12-31  8:30 Bug in loop optimize (invalid postinc to preinc transformation) dewar
2001-01-03  0:52 ` Jamie Lokier
  -- strict thread matches above, loose matches on Subject: below --
2000-12-29 18:43 dewar
2000-12-30 15:18 ` Toon Moene
2000-12-28 20:33 dewar
2000-12-28  5:40 Robert Dewar
2000-12-28 12:21 ` Alexandre Oliva
2000-12-28 14:32   ` Geoff Keating
2000-12-28 15:22     ` Tim Hollebeek
2000-12-28 22:20       ` Dave Korn
2000-12-29  0:52         ` Richard Henderson
2000-12-29  1:51         ` Tim Hollebeek
2000-12-28  1:14 Richard Kenner
2000-12-27 22:40 Robert Dewar
2000-12-29 18:36 ` Jamie Lokier
2000-12-27  3:04 Bug in loop optimize (TREE stage) David Korn
2000-12-27 15:42 ` Bug in loop optimize (invalid postinc to preinc transformation) Peter Osterlund
2000-12-27 19:55   ` Alexandre Oliva
2000-12-27 21:09     ` Torbjorn Granlund
2000-12-27 21:20       ` Alexandre Oliva
2000-12-27 22:24     ` Jamie Lokier
2000-12-31  8:25       ` Andreas Schwab

This is a public inbox, see mirroring instructions
for how to clone and mirror all data and code used for this inbox;
as well as URLs for read-only IMAP folder(s) and NNTP newsgroup(s).