This is the mail archive of the gcc-patches@gcc.gnu.org mailing list for the GCC project.


Index Nav: [Date Index] [Subject Index] [Author Index] [Thread Index]
Message Nav: [Date Prev] [Date Next] [Thread Prev] [Thread Next]

bitmap_operation change


More prep work for flow --

The biggest change here is bitmap_operation reports if the
destination bitmap changed in the operation.  This is a 
quick and easy way to stop propogation when there's nothing
left to do.

And for those couple of occations when that's not handy,
I also added bitmap_equal_p.


r~


        * bitmap.h (enum bitmap_bits): Add BITMAP_XOR.
        * bitmap.c (bitmap_operation): Return true iff TO changed.
        (bitmap_equal_p): New.
        (bitmap_bit_p): Tidy arithmetic.
        (debug_bitmap_file): Likewise.

Index: bitmap.h
===================================================================
RCS file: /egcs/carton/cvsfiles/egcs/gcc/bitmap.h,v
retrieving revision 1.12
diff -c -p -d -r1.12 bitmap.h
*** bitmap.h	1999/09/20 11:52:22	1.12
--- bitmap.h	1999/10/04 18:49:34
*************** typedef struct bitmap_head_def {
*** 55,61 ****
  enum bitmap_bits {
    BITMAP_AND,			/* TO = FROM1 & FROM2 */
    BITMAP_AND_COMPL,		/* TO = FROM1 & ~ FROM2 */
!   BITMAP_IOR			/* TO = FROM1 | FROM2 */
  };
  
  /* Global data */
--- 55,62 ----
  enum bitmap_bits {
    BITMAP_AND,			/* TO = FROM1 & FROM2 */
    BITMAP_AND_COMPL,		/* TO = FROM1 & ~ FROM2 */
!   BITMAP_IOR,			/* TO = FROM1 | FROM2 */
!   BITMAP_XOR			/* TO = FROM1 ^ FROM2 */
  };
  
  /* Global data */
*************** extern void bitmap_clear PROTO((bitmap))
*** 68,75 ****
  /* Copy a bitmap to another bitmap. */
  extern void bitmap_copy PROTO((bitmap, bitmap));
  
  /* Perform an operation on two bitmaps, yielding a third.  */
! extern void bitmap_operation PROTO((bitmap, bitmap, bitmap, enum bitmap_bits));
  
  /* `or' into one bitmap the `and' of a second bitmap witih the complement
     of a third.  */
--- 69,79 ----
  /* Copy a bitmap to another bitmap. */
  extern void bitmap_copy PROTO((bitmap, bitmap));
  
+ /* True if two bitmaps are identical.  */
+ extern int bitmap_equal_p PROTO((bitmap, bitmap));
+ 
  /* Perform an operation on two bitmaps, yielding a third.  */
! extern int bitmap_operation PROTO((bitmap, bitmap, bitmap, enum bitmap_bits));
  
  /* `or' into one bitmap the `and' of a second bitmap witih the complement
     of a third.  */
Index: bitmap.c
===================================================================
RCS file: /egcs/carton/cvsfiles/egcs/gcc/bitmap.c,v
retrieving revision 1.17
diff -c -p -d -r1.17 bitmap.c
*** bitmap.c	1999/10/03 17:01:59	1.17
--- bitmap.c	1999/10/04 18:49:34
*************** bitmap_bit_p (head, bit)
*** 382,425 ****
    word_num
      = ((bit / (unsigned) HOST_BITS_PER_WIDE_INT) % BITMAP_ELEMENT_WORDS);
  
!   return
!     (ptr->bits[word_num] & (((unsigned HOST_WIDE_INT) 1) << bit_num)) != 0;
  }
  
! /* Store in bitmap TO the result of combining bitmap FROM1 and
!    FROM2 using a specific bit manipulation.  */
  
