[Bug middle-end/58585] New: [4.9 Regression] ICE in ipa with virtual inheritance

[Bug middle-end/58585] New: [4.9 Regression] ICE in ipa with virtual inheritance

[reichelt at gcc dot gnu.org]

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

            Bug ID: 58585
           Summary: [4.9 Regression] ICE in ipa with virtual inheritance
           Product: gcc
           Version: 4.9.0
            Status: UNCONFIRMED
          Severity: normal
          Priority: P3
         Component: middle-end
          Assignee: unassigned at gcc dot gnu.org
          Reporter: reichelt at gcc dot gnu.org

The following valid code snippet triggers an ICE on trunk when compiled with
"-O2 -fPIC":

================================
struct A
{
  virtual void foo() {}
  void bar();
};
void A::bar() { foo(); }

struct B : virtual A
{
  virtual void foo() {}
  char c;
};

struct C : virtual B
{
  C();
};
C::C() { bar(); }
================================

bug.cc:18:17: internal compiler error: in ipa_get_indirect_edge_target_1, at
ipa-cp.c:1570
 C::C() { bar(); }
                 ^
0xf46f8d ipa_get_indirect_edge_target_1
        ../../gcc/gcc/ipa-cp.c:1569
0x9958fe estimate_edge_devirt_benefit
        ../../gcc/gcc/ipa-inline-analysis.c:2783
0x9958fe estimate_edge_size_and_time
        ../../gcc/gcc/ipa-inline-analysis.c:2815
0x9958fe estimate_calls_size_and_time
        ../../gcc/gcc/ipa-inline-analysis.c:2868
0x996a72 estimate_node_size_and_time
        ../../gcc/gcc/ipa-inline-analysis.c:2955
0x999046 do_estimate_edge_size(cgraph_edge*)
        ../../gcc/gcc/ipa-inline-analysis.c:3498
0x99918c estimate_edge_size
        ../../gcc/gcc/ipa-inline.h:275
0x99918c estimate_edge_growth
        ../../gcc/gcc/ipa-inline.h:287
0x99918c do_estimate_growth_1
        ../../gcc/gcc/ipa-inline-analysis.c:3609
0x8004de cgraph_for_node_and_aliases(cgraph_node*, bool (*)(cgraph_node*,
void*), void*, bool)
        ../../gcc/gcc/cgraph.c:2156
0x999617 do_estimate_growth(cgraph_node*)
        ../../gcc/gcc/ipa-inline-analysis.c:3623
0xf5513d estimate_growth
        ../../gcc/gcc/ipa-inline.h:262
0xf5513d inline_small_functions
        ../../gcc/gcc/ipa-inline.c:1549
0xf5513d ipa_inline
        ../../gcc/gcc/ipa-inline.c:2009
0xf5513d execute
        ../../gcc/gcc/ipa-inline.c:2379
Please submit a full bug report, [etc.]

The regression appeared between 4.9.0-20130922 and 4.9.0-20130926.

[Bug middle-end/58585] [4.9 Regression] ICE in ipa with virtual inheritance

[hubicka at gcc dot gnu.org]

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

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

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

--- Comment #2 from Jan Hubicka <hubicka at gcc dot gnu.org> ---
Mine, thanks for the testcase!

[Bug middle-end/58585] [4.9 Regression] ICE in ipa with virtual inheritance

[hubicka at gcc dot gnu.org]

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

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

           What    |Removed                     |Added
----------------------------------------------------------------------------
                 CC|                            |jason at redhat dot com
             Blocks|                            |58252

--- Comment #3 from Jan Hubicka <hubicka at gcc dot gnu.org> ---
Thanks for nice testcase.

The problem here is that record_binfos and get_binfo_at_offset do not agree.
I think it may be the same problem as in PR58252.

Here we have class C with one (virtual) base B that has one (virtual) base A.

record_binfos starts walk in binfo of C and it looks at base B.  It passes two
binfos around.  type_binfo is binfo pointing to a virtual table to use, while
binfo is the BINFo being walked.  For non-virtual inheritance the first base
share virtual table with outer class and its BINFO has no pointer to any
vtable. So there is a conditional setting type_binfo to the base only if its
vtable is non-NULL.

Now for virtual inheritance, B have its own table defined, so we switch to B
and eventually we look into vtable assigned to A.

get_binfo_at_offset works slightly differently.  It first walks fields of the
structure identifying the field at proper offset.  If it is abstract it is
considered to represent base type.  Then if offset is non-0 it uses BINFO of
the base, while otherwise it stays on BINFO of outer type.

