[llvm-dev] proposal for optimization method
or dv via llvm-dev
llvm-dev at lists.llvm.org
Wed Feb 20 04:08:59 PST 2019
Hello everyone, I discovered a way to perform optimization on the following
code (I gave an example that uses 32bit integer, but it works with any
size.):
const uint32 d,r;//d is an odd number
//d is the divisor, r is the remainder
bool check_remainder(uint32 x)
{
return x%d==r;
}
if we know d and r at compile time, and d is an odd integer, we can use
modular multiplicative inverse to bypass the division operation.
I wrote the following code to calculate the M.M.I of a number over 2^b. I
give anyone the permission to use it (unlicensed).
uint64_t find_mod_mul_inverse(uint64_t x, uint64_t bits)
{
if (bits > 64 || ((x&1)==0))
return 0;// invalid parameters
uint64_t mask;
if (bits == 64)
mask = -1;
else
{
mask = 1;
mask<<=bits;
mask--;
}
x&=mask;
uint64_t result=1, state=x, ctz=0;
while(state!=1ULL)
{
ctz=__builtin_ctzll(state^1);
result|=1ULL<<ctz;
state+=x<<ctz;
state&=mask;
}
return result;
}
now consider the following steps:
from the 2 constants (d and r) we create 3 constants (with the same bit length):
constants uint32 s,u,mmi;
mmi = find_mod_mul_inverse(d,32);
s = (r*mmi);
u = (UINT32_MAX-r)/d; // UINT32_MAX corresponds to pow(2,32)-1.
the idea behind these constants is the following formula:
mmi_of(d)*x=x/d+(x%d)*mmi_of(d)
now after we generated the constants, we will just emit the following
code instead of the former:
bool check_remainder(uint32 x)
{
return ((x*mmi)-s)<=u;
}
Anyway, I looked at the file IntegerDivision.cpp, it seems to me that
this new optimization is more effective then the optimization used
there. However, I have no experience with compiler development, so I
can just give you my idea. if further explanation is needed, just ask.
I tested my method and it gives the correct results.
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://lists.llvm.org/pipermail/llvm-dev/attachments/20190220/9e9e5aec/attachment.html>
More information about the llvm-dev
mailing list