<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=us-ascii">
<meta name="Generator" content="Microsoft Word 15 (filtered medium)">
<style><!--
/* Font Definitions */
@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;}
/* Style Definitions */
p.MsoNormal, li.MsoNormal, div.MsoNormal
{margin:0in;
font-size:11.0pt;
font-family:"Calibri",sans-serif;}
a:link, span.MsoHyperlink
{mso-style-priority:99;
color:#0563C1;
text-decoration:underline;}
span.EmailStyle21
{mso-style-type:personal-compose;
font-family:"Calibri",sans-serif;
color:windowtext;}
.MsoChpDefault
{mso-style-type:export-only;
font-size:10.0pt;
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="#0563C1" vlink="#954F72" style="word-wrap:break-word">
<div class="WordSection1">
<p class="MsoNormal">Hi all,<o:p></o:p></p>
<p class="MsoNormal"><o:p> </o:p></p>
<p class="MsoNormal"><a href="https://stackoverflow.com/a/68084577">https://stackoverflow.com/a/68084577</a> provides a simple transformation to optimize the calculation.<o:p></o:p></p>
<p class="MsoNormal">I don’t know about its the correctness but at least alive tv says that the transformation is correct:
<a href="https://alive2.llvm.org/ce/z/gDn5xP">https://alive2.llvm.org/ce/z/gDn5xP</a><o:p></o:p></p>
<p class="MsoNormal"><o:p> </o:p></p>
<p class="MsoNormal">Godbolt link comparing assembly for Aarch64 and X86 to show the codegen improvements:
<a href="https://godbolt.org/z/qqb5enezr">https://godbolt.org/z/qqb5enezr</a> <o:p>
</o:p></p>
<p class="MsoNormal"><o:p> </o:p></p>
<p class="MsoNormal">I made a change in instcombine (copied below) to see the impact and looked at some cases. For Aarch64 it resulted in either fewer or same number of instructions and in many cases the new sequence of instructions was cheaper.<o:p></o:p></p>
<p class="MsoNormal"><o:p> </o:p></p>
<p class="MsoNormal">This looks like a simple transformation with a good impact, any thoughts?<o:p></o:p></p>
<p class="MsoNormal">--<o:p></o:p></p>
<p class="MsoNormal"><o:p> </o:p></p>
<p class="MsoNormal"><o:p> </o:p></p>
<p class="MsoNormal" style="line-height:125%;background:white"><span style="font-size:10.0pt;line-height:125%;font-family:"Courier New";color:black;background:#FFDDDD">--- a/llvm/lib/Transforms/InstCombine/InstCombineMulDivRem.cpp</span><span style="font-size:10.0pt;line-height:125%;font-family:"Courier New""><o:p></o:p></span></p>
<p class="MsoNormal" style="line-height:125%;background:white"><span style="font-size:10.0pt;line-height:125%;font-family:"Courier New";color:black;background:#DDFFDD">+++ b/llvm/lib/Transforms/InstCombine/InstCombineMulDivRem.cpp</span><span style="font-size:10.0pt;line-height:125%;font-family:"Courier New""><o:p></o:p></span></p>
<p class="MsoNormal" style="line-height:125%;background:white"><span style="font-size:10.0pt;line-height:125%;font-family:"Courier New";color:#666666">@@ -1508,6 +1508,18 @@ Instruction *InstCombinerImpl::visitURem(BinaryOperator &I) {</span><span style="font-size:10.0pt;line-height:125%;font-family:"Courier New""><o:p></o:p></span></p>
<p class="MsoNormal" style="line-height:125%;background:white"><span style="font-size:10.0pt;line-height:125%;font-family:"Courier New";color:black"> return BinaryOperator::CreateAnd(Op0, Add);</span><span style="font-size:10.0pt;line-height:125%;font-family:"Courier New""><o:p></o:p></span></p>
<p class="MsoNormal" style="line-height:125%;background:white"><span style="font-size:10.0pt;line-height:125%;font-family:"Courier New";color:black"> }</span><span style="font-size:10.0pt;line-height:125%;font-family:"Courier New""><o:p></o:p></span></p>
<p class="MsoNormal" style="line-height:125%;background:white"><span style="font-size:10.0pt;line-height:125%;font-family:"Courier New""><o:p> </o:p></span></p>
<p class="MsoNormal" style="line-height:125%;background:white"><span style="font-size:10.0pt;line-height:125%;font-family:"Courier New";color:black;background:#DDFFDD">+ // X urem Y --> (X + X/Y) urem Y+1 where Y+1 is a power of 2.</span><span style="font-size:10.0pt;line-height:125%;font-family:"Courier New""><o:p></o:p></span></p>
<p class="MsoNormal" style="line-height:125%;background:white"><span style="font-size:10.0pt;line-height:125%;font-family:"Courier New";color:black;background:#DDFFDD">+ if (isa<ConstantInt>(Op1)) {</span><span style="font-size:10.0pt;line-height:125%;font-family:"Courier New""><o:p></o:p></span></p>
<p class="MsoNormal" style="line-height:125%;background:white"><span style="font-size:10.0pt;line-height:125%;font-family:"Courier New";color:black;background:#DDFFDD">+ Value *PlusOne = Builder.CreateAdd(Op1, ConstantInt::get(Ty, 1));</span><span style="font-size:10.0pt;line-height:125%;font-family:"Courier New""><o:p></o:p></span></p>
<p class="MsoNormal" style="line-height:125%;background:white"><span style="font-size:10.0pt;line-height:125%;font-family:"Courier New";color:black;background:#DDFFDD">+ if (isKnownToBeAPowerOfTwo(PlusOne, /*OrZero*/ false, 0, &I)) {</span><span style="font-size:10.0pt;line-height:125%;font-family:"Courier New""><o:p></o:p></span></p>
<p class="MsoNormal" style="line-height:125%;background:white"><span style="font-size:10.0pt;line-height:125%;font-family:"Courier New";color:black;background:#DDFFDD">+ auto *Div = Builder.CreateUDiv(Op0, Op1);</span><span style="font-size:10.0pt;line-height:125%;font-family:"Courier New""><o:p></o:p></span></p>
<p class="MsoNormal" style="line-height:125%;background:white"><span style="font-size:10.0pt;line-height:125%;font-family:"Courier New";color:black;background:#DDFFDD">+ auto *Add = Builder.CreateAdd(Op0, Div);</span><span style="font-size:10.0pt;line-height:125%;font-family:"Courier New""><o:p></o:p></span></p>
<p class="MsoNormal" style="line-height:125%;background:white"><span style="font-size:10.0pt;line-height:125%;font-family:"Courier New";color:black;background:#DDFFDD">+ return BinaryOperator::CreateWithCopiedFlags(I.getOpcode(), Add, PlusOne,</span><span style="font-size:10.0pt;line-height:125%;font-family:"Courier New""><o:p></o:p></span></p>
<p class="MsoNormal" style="line-height:125%;background:white"><span style="font-size:10.0pt;line-height:125%;font-family:"Courier New";color:black;background:#DDFFDD">+ &I);</span><span style="font-size:10.0pt;line-height:125%;font-family:"Courier New""><o:p></o:p></span></p>
<p class="MsoNormal" style="line-height:125%;background:white"><span style="font-size:10.0pt;line-height:125%;font-family:"Courier New";color:black;background:#DDFFDD">+ }</span><span style="font-size:10.0pt;line-height:125%;font-family:"Courier New""><o:p></o:p></span></p>
<p class="MsoNormal" style="line-height:125%;background:white"><span style="font-size:10.0pt;line-height:125%;font-family:"Courier New";color:black;background:#DDFFDD">+ }</span><span style="font-size:10.0pt;line-height:125%;font-family:"Courier New""><o:p></o:p></span></p>
<p class="MsoNormal" style="line-height:125%;background:white"><span style="font-size:10.0pt;line-height:125%;font-family:"Courier New";color:black;background:#DDFFDD">+</span><span style="font-size:10.0pt;line-height:125%;font-family:"Courier New""><o:p></o:p></span></p>
<p class="MsoNormal"><o:p> </o:p></p>
</div>
</body>
</html>