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.
In meantime I've bootstrapped/regtested i686, but noticed that I do debug
output even when file is closed.

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 16:14:17
*************** 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,671 ----
        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;
  	    }
! 	  if (rtl_dump_file)
! 	    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 ++;
      }
  }
  
--- 700,707 ----
*************** estimate_bb_frequencies (loops)
*** 801,806 ****
--- 781,787 ----
    int i;
    double freq_max = 0;
  
+   mark_dfs_back_edges ();
    if (flag_branch_probabilities)
      {
        counts_to_freqs ();