Re: [PATCH] Improve DSE to handle stores before __builtin_unreachable ()

Re: [PATCH] Improve DSE to handle stores before __builtin_unreachable ()

[Jeff Law]

On 6/20/23 00:59, Richard Biener via Gcc-patches wrote:
> DSE isn't good at identifying program points that end lifetime
> of variables that are not associated with virtual operands.  But
> at least for those that end basic-blocks we can handle the simple
> case where this ending is in the same basic-block as the definition
> we want to elide.  That should catch quite some common cases already.
> 
> Bootstrapped and tested on x86_64-unknown-linux-gnu.
> 
> As you can see from the testcase I had to adjust this possibly can
> lead to more severe issues when one forgets a return (the C++ frontend
> places builtin_unreachable () there).  I'm still planning to push
> this improvement unless I hear objections.
> 
> Thanks,
> Richard.
> 
> 	* tree-ssa-dse.cc (dse_classify_store): When we found
> 	no defs and the basic-block with the original definition
> 	ends in __builtin_unreachable[_trap] the store is dead.
> 
> 	* gcc.dg/tree-ssa/ssa-dse-47.c: New testcase.
> 	* c-c++-common/asan/pr106558.c: Avoid undefined behavior
> 	due to missing return.
I thought during the introduction of erroneous path isolation that we 
concluded stores, calls and such had observable side effects that must 
be preserved, even when we hit a block that leads to __builtin_unreachable.

Don't get me wrong, I'm all for removing the memory references if it's 
safe to do so.

Jeff

Re: [PATCH] Improve DSE to handle stores before __builtin_unreachable ()

[Richard Biener]

On Tue, 20 Jun 2023, Jeff Law wrote:

> 
> 
> On 6/20/23 00:59, Richard Biener via Gcc-patches wrote:
> > DSE isn't good at identifying program points that end lifetime
> > of variables that are not associated with virtual operands.  But
> > at least for those that end basic-blocks we can handle the simple
> > case where this ending is in the same basic-block as the definition
> > we want to elide.  That should catch quite some common cases already.
> > 
> > Bootstrapped and tested on x86_64-unknown-linux-gnu.
> > 
> > As you can see from the testcase I had to adjust this possibly can
> > lead to more severe issues when one forgets a return (the C++ frontend
> > places builtin_unreachable () there).  I'm still planning to push
> > this improvement unless I hear objections.
> > 
> > Thanks,
> > Richard.
> > 
> >  * tree-ssa-dse.cc (dse_classify_store): When we found
> >  no defs and the basic-block with the original definition
> >  ends in __builtin_unreachable[_trap] the store is dead.
> > 
> >  * gcc.dg/tree-ssa/ssa-dse-47.c: New testcase.
> >  * c-c++-common/asan/pr106558.c: Avoid undefined behavior
> >  due to missing return.
> I thought during the introduction of erroneous path isolation that we
> concluded stores, calls and such had observable side effects that must be
> preserved, even when we hit a block that leads to __builtin_unreachable.

Indeed, I remember we repeatedly hit this in the past.  But 
double-checking I see that we instrument

  if (x)
    *(int *)0 = 0;

as

  <bb 2> [local count: 1073741824]:
  if (x_2(D) != 0)
    goto <bb 3>; [50.00%]
  else
    goto <bb 4>; [50.00%]

  <bb 3> [local count: 536870913]:
  MEM[(int *)0B] ={v} 0;
  __builtin_trap ();

path isolation doesn't seem to use __builtin_unreachable ().  I did
not add __builtin_trap () as possible sink (but I did want to treat
__builtin_unreachable () and __builtin_unreachable_trap () the same
way).  The pass also marks the offending store as volatile.

We do have testsuite coverage that this happens (dump-scanning,
not runtime it seems).

So yes, I think preserving the original trap kind (if there is any)
is important and it still seems to work.  I don't remember whether
we have any test coverage for that though.  I'll also note that
__builtin_trap () has virtual operands (def and use) while
__builtin_unreachable[_trap] () are 'const'.  Honza correctly
says they should probably be novops instead of 'const' preserving
the fact that they have side-effects.

> Don't get me wrong, I'm all for removing the memory references if it's safe to
> do so.

