[patch] Remove BB_VISITED

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

Hello,

this patch avoids usage of BB_VISITED in dfs_enumerate_from, thus
making it possible to get rid of the flag completely (having a bb flag
reserved for just one function is quite weird).

Bootstrapped & regtested on i686.

Zdenek

	* basic-block.h (BB_VISITED): Removed.
	* cfganal.c (dfs_enumerate_from): Do not use BB_VISITED flag.

Index: basic-block.h
===================================================================
RCS file: /cvs/gcc/gcc/gcc/basic-block.h,v
retrieving revision 1.243
diff -c -3 -p -r1.243 basic-block.h
*** basic-block.h	11 Mar 2005 09:30:50 -0000	1.243
--- basic-block.h	13 Mar 2005 23:00:29 -0000
*************** typedef struct reorder_block_def
*** 287,329 ****
  
  /* Masks for basic_block.flags.
  
-    BB_VISITED should not be used by passes, it is used internally by
-    dfs_enumerate_from.
- 
     BB_HOT_PARTITION and BB_COLD_PARTITION should be preserved throughout
     the compilation, so they are never cleared.
  
     All other flags may be cleared by clear_bb_flags().  It is generally
     a bad idea to rely on any flags being up-to-date.  */
  
! /* Set if insns in BB have are modified.  Used for updating liveness info.  */
! #define BB_DIRTY		1
  
! /* Only set on blocks that have just been created by create_bb.  */
! #define BB_NEW			2
  
! /* Set by find_unreachable_blocks.  Do not rely on this being set in any
!    pass.  */
! #define BB_REACHABLE		4
  
! /* Used by dfs_enumerate_from to keep track of visited basic blocks.  */
! #define BB_VISITED		8
  
! /* Set for blocks in an irreducible loop by loop analysis.  */
! #define BB_IRREDUCIBLE_LOOP	16
  
! /* Set on blocks that may actually not be single-entry single-exit block.  */
! #define BB_SUPERBLOCK		32
  
! /* Set on basic blocks that the scheduler should not touch.  This is used
!    by SMS to prevent other schedulers from messing with the loop schedule.  */
! #define BB_DISABLE_SCHEDULE	64
  
! /* Set on blocks that should be put in a hot section.  */
! #define BB_HOT_PARTITION	128
  
! /* Set on blocks that should be put in a cold section.  */
! #define BB_COLD_PARTITION	256
  
  /* Dummy flag for convenience in the hot/cold partitioning code.  */
  #define BB_UNPARTITIONED	0
--- 287,327 ----
  
  /* Masks for basic_block.flags.
  
     BB_HOT_PARTITION and BB_COLD_PARTITION should be preserved throughout
     the compilation, so they are never cleared.
  
     All other flags may be cleared by clear_bb_flags().  It is generally
     a bad idea to rely on any flags being up-to-date.  */
  
! enum
! {
  
!   /* Set if insns in BB have are modified.  Used for updating liveness info.  */
!   BB_DIRTY = 1,
  
!   /* Only set on blocks that have just been created by create_bb.  */
!   BB_NEW = 2,
  
!   /* Set by find_unreachable_blocks.  Do not rely on this being set in any
!      pass.  */
!   BB_REACHABLE = 4,
  
!   /* Set for blocks in an irreducible loop by loop analysis.  */
!   BB_IRREDUCIBLE_LOOP = 8,
  
!   /* Set on blocks that may actually not be single-entry single-exit block.  */
!   BB_SUPERBLOCK = 16,
  
!   /* Set on basic blocks that the scheduler should not touch.  This is used
!      by SMS to prevent other schedulers from messing with the loop schedule.  */
!   BB_DISABLE_SCHEDULE = 32,
  
!   /* Set on blocks that should be put in a hot section.  */
!   BB_HOT_PARTITION = 64,
  
!   /* Set on blocks that should be put in a cold section.  */
!   BB_COLD_PARTITION = 128
! };
  
  /* Dummy flag for convenience in the hot/cold partitioning code.  */
  #define BB_UNPARTITIONED	0
