Re: Basic block renumbering removal

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

Hello.

This patch creates and keeps double linked list of basic blocks (without
using it for anything).

Bootstrapped/regtested on i686.

Zdenek Dvorak

Changelog:
	* basic_block.h (struct basic_block_def): Added prev_bb and next_bb fields.
	(FOR_BB_BETWEEN, FOR_ALL_BB, FOR_ALL_BB_REVERSE): New macros for
	traversing basic block chain.
	(create_basic_block_structure, create_basic_block): Declaration changed.
	(link_block, unlink_block): Declare.
	* cfg.c (entry_exit_blocks): Initialize new fields.
	(link_block, unlink_block): New.
	(expunge_block_nocompact): Unlink basic block.
	(dump_flow_info): Print prev_bb/next_bb fields.
	* cfgbuild.c (find_basic_blocks_1, find_basic_blocks): Modified.
	* cfgcleanup.c (merge_blocks_move_predecessor_nojumps): Modified.
	* cfglayout.c (fixup_reorder_chain, cfg_layout_duplicate_bb): Modified.
	* cfgrtl.c (create_basic_block_structure, create_basic_block,
	split_block, force_nonfallthru_and_redirect, split_edge): Modified.
	(verify_flow_info): Check that list agrees with numbering.

Index: basic-block.h
===================================================================
RCS file: /cvsroot/gcc/gcc/gcc/basic-block.h,v
retrieving revision 1.143
diff -c -3 -p -r1.143 basic-block.h
*** basic-block.h	17 May 2002 02:31:26 -0000	1.143
--- basic-block.h	19 May 2002 20:13:00 -0000
*************** typedef struct basic_block_def {
*** 206,211 ****
--- 206,214 ----
    /* The index of this block.  */
    int index;
  
+   /* Previous and next blocks in the chain.  */
+   struct basic_block_def *prev_bb, *next_bb;
+ 
    /* The loop depth of this block.  */
    int loop_depth;
  
*************** extern varray_type basic_block_info;
*** 240,245 ****
--- 243,258 ----
  
  #define BASIC_BLOCK(N)  (VARRAY_BB (basic_block_info, (N)))
  
+ /* For iterating over basic blocks.  */
+ #define FOR_BB_BETWEEN(BB, FROM, TO, DIR) \
+   for (BB = FROM; BB != TO; BB = BB->DIR)
+ 
+ #define FOR_EACH_BB(BB) \
+   FOR_BB_BETWEEN (BB, ENTRY_BLOCK_PTR->next_bb, EXIT_BLOCK_PTR, next_bb)
+ 
+ #define FOR_EACH_BB_REVERSE(BB) \
+   FOR_BB_BETWEEN (BB, EXIT_BLOCK_PTR->prev_bb, ENTRY_BLOCK_PTR, prev_bb)
+ 
  /* What registers are live at the setjmp call.  */
  
  extern regset regs_live_at_setjmp;
*************** extern void remove_edge			PARAMS ((edge)
*** 314,321 ****
  extern void redirect_edge_succ		PARAMS ((edge, basic_block));
  extern edge redirect_edge_succ_nodup	PARAMS ((edge, basic_block));
  extern void redirect_edge_pred		PARAMS ((edge, basic_block));
! extern basic_block create_basic_block_structure PARAMS ((int, rtx, rtx, rtx));
! extern basic_block create_basic_block	PARAMS ((int, rtx, rtx));
  extern int flow_delete_block		PARAMS ((basic_block));
  extern int flow_delete_block_noexpunge	PARAMS ((basic_block));
  extern void clear_bb_flags		PARAMS ((void));
--- 327,334 ----
  extern void redirect_edge_succ		PARAMS ((edge, basic_block));
  extern edge redirect_edge_succ_nodup	PARAMS ((edge, basic_block));
  extern void redirect_edge_pred		PARAMS ((edge, basic_block));
! extern basic_block create_basic_block_structure PARAMS ((int, rtx, rtx, rtx, basic_block));
! extern basic_block create_basic_block	PARAMS ((rtx, rtx, basic_block));
  extern int flow_delete_block		PARAMS ((basic_block));
  extern int flow_delete_block_noexpunge	PARAMS ((basic_block));
  extern void clear_bb_flags		PARAMS ((void));
*************** extern void debug_regset		PARAMS ((regse
*** 644,649 ****
--- 657,664 ----
  extern void allocate_reg_life_data      PARAMS ((void));
  extern void allocate_bb_life_data	PARAMS ((void));
  extern void expunge_block		PARAMS ((basic_block));
+ extern void link_block			PARAMS ((basic_block, basic_block));
+ extern void unlink_block		PARAMS ((basic_block));
  extern void expunge_block_nocompact	PARAMS ((basic_block));
  extern basic_block alloc_block		PARAMS ((void));
  extern void find_unreachable_blocks	PARAMS ((void));
Index: cfg.c
===================================================================
RCS file: /cvsroot/gcc/gcc/gcc/cfg.c,v
retrieving revision 1.26
diff -c -3 -p -r1.26 cfg.c
*** cfg.c	17 May 2002 02:31:27 -0000	1.26
--- cfg.c	19 May 2002 20:13:00 -0000
*************** struct basic_block_def entry_exit_blocks
*** 93,98 ****
--- 93,100 ----
      NULL,			/* global_live_at_end */
      NULL,			/* aux */
      ENTRY_BLOCK,		/* index */
+     NULL,			/* prev_bb */
+     EXIT_BLOCK_PTR,		/* next_bb */
      0,				/* loop_depth */
      0,				/* count */
      0,				/* frequency */
*************** struct basic_block_def entry_exit_blocks
*** 111,116 ****
--- 113,120 ----
      NULL,			/* global_live_at_end */
      NULL,			/* aux */
      EXIT_BLOCK,			/* index */
+     ENTRY_BLOCK_PTR,		/* prev_bb */
+     NULL,			/* next_bb */
      0,				/* loop_depth */
      0,				/* count */
      0,				/* frequency */
*************** alloc_block ()
*** 220,231 ****
--- 224,258 ----
    return bb;
  }
  
+ /* Link block B to chain after AFTER.  */
+ void
+ link_block (b, after)
+      basic_block b, after;
+ {
+   b->next_bb = after->next_bb;
+   b->prev_bb = after;
+   after->next_bb = b;
+   b->next_bb->prev_bb = b;
+ }
+   
+ /* Unlink block B from chain.  */
+ void
+ unlink_block (b)
+      basic_block b;
+ {
+   b->next_bb->prev_bb = b->prev_bb;
+   b->prev_bb->next_bb = b->next_bb;
+ }
+   
+ 
  /* Remove block B from the basic block array and compact behind it.  */
  
  void
  expunge_block_nocompact (b)
       basic_block b;
  {
+   unlink_block (b);
+ 
    /* Invalidate data to make bughunting easier.  */
    memset (b, 0, sizeof *b);
    b->index = -3;
*************** dump_flow_info (file)
*** 521,526 ****
--- 548,555 ----
  
        fprintf (file, "\nBasic block %d: first insn %d, last %d, ",
  	       i, INSN_UID (bb->head), INSN_UID (bb->end));
+       fprintf (file, "prev %d, next %d, ",
+ 	       bb->prev_bb->index, bb->next_bb->index);
        fprintf (file, "loop_depth %d, count ", bb->loop_depth);
        fprintf (file, HOST_WIDEST_INT_PRINT_DEC, bb->count);
        fprintf (file, ", freq %i.\n", bb->frequency);
Index: cfgbuild.c
===================================================================
RCS file: /cvsroot/gcc/gcc/gcc/cfgbuild.c,v
retrieving revision 1.15
diff -c -3 -p -r1.15 cfgbuild.c
*** cfgbuild.c	17 May 2002 02:31:27 -0000	1.15
--- cfgbuild.c	19 May 2002 20:13:00 -0000
*************** find_basic_blocks_1 (f)
*** 476,481 ****
--- 476,482 ----
    rtx trll = NULL_RTX;
    rtx head = NULL_RTX;
    rtx end = NULL_RTX;
+   basic_block prev = ENTRY_BLOCK_PTR;
  
    /* We process the instructions in a slightly different way than we did
       previously.  This is so that we see a NOTE_BASIC_BLOCK after we have
*************** find_basic_blocks_1 (f)
*** 492,498 ****
        if ((GET_CODE (insn) == CODE_LABEL || GET_CODE (insn) == BARRIER)
  	  && head)
  	{
! 	  create_basic_block_structure (i++, head, end, bb_note);
  	  head = end = NULL_RTX;
  	  bb_note = NULL_RTX;
  	}
--- 493,499 ----
        if ((GET_CODE (insn) == CODE_LABEL || GET_CODE (insn) == BARRIER)
  	  && head)
  	{
! 	  prev = create_basic_block_structure (i++, head, end, bb_note, prev);
  	  head = end = NULL_RTX;
  	  bb_note = NULL_RTX;
  	}
*************** find_basic_blocks_1 (f)
*** 506,512 ****
  
        if (head && control_flow_insn_p (insn))
  	{
! 	  create_basic_block_structure (i++, head, end, bb_note);
  	  head = end = NULL_RTX;
  	  bb_note = NULL_RTX;
  	}
--- 507,513 ----
  
        if (head && control_flow_insn_p (insn))
  	{
! 	  prev = create_basic_block_structure (i++, head, end, bb_note, prev);
  	  head = end = NULL_RTX;
  	  bb_note = NULL_RTX;
  	}
*************** find_basic_blocks_1 (f)
*** 588,594 ****
      }
  
    if (head != NULL_RTX)
!     create_basic_block_structure (i++, head, end, bb_note);
    else if (bb_note)
      delete_insn (bb_note);
  
--- 589,595 ----
      }
  
    if (head != NULL_RTX)
!     create_basic_block_structure (i++, head, end, bb_note, prev);
    else if (bb_note)
      delete_insn (bb_note);
  
*************** find_basic_blocks (f, nregs, file)
*** 633,638 ****
--- 634,641 ----
      }
  
    n_basic_blocks = count_basic_blocks (f);
+   ENTRY_BLOCK_PTR->next_bb = EXIT_BLOCK_PTR;
+   EXIT_BLOCK_PTR->prev_bb = ENTRY_BLOCK_PTR;
  
    /* Size the basic block table.  The actual structures will be allocated
       by find_basic_blocks_1, since we want to keep the structure pointers
Index: cfgcleanup.c
===================================================================
RCS file: /cvsroot/gcc/gcc/gcc/cfgcleanup.c,v
retrieving revision 1.55
diff -c -3 -p -r1.55 cfgcleanup.c
*** cfgcleanup.c	17 May 2002 02:31:28 -0000	1.55
--- cfgcleanup.c	19 May 2002 20:13:00 -0000
*************** merge_blocks_move_predecessor_nojumps (a
*** 723,728 ****
--- 723,731 ----
    a->index = b->index;
    b->index = index;
  
+   unlink_block (a);
+   link_block (a, b->prev_bb);
+ 
    /* Now blocks A and B are contiguous.  Merge them.  */
    merge_blocks_nomove (a, b);
  }
Index: cfglayout.c
===================================================================
RCS file: /cvsroot/gcc/gcc/gcc/cfglayout.c,v
retrieving revision 1.13
diff -c -3 -p -r1.13 cfglayout.c
*** cfglayout.c	17 May 2002 02:31:28 -0000	1.13
--- cfglayout.c	19 May 2002 20:13:00 -0000
*************** scope_to_insns_finalize ()
*** 357,363 ****
  static void
  fixup_reorder_chain ()
  {
!   basic_block bb;
    int index;
    rtx insn = NULL;
  
--- 357,363 ----
  static void
  fixup_reorder_chain ()
  {
!   basic_block bb, prev_bb;
    int index;
    rtx insn = NULL;
  
*************** fixup_reorder_chain ()
*** 541,551 ****
  	}
      }
  
!   for (bb = BASIC_BLOCK (0), index = 0; bb; bb = RBI (bb)->next, index ++)
      {
        bb->index = index;
        BASIC_BLOCK (index) = bb;
      }
  }
  
  /* Perform sanity checks on the insn chain.
--- 541,560 ----
  	}
      }
  
!   prev_bb = ENTRY_BLOCK_PTR;
!   bb = BASIC_BLOCK (0);
!   index = 0;
! 
!   for (; bb; prev_bb = bb, bb = RBI (bb)->next, index ++)
      {
        bb->index = index;
        BASIC_BLOCK (index) = bb;
+ 
+       bb->prev_bb = prev_bb;
+       prev_bb->next_bb = bb;
      }
+   prev_bb->next_bb = EXIT_BLOCK_PTR;
+   EXIT_BLOCK_PTR->prev_bb = prev_bb;
  }
  
  /* Perform sanity checks on the insn chain.
*************** cfg_layout_duplicate_bb (bb, e)
*** 871,878 ****
  #endif
  
    insn = duplicate_insn_chain (bb->head, bb->end);
!   new_bb = create_basic_block (n_basic_blocks, insn,
! 		 	       insn ? get_last_insn () : NULL);
    alloc_aux_for_block (new_bb, sizeof (struct reorder_block_def));
  
    if (RBI (bb)->header)
--- 880,888 ----
  #endif
  
    insn = duplicate_insn_chain (bb->head, bb->end);
!   new_bb = create_basic_block (insn,
! 		 	       insn ? get_last_insn () : NULL,
! 			       EXIT_BLOCK_PTR->prev_bb);
    alloc_aux_for_block (new_bb, sizeof (struct reorder_block_def));
  
    if (RBI (bb)->header)
Index: cfgrtl.c
===================================================================
RCS file: /cvsroot/gcc/gcc/gcc/cfgrtl.c,v
retrieving revision 1.47
diff -c -3 -p -r1.47 cfgrtl.c
*** cfgrtl.c	17 May 2002 02:31:28 -0000	1.47
--- cfgrtl.c	19 May 2002 20:13:01 -0000
*************** delete_insn_chain_and_edges (first, last
*** 248,259 ****
     the note and basic block struct in BB_NOTE, if any and do not grow
     BASIC_BLOCK chain and should be used directly only by CFG construction code.
     END can be NULL in to create new empty basic block before HEAD.  Both END
!    and HEAD can be NULL to create basic block at the end of INSN chain.  */
  
  basic_block
! create_basic_block_structure (index, head, end, bb_note)
       int index;
       rtx head, end, bb_note;
  {
    basic_block bb;
  
--- 248,261 ----
     the note and basic block struct in BB_NOTE, if any and do not grow
     BASIC_BLOCK chain and should be used directly only by CFG construction code.
     END can be NULL in to create new empty basic block before HEAD.  Both END
!    and HEAD can be NULL to create basic block at the end of INSN chain.
!    AFTER is the basic block we should be put after.  */
  
  basic_block
! create_basic_block_structure (index, head, end, bb_note, after)
       int index;
       rtx head, end, bb_note;
+      basic_block after;
  {
    basic_block bb;
  
*************** create_basic_block_structure (index, hea
*** 311,316 ****
--- 313,319 ----
    bb->end = end;
    bb->index = index;
    bb->flags = BB_NEW;
+   link_block (bb, after);
    BASIC_BLOCK (index) = bb;
    if (basic_block_for_insn)
      update_bb_for_insn (bb);
*************** create_basic_block_structure (index, hea
*** 323,339 ****
  }
  
  /* Create new basic block consisting of instructions in between HEAD and END
!    and place it to the BB chain at position INDEX.  END can be NULL in to
     create new empty basic block before HEAD.  Both END and HEAD can be NULL to
     create basic block at the end of INSN chain.  */
  
  basic_block
! create_basic_block (index, head, end)
!      int index;
       rtx head, end;
  {
    basic_block bb;
    int i;
  
    /* Place the new block just after the block being split.  */
    VARRAY_GROW (basic_block_info, ++n_basic_blocks);
--- 326,343 ----
  }
  
  /* Create new basic block consisting of instructions in between HEAD and END
!    and place it to the BB chain after block AFTER.  END can be NULL in to
     create new empty basic block before HEAD.  Both END and HEAD can be NULL to
     create basic block at the end of INSN chain.  */
  
  basic_block
! create_basic_block (head, end, after)
       rtx head, end;
+      basic_block after;
  {
    basic_block bb;
    int i;
+   int index = after->index + 1;
  
    /* Place the new block just after the block being split.  */
    VARRAY_GROW (basic_block_info, ++n_basic_blocks);
*************** create_basic_block (index, head, end)
*** 349,355 ****
        tmp->index = i;
      }
  
!   bb = create_basic_block_structure (index, head, end, NULL);
    bb->aux = NULL;
    return bb;
  }
--- 353,359 ----
        tmp->index = i;
      }
  
!   bb = create_basic_block_structure (index, head, end, NULL, after);
    bb->aux = NULL;
    return bb;
  }
*************** split_block (bb, insn)
*** 537,543 ****
      return 0;
  
    /* Create the new basic block.  */
!   new_bb = create_basic_block (bb->index + 1, NEXT_INSN (insn), bb->end);
    new_bb->count = bb->count;
    new_bb->frequency = bb->frequency;
    new_bb->loop_depth = bb->loop_depth;
--- 541,547 ----
      return 0;
  
    /* Create the new basic block.  */
!   new_bb = create_basic_block (NEXT_INSN (insn), bb->end, bb);
    new_bb->count = bb->count;
    new_bb->frequency = bb->frequency;
    new_bb->loop_depth = bb->loop_depth;
*************** force_nonfallthru_and_redirect (e, targe
*** 998,1004 ****
        /* We can't redirect the entry block.  Create an empty block at the
           start of the function which we use to add the new jump.  */
        edge *pe1;
!       basic_block bb = create_basic_block (0, e->dest->head, NULL);
  
        /* Change the existing edge's source to be the new block, and add
  	 a new edge from the entry block to the new block.  */
--- 1002,1008 ----
        /* We can't redirect the entry block.  Create an empty block at the
           start of the function which we use to add the new jump.  */
        edge *pe1;
!       basic_block bb = create_basic_block (e->dest->head, NULL, ENTRY_BLOCK_PTR);
  
        /* Change the existing edge's source to be the new block, and add
  	 a new edge from the entry block to the new block.  */
*************** force_nonfallthru_and_redirect (e, targe
*** 1019,1025 ****
        /* Create the new structures.  */
        note = last_loop_beg_note (e->src->end);
        jump_block
! 	= create_basic_block (e->src->index + 1, NEXT_INSN (note), NULL);
        jump_block->count = e->count;
        jump_block->frequency = EDGE_FREQUENCY (e);
        jump_block->loop_depth = target->loop_depth;
--- 1023,1029 ----
        /* Create the new structures.  */
        note = last_loop_beg_note (e->src->end);
        jump_block
! 	= create_basic_block (NEXT_INSN (note), NULL, e->src);
        jump_block->count = e->count;
        jump_block->frequency = EDGE_FREQUENCY (e);
        jump_block->loop_depth = target->loop_depth;
*************** split_edge (edge_in)
*** 1286,1293 ****
    else
      before = NULL_RTX;
  
!   bb = create_basic_block (edge_in->dest == EXIT_BLOCK_PTR ? n_basic_blocks
! 			   : edge_in->dest->index, before, NULL);
    bb->count = edge_in->count;
    bb->frequency = EDGE_FREQUENCY (edge_in);
  
--- 1290,1296 ----
    else
      before = NULL_RTX;
  
!   bb = create_basic_block (before, NULL, edge_in->dest->prev_bb);
    bb->count = edge_in->count;
    bb->frequency = EDGE_FREQUENCY (edge_in);
  
*************** verify_flow_info ()
*** 1719,1729 ****
--- 1722,1769 ----
    size_t *edge_checksum;
    rtx x;
    int i, last_bb_num_seen, num_bb_notes, err = 0;
+   basic_block bb, last_bb_seen;
  
    bb_info = (basic_block *) xcalloc (max_uid, sizeof (basic_block));
    last_visited = (basic_block *) xcalloc (n_basic_blocks + 2,
  					  sizeof (basic_block));
    edge_checksum = (size_t *) xcalloc (n_basic_blocks + 2, sizeof (size_t));
+ 
+   /* Check bb chain & numbers.  */
+   last_bb_seen = ENTRY_BLOCK_PTR;
+   FOR_BB_BETWEEN (bb, ENTRY_BLOCK_PTR->next_bb, NULL, next_bb)
+     {
+       if (bb != EXIT_BLOCK_PTR
+ 	  && bb != BASIC_BLOCK (bb->index))
+ 	{
+ 	  error ("bb %d on wrong place", bb->index);
+ 	  err = 1;
+ 	}
+ 
+       if (bb->prev_bb != last_bb_seen)
+ 	{
+ 	  error ("prev_bb of %d should be %d, not %d",
+ 		 bb->index, last_bb_seen->index, bb->prev_bb->index);
+ 	  err = 1;
+ 	}
+ 
+       /* For now, also check that we didn't change the order.  */
+       if (bb != EXIT_BLOCK_PTR && bb->index != last_bb_seen->index + 1)
+ 	{
+ 	  error ("Wrong order of blocks %d and %d",
+ 		 last_bb_seen->index, bb->index);
+ 	  err = 1;
+ 	}
+ 
+       if (bb == EXIT_BLOCK_PTR && last_bb_seen->index != n_basic_blocks - 1)
+ 	{
+ 	  error ("Only %d of %d blocks in chain",
+ 		 last_bb_seen->index + 1, n_basic_blocks);
+ 	  err = 1;
+ 	}
+ 
+       last_bb_seen = bb;
+     }
  
    for (i = n_basic_blocks - 1; i >= 0; i--)
      {