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]
Other format: [Raw text]

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)


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