* [PATCH] Speed-up IPA ICF by enhanced hash values
@ 2015-03-19 19:39 Martin Liška
2015-03-19 20:42 ` Jan Hubicka
0 siblings, 1 reply; 3+ messages in thread
From: Martin Liška @ 2015-03-19 19:39 UTC (permalink / raw)
To: GCC Patches; +Cc: hubic >> Jan Hubicka
[-- Attachment #1: Type: text/plain, Size: 207 bytes --]
Hi.
Following patch improves performance by adding hash values of references that are not
candidates for IPA ICF. Tested on x86_64-linux-pc w/o any new regression observed.
Ready for trunk?
Thanks,
Martin
[-- Attachment #2: 0001-IPA-ICF-include-hash-values-of-references.patch --]
[-- Type: text/x-patch, Size: 5978 bytes --]
From 6c04cc4283d08a8aa9829574dd91579a918cb508 Mon Sep 17 00:00:00 2001
From: marxin <marxin.liska@gmail.com>
Date: Sun, 15 Mar 2015 19:21:39 -0500
Subject: [PATCH] IPA ICF: include hash values of references.
gcc/ChangeLog:
2015-03-15 Martin Liska <mliska@suse.cz>
* ipa-icf.c (sem_item::update_hash_by_addr_refs): New function.
(sem_item::update_hash_by_local_refs): Likewise.
(sem_variable::get_hash): Empty line is fixed.
(sem_item_optimizer::execute): Include adding of hash references.
(sem_item_optimizer::update_hash_by_addr_refs): New function.
(sem_item_optimizer::build_hash_based_classes): Use local hash.
* ipa-icf.h (sem_item::update_hash_by_addr_refs): New function.
(sem_item::update_hash_by_local_refs): Likewise.
---
gcc/ipa-icf.c | 84 ++++++++++++++++++++++++++++++++++++++++++++++++++++++++---
gcc/ipa-icf.h | 18 ++++++++++++-
2 files changed, 97 insertions(+), 5 deletions(-)
diff --git a/gcc/ipa-icf.c b/gcc/ipa-icf.c
index f68d23c..b8e3aa4 100644
--- a/gcc/ipa-icf.c
+++ b/gcc/ipa-icf.c
@@ -557,6 +557,69 @@ sem_function::equals_wpa (sem_item *item,
return true;
}
+/* Update hash by address sensitive references. */
+
+void
+sem_item::update_hash_by_addr_refs (hash_map <symtab_node *,
+ sem_item *> &m_symtab_node_map)
+{
+ if (is_a <varpool_node *> (node) && DECL_VIRTUAL_P (node->decl))
+ return;
+
+ ipa_ref* ref;
+ inchash::hash hstate (hash);
+ for (unsigned i = 0; i < node->num_references (); i++)
+ {
+ ref = node->iterate_reference (i, ref);
+ if (ref->address_matters_p ())
+ hstate.add_ptr (ref->referred->ultimate_alias_target ());
+ }
+
+ if (is_a <cgraph_node *> (node))
+ {
+ for (cgraph_edge *e = dyn_cast <cgraph_node *> (node)->callers; e;
+ e = e->next_caller)
+ {
+ sem_item **result = m_symtab_node_map.get (e->callee);
+ if (!result)
+ hstate.add_ptr (e->callee->ultimate_alias_target ());
+ }
+ }
+
+ hash = hstate.end ();
+}
+
+/* Update hash by computed local hash values taken from different
+ semantic items. */
+
+void
+sem_item::update_hash_by_local_refs (hash_map <symtab_node *,
+ sem_item *> &m_symtab_node_map)
+{
+ inchash::hash state (hash);
+ for (unsigned j = 0; j < node->num_references (); j++)
+ {
+ ipa_ref *ref;
+ ref = node->iterate_reference (j, ref);
+ sem_item **result = m_symtab_node_map.get (ref->referring);
+ if (result)
+ state.merge_hash ((*result)->hash);
+ }
+
+ if (type == FUNC)
+ {
+ for (cgraph_edge *e = dyn_cast <cgraph_node *> (node)->callees; e;
+ e = e->next_callee)
+ {
+ sem_item **result = m_symtab_node_map.get (e->caller);
+ if (result)
+ state.merge_hash ((*result)->hash);
+ }
+ }
+
+ global_hash = state.end ();
+}
+
/* Returns true if the item equals to ITEM given as argument. */
bool
@@ -1742,8 +1805,8 @@ hashval_t
sem_variable::get_hash (void)
{
if (hash)
-
return hash;
+
/* All WPA streamed in symbols should have their hashes computed at compile
time. At this point, the constructor may not be in memory at all.
DECL_INITIAL (decl) would be error_mark_node in that case. */
@@ -2202,6 +2265,8 @@ sem_item_optimizer::execute (void)
filter_removed_items ();
unregister_hooks ();
+ build_graph ();
+ update_hash_by_addr_refs ();
build_hash_based_classes ();
if (dump_file)
@@ -2211,8 +2276,6 @@ sem_item_optimizer::execute (void)
for (unsigned int i = 0; i < m_items.length(); i++)
m_items[i]->init_wpa ();
- build_graph ();
-
subdivide_classes_by_equality (true);
if (dump_file)
@@ -2301,6 +2364,19 @@ sem_item_optimizer::add_item_to_class (congruence_class *cls, sem_item *item)
item->cls = cls;
}
+void
+sem_item_optimizer::update_hash_by_addr_refs ()
+{
+ for (unsigned i = 0; i < m_items.length (); i++)
+ m_items[i]->update_hash_by_addr_refs (m_symtab_node_map);
+
+ for (unsigned i = 0; i < m_items.length (); i++)
+ m_items[i]->update_hash_by_local_refs (m_symtab_node_map);
+
+ for (unsigned i = 0; i < m_items.length (); i++)
+ m_items[i]->hash = m_items[i]->global_hash;
+}
+
/* Congruence classes are built by hash value. */
void
@@ -2310,7 +2386,7 @@ sem_item_optimizer::build_hash_based_classes (void)
{
sem_item *item = m_items[i];
- congruence_class_group *group = get_group_by_hash (item->get_hash (),
+ congruence_class_group *group = get_group_by_hash (item->hash,
item->type);
if (!group->classes.length ())
diff --git a/gcc/ipa-icf.h b/gcc/ipa-icf.h
index 8245b54..ad502a7 100644
--- a/gcc/ipa-icf.h
+++ b/gcc/ipa-icf.h
@@ -189,6 +189,15 @@ public:
/* Dump symbol to FILE. */
virtual void dump_to_file (FILE *file) = 0;
+ /* Update hash by address sensitive references. */
+ void update_hash_by_addr_refs (hash_map <symtab_node *,
+ sem_item *> &m_symtab_node_map);
+
+ /* Update hash by computed local hash values taken from different
+ semantic items. */
+ void update_hash_by_local_refs (hash_map <symtab_node *,
+ sem_item *> &m_symtab_node_map);
+
/* Return base tree that can be used for compatible_types_p and
contains_polymorphic_type_p comparison. */
static bool get_base_types (tree *t1, tree *t2);
@@ -226,9 +235,13 @@ public:
/* A set with symbol table references. */
hash_set <symtab_node *> refs_set;
+ /* Hash of item. */
+ hashval_t hash;
+
+ /* Temporary hash used where hash values of references are added. */
+ hashval_t global_hash;
protected:
/* Cached, once calculated hash for the item. */
- hashval_t hash;
/* Accumulate to HSTATE a hash of constructor expression EXP. */
static void add_expr (const_tree exp, inchash::hash &hstate);
@@ -494,6 +507,9 @@ public:
private:
+ /* Update hash of symbol by address memory references. */
+ void update_hash_by_addr_refs ();
+
/* Congruence classes are built by hash value. */
void build_hash_based_classes (void);
--
2.1.2
^ permalink raw reply [flat|nested] 3+ messages in thread
* Re: [PATCH] Speed-up IPA ICF by enhanced hash values
2015-03-19 19:39 [PATCH] Speed-up IPA ICF by enhanced hash values Martin Liška
@ 2015-03-19 20:42 ` Jan Hubicka
2015-03-22 20:17 ` Martin Liška
0 siblings, 1 reply; 3+ messages in thread
From: Jan Hubicka @ 2015-03-19 20:42 UTC (permalink / raw)
To: Martin Liška; +Cc: GCC Patches, hubic >> Jan Hubicka
> diff --git a/gcc/ipa-icf.c b/gcc/ipa-icf.c
> index f68d23c..b8e3aa4 100644
> --- a/gcc/ipa-icf.c
> +++ b/gcc/ipa-icf.c
> @@ -557,6 +557,69 @@ sem_function::equals_wpa (sem_item *item,
> return true;
> }
>
> +/* Update hash by address sensitive references. */
> +
> +void
> +sem_item::update_hash_by_addr_refs (hash_map <symtab_node *,
> + sem_item *> &m_symtab_node_map)
> +{
> + if (is_a <varpool_node *> (node) && DECL_VIRTUAL_P (node->decl))
Do not return early here, if reference goes to external symbol, we still want
to record it as sensitive. ref->address_matters_p () should behave well here.
> + return;
> +
> + ipa_ref* ref;
> + inchash::hash hstate (hash);
> + for (unsigned i = 0; i < node->num_references (); i++)
> + {
> + ref = node->iterate_reference (i, ref);
> + if (ref->address_matters_p ())
ref->address_matters_p () || !m_symtab_node_map.get (ref->referred)
if refernce goes to external symbol, it behaves like sensitive.
You probably want to update topleve comment explaining what is sensitive and local
reference and how the hashing is handled.
> + hstate.add_ptr (ref->referred->ultimate_alias_target ());
> + }
> +
> + if (is_a <cgraph_node *> (node))
> + {
> + for (cgraph_edge *e = dyn_cast <cgraph_node *> (node)->callers; e;
> + e = e->next_caller)
> + {
> + sem_item **result = m_symtab_node_map.get (e->callee);
> + if (!result)
> + hstate.add_ptr (e->callee->ultimate_alias_target ());
> + }
> + }
> +
> + hash = hstate.end ();
> +}
> +
> +/* Update hash by computed local hash values taken from different
> + semantic items. */
Please add TODO that stronger SCC based hashing would be desirable here.
> @@ -2301,6 +2364,19 @@ sem_item_optimizer::add_item_to_class (congruence_class *cls, sem_item *item)
> item->cls = cls;
> }
>
> +void
> +sem_item_optimizer::update_hash_by_addr_refs ()
Add block comment ande xplain why the addr and local updates can not be performed at once
or someone gets an idea to merge the loops.
> +{
> + for (unsigned i = 0; i < m_items.length (); i++)
> + m_items[i]->update_hash_by_addr_refs (m_symtab_node_map);
> +
> + for (unsigned i = 0; i < m_items.length (); i++)
> + m_items[i]->update_hash_by_local_refs (m_symtab_node_map);
> +
> + for (unsigned i = 0; i < m_items.length (); i++)
> + m_items[i]->hash = m_items[i]->global_hash;
> +}
> +
OK with these changes.
Honza
^ permalink raw reply [flat|nested] 3+ messages in thread
* Re: [PATCH] Speed-up IPA ICF by enhanced hash values
2015-03-19 20:42 ` Jan Hubicka
@ 2015-03-22 20:17 ` Martin Liška
0 siblings, 0 replies; 3+ messages in thread
From: Martin Liška @ 2015-03-22 20:17 UTC (permalink / raw)
To: Jan Hubicka; +Cc: GCC Patches
[-- Attachment #1: Type: text/plain, Size: 2675 bytes --]
On 03/19/2015 09:42 PM, Jan Hubicka wrote:
>
>> diff --git a/gcc/ipa-icf.c b/gcc/ipa-icf.c
>> index f68d23c..b8e3aa4 100644
>> --- a/gcc/ipa-icf.c
>> +++ b/gcc/ipa-icf.c
>> @@ -557,6 +557,69 @@ sem_function::equals_wpa (sem_item *item,
>> return true;
>> }
>>
>> +/* Update hash by address sensitive references. */
>> +
>> +void
>> +sem_item::update_hash_by_addr_refs (hash_map <symtab_node *,
>> + sem_item *> &m_symtab_node_map)
>> +{
>> + if (is_a <varpool_node *> (node) && DECL_VIRTUAL_P (node->decl))
>
> Do not return early here, if reference goes to external symbol, we still want
> to record it as sensitive. ref->address_matters_p () should behave well here.
>> + return;
>> +
>> + ipa_ref* ref;
>> + inchash::hash hstate (hash);
>> + for (unsigned i = 0; i < node->num_references (); i++)
>> + {
>> + ref = node->iterate_reference (i, ref);
>> + if (ref->address_matters_p ())
>
> ref->address_matters_p () || !m_symtab_node_map.get (ref->referred)
>
> if refernce goes to external symbol, it behaves like sensitive.
>
> You probably want to update topleve comment explaining what is sensitive and local
> reference and how the hashing is handled.
>> + hstate.add_ptr (ref->referred->ultimate_alias_target ());
>> + }
>> +
>> + if (is_a <cgraph_node *> (node))
>> + {
>> + for (cgraph_edge *e = dyn_cast <cgraph_node *> (node)->callers; e;
>> + e = e->next_caller)
>> + {
>> + sem_item **result = m_symtab_node_map.get (e->callee);
>> + if (!result)
>> + hstate.add_ptr (e->callee->ultimate_alias_target ());
>> + }
>> + }
>> +
>> + hash = hstate.end ();
>> +}
>> +
>> +/* Update hash by computed local hash values taken from different
>> + semantic items. */
>
> Please add TODO that stronger SCC based hashing would be desirable here.
>> @@ -2301,6 +2364,19 @@ sem_item_optimizer::add_item_to_class (congruence_class *cls, sem_item *item)
>> item->cls = cls;
>> }
>>
>> +void
>> +sem_item_optimizer::update_hash_by_addr_refs ()
>
> Add block comment ande xplain why the addr and local updates can not be performed at once
> or someone gets an idea to merge the loops.
>> +{
>> + for (unsigned i = 0; i < m_items.length (); i++)
>> + m_items[i]->update_hash_by_addr_refs (m_symtab_node_map);
>> +
>> + for (unsigned i = 0; i < m_items.length (); i++)
>> + m_items[i]->update_hash_by_local_refs (m_symtab_node_map);
>> +
>> + for (unsigned i = 0; i < m_items.length (); i++)
>> + m_items[i]->hash = m_items[i]->global_hash;
>> +}
>> +
>
> OK with these changes.
> Honza
>
Hello.
Enhanced version of the patch I'm going to install, if no additional notes.
Thanks,
Martin
[-- Attachment #2: 0001-IPA-ICF-include-hash-values-of-references.patch --]
[-- Type: text/x-patch, Size: 6578 bytes --]
From 2823fe3eec49b341afacb57ecb99aeae7c35bd07 Mon Sep 17 00:00:00 2001
From: mliska <mliska@suse.cz>
Date: Fri, 20 Mar 2015 18:00:40 +0100
Subject: [PATCH] IPA ICF: include hash values of references.
gcc/ChangeLog:
2015-03-15 Martin Liska <mliska@suse.cz>
* ipa-icf.c (sem_item::update_hash_by_addr_refs): New function.
(sem_item::update_hash_by_local_refs): Likewise.
(sem_variable::get_hash): Empty line is fixed.
(sem_item_optimizer::execute): Include adding of hash references.
(sem_item_optimizer::update_hash_by_addr_refs): New function.
(sem_item_optimizer::build_hash_based_classes): Use local hash.
* ipa-icf.h (sem_item::update_hash_by_addr_refs): New function.
(sem_item::update_hash_by_local_refs): Likewise.
---
gcc/ipa-icf.c | 93 ++++++++++++++++++++++++++++++++++++++++++++++++++++++++---
gcc/ipa-icf.h | 18 +++++++++++-
2 files changed, 106 insertions(+), 5 deletions(-)
diff --git a/gcc/ipa-icf.c b/gcc/ipa-icf.c
index 360cf17..3cf1261 100644
--- a/gcc/ipa-icf.c
+++ b/gcc/ipa-icf.c
@@ -557,6 +557,72 @@ sem_function::equals_wpa (sem_item *item,
return true;
}
+/* Update hash by address sensitive references. We iterate over all
+ sensitive references (address_matters_p) and we hash ultime alias
+ target of these nodes, which can improve a semantic item hash.
+ TODO: stronger SCC based hashing would be desirable here. */
+
+void
+sem_item::update_hash_by_addr_refs (hash_map <symtab_node *,
+ sem_item *> &m_symtab_node_map)
+{
+ if (is_a <varpool_node *> (node) && DECL_VIRTUAL_P (node->decl))
+ return;
+
+ ipa_ref* ref;
+ inchash::hash hstate (hash);
+ for (unsigned i = 0; i < node->num_references (); i++)
+ {
+ ref = node->iterate_reference (i, ref);
+ if (ref->address_matters_p () || !m_symtab_node_map.get (ref->referred))
+ hstate.add_ptr (ref->referred->ultimate_alias_target ());
+ }
+
+ if (is_a <cgraph_node *> (node))
+ {
+ for (cgraph_edge *e = dyn_cast <cgraph_node *> (node)->callers; e;
+ e = e->next_caller)
+ {
+ sem_item **result = m_symtab_node_map.get (e->callee);
+ if (!result)
+ hstate.add_ptr (e->callee->ultimate_alias_target ());
+ }
+ }
+
+ hash = hstate.end ();
+}
+
+/* Update hash by computed local hash values taken from different
+ semantic items. */
+
+void
+sem_item::update_hash_by_local_refs (hash_map <symtab_node *,
+ sem_item *> &m_symtab_node_map)
+{
+ inchash::hash state (hash);
+ for (unsigned j = 0; j < node->num_references (); j++)
+ {
+ ipa_ref *ref;
+ ref = node->iterate_reference (j, ref);
+ sem_item **result = m_symtab_node_map.get (ref->referring);
+ if (result)
+ state.merge_hash ((*result)->hash);
+ }
+
+ if (type == FUNC)
+ {
+ for (cgraph_edge *e = dyn_cast <cgraph_node *> (node)->callees; e;
+ e = e->next_callee)
+ {
+ sem_item **result = m_symtab_node_map.get (e->caller);
+ if (result)
+ state.merge_hash ((*result)->hash);
+ }
+ }
+
+ global_hash = state.end ();
+}
+
/* Returns true if the item equals to ITEM given as argument. */
bool
@@ -1749,8 +1815,8 @@ hashval_t
sem_variable::get_hash (void)
{
if (hash)
-
return hash;
+
/* All WPA streamed in symbols should have their hashes computed at compile
time. At this point, the constructor may not be in memory at all.
DECL_INITIAL (decl) would be error_mark_node in that case. */
@@ -2216,6 +2282,8 @@ sem_item_optimizer::execute (void)
filter_removed_items ();
unregister_hooks ();
+ build_graph ();
+ update_hash_by_addr_refs ();
build_hash_based_classes ();
if (dump_file)
@@ -2225,8 +2293,6 @@ sem_item_optimizer::execute (void)
for (unsigned int i = 0; i < m_items.length(); i++)
m_items[i]->init_wpa ();
- build_graph ();
-
subdivide_classes_by_equality (true);
if (dump_file)
@@ -2315,6 +2381,25 @@ sem_item_optimizer::add_item_to_class (congruence_class *cls, sem_item *item)
item->cls = cls;
}
+void
+sem_item_optimizer::update_hash_by_addr_refs ()
+{
+ /* First, append to hash sensitive references. */
+ for (unsigned i = 0; i < m_items.length (); i++)
+ m_items[i]->update_hash_by_addr_refs (m_symtab_node_map);
+
+ /* Once all symbols have enhanced hash value, we can append
+ hash values of symbols that are seen by IPA ICF and are
+ references by a semantic item. Newly computed values
+ are saved to global_hash member variable. */
+ for (unsigned i = 0; i < m_items.length (); i++)
+ m_items[i]->update_hash_by_local_refs (m_symtab_node_map);
+
+ /* Global hash value replace current hash values. */
+ for (unsigned i = 0; i < m_items.length (); i++)
+ m_items[i]->hash = m_items[i]->global_hash;
+}
+
/* Congruence classes are built by hash value. */
void
@@ -2324,7 +2409,7 @@ sem_item_optimizer::build_hash_based_classes (void)
{
sem_item *item = m_items[i];
- congruence_class_group *group = get_group_by_hash (item->get_hash (),
+ congruence_class_group *group = get_group_by_hash (item->hash,
item->type);
if (!group->classes.length ())
diff --git a/gcc/ipa-icf.h b/gcc/ipa-icf.h
index 8245b54..ad502a7 100644
--- a/gcc/ipa-icf.h
+++ b/gcc/ipa-icf.h
@@ -189,6 +189,15 @@ public:
/* Dump symbol to FILE. */
virtual void dump_to_file (FILE *file) = 0;
+ /* Update hash by address sensitive references. */
+ void update_hash_by_addr_refs (hash_map <symtab_node *,
+ sem_item *> &m_symtab_node_map);
+
+ /* Update hash by computed local hash values taken from different
+ semantic items. */
+ void update_hash_by_local_refs (hash_map <symtab_node *,
+ sem_item *> &m_symtab_node_map);
+
/* Return base tree that can be used for compatible_types_p and
contains_polymorphic_type_p comparison. */
static bool get_base_types (tree *t1, tree *t2);
@@ -226,9 +235,13 @@ public:
/* A set with symbol table references. */
hash_set <symtab_node *> refs_set;
+ /* Hash of item. */
+ hashval_t hash;
+
+ /* Temporary hash used where hash values of references are added. */
+ hashval_t global_hash;
protected:
/* Cached, once calculated hash for the item. */
- hashval_t hash;
/* Accumulate to HSTATE a hash of constructor expression EXP. */
static void add_expr (const_tree exp, inchash::hash &hstate);
@@ -494,6 +507,9 @@ public:
private:
+ /* Update hash of symbol by address memory references. */
+ void update_hash_by_addr_refs ();
+
/* Congruence classes are built by hash value. */
void build_hash_based_classes (void);
--
2.1.4
^ permalink raw reply [flat|nested] 3+ messages in thread
end of thread, other threads:[~2015-03-22 20:17 UTC | newest]
Thread overview: 3+ messages (download: mbox.gz / follow: Atom feed)
-- links below jump to the message on this page --
2015-03-19 19:39 [PATCH] Speed-up IPA ICF by enhanced hash values Martin Liška
2015-03-19 20:42 ` Jan Hubicka
2015-03-22 20:17 ` Martin Liška
This is a public inbox, see mirroring instructions
for how to clone and mirror all data and code used for this inbox;
as well as URLs for read-only IMAP folder(s) and NNTP newsgroup(s).