On 02/20/2015 07:39 PM, Jan Hubicka wrote:
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 <mli...@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 <mli...@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 <mli...@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.
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. */
OK, I am bit surprised you have a separate loop for this instead of doing it at
a place you compare ipa-ref rerences anyway, but I suppose you know the code
better than I do ;)
+ 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 ();
I think this needs to be performed just once, because subdividing does not
depend on congurences.
+/* 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);
You do not need to consider IPA_REF_ADDR of virtual table/ctors/dtors and
virtual functions
to be address references (because these are never compared for equality.) Test
it as
The proper conditon on when address matter is
if (!DECL_VIRTUAL_P (ref->referred->decl)
&& (TREE_CODE (ref->referred->decl) != FUNCTION_DECL
|| (!DECL_CXX_CONSTRUCTOR_P (ref->referred->decl)
&& !DECL_CXX_DESTRUCTOR_P (ref->referred->decl)))
please also update sem_function::merge by adding cdtors in addition
to DECL_VIRTUAL_P
Why sem_item_optimizer::filter_removed_items checks cdtors?
+ }
+ }
+
+ /* 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 ();
This looks like a poor choice of hash function because the count will likely
match. equal_address_to basically walks to alias targets
A safe approximation is to hash ultimate_alias_target of all entries in your
list.
+ }
+
+ 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;
+ }
+};
OK with these changes.
Honza
Hello Honza.
I've updated the patch so that your notes are resolved. Moreover, I've added
comparison
for interposable symbols that are either target of reference or are called by a
function.
Please read the patch to verify the comparison is as you expected.
I'm going to run testsuite.
Thanks,
Martin
>From 8dae064e67e30537486e0d502fc5df39d37cee3e Mon Sep 17 00:00:00 2001
From: mliska <mli...@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 <mli...@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 <mli...@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
