<html><head><meta http-equiv="Content-Type" content="text/html; charset=utf-8"></head><body style="word-wrap: break-word; -webkit-nbsp-mode: space; line-break: after-white-space;" class="">Hi, <div class=""><br class=""></div><div class="">I think this should be optimized as expected on latest trunk: <a href="https://godbolt.org/z/vW7K7f" class="">https://godbolt.org/z/vW7K7f</a><div class=""><br class=""></div><div class="">Cheers<br class=""><div class=""><div><br class=""><blockquote type="cite" class=""><div class="">On Apr 6, 2020, at 16:53, Stefanos Baziotis <<a href="mailto:stefanos.baziotis@gmail.com" class="">stefanos.baziotis@gmail.com</a>> wrote:</div><br class="Apple-interchange-newline"><div class=""><div dir="ltr" class="">Hi,<br class=""><br class="">> But the value can't be [0,7] due to the earlier branch. When I said it was guaranteed to wrap, I only meant for the range of values that were possible after the first branch.<br class="">Indeed, for some reason I remembered that the left check is >= 0 when I wrote this.<br class=""><br class="">Thanks a lot for the breakdown in CorrelatedValuePropagation. I had no idea about this pass.<br class=""><br class="">> It was able to see that the input to add was in the range [8,14) in the call to LVI->getConstantRange in processBinOp.<br class=""><br class="">I could not reproduce that. I get:<br class="">BinOp: %4 = add nsw i32 %2, -8<br class="">LRange: [0,-2147483648)<br class="">RRange: [-8,-7)<br class=""><br class="">> processCmp skips calling LVI for the select's icmp because the input isn't in the same basic block and isn't a phi.<br class="">Do you maybe mean: _is_ in the same BB (and isn't a PHI).<br class=""><br class="">By the way, I don't get the reasoning in the comment above:<br class="">// As a policy choice, we choose not to waste compile time on anything where<br class="">// the comparison is testing local values.<br class=""><br class="">> I think this is because the code executed for getConstant doesn't handle icmp even when it can prove the input is in a constant range.<br class=""><br class="">Maybe we ended up on the same thing. I'm not sure I followed that correctly but getValueFromICmpCondition() should have been able to handle that.<br class=""><br class="">Best,<br class="">Stefanos<br class=""><br class=""></div><br class=""><div class="gmail_quote"><div dir="ltr" class="gmail_attr">Στις Δευ, 6 Απρ 2020 στις 5:22 π.μ., ο/η Craig Topper <<a href="mailto:craig.topper@gmail.com" class="">craig.topper@gmail.com</a>> έγραψε:<br class=""></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" class=""><div dir="ltr" class="">On Sun, Apr 5, 2020 at 6:34 PM Stefanos Baziotis <<a href="mailto:stefanos.baziotis@gmail.com" target="_blank" class="">stefanos.baziotis@gmail.com</a>> wrote:<br class=""></div><div class="gmail_quote"><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" class="">Hi Craig,<br class=""><br class="">> Adding a nuw to the add -8 is incorrect.<br class="">Yeah, I didn't mean to say it was correct. It was just an observation that with nuw the optimization was happened and I asked if someone thought it was somehow connected.<br class=""><br class="">> From the perspective of the unsigned math, -8 is treated a very large positive number. The input to the add is [8,13) and adding a large positive number to it wraps around past 0. So that is guaranteed unsigned wrap<br class="">I understand yes, but I don't think it is guaranteed. Unless I miss something, for values in [0, 7] it won't wrap. But past that and up to (and including in the original source code) 13, it will wrap yes.<br class=""></div></blockquote><div class=""><br class=""></div><div class="">But the value can't be [0,7] due to the earlier branch. When I said it was guaranteed to wrap, I only meant for the range of values that were possible after the first branch.</div><div class=""> </div><div class="">In theory, the CorrelatedValuePropagation pass should have been able to optimize the select. It was able to see that the input to add was in the range [8,14) in the call to LVI->getConstantRange in processBinOp. processCmp skips calling LVI for the select's icmp because the input isn't in the same basic block and isn't a phi. And the call to LVI->getConstant for the select in processSelect didn't return a constant. I think this is because the code executed for getConstant doesn't handle icmp even when it can prove the input is in a constant range. I tried removing the local value check in processCmp so that getPredicateAt would called, but that didn't help either.</div><div class=""><br class=""></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" class=""><br class="">Best,<br class="">- Stefanos<br class=""><br class=""></div><br class=""><div class="gmail_quote"><div dir="ltr" class="gmail_attr">Στις Δευ, 6 Απρ 2020 στις 3:10 π.μ., ο/η Craig Topper <<a href="mailto:craig.topper@gmail.com" target="_blank" class="">craig.topper@gmail.com</a>> έγραψε:<br class=""></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" class="">Adding a nuw to the add -8 is incorrect. From the perspective of the unsigned math, -8 is treated a very large positive number. The input to the add is [8,13) and adding a large positive number to it wraps around past 0. So that is guaranteed unsigned wrap. On the other hand, a sub nuw 8 would be correct.<div class=""><br clear="all" class=""><div class=""><div dir="ltr" class="">~Craig</div></div><br class=""></div></div><br class=""><div class="gmail_quote"><div dir="ltr" class="gmail_attr">On Sun, Apr 5, 2020 at 3:27 PM Stefanos Baziotis via llvm-dev <<a href="mailto:llvm-dev@lists.llvm.org" target="_blank" class="">llvm-dev@lists.llvm.org</a>> wrote:<br class=""></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" class="">Thanks, I didn't know that! Indeed, it's instruction combine that does the job.<br class=""><br class="">- Stefanos</div><br class=""><div class="gmail_quote"><div dir="ltr" class="gmail_attr">Στις Δευ, 6 Απρ 2020 στις 12:38 π.μ., ο/η Florian Hahn <<a href="mailto:florian_hahn@apple.com" target="_blank" class="">florian_hahn@apple.com</a>> έγραψε:<br class=""></div><blockquote class="gmail_quote" style="margin:0px 0px 0px 0.8ex;border-left:1px solid rgb(204,204,204);padding-left:1ex"><br class="">
<br class="">
> On Apr 5, 2020, at 22:20, Stefanos Baziotis <<a href="mailto:stefanos.baziotis@gmail.com" target="_blank" class="">stefanos.baziotis@gmail.com</a>> wrote:<br class="">
> <br class="">
> > Any idea about how the compiler could remove the lshr and use a add -16?<br class="">
> Actually, I just figured that doing this test is like solving this:<br class="">
> <br class="">
> 8 <= x/2 <= 13<br class="">
> 16 <= x <= 26<br class="">
> 0 <= x - 16 <= 10 => 0 <= x < 11<br class="">
> The left part is know since it's unsigned<br class="">
> The right part could be done x <= 11 => x < 12 because it's actually an integer division.<br class="">
> Wow... I would be really happy to know what pass does that.<br class="">
<br class="">
I’d guess a combination of instcombine rules together with some other transforms. You could probably use `-print-after-all` (`clang -mllvm -print-after-all` if you are using clang) to track down the relevant passes/steps.</blockquote></div>
_______________________________________________<br class="">
LLVM Developers mailing list<br class="">
<a href="mailto:llvm-dev@lists.llvm.org" target="_blank" class="">llvm-dev@lists.llvm.org</a><br class="">
<a href="https://lists.llvm.org/cgi-bin/mailman/listinfo/llvm-dev" rel="noreferrer" target="_blank" class="">https://lists.llvm.org/cgi-bin/mailman/listinfo/llvm-dev</a><br class="">
</blockquote></div>
</blockquote></div>
</blockquote></div></div>
</blockquote></div>
</div></blockquote></div><br class=""></div></div></div></body></html>