[PATCH][RFC] Fix PR56113 more

[Richard Biener <rguenther at suse dot de>]

This reduces compile-time of the testcase in PR56113 (with n = 40000)
from 575s to 353s.  It does so by reducing the quadratic algorithm
to impose an order on visiting dominator sons during a domwalk.

Steven raises the issue that there exist domwalk users that modify
the CFG during the walk and thus the new scheme does not work
(at least optimally, as the current quadratic scheme does).  As
we are using a fixed-size sbitmap to track visited blocks existing
domwalks cannot add new blocks to the CFG so the worst thing that
can happen is that the order of dominator sons is no longer
optimal (I suppose with the "right" CFG manipulations even the
domwalk itself does not work - so I'd be hesitant to try to support
such domwalk users) - back to the state before any ordering
was imposed on the dom children visits (see rev 159100).

Bootstrapped and tested on x86_64-unknown-linux-gnu, ok for trunk?
(it's a regression from 4.5)

Thanks,
Richard.

2013-02-01  Richard Biener  <rguenther@suse.de>

	PR middle-end/56113
	* domwalk.c (bb_postorder): New global static.
	(cmp_bb_postorder): New function.
	(walk_dominator_tree): Replace scheme imposing an order for
	visiting dominator sons by one sorting them at the time they
	are pushed on the stack.

Index: gcc/domwalk.c
===================================================================
*** gcc/domwalk.c	(revision 195615)
--- gcc/domwalk.c	(working copy)
*************** along with GCC; see the file COPYING3.
*** 128,133 ****
--- 128,148 ----
      which is currently an abstraction over walking tree statements.  Thus
      the dominator walker is currently only useful for trees.  */
  
+ static int *bb_postorder;
+ 
+ static int
+ cmp_bb_postorder (const void *a, const void *b)
+ {
+   basic_block bb1 = *(basic_block *)const_cast<void *>(a);
+   basic_block bb2 = *(basic_block *)const_cast<void *>(b);
+   if (bb1->index == bb2->index)
+     return 0;
+   /* Place higher completion number first (pop off lower number first).  */
+   if (bb_postorder[bb1->index] > bb_postorder[bb2->index])
+     return -1;
+   return 1;
+ }
+ 
  /* Recursively walk the dominator tree.
  
     WALK_DATA contains a set of callbacks to perform pass-specific
*************** walk_dominator_tree (struct dom_walk_dat
*** 143,151 ****
    basic_block dest;
    basic_block *worklist = XNEWVEC (basic_block, n_basic_blocks * 2);
    int sp = 0;
!   sbitmap visited = sbitmap_alloc (last_basic_block + 1);
!   bitmap_clear (visited);
!   bitmap_set_bit (visited, ENTRY_BLOCK_PTR->index);
  
    while (true)
      {
--- 158,174 ----
    basic_block dest;
    basic_block *worklist = XNEWVEC (basic_block, n_basic_blocks * 2);
    int sp = 0;
!   int *postorder, postorder_num;
! 
!   if (walk_data->dom_direction == CDI_DOMINATORS)
!     {
!       postorder = XNEWVEC (int, n_basic_blocks);
!       postorder_num = inverted_post_order_compute (postorder);
!       bb_postorder = XNEWVEC (int, last_basic_block);
!       for (int i = 0; i < postorder_num; ++i)
! 	bb_postorder[postorder[i]] = i;
!       free (postorder);
!     }
  
    while (true)
      {
*************** walk_dominator_tree (struct dom_walk_dat
*** 186,201 ****
  	  if (walk_data->before_dom_children)
  	    (*walk_data->before_dom_children) (walk_data, bb);
  
- 	  bitmap_set_bit (visited, bb->index);
- 
  	  /* Mark the current BB to be popped out of the recursion stack
  	     once children are processed.  */
  	  worklist[sp++] = bb;
  	  worklist[sp++] = NULL;
  
  	  for (dest = first_dom_son (walk_data->dom_direction, bb);
  	       dest; dest = next_dom_son (walk_data->dom_direction, dest))
  	    worklist[sp++] = dest;
  	}
        /* NULL is used to mark pop operations in the recursion stack.  */
        while (sp > 0 && !worklist[sp - 1])
--- 209,233 ----
  	  if (walk_data->before_dom_children)
  	    (*walk_data->before_dom_children) (walk_data, bb);
  
  	  /* Mark the current BB to be popped out of the recursion stack
  	     once children are processed.  */
  	  worklist[sp++] = bb;
  	  worklist[sp++] = NULL;
  
+ 	  int saved_sp = sp;
  	  for (dest = first_dom_son (walk_data->dom_direction, bb);
  	       dest; dest = next_dom_son (walk_data->dom_direction, dest))
  	    worklist[sp++] = dest;
+ 	  if (walk_data->dom_direction == CDI_DOMINATORS)
+ 	    switch (sp - saved_sp)
+ 	      {
+ 	      case 0:
+ 	      case 1:
+ 		break;
+ 	      default:
+ 		qsort (&worklist[saved_sp], sp - saved_sp,
+ 		       sizeof (basic_block), cmp_bb_postorder);
+ 	      }
  	}
        /* NULL is used to mark pop operations in the recursion stack.  */
        while (sp > 0 && !worklist[sp - 1])
*************** walk_dominator_tree (struct dom_walk_dat
*** 217,260 ****
  	    }
  	}
        if (sp)
! 	{
! 	  int spp;
! 	  spp = sp - 1;
! 	  if (walk_data->dom_direction == CDI_DOMINATORS)
! 	    /* Find the dominator son that has all its predecessors
! 	       visited and continue with that.  */
! 	    while (1)
! 	      {
! 		edge_iterator ei;
! 		edge e;
! 		bool found = true;
! 		bb = worklist[spp];
! 		FOR_EACH_EDGE (e, ei, bb->preds)
! 		  {
! 		    if (!dominated_by_p (CDI_DOMINATORS, e->src, e->dest)
! 			&& !bitmap_bit_p (visited, e->src->index))
! 		      {
! 			found = false;
! 			break;
! 		      }
! 		  }
! 		if (found)
! 		  break;
! 		/* If we didn't find a dom child with all visited
! 		   predecessors just use the candidate we were checking.
! 		   This happens for candidates in irreducible loops.  */
! 		if (!worklist[spp - 1])
! 		  break;
! 		--spp;
! 	      }
! 	  bb = worklist[spp];
! 	  worklist[spp] = worklist[--sp];
! 	}
        else
  	break;
      }
    free (worklist);
-   sbitmap_free (visited);
  }
  
  void
--- 249,264 ----
  	    }
  	}
        if (sp)
! 	bb = worklist[--sp];
        else
  	break;
      }
+   if (walk_data->dom_direction == CDI_DOMINATORS)
+     {
+       free (bb_postorder);
+       bb_postorder = NULL;
+     }
    free (worklist);
  }
  
  void