For the testcase get_binfo_at_offsets is called with offset 0 and it makes
lookup in the vtable pointed by BINFO of C that contains a thunk, while
record_binfos looks into vtable pointer by BINFO representing base A within C
that has directly method foo.

Obviously both functions must be made to agree.

C::C seems to be compiled as:
_ZN1CC1Ev:
.LFB12: 
        .cfi_startproc
        .cfi_personality 0x3,__gxx_personality_v0
        movq    _ZTT1C+24(%rip), %rax
        movq    _ZTT1C+32(%rip), %rdx
        movq    -32(%rax), %rax
        movq    %rdx, 8(%rdi,%rax)
        movq    $_ZTV1C+88, 8(%rdi)
        movq    $_ZTV1C+40, (%rdi)
        movq    _ZTV1C+40(%rip), %rax
        jmp     *%rax

and
_ZTV1C: 
        .quad   0
        .quad   8
        .quad   8
        .quad   0
        .quad   _ZTI1C
        .quad   _ZTv0_n24_N1B3fooEv

so we really call thunk here and probably record_binfos is incorrect.  I can
fix it by also waking fields and handling fields at offset 0 specially, but I
would hope there is direct way how to do so via BASE_BINFOs walk....

I tried to change conditional in record_binfos to only switch type_binfo if 
BINFO_OFFSET != 0, but in this case it is 8. This also seems incorect to me...

Jason, any ideas about the proper fix?

Honza

[Bug middle-end/58585] [4.9 Regression] ICE in ipa with virtual inheritance

[hubicka at gcc dot gnu.org]

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

--- Comment #4 from Jan Hubicka <hubicka at gcc dot gnu.org> ---
This is the code I am playing with:
  /* Walk bases.  */
  for (i = 0; BINFO_BASE_ITERATE (binfo, i, base_binfo); i++)
    /* Walking bases that have no virtual method is pointless excercise.  */
    if (polymorphic_type_binfo_p (base_binfo))
      record_binfo (nodes, base_binfo, otr_type,
                    /* In the case of single inheritance, the virtual table
                       is shared with the outer type.  */
                    BINFO_OFFSET_ZEROP (base_binfo)
                    ? type_binfo : base_binfo,
                    otr_token, inserted,
                    matched_vtables, anonymous);

(i.e. using BINFO_OFFSET_ZEROP check instead of BINFO_VTABLE != NULL).

I think I understand the problem now.  The binfos of C looks like

  BINFO of C, BINFO vtable is C's vtable
  BASE:
    BINFO of B, BINFO vtable is non-NULL, offset is 8
    BASE:
      BINFO of A, BINFO vtable is non-NULL, offset is 0.

i.e. by the virtual inheritance the A is outside layout of B. So while B's
VTABLE is set, A's VTABLE should be VTABLE of C, my code however considers
VTABLE of B.

get_binfo_at_offset won't get confused, since type of C contains both A and B
as fields, so it gets to BINFO of A directly without walking BINFO of B.

Is there way how to keep track of the vtables w/o doing the walk based on
fields instead of BINFO_BASEs? If not, I will simply switch record_binfos to it
- it seems quite straighforward, but it will end up with more walking, since
there are more fileds than bases.

[Bug middle-end/58585] [4.9 Regression] ICE in ipa with virtual inheritance

[hubicka at ucw dot cz]

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

--- Comment #6 from Jan Hubicka <hubicka at ucw dot cz> ---
> > Is there way how to keep track of the vtables w/o doing the walk based on
> > fields instead of BINFO_BASEs?
> 
> There should be.  Your code change makes sense to me; a primary base will
> always be at offset 0, and from the comment those are the only ones we want to
> walk into.

It does not fix the problem, unfortunately.  This is what happens:

  1) we call record_binfo, binfo points to TYPE_BINFO of C and type_binfo
points to TYPE_BINFO of C
  2) record_binfo calls itself on base of C (that is B).
     both binfo and type_binfo gets updated to base_binfo (that is of type B)
     because BINFO_OFFSET is 8
  3) record_binfo calls itslf on base of B (that is A)
     this time BINOF_OFFSET is 0, so type_binfo ends up to be one of type B,
     but we want one of type A.

So in short the problem is that binfos represent the hiearchy 
  C
  |
  B
  |
  A

but only A and C have offset 0 (within C). Walking fields represents a hiearchy

     C
    / \
   A   B
       |
       A

I tried to modify the code to always keep type_binfo to be the binfo of the
type walked,
but that does not work always either.  (it fails when one has multiple
inheritance and
the second base has another base)

