Fix unresolved symbols during Mozilla WHOPR build

Hi,
Mozilla fails to build with WHOPR on undefined symbols.  The symbol belongs
to COMDAT function that ends up being used in one ltrans and defined in another.

In normal compilation this never happens, since we define comdat functions in every
unit referring it and it seems that the same has to be done in WHOPR partitioning
too, since linker drops the comdat sections if they are not used in same unit.

This patch updated partitioning algorithm to put COMDAT function into every
partition that refers to it.  This shown latent bug in referenced_from_other_partition_p
logic that assume that if function is found in current partition, it is not part
of other partition.  This is not correct for functions present in multiple partitions.

Since the predicate sees one partition at a time (and I think it is good idea
to do so), I need to record what nodes are present in multiple units.  I ended
up using in_other_partition flg for this purpose during WPA stage.

When inserting node, first time I set aux pointer to the corresponding partition
and when we insert it into second partiiton, we set the flag.

Bootstrapped/regtested x86_64-linux.  I also tested it on mozilla build (that
still fails but for other reasons) and I am running WHOPR bootstrap.  OK if that passes?

Honza

	* cgraph.h (cgraph_node, cgraph_varpool_node): Update docmentation of
	in_other_partition.
	* lto-cgraph.c (referenced_from_other_partition_p,
	reachable_from_other_partition_p): Use in_other_partition flags.
	(output_node, output_varpool_node): COMDAT nodes always have private
	copies and thus are never used from other partition.

	* lto.c (add_cgraph_node_to_partition): Forward declare; walk also
	nodes from same comdat group as well as all comdat functions referenced
	here.
	(add_varpool_node_to_partition, add_references_to_partition): New function.
	(lto_1_1_map): Skip COMDAT fnctions/variables; use add_varpool_node_to_partition;
	clear aux flags when done.
	(lto_promote_cross_file_statics): Do not promote stuff that gets duplicated to
	each ltrans.

On Mon, 5 Jul 2010, Jan Hubicka wrote:

> Hi,
> Mozilla fails to build with WHOPR on undefined symbols.  The symbol belongs
> to COMDAT function that ends up being used in one ltrans and defined in another.
> 
> In normal compilation this never happens, since we define comdat functions in every
> unit referring it and it seems that the same has to be done in WHOPR partitioning
> too, since linker drops the comdat sections if they are not used in same unit.
> 
> This patch updated partitioning algorithm to put COMDAT function into every
> partition that refers to it.  This shown latent bug in referenced_from_other_partition_p
> logic that assume that if function is found in current partition, it is not part
> of other partition.  This is not correct for functions present in multiple partitions.
> 
> Since the predicate sees one partition at a time (and I think it is good idea
> to do so), I need to record what nodes are present in multiple units.  I ended
> up using in_other_partition flg for this purpose during WPA stage.
> 
> When inserting node, first time I set aux pointer to the corresponding partition
> and when we insert it into second partiiton, we set the flag.
> 
> Bootstrapped/regtested x86_64-linux.  I also tested it on mozilla build (that
> still fails but for other reasons) and I am running WHOPR bootstrap.  OK if that passes?
> 
> Honza
> 
> 	* cgraph.h (cgraph_node, cgraph_varpool_node): Update docmentation of
> 	in_other_partition.
> 	* lto-cgraph.c (referenced_from_other_partition_p,
> 	reachable_from_other_partition_p): Use in_other_partition flags.
> 	(output_node, output_varpool_node): COMDAT nodes always have private
> 	copies and thus are never used from other partition.
> 
> 	* lto.c (add_cgraph_node_to_partition): Forward declare; walk also
> 	nodes from same comdat group as well as all comdat functions referenced
> 	here.
> 	(add_varpool_node_to_partition, add_references_to_partition): New function.
> 	(lto_1_1_map): Skip COMDAT fnctions/variables; use add_varpool_node_to_partition;
> 	clear aux flags when done.
> 	(lto_promote_cross_file_statics): Do not promote stuff that gets duplicated to
> 	each ltrans.
> Index: cgraph.h
> ===================================================================
> --- cgraph.h	(revision 161812)
> +++ cgraph.h	(working copy)
> @@ -286,7 +286,9 @@
>    /* Set once the function has been instantiated and its callee
>       lists created.  */
>    unsigned analyzed : 1;
> -  /* Set when function is available in the other LTRANS partition.  */
> +  /* Set when function is available in the other LTRANS partition.  
> +     During WPA output it is used to mark nodes that are present in
> +     multiple partitions.  */
>    unsigned in_other_partition : 1;
>    /* Set when function is scheduled to be processed by local passes.  */
>    unsigned process : 1;
> @@ -497,7 +499,9 @@
>    unsigned alias : 1;
>    /* Set when variable is used from other LTRANS partition.  */
>    unsigned used_from_other_partition : 1;
> -  /* Set when variable is available in the other LTRANS partition.  */
> +  /* Set when variable is available in the other LTRANS partition.
> +     During WPA output it is used to mark nodes that are present in
> +     multiple partitions.  */
>    unsigned in_other_partition : 1;
>  };
>  
> @@ -556,6 +560,7 @@
>  struct cgraph_edge *cgraph_create_indirect_edge (struct cgraph_node *, gimple, int,
>  						 gcov_type, int, int);
>  struct cgraph_node * cgraph_get_node (tree);
> +struct cgraph_node * cgraph_get_node_or_alias (tree);
>  struct cgraph_node *cgraph_node (tree);
>  bool cgraph_same_body_alias (tree, tree);
>  void cgraph_add_thunk (tree, tree, bool, HOST_WIDE_INT, HOST_WIDE_INT, tree, tree);
> Index: lto-cgraph.c
> ===================================================================
> --- lto-cgraph.c	(revision 161812)
> +++ lto-cgraph.c	(working copy)
> @@ -319,13 +319,15 @@
>      {
>        if (ref->refering_type == IPA_REF_CGRAPH)
>  	{
> -	  if (!cgraph_node_in_set_p (ipa_ref_refering_node (ref), set))
> +	  if (ipa_ref_refering_node (ref)->in_other_partition
> +	      || !cgraph_node_in_set_p (ipa_ref_refering_node (ref), set))
>  	    return true;
>  	}
>        else
>  	{
> -	  if (!varpool_node_in_set_p (ipa_ref_refering_varpool_node (ref),
> -				      vset))
> +	  if (ipa_ref_refering_varpool_node (ref)->in_other_partition
> +	      || !varpool_node_in_set_p (ipa_ref_refering_varpool_node (ref),
> +				         vset))
>  	    return true;
>  	}
>      }
> @@ -343,7 +345,8 @@
>    if (node->global.inlined_to)
>      return false;
>    for (e = node->callers; e; e = e->next_caller)
> -    if (!cgraph_node_in_set_p (e->caller, set))
> +    if (e->caller->in_other_partition
> +	|| !cgraph_node_in_set_p (e->caller, set))
>        return true;
>    return false;
>  }
> @@ -503,6 +506,7 @@
>    bp_pack_value (&bp, node->abstract_and_needed, 1);
>    bp_pack_value (&bp, tag == LTO_cgraph_analyzed_node
>  		 && !DECL_EXTERNAL (node->decl)
> +		 && !DECL_COMDAT (node->decl)
>  		 && (reachable_from_other_partition_p (node, set)
>  		     || referenced_from_other_partition_p (&node->ref_list, set, vset)), 1);
>    bp_pack_value (&bp, node->lowered, 1);
> @@ -576,7 +580,8 @@
>    /* Constant pool initializers can be de-unified into individual ltrans units.
>       FIXME: Alternatively at -Os we may want to avoid generating for them the local
>       labels and share them across LTRANS partitions.  */
> -  if (DECL_IN_CONSTANT_POOL (node->decl))
> +  if (DECL_IN_CONSTANT_POOL (node->decl)
> +      && !DECL_COMDAT (node->decl))
>      {
>        bp_pack_value (&bp, 0, 1);  /* used_from_other_parition.  */
>        bp_pack_value (&bp, 0, 1);  /* in_other_partition.  */
> Index: lto/lto.c
> ===================================================================
> --- lto/lto.c	(revision 161812)
> +++ lto/lto.c	(working copy)
> @@ -525,6 +525,9 @@
>  
>  static GTY (()) VEC(ltrans_partition, gc) *ltrans_partitions;
>  
> +static void add_cgraph_node_to_partition (ltrans_partition part, struct cgraph_node *node);
> +static void add_varpool_node_to_partition (ltrans_partition part, struct varpool_node *vnode);
> +
>  /* Create new partition with name NAME.  */
>  static ltrans_partition
>  new_partition (const char *name)
> @@ -538,19 +541,79 @@
>    return part;
>  }
>  
> -/* Add NODE to partition as well as the inline callees into partition PART. */
> +/* See all references that go to comdat objects and bring them into partition too.  */

