Fix undefined symbols seen in Mozilla LTO build

[Jan Hubicka <hubicka at ucw dot cz>]

Hi,
this patch makes Mozilla to build again with LTO at mainline.

The problem is very, well, interesting and kept me busy for few days.

What happens is that C++ FE finalizes destructor of gfxUnknownSurface despite
the fact that this function is not reachable in its FE reachability analysis.
Consequently the destructor is not seen by the reachability analysis and it
does use vtable for gfxUnknownSurface that gets "optimized" out in C++ FE in a
way it never calls varpool_finalize_decl on it.

Both the vtable and function are comdat.  Now we end up with referenced but
finalized variable in the code. In normal compilation this is not problem even
at -O0 because we do remove unreachable comdats and thus we never end up
referencing the vtable.

Things go wrong at LTO plugin path.

Code removing unreachable functions now holds virtual functions after inlining
in hope they will be devirtualized. Consequently we end up seeing this
constructor and vtable at the time we produce LTO symtable. Therefore we put
the function and vtable into symbol table.  It is because function is
referenced by the vtable and thus has address taken. Otherwise we would play
the trick with keeping the comdat unannounced.

This leads to the known problem with linker plugin and the fact that all
COMDATs gets automatically PREVAILING_DEF and thus must say in the program
even if they are unused.

>From this point we need to output the destructor.  Because the vtable is still
unfinalized and it is not used elsewhere we finally result in undefined symbol
reference.

This patch does not address the original C++ problem I will write verifier for
and will try to get better testcase (basically later in the game every
non-external variable must be finalized).  The patch makes the destructor to
be optimized out at linktime in same way as in non-LTO optimization.

I take into account the fact that references from vtables do not need to be
unique and thus they still can be unsahred. Same way I keep vtables unshared.
This was discussed during the summit as valid transform.

Bootstrapped/regtested x86_64-linux and tested with the mozilla build.
Will commit it shortly.

	* cgraph.c (ld_plugin_symbol_resolution_names): New.
	(dump_cgraph_node): Dump resolution.
	* cgraph.h (ld_plugin_symbol_resolution_names): Declare.
	(cgraph_comdat_can_be_unshared_p): Dclare.
	* lto-streamer-out.c (produce_symtab): Use
	cgraph_comdat_can_be_unshared_p.
	* ipa.c (cgraph_address_taken_from_non_vtable_p): New function.
	(cgraph_comdat_can_be_unshared_p): New function based on logic
	in cgraph_externally_visible_p.
	(cgraph_externally_visible_p): Use it.
	(varpool_externally_visible_p): Virtual tables can be unshared.
	* varpool.c (dump_varpool_node): Dump resolution.

Index: cgraph.c
===================================================================
*** cgraph.c	(revision 166945)
--- cgraph.c	(working copy)
*************** The callgraph:
*** 99,104 ****
--- 99,117 ----
  #include "ipa-utils.h"
  #include "lto-streamer.h"
  
+ const char * const ld_plugin_symbol_resolution_names[]=
+ {
+   "",
+   "undef",
+   "prevailing_def",
+   "prevailing_def_ironly",
+   "preempted_reg",
+   "preempted_ir",
+   "resolved_ir",
+   "resolved_exec",
+   "resolved_dyn"
+ };
+ 
  static void cgraph_node_remove_callers (struct cgraph_node *node);
  static inline void cgraph_edge_remove_caller (struct cgraph_edge *e);
  static inline void cgraph_edge_remove_callee (struct cgraph_edge *e);
