[Bug rtl-optimization/104515] New: trivially-destructible destructors interfere with loop optimization - maybe related to lifetime-dse.

[Bug rtl-optimization/104515] New: trivially-destructible destructors interfere with loop optimization - maybe related to lifetime-dse.

[gcc at rabensky dot com]

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

            Bug ID: 104515
           Summary: trivially-destructible destructors interfere with loop
                    optimization - maybe related to lifetime-dse.
           Product: gcc
           Version: og11 (devel/omp/gcc-11)
            Status: UNCONFIRMED
          Severity: normal
          Priority: P3
         Component: rtl-optimization
          Assignee: unassigned at gcc dot gnu.org
          Reporter: gcc at rabensky dot com
  Target Milestone: ---

This issue started in GCC-9.1, but a change in GCC-11 made it worse.

It didn't exist in GCC-7.1-GCC-8.5

Short description:
-----------------

When we have a loop that can be optimized out, calling the destructor for a
trivially-destructible type will prevent the optimization starting from GCC-9.1

These are loops that correctly optimized out in GCC-7.1 to GCC-8.5

This bug doesn't happen if we set -fno-lifetime-dse

Interestingly enough - a non-trivially-destructible destructor doesn't
necessarily prevent the optimization.

How this became worse in GCC-11:
-------------------------------

In GCC-11 this also applies to calling the destructor of basic types (int, long
etc.)

So loops that optimized in GCC-7.1 to GCC-10.3 no longer optimize.

Short reproducing example:
-------------------------

NOTE: No `include`s are needed

```
using T = int;
struct Vec {
  T* end;
};
void pop_back_many(Vec& v, unsigned n) {
  for (unsigned i = 0; i < n; ++i) {
    --v.end;
    v.end->~T();
  }
}
```
compiled with `-O3 -Wall`

In GCC-7 to GCC-10, `pop_back_many` optimizes out the loop (becomes
`v.end-=n`).
In GCC-11, the loop remains.

See https://godbolt.org/z/vTexxhxP9

NOTE that adding `-fno-lifetime-dse` will re-enable the loop optimization.

Why this matters
----------------
This prevents optimization of a loop over `std::vector<int>::pop_back()`, which
is a very common usecase!

Loops that optimize out in GCC-7.1 to GCC-10.3 will suddenly not optimize in
GCC-11.1/2, making existing code run MUCH slower! (O(n) instead of O(1))

NOTE: std::vector<int>::resize is a lot slower than loop over pop_back. A loop
over pop_back is currently the most efficient way to do pop_back_many!

More complete reproducing example:
---------------------------------

- We can replace the type `T` with a class that is trivially destructible.
**In that case, the problem exists in previous versions of GCC as well**

- We can replace the type `T` with a class that had user-supplied destructor.
**In that case, the loop correctly optimizes out if possible**

Actual examples:
https://godbolt.org/z/7WqTPq3cE

compiled with `-O3 -Wall`
```
template <typename T>
struct Vec {
  T* end;
};

template <typename T>
void pop_back_many(Vec<T>& v, unsigned n) {
  for (unsigned i = 0; i < n; ++i) {
    --v.end;
    v.end->~T();
  }
}

struct TrivialDestruct {
    ~TrivialDestruct()=default;
};

struct NoopDestruct {
    ~NoopDestruct(){}
};

unsigned count=0;
struct CountDestruct {
    ~CountDestruct(){++count;}
};

// Here loop optimization fails in GCC-11.1-11.2
// But succeeds in GCC 7.1-10.3
//
// NOTE that adding -fno-lifetime-dse re-enabled the optimization
template void pop_back_many(Vec<int>&, unsigned);
// Here loop optimization fails in GCC-9.1-11.2
// But succeeds in GCC 7.1-8.5
//
// NOTE that adding -fno-lifetime-dse re-enabled the optimization
template void pop_back_many(Vec<TrivialDestruct>&, unsigned);
// Here loop optimization succeeds in all versions
//
// NOTE that it's surprising that a no-op destructor can be optimized
// but a trivial destructor can't
template void pop_back_many(Vec<NoopDestruct>&, unsigned);
// Here loop optimization succeeds in all version
//
// NOTE that it's surprising that a destructor with an action
// can be optimized, but a trivial destructor can't
template void pop_back_many(Vec<CountDestruct>&, unsigned);
```

