[Bug tree-optimization/47316] New: devirtualize calls to virtual methods that are never further overriden

[Bug tree-optimization/47316] New: devirtualize calls to virtual methods that are never further overriden

[zsojka at seznam dot cz]

http://gcc.gnu.org/bugzilla/show_bug.cgi?id=47316

           Summary: devirtualize calls to virtual methods that are never
                    further overriden
           Product: gcc
           Version: 4.6.0
            Status: UNCONFIRMED
          Severity: enhancement
          Priority: P3
         Component: tree-optimization
        AssignedTo: unassigned@gcc.gnu.org
        ReportedBy: zsojka@seznam.cz
                CC: jamborm@gcc.gnu.org


Created attachment 22984
  --> http://gcc.gnu.org/bugzilla/attachment.cgi?id=22984
testcase

Similiar to PR46043, but the compiler itself can be able to find out there are
cases a virtual method is never overriden.

Maybe this is the original intention of the devirtualization work, but in the
case it is not, I am opening this PR.

It is quite common to have one base class and several derived classes that are
no further derived, and the hierarchy looks roughly like:

class Base {
  virtual void f1();
  virtual void f2();
  virtual void f3();
};

class A : Base {
  virtual void f1() { ... this->f3(); ... }
  virtual void f2() { ... this->f1(); ... }
};

class B : Base {
  virtual void f2() { ... this->f1(); ... }
};

void foo(A *a)
{
  ... a->f1(); ...
}

In a whole-program mode, if the compiler finds no type/variable is coming from
external calls (where there could be possibly type derived from Base/A/B), all
these cases could be devirtualized.

Attached is a simple testcase that could be devirtualized, but isn't even with:
$ g++ tstdevirt.C -O3 -fwhole-program

[Bug tree-optimization/47316] devirtualize calls to virtual methods that are never further overriden

[zsojka at seznam dot cz]

http://gcc.gnu.org/bugzilla/show_bug.cgi?id=47316

--- Comment #1 from Zdenek Sojka <zsojka at seznam dot cz> 2011-01-17 06:48:50 UTC ---
Actually better solution would be function and type attributes, hinting the
function is never overriden.

The automatic analysis wouldn't work in cases like:

std::vector<A *> vec;

if there are any library calls inside std::vector.

Attributes would also work in non-whole-program mode.

I am sorry for not thinking it through - or rather forgetting the issues it had
and opening this PR so enthusiastically.

[Bug tree-optimization/47316] devirtualize calls to virtual methods that are never further overriden

[redi at gcc dot gnu.org]

http://gcc.gnu.org/bugzilla/show_bug.cgi?id=47316

--- Comment #2 from Jonathan Wakely <redi at gcc dot gnu.org> 2011-01-17 12:02:02 UTC ---
(In reply to comment #1)
> Actually better solution would be function and type attributes, hinting the
> function is never overriden.

C++0x has override control features:

struct B {
  virtual void f() const final;
};

As I've commented on several PRs, any work in this area should be done in line
with C++0x, not with GNU-specific attributes

[Bug tree-optimization/47316] devirtualize calls to virtual methods that are never further overriden

[jamborm at gcc dot gnu.org]

http://gcc.gnu.org/bugzilla/show_bug.cgi?id=47316

--- Comment #3 from Martin Jambor <jamborm at gcc dot gnu.org> 2011-01-17 12:20:09 UTC ---
Actually, thanks for filing the bug.  Devirtualization and other
optimizations (such as struct-reorg) based on type escape analysis are
a debated issue and it is nice to know users have interest in it.

[Bug tree-optimization/47316] devirtualize calls to virtual methods that are never further overriden

[hubicka at gcc dot gnu.org]

http://gcc.gnu.org/bugzilla/show_bug.cgi?id=47316

Jan Hubicka <hubicka at gcc dot gnu.org> changed:

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

--- Comment #4 from Jan Hubicka <hubicka at gcc dot gnu.org> ---
We now support final and do this type of analyzis that will lead to
devirtualization (if final or anonymous namespace is used) or speculative
devirtualization otherwise if doing so seems win.

We still do not assume that type hiearchy is complete even with -fwhole-program
since we do allow to link with libraries that may provide their own
derivations.
We may have a flag to enable this assumption and we probably want to strenghten
analysis of what can be supplied by library.

[Bug tree-optimization/47316] devirtualize calls to virtual methods that are never further overriden

[hubicka at gcc dot gnu.org]

http://gcc.gnu.org/bugzilla/show_bug.cgi?id=47316

--- Comment #5 from Jan Hubicka <hubicka at gcc dot gnu.org> ---
The testcase provided now generates:
void foo(A*) (struct A * a)
{
  int (*__vtbl_ptr_type) () * _3;
  int (*__vtbl_ptr_type) () _4;
  int i.0_6;
  int i.1_7;
  void * PROF_9;
  int i.2_11;
  int i.3_12;

  <bb 2>:
  _3 = a_2(D)->_vptr.A;
  _4 = *_3;
  PROF_9 = [obj_type_ref] OBJ_TYPE_REF(_4;(struct A)a_2(D)->0);
  if (PROF_9 == f)
    goto <bb 3>;
  else
    goto <bb 4>;

  <bb 3>:
  i.2_11 ={v} i;
  i.3_12 = i.2_11 + -1;
  i ={v} i.3_12;
  goto <bb 5>;

  <bb 4>:
  OBJ_TYPE_REF(_4;(struct A)a_2(D)->0) (a_2(D));

  <bb 5>:
  i.0_6 ={v} i;
  i.1_7 = i.0_6 + -1;
  i ={v} i.1_7;
  return;

}

where
  PROF_9 = [obj_type_ref] OBJ_TYPE_REF(_4;(struct A)a_2(D)->0);
  if (PROF_9 == f)
    goto <bb 3>;
  else
    goto <bb 4>;

looking at it, I am not sure if we want to keep OBJ_TYPE_REF here.
It is generally ignored except for the call statements themselves.
So either we want to drop it or extend type devirtualization in the folding
machinery to work for non-calls, too.