[llvm-bugs] [Bug 42874] New: InstCombine combines mul->shift into two multiplies.

[via llvm-bugs]

https://bugs.llvm.org/show_bug.cgi?id=42874

            Bug ID: 42874
           Summary: InstCombine combines mul->shift into two multiplies.
           Product: libraries
           Version: trunk
          Hardware: All
                OS: All
            Status: NEW
          Severity: enhancement
          Priority: P
         Component: Scalar Optimizations
          Assignee: unassignedbugs at nondot.org
          Reporter: husseydevin at gmail.com
                CC: llvm-bugs at lists.llvm.org

InstCombine is often too willing to turn a multiply followed by a shift/rotate
to two multiplies. 

https://godbolt.org/z/W44mjh

C:

#include <stdint.h>

uint32_t mulrot(uint32_t a)
{
    a *= 0x90000007;
    a = (a << 4) | (a >> 28);
    return a;
}

LLVM IR:

define i32 @mulrot(i32) {
  %2 = mul i32 %0, -1879048185 ; 0x90000007
  %3 = shl i32 %2, 4
  %4 = lshr i32 %2, 28
  %5 = or i32 %3, %4
  ret i32 %5
}


After running instcombine on this code, it converts it to this:

define i32 @mulrot(i32) {
  %2 = mul i32 %0, -1879048185 ; 0x90000007
  %3 = mul i32 %0, 112         ; 0x70
  %4 = lshr i32 %2, 28
  %5 = or i32 %3, %4
  ret i32 %5
}

So for example, on x86_64, the code I want is

mulrot:
    imul eax, edx, 0x90000007
    rol eax, 4
    ret

but I get this instead.

mulrot:
    imul eax, edi, 0x90000007
    imul ecx, edi, 0x70
    shr eax, 28
    or eax, ecx
    ret

This is incredibly inefficient and screws some stuff up.

instcombine is trying to use the associative property to make it so the
multiplies don't depend on each other.

    x *= 5;
    int y = x * 9;

is the same as 

    int y = x * 9 * 5;
    x *= 9;

In a normal scenario, this would probably be faster, as it can now use ILP.
However, a rotate/shift is usually much faster in this case and should be
prioritized.

While it is easiest to reproduce with a rotate, a simple left shift works as
well, as long as you use both results.

Using the funnel shift intrinsic doesn't cause this behavior.

-- 
You are receiving this mail because:
You are on the CC list for the bug.
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://lists.llvm.org/pipermail/llvm-bugs/attachments/20190802/fb7608c9/attachment.html>