Re: Enable TBAA on anonymous types with LTO

[Richard Biener <richard dot guenther at gmail dot com>]

On Mon, Sep 29, 2014 at 5:36 PM, Jan Hubicka <hubicka@ucw.cz> wrote:
>>
>> Why not just make all anonymous types their own canonical type?
>> (of course considering type variants)
>
> If C++ FE sets canonical type always to main variant, it should work.
> Is it always the case? I noticed you do this for variadic types.
> I tought there is reason why canonical types differ from main variants
> and the way canonical types are built in FE seems more complex too, than
> just setting CANONICAL=MAIN_VARIAN

Ok, as Jason explained this wouldn't work, so we indeed need to stream
TYPE_CANONICAL in this case (and also properly SCC-walk it!)

> >   2) update canonical type hash so it can deal with types that already have
>> >      canonical type set.
>> >      I insert even anonymous types there because I am not able to get rid
>> >      of cases where non-anonmous type explicitly mentions anonymous. Consider:
>> >       namespace {
>> >       struct B {};
>> >       }
>> >       struct A
>> >       {
>> >     void t(B);
>> >     void t2();
>> >       };
>> >       void
>> >       A::t(B)
>> >       {
>> >       }
>> >       void
>> >       A::t2()
>> >       {
>> >       }
>> >      Here we end up having type of method T non-anonymous but it builds from B that
>> >      is anonymous.
>>
>> But that makes B non-anonymous as well?  How is A::t mangled?  Consider
>> also the simpler case
>>
>> struct A { struct B b; };
>
> Yep, A seems to be not anonymous and mangled as A.  I think it is ODR violation
> to declare such type in more than one compilation unit (and we will warn on
> it). We can make it anonymous, but I think it is C++ FE to do so.

Ok.

>>
>> >      Being bale to handle non-upwards closed cases will be needed soon for full ODR
>> >      type handling
>> >   3) Disable tree merging of anonymous namespace nodes and anonymous types.  The second
>> >      is needed, because I can have two identically looking anonymous types from
>> >      same unit with different canonical types.
>>
>> But the container should be distinct?  Isn't this again the issue that
>> we merge anonymous namespace decls?  Please try to fix that one and
>> forall.
>
> I already made anonymous namespaces unmerged in this patch. But still I saw
> cases where two anonymous namespace types differed only by TYPE_CANONICAL and
> had DFS components of different size.  Because we do not compare TYPE_CANONICAl
> we declared them equivalent and DFS merging ICEd.

Huh?  The merging code has an early out on different SCC size.  And
TYPE_CANONICAL
is not set at this point (once you stream it you have to walk and
compare it during
comparison).

>>
>> >      This may go away once we get some ability to decide on unmergability at
>> >      stream out time.
>> >
>> > I do not attept to merge anonymous types with structurally equivalent
>> > non-anonymous types from other compilation units.  I think it is nature of C++
>> > language that types in anonymous namespaces can not be accessed by other units
>> > and I hope to use this for other optimizations, too.
>>
>> What about cross-language LTO?  With your scheme you say that you can't
>> ever interoperate using "anonymous" entities (even if used from a
>> non-anonymous one like in the examples above)?
>>
>> I think that's a dangerous route to go.  Maybe detect the case where
>> we compile from multiple source languages and behave differently?
>
> I really think that anonymous types are meant to not be accessible from other
> compilation unit and I do not see why other languages need different rule.
>
> Of course for proper ODR types we need to solve how to merge non-C++ types with
> them.  So I can do that for anonymous types, too.  I had to revisit my original
> plan for canonical types for ODR.  I originally just insterted ODR types into
> ODR hash as well as canonical type hash (without killing their canonical type).
> While doing so I recordedif given canonical type has non-ODR type in it.
> Finally I went through ODR types and updated their canonical types by canonical
> hash if the conflict happen.

What about other languages that match your anonymous-namespace check?
This should really be thoroughly documented as a middle-end feature/requirement
that languages should be aware of.

> This does not work for types build from ODR types that arenot ODR themselves.
> My plan is:
>   1) fork current canonical_type hash into two - structural_type_hash and
>      canonical_type_hash

Ick, please no.

>   2) During the streaming in, I populate structural_type_hash and the existing
>      odr_hash.  I record what structural type hash buckets contains non-ODR
>      type
>   3) During the existing loop that recomputes canonical type I start populating
>      canonical type hash.  It works same way as structural except for ODR
>      types that do not conflict. THose are considered by ODR equality.

What's the advantage over what your proposed patch did?  Apart from a lot
of extra complexity?

