floor_log2_wide speedup
DJ Delorie
dj@redhat.com
Fri Jun 4 22:58:00 GMT 2004
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);
More information about the Gcc-patches
mailing list