This is the mail archive of the gcc-patches@gcc.gnu.org mailing list for the GCC project.


Index Nav: [Date Index] [Subject Index] [Author Index] [Thread Index]
Message Nav: [Date Prev] [Date Next] [Thread Prev] [Thread Next]
Other format: [Raw text]

Re: [PATCH] Fix for PR ipa/64693


On 02/12/2015 05:57 PM, Jan Hubicka wrote:
From: mliska <mliska@suse.cz>V
Date: Fri, 23 Jan 2015 14:58:36 +0100
Subject: [PATCH] Fix PR ipa/64693.

gcc/ChangeLog:

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

	PR ipa/64693
	* ipa-icf.c (sem_item_optimizer::execute): Call identify_address_sensitive_classes.
	(sem_item_optimizer::identify_address_sensitive_classes): New function.
	(sem_item_optimizer::merge_classes): Handle cases where we merge a class
	with a sensitive reference.
	(congruence_class::dump): Add support for a new sensitive_reference flag.
	* ipa-icf.h: Add new function.

+
+/* Identify congruence classes which have an address taken. These
+   classes can be potentially been merged just as thunks.  */

Hmm, I would expect someting like this

  1) break out code in sem_function::merge which decides if function A and B
     can be identified or if thunk is needed
  2) when comparing references to verify congruence, actually check if merging
     would result in thunk and subdivide.

In the following:

void f1()
{
}
void f2()
{
}
void *a=&f1;
void *b=&f1;
void *c=&f2;
void *d=&f2;

The code bellow seems to disable all merging, while we ought to be able to mere A,B
and C,D into two congruences.
Similarly we ought to be able to merge in a case F2 is a virtual function/ctor/dtor
where address can not be compared for equality.
+
+void
+sem_item_optimizer::identify_address_sensitive_classes (void)
+{
+  for (hash_table<congruence_class_group_hash>::iterator it = m_classes.begin ();
+       it != m_classes.end (); ++it)
+    for (unsigned i = 0; i < (*it)->classes.length (); i++)
+      {
+	congruence_class *cls = (*it)->classes[i];
+
+	if (cls->members.length () == 1)
+	  continue;
+
+	auto_vec <sem_item *> references;
+	sem_item *source_node = cls->members[0];
+	ipa_ref *r;
+
+	for (unsigned j = 0; j < source_node->node->num_references (); j++)
+	  {
+	    symtab_node *ref = source_node->node->iterate_reference (j, r)->referred;
+	    sem_item **symbol = m_symtab_node_map.get (ref);
+	    if (symbol)
+	      references.safe_push (*symbol);
+	  }
+
+	for (unsigned j = 1; j < cls->members.length (); j++)
+	  {
+	    source_node = cls->members[j];
+
+	    unsigned l = 0;
+	    for (unsigned k = 0; k < source_node->node->num_references (); k++)
+	      {
+		symtab_node *ref = source_node->node->iterate_reference (k, r)->referred;
+		sem_item **symbol = m_symtab_node_map.get (ref);
+		if (symbol)
+		  {
+		    if (l >= references.length () || references[l] != *symbol)
+		      {
+			cls->sensitive_reference = true;
+			break;
+		      }
+
+		    l++;
+		  }
+	      }
+
+	    if (cls->sensitive_reference)
+	      break;
+	  }
+      }
+}
+
  /* Debug function prints all informations about congruence classes.  */

  void
@@ -2374,6 +2430,15 @@ sem_item_optimizer::merge_classes (unsigned int prev_class_count)
  		continue;
  	      }