How many types in anonymous namespaces do C++ programs usually have?
That is, does it make a difference in real-world?  What's the number of
extra disambiguations we get from it?

>>
>> > We can add documentation about this to -fstrict-aliasing section of
>> > manual I guess.
>> >
>> > What I am concerned about is the needed change in c-decl.c.  C frontend currently
>> > outputs declarations that are confused by type_in_anonymous_namespace_p as anonymous
>> > in some cases.  This is because it does not set PUBLIC flag on TYPE decl.  This is
>> > bug:
>> > /* In a VAR_DECL, FUNCTION_DECL, NAMESPACE_DECL or TYPE_DECL,
>> >    nonzero means name is to be accessible from outside this translation unit.
>> >    In an IDENTIFIER_NODE, nonzero means an external declaration
>> >    accessible from outside this translation unit was previously seen
>> >    for this name in an inner scope.  */
>> > #define TREE_PUBLIC(NODE) ((NODE)->base.public_flag)
>> >
>> > This fortunately manifests itself as false warnings about type incompatiblity
>> > from lto-symtab.  I did not see these with other languages, but I suppose we will
>> > want to check that other FEs are behaving correctly here.
>> > I do not know how Ada and Fortran should behave here.
>> >
>> > Bootstrapped/regtested x86_64-linux, lto-bootstrapped, tested with Firefox and
>> > libreoffice. I also checked that tree merging is working still well. OK?
>>
>> Not in this form, we have to discuss this further.  It's way too agressive
>> in my view.
>
> Yep, I expected that, but we need to start somewhere ;))

Do we really?  I think that you eventually want something like a "type escape
analysis" instead?  Or better said, we make use of TBAA only intra-procedural
and thus after LTO IPA inlining we know exactly what types are refered to
per function.  Which means if a function is composed only from bits of a
single TU we can retain the original TYPE_CANONICALs for all memory
accesses inside that function.

>> I don't like changing the hashing/registering machinery this way.
>>
>> Can you please introduce a function that enters both hash and type
>> into the tables (asserting they are not already there) and call that
>> explicitely for anonymous types from lto_read_decls ...
>
> OK, so having something like register_odr_type doing both?

Well, you only register it in the hash-hash, no?

> Of course multiple ODR types may have same canonical type hash, so I can not
> just assert they are not already there.

As the ODR type should never be merged with anything (and thus does not
need an entry in the canonical type hash) it doesn't matter.

> I believe the TYPE_CANONICAl check originally prevented ICE in the case
> where strongly connected component is ordered in a way so registering earlier
> type into canonical type hash makes it recursively regiser later type.
> So it may happen that the type is already registered at a time lto_read_decls
> walks acorss it.

I don't remember exactly, but the assert was more like a contract one on the
existing API.

>> >     compare_tree_edges (TYPE_CONTEXT (t1), TYPE_CONTEXT (t2));
>> > -      /* TYPE_CANONICAL is re-computed during type merging, so do not
>> > -    compare it here.  */
>> > +      /* TYPE_CANONICAL of non-anonymous types is re-computed during type
>> > +    merging, so do not compare it here.  */
>> >        compare_tree_edges (TYPE_STUB_DECL (t1), TYPE_STUB_DECL (t2));
>> > +
>> > +      /* Two anonymous namespace types from the same unit still should
>> > +    not be unified.  */
>> > +      if (type_in_anonymous_namespace_p (t1))
>> > +   return false;
>>
>> Well, then exempt them from the merging process?  And compute the
>> property properly by also treating compositing with anon types
>> as anonymous.  (the patch somewhat feels like being the 2nd in a
>> series of two ...)  Didn't you have patches to do that during
>> SCC discovery at compile-time?  What happened to them?
>
> Yes, I had patches for that. You told you will think about best implementatoin
> later.  Later did not seem to happen yet :)
> https://gcc.gnu.org/ml/gcc-patches/2014-07/msg00614.html
> seems to be end of the thread.
>
> Yes, having that patch makes it possible to dropthese checks.

Ok, I'll try to revisit above somewhen next week.

