[Bug c/61502] New: == comparison on "one-past" pointer gives wrong result

[Bug c/61502] New: == comparison on "one-past" pointer gives wrong result

[Peter.Sewell at cl dot cam.ac.uk]

https://gcc.gnu.org/bugzilla/show_bug.cgi?id=61502

            Bug ID: 61502
           Summary: == comparison on "one-past" pointer gives wrong result
           Product: gcc
           Version: 4.8.1
            Status: UNCONFIRMED
          Severity: normal
          Priority: P3
         Component: c
          Assignee: unassigned at gcc dot gnu.org
          Reporter: Peter.Sewell at cl dot cam.ac.uk

Created attachment 32934
  --> https://gcc.gnu.org/bugzilla/attachment.cgi?id=32934&action=edit
C code as pasted into bug report

The following code can produce a pointer to one-past the x object.  When it
does, according to the C11 standard text, the result of the pointer comparison
should be true, but gcc gives false.

#include <stdio.h> 
int  y = 2, x=1; 
int main()
{
  int *p;
  p = &x +1 ;  
  printf("&x=%p  &y=%p  p=%p\n",(void*)&x, (void*)&y, (void*)p); 
  _Bool b1 = (p==&y);   
  printf("(p==&y) = %s\n", b1?"true":"false");
  return 0;
}

gcc-4.8 -std=c11 -pedantic -Wall -Wextra -O2 -o a.out
pointer_representation_1e.c && ./a.out
&x=0x601020  &y=0x601024  p=0x601024
(p==&y) = false

gcc-4.8 --version
gcc-4.8 (Ubuntu 4.8.1-2ubuntu1~12.04) 4.8.1

The pointer addition is licensed by 6.5.6 "Additive operators", where:

6.5.6p7 says "For the purposes of these operators, a pointer to an object that
is not an element of an array 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.", and 

6.5.6p8 says "[...] 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 [...]".

The pointer comparison is licensed by 6.5.9 "Equality operators", where:

6.5.9p7 says "For the purposes of these operators, a pointer to an object that
is not an element of an array 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.",

6.5.9p6 says "Two pointers compare equal if and only if [...] or one is a
pointer to one past the end of one array object and the other is a pointer to
the start of a different array object that happens to immediately follow the
first array object in the address space.109)", and

Footnote 109 says "Two objects may be adjacent in memory because they are
adjacent elements of a larger array or adjacent members of a structure with no
padding between them, or because the implementation chose to place them so,
even though they are unrelated. [...]".

[Bug c/61502] == comparison on "one-past" pointer gives wrong result

[joseph at codesourcery dot com]

https://gcc.gnu.org/bugzilla/show_bug.cgi?id=61502

--- Comment #1 from joseph at codesourcery dot com <joseph at codesourcery dot com> ---
Just because two pointers print the same and have the same bit-pattern 
doesn't mean they need to compare equal (see the response to DR#260, which 
may be presumed to apply to C11 in the absence of relevant textual changes 
to make it not apply).

[Bug c/61502] == comparison on "one-past" pointer gives wrong result

[joseph at codesourcery dot com]

https://gcc.gnu.org/bugzilla/show_bug.cgi?id=61502

--- Comment #3 from joseph at codesourcery dot com <joseph at codesourcery dot com> ---
Except within a larger object, I'm not aware of any reason the cases of 
two objects following or not following each other in memory must be 
mutually exclusive.  (If the implementation can track the origins of 
bit-patterns and where copies of those bit-patterns have got to, it might 
have a compacting garbage collector that relocates objects and changes 
what's adjacent to what, for example - I think such implementations are 
within the scope of what the C standard is intended to support.  Or if 
you're concerned about how this changes bit-patterns of pointers, imagine 
that a C pointer is a (object key, offset) pair, and that comparison first 
converts the C pointer into a hardware address, where it's the mapping 
from object keys to hardware addresses that changes as a result of garbage 
collection rather than anything about the representation of the pointer.)

So the only way within the C standard you could deduce that two objects 
follow each other in memory is that the address of one compares equal to 
one past the address of the other - but that does not mean they follow 
each other in memory for any other comparison.

