Fix pure/const discovery WRT interposition part 1

[Jan Hubicka <hubicka at ucw dot cz>]

Hi,
this is preparation patch for fix for PR ipa/70018.  It adds
binds_to_current_def predicate that works just like decl_binds_to_current_def
but at symtab level.  The main change is that local binding depends on user
(if function refers itself and has no aliases, it must bind to current def
and likewise within the comdat group).

With followup patch I plan to disable const discovery for functions that are
not binding to current def (most C++ inlines without LTO!) and at least with
this chnage the patch does not disable detection on all self recursive
functions (which is surprisingly common case for libreoffice). See PR log for
details.

Next stage1 we can work harder and implement tracking of existence of memory
references down from pre-gimple stages.

The new code path with REF parameter is unused otherwise and the patch has
no effect by itself thus.

Bootstrapped/regtested x86_64-linux

Honza

	PR ipa/70018
	* cgraph.c (cgraph_node::get_availability): Add REF parameter.
	(cgraph_node::function_symbol): Likewise.
	(cgraph_node::function_or_virtual_thunk_symbol): Likewise.
	* cgraph.h (symtab_node::get_availabbility): Add REF parameter.
	(symtab_node::ultimate_alias_target): Add REF parameter.
	(symtab_node::binds_to_current_def_p): Declare.
	(symtab_node;:ultimate_alias_target_1): Add REF parameter.
	(cgraph_node::function_symbol): Likewise.
	(cgraph_node::function_or_virtual_thunk_symbol): Likewise.
	(cgraph_node::get_availability): Likewise.
	(cgraph_edge::binds_to_current_def_p): New inline function.
	(varpool_node::get_availability): Add REF parameter.
	(varpool_node::ultimate_alias_target): Likewise.
	* symtab.c (symtab_node::ultimate_alias_target_1): Likewise.
	(symtab_node::binds_to_current_def_p): Likewise.
	* varpool.c (varpool_node::get_availability): Likewise.
Index: cgraph.c
===================================================================
--- cgraph.c	(revision 234761)
+++ cgraph.c	(working copy)
@@ -2209,19 +2209,36 @@ cgraph_node::unnest (void)
 /* Return function availability.  See cgraph.h for description of individual
    return values.  */
 enum availability
-cgraph_node::get_availability (void)
+cgraph_node::get_availability (symtab_node *ref)
 {
+  if (ref)
+    {
+      cgraph_node *cref = dyn_cast <cgraph_node *> (ref);
+      if (cref)
+	ref = cref->global.inlined_to;
+    }
   enum availability avail;
   if (!analyzed)
     avail = AVAIL_NOT_AVAILABLE;
   else if (local.local)
     avail = AVAIL_LOCAL;
+  else if (global.inlined_to)
+    avail = AVAIL_AVAILABLE;
   else if (transparent_alias)
-    ultimate_alias_target (&avail);
+    ultimate_alias_target (&avail, ref);
   else if (lookup_attribute ("ifunc", DECL_ATTRIBUTES (decl)))
     avail = AVAIL_INTERPOSABLE;
   else if (!externally_visible)
     avail = AVAIL_AVAILABLE;
+  /* If this is a reference from symbol itself and there are no aliases, we
+     may be sure that the symbol was not interposed by soemthing else because
+     the symbol itself would be unreachable otherwise.
+
+     Also comdat groups are always resolved in groups.  */
+  else if ((this == ref && !has_aliases_p ())
+           || (ref && get_comdat_group ()
+               && get_comdat_group () == ref->get_comdat_group ()))
+    avail = AVAIL_AVAILABLE;
   /* Inline functions are safe to be analyzed even if their symbol can
      be overwritten at runtime.  It is not meaningful to enforce any sane
      behavior on replacing inline function by different body.  */
@@ -2232,11 +2249,7 @@ cgraph_node::get_availability (void)
      care at least of two notable extensions - the COMDAT functions
      used to share template instantiations in C++ (this is symmetric
      to code cp_cannot_inline_tree_fn and probably shall be shared and
-     the inlinability hooks completely eliminated).
-
-     ??? Does the C++ one definition rule allow us to always return
-     AVAIL_AVAILABLE here?  That would be good reason to preserve this
-     bit.  */
+     the inlinability hooks completely eliminated).  */
 
   else if (decl_replaceable_p (decl) && !DECL_EXTERNAL (decl))
     avail = AVAIL_INTERPOSABLE;
