On Thu, Mar 15, 2018 at 6:44 PM, Nick Lewycky <nlewycky_at_[hidden]> wrote:

>
> As-if transformations maintain the actions of the written program under
> the assumption that undefined behaviour does not occur. The two are
> fundamentally intertwined.
>
> Here's a few thought experiments: [...]
> Today, all these optimizations are justified by the fact that any attempt
> to observe the difference before and after optimization must necessarily
> execute undefined behaviour, and executing undefined behaviour is a priori
> assumed to be impossible.
>
> It's possible that there's another way to show that these and other
> optimizations are valid, but I would need to see a proposal on how to do
> that. I've tried to create one myself and failed. Frankly, I'm starting to
> believe that our current situation with UB really is the best possible
> design choice.
>

This is beautiful, by the way. Hear hear.


Can you fix this without adding a listing of CPU instructions to the
>>> language standard
>>>
>> and without fully defining it?
>>>
>>
>> I don't need to. The C++ Standard already specifies that atomic integers
>> obey the rules
>> of 2's-complement arithmetic, and it doesn't spell out what those rules
>> are.
>>
>
> I would consider it shall "obey the rules of 2's complement arithmetic" to
> be fully defined, as 1's complement machines would have to simulate 2's
> complement arithmetic. (Offhand, I think this is what happens with atomics
> today; 1's complement machines are expected to use a library call to
> implement the atomic and ensure 2's complement?)
>

This is relevant to JF's P0907R0
<http://www.open-std.org/jtc1/sc22/wg21/docs/papers/2018/p0907r0.html> (and
to my UB-preserving fork
<https://quuxplusone.github.io/draft/twosc-conservative.html> too), so I'm
curious to explore this.
What N4700 says on the subject is...

> There are specializations of the `atomic` template for the integral types
[...] `int`, [...]
>
> template<> struct atomic<*integral*> {
> [...]
> *integral* operator++() noexcept;
> *integral* operator+=(*integral*) noexcept;
> [...]
> };
>
> Descriptions are provided below only for members that differ from the
primary template.
> The following operations perform arithmetic computations. [... a table
follows; it does not include operator++ ...]
> [...]
> T fetch_*key*(T operand, memory_order order = memory_order_seq_cst)
noexcept;
> [...]
> Remarks: For signed integer types, arithmetic is defined to use two's
complement representation. There are no undefined results.
>
> T operator *op*=(T operand) noexcept;
> Effects: Equivalent to: return fetch_*key*(operand) *op* operand;

So, first of all, there's no official semantics provided for e.g.
    std::atomic<int> x(42);
    ++x;
But we can intuitively assume that `++x` should be equivalent to `x+=1`,
and move on from there.
`x+=1` is officially defined to be equivalent to `x.fetch_add(1) + 1`.

Now things start breaking down, on non-two's-complement machines. We have
to somehow make `x.fetch_add(1)` perform an operation which is equivalent
to a "two's complement" addition, i.e., it needs to modify the bitwise
representation of `x` in some way that corresponds to a two's-complement
increment.
    std::atomic<int> y(INT_MAX); // for the sake of argument, let's use a
16-bit sign-magnitude machine
    y+=1;
    y+=1;
This means that if we have the bit-pattern 0x7FFF (a 16-bit INT_MAX),
incrementing it *must* produce the bit-pattern 0x8000, because that's what
a two's complement addition would produce.
And then we do the second `+=`. It adds 1 to the bit-pattern 0x8000 and
stores 0x8001 safely back into it.
But look at the return type of `y.fetch_add(1)`! It is specified to return
*integral*, i.e. int, i.e. it will return 0x8000, which is "negative zero"
on this machine.
And then operator+= is specified to behave as-if `y.fetch_add(1) + 1`!
So we have "negative zero" 0x8000, and we're trying to "+1" to it, in the
native ones'-complement arithmetic. If negative zero is a trap
representation, we will get a trap. Otherwise, we will observe that
"INT_MAX plus 1 plus 1" is "negative zero plus 1" is int(1) — anyway, it is
certainly not INT_MIN as we were naively hoping!

The (intermediate) result is that atomics do not visibly behave in a
two's-complement manner on a ones'-complement machine.

Now let's do the same operation on a two's-complement machine.

    std::atomic<int> y(INT_MAX);
    y+=1;

We add 1 to the bit-pattern 0x7FFF and store 0x8000 safely back into it.
But look at the return type of `y.fetch_add(1)`! It is specified to return
*integral*, i.e. int, i.e. it will return 0x7FFF, which is INT_MAX on this
machine.
And then operator+= is specified to behave as-if `y.fetch_add(1) + 1`!
So we have "INT_MAX" 0x7FFF, and we're trying to "+1" to it, in the native
arithmetic. If overflow checking is enabled, we will get a trap. In
general, we have undefined behavior here. (That is, fetch_add has defined
behavior on overflow, but operator+= has undefined behavior on overflow.)

The (ultimate) result is that atomics do not visibly behave in a
two's-complement manner even on a *two's*-complement machine.

Now, I don't think this is fatal to C++. I think this is fatal to *platforms
attempting to implement a dialect of C++ where native `int` has an
arithmetic other than two's complement*. I strongly support the idea of
dropping <https://quuxplusone.github.io/draft/twosc-conservative.html>
non-two's-complement arithmetic from C++ altogether. (And, incidentally,
the wording for atomics is broken as demonstrated above; but that's a
separate issue IMHO.)

–Arthur