================
@@ -55,39 +55,168 @@ LIBC_INLINE static const void
*calculate_find_first_character_return(
return src + c_offset;
}
-LIBC_NO_SANITIZE_OOB_ACCESS LIBC_INLINE static const void *
+LIBC_INLINE_VAR constexpr size_t VEC_SIZE = sizeof(cpp::simd<char>);
+LIBC_INLINE_VAR constexpr size_t LOOP_BLOCK_SIZE = 4 * VEC_SIZE;
+
+// A find_first_character implementation for inputs less than the loop block
+// size. It loads N vectors with the last end of the last vector alinging
+// with the end of the buffer passed in.
+template <size_t N>
+LIBC_NO_SANITIZE_OOB_ACCESS LIBC_ALWAYS_INLINE static const void *
+find_first_character_small(const unsigned char *s, cpp::simd<char> c,
+ size_t n) {
+ static_assert(N >= 2 && N <= 4);
+
+ const unsigned char *ptrs[N];
+ cpp::simd_mask<char> masks[N];
+ for (size_t i = 0; i < N - 1; ++i) {
+ ptrs[i] = s + i * VEC_SIZE;
+ masks[i] = cpp::load<cpp::simd<char>>(ptrs[i], /*aligned=*/false) == c;
+ }
+ ptrs[N - 1] = s + n - VEC_SIZE;
+ masks[N - 1] =
+ cpp::load<cpp::simd<char>>(ptrs[N - 1], /*aligned=*/false) == c;
+
+ cpp::simd_mask<char> combined = masks[0] | masks[1];
+ if constexpr (N == 3)
+ combined = combined | masks[2];
+ else if constexpr (N == 4)
+ combined = combined | (masks[2] | masks[3]);
+
+ if (cpp::any_of(combined)) {
+ for (size_t i = 0; i < N - 1; ++i)
+ if (cpp::any_of(masks[i]))
+ return ptrs[i] + cpp::find_first_set(masks[i]);
+ return ptrs[N - 1] + cpp::find_first_set(masks[N - 1]);
+ }
+ return nullptr;
+}
+
+// A find_first_character implementation for large inputs. The input is
+// expected to be aligned to LOOP_BLOCK_SIZE. There is then a loop that
+// does four VEC_SIZE loads per iteration.
+LIBC_NO_SANITIZE_OOB_ACCESS LIBC_ALWAYS_INLINE static const void *
+find_first_aligned_loop(const cpp::simd<char> *s, cpp::simd<char> c, size_t n)
{
+ LIBC_LOOP_NOUNROLL
+ for (;;) {
+ cpp::simd_mask<char> m0 =
+ cpp::load<cpp::simd<char>>(s, /*aligned=*/true) == c;
+ cpp::simd_mask<char> m1 =
+ cpp::load<cpp::simd<char>>(s + 1, /*aligned=*/true) == c;
+ cpp::simd_mask<char> m2 =
+ cpp::load<cpp::simd<char>>(s + 2, /*aligned=*/true) == c;
+ cpp::simd_mask<char> m3 =
+ cpp::load<cpp::simd<char>>(s + 3, /*aligned=*/true) == c;
+ if (LIBC_UNLIKELY(cpp::any_of((m0 | m1) | (m2 | m3)))) {
+ size_t found_offset;
+ if (cpp::any_of(m0))
+ found_offset = cpp::find_first_set(m0);
+ else if (cpp::any_of(m1))
+ found_offset = VEC_SIZE + cpp::find_first_set(m1);
+ else if (cpp::any_of(m2))
+ found_offset = 2 * VEC_SIZE + cpp::find_first_set(m2);
+ else
+ found_offset = 3 * VEC_SIZE + cpp::find_first_set(m3);
+ if (found_offset >= n)
+ return nullptr;
+ return reinterpret_cast<const char *>(s) + found_offset;
+ }
+ if (n <= LOOP_BLOCK_SIZE)
+ return nullptr;
+ s += 4;
+ n -= LOOP_BLOCK_SIZE;
+ }
+}
+
+LIBC_NO_SANITIZE_OOB_ACCESS LIBC_ALWAYS_INLINE static const void *
find_first_character(const unsigned char *s, unsigned char c, size_t n) {
// s doesn't have to be dereferenceable if there is nothing to search.
if (n == 0)
return nullptr;
- using Vector = cpp::simd<char>;
- using Mask = cpp::simd_mask<char>;
- Vector c_byte = c;
-
- size_t alignment = alignof(Vector);
- const Vector *aligned =
- reinterpret_cast<const Vector *>(__builtin_align_down(s, alignment));
-
- Vector chars = cpp::load<Vector>(aligned, /*aligned=*/true);
- Mask cmp_v = chars == c_byte;
- size_t offset = s - reinterpret_cast<const unsigned char *>(aligned);
-
- cmp_v = shift_mask<unsigned char>(cmp_v, offset);
- if (cpp::any_of(cmp_v))
- return calculate_find_first_character_return(
- reinterpret_cast<const char *>(s), cmp_v, n);
+ constexpr size_t min_page_size = 4096;
+ static_assert(cpp::has_single_bit(min_page_size) &&
+ cpp::has_single_bit(LOOP_BLOCK_SIZE) &&
+ min_page_size % LOOP_BLOCK_SIZE == 0,
+ "4x vector block must cleanly divide a page.");
+
+ cpp::simd<char> c_byte = c;
+
+ if (n <= LOOP_BLOCK_SIZE) {
+ const uintptr_t page_offset =
+ reinterpret_cast<uintptr_t>(s) & (min_page_size - 1);
+ if (LIBC_LIKELY(page_offset <= min_page_size - LOOP_BLOCK_SIZE)) {
+ if (n <= VEC_SIZE) {
+ cpp::simd_mask<char> m0 =
+ cpp::load<cpp::simd<char>>(s, /*aligned=*/false) == c_byte;
+ return cpp::any_of(m0) ? calculate_find_first_character_return(
+ reinterpret_cast<const char *>(s), m0, n)
+ : nullptr;
+ }
+ if (n <= 2 * VEC_SIZE)
+ return find_first_character_small<2>(s, c_byte, n);
+ if (n <= 3 * VEC_SIZE)
+ return find_first_character_small<3>(s, c_byte, n);
+ return find_first_character_small<4>(s, c_byte, n);
+ }
+ }
- for (size_t bytes_checked = sizeof(Vector) - offset; bytes_checked < n;
- bytes_checked += sizeof(Vector)) {
- aligned++;
- chars = cpp::load<Vector>(aligned, /*aligned=*/true);
- cmp_v = chars == c_byte;
+ const cpp::simd<char> *loop_aligned;
+ if (LOOP_BLOCK_SIZE <= 64 && n > LOOP_BLOCK_SIZE) {
+ if constexpr (LOOP_BLOCK_SIZE <= 64) {
+ // Align s down to LOOP_BLOCK_SIZE; all 4 vectors lie on the same page.
+ const cpp::simd<char> *block = reinterpret_cast<const cpp::simd<char> *>(
+ __builtin_align_down(s, LOOP_BLOCK_SIZE));
+ size_t offset = static_cast<size_t>(
+ s - reinterpret_cast<const unsigned char *>(block));
+ uint64_t combined = 0;
+ for (size_t i = 0; i < 4; ++i) {
+ cpp::simd_mask<char> m =
+ cpp::load<cpp::simd<char>>(block + i, /*aligned=*/true) == c_byte;
+ combined |=
+ static_cast<uint64_t>(cpp::bit_cast<cpp::simd_bitmask<char>>(m))
----------------
boomanaiden154 wrote:
Turns out we also had this issue in the existing `shift_mask` implementation.
I've refactored to a common helper in
https://github.com/llvm/llvm-project/pull/244696. Need to do some review of
that myself after lunch though.
https://github.com/llvm/llvm-project/pull/244469
_______________________________________________
llvm-branch-commits mailing list
[email protected]
https://lists.llvm.org/cgi-bin/mailman/listinfo/llvm-branch-commits