sysdeps/x86_64/multiarch/strrchr-evex.S

   1 /* strrchr/wcsrchr optimized with 256-bit EVEX instructions.
   2    Copyright (C) 2021-2022 Free Software Foundation, Inc.
   3    This file is part of the GNU C Library.
   4
   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.
   9
  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.
  14
  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/>.  */
  18
  19 #include <isa-level.h>
  20
  21 #if ISA_SHOULD_BUILD (4)
  22
  23 # include <sysdep.h>
  24
  25 # ifndef STRRCHR
  26 #  define STRRCHR       __strrchr_evex
  27 # endif
  28
  29 # include "x86-evex256-vecs.h"
  30
  31 # ifdef USE_AS_WCSRCHR
  32 #  define RCX_M cl
  33 #  define SHIFT_REG     rcx
  34 #  define VPCOMPRESS    vpcompressd
  35 #  define kunpck_2x     kunpckbw
  36 #  define kmov_2x       kmovd
  37 #  define maskz_2x      ecx
  38 #  define maskm_2x      eax
  39 #  define CHAR_SIZE     4
  40 #  define VPMIN vpminud
  41 #  define VPTESTN       vptestnmd
  42 #  define VPTEST        vptestmd
  43 #  define VPBROADCAST   vpbroadcastd
  44 #  define VPCMPEQ       vpcmpeqd
  45 #  define VPCMP vpcmpd
  46
  47 #  define USE_WIDE_CHAR
  48 # else
  49 #  define RCX_M ecx
  50 #  define SHIFT_REG     rdi
  51 #  define VPCOMPRESS    vpcompressb
  52 #  define kunpck_2x     kunpckdq
  53 #  define kmov_2x       kmovq
  54 #  define maskz_2x      rcx
  55 #  define maskm_2x      rax
  56
  57 #  define CHAR_SIZE     1
  58 #  define VPMIN vpminub
  59 #  define VPTESTN       vptestnmb
  60 #  define VPTEST        vptestmb
  61 #  define VPBROADCAST   vpbroadcastb
  62 #  define VPCMPEQ       vpcmpeqb
  63 #  define VPCMP vpcmpb
  64 # endif
  65
  66 # include "reg-macros.h"
  67
  68 # define VMATCH VMM(0)
  69 # define CHAR_PER_VEC   (VEC_SIZE / CHAR_SIZE)
  70 # define PAGE_SIZE      4096
  71
  72         .section SECTION(.text), "ax", @progbits
  73 ENTRY_P2ALIGN(STRRCHR, 6)
  74         movl    %edi, %eax
  75         /* Broadcast CHAR to VMATCH.  */
  76         VPBROADCAST %esi, %VMATCH
  77
  78         andl    $(PAGE_SIZE - 1), %eax
  79         cmpl    $(PAGE_SIZE - VEC_SIZE), %eax
  80         jg      L(cross_page_boundary)
  81
  82         VMOVU   (%rdi), %VMM(1)
  83         /* k0 has a 1 for each zero CHAR in VEC(1).  */
  84         VPTESTN %VMM(1), %VMM(1), %k0
  85         KMOV    %k0, %VRSI
  86         test    %VRSI, %VRSI
  87         jz      L(aligned_more)
  88         /* fallthrough: zero CHAR in first VEC.  */
  89 L(page_cross_return):
  90         /* K1 has a 1 for each search CHAR match in VEC(1).  */
  91         VPCMPEQ %VMATCH, %VMM(1), %k1
  92         KMOV    %k1, %VRAX
  93         /* Build mask up until first zero CHAR (used to mask of
  94            potential search CHAR matches past the end of the string).
  95          */
  96         blsmsk  %VRSI, %VRSI
  97         and     %VRSI, %VRAX
  98         jz      L(ret0)
  99         /* Get last match (the `and` removed any out of bounds matches).
 100          */
 101         bsr     %VRAX, %VRAX
 102 # ifdef USE_AS_WCSRCHR
 103         leaq    (%rdi, %rax, CHAR_SIZE), %rax
 104 # else
 105         addq    %rdi, %rax
 106 # endif
 107 L(ret0):
 108         ret
 109
 110         /* Returns for first vec x1/x2/x3 have hard coded backward
 111            search path for earlier matches.  */
 112         .p2align 4,, 6
 113 L(first_vec_x1):
 114         VPCMPEQ %VMATCH, %VMM(2), %k1
 115         KMOV    %k1, %VRAX
 116         blsmsk  %VRCX, %VRCX
 117         /* eax non-zero if search CHAR in range.  */
 118         and     %VRCX, %VRAX
 119         jnz     L(first_vec_x1_return)
 120
 121         /* fallthrough: no match in VEC(2) then need to check for
 122            earlier matches (in VEC(1)).  */
 123         .p2align 4,, 4
 124 L(first_vec_x0_test):
 125         VPCMPEQ %VMATCH, %VMM(1), %k1
 126         KMOV    %k1, %VRAX
 127         test    %VRAX, %VRAX
 128         jz      L(ret1)
 129         bsr     %VRAX, %VRAX
 130 # ifdef USE_AS_WCSRCHR
 131         leaq    (%rsi, %rax, CHAR_SIZE), %rax
 132 # else
 133         addq    %rsi, %rax
 134 # endif
 135 L(ret1):
 136         ret
 137
 138         .p2align 4,, 10
 139 L(first_vec_x1_or_x2):
 140         VPCMPEQ %VMM(3), %VMATCH, %k3
 141         VPCMPEQ %VMM(2), %VMATCH, %k2
 142         /* K2 and K3 have 1 for any search CHAR match. Test if any
 143            matches between either of them. Otherwise check VEC(1).  */
 144         KORTEST %k2, %k3
 145         jz      L(first_vec_x0_test)
 146
 147         /* Guranteed that VEC(2) and VEC(3) are within range so merge
 148            the two bitmasks then get last result.  */
 149         kunpck_2x %k2, %k3, %k3
 150         kmov_2x %k3, %maskm_2x
 151         bsr     %maskm_2x, %maskm_2x
 152         leaq    (VEC_SIZE * 1)(%r8, %rax, CHAR_SIZE), %rax
 153         ret
 154
 155         .p2align 4,, 7
 156 L(first_vec_x3):
 157         VPCMPEQ %VMATCH, %VMM(4), %k1
 158         KMOV    %k1, %VRAX
 159         blsmsk  %VRCX, %VRCX
 160         /* If no search CHAR match in range check VEC(1)/VEC(2)/VEC(3).
 161          */
 162         and     %VRCX, %VRAX
 163         jz      L(first_vec_x1_or_x2)
 164         bsr     %VRAX, %VRAX
 165         leaq    (VEC_SIZE * 3)(%rdi, %rax, CHAR_SIZE), %rax
 166         ret
 167
 168
 169         .p2align 4,, 6
 170 L(first_vec_x0_x1_test):
 171         VPCMPEQ %VMATCH, %VMM(2), %k1
 172         KMOV    %k1, %VRAX
 173         /* Check VEC(2) for last match first. If no match try VEC(1).
 174          */
 175         test    %VRAX, %VRAX
 176         jz      L(first_vec_x0_test)
 177         .p2align 4,, 4
 178 L(first_vec_x1_return):
 179         bsr     %VRAX, %VRAX
 180         leaq    (VEC_SIZE)(%rdi, %rax, CHAR_SIZE), %rax
 181         ret
 182
 183
 184         .p2align 4,, 10
 185 L(first_vec_x2):
 186         VPCMPEQ %VMATCH, %VMM(3), %k1
 187         KMOV    %k1, %VRAX
 188         blsmsk  %VRCX, %VRCX
 189         /* Check VEC(3) for last match first. If no match try
 190            VEC(2)/VEC(1).  */
 191         and     %VRCX, %VRAX
 192         jz      L(first_vec_x0_x1_test)
 193         bsr     %VRAX, %VRAX
 194         leaq    (VEC_SIZE * 2)(%rdi, %rax, CHAR_SIZE), %rax
 195         ret
 196
 197
 198         .p2align 4,, 12
 199 L(aligned_more):
 200 L(page_cross_continue):
 201         /* Need to keep original pointer incase VEC(1) has last match.
 202          */
 203         movq    %rdi, %rsi
 204         andq    $-VEC_SIZE, %rdi
 205
 206         VMOVU   VEC_SIZE(%rdi), %VMM(2)
 207         VPTESTN %VMM(2), %VMM(2), %k0
 208         KMOV    %k0, %VRCX
 209
 210         test    %VRCX, %VRCX
 211         jnz     L(first_vec_x1)
 212
 213         VMOVU   (VEC_SIZE * 2)(%rdi), %VMM(3)
 214         VPTESTN %VMM(3), %VMM(3), %k0
 215         KMOV    %k0, %VRCX
 216
 217         test    %VRCX, %VRCX
 218         jnz     L(first_vec_x2)
 219
 220         VMOVU   (VEC_SIZE * 3)(%rdi), %VMM(4)
 221         VPTESTN %VMM(4), %VMM(4), %k0
 222         KMOV    %k0, %VRCX
 223         movq    %rdi, %r8
 224         test    %VRCX, %VRCX
 225         jnz     L(first_vec_x3)
 226
 227         andq    $-(VEC_SIZE * 2), %rdi
 228         .p2align 4,, 10
 229 L(first_aligned_loop):
 230         /* Preserve VEC(1), VEC(2), VEC(3), and VEC(4) until we can
 231            gurantee they don't store a match.  */
 232         VMOVA   (VEC_SIZE * 4)(%rdi), %VMM(5)
 233         VMOVA   (VEC_SIZE * 5)(%rdi), %VMM(6)
 234
 235         VPCMPEQ %VMM(5), %VMATCH, %k2
 236         vpxord  %VMM(6), %VMATCH, %VMM(7)
 237
 238         VPMIN   %VMM(5), %VMM(6), %VMM(8)
 239         VPMIN   %VMM(8), %VMM(7), %VMM(7)
 240
 241         VPTESTN %VMM(7), %VMM(7), %k1
 242         subq    $(VEC_SIZE * -2), %rdi
 243         KORTEST %k1, %k2
 244         jz      L(first_aligned_loop)
 245
 246         VPCMPEQ %VMM(6), %VMATCH, %k3
 247         VPTESTN %VMM(8), %VMM(8), %k1
 248
 249         /* If k1 is zero, then we found a CHAR match but no null-term.
 250            We can now safely throw out VEC1-4.  */
 251         KTEST   %k1, %k1
 252         jz      L(second_aligned_loop_prep)
 253
 254         KORTEST %k2, %k3
 255         jnz     L(return_first_aligned_loop)
 256
 257
 258         .p2align 4,, 6
 259 L(first_vec_x1_or_x2_or_x3):
 260         VPCMPEQ %VMM(4), %VMATCH, %k4
 261         KMOV    %k4, %VRAX
 262         bsr     %VRAX, %VRAX
 263         jz      L(first_vec_x1_or_x2)
 264         leaq    (VEC_SIZE * 3)(%r8, %rax, CHAR_SIZE), %rax
 265         ret
 266
 267
 268         .p2align 4,, 8
 269 L(return_first_aligned_loop):
 270         VPTESTN %VMM(5), %VMM(5), %k0
 271
 272         /* Combined results from VEC5/6.  */
 273         kunpck_2x %k0, %k1, %k0
 274         kmov_2x %k0, %maskz_2x
 275
 276         blsmsk  %maskz_2x, %maskz_2x
 277         kunpck_2x %k2, %k3, %k3
 278         kmov_2x %k3, %maskm_2x
 279         and     %maskz_2x, %maskm_2x
 280         jz      L(first_vec_x1_or_x2_or_x3)
 281
 282         bsr     %maskm_2x, %maskm_2x
 283         leaq    (VEC_SIZE * 2)(%rdi, %rax, CHAR_SIZE), %rax
 284         ret
 285
 286         .p2align 4
 287         /* We can throw away the work done for the first 4x checks here
 288            as we have a later match. This is the 'fast' path persay.
 289          */
 290 L(second_aligned_loop_prep):
 291 L(second_aligned_loop_set_furthest_match):
 292         movq    %rdi, %rsi
 293         /* Ideally we would safe k2/k3 but `kmov/kunpck` take uops on
 294            port0 and have noticable overhead in the loop.  */
 295         VMOVA   %VMM(5), %VMM(7)
 296         VMOVA   %VMM(6), %VMM(8)
 297         .p2align 4
 298 L(second_aligned_loop):
 299         VMOVU   (VEC_SIZE * 4)(%rdi), %VMM(5)
 300         VMOVU   (VEC_SIZE * 5)(%rdi), %VMM(6)
 301         VPCMPEQ %VMM(5), %VMATCH, %k2
 302         vpxord  %VMM(6), %VMATCH, %VMM(3)
 303
 304         VPMIN   %VMM(5), %VMM(6), %VMM(4)
 305         VPMIN   %VMM(3), %VMM(4), %VMM(3)
 306
 307         VPTESTN %VMM(3), %VMM(3), %k1
 308         subq    $(VEC_SIZE * -2), %rdi
 309         KORTEST %k1, %k2
 310         jz      L(second_aligned_loop)
 311         VPCMPEQ %VMM(6), %VMATCH, %k3
 312         VPTESTN %VMM(4), %VMM(4), %k1
 313         KTEST   %k1, %k1
 314         jz      L(second_aligned_loop_set_furthest_match)
 315
 316         /* branch here because we know we have a match in VEC7/8 but
 317            might not in VEC5/6 so the latter is expected to be less
 318            likely.  */
 319         KORTEST %k2, %k3
 320         jnz     L(return_new_match)
 321
 322 L(return_old_match):
 323         VPCMPEQ %VMM(8), %VMATCH, %k0
 324         KMOV    %k0, %VRCX
 325         bsr     %VRCX, %VRCX
 326         jnz     L(return_old_match_ret)
 327
 328         VPCMPEQ %VMM(7), %VMATCH, %k0
 329         KMOV    %k0, %VRCX
 330         bsr     %VRCX, %VRCX
 331         subq    $VEC_SIZE, %rsi
 332 L(return_old_match_ret):
 333         leaq    (VEC_SIZE * 3)(%rsi, %rcx, CHAR_SIZE), %rax
 334         ret
 335
 336         .p2align 4,, 10
 337 L(return_new_match):
 338         VPTESTN %VMM(5), %VMM(5), %k0
 339
 340         /* Combined results from VEC5/6.  */
 341         kunpck_2x %k0, %k1, %k0
 342         kmov_2x %k0, %maskz_2x
 343
 344         blsmsk  %maskz_2x, %maskz_2x
 345         kunpck_2x %k2, %k3, %k3
 346         kmov_2x %k3, %maskm_2x
 347
 348         /* Match at end was out-of-bounds so use last known match.  */
 349         and     %maskz_2x, %maskm_2x
 350         jz      L(return_old_match)
 351
 352         bsr     %maskm_2x, %maskm_2x
 353         leaq    (VEC_SIZE * 2)(%rdi, %rax, CHAR_SIZE), %rax
 354         ret
 355
 356         .p2align 4,, 4
 357 L(cross_page_boundary):
 358         xorq    %rdi, %rax
 359         mov     $-1, %VRDX
 360         VMOVU   (PAGE_SIZE - VEC_SIZE)(%rax), %VMM(6)
 361         VPTESTN %VMM(6), %VMM(6), %k0
 362         KMOV    %k0, %VRSI
 363
 364 # ifdef USE_AS_WCSRCHR
 365         movl    %edi, %ecx
 366         and     $(VEC_SIZE - 1), %ecx
 367         shrl    $2, %ecx
 368 # endif
 369         shlx    %VGPR(SHIFT_REG), %VRDX, %VRDX
 370
 371 # ifdef USE_AS_WCSRCHR
 372         kmovb   %edx, %k1
 373 # else
 374         KMOV    %VRDX, %k1
 375 # endif
 376
 377         /* Need to adjust result to VEC(1) so it can be re-used by
 378            L(return_vec_x0_test).  The alternative is to collect VEC(1)
 379            will a page cross load which is far more expensive.  */
 380         VPCOMPRESS %VMM(6), %VMM(1){%k1}{z}
 381
 382         /* We could technically just jmp back after the vpcompress but
 383            it doesn't save any 16-byte blocks.  */
 384         shrx    %VGPR(SHIFT_REG), %VRSI, %VRSI
 385         test    %VRSI, %VRSI
 386         jz      L(page_cross_continue)
 387
 388         /* Duplicate of return logic from ENTRY. Doesn't cause spill to
 389            next cache line so might as well copy it here.  */
 390         VPCMPEQ %VMATCH, %VMM(1), %k1
 391         KMOV    %k1, %VRAX
 392         blsmsk  %VRSI, %VRSI
 393         and     %VRSI, %VRAX
 394         jz      L(ret_page_cross)
 395         bsr     %VRAX, %VRAX
 396 # ifdef USE_AS_WCSRCHR
 397         leaq    (%rdi, %rax, CHAR_SIZE), %rax
 398 # else
 399         addq    %rdi, %rax
 400 # endif
 401 L(ret_page_cross):
 402         ret
 403         /* 1 byte till next cache line.  */
 404 END(STRRCHR)
 405 #endif