| // Copyright 2018 The Go Authors. All rights reserved. |
| // Use of this source code is governed by a BSD-style |
| // license that can be found in the LICENSE file. |
| |
| // +build ppc64 ppc64le |
| |
| #include "go_asm.h" |
| #include "textflag.h" |
| |
| TEXT ·IndexByte(SB),NOSPLIT|NOFRAME,$0-40 |
| MOVD b_base+0(FP), R3 // R3 = byte array pointer |
| MOVD b_len+8(FP), R4 // R4 = length |
| MOVBZ c+24(FP), R5 // R5 = byte |
| MOVD $ret+32(FP), R14 // R14 = &ret |
| BR indexbytebody<>(SB) |
| |
| TEXT ·IndexByteString(SB),NOSPLIT|NOFRAME,$0-32 |
| MOVD s_base+0(FP), R3 // R3 = string |
| MOVD s_len+8(FP), R4 // R4 = length |
| MOVBZ c+16(FP), R5 // R5 = byte |
| MOVD $ret+24(FP), R14 // R14 = &ret |
| BR indexbytebody<>(SB) |
| |
| TEXT indexbytebody<>(SB),NOSPLIT|NOFRAME,$0-0 |
| MOVD R3,R17 // Save base address for calculating the index later. |
| RLDICR $0,R3,$60,R8 // Align address to doubleword boundary in R8. |
| RLDIMI $8,R5,$48,R5 // Replicating the byte across the register. |
| ADD R4,R3,R7 // Last acceptable address in R7. |
| DCBT (R8) // Prepare cache line. |
| |
| RLDIMI $16,R5,$32,R5 |
| CMPU R4,$32 // Check if it's a small string (≤32 bytes). Those will be processed differently. |
| MOVD $-1,R9 |
| WORD $0x54661EB8 // Calculate padding in R6 (rlwinm r6,r3,3,26,28). |
| RLDIMI $32,R5,$0,R5 |
| MOVD R7,R10 // Save last acceptable address in R10 for later. |
| ADD $-1,R7,R7 |
| #ifdef GOARCH_ppc64le |
| SLD R6,R9,R9 // Prepare mask for Little Endian |
| #else |
| SRD R6,R9,R9 // Same for Big Endian |
| #endif |
| BLE small_string // Jump to the small string case if it's ≤32 bytes. |
| |
| // If we are 64-byte aligned, branch to qw_align just to get the auxiliary values |
| // in V0, V1 and V10, then branch to the preloop. |
| ANDCC $63,R3,R11 |
| BEQ CR0,qw_align |
| RLDICL $0,R3,$61,R11 |
| |
| MOVD 0(R8),R12 // Load one doubleword from the aligned address in R8. |
| CMPB R12,R5,R3 // Check for a match. |
| AND R9,R3,R3 // Mask bytes below s_base |
| RLDICL $0,R7,$61,R6 // length-1 |
| RLDICR $0,R7,$60,R7 // Last doubleword in R7 |
| CMPU R3,$0,CR7 // If we have a match, jump to the final computation |
| BNE CR7,done |
| ADD $8,R8,R8 |
| ADD $-8,R4,R4 |
| ADD R4,R11,R4 |
| |
| // Check for quadword alignment |
| ANDCC $15,R8,R11 |
| BEQ CR0,qw_align |
| |
| // Not aligned, so handle the next doubleword |
| MOVD 0(R8),R12 |
| CMPB R12,R5,R3 |
| CMPU R3,$0,CR7 |
| BNE CR7,done |
| ADD $8,R8,R8 |
| ADD $-8,R4,R4 |
| |
| // Either quadword aligned or 64-byte at this point. We can use LVX. |
| qw_align: |
| |
| // Set up auxiliary data for the vectorized algorithm. |
| VSPLTISB $0,V0 // Replicate 0 across V0 |
| VSPLTISB $3,V10 // Use V10 as control for VBPERMQ |
| MTVRD R5,V1 |
| LVSL (R0+R0),V11 |
| VSLB V11,V10,V10 |
| VSPLTB $7,V1,V1 // Replicate byte across V1 |
| CMPU R4, $64 // If len ≤ 64, don't use the vectorized loop |
| BLE tail |
| |
| // We will load 4 quardwords per iteration in the loop, so check for |
| // 64-byte alignment. If 64-byte aligned, then branch to the preloop. |
| ANDCC $63,R8,R11 |
| BEQ CR0,preloop |
| |
| // Not 64-byte aligned. Load one quadword at a time until aligned. |
| LVX (R8+R0),V4 |
| VCMPEQUBCC V1,V4,V6 // Check for byte in V4 |
| BNE CR6,found_qw_align |
| ADD $16,R8,R8 |
| ADD $-16,R4,R4 |
| |
| ANDCC $63,R8,R11 |
| BEQ CR0,preloop |
| LVX (R8+R0),V4 |
| VCMPEQUBCC V1,V4,V6 // Check for byte in V4 |
| BNE CR6,found_qw_align |
| ADD $16,R8,R8 |
| ADD $-16,R4,R4 |
| |
| ANDCC $63,R8,R11 |
| BEQ CR0,preloop |
| LVX (R8+R0),V4 |
| VCMPEQUBCC V1,V4,V6 // Check for byte in V4 |
| BNE CR6,found_qw_align |
| ADD $-16,R4,R4 |
| ADD $16,R8,R8 |
| |
| // 64-byte aligned. Prepare for the main loop. |
| preloop: |
| CMPU R4,$64 |
| BLE tail // If len ≤ 64, don't use the vectorized loop |
| |
| // We are now aligned to a 64-byte boundary. We will load 4 quadwords |
| // per loop iteration. The last doubleword is in R10, so our loop counter |
| // starts at (R10-R8)/64. |
| SUB R8,R10,R6 |
| SRD $6,R6,R9 // Loop counter in R9 |
| MOVD R9,CTR |
| |
| ADD $-64,R8,R8 // Adjust index for loop entry |
| MOVD $16,R11 // Load offsets for the vector loads |
| MOVD $32,R9 |
| MOVD $48,R7 |
| |
| // Main loop we will load 64 bytes per iteration |
| loop: |
| ADD $64,R8,R8 // Fuse addi+lvx for performance |
| LVX (R8+R0),V2 // Load 4 16-byte vectors |
| LVX (R8+R11),V3 |
| VCMPEQUB V1,V2,V6 // Look for byte in each vector |
| VCMPEQUB V1,V3,V7 |
| |
| LVX (R8+R9),V4 |
| LVX (R8+R7),V5 |
| VCMPEQUB V1,V4,V8 |
| VCMPEQUB V1,V5,V9 |
| |
| VOR V6,V7,V11 // Compress the result in a single vector |
| VOR V8,V9,V12 |
| VOR V11,V12,V13 |
| VCMPEQUBCC V0,V13,V14 // Check for byte |
| BGE CR6,found |
| BC 16,0,loop // bdnz loop |
| |
| // Handle the tailing bytes or R4 ≤ 64 |
| RLDICL $0,R6,$58,R4 |
| ADD $64,R8,R8 |
| tail: |
| CMPU R4,$0 |
| BEQ notfound |
| LVX (R8+R0),V4 |
| VCMPEQUBCC V1,V4,V6 |
| BNE CR6,found_qw_align |
| ADD $16,R8,R8 |
| CMPU R4,$16,CR6 |
| BLE CR6,notfound |
| ADD $-16,R4,R4 |
| |
| LVX (R8+R0),V4 |
| VCMPEQUBCC V1,V4,V6 |
| BNE CR6,found_qw_align |
| ADD $16,R8,R8 |
| CMPU R4,$16,CR6 |
| BLE CR6,notfound |
| ADD $-16,R4,R4 |
| |
| LVX (R8+R0),V4 |
| VCMPEQUBCC V1,V4,V6 |
| BNE CR6,found_qw_align |
| ADD $16,R8,R8 |
| CMPU R4,$16,CR6 |
| BLE CR6,notfound |
| ADD $-16,R4,R4 |
| |
| LVX (R8+R0),V4 |
| VCMPEQUBCC V1,V4,V6 |
| BNE CR6,found_qw_align |
| |
| notfound: |
| MOVD $-1,R3 |
| MOVD R3,(R14) |
| RET |
| |
| found: |
| // We will now compress the results into a single doubleword, |
| // so it can be moved to a GPR for the final index calculation. |
| |
| // The bytes in V6-V9 are either 0x00 or 0xFF. So, permute the |
| // first bit of each byte into bits 48-63. |
| VBPERMQ V6,V10,V6 |
| VBPERMQ V7,V10,V7 |
| VBPERMQ V8,V10,V8 |
| VBPERMQ V9,V10,V9 |
| |
| // Shift each 16-bit component into its correct position for |
| // merging into a single doubleword. |
| #ifdef GOARCH_ppc64le |
| VSLDOI $2,V7,V7,V7 |
| VSLDOI $4,V8,V8,V8 |
| VSLDOI $6,V9,V9,V9 |
| #else |
| VSLDOI $6,V6,V6,V6 |
| VSLDOI $4,V7,V7,V7 |
| VSLDOI $2,V8,V8,V8 |
| #endif |
| |
| // Merge V6-V9 into a single doubleword and move to a GPR. |
| VOR V6,V7,V11 |
| VOR V8,V9,V4 |
| VOR V4,V11,V4 |
| MFVRD V4,R3 |
| |
| #ifdef GOARCH_ppc64le |
| ADD $-1,R3,R11 |
| ANDN R3,R11,R11 |
| POPCNTD R11,R11 // Count trailing zeros (Little Endian). |
| #else |
| CNTLZD R3,R11 // Count leading zeros (Big Endian). |
| #endif |
| ADD R8,R11,R3 // Calculate byte address |
| |
| return: |
| SUB R17,R3 |
| MOVD R3,(R14) |
| RET |
| |
| found_qw_align: |
| // Use the same algorithm as above. Compress the result into |
| // a single doubleword and move it to a GPR for the final |
| // calculation. |
| VBPERMQ V6,V10,V6 |
| |
| #ifdef GOARCH_ppc64le |
| MFVRD V6,R3 |
| ADD $-1,R3,R11 |
| ANDN R3,R11,R11 |
| POPCNTD R11,R11 |
| #else |
| VSLDOI $6,V6,V6,V6 |
| MFVRD V6,R3 |
| CNTLZD R3,R11 |
| #endif |
| ADD R8,R11,R3 |
| CMPU R11,R4 |
| BLT return |
| BR notfound |
| |
| done: |
| // At this point, R3 has 0xFF in the same position as the byte we are |
| // looking for in the doubleword. Use that to calculate the exact index |
| // of the byte. |
| #ifdef GOARCH_ppc64le |
| ADD $-1,R3,R11 |
| ANDN R3,R11,R11 |
| POPCNTD R11,R11 // Count trailing zeros (Little Endian). |
| #else |
| CNTLZD R3,R11 // Count leading zeros (Big Endian). |
| #endif |
| CMPU R8,R7 // Check if we are at the last doubleword. |
| SRD $3,R11 // Convert trailing zeros to bytes. |
| ADD R11,R8,R3 |
| CMPU R11,R6,CR7 // If at the last doubleword, check the byte offset. |
| BNE return |
| BLE CR7,return |
| BR notfound |
| |
| small_string: |
| // We unroll this loop for better performance. |
| CMPU R4,$0 // Check for length=0 |
| BEQ notfound |
| |
| MOVD 0(R8),R12 // Load one doubleword from the aligned address in R8. |
| CMPB R12,R5,R3 // Check for a match. |
| AND R9,R3,R3 // Mask bytes below s_base. |
| CMPU R3,$0,CR7 // If we have a match, jump to the final computation. |
| RLDICL $0,R7,$61,R6 // length-1 |
| RLDICR $0,R7,$60,R7 // Last doubleword in R7. |
| CMPU R8,R7 |
| BNE CR7,done |
| BEQ notfound // Hit length. |
| |
| MOVDU 8(R8),R12 |
| CMPB R12,R5,R3 |
| CMPU R3,$0,CR6 |
| CMPU R8,R7 |
| BNE CR6,done |
| BEQ notfound |
| |
| MOVDU 8(R8),R12 |
| CMPB R12,R5,R3 |
| CMPU R3,$0,CR6 |
| CMPU R8,R7 |
| BNE CR6,done |
| BEQ notfound |
| |
| MOVDU 8(R8),R12 |
| CMPB R12,R5,R3 |
| CMPU R3,$0,CR6 |
| CMPU R8,R7 |
| BNE CR6,done |
| BEQ notfound |
| |
| MOVDU 8(R8),R12 |
| CMPB R12,R5,R3 |
| CMPU R3,$0,CR6 |
| BNE CR6,done |
| BR notfound |
| |
