[Bug tree-optimization/102546] New: Missed Dead Code Elimination regression (trunk vs 11.2.0) at -O3

[Bug tree-optimization/102546] New: Missed Dead Code Elimination regression (trunk vs 11.2.0) at -O3

[theodort at inf dot ethz.ch]

https://gcc.gnu.org/bugzilla/show_bug.cgi?id=102546

            Bug ID: 102546
           Summary: Missed Dead Code Elimination regression (trunk vs
                    11.2.0) at -O3
           Product: gcc
           Version: 12.0
            Status: UNCONFIRMED
          Severity: normal
          Priority: P3
         Component: tree-optimization
          Assignee: unassigned at gcc dot gnu.org
          Reporter: theodort at inf dot ethz.ch
  Target Milestone: ---

cat missed_case.c
static int a;
static char b, c, d;
void bar(void);
void foo(void);

int main() {
    int f = 0;
    for (; f <= 5; f++) {
        bar();
        b = b && f;
        d = f << f;
        if (!(a >= d || f))
            foo();
        c = 1;
        for (; c; c = 0)
            ;
    }
}


11.2.0 at -O3 can eliminate the call to foo but trunk at -O3 cannot:

gcc-trunk -v
Using built-in specs.
Target: x86_64-pc-linux-gnu
Configured with: ../configure --disable-multilib --disable-bootstrap
--enable-languages=c,c++ 
Thread model: posix
Supported LTO compression algorithms: zlib zstd
gcc version 12.0.0 20210930 (experimental) (GCC)

gcc-trunk -O3 -S missed_case.c

main:
.LFB0:
        .cfi_startproc
        pushq   %rbx
        .cfi_def_cfa_offset 16
        .cfi_offset 3, -16
        xorl    %ebx, %ebx
.L6:
        call    bar
        cmpb    $0, b(%rip)
        je      .L2
        testl   %ebx, %ebx
        jne     .L5
        movb    $0, b(%rip)
        movl    $1, %ebx
        movb    $0, c(%rip)
        call    bar
        cmpb    $0, b(%rip)
        je      .L4
.L5:
        movb    $1, b(%rip)
.L4:
        addl    $1, %ebx
        movb    $0, c(%rip)
        cmpl    $6, %ebx
        jne     .L6
        xorl    %eax, %eax
        popq    %rbx
        .cfi_remember_state
        .cfi_def_cfa_offset 8
        ret
        .p2align 4,,10
        .p2align 3
.L2:
        .cfi_restore_state
        movl    %ebx, %eax
        movl    %ebx, %ecx
        sall    %cl, %eax
        testb   %al, %al
        jle     .L4
        testl   %ebx, %ebx
        jne     .L4
        call    foo
        movb    $0, c(%rip)
        movl    $1, %ebx
        call    bar
        cmpb    $0, b(%rip)
        jne     .L5
        jmp     .L2
        .cfi_endproc


gcc-11 -v
Using built-in specs.
Target: x86_64-pc-linux-gnu
Configured with: ../configure --disable-multilib --disable-bootstrap
--enable-languages=c,c++ 
Thread model: posix
Supported LTO compression algorithms: zlib zstd
gcc version 11.2.0 (GCC)

cat missed_case.s

main:
.LFB0:
        .cfi_startproc
        pushq   %rbx
        .cfi_def_cfa_offset 16
        .cfi_offset 3, -16
        movl    $5, %ebx
        call    bar
        movb    $0, b(%rip)
        movb    $0, c(%rip)
        .p2align 4,,10
        .p2align 3
.L2:
        call    bar
        cmpb    $0, b(%rip)
        movb    $0, c(%rip)
        setne   b(%rip)
        subl    $1, %ebx
        jne     .L2
        xorl    %eax, %eax
        popq    %rbx
        .cfi_def_cfa_offset 8
        ret
        .cfi_endproc

[Bug tree-optimization/102546] Missed Dead Code Elimination regression (trunk vs 11.2.0) at -O3

[theodort at inf dot ethz.ch]

https://gcc.gnu.org/bugzilla/show_bug.cgi?id=102546

--- Comment #1 from Theodoros Theodoridis <theodort at inf dot ethz.ch> ---
It bisects to 2e96b5f14e4025691b57d2301d71aa6092ed44bc

