Enable TBAA on anonymous types with LTO

Enable TBAA on anonymous types with LTO

[Jan Hubicka]

Hello,
this is patch to preserve TBAA for anonymous types to LTO.  The difference
can be seen on the testcase:

namespace
{
  struct A {int a;};
  struct B {int b;};
}

struct A aa,*a=&aa;
struct B bb,*b=&bb;

void
setA()
{
  a->a=1;
}
void
setB()
{
  b->b=2;
}
int
main()
{
  asm("":"=r"(a),"=r"(b));
  setA();
  setB();
  if (!__builtin_constant_p (a->a))
    __builtin_abort ();
  return 0;
}

With patch it does get properly optimized with -O2 -fno-early-inlining.

The basic idea is to:
  1) stream canonical types when they are anonymous
     (and thus need not be structurally merged)
  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.

     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.

     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.

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?

Honza

	* c-decl.c (pushtag): Set TREE_PUBLIC on STUB DECL>

	* lto-streamer-out.c (DFS::DFS_write_tree_body): Optinally stream
	TYPE_CANONICAL.
	
	* lto.c (iterative_hash_canonical_type): Handle cases where TYPE_CANONICAL
	is pre-set.
	(gimple_register_canonical_type_1): Likewise.
	(lto_register_canonical_types): Likewise.
	(compare_tree_sccs_1): Anonymous namespaces never compare;
	neither does types in anonymous namespace.
	(lto_read_decls): Do not check TYPE_CANONICAL.
	* tree-streamer-out.c (write_ts_type_common_tree_pointers): Optinally write
	TYPE_CANONICAL.
	* lto-streamer-in.c (lto_read_body_or_constructor): Handle case
	where TYPE_CANONICAL is pre-set.
	* tree-streamer-in.c (lto_input_ts_type_common_tree_pointers): Stream
	in TYPE_CANONICAL.

