Re: Timing information for CFG manipulations

[Jan Hubicka <jh@suse.cz>]

Hi,
this patch should track down the second problem:

>  flow 2                : 267.66 (34%) usr 251.44 (98%) sys 519.08 (49%) wall
>  32.36    602.16   253.66     9556    26.54    26.54  sbitmap_vector_alloc

It makes find_sub_basic_blocks to operate at bitmap of blocks, instead of just
one and thus it avoids multiple initializations of edge cache structure.

The possible problem is that I now need to benerate bitmap when calling from
recog.c.  I hope it won't cause perofrmance regression as the bitmap is
relativly small (compared to edge cache).  If it will, I can use bitmap,
instead of sbitmap, that will add some overhead at split_all_insns side.

I don't have time to finish bootstrap, but the patch appears to work.
OK assuming the bootstrapping/regtesting i386 passes fluently?

Honza

Tue Oct 16 16:56:33 CEST 2001  Jan Hubicka  <jh@suse.cz>
	* basic-block.h (find_sub_basic_blocks): Use sbitmap parameter.
	* cfgbuild.c (find_bb_boundaries): Break out from ...
	(find_sub_basic_blocks): ... here; reorganize to handle multiple
	basic blocks at once.
	* cfgrtl.c (commite_one_edge_insertion): Create an bitmap to pass
	to find_sub_basic_blocks.
	* recog.c (split_all_insns): Update find_sub_basic_blocks call.


