Re: propagate_freq enormous performance hit in 3.1

[Jan Hubicka <jh at suse dot cz>]

> Jan:
> 
> >From examining the sources, it seems that predict.c is your baby,
> and it seems to have a serious performance problem in propagate_freq
> for large flow graphs, see
> 
> http://gcc.gnu.org/ml/gcc-prs/2001-08/msg00184.html
> 
> Do you have any idea of what's going on here?
Yes - the irregular region detection is somewhat, uhm, slow.

I don't have setup here able to compile your testcase, but this patch should
solve it. Now, when we have mark_dfs_back_edges it is nice cleanup anyway

Still in extreme case of many nested loops the code may expose quadratic
behaviour, but I hope it is not main issue, as it is overall relativly fast.

In case it is still slow, we can limit loop nest the code is taking into
account.

Honza

Tue Aug 14 17:56:30 CEST 2001  Jan Hubicka  <jh@suse.cz>

	* predict.c (struct block_info_def): Remove nvisited.
	(propagate_freq): Use EDGE_DFS_BACK to detect irreducible regions.
	(estimate_bb_frequencies): Call mark_dfs_back_edges.

Index: predict.c
===================================================================
RCS file: /cvs/gcc/egcs/gcc/predict.c,v
retrieving revision 1.34
diff -c -3 -p -r1.34 predict.c
*** predict.c	2001/08/13 14:32:06	1.34
--- predict.c	2001/08/14 15:56:04
*************** typedef struct block_info_def
*** 608,617 ****
  
    /* True if block already converted.  */
    int visited:1;
- 
-   /* Number of block proceeded before adding basic block to the queue.  Used
-      to recognize irregular regions.  */
-   int nvisited;
  } *block_info;
  
  /* Similar information for edges.  */
--- 608,613 ----
*************** propagate_freq (head)
*** 638,644 ****
    basic_block last = bb;
    edge e;
    basic_block nextbb;
-   int nvisited = 0;
  
    BLOCK_INFO (head)->frequency = 1;
    for (; bb; bb = nextbb)
--- 634,639 ----
*************** propagate_freq (head)
*** 652,689 ****
        if (bb != head)
  	{
  	  for (e = bb->pred; e; e = e->pred_next)
! 	    if (!BLOCK_INFO (e->src)->visited && !EDGE_INFO (e)->back_edge)
  	      break;
  
! 	  /* We haven't proceeded all predecessors of edge e yet.
! 	     These may be waiting in the queue or we may hit an
! 	     irreducible region.
! 
! 	     To avoid infinite looping on irrecudible regions, count
! 	     the number of blocks proceeded at the time the basic
! 	     block has been queued.  In the case the number doesn't
! 	     change, we've hit an irreducible region and we can forget
! 	     the backward edge.	 This can increase the time complexity
! 	     by the number of irreducible blocks, but in the same way
! 	     the standard the loop does, so it should not result in a
! 	     noticeable slowdown.
! 
! 	     Alternatively we may distinguish backward and cross edges
! 	     in the DFS tree by the preprocessing pass and ignore the
! 	     existence of non-loop backward edges.  */
! 	  if (e && BLOCK_INFO (bb)->nvisited != nvisited)
  	    {
  	      if (!nextbb)
  		nextbb = e->dest;
  	      else
  		BLOCK_INFO (last)->next = e->dest;
- 	      BLOCK_INFO (last)->nvisited = nvisited;
  	      last = e->dest;
  	      continue;
  	    }
! 	  else if (e && rtl_dump_file)
! 	    fprintf (rtl_dump_file, "Irreducible region hit, ignoring edge to bb %i\n",
! 		     bb->index);
  
  	  for (e = bb->pred; e; e = e->pred_next)
  	    if (EDGE_INFO (e)->back_edge)
--- 647,670 ----
        if (bb != head)
  	{
  	  for (e = bb->pred; e; e = e->pred_next)
! 	    if (!BLOCK_INFO (e->src)->visited && !(e->flags & EDGE_DFS_BACK))
  	      break;
  
! 	  /* We haven't proceeded all predecessors of edge e yet.  */
! 	  if (e)
  	    {
  	      if (!nextbb)
  		nextbb = e->dest;
  	      else
  		BLOCK_INFO (last)->next = e->dest;
  	      last = e->dest;
  	      continue;
  	    }
! 	  for (e = bb->pred; e; e = e->pred_next)
! 	    if (!BLOCK_INFO (e->src)->visited && !EDGE_INFO (e)->back_edge)
! 	      fprintf (rtl_dump_file,
! 		       "Irreducible region hit, ignoring edge to %i->%i\n",
! 		       e->src->index, bb->index);
  
  	  for (e = bb->pred; e; e = e->pred_next)
  	    if (EDGE_INFO (e)->back_edge)
*************** propagate_freq (head)
*** 718,727 ****
  	      nextbb = e->dest;
  	    else
  	      BLOCK_INFO (last)->next = e->dest;
- 	    BLOCK_INFO (last)->nvisited = nvisited;
  	    last = e->dest;
  	  }
-       nvisited ++;
      }
  }
  
--- 699,706 ----
*************** estimate_bb_frequencies (loops)
*** 801,806 ****
--- 780,786 ----
    int i;
    double freq_max = 0;
  
+   mark_dfs_back_edges ();
    if (flag_branch_probabilities)
      {
        counts_to_freqs ();