I think it's desirable for assertions.  Since we elide plain
__builtin_unreachable () and fall thru whereever it leads that
shouldn't be an issue.

If I manually add a __builtin_unreachable () to the above case
I see the *(int *)0 = 0; store DSEd.  Maybe we should avoid
removing stores that might trap here?  POSIX wise such a trap
could be a way to jump out of the path leading to unreachable ()
via siglongjmp ...

Thanks,
Richard.

Re: [PATCH] Improve DSE to handle stores before __builtin_unreachable ()

[Jan Hubicka]

> 
> If I manually add a __builtin_unreachable () to the above case
> I see the *(int *)0 = 0; store DSEd.  Maybe we should avoid
> removing stores that might trap here?  POSIX wise such a trap
> could be a way to jump out of the path leading to unreachable ()
> via siglongjmp ...

I am not sure how much POSIX actually promises here.
I don't think we are supposed to keep such undefined behaviours in
original order.  We compile:

int test (int *a, int *b, int c)
{
        int res = *a;
        return res + *b / c;
}

to:

test:
.LFB0:
        .cfi_startproc
        movl    (%rsi), %eax
        movl    %edx, %ecx
        cltd
        idivl   %ecx
        addl    (%rdi), %eax
        ret

So we read *b before *a.  Passing a==NULL, b non-null and c==0 and
using signal sigsev to recover the program before division by 0 will not
work with optimization.

Reaching unreachable is always undefined behaviour so I think we are
safe to reorder it with a load.
Honza


> 
> Thanks,
> Richard.

Re: [PATCH] Improve DSE to handle stores before __builtin_unreachable ()

[Jeff Law]

On 6/21/23 00:41, Richard Biener wrote:
>> I thought during the introduction of erroneous path isolation that we
>> concluded stores, calls and such had observable side effects that must be
>> preserved, even when we hit a block that leads to __builtin_unreachable.
> 
> Indeed, I remember we repeatedly hit this in the past.  But
> double-checking I see that we instrument
> 
>    if (x)
>      *(int *)0 = 0;
> 
> as
> 
>    <bb 2> [local count: 1073741824]:
>    if (x_2(D) != 0)
>      goto <bb 3>; [50.00%]
>    else
>      goto <bb 4>; [50.00%]
> 
>    <bb 3> [local count: 536870913]:
>    MEM[(int *)0B] ={v} 0;
>    __builtin_trap ();
> 
> path isolation doesn't seem to use __builtin_unreachable ().  I did
> not add __builtin_trap () as possible sink (but I did want to treat
> __builtin_unreachable () and __builtin_unreachable_trap () the same
> way).  The pass also marks the offending store as volatile.
Nuts.  I mixed up trap vs unreachable in my own head.  Though I think 
for the purposes of this issue they should be treated the same.  The 
only difference is one actively halts the code, the other silently lets 
it keep going.


> So yes, I think preserving the original trap kind (if there is any)
> is important and it still seems to work.  I don't remember whether
> we have any test coverage for that though.  I'll also note that
> __builtin_trap () has virtual operands (def and use) while
> __builtin_unreachable[_trap] () are 'const'.  Honza correctly
> says they should probably be novops instead of 'const' preserving
> the fact that they have side-effects.
If we have test coverage it's probably minimal -- a few things to 
validate proper behavior around builtin_trap plus whatever regressions 
came up.


> I think it's desirable for assertions.  Since we elide plain
> __builtin_unreachable () and fall thru whereever it leads that
> shouldn't be an issue.
> 
> If I manually add a __builtin_unreachable () to the above case
> I see the *(int *)0 = 0; store DSEd.  Maybe we should avoid
> removing stores that might trap here?  POSIX wise such a trap
> could be a way to jump out of the path leading to unreachable ()
> via siglongjmp ...
Yea, removing the store seemswrong .  As you note, someone could have a 
handler to catch the store, then longjump elsewhere to continue some 
kind of sensible execution.

The erroneous path isolation bits have some code to try and clean up the 
bogus path a bit.  Ideally leaving a single statement with undefined 
beahvior and the trap.  I wonder if there's any code you could re-use 
from that effort.

