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

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

[theodort at inf dot ethz.ch]

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

            Bug ID: 102880
           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 b, c, d, e, f, ah;
static short g, ai, am, aq, as;
static char an, at, av, ax, ay;
static char a(char h, char i) { return i == 0 || h && i == 1 ? 0 : h % i; }
static void ae(int h) {
  if (a(b, h))
    foo();

}
int main() {
  ae(1);
  ay = a(0, ay);
  ax = a(g, aq);
  at = a(0, as);
  av = a(c, 1);
  an = a(am, f);
  int al = e || ((a(1, ah) && b) & d) == 2;
  ai = al;
}

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

gcc-11 -O3 -S test.c -o /dev/stdout
...
main:
.LFB2:
        .cfi_startproc
        movb    $0, ay(%rip)
        xorl    %eax, %eax
        ret
        .cfi_endproc

gcc-11 -O3 -S test.c -o /dev/stdout
...
a.part.0:
.LFB3:
        .cfi_startproc
        testb   %dil, %dil
        je      .L5
        xorl    %eax, %eax
        cmpb    $1, %sil
        jne     .L5
        ret
.L5:
        movsbl  %dil, %eax
        movsbl  %sil, %esi
        cltd
        idivl   %esi
        movl    %edx, %eax
        ret
        .cfi_endproc
...
main:
.LFB2:
        .cfi_startproc
        subq    $8, %rsp
        .cfi_def_cfa_offset 16
        xorl    %edi, %edi
        movl    $1, %esi
        call    a.part.0
        testb   %al, %al
        jne     .L18
.L9:
        movzbl  ay(%rip), %eax
        testb   %al, %al
        je      .L10
        movsbl  %al, %esi
        xorl    %edi, %edi
        call    a.part.0
.L10:
        movb    %al, ay(%rip)
        xorl    %eax, %eax
        addq    $8, %rsp
        .cfi_remember_state
        .cfi_def_cfa_offset 8
        ret
.L18:
        .cfi_restore_state
        call    foo
        jmp     .L9
        .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 20211021 (experimental) (GCC)

Started with
https://gcc.gnu.org/git/?p=gcc.git;a=commit;h=b58dc0b803057c0e6032e0d9bd92cd834f72c75c

[Bug tree-optimization/102880] [12 Regression] Dead Code Elimination Regression at -O3

[marxin at gcc dot gnu.org]

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

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

           What    |Removed                     |Added
----------------------------------------------------------------------------
             Status|UNCONFIRMED                 |NEW
   Last reconfirmed|                            |2021-10-21
     Ever confirmed|0                           |1
                 CC|                            |marxin at gcc dot gnu.org,
                   |                            |rguenth at gcc dot gnu.org

--- Comment #1 from Martin Liška <marxin at gcc dot gnu.org> ---
Thanks for the report. Please CC authors of the revision that you bisected to.

[Bug tree-optimization/102880] [12 Regression] Dead Code Elimination Regression at -O3

[pinskia at gcc dot gnu.org]

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

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

           What    |Removed                     |Added
----------------------------------------------------------------------------
           Keywords|                            |missed-optimization

--- Comment #2 from Andrew Pinski <pinskia at gcc dot gnu.org> ---
So this is standard main is called once only difference.
renaming main to hhh (and adding a return 0; at the end), I get the
optimization.

the added DCE changes how inlining heurstic are for the functions so I really
doubt this is a real issue.

[Bug tree-optimization/102880] [12 Regression] Dead Code Elimination Regression at -O3

[rguenth at gcc dot gnu.org]

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

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

           What    |Removed                     |Added
----------------------------------------------------------------------------
           Keywords|missed-optimization         |
             Status|NEW                         |ASSIGNED
   Target Milestone|---                         |12.0
           Assignee|unassigned at gcc dot gnu.org      |rguenth at gcc dot gnu.org

--- Comment #3 from Richard Biener <rguenth at gcc dot gnu.org> ---
The difference after DSE1 is (for main):

@@ -235,20 +251,9 @@

   <bb 13> :
   b.11_31 = b;
