From mboxrd@z Thu Jan 1 00:00:00 1970 Return-Path: Received: from mail-pj1-x1034.google.com (mail-pj1-x1034.google.com [IPv6:2607:f8b0:4864:20::1034]) by sourceware.org (Postfix) with ESMTPS id 4A19E385840B for ; Tue, 5 Oct 2021 16:32:59 +0000 (GMT) DMARC-Filter: OpenDMARC Filter v1.4.1 sourceware.org 4A19E385840B Received: by mail-pj1-x1034.google.com with SMTP id cs11-20020a17090af50b00b0019fe3df3dddso2241436pjb.0 for ; Tue, 05 Oct 2021 09:32:59 -0700 (PDT) X-Google-DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=1e100.net; s=20210112; h=x-gm-message-state:mime-version:references:in-reply-to:from:date :message-id:subject:to:cc; bh=bkc4S8EcXoIGdkIxAFslCLbNap6oYi6Smm+dmm+GS9U=; b=pu6B/yRS/r8BNoGEnZ5Z0d3ADcSS7G3JK2y20tWbTXmzF1qoHZ5ffRHMQFEd3ykgru zVSBRC6zFcRsyqizT45KeqSEpdcs79hCXPz43l8JHKrkEhyokKrwCxdIAPSjO7hfgwQv 3AB5NmETddl6adY1trf4XhqXtipE2lD7BBYorl71FbYv0jRKzt5mWG1ag+JuqkWQYYXy hFIxi9FqzzbYzJc+7mzR42YujtEd+cNpZ/+Mk5XRLg31vFrcgJduDwbzjy4lbWPLhAk6 2MdFXzZ9dgBo127AxpXzQOVBMEPUO/gwRhtrRrc/rPQFKaQ1V7lXZTVi55hIarBB+Hn3 SdEg== X-Gm-Message-State: AOAM531uRaBEIncTCoZCACqKSvX0DmwQ8zNehJZ7pjSkDDEGr4aIHxw4 r9guAuPdQ1kslMbOPRByO8qQ8Hfhws7P9wXZm9/OGtP8 X-Google-Smtp-Source: ABdhPJwnivlfIQmQrfzo6rnHaeDpMk1XJwJftAMMubKpnN6x7ZyMQGFeMZEP37AZcwqm65l784rMDbIuBKXh1cKpVM8= X-Received: by 2002:a17:90a:b794:: with SMTP id m20mr5032857pjr.178.1633451578004; Tue, 05 Oct 2021 09:32:58 -0700 (PDT) MIME-Version: 1.0 References: <20210922005018.1542107-1-goldstein.w.n@gmail.com> <20210922005018.1542107-2-goldstein.w.n@gmail.com> In-Reply-To: From: Noah Goldstein Date: Tue, 5 Oct 2021 11:32:46 -0500 Message-ID: Subject: Re: [PATCH v1 2/2] x86: Optimize memcmp-evex-movbe.S for frontend behavior and size To: GNU C Library X-Spam-Status: No, score=-7.7 required=5.0 tests=BAYES_00, DKIM_SIGNED, DKIM_VALID, DKIM_VALID_AU, DKIM_VALID_EF, FREEMAIL_FROM, GIT_PATCH_0, HTML_MESSAGE, KAM_STORAGE_GOOGLE, RCVD_IN_DNSWL_NONE, SCC_5_SHORT_WORD_LINES, SPF_HELO_NONE, SPF_PASS, TXREP, URIBL_SBL_A autolearn=ham autolearn_force=no version=3.4.4 X-Spam-Checker-Version: SpamAssassin 3.4.4 (2020-01-24) on server2.sourceware.org Content-Type: text/plain; charset="UTF-8" X-Content-Filtered-By: Mailman/MimeDel 2.1.29 X-BeenThere: libc-alpha@sourceware.org X-Mailman-Version: 2.1.29 Precedence: list List-Id: Libc-alpha mailing list List-Unsubscribe: , List-Archive: List-Post: List-Help: List-Subscribe: , X-List-Received-Date: Tue, 05 Oct 2021 16:33:04 -0000 On Mon, Sep 27, 2021 at 11:07 AM Noah Goldstein wrote: > > > On Tue, Sep 21, 2021 at 7:52 PM Noah Goldstein > wrote: > >> >> >> On Tue, Sep 21, 2021 at 7:51 PM Noah Goldstein >> wrote: >> >>> No bug. >>> >>> The frontend optimizations are to: >>> 1. Reorganize logically connected basic blocks so they are either in >>> the same cache line or adjacent cache lines. >>> 2. Avoid cases when basic blocks unnecissarily cross cache lines. >>> 3. Try and 32 byte align any basic blocks possible without sacrificing >>> code size. Smaller / Less hot basic blocks are used for this. >>> >>> Overall code size shrunk by 168 bytes. This should make up for any >>> extra costs due to aligning to 64 bytes. >>> >>> In general performance before deviated a great deal dependending on >>> whether entry alignment % 64 was 0, 16, 32, or 48. These changes >>> essentially make it so that the current implementation is at least >>> equal to the best alignment of the original for any arguments. >>> >>> The only additional optimization is in the page cross case. Branch on >>> equals case was removed from the size == [4, 7] case. As well the [4, >>> 7] and [2, 3] case where swapped as [4, 7] is likely a more hot >>> argument size. >>> >>> test-memcmp and test-wmemcmp are both passing. >>> --- >>> Performance results attached in reply. >>> >> Performance numbers. >> >>> >>> Benchmark CPU: >>> https://ark.intel.com/content/www/us/en/ark/products/208921/intel-core-i7-1165g7-processor-12m-cache-up-to-4-70-ghz-with-ipu.html >>> >>> Results are from geometric mean of N = 20 runs. >>> >>> Time for new implemention shown. >>> >>> Score(N) is the New Time / Old Time with entry alignment == N >>> >>> In general there is one performance degregation for size range [2, 3] >>> in the page cross case. This is expected as the new code intentionally >>> gives the fallthrough path to the hotter size range [4, 7]. >>> >>> >>> For the micro benchmarks there is no outright performance improvement >>> in the sense that for each benchmark configuration there is at least >>> one entry alignment where the old version had roughly the same >>> performance. But this should provide a great deal more performance >>> stability. >>> >>> The hope, however, is that with the code size shrink and >>> reorganization of basic blocks for better icache behavior. Concerns >>> such as those brought up in this paper: >>> >>> >>> https://storage.googleapis.com/pub-tools-public-publication-data/pdf/e52f61fd2c51e8962305120548581efacbc06ffc.pdf >>> >>> should be better addressed. >>> >>> sysdeps/x86_64/multiarch/memcmp-evex-movbe.S | 434 +++++++++++-------- >>> 1 file changed, 242 insertions(+), 192 deletions(-) >>> >>> diff --git a/sysdeps/x86_64/multiarch/memcmp-evex-movbe.S >>> b/sysdeps/x86_64/multiarch/memcmp-evex-movbe.S >>> index 654dc7ac8c..2761b54f2e 100644 >>> --- a/sysdeps/x86_64/multiarch/memcmp-evex-movbe.S >>> +++ b/sysdeps/x86_64/multiarch/memcmp-evex-movbe.S >>> @@ -34,7 +34,24 @@ >>> area. >>> 7. Use 2 vector compares when size is 2 * CHAR_PER_VEC or less. >>> 8. Use 4 vector compares when size is 4 * CHAR_PER_VEC or less. >>> - 9. Use 8 vector compares when size is 8 * CHAR_PER_VEC or less. */ >>> + 9. Use 8 vector compares when size is 8 * CHAR_PER_VEC or less. >>> + >>> +When possible the implementation tries to optimize for frontend in the >>> +following ways: >>> +Throughput: >>> + 1. All code sections that fit are able to run optimally out of the >>> + LSD. >>> + 2. All code sections that fit are able to run optimally out of the >>> + DSB >>> + 3. Basic blocks are contained in minimum number of fetch blocks >>> + necessary. >>> + >>> +Latency: >>> + 1. Logically connected basic blocks are put in the same >>> + cache-line. >>> + 2. Logically connected basic blocks that do not fit in the same >>> + cache-line are put in adjacent lines. This can get beneficial >>> + L2 spatial prefetching and L1 next-line prefetching. */ >>> >>> # include >>> >>> @@ -47,9 +64,11 @@ >>> # ifdef USE_AS_WMEMCMP >>> # define CHAR_SIZE 4 >>> # define VPCMP vpcmpd >>> +# define VPTEST vptestmd >>> # else >>> # define CHAR_SIZE 1 >>> # define VPCMP vpcmpub >>> +# define VPTEST vptestmb >>> # endif >>> >>> # define VEC_SIZE 32 >>> @@ -75,7 +94,9 @@ >>> */ >>> >>> .section .text.evex,"ax",@progbits >>> -ENTRY (MEMCMP) >>> +/* Cache align memcmp entry. This allows for much more thorough >>> + frontend optimization. */ >>> +ENTRY_P2ALIGN (MEMCMP, 6) >>> # ifdef __ILP32__ >>> /* Clear the upper 32 bits. */ >>> movl %edx, %edx >>> @@ -89,7 +110,7 @@ ENTRY (MEMCMP) >>> VPCMP $4, (%rdi), %YMM1, %k1 >>> kmovd %k1, %eax >>> /* NB: eax must be destination register if going to >>> - L(return_vec_[0,2]). For L(return_vec_3 destination register >>> + L(return_vec_[0,2]). For L(return_vec_3) destination register >>> must be ecx. */ >>> testl %eax, %eax >>> jnz L(return_vec_0) >>> @@ -121,10 +142,6 @@ ENTRY (MEMCMP) >>> testl %ecx, %ecx >>> jnz L(return_vec_3) >>> >>> - /* Zero YMM0. 4x VEC reduction is done with vpxor + vtern so >>> - compare with zero to get a mask is needed. */ >>> - vpxorq %XMM0, %XMM0, %XMM0 >>> - >>> /* Go to 4x VEC loop. */ >>> cmpq $(CHAR_PER_VEC * 8), %rdx >>> ja L(more_8x_vec) >>> @@ -148,47 +165,61 @@ ENTRY (MEMCMP) >>> >>> VMOVU (VEC_SIZE * 2)(%rsi), %YMM3 >>> vpxorq (VEC_SIZE * 2)(%rdi), %YMM3, %YMM3 >>> - /* Or together YMM1, YMM2, and YMM3 into YMM3. */ >>> - vpternlogd $0xfe, %YMM1, %YMM2, %YMM3 >>> >>> VMOVU (VEC_SIZE * 3)(%rsi), %YMM4 >>> /* Ternary logic to xor (VEC_SIZE * 3)(%rdi) with YMM4 while >>> - oring with YMM3. Result is stored in YMM4. */ >>> - vpternlogd $0xde, (VEC_SIZE * 3)(%rdi), %YMM3, %YMM4 >>> - /* Compare YMM4 with 0. If any 1s s1 and s2 don't match. */ >>> - VPCMP $4, %YMM4, %YMM0, %k1 >>> + oring with YMM1. Result is stored in YMM4. */ >>> + vpternlogd $0xde, (VEC_SIZE * 3)(%rdi), %YMM1, %YMM4 >>> + >>> + /* Or together YMM2, YMM3, and YMM4 into YMM4. */ >>> + vpternlogd $0xfe, %YMM2, %YMM3, %YMM4 >>> + >>> + /* Test YMM4 against itself. Store any CHAR mismatches in k1. >>> + */ >>> + VPTEST %YMM4, %YMM4, %k1 >>> + /* k1 must go to ecx for L(return_vec_0_1_2_3). */ >>> kmovd %k1, %ecx >>> testl %ecx, %ecx >>> jnz L(return_vec_0_1_2_3) >>> /* NB: eax must be zero to reach here. */ >>> ret >>> >>> - /* NB: aligning 32 here allows for the rest of the jump targets >>> - to be tuned for 32 byte alignment. Most important this ensures >>> - the L(more_8x_vec) loop is 32 byte aligned. */ >>> - .p2align 5 >>> -L(less_vec): >>> - /* Check if one or less CHAR. This is necessary for size = 0 but >>> - is also faster for size = CHAR_SIZE. */ >>> - cmpl $1, %edx >>> - jbe L(one_or_less) >>> + .p2align 4 >>> +L(8x_end_return_vec_0_1_2_3): >>> + movq %rdx, %rdi >>> +L(8x_return_vec_0_1_2_3): >>> + addq %rdi, %rsi >>> +L(return_vec_0_1_2_3): >>> + VPTEST %YMM1, %YMM1, %k0 >>> + kmovd %k0, %eax >>> + testl %eax, %eax >>> + jnz L(return_vec_0) >>> >>> - /* Check if loading one VEC from either s1 or s2 could cause a >>> - page cross. This can have false positives but is by far the >>> - fastest method. */ >>> - movl %edi, %eax >>> - orl %esi, %eax >>> - andl $(PAGE_SIZE - 1), %eax >>> - cmpl $(PAGE_SIZE - VEC_SIZE), %eax >>> - jg L(page_cross_less_vec) >>> + VPTEST %YMM2, %YMM2, %k0 >>> + kmovd %k0, %eax >>> + testl %eax, %eax >>> + jnz L(return_vec_1) >>> >>> - /* No page cross possible. */ >>> - VMOVU (%rsi), %YMM2 >>> - VPCMP $4, (%rdi), %YMM2, %k1 >>> - kmovd %k1, %eax >>> - /* Create mask in ecx for potentially in bound matches. */ >>> - bzhil %edx, %eax, %eax >>> - jnz L(return_vec_0) >>> + VPTEST %YMM3, %YMM3, %k0 >>> + kmovd %k0, %eax >>> + testl %eax, %eax >>> + jnz L(return_vec_2) >>> +L(return_vec_3): >>> + /* bsf saves 1 byte from tzcnt. This keep L(return_vec_3) in one >>> + fetch block and the entire L(*return_vec_0_1_2_3) in 1 cache >>> + line. */ >>> + bsfl %ecx, %ecx >>> +# ifdef USE_AS_WMEMCMP >>> + movl (VEC_SIZE * 3)(%rdi, %rcx, CHAR_SIZE), %eax >>> + xorl %edx, %edx >>> + cmpl (VEC_SIZE * 3)(%rsi, %rcx, CHAR_SIZE), %eax >>> + setg %dl >>> + leal -1(%rdx, %rdx), %eax >>> +# else >>> + movzbl (VEC_SIZE * 3)(%rdi, %rcx), %eax >>> + movzbl (VEC_SIZE * 3)(%rsi, %rcx), %ecx >>> + subl %ecx, %eax >>> +# endif >>> ret >>> >>> .p2align 4 >>> @@ -209,10 +240,11 @@ L(return_vec_0): >>> # endif >>> ret >>> >>> - /* NB: No p2align necessary. Alignment % 16 is naturally 1 >>> - which is good enough for a target not in a loop. */ >>> + .p2align 4 >>> L(return_vec_1): >>> - tzcntl %eax, %eax >>> + /* bsf saves 1 byte over tzcnt and keeps L(return_vec_1) in one >>> + fetch block. */ >>> + bsfl %eax, %eax >>> # ifdef USE_AS_WMEMCMP >>> movl VEC_SIZE(%rdi, %rax, CHAR_SIZE), %ecx >>> xorl %edx, %edx >>> @@ -226,10 +258,11 @@ L(return_vec_1): >>> # endif >>> ret >>> >>> - /* NB: No p2align necessary. Alignment % 16 is naturally 2 >>> - which is good enough for a target not in a loop. */ >>> + .p2align 4,, 10 >>> L(return_vec_2): >>> - tzcntl %eax, %eax >>> + /* bsf saves 1 byte over tzcnt and keeps L(return_vec_2) in one >>> + fetch block. */ >>> + bsfl %eax, %eax >>> # ifdef USE_AS_WMEMCMP >>> movl (VEC_SIZE * 2)(%rdi, %rax, CHAR_SIZE), %ecx >>> xorl %edx, %edx >>> @@ -243,40 +276,6 @@ L(return_vec_2): >>> # endif >>> ret >>> >>> - .p2align 4 >>> -L(8x_return_vec_0_1_2_3): >>> - /* Returning from L(more_8x_vec) requires restoring rsi. */ >>> - addq %rdi, %rsi >>> -L(return_vec_0_1_2_3): >>> - VPCMP $4, %YMM1, %YMM0, %k0 >>> - kmovd %k0, %eax >>> - testl %eax, %eax >>> - jnz L(return_vec_0) >>> - >>> - VPCMP $4, %YMM2, %YMM0, %k0 >>> - kmovd %k0, %eax >>> - testl %eax, %eax >>> - jnz L(return_vec_1) >>> - >>> - VPCMP $4, %YMM3, %YMM0, %k0 >>> - kmovd %k0, %eax >>> - testl %eax, %eax >>> - jnz L(return_vec_2) >>> -L(return_vec_3): >>> - tzcntl %ecx, %ecx >>> -# ifdef USE_AS_WMEMCMP >>> - movl (VEC_SIZE * 3)(%rdi, %rcx, CHAR_SIZE), %eax >>> - xorl %edx, %edx >>> - cmpl (VEC_SIZE * 3)(%rsi, %rcx, CHAR_SIZE), %eax >>> - setg %dl >>> - leal -1(%rdx, %rdx), %eax >>> -# else >>> - movzbl (VEC_SIZE * 3)(%rdi, %rcx), %eax >>> - movzbl (VEC_SIZE * 3)(%rsi, %rcx), %ecx >>> - subl %ecx, %eax >>> -# endif >>> - ret >>> - >>> .p2align 4 >>> L(more_8x_vec): >>> /* Set end of s1 in rdx. */ >>> @@ -288,21 +287,19 @@ L(more_8x_vec): >>> andq $-VEC_SIZE, %rdi >>> /* Adjust because first 4x vec where check already. */ >>> subq $-(VEC_SIZE * 4), %rdi >>> + >>> .p2align 4 >>> L(loop_4x_vec): >>> VMOVU (%rsi, %rdi), %YMM1 >>> vpxorq (%rdi), %YMM1, %YMM1 >>> - >>> VMOVU VEC_SIZE(%rsi, %rdi), %YMM2 >>> vpxorq VEC_SIZE(%rdi), %YMM2, %YMM2 >>> - >>> VMOVU (VEC_SIZE * 2)(%rsi, %rdi), %YMM3 >>> vpxorq (VEC_SIZE * 2)(%rdi), %YMM3, %YMM3 >>> - vpternlogd $0xfe, %YMM1, %YMM2, %YMM3 >>> - >>> VMOVU (VEC_SIZE * 3)(%rsi, %rdi), %YMM4 >>> - vpternlogd $0xde, (VEC_SIZE * 3)(%rdi), %YMM3, %YMM4 >>> - VPCMP $4, %YMM4, %YMM0, %k1 >>> + vpternlogd $0xde, (VEC_SIZE * 3)(%rdi), %YMM1, %YMM4 >>> + vpternlogd $0xfe, %YMM2, %YMM3, %YMM4 >>> + VPTEST %YMM4, %YMM4, %k1 >>> kmovd %k1, %ecx >>> testl %ecx, %ecx >>> jnz L(8x_return_vec_0_1_2_3) >>> @@ -319,28 +316,25 @@ L(loop_4x_vec): >>> cmpl $(VEC_SIZE * 2), %edi >>> jae L(8x_last_2x_vec) >>> >>> + vpxorq (VEC_SIZE * 2)(%rdx), %YMM3, %YMM3 >>> + >>> VMOVU (%rsi, %rdx), %YMM1 >>> vpxorq (%rdx), %YMM1, %YMM1 >>> >>> VMOVU VEC_SIZE(%rsi, %rdx), %YMM2 >>> vpxorq VEC_SIZE(%rdx), %YMM2, %YMM2 >>> - >>> - vpxorq (VEC_SIZE * 2)(%rdx), %YMM3, %YMM3 >>> - vpternlogd $0xfe, %YMM1, %YMM2, %YMM3 >>> - >>> VMOVU (VEC_SIZE * 3)(%rsi, %rdx), %YMM4 >>> - vpternlogd $0xde, (VEC_SIZE * 3)(%rdx), %YMM3, %YMM4 >>> - VPCMP $4, %YMM4, %YMM0, %k1 >>> + vpternlogd $0xde, (VEC_SIZE * 3)(%rdx), %YMM1, %YMM4 >>> + vpternlogd $0xfe, %YMM2, %YMM3, %YMM4 >>> + VPTEST %YMM4, %YMM4, %k1 >>> kmovd %k1, %ecx >>> - /* Restore s1 pointer to rdi. */ >>> - movq %rdx, %rdi >>> testl %ecx, %ecx >>> - jnz L(8x_return_vec_0_1_2_3) >>> + jnz L(8x_end_return_vec_0_1_2_3) >>> /* NB: eax must be zero to reach here. */ >>> ret >>> >>> /* Only entry is from L(more_8x_vec). */ >>> - .p2align 4 >>> + .p2align 4,, 10 >>> L(8x_last_2x_vec): >>> VPCMP $4, (VEC_SIZE * 2)(%rdx), %YMM3, %k1 >>> kmovd %k1, %eax >>> @@ -355,7 +349,31 @@ L(8x_last_1x_vec): >>> jnz L(8x_return_vec_3) >>> ret >>> >>> - .p2align 4 >>> + /* Not ideally aligned (at offset +9 bytes in fetch block) but >>> + not aligning keeps it in the same cache line as >>> + L(8x_last_1x/2x_vec) so likely worth it. As well, saves code >>> + size. */ >>> + .p2align 4,, 4 >>> +L(8x_return_vec_2): >>> + subq $VEC_SIZE, %rdx >>> +L(8x_return_vec_3): >>> + bsfl %eax, %eax >>> +# ifdef USE_AS_WMEMCMP >>> + leaq (%rdx, %rax, CHAR_SIZE), %rax >>> + movl (VEC_SIZE * 3)(%rax), %ecx >>> + xorl %edx, %edx >>> + cmpl (VEC_SIZE * 3)(%rsi, %rax), %ecx >>> + setg %dl >>> + leal -1(%rdx, %rdx), %eax >>> +# else >>> + addq %rdx, %rax >>> + movzbl (VEC_SIZE * 3)(%rsi, %rax), %ecx >>> + movzbl (VEC_SIZE * 3)(%rax), %eax >>> + subl %ecx, %eax >>> +# endif >>> + ret >>> + >>> + .p2align 4,, 10 >>> L(last_2x_vec): >>> /* Check second to last VEC. */ >>> VMOVU -(VEC_SIZE * 2)(%rsi, %rdx, CHAR_SIZE), %YMM1 >>> @@ -374,26 +392,49 @@ L(last_1x_vec): >>> jnz L(return_vec_0_end) >>> ret >>> >>> - .p2align 4 >>> -L(8x_return_vec_2): >>> - subq $VEC_SIZE, %rdx >>> -L(8x_return_vec_3): >>> - tzcntl %eax, %eax >>> + .p2align 4,, 10 >>> +L(return_vec_1_end): >>> + /* Use bsf to save code size. This is necessary to have >>> + L(one_or_less) fit in aligning bytes between. */ >>> + bsfl %eax, %eax >>> + addl %edx, %eax >>> # ifdef USE_AS_WMEMCMP >>> - leaq (%rdx, %rax, CHAR_SIZE), %rax >>> - movl (VEC_SIZE * 3)(%rax), %ecx >>> + movl -(VEC_SIZE * 2)(%rdi, %rax, CHAR_SIZE), %ecx >>> xorl %edx, %edx >>> - cmpl (VEC_SIZE * 3)(%rsi, %rax), %ecx >>> + cmpl -(VEC_SIZE * 2)(%rsi, %rax, CHAR_SIZE), %ecx >>> setg %dl >>> leal -1(%rdx, %rdx), %eax >>> # else >>> - addq %rdx, %rax >>> - movzbl (VEC_SIZE * 3)(%rsi, %rax), %ecx >>> - movzbl (VEC_SIZE * 3)(%rax), %eax >>> + movzbl -(VEC_SIZE * 2)(%rsi, %rax), %ecx >>> + movzbl -(VEC_SIZE * 2)(%rdi, %rax), %eax >>> subl %ecx, %eax >>> # endif >>> ret >>> >>> + /* NB: L(one_or_less) fits in alignment padding between >>> + L(return_vec_1_end) and L(return_vec_0_end). */ >>> +# ifdef USE_AS_WMEMCMP >>> +L(one_or_less): >>> + jb L(zero) >>> + movl (%rdi), %ecx >>> + xorl %edx, %edx >>> + cmpl (%rsi), %ecx >>> + je L(zero) >>> + setg %dl >>> + leal -1(%rdx, %rdx), %eax >>> + ret >>> +# else >>> +L(one_or_less): >>> + jb L(zero) >>> + movzbl (%rsi), %ecx >>> + movzbl (%rdi), %eax >>> + subl %ecx, %eax >>> + ret >>> +# endif >>> +L(zero): >>> + xorl %eax, %eax >>> + ret >>> + >>> .p2align 4 >>> L(return_vec_0_end): >>> tzcntl %eax, %eax >>> @@ -412,23 +453,56 @@ L(return_vec_0_end): >>> ret >>> >>> .p2align 4 >>> -L(return_vec_1_end): >>> +L(less_vec): >>> + /* Check if one or less CHAR. This is necessary for size == 0 >>> + but is also faster for size == CHAR_SIZE. */ >>> + cmpl $1, %edx >>> + jbe L(one_or_less) >>> + >>> + /* Check if loading one VEC from either s1 or s2 could cause a >>> + page cross. This can have false positives but is by far the >>> + fastest method. */ >>> + movl %edi, %eax >>> + orl %esi, %eax >>> + andl $(PAGE_SIZE - 1), %eax >>> + cmpl $(PAGE_SIZE - VEC_SIZE), %eax >>> + jg L(page_cross_less_vec) >>> + >>> + /* No page cross possible. */ >>> + VMOVU (%rsi), %YMM2 >>> + VPCMP $4, (%rdi), %YMM2, %k1 >>> + kmovd %k1, %eax >>> + /* Check if any matches where in bounds. Intentionally not >>> + storing result in eax to limit dependency chain if it goes to >>> + L(return_vec_0_lv). */ >>> + bzhil %edx, %eax, %edx >>> + jnz L(return_vec_0_lv) >>> + xorl %eax, %eax >>> + ret >>> + >>> + /* Essentially duplicate of L(return_vec_0). Ends up not costing >>> + any code as shrinks L(less_vec) by allowing 2-byte encoding of >>> + the jump and ends up fitting in aligning bytes. As well fits >>> on >>> + same cache line as L(less_vec) so also saves a line from >>> having >>> + to be fetched on cold calls to memcmp. */ >>> + .p2align 4,, 4 >>> +L(return_vec_0_lv): >>> tzcntl %eax, %eax >>> - addl %edx, %eax >>> # ifdef USE_AS_WMEMCMP >>> - movl -(VEC_SIZE * 2)(%rdi, %rax, CHAR_SIZE), %ecx >>> + movl (%rdi, %rax, CHAR_SIZE), %ecx >>> xorl %edx, %edx >>> - cmpl -(VEC_SIZE * 2)(%rsi, %rax, CHAR_SIZE), %ecx >>> + cmpl (%rsi, %rax, CHAR_SIZE), %ecx >>> + /* NB: no partial register stall here because xorl zero idiom >>> + above. */ >>> setg %dl >>> leal -1(%rdx, %rdx), %eax >>> # else >>> - movzbl -(VEC_SIZE * 2)(%rsi, %rax), %ecx >>> - movzbl -(VEC_SIZE * 2)(%rdi, %rax), %eax >>> + movzbl (%rsi, %rax), %ecx >>> + movzbl (%rdi, %rax), %eax >>> subl %ecx, %eax >>> # endif >>> ret >>> >>> - >>> .p2align 4 >>> L(page_cross_less_vec): >>> /* if USE_AS_WMEMCMP it can only be 0, 4, 8, 12, 16, 20, 24, 28 >>> @@ -439,108 +513,84 @@ L(page_cross_less_vec): >>> cmpl $8, %edx >>> jae L(between_8_15) >>> cmpl $4, %edx >>> - jae L(between_4_7) >>> -L(between_2_3): >>> - /* Load as big endian to avoid branches. */ >>> - movzwl (%rdi), %eax >>> - movzwl (%rsi), %ecx >>> - shll $8, %eax >>> - shll $8, %ecx >>> - bswap %eax >>> - bswap %ecx >>> - movzbl -1(%rdi, %rdx), %edi >>> - movzbl -1(%rsi, %rdx), %esi >>> - orl %edi, %eax >>> - orl %esi, %ecx >>> - /* Subtraction is okay because the upper 8 bits are zero. */ >>> - subl %ecx, %eax >>> - ret >>> - .p2align 4 >>> -L(one_or_less): >>> - jb L(zero) >>> - movzbl (%rsi), %ecx >>> - movzbl (%rdi), %eax >>> - subl %ecx, %eax >>> + jb L(between_2_3) >>> + >>> + /* Load as big endian with overlapping movbe to avoid branches. >>> + */ >>> + movbe (%rdi), %eax >>> + movbe (%rsi), %ecx >>> + shlq $32, %rax >>> + shlq $32, %rcx >>> + movbe -4(%rdi, %rdx), %edi >>> + movbe -4(%rsi, %rdx), %esi >>> + orq %rdi, %rax >>> + orq %rsi, %rcx >>> + subq %rcx, %rax >>> + /* edx is guranteed to be positive int32 in range [4, 7]. */ >>> + cmovne %edx, %eax >>> + /* ecx is -1 if rcx > rax. Otherwise 0. */ >>> + sbbl %ecx, %ecx >>> + /* If rcx > rax, then ecx is 0 and eax is positive. If rcx == >>> + rax then eax and ecx are zero. If rax < rax then ecx is -1 so >>> + eax doesn't matter. */ >>> + orl %ecx, %eax >>> ret >>> >>> - .p2align 4 >>> + .p2align 4,, 8 >>> L(between_8_15): >>> # endif >>> /* If USE_AS_WMEMCMP fall through into 8-15 byte case. */ >>> - vmovq (%rdi), %XMM1 >>> - vmovq (%rsi), %XMM2 >>> - VPCMP $4, %XMM1, %XMM2, %k1 >>> + vmovq (%rdi), %xmm1 >>> + vmovq (%rsi), %xmm2 >>> + VPCMP $4, %xmm1, %xmm2, %k1 >>> kmovd %k1, %eax >>> testl %eax, %eax >>> - jnz L(return_vec_0) >>> + jnz L(return_vec_0_lv) >>> /* Use overlapping loads to avoid branches. */ >>> - leaq -8(%rdi, %rdx, CHAR_SIZE), %rdi >>> - leaq -8(%rsi, %rdx, CHAR_SIZE), %rsi >>> - vmovq (%rdi), %XMM1 >>> - vmovq (%rsi), %XMM2 >>> - VPCMP $4, %XMM1, %XMM2, %k1 >>> + vmovq -8(%rdi, %rdx, CHAR_SIZE), %xmm1 >>> + vmovq -8(%rsi, %rdx, CHAR_SIZE), %xmm2 >>> + VPCMP $4, %xmm1, %xmm2, %k1 >>> + addl $(CHAR_PER_VEC - (8 / CHAR_SIZE)), %edx >>> kmovd %k1, %eax >>> testl %eax, %eax >>> - jnz L(return_vec_0) >>> - ret >>> - >>> - .p2align 4 >>> -L(zero): >>> - xorl %eax, %eax >>> + jnz L(return_vec_0_end) >>> ret >>> >>> - .p2align 4 >>> + .p2align 4,, 8 >>> L(between_16_31): >>> /* From 16 to 31 bytes. No branch when size == 16. */ >>> - VMOVU (%rsi), %XMM2 >>> - VPCMP $4, (%rdi), %XMM2, %k1 >>> + >>> + /* Use movups to save code size. */ >>> + movups (%rsi), %xmm2 >>> + VPCMP $4, (%rdi), %xmm2, %k1 >>> kmovd %k1, %eax >>> testl %eax, %eax >>> - jnz L(return_vec_0) >>> - >>> + jnz L(return_vec_0_lv) >>> /* Use overlapping loads to avoid branches. */ >>> - >>> - VMOVU -16(%rsi, %rdx, CHAR_SIZE), %XMM2 >>> - leaq -16(%rdi, %rdx, CHAR_SIZE), %rdi >>> - leaq -16(%rsi, %rdx, CHAR_SIZE), %rsi >>> - VPCMP $4, (%rdi), %XMM2, %k1 >>> + movups -16(%rsi, %rdx, CHAR_SIZE), %xmm2 >>> + VPCMP $4, -16(%rdi, %rdx, CHAR_SIZE), %xmm2, %k1 >>> + addl $(CHAR_PER_VEC - (16 / CHAR_SIZE)), %edx >>> kmovd %k1, %eax >>> testl %eax, %eax >>> - jnz L(return_vec_0) >>> - ret >>> - >>> -# ifdef USE_AS_WMEMCMP >>> - .p2align 4 >>> -L(one_or_less): >>> - jb L(zero) >>> - movl (%rdi), %ecx >>> - xorl %edx, %edx >>> - cmpl (%rsi), %ecx >>> - je L(zero) >>> - setg %dl >>> - leal -1(%rdx, %rdx), %eax >>> + jnz L(return_vec_0_end) >>> ret >>> -# else >>> >>> - .p2align 4 >>> -L(between_4_7): >>> - /* Load as big endian with overlapping movbe to avoid branches. >>> - */ >>> - movbe (%rdi), %eax >>> - movbe (%rsi), %ecx >>> - shlq $32, %rax >>> - shlq $32, %rcx >>> - movbe -4(%rdi, %rdx), %edi >>> - movbe -4(%rsi, %rdx), %esi >>> - orq %rdi, %rax >>> - orq %rsi, %rcx >>> - subq %rcx, %rax >>> - jz L(zero_4_7) >>> - sbbl %eax, %eax >>> - orl $1, %eax >>> -L(zero_4_7): >>> +# ifndef USE_AS_WMEMCMP >>> +L(between_2_3): >>> + /* Load as big endian to avoid branches. */ >>> + movzwl (%rdi), %eax >>> + movzwl (%rsi), %ecx >>> + shll $8, %eax >>> + shll $8, %ecx >>> + bswap %eax >>> + bswap %ecx >>> + movzbl -1(%rdi, %rdx), %edi >>> + movzbl -1(%rsi, %rdx), %esi >>> + orl %edi, %eax >>> + orl %esi, %ecx >>> + /* Subtraction is okay because the upper 8 bits are zero. */ >>> + subl %ecx, %eax >>> ret >>> # endif >>> - >>> END (MEMCMP) >>> #endif >>> -- >>> 2.25.1 >>> >>> ping > ping