> gcc/ChangeLog:
>
> 2014-11-13 Martin Liska <mli...@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
