[patch] Speed up dominance frontier computation in update_ssa

[Zdenek Dvorak <rakdver at atrey dot karlin dot mff dot cuni dot cz>]

Hello,

currently, we compute dominance frontiers for all blocks in CFG in
update_ssa.  However, update_ssa determines the set of interesting
blocks S, and it is sufficient to compute the dominance frontiers
in the part of the cfg necessary to obtain iterated dominance frontiers
of S.  The basic observation is that if block A belongs to the iterated
dominance frontier of block B, then the immediate dominator of A
dominates B.  Therefore, it suffices to take into account the blocks
whose immediate dominator dominates one of the block in S.  This
reduces the time spent in dominance frontier computation in the testcase
for PR26830 about 4 times (decreasing the total compile time by about 5%).

Bootstrapped & regtested on ia64 and i686.

Zdenek

	* tree-into-ssa.c (find_idf): Handle NULL bitmaps in
	dfs.
	(rewrite_into_ssa): Do not allocate the bitmaps in dfs.
	Pass NULL to compute_dominance_frontiers.
	(update_ssa): Do not allocate the bitmaps in dfs.
	Pass blocks to compute_dominance_frontiers.
	* cfganal.c (add_to_dominance_frontiers): New function.
	(compute_dominance_frontiers_1, compute_dominance_frontiers):
	Allow restricting the computation to interesting blocks.
	* basic-block.h (compute_dominance_frontiers): Declaration
	changed.

