Improve TBAA for types in anonymous namespaces

Hi,
this patch adjusts LTO tree merging to treat anonymous namespace types
as local to a given TU, so just like !TREE_PUBLIC decls they are not
merged (this is unify_scc change). This makes them to get different
canonical types and act as independent types for TBAA.

I also modified canonical type calculation to never consider anonymous
namespace types as interoperable with structurally equivalent types
declared in non-C++ translation units.

Both these changes are tested by the testcase (first change makes set1
and set2 independent and second chnage makes set1&set2 independent of
set3).

lto-bootstrapped/regtested x86_64-linux
Honza

	* lto-common.c (gimple_register_canonical_type_1): Do not look for
	non-ODR conflicts of types in anonymous namespaces.
	(unify_scc): Do not merge anonymous namespace types.
	* g++.dg/lto/alias-5_0.C: New testcase.
	* g++.dg/lto/alias-5_1.C: New.
	* g++.dg/lto/alias-5_2.c: New.

On Thu, 18 Jul 2019, Jan Hubicka wrote:

> Hi,
> this patch adjusts LTO tree merging to treat anonymous namespace types
> as local to a given TU, so just like !TREE_PUBLIC decls they are not
> merged (this is unify_scc change). This makes them to get different
> canonical types and act as independent types for TBAA.
> 
> I also modified canonical type calculation to never consider anonymous
> namespace types as interoperable with structurally equivalent types
> declared in non-C++ translation units.
> 
> Both these changes are tested by the testcase (first change makes set1
> and set2 independent and second chnage makes set1&set2 independent of
> set3).
> 
> lto-bootstrapped/regtested x86_64-linux

OK.  I wonder if we can/should carve off some bits to note
type_with_linkage_p and type_in_anonymous_namespace_p in the tree
itself?  At least in type_common there's plenty of bits left.
Not sure how expensive / reliable (non-C++?) those tests otherwise are.

Thanks,
Richard.