Index: c/c-decl.c
===================================================================
--- c/c-decl.c	(revision 215645)
+++ c/c-decl.c	(working copy)
@@ -1466,6 +1466,7 @@ pushtag (location_t loc, tree name, tree
   /* An approximation for now, so we can tell this is a function-scope tag.
      This will be updated in pop_scope.  */
   TYPE_CONTEXT (type) = DECL_CONTEXT (TYPE_STUB_DECL (type));
+  TREE_PUBLIC (TYPE_STUB_DECL (type)) = 1;
 
   if (warn_cxx_compat && name != NULL_TREE)
     {
Index: lto-streamer-out.c
===================================================================
--- lto-streamer-out.c	(revision 215645)
+++ lto-streamer-out.c	(working copy)
@@ -600,8 +600,11 @@ DFS::DFS_write_tree_body (struct output_
 	 during fixup.  */
       DFS_follow_tree_edge (TYPE_MAIN_VARIANT (expr));
       DFS_follow_tree_edge (TYPE_CONTEXT (expr));
-      /* TYPE_CANONICAL is re-computed during type merging, so no need
-	 to follow 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)))
+        DFS_follow_tree_edge (TYPE_CANONICAL (expr));
       DFS_follow_tree_edge (TYPE_STUB_DECL (expr));
     }
 
Index: lto/lto.c
===================================================================
--- lto/lto.c	(revision 215645)
+++ lto/lto.c	(working copy)
@@ -388,17 +389,29 @@ iterative_hash_canonical_type (tree type
   if (TYPE_CANONICAL (type))
     {
       type = TYPE_CANONICAL (type);
-      v = gimple_canonical_type_hash (type);
-    }
-  else
-    {
-      /* Canonical types should not be able to form SCCs by design, this
-	 recursion is just because we do not register canonical types in
-	 optimal order.  To avoid quadratic behavior also register the
-	 type here.  */
-      v = hash_canonical_type (type);
-      gimple_register_canonical_type_1 (type, v);
+      num_canonical_type_hash_queries++;
+      hashval_t *slot = canonical_type_hash_cache->get (type);
+
+      /* Normally we set TYPE_CANONICAL only after adding TYPE
+	 into the CANONICAL_TYPE_HASH_CACHE.  For anonymous
+	 namespace types we however explicitly stream the
+	 canonical type and thus we may need to recurse here.  */
+      if (slot)
+	{
+          hstate.add_int (*slot);
+	  return;
+	}
+#ifdef ENABLE_CHECKING
+      else
+	gcc_assert (type_in_anonymous_namespace_p (type));
+#endif
     }
+  /* Canonical types should not be able to form SCCs by design, this
+     recursion is just because we do not register canonical types in
+     optimal order.  To avoid quadratic behavior also register the
+     type here.  */
+  v = hash_canonical_type (type);
+  gimple_register_canonical_type_1 (type, v);
   hstate.add_int (v);
 }
 
@@ -635,18 +649,26 @@ gimple_register_canonical_type_1 (tree t
 {
   void **slot;
 
-  gcc_checking_assert (TYPE_P (t) && !TYPE_CANONICAL (t));
+  gcc_checking_assert (TYPE_P (t));
 
   slot = htab_find_slot_with_hash (gimple_canonical_types, t, hash, INSERT);
   if (*slot)
     {
       tree new_type = (tree)(*slot);
       gcc_checking_assert (new_type != t);
-      TYPE_CANONICAL (t) = new_type;
+      if (!TYPE_CANONICAL (t))
+        TYPE_CANONICAL (t) = new_type;
+      else
+	{
+          bool existed_p = canonical_type_hash_cache->put (t, hash);
+	  if (!existed_p)
+	    num_canonical_type_hash_entries++;
+	}
     }
   else
     {
-      TYPE_CANONICAL (t) = t;
+      if (!TYPE_CANONICAL (t))
+        TYPE_CANONICAL (t) = t;
       *slot = (void *) t;
       /* Cache the just computed hash value.  */
       num_canonical_type_hash_entries++;
@@ -683,16 +705,22 @@ lto_register_canonical_types (tree node,
       || !TYPE_P (node))
     return;
 
-  if (first_p)
-    TYPE_CANONICAL (node) = NULL_TREE;
+  if (!TYPE_CANONICAL (node)
+      || !type_in_anonymous_namespace_p (TYPE_CANONICAL (node)))
+    {
+      if (first_p)
+	TYPE_CANONICAL (node) = NULL_TREE;
 
-  if (POINTER_TYPE_P (node)
-      || TREE_CODE (node) == COMPLEX_TYPE
-      || TREE_CODE (node) == ARRAY_TYPE)
-    lto_register_canonical_types (TREE_TYPE (node), first_p);
+      if (POINTER_TYPE_P (node)
+	  || TREE_CODE (node) == COMPLEX_TYPE
+	  || TREE_CODE (node) == ARRAY_TYPE)
+	lto_register_canonical_types (TREE_TYPE (node), first_p);
 
- if (!first_p) 
-    gimple_register_canonical_type (node);
+     if (!first_p) 
+	gimple_register_canonical_type (node);
+    }
+  else
+    gcc_assert (TYPE_CANONICAL (node) == TYPE_CANONICAL (TYPE_CANONICAL (node)));
 }
 
 
@@ -1469,6 +1497,11 @@ compare_tree_sccs_1 (tree t1, tree t2, t
   if (CODE_CONTAINS_STRUCT (code, TS_DECL_MINIMAL))
     {
       compare_tree_edges (DECL_NAME (t1), DECL_NAME (t2));
+
+      /* Two anonymous namespaces are never equal.  */
+      if (code == NAMESPACE_DECL
+	  && !TREE_PUBLIC (t1))
+	return false;
       /* ???  Global decls from different TUs have non-matching
 	 TRANSLATION_UNIT_DECLs.  Only consider a small set of
 	 decls equivalent, we should not end up merging others.  */
@@ -1565,9 +1598,14 @@ compare_tree_sccs_1 (tree t1, tree t2, t
 	;
       else
 	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;
     }
 
   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))
 		{
 		  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);
   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));
 		  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);
 }
 

Re: Enable TBAA on anonymous types with LTO

[Richard Biener]

On Fri, 26 Sep 2014, Jan Hubicka wrote:

> Hello,
> this is patch to preserve TBAA for anonymous types to LTO.  The difference
> can be seen on the testcase:
> 
> namespace
> {
>   struct A {int a;};
>   struct B {int b;};
> }
> 
> struct A aa,*a=&aa;
> struct B bb,*b=&bb;
> 
> void
> setA()
> {
>   a->a=1;
> }
> void
> setB()
> {
>   b->b=2;
> }
> int
> main()
> {
>   asm("":"=r"(a),"=r"(b));
>   setA();
>   setB();
>   if (!__builtin_constant_p (a->a))
>     __builtin_abort ();
>   return 0;
> }
> 
> With patch it does get properly optimized with -O2 -fno-early-inlining.
> 
> The basic idea is to:
>   1) stream canonical types when they are anonymous
>      (and thus need not be structurally merged)

Why not just make all anonymous types their own canonical type?
(of course considering type variants)

