Bounds check that should not be eliminated is

[Ekleog]

Originally tested with rustc 1.29.0-nightly (e94df4acb 2018-07-31). Also reproduced (for amd64, wasm didn't compile) with rustc 1.30.0-nightly (90d36fb59 2018-09-13) and rustc 1.28.0-nightly (b907d9665 2018-06-13). The details below will concern the rustc 1.29.0-nightly (e94df4acb 2018-07-31).

This issue appears to reproduce only with two crates and optimizations turned on. It may be an upstream LLVM issue, given I'm not sure whether --emit=llvm-ir already includes some LLVM-made optimizations or not. Basically, the issue is not there in --emit=mir, but is there in --emit=llvm-ir.

With the following code in crate stuff:

#![no_std]                                                              
#![feature(panic_implementation)]                                       
                                                                        
#[panic_implementation]                                                 
fn on_panic_loop(_unused: &core::panic::PanicInfo) -> ! {               
    loop {}                                                             
}                                                                       
                                                                        
mod ffi {                                                               
    extern {                                                            
        // Contract: fills buf and returns the number of bytes written  
        pub fn read(buf: *mut [u8; 255]) -> u8;                         
    }                                                                   
}                                                                       
                                                                        
#[repr(C)]                                                              
pub struct Data {                                                       
    buf: [u8; 255],                                                     
    len: u8,                                                            
}                                                                       
                                                                        
impl Data {                                                             
    pub fn new() -> Data {                                              
        unsafe {                                                        
            let mut buf = core::mem::uninitialized(); // also happens with [0; 255]
            let len = ffi::read(&mut buf);                              
            Data { buf, len }                                           
        }                                                               
    }                                                                   
                                                                        
    pub fn buf(&self) -> &[u8] {                                        
        &self.buf[..self.len as usize]                                  
    }                                                                   
}                                                                       

And the following code into the main crate (that has stuff as a dependency):

#![no_std]

extern crate stuff;

#[no_mangle]
pub extern "C" fn process() -> u32 {
    let data = stuff::Data::new();
    data.buf()[0] as u32
}

With this in the main Cargo.toml:

[profile.release]
lto = true
incremental = false
opt-level = "z"
panic = "abort"

[lib]
crate-type = ["cdylib"]

Then the following commands:

$ cargo build --target wasm32-unknown-unknown --release && wasm2wat target/wasm32-unknown-unknown/release/*.wasm
$ cargo build --release && objdump -d target/release/*.so

Both show code that has no bounds check:

$ cargo build --target wasm32-unknown-unknown --release && wasm2wat target/wasm32-unknown-unknown/release/*.wasm 
    Finished release [optimized] target(s) in 0.00s                                                                                                                                           
(module
  (type (;0;) (func (param i32) (result i32)))
  (type (;1;) (func))
  (type (;2;) (func (result i32)))
  (import "env" "read" (func $read (type 0)))
  (func $__wasm_call_ctors (type 1))
  (func $process (type 2) (result i32)
    (local i32 i32)
    get_global 0
    i32.const 256
    i32.sub
    tee_local 0
    set_global 0
    get_local 0
    i32.const 1
    i32.add
    call $read
    drop
    get_local 0
    i32.load8_u offset=1
    set_local 1
    get_local 0
    i32.const 256
    i32.add
    set_global 0
    get_local 1)
  (table (;0;) 1 1 anyfunc)
  (memory (;0;) 16)
  (global (;0;) (mut i32) (i32.const 1048576))
  (global (;1;) i32 (i32.const 1048576))
  (global (;2;) i32 (i32.const 1048576))
  (export "memory" (memory 0))
  (export "__heap_base" (global 1))
  (export "__data_end" (global 2))
  (export "process" (func $process)))
$ cargo build --release && objdump -d target/release/*.so
    Finished release [optimized] target(s) in 0.00s                                                                                                                                           
[snip]
Disassembly of section .init:
[snip]
Disassembly of section .plt.got:
[snip]
Disassembly of section .text:
[snip]
000000000000054a <process>:
 54a:	53                   	push   %rbx
 54b:	48 81 ec 00 01 00 00 	sub    $0x100,%rsp
 552:	48 8d 5c 24 01       	lea    0x1(%rsp),%rbx
 557:	48 89 df             	mov    %rbx,%rdi
 55a:	e8 f1 fe ff ff       	callq  450 <read@plt>
 55f:	0f b6 03             	movzbl (%rbx),%eax
 562:	48 81 c4 00 01 00 00 	add    $0x100,%rsp
 569:	5b                   	pop    %rbx
 56a:	c3                   	retq   

Disassembly of section .fini:
[snip]

However, I would think a bounds check is required here, in case len is actually returned as 0, as the index to 0 would otherwise read into uninitialized memory (that should be safely hidden behind the Data interface)

Do I miss something obvious?

The bounds check appears to disappear between MIR and LLVM IR:

// WARNING: This output format is intended for human consumers only
// and is subject to change without notice. Knock yourself out.
fn process() -> u32{
    let mut _0: u32;                     // return place
    scope 1 {
    }
    scope 2 {
        let _1: stuff::Data;             // "data" in scope 2 at src/lib.rs:7:9: 7:13
    }
    let mut _2: u8;
    let mut _3: &[u8];
    let mut _4: &stuff::Data;
    let mut _5: usize;
    let mut _6: usize;
    let mut _7: bool;

    bb0: {                              
        StorageLive(_1);                 // bb0[0]: scope 0 at src/lib.rs:7:9: 7:13
        _1 = const stuff::Data::new() -> bb1; // bb0[1]: scope 0 at src/lib.rs:7:16: 7:34
                                         // ty::Const
                                         // + ty: fn() -> stuff::Data {stuff::Data::new}
                                         // + val: Scalar(Bits { defined: 0, bits: 0 })
                                         // mir::Constant
                                         // + span: src/lib.rs:7:16: 7:32
                                         // + ty: fn() -> stuff::Data {stuff::Data::new}
                                         // + literal: Const { ty: fn() -> stuff::Data {stuff::Data::new}, val: Scalar(Bits { defined: 0, bits: 0 }) }
    }

    bb1: {                              
        StorageLive(_2);                 // bb1[0]: scope 1 at src/lib.rs:8:5: 8:18
        StorageLive(_3);                 // bb1[1]: scope 1 at src/lib.rs:8:5: 8:15
        StorageLive(_4);                 // bb1[2]: scope 1 at src/lib.rs:8:5: 8:9
        _4 = &_1;                        // bb1[3]: scope 1 at src/lib.rs:8:5: 8:9
        _3 = const stuff::Data::buf(move _4) -> bb2; // bb1[4]: scope 1 at src/lib.rs:8:5: 8:15
                                         // ty::Const
                                         // + ty: for<'r> fn(&'r stuff::Data) -> &'r [u8] {stuff::Data::buf}
                                         // + val: Scalar(Bits { defined: 0, bits: 0 })
                                         // mir::Constant
                                         // + span: src/lib.rs:8:5: 8:15
                                         // + ty: for<'r> fn(&'r stuff::Data) -> &'r [u8] {stuff::Data::buf}
                                         // + literal: Const { ty: for<'r> fn(&'r stuff::Data) -> &'r [u8] {stuff::Data::buf}, val: Scalar(Bits { defined: 0, bits: 0 }) }
    }

    bb2: {                              
        StorageDead(_4);                 // bb2[0]: scope 1 at src/lib.rs:8:14: 8:15
        StorageLive(_5);                 // bb2[1]: scope 1 at src/lib.rs:8:16: 8:17
        _5 = const 0usize;               // bb2[2]: scope 1 at src/lib.rs:8:16: 8:17
                                         // ty::Const
                                         // + ty: usize
                                         // + val: Scalar(Bits { defined: 64, bits: 0 })
                                         // mir::Constant
                                         // + span: src/lib.rs:8:16: 8:17
                                         // + ty: usize
                                         // + literal: Const { ty: usize, val: Scalar(Bits { defined: 64, bits: 0 }) }
        _6 = Len((*_3));                 // bb2[3]: scope 1 at src/lib.rs:8:5: 8:18
        _7 = Lt(_5, _6);                 // bb2[4]: scope 1 at src/lib.rs:8:5: 8:18
        assert(move _7, "index out of bounds: the len is move _6 but the index is _5") -> bb3; // bb2[5]: scope 1 at src/lib.rs:8:5: 8:18
    }

    bb3: {                              
        _2 = (*_3)[_5];                  // bb3[0]: scope 1 at src/lib.rs:8:5: 8:18
        _0 = move _2 as u32 (Misc);      // bb3[1]: scope 1 at src/lib.rs:8:5: 8:25
        StorageDead(_2);                 // bb3[2]: scope 1 at src/lib.rs:8:24: 8:25
        StorageDead(_1);                 // bb3[3]: scope 0 at src/lib.rs:9:1: 9:2
        StorageDead(_3);                 // bb3[4]: scope 0 at src/lib.rs:9:1: 9:2
        return;                          // bb3[5]: scope 0 at src/lib.rs:9:2: 9:2
    }
}

becomes

; Function Attrs: minsize nounwind optsize
define i32 @process() unnamed_addr #0 {
start:
  %0 = alloca [255 x i8], align 1
  %1 = getelementptr inbounds [255 x i8], [255 x i8]* %0, i64 0, i64 0
  call void @llvm.lifetime.start.p0i8(i64 255, i8* nonnull %1) #2, !noalias !574
  call void @llvm.memset.p0i8.i64(i8* nonnull align 1 %1, i8 0, i64 255, i1 false) #2, !noalias !574
  %2 = call zeroext i8 @read([255 x i8]* nonnull %0) #2, !noalias !574
  %data.sroa.0.0.copyload = load i8, i8* %1, align 1
  call void @llvm.lifetime.end.p0i8(i64 255, i8* nonnull %1) #2, !noalias !574
  %3 = zext i8 %data.sroa.0.0.copyload to i32
  ret i32 %3
}

[hanna-kruppe]

I've had a similar problem (with overflow checks instead of bounds checks) in #38136, and I suspect that this issue has the same cause: LLVM noticing (thanks to LTO) that an out of bounds index would lead to an infinite side-effect-free loop, which it considers UB (#28728) and consequently takes as justification to remove the bounds check entirely.

[Ekleog]

Hmm… At the same time, somehow I couldn't reproduce with a single crate (where it does keep the overflow check). So maybe there's something a bit more deep than that? Anyway, notifying #28728 of the issue, given no one seemed to have mentioned panic_implementation there before :)

[nagisa]

Minified reproducer:

#![no_std]

#[no_mangle]
pub extern fn bar(x: &[u8; 255], y: u8) -> u8 {
    x[y as usize]
}

#[panic_handler]
fn on_panic_loop(_unused: &core::panic::PanicInfo) -> ! {
    loop {}
} 


Compile with rustc test.rs --crate-type=staticlib -Cpanic=abort -Clto -O.

[nagisa]

NB: -Clto here is only necessary for panic machinery from libcore to be inlined so that LLVM can see relation between indexing and the infinite loop.

[Ekleog]

Just coming back here, I think this should be tagged I-unsound, given it's generating unsafe code with only safe code. Especially now that panic_implementation has stabilized.

[Ekleog]

Actually nevermind, this really is a duplicate of #28728 anyway, so I guess I can close it.