[Bug tree-optimization/102546] Missed Dead Code Elimination regression (trunk vs 11.2.0) at -O3

[aldyh at gcc dot gnu.org]

https://gcc.gnu.org/bugzilla/show_bug.cgi?id=102546

Aldy Hernandez <aldyh at gcc dot gnu.org> changed:

           What    |Removed                     |Added
----------------------------------------------------------------------------
                 CC|                            |aldyh at gcc dot gnu.org,
                   |                            |amacleod at redhat dot com

--- Comment #2 from Aldy Hernandez <aldyh at gcc dot gnu.org> ---
By VRP1 we seem to be calculating the following:

(f_8 << f_8) && (f_8 == 0)

This would fold to false, which would elide the foo():

 <bb 7> [local count: 59055800]:
  b = 0;
  _3 = f_8 << f_8;
  _4 = (char) _3;
  _5 = (int) _4;
  if (_4 > 0)
    goto <bb 8>; [64.06%]
  else
    goto <bb 10>; [35.94%]

  <bb 8> [local count: 34842922]:
  if (f_8 == 0)
    goto <bb 9>; [71.10%]
  else
    goto <bb 10>; [28.90%]

  <bb 9> [local count: 12809203]:
  foo ();

So from the outset, it seems like this is a missing relation in range-ops. 
That is if we know f_8 << f_8 is non-zero, then we know f_8 cannot be 0.  This
looks like an easy fix, however...

What I fail to see is how "a" got removed entirely from the IL, making this
scenario possible:

 if (!(a >= d || f))
            foo();

Am I missing something obvious here?

[Bug tree-optimization/102546] Missed Dead Code Elimination regression (trunk vs 11.2.0) at -O3

[aldyh at gcc dot gnu.org]

https://gcc.gnu.org/bugzilla/show_bug.cgi?id=102546

--- Comment #3 from Aldy Hernandez <aldyh at gcc dot gnu.org> ---

> What I fail to see is how "a" got removed entirely from the IL, making this
> scenario possible:
> 
>  if (!(a >= d || f))
>             foo();

What I meant to say is that I don't understand how "a" got removed from the IL
representing this:

 if (!(a >= d || f))
     foo();

Because it's the missing "a" which opens the door for the un-folded expression
here:

    (f_8 << f_8) && (f_8 == 0)

[Bug tree-optimization/102546] [12 Regregression] Missed Dead Code Elimination regression (trunk vs 11.2.0) at -O3

[pinskia at gcc dot gnu.org]

https://gcc.gnu.org/bugzilla/show_bug.cgi?id=102546

Andrew Pinski <pinskia at gcc dot gnu.org> changed:

           What    |Removed                     |Added
----------------------------------------------------------------------------
   Target Milestone|---                         |12.0
            Summary|Missed Dead Code            |[12 Regregression] Missed
                   |Elimination regression      |Dead Code Elimination
                   |(trunk vs 11.2.0) at -O3    |regression (trunk vs
                   |                            |11.2.0) at -O3
           Keywords|                            |missed-optimization

[Bug tree-optimization/102546] [12 Regregression] Missed Dead Code Elimination regression (trunk vs 11.2.0) at -O3

[rguenth at gcc dot gnu.org]

https://gcc.gnu.org/bugzilla/show_bug.cgi?id=102546

