Subject: Idea for optimization (test for remainder) Newsgroups: gmane.comp.compilers.llvm.devel Date: Thursday 27th February 2014 16:07:26 UTC (over 4 years ago) Hello folks! 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 // 0xffffffff / 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). Best regards Jasper |
|||