reordering of trapping operations and volatile

reordering of trapping operations and volatile

[Martin Uecker]

Hi Richard,

I have a question regarding reodering of volatile
accesses and trapping operations. My initial
assumption (and  hope) was that compilers take
care to avoid creating traps that are incorrectly
ordered relative to observable behavior.

I had trouble finding examples, and my cursory
glace at the code seemed to confirm that GCC
carefully avoids this.  But then someone showed
me this example, where this can happen in GCC:


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;
}


https://godbolt.org/z/vq3r8vjxr

In this example a division is hoisted 
before the volatile store. (the division
by zero which could trap is UB, of course).

As Martin Sebor pointed out this is done
as part of redundancy elimination 
in tree-ssa-pre.c and that this might
simply be an oversight (and could then be
fixed with a small change).

Could you clarify whether such reordering
is intentional and could be exploited in
general also in other optimizations or
confirm that this is an oversight that
affects only this specific case?

If this is intentional, are there examples
where this is important for optimization?


Martin

Re: reordering of trapping operations and volatile

[Richard Biener]

On January 8, 2022 9:32:24 AM GMT+01:00, Martin Uecker <ma.uecker@gmail.com> wrote:
>
>Hi Richard,
>
>I have a question regarding reodering of volatile
>accesses and trapping operations. My initial
>assumption (and  hope) was that compilers take
>care to avoid creating traps that are incorrectly
>ordered relative to observable behavior.
>
>I had trouble finding examples, and my cursory
>glace at the code seemed to confirm that GCC
>carefully avoids this.  But then someone showed
>me this example, where this can happen in GCC:
>
>
>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;
>}
>
>
>https://godbolt.org/z/vq3r8vjxr
>
>In this example a division is hoisted 
>before the volatile store. (the division
>by zero which could trap is UB, of course).
>
>As Martin Sebor pointed out this is done
>as part of redundancy elimination 
>in tree-ssa-pre.c and that this might
>simply be an oversight (and could then be
>fixed with a small change).
>
>Could you clarify whether such reordering
>is intentional and could be exploited in
>general also in other optimizations or
>confirm that this is an oversight that
>affects only this specific case?
>
>If this is intentional, are there examples
>where this is important for optimization?


In general there is no data flow information that prevents traps from being reordered with respect to volatile accesses. The specific case could be easily mitigated in PRE. Another case would be

A = c / d;
X = 1;
If (use_a)
  Bar (a);

Where we'd sink a across x into the guarded Bb I suspect. 

(sorry for the odd formatting, writing this on a mobile device). 

Richard. 
>
>Martin
>
>
>
>
>
>

Re: reordering of trapping operations and volatile

[Martin Uecker]

Am Samstag, den 08.01.2022, 13:41 +0100 schrieb Richard Biener:
> On January 8, 2022 9:32:24 AM GMT+01:00, Martin Uecker <ma.uecker@gmail.com> wrote:
> > Hi Richard,

thank you for your quick response!

> > I have a question regarding reodering of volatile
> > accesses and trapping operations. My initial
> > assumption (and  hope) was that compilers take
> > care to avoid creating traps that are incorrectly
> > ordered relative to observable behavior.
> > 
> > I had trouble finding examples, and my cursory
> > glace at the code seemed to confirm that GCC
> > carefully avoids this.  But then someone showed
> > me this example, where this can happen in GCC:
> > 
> > 
> > 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;
> > }
> > 
> > 
> > https://godbolt.org/z/vq3r8vjxr
> > 
> > In this example a division is hoisted 
> > before the volatile store. (the division
> > by zero which could trap is UB, of course).
> > 
> > As Martin Sebor pointed out this is done
> > as part of redundancy elimination 
> > in tree-ssa-pre.c and that this might
> > simply be an oversight (and could then be
> > fixed with a small change).
> > 
> > Could you clarify whether such reordering
> > is intentional and could be exploited in
> > general also in other optimizations or
> > confirm that this is an oversight that
> > affects only this specific case?
> > 
> > If this is intentional, are there examples
> > where this is important for optimization?
> 
> In general there is no data flow information that
> prevents traps from being reordered with respect
> to volatile accesses. 

Yes, although I think potentially trapping ops
are not moved before calls (as this would be
incorrect).  So do you think it would be feasable
to prevent this for volatile too?

> The specific case could be
> easily mitigated in PRE. Another case would be
> 
> A = c / d;
> X = 1;
> If (use_a)
>   Bar (a);
> 
> Where we'd sink a across x into the guarded Bb I suspect. 

Yes. Related example:

https://godbolt.org/z/5WGhadre3

volatile int x;
void bar(int a);

void foo(int c, int d)
{
  int a = c / d;
  x = 1;
  if (d)
    bar(a);
}

foo:
        mov     DWORD PTR x[rip], 1
        test    esi, esi
        jne     .L4
        ret
.L4:
        mov     eax, edi
        cdq
        idiv    esi
        mov     edi, eax
        jmp     bar


It would be nice to prevent this too, although
I am less concerned about this direction, as
the UB has already happened so there is not
much we could guarantee about this anyway.

In the other case, it could affect correct
code before the trap. 

Martin


> (sorry for the odd formatting, writing this on a mobile device). 
> 
> Richard. 
> > Martin
> > 
> > 
> > 
> > 
> > 
> > 

Re: reordering of trapping operations and volatile

[Marc Glisse]

On Sat, 8 Jan 2022, Martin Uecker via Gcc wrote:

> Am Samstag, den 08.01.2022, 13:41 +0100 schrieb Richard Biener:
>> On January 8, 2022 9:32:24 AM GMT+01:00, Martin Uecker <ma.uecker@gmail.com> wrote:
>>> Hi Richard,
>
> thank you for your quick response!
>
>>> I have a question regarding reodering of volatile
>>> accesses and trapping operations. My initial
>>> assumption (and  hope) was that compilers take
>>> care to avoid creating traps that are incorrectly
>>> ordered relative to observable behavior.
>>>
>>> I had trouble finding examples, and my cursory
>>> glace at the code seemed to confirm that GCC
>>> carefully avoids this.  But then someone showed
>>> me this example, where this can happen in GCC:
>>>
>>>
>>> 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;
>>> }
>>>
>>>
>>> https://godbolt.org/z/vq3r8vjxr
>>>
>>> In this example a division is hoisted
>>> before the volatile store. (the division
>>> by zero which could trap is UB, of course).
>>>
>>> As Martin Sebor pointed out this is done
>>> as part of redundancy elimination
>>> in tree-ssa-pre.c and that this might
>>> simply be an oversight (and could then be
>>> fixed with a small change).
>>>
>>> Could you clarify whether such reordering
>>> is intentional and could be exploited in
>>> general also in other optimizations or
>>> confirm that this is an oversight that
>>> affects only this specific case?
>>>
>>> If this is intentional, are there examples
>>> where this is important for optimization?
>>
>> In general there is no data flow information that
>> prevents traps from being reordered with respect
>> to volatile accesses.
>
> Yes, although I think potentially trapping ops
> are not moved before calls (as this would be
> incorrect).  So do you think it would be feasable
> to prevent this for volatile too?
>
>> The specific case could be
>> easily mitigated in PRE. Another case would be
>>
>> A = c / d;
>> X = 1;
>> If (use_a)
>>   Bar (a);
>>
>> Where we'd sink a across x into the guarded Bb I suspect.
>
> Yes. Related example:
>
> https://godbolt.org/z/5WGhadre3
>
> volatile int x;
> void bar(int a);
>
> void foo(int c, int d)
> {
>  int a = c / d;
>  x = 1;
>  if (d)
>    bar(a);
> }
>
> foo:
>        mov     DWORD PTR x[rip], 1
>        test    esi, esi
>        jne     .L4
>        ret
> .L4:
>        mov     eax, edi
>        cdq
>        idiv    esi
>        mov     edi, eax
>        jmp     bar
>
>
> It would be nice to prevent this too, although
> I am less concerned about this direction, as
> the UB has already happened so there is not
> much we could guarantee about this anyway.
>
> In the other case, it could affect correct
> code before the trap.

-fnon-call-exceptions helps with the first testcase but not with the 
second one. I don't know if that's by accident, but the flag seems 
possibly relevant.

-- 
Marc Glisse

Re: reordering of trapping operations and volatile

[Eric Botcazou]

> Yes, although I think potentially trapping ops
> are not moved before calls (as this would be
> incorrect).  So do you think it would be feasable
> to prevent this for volatile too?

Feasible probably, but why would this be desirable in C?  It's not Java!

-- 
Eric Botcazou

Re: reordering of trapping operations and volatile

[David Brown]

On 08/01/2022 09:32, Martin Uecker via Gcc wrote:
> 
> Hi Richard,
> 
> I have a question regarding reodering of volatile
> accesses and trapping operations. My initial
> assumption (and  hope) was that compilers take
> care to avoid creating traps that are incorrectly
> ordered relative to observable behavior.
> 
> I had trouble finding examples, and my cursory
> glace at the code seemed to confirm that GCC
> carefully avoids this.  But then someone showed
> me this example, where this can happen in GCC:
> 
> 
> 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;
> }
> 
> 
> https://godbolt.org/z/vq3r8vjxr
> 
> In this example a division is hoisted 
> before the volatile store. (the division
> by zero which could trap is UB, of course).
> 

Doesn't this depend on whether the trap is considered "observable
behaviour", or "undefined behaviour" ?

If (on the given target cpu and OS, and with any relevant compiler
flags) dividing by zero is guaranteed to give a trap with specific known
behaviour, then it is observable behaviour and thus should be ordered
carefully with respect to the volatile accesses.

On the other hand, if division by 0 is considered undefined behaviour
(the C and C++ standards explicitly mark it as undefined, but a compiler
can of course define its behaviour) then the compiler can assume it does
not happen, or you don't care about the result of the program if it
happens.  Undefined behaviour can be freely re-ordered around volatile
accesses, as far as I understand it - though that can come as a surprise
to some people.


I don't know which of these views gcc takes - I think both are valid.
But it might be worth noting in the reference manual.

David



> As Martin Sebor pointed out this is done
> as part of redundancy elimination 
> in tree-ssa-pre.c and that this might
> simply be an oversight (and could then be
> fixed with a small change).
> 
> Could you clarify whether such reordering
> is intentional and could be exploited in
> general also in other optimizations or
> confirm that this is an oversight that
> affects only this specific case?
> 
> If this is intentional, are there examples
> where this is important for optimization?
> 
> 
> Martin
> 
> 
> 
> 
> 
> 
> 

Re: reordering of trapping operations and volatile

[Martin Uecker]

Am Samstag, den 08.01.2022, 15:41 +0100 schrieb Eric Botcazou:
> > Yes, although I think potentially trapping ops
> > are not moved before calls (as this would be
> > incorrect).  So do you think it would be feasable
> > to prevent this for volatile too?
> 
> Feasible probably, but why would this be desirable in C?  It's not Java!

It would allow us to still give at least some guarantees about the
observable behavior of programs that later in their execution
encounter UB (e.g. that an transaction with an external
device is correctly completed).  Considering the fact that it
is virtually impossible to prove that any realistic C program
is completely free of UB, this is would be very useful.

As another example, there was recently the a proposal about
adding a safe memory erasure function to the standard lib.
It was pointed out that volatile stores would not be enough
to be sure that the compiler safely erased some sensitive
information, because an optimization based on later UB in 
the program could undo this.  

There is now also a proposal for C++ to introduce std::observable,
which would require similar ordering constraints.  But this would
require the programmer to annotate the program correctly.
Most C programmers would assume that volatile accesses already
provides this guarantee, so actually doing so would be good.