--- Comment #4 from Richard Biener <rguenth at gcc dot gnu.org> ---
(In reply to Aldy Hernandez from comment #2)
> By VRP1 we seem to be calculating the following:
> 
> (f_8 << f_8) && (f_8 == 0)
> 
> This would fold to false, which would elide the foo():
> 
>  <bb 7> [local count: 59055800]:
>   b = 0;
>   _3 = f_8 << f_8;
>   _4 = (char) _3;
>   _5 = (int) _4;
>   if (_4 > 0)
>     goto <bb 8>; [64.06%]
>   else
>     goto <bb 10>; [35.94%]
> 
>   <bb 8> [local count: 34842922]:
>   if (f_8 == 0)
>     goto <bb 9>; [71.10%]
>   else
>     goto <bb 10>; [28.90%]
> 
>   <bb 9> [local count: 12809203]:
>   foo ();

I think it's similar to in the other PR, with old EVRP when visiting BB 8
we pushed [1, +INF] as the global range for _4, then supposedly ranger
manages to evaluate f_8 == 0 with its backward infering somehow.

We no longer do this "path sensitive" adjustment of (global) ranges since
you removed the EVRP DOM walk algorithm.

[Bug tree-optimization/102546] [12 Regregression] Missed Dead Code Elimination regression (trunk vs 11.2.0) at -O3

[aldyh at gcc dot gnu.org]

https://gcc.gnu.org/bugzilla/show_bug.cgi?id=102546

Aldy Hernandez <aldyh at gcc dot gnu.org> changed:

           What    |Removed                     |Added
----------------------------------------------------------------------------
   Last reconfirmed|                            |2021-10-01
             Status|UNCONFIRMED                 |NEW
     Ever confirmed|0                           |1
           Assignee|unassigned at gcc dot gnu.org      |aldyh at gcc dot gnu.org

--- Comment #5 from Aldy Hernandez <aldyh at gcc dot gnu.org> ---
(In reply to Richard Biener from comment #4)
> (In reply to Aldy Hernandez from comment #2)
> > By VRP1 we seem to be calculating the following:
> > 
> > (f_8 << f_8) && (f_8 == 0)
> > 
> > This would fold to false, which would elide the foo():
> > 
> >  <bb 7> [local count: 59055800]:
> >   b = 0;
> >   _3 = f_8 << f_8;
> >   _4 = (char) _3;
> >   _5 = (int) _4;
> >   if (_4 > 0)
> >     goto <bb 8>; [64.06%]
> >   else
> >     goto <bb 10>; [35.94%]
> > 
> >   <bb 8> [local count: 34842922]:
> >   if (f_8 == 0)
> >     goto <bb 9>; [71.10%]
> >   else
> >     goto <bb 10>; [28.90%]
> > 
> >   <bb 9> [local count: 12809203]:
> >   foo ();
> 
> I think it's similar to in the other PR, with old EVRP when visiting BB 8
> we pushed [1, +INF] as the global range for _4, then supposedly ranger
> manages to evaluate f_8 == 0 with its backward infering somehow.
> 
> We no longer do this "path sensitive" adjustment of (global) ranges since
> you removed the EVRP DOM walk algorithm.

The hybrid threader does path sensitive ranges and relationals.  What's missing
is the range-op entry for the following relation:

  ~[0,0] = x << x

In this case, we know that X cannot be 0.  Fixing this, causes all the right
things to happen.

However, I see that the none of the op1_range entries are being called with a
relation.  Presumably this was an oversight on Andrew's part, but can easily be
fixed.

Interestingly on this case, the VRP threader shouldn't even need to step up
here.  VRP1 should have folded the conditional in BB8.  The new evrp can
though.  If I tweak range-ops, and call execute_early_vrp() from VRP1, evrp
folds the conditional and there's no need to thread.

Now before Andrew asks why evrp doesn't clean this up earlier (with the
range-ops tweak), it's because the IL is different.  See my question about the
"a" present in earlier passes. ;-)

So...mine.  I'll address all the issues pointed out.

[Bug tree-optimization/102546] [12 Regregression] Missed Dead Code Elimination regression (trunk vs 11.2.0) at -O3

[aldyh at gcc dot gnu.org]

https://gcc.gnu.org/bugzilla/show_bug.cgi?id=102546

--- Comment #6 from Aldy Hernandez <aldyh at gcc dot gnu.org> ---
(In reply to Richard Biener from comment #4)
> I think it's similar to in the other PR, with old EVRP when visiting BB 8

BTW, which is this other PR, so I may see if my work for this PR fixes that
one?

[Bug tree-optimization/102546] [12 Regregression] Missed Dead Code Elimination regression (trunk vs 11.2.0) at -O3

[zhendong.su at inf dot ethz.ch]

https://gcc.gnu.org/bugzilla/show_bug.cgi?id=102546

--- Comment #7 from Zhendong Su <zhendong.su at inf dot ethz.ch> ---
(In reply to Aldy Hernandez from comment #6)
> (In reply to Richard Biener from comment #4)
> > I think it's similar to in the other PR, with old EVRP when visiting BB 8
> 
> BTW, which is this other PR, so I may see if my work for this PR fixes that
> one?

https://gcc.gnu.org/bugzilla/show_bug.cgi?id=102540

[Bug tree-optimization/102546] [12 Regregression] Missed Dead Code Elimination regression (trunk vs 11.2.0) at -O3

[amacleod at redhat dot com]

https://gcc.gnu.org/bugzilla/show_bug.cgi?id=102546

--- Comment #8 from Andrew Macleod <amacleod at redhat dot com> ---
On 10/1/21 5:18 AM, aldyh at gcc dot gnu.org wrote:
> https://gcc.gnu.org/bugzilla/show_bug.cgi?id=102546
>
> Aldy Hernandez <aldyh at gcc dot gnu.org> changed:
>
>             What    |Removed                     |Added
> ----------------------------------------------------------------------------
>     Last reconfirmed|                            |2021-10-01
>               Status|UNCONFIRMED                 |NEW
>       Ever confirmed|0                           |1
>             Assignee|unassigned at gcc dot gnu.org      |aldyh at gcc dot gnu.org
>
> --- Comment #5 from Aldy Hernandez <aldyh at gcc dot gnu.org> ---
> (In reply to Richard Biener from comment #4)
>> (In reply to Aldy Hernandez from comment #2)
>>> By VRP1 we seem to be calculating the following:
>>>
>>> (f_8 << f_8) && (f_8 == 0)
>>>
>>> This would fold to false, which would elide the foo():
>>>
>>>   <bb 7> [local count: 59055800]:
>>>    b = 0;
>>>    _3 = f_8 << f_8;
>>>    _4 = (char) _3;
>>>    _5 = (int) _4;
>>>    if (_4 > 0)
>>>      goto <bb 8>; [64.06%]
>>>    else
>>>      goto <bb 10>; [35.94%]
>>>
>>>    <bb 8> [local count: 34842922]:
>>>    if (f_8 == 0)
>>>      goto <bb 9>; [71.10%]
>>>    else
>>>      goto <bb 10>; [28.90%]
>>>
>>>    <bb 9> [local count: 12809203]:
>>>    foo ();
>> I think it's similar to in the other PR, with old EVRP when visiting BB 8
>> we pushed [1, +INF] as the global range for _4, then supposedly ranger
>> manages to evaluate f_8 == 0 with its backward infering somehow.
>>
>> We no longer do this "path sensitive" adjustment of (global) ranges since
>> you removed the EVRP DOM walk algorithm.
> The hybrid threader does path sensitive ranges and relationals.  What's missing
> is the range-op entry for the following relation:
>
>    ~[0,0] = x << x
>
> In this case, we know that X cannot be 0.  Fixing this, causes all the right
> things to happen.
>
> However, I see that the none of the op1_range entries are being called with a
> relation.  Presumably this was an oversight on Andrew's part, but can easily be
> fixed.

Not an oversight.  I believe I added the infrastructure to pass 
relations to GORI when I introduce relations to range-ops for folding, 
but there has not been time to flush out actually utilizing them yet.

I can maybe take a look at that next week. maybe.  It also opens up some 
possibilities for solving unsigned overflow questions:

c_1 = a_2 + 2
if (c_1 < a_2)  // check overflow condition

On the true edge, solving [1,1] = c_1 < a_2...  would propagate c_1 < 
a_2 to the defining insn as:
[varying] = a_2 + 2, (LHS < a_2).
op1_range for PLUS can use that relation to determine that a_2 must be 
fully contained in  [INF - 1, INF] on the TRUE side, and therefore c_1  
is [0,1].
The false side would then also calculate a_2 =  [0, INF - 2] and c_1 as 
[2, INF]


> Interestingly on this case, the VRP threader shouldn't even need to step up
> here.  VRP1 should have folded the conditional in BB8.  The new evrp can
> though.  If I tweak range-ops, and call execute_early_vrp() from VRP1, evrp
> folds the conditional and there's no need to thread.
>
> Now before Andrew asks why evrp doesn't clean this up earlier (with the
> range-ops tweak), it's because the IL is different.  See my question about the
> "a" present in earlier passes. ;-)
>
> So...mine.  I'll address all the issues pointed out.
>

[Bug tree-optimization/102546] [12 Regregression] Missed Dead Code Elimination regression (trunk vs 11.2.0) at -O3

[cvs-commit at gcc dot gnu.org]

https://gcc.gnu.org/bugzilla/show_bug.cgi?id=102546

--- Comment #9 from CVS Commits <cvs-commit at gcc dot gnu.org> ---
The master branch has been updated by Aldy Hernandez <aldyh@gcc.gnu.org>:

https://gcc.gnu.org/g:5f9ccf17de7f7581412c6bffd4a37beca9a79836

commit r12-4088-g5f9ccf17de7f7581412c6bffd4a37beca9a79836
Author: Aldy Hernandez <aldyh@redhat.com>
Date:   Fri Oct 1 13:05:36 2021 +0200

    [PR102546] X << Y being non-zero implies X is also non-zero.

    This patch teaches this to range-ops.

    Tested on x86-64 Linux.

    gcc/ChangeLog:

            PR tree-optimization/102546
            * range-op.cc (operator_lshift::op1_range): Teach range-ops that
            X << Y is non-zero implies X is also non-zero.

[Bug tree-optimization/102546] [12 Regregression] Missed Dead Code Elimination regression (trunk vs 11.2.0) at -O3

[aldyh at gcc dot gnu.org]

https://gcc.gnu.org/bugzilla/show_bug.cgi?id=102546

Aldy Hernandez <aldyh at gcc dot gnu.org> changed:

           What    |Removed                     |Added
----------------------------------------------------------------------------
         Resolution|---                         |FIXED
             Status|NEW                         |RESOLVED

--- Comment #10 from Aldy Hernandez <aldyh at gcc dot gnu.org> ---
fixed

[Bug tree-optimization/102546] [12 Regregression] Missed Dead Code Elimination regression (trunk vs 11.2.0) at -O3

[jakub at gcc dot gnu.org]

https://gcc.gnu.org/bugzilla/show_bug.cgi?id=102546

Jakub Jelinek <jakub at gcc dot gnu.org> changed:

           What    |Removed                     |Added
----------------------------------------------------------------------------
                 CC|                            |jakub at gcc dot gnu.org

--- Comment #11 from Jakub Jelinek <jakub at gcc dot gnu.org> ---
Isn't the same thing true also for operator_rshift::op1_range?
I mean, (X >> Y) != 0 implies X != 0.

[Bug tree-optimization/102546] [12 Regregression] Missed Dead Code Elimination regression (trunk vs 11.2.0) at -O3

[aldyh at redhat dot com]

https://gcc.gnu.org/bugzilla/show_bug.cgi?id=102546

--- Comment #12 from Aldy Hernandez <aldyh at redhat dot com> ---
Absolutely, but I didn't want to pollute the patch for this PR. Consider
the patch to do so pre-approved :-).

On Sat, Oct 2, 2021, 00:20 jakub at gcc dot gnu.org <
gcc-bugzilla@gcc.gnu.org> wrote:

> https://gcc.gnu.org/bugzilla/show_bug.cgi?id=102546
>
> Jakub Jelinek <jakub at gcc dot gnu.org> changed:
>
>            What    |Removed                     |Added
>
> ----------------------------------------------------------------------------
>                  CC|                            |jakub at gcc dot gnu.org
>
> --- Comment #11 from Jakub Jelinek <jakub at gcc dot gnu.org> ---
> Isn't the same thing true also for operator_rshift::op1_range?
> I mean, (X >> Y) != 0 implies X != 0.
>
> --
> You are receiving this mail because:
> You are the assignee for the bug.
> You are on the CC list for the bug.
>
>

[Bug tree-optimization/102546] [12 Regregression] Missed Dead Code Elimination regression (trunk vs 11.2.0) at -O3

[jakub at gcc dot gnu.org]

https://gcc.gnu.org/bugzilla/show_bug.cgi?id=102546

--- Comment #13 from Jakub Jelinek <jakub at gcc dot gnu.org> ---
Other cases where that is true are operator_mult (both op1 and op2),
operator_divide,  operator_trunc_mod, operator_abs, operator_absu.