Re: speeding up parts of gcc by using ffs

[Andrew Pinski <pinskia@physics.uc.edu>]

Here is the first patch for using ffs{,l,ll} in gcc, will be posting 
the rest by Monday.
This adds ffsl and ffsll to libiberty, and also adds the ffs's to the 
libiberty.a.

Thanks,
Andrew Pinski
apinski@apple.com
pinskia@physics.uc.edu



On Monday, Jan 6, 2003, at 09:49 US/Pacific, Zack Weinberg wrote:

> Andrew Pinski <pinskia@physics.uc.edu> writes:
>
>> A follow of the comments I received, I have only right now added the
>> simple cases of HOST_BITS_PER_WIDE_INT == HOST_BITS_PER_INT and
>> HOST_BITS_PER_INT == HOST_BITS_PER_LONG.  I might implement the other
>> part of the patch for when HOST_BITS_PER_WIDE_INT ==
>> HOST_BITS_PER_LONG_LONG and HOST_BITS_PER_WIDE_INT ==
>> HOST_BITS_PER_LONG but this might take some time because I have to add
>> some more builtins but it will clean things up.
>
> I'm not enthusiastic about all the #ifdefs.
>
> glibc provides ffsl and ffsll which take 'long' and 'long long'
> respectively; may I suggest that you follow these steps:
>
> 1) put ffsl and ffsll into libiberty.
> 2) have hwint.h #define ffs_hwi and ffs_hwidesti appropriately
> 3) use ffs/ffsl/ffsll/ffs_hwi throughout the compiler
> 4) create __builtin_ffsl and __builtin_ffsll
>
> zw



ChangeLog:
2003-01-07	Andrew Pinski <pinskia@physics.uc.edu>
	* Makefile.in (ffsll.o): special rule for long long warning.
	(CFILES): add ffsl.c and ffsll.c. (CONFIGURED_OFILES): add
	ffsl.o and ffsll.o. (NEEDED): add ffs, ffsl, and ffsll.
	* aclocal.m4 include ../config/accross.m4 for AC_C_BIGENDIAN_CROSS,
   and AC_COMPILE_CHECK_SIZEOF. (libiberty_AC_C_LONG_LONG) copied from
   gcc's gcc_AC_C_LONG_LONG.
	* configure.in (AC_C_BIGENDIAN_CROSS) use it.
   (libiberty_AC_C_LONG_LONG) use it. (AC_COMPILE_CHECK_SIZEOF) use it.
   Probe the size of int, long, and long long/__int64 if we have them.
   Check for ffsl and ffsll.
	* configure regenerate.
   (LIB_AC_PROG_CC) add ac_libiberty_warn_long_long_cflags.
	* config.in regenerate.
	* ffsl.c new file.
	* ffsll.c new file.

Index: Makefile.in
===================================================================
RCS file: /cvs/gcc/gcc/libiberty/Makefile.in,v
retrieving revision 1.78
diff -u -d -b -w -b -B -u -r1.78 Makefile.in
--- Makefile.in	22 Nov 2002 20:01:07 -0000	1.78
+++ Makefile.in	8 Jan 2003 07:32:39 -0000
@@ -122,15 +122,22 @@
  	else true; fi
  	$(COMPILE.c) $< $(OUTPUT_OPTION)

+#special case ffsll.o because of extra warnings will show up other wise
+ffsll.o: ffsll.c
+	if [ x"$(PICFLAG)" != x ]; then \
+	  $(COMPILE.c) @ac_libiberty_warn_long_long_cflags@  $(PICFLAG) $< -o 
pic/$@; \
+	else true; fi
+	$(COMPILE.c) @ac_libiberty_warn_long_long_cflags@ $< $(OUTPUT_OPTION)
+
  # NOTE: If you add new files to the library, add them to this list
  # (alphabetical), and add them to REQUIRED_OFILES, or
  # CONFIGURED_OFILES and funcs in configure.in.
  CFILES = alloca.c argv.c asprintf.c atexit.c				\
  	basename.c bcmp.c bcopy.c bsearch.c bzero.c			\
-	calloc.c choose-temp.c clock.c concat.c cp-demangle.c		\
-	 cplus-dem.c							\
+	calloc.c choose-temp.c clock.c concat.c 			\
+	 cp-demangle.c cplus-dem.c					\
  	dyn-string.c							\
-	fdmatch.c ffs.c fibheap.c floatformat.c fnmatch.c		\
+	fdmatch.c ffs.c ffsl.c ffsll.c fibheap.c floatformat.c fnmatch.c\
  	getcwd.c getopt.c getopt1.c getpagesize.c getpwd.c getruntime.c	\
  	hashtab.c hex.c							\
  	index.c insque.c						\
@@ -176,7 +183,7 @@
  	basename.o bcmp.o bcopy.o bsearch.o bzero.o			\
  	calloc.o clock.o copysign.o					\
  	_doprnt.o							\
