[X86][SSE] Improve general memcmp support

[RKSimon]

Bugzilla Link	33329
Version	trunk
OS	Windows NT
CC	@adibiagio,@legrosbuffle,@efriedma-quic,@filcab,@rotateright,@ZviRackover

Extended Description

Currently memcmp lowers to a libcall:

int cmp16(const char *a, const char *b) {
	return __builtin_memcmp(a, b, 16);
}

cmp16(char const*, char const*):
        movl    $16, %edx
        jmp     memcmp

Which depending on the lib implementation/shim calls can be quite slow. A possible alternative would be to vectorize this, using a more complex version of what we do for 'equality' memcmp (Bug #​33325):

#include <x86intrin.h>
int cmp16(const char *a, const char *b) {
  __m128i va = _mm_loadu_si128((const __m128i*)a);
  __m128i vb = _mm_loadu_si128((const __m128i*)b);
  unsigned eq = _mm_movemask_epi8(_mm_cmpeq_epi8(va, vb));

  __m128i kSign = _mm_set1_epi8(0x80);
  va = _mm_xor_si128(va, kSign);
  vb = _mm_xor_si128(vb, kSign);
  unsigned gt = _mm_movemask_epi8(_mm_cmpgt_epi8(va, vb));
  unsigned lt = _mm_movemask_epi8(_mm_cmplt_epi8(va, vb));

  unsigned cgt = __tzcnt_u32(gt);
  unsigned clt = __tzcnt_u32(lt);
  return ((eq == 0xFFFF) ? 0 : (clt - cgt));
}

clang -g0 -O3 -march=btver2

cmp16(char const*, char const*):
        vmovdqu (%rdi), %xmm0
        vmovdqu (%rsi), %xmm1
        vpcmpeqb        %xmm1, %xmm0, %xmm2
        vpmovmskb       %xmm2, %ecx
        vmovdqa .LCPI0_0(%rip), %xmm2   # xmm2 = [9259542123273814144,9259542123273814144]
        vpxor   %xmm2, %xmm0, %xmm0
        vpxor   %xmm2, %xmm1, %xmm1
        vpcmpgtb        %xmm1, %xmm0, %xmm2
        vpcmpgtb        %xmm0, %xmm1, %xmm0
        vpmovmskb       %xmm2, %eax
        vpmovmskb       %xmm0, %edx
        tzcntl  %eax, %eax
        tzcntl  %edx, %edx
        subl    %eax, %edx
        xorl    %eax, %eax
        cmpl    $65535, %ecx            # imm = 0xFFFF
        cmovnel %edx, %eax
        retq

[RKSimon]

IR implementation (cleaned up version of the SSE intrinsics implementation above):

define i32 @cmp16(i8* nocapture readonly, i8* nocapture readonly) {
  %3  = bitcast i8* %0 to <16 x i8>*
  %4  = load <16 x i8>, <16 x i8>* %3, align 1
  %5  = bitcast i8* %1 to <16 x i8>*
  %6  = load <16 x i8>, <16 x i8>* %5, align 1
  %7  = icmp eq <16 x i8> %4, %6
  %8  = icmp ugt <16 x i8> %4, %6
  %9  = icmp ugt <16 x i8> %6, %4
  %10 = bitcast <16 x i1> %7 to i16
  %11 = bitcast <16 x i1> %8 to i16
  %12 = bitcast <16 x i1> %9 to i16
  %13 = zext i16 %10 to i32
  %14 = zext i16 %11 to i32
  %15 = zext i16 %12 to i32
  %16 = tail call i32 @llvm.cttz.i32(i32 %14, i1 false)
  %17 = tail call i32 @llvm.cttz.i32(i32 %15, i1 false)
  %18 = icmp eq i32 %13, 65535
  %19 = sub nsw i32 %17, %16
  %20 = select i1 %18, i32 0, i32 %19
  ret i32 %20
}
declare i32 @llvm.cttz.i32(i32, i1)

[efriedma-quic]

See https://reviews.llvm.org/rL304313

[rotateright]

This puts us in position to allow a single-block 16-byte expansion for x86 in CGP:
https://reviews.llvm.org/rL306485

Getting from generic IR to this AVX version is a separate challenge. :)

Also, we'll either need to bypass the 16/32-byte expansion for the equality case (bug 33325) or get those cases to produce equivalent code from the CGP expansion that we currently get from the DAG.

[rotateright]

I have an alternate (scalar) memcmp16 implementation that I want to benchmark against the vector code shown in the description:

movq (%rdi), %rax   <--- load as scalars and swap everything
movq 8(%rdi), %rcx
movq (%rsi), %rdx
movq 8(%rsi), %rsi
bswapq %rax       
bswapq %rcx
bswapq %rdx
bswapq %rsi
cmpq %rcx, %rsi    
movq %rdx, %rdi
sbbq %rax, %rdi    
setb %dil           <--- is first op <u second op?
cmpq %rsi, %rcx    
sbbq %rdx, %rax     <--- is first op >u second op
movzbl %dil, %eax
sbbl $0, %eax       <--- 1, 0, -1 result
retq

The IR that produces this output is:

define i32 @memcmp16(i8* %x, i8* %y) {
  %1 = bitcast i8* %x to i128*
  %2 = bitcast i8* %y to i128*
  %3 = load i128, i128* %1
  %4 = load i128, i128* %2
  %5 = call i128 @llvm.bswap.i128(i128 %3)
  %6 = call i128 @llvm.bswap.i128(i128 %4)
  %7 = icmp ugt i128 %5, %6
  %8 = icmp ult i128 %5, %6
  %9 = zext i1 %7 to i32
  %10 = zext i1 %8 to i32
  %11 = sub i32 %9, %10
  ret i32 %11
}

