[dataflow] Add/use bitmap_set_range

[Paolo Bonzini <paolo dot bonzini at lu dot unisi dot ch>]

This is a simple low-hanging fruit.  Instead of using
the relatively complex df_ref_bitmap mechanism (which
builds bitmaps with a single range of 1's) we can use
those lines of code to write a new bitmap_set_range
function (to complement the existing bitmap_clear_range).

This is compile-time neutral on bootstrap, saves 2%
on PR28071 -O2.  Might save a few megabytes of memory,
though not much (by the way: it might be time for another
merge; there were some improvements on mainline lately
with respect to memory savings).

I figure a reason for this could be either a different
implementation in the past, or preparing for a different
implementation in the future.

Anyway, svn is there to find the code if needed.  Ok?

Paolo
2007-04-07  Paolo Bonzini  <bonzini@gnu.org>

	* bitmap.c (bitmap_set_range): New.
	(bitmap_clear_range): Small optimization.
	* bitmap.h (bitmap_set_range): New.
	* df-problems.c (df_ref_bitmap): Remove.
	(struct df_rd_problem_data, df_ru_problem_data): Remove related
	data structures.
	(df_ru_alloc, df_rd_alloc): Don't allocate them.
	(df_ru_free, df_rd_free): Don't free them.
	(df_ru_bb_local_compute_process_def, df_ru_local_compute,
	df_rd_bb_local_compute_process_def, df_rd_local_compute):
	Use bitmap_set_range and bitmap_clear_range instead of df_ref_bitmap.

Index: bitmap.c
===================================================================
--- bitmap.c	(revision 123416)
+++ bitmap.c	(working copy)
@@ -1053,6 +1053,104 @@ bitmap_and_compl_into (bitmap a, bitmap 
   return changed != 0;
 }
 
+/* Set COUNT bits from START in HEAD.  */
+void
+bitmap_set_range (bitmap head, unsigned int start, unsigned int count)
+{
+  unsigned int first_index = start / BITMAP_ELEMENT_ALL_BITS;
+  unsigned int end_bit_plus1 = start + count;
+  unsigned int end_bit = end_bit_plus1 - 1;
+  unsigned int last_index = end_bit / BITMAP_ELEMENT_ALL_BITS;
+  bitmap_element *elt = bitmap_find_bit (head, start);
+  bitmap_element *elt_prev;
+  unsigned int i;
+
+  /* If bitmap_find_bit returns zero, the current is the closest block
+     to the result.  Do it the easy way and just use bitmap_element_link
+     to place it at the right spot.  */
+  if (!elt)
+    {
+      elt = bitmap_element_allocate (head);
+      elt->indx = first_index;
+      bitmap_element_link (head, elt);
+    }
+
+  gcc_assert (elt->indx == first_index);
+  elt_prev = elt->prev;
+  for (i = first_index; i <= last_index; i++)
+    {
+      unsigned elt_start_bit = i * BITMAP_ELEMENT_ALL_BITS;
+      unsigned elt_end_bit_plus1 = elt_start_bit + BITMAP_ELEMENT_ALL_BITS;
+
+      unsigned int first_word_to_mod;
+      BITMAP_WORD first_mask;
+      unsigned int last_word_to_mod;
+      BITMAP_WORD last_mask;
+      unsigned int ix;
+
+      if (!elt || elt->indx != i)
+	elt = bitmap_elt_insert_after (head, elt->prev, i);
+
+      if (elt_start_bit <= start)
+	{
+	  /* The first bit to turn on is somewhere inside this
+	     elt.  */
+	  first_word_to_mod = (start - elt_start_bit) / BITMAP_WORD_BITS;
+
+	  /* This mask should have 1s in all bits >= start position. */
+	  first_mask =
+	    (((BITMAP_WORD) 1) << ((start % BITMAP_WORD_BITS))) - 1;
+	  first_mask = ~first_mask;
+	}
+      else
+	{
+	  /* The first bit to turn on is below this start of this elt.  */
+	  first_word_to_mod = 0;
+	  first_mask = ~(BITMAP_WORD) 0;
+	}
+
+      if (elt_end_bit_plus1 <= end_bit_plus1)
+	{
+	  /* The last bit to turn on is beyond this elt.  */
+	  last_word_to_mod = BITMAP_ELEMENT_WORDS - 1;
+	  last_mask = ~(BITMAP_WORD) 0;
+	}
+      else
+	{
+	  /* The last bit to turn on is inside to this elt.  */
+	  last_word_to_mod =
+	    (end_bit_plus1 - elt_start_bit) / BITMAP_WORD_BITS;
+
+	  /* The last mask should have 1s below the end bit.  */
+	  last_mask =
+	    (((BITMAP_WORD) 1) << ((end_bit_plus1 % BITMAP_WORD_BITS))) - 1;
+	}
+
+      if (first_word_to_mod == last_word_to_mod)
+	{
+	  BITMAP_WORD mask = first_mask & last_mask;
+	  elt->bits[first_word_to_mod] |= mask;
+	}
+      else
+	{
+	  elt->bits[first_word_to_mod] |= first_mask;
+	  if (BITMAP_ELEMENT_WORDS > 2)
+	    for (ix = first_word_to_mod + 1; ix < last_word_to_mod; ix++)
+	      elt->bits[ix] = ~(BITMAP_WORD) 0;
+	  elt->bits[last_word_to_mod] |= last_mask;
+	}
+
+      elt_prev = elt;
+      elt = elt->next;
+    }
+
+  if (elt_prev)
+    {
+      head->current = elt_prev;
+      head->indx = head->current->indx;
+    }
+}
+
 /* Clear COUNT bits from START in HEAD.  */
 void
 bitmap_clear_range (bitmap head, unsigned int start, unsigned int count)
@@ -1149,8 +1247,9 @@ bitmap_clear_range (bitmap head, unsigne
 	  else
 	    {
 	      elt->bits[first_word_to_mod] &= ~first_mask;
-	      for (i = first_word_to_mod + 1; i < last_word_to_mod; i++)
-		elt->bits[i] = 0;
+	      if (BITMAP_ELEMENT_WORDS > 2)
+	        for (i = first_word_to_mod + 1; i < last_word_to_mod; i++)
+		  elt->bits[i] = 0;
 	      elt->bits[last_word_to_mod] &= ~last_mask;
 	    }
 	  for (i = 0; i < BITMAP_ELEMENT_WORDS; i++)
Index: bitmap.h
===================================================================
--- bitmap.h	(revision 123416)
+++ bitmap.h	(working copy)
@@ -131,6 +131,7 @@ extern bool bitmap_and_compl_into (bitma
 #define bitmap_compl_and(DST, A, B) bitmap_and_compl (DST, B, A)
 extern void bitmap_compl_and_into (bitmap, bitmap);
 extern void bitmap_clear_range (bitmap, unsigned int, unsigned int);
+extern void bitmap_set_range (bitmap, unsigned int, unsigned int);
 extern bool bitmap_ior (bitmap, bitmap, bitmap);
 extern bool bitmap_ior_into (bitmap, bitmap);
 extern void bitmap_xor (bitmap, bitmap, bitmap);
Index: df-problems.c
===================================================================
--- df-problems.c	(revision 123475)
+++ df-problems.c	(working copy)
@@ -178,26 +178,6 @@ df_print_bb_index (basic_block bb, FILE 
 }
 
 
-/* Return a bitmap for REGNO from the cache MAPS.  The bitmap is to
-   contain COUNT bits starting at START.  These bitmaps are not to be
-   changed since there is a cache of them.  */
-
-static inline bitmap
-df_ref_bitmap (bitmap *maps, unsigned int regno, int start, int count)
-{
-  bitmap ids = maps[regno];
-  if (!ids)
-    {
-      unsigned int i;
-      unsigned int end = start + count;;
-      ids = BITMAP_ALLOC (NULL);
-      maps[regno] = ids;
-      for (i = start; i < end; i++)
-	bitmap_set_bit (ids, i);
-    }
-  return ids;
-}
-
 
 /* Make sure that the seen_in_insn and seen_in_block sbitmaps are set
    up correctly. */
@@ -239,9 +219,7 @@ df_unset_seen (void)
    2) There are two kill sets, one if the number of uses is less or
    equal to DF_SPARSE_THRESHOLD and another if it is greater.
 
-   <= : There is a bitmap for each register, uses_sites[N], that is
-   built on demand.  This bitvector contains a 1 for each use or reg
-   N.
+   <= : Data is built directly in the kill set.
 
    > : One level of indirection is used to keep from generating long
    strings of 1 bits in the kill sets.  Bitvectors that are indexed
@@ -257,9 +235,6 @@ df_unset_seen (void)
    data structures are not accessible outside of this module.  */
 struct df_ru_problem_data
 {
-
-  bitmap *use_sites;            /* Bitmap of uses for each pseudo.  */
-  unsigned int use_sites_size;  /* Size of use_sites.  */
   /* The set of defs to regs invalidated by call.  */
   bitmap sparse_invalidated_by_call;  
   /* The set of defs to regs invalidated by call for ru.  */  
@@ -304,7 +279,6 @@ df_ru_alloc (bitmap all_blocks)
 {
   unsigned int bb_index;
   bitmap_iterator bi;
-  unsigned int reg_size = max_reg_num ();
 
   if (!df_ru->block_pool)
     df_ru->block_pool = create_alloc_pool ("df_ru_block pool", 
@@ -312,29 +286,9 @@ df_ru_alloc (bitmap all_blocks)
 
   if (df_ru->problem_data)
     {
-      unsigned int i;
       struct df_ru_problem_data *problem_data
 	= (struct df_ru_problem_data *) df_ru->problem_data;
 
-      for (i = 0; i < problem_data->use_sites_size; i++)
-	{
-	  bitmap bm = problem_data->use_sites[i];
-	  if (bm)
-	    {
-	      BITMAP_FREE (bm);
-	      problem_data->use_sites[i] = NULL;
-	    }
-	}
-      
-      if (problem_data->use_sites_size < reg_size)
-	{
-	  problem_data->use_sites 
-	    = xrealloc (problem_data->use_sites, reg_size * sizeof (bitmap));
-	  memset (problem_data->use_sites + problem_data->use_sites_size, 0,
-		  (reg_size - problem_data->use_sites_size) * sizeof (bitmap));
-	  problem_data->use_sites_size = reg_size;
-	}
-
       bitmap_clear (problem_data->sparse_invalidated_by_call);
       bitmap_clear (problem_data->dense_invalidated_by_call);
     }
@@ -343,8 +297,6 @@ df_ru_alloc (bitmap all_blocks)
       struct df_ru_problem_data *problem_data = XNEW (struct df_ru_problem_data);
       df_ru->problem_data = problem_data;
 
-      problem_data->use_sites = XCNEWVEC (bitmap, reg_size);
-      problem_data->use_sites_size = reg_size;
       problem_data->sparse_invalidated_by_call = BITMAP_ALLOC (NULL);
       problem_data->dense_invalidated_by_call = BITMAP_ALLOC (NULL);
     }
@@ -409,14 +361,7 @@ df_ru_bb_local_compute_process_def (stru
 		  if (n_uses > DF_SPARSE_THRESHOLD)
 		    bitmap_set_bit (bb_info->sparse_kill, regno);
 		  else
-		    {
-		      struct df_ru_problem_data * problem_data
-			= (struct df_ru_problem_data *)df_ru->problem_data;
-		      bitmap uses 
-			= df_ref_bitmap (problem_data->use_sites, regno, 
-				       begin, n_uses);
-		      bitmap_ior_into (bb_info->kill, uses);
-		    }
+		    bitmap_set_range (bb_info->kill, begin, n_uses);
 		}
 	      bitmap_set_bit (seen_in_insn, regno);
 	    }
@@ -530,12 +475,9 @@ df_ru_local_compute (bitmap all_blocks)
       if (DF_USES_COUNT (regno) > DF_SPARSE_THRESHOLD)
 	bitmap_set_bit (sparse_invalidated, regno);
       else
-	{
-	  bitmap defs = df_ref_bitmap (problem_data->use_sites, regno, 
-				       DF_USES_BEGIN (regno), 
-				       DF_USES_COUNT (regno));
-	  bitmap_ior_into (dense_invalidated, defs);
-	}
+	bitmap_set_range (dense_invalidated,
+			  DF_USES_BEGIN (regno), 
+			  DF_USES_COUNT (regno));
     }
 
   df_unset_seen ();
@@ -661,15 +603,6 @@ df_ru_free (void)
 	}
       
       free_alloc_pool (df_ru->block_pool);
-      
-      for (i = 0; i < problem_data->use_sites_size; i++)
-	{
-	  bitmap bm = problem_data->use_sites[i];
-	  if (bm)
-	    BITMAP_FREE (bm);
-	}
-      
-      free (problem_data->use_sites);
       BITMAP_FREE (problem_data->sparse_invalidated_by_call);
       BITMAP_FREE (problem_data->dense_invalidated_by_call);
       
@@ -798,13 +731,6 @@ df_ru_add_problem (void)
    data structures are not accessible outside of this module.  */
 struct df_rd_problem_data
 {
-  /* If the number of defs for regnum N is less than
-     DF_SPARSE_THRESHOLD, uses_sites[N] contains a mask of the all of
-     the defs of reg N indexed by the id in the ref structure.  If
-     there are more than DF_SPARSE_THRESHOLD defs for regnum N a
-     different mechanism is used to mask the def.  */
-  bitmap *def_sites;            /* Bitmap of defs for each pseudo.  */
-  unsigned int def_sites_size;  /* Size of def_sites.  */
   /* The set of defs to regs invalidated by call.  */
   bitmap sparse_invalidated_by_call;  
   /* The set of defs to regs invalidate by call for rd.  */  
@@ -850,7 +776,6 @@ df_rd_alloc (bitmap all_blocks)
 {
   unsigned int bb_index;
   bitmap_iterator bi;
-  unsigned int reg_size = max_reg_num ();
 
   if (!df_rd->block_pool)
     df_rd->block_pool = create_alloc_pool ("df_rd_block pool", 
@@ -858,29 +783,9 @@ df_rd_alloc (bitmap all_blocks)
 
   if (df_rd->problem_data)
     {
-      unsigned int i;
       struct df_rd_problem_data *problem_data
 	= (struct df_rd_problem_data *) df_rd->problem_data;
 
-      for (i = 0; i < problem_data->def_sites_size; i++)
-	{
-	  bitmap bm = problem_data->def_sites[i];
-	  if (bm)
-	    {
-	      BITMAP_FREE (bm);
-	      problem_data->def_sites[i] = NULL;
-	    }
-	}
-      
-      if (problem_data->def_sites_size < reg_size)
-	{
-	  problem_data->def_sites 
-	    = xrealloc (problem_data->def_sites, reg_size *sizeof (bitmap));
-	  memset (problem_data->def_sites + problem_data->def_sites_size, 0,
-		  (reg_size - problem_data->def_sites_size) *sizeof (bitmap));
-	  problem_data->def_sites_size = reg_size;
-	}
-
       bitmap_clear (problem_data->sparse_invalidated_by_call);
       bitmap_clear (problem_data->dense_invalidated_by_call);
     }
@@ -888,9 +793,6 @@ df_rd_alloc (bitmap all_blocks)
     {
       struct df_rd_problem_data *problem_data = XNEW (struct df_rd_problem_data);
       df_rd->problem_data = problem_data;
-
-      problem_data->def_sites = XCNEWVEC (bitmap, reg_size);
-      problem_data->def_sites_size = reg_size;
       problem_data->sparse_invalidated_by_call = BITMAP_ALLOC (NULL);
       problem_data->dense_invalidated_by_call = BITMAP_ALLOC (NULL);
     }
@@ -962,12 +864,8 @@ df_rd_bb_local_compute_process_def (stru
 			}
 		      else
 			{
-			  struct df_rd_problem_data * problem_data
-			    = (struct df_rd_problem_data *)df_rd->problem_data;
-			  bitmap defs = df_ref_bitmap (problem_data->def_sites, 
-						       regno, begin, n_defs);
-			  bitmap_ior_into (bb_info->kill, defs);
-			  bitmap_and_compl_into (bb_info->gen, defs);
+			  bitmap_set_range (bb_info->kill, begin, n_defs);
+			  bitmap_clear_range (bb_info->gen, begin, n_defs);
 			}
 		    }
 		  
@@ -1060,12 +958,9 @@ df_rd_local_compute (bitmap all_blocks)
       if (DF_DEFS_COUNT (regno) > DF_SPARSE_THRESHOLD)
 	bitmap_set_bit (sparse_invalidated, regno);
       else
-	{
-	  bitmap defs = df_ref_bitmap (problem_data->def_sites, regno, 
-				       DF_DEFS_BEGIN (regno), 
-				       DF_DEFS_COUNT (regno));
-	  bitmap_ior_into (dense_invalidated, defs);
-	}
+	bitmap_set_range (dense_invalidated, 
+			  DF_DEFS_BEGIN (regno), 
+			  DF_DEFS_COUNT (regno));
     }
   df_unset_seen ();
 }
@@ -1190,15 +1085,6 @@ df_rd_free (void)
 	}
       
       free_alloc_pool (df_rd->block_pool);
-      
-      for (i = 0; i < problem_data->def_sites_size; i++)
-	{
-	  bitmap bm = problem_data->def_sites[i];
-	  if (bm)
-	    BITMAP_FREE (bm);
-	}
-      
-      free (problem_data->def_sites);
       BITMAP_FREE (problem_data->sparse_invalidated_by_call);
       BITMAP_FREE (problem_data->dense_invalidated_by_call);