[Bug rtl-optimization/17236] inefficient code for long long multiply on x86

["bonzini at gnu dot org" <gcc-bugzilla at gcc dot gnu dot org>]

------- Comment #7 from bonzini at gnu dot org  2007-12-18 07:43 -------
The generated code has changed a lot recently, though it still uses two spills:

        pushl   %esi
        pushl   %ebx
        movl    12(%esp), %ebx         ; load alow
        movl    20(%esp), %esi         ; load blow
        movl    24(%esp), %ecx         ; load bhigh
        imull   %ebx, %ecx             ; bhigh = bhigh * alow
        movl    16(%esp), %eax         ; load ahigh
        imull   %esi, %eax             ; ahigh = ahigh * blow
        addl    %eax, %ecx
        movl    %esi, %eax             ; need to move a low part in %eax
        mull    %ebx
        leal    (%ecx,%edx), %esi      ; what the heck, a simple addl could do!
        movl    %esi, %edx
        popl    %ebx
        popl    %esi

The important thing is that the adds are one before, and one after the
multiply.      And the RTL before reload is very nice!

   28 r64:SI=[argp:SI]
   30 r66:SI=[argp:SI+0x8]
    7 {r62:SI=[argp:SI+0xc]*r64:SI;clobber flags:CC;}
    8 {r63:SI=[argp:SI+0x4]*r66:SI;clobber flags:CC;}
    9 {r62:SI=r62:SI+r63:SI;clobber flags:CC;}
   10 {r61:DI=zero_extend(r66:SI)*zero_extend(r64:SI);clobber flags:CC;}
   12 {r61:DI#4=r62:SI+r61:DI#4;clobber flags:CC;}

That could be basically

   mov (blow), %eax
   mov (alow), %ecx
   imul (bhigh), %eax, %ebx  ;needs reload of (bh) in %ebx
   imul (ahigh), %ecx, %edx  ;needs reload of (ah) in %edx
   addl %edx, %ebx
   mul  %ecx
   addl %ebx, %edx

So, if we are content with a single spill, there is now mainly a register
allocation problem.  For zero spills, we would need rematerialization of either
alow or blow, as in:

   mov (blow), %eax
   imul (bhigh), %eax, %ecx  ;needs reload of (bh) in %ecx
   imul (ahigh), (alow), %edx  ;needs reload of (ah) in %edx
   addl %edx, %ecx
   mul  (al)
   addl %ebx, %edx

So, for now let's aim at having one spill.  Then the main problem is that gcc
should try to keep one of alow or blow in %eax, in order to reuse it for the
mull.  Then it could do with a single spill, like this:

        pushl   %ebx
        movl    12(%esp), %eax         ; load alow
        movl    20(%esp), %ecx         ; load blow
        movl    24(%esp), %ebx         ; load bhigh, input reload
        imull   %eax, %ebx
        movl    16(%esp), %edx         ; load ahigh, input reload
        imull   %ecx, %edx
        addl    %edx, %ebx
        mul     %ecx
        addl    %ebx, %edx
        popl    %ebx


-- 

bonzini at gnu dot org changed:

           What    |Removed                     |Added
----------------------------------------------------------------------------
                 CC|                            |bonzini at gnu dot org


http://gcc.gnu.org/bugzilla/show_bug.cgi?id=17236