Or a more practical example: While debugging some embedded
device, it would also be very annoying if the compilers reorders
some trap before some debugging output. I could easily imagine
loosing hours figuring out what happens.


Martin

Re: reordering of trapping operations and volatile

[Martin Uecker]

Am Samstag, den 08.01.2022, 16:03 +0100 schrieb David Brown:
> On 08/01/2022 09:32, Martin Uecker via Gcc wrote:
> > Hi Richard,
> > 
> > I have a question regarding reodering of volatile
> > accesses and trapping operations. My initial
> > assumption (and  hope) was that compilers take
> > care to avoid creating traps that are incorrectly
> > ordered relative to observable behavior.
> > 
> > I had trouble finding examples, and my cursory
> > glace at the code seemed to confirm that GCC
> > carefully avoids this.  But then someone showed
> > me this example, where this can happen in GCC:
> > 
> > 
> > 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;
> > }
> > 
> > 
> > https://godbolt.org/z/vq3r8vjxr
> > 
> > In this example a division is hoisted 
> > before the volatile store. (the division
> > by zero which could trap is UB, of course).
> > 
> 
> Doesn't this depend on whether the trap is considered "observable
> behaviour", or "undefined behaviour" ?
> 
> If (on the given target cpu and OS, and with any relevant compiler
> flags) dividing by zero is guaranteed to give a trap with specific known
> behaviour, then it is observable behaviour and thus should be ordered
> carefully with respect to the volatile accesses.
> 
> On the other hand, if division by 0 is considered undefined behaviour
> (the C and C++ standards explicitly mark it as undefined, but a compiler
> can of course define its behaviour) then the compiler can assume it does
> not happen, or you don't care about the result of the program if it
> happens.  Undefined behaviour can be freely re-ordered around volatile
> accesses, as far as I understand it - though that can come as a surprise
> to some people.

In C++ has wording that makes it clear that this reordering
is allowed. In C, some people also see it this way.  In my
opinion, this is not clear and I always read the standard
in a different way (i.e. run-time UB happens at a point
in time but can not go backwards at change previous
defined behavior).

But in any case, I would find it much more useful if it is
guaranteed to not affect previous observable behavior.
This would make volatile more useful, which in my opinion
is preferable to introducing another language feature to
work around this issue.

This of course assumes that this reodering around volatile
accesses and I/O is not essential for optimization.

Martin


> 
> I don't know which of these views gcc takes - I think both are valid.
> But it might be worth noting in the reference manual.
> 
> David
> 
> 
> 
> > As Martin Sebor pointed out this is done
> > as part of redundancy elimination 
> > in tree-ssa-pre.c and that this might
> > simply be an oversight (and could then be
> > fixed with a small change).
> > 
> > Could you clarify whether such reordering
> > is intentional and could be exploited in
> > general also in other optimizations or
> > confirm that this is an oversight that
> > affects only this specific case?
> > 
> > If this is intentional, are there examples
> > where this is important for optimization?
> > 
> > 
> > Martin
> > 
> > 
> > 
> > 
> > 
> > 
> > 

Re: reordering of trapping operations and volatile

[Eric Botcazou]

> Most C programmers would assume that volatile accesses already
> provides this guarantee, so actually doing so would be good.

I'm a little skeptical of this statement: if it was true, how come the most 
recent version of the standard does not provide it 30 years after the language 
was first standardized?

> Or a more practical example: While debugging some embedded
> device, it would also be very annoying if the compilers reorders
> some trap before some debugging output. I could easily imagine
> loosing hours figuring out what happens.

The thing to do to avoid losing these hours is to debug the code at -O0.

-- 
Eric Botcazou

Re: reordering of trapping operations and volatile

[Andrew Pinski]

On Sat, Jan 8, 2022 at 12:33 AM Martin Uecker via Gcc <gcc@gcc.gnu.org> wrote:
>
>
> Hi Richard,
>
> I have a question regarding reodering of volatile
> accesses and trapping operations. My initial
> assumption (and  hope) was that compilers take
> care to avoid creating traps that are incorrectly
> ordered relative to observable behavior.
>
> I had trouble finding examples, and my cursory
> glace at the code seemed to confirm that GCC
> carefully avoids this.  But then someone showed
> me this example, where this can happen in GCC:
>
>
> 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;
> }
>
>
> https://godbolt.org/z/vq3r8vjxr

The question becomes what is a trapping instruction vs an undefined instruction?
For floating point types, it is well defined what is a trapping
instruction while for integer types it is not well defined.
On some (many?) targets dividing by 0 is just undefined and does not
trap (powerpc, aarch64, arm and many others; MIPS it depends on the
options passed to GCC if the conditional trap should be inserted or
not).
The other side is if there is undefined code on the path, should
observable results happen first (stores to volatile/atomics, etc.)?

GCC assumes by default that divide is trappable but stores not are not
observable. This is where -fnon-call-exceptions come into play.

In the second case, GCC assumes reducing trappable instructions are
fine. Note I thought -fno-delete-dead-exceptions would fix the sink
but it didn't.

Thanks,
Andrew Pinski

>
> In this example a division is hoisted
> before the volatile store. (the division
> by zero which could trap is UB, of course).
>
> As Martin Sebor pointed out this is done
> as part of redundancy elimination
> in tree-ssa-pre.c and that this might
> simply be an oversight (and could then be
> fixed with a small change).
>
> Could you clarify whether such reordering
> is intentional and could be exploited in
> general also in other optimizations or
> confirm that this is an oversight that
> affects only this specific case?
>
> If this is intentional, are there examples
> where this is important for optimization?
>
>
> Martin
>
>
>
>
>
>

Re: reordering of trapping operations and volatile

[Martin Uecker]

Am Samstag, den 08.01.2022, 10:35 -0800 schrieb Andrew Pinski:
> On Sat, Jan 8, 2022 at 12:33 AM Martin Uecker via Gcc <gcc@gcc.gnu.org> wrote:
> > 
> > Hi Richard,
> > 
> > I have a question regarding reodering of volatile
> > accesses and trapping operations. My initial
> > assumption (and  hope) was that compilers take
> > care to avoid creating traps that are incorrectly
> > ordered relative to observable behavior.
> > 
> > I had trouble finding examples, and my cursory
> > glace at the code seemed to confirm that GCC
> > carefully avoids this.  But then someone showed
> > me this example, where this can happen in GCC:
> > 
> > 
> > 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;
> > }
> > 
> > 
> > https://godbolt.org/z/vq3r8vjxr
> 
> The question becomes what is a trapping instruction vs an undefined
> instruction?
> For floating point types, it is well defined what is a trapping
> instruction while for integer types it is not well defined.
> On some (many?) targets dividing by 0 is just undefined and does not
> trap (powerpc, aarch64, arm and many others; MIPS it depends on the
> options passed to GCC if the conditional trap should be inserted or
> not).

> The other side is if there is undefined code on the path, should
> observable results happen first (stores to volatile/atomics, etc.)?

I think for volatile stores and I/O, I think it would be
nice of we could guarantee that those happen before the UB
ruins the day. (I am not sure about atomics, those are 
not directly obsevable)

For I/O this is probably already the case (?).
For volatile, it seems this would need some tweaks.

I am trying to figure out whether this is feasible.

> GCC assumes by default that divide is trappable but stores not are not
> observable. This is where -fnon-call-exceptions come into play.

Ok, thanks! I will look at this!

> In the second case, GCC assumes reducing trappable instructions are
> fine. 

-fnon-call-exceptions would treat trapping instructions
as defined (and trapping) instead of UB? This is
then probably even stronger than the requirement above.

> Note I thought -fno-delete-dead-exceptions would fix the sink
> but it didn't.


Martin

Re: reordering of trapping operations and volatile

[Richard Biener]

On Sat, Jan 8, 2022 at 10:09 PM Martin Uecker via Gcc <gcc@gcc.gnu.org> wrote:
>
> Am Samstag, den 08.01.2022, 10:35 -0800 schrieb Andrew Pinski:
> > On Sat, Jan 8, 2022 at 12:33 AM Martin Uecker via Gcc <gcc@gcc.gnu.org> wrote:
> > >
> > > Hi Richard,
> > >
> > > I have a question regarding reodering of volatile
> > > accesses and trapping operations. My initial
> > > assumption (and  hope) was that compilers take
> > > care to avoid creating traps that are incorrectly
> > > ordered relative to observable behavior.
> > >
> > > I had trouble finding examples, and my cursory
> > > glace at the code seemed to confirm that GCC
> > > carefully avoids this.  But then someone showed
> > > me this example, where this can happen in GCC:
> > >
> > >
> > > 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;
> > > }
> > >
> > >
> > > https://godbolt.org/z/vq3r8vjxr
> >
> > The question becomes what is a trapping instruction vs an undefined
> > instruction?
> > For floating point types, it is well defined what is a trapping
> > instruction while for integer types it is not well defined.
> > On some (many?) targets dividing by 0 is just undefined and does not
> > trap (powerpc, aarch64, arm and many others; MIPS it depends on the
> > options passed to GCC if the conditional trap should be inserted or
> > not).
>
> > The other side is if there is undefined code on the path, should
> > observable results happen first (stores to volatile/atomics, etc.)?
>
> I think for volatile stores and I/O, I think it would be
> nice of we could guarantee that those happen before the UB
> ruins the day. (I am not sure about atomics, those are
> not directly obsevable)
>
> For I/O this is probably already the case (?).

I/O usually happens through function calls where this is usually
already guaranteed as GCC doesn't know whether the function
will always return normally so the UB of a divide by zero might
be properly guarded.

> For volatile, it seems this would need some tweaks.

Yes, likewise when re-ordering (observable) traps like

  r = a / b;
  q = c / d;

> I am trying to figure out whether this is feasible.

For PRE yes, you'd just need to include the observable stmts you
care in the set of stmts that cause PRE to set BB_MAY_NOTRETURN.
In general this is of course harder.

> > GCC assumes by default that divide is trappable but stores not are not
> > observable. This is where -fnon-call-exceptions come into play.
>
> Ok, thanks! I will look at this!
>
> > In the second case, GCC assumes reducing trappable instructions are
> > fine.
>
> -fnon-call-exceptions would treat trapping instructions
> as defined (and trapping) instead of UB? This is
> then probably even stronger than the requirement above.

No, I don't think it turns UB into defined behavior.  Some frontends might
expect that to some extent.  So even with -fnon-call-exceptions we'd
happily do the re-ordering unless the exception is catched in the same
function.

> > Note I thought -fno-delete-dead-exceptions would fix the sink
> > but it didn't.
>
>
> Martin
>
>

Re: reordering of trapping operations and volatile

[Martin Uecker]

