[Bug tree-optimization/104800] New: reodering of potentially trapping operations and volatile stores

[Bug tree-optimization/104800] New: reodering of potentially trapping operations and volatile stores

[muecker at gwdg dot de]

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

            Bug ID: 104800
           Summary: reodering of potentially trapping operations and
                    volatile stores
           Product: gcc
           Version: 11.2.0
            Status: UNCONFIRMED
          Severity: normal
          Priority: P3
         Component: tree-optimization
          Assignee: unassigned at gcc dot gnu.org
          Reporter: muecker at gwdg dot de
  Target Milestone: ---

In the following example, a potentially trapping operation is moved before the
store to the volatile variable.  This can change observable behavior.  Because
division by zero is UB this is a correct optimization in C++ where UB is
allowed to affect previous observable behavior.  For C, I believe that this is
not allowed by the standard. In any case, it annoying (e.g. when debugging of
embedded devices) and dangerous (e.g. in device drivers or when controling
machines) and best avoided.


volatile int x;

int foo(int a, int b, _Bool store_to_x)
{
  if (!store_to_x)
    return a / b;
  x = b;
  return a / b;
}

[Bug tree-optimization/104800] reodering of potentially trapping operations and volatile stores

[muecker at gwdg dot de]

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

--- Comment #1 from Martin Uecker <muecker at gwdg dot de> ---

Godbolt link:
https://godbolt.org/z/111a7a3Y8

[Bug tree-optimization/104800] reodering of potentially trapping operations and volatile stores

[pinskia at gcc dot gnu.org]

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

--- Comment #2 from Andrew Pinski <pinskia at gcc dot gnu.org> ---
https://gcc.gnu.org/pipermail/gcc/2022-January/238038.html

[Bug middle-end/104800] reodering of potentially trapping operations and volatile stores

[paulmckrcu at gmail dot com]

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

Paul McKenney <paulmckrcu at gmail dot com> changed:

           What    |Removed                     |Added
----------------------------------------------------------------------------
                 CC|                            |paulmckrcu at gmail dot com

--- Comment #3 from Paul McKenney <paulmckrcu at gmail dot com> ---
Expanding on Martin's description...

The volatile write's device semantics are unknown to the compiler.  Those
semantics can include generating a trap.  This trap need not return, for
example, it could resume execution in a different place via
setjump()/longjump().  The overall design (including the
unknown-to-the-compiler device semantics) might guarantee that when b is equal
to zero, execution will resume somewhere else, that is, the trap handler is
guaranteed not to return in that case.

And this is one reason why possibly trapping operations must not be moved
across volatile accesses.  Doing so breaks device drivers.

[Bug middle-end/104800] reodering of potentially trapping operations and volatile stores

[muecker at gwdg dot de]

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

--- Comment #4 from Martin Uecker <muecker at gwdg dot de> ---

Patch (by Martin Sebor)

diff --git a/gcc/tree-ssa-pre.c b/gcc/tree-ssa-pre.c
index ab24fa98a1f..8f437791d94 100644
--- a/gcc/tree-ssa-pre.c
+++ b/gcc/tree-ssa-pre.c
@@ -3971,6 +3971,13 @@ compute_avail (function *fun)
              set_bb_may_notreturn = false;
            }

