<div dir="ltr">Patch posted for review here <a href="https://reviews.llvm.org/D64190">https://reviews.llvm.org/D64190</a><div><br></div><div>~Craig</div></div><br><div class="gmail_quote"><div dir="ltr" class="gmail_attr">On Wed, Jul 3, 2019 at 5:28 PM Craig Topper <<a href="mailto:craig.topper@gmail.com">craig.topper@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">This patch fixes the issue. I haven't checked our lit tests yet to see what effect this has and if we can commit it.<div><font color="#000000"><br></font></div><div>
<p class="gmail-m_-566175991907960284gmail-p1" style="margin:0px;font-variant-numeric:normal;font-variant-east-asian:normal;font-stretch:normal;font-size:11px;line-height:normal;font-family:Menlo"><span class="gmail-m_-566175991907960284gmail-s1" style="font-variant-ligatures:no-common-ligatures;background-color:rgb(255,255,255)"><font color="#000000">lib/CodeGen/SelectionDAG/DAGCombiner.cpp</font></span></p>
<p class="gmail-m_-566175991907960284gmail-p1" style="margin:0px;font-variant-numeric:normal;font-variant-east-asian:normal;font-stretch:normal;font-size:11px;line-height:normal;font-family:Menlo"><font style="background-color:rgb(255,255,255)" color="#000000"><span class="gmail-m_-566175991907960284gmail-s2" style="font-variant-ligatures:no-common-ligatures">@@ -2967,7 +2967,8 @@</span><span class="gmail-m_-566175991907960284gmail-s1" style="font-variant-ligatures:no-common-ligatures"> SDValue DAGCombiner::visitADDCARRYLike(SDValue N0, SDValue N1, SDValue CarryIn,</span></font></p>
<p class="gmail-m_-566175991907960284gmail-p1" style="margin:0px;font-variant-numeric:normal;font-variant-east-asian:normal;font-stretch:normal;font-size:11px;line-height:normal;font-family:Menlo"><span class="gmail-m_-566175991907960284gmail-s1" style="font-variant-ligatures:no-common-ligatures;background-color:rgb(255,255,255)"><font color="#000000"><span class="gmail-m_-566175991907960284gmail-Apple-converted-space"> </span>// Iff the flag result is dead:</font></span></p>
<p class="gmail-m_-566175991907960284gmail-p1" style="margin:0px;font-variant-numeric:normal;font-variant-east-asian:normal;font-stretch:normal;font-size:11px;line-height:normal;font-family:Menlo"><span class="gmail-m_-566175991907960284gmail-s1" style="font-variant-ligatures:no-common-ligatures;background-color:rgb(255,255,255)"><font color="#000000"><span class="gmail-m_-566175991907960284gmail-Apple-converted-space"> </span>// (addcarry (add|uaddo X, Y), 0, Carry) -> (addcarry X, Y, Carry)</font></span></p>
<p class="gmail-m_-566175991907960284gmail-p1" style="margin:0px;font-variant-numeric:normal;font-variant-east-asian:normal;font-stretch:normal;font-size:11px;line-height:normal;font-family:Menlo"><span class="gmail-m_-566175991907960284gmail-s1" style="font-variant-ligatures:no-common-ligatures;background-color:rgb(255,255,255)"><font color="#000000"><span class="gmail-m_-566175991907960284gmail-Apple-converted-space"> </span>if ((N0.getOpcode() == ISD::ADD ||</font></span></p>
<p class="gmail-m_-566175991907960284gmail-p2" style="margin:0px;font-variant-numeric:normal;font-variant-east-asian:normal;font-stretch:normal;font-size:11px;line-height:normal;font-family:Menlo"><span class="gmail-m_-566175991907960284gmail-s1" style="font-variant-ligatures:no-common-ligatures;background-color:rgb(255,255,255)"><font color="#000000">- <span class="gmail-m_-566175991907960284gmail-Apple-converted-space"> </span>(N0.getOpcode() == ISD::UADDO && N0.getResNo() == 0)) &&</font></span></p>
<p class="gmail-m_-566175991907960284gmail-p3" style="margin:0px;font-variant-numeric:normal;font-variant-east-asian:normal;font-stretch:normal;font-size:11px;line-height:normal;font-family:Menlo"><span class="gmail-m_-566175991907960284gmail-s1" style="font-variant-ligatures:no-common-ligatures;background-color:rgb(255,255,255)"><font color="#000000">+ <span class="gmail-m_-566175991907960284gmail-Apple-converted-space"> </span>(N0.getOpcode() == ISD::UADDO && N0.getResNo() == 0 &&</font></span></p>
<p class="gmail-m_-566175991907960284gmail-p3" style="margin:0px;font-variant-numeric:normal;font-variant-east-asian:normal;font-stretch:normal;font-size:11px;line-height:normal;font-family:Menlo"><span class="gmail-m_-566175991907960284gmail-s1" style="font-variant-ligatures:no-common-ligatures;background-color:rgb(255,255,255)"><font color="#000000">+<span class="gmail-m_-566175991907960284gmail-Apple-converted-space"> </span>N0.getValue(1) != CarryIn)) &&</font></span></p>
<p class="gmail-m_-566175991907960284gmail-p1" style="margin:0px;font-variant-numeric:normal;font-variant-east-asian:normal;font-stretch:normal;font-size:11px;line-height:normal;font-family:Menlo"><span class="gmail-m_-566175991907960284gmail-s1" style="font-variant-ligatures:no-common-ligatures;background-color:rgb(255,255,255)"><font color="#000000"><span class="gmail-m_-566175991907960284gmail-Apple-converted-space"> </span>isNullConstant(N1) && !N->hasAnyUseOfValue(1))</font></span></p>
<p class="gmail-m_-566175991907960284gmail-p1" style="margin:0px;font-variant-numeric:normal;font-variant-east-asian:normal;font-stretch:normal;font-size:11px;line-height:normal;font-family:Menlo"><span class="gmail-m_-566175991907960284gmail-s1" style="font-variant-ligatures:no-common-ligatures;background-color:rgb(255,255,255)"><font color="#000000"><span class="gmail-m_-566175991907960284gmail-Apple-converted-space"> </span>return DAG.getNode(ISD::ADDCARRY, SDLoc(N), N->getVTList(),</font></span></p>
<p class="gmail-m_-566175991907960284gmail-p1" style="margin:0px;font-variant-numeric:normal;font-variant-east-asian:normal;font-stretch:normal;font-size:11px;line-height:normal;font-family:Menlo"><span class="gmail-m_-566175991907960284gmail-s1" style="font-variant-ligatures:no-common-ligatures;background-color:rgb(255,255,255)"><font color="#000000"><span class="gmail-m_-566175991907960284gmail-Apple-converted-space"> </span>N0.getOperand(0), N0.getOperand(1), CarryIn);</font></span></p></div><div><br clear="all"><div><div dir="ltr" class="gmail-m_-566175991907960284gmail_signature">~Craig</div></div><br></div></div><br><div class="gmail_quote"><div dir="ltr" class="gmail_attr">On Wed, Jul 3, 2019 at 9:40 AM Marc <<a href="mailto:mh@mh-sec.de" target="_blank">mh@mh-sec.de</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">Hi Craig,<br>
<br>
On 03.07.19 17:33, Craig Topper wrote:<br>
> Don't the CreateICmp calls return a Value* with an i1 type? But then<br>
> they are added to an i8 type? Not sure that works. <br>
<br>
I had that initially:<br>
auto cf = IRB.CreateICmpULT(Incr, ConstantInt::get(Int8Ty, 1));<br>
auto carry = IRB.CreateZExt(cf, Int8Ty);<br>
Incr = IRB.CreateAdd(Incr, carry);<br>
it makes no difference to the generated assembly<br>
<br>
<br>
> Have you tried using the llvm.uadd.with.overflow.i8 intrinsic?<br>
<br>
we have tried this:<br>
<br>
CallInst *AddOv =<br>
IRB.CreateBinaryIntrinsic(Intrinsic::uadd_with_overflow, Counter,<br>
ConstantInt::get(Int8Ty, 1));<br>
AddOv->setMetadata(M.getMDKindID("nosanitize"), MDNode::get(C, None));<br>
Value *SumWithOverflowBit = AddOv;<br>
Incr = IRB.CreateAdd(IRB.CreateExtractValue(SumWithOverflowBit, 0),<br>
IRB.CreateZExt(IRB.CreateExtractValue(SumWithOverflowBit, 1), Int8Ty));<br>
<br>
but that generated exactly the same as<br>
<br>
auto cf = IRB.CreateICmpULT(Incr, ConstantInt::get(Int8Ty, 1));<br>
Incr = IRB.CreateAdd(Incr, cf);<br>
<br>
<br>
All the above create (with llvm 6.0, 7 and 8):<br>
<br>
mov dl,BYTE PTR [rsi+rdi*1]<br>
mov ecx,edx // <- not needed<br>
add cl,0x1 // <- should be done to dl instead<br>
adc dl,0x1<br>
mov BYTE PTR [rsi+rdi*1],dl<br>
<br>
<br>
Thanks!<br>
<br>
Regards,<br>
Marc<br>
<br>
> <br>
> ~Craig<br>
> <br>
> <br>
> On Wed, Jul 3, 2019 at 4:01 AM Marc via llvm-dev<br>
> <<a href="mailto:llvm-dev@lists.llvm.org" target="_blank">llvm-dev@lists.llvm.org</a> <mailto:<a href="mailto:llvm-dev@lists.llvm.org" target="_blank">llvm-dev@lists.llvm.org</a>>> wrote:<br>
> <br>
> Hello,<br>
> <br>
> I have an optimisation issue in an llvm IR pass - the issue being that<br>
> unnecessary instructions are generated in the final assembly (with -O3).<br>
> <br>
> I want to create the following assembly snippet:<br>
> <br>
> mov dl,BYTE PTR [rsi+rdi*1]<br>
> add dl,0x1<br>
> adc dl,0x0<br>
> mov BYTE PTR [rsi+rdi*1],dl<br>
> <br>
> however what is created is (variant #1):<br>
> <br>
> mov dl,BYTE PTR [rsi+rdx*1]<br>
> add dl,0x1<br>
> cmp dl,0x1 // <- not needed<br>
> adc dl,0x0<br>
> mov BYTE PTR [rsi+rdi*1],dl<br>
> <br>
> in variant #2 the following is created:<br>
> <br>
> mov dl,BYTE PTR [rsi+rdi*1]<br>
> mov ecx,edx // <- not needed<br>
> add cl,0x1 // <- should be done to dl instead<br>
> adc dl,0x1<br>
> mov BYTE PTR [rsi+rdi*1],dl<br>
> <br>
> Far below are both variants with the full code around it, however the<br>
> difference in both variants is this:<br>
> <br>
> //variant1<br>
> auto cf = IRB.CreateICmpEQ(Incr, ConstantInt::get(Int8Ty, 0));<br>
> Incr = IRB.CreateAdd(Incr, cf);<br>
> <br>
> //variant2<br>
> auto cf = IRB.CreateICmpULT(Incr, ConstantInt::get(Int8Ty, 1));<br>
> Incr = IRB.CreateAdd(Incr, cf);<br>
> <br>
> //interestingly this totally different approach creates the same<br>
> instructions as variant2<br>
> CallInst *AddOv = IRB.CreateBinaryIntrinsic(Intrinsic::uadd_with_over<br>
> flow, Counter, ConstantInt::get(Int8Ty, 1));<br>
> AddOv->setMetadata(M.getMDKindID("nosanitize"), MDNode::get(C, None));<br>
> Value *SumWithOverflowBit = AddOv;<br>
> Incr = IRB.CreateAdd(IRB.CreateExtractValue(SumWithOverflowBit, 0),<br>
> IRB.CreateZExt(IRB.CreateExtractValue(SumWithOverflowBit, 1), Int8Ty));<br>
> <br>
> So - How do I have to write the code that the target code has a chance<br>
> of being generated?<br>
> For me its the same result on LLVM 6.0 and 7.<br>
> <br>
> Alternatively<br>
> add BYTE PTR [rsi+rdi*1],0x1<br>
> adc BYTE PTR [rsi+rdi*1],0x0<br>
> would work as well.<br>
> <br>
> Thank you very much!<br>
> <br>
> Regards,<br>
> Marc<br>
> <br>
> -> Below now is the full llvm IR pass code<br>
> <br>
> // vvv same code before both variants<br>
> LoadInst *PrevLoc = IRB.CreateLoad(AFLPrevLoc);<br>
> PrevLoc->setMetadata(M.getMDKindID("nosanitize"), MDNode::get(C, None));<br>
> Value *PrevLocCasted = IRB.CreateZExt(PrevLoc, IRB.getInt32Ty());<br>
> <br>
> LoadInst *MapPtr = IRB.CreateLoad(AFLMapPtr);<br>
> MapPtr->setMetadata(M.getMDKindID("nosanitize"), MDNode::get(C, None));<br>
> Value *MapPtrIdx = IRB.CreateGEP(MapPtr, IRB.CreateXor(PrevLocCasted,<br>
> CurLoc));<br>
> <br>
> LoadInst *Counter = IRB.CreateLoad(MapPtrIdx);<br>
> Counter->setMetadata(M.getMDKindID("nosanitize"), MDNode::get(C, None));<br>
> <br>
> Value *Incr = IRB.CreateAdd(Counter, ConstantInt::get(Int8Ty, 1));<br>
> // ^^^ same code before both variants<br>
> <br>
> // CODE FOR VARIANT #1<br>
> auto cf = IRB.CreateICmpEQ(Incr, ConstantInt::get(Int8Ty, 0));<br>
> Incr = IRB.CreateAdd(Incr, cf);<br>
> <br>
> // CODE FOR VARIANT #2<br>
> auto cf = IRB.CreateICmpULT(Incr, ConstantInt::get(Int8Ty, 1));<br>
> Incr = IRB.CreateAdd(Incr, cf);<br>
> <br>
> // vvv same code after both variants<br>
> IRB.CreateStore(Incr,<br>
> MapPtrIdx)->setMetadata(M.getMDKindID("nosanitize"), MDNode::get(C,<br>
> None));<br>
> StoreInst *Store = IRB.CreateStore(ConstantInt::get(Int32Ty, cur_loc >><br>
> 1), AFLPrevLoc);<br>
> Store->setMetadata(M.getMDKindID("nosanitize"), MDNode::get(C, None));<br>
> // ^^^ same code after both variants<br>
> <br>
> <br>
> -- <br>
> Marc Heuse<br>
> <a href="http://www.mh-sec.de" rel="noreferrer" target="_blank">www.mh-sec.de</a> <<a href="http://www.mh-sec.de" rel="noreferrer" target="_blank">http://www.mh-sec.de</a>><br>
> <br>
> PGP: AF3D 1D4C D810 F0BB 977D 3807 C7EE D0A0 6BE9 F573<br>
> _______________________________________________<br>
> LLVM Developers mailing list<br>
> <a href="mailto:llvm-dev@lists.llvm.org" target="_blank">llvm-dev@lists.llvm.org</a> <mailto:<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>
> <br>
<br>
-- <br>
Marc Heuse<br>
Mobil: +49 177 9611560<br>
Fax: +49 30 37309726<br>
<a href="http://www.mh-sec.de" rel="noreferrer" target="_blank">www.mh-sec.de</a><br>
<br>
Marc Heuse - IT-Security Consulting<br>
Winsstr. 68<br>
10405 Berlin<br>
<br>
Ust.-Ident.-Nr.: DE244222388<br>
PGP: AF3D 1D4C D810 F0BB 977D 3807 C7EE D0A0 6BE9 F573<br>
</blockquote></div>
</blockquote></div>