>>
>> >      }
>> >
>> >    if (CODE_CONTAINS_STRUCT (code, TS_TYPE_NON_COMMON))
>> > @@ -1909,9 +1947,7 @@ lto_read_decls (struct lto_file_decl_dat
>> >               num_prevailing_types++;
>> >               lto_fixup_prevailing_type (t);
>> >             }
>> > -         /* Compute the canonical type of all types.
>> > -            ???  Should be able to assert that !TYPE_CANONICAL.  */
>> > -         if (TYPE_P (t) && !TYPE_CANONICAL (t))
>> > +         if (TYPE_P (t))
>>
>> ... here as else { ...?
>
> I am not sure what you mean here?

A continued comment from one above, where to put the register_odr_type call.

>>
>> >             {
>> >               gimple_register_canonical_type (t);
>> >               if (odr_type_p (t))
>> > Index: tree-streamer-out.c
>> > ===================================================================
>> > --- tree-streamer-out.c     (revision 215645)
>> > +++ tree-streamer-out.c     (working copy)
>> > @@ -708,8 +708,13 @@ write_ts_type_common_tree_pointers (stru
>> >       during fixup.  */
>> >    stream_write_tree (ob, TYPE_MAIN_VARIANT (expr), ref_p);
>> >    stream_write_tree (ob, TYPE_CONTEXT (expr), ref_p);
>> > -  /* TYPE_CANONICAL is re-computed during type merging, so no need
>> > -     to stream it here.  */
>> > +  /* For non-anonymous types, TYPE_CANONICAL is re-computed during type
>> > +     merging, so no need to follow it here.  */
>> > +  if (TYPE_CANONICAL (expr)
>> > +      && type_in_anonymous_namespace_p (TYPE_CANONICAL (expr)))
>> > +    stream_write_tree (ob, TYPE_CANONICAL (expr), ref_p);
>> > +  else
>> > +    stream_write_tree (ob, NULL_TREE, ref_p);
>>
>> We can compute type_in_anonymous_namespace_p in lto_read_decls
>> where we can simply set TYPE_CANONICAL (t) = TYPE_MAIN_VARIANT (t).
>> That's more light-weight on streaming.
>
> Yes, if that it is always correct canonical type, we could do it.  Just go with a flag.

Yeah, unfortunately it won't work.

>>
>> >    stream_write_tree (ob, TYPE_STUB_DECL (expr), ref_p);
>> >  }
>> >
>> > Index: lto-streamer-in.c
>> > ===================================================================
>> > --- lto-streamer-in.c       (revision 215645)
>> > +++ lto-streamer-in.c       (working copy)
>> > @@ -1104,8 +1104,8 @@ lto_read_body_or_constructor (struct lto
>> >
>> >           if (TYPE_P (t))
>> >             {
>> > -             gcc_assert (TYPE_CANONICAL (t) == NULL_TREE);
>> > -             TYPE_CANONICAL (t) = TYPE_MAIN_VARIANT (t);
>> > +             if (TYPE_CANONICAL (t))
>> > +               TYPE_CANONICAL (t) = TYPE_CANONICAL (TYPE_CANONICAL (t));
>>
>> Eh??!!  One more reason to not trust broken canonical types from the
>> C++ FE (the FE uses this for its very own thing, not really TBAA).
>
> Sorry, this is a forgotten hunk.  I was originally streaming TYPE_CANONICAL
> of all anonymous namespace type and was wondering about scenario where
> TYPE_CANONICAL of anonymous namespace is not anonymous and thus structurally
> merged. For such types we would compute new TYPE_CANONICAL and introduce this bug.
> I later asserted that this never happens, but forgot it here.

I see.

Richard.

> Honza
>>
>> >               if (TYPE_MAIN_VARIANT (t) != t)
>> >                 {
>> >                   gcc_assert (TYPE_NEXT_VARIANT (t) == NULL_TREE);
>> > Index: tree-streamer-in.c
>> > ===================================================================
>> > --- tree-streamer-in.c      (revision 215645)
>> > +++ tree-streamer-in.c      (working copy)
>> > @@ -804,8 +804,7 @@ lto_input_ts_type_common_tree_pointers (
>> >       during fixup.  */
>> >    TYPE_MAIN_VARIANT (expr) = stream_read_tree (ib, data_in);
>> >    TYPE_CONTEXT (expr) = stream_read_tree (ib, data_in);
>> > -  /* TYPE_CANONICAL gets re-computed during type merging.  */
>> > -  TYPE_CANONICAL (expr) = NULL_TREE;
>> > +  TYPE_CANONICAL (expr) = stream_read_tree (ib, data_in);
>> >    TYPE_STUB_DECL (expr) = stream_read_tree (ib, data_in);
>> >  }
>> >
>> >
>> >
>>
>> --
>> Richard Biener <rguenther@suse.de>
>> SUSE / SUSE Labs
>> SUSE LINUX Products GmbH - Nuernberg - AG Nuernberg - HRB 16746
>> GF: Jeff Hawn, Jennifer Guild, Felix Imend"orffer