[llvm-bugs] [Bug 35479] New: more efficient code for x % C == 0

[via llvm-bugs]

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

            Bug ID: 35479
           Summary: more efficient code for x % C == 0
           Product: libraries
           Version: trunk
          Hardware: PC
                OS: Linux
            Status: NEW
          Severity: enhancement
          Priority: P
         Component: Common Code Generator Code
          Assignee: unassignedbugs at nondot.org
          Reporter: jay.foad at gmail.com
                CC: llvm-bugs at lists.llvm.org

Given:

int f(unsigned x) { return x % 25 == 0; }

clang -O3 currently (svn r319159) generates:

        movl    %edi, %eax
        imulq   $1374389535, %rax, %rax # imm = 0x51EB851F
        shrq    $35, %rax
        leal    (%rax,%rax,4), %eax
        leal    (%rax,%rax,4), %ecx
        xorl    %eax, %eax
        cmpl    %ecx, %edi
        sete    %al

Following Hacker's Delight 10-16 "Test for Zero Remainder after Division by a
Constant" it would be more efficient to generate:

        imull   $-1030792151, %edi, %ecx # imm = 0xC28F5C29
        xorl    %eax, %eax
        cmpl    $171798692, %ecx        # imm = 0xA3D70A4
        setb    %al

i.e. as if the source had been:

int f(unsigned x) { return x * 0xC28F5C29 <= 0x0A3D70A3; }

The code is similar, but slightly more complicated, for even divisors, and for
signed division.

-- 
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/20171130/3a470395/attachment.html>