Skip to contentSkip to conversation

target-arm: use clz32() instead of a for loop

PATCH In review Aurelien Jarno 3 participants 6 messages Oct 15, 2009 – Oct 23, 2009

lore
Share & tools
lore
#0 lore raw

PATCH 1/1 target-arm: use clz32() instead of a for loop

---
 target-arm/helper.c |    6 ++----
 1 files changed, 2 insertions(+), 4 deletions(-)
target-arm/helper.c +2 -4
index 701629a..656b5df 100644
@@ -7,6 +7,7 @@
 #include "gdbstub.h"
 #include "helpers.h"
 #include "qemu-common.h"
+#include "host-utils.h"
 
 static uint32_t cortexa8_cp15_c0_c1[8] =
 { 0x1031, 0x11, 0x400, 0, 0x31100003, 0x20000000, 0x01202000, 0x11 };
@@ -394,10 +395,7 @@ uint32_t HELPER(uxtb16)(uint32_t x)
 
 uint32_t HELPER(clz)(uint32_t x)
 {
-    int count;
-    for (count = 32; x; count--)
-        x >>= 1;
-    return count;
+    return clz32(x);
 }
 
 int32_t HELPER(sdiv)(int32_t num, int32_t den)
Signature · 1 line
1.6.1.3
Acked-by on v1 1/1
#1 lore raw
Quoted 30 lines · Aurelien Jarno

---
 target-arm/helper.c |    6 ++----

 1 files changed, 2 insertions(+), 4 deletions(-)
target-arm/helper.c +1 -0
index 701629a..656b5df 100644
@@ -7,6 +7,7 @@
  #include "gdbstub.h"
  #include "helpers.h"
  #include "qemu-common.h"
+#include "host-utils.h"
 

 static uint32_t cortexa8_cp15_c0_c1[8] =
 { 0x1031, 0x11, 0x400, 0, 0x31100003, 0x20000000, 0x01202000, 0x11 };

target-arm/helper.c +1 -5
@@ -394,10 +395,7 @@ uint32_t HELPER(uxtb16)(uint32_t x)
 
  uint32_t HELPER(clz)(uint32_t x)
  {
-    int count;
-    for (count = 32; x; count--)
-        x >>= 1;
-    return count;
+    return clz32(x);
  }
 
  int32_t HELPER(sdiv)(int32_t num, int32_t den)
--
Quoted 1 line

1.6.1.3

#2 lore raw
In reply to Aurelien Jarno

target-arm/helper.c uint32_t HELPER(uxtb16)(uint32_t x) · line 401

Quoted 12 lines · Aurelien Jarno
target-arm/helper.c +1 -4
@@ -394,10 +395,7 @@ uint32_t HELPER(uxtb16)(uint32_t x)
 
 uint32_t HELPER(clz)(uint32_t x)
 {
-    int count;
-    for (count = 32; x; count--)
-        x >>= 1;
-    return count;
+    return clz32(x);
 }
 
 int32_t HELPER(sdiv)(int32_t num, int32_t den)

Just a quick note that the implementation of clz, ctz and popcnt is still listed in the TCG TODO list. The last time I looked, I noticed that quite a few architectures have clz/ctz instructions:

http://lkml.indiana.edu/hypermail/linux/kernel/0601.3/1683.html

For those that don't, I think a combination the following two hacks at
http://graphics.stanford.edu/~seander/bithacks.html could be used:

'Round up to the next highest power of 2'
'Counting bits set, in parallel'

With this, it should be possible to implement clz and ctz without too many operations for both 32-bit and 64-bit integers, without requiring floats, lookup tables or branches. Of course, __builtin_clz() might well do a better job...

BTW, it may be worth pointing out:

   B[4] = 0x0000ffff;
   B[3] = B[4] ^ (B[4] << 8) => 0x00ff00ff
   B[2] = B[3] ^ (B[3] << 4) => 0x0f0f0f0f
   B[1] = B[2] ^ (B[2] << 2) => 0x33333333
   B[0] = B[1] ^ (B[1] << 1) => 0x55555555

In reality, I wonder if five separate loads would be quicker, though.

Cheers,

Signature · 1 line
Stuart Brady
#3 lore raw
Quoted 12 lines · Stuart Brady
Quoted 11 lines · Aurelien Jarno
target-arm/helper.c +1 -4
@@ -394,10 +395,7 @@ uint32_t HELPER(uxtb16)(uint32_t x)
 
 uint32_t HELPER(clz)(uint32_t x)
 {
-    int count;
-    for (count = 32; x; count--)
-        x >>= 1;
-    return count;
+    return clz32(x);
 }
 
