Re: TYPE_BINFO and canonical types at LTO

[Richard Biener <rguenther at suse dot de>]

On Wed, 19 Feb 2014, Jan Hubicka wrote:

> > 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'm considering interoperation as defined by language standards
(definitely existing for Fortran <-> C) only.  I'm quite sure such
language specified interoperation exists for Ada as well and it
does exist for Java NI / C++ (not that we care here I guess).

I'm not at all sure to what extent interoperation between C and C++
is defined (apart from knowing 'extern "C"' to avoid mangling), so
I'm curious there.

So what we need to make sure is that the TBAA we apply does not break
when LTO-ing "valid" cross-language interoperation.  The current 
implementation is somewhat ad-hoc and tries to be very conservative
(but at the same time has known issues).

> 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.

Sure.  You can also track "language" per function and update it to
"mix" when inlining different language functions (but then you have to
implement knowledge into IPA propagators as well), and then fall back
to conservative TBAA for functions with cross-language interoperation.

I'm just not sure how to represent those "two" views of TBAA with
current infrastructure ...

> > 
> > > > ?  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.

Ok, so currently we don't have that "list of variants" but we could
keep it.  So we'd compute the conservative TYPE_CANONICAL but keep
a list of "equivalent" types during streaming.

After streaming we iterate over all canonical type leaders, looking
in the list of structurally equal types and if all of them need
to follow ODR rules split this canonical group into multiple distinct
groups based on ODR rules?

We can (and should) do that at LTRANS stage only?  That avoids
the need to keep the list at WPA time and the time to dissect the
groups?

> > > 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.

Yeah.  It should be quite easy to do for SCCs without hash collisions
(just keep around the on-disk SCC rep of the prevailing SCC and
do a memcmp with the SCC you are about to read).  For SCCs with
hash collisions the compare isn't so trivial so maybe we'd just keep
the re-materializing code-path for those.  We can easily stream
a flag whether the SCC does have multiple entries with the same hash
or not.

I will probably play with this during next stage1 if nobody beats me
on it (you can add statistics to lto-streamer-out.c:1254 to see
how many SCCs or SCC entries you'll cover with that approach).

Richard.

> > > 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.