1 /* memcmp/wmemcmp optimized with 256-bit EVEX instructions.
2 Copyright (C) 2021-2024 Free Software Foundation, Inc.
3 This file is part of the GNU C Library.
5 The GNU C Library is free software; you can redistribute it and/or
6 modify it under the terms of the GNU Lesser General Public
7 License as published by the Free Software Foundation; either
8 version 2.1 of the License, or (at your option) any later version.
10 The GNU C Library is distributed in the hope that it will be useful,
11 but WITHOUT ANY WARRANTY; without even the implied warranty of
12 MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU
13 Lesser General Public License for more details.
15 You should have received a copy of the GNU Lesser General Public
16 License along with the GNU C Library; if not, see
17 <https://www.gnu.org/licenses/>. */
19 #include <isa-level.h>
21 #if ISA_SHOULD_BUILD (4)
24 /* memcmp/wmemcmp is implemented as:
25 1. Use ymm vector compares when possible. The only case where
26 vector compares is not possible for when size < CHAR_PER_VEC
27 and loading from either s1 or s2 would cause a page cross.
28 2. For size from 2 to 7 bytes on page cross, load as big endian
29 with movbe and bswap to avoid branches.
30 3. Use xmm vector compare when size >= 4 bytes for memcmp or
31 size >= 8 bytes for wmemcmp.
32 4. Optimistically compare up to first 4 * CHAR_PER_VEC one at a
33 to check for early mismatches. Only do this if its guaranteed the
35 5. If size is 8 * VEC_SIZE or less, unroll the loop.
36 6. Compare 4 * VEC_SIZE at a time with the aligned first memory
38 7. Use 2 vector compares when size is 2 * CHAR_PER_VEC or less.
39 8. Use 4 vector compares when size is 4 * CHAR_PER_VEC or less.
40 9. Use 8 vector compares when size is 8 * CHAR_PER_VEC or less.
42 When possible the implementation tries to optimize for frontend in the
45 1. All code sections that fit are able to run optimally out of the
47 2. All code sections that fit are able to run optimally out of the
49 3. Basic blocks are contained in minimum number of fetch blocks
53 1. Logically connected basic blocks are put in the same
55 2. Logically connected basic blocks that do not fit in the same
56 cache-line are put in adjacent lines. This can get beneficial
57 L2 spatial prefetching and L1 next-line prefetching. */
62 # define MEMCMP __memcmp_evex_movbe
66 # include "x86-evex256-vecs.h"
69 # ifdef USE_AS_WMEMCMP
70 # define VMOVU_MASK vmovdqu32
73 # define VPCMPEQ vpcmpeqd
74 # define VPTEST vptestmd
76 # define USE_WIDE_CHAR
78 # define VMOVU_MASK vmovdqu8
80 # define VPCMP vpcmpub
81 # define VPCMPEQ vpcmpeqb
82 # define VPTEST vptestmb
85 # include "reg-macros.h"
87 # define PAGE_SIZE 4096
88 # define CHAR_PER_VEC (VEC_SIZE / CHAR_SIZE)
92 wmemcmp has to use SIGNED comparison for elements.
93 memcmp has to use UNSIGNED comparison for elements.
96 .section SECTION(.text), "ax", @progbits
97 /* Cache align memcmp entry. This allows for much more thorough
98 frontend optimization. */
99 ENTRY_P2ALIGN (MEMCMP, 6)
101 /* Clear the upper 32 bits. */
104 cmp $CHAR_PER_VEC, %RDX_LP
105 /* Fall through for [0, VEC_SIZE] as its the hottest. */
108 /* Create mask of bytes that are guaranteed to be valid because
109 of length (edx). Using masked movs allows us to skip checks
110 for page crosses/zero size. */
112 bzhi %VRDX, %VRAX, %VRAX
113 /* NB: A `jz` might be useful here. Page-faults that are
114 invalidated by predicate execution (the evex mask) can be
115 very slow. The expectation is this is not the norm so and
116 "most" code will not regularly call 'memcmp' with length = 0
117 and memory that is not wired up. */
122 /* Safe to load full ymm with mask. */
123 VMOVU_MASK (%rsi), %VMM(2){%k2}{z}
124 /* Slightly different method for VEC_SIZE == 64 to save a bit of
125 code size. This allows us to fit L(return_vec_0) entirely in
126 the first cache line. */
128 VPCMPEQ (%rdi), %VMM(2), %k1{%k2}
132 VPCMP $4, (%rdi), %VMM(2), %k1{%k2}
142 # ifdef USE_AS_WMEMCMP
143 movl (%rdi, %rax, CHAR_SIZE), %ecx
145 cmpl (%rsi, %rax, CHAR_SIZE), %ecx
146 /* NB: no partial register stall here because xorl zero idiom
149 leal -1(%rdx, %rdx), %eax
151 movzbl (%rsi, %rax), %ecx
153 movb (%rdi, %rax), %al
155 movzbl (%rdi, %rax), %eax
163 /* From VEC to 2 * VEC. No branch when size == VEC_SIZE. */
164 VMOVU (%rsi), %VMM(1)
165 /* Use compare not equals to directly check for mismatch. */
166 VPCMP $4, (%rdi), %VMM(1), %k1
168 /* NB: eax must be destination register if going to
169 L(return_vec_[0,2]). For L(return_vec_3) destination
170 register must be ecx. */
174 cmpq $(CHAR_PER_VEC * 2), %rdx
177 /* Check second VEC no matter what. */
178 VMOVU VEC_SIZE(%rsi), %VMM(2)
179 VPCMP $4, VEC_SIZE(%rdi), %VMM(2), %k1
184 /* Less than 4 * VEC. */
185 cmpq $(CHAR_PER_VEC * 4), %rdx
188 /* Check third and fourth VEC no matter what. */
189 VMOVU (VEC_SIZE * 2)(%rsi), %VMM(3)
190 VPCMP $4, (VEC_SIZE * 2)(%rdi), %VMM(3), %k1
195 VMOVU (VEC_SIZE * 3)(%rsi), %VMM(4)
196 VPCMP $4, (VEC_SIZE * 3)(%rdi), %VMM(4), %k1
201 /* Go to 4x VEC loop. */
202 cmpq $(CHAR_PER_VEC * 8), %rdx
205 /* Handle remainder of size = 4 * VEC + 1 to 8 * VEC without any
208 /* Load first two VEC from s2 before adjusting addresses. */
209 VMOVU -(VEC_SIZE * 4)(%rsi, %rdx, CHAR_SIZE), %VMM(1)
210 VMOVU -(VEC_SIZE * 3)(%rsi, %rdx, CHAR_SIZE), %VMM(2)
211 leaq -(4 * VEC_SIZE)(%rdi, %rdx, CHAR_SIZE), %rdi
212 leaq -(4 * VEC_SIZE)(%rsi, %rdx, CHAR_SIZE), %rsi
214 /* Wait to load from s1 until addressed adjust due to
215 unlamination of microfusion with complex address mode. */
217 /* vpxor will be all 0s if s1 and s2 are equal. Otherwise it
218 will have some 1s. */
219 vpxorq (%rdi), %VMM(1), %VMM(1)
220 vpxorq (VEC_SIZE)(%rdi), %VMM(2), %VMM(2)
222 VMOVU (VEC_SIZE * 2)(%rsi), %VMM(3)
223 vpxorq (VEC_SIZE * 2)(%rdi), %VMM(3), %VMM(3)
225 VMOVU (VEC_SIZE * 3)(%rsi), %VMM(4)
226 /* Ternary logic to xor (VEC_SIZE * 3)(%rdi) with VEC(4) while
227 oring with VEC(1). Result is stored in VEC(4). */
228 vpternlogd $0xde, (VEC_SIZE * 3)(%rdi), %VMM(1), %VMM(4)
230 /* Or together VEC(2), VEC(3), and VEC(4) into VEC(4). */
231 vpternlogd $0xfe, %VMM(2), %VMM(3), %VMM(4)
233 /* Test VEC(4) against itself. Store any CHAR mismatches in k1.
235 VPTEST %VMM(4), %VMM(4), %k1
236 /* k1 must go to ecx for L(return_vec_0_1_2_3). */
239 jnz L(return_vec_0_1_2_3)
240 /* NB: eax must be zero to reach here. */
245 L(8x_end_return_vec_0_1_2_3):
247 L(8x_return_vec_0_1_2_3):
248 /* L(loop_4x_vec) leaves result in `k1` for VEC_SIZE == 64. */
253 L(return_vec_0_1_2_3):
254 VPTEST %VMM(1), %VMM(1), %k0
259 VPTEST %VMM(2), %VMM(2), %k0
264 VPTEST %VMM(3), %VMM(3), %k0
270 /* bsf saves 1 byte from tzcnt. This keep L(return_vec_3) in one
271 fetch block and the entire L(*return_vec_0_1_2_3) in 1 cache
274 # ifdef USE_AS_WMEMCMP
275 movl (VEC_SIZE * 3)(%rdi, %rcx, CHAR_SIZE), %eax
277 cmpl (VEC_SIZE * 3)(%rsi, %rcx, CHAR_SIZE), %eax
279 leal -1(%rdx, %rdx), %eax
281 movzbl (VEC_SIZE * 3)(%rdi, %rcx), %eax
282 movzbl (VEC_SIZE * 3)(%rsi, %rcx), %ecx
290 /* bsf saves 1 byte over tzcnt and keeps L(return_vec_1) in one
293 # ifdef USE_AS_WMEMCMP
294 movl VEC_SIZE(%rdi, %rax, CHAR_SIZE), %ecx
296 cmpl VEC_SIZE(%rsi, %rax, CHAR_SIZE), %ecx
298 leal -1(%rdx, %rdx), %eax
300 movzbl VEC_SIZE(%rsi, %rax), %ecx
301 movzbl VEC_SIZE(%rdi, %rax), %eax
308 /* bsf saves 1 byte over tzcnt and keeps L(return_vec_2) in one
311 # ifdef USE_AS_WMEMCMP
312 movl (VEC_SIZE * 2)(%rdi, %rax, CHAR_SIZE), %ecx
314 cmpl (VEC_SIZE * 2)(%rsi, %rax, CHAR_SIZE), %ecx
316 leal -1(%rdx, %rdx), %eax
318 movzbl (VEC_SIZE * 2)(%rsi, %rax), %ecx
319 movzbl (VEC_SIZE * 2)(%rdi, %rax), %eax
326 /* Set end of s1 in rdx. */
327 leaq -(VEC_SIZE * 4)(%rdi, %rdx, CHAR_SIZE), %rdx
328 /* rsi stores s2 - s1. This allows loop to only update one
331 /* Align s1 pointer. */
332 andq $-VEC_SIZE, %rdi
333 /* Adjust because first 4x vec where check already. */
334 subq $-(VEC_SIZE * 4), %rdi
338 VMOVU (%rsi, %rdi), %VMM(1)
339 vpxorq (%rdi), %VMM(1), %VMM(1)
340 VMOVU VEC_SIZE(%rsi, %rdi), %VMM(2)
341 vpxorq VEC_SIZE(%rdi), %VMM(2), %VMM(2)
342 VMOVU (VEC_SIZE * 2)(%rsi, %rdi), %VMM(3)
343 vpxorq (VEC_SIZE * 2)(%rdi), %VMM(3), %VMM(3)
344 VMOVU (VEC_SIZE * 3)(%rsi, %rdi), %VMM(4)
345 vpternlogd $0xde, (VEC_SIZE * 3)(%rdi), %VMM(1), %VMM(4)
346 vpternlogd $0xfe, %VMM(2), %VMM(3), %VMM(4)
347 VPTEST %VMM(4), %VMM(4), %k1
348 /* If VEC_SIZE == 64 just branch with KTEST. We have free port0
349 space and it allows the loop to fit in 2x cache lines
357 jnz L(8x_return_vec_0_1_2_3)
358 subq $-(VEC_SIZE * 4), %rdi
362 /* rdi has 4 * VEC_SIZE - remaining length. */
363 cmpl $(VEC_SIZE * 3), %edi
364 jge L(8x_last_1x_vec)
365 /* Load regardless of branch. */
366 VMOVU (VEC_SIZE * 2)(%rsi, %rdx), %VMM(3)
368 /* Separate logic as we can only use testb for VEC_SIZE == 64.
374 cmpl $(VEC_SIZE * 2), %edi
375 jge L(8x_last_2x_vec)
378 vpxorq (VEC_SIZE * 2)(%rdx), %VMM(3), %VMM(3)
380 VMOVU (%rsi, %rdx), %VMM(1)
381 vpxorq (%rdx), %VMM(1), %VMM(1)
383 VMOVU VEC_SIZE(%rsi, %rdx), %VMM(2)
384 vpxorq VEC_SIZE(%rdx), %VMM(2), %VMM(2)
385 VMOVU (VEC_SIZE * 3)(%rsi, %rdx), %VMM(4)
386 vpternlogd $0xde, (VEC_SIZE * 3)(%rdx), %VMM(1), %VMM(4)
387 vpternlogd $0xfe, %VMM(2), %VMM(3), %VMM(4)
388 VPTEST %VMM(4), %VMM(4), %k1
389 /* L(8x_end_return_vec_0_1_2_3) expects bitmask to still be in
390 `k1` if VEC_SIZE == 64. */
397 jnz L(8x_end_return_vec_0_1_2_3)
398 /* NB: eax must be zero to reach here. */
401 /* Only entry is from L(more_8x_vec). */
404 VPCMP $4, (VEC_SIZE * 2)(%rdx), %VMM(3), %k1
407 jnz L(8x_return_vec_2)
410 VMOVU (VEC_SIZE * 3)(%rsi, %rdx), %VMM(1)
411 VPCMP $4, (VEC_SIZE * 3)(%rdx), %VMM(1), %k1
414 jnz L(8x_return_vec_3)
417 /* Not ideally aligned (at offset +9 bytes in fetch block) but
418 not aligning keeps it in the same cache line as
419 L(8x_last_1x/2x_vec) so likely worth it. As well, saves code
426 # ifdef USE_AS_WMEMCMP
427 leaq (%rdx, %rax, CHAR_SIZE), %rax
428 movl (VEC_SIZE * 3)(%rax), %ecx
430 cmpl (VEC_SIZE * 3)(%rsi, %rax), %ecx
432 leal -1(%rdx, %rdx), %eax
435 movzbl (VEC_SIZE * 3)(%rsi, %rax), %ecx
436 movzbl (VEC_SIZE * 3)(%rax), %eax
443 /* Check second to last VEC. */
444 VMOVU -(VEC_SIZE * 2)(%rsi, %rdx, CHAR_SIZE), %VMM(1)
445 VPCMP $4, -(VEC_SIZE * 2)(%rdi, %rdx, CHAR_SIZE), %VMM(1), %k1
448 jnz L(return_vec_1_end)
450 /* Check last VEC. */
453 VMOVU -(VEC_SIZE * 1)(%rsi, %rdx, CHAR_SIZE), %VMM(1)
454 VPCMP $4, -(VEC_SIZE * 1)(%rdi, %rdx, CHAR_SIZE), %VMM(1), %k1
457 jnz L(return_vec_0_end)
461 /* Don't fully align. Takes 2-fetch blocks either way and
462 aligning will cause code to spill into another cacheline.
466 /* Use bsf to save code size. This is necessary to have
467 L(one_or_less) fit in aligning bytes between. */
470 # ifdef USE_AS_WMEMCMP
471 movl -(VEC_SIZE * 2)(%rdi, %rax, CHAR_SIZE), %ecx
473 cmpl -(VEC_SIZE * 2)(%rsi, %rax, CHAR_SIZE), %ecx
475 leal -1(%rdx, %rdx), %eax
477 movzbl -(VEC_SIZE * 2)(%rsi, %rax), %ecx
478 movzbl -(VEC_SIZE * 2)(%rdi, %rax), %eax
484 /* Don't align. Takes 2-fetch blocks either way and aligning
485 will cause code to spill into another cacheline. */
489 # ifdef USE_AS_WMEMCMP
490 movl -VEC_SIZE(%rdi, %rax, CHAR_SIZE), %ecx
492 cmpl -VEC_SIZE(%rsi, %rax, CHAR_SIZE), %ecx
494 leal -1(%rdx, %rdx), %eax
496 movzbl -VEC_SIZE(%rsi, %rax), %ecx
497 movzbl -VEC_SIZE(%rdi, %rax), %eax
501 /* evex256: 2-byte until next cache line. evex512: 46-bytes
502 until next cache line. */