An object having a constant address (6.2.4#2) is described non-normatively 
in footnote 33 in terms of comparisons of pointers to that object.  I 
don't think it should be taken to mean comparisons of pointers to 
different objects need to have constant results.

[Bug c/61502] == comparison on "one-past" pointer gives wrong result

[harald at gigawatt dot nl]

https://gcc.gnu.org/bugzilla/show_bug.cgi?id=61502

--- Comment #4 from Harald van Dijk <harald at gigawatt dot nl> ---
That's an interesting argument. You may well be right that the original code,
strictly speaking, does not prove that GCC has a bug, but I do think GCC has a
bug nonetheless, and have come up with a different example.

#include <stdio.h>
#include <string.h>

int x, y;

char buf[sizeof (int *)];

int main()
{
  int *p = &y;
  memcpy (buf, &p, sizeof p);
  memcpy (&p, buf, sizeof p);
  x = 2, y = 1;
  if (p == &x + 1)
    *p = 2;
  else
    y = 2;
  printf ("x = %d, y = %d\n", x, y);
  return 0;
}

Compiling with -O2, I see "x = 2, y = 1". p has been assigned &y. Whether it
compares equal to &x + 1 is unspecified, but it doesn't change its origins: p
points to y. Therefore, either the assignment to *p should change y, or in the
else branch, the plain assignment to y should change y. Either way, the correct
result is "x = 2, y = 2".

It seems like GCC is assuming that if p == &x + 1, and &x + 1 != &y, then p !=
&y, so the assignment to *p cannot change y. The flaw in that logic is again
the optimisation of &x + 1 != &y to a constant.

I see the behaviour I describe in versions 4.9.0 and 4.8.2. This program does
print "x = 2, y = 2" in my testing on GCC 4.7.3, but that is because p == &x +
1 happens to not compare as true in that version. Slightly tweaked versions of
this fail with versions 4.7.3, 4.6.4, 4.5.4 and 4.4.7, but not 4.3.6.

[Bug tree-optimization/61502] == comparison on "one-past" pointer gives wrong result

[jsm28 at gcc dot gnu.org]

https://gcc.gnu.org/bugzilla/show_bug.cgi?id=61502

Joseph S. Myers <jsm28 at gcc dot gnu.org> changed:

           What    |Removed                     |Added
----------------------------------------------------------------------------
                 CC|                            |Keith.S.Thompson at gmail dot com

--- Comment #5 from Joseph S. Myers <jsm28 at gcc dot gnu.org> ---
*** Bug 63611 has been marked as a duplicate of this bug. ***

[Bug tree-optimization/61502] == comparison on "one-past" pointer gives wrong result

[Keith.S.Thompson at gmail dot com]

https://gcc.gnu.org/bugzilla/show_bug.cgi?id=61502

--- Comment #6 from Keith Thompson <Keith.S.Thompson at gmail dot com> ---
In the test case for Bug 63611 (marked as a duplicate of this one)
we have:

    element x[1];
    element y[1];
    element *const x0 = x;
    element *const x1 = x0 + 1;
    element *const y0 = y;

When the test case is executed, the condition (x1 == y0) is true
when it's evaluated, but the condition (x + 1 == y) (which I argue is
equivalent) is false when it's evaluated 2 lines later.

I don't believe that DR#260 applies, since there are no indeterminate
values being used here.  Which means, I think, that N1570 6.2.4p2:

    An object exists, has a constant address, and retains its
    last-stored value throughout its lifetime.

does apply.

Whether x follows y or y follows x in memory, or neither, is 
unimportant.  The problem is that the "==" comparison is behaving
inconsistently for the same two pointer values.

I'm unconvinced by the argument (if I understand it correctly) that 
the objects x and y might be adjacent when the first comparison is
evaluated, but not when the second is evaluated.  I believe that would
violate the requirement that objects have constant addresses and retain
their last-stored values.  Furthermore, even if relocating objects so
they're no long adjacent is permitted by the language, I don't believe
gcc (or the code that it generates) is actually doing so in this case.

