This fixes BB reorder speed for the testcase (lots of computed gotos
in a very large function). BB reorder time goes down from
reorder blocks : 260.53 (80%) usr 0.37 (27%) sys 261.80 (80%)
wall 432597 kB (58%) ggc
to
reorder blocks : 1.03 ( 2%) usr 0.08 ( 7%) sys 1.08 ( 2%)
wall 432597 kB (58%) ggc
with this patch which effectively removes a quadraticness in
the number of incoming/outgoing edges.
Bootstrapped on x86_64-unknown-linux-gnu, testing in progress. I verified
code generation is not affected on a set of cc1files.
Richard.
2016-02-17 Richard Biener <rguent...@suse.de>
PR rtl-optimization/69609
* bb-reorder.c (struct bbro_basic_block_data): Add priority member.
(find_traces_1_round): When ending a trace update cached priority
of successors.
(bb_to_key): Use cached priority when available.
(copy_bb): Initialize cached priority.
(reorder_basic_blocks_software_trace_cache): Likewise.
Index: gcc/bb-reorder.c
===================================================================
*** gcc/bb-reorder.c (revision 233452)
--- gcc/bb-reorder.c (working copy)
*************** struct bbro_basic_block_data
*** 157,162 ****
--- 157,166 ----
/* Which trace was this bb visited in? */
int visited;
+ /* Cached maximum frequency of interesting incoming edges.
+ Minus one means not yet computed. */
+ int priority;
+
/* Which heap is BB in (if any)? */
bb_heap_t *heap;
*************** find_traces_1_round (int branch_th, int
*** 775,781 ****
while (best_edge);
trace->last = bb;
bbd[trace->first->index].start_of_trace = *n_traces - 1;
! bbd[trace->last->index].end_of_trace = *n_traces - 1;
/* The trace is terminated so we have to recount the keys in heap
(some block can have a lower key because now one of its predecessors
--- 779,793 ----
while (best_edge);
trace->last = bb;
bbd[trace->first->index].start_of_trace = *n_traces - 1;
! if (bbd[trace->last->index].end_of_trace != *n_traces - 1)
! {
! bbd[trace->last->index].end_of_trace = *n_traces - 1;
! /* Update the cached maximum frequency for interesting predecessor
! edges for successors of the new trace end. */
! FOR_EACH_EDGE (e, ei, trace->last->succs)
! if (EDGE_FREQUENCY (e) > bbd[e->dest->index].priority)
! bbd[e->dest->index].priority = EDGE_FREQUENCY (e);
! }
/* The trace is terminated so we have to recount the keys in heap
(some block can have a lower key because now one of its predecessors
*************** copy_bb (basic_block old_bb, edge e, bas
*** 845,850 ****
--- 857,863 ----
bbd[i].end_of_trace = -1;
bbd[i].in_trace = -1;
bbd[i].visited = 0;
+ bbd[i].priority = -1;
bbd[i].heap = NULL;
bbd[i].node = NULL;
}
*************** bb_to_key (basic_block bb)
*** 875,881 ****
{
edge e;
edge_iterator ei;
- int priority = 0;
/* Use index as key to align with its original order. */
if (optimize_function_for_size_p (cfun))
--- 888,893 ----
*************** bb_to_key (basic_block bb)
*** 889,905 ****
/* Prefer blocks whose predecessor is an end of some trace
or whose predecessor edge is EDGE_DFS_BACK. */
! FOR_EACH_EDGE (e, ei, bb->preds)
{
! if ((e->src != ENTRY_BLOCK_PTR_FOR_FN (cfun)
! && bbd[e->src->index].end_of_trace >= 0)
! || (e->flags & EDGE_DFS_BACK))
{
! int edge_freq = EDGE_FREQUENCY (e);
! if (edge_freq > priority)
! priority = edge_freq;
}
}
if (priority)
--- 901,923 ----
/* Prefer blocks whose predecessor is an end of some trace
or whose predecessor edge is EDGE_DFS_BACK. */
! int priority = bbd[bb->index].priority;
! if (priority == -1)
{
! priority = 0;
! FOR_EACH_EDGE (e, ei, bb->preds)
{
! if ((e->src != ENTRY_BLOCK_PTR_FOR_FN (cfun)
! && bbd[e->src->index].end_of_trace >= 0)
! || (e->flags & EDGE_DFS_BACK))
! {
! int edge_freq = EDGE_FREQUENCY (e);
! if (edge_freq > priority)
! priority = edge_freq;
! }
}
+ bbd[bb->index].priority = priority;
}
if (priority)
*************** reorder_basic_blocks_software_trace_cach
*** 2253,2258 ****
--- 2271,2277 ----
bbd[i].end_of_trace = -1;
bbd[i].in_trace = -1;
bbd[i].visited = 0;
+ bbd[i].priority = -1;
bbd[i].heap = NULL;
bbd[i].node = NULL;
}
