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

bugzilla-daemon at llvm.org bugzilla-daemon at llvm.org
Thu Mar 20 03:54:03 PDT 2014

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>