[PATCH] Fix PR69609, BB reorder slowness

[Richard Biener <rguenther at suse dot de>]

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  <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.

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;
      }