[RFC] [PR tree-optimization/92539] Optimize away tests against invalid pointers

[RFC] [PR tree-optimization/92539] Optimize away tests against invalid pointers

[Jeff Law]

Here's a potential approach to fixing PR92539, a P2 -Warray-bounds false 
positive triggered by loop unrolling.

As I speculated a couple years ago, we could eliminate the comparisons 
against bogus pointers.  Consider:

>   <bb 8> [local count: 30530247]:
>   if (last_12 != &MEM <const char> [(void *)"aa" + 3B])
>     goto <bb 9>; [54.59%]
>   else
>     goto <bb 12>; [45.41%]


That's a valid comparison as ISO allows us to generate, but not 
dereference, a pointer one element past the end of the object.

But +4B is a bogus pointer.  So given an EQ comparison against that 
pointer we could always return false and for NE always return true.

VRP and DOM seem to be the most natural choices for this kind of 
optimization on the surface.  However DOM is actually not viable because 
the out-of-bounds pointer warning pass is run at the end of VRP.  So 
we've got to take care of this prior to the end of VRP.



I haven't done a bootstrap or regression test with this.  But if it 
looks reasonable I can certainly push on it further. I have confirmed it 
does eliminate the tests and shuts up the bogus warning.

The downside is this would also shut up valid warnings if user code did 
this kind of test.

Comments/Suggestions?

Jeff

Re: [RFC] [PR tree-optimization/92539] Optimize away tests against invalid pointers

[Andrew Pinski]

On Sun, Mar 10, 2024 at 2:04 PM Jeff Law <jlaw@ventanamicro.com> wrote:
>
> Here's a potential approach to fixing PR92539, a P2 -Warray-bounds false
> positive triggered by loop unrolling.
>
> As I speculated a couple years ago, we could eliminate the comparisons
> against bogus pointers.  Consider:
>
> >   <bb 8> [local count: 30530247]:
> >   if (last_12 != &MEM <const char> [(void *)"aa" + 3B])
> >     goto <bb 9>; [54.59%]
> >   else
> >     goto <bb 12>; [45.41%]
>
>
> That's a valid comparison as ISO allows us to generate, but not
> dereference, a pointer one element past the end of the object.
>
> But +4B is a bogus pointer.  So given an EQ comparison against that
> pointer we could always return false and for NE always return true.
>
> VRP and DOM seem to be the most natural choices for this kind of
> optimization on the surface.  However DOM is actually not viable because
> the out-of-bounds pointer warning pass is run at the end of VRP.  So
> we've got to take care of this prior to the end of VRP.
>
>
>
> I haven't done a bootstrap or regression test with this.  But if it
> looks reasonable I can certainly push on it further. I have confirmed it
> does eliminate the tests and shuts up the bogus warning.
>
> The downside is this would also shut up valid warnings if user code did
> this kind of test.
>
> Comments/Suggestions?

ENOPATCH

>
> Jeff

Re: [RFC] [PR tree-optimization/92539] Optimize away tests against invalid pointers

[Jeff Law]

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



On 3/10/24 3:05 PM, Andrew Pinski wrote:
> On Sun, Mar 10, 2024 at 2:04 PM Jeff Law <jlaw@ventanamicro.com> wrote:
>>
>> Here's a potential approach to fixing PR92539, a P2 -Warray-bounds false
>> positive triggered by loop unrolling.
>>
>> As I speculated a couple years ago, we could eliminate the comparisons
>> against bogus pointers.  Consider:
>>
>>>    <bb 8> [local count: 30530247]:
>>>    if (last_12 != &MEM <const char> [(void *)"aa" + 3B])
>>>      goto <bb 9>; [54.59%]
>>>    else
>>>      goto <bb 12>; [45.41%]
>>
>>
>> That's a valid comparison as ISO allows us to generate, but not
>> dereference, a pointer one element past the end of the object.
>>
>> But +4B is a bogus pointer.  So given an EQ comparison against that
>> pointer we could always return false and for NE always return true.
>>
>> VRP and DOM seem to be the most natural choices for this kind of
>> optimization on the surface.  However DOM is actually not viable because
>> the out-of-bounds pointer warning pass is run at the end of VRP.  So
>> we've got to take care of this prior to the end of VRP.
>>
>>
>>
>> I haven't done a bootstrap or regression test with this.  But if it
>> looks reasonable I can certainly push on it further. I have confirmed it
>> does eliminate the tests and shuts up the bogus warning.
>>
>> The downside is this would also shut up valid warnings if user code did
>> this kind of test.
>>
>> Comments/Suggestions?
> 
> ENOPATCH
Yea, realized it as I pushed the send button.  Then t-bird crashed, 
repeatedly.

