[x86] Ugly code for a simple function

[lattner]

Bugzilla Link	478
Resolution	FIXED
Resolved on	Feb 22, 2010 12:51
Version	1.0
OS	All

Extended Description

Consider this simple function:

int f(int a, int b){
return a * a + 2 * a * b + b * b;
}

We currently generate this X86 code for it:

f:
subl $4, %esp
movl %esi, (%esp)
movl 8(%esp), %ecx
movl 12(%esp), %eax
movl %ecx, %edx
imull %edx, %edx
movl %eax, %esi
imull %ecx, %esi
addl %esi, %esi
imull %eax, %eax
addl %edx, %eax
addl %esi, %eax
movl (%esp), %esi
addl $4, %esp
ret

... uh, yuck.

GCC generates this:
f:
movl 4(%esp), %eax
movl 8(%esp), %edx
movl %eax, %ecx
imull %eax, %ecx
imull %edx, %eax
imull %edx, %edx
leal (%ecx,%eax,2), %eax
addl %edx, %eax
ret

Which is much nicer.

It would be even better if we reassociated it into something like:

int f(int a, int b) {
return a * (a + 2 * b) + b * b;
}

... which would save a multiply (this is an instcombine thing).

The PPC backend is producing nice code:

_f:
mullw r2, r3, r3
mullw r3, r4, r3
rlwinm r3, r3, 1, 0, 30
mullw r4, r4, r4
add r2, r4, r2
add r3, r2, r3
blr

The X86 backend should do so too! :)

-Chris

[lattner]

Note that if someone is interested in working on this, this amounts to making
the X86 backend instruction select '2*X+Y' as LEA, along with its obvious
generalizations, when the expression has a 32- or 16-bit integer type.

-Chris

[lattner]

Note that half of this bug is fixed. Now that the X86 code generator knows
that imul commutes, we can generate this code:

f:
movl 4(%esp), %ecx
movl 8(%esp), %eax
movl %ecx, %edx
imull %edx, %edx
imull %eax, %ecx
addl %ecx, %ecx
imull %eax, %eax
addl %edx, %eax
addl %ecx, %eax
ret

This only has one register-register copy (which is required), which is much
better than the before. Also because of this, register pressure is reduced,
allowing us to avoid spilling an callee saved register.

-Chris

[llvmbot]

With a newer x86 backend coming, we need to rerun this test and see what kind of
code is being emitted now. This looks like it hasn't been done in nearly a year.
Hopefully the X86 move to the new backend framework will improve this
automatically. If not, it needs to be attended to.

Evan: cc'd you on this since its probably of interest to you.

[lattner]

Evan, note that this has regressed. This appears to be an LEA selection / node duplication thing. I'm
getting this:

_f:
sub %ESP, 4
mov DWORD PTR [%ESP], %ESI
mov %ECX, DWORD PTR [%ESP + 12]
mov %EAX, %ECX
imul %EAX, %EAX
mov %EDX, DWORD PTR [%ESP + 8]
mov %ESI, %EDX
imul %ESI, %ESI
add %EAX, %ESI
lea %EDX, DWORD PTR [2*%EDX]
imul %EDX, %ECX
add %EAX, %EDX
mov %ESI, DWORD PTR [%ESP]
add %ESP, 4
ret

-Chris

[lattner]

In particular, this:

lea %EDX, DWORD PTR [2*%EDX]

would be much cheaper as 'add EDX, EDX'.

-Chris

[llvmbot]

The regression (lea %EDX, DWORD PTR [2*%EDX]) has been fixed. It now emits an ADD instead.

However, we still emit worse code than gcc. We need to reassociate

((a * a) + (b * b)) + ((b * 2) * a)
to
((a * a) + (b * b)) + (2 * (b * a))

So the LEA match code would see something like X + (a * Y).

[lattner]

The regression (lea %EDX, DWORD PTR [2*%EDX]) has been fixed. It now emits an ADD instead.

Thanks.

However, we still emit worse code than gcc. We need to reassociate
So the LEA match code would see something like X + (a * Y).

Agreed, I'll try to take care of this tonight.

Thanks!

-Chris

[lattner]

The reassociation is now implemented, giving us this code:

_f:
sub %ESP, 4
mov DWORD PTR [%ESP], %ESI
mov %EAX, DWORD PTR [%ESP + 12]
mov %ECX, %EAX
imul %ECX, %ECX
mov %EDX, DWORD PTR [%ESP + 8]
mov %ESI, %EDX
imul %ESI, %ESI
add %ECX, %ESI
imul %EDX, %EAX
lea %EAX, DWORD PTR [%ECX + 2*%EDX]
mov %ESI, DWORD PTR [%ESP]
add %ESP, 4
ret

I think this is right from a selection standpoint, but now we have scheduling issues which is causing us
to use more registers than we should. This causes us to have to use ESI, which requires us to spill/
restore it and create a stack frame. Thus the code is still worse than that in comment 2.

-Chris

[llvmbot]

My gut reaction is the scheduler needs to be taught about 2-address code. I'll look into this a bit later.

[lattner]

Quite possible (also, it would be a big win on x86). Do you think the pattern isel and gcc were just getting
lucky?

-Chris

[llvmbot]

We now generates:

_f:
movl 4(%esp), %eax
movl 8(%esp), %ecx
movl %eax, %edx
imull %ecx, %edx
imull %eax, %eax
imull %ecx, %ecx
addl %eax, %ecx
leal (%ecx,%edx,2), %eax
ret

This is just as good as what gcc generates. :)

[lattner]

We now generate:

_f:
movl 8(%esp), %ecx
movl 4(%esp), %edx
leal (%ecx,%edx,2), %eax
imull %edx, %edx
imull %ecx, %eax
addl %edx, %eax
ret

which is even better :)