[Bug tree-optimization/100221] New: missed optimization for dead code elimination at -O3 (vs. -O1, -Os, -O2)

[Bug tree-optimization/100221] New: missed optimization for dead code elimination at -O3 (vs. -O1, -Os, -O2)

[zhendong.su at inf dot ethz.ch]

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

            Bug ID: 100221
           Summary: missed optimization for dead code elimination at -O3
                    (vs. -O1, -Os, -O2)
           Product: gcc
           Version: unknown
            Status: UNCONFIRMED
          Severity: normal
          Priority: P3
         Component: tree-optimization
          Assignee: unassigned at gcc dot gnu.org
          Reporter: zhendong.su at inf dot ethz.ch
  Target Milestone: ---

[551] % gcctk -v
Using built-in specs.
COLLECT_GCC=gcctk
COLLECT_LTO_WRAPPER=/local/suz-local/software/local/gcc-trunk/libexec/gcc/x86_64-pc-linux-gnu/12.0.0/lto-wrapper
Target: x86_64-pc-linux-gnu
Configured with: ../gcc-trunk/configure --disable-bootstrap
--prefix=/local/suz-local/software/local/gcc-trunk --enable-languages=c,c++
--disable-werror --enable-multilib --with-system-zlib
Thread model: posix
Supported LTO compression algorithms: zlib
gcc version 12.0.0 20210422 (experimental) [master revision
3cf04d1afa8:0e51007a40c:d42088e453042f4f8ba9190a7e29efd937ea2181] (GCC) 
[552] % 
[552] % gcctk -O1 -S -o O1.s small.c
[553] % gcctk -O3 -S -o O3.s small.c
[554] % 
[554] % wc O1.s O3.s
  49  100  693 O1.s
  73  151 1072 O3.s
 122  251 1765 total
[555] % 
[555] % grep foo O1.s 
[556] % grep foo O3.s
        call    foo
[557] % 
[557] % cat small.c
extern void foo(void);
int a, b;
static int c;
static void f() {
  while (a)
    for (; b; b--)
      ;
}
void i() {
  if (c)
    foo();
  int *g = &c;
  {
    int **h[1] = {&g};
    f();
  }
}
int main() {
  i();
  return 0;
}

[Bug tree-optimization/100221] missed optimization for dead code elimination at -O3 (vs. -O1, -Os, -O2)

[pinskia at gcc dot gnu.org]

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

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

           What    |Removed                     |Added
----------------------------------------------------------------------------
   Last reconfirmed|                            |2021-09-25
             Status|UNCONFIRMED                 |NEW
     Ever confirmed|0                           |1

--- Comment #1 from Andrew Pinski <pinskia at gcc dot gnu.org> ---
So the difference is inlining of f into i early which causes dse1 not to be
able to remove stores for h or g (because of the loop?).

[Bug tree-optimization/100221] missed optimization for dead code elimination at -O3 (vs. -O1, -Os, -O2)

[pinskia at gcc dot gnu.org]

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

--- Comment #2 from Andrew Pinski <pinskia at gcc dot gnu.org> ---
If we force inline f: like:
[[gnu::always_inline]]
static inline void f()

-O2 behavior becomes the same as -O3.

-O3:

  Deleted dead store: # .MEM_7 = VDEF <.MEM_6>
hD.2116[0] = &gD.2115;

-O2:

ipa-modref: call stmt f ();
ipa-modref: call to void f()/3 does not use ref: h[0] alias sets: 3->3
  Deleted dead store: # .MEM_7 = VDEF <.MEM_6>
hD.2116[0] = &gD.2115;

ipa-modref: call stmt f ();
ipa-modref: call to void f()/3 does not use ref: g alias sets: 2->2
  Deleted dead store: # .MEM_6 = VDEF <.MEM_2>
gD.2115 = &_ZL1cD.2103;


I don't see why there is a difference between g and h here except g had its
address taken before maybe tracking MEM though the loop is what is causing the
issue.

[Bug tree-optimization/100221] Takes two passes at DSE to remove some dead stores

[pinskia at gcc dot gnu.org]

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

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

           What    |Removed                     |Added
----------------------------------------------------------------------------
            Summary|missed optimization for     |Takes two passes at DSE to
                   |dead code elimination at    |remove some dead stores
                   |-O3 (vs. -O1, -Os, -O2)     |