>   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; };

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

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

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

> Honza
> 
> 	* c-decl.c (pushtag): Set TREE_PUBLIC on STUB DECL>
> 
> 	* lto-streamer-out.c (DFS::DFS_write_tree_body): Optinally stream
> 	TYPE_CANONICAL.
> 	
> 	* lto.c (iterative_hash_canonical_type): Handle cases where TYPE_CANONICAL
> 	is pre-set.
> 	(gimple_register_canonical_type_1): Likewise.
> 	(lto_register_canonical_types): Likewise.
> 	(compare_tree_sccs_1): Anonymous namespaces never compare;
> 	neither does types in anonymous namespace.
> 	(lto_read_decls): Do not check TYPE_CANONICAL.
> 	* tree-streamer-out.c (write_ts_type_common_tree_pointers): Optinally write
> 	TYPE_CANONICAL.
> 	* lto-streamer-in.c (lto_read_body_or_constructor): Handle case
> 	where TYPE_CANONICAL is pre-set.
> 	* tree-streamer-in.c (lto_input_ts_type_common_tree_pointers): Stream
> 	in TYPE_CANONICAL.
> 
> Index: c/c-decl.c
> ===================================================================
> --- c/c-decl.c	(revision 215645)
> +++ c/c-decl.c	(working copy)
> @@ -1466,6 +1466,7 @@ pushtag (location_t loc, tree name, tree
>    /* An approximation for now, so we can tell this is a function-scope tag.
>       This will be updated in pop_scope.  */
>    TYPE_CONTEXT (type) = DECL_CONTEXT (TYPE_STUB_DECL (type));
> +  TREE_PUBLIC (TYPE_STUB_DECL (type)) = 1;
>  
>    if (warn_cxx_compat && name != NULL_TREE)
>      {
> Index: lto-streamer-out.c
> ===================================================================
> --- lto-streamer-out.c	(revision 215645)
> +++ lto-streamer-out.c	(working copy)
> @@ -600,8 +600,11 @@ DFS::DFS_write_tree_body (struct output_
>  	 during fixup.  */
>        DFS_follow_tree_edge (TYPE_MAIN_VARIANT (expr));
>        DFS_follow_tree_edge (TYPE_CONTEXT (expr));
> -      /* TYPE_CANONICAL is re-computed during type merging, so no need
> -	 to follow 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)))
> +        DFS_follow_tree_edge (TYPE_CANONICAL (expr));
>        DFS_follow_tree_edge (TYPE_STUB_DECL (expr));
>      }
>  
> Index: lto/lto.c
> ===================================================================
> --- lto/lto.c	(revision 215645)
> +++ lto/lto.c	(working copy)
> @@ -388,17 +389,29 @@ iterative_hash_canonical_type (tree type
>    if (TYPE_CANONICAL (type))
>      {
>        type = TYPE_CANONICAL (type);
> -      v = gimple_canonical_type_hash (type);
> -    }
> -  else
> -    {
> -      /* Canonical types should not be able to form SCCs by design, this
> -	 recursion is just because we do not register canonical types in
> -	 optimal order.  To avoid quadratic behavior also register the
> -	 type here.  */
> -      v = hash_canonical_type (type);
> -      gimple_register_canonical_type_1 (type, v);
> +      num_canonical_type_hash_queries++;
> +      hashval_t *slot = canonical_type_hash_cache->get (type);
> +
> +      /* Normally we set TYPE_CANONICAL only after adding TYPE
> +	 into the CANONICAL_TYPE_HASH_CACHE.  For anonymous
> +	 namespace types we however explicitly stream the
> +	 canonical type and thus we may need to recurse here.  */
> +      if (slot)
> +	{
> +          hstate.add_int (*slot);
> +	  return;
> +	}
> +#ifdef ENABLE_CHECKING
> +      else
> +	gcc_assert (type_in_anonymous_namespace_p (type));
> +#endif
>      }
> +  /* Canonical types should not be able to form SCCs by design, this
> +     recursion is just because we do not register canonical types in
> +     optimal order.  To avoid quadratic behavior also register the
> +     type here.  */
> +  v = hash_canonical_type (type);
> +  gimple_register_canonical_type_1 (type, v);
>    hstate.add_int (v);
>  }
>  
> @@ -635,18 +649,26 @@ gimple_register_canonical_type_1 (tree t
>  {
>    void **slot;
>  
> -  gcc_checking_assert (TYPE_P (t) && !TYPE_CANONICAL (t));
> +  gcc_checking_assert (TYPE_P (t));
>  
>    slot = htab_find_slot_with_hash (gimple_canonical_types, t, hash, INSERT);
>    if (*slot)
>      {
>        tree new_type = (tree)(*slot);
>        gcc_checking_assert (new_type != t);
> -      TYPE_CANONICAL (t) = new_type;
> +      if (!TYPE_CANONICAL (t))
> +        TYPE_CANONICAL (t) = new_type;
> +      else
> +	{
> +          bool existed_p = canonical_type_hash_cache->put (t, hash);
> +	  if (!existed_p)
> +	    num_canonical_type_hash_entries++;
> +	}

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

>      }
>    else
>      {
> -      TYPE_CANONICAL (t) = t;
> +      if (!TYPE_CANONICAL (t))
> +        TYPE_CANONICAL (t) = t;
>        *slot = (void *) t;
>        /* Cache the just computed hash value.  */
>        num_canonical_type_hash_entries++;
> @@ -683,16 +705,22 @@ lto_register_canonical_types (tree node,
>        || !TYPE_P (node))
>      return;
>  
> -  if (first_p)
> -    TYPE_CANONICAL (node) = NULL_TREE;
> +  if (!TYPE_CANONICAL (node)
> +      || !type_in_anonymous_namespace_p (TYPE_CANONICAL (node)))
> +    {
> +      if (first_p)
> +	TYPE_CANONICAL (node) = NULL_TREE;
>  
> -  if (POINTER_TYPE_P (node)
> -      || TREE_CODE (node) == COMPLEX_TYPE
> -      || TREE_CODE (node) == ARRAY_TYPE)
> -    lto_register_canonical_types (TREE_TYPE (node), first_p);
> +      if (POINTER_TYPE_P (node)
> +	  || TREE_CODE (node) == COMPLEX_TYPE
> +	  || TREE_CODE (node) == ARRAY_TYPE)
> +	lto_register_canonical_types (TREE_TYPE (node), first_p);
>  
> - if (!first_p) 
> -    gimple_register_canonical_type (node);
> +     if (!first_p) 
> +	gimple_register_canonical_type (node);
> +    }
> +  else
> +    gcc_assert (TYPE_CANONICAL (node) == TYPE_CANONICAL (TYPE_CANONICAL (node)));
>  }
>  
>  
> @@ -1469,6 +1497,11 @@ compare_tree_sccs_1 (tree t1, tree t2, t
>    if (CODE_CONTAINS_STRUCT (code, TS_DECL_MINIMAL))
>      {
>        compare_tree_edges (DECL_NAME (t1), DECL_NAME (t2));
> +
> +      /* Two anonymous namespaces are never equal.  */
> +      if (code == NAMESPACE_DECL
> +	  && !TREE_PUBLIC (t1))
> +	return false;
>        /* ???  Global decls from different TUs have non-matching
>  	 TRANSLATION_UNIT_DECLs.  Only consider a small set of
>  	 decls equivalent, we should not end up merging others.  */
> @@ -1565,9 +1598,14 @@ compare_tree_sccs_1 (tree t1, tree t2, t
>  	;
>        else
>  	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?

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

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

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

>  		  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

Re: Enable TBAA on anonymous types with LTO

[Jan Hubicka]

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

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
  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.
> 
> > 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 ;))
> 
> 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?
Of course multiple ODR types may have same canonical type hash, so I can not
just assert they are not already there.

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

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

Re: Enable TBAA on anonymous types with LTO

[Jan Hubicka]

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

If I update my testcase to also have struct B b as a field I get:
        .type   _ZN1A2t2Ev, @function
_ZN1A2t2Ev:
.LFB1:
        .cfi_startproc
        rep ret
        .cfi_endproc

I.e. a::t is static (based on its anonymous namespace argument B) while a::t2 is normal
externally visible method for type mangled as A.

Re: Enable TBAA on anonymous types with LTO

[Jason Merrill]

On 09/29/2014 11:36 AM, Jan Hubicka wrote:
> If C++ FE sets canonical type always to main variant, it should work.
> Is it always the case?

No.  For a compound type like a pointer or function the canonical type 
strips all typedefs, but a main variant does not.

>>>        namespace {
>>>        struct B {};
>>>        }
>>>        struct A
>>>        {
>>> 	void t(B);
>>> 	void t2();
>>>        };
>
> 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.

Yes, it's an ODR violation.  The FE currently warns about a field with 
internal type, and I suppose could warn about other members as well.

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

Agreed.

> This does not work for types build from ODR types that are not ODR themselves.

I'm not sure what you mean.  In C++ the only types not subject to the 
ODR are local to one translation unit, so merging isn't an issue.  Do 
you mean types from other languages?

Jason

Re: Enable TBAA on anonymous types with LTO

[Jan Hubicka]

> On 09/29/2014 11:36 AM, Jan Hubicka wrote:
> >If C++ FE sets canonical type always to main variant, it should work.
> >Is it always the case?
> 
> No.  For a compound type like a pointer or function the canonical
> type strips all typedefs, but a main variant does not.
> 
> >>>       namespace {
> >>>       struct B {};
> >>>       }
> >>>       struct A
> >>>       {
> >>>	void t(B);
> >>>	void t2();
> >>>       };
> >
> >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.
> 
> Yes, it's an ODR violation.  The FE currently warns about a field
> with internal type, and I suppose could warn about other members as
> well.

The testcase seems to get around without a warning for both G++ and clang
(at least without -Wall)
> 
> >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.
> 
> Agreed.
> 
> >This does not work for types build from ODR types that are not ODR themselves.
> 
> I'm not sure what you mean.  In C++ the only types not subject to
> the ODR are local to one translation unit, so merging isn't an
> issue.  Do you mean types from other languages?

Yes, Richard would like

namespace {
  struct A {int a;};
}

to be considered with aliasing with 

  struct B {int b;};

in the other unit if that unit is built in C language (or any other than C++).

Honza
> Jason

Re: Enable TBAA on anonymous types with LTO

[Richard Biener]

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

Re: Enable TBAA on anonymous types with LTO

[Jan Hubicka]

> 
> 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!)

Yep, my patch streams and SCC walks them when they are anonymous.
By incremental patch I plan to handle all ODR and component types,
so basically stream canonical types for all C++ types.
> 
> Huh?  The merging code has an early out on different SCC size.  And
> TYPE_CANONICAL

I was seeing ICE in the loop merging the SCC unions. Will try to reproduce
it and investigate further.

> is not set at this point (once you stream it you have to walk and
> compare it during
> comparison).

At the moment I probably don't need to compare it, because it is set only for
anonymous types that are never merged. Once ODR part is in, we will ideed need
to match them.  
I do not want to match when the TYPE_CANONICAL is set by canonical type hash,
but I suppose I only need to check if TYPE_CANONICAL of one of types is
anonymous and rely on canonical type hash never set TYPE_CANONICAL to anonymous
type (it should not)
> 
> 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.

TREE_PUBLIC flag is already documented as such in tree.h
/* 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.  */

But indeed the C frontend does not set it according to this in all cases (fixed
in my patch). I added Ada and Fortran maintainers to help me identifying if
these have notion of such local types.

Fixing FE's is forutnately easy - there are very few places TYPE_STUB is built
and all I need is to hack stream out to accept anonymous types only for C++
and LTO FE.
> 
> > 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?

I am shooting to handle all ODR types, tobasically to fully preserve TBAA for
C++ (modulo structural conficts with non-C++).  This patch is first step as I
tought it will be easier to first get anonymous types right and build
incrementally from this. I expected that for anonymous types I do not need
to solve the conflicts with non-C++ and also they never merge. Still they
need good part of the full infrastructure I want.

Obviously C++ programs tends to have a lot of different types that have
same layout.  Making them all alias does not make them easier to optimize.
> 
> 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?

How do I measure the extra disambiguations?
> >> 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 do not think we have that many functions that would be composed only from
stuff from single TU.  This is becuase most of COMDAT code gets commonized
before inlining and true cross-module inlining is also very common thing.
On extension I was thinking about in longer term is to tag memory accesses
with original translation unit and make TBAA to be stronger for two
accesses within same unit.

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

Yes, you are riht. I want to have it only in hash-hash to make types built
from it that are non-anonymous (ICK) not ICE.
> 
> > 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.

I was looking into it - as the TYPE_CANONICAL check looked bogues on to me
and the "wrongly" ordered SCC components seemed to be the reason. That is also
why hash-hash sometimes need to recurse.
> >
> > 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.

Cool!
> 
> >>
> >> >      }
> >> >
> >> >    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.

Yep, I get what you mean and will give it a try.
I still wonder about wrongly ordered SCCs.  I proably can not simply try it,
because we have no non-anonymous type built from anonymous in testsuite. I noticed
those only in libreoffice where few anonymous enums are used in methods of
non-anonymous classes.  I suppose I can try to biuld artificial testcase,
but I am not that familiar with forcing SCC and their order.

Thanks for looking into this - indeed it is difficult area.
Honza