<div dir="ltr"><br><div class="gmail_extra"><br><div class="gmail_quote">On Mon, Apr 6, 2015 at 12:59 AM, Sanjoy Das <span dir="ltr"><<a href="mailto:sanjoy@playingwithpointers.com" target="_blank">sanjoy@playingwithpointers.com</a>></span> wrote:<br><blockquote class="gmail_quote" style="margin:0px 0px 0px 0.8ex;border-left-width:1px;border-left-color:rgb(204,204,204);border-left-style:solid;padding-left:1ex">The LangRef says this for left shifts:<br>
<br>
"If the nsw keyword is present, then the shift produces a poison value<br>
if it shifts out any bits that disagree with the resultant sign bit."<br>
... (1)<br>
<br>
followed by<br>
<br>
"As such, NUW/NSW have the same semantics as they would if the shift<br>
were expressed as a mul instruction with the same nsw/nuw bits in (mul<br>
%op1, (shl 1, %op2))." ... (2)<br>
<br>
But by (1) "shl i8 1, i8 7" sign overflows (since it shifts out only<br>
zeros, but the result has the sign bit set) but "mul i8 1, i8 -128"<br>
does not sign overflow (by the usual definition of sign-overflow), so<br>
this violates (2).<br>
<br>
InstCombine already has a check for this edge-case when folding<br>
multiplies into left shifts:<br>
<br>
...<br>
if (I.hasNoUnsignedWrap())<br>
Shl->setHasNoUnsignedWrap();<br>
if (I.hasNoSignedWrap() && *** NewCst->isNotMinSignedValue() ***)<br>
Shl->setHasNoSignedWrap();<br>
...<br>
<br>
(though the check is a bit weird -- NewCst is Log2(IVal) so I think it<br>
cannot ever be INT_MIN, and I suspect that the check is supposed to be<br>
"IVal->isNotMinSignedValue()" or equivalent.)<br></blockquote><div><br></div><div>Yes, it looks like that check is a bit off. I think this does the trick though:</div><div><div>diff --git a/lib/Transforms/InstCombine/InstCombineMulDivRem.cpp b/lib/Transforms/InstCombine/InstCombineMulDivRem.cpp</div><div>index 35513f1..a554e9f 100644</div><div>--- a/lib/Transforms/InstCombine/InstCombineMulDivRem.cpp</div><div>+++ b/lib/Transforms/InstCombine/InstCombineMulDivRem.cpp</div><div>@@ -217,12 +217,16 @@ Instruction *InstCombiner::visitMul(BinaryOperator &I) {</div><div> NewCst = getLogBase2Vector(CV);</div><div> </div><div> if (NewCst) {</div><div>+ unsigned Width = NewCst->getType()->getPrimitiveSizeInBits();</div><div> BinaryOperator *Shl = BinaryOperator::CreateShl(NewOp, NewCst);</div><div> </div><div> if (I.hasNoUnsignedWrap())</div><div> Shl->setHasNoUnsignedWrap();</div><div>- if (I.hasNoSignedWrap() && NewCst->isNotMinSignedValue())</div><div>- Shl->setHasNoSignedWrap();</div><div>+ if (I.hasNoSignedWrap()) {</div><div>+ uint64_t V;</div><div>+ if (match(NewCst, m_ConstantInt(V)) && V != Width - 1)</div><div>+ Shl->setHasNoSignedWrap();</div><div>+ }</div><div> </div><div> return Shl;</div><div> }</div></div><div><br></div><blockquote class="gmail_quote" style="margin:0px 0px 0px 0.8ex;border-left-width:1px;border-left-color:rgb(204,204,204);border-left-style:solid;padding-left:1ex">
<br>
Should one of the two clauses be removed from the LangRef? I'd prefer<br>
keeping (2) and removing (1) unless it inhibits some important<br>
optimization, solely because (2) is easier to reason in.</blockquote><div><br></div><div>C11 seems to say that "1 << 31" results in overflow but C++11 disagrees because it only requires the result to be representable in the corresponding *unsigned* type of the result type. Annoying.</div><div><br></div><div>If I had to guess, the intent of (1) was to make "1 << 31" UB.<br></div><div><br></div><div>I'm of the opinion that the C++11 rules are more sane, "1 << 31" should not result in overflow just like "1 * INT_MIN" doesn't. We should try to switch to (2).</div><div><br></div><div>I wouldn't be surprised if InstSimplify were relying on (1) to implement some of its optimizations: <a href="http://llvm.org/viewvc/llvm-project/llvm/trunk/lib/Analysis/InstructionSimplify.cpp?revision=233938&view=markup#l2298">http://llvm.org/viewvc/llvm-project/llvm/trunk/lib/Analysis/InstructionSimplify.cpp?revision=233938&view=markup#l2298</a></div><div> <br></div><blockquote class="gmail_quote" style="margin:0px 0px 0px 0.8ex;border-left-width:1px;border-left-color:rgb(204,204,204);border-left-style:solid;padding-left:1ex">
<br>
Note1: neither clause is stronger than the other -- "shl i8 -1, 7"<br>
sign-overflows by (2) but not by (1).<br></blockquote><div><br></div><div>Both C and C++ would say that this is UB. Again, (2) sounds better.</div><div><br></div><blockquote class="gmail_quote" style="margin:0px 0px 0px 0.8ex;border-left-width:1px;border-left-color:rgb(204,204,204);border-left-style:solid;padding-left:1ex">
<br>
Note2: there may be similar issues with nuw; I have not investigated that yet.<br></blockquote><div><br></div><div>FWIW, I don't see any issues with the nuw side.</div><div><br></div><blockquote class="gmail_quote" style="margin:0px 0px 0px 0.8ex;border-left-width:1px;border-left-color:rgb(204,204,204);border-left-style:solid;padding-left:1ex">
<br>
-- Sanjoy<br>
_______________________________________________<br>
LLVM Developers mailing list<br>
<a href="mailto:LLVMdev@cs.uiuc.edu">LLVMdev@cs.uiuc.edu</a> <a href="http://llvm.cs.uiuc.edu" target="_blank">http://llvm.cs.uiuc.edu</a><br>
<a href="http://lists.cs.uiuc.edu/mailman/listinfo/llvmdev" target="_blank">http://lists.cs.uiuc.edu/mailman/listinfo/llvmdev</a><br>
</blockquote></div><br></div></div>