Incorrect specification of ShiftLeft Expression and ShiftRightExpression

[rcseacord]

The following specification:

6.5.6:37 If the types of both operands are integer types, then the shift left expression evaluates to the value of the left operand whose bits are shifted left by the number of positions the right operand evaluates to. Vacated bits are filled with zeros. lhs << rhs evaluates to , casted to the type of the left operand. If the value of the right operand is negative or greater than or equal to the width of the left operand, then the operation results in an arithmetic overflow.

The same problem exists in 6.5.6:42.

The issue in both cases is that these operations are specified to result in arithmetic overflow.

However, arithmetic overflow allows the following behaviors:

6.23:2There are two allowed behaviors for arithmetic overflow:

6.23:3Evaluation of the expression may result in a panic.

6.23:4The resulting value of the expression may be truncated, discarding the most significant bits that do not fit in the target type.

The first is true for Debug, but the second is not true for Release. The value of the operator expression is not truncated. Instead, in performs a masked shift using LLVM semantics, effectively:
shift_amount = right_operand % bit_width

I'm not exactly sure what the actual behavior is, but my theory is that it is implementation defined.
For example:

• left-shifting a 32-bit one by 32 bits yields 0 on ARM and PowerPC, but 1 on x86;
• left-shifting a 32-bit one by 64 bits yields 0 on ARM, but 1 on x86 and PowerPC

If it's not implementation defined, it probably should be. There is no reason to emulate portable behavior in software for such an edge case.

[rcseacord]

Also, "casted" isn't a word. Well, it is a word, but it's considered nonstandard or incorrect in formal English; the proper past tense and past participle of the irregular verb "cast" is "cast".

[traviscross]

Rust does indeed have defined behavior on integer overflow, including for overflowing shift amounts. See:

• https://doc.rust-lang.org/nightly/reference/behavior-not-considered-unsafe.html#integer-overflow
• https://doc.rust-lang.org/nightly/reference/expressions/operator-expr.html#overflow

In the case of implicitly-wrapped overflow, implementations must provide well-defined (even if still considered erroneous) results by using two's complement overflow conventions.

For this program, e.g.:

#[unsafe(no_mangle)]
pub fn f(x: u32) -> u32 {
    1u32 << x
}

We produce this LLVM IR:

define noundef range(i32 1, -2147483647) i32 @f(i32 noundef %x) unnamed_addr #0 {
start:
  %0 = and i32 %x, 31
  %_0 = shl nuw i32 1, %0
  ret i32 %_0
}

[traviscross]

Aside: If one really wants to optimize out that and, by the way, as of Rust 1.94, we'll provide unchecked_shl:

#[unsafe(no_mangle)]
/// SAFETY: Caller must guaratee `x < 32`.
pub unsafe fn f(x: u32) -> u32 {
    // SAFETY: Caller guaranteed `x < 32`.
    unsafe { 1u32.unchecked_shl(x) }
}

define noundef range(i32 1, -2147483647) i32 @f(i32 noundef %x) unnamed_addr #0 {
start:
  %_0 = shl nuw i32 1, %x
  ret i32 %_0
}

[rcseacord]

Interesting, but my point is not about overflow, but that the specification is incorrect. If the value of the right operand is negative or greater than or equal to the width of the left operand the FLS says you get arithmetic overflow. But the actual behavior for (u32)lhs << u32)rhs you pointed out above is that it computes lhs << (x & 31) (a power of 2 based on the lower 5 bits of the rhs). So this is a bug in the FLS.

In C and C++ we classify this as undefined behavior but basically do the same thing you do, except we probably just generate the instructions and let the hardware do whatever it does because it's not worth it to generate extra instructions for these nonsensical edge cases.

[traviscross]

Yes, agreed it's not specified correctly.

[traviscross]

See also:

• Basic arithmetic without overflow-checks undocumented reference#1729

[felix91gr]

Perhaps the current behavior comes from RFC 560?

It seems to describe verbatim what happens today (at least up to what Robert and I have been able to test):

Shift operations (<<, >>) on a value of width N can be passed a shift value >= N. It is unclear what behaviour should result from this, so the shift value is unconditionally masked to be modulo N to ensure that the argument is always in range.

---

Also funny (in a sad way) how this became true (from the Drawbacks section):

Divergence of debug and optimized code. The proposal here causes additional divergence of debug and optimized code, since optimized code will not include overflow checking.

[felix91gr]

Here's a more detailed analysis of what the shift operation does.

So what it seems to be doing is precisely what RFC 560 suggested:

the shift value is unconditionally masked to be modulo N to ensure that the argument is always in range.

i.e., when shifting between 2 elements of type uN, we first do

rhs = rhs % 2^N,

which in this case is the same as

rhs = rhs & (2^N - 1).

In this case, since this operations is being done at the LLVM IR, I believe the behavior is at least consistent across all platforms.

Well, all platforms that depend on the LLVM backend.

I've still left to check whether or not it's true for all backends. I'll get back to you on that, @rcseacord

[felix91gr]

