Re: [PATCH 2/9] New template fibonacci_heap class introduced.

[Jan Hubicka <hubicka at ucw dot cz>]

> gcc/ChangeLog:
> 
> 2014-11-13  Martin Liska  <mliska@suse.cz>
> 
> 	* fibonacci_heap.h: New file.
> 	* ipa-inline.c (update_edge_key): New heap API is used.
> 	(update_caller_keys): Likewise.
> 	(update_callee_keys): Likewise.
> 	(lookup_recursive_calls): Likewise.
> 	(recursive_inlining): Likewise.
> 	(add_new_edges_to_heap): Likewise.
> 	(heap_edge_removal_hook): Likewise.
> 	(inline_small_functions): Likewise.

My C++-fu is not on par to properly review fibonaci_heap.h.  Trevor, Richard, could
you please comment? My only concer is about the amount of code this winds into that
may be shared across instantiations in other way than via ICF :)

Also I wonder if API compatibility with std:: heaps would be useful in future.
(we can not use priority queue from libstdc++ because inliner actually need operation
to decrease keys badness and to remove a key)

> diff --git a/gcc/ipa-inline.c b/gcc/ipa-inline.c
> index 5c97815..1ce856f 100644
> --- a/gcc/ipa-inline.c
> +++ b/gcc/ipa-inline.c
> @@ -138,6 +138,10 @@ along with GCC; see the file COPYING3.  If not see
>  #include "auto-profile.h"
>  #include "cilk.h"
>  #include "builtins.h"
> +#include "fibonacci_heap.h"
> +
> +typedef fibonacci_heap <long, cgraph_edge> edge_heap_t;
> +typedef fibonacci_node <long, cgraph_edge> edge_heap_node_t;

The second can be just typedef of first, right?
>  
>  /* Statistics we collect about inlining algorithm.  */
>  static int overall_size;
> @@ -1076,19 +1080,19 @@ edge_badness (struct cgraph_edge *edge, bool dump)
>  
>  /* Recompute badness of EDGE and update its key in HEAP if needed.  */
>  static inline void
> -update_edge_key (fibheap_t heap, struct cgraph_edge *edge)
> +update_edge_key (edge_heap_t *heap, struct cgraph_edge *edge)
>  {
>    int badness = edge_badness (edge, false);
>    if (edge->aux)
>      {
> -      fibnode_t n = (fibnode_t) edge->aux;
> -      gcc_checking_assert (n->data == edge);
> +      edge_heap_node_t *n = (edge_heap_node_t *) edge->aux;
> +      gcc_checking_assert (n->get_data () == edge);
>  
> -      /* fibheap_replace_key only decrease the keys.
> +      /* fibonacci_heap::replace_key only decrease the keys.
>  	 When we increase the key we do not update heap
>  	 and instead re-insert the element once it becomes
>  	 a minimum of heap.  */
> -      if (badness < n->key)
> +      if (badness < n->get_key ())
>  	{
>  	  if (dump_file && (dump_flags & TDF_DETAILS))
>  	    {
> @@ -1098,11 +1102,11 @@ update_edge_key (fibheap_t heap, struct cgraph_edge *edge)
>  		       edge->caller->order,
>  		       xstrdup (edge->callee->name ()),
>  		       edge->callee->order,
> -		       (int)n->key,
> +		       (int)n->get_key (),
>  		       badness);
>  	    }
> -	  fibheap_replace_key (heap, n, badness);
> -	  gcc_checking_assert (n->key == badness);
> +	  heap->replace_key (n, badness);

One thing that can be "fixed" is that fibheap actually do not allow you to increase key
(if you do so it will give bogus order). Perhaps replace_key should be called decrease_key ;)

Otherwise the ipa-inline.c changes are OK.

Honza