Re: Timing information for CFG manipulations

[Jan Hubicka <jh@suse.cz>]

> On Tue, Oct 16, 2001 at 05:01:37PM +0200, Jan Hubicka wrote:
> > 	* cfgrtl.c (commite_one_edge_insertion): Create an bitmap to pass
> > 	to find_sub_basic_blocks.
> 
> I don't especially like the feature that commite_one_edge_insertion
> has to do all sorts of extra work to update one block.  Perhaps you
> should create a find_many_sub_basic_blocks that takes the sbitmap,
> but find_sub_basic_blocks continues to update one block.
> 
Done.

Thu Oct 18 01:47:20 CEST 2001  Jan Hubicka  <jh@suse.cz>
	* basic-block.h (find_sub_basic_blocks): Use sbitmap parameter.
	* cfgbuild.c (find_bb_boundaries, compute_outgoing_frequencies):
	Break out from ...
	(find_sub_basic_blocks): ... here;
	(find_many_sub_basic_blocks): New.
	* recog.c (split_all_insns): Update find_sub_basic_blocks call.

*** cfgbuild.c.b	Thu Oct 18 01:34:54 2001
--- cfgbuild.c	Thu Oct 18 01:46:25 2001
*************** static void make_edges			PARAMS ((rtx, i
*** 55,60 ****
--- 55,62 ----
  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));
+ static void compute_outgoing_frequencies 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)
      {
--- 248,255 ----
      }
  
    /* 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;
--- 666,692 ----
    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)
--- 706,712 ----
  	    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)
--- 737,743 ----
  	    {
  	      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;
--- 776,862 ----
       followed by cleanup at fallthru edge, so the outgoing edges may
       be dead.  */
    purge_dead_edges (bb);
+ }
+ 
+ /*  Assume that frequency of basic block B is known.  Compute frequencies
+     and probabilities of outgoing edges.  */
+ 
+ static void
+ compute_outgoing_frequencies (b)
+      basic_block b;
+ {
+   edge e, f;
+   if (b->succ && b->succ->succ_next && !b->succ->succ_next->succ_next)
+     {
+       rtx note = find_reg_note (b->end, REG_BR_PROB, NULL);
+       int probability;
+ 
+       if (!note)
+ 	return;
+       probability = INTVAL (XEXP (find_reg_note (b->end,
+ 						 REG_BR_PROB, NULL), 0));
+       e = BRANCH_EDGE (b);
+       e->probability = probability;
+       e->count = ((b->count * probability + REG_BR_PROB_BASE / 2)
+ 		  / REG_BR_PROB_BASE);
+       f = FALLTHRU_EDGE (b);
+       f->probability = REG_BR_PROB_BASE - probability;
+       f->count = b->count - e->count;
+     }
+   if (b->succ && !b->succ->succ_next)
+     {
+       e = b->succ;
+       e->probability = REG_BR_PROB_BASE;
+       e->count = b->count;
+     }
+ }
+ 
+ /* Assume that someone emitted code with control flow instructions to the
+    basic block.  Update the data structure.  */
+ 
+ void
+ find_many_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;
        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)
*** 785,813 ****
  	      b->frequency += EDGE_FREQUENCY (e);
  	    }
  	}
!       if (b->succ && b->succ->succ_next && !b->succ->succ_next->succ_next)
! 	{
! 	  rtx note = find_reg_note (b->end, REG_BR_PROB, NULL);
! 	  int probability;
  
! 	  if (!note)
! 	    continue;
! 	  probability = INTVAL (XEXP (find_reg_note (b->end,
! 						     REG_BR_PROB,
! 						     NULL), 0));
! 	  e = BRANCH_EDGE (b);
! 	  e->probability = probability;
! 	  e->count = ((b->count * probability + REG_BR_PROB_BASE / 2)
! 		      / REG_BR_PROB_BASE);
! 	  f = FALLTHRU_EDGE (b);
! 	  f->probability = REG_BR_PROB_BASE - probability;
! 	  f->count = b->count - e->count;
! 	}
!       if (b->succ && !b->succ->succ_next)
  	{
! 	  e = b->succ;
! 	  e->probability = REG_BR_PROB_BASE;
! 	  e->count = b->count;
  	}
      }
  }
--- 866,913 ----
  	      b->frequency += EDGE_FREQUENCY (e);
  	    }
  	}
!       compute_outgoing_frequencies (b);
!     }
!   for (i = 0; i < n_basic_blocks; i++)
!     SET_STATE (BASIC_BLOCK (i), 0);
! }
  
! /* Like above but for single basic block only.  */
! 
! void
! find_sub_basic_blocks (bb)
!     basic_block bb;
! {
!   int i;
!   int min, max;
!   basic_block next = (bb->index == n_basic_blocks - 1
! 		      ? NULL : BASIC_BLOCK (bb->index + 1));
! 
!   min = bb->index;
!   find_bb_boundaries (bb);
!   max = (next ? next->index : n_basic_blocks) - 1;
! 
!   /* 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;
!       basic_block b = BASIC_BLOCK (i);
! 
!       if (i != min)
  	{
! 	  b->count = 0;
! 	  b->frequency = 0;
! 	  for (e = b->pred; e; e=e->pred_next)
! 	    {
! 	      b->count += e->count;
! 	      b->frequency += EDGE_FREQUENCY (e);
! 	    }
  	}
+       compute_outgoing_frequencies (b);
      }
  }
*** basic-block.h.b	Thu Oct 18 01:35:12 2001
--- basic-block.h	Thu Oct 18 01:35:24 2001
*************** extern bool forwarder_block_p		PARAMS ((
*** 642,647 ****
--- 642,648 ----
  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 void find_many_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 *));
*** recog.c.b	Thu Oct 18 01:34:59 2001
--- recog.c	Thu Oct 18 01:35:04 2001
*************** 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_many_sub_basic_blocks (blocks);
      }
  
    if (changed && upd_life)