<html xmlns:v="urn:schemas-microsoft-com:vml" xmlns:o="urn:schemas-microsoft-com:office:office" xmlns:w="urn:schemas-microsoft-com:office:word" xmlns:m="http://schemas.microsoft.com/office/2004/12/omml" xmlns="http://www.w3.org/TR/REC-html40">
<head>
<meta http-equiv="Content-Type" content="text/html; charset=utf-8">
<meta name="Generator" content="Microsoft Word 15 (filtered medium)">
<style><!--
/* Font Definitions */
@font-face
{font-family:Helvetica;
panose-1:2 11 6 4 2 2 2 2 2 4;}
@font-face
{font-family:"Cambria Math";
panose-1:2 4 5 3 5 4 6 3 2 4;}
@font-face
{font-family:Calibri;
panose-1:2 15 5 2 2 2 4 3 2 4;}
@font-face
{font-family:Consolas;
panose-1:2 11 6 9 2 2 4 3 2 4;}
/* Style Definitions */
p.MsoNormal, li.MsoNormal, div.MsoNormal
{margin:0in;
margin-bottom:.0001pt;
font-size:11.0pt;
font-family:"Calibri",sans-serif;}
a:link, span.MsoHyperlink
{mso-style-priority:99;
color:blue;
text-decoration:underline;}
a:visited, span.MsoHyperlinkFollowed
{mso-style-priority:99;
color:purple;
text-decoration:underline;}
pre
{mso-style-priority:99;
mso-style-link:"HTML Preformatted Char";
margin:0in;
margin-bottom:.0001pt;
font-size:10.0pt;
font-family:"Courier New";}
p.msonormal0, li.msonormal0, div.msonormal0
{mso-style-name:msonormal;
mso-margin-top-alt:auto;
margin-right:0in;
mso-margin-bottom-alt:auto;
margin-left:0in;
font-size:11.0pt;
font-family:"Calibri",sans-serif;}
span.HTMLPreformattedChar
{mso-style-name:"HTML Preformatted Char";
mso-style-priority:99;
mso-style-link:"HTML Preformatted";
font-family:Consolas;}
span.gmail-m2356665475379693387gmail-m2627065711439770122pl-c1
{mso-style-name:gmail-m_2356665475379693387gmail-m_2627065711439770122pl-c1;}
span.gmail-m2356665475379693387gmail-m2627065711439770122pl-en
{mso-style-name:gmail-m_2356665475379693387gmail-m_2627065711439770122pl-en;}
span.gmail-m2356665475379693387gmail-m2627065711439770122pl-k
{mso-style-name:gmail-m_2356665475379693387gmail-m_2627065711439770122pl-k;}
span.EmailStyle23
{mso-style-type:personal-reply;
font-family:"Calibri",sans-serif;
color:windowtext;}
.MsoChpDefault
{mso-style-type:export-only;
font-family:"Calibri",sans-serif;}
@page WordSection1
{size:8.5in 11.0in;
margin:1.0in 1.0in 1.0in 1.0in;}
div.WordSection1
{page:WordSection1;}
--></style><!--[if gte mso 9]><xml>
<o:shapedefaults v:ext="edit" spidmax="1026" />
</xml><![endif]--><!--[if gte mso 9]><xml>
<o:shapelayout v:ext="edit">
<o:idmap v:ext="edit" data="1" />
</o:shapelayout></xml><![endif]-->
</head>
<body lang="EN-US" link="blue" vlink="purple">
<div class="WordSection1">
<p class="MsoNormal">There’s a work-in-progress patch for the case r=0: <a href="https://reviews.llvm.org/D50222">
https://reviews.llvm.org/D50222</a> . (Not sure what the current status of that patch is.)<o:p></o:p></p>
<p class="MsoNormal"><o:p> </o:p></p>
<p class="MsoNormal">-Eli<o:p></o:p></p>
<p class="MsoNormal"><o:p> </o:p></p>
<div style="border:none;border-left:solid blue 1.5pt;padding:0in 0in 0in 4.0pt">
<div>
<div style="border:none;border-top:solid #E1E1E1 1.0pt;padding:3.0pt 0in 0in 0in">
<p class="MsoNormal"><b>From:</b> llvm-dev <llvm-dev-bounces@lists.llvm.org> <b>On Behalf Of
</b>Craig Topper via llvm-dev<br>
<b>Sent:</b> Wednesday, February 20, 2019 9:27 PM<br>
<b>To:</b> or dv <dvoreader@gmail.com><br>
<b>Cc:</b> llvm-dev <llvm-dev@lists.llvm.org><br>
<b>Subject:</b> [EXT] Re: [llvm-dev] proposal for optimization method<o:p></o:p></p>
</div>
</div>
<p class="MsoNormal"><o:p> </o:p></p>
<div>
<div>
<div>
<p class="MsoNormal">It looks like gcc already does something like this. <a href="https://godbolt.org/z/JWljkL" target="_blank">https://godbolt.org/z/JWljkL</a><o:p></o:p></p>
</div>
<p class="MsoNormal"><br clear="all">
<o:p></o:p></p>
<div>
<div>
<p class="MsoNormal">~Craig<o:p></o:p></p>
</div>
</div>
<p class="MsoNormal"><o:p> </o:p></p>
</div>
</div>
<p class="MsoNormal"><o:p> </o:p></p>
<div>
<div>
<p class="MsoNormal">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:<o:p></o:p></p>
</div>
<blockquote style="border:none;border-left:solid #CCCCCC 1.0pt;padding:0in 0in 0in 6.0pt;margin-left:4.8pt;margin-right:0in">
<p class="MsoNormal">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.):<o:p></o:p></p>
<div>
<p class="MsoNormal"><o:p> </o:p></p>
<div>
<p class="MsoNormal">const uint32 d,r;//d is an odd number<o:p></o:p></p>
</div>
<div>
<p class="MsoNormal">//d is the divisor, r is the remainder<o:p></o:p></p>
</div>
<div>
<p class="MsoNormal">bool check_remainder(uint32 x)<o:p></o:p></p>
</div>
<div>
<p class="MsoNormal">{<o:p></o:p></p>
</div>
<div>
<p class="MsoNormal">return x%d==r;<o:p></o:p></p>
</div>
<div>
<p class="MsoNormal">}<o:p></o:p></p>
</div>
<div>
<p class="MsoNormal"><o:p> </o:p></p>
</div>
<div>
<p class="MsoNormal">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.<o:p></o:p></p>
</div>
<div>
<p class="MsoNormal">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).<o:p></o:p></p>
</div>
<div>
<div id="gmail-m_2356665475379693387gmail-m_2627065711439770122LC3">
<pre><span class="gmail-m2356665475379693387gmail-m2627065711439770122pl-c1"><span style="font-size:10.5pt;font-family:Consolas;color:#005CC5">uint64_t</span></span><span style="font-size:10.5pt;font-family:Consolas;color:#24292E"> </span><span class="gmail-m2356665475379693387gmail-m2627065711439770122pl-en"><span style="font-size:10.5pt;font-family:Consolas;color:#6F42C1">find_mod_mul_inverse</span></span><span style="font-size:10.5pt;font-family:Consolas;color:#24292E">(</span><span class="gmail-m2356665475379693387gmail-m2627065711439770122pl-c1"><span style="font-size:10.5pt;font-family:Consolas;color:#005CC5">uint64_t</span></span><span style="font-size:10.5pt;font-family:Consolas;color:#24292E"> x, </span><span class="gmail-m2356665475379693387gmail-m2627065711439770122pl-c1"><span style="font-size:10.5pt;font-family:Consolas;color:#005CC5">uint64_t</span></span><span style="font-size:10.5pt;font-family:Consolas;color:#24292E"> bits)<o:p></o:p></span></pre>
</div>
<div id="gmail-m_2356665475379693387gmail-m_2627065711439770122LC4">
<pre><span style="font-size:10.5pt;font-family:Consolas;color:#24292E">{<o:p></o:p></span></pre>
</div>
<div id="gmail-m_2356665475379693387gmail-m_2627065711439770122LC5">
<pre><span style="font-size:10.5pt;font-family:Consolas;color:#24292E"> </span><span class="gmail-m2356665475379693387gmail-m2627065711439770122pl-k"><span style="font-size:10.5pt;font-family:Consolas;color:#D73A49">if</span></span><span style="font-size:10.5pt;font-family:Consolas;color:#24292E"> (bits > </span><span class="gmail-m2356665475379693387gmail-m2627065711439770122pl-c1"><span style="font-size:10.5pt;font-family:Consolas;color:#005CC5">64</span></span><span style="font-size:10.5pt;font-family:Consolas;color:#24292E"> || ((x&</span><span class="gmail-m2356665475379693387gmail-m2627065711439770122pl-c1"><span style="font-size:10.5pt;font-family:Consolas;color:#005CC5">1</span></span><span style="font-size:10.5pt;font-family:Consolas;color:#24292E">)==</span><span class="gmail-m2356665475379693387gmail-m2627065711439770122pl-c1"><span style="font-size:10.5pt;font-family:Consolas;color:#005CC5">0</span></span><span style="font-size:10.5pt;font-family:Consolas;color:#24292E">))<o:p></o:p></span></pre>
</div>
<div id="gmail-m_2356665475379693387gmail-m_2627065711439770122LC6">
<pre><span style="font-size:10.5pt;font-family:Consolas;color:#24292E"> </span><span class="gmail-m2356665475379693387gmail-m2627065711439770122pl-k"><span style="font-size:10.5pt;font-family:Consolas;color:#D73A49">return</span></span><span style="font-size:10.5pt;font-family:Consolas;color:#24292E"> </span><span class="gmail-m2356665475379693387gmail-m2627065711439770122pl-c1"><span style="font-size:10.5pt;font-family:Consolas;color:#005CC5">0</span></span><span style="font-size:10.5pt;font-family:Consolas;color:#24292E">;// invalid parameters<o:p></o:p></span></pre>
</div>
<div id="gmail-m_2356665475379693387gmail-m_2627065711439770122LC7">
<pre><span style="font-size:10.5pt;font-family:Consolas;color:#24292E"> </span><span class="gmail-m2356665475379693387gmail-m2627065711439770122pl-c1"><span style="font-size:10.5pt;font-family:Consolas;color:#005CC5">uint64_t</span></span><span style="font-size:10.5pt;font-family:Consolas;color:#24292E"> mask;<o:p></o:p></span></pre>
</div>
<div id="gmail-m_2356665475379693387gmail-m_2627065711439770122LC8">
<pre><span style="font-size:10.5pt;font-family:Consolas;color:#24292E"> </span><span class="gmail-m2356665475379693387gmail-m2627065711439770122pl-k"><span style="font-size:10.5pt;font-family:Consolas;color:#D73A49">if</span></span><span style="font-size:10.5pt;font-family:Consolas;color:#24292E"> (bits == </span><span class="gmail-m2356665475379693387gmail-m2627065711439770122pl-c1"><span style="font-size:10.5pt;font-family:Consolas;color:#005CC5">64</span></span><span style="font-size:10.5pt;font-family:Consolas;color:#24292E">)<o:p></o:p></span></pre>
</div>
<div id="gmail-m_2356665475379693387gmail-m_2627065711439770122LC9">
<pre><span style="font-size:10.5pt;font-family:Consolas;color:#24292E"> mask = -</span><span class="gmail-m2356665475379693387gmail-m2627065711439770122pl-c1"><span style="font-size:10.5pt;font-family:Consolas;color:#005CC5">1</span></span><span style="font-size:10.5pt;font-family:Consolas;color:#24292E">;<o:p></o:p></span></pre>
</div>
<div id="gmail-m_2356665475379693387gmail-m_2627065711439770122LC10">
<pre><span style="font-size:10.5pt;font-family:Consolas;color:#24292E"> </span><span class="gmail-m2356665475379693387gmail-m2627065711439770122pl-k"><span style="font-size:10.5pt;font-family:Consolas;color:#D73A49">else</span></span><span style="font-size:10.5pt;font-family:Consolas;color:#24292E"><o:p></o:p></span></pre>
</div>
<div id="gmail-m_2356665475379693387gmail-m_2627065711439770122LC11">
<pre><span style="font-size:10.5pt;font-family:Consolas;color:#24292E"> { <o:p></o:p></span></pre>
</div>
<div id="gmail-m_2356665475379693387gmail-m_2627065711439770122LC12">
<pre><span style="font-size:10.5pt;font-family:Consolas;color:#24292E"> mask = </span><span class="gmail-m2356665475379693387gmail-m2627065711439770122pl-c1"><span style="font-size:10.5pt;font-family:Consolas;color:#005CC5">1</span></span><span style="font-size:10.5pt;font-family:Consolas;color:#24292E">;<o:p></o:p></span></pre>
</div>
<div id="gmail-m_2356665475379693387gmail-m_2627065711439770122LC13">
<pre><span style="font-size:10.5pt;font-family:Consolas;color:#24292E"> mask<<=bits;<o:p></o:p></span></pre>
</div>
<div id="gmail-m_2356665475379693387gmail-m_2627065711439770122LC14">
<pre><span style="font-size:10.5pt;font-family:Consolas;color:#24292E"> mask--;<o:p></o:p></span></pre>
</div>
<div id="gmail-m_2356665475379693387gmail-m_2627065711439770122LC15">
<pre><span style="font-size:10.5pt;font-family:Consolas;color:#24292E"> }<o:p></o:p></span></pre>
</div>
<div id="gmail-m_2356665475379693387gmail-m_2627065711439770122LC16">
<pre><span style="font-size:10.5pt;font-family:Consolas;color:#24292E"> x&=mask;<o:p></o:p></span></pre>
</div>
<div id="gmail-m_2356665475379693387gmail-m_2627065711439770122LC17">
<pre><span style="font-size:10.5pt;font-family:Consolas;color:#24292E"> </span><span class="gmail-m2356665475379693387gmail-m2627065711439770122pl-c1"><span style="font-size:10.5pt;font-family:Consolas;color:#005CC5">uint64_t</span></span><span style="font-size:10.5pt;font-family:Consolas;color:#24292E"> result=</span><span class="gmail-m2356665475379693387gmail-m2627065711439770122pl-c1"><span style="font-size:10.5pt;font-family:Consolas;color:#005CC5">1</span></span><span style="font-size:10.5pt;font-family:Consolas;color:#24292E">, state=x, ctz=</span><span class="gmail-m2356665475379693387gmail-m2627065711439770122pl-c1"><span style="font-size:10.5pt;font-family:Consolas;color:#005CC5">0</span></span><span style="font-size:10.5pt;font-family:Consolas;color:#24292E">;<o:p></o:p></span></pre>
</div>
<div id="gmail-m_2356665475379693387gmail-m_2627065711439770122LC18">
<pre><span style="font-size:10.5pt;font-family:Consolas;color:#24292E"> </span><span class="gmail-m2356665475379693387gmail-m2627065711439770122pl-k"><span style="font-size:10.5pt;font-family:Consolas;color:#D73A49">while</span></span><span style="font-size:10.5pt;font-family:Consolas;color:#24292E">(state!=</span><span class="gmail-m2356665475379693387gmail-m2627065711439770122pl-c1"><span style="font-size:10.5pt;font-family:Consolas;color:#005CC5">1ULL</span></span><span style="font-size:10.5pt;font-family:Consolas;color:#24292E">)<o:p></o:p></span></pre>
</div>
<div id="gmail-m_2356665475379693387gmail-m_2627065711439770122LC19">
<pre><span style="font-size:10.5pt;font-family:Consolas;color:#24292E"> {<o:p></o:p></span></pre>
</div>
<div id="gmail-m_2356665475379693387gmail-m_2627065711439770122LC20">
<pre><span style="font-size:10.5pt;font-family:Consolas;color:#24292E"> ctz=</span><span class="gmail-m2356665475379693387gmail-m2627065711439770122pl-c1"><span style="font-size:10.5pt;font-family:Consolas;color:#005CC5">__builtin_ctzll</span></span><span style="font-size:10.5pt;font-family:Consolas;color:#24292E">(state^</span><span class="gmail-m2356665475379693387gmail-m2627065711439770122pl-c1"><span style="font-size:10.5pt;font-family:Consolas;color:#005CC5">1</span></span><span style="font-size:10.5pt;font-family:Consolas;color:#24292E">);<o:p></o:p></span></pre>
</div>
<div id="gmail-m_2356665475379693387gmail-m_2627065711439770122LC21">
<pre><span style="font-size:10.5pt;font-family:Consolas;color:#24292E"> result|=</span><span class="gmail-m2356665475379693387gmail-m2627065711439770122pl-c1"><span style="font-size:10.5pt;font-family:Consolas;color:#005CC5">1ULL</span></span><span style="font-size:10.5pt;font-family:Consolas;color:#24292E"><<ctz;<o:p></o:p></span></pre>
</div>
<div id="gmail-m_2356665475379693387gmail-m_2627065711439770122LC22">
<pre><span style="font-size:10.5pt;font-family:Consolas;color:#24292E"> state+=x<<ctz;<o:p></o:p></span></pre>
</div>
<div id="gmail-m_2356665475379693387gmail-m_2627065711439770122LC23">
<pre><span style="font-size:10.5pt;font-family:Consolas;color:#24292E"> state&=mask;<o:p></o:p></span></pre>
</div>
<div id="gmail-m_2356665475379693387gmail-m_2627065711439770122LC24">
<pre><span style="font-size:10.5pt;font-family:Consolas;color:#24292E"> }<o:p></o:p></span></pre>
</div>
<div id="gmail-m_2356665475379693387gmail-m_2627065711439770122LC25">
<pre><span style="font-size:10.5pt;font-family:Consolas;color:#24292E"> </span><span class="gmail-m2356665475379693387gmail-m2627065711439770122pl-k"><span style="font-size:10.5pt;font-family:Consolas;color:#D73A49">return</span></span><span style="font-size:10.5pt;font-family:Consolas;color:#24292E"> result;<o:p></o:p></span></pre>
</div>
<div id="gmail-m_2356665475379693387gmail-m_2627065711439770122LC26">
<pre><span style="font-size:10.5pt;font-family:Consolas;color:#24292E">}<o:p></o:p></span></pre>
</div>
<div id="gmail-m_2356665475379693387gmail-m_2627065711439770122LC26">
<pre><span style="font-size:10.5pt;font-family:Consolas;color:#24292E"><o:p> </o:p></span></pre>
</div>
<div id="gmail-m_2356665475379693387gmail-m_2627065711439770122LC26">
<pre><span style="font-size:10.5pt;font-family:Consolas;color:#24292E">now consider the following steps:<o:p></o:p></span></pre>
</div>
<div id="gmail-m_2356665475379693387gmail-m_2627065711439770122LC26">
<pre><span style="font-size:10.5pt;font-family:Consolas;color:#24292E">from the 2 constants (d and r) we create 3 constants (with the same bit length):<o:p></o:p></span></pre>
</div>
<div id="gmail-m_2356665475379693387gmail-m_2627065711439770122LC26">
<pre><span style="font-size:10.5pt;font-family:Consolas;color:#24292E">constants uint32 s,u,mmi;</span><o:p></o:p></pre>
</div>
<div id="gmail-m_2356665475379693387gmail-m_2627065711439770122LC26">
<pre><span style="font-size:10.5pt;font-family:Consolas;color:#24292E">mmi = </span><span style="font-size:10.5pt;font-family:Consolas;color:#6F42C1">find_mod_mul_inverse(d,32);</span><o:p></o:p></pre>
</div>
<div id="gmail-m_2356665475379693387gmail-m_2627065711439770122LC26">
<pre><span style="font-size:10.5pt;font-family:Consolas;color:#24292E">s = (r*mmi);<o:p></o:p></span></pre>
<pre><span style="font-size:10.5pt;font-family:Consolas;color:#24292E">u = (UINT32_MAX-r)/d; // UINT32_MAX corresponds to pow(2,32)-1.</span><o:p></o:p></pre>
</div>
<div id="gmail-m_2356665475379693387gmail-m_2627065711439770122LC26">
<pre><span style="font-size:10.5pt;font-family:Consolas;color:#24292E">the idea behind these constants is the following formula:</span><o:p></o:p></pre>
</div>
<div id="gmail-m_2356665475379693387gmail-m_2627065711439770122LC26">
<pre><span style="font-size:10.5pt;font-family:Consolas;color:#24292E">mmi_of(d)*x=x/d+(x%d)*mmi_of(d)</span><o:p></o:p></pre>
</div>
<div id="gmail-m_2356665475379693387gmail-m_2627065711439770122LC26">
<pre><o:p> </o:p></pre>
</div>
<div id="gmail-m_2356665475379693387gmail-m_2627065711439770122LC26">
<pre><span style="font-size:10.5pt;font-family:Consolas;color:#24292E">now after we generated the constants, we will just emit the following code instead of the former:<o:p></o:p></span></pre>
<div>
<pre><span style="font-family:"Helvetica",sans-serif">bool check_remainder(uint32 x)<o:p></o:p></span></pre>
</div>
<div>
<pre><span style="font-family:"Helvetica",sans-serif">{<o:p></o:p></span></pre>
</div>
<div>
<pre><span style="font-family:"Helvetica",sans-serif">return </span><span style="font-size:10.5pt;font-family:Consolas;color:#24292E">((x*mmi)-s)<=u</span><span style="font-family:"Helvetica",sans-serif">;<o:p></o:p></span></pre>
</div>
<pre><span style="font-family:"Helvetica",sans-serif">}</span><o:p></o:p></pre>
</div>
<div id="gmail-m_2356665475379693387gmail-m_2627065711439770122LC26">
<pre><o:p> </o:p></pre>
</div>
<div id="gmail-m_2356665475379693387gmail-m_2627065711439770122LC26">
<pre><span style="font-family:"Helvetica",sans-serif">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><o:p></o:p></pre>
</div>
</div>
</div>
<p class="MsoNormal">_______________________________________________<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" target="_blank">https://lists.llvm.org/cgi-bin/mailman/listinfo/llvm-dev</a><o:p></o:p></p>
</blockquote>
</div>
</div>
</div>
</body>
</html>