This is the mail archive of the
gcc-patches@gcc.gnu.org
mailing list for the GCC project.
speed up bitmap.c
- From: Segher Boessenkool <segher at koffie dot nl>
- To: gcc-patches at gcc dot gnu dot org
- Date: Thu, 09 Jan 2003 21:05:26 +0100
- Subject: speed up bitmap.c
Hi,
HOST_WIDE_INT is DImode on some (most?) platforms; SImode is usually
faster (and hopefully never slower). This patch changes bitmap.[ch] to
use unsigned long instead of HOST_WIDE_INT. It helps about five percent
on compilation time on "typical" C files; tested on powerpc-unknown-linux-gnu.
2003-01-08 Segher Boessenkool <segher@koffie.nl>
* bitmap.h (BITMAP_WORD): New typedef: fundamental storage
type for bitmaps. Use unsigned long.
(nBITMAP_WORD_BITS): New macro.
(BITMAP_WORD_BITS): New macro.
(rest of file): Use it.
* bitmap.c: Use it.
*** bitmap.h.orig Wed Jan 8 00:11:48 2003
--- bitmap.h Wed Jan 8 15:33:32 2003
***************
*** 1,5 ****
/* Functions to support general ended bitmaps.
! Copyright (C) 1997, 1998, 1999, 2000, 2001, 2002
Free Software Foundation, Inc.
This file is part of GCC.
--- 1,5 ----
/* Functions to support general ended bitmaps.
! Copyright (C) 1997, 1998, 1999, 2000, 2001, 2002, 2003
Free Software Foundation, Inc.
This file is part of GCC.
*************** Software Foundation, 59 Temple Place - S
*** 22,31 ****
#ifndef GCC_BITMAP_H
#define GCC_BITMAP_H
/* Number of words to use for each element in the linked list. */
#ifndef BITMAP_ELEMENT_WORDS
! #define BITMAP_ELEMENT_WORDS 2
#endif
/* Number of bits in each actual element of a bitmap. We get slightly better
--- 22,39 ----
#ifndef GCC_BITMAP_H
#define GCC_BITMAP_H
+ /* Fundamental storage type for bitmap. */
+
+ /* typedef unsigned HOST_WIDE_INT BITMAP_WORD; */
+ /* #define nBITMAP_WORD_BITS HOST_BITS_PER_WIDE_INT */
+ typedef unsigned long BITMAP_WORD;
+ #define nBITMAP_WORD_BITS (CHAR_BIT * SIZEOF_LONG)
+ #define BITMAP_WORD_BITS (unsigned) nBITMAP_WORD_BITS
+
/* Number of words to use for each element in the linked list. */
#ifndef BITMAP_ELEMENT_WORDS
! #define BITMAP_ELEMENT_WORDS ((128 + nBITMAP_WORD_BITS - 1) / nBITMAP_WORD_BITS)
#endif
/* Number of bits in each actual element of a bitmap. We get slightly better
*************** Software Foundation, 59 Temple Place - S
*** 33,39 ****
bits is unsigned, assuming it is a power of 2. */
#define BITMAP_ELEMENT_ALL_BITS \
! ((unsigned) (BITMAP_ELEMENT_WORDS * HOST_BITS_PER_WIDE_INT))
/* Bitmap set element. We use a linked list to hold only the bits that
are set. This allows for use to grow the bitset dynamically without
--- 41,47 ----
bits is unsigned, assuming it is a power of 2. */
#define BITMAP_ELEMENT_ALL_BITS \
! ((unsigned) (BITMAP_ELEMENT_WORDS * BITMAP_WORD_BITS))
/* Bitmap set element. We use a linked list to hold only the bits that
are set. This allows for use to grow the bitset dynamically without
*************** typedef struct bitmap_element_def GTY(()
*** 45,51 ****
struct bitmap_element_def *next; /* Next element. */
struct bitmap_element_def *prev; /* Previous element. */
unsigned int indx; /* regno/BITMAP_ELEMENT_ALL_BITS. */
! unsigned HOST_WIDE_INT bits[BITMAP_ELEMENT_WORDS]; /* Bits that are set. */
} bitmap_element;
/* Head of bitmap linked list. */
--- 53,59 ----
struct bitmap_element_def *next; /* Next element. */
struct bitmap_element_def *prev; /* Previous element. */
unsigned int indx; /* regno/BITMAP_ELEMENT_ALL_BITS. */
! BITMAP_WORD bits[BITMAP_ELEMENT_WORDS]; /* Bits that are set. */
} bitmap_element;
/* Head of bitmap linked list. */
*************** do { \
*** 162,170 ****
do { \
bitmap_element *ptr_ = (BITMAP)->first; \
unsigned int indx_ = (MIN) / BITMAP_ELEMENT_ALL_BITS; \
! unsigned bit_num_ = (MIN) % ((unsigned) HOST_BITS_PER_WIDE_INT); \
! unsigned word_num_ = (((MIN) / ((unsigned) HOST_BITS_PER_WIDE_INT)) \
! % BITMAP_ELEMENT_WORDS); \
\
\
/* Find the block the minimum bit is in. */ \
--- 170,177 ----
do { \
bitmap_element *ptr_ = (BITMAP)->first; \
unsigned int indx_ = (MIN) / BITMAP_ELEMENT_ALL_BITS; \
! unsigned bit_num_ = (MIN) % BITMAP_WORD_BITS; \
! unsigned word_num_ = (MIN) / BITMAP_WORD_BITS % BITMAP_ELEMENT_WORDS; \
\
\
/* Find the block the minimum bit is in. */ \
*************** do { \
*** 181,200 ****
{ \
for (; word_num_ < BITMAP_ELEMENT_WORDS; word_num_++) \
{ \
! unsigned HOST_WIDE_INT word_ = ptr_->bits[word_num_]; \
\
if (word_ != 0) \
{ \
! for (; bit_num_ < HOST_BITS_PER_WIDE_INT; bit_num_++) \
{ \
! unsigned HOST_WIDE_INT mask_ \
! = ((unsigned HOST_WIDE_INT) 1) << bit_num_; \
\
if ((word_ & mask_) != 0) \
{ \
word_ &= ~ mask_; \
(BITNUM) = (ptr_->indx * BITMAP_ELEMENT_ALL_BITS \
! + word_num_ * HOST_BITS_PER_WIDE_INT \
+ bit_num_); \
CODE; \
\
--- 188,206 ----
{ \
for (; word_num_ < BITMAP_ELEMENT_WORDS; word_num_++) \
{ \
! BITMAP_WORD word_ = ptr_->bits[word_num_]; \
\
if (word_ != 0) \
{ \
! for (; bit_num_ < BITMAP_WORD_BITS; bit_num_++) \
{ \
! BITMAP_WORD mask_ = ((BITMAP_WORD) 1) << bit_num_; \
\
if ((word_ & mask_) != 0) \
{ \
word_ &= ~ mask_; \
(BITNUM) = (ptr_->indx * BITMAP_ELEMENT_ALL_BITS \
! + word_num_ * BITMAP_WORD_BITS \
+ bit_num_); \
CODE; \
\
*************** do { \
*** 220,228 ****
bitmap_element *ptr1_ = (BITMAP1)->first; \
bitmap_element *ptr2_ = (BITMAP2)->first; \
unsigned int indx_ = (MIN) / BITMAP_ELEMENT_ALL_BITS; \
! unsigned bit_num_ = (MIN) % ((unsigned) HOST_BITS_PER_WIDE_INT); \
! unsigned word_num_ = (((MIN) / ((unsigned) HOST_BITS_PER_WIDE_INT)) \
! % BITMAP_ELEMENT_WORDS); \
\
/* Find the block the minimum bit is in in the first bitmap. */ \
while (ptr1_ != 0 && ptr1_->indx < indx_) \
--- 226,233 ----
bitmap_element *ptr1_ = (BITMAP1)->first; \
bitmap_element *ptr2_ = (BITMAP2)->first; \
unsigned int indx_ = (MIN) / BITMAP_ELEMENT_ALL_BITS; \
! unsigned bit_num_ = (MIN) % BITMAP_WORD_BITS; \
! unsigned word_num_ = (MIN) / BITMAP_WORD_BITS % BITMAP_ELEMENT_WORDS; \
\
/* Find the block the minimum bit is in in the first bitmap. */ \
while (ptr1_ != 0 && ptr1_->indx < indx_) \
*************** do { \
*** 248,267 ****
\
for (; word_num_ < BITMAP_ELEMENT_WORDS; word_num_++) \
{ \
! unsigned HOST_WIDE_INT word_ = (ptr1_->bits[word_num_] \
! & ~ tmp2_->bits[word_num_]); \
if (word_ != 0) \
{ \
! for (; bit_num_ < HOST_BITS_PER_WIDE_INT; bit_num_++) \
{ \
! unsigned HOST_WIDE_INT mask_ \
! = ((unsigned HOST_WIDE_INT)1) << bit_num_; \
\
if ((word_ & mask_) != 0) \
{ \
word_ &= ~ mask_; \
(BITNUM) = (ptr1_->indx * BITMAP_ELEMENT_ALL_BITS \
! + word_num_ * HOST_BITS_PER_WIDE_INT \
+ bit_num_); \
\
CODE; \
--- 253,271 ----
\
for (; word_num_ < BITMAP_ELEMENT_WORDS; word_num_++) \
{ \
! BITMAP_WORD word_ = (ptr1_->bits[word_num_] \
! & ~ tmp2_->bits[word_num_]); \
if (word_ != 0) \
{ \
! for (; bit_num_ < BITMAP_WORD_BITS; bit_num_++) \
{ \
! BITMAP_WORD mask_ = ((BITMAP_WORD) 1) << bit_num_; \
\
if ((word_ & mask_) != 0) \
{ \
word_ &= ~ mask_; \
(BITNUM) = (ptr1_->indx * BITMAP_ELEMENT_ALL_BITS \
! + word_num_ * BITMAP_WORD_BITS \
+ bit_num_); \
\
CODE; \
*************** do { \
*** 287,295 ****
bitmap_element *ptr1_ = (BITMAP1)->first; \
bitmap_element *ptr2_ = (BITMAP2)->first; \
unsigned int indx_ = (MIN) / BITMAP_ELEMENT_ALL_BITS; \
! unsigned bit_num_ = (MIN) % ((unsigned) HOST_BITS_PER_WIDE_INT); \
! unsigned word_num_ = (((MIN) / ((unsigned) HOST_BITS_PER_WIDE_INT)) \
! % BITMAP_ELEMENT_WORDS); \
\
/* Find the block the minimum bit is in in the first bitmap. */ \
while (ptr1_ != 0 && ptr1_->indx < indx_) \
--- 291,298 ----
bitmap_element *ptr1_ = (BITMAP1)->first; \
bitmap_element *ptr2_ = (BITMAP2)->first; \
unsigned int indx_ = (MIN) / BITMAP_ELEMENT_ALL_BITS; \
! unsigned bit_num_ = (MIN) % BITMAP_WORD_BITS; \
! unsigned word_num_ = (MIN) / BITMAP_WORD_BITS % BITMAP_ELEMENT_WORDS; \
\
/* Find the block the minimum bit is in in the first bitmap. */ \
while (ptr1_ != 0 && ptr1_->indx < indx_) \
*************** do { \
*** 321,340 ****
\
for (; word_num_ < BITMAP_ELEMENT_WORDS; word_num_++) \
{ \
! unsigned HOST_WIDE_INT word_ = (ptr1_->bits[word_num_] \
! & ptr2_->bits[word_num_]); \
if (word_ != 0) \
{ \
! for (; bit_num_ < HOST_BITS_PER_WIDE_INT; bit_num_++) \
{ \
! unsigned HOST_WIDE_INT mask_ \
! = ((unsigned HOST_WIDE_INT)1) << bit_num_; \
\
if ((word_ & mask_) != 0) \
{ \
word_ &= ~ mask_; \
(BITNUM) = (ptr1_->indx * BITMAP_ELEMENT_ALL_BITS \
! + word_num_ * HOST_BITS_PER_WIDE_INT \
+ bit_num_); \
\
CODE; \
--- 324,342 ----
\
for (; word_num_ < BITMAP_ELEMENT_WORDS; word_num_++) \
{ \
! BITMAP_WORD word_ = (ptr1_->bits[word_num_] \
! & ptr2_->bits[word_num_]); \
if (word_ != 0) \
{ \
! for (; bit_num_ < BITMAP_WORD_BITS; bit_num_++) \
{ \
! BITMAP_WORD mask_ = ((BITMAP_WORD) 1) << bit_num_; \
\
if ((word_ & mask_) != 0) \
{ \
word_ &= ~ mask_; \
(BITNUM) = (ptr1_->indx * BITMAP_ELEMENT_ALL_BITS \
! + word_num_ * BITMAP_WORD_BITS \
+ bit_num_); \
\
CODE; \
*** bitmap.c.orig Wed Jan 8 00:11:57 2003
--- bitmap.c Wed Jan 8 15:33:43 2003
***************
*** 1,5 ****
/* Functions to support general ended bitmaps.
! Copyright (C) 1997, 1998, 1999, 2000, 2001 Free Software Foundation, Inc.
This file is part of GCC.
--- 1,6 ----
/* Functions to support general ended bitmaps.
! Copyright (C) 1997, 1998, 1999, 2000, 2001, 2003
! Free Software Foundation, Inc.
This file is part of GCC.
*************** bitmap_find_bit (head, bit)
*** 330,336 ****
unsigned int bit;
{
bitmap_element *element;
! unsigned HOST_WIDE_INT indx = bit / BITMAP_ELEMENT_ALL_BITS;
if (head->current == 0
|| head->indx == indx)
--- 331,337 ----
unsigned int bit;
{
bitmap_element *element;
! unsigned int indx = bit / BITMAP_ELEMENT_ALL_BITS;
if (head->current == 0
|| head->indx == indx)
*************** bitmap_clear_bit (head, bit)
*** 369,378 ****
if (ptr != 0)
{
! unsigned bit_num = bit % (unsigned) HOST_BITS_PER_WIDE_INT;
! unsigned word_num = ((bit / (unsigned) HOST_BITS_PER_WIDE_INT)
! % BITMAP_ELEMENT_WORDS);
! ptr->bits[word_num] &= ~ (((unsigned HOST_WIDE_INT) 1) << bit_num);
/* If we cleared the entire word, free up the element */
if (bitmap_element_zerop (ptr))
--- 370,378 ----
if (ptr != 0)
{
! unsigned bit_num = bit % BITMAP_WORD_BITS;
! unsigned word_num = bit / BITMAP_WORD_BITS % BITMAP_ELEMENT_WORDS;
! ptr->bits[word_num] &= ~ (((BITMAP_WORD) 1) << bit_num);
/* If we cleared the entire word, free up the element */
if (bitmap_element_zerop (ptr))
*************** bitmap_set_bit (head, bit)
*** 388,397 ****
int bit;
{
bitmap_element *ptr = bitmap_find_bit (head, bit);
! unsigned word_num
! = ((bit / (unsigned) HOST_BITS_PER_WIDE_INT) % BITMAP_ELEMENT_WORDS);
! unsigned bit_num = bit % (unsigned) HOST_BITS_PER_WIDE_INT;
! unsigned HOST_WIDE_INT bit_val = ((unsigned HOST_WIDE_INT) 1) << bit_num;
if (ptr == 0)
{
--- 388,396 ----
int bit;
{
bitmap_element *ptr = bitmap_find_bit (head, bit);
! unsigned word_num = bit / BITMAP_WORD_BITS % BITMAP_ELEMENT_WORDS;
! unsigned bit_num = bit % BITMAP_WORD_BITS;
! BITMAP_WORD bit_val = ((BITMAP_WORD) 1) << bit_num;
if (ptr == 0)
{
*************** bitmap_bit_p (head, bit)
*** 419,427 ****
if (ptr == 0)
return 0;
! bit_num = bit % (unsigned) HOST_BITS_PER_WIDE_INT;
! word_num
! = ((bit / (unsigned) HOST_BITS_PER_WIDE_INT) % BITMAP_ELEMENT_WORDS);
return (ptr->bits[word_num] >> bit_num) & 1;
}
--- 418,425 ----
if (ptr == 0)
return 0;
! bit_num = bit % BITMAP_WORD_BITS;
! word_num = bit / BITMAP_WORD_BITS % BITMAP_ELEMENT_WORDS;
return (ptr->bits[word_num] >> bit_num) & 1;
}
*************** bitmap_first_set_bit (a)
*** 434,440 ****
bitmap a;
{
bitmap_element *ptr = a->first;
! unsigned HOST_WIDE_INT word;
unsigned word_num, bit_num;
if (ptr == NULL)
--- 432,438 ----
bitmap a;
{
bitmap_element *ptr = a->first;
! BITMAP_WORD word;
unsigned word_num, bit_num;
if (ptr == NULL)
*************** bitmap_first_set_bit (a)
*** 456,465 ****
bit_num = 0;
word = word & -word;
! #if HOST_BITS_PER_WIDE_INT > 64
#error "Fill out the table."
#endif
! #if HOST_BITS_PER_WIDE_INT > 32
if ((word & 0xffffffff) == 0)
word >>= 32, bit_num += 32;
#endif
--- 454,463 ----
bit_num = 0;
word = word & -word;
! #if nBITMAP_WORD_BITS > 64
#error "Fill out the table."
#endif
! #if nBITMAP_WORD_BITS > 32
if ((word & 0xffffffff) == 0)
word >>= 32, bit_num += 32;
#endif
*************** bitmap_first_set_bit (a)
*** 475,481 ****
bit_num += 1;
return (ptr->indx * BITMAP_ELEMENT_ALL_BITS
! + word_num * HOST_BITS_PER_WIDE_INT
+ bit_num);
}
--- 473,479 ----
bit_num += 1;
return (ptr->indx * BITMAP_ELEMENT_ALL_BITS
! + word_num * BITMAP_WORD_BITS
+ bit_num);
}
*************** bitmap_last_set_bit (a)
*** 487,493 ****
bitmap a;
{
bitmap_element *ptr = a->first;
! unsigned HOST_WIDE_INT word;
unsigned word_num, bit_num;
if (ptr == NULL)
--- 485,491 ----
bitmap a;
{
bitmap_element *ptr = a->first;
! BITMAP_WORD word;
unsigned word_num, bit_num;
if (ptr == NULL)
*************** bitmap_last_set_bit (a)
*** 509,519 ****
/* Binary search for the last set bit. */
bit_num = 0;
! #if HOST_BITS_PER_WIDE_INT > 64
#error "Fill out the table."
#endif
! #if HOST_BITS_PER_WIDE_INT > 32
! if (word & ~ (unsigned HOST_WIDE_INT) 0xffffffff)
word >>= 32, bit_num += 32;
#endif
if (word & 0xffff0000)
--- 507,517 ----
/* Binary search for the last set bit. */
bit_num = 0;
! #if nBITMAP_WORD_BITS > 64
#error "Fill out the table."
#endif
! #if nBITMAP_WORD_BITS > 32
! if (word & ~0xffffffff)
word >>= 32, bit_num += 32;
#endif
if (word & 0xffff0000)
*************** bitmap_last_set_bit (a)
*** 528,534 ****
bit_num += 1;
return (ptr->indx * BITMAP_ELEMENT_ALL_BITS
! + word_num * HOST_BITS_PER_WIDE_INT
+ bit_num);
}
--- 526,532 ----
bit_num += 1;
return (ptr->indx * BITMAP_ELEMENT_ALL_BITS
! + word_num * BITMAP_WORD_BITS
+ bit_num);
}
*************** bitmap_operation (to, from1, from2, oper
*** 558,564 ****
#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; \
--- 556,562 ----
#if BITMAP_ELEMENT_WORDS == 2
#define DOIT(OP) \
do { \
! BITMAP_WORD t0, t1, f10, f11, f20, f21; \
f10 = from1_tmp->bits[0]; \
f20 = from2_tmp->bits[0]; \
t0 = f10 OP f20; \
*************** bitmap_operation (to, from1, from2, oper
*** 573,579 ****
#else
#define DOIT(OP) \
do { \
! unsigned HOST_WIDE_INT t, f1, f2; \
int i; \
for (i = 0; i < BITMAP_ELEMENT_WORDS; ++i) \
{ \
--- 571,577 ----
#else
#define DOIT(OP) \
do { \
! BITMAP_WORD t, f1, f2; \
int i; \
for (i = 0; i < BITMAP_ELEMENT_WORDS; ++i) \
{ \
*************** debug_bitmap_file (file, head)
*** 785,791 ****
for (ptr = head->first; ptr; ptr = ptr->next)
{
! int i, j, col = 26;
fprintf (file, "\t");
fprintf (file, HOST_PTR_PRINTF, (PTR) ptr);
--- 783,789 ----
for (ptr = head->first; ptr; ptr = ptr->next)
{
! unsigned int i, j, col = 26;
fprintf (file, "\t");
fprintf (file, HOST_PTR_PRINTF, (PTR) ptr);
*************** debug_bitmap_file (file, head)
*** 796,802 ****
fprintf (file, " indx = %u\n\t\tbits = {", ptr->indx);
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)
--- 794,800 ----
fprintf (file, " indx = %u\n\t\tbits = {", ptr->indx);
for (i = 0; i < BITMAP_ELEMENT_WORDS; i++)
! for (j = 0; j < BITMAP_WORD_BITS; j++)
if ((ptr->bits[i] >> j) & 1)
{
if (col > 70)
*************** debug_bitmap_file (file, head)
*** 806,812 ****
}
fprintf (file, " %u", (ptr->indx * BITMAP_ELEMENT_ALL_BITS
! + i * HOST_BITS_PER_WIDE_INT + j));
col += 4;
}
--- 804,810 ----
}
fprintf (file, " %u", (ptr->indx * BITMAP_ELEMENT_ALL_BITS
! + i * BITMAP_WORD_BITS + j));
col += 4;
}