Bug 92963 - Optimization with `restrict`: is `p == q ? p : q` "based" on `p`?
Summary: Optimization with `restrict`: is `p == q ? p : q` "based" on `p`?
Status: UNCONFIRMED
Alias: None
Product: gcc
Classification: Unclassified
Component: tree-optimization (show other bugs)
Version: 10.0
: P3 normal
Target Milestone: ---
Assignee: Not yet assigned to anyone
URL:
Keywords: alias
Depends on:
Blocks: restrict
  Show dependency treegraph
 
Reported: 2019-12-16 21:40 UTC by Alexander Cherepanov
Modified: 2021-12-24 04:33 UTC (History)
1 user (show)

See Also:
Host:
Target:
Build:
Known to work:
Known to fail:
Last reconfirmed:


Attachments

Note You need to log in before you can comment on or make changes to this bug.
Description Alexander Cherepanov 2019-12-16 21:40:02 UTC
The question: is `p == q ? p : q` "based" on `p` (as in C11, 6.7.3.1p3)?

First, suppose that the answer is "yes". Then the following program should be strictly conforming and should always print "2":

----------------------------------------------------------------------
#include <stdio.h>

__attribute__((__noinline__)) // imagine it in a separate TU
static int f(int *restrict p, int *restrict q)
{
    *p = 1;
    
    int *r;
    if (p == q)
        r = p;
    else
        r = q;

    // is r "based" on p?
    
    *r = 2;

    return *p;
}

int main()
{
    int x;
    printf("%d\n", f(&x, &x));
}
----------------------------------------------------------------------
$ gcc -std=c11 test.c && ./a.out
2
$ gcc -std=c11 -O3 test.c && ./a.out
1
----------------------------------------------------------------------
gcc x86-64 version: gcc (GCC) 10.0.0 20191216 (experimental)
----------------------------------------------------------------------

Ok, fair enough, `p == q ? p : q` is always equal to `q`, doesn't change when `p` changes and, thus, is not "based" on `p`.
Then the following program (3 differences are marked) should be fine according to the standard and should always print "2":

----------------------------------------------------------------------
#include <stdio.h>

__attribute__((__noinline__)) // imagine it in a separate TU
static int f(int *restrict p, int *restrict q)
{
    *q = 1; // 1) changed p -> q
    
    int *r;
    if (p == q)
        r = p;
    else
        r = q;

    // is r "based" on p?
    
    if (p == q) // 2) added if
        *r = 2;

    return *q; // 3) changed p -> q
}

int main()
{
    int x;
    printf("%d\n", f(&x, &x));
}
----------------------------------------------------------------------
$ gcc -std=c11 test.c && ./a.out
2
$ gcc -std=c11 -O3 test.c && ./a.out
1
----------------------------------------------------------------------

Either way, there is a problem...
Comment 1 Andrew Pinski 2019-12-16 21:50:32 UTC
Take:

    if (p == q)
        r = p;
    else
        r = q;

p cannot be q as they cannot be based on each other based on my reading of 6.7.3.1p3.

Therefore r is only ever based on q.
Comment 2 Alexander Cherepanov 2019-12-16 22:22:43 UTC
> p cannot be q as they cannot be based on each other based on my reading of
> 6.7.3.1p3.

Perhaps something like that was intended at some point but I don't see it in the text. Until you start analyzing actual accesses you cannot draw any conclusions about values of p and q. Example 3 in the formal definition of restrict (C11, 6.7.3.1p10) specifically illustrates the case of two equal restricted pointers.
Comment 3 Richard Biener 2020-01-08 13:56:48 UTC
To GCC the "mixing" makes it conservative, not assessing any 'restrict' on
r and thus not disambiguate.  Then we're jump-threading the second branch
and thus instead of *r = 2 we suddenly see *p = 2 and that's _not_
aliasing the load from *q because you said so.

That is, you're trying to use 'r' as a mean to make p based on q (or the
other way around).  That's probably not intended.

Of course GCC comes along and makes r which might be based on p with some
reading using q instead which clearly isn't.

So yes, all this lexical semantic reasoning easily breaks down with an
optimizing compiler.  (and all this pointer provenance nonsense)

I'm not convinced this is a bug in GCC.  That you do if (p == q) is a good
hint at that you're doing something not intended.