From 8dae064e67e30537486e0d502fc5df39d37cee3e Mon Sep 17 00:00:00 2001
From: mliska <mliska@suse.cz>
Date: Thu, 19 Feb 2015 16:08:09 +0100
Subject: [PATCH 1/3] Fix PR ipa/64693

gcc/ChangeLog:

2015-02-20  Martin Liska  <mliska@suse.cz>

	PR ipa/64693
	* ipa-icf.c (sem_item_optimizer::add_item_to_class): Identify if
	a newly added item has an address reference.
	(sem_item_optimizer::subdivide_classes_by_addr_references):
	New function.
	(sem_item_optimizer::process_cong_reduction): Include subdivision
	based on address references.
	* ipa-icf.h (struct addr_refs_hashmap_traits): New struct.
	(sem_item::is_nonvirtual_or_cdtor): New function.

gcc/testsuite/ChangeLog:

2015-02-20  Martin Liska  <mliska@suse.cz>

	* gcc.dg/ipa/ipa-icf-26.c: Update expected test results.
	* gcc.dg/ipa/ipa-icf-33.c: Remove duplicate line.
	* gcc.dg/ipa/ipa-icf-34.c: New test.
---
 gcc/ipa-icf.c                         | 130 ++++++++++++++++++++++++++++++++--
 gcc/ipa-icf.h                         |  85 ++++++++++++++++++++++
 gcc/testsuite/gcc.dg/ipa/ipa-icf-26.c |   3 +-
 gcc/testsuite/gcc.dg/ipa/ipa-icf-33.c |   1 -
 gcc/testsuite/gcc.dg/ipa/ipa-icf-34.c |  43 +++++++++++
 5 files changed, 255 insertions(+), 7 deletions(-)
 create mode 100644 gcc/testsuite/gcc.dg/ipa/ipa-icf-34.c

