Enable TBAA on anonymous types with LTO

[Jan Hubicka <hubicka@ucw.cz>]

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