[Bug c++/78655] gcc doesn't exploit the fact that the result of pointer addition can not be nullptr

[Bug c++/78655] gcc doesn't exploit the fact that the result of pointer addition can not be nullptr

[amacleod at redhat dot com]

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

Andrew Macleod <amacleod at redhat dot com> changed:

           What    |Removed                     |Added
----------------------------------------------------------------------------
                 CC|                            |amacleod at redhat dot com

--- Comment #9 from Andrew Macleod <amacleod at redhat dot com> ---
Created attachment 49556
  --> https://gcc.gnu.org/bugzilla/attachment.cgi?id=49556&action=edit
testcase

(In reply to Marc Glisse from comment #8)
> (just to put this somewhere)
> We have multiple ways of doing pointer arithmetic in gcc. After the recent
> patch, we know that g returns nonnull, but we don't know it for f.
> 
> struct A{int a,b;};
> int*f(A*p){return&p->b;}
> int*g(A*p){return(int*)p+1;}

I tweaked this and made a testcase out of it. I think it is correct?  
We do know that both f and g are non-null now, as well as checks for when
returning p->a for 0 offsets... So I think this is covered?

Furthermore,

bool f(int* a)
{
  bool x = a == nullptr;
  a += 10;
  return x;
}
turns into
a_1(D)  int * VARYING
    <bb 2> :
    x_2 = a_1(D) == 0B;
    a_3 = a_1(D) + 40;
    return x_2;

a_3 : int * [1B, +INF]

And from there, I don't see any way to determine that 'a_1' can't be nullptr. 
we've lost whatever context nullptr is suppose to provide... its just a 0 now.
All we can see is that a_3 is non-null.

[Bug c++/78655] gcc doesn't exploit the fact that the result of pointer addition can not be nullptr

[amacleod at redhat dot com]

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

--- Comment #10 from Andrew Macleod <amacleod at redhat dot com> ---
We currently get everything except the last tidbit.

a_1(D)  int * VARYING
    <bb 2> :
    x_2 = a_1(D) == 0B;
    a_3 = a_1(D) + 40;
    return x_2;

When we see
   a_3 = a_1(D) + 40;

Are we allowed to assume that a_1 is non-null, just like we do with *a_1? That
seems a little dicier

Because if that is a valid assumption, we can handle pointer_plus the same as
we do non-null pointer tracking of dereferences.  That alone might handle it. 
We could also consider recalculating x_2 at the return location if need be.

If we cant make that assumption, then there isn't much else to do here as the
rest of the PR is covered.

[Bug c++/78655] gcc doesn't exploit the fact that the result of pointer addition can not be nullptr

[law at gcc dot gnu.org]

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

--- Comment #11 from Jeffrey A. Law <law at gcc dot gnu.org> ---
We can assume that the result of a POINTER_PLUS is non-null if either argument
is non-null.  So X + constant is always non-null.  X + Y would be non-null if
either X or Y is known to be non-null.

If we know that X + Y is non-null via some mechanism (for example the result
was dereferenced), then we know that X and Y are non-null.

[Bug c++/78655] gcc doesn't exploit the fact that the result of pointer addition can not be nullptr

[rguenth at gcc dot gnu.org]

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

--- Comment #12 from Richard Biener <rguenth at gcc dot gnu.org> ---
(In reply to Jeffrey A. Law from comment #11)
> We can assume that the result of a POINTER_PLUS is non-null if either
> argument is non-null.  So X + constant is always non-null.  X + Y would be
> non-null if either X or Y is known to be non-null.
> 
> If we know that X + Y is non-null via some mechanism (for example the result
> was dereferenced), then we know that X and Y are non-null.

Yes, that summarizes it.  Note this only applies when
!targetm.addr_space.zero_address_valid.  There non-null plus a negative offset
may yield null.

Btw, the old VRP did this already, so I wonder whether it isn't already handled
correctly (minus the addr space thing maybe).

[Bug c++/78655] gcc doesn't exploit the fact that the result of pointer addition can not be nullptr

[amacleod at redhat dot com]

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

--- Comment #13 from Andrew Macleod <amacleod at redhat dot com> ---
Probably.  rangers nonnull processing also invokes infer_nonnull_range () on
the statement, so should also be picking it up.

The latter test case is really about recomputation then

    x_2 = a_1(D) == 0B;
    a_3 = a_1(D) + 40;
    return x_2;

When x_2 is defined, we don't know that it is non-null.  we only know its
non-null if we were to recompute its value at the use in return x_2.

We can leave this for now.. I'll follow up with it when we revisit the nonnull
processing and recomputation model for the next stage 1.

[Bug c++/78655] gcc doesn't exploit the fact that the result of pointer addition can not be nullptr

[amacleod at redhat dot com]

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

Andrew Macleod <amacleod at redhat dot com> changed:

           What    |Removed                     |Added
----------------------------------------------------------------------------
             Status|NEW                         |ASSIGNED
           Assignee|unassigned at gcc dot gnu.org      |amacleod at redhat dot com

--- Comment #14 from Andrew Macleod <amacleod at redhat dot com> ---
Created attachment 53910
  --> https://gcc.gnu.org/bugzilla/attachment.cgi?id=53910&action=edit
patch to fix the problem

This patch fixes the PR, but exposes issues in other passes.  They introduce
undefined behaviour by hoisting POINTER_PLUS expressions into blocks in which
the operand is not known to be non-null.   (See PR 107709)
Until this can be audited fully, we put this patch on hold.

[Bug c++/78655] gcc doesn't exploit the fact that the result of pointer addition can not be nullptr

[rguenther at suse dot de]

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

--- Comment #15 from rguenther at suse dot de <rguenther at suse dot de> ---
On Wed, 16 Nov 2022, amacleod at redhat dot com wrote:

> https://gcc.gnu.org/bugzilla/show_bug.cgi?id=78655
> 
> Andrew Macleod <amacleod at redhat dot com> changed:
> 
>            What    |Removed                     |Added
> ----------------------------------------------------------------------------
>              Status|NEW                         |ASSIGNED
>            Assignee|unassigned at gcc dot gnu.org      |amacleod at redhat dot com
> 
> --- Comment #14 from Andrew Macleod <amacleod at redhat dot com> ---
> Created attachment 53910
>   --> https://gcc.gnu.org/bugzilla/attachment.cgi?id=53910&action=edit
> patch to fix the problem
> 
> This patch fixes the PR, but exposes issues in other passes.  They introduce
> undefined behaviour by hoisting POINTER_PLUS expressions into blocks in which
> the operand is not known to be non-null.   (See PR 107709)
> Until this can be audited fully, we put this patch on hold.

In fact the patch doesnt 'exploit the fact that the result of
pointer addition can not be nullptr' but it exploits that if
ptr + CST is performed then 'ptr' cannot be nullptr(?)

That is, it assumes that there is a zero sized object at nullptr and
thus the pointer increment to outside (but not one after it) invokes UB.

That's much more aggressive than optimizing

  ptr + 4 != nullptr

to true and I'm not sure the reasoning follows.  I think at 'nullptr'
there is _no_ object and thus the restriction to pointer addition
doesn't apply at all - if a pointer does not refer to an object then
the rule that increment to outside of the object invokes UB doesn't 
apply.

[Bug c++/78655] gcc doesn't exploit the fact that the result of pointer addition can not be nullptr

[amacleod at redhat dot com]

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

--- Comment #16 from Andrew Macleod <amacleod at redhat dot com> ---
(In reply to rguenther@suse.de from comment #15)
> On Wed, 16 Nov 2022, amacleod at redhat dot com wrote:
> 
> > https://gcc.gnu.org/bugzilla/show_bug.cgi?id=78655
> > 
> > Andrew Macleod <amacleod at redhat dot com> changed:
> > 
> >            What    |Removed                     |Added
> > ----------------------------------------------------------------------------
> >              Status|NEW                         |ASSIGNED
> >            Assignee|unassigned at gcc dot gnu.org      |amacleod at redhat dot com
> > 
> > --- Comment #14 from Andrew Macleod <amacleod at redhat dot com> ---
> > Created attachment 53910 [details]
> >   --> https://gcc.gnu.org/bugzilla/attachment.cgi?id=53910&action=edit
> > patch to fix the problem
> > 
> > This patch fixes the PR, but exposes issues in other passes.  They introduce
> > undefined behaviour by hoisting POINTER_PLUS expressions into blocks in which
> > the operand is not known to be non-null.   (See PR 107709)
> > Until this can be audited fully, we put this patch on hold.
> 
> In fact the patch doesnt 'exploit the fact that the result of
> pointer addition can not be nullptr' but it exploits that if
> ptr + CST is performed then 'ptr' cannot be nullptr(?)
> 

GCC already exploits the title of the PR, when the code represents it with that
situation. 
The only case we don't get is if the code is reordered slightly as the testcase
in comment 4:

bool f(int* a)
{
  bool x = a == nullptr;
  a += 10;
  return x;
}

That testcase requires this patch.  


> That is, it assumes that there is a zero sized object at nullptr and
> thus the pointer increment to outside (but not one after it) invokes UB.
> 
> That's much more aggressive than optimizing
> 
>   ptr + 4 != nullptr
> 
> to true and I'm not sure the reasoning follows.  I think at 'nullptr'
> there is _no_ object and thus the restriction to pointer addition
> doesn't apply at all - if a pointer does not refer to an object then
> the rule that increment to outside of the object invokes UB doesn't 
> apply.

It implements comment 11, and comment 12 confirmed that 11 was accurate.

(1)
>> X + Y would be non-null if either X or Y is known to be non-null.
so if Y is non-zero, X + Y is non-zero.
(2)
>> If we know that X + Y is non-null via some mechanism (for example the result was dereferenced), then we know that X and Y are non-null.
X + Y is non-null based on (2)

Going back to the code generated for this:

    x_2 = a_1(D) == 0B;
    a_3 = a_1(D) + 40;
    return x_2;

The only way to to return 1 with this sequence is for a_3 = a_1(D) + 40 to
determine that a_1 is non-zero after this statement... which is what this patch
does.
It then reapplies this knowledge as a recomputation of x_2 based on this
knowledge after the defintion of a_3.

So yes, this is much more aggressive.  I suppose in theory we could close this
PR and open a new one to cover the more aggressive version.

[Bug c++/78655] gcc doesn't exploit the fact that the result of pointer addition can not be nullptr

[rguenther at suse dot de]

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

--- Comment #17 from rguenther at suse dot de <rguenther at suse dot de> ---
On Thu, 17 Nov 2022, amacleod at redhat dot com wrote:

> https://gcc.gnu.org/bugzilla/show_bug.cgi?id=78655
> 
> --- Comment #16 from Andrew Macleod <amacleod at redhat dot com> ---
> (In reply to rguenther@suse.de from comment #15)
> > On Wed, 16 Nov 2022, amacleod at redhat dot com wrote:
> > 
> > > https://gcc.gnu.org/bugzilla/show_bug.cgi?id=78655
> > > 
> > > Andrew Macleod <amacleod at redhat dot com> changed:
> > > 
> > >            What    |Removed                     |Added
> > > ----------------------------------------------------------------------------
> > >              Status|NEW                         |ASSIGNED
> > >            Assignee|unassigned at gcc dot gnu.org      |amacleod at redhat dot com
> > > 
> > > --- Comment #14 from Andrew Macleod <amacleod at redhat dot com> ---
> > > Created attachment 53910 [details]
> > >   --> https://gcc.gnu.org/bugzilla/attachment.cgi?id=53910&action=edit
> > > patch to fix the problem
> > > 
> > > This patch fixes the PR, but exposes issues in other passes.  They introduce
> > > undefined behaviour by hoisting POINTER_PLUS expressions into blocks in which
> > > the operand is not known to be non-null.   (See PR 107709)
> > > Until this can be audited fully, we put this patch on hold.
> > 
> > In fact the patch doesnt 'exploit the fact that the result of
> > pointer addition can not be nullptr' but it exploits that if
> > ptr + CST is performed then 'ptr' cannot be nullptr(?)
> > 
> 
> GCC already exploits the title of the PR, when the code represents it with that
> situation. 
> The only case we don't get is if the code is reordered slightly as the testcase
> in comment 4:
> 
> bool f(int* a)
> {
>   bool x = a == nullptr;
>   a += 10;
>   return x;
> }
> 
> That testcase requires this patch.  
> 
> 
> > That is, it assumes that there is a zero sized object at nullptr and
> > thus the pointer increment to outside (but not one after it) invokes UB.
> > 
> > That's much more aggressive than optimizing
> > 
> >   ptr + 4 != nullptr
> > 
> > to true and I'm not sure the reasoning follows.  I think at 'nullptr'
> > there is _no_ object and thus the restriction to pointer addition
> > doesn't apply at all - if a pointer does not refer to an object then
> > the rule that increment to outside of the object invokes UB doesn't 
> > apply.
> 
> It implements comment 11, and comment 12 confirmed that 11 was accurate.
> 
> (1)
> >> X + Y would be non-null if either X or Y is known to be non-null.
> so if Y is non-zero, X + Y is non-zero.
> (2)
> >> If we know that X + Y is non-null via some mechanism (for example the result was dereferenced), then we know that X and Y are non-null.
> X + Y is non-null based on (2)

But (2) is IMHO false for 'nullptr + 4', we know from (1) that the result
is not nullptr but we don't know that _both_ are not null.  I don't see
how computing 'nullptr + 4' invokes UB.  Hmm, one might read that
into C17/6.5.6/8 "If both the pointer operand and the result point to
elements of the same array object, or one past the last element of an 
array object, the evaluation shall not produce an overflow; otherwise,
the behavior is undefined" - here nullptr and nullptr + 4 do not
point to elements of the same array object (nullptr doesn't point to
any object), so 'otherwise' applies and the behavior is undefined?

[Bug c++/78655] gcc doesn't exploit the fact that the result of pointer addition can not be nullptr

[amacleod at redhat dot com]

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

--- Comment #18 from Andrew Macleod <amacleod at redhat dot com> ---
(In reply to rguenther@suse.de from comment #17)
> On Thu, 17 Nov 2022, amacleod at redhat dot com wrote:
> 
> > https://gcc.gnu.org/bugzilla/show_bug.cgi?id=78655
> > 
> > --- Comment #16 from Andrew Macleod <amacleod at redhat dot com> ---
> > (In reply to rguenther@suse.de from comment #15)
> > > On Wed, 16 Nov 2022, amacleod at redhat dot com wrote:
> > > 
> > > > https://gcc.gnu.org/bugzilla/show_bug.cgi?id=78655
> > > > 
> > > > Andrew Macleod <amacleod at redhat dot com> changed:
> > > > 
> > > >            What    |Removed                     |Added
> > > > ----------------------------------------------------------------------------
> > > >              Status|NEW                         |ASSIGNED
> > > >            Assignee|unassigned at gcc dot gnu.org      |amacleod at redhat dot com
> > > > 
> > > > --- Comment #14 from Andrew Macleod <amacleod at redhat dot com> ---
> > > > Created attachment 53910 [details]
> > > >   --> https://gcc.gnu.org/bugzilla/attachment.cgi?id=53910&action=edit
> > > > patch to fix the problem
> > > > 
> > > > This patch fixes the PR, but exposes issues in other passes.  They introduce
> > > > undefined behaviour by hoisting POINTER_PLUS expressions into blocks in which
> > > > the operand is not known to be non-null.   (See PR 107709)
> > > > Until this can be audited fully, we put this patch on hold.
> > > 
> > > In fact the patch doesnt 'exploit the fact that the result of
> > > pointer addition can not be nullptr' but it exploits that if
> > > ptr + CST is performed then 'ptr' cannot be nullptr(?)
> > > 
> > 
> > GCC already exploits the title of the PR, when the code represents it with that
> > situation. 
> > The only case we don't get is if the code is reordered slightly as the testcase
> > in comment 4:
> > 
> > bool f(int* a)
> > {
> >   bool x = a == nullptr;
> >   a += 10;
> >   return x;
> > }
> > 
> > That testcase requires this patch.  
> > 
> > 
> > > That is, it assumes that there is a zero sized object at nullptr and
> > > thus the pointer increment to outside (but not one after it) invokes UB.
> > > 
> > > That's much more aggressive than optimizing
> > > 
> > >   ptr + 4 != nullptr
> > > 
> > > to true and I'm not sure the reasoning follows.  I think at 'nullptr'
> > > there is _no_ object and thus the restriction to pointer addition
> > > doesn't apply at all - if a pointer does not refer to an object then
> > > the rule that increment to outside of the object invokes UB doesn't 
> > > apply.
> > 
> > It implements comment 11, and comment 12 confirmed that 11 was accurate.
> > 
> > (1)
> > >> X + Y would be non-null if either X or Y is known to be non-null.
> > so if Y is non-zero, X + Y is non-zero.
> > (2)
> > >> If we know that X + Y is non-null via some mechanism (for example the result was dereferenced), then we know that X and Y are non-null.
> > X + Y is non-null based on (2)
> 
> But (2) is IMHO false for 'nullptr + 4', we know from (1) that the result
> is not nullptr but we don't know that _both_ are not null.  I don't see
> how computing 'nullptr + 4' invokes UB.  Hmm, one might read that
> into C17/6.5.6/8 "If both the pointer operand and the result point to
> elements of the same array object, or one past the last element of an 
> array object, the evaluation shall not produce an overflow; otherwise,
> the behavior is undefined" - here nullptr and nullptr + 4 do not
> point to elements of the same array object (nullptr doesn't point to
> any object), so 'otherwise' applies and the behavior is undefined?

FWIW, that would be my take...  NULL + anything would be UB.  Assuming of
course 0 is not an addressable value.