Quoted 7 lines

target-arm/helper.c uint32_t HELPER(uxtb16)(uint32_t x) · line 401

Quoted 1 line
target-arm/helper.c +0 -0
 int32_t HELPER(sdiv)(int32_t num, int32_t den)

Just a quick note that the implementation of clz, ctz and popcnt is still listed in the TCG TODO list. The last time I looked, I noticed that quite a few architectures have clz/ctz instructions:

   http://lkml.indiana.edu/hypermail/linux/kernel/0601.3/1683.html

OTOH, a dump shows that those instruction are not used than often, so I am not sure it worth implementing it.

Quoted 2 lines

For those that don't, I think a combination the following two hacks at
http://graphics.stanford.edu/~seander/bithacks.html could be used:

The best is probably to use an helper in that case, calling clz32(x).

Signature · 2 lines
Aurelien Jarno                          GPG: 1024D/F1BCDB73
[email protected]                 http://www.aurel32.net
#4 lore raw
Quoted 9 lines · Aurelien Jarno
Quoted 5 lines · Stuart Brady

Just a quick note that the implementation of clz, ctz and popcnt is still listed in the TCG TODO list. The last time I looked, I noticed that quite a few architectures have clz/ctz instructions:

   http://lkml.indiana.edu/hypermail/linux/kernel/0601.3/1683.html

OTOH, a dump shows that those instruction are not used than often, so I am not sure it worth implementing it.

Really? I'm surprised, as I gather that optimised ffs/fls/hweight functions in the kernel do give a modest gain... I suppose I'll have to try it on several different targets and see! :-)

Quoted 4 lines
Quoted 2 lines

For those that don't, I think a combination the following two hacks at
http://graphics.stanford.edu/~seander/bithacks.html could be used:

The best is probably to use an helper in that case, calling clz32(x).

Yes, you're right.

There are several other places that should also call clz32()/ctz32(). The ones that I can see are helper_neon_cls_s32() for ARM, helper_bsf() and helper_bsr() for X86, helper_ff1() for M68K. (I'm not sure about 'do_clz8' and 'do_clz16', though.)

At some point, possibly next weekend, I'll submit patches to add clz and ctz helpers to tcg-runtime.c, and to convert Alpha, ARM, CRIS, M68K, MIPS, PowerPC and x86 (any others I've missed?) to use those helpers.

Cheers,

Signature · 1 line
Stuart Brady
#5 lore raw
Quoted 6 lines · Stuart Brady
Quoted 5 lines · Aurelien Jarno
Quoted 4 lines · Stuart Brady

Just a quick note that the implementation of clz, ctz and popcnt is still listed in the TCG TODO list. The last time I looked, I noticed that quite a few architectures have clz/ctz instructions:

Quoted 7 lines
Quoted 3 lines
Quoted 1 line
   http://lkml.indiana.edu/hypermail/linux/kernel/0601.3/1683.html

OTOH, a dump shows that those instruction are not used than often, so I am not sure it worth implementing it.

Really? I'm surprised, as I gather that optimised ffs/fls/hweight functions in the kernel do give a modest gain... I suppose I'll have to try it on several different targets and see! :-)

I gave a quick look at MIPS, and at least here, it is used often.

Quoted 6 lines
Quoted 3 lines
Quoted 2 lines

For those that don't, I think a combination the following two hacks at
http://graphics.stanford.edu/~seander/bithacks.html could be used:

The best is probably to use an helper in that case, calling clz32(x).

Yes, you're right.

Quoted 8 lines

There are several other places that should also call clz32()/ctz32(). The ones that I can see are helper_neon_cls_s32() for ARM, helper_bsf() and helper_bsr() for X86, helper_ff1() for M68K. (I'm not sure about 'do_clz8' and 'do_clz16', though.)

At some point, possibly next weekend, I'll submit patches to add clz and ctz helpers to tcg-runtime.c, and to convert Alpha, ARM, CRIS, M68K, MIPS, PowerPC and x86 (any others I've missed?) to use those helpers.

The main problem I see for a TCG implementation is the definition of clz/ctz. Some targets define that clz(0) or ctz(0) returns 32, some other define it as being "undefined".

If we go for the common denominator for the TCG op, that is clz(0) = undefined, it means that a test with brcond has to be added in the targets using clz(0) = 32, and this is likely to give more slow down than speed gain.

If we go for clz(0) = 32, it means the test has to be implemented in TCG, which might be complicated for some hosts.

Signature · 2 lines
Aurelien Jarno                          GPG: 1024D/F1BCDB73
[email protected]                 http://www.aurel32.net