Attached this time..

jeff


[-- Attachment #2: P --]
[-- Type: text/plain, Size: 1270 bytes --]

diff --git a/gcc/vr-values.cc b/gcc/vr-values.cc
index 3ccb77d28be..cc753e79a8a 100644
--- a/gcc/vr-values.cc
+++ b/gcc/vr-values.cc
@@ -325,6 +325,34 @@ simplify_using_ranges::fold_cond_with_ops (enum tree_code code,
       if (res == range_false (type))
 	return boolean_false_node;
     }
+
+  /* If we're comparing pointers and one of the pointers is
+     not a valid pointer (say &MEM <const char> [(void *)"aa" + 4B)
+     return true for EQ and false for NE.  */
+  if ((code == EQ_EXPR || code == NE_EXPR)
+      && POINTER_TYPE_P (type)
+      && TREE_CODE (op1) == ADDR_EXPR
+      && TREE_CODE (TREE_OPERAND (op1, 0)) == MEM_REF)
+    {
+      tree mem_ref = TREE_OPERAND (op1, 0);
+      if (TREE_CODE (TREE_OPERAND (mem_ref, 0)) == ADDR_EXPR)
+	{
+	  tree addr_expr = TREE_OPERAND (mem_ref, 0);
+	  if (TREE_CODE (TREE_OPERAND (addr_expr, 0)) == STRING_CST)
+	    {
+	      tree string = TREE_OPERAND (addr_expr, 0);
+
+	      if (TREE_CODE (TREE_OPERAND (mem_ref, 1)) == INTEGER_CST)
+		{
+		  HOST_WIDE_INT len = TREE_STRING_LENGTH (string);
+		  HOST_WIDE_INT offset = tree_to_uhwi (TREE_OPERAND (mem_ref, 1));
+		  if (offset > len)
+		    return code == EQ_EXPR ? boolean_false_node : boolean_true_node;
+		}
+	    }
+	}
+    }
+
   return NULL;
 }
 

Re: [RFC] [PR tree-optimization/92539] Optimize away tests against invalid pointers

[Andrew Pinski]

On Sun, Mar 10, 2024 at 2:09 PM Jeff Law <jlaw@ventanamicro.com> wrote:
>
>
>
> On 3/10/24 3:05 PM, Andrew Pinski wrote:
> > On Sun, Mar 10, 2024 at 2:04 PM Jeff Law <jlaw@ventanamicro.com> wrote:
> >>
> >> Here's a potential approach to fixing PR92539, a P2 -Warray-bounds false
> >> positive triggered by loop unrolling.
> >>
> >> As I speculated a couple years ago, we could eliminate the comparisons
> >> against bogus pointers.  Consider:
> >>
> >>>    <bb 8> [local count: 30530247]:
> >>>    if (last_12 != &MEM <const char> [(void *)"aa" + 3B])
> >>>      goto <bb 9>; [54.59%]
> >>>    else
> >>>      goto <bb 12>; [45.41%]
> >>
> >>
> >> That's a valid comparison as ISO allows us to generate, but not
> >> dereference, a pointer one element past the end of the object.
> >>
> >> But +4B is a bogus pointer.  So given an EQ comparison against that
> >> pointer we could always return false and for NE always return true.
> >>
> >> VRP and DOM seem to be the most natural choices for this kind of
> >> optimization on the surface.  However DOM is actually not viable because
> >> the out-of-bounds pointer warning pass is run at the end of VRP.  So
> >> we've got to take care of this prior to the end of VRP.
> >>
> >>
> >>
> >> I haven't done a bootstrap or regression test with this.  But if it
> >> looks reasonable I can certainly push on it further. I have confirmed it
> >> does eliminate the tests and shuts up the bogus warning.
> >>
> >> The downside is this would also shut up valid warnings if user code did
> >> this kind of test.
> >>
> >> Comments/Suggestions?
> >
> > ENOPATCH
> Yea, realized it as I pushed the send button.  Then t-bird crashed,
> repeatedly.
>
> Attached this time..


One minor comment on it

The comment:
> return true for EQ and false for NE.

Seems to be the opposite for what the code does:
> return code == EQ_EXPR ? boolean_false_node : boolean_true_node;

