Shl/Shr should throw UB on too large shift

[RalfJung]

The LLVM docs for shl say

If op2 is (statically or dynamically) equal to or larger than the number of bits in op1, this instruction returns a poison value.

However, the CTFE/Miri implementation of shl/shr currently just truncates the shift amount. In rustc-generated MIR this can never happen since there always is a check being emitted, but we should still make sure to implement all UB checks for this operation correctly -- and the simd_shl intrinsic also exposes direct access to this operation, making it possible to trigger this UB. (I plan to add tests for this.)

I just hope we didn't miss any other MIR operations which compile ti LLVM arithmetic operations that can produce poison/undef/UB... (we do check for div-by-zero, of course). Cc @rust-lang/wg-llvm

[nagisa]

To my knowledge Div, Rem and the two shifts are the only MIR-native operations that have validity invariants. We also have unchecked methods for various operations, including those same shifts which expose these invariants to the users.

[bjorn3]

In rustc-generated MIR this can never happen since there always is a check being emitted

It can with -Zforce-overflow=checks=no. The shift amounts need to be truncated in that case: https://github.com/rust-lang/rust/blob/22c2d9ddbf356bcdb718e88ca6ee3665e1e42690/src/test/ui/mir/mir_overflow_off.rs#L2

[RalfJung]

We also have unchecked methods for various operations, including those same shifts which expose these invariants to the users.

Miri currently implements those by executing the MIR operation and then raising UB if an overflow is indicated.
For div and rem, AFAIK the unchecked intrinsics have a different validity invariant than the MIR-native operations: unchecked_div also makes overflow UB, such as in int_min / -1.

It can with -Zforce-overflow=checks=no. The shift amounts need to be truncated in that case

I assume truncation is happening as explicit MIR operation then (like the div-by-zero checks) -- or do the codegen backends implicitly insert truncation?

[bjorn3]

I assume truncation is happening as explicit MIR operation then (like the div-by-zero checks) -- or do the codegen backends implicitly insert truncation?

It is implicitly added.

pub fn foo(shift_amount: u8) -> bool {
    if 1 << shift_amount != 2_u8 {
        return false;
    }
    if 2 >> shift_amount != 1_u8 {
        return false;
    }
    true
}

gives the following MIR with -Zforce-overflow-checks=no:

fn foo(_1: u8) -> bool {
    debug shift_amount => _1;            // in scope 0 at /app/example.rs:1:12: 1:24
    let mut _0: bool;                    // return place in scope 0 at /app/example.rs:1:33: 1:37
    let mut _2: u8;                      // in scope 0 at /app/example.rs:2:8: 2:25
    let mut _3: u8;                      // in scope 0 at /app/example.rs:2:13: 2:25
    let mut _4: u8;                      // in scope 0 at /app/example.rs:5:8: 5:25
    let mut _5: u8;                      // in scope 0 at /app/example.rs:5:13: 5:25

    bb0: {
        _3 = _1;                         // scope 0 at /app/example.rs:2:13: 2:25
        _2 = Shl(const 1_u8, move _3);   // scope 0 at /app/example.rs:2:8: 2:25
        switchInt(move _2) -> [2_u8: bb2, otherwise: bb1]; // scope 0 at /app/example.rs:2:8: 2:33
    }

    bb1: {
        _0 = const false;                // scope 0 at /app/example.rs:3:16: 3:21
        goto -> bb5;                     // scope 0 at no-location
    }

    bb2: {
        _5 = _1;                         // scope 0 at /app/example.rs:5:13: 5:25
        _4 = Shr(const 2_u8, move _5);   // scope 0 at /app/example.rs:5:8: 5:25
        switchInt(move _4) -> [1_u8: bb4, otherwise: bb3]; // scope 0 at /app/example.rs:5:8: 5:33
    }

    bb3: {
        _0 = const false;                // scope 0 at /app/example.rs:6:16: 6:21
        goto -> bb5;                     // scope 0 at no-location
    }

    bb4: {
        _0 = const true;                 // scope 0 at /app/example.rs:8:5: 8:9
        goto -> bb5;                     // scope 0 at /app/example.rs:9:2: 9:2
    }

    bb5: {
        return;                          // scope 0 at /app/example.rs:9:2: 9:2
    }
}

The reason I know about this test in the first place is because it used to fail with cg_clif due to incorrectly implementing this truncating behavior.

[RalfJung]

So from that it seems like Miri is doing the right thing already -- but I can't find the code in the LLVM backend that does this truncation. Here it looks like it is just constructing a single Shl for the MIR binop.

[bjorn3]

The masking is done in cg_ssa: https://github.com/rust-lang/rust/blob/a3b9405ae7bb6ab4e8103b414e75c44598a10fd2/compiler/rustc_codegen_ssa/src/common.rs#L131-L158

[RalfJung]

Ah, there it is, thanks! I will add a comment in the Miri/CTFE code explaining this.

I assume the simd shift intrinsics directly use the underlying LLVM operation though, and thus do not implicitly truncate and do require a UB check here... so our SIMD operations are inconsistent with our MIR operations. :/

[bjorn3]

Indeed. It directly exposes the LLVM operation.

#![feature(platform_intrinsics, repr_simd)]

extern "platform-intrinsic" {
    fn simd_shl<T>(a: T, amount: T) -> T;
}

#[repr(simd)]
#[derive(Copy, Clone)]
pub struct u8x8([u8; 8]);

pub fn foo(a: u8x8) -> u8x8 {
    unsafe {
        simd_shl(a, a)
    }
}

define void @_ZN7example3foo17he8b5d79f940e09f4E(<8 x i8>* noalias nocapture sret(<8 x i8>) dereferenceable(8) %0, <8 x i8>* noalias nocapture dereferenceable(8) %a) unnamed_addr #0 !dbg !6 {
  %_2 = load <8 x i8>, <8 x i8>* %a, align 8, !dbg !10
  %_3 = load <8 x i8>, <8 x i8>* %a, align 8, !dbg !11
  %1 = shl <8 x i8> %_2, %_3, !dbg !12
  store <8 x i8> %1, <8 x i8>* %0, align 8, !dbg !12
  br label %bb1, !dbg !12

bb1:                                              ; preds = %start
  ret void, !dbg !13
}

[RalfJung]

Okay, that is good to know. Cc @workingjubilee this might be interesting to know for the SIMD folks, though I am not sure if you want to change anything here -- the SIMD shift intrinsics are not consistent with the MIR shift primitives. This will require extra care in a Miri implementation of those intrinsics, and could also be potentially confusing for other codegen backends.

AFAIK shifts are the only MIR operators that does not directly correspond to an LLVM primitive, so I hope this is the only SIMD vs MIR inconsistency.

[oli-obk]

Since all backends need to do the truncation, how about we make it explicit in MIR and stop doing it in the backends?

[RalfJung]

So basically, we'd make too large shifts UB in the MIR -- seems fine to me, if someone wants to push through that change.

[bjorn3]

In Cranelift ishl/ushr/sshr are specified as masking themself. (Cranelift tries to avoid UB as much as possible.) Adding the masking at MIR level would result in two maskings for cg_clif.

[oli-obk]

OK then let's proceed with keeping the masking in the backends and just documenting this

[RalfJung]

That could also be handled by an optimization in cranelift though.

No strong opinion here, but it would be nice to make the MIR binops and SIMD intrinsics consistent (and that seems to be true for any backend that plans to implement simd_shl/shr).