Inneficient code generation for array xor'ing

[newpavlov]

The following functions:

pub fn xor_in_place(a: &mut [u8; 16], b: &[u8; 16]) {
    for (b1, b2) in a.iter_mut().zip(b.iter()) {
        *b1 ^= *b2;
    }
}

pub fn xor_in_place2(a: &mut [u8; 16], b: &[u8; 16]) {
    for i in 0..16 {
        a[i] ^= b[i];
    }
}

Produce the following ineffective assembly (with -O):

Click to expand

  mov al, byte ptr [rsi]
  xor byte ptr [rdi], al
  mov al, byte ptr [rsi + 1]
  xor byte ptr [rdi + 1], al
  mov al, byte ptr [rsi + 2]
  xor byte ptr [rdi + 2], al
  mov al, byte ptr [rsi + 3]
  xor byte ptr [rdi + 3], al
  mov al, byte ptr [rsi + 4]
  xor byte ptr [rdi + 4], al
  mov al, byte ptr [rsi + 5]
  xor byte ptr [rdi + 5], al
  mov al, byte ptr [rsi + 6]
  xor byte ptr [rdi + 6], al
  mov al, byte ptr [rsi + 7]
  xor byte ptr [rdi + 7], al
  mov al, byte ptr [rsi + 8]
  xor byte ptr [rdi + 8], al
  mov al, byte ptr [rsi + 9]
  xor byte ptr [rdi + 9], al
  mov al, byte ptr [rsi + 10]
  xor byte ptr [rdi + 10], al
  mov al, byte ptr [rsi + 11]
  xor byte ptr [rdi + 11], al
  mov al, byte ptr [rsi + 12]
  xor byte ptr [rdi + 12], al
  mov al, byte ptr [rsi + 13]
  xor byte ptr [rdi + 13], al
  mov al, byte ptr [rsi + 14]
  xor byte ptr [rdi + 14], al
  mov al, byte ptr [rsi + 15]
  xor byte ptr [rdi + 15], al

Instead of using movups and pxor.

Meanwhile if we pass slices as arguments function gets vectorized:

pub fn xor_in_place(a: &mut [u8], b: &[u8]) {
    for (b1, b2) in a.iter_mut().zip(b.iter()) {
        *b1 ^= *b2;
    }
}

Click to expand

  movups xmm0, xmmword ptr [rdx]
  movups xmm1, xmmword ptr [rdx + 16]
  movups xmm2, xmmword ptr [rdi]
  movups xmm3, xmmword ptr [rdi + 16]
  xorps xmm2, xmm0
  xorps xmm3, xmm1
  movups xmmword ptr [rdi], xmm2
  movups xmmword ptr [rdi + 16], xmm3
  mov r9d, 32

UPD: See also this comment.

[kennytm]

No repro when using -Copt-level=3

example::xor_in_place:
        push    rbp
        mov     rbp, rsp
        movups  xmm0, xmmword ptr [rsi]
        movups  xmm1, xmmword ptr [rdi]
        xorps   xmm1, xmm0
        movups  xmmword ptr [rdi], xmm1
        pop     rbp
        ret

example::xor_in_place2:
        push    rbp
        mov     rbp, rsp
        movups  xmm0, xmmword ptr [rsi]
        movups  xmm1, xmmword ptr [rdi]
        xorps   xmm1, xmm0
        movups  xmmword ptr [rdi], xmm1
        pop     rbp
        ret

[oyvindln]

Yeah, -O is equal to -C opt-level=2, so it's not the highest optimization level.

[newpavlov]

Hm, I thought -O is a default level for release builds, but I guess I was wrong. Fell free to close this issue if such behaviour for this optimisation level is considered appropriate. (Personally I don't think so)

[newpavlov]

Other example of ineffective code generation (with opt-level=3).

zip over fixed size arrays produces assembly without SIMD instructions, while explicit loop which does the same thing produces the good result. (although I am not sure why compiler generated .LBB0_7 section)

[oyvindln]

For the original example, for opt-level=2 it looks like llvm decides to completely unroll the loop in the array example before it get to the vectorization pass since it knows iteration count at compile time, while the slice one is only partially unrolled. If the optimization passes are similar to llvm's -O<n> options, the difference between 2 and 3 is the argpromotion pass. Looking at the output from llvm, the function calls where there is argument promotion in that pass are size_hint, len, eq and get_unchecked. I suspect it's the last one that makes the most difference as it looks like it helps llvm understand that the area the loads and stores access are next to each other in memory. This makes it simple to translate to vector instructions when generating the actual machine code. For opt-level=3 llvm IR output for the slice one is full of vector stuff, while for the array one there are only a few operations on an array type.

tl:dr fixed length leads to full loop unroll which stops vectorization later on opt-level=2

[newpavlov]

I've encountered even more interesting behaviour while examening the last case. While both examples are completely equivalent, looks like the second one gets compiled into a more efficient code:

pub fn square(mut buf: &mut [u8], self_buf: &[u8; 16*8]) {
  while buf.len() >= self_buf.len() {
      let (l, r) = {buf}.split_at_mut(self_buf.len());
      buf = r;
      for i in 0..16*8 { l[i] ^= self_buf[i]; }
  }
}

#[inline(always)]
fn xor(l: &mut [u8], self_buf: &[u8; 16*8]) {
  for i in 0..16*8 { l[i] ^= self_buf[i]; }
}

pub fn square(mut buf: &mut [u8], self_buf: &[u8; 16*8]) {
  while buf.len() >= self_buf.len() {
      let (l, r) = {buf}.split_at_mut(self_buf.len());
      buf = r;
      xor(l, self_buf);
  }
}

You can example assembly for them here:

1. https://godbolt.org/g/BsE6Nq
2. https://godbolt.org/g/xFHeVN

[newpavlov]

I will close this issue and will create a separate one for the latest one.