# [EXTERNAL] Re: [PATCH] tree-optimization/98956 Optimizing out boolean left shift

Andrew Pinski pinskia@gmail.com
Tue Nov 30 23:18:55 GMT 2021

```On Tue, Nov 30, 2021 at 3:08 PM Navid Rahimi <navidrahimi@microsoft.com> wrote:
>
> Hi Andrew,
>
> Thanks for your detailed comment. There are two problem I wanted to discuss with you about:
>
> a) The optimization I have sent patch, does optimize variable length "<<" too(for example B0 << x, where x is variable). This [1] link shows the actual optimization and a link for the proof is included in the editor.
>
> b) I am unable to prove the optimization you are describing for non-constant length shift. You can take a look at the code example [2] and proof [3]. I am getting "Transformation doesn't verify!" when I do implement the optimization you mentioned for non-constant shift.
>
> The optimization you are describing only works for "(take: (t << 1) != 0) -> ((t & 0x7fffffff) != 0)" which only is provable and works for INTEGER_CST.

No it works with non constants too:
t << y != 0 -> t & (-1u>>y) != 0

When y == 0, you have t != 0.
Which is exactly what you think it should be.
Which can be further reduced to t != 0 as y >= sizeof(t)*BITS_PER_UNIT
is undefined.

Thanks,
Andrew Pinski

>
> My understanding might be incorrect here, please don't hesitate to correct me.
>
> 1) https://compiler-explorer.com/z/r46znh4Tj
> 2) https://compiler-explorer.com/z/K1so39dbK
> 3) https://alive2.llvm.org/ce/z/-54zZv
>
> Best wishes,
> Navid.
>
> ________________________________________
> From: Andrew Pinski <pinskia@gmail.com>
> Sent: Tuesday, November 30, 2021 14:03
> To: Navid Rahimi
> Cc: Navid Rahimi via Gcc-patches
> Subject: [EXTERNAL] Re: [PATCH] tree-optimization/98956 Optimizing out boolean left shift
>
> On Tue, Nov 30, 2021 at 8:35 AM Navid Rahimi via Gcc-patches
> <gcc-patches@gcc.gnu.org> wrote:
> >
> > Hi GCC community,
> >
> > This patch will add the missed pattern described in bug 98956 [1] to the match.pd. The codegen and correctness proof for this pattern is here [2,3] in case anyone is curious. Tested on x86_64 Linux.
> >
>
> A better way to optimize this is the following (which I describe in PR 64992):
>  take: (t << 1) != 0;
>
> This should be transformed into:
> (t & 0x7fffffff) != 0
>
> The rest will just fall out really.  That is there is no reason to
> special case bool here.
> I have most of the patch except for creating the mask part which
> should be simple, I just did not want to look up the wi:: functions at
> the time I was writing it into the bug report.
>
> Thanks,
> Andrew Pinski
>
>
>
> > Tree-optimization/98956:
> >
> > Adding new optimization to match.pd:
> >                 * match.pd ((B0 << x) cmp 0) -> B0 cmp 0 : New optimization.
> >                 * gcc.dg/tree-ssa/pr98956.c: testcase for this optimization.
> >                 * gcc.dg/tree-ssa/pr98956-2.c: testcase for node with side-effect.
> >