@@ -3250,24 +3286,28 @@ cgraph_node::verify_cgraph_nodes (void)
 
 /* Walk the alias chain to return the function cgraph_node is alias of.
    Walk through thunks, too.
-   When AVAILABILITY is non-NULL, get minimal availability in the chain.  */
+   When AVAILABILITY is non-NULL, get minimal availability in the chain.
+   When REF is non-NULL, assume that reference happens in symbol REF
+   when determining the availability.  */
 
 cgraph_node *
-cgraph_node::function_symbol (enum availability *availability)
+cgraph_node::function_symbol (enum availability *availability,
+			      struct symtab_node *ref)
 {
-  cgraph_node *node = ultimate_alias_target (availability);
+  cgraph_node *node = ultimate_alias_target (availability, ref);
 
   while (node->thunk.thunk_p)
     {
+      ref = node;
       node = node->callees->callee;
       if (availability)
 	{
 	  enum availability a;
-	  a = node->get_availability ();
+	  a = node->get_availability (ref);
 	  if (a < *availability)
 	    *availability = a;
 	}
-      node = node->ultimate_alias_target (availability);
+      node = node->ultimate_alias_target (availability, ref);
     }
   return node;
 }
@@ -3275,25 +3315,29 @@ cgraph_node::function_symbol (enum avail
 /* Walk the alias chain to return the function cgraph_node is alias of.
    Walk through non virtual thunks, too.  Thus we return either a function
    or a virtual thunk node.
-   When AVAILABILITY is non-NULL, get minimal availability in the chain.  */
+   When AVAILABILITY is non-NULL, get minimal availability in the chain. 
+   When REF is non-NULL, assume that reference happens in symbol REF
+   when determining the availability.  */
 
 cgraph_node *
 cgraph_node::function_or_virtual_thunk_symbol
-				(enum availability *availability)
+				(enum availability *availability,
+				 struct symtab_node *ref)
 {
-  cgraph_node *node = ultimate_alias_target (availability);
+  cgraph_node *node = ultimate_alias_target (availability, ref);
 
   while (node->thunk.thunk_p && !node->thunk.virtual_offset_p)
     {
+      ref = node;
       node = node->callees->callee;
       if (availability)
 	{
 	  enum availability a;
-	  a = node->get_availability ();
+	  a = node->get_availability (ref);
 	  if (a < *availability)
 	    *availability = a;
 	}
-      node = node->ultimate_alias_target (availability);
+      node = node->ultimate_alias_target (availability, ref);
     }
   return node;
 }
Index: cgraph.h
===================================================================
--- cgraph.h	(revision 234761)
+++ cgraph.h	(working copy)
@@ -242,8 +242,11 @@ public:
 
   /* Walk the alias chain to return the symbol NODE is alias of.
      If NODE is not an alias, return NODE.
-     When AVAILABILITY is non-NULL, get minimal availability in the chain.  */
-  symtab_node *ultimate_alias_target (enum availability *avail = NULL);
+     When AVAILABILITY is non-NULL, get minimal availability in the chain.
+     When REF is non-NULL, assume that reference happens in symbol REF
+     when determining the availability.  */
+  symtab_node *ultimate_alias_target (enum availability *avail = NULL,
+				      struct symtab_node *ref = NULL);
 
   /* Return next reachable static symbol with initializer after NODE.  */
   inline symtab_node *next_defined_symbol (void);
@@ -287,8 +290,13 @@ public:
   /* Return the initialization priority.  */
   priority_type get_init_priority ();
 
-  /* Return availability of NODE.  */
-  enum availability get_availability (void);
+  /* Return availability of NODE when referenced from REF.  */
+  enum availability get_availability (symtab_node *ref = NULL);
+
+  /* Return true if NODE binds to current definition in final executable
+     when referenced from REF.  If REF is NULL return conservative value
+     for any reference.  */
+  bool binds_to_current_def_p (symtab_node *ref = NULL);
 
   /* Make DECL local.  */
   void make_decl_local (void);
@@ -595,7 +604,8 @@ private:
   static bool noninterposable_alias (symtab_node *node, void *data);
 
   /* Worker for ultimate_alias_target.  */
-  symtab_node *ultimate_alias_target_1 (enum availability *avail = NULL);
+  symtab_node *ultimate_alias_target_1 (enum availability *avail = NULL,
+					symtab_node *ref = NULL);
 };
 
 inline void