[Bug tree-optimization/104515] [11/12 Regression] trivially-destructible destructors interfere with loop optimization - maybe related to lifetime-dse.

[rguenth at gcc dot gnu.org]

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

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

           What    |Removed                     |Added
----------------------------------------------------------------------------
   Last reconfirmed|                            |2022-02-14
     Ever confirmed|0                           |1
           Priority|P3                          |P2
          Component|rtl-optimization            |tree-optimization
            Summary|trivially-destructible      |[11/12 Regression]
                   |destructors interfere with  |trivially-destructible
                   |loop optimization - maybe   |destructors interfere with
                   |related to lifetime-dse.    |loop optimization - maybe
                   |                            |related to lifetime-dse.
                 CC|                            |jakub at gcc dot gnu.org,
                   |                            |rguenth at gcc dot gnu.org
             Status|UNCONFIRMED                 |ASSIGNED
   Target Milestone|---                         |11.3

--- Comment #1 from Richard Biener <rguenth at gcc dot gnu.org> ---
Confirmed.  The issue is that store motion of v_7(D)->end cannot be performed
on

  <bb 3> [local count: 955630225]:
  # i_13 = PHI <i_10(6), 0(5)>
  _1 = v_7(D)->end;
  _2 = _1 + 18446744073709551612;
  v_7(D)->end = _2;
  MEM[(T *)_1 + -4B] ={v} {CLOBBER};   // <- inserted by -flifetime-dse
  i_10 = i_13 + 1;
  if (n_6(D) > i_10)
    goto <bb 6>; [89.00%]
  else
    goto <bb 4>; [11.00%]

  <bb 6> [local count: 850510901]:
  goto <bb 3>; [100.00%]

With GCC 10 we didn't have this particular CLOBBER and at least in GCC 10 the
first testcase was properly optimized.

Note there's a dependence on the value of v_7(D)->end for the clobber so
the clobber itself cannot be moved out of the loop.  So the only option
here would be to drop it if it enables store-motion.

We remove all *ssaname_N ={v} {CLOBBER} stmts during the fold-all-builtins
pass but that's very late, in particular _after_ the last CDDCE.  I suspect
that instead of

      NEXT_PASS (pass_dse);
      NEXT_PASS (pass_cd_dce, true /* update_address_taken_p */);
      /* After late CD DCE we rewrite no longer addressed locals into SSA
         form if possible.  */
      NEXT_PASS (pass_forwprop);
      NEXT_PASS (pass_phiopt, false /* early_p */);
      NEXT_PASS (pass_fold_builtins);

we might consider doing FAB (or the CLOBBER removal part) after the last
DSE (or simply direct that last DSE pass do that, with some pass specific
flag).  Note that's still too late since we need store-motion here.

Doing the *ssaname_N ={v} {CLOBBER} clobber removal after the _first_
DSE after IPA inlining would be another option.  Likewise of course
removing it as part of SM as said above.

I can see how easy it is to do from store-motion.

[Bug tree-optimization/104515] [11/12 Regression] trivially-destructible destructors interfere with loop optimization - maybe related to lifetime-dse.

[gcc at rabensky dot com]

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

--- Comment #2 from GBE <gcc at rabensky dot com> ---
I don't know if it helps - but I used git-bisect to find the original commit
that added this issue: cdc184174ce

https://github.com/gcc-mirror/gcc/commit/cdc184174ce

It indeed has to do with trivial destructors and clobber and lifetime-dse, so
that confirms it.

It's a fairly small commit - but it's beyond my knowledge of the codebase to
understand it.

I hope it's helpful!

[Bug tree-optimization/104515] [11/12 Regression] trivially-destructible destructors interfere with loop optimization - maybe related to lifetime-dse.

[redi at gcc dot gnu.org]

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

--- Comment #3 from Jonathan Wakely <redi at gcc dot gnu.org> ---
aka r9-84-gcdc184174ce56d

[Bug tree-optimization/104515] [11/12 Regression] trivially-destructible destructors interfere with loop optimization - maybe related to lifetime-dse.

[gcc at rabensky dot com]

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

--- Comment #4 from GBE <gcc at rabensky dot com> ---
The commit that make this issue affect "basic types" as well:

https://gcc.gnu.org/git/gitweb.cgi?p=gcc.git;h=e443d821386