+         if (is_gimple_assign (stmt))
+           {
+             tree lhs = gimple_assign_lhs (stmt);
+             if (TREE_THIS_VOLATILE (lhs))
+               set_bb_may_notreturn = true;
+           }
+
          /* Cache whether the basic-block has any non-visible side-effect
             or control flow.
             If this isn't a call or it is the last stmt in the

[Bug middle-end/104800] reodering of potentially trapping operations and volatile stores

[muecker at gwdg dot de]

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

--- Comment #5 from Martin Uecker <muecker at gwdg dot de> ---

Different context, but also relevant:

https://gcc.gnu.org/pipermail/gcc-patches/2022-February/590757.html


"The problem is there may be observable side effects on the *0 path 
between the test and the actual *0 -- including calls to nonreturning 
functions, setjmp/longjmp, things that could trap, etc.  This case is 
similar.  We can't back-propagate the non-null status through any 
statements with observable side effects."

[Bug middle-end/104800] reodering of potentially trapping operations and volatile stores

[rguenth at gcc dot gnu.org]

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

--- Comment #6 from Richard Biener <rguenth at gcc dot gnu.org> ---
Generally GCCs middle-end considers volatile stores (or loads) to not have any
side-effects that are not visible in the IL.  That includes (synchronous)
raise of signals (and thus effects on control flow), effects on other
(non-volatile) memory, etc.  If a volatile access has to be considered having
an effect on control flow then the standard should explicitely mention that,
I don't think it does that at the moment, it merely says those statements
invoke "changes in the state of the execution environment"

So volatile "issues" like this are no different from issues that arise
with respect to observability when you consider asynchronous events and
the effect of re-ordering of statements.  In fact C17 especially notes
that objects that are not volatile sig_atomic_t have unspecified value
on such events, so that IMHO also covers generating a trap from a volatile
access.

Volatile accesses are deemed observable but we do not re-order those, this
bug is about re-ordering unrelated stmts with respect to such accesses.

I don't think the standard requires us to fix this reported behavior.

A mitigation in the middle-end requires volatile accesses to behave as
possibly altering control flow.  That's iffy if they continue to be
represented as simple assign statements, the closest would be to always
mark them as possibly trapping (something we cannot do right now).

The PRE "fix" is just covering up a single place in the compiler that fails
to consider volatile accesses as altering control flow.

[Bug middle-end/104800] reodering of potentially trapping operations and volatile stores

[paulmckrcu at gmail dot com]

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

--- Comment #7 from Paul McKenney <paulmckrcu at gmail dot com> ---
(In reply to Richard Biener from comment #6)
> Generally GCCs middle-end considers volatile stores (or loads) to not have
> any side-effects that are not visible in the IL.  That includes (synchronous)
> raise of signals (and thus effects on control flow), effects on other
> (non-volatile) memory, etc.  If a volatile access has to be considered having
> an effect on control flow then the standard should explicitely mention that,
> I don't think it does that at the moment, it merely says those statements
> invoke "changes in the state of the execution environment"
> 
> So volatile "issues" like this are no different from issues that arise
> with respect to observability when you consider asynchronous events and
> the effect of re-ordering of statements.  In fact C17 especially notes
> that objects that are not volatile sig_atomic_t have unspecified value
> on such events, so that IMHO also covers generating a trap from a volatile
> access.
> 
> Volatile accesses are deemed observable but we do not re-order those, this
> bug is about re-ordering unrelated stmts with respect to such accesses.
> 
> I don't think the standard requires us to fix this reported behavior.
> 
> A mitigation in the middle-end requires volatile accesses to behave as
> possibly altering control flow.  That's iffy if they continue to be
> represented as simple assign statements, the closest would be to always
> mark them as possibly trapping (something we cannot do right now).
> 
> The PRE "fix" is just covering up a single place in the compiler that fails
> to consider volatile accesses as altering control flow.

Understood that normal accesses can be reordered with volatile accesses.  Cases
where this is a problem can prevent it, for example, using an asm with the
"memory" clobber.

The concern here is not the memory access, but the potential for trapping,
which in this case is the potential division by zero.

[Bug middle-end/104800] reodering of potentially trapping operations and volatile stores

[muecker at gwdg dot de]

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

--- Comment #8 from Martin Uecker <muecker at gwdg dot de> ---

The standard specifies in 5.1.2.3p6 that

"— Volatile accesses to objects are evaluated strictly
according to the rules of the abstract machine."

and

"This is the observable behavior of the program."


If a trap is moved before a volatile access so that the access never happens,
than this changes the observable behavior because the volatile access was then
not evaluated strictly according to the abstract machine.

Some people argue that this is OK because the trap is undefined behavior, but I
do not see how this follows from the C standard. It defines undefined behavior
as 

"behavior, upon use of a nonportable or erroneous program construct
or of erroneous data, for which this document imposes no requirements"

This states that there are no requirements on what undefined operation can do.
But I do not see how this allows changing other previous defined behavior
mandated by the standard.  Now, we could make it clear in the C standard that
UB invalidates the complete program (as in C++), but to me it is obvious that
this is dangerous and it increasingly becomes clear that this also causes other
problems.*) It would rather have some more restricted notion of UB and the
volatile cases in GCC fixed. 

*) For example, it is problematic if UB is allowed to affect previous atomic
operations.

[Bug middle-end/104800] reodering of potentially trapping operations and volatile stores

[rguenth at gcc dot gnu.org]

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

--- Comment #9 from Richard Biener <rguenth at gcc dot gnu.org> ---
(In reply to Martin Uecker from comment #8)
> The standard specifies in 5.1.2.3p6 that
> 
> "— Volatile accesses to objects are evaluated strictly
> according to the rules of the abstract machine."
> 
> and
> 
> "This is the observable behavior of the program."
> 
> 
> If a trap is moved before a volatile access so that the access never
> happens, than this changes the observable behavior because the volatile
> access was then not evaluated strictly according to the abstract machine.

Well, the volatile access _was_ evaluated strictly according to the abstract
machine.  Can't your argument be stretched in a way that for

 global = 2;
 *volatile = 1;

your reasoning says that since the volatile has to be evaluated strictly
according to the abstract machine that the full abstract machine status
has to be reflected at the point of the volatile and thus the write of
the global (non-volatile) memory has to be observable at that point
and so we may not move accesses to global memory across (earlier or later)
volatile accesses?

IMHO the case with the division is similar, you just introduce the extra
twist of a trap.

The two volatile accesses in your example are still evaluated according
to the abstract machine, just all non-volatile (and non-I/O) statements
are not necessarily.

[Bug middle-end/104800] reodering of potentially trapping operations and volatile stores

[rguenth at gcc dot gnu.org]

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

--- Comment #10 from Richard Biener <rguenth at gcc dot gnu.org> ---
Btw, with -ftrapv it would mean we cannot re-order any signed arithmetic with
respect to volatile accesses unless we can prove it does not invoke (undefined,
but -ftrapv makes it implementation defined) signed overflow.

[Bug middle-end/104800] reodering of potentially trapping operations and volatile stores

[muecker at gwdg dot de]

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

--- Comment #11 from Martin Uecker <muecker at gwdg dot de> ---
(In reply to Richard Biener from comment #9)
> (In reply to Martin Uecker from comment #8)
> > The standard specifies in 5.1.2.3p6 that
> > 
> > "— Volatile accesses to objects are evaluated strictly
> > according to the rules of the abstract machine."
> > 
> > and
> > 
> > "This is the observable behavior of the program."
> > 
> > 
> > If a trap is moved before a volatile access so that the access never
> > happens, than this changes the observable behavior because the volatile
> > access was then not evaluated strictly according to the abstract machine.
> 
> Well, the volatile access _was_ evaluated strictly according to the abstract
> machine. 

Not if there is a trap.

> Can't your argument be stretched in a way that for
> 
>  global = 2;
>  *volatile = 1;
> 
> your reasoning says that since the volatile has to be evaluated strictly
> according to the abstract machine that the full abstract machine status
> has to be reflected at the point of the volatile and thus the write of
> the global (non-volatile) memory has to be observable at that point
> and so we may not move accesses to global memory across (earlier or later)
> volatile accesses?

The state of the global variables is not directly observable.

> IMHO the case with the division is similar, you just introduce the extra
> twist of a trap.

The point is that the trap prevents the volatile store to happen.

> The two volatile accesses in your example are still evaluated according
> to the abstract machine, just all non-volatile (and non-I/O) statements
> are not necessarily.

The problem is that the volatile store might not be evaluated if there is a
trap.

[Bug middle-end/104800] reodering of potentially trapping operations and volatile stores

[muecker at gwdg dot de]

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

--- Comment #12 from Martin Uecker <muecker at gwdg dot de> ---
(In reply to Richard Biener from comment #10)
> Btw, with -ftrapv it would mean we cannot re-order any signed arithmetic
> with respect to volatile accesses unless we can prove it does not invoke
> (undefined,
> but -ftrapv makes it implementation defined) signed overflow.


Yes, and I think this would be desirable too. For example, if you safetly turn
off a machine with a volatile store, you want a later logic error in unrelated
code not to be able to prevent this.

[Bug middle-end/104800] reodering of potentially trapping operations and volatile stores

[rguenther at suse dot de]

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

--- Comment #13 from rguenther at suse dot de <rguenther at suse dot de> ---
On Wed, 9 Mar 2022, muecker at gwdg dot de wrote:

> https://gcc.gnu.org/bugzilla/show_bug.cgi?id=104800
> 
> --- Comment #11 from Martin Uecker <muecker at gwdg dot de> ---
> (In reply to Richard Biener from comment #9)
> > (In reply to Martin Uecker from comment #8)
> > > The standard specifies in 5.1.2.3p6 that
> > > 
> > > "— Volatile accesses to objects are evaluated strictly
> > > according to the rules of the abstract machine."
> > > 
> > > and
> > > 
> > > "This is the observable behavior of the program."
> > > 
> > > 
> > > If a trap is moved before a volatile access so that the access never
> > > happens, than this changes the observable behavior because the volatile
> > > access was then not evaluated strictly according to the abstract machine.
> > 
> > Well, the volatile access _was_ evaluated strictly according to the abstract
> > machine. 
> 
> Not if there is a trap.
> 
> > Can't your argument be stretched in a way that for
> > 
> >  global = 2;
> >  *volatile = 1;
> > 
> > your reasoning says that since the volatile has to be evaluated strictly
> > according to the abstract machine that the full abstract machine status
> > has to be reflected at the point of the volatile and thus the write of
> > the global (non-volatile) memory has to be observable at that point
> > and so we may not move accesses to global memory across (earlier or later)
> > volatile accesses?
> 
> The state of the global variables is not directly observable.
> 
> > IMHO the case with the division is similar, you just introduce the extra
> > twist of a trap.
> 
> The point is that the trap prevents the volatile store to happen.
> 
> > The two volatile accesses in your example are still evaluated according
> > to the abstract machine, just all non-volatile (and non-I/O) statements
> > are not necessarily.
> 
> The problem is that the volatile store might not be evaluated if there is a
> trap.

So?  The abstract machine evaluation simply does not have reached the
second volatile store then.  All indirect memory accesses might trap
(again undefined behavior), direct stores might trap if they are
mapped to readonly memory (again undefined behavior).  General
FP operations might trap (sNaNs), other general operations might trap
(certain CPU insns trap on overflow, some CPUs have NaTs that trap, etc.).

I'm raising these issues because while the case at hand (division
by zero trap and volatiles) might be an obvious candidate to "fix"
just for the sake of QOI the question is where to stop?

Take

volatile flag;
void foo (int *p)
{
  if (p == NULL)
    {
      flag = 1;
      *p = 1;
    }
}

it's an artifact that we currently fail to eliminate the branch
because it leads to UB *p = 1, and I think it would be valid to
eliminate it.  Would that be in violation of your desired
reading of the standard since it elides the volatile store
(the UB happens later)?

[Bug middle-end/104800] reodering of potentially trapping operations and volatile stores

[rguenther at suse dot de]

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

--- Comment #14 from rguenther at suse dot de <rguenther at suse dot de> ---
On Wed, 9 Mar 2022, muecker at gwdg dot de wrote:

> https://gcc.gnu.org/bugzilla/show_bug.cgi?id=104800
> 
> --- Comment #12 from Martin Uecker <muecker at gwdg dot de> ---
> (In reply to Richard Biener from comment #10)
> > Btw, with -ftrapv it would mean we cannot re-order any signed arithmetic
> > with respect to volatile accesses unless we can prove it does not invoke
> > (undefined,
> > but -ftrapv makes it implementation defined) signed overflow.
> 
> 
> Yes, and I think this would be desirable too. For example, if you safetly turn
> off a machine with a volatile store, you want a later logic error in unrelated
> code not to be able to prevent this.

As said, volatile accesses are not considered to alter control flow and
thus "turning off the machine" is not something GCC "allows", the
program has to resume after the volatile store.

For example volatile accesses are also not considered to abnormally
return.  Consider them raising an interrupt, that triggering a signal
and using siglongjmp - GCC is not prepared for that to happen
(so it's not "allowed").

The following might be eventually a catch-all fix (but too aggressive
as noted in the comment).  With it GCC should consider (on the
GIMPLE / GENERIC level ...) all volatile accesses possibly trapping
and thus altering control flow.

diff --git a/gcc/tree-eh.cc b/gcc/tree-eh.cc
index c37a5845343..21179081be9 100644
--- a/gcc/tree-eh.cc
+++ b/gcc/tree-eh.cc
@@ -2662,8 +2662,15 @@ tree_could_trap_p (tree expr)
     return false;

   code = TREE_CODE (expr);
-  t = TREE_TYPE (expr);
+  /* Volatile accesses need to be considered as altering control flow
+     if they are for example device I/O.
+     ???  We can probably exclude automatic variables and accesses that
+     are known to not map to device memory here.  */
+  if (TREE_CODE_CLASS (code) == tcc_reference
+      && TREE_THIS_VOLATILE (expr))
+    return true;