-  if (b.11_31 != 0)
-    goto <bb 15>; [INV]
-  else
-    goto <bb 14>; [INV]

   <bb 14> :
-
-  <bb 15> :
-  # iftmp.9_36 = PHI <1(13), 0(14)>
-  d.12_32 = d;
-  _33 = d.12_32 & iftmp.9_36;
-
-  <bb 17> :
-  # iftmp.7_35 = PHI <1(10), 0(15)>
+  # iftmp.7_35 = PHI <1(10), 0(11), 0(13), 0(12)>
   _34 = (short int) iftmp.7_35;
   ai = _34;
   return 0;

where this then causes less CDDCE:

-marking necessary through iftmp.7_35 stmt iftmp.7_35 = PHI <1(10), 0(15)>
-processing: iftmp.7_35 = PHI <1(10), 0(15)>
+marking necessary through iftmp.7_35 stmt iftmp.7_35 = PHI <1(10), 0(11),
0(13), 0(12)>
+processing: iftmp.7_35 = PHI <1(10), 0(11), 0(13), 0(12)>

 Marking useful stmt: if (e.8_26 != 0)

+Marking useful stmt: if (iftmp.14_83 != 0)
+
+Marking useful stmt: if (_28 != 0)
+
+processing: if (_28 != 0)
+
+marking necessary through _28 stmt _28 = (char) ah.10_27;
+processing: _28 = (char) ah.10_27;
+
+marking necessary through ah.10_27 stmt ah.10_27 = ah;
+processing: ah.10_27 = ah;
+
+processing: if (iftmp.14_83 != 0)
+
+marking necessary through iftmp.14_83 stmt iftmp.14_83 = a.part.0 (1, _29);
+processing: iftmp.14_83 = a.part.0 (1, _29);
+
+marking necessary through _29 stmt _29 = (int) _28;
+processing: _29 = (int) _28;
+

the key here is I guess that if we'd split the CFG so that PHIs only
have _different_ arguments we would be able to reduce the number of
control dependences.

That seems like a general issue of CD-DCE, in this case exposed by the
extra DCE from DSE which in turn triggers block merging from CFG cleanup
(we trigger that once we removed a PHI which we did).

Now the question is whether there's a good way to alter the control
dependence query in a way to make this work without factoring the PHIs
first.  I suppose querying control dependence of the common dominator
of the same-argument PHI edges might work.

[Bug tree-optimization/102880] [12 Regression] Dead Code Elimination Regression at -O3

[rguenth at gcc dot gnu.org]

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

--- Comment #4 from Richard Biener <rguenth at gcc dot gnu.org> ---
Created attachment 51652
  --> https://gcc.gnu.org/bugzilla/attachment.cgi?id=51652&action=edit
not working patch

OK, that's definitely a too simplistic idea, the basic assessment still holds
though.  CD-DCE benefits from forwarders for equal PHI arguments.

Not working patch attached (using the common dominator idea).  Regresses
for example gcc.c-torture/execute/20050218-1.c.

[Bug tree-optimization/102880] [12 Regression] Dead Code Elimination Regression at -O3

[rguenth at gcc dot gnu.org]

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

--- Comment #5 from Richard Biener <rguenth at gcc dot gnu.org> ---
Created attachment 51699
  --> https://gcc.gnu.org/bugzilla/attachment.cgi?id=51699&action=edit
hack to make forwarders

This is an overly simple attempt to make forwarders which works to restore the
DCE.

Given this it probably makes sense to at least move the early merge_phi pass
after CD-DCE.  That doesn't help this testcase since regular CFG cleanup
performs the merging in our case.  It's remove_forwarder_block will perform
this.

An alternative band-aid would be to resolve the regression by not running
CFG cleanup after DSE (we're failing to run it when we empty a BB as well,
something we might want to fix instead).

Undoing PHI merging might be also a good thing to perform before going out of
SSA.  And merge_phi itself might do this as a 2nd step.

[Bug tree-optimization/102880] [12 Regression] Dead Code Elimination Regression at -O3

[rguenth at gcc dot gnu.org]

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

