[2/2] IPA ICF: use fibonacci heap instead of list as a worklist.

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(-)

> 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);
>