[LLVMbugs] [Bug 19206] New: Missed optimization when testing for a constant remainder

[bugzilla-daemon at llvm.org]

http://llvm.org/bugs/show_bug.cgi?id=19206

            Bug ID: 19206
           Summary: Missed optimization when testing for a constant
                    remainder
           Product: libraries
           Version: trunk
          Hardware: PC
                OS: Linux
            Status: NEW
          Severity: normal
          Priority: P
         Component: Common Code Generator Code
          Assignee: unassignedbugs at nondot.org
          Reporter: jn at sirrida.de
                CC: llvmbugs at cs.uiuc.edu
    Classification: Unclassified

Consider the expression (x % d) == c where d and c are constants.
For simplicity let us assume that x is unsigned and 0 <= c < d.
Let us further assume that d = a * (1 << b) and a is odd.
Then our expression can be transformed to
rotate_right(x-c, b) * inverse_mul(a) <= (high_value(x) - c) / d .
Example [(x % 250) == 3]:
   sub eax,3
   ror eax,1
   imul eax,eax,0x26e978d5  // multiplicative inverse of 125
   cmp eax,17179869  // floor((0xffffffff-3) / 250)
   jbe OK

A range check for x can be embedded as well with no additional code.
For signed values a similar transformation is possible.

For more details see my comment on Hacker's Delight
(http://hackersdelight.org/corres.txt) and/or our paper about hashing
(http://programming.sirrida.de/hashsuper.pdf).

The current version of Clang / LLVM (clang -O3 -S) translates it to the
following (GCC produces similar code):
   movl  %edi, %eax
   imulq $274877907, %rax, %rax  # imm = 0x10624DD3
   shrq $36, %rax
   imull $250, %eax, %eax
   movl  %edi, %ecx
   subl  %eax, %ecx
   cmpl  $3, %ecx
   je    OK
Please note that there are 2 multiply operations and one of them produces a
double width result (multiply high).

A first test shows that it is possible to address this optimization with a new
function in InstCombineCompares.cpp in a similar way like FoldICmpDivCst.
See
http://lists.cs.uiuc.edu/pipermail/llvm-commits/Week-of-Mon-20140303/207906.html

-- 
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/20140320/a67ec54a/attachment.html>