Terrible code generation with a zillion bounds checks.

[khuey]

This is probably a duplicate of something.

In psychon/x11rb#491 we have a function that looks like:

    pub fn try_parse_request(header: RequestHeader, value: &[u8]) -> Result<Self, ParseError> {
        if header.minor_opcode != LATCH_LOCK_STATE_REQUEST {
            return Err(ParseError::ParseError);
        }
        let (device_spec, remaining) = DeviceSpec::try_parse(value)?;
        let (affect_mod_locks, remaining) = u8::try_parse(remaining)?;
        let (mod_locks, remaining) = u8::try_parse(remaining)?;
        let (lock_group, remaining) = bool::try_parse(remaining)?;
        let (group_lock, remaining) = u8::try_parse(remaining)?;
        let group_lock = group_lock.try_into()?;
        let (affect_mod_latches, remaining) = u8::try_parse(remaining)?;
        let remaining = remaining.get(1..).ok_or(ParseError::InsufficientData)?;
        let remaining = remaining.get(1..).ok_or(ParseError::InsufficientData)?;
        let (latch_group, remaining) = bool::try_parse(remaining)?;
        let (group_latch, remaining) = u16::try_parse(remaining)?;
        let _ = remaining;
        Ok(LatchLockStateRequest {
            device_spec,
            affect_mod_locks,
            mod_locks,
            lock_group,
            group_lock,
            affect_mod_latches,
            latch_group,
            group_latch,
        })
    }

Basically, it takes a byte stream in a wire format and parses it into an in-memory struct.

The generated assembly looks like

_ZN5x11rb8protocol3xkb21LatchLockStateRequest17try_parse_request17hb503842b081124b2E:
        movq    %rdi, %rax
        shrq    $40, %rsi
        cmpb    $5, %sil
        jne     .LBB4888_13
        cmpq    $2, %rcx
        jb      .LBB4888_16
        je      .LBB4888_16
        cmpq    $3, %rcx
        je      .LBB4888_16
        cmpq    $4, %rcx
        je      .LBB4888_16
        cmpb    $0, 4(%rdx)
        setne   %sil
        cmpq    $5, %rcx
        je      .LBB4888_16
        movb    5(%rdx), %dil
        cmpb    $4, %dil
        jae     .LBB4888_13
        cmpq    $6, %rcx
        je      .LBB4888_16
        cmpq    $7, %rcx
        je      .LBB4888_16
        cmpq    $8, %rcx
        je      .LBB4888_16
        cmpq    $9, %rcx
        je      .LBB4888_16
        andq    $-2, %rcx
        cmpq    $10, %rcx
        jne     .LBB4888_12
.LBB4888_16:
        movb    $0, 1(%rax)
        movb    $1, %cl
        movb    %cl, (%rax)
        retq
.LBB4888_13:
        movb    $1, 1(%rax)
        movb    $1, %cl
        movb    %cl, (%rax)
        retq
.LBB4888_12:
        movzwl  (%rdx), %ecx
        movb    2(%rdx), %r8b
        movb    3(%rdx), %r9b
        movb    6(%rdx), %r10b
        cmpb    $0, 9(%rdx)
        movzwl  10(%rdx), %edx
        movw    %cx, 2(%rax)
        movw    %dx, 4(%rax)
        movb    %r8b, 6(%rax)
        movb    %r9b, 7(%rax)
        movb    %sil, 8(%rax)
        movb    %dil, 9(%rax)
        movb    %r10b, 10(%rax)
        setne   11(%rax)
        xorl    %ecx, %ecx
        movb    %cl, (%rax)
        retq

LBB4888_16 is the ParseError::InsufficientData return and LBB4888_13 is the ParseError::ParseError return.

The compiler really should be able to consolidate the adjacent bounds checks. And although much smaller, not condensing the adjacent jb/jes is a comically easy missed optimization.

Meta

rustc --version --verbose:

rustc 1.46.0-nightly (e55d3f9c5 2020-06-18)
binary: rustc
commit-hash: e55d3f9c5213fe1a25366450127bdff67ad1eca2
commit-date: 2020-06-18
host: x86_64-unknown-linux-gnu
release: 1.46.0-nightly
LLVM version: 10.0

[khuey]

I filed https://bugs.llvm.org/show_bug.cgi?id=46402

[Enselic]

Triage: Can this still be reproduced? If yes, please provide a reproducer others can run, otherwise it is more or less impossible to make progress on this issue. Thanks!

[psychon]

Here is a self-contained reproducer:

#[derive(Debug, Clone, Copy)]
pub struct RequestHeader {
    pub minor_opcode: u8,
}

#[derive(Debug, Copy, Clone, PartialEq, Eq)]
#[non_exhaustive]
pub enum ParseError {
    InsufficientData,
    ConversionFailed,
    InvalidExpression,
    InvalidValue,
    MissingFileDescriptors,
}

trait TryParse: Sized {
    fn try_parse(value: &[u8]) -> Result<(Self, &[u8]), ParseError>;
}

macro_rules! implement_try_parse {
    ($t:ty) => {
        impl TryParse for $t {
            fn try_parse(value: &[u8]) -> Result<(Self, &[u8]), ParseError> {
                let len = core::mem::size_of::<$t>();
                let bytes = value
                    .get(..len)
                    .ok_or(ParseError::InsufficientData)?
                    .try_into() // TryInto<[u8; len]>
                    .unwrap();
                Ok((<$t>::from_ne_bytes(bytes), &value[len..]))
            }
        }
    };
}

implement_try_parse!(u8);
implement_try_parse!(i8);
implement_try_parse!(u16);
implement_try_parse!(i16);
implement_try_parse!(u32);
implement_try_parse!(i32);
implement_try_parse!(u64);
implement_try_parse!(i64);

impl TryParse for bool {
    fn try_parse(value: &[u8]) -> Result<(Self, &[u8]), ParseError> {
        let (data, remaining) = u8::try_parse(value)?;
        Ok((data != 0, remaining))
    }
}

type DeviceSpec = u16;
type Group = u8;

#[derive(Debug)]
struct LatchLockStateRequest {
    device_spec: DeviceSpec,
    affect_mod_locks: u8,
    mod_locks: u8,
    lock_group: bool,
    group_lock: Group,
    affect_mod_latches: u8,
    latch_group: bool,
    group_latch: u16,
}

const LATCH_LOCK_STATE_REQUEST: u8 = 123;

impl LatchLockStateRequest {
    #[inline(never)]
    pub fn try_parse_request(header: RequestHeader, value: &[u8]) -> Result<Self, ParseError> {
        if header.minor_opcode != LATCH_LOCK_STATE_REQUEST {
            return Err(ParseError::InvalidValue);
        }
        let (device_spec, remaining) = DeviceSpec::try_parse(value)?;
        let (affect_mod_locks, remaining) = u8::try_parse(remaining)?;
        let (mod_locks, remaining) = u8::try_parse(remaining)?;
        let (lock_group, remaining) = bool::try_parse(remaining)?;
        let (group_lock, remaining) = u8::try_parse(remaining)?;
        let group_lock = group_lock; // .try_into()?;
        let (affect_mod_latches, remaining) = u8::try_parse(remaining)?;
        let remaining = remaining.get(1..).ok_or(ParseError::InsufficientData)?;
        let remaining = remaining.get(1..).ok_or(ParseError::InsufficientData)?;
        let (latch_group, remaining) = bool::try_parse(remaining)?;
        let (group_latch, remaining) = u16::try_parse(remaining)?;
        let _ = remaining;
        Ok(LatchLockStateRequest {
            device_spec,
            affect_mod_locks,
            mod_locks,
            lock_group,
            group_lock,
            affect_mod_latches,
            latch_group,
            group_latch,
        })
    }
}

fn fake_it() -> (RequestHeader, &'static [u8]) {
    let header = RequestHeader { minor_opcode: 123 };
    let data = &[];
    std::hint::black_box((header, data))
}

fn main() {
    let (header, data) = fake_it();
    println!(
        "{:?}",
        LatchLockStateRequest::try_parse_request(header, data)
    );
}

Compiling with Rust 1.94.1 and cargo build --release, then looking at objdump -S target/release/foo finds:

0000000000014a80 <_ZN3foo21LatchLockStateRequest17try_parse_request17h0a0b2e63c7405e8fE>:
   14a80:	40 80 fe 7b          	cmp    $0x7b,%sil
   14a84:	75 35                	jne    14abb <_ZN3foo21LatchLockStateRequest17try_parse_request17h0a0b2e63c7405e8fE+0x3b>
   14a86:	48 83 f9 01          	cmp    $0x1,%rcx
   14a8a:	76 26                	jbe    14ab2 <_ZN3foo21LatchLockStateRequest17try_parse_request17h0a0b2e63c7405e8fE+0x32>
   14a8c:	48 83 f9 02          	cmp    $0x2,%rcx
   14a90:	74 20                	je     14ab2 <_ZN3foo21LatchLockStateRequest17try_parse_request17h0a0b2e63c7405e8fE+0x32>
   14a92:	48 83 f9 03          	cmp    $0x3,%rcx
   14a96:	74 1a                	je     14ab2 <_ZN3foo21LatchLockStateRequest17try_parse_request17h0a0b2e63c7405e8fE+0x32>
   14a98:	48 83 f9 04          	cmp    $0x4,%rcx
   14a9c:	74 14                	je     14ab2 <_ZN3foo21LatchLockStateRequest17try_parse_request17h0a0b2e63c7405e8fE+0x32>
   14a9e:	80 7a 04 00          	cmpb   $0x0,0x4(%rdx)
   14aa2:	40 0f 95 c6          	setne  %sil
   14aa6:	48 83 f9 05          	cmp    $0x5,%rcx
   14aaa:	74 06                	je     14ab2 <_ZN3foo21LatchLockStateRequest17try_parse_request17h0a0b2e63c7405e8fE+0x32>
   14aac:	48 83 f9 06          	cmp    $0x6,%rcx
   14ab0:	75 12                	jne    14ac4 <_ZN3foo21LatchLockStateRequest17try_parse_request17h0a0b2e63c7405e8fE+0x44>
   14ab2:	c6 07 00             	movb   $0x0,(%rdi)
   14ab5:	b0 02                	mov    $0x2,%al
   14ab7:	88 47 09             	mov    %al,0x9(%rdi)
   14aba:	c3                   	ret
   14abb:	c6 07 03             	movb   $0x3,(%rdi)
   14abe:	b0 02                	mov    $0x2,%al
   14ac0:	88 47 09             	mov    %al,0x9(%rdi)
   14ac3:	c3                   	ret
   14ac4:	48 83 f9 09          	cmp    $0x9,%rcx
   14ac8:	74 e8                	je     14ab2 <_ZN3foo21LatchLockStateRequest17try_parse_request17h0a0b2e63c7405e8fE+0x32>
   14aca:	48 83 f9 08          	cmp    $0x8,%rcx
   14ace:	74 e2                	je     14ab2 <_ZN3foo21LatchLockStateRequest17try_parse_request17h0a0b2e63c7405e8fE+0x32>
   14ad0:	48 83 f9 07          	cmp    $0x7,%rcx
   14ad4:	74 dc                	je     14ab2 <_ZN3foo21LatchLockStateRequest17try_parse_request17h0a0b2e63c7405e8fE+0x32>
   14ad6:	48 b8 fe ff ff ff ff 	movabs $0x7ffffffffffffffe,%rax
   14add:	ff ff 7f 
   14ae0:	48 21 c1             	and    %rax,%rcx
   14ae3:	48 83 f9 0a          	cmp    $0xa,%rcx
   14ae7:	74 c9                	je     14ab2 <_ZN3foo21LatchLockStateRequest17try_parse_request17h0a0b2e63c7405e8fE+0x32>
   14ae9:	0f b7 0a             	movzwl (%rdx),%ecx
   14aec:	44 0f b6 42 02       	movzbl 0x2(%rdx),%r8d
   14af1:	44 0f b6 4a 03       	movzbl 0x3(%rdx),%r9d
   14af6:	44 0f b6 52 05       	movzbl 0x5(%rdx),%r10d
   14afb:	44 0f b6 5a 06       	movzbl 0x6(%rdx),%r11d
   14b00:	80 7a 09 00          	cmpb   $0x0,0x9(%rdx)
   14b04:	0f 95 c0             	setne  %al
   14b07:	0f b7 52 0a          	movzwl 0xa(%rdx),%edx
   14b0b:	66 89 0f             	mov    %cx,(%rdi)
   14b0e:	66 89 57 02          	mov    %dx,0x2(%rdi)
   14b12:	44 88 47 04          	mov    %r8b,0x4(%rdi)
   14b16:	44 88 4f 05          	mov    %r9b,0x5(%rdi)
   14b1a:	44 88 57 06          	mov    %r10b,0x6(%rdi)
   14b1e:	44 88 5f 07          	mov    %r11b,0x7(%rdi)
   14b22:	40 88 77 08          	mov    %sil,0x8(%rdi)
   14b26:	88 47 09             	mov    %al,0x9(%rdi)
   14b29:	c3                   	ret

This still has all the redundant length checks, I think. But somehow who can ready assembly better than I do can decide that.