[Bug tree-optimization/110057] New: Missed devirtualization opportunities

[Bug tree-optimization/110057] New: Missed devirtualization opportunities

[yongxiangng at gmail dot com]

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

            Bug ID: 110057
           Summary: Missed devirtualization opportunities
           Product: gcc
           Version: 14.0
            Status: UNCONFIRMED
          Severity: normal
          Priority: P3
         Component: tree-optimization
          Assignee: unassigned at gcc dot gnu.org
          Reporter: yongxiangng at gmail dot com
  Target Milestone: ---

There are some missed devirtualization opportunities involving vectors. The
issue is discussed in the stackoverflow here.

https://stackoverflow.com/questions/73257739/missed-optimization-stdvectortpop-back-not-qualifying-destructor-call/

Because we know the type of the objects in the vector (they have to be _Tp),
there is no need to invoke the virtual methods and we can devirtualize them. I
believe this applies not just to the destructor, but also other member
functions.

This missed optimization does not only affect vector. When creating an array,
the virtual destructor is invoked even though it should be quite clear to the
compiler that it can resolve the type of the object in the array at compile
time.

There is a possibility of using placement new and "spoofing" the type
https://godbolt.org/z/3MdMsdKha (thanks Jonathan Wakely), but I'm not sure if
this is legal c++ and if this applies to raw arrays

I think this might be a problem with the IPA component, I might have
mislabelled the issue because there isn't an option for IPA. Please let me know
if this makes sense or I have some misconception.

A sample program that shows this behavior is below.

/* { dg-do run } */
/* Virtual calls should be devirtualized because we know dynamic type of object
in vector at compile time */
/* { dg-options "-O3 -fdump-tree-ssa"  } */

#include <vector>

using std::vector;

class A {
public:
    virtual ~A()
    {

    }
};

class B  : public A
{
public:
    virtual ~B()
    {

    }
};

int main()
{
    vector<B> arr;
//    B b[40];
    return 0;
}

/* { dg-final { scan-tree-dump-times "OBJ_TYPE_REF" 0 "ssa"} } */

[Bug ipa/110057] Missed devirtualization opportunities

[pinskia at gcc dot gnu.org]

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

--- Comment #1 from Andrew Pinski <pinskia at gcc dot gnu.org> ---
I don't think it should be checking ssa dump (which is the output right after
going into ssa mode) but rather optimized.

[Bug ipa/110057] Missed devirtualization opportunities

[pinskia at gcc dot gnu.org]

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

--- Comment #2 from Andrew Pinski <pinskia at gcc dot gnu.org> ---
I am not 100% sure the all of the objects in the vector<C> has to be in type of
C. Because you could do some tricks dealing with inplacement new.

>if this applies to raw arrays

It does applies to raw arrays.

[Bug ipa/110057] Missed devirtualization opportunities

[yongxiangng at gmail dot com]

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

--- Comment #3 from Ng YongXiang <yongxiangng at gmail dot com> ---
I'm giving the example of an array for now, because gcc treatment of the
destructor is inconsistent and depends on the length of the array. Clang on the
other hand is able to devirtualize the destructor in the array no matter the
length of the array.

Virtual call

https://godbolt.org/z/f33Gh5EGM

Devirtualized call

https://godbolt.org/z/jPz3Ka1cd

We know it is devirtualized because the destructor of the derived object is not
called and the compiler assumes that the items in the array are all Base
objects.

So currently, gcc does perform this kind of "devirtualization" (I wouldn't
really call it a devirtualization for an array, because it is similar to
declaring Derived d; on the stack), but it is dependent on array length, and I
think we should make it devirtualized for all length of array.

I changed my testing to dump tree optimized like below (let me know if there's
issues with the example because I am not familiar with hacking gcc).

/* { dg-do run } */
/* Virtual calls should be devirtualized because we know dynamic type of object
in vector at compile time */
/* { dg-options "-O3 -fdump-tree-optimized -fno-inline"  } */

#include <vector>
#include <iostream>
#include <memory>

using std::vector;

class A
{
public:
    virtual ~A()
    {
    }
};

class B : public A
{
public:
    virtual ~B()
    {
    }
};

int main()
{
    B b[3];
    return 0;
}

/* { dg-final { scan-tree-dump-times "OBJ_TYPE_REF" 0 "optimized"} } */

[Bug ipa/110057] Missed devirtualization opportunities

[yongxiangng at gmail dot com]

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

--- Comment #4 from Ng YongXiang <yongxiangng at gmail dot com> ---
Would anyone be able to direct me to which portion of the code is responsible
for this threshold between len 2 & 3 array? Is this the responsibility of the
c++ frontend? or is it still related to the optimizer.

[Bug ipa/110057] Missed devirtualization opportunities

[pinskia at gcc dot gnu.org]

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

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

           What    |Removed                     |Added
----------------------------------------------------------------------------
           See Also|                            |https://gcc.gnu.org/bugzill
                   |                            |a/show_bug.cgi?id=80899

