target-arm: use clz32() instead of a for loop
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
@@ -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
Quoted 30 lines · Aurelien Jarno
Signed-off-by Aurelien Jarno <[email protected]>---
target-arm/helper.c | 6 ++----1 files changed, 2 insertions(+), 4 deletions(-)target-arm/helper.c +1
-0@@ -7,6 +7,7 @@ #include "gdbstub.h" #include "helpers.h" #include "qemu-common.h" +#include "host-utils.h" static
uint32_tcortexa8_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
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
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
-0int32_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
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.htmlOTOH, 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
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
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()andhelper_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