Am Montag, den 10.01.2022, 10:04 +0100 schrieb Richard Biener:
> On Sat, Jan 8, 2022 at 10:09 PM Martin Uecker via Gcc <gcc@gcc.gnu.org> wrote:
> > Am Samstag, den 08.01.2022, 10:35 -0800 schrieb Andrew Pinski:
> > > On Sat, Jan 8, 2022 at 12:33 AM Martin Uecker via Gcc <gcc@gcc.gnu.org> wrote:
> > > > Hi Richard,
> > > > 
> > > > I have a question regarding reodering of volatile
> > > > accesses and trapping operations. My initial
> > > > assumption (and  hope) was that compilers take
> > > > care to avoid creating traps that are incorrectly
> > > > ordered relative to observable behavior.
> > > > 
> > > > I had trouble finding examples, and my cursory
> > > > glace at the code seemed to confirm that GCC
> > > > carefully avoids this.  But then someone showed
> > > > me this example, where this can happen in GCC:
> > > > 
> > > > 
> > > > 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;
> > > > }
> > > > 
> > > > 
> > > > https://godbolt.org/z/vq3r8vjxr
> > > 
> > > The question becomes what is a trapping instruction vs an undefined
> > > instruction?
> > > For floating point types, it is well defined what is a trapping
> > > instruction while for integer types it is not well defined.
> > > On some (many?) targets dividing by 0 is just undefined and does not
> > > trap (powerpc, aarch64, arm and many others; MIPS it depends on the
> > > options passed to GCC if the conditional trap should be inserted or
> > > not).
> > > The other side is if there is undefined code on the path, should
> > > observable results happen first (stores to volatile/atomics, etc.)?
> > 
> > I think for volatile stores and I/O, I think it would be
> > nice of we could guarantee that those happen before the UB
> > ruins the day. (I am not sure about atomics, those are
> > not directly obsevable)
> > 
> > For I/O this is probably already the case (?).
> 
> I/O usually happens through function calls where this is usually
> already guaranteed as GCC doesn't know whether the function
> will always return normally so the UB of a divide by zero might
> be properly guarded.

Yes.

> > For volatile, it seems this would need some tweaks.
> 
> Yes, likewise when re-ordering (observable) traps like
> 
>   r = a / b;
>   q = c / d;

I think this could also be useful. But at the moment I am
concerned about the effect previous defined behavior
being affected. For this, reordering traps is OK.  Also
sinking traps across observable behavior is OK. Just
hoisting it up across observable behavior would 
be a problem.

> > I am trying to figure out whether this is feasible.
> 
> For PRE yes, you'd just need to include the observable stmts you
> care in the set of stmts that cause PRE to set BB_MAY_NOTRETURN.
> In general this is of course harder.

What other passes would need to be checked?

And do you think there is any negative impact on
an important optimization (considering this affects
only volatile accesses)?

> > > GCC assumes by default that divide is trappable but stores not are not
> > > observable. This is where -fnon-call-exceptions come into play.
> > 
> > Ok, thanks! I will look at this!
> > 
> > > In the second case, GCC assumes reducing trappable instructions are
> > > fine.
> > 
> > -fnon-call-exceptions would treat trapping instructions
> > as defined (and trapping) instead of UB? This is
> > then probably even stronger than the requirement above.
> 
> No, I don't think it turns UB into defined behavior.  Some frontends might
> expect that to some extent.  So even with -fnon-call-exceptions we'd
> happily do the re-ordering unless the exception is catched in the same
> function.

Thanks,
Martin

> > > Note I thought -fno-delete-dead-exceptions would fix the sink
> > > but it didn't.
> > 
> > Martin
> > 
> > 

Re: reordering of trapping operations and volatile

[Richard Biener]

On Mon, Jan 10, 2022 at 6:36 PM Martin Uecker <ma.uecker@gmail.com> wrote:
>
> Am Montag, den 10.01.2022, 10:04 +0100 schrieb Richard Biener:
> > On Sat, Jan 8, 2022 at 10:09 PM Martin Uecker via Gcc <gcc@gcc.gnu.org> wrote:
> > > Am Samstag, den 08.01.2022, 10:35 -0800 schrieb Andrew Pinski:
> > > > On Sat, Jan 8, 2022 at 12:33 AM Martin Uecker via Gcc <gcc@gcc.gnu.org> wrote:
> > > > > Hi Richard,
> > > > >
> > > > > I have a question regarding reodering of volatile
> > > > > accesses and trapping operations. My initial
> > > > > assumption (and  hope) was that compilers take
> > > > > care to avoid creating traps that are incorrectly
> > > > > ordered relative to observable behavior.
> > > > >
> > > > > I had trouble finding examples, and my cursory
> > > > > glace at the code seemed to confirm that GCC
> > > > > carefully avoids this.  But then someone showed
> > > > > me this example, where this can happen in GCC:
> > > > >
> > > > >
> > > > > 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;
> > > > > }
> > > > >
> > > > >
> > > > > https://godbolt.org/z/vq3r8vjxr
> > > >
> > > > The question becomes what is a trapping instruction vs an undefined
> > > > instruction?
> > > > For floating point types, it is well defined what is a trapping
> > > > instruction while for integer types it is not well defined.
> > > > On some (many?) targets dividing by 0 is just undefined and does not
> > > > trap (powerpc, aarch64, arm and many others; MIPS it depends on the
> > > > options passed to GCC if the conditional trap should be inserted or
> > > > not).
> > > > The other side is if there is undefined code on the path, should
> > > > observable results happen first (stores to volatile/atomics, etc.)?
> > >
> > > I think for volatile stores and I/O, I think it would be
> > > nice of we could guarantee that those happen before the UB
> > > ruins the day. (I am not sure about atomics, those are
> > > not directly obsevable)
> > >
> > > For I/O this is probably already the case (?).
> >
> > I/O usually happens through function calls where this is usually
> > already guaranteed as GCC doesn't know whether the function
> > will always return normally so the UB of a divide by zero might
> > be properly guarded.
>
> Yes.
>
> > > For volatile, it seems this would need some tweaks.
> >
> > Yes, likewise when re-ordering (observable) traps like
> >
> >   r = a / b;
> >   q = c / d;
>
> I think this could also be useful. But at the moment I am
> concerned about the effect previous defined behavior
> being affected. For this, reordering traps is OK.  Also
> sinking traps across observable behavior is OK. Just
> hoisting it up across observable behavior would
> be a problem.

But in general that would apply to all UB.  Consider

int foo (int a, int b)
{
   if (a < b)
     return a + b;
   bar ();
   return a + b;
}

we are happily hoisting a + b to the start of the function
but of course a + b can invoke UB.  We consider that to
not matter because we eventually invoke this UB anyway.
Unless of course bar() does not return.

I realize that UB in a + b isn't (usually) observable but
UB resulting in traps are.

So I'm still wondering why you think that 'volatile' makes
a critical difference we ought to honor?  I don't remember
'volatile' being special in the definition of the abstract
machine with regarding to observability (as opposed to
sequence points).

> > > I am trying to figure out whether this is feasible.
> >
> > For PRE yes, you'd just need to include the observable stmts you
> > care in the set of stmts that cause PRE to set BB_MAY_NOTRETURN.
> > In general this is of course harder.
>
> What other passes would need to be checked?

All that do code motion by design or by accident.  The difficulty is
that the resulting "wrong IL" is not wrong per se, just the difference is
which is hard to write a checker for (well, in priciple you could copy the
IL before passes and compare to the IL after)

> And do you think there is any negative impact on
> an important optimization (considering this affects
> only volatile accesses)?

Probably not.  But then semantics of 'volatile' are very weak defined
so I'd like
to see a reference to a part of the standard that supports declaring this
(and only this - the 'volatile' case) a bug.

> > > > GCC assumes by default that divide is trappable but stores not are not
> > > > observable. This is where -fnon-call-exceptions come into play.
> > >
> > > Ok, thanks! I will look at this!
> > >
> > > > In the second case, GCC assumes reducing trappable instructions are
> > > > fine.
> > >
> > > -fnon-call-exceptions would treat trapping instructions
> > > as defined (and trapping) instead of UB? This is
> > > then probably even stronger than the requirement above.
> >
> > No, I don't think it turns UB into defined behavior.  Some frontends might
> > expect that to some extent.  So even with -fnon-call-exceptions we'd
> > happily do the re-ordering unless the exception is catched in the same
> > function.
>
> Thanks,
> Martin
>
> > > > Note I thought -fno-delete-dead-exceptions would fix the sink
> > > > but it didn't.
> > >
> > > Martin
> > >
> > >
>

Re: reordering of trapping operations and volatile

[Martin Uecker]

Am Dienstag, den 11.01.2022, 08:11 +0100 schrieb Richard Biener:
> On Mon, Jan 10, 2022 at 6:36 PM Martin Uecker <ma.uecker@gmail.com> wrote:
> > Am Montag, den 10.01.2022, 10:04 +0100 schrieb Richard Biener:

Hi Richard,

> > > > For volatile, it seems this would need some tweaks.
> > > 
> > > Yes, likewise when re-ordering (observable) traps like
> > > 
> > >   r = a / b;
> > >   q = c / d;
> > 
> > I think this could also be useful. But at the moment I am
> > concerned about the effect previous defined behavior
> > being affected. For this, reordering traps is OK.  Also
> > sinking traps across observable behavior is OK. Just
> > hoisting it up across observable behavior would
> > be a problem.
> 
> But in general that would apply to all UB.  Consider
> 
> int foo (int a, int b)
> {
>    if (a < b)
>      return a + b;
>    bar ();
>    return a + b;
> }
> 
> we are happily hoisting a + b to the start of the function
> but of course a + b can invoke UB.  We consider that to
> not matter because we eventually invoke this UB anyway.
> Unless of course bar() does not return.

Yes.

> I realize that UB in a + b isn't (usually) observable but
> UB resulting in traps are.

Code motion for UB which then does not cause
a change in observable behavior would still be ok.

So my understanding is that you can not hoist a potentially
trapping operation across a function call, but if it is
UB which is implemented in way that just produces some
random result but does not trap then this is ok.

It would also be wrong if it affects the arguments for
the function call. Here MSVC seems to do this:

https://godbolt.org/z/8a8fTW8qP

This seems incorect because if the call does not
return there is no UB. I did not observe this with
GCC or another compiler.

> So I'm still wondering why you think that 'volatile' makes
> a critical difference we ought to honor?  I don't remember
> 'volatile' being special in the definition of the abstract
> machine with regarding to observability (as opposed to
> sequence points).

It is because it is used for I/O.   Sequence points only
matter for the semantics of the abstract machine, so
according to "as-if" rule optimizers can do whatever
they want as long as the observable behavior is the same
"as-if" it followed the rules of the abstract machine.

This observable behavior that needs to be preserved is
defined as I/O and volatile accesses. The relevant
part o the standard is this:

"5.1.2.3 Program execution" paragraph 6

The least requirements on a conforming implementation are:

— Accesses to volatile objects are evaluated strictly
according to the rules of the abstract machine.
— At program termination, all data written into files
shall be identical to the result that execution
of the program according to the abstract semantics would 
have produced.
— The input and output dynamics of interactive devices 
shall take place as specified in 7.21.3.

The intent of these requirements is that unbuffered or
line-buffered output appear as soon as possible, to 
ensure that prompting messages actually appear prior
to a program waiting for input.

This is the observable behavior of the program."



Martin

> > > > I am trying to figure out whether this is feasible.
> > > 
> > > For PRE yes, you'd just need to include the observable stmts you
> > > care in the set of stmts that cause PRE to set BB_MAY_NOTRETURN.
> > > In general this is of course harder.
> > 
> > What other passes would need to be checked?
> 
> All that do code motion by design or by accident.  The difficulty is
> that the resulting "wrong IL" is not wrong per se, just the difference is
> which is hard to write a checker for (well, in priciple you could copy the
> IL before passes and compare to the IL after)
> 
> > And do you think there is any negative impact on
> > an important optimization (considering this affects
> > only volatile accesses)?
> 
> Probably not.  But then semantics of 'volatile' are very weak defined
> so I'd like
> to see a reference to a part of the standard that supports declaring this
> (and only this - the 'volatile' case) a bug.
> 
> > > > > GCC assumes by default that divide is trappable but stores not are not
> > > > > observable. This is where -fnon-call-exceptions come into play.
> > > > 
> > > > Ok, thanks! I will look at this!
> > > > 
> > > > > In the second case, GCC assumes reducing trappable instructions are
> > > > > fine.
> > > > 
> > > > -fnon-call-exceptions would treat trapping instructions
> > > > as defined (and trapping) instead of UB? This is
> > > > then probably even stronger than the requirement above.
> > > 
> > > No, I don't think it turns UB into defined behavior.  Some frontends might
> > > expect that to some extent.  So even with -fnon-call-exceptions we'd
> > > happily do the re-ordering unless the exception is catched in the same
> > > function.
> > 
> > Thanks,
> > Martin
> > 
> > > > > Note I thought -fno-delete-dead-exceptions would fix the sink
> > > > > but it didn't.
> > > > 
> > > > Martin
> > > > 
> > > > 