Index: tree-into-ssa.c
===================================================================
*** tree-into-ssa.c	(revision 112911)
--- tree-into-ssa.c	(working copy)
*************** find_idf (bitmap def_blocks, bitmap *dfs
*** 697,703 ****
    bitmap_iterator bi;
    unsigned bb_index;
    VEC(int,heap) *work_stack;
!   bitmap phi_insertion_points;
  
    work_stack = VEC_alloc (int, heap, n_basic_blocks);
    phi_insertion_points = BITMAP_ALLOC (NULL);
--- 697,703 ----
    bitmap_iterator bi;
    unsigned bb_index;
    VEC(int,heap) *work_stack;
!   bitmap phi_insertion_points, bmp;
  
    work_stack = VEC_alloc (int, heap, n_basic_blocks);
    phi_insertion_points = BITMAP_ALLOC (NULL);
*************** find_idf (bitmap def_blocks, bitmap *dfs
*** 726,732 ****
  	 we may pull a non-existing block from the work stack.  */
        gcc_assert (bb_index < (unsigned) last_basic_block);
  
!       EXECUTE_IF_AND_COMPL_IN_BITMAP (dfs[bb_index], phi_insertion_points,
  	                              0, bb_index, bi)
  	{
  	  /* Use a safe push because if there is a definition of VAR
--- 726,736 ----
  	 we may pull a non-existing block from the work stack.  */
        gcc_assert (bb_index < (unsigned) last_basic_block);
  
!       bmp = dfs[bb_index];
!       if (!bmp)
! 	continue;
! 
!       EXECUTE_IF_AND_COMPL_IN_BITMAP (bmp, phi_insertion_points,
  	                              0, bb_index, bi)
  	{
  	  /* Use a safe push because if there is a definition of VAR
*************** rewrite_into_ssa (void)
*** 1745,1757 ****
    sbitmap_zero (interesting_blocks);
  
    /* Initialize dominance frontier.  */
!   dfs = (bitmap *) xmalloc (last_basic_block * sizeof (bitmap));
!   FOR_EACH_BB (bb)
!     dfs[bb->index] = BITMAP_ALLOC (NULL);
  
    /* 1- Compute dominance frontiers.  */
    calculate_dominance_info (CDI_DOMINATORS);
!   compute_dominance_frontiers (dfs);
  
    /* 2- Find and mark definition sites.  */
    mark_def_site_blocks (interesting_blocks);
--- 1749,1759 ----
    sbitmap_zero (interesting_blocks);
  
    /* Initialize dominance frontier.  */
!   dfs = XCNEWVEC (bitmap, last_basic_block);
  
    /* 1- Compute dominance frontiers.  */
    calculate_dominance_info (CDI_DOMINATORS);
!   compute_dominance_frontiers (dfs, NULL);
  
    /* 2- Find and mark definition sites.  */
    mark_def_site_blocks (interesting_blocks);
*************** update_ssa (unsigned update_flags)
*** 2744,2753 ****
  
        /* If the caller requested PHI nodes to be added, compute
  	 dominance frontiers.  */
!       dfs = XNEWVEC (bitmap, last_basic_block);
!       FOR_EACH_BB (bb)
! 	dfs[bb->index] = BITMAP_ALLOC (NULL);
!       compute_dominance_frontiers (dfs);
  
        if (sbitmap_first_set_bit (old_ssa_names) >= 0)
  	{
--- 2746,2753 ----
  
        /* If the caller requested PHI nodes to be added, compute
  	 dominance frontiers.  */
!       dfs = XCNEWVEC (bitmap, last_basic_block);
!       compute_dominance_frontiers (dfs, blocks);
  
        if (sbitmap_first_set_bit (old_ssa_names) >= 0)
  	{
Index: cfganal.c
===================================================================
*** cfganal.c	(revision 112911)
--- cfganal.c	(working copy)
*************** dfs_enumerate_from (basic_block bb, int 
*** 1010,1015 ****
--- 1010,1053 ----
  #undef VISITED_P
  }
  
+ /* Adds basic block BB to dominance frontiers (stored in FRONTIERS).  */
+ 
+ static void
+ add_to_dominance_frontiers (bitmap *frontiers, basic_block bb)
+ {
+   edge p;
+   edge_iterator ei;
+   unsigned idx = bb->index;
+   
+   /* If the block has only one predecessor, it cannot belong to any dominance
+      frontiers.  */
+   if (EDGE_COUNT (bb->preds) < 2)
+     return;
+ 
+   /* Otherwise, it belongs to the dominance frontiers of all blocks that
+      dominate one of its predecessors, up till the immediate dominator
+      of BB.  */
+   FOR_EACH_EDGE (p, ei, bb->preds)
+     {
+       basic_block runner = p->src;
+       basic_block domsb;
+       if (runner == ENTRY_BLOCK_PTR)
+ 	continue;
+ 	      
+       domsb = get_immediate_dominator (CDI_DOMINATORS, bb);
+       while (runner != domsb)
+ 	{
+ 	  bitmap bmp = frontiers[runner->index];
+ 	  if (!bmp)
+ 	    {
+ 	      bmp = BITMAP_ALLOC (NULL);
+ 	      frontiers[runner->index] = bmp;
+ 	    }
+ 	  bitmap_set_bit (bmp, idx);
+ 	  runner = get_immediate_dominator (CDI_DOMINATORS, runner);
+ 	}
+     }
+ }
  
  /* Compute dominance frontiers, ala Harvey, Ferrante, et al.
     
*************** dfs_enumerate_from (basic_block bb, int 
*** 1031,1076 ****
  
     The number of nodes touched by this algorithm is equal to the size 
     of the dominance frontiers, no more, no less.
! */
  
  
  static void
! compute_dominance_frontiers_1 (bitmap *frontiers)
  {
!   edge p;
!   edge_iterator ei;
!   basic_block b;
!   FOR_EACH_BB (b)
      {
!       if (EDGE_COUNT (b->preds) >= 2)
  	{
! 	  FOR_EACH_EDGE (p, ei, b->preds)
  	    {
! 	      basic_block runner = p->src;
! 	      basic_block domsb;
! 	      if (runner == ENTRY_BLOCK_PTR)
! 		continue;
! 	      
! 	      domsb = get_immediate_dominator (CDI_DOMINATORS, b);
! 	      while (runner != domsb)
! 		{
! 		  bitmap_set_bit (frontiers[runner->index], 
! 				  b->index);
! 		  runner = get_immediate_dominator (CDI_DOMINATORS,
! 						    runner);
! 		}
  	    }
  	}
      }
  }	      
    
  
  void
! compute_dominance_frontiers (bitmap *frontiers)
  {
    timevar_push (TV_DOM_FRONTIERS);
  
!   compute_dominance_frontiers_1 (frontiers);
  
    timevar_pop (TV_DOM_FRONTIERS);
  }
--- 1069,1133 ----
  
     The number of nodes touched by this algorithm is equal to the size 
     of the dominance frontiers, no more, no less.
! 
!    If BLOCKS is not NULL, only the blocks whose immediate dominator dominates
!    a basic block in BLOCKS are put to the frontiers; this is sufficient to
!    ensure that the dominance frontier information is correct for BLOCKS and
!    all blocks in the iterated dominance frontier of BLOCKS.  */
  
  
  static void
! compute_dominance_frontiers_1 (bitmap *frontiers, bitmap blocks)
  {
!   basic_block bb;
! 
!   if (blocks)
      {
!       bitmap dominators_of_blocks = BITMAP_ALLOC (NULL);
!       bitmap_iterator bi;
!       unsigned i;
!       basic_block son;
! 
!       /* Determine all blocks that dominate one of BLOCKS, and traverse
! 	 their dominance sons.  */
!       bitmap_set_bit (dominators_of_blocks, ENTRY_BLOCK_PTR->index);
!       for (son = first_dom_son (CDI_DOMINATORS, ENTRY_BLOCK_PTR);
! 	   son; son = next_dom_son (CDI_DOMINATORS, son))
! 	add_to_dominance_frontiers (frontiers, son);
! 	
!       EXECUTE_IF_SET_IN_BITMAP (blocks, 0, i, bi)
  	{
! 	  bb = BASIC_BLOCK (i);
! 
! 	  while (!bitmap_bit_p (dominators_of_blocks, bb->index))
  	    {
! 	      for (son = first_dom_son (CDI_DOMINATORS, bb);
! 		   son; son = next_dom_son (CDI_DOMINATORS, son))
! 		add_to_dominance_frontiers (frontiers, son);
! 
! 	      bitmap_set_bit (dominators_of_blocks, bb->index);
! 	      bb = get_immediate_dominator (CDI_DOMINATORS, bb);
  	    }
  	}
+ 
+       BITMAP_FREE (dominators_of_blocks);
+     }
+   else
+     {
+       FOR_EACH_BB (bb)
+ 	{
+ 	  add_to_dominance_frontiers (frontiers, bb);
+ 	}
      }
  }	      
    
  
  void
! compute_dominance_frontiers (bitmap *frontiers, bitmap blocks)
  {
    timevar_push (TV_DOM_FRONTIERS);
  
!   compute_dominance_frontiers_1 (frontiers, blocks);
  
    timevar_pop (TV_DOM_FRONTIERS);
  }
Index: basic-block.h
===================================================================
*** basic-block.h	(revision 112911)
--- basic-block.h	(working copy)
*************** extern int pre_and_rev_post_order_comput
*** 509,515 ****
  extern int dfs_enumerate_from (basic_block, int,
  			       bool (*)(basic_block, void *),
  			       basic_block *, int, void *);
! extern void compute_dominance_frontiers (bitmap *);
  extern void dump_bb_info (basic_block, bool, bool, int, const char *, FILE *);
  extern void dump_edge_info (FILE *, edge, int);
  extern void brief_dump_cfg (FILE *);
--- 509,515 ----
  extern int dfs_enumerate_from (basic_block, int,
  			       bool (*)(basic_block, void *),
  			       basic_block *, int, void *);
! extern void compute_dominance_frontiers (bitmap *, bitmap);
  extern void dump_bb_info (basic_block, bool, bool, int, const char *, FILE *);
  extern void dump_edge_info (FILE *, edge, int);
  extern void brief_dump_cfg (FILE *);