Re: Enable TBAA on anonymous types with LTO

[Richard Biener <rguenther@suse.de>]

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