-	ffs.o								\
+	ffs.o ffsl.o ffsll.o						\
  	getcwd.o getpagesize.o						\
  	index.o insque.o						\
  	memchr.o memcmp.o memcpy.o memmove.o memset.o mkstemps.o	\
@@ -287,7 +294,7 @@
  # can't use anything encumbering.
  NEEDED = atexit calloc memchr memcmp memcpy memmove memset rename 
strchr \
  	 strerror strncmp strrchr strstr strtol strtoul tmpnam vfprintf 
vprintf \
-	 vfork waitpid bcmp bcopy bzero
+	 vfork waitpid bcmp bcopy bzero ffs ffsl ffsll
  needed-list: Makefile
  	rm -f needed-list; touch needed-list; \
  	for f in $(NEEDED); do \
Index: aclocal.m4
===================================================================
RCS file: /cvs/gcc/gcc/libiberty/aclocal.m4,v
retrieving revision 1.5
diff -u -d -b -w -b -B -u -r1.5 aclocal.m4
--- aclocal.m4	31 Dec 2001 23:23:49 -0000	1.5
+++ aclocal.m4	8 Jan 2003 07:32:39 -0000
@@ -1,3 +1,5 @@
+sinclude(../config/accross.m4)
+
  dnl See whether strncmp reads past the end of its string parameters.
  dnl On some versions of SunOS4 at least, strncmp reads a word at a time
  dnl but erroneously reads past the end of strings.  This can cause
@@ -107,6 +109,7 @@
  if test $ac_cv_prog_gcc = yes; then
    GCC=yes
    ac_libiberty_warn_cflags='-W -Wall -Wtraditional -pedantic'
+  ac_libiberty_warn_long_long_cflags='-Wno-long-long'
  dnl Check whether -g works, even if CFLAGS is set, in case the package
  dnl plays around with CFLAGS (such as to build both debugging and
  dnl normal versions of a library), tasteless as that idea is.
@@ -124,9 +127,11 @@
  else
    GCC=
    ac_libiberty_warn_cflags=
+  ac_libiberty_warn_long_long_cflags=
    test "${CFLAGS+set}" = set || CFLAGS="-g"
  fi
  AC_SUBST(ac_libiberty_warn_cflags)
+AC_SUBST(ac_libiberty_warn_long_long_cflags)
  ])

  # Work around a bug in autoheader.  This can go away when we switch to
@@ -188,4 +193,27 @@
          STACK_DIRECTION > 0 => grows toward higher addresses
          STACK_DIRECTION < 0 => grows toward lower addresses
          STACK_DIRECTION = 0 => direction of growth unknown])
