The existing Arm search_line_fast is ancient and not well optimized.
Optimize it for typical inputs (short lines) - what matters is to quickly
get the match result for the first few vectors with minimal initialization
overhead. We simply loop until a match is found even if the input pointer
is unaligned or close to the end. Since this may overread, it relies on
*end containing a match and CPP_BUFFER_PADDING >= 16.
Lookup the low 3 bits of each character using 2 64-bit TBLs and compare
the 128-bit result with the original input. The lookup table contains
the 4 search characters at entries MOD 8, so a match results in the same
character. This works because the low 3 bits of the search characters
are unique.
The optimized sequence is less than a third of the old code:
vmov.i8 q12, #7 @ v16qi
vldr d22, .L29
.L25:
vld1.8 {d18-d19}, [r0]!
vand q10, q9, q12
vtbl.8 d16, {d22}, d20
vtbl.8 d17, {d22}, d21
vceq.i8 q8, q8, q9
vaddhn.i16 d16, q8, q8
vmov r2, r3, d16 @ int
orrs r1, r2, r3
beq .L25
cmp r2, #0
rbiteq r2, r3
rbitne r2, r2
clzeq r2, r2
clzne r2, r2
addeq r2, r2, #32
sub r2, r2, #61
add r0, r0, r2, asr #2
bx lr
Performance is significantly better as a result: on a huge trace that replays
the calls from libcpp it is ~24% faster on Neoverse N1.
Passes bootstrap, OK for commit?
libcpp/ChangeLog:
* lex.cc (search_line_fast): Optimized Arm implementation.
---
diff --git a/libcpp/lex.cc b/libcpp/lex.cc
index
0e4d29a2950a45b9e43f4673bf69394134264660..0c4e479ec4b847fd136a4c1950603d2ef69d6806
100644
--- a/libcpp/lex.cc
+++ b/libcpp/lex.cc
@@ -785,64 +785,49 @@ search_line_fast (const uchar *s, const uchar *end)
#elif defined (__ARM_NEON)
#include "arm_neon.h"
-static const uchar *
-search_line_fast (const uchar *s, const uchar *end ATTRIBUTE_UNUSED)
-{
- const uint8x16_t repl_nl = vdupq_n_u8 ('\n');
- const uint8x16_t repl_cr = vdupq_n_u8 ('\r');
- const uint8x16_t repl_bs = vdupq_n_u8 ('\\');
- const uint8x16_t repl_qm = vdupq_n_u8 ('?');
- const uint8x16_t xmask = (uint8x16_t) vdupq_n_u64 (0x8040201008040201ULL);
+/* A fast NEON scanner implementation using table lookup.
- unsigned int misalign, found, mask;
- const uint8_t *p;
- uint8x16_t data;
+ Lookup the low 3 bits of each character using 2 64-bit TBLs and compare
+ the 128-bit result with the original input. The lookup table contains
+ the 4 search characters at entries MOD 8, so a match results in the same
+ character. This works because the low 3 bits of the search characters
+ are unique.
- /* Align the source pointer. */
- misalign = (uintptr_t)s & 15;
- p = (const uint8_t *)((uintptr_t)s & -16);
- data = vld1q_u8 (p);
+ To get good performance, what matters is to quickly get the match result
+ for the first few vectors with minimal initialization overhead.
+ We simply loop until a match is found even if the input pointer is
+ unaligned or close to the end. Since this may overread, it relies on
+ *end containing a match and CPP_BUFFER_PADDING >= 16.
+*/
- /* Create a mask for the bytes that are valid within the first
- 16-byte block. The Idea here is that the AND with the mask
- within the loop is "free", since we need some AND or TEST
- insn in order to set the flags for the branch anyway. */
- mask = (-1u << misalign) & 0xffff;
+static_assert (CPP_BUFFER_PADDING >= 16, "");
- /* Main loop, processing 16 bytes at a time. */
- goto start;
+static const uchar *
+search_line_fast (const uchar *s, const uchar *end ATTRIBUTE_UNUSED)
+{
+ uint8x16_t data, res, m;
+ uint8x8_t tab, res1, res2;
+ uint64_t mask;
+ m = vdupq_n_u8 (0x7);
+ tab = (uint8x8_t) vdup_n_u64 (0x3f000d5c000a0001UL);
- do
+ while (1)
{
- uint8x8_t l;
- uint16x4_t m;
- uint32x2_t n;
- uint8x16_t t, u, v, w;
-
- p += 16;
- data = vld1q_u8 (p);
- mask = 0xffff;
-
- start:
- t = vceqq_u8 (data, repl_nl);
- u = vceqq_u8 (data, repl_cr);
- v = vorrq_u8 (t, vceqq_u8 (data, repl_bs));
- w = vorrq_u8 (u, vceqq_u8 (data, repl_qm));
- t = vandq_u8 (vorrq_u8 (v, w), xmask);
- l = vpadd_u8 (vget_low_u8 (t), vget_high_u8 (t));
- m = vpaddl_u8 (l);
- n = vpaddl_u16 (m);
-
- found = vget_lane_u32 ((uint32x2_t) vorr_u64 ((uint64x1_t) n,
- vshr_n_u64 ((uint64x1_t) n, 24)), 0);
- found &= mask;
+ data = vld1q_u8 (s);
+ s += 16;
+ res = vandq_u8 (data, m);
+ res1 = vtbl1_u8 (tab, vget_low_u8 (res));
+ res2 = vtbl1_u8 (tab, vget_high_u8 (res));
+ res = vcombine_u8 (res1, res2);
+ res = vceqq_u8 (res, data);
+ mask = (uint64_t) vaddhn_u16 ((uint16x8_t)res, (uint16x8_t)res);
+ /* Use asm to ensure the vmov r2, r3, d16 to transfer 'mask' to scalar
+ registers does not get split into 32-bit transfers. */
+ asm ("" : "+r" (mask));
+ /* After CTZ adjust for ADDHN bias and the post-increment of 's'. */
+ if (mask)
+ return s + ((__builtin_ctzll (mask) + 3 - 16 * 4) >> 2);
}
- while (!found);
-
- /* FOUND contains 1 in bits for which we matched a relevant
- character. Conversion to the byte index is trivial. */
- found = __builtin_ctz (found);
- return (const uchar *)p + found;
}
#else
