Get aliases and weakrefs into better shape with LTO

[Jan Hubicka <hubicka at ucw dot cz>]

Hi,
this patch originated as attempt to fix new problems with aliases in Mozilla, but it ended up
somewhat more involved.  There seems to be numberous issues with current code handling aliases,
weakrefs in particular.

We have following problems:

 1) alias partitioning is broken in case where function with alias is inlined in other
    ltrans unit.  We end up with bogus error "XYZ aliased to undefined BLAH"
    because we end up assembling the alias in the wrong unit.

    What gets wrong here is the fact that lto_materialize_function
    calls rest_of_decl_compilation that in turn calls assemble_alias that inserts
    alias into alias pairs.  This code performs check and because the function
    is external in the ltrans unit that do not define it, it errors out.

    LTO streaming already takes care to output proper alias pairs into proper
    partition, so collecting alias pairs should not be redone (and it does not
    happen for variables).

    Fixing this issue (by adding in_lto_p check into rest_of_decl_compilation)
    however uncovers ...

 2) LTO alias code is written with normal aliases in mind.  We also do have weakref
    where the aliased symbol is not defined in the unit, yet the alias has to
    be assembled.  So lto streamer and partitioning needs updating to handle
    weakrefs specially.  We put them into every partition that uses them and
    we also add the corresponding alias pair.

    Weakref sort of worked previously because the pair was reconstructed,
    but not in all cases as demonstrated in PR45721

 3) remove_unreachable_alias_pairs is broken WRT weakrefs, too, incorrectly
    removing them.  This is masked since we tend to re-insert them later
    from rest_of_decl_compilation but it is not how things should work as
    if the symbol is defined locally, it would not be recognized as aliased.

    Overall I missed logic behing remove_unreachable_alias_pairs.  It seems to
    me that alias is dead if it is not used, not external and not used by
    other live alias.

    The original code first compute aliase whose target is defined and then
    it removes undefined ones if they are not directly referenced from code.
    This seems a symptomatic fix as it goes backwards.  I assume that original
    problem was an aliases stalling referencing optimized out object.

    We do take care that objects with alises are not optimized out before their
    aliases are.  We also take care that all aliases alias live objects, except for
    weakref. 

    I reorganized remove_unreachable_alias_pairs to do simple liveness analysis
    (starting from locally referenced aliases propagating to alises referenced by
    used aliases) as it is excatly what LTO alias code needs to do and is consitent
    with rest of dead stuff removal we do elsewhere.

    For this we need to propagate forward across aliases. So far we had
    only function compute_visible_aliases propagating backward.  It is used
    by finish_aliases_1 to output diagnostics about aliases whose target is not
    defined.  The name of functoin seems confusing to me as term "visible"
    does not seem to match here.  

    For this reason I introduced two propagation functions:
    propagate_aliases_forward, propagate_aliases_backward and made them generic
    as we do now 3 different propagations.  For 3) propagating from all aliases
    that are exported or used by code forward, 4) propagating from all aliases
    that are defined in given partition backwards and original propagation
    for finish_alises_1 propagating from all defined alises backward.

 4) LTO code deciding what alias is defined is broken, since it does not
    support chained aliases.  Code in remove_unreachable_alias_pairs 
    does that, so I re-used the logic.

 5) On the top of all this PR 45721 still needs fix in ipa.c.  There is sanity check
    that destination of an alias is needed so it is not optimized away (until cgraph
    code understand better the alises).  This is not true when we LTO weakref alias
    from one unit aliasing symbol from the other unit.  In this case we need to set
    the needed flag now.

