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

[vincent-gcc at vinc17 dot net via Gcc-bugs]

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

--- Comment #48 from Vincent Lefèvre  ---
(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.

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

[egallager at gcc dot gnu.org via Gcc-bugs]

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

--- Comment #47 from Eric Gallager  ---
(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

[pinskia at gcc dot gnu.org via Gcc-bugs]

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

--- Comment #46 from Andrew Pinski  ---
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

[pinskia at gcc dot gnu.org via Gcc-bugs]

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

Andrew Pinski  changed:

   What|Removed |Added

 CC||gabravier at gmail dot com

--- Comment #45 from Andrew Pinski  ---
*** Bug 103343 has been marked as a duplicate of this bug. ***

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

[rguenther at suse dot de]

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

--- Comment #44 from rguenther at suse dot de  ---
On Mon, 20 Jan 2020, ch3root at openwall dot com wrote:

> https://gcc.gnu.org/bugzilla/show_bug.cgi?id=61502
> 
> --- Comment #43 from Alexander Cherepanov  ---
> The following example demonstrates that the instability taints the surrounding
> code even if it's in dead code itself. In particular, this shows that even
> making comparisons like ` + 1 == ` undefined will not help.
> 
> --
> #include 
> #include 
> 
> __attribute__((noipa)) // imagine it in a separate TU
> static void *opaque(void *p) { return p; }
> 
> __attribute__((noipa)) // imagine it in a separate TU
> static void g(int a)
> {
> printf("%d\n", a);
> exit(0);
> }
> 
> static void f(int c, void *p, void *q, void *r)
> {
> while (c) {
> g(p == r);
> 
> if (p != q && q == r)
> puts("unreachable");
> }
> }
> 
> int main(int c, char **v)
> {
> (void)v;
> 
> int x[5];
> int y[2];
> 
> void *p = 
> void *q =  + 1;
> 
> opaque(q); // escaped
> void *r = opaque(p); // hide the provenance of p
> 
> f(c, p, q, r);
> }
> --
> $ gcc -std=c11 -pedantic -Wall -Wextra test.c && ./a.out
> 1
> $ gcc -std=c11 -pedantic -Wall -Wextra -O3 test.c && ./a.out
> 0
> --
> gcc x86-64 version: gcc (GCC) 10.0.1 20200120 (experimental)
> --

Not sure what it proves but here the loop unswitching pass
decides to unswitch on c != 0 and  + 1 == r (aka q == r).
That in itself doesn't look wrong but I guess it's (again)
the conditional equivalence that somehow breaks things.

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

[ch3root at openwall dot com]

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

--- Comment #43 from Alexander Cherepanov  ---
The following example demonstrates that the instability taints the surrounding
code even if it's in dead code itself. In particular, this shows that even
making comparisons like ` + 1 == ` undefined will not help.

--
#include 
#include 

__attribute__((noipa)) // imagine it in a separate TU
static void *opaque(void *p) { return p; }

__attribute__((noipa)) // imagine it in a separate TU
static void g(int a)
{
printf("%d\n", a);
exit(0);
}

static void f(int c, void *p, void *q, void *r)
{
while (c) {
g(p == r);

if (p != q && q == r)
puts("unreachable");
}
}

int main(int c, char **v)
{
(void)v;

int x[5];
int y[2];

void *p = 
void *q =  + 1;

opaque(q); // escaped
void *r = opaque(p); // hide the provenance of p

f(c, p, q, r);
}
--
$ gcc -std=c11 -pedantic -Wall -Wextra test.c && ./a.out
1
$ gcc -std=c11 -pedantic -Wall -Wextra -O3 test.c && ./a.out
0
--
gcc x86-64 version: gcc (GCC) 10.0.1 20200120 (experimental)
--

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

[ch3root at openwall dot com]

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

--- Comment #42 from Alexander Cherepanov  ---
I've recently stumbled upon a straightforward description (from Hal Finkel, in
https://bugs.llvm.org/show_bug.cgi?id=34548#c77) for the thing that bothered me
in the second part of comment 17. Roughly speaking: instability is
inconsistency, which leads to logical contradictions, which leads to total
chaos. Instability taints everything around it and you cannot trust anything in
the end. A small modification to the example in comment 18 will hopefully
illustrate it:

--
#include 

__attribute__((noipa)) // imagine it in a separate TU
static void *opaque(void *p) { return p; }

static void f(void *p, void *q, void *r)
{
if (p != q && q == r)
printf("%d\n", p == r);
}

int main()
{
int x[5];
int y[2];

void *p = 
void *q =  + 1;

opaque(q); // escaped
void *r = opaque(p); // hide the provenance of p

f(p, q, r);
}
--
$ gcc -std=c11 -pedantic -Wall -Wextra -fno-partial-inlining -O3 test.c &&
./a.out
0
--
gcc x86-64 version: gcc (GCC) 10.0.0 20200110 (experimental)
--

Here `r` has the same value as `p` but the optimizer cannot see this. Comparing
them to `q` gives different results -- `p` is non-equal to `q` (at compile
time) and `r` is equal to `q` (at run time). Then, given these results, we ask
the optimizer to compare `p` and `r` and it happily concludes that they are
non-equal which is nonsense.

This example could be explained by conditional propagation of wrong provenance
but I see the optimization happening during the einline pass so it's probably
not it. (-fno-partial-inlining simplifies the analysis but doesn't affect the
result.) Even if this particular example triggers some other bug(s) in gcc the
logic in the previous paragraph is probably nice to have in the optimizer. But
it could not until the instability is fixed.

I guess this settles the question for me FWIW. Unless there is a magic way to
contain logical contradictions I think the right way is like this:
- the C standard could be changed to make comparison of the form ` ==  + 1`
unspecified or not -- not that important;
- all (non-UB) things in practice should have stable behavior;
- comparison of the form ` ==  + 1` in practice should give results
according to naive, literal reading of C11.

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

[ch3root at openwall dot com]

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

--- Comment #41 from Alexander Cherepanov  ---
(In reply to Richard Biener from comment #38)
> (In reply to Alexander Cherepanov from comment #37)
> > On 30/12/2019 10.51, rguenther at suse dot de wrote:
> > >> Obviously, it could be used to fold `a + i == b` to `0` if `a` and `b`
> > >> are two different known arrays and `i` is unknown
> > > 
> > > That's indeed the main thing. Basically it allows points-to analysis work 
> > > at
> > > all in the presence of non-constant offsets.
> > 
> > But what is PTA used for? Examples that I've seen all deal with
> > dereferenceable pointers. And current gcc behaviour is just fine in that
> > case. The problem is with non-dereferenceable pointers. So is PTA important
> > for cases where dereferenceability is unknown (or known to be false) or it's
> > just too complicated to take dereferenceability into account?
> 
> points-to analysis doesn't care about whether a pointer is dereferenced or
> not when computing its points-to set.  You can very well add a dereference
> to your testcase and that shouldn't affect its outcome, no?

No, I mean dereferences of both pointers, these cannot be added to my testcase.
To exclude any ambiguity, I'm talking about my last testcase (comment 35) in
this bug report. (Or the original testcase from Peter Sewell in comment 0.) One
pointer is ``, fine, dereferenceable. The other one is ` + 1`, just past
the end of the object `y`, non-dereferenceable (C11, 6.5.6p8).

So the rough idea is to do it like this: if both pointers are known to be
dereferenceable at the point of check (e.g., we want to move `a[i] = 1;` over
`b[j] = 2;`) then the results of the PTA could be used, otherwise (e.g., we
want to fold `a + i == b + j` only knowing that `a` and `b` are different
arrays) pass the comparison to run time.

A nice thing about this approach is that it treats pointers and integers in the
same way. In particular, it will also solve bug 93010.
And it is applicable to dynamic memory which is handled somewhat differently
now.
It even almost works for `restrict`! (It should be possible to optimize `int
f(int *restrict p, int *q) { *p = 1; *q; return p == q; }` but not with `*p =
1;` replaced with just `*p;`.)

In some sense this approach delegates a part of the work to the programmer. If
they put a dereference somewhere they effectively assert that the pointer (even
if it's a casted from an integer) is good at this particular moment -- that the
result of malloc was not null, that the memory was not free'd, delete'd or
reused via placement new since, or that the local variable is still in scope,
or that the pointer is not past the end, or that the storage is not of zero
size. This of course depends on the programmer respecting the provenances but
that's not a news:-)

What is a dereference in this context is a somewhat tricky question.
Dereferencing a pointer to an empty struct should not count. But calling a
static method in non-empty class probably should (need to check the C++ std).
Then, while analyzing `p == q` it's not necessary to require dereferenceability
of `p` and `q` themselves, dereferenceability of `p + k` and `q + l` is enough
if `k` and `l` are both nonnegative or strictly negative.

Many more improvements are possible too. E.g., `a + i == b + j` could be folded
to `0` if the addresses are not exposed or only exposed in ways that don't
allow one to reason about the arrangement of the objects. IIUC llvm does some
of this, e.g., https://reviews.llvm.org/rL249490.

> And yes, GCC uses points-to analysis results to optimize pointer equality
> compares like p == q to false if the points-to sets do not intersect (for
> a set of cases, but that's current implementation detail).  That helps
> surprisingly often for abstraction coming from the C++ standard library
> container iterators.

Isn't it mainly dynamic memory? Then it's already handled a bit differently,
even `new int == new int` is not optimized right now (unlike in clang).
AIUI this bug report is relevant to non-dynamic memory only (but the fix could
improve the case of dynamic memory too).

> I do agree that we have bugs in GCC but AFAICS those come from conditional
> equivalences being propagated and from the very old RTL alias analysis issue
> involving base_alias_check.  Once we dealt with the latter I'm happily
> exploring fixes for the former - but the latter will happily nullify fixes
> of the former.

IMHO those two are quite different problems -- this bug is about wrong results
at compile-time and conditional equivalence propagation depends on the results
not being available at the optimization time. I could be wrong but it seems to
me that it's better to deal with them separately.

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

[ch3root at openwall dot com]

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

--- Comment #40 from Alexander Cherepanov  ---
Example with a flexible array member:

--
#include 
#include 

__attribute__((noipa)) // imagine it in a separate TU
static void *opaque(void *p) { return p; }

int main()
{
int x[5];
struct { int i, j, a[]; } y;

printf("eq1: %d\n", x == y.a);

int *p = x;
int *q = y.a;
printf("eq2: %d\n", p == q);
printf("diff: %d\n", memcmp(, , sizeof(int *)));

opaque(q); // escaped
opaque(); // move the next comparison to run-time
printf("eq3: %d\n", p == q);
}
--
$ gcc -std=c11 -pedantic -Wall -Wextra test.c && ./a.out
eq1: 0
eq2: 1
diff: 0
eq3: 1
$ gcc -std=c11 -pedantic -Wall -Wextra -O3 test.c && ./a.out
eq1: 0
eq2: 0
diff: 0
eq3: 1
--
gcc x86-64 version: gcc (GCC) 10.0.0 20200110 (experimental)
--

This example should be standard-compliant.

eq1 is wrong even without optimization, eq2 folded by fre1.

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

[ch3root at openwall dot com]

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

--- Comment #39 from Alexander Cherepanov  ---
For diversity, a couple of examples with zero sized objects. Even though they
don't have pointer arithmetic at all they could be classified as being about
past-the-end pointers:-) Please let me know if it's better to move them into a
separate bug (or bugs).

--
#include 

int main()
{
struct {} x, y, *p = , *q = 

printf("eq1: %d\n",  == );
printf("eq2: %d\n", p == q);
}
--
$ gcc -std=c11 -Wall -Wextra test.c && ./a.out
eq1: 0
eq2: 1
--
gcc x86-64 version: gcc (GCC) 10.0.0 20200110 (experimental)
--

Empty structs is a gcc extension (they are UB according to C11, 6.7.2.1p8) but
IMHO the demonstrated instability is not good.

Happens only without optimizations (optimizations add some padding between `x`
and `y`).

Similar clang bug -- https://bugs.llvm.org/show_bug.cgi?id=44508.

[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 #38 from Richard Biener  ---
(In reply to Alexander Cherepanov from comment #37)
> On 30/12/2019 10.51, rguenther at suse dot de wrote:
> >> Obviously, it could be used to fold `a + i == b` to `0` if `a` and `b`
> >> are two different known arrays and `i` is unknown
> > 
> > That's indeed the main thing. Basically it allows points-to analysis work at
> > all in the presence of non-constant offsets.
> 
> But what is PTA used for? Examples that I've seen all deal with
> dereferenceable pointers. And current gcc behaviour is just fine in that
> case. The problem is with non-dereferenceable pointers. So is PTA important
> for cases where dereferenceability is unknown (or known to be false) or it's
> just too complicated to take dereferenceability into account?

points-to analysis doesn't care about whether a pointer is dereferenced or not
when computing its points-to set.  You can very well add a dereference to your
testcase and that shouldn't affect its outcome, no?

And yes, GCC uses points-to analysis results to optimize pointer equality
compares like p == q to false if the points-to sets do not intersect (for
a set of cases, but that's current implementation detail).  That helps
surprisingly often for abstraction coming from the C++ standard library
container iterators.

I do agree that we have bugs in GCC but AFAICS those come from conditional
equivalences being propagated and from the very old RTL alias analysis issue
involving base_alias_check.  Once we dealt with the latter I'm happily
exploring
fixes for the former - but the latter will happily nullify fixes of the former.

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

[ch3root at openwall dot com]

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

--- Comment #37 from Alexander Cherepanov  ---
On 30/12/2019 10.51, rguenther at suse dot de wrote:
>> Obviously, it could be used to fold `a + i == b` to `0` if `a` and `b`
>> are two different known arrays and `i` is unknown
> 
> That's indeed the main thing. Basically it allows points-to analysis work at
> all in the presence of non-constant offsets.

But what is PTA used for? Examples that I've seen all deal with dereferenceable
pointers. And current gcc behaviour is just fine in that case. The problem is
with non-dereferenceable pointers. So is PTA important for cases where
dereferenceability is unknown (or known to be false) or it's just too
complicated to take dereferenceability into account?

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

[rguenther at suse dot de]

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

--- Comment #36 from rguenther at suse dot de  ---
On December 29, 2019 6:42:55 PM GMT+01:00, ch3root at openwall dot com
 wrote:
>https://gcc.gnu.org/bugzilla/show_bug.cgi?id=61502
>
>--- Comment #35 from Alexander Cherepanov 
>---
>What remains in this pr is the original problem.
>
>1. The best way to demonstrate that there is indeed a bug here is
>probably to
>compare representation of pointers directly:
>
>--
>#include 
>#include 
>
>__attribute__((noipa)) // imagine it in a separate TU
>static void *opaque(void *p) { return p; }
>
>int main()
>{
>int x[5];
>int y[2];
>
>void *p = 
>void *q =  + 1;
>
>printf("val1: %d\n", p == q);
>printf("repr: %d\n", memcmp(, , sizeof(void *)) == 0);
>
>opaque(); // move the next comparison to runtime
>printf("val2: %d\n", p == q);
>
>opaque(q);
>}
>--
>$ gcc -std=c11 -pedantic -Wall -Wextra -O3 test.c && ./a.out
>val1: 0
>repr: 1
>val2: 1
>--
>gcc x86-64 version: gcc (GCC) 10.0.0 20191229 (experimental)
>--
>
>C11, 6.2.6.1p4: "Two values (other than NaNs) with the same object
>representation compare equal". Our pointers are not NaNs and have the
>same
>representation so should compare equal.
>
>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.
>
>While at it, the testcase also demonstrates that the comparison `p ==
>q` is
>unstable.
>
>I'm not taking sides here, just stating that the standard and the
>compiler
>disagree.
>
>2. C++ at some point made results of the discussed comparison
>unspecified --
>https://eel.is/c++draft/expr.eq#3.1 . According to the DR linked to in
>comment
>27, it's done to make the definition usable at compile time. Perhaps
>harmonization of the standards should move in this direction, not vice
>versa.
>
>3. OTOH clang was fixed to be complying with C11.
>
>4. What seems missing in the discussion is a clear description of
>benefits of
>the current gcc's approach. Does it make some optimizations easier to
>implement? Does it enable other optimizations?
>Obviously, it could be used to fold `a + i == b` to `0` if `a` and `b`
>are two
>different known arrays and `i` is unknown

That's indeed the main thing. Basically it allows points-to analysis work at
all in the presence of non-constant offsets. 

 (or known to be exactly the
>length of
>`a`). But this is probably not helpful for aliasing analysis as AA
>doesn't deal
>with past-the-end pointers. And optimization of loops like in comment
>19 is
>probably not superhelpful too:-)

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

[ch3root at openwall dot com]

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

--- Comment #35 from Alexander Cherepanov  ---
What remains in this pr is the original problem.

1. The best way to demonstrate that there is indeed a bug here is probably to
compare representation of pointers directly:

--
#include 
#include 

__attribute__((noipa)) // imagine it in a separate TU
static void *opaque(void *p) { return p; }

int main()
{
int x[5];
int y[2];

void *p = 
void *q =  + 1;

printf("val1: %d\n", p == q);
printf("repr: %d\n", memcmp(, , sizeof(void *)) == 0);

opaque(); // move the next comparison to runtime
printf("val2: %d\n", p == q);

opaque(q);
}
--
$ gcc -std=c11 -pedantic -Wall -Wextra -O3 test.c && ./a.out
val1: 0
repr: 1
val2: 1
--
gcc x86-64 version: gcc (GCC) 10.0.0 20191229 (experimental)
--

C11, 6.2.6.1p4: "Two values (other than NaNs) with the same object
representation compare equal". Our pointers are not NaNs and have the same
representation so should compare equal.

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.

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

I'm not taking sides here, just stating that the standard and the compiler
disagree.

2. C++ at some point made results of the discussed comparison unspecified --
https://eel.is/c++draft/expr.eq#3.1 . According to the DR linked to in comment
27, it's done to make the definition usable at compile time. Perhaps
harmonization of the standards should move in this direction, not vice versa.

3. OTOH clang was fixed to be complying with C11.

4. What seems missing in the discussion is a clear description of benefits of
the current gcc's approach. Does it make some optimizations easier to
implement? Does it enable other optimizations?
Obviously, it could be used to fold `a + i == b` to `0` if `a` and `b` are two
different known arrays and `i` is unknown (or known to be exactly the length of
`a`). But this is probably not helpful for aliasing analysis as AA doesn't deal
with past-the-end pointers. And optimization of loops like in comment 19 is
probably not superhelpful too:-)

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

[ch3root at openwall dot com]

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

--- Comment #34 from Alexander Cherepanov  ---
It seems to me that problems with the optimization `if (p == q) use p` -> `if
(p == q) use q` (comment 4 etc.) are not specific to past-the-end pointers. So
I filed a separated bug for it with various testcases -- see pr93051.

The same for the optimization `p == q ? p : q` -> `q` (comment 30) -- see
pr93052.

[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

Eric Gallager  changed:

   What|Removed |Added

 CC||egallager at gcc dot gnu.org

--- Comment #33 from Eric Gallager  ---
This came up on the mailing lists again here:
https://gcc.gnu.org/ml/gcc/2019-04/msg00276.html

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

[jakub at gcc dot gnu.org]

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

Jakub Jelinek  changed:

   What|Removed |Added

 CC||jakub at gcc dot gnu.org

--- Comment #32 from Jakub Jelinek  ---
See PR88775 discussions regarding this.

[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  changed:

   What|Removed |Added

 CC||SztfG at yandex dot ru

--- Comment #31 from Andrew Pinski  ---
*** Bug 89157 has been marked as a duplicate of this bug. ***

[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  changed:

   What|Removed |Added

 Blocks||85800

--- Comment #30 from Richard Biener  ---
Another interesting example in PR85800 where the offending "bad" transformation
is
for char a, b

  if (a == b)
a[i] = a;
  else
a[i] = b;

if-convert that to

  a[i] = b;

because a and b have different pointer provenance -- runtime equal pointers
 and +1 (one-after-end) again.  The if-converted result results in
a[i] having same provenance as b rather than "both" (GCC happily tracks
provenance union).

In isolation avoiding this kind of transforms is bad (consider this is isolated
into a separate function and later inlined).


Referenced Bugs:

https://gcc.gnu.org/bugzilla/show_bug.cgi?id=85800
[Bug 85800] A miscompilation bug with unsigned char

[Bug tree-optimization/61502] == 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

--- Comment #29 from Peter Sewell  ---
On 8 May 2018 at 08:22, rguenth at gcc dot gnu.org  wrote:

> https://gcc.gnu.org/bugzilla/show_bug.cgi?id=61502
>
> --- Comment #25 from Richard Biener  ---
> (In reply to Harald van Dijk from comment #22)
> > (In reply to Andrew Pinski from comment #21)
> > > Invalid as mentioned a few times already but never actually closed
> until now.
> >
> > I posted a strictly conforming program that with GCC does not behave as
> > required by the standard. The issue is valid, even if the original test
> case
> > is not.
>
> If you are talking about the one in comment#12 then this is the same issue
> as present in a few other "similar" bugs where GCC propagates conditional
> equivalences (for example the linked PR65752):
>
>   v = 
>   p = v;
>   x = 2, y = 1;
>   if (p ==  + 1)
> *p = 2;
>
> is turned into
>
>   v = 
>   p = v;
>   x = 2, y = 1;
>   if (p ==  + 1)
> *( + 1) = 2;
>
> by GCC and the store is then no longer possibly aliasing y.
>
> Conditional equivalences are a difficult thing to exploit for optimization
> and there's some work in progress for the standard regarding to pointer
> provenance which IIRC says that the comparison result of  ==  + 1
> returns an unspecified value.  Not sure if that helps us


FYI, the current state of that work in progress is here:

https://cdn.rawgit.com/C-memory-object-model-study-group/c-mom-sg/master/notes/cmom-0001-2018-05-04-sewell-clarifying-provenance-v4.html

and comments from a GCC perspective would be much appreciated.
It's been informed by useful discussion at the recent WG14 and EuroLLVM
meetings.

Our current proposal indeed makes that comparison an unspecified value -
more
generally, allowing any pointer equality comparison to either take
provenance
into account or not - exactly because we see GCC do so in some cases.
If that isn't important for optimisation, returning to a fully concrete
semantics
for == would be a simpler choice.

but then the
> only way our for GCC for this particular issue would be to never actually
> propagate conditional equivalences.
>

(Conceivably it could be allowed where the compiler can see that the two
have the same provenance.  We've no idea how useful that would be.)


>
> Sth that might be worth investigating, but within the current structure of
> the optimization passes that apply this transform it's impossible to decide
> whether a value resulted from conditional equivalences or not...  I'm also
> not sure to what extent simplification results using a conditional
> predicate
> like p ==  + 1 are affected as well.
>
> IMHO it's a defect in the language if
>
>   p = 
>   if (p ==  + 1)
> *p = 2;
>
> is valid but
>
>   p = 
>   if (p ==  + 1)
> *( + 1) = 2;
>
> is invoking undefined behavior.  Or at least a very uncomfortable situation
> for a compiler writer.  IMHO the pointer provenance work making the
> comparison having unspecified result doesn't really help since that doesn't
> make it invoke undefined behavior.
>

It's not clear how this could be resolved. For the source-language
semantics,
if one wants to be able to do provenance-based alias analysis, we don't see
any clean way in which the second could be allowed.
And forbidding the first would need one to make == of pointers with
different
provenances UB, which we imagine would break a lot of C code.

That said, in general the intermediate-language semantics might be quite
different
from the C-source-language semantics (as we discover in discussion with
Nuno Lopes
and his colleagues about their LLVM semantics), so long as it implements
the source
semantics.

Peter, Kayvan, Victor


>
> --
> You are receiving this mail because:
> You reported the bug.
>

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

[rguenther at suse dot de]

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

--- Comment #28 from rguenther at suse dot de  ---
On Tue, 8 May 2018, harald at gigawatt dot nl wrote:

> https://gcc.gnu.org/bugzilla/show_bug.cgi?id=61502
> 
> --- Comment #27 from Harald van Dijk  ---
> (In reply to Richard Biener from comment #26)
> > Unfortunately it isn't visible _what_ change fixed this
> 
> The revision number is listed in Richard Smith's second comment. The changes
> can be seen with
> 
>   svn diff -c 220343 https://llvm.org/svn/llvm-project/
> 
> That's also where I got the C++ issue number from.

OK, so that's a frontend only change (constexpr).

> > and thus if just
> > some more massaging of the testcase is necessary to make the bug resurface
> > or if LLVM found a clever way to attack the underlying issue (whatever
> > underlying issue LLVM had - I'm only guessing it may be the same conditional
> > propagation).
> 
> When they turn a comparison between a pointer to an object and a pointer to 
> one
> past an object into a non-constant expression, that's apparently enough for
> them to force the comparison to be performed at run-time.

I'm quite sure they manage to "optimize"

int a, b;
bool foo()
{
  return  == 
}

as well as

int a, b;
bool foo(int i)
{
  if (i == 1)
return  ==  + i;
  return true;
}

hmm, clang 3.8 does not.  It even fails to optimize  ==  + 2
which would be a valid optimization (to false) as this bug is only
about one-past, not about arbitrary compares.

As said the real issue in GCC is the propagation of the
address constant triggered by the conditional equality.
In the other PR that re-surfaces even for integer comparisons.

[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 #27 from Harald van Dijk  ---
(In reply to Richard Biener from comment #25)
> (In reply to Harald van Dijk from comment #22)
> > (In reply to Andrew Pinski from comment #21)
> > > Invalid as mentioned a few times already but never actually closed until 
> > > now.
> > 
> > I posted a strictly conforming program that with GCC does not behave as
> > required by the standard. The issue is valid, even if the original test case
> > is not.
> 
> If you are talking about the one in comment#12 then this is the same issue
> as present in a few other "similar" bugs where GCC propagates conditional
> equivalences (for example the linked PR65752):

Right, there are a lot of ways this can come up.

> Conditional equivalences are a difficult thing to exploit for optimization
> and there's some work in progress for the standard regarding to pointer
> provenance which IIRC says that the comparison result of  ==  + 1
> returns an unspecified value.

For C++ it's http://www.open-std.org/jtc1/sc22/wg21/docs/cwg_defects.html#1652

> Not sure if that helps us

I don't think it does. Although the change would allow p ==  + 1 to evaluate
as false even though they have the same address, there is no sane way for GCC
to actually let it evaluate it as false when p comes from a volatile variable.

> but then the
> only way our for GCC for this particular issue would be to never actually
> propagate conditional equivalences.

Well, there are two incompatible optimisations. This one could be disabled or
restricted, or see below.

> IMHO it's a defect in the language if
> 
>   p = 
>   if (p ==  + 1)
> *p = 2;
> 
> is valid but
> 
>   p = 
>   if (p ==  + 1)
> *( + 1) = 2;
> 
> is invoking undefined behavior.

A legitimate reading of C90 and C99 says the second is valid as well, but it's
not the reading the committee went with. Allowing this, as an extension to what
the standards allow, would be a way to keep the p ->  + 1 transformation
working. It would naturally break some of the current optimisations that GCC
performs, but so would the alternative.

(In reply to Richard Biener from comment #26)
> Unfortunately it isn't visible _what_ change fixed this

The revision number is listed in Richard Smith's second comment. The changes
can be seen with

  svn diff -c 220343 https://llvm.org/svn/llvm-project/

That's also where I got the C++ issue number from.

> and thus if just
> some more massaging of the testcase is necessary to make the bug resurface
> or if LLVM found a clever way to attack the underlying issue (whatever
> underlying issue LLVM had - I'm only guessing it may be the same conditional
> propagation).

When they turn a comparison between a pointer to an object and a pointer to one
past an object into a non-constant expression, that's apparently enough for
them to force the comparison to be performed at run-time.

[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 #26 from Richard Biener  ---
(In reply to James Y Knight from comment #24)
> FWIW, clang did consider this a bug and fixed it in
> https://bugs.llvm.org/show_bug.cgi?id=21327.

Unfortunately it isn't visible _what_ change fixed this and thus if just
some more massaging of the testcase is necessary to make the bug resurface
or if LLVM found a clever way to attack the underlying issue (whatever
underlying issue LLVM had - I'm only guessing it may be the same conditional
propagation).

[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 #25 from Richard Biener  ---
(In reply to Harald van Dijk from comment #22)
> (In reply to Andrew Pinski from comment #21)
> > Invalid as mentioned a few times already but never actually closed until 
> > now.
> 
> I posted a strictly conforming program that with GCC does not behave as
> required by the standard. The issue is valid, even if the original test case
> is not.

If you are talking about the one in comment#12 then this is the same issue
as present in a few other "similar" bugs where GCC propagates conditional
equivalences (for example the linked PR65752):

  v = 
  p = v;
  x = 2, y = 1;
  if (p ==  + 1)
*p = 2;

is turned into

  v = 
  p = v;
  x = 2, y = 1;
  if (p ==  + 1)
*( + 1) = 2;

by GCC and the store is then no longer possibly aliasing y.

Conditional equivalences are a difficult thing to exploit for optimization
and there's some work in progress for the standard regarding to pointer
provenance which IIRC says that the comparison result of  ==  + 1
returns an unspecified value.  Not sure if that helps us but then the
only way our for GCC for this particular issue would be to never actually
propagate conditional equivalences.

Sth that might be worth investigating, but within the current structure of
the optimization passes that apply this transform it's impossible to decide
whether a value resulted from conditional equivalences or not...  I'm also
not sure to what extent simplification results using a conditional predicate
like p ==  + 1 are affected as well.

IMHO it's a defect in the language if

  p = 
  if (p ==  + 1)
*p = 2;

is valid but

  p = 
  if (p ==  + 1)
*( + 1) = 2;

is invoking undefined behavior.  Or at least a very uncomfortable situation
for a compiler writer.  IMHO the pointer provenance work making the
comparison having unspecified result doesn't really help since that doesn't
make it invoke undefined behavior.

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

[foom at fuhm dot net]

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

James Y Knight  changed:

   What|Removed |Added

 CC||foom at fuhm dot net

--- Comment #24 from James Y Knight  ---
FWIW, clang did consider this a bug and fixed it in
https://bugs.llvm.org/show_bug.cgi?id=21327.

[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  changed:

   What|Removed |Added

 Status|RESOLVED|SUSPENDED
   Last reconfirmed||2016-10-19
 Resolution|INVALID |---
 Ever confirmed|0   |1

--- Comment #23 from Richard Biener  ---
.

[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 #22 from Harald van Dijk  ---
(In reply to Andrew Pinski from comment #21)
> Invalid as mentioned a few times already but never actually closed until now.

I posted a strictly conforming program that with GCC does not behave as
required by the standard. The issue is valid, even if the original test case is
not.

[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  changed:

   What|Removed |Added

 Status|UNCONFIRMED |RESOLVED
 Resolution|--- |INVALID

--- Comment #21 from Andrew Pinski  ---
Invalid as mentioned a few times already but never actually closed until now.

[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 #20 from Andrew Pinski  ---
(In reply to Alexander Cherepanov from comment #19)
> (In reply to jos...@codesourcery.com from comment #3)
> > 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.
> 
> Apparently some folks use linker scripts to get a specific arrangement of
> objects.
> 
> A fresh example is a problem in Linux -- https://lkml.org/lkml/2016/6/25/77
> . A simplified example from http://pastebin.com/4Qc6pUAA :
> 
> extern int __start[];
> extern int __end[];
>  
> extern void bar(int *);
>  
> void foo()
> {
> for (int *x = __start; x != __end; ++x)
> bar(x);
> }


To get around the above example:
extern int __start[];
extern int __end[];

extern void bar(int *);

void foo()
{
int *x = __start;
int *y = __end;
asm("":"+r"(x));
asm("":"+r"(y));
for (; x != y; ++x)
bar(x);
}

> 
> This is optimized into an infinite loop by gcc 7 at -O.

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

[ch3root at openwall dot com]

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

--- Comment #19 from Alexander Cherepanov  ---
(In reply to jos...@codesourcery.com from comment #3)
> 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.

Apparently some folks use linker scripts to get a specific arrangement of
objects.

A fresh example is a problem in Linux -- https://lkml.org/lkml/2016/6/25/77 . A
simplified example from http://pastebin.com/4Qc6pUAA :

extern int __start[];
extern int __end[];

extern void bar(int *);

void foo()
{
for (int *x = __start; x != __end; ++x)
bar(x);
}

This is optimized into an infinite loop by gcc 7 at -O.

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

[ch3root at openwall dot com]

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

--- Comment #18 from Alexander Cherepanov  ---
A bit simplified variant:

#include 

int main()
{
   int x, y = 1;
   int *volatile v;
   int *p;

   v = 
   p = v;
   if (p ==  + 1) {
 *p = 2;
 printf("y = %d\n", y);
   }
}

077t.alias dump shows such "Points-to sets" (among others):

v = { y }
p_5 = { y } same as v

and then the code:

   :
   *p_5 = 2;
   y.0_7 = y;
   printf ("y = %d\n", y.0_7);

Seems right.

081t.vrp1 dump shows such "Value ranges after VRP":

p_11: [[(void *) + 4B], [(void *) + 4B]]  EQUIVALENCES: { 
p_5 } (1 elements)

and the code:

   :
   MEM[(int *) + 4B] = 2;
   y.0_7 = y;
   printf ("y = %d\n", y.0_7);

Seems wrong.

gcc 5.2.0

On 2015-11-16 01:30, ch3root at openwall dot com wrote:
> I guess it depends on the transitivity of the == operator. After this bug is
> fixed it will be possible to constuct a third pointer r from two pointer p and
> q such that r == p and r == q but p != q. For p and q take  + 1 and  as
> above, obtain r by stripping provenance info from p or q (e.g. by printf/scanf
> with %p).

This bug turned out to be not that tricky after all. The program:

#include 

int main()
{
   int x, y;
   void *p =  + 1, *q = , *r;

   /* Strip p of provenance info */
   /* To simplify testing: */
   char s[100]; sprintf(s, "%p", p); sscanf(s, "%p", );
   /* Instead, imagine this:
   printf("%p or %p? ", p, q); scanf("%p", );
   */

   char *eq[] = {"!=", "=="};
   printf("r %s p, r %s q, p %s q\n", eq[r == p], eq[r == q], eq[p == q]);
}

prints "r == p, r == q, p != q" and the first two equalities are 
essentially mandated by C11 (unless you patch it by making one of them UB).

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

[ch3root at openwall dot com]

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

Alexander Cherepanov  changed:

   What|Removed |Added

 CC||ch3root at openwall dot com

--- Comment #17 from Alexander Cherepanov  ---
(In reply to jos...@codesourcery.com from comment #1)
> Just because two pointers print the same and have the same bit-pattern 
> doesn't mean they need to compare equal

The standard seems to disagree. C11, 6.2.6.1p4: "Two values (other than NaNs)
with the same object representation compare equal".

;-)

(In reply to jos...@codesourcery.com from comment #3)
> 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.

I guess it depends on the transitivity of the == operator. After this bug is
fixed it will be possible to constuct a third pointer r from two pointer p and
q such that r == p and r == q but p != q. For p and q take  + 1 and  as
above, obtain r by stripping provenance info from p or q (e.g. by printf/scanf
with %p).

My impression is that the text of the standard implies interchangability of
equal pointers (and hence transitivity of == ) but this area is underspecified
and probably could be fixed in a way that doesn't imply transitivity of == .
But is gcc ok with this? This bug and pr65752 show some complexities. OTOH ==
is not reflexive for double and it's ok.

[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

[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

[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

[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

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