Re: TYPE_BINFO and canonical types at LTO

[Jan Hubicka <hubicka at ucw dot cz>]

> On Tue, 18 Feb 2014, Jan Hubicka wrote:
> 
> > > > Non-ODR types born from other frontends will then need to be made to 
> > > > alias all the ODR variants that can be done by storing them into the 
> > > > current canonical type hash.
> > > > (I wonder if we want to support cross language aliasing for non-POD?)
> > > 
> > > Surely for accessing components of non-POD types, no?  Like
> > > 
> > > class Foo {
> > > Foo();
> > > int *get_data ();
> > > int *data;
> > > } glob_foo;
> > > 
> > > extern "C" int *get_foo_data() { return glob_foo.get_data(); }
> > 
> > OK, if we want to support this, then we want to merge.
> > What about types with vtbl pointer? :)
> 
> I can easily create a C struct variant covering that.  Basically
> in _practice_ I can inter-operate with any language from C if I
> know its ABI.  Do we really want to make this undefined?  See
> the (even standard) Fortran - C interoperability spec.  I'm sure
> something exists for Ada interoperating with C (or even C++).

Well, if you know the ABI, you can interoperate C
struct {int a,b;};
with
struct {struct {int a;} a; struct {int b;}};

So we don't interoperate everything.  We may eventually want to define what
kind of inter-operation we support.  non-POD class layout is not always a
natural extension of C struct layout as one would expect
http://mentorembedded.github.io/cxx-abi/abi.html#layout
so it may make sense to declare it uninteroperable if it helps something in real
world (which I am not quite sure about)

I am not really shooting for this. I just want to get something that would
improve TBAA in pre-dominantly C++ programs (with some C code in them) such as
firefox, chromium, openoffice or GCC. Because I see us giving up on TBAA very
often when playing with cases that should be devirtualized by GVN/aggregate
propagation in ipa-prop but aren't. Also given that C++ standard actually
have notion of inter-module type equivalence it may be good idea to honnor it.
> 
> > > ?  But you are talking about the "tree" merging part using ODR info
> > > to also merge types which differ in completeness of contained
> > > pointer types, right?  (exactly equal cases should be already merged)
> > 
> > Actually I was speaking of canonical types here. I want to preserve more 
> > of TBAA via honoring ODR and local types.
> 
> So, are you positive there will be a net gain in optimization when
> doing that?  Please factor in the surprises you'll get when code
> gets "miscompiled" because of "slight" ODR violations or interoperability
> that no longer works.
> 
> > I want to change lto to not 
> > merge canonical types for pairs of types of same layout (i.e. equivalent 
> > in the current canonical type definition) but with different mangled 
> > names.
> 
> Names are nothing ;)  In C I very often see different _names_ used
> in headers vs. implementation (when the implementation uses a different
> internal header).  You have struct Foo; in public headers vs.
> struct Foo_impl; in the implementation.

Yes, I am aware of that - I had to go through all those issues with --combine
code in mid 2000s. C++ is different.
What I want is to make TBAA in between C++ types stronger and TBAA between
C++ and other languages to do pretty much what we donot, if possible.
> 
> > I also want it to never merge when types are local. For 
> > inter-language TBAA we will need to ensure aliasing in between non-ODR 
> > type of same layout and all unmerged variants of ODR type.
> >  Can it be 
> > done by attaching chains of ODR types into the canonical type hash and 
> > when non-ODR type appears, just make it alias with all of them?
> 
> No, how would that work?

This is what I am asking you about.
At the end of streaming process, we will have canonical type hash with one leader
and list of ODR variants that was not merged based on ODR rules.
If leader happens to be non-ODR, then it must be made to alias all of them.
I think either we can rewrite all ODR cases to have the non-ODR as canonical type
or make something more fine grained so we can force loads/stores through non-ODR
types to alias with all of them, but loads/stores through ODR types to alias
as within C++ compilation unit.
> 
> > It would make sense to ODR merge in tree merging, too, but I am not sure if
> > this fits the current design, since you would need to merge SCC components of
> > different shape then that seems hard, right?
> 
> Right.  You'd lose the nice incremental SCC merging (where we haven't even
> yet implemented the nicest way - avoid re-materializing the SCC until
> we know it prevails).

Yes, SCC merging w/o re-materialization is a priority, indeed.
> 
> > It may be easier to ODR merge after streaming (during DECL fixup) just to make
> > WPA streaming cheaper and to reduce debug info size.  If you use
> > -fdump-ipa-devirt, it will dump you ODR types that did not get merged (only
> > ones with vtable pointers in them ATM) and there are quite long chains for
> > firefox. Surely then hundreds of duplicated ODR types will end up in the ltrans
> > partition streams and they eventually hit debug output machinery.
> > Eric sent me presentation about doing this in LLVM.
> > http://llvm.org/devmtg/2013-11/slides/Christopher-DebugInfo.pdf
> 
> Debuginfo is sth completely separate and should be done separately
> (early debug), avoiding to stream the types in the first place.

If we generate dwarf dies, we still need to hook them to our IL so we know what they describe.
We will also need to merge them. LLVM basically does early debug and it does the merging
and it needs 13GB extra memory use when you compile firefox with -g compared to no -g.
So it seems to serve as a warning that this path is not 100% problem-free either.

But yes, it is a separate issue.
> 
> > > 
> > > The canonical type computation happens separately (only for prevailing
> > > types, of course), and there we already "merge" types which differ
> > > in completeness.  Canonical type merging is conservative the other
> > > way aroud - if we merge _all_ types to a single canonical type then
> > > TBAA is still correct (we get a single alias set).
> > 
> > Yes, I think I understand that. One equivalence is kind of minimal so we merge
> > only if we are sure there is no informationloss, other is maximal so we are
> > sure that types that needs to be equivalent by whatever underlying langauge
> > TBAA rules are actually equivalent.
> 
> The former is just not correct - it would mean that not merging at all
> would be valid, which it is not (you'd create wrong-code all over the 
> place).

Ah yes, because of memory layout differences.
> 
> Ok.  You have to be aware of the effects on inter-language 
> interoperability though (you'll break it).  Thus I'd make this
> guarded by -fextra-strict-aliasing and only auto-enable that when
> all TUs are produced by the same frontend (easy enough to check I guess).

What I am trying to propose (in first step) should be safe inter-language.
But yes, we can start doing it optional and gain some experience. I am sure
there will be surprises ;)

Honza
> 
> Richard.
> 
> > > Oh - and the easiest way to improve things is to get less types into
> > > the merging process in the first place!
> > 
> > Yep, my experiments with not streaming BINFO are directed in it.  I will collect
> > some numbers and send.
> > 
> > Honza
> > > 
> > > Richard.