+  t = TREE_TYPE (expr);
   if (t)
     {
       if (COMPARISON_CLASS_P (expr))

[Bug middle-end/104800] reodering of potentially trapping operations and volatile stores

[muecker at gwdg dot de]

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

--- Comment #15 from Martin Uecker <muecker at gwdg dot de> ---
(In reply to rguenther@suse.de from comment #13)
> On Wed, 9 Mar 2022, muecker at gwdg dot de wrote:
> 
> > https://gcc.gnu.org/bugzilla/show_bug.cgi?id=104800
> > 
> > --- Comment #11 from Martin Uecker <muecker at gwdg dot de> ---
> > (In reply to Richard Biener from comment #9)
> > > (In reply to Martin Uecker from comment #8)
> > > > The standard specifies in 5.1.2.3p6 that
> > > > 
> > > > "— Volatile accesses to objects are evaluated strictly
> > > > according to the rules of the abstract machine."
> > > > 
> > > > and
> > > > 
> > > > "This is the observable behavior of the program."
> > > > 
> > > > 
> > > > If a trap is moved before a volatile access so that the access never
> > > > happens, than this changes the observable behavior because the volatile
> > > > access was then not evaluated strictly according to the abstract machine.
> > > 
> > > Well, the volatile access _was_ evaluated strictly according to the abstract
> > > machine. 
> > 
> > Not if there is a trap.
> > 
> > > Can't your argument be stretched in a way that for
> > > 
> > >  global = 2;
> > >  *volatile = 1;
> > > 
> > > your reasoning says that since the volatile has to be evaluated strictly
> > > according to the abstract machine that the full abstract machine status
> > > has to be reflected at the point of the volatile and thus the write of
> > > the global (non-volatile) memory has to be observable at that point
> > > and so we may not move accesses to global memory across (earlier or later)
> > > volatile accesses?
> > 
> > The state of the global variables is not directly observable.
> > 
> > > IMHO the case with the division is similar, you just introduce the extra
> > > twist of a trap.
> > 
> > The point is that the trap prevents the volatile store to happen.
> > 
> > > The two volatile accesses in your example are still evaluated according
> > > to the abstract machine, just all non-volatile (and non-I/O) statements
> > > are not necessarily.
> > 
> > The problem is that the volatile store might not be evaluated if there is a
> > trap.
> 
> So?  The abstract machine evaluation simply does not have reached the
> second volatile store then.  

There is only one volatile store. If store_to_x is false, the
volatile store is reached followed by the division. So according
to the abstract machine evaluation the store is executed in
this case. If the compiler reorders the instructions it might not.

> All indirect memory accesses might trap
> (again undefined behavior), direct stores might trap if they are
> mapped to readonly memory (again undefined behavior).  General
> FP operations might trap (sNaNs), other general operations might trap
> (certain CPU insns trap on overflow, some CPUs have NaTs that trap, etc.).

Yes, if those may trap, then reordering volatile stores
with those instructions is dangerous. 

> I'm raising these issues because while the case at hand (division
> by zero trap and volatiles) might be an obvious candidate to "fix"
> just for the sake of QOI the question is where to stop?

I would stop once behaviour is fully correct assuming a sensible
interpretation of the C standard.  If the C standard does not make
sense, we should change the standard or introduce explicit
non-standard compilation modes.

> Take
> 
> volatile flag;
> void foo (int *p)
> {
>   if (p == NULL)
>     {
>       flag = 1;
>       *p = 1;
>     }
> }
> 
> it's an artifact that we currently fail to eliminate the branch
> because it leads to UB *p = 1, and I think it would be valid to
> eliminate it.  Would that be in violation of your desired
> reading of the standard since it elides the volatile store
> (the UB happens later)?

Yes. This is my "desired interpretation" because it 1) matches
the wording and 2) gives useful for guarantees about the
behaviour of the program even in case of errors (which we all
know exist). 

I also think that in the presence of volatile stores
reliable and correct behaviour of a program is more important
than optimization,

The quote from Jeff in comment 5 would also imply that this is
not currently considered a valid optimization in CC.

[Bug middle-end/104800] reodering of potentially trapping operations and volatile stores

[muecker at gwdg dot de]

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

--- Comment #16 from Martin Uecker <muecker at gwdg dot de> ---
(In reply to rguenther@suse.de from comment #14)
> On Wed, 9 Mar 2022, muecker at gwdg dot de wrote:
> 
> > https://gcc.gnu.org/bugzilla/show_bug.cgi?id=104800
> > 
> > --- Comment #12 from Martin Uecker <muecker at gwdg dot de> ---
> > (In reply to Richard Biener from comment #10)
> > > Btw, with -ftrapv it would mean we cannot re-order any signed arithmetic
> > > with respect to volatile accesses unless we can prove it does not invoke
> > > (undefined,
> > > but -ftrapv makes it implementation defined) signed overflow.
> > 
> > 
> > Yes, and I think this would be desirable too. For example, if you safetly turn
> > off a machine with a volatile store, you want a later logic error in unrelated
> > code not to be able to prevent this.
> 
> As said, volatile accesses are not considered to alter control flow and
> thus "turning off the machine" is not something GCC "allows", the
> program has to resume after the volatile store.

Sorry, I was not clear. I agree that volatile accesses are not
meant to alter control flow according to the C standard (although
the assumption that they may terminate the program may be one
possible way to express their semantics for optimization). 

With "turning off a machine" I meant an external device 
controlled by a C program. For sake of argument: moving
the control rods into a nuclear reactor. 

> For example volatile accesses are also not considered to abnormally
> return.  Consider them raising an interrupt, that triggering a signal
> and using siglongjmp - GCC is not prepared for that to happen
> (so it's not "allowed").
> 
> The following might be eventually a catch-all fix (but too aggressive
> as noted in the comment).  With it GCC should consider (on the
> GIMPLE / GENERIC level ...) all volatile accesses possibly trapping
> and thus altering control flow.
> 
> diff --git a/gcc/tree-eh.cc b/gcc/tree-eh.cc
> index c37a5845343..21179081be9 100644
> --- a/gcc/tree-eh.cc
> +++ b/gcc/tree-eh.cc
> @@ -2662,8 +2662,15 @@ tree_could_trap_p (tree expr)
>      return false;
>  
>    code = TREE_CODE (expr);
> -  t = TREE_TYPE (expr);
> +  /* Volatile accesses need to be considered as altering control flow
> +     if they are for example device I/O.
> +     ???  We can probably exclude automatic variables and accesses that
> +     are known to not map to device memory here.  */
> +  if (TREE_CODE_CLASS (code) == tcc_reference
> +      && TREE_THIS_VOLATILE (expr))
> +    return true;
>  
> +  t = TREE_TYPE (expr);
>    if (t)
>      {
>        if (COMPARISON_CLASS_P (expr))