Bootstrapped/regtested x86_64 and tested by mozilla build. Seems sane?

	* tree.h (symbol_alias_set_t): Move typedef here from varasm.c
	(symbol_alias_set_destroy, symbol_alias_set_contains,
	propagate_aliases_backward): Declare.
	* lto-streamer-out.c (struct sets): New sturcture.
	(trivally_defined_alias): New function.
	(output_alias_pair_p): Rewrite.
	(output_unreferenced_globals): Fix output of alias pairs.
	(produce_symtab): Likewise.
	* ipa.c (function_and_variable_visibility): Set weak alias destination
	as needed in lto.
	* varasm.c (symbol_alias_set_t): Remove.
	(symbol_alias_set_destroy): Export.
	(propagate_aliases_forward, propagate_aliases_backward): New functions
	based on ...
	(compute_visible_aliases): ... this one; remove.
	(trivially_visible_alias): New
	(trivially_defined_alias): New.
	(remove_unreachable_alias_pairs): Rewrite.
	(finish_aliases_1): Reorganize code checking if alias is defined.
	* passes.c (rest_of_decl_compilation): Do not call assemble_alias when
	in LTO mode.

	* lto.c (partition_cgraph_node_p, partition_varpool_node_p): Weakrefs are
	not partitioned.

	* testsuite/gcc.dg/lto/pr45721_1.c: New file.
	* testsuite/gcc.dg/lto/pr45721_0.c: New file.
Index: tree.h
===================================================================
--- tree.h	(revision 168508)
+++ tree.h	(working copy)
@@ -5389,6 +5389,18 @@ extern void remove_unreachable_alias_pai
 extern bool decl_replaceable_p (tree);
 extern bool decl_binds_to_current_def_p (tree);
 
+/* Derived type for use by compute_visible_aliases and callers.  A symbol
+   alias set is a pointer set into which we enter IDENTIFIER_NODES bearing
+   the canonicalised assembler-level symbol names corresponding to decls
+   and their aliases.  */
+typedef struct pointer_set_t symbol_alias_set_t;
+
+extern void symbol_alias_set_destroy (symbol_alias_set_t *);
+extern int symbol_alias_set_contains (const symbol_alias_set_t *, tree);
+extern symbol_alias_set_t * propagate_aliases_backward (bool (*)
+							 (tree, tree, void *),
+							void *);
+
 /* In stmt.c */
 extern void expand_computed_goto (tree);
 extern bool parse_output_constraint (const char **, int, int, int,
Index: lto-streamer-out.c
===================================================================
--- lto-streamer-out.c	(revision 168508)
+++ lto-streamer-out.c	(working copy)
@@ -2005,6 +2005,13 @@ output_function (struct cgraph_node *nod
 }
 
 
+/* Used to pass data to trivally_defined_alias callback.  */
+struct sets {
+  cgraph_node_set set;
+  varpool_node_set vset;
+};
+
+
 /* Return true if alias pair P belongs to the set of cgraph nodes in
    SET.  If P is a an alias for a VAR_DECL, it can always be emitted.
    However, for FUNCTION_DECL aliases, we should only output the pair
@@ -2014,16 +2021,51 @@ output_function (struct cgraph_node *nod
    the file processed by LTRANS.  */
 
 static bool
-output_alias_pair_p (alias_pair *p, cgraph_node_set set, varpool_node_set vset)
+trivally_defined_alias (tree decl ATTRIBUTE_UNUSED,
+			tree target, void *data)
+{
+  struct sets *set = (struct sets *) data;
+  struct cgraph_node *fnode = NULL;
+  struct varpool_node *vnode = NULL;
+
+  fnode = cgraph_node_for_asm (target);
+  if (fnode)
+    return cgraph_node_in_set_p (fnode, set->set);
+  vnode = varpool_node_for_asm (target);
+  return vnode && varpool_node_in_set_p (vnode, set->vset);
+}
+
+/* Return true if alias pair P should be output in the current
+   partition contains cgrpah nodes SET and varpool nodes VSET.
+   DEFINED is set of all aliases whose targets are defined in
+   the partition.
+
+   Normal aliases are output when they are defined, while WEAKREF
+   aliases are output when they are used.  */
+
+static bool
+output_alias_pair_p (alias_pair *p, symbol_alias_set_t *defined,
+		     cgraph_node_set set, varpool_node_set vset)
 {
-  if (TREE_CODE (p->decl) == VAR_DECL)
-    return varpool_node_in_set_p (varpool_node_for_asm (p->target), vset);
+  struct cgraph_node *node;
+  struct varpool_node *vnode;
 
-  /* Check if the assembler name for P->TARGET has its cgraph node in SET.  */
-  gcc_assert (TREE_CODE (p->decl) == FUNCTION_DECL);
-  return cgraph_node_in_set_p (cgraph_node_for_asm (p->target), set);
+  if (lookup_attribute ("weakref", DECL_ATTRIBUTES (p->decl)))
+    {
+      if (TREE_CODE (p->decl) == VAR_DECL)
+	{
+	  vnode = varpool_get_node (p->decl);
+	  return (vnode
+		  && referenced_from_this_partition_p (&vnode->ref_list, set, vset));
+	}
+      node = cgraph_get_node (p->decl);
+      return (node
+	      && (referenced_from_this_partition_p (&node->ref_list, set, vset)
+		  || reachable_from_this_partition_p (node, set)));
+    }
+  else
+    return symbol_alias_set_contains (defined, p->decl);
 }
 
 /* Output any unreferenced global symbol defined in SET, alias pairs
    and labels.  */
@@ -2035,6 +2079,11 @@ output_unreferenced_globals (cgraph_node
   alias_pair *p;
   unsigned i;
   struct varpool_node *vnode;
+  symbol_alias_set_t *defined;
+  struct sets setdata;
+
+  setdata.set = set;
+  setdata.vset = vset;
 
   ob = create_output_block (LTO_section_static_initializer);
   ob->cgraph_node = NULL;
@@ -2068,15 +2117,20 @@ output_unreferenced_globals (cgraph_node
 
   output_zero (ob);
 
+  /* We really need to propagate in both directoins:
+     for normal aliases we propagate from first defined alias to
+     all aliases defined based on it.  For weakrefs we propagate in
+     the oposite direction.  */
+  defined = propagate_aliases_backward (trivally_defined_alias, &setdata);
+
   /* Emit the alias pairs for the nodes in SET.  */
   FOR_EACH_VEC_ELT (alias_pair, alias_pairs, i, p)
-    {
-      if (output_alias_pair_p (p, set, vset))
-	{
-	  lto_output_tree_ref (ob, p->decl);
-	  lto_output_tree_ref (ob, p->target);
-	}
-    }
+    if (output_alias_pair_p (p, defined, set, vset))
+      {
+	lto_output_tree_ref (ob, p->decl);
+	lto_output_tree_ref (ob, p->target);
+      }
+  symbol_alias_set_destroy (defined);
 
   output_zero (ob);
 
@@ -2474,6 +2530,11 @@ produce_symtab (struct output_block *ob,
   lto_cgraph_encoder_t encoder = ob->decl_state->cgraph_node_encoder;
   int i;
   alias_pair *p;
+  struct sets setdata;
+  symbol_alias_set_t *defined;
+
+  setdata.set = set;
+  setdata.vset = vset;
 
   lto_begin_section (section_name, false);
   free (section_name);
@@ -2551,9 +2612,11 @@ produce_symtab (struct output_block *ob,
     }
 
   /* Write all aliases.  */
+  defined = propagate_aliases_backward (trivally_defined_alias, &setdata);
   FOR_EACH_VEC_ELT (alias_pair, alias_pairs, i, p)
-    if (output_alias_pair_p (p, set, vset))
+    if (output_alias_pair_p (p, defined, set, vset))
       write_symbol (cache, &stream, p->decl, seen, true);
+  symbol_alias_set_destroy (defined);
 
   lto_write_stream (&stream);
   pointer_set_destroy (seen);
Index: ipa.c
===================================================================
--- ipa.c	(revision 168508)
+++ ipa.c	(working copy)
@@ -846,6 +846,13 @@ function_and_variable_visibility (bool w
 		
       if ((node = cgraph_node_for_asm (p->target)) != NULL)
         {
+	  /* Weakrefs alias symbols from other compilation unit.  In the case
+	     the destination of weakref became available because of LTO, we must
+	     mark it as needed.  */
+	  if (in_lto_p
+	      && lookup_attribute ("weakref", DECL_ATTRIBUTES (p->decl))
+	      && !node->needed)
+	    cgraph_mark_needed_node (node);
 	  gcc_assert (node->needed);
 	  pointer_set_insert (aliased_nodes, node);
 	  if (dump_file)
@@ -854,6 +861,13 @@ function_and_variable_visibility (bool w
         }
       else if ((vnode = varpool_node_for_asm (p->target)) != NULL)
         {
+	  /* Weakrefs alias symbols from other compilation unit.  In the case
+	     the destination of weakref became available because of LTO, we must
+	     mark it as needed.  */
+	  if (in_lto_p
+	      && lookup_attribute ("weakref", DECL_ATTRIBUTES (p->decl))
+	      && !vnode->needed)
+	    varpool_mark_needed_node (vnode);
 	  gcc_assert (vnode->needed);
 	  pointer_set_insert (aliased_vnodes, vnode);
 	  if (dump_file)
Index: lto/lto.c
===================================================================
--- lto/lto.c	(revision 168508)
+++ lto/lto.c	(working copy)
@@ -837,6 +837,8 @@ partition_cgraph_node_p (struct cgraph_n
       || (DECL_COMDAT (node->decl)
 	  && !cgraph_used_from_object_file_p (node)))
     return false;
+  if (lookup_attribute ("weakref", DECL_ATTRIBUTES (node->decl)))
+    return false;
   return true;
 }
 
@@ -854,6 +856,8 @@ partition_varpool_node_p (struct varpool
 	  && !vnode->force_output
 	  && !varpool_used_from_object_file_p (vnode)))
     return false;
+  if (lookup_attribute ("weakref", DECL_ATTRIBUTES (vnode->decl)))
+    return false;
   return true;
 }
 
Index: passes.c
===================================================================
--- passes.c	(revision 168508)
+++ passes.c	(working copy)
@@ -144,6 +144,7 @@ rest_of_decl_compilation (tree decl,
 {
   /* We deferred calling assemble_alias so that we could collect
      other attributes such as visibility.  Emit the alias now.  */
+  if (!in_lto_p)
   {
     tree alias;
     alias = lookup_attribute ("alias", DECL_ATTRIBUTES (decl));
Index: varasm.c
===================================================================
*** varasm.c	(revision 168508)
--- varasm.c	(working copy)
*************** do_assemble_alias (tree decl, tree targe
*** 5504,5515 ****
  #endif
  }
  
- /* Derived type for use by compute_visible_aliases and callers.  A symbol
-    alias set is a pointer set into which we enter IDENTIFIER_NODES bearing
-    the canonicalised assembler-level symbol names corresponding to decls
-    and their aliases.  */
- 
- typedef struct pointer_set_t symbol_alias_set_t;
  
  /* Allocate and construct a symbol alias set.  */
  
--- 5504,5509 ----
*************** symbol_alias_set_create (void)
*** 5521,5527 ****
  
  /* Destruct and free a symbol alias set.  */
  
! static void
  symbol_alias_set_destroy (symbol_alias_set_t *aset)
  {
    pointer_set_destroy (aset);
--- 5515,5521 ----
  
  /* Destruct and free a symbol alias set.  */
  
! void
  symbol_alias_set_destroy (symbol_alias_set_t *aset)
  {
    pointer_set_destroy (aset);
*************** symbol_alias_set_destroy (symbol_alias_s
*** 5529,5535 ****
  
  /* Test if a symbol alias set contains a given name.  */
  
! static int
  symbol_alias_set_contains (const symbol_alias_set_t *aset, tree t)
  {
    /* We accept either a DECL or an IDENTIFIER directly.  */
--- 5523,5529 ----
  
  /* Test if a symbol alias set contains a given name.  */
  
! int
  symbol_alias_set_contains (const symbol_alias_set_t *aset, tree t)
  {
    /* We accept either a DECL or an IDENTIFIER directly.  */
*************** symbol_alias_set_insert (symbol_alias_se
*** 5551,5590 ****
    return pointer_set_insert (aset, t);
  }
  
! /* Compute the set of indentifier nodes that is generated by aliases
!    whose targets are reachable.  */
  
  static symbol_alias_set_t *
! compute_visible_aliases (void)
  {
!   symbol_alias_set_t *visible;
    unsigned i;
    alias_pair *p;
    bool changed;
  
!   /* We have to compute the set of visible nodes including aliases
!      themselves.  */
!   visible = symbol_alias_set_create ();
    do
      {
        changed = false;
        for (i = 0; VEC_iterate (alias_pair, alias_pairs, i, p); ++i)
! 	{
! 	  struct cgraph_node *fnode = NULL;
! 	  struct varpool_node *vnode = NULL;
  
! 	  fnode = cgraph_node_for_asm (p->target);
! 	  vnode = (fnode == NULL) ? varpool_node_for_asm (p->target) : NULL;
! 	  if ((fnode
! 	       || vnode
! 	       || symbol_alias_set_contains (visible, p->target))
! 	      && !symbol_alias_set_insert (visible, p->decl))
! 	    changed = true;
! 	}
      }
    while (changed);
  
!   return visible;
  }
  
  /* Remove the alias pairing for functions that are no longer in the call
--- 5545,5654 ----
    return pointer_set_insert (aset, t);
  }
  
! /* IN_SET_P is a predicate function assuming to be taken
!    alias_pair->decl, alias_pair->target and DATA arguments.
! 
!    Compute set of aliases by including everything where TRIVIALLY_VISIBLE
!    predeicate is true and propagate across aliases such that when
!    alias DECL is included, its TARGET is included too.  */
  
  static symbol_alias_set_t *
! propagate_aliases_forward (bool (*in_set_p)
! 			     (tree decl, tree target, void *data),
! 		           void *data)
  {
!   symbol_alias_set_t *set;
    unsigned i;
    alias_pair *p;
    bool changed;
  
!   set = symbol_alias_set_create ();
!   for (i = 0; VEC_iterate (alias_pair, alias_pairs, i, p); ++i)
!     if (in_set_p (p->decl, p->target, data))
!       symbol_alias_set_insert (set, p->decl);
    do
      {
        changed = false;
        for (i = 0; VEC_iterate (alias_pair, alias_pairs, i, p); ++i)
! 	if (symbol_alias_set_contains (set, p->decl)
! 	    && !symbol_alias_set_insert (set, p->target))
! 	  changed = true;
!     }
!   while (changed);
  
!   return set;
! }
! 
! /* Like propagate_aliases_forward but do backward propagation.  */
! 
! symbol_alias_set_t *
! propagate_aliases_backward (bool (*in_set_p)
! 			     (tree decl, tree target, void *data),
! 		           void *data)
! {
!   symbol_alias_set_t *set;
!   unsigned i;
!   alias_pair *p;
!   bool changed;
! 
!   /* We have to compute the set of set nodes including aliases
!      themselves.  */
!   set = symbol_alias_set_create ();
!   for (i = 0; VEC_iterate (alias_pair, alias_pairs, i, p); ++i)
!     if (in_set_p (p->decl, p->target, data))
!       symbol_alias_set_insert (set, p->target);
!   do
!     {
!       changed = false;
!       for (i = 0; VEC_iterate (alias_pair, alias_pairs, i, p); ++i)
! 	if (symbol_alias_set_contains (set, p->target)
! 	    && !symbol_alias_set_insert (set, p->decl))
! 	  changed = true;
      }
    while (changed);
  
!   return set;
! }
! /* See if the alias is trivially visible.  This means
!      1) alias is expoerted from the unit or
!      2) alias is used in the code.
!    We assume that unused cgraph/varpool nodes has been
!    removed.
!    Used as callback for propagate_aliases.  */
! 
! static bool
! trivially_visible_alias (tree decl, tree target ATTRIBUTE_UNUSED,
! 			 void *data ATTRIBUTE_UNUSED)
! {
!   struct cgraph_node *fnode = NULL;
!   struct varpool_node *vnode = NULL;
! 
!   if (!TREE_PUBLIC (decl))
!     {
!       if (TREE_CODE (decl) == FUNCTION_DECL)
! 	fnode = cgraph_get_node (decl);
!       else
! 	vnode = varpool_get_node (decl);
!       return vnode || fnode;
!     }
!   else
!     return true;
! }
! 
! /* See if the target of alias is defined in this unit.
!    Used as callback for propagate_aliases.  */
! 
! static bool
! trivially_defined_alias (tree decl ATTRIBUTE_UNUSED,
! 			 tree target,
! 			 void *data ATTRIBUTE_UNUSED)
! {
!   struct cgraph_node *fnode = NULL;
!   struct varpool_node *vnode = NULL;
! 
!   fnode = cgraph_node_for_asm (target);
!   vnode = (fnode == NULL) ? varpool_node_for_asm (target) : NULL;
!   return (fnode && fnode->analyzed) || (vnode && vnode->finalized);
  }
  
  /* Remove the alias pairing for functions that are no longer in the call
*************** remove_unreachable_alias_pairs (void)
*** 5602,5624 ****
  
    /* We have to compute the set of visible nodes including aliases
       themselves.  */
!   visible = compute_visible_aliases ();
  
    for (i = 0; VEC_iterate (alias_pair, alias_pairs, i, p); )
      {
!       if (!DECL_EXTERNAL (p->decl))
  	{
! 	  struct cgraph_node *fnode = NULL;
! 	  struct varpool_node *vnode = NULL;
! 	  fnode = cgraph_node_for_asm (p->target);
! 	  vnode = (fnode == NULL) ? varpool_node_for_asm (p->target) : NULL;
! 	  if (!fnode
! 	      && !vnode
! 	      && !symbol_alias_set_contains (visible, p->target))
! 	    {
! 	      VEC_unordered_remove (alias_pair, alias_pairs, i);
! 	      continue;
! 	    }
  	}
  
        i++;
--- 5666,5680 ----
  
    /* We have to compute the set of visible nodes including aliases
       themselves.  */
!   visible = propagate_aliases_forward (trivially_visible_alias, NULL);
  
    for (i = 0; VEC_iterate (alias_pair, alias_pairs, i, p); )
      {
!       if (!DECL_EXTERNAL (p->decl)
! 	  && !symbol_alias_set_contains (visible, p->decl))
  	{
! 	  VEC_unordered_remove (alias_pair, alias_pairs, i);
! 	  continue;
  	}
  
        i++;
*************** remove_unreachable_alias_pairs (void)
*** 5634,5649 ****
  void
  finish_aliases_1 (void)
  {
!   symbol_alias_set_t *visible;
    unsigned i;
    alias_pair *p;
  
    if (alias_pairs == NULL)
      return;
  
!   /* We have to compute the set of visible nodes including aliases
       themselves.  */
!   visible = compute_visible_aliases ();
  
    FOR_EACH_VEC_ELT (alias_pair, alias_pairs, i, p)
      {
--- 5690,5705 ----
  void
  finish_aliases_1 (void)
  {
!   symbol_alias_set_t *defined;
    unsigned i;
    alias_pair *p;
  
    if (alias_pairs == NULL)
      return;
  
!   /* We have to compute the set of defined nodes including aliases
       themselves.  */
!   defined = propagate_aliases_backward (trivially_defined_alias, NULL);
  
    FOR_EACH_VEC_ELT (alias_pair, alias_pairs, i, p)
      {
*************** finish_aliases_1 (void)
*** 5652,5658 ****
        target_decl = find_decl_and_mark_needed (p->decl, p->target);
        if (target_decl == NULL)
  	{
! 	  if (symbol_alias_set_contains (visible, p->target))
  	    continue;
  
  	  if (! (p->emitted_diags & ALIAS_DIAG_TO_UNDEF)
--- 5708,5714 ----
        target_decl = find_decl_and_mark_needed (p->decl, p->target);
        if (target_decl == NULL)
  	{
! 	  if (symbol_alias_set_contains (defined, p->target))
  	    continue;
  
  	  if (! (p->emitted_diags & ALIAS_DIAG_TO_UNDEF)
*************** finish_aliases_1 (void)
*** 5678,5684 ****
  	}
      }
  
!   symbol_alias_set_destroy (visible);
  }
  
  /* Second pass of completing pending aliases.  Emit the actual assembly.
--- 5734,5740 ----
  	}
      }
  
!   symbol_alias_set_destroy (defined);
  }
  
  /* Second pass of completing pending aliases.  Emit the actual assembly.
Index: testsuite/gcc.dg/lto/pr45721_0.c
===================================================================
*** testsuite/gcc.dg/lto/pr45721_0.c	(revision 0)
--- testsuite/gcc.dg/lto/pr45721_0.c	(revision 0)
***************
*** 0 ****
--- 1,4 ----
+ /* { dg-lto-do assemble }  */
+ void baz(void) {}
+ void *y = (void *)baz;
+ int main () { return 0; }
Index: testsuite/gcc.dg/lto/pr45721_1.c
===================================================================
*** testsuite/gcc.dg/lto/pr45721_1.c	(revision 0)
--- testsuite/gcc.dg/lto/pr45721_1.c	(revision 0)
***************
*** 0 ****
--- 1,2 ----
+ static void bar(void) __attribute__ ((weakref("baz")));
+ void *x = (void *)bar;