This is the mail archive of the
gcc-patches@gcc.gnu.org
mailing list for the GCC project.
Re: [patch] sbitmap.h: Speed up EXECUTE_IF_SET_IN_SBITMAP.
Hi Richard,
> > 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_]; \
> [...]
> > + SBITMAP_ELT_TYPE word_ = ptr_[word_num_] >> bit_num_; \
>
> Previously, setting MIN arbitrarily large would not read from PTR;
> now it does. I think this is a faulty translation of this function.
oops. I found another problem of accessing PTR beyond its end. Note
that I check for the end condition *after* I increment word_num and
get a new word_ like so.
for (; \
word_num_ < size_; \
word_num_++, bit_num_ = 0, word_ = ptr_[word_num_]) \
I'll be testing the patch below shortly. The end result is a bit
ugly, but there shouldn't be any performance loss. OK to apply if
testing passes?
Kazu Hirata
2004-10-19 Kazu Hirata <kazu@cs.umass.edu>
* sbitmap.h (EXECUTE_IF_SET_IN_SBITMAP): Don't access PTR
beyond its end.
Index: sbitmap.h
===================================================================
RCS file: /cvs/gcc/gcc/gcc/sbitmap.h,v
retrieving revision 1.24
diff -c -r1.24 sbitmap.h
*** sbitmap.h 18 Oct 2004 23:56:18 -0000 1.24
--- sbitmap.h 20 Oct 2004 02:06:38 -0000
***************
*** 62,80 ****
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)
--- 62,87 ----
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_; \
\
! if (word_num_ < size_) \
{ \
! word_ = ptr_[word_num_] >> bit_num_; \
! \
! while (1) \
{ \
! for (; word_ != 0; word_ >>= 1, bit_num_++) \
{ \
! if ((word_ & 1) != 0) \
! { \
! (N) = word_num_ * SBITMAP_ELT_BITS + bit_num_; \
! CODE; \
! } \
} \
+ word_num_++; \
+ if (word_num_ >= size_) \
+ break; \
+ bit_num_ = 0, word_ = ptr_[word_num_]; \
} \
} \
} while (0)