+])
+
+dnl Checking for long long.
+dnl By Caolan McNamara <caolan@skynet.ie>
+dnl Added check for __int64, Zack Weinberg <zackw@stanford.edu>
+dnl
+AC_DEFUN([libiberty_AC_C_LONG_LONG],
+[AC_CACHE_CHECK(for long long int, ac_cv_c_long_long,
+  [AC_TRY_COMPILE(,[long long int i;],
+         ac_cv_c_long_long=yes,
+         ac_cv_c_long_long=no)])
+  if test $ac_cv_c_long_long = yes; then
+    AC_DEFINE(HAVE_LONG_LONG, 1,
+      [Define if your compiler supports the \`long long' type.])
+  fi
+AC_CACHE_CHECK(for __int64, ac_cv_c___int64,
+  [AC_TRY_COMPILE(,[__int64 i;],
+	ac_cv_c___int64=yes,
+	ac_cv_c___int64=no)])
+  if test $ac_cv_c___int64 = yes; then
+    AC_DEFINE(HAVE___INT64, 1,
+      [Define if your compiler supports the \`__int64' type.])
+  fi
  ])
Index: configure.in
===================================================================
RCS file: /cvs/gcc/gcc/libiberty/configure.in,v
retrieving revision 1.52
diff -u -d -b -w -b -B -u -r1.52 configure.in
--- configure.in	1 Jul 2002 05:38:50 -0000	1.52
+++ configure.in	8 Jan 2003 07:32:39 -0000
@@ -145,6 +145,9 @@
  AC_HEADER_SYS_WAIT
  AC_HEADER_TIME

+
+AC_C_BIGENDIAN_CROSS
+
  libiberty_AC_DECLARE_ERRNO

  AC_CHECK_TYPE(uintptr_t, unsigned long)
@@ -154,6 +158,18 @@
    AC_DEFINE(HAVE_UINTPTR_T, 1, [Define if you have the \`uintptr_t' 
type.])
  fi

+libiberty_AC_C_LONG_LONG
+
+AC_COMPILE_CHECK_SIZEOF(int)
+AC_COMPILE_CHECK_SIZEOF(long)
+
+if test $ac_cv_c_long_long = yes; then
+  AC_COMPILE_CHECK_SIZEOF(long long)
+fi
+if test $ac_cv_c___int64 = yes; then
+  AC_COMPILE_CHECK_SIZEOF(__int64)
+fi
+
  AC_TYPE_PID_T

  # This is the list of functions which libiberty will provide if they
@@ -200,6 +216,14 @@
  funcs="$funcs vprintf"
  funcs="$funcs vsprintf"
  funcs="$funcs waitpid"
+funcs="$funcs ffsl"
+
+if test $ac_cv_c_long_long = yes; then
+    funcs="$funcs ffsll"
+fi
+if test $ac_cv_c___int64 = yes; then
+    funcs="$funcs ffsll"
+fi

  # Also in the old function.def file: alloca, vfork, getopt.

@@ -216,7 +240,7 @@
    AC_CHECK_FUNCS(strcasecmp setenv strchr strdup strncasecmp strrchr 
strstr)
    AC_CHECK_FUNCS(strtod strtol strtoul tmpnam vasprintf vfprintf 
vprintf)
    AC_CHECK_FUNCS(vsprintf waitpid getrusage on_exit psignal strerror 
strsignal)
-  AC_CHECK_FUNCS(sysconf times sbrk gettimeofday ffs)
+  AC_CHECK_FUNCS(sysconf times sbrk gettimeofday ffs ffsl ffsll)
    AC_DEFINE(HAVE_SYS_ERRLIST, 1, [Define if you have the sys_errlist 
variable.])
    AC_DEFINE(HAVE_SYS_NERR,    1, [Define if you have the sys_nerr 
variable.])
    AC_DEFINE(HAVE_SYS_SIGLIST, 1, [Define if you have the sys_siglist 
variable.])
Index: ffsl.c
===================================================================
RCS file: ffsl.c
diff -N ffsl.c
--- /dev/null	1 Jan 1970 00:00:00 -0000
+++ ffsl.c	8 Jan 2003 07:32:39 -0000
@@ -0,0 +1,31 @@
+/* ffsl -- Find the first bit set in the parameter
+
+@deftypefn Supplemental int ffsl (long @var{valu})
+
+Find the first (least significant) bit set in @var{valu}.  Bits are
+numbered from right to left, starting with bit 1 (corresponding to the
+value 1).  If @var{valu} is zero, zero is returned.
+
+@end deftypefn
+
+*/
+
+#include "config.h"
+
+int
+ffsl (valu)
+  register long valu;
+{
+#if SIZEOF_LONG == SIZEOF_INT
+  extern int ffs();
+  return ffs(valu);
+#else
+#if SIZEOF_LONG == SIZEOF_LONG_LONG || SIZEOF_LONG == SIZEOF___INT64
+  extern int ffs();
+  return ffsll(valu);
+#else
+  #error Do not know what size long is.
+#endif
+#endif
+}
+
Index: ffsll.c
===================================================================
RCS file: ffsll.c
diff -N ffsll.c
--- /dev/null	1 Jan 1970 00:00:00 -0000
+++ ffsll.c	8 Jan 2003 07:32:39 -0000
@@ -0,0 +1,75 @@
+/* ffsll -- Find the first bit set in the parameter
+
+@deftypefn Supplemental int ffsll (int @var{valu})
+
+Find the first (least significant) bit set in @var{valu}.  Bits are
+numbered from right to left, starting with bit 1 (corresponding to the
+value 1).  If @var{valu} is zero, zero is returned.
+
+@end deftypefn
+
+*/
+
+#include "config.h"
+
+#if defined(HAVE_LONG_LONG)
+#define NEED_FFSLL
+typedef long long ll;
+#define SIZEOF_LL SIZEOF_LONG_LONG
+
+#else
+#if defined(HAVE___INT64)
+#define NEED_FFSLL
+typedef __int64 ll;
+#define SIZEOF_LL SIZEOF___INT64
+
+#endif
+#endif
+
+#if defined(NEED_FFSLL)
+
+union ll_ints {
+  ll longlongs;
+  struct {
+#if defined(WORDS_BIGENDIAN)
+    int hi;
+    int low;
+#else
+    int low;
+    int hi;
+#endif
+  } ints;
+};
+
+int ffs ();
+
+int
+ffsll (valu)
+  register ll valu;
+{
+#if SIZEOF_LL == SIZEOF_INT*2
+  ll x  = valu & -valu;
+  union ll_ints temp;
+  union ll_ints temp1;
+  int add = 0;
+  int word;
+  temp.longlongs = valu;
+  temp1.longlongs = x;
+  if(temp1.ints.hi!=0)
+    word = temp.ints.low;
+  else
+    word = temp.ints.hi, add = 32;
+  return add + ffs (word);
+#else
+ int bit_num = 0;
+ if(valu==0)
+   return 0;
+ while((valu&1)!=0)
+   bit_num ++, valu >>= 1;
+
+  return bit_num;
+#endif
+
+}
+
+#endif