Re: reordering of trapping operations and volatile

[Richard Biener]

On Tue, Jan 11, 2022 at 9:17 AM Martin Uecker <ma.uecker@gmail.com> wrote:
>
> Am Dienstag, den 11.01.2022, 08:11 +0100 schrieb Richard Biener:
> > On Mon, Jan 10, 2022 at 6:36 PM Martin Uecker <ma.uecker@gmail.com> wrote:
> > > Am Montag, den 10.01.2022, 10:04 +0100 schrieb Richard Biener:
>
> Hi Richard,
>
> > > > > For volatile, it seems this would need some tweaks.
> > > >
> > > > Yes, likewise when re-ordering (observable) traps like
> > > >
> > > >   r = a / b;
> > > >   q = c / d;
> > >
> > > I think this could also be useful. But at the moment I am
> > > concerned about the effect previous defined behavior
> > > being affected. For this, reordering traps is OK.  Also
> > > sinking traps across observable behavior is OK. Just
> > > hoisting it up across observable behavior would
> > > be a problem.
> >
> > But in general that would apply to all UB.  Consider
> >
> > int foo (int a, int b)
> > {
> >    if (a < b)
> >      return a + b;
> >    bar ();
> >    return a + b;
> > }
> >
> > we are happily hoisting a + b to the start of the function
> > but of course a + b can invoke UB.  We consider that to
> > not matter because we eventually invoke this UB anyway.
> > Unless of course bar() does not return.
>
> Yes.
>
> > I realize that UB in a + b isn't (usually) observable but
> > UB resulting in traps are.
>
> Code motion for UB which then does not cause
> a change in observable behavior would still be ok.
>
> So my understanding is that you can not hoist a potentially
> trapping operation across a function call, but if it is
> UB which is implemented in way that just produces some
> random result but does not trap then this is ok.
>
> It would also be wrong if it affects the arguments for
> the function call. Here MSVC seems to do this:
>
> https://godbolt.org/z/8a8fTW8qP
>
> This seems incorect because if the call does not
> return there is no UB. I did not observe this with
> GCC or another compiler.
>
> > So I'm still wondering why you think that 'volatile' makes
> > a critical difference we ought to honor?  I don't remember
> > 'volatile' being special in the definition of the abstract
> > machine with regarding to observability (as opposed to
> > sequence points).
>
> It is because it is used for I/O.   Sequence points only
> matter for the semantics of the abstract machine, so
> according to "as-if" rule optimizers can do whatever
> they want as long as the observable behavior is the same
> "as-if" it followed the rules of the abstract machine.
>
> This observable behavior that needs to be preserved is
> defined as I/O and volatile accesses. The relevant
> part o the standard is this:
>
> "5.1.2.3 Program execution" paragraph 6
>
> The least requirements on a conforming implementation are:
>
> — Accesses to volatile objects are evaluated strictly
> according to the rules of the abstract machine.
> — At program termination, all data written into files
> shall be identical to the result that execution
> of the program according to the abstract semantics would
> have produced.
> — The input and output dynamics of interactive devices
> shall take place as specified in 7.21.3.
>
> The intent of these requirements is that unbuffered or
> line-buffered output appear as soon as possible, to
> ensure that prompting messages actually appear prior
> to a program waiting for input.
>
> This is the observable behavior of the program."

OK, I think that 'volatile is used for I/O' is a common misconception,
but well.  Consider

int a[1024];
void foo (volatile int *p, float *q)
{
   for (int i = 0; i < 1024; ++i)
      {
         *p = 1;
         a[i] = *q;
      }
}

we happily apply invariant motion to the load from *q, making
it cross the store to the volatile object at *p.  Now, q might be
NULL upon entry to the function and thus this transform
would violate the volatile "I/O" constraint (since I/O is observable)
and thus we will crash (which is UB) before doing the first I/O.

That's an example I'd consider important for performance and
also a case that shows that usually the compiler will have a
very hard time proving UB cannot happen (as opposed to the
usual stance where it can assume it doesn't).

The case we run into sth similar is with use of uninitialized
variables where proving some variable is initialized is nearly
impossible (copy initialization from a variable that is not
initialized is not initialization).

We've mainly settled to the stance that only program termination
is observable which means if we do not know that a function
call will always return normally we have to avoid hoisting
observable UB across such function call (and I/O routines
usually fall into this category because they are not annotated
as always returning).  Handling all volatile accesses in the
very same way would be possible but quite some work I don't
see much value in.

Richard.

>
>
> Martin
>
> > > > > I am trying to figure out whether this is feasible.
> > > >
> > > > For PRE yes, you'd just need to include the observable stmts you
> > > > care in the set of stmts that cause PRE to set BB_MAY_NOTRETURN.
> > > > In general this is of course harder.
> > >
> > > What other passes would need to be checked?
> >
> > All that do code motion by design or by accident.  The difficulty is
> > that the resulting "wrong IL" is not wrong per se, just the difference is
> > which is hard to write a checker for (well, in priciple you could copy the
> > IL before passes and compare to the IL after)
> >
> > > And do you think there is any negative impact on
> > > an important optimization (considering this affects
> > > only volatile accesses)?
> >
> > Probably not.  But then semantics of 'volatile' are very weak defined
> > so I'd like
> > to see a reference to a part of the standard that supports declaring this
> > (and only this - the 'volatile' case) a bug.
> >
> > > > > > GCC assumes by default that divide is trappable but stores not are not
> > > > > > observable. This is where -fnon-call-exceptions come into play.
> > > > >
> > > > > Ok, thanks! I will look at this!
> > > > >
> > > > > > In the second case, GCC assumes reducing trappable instructions are
> > > > > > fine.
> > > > >
> > > > > -fnon-call-exceptions would treat trapping instructions
> > > > > as defined (and trapping) instead of UB? This is
> > > > > then probably even stronger than the requirement above.
> > > >
> > > > No, I don't think it turns UB into defined behavior.  Some frontends might
> > > > expect that to some extent.  So even with -fnon-call-exceptions we'd
> > > > happily do the re-ordering unless the exception is catched in the same
> > > > function.
> > >
> > > Thanks,
> > > Martin
> > >
> > > > > > Note I thought -fno-delete-dead-exceptions would fix the sink
> > > > > > but it didn't.
> > > > >
> > > > > Martin
> > > > >
> > > > >
>

Re: reordering of trapping operations and volatile

[David Brown]

On 11/01/2022 08:11, Richard Biener via Gcc wrote:
> On Mon, Jan 10, 2022 at 6:36 PM Martin Uecker <ma.uecker@gmail.com> wrote:
>>

<snip>

> 
> I realize that UB in a + b isn't (usually) observable but
> UB resulting in traps are.
> 
> So I'm still wondering why you think that 'volatile' makes
> a critical difference we ought to honor?  I don't remember
> 'volatile' being special in the definition of the abstract
> machine with regarding to observability (as opposed to
> sequence points).
> 
> 

Actually, volatile accesses /are/ critical to observable behaviour -
observable behaviour is program start and termination (normal
termination flushing file buffers, not crashes which are UB), input and
output via "interactive devices" (these are not defined by the
standard), and volatile accesses.  (See 5.1.2.3p6 in the standards if
you want the details.  Note that in C18, "volatile access" was expanded
to include all accesses through volatile-qualified lvalues.)


However, undefined behaviour is /not/ observable behaviour.  It can also
be viewed as not affecting anything else, and so moving it does not
affect volatile accesses.

So you can't re-order two volatile accesses with respect to each other.
 But you /can/ re-order UB with respect to anything else, including
volatile accesses.  (IMHO)

"Performing a trap" - such as some systems will do when dividing by 0,
for example - is not listed as observable behaviour.

<snip>

Re: reordering of trapping operations and volatile

[Martin Uecker]

Am Dienstag, den 11.01.2022, 10:13 +0100 schrieb Richard Biener:
> On Tue, Jan 11, 2022 at 9:17 AM Martin Uecker <ma.uecker@gmail.com> wrote:
> > Am Dienstag, den 11.01.2022, 08:11 +0100 schrieb Richard Biener:
> > > On Mon, Jan 10, 2022 at 6:36 PM Martin Uecker <ma.uecker@gmail.com> wrote:
> > > > Am Montag, den 10.01.2022, 10:04 +0100 schrieb Richard Biener:

...
> Consider
> 
> int a[1024];
> void foo (volatile int *p, float *q)
> {
>    for (int i = 0; i < 1024; ++i)
>       {
>          *p = 1;
>          a[i] = *q;
>       }
> }
> 
> we happily apply invariant motion to the load from *q, making
> it cross the store to the volatile object at *p.  Now, q might be
> NULL upon entry to the function and thus this transform
> would violate the volatile "I/O" constraint (since I/O is observable)
> and thus we will crash (which is UB) before doing the first I/O.
> 
> That's an example I'd consider important for performance and
> also a case that shows that usually the compiler will have a
> very hard time proving UB cannot happen (as opposed to the
> usual stance where it can assume it doesn't).

I can see that the transformation in general is important,
but why is it important if the "volatile" is there?

I would assume that performance-sensitive code usually
does not volatile. 

Or in other words, what is the purpose of volatile in 
this example if not either I/O or to prevent such
optimizations?

> The case we run into sth similar is with use of uninitialized
> variables where proving some variable is initialized is nearly
> impossible (copy initialization from a variable that is not
> initialized is not initialization).

These are the C++ rules.

For C, an automatic variables which is not initialized and
(as long as the address is not taken), it is directly UB.


> We've mainly settled to the stance that only program termination
> is observable which means if we do not know that a function
> call will always return normally we have to avoid hoisting
> observable UB across such function call (and I/O routines
> usually fall into this category because they are not annotated
> as always returning). 

Yes.

>  Handling all volatile accesses in the
> very same way would be possible but quite some work I don't
> see much value in.

I see some value. 

But an alternative could be to remove volatile
from the observable behavior in the standard
or make it implementation-defined whether it
is observable or not.

Martin


> Richard.
> 
> > Martin
> > 
> > > > > > I am trying to figure out whether this is feasible.
> > > > > 
> > > > > For PRE yes, you'd just need to include the observable stmts you
> > > > > care in the set of stmts that cause PRE to set BB_MAY_NOTRETURN.
> > > > > In general this is of course harder.
> > > > 
> > > > What other passes would need to be checked?
> > > 
> > > All that do code motion by design or by accident.  The difficulty is
> > > that the resulting "wrong IL" is not wrong per se, just the difference is
> > > which is hard to write a checker for (well, in priciple you could copy the
> > > IL before passes and compare to the IL after)
> > > 
> > > > And do you think there is any negative impact on
> > > > an important optimization (considering this affects
> > > > only volatile accesses)?
> > > 
> > > Probably not.  But then semantics of 'volatile' are very weak defined
> > > so I'd like
> > > to see a reference to a part of the standard that supports declaring this
> > > (and only this - the 'volatile' case) a bug.
> > > 
> > > > > > > GCC assumes by default that divide is trappable but stores not are not
> > > > > > > observable. This is where -fnon-call-exceptions come into play.
> > > > > > 
> > > > > > Ok, thanks! I will look at this!
> > > > > > 
> > > > > > > In the second case, GCC assumes reducing trappable instructions are
> > > > > > > fine.
> > > > > > 
> > > > > > -fnon-call-exceptions would treat trapping instructions
> > > > > > as defined (and trapping) instead of UB? This is
> > > > > > then probably even stronger than the requirement above.
> > > > > 
> > > > > No, I don't think it turns UB into defined behavior.  Some frontends might
> > > > > expect that to some extent.  So even with -fnon-call-exceptions we'd
> > > > > happily do the re-ordering unless the exception is catched in the same
> > > > > function.
> > > > 
> > > > Thanks,
> > > > Martin
> > > > 
> > > > > > > Note I thought -fno-delete-dead-exceptions would fix the sink
> > > > > > > but it didn't.
> > > > > > 
> > > > > > Martin
> > > > > > 
> > > > > > 

Re: reordering of trapping operations and volatile

[Michael Matz]

Hello,

On Tue, 11 Jan 2022, Martin Uecker via Gcc wrote:

> >  Handling all volatile accesses in the
> > very same way would be possible but quite some work I don't
> > see much value in.
> 
> I see some value. 
> 
> But an alternative could be to remove volatile
> from the observable behavior in the standard
> or make it implementation-defined whether it
> is observable or not.

But you are actually arguing for making UB be observable (which then 
directly implies an ordering with respect to volatile accesses).  That's 
much different from making volatile not be observable anymore (which 
obviously would be a bad idea), and is also much harder to do, it's 
the nature of undefined behaviour to be hard to define :)

Well, what you _actually_ want is an implied dependency between some UB 
and volatile accesses (and _only_ those, not e.g. with other UB), and the 
difficulty now is to define "some" and to create the dependency without 
making that specific UB to be properly observable.  I think to define this 
all rigorously seems futile (you need a new category between observable 
and UB), so it comes down to compiler QoI on a case by case basis.


Ciao,
Michael.

Re: reordering of trapping operations and volatile

[Martin Uecker]

Am Donnerstag, den 13.01.2022, 16:45 +0000 schrieb Michael Matz:
> Hello,
> 
> On Tue, 11 Jan 2022, Martin Uecker via Gcc wrote:
> 
> > >  Handling all volatile accesses in the
> > > very same way would be possible but quite some work I don't
> > > see much value in.
> > 
> > I see some value. 
> > 
> > But an alternative could be to remove volatile
> > from the observable behavior in the standard
> > or make it implementation-defined whether it
> > is observable or not.
> 
> But you are actually arguing for making UB be observable

No, I am arguing for UB not to have the power
to go back in time and change previous defined
observable behavior.  The reason is that it
makes it impossible to give any guarantees
about partial executions of a program  e.g.
that a transaction completed or privileges
were dropped or a log message went out to
the log server), when there is the possibility
that later there could be some UB in the program.