[Bug tree-optimization/61502] == comparison on "one-past" pointer gives wrong result

[joseph at codesourcery dot com]

https://gcc.gnu.org/bugzilla/show_bug.cgi?id=61502

--- Comment #7 from joseph at codesourcery dot com <joseph at codesourcery dot com> ---
On Tue, 21 Oct 2014, Keith.S.Thompson at gmail dot com wrote:

> their last-stored values.  Furthermore, even if relocating objects so
> they're no long adjacent is permitted by the language, I don't believe
> gcc (or the code that it generates) is actually doing so in this case.

Really, it's a bad idea to apply concepts such as "actually doing so" to 
understanding the semantics of C, specified as a high-level language.  
"happens to immediately follow the first array object in the address 
space" in the high-level language need not satisfy any particular rules 
you might expect from thinking of C as relating to particular hardware, 
only the rules that can be deduced from the C standard (which as far as I 
can tell, do not say that "follows" is constant just because the addresses 
of the two objects in question are constant - or anything else such as 
that you can't have x + 1 == y and y + 1 == x, which you might expect from 
relating things to hardware rather than to standard requirements).

[Bug tree-optimization/61502] == comparison on "one-past" pointer gives wrong result

[Keith.S.Thompson at gmail dot com]

https://gcc.gnu.org/bugzilla/show_bug.cgi?id=61502

--- Comment #8 from Keith Thompson <Keith.S.Thompson at gmail dot com> ---
I'm not (deliberately) considering anything other than the requirements
of the C standard.

The standard talks about an array object immediately following another
array object in the address space. Since that phrase is used in
normative wording in the standard, I presume it's meaningful.  Since
the term is not otherwise defined, I presume that the intended meaning
is one that follows reasonably clearly from the wording.

The test program for Bug 63611, when I execute it, prints the string
"y immediately follows x", followed by the string "inconsistent behavior:".

Are you saying it's possible that y immediately follows x in the
address space when that line of output is printed, and that y *doesn't*
immediately follow x in the address space when "inconsistent behavior:"
is printed?

If so, can you describe what the word "follows" means in this context?
If it has a meaning that permits such behavior, can you cite a source
that indicates that that's how the authors of the standard meant it?

[Bug tree-optimization/61502] == comparison on "one-past" pointer gives wrong result

[joseph at codesourcery dot com]

https://gcc.gnu.org/bugzilla/show_bug.cgi?id=61502

--- Comment #9 from joseph at codesourcery dot com <joseph at codesourcery dot com> ---
On Tue, 21 Oct 2014, Keith.S.Thompson at gmail dot com wrote:

> Are you saying it's possible that y immediately follows x in the
> address space when that line of output is printed, and that y *doesn't*
> immediately follow x in the address space when "inconsistent behavior:"
> is printed?

Yes.

> If so, can you describe what the word "follows" means in this context?

"follows" is a binary relation with no constraints except when two objects 
are part of the same declared or allocated larger object.  If part of the 
same declared or allocated larger object, it means that the bytes of the 
latter object immediately follow the bytes of the former object within the 
sequence of bytes making up the representation of the larger object (but 
this does *not* mean that it is necessarily valid to derive pointers to 
one of the smaller objects from pointers to the other, unless you are very 
careful about what sequences of conversions and arithmetic are involved; 
many cases of pointer conversions and arithmetic are less fully defined 
than one might naively expect, and the question of which of multiple 
possible objects is relevant in a particular context is one of the more 
poorly defined areas of C).

[Bug tree-optimization/61502] == comparison on "one-past" pointer gives wrong result

[Keith.S.Thompson at gmail dot com]

https://gcc.gnu.org/bugzilla/show_bug.cgi?id=61502

--- Comment #10 from Keith Thompson <Keith.S.Thompson at gmail dot com> ---
I strongly disagree with your interpretation.

Do you believe that the authors of the standard meant it the way you do?

I suggest that the footnote:

> Two objects may be adjacent in memory because they are adjacent elements
> of a larger array or adjacent members of a structure with no padding
> between them, or because the implementation chose to place them so,
> even though they are unrelated.

