mpn/x86/aors_n.asm low-hanging fruit

[David Sparks]

As the comment suggests, it is indeed possible to simplify.
The big win is avoiding a register spill.

The one thing I want to be certain of is that I am assuming the
carry parameter is a boolean and the change in the handling of
non-zero even values is not a problem.

I tried to audit the call sites, but there's a lot of subtle code
(toom*.c is twisty maze of little passages) and it's difficult to
be sure.

The other alternative is "shr $1,PARAM_CARRY", which would be
exactly compatible and even shorter, but would perform an
unnecessary stack write.


diff --git a/mpn/x86/aors_n.asm b/mpn/x86/aors_n.asm
index 5d359f59b..7af326ebd 100644
--- a/mpn/x86/aors_n.asm
+++ b/mpn/x86/aors_n.asm
@@ -105,12 +105,9 @@ L(0a):	leal	(%eax,%eax,8),%eax
 	leal	L(oop)-3(%eax,%eax,8),%eax
 ')
 
-	C These lines initialize carry from the 5th parameter.  Should be
-	C possible to simplify.
-	pushl	%ebp		FRAME_pushl()
-	movl	PARAM_CARRY,%ebp
-	shrl	%ebp			C shift bit 0 into carry
-	popl	%ebp		FRAME_popl()
+	C Initialize the carry from the 5th parameter (without another spill)
+	cmpl    $1,PARAM_CARRY	C set borrow iff PARAM_CARRY < 1
+	cmc			C complement carry, now set iff PARAM_CARRY > 0
 
 	jmp	*%eax			C jump into loop
 


I'd let the 32-bit x86 code quietly molder in obsolescence,
but the comment was a big flashing <blink>FIXME</blink>.

If I *were* going to tackle it, I'd have a look at mpn/x86/gcd_11.asm
(which assumes bsf is unusably slow for ctz) and see if it would
help to replace the current lookup table

	while (unlikely((u & 0x3f) == 0))
		u >>= 6;
	u >>= ctz_table[u & 0x3f];

with an immediate constant like

	// We know that u is even, as it's the difference of two odds
	while (unlikely((u & 0x1e) == 0))
		u >>= 4;
	u >>= 0x12131210 >> (u & 0x1e) & 3;
	u >>= 1;

This has a MAXSHIFT of 4, rather than 6, although it takes advantage
of the fact that u is initially even, so the chance of looping at least
once is 1/16, only twice as bad as the current code's 1/32.

... but I can't, because I have no idea where to find a suitable
benchmark target.