Debian Codegraph @

mpn/powerpc64/vmx/popcount.asm

raw
1 dnl PowerPC-32/VMX and PowerPC-64/VMX mpn_popcount.
2
3 dnl Copyright 2006, 2010 Free Software Foundation, Inc.
4
5 dnl This file is part of the GNU MP Library.
6 dnl
7 dnl The GNU MP Library is free software; you can redistribute it and/or modify
8 dnl it under the terms of either:
9 dnl
10 dnl * the GNU Lesser General Public License as published by the Free
11 dnl Software Foundation; either version 3 of the License, or (at your
12 dnl option) any later version.
13 dnl
14 dnl or
15 dnl
16 dnl * the GNU General Public License as published by the Free Software
17 dnl Foundation; either version 2 of the License, or (at your option) any
18 dnl later version.
19 dnl
20 dnl or both in parallel, as here.
21 dnl
22 dnl The GNU MP Library is distributed in the hope that it will be useful, but
23 dnl WITHOUT ANY WARRANTY; without even the implied warranty of MERCHANTABILITY
24 dnl or FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License
25 dnl for more details.
26 dnl
27 dnl You should have received copies of the GNU General Public License and the
28 dnl GNU Lesser General Public License along with the GNU MP Library. If not,
29 dnl see https://www.gnu.org/licenses/.
30
31 include(`../config.m4')
32
33 C cycles/limb
34 C 7400,7410 (G4): ?
35 C 744x,745x (G4+): 1.125
36 C 970 (G5): 2.25
37
38 C TODO
39 C * Rewrite the awkward huge n outer loop code.
40 C * Two lvx, two vperm, and two vxor could make us a similar hamdist.
41 C * Compress cnsts table in 64-bit mode, only half the values are needed.
42
43 define(`GMP_LIMB_BYTES', eval(GMP_LIMB_BITS/8))
44 define(`LIMBS_PER_VR', eval(16/GMP_LIMB_BYTES))
45 define(`LIMBS_PER_2VR', eval(32/GMP_LIMB_BYTES))
46
47 define(`OPERATION_popcount')
48
49 define(`ap', `r3')
50 define(`n', `r4')
51
52 define(`rtab', `v10')
53 define(`cnt4', `v11')
54
55 ifelse(GMP_LIMB_BITS,32,`
56 define(`LIMB32',` $1')
57 define(`LIMB64',`')
58 ',`
59 define(`LIMB32',`')
60 define(`LIMB64',` $1')
61 ')
62
63 C The inner loop handles up to 2^34 bits, i.e., 2^31 64-limbs, due to overflow
64 C in vsum4ubs. For large operands, we work in chunks, of size LIMBS_PER_CHUNK.
65 define(`LIMBS_PER_CHUNK', 0x1000)
66 define(`LIMBS_CHUNK_THRES', 0x1001)
67
68 ASM_START()
69 PROLOGUE(mpn_popcount,toc)
70 mfspr r10, 256
71 oris r0, r10, 0xfffc C Set VRSAVE bit 0-13
72 mtspr 256, r0
73
74 ifdef(`HAVE_ABI_mode32',
75 ` rldicl n, n, 0, 32') C zero extend n
76
77 C Load various constants into vector registers
78 LEAL( r11, cnsts)
79 li r12, 16
80 vspltisb cnt4, 4 C 0x0404...04 used as shift count
81
82 li r7, 160
83 lvx rtab, 0, r11
84
85 LIMB64(`lis r0, LIMBS_CHUNK_THRES ')
86 LIMB64(`cmpd cr7, n, r0 ')
87
88 lvx v0, 0, ap
89 addi r7, r11, 80
90 rlwinm r6, ap, 2,26,29
91 lvx v8, r7, r6
92 vand v0, v0, v8
93
94 LIMB32(`rlwinm r8, ap, 30,30,31 ')
95 LIMB64(`rlwinm r8, ap, 29,31,31 ')
96 add n, n, r8 C compensate n for rounded down `ap'
97
98 vxor v1, v1, v1
99 li r8, 0 C grand total count
100
101 vxor v12, v12, v12 C zero total count
102 vxor v13, v13, v13 C zero total count
103
104 addic. n, n, -LIMBS_PER_VR
105 ble L(sum)
106
107 addic. n, n, -LIMBS_PER_VR
108 ble L(lsum)
109
110 C For 64-bit machines, handle huge n that would overflow vsum4ubs
111 LIMB64(`ble cr7, L(small) ')
112 LIMB64(`addis r9, n, -LIMBS_PER_CHUNK ') C remaining n
113 LIMB64(`lis n, LIMBS_PER_CHUNK ')
114
115 ALIGN(16)
116 L(small):
117 LIMB32(`srwi r7, n, 3 ') C loop count corresponding to n
118 LIMB64(`srdi r7, n, 2 ') C loop count corresponding to n
119 addi r7, r7, 1
120 mtctr r7 C copy n to count register
121 b L(ent)
122
123 ALIGN(16)
124 L(top):
125 lvx v0, 0, ap
126 L(ent): lvx v1, r12, ap
127 addi ap, ap, 32
128 vsrb v8, v0, cnt4
129 vsrb v9, v1, cnt4
130 vperm v2, rtab, rtab, v0
131 vperm v3, rtab, rtab, v8
132 vperm v4, rtab, rtab, v1
133 vperm v5, rtab, rtab, v9
134 vaddubm v6, v2, v3
135 vaddubm v7, v4, v5
136 vsum4ubs v12, v6, v12
137 vsum4ubs v13, v7, v13
138 bdnz L(top)
139
140 andi. n, n, eval(LIMBS_PER_2VR-1)
141 beq L(rt)
142
143 lvx v0, 0, ap
144 vxor v1, v1, v1
145 cmpwi n, LIMBS_PER_VR
146 ble L(sum)
147 L(lsum):
148 vor v1, v0, v0
149 lvx v0, r12, ap
150 L(sum):
151 LIMB32(`rlwinm r6, n, 4,26,27 ')
152 LIMB64(`rlwinm r6, n, 5,26,26 ')
153 addi r7, r11, 16
154 lvx v8, r7, r6
155 vand v0, v0, v8
156 vsrb v8, v0, cnt4
157 vsrb v9, v1, cnt4
158 vperm v2, rtab, rtab, v0
159 vperm v3, rtab, rtab, v8
160 vperm v4, rtab, rtab, v1
161 vperm v5, rtab, rtab, v9
162 vaddubm v6, v2, v3
163 vaddubm v7, v4, v5
164 vsum4ubs v12, v6, v12
165 vsum4ubs v13, v7, v13
166
167 ALIGN(16)
168 L(rt): vadduwm v3, v12, v13
169 li r7, -16 C FIXME: does all ppc32 and ppc64 ABIs
170 stvx v3, r7, r1 C FIXME: ...support storing below sp?
171
172 lwz r7, -16(r1)
173 add r8, r8, r7
174 lwz r7, -12(r1)
175 add r8, r8, r7
176 lwz r7, -8(r1)
177 add r8, r8, r7
178 lwz r7, -4(r1)
179 add r8, r8, r7
180
181 C Handle outer loop for huge n. We inherit cr7 and r0 from above.
182 LIMB64(`ble cr7, L(ret)
183 vxor v12, v12, v12 C zero total count
184 vxor v13, v13, v13 C zero total count
185 mr n, r9
186 cmpd cr7, n, r0
187 ble cr7, L(2)
188 addis r9, n, -LIMBS_PER_CHUNK C remaining n
189 lis n, LIMBS_PER_CHUNK
190 L(2): srdi r7, n, 2 C loop count corresponding to n
191 mtctr r7 C copy n to count register
192 b L(top)
193 ')
194
195 ALIGN(16)
196 L(ret): mr r3, r8
197 mtspr 256, r10
198 blr
199 EPILOGUE()
200
201 DEF_OBJECT(cnsts,16)
202 C Counts for vperm
203 .byte 0x00,0x01,0x01,0x02,0x01,0x02,0x02,0x03
204 .byte 0x01,0x02,0x02,0x03,0x02,0x03,0x03,0x04
205 C Masks for high end of number
206 .byte 0xff,0xff,0xff,0xff,0xff,0xff,0xff,0xff
207 .byte 0xff,0xff,0xff,0xff,0xff,0xff,0xff,0xff
208
209 .byte 0xff,0xff,0xff,0xff,0x00,0x00,0x00,0x00
210 .byte 0x00,0x00,0x00,0x00,0x00,0x00,0x00,0x00
211
212 .byte 0xff,0xff,0xff,0xff,0xff,0xff,0xff,0xff
213 .byte 0x00,0x00,0x00,0x00,0x00,0x00,0x00,0x00
214
215 .byte 0xff,0xff,0xff,0xff,0xff,0xff,0xff,0xff
216 .byte 0xff,0xff,0xff,0xff,0x00,0x00,0x00,0x00
217 C Masks for low end of number
218 .byte 0xff,0xff,0xff,0xff,0xff,0xff,0xff,0xff
219 .byte 0xff,0xff,0xff,0xff,0xff,0xff,0xff,0xff
220
221 .byte 0x00,0x00,0x00,0x00,0xff,0xff,0xff,0xff
222 .byte 0xff,0xff,0xff,0xff,0xff,0xff,0xff,0xff
223
224 .byte 0x00,0x00,0x00,0x00,0x00,0x00,0x00,0x00
225 .byte 0xff,0xff,0xff,0xff,0xff,0xff,0xff,0xff
226
227 .byte 0x00,0x00,0x00,0x00,0x00,0x00,0x00,0x00
228 .byte 0x00,0x00,0x00,0x00,0xff,0xff,0xff,0xff
229 END_OBJECT(cnsts)
230 ASM_END()