This is the mail archive of the
gcc-patches@gcc.gnu.org
mailing list for the GCC project.
[PATCH 3/9] fibonacci_heap is used for bb-reoder purpose.
- From: mliska <mliska at suse dot cz>
- To: gcc-patches at gcc dot gnu dot org
- Date: Thu, 13 Nov 2014 02:45:07 +0100
- Subject: [PATCH 3/9] fibonacci_heap is used for bb-reoder purpose.
- Authentication-results: sourceware.org; auth=none
- References: <398814b6afe28679f16c5d4b9879accb7984b76b dot 1415911038 dot git dot mliska at suse dot cz>
- Resent-user-agent: Mozilla/5.0 (X11; Linux x86_64; rv:31.0) Gecko/20100101 Thunderbird/31.2.0
gcc/ChangeLog:
2014-11-13 Martin Liska <mliska@suse.cz>
* bb-reorder.c (mark_bb_visited): New fibonacci_heap is used.
(find_traces): Likewise.
(find_traces_1_round): Likewise.
---
gcc/bb-reorder.c | 54 +++++++++++++++++++++++++++---------------------------
1 file changed, 27 insertions(+), 27 deletions(-)
diff --git a/gcc/bb-reorder.c b/gcc/bb-reorder.c
index 1f7c3ee..b1223a7 100644
--- a/gcc/bb-reorder.c
+++ b/gcc/bb-reorder.c
@@ -120,6 +120,7 @@
#include "ipa-ref.h"
#include "cgraph.h"
#include "except.h"
+#include "fibonacci_heap.h"
/* The number of rounds. In most cases there will only be 4 rounds, but
when partitioning hot and cold basic blocks into separate sections of
@@ -153,6 +154,9 @@ static const int exec_threshold[N_ROUNDS] = {500, 200, 50, 0, 0};
block the edge destination is not duplicated while connecting traces. */
#define DUPLICATION_THRESHOLD 100
+typedef fibonacci_heap <long, basic_block_def> bb_heap_t;
+typedef fibonacci_node <long, basic_block_def> bb_heap_node_t;
+
/* Structure to hold needed information for each basic block. */
typedef struct bbro_basic_block_data_def
{
@@ -169,10 +173,10 @@ typedef struct bbro_basic_block_data_def
int visited;
/* Which heap is BB in (if any)? */
- fibheap_t heap;
+ bb_heap_t *heap;
/* Which heap node is BB in (if any)? */
- fibnode_t node;
+ bb_heap_node_t *node;
} bbro_basic_block_data;
/* The current size of the following dynamic array. */
@@ -210,7 +214,7 @@ static void find_traces (int *, struct trace *);
static basic_block rotate_loop (edge, struct trace *, int);
static void mark_bb_visited (basic_block, int);
static void find_traces_1_round (int, int, gcov_type, struct trace *, int *,
- int, fibheap_t *, int);
+ int, bb_heap_t **, int);
static basic_block copy_bb (basic_block, edge, basic_block, int);
static fibheapkey_t bb_to_key (basic_block);
static bool better_edge_p (const_basic_block, const_edge, int, int, int, int,
@@ -238,7 +242,7 @@ mark_bb_visited (basic_block bb, int trace)
bbd[bb->index].visited = trace;
if (bbd[bb->index].heap)
{
- fibheap_delete_node (bbd[bb->index].heap, bbd[bb->index].node);
+ bbd[bb->index].heap->delete_node (bbd[bb->index].node);
bbd[bb->index].heap = NULL;
bbd[bb->index].node = NULL;
}
@@ -283,7 +287,7 @@ find_traces (int *n_traces, struct trace *traces)
int number_of_rounds;
edge e;
edge_iterator ei;
- fibheap_t heap;
+ bb_heap_t *heap = new bb_heap_t (LONG_MIN);
/* Add one extra round of trace collection when partitioning hot/cold
basic blocks into separate sections. The last round is for all the
@@ -292,14 +296,12 @@ find_traces (int *n_traces, struct trace *traces)
number_of_rounds = N_ROUNDS - 1;
/* Insert entry points of function into heap. */
- heap = fibheap_new ();
max_entry_frequency = 0;
max_entry_count = 0;
FOR_EACH_EDGE (e, ei, ENTRY_BLOCK_PTR_FOR_FN (cfun)->succs)
{
bbd[e->dest->index].heap = heap;
- bbd[e->dest->index].node = fibheap_insert (heap, bb_to_key (e->dest),
- e->dest);
+ bbd[e->dest->index].node = heap->insert (bb_to_key (e->dest), e->dest);
if (e->dest->frequency > max_entry_frequency)
max_entry_frequency = e->dest->frequency;
if (e->dest->count > max_entry_count)
@@ -324,7 +326,7 @@ find_traces (int *n_traces, struct trace *traces)
count_threshold, traces, n_traces, i, &heap,
number_of_rounds);
}
- fibheap_delete (heap);
+ delete heap;
if (dump_file)
{
@@ -470,14 +472,14 @@ rotate_loop (edge back_edge, struct trace *trace, int trace_n)
static void
find_traces_1_round (int branch_th, int exec_th, gcov_type count_th,
struct trace *traces, int *n_traces, int round,
- fibheap_t *heap, int number_of_rounds)
+ bb_heap_t **heap, int number_of_rounds)
{
/* Heap for discarded basic blocks which are possible starting points for
the next round. */
- fibheap_t new_heap = fibheap_new ();
+ bb_heap_t *new_heap = new bb_heap_t (LONG_MIN);
bool for_size = optimize_function_for_size_p (cfun);
- while (!fibheap_empty (*heap))
+ while (!(*heap)->empty ())
{
basic_block bb;
struct trace *trace;
@@ -485,7 +487,7 @@ find_traces_1_round (int branch_th, int exec_th, gcov_type count_th,
fibheapkey_t key;
edge_iterator ei;
- bb = (basic_block) fibheap_extract_min (*heap);
+ bb = (*heap)->extract_min ();
bbd[bb->index].heap = NULL;
bbd[bb->index].node = NULL;
@@ -503,7 +505,7 @@ find_traces_1_round (int branch_th, int exec_th, gcov_type count_th,
{
int key = bb_to_key (bb);
bbd[bb->index].heap = new_heap;
- bbd[bb->index].node = fibheap_insert (new_heap, key, bb);
+ bbd[bb->index].node = new_heap->insert (key, bb);
if (dump_file)
fprintf (dump_file,
@@ -633,23 +635,23 @@ find_traces_1_round (int branch_th, int exec_th, gcov_type count_th,
if (bbd[e->dest->index].heap)
{
/* E->DEST is already in some heap. */
- if (key != bbd[e->dest->index].node->key)
+ if (key != bbd[e->dest->index].node->get_key ())
{
if (dump_file)
{
fprintf (dump_file,
"Changing key for bb %d from %ld to %ld.\n",
e->dest->index,
- (long) bbd[e->dest->index].node->key,
+ (long) bbd[e->dest->index].node->get_key (),
key);
}
- fibheap_replace_key (bbd[e->dest->index].heap,
- bbd[e->dest->index].node, key);
+ bbd[e->dest->index].heap->replace_key
+ (bbd[e->dest->index].node, key);
}
}
else
{
- fibheap_t which_heap = *heap;
+ bb_heap_t *which_heap = *heap;
prob = e->probability;
freq = EDGE_FREQUENCY (e);
@@ -671,8 +673,7 @@ find_traces_1_round (int branch_th, int exec_th, gcov_type count_th,
}
bbd[e->dest->index].heap = which_heap;
- bbd[e->dest->index].node = fibheap_insert (which_heap,
- key, e->dest);
+ bbd[e->dest->index].node = which_heap->insert (key, e->dest);
if (dump_file)
{
@@ -803,24 +804,23 @@ find_traces_1_round (int branch_th, int exec_th, gcov_type count_th,
if (bbd[e->dest->index].heap)
{
key = bb_to_key (e->dest);
- if (key != bbd[e->dest->index].node->key)
+ if (key != bbd[e->dest->index].node->get_key ())
{
if (dump_file)
{
fprintf (dump_file,
"Changing key for bb %d from %ld to %ld.\n",
e->dest->index,
- (long) bbd[e->dest->index].node->key, key);
+ (long) bbd[e->dest->index].node->get_key (), key);
}
- fibheap_replace_key (bbd[e->dest->index].heap,
- bbd[e->dest->index].node,
- key);
+ bbd[e->dest->index].heap->replace_key
+ (bbd[e->dest->index].node, key);
}
}
}
}
- fibheap_delete (*heap);
+ delete (*heap);
/* "Return" the new heap. */
*heap = new_heap;
--
2.1.2