implies that the phrase "adjacent in memory" (which appears to
be synonymous with "immediately following in the address space") is
intended to have a *consistent* meaning, even for unrelated objects.
Two given objects may or may not be adjacent, and if they are adjacent
they may appear in either order, entirely at the whim of the compiler.
But I don't see a reasonable interpretation of the standard's wording
that doesn't require "==" to behave consistently. Indeed, I believe
that consistency (which gcc lacks) is the whole point of that wording.

Any two pointer values are either equal or unequal. In the test program,
the pointer values do not change, but they compare both equal and unequal
at different points in the code. In my opinion, that's a clear violation
of the required semantics.

And I don't believe you've fullyl answered my question about what is meant
by "follows", at least not fully. I agree with you about the meaning
for objects that are subobjects of some larger object, but for other cases
you've essentially said that it's meaningless. I actually would have no
problem with that, and I wouldn't complain if the standard left it
unspecified -- but it doesn't.

[Bug tree-optimization/61502] == comparison on "one-past" pointer gives wrong result

[rguenth at gcc dot gnu.org]

https://gcc.gnu.org/bugzilla/show_bug.cgi?id=61502

--- Comment #11 from Richard Biener <rguenth at gcc dot gnu.org> ---
(In reply to Harald van Dijk from comment #4)
> That's an interesting argument. You may well be right that the original
> code, strictly speaking, does not prove that GCC has a bug, but I do think
> GCC has a bug nonetheless, and have come up with a different example.
> 
> #include <stdio.h>
> #include <string.h>
> 
> int x, y;
> 
> char buf[sizeof (int *)];
> 
> int main()
> {
>   int *p = &y;
>   memcpy (buf, &p, sizeof p);
>   memcpy (&p, buf, sizeof p);
>   x = 2, y = 1;
>   if (p == &x + 1)
>     *p = 2;
>   else
>     y = 2;
>   printf ("x = %d, y = %d\n", x, y);
>   return 0;
> }
> 
> Compiling with -O2, I see "x = 2, y = 1". p has been assigned &y. Whether it
> compares equal to &x + 1 is unspecified, but it doesn't change its origins:
> p points to y. Therefore, either the assignment to *p should change y, or in
> the else branch, the plain assignment to y should change y. Either way, the
> correct result is "x = 2, y = 2".
> 
> It seems like GCC is assuming that if p == &x + 1, and &x + 1 != &y, then p
> != &y, so the assignment to *p cannot change y. The flaw in that logic is
> again the optimisation of &x + 1 != &y to a constant.
> 
> I see the behaviour I describe in versions 4.9.0 and 4.8.2. This program
> does print "x = 2, y = 2" in my testing on GCC 4.7.3, but that is because p
> == &x + 1 happens to not compare as true in that version. Slightly tweaked
> versions of this fail with versions 4.7.3, 4.6.4, 4.5.4 and 4.4.7, but not
> 4.3.6.

I can't reproduce your findings with any of the specified GCC version nor
with any other I tried (I tried on x86_64-linux and x86_64-linux with -m32).
The test program always prints "x = 2, y = 2" as expected.

[Bug tree-optimization/61502] == comparison on "one-past" pointer gives wrong result

[harald at gigawatt dot nl]

https://gcc.gnu.org/bugzilla/show_bug.cgi?id=61502

--- Comment #12 from Harald van Dijk <harald at gigawatt dot nl> ---
(In reply to Richard Biener from comment #11)
> I can't reproduce your findings with any of the specified GCC version nor
> with any other I tried (I tried on x86_64-linux and x86_64-linux with -m32).
> The test program always prints "x = 2, y = 2" as expected.

The wrong code should be visible by inspecting the generated assembly, but it
only actually fails at run-time if y directly follows x in memory. It did for
me back when I commented, but it no longer does. Here is a version that should
fail more reliably, by having only x and y as global variables, and by covering
both the case where y immediately follows x and the case where x immediately
follows y:

#include <stdio.h>
#include <string.h>

int x, y;

int main()
{
  int *volatile v;
  int *p;

  v = &y;
  p = v;
  x = 2, y = 1;
  if (p == &x + 1)
    *p = 2;
  else
    y = 2;
  printf ("x = %d, y = %d\n", x, y);

  v = &x;
  p = v;
  x = 2, y = 1;
  if (p == &y + 1)
    *p = 1;
  else
    x = 1;
  printf ("x = %d, y = %d\n", x, y);

  return 0;
}

The only correct output is "x = 2, y = 2" followed by "x = 1, y = 1". On my
main system, I get "x = 2, y = 1" followed by "x = 1, y = 1". On another, I get
"x = 2, y = 2" followed by "x = 2, y = 1".

[Bug tree-optimization/61502] == comparison on "one-past" pointer gives wrong result

[joseph at codesourcery dot com]

https://gcc.gnu.org/bugzilla/show_bug.cgi?id=61502

--- Comment #13 from joseph at codesourcery dot com <joseph at codesourcery dot com> ---
On Wed, 22 Oct 2014, Keith.S.Thompson at gmail dot com wrote:

> Do you believe that the authors of the standard meant it the way you do?

The "authors of the standard" are an amorphous group over 30 years and I 
don't think a single intent can meaningfully be assigned to them.

In recent years, the general position has included:

* C is a high-level language supporting a wide range of implementations, 
not just ones with a conventional linear address space and otherwise 
conventional direct mappings to machine operations;

* edge cases should generally be resolved in the way that is convenient 
for optimization rather than the way that is simplest to specify.

For the latter, see for example the discussion in the Parma minutes of 
instability of uninitialized variables with automatic storage duration.  
That is, if you have

  unsigned char a; // uninitialized, inside a function
  unsigned char b = a;
  unsigned char c = b;

then even if there isn't undefined behavior, there is no requirement 
(given no further assignments to b or c) for b == c, or for the value of b 
== c to stay unchanged, or for the values of b and c to remain unchanged.

(As another example, C11 chose to make INT_MIN % -1 explicitly undefined 
for implementation convenience, even though users might think the value is 
obviously 0.)

[Bug tree-optimization/61502] == comparison on "one-past" pointer gives wrong result

[Keith.S.Thompson at gmail dot com]

https://gcc.gnu.org/bugzilla/show_bug.cgi?id=61502

--- Comment #14 from Keith Thompson <Keith.S.Thompson at gmail dot com> ---
The C standard requires that, if y "happens to immediately follow"
x in the address space, then a pointer just past the end of x shall
compare equal to a pointer to the beginning of y (C99 and C11 6.5.9p6).

How could I distinguish the current behavior of gcc from the behavior
of a hypothetical C compiler that violates that requirement? In
other words, in what sense does gcc actually obey that requirement?

Or is it your position that the requirement is so vague that it
cannot meaningfully be followed? If so, have you followed up with
the standard committee to clarify or remove it?

[Bug tree-optimization/61502] == comparison on "one-past" pointer gives wrong result

[joseph at codesourcery dot com]

https://gcc.gnu.org/bugzilla/show_bug.cgi?id=61502

--- Comment #15 from joseph at codesourcery dot com <joseph at codesourcery dot com> ---
On Sun, 26 Oct 2014, Keith.S.Thompson at gmail dot com wrote:

> https://gcc.gnu.org/bugzilla/show_bug.cgi?id=61502
> 
> --- Comment #14 from Keith Thompson <Keith.S.Thompson at gmail dot com> ---
> The C standard requires that, if y "happens to immediately follow"
> x in the address space, then a pointer just past the end of x shall
> compare equal to a pointer to the beginning of y (C99 and C11 6.5.9p6).
> 
> How could I distinguish the current behavior of gcc from the behavior
> of a hypothetical C compiler that violates that requirement? In
> other words, in what sense does gcc actually obey that requirement?

They are not distinguishable (unless by implementation documentation 
defining what "happens to immediately follow" means for the given 
implementation - but the meaning of that phrase is unspecified, not 
implementation-defined, so there is no requirement for implementations to 
document anything in that regard).  "happens to immediately follow" is an 
intuitive description that explains *why* such pointers are allowed to 
compare equal at all (to avoid a requirement for otherwise unnecessary 
padding in common classes of implementations), but can only be observed by 
the result of a comparison (an observation that is then only valid for 
that particular comparison).

The natural state would be for such pointers to compare unequal.  The 
standard gives latitude for them to compare equal, but there is never an 
observable requirement that they do, even if some other comparison had 
that result.

[Bug tree-optimization/61502] == comparison on "one-past" pointer gives wrong result

[rguenth at gcc dot gnu.org]

https://gcc.gnu.org/bugzilla/show_bug.cgi?id=61502

Richard Biener <rguenth at gcc dot gnu.org> changed:

           What    |Removed                     |Added
----------------------------------------------------------------------------
                 CC|                            |gcc at robbertkrebbers dot nl

--- Comment #16 from Richard Biener <rguenth at gcc dot gnu.org> ---
*** Bug 65679 has been marked as a duplicate of this bug. ***

[Bug tree-optimization/61502] == comparison on "one-past" pointer gives wrong result

[pinskia at gcc dot gnu.org]

https://gcc.gnu.org/bugzilla/show_bug.cgi?id=61502

Andrew Pinski <pinskia at gcc dot gnu.org> changed:

           What    |Removed                     |Added
----------------------------------------------------------------------------
                 CC|                            |gabravier at gmail dot com

--- Comment #45 from Andrew Pinski <pinskia at gcc dot gnu.org> ---
*** Bug 103343 has been marked as a duplicate of this bug. ***

[Bug tree-optimization/61502] == comparison on "one-past" pointer gives wrong result

[pinskia at gcc dot gnu.org]

https://gcc.gnu.org/bugzilla/show_bug.cgi?id=61502

--- Comment #46 from Andrew Pinski <pinskia at gcc dot gnu.org> ---
Note this came up on twitter the other day:
https://twitter.com/rep_stosq_void/status/1461635511009828864

[Bug tree-optimization/61502] == comparison on "one-past" pointer gives wrong result

[egallager at gcc dot gnu.org]

https://gcc.gnu.org/bugzilla/show_bug.cgi?id=61502

--- Comment #47 from Eric Gallager <egallager at gcc dot gnu.org> ---
(In reply to Andrew Pinski from comment #46)
> Note this came up on twitter the other day:
> https://twitter.com/rep_stosq_void/status/1461635511009828864

Wayback Machine link, since the original has been deleted:
http://web.archive.org/web/20220319120336/https://twitter.com/rep_stosq_void/status/1461635511009828864

[Bug tree-optimization/61502] == comparison on "one-past" pointer gives wrong result

[vincent-gcc at vinc17 dot net]

https://gcc.gnu.org/bugzilla/show_bug.cgi?id=61502

--- Comment #48 from Vincent Lefèvre <vincent-gcc at vinc17 dot net> ---
(In reply to Alexander Cherepanov from comment #35)
> DR 260 allows one to argue that representation of these pointers could
> change right between the checks but IMHO this part of DR 260 is just wrong
> as it makes copying objects byte-by-byte impossible. See
> https://bugs.llvm.org/show_bug.cgi?id=44188 for a nice illustration.

Note that the behavior of GCC with your testcase is unrelated to the LLVM issue
and DR 260. And it is even reversed: here with GCC, the result of the
comparison is *incorrect before* the (potentially invalid) copy of the pointer,
and it is *correct after* the copy.

It seems that the reason why the result incorrect before the copy is that GCC
optimizes based on the fact that p and q points to distinct objects (or past to
them), i.e. GCC considers that the pointers are necessarily different in such a
case, without needing a further analysis. For repr and val2, I assume that GCC
gives the correct result because it does not optimize: it just compares the
representations of p and q, which are the same.

> While at it, the testcase also demonstrates that the comparison `p == q` is
> unstable.

p == p would also be unstable: What could happen is that:
1. The implementation evaluates the first p.
2. The representation of p changes.
3. The implementation evaluates the second p.
4. Due to the different representations, the comparison returns false.