[rotateright]

After benchmarking several vector and scalar variants for memcmp() 16/32 bytes on both Haswell and Jaguar, I can't find any cases where the vector version is best.

This even includes the seemingly superior memcmp() equality cases in bug 33325.

I can't explain this behavior yet. Based on the instruction timing from Agner and the CPU guides, the vector versions for equality shouldn't be timing as bad as I'm measuring. What should be ~10 cycles based on the docs appears to be at least 6-8 cycles greater than that.

Given these results, I think the best thing to do is enable general memcmp() expansion for x86 for all small sizes. This scalar code will outperform our existing vector implementations for memcmp() 16/32 equality, and it will be substantially faster than going out to the system lib (tested on macOS and Linux).

[rotateright]

memcmp test harness source

[rotateright]

asm functions for testing

[rotateright]

For reference, I've attached the simple test program that I've been using to measure the latency of the various memcmp() implementations.

I'll post the output for Haswell and Jaguar next.

[rotateright]

After hacking the test program, I've found the explanation for the poor vector perf that I was seeing.

The test program was storing the memcmp() result back into the input buffers to ensure that the CPU could not dynamically execute instructions out-of-order and thwart my attempt to calculate true latency.

But this has its own pitfall: the subsequent memcmp() load can't be serviced by the load-store forwarding buffer on Jaguar because I was using a scalar store of a single-byte and then loading a larger amount in memcmp(). That means the store has to complete to memory (L1 at least) before the load can proceed.

I'm still not sure why a vector load would have a much greater (10 cycle greater) penalty in this situation than a scalar load (on Jaguar at least; Haswell doesn't appear to have that much diff), but that's a bug in my test program. I can't imagine any real world use of memcmp() where you store the output back into the input buffer.

I'll update the test program and re-evaluate.

[rotateright]

memcmp test harness source

[rotateright]

asm functions for testing

[rotateright]

Removing the conflicting store effectively turns this into a throughput tester...but that's a better metric anyway since the only way this probably matters for perf is if it's happening a lot.

The latency difference between the inlined scalar and vector versions is small enough that I don't think we need to worry about it.

Here's some analysis of the output from the updated test program on Jaguar. First, let's look at the general memcmp() case where all bytes are equal (so we can't early exit in the scalar case), and we have close to perfect branch prediction:

scalar_64_less_branchy_mcmp16_movbe : 9.52 cycles/iter
avxcmp16_tzcnt : 14.02 cycles/iter

Note: the "less branchy" name isn't actually accurate; it trades cmov for math though. This would be the result of getting https://reviews.llvm.org/D34904 or something equivalent to happen in x86 codegen. The code that we currently produce would result in an extra 1.5 cycles/iter (not sure yet how we get half cycles, but it's repeatable). Either way, the scalar code has better throughput on Jaguar.

If the first chunk is not equal, then scalar code can exit early. In that case, we get either 9 or 10 cycles. Still better than the vector code. The only way vector would be a winner is if the branch was terribly mispredicted, but I think we have to trust the hardware.

Second, let's look at memcmp equality. We were pretty sure that the vector versions for 16 and 32 byte should be faster. Thankfully, they are...but the difference on Jaguar is only +/- 1.5 cycles:

memcmp16eq_scalar : 8.52 cycles/iter
memcmp16eq_sse : 8.01 cycles/iter

Similarly, for a 32-byte memcmp() == 0:

memcmp32eq_scalar : 11.52 cycles/iter
memcmp32eq_sse : 10.02 cycles/iter

Those are for the case where all bytes are equal, so scalar has to read them all. If we detect not-equal in the first read with correct branch prediction, the 16-byte case somehow costs an extra 0.5 cycle, but the 32-byte case gets faster as expected:

memcmp16eq_scalar : 9.05 cycles/iter
memcmp16eq_sse : 8.02 cycles/iter

memcmp32eq_scalar : 9.02 cycles/iter
memcmp32eq_sse : 10.02 cycles/iter

Results on Haswell show better throughput for all cases as expected given the wider uarch, but I reach the same conclusion: we should enable scalar memcmp expansion for all small memcmps. The existing vector code for 16 and 32 byte memcmp equality would usually be a slight winner, but it's not enough to justify holding off improvements for all of the other cases.

[rotateright]

https://reviews.llvm.org/rL308322

This allowed memcmp expansion using up to 4 scalar load-pairs (32-bytes on x86-64), but it caused a regression (bug 33914), so it got scaled back to just 2 scalar load-pairs to avoid the 24-byte case with:

https://reviews.llvm.org/rL308986

So now it seems we have to try for a vector solution again if we're going to handle larger expansions because that's what Linux does to achieve better perf on that benchmark.

Looking at the Linux implementation:
https://fossies.org/linux/glibc/sysdeps/x86_64/multiarch/memcmp-sse4.S
...shows that they use pxor+ptest to quickly check for equality and then handle inequality on a relatively slow path with scalar ops.

So I'm guessing that the EEMBC benchmark that regressed has mostly equal 24-byte buffers, otherwise we should have won using bswap/movbe. Not sure yet how to view/run that benchmark.

[rotateright]

memcmp test harness source (including misaligned and system memcmp)

[rotateright]

I've updated the test program to include the system memcmp (a stray store defeats the optimizer from zapping the entire memcmp loop) and also include misaligned accesses.

In my testing so far on Haswell and Jaguar, I see no difference for misaligned buffers. Our inlined code is also faster than a call to Linux memcmp() in all cases, so I'm still not sure why we're seeing benchmark regressions as in bug 34032.