diff --git a/gcc/ipa-icf.c b/gcc/ipa-icf.c
index 494fdcf..fbb641d 100644
--- a/gcc/ipa-icf.c
+++ b/gcc/ipa-icf.c
@@ -126,6 +126,40 @@ along with GCC; see the file COPYING3.  If not see
 using namespace ipa_icf_gimple;
 
 namespace ipa_icf {
+
+/* Constructor.  */
+
+addr_refs_collection::addr_refs_collection (symtab_node *node)
+{
+  m_references.create (0);
+  m_interposables.create (0);
+
+  ipa_ref *ref;
+
+  if (is_a <varpool_node *> (node) && DECL_VIRTUAL_P (node->decl))
+    return;
+
+  for (unsigned i = 0; i < node->num_references (); i++)
+    {
+      ref = node->iterate_reference (i, ref);
+      if (ref->use == IPA_REF_ADDR
+	  && sem_item::is_nonvirtual_or_cdtor (ref->referred->decl))
+	m_references.safe_push (ref->referred);
+
+      if (ref->referred->get_availability () <= AVAIL_INTERPOSABLE)
+	m_interposables.safe_push (ref->referred);
+    }
+
+  if (is_a <cgraph_node *> (node))
+    {
+      cgraph_node *cnode = dyn_cast <cgraph_node *> (node);
+
+      for (cgraph_edge *e = cnode->callees; e; e = e->next_callee)
+	if (e->callee->get_availability () <= AVAIL_INTERPOSABLE)
+	  m_interposables.safe_push (e->callee);
+    }
+}
+
 /* Constructor for key value pair, where _ITEM is key and _INDEX is a target.  */
 
 sem_usage_pair::sem_usage_pair (sem_item *_item, unsigned int _index):
@@ -638,11 +672,11 @@ sem_function::merge (sem_item *alias_item)
 
   /* See if original and/or alias address can be compared for equality.  */
   original_address_matters
-    = (!DECL_VIRTUAL_P (original->decl)
+    = (sem_item::is_nonvirtual_or_cdtor (original->decl)
        && (original->externally_visible
 	   || original->address_taken_from_non_vtable_p ()));
   alias_address_matters
-    = (!DECL_VIRTUAL_P (alias->decl)
+    = (sem_item::is_nonvirtual_or_cdtor (alias->decl)
        && (alias->externally_visible
 	   || alias->address_taken_from_non_vtable_p ()));
 
@@ -1969,6 +2003,82 @@ sem_item_optimizer::subdivide_classes_by_equality (bool in_wpa)
   verify_classes ();
 }
 
+/* Subdivide classes by address references that members of the class
+   reference. Example can be a pair of functions that have an address
+   taken from a function. If these addresses are different the class
+   is split.  */
+
+unsigned
+sem_item_optimizer::subdivide_classes_by_addr_references ()
+{
+  unsigned newly_created_classes = 0;
+
+  for (hash_table <congruence_class_group_hash>::iterator it = m_classes.begin ();
+       it != m_classes.end (); ++it)
+    {
+      unsigned int class_count = (*it)->classes.length ();
+      auto_vec<congruence_class *> new_classes;
+
+      for (unsigned i = 0; i < class_count; i++)
+	{
+	  congruence_class *c = (*it)->classes [i];
+
+	  if (c->members.length() > 1)
+	    {
+	      hash_map <addr_refs_collection *, vec <sem_item *>, addr_refs_hashmap_traits> split_map;
+
+	      for (unsigned j = 0; j < c->members.length (); j++)
+	        {
+		  sem_item *source_node = c->members[j];
+
+		  addr_refs_collection *collection = new addr_refs_collection (source_node->node);
+
+		  vec <sem_item *> *slot = &split_map.get_or_insert (collection);
+		  gcc_checking_assert (slot);
+
+		  slot->safe_push (source_node);
+	        }
+
+	       /* If the map contains more than one key, we have to split the map
+		  appropriately.  */
+	      if (split_map.elements () != 1)
+	        {
+		  bool first_class = true;
+
+		  hash_map <addr_refs_collection *, vec <sem_item *>, addr_refs_hashmap_traits>::iterator it2 = split_map.begin ();
+		  for (; it2 != split_map.end (); ++it2)
+		    {
+		      congruence_class *new_cls;
+		      new_cls = new congruence_class (class_id++);
+
+		      for (unsigned k = 0; k < (*it2).second.length (); k++)
+			add_item_to_class (new_cls, (*it2).second[k]);
+
+		      worklist_push (new_cls);
+		      newly_created_classes++;
+
+		      if (first_class)
+		        {
+			  (*it)->classes[i] = new_cls;
+			  first_class = false;
+			}
+		      else
+		        {
+		          new_classes.safe_push (new_cls);
+			  m_classes_count++;
+		        }
+		    }
+		}
+	    }
+	  }
+
+	for (unsigned i = 0; i < new_classes.length (); i++)
+	  (*it)->classes.safe_push (new_classes[i]);
+    }
+
+  return newly_created_classes;
+}
+
 /* Verify congruence classes if checking is enabled.  */
 
 void
@@ -2258,8 +2368,20 @@ sem_item_optimizer::process_cong_reduction (void)
     fprintf (dump_file, "Congruence class reduction\n");
 
   congruence_class *cls;
-  while ((cls = worklist_pop ()) != NULL)
-    do_congruence_step (cls);
+
+  while(!worklist_empty ())
+  {
+    /* Process complete congruence reduction.  */
+    while ((cls = worklist_pop ()) != NULL)
+      do_congruence_step (cls);
+
+    /* Subdivide newly created classes according to references.  */
+    unsigned new_classes = subdivide_classes_by_addr_references ();
+
+    if (dump_file)
+      fprintf (dump_file, "Address reference subdivision created: %u "
+	       "new classes.\n", new_classes);
+  }
 }
 
 /* Debug function prints all informations about congruence classes.  */
diff --git a/gcc/ipa-icf.h b/gcc/ipa-icf.h
index a55699b..dd016f3 100644
--- a/gcc/ipa-icf.h
+++ b/gcc/ipa-icf.h
@@ -63,6 +63,70 @@ enum sem_item_type
   VAR
 };
 
