This is the mail archive of the
gcc-patches@gcc.gnu.org
mailing list for the GCC project.
[patch] sbitmap.h: Speed up EXECUTE_IF_SET_IN_SBITMAP.
- From: Kazu Hirata <kazu at cs dot umass dot edu>
- To: gcc-patches at gcc dot gnu dot org
- Date: Mon, 18 Oct 2004 17:22:13 -0400 (EDT)
- Subject: [patch] sbitmap.h: Speed up EXECUTE_IF_SET_IN_SBITMAP.
Hi,
Attached is a patch to speed up EXECUTE_IF_SET_IN_SBITMAP.
Currently, EXECUTE_IF_SET_IN_SBITMAP tests if a bit is set by using a
construct of the form:
mask = 1 << bit_num;
if ((word & mask) != 0)
CODE;
We can improve this by shifting the currently visited word to right in
every iteration like so:
word >>= 1;
if ((word & 1) != 0)
CODE;
The patch precisely implements the above improvement. Here are some
advantages over the current version.
o Two "if"s are gone, namely "if (word_ != 0)" and "if (word_ == 0)"
o "bit_num_ < SBITMAP_ELT_BITS" is replaced with "word_ != 0"
- equality comparison with 0 is often cheaper.
o no masking off like "word_ &= ~ _mask;"
- a right shift will take care of killing bits that are behind us.
o no loading of constant 1 arising from the left shift
- x86 cannot shift 1 without loading it first.
o 6 lines shorter :-)
There is no functional change.
Here is a timing for compiling preprocessed GCC sources with
cc1 -O2 -fomit-frame-pointer -march=athlon-xp -o /dev/null.
original patched
real: 521.159s 519.647s (0.290% down)
user: 485.607s 484.922s (0.141% down)
Tested on i686-pc-linux-gnu. OK to apply?
Kazu Hirata
2004-10-18 Kazu Hirata <kazu@cs.umass.edu>
* sbitmap.h (EXECUTE_IF_SET_IN_SBITMAP): Speed up by shifting
the currently visited word to right.
Index: sbitmap.h
===================================================================
RCS file: /cvs/gcc/gcc/gcc/sbitmap.h,v
retrieving revision 1.23
diff -c -r1.23 sbitmap.h
*** sbitmap.h 15 Oct 2004 14:47:11 -0000 1.23
--- sbitmap.h 18 Oct 2004 14:21:55 -0000
***************
*** 58,87 ****
/* Loop over all elements of SBITSET, starting with MIN. */
#define EXECUTE_IF_SET_IN_SBITMAP(SBITMAP, MIN, N, CODE) \
do { \
! unsigned int word_num_; \
unsigned int bit_num_ = (MIN) % (unsigned int) SBITMAP_ELT_BITS; \
unsigned int size_ = (SBITMAP)->size; \
SBITMAP_ELT_TYPE *ptr_ = (SBITMAP)->elms; \
\
! for (word_num_ = (MIN) / (unsigned int) SBITMAP_ELT_BITS; \
! word_num_ < size_; word_num_++, bit_num_ = 0) \
{ \
! SBITMAP_ELT_TYPE word_ = ptr_[word_num_]; \
! \
! if (word_ != 0) \
! for (; bit_num_ < SBITMAP_ELT_BITS; bit_num_++) \
! { \
! SBITMAP_ELT_TYPE _mask = (SBITMAP_ELT_TYPE) 1 << bit_num_; \
! \
! if ((word_ & _mask) != 0) \
! { \
! word_ &= ~ _mask; \
! (N) = word_num_ * SBITMAP_ELT_BITS + bit_num_; \
! CODE; \
! if (word_ == 0) \
! break; \
! } \
! } \
} \
} while (0)
--- 58,81 ----
/* Loop over all elements of SBITSET, starting with MIN. */
#define EXECUTE_IF_SET_IN_SBITMAP(SBITMAP, MIN, N, CODE) \
do { \
! unsigned int word_num_ = (MIN) / (unsigned int) SBITMAP_ELT_BITS; \
unsigned int bit_num_ = (MIN) % (unsigned int) SBITMAP_ELT_BITS; \
unsigned int size_ = (SBITMAP)->size; \
SBITMAP_ELT_TYPE *ptr_ = (SBITMAP)->elms; \
+ SBITMAP_ELT_TYPE word_ = ptr_[word_num_] >> bit_num_; \
\
! for (; \
! word_num_ < size_; \
! word_num_++, bit_num_ = 0, word_ = ptr_[word_num_]) \
{ \
! for (; word_ != 0; word_ >>= 1, bit_num_++) \
! { \
! if ((word_ & 1) != 0) \
! { \
! (N) = word_num_ * SBITMAP_ELT_BITS + bit_num_; \
! CODE; \
! } \
! } \
} \
} while (0)