Hacker News Reader

Comment by SAI_Peregrinus | Hacker News Reader

I think it means what you think is ridiculous. Shifting the sign bit out is UB. Unrepresentable results are UB.

> Shifting the sign bit out is UB

Shifting into the sign bit is also UB. Can I please have a language that actually has bitwise operators with defined semantics? No CPUs had differentiated between SAL/SHL for more than 30 years, if that was the original justification.

I'm fine with left shift trapping on overflow. I'm fine with it just wrapping around. I'm even fine with bitwise shifts simply unapplicable to ints ("cast to unsigned first, then cast back to int"). I am not fine with an operator that invokes UB for literally half of the values of the lhs's domains.

Swift: https://developer.apple.com/documentation/swift/binaryintege...

> The << operator performs a smart shift, which defines a result for a shift of any value.

> - Using a negative value for rhs performs a right shift using abs(rhs).

> - Using a value for rhs that is greater than or equal to the bit width of lhs is an overshift, resulting in zero.

> - Using any other value for rhs performs a left shift on lhs by that amount.

And while the docs don’t say it, `Int.max << 1 == -2`. And in fact, `T.max << 1 == -2` for all `T: BinaryInteger`.

That seems like an exceedingly bad thing. It means that << can't be compiled to a single instruction with single-clock throughput on x86, since shift instructions take an UNSIGNED shift count. As a further complication, x86 processors treat overshifts differently.

e.g.

   MOV AX, 1
   MOV CL, 33
   SHL AX, CL

Afterward, on an 80186, AX contains 2, since the contents of CL are treated MOD 32. The AX register gets shifted by one bit. On an 8086, AX contains zero, since the 8086 implementation shifts by one bit 33 times. (Yes, it will shift 255 times, taking 1024 CPU cycles if you tell it to do that).

Given a choice, I'd prefer performant bit-twiddling in exchange for UB in cases that never occur in practice.

It may seem like an exceedingly bad thing, but in practice most shift amounts are constants, statically known to the compiler, which makes choosing between single instruction-long sequences "shl eax/rax, <imm8>", "shr eax/rax, <imm8>", and "xor eax, eax" trivial.

But variable shifts also happen sometimes, which brings me to the next point:

> in exchange for UB in cases that never occur in practice.

It does happen, and people depend on what their platform does. That's one of the things that sunk John Regehr's proposal for "Friendly C" [0]:

    After publishing the Friendly C Proposal, I spent some time discussing its design with people,
    and eventually I came to the depressing conclusion that there’s no way to get a group of C
    experts — even if they are knowledgable, intelligent, and otherwise reasonable — to agree on
    the Friendly C dialect. There are just too many variations, each with its own set of performance
    tradeoffs, for consensus to be possible. [...] Another example is what should be done when a
    32-bit integer is shifted by 32 places (this is undefined behavior in C and C++). Stephen Canon
    pointed out on twitter that there are many programs typically compiled for ARM that would fail
    if this produced something besides 0, and there are also many programs typically compiled for
    x86 that would fail when this evaluates to something other than the original value. So what is
    the friendly thing to do here?

So. You want a modulo behaviour? Write "expr << (var & 32)" or "expr << (var & 64)", the compiler will recognize this idiom and emit a simple "mov cl, var; shl eax/rax, cl" on x64 and RISC-V, and an additional explicit AND mask on ARMs. You want an overshift? Well, that's the default semantics, and it would emit an simple shift on ARM, and "xor eax, eax; shl edx/rdx, cl; cmp ecx, 32/64; cmovb eax/rax, edx/rdx" on x64 (and something similar on RISC-V). It's your choice!

[0] https://blog.regehr.org/archives/1287

In passing, just to make things even more fun, ARM32 overshifting produces zero; ARM64 uses MODULO overshifting. :-P

I was thinking about eliminating this shift-into-left bit UB. There was a previous attempt though that failed to get consensus. (but long enough ago that one could try again).

But all this signed overflow UB can be turned into traps using sanitizers. In practice, generally mandating a trap is difficult though in ISO C. My plan is to mandate this as part of a special mode, in which case I would just leave this UB in the main standard.

(One problem we also have that some special interests groups in WG14 are rather hostile to our work and the rest of the C community - so I encourage everybody who is actually using C and caring about it to join).

> I was thinking about eliminating this shift-into-left bit UB.