I think only way to retrieve BINFO with vtable I want to walk is to walk up in
the recursion chain and look if there is already BINFO with identical offset I
am seeing.  This is bit unhandy (one would have to manage the whole recursion
stack of binfos) and may be easier to just immitate what get_binfo_at_offset
does...

I may be missing something obvious...

[Bug middle-end/58585] [4.9 Regression] ICE in ipa with virtual inheritance

[jason at gcc dot gnu.org]

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

--- Comment #7 from Jason Merrill <jason at gcc dot gnu.org> ---
(In reply to Jan Hubicka from comment #6)
> It does not fix the problem, unfortunately.  This is what happens:

Ah, right.  We don't have an A binfo in C's base list.

I believe you can distinguish this case by looking at the
BINFO_INHERITANCE_CHAIN of the A binfo; in this case, it should point back to C
rather than to B because A is a primary base of C and not of B-in-C.

[Bug middle-end/58585] [4.9 Regression] ICE in ipa with virtual inheritance

[hubicka at ucw dot cz]

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

--- Comment #8 from Jan Hubicka <hubicka at ucw dot cz> ---
> Ah, right.  We don't have an A binfo in C's base list.
> 
> I believe you can distinguish this case by looking at the
> BINFO_INHERITANCE_CHAIN of the A binfo; in this case, it should point back to C
> rather than to B because A is a primary base of C and not of B-in-C.

BINFO_INHERITANCE_CHAIN is cleared by free_lang_data, so it is not available to
me.
It would not be hard to change this and add streaming of this pointer.  

I have bit problem to interpret the comment:

/* The BINFO_INHERITANCE_CHAIN points at the binfo for the base
   inheriting this base for non-virtual bases. For virtual bases it
   points either to the binfo for which this is a primary binfo, or to
   the binfo of the most derived type.  */

So basically given a BINFO I walk I can look at BINFO_INHERITANCE_CHAIN and if
my offset is the same as offset of BINFO_INHERITANCE_CHAIN I will take its
virtual table and if not, I will take virutal table of BINFO that will always
be non-NULL?

Will this work in a case of non-virtual multiple inheritance? I.e

       A
      / \
     B  C
       / \
      D   E
where I think A+B share vtable and C+D share vtable?
I need D BINFO_INHERITANCE_CHAIN to point to C instead of A, but in the case of
virtual inheritance I need it to point to A instead of C.

It is not big deal to change record_binfos to walk the fields
instead of base list and perhaps it would end up being easier than the above. 
However I am not sure about get_binfo_at_offset implementation either.  it does

1) walk fields and find corresponding filed
2)  a) if field is not artificial  then it switches to new binfo
   otherwise:
    b) if offset is non-0 it walks bases to look up BINFO corresponding to the
field.

What will hapen in the case of multiple virtual inheritance? Assume the example
above has all bases virtual.  Here I think D will be field of A with non-0
offset
but it will not be in list of bases of A. So I think get_binfo_at_offset will
fail
in b) and will return NULL.

I think we do not hit this problem only because devirt machinery do not
understand virtual inheritance lookup - it basically never gets into the outer
type.

Honza

[Bug middle-end/58585] [4.9 Regression] ICE in ipa with virtual inheritance

[rguenth at gcc dot gnu.org]

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

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

           What    |Removed                     |Added
----------------------------------------------------------------------------
           Priority|P3                          |P1

[Bug middle-end/58585] [4.9 Regression] ICE in ipa with virtual inheritance

[octoploid at yandex dot com]

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

Markus Trippelsdorf <octoploid at yandex dot com> changed:

           What    |Removed                     |Added
----------------------------------------------------------------------------
                 CC|                            |octoploid at yandex dot com

--- Comment #9 from Markus Trippelsdorf <octoploid at yandex dot com> ---
Jason, can you address Honza's questions from comment 8 please?

This issue breaks many C++ projects and makes testing impossible.

[Bug middle-end/58585] [4.9 Regression] ICE in ipa with virtual inheritance

[hubicka at gcc dot gnu.org]

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

--- Comment #10 from Jan Hubicka <hubicka at gcc dot gnu.org> ---
Seems we got stuck on solving the virtual vtable representation issues.  Here
are some of my experiments.

I think we have two problems, the first one is manifested by this testcase.
Here record_targets_from_binfo is not able to work out proper vtable
associated with a call.  Martin pointed out to me that C++ FE uses BINFO_FLAG_2
to mark binfos for which it generated vtable.  This seems to help this testcase
(w/o LTO, since we do not stream it)

