[llvm-dev] Branch is not optimized because of right shift

[Craig Topper via llvm-dev]

On Sun, Apr 5, 2020 at 6:34 PM Stefanos Baziotis <
stefanos.baziotis at gmail.com> wrote:

> Hi Craig,
>
> > Adding a nuw to the add -8 is incorrect.
> 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.
>
> > 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
> 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.
>

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.

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.


> Best,
> - Stefanos
>
>
> Στις Δευ, 6 Απρ 2020 στις 3:10 π.μ., ο/η Craig Topper <
> craig.topper at gmail.com> έγραψε:
>
>> 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.
>>
>> ~Craig
>>
>>
>> On Sun, Apr 5, 2020 at 3:27 PM Stefanos Baziotis via llvm-dev <
>> llvm-dev at lists.llvm.org> wrote:
>>
>>> Thanks, I didn't know that! Indeed, it's instruction combine that does
>>> the job.
>>>
>>> - Stefanos
>>>
>>> Στις Δευ, 6 Απρ 2020 στις 12:38 π.μ., ο/η Florian Hahn <
>>> florian_hahn at apple.com> έγραψε:
>>>
>>>>
>>>>
>>>> > On Apr 5, 2020, at 22:20, Stefanos Baziotis <
>>>> stefanos.baziotis at gmail.com> wrote:
>>>> >
>>>> > > Any idea about how the compiler could remove the lshr and use a add
>>>> -16?
>>>> > Actually, I just figured that doing this test is like solving this:
>>>> >
>>>> > 8 <= x/2 <= 13
>>>> > 16 <= x <= 26
>>>> > 0 <= x - 16 <= 10 => 0 <= x < 11
>>>> > The left part is know since it's unsigned
>>>> > The right part could be done x <= 11 => x < 12 because it's actually
>>>> an integer division.
>>>> > Wow... I would be really happy to know what pass does that.
>>>>
>>>> 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.
>>>
>>> _______________________________________________
>>> LLVM Developers mailing list
>>> llvm-dev at lists.llvm.org
>>> https://lists.llvm.org/cgi-bin/mailman/listinfo/llvm-dev
>>>
>>
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://lists.llvm.org/pipermail/llvm-dev/attachments/20200405/df366aa8/attachment-0001.html>