pointer comparison in GIMPLE

pointer comparison in GIMPLE

[Krister Walfridsson]

I have a problem in smtgcc with the semantics of pointer comparison in 
GIMPLE.

Consider the function foo:

   void foo(char *p, long long i)
   {
     char a;
     if (p + i == &a)
       __builtin_abort();
   }

The FRE pass determines that the condition is always false, and the 
if-statement is removed. This is correct in the C semantics, as the only 
way the condition can be true invokes undefined behavior. But GIMPLE is 
more permissive, so p + i may in fact evaluate to the address of a. So 
something else is needed to allow this optimization for GIMPLE.

This could easily be fixed by letting EQ_EXPR evaluate to false for 
pointers with different provenance. But that makes other optimizations 
invalid because then p > q, p == q, and p < q can all be false 
simultaneously.

So I guess I am missing something... Why is this optimization allowed on 
GIMPLE?

    /Krister

Re: pointer comparison in GIMPLE

[Richard Biener]

> Am 10.12.2025 um 04:53 schrieb Krister Walfridsson via Gcc <gcc@gcc.gnu.org>:
> 
> I have a problem in smtgcc with the semantics of pointer comparison in GIMPLE.
> 
> Consider the function foo:
> 
>  void foo(char *p, long long i)
>  {
>    char a;
>    if (p + i == &a)
>      __builtin_abort();
>  }
> 
> The FRE pass determines that the condition is always false, and the if-statement is removed. This is correct in the C semantics, as the only way the condition can be true invokes undefined behavior. But GIMPLE is more permissive, so p + i may in fact evaluate to the address of a. So something else is needed to allow this optimization for GIMPLE.
> 
> This could easily be fixed by letting EQ_EXPR evaluate to false for pointers with different provenance. But that makes other optimizations invalid because then p > q, p == q, and p < q can all be false simultaneously.
> 
> So I guess I am missing something... Why is this optimization allowed on GIMPLE?

We do the optimization based on pointer analysis which computes provenance that’s useful for alias analysis.  GIMPLE does not optimize relational compares this way - while those are UB we do not decide one way or the other IIRC.

IIRC only relational compares between different provenance pointers invoke UB in C, equality compares do not?

Richard 

> 
>   /Krister

Re: pointer comparison in GIMPLE

[Krister Walfridsson]

