[Bug tree-optimization/102703] New: [12 Regression] Dead Code Elimination Regression at -O3

[Bug tree-optimization/102703] New: [12 Regression] Dead Code Elimination Regression at -O3

[theodort at inf dot ethz.ch]

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

            Bug ID: 102703
           Summary: [12 Regression]  Dead Code Elimination Regression 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 test.c
void foo(void);

static int a, b;
static short c;
int main() {
  for (; a; ++a) {
    unsigned short d = a;
    c = d >= 2 ? 0 : 2;
    if (!(b | d) && d)
      foo();
  }
}

gcc-11.2.0 test.c -S -O3 -o /dev/stdout
main:
.LFB0:
        .cfi_startproc
.L2:
        movl    a(%rip), %eax
        testl   %eax, %eax
        je      .L12
        incl    a(%rip)
        jmp     .L2
.L12:
        ret
        .cfi_endproc


gcc-trunk test.c -S -O3 -o /dev/stdout
main:
.LFB0:
        .cfi_startproc
        movl    a(%rip), %eax
        testl   %eax, %eax
        je      .L25
        .p2align 4,,10
        .p2align 3
.L24:
        movzwl  %ax, %edx
        cmpw    $1, %ax
        jbe     .L27
        testl   %edx, %edx
        jne     .L35
.L33:
        subq    $8, %rsp
        .cfi_def_cfa_offset 16
.L4:
        call    foo
        movl    a(%rip), %eax
        addl    $1, %eax
        movl    %eax, a(%rip)
        je      .L36
.L2:
        movzwl  %ax, %edx
        cmpw    $1, %ax
        jbe     .L3
        testl   %edx, %edx
        je      .L4
        addl    $1, %eax
        movl    %eax, a(%rip)
        jne     .L2
.L36:
        xorl    %eax, %eax
        popq    %rdx
        .cfi_def_cfa_offset 8
        ret
        .p2align 4,,10
        .p2align 3
.L35:
        addl    $1, %eax
        movl    %eax, a(%rip)
        jne     .L24
.L25:
        xorl    %eax, %eax
        ret
        .p2align 4,,10
        .p2align 3
.L27:
        testl   %edx, %edx
        jne     .L30
        testb   $1, %al
        jne     .L33
.L30:
        addl    $1, %eax
        movl    %eax, a(%rip)
        jmp     .L24
        .p2align 4,,10
        .p2align 3
.L3:
        .cfi_def_cfa_offset 16
        testl   %edx, %edx
        jne     .L6
        testb   $1, %al
        jne     .L4
.L6:
        addl    $1, %eax
        movl    %eax, a(%rip)
        jmp     .L2
        .cfi_endproc


gcc-trunk -v   
Using built-in specs.
Target: x86_64-pc-linux-gnu
Thread model: posix
Supported LTO compression algorithms: zlib zstd
gcc version 12.0.0 20211012 (experimental) (GCC)