[Bug tree-optimization/104515] [11/12 Regression] trivially-destructible destructors interfere with loop optimization - maybe related to lifetime-dse.

[rguenth at gcc dot gnu.org]

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

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

           What    |Removed                     |Added
----------------------------------------------------------------------------
   Target Milestone|11.3                        |11.4

--- Comment #5 from Richard Biener <rguenth at gcc dot gnu.org> ---
GCC 11.3 is being released, retargeting bugs to GCC 11.4.

[Bug tree-optimization/104515] [11/12/13 Regression] trivially-destructible destructors interfere with loop optimization - maybe related to lifetime-dse.

[rguenth at gcc dot gnu.org]

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

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

           What    |Removed                     |Added
----------------------------------------------------------------------------
                 CC|                            |pshevchuk at pshevchuk dot com

--- Comment #6 from Richard Biener <rguenth at gcc dot gnu.org> ---
*** Bug 109486 has been marked as a duplicate of this bug. ***

[Bug tree-optimization/104515] [11/12/13 Regression] trivially-destructible destructors interfere with loop optimization - maybe related to lifetime-dse.

[rguenth at gcc dot gnu.org]

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

--- Comment #7 from Richard Biener <rguenth at gcc dot gnu.org> ---
(In reply to Richard Biener from comment #1)
> Confirmed.  The issue is that store motion of v_7(D)->end cannot be
> performed on
> 
>   <bb 3> [local count: 955630225]:
>   # i_13 = PHI <i_10(6), 0(5)>
>   _1 = v_7(D)->end;
>   _2 = _1 + 18446744073709551612;
>   v_7(D)->end = _2;
>   MEM[(T *)_1 + -4B] ={v} {CLOBBER};   // <- inserted by -flifetime-dse
>   i_10 = i_13 + 1;
>   if (n_6(D) > i_10)
>     goto <bb 6>; [89.00%]
>   else
>     goto <bb 4>; [11.00%]
> 
>   <bb 6> [local count: 850510901]:
>   goto <bb 3>; [100.00%]

It's possible to perform store-motion of the above as the following,
preserving the CLOBBER in the loop but necessarily re-issueing the
last iteration CLOBBER on the exit edge.  I _think_ that's fine to do.
The oacc-kernels pipeline does LIM quite early before IPA.  For the
later LIM passes we might as well go with eliminating the non-decl
CLOBBERs earlier - but the issue also exists for decl CLOBBERs of course.

Note duplicating "lifetime" CLOBBERs might prove bad (we only have EOL
clobbers right now).

  <bb 3> [local count: 955630225]:
  # i_13 = PHI <i_10(6), 0(5)>
  # v__end_lsm.3_4 = PHI <v__end_lsm.3_12(6), v__end_lsm.3_3(5)>
  _1 = v__end_lsm.3_4;
  _2 = _1 + 18446744073709551612;
  v__end_lsm.3_12 = _2;
  MEM[(int *)_1 + -4B] ={v} {CLOBBER};
  i_10 = i_13 + 1;
  if (n_6(D) > i_10)
    goto <bb 6>; [89.00%]
  else
    goto <bb 7>; [11.00%]

  <bb 6> [local count: 850510901]:
  goto <bb 3>; [100.00%]

  <bb 7> [local count: 105119324]:
  # _17 = PHI <_1(3)>
  # v__end_lsm.3_19 = PHI <v__end_lsm.3_12(3)>
  v_7(D)->end = v__end_lsm.3_19;
  MEM[(int *)_17 + -4B] ={v} {CLOBBER};

  <bb 4> [local count: 118111600]:
  return;

[Bug tree-optimization/104515] [11/12/13/14 Regression] trivially-destructible destructors interfere with loop optimization - maybe related to lifetime-dse.

[jakub at gcc dot gnu.org]

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

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

           What    |Removed                     |Added
----------------------------------------------------------------------------
   Target Milestone|11.4                        |11.5

--- Comment #8 from Jakub Jelinek <jakub at gcc dot gnu.org> ---
GCC 11.4 is being released, retargeting bugs to GCC 11.5.

[Bug tree-optimization/104515] [11/12/13/14/15 Regression] trivially-destructible destructors interfere with loop optimization - maybe related to lifetime-dse.

[rguenth at gcc dot gnu.org]

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

--- Comment #9 from Richard Biener <rguenth at gcc dot gnu.org> ---
I think not re-emitting the clobber on the exit might be OK semantically - it's
at most a missed optimization for a store.  I think it's also OK for the
stack slot sharing logic as any object becoming live after a clobber
would need to have a mention inbetween the clobber and the exit.  I'll note
that if that's not OK then duplicating the clobber wouldn't either.
As we don't know whether the object we store to ends its lifetime (it's only
a may-alias) we can't do both - extend its lifetime and preserve the
original one.

