aboutsummaryrefslogtreecommitdiffstats
path: root/include/llvm/Support
diff options
context:
space:
mode:
authorOwen Anderson <resistor@mac.com>2007-03-01 05:41:28 +0000
committerOwen Anderson <resistor@mac.com>2007-03-01 05:41:28 +0000
commit2a934cb6072bb0840b39e899e02ad9dea95b18dc (patch)
treef4f377914ba248494332eaeab39a2e33844336ce /include/llvm/Support
parentaf8fb1984674db462bc6923ed54db0275c78b711 (diff)
downloadexternal_llvm-2a934cb6072bb0840b39e899e02ad9dea95b18dc.zip
external_llvm-2a934cb6072bb0840b39e899e02ad9dea95b18dc.tar.gz
external_llvm-2a934cb6072bb0840b39e899e02ad9dea95b18dc.tar.bz2
Use the GCC built-in for PopulationCount when it's available, and use a faster
algorithm when it's not. This should be particularly noticeable in the 64-bit case. git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@34776 91177308-0d34-0410-b5e6-96231b3b80d8
Diffstat (limited to 'include/llvm/Support')
-rw-r--r--include/llvm/Support/MathExtras.h27
1 files changed, 16 insertions, 11 deletions
diff --git a/include/llvm/Support/MathExtras.h b/include/llvm/Support/MathExtras.h
index f660d48..6ba51d6 100644
--- a/include/llvm/Support/MathExtras.h
+++ b/include/llvm/Support/MathExtras.h
@@ -208,22 +208,27 @@ inline unsigned CountTrailingZeros_64(uint64_t Value) {
/// CountPopulation_32 - this function counts the number of set bits in a value.
/// Ex. CountPopulation(0xF000F000) = 8
/// Returns 0 if the word is zero.
-inline unsigned CountPopulation_32(unsigned Value) {
- unsigned x, t;
- x = Value - ((Value >> 1) & 0x55555555);
- t = ((x >> 2) & 0x33333333);
- x = (x & 0x33333333) + t;
- x = (x + (x >> 4)) & 0x0F0F0F0F;
- x = x + (x << 8);
- x = x + (x << 16);
- return x >> 24;
+inline unsigned CountPopulation_32(uint32_t Value) {
+#if __GNUC__ >= 4
+ return __builtin_popcount(Value);
+#else
+ uint32_t v = v - ((v >> 1) & 0x55555555);
+ v = (v & 0x33333333) + ((v >> 2) & 0x33333333);
+ return ((v + (v >> 4) & 0xF0F0F0F) * 0x1010101) >> 24;
+#endif
}
/// CountPopulation_64 - this function counts the number of set bits in a value,
/// (64 bit edition.)
inline unsigned CountPopulation_64(uint64_t Value) {
- return CountPopulation_32(unsigned(Value >> 32)) +
- CountPopulation_32(unsigned(Value));
+#if __GNUC__ >= 4
+ return __builtin_popcountll(Value);
+#else
+ uint64_t v = Value - ((Value >> 1) & 0x5555555555555555ULL);
+ v = (v & 0x3333333333333333ULL) + ((v >> 2) & 0x3333333333333333ULL);
+ v = (v + (v >> 4)) & 0x0F0F0F0F0F0F0F0FULL;
+ return (uint64_t)(v * 0x0101010101010101ULL) >> 56;
+#endif
}
/// Log2_32 - This function returns the floor log base 2 of the specified value,