Re: floor_log2_wide speedup

[DJ Delorie <dj at redhat dot com>]

Here's the whole patch so far.  It's currently building stage2, so
now's a good time to suggest a level of testing.

I wanted to use a statement expression, but there was an ISO warning
and no way to tell gcc that I'd conditional'd that for gcc, so it had
to go :-(  (another case for source-level warning control!)

I used #defines to modify the static inline function just to keep it
more maintainable; I can do three copies of the function if that's
preferred.

2004-06-04  DJ Delorie  <dj@redhat.com>

	* toplev.c (floor_log2_wide): Replace loop with faster bit
	operations.
	(exact_log2_wide): Define in terms of the above.
	* toplev.h (floor_log2): Use _builtin_clz family of builtins if
	available.

Index: toplev.c
===================================================================
RCS file: /cvs/gcc/gcc/gcc/toplev.c,v
retrieving revision 1.901
diff -p -C2 -r1.901 toplev.c
*** toplev.c	3 Jun 2004 23:16:21 -0000	1.901
--- toplev.c	4 Jun 2004 21:42:06 -0000
*************** read_integral_parameter (const char *p, 
*** 1249,1282 ****
  }
  
! /* Return the logarithm of X, base 2, considering X unsigned,
!    if X is a power of 2.  Otherwise, returns -1.
  
!    This should be used via the `exact_log2' macro.  */
  
  int
! exact_log2_wide (unsigned HOST_WIDE_INT x)
  {
!   int log = 0;
!   /* Test for 0 or a power of 2.  */
!   if (x == 0 || x != (x & -x))
      return -1;
!   while ((x >>= 1) != 0)
!     log++;
!   return log;
  }
  
! /* Given X, an unsigned number, return the largest int Y such that 2**Y <= X.
!    If X is 0, return -1.
  
!    This should be used via the floor_log2 macro.  */
  
  int
! floor_log2_wide (unsigned HOST_WIDE_INT x)
  {
!   int log = -1;
!   while (x != 0)
!     log++,
!     x >>= 1;
!   return log;
  }
  
--- 1249,1294 ----
  }
  
! /* Given X, an unsigned number, return the largest int Y such that 2**Y <= X.
!    If X is 0, return -1.
  
!    This should be used via the floor_log2 macro.  */
  
  int
! floor_log2_wide (unsigned HOST_WIDE_INT x)
  {
!   int t=0;
!   if (x == 0)
      return -1;
!   if (sizeof (HOST_WIDE_INT)*8 > 64)
!     if (x >= (unsigned HOST_WIDE_INT)(1 << (t+64)))
!       t += 64;
!   if (sizeof (HOST_WIDE_INT)*8 > 32)
!     if (x >= (unsigned HOST_WIDE_INT)(1 << (t+32)))
!       t += 32;
!   if (x >= (unsigned HOST_WIDE_INT)(1 << (t+16)))
!     t += 16;
!   if (x >= (unsigned HOST_WIDE_INT)(1 << (t+8)))
!     t += 8;
!   if (x >= (unsigned HOST_WIDE_INT)(1 << (t+4)))
!     t += 4;
!   if (x >= (unsigned HOST_WIDE_INT)(1 << (t+2)))
!     t += 2;
!   if (x >= (unsigned HOST_WIDE_INT)(1 << (t+1)))
!     t += 1;
!   return t;
  }
  
! /* Return the logarithm of X, base 2, considering X unsigned,
!    if X is a power of 2.  Otherwise, returns -1.
  
!    This should be used via the `exact_log2' macro.  */
  
  int
! exact_log2_wide (unsigned HOST_WIDE_INT x)
  {
!   /* Test for 0 or a power of 2.  */
!   if (x == 0 || x != (x & -x))
!     return -1;
!   return floor_log2_wide (x);
  }
  
Index: toplev.h
===================================================================
RCS file: /cvs/gcc/gcc/gcc/toplev.h,v
retrieving revision 1.122
diff -p -C2 -r1.122 toplev.h
*** toplev.h	24 May 2004 19:28:20 -0000	1.122
--- toplev.h	4 Jun 2004 21:42:06 -0000
*************** extern bool fast_math_flags_set_p	(void)
*** 153,158 ****
--- 153,181 ----
  #ifndef exact_log2
  #define exact_log2(N) exact_log2_wide ((unsigned HOST_WIDE_INT) (N))
+ 
+ #if (__GNUC__ * 1000 + __GNUC_MINOR__) >= 3004
+ #if HOST_BITS_PER_WIDE_INT == HOST_BITS_PER_LONGLONG
+ #define FL2T__ HOST_WIDE_INT
+ #define FL2T_CLZ__ __builtin_clzll
+ #else
+ #if HOST_BITS_PER_WIDE_INT == HOST_BITS_PER_LONG
+ #define FL2T__ HOST_WIDE_INT
+ #define FL2T_CLZ__ __builtin_clzl
+ #else
+ #define FL2T__ int
+ #define FL2T_CLZ__ __builtin_clz
+ #endif
+ #endif
+ static inline int floor_log2(FL2T__ n)
+ {
+   if (n)
+     return (sizeof(FL2T__)*8-1) - (int)FL2T_CLZ__(n);
+   return -1;
+ }
+ #else
  #define floor_log2(N) floor_log2_wide ((unsigned HOST_WIDE_INT) (N))
  #endif
+ 
+ #endif
  extern int exact_log2_wide             (unsigned HOST_WIDE_INT);
  extern int floor_log2_wide             (unsigned HOST_WIDE_INT);