Thanks,
Andrew


>
> jeff
>

Re: [RFC] [PR tree-optimization/92539] Optimize away tests against invalid pointers

[Richard Biener]

On Sun, Mar 10, 2024 at 10:09 PM Jeff Law <jlaw@ventanamicro.com> wrote:
>
>
>
> On 3/10/24 3:05 PM, Andrew Pinski wrote:
> > On Sun, Mar 10, 2024 at 2:04 PM Jeff Law <jlaw@ventanamicro.com> wrote:
> >>
> >> Here's a potential approach to fixing PR92539, a P2 -Warray-bounds false
> >> positive triggered by loop unrolling.
> >>
> >> As I speculated a couple years ago, we could eliminate the comparisons
> >> against bogus pointers.  Consider:
> >>
> >>>    <bb 8> [local count: 30530247]:
> >>>    if (last_12 != &MEM <const char> [(void *)"aa" + 3B])
> >>>      goto <bb 9>; [54.59%]
> >>>    else
> >>>      goto <bb 12>; [45.41%]
> >>
> >>
> >> That's a valid comparison as ISO allows us to generate, but not
> >> dereference, a pointer one element past the end of the object.
> >>
> >> But +4B is a bogus pointer.  So given an EQ comparison against that
> >> pointer we could always return false and for NE always return true.
> >>
> >> VRP and DOM seem to be the most natural choices for this kind of
> >> optimization on the surface.  However DOM is actually not viable because
> >> the out-of-bounds pointer warning pass is run at the end of VRP.  So
> >> we've got to take care of this prior to the end of VRP.
> >>
> >>
> >>
> >> I haven't done a bootstrap or regression test with this.  But if it
> >> looks reasonable I can certainly push on it further. I have confirmed it
> >> does eliminate the tests and shuts up the bogus warning.
> >>
> >> The downside is this would also shut up valid warnings if user code did
> >> this kind of test.
> >>
> >> Comments/Suggestions?
> >
> > ENOPATCH
> Yea, realized it as I pushed the send button.  Then t-bird crashed,
> repeatedly.
>
> Attached this time..

There's fold-const.cc:address_compare and
tree-ssa-alias.cc:ptrs_compare_unequal,
both eventually used by match.pd that could see this change, the former already
special-cases STRING_CST to some extent.

I'll note that the value we simplify such comparison to is arbitrary.
Doing such
simplification directly (as opposed to only benefit from its
undefinedness indirectly)
always gives me the creeps ;)

IMO we should instead simplify the condition to __builtin_unreachable/trap aka
isolate the path as unreachable.

Richard.

> jeff
>

Re: [RFC] [PR tree-optimization/92539] Optimize away tests against invalid pointers

[Richard Biener]

On Mon, Mar 11, 2024 at 8:46 AM Richard Biener
<richard.guenther@gmail.com> wrote:
>
> On Sun, Mar 10, 2024 at 10:09 PM Jeff Law <jlaw@ventanamicro.com> wrote:
> >
> >
> >
> > On 3/10/24 3:05 PM, Andrew Pinski wrote:
> > > On Sun, Mar 10, 2024 at 2:04 PM Jeff Law <jlaw@ventanamicro.com> wrote:
> > >>
> > >> Here's a potential approach to fixing PR92539, a P2 -Warray-bounds false
> > >> positive triggered by loop unrolling.
> > >>
> > >> As I speculated a couple years ago, we could eliminate the comparisons
> > >> against bogus pointers.  Consider:
> > >>
> > >>>    <bb 8> [local count: 30530247]:
> > >>>    if (last_12 != &MEM <const char> [(void *)"aa" + 3B])
> > >>>      goto <bb 9>; [54.59%]
> > >>>    else
> > >>>      goto <bb 12>; [45.41%]
> > >>
> > >>
> > >> That's a valid comparison as ISO allows us to generate, but not
> > >> dereference, a pointer one element past the end of the object.
> > >>
> > >> But +4B is a bogus pointer.  So given an EQ comparison against that
> > >> pointer we could always return false and for NE always return true.
> > >>
> > >> VRP and DOM seem to be the most natural choices for this kind of
> > >> optimization on the surface.  However DOM is actually not viable because
> > >> the out-of-bounds pointer warning pass is run at the end of VRP.  So
> > >> we've got to take care of this prior to the end of VRP.
> > >>
> > >>
> > >>
> > >> I haven't done a bootstrap or regression test with this.  But if it
> > >> looks reasonable I can certainly push on it further. I have confirmed it
> > >> does eliminate the tests and shuts up the bogus warning.
> > >>
> > >> The downside is this would also shut up valid warnings if user code did
> > >> this kind of test.
> > >>
> > >> Comments/Suggestions?
> > >
> > > ENOPATCH
> > Yea, realized it as I pushed the send button.  Then t-bird crashed,
> > repeatedly.
> >
> > Attached this time..
>
> There's fold-const.cc:address_compare and
> tree-ssa-alias.cc:ptrs_compare_unequal,
> both eventually used by match.pd that could see this change, the former already
> special-cases STRING_CST to some extent.
>
> I'll note that the value we simplify such comparison to is arbitrary.
> Doing such
> simplification directly (as opposed to only benefit from its
> undefinedness indirectly)
> always gives me the creeps ;)
>
> IMO we should instead simplify the condition to __builtin_unreachable/trap aka
> isolate the path as unreachable.