--- Comment #5 from Andrew Pinski <pinskia at gcc dot gnu.org> ---
(In reply to Ng YongXiang from comment #4)
> Would anyone be able to direct me to which portion of the code is
> responsible for this threshold between len 2 & 3 array? Is this the
> responsibility of the c++ frontend? or is it still related to the optimizer.

The front-end has nothing to do with the difference between 2 and 3. The
difference between 2 and 3 is unrolling of the loop in the optimizers. See bug
109770 and bug 80899 for other cases of inplacement new causing issues.

[Bug ipa/110057] Missed devirtualization opportunities

[yongxiangng at gmail dot com]

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

--- Comment #6 from Ng YongXiang <yongxiangng at gmail dot com> ---
That is interesting. Thanks for the reply.

However, I'd argue that the 2 bugs mentioned are different from what I am
proposing. The 2 bugs linked access virtual functions via ptr (delete p;
val->f();) and are invoked by the user directly, and so I think it makes sense
for the compiler to access the vtable. 

However, the array issue I'm putting forth is caused by the destruction of the
array with automatic storage duration, and the destruction code is generated by
the compiler not by the user via some kind of ptr or reference.

Moreover, clang does it right and devirtualizes the destruction of the array
while gcc still doesn't.

https://godbolt.org/z/f33Gh5EGM

#include <iostream>
#include <memory>

struct A
{
    A()
    {
        std::cout << "A()" << std::endl;
    }
    virtual ~A() 
    {
        std::cout << "~A()" << std::endl;
    }
};

struct B : public  A
{
    B()
    {
        std::cout << "B()" << std::endl;
    }
    virtual ~B()
    {
        std::cout << "~B()" << std::endl;
    }
};

int main()
{
    A a[3];
    a[0].~A();
    :: new(std::addressof(a[0])) B();
}

[Bug ipa/110057] Missed devirtualization opportunities

[yongxiangng at gmail dot com]

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

Ng YongXiang <yongxiangng at gmail dot com> changed:

           What    |Removed                     |Added
----------------------------------------------------------------------------
                 CC|                            |yongxiangng at gmail dot com

--- Comment #7 from Ng YongXiang <yongxiangng at gmail dot com> ---
Created attachment 55256
  --> https://gcc.gnu.org/bugzilla/attachment.cgi?id=55256&action=edit
Arrays should do non virtual lookup when destructing individual elements

This is a draft patch outlining a possible solution to call non virtual
destructor of elements when arrays are destructed (clang already does this, see
https://godbolt.org/z/f33Gh5EGM).

[Bug ipa/110057] Missed devirtualization opportunities

[yongxiangng at gmail dot com]

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

--- Comment #8 from Ng YongXiang <yongxiangng at gmail dot com> ---
Just added a patch to illustrate the array destruction issue. What do you
think?

[Bug ipa/110057] Missed devirtualization opportunities

[yongxiangng at gmail dot com]

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

--- Comment #9 from Ng YongXiang <yongxiangng at gmail dot com> ---
Would anyone be willing to provide some feedback regarding the attachment
(https://gcc.gnu.org/bugzilla/attachment.cgi?id=55256&action=diff) that I have
created? Thanks.

[Bug ipa/110057] Missed devirtualization opportunities

[cvs-commit at gcc dot gnu.org]

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

--- Comment #10 from CVS Commits <cvs-commit at gcc dot gnu.org> ---
The trunk branch has been updated by Jason Merrill <jason@gcc.gnu.org>:

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

commit r14-2853-ga47e615fbf9c6f4b24e5032df5d720b6bf9b63b5
Author: Ng YongXiang <yongxiangng@gmail.com>
Date:   Thu Jul 27 08:06:14 2023 +0800

    c++: devirtualization of array destruction [PR110057]

            PR c++/110057
            PR ipa/83054

    gcc/cp/ChangeLog:

            * init.cc (build_vec_delete_1): Devirtualize array destruction.

    gcc/testsuite/ChangeLog:

            * g++.dg/warn/pr83054.C: Remove devirtualization warning.
            * g++.dg/lto/pr89335_0.C: Likewise.
            * g++.dg/tree-ssa/devirt-array-destructor-1.C: New test.
            * g++.dg/tree-ssa/devirt-array-destructor-2.C: New test.
            * g++.dg/warn/pr83054-2.C: New test.

    Signed-off-by: Ng Yong Xiang <yongxiangng@gmail.com>

[Bug ipa/110057] Missed devirtualization opportunities

[pinskia at gcc dot gnu.org]

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

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

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

[Bug ipa/110057] Missed devirtualization opportunities

[user202729 at protonmail dot com]

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

user202729 <user202729 at protonmail dot com> changed:

           What    |Removed                     |Added
----------------------------------------------------------------------------
                 CC|                            |user202729 at protonmail dot com

--- Comment #11 from user202729 <user202729 at protonmail dot com> ---
One way this could be implemented is the following.

* implement built-in `__builtin_vptr(object)` and `__builtin_vptr(Type)` that
obtains the pointer to the vtable (or NULL if the object type has no virtual
method)
* in the implementation `vector.pop_back()` etc., add the the following:

    if (__builtin_vptr(this->_M_impl._M_finish) != __builtin_vptr(_Tp))
      __builtin_unreachable();

* the optimizer should be able to figure out the rest.

What do you think about this approach?

--------

Alternatively, we can also use the existing `typeid()` --- although the
optimizer is not smart enough to optimize the following code yet.

```
#include<cstdio>
#include<typeinfo>
struct Base{
    Base() {}
    virtual void f(){ std::printf("Base\n"); }
};
struct Derived final: Base{
    Derived() {}
    virtual void f(){ std::printf("Derived\n"); }
};
void f(Base* b){
    if(!b or typeid(*b)!=typeid(Base)) __builtin_unreachable();
    b->f();
}
```