Index: basic-block.h
===================================================================
RCS file: /cvs/gcc/egcs/gcc/basic-block.h,v
retrieving revision 1.123
diff -c -3 -p -r1.123 basic-block.h
*** basic-block.h	2001/10/11 12:43:38	1.123
--- basic-block.h	2001/10/16 14:54:27
*************** extern rtx block_label			PARAMS ((basic_
*** 639,645 ****
  extern bool forwarder_block_p		PARAMS ((basic_block));
  extern bool purge_all_dead_edges	PARAMS ((void));
  extern bool purge_dead_edges		PARAMS ((basic_block));
! extern void find_sub_basic_blocks	PARAMS ((basic_block));
  extern bool can_fallthru		PARAMS ((basic_block, basic_block));
  extern void flow_nodes_print		PARAMS ((const char *, const sbitmap,
  						 FILE *));
--- 639,645 ----
  extern bool forwarder_block_p		PARAMS ((basic_block));
  extern bool purge_all_dead_edges	PARAMS ((void));
  extern bool purge_dead_edges		PARAMS ((basic_block));
! extern void find_sub_basic_blocks	PARAMS ((sbitmap));
  extern bool can_fallthru		PARAMS ((basic_block, basic_block));
  extern void flow_nodes_print		PARAMS ((const char *, const sbitmap,
  						 FILE *));
Index: cfgbuild.c
===================================================================
RCS file: /cvs/gcc/egcs/gcc/cfgbuild.c,v
retrieving revision 1.7
diff -c -3 -p -r1.7 cfgbuild.c
*** cfgbuild.c	2001/10/11 03:15:24	1.7
--- cfgbuild.c	2001/10/16 14:54:28
*************** static void make_edges			PARAMS ((rtx, i
*** 55,60 ****
--- 55,61 ----
  static void make_label_edge		PARAMS ((sbitmap *, basic_block,
  						 rtx, int));
  static void make_eh_edge		PARAMS ((sbitmap *, basic_block, rtx));
+ static void find_bb_boundaries		PARAMS ((basic_block));
  
  /* Count the basic blocks of the function.  */
  
*************** make_edges (label_value_list, min, max, 
*** 246,252 ****
      }
  
    /* By nature of the way these get numbered, block 0 is always the entry.  */
!   cached_make_edge (edge_cache, ENTRY_BLOCK_PTR, BASIC_BLOCK (0), EDGE_FALLTHRU);
  
    for (i = min; i <= max; ++i)
      {
--- 247,254 ----
      }
  
    /* By nature of the way these get numbered, block 0 is always the entry.  */
!   if (min == 0)
!     cached_make_edge (edge_cache, ENTRY_BLOCK_PTR, BASIC_BLOCK (0), EDGE_FALLTHRU);
  
    for (i = min; i <= max; ++i)
      {
*************** find_basic_blocks (f, nregs, file)
*** 663,680 ****
    timevar_pop (TV_CFG);
  }
  \f
! /* Assume that someone emitted code with control flow instructions to the
!    basic block.  Update the data structure.  */
! void
! find_sub_basic_blocks (bb)
       basic_block bb;
  {
    rtx insn = bb->head;
    rtx end = bb->end;
    rtx flow_transfer_insn = NULL_RTX;
    edge fallthru = NULL;
-   basic_block first_bb = bb;
-   int i;
  
    if (insn == bb->end)
      return;
--- 665,691 ----
    timevar_pop (TV_CFG);
  }
  \f
! /* State of basic block as seen by find_sub_basic_blocks.  */
! enum state
!   {
!     BLOCK_NEW = 0,
!     BLOCK_ORIGINAL,
!     BLOCK_TO_SPLIT
!   };
! #define STATE(bb) (enum state)(size_t)(bb)->aux
! #define SET_STATE(bb, state) (bb)->aux = (void *)(state)
! 
! /* Scan basic block BB for possible BB boundaries inside the block
!    and create new basic blocks in the progress.  */
! 
! static void
! find_bb_boundaries (bb)
       basic_block bb;
  {
    rtx insn = bb->head;
    rtx end = bb->end;
    rtx flow_transfer_insn = NULL_RTX;
    edge fallthru = NULL;
  
    if (insn == bb->end)
      return;
*************** find_sub_basic_blocks (bb)
*** 694,700 ****
  	    abort ();
  	  break;
  
! 	/* On code label, split current basic block.  */
  	case CODE_LABEL:
  	  fallthru = split_block (bb, PREV_INSN (insn));
  	  if (flow_transfer_insn)
--- 705,711 ----
  	    abort ();
  	  break;
  
! 	  /* On code label, split current basic block.  */
  	case CODE_LABEL:
  	  fallthru = split_block (bb, PREV_INSN (insn));
  	  if (flow_transfer_insn)
*************** find_sub_basic_blocks (bb)
*** 725,731 ****
  	    {
  	      if (GET_CODE (PATTERN (insn)) == ADDR_VEC
  		  || GET_CODE (PATTERN (insn)) == ADDR_DIFF_VEC)
! 		abort();
  	      flow_transfer_insn = insn;
  	    }
  	  else if (code == CALL_INSN)
--- 736,742 ----
  	    {
  	      if (GET_CODE (PATTERN (insn)) == ADDR_VEC
  		  || GET_CODE (PATTERN (insn)) == ADDR_DIFF_VEC)
! 		abort ();
  	      flow_transfer_insn = insn;
  	    }
  	  else if (code == CALL_INSN)
*************** find_sub_basic_blocks (bb)
*** 764,781 ****
       followed by cleanup at fallthru edge, so the outgoing edges may
       be dead.  */
    purge_dead_edges (bb);
  
    /* Now re-scan and wire in all edges.  This expect simple (conditional)
       jumps at the end of each new basic blocks.  */
!   make_edges (NULL, first_bb->index, bb->index, 1);
  
    /* Update branch probabilities.  Expect only (un)conditional jumps
       to be created with only the forward edges.  */
!   for (i = first_bb->index; i <= bb->index; i++)
      {
        edge e,f;
        basic_block b = BASIC_BLOCK (i);
!       if (b != first_bb)
  	{
  	  b->count = 0;
  	  b->frequency = 0;
--- 775,828 ----
       followed by cleanup at fallthru edge, so the outgoing edges may
       be dead.  */
    purge_dead_edges (bb);
+ }
+ 
+ /* Assume that someone emitted code with control flow instructions to the
+    basic block.  Update the data structure.  */
  
+ void
+ find_sub_basic_blocks (blocks)
+      sbitmap blocks;
+ {
+   int i;
+   int min, max;
+ 
+   for (i = 0; i < n_basic_blocks; i++)
+     {
+       SET_STATE (BASIC_BLOCK (i),
+ 		 TEST_BIT (blocks, i)
+ 		 ? BLOCK_TO_SPLIT : BLOCK_ORIGINAL);
+     }
+ 
+   for (i = 0; i < n_basic_blocks; i++)
+     {
+       basic_block bb = BASIC_BLOCK (i);
+       if (STATE (bb) == BLOCK_TO_SPLIT)
+ 	find_bb_boundaries (bb);
+     }
+ 
+   for (i = 0; i < n_basic_blocks; i++)
+     if (STATE (BASIC_BLOCK (i)) != BLOCK_ORIGINAL)
+       break;
+   min = max = i;
+   for (; i < n_basic_blocks; i++)
+     if (STATE (BASIC_BLOCK (i)) != BLOCK_ORIGINAL)
+       max = i;
+ 
    /* Now re-scan and wire in all edges.  This expect simple (conditional)
       jumps at the end of each new basic blocks.  */
!   make_edges (NULL, min, max, 1);
  
    /* Update branch probabilities.  Expect only (un)conditional jumps
       to be created with only the forward edges.  */
!   for (i = min; i <= max; i++)
      {
        edge e,f;
        basic_block b = BASIC_BLOCK (i);
! 
!       if (STATE (b) == BLOCK_ORIGINAL)
! 	continue;
!       if (STATE (b) == BLOCK_NEW)
  	{
  	  b->count = 0;
  	  b->frequency = 0;
*************** find_sub_basic_blocks (bb)
*** 810,813 ****
--- 857,862 ----
  	  e->count = b->count;
  	}
      }
+   for (i = 0; i < n_basic_blocks; i++)
+     SET_STATE (BASIC_BLOCK (i), 0);
  }
Index: cfgrtl.c
===================================================================
RCS file: /cvs/gcc/egcs/gcc/cfgrtl.c,v
retrieving revision 1.4
diff -c -3 -p -r1.4 cfgrtl.c
*** cfgrtl.c	2001/10/11 03:15:24	1.4
--- cfgrtl.c	2001/10/16 14:54:28
*************** commit_one_edge_insertion (e)
*** 1221,1226 ****
--- 1221,1227 ----
  {
    rtx before = NULL_RTX, after = NULL_RTX, insns, tmp, last;
    basic_block bb;
+   sbitmap b;
  
    /* Pull the insns off the edge now since the edge might go away.  */
    insns = e->insns;
*************** commit_one_edge_insertion (e)
*** 1314,1320 ****
      }
    else if (GET_CODE (last) == JUMP_INSN)
      abort ();
!   find_sub_basic_blocks (bb);
  }
  
  /* Update the CFG for all queued instructions.  */
--- 1315,1325 ----
      }
    else if (GET_CODE (last) == JUMP_INSN)
      abort ();
! 
!   b = sbitmap_alloc (n_basic_blocks);
!   sbitmap_zero (b);
!   SET_BIT (b, bb->index);
!   find_sub_basic_blocks (b);
  }
  
  /* Update the CFG for all queued instructions.  */
Index: recog.c
===================================================================
RCS file: /cvs/gcc/egcs/gcc/recog.c,v
retrieving revision 1.128
diff -c -3 -p -r1.128 recog.c
*** recog.c	2001/10/16 04:19:26	1.128
--- recog.c	2001/10/16 14:54:31
*************** split_all_insns (upd_life)
*** 2778,2785 ****
  
    if (changed)
      {
!       for (i = 0; i < n_basic_blocks; i++)
! 	find_sub_basic_blocks (BASIC_BLOCK (i));
      }
  
    if (changed && upd_life)
--- 2778,2784 ----
  
    if (changed)
      {
!       find_sub_basic_blocks (blocks);
      }
  
    if (changed && upd_life)