This is the mail archive of the
gcc-patches@gcc.gnu.org
mailing list for the GCC project.
bitmap_operation change
- To: gcc-patches at gcc dot gnu dot org
- Subject: bitmap_operation change
- From: Richard Henderson <rth at cygnus dot com>
- Date: Mon, 4 Oct 1999 11:55:33 -0700
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)
{