+/* Class is container for address references for a symtab_node.  */
+
+class addr_refs_collection
+{
+public:
+  /* Constructor.  */
+  addr_refs_collection (symtab_node *node);
+
+  /* Destructor.  */
+  ~addr_refs_collection ()
+  {
+    m_references.release ();
+    m_interposables.release ();
+  }
+
+  /* Vector of address references.  */
+  vec<symtab_node *> m_references;
+
+  /* Vector of interposable references.  */
+  vec<symtab_node *> m_interposables;
+};
+
+/* Hash traits for addr_refs_collection map.  */
+
+struct addr_refs_hashmap_traits: default_hashmap_traits
+{
+  static hashval_t
+  hash (const addr_refs_collection *v)
+  {
+    inchash::hash hstate;
+    hstate.add_int (v->m_references.length ());
+
+    for (unsigned i = 0; i < v->m_references.length (); i++)
+      hstate.add_ptr (v->m_references[i]->ultimate_alias_target ());
+
+    hstate.add_int (v->m_interposables.length ());
+
+    for (unsigned i = 0; i < v->m_interposables.length (); i++)
+      hstate.add_ptr (v->m_interposables[i]->ultimate_alias_target ());
+
+    return hstate.end ();
+  }
+
+  static bool
+  equal_keys (const addr_refs_collection *a,
+	      const addr_refs_collection *b)
+  {
+    if (a->m_references.length () != b->m_references.length ())
+      return false;
+
+    for (unsigned i = 0; i < a->m_references.length (); i++)
+      if (a->m_references[i]->equal_address_to (b->m_references[i]) != 1)
+	return false;
+
+    for (unsigned i = 0; i < a->m_interposables.length (); i++)
+      if (!a->m_interposables[i]->semantically_equivalent_p
+	(b->m_interposables[i]))
+	return false;
+
+    return true;
+  }
+};
+
+
 /* Semantic item usage pair.  */
 class sem_usage_pair
 {
@@ -140,6 +204,15 @@ public:
      contains_polymorphic_type_p comparison.  */
   static bool get_base_types (tree *t1, tree *t2);
 
+  /* Return true if given DECL is neither virtual nor cdtor.  */
+  static bool is_nonvirtual_or_cdtor (tree decl)
+  {
+    return !DECL_VIRTUAL_P (decl)
+	   && (TREE_CODE (decl) != FUNCTION_DECL
+	       || (!DECL_CXX_CONSTRUCTOR_P (decl)
+		   && !DECL_CXX_DESTRUCTOR_P (decl)));
+  }
+
   /* Return true if target supports alias symbols.  */
   bool target_supports_symbol_aliases_p (void);
 
@@ -467,6 +540,12 @@ private:
      classes. If IN_WPA, fast equality function is invoked.  */
   void subdivide_classes_by_equality (bool in_wpa = false);
 
+  /* Subdivide classes by address references that members of the class
+     reference. Example can be a pair of functions that have an address
+     taken from a function. If these addresses are different the class
+     is split.  */
+  unsigned subdivide_classes_by_addr_references ();
+
   /* Debug function prints all informations about congruence classes.  */
   void dump_cong_classes (void);
 
@@ -487,6 +566,12 @@ private:
   /* Pops a class from worklist. */
   congruence_class *worklist_pop ();
 
+  /* Return true if worklist is empty.  */
+  bool worklist_empty ()
+  {
+    return worklist.empty ();
+  }
+
   /* Every usage of a congruence class CLS is a candidate that can split the
      collection of classes. Bitmap stack BMSTACK is used for bitmap
      allocation.  */
diff --git a/gcc/testsuite/gcc.dg/ipa/ipa-icf-26.c b/gcc/testsuite/gcc.dg/ipa/ipa-icf-26.c
index 0c5a5a6..f48c040 100644
--- a/gcc/testsuite/gcc.dg/ipa/ipa-icf-26.c
+++ b/gcc/testsuite/gcc.dg/ipa/ipa-icf-26.c
@@ -38,7 +38,6 @@ int main()
   return 0;
 }
 
-/* { dg-final { scan-ipa-dump "Semantic equality hit:bar->foo" "icf"  } } */
 /* { dg-final { scan-ipa-dump "Semantic equality hit:remove->destroy" "icf"  } } */
-/* { dg-final { scan-ipa-dump "Equal symbols: 2" "icf"  } } */
+/* { dg-final { scan-ipa-dump "Equal symbols: 1" "icf"  } } */
 /* { dg-final { cleanup-ipa-dump "icf" } } */
diff --git a/gcc/testsuite/gcc.dg/ipa/ipa-icf-33.c b/gcc/testsuite/gcc.dg/ipa/ipa-icf-33.c
index d7e814d..7b6a8ae 100644
--- a/gcc/testsuite/gcc.dg/ipa/ipa-icf-33.c
+++ b/gcc/testsuite/gcc.dg/ipa/ipa-icf-33.c
@@ -23,5 +23,4 @@ int main()
 }
 
 /* { dg-final { scan-ipa-dump "Equal symbols: 1" "icf"  } } */
-/* { dg-final { scan-ipa-dump "Equal symbols: 1" "icf"  } } */
 /* { dg-final { cleanup-ipa-dump "icf" } } */
diff --git a/gcc/testsuite/gcc.dg/ipa/ipa-icf-34.c b/gcc/testsuite/gcc.dg/ipa/ipa-icf-34.c
new file mode 100644
index 0000000..7772e49
--- /dev/null
+++ b/gcc/testsuite/gcc.dg/ipa/ipa-icf-34.c
@@ -0,0 +1,43 @@
+/* { dg-do compile } */
+/* { dg-options "-O0 -fipa-icf -fdump-ipa-icf-details"  } */
+
+#include <stdlib.h>
+#include <assert.h>
+
+int callback1(int a)
+{
+  return a * a;
+}
+
+int callback2(int a)
+{
+  return a * a;
+}
+
+static int test(int (*callback) (int))
+{
+  if (callback == callback1)
+    return 1;
+
+  return 0;
+}
+
+int foo()
+{
+  return test(&callback1);
+}
+
+int bar()
+{
+  return test(&callback2);
+}
+
+int main()
+{
+  assert (foo() != bar());
+
+  return 0;
+}
+
+/* { dg-final { scan-ipa-dump "Equal symbols: 1" "icf"  } } */
+/* { dg-final { cleanup-ipa-dump "icf" } } */
-- 
2.1.2