Watch long lines (get yourself a terminal with 80 columns please).

> +static void
> +add_references_to_partition (ltrans_partition part, struct ipa_ref_list *refs)
> +{
> +  int i;
> +  struct ipa_ref *ref;
> +  for (i = 0; ipa_ref_list_reference_iterate (refs, i, ref); i++)
> +    {
> +      if (ref->refered_type == IPA_REF_CGRAPH
> +	  && DECL_COMDAT (ipa_ref_node (ref)->decl)
> +	  && !cgraph_node_in_set_p (ipa_ref_node (ref), part->cgraph_set))
> +	add_cgraph_node_to_partition (part, ipa_ref_node (ref));
> +      else
> +	if (ref->refered_type == IPA_REF_VARPOOL
> +	    && DECL_COMDAT (ipa_ref_varpool_node (ref)->decl)
> +	    && !varpool_node_in_set_p (ipa_ref_varpool_node (ref), part->varpool_set))
> +	  add_varpool_node_to_partition (part, ipa_ref_varpool_node (ref));

Do we need to make sure to add all members of a comdat group here?

> +    }
> +}
>  
> +/* Add NODE to partition as well as the inline callees and referred comdats into partition PART. */
> +
>  static void
>  add_cgraph_node_to_partition (ltrans_partition part, struct cgraph_node *node)
>  {
>    struct cgraph_edge *e;
> +
>    part->insns += node->local.inline_summary.self_size;
> +
> +  if (node->aux)
> +    {
> +      gcc_assert (node->aux != part);
> +      node->in_other_partition = 1;
> +    }
> +  else
> +    node->aux = part;
> +
>    cgraph_node_set_add (part->cgraph_set, node);
> +
>    for (e = node->callees; e; e = e->next_callee)
> -    if (!e->inline_failed)
> +    if ((!e->inline_failed || DECL_ONE_ONLY (e->callee->decl))
> +	&& !cgraph_node_in_set_p (e->callee, part->cgraph_set))
>        add_cgraph_node_to_partition (part, e->callee);
> +
> +  add_references_to_partition (part, &node->ref_list);
> +
> +  if (node->same_comdat_group
> +      && !cgraph_node_in_set_p (node->same_comdat_group, part->cgraph_set))
> +    add_cgraph_node_to_partition (part, node->same_comdat_group);
>  }
>  
> +/* Add VNODE to partition as well as comdat references partition PART. */
> +
> +static void
> +add_varpool_node_to_partition (ltrans_partition part, struct varpool_node *vnode)
> +{
> +  varpool_node_set_add (part->varpool_set, vnode);
> +
> +  if (vnode->aux)
> +    {
> +      gcc_assert (vnode->aux != part);
> +      vnode->in_other_partition = 1;
> +    }
> +  else
> +    vnode->aux = part;
> +
> +  add_references_to_partition (part, &vnode->ref_list);
> +
> +  if (vnode->same_comdat_group
> +      && !varpool_node_in_set_p (vnode->same_comdat_group, part->varpool_set))
> +    add_varpool_node_to_partition (part, vnode->same_comdat_group);
> +}
> +
>  /* Group cgrah nodes by input files.  This is used mainly for testing
>     right now.  */
>  
> @@ -577,6 +640,10 @@

diff -c please ...