Essentially a mini pass that cleans up paths post-dominated by a 
builtin_unreachable or builtin_trap.



jeff

Re: [PATCH] Improve DSE to handle stores before __builtin_unreachable ()

[Richard Biener]

On Wed, 21 Jun 2023, Jeff Law wrote:

> 
> 
> On 6/21/23 00:41, Richard Biener wrote:
> >> I thought during the introduction of erroneous path isolation that we
> >> concluded stores, calls and such had observable side effects that must be
> >> preserved, even when we hit a block that leads to __builtin_unreachable.
> > 
> > Indeed, I remember we repeatedly hit this in the past.  But
> > double-checking I see that we instrument
> > 
> >    if (x)
> >      *(int *)0 = 0;
> > 
> > as
> > 
> >    <bb 2> [local count: 1073741824]:
> >    if (x_2(D) != 0)
> >      goto <bb 3>; [50.00%]
> >    else
> >      goto <bb 4>; [50.00%]
> > 
> >    <bb 3> [local count: 536870913]:
> >    MEM[(int *)0B] ={v} 0;
> >    __builtin_trap ();
> > 
> > path isolation doesn't seem to use __builtin_unreachable ().  I did
> > not add __builtin_trap () as possible sink (but I did want to treat
> > __builtin_unreachable () and __builtin_unreachable_trap () the same
> > way).  The pass also marks the offending store as volatile.
> Nuts.  I mixed up trap vs unreachable in my own head.  Though I think for the
> purposes of this issue they should be treated the same.  The only difference
> is one actively halts the code, the other silently lets it keep going.

I think there's a difference in that __builtin_trap () is observable
while __builtin_unreachable () is not and reaching __builtin_unreachable 
() invokes undefined behavior while reaching __builtin_trap () does not.

So the isolation code marking the trapping code volatile should be
enough and the trap () is just there to end the basic block
(and maybe be on the safe side to really trap).

Richard.

> > So yes, I think preserving the original trap kind (if there is any)
> > is important and it still seems to work.  I don't remember whether
> > we have any test coverage for that though.  I'll also note that
> > __builtin_trap () has virtual operands (def and use) while
> > __builtin_unreachable[_trap] () are 'const'.  Honza correctly
> > says they should probably be novops instead of 'const' preserving
> > the fact that they have side-effects.
> If we have test coverage it's probably minimal -- a few things to validate
> proper behavior around builtin_trap plus whatever regressions came up.
> 
> 
> > I think it's desirable for assertions.  Since we elide plain
> > __builtin_unreachable () and fall thru whereever it leads that
> > shouldn't be an issue.
> > 
> > If I manually add a __builtin_unreachable () to the above case
> > I see the *(int *)0 = 0; store DSEd.  Maybe we should avoid
> > removing stores that might trap here?  POSIX wise such a trap
> > could be a way to jump out of the path leading to unreachable ()
> > via siglongjmp ...
> Yea, removing the store seemswrong .  As you note, someone could have a
> handler to catch the store, then longjump elsewhere to continue some kind of
> sensible execution.
> 
> The erroneous path isolation bits have some code to try and clean up the bogus
> path a bit.  Ideally leaving a single statement with undefined beahvior and
> the trap.  I wonder if there's any code you could re-use from that effort.
> 
> Essentially a mini pass that cleans up paths post-dominated by a
> builtin_unreachable or builtin_trap.

Re: [PATCH] Improve DSE to handle stores before __builtin_unreachable ()

[Jeff Law]

On 6/22/23 00:31, Richard Biener wrote:
> I think there's a difference in that __builtin_trap () is observable
> while __builtin_unreachable () is not and reaching __builtin_unreachable
> () invokes undefined behavior while reaching __builtin_trap () does not.
> 
> So the isolation code marking the trapping code volatile should be
> enough and the trap () is just there to end the basic block
> (and maybe be on the safe side to really trap).
Agreed WRT observability -- but that's not really the point of the trap 
and if we wanted we could change that behavior.

The trap is there to halt execution immediately rather than letting it 
keep running.  That was a design decision from a security standpoint. 
If we've detected that we're executing undefined behavior, stop rather 
than potentially letting a malicious actor turn a bug into an exploit.

jeff