! void
  bitmap_operation (to, from1, from2, operation)
       bitmap to;
       bitmap from1;
       bitmap from2;
       enum bitmap_bits operation;
  {
-   bitmap_element *delete_list = 0;
    bitmap_element *from1_ptr = from1->first;
    bitmap_element *from2_ptr = from2->first;
!   unsigned int indx1
!     = (from1_ptr) ? from1_ptr->indx : ~ (unsigned HOST_WIDE_INT) 0;
!   unsigned int indx2
!     = (from2_ptr) ? from2_ptr->indx : ~ (unsigned HOST_WIDE_INT) 0;
!   bitmap_element *to_ptr = 0;
    bitmap_element *from1_tmp;
    bitmap_element *from2_tmp;
    unsigned int indx;
! #if BITMAP_ELEMENT_WORDS != 2
!   int i;
  #endif
  
!   /* To simplify things, always create a new list.  If the old list was one
!      of the inputs, free it later.  Otherwise, free it now.  */
!   if (to == from1 || to == from2)
!     {
!       delete_list = to->first;
!       to->first = to->current = 0;
!     }
!   else
!     bitmap_clear (to);
  
    while (from1_ptr != 0 || from2_ptr != 0)
      {
--- 382,443 ----
    word_num
      = ((bit / (unsigned) HOST_BITS_PER_WIDE_INT) % BITMAP_ELEMENT_WORDS);
  
!   return (ptr->bits[word_num] >> bit_num) & 1;
  }
  
! /* Store in bitmap TO the result of combining bitmap FROM1 and FROM2 using
!    a specific bit manipulation.  Return true if TO changes.  */
  
! int
  bitmap_operation (to, from1, from2, operation)
       bitmap to;
       bitmap from1;
       bitmap from2;
       enum bitmap_bits operation;
  {
    bitmap_element *from1_ptr = from1->first;
    bitmap_element *from2_ptr = from2->first;
!   unsigned int indx1 = (from1_ptr) ? from1_ptr->indx : -1;
!   unsigned int indx2 = (from2_ptr) ? from2_ptr->indx : -1;
!   bitmap_element *to_ptr = to->first;
    bitmap_element *from1_tmp;
    bitmap_element *from2_tmp;
+   bitmap_element *to_tmp;
    unsigned int indx;
!   int changed = 0;
! 
! #if BITMAP_ELEMENT_WORDS == 2
! #define DOIT(OP)					\
!   do {							\
!     unsigned HOST_WIDE_INT t0, t1, f10, f11, f20, f21;	\
!     f10 = from1_tmp->bits[0];				\
!     f20 = from2_tmp->bits[0];				\
!     t0 = f10 OP f20;					\
!     changed |= (t0 != to_tmp->bits[0]);			\
!     f11 = from1_tmp->bits[1];				\
!     f21 = from2_tmp->bits[1];				\
!     t1 = f11 OP f21;					\
!     changed |= (t1 != to_tmp->bits[1]);			\
!     to_tmp->bits[0] = t0;				\
!     to_tmp->bits[1] = t1;				\
!   } while (0)
! #else
! #define DOIT(OP)					\
!   do {							\
!     unsigned HOST_WIDE_INT t, f1, f2;			\
!     int i;						\
!     for (i = 0; i < BITMAP_ELEMENT_WORDS; ++i)		\
!       {							\
! 	f1 = from1_tmp->bits[i];			\
! 	f2 = from2_tmp->bits[i];			\
! 	t = f1 OP f2;					\
! 	changed |= (t != to_tmp->bits[i]);		\
! 	to_tmp->bits[i] = t;				\
!       }							\
!   } while (0)
  #endif
  
!   to->first = to->current = 0;
  
    while (from1_ptr != 0 || from2_ptr != 0)
      {
*************** bitmap_operation (to, from1, from2, oper
*** 431,439 ****
  	  from1_tmp = from1_ptr;
  	  from2_tmp = from2_ptr;
  	  from1_ptr = from1_ptr->next;
! 	  indx1 = (from1_ptr) ? from1_ptr->indx : ~ (unsigned HOST_WIDE_INT) 0;
  	  from2_ptr = from2_ptr->next;
! 	  indx2 = (from2_ptr) ? from2_ptr->indx : ~ (unsigned HOST_WIDE_INT) 0;
  	}
        else if (indx1 < indx2)
  	{
--- 449,457 ----
  	  from1_tmp = from1_ptr;
  	  from2_tmp = from2_ptr;
  	  from1_ptr = from1_ptr->next;
! 	  indx1 = (from1_ptr) ? from1_ptr->indx : -1;
  	  from2_ptr = from2_ptr->next;
! 	  indx2 = (from2_ptr) ? from2_ptr->indx : -1;
  	}
        else if (indx1 < indx2)
  	{
*************** bitmap_operation (to, from1, from2, oper
*** 441,447 ****
  	  from1_tmp = from1_ptr;
  	  from2_tmp = &bitmap_zero;
  	  from1_ptr = from1_ptr->next;
! 	  indx1 = (from1_ptr) ? from1_ptr->indx : ~ (unsigned HOST_WIDE_INT) 0;
  	}
        else
  	{
--- 459,465 ----
  	  from1_tmp = from1_ptr;
  	  from2_tmp = &bitmap_zero;
  	  from1_ptr = from1_ptr->next;
! 	  indx1 = (from1_ptr) ? from1_ptr->indx : -1;
  	}
        else
  	{
*************** bitmap_operation (to, from1, from2, oper
*** 449,459 ****
  	  from1_tmp = &bitmap_zero;
  	  from2_tmp = from2_ptr;
  	  from2_ptr = from2_ptr->next;
! 	  indx2 = (from2_ptr) ? from2_ptr->indx : ~ (unsigned HOST_WIDE_INT) 0;
  	}
  
!       if (to_ptr == 0)
! 	to_ptr = bitmap_element_allocate ();
  
        /* Do the operation, and if any bits are set, link it into the
  	 linked list.  */
--- 467,492 ----
  	  from1_tmp = &bitmap_zero;
  	  from2_tmp = from2_ptr;
  	  from2_ptr = from2_ptr->next;
! 	  indx2 = (from2_ptr) ? from2_ptr->indx : -1;
  	}
  
!       /* Find the appropriate element from TO.  Begin by discarding
! 	 elements that we've skipped. */
!       while (to_ptr && to_ptr->indx < indx)
! 	{
! 	  changed = 1;
! 	  to_tmp = to_ptr;
! 	  to_ptr = to_ptr->next;
! 	  to_tmp = bitmap_free;
! 	  bitmap_free = to_tmp;
! 	}
!       if (to_ptr && to_ptr->indx == indx)
! 	{
! 	  to_tmp = to_ptr;
! 	  to_ptr = to_ptr->next;
! 	}
!       else
! 	to_tmp = bitmap_element_allocate ();
  
        /* Do the operation, and if any bits are set, link it into the
  	 linked list.  */
*************** bitmap_operation (to, from1, from2, oper
*** 463,523 ****
  	  abort ();
  
  	case BITMAP_AND:
! #if BITMAP_ELEMENT_WORDS == 2
! 	  to_ptr->bits[0] = from1_tmp->bits[0] & from2_tmp->bits[0];
! 	  to_ptr->bits[1] = from1_tmp->bits[1] & from2_tmp->bits[1];
! #else
! 	  for (i = BITMAP_ELEMENT_WORDS - 1; i >= 0; i--)
! 	    to_ptr->bits[i] = from1_tmp->bits[i] & from2_tmp->bits[i];
! #endif
  	  break;
  
  	case BITMAP_AND_COMPL:
! #if BITMAP_ELEMENT_WORDS == 2
! 	  to_ptr->bits[0] = from1_tmp->bits[0] & ~ from2_tmp->bits[0];
! 	  to_ptr->bits[1] = from1_tmp->bits[1] & ~ from2_tmp->bits[1];
! #else
! 	  for (i = BITMAP_ELEMENT_WORDS - 1; i >= 0; i--)
! 	    to_ptr->bits[i] = from1_tmp->bits[i] & ~ from2_tmp->bits[i];
! #endif
  	  break;
  
  	case BITMAP_IOR:
! #if BITMAP_ELEMENT_WORDS == 2
! 	  to_ptr->bits[0] = from1_tmp->bits[0] | from2_tmp->bits[0];
! 	  to_ptr->bits[1] = from1_tmp->bits[1] | from2_tmp->bits[1];
! #else
! 	  for (i = BITMAP_ELEMENT_WORDS - 1; i >= 0; i--)
! 	    to_ptr->bits[i] = from1_tmp->bits[i] | from2_tmp->bits[i];
! #endif
  	  break;
  	}
  
!       if (! bitmap_element_zerop (to_ptr))
  	{
! 	  to_ptr->indx = indx;
! 	  bitmap_element_link (to, to_ptr);
! 	  to_ptr = 0;
  	}
      }
  
!   /* If we have an unallocated element due to the last element being 0,
!      release it back to the free pool.  Don't bother calling
!      bitmap_element_free since it was never linked into a bitmap.  */
!   if (to_ptr != 0)
      {
!       to_ptr->next = bitmap_free;
        bitmap_free = to_ptr;
      }
  
!   /* If the output bitmap was one of the inputs, free up its
!      elements now that we're done.  */
!   for (; delete_list != 0; delete_list = to_ptr)
!     {
!       to_ptr = delete_list->next;
!       delete_list->next = bitmap_free;
!       bitmap_free = delete_list;
!     }
  }
  
  /* Or into bitmap TO bitmap FROM1 and'ed with the complement of
--- 496,554 ----
  	  abort ();
  
  	case BITMAP_AND:
! 	  DOIT (&);
  	  break;
  
  	case BITMAP_AND_COMPL:
! 	  DOIT (&~);
  	  break;
  
  	case BITMAP_IOR:
! 	  DOIT (|);
! 	  break;
! 
! 	case BITMAP_XOR:
! 	  DOIT (^);
  	  break;
  	}
  
!       if (! bitmap_element_zerop (to_tmp))
  	{
! 	  to_tmp->indx = indx;
! 	  bitmap_element_link (to, to_tmp);
  	}
      }
  
!   /* If we have elements of TO left over, free the lot.  */
!   if (to_ptr)
      {
!       changed = 1;
!       for (to_tmp = to_ptr; to_tmp->next ; to_tmp = to_tmp->next)
! 	continue;
!       to_tmp->next = bitmap_free;
        bitmap_free = to_ptr;
      }
  
! #undef DOIT
! 
!   return changed;
! }
! 
! /* Return true if two bitmaps are identical.  */
! 
! int
! bitmap_equal_p (a, b)
!      bitmap a;
!      bitmap b;
! {
!   bitmap_head c;
!   int ret;
! 
!   c.first = c.current = 0;
!   ret = ! bitmap_operation (&c, a, b, BITMAP_XOR);
!   bitmap_clear (&c);
! 
!   return ret;
  }
  
  /* Or into bitmap TO bitmap FROM1 and'ed with the complement of
*************** debug_bitmap_file (file, head)
*** 578,584 ****
  
        for (i = 0; i < BITMAP_ELEMENT_WORDS; i++)
  	for (j = 0; j < HOST_BITS_PER_WIDE_INT; j++)
! 	  if ((ptr->bits[i] & (((unsigned HOST_WIDE_INT) 1) << j)) != 0)
  	    {
  	      if (col > 70)
  		{
--- 609,615 ----
  
        for (i = 0; i < BITMAP_ELEMENT_WORDS; i++)
  	for (j = 0; j < HOST_BITS_PER_WIDE_INT; j++)
! 	  if ((ptr->bits[i] >> j) & 1)
  	    {
  	      if (col > 70)
  		{


Index Nav: [Date Index] [Subject Index] [Author Index] [Thread Index]
Message Nav: [Date Prev] [Date Next] [Thread Prev] [Thread Next]