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: ffs/ctz expansions using clz


Mark Mitchell wrote:

Sandra, please adjust the documentation in tm.texi to reflect the
possible value "2" and your patch to test for that.  With those changes,
your patch is OK.

OK, I've tested and committed the patch with that change. Here's the final version.


-Sandra

2007-08-09  Sandra Loosemore  <sandra@codesourcery.com>
	    Nigel Stephens  <nigel@mips.com>

	gcc/
	* doc/tm.texi (CLZ_DEFINED_VALUE_AT_ZERO, CTZ_DEFINED_VALUE_AT_ZERO):
	Document change in interpretation of value from boolean to
	tri-state integer.
	* optabs.c (expand_ffs, expand_ctz): New functions to compute
	ffs and ctz using clz.
	(expand_unop):  Call them.
	* config/rs6000/rs6000.h (CLZ_DEFINED_VALUE_AT_ZERO): Fix its
	result value.
	(CTZ_DEFINED_VALUE_AT_ZERO): Likewise.
	* config/mips/mips.h (CLZ_DEFINED_VALUE_AT_ZERO): Likewise, to
	enable the new ffs expansion on this target.
Index: gcc/doc/tm.texi
===================================================================
*** gcc/doc/tm.texi	(revision 127304)
--- gcc/doc/tm.texi	(working copy)
*************** given mode.
*** 9590,9603 ****
  
  @defmac CLZ_DEFINED_VALUE_AT_ZERO (@var{mode}, @var{value})
  @defmacx CTZ_DEFINED_VALUE_AT_ZERO (@var{mode}, @var{value})
! A C expression that evaluates to true if the architecture defines a value
! for @code{clz} or @code{ctz} with a zero operand.  If so, @var{value}
! should be set to this value.  If this macro is not defined, the value of
! @code{clz} or @code{ctz} is assumed to be undefined.
  
  This macro must be defined if the target's expansion for @code{ffs}
  relies on a particular value to get correct results.  Otherwise it
! is not necessary, though it may be used to optimize some corner cases.
  
  Note that regardless of this macro the ``definedness'' of @code{clz}
  and @code{ctz} at zero do @emph{not} extend to the builtin functions
--- 9590,9612 ----
  
  @defmac CLZ_DEFINED_VALUE_AT_ZERO (@var{mode}, @var{value})
  @defmacx CTZ_DEFINED_VALUE_AT_ZERO (@var{mode}, @var{value})
! A C expression that indicates whether the architecture defines a value
! for @code{clz} or @code{ctz} with a zero operand.  
! A result of @code{0} indicates the value is undefined.
! If the value is defined for only the RTL expression, the macro should
! evaluate to @code{1}; if the value applies also to the corresponding optab
! entry (which is normally the case if it expands directly into
! the corresponding RTL), then the macro should evaluate to @code{2}.  
! In the cases where the value is defined, @var{value} should be set to
! this value.  
! 
! If this macro is not defined, the value of @code{clz} or
! @code{ctz} at zero is assumed to be undefined.
  
  This macro must be defined if the target's expansion for @code{ffs}
  relies on a particular value to get correct results.  Otherwise it
! is not necessary, though it may be used to optimize some corner cases, and
! to provide a default expansion for the @code{ffs} optab.
  
  Note that regardless of this macro the ``definedness'' of @code{clz}
  and @code{ctz} at zero do @emph{not} extend to the builtin functions
Index: gcc/optabs.c
===================================================================
*** gcc/optabs.c	(revision 127304)
--- gcc/optabs.c	(working copy)
*************** static void prepare_float_lib_cmp (rtx *
*** 122,127 ****
--- 122,129 ----
  				   enum machine_mode *, int *);
  static rtx widen_clz (enum machine_mode, rtx, rtx);
  static rtx expand_parity (enum machine_mode, rtx, rtx);
+ static rtx expand_ffs (enum machine_mode, rtx, rtx);
+ static rtx expand_ctz (enum machine_mode, rtx, rtx);
  static enum rtx_code get_rtx_code (enum tree_code, bool);
  static rtx vector_compare_rtx (tree, bool, enum insn_code);
  
*************** expand_parity (enum machine_mode mode, r
*** 2560,2565 ****
--- 2562,2629 ----
    return 0;
  }
  