Re: [PATCH] Improve DSE to handle stores before __builtin_unreachable ()

[Jan Hubicka]

> 
> 
> On 6/22/23 00:31, Richard Biener wrote:
> > I think there's a difference in that __builtin_trap () is observable
> > while __builtin_unreachable () is not and reaching __builtin_unreachable
> > () invokes undefined behavior while reaching __builtin_trap () does not.
> > 
> > So the isolation code marking the trapping code volatile should be
> > enough and the trap () is just there to end the basic block
> > (and maybe be on the safe side to really trap).
> Agreed WRT observability -- but that's not really the point of the trap and
> if we wanted we could change that behavior.
> 
> The trap is there to halt execution immediately rather than letting it keep
> running.  That was a design decision from a security standpoint. If we've
> detected that we're executing undefined behavior, stop rather than
> potentially letting a malicious actor turn a bug into an exploit.

Also as discussed some time ago, the volatile loads between traps has
effect of turning previously pure/const functions into non-const which
is somewhat sad, so it is still on my todo list to change it this stage1
to something more careful.   We discussed internal functions trap_store
and trap_load which will expand to load/store + trap but will make it
clear that side effect does not count to modref.

I wanted to give it some time if I can come with something better, but
didn't so far.

Honza

Re: [PATCH] Improve DSE to handle stores before __builtin_unreachable ()

[Jeff Law]

On 6/22/23 07:42, Jan Hubicka wrote:
>>
>>
>> On 6/22/23 00:31, Richard Biener wrote:
>>> I think there's a difference in that __builtin_trap () is observable
>>> while __builtin_unreachable () is not and reaching __builtin_unreachable
>>> () invokes undefined behavior while reaching __builtin_trap () does not.
>>>
>>> So the isolation code marking the trapping code volatile should be
>>> enough and the trap () is just there to end the basic block
>>> (and maybe be on the safe side to really trap).
>> Agreed WRT observability -- but that's not really the point of the trap and
>> if we wanted we could change that behavior.
>>
>> The trap is there to halt execution immediately rather than letting it keep
>> running.  That was a design decision from a security standpoint. If we've
>> detected that we're executing undefined behavior, stop rather than
>> potentially letting a malicious actor turn a bug into an exploit.
> 
> Also as discussed some time ago, the volatile loads between traps has
> effect of turning previously pure/const functions into non-const which
> is somewhat sad, so it is still on my todo list to change it this stage1
> to something more careful.   We discussed internal functions trap_store
> and trap_load which will expand to load/store + trap but will make it
> clear that side effect does not count to modref.
It's been a long time since I looked at this code -- isn't it the case 
that we already must have had a load/store and that all we've done is 
change its form (to enable more DCE) and added the volatile marker?

Meaning that it couldn't have been pure/cost before, could it?  Or is it 
the case that you want to not have the erroneous path be the sole reason 
to spoil pure/const detection -- does that happen often in practice?

jeff

Re: [PATCH] Improve DSE to handle stores before __builtin_unreachable ()

[Jan Hubicka]

> > Also as discussed some time ago, the volatile loads between traps has
> > effect of turning previously pure/const functions into non-const which
> > is somewhat sad, so it is still on my todo list to change it this stage1
> > to something more careful.   We discussed internal functions trap_store
> > and trap_load which will expand to load/store + trap but will make it
> > clear that side effect does not count to modref.
> It's been a long time since I looked at this code -- isn't it the case that
> we already must have had a load/store and that all we've done is change its
> form (to enable more DCE) and added the volatile marker?
> 
> Meaning that it couldn't have been pure/cost before, could it?  Or is it the
> case that you want to not have the erroneous path be the sole reason to
> spoil pure/const detection -- does that happen often in practice?

I noticed that while looking into cases during GCC bootstrap where
function analysis went worse after inlning than before, so it happens
in practice.

mod-ref can now analyse independently whether function reads/wrotes
memory (and what memory) and whether function has other side effects or
is non-deterministics.  We can now DSE function call if it has no side
effects and all memory stores are understood and dead.

Problem is that split paths turns undefined behaivour into side effects
and blocks this optimization.

Honza

Re: [PATCH] Improve DSE to handle stores before __builtin_unreachable ()