*************** dump_cgraph_node (FILE *f, struct cgraph
*** 1866,1871 ****
--- 1879,1887 ----
      fprintf (f, " local");
    if (node->local.externally_visible)
      fprintf (f, " externally_visible");
+   if (node->resolution != LDPR_UNKNOWN)
+     fprintf (f, " %s",
+  	     ld_plugin_symbol_resolution_names[(int)node->resolution]);
    if (node->local.finalized)
      fprintf (f, " finalized");
    if (node->local.disregard_inline_limits)
Index: cgraph.h
===================================================================
*** cgraph.h	(revision 166945)
--- cgraph.h	(working copy)
*************** enum availability
*** 56,61 ****
--- 56,62 ----
  struct lto_file_decl_data;
  
  extern const char * const cgraph_availability_names[];
+ extern const char * const ld_plugin_symbol_resolution_names[];
  
  /* Function inlining information.  */
  
*************** void varpool_node_set_remove (varpool_no
*** 695,700 ****
--- 696,702 ----
  void dump_varpool_node_set (FILE *, varpool_node_set);
  void debug_varpool_node_set (varpool_node_set);
  void ipa_discover_readonly_nonaddressable_vars (void);
+ bool cgraph_comdat_can_be_unshared_p (struct cgraph_node *);
  
  /* In predict.c  */
  bool cgraph_maybe_hot_edge_p (struct cgraph_edge *e);
Index: lto-streamer-out.c
===================================================================
*** lto-streamer-out.c	(revision 166945)
--- lto-streamer-out.c	(working copy)
*************** produce_symtab (struct output_block *ob,
*** 2492,2498 ****
        if (DECL_EXTERNAL (node->decl))
  	continue;
        if (DECL_COMDAT (node->decl)
! 	  && cgraph_can_remove_if_no_direct_calls_p (node))
  	continue;
        if (node->alias || node->global.inlined_to)
  	continue;
--- 2492,2498 ----
        if (DECL_EXTERNAL (node->decl))
  	continue;
        if (DECL_COMDAT (node->decl)
! 	  && cgraph_comdat_can_be_unshared_p (node))
  	continue;
        if (node->alias || node->global.inlined_to)
  	continue;
*************** produce_symtab (struct output_block *ob,
*** 2506,2512 ****
        if (!DECL_EXTERNAL (node->decl))
  	continue;
        if (DECL_COMDAT (node->decl)
! 	  && cgraph_can_remove_if_no_direct_calls_p (node))
  	continue;
        if (node->alias || node->global.inlined_to)
  	continue;
--- 2506,2512 ----
        if (!DECL_EXTERNAL (node->decl))
  	continue;
        if (DECL_COMDAT (node->decl)
! 	  && cgraph_comdat_can_be_unshared_p (node))
  	continue;
        if (node->alias || node->global.inlined_to)
  	continue;
*************** produce_symtab (struct output_block *ob,
*** 2521,2526 ****
--- 2521,2534 ----
        vnode = lto_varpool_encoder_deref (varpool_encoder, i);
        if (DECL_EXTERNAL (vnode->decl))
  	continue;
+       /* COMDAT virtual tables can be unshared.  Do not declare them
+ 	 in the LTO symbol table to prevent linker from forcing them
+ 	 into the output. */
+       if (DECL_COMDAT (vnode->decl)
+ 	  && !vnode->force_output
+ 	  && vnode->finalized 
+ 	  && DECL_VIRTUAL_P (vnode->decl))
+ 	continue;
        if (vnode->alias)
  	continue;
        write_symbol (cache, &stream, vnode->decl, seen, false);
*************** produce_symtab (struct output_block *ob,
*** 2532,2537 ****
--- 2540,2550 ----
        vnode = lto_varpool_encoder_deref (varpool_encoder, i);
        if (!DECL_EXTERNAL (vnode->decl))
  	continue;
+       if (DECL_COMDAT (vnode->decl)
+ 	  && !vnode->force_output
+ 	  && vnode->finalized 
+ 	  && DECL_VIRTUAL_P (vnode->decl))
+ 	continue;
        if (vnode->alias)
  	continue;
        write_symbol (cache, &stream, vnode->decl, seen, false);
Index: ipa.c
===================================================================
*** ipa.c	(revision 166945)
--- ipa.c	(working copy)
*************** ipa_discover_readonly_nonaddressable_var
*** 588,593 ****
--- 588,643 ----
      fprintf (dump_file, "\n");
  }
  
+ /* Return true when there is a reference to node and it is not vtable.  */
+ static bool
+ cgraph_address_taken_from_non_vtable_p (struct cgraph_node *node)
+ {
+   int i;
+   struct ipa_ref *ref;
+   for (i = 0; ipa_ref_list_reference_iterate (&node->ref_list, i, ref); i++)
+     {
+       struct varpool_node *node;
+       if (ref->refered_type == IPA_REF_CGRAPH)
+ 	return true;
+       node = ipa_ref_varpool_node (ref);
+       if (!DECL_VIRTUAL_P (node->decl))
+ 	return true;
+     }
+   return false;
+ }
+ 
+ /* COMDAT functions must be shared only if they have address taken,
+    otherwise we can produce our own private implementation with
+    -fwhole-program.  
+    Return true when turning COMDAT functoin static can not lead to wrong
+    code when the resulting object links with a library defining same COMDAT.
+ 
+    Virtual functions do have their addresses taken from the vtables,
+    but in C++ there is no way to compare their addresses for equality.  */
+ 
+ bool
+ cgraph_comdat_can_be_unshared_p (struct cgraph_node *node)
+ {
+   if ((cgraph_address_taken_from_non_vtable_p (node)
+        && !DECL_VIRTUAL_P (node->decl))
+       || !node->analyzed)
+     return false;
+   if (node->same_comdat_group)
+     {
+       struct cgraph_node *next;
+ 
+       /* If more than one function is in the same COMDAT group, it must
+          be shared even if just one function in the comdat group has
+          address taken.  */
+       for (next = node->same_comdat_group;
+ 	   next != node; next = next->same_comdat_group)
+ 	if (cgraph_address_taken_from_non_vtable_p (node)
+ 	    && !DECL_VIRTUAL_P (next->decl))
+ 	  return false;
+     }
+   return true;
+ }
+ 
  /* Return true when function NODE should be considered externally visible.  */
  
  static bool
*************** cgraph_externally_visible_p (struct cgra
*** 613,618 ****
--- 663,677 ----
    if (lookup_attribute ("externally_visible", DECL_ATTRIBUTES (node->decl)))
      return true;
  
+   /* When doing LTO or whole program, we can bring COMDAT functoins static.
+      This improves code quality and we know we will duplicate them at most twice
+      (in the case that we are not using plugin and link with object file
+       implementing same COMDAT)  */
+   if ((in_lto_p || whole_program)
+       && DECL_COMDAT (node->decl)
+       && cgraph_comdat_can_be_unshared_p (node))
+     return false;
+ 
    /* See if we have linker information about symbol not being used or
       if we need to make guess based on the declaration.
  
*************** cgraph_externally_visible_p (struct cgra
*** 635,661 ****
      ;
    else if (!whole_program)
      return true;
-   /* COMDAT functions must be shared only if they have address taken,
-      otherwise we can produce our own private implementation with
-      -fwhole-program.  */
-   else if (DECL_COMDAT (node->decl))
-     {
-       if (node->address_taken || !node->analyzed)
- 	return true;
-       if (node->same_comdat_group)
- 	{
- 	  struct cgraph_node *next;
- 
- 	  /* If more than one function is in the same COMDAT group, it must
- 	     be shared even if just one function in the comdat group has
- 	     address taken.  */
- 	  for (next = node->same_comdat_group;
- 	       next != node;
- 	       next = next->same_comdat_group)
- 	    if (next->address_taken || !next->analyzed)
- 	      return true;
- 	}
-     }
  
    if (MAIN_NAME_P (DECL_NAME (node->decl)))
      return true;
--- 694,699 ----
*************** varpool_externally_visible_p (struct var
*** 701,706 ****
--- 739,754 ----
    if (!alias && vnode->resolution == LDPR_PREVAILING_DEF_IRONLY)
      return false;
  
+   /* As a special case, the COMDAT virutal tables can be unshared.
+      In LTO mode turn vtables into static variables.  The variable is readonly,
+      so this does not enable more optimization, but referring static var
+      is faster for dynamic linking.  Also this match logic hidding vtables
+      from LTO symbol tables.  */
+   if ((in_lto_p || flag_whole_program)
+       && !vnode->force_output
+       && DECL_COMDAT (vnode->decl) && DECL_VIRTUAL_P (vnode->decl))
+     return false;
+ 
    /* When doing link time optimizations, hidden symbols become local.  */
    if (in_lto_p
        && (DECL_VISIBILITY (vnode->decl) == VISIBILITY_HIDDEN
Index: varpool.c
===================================================================
*** varpool.c	(revision 166945)
--- varpool.c	(working copy)
*************** dump_varpool_node (FILE *f, struct varpo
*** 241,246 ****
--- 241,249 ----
      fprintf (f, " output");
    if (node->externally_visible)
      fprintf (f, " externally_visible");
+   if (node->resolution != LDPR_UNKNOWN)
+     fprintf (f, " %s",
+  	     ld_plugin_symbol_resolution_names[(int)node->resolution]);
    if (node->in_other_partition)
      fprintf (f, " in_other_partition");
    else if (node->used_from_other_partition)