Skip to contentSkip to conversation

alpha: simplify and optimize sched_find_first_bit

PATCH NAK [email protected] 2 participants 3 messages Apr 8, 2010 – Apr 29, 2010 1 message not in the archive

Subsystems (2)
Alpha port Bitops API
lore
Share & tools
lore

[email protected]

author maintainer
#0 lore raw

PATCH 1/1 alpha: simplify and optimize sched_find_first_bit

From: Matt Turner <[email protected]>

Search only the first 100 bits instead of 140, saving a couple instructions. Also use inline assembly to use cmov instructions instead of letting gcc emit multiple branches. The resulting code is about 6x faster.

Thanks to Zack Weinberg and Uros Bizjak (GCC Bug 43691) for helping me identify problems with the inline assembly.

Cc Peter Zijlstra <[email protected]>
Cc Ingo Molnar <[email protected]>
Cc Richard Henderson <[email protected]>
Cc Ivan Kokshaysky <[email protected]>
Cc [email protected]
Signed-off-by Matt Turner <[email protected]>
---
 arch/alpha/include/asm/bitops.h |   24 ++++++++++++------------
 1 files changed, 12 insertions(+), 12 deletions(-)
arch/alpha/include/asm/bitops.h +12 -12
index 15f3ae2..cfa7526 100644
@@ -436,22 +436,22 @@ static inline unsigned int hweight8(unsigned int w)
 
 /*
  * Every architecture must define this function. It's the fastest
- * way of searching a 140-bit bitmap where the first 100 bits are
- * unlikely to be set. It's guaranteed that at least one of the 140
- * bits is set.
+ * way of searching a 100-bit bitmap.  It's guaranteed that at least
+ * one of the 100 bits is cleared.
  */
 static inline unsigned long
-sched_find_first_bit(unsigned long b[3])
+sched_find_first_bit(const unsigned long b[2])
 {
-	unsigned long b0 = b[0], b1 = b[1], b2 = b[2];
 	unsigned long ofs;
-
-	ofs = (b1 ? 64 : 128);
-	b1 = (b1 ? b1 : b2);
-	ofs = (b0 ? 0 : ofs);
-	b0 = (b0 ? b0 : b1);
-
-	return __ffs(b0) + ofs;
+	unsigned long output;
+	asm(
+		"cmoveq %0,64,%1        # ofs = (b[0] ? ofs : 64);\n"
+		"cmoveq %0,%2,%0        # temp = (b[0] ? b[0] : b[1]);\n"
+		"cttz   %0,%0           # output = cttz(temp);\n "
+		: "=r" (output), "=r" (ofs)
+		: "r" (b[1]), "0" (b[0]), "1" (0)
+	);
+	return output + ofs;
 }
 
 #include <asm-generic/bitops/ext2-non-atomic.h>
Signature · 1 line
1.6.4.4
NAK
#1 lore raw

arch/alpha/include/asm/bitops.h static inline unsigned int hweight8(unsigned int w) · line 454

Quoted 10 lines · On 04/08/2010 11:34 AM, [email protected] wrote:
arch/alpha/include/asm/bitops.h +9 -1
-	return __ffs(b0) + ofs;
+	unsigned long output;
+	asm(
+		"cmoveq %0,64,%1        # ofs = (b[0] ? ofs : 64);\n"
+		"cmoveq %0,%2,%0        # temp = (b[0] ? b[0] : b[1]);\n"
+		"cttz   %0,%0           # output = cttz(temp);\n "
+		: "=r" (output), "=r" (ofs)
+		: "r" (b[1]), "0" (b[0]), "1" (0)
+	);
+	return output + ofs;

NACK.

You need to move that cttz out of the asm as well, to continue to support pre-ev67. Ack if you adjust to use __ffs.

r~

A message that is not in the archive (sent off-list or not yet received): [email protected]

author maintainer
#3 lore raw
Quoted 54 lines · Richard Henderson
Quoted 6 lines · On 04/08/2010 11:34 AM, [email protected] wrote:

+     asm(
+             "cmoveq %0,64,%1        # ofs = (b[0] ? ofs : 64);\n"
+             "cmoveq %0,%2,%0        # temp = (b[0] ? b[0] : b[1]);\n"
+             "cttz   %0,%0           # output = cttz(temp);\n "
+             : "=r" (output), "=r" (ofs)
+             : "r" (b[1]), "0" (b[0]), "1" (0)

I must say I'd also prefer a comment like

       /* This is equivalent to
               ofs = (b[0] ? 0 : 64);
               tmp = (b[0] ? b[0] : b[1]);
          but is a bit faster than what GCC would produce on its own.  */ asm("cmoveq %0,64,%1\n\tcmoveq %0,%2,%0"
           : "=r"(output), "=r"(ofs)
           : "r"(b[1]), "0"(b[0]), "1"(0));

... except that I can't see that it is, at least for mainline gcc.

[anchor:~] cat z.c
long foo(const unsigned long *b)
{
 unsigned long b0, b1, ofs, tmp;

 b0 = b[0];
 b1 = b[1];
 ofs = (b0 ? 0 : 64);
 tmp = (b0 ? b0 : b1);

 /* tmp = __ffs(tmp); -- elided for clarity wrt ev5 vs ev67 */ return tmp + ofs;
}

-mcpu=ev5 -Os (to avoid nop padding):
       ldq $2,0($16)
       ldq $1,8($16)
       lda $0,64($31)
       cmovne $2,0,$0
       cmovne $2,$2,$1
       addq $0,$1,$0

-mcpu=ev6 -Os:
       ldq $0,0($16)
       ldq $1,8($16)
       cmovne $0,$0,$1
       cmpeq $0,0,$0
       sll $0,6,$0
       addq $0,$1,$0

I seem to recall that cmov is slightly more expensive on ev6, so gcc doesn't prefer it and came up with an equivalent using cmpeq+sll.

Quoted 6 lines

If some previous version of gcc isn't so smart, I'm ok with continuing to use the asm.

r~

So with your test program, the code generation results are:

4.3.4 -Os: good
4.3.4 -O1: bad
4.3.4 -O2: good
4.3.4 -O3: good

4.4.3 -Os: bad
4.4.3 -O1: bad
4.4.3 -O2: bad
4.4.3 -O3: good

4.5.0 -Os: good
4.5.0 -O1: bad
4.5.0 -O2: good
4.5.0 -O3: good

o -O3 is produces good code in all versions.
o -O1 is bad in all versions.
o -Os and -O2 regressed from 4.3.4 to 4.4.3,
but are back to 4.3.4 quality as of 4.5.0.

All produced cmov instructions just as you said.

My patch doesn't help any of the bad cases and even causes some that were good to produce worse code, so it's not useful. Does any of this look like it should warrant a gcc bug report, Richard?

I'll send a patch just to update sched_find_first_bit to search just the first 100-bits.

Thanks!
Matt