Okay, I have compiled the same snippet with the Cranelift backend. Below is the optimized low-level IR that it generates from my machine. I'm asking around to figure out if this IR generation is platform-independent. It might not be, but for now... here's what I found out Cranelift does for each one of the functions:

• f3:

  pushq   %rbp
  unwind PushFrameRegs { offset_upward_to_caller_sp: 16 }
  movq    %rsp, %rbp
  unwind DefineNewFrame { offset_upward_to_caller_sp: 16, offset_downward_to_clobbers: 0 }
block0:
  jmp     label1
block1:
  movq    %rsi, %rcx
  andq    %rcx, $7, %rcx
  movq    %rdi, %rax
  shlb    %cl, %al, %al
  movq    %rbp, %rsp
  popq    %rbp
  ret

We can see here that the rhs operand (in this case addressed as %rcx) is being truncated by doing rhs & 7. This reflects how LLVM compiled f3.

Note: the other functions, up to f6, all have the same 6 lines, and they only differ in the scope of block1. So I'm going to elide those lines from now on.

• f4:

f4 does pretty much the same thing, but the AND operation is with 15 instead, and the shlb (shift left for bytes) gets replaced by shlw (shift left for... wide ints? dunno, but it's for 16 bit integers).

This also reflects LLVM's behavior.

block1:
  movq    %rsi, %rcx
  andq    %rcx, $15, %rcx
  movq    %rdi, %rax
  shlw    %cl, %ax, %ax
  movq    %rbp, %rsp
  popq    %rbp
  ret

• f5 and f6:

These differ from the other two. See here:

f5

block1:
  movq    %rsi, %rcx
  movq    %rdi, %rax
  shll    %cl, %eax, %eax
  movq    %rbp, %rsp
  popq    %rbp
  ret

f6

block1:
  movq    %rsi, %rcx
  movq    %rdi, %rax
  shlq    %cl, %rax, %rax
  movq    %rbp, %rsp
  popq    %rbp
  ret

They, however, somehow manage to still give the same result as the LLVM backend: when I call f5(1, 32) I get back 1, and when I call f6(1, 64) I get back 1 as well. I declare myself ignorant in this matter; I have no idea how is it that this happens, though it gives out the same result as the reference compiler (which at the moment is LLVM's).

• f7

f7 does something interesting. I haven't unraveled what it does, but again, it gives me the same behavior as code compiled with the LLVM backend:

  pushq   %rbp
  unwind PushFrameRegs { offset_upward_to_caller_sp: 16 }
  movq    %rsp, %rbp
  unwind DefineNewFrame { offset_upward_to_caller_sp: 16, offset_downward_to_clobbers: 0 }
block0:
  movq    %rdx, %r10
  jmp     label1
block1:
  movq    %r10, %rcx
  movq    %rdi, %rdx
  shlq    %cl, %rdx, %rdx
  shlq    %cl, %rsi, %rsi
  movl    $64, %ecx
  movq    %r10, %r8
  subq    %rcx, %r8, %rcx
  shrq    %cl, %rdi, %rdi
  xorq    %rax, %rax, %rax
  testq   $127, %r8
  cmovzq  %rax, %rdi, %rdi
  orq     %rdi, %rsi, %rdi
  testq   $64, %r8
  cmovzq  %rdx, %rax, %rax
  cmovzq  %rdi, %rdx, %rdx
  movq    %rbp, %rsp
  popq    %rbp
  ret

I suspect this implementation is how it is because Cranelift doesn't have primitive integer types of 128 bits. This implementation is probably how it manages to do it with 64 bit ints.

---

Anyway, interesting to see it like this. So far, the Cranelift backend seems to have the same exact behavior for integer shifts as LLVM does. I'll get back to yall when I get information on how universal the generated IR is.

[felix91gr]

Thanks to its maintainer (thanks @bjorn3 🫶 ), now I know where to look for Cranelift's codegen primitives.

Turns out, yes: the shifts are masked by the size of the LHS before shifting.

[bjorn3]

shlw (shift left for... wide ints? dunno, but it's for 16 bit integers).

The w suffix in x86 assembly stands for word. The names for various sizes of values on x86 are byte (b, 8bit), word (w, 16bit), double word (d, 32bit) and quad word (q, 64bit).

I suspect this implementation is how it is because Cranelift doesn't have primitive integer types of 128 bits. This implementation is probably how it manages to do it with 64 bit ints.

Cranelift does support 128bit integers. The exact lowering of ishl.i128 is just rather big: https://github.com/bytecodealliance/wasmtime/blob/05a711f6ff5317bbc5b5268a05543719f96482d5/cranelift/codegen/src/isa/x64/lower.isle#L569-L605 It can probably be optimized to match LLVM.

[felix91gr]

Cranelift does support 128bit integers.

Oh, I don't know where I got that idea from. My bad. There's an upper bound on register width though, right? Looking at the docs, it looks like it might be 128? But I don't know if that's what that means

[bjorn3]

Yeah, Cranelift only supports up to 128bit integers, just like Rust. It has been added specifically for cg_clif.