* [PATCH 2/2] IPA ICF: use fibonacci heap instead of list as a worklist.
@ 2019-06-03 13:39 Martin Liška
2019-06-03 14:56 ` Jan Hubicka
0 siblings, 1 reply; 2+ messages in thread
From: Martin Liška @ 2019-06-03 13:39 UTC (permalink / raw)
To: gcc-patches; +Cc: Jan Hubicka
[-- Attachment #1: Type: text/plain, Size: 781 bytes --]
This is second part which has not a significant speed up but
it's mentioned in the Value Numbering algorithm as a useful heuristics.
Patch can bootstrap on x86_64-linux-gnu and survives regression tests.
Ready to be installed?
Thanks,
Martin
gcc/ChangeLog:
2019-06-03 Martin Liska <mliska@suse.cz>
* ipa-icf.c (sem_item_optimizer::add_item_to_class): Count
number of references.
(sem_item_optimizer::do_congruence_step):
(sem_item_optimizer::worklist_push): Dump how references
a class has.
(sem_item_optimizer::worklist_pop): Use heap.
(sem_item_optimizer::process_cong_reduction): Likewise.
* ipa-icf.h: Use fibonacci_heap insteam of std::list.
---
gcc/ipa-icf.c | 12 +++++++-----
gcc/ipa-icf.h | 8 ++++++--
2 files changed, 13 insertions(+), 7 deletions(-)
[-- Attachment #2: 0002-IPA-ICF-use-fibonacci-heap-instead-of-list-as-a-work.patch --]
[-- Type: text/x-patch, Size: 2944 bytes --]
diff --git a/gcc/ipa-icf.c b/gcc/ipa-icf.c
index a4705eee936..ac563623ea2 100644
--- a/gcc/ipa-icf.c
+++ b/gcc/ipa-icf.c
@@ -80,6 +80,7 @@ along with GCC; see the file COPYING3. If not see
#include "print-tree.h"
#include "ipa-utils.h"
#include "ipa-icf-gimple.h"
+#include "fibonacci_heap.h"
#include "ipa-icf.h"
#include "stor-layout.h"
#include "dbgcnt.h"
@@ -2626,6 +2627,7 @@ 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);
+ cls->referenced_by_count += item->referenced_by_count;
item->cls = cls;
}
@@ -3188,7 +3190,8 @@ sem_item_optimizer::do_congruence_step (congruence_class *cls)
{
if (dump_file && (dump_flags & TDF_DETAILS))
fprintf (dump_file, " processing congruence step for class: %u "
- "(%u items), index: %u\n", cls->id, cls->members.length (), i);
+ "(%u items, %u references), index: %u\n", cls->id,
+ cls->referenced_by_count, cls->members.length (), i);
do_congruence_step_for_index (cls, i);
if (splitter_class_removed)
@@ -3208,7 +3211,7 @@ sem_item_optimizer::worklist_push (congruence_class *cls)
return;
cls->in_worklist = true;
- worklist.push_back (cls);
+ worklist.insert (cls->referenced_by_count, cls);
}
/* Pops a class from worklist. */
@@ -3220,8 +3223,7 @@ sem_item_optimizer::worklist_pop (void)
while (!worklist.empty ())
{
- cls = worklist.front ();
- worklist.pop_front ();
+ cls = worklist.extract_min ();
if (cls->in_worklist)
{
cls->in_worklist = false;
@@ -3253,7 +3255,7 @@ sem_item_optimizer::process_cong_reduction (void)
if (dump_file)
fprintf (dump_file, "Worklist has been filled with: %lu\n",
- (unsigned long) worklist.size ());
+ (unsigned long) worklist.nodes ());
if (dump_file && (dump_flags & TDF_DETAILS))
fprintf (dump_file, "Congruence class reduction\n");
diff --git a/gcc/ipa-icf.h b/gcc/ipa-icf.h
index ede4c94dbd3..6b81eb38b2a 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),
+ referenced_by_count (0)
{
}
@@ -54,6 +55,9 @@ public:
/* Global unique class identifier. */
unsigned int id;
+
+ /* Total number of references to items of this class. */
+ unsigned referenced_by_count;
};
/* Semantic item type enum. */
@@ -530,7 +534,7 @@ public:
/* Worklist of congruence classes that can potentially
refine classes of congruence. */
- std::list<congruence_class *> worklist;
+ fibonacci_heap<unsigned, congruence_class> worklist;
/* Remove semantic ITEM and release memory. */
void remove_item (sem_item *item);
^ permalink raw reply [flat|nested] 2+ messages in thread
* Re: [PATCH 2/2] IPA ICF: use fibonacci heap instead of list as a worklist.
2019-06-03 13:39 [PATCH 2/2] IPA ICF: use fibonacci heap instead of list as a worklist Martin Liška
@ 2019-06-03 14:56 ` Jan Hubicka
0 siblings, 0 replies; 2+ messages in thread
From: Jan Hubicka @ 2019-06-03 14:56 UTC (permalink / raw)
To: Martin Liška; +Cc: gcc-patches
> This is second part which has not a significant speed up but
> it's mentioned in the Value Numbering algorithm as a useful heuristics.
>
> Patch can bootstrap on x86_64-linux-gnu and survives regression tests.
>
> Ready to be installed?
> Thanks,
> Martin
>
> gcc/ChangeLog:
>
> 2019-06-03 Martin Liska <mliska@suse.cz>
>
> * ipa-icf.c (sem_item_optimizer::add_item_to_class): Count
> number of references.
> (sem_item_optimizer::do_congruence_step):
> (sem_item_optimizer::worklist_push): Dump how references
> a class has.
> (sem_item_optimizer::worklist_pop): Use heap.
> (sem_item_optimizer::process_cong_reduction): Likewise.
> * ipa-icf.h: Use fibonacci_heap insteam of std::list.
I am not quite sure if the patch is not an overkill - fibonacci
heap has quite noticeable constant factors.
But I suppose we will see it in profiles easilly then, so patch
is OK and lets see if this helps in practice.
Honza
> ---
> gcc/ipa-icf.c | 12 +++++++-----
> gcc/ipa-icf.h | 8 ++++++--
> 2 files changed, 13 insertions(+), 7 deletions(-)
>
>
> diff --git a/gcc/ipa-icf.c b/gcc/ipa-icf.c
> index a4705eee936..ac563623ea2 100644
> --- a/gcc/ipa-icf.c
> +++ b/gcc/ipa-icf.c
> @@ -80,6 +80,7 @@ along with GCC; see the file COPYING3. If not see
> #include "print-tree.h"
> #include "ipa-utils.h"
> #include "ipa-icf-gimple.h"
> +#include "fibonacci_heap.h"
> #include "ipa-icf.h"
> #include "stor-layout.h"
> #include "dbgcnt.h"
> @@ -2626,6 +2627,7 @@ 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);
> + cls->referenced_by_count += item->referenced_by_count;
> item->cls = cls;
> }
>
> @@ -3188,7 +3190,8 @@ sem_item_optimizer::do_congruence_step (congruence_class *cls)
> {
> if (dump_file && (dump_flags & TDF_DETAILS))
> fprintf (dump_file, " processing congruence step for class: %u "
> - "(%u items), index: %u\n", cls->id, cls->members.length (), i);
> + "(%u items, %u references), index: %u\n", cls->id,
> + cls->referenced_by_count, cls->members.length (), i);
> do_congruence_step_for_index (cls, i);
>
> if (splitter_class_removed)
> @@ -3208,7 +3211,7 @@ sem_item_optimizer::worklist_push (congruence_class *cls)
> return;
>
> cls->in_worklist = true;
> - worklist.push_back (cls);
> + worklist.insert (cls->referenced_by_count, cls);
> }
>
> /* Pops a class from worklist. */
> @@ -3220,8 +3223,7 @@ sem_item_optimizer::worklist_pop (void)
>
> while (!worklist.empty ())
> {
> - cls = worklist.front ();
> - worklist.pop_front ();
> + cls = worklist.extract_min ();
> if (cls->in_worklist)
> {
> cls->in_worklist = false;
> @@ -3253,7 +3255,7 @@ sem_item_optimizer::process_cong_reduction (void)
>
> if (dump_file)
> fprintf (dump_file, "Worklist has been filled with: %lu\n",
> - (unsigned long) worklist.size ());
> + (unsigned long) worklist.nodes ());
>
> if (dump_file && (dump_flags & TDF_DETAILS))
> fprintf (dump_file, "Congruence class reduction\n");
> diff --git a/gcc/ipa-icf.h b/gcc/ipa-icf.h
> index ede4c94dbd3..6b81eb38b2a 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),
> + referenced_by_count (0)
> {
> }
>
> @@ -54,6 +55,9 @@ public:
>
> /* Global unique class identifier. */
> unsigned int id;
> +
> + /* Total number of references to items of this class. */
> + unsigned referenced_by_count;
> };
>
> /* Semantic item type enum. */
> @@ -530,7 +534,7 @@ public:
>
> /* Worklist of congruence classes that can potentially
> refine classes of congruence. */
> - std::list<congruence_class *> worklist;
> + fibonacci_heap<unsigned, congruence_class> worklist;
>
> /* Remove semantic ITEM and release memory. */
> void remove_item (sem_item *item);
>
^ permalink raw reply [flat|nested] 2+ messages in thread
end of thread, other threads:[~2019-06-03 14:56 UTC | newest]
Thread overview: 2+ messages (download: mbox.gz / follow: Atom feed)
-- links below jump to the message on this page --
2019-06-03 13:39 [PATCH 2/2] IPA ICF: use fibonacci heap instead of list as a worklist Martin Liška
2019-06-03 14:56 ` Jan Hubicka
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).