> Honza
> 
> 	* lto-common.c (gimple_register_canonical_type_1): Do not look for
> 	non-ODR conflicts of types in anonymous namespaces.
> 	(unify_scc): Do not merge anonymous namespace types.
> 	* g++.dg/lto/alias-5_0.C: New testcase.
> 	* g++.dg/lto/alias-5_1.C: New.
> 	* g++.dg/lto/alias-5_2.c: New.
> Index: lto/lto-common.c
> ===================================================================
> --- lto/lto-common.c	(revision 273551)
> +++ lto/lto-common.c	(working copy)
> @@ -418,13 +418,19 @@ gimple_register_canonical_type_1 (tree t
>    if (RECORD_OR_UNION_TYPE_P (t)
>        && odr_type_p (t) && !odr_type_violation_reported_p (t))
>      {
> -      /* Here we rely on fact that all non-ODR types was inserted into
> -	 canonical type hash and thus we can safely detect conflicts between
> -	 ODR types and interoperable non-ODR types.  */
> -      gcc_checking_assert (type_streaming_finished
> -			   && TYPE_MAIN_VARIANT (t) == t);
> -      slot = htab_find_slot_with_hash (gimple_canonical_types, t, hash,
> -				       NO_INSERT);
> +      /* Anonymous namespace types never conflict with non-C++ types.  */
> +      if (type_with_linkage_p (t) && type_in_anonymous_namespace_p (t))
> +	slot = NULL;
> +      else
> +	{
> +	  /* Here we rely on fact that all non-ODR types was inserted into
> +	     canonical type hash and thus we can safely detect conflicts between
> +	     ODR types and interoperable non-ODR types.  */
> +	  gcc_checking_assert (type_streaming_finished
> +			       && TYPE_MAIN_VARIANT (t) == t);
> +	  slot = htab_find_slot_with_hash (gimple_canonical_types, t, hash,
> +					   NO_INSERT);
> +	}
>        if (slot && !TYPE_CXX_ODR_P (*(tree *)slot))
>  	{
>  	  tree nonodr = *(tree *)slot;
> @@ -1640,11 +1646,14 @@ unify_scc (class data_in *data_in, unsig
>        tree t = streamer_tree_cache_get_tree (cache, from + i);
>        scc->entries[i] = t;
>        /* Do not merge SCCs with local entities inside them.  Also do
> -	 not merge TRANSLATION_UNIT_DECLs.  */
> +	 not merge TRANSLATION_UNIT_DECLs and anonymous namespace types.  */
>        if (TREE_CODE (t) == TRANSLATION_UNIT_DECL
>  	  || (VAR_OR_FUNCTION_DECL_P (t)
>  	      && !(TREE_PUBLIC (t) || DECL_EXTERNAL (t)))
> -	  || TREE_CODE (t) == LABEL_DECL)
> +	  || TREE_CODE (t) == LABEL_DECL
> +	  || (TYPE_P (t)
> +	      && type_with_linkage_p (TYPE_MAIN_VARIANT (t))
> +	      && type_in_anonymous_namespace_p (TYPE_MAIN_VARIANT (t))))
>  	{
>  	  /* Avoid doing any work for these cases and do not worry to
>  	     record the SCCs for further merging.  */
> Index: testsuite/g++.dg/lto/alias-5_0.C
> ===================================================================
> --- testsuite/g++.dg/lto/alias-5_0.C	(nonexistent)
> +++ testsuite/g++.dg/lto/alias-5_0.C	(working copy)
> @@ -0,0 +1,35 @@
> +/* { dg-lto-do run } */
> +/* { dg-lto-options { { -O3 -flto } } } */
> +/* This testcase tests that anonymous namespaces in different TUs are treated
> +   as different types by LTO TBAA and that they never alias with structurally
> +   same C types.  */
> +namespace {
> +  __attribute__((used))
> +  struct a {int a;} *p,**ptr=&p;
> +};
> +void
> +set1()
> +{
> +  *ptr=0;
> +}
> +void
> +get1()
> +{
> +  if (!__builtin_constant_p (*ptr==0))
> +    __builtin_abort ();
> +}
> +extern void set2();
> +extern "C" void set3();
> +int n = 1;
> +int
> +main()
> +{
> +  for (int i = 0; i < n; i++)
> +    {
> +      set1();
> +      set2();
> +      set3();
> +      get1();
> +    }
> +  return 0;
> +}
> Index: testsuite/g++.dg/lto/alias-5_1.C
> ===================================================================
> --- testsuite/g++.dg/lto/alias-5_1.C	(nonexistent)
> +++ testsuite/g++.dg/lto/alias-5_1.C	(working copy)
> @@ -0,0 +1,9 @@
> +namespace {
> +  __attribute__((used))
> +  struct a {int a;} *p,**ptr=&p,q;
> +};
> +void
> +set2()
> +{
> +  *ptr=&q;
> +}
> Index: testsuite/g++.dg/lto/alias-5_2.c
> ===================================================================
> --- testsuite/g++.dg/lto/alias-5_2.c	(nonexistent)
> +++ testsuite/g++.dg/lto/alias-5_2.c	(working copy)
> @@ -0,0 +1,7 @@
> +  __attribute__((used))
> +  struct a {int a;} *p,**ptr=&p,q;
> +void
> +set3()
> +{
> +  *ptr=&q;
> +}
>

> On Thu, 18 Jul 2019, Jan Hubicka wrote:
> 
> > Hi,
> > this patch adjusts LTO tree merging to treat anonymous namespace types
> > as local to a given TU, so just like !TREE_PUBLIC decls they are not
> > merged (this is unify_scc change). This makes them to get different
> > canonical types and act as independent types for TBAA.
> > 
> > I also modified canonical type calculation to never consider anonymous
> > namespace types as interoperable with structurally equivalent types
> > declared in non-C++ translation units.
> > 
> > Both these changes are tested by the testcase (first change makes set1
> > and set2 independent and second chnage makes set1&set2 independent of
> > set3).
> > 
> > lto-bootstrapped/regtested x86_64-linux
> 
> OK.  I wonder if we can/should carve off some bits to note
> type_with_linkage_p and type_in_anonymous_namespace_p in the tree
> itself?  At least in type_common there's plenty of bits left.
> Not sure how expensive / reliable (non-C++?) those tests otherwise are.

I was thinking of that too. The pattern matching is somewhat ugly.
It is now sanity checked to non-C++ FEs by verifying that CXX_ODR_P is
set if the test matches, so it seems to work reliably (byt indeed there
was issues until this stage1)

After we dropped -fno-odr-type-merging these predicates are no longer
absolutely terrible though. type_with_linkage_p boils down to testing
that TYPE_NAME is TYPE_DECL and it has ASSEMBLER_NAME set.  Anonymous
namespace just looks for <anon> in the type name.

I plan to do some profiling and we can see how bad are they these days.
Flag would also save the weird set of tests we do in
need_assembler_name_p to not get confused by other languages.

Honza

> 
> OK.  I wonder if we can/should carve off some bits to note
> type_with_linkage_p and type_in_anonymous_namespace_p in the tree
> itself?  At least in type_common there's plenty of bits left.
> Not sure how expensive / reliable (non-C++?) those tests otherwise are.

It also makes me wonder if other languages (D, Ada, go, Fortran...) have
concept of anonymous namespace types - that is types that are never
interoperable with types from another translation unit.  That would
justify the extra flag pretty well.

Similarly for types with name mangling defined.  Both these bits can be
made indpendent of C++.

Honza

Jan Hubicka <hubicka@ucw.cz> writes:

>> 
>> OK.  I wonder if we can/should carve off some bits to note
>> type_with_linkage_p and type_in_anonymous_namespace_p in the tree
>> itself?  At least in type_common there's plenty of bits left.
>> Not sure how expensive / reliable (non-C++?) those tests otherwise are.
>
> It also makes me wonder if other languages (D, Ada, go, Fortran...) have
> concept of anonymous namespace types - that is types that are never
> interoperable with types from another translation unit.  That would
> justify the extra flag pretty well.
>
> Similarly for types with name mangling defined.  Both these bits can be
> made indpendent of C++.

Go has the concept, but it implements it by mangling the names with the
package-path, which is required to be unique within an application (the
package-path is normally the path used to find an import, so it is
inherently unique within a file system).

Ian

> Jan Hubicka <hubicka@ucw.cz> writes:
> 
> >> 
> >> OK.  I wonder if we can/should carve off some bits to note
> >> type_with_linkage_p and type_in_anonymous_namespace_p in the tree
> >> itself?  At least in type_common there's plenty of bits left.
> >> Not sure how expensive / reliable (non-C++?) those tests otherwise are.
> >
> > It also makes me wonder if other languages (D, Ada, go, Fortran...) have
> > concept of anonymous namespace types - that is types that are never
> > interoperable with types from another translation unit.  That would
> > justify the extra flag pretty well.
> >
> > Similarly for types with name mangling defined.  Both these bits can be
> > made indpendent of C++.
> 
> Go has the concept, but it implements it by mangling the names with the
> package-path, which is required to be unique within an application (the
> package-path is normally the path used to find an import, so it is
> inherently unique within a file system).

Currently we implement ODR names only for C++.  If Go has similar
concept (i.e. types has mangled names and equal names implies equal
types acros sunits), we may want to implemnt it too and improve TBAA for
go programs..  I wonder is there something I can read about go types and
mangling?

This would be good motivation to make ODR type machinery indepenent of
C++.  Until now it was only used to drive devirtualization (which needs
BINFOs that are not done by go FE either) and produce ODR violation
warnings (that I am not sure if would make sense for go), but with TBAA
I think I can take a look into this.

Honza
> 
> Ian

Jan Hubicka <hubicka@ucw.cz> writes:

>> >> 
>> >> OK.  I wonder if we can/should carve off some bits to note
>> >> type_with_linkage_p and type_in_anonymous_namespace_p in the tree
>> >> itself?  At least in type_common there's plenty of bits left.
>> >> Not sure how expensive / reliable (non-C++?) those tests otherwise are.
>> >
>> > It also makes me wonder if other languages (D, Ada, go, Fortran...) have
>> > concept of anonymous namespace types - that is types that are never
>> > interoperable with types from another translation unit.  That would
>> > justify the extra flag pretty well.
>> >
>> > Similarly for types with name mangling defined.  Both these bits can be
>> > made indpendent of C++.
>> 
>> Go has the concept, but it implements it by mangling the names with the
>> package-path, which is required to be unique within an application (the
>> package-path is normally the path used to find an import, so it is
>> inherently unique within a file system).
>
> Currently we implement ODR names only for C++.  If Go has similar
> concept (i.e. types has mangled names and equal names implies equal
> types acros sunits), we may want to implemnt it too and improve TBAA for
> go programs..  I wonder is there something I can read about go types and
> mangling?

I don't know that the mangling is documented anywhere.  It's just an
implementation detail.  The basic idea follows from
https://golang.org/ref/spec#Import_declarations which explains how to
refer to identifiers defined in other packages.  There is no requirement
that the identifiers in different packages have unique names.  That is
if packages p1 and p2 both define a type T, then p1.T and p2.T are
different types.

Within the GCC middle-end, names will have the mangling applied, so if
the middle-end sees two types both named p1.T, then they are indeed the
same type.  It may be possible to use this fact for better TBAA when
using LTO.


> This would be good motivation to make ODR type machinery indepenent of
> C++.  Until now it was only used to drive devirtualization (which needs
> BINFOs that are not done by go FE either) and produce ODR violation
> warnings (that I am not sure if would make sense for go), but with TBAA
> I think I can take a look into this.

ODR violations can't arise in Go, since there is no way to give two
distinct types/variables/functions the same mangled name.

Go could in principle benefit from devirtualization optimizations, but
they would look pretty different than they do in C++ and I doubt they
could actually share an implementation.

Ian