Use SIMD to expand memchr

Quuxplusone commented 2 years ago


Bugzilla Link	PR52272
Status	NEW
Importance	P enhancement
Reported by	David Bolvansky (david.bolvansky@gmail.com)
Reported on	2021-10-23 09:04:54 -0700
Last modified on	2021-10-23 10:49:40 -0700
Version	trunk
Hardware	PC Windows NT
CC	craig.topper@gmail.com, llvm-bugs@lists.llvm.org, llvm-dev@redking.me.uk, pengfei.wang@intel.com, spatel+llvm@rotateright.com
Fixed by commit(s)
Attachments
Blocks
Blocked by
See also	PR52271

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?

Quuxplusone 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.

Quuxplusone 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 .. ?

Quuxplusone / LLVMBugzillaTest

Use SIMD to expand memchr #51239