tree profilng merge 3 - find_sub_basic_blocks fixes wrt computed gotos

tree profilng merge 3 - find_sub_basic_blocks fixes wrt computed gotos

[Jan Hubicka]

Hi,
this patch fix find_many_sub_basic_blocks so it update CFG correctly when new
computed goto is inserted.

Bootstrapped/regtested i686-pc-gnu-linux
without useable libjava testsuite (I hope to have this problem resolved before
possible approval of the patch and have chance to re-test it in meantime)
OK assuming that I manage to test libjava?

2004-05-25  Jan Hubicka  <jh@suse.cz>
	* cfgbuild.c (find_bb_boundaries):  Return list of computed goto
	destinations.
	(find_many_sub_basic_blocks):  Deal properly with computed
	goto detinations.
Index: cfgbuild.c
===================================================================
RCS file: /cvs/gcc/gcc/gcc/cfgbuild.c,v
retrieving revision 1.45
diff -c -3 -p -r1.45 cfgbuild.c
*** cfgbuild.c	13 May 2004 06:39:32 -0000	1.45
--- cfgbuild.c	25 May 2004 15:20:23 -0000
*************** static void find_basic_blocks_1 (rtx);
*** 53,59 ****
  static rtx find_label_refs (rtx, rtx);
  static void make_edges (rtx, basic_block, basic_block, int);
  static void make_label_edge (sbitmap *, basic_block, rtx, int);
