<div dir="ltr"><div dir="ltr"><div>It looks like gcc already does something like this. <a href="https://godbolt.org/z/JWljkL" target="_blank">https://godbolt.org/z/JWljkL</a></div><br clear="all"><div><div dir="ltr" class="m_2356665475379693387gmail_signature">~Craig</div></div><br></div></div><br><div class="gmail_quote"><div dir="ltr" class="gmail_attr">On Wed, Feb 20, 2019 at 8:45 PM or dv via llvm-dev <<a href="mailto:llvm-dev@lists.llvm.org" target="_blank">llvm-dev@lists.llvm.org</a>> wrote:<br></div><blockquote class="gmail_quote" style="margin:0px 0px 0px 0.8ex;border-left:1px solid rgb(204,204,204);padding-left:1ex">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.):<div><br><div>const uint32 d,r;//d is an odd number</div><div>//d is the divisor, r is the remainder</div><div>bool check_remainder(uint32 x)</div><div>{</div><div>return x%d==r;</div><div>}</div><div><br></div><div>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.</div><div>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).</div><div><pre style="box-sizing:border-box;margin-top:0px;margin-bottom:0px;overflow:scroll;padding:15px 0px"><div class="gmail-m_2356665475379693387gmail-m_2627065711439770122line gmail-m_2356665475379693387gmail-m_2627065711439770122js-file-line" id="gmail-m_2356665475379693387gmail-m_2627065711439770122LC3" style="color:rgb(36,41,46);font-family:Consolas,"Liberation Mono",Courier,monospace;font-size:14px;white-space:pre-wrap;box-sizing:border-box;padding:0px 15px"><span class="gmail-m_2356665475379693387gmail-m_2627065711439770122pl-c1" style="box-sizing:border-box;color:rgb(0,92,197)">uint64_t</span> <span class="gmail-m_2356665475379693387gmail-m_2627065711439770122pl-en" style="box-sizing:border-box;color:rgb(111,66,193)">find_mod_mul_inverse</span>(<span class="gmail-m_2356665475379693387gmail-m_2627065711439770122pl-c1" style="box-sizing:border-box;color:rgb(0,92,197)">uint64_t</span> x, <span class="gmail-m_2356665475379693387gmail-m_2627065711439770122pl-c1" style="box-sizing:border-box;color:rgb(0,92,197)">uint64_t</span> bits)</div><div class="gmail-m_2356665475379693387gmail-m_2627065711439770122line gmail-m_2356665475379693387gmail-m_2627065711439770122js-file-line" id="gmail-m_2356665475379693387gmail-m_2627065711439770122LC4" style="color:rgb(36,41,46);font-family:Consolas,"Liberation Mono",Courier,monospace;font-size:14px;white-space:pre-wrap;box-sizing:border-box;padding:0px 15px">{</div><div class="gmail-m_2356665475379693387gmail-m_2627065711439770122line gmail-m_2356665475379693387gmail-m_2627065711439770122js-file-line" id="gmail-m_2356665475379693387gmail-m_2627065711439770122LC5" style="color:rgb(36,41,46);font-family:Consolas,"Liberation Mono",Courier,monospace;font-size:14px;white-space:pre-wrap;box-sizing:border-box;padding:0px 15px"> <span class="gmail-m_2356665475379693387gmail-m_2627065711439770122pl-k" style="box-sizing:border-box;color:rgb(215,58,73)">if</span> (bits > <span class="gmail-m_2356665475379693387gmail-m_2627065711439770122pl-c1" style="box-sizing:border-box;color:rgb(0,92,197)">64</span> || ((x&<span class="gmail-m_2356665475379693387gmail-m_2627065711439770122pl-c1" style="box-sizing:border-box;color:rgb(0,92,197)">1</span>)==<span class="gmail-m_2356665475379693387gmail-m_2627065711439770122pl-c1" style="box-sizing:border-box;color:rgb(0,92,197)">0</span>))</div><div class="gmail-m_2356665475379693387gmail-m_2627065711439770122line gmail-m_2356665475379693387gmail-m_2627065711439770122js-file-line" id="gmail-m_2356665475379693387gmail-m_2627065711439770122LC6" style="color:rgb(36,41,46);font-family:Consolas,"Liberation Mono",Courier,monospace;font-size:14px;white-space:pre-wrap;box-sizing:border-box;padding:0px 15px"> <span class="gmail-m_2356665475379693387gmail-m_2627065711439770122pl-k" style="box-sizing:border-box;color:rgb(215,58,73)">return</span> <span class="gmail-m_2356665475379693387gmail-m_2627065711439770122pl-c1" style="box-sizing:border-box;color:rgb(0,92,197)">0</span>;// invalid parameters</div><div class="gmail-m_2356665475379693387gmail-m_2627065711439770122line gmail-m_2356665475379693387gmail-m_2627065711439770122js-file-line" id="gmail-m_2356665475379693387gmail-m_2627065711439770122LC7" style="color:rgb(36,41,46);font-family:Consolas,"Liberation Mono",Courier,monospace;font-size:14px;white-space:pre-wrap;box-sizing:border-box;padding:0px 15px"> <span class="gmail-m_2356665475379693387gmail-m_2627065711439770122pl-c1" style="box-sizing:border-box;color:rgb(0,92,197)">uint64_t</span> mask;</div><div class="gmail-m_2356665475379693387gmail-m_2627065711439770122line gmail-m_2356665475379693387gmail-m_2627065711439770122js-file-line" id="gmail-m_2356665475379693387gmail-m_2627065711439770122LC8" style="color:rgb(36,41,46);font-family:Consolas,"Liberation Mono",Courier,monospace;font-size:14px;white-space:pre-wrap;box-sizing:border-box;padding:0px 15px"> <span class="gmail-m_2356665475379693387gmail-m_2627065711439770122pl-k" style="box-sizing:border-box;color:rgb(215,58,73)">if</span> (bits == <span class="gmail-m_2356665475379693387gmail-m_2627065711439770122pl-c1" style="box-sizing:border-box;color:rgb(0,92,197)">64</span>)</div><div class="gmail-m_2356665475379693387gmail-m_2627065711439770122line gmail-m_2356665475379693387gmail-m_2627065711439770122js-file-line" id="gmail-m_2356665475379693387gmail-m_2627065711439770122LC9" style="color:rgb(36,41,46);font-family:Consolas,"Liberation Mono",Courier,monospace;font-size:14px;white-space:pre-wrap;box-sizing:border-box;padding:0px 15px"> mask = -<span class="gmail-m_2356665475379693387gmail-m_2627065711439770122pl-c1" style="box-sizing:border-box;color:rgb(0,92,197)">1</span>;</div><div class="gmail-m_2356665475379693387gmail-m_2627065711439770122line gmail-m_2356665475379693387gmail-m_2627065711439770122js-file-line" id="gmail-m_2356665475379693387gmail-m_2627065711439770122LC10" style="color:rgb(36,41,46);font-family:Consolas,"Liberation Mono",Courier,monospace;font-size:14px;white-space:pre-wrap;box-sizing:border-box;padding:0px 15px"> <span class="gmail-m_2356665475379693387gmail-m_2627065711439770122pl-k" style="box-sizing:border-box;color:rgb(215,58,73)">else</span></div><div class="gmail-m_2356665475379693387gmail-m_2627065711439770122line gmail-m_2356665475379693387gmail-m_2627065711439770122js-file-line" id="gmail-m_2356665475379693387gmail-m_2627065711439770122LC11" style="color:rgb(36,41,46);font-family:Consolas,"Liberation Mono",Courier,monospace;font-size:14px;white-space:pre-wrap;box-sizing:border-box;padding:0px 15px"> { </div><div class="gmail-m_2356665475379693387gmail-m_2627065711439770122line gmail-m_2356665475379693387gmail-m_2627065711439770122js-file-line" id="gmail-m_2356665475379693387gmail-m_2627065711439770122LC12" style="color:rgb(36,41,46);font-family:Consolas,"Liberation Mono",Courier,monospace;font-size:14px;white-space:pre-wrap;box-sizing:border-box;padding:0px 15px"> mask = <span class="gmail-m_2356665475379693387gmail-m_2627065711439770122pl-c1" style="box-sizing:border-box;color:rgb(0,92,197)">1</span>;</div><div class="gmail-m_2356665475379693387gmail-m_2627065711439770122line gmail-m_2356665475379693387gmail-m_2627065711439770122js-file-line" id="gmail-m_2356665475379693387gmail-m_2627065711439770122LC13" style="color:rgb(36,41,46);font-family:Consolas,"Liberation Mono",Courier,monospace;font-size:14px;white-space:pre-wrap;box-sizing:border-box;padding:0px 15px"> mask<<=bits;</div><div class="gmail-m_2356665475379693387gmail-m_2627065711439770122line gmail-m_2356665475379693387gmail-m_2627065711439770122js-file-line" id="gmail-m_2356665475379693387gmail-m_2627065711439770122LC14" style="color:rgb(36,41,46);font-family:Consolas,"Liberation Mono",Courier,monospace;font-size:14px;white-space:pre-wrap;box-sizing:border-box;padding:0px 15px"> mask--;</div><div class="gmail-m_2356665475379693387gmail-m_2627065711439770122line gmail-m_2356665475379693387gmail-m_2627065711439770122js-file-line" id="gmail-m_2356665475379693387gmail-m_2627065711439770122LC15" style="color:rgb(36,41,46);font-family:Consolas,"Liberation Mono",Courier,monospace;font-size:14px;white-space:pre-wrap;box-sizing:border-box;padding:0px 15px"> }</div><div class="gmail-m_2356665475379693387gmail-m_2627065711439770122line gmail-m_2356665475379693387gmail-m_2627065711439770122js-file-line" id="gmail-m_2356665475379693387gmail-m_2627065711439770122LC16" style="color:rgb(36,41,46);font-family:Consolas,"Liberation Mono",Courier,monospace;font-size:14px;white-space:pre-wrap;box-sizing:border-box;padding:0px 15px"> x&=mask;</div><div class="gmail-m_2356665475379693387gmail-m_2627065711439770122line gmail-m_2356665475379693387gmail-m_2627065711439770122js-file-line" id="gmail-m_2356665475379693387gmail-m_2627065711439770122LC17" style="color:rgb(36,41,46);font-family:Consolas,"Liberation Mono",Courier,monospace;font-size:14px;white-space:pre-wrap;box-sizing:border-box;padding:0px 15px"> <span class="gmail-m_2356665475379693387gmail-m_2627065711439770122pl-c1" style="box-sizing:border-box;color:rgb(0,92,197)">uint64_t</span> result=<span class="gmail-m_2356665475379693387gmail-m_2627065711439770122pl-c1" style="box-sizing:border-box;color:rgb(0,92,197)">1</span>, state=x, ctz=<span class="gmail-m_2356665475379693387gmail-m_2627065711439770122pl-c1" style="box-sizing:border-box;color:rgb(0,92,197)">0</span>;</div><div class="gmail-m_2356665475379693387gmail-m_2627065711439770122line gmail-m_2356665475379693387gmail-m_2627065711439770122js-file-line" id="gmail-m_2356665475379693387gmail-m_2627065711439770122LC18" style="color:rgb(36,41,46);font-family:Consolas,"Liberation Mono",Courier,monospace;font-size:14px;white-space:pre-wrap;box-sizing:border-box;padding:0px 15px"> <span class="gmail-m_2356665475379693387gmail-m_2627065711439770122pl-k" style="box-sizing:border-box;color:rgb(215,58,73)">while</span>(state!=<span class="gmail-m_2356665475379693387gmail-m_2627065711439770122pl-c1" style="box-sizing:border-box;color:rgb(0,92,197)">1ULL</span>)</div><div class="gmail-m_2356665475379693387gmail-m_2627065711439770122line gmail-m_2356665475379693387gmail-m_2627065711439770122js-file-line" id="gmail-m_2356665475379693387gmail-m_2627065711439770122LC19" style="color:rgb(36,41,46);font-family:Consolas,"Liberation Mono",Courier,monospace;font-size:14px;white-space:pre-wrap;box-sizing:border-box;padding:0px 15px"> {</div><div class="gmail-m_2356665475379693387gmail-m_2627065711439770122line gmail-m_2356665475379693387gmail-m_2627065711439770122js-file-line" id="gmail-m_2356665475379693387gmail-m_2627065711439770122LC20" style="color:rgb(36,41,46);font-family:Consolas,"Liberation Mono",Courier,monospace;font-size:14px;white-space:pre-wrap;box-sizing:border-box;padding:0px 15px"> ctz=<span class="gmail-m_2356665475379693387gmail-m_2627065711439770122pl-c1" style="box-sizing:border-box;color:rgb(0,92,197)">__builtin_ctzll</span>(state^<span class="gmail-m_2356665475379693387gmail-m_2627065711439770122pl-c1" style="box-sizing:border-box;color:rgb(0,92,197)">1</span>);</div><div class="gmail-m_2356665475379693387gmail-m_2627065711439770122line gmail-m_2356665475379693387gmail-m_2627065711439770122js-file-line" id="gmail-m_2356665475379693387gmail-m_2627065711439770122LC21" style="color:rgb(36,41,46);font-family:Consolas,"Liberation Mono",Courier,monospace;font-size:14px;white-space:pre-wrap;box-sizing:border-box;padding:0px 15px"> result|=<span class="gmail-m_2356665475379693387gmail-m_2627065711439770122pl-c1" style="box-sizing:border-box;color:rgb(0,92,197)">1ULL</span><<ctz;</div><div class="gmail-m_2356665475379693387gmail-m_2627065711439770122line gmail-m_2356665475379693387gmail-m_2627065711439770122js-file-line" id="gmail-m_2356665475379693387gmail-m_2627065711439770122LC22" style="color:rgb(36,41,46);font-family:Consolas,"Liberation Mono",Courier,monospace;font-size:14px;white-space:pre-wrap;box-sizing:border-box;padding:0px 15px"> state+=x<<ctz;</div><div class="gmail-m_2356665475379693387gmail-m_2627065711439770122line gmail-m_2356665475379693387gmail-m_2627065711439770122js-file-line" id="gmail-m_2356665475379693387gmail-m_2627065711439770122LC23" style="color:rgb(36,41,46);font-family:Consolas,"Liberation Mono",Courier,monospace;font-size:14px;white-space:pre-wrap;box-sizing:border-box;padding:0px 15px"> state&=mask;</div><div class="gmail-m_2356665475379693387gmail-m_2627065711439770122line gmail-m_2356665475379693387gmail-m_2627065711439770122js-file-line" id="gmail-m_2356665475379693387gmail-m_2627065711439770122LC24" style="color:rgb(36,41,46);font-family:Consolas,"Liberation Mono",Courier,monospace;font-size:14px;white-space:pre-wrap;box-sizing:border-box;padding:0px 15px"> }</div><div class="gmail-m_2356665475379693387gmail-m_2627065711439770122line gmail-m_2356665475379693387gmail-m_2627065711439770122js-file-line" id="gmail-m_2356665475379693387gmail-m_2627065711439770122LC25" style="color:rgb(36,41,46);font-family:Consolas,"Liberation Mono",Courier,monospace;font-size:14px;white-space:pre-wrap;box-sizing:border-box;padding:0px 15px"> <span class="gmail-m_2356665475379693387gmail-m_2627065711439770122pl-k" style="box-sizing:border-box;color:rgb(215,58,73)">return</span> result;</div><div class="gmail-m_2356665475379693387gmail-m_2627065711439770122line gmail-m_2356665475379693387gmail-m_2627065711439770122js-file-line" id="gmail-m_2356665475379693387gmail-m_2627065711439770122LC26" style="color:rgb(36,41,46);font-family:Consolas,"Liberation Mono",Courier,monospace;font-size:14px;white-space:pre-wrap;box-sizing:border-box;padding:0px 15px">}</div><div class="gmail-m_2356665475379693387gmail-m_2627065711439770122line gmail-m_2356665475379693387gmail-m_2627065711439770122js-file-line" id="gmail-m_2356665475379693387gmail-m_2627065711439770122LC26" style="color:rgb(36,41,46);font-family:Consolas,"Liberation Mono",Courier,monospace;font-size:14px;white-space:pre-wrap;box-sizing:border-box;padding:0px 15px"><br></div><div class="gmail-m_2356665475379693387gmail-m_2627065711439770122line gmail-m_2356665475379693387gmail-m_2627065711439770122js-file-line" id="gmail-m_2356665475379693387gmail-m_2627065711439770122LC26" style="color:rgb(36,41,46);font-family:Consolas,"Liberation Mono",Courier,monospace;font-size:14px;white-space:pre-wrap;box-sizing:border-box;padding:0px 15px">now consider the following steps:</div><div class="gmail-m_2356665475379693387gmail-m_2627065711439770122line gmail-m_2356665475379693387gmail-m_2627065711439770122js-file-line" id="gmail-m_2356665475379693387gmail-m_2627065711439770122LC26" style="color:rgb(36,41,46);font-family:Consolas,"Liberation Mono",Courier,monospace;font-size:14px;white-space:pre-wrap;box-sizing:border-box;padding:0px 15px">from the 2 constants (d and r) we create 3 constants (with the same bit length):</div><div class="gmail-m_2356665475379693387gmail-m_2627065711439770122line gmail-m_2356665475379693387gmail-m_2627065711439770122js-file-line" id="gmail-m_2356665475379693387gmail-m_2627065711439770122LC26" style="box-sizing:border-box;padding:0px 15px"><font color="#24292e" face="Consolas, Liberation Mono, Courier, monospace"><span style="font-size:14px;white-space:pre-wrap">constants uint32 s,u,mmi;</span></font></div><div class="gmail-m_2356665475379693387gmail-m_2627065711439770122line gmail-m_2356665475379693387gmail-m_2627065711439770122js-file-line" id="gmail-m_2356665475379693387gmail-m_2627065711439770122LC26" style="box-sizing:border-box;padding:0px 15px"><font color="#24292e" face="Consolas, Liberation Mono, Courier, monospace"><span style="font-size:14px;white-space:pre-wrap">mmi = </span></font><span style="color:rgb(111,66,193);font-family:Consolas,"Liberation Mono",Courier,monospace;font-size:14px;white-space:pre-wrap">find_mod_mul_inverse(d,32);</span></div><div class="gmail-m_2356665475379693387gmail-m_2627065711439770122line gmail-m_2356665475379693387gmail-m_2627065711439770122js-file-line" id="gmail-m_2356665475379693387gmail-m_2627065711439770122LC26" style="box-sizing:border-box;padding:0px 15px"><font color="#24292e" face="Consolas, Liberation Mono, Courier, monospace"><span style="font-size:14px;white-space:pre-wrap">s = (r*mmi);
u = (UINT32_MAX-r)/d; // </span></font><span style="color:rgb(36,41,46);font-family:Consolas,"Liberation Mono",Courier,monospace;font-size:14px;white-space:pre-wrap">UINT32_MAX corresponds to pow(2,32)-1.</span></div><div class="gmail-m_2356665475379693387gmail-m_2627065711439770122line gmail-m_2356665475379693387gmail-m_2627065711439770122js-file-line" id="gmail-m_2356665475379693387gmail-m_2627065711439770122LC26" style="box-sizing:border-box;padding:0px 15px"><span style="color:rgb(36,41,46);font-family:Consolas,"Liberation Mono",Courier,monospace;font-size:14px;white-space:pre-wrap">the idea behind these constants is the following formula:</span></div><div class="gmail-m_2356665475379693387gmail-m_2627065711439770122line gmail-m_2356665475379693387gmail-m_2627065711439770122js-file-line" id="gmail-m_2356665475379693387gmail-m_2627065711439770122LC26" style="box-sizing:border-box;padding:0px 15px"><span style="color:rgb(36,41,46);font-family:Consolas,"Liberation Mono",Courier,monospace;font-size:14px;white-space:pre-wrap">mmi_of(d)*x=x/d+(x%d)*mmi_of(d)</span></div><div class="gmail-m_2356665475379693387gmail-m_2627065711439770122line gmail-m_2356665475379693387gmail-m_2627065711439770122js-file-line" id="gmail-m_2356665475379693387gmail-m_2627065711439770122LC26" style="box-sizing:border-box;padding:0px 15px"><span style="color:rgb(36,41,46);font-family:Consolas,"Liberation Mono",Courier,monospace;font-size:14px;white-space:pre-wrap"><br></span></div><div class="gmail-m_2356665475379693387gmail-m_2627065711439770122line gmail-m_2356665475379693387gmail-m_2627065711439770122js-file-line" id="gmail-m_2356665475379693387gmail-m_2627065711439770122LC26" style="box-sizing:border-box;padding:0px 15px"><font color="#24292e" face="Consolas, Liberation Mono, Courier, monospace"><span style="font-size:14px;white-space:pre-wrap">now after we generated the constants, we will just emit the following code instead of the former:
</span></font><div style="font-family:"Helvetica Neue",Helvetica,Arial,sans-serif;white-space:normal">bool check_remainder(uint32 x)</div><div style="font-family:"Helvetica Neue",Helvetica,Arial,sans-serif;white-space:normal">{</div><div style="font-family:"Helvetica Neue",Helvetica,Arial,sans-serif;white-space:normal">return <span style="color:rgb(36,41,46);font-family:Consolas,"Liberation Mono",Courier,monospace;font-size:14px;white-space:pre-wrap">((x*mmi)-s)<=u</span>;</div><span style="font-family:"Helvetica Neue",Helvetica,Arial,sans-serif;white-space:normal">}</span><font color="#24292e" face="Consolas, Liberation Mono, Courier, monospace"><span style="font-size:14px;white-space:pre-wrap"><br></span></font></div><div class="gmail-m_2356665475379693387gmail-m_2627065711439770122line gmail-m_2356665475379693387gmail-m_2627065711439770122js-file-line" id="gmail-m_2356665475379693387gmail-m_2627065711439770122LC26" style="box-sizing:border-box;padding:0px 15px"><span style="font-family:"Helvetica Neue",Helvetica,Arial,sans-serif;white-space:normal"><br></span></div><div class="gmail-m_2356665475379693387gmail-m_2627065711439770122line gmail-m_2356665475379693387gmail-m_2627065711439770122js-file-line" id="gmail-m_2356665475379693387gmail-m_2627065711439770122LC26" style="box-sizing:border-box;padding:0px 15px"><span style="font-family:"Helvetica Neue",Helvetica,Arial,sans-serif;white-space:normal">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.</span></div></pre></div></div>
_______________________________________________<br>
LLVM Developers mailing list<br>
<a href="mailto:llvm-dev@lists.llvm.org" target="_blank">llvm-dev@lists.llvm.org</a><br>
<a href="https://lists.llvm.org/cgi-bin/mailman/listinfo/llvm-dev" rel="noreferrer" target="_blank">https://lists.llvm.org/cgi-bin/mailman/listinfo/llvm-dev</a><br>
</blockquote></div>