llvm dev - Apr 2020 - Branch is not optimized because of right shift

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
-------------- next part --------------
An HTML attachment was scrubbed...
URL:
<http://lists.llvm.org/pipermail/llvm-dev/attachments/20200405/f5b27e28/attachment.html>

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
>

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>