CRIS: Add hardware support for __builtin_ctz

[Jesper Nilsson <jesper dot nilsson at axis dot com>]

Hi,

This patch for CRIS adds support for __builtin_ctz using the machine
instruction 'swap' (which can be used to reverse the bit order of a
register) in combination with 'clz'.

The implementation uses an unspec insn for the bitswapping,
and a define_expand for combining the bitswap and the clz.

I've added the define for count_trailing_zeros as an analog to
count_leading_zeros in longlong.h, inside an additional test
for __CRIS_arch_version >= 8.

I've also added testcases for this instruction that checks
for existence and absence of the special swap-instruction in
assembler output.


One question mark still remaining is why the define_expand for
ctzsi2 can't use the following:

(define_expand "ctzsi2"
  [(set (match_scratch:SI 2)
        (match_operand:SI 0 "register_operand"))
   (set (match_dup 2)
        (unspec:SI [(match_dup 2)] CRIS_UNSPEC_SWAP_BITS))
   (set (match_operand:SI 0 "register_operand")
        (clz:SI (match_dup 2)))
  ]
  "TARGET_HAS_LZ && TARGET_HAS_SWAP"
  ""
  )

If the above construction is used, I get an ICE in copy_rtx for the
scratch operand...



Testing has been done for cris-axis-elf on i686-pc-linux-gnu using
make check 'RUNTESTFLAGS=--target_board=cris-sim\{,-march=v3,-march=v8,-march=v10\}'
No new regressions found.

Best regards,

/Jesper Nilsson

:ADDPATCH cris ctz:

gcc/ChangeLog:

2007-09-03  Jesper Nilsson  <jesper.nilsson@axis.com>

	* longlong.h  [__CRIS_arch_version >= 8] (count_trailing_zeros):
	Defined.
	* config/cris/cris.md (ctzsi2, cris_swap_bits): Implemented.
	* config/cris/cris.h (CTZ_DEFINED_VALUE_AT_ZERO): Defined.

testsuite/ChangeLog:

2007-09-03  Jesper Nilsson  <jesper.nilsson@axis.com>

	* gcc.target/cris/builtin_ctz_v3.c: New testcase.
	* gcc.target/cris/builtin_ctz_v8.c: New testcase.

Index: longlong.h
===================================================================
--- longlong.h	(revision 128037)
+++ longlong.h	(working copy)
@@ -228,6 +228,9 @@
 
 #if defined (__CRIS__) && __CRIS_arch_version >= 3
 #define count_leading_zeros(COUNT, X) ((COUNT) = __builtin_clz (X))
+#if __CRIS_arch_version >= 8
+#define count_trailing_zeros(COUNT, X) ((COUNT) = __builtin_ctz (X))
+#endif
 #endif /* __CRIS__ */
 
 #if defined (__hppa) && W_TYPE_SIZE == 32
Index: config/cris/cris.md
===================================================================
--- config/cris/cris.md	(revision 128067)
+++ config/cris/cris.md	(working copy)
@@ -69,7 +69,8 @@
    (CRIS_UNSPEC_GOT 2)
    (CRIS_UNSPEC_GOTREL 3)
    (CRIS_UNSPEC_GOTREAD 4)
-   (CRIS_UNSPEC_PLTGOTREAD 5)])
+   (CRIS_UNSPEC_PLTGOTREAD 5)
+   (CRIS_UNSPEC_SWAP_BITS 6)])
 
 ;; Register numbers.
 (define_constants
@@ -2678,6 +2679,32 @@
   "swapwb %0"
   [(set_attr "slottable" "yes")])
 
+;; This instruction is swaps all bits in a register.
+;; That means that the most significant bit is put in the place
+;; of the least significant bit, and so on.
+
+(define_insn "cris_swap_bits"
+  [(set (match_operand:SI 0 "register_operand" "=r")
+        (unspec:SI [(match_operand:SI 1 "register_operand" "0")]
+         CRIS_UNSPEC_SWAP_BITS))]
+  "TARGET_HAS_SWAP"
+  "swapwbr %0"
+  [(set_attr "slottable" "yes")])
+
+;; Implement ctz using two instructions, one for bit swap and one for clz.
+;; Defines a scratch register to avoid clobbering input.
+
+(define_expand "ctzsi2"
+  [(set (match_dup 2)
+        (match_operand:SI 1 "register_operand"))
+   (set (match_dup 2)
+        (unspec:SI [(match_dup 2)] CRIS_UNSPEC_SWAP_BITS))
+   (set (match_operand:SI 0 "register_operand")
+        (clz:SI (match_dup 2)))]
+  "TARGET_HAS_LZ && TARGET_HAS_SWAP"
+  "operands[2] = gen_reg_rtx (SImode);"
+  )
+
 ;; Bound-insn.  Defined to be the same as an unsigned minimum, which is an
 ;; operation supported by gcc.  Used in casesi, but used now and then in
 ;; normal code too.
Index: config/cris/cris.h
===================================================================
--- config/cris/cris.h	(revision 128067)
+++ config/cris/cris.h	(working copy)
@@ -1410,6 +1410,7 @@
 #define TRULY_NOOP_TRUNCATION(OUTPREC, INPREC) 1
 
 #define CLZ_DEFINED_VALUE_AT_ZERO(MODE, VALUE) ((VALUE) = 32, 1)
+#define CTZ_DEFINED_VALUE_AT_ZERO(MODE, VALUE) ((VALUE) = 32, 1)
 
 #define Pmode SImode
 


/^JN - Jesper Nilsson
--
               Jesper Nilsson -- jesper.nilsson@axis.com

/* Check that we don't use the swap insn for ctz by checking
   assembler output.  The swap instruction was implemented in v8.  */
/* { dg-do compile } */
/* { dg-skip-if "" { "cris-*-elf" } { "-march*" } { "" } } */
/* { dg-options "-O2 -march=v3" } */
/* { dg-final { scan-assembler-not "\[ \t\]swapwbr\[ \t\]" } } */

int
f (int a)
{
	return __builtin_ctz(a);
}

/* Check that we use the swap insn for ctz by checking assembler output.
   The swap instruction was implemented in v8.  */
/* { dg-do compile } */
/* { dg-skip-if "" { "cris-*-elf" } { "-march*" } { "" } } */
/* { dg-options "-O2 -march=v8" } */
/* { dg-final { scan-assembler "\[ \t\]swapwbr\[ \t\]" } } */

int
f (int a)
{
	return __builtin_ctz(a);
}