From c3af5442898aadc277f95732fd40287a2d5cfc86 Mon Sep 17 00:00:00 2001 From: Martin Liska Date: Tue, 4 Jun 2019 09:53:08 +0200 Subject: [PATCH] IPA ICF: use fibonacci heap instead of list as a worklist. 2019-06-04 Martin Liska * 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. From-SVN: r271901 --- gcc/ChangeLog | 11 +++++++++++ gcc/ipa-icf.c | 12 +++++++----- gcc/ipa-icf.h | 8 ++++++-- 3 files changed, 24 insertions(+), 7 deletions(-) diff --git a/gcc/ChangeLog b/gcc/ChangeLog index 8fbeb6eb1fb..d249d12ca50 100644 --- a/gcc/ChangeLog +++ b/gcc/ChangeLog @@ -1,3 +1,14 @@ +2019-06-04 Martin Liska + + * 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. + 2019-06-04 Martin Liska * ipa-icf.h (struct sem_usage_pair_hash): New. diff --git a/gcc/ipa-icf.c b/gcc/ipa-icf.c index 9f1e2c8f38e..19b45b35c9a 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" @@ -2624,6 +2625,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; } @@ -3186,7 +3188,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) @@ -3206,7 +3209,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. */ @@ -3218,8 +3221,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; @@ -3251,7 +3253,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 worklist; + fibonacci_heap worklist; /* Remove semantic ITEM and release memory. */ void remove_item (sem_item *item); -- 2.30.2