strangely pessimized code for double-word operations

[Quuxplusone]

Bugzilla Link	PR24983
Status	NEW
Importance	P normal
Reported by	Paolo Bonzini (bonzini@gnu.org)
Reported on	2015-09-29 05:05:14 -0700
Last modified on	2015-09-29 05:39:47 -0700
Version	3.7
Hardware	PC Linux
CC	hfinkel@anl.gov, llvm-bugs@lists.llvm.org
Fixed by commit(s)
Attachments
Blocks
Blocked by
See also

For this function:

#include <stdint.h>
void mul64(uint64_t *lo, uint64_t *hi, uint64_t a, uint64_t b)
{
    typedef union {
        uint64_t ll;
        struct { uint32_t high, low; } l;
    } LL;
    LL *ra = (LL *)&a;
    LL *rb = (LL *)&b;
    LL r0, r32, rt;

    /* Build the two products that will go in bits 32-95 */
    rt.ll = (uint64_t)ra->l.high * rb->l.low;
    r32.ll = (uint64_t)ra->l.low * rb->l.high;

    /* Reorganize these two factors into two 33-bit numbers */
    *hi = (uint64_t)r32.l.high + rt.l.high;       // bits 64-127
    r32.ll = (uint64_t)r32.l.low + rt.l.low;      // bits 32-95

    /* Now build the result 32 bits at a time.  Finish bits 0-31... */
    r0.ll = (uint64_t)ra->l.low * rb->l.low;

    /* ... then bits 32-63... */
    r32.ll += r0.l.high;
    r0.l.high = r32.l.low;
    *lo = r0.ll;

    /* ... then bits 64-127. */
    *hi += r32.l.high;
    *hi += (uint64_t)ra->l.high * rb->l.high;
}

LLVM generally produces nicely optimized code, except for some strange bits:

   0:   55                      push   %ebp
   1:   53                      push   %ebx
   2:   57                      push   %edi
   3:   56                      push   %esi
   4:   8b 44 24 24             mov    0x24(%esp),%eax
   8:   8b 6c 24 28             mov    0x28(%esp),%ebp
   c:   8b 74 24 1c             mov    0x1c(%esp),%esi
  10:   f7 64 24 20             mull   0x20(%esp)
  14:   89 d7                   mov    %edx,%edi
  16:   89 c3                   mov    %eax,%ebx
  18:   89 e8                   mov    %ebp,%eax
  1a:   f7 e6                   mul    %esi
  1c:   01 fa                   add    %edi,%edx
  1e:   8b 7c 24 18             mov    0x18(%esp),%edi
  22:   89 17                   mov    %edx,(%edi)
  24:   19 d2                   sbb    %edx,%edx
  26:   83 e2 01                and    $0x1,%edx
  29:   89 57 04                mov    %edx,0x4(%edi)
  2c:   01 d8                   add    %ebx,%eax
  2e:   19 d2                   sbb    %edx,%edx
  30:   bb ff ff ff ff          mov    $0xffffffff,%ebx   ; here it starts...
  35:   83 c3 01                add    $0x1,%ebx          ; EBX = 0, CF = 1?
  38:   19 c9                   sbb    %ecx,%ecx          ; ECX = -1?
  3a:   21 d1                   and    %edx,%ecx          ; AND into -1???
  3c:   21 c3                   and    %eax,%ebx          ; AND into 0???
  3e:   09 c3                   or     %eax,%ebx          ; OR into 0???
  40:   83 e1 01                and    $0x1,%ecx

which could be changed into simply

   mov %edx, %ecx
   mov %eax, %ebx

The moves could even be coalesced with the two previous instructions, giving:

   add %eax, %ebx
   sbb %ecx, %ecx

because both %eax and %edx are dead at this point:

  43:   8b 44 24 24             mov    0x24(%esp),%eax
  47:   f7 e6                   mul    %esi
  49:   01 d3                   add    %edx,%ebx
  4b:   8b 54 24 14             mov    0x14(%esp),%edx
  ...

[Quuxplusone]

The above is for 32-bit x86, so with -m32.