Debian Codegraph @

gmp4/mpn/x86_64/coreihwl/sqr_basecase.asm

raw
1 dnl AMD64 mpn_sqr_basecase optimised for Intel Haswell.
2
3 dnl Contributed to the GNU project by Torbjörn Granlund.
4
5 dnl Copyright 2008, 2009, 2011-2013 Free Software Foundation, Inc.
6
7 dnl This file is part of the GNU MP Library.
8 dnl
9 dnl The GNU MP Library is free software; you can redistribute it and/or modify
10 dnl it under the terms of either:
11 dnl
12 dnl * the GNU Lesser General Public License as published by the Free
13 dnl Software Foundation; either version 3 of the License, or (at your
14 dnl option) any later version.
15 dnl
16 dnl or
17 dnl
18 dnl * the GNU General Public License as published by the Free Software
19 dnl Foundation; either version 2 of the License, or (at your option) any
20 dnl later version.
21 dnl
22 dnl or both in parallel, as here.
23 dnl
24 dnl The GNU MP Library is distributed in the hope that it will be useful, but
25 dnl WITHOUT ANY WARRANTY; without even the implied warranty of MERCHANTABILITY
26 dnl or FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License
27 dnl for more details.
28 dnl
29 dnl You should have received copies of the GNU General Public License and the
30 dnl GNU Lesser General Public License along with the GNU MP Library. If not,
31 dnl see https://www.gnu.org/licenses/.
32
33 include(`../config.m4')
34
35 C cycles/limb mul_2 addmul_2 sqr_diag_addlsh1
36 C AMD K8,K9 n/a n/a n/a
37 C AMD K10 n/a n/a n/a
38 C AMD bull n/a n/a n/a
39 C AMD pile n/a n/a n/a
40 C AMD steam ? ? ?
41 C AMD bobcat n/a n/a n/a
42 C AMD jaguar ? ? ?
43 C Intel P4 n/a n/a n/a
44 C Intel core n/a n/a n/a
45 C Intel NHM n/a n/a n/a
46 C Intel SBR n/a n/a n/a
47 C Intel IBR n/a n/a n/a
48 C Intel HWL 1.86 2.15 ~2.5
49 C Intel BWL ? ? ?
50 C Intel atom n/a n/a n/a
51 C VIA nano n/a n/a n/a
52
53 C The inner loops of this code are the result of running a code generation and
54 C optimisation tool suite written by David Harvey and Torbjörn Granlund, except
55 C that the sqr_diag_addlsh1 loop was manually written.
56
57 C TODO
58 C * Replace current unoptimised sqr_diag_addlsh1 loop; 1.75 c/l might be
59 C possible.
60 C * Consider splitting outer loop into 2, one for n = 1 (mod 2) and one for
61 C n = 0 (mod 2). These loops could fall into specific "corner" code.
62 C * Consider splitting outer loop into 4.
63 C * Streamline pointer updates.
64 C * Perhaps suppress a few more xor insns in feed-in code.
65 C * Make sure we write no dead registers in feed-in code.
66 C * We might use 32-bit size ops, since n >= 2^32 is non-terminating. Watch
67 C out for negative sizes being zero-extended, though.
68 C * Provide straight-line code for n = 4; then look for simplifications in
69 C main code.
70
71 define(`rp', `%rdi')
72 define(`up', `%rsi')
73 define(`un_param',`%rdx')
74
75
76 ABI_SUPPORT(DOS64)
77 ABI_SUPPORT(STD64)
78
79 ASM_START()
80 TEXT
81 ALIGN(32)
82 PROLOGUE(mpn_sqr_basecase)
83 FUNC_ENTRY(3)
84
85 cmp $2, un_param
86 jae L(gt1)
87
88 mov (up), %rdx
89 mulx( %rdx, %rax, %rdx)
90 mov %rax, (rp)
91 mov %rdx, 8(rp)
92 FUNC_EXIT()
93 ret
94
95 L(gt1): jne L(gt2)
96
97 mov (up), %rdx
98 mov 8(up), %rcx
99 mulx( %rcx, %r9, %r10) C v0 * v1 W 1 2
100 mulx( %rdx, %rax, %r8) C v0 * v0 W 0 1
101 mov %rcx, %rdx
102 mulx( %rdx, %r11, %rdx) C v1 * v1 W 2 3
103 add %r9, %r9 C W 1
104 adc %r10, %r10 C W 2
105 adc $0, %rdx C W 3
106 add %r9, %r8 C W 1
107 adc %r11, %r10 C W 2
108 adc $0, %rdx C W 3
109 mov %rax, (rp)
110 mov %r8, 8(rp)
111 mov %r10, 16(rp)
112 mov %rdx, 24(rp)
113 FUNC_EXIT()
114 ret
115
116 L(gt2): cmp $4, un_param
117 jae L(gt3)
118 define(`v0', `%r8')
119 define(`v1', `%r9')
120 define(`w0', `%r10')
121 define(`w2', `%r11')
122
123 mov (up), v0
124 mov 8(up), %rdx
125 mov %rdx, v1
126 mulx( v0, w2, %rax)
127 mov 16(up), %rdx
128 mulx( v0, w0, %rcx)
129 mov w2, %r8
130 add %rax, w0
131 adc $0, %rcx
132 mulx( v1, %rdx, %rax)
133 add %rcx, %rdx
134 mov %rdx, 24(rp)
135 adc $0, %rax
136 mov %rax, 32(rp)
137 xor R32(%rcx), R32(%rcx)
138 mov (up), %rdx
139 mulx( %rdx, %rax, w2)
140 mov %rax, (rp)
141 add %r8, %r8
142 adc w0, w0
143 setc R8(%rcx)
144 mov 8(up), %rdx
145 mulx( %rdx, %rax, %rdx)
146 add w2, %r8
147 adc %rax, w0
148 mov %r8, 8(rp)
149 mov w0, 16(rp)
150 mov 24(rp), %r8
151 mov 32(rp), w0
152 lea (%rdx,%rcx), w2
153 adc %r8, %r8
154 adc w0, w0
155 setc R8(%rcx)
156 mov 16(up), %rdx
157 mulx( %rdx, %rax, %rdx)
158 add w2, %r8
159 adc %rax, w0
160 mov %r8, 24(rp)
161 mov w0, 32(rp)
162 adc %rcx, %rdx
163 mov %rdx, 40(rp)
164 FUNC_EXIT()
165 ret
166
167 L(gt3):
168
169 define(`v0', `%r8')
170 define(`v1', `%r9')
171 define(`w0', `%r10')
172 define(`w1', `%r11')
173 define(`w2', `%rbx')
174 define(`w3', `%rbp')
175 define(`un', `%r12')
176 define(`n', `%rcx')
177
178 define(`X0', `%r13')
179 define(`X1', `%r14')
180
181 L(do_mul_2):
182 push %rbx
183 push %rbp
184 push %r12
185 push %r13
186 push %r14
187 mov $0, R32(un)
188 sub un_param, un C free up rdx
189 push un
190 mov (up), v0
191 mov 8(up), %rdx
192 lea 2(un), n
193 sar $2, n C FIXME: suppress, change loop?
194 inc un C decrement |un|
195 mov %rdx, v1
196
197 test $1, R8(un)
198 jnz L(mx1)
199
200 L(mx0): mulx( v0, w2, w1)
201 mov 16(up), %rdx
202 mov w2, 8(rp)
203 xor w2, w2
204 mulx( v0, w0, w3)
205 test $2, R8(un)
206 jz L(m00)
207
208 L(m10): lea -8(rp), rp
209 lea -8(up), up
210 jmp L(mlo2)
211
212 L(m00): lea 8(up), up
213 lea 8(rp), rp
214 jmp L(mlo0)
215
216 L(mx1): mulx( v0, w0, w3)
217 mov 16(up), %rdx
218 mov w0, 8(rp)
219 xor w0, w0
220 mulx( v0, w2, w1)
221 test $2, R8(un)
222 jz L(mlo3)
223
224 L(m01): lea 16(rp), rp
225 lea 16(up), up
226 jmp L(mlo1)
227
228 ALIGN(32)
229 L(mtop):mulx( v1, %rax, w0)
230 add %rax, w2 C 0
231 mov (up), %rdx
232 mulx( v0, %rax, w1)
233 adc $0, w0 C 1
234 add %rax, w2 C 0
235 L(mlo1):adc $0, w1 C 1
236 add w3, w2 C 0
237 mov w2, (rp) C 0
238 adc $0, w1 C 1
239 mulx( v1, %rax, w2)
240 add %rax, w0 C 1
241 mov 8(up), %rdx
242 adc $0, w2 C 2
243 mulx( v0, %rax, w3)
244 add %rax, w0 C 1
245 adc $0, w3 C 2
246 L(mlo0):add w1, w0 C 1
247 mov w0, 8(rp) C 1
248 adc $0, w3 C 2
249 mulx( v1, %rax, w0)
250 add %rax, w2 C 2
251 mov 16(up), %rdx
252 mulx( v0, %rax, w1)
253 adc $0, w0 C 3
254 add %rax, w2 C 2
255 adc $0, w1 C 3
256 L(mlo3):add w3, w2 C 2
257 mov w2, 16(rp) C 2
258 adc $0, w1 C 3
259 mulx( v1, %rax, w2)
260 add %rax, w0 C 3
261 mov 24(up), %rdx
262 adc $0, w2 C 4
263 mulx( v0, %rax, w3)
264 add %rax, w0 C 3
265 adc $0, w3 C 4
266 L(mlo2):add w1, w0 C 3
267 lea 32(up), up
268 mov w0, 24(rp) C 3
269 adc $0, w3 C 4
270 inc n
271 lea 32(rp), rp
272 jnz L(mtop)
273
274 L(mend):mulx( v1, %rdx, %rax)
275 add %rdx, w2
276 adc $0, %rax
277 add w3, w2
278 mov w2, (rp)
279 adc $0, %rax
280 mov %rax, 8(rp)
281
282 lea 16(up), up
283 lea -16(rp), rp
284
285 L(do_addmul_2):
286 L(outer):
287 lea (up,un,8), up C put back up to 2 positions above last time
288 lea 48(rp,un,8), rp C put back rp to 4 positions above last time
289
290 mov -8(up), v0 C shared between addmul_2 and corner
291
292 add $2, un C decrease |un|
293 cmp $-2, un
294 jge L(corner)
295
296 mov (up), v1
297
298 lea 1(un), n
299 sar $2, n C FIXME: suppress, change loop?
300
301 mov v1, %rdx
302 test $1, R8(un)
303 jnz L(bx1)
304
305 L(bx0): mov (rp), X0
306 mov 8(rp), X1
307 mulx( v0, %rax, w1)
308 add %rax, X0
309 adc $0, w1
310 mov X0, (rp)
311 xor w2, w2
312 test $2, R8(un)
313 jnz L(b10)
314
315 L(b00): mov 8(up), %rdx
316 lea 16(rp), rp
317 lea 16(up), up
318 jmp L(lo0)
319
320 L(b10): mov 8(up), %rdx
321 mov 16(rp), X0
322 lea 32(up), up
323 inc n
324 mulx( v0, %rax, w3)
325 jz L(ex)
326 jmp L(lo2)
327
328 L(bx1): mov (rp), X1
329 mov 8(rp), X0
330 mulx( v0, %rax, w3)
331 mov 8(up), %rdx
332 add %rax, X1
333 adc $0, w3
334 xor w0, w0
335 mov X1, (rp)
336 mulx( v0, %rax, w1)
337 test $2, R8(un)
338 jz L(b11)
339
340 L(b01): mov 16(rp), X1
341 lea 24(rp), rp
342 lea 24(up), up
343 jmp L(lo1)
344
345 L(b11): lea 8(rp), rp
346 lea 8(up), up
347 jmp L(lo3)
348
349 ALIGN(32)
350 L(top): mulx( v0, %rax, w3)
351 add w0, X1
352 adc $0, w2
353 L(lo2): add %rax, X1
354 adc $0, w3
355 mulx( v1, %rax, w0)
356 add %rax, X0
357 adc $0, w0
358 lea 32(rp), rp
359 add w1, X1
360 mov -16(up), %rdx
361 mov X1, -24(rp)
362 adc $0, w3
363 add w2, X0
364 mov -8(rp), X1
365 mulx( v0, %rax, w1)
366 adc $0, w0
367 L(lo1): add %rax, X0
368 mulx( v1, %rax, w2)
369 adc $0, w1
370 add w3, X0
371 mov X0, -16(rp)
372 adc $0, w1
373 add %rax, X1
374 adc $0, w2
375 add w0, X1
376 mov -8(up), %rdx
377 adc $0, w2
378 L(lo0): mulx( v0, %rax, w3)
379 add %rax, X1
380 adc $0, w3
381 mov (rp), X0
382 mulx( v1, %rax, w0)
383 add %rax, X0
384 adc $0, w0
385 add w1, X1
386 mov X1, -8(rp)
387 adc $0, w3
388 mov (up), %rdx
389 add w2, X0
390 mulx( v0, %rax, w1)
391 adc $0, w0
392 L(lo3): add %rax, X0
393 adc $0, w1
394 mulx( v1, %rax, w2)
395 add w3, X0
396 mov 8(rp), X1
397 mov X0, (rp)
398 mov 16(rp), X0
399 adc $0, w1
400 add %rax, X1
401 adc $0, w2
402 mov 8(up), %rdx
403 lea 32(up), up
404 inc n
405 jnz L(top)
406
407 L(end): mulx( v0, %rax, w3)
408 add w0, X1
409 adc $0, w2
410 L(ex): add %rax, X1
411 adc $0, w3
412 mulx( v1, %rdx, %rax)
413 add w1, X1
414 mov X1, 8(rp)
415 adc $0, w3
416 add w2, %rdx
417 adc $0, %rax
418 add %rdx, w3
419 mov w3, 16(rp)
420 adc $0, %rax
421 mov %rax, 24(rp)
422
423 jmp L(outer) C loop until a small corner remains
424
425 L(corner):
426 pop un
427 mov (up), %rdx
428 jg L(small_corner)
429
430 mov %rdx, v1
431 mov (rp), X0
432 mov %rax, X1 C Tricky rax reuse of last iteration
433 mulx( v0, %rax, w1)
434 add %rax, X0
435 adc $0, w1
436 mov X0, (rp)
437 mov 8(up), %rdx
438 mulx( v0, %rax, w3)
439 add %rax, X1
440 adc $0, w3
441 mulx( v1, %rdx, %rax)
442 add w1, X1
443 mov X1, 8(rp)
444 adc $0, w3
445 add w3, %rdx
446 mov %rdx, 16(rp)
447 adc $0, %rax
448 mov %rax, 24(rp)
449 lea 32(rp), rp
450 lea 16(up), up
451 jmp L(com)
452
453 L(small_corner):
454 mulx( v0, X1, w3)
455 add %rax, X1 C Tricky rax reuse of last iteration
456 adc $0, w3
457 mov X1, (rp)
458 mov w3, 8(rp)
459 lea 16(rp), rp
460 lea 8(up), up
461
462 L(com):
463
464 L(sqr_diag_addlsh1):
465 lea 8(up,un,8), up C put back up at its very beginning
466 lea (rp,un,8), rp
467 lea (rp,un,8), rp C put back rp at its very beginning
468 inc un
469
470 mov -8(up), %rdx
471 xor R32(%rbx), R32(%rbx) C clear CF as side effect
472 mulx( %rdx, %rax, %r10)
473 mov %rax, 8(rp)
474 mov 16(rp), %r8
475 mov 24(rp), %r9
476 jmp L(dm)
477
478 ALIGN(16)
479 L(dtop):mov 32(rp), %r8
480 mov 40(rp), %r9
481 lea 16(rp), rp
482 lea (%rdx,%rbx), %r10
483 L(dm): adc %r8, %r8
484 adc %r9, %r9
485 setc R8(%rbx)
486 mov (up), %rdx
487 lea 8(up), up
488 mulx( %rdx, %rax, %rdx)
489 add %r10, %r8
490 adc %rax, %r9
491 mov %r8, 16(rp)
492 mov %r9, 24(rp)
493 inc un
494 jnz L(dtop)
495
496 L(dend):adc %rbx, %rdx
497 mov %rdx, 32(rp)
498
499 pop %r14
500 pop %r13
501 pop %r12
502 pop %rbp
503 pop %rbx
504 FUNC_EXIT()
505 ret
506 EPILOGUE()