> Hello.
>
> As I reimplemented fibheap to C++ template, Honza told me that replace_key
> method actually
> supports just decrement operation. Old implementation suppress any feedback
> if we try to increase key:
>
> fibheap.c:
> ...
> /* If we wanted to, we could actually do a real increase by redeleting and
> inserting. However, this would require O (log n) time. So just bail out
> for now. */
> if (fibheap_comp_data (heap, key, data, node) > 0)
> return NULL;
> ...
>
> My reimplementation added assert for such kind operation, as this PR shows we
> try to do increment in reorder-bb.
> Thus, I added fibonacci_heap::replace_key method that can increment key (it
> deletes the node and new key
> is associated with the node).
>
> The patch can bootstrap on x86_64-linux-pc and no new regression was
> introduced.
> I would like to ask someone if the increase operation for bb-reorder is valid
> or not?
Can you verify that the implementation is correct? I tend to remember that I
introduced the
lazy incerementation to inliner both for perofrmance and correctness reasons. I
used to get
odd orders when keys was increased.
Honza
>
> Thanks,
> Martin
> gcc/ChangeLog:
>
> 2014-11-20 Martin Liska <mli...@suse.cz>
>
> * bb-reorder.c (find_traces_1_round): decreate_key is replaced
> with replace_key method.
> * fibonacci_heap.h (fibonacci_heap::insert): New argument.
> (fibonacci_heap::replace_key_data): Likewise.
> (fibonacci_heap::replace_key): New method that can even increment key,
> this operation costs O(log N).
> (fibonacci_heap::extract_min): New argument.
> (fibonacci_heap::delete_node): Likewise.
> diff --git a/gcc/bb-reorder.c b/gcc/bb-reorder.c
> index 689d7b6..b568114 100644
> --- a/gcc/bb-reorder.c
> +++ b/gcc/bb-reorder.c
> @@ -644,7 +644,7 @@ find_traces_1_round (int branch_th, int exec_th,
> gcov_type count_th,
> (long) bbd[e->dest->index].node->get_key (),
> key);
> }
> - bbd[e->dest->index].heap->decrease_key
> + bbd[e->dest->index].heap->replace_key
> (bbd[e->dest->index].node, key);
> }
> }
> @@ -812,7 +812,7 @@ find_traces_1_round (int branch_th, int exec_th,
> gcov_type count_th,
> e->dest->index,
> (long) bbd[e->dest->index].node->get_key (),
> key);
> }
> - bbd[e->dest->index].heap->decrease_key
> + bbd[e->dest->index].heap->replace_key
> (bbd[e->dest->index].node, key);
> }
> }
> diff --git a/gcc/fibonacci_heap.h b/gcc/fibonacci_heap.h
> index ecb92f8..3fce370 100644
> --- a/gcc/fibonacci_heap.h
> +++ b/gcc/fibonacci_heap.h
> @@ -183,20 +183,27 @@ public:
> }
>
> /* For given NODE, set new KEY value. */
> - K decrease_key (fibonacci_node_t *node, K key)
> + K replace_key (fibonacci_node_t *node, K key)
> {
> K okey = node->m_key;
> - gcc_assert (key <= okey);
>
> replace_key_data (node, key, node->m_data);
> return okey;
> }
>
> + /* For given NODE, decrease value to new KEY. */
> + K decrease_key (fibonacci_node_t *node, K key)
> + {
> + gcc_assert (key <= node->m_key);
> + return replace_key (node, key);
> + }
> +
> /* For given NODE, set new KEY and DATA value. */
> V *replace_key_data (fibonacci_node_t *node, K key, V *data);
>
> - /* Extract minimum node in the heap. */
> - V *extract_min ();
> + /* Extract minimum node in the heap. If RELEASE is specified,
> + memory is released. */
> + V *extract_min (bool release = true);
>
> /* Return value associated with minimum node in the heap. */
> V *min ()
> @@ -214,12 +221,15 @@ public:
> }
>
> /* Delete NODE in the heap. */
> - V *delete_node (fibonacci_node_t *node);
> + V *delete_node (fibonacci_node_t *node, bool release = true);
>
> /* Union the heap with HEAPB. */
> fibonacci_heap *union_with (fibonacci_heap *heapb);
>
> private:
> + /* Insert new NODE given by KEY and DATA associated with the key. */
> + fibonacci_node_t *insert (fibonacci_node_t *node, K key, V *data);
> +
> /* Insert it into the root list. */
> void insert_root (fibonacci_node_t *node);
>
> @@ -322,6 +332,15 @@ fibonacci_heap<K,V>::insert (K key, V *data)
> /* Create the new node. */
> fibonacci_node<K,V> *node = new fibonacci_node_t ();
>
> + return insert (node, key, data);
> +}
> +
> +/* Insert new NODE given by KEY and DATA associated with the key. */
> +
> +template<class K, class V>
> +fibonacci_node<K,V>*
> +fibonacci_heap<K,V>::insert (fibonacci_node_t *node, K key, V *data)
> +{
> /* Set the node's data. */
> node->m_data = data;
> node->m_key = key;
> @@ -345,17 +364,22 @@ V*
> fibonacci_heap<K,V>::replace_key_data (fibonacci_node<K,V> *node, K key,
> V *data)
> {
> - V *odata;
> K okey;
> fibonacci_node<K,V> *y;
> + V *odata = node->m_data;
>
> - /* If we wanted to, we could actually do a real increase by redeleting and
> - inserting. However, this would require O (log n) time. So just bail out
> - for now. */
> + /* If we wanted to, we do a real increase by redeleting and
> + inserting. */
> if (node->compare_data (key) > 0)
> - return NULL;
> + {
> + delete_node (node, false);
> +
> + node = new (node) fibonacci_node_t ();
> + insert (node, key, data);
> +
> + return odata;
> + }
>
> - odata = node->m_data;
> okey = node->m_key;
> node->m_data = data;
> node->m_key = key;
> @@ -385,7 +409,7 @@ fibonacci_heap<K,V>::replace_key_data
> (fibonacci_node<K,V> *node, K key,
> /* Extract minimum node in the heap. */
> template<class K, class V>
> V*
> -fibonacci_heap<K,V>::extract_min ()
> +fibonacci_heap<K,V>::extract_min (bool release)
> {
> fibonacci_node<K,V> *z;
> V *ret = NULL;
> @@ -397,28 +421,30 @@ fibonacci_heap<K,V>::extract_min ()
> node's data. */
> z = extract_minimum_node ();
> ret = z->m_data;
> - delete (z);
> +
> + if (release)
> + delete (z);
> }
>
> return ret;
> }
>
> -/* Delete NODE in the heap. */
> +/* Delete NODE in the heap, if RELEASE is specified memory is released. */
>
> template<class K, class V>
> V*
> -fibonacci_heap<K,V>::delete_node (fibonacci_node<K,V> *node)
> +fibonacci_heap<K,V>::delete_node (fibonacci_node<K,V> *node, bool release)
> {
> V *ret = node->m_data;
>
> /* To perform delete, we just make it the min key, and extract. */
> - decrease_key (node, m_global_min_key);
> + replace_key (node, m_global_min_key);
> if (node != m_min)
> {
> fprintf (stderr, "Can't force minimum on fibheap.\n");
> abort ();
> }
> - extract_min ();
> + extract_min (release);
>
> return ret;
> }