Started with
https://gcc.gnu.org/git/?p=gcc.git;a=commit;h=2e96b5f14e4025691b57d2301d71aa6092ed44bc
(same as https://gcc.gnu.org/bugzilla/show_bug.cgi?id=102546)

[Bug tree-optimization/102703] [12 Regression] Dead Code Elimination Regression at -O3 (trunk vs 11.2.0)

[theodort at inf dot ethz.ch]

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

--- Comment #1 from Theodoros Theodoridis <theodort at inf dot ethz.ch> ---
(11.2.0 at -O3 can eliminate the call to foo but trunk at -O3 cannot)

[Bug tree-optimization/102703] [12 Regression] Dead Code Elimination Regression at -O3 since r12-2591-g2e96b5f14e402569

[marxin at gcc dot gnu.org]

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

Martin Liška <marxin at gcc dot gnu.org> changed:

           What    |Removed                     |Added
----------------------------------------------------------------------------
            Summary|[12 Regression]  Dead Code  |[12 Regression] Dead Code
                   |Elimination Regression at   |Elimination Regression at
                   |-O3 (trunk vs 11.2.0)       |-O3 since
                   |                            |r12-2591-g2e96b5f14e402569
             Status|UNCONFIRMED                 |NEW
   Last reconfirmed|                            |2021-10-12
                 CC|                            |marxin at gcc dot gnu.org
     Ever confirmed|0                           |1

--- Comment #2 from Martin Liška <marxin at gcc dot gnu.org> ---
Confirmed, started with r12-2591-g2e96b5f14e402569.

[Bug tree-optimization/102703] [12 Regression] Dead Code Elimination Regression at -O3 since r12-2591-g2e96b5f14e402569

[rguenth at gcc dot gnu.org]

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

Richard Biener <rguenth at gcc dot gnu.org> changed:

           What    |Removed                     |Added
----------------------------------------------------------------------------
           Keywords|                            |missed-optimization
   Target Milestone|---                         |12.0

[Bug tree-optimization/102703] [12 Regression] Dead Code Elimination Regression at -O3 since r12-2591-g2e96b5f14e402569

[aldyh at gcc dot gnu.org]

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

--- Comment #3 from Aldy Hernandez <aldyh at gcc dot gnu.org> ---
This seems to be some limitation of the RTL optimizers in the presence of more
aggressive jump threading.

Neither the old backward threader nor the old VRP threader could find any
threading possibilities:

[old code]
$ ./cc1 a.c -fdump-tree-all-details -quiet -I/tmp -O3
$ grep threaded a.c.*stati*
$

On the other hand, current trunk gets one thread in the backward threader and
one in the VRP threader:

[trunk]
$ grep threaded a.c.*stati*
116 thread "Jumps threaded" "main" 1
202 vrp-thread "Jumps threaded" "main" 1

Now, neither the old code nor the new code can remove the call to foo() in the
SSA optimizers.  It is the jump_after_combine RTL pass that removes it.

Perhaps an RTL expert could opine here.

[Bug tree-optimization/102703] [12 Regression] Dead Code Elimination Regression at -O3 since r12-2591-g2e96b5f14e402569

[pinskia at gcc dot gnu.org]

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

--- Comment #4 from Andrew Pinski <pinskia at gcc dot gnu.org> ---
There is a missed optimization at the gimple level for sure.


  if (d_11 > 1)
    goto <bb 5>; [59.00%]
  else
    goto <bb 4>; [41.00%]

  <bb 4> [local count: 391808389]:

  <bb 5> [local count: 955630225]:
  # iftmp.1_6 = PHI <0(3), 2(4)>
  c = iftmp.1_6;

The store to c is removed by the time we get to fixup_cfg3 but the phi is
around still:

In .mergephi2:
  d_11 = (short unsigned int) a.4_5;
  if (d_11 > 1)
    goto <bb 5>; [59.00%]
  else
    goto <bb 4>; [41.00%]

  <bb 4> [local count: 391808389]:

  <bb 5> [local count: 955630225]:
  # iftmp.1_6 = PHI <0(3), 2(4)>
  _10 = a.4_5 & 65535;
  if (_10 == 0)
    goto <bb 6>; [50.00%]
  else
    goto <bb 8>; [50.00%]


Then thread1 decides to thread based on the if statement for some unknown
reason ....
even if the first if statement was dead as the phi is dead.  Maybe we need a
quick DCE sometime right after forwprop2?

But maybe jump threading should NOT happen here.



Yes there is a missing jump threading at the gimple level with older versions
too (but it is related to the problem here because of the added jump threading
which was bogus).
This is missed optimization for previous versions:
  d_11 = (short unsigned int) a.4_2;
  _10 = a.4_2 & 65535;
  _6 = d_11 != 0;
  _15 = _10 == 0;
  _1 = _6 & _15;

The above is always false as we have (a&65535) == 0 && (a&65535) != .0

[Bug tree-optimization/102703] [12 Regression] Dead Code Elimination Regression at -O3 since r12-2591-g2e96b5f14e402569

[pinskia at gcc dot gnu.org]

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

--- Comment #5 from Andrew Pinski <pinskia at gcc dot gnu.org> ---
(In reply to Aldy Hernandez from comment #3)
> This seems to be some limitation of the RTL optimizers in the presence of
> more aggressive jump threading.

But the more aggressive jump threading is actually jump threading a "dead"
jump.  that is the biggest problem really.

[Bug tree-optimization/102703] [12 Regression] Dead Code Elimination Regression at -O3 since r12-2591-g2e96b5f14e402569

[aldyh at gcc dot gnu.org]

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

--- Comment #6 from Aldy Hernandez <aldyh at gcc dot gnu.org> ---
(In reply to Andrew Pinski from comment #4)
> There is a missed optimization at the gimple level for sure.
> 
> 
>   if (d_11 > 1)
>     goto <bb 5>; [59.00%]
>   else
>     goto <bb 4>; [41.00%]
> 
>   <bb 4> [local count: 391808389]:
> 
>   <bb 5> [local count: 955630225]:
>   # iftmp.1_6 = PHI <0(3), 2(4)>
>   c = iftmp.1_6;
> 
> The store to c is removed by the time we get to fixup_cfg3 but the phi is
> around still:
> 
> In .mergephi2:
>   d_11 = (short unsigned int) a.4_5;
>   if (d_11 > 1)
>     goto <bb 5>; [59.00%]
>   else
>     goto <bb 4>; [41.00%]
> 
>   <bb 4> [local count: 391808389]:
> 
>   <bb 5> [local count: 955630225]:
>   # iftmp.1_6 = PHI <0(3), 2(4)>
>   _10 = a.4_5 & 65535;
>   if (_10 == 0)
>     goto <bb 6>; [50.00%]
>   else
>     goto <bb 8>; [50.00%]
> 
> 
> Then thread1 decides to thread based on the if statement for some unknown
> reason ....
> even if the first if statement was dead as the phi is dead.  Maybe we need a
> quick DCE sometime right after forwprop2?
> 
> But maybe jump threading should NOT happen here.

The thread in the thread1 pass is 3->5->6->7.  It is an attempt to fold d_11 !=
0 at the end of BB6:

  <bb 3> [local count: 955630225]:
  d_11 = (short unsigned int) a.4_5;
  if (d_11 > 1)
    goto <bb 5>; [59.00%]
  else
    goto <bb 4>; [41.00%]

  <bb 4> [local count: 391808389]:

  <bb 5> [local count: 955630225]:
  # iftmp.1_6 = PHI <0(3), 2(4)>
  _10 = a.4_5 & 65535;
  if (_10 == 0)
    goto <bb 6>; [50.00%]
  else
    goto <bb 8>; [50.00%]

  <bb 6> [local count: 477815112]:
  if (d_11 != 0)
    goto <bb 7>; [33.00%]
  else
    goto <bb 8>; [67.00%]

  <bb 7> [local count: 157678986]:
  foo ();


The only way it can fold d_11 != 0, is by chasing back to the 3->5 edge.  The
PHI in BB5 is irrelevant, as the conditional in it is a check against _10 not
the iftmp.1_6 PHI result.  What is useful is the 3->5 edge.

I don't understand why you think this thread is incorrect.

[Bug tree-optimization/102703] [12 Regression] Dead Code Elimination Regression at -O3 since r12-2591-g2e96b5f14e402569

[pinskia at gcc dot gnu.org]

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

--- Comment #7 from Andrew Pinski <pinskia at gcc dot gnu.org> ---
Because:
  if (d_11 > 1)
    goto <bb 5>; [59.00%]
  else
    goto <bb 4>; [41.00%]

  <bb 4> [local count: 391808389]:

  <bb 5> [local count: 955630225]:
  # iftmp.1_6 = PHI <0(3), 2(4)>

If the phi node was removed, the original al condition for d_11 > 1 would be
remove.

[Bug tree-optimization/102703] [12 Regression] Dead Code Elimination Regression at -O3 since r12-2591-g2e96b5f14e402569

[aldyh at redhat dot com]

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

--- Comment #8 from Aldy Hernandez <aldyh at redhat dot com> ---
On Wed, Oct 13, 2021, 11:37 pinskia at gcc dot gnu.org <
gcc-bugzilla@gcc.gnu.org> wrote:

> https://gcc.gnu.org/bugzilla/show_bug.cgi?id=102703
>
> --- Comment #7 from Andrew Pinski <pinskia at gcc dot gnu.org> ---
> Because:
>   if (d_11 > 1)
>     goto <bb 5>; [59.00%]
>   else
>     goto <bb 4>; [41.00%]
>
>   <bb 4> [local count: 391808389]:
>
>   <bb 5> [local count: 955630225]:
>   # iftmp.1_6 = PHI <0(3), 2(4)>
>
> If the phi node was removed, the original al condition for d_11 > 1 would
> be
> remove.
>

As the IL stands, the 3->5 edge has relevant range information.  If the IL
should be different at this point, there is no way the threader can know
this.

Aldy

[Bug tree-optimization/102703] [12 Regression] Dead Code Elimination Regression at -O3 since r12-2591-g2e96b5f14e402569

[aldyh at gcc dot gnu.org]

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

--- Comment #9 from Aldy Hernandez <aldyh at gcc dot gnu.org> ---
(In reply to Aldy Hernandez from comment #8)
> On Wed, Oct 13, 2021, 11:37 pinskia at gcc dot gnu.org <
> gcc-bugzilla@gcc.gnu.org> wrote:
> 
> > https://gcc.gnu.org/bugzilla/show_bug.cgi?id=102703
> >
> > --- Comment #7 from Andrew Pinski <pinskia at gcc dot gnu.org> ---
> > Because:
> >   if (d_11 > 1)
> >     goto <bb 5>; [59.00%]
> >   else
> >     goto <bb 4>; [41.00%]
> >
> >   <bb 4> [local count: 391808389]:
> >
> >   <bb 5> [local count: 955630225]:
> >   # iftmp.1_6 = PHI <0(3), 2(4)>
> >
> > If the phi node was removed, the original al condition for d_11 > 1 would
> > be
> > remove.
> >
> 
> As the IL stands, the 3->5 edge has relevant range information.  If the IL
> should be different at this point, there is no way the threader can know
> this.

Note that I'm not against a cleanup pass running before as you suggested, or
perhaps whomever made the PHI redundant could also clean up the PHI itself. 
I'm just merely saying that the threader is working as expected with the IL at
hand.

Also, if we did have cleaner IL, we could probably tweak the threader to elide
the call to foo() earlier.  That is, without having to resort to help from the
RTL optimizers.

In this testcase we could probably divine that the combination of the
truncating cast and the bitwise AND is showing that a.4_2 can't have both the
lower bits set and cleared at the same time.  I'm not sure it's worth tweaking
the path solver for this, but it's definitely worth exploring.

As usual, thanks for narrowing all these bug reports.  It makes a big
difference, and your presence during bug hunting season is always a big plus.

[Bug tree-optimization/102703] [12 Regression] Dead Code Elimination Regression at -O3 since r12-2591-g2e96b5f14e402569

[pinskia at gcc dot gnu.org]

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

--- Comment #10 from Andrew Pinski <pinskia at gcc dot gnu.org> ---
(In reply to Aldy Hernandez from comment #9)
> Also, if we did have cleaner IL, we could probably tweak the threader to
> elide the call to foo() earlier.  That is, without having to resort to help
> from the RTL optimizers.

Right which is why I had wrote:
> Maybe we need a quick DCE sometime right after forwprop2?

Another way to do the cleanup is when the store is removed when detected it was
a write only store, also remove the definiving SSA_NAME what was used for the
store's rhs (if it was only used in that statement). I could not figure out
which pass removed that but let me see if I can figure that out and it should
help here (and others).

> As usual, thanks for narrowing all these bug reports.  It makes a big
> difference, and your presence during bug hunting season is always a big plus.

[Bug tree-optimization/102703] [12 Regression] Dead Code Elimination Regression at -O3 since r12-2591-g2e96b5f14e402569

[pinskia at gcc dot gnu.org]

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

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

           What    |Removed                     |Added
----------------------------------------------------------------------------
             Status|NEW                         |ASSIGNED
           Assignee|unassigned at gcc dot gnu.org      |pinskia at gcc dot gnu.org

--- Comment #11 from Andrew Pinski <pinskia at gcc dot gnu.org> ---
Mine for the DCE issue.
The delete of the store comes from execute_fixup_cfg but there was no printing
out so it was hard to figure that part out.
Anyways I am going to add the debug prints too.

[Bug tree-optimization/102703] [12 Regression] Dead Code Elimination Regression at -O3 since r12-2591-g2e96b5f14e402569

[pinskia at gcc dot gnu.org]

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

--- Comment #12 from Andrew Pinski <pinskia at gcc dot gnu.org> ---
Created attachment 51613
  --> https://gcc.gnu.org/bugzilla/attachment.cgi?id=51613&action=edit
Current patchset which I am testing

Here is my current patch set which fixes this.  It is 4 patches.  The first
three are either adding dumping info or cleanup of the code.  The 4th is the
one which does the optimization.

[Bug tree-optimization/102703] [12 Regression] Dead Code Elimination Regression at -O3 since r12-2591-g2e96b5f14e402569

[pinskia at gcc dot gnu.org]

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

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

           What    |Removed                     |Added
----------------------------------------------------------------------------
  Attachment #51613|0                           |1
        is obsolete|                            |

--- Comment #13 from Andrew Pinski <pinskia at gcc dot gnu.org> ---
Created attachment 51614
  --> https://gcc.gnu.org/bugzilla/attachment.cgi?id=51614&action=edit
Patch which I am testing

The previous file had an extra (older) patch in it.

[Bug tree-optimization/102703] [12 Regression] Dead Code Elimination Regression at -O3 since r12-2591-g2e96b5f14e402569

[pinskia at gcc dot gnu.org]

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

--- Comment #14 from Andrew Pinski <pinskia at gcc dot gnu.org> ---
(In reply to Andrew Pinski from comment #13)
> Created attachment 51614 [details]
> Patch which I am testing
> 
> The previous file had an extra (older) patch in it.

I should add some stats for this, oh well, I will do that after my current
build/test finishes.

[Bug tree-optimization/102703] [12 Regression] Dead Code Elimination Regression at -O3 since r12-2591-g2e96b5f14e402569

[pinskia at gcc dot gnu.org]

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

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

           What    |Removed                     |Added
----------------------------------------------------------------------------
                URL|                            |https://gcc.gnu.org/piperma
                   |                            |il/gcc-patches/2021-October
                   |                            |/581963.html
           Keywords|                            |patch

--- Comment #15 from Andrew Pinski <pinskia at gcc dot gnu.org> ---
Patch series starts here:
https://gcc.gnu.org/pipermail/gcc-patches/2021-October/581963.html

[Bug tree-optimization/102703] [12 Regression] Dead Code Elimination Regression at -O3 since r12-2591-g2e96b5f14e402569

[pinskia at gcc dot gnu.org]

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

--- Comment #16 from Andrew Pinski <pinskia at gcc dot gnu.org> ---
I have a new patch in testing that replaces patch 4 and uses
simple_dce_from_worklist instead which moves of the detection of dead code to
already common code.

[Bug tree-optimization/102703] [12 Regression] Dead Code Elimination Regression at -O3 since r12-2591-g2e96b5f14e402569

[pinskia at gcc dot gnu.org]

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

--- Comment #17 from Andrew Pinski <pinskia at gcc dot gnu.org> ---
Hmm, I get one regression:
+FAIL: gcc.dg/pr36902.c  (test for warnings, line 47)

I filed PR 102864 and will change the testcase so we don't run into that issue.

[Bug tree-optimization/102703] [12 Regression] Dead Code Elimination Regression at -O3 since r12-2591-g2e96b5f14e402569

[cvs-commit at gcc dot gnu.org]

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

--- Comment #18 from CVS Commits <cvs-commit at gcc dot gnu.org> ---
The trunk branch has been updated by Andrew Pinski <pinskia@gcc.gnu.org>:

https://gcc.gnu.org/g:005ebe1c07843e6312cd70523945fa1d729e7253

commit r12-4595-g005ebe1c07843e6312cd70523945fa1d729e7253
Author: Andrew Pinski <apinski@marvell.com>
Date:   Sat Oct 16 02:30:55 2021 +0000

    Add dump prints when execute_fixup_cfg removes a write only var store.

    While debugging PR 102703, I found it was hard to figure out where
    the store was being removed as there was no pass which was outputting
    why the store was removed.
    This adds to execute_fixup_cfg the output.
    Also note most of removals happen when execute_fixup_cfg is called
    from the inliner.

    gcc/ChangeLog:

            * tree-cfg.c (execute_fixup_cfg): Output when the statement
            is removed when it is a write only var.

[Bug tree-optimization/102703] [12 Regression] Dead Code Elimination Regression at -O3 since r12-2591-g2e96b5f14e402569

[cvs-commit at gcc dot gnu.org]

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

--- Comment #19 from CVS Commits <cvs-commit at gcc dot gnu.org> ---
The trunk branch has been updated by Andrew Pinski <pinskia@gcc.gnu.org>:

https://gcc.gnu.org/g:36ec4a3c927bd2cc212a7f331ad842cd90eb5283

commit r12-4597-g36ec4a3c927bd2cc212a7f331ad842cd90eb5283
Author: Andrew Pinski <apinski@marvell.com>
Date:   Sat Oct 16 03:09:05 2021 +0000

    Factor out removal of write only stores from execute_fixup_cfg

    To make it easier to fix PR 102703, factoring this code out
    to its own function makes it easier to read and less indentions
    too.

    gcc/ChangeLog:

            * tree-cfg.c (maybe_remove_writeonly_store): New function
            factored out from ...
            (execute_fixup_cfg): Here. Call maybe_remove_writeonly_store.

[Bug tree-optimization/102703] [12 Regression] Dead Code Elimination Regression at -O3 since r12-2591-g2e96b5f14e402569

[pinskia at gcc dot gnu.org]

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

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

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

--- Comment #20 from Andrew Pinski <pinskia at gcc dot gnu.org> ---
Fixed.
https://gcc.gnu.org/pipermail/gcc-cvs/2021-October/355644.html