! static void find_bb_boundaries (basic_block);
  static void compute_outgoing_frequencies (basic_block);
  \f
  /* Return true if insn is something that should be contained inside basic
--- 53,59 ----
  static rtx find_label_refs (rtx, rtx);
  static void make_edges (rtx, basic_block, basic_block, int);
  static void make_label_edge (sbitmap *, basic_block, rtx, int);
! static rtx find_bb_boundaries (rtx, basic_block);
  static void compute_outgoing_frequencies (basic_block);
  \f
  /* Return true if insn is something that should be contained inside basic
*************** enum state {BLOCK_NEW = 0, BLOCK_ORIGINA
*** 650,659 ****
  #define SET_STATE(BB, STATE) ((BB)->aux = (void *) (size_t) (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 (basic_block bb)
  {
    rtx insn = BB_HEAD (bb);
    rtx end = BB_END (bb);
--- 661,673 ----
  #define SET_STATE(BB, STATE) ((BB)->aux = (void *) (size_t) (STATE))
  
  /* Scan basic block BB for possible BB boundaries inside the block
!    and create new basic blocks in the progress. 
  
!    Collect and return a list of labels whose addresses are taken.  This
!    will be used in make_edges for use with computed gotos.  */
! 
! static rtx
! find_bb_boundaries (rtx lvl, basic_block bb)
  {
    rtx insn = BB_HEAD (bb);
    rtx end = BB_END (bb);
*************** find_bb_boundaries (basic_block bb)
*** 661,667 ****
    edge fallthru = NULL;
  
    if (insn == BB_END (bb))
!     return;
  
    if (GET_CODE (insn) == CODE_LABEL)
      insn = NEXT_INSN (insn);
--- 675,681 ----
    edge fallthru = NULL;
  
    if (insn == BB_END (bb))
!     return lvl;
  
    if (GET_CODE (insn) == CODE_LABEL)
      insn = NEXT_INSN (insn);
*************** find_bb_boundaries (basic_block bb)
*** 671,676 ****
--- 685,714 ----
      {
        enum rtx_code code = GET_CODE (insn);
  
+       if (GET_CODE (insn) == INSN || GET_CODE (insn) == CALL_INSN)
+ 	{
+ 	  rtx note;
+ 
+ 	  for (note = REG_NOTES (insn); note; note = XEXP (note, 1))
+ 	    if (REG_NOTE_KIND (note) == REG_LABEL)
+ 	      {
+ 		rtx lab = XEXP (note, 0), next;
+ 
+ 		if ((next = next_nonnote_insn (lab)) != NULL
+ 			 && GET_CODE (next) == JUMP_INSN
+ 			 && (GET_CODE (PATTERN (next)) == ADDR_VEC
+ 			     || GET_CODE (PATTERN (next)) == ADDR_DIFF_VEC))
+ 		  ;
+ 		else if (GET_CODE (lab) == NOTE)
+ 		  ;
+ 		else if (GET_CODE (NEXT_INSN (insn)) == JUMP_INSN
+ 			 && find_reg_note (NEXT_INSN (insn), REG_LABEL, lab))
+ 		  ;
+ 		else
+ 		  lvl = alloc_EXPR_LIST (0, XEXP (note, 0), lvl);
+ 	      }
+ 	}
+ 
        /* On code label, split current basic block.  */
        if (code == CODE_LABEL)
  	{
*************** find_bb_boundaries (basic_block bb)
*** 713,718 ****
--- 751,757 ----
       followed by cleanup at fallthru edge, so the outgoing edges may
       be dead.  */
    purge_dead_edges (bb);
+   return lvl;
  }
  
  /*  Assume that frequency of basic block B is known.  Compute frequencies
*************** void
*** 756,761 ****
--- 805,811 ----
  find_many_sub_basic_blocks (sbitmap blocks)
  {
    basic_block bb, min, max;
+   rtx label_value_list = NULL;
  
    FOR_EACH_BB (bb)
      SET_STATE (bb,
*************** find_many_sub_basic_blocks (sbitmap bloc
*** 763,769 ****
  
    FOR_EACH_BB (bb)
      if (STATE (bb) == BLOCK_TO_SPLIT)
!       find_bb_boundaries (bb);
  
    FOR_EACH_BB (bb)
      if (STATE (bb) != BLOCK_ORIGINAL)
--- 813,819 ----
  
    FOR_EACH_BB (bb)
      if (STATE (bb) == BLOCK_TO_SPLIT)
!       label_value_list = find_bb_boundaries (label_value_list, bb);
  
    FOR_EACH_BB (bb)
      if (STATE (bb) != BLOCK_ORIGINAL)
*************** find_many_sub_basic_blocks (sbitmap bloc
*** 776,782 ****
  
    /* 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.  */
--- 826,832 ----
  
    /* Now re-scan and wire in all edges.  This expect simple (conditional)
       jumps at the end of each new basic blocks.  */
!   make_edges (label_value_list, min, max, 1);
  
    /* Update branch probabilities.  Expect only (un)conditional jumps
       to be created with only the forward edges.  */
*************** find_sub_basic_blocks (basic_block bb)
*** 813,819 ****
    basic_block next = bb->next_bb;
  
    min = bb;
!   find_bb_boundaries (bb);
    max = next->prev_bb;
  
    /* Now re-scan and wire in all edges.  This expect simple (conditional)
--- 863,869 ----
    basic_block next = bb->next_bb;
  
    min = bb;
!   find_bb_boundaries (NULL, bb);
    max = next->prev_bb;
  
    /* Now re-scan and wire in all edges.  This expect simple (conditional)

Re: tree profilng merge 3 - find_sub_basic_blocks fixes wrt computed gotos

[Richard Henderson]

On Fri, May 28, 2004 at 12:45:44PM +0200, Jan Hubicka wrote:
> this patch fix find_many_sub_basic_blocks so it update CFG correctly when new
> computed goto is inserted.

Well, sort of.  It adds to label_value_list, but doesn't update 
existing computed gotos to jump to the new labels.  It means that
if you were to rebuild the CFG from scratch afterward you wouldn't
get the same answer.

What's the test case for this?  I would have expected all labels
visible to computed jumps to already exist at the tree level,
and thus we could derive the rtl list from that.



r~

Re: tree profilng merge 3 - find_sub_basic_blocks fixes wrt computed gotos

[Jan Hubicka]

> On Fri, May 28, 2004 at 12:45:44PM +0200, Jan Hubicka wrote:
> > this patch fix find_many_sub_basic_blocks so it update CFG correctly when new
> > computed goto is inserted.
> 
> Well, sort of.  It adds to label_value_list, but doesn't update 
> existing computed gotos to jump to the new labels.  It means that
> if you were to rebuild the CFG from scratch afterward you wouldn't
> get the same answer.

Hmm, it works for me I guess just because I do find_sub_basic_blocks for
all basic blocks at once after the RTL expansions.
> 
> What's the test case for this?  I would have expected all labels
> visible to computed jumps to already exist at the tree level,
> and thus we could derive the rtl list from that.

At the very moment I am simply removing the abormal edges and
re-creating them from scratch using find_sub_basic_blocks since
representation of some abnormal edges differ.  I have fixed few of these
(link longjmps and some of EH) already so perhaps the situation is not
too bad.  I can try to experiment with it after returning from the
vacation at 14th.

Honza
>
> 
> 
> r~

Re: tree profilng merge 3 - find_sub_basic_blocks fixes wrt computed gotos

[Jan Hubicka]

> At the very moment I am simply removing the abormal edges and
> re-creating them from scratch using find_sub_basic_blocks since
> representation of some abnormal edges differ.  I have fixed few of these
> (link longjmps and some of EH) already so perhaps the situation is not
> too bad.  I can try to experiment with it after returning from the
> vacation at 14th.

Another problem with abnormal edges is that the expanders comonly put
some instructions after the instruction producing the edge (for case of
noncall EH it is for valid reasons, in the case of noreturn calls it is
bogus).  I would like to track these cases down, but it is bit involved.
So I guess for now we can simply collect the list of lables either in
find_basic_block or during the cfg expansion from tree level and use it
in the find_sub_basic_block assuming that none of those labels gets
removed.  Does this sound sane
I will also gradually fix the backends expanding code after functions
terminating the flow...

Honza
> 
> Honza
> >
> > 
> > 
> > r~

Re: tree profilng merge 3 - find_sub_basic_blocks fixes wrt computed gotos

[Richard Henderson]

On Wed, Jun 09, 2004 at 03:58:10PM +0200, Jan Hubicka wrote:
> So I guess for now we can simply collect the list of lables either in
> find_basic_block or during the cfg expansion from tree level and use it
> in the find_sub_basic_block assuming that none of those labels gets
> removed.  Does this sound sane

Yes.

> I will also gradually fix the backends expanding code after functions
> terminating the flow...

Thanks.


r~

Re: tree profilng merge 3 - find_sub_basic_blocks fixes wrt computed gotos

[Jan Hubicka]

Hi,
as discussed on IRC, the code collecting label_value_list appears to be
unnecesary.  All labels with address taken on source level are already
in forced_list and thus this list can only make difference if the
expansion introduced new computed jumps and labels.  This should not
happen as there are always better ways of solving this.

Bootstrapped/regtested i686-pc-gnu-linux, OK?

Honza

2004-06-16  Jan Hubicka  <jh@suse.cz>
	* cfgbuild.c (make_edges): Do not use label_value_list.
	(find_basic_blocks_1): Do not collect label_value_list.
	(find_sub_basic_blocks): Update call of make_edges.
Index: cfgbuild.c
===================================================================
RCS file: /cvs/gcc/gcc/gcc/cfgbuild.c,v
retrieving revision 1.48
diff -c -3 -p -r1.48 cfgbuild.c
*** cfgbuild.c	14 Jun 2004 12:09:07 -0000	1.48
--- cfgbuild.c	16 Jun 2004 13:17:35 -0000
*************** Software Foundation, 59 Temple Place - S
*** 50,56 ****
  
  static int count_basic_blocks (rtx);
  static void find_basic_blocks_1 (rtx);
! static void make_edges (rtx, basic_block, basic_block, int);
  static void make_label_edge (sbitmap *, basic_block, rtx, int);
  static void find_bb_boundaries (basic_block);
  static void compute_outgoing_frequencies (basic_block);
--- 50,56 ----
  
  static int count_basic_blocks (rtx);
  static void find_basic_blocks_1 (rtx);
! static void make_edges (basic_block, basic_block, int);
  static void make_label_edge (sbitmap *, basic_block, rtx, int);
  static void find_bb_boundaries (basic_block);
  static void compute_outgoing_frequencies (basic_block);
*************** rtl_make_eh_edge (sbitmap *edge_cache, b
*** 223,229 ****
     the list of exception regions active at the end of the basic block.  */
  
  static void
! make_edges (rtx label_value_list, basic_block min, basic_block max, int update_p)
  {
    basic_block bb;
    sbitmap *edge_cache = NULL;
--- 223,229 ----
     the list of exception regions active at the end of the basic block.  */
  
  static void
! make_edges (basic_block min, basic_block max, int update_p)
  {
    basic_block bb;
    sbitmap *edge_cache = NULL;
*************** make_edges (rtx label_value_list, basic_
*** 240,246 ****
    /* Heavy use of computed goto in machine-generated code can lead to
       nearly fully-connected CFGs.  In that case we spend a significant
       amount of time searching the edge lists for duplicates.  */
!   if (forced_labels || label_value_list || cfun->max_jumptable_ents > 100)
      {
        edge_cache = sbitmap_vector_alloc (last_basic_block, last_basic_block);
        sbitmap_vector_zero (edge_cache, last_basic_block);
--- 240,246 ----
    /* Heavy use of computed goto in machine-generated code can lead to
       nearly fully-connected CFGs.  In that case we spend a significant
       amount of time searching the edge lists for duplicates.  */
!   if (forced_labels || cfun->max_jumptable_ents > 100)
      {
        edge_cache = sbitmap_vector_alloc (last_basic_block, last_basic_block);
        sbitmap_vector_zero (edge_cache, last_basic_block);
*************** make_edges (rtx label_value_list, basic_
*** 326,339 ****
  	    }
  
  	  /* If this is a computed jump, then mark it as reaching
! 	     everything on the label_value_list and forced_labels list.  */
  	  else if (computed_jump_p (insn))
  	    {
  	      current_function_has_computed_jump = 1;
  
- 	      for (x = label_value_list; x; x = XEXP (x, 1))
- 		make_label_edge (edge_cache, bb, XEXP (x, 0), EDGE_ABNORMAL);
- 
  	      for (x = forced_labels; x; x = XEXP (x, 1))
  		make_label_edge (edge_cache, bb, XEXP (x, 0), EDGE_ABNORMAL);
  	    }
--- 326,336 ----
  	    }
  
  	  /* If this is a computed jump, then mark it as reaching
! 	     everything on the forced_labels list.  */
  	  else if (computed_jump_p (insn))
  	    {
  	      current_function_has_computed_jump = 1;
  
  	      for (x = forced_labels; x; x = XEXP (x, 1))
  		make_label_edge (edge_cache, bb, XEXP (x, 0), EDGE_ABNORMAL);
  	    }
*************** find_basic_blocks_1 (rtx f)
*** 424,430 ****
  {
    rtx insn, next;
    rtx bb_note = NULL_RTX;
-   rtx lvl = NULL_RTX;
    rtx head = NULL_RTX;
    rtx end = NULL_RTX;
    basic_block prev = ENTRY_BLOCK_PTR;
--- 421,426 ----
*************** find_basic_blocks_1 (rtx f)
*** 493,530 ****
  	default:
  	  abort ();
  	}
- 
-       if (GET_CODE (insn) == INSN || GET_CODE (insn) == CALL_INSN)
- 	{
- 	  rtx note;
- 
- 	  /* Make a list of all labels referred to other than by jumps.
- 
- 	     Make a special exception for labels followed by an ADDR*VEC,
- 	     as this would be a part of the tablejump setup code.
- 
- 	     Make a special exception to registers loaded with label
- 	     values just before jump insns that use them.  */
- 
- 	  for (note = REG_NOTES (insn); note; note = XEXP (note, 1))
- 	    if (REG_NOTE_KIND (note) == REG_LABEL)
- 	      {
- 		rtx lab = XEXP (note, 0), next;
- 
- 		if ((next = next_nonnote_insn (lab)) != NULL
- 			 && GET_CODE (next) == JUMP_INSN
- 			 && (GET_CODE (PATTERN (next)) == ADDR_VEC
- 			     || GET_CODE (PATTERN (next)) == ADDR_DIFF_VEC))
- 		  ;
- 		else if (GET_CODE (lab) == NOTE)
- 		  ;
- 		else if (GET_CODE (NEXT_INSN (insn)) == JUMP_INSN
- 			 && find_reg_note (NEXT_INSN (insn), REG_LABEL, lab))
- 		  ;
- 		else
- 		  lvl = alloc_EXPR_LIST (0, XEXP (note, 0), lvl);
- 	      }
- 	}
      }
  
    if (head != NULL_RTX)
--- 489,494 ----
*************** find_basic_blocks_1 (rtx f)
*** 535,541 ****
    if (last_basic_block != n_basic_blocks)
      abort ();
  
-   label_value_list = lvl;
    clear_aux_for_blocks ();
  }
  
--- 499,504 ----
*************** find_basic_blocks (rtx f, int nregs ATTR
*** 584,590 ****
    find_basic_blocks_1 (f);
  
    /* Discover the edges of our cfg.  */
!   make_edges (label_value_list, ENTRY_BLOCK_PTR->next_bb, EXIT_BLOCK_PTR->prev_bb, 0);
  
    /* Do very simple cleanup now, for the benefit of code that runs between
       here and cleanup_cfg, e.g. thread_prologue_and_epilogue_insns.  */
--- 547,553 ----
    find_basic_blocks_1 (f);
  
    /* Discover the edges of our cfg.  */
!   make_edges (ENTRY_BLOCK_PTR->next_bb, EXIT_BLOCK_PTR->prev_bb, 0);
  
    /* Do very simple cleanup now, for the benefit of code that runs between
       here and cleanup_cfg, e.g. thread_prologue_and_epilogue_insns.  */
*************** find_many_sub_basic_blocks (sbitmap bloc
*** 729,735 ****
  
    /* 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.  */
--- 692,698 ----
  
    /* Now re-scan and wire in all edges.  This expect simple (conditional)
       jumps at the end of each new basic blocks.  */
!   make_edges (min, max, 1);
  
    /* Update branch probabilities.  Expect only (un)conditional jumps
       to be created with only the forward edges.  */
*************** find_sub_basic_blocks (basic_block bb)
*** 771,777 ****
  
    /* 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.  */
--- 734,740 ----
  
    /* Now re-scan and wire in all edges.  This expect simple (conditional)
       jumps at the end of each new basic blocks.  */
!   make_edges (min, max, 1);
  
    /* Update branch probabilities.  Expect only (un)conditional jumps
       to be created with only the forward edges.  */

Re: tree profilng merge 3 - find_sub_basic_blocks fixes wrt computed gotos

[Richard Henderson]

On Wed, Jun 16, 2004 at 03:28:36PM +0200, Jan Hubicka wrote:
> 	* cfgbuild.c (make_edges): Do not use label_value_list.
> 	(find_basic_blocks_1): Do not collect label_value_list.
> 	(find_sub_basic_blocks): Update call of make_edges.

Ok.


r~