[Jan Hubicka]

Hi,
playing with testcases for path isolation and const function, I noticed
that we do not seem to even try to isolate out of range array accesses:
int a[3]={0,1,2};
test(int i)
{
       if (i > 3)
         return test2(a[i]);
       return a[i];
}

Here call to test2 is dead, since a[i] will access memory past of the
array.  We produce a warning:

t.c:5:24: warning: array subscript 4 is above array bounds of ‘int[3]’ [-Warray-bounds=]

but we still keep the call:

test:
.LFB0:
        .cfi_startproc
        movslq  %edi, %rax
        movl    a(,%rax,4), %eax
        cmpl    $3, %edi
        jg      .L4
        ret
        .p2align 4,,10
        .p2align 3
.L4:
        movl    %eax, %edi
        xorl    %eax, %eax
        jmp     test2

We eventually move the load before conditional, but at path isolation
time it is still quite obvious the conditional being true invokes
undefined behaviour

int test (int i)
{
  int _1;
  int _2;
  int _6;
  int _8;
  
  <bb 2> [local count: 1073741824]:
  if (i_4(D) > 3)
    goto <bb 3>; [20.24%]
  else
    goto <bb 4>; [79.76%]

  <bb 3> [local count: 217325344]:
  _1 = a[i_4(D)];
  _8 = test2 (_1);
  goto <bb 5>; [100.00%]

  <bb 4> [local count: 856416481]:
  _6 = a[i_4(D)];
  
  <bb 5> [local count: 1073741824]:
  # _2 = PHI <_8(3), _6(4)>
  return _2;
} 

Curiously adjusting the testcase:

const int a[3]={0,1,2};
test(int i)
{
        if (i == 3)
                return test2(a[i]);
        return a[i];
}
no longer has undefined behaviour visible at isolate-paths
int test (int i)
{
  int _1;
  int _5;
  int _7;

  <bb 2> [local count: 1073741824]:
  if (i_3(D) == 3)
    goto <bb 3>; [11.56%]
  else
    goto <bb 4>; [88.44%]

  <bb 3> [local count: 124124552]:
  _7 = test2 (0);
  goto <bb 5>; [100.00%]

  <bb 4> [local count: 949617273]:
  _5 = a[i_3(D)];

  <bb 5> [local count: 1073741824]:
  # _1 = PHI <_7(3), _5(4)>
  return _1;
}
since we fold the load to 0.  It would perhaps help optimizers to keep info on undefined behaviour happening there.

Honza

Re: [PATCH] Improve DSE to handle stores before __builtin_unreachable ()

[Jeff Law]

On 6/26/23 11:21, Jan Hubicka wrote:
> Hi,
> playing with testcases for path isolation and const function, I noticed
> that we do not seem to even try to isolate out of range array accesses:
> int a[3]={0,1,2};
> test(int i)
> {
>         if (i > 3)
>           return test2(a[i]);
>         return a[i];
> }
> 
> Here call to test2 is dead, since a[i] will access memory past of the
> array.  We produce a warning:
> 
> t.c:5:24: warning: array subscript 4 is above array bounds of ‘int[3]’ [-Warray-bounds=]
> 
> but we still keep the call:
My recollection is that we'd planned to have those cases call into the 
isolate paths code, but it may not have moved forward -- I lost track of 
that work when I left Red Hat.  I don't think Martin S. is doing GCC 
work anymore, so we'll probably need to update things ourselves.



