<div dir="ltr"><div class="gmail_default" style="font-family:verdana,sans-serif">Dear Paweł,</div><div class="gmail_default" style="font-family:verdana,sans-serif"><br></div><div class="gmail_default" style="font-family:verdana,sans-serif">Thanks a lot! The solution helped!</div><div class="gmail_default" style="font-family:verdana,sans-serif"><br></div><div><div dir="ltr" class="gmail_signature" data-smartmail="gmail_signature"><div dir="ltr"><div><div dir="ltr"><font face="verdana, sans-serif">Thank you!<br>Regards,<br>Vivek JP Pandey,<br>Software Professional,<br><font color="#351c75" size="1"><b>+91-7775054441</b></font></font><br></div></div></div></div></div><br></div><br><div class="gmail_quote"><div dir="ltr" class="gmail_attr">On Thu, May 21, 2020 at 7:08 PM Paweł Bylica <<a href="mailto:chfast@gmail.com">chfast@gmail.com</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"><div dir="ltr"><div>Hi,</div><div><br></div><div>First of all, the code in compiler-rt/builtins is rather confusing for me. No idea what `tu_int` is but I'm guessing this must be `unsigned __int128`, not `unsigned long long`.<br><a href="https://github.com/llvm/llvm-project/blob/master/compiler-rt/lib/builtins/udivmodti4.c#L22" target="_blank">https://github.com/llvm/llvm-project/blob/master/compiler-rt/lib/builtins/udivmodti4.c#L22</a></div><div><br></div><div>Secondly the "slow" case proceeds single bit at a time, so this loop may need ~64 iterations in worst case:<br><a href="https://github.com/llvm/llvm-project/blob/master/compiler-rt/lib/builtins/udivmodti4.c#L167-L188" target="_blank">https://github.com/llvm/llvm-project/blob/master/compiler-rt/lib/builtins/udivmodti4.c#L167-L188</a><br><br></div><div>From measurements, it looks GCC has it implemented more efficiently although I have no idea where do they have the code for it.</div><div><br></div><div>If you are interested, I have division implemented for unsigned 128-bit integer here: <a href="https://github.com/chfast/intx/blob/master/include/intx/int128.hpp#L632-L687" target="_blank">https://github.com/chfast/intx/blob/master/include/intx/int128.hpp#L632-L687</a><br></div><div>From quick check it takes 16 ns, GCC runtime lib: 25 ns, GMP: 20 ns.<br><br></div><div>It follows "Improved division by invariant integers" <a href="https://gmplib.org/~tege/division-paper.pdf" target="_blank">https://gmplib.org/~tege/division-paper.pdf</a></div><div><br></div><div>If make sense I can contribute this implementation as replacement for `__udivmodti4`. Although I'm not sure what requirements for __udivmodti4 are.<br></div><div><br>--<br></div><div>Paweł<br></div><div><br></div></div><br><div class="gmail_quote"><div dir="ltr" class="gmail_attr">On Thu, May 21, 2020 at 11:30 AM Vivek Pandey 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"><div dir="ltr"><div class="gmail_default" style="font-family:verdana,sans-serif">Hi Team,</div><div class="gmail_default" style="font-family:verdana,sans-serif"><br></div><div class="gmail_default" style="font-family:verdana,sans-serif">I observer that division of __int128 bit is very heavy operation.</div><div class="gmail_default" style="font-family:verdana,sans-serif">It internally call a routine '<span style="background-color:yellow;color:rgb(85,85,85);font-family:Consolas;font-size:9.5pt">__udivti3</span>', which internally call '<span style="background-color:yellow;color:rgb(85,85,85);font-family:Consolas;font-size:9.5pt">__udivmodti4</span>'. </div><div class="gmail_default" style="font-family:verdana,sans-serif"><br></div><div class="gmail_default" style="font-family:verdana,sans-serif">Due to it the overall performance is much much slower (almost 15 time slower than if I do it via a combination of 64-bit or microsoft '<span style="font-size:10pt;font-family:"Courier New"">_udiv128</span>').</div><div class="gmail_default" style="font-family:verdana,sans-serif"><br></div><div class="gmail_default" style="font-family:verdana,sans-serif">Also what to know if I can directly call below routine directly from my code : </div><div class="gmail_default" style="font-family:verdana,sans-serif"><em><span style="font-size:11pt;font-family:Calibri,sans-serif;color:black">unsigned
long long</span></em><span style="font-size:11pt;font-family:Calibri,sans-serif;color:black"> <strong>__udivmodti4</strong> <em>(unsigned long long </em><var>a</var><em>, unsigned long long </em><var>b</var><em>, unsigned long long *</em><var>c</var><em>)</em></span><br></div><div class="gmail_default" style="font-family:verdana,sans-serif"><br></div><div class="gmail_default" style="font-family:verdana,sans-serif">This is against statement  "<span style="font-size:10pt;font-family:"Courier New";color:black">Conceptually,in
operation, like ‘/’ or ‘%’, no function is called, so no header is provided for
</span><strong style="font-family:Arial,Helvetica,sans-serif"><span style="font-size:11pt;font-family:Calibri,sans-serif;color:black">__udivmodti4</span></strong><span style="font-size:10pt;font-family:"Courier New";color:black"> etc. – and we should not
call them explicitly in our code.</span>" but wanted to know more on it.</div><div class="gmail_default" style="font-family:verdana,sans-serif"><br></div><div><div dir="ltr"><div dir="ltr"><div><div dir="ltr"><font face="verdana, sans-serif">Thank you!<br>Regards,<br>Vivek JP Pandey,<br>Software Professional,<br><font size="1" color="#351c75"><b>+91-7775054441</b></font></font><br></div></div></div></div></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>
</blockquote></div>