At least make it "change of the sign bit is UB" — if 0 shifts into the sign-bit of a positive number, or 1 shifts into the sign-bit of a negative number, that shouldn't be UB. This would make left-shifts of negative numbers well-defined, their behaviour being that of two's complement numbers. And C23 already demands two's complement from the implementations, doesn't?

> signed overflow UB can be turned into traps using sanitizers.

Well, yeah, sure, but shifting -1 one place to the left doesn't overflow, it produces -2; only shifting INT_MIN or something up to and including INT_MIN + (INT_MAX/2) would overflow.

I agree. Thanks!

The problem is that this is different from C++, so probably we can not do the reasonable thing because it makes the "it must be exactly like C++" people upset.

Apparently, C++23 went on and fully defined it, see the sibling comment from leni536 [0]:

    1) ........................ The behavior is undefined if the right operand is negative,
    or greater than or equal to the width of the promoted left operand.

    2) The value of E1 << E2 is the unique value congruent to E1 × 2**E2 modulo 2**N, where
    N is the width of the type of the result.

    [Note 1 : E1 is left-shifted E2 bit positions; vacated bits are zero-filled. — end note]

    3) The value of E1 >> E2 is E1 / 2**E2, rounded down.

    [Note 2 : E1 is right-shifted E2 bit positions. Right-shift on signed integral types is
    an arithmetic right shift, which performs sign-extension. — end note]

So you can adopt that as well. In any case: since C23/C++23 the integers are two's complement, so make them behave so. Again, I don't mind signed overflow being undefined all that much (although again, I feel like there has to be some middle ground between "full-blown UB and nasal demons" and "the implementations/sanitiziers are allowed to trap it instead of silently wrapping/assuming it never happens") so perhaps you can slightly deviate from C++ here: it apparently allows 1 << (INT_WIDTH - 1) to become INT_MIN, fully defined-ly, maybe this can still be UB in C? But (-1) << (whatever up to INT_WIDTH - 1) absolutely should be defined, it's just ridiculous otherwise.

[0] https://news.ycombinator.com/item?id=50117296

Ah right, they had improved that. Btw: Everbody can submit proposals to WG14.

The more immediate problem is modern x86 processors have anomalous over-shift behavior, and can't do signed shift counts. On x86 (80186 and later), the shift count of SHL is UNSIGNED MODULO 32 (or MODULO 64). So the over-shift behavior MUST be UB. So any attempt to define the behavior is going to be incredibly painful, and the best one can do is make provisions for optional sanitizers in debug builds.

> Can I please have a language that actually has bitwise operators with defined semantics?

C++? It has defined semantics since C++20.

No, not really? From C++23:

    4) The result of E1 << E2 is E1 left-shifted E2 bit positions; vacated bits
    are filled with zeros. If E1 has an unsigned type, the value of the result
    is E1 × 2**E2, wrapped around. If E1 has a signed type and nonnegative value,
    and E1 × 2**E2 is representable in the result type, then that is the resulting
    value; otherwise, the behavior is undefined.

    5) The result of E1 >> E2 is E1 right-shifted E2 bit positions. If E1 has an
    unsigned type or if E1 has a signed type and a nonnegative value, the value of
    the result is the integral part of the quotient of E1 / 2**E2. If E1 has a
    signed type and a negative value, the resulting value is implementation-defined.

It's marginally more well-defined, sure, but not fully. The right shifts of negative numbers are no longer UB but are still an unportable mystery; and the left shifts of negative values are still outright UB.

Huh, I stand corrected. It is defined in the current draft though:

https://eel.is/c++draft/expr.shift

I thought this was part of the guaranteed two's complement change in C++20.

Actually, no, your copy of C++23 doesn't match mine:

https://www.open-std.org/jtc1/sc22/wg21/docs/papers/2023/n49...

This is indeed from the C++20 paper P1236R1:

https://www.open-std.org/jtc1/sc22/wg21/docs/papers/2018/p12...

Ah, I see. Those "final drafts PDFs" are a bit confusing to google, I must admit. I guess I'd better save them once locally, properly titled, and reference those copies instead?

In any case, thanks; it's nice to see C++ at least fully embracing the mandate on integers being two's complement, finally. There is enough footguns already without basic arithmetic operators being UB half of the time.

Ada?

Operations are well defined, and to do stuff like in C, you must do Unchecked_Something calls.

Reply on news.ycombinator.com