> 
> Curiously adjusting the testcase:
> 
> const int a[3]={0,1,2};
> test(int i)
> {
>          if (i == 3)
>                  return test2(a[i]);
>          return a[i];
I would guess that we cprop a[i] into a[3] at which point the oob 
reference is painfully obvious and something cleans that up, likely 
before we even get to isolate-paths.


Jeff

[PATCH] Improve DSE to handle stores before __builtin_unreachable ()

[Richard Biener]

DSE isn't good at identifying program points that end lifetime
of variables that are not associated with virtual operands.  But
at least for those that end basic-blocks we can handle the simple
case where this ending is in the same basic-block as the definition
we want to elide.  That should catch quite some common cases already.

Bootstrapped and tested on x86_64-unknown-linux-gnu.

As you can see from the testcase I had to adjust this possibly can
lead to more severe issues when one forgets a return (the C++ frontend
places builtin_unreachable () there).  I'm still planning to push
this improvement unless I hear objections.

Thanks,
Richard.

	* tree-ssa-dse.cc (dse_classify_store): When we found
	no defs and the basic-block with the original definition
	ends in __builtin_unreachable[_trap] the store is dead.

	* gcc.dg/tree-ssa/ssa-dse-47.c: New testcase.
	* c-c++-common/asan/pr106558.c: Avoid undefined behavior
	due to missing return.
---
 gcc/testsuite/c-c++-common/asan/pr106558.c |  2 +-
 gcc/testsuite/gcc.dg/tree-ssa/ssa-dse-47.c | 17 +++++++++++++++++
 gcc/tree-ssa-dse.cc                        | 21 ++++++++++++++++++++-
 3 files changed, 38 insertions(+), 2 deletions(-)
 create mode 100644 gcc/testsuite/gcc.dg/tree-ssa/ssa-dse-47.c

diff --git a/gcc/testsuite/c-c++-common/asan/pr106558.c b/gcc/testsuite/c-c++-common/asan/pr106558.c
index d82b2dc7a83..c8cefdf09ff 100644
--- a/gcc/testsuite/c-c++-common/asan/pr106558.c
+++ b/gcc/testsuite/c-c++-common/asan/pr106558.c
@@ -8,7 +8,7 @@ int **c = &b;
 int d[1];
 int *e = &d[1];
 
-static int f(int *g) {
+static void f(int *g) {
   *b = e;
   *c = e;
   *b = 2;
diff --git a/gcc/testsuite/gcc.dg/tree-ssa/ssa-dse-47.c b/gcc/testsuite/gcc.dg/tree-ssa/ssa-dse-47.c
new file mode 100644
index 00000000000..659f1d0d415
--- /dev/null
+++ b/gcc/testsuite/gcc.dg/tree-ssa/ssa-dse-47.c
@@ -0,0 +1,17 @@
+/* { dg-do compile } */
+/* { dg-options "-O -fdump-tree-dse1-details" } */
+
+int a;
+int b[3];
+void test()
+{
+  if (a > 0)
+    {
+      b[0] = 0;
+      b[1] = 1;
+      b[2] = 2;
+      __builtin_unreachable ();
+    }
+}
+
+/* { dg-final { scan-tree-dump-times "Deleted dead store" 3 "dse1" } } */
diff --git a/gcc/tree-ssa-dse.cc b/gcc/tree-ssa-dse.cc
index eabe8ba4522..3c7a2e9992d 100644
--- a/gcc/tree-ssa-dse.cc
+++ b/gcc/tree-ssa-dse.cc
@@ -1118,7 +1118,26 @@ dse_classify_store (ao_ref *ref, gimple *stmt,
       if (defs.is_empty ())
 	{
 	  if (ref_may_alias_global_p (ref, false))
-	    return DSE_STORE_LIVE;
+	    {
+	      basic_block def_bb = gimple_bb (SSA_NAME_DEF_STMT (defvar));
+	      /* Assume that BUILT_IN_UNREACHABLE and BUILT_IN_UNREACHABLE_TRAP
+		 do not need to keep (global) memory side-effects live.
+		 We do not have virtual operands on BUILT_IN_UNREACHABLE
+		 but we can do poor mans reachability when the last
+		 definition we want to elide is in the block that ends
+		 in such a call.  */
+	      if (EDGE_COUNT (def_bb->succs) == 0)
+		if (gcall *last = dyn_cast <gcall *> (*gsi_last_bb (def_bb)))
+		  if (gimple_call_builtin_p (last, BUILT_IN_UNREACHABLE)
+		      || gimple_call_builtin_p (last,
+						BUILT_IN_UNREACHABLE_TRAP))
+		    {
+		      if (by_clobber_p)
+			*by_clobber_p = false;
+		      return DSE_STORE_DEAD;
+		    }
+	      return DSE_STORE_LIVE;
+	    }
 
 	  if (by_clobber_p)
 	    *by_clobber_p = false;
-- 
2.35.3