search

llvm / llvm-project

The LLVM Project is a collection of modular and reusable compiler and toolchain technologies.
http://llvm.org
Other
27.52k stars 11.3k forks source link

Use SIMD to expand memchr #51614

Open davidbolvansky opened 2 years ago

davidbolvansky commented 2 years ago
Bugzilla Link 52272
Version trunk
OS Windows NT
CC @topperc,@RKSimon,@phoebewang,@rotateright

Extended Description

int* findK(int k, const int* v, unsigned long long n)
{
  return(int*)__builtin_memchr(v, k, 32);
}
findK(int, int const*, unsigned long long):
        mov     r8d, edi
        mov     edx, 32
        mov     rdi, rsi
        mov     esi, r8d
        jmp     memchr

Better to use SIMD than libcall for some reasonable N?

davidbolvansky commented 2 years ago

Yeah, kinda tricky, but...

https://stackoverflow.com/questions/47315902/is-it-legal-to-call-memchr-with-a-too-long-length-if-you-know-the-character-wil

but still SIMD impl. could be possible? https://sourceware.org/git/?p=glibc.git;a=blob;f=sysdeps/x86_64/memchr.S;hb=HEAD#l29

We have custom expander for SystemZ: https://github.com/llvm/llvm-project/blob/a33e4c8ae925e99e565b2ca5dcda8ec2edbb78ee/llvm/lib/Target/SystemZ/SystemZSelectionDAGInfo.cpp#L177

And isn't memcmp same story and still we have SIMD version of memcmp .. ?

RKSimon commented 2 years ago

I'm not certain when we can read beyond the first match in general terms. If we know the dereferencable range (not just the memchr count arg), we might be able to do more.

RKSimon commented 2 years ago

And isn't memcmp same story and still we have SIMD version of memcmp .. ?

From my reading of memchr's definition it says memchr must stop reading at first match, but any memcmp read within range is permitted.

https://en.cppreference.com/w/c/string/byte/memchr https://en.cppreference.com/w/c/string/byte/memcmp