re PR rtl-optimization/69609 (block reordering consumes an inordinate amount of time, REE consumes much memory)

2016-02-17  Richard Biener  <rguenther@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.

From-SVN: r233498

2 files changed, 38 insertions, 9 deletions

diff --git a/gcc/ChangeLog b/gcc/ChangeLog
index 6d2a4bd..4646617 100644
--- a/gcc/ChangeLog
+++ b/gcc/ChangeLog
@@ -1,3 +1,13 @@
+2016-02-17  Richard Biener  <rguenther@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.
+
 2016-02-17  Kyrylo Tkachov  <kyrylo.tkachov@arm.com>
 
 	PR target/69161
diff --git a/gcc/bb-reorder.c b/gcc/bb-reorder.c
index 8cbde89..5fb60bd 100644
--- a/gcc/bb-reorder.c
+++ b/gcc/bb-reorder.c
@@ -157,6 +157,10 @@ struct bbro_basic_block_data
   /* 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;
 
@@ -775,7 +779,15 @@ find_traces_1_round (int branch_th, int exec_th, gcov_type count_th,
       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;
+      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
@@ -845,6 +857,7 @@ copy_bb (basic_block old_bb, edge e, basic_block bb, int trace)
 	  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;
 	}
@@ -875,7 +888,6 @@ bb_to_key (basic_block bb)
 {
   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))
@@ -889,17 +901,23 @@ bb_to_key (basic_block bb)
 
   /* 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)
+  int priority = bbd[bb->index].priority;
+  if (priority == -1)
     {
-      if ((e->src != ENTRY_BLOCK_PTR_FOR_FN (cfun)
-	   && bbd[e->src->index].end_of_trace >= 0)
-	  || (e->flags & EDGE_DFS_BACK))
+      priority = 0;
+      FOR_EACH_EDGE (e, ei, bb->preds)
 	{
-	  int edge_freq = EDGE_FREQUENCY (e);
+	  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 (edge_freq > priority)
+		priority = edge_freq;
+	    }
 	}
+      bbd[bb->index].priority = priority;
     }
 
   if (priority)
@@ -2253,6 +2271,7 @@ reorder_basic_blocks_software_trace_cache (void)
       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;
     }