I see for the testcase we get to see the invalid compares in forwprop while
the diagnostic happens in VRP which is way before path isolation.

IMO it's sensible to make forwprop do the path isolation, but this is probably
nothing for stage4.

Scheduling another pass isolation path before array-bound diagnostics might
also make sense (it would be nice to dis-entangle -Warray-bounds from VRP
itself)

Richard.

> Richard.
>
> > jeff
> >

Re: [RFC] [PR tree-optimization/92539] Optimize away tests against invalid pointers

[Jeff Law]

On 3/11/24 1:46 AM, Richard Biener wrote:
> On Sun, Mar 10, 2024 at 10:09 PM Jeff Law <jlaw@ventanamicro.com> wrote:
>>
>>
>>
>> On 3/10/24 3:05 PM, Andrew Pinski wrote:
>>> On Sun, Mar 10, 2024 at 2:04 PM Jeff Law <jlaw@ventanamicro.com> wrote:
>>>>
>>>> Here's a potential approach to fixing PR92539, a P2 -Warray-bounds false
>>>> positive triggered by loop unrolling.
>>>>
>>>> As I speculated a couple years ago, we could eliminate the comparisons
>>>> against bogus pointers.  Consider:
>>>>
>>>>>     <bb 8> [local count: 30530247]:
>>>>>     if (last_12 != &MEM <const char> [(void *)"aa" + 3B])
>>>>>       goto <bb 9>; [54.59%]
>>>>>     else
>>>>>       goto <bb 12>; [45.41%]
>>>>
>>>>
>>>> That's a valid comparison as ISO allows us to generate, but not
>>>> dereference, a pointer one element past the end of the object.
>>>>
>>>> But +4B is a bogus pointer.  So given an EQ comparison against that
>>>> pointer we could always return false and for NE always return true.
>>>>
>>>> VRP and DOM seem to be the most natural choices for this kind of
>>>> optimization on the surface.  However DOM is actually not viable because
>>>> the out-of-bounds pointer warning pass is run at the end of VRP.  So
>>>> we've got to take care of this prior to the end of VRP.
>>>>
>>>>
>>>>
>>>> I haven't done a bootstrap or regression test with this.  But if it
>>>> looks reasonable I can certainly push on it further. I have confirmed it
>>>> does eliminate the tests and shuts up the bogus warning.
>>>>
>>>> The downside is this would also shut up valid warnings if user code did
>>>> this kind of test.
>>>>
>>>> Comments/Suggestions?
>>>
>>> ENOPATCH
>> Yea, realized it as I pushed the send button.  Then t-bird crashed,
>> repeatedly.
>>
>> Attached this time..
> 
> There's fold-const.cc:address_compare and
> tree-ssa-alias.cc:ptrs_compare_unequal,
> both eventually used by match.pd that could see this change, the former already
> special-cases STRING_CST to some extent.
> 
> I'll note that the value we simplify such comparison to is arbitrary.
> Doing such
> simplification directly (as opposed to only benefit from its
> undefinedness indirectly)
> always gives me the creeps ;)
> 
> IMO we should instead simplify the condition to __builtin_unreachable/trap aka
> isolate the path as unreachable.
Path isolation is a better conceptual place, but to do that I think we'd 
need to finish moving the array warnings out of VRP to a later point in 
the pipeline.

That's probably a good thing to do regardless -- even with the almost 
certain fallout.

jeff
> 
> Richard.
> 
>> jeff
>>