@@ -862,15 +872,21 @@ public:
 
   /* Walk the alias chain to return the function cgraph_node is alias of.
      Walk through thunk, too.
-     When AVAILABILITY is non-NULL, get minimal availability in the chain.  */
-  cgraph_node *function_symbol (enum availability *avail = NULL);
+     When AVAILABILITY is non-NULL, get minimal availability in the chain. 
+     When REF is non-NULL, assume that reference happens in symbol REF
+     when determining the availability.  */
+  cgraph_node *function_symbol (enum availability *avail = NULL,
+				struct symtab_node *ref = NULL);
 
   /* Walk the alias chain to return the function cgraph_node is alias of.
      Walk through non virtual thunks, too.  Thus we return either a function
      or a virtual thunk node.
-     When AVAILABILITY is non-NULL, get minimal availability in the chain.  */
+     When AVAILABILITY is non-NULL, get minimal availability in the chain.  
+     When REF is non-NULL, assume that reference happens in symbol REF
+     when determining the availability.  */
   cgraph_node *function_or_virtual_thunk_symbol
-				(enum availability *avail = NULL);
+				(enum availability *avail = NULL,
+				 struct symtab_node *ref = NULL);
 
   /* Create node representing clone of N executed COUNT times.  Decrease
      the execution counts from original node too.
@@ -969,16 +985,19 @@ public:
 
   /* Given function symbol, walk the alias chain to return the function node
      is alias of. Do not walk through thunks.
-     When AVAILABILITY is non-NULL, get minimal availability in the chain.  */
+     When AVAILABILITY is non-NULL, get minimal availability in the chain.
+     When REF is non-NULL, assume that reference happens in symbol REF
+     when determining the availability.  */
 
-  cgraph_node *ultimate_alias_target (availability *availability = NULL);
+  cgraph_node *ultimate_alias_target (availability *availability = NULL,
+				      symtab_node *ref = NULL);
 
   /* Expand thunk NODE to gimple if possible.
      When FORCE_GIMPLE_THUNK is true, gimple thunk is created and
      no assembler is produced.
      When OUTPUT_ASM_THUNK is true, also produce assembler for
      thunks that are not lowered.  */
-  bool expand_thunk (bool output_asm_thunks, bool force_gimple_thunk);
+  bool expand_thunk (bool output_asm_thunks, bool force_gimple_thunk);
 
   /*  Call expand_thunk on all callers that are thunks and analyze those
       nodes that were expanded.  */
@@ -1084,7 +1104,7 @@ public:
 
   /* Return function availability.  See cgraph.h for description of individual
      return values.  */
-  enum availability get_availability (void);
+  enum availability get_availability (symtab_node *ref = NULL);
 
   /* Set TREE_NOTHROW on cgraph_node's decl and on aliases of the node
      if any to NOTHROW.  */
