From a3dc1a4518793aa75cd60e41cf7f75d234a55031 Mon Sep 17 00:00:00 2001 From: Martin Liska Date: Mon, 24 Nov 2014 11:25:06 +0100 Subject: [PATCH] re PR lto/63968 (175.vpr from cpu2000 fails to build with LTO) PR lto/63968 * 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. From-SVN: r218006 --- gcc/ChangeLog | 12 +++++++++ gcc/bb-reorder.c | 4 +-- gcc/fibonacci_heap.h | 60 +++++++++++++++++++++++++++++++------------- 3 files changed, 57 insertions(+), 19 deletions(-) diff --git a/gcc/ChangeLog b/gcc/ChangeLog index d9507500dd4..8f42d090245 100644 --- a/gcc/ChangeLog +++ b/gcc/ChangeLog @@ -1,3 +1,15 @@ +2014-11-24 Martin Liska + + PR lto/63968 + * 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. + 2014-11-24 Richard Biener PR tree-optimization/55334 diff --git a/gcc/bb-reorder.c b/gcc/bb-reorder.c index 689d7b6a471..b568114ecb7 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 ecb92f8b01f..3fce3701737 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::insert (K key, V *data) /* Create the new node. */ fibonacci_node *node = new fibonacci_node_t (); + return insert (node, key, data); +} + +/* Insert new NODE given by KEY and DATA associated with the key. */ + +template +fibonacci_node* +fibonacci_heap::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::replace_key_data (fibonacci_node *node, K key, V *data) { - V *odata; K okey; fibonacci_node *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::replace_key_data (fibonacci_node *node, K key, /* Extract minimum node in the heap. */ template V* -fibonacci_heap::extract_min () +fibonacci_heap::extract_min (bool release) { fibonacci_node *z; V *ret = NULL; @@ -397,28 +421,30 @@ fibonacci_heap::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 V* -fibonacci_heap::delete_node (fibonacci_node *node) +fibonacci_heap::delete_node (fibonacci_node *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; } -- 2.30.2