--- Comment #6 from Richard Biener <rguenth at gcc dot gnu.org> ---
So interestingly as a band-aid fix I bootstrapped and tested

diff --git a/gcc/tree-cfgcleanup.c b/gcc/tree-cfgcleanup.c
index a016ee47a02..c2a0555dd78 100644
--- a/gcc/tree-cfgcleanup.c
+++ b/gcc/tree-cfgcleanup.c
@@ -351,6 +351,7 @@ tree_forwarder_block_p (basic_block bb, bool phi_wanted)
       /* If PHI_WANTED is false, BB must not have any PHI nodes.
         Otherwise, BB must have PHI nodes.  */
       || gimple_seq_empty_p (phi_nodes (bb)) == phi_wanted
+      || single_pred_p (bb) == phi_wanted
       /* BB may not be a predecessor of the exit block.  */
       || single_succ (bb) == EXIT_BLOCK_PTR_FOR_FN (cfun)
       /* Nor should this be an infinite loop.  */

which makes the forwarder block removal of CFG cleanup only remove forwarders
with a single predecessor (formerly it handled multiple predecessors if they
did not have PHIs).

There's no testsuite fallout from this patch but the testcase is fixed.

IMHO we should handle degenerate PHIs with a single predecessor here
and yank the PHI node restriction if we go with this.

It will still not catch all CD-DCE opportunities since that's of course not
a reliable way to have common arguments factored.  We talked a bit about
recovering the control dependence info of a virtuall inserted forwarder
but if possible it isn't anything trivial so I'd tend to go with explicit
factoring before running CD-DCE.

[Bug tree-optimization/102880] [12 Regression] Dead Code Elimination Regression at -O3

[cvs-commit at gcc dot gnu.org]

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

--- Comment #7 from CVS Commits <cvs-commit at gcc dot gnu.org> ---
The master branch has been updated by Richard Biener <rguenth@gcc.gnu.org>:

https://gcc.gnu.org/g:f98f373dd822b35c52356b753d528924e9f89678

commit r12-5300-gf98f373dd822b35c52356b753d528924e9f89678
Author: Richard Biener <rguenther@suse.de>
Date:   Mon Nov 15 15:19:36 2021 +0100

    tree-optimization/102880 - make PHI-OPT recognize more CFGs

    This allows extra edges into the middle BB for the PHI-OPT
    transforms using replace_phi_edge_with_variable that do not
    end up moving stmts from that middle BB.  This avoids regressing
    gcc.dg/tree-ssa/ssa-hoist-4.c with the actual fix for PR102880
    where CFG cleanup has the choice to remove two forwarders and
    picks "the wrong" leading to

       if (a > b) /
           /\    /
          /  <BB>
         /    |
      # PHI <a, b>

    rather than

       if (a > b)  |
           /\      |
        <BB> \     |
         /    \    |
      # PHI <a, b, b>

    but it's relatively straight-forward to support extra edges
    into the middle-BB in paths ending in replace_phi_edge_with_variable
    and that do not require moving stmts.  That's because we really
    only want to remove the edge from the condition to the middle BB.
    Of course actually doing that means updating dominators in non-trival
    ways which is why I kept the original code for the single edge
    case and simply defer to CFG cleanup by adjusting the condition for
    the complicated case.

    The testcase needs to be a GIMPLE one since it's quite unreliable
    to produce the desired CFG.

    2021-11-15  Richard Biener  <rguenther@suse.de>

            PR tree-optimization/102880
            * tree-ssa-phiopt.c (tree_ssa_phiopt_worker): Push
            single_pred (bb1) condition to places that really need it.
            (match_simplify_replacement): Likewise.
            (value_replacement): Likewise.
            (replace_phi_edge_with_variable): Deal with extra edges
            into the middle BB.

            * gcc.dg/tree-ssa/phi-opt-26.c: New testcase.

[Bug tree-optimization/102880] [12 Regression] Dead Code Elimination Regression at -O3

[cvs-commit at gcc dot gnu.org]

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