--- Comment #3 from Andrew Pinski <pinskia at gcc dot gnu.org> ---
Reduced testcase even further to show the problem (note -O2 and -O3 both now
don't optimize):
extern void foo(void);
int a, b;
static int c;
int main() {
    if (c)
        foo ();
    int *g = &c;
    int **h = &g;
    int ***h1 = &h;
    if (a)
        while (b)
            b = 0;
}

[Bug tree-optimization/100221] Takes two passes at DSE to remove some dead stores

[pinskia at gcc dot gnu.org]

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

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

           What    |Removed                     |Added
----------------------------------------------------------------------------
           Severity|normal                      |enhancement

[Bug tree-optimization/100221] Takes two passes at DSE to remove some dead stores

[rguenth at gcc dot gnu.org]

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

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

           What    |Removed                     |Added
----------------------------------------------------------------------------
            Version|unknown                     |12.0

--- Comment #4 from Richard Biener <rguenth at gcc dot gnu.org> ---
For the reduced testcase the issue is simply that DSE doesn't walk across
multiple paths and we have

<bb 4> :
# .MEM_9 = VDEF <MEM_4>
g = &c;
a.1_2 = a;
if (a.1_2 != 0)
  goto <bb 6>; [INV]
else
  goto <bb 7>; [INV]

  <bb 5> :
  b = 0;

  <bb 6> :
  .MEM_5 = PHI <.MEM_9(4), .MEM_12(5)>
  b.2_3 = b;
  if (b.2_3 != 0)
    goto <bb 5>; [INV]
  else
    goto <bb 7>; [INV]

<bb 7> :
.MEM_6 = PHI <.MEM_9(4), .MEM_5(6)>
g ={v} {CLOBBER};
return 0;

with the walking gathered the .MEM_5 and .MEM_6 defs when following the
.MEM_9 uses and

          /* In addition to kills we can remove defs whose only use
             is another def in defs.  That can only ever be PHIs of which
             we track two for simplicity reasons, the first and last in
             {first,last}_phi_def (we fail for multiple PHIs anyways).
             We can also ignore defs that feed only into
             already visited PHIs.  */
          else if (single_imm_use (vdef, &use_p, &use_stmt)
                   && (use_stmt == first_phi_def
                       || use_stmt == last_phi_def
                       || (gimple_code (use_stmt) == GIMPLE_PHI
                           && bitmap_bit_p (visited,
                                            SSA_NAME_VERSION
                                              (PHI_RESULT (use_stmt))))))
            defs.unordered_remove (i);

does not trigger to remove either PHI def from consideration (but in
principle we could elide .MEM_6 and continue processing .MEM_5 which
eventually will lead us to .MEM_6 anyway).  I suppose the key would be
realizing that one of the PHI defs is a PHI argument of the PHI we can
postpone in this round.

[Bug tree-optimization/100221] Takes two passes at DSE to remove some dead stores

[rguenth at gcc dot gnu.org]

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

--- Comment #5 from Richard Biener <rguenth at gcc dot gnu.org> ---
Note handling this special case doesn't resolve the issue in the original
testcase since the virtual operand setup is different there.  As said, DSE
is not set up to follow multiple paths to uses (sth akin to maybe_skip_until
for the CSE case), but we only try somewhat hard to reduce multiple paths
to one.

[Bug tree-optimization/100221] Takes two passes at DSE to remove some dead stores

[rguenth at gcc dot gnu.org]

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

--- Comment #6 from Richard Biener <rguenth at gcc dot gnu.org> ---
Created attachment 52162
  --> https://gcc.gnu.org/bugzilla/attachment.cgi?id=52162&action=edit
untested patch fixing the reduced testcase

[Bug tree-optimization/100221] Takes two passes at DSE to remove some dead stores

[rguenth at gcc dot gnu.org]

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

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

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

[Bug tree-optimization/100221] Takes two passes at DSE to remove some dead stores

[cvs-commit at gcc dot gnu.org]

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

--- 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:1adf11822bd48f4d65156b7642514630c08c4d00

commit r13-723-g1adf11822bd48f4d65156b7642514630c08c4d00
Author: Richard Biener <rguenther@suse.de>
Date:   Fri May 20 12:24:40 2022 +0200

    tree-optimization/100221 - improve DSE a bit

    When facing multiple PHI defs and one feeding the other we can
    postpone processing uses of one and thus can proceed.

    2022-05-20  Richard Biener  <rguenther@suse.de>

            PR tree-optimization/100221
            * tree-ssa-dse.cc (contains_phi_arg): New function.
            (dse_classify_store): Postpone PHI defs that feed another PHI in
defs.

            * gcc.dg/tree-ssa/ssa-dse-44.c: New testcase.
            * gcc.dg/tree-ssa/ssa-dse-45.c: Likewise.

[Bug tree-optimization/100221] Takes two passes at DSE to remove some dead stores

[rguenth at gcc dot gnu.org]

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

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

           What    |Removed                     |Added
----------------------------------------------------------------------------
             Status|ASSIGNED                    |RESOLVED
      Known to work|                            |13.0
         Resolution|---                         |FIXED

--- Comment #8 from Richard Biener <rguenth at gcc dot gnu.org> ---
Fixed for GCC 13.