Index: ipa-devirt.c
===================================================================
--- ipa-devirt.c        (revision 205941)
+++ ipa-devirt.c        (working copy)
@@ -679,7 +679,7 @@
                                /* In the case of single inheritance,
                                   the virtual table is shared with
                                   the outer type.  */
-                               BINFO_VTABLE (base_binfo) ? base_binfo :
type_binfo,
+                               BINFO_FLAG_2 (base_binfo) && BINFO_VTABLE
(base_binfo) ? base_binfo : type_binfo,
                                otr_token, outer_type, offset, inserted,
                                matched_vtables, anonymous);
 }

I am not happy that I need BINFO_VTABLE flag, too. Apparently sometimes C++ FE
marks even binfos that do not have vtable with them.
Jason, does this seem at all some sense?

[Bug middle-end/58585] [4.9 Regression] ICE in ipa with virtual inheritance

[hubicka at gcc dot gnu.org]

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

--- Comment #11 from Jan Hubicka <hubicka at gcc dot gnu.org> ---
Created attachment 31762
  --> http://gcc.gnu.org/bugzilla/attachment.cgi?id=31762&action=edit
Proposed fix

Hi,
this patch makes us to look harder for correct virtual table.  I walk the stack
of binfos with vtables and find first one with matching offset.  If I
understand thigns right, that should be always the binfo that holds the valid
vtable, since these are shared.
I will probably need to dive into C++ ABI to double check it.

[Bug middle-end/58585] [4.9 Regression] ICE in ipa with virtual inheritance

[hubicka at gcc dot gnu.org]

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

--- Comment #12 from Jan Hubicka <hubicka at gcc dot gnu.org> ---
Created attachment 31763
  --> http://gcc.gnu.org/bugzilla/attachment.cgi?id=31763&action=edit
Proposed fix 2

It turns out that in the case of multiple inheritance we may miss vtables on
certain paths when it is duplicated binfo for shared base.  This patch won't
ICE in this case.

[Bug middle-end/58585] [4.9 Regression] ICE in ipa with virtual inheritance

[trippels at gcc dot gnu.org]

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

Markus Trippelsdorf <trippels at gcc dot gnu.org> changed:

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