--- Comment #8 from CVS Commits <cvs-commit at gcc dot gnu.org> ---
The master branch has been updated by Richard Biener <rguenth@gcc.gnu.org>:

https://gcc.gnu.org/g:045206450386bcd774db3bde0c696828402361c6

commit r12-5301-g045206450386bcd774db3bde0c696828402361c6
Author: Richard Biener <rguenther@suse.de>
Date:   Fri Nov 12 10:21:22 2021 +0100

    tree-optimization/102880 - improve CD-DCE

    The PR shows a missed control-dependent DCE caused by CFG cleanup
    merging a forwarder resulting in a partially degenerate PHI node.
    With control-dependent DCE we need to mark control dependences
    of incoming edges into PHIs as necessary but that is unnecessarily
    conservative for the case when two edges have the same value.
    There is no easy way to mark only a subset of control dependences
    of both edges necessary so the fix is to produce forwarder blocks
    where then the control dependence captures the requirements more
    precisely.

    For gcc.dg/tree-ssa/ssa-dom-thread-7.c the number of edges in the
    CFG decrease as we have commonized PHI arguments which in turn
    results in different threadings.  The testcase is too complex
    and the dump scanning too simple to do anything meaningful here
    but to adjust the number of expected threads.

    The same CFG massaging could be useful at RTL expansion time to
    reduce the number of copies we need to insert on edges.

    FAIL: gcc.dg/tree-ssa/ssa-hoist-4.c scan-tree-dump-times optimized
"MAX_EXPR" 1

    2021-11-12  Richard Biener  <rguenther@suse.de>

            PR tree-optimization/102880
            * tree-ssa-dce.c (sort_phi_args): New function.
            (make_forwarders_with_degenerate_phis): Likewise.
            (perform_tree_ssa_dce): Call
            make_forwarders_with_degenerate_phis.

            * gcc.dg/tree-ssa/pr102880.c: New testcase.
            * gcc.dg/tree-ssa/pr69270-3.c: Robustify.
            * gcc.dg/tree-ssa/ssa-dom-thread-7.c: Change the number of
            expected threadings.

[Bug tree-optimization/102880] [12 Regression] Dead Code Elimination Regression at -O3

[rguenth at gcc dot gnu.org]

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

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

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

--- Comment #9 from Richard Biener <rguenth at gcc dot gnu.org> ---
Fixed.

[Bug tree-optimization/102880] [12 Regression] Dead Code Elimination Regression at -O3

[clyon at gcc dot gnu.org]

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

Christophe Lyon <clyon at gcc dot gnu.org> changed:

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

--- Comment #10 from Christophe Lyon <clyon at gcc dot gnu.org> ---
After r12-5301, on aarch64 I can see:
FAIL: gcc.dg/tree-ssa/ssa-dom-thread-7.c scan-tree-dump thread2 "Jumps
threaded: 18"

[Bug tree-optimization/102880] [12 Regression] Dead Code Elimination Regression at -O3

[pinskia at gcc dot gnu.org]

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

--- Comment #11 from Andrew Pinski <pinskia at gcc dot gnu.org> ---
(In reply to Christophe Lyon from comment #10)
> After r12-5301, on aarch64 I can see:
> FAIL: gcc.dg/tree-ssa/ssa-dom-thread-7.c scan-tree-dump thread2 "Jumps
> threaded: 18"

Yes it looks like Richard forgot to adjust the testcase for aarch64

[Bug tree-optimization/102880] [12 Regression] Dead Code Elimination Regression at -O3

[rguenth at gcc dot gnu.org]

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

--- Comment #12 from Richard Biener <rguenth at gcc dot gnu.org> ---
(In reply to Andrew Pinski from comment #11)
> (In reply to Christophe Lyon from comment #10)
> > After r12-5301, on aarch64 I can see:
> > FAIL: gcc.dg/tree-ssa/ssa-dom-thread-7.c scan-tree-dump thread2 "Jumps
> > threaded: 18"
> 
> Yes it looks like Richard forgot to adjust the testcase for aarch64

No, I just didn't know the new "magic" number ;)  Please adjust it to reflect
reality.