Particularly ugly x86 long long code generation

[gcc at horizon dot com]

(I realize that overhauling long long is not really in the cards in the
run-up to 3.0, but it seemed worth throwing this into the pile anyway.

Also, of course, thanks for a wonderful compiler and sorry you only get
to hear the squeaky wheels, not the millions of smoothly running ones!

The following source code:

unsigned lone long
crc64(unsigned char const *buf, unsigned len)
{
        unsigned long long crc = 0;
        extern unsigned crctable[256];
        unsigned char c;

        while (len--) {
                c = ((unsigned char)crc ^ *buf++) & 255;
                crc >>= 8;
                crc ^= (unsigned long long)crctable[c] << 32;
        }
        return crc;
}

Generates, using GCC 2.95.3 -O3 -S -fomit-frame-pointer -march=pentium
the following assembly code:
(This is the Debian 2.95.3-5 package, which hasn't caught up with 2.95.3
release quite yet.)

	.file	"crcbug.c"
	.version	"01.01"
gcc2_compiled.:
.text
	.align 4
.globl crc64
	.type	crc64,@function
crc64:
	pushl %ebp
	pushl %edi
	pushl %esi
	pushl %ebx
	movl 20(%esp),%edi
	xorl %ecx,%ecx
	xorl %ebx,%ebx
	movl 24(%esp),%esi
	decl %esi
	cmpl $-1,%esi
	je .L4
	movl $crctable,%ebp
	.p2align 4,,7
.L5:
	movb %cl,%al
	xorb (%edi),%al
	incl %edi
	shrdl $8,%ebx,%ecx
	shrl $8,%ebx
	andl $255,%eax
	movl (%ebp,%eax,4),%eax	\
	xorl %edx,%edx		 \
	movl %eax,%edx		  \ Area of
	xorl %eax,%eax		  / concern
	xorl %eax,%ecx		 /
	xorl %edx,%ebx		/
	subl $1,%esi
	jnc .L5
.L4:
	movl %ecx,%eax
	movl %ebx,%edx
	popl %ebx
	popl %esi
	popl %edi
	popl %ebp
	ret
.Lfe1:
	.size	crc64,.Lfe1-crc64
	.ident	"GCC: (GNU) 2.95.3 20010219 (prerelease)"


Observe the fact that it clears %edx and then immedately moves %eax to it.
The clearing is dead code that should be obvious to a peephole optimizer.

Since %eax is then dead, it could just load into %edx in the first place.
In fact, it could xorl into %ebx in the first place.

Observe also the fact that it clears %eax then immedaitely xors that into
%ecx.  Since %eax is then dead, this is a really dumb no-op.

In other words, the entire "area of concern" could be reduced to the
single instruction

	xorl (%ebp,%eax,4),%ebx


The latest prerelease at codesourcery.com (*very* useful resource, BTW!)
produces even worse code:

	.file	"@24001.7.c"
	.version	"01.01"
gcc2_compiled.:
	.text
	.align 4
.globl crc64
	.type	crc64,@function
crc64:
	pushl	%ebp
	pushl	%edi
	pushl	%esi
	pushl	%ebx
	movl	24(%esp), %ebp
	decl	%ebp
	xorl	%esi, %esi
	xorl	%edi, %edi
	cmpl	$-1, %ebp
	je	.L7
	.p2align 2
.L5:
	movl	20(%esp), %eax
	movl	%esi, %ebx
	xorb	(%eax), %bl
	movzbl	%bl, %ecx
	shrdl	$8, %edi, %esi
	incl	%eax
	shrl	$8, %edi
	movl	crctable(,%ecx,4), %edx
	xorl	%ebx, %ebx
	movl	%edi, %ecx
	movl	%eax, 20(%esp)
	decl	%ebp
	movl	%edx, %eax
	movl	%esi, %edx
	xorl	%ebx, %edx
	xorl	%eax, %ecx
	cmpl	$-1, %ebp
	movl	%edx, %esi
	movl	%ecx, %edi
	jne	.L5
.L7:
	popl	%ebx
	movl	%esi, %eax
	popl	%esi
	movl	%edi, %edx
	popl	%edi
	popl	%ebp
	ret
.Lfe1:
	.size	crc64,.Lfe1-crc64
	.ident	"GCC: (GNU) 3.0 20010316 (prerelease)"

In addition to all the previous steps (just in a different order), it
uses both %ebx and %ecx in the formation of "c" and pointlessly copies
crc from %edi/%esi to %ecx/%edx and back, thereby wasting registers that
could have been used to avoid spilling "buf".

The desired code has exactly half as many instructions in the inner loop:
.L5:
	movl	%esi, %ebx
	xorb	(%eax), %bl
	movzbl	%bl, %ebx
	shrdl	$8, %edi, %esi
	incl	%eax
	shrl	$8, %edi
	xorl	crctable(,%ebx,4), %edi
	decl	%ebp
	cmpl	$-1, %ebp
	jne	.L5

This can mostly be produced by the source:

unsigned long long
crc64a(byte const *buf, unsigned len)
{
	unsigned hi = 0, lo = 0;
	extern unsigned crctable[256];
	unsigned char c;

	while (len--) {
		c = ((unsigned char)lo ^ *buf++) & 255;
		lo = lo>>8 | hi<<24;
		hi = hi>>8 ^ crctable[c];
	}
	return (unsigned long long)hi<<32 | lo;
}

except that it misses the shrdl optimization and, of course, makes
a complete mess out of the return code, using 10 instructions where
*zero* are actually needed if the register assignment had been right in
the first place:

crc64a:
	pushl %ebp
	pushl %edi
	pushl %esi
	pushl %ebx
	movl 20(%esp),%edi
	xorl %ebx,%ebx
	xorl %esi,%esi
	movl 24(%esp),%ecx
	decl %ecx
	cmpl $-1,%ecx
	je .L9
	movl $crctable,%ebp
	.p2align 4,,7
.L10:
	movl %esi,%eax
	xorb (%edi),%al
	incl %edi
	shrl $8,%esi	\
	movl %ebx,%edx	 \ How about
	sall $24,%edx	 / "shrdl $8, %ebx, %esi"
	orl %edx,%esi	/
	shrl $8,%ebx
	andl $255,%eax
	xorl (%ebp,%eax,4),%ebx
	subl $1,%ecx
	jnc .L10
.L9:
	movl %ebx,%ecx	\
	xorl %ebx,%ebx	 \
	movl %ecx,%ebx	  \
	xorl %ecx,%ecx	   \
	movl %esi,%eax	    \ Yuk!  Especially as the variables could have
	xorl %edx,%edx	    / just been assigned to %edx/%eax originally.
	orl %eax,%ecx	   /
	orl %edx,%ebx	  /
	movl %ecx,%eax	 /
	movl %ebx,%edx	/
	popl %ebx
	popl %esi
	popl %edi
	popl %ebp
	ret

Is there some way to trick gcc into generating the desired code as
follows on x86 without hurting 64-bit machines?

crc64:
	pushl %ebx
	pushl %edi
	pushl %esi
	movl 20(%esp),%edi
	xorl %eax,%eax
	movl 24(%esp),%esi
	xorl %edx,%edx
	testl %esi,%esi
	je .L4
	movl $crctable,%ebx
	.p2align 4,,7
.L5:
	movb %al,%cl
	shrdl $8,%edx,%eax
	xorb (%edi),%cl
	shrl $8,%edx
	andl $255,%ecx
	incl %edi
	xorl (%ebx,%ecx,4),%edx
	decl %esi
	jnz .L5
.L4:
	popl %esi
	popl %edi
	popl %ebx
	ret