--- Comment #13 from Markus Trippelsdorf <trippels at gcc dot gnu.org> ---
(In reply to Jan Hubicka from comment #12)
> Created attachment 31763 [details]
> Proposed fix 2
> 
> It turns out that in the case of multiple inheritance we may miss vtables on
> certain paths when it is duplicated binfo for shared base.  This patch won't
> ICE in this case.

Doesn't (LTO/PGO) bootstrap:
lto1: internal compiler error: in hash_type_name, at ipa-devirt.c:225

[Bug middle-end/58585] [4.9 Regression] ICE in ipa with virtual inheritance

[trippels at gcc dot gnu.org]

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

--- Comment #14 from Markus Trippelsdorf <trippels at gcc dot gnu.org> ---
Hmm,

markus@x4 gcc % cat test.ii
class A {
  void m();
};
void A::m() {}

markus@x4 gcc % /var/tmp/gcc_build_dir_/./prev-gcc/xg++
-B/var/tmp/gcc_build_dir_/./prev-gcc/ -r -nostdlib -flto -O2 -pipe test.ii
lto1: internal compiler error: in hash_type_name, at ipa-devirt.c:225

[Bug middle-end/58585] [4.9 Regression] ICE in ipa with virtual inheritance

[hubicka at ucw dot cz]

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

--- Comment #15 from Jan Hubicka <hubicka at ucw dot cz> ---
> markus@x4 gcc % cat test.ii
> class A {
>   void m();
> };
> void A::m() {}
> 
> markus@x4 gcc % /var/tmp/gcc_build_dir_/./prev-gcc/xg++
> -B/var/tmp/gcc_build_dir_/./prev-gcc/ -r -nostdlib -flto -O2 -pipe test.ii
> lto1: internal compiler error: in hash_type_name, at ipa-devirt.c:225

Grr, ignore the first hunks replacing DECL_VIRTUAL_P.  I added them for
separate
issue (related one though - it happens when you have method virtually
inheriting methods
with virtual calls that is not polymorphic by itself.  I will need to figure
out
separate fix for it).  I am at meeting now, will prepare updated patch
afterwards.

Honza

[Bug middle-end/58585] [4.9 Regression] ICE in ipa with virtual inheritance

[hubicka at gcc dot gnu.org]

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

--- Comment #16 from Jan Hubicka <hubicka at gcc dot gnu.org> ---
Created attachment 31766
  --> http://gcc.gnu.org/bugzilla/attachment.cgi?id=31766&action=edit
Proposed fix 3

Hi,
it is still lightly tested due lack of time, but fixes the previous issue with
missing vtable.

[Bug middle-end/58585] [4.9 Regression] ICE in ipa with virtual inheritance

[hubicka at gcc dot gnu.org]

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

--- Comment #17 from Jan Hubicka <hubicka at gcc dot gnu.org> ---
The patch seems to work and it seems to give correct answers for various cases
of multiple inheritance I can think of.  I would welcome testing on the
original sources and if it looks fine, I will go ahead with it.

Honza

[Bug middle-end/58585] [4.9 Regression] ICE in ipa with virtual inheritance

[trippels at gcc dot gnu.org]

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

--- Comment #18 from Markus Trippelsdorf <trippels at gcc dot gnu.org> ---
(In reply to Jan Hubicka from comment #17)
> The patch seems to work and it seems to give correct answers for various
> cases of multiple inheritance I can think of.  I would welcome testing on
> the original sources and if it looks fine, I will go ahead with it.

FWIW I've tested your patch with Firefox (PGO/LTO), Chromium 
and Boost. And everything works fine...

[Bug middle-end/58585] [4.9 Regression] ICE in ipa with virtual inheritance

[hubicka at gcc dot gnu.org]

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

--- Comment #19 from Jan Hubicka <hubicka at gcc dot gnu.org> ---
Fix for PR58252 and PR59226 fixed first two problems contributing to the ICE on
the testcase.  The last remaining problem is that our type inheritance graph is
incomplete, it misses the class C.

The reason is that I build the graph by looking for virtual methods and adding
their types.  C has no virtual methods per se, but it does use thunk of A's
constructor. This thunk is considered, but it does not have type of C that I
think is a frontend bug.

The patch I attached fixes it by considering also non-virtual methods to build
the graph. This matches the constructor of C and gets testcase working, but I
think it is symptomatic fix and may break if ctor is optimized out with LTO.
I am looking into a safer way to discover existence of C.

[Bug middle-end/58585] [4.9 Regression] ICE in ipa with virtual inheritance

[hubicka at gcc dot gnu.org]

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

--- Comment #20 from Jan Hubicka <hubicka at gcc dot gnu.org> ---
Looking even deeper, there are two problems.  The first is that we miss C in
type hiearchy graph.

C however may be defined in other unit. We do mistake already while walking B. 
There are two variants of B::foo.  One when base A is non-virtual and other
when it is virtual.

B's vtable is:
_ZTV1C: 
        .quad   0
        .quad   8
        .quad   8
        .quad   0
        .quad   _ZTI1C
        .quad   _ZTv0_n24_N1B3fooEv
        .quad   -8
        .quad   0
        .quad   -8
        .quad   _ZTI1C
        .quad   _ZN1B3fooEv

Our walking logic misses the fact that descendands of B may use the thunk
instead of FOO based on presence of virtual inheritance.

I suppose for complete correctness I would have to add code associating methods
with their virtual thunks and lookup the thunks when walking B and knowng that
I am interested in the derived types.

Simpler solution solving both problems practically is probably to simply walk
known vtables and insert their types to the type hiearchy: all internal
devirtualizations will be correct and all the missed calls to thunk from vtable
of type defined externally are harmless: the visibility code already makes all
the assumption that the call can happen.

[Bug middle-end/58585] [4.9 Regression] ICE in ipa with virtual inheritance

[hubicka at gcc dot gnu.org]

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

--- Comment #21 from Jan Hubicka <hubicka at gcc dot gnu.org> ---
Author: hubicka
Date: Fri Jan 10 21:34:37 2014
New Revision: 206543

URL: http://gcc.gnu.org/viewcvs?rev=206543&root=gcc&view=rev
Log:

    PR ipa/58585
    * ipa-devirt.c (build_type_inheritance_graph): Also add types of vtables
    into the type inheritance graph.

    * g++.dg/torture/pr58585.C: New testcase.

Added:
    trunk/gcc/testsuite/g++.dg/torture/pr58585.C
Modified:
    trunk/gcc/ChangeLog
    trunk/gcc/ipa-devirt.c
    trunk/gcc/testsuite/ChangeLog

[Bug middle-end/58585] [4.9 Regression] ICE in ipa with virtual inheritance

[hubicka at gcc dot gnu.org]

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

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

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

--- Comment #22 from Jan Hubicka <hubicka at gcc dot gnu.org> ---
Fixed, finally.