Please update addaddmul_1msb0.asm to support ABI in mingw64

[Niels Möller]

Torbjörn Granlund <tg at gmplib.org> writes:

> On 2nd thought, the bookkeeping inc will clear the O flag and leave the C
> flag alone.

And will cause an interesting failure if one can ever afford enough RAM
to use an input size larger than 2^63 limbs ;-)

> So, except for a typo in addressing your code loooks
> correct.

Attaching a version that actually passes some tests (I should commit the
unit tests, but not today). The loop is only 2-way, and there are three
spare registers:

L(top):
	mov	(ap, n, 8), %rdx
	mulx	u0, l0, hi
	mov	(bp, n, 8), %rdx
	mulx	v0, l1, c1
	adox	c0, l0
	adox	hi, c1
	adc	l0, l1
	mov	l1, (rp, n, 8)

	inc	n
	mov	(ap, n, 8), %rdx
	mulx	u0, l0, hi
	mov	(bp, n, 8), %rdx
	mulx	v0, l1, c0
	adox	c1, l0
	adox	hi, c0
	adc	l0, l1
	mov	l1, (rp, n, 8)
	inc	n

	jnz	L(top)

I've eliminated the zero adds by adding together the high half of the
products earlier (thanks to the "msb0" condition, there's no carry out
from the second adox in the pairs). I think the critical recurrency
involves the alternating carry limbs c0, c1, and the OF flag which is
live only between the adjacent adox instructions.

Benchmarking on my laptop (AMD ryzen), I get 

$ ./tune/speed -p 10000000 -C mpn_mul_1.0x9999999999999999 mpn_addmul_1.9999999999999999 mpn_addaddmul_1msb0 -s 1-200 -f 1.3
overhead 4.34 cycles, precision 10000000 units of 7.16e-10 secs, CPU freq 1397.19 MHz
        mpn_mul_1.0x9999999999999999 mpn_addmul_1.9999999999999999 mpn_addaddmul_1msb0
1             #6.0772        6.5963        6.2874
2             #3.4713        3.9056        4.6860
3             #2.6382        2.6919        4.0909
4              2.4400       #2.2825        4.1684
5             #2.4537        2.5213        3.7127
6             #2.2549        2.5762        3.5821
7             #2.1174        2.3741        3.7313
9             #2.0589        2.1572        3.3585
11            #1.8486        2.1634        3.1464
14            #1.7917        1.9840        3.2297
18            #1.6255        1.9356        2.9995
23            #1.5938        1.8239        2.9059
29            #1.5380        1.7372        2.8521
37            #1.5505        1.7278        2.8299
48            #1.4754        1.7155        2.8755
62            #1.4706        1.7699        2.7680
80            #1.4662        1.7399        2.7284
104           #1.4628        1.7610        2.7784
135           #1.4634        1.8041        2.8026
175           #1.4553        1.8036        2.7376

so about 20% faster than mul_1 + addmul_1. Maybe instruction issue is a
bottleneck? 

Cycle numbers are getting bit fuzzy, so let's scale all numbers by some
fudge factor to get 2 c/l for addmul_1, we then have

               1.6           2.0           3.0

The 3 cycles/limb means 6 cycles for the two-way loop of 19
instructions, or 3.1 instructions per cycle. To reach the ideal of 2
cycles/limb (critical path limit, one iteration of this 2-way loop in 4
cycles), one would need to issue almost 5 instructions per cycle, and
that's not very realistic, right?

A few instructions can be shaved off by going to k-way for larger k, and
moving the invariant u0/v0 to %rdx, as you suggested. Is that the way to
go?

This structure doesn't work as is for addsubmul_1msb0, one would need to
either organize it differently, or negate on the fly (but adding 4 not
instructions into the loop sounds rather expensive, if speed is
already limited by the number of instruction).

Ah, and one final question: Where should mulx-code go? I tried putting
this in x86_64/mulx/adx/, but it wasn't picked up automagically by
configure, I had to link it in manually.
 
Regards,
/Niels

-------------- next part --------------
An embedded and charset-unspecified text was scrubbed...
Name: addaddmul_1msb0.asm
URL: <https://gmplib.org/list-archives/gmp-devel/attachments/20211007/741571b6/attachment.ksh>
-------------- next part --------------

-- 
Niels Möller. PGP-encrypted email is preferred. Keyid 368C6677.
Internet email is subject to wholesale government surveillance.