+ /* Try calculating ffs(x) using clz(x).  Since the ffs builtin promises
+    to return zero for a zero value and clz may have an undefined value
+    in that case, only do this if we know clz returns the right thing so
+    that we don't have to generate a test and branch.  */
+ static rtx
+ expand_ffs (enum machine_mode mode, rtx op0, rtx target)
+ {
+   HOST_WIDE_INT val;
+   if (clz_optab->handlers[(int) mode].insn_code != CODE_FOR_nothing
+       && CLZ_DEFINED_VALUE_AT_ZERO (mode, val) == 2
+       && val == GET_MODE_BITSIZE (mode))
+     {
+       rtx last = get_last_insn ();
+       rtx temp;
+ 
+       temp = expand_unop (mode, neg_optab, op0, NULL_RTX, true);
+       if (temp)
+ 	temp = expand_binop (mode, and_optab, op0, temp, NULL_RTX,
+ 			     true, OPTAB_DIRECT);
+       if (temp)
+ 	temp = expand_unop (mode, clz_optab, temp, NULL_RTX, true);
+       if (temp)
+ 	temp = expand_binop (mode, sub_optab,
+ 			     GEN_INT (GET_MODE_BITSIZE (mode)),
+ 			     temp,
+ 			     target, true, OPTAB_DIRECT);
+       if (temp == 0)
+ 	delete_insns_since (last);
+       return temp;
+     }
+   return 0;
+ }
+ 
+ /* We can compute ctz(x) using clz(x) with a similar recipe.  Here the ctz
+    builtin has an undefined result on zero, just like clz, so we don't have
+    to do that check.  */
+ static rtx
+ expand_ctz (enum machine_mode mode, rtx op0, rtx target)
+ {
+   if (clz_optab->handlers[(int) mode].insn_code != CODE_FOR_nothing)
+     {
+       rtx last = get_last_insn ();
+       rtx temp;
+ 
+       temp = expand_unop (mode, neg_optab, op0, NULL_RTX, true);
+       if (temp)
+ 	temp = expand_binop (mode, and_optab, op0, temp, NULL_RTX,
+ 			     true, OPTAB_DIRECT);
+       if (temp)
+ 	temp = expand_unop (mode, clz_optab, temp, NULL_RTX, true);
+       if (temp)
+ 	temp = expand_binop (mode, xor_optab, temp,
+ 			     GEN_INT (GET_MODE_BITSIZE (mode) - 1),
+ 			     target,
+ 			     true, OPTAB_DIRECT);
+       if (temp == 0)
+ 	delete_insns_since (last);
+       return temp;
+     }
+   return 0;
+ }
+ 
  /* Extract the OMODE lowpart from VAL, which has IMODE.  Under certain
     conditions, VAL may already be a SUBREG against which we cannot generate
     a further SUBREG.  In this case, we expect forcing the value into a
*************** expand_unop (enum machine_mode mode, opt
*** 2885,2890 ****
--- 2949,2970 ----
  	return temp;
      }
  
+   /* Try implementing ffs (x) in terms of clz (x).  */
+   if (unoptab == ffs_optab)
+     {
+       temp = expand_ffs (mode, op0, target);
+       if (temp)
+ 	return temp;
+     }
+ 
+   /* Try implementing ctz (x) in terms of clz (x).  */
+   if (unoptab == ctz_optab)
+     {
+       temp = expand_ctz (mode, op0, target);
+       if (temp)
+ 	return temp;
+     }
+ 
   try_libcall:
    /* Now try a library call in this mode.  */
    if (unoptab->handlers[(int) mode].libfunc)
Index: gcc/config/rs6000/rs6000.h
===================================================================
*** gcc/config/rs6000/rs6000.h	(revision 127304)
--- gcc/config/rs6000/rs6000.h	(working copy)
*************** do {								\
*** 1856,1865 ****
  
  /* The cntlzw and cntlzd instructions return 32 and 64 for input of zero.  */
  #define CLZ_DEFINED_VALUE_AT_ZERO(MODE, VALUE) \
!   ((VALUE) = ((MODE) == SImode ? 32 : 64))
  
  /* The CTZ patterns return -1 for input of zero.  */
! #define CTZ_DEFINED_VALUE_AT_ZERO(MODE, VALUE) ((VALUE) = -1)
  
  /* Specify the machine mode that pointers have.
     After generation of rtl, the compiler makes no further distinction
--- 1856,1865 ----
  
  /* The cntlzw and cntlzd instructions return 32 and 64 for input of zero.  */
  #define CLZ_DEFINED_VALUE_AT_ZERO(MODE, VALUE) \
!   ((VALUE) = ((MODE) == SImode ? 32 : 64), 1)
  
  /* The CTZ patterns return -1 for input of zero.  */
! #define CTZ_DEFINED_VALUE_AT_ZERO(MODE, VALUE) ((VALUE) = -1, 1)
  
  /* Specify the machine mode that pointers have.
     After generation of rtl, the compiler makes no further distinction
Index: gcc/config/mips/mips.h
===================================================================
*** gcc/config/mips/mips.h	(revision 127304)
--- gcc/config/mips/mips.h	(working copy)
*************** extern enum mips_code_readable_setting m
*** 1295,1301 ****
  /* The [d]clz instructions have the natural values at 0.  */
  
  #define CLZ_DEFINED_VALUE_AT_ZERO(MODE, VALUE) \
!   ((VALUE) = GET_MODE_BITSIZE (MODE), true)
  
  /* Standard register usage.  */
  
--- 1295,1301 ----
  /* The [d]clz instructions have the natural values at 0.  */
  
  #define CLZ_DEFINED_VALUE_AT_ZERO(MODE, VALUE) \
!   ((VALUE) = GET_MODE_BITSIZE (MODE), 2)
  
  /* Standard register usage.  */
  

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