Making UB observable would be even stronger.
For example I do not mind a compiler sinking
a division by zero across other observable
behavior, which would not be possible if we
consider the trap to be observable.

>  (which then  directly implies an ordering
> with respect to volatile accesses). 

Yes, it would, but "no time-travel" only implies
some weaker constraints for UB and only if
it actually traps or could affect observable
behavior in other ways.

For I/O using function calls these constraints
are already fulfilled.

>  That's 
> much different from making volatile not be
> observable anymore (which  obviously would
> be a bad idea), and is also much harder to

I tend to agree that volatile should be
considered observable. But volatile is
a bit implementation-defined anyway, so this
would be a compromise so that implementations
do not have to make all the implied changes
if we revise the meaning of UB.

> do, it's  the nature of undefined behaviour
> to be hard to define :)
>
> Well, what you _actually_ want is an implied
> dependency between some UB and volatile accesses
> (and _only_ those, not e.g. with other UB), and the 
> difficulty now is to define "some" and to create
> the dependency without making that specific UB
> to be properly observable. 

Yes, this is what I actually want.

>  I think to define this 
> all rigorously seems futile (you need a new
> category between observable  and UB), so it comes
> down to compiler QoI on a case by case basis.

We would simply change UB to mean "arbitrary
behavior at the point of time the erraneous
construct is encountered at run-time"  and 
not "the complete program is invalid all
together". I see no problem in specifying this
(even in a formally precise way)

Martin

Re: reordering of trapping operations and volatile

[Michael Matz]

Hello,

On Thu, 13 Jan 2022, Martin Uecker wrote:

> > > >  Handling all volatile accesses in the very same way would be 
> > > > possible but quite some work I don't see much value in.
> > > 
> > > I see some value. 
> > > 
> > > But an alternative could be to remove volatile
> > > from the observable behavior in the standard
> > > or make it implementation-defined whether it
> > > is observable or not.
> > 
> > But you are actually arguing for making UB be observable
> 
> No, I am arguing for UB not to have the power
> to go back in time and change previous defined
> observable behavior.

But right now that's equivalent to making it observable,
because we don't have any other terms than observable or
undefined.  As aluded to later you would have to
introduce a new concept, something pseudo-observable,
which you then started doing.  So, see below.
 
> > That's 
> > much different from making volatile not be
> > observable anymore (which  obviously would
> > be a bad idea), and is also much harder to
> 
> I tend to agree that volatile should be
> considered observable. But volatile is
> a bit implementation-defined anyway, so this
> would be a compromise so that implementations
> do not have to make all the implied changes
> if we revise the meaning of UB.

Using volatile accesses for memory mapped IO is a much stronger use-case 
than your wish of using volatile accesses to block moving of UB as a 
debugging aid, and the former absolutely needs some guarantees, so I don't 
think it would be a compromise at all.  Mkaing volatile not be observable 
would break the C language.

> > Well, what you _actually_ want is an implied
> > dependency between some UB and volatile accesses
> > (and _only_ those, not e.g. with other UB), and the 
> > difficulty now is to define "some" and to create
> > the dependency without making that specific UB
> > to be properly observable. 
> 
> Yes, this is what I actually want.
> 
> >  I think to define this 
> > all rigorously seems futile (you need a new
> > category between observable  and UB), so it comes
> > down to compiler QoI on a case by case basis.
> 
> We would simply change UB to mean "arbitrary
> behavior at the point of time the erraneous
> construct is encountered at run-time"  and 
> not "the complete program is invalid all
> together". I see no problem in specifying this
> (even in a formally precise way)

First you need to define "point in time", a concept which doesn't exist 
yet in C.  The obvious choice is of course observable behaviour in the 
execution environment and its specified ordering from the abstract 
machine, as clarified via sequence points.  With that your "at the point 
in time" becomes something like "after all side effects of previous 
sequence point, but strictly before all side effects of next sequence 
point".

But doing that would have very far reaching consequences, as already
stated in this thread.  The above would basically make undefined behaviour 
be reliably countable, and all implementations would need to produce the 
same counts of UB.  That in turn disables many code movement and 
commonization transformations, e.g. this:

int a = ..., b = ...;
int x = a + b;
int y = a + b;

can't be transformed into "y = x = a + b" anymore, because the addition 
_might_ overflow, and if it does you have two UBs originally but would 
have one UB after.  I know that you don't want to inhibit this or similar 
transformations, but that would be the result of making UB countable, 
which is the result of forcing UB to happen at specific points in time.  
So, I continue to see problems in precisely specifying what you want, _but 
not more_.

I think all models in which you order the happening of UB with respect to 
existing side effects (per abstract machine, so it includes modification 
of objects!) have this same problem, it always becomes a side effect 
itself (one where you don't specify what actually happens, but a side 
effect nontheless) and hence becomes observable.


Ciao,
Michael.

Re: reordering of trapping operations and volatile

[Paul Koning]

> On Jan 14, 2022, at 9:15 AM, Michael Matz via Gcc <gcc@gcc.gnu.org> wrote:
> 
> Hello,
> 
> On Thu, 13 Jan 2022, Martin Uecker wrote:
> 
>>>>> Handling all volatile accesses in the very same way would be 
>>>>> possible but quite some work I don't see much value in.
>>>> 
>>>> I see some value. 
>>>> 
>>>> But an alternative could be to remove volatile
>>>> from the observable behavior in the standard
>>>> or make it implementation-defined whether it
>>>> is observable or not.
>>> 
>>> But you are actually arguing for making UB be observable
>> 
>> No, I am arguing for UB not to have the power
>> to go back in time and change previous defined
>> observable behavior.
> 
> But right now that's equivalent to making it observable,
> because we don't have any other terms than observable or
> undefined.  As aluded to later you would have to
> introduce a new concept, something pseudo-observable,
> which you then started doing.  So, see below.

I find it really hard to view this notion of doing work for UB with any favor.  The way I see it is that a program having UB is synonymous with "defective program" and for the compiler to do extra work for these doesn't make much sense to me.