+	    if (c->sensitive_reference)
+	      {
+		if (dump_file)
+		  fprintf (dump_file, "A function from the congruence class "
+			   "uses a sensitive reference.\n");
+
+		continue;
+	      }
+
  	    if (dump_file && (dump_flags & TDF_DETAILS))
  	      {
  		source->dump_to_file (dump_file);
@@ -2390,8 +2455,10 @@ sem_item_optimizer::merge_classes (unsigned int prev_class_count)
  void
  congruence_class::dump (FILE *file, unsigned int indent) const
  {
-  FPRINTF_SPACES (file, indent, "class with id: %u, hash: %u, items: %u\n",
-		  id, members[0]->get_hash (), members.length ());
+  FPRINTF_SPACES (file, indent,
+		  "class with id: %u, hash: %u, items: %u %s\n",
+		  id, members[0]->get_hash (), members.length (),
+		  sensitive_reference ? "sensitive_reference" : "");

    FPUTS_SPACES (file, indent + 2, "");
    for (unsigned i = 0; i < members.length (); i++)
diff --git a/gcc/ipa-icf.h b/gcc/ipa-icf.h
index adbedd6..db0bc54 100644
--- a/gcc/ipa-icf.h
+++ b/gcc/ipa-icf.h
@@ -29,7 +29,8 @@ class congruence_class
  {
  public:
    /* Congruence class constructor for a new class with _ID.  */
-  congruence_class (unsigned int _id): in_worklist (false), id(_id)
+  congruence_class (unsigned int _id): in_worklist (false), id(_id),
+    sensitive_reference (false)
    {
    }

@@ -54,6 +55,9 @@ public:

    /* Global unique class identifier.  */
    unsigned int id;
+
+  /* A function from the class contains a reference to another class.  */
+  bool sensitive_reference;
  };

  /* Semantic item type enum.  */
@@ -476,6 +480,10 @@ private:
    /* Iterative congruence reduction function.  */
    void process_cong_reduction (void);

+  /* Identify congruence classes which have an address taken. These
+     classes can be potentially been merged just as thunks.  */
+  void identify_address_sensitive_classes (void);
+
    /* After reduction is done, we can declare all items in a group
       to be equal. PREV_CLASS_COUNT is start number of classes
       before reduction.  */
diff --git a/gcc/testsuite/gcc.dg/ipa/ipa-icf-26.c b/gcc/testsuite/gcc.dg/ipa/ipa-icf-26.c
index 0c5a5a6..f25a251 100644
--- a/gcc/testsuite/gcc.dg/ipa/ipa-icf-26.c
+++ b/gcc/testsuite/gcc.dg/ipa/ipa-icf-26.c
@@ -38,7 +38,7 @@ 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 "A function from the congruence class uses a sensitive reference." "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..66bcac5
--- /dev/null
+++ b/gcc/testsuite/gcc.dg/ipa/ipa-icf-34.c
@@ -0,0 +1,44 @@
+/* { 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: 2" "icf"  } } */
+/* { dg-final { scan-ipa-dump "A function from the congruence class uses a sensitive reference." "icf"  } } */
+/* { dg-final { cleanup-ipa-dump "icf" } } */
--
2.1.2



Hello.

There's updated version that reflects how should we handle congruence classes that have any
address reference. Patch can bootstrap x86_64-linux-pc and no new regression is introduced?

Ready for trunk?
Thanks,
Martin


>From d7472e55b345214d55ed49f5f10deafa9a24a4fc Mon Sep 17 00:00:00 2001
From: mliska <mliska@suse.cz>
Date: Thu, 19 Feb 2015 16:08:09 +0100
Subject: [PATCH 1/2] 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.
	* ipa-ref.h (has_addr_ref_p): 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                         | 97 ++++++++++++++++++++++++++++++++++-
 gcc/ipa-icf.h                         | 72 +++++++++++++++++++++++++-
 gcc/ipa-ref.h                         | 13 +++++
 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 ++++++++++++++++
 6 files changed, 223 insertions(+), 6 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..859b9d1 100644
--- a/gcc/ipa-icf.c
+++ b/gcc/ipa-icf.c
@@ -1809,6 +1809,9 @@ sem_item_optimizer::add_item_to_class (congruence_class *cls, sem_item *item)
   item->index_in_class = cls->members.length ();
   cls->members.safe_push (item);
   item->cls = cls;
+
+  if (!cls->has_member_with_addr_ref && item->node->ref_list.has_addr_ref_p ())
+    cls->has_member_with_addr_ref = true;
 }
 
 /* Congruence classes are built by hash value.  */
@@ -1969,6 +1972,84 @@ 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->has_member_with_addr_ref)
+	    continue;
+
+	  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 +2339,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..26facc4 100644
--- a/gcc/ipa-icf.h
+++ b/gcc/ipa-icf.h
@@ -29,7 +29,8 @@ class congruence_class
 {
 public:
   /* Congruence class constructor for a new class with _ID.  */
-  congruence_class (unsigned int _id): in_worklist (false), id(_id)
+  congruence_class (unsigned int _id): in_worklist (false), id(_id),
+    has_member_with_addr_ref (false)
   {
   }
 
@@ -54,6 +55,9 @@ public:
 
   /* Global unique class identifier.  */
   unsigned int id;
+
+  /* Identify if a member of this class has an address reference.  */
+  bool has_member_with_addr_ref;
 };
 
 /* Semantic item type enum.  */
@@ -63,6 +67,60 @@ enum sem_item_type
   VAR
 };
 
+/* Class is container for address references for a symtab_node.  */
+
+class addr_refs_collection
+{
+public:
+  addr_refs_collection (symtab_node *node)
+  {
+    m_references.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)
+	  m_references.safe_push (ref->referred);
+      }
+  }
+
+  /* Vector of address references.  */
+  vec<symtab_node *> m_references;
+};
+
+/* 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 ());
+
+    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;
+
+    return true;
+  }
+};
+
+
 /* Semantic item usage pair.  */
 class sem_usage_pair
 {
@@ -467,6 +525,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 +551,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/ipa-ref.h b/gcc/ipa-ref.h
index aea7f4c..b2ed801 100644
--- a/gcc/ipa-ref.h
+++ b/gcc/ipa-ref.h
@@ -112,6 +112,19 @@ public:
     return first_alias ();
   }
 
+  /* Return true if there's any address reference.  */
+  bool inline has_addr_ref_p (void)
+  {
+    if (!vec_safe_length (references))
+      return 0;
+
+     for(unsigned i = 0; i < references->length (); i++)
+       if ((*references)[i].use == IPA_REF_ADDR)
+	 return true;
+
+    return false;
+  }
+
   /* Clear reference list.  */
   void clear (void)
   {
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


Index Nav: [Date Index] [Subject Index] [Author Index] [Thread Index]
Message Nav: [Date Prev] [Date Next] [Thread Prev] [Thread Next]