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

[Stefanos Baziotis via llvm-dev]

Hi John,

I hadn't seen alive2, amazing program, thank you! Keep up the good work.

> I'm not sure that I've captured what you mean here

To be more specific for everyone:
- First of all, I hope it's clear that in the original (C) code, the region
- 0x8 > 1000 branch should
be eliminated. That is because it is inside a block that has ensured that 8
< region < 12. But for some reason,
it is not eliminated. I'm trying to find that reason. :)
- I understand that in the -O2 .ll output, we take %0 and do it a right
shift. That means that we don't have
any range info about %0 or %0 >>= 1, so we can't eliminate the branch. What
I don't understand
is why we chose to reuse %0 and do it a right shift and instead we didn't
have a phi there.
- Finally, I saw that putting nuw in the addition with -8 eliminates the
branch. This makes sense since,
we know probably know from the code above that %0 >>= 1 is less than 12.
Although, I don't understand
why the right shift was translated to an add with -16.

I hope this made some sense. You may ignore the last 2 and focus on the
first, i.e. what optimization
should have been done but it's not and what we can do about it.

A clearer version of the .ll: https://godbolt.org/z/2t4RU5

Best,
Stefanos

p.s. John I had sent you an e-mail regarding loop rotation some time ago.
I'm not sure if it was intentional
on your part to be skipped, if so, sorry to bother you. :) But there's the
alternative that it was just lost.

Στις Κυρ, 5 Απρ 2020 στις 7:12 π.μ., ο/η John Regehr via llvm-dev <
llvm-dev at lists.llvm.org> έγραψε:

> I'm not sure that I've captured what you mean here, but you can explore
> these sorts of things using Alive2:
>
>    http://volta.cs.utah.edu:8080/z/b7Yj7j
>
> John
>
>
>
> On 4/4/20 6:29 PM, Stefanos Baziotis via llvm-dev wrote:
> > Hi everyone,
> >
> > In a twitch chat someone redirected me to an example that is not
> > optimized: https://godbolt.org/z/BL-4jL
> >
> > I included the original source code and this is after -O2. We both
> > thought that the -8 branch could be optimized out. I added a nuw in the
> > subtraction and it actually does it.
> >
> > Any thoughts on why that doesn't happen already?
> >
> > Best,
> > Stefanos Baziotis
> >
> > _______________________________________________
> > LLVM Developers mailing list
> > llvm-dev at lists.llvm.org
> > https://lists.llvm.org/cgi-bin/mailman/listinfo/llvm-dev
> >
> _______________________________________________
> 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/890eb693/attachment-0001.html>