If the issue is specifically the handling of overflow traps, perhaps a better answer would be to argue for language changes that manage such events explicitly rather than having them be undefined behavior.  Another (similar) option might be to choose a language in which this is done.  (Is Ada such a language?  I don't remember.)

	paul

Re: reordering of trapping operations and volatile

[Martin Uecker]

Am Freitag, den 14.01.2022, 14:15 +0000 schrieb Michael Matz:
> Hello,
> 
> On Thu, 13 Jan 2022, Martin Uecker wrote:

...

> > >  I think to define this 
> > > all rigorously seems futile (you need a new
> > > category between observable  and UB), so it comes
> > > down to compiler QoI on a case by case basis.
> > 
> > We would simply change UB to mean "arbitrary
> > behavior at the point of time the erraneous
> > construct is encountered at run-time"  and 
> > not "the complete program is invalid all
> > together". I see no problem in specifying this
> > (even in a formally precise way)
> 
> First you need to define "point in time", a concept which doesn't exist 
> yet in C.  The obvious choice is of course observable behaviour in the 
> execution environment and its specified ordering from the abstract 
> machine, as clarified via sequence points.  With that your "at the point 
> in time" becomes something like "after all side effects of previous 
> sequence point, but strictly before all side effects of next sequence 
> point".

Yes, all observable side effects sequenced before
the erroneous operation should be preserved. We
also need to consider multi-threading (happens-before)
But I do not think there is any need to discuss the
precise wording now.

> But doing that would have very far reaching consequences, as already
> stated in this thread.  

We already agreed that UB already works like this
relative to every function call.  So why do you
think this could have far reaching consequences
when we also require this for volatile accesses
- considering that volatile accesses are not nearly
as common as function calls, and often already
limit optimization?

We had a lot of trouble even finding examples where
compiler currently exhibit behavior that would need
to change.

> The above would basically make undefined behaviour 
> be reliably countable, and all implementations would need to produce the 
> same counts of UB.  That in turn disables many code movement and 
> commonization transformations, e.g. this:
> 
> int a = ..., b = ...;
> int x = a + b;
> int y = a + b;
> 
> can't be transformed into "y = x = a + b" anymore, because the addition 
> _might_ overflow, and if it does you have two UBs originally but would 
> have one UB after.  I know that you don't want to inhibit this or similar 
> transformations, but that would be the result of making UB countable, 
> which is the result of forcing UB to happen at specific points in time.  
> So, I continue to see problems in precisely specifying what you want, _but 
> not more_.

Don't worry, I do not want to make UB observable or
countable. Your example does not contain observable
behavior, so would be unaffected.

> I think all models in which you order the happening of UB with respect to 
> existing side effects (per abstract machine, so it includes modification 
> of objects!) have this same problem, it always becomes a side effect 
> itself (one where you don't specify what actually happens, but a side 
> effect nontheless) and hence becomes observable.

I don't think so. The standard always only defines behavior.
Here, would only guarantee that observable behavior before
a specific time point stays defined. For this we do not make
UB observable or countable because the statements we make 
is not about the UB,  but about the defined behavior before.


Martin

Re: reordering of trapping operations and volatile

[Jonathan Wakely]

On Fri, 14 Jan 2022, 14:17 Michael Matz via Gcc, <gcc@gcc.gnu.org> wrote:

> Hello,
>
> On Thu, 13 Jan 2022, Martin Uecker wrote:
>
> > > > >  Handling all volatile accesses in the very same way would be
> > > > > possible but quite some work I don't see much value in.
> > > >
> > > > I see some value.
> > > >
> > > > But an alternative could be to remove volatile
> > > > from the observable behavior in the standard
> > > > or make it implementation-defined whether it
> > > > is observable or not.
> > >
> > > But you are actually arguing for making UB be observable
> >
> > No, I am arguing for UB not to have the power
> > to go back in time and change previous defined
> > observable behavior.
>
> But right now that's equivalent to making it observable,
> because we don't have any other terms than observable or
> undefined.  As aluded to later you would have to
> introduce a new concept, something pseudo-observable,
> which you then started doing.  So, see below.
>
> > > That's
> > > much different from making volatile not be
> > > observable anymore (which  obviously would
> > > be a bad idea), and is also much harder to
> >
> > I tend to agree that volatile should be
> > considered observable. But volatile is
> > a bit implementation-defined anyway, so this
> > would be a compromise so that implementations
> > do not have to make all the implied changes
> > if we revise the meaning of UB.
>
> Using volatile accesses for memory mapped IO is a much stronger use-case
> than your wish of using volatile accesses to block moving of UB as a
> debugging aid, and the former absolutely needs some guarantees, so I don't
> think it would be a compromise at all.  Mkaing volatile not be observable
> would break the C language.
>
> > > Well, what you _actually_ want is an implied
> > > dependency between some UB and volatile accesses
> > > (and _only_ those, not e.g. with other UB), and the
> > > difficulty now is to define "some" and to create
> > > the dependency without making that specific UB
> > > to be properly observable.
> >
> > Yes, this is what I actually want.
> >
> > >  I think to define this
> > > all rigorously seems futile (you need a new
> > > category between observable  and UB), so it comes
> > > down to compiler QoI on a case by case basis.
> >
> > We would simply change UB to mean "arbitrary
> > behavior at the point of time the erraneous
> > construct is encountered at run-time"  and
> > not "the complete program is invalid all
> > together". I see no problem in specifying this
> > (even in a formally precise way)
>
> First you need to define "point in time", a concept which doesn't exist
> yet in C.  The obvious choice is of course observable behaviour in the
> execution environment and its specified ordering from the abstract
> machine, as clarified via sequence points.  With that your "at the point
> in time" becomes something like "after all side effects of previous
> sequence point, but strictly before all side effects of next sequence
> point".
>
> But doing that would have very far reaching consequences, as already
> stated in this thread.  The above would basically make undefined behaviour
> be reliably countable, and all implementations would need to produce the
> same counts of UB.  That in turn disables many code movement and
> commonization transformations, e.g. this:
>
> int a = ..., b = ...;
> int x = a + b;
> int y = a + b;
>
> can't be transformed into "y = x = a + b" anymore, because the addition
> _might_ overflow, and if it does you have two UBs originally but would
> have one UB after.  I know that you don't want to inhibit this or similar
> transformations, but that would be the result of making UB countable,
> which is the result of forcing UB to happen at specific points in time.
> So, I continue to see problems in precisely specifying what you want, _but
> not more_.
>
> I think all models in which you order the happening of UB with respect to
> existing side effects (per abstract machine, so it includes modification
> of objects!) have this same problem, it always becomes a side effect
> itself (one where you don't specify what actually happens, but a side
> effect nontheless) and hence becomes observable.
>


The C++ committee is currently considering this paper:

http://www.open-std.org/jtc1/sc22/wg21/docs/papers/2021/p1494r2.html

I think this explicit barrier-like solution is better than trying to use
volatile accesses to achieve something similar.





>
>
>

Re: reordering of trapping operations and volatile

[Martin Uecker]

Am Freitag, den 14.01.2022, 19:54 +0000 schrieb Jonathan Wakely:
> On Fri, 14 Jan 2022, 14:17 Michael Matz via Gcc, <gcc@gcc.gnu.org> wrote:
> 
> > Hello,
> > 
> > On Thu, 13 Jan 2022, Martin Uecker wrote:
> > 
> > > > > >  Handling all volatile accesses in the very same way would be
> > > > > > possible but quite some work I don't see much value in.
> > > > > 
> > > > > I see some value.
> > > > > 
> > > > > But an alternative could be to remove volatile
> > > > > from the observable behavior in the standard
> > > > > or make it implementation-defined whether it
> > > > > is observable or not.
> > > > 
> > > > But you are actually arguing for making UB be observable
> > > 
> > > No, I am arguing for UB not to have the power
> > > to go back in time and change previous defined
> > > observable behavior.
> > 
> > But right now that's equivalent to making it observable,
> > because we don't have any other terms than observable or
> > undefined.  As aluded to later you would have to
> > introduce a new concept, something pseudo-observable,
> > which you then started doing.  So, see below.
> > 
> > > > That's
> > > > much different from making volatile not be
> > > > observable anymore (which  obviously would
> > > > be a bad idea), and is also much harder to
> > > 
> > > I tend to agree that volatile should be
> > > considered observable. But volatile is
> > > a bit implementation-defined anyway, so this
> > > would be a compromise so that implementations
> > > do not have to make all the implied changes
> > > if we revise the meaning of UB.
> > 
> > Using volatile accesses for memory mapped IO is a much stronger use-case
> > than your wish of using volatile accesses to block moving of UB as a
> > debugging aid, and the former absolutely needs some guarantees, so I don't
> > think it would be a compromise at all.  Mkaing volatile not be observable
> > would break the C language.
> > 
> > > > Well, what you _actually_ want is an implied
> > > > dependency between some UB and volatile accesses
> > > > (and _only_ those, not e.g. with other UB), and the
> > > > difficulty now is to define "some" and to create
> > > > the dependency without making that specific UB
> > > > to be properly observable.
> > > 
> > > Yes, this is what I actually want.
> > > 
> > > >  I think to define this
> > > > all rigorously seems futile (you need a new
> > > > category between observable  and UB), so it comes
> > > > down to compiler QoI on a case by case basis.
> > > 
> > > We would simply change UB to mean "arbitrary
> > > behavior at the point of time the erraneous
> > > construct is encountered at run-time"  and
> > > not "the complete program is invalid all
> > > together". I see no problem in specifying this
> > > (even in a formally precise way)
> > 
> > First you need to define "point in time", a concept which doesn't exist
> > yet in C.  The obvious choice is of course observable behaviour in the
> > execution environment and its specified ordering from the abstract
> > machine, as clarified via sequence points.  With that your "at the point
> > in time" becomes something like "after all side effects of previous
> > sequence point, but strictly before all side effects of next sequence
> > point".
> > 
> > But doing that would have very far reaching consequences, as already
> > stated in this thread.  The above would basically make undefined behaviour
> > be reliably countable, and all implementations would need to produce the
> > same counts of UB.  That in turn disables many code movement and
> > commonization transformations, e.g. this:
> > 
> > int a = ..., b = ...;
> > int x = a + b;
> > int y = a + b;
> > 
> > can't be transformed into "y = x = a + b" anymore, because the addition
> > _might_ overflow, and if it does you have two UBs originally but would
> > have one UB after.  I know that you don't want to inhibit this or similar
> > transformations, but that would be the result of making UB countable,
> > which is the result of forcing UB to happen at specific points in time.
> > So, I continue to see problems in precisely specifying what you want, _but
> > not more_.
> > 
> > I think all models in which you order the happening of UB with respect to
> > existing side effects (per abstract machine, so it includes modification
> > of objects!) have this same problem, it always becomes a side effect
> > itself (one where you don't specify what actually happens, but a side
> > effect nontheless) and hence becomes observable.
> > 
> 
> The C++ committee is currently considering this paper:
> 
> http://www.open-std.org/jtc1/sc22/wg21/docs/papers/2021/p1494r2.html
> 
> I think this explicit barrier-like solution is better than trying to use
> volatile accesses to achieve something similar.

Can you explain why?  To me a solution which would make
it "just work" (and also fixes existing code) seems 
better than letting programmers jump through even 
more hoops, especially if only difficult corner
cases are affected.


Martin


> 
> 
> > 
> > 

Re: reordering of trapping operations and volatile

[Jonathan Wakely]

On Sat, 15 Jan 2022, 09:00 Martin Uecker, <ma.uecker@gmail.com> wrote:

> Am Freitag, den 14.01.2022, 19:54 +0000 schrieb Jonathan Wakely:
> > On Fri, 14 Jan 2022, 14:17 Michael Matz via Gcc, <gcc@gcc.gnu.org>
> wrote:
> >
> > > Hello,
> > >
> > > On Thu, 13 Jan 2022, Martin Uecker wrote:
> > >
> > > > > > >  Handling all volatile accesses in the very same way would be
> > > > > > > possible but quite some work I don't see much value in.
> > > > > >
> > > > > > I see some value.
> > > > > >
> > > > > > But an alternative could be to remove volatile
> > > > > > from the observable behavior in the standard
> > > > > > or make it implementation-defined whether it
> > > > > > is observable or not.
> > > > >
> > > > > But you are actually arguing for making UB be observable
> > > >
> > > > No, I am arguing for UB not to have the power
> > > > to go back in time and change previous defined
> > > > observable behavior.
> > >
> > > But right now that's equivalent to making it observable,
> > > because we don't have any other terms than observable or
> > > undefined.  As aluded to later you would have to
> > > introduce a new concept, something pseudo-observable,
> > > which you then started doing.  So, see below.
> > >
> > > > > That's
> > > > > much different from making volatile not be
> > > > > observable anymore (which  obviously would
> > > > > be a bad idea), and is also much harder to
> > > >
> > > > I tend to agree that volatile should be
> > > > considered observable. But volatile is
> > > > a bit implementation-defined anyway, so this
> > > > would be a compromise so that implementations
> > > > do not have to make all the implied changes
> > > > if we revise the meaning of UB.
> > >
> > > Using volatile accesses for memory mapped IO is a much stronger
> use-case
> > > than your wish of using volatile accesses to block moving of UB as a
> > > debugging aid, and the former absolutely needs some guarantees, so I
> don't
> > > think it would be a compromise at all.  Mkaing volatile not be
> observable
> > > would break the C language.
> > >
> > > > > Well, what you _actually_ want is an implied
> > > > > dependency between some UB and volatile accesses
> > > > > (and _only_ those, not e.g. with other UB), and the
> > > > > difficulty now is to define "some" and to create
> > > > > the dependency without making that specific UB
> > > > > to be properly observable.
> > > >
> > > > Yes, this is what I actually want.
> > > >
> > > > >  I think to define this
> > > > > all rigorously seems futile (you need a new
> > > > > category between observable  and UB), so it comes
> > > > > down to compiler QoI on a case by case basis.
> > > >
> > > > We would simply change UB to mean "arbitrary
> > > > behavior at the point of time the erraneous
> > > > construct is encountered at run-time"  and
> > > > not "the complete program is invalid all
> > > > together". I see no problem in specifying this
> > > > (even in a formally precise way)
> > >
> > > First you need to define "point in time", a concept which doesn't exist
> > > yet in C.  The obvious choice is of course observable behaviour in the
> > > execution environment and its specified ordering from the abstract
> > > machine, as clarified via sequence points.  With that your "at the
> point
> > > in time" becomes something like "after all side effects of previous
> > > sequence point, but strictly before all side effects of next sequence
> > > point".
> > >
> > > But doing that would have very far reaching consequences, as already
> > > stated in this thread.  The above would basically make undefined
> behaviour
> > > be reliably countable, and all implementations would need to produce
> the
> > > same counts of UB.  That in turn disables many code movement and
> > > commonization transformations, e.g. this:
> > >
> > > int a = ..., b = ...;
> > > int x = a + b;
> > > int y = a + b;
> > >
> > > can't be transformed into "y = x = a + b" anymore, because the addition
> > > _might_ overflow, and if it does you have two UBs originally but would
> > > have one UB after.  I know that you don't want to inhibit this or
> similar
> > > transformations, but that would be the result of making UB countable,
> > > which is the result of forcing UB to happen at specific points in time.
> > > So, I continue to see problems in precisely specifying what you want,
> _but
> > > not more_.
> > >
> > > I think all models in which you order the happening of UB with respect
> to
> > > existing side effects (per abstract machine, so it includes
> modification
> > > of objects!) have this same problem, it always becomes a side effect
> > > itself (one where you don't specify what actually happens, but a side
> > > effect nontheless) and hence becomes observable.
> > >
> >
> > The C++ committee is currently considering this paper:
> >
> > http://www.open-std.org/jtc1/sc22/wg21/docs/papers/2021/p1494r2.html
> >
> > I think this explicit barrier-like solution is better than trying to use
> > volatile accesses to achieve something similar.
>
> Can you explain why?  To me a solution which would make
> it "just work" (and also fixes existing code) seems
> better than letting programmers jump through even
> more hoops, especially if only difficult corner
> cases are affected.
>

Because it interferes with existing optimisations. An explicit checkpoint
has a clear meaning. Using every volatile access that way will hurt
performance of code that doesn't require that behaviour for correctness.




>
> Martin
>
>
> >
> >
> > >
> > >
>
>

Re: reordering of trapping operations and volatile

[Martin Uecker]

Am Samstag, den 15.01.2022, 16:33 +0000 schrieb Jonathan Wakely:
> On Sat, 15 Jan 2022, 09:00 Martin Uecker, <ma.uecker@gmail.com> wrote:
> 
> > Am Freitag, den 14.01.2022, 19:54 +0000 schrieb Jonathan Wakely:
> > > On Fri, 14 Jan 2022, 14:17 Michael Matz via Gcc, <gcc@gcc.gnu.org>
> > wrote:
> > > > Hello,
> > > > 
> > > > On Thu, 13 Jan 2022, Martin Uecker wrote:
> > > > 
> > > > > > > >  Handling all volatile accesses in the very same way would be
> > > > > > > > possible but quite some work I don't see much value in.
> > > > > > > 
> > > > > > > I see some value.
> > > > > > > 
> > > > > > > But an alternative could be to remove volatile
> > > > > > > from the observable behavior in the standard
> > > > > > > or make it implementation-defined whether it
> > > > > > > is observable or not.
> > > > > > 
> > > > > > But you are actually arguing for making UB be observable
> > > > > 
> > > > > No, I am arguing for UB not to have the power
> > > > > to go back in time and change previous defined
> > > > > observable behavior.
> > > > 
> > > > But right now that's equivalent to making it observable,
> > > > because we don't have any other terms than observable or
> > > > undefined.  As aluded to later you would have to
> > > > introduce a new concept, something pseudo-observable,
> > > > which you then started doing.  So, see below.
> > > > 
> > > > > > That's
> > > > > > much different from making volatile not be
> > > > > > observable anymore (which  obviously would
> > > > > > be a bad idea), and is also much harder to
> > > > > 
> > > > > I tend to agree that volatile should be
> > > > > considered observable. But volatile is
> > > > > a bit implementation-defined anyway, so this
> > > > > would be a compromise so that implementations
> > > > > do not have to make all the implied changes
> > > > > if we revise the meaning of UB.
> > > > 
> > > > Using volatile accesses for memory mapped IO is a much stronger
> > use-case
> > > > than your wish of using volatile accesses to block moving of UB as a
> > > > debugging aid, and the former absolutely needs some guarantees, so I
> > don't
> > > > think it would be a compromise at all.  Mkaing volatile not be
> > observable
> > > > would break the C language.
> > > > 
> > > > > > Well, what you _actually_ want is an implied
> > > > > > dependency between some UB and volatile accesses
> > > > > > (and _only_ those, not e.g. with other UB), and the
> > > > > > difficulty now is to define "some" and to create
> > > > > > the dependency without making that specific UB
> > > > > > to be properly observable.
> > > > > 
> > > > > Yes, this is what I actually want.
> > > > > 
> > > > > >  I think to define this
> > > > > > all rigorously seems futile (you need a new
> > > > > > category between observable  and UB), so it comes
> > > > > > down to compiler QoI on a case by case basis.
> > > > > 
> > > > > We would simply change UB to mean "arbitrary
> > > > > behavior at the point of time the erraneous
> > > > > construct is encountered at run-time"  and
> > > > > not "the complete program is invalid all
> > > > > together". I see no problem in specifying this
> > > > > (even in a formally precise way)
> > > > 
> > > > First you need to define "point in time", a concept which doesn't exist
> > > > yet in C.  The obvious choice is of course observable behaviour in the
> > > > execution environment and its specified ordering from the abstract
> > > > machine, as clarified via sequence points.  With that your "at the
> > point
> > > > in time" becomes something like "after all side effects of previous
> > > > sequence point, but strictly before all side effects of next sequence
> > > > point".
> > > > 
> > > > But doing that would have very far reaching consequences, as already
> > > > stated in this thread.  The above would basically make undefined
> > behaviour
> > > > be reliably countable, and all implementations would need to produce
> > the
> > > > same counts of UB.  That in turn disables many code movement and
> > > > commonization transformations, e.g. this:
> > > > 
> > > > int a = ..., b = ...;
> > > > int x = a + b;
> > > > int y = a + b;
> > > > 
> > > > can't be transformed into "y = x = a + b" anymore, because the addition
> > > > _might_ overflow, and if it does you have two UBs originally but would
> > > > have one UB after.  I know that you don't want to inhibit this or
> > similar
> > > > transformations, but that would be the result of making UB countable,
> > > > which is the result of forcing UB to happen at specific points in time.
> > > > So, I continue to see problems in precisely specifying what you want,
> > _but
> > > > not more_.
> > > > 
> > > > I think all models in which you order the happening of UB with respect
> > to
> > > > existing side effects (per abstract machine, so it includes
> > modification
> > > > of objects!) have this same problem, it always becomes a side effect
> > > > itself (one where you don't specify what actually happens, but a side
> > > > effect nontheless) and hence becomes observable.
> > > > 
> > > 
> > > The C++ committee is currently considering this paper:
> > > 
> > > http://www.open-std.org/jtc1/sc22/wg21/docs/papers/2021/p1494r2.html
> > > 
> > > I think this explicit barrier-like solution is better than trying to use
> > > volatile accesses to achieve something similar.
> > 
> > Can you explain why?  To me a solution which would make
> > it "just work" (and also fixes existing code) seems
> > better than letting programmers jump through even
> > more hoops, especially if only difficult corner
> > cases are affected.
> > 
> 
> Because it interferes with existing optimisations. An explicit checkpoint
> has a clear meaning. Using every volatile access that way will hurt
> performance of code that doesn't require that behaviour for correctness.

This is why I would like to understand better
what real use cases of performance sensitive code
actually make use of volatile and are negatively
affected. Then one could discuss the tradeoffs.

Martin

Re: reordering of trapping operations and volatile

[Martin Sebor]

On 1/14/22 07:58, Paul Koning via Gcc wrote:
> 
> 
>> On Jan 14, 2022, at 9:15 AM, Michael Matz via Gcc <gcc@gcc.gnu.org> wrote:
>>
>> Hello,
>>
>> On Thu, 13 Jan 2022, Martin Uecker wrote:
>>
>>>>>> Handling all volatile accesses in the very same way would be
>>>>>> possible but quite some work I don't see much value in.
>>>>>
>>>>> I see some value.
>>>>>
>>>>> But an alternative could be to remove volatile
>>>>> from the observable behavior in the standard
>>>>> or make it implementation-defined whether it
>>>>> is observable or not.
>>>>
>>>> But you are actually arguing for making UB be observable
>>>
>>> No, I am arguing for UB not to have the power
>>> to go back in time and change previous defined
>>> observable behavior.
>>
>> But right now that's equivalent to making it observable,
>> because we don't have any other terms than observable or
>> undefined.  As aluded to later you would have to
>> introduce a new concept, something pseudo-observable,
>> which you then started doing.  So, see below.
> 
> I find it really hard to view this notion of doing work for UB with any favor.  The way I see it is that a program having UB is synonymous with "defective program" and for the compiler to do extra work for these doesn't make much sense to me.

This is also the official position of the C committee on record,
but it's one that's now being challenged.

> 
> If the issue is specifically the handling of overflow traps, perhaps a better answer would be to argue for language changes that manage such events explicitly rather than having them be undefined behavior.  Another (similar) option might be to choose a language in which this is done.  (Is Ada such a language?  I don't remember.)

A change to the language standard is only feasible if it doesn't
overly constrain existing implementations.  The impetus for Martin's
question here is to try to understand the impact on GCC.  Of course,
GCC is just one of many C implementations, and WG14 has only a very
limited visibility into existing compilers.  As a result, even if
GCC were not to be impacted by a change here, imposing requirements
that might have an adverse effect on other implementations isn't
likely to gain enough support.

Martin

Re: reordering of trapping operations and volatile

[Paul Koning]

> On Jan 15, 2022, at 4:28 PM, Martin Sebor <msebor@gmail.com> wrote:
> 
> On 1/14/22 07:58, Paul Koning via Gcc wrote:
>>> On Jan 14, 2022, at 9:15 AM, Michael Matz via Gcc <gcc@gcc.gnu.org> wrote:
>>> 
>>>> ...
>>> But right now that's equivalent to making it observable,
>>> because we don't have any other terms than observable or
>>> undefined.  As aluded to later you would have to
>>> introduce a new concept, something pseudo-observable,
>>> which you then started doing.  So, see below.
>> I find it really hard to view this notion of doing work for UB with any favor.  The way I see it is that a program having UB is synonymous with "defective program" and for the compiler to do extra work for these doesn't make much sense to me.
> 
> This is also the official position of the C committee on record,
> but it's one that's now being challenged.
> 
>> If the issue is specifically the handling of overflow traps, perhaps a better answer would be to argue for language changes that manage such events explicitly rather than having them be undefined behavior.  Another (similar) option might be to choose a language in which this is done.  (Is Ada such a language?  I don't remember.)
> 
> A change to the language standard is only feasible if it doesn't
> overly constrain existing implementations. 

I was thinking that if a new feature is involved, rather than a new definition of behavior for existing code, it wouldn't be a constraint on existing implementations (in the sense of "what the compiler does for existing code written to the current rules").  In other words, suppose there was a concept of "trapping operations" that could be enabled by some new mechanism in the program text.  If you use that, then you're asking the compiler to do more work and your code may get slower or bigger.  But if you don't, the existing rules apply and nothing bad happens (other than that the compiler is somewhat larger and more complex due to the support for both cases).

	paul

Re: reordering of trapping operations and volatile

[Martin Uecker]

Am Samstag, den 15.01.2022, 16:38 -0500 schrieb Paul Koning:
> > On Jan 15, 2022, at 4:28 PM, Martin Sebor <msebor@gmail.com> wrote:
> > 
> > On 1/14/22 07:58, Paul Koning via Gcc wrote:
> > > > On Jan 14, 2022, at 9:15 AM, Michael Matz via Gcc <gcc@gcc.gnu.org> wrote:
> > > > 
> > > > > ...
> > > > But right now that's equivalent to making it observable,
> > > > because we don't have any other terms than observable or
> > > > undefined.  As aluded to later you would have to
> > > > introduce a new concept, something pseudo-observable,
> > > > which you then started doing.  So, see below.
> > > I find it really hard to view this notion of doing work for UB with any favor.  The way I see
> > > it is that a program having UB is synonymous with "defective program" and for the compiler to
> > > do extra work for these doesn't make much sense to me.
> > 
> > This is also the official position of the C committee on record,
> > but it's one that's now being challenged.

"nonportable or erroneous" is the official position.

> > > If the issue is specifically the handling of overflow traps, perhaps a better answer would be
> > > to argue for language changes that manage such events explicitly rather than having them be
> > > undefined behavior.  Another (similar) option might be to choose a language in which this is
> > > done.  (Is Ada such a language?  I don't remember.)
> > 
> > A change to the language standard is only feasible if it doesn't
> > overly constrain existing implementations. 
> 
> I was thinking that if a new feature is involved, rather than a new definition of behavior for
> existing code, it wouldn't be a constraint on existing implementations (in the sense of "what the
> compiler does for existing code written to the current rules").  In other words, suppose there was
> a concept of "trapping operations" that could be enabled by some new mechanism in the program
> text.  If you use that, then you're asking the compiler to do more work and your code may get
> slower or bigger.  But if you don't, the existing rules apply and nothing bad happens (other than
> that the compiler is somewhat larger and more complex due to the support for both cases).

There are also different proposal for doing something like this,
e.g. making certain undefined behaviour defined as trapping
operations, either as a language variant or by default.

But this is not my idea here, I want to limit the impact of UB
on defective programs - accepting the reality that in the real
world programs often have defects and any serious field of 
engineering needs to deal with this in a better way than to
say "the ISO standard says no requirements - so you loose".

Imagine an aurospace, biomedical, mechanical, or civil engineer
saying: " It makes no sense to consider for the case where one
part fails, this is then just then a defective
airplane/CT scanner/car/bridge.  Not worth spending extra
resources on it, and a non-defective airplane might potentially
be a little bit slower if we were to give you some guarantees
in this failure case. First you need to show that this has no
performance impact at all to anybody anywhere, then maybe we
consider this." (When, at the same time there is quite
substantial damage caused by defective C programs).

I thought limiting the impact of UB on previous defined I/O
would be a rather modest step towards more reliable software,
considering that this is already the case for most I/O and
it seems only some volatile accesses would need fixing (where
I still do not see how this could affect performance anywhere
where it actually matters). 


Martin

Re: reordering of trapping operations and volatile

[Michael Matz]

Hello,

On Sat, 15 Jan 2022, Martin Uecker wrote:

> > Because it interferes with existing optimisations. An explicit 
> > checkpoint has a clear meaning. Using every volatile access that way 
> > will hurt performance of code that doesn't require that behaviour for 
> > correctness.
> 
> This is why I would like to understand better what real use cases of 
> performance sensitive code actually make use of volatile and are 
> negatively affected. Then one could discuss the tradeoffs.

But you seem to ignore whatever we say in this thread.  There are now 
multiple examples that demonstrate problems with your proposal as imagined 
(for lack of a _concrete_ proposal with wording from you), problems that 
don't involve volatile at all.  They all stem from the fact that you order 
UB with respect to all side effects (because you haven't said how you want 
to avoid such total ordering with all side effects).

As I said upthread: you need to define a concept of time at whose 
granularity you want to limit the effects of UB, and the borders of each 
time step can't simply be (all) the existing side effects.  Then you need 
to have wording of what it means for UB to occur within such time step, in 
particular if multiple UB happens within one (for best results it should 
simply be UB, not individual instances of different UBs).

If you look at the C++ proposal (thanks Jonathan) I think you will find 
that if you replace 'std::observable' with 'sequence point containing a 
volatile access' that you basically end up with what you wanted.  The 
crucial point being that the time steps (epochs in that proposal) aren't 
defined by all side effects but by a specific and explicit thing only (new 
function in the proposal, volatile accesses in an alternative).

FWIW: I think for a new language feature reusing volatile accesses as the 
clock ticks are the worse choice: if you intend that feature to be used 
for writing safer programs (a reasonable thing) I think being explicit and 
at the same time null-overhead is better (i.e. a new internal 
function/keyword/builtin, specified to have no effects except moving the 
clock forward).  volatile accesses obviously already exist and hence are 
easier to integrate into the standard, but in a given new/safe program, 
whenever you see a volatile access you would always need to ask 'is thise 
for clock ticks, or is it a "real" volatile access for memmap IO'.


Ciao,
Michael.

Re: reordering of trapping operations and volatile

[Richard Biener]

On Mon, Jan 17, 2022 at 3:11 PM Michael Matz via Gcc <gcc@gcc.gnu.org> wrote:
>
> Hello,
>
> On Sat, 15 Jan 2022, Martin Uecker wrote:
>
> > > Because it interferes with existing optimisations. An explicit
> > > checkpoint has a clear meaning. Using every volatile access that way
> > > will hurt performance of code that doesn't require that behaviour for
> > > correctness.
> >
> > This is why I would like to understand better what real use cases of
> > performance sensitive code actually make use of volatile and are
> > negatively affected. Then one could discuss the tradeoffs.
>
> But you seem to ignore whatever we say in this thread.  There are now
> multiple examples that demonstrate problems with your proposal as imagined
> (for lack of a _concrete_ proposal with wording from you), problems that
> don't involve volatile at all.  They all stem from the fact that you order
> UB with respect to all side effects (because you haven't said how you want
> to avoid such total ordering with all side effects).
>
> As I said upthread: you need to define a concept of time at whose
> granularity you want to limit the effects of UB, and the borders of each
> time step can't simply be (all) the existing side effects.  Then you need
> to have wording of what it means for UB to occur within such time step, in
> particular if multiple UB happens within one (for best results it should
> simply be UB, not individual instances of different UBs).
>
> If you look at the C++ proposal (thanks Jonathan) I think you will find
> that if you replace 'std::observable' with 'sequence point containing a
> volatile access' that you basically end up with what you wanted.  The
> crucial point being that the time steps (epochs in that proposal) aren't
> defined by all side effects but by a specific and explicit thing only (new
> function in the proposal, volatile accesses in an alternative).
>
> FWIW: I think for a new language feature reusing volatile accesses as the
> clock ticks are the worse choice: if you intend that feature to be used
> for writing safer programs (a reasonable thing) I think being explicit and
> at the same time null-overhead is better (i.e. a new internal
> function/keyword/builtin, specified to have no effects except moving the
> clock forward).  volatile accesses obviously already exist and hence are
> easier to integrate into the standard, but in a given new/safe program,
> whenever you see a volatile access you would always need to ask 'is thise
> for clock ticks, or is it a "real" volatile access for memmap IO'.

I guess Martin want's to have accesses to volatiles handled the same as
function calls where we do not know whether the function call will return
or terminate the program normally.  As if the volatile access could have
a similar effect (it might actually reboot the machine or so - but of course
that and anything else I can imagine would be far from "normal termination
of the program").  That's technically possible to implement with a yet unknown
amount of work.

Btw, I'm not sure we all agree that (*) in the following program doesn't make
it invoke UB and thus the compiler is not free to re-order the
offending statement
to before the exit (0) call.  Thus UB is only "realized" if a stmt
containing it is
executed in the abstract machine.

int main()
{
   exit(0);
   1 / 0;  /// (*)
}

>
>
> Ciao,
> Michael.

Re: reordering of trapping operations and volatile

[Martin Uecker]

Am Dienstag, den 18.01.2022, 09:31 +0100 schrieb Richard Biener:
> On Mon, Jan 17, 2022 at 3:11 PM Michael Matz via Gcc <gcc@gcc.gnu.org> wrote:
> > Hello,
> > 
> > On Sat, 15 Jan 2022, Martin Uecker wrote:
> > 
> > > > Because it interferes with existing optimisations. An explicit
> > > > checkpoint has a clear meaning. Using every volatile access that way
> > > > will hurt performance of code that doesn't require that behaviour for
> > > > correctness.
> > > 
> > > This is why I would like to understand better what real use cases of
> > > performance sensitive code actually make use of volatile and are
> > > negatively affected. Then one could discuss the tradeoffs.
> > 
> > But you seem to ignore whatever we say in this thread.  There are now
> > multiple examples that demonstrate problems with your proposal as imagined
> > (for lack of a _concrete_ proposal with wording from you), problems that
> > don't involve volatile at all.  They all stem from the fact that you order
> > UB with respect to all side effects (because you haven't said how you want
> > to avoid such total ordering with all side effects).

Again, this is simply not what I am proposing. I don't
want to order UB with all side effects.

You are right, there is not yet a specific proposal. But
at the moment I simply wanted to understand the impact of
reordering traps and volatile.

> > As I said upthread: you need to define a concept of time at whose
> > granularity you want to limit the effects of UB, and the borders of each
> > time step can't simply be (all) the existing side effects.  Then you need
> > to have wording of what it means for UB to occur within such time step, in
> > particular if multiple UB happens within one (for best results it should
> > simply be UB, not individual instances of different UBs).
> > 
> > If you look at the C++ proposal (thanks Jonathan) I think you will find
> > that if you replace 'std::observable' with 'sequence point containing a
> > volatile access' that you basically end up with what you wanted.  The
> > crucial point being that the time steps (epochs in that proposal) aren't
> > defined by all side effects but by a specific and explicit thing only (new
> > function in the proposal, volatile accesses in an alternative).
> > 
> > FWIW: I think for a new language feature reusing volatile accesses as the
> > clock ticks are the worse choice: if you intend that feature to be used
> > for writing safer programs (a reasonable thing) I think being explicit and
> > at the same time null-overhead is better (i.e. a new internal
> > function/keyword/builtin, specified to have no effects except moving the
> > clock forward).  volatile accesses obviously already exist and hence are
> > easier to integrate into the standard, but in a given new/safe program,
> > whenever you see a volatile access you would always need to ask 'is thise
> > for clock ticks, or is it a "real" volatile access for memmap IO'.
> 
> I guess Martin want's to have accesses to volatiles handled the same as
> function calls where we do not know whether the function call will return
> or terminate the program normally.  As if the volatile access could have
> a similar effect (it might actually reboot the machine or so - but of course
> that and anything else I can imagine would be far from "normal termination
> of the program").  That's technically possible to implement with a yet unknown
> amount of work.

Yes. thanks! Semantically this is equivalent to what I want.

> Btw, I'm not sure we all agree that (*) in the following program doesn't make
> it invoke UB and thus the compiler is not free to re-order the
> offending statement
> to before the exit (0) call.  Thus UB is only "realized" if a stmt
> containing it is
> executed in the abstract machine.
> 
> int main()
> {
>    exit(0);
>    1 / 0;  /// (*)
> }

Yes, this not clear although there seems to be some
understanding there is a difference between 
compile-time UB and run-time UB and I think the
standard should make it clear what is what.

Martin