[-- Attachment #1: Type: TEXT/PLAIN, Size: 2424 bytes --]

On Wed, 10 Dec 2025, Richard Biener wrote:

> Date: Wed, 10 Dec 2025 08:18:49 +0100
> From: Richard Biener <richard.guenther@gmail.com>
> To: Krister Walfridsson <krister.walfridsson@gmail.com>
> Cc: gcc@gcc.gnu.org
> Subject: Re: pointer comparison in GIMPLE
> 
>
>
>> Am 10.12.2025 um 04:53 schrieb Krister Walfridsson via Gcc <gcc@gcc.gnu.org>:
>>
>> I have a problem in smtgcc with the semantics of pointer comparison in GIMPLE.
>>
>> Consider the function foo:
>>
>>  void foo(char *p, long long i)
>>  {
>>    char a;
>>    if (p + i == &a)
>>      __builtin_abort();
>>  }
>>
>> The FRE pass determines that the condition is always false, and the if-statement is removed. This is correct in the C semantics, as the only way the condition can be true invokes undefined behavior. But GIMPLE is more permissive, so p + i may in fact evaluate to the address of a. So something else is needed to allow this optimization for GIMPLE.
>>
>> This could easily be fixed by letting EQ_EXPR evaluate to false for pointers with different provenance. But that makes other optimizations invalid because then p > q, p == q, and p < q can all be false simultaneously.
>>
>> So I guess I am missing something... Why is this optimization allowed on GIMPLE?
>
> We do the optimization based on pointer analysis which computes provenance that’s useful for alias analysis.  GIMPLE does not optimize relational compares this way - while those are UB we do not decide one way or the other IIRC.

But my point is that the GIMPLE semantics do not allow you to conclude 
that the pointers do not alias!

In C, a pointer must point into an object (or one past it), otherwise the 
behavior is undefined. So we know that p points into some object (or one 
past it), and p + i must also point into that same object (or one past 
it). Therefore it cannot be equal to &a (at least if we assume there is at 
least a one-byte gap at the start of the stack, or we can argue as in the 
comments of PR61502).

The problem is that in GIMPLE, a pointer does not need to be in bounds. 
The caller could call the function with a value of i such that p + i 
happens to be equal to &a. So, as I understand it, the GIMPLE semantics 
do not allow the pass to conclude that p + i == &a is false, unless p + i 
is dereferenced (because dereferencing a through p + i would be UB due to 
provenance).

    /Krister

Re: pointer comparison in GIMPLE

[Martin Uecker]

Am Mittwoch, dem 10.12.2025 um 03:51 +0000 schrieb Krister Walfridsson via Gcc:
> I have a problem in smtgcc with the semantics of pointer comparison in 
> GIMPLE.
> 
> Consider the function foo:
> 
>    void foo(char *p, long long i)
>    {
>      char a;
>      if (p + i == &a)
>        __builtin_abort();
>    }
> 
> The FRE pass determines that the condition is always false, and the 
> if-statement is removed. This is correct in the C semantics, as the only 
> way the condition can be true invokes undefined behavior. But GIMPLE is 
> more permissive, so p + i may in fact evaluate to the address of a. So 
> something else is needed to allow this optimization for GIMPLE.
> 
> This could easily be fixed by letting EQ_EXPR evaluate to false for 
> pointers with different provenance. But that makes other optimizations 
> invalid because then p > q, p == q, and p < q can all be false 
> simultaneously.
> 
> So I guess I am missing something... Why is this optimization allowed on 
> GIMPLE?

Are the precise GIMPLE semantics documented somewhere?   I would guess that
some notion of provenance would be criticial also for GIMPLE.


Martin 


> 
>     /Krister

Re: pointer comparison in GIMPLE

[Richard Biener]

> Am 10.12.2025 um 09:07 schrieb Krister Walfridsson <krister.walfridsson@gmail.com>:
> 
> On Wed, 10 Dec 2025, Richard Biener wrote:
> 
>> Date: Wed, 10 Dec 2025 08:18:49 +0100
>> From: Richard Biener <richard.guenther@gmail.com>
>> To: Krister Walfridsson <krister.walfridsson@gmail.com>
>> Cc: gcc@gcc.gnu.org
>> Subject: Re: pointer comparison in GIMPLE
>> 
>> 
>>>> Am 10.12.2025 um 04:53 schrieb Krister Walfridsson via Gcc <gcc@gcc.gnu.org>:
>>> 
>>> I have a problem in smtgcc with the semantics of pointer comparison in GIMPLE.
>>> 
>>> Consider the function foo:
>>> 
>>> void foo(char *p, long long i)
>>> {
>>>   char a;
>>>   if (p + i == &a)
>>>     __builtin_abort();
>>> }
>>> 
>>> The FRE pass determines that the condition is always false, and the if-statement is removed. This is correct in the C semantics, as the only way the condition can be true invokes undefined behavior. But GIMPLE is more permissive, so p + i may in fact evaluate to the address of a. So something else is needed to allow this optimization for GIMPLE.
>>> 
>>> This could easily be fixed by letting EQ_EXPR evaluate to false for pointers with different provenance. But that makes other optimizations invalid because then p > q, p == q, and p < q can all be false simultaneously.
>>> 
>>> So I guess I am missing something... Why is this optimization allowed on GIMPLE?
>> 
>> We do the optimization based on pointer analysis which computes provenance that’s useful for alias analysis.  GIMPLE does not optimize relational compares this way - while those are UB we do not decide one way or the other IIRC.
> 
> But my point is that the GIMPLE semantics do not allow you to conclude that the pointers do not alias!
> 
> In C, a pointer must point into an object (or one past it), otherwise the behavior is undefined. So we know that p points into some object (or one past it), and p + i must also point into that same object (or one past it). Therefore it cannot be equal to &a (at least if we assume there is at least a one-byte gap at the start of the stack, or we can argue as in the comments of PR61502).
> 
> The problem is that in GIMPLE, a pointer does not need to be in bounds. The caller could call the function with a value of i such that p + i happens to be equal to &a. So, as I understand it, the GIMPLE semantics do not allow the pass to conclude that p + i == &a is false, unless p + i is dereferenced (because dereferencing a through p + i would be UB due to provenance).

GIMPLE adopts most of the C pointer restrictions here thus we can (and do) conclude that pointers stay within an object when advanced.  This is used by the PTA pass which results are used when we optimize your example.  You have to divert to integer arithmetic to circumvent this and the PTA pass, while tracking provenance through integers as well, does the right thing with this.

Richard 

> 
>   /Krister

Re: pointer comparison in GIMPLE

[Krister Walfridsson]

On Wed, 10 Dec 2025, Richard Biener wrote:

>> The problem is that in GIMPLE, a pointer does not need to be in bounds. The caller could call the function with a value of i such that p + i happens to be equal to &a. So, as I understand it, the GIMPLE semantics do not allow the pass to conclude that p + i == &a is false, unless p + i is dereferenced (because dereferencing a through p + i would be UB due to provenance).
>
> GIMPLE adopts most of the C pointer restrictions here thus we can (and do) conclude that pointers stay within an object when advanced.  This is used by the PTA pass which results are used when we optimize your example.  You have to divert to integer arithmetic to circumvent this and the PTA pass, while tracking provenance through integers as well, does the right thing with this.

Great, that is much better for smtgcc than the semantics I have currently 
implemented!

But it is not completely clear to me what "most of the C pointer 
restrictions" implies. Is the following a correct interpretation?

1. A pointer must contain a value that points into (or one past) an object 
corresponding to its provenance (where a pointer may have multiple 
provenances). Otherwise it invokes undefined behavior.

2. The provenance used for the result of POINTER_PLUS is the union of the 
provenances for the two arguments.

3. The POINTER_PLUS operation is UB if the calculation overflows and 
TYPE_OVERFLOW_WRAPS(ptr_type) is false.

4. The rules are the same for the calculations done in MEM_REF and 
TARGET_MEM_REF as for POINTER_PLUS.

Question: For the TARGET_MEM_REF calculation:
   BASE + STEP * INDEX + INDEX2 + OFFSET
Is it treated as one POINTER_PLUS, i.e.
   BASE + (STEP * INDEX + INDEX2 + OFFSET)
or as two (i.e. do we care about overflow and OOB between the two index 
calculations)?


FWIW, the vectorizer and ivopts do introduce pointers that are outside the 
object (which is why I allowed it in my current semantics)...

    /Krister

Re: pointer comparison in GIMPLE

[Krister Walfridsson]

On Wed, 10 Dec 2025, Martin Uecker wrote:

> Date: Wed, 10 Dec 2025 09:11:14 +0100
> From: Martin Uecker <muecker@gwdg.de>
> To: Krister Walfridsson <krister.walfridsson@gmail.com>, gcc@gcc.gnu.org
> Cc: Richard Biener <richard.guenther@gmail.com>
> Subject: Re: pointer comparison in GIMPLE
> 
> Am Mittwoch, dem 10.12.2025 um 03:51 +0000 schrieb Krister Walfridsson via Gcc:
>> I have a problem in smtgcc with the semantics of pointer comparison in
>> GIMPLE.
>>
>> Consider the function foo:
>>
>>    void foo(char *p, long long i)
>>    {
>>      char a;
>>      if (p + i == &a)
>>        __builtin_abort();
>>    }
>>
>> The FRE pass determines that the condition is always false, and the
>> if-statement is removed. This is correct in the C semantics, as the only
>> way the condition can be true invokes undefined behavior. But GIMPLE is
>> more permissive, so p + i may in fact evaluate to the address of a. So
>> something else is needed to allow this optimization for GIMPLE.
>>
>> This could easily be fixed by letting EQ_EXPR evaluate to false for
>> pointers with different provenance. But that makes other optimizations
>> invalid because then p > q, p == q, and p < q can all be false
>> simultaneously.
>>
>> So I guess I am missing something... Why is this optimization allowed on
>> GIMPLE?
>
> Are the precise GIMPLE semantics documented somewhere?   I would guess that
> some notion of provenance would be criticial also for GIMPLE.

It is, to my knowledge, not conveniently documented in one place, even 
though the information is probably available spread out across the 
internals manual, various .def files, and comments in the source code.

I plan to write some documentation when I have fully figured out the 
rules. The following two earlier mail threads and bug report are part of 
that effort:
* https://gcc.gnu.org/pipermail/gcc/2025-March/245763.html
* https://gcc.gnu.org/pipermail/gcc/2025-April/245870.html
* https://gcc.gnu.org/bugzilla/show_bug.cgi?id=120980

    /Krister

Re: pointer comparison in GIMPLE

[Jose E. Marchesi]

> On Wed, 10 Dec 2025, Martin Uecker wrote:
>
>> Date: Wed, 10 Dec 2025 09:11:14 +0100
>> From: Martin Uecker <muecker@gwdg.de>
>> To: Krister Walfridsson <krister.walfridsson@gmail.com>, gcc@gcc.gnu.org
>> Cc: Richard Biener <richard.guenther@gmail.com>
>> Subject: Re: pointer comparison in GIMPLE
>> Am Mittwoch, dem 10.12.2025 um 03:51 +0000 schrieb Krister
>> Walfridsson via Gcc:
>>> I have a problem in smtgcc with the semantics of pointer comparison in
>>> GIMPLE.
>>>
>>> Consider the function foo:
>>>
>>>    void foo(char *p, long long i)
>>>    {
>>>      char a;
>>>      if (p + i == &a)
>>>        __builtin_abort();
>>>    }
>>>
>>> The FRE pass determines that the condition is always false, and the
>>> if-statement is removed. This is correct in the C semantics, as the only
>>> way the condition can be true invokes undefined behavior. But GIMPLE is
>>> more permissive, so p + i may in fact evaluate to the address of a. So
>>> something else is needed to allow this optimization for GIMPLE.
>>>
>>> This could easily be fixed by letting EQ_EXPR evaluate to false for
>>> pointers with different provenance. But that makes other optimizations
>>> invalid because then p > q, p == q, and p < q can all be false
>>> simultaneously.
>>>
>>> So I guess I am missing something... Why is this optimization allowed on
>>> GIMPLE?
>>
>> Are the precise GIMPLE semantics documented somewhere?   I would guess that
>> some notion of provenance would be criticial also for GIMPLE.
>
> It is, to my knowledge, not conveniently documented in one place, even
> though the information is probably available spread out across the
> internals manual, various .def files, and comments in the source code.
>
> I plan to write some documentation when I have fully figured out the
> rules. The following two earlier mail threads and bug report are part
> of that effort:
> * https://gcc.gnu.org/pipermail/gcc/2025-March/245763.html
> * https://gcc.gnu.org/pipermail/gcc/2025-April/245870.html
> * https://gcc.gnu.org/bugzilla/show_bug.cgi?id=120980

That would be really awesome.

Re: pointer comparison in GIMPLE

[Martin Uecker]

Am Donnerstag, dem 11.12.2025 um 04:12 +0000 schrieb Krister Walfridsson via Gcc:
> On Wed, 10 Dec 2025, Richard Biener wrote:
> 
> > > The problem is that in GIMPLE, a pointer does not need to be in bounds. The caller could call the function with a value of i such that p + i happens to be equal to &a. So, as I understand it, the GIMPLE semantics do not allow the pass to conclude that p + i == &a is false, unless p + i is dereferenced (because dereferencing a through p + i would be UB due to provenance).
> > 
> > GIMPLE adopts most of the C pointer restrictions here thus we can (and do) conclude that pointers stay within an object when advanced.  This is used by the PTA pass which results are used when we optimize your example.  You have to divert to integer arithmetic to circumvent this and the PTA pass, while tracking provenance through integers as well, does the right thing with this.
> 
> Great, that is much better for smtgcc than the semantics I have currently 
> implemented!
> 
> But it is not completely clear to me what "most of the C pointer 
> restrictions" implies. Is the following a correct interpretation?
> 
> 1. A pointer must contain a value that points into (or one past) an object 
> corresponding to its provenance (where a pointer may have multiple 
> provenances). Otherwise it invokes undefined behavior.
> 
> 2. The provenance used for the result of POINTER_PLUS is the union of the 
> provenances for the two arguments.

Note that in C one argument would be an integer and there is no
provenance on integers in C as this can not work consistently.

(and I think GCC gets this wrong)

Martin


> 
> 3. The POINTER_PLUS operation is UB if the calculation overflows and 
> TYPE_OVERFLOW_WRAPS(ptr_type) is false.
> 
> 4. The rules are the same for the calculations done in MEM_REF and 
> TARGET_MEM_REF as for POINTER_PLUS.
> 
> Question: For the TARGET_MEM_REF calculation:
>    BASE + STEP * INDEX + INDEX2 + OFFSET
> Is it treated as one POINTER_PLUS, i.e.
>    BASE + (STEP * INDEX + INDEX2 + OFFSET)
> or as two (i.e. do we care about overflow and OOB between the two index 
> calculations)?
> 
> 
> FWIW, the vectorizer and ivopts do introduce pointers that are outside the 
> object (which is why I allowed it in my current semantics)...
> 
>     /Krister

Re: pointer comparison in GIMPLE

[Richard Biener]

On Thu, Dec 11, 2025 at 5:12 AM Krister Walfridsson
<krister.walfridsson@gmail.com> wrote:
>
> On Wed, 10 Dec 2025, Richard Biener wrote:
>
> >> The problem is that in GIMPLE, a pointer does not need to be in bounds. The caller could call the function with a value of i such that p + i happens to be equal to &a. So, as I understand it, the GIMPLE semantics do not allow the pass to conclude that p + i == &a is false, unless p + i is dereferenced (because dereferencing a through p + i would be UB due to provenance).
> >
> > GIMPLE adopts most of the C pointer restrictions here thus we can (and do) conclude that pointers stay within an object when advanced.  This is used by the PTA pass which results are used when we optimize your example.  You have to divert to integer arithmetic to circumvent this and the PTA pass, while tracking provenance through integers as well, does the right thing with this.
>
> Great, that is much better for smtgcc than the semantics I have currently
> implemented!
>
> But it is not completely clear to me what "most of the C pointer
> restrictions" implies. Is the following a correct interpretation?
>
> 1. A pointer must contain a value that points into (or one past) an object
> corresponding to its provenance (where a pointer may have multiple
> provenances). Otherwise it invokes undefined behavior.

Hmm.  I think it's only UB when you'd "use" that pointer.  That is, PTA would
compute the points-to set to 'nothing'.  The immediate consequences are such
pointer isn't equal to any other pointer and accesses through it alias
with nothing,
stores would be DSEd.  But at the point a SSA var is assigned such a pointer
we couldn't place a trap() (?)

> 2. The provenance used for the result of POINTER_PLUS is the union of the
> provenances for the two arguments.

For POINTER_PLUS it's the provenance of the first argument.

For PLUS_EXPR it is the union of both arguments.  For POINTER_DIFF_EXPR
the result has no provenance.

> 3. The POINTER_PLUS operation is UB if the calculation overflows and
> TYPE_OVERFLOW_WRAPS(ptr_type) is false.

Yes.

> 4. The rules are the same for the calculations done in MEM_REF and
> TARGET_MEM_REF as for POINTER_PLUS.

Yes.

> Question: For the TARGET_MEM_REF calculation:
>    BASE + STEP * INDEX + INDEX2 + OFFSET
> Is it treated as one POINTER_PLUS, i.e.
>    BASE + (STEP * INDEX + INDEX2 + OFFSET)
> or as two (i.e. do we care about overflow and OOB between the two index
> calculations)?

I'd say it counts as one pointer + offset calculation with all the offset
calculation being done in wrapping operations.

>
>
> FWIW, the vectorizer and ivopts do introduce pointers that are outside the
> object (which is why I allowed it in my current semantics)...

But only "slightly" ... that is, we consider it having the objects provenance
still given the vectorizer/ivopts will ensure actual accesses do not access
another object [in a way a program can observe].

>     /Krister

Re: pointer comparison in GIMPLE

[Richard Biener]

On Thu, Dec 11, 2025 at 7:48 AM Martin Uecker <muecker@gwdg.de> wrote:
>
> Am Donnerstag, dem 11.12.2025 um 04:12 +0000 schrieb Krister Walfridsson via Gcc:
> > On Wed, 10 Dec 2025, Richard Biener wrote:
> >
> > > > The problem is that in GIMPLE, a pointer does not need to be in bounds. The caller could call the function with a value of i such that p + i happens to be equal to &a. So, as I understand it, the GIMPLE semantics do not allow the pass to conclude that p + i == &a is false, unless p + i is dereferenced (because dereferencing a through p + i would be UB due to provenance).
> > >
> > > GIMPLE adopts most of the C pointer restrictions here thus we can (and do) conclude that pointers stay within an object when advanced.  This is used by the PTA pass which results are used when we optimize your example.  You have to divert to integer arithmetic to circumvent this and the PTA pass, while tracking provenance through integers as well, does the right thing with this.
> >
> > Great, that is much better for smtgcc than the semantics I have currently
> > implemented!
> >
> > But it is not completely clear to me what "most of the C pointer
> > restrictions" implies. Is the following a correct interpretation?
> >
> > 1. A pointer must contain a value that points into (or one past) an object
> > corresponding to its provenance (where a pointer may have multiple
> > provenances). Otherwise it invokes undefined behavior.
> >
> > 2. The provenance used for the result of POINTER_PLUS is the union of the
> > provenances for the two arguments.
>
> Note that in C one argument would be an integer and there is no
> provenance on integers in C as this can not work consistently.
>
> (and I think GCC gets this wrong)

What GCC gets "right" (right in terms of improving optimization) is
that (int *)(intptr_t)ptr has the same provenance as ptr.

GCC considers literal zero to have "no" provenance (unless the target
claims objects can exist at address zero).  So (int *)((intptr_t)ptr + 0)
retains the provenance of ptr.  (int *)((intptr_t)ptr + 4) OTOH has
provenance of ptr merged with 'nonlocal' provenance (a literal address
never has provenance of a stack object).  That is, constant folding
loses the fact that (void *)0 + 4 would have "no" provenance (actually
not sure whether the null "object" is subject to pointer arithmetic
constraints).

There's one thing GCC gets wrong (see some PRs) which is
"conditional provenance".

 if (p == q)
   /* we now should treat p and q as having unioned provenance since
      p can be substituted for q (and vice versa) by the compiler.  */

I have not yet seen a good answer to this from the C pointer provenance proposal
folks.

Richard.

>
> Martin
>
>
> >
> > 3. The POINTER_PLUS operation is UB if the calculation overflows and
> > TYPE_OVERFLOW_WRAPS(ptr_type) is false.
> >
> > 4. The rules are the same for the calculations done in MEM_REF and
> > TARGET_MEM_REF as for POINTER_PLUS.
> >
> > Question: For the TARGET_MEM_REF calculation:
> >    BASE + STEP * INDEX + INDEX2 + OFFSET
> > Is it treated as one POINTER_PLUS, i.e.
> >    BASE + (STEP * INDEX + INDEX2 + OFFSET)
> > or as two (i.e. do we care about overflow and OOB between the two index
> > calculations)?
> >
> >
> > FWIW, the vectorizer and ivopts do introduce pointers that are outside the
> > object (which is why I allowed it in my current semantics)...
> >
> >     /Krister

Re: pointer comparison in GIMPLE

[Martin Uecker]

Am Donnerstag, dem 11.12.2025 um 12:48 +0100 schrieb Richard Biener:
> On Thu, Dec 11, 2025 at 7:48 AM Martin Uecker <muecker@gwdg.de> wrote:
> > 
> > Am Donnerstag, dem 11.12.2025 um 04:12 +0000 schrieb Krister Walfridsson via Gcc:
> > > On Wed, 10 Dec 2025, Richard Biener wrote:
> > > 
> > > > > The problem is that in GIMPLE, a pointer does not need to be in bounds. The caller could call the function with a value of i such that p + i happens to be equal to &a. So, as I understand it, the GIMPLE semantics do not allow the pass to conclude that p + i == &a is false, unless p + i is dereferenced (because dereferencing a through p + i would be UB due to provenance).
> > > > 
> > > > GIMPLE adopts most of the C pointer restrictions here thus we can (and do) conclude that pointers stay within an object when advanced.  This is used by the PTA pass which results are used when we optimize your example.  You have to divert to integer arithmetic to circumvent this and the PTA pass, while tracking provenance through integers as well, does the right thing with this.
> > > 
> > > Great, that is much better for smtgcc than the semantics I have currently
> > > implemented!
> > > 
> > > But it is not completely clear to me what "most of the C pointer
> > > restrictions" implies. Is the following a correct interpretation?
> > > 
> > > 1. A pointer must contain a value that points into (or one past) an object
> > > corresponding to its provenance (where a pointer may have multiple
> > > provenances). Otherwise it invokes undefined behavior.
> > > 
> > > 2. The provenance used for the result of POINTER_PLUS is the union of the
> > > provenances for the two arguments.
> > 
> > Note that in C one argument would be an integer and there is no
> > provenance on integers in C as this can not work consistently.
> > 
> > (and I think GCC gets this wrong)
> 
> What GCC gets "right" (right in terms of improving optimization) is
> that (int *)(intptr_t)ptr has the same provenance as ptr.

The problem is nobody could come up with a convincing model
for this that is sound.  Currently GCC breaks the requirement
that roundtrips through integers have to work in all cases 
because sometimes the compiler gets confused about the
provenance of the back-converted pointer and assigns the
wrong one.

The model that *is* sound is to treat conversion to integer as
escaped and pointers converted back from integers as pointing
to any previously escaped provenance.

LLVM also gets this wrong but my understanding is that they
want to fix this.

> 
> GCC considers literal zero to have "no" provenance (unless the target
> claims objects can exist at address zero).  So (int *)((intptr_t)ptr + 0)
> retains the provenance of ptr.  (int *)((intptr_t)ptr + 4) OTOH has
> provenance of ptr merged with 'nonlocal' provenance (a literal address
> never has provenance of a stack object).  That is, constant folding
> loses the fact that (void *)0 + 4 would have "no" provenance (actually
> not sure whether the null "object" is subject to pointer arithmetic
> constraints).
> 
> There's one thing GCC gets wrong (see some PRs) which is
> "conditional provenance".
> 
>  if (p == q)
>    /* we now should treat p and q as having unioned provenance since
>       p can be substituted for q (and vice versa) by the compiler.  */
> 
> I have not yet seen a good answer to this from the C pointer provenance proposal
> folks.

I am not sure what answer you want. This optimization is unsound.  

I think one could retain such optimizations by adding some additional
conditions that exclude the special case that p and q have different
provenance but the same address.

Martin

> 
> Richard.
> 
> > 
> > Martin
> > 
> > 
> > > 
> > > 3. The POINTER_PLUS operation is UB if the calculation overflows and
> > > TYPE_OVERFLOW_WRAPS(ptr_type) is false.
> > > 
> > > 4. The rules are the same for the calculations done in MEM_REF and
> > > TARGET_MEM_REF as for POINTER_PLUS.
> > > 
> > > Question: For the TARGET_MEM_REF calculation:
> > >    BASE + STEP * INDEX + INDEX2 + OFFSET
> > > Is it treated as one POINTER_PLUS, i.e.
> > >    BASE + (STEP * INDEX + INDEX2 + OFFSET)
> > > or as two (i.e. do we care about overflow and OOB between the two index
> > > calculations)?
> > > 
> > > 
> > > FWIW, the vectorizer and ivopts do introduce pointers that are outside the
> > > object (which is why I allowed it in my current semantics)...
> > > 
> > >     /Krister

Re: pointer comparison in GIMPLE

[Krister Walfridsson]

[-- Attachment #1: Type: TEXT/PLAIN, Size: 5941 bytes --]

On Thu, 11 Dec 2025, Richard Biener wrote:

> Date: Thu, 11 Dec 2025 12:38:43 +0100
> From: Richard Biener <richard.guenther@gmail.com>
> To: Krister Walfridsson <krister.walfridsson@gmail.com>
> Cc: gcc@gcc.gnu.org
> Subject: Re: pointer comparison in GIMPLE
> 
> On Thu, Dec 11, 2025 at 5:12 AM Krister Walfridsson
> <krister.walfridsson@gmail.com> wrote:
>>
>> On Wed, 10 Dec 2025, Richard Biener wrote:
>>
>>>> The problem is that in GIMPLE, a pointer does not need to be in bounds. The caller could call the function with a value of i such that p + i happens to be equal to &a. So, as I understand it, the GIMPLE semantics do not allow the pass to conclude that p + i == &a is false, unless p + i is dereferenced (because dereferencing a through p + i would be UB due to provenance).
>>>
>>> GIMPLE adopts most of the C pointer restrictions here thus we can (and do) conclude that pointers stay within an object when advanced.  This is used by the PTA pass which results are used when we optimize your example.  You have to divert to integer arithmetic to circumvent this and the PTA pass, while tracking provenance through integers as well, does the right thing with this.
>>
>> Great, that is much better for smtgcc than the semantics I have currently
>> implemented!
>>
>> But it is not completely clear to me what "most of the C pointer
>> restrictions" implies. Is the following a correct interpretation?
>>
>> 1. A pointer must contain a value that points into (or one past) an object
>> corresponding to its provenance (where a pointer may have multiple
>> provenances). Otherwise it invokes undefined behavior.
>
> Hmm.  I think it's only UB when you'd "use" that pointer.  That is, PTA would
> compute the points-to set to 'nothing'.  The immediate consequences are such
> pointer isn't equal to any other pointer and accesses through it alias
> with nothing,
> stores would be DSEd.  But at the point a SSA var is assigned such a pointer
> we couldn't place a trap() (?)
>
>> 2. The provenance used for the result of POINTER_PLUS is the union of the
>> provenances for the two arguments.
>
> For POINTER_PLUS it's the provenance of the first argument.
>
> For PLUS_EXPR it is the union of both arguments.  For POINTER_DIFF_EXPR
> the result has no provenance.
>
>> 3. The POINTER_PLUS operation is UB if the calculation overflows and
>> TYPE_OVERFLOW_WRAPS(ptr_type) is false.
>
> Yes.
>
>> 4. The rules are the same for the calculations done in MEM_REF and
>> TARGET_MEM_REF as for POINTER_PLUS.
>
> Yes.
>
>> Question: For the TARGET_MEM_REF calculation:
>>    BASE + STEP * INDEX + INDEX2 + OFFSET
>> Is it treated as one POINTER_PLUS, i.e.
>>    BASE + (STEP * INDEX + INDEX2 + OFFSET)
>> or as two (i.e. do we care about overflow and OOB between the two index
>> calculations)?
>
> I'd say it counts as one pointer + offset calculation with all the offset
> calculation being done in wrapping operations.

Your answers match exactly what is currently implemented in smtgcc, so I 
am still thinking this is a bug in GCC (or that there is some missing 
GIMPLE rule I must implement).

The original program looks in GIMPLE like:

   void foo (char * p, long long int i)
   {
     char a;
     sizetype i.0_1;
     char * _2;

     <bb 2> :
     i.0_1 = (sizetype) i_3(D);
     _2 = p_4(D) + i.0_1;
     if (_2 == &a)
       goto <bb 3>;
     else
       goto <bb 4>;

     <bb 3> :
     __builtin_abort ();

     <bb 4> :
     a ={v} {CLOBBER(eos)};
     return;
   }

Assume, for the sake of argument, that the address of a is 0x2000000, p = 
0x1000000 and i = 0x1000000.

With the semantics as described in this mail thread, all operations are 
defined:
  * _2 evaluates to 0x2000000, with the provenance of p (although the
    provenance is irrelevant in this execution).
  * The comparison is also defined and evaluates to true.
  * As a result, the program then calls __builtin_abort, which exits.

A valid optimization must produce the same result (including side effects) 
given the same input for executions where all steps have defined 
semantics. Therefore, an optimization that does not call __builtin_abort 
for this input is buggy (or the semantics is incorrect).

You said in your second mail: "GIMPLE adopts most of the C pointer 
restrictions here thus we can (and do) conclude that pointers stay within 
an object when advanced.  This is used by the PTA pass which results are 
used when we optimize your example." which is what I tried to reflect in:

>> 1. A pointer must contain a value that points into (or one past) an object
>> corresponding to its provenance (where a pointer may have multiple
>> provenances). Otherwise it invokes undefined behavior.

But as you say, that is wrong (and the vectorizer and ifconv do indeed 
perform transformations that would be invalid with this semantics). So 
what is the correct rule here for "pointers stay within an object"? All 
ideas I have tried fails in different ways... :(

---

I also have a somewhat related question regarding:

>> 2. The provenance used for the result of POINTER_PLUS is the union of the
>> provenances for the two arguments.
>
> For POINTER_PLUS it's the provenance of the first argument.

>> 4. The rules are the same for the calculations done in MEM_REF and
>> TARGET_MEM_REF as for POINTER_PLUS.
>
> Yes.

The ifconv pass sometimes rewrites memory accesses as:

   _84 = &MEM[(float *)0B + _83 + ivtmp.41_75 * 4];
   MEM[(float *)_84] = _3;

which you can see by compiling testsuite/gcc.dg/sms-11.c for x86_64 with 
-O1.

If TARGET_MEM_REF works like POINTER_PLUS, which does not propagate 
provenance through integers, then this store has no provenance and invokes 
undefined behavior. So is ifopts buggy, or do TARGET_MEM_REF propagate 
provenance from index/offset?

    /Krister

Re: pointer comparison in GIMPLE

[Jason Merrill]

[-- Attachment #1: Type: text/plain, Size: 6451 bytes --]

On Fri, Dec 12, 2025, 8:57 a.m. Krister Walfridsson via Gcc <gcc@gcc.gnu.org>
wrote:

> On Thu, 11 Dec 2025, Richard Biener wrote:
>
> > Date: Thu, 11 Dec 2025 12:38:43 +0100
> > From: Richard Biener <richard.guenther@gmail.com>
> > To: Krister Walfridsson <krister.walfridsson@gmail.com>
> > Cc: gcc@gcc.gnu.org
> > Subject: Re: pointer comparison in GIMPLE
> >
> > On Thu, Dec 11, 2025 at 5:12 AM Krister Walfridsson
> > <krister.walfridsson@gmail.com> wrote:
> >>
> >> On Wed, 10 Dec 2025, Richard Biener wrote:
> >>
> >>>> The problem is that in GIMPLE, a pointer does not need to be in
> bounds. The caller could call the function with a value of i such that p +
> i happens to be equal to &a. So, as I understand it, the GIMPLE semantics
> do not allow the pass to conclude that p + i == &a is false, unless p + i
> is dereferenced (because dereferencing a through p + i would be UB due to
> provenance).
> >>>
> >>> GIMPLE adopts most of the C pointer restrictions here thus we can (and
> do) conclude that pointers stay within an object when advanced.  This is
> used by the PTA pass which results are used when we optimize your example.
> You have to divert to integer arithmetic to circumvent this and the PTA
> pass, while tracking provenance through integers as well, does the right
> thing with this.
> >>
> >> Great, that is much better for smtgcc than the semantics I have
> currently
> >> implemented!
> >>
> >> But it is not completely clear to me what "most of the C pointer
> >> restrictions" implies. Is the following a correct interpretation?
> >>
> >> 1. A pointer must contain a value that points into (or one past) an
> object
> >> corresponding to its provenance (where a pointer may have multiple
> >> provenances). Otherwise it invokes undefined behavior.
> >
> > Hmm.  I think it's only UB when you'd "use" that pointer.  That is, PTA
> would
> > compute the points-to set to 'nothing'.  The immediate consequences are
> such
> > pointer isn't equal to any other pointer and accesses through it alias
> > with nothing,
> > stores would be DSEd.  But at the point a SSA var is assigned such a
> pointer
> > we couldn't place a trap() (?)
> >
> >> 2. The provenance used for the result of POINTER_PLUS is the union of
> the
> >> provenances for the two arguments.
> >
> > For POINTER_PLUS it's the provenance of the first argument.
> >
> > For PLUS_EXPR it is the union of both arguments.  For POINTER_DIFF_EXPR
> > the result has no provenance.
> >
> >> 3. The POINTER_PLUS operation is UB if the calculation overflows and
> >> TYPE_OVERFLOW_WRAPS(ptr_type) is false.
> >
> > Yes.
> >
> >> 4. The rules are the same for the calculations done in MEM_REF and
> >> TARGET_MEM_REF as for POINTER_PLUS.
> >
> > Yes.
> >
> >> Question: For the TARGET_MEM_REF calculation:
> >>    BASE + STEP * INDEX + INDEX2 + OFFSET
> >> Is it treated as one POINTER_PLUS, i.e.
> >>    BASE + (STEP * INDEX + INDEX2 + OFFSET)
> >> or as two (i.e. do we care about overflow and OOB between the two index
> >> calculations)?
> >
> > I'd say it counts as one pointer + offset calculation with all the offset
> > calculation being done in wrapping operations.
>
> Your answers match exactly what is currently implemented in smtgcc, so I
> am still thinking this is a bug in GCC (or that there is some missing
> GIMPLE rule I must implement).
>
> The original program looks in GIMPLE like:
>
>    void foo (char * p, long long int i)
>    {
>      char a;
>      sizetype i.0_1;
>      char * _2;
>
>      <bb 2> :
>      i.0_1 = (sizetype) i_3(D);
>      _2 = p_4(D) + i.0_1;
>      if (_2 == &a)
>        goto <bb 3>;
>      else
>        goto <bb 4>;
>
>      <bb 3> :
>      __builtin_abort ();
>
>      <bb 4> :
>      a ={v} {CLOBBER(eos)};
>      return;
>    }
>
> Assume, for the sake of argument, that the address of a is 0x2000000, p =
> 0x1000000 and i = 0x1000000.
>
> With the semantics as described in this mail thread, all operations are
> defined:
>   * _2 evaluates to 0x2000000, with the provenance of p (although the
>     provenance is irrelevant in this execution).
>   * The comparison is also defined and evaluates to true.
>   * As a result, the program then calls __builtin_abort, which exits.
>
> A valid optimization must produce the same result (including side effects)
> given the same input for executions where all steps have defined
> semantics.


Except this comparison has an unspecified value, so an optimization is
allowed to change it.


Therefore, an optimization that does not call __builtin_abort
> for this input is buggy (or the semantics is incorrect).
>
> You said in your second mail: "GIMPLE adopts most of the C pointer
> restrictions here thus we can (and do) conclude that pointers stay within
> an object when advanced.  This is used by the PTA pass which results are
> used when we optimize your example." which is what I tried to reflect in:
>
> >> 1. A pointer must contain a value that points into (or one past) an
> object
> >> corresponding to its provenance (where a pointer may have multiple
> >> provenances). Otherwise it invokes undefined behavior.
>
> But as you say, that is wrong (and the vectorizer and ifconv do indeed
> perform transformations that would be invalid with this semantics). So
> what is the correct rule here for "pointers stay within an object"? All
> ideas I have tried fails in different ways... :(
>
> ---
>
> I also have a somewhat related question regarding:
>
> >> 2. The provenance used for the result of POINTER_PLUS is the union of
> the
> >> provenances for the two arguments.
> >
> > For POINTER_PLUS it's the provenance of the first argument.
>
> >> 4. The rules are the same for the calculations done in MEM_REF and
> >> TARGET_MEM_REF as for POINTER_PLUS.
> >
> > Yes.
>
> The ifconv pass sometimes rewrites memory accesses as:
>
>    _84 = &MEM[(float *)0B + _83 + ivtmp.41_75 * 4];
>    MEM[(float *)_84] = _3;
>
> which you can see by compiling testsuite/gcc.dg/sms-11.c for x86_64 with
> -O1.
>
> If TARGET_MEM_REF works like POINTER_PLUS, which does not propagate
> provenance through integers, then this store has no provenance and invokes
> undefined behavior. So is ifopts buggy, or do TARGET_MEM_REF propagate
> provenance from index/offset?
>
>     /Krister
>
>

Re: pointer comparison in GIMPLE

[Martin Uecker]

Am Freitag, dem 12.12.2025 um 09:21 +0700 schrieb Jason Merrill via Gcc:
> On Fri, Dec 12, 2025, 8:57 a.m. Krister Walfridsson via Gcc <gcc@gcc.gnu.org>
> wrote:
> 
> > On Thu, 11 Dec 2025, Richard Biener wrote:
> > 
> > > Date: Thu, 11 Dec 2025 12:38:43 +0100
> > > From: Richard Biener <richard.guenther@gmail.com>
> > > To: Krister Walfridsson <krister.walfridsson@gmail.com>
> > > Cc: gcc@gcc.gnu.org
> > > Subject: Re: pointer comparison in GIMPLE
> > > 
> > > On Thu, Dec 11, 2025 at 5:12 AM Krister Walfridsson
> > > <krister.walfridsson@gmail.com> wrote:
> > > > 
> > > > On Wed, 10 Dec 2025, Richard Biener wrote:
> > > > 
> > > > > > The problem is that in GIMPLE, a pointer does not need to be in
> > bounds. The caller could call the function with a value of i such that p +
> > i happens to be equal to &a. So, as I understand it, the GIMPLE semantics
> > do not allow the pass to conclude that p + i == &a is false, unless p + i
> > is dereferenced (because dereferencing a through p + i would be UB due to
> > provenance).
> > > > > 
> > > > > GIMPLE adopts most of the C pointer restrictions here thus we can (and
> > do) conclude that pointers stay within an object when advanced.  This is
> > used by the PTA pass which results are used when we optimize your example.
> > You have to divert to integer arithmetic to circumvent this and the PTA
> > pass, while tracking provenance through integers as well, does the right
> > thing with this.
> > > > 
> > > > Great, that is much better for smtgcc than the semantics I have
> > currently
> > > > implemented!
> > > > 
> > > > But it is not completely clear to me what "most of the C pointer
> > > > restrictions" implies. Is the following a correct interpretation?
> > > > 
> > > > 1. A pointer must contain a value that points into (or one past) an
> > object
> > > > corresponding to its provenance (where a pointer may have multiple
> > > > provenances). Otherwise it invokes undefined behavior.
> > > 
> > > Hmm.  I think it's only UB when you'd "use" that pointer.  That is, PTA
> > would
> > > compute the points-to set to 'nothing'.  The immediate consequences are
> > such
> > > pointer isn't equal to any other pointer and accesses through it alias
> > > with nothing,
> > > stores would be DSEd.  But at the point a SSA var is assigned such a
> > pointer
> > > we couldn't place a trap() (?)
> > > 
> > > > 2. The provenance used for the result of POINTER_PLUS is the union of
> > the
> > > > provenances for the two arguments.
> > > 
> > > For POINTER_PLUS it's the provenance of the first argument.
> > > 
> > > For PLUS_EXPR it is the union of both arguments.  For POINTER_DIFF_EXPR
> > > the result has no provenance.
> > > 
> > > > 3. The POINTER_PLUS operation is UB if the calculation overflows and
> > > > TYPE_OVERFLOW_WRAPS(ptr_type) is false.
> > > 
> > > Yes.
> > > 
> > > > 4. The rules are the same for the calculations done in MEM_REF and
> > > > TARGET_MEM_REF as for POINTER_PLUS.
> > > 
> > > Yes.
> > > 
> > > > Question: For the TARGET_MEM_REF calculation:
> > > >    BASE + STEP * INDEX + INDEX2 + OFFSET
> > > > Is it treated as one POINTER_PLUS, i.e.
> > > >    BASE + (STEP * INDEX + INDEX2 + OFFSET)
> > > > or as two (i.e. do we care about overflow and OOB between the two index
> > > > calculations)?
> > > 
> > > I'd say it counts as one pointer + offset calculation with all the offset
> > > calculation being done in wrapping operations.
> > 
> > Your answers match exactly what is currently implemented in smtgcc, so I
> > am still thinking this is a bug in GCC (or that there is some missing
> > GIMPLE rule I must implement).
> > 
> > The original program looks in GIMPLE like:
> > 
> >    void foo (char * p, long long int i)
> >    {
> >      char a;
> >      sizetype i.0_1;
> >      char * _2;
> > 
> >      <bb 2> :
> >      i.0_1 = (sizetype) i_3(D);
> >      _2 = p_4(D) + i.0_1;
> >      if (_2 == &a)
> >        goto <bb 3>;
> >      else
> >        goto <bb 4>;
> > 
> >      <bb 3> :
> >      __builtin_abort ();
> > 
> >      <bb 4> :
> >      a ={v} {CLOBBER(eos)};
> >      return;
> >    }
> > 
> > Assume, for the sake of argument, that the address of a is 0x2000000, p =
> > 0x1000000 and i = 0x1000000.
> > 
> > With the semantics as described in this mail thread, all operations are
> > defined:
> >   * _2 evaluates to 0x2000000, with the provenance of p (although the
> >     provenance is irrelevant in this execution).
> >   * The comparison is also defined and evaluates to true.
> >   * As a result, the program then calls __builtin_abort, which exits.
> > 
> > A valid optimization must produce the same result (including side effects)
> > given the same input for executions where all steps have defined
> > semantics.
> 
> 
> Except this comparison has an unspecified value, so an optimization is
> allowed to change it.

Is it?  For, C this is defined.

Martin


> 
> 
> Therefore, an optimization that does not call __builtin_abort
> > for this input is buggy (or the semantics is incorrect).
> > 
> > You said in your second mail: "GIMPLE adopts most of the C pointer
> > restrictions here thus we can (and do) conclude that pointers stay within
> > an object when advanced.  This is used by the PTA pass which results are
> > used when we optimize your example." which is what I tried to reflect in:
> > 
> > > > 1. A pointer must contain a value that points into (or one past) an
> > object
> > > > corresponding to its provenance (where a pointer may have multiple
> > > > provenances). Otherwise it invokes undefined behavior.
> > 
> > But as you say, that is wrong (and the vectorizer and ifconv do indeed
> > perform transformations that would be invalid with this semantics). So
> > what is the correct rule here for "pointers stay within an object"? All
> > ideas I have tried fails in different ways... :(
> > 
> > ---
> > 
> > I also have a somewhat related question regarding:
> > 
> > > > 2. The provenance used for the result of POINTER_PLUS is the union of
> > the
> > > > provenances for the two arguments.
> > > 
> > > For POINTER_PLUS it's the provenance of the first argument.
> > 
> > > > 4. The rules are the same for the calculations done in MEM_REF and
> > > > TARGET_MEM_REF as for POINTER_PLUS.
> > > 
> > > Yes.
> > 
> > The ifconv pass sometimes rewrites memory accesses as:
> > 
> >    _84 = &MEM[(float *)0B + _83 + ivtmp.41_75 * 4];
> >    MEM[(float *)_84] = _3;
> > 
> > which you can see by compiling testsuite/gcc.dg/sms-11.c for x86_64 with
> > -O1.
> > 
> > If TARGET_MEM_REF works like POINTER_PLUS, which does not propagate
> > provenance through integers, then this store has no provenance and invokes
> > undefined behavior. So is ifopts buggy, or do TARGET_MEM_REF propagate
> > provenance from index/offset?
> > 
> >     /Krister
> > 
> > 

Re: pointer comparison in GIMPLE

[Jason Merrill]

On 12/12/25 2:10 PM, Martin Uecker wrote:
> Am Freitag, dem 12.12.2025 um 09:21 +0700 schrieb Jason Merrill via Gcc:
>> On Fri, Dec 12, 2025, 8:57 a.m. Krister Walfridsson via Gcc <gcc@gcc.gnu.org>
>> wrote:
>>
>>> On Thu, 11 Dec 2025, Richard Biener wrote:
>>>
>>>> Date: Thu, 11 Dec 2025 12:38:43 +0100
>>>> From: Richard Biener <richard.guenther@gmail.com>
>>>> To: Krister Walfridsson <krister.walfridsson@gmail.com>
>>>> Cc: gcc@gcc.gnu.org
>>>> Subject: Re: pointer comparison in GIMPLE
>>>>
>>>> On Thu, Dec 11, 2025 at 5:12 AM Krister Walfridsson
>>>> <krister.walfridsson@gmail.com> wrote:
>>>>>
>>>>> On Wed, 10 Dec 2025, Richard Biener wrote:
>>>>>
>>>>>>> The problem is that in GIMPLE, a pointer does not need to be in
>>> bounds. The caller could call the function with a value of i such that p +
>>> i happens to be equal to &a. So, as I understand it, the GIMPLE semantics
>>> do not allow the pass to conclude that p + i == &a is false, unless p + i
>>> is dereferenced (because dereferencing a through p + i would be UB due to
>>> provenance).
>>>>>>
>>>>>> GIMPLE adopts most of the C pointer restrictions here thus we can (and
>>> do) conclude that pointers stay within an object when advanced.  This is
>>> used by the PTA pass which results are used when we optimize your example.
>>> You have to divert to integer arithmetic to circumvent this and the PTA
>>> pass, while tracking provenance through integers as well, does the right
>>> thing with this.
>>>>>
>>>>> Great, that is much better for smtgcc than the semantics I have
>>> currently
>>>>> implemented!
>>>>>
>>>>> But it is not completely clear to me what "most of the C pointer
>>>>> restrictions" implies. Is the following a correct interpretation?
>>>>>
>>>>> 1. A pointer must contain a value that points into (or one past) an
>>> object
>>>>> corresponding to its provenance (where a pointer may have multiple
>>>>> provenances). Otherwise it invokes undefined behavior.
>>>>
>>>> Hmm.  I think it's only UB when you'd "use" that pointer.  That is, PTA
>>> would
>>>> compute the points-to set to 'nothing'.  The immediate consequences are
>>> such
>>>> pointer isn't equal to any other pointer and accesses through it alias
>>>> with nothing,
>>>> stores would be DSEd.  But at the point a SSA var is assigned such a
>>> pointer
>>>> we couldn't place a trap() (?)
>>>>
>>>>> 2. The provenance used for the result of POINTER_PLUS is the union of
>>> the
>>>>> provenances for the two arguments.
>>>>
>>>> For POINTER_PLUS it's the provenance of the first argument.
>>>>
>>>> For PLUS_EXPR it is the union of both arguments.  For POINTER_DIFF_EXPR
>>>> the result has no provenance.
>>>>
>>>>> 3. The POINTER_PLUS operation is UB if the calculation overflows and
>>>>> TYPE_OVERFLOW_WRAPS(ptr_type) is false.
>>>>
>>>> Yes.
>>>>
>>>>> 4. The rules are the same for the calculations done in MEM_REF and
>>>>> TARGET_MEM_REF as for POINTER_PLUS.
>>>>
>>>> Yes.
>>>>
>>>>> Question: For the TARGET_MEM_REF calculation:
>>>>>     BASE + STEP * INDEX + INDEX2 + OFFSET
>>>>> Is it treated as one POINTER_PLUS, i.e.
>>>>>     BASE + (STEP * INDEX + INDEX2 + OFFSET)
>>>>> or as two (i.e. do we care about overflow and OOB between the two index
>>>>> calculations)?
>>>>
>>>> I'd say it counts as one pointer + offset calculation with all the offset
>>>> calculation being done in wrapping operations.
>>>
>>> Your answers match exactly what is currently implemented in smtgcc, so I
>>> am still thinking this is a bug in GCC (or that there is some missing
>>> GIMPLE rule I must implement).
>>>
>>> The original program looks in GIMPLE like:
>>>
>>>     void foo (char * p, long long int i)
>>>     {
>>>       char a;
>>>       sizetype i.0_1;
>>>       char * _2;
>>>
>>>       <bb 2> :
>>>       i.0_1 = (sizetype) i_3(D);
>>>       _2 = p_4(D) + i.0_1;
>>>       if (_2 == &a)
>>>         goto <bb 3>;
>>>       else
>>>         goto <bb 4>;
>>>
>>>       <bb 3> :
>>>       __builtin_abort ();
>>>
>>>       <bb 4> :
>>>       a ={v} {CLOBBER(eos)};
>>>       return;
>>>     }
>>>
>>> Assume, for the sake of argument, that the address of a is 0x2000000, p =
>>> 0x1000000 and i = 0x1000000.
>>>
>>> With the semantics as described in this mail thread, all operations are
>>> defined:
>>>    * _2 evaluates to 0x2000000, with the provenance of p (although the
>>>      provenance is irrelevant in this execution).
>>>    * The comparison is also defined and evaluates to true.
>>>    * As a result, the program then calls __builtin_abort, which exits.
>>>
>>> A valid optimization must produce the same result (including side effects)
>>> given the same input for executions where all steps have defined
>>> semantics.
>>
>>
>> Except this comparison has an unspecified value, so an optimization is
>> allowed to change it.
> 
> Is it?  For, C this is defined.

Ah, indeed this seems to be a difference between C and C++.  C++:

https://eel.is/c++draft/expr#eq-3.1
"If one pointer represents the address of a complete object, and another 
pointer represents the address one past the last element of a different 
complete object, the result of the comparison is unspecified."

C:

"Two pointers compare equal if and only if ... 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."

Jason

Re: pointer comparison in GIMPLE

[Martin Uecker]

Am Freitag, dem 12.12.2025 um 18:50 +0700 schrieb Jason Merrill:
> On 12/12/25 2:10 PM, Martin Uecker wrote:
> > Am Freitag, dem 12.12.2025 um 09:21 +0700 schrieb Jason Merrill via Gcc:
> > > On Fri, Dec 12, 2025, 8:57 a.m. Krister Walfridsson via Gcc <gcc@gcc.gnu.org>
> > > wrote:
> > > 
> > > > On Thu, 11 Dec 2025, Richard Biener wrote:
> > > > 
> > > > > Date: Thu, 11 Dec 2025 12:38:43 +0100
> > > > > From: Richard Biener <richard.guenther@gmail.com>
> > > > > To: Krister Walfridsson <krister.walfridsson@gmail.com>
> > > > > Cc: gcc@gcc.gnu.org
> > > > > Subject: Re: pointer comparison in GIMPLE
> > > > > 
> > > > > On Thu, Dec 11, 2025 at 5:12 AM Krister Walfridsson
> > > > > <krister.walfridsson@gmail.com> wrote:
> > > > > > 
> > > > > > On Wed, 10 Dec 2025, Richard Biener wrote:
> > > > > > 
> > > > > > > > The problem is that in GIMPLE, a pointer does not need to be in
> > > > bounds. The caller could call the function with a value of i such that p +
> > > > i happens to be equal to &a. So, as I understand it, the GIMPLE semantics
> > > > do not allow the pass to conclude that p + i == &a is false, unless p + i
> > > > is dereferenced (because dereferencing a through p + i would be UB due to
> > > > provenance).
> > > > > > > 
> > > > > > > GIMPLE adopts most of the C pointer restrictions here thus we can (and
> > > > do) conclude that pointers stay within an object when advanced.  This is
> > > > used by the PTA pass which results are used when we optimize your example.
> > > > You have to divert to integer arithmetic to circumvent this and the PTA
> > > > pass, while tracking provenance through integers as well, does the right
> > > > thing with this.
> > > > > > 
> > > > > > Great, that is much better for smtgcc than the semantics I have
> > > > currently
> > > > > > implemented!
> > > > > > 
> > > > > > But it is not completely clear to me what "most of the C pointer
> > > > > > restrictions" implies. Is the following a correct interpretation?
> > > > > > 
> > > > > > 1. A pointer must contain a value that points into (or one past) an
> > > > object
> > > > > > corresponding to its provenance (where a pointer may have multiple
> > > > > > provenances). Otherwise it invokes undefined behavior.
> > > > > 
> > > > > Hmm.  I think it's only UB when you'd "use" that pointer.  That is, PTA
> > > > would
> > > > > compute the points-to set to 'nothing'.  The immediate consequences are
> > > > such
> > > > > pointer isn't equal to any other pointer and accesses through it alias
> > > > > with nothing,
> > > > > stores would be DSEd.  But at the point a SSA var is assigned such a
> > > > pointer
> > > > > we couldn't place a trap() (?)
> > > > > 
> > > > > > 2. The provenance used for the result of POINTER_PLUS is the union of
> > > > the
> > > > > > provenances for the two arguments.
> > > > > 
> > > > > For POINTER_PLUS it's the provenance of the first argument.
> > > > > 
> > > > > For PLUS_EXPR it is the union of both arguments.  For POINTER_DIFF_EXPR
> > > > > the result has no provenance.
> > > > > 
> > > > > > 3. The POINTER_PLUS operation is UB if the calculation overflows and
> > > > > > TYPE_OVERFLOW_WRAPS(ptr_type) is false.
> > > > > 
> > > > > Yes.
> > > > > 
> > > > > > 4. The rules are the same for the calculations done in MEM_REF and
> > > > > > TARGET_MEM_REF as for POINTER_PLUS.
> > > > > 
> > > > > Yes.
> > > > > 
> > > > > > Question: For the TARGET_MEM_REF calculation:
> > > > > >     BASE + STEP * INDEX + INDEX2 + OFFSET
> > > > > > Is it treated as one POINTER_PLUS, i.e.
> > > > > >     BASE + (STEP * INDEX + INDEX2 + OFFSET)
> > > > > > or as two (i.e. do we care about overflow and OOB between the two index
> > > > > > calculations)?
> > > > > 
> > > > > I'd say it counts as one pointer + offset calculation with all the offset
> > > > > calculation being done in wrapping operations.
> > > > 
> > > > Your answers match exactly what is currently implemented in smtgcc, so I
> > > > am still thinking this is a bug in GCC (or that there is some missing
> > > > GIMPLE rule I must implement).
> > > > 
> > > > The original program looks in GIMPLE like:
> > > > 
> > > >     void foo (char * p, long long int i)
> > > >     {
> > > >       char a;
> > > >       sizetype i.0_1;
> > > >       char * _2;
> > > > 
> > > >       <bb 2> :
> > > >       i.0_1 = (sizetype) i_3(D);
> > > >       _2 = p_4(D) + i.0_1;
> > > >       if (_2 == &a)
> > > >         goto <bb 3>;
> > > >       else
> > > >         goto <bb 4>;
> > > > 
> > > >       <bb 3> :
> > > >       __builtin_abort ();
> > > > 
> > > >       <bb 4> :
> > > >       a ={v} {CLOBBER(eos)};
> > > >       return;
> > > >     }
> > > > 
> > > > Assume, for the sake of argument, that the address of a is 0x2000000, p =
> > > > 0x1000000 and i = 0x1000000.
> > > > 
> > > > With the semantics as described in this mail thread, all operations are
> > > > defined:
> > > >    * _2 evaluates to 0x2000000, with the provenance of p (although the
> > > >      provenance is irrelevant in this execution).
> > > >    * The comparison is also defined and evaluates to true.
> > > >    * As a result, the program then calls __builtin_abort, which exits.
> > > > 
> > > > A valid optimization must produce the same result (including side effects)
> > > > given the same input for executions where all steps have defined
> > > > semantics.
> > > 
> > > 
> > > Except this comparison has an unspecified value, so an optimization is
> > > allowed to change it.
> > 
> > Is it?  For, C this is defined.
> 
> Ah, indeed this seems to be a difference between C and C++.  C++:
> 
> https://eel.is/c++draft/expr#eq-3.1
> "If one pointer represents the address of a complete object, and another 
> pointer represents the address one past the last element of a different 
> complete object, the result of the comparison is unspecified."
> 
> C:
> 
> "Two pointers compare equal if and only if ... 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."
> 

We certainly also considered changes for C.  But mostly
the problem with "unspecified" is that it practice it
is not a lot better than "undefined".  Optimizers
confuse themselves if they then have other
optimizations which rely on the stability of the value.
For example, see the comment by Alexander Cherepanov:

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


One could make comparisons for unrelated pointers for the
case that one is a one-after pointer undefined in C (and C++),
but this is difficult to sell.

So for me it seems that GCC should be changed to make
these comparisons deterministic based on the address as
required by the C standard.  Conditional equivalences need
to have guards against the special case of one-after pointers.
(for example, after a pointer is dereferenced once, one
can be sure it is not a one-after pointer)

Of course, GIMPLE could also have other semantics than
C/C++, but then we need a way to express C/C++ semantics
correctly.  For example, if we had 
__builtin_expose / __builtin_synthesize that mark
a pointer escaped or as of unknown provenance, 
respectively (maybe we have something like this?)
then the front-ends could add those for casts from/to
integers and for comparisons to implement the desired
semantics.  I assume the Rust FE will also need a solution. 

Martin

Re: pointer comparison in GIMPLE

[Richard Biener]

On Fri, Dec 12, 2025 at 1:43 PM Martin Uecker <muecker@gwdg.de> wrote:
>
> Am Freitag, dem 12.12.2025 um 18:50 +0700 schrieb Jason Merrill:
> > On 12/12/25 2:10 PM, Martin Uecker wrote:
> > > Am Freitag, dem 12.12.2025 um 09:21 +0700 schrieb Jason Merrill via Gcc:
> > > > On Fri, Dec 12, 2025, 8:57 a.m. Krister Walfridsson via Gcc <gcc@gcc.gnu.org>
> > > > wrote:
> > > >
> > > > > On Thu, 11 Dec 2025, Richard Biener wrote:
> > > > >
> > > > > > Date: Thu, 11 Dec 2025 12:38:43 +0100
> > > > > > From: Richard Biener <richard.guenther@gmail.com>
> > > > > > To: Krister Walfridsson <krister.walfridsson@gmail.com>
> > > > > > Cc: gcc@gcc.gnu.org
> > > > > > Subject: Re: pointer comparison in GIMPLE
> > > > > >
> > > > > > On Thu, Dec 11, 2025 at 5:12 AM Krister Walfridsson
> > > > > > <krister.walfridsson@gmail.com> wrote:
> > > > > > >
> > > > > > > On Wed, 10 Dec 2025, Richard Biener wrote:
> > > > > > >
> > > > > > > > > The problem is that in GIMPLE, a pointer does not need to be in
> > > > > bounds. The caller could call the function with a value of i such that p +
> > > > > i happens to be equal to &a. So, as I understand it, the GIMPLE semantics
> > > > > do not allow the pass to conclude that p + i == &a is false, unless p + i
> > > > > is dereferenced (because dereferencing a through p + i would be UB due to
> > > > > provenance).
> > > > > > > >
> > > > > > > > GIMPLE adopts most of the C pointer restrictions here thus we can (and
> > > > > do) conclude that pointers stay within an object when advanced.  This is
> > > > > used by the PTA pass which results are used when we optimize your example.
> > > > > You have to divert to integer arithmetic to circumvent this and the PTA
> > > > > pass, while tracking provenance through integers as well, does the right
> > > > > thing with this.
> > > > > > >
> > > > > > > Great, that is much better for smtgcc than the semantics I have
> > > > > currently
> > > > > > > implemented!
> > > > > > >
> > > > > > > But it is not completely clear to me what "most of the C pointer
> > > > > > > restrictions" implies. Is the following a correct interpretation?
> > > > > > >
> > > > > > > 1. A pointer must contain a value that points into (or one past) an
> > > > > object
> > > > > > > corresponding to its provenance (where a pointer may have multiple
> > > > > > > provenances). Otherwise it invokes undefined behavior.
> > > > > >
> > > > > > Hmm.  I think it's only UB when you'd "use" that pointer.  That is, PTA
> > > > > would
> > > > > > compute the points-to set to 'nothing'.  The immediate consequences are
> > > > > such
> > > > > > pointer isn't equal to any other pointer and accesses through it alias
> > > > > > with nothing,
> > > > > > stores would be DSEd.  But at the point a SSA var is assigned such a
> > > > > pointer
> > > > > > we couldn't place a trap() (?)
> > > > > >
> > > > > > > 2. The provenance used for the result of POINTER_PLUS is the union of
> > > > > the
> > > > > > > provenances for the two arguments.
> > > > > >
> > > > > > For POINTER_PLUS it's the provenance of the first argument.
> > > > > >
> > > > > > For PLUS_EXPR it is the union of both arguments.  For POINTER_DIFF_EXPR
> > > > > > the result has no provenance.
> > > > > >
> > > > > > > 3. The POINTER_PLUS operation is UB if the calculation overflows and
> > > > > > > TYPE_OVERFLOW_WRAPS(ptr_type) is false.
> > > > > >
> > > > > > Yes.
> > > > > >
> > > > > > > 4. The rules are the same for the calculations done in MEM_REF and
> > > > > > > TARGET_MEM_REF as for POINTER_PLUS.
> > > > > >
> > > > > > Yes.
> > > > > >
> > > > > > > Question: For the TARGET_MEM_REF calculation:
> > > > > > >     BASE + STEP * INDEX + INDEX2 + OFFSET
> > > > > > > Is it treated as one POINTER_PLUS, i.e.
> > > > > > >     BASE + (STEP * INDEX + INDEX2 + OFFSET)
> > > > > > > or as two (i.e. do we care about overflow and OOB between the two index
> > > > > > > calculations)?
> > > > > >
> > > > > > I'd say it counts as one pointer + offset calculation with all the offset
> > > > > > calculation being done in wrapping operations.
> > > > >
> > > > > Your answers match exactly what is currently implemented in smtgcc, so I
> > > > > am still thinking this is a bug in GCC (or that there is some missing
> > > > > GIMPLE rule I must implement).
> > > > >
> > > > > The original program looks in GIMPLE like:
> > > > >
> > > > >     void foo (char * p, long long int i)
> > > > >     {
> > > > >       char a;
> > > > >       sizetype i.0_1;
> > > > >       char * _2;
> > > > >
> > > > >       <bb 2> :
> > > > >       i.0_1 = (sizetype) i_3(D);
> > > > >       _2 = p_4(D) + i.0_1;
> > > > >       if (_2 == &a)
> > > > >         goto <bb 3>;
> > > > >       else
> > > > >         goto <bb 4>;
> > > > >
> > > > >       <bb 3> :
> > > > >       __builtin_abort ();
> > > > >
> > > > >       <bb 4> :
> > > > >       a ={v} {CLOBBER(eos)};
> > > > >       return;
> > > > >     }
> > > > >
> > > > > Assume, for the sake of argument, that the address of a is 0x2000000, p =
> > > > > 0x1000000 and i = 0x1000000.
> > > > >
> > > > > With the semantics as described in this mail thread, all operations are
> > > > > defined:
> > > > >    * _2 evaluates to 0x2000000, with the provenance of p (although the
> > > > >      provenance is irrelevant in this execution).
> > > > >    * The comparison is also defined and evaluates to true.
> > > > >    * As a result, the program then calls __builtin_abort, which exits.
> > > > >
> > > > > A valid optimization must produce the same result (including side effects)
> > > > > given the same input for executions where all steps have defined
> > > > > semantics.
> > > >
> > > >
> > > > Except this comparison has an unspecified value, so an optimization is
> > > > allowed to change it.
> > >
> > > Is it?  For, C this is defined.
> >
> > Ah, indeed this seems to be a difference between C and C++.  C++:
> >
> > https://eel.is/c++draft/expr#eq-3.1
> > "If one pointer represents the address of a complete object, and another
> > pointer represents the address one past the last element of a different
> > complete object, the result of the comparison is unspecified."
> >
> > C:
> >
> > "Two pointers compare equal if and only if ... 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."
> >

We optimize this with the C++ rules because points-to info does not
track whether we can prove pointers will stay within the object or
eventually point to one-after.

> We certainly also considered changes for C.  But mostly
> the problem with "unspecified" is that it practice it
> is not a lot better than "undefined".  Optimizers
> confuse themselves if they then have other
> optimizations which rely on the stability of the value.
> For example, see the comment by Alexander Cherepanov:
>
> https://gcc.gnu.org/bugzilla/show_bug.cgi?id=61502#c42
>
>
> One could make comparisons for unrelated pointers for the
> case that one is a one-after pointer undefined in C (and C++),
> but this is difficult to sell.
>
> So for me it seems that GCC should be changed to make
> these comparisons deterministic based on the address as
> required by the C standard.  Conditional equivalences need
> to have guards against the special case of one-after pointers.
> (for example, after a pointer is dereferenced once, one
> can be sure it is not a one-after pointer)
>
> Of course, GIMPLE could also have other semantics than
> C/C++, but then we need a way to express C/C++ semantics
> correctly.  For example, if we had
> __builtin_expose / __builtin_synthesize that mark
> a pointer escaped or as of unknown provenance,
> respectively (maybe we have something like this?)
> then the front-ends could add those for casts from/to
> integers and for comparisons to implement the desired
> semantics.  I assume the Rust FE will also need a solution.
>
> Martin

Re: pointer comparison in GIMPLE

[Richard Biener]

On Thu, Dec 11, 2025 at 8:33 PM Martin Uecker <muecker@gwdg.de> wrote:
>
> Am Donnerstag, dem 11.12.2025 um 12:48 +0100 schrieb Richard Biener:
> > On Thu, Dec 11, 2025 at 7:48 AM Martin Uecker <muecker@gwdg.de> wrote:
> > >
> > > Am Donnerstag, dem 11.12.2025 um 04:12 +0000 schrieb Krister Walfridsson via Gcc:
> > > > On Wed, 10 Dec 2025, Richard Biener wrote:
> > > >
> > > > > > The problem is that in GIMPLE, a pointer does not need to be in bounds. The caller could call the function with a value of i such that p + i happens to be equal to &a. So, as I understand it, the GIMPLE semantics do not allow the pass to conclude that p + i == &a is false, unless p + i is dereferenced (because dereferencing a through p + i would be UB due to provenance).
> > > > >
> > > > > GIMPLE adopts most of the C pointer restrictions here thus we can (and do) conclude that pointers stay within an object when advanced.  This is used by the PTA pass which results are used when we optimize your example.  You have to divert to integer arithmetic to circumvent this and the PTA pass, while tracking provenance through integers as well, does the right thing with this.
> > > >
> > > > Great, that is much better for smtgcc than the semantics I have currently
> > > > implemented!
> > > >
> > > > But it is not completely clear to me what "most of the C pointer
> > > > restrictions" implies. Is the following a correct interpretation?
> > > >
> > > > 1. A pointer must contain a value that points into (or one past) an object
> > > > corresponding to its provenance (where a pointer may have multiple
> > > > provenances). Otherwise it invokes undefined behavior.
> > > >
> > > > 2. The provenance used for the result of POINTER_PLUS is the union of the
> > > > provenances for the two arguments.
> > >
> > > Note that in C one argument would be an integer and there is no
> > > provenance on integers in C as this can not work consistently.
> > >
> > > (and I think GCC gets this wrong)
> >
> > What GCC gets "right" (right in terms of improving optimization) is
> > that (int *)(intptr_t)ptr has the same provenance as ptr.
>
> The problem is nobody could come up with a convincing model
> for this that is sound.  Currently GCC breaks the requirement
> that roundtrips through integers have to work in all cases
> because sometimes the compiler gets confused about the
> provenance of the back-converted pointer and assigns the
> wrong one.

Does it?  I don't remember such a case, can you point me to it?

>
> The model that *is* sound is to treat conversion to integer as
> escaped and pointers converted back from integers as pointing
> to any previously escaped provenance.
>
> LLVM also gets this wrong but my understanding is that they
> want to fix this.
>
> >
> > GCC considers literal zero to have "no" provenance (unless the target
> > claims objects can exist at address zero).  So (int *)((intptr_t)ptr + 0)
> > retains the provenance of ptr.  (int *)((intptr_t)ptr + 4) OTOH has
> > provenance of ptr merged with 'nonlocal' provenance (a literal address
> > never has provenance of a stack object).  That is, constant folding
> > loses the fact that (void *)0 + 4 would have "no" provenance (actually
> > not sure whether the null "object" is subject to pointer arithmetic
> > constraints).
> >
> > There's one thing GCC gets wrong (see some PRs) which is
> > "conditional provenance".
> >
> >  if (p == q)
> >    /* we now should treat p and q as having unioned provenance since
> >       p can be substituted for q (and vice versa) by the compiler.  */
> >
> > I have not yet seen a good answer to this from the C pointer provenance proposal
> > folks.
>
> I am not sure what answer you want. This optimization is unsound.
>
> I think one could retain such optimizations by adding some additional
> conditions that exclude the special case that p and q have different
> provenance but the same address.

I don't think this is workable for GCC.  We'd have to disable all
conditional copy propagation (in the GCC case for both pointers
and integers, since the latter carry provenance).  My other "simple"
fix would be to make sure to unify provenances of p and q when
there's an equality compare but even that's a bit difficult if you
consider (SSA form)

  p_1 = p_2 + 1;
  if (p_1 == q_3)
    ...

not only p_1 and q_3 would have to unify provenances but of course
also p_2 and all other pointers based on (or related to) p_1.

So I understand why you think that conditional copy propgation
is "unsound", because it does not play well with provenances.

Richard.

> Martin
>
> >
> > Richard.
> >
> > >
> > > Martin
> > >
> > >
> > > >
> > > > 3. The POINTER_PLUS operation is UB if the calculation overflows and
> > > > TYPE_OVERFLOW_WRAPS(ptr_type) is false.
> > > >
> > > > 4. The rules are the same for the calculations done in MEM_REF and
> > > > TARGET_MEM_REF as for POINTER_PLUS.
> > > >
> > > > Question: For the TARGET_MEM_REF calculation:
> > > >    BASE + STEP * INDEX + INDEX2 + OFFSET
> > > > Is it treated as one POINTER_PLUS, i.e.
> > > >    BASE + (STEP * INDEX + INDEX2 + OFFSET)
> > > > or as two (i.e. do we care about overflow and OOB between the two index
> > > > calculations)?
> > > >
> > > >
> > > > FWIW, the vectorizer and ivopts do introduce pointers that are outside the
> > > > object (which is why I allowed it in my current semantics)...
> > > >
> > > >     /Krister

Re: pointer comparison in GIMPLE

[Martin Uecker]

Am Freitag, dem 12.12.2025 um 16:16 +0100 schrieb Richard Biener:
> On Thu, Dec 11, 2025 at 8:33 PM Martin Uecker <muecker@gwdg.de> wrote:
> > 
> > Am Donnerstag, dem 11.12.2025 um 12:48 +0100 schrieb Richard Biener:
> > > On Thu, Dec 11, 2025 at 7:48 AM Martin Uecker <muecker@gwdg.de> wrote:
> > > > 
> > > > Am Donnerstag, dem 11.12.2025 um 04:12 +0000 schrieb Krister Walfridsson via Gcc:
> > > > > On Wed, 10 Dec 2025, Richard Biener wrote:
> > > > > 
> > > > > > > The problem is that in GIMPLE, a pointer does not need to be in bounds. The caller could call the function with a value of i such that p + i happens to be equal to &a. So, as I understand it, the GIMPLE semantics do not allow the pass to conclude that p + i == &a is false, unless p + i is dereferenced (because dereferencing a through p + i would be UB due to provenance).
> > > > > > 
> > > > > > GIMPLE adopts most of the C pointer restrictions here thus we can (and do) conclude that pointers stay within an object when advanced.  This is used by the PTA pass which results are used when we optimize your example.  You have to divert to integer arithmetic to circumvent this and the PTA pass, while tracking provenance through integers as well, does the right thing with this.
> > > > > 
> > > > > Great, that is much better for smtgcc than the semantics I have currently
> > > > > implemented!
> > > > > 
> > > > > But it is not completely clear to me what "most of the C pointer
> > > > > restrictions" implies. Is the following a correct interpretation?
> > > > > 
> > > > > 1. A pointer must contain a value that points into (or one past) an object
> > > > > corresponding to its provenance (where a pointer may have multiple
> > > > > provenances). Otherwise it invokes undefined behavior.
> > > > > 
> > > > > 2. The provenance used for the result of POINTER_PLUS is the union of the
> > > > > provenances for the two arguments.
> > > > 
> > > > Note that in C one argument would be an integer and there is no
> > > > provenance on integers in C as this can not work consistently.
> > > > 
> > > > (and I think GCC gets this wrong)
> > > 
> > > What GCC gets "right" (right in terms of improving optimization) is
> > > that (int *)(intptr_t)ptr has the same provenance as ptr.
> > 
> > The problem is nobody could come up with a convincing model
> > for this that is sound.  Currently GCC breaks the requirement
> > that roundtrips through integers have to work in all cases
> > because sometimes the compiler gets confused about the
> > provenance of the back-converted pointer and assigns the
> > wrong one.
> 
> Does it?  I don't remember such a case, can you point me to it?

I think there are couple PRs related to this. One which
illustrates the underlying issue nicely is this one:

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

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

int main() {
  int x = 0, *p = 0;
  for (uintptr_t i = 0; ; i++) {
    if (i == (uintptr_t)&x) { p = (int*)i; break; }
  }
  *p = 15;
  printf("%d\n", x);
}

The loop is a no-op integer transformation that should set p to the
address of &x.  But the compiler is not able to understand it and
forgets the provenance.  The C standard requires that if you transform
the same integer back, you get the same pointer.  So this is wrong.


If one tried to formulate consistent rules which make this example
have UB, then you would need to formulate some set rules that exactly
specifies how all possible operations on integers affect their
provenance, and this ruleset might then say that copying integers leads
to a loss of provenance.  But this then also means in general that
all optimizations GCC does on integers would need to conform to
these rules about provenance, and not naively assume that integers
are just integers.   As reasoning based on value equivalency goes
wrong already for pointers, I assume it is practically impossible to make
it work consistently for all integer operations.


Dropping provenance for integers will remove this problem completely
at the cost of some optimizations, and I think we should support a
correct mode at least as an option.   This dropping of provenance could
also be done in the FE by inserting some __builtin or similar.

> 
> > 
> > The model that *is* sound is to treat conversion to integer as
> > escaped and pointers converted back from integers as pointing
> > to any previously escaped provenance.
> > 
> > LLVM also gets this wrong but my understanding is that they
> > want to fix this.
> > 
> > > 
> > > GCC considers literal zero to have "no" provenance (unless the target
> > > claims objects can exist at address zero).  So (int *)((intptr_t)ptr + 0)
> > > retains the provenance of ptr.  (int *)((intptr_t)ptr + 4) OTOH has
> > > provenance of ptr merged with 'nonlocal' provenance (a literal address
> > > never has provenance of a stack object).  That is, constant folding
> > > loses the fact that (void *)0 + 4 would have "no" provenance (actually
> > > not sure whether the null "object" is subject to pointer arithmetic
> > > constraints).
> > > 
> > > There's one thing GCC gets wrong (see some PRs) which is
> > > "conditional provenance".
> > > 
> > >  if (p == q)
> > >    /* we now should treat p and q as having unioned provenance since
> > >       p can be substituted for q (and vice versa) by the compiler.  */
> > > 
> > > I have not yet seen a good answer to this from the C pointer provenance proposal
> > > folks.
> > 
> > I am not sure what answer you want. This optimization is unsound.
> > 
> > I think one could retain such optimizations by adding some additional
> > conditions that exclude the special case that p and q have different
> > provenance but the same address.
> 
> I don't think this is workable for GCC.  We'd have to disable all
> conditional copy propagation (in the GCC case for both pointers
> and integers, since the latter carry provenance).  

I think we should have a mode that does not carry provenance
via integers.  This is also what LLVM will do as far as I know,
and also what the folks working on Rust semantics wanted once
I last talked to them.


Martin


> My other "simple"
> fix would be to make sure to unify provenances of p and q when
> there's an equality compare but even that's a bit difficult if you
> consider (SSA form)
> 
>   p_1 = p_2 + 1;
>   if (p_1 == q_3)
>     ...
> 
> not only p_1 and q_3 would have to unify provenances but of course
> also p_2 and all other pointers based on (or related to) p_1.
> 
> So I understand why you think that conditional copy propgation
> is "unsound", because it does not play well with provenances.
> 
> Richard.
> 
> > Martin
> > 
> > > 
> > > Richard.
> > > 
> > > > 
> > > > Martin
> > > > 
> > > > 
> > > > > 
> > > > > 3. The POINTER_PLUS operation is UB if the calculation overflows and
> > > > > TYPE_OVERFLOW_WRAPS(ptr_type) is false.
> > > > > 
> > > > > 4. The rules are the same for the calculations done in MEM_REF and
> > > > > TARGET_MEM_REF as for POINTER_PLUS.
> > > > > 
> > > > > Question: For the TARGET_MEM_REF calculation:
> > > > >    BASE + STEP * INDEX + INDEX2 + OFFSET
> > > > > Is it treated as one POINTER_PLUS, i.e.
> > > > >    BASE + (STEP * INDEX + INDEX2 + OFFSET)
> > > > > or as two (i.e. do we care about overflow and OOB between the two index
> > > > > calculations)?
> > > > > 
> > > > > 
> > > > > FWIW, the vectorizer and ivopts do introduce pointers that are outside the
> > > > > object (which is why I allowed it in my current semantics)...
> > > > > 
> > > > >     /Krister

Re: pointer comparison in GIMPLE

[Martin Uecker]

This version is even nicer: https://godbolt.org/z/3M4Y6Pa3h

In both cases the compiler understands that the function is the
identity on integers and optimizes it to a move, but it still
makes an aliasing decision that is inconsistent with this basic
fact when this integer is back-converted to a pointer.

Martin

Am Freitag, dem 12.12.2025 um 18:23 +0100 schrieb Martin Uecker:
> Am Freitag, dem 12.12.2025 um 16:16 +0100 schrieb Richard Biener:
> > On Thu, Dec 11, 2025 at 8:33 PM Martin Uecker <muecker@gwdg.de> wrote:
> > > 
> > > Am Donnerstag, dem 11.12.2025 um 12:48 +0100 schrieb Richard Biener:
> > > > On Thu, Dec 11, 2025 at 7:48 AM Martin Uecker <muecker@gwdg.de> wrote:
> > > > > 
> > > > > Am Donnerstag, dem 11.12.2025 um 04:12 +0000 schrieb Krister Walfridsson via Gcc:
> > > > > > On Wed, 10 Dec 2025, Richard Biener wrote:
> > > > > > 
> > > > > > > > The problem is that in GIMPLE, a pointer does not need to be in bounds. The caller could call the function with a value of i such that p + i happens to be equal to &a. So, as I understand it, the GIMPLE semantics do not allow the pass to conclude that p + i == &a is false, unless p + i is dereferenced (because dereferencing a through p + i would be UB due to provenance).
> > > > > > > 
> > > > > > > GIMPLE adopts most of the C pointer restrictions here thus we can (and do) conclude that pointers stay within an object when advanced.  This is used by the PTA pass which results are used when we optimize your example.  You have to divert to integer arithmetic to circumvent this and the PTA pass, while tracking provenance through integers as well, does the right thing with this.
> > > > > > 
> > > > > > Great, that is much better for smtgcc than the semantics I have currently
> > > > > > implemented!
> > > > > > 
> > > > > > But it is not completely clear to me what "most of the C pointer
> > > > > > restrictions" implies. Is the following a correct interpretation?
> > > > > > 
> > > > > > 1. A pointer must contain a value that points into (or one past) an object
> > > > > > corresponding to its provenance (where a pointer may have multiple
> > > > > > provenances). Otherwise it invokes undefined behavior.
> > > > > > 
> > > > > > 2. The provenance used for the result of POINTER_PLUS is the union of the
> > > > > > provenances for the two arguments.
> > > > > 
> > > > > Note that in C one argument would be an integer and there is no
> > > > > provenance on integers in C as this can not work consistently.
> > > > > 
> > > > > (and I think GCC gets this wrong)
> > > > 
> > > > What GCC gets "right" (right in terms of improving optimization) is
> > > > that (int *)(intptr_t)ptr has the same provenance as ptr.
> > > 
> > > The problem is nobody could come up with a convincing model
> > > for this that is sound.  Currently GCC breaks the requirement
> > > that roundtrips through integers have to work in all cases
> > > because sometimes the compiler gets confused about the
> > > provenance of the back-converted pointer and assigns the
> > > wrong one.
> > 
> > Does it?  I don't remember such a case, can you point me to it?
> 
> I think there are couple PRs related to this. One which
> illustrates the underlying issue nicely is this one:
> 
> https://gcc.gnu.org/bugzilla/show_bug.cgi?id=65752
> 
> #include <stdio.h>
> #include <stdint.h>
> #include <limits.h>
> 
> int main() {
>   int x = 0, *p = 0;
>   for (uintptr_t i = 0; ; i++) {
>     if (i == (uintptr_t)&x) { p = (int*)i; break; }
>   }
>   *p = 15;
>   printf("%d\n", x);
> }
> 
> The loop is a no-op integer transformation that should set p to the
> address of &x.  But the compiler is not able to understand it and
> forgets the provenance.  The C standard requires that if you transform
> the same integer back, you get the same pointer.  So this is wrong.
> 
> 
> If one tried to formulate consistent rules which make this example
> have UB, then you would need to formulate some set rules that exactly
> specifies how all possible operations on integers affect their
> provenance, and this ruleset might then say that copying integers leads
> to a loss of provenance.  But this then also means in general that
> all optimizations GCC does on integers would need to conform to
> these rules about provenance, and not naively assume that integers
> are just integers.   As reasoning based on value equivalency goes
> wrong already for pointers, I assume it is practically impossible to make
> it work consistently for all integer operations.
> 
> 
> Dropping provenance for integers will remove this problem completely
> at the cost of some optimizations, and I think we should support a
> correct mode at least as an option.   This dropping of provenance could
> also be done in the FE by inserting some __builtin or similar.
> 
> > 
> > > 
> > > The model that *is* sound is to treat conversion to integer as
> > > escaped and pointers converted back from integers as pointing
> > > to any previously escaped provenance.
> > > 
> > > LLVM also gets this wrong but my understanding is that they
> > > want to fix this.
> > > 
> > > > 
> > > > GCC considers literal zero to have "no" provenance (unless the target
> > > > claims objects can exist at address zero).  So (int *)((intptr_t)ptr + 0)
> > > > retains the provenance of ptr.  (int *)((intptr_t)ptr + 4) OTOH has
> > > > provenance of ptr merged with 'nonlocal' provenance (a literal address
> > > > never has provenance of a stack object).  That is, constant folding
> > > > loses the fact that (void *)0 + 4 would have "no" provenance (actually
> > > > not sure whether the null "object" is subject to pointer arithmetic
> > > > constraints).
> > > > 
> > > > There's one thing GCC gets wrong (see some PRs) which is
> > > > "conditional provenance".
> > > > 
> > > >  if (p == q)
> > > >    /* we now should treat p and q as having unioned provenance since
> > > >       p can be substituted for q (and vice versa) by the compiler.  */
> > > > 
> > > > I have not yet seen a good answer to this from the C pointer provenance proposal
> > > > folks.
> > > 
> > > I am not sure what answer you want. This optimization is unsound.
> > > 
> > > I think one could retain such optimizations by adding some additional
> > > conditions that exclude the special case that p and q have different
> > > provenance but the same address.
> > 
> > I don't think this is workable for GCC.  We'd have to disable all
> > conditional copy propagation (in the GCC case for both pointers
> > and integers, since the latter carry provenance).  
> 
> I think we should have a mode that does not carry provenance
> via integers.  This is also what LLVM will do as far as I know,
> and also what the folks working on Rust semantics wanted once
> I last talked to them.
> 
> 
> Martin
> 
> 
> > My other "simple"
> > fix would be to make sure to unify provenances of p and q when
> > there's an equality compare but even that's a bit difficult if you
> > consider (SSA form)
> > 
> >   p_1 = p_2 + 1;
> >   if (p_1 == q_3)
> >     ...
> > 
> > not only p_1 and q_3 would have to unify provenances but of course
> > also p_2 and all other pointers based on (or related to) p_1.
> > 
> > So I understand why you think that conditional copy propgation
> > is "unsound", because it does not play well with provenances.
> > 
> > Richard.
> > 
> > > Martin
> > > 
> > > > 
> > > > Richard.
> > > > 
> > > > > 
> > > > > Martin
> > > > > 
> > > > > 
> > > > > > 
> > > > > > 3. The POINTER_PLUS operation is UB if the calculation overflows and
> > > > > > TYPE_OVERFLOW_WRAPS(ptr_type) is false.
> > > > > > 
> > > > > > 4. The rules are the same for the calculations done in MEM_REF and
> > > > > > TARGET_MEM_REF as for POINTER_PLUS.
> > > > > > 
> > > > > > Question: For the TARGET_MEM_REF calculation:
> > > > > >    BASE + STEP * INDEX + INDEX2 + OFFSET
> > > > > > Is it treated as one POINTER_PLUS, i.e.
> > > > > >    BASE + (STEP * INDEX + INDEX2 + OFFSET)
> > > > > > or as two (i.e. do we care about overflow and OOB between the two index
> > > > > > calculations)?
> > > > > > 
> > > > > > 
> > > > > > FWIW, the vectorizer and ivopts do introduce pointers that are outside the
> > > > > > object (which is why I allowed it in my current semantics)...
> > > > > > 
> > > > > >     /Krister

Re: pointer comparison in GIMPLE

[Richard Biener]

On Fri, Dec 12, 2025 at 6:41 PM Martin Uecker <muecker@gwdg.de> wrote:
>
>
>
> This version is even nicer: https://godbolt.org/z/3M4Y6Pa3h
>
> In both cases the compiler understands that the function is the
> identity on integers and optimizes it to a move, but it still
> makes an aliasing decision that is inconsistent with this basic
> fact when this integer is back-converted to a pointer.

Both show the issue is that we consider integers of unknown provenance
to only point to global variables, never to stack ones.  This "rule" is derived
from the idea of no code doing such thing but eventually having global
variables laid out at absolute addresses.  Conditional copy propagating of
(uintptr_t)&x to the assignment site would also avoid the issue since the
provenance is no longer transfered by an equivalence but an assignment.
That it works when retaining the function call (see below for your godbolt
case inline) shows that nonlocal properly handles escaped "integers".
But with inlining it degenerates.

This is also easier to fix than dropping integer provenance tracking.  Simply
by making 100 not have nonlocal but anything provenance (also at some cost).

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

#ifdef NOIPA
[[gnu::noipa]]
#endif
uintptr_t id(uintptr_t x)
{
  return x;
    uintptr_t i = 0;
    while (1)
        if (++i == x) break;
    return i;
}

int main()
{
    int x = 0;
    int *p = (int*)id((uintptr_t)&x);
    *p = 15;
    printf("%d\n", x);
}

IMO while academically interesting the loop case isn't of practical concern,
the conditional equivalence one is more so.

Btw, we can properly handle "pointer difference addressing" where you
construct a pointer to an object from the difference of two object pointers.
"Properly" as in, we can optimize this.

  int *i = malloc (4);
  int *j = malloc (4);
  ptrdiff_t diff = (uintptr_t)i - (uintptr_t)j;
  int *ip = (int *)((uintptr_t)j + diff);

This was once a common way of handling pointers in sysv shared memory from
different processes and IIRC this was important to optimize this use-case.  The
other was from Matlab generated code which plumbed C <-> fortran by marshalling
64bit C pointers through fortan routines by splitting into two halves
and passing as
double values.  So yes, we also track provenance through FP values.

That said, we arrived here by optimization needs plus handling code in the wild
correctly that's invalid with strict reading of the C standard (which
only allows
back-and-forth casting of pointer-to-integer of exactly the original
pointer value,
not any offsetted value).

Richard.

> Martin
>
> Am Freitag, dem 12.12.2025 um 18:23 +0100 schrieb Martin Uecker:
> > Am Freitag, dem 12.12.2025 um 16:16 +0100 schrieb Richard Biener:
> > > On Thu, Dec 11, 2025 at 8:33 PM Martin Uecker <muecker@gwdg.de> wrote:
> > > >
> > > > Am Donnerstag, dem 11.12.2025 um 12:48 +0100 schrieb Richard Biener:
> > > > > On Thu, Dec 11, 2025 at 7:48 AM Martin Uecker <muecker@gwdg.de> wrote:
> > > > > >
> > > > > > Am Donnerstag, dem 11.12.2025 um 04:12 +0000 schrieb Krister Walfridsson via Gcc:
> > > > > > > On Wed, 10 Dec 2025, Richard Biener wrote:
> > > > > > >
> > > > > > > > > The problem is that in GIMPLE, a pointer does not need to be in bounds. The caller could call the function with a value of i such that p + i happens to be equal to &a. So, as I understand it, the GIMPLE semantics do not allow the pass to conclude that p + i == &a is false, unless p + i is dereferenced (because dereferencing a through p + i would be UB due to provenance).
> > > > > > > >
> > > > > > > > GIMPLE adopts most of the C pointer restrictions here thus we can (and do) conclude that pointers stay within an object when advanced.  This is used by the PTA pass which results are used when we optimize your example.  You have to divert to integer arithmetic to circumvent this and the PTA pass, while tracking provenance through integers as well, does the right thing with this.
> > > > > > >
> > > > > > > Great, that is much better for smtgcc than the semantics I have currently
> > > > > > > implemented!
> > > > > > >
> > > > > > > But it is not completely clear to me what "most of the C pointer
> > > > > > > restrictions" implies. Is the following a correct interpretation?
> > > > > > >
> > > > > > > 1. A pointer must contain a value that points into (or one past) an object
> > > > > > > corresponding to its provenance (where a pointer may have multiple
> > > > > > > provenances). Otherwise it invokes undefined behavior.
> > > > > > >
> > > > > > > 2. The provenance used for the result of POINTER_PLUS is the union of the
> > > > > > > provenances for the two arguments.
> > > > > >
> > > > > > Note that in C one argument would be an integer and there is no
> > > > > > provenance on integers in C as this can not work consistently.
> > > > > >
> > > > > > (and I think GCC gets this wrong)
> > > > >
> > > > > What GCC gets "right" (right in terms of improving optimization) is
> > > > > that (int *)(intptr_t)ptr has the same provenance as ptr.
> > > >
> > > > The problem is nobody could come up with a convincing model
> > > > for this that is sound.  Currently GCC breaks the requirement
> > > > that roundtrips through integers have to work in all cases
> > > > because sometimes the compiler gets confused about the
> > > > provenance of the back-converted pointer and assigns the
> > > > wrong one.
> > >
> > > Does it?  I don't remember such a case, can you point me to it?
> >
> > I think there are couple PRs related to this. One which
> > illustrates the underlying issue nicely is this one:
> >
> > https://gcc.gnu.org/bugzilla/show_bug.cgi?id=65752
> >
> > #include <stdio.h>
> > #include <stdint.h>
> > #include <limits.h>
> >
> > int main() {
> >   int x = 0, *p = 0;
> >   for (uintptr_t i = 0; ; i++) {
> >     if (i == (uintptr_t)&x) { p = (int*)i; break; }
> >   }
> >   *p = 15;
> >   printf("%d\n", x);
> > }
> >
> > The loop is a no-op integer transformation that should set p to the
> > address of &x.  But the compiler is not able to understand it and
> > forgets the provenance.  The C standard requires that if you transform
> > the same integer back, you get the same pointer.  So this is wrong.
> >
> >
> > If one tried to formulate consistent rules which make this example
> > have UB, then you would need to formulate some set rules that exactly
> > specifies how all possible operations on integers affect their
> > provenance, and this ruleset might then say that copying integers leads
> > to a loss of provenance.  But this then also means in general that
> > all optimizations GCC does on integers would need to conform to
> > these rules about provenance, and not naively assume that integers
> > are just integers.   As reasoning based on value equivalency goes
> > wrong already for pointers, I assume it is practically impossible to make
> > it work consistently for all integer operations.
> >
> >
> > Dropping provenance for integers will remove this problem completely
> > at the cost of some optimizations, and I think we should support a
> > correct mode at least as an option.   This dropping of provenance could
> > also be done in the FE by inserting some __builtin or similar.
> >
> > >
> > > >
> > > > The model that *is* sound is to treat conversion to integer as
> > > > escaped and pointers converted back from integers as pointing
> > > > to any previously escaped provenance.
> > > >
> > > > LLVM also gets this wrong but my understanding is that they
> > > > want to fix this.
> > > >
> > > > >
> > > > > GCC considers literal zero to have "no" provenance (unless the target
> > > > > claims objects can exist at address zero).  So (int *)((intptr_t)ptr + 0)
> > > > > retains the provenance of ptr.  (int *)((intptr_t)ptr + 4) OTOH has
> > > > > provenance of ptr merged with 'nonlocal' provenance (a literal address
> > > > > never has provenance of a stack object).  That is, constant folding
> > > > > loses the fact that (void *)0 + 4 would have "no" provenance (actually
> > > > > not sure whether the null "object" is subject to pointer arithmetic
> > > > > constraints).
> > > > >
> > > > > There's one thing GCC gets wrong (see some PRs) which is
> > > > > "conditional provenance".
> > > > >
> > > > >  if (p == q)
> > > > >    /* we now should treat p and q as having unioned provenance since
> > > > >       p can be substituted for q (and vice versa) by the compiler.  */
> > > > >
> > > > > I have not yet seen a good answer to this from the C pointer provenance proposal
> > > > > folks.
> > > >
> > > > I am not sure what answer you want. This optimization is unsound.
> > > >
> > > > I think one could retain such optimizations by adding some additional
> > > > conditions that exclude the special case that p and q have different
> > > > provenance but the same address.
> > >
> > > I don't think this is workable for GCC.  We'd have to disable all
> > > conditional copy propagation (in the GCC case for both pointers
> > > and integers, since the latter carry provenance).
> >
> > I think we should have a mode that does not carry provenance
> > via integers.  This is also what LLVM will do as far as I know,
> > and also what the folks working on Rust semantics wanted once
> > I last talked to them.
> >
> >
> > Martin
> >
> >
> > > My other "simple"
> > > fix would be to make sure to unify provenances of p and q when
> > > there's an equality compare but even that's a bit difficult if you
> > > consider (SSA form)
> > >
> > >   p_1 = p_2 + 1;
> > >   if (p_1 == q_3)
> > >     ...
> > >
> > > not only p_1 and q_3 would have to unify provenances but of course
> > > also p_2 and all other pointers based on (or related to) p_1.
> > >
> > > So I understand why you think that conditional copy propgation
> > > is "unsound", because it does not play well with provenances.
> > >
> > > Richard.
> > >
> > > > Martin
> > > >
> > > > >
> > > > > Richard.
> > > > >
> > > > > >
> > > > > > Martin
> > > > > >
> > > > > >
> > > > > > >
> > > > > > > 3. The POINTER_PLUS operation is UB if the calculation overflows and
> > > > > > > TYPE_OVERFLOW_WRAPS(ptr_type) is false.
> > > > > > >
> > > > > > > 4. The rules are the same for the calculations done in MEM_REF and
> > > > > > > TARGET_MEM_REF as for POINTER_PLUS.
> > > > > > >
> > > > > > > Question: For the TARGET_MEM_REF calculation:
> > > > > > >    BASE + STEP * INDEX + INDEX2 + OFFSET
> > > > > > > Is it treated as one POINTER_PLUS, i.e.
> > > > > > >    BASE + (STEP * INDEX + INDEX2 + OFFSET)
> > > > > > > or as two (i.e. do we care about overflow and OOB between the two index
> > > > > > > calculations)?
> > > > > > >
> > > > > > >
> > > > > > > FWIW, the vectorizer and ivopts do introduce pointers that are outside the
> > > > > > > object (which is why I allowed it in my current semantics)...
> > > > > > >
> > > > > > >     /Krister

Re: pointer comparison in GIMPLE

[Richard Biener]

On Sat, Dec 13, 2025 at 11:23 AM Richard Biener
<richard.guenther@gmail.com> wrote:
>
> On Fri, Dec 12, 2025 at 6:41 PM Martin Uecker <muecker@gwdg.de> wrote:
> >
> >
> >
> > This version is even nicer: https://godbolt.org/z/3M4Y6Pa3h
> >
> > In both cases the compiler understands that the function is the
> > identity on integers and optimizes it to a move, but it still
> > makes an aliasing decision that is inconsistent with this basic
> > fact when this integer is back-converted to a pointer.
>
> Both show the issue is that we consider integers of unknown provenance
> to only point to global variables, never to stack ones.  This "rule" is derived
> from the idea of no code doing such thing but eventually having global
> variables laid out at absolute addresses.  Conditional copy propagating of
> (uintptr_t)&x to the assignment site would also avoid the issue since the
> provenance is no longer transfered by an equivalence but an assignment.
> That it works when retaining the function call (see below for your godbolt
> case inline) shows that nonlocal properly handles escaped "integers".
> But with inlining it degenerates.
>
> This is also easier to fix than dropping integer provenance tracking.  Simply
> by making 100 not have nonlocal but anything provenance (also at some cost).

That said, it should be reasonably easy to add a -fstrict-provenance flag.  But
I'd rather have that adhere to whatever the C or C++ standard come up with
rather than something we make up.  There's always -fno-tree-pta.  As said,
I view the conditional equivalence problem as the most practical one we
currently have (although also only on fuzzed testcases at this point).

Richard.

> #include <stdio.h>
> #include <stdint.h>
> #include <limits.h>
>
> #ifdef NOIPA
> [[gnu::noipa]]
> #endif
> uintptr_t id(uintptr_t x)
> {
>   return x;
>     uintptr_t i = 0;
>     while (1)
>         if (++i == x) break;
>     return i;
> }
>
> int main()
> {
>     int x = 0;
>     int *p = (int*)id((uintptr_t)&x);
>     *p = 15;
>     printf("%d\n", x);
> }
>
> IMO while academically interesting the loop case isn't of practical concern,
> the conditional equivalence one is more so.
>
> Btw, we can properly handle "pointer difference addressing" where you
> construct a pointer to an object from the difference of two object pointers.
> "Properly" as in, we can optimize this.
>
>   int *i = malloc (4);
>   int *j = malloc (4);
>   ptrdiff_t diff = (uintptr_t)i - (uintptr_t)j;
>   int *ip = (int *)((uintptr_t)j + diff);
>
> This was once a common way of handling pointers in sysv shared memory from
> different processes and IIRC this was important to optimize this use-case.  The
> other was from Matlab generated code which plumbed C <-> fortran by marshalling
> 64bit C pointers through fortan routines by splitting into two halves
> and passing as
> double values.  So yes, we also track provenance through FP values.
>
> That said, we arrived here by optimization needs plus handling code in the wild
> correctly that's invalid with strict reading of the C standard (which
> only allows
> back-and-forth casting of pointer-to-integer of exactly the original
> pointer value,
> not any offsetted value).
>
> Richard.
>
> > Martin
> >
> > Am Freitag, dem 12.12.2025 um 18:23 +0100 schrieb Martin Uecker:
> > > Am Freitag, dem 12.12.2025 um 16:16 +0100 schrieb Richard Biener:
> > > > On Thu, Dec 11, 2025 at 8:33 PM Martin Uecker <muecker@gwdg.de> wrote:
> > > > >
> > > > > Am Donnerstag, dem 11.12.2025 um 12:48 +0100 schrieb Richard Biener:
> > > > > > On Thu, Dec 11, 2025 at 7:48 AM Martin Uecker <muecker@gwdg.de> wrote:
> > > > > > >
> > > > > > > Am Donnerstag, dem 11.12.2025 um 04:12 +0000 schrieb Krister Walfridsson via Gcc:
> > > > > > > > On Wed, 10 Dec 2025, Richard Biener wrote:
> > > > > > > >
> > > > > > > > > > The problem is that in GIMPLE, a pointer does not need to be in bounds. The caller could call the function with a value of i such that p + i happens to be equal to &a. So, as I understand it, the GIMPLE semantics do not allow the pass to conclude that p + i == &a is false, unless p + i is dereferenced (because dereferencing a through p + i would be UB due to provenance).
> > > > > > > > >
> > > > > > > > > GIMPLE adopts most of the C pointer restrictions here thus we can (and do) conclude that pointers stay within an object when advanced.  This is used by the PTA pass which results are used when we optimize your example.  You have to divert to integer arithmetic to circumvent this and the PTA pass, while tracking provenance through integers as well, does the right thing with this.
> > > > > > > >
> > > > > > > > Great, that is much better for smtgcc than the semantics I have currently
> > > > > > > > implemented!
> > > > > > > >
> > > > > > > > But it is not completely clear to me what "most of the C pointer
> > > > > > > > restrictions" implies. Is the following a correct interpretation?
> > > > > > > >
> > > > > > > > 1. A pointer must contain a value that points into (or one past) an object
> > > > > > > > corresponding to its provenance (where a pointer may have multiple
> > > > > > > > provenances). Otherwise it invokes undefined behavior.
> > > > > > > >
> > > > > > > > 2. The provenance used for the result of POINTER_PLUS is the union of the
> > > > > > > > provenances for the two arguments.
> > > > > > >
> > > > > > > Note that in C one argument would be an integer and there is no
> > > > > > > provenance on integers in C as this can not work consistently.
> > > > > > >
> > > > > > > (and I think GCC gets this wrong)
> > > > > >
> > > > > > What GCC gets "right" (right in terms of improving optimization) is
> > > > > > that (int *)(intptr_t)ptr has the same provenance as ptr.
> > > > >
> > > > > The problem is nobody could come up with a convincing model
> > > > > for this that is sound.  Currently GCC breaks the requirement
> > > > > that roundtrips through integers have to work in all cases
> > > > > because sometimes the compiler gets confused about the
> > > > > provenance of the back-converted pointer and assigns the
> > > > > wrong one.
> > > >
> > > > Does it?  I don't remember such a case, can you point me to it?
> > >
> > > I think there are couple PRs related to this. One which
> > > illustrates the underlying issue nicely is this one:
> > >
> > > https://gcc.gnu.org/bugzilla/show_bug.cgi?id=65752
> > >
> > > #include <stdio.h>
> > > #include <stdint.h>
> > > #include <limits.h>
> > >
> > > int main() {
> > >   int x = 0, *p = 0;
> > >   for (uintptr_t i = 0; ; i++) {
> > >     if (i == (uintptr_t)&x) { p = (int*)i; break; }
> > >   }
> > >   *p = 15;
> > >   printf("%d\n", x);
> > > }
> > >
> > > The loop is a no-op integer transformation that should set p to the
> > > address of &x.  But the compiler is not able to understand it and
> > > forgets the provenance.  The C standard requires that if you transform
> > > the same integer back, you get the same pointer.  So this is wrong.
> > >
> > >
> > > If one tried to formulate consistent rules which make this example
> > > have UB, then you would need to formulate some set rules that exactly
> > > specifies how all possible operations on integers affect their
> > > provenance, and this ruleset might then say that copying integers leads
> > > to a loss of provenance.  But this then also means in general that
> > > all optimizations GCC does on integers would need to conform to
> > > these rules about provenance, and not naively assume that integers
> > > are just integers.   As reasoning based on value equivalency goes
> > > wrong already for pointers, I assume it is practically impossible to make
> > > it work consistently for all integer operations.
> > >
> > >
> > > Dropping provenance for integers will remove this problem completely
> > > at the cost of some optimizations, and I think we should support a
> > > correct mode at least as an option.   This dropping of provenance could
> > > also be done in the FE by inserting some __builtin or similar.
> > >
> > > >
> > > > >
> > > > > The model that *is* sound is to treat conversion to integer as
> > > > > escaped and pointers converted back from integers as pointing
> > > > > to any previously escaped provenance.
> > > > >
> > > > > LLVM also gets this wrong but my understanding is that they
> > > > > want to fix this.
> > > > >
> > > > > >
> > > > > > GCC considers literal zero to have "no" provenance (unless the target
> > > > > > claims objects can exist at address zero).  So (int *)((intptr_t)ptr + 0)
> > > > > > retains the provenance of ptr.  (int *)((intptr_t)ptr + 4) OTOH has
> > > > > > provenance of ptr merged with 'nonlocal' provenance (a literal address
> > > > > > never has provenance of a stack object).  That is, constant folding
> > > > > > loses the fact that (void *)0 + 4 would have "no" provenance (actually
> > > > > > not sure whether the null "object" is subject to pointer arithmetic
> > > > > > constraints).
> > > > > >
> > > > > > There's one thing GCC gets wrong (see some PRs) which is
> > > > > > "conditional provenance".
> > > > > >
> > > > > >  if (p == q)
> > > > > >    /* we now should treat p and q as having unioned provenance since
> > > > > >       p can be substituted for q (and vice versa) by the compiler.  */
> > > > > >
> > > > > > I have not yet seen a good answer to this from the C pointer provenance proposal
> > > > > > folks.
> > > > >
> > > > > I am not sure what answer you want. This optimization is unsound.
> > > > >
> > > > > I think one could retain such optimizations by adding some additional
> > > > > conditions that exclude the special case that p and q have different
> > > > > provenance but the same address.
> > > >
> > > > I don't think this is workable for GCC.  We'd have to disable all
> > > > conditional copy propagation (in the GCC case for both pointers
> > > > and integers, since the latter carry provenance).
> > >
> > > I think we should have a mode that does not carry provenance
> > > via integers.  This is also what LLVM will do as far as I know,
> > > and also what the folks working on Rust semantics wanted once
> > > I last talked to them.
> > >
> > >
> > > Martin
> > >
> > >
> > > > My other "simple"
> > > > fix would be to make sure to unify provenances of p and q when
> > > > there's an equality compare but even that's a bit difficult if you
> > > > consider (SSA form)
> > > >
> > > >   p_1 = p_2 + 1;
> > > >   if (p_1 == q_3)
> > > >     ...
> > > >
> > > > not only p_1 and q_3 would have to unify provenances but of course
> > > > also p_2 and all other pointers based on (or related to) p_1.
> > > >
> > > > So I understand why you think that conditional copy propgation
> > > > is "unsound", because it does not play well with provenances.
> > > >
> > > > Richard.
> > > >
> > > > > Martin
> > > > >
> > > > > >
> > > > > > Richard.
> > > > > >
> > > > > > >
> > > > > > > Martin
> > > > > > >
> > > > > > >
> > > > > > > >
> > > > > > > > 3. The POINTER_PLUS operation is UB if the calculation overflows and
> > > > > > > > TYPE_OVERFLOW_WRAPS(ptr_type) is false.
> > > > > > > >
> > > > > > > > 4. The rules are the same for the calculations done in MEM_REF and
> > > > > > > > TARGET_MEM_REF as for POINTER_PLUS.
> > > > > > > >
> > > > > > > > Question: For the TARGET_MEM_REF calculation:
> > > > > > > >    BASE + STEP * INDEX + INDEX2 + OFFSET
> > > > > > > > Is it treated as one POINTER_PLUS, i.e.
> > > > > > > >    BASE + (STEP * INDEX + INDEX2 + OFFSET)
> > > > > > > > or as two (i.e. do we care about overflow and OOB between the two index
> > > > > > > > calculations)?
> > > > > > > >
> > > > > > > >
> > > > > > > > FWIW, the vectorizer and ivopts do introduce pointers that are outside the
> > > > > > > > object (which is why I allowed it in my current semantics)...
> > > > > > > >
> > > > > > > >     /Krister

Re: pointer comparison in GIMPLE

[Martin Uecker]

Am Samstag, dem 13.12.2025 um 11:25 +0100 schrieb Richard Biener:
> On Sat, Dec 13, 2025 at 11:23 AM Richard Biener
> <richard.guenther@gmail.com> wrote:
> > 
> > On Fri, Dec 12, 2025 at 6:41 PM Martin Uecker <muecker@gwdg.de> wrote:
> > > 
> > > 
> > > 
> > > This version is even nicer: https://godbolt.org/z/3M4Y6Pa3h
> > > 
> > > In both cases the compiler understands that the function is the
> > > identity on integers and optimizes it to a move, but it still
> > > makes an aliasing decision that is inconsistent with this basic
> > > fact when this integer is back-converted to a pointer.
> > 
> > Both show the issue is that we consider integers of unknown provenance
> > to only point to global variables, never to stack ones.  This "rule" is derived
> > from the idea of no code doing such thing but eventually having global
> > variables laid out at absolute addresses.  Conditional copy propagating of
> > (uintptr_t)&x to the assignment site would also avoid the issue since the
> > provenance is no longer transfered by an equivalence but an assignment.
> > That it works when retaining the function call (see below for your godbolt
> > case inline) shows that nonlocal properly handles escaped "integers".
> > But with inlining it degenerates.

Yes. It is clear that these are corner cases, but I am not sure
such things could never happen in real code.   There are also provenance
issues for reallocation at the same address.

But even if not, it is a conceptual problem that hinders efforts
in formal verification.

> > 
> > This is also easier to fix than dropping integer provenance tracking.  Simply
> > by making 100 not have nonlocal but anything provenance (also at some cost).
> 
> That said, it should be reasonably easy to add a -fstrict-provenance flag.  But
> I'd rather have that adhere to whatever the C or C++ standard come up with
> rather than something we make up. 

The proposal currently favoured by WG14 is TS 6010.  I think we could
add a flag for this.   The idea with the TS is that get tried out 
so that it can still get modified for integration into the IS based
on the experience, such as complications while implementing it, serious
performance or usability issues.

Martin


>  There's always -fno-tree-pta.  As said,
> I view the conditional equivalence problem as the most practical one we
> currently have (although also only on fuzzed testcases at this point).

> 
> Richard.
> 
> > #include <stdio.h>
> > #include <stdint.h>
> > #include <limits.h>
> > 
> > #ifdef NOIPA
> > [[gnu::noipa]]
> > #endif
> > uintptr_t id(uintptr_t x)
> > {
> >   return x;
> >     uintptr_t i = 0;
> >     while (1)
> >         if (++i == x) break;
> >     return i;
> > }
> > 
> > int main()
> > {
> >     int x = 0;
> >     int *p = (int*)id((uintptr_t)&x);
> >     *p = 15;
> >     printf("%d\n", x);
> > }
> > 
> > IMO while academically interesting the loop case isn't of practical concern,
> > the conditional equivalence one is more so.
> > 
> > Btw, we can properly handle "pointer difference addressing" where you
> > construct a pointer to an object from the difference of two object pointers.
> > "Properly" as in, we can optimize this.
> > 
> >   int *i = malloc (4);
> >   int *j = malloc (4);
> >   ptrdiff_t diff = (uintptr_t)i - (uintptr_t)j;
> >   int *ip = (int *)((uintptr_t)j + diff);
> > 
> > This was once a common way of handling pointers in sysv shared memory from
> > different processes and IIRC this was important to optimize this use-case.  The
> > other was from Matlab generated code which plumbed C <-> fortran by marshalling
> > 64bit C pointers through fortan routines by splitting into two halves
> > and passing as
> > double values.  So yes, we also track provenance through FP values.
> > 
> > That said, we arrived here by optimization needs plus handling code in the wild
> > correctly that's invalid with strict reading of the C standard (which
> > only allows
> > back-and-forth casting of pointer-to-integer of exactly the original
> > pointer value,
> > not any offsetted value).
> > 
> > Richard.
> > 
> > > Martin
> > > 
> > > Am Freitag, dem 12.12.2025 um 18:23 +0100 schrieb Martin Uecker:
> > > > Am Freitag, dem 12.12.2025 um 16:16 +0100 schrieb Richard Biener:
> > > > > On Thu, Dec 11, 2025 at 8:33 PM Martin Uecker <muecker@gwdg.de> wrote:
> > > > > > 
> > > > > > Am Donnerstag, dem 11.12.2025 um 12:48 +0100 schrieb Richard Biener:
> > > > > > > On Thu, Dec 11, 2025 at 7:48 AM Martin Uecker <muecker@gwdg.de> wrote:
> > > > > > > > 
> > > > > > > > Am Donnerstag, dem 11.12.2025 um 04:12 +0000 schrieb Krister Walfridsson via Gcc:
> > > > > > > > > On Wed, 10 Dec 2025, Richard Biener wrote:
> > > > > > > > > 
> > > > > > > > > > > The problem is that in GIMPLE, a pointer does not need to be in bounds. The caller could call the function with a value of i such that p + i happens to be equal to &a. So, as I understand it, the GIMPLE semantics do not allow the pass to conclude that p + i == &a is false, unless p + i is dereferenced (because dereferencing a through p + i would be UB due to provenance).
> > > > > > > > > > 
> > > > > > > > > > GIMPLE adopts most of the C pointer restrictions here thus we can (and do) conclude that pointers stay within an object when advanced.  This is used by the PTA pass which results are used when we optimize your example.  You have to divert to integer arithmetic to circumvent this and the PTA pass, while tracking provenance through integers as well, does the right thing with this.
> > > > > > > > > 
> > > > > > > > > Great, that is much better for smtgcc than the semantics I have currently
> > > > > > > > > implemented!
> > > > > > > > > 
> > > > > > > > > But it is not completely clear to me what "most of the C pointer
> > > > > > > > > restrictions" implies. Is the following a correct interpretation?
> > > > > > > > > 
> > > > > > > > > 1. A pointer must contain a value that points into (or one past) an object
> > > > > > > > > corresponding to its provenance (where a pointer may have multiple
> > > > > > > > > provenances). Otherwise it invokes undefined behavior.
> > > > > > > > > 
> > > > > > > > > 2. The provenance used for the result of POINTER_PLUS is the union of the
> > > > > > > > > provenances for the two arguments.
> > > > > > > > 
> > > > > > > > Note that in C one argument would be an integer and there is no
> > > > > > > > provenance on integers in C as this can not work consistently.
> > > > > > > > 
> > > > > > > > (and I think GCC gets this wrong)
> > > > > > > 
> > > > > > > What GCC gets "right" (right in terms of improving optimization) is
> > > > > > > that (int *)(intptr_t)ptr has the same provenance as ptr.
> > > > > > 
> > > > > > The problem is nobody could come up with a convincing model
> > > > > > for this that is sound.  Currently GCC breaks the requirement
> > > > > > that roundtrips through integers have to work in all cases
> > > > > > because sometimes the compiler gets confused about the
> > > > > > provenance of the back-converted pointer and assigns the
> > > > > > wrong one.
> > > > > 
> > > > > Does it?  I don't remember such a case, can you point me to it?
> > > > 
> > > > I think there are couple PRs related to this. One which
> > > > illustrates the underlying issue nicely is this one:
> > > > 
> > > > https://gcc.gnu.org/bugzilla/show_bug.cgi?id=65752
> > > > 
> > > > #include <stdio.h>
> > > > #include <stdint.h>
> > > > #include <limits.h>
> > > > 
> > > > int main() {
> > > >   int x = 0, *p = 0;
> > > >   for (uintptr_t i = 0; ; i++) {
> > > >     if (i == (uintptr_t)&x) { p = (int*)i; break; }
> > > >   }
> > > >   *p = 15;
> > > >   printf("%d\n", x);
> > > > }
> > > > 
> > > > The loop is a no-op integer transformation that should set p to the
> > > > address of &x.  But the compiler is not able to understand it and
> > > > forgets the provenance.  The C standard requires that if you transform
> > > > the same integer back, you get the same pointer.  So this is wrong.
> > > > 
> > > > 
> > > > If one tried to formulate consistent rules which make this example
> > > > have UB, then you would need to formulate some set rules that exactly
> > > > specifies how all possible operations on integers affect their
> > > > provenance, and this ruleset might then say that copying integers leads
> > > > to a loss of provenance.  But this then also means in general that
> > > > all optimizations GCC does on integers would need to conform to
> > > > these rules about provenance, and not naively assume that integers
> > > > are just integers.   As reasoning based on value equivalency goes
> > > > wrong already for pointers, I assume it is practically impossible to make
> > > > it work consistently for all integer operations.
> > > > 
> > > > 
> > > > Dropping provenance for integers will remove this problem completely
> > > > at the cost of some optimizations, and I think we should support a
> > > > correct mode at least as an option.   This dropping of provenance could
> > > > also be done in the FE by inserting some __builtin or similar.
> > > > 
> > > > > 
> > > > > > 
> > > > > > The model that *is* sound is to treat conversion to integer as
> > > > > > escaped and pointers converted back from integers as pointing
> > > > > > to any previously escaped provenance.
> > > > > > 
> > > > > > LLVM also gets this wrong but my understanding is that they
> > > > > > want to fix this.
> > > > > > 
> > > > > > > 
> > > > > > > GCC considers literal zero to have "no" provenance (unless the target
> > > > > > > claims objects can exist at address zero).  So (int *)((intptr_t)ptr + 0)
> > > > > > > retains the provenance of ptr.  (int *)((intptr_t)ptr + 4) OTOH has
> > > > > > > provenance of ptr merged with 'nonlocal' provenance (a literal address
> > > > > > > never has provenance of a stack object).  That is, constant folding
> > > > > > > loses the fact that (void *)0 + 4 would have "no" provenance (actually
> > > > > > > not sure whether the null "object" is subject to pointer arithmetic
> > > > > > > constraints).
> > > > > > > 
> > > > > > > There's one thing GCC gets wrong (see some PRs) which is
> > > > > > > "conditional provenance".
> > > > > > > 
> > > > > > >  if (p == q)
> > > > > > >    /* we now should treat p and q as having unioned provenance since
> > > > > > >       p can be substituted for q (and vice versa) by the compiler.  */
> > > > > > > 
> > > > > > > I have not yet seen a good answer to this from the C pointer provenance proposal
> > > > > > > folks.
> > > > > > 
> > > > > > I am not sure what answer you want. This optimization is unsound.
> > > > > > 
> > > > > > I think one could retain such optimizations by adding some additional
> > > > > > conditions that exclude the special case that p and q have different
> > > > > > provenance but the same address.
> > > > > 
> > > > > I don't think this is workable for GCC.  We'd have to disable all
> > > > > conditional copy propagation (in the GCC case for both pointers
> > > > > and integers, since the latter carry provenance).
> > > > 
> > > > I think we should have a mode that does not carry provenance
> > > > via integers.  This is also what LLVM will do as far as I know,
> > > > and also what the folks working on Rust semantics wanted once
> > > > I last talked to them.
> > > > 
> > > > 
> > > > Martin
> > > > 
> > > > 
> > > > > My other "simple"
> > > > > fix would be to make sure to unify provenances of p and q when
> > > > > there's an equality compare but even that's a bit difficult if you
> > > > > consider (SSA form)
> > > > > 
> > > > >   p_1 = p_2 + 1;
> > > > >   if (p_1 == q_3)
> > > > >     ...
> > > > > 
> > > > > not only p_1 and q_3 would have to unify provenances but of course
> > > > > also p_2 and all other pointers based on (or related to) p_1.
> > > > > 
> > > > > So I understand why you think that conditional copy propgation
> > > > > is "unsound", because it does not play well with provenances.
> > > > > 
> > > > > Richard.
> > > > > 
> > > > > > Martin
> > > > > > 
> > > > > > > 
> > > > > > > Richard.
> > > > > > > 
> > > > > > > > 
> > > > > > > > Martin
> > > > > > > > 
> > > > > > > > 
> > > > > > > > > 
> > > > > > > > > 3. The POINTER_PLUS operation is UB if the calculation overflows and
> > > > > > > > > TYPE_OVERFLOW_WRAPS(ptr_type) is false.
> > > > > > > > > 
> > > > > > > > > 4. The rules are the same for the calculations done in MEM_REF and
> > > > > > > > > TARGET_MEM_REF as for POINTER_PLUS.
> > > > > > > > > 
> > > > > > > > > Question: For the TARGET_MEM_REF calculation:
> > > > > > > > >    BASE + STEP * INDEX + INDEX2 + OFFSET
> > > > > > > > > Is it treated as one POINTER_PLUS, i.e.
> > > > > > > > >    BASE + (STEP * INDEX + INDEX2 + OFFSET)
> > > > > > > > > or as two (i.e. do we care about overflow and OOB between the two index
> > > > > > > > > calculations)?
> > > > > > > > > 
> > > > > > > > > 
> > > > > > > > > FWIW, the vectorizer and ivopts do introduce pointers that are outside the
> > > > > > > > > object (which is why I allowed it in my current semantics)...
> > > > > > > > > 
> > > > > > > > >     /Krister

Re: pointer comparison in GIMPLE

[Martin Uecker]

Am Samstag, dem 13.12.2025 um 11:23 +0100 schrieb Richard Biener:
> On Fri, Dec 12, 2025 at 6:41 PM Martin Uecker <muecker@gwdg.de> wrote:
> > 
> > 
> > 
> > This version is even nicer: https://godbolt.org/z/3M4Y6Pa3h
> > 
> > In both cases the compiler understands that the function is the
> > identity on integers and optimizes it to a move, but it still
> > makes an aliasing decision that is inconsistent with this basic
> > fact when this integer is back-converted to a pointer.
> 
> Both show the issue is that we consider integers of unknown provenance
> to only point to global variables, never to stack ones.  This "rule" is derived
> from the idea of no code doing such thing but eventually having global
> variables laid out at absolute addresses.  Conditional copy propagating of
> (uintptr_t)&x to the assignment site would also avoid the issue since the
> provenance is no longer transfered by an equivalence but an assignment.
> That it works when retaining the function call (see below for your godbolt
> case inline) shows that nonlocal properly handles escaped "integers".
> But with inlining it degenerates.
> 
> This is also easier to fix than dropping integer provenance tracking.  Simply
> by making 100 not have nonlocal but anything provenance (also at some cost).
> 
> #include <stdio.h>
> #include <stdint.h>
> #include <limits.h>
> 
> #ifdef NOIPA
> [[gnu::noipa]]
> #endif
> uintptr_t id(uintptr_t x)
> {
>   return x;
>     uintptr_t i = 0;
>     while (1)
>         if (++i == x) break;
>     return i;
> }
> 
> int main()
> {
>     int x = 0;
>     int *p = (int*)id((uintptr_t)&x);
>     *p = 15;
>     printf("%d\n", x);
> }
> 
> IMO while academically interesting the loop case isn't of practical concern,
> the conditional equivalence one is more so.

Yes, but it just illustrates nicely that once you track provenance via
integers, usual transformation of code using integer are not necessarily
consistent with it, and the provenance information  then
depends on where during optimization you extract it, which makes it
difficult to come up with a consistent model.

> 
> Btw, we can properly handle "pointer difference addressing" where you
> construct a pointer to an object from the difference of two object pointers.
> "Properly" as in, we can optimize this.
> 
>   int *i = malloc (4);
>   int *j = malloc (4);
>   ptrdiff_t diff = (uintptr_t)i - (uintptr_t)j;
>   int *ip = (int *)((uintptr_t)j + diff);
> 
> This was once a common way of handling pointers in sysv shared memory from
> different processes and IIRC this was important to optimize this use-case.  The
> other was from Matlab generated code which plumbed C <-> fortran by marshalling
> 64bit C pointers through fortan routines by splitting into two halves
> and passing as
> double values.  So yes, we also track provenance through FP values.

I am still wondering to what extend these optimization could not
be preserved also in a strict provenance model.

Martin

> 
> That said, we arrived here by optimization needs plus handling code in the wild
> correctly that's invalid with strict reading of the C standard (which
> only allows
> back-and-forth casting of pointer-to-integer of exactly the original
> pointer value,
> not any offsetted value).
> 
> Richard.
> 
> > Martin
> > 
> > Am Freitag, dem 12.12.2025 um 18:23 +0100 schrieb Martin Uecker:
> > > Am Freitag, dem 12.12.2025 um 16:16 +0100 schrieb Richard Biener:
> > > > On Thu, Dec 11, 2025 at 8:33 PM Martin Uecker <muecker@gwdg.de> wrote:
> > > > > 
> > > > > Am Donnerstag, dem 11.12.2025 um 12:48 +0100 schrieb Richard Biener:
> > > > > > On Thu, Dec 11, 2025 at 7:48 AM Martin Uecker <muecker@gwdg.de> wrote:
> > > > > > > 
> > > > > > > Am Donnerstag, dem 11.12.2025 um 04:12 +0000 schrieb Krister Walfridsson via Gcc:
> > > > > > > > On Wed, 10 Dec 2025, Richard Biener wrote:
> > > > > > > > 
> > > > > > > > > > The problem is that in GIMPLE, a pointer does not need to be in bounds. The caller could call the function with a value of i such that p + i happens to be equal to &a. So, as I understand it, the GIMPLE semantics do not allow the pass to conclude that p + i == &a is false, unless p + i is dereferenced (because dereferencing a through p + i would be UB due to provenance).
> > > > > > > > > 
> > > > > > > > > GIMPLE adopts most of the C pointer restrictions here thus we can (and do) conclude that pointers stay within an object when advanced.  This is used by the PTA pass which results are used when we optimize your example.  You have to divert to integer arithmetic to circumvent this and the PTA pass, while tracking provenance through integers as well, does the right thing with this.
> > > > > > > > 
> > > > > > > > Great, that is much better for smtgcc than the semantics I have currently
> > > > > > > > implemented!
> > > > > > > > 
> > > > > > > > But it is not completely clear to me what "most of the C pointer
> > > > > > > > restrictions" implies. Is the following a correct interpretation?
> > > > > > > > 
> > > > > > > > 1. A pointer must contain a value that points into (or one past) an object
> > > > > > > > corresponding to its provenance (where a pointer may have multiple
> > > > > > > > provenances). Otherwise it invokes undefined behavior.
> > > > > > > > 
> > > > > > > > 2. The provenance used for the result of POINTER_PLUS is the union of the
> > > > > > > > provenances for the two arguments.
> > > > > > > 
> > > > > > > Note that in C one argument would be an integer and there is no
> > > > > > > provenance on integers in C as this can not work consistently.
> > > > > > > 
> > > > > > > (and I think GCC gets this wrong)
> > > > > > 
> > > > > > What GCC gets "right" (right in terms of improving optimization) is
> > > > > > that (int *)(intptr_t)ptr has the same provenance as ptr.
> > > > > 
> > > > > The problem is nobody could come up with a convincing model
> > > > > for this that is sound.  Currently GCC breaks the requirement
> > > > > that roundtrips through integers have to work in all cases
> > > > > because sometimes the compiler gets confused about the
> > > > > provenance of the back-converted pointer and assigns the
> > > > > wrong one.
> > > > 
> > > > Does it?  I don't remember such a case, can you point me to it?
> > > 
> > > I think there are couple PRs related to this. One which
> > > illustrates the underlying issue nicely is this one:
> > > 
> > > https://gcc.gnu.org/bugzilla/show_bug.cgi?id=65752
> > > 
> > > #include <stdio.h>
> > > #include <stdint.h>
> > > #include <limits.h>
> > > 
> > > int main() {
> > >   int x = 0, *p = 0;
> > >   for (uintptr_t i = 0; ; i++) {
> > >     if (i == (uintptr_t)&x) { p = (int*)i; break; }
> > >   }
> > >   *p = 15;
> > >   printf("%d\n", x);
> > > }
> > > 
> > > The loop is a no-op integer transformation that should set p to the
> > > address of &x.  But the compiler is not able to understand it and
> > > forgets the provenance.  The C standard requires that if you transform
> > > the same integer back, you get the same pointer.  So this is wrong.
> > > 
> > > 
> > > If one tried to formulate consistent rules which make this example
> > > have UB, then you would need to formulate some set rules that exactly
> > > specifies how all possible operations on integers affect their
> > > provenance, and this ruleset might then say that copying integers leads
> > > to a loss of provenance.  But this then also means in general that
> > > all optimizations GCC does on integers would need to conform to
> > > these rules about provenance, and not naively assume that integers
> > > are just integers.   As reasoning based on value equivalency goes
> > > wrong already for pointers, I assume it is practically impossible to make
> > > it work consistently for all integer operations.
> > > 
> > > 
> > > Dropping provenance for integers will remove this problem completely
> > > at the cost of some optimizations, and I think we should support a
> > > correct mode at least as an option.   This dropping of provenance could
> > > also be done in the FE by inserting some __builtin or similar.
> > > 
> > > > 
> > > > > 
> > > > > The model that *is* sound is to treat conversion to integer as
> > > > > escaped and pointers converted back from integers as pointing
> > > > > to any previously escaped provenance.
> > > > > 
> > > > > LLVM also gets this wrong but my understanding is that they
> > > > > want to fix this.
> > > > > 
> > > > > > 
> > > > > > GCC considers literal zero to have "no" provenance (unless the target
> > > > > > claims objects can exist at address zero).  So (int *)((intptr_t)ptr + 0)
> > > > > > retains the provenance of ptr.  (int *)((intptr_t)ptr + 4) OTOH has
> > > > > > provenance of ptr merged with 'nonlocal' provenance (a literal address
> > > > > > never has provenance of a stack object).  That is, constant folding
> > > > > > loses the fact that (void *)0 + 4 would have "no" provenance (actually
> > > > > > not sure whether the null "object" is subject to pointer arithmetic
> > > > > > constraints).
> > > > > > 
> > > > > > There's one thing GCC gets wrong (see some PRs) which is
> > > > > > "conditional provenance".
> > > > > > 
> > > > > >  if (p == q)
> > > > > >    /* we now should treat p and q as having unioned provenance since
> > > > > >       p can be substituted for q (and vice versa) by the compiler.  */
> > > > > > 
> > > > > > I have not yet seen a good answer to this from the C pointer provenance proposal
> > > > > > folks.
> > > > > 
> > > > > I am not sure what answer you want. This optimization is unsound.
> > > > > 
> > > > > I think one could retain such optimizations by adding some additional
> > > > > conditions that exclude the special case that p and q have different
> > > > > provenance but the same address.
> > > > 
> > > > I don't think this is workable for GCC.  We'd have to disable all
> > > > conditional copy propagation (in the GCC case for both pointers
> > > > and integers, since the latter carry provenance).
> > > 
> > > I think we should have a mode that does not carry provenance
> > > via integers.  This is also what LLVM will do as far as I know,
> > > and also what the folks working on Rust semantics wanted once
> > > I last talked to them.
> > > 
> > > 
> > > Martin
> > > 
> > > 
> > > > My other "simple"
> > > > fix would be to make sure to unify provenances of p and q when
> > > > there's an equality compare but even that's a bit difficult if you
> > > > consider (SSA form)
> > > > 
> > > >   p_1 = p_2 + 1;
> > > >   if (p_1 == q_3)
> > > >     ...
> > > > 
> > > > not only p_1 and q_3 would have to unify provenances but of course
> > > > also p_2 and all other pointers based on (or related to) p_1.
> > > > 
> > > > So I understand why you think that conditional copy propgation
> > > > is "unsound", because it does not play well with provenances.
> > > > 
> > > > Richard.
> > > > 
> > > > > Martin
> > > > > 
> > > > > > 
> > > > > > Richard.
> > > > > > 
> > > > > > > 
> > > > > > > Martin
> > > > > > > 
> > > > > > > 
> > > > > > > > 
> > > > > > > > 3. The POINTER_PLUS operation is UB if the calculation overflows and
> > > > > > > > TYPE_OVERFLOW_WRAPS(ptr_type) is false.
> > > > > > > > 
> > > > > > > > 4. The rules are the same for the calculations done in MEM_REF and
> > > > > > > > TARGET_MEM_REF as for POINTER_PLUS.
> > > > > > > > 
> > > > > > > > Question: For the TARGET_MEM_REF calculation:
> > > > > > > >    BASE + STEP * INDEX + INDEX2 + OFFSET
> > > > > > > > Is it treated as one POINTER_PLUS, i.e.
> > > > > > > >    BASE + (STEP * INDEX + INDEX2 + OFFSET)
> > > > > > > > or as two (i.e. do we care about overflow and OOB between the two index
> > > > > > > > calculations)?
> > > > > > > > 
> > > > > > > > 
> > > > > > > > FWIW, the vectorizer and ivopts do introduce pointers that are outside the
> > > > > > > > object (which is why I allowed it in my current semantics)...
> > > > > > > > 
> > > > > > > >     /Krister