We could maybe move the clobber (duplicating it to each edge but removing
it from the loop body).

I'm testing a patch.

[Bug tree-optimization/104515] [11/12/13/14/15 Regression] trivially-destructible destructors interfere with loop optimization - maybe related to lifetime-dse.

[rguenth at gcc dot gnu.org]

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

--- Comment #10 from Richard Biener <rguenth at gcc dot gnu.org> ---
Testcase from PR96717, also fixed with my patch in testing.

#include <vector>

void pop_many(std::vector<int>& v, unsigned n) {
    for (unsigned i = 0; i < n; ++i) {
        v.pop_back();
    }
}

[Bug tree-optimization/104515] [11/12/13/14/15 Regression] trivially-destructible destructors interfere with loop optimization - maybe related to lifetime-dse.

[cvs-commit at gcc dot gnu.org]

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

--- Comment #11 from GCC 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:8c67dc40459e3d72e8169b099cc8c5dbdb759da3

commit r15-2133-g8c67dc40459e3d72e8169b099cc8c5dbdb759da3
Author: Richard Biener <rguenther@suse.de>
Date:   Wed Jul 17 10:22:47 2024 +0200

    tree-optimization/104515 - store motion and clobbers

    The following addresses an old regression when end-of-object/storage
    clobbers were introduced.  In particular when there's an end-of-object
    clobber in a loop but no corresponding begin-of-object we can still
    perform store motion of may-aliased refs when we re-issue the
    end-of-object/storage on the exits but elide it from the loop.  This
    should be the safest way to deal with this considering stack-slot
    sharing and it should not cause missed dead store eliminations given
    DSE can now follow multiple paths in case there are multiple exits.

    Note when the clobber is re-materialized only on one exit but not
    on anther we are erroring on the side of removing the clobber on
    such path.  This should be OK (removing clobbers is always OK).

    Note there's no corresponding code to handle begin-of-object/storage
    during the hoisting part of loads that are part of a store motion
    optimization, so this only enables stored-only store motion or cases
    without such clobber inside the loop.

            PR tree-optimization/104515
            * tree-ssa-loop-im.cc (execute_sm_exit): Add clobbers_to_prune
            parameter and handle re-materializing of clobbers.
            (sm_seq_valid_bb): end-of-storage/object clobbers are OK inside
            an ordered sequence of stores.
            (sm_seq_push_down): Refuse to push down clobbers.
            (hoist_memory_references): Prune clobbers from the loop body
            we re-materialized on an exit.

            * g++.dg/opt/pr104515.C: New testcase.

[Bug tree-optimization/104515] [11/12/13/14 Regression] trivially-destructible destructors interfere with loop optimization - maybe related to lifetime-dse.

[rguenth at gcc dot gnu.org]

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

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

           What    |Removed                     |Added
----------------------------------------------------------------------------
      Known to work|                            |15.0
            Summary|[11/12/13/14/15 Regression] |[11/12/13/14 Regression]
                   |trivially-destructible      |trivially-destructible
                   |destructors interfere with  |destructors interfere with
                   |loop optimization - maybe   |loop optimization - maybe
                   |related to lifetime-dse.    |related to lifetime-dse.

--- Comment #12 from Richard Biener <rguenth at gcc dot gnu.org> ---
This has been fixed for GCC 15, it's unlikely backported but I'll leave this
open for tracking purposes.

[Bug tree-optimization/104515] [12/13/14 Regression] trivially-destructible destructors interfere with loop optimization - maybe related to lifetime-dse.

[rguenth at gcc dot gnu.org]

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

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

           What    |Removed                     |Added
----------------------------------------------------------------------------
   Target Milestone|11.5                        |12.5

--- Comment #13 from Richard Biener <rguenth at gcc dot gnu.org> ---
GCC 11 branch is being closed.