@@ -1684,6 +1704,9 @@ struct GTY((chain_next ("%h.next_caller"
      type.  */
   unsigned in_polymorphic_cdtor : 1;
 
+  /* Return true if call must bind to current definition.  */
+  bool binds_to_current_def_p ();
+
 private:
   /* Remove the edge from the list of the callers of the callee.  */
   void remove_caller (void);
@@ -1726,7 +1749,7 @@ public:
   void analyze (void);
 
   /* Return variable availability.  */
-  availability get_availability (void);
+  availability get_availability (symtab_node *ref = NULL);
 
   /* When doing LTO, read variable's constructor from disk if
      it is not already present.  */
@@ -1737,9 +1760,11 @@ public:
 
   /* For given variable pool node, walk the alias chain to return the function
      the variable is alias of. Do not walk through thunks.
-     When AVAILABILITY is non-NULL, get minimal availability in the chain.  */
+     When AVAILABILITY is non-NULL, get minimal availability in the chain.
+     When REF is non-NULL, assume that reference happens in symbol REF
+     when determining the availability.  */
   inline varpool_node *ultimate_alias_target
-    (availability *availability = NULL);
+    (availability *availability = NULL, symtab_node *ref = NULL);
 
   /* Return node that alias is aliasing.  */
   inline varpool_node *get_alias_target (void);
@@ -2883,30 +2908,36 @@ varpool_node::get_alias_target (void)
 
 /* Walk the alias chain to return the symbol NODE is alias of.
    If NODE is not an alias, return NODE.
-   When AVAILABILITY is non-NULL, get minimal availability in the chain.  */
+   When AVAILABILITY is non-NULL, get minimal availability in the chain.
+   When REF is non-NULL, assume that reference happens in symbol REF
+   when determining the availability.  */
 
 inline symtab_node *
-symtab_node::ultimate_alias_target (enum availability *availability)
+symtab_node::ultimate_alias_target (enum availability *availability,
+				    symtab_node *ref)
 {
   if (!alias)
     {
       if (availability)
-	*availability = get_availability ();
+	*availability = get_availability (ref);
       return this;
     }
 
-  return ultimate_alias_target_1 (availability);
+  return ultimate_alias_target_1 (availability, ref);
 }
 
 /* Given function symbol, walk the alias chain to return the function node
    is alias of. Do not walk through thunks.
-   When AVAILABILITY is non-NULL, get minimal availability in the chain.  */
+   When AVAILABILITY is non-NULL, get minimal availability in the chain.
+   When REF is non-NULL, assume that reference happens in symbol REF
+   when determining the availability.  */
 
 inline cgraph_node *
-cgraph_node::ultimate_alias_target (enum availability *availability)
+cgraph_node::ultimate_alias_target (enum availability *availability,
+				    symtab_node *ref)
 {
   cgraph_node *n = dyn_cast <cgraph_node *>
-    (symtab_node::ultimate_alias_target (availability));
+    (symtab_node::ultimate_alias_target (availability, ref));
   if (!n && availability)
     *availability = AVAIL_NOT_AVAILABLE;
   return n;
@@ -2914,13 +2945,16 @@ cgraph_node::ultimate_alias_target (enum
 
 /* For given variable pool node, walk the alias chain to return the function
    the variable is alias of. Do not walk through thunks.
-   When AVAILABILITY is non-NULL, get minimal availability in the chain.  */
+   When AVAILABILITY is non-NULL, get minimal availability in the chain.
+   When REF is non-NULL, assume that reference happens in symbol REF
+   when determining the availability.  */
 
 inline varpool_node *
-varpool_node::ultimate_alias_target (availability *availability)
+varpool_node::ultimate_alias_target (availability *availability,
+				     symtab_node *ref)
 {
   varpool_node *n = dyn_cast <varpool_node *>
-    (symtab_node::ultimate_alias_target (availability));
+    (symtab_node::ultimate_alias_target (availability, ref));
 
   if (!n && availability)
     *availability = AVAIL_NOT_AVAILABLE;
@@ -2980,6 +3014,17 @@ cgraph_edge::remove_callee (void)
     callee->callers = next_caller;
 }
 
+/* Return true if call must bind to current definition.  */
+
+inline bool
+cgraph_edge::binds_to_current_def_p ()
+{
+  if (callee)
+    return callee->binds_to_current_def_p (caller);
+  else
+    return NULL;
+}
+
 /* Return true if the TM_CLONE bit is set for a given FNDECL.  */
 static inline bool
 decl_is_tm_clone (const_tree fndecl)
@@ -3025,15 +3070,15 @@ symtab_node::get_create (tree node)
     return cgraph_node::get_create (node);
 }
 
-/* Return availability of NODE.  */
+/* Return availability of NODE when referenced from REF.  */
 
 inline enum availability
-symtab_node::get_availability (void)
+symtab_node::get_availability (symtab_node *ref)
 {
   if (is_a <cgraph_node *> (this))
-    return dyn_cast <cgraph_node *> (this)->get_availability ();
+    return dyn_cast <cgraph_node *> (this)->get_availability (ref);
   else
-    return dyn_cast <varpool_node *> (this)->get_availability ();
+    return dyn_cast <varpool_node *> (this)->get_availability (ref);
 }
 
 /* Call calback on symtab node and aliases associated to this node.
Index: symtab.c
===================================================================
--- symtab.c	(revision 234761)
+++ symtab.c	(working copy)
@@ -1347,7 +1347,8 @@ symtab_node::copy_visibility_from (symta
    Assumes NODE is known to be alias.  */
 
 symtab_node *
-symtab_node::ultimate_alias_target_1 (enum availability *availability)
+symtab_node::ultimate_alias_target_1 (enum availability *availability,
+				      symtab_node *ref)
 {
   bool transparent_p = false;
 
@@ -1368,7 +1369,7 @@ symtab_node::ultimate_alias_target_1 (en
     {
       transparent_p = transparent_alias;
       if (!transparent_p)
-	*availability = get_availability ();
+	*availability = get_availability (ref);
       else
 	*availability = AVAIL_NOT_AVAILABLE;
     }
@@ -1383,7 +1384,7 @@ symtab_node::ultimate_alias_target_1 (en
 	  if (!availability || (!transparent_p && node->analyzed))
 	    ;
 	  else if (node->analyzed && !node->transparent_alias)
-	    *availability = node->get_availability ();
+	    *availability = node->get_availability (ref);
 	  else
 	    *availability = AVAIL_NOT_AVAILABLE;
 	  return node;
@@ -1391,7 +1392,7 @@ symtab_node::ultimate_alias_target_1 (en
       if (node && availability && transparent_p
 	  && node->transparent_alias)
 	{
-	  *availability = node->get_availability ();
+	  *availability = node->get_availability (ref);
 	  transparent_p = false;
 	}
     }
@@ -2206,3 +2207,58 @@ symbol_table::symbol_suffix_separator ()
   return '_';
 #endif
 }
+
+/* Return true when references to this symbol from REF must bind to current
+   definition in final executable.  */
+
+bool
+symtab_node::binds_to_current_def_p (symtab_node *ref)
+{
+  if (!definition)
+    return false;
+  if (decl_binds_to_current_def_p (decl))
+    return true;
+
+  /* Inline clones always binds locally.  */
+  cgraph_node *cnode = dyn_cast <cgraph_node *> (this);
+  if (cnode && cnode->global.inlined_to)
+    return true;
+
+  if (DECL_EXTERNAL (decl))
+    return false;
+
+  if (!externally_visible)
+    debug ();
+  gcc_assert (externally_visible);
+
+  if (ref)
+    {
+      cgraph_node *cref = dyn_cast <cgraph_node *> (ref);
+      if (cref)
+	ref = cref->global.inlined_to;
+    }
+
+  /* If this is a reference from symbol itself and there are no aliases, we
+     may be sure that the symbol was not interposed by soemthing else because
+     the symbol itself would be unreachable otherwise.  This is important
+     to optimize recursive functions well.
+
+     This assumption may be broken by inlining: if symbol is interposable
+     but the body is available (i.e. declared inline), inliner may make
+     the body reachable even with interposition.  */
+  if (this == ref && !has_aliases_p ()
+      && (!cnode
+	  || symtab->state >= IPA_SSA_AFTER_INLINING
+	  || get_availability () >= AVAIL_INTERPOSABLE))
+    return true;
+
+
+  /* References within one comdat group are always bound in a group.  */
+  if (ref
+      && symtab->state >= IPA_SSA_AFTER_INLINING
+      && get_comdat_group ()
+      && get_comdat_group () == ref->get_comdat_group ())
+    return true;
+
+  return false;
+}
Index: varpool.c
===================================================================
--- varpool.c	(revision 234761)
+++ varpool.c	(working copy)
@@ -482,7 +482,7 @@ varpool_node::add (tree decl)
 /* Return variable availability.  See cgraph.h for description of individual
    return values.  */
 enum availability
-varpool_node::get_availability (void)
+varpool_node::get_availability (symtab_node *ref)
 {
   if (!definition)
     return AVAIL_NOT_AVAILABLE;
@@ -495,9 +495,16 @@ varpool_node::get_availability (void)
     {
       enum availability avail;
 
-      ultimate_alias_target (&avail);
+      ultimate_alias_target (&avail, ref);
       return avail;
     }
+  /* If this is a reference from symbol itself and there are no aliases, we
+     may be sure that the symbol was not interposed by soemthing else because
+     the symbol itself would be unreachable otherwise.  */
+  if ((this == ref && !has_aliases_p ())
+      || (ref && get_comdat_group ()
+          && get_comdat_group () == ref->get_comdat_group ()))
+    return AVAIL_AVAILABLE;
   /* If the variable can be overwritten, return OVERWRITABLE.  Takes
      care of at least one notable extension - the COMDAT variables
      used to share template instantiations in C++.  */