Index: cfganal.c
===================================================================
RCS file: /cvs/gcc/gcc/gcc/cfganal.c,v
retrieving revision 1.60
diff -c -3 -p -r1.60 cfganal.c
*** cfganal.c	11 Mar 2005 09:04:47 -0000	1.60
--- cfganal.c	13 Mar 2005 23:00:29 -0000
*************** dfs_enumerate_from (basic_block bb, int 
*** 900,909 ****
  {
    basic_block *st, lbb;
    int sp = 0, tv = 0;
  
    st = xcalloc (rslt_max, sizeof (basic_block));
    rslt[tv++] = st[sp++] = bb;
!   bb->flags |= BB_VISITED;
    while (sp)
      {
        edge e;
--- 900,944 ----
  {
    basic_block *st, lbb;
    int sp = 0, tv = 0;
+   unsigned size;
+ 
+   /* A bitmap to keep track of visited blocks.  Allocating it each time
+      this function is called is not possible, since dfs_enumerate_from
+      is often used on small (almost) disjoint parts of cfg (bodies of
+      loops), and allocating a large sbitmap would lead to quadratic
+      behavior.  */
+   static sbitmap visited;
+   static unsigned v_size;
+ 
+ #define MARK_VISITED(BB) (SET_BIT (visited, (BB)->index + 2))
+ #define UNMARK_VISITED(BB) (RESET_BIT (visited, (BB)->index + 2))
+ #define VISITED_P(BB) (TEST_BIT (visited, (BB)->index + 2))
+ 
+   /* Resize the VISITED sbitmap if necessary.  */
+   size = last_basic_block + 2;
+   if (size < 10)
+     size = 10;
+ 
+   if (!visited)
+     {
+ 
+       visited = sbitmap_alloc (size);
+       sbitmap_zero (visited);
+       v_size = size;
+     }
+   else if (v_size < size)
+     {
+       /* Ensure that we increase the size of the sbitmap exponentially.  */
+       if (2 * v_size > size)
+ 	size = 2 * v_size;
+ 
+       visited = sbitmap_resize (visited, size, 0);
+       v_size = size;
+     }
  
    st = xcalloc (rslt_max, sizeof (basic_block));
    rslt[tv++] = st[sp++] = bb;
!   MARK_VISITED (bb);
    while (sp)
      {
        edge e;
*************** dfs_enumerate_from (basic_block bb, int 
*** 912,939 ****
        if (reverse)
          {
  	  FOR_EACH_EDGE (e, ei, lbb->preds)
! 	    if (!(e->src->flags & BB_VISITED) && predicate (e->src, data))
  	      {
  	        gcc_assert (tv != rslt_max);
  	        rslt[tv++] = st[sp++] = e->src;
! 	        e->src->flags |= BB_VISITED;
  	      }
          }
        else
          {
  	  FOR_EACH_EDGE (e, ei, lbb->succs)
! 	    if (!(e->dest->flags & BB_VISITED) && predicate (e->dest, data))
  	      {
  	        gcc_assert (tv != rslt_max);
  	        rslt[tv++] = st[sp++] = e->dest;
! 	        e->dest->flags |= BB_VISITED;
  	      }
  	}
      }
    free (st);
    for (sp = 0; sp < tv; sp++)
!     rslt[sp]->flags &= ~BB_VISITED;
    return tv;
  }
  
  
--- 947,977 ----
        if (reverse)
          {
  	  FOR_EACH_EDGE (e, ei, lbb->preds)
! 	    if (!VISITED_P (e->src) && predicate (e->src, data))
  	      {
  	        gcc_assert (tv != rslt_max);
  	        rslt[tv++] = st[sp++] = e->src;
! 	        MARK_VISITED (e->src);
  	      }
          }
        else
          {
  	  FOR_EACH_EDGE (e, ei, lbb->succs)
! 	    if (!VISITED_P (e->dest) && predicate (e->dest, data))
  	      {
  	        gcc_assert (tv != rslt_max);
  	        rslt[tv++] = st[sp++] = e->dest;
! 	        MARK_VISITED (e->dest);
  	      }
  	}
      }
    free (st);
    for (sp = 0; sp < tv; sp++)
!     UNMARK_VISITED (rslt[sp]);
    return tv;
+ #undef MARK_VISITED
+ #undef UNMARK_VISITED
+ #undef VISITED_P
  }