diff options
author | Jan Hubicka <jh@suse.cz> | 2019-11-20 16:04:34 +0100 |
---|---|---|
committer | Jan Hubicka <hubicka@gcc.gnu.org> | 2019-11-20 15:04:34 +0000 |
commit | 516fd7cedb025b09000563cdba6214461621400d (patch) | |
tree | 61c772013cc91032ba6dcdcaffd99445d40bd10b | |
parent | f6fbdc385ae9fd3f07b2f5fe8b7fe2a134622be7 (diff) |
Add pool_allocator for fibonaci heaps.
* fibonacci_heap.h (fibonacci_heap<K,V>::fibonacci_heap):
Add allocator parameter.
(fibonacci_heap<K,V>::~fibonacci_heap): Optimize destruction.
(fibonacci_heap<K,V>::m_allocator): New.
(fibonacci_heap<K,V>::m_own_allocator): New.
(fibonacci_heap<K,V>::insert): Use allocator.
(fibonacci_heap<K,V>::extract_min): Likewise.
(fibonacci_heap<K,V>::union_with): Assert that both heaps share
allocator.
(fibonacci_heap<K,V>::consolidate): Allocate constant sized vector
on stack.
* fibonacci_heap.c: Include alloc-pool
(test_empty_heap): Initialize allocator.
(test_union): Likewise.
* bb-reorder.c: Include alloc-pool.h.
* tracer.c: Inlclude alloc-pool.h.
From-SVN: r278501
-rw-r--r-- | gcc/ChangeLog | 19 | ||||
-rw-r--r-- | gcc/bb-reorder.c | 1 | ||||
-rw-r--r-- | gcc/fibonacci_heap.c | 16 | ||||
-rw-r--r-- | gcc/fibonacci_heap.h | 52 | ||||
-rw-r--r-- | gcc/tracer.c | 1 |
5 files changed, 73 insertions, 16 deletions
diff --git a/gcc/ChangeLog b/gcc/ChangeLog index c8f1928eb2d..6eb037f7d45 100644 --- a/gcc/ChangeLog +++ b/gcc/ChangeLog @@ -1,5 +1,24 @@ 2019-11-20 Jan Hubicka <jh@suse.cz> + * fibonacci_heap.h (fibonacci_heap<K,V>::fibonacci_heap): + Add allocator parameter. + (fibonacci_heap<K,V>::~fibonacci_heap): Optimize destruction. + (fibonacci_heap<K,V>::m_allocator): New. + (fibonacci_heap<K,V>::m_own_allocator): New. + (fibonacci_heap<K,V>::insert): Use allocator. + (fibonacci_heap<K,V>::extract_min): Likewise. + (fibonacci_heap<K,V>::union_with): Assert that both heaps share + allocator. + (fibonacci_heap<K,V>::consolidate): Allocate constant sized vector + on stack. + * fibonacci_heap.c: Include alloc-pool + (test_empty_heap): Initialize allocator. + (test_union): Likewise. + * bb-reorder.c: Include alloc-pool.h. + * tracer.c: Inlclude alloc-pool.h. + +2019-11-20 Jan Hubicka <jh@suse.cz> + * lto-streamer-out.c (DFS::sccstack): Turn into auto-vec. Preallocate for 32 entries. (DFS::worklist): Likewise. diff --git a/gcc/bb-reorder.c b/gcc/bb-reorder.c index f811569a7df..d1a2f1e1115 100644 --- a/gcc/bb-reorder.c +++ b/gcc/bb-reorder.c @@ -112,6 +112,7 @@ #include "cfgcleanup.h" #include "bb-reorder.h" #include "except.h" +#include "alloc-pool.h" #include "fibonacci_heap.h" #include "stringpool.h" #include "attribs.h" diff --git a/gcc/fibonacci_heap.c b/gcc/fibonacci_heap.c index bddd0477694..2470715a70c 100644 --- a/gcc/fibonacci_heap.c +++ b/gcc/fibonacci_heap.c @@ -21,6 +21,7 @@ along with GCC; see the file COPYING3. If not see #include "config.h" #include "system.h" #include "coretypes.h" +#include "alloc-pool.h" #include "fibonacci_heap.h" #include "selftest.h" @@ -38,13 +39,14 @@ typedef fibonacci_heap <int, int> int_heap_t; static void test_empty_heap () { - int_heap_t *h1 = new int_heap_t (INT_MIN); + pool_allocator allocator ("fibheap test", sizeof (int_heap_node_t)); + int_heap_t *h1 = new int_heap_t (INT_MIN, &allocator); ASSERT_TRUE (h1->empty ()); ASSERT_EQ (0, h1->nodes ()); ASSERT_EQ (NULL, h1->min ()); - int_heap_t *h2 = new int_heap_t (INT_MIN); + int_heap_t *h2 = new int_heap_t (INT_MIN, &allocator); int_heap_t *r = h1->union_with (h2); ASSERT_TRUE (r->empty ()); @@ -169,12 +171,13 @@ static void test_union () { int value = 777; + pool_allocator allocator ("fibheap test", sizeof (int_heap_node_t)); - int_heap_t *heap1 = new int_heap_t (INT_MIN); + int_heap_t *heap1 = new int_heap_t (INT_MIN, &allocator); for (unsigned i = 0; i < 2 * TEST_HEAP_N; i++) heap1->insert (i, &value); - int_heap_t *heap2 = new int_heap_t (INT_MIN); + int_heap_t *heap2 = new int_heap_t (INT_MIN, &allocator); for (unsigned i = 2 * TEST_HEAP_N; i < 3 * TEST_HEAP_N; i++) heap2->insert (i, &value); @@ -196,12 +199,13 @@ static void test_union_of_equal_heaps () { int value = 777; + pool_allocator allocator ("fibheap test", sizeof (int_heap_node_t)); - int_heap_t *heap1 = new int_heap_t (INT_MIN); + int_heap_t *heap1 = new int_heap_t (INT_MIN, &allocator); for (unsigned i = 0; i < TEST_HEAP_N; i++) heap1->insert (i, &value); - int_heap_t *heap2 = new int_heap_t (INT_MIN); + int_heap_t *heap2 = new int_heap_t (INT_MIN, &allocator); for (unsigned i = 0; i < TEST_HEAP_N; i++) heap2->insert (i, &value); diff --git a/gcc/fibonacci_heap.h b/gcc/fibonacci_heap.h index 2ff26270048..9961648d505 100644 --- a/gcc/fibonacci_heap.h +++ b/gcc/fibonacci_heap.h @@ -145,17 +145,36 @@ class fibonacci_heap friend class fibonacci_node<K,V>; public: - /* Default constructor. */ - fibonacci_heap (K global_min_key): m_nodes (0), m_min (NULL), m_root (NULL), - m_global_min_key (global_min_key) + /* Default constructor. ALLOCATOR is optional and is primarily useful + when heaps are going to be merged (in that case they need to be allocated + in same alloc pool). */ + fibonacci_heap (K global_min_key, pool_allocator *allocator = NULL): + m_nodes (0), m_min (NULL), m_root (NULL), + m_global_min_key (global_min_key), + m_allocator (allocator), m_own_allocator (false) { + if (!m_allocator) + { + m_allocator = new pool_allocator ("Fibonacci heap", + sizeof (fibonacci_node_t)); + m_own_allocator = true; + } } /* Destructor. */ ~fibonacci_heap () { - while (m_min != NULL) - delete (extract_minimum_node ()); + /* Actual memory will be released by the destructor of m_allocator. */ + if (need_finalization_p<fibonacci_node_t> () || !m_own_allocator) + while (m_min != NULL) + { + fibonacci_node_t *n = extract_minimum_node (); + n->~fibonacci_node_t (); + if (!m_own_allocator) + m_allocator->remove (n); + } + if (m_own_allocator) + delete m_allocator; } /* Insert new node given by KEY and DATA associated with the key. */ @@ -259,6 +278,11 @@ private: fibonacci_node_t *m_root; /* Global minimum given in the heap construction. */ K m_global_min_key; + + /* Allocator used to hold nodes. */ + pool_allocator *m_allocator; + /* True if alocator is owned by the current heap only. */ + bool m_own_allocator; }; /* Remove fibonacci heap node. */ @@ -333,7 +357,8 @@ fibonacci_node<K,V>* fibonacci_heap<K,V>::insert (K key, V *data) { /* Create the new node. */ - fibonacci_node<K,V> *node = new fibonacci_node_t (key, data); + fibonacci_node<K,V> *node = new (m_allocator->allocate ()) + fibonacci_node_t (key, data); return insert_node (node); } @@ -438,7 +463,10 @@ fibonacci_heap<K,V>::extract_min (bool release) ret = z->m_data; if (release) - delete (z); + { + z->~fibonacci_node_t (); + m_allocator->remove (z); + } } return ret; @@ -474,6 +502,9 @@ fibonacci_heap<K,V>::union_with (fibonacci_heap<K,V> *heapb) fibonacci_node<K,V> *a_root, *b_root; + /* Both heaps must share allocator. */ + gcc_checking_assert (m_allocator == heapb->m_allocator); + /* If one of the heaps is empty, the union is just the other heap. */ if ((a_root = heapa->m_root) == NULL) { @@ -616,12 +647,13 @@ fibonacci_heap<K,V>::remove_root (fibonacci_node<K,V> *node) template<class K, class V> void fibonacci_heap<K,V>::consolidate () { - int D = 1 + 8 * sizeof (long); - auto_vec<fibonacci_node<K,V> *> a (D); - a.safe_grow_cleared (D); + const int D = 1 + 8 * sizeof (long); + auto_vec<fibonacci_node<K,V> *, D> a; fibonacci_node<K,V> *w, *x, *y; int i, d; + a.quick_grow_cleared (D); + while ((w = m_root) != NULL) { x = w; diff --git a/gcc/tracer.c b/gcc/tracer.c index 4ee3fef92ec..7db0d285a70 100644 --- a/gcc/tracer.c +++ b/gcc/tracer.c @@ -49,6 +49,7 @@ #include "tree-ssa.h" #include "tree-inline.h" #include "cfgloop.h" +#include "alloc-pool.h" #include "fibonacci_heap.h" #include "tracer.h" |