Bug 93051 - Wrong optimizations for pointers: `if (p == q) use p` -> `if (p == q) use q`
Summary: Wrong optimizations for pointers: `if (p == q) use p` -> `if (p == q) use q`
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: wrong-code
: 103343 (view as bug list)
Depends on: 61502 65752 93052
Blocks:
  Show dependency treegraph
 
Reported: 2019-12-23 12:59 UTC by Alexander Cherepanov
Modified: 2021-11-22 23:13 UTC (History)
2 users (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-23 12:59:35 UTC
The optimizer sometimes changes `if (p == q) use p` to `if (p == q) use q` if it can track the provenance of `q` but not of `p`. This is wrong when the actual provenance of `p` differs from that of `q`.

Examples demonstrate the problem in different cases:
- with integers and with live pointers (to show that the problem is not in casts to integers);
- with past-the-end pointers and without them (to show that even changing the standard to make their comparisons UB will not help);
- with two allocations and with only one (to show that it's not related to how memory is allocated by the compiler/libc).
Plus, all examples behaves quite well:
- respect provenance of pointers including via casts to integers (so this bug is not about (im)possibility to clear provenance by casts to integers or something);
- use only one comparison (so the question of its stability is not touched).

There is some previous analysis of propagation of conditional equivalences in other bugs, e.g., pr65752#c52, pr61502#c25.

Somewhat more general clang bug -- https://bugs.llvm.org/show_bug.cgi?id=44313. Previous lengthy discussion is in https://bugs.llvm.org/show_bug.cgi?id=34548.

Example with a past-the-end pointer (the wrong optimization seems to be applied in vrp1):

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

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

int main()
{
    int x[5];
    int y[1];
    
    int *p = x;
    int *q = y + 1;

    int *r = opaque(p); // hide provenance of p
    if (r == q) {
        *p = 1;
        *r = 2;
        printf("result: %d\n", *p);
    }

    opaque(q);
}
----------------------------------------------------------------------
$ gcc -std=c11 -pedantic -Wall -Wextra -Wno-attributes test.c && ./a.out
result: 2
$ gcc -std=c11 -pedantic -Wall -Wextra -Wno-attributes -O3 test.c && ./a.out
test.c: In function ‘main’:
test.c:17:9: warning: array subscript 1 is outside array bounds of ‘int[1]’ [-Warray-bounds]
   17 |         *r = 2;
      |         ^~
test.c:9:9: note: while referencing ‘y’
    9 |     int y[1];
      |         ^
result: 1
----------------------------------------------------------------------
gcc x86-64 version: gcc (GCC) 10.0.0 20191223 (experimental)
----------------------------------------------------------------------

The warning nicely illustrates the problem:-)

Based on the example from Harald van Dijk in pr61502#c4.
Comment 1 Alexander Cherepanov 2019-12-23 13:00:31 UTC
Example with a restricted pointer (dom2):

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

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

__attribute__((noipa)) // imagine it in a separate TU
static void f(int *restrict p, int *restrict q)
{
    int *r = opaque(p); // hide provenance of p
    if (r == q) {
        *p = 1;
        *r = 2;
        printf("result: %d\n", *p);
    }

    opaque(q);
}

int main()
{
    int x;
    f(&x, &x);
}
----------------------------------------------------------------------
$ gcc -std=c11 -pedantic -Wall -Wextra -Wno-attributes test.c && ./a.out
test.c: In function ‘main’:
test.c:22:7: warning: passing argument 1 to ‘restrict’-qualified parameter aliases with argument 2 [-Wrestrict]
   22 |     f(&x, &x);
      |       ^~  ~~
result: 2
$ gcc -std=c11 -pedantic -Wall -Wextra -Wno-attributes -O3 test.c && ./a.out
test.c: In function ‘main’:
test.c:22:7: warning: passing argument 1 to ‘restrict’-qualified parameter aliases with argument 2 [-Wrestrict]
   22 |     f(&x, &x);
      |       ^~  ~~
result: 1
----------------------------------------------------------------------
gcc x86-64 version: gcc (GCC) 10.0.0 20191223 (experimental)
----------------------------------------------------------------------

Strictly speaking this example is not about provenance (both pointers have the same provenance) but, for the optimizer, different restricted pointers probably play similar roles.

Despite the warning, equal restricted pointers are fine per se -- see, e.g., Example 3 in C11, 6.7.3.1p10.
Comment 2 Alexander Cherepanov 2019-12-23 13:01:14 UTC
Example with a dead malloc (not in tree-opt):

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

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

int main()
{
    int *q = malloc(sizeof(int));
    uintptr_t iq = (uintptr_t)(void *)q;
    free(q);

    int *p = malloc(sizeof(int));

    uintptr_t ir = (uintptr_t)(void *)opaque(p); // hide provenance of p

    if (ir == iq) {
        *p = 1;
        *(int *)ir = 2;
        printf("result: %d\n", *p);
    }
}
----------------------------------------------------------------------
$ gcc -std=c11 -pedantic -Wall -Wextra -Wno-attributes test.c && ./a.out
result: 2
$ gcc -std=c11 -pedantic -Wall -Wextra -Wno-attributes -O3 test.c && ./a.out
result: 1
----------------------------------------------------------------------
gcc x86-64 version: gcc (GCC) 10.0.0 20191223 (experimental)
----------------------------------------------------------------------
Comment 3 Alexander Cherepanov 2019-12-24 17:23:14 UTC
For completeness, an example with a guessed pointer, based on the testcase from bug 65752, comment 0, gcc-only (dom2):

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

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

int main()
{
    int x;
    int *p = &x;
    uintptr_t ip = (uintptr_t)p;

    uintptr_t iq = 0;
    while (iq < ip)
        iq++;

    uintptr_t ir = opaque_to_int(p); // hide provenance of p

    if (ir == iq) {
        *p = 1;
        *(int *)ir = 2;
        printf("result: %d\n", *p);
    }
}
----------------------------------------------------------------------
$ gcc -std=c11 -pedantic -Wall -Wextra -O3 test.c && ./a.out
result: 1
----------------------------------------------------------------------
gcc x86-64 version: gcc (GCC) 10.0.0 20191224 (experimental)
----------------------------------------------------------------------
Comment 4 Richard Biener 2020-01-09 08:42:47 UTC
There's duplicates about this conditional propagation issue.  It also applies to integers since we track provenance through them as well.

Not sure if it's really useful to have yet another bug about this.
Comment 5 Andrew Pinski 2021-11-22 23:13:53 UTC
*** Bug 103343 has been marked as a duplicate of this bug. ***