>        /* Nodes without a body do not need partitioning.  */
>        if (!node->analyzed)
>  	continue;
> +      /* Extern inlines and comdat are always only in partitions they are needed.  */
> +      if (DECL_EXTERNAL (node->decl)
> +	  || DECL_COMDAT (node->decl))
> +	continue;
>  
>        file_data = node->local.lto_file_data;
>        gcc_assert (!node->same_body_alias && file_data);
> @@ -599,6 +666,10 @@
>      {
>        if (vnode->alias || !vnode->needed)
>  	continue;
> +      /* Constant pool and comdat are always only in partitions they are needed.  */
> +      if (DECL_IN_CONSTANT_POOL (vnode->decl)
> +	  || DECL_COMDAT (vnode->decl))
> +	continue;
>        file_data = vnode->lto_file_data;
>        slot = pointer_map_contains (pmap, file_data);
>        if (slot)
> @@ -611,8 +682,12 @@
>  	  npartitions++;
>  	}
>  
> -      varpool_node_set_add (partition->varpool_set, vnode);
> +      add_varpool_node_to_partition (partition, vnode);
>      }
> +  for (node = cgraph_nodes; node; node = node->next)
> +    node->aux = NULL;
> +  for (vnode = varpool_nodes; vnode; vnode = vnode->next)
> +    vnode->aux = NULL;
>  
>    /* If the cgraph is empty, create one cgraph node set so that there is still
>       an output file for any variables that need to be exported in a DSO.  */
> @@ -704,7 +779,7 @@
>  	    continue;
>  	  if (node->global.inlined_to)
>  	    continue;
> -	  if (!DECL_EXTERNAL (node->decl)
> +	  if ((!DECL_EXTERNAL (node->decl) && !DECL_COMDAT (node->decl))
>  	      && (referenced_from_other_partition_p (&node->ref_list, set, vset)
>  		  || reachable_from_other_partition_p (node, set)))
>  	    promote_fn (node);
> @@ -715,10 +790,10 @@
>  	  /* Constant pool references use internal labels and thus can not
>  	     be made global.  It is sensible to keep those ltrans local to
>  	     allow better optimization.  */
> -	  if (!DECL_IN_CONSTANT_POOL (vnode->decl)
> -	     && !vnode->externally_visible && vnode->analyzed
> -	     && referenced_from_other_partition_p (&vnode->ref_list,
> -						   set, vset))
> +	  if (!DECL_IN_CONSTANT_POOL (vnode->decl) && !DECL_COMDAT (vnode->decl)
> +	      && !vnode->externally_visible && vnode->analyzed
> +	      && referenced_from_other_partition_p (&vnode->ref_list,
> +						    set, vset))
>  	    promote_var (vnode);
>  	}

Ok.

Thanks,
Richard.

> > +static void
> > +add_references_to_partition (ltrans_partition part, struct ipa_ref_list *refs)
> > +{
> > +  int i;
> > +  struct ipa_ref *ref;
> > +  for (i = 0; ipa_ref_list_reference_iterate (refs, i, ref); i++)
> > +    {
> > +      if (ref->refered_type == IPA_REF_CGRAPH
> > +	  && DECL_COMDAT (ipa_ref_node (ref)->decl)
> > +	  && !cgraph_node_in_set_p (ipa_ref_node (ref), part->cgraph_set))
> > +	add_cgraph_node_to_partition (part, ipa_ref_node (ref));
> > +      else
> > +	if (ref->refered_type == IPA_REF_VARPOOL
> > +	    && DECL_COMDAT (ipa_ref_varpool_node (ref)->decl)
> > +	    && !varpool_node_in_set_p (ipa_ref_varpool_node (ref), part->varpool_set))
> > +	  add_varpool_node_to_partition (part, ipa_ref_varpool_node (ref));
> 
> Do we need to make sure to add all members of a comdat group here?

I think so, yes.  We still need to play that comdat group game correctly.  Adding just part
of comdat group would result in incorrect linking.
With 1-1 map the problem never happens.
> 
> diff -c please ...

This is svn setup on evans.  I fixed it now.

Honza