<div dir="ltr"><div>Looks like a good optimization, but I don't think it belongs in instcombine.</div><div>1. If you increase the variable uses in IR, you must insert "freeze" to make the transform poison-safe. That's why Alive2 says the transform is only safe with "-disable-undef-input":</div><div><a href="https://alive2.llvm.org/ce/z/jpYDi8">https://alive2.llvm.org/ce/z/jpYDi8</a></div><div><br></div><div>2. When expanding the urem, you might as well convert it to 'and' directly (as in the above Alive2 link) to make the optimization more directly.</div><div><br></div><div>3. If we are expanding the udiv in SDAG based on target hooks, this transform would be better placed there and use those same hooks to decide if the transform is desirable. For example, we probably don't want to expand if the optimization mode is set to minimize code size.<br></div></div><br><div class="gmail_quote"><div dir="ltr" class="gmail_attr">On Tue, Oct 12, 2021 at 4:04 PM Usman Nadeem via llvm-dev <<a href="mailto:llvm-dev@lists.llvm.org">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 style="overflow-wrap: break-word;" lang="EN-US">
<div class="gmail-m_3157845615901068517WordSection1">
<p class="MsoNormal">Hi all,<u></u><u></u></p>
<p class="MsoNormal"><u></u> <u></u></p>
<p class="MsoNormal"><a href="https://stackoverflow.com/a/68084577" target="_blank">https://stackoverflow.com/a/68084577</a> provides a simple transformation to optimize the calculation.<u></u><u></u></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" target="_blank">https://alive2.llvm.org/ce/z/gDn5xP</a><u></u><u></u></p>
<p class="MsoNormal"><u></u> <u></u></p>
<p class="MsoNormal">Godbolt link comparing assembly for Aarch64 and X86 to show the codegen improvements:
<a href="https://godbolt.org/z/qqb5enezr" target="_blank">https://godbolt.org/z/qqb5enezr</a> <u></u>
<u></u></p>
<p class="MsoNormal"><u></u> <u></u></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.<u></u><u></u></p>
<p class="MsoNormal"><u></u> <u></u></p>
<p class="MsoNormal">This looks like a simple transformation with a good impact, any thoughts?<u></u><u></u></p>
<p class="MsoNormal">--<u></u><u></u></p>
<p class="MsoNormal"><u></u> <u></u></p>
<p class="MsoNormal"><u></u> <u></u></p>
<p class="MsoNormal" style="line-height:125%;background:white none repeat scroll 0% 0%"><span style="font-size:10pt;line-height:125%;font-family:"Courier New";color:black;background:rgb(255,221,221) none repeat scroll 0% 0%">--- a/llvm/lib/Transforms/InstCombine/InstCombineMulDivRem.cpp</span><span style="font-size:10pt;line-height:125%;font-family:"Courier New""><u></u><u></u></span></p>
<p class="MsoNormal" style="line-height:125%;background:white none repeat scroll 0% 0%"><span style="font-size:10pt;line-height:125%;font-family:"Courier New";color:black;background:rgb(221,255,221) none repeat scroll 0% 0%">+++ b/llvm/lib/Transforms/InstCombine/InstCombineMulDivRem.cpp</span><span style="font-size:10pt;line-height:125%;font-family:"Courier New""><u></u><u></u></span></p>
<p class="MsoNormal" style="line-height:125%;background:white none repeat scroll 0% 0%"><span style="font-size:10pt;line-height:125%;font-family:"Courier New";color:rgb(102,102,102)">@@ -1508,6 +1508,18 @@ Instruction *InstCombinerImpl::visitURem(BinaryOperator &I) {</span><span style="font-size:10pt;line-height:125%;font-family:"Courier New""><u></u><u></u></span></p>
<p class="MsoNormal" style="line-height:125%;background:white none repeat scroll 0% 0%"><span style="font-size:10pt;line-height:125%;font-family:"Courier New";color:black"> return BinaryOperator::CreateAnd(Op0, Add);</span><span style="font-size:10pt;line-height:125%;font-family:"Courier New""><u></u><u></u></span></p>
<p class="MsoNormal" style="line-height:125%;background:white none repeat scroll 0% 0%"><span style="font-size:10pt;line-height:125%;font-family:"Courier New";color:black"> }</span><span style="font-size:10pt;line-height:125%;font-family:"Courier New""><u></u><u></u></span></p>
<p class="MsoNormal" style="line-height:125%;background:white none repeat scroll 0% 0%"><span style="font-size:10pt;line-height:125%;font-family:"Courier New""><u></u> <u></u></span></p>
<p class="MsoNormal" style="line-height:125%;background:white none repeat scroll 0% 0%"><span style="font-size:10pt;line-height:125%;font-family:"Courier New";color:black;background:rgb(221,255,221) none repeat scroll 0% 0%">+ // X urem Y --> (X + X/Y) urem Y+1 where Y+1 is a power of 2.</span><span style="font-size:10pt;line-height:125%;font-family:"Courier New""><u></u><u></u></span></p>
<p class="MsoNormal" style="line-height:125%;background:white none repeat scroll 0% 0%"><span style="font-size:10pt;line-height:125%;font-family:"Courier New";color:black;background:rgb(221,255,221) none repeat scroll 0% 0%">+ if (isa<ConstantInt>(Op1)) {</span><span style="font-size:10pt;line-height:125%;font-family:"Courier New""><u></u><u></u></span></p>
<p class="MsoNormal" style="line-height:125%;background:white none repeat scroll 0% 0%"><span style="font-size:10pt;line-height:125%;font-family:"Courier New";color:black;background:rgb(221,255,221) none repeat scroll 0% 0%">+ Value *PlusOne = Builder.CreateAdd(Op1, ConstantInt::get(Ty, 1));</span><span style="font-size:10pt;line-height:125%;font-family:"Courier New""><u></u><u></u></span></p>
<p class="MsoNormal" style="line-height:125%;background:white none repeat scroll 0% 0%"><span style="font-size:10pt;line-height:125%;font-family:"Courier New";color:black;background:rgb(221,255,221) none repeat scroll 0% 0%">+ if (isKnownToBeAPowerOfTwo(PlusOne, /*OrZero*/ false, 0, &I)) {</span><span style="font-size:10pt;line-height:125%;font-family:"Courier New""><u></u><u></u></span></p>
<p class="MsoNormal" style="line-height:125%;background:white none repeat scroll 0% 0%"><span style="font-size:10pt;line-height:125%;font-family:"Courier New";color:black;background:rgb(221,255,221) none repeat scroll 0% 0%">+ auto *Div = Builder.CreateUDiv(Op0, Op1);</span><span style="font-size:10pt;line-height:125%;font-family:"Courier New""><u></u><u></u></span></p>
<p class="MsoNormal" style="line-height:125%;background:white none repeat scroll 0% 0%"><span style="font-size:10pt;line-height:125%;font-family:"Courier New";color:black;background:rgb(221,255,221) none repeat scroll 0% 0%">+ auto *Add = Builder.CreateAdd(Op0, Div);</span><span style="font-size:10pt;line-height:125%;font-family:"Courier New""><u></u><u></u></span></p>
<p class="MsoNormal" style="line-height:125%;background:white none repeat scroll 0% 0%"><span style="font-size:10pt;line-height:125%;font-family:"Courier New";color:black;background:rgb(221,255,221) none repeat scroll 0% 0%">+ return BinaryOperator::CreateWithCopiedFlags(I.getOpcode(), Add, PlusOne,</span><span style="font-size:10pt;line-height:125%;font-family:"Courier New""><u></u><u></u></span></p>
<p class="MsoNormal" style="line-height:125%;background:white none repeat scroll 0% 0%"><span style="font-size:10pt;line-height:125%;font-family:"Courier New";color:black;background:rgb(221,255,221) none repeat scroll 0% 0%">+ &I);</span><span style="font-size:10pt;line-height:125%;font-family:"Courier New""><u></u><u></u></span></p>
<p class="MsoNormal" style="line-height:125%;background:white none repeat scroll 0% 0%"><span style="font-size:10pt;line-height:125%;font-family:"Courier New";color:black;background:rgb(221,255,221) none repeat scroll 0% 0%">+ }</span><span style="font-size:10pt;line-height:125%;font-family:"Courier New""><u></u><u></u></span></p>
<p class="MsoNormal" style="line-height:125%;background:white none repeat scroll 0% 0%"><span style="font-size:10pt;line-height:125%;font-family:"Courier New";color:black;background:rgb(221,255,221) none repeat scroll 0% 0%">+ }</span><span style="font-size:10pt;line-height:125%;font-family:"Courier New""><u></u><u></u></span></p>
<p class="MsoNormal" style="line-height:125%;background:white none repeat scroll 0% 0%"><span style="font-size:10pt;line-height:125%;font-family:"Courier New";color:black;background:rgb(221,255,221) none repeat scroll 0% 0%">+</span><span style="font-size:10pt;line-height:125%;font-family:"Courier New""><u></u><u></u></span></p>
<p class="MsoNormal"><u></u> <u></u></p>
</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>