Gabriel B. has uploaded this change for review. (
https://gem5-review.googlesource.com/c/public/gem5/+/67670?usp=email )
Change subject: base: Generalize findLsbSet to std::bitset<N>
......................................................................
base: Generalize findLsbSet to std::bitset<N>
Change-Id: I2ec59ab9cda2243666def09e3414d8ef75197d49
---
M src/base/bitfield.hh
1 file changed, 63 insertions(+), 26 deletions(-)
diff --git a/src/base/bitfield.hh b/src/base/bitfield.hh
index 288c5ca..645a77b 100644
--- a/src/base/bitfield.hh
+++ b/src/base/bitfield.hh
@@ -41,9 +41,11 @@
#ifndef __BASE_BITFIELD_HH__
#define __BASE_BITFIELD_HH__
+#include <bitset>
#include <cassert>
#include <cstddef>
#include <cstdint>
+#include <limits>
#include <type_traits>
namespace gem5
@@ -289,38 +291,64 @@
/**
* Returns the bit position of the LSB that is set in the input
+ * That function will either use a builting that exploit a "count trailing
+ * zeros" instruction or use a bit-fidling algorithm explained bellow.
*
* @ingroup api_bitfield
*/
constexpr int
-findLsbSet(uint64_t val)
+findLsbSet(uint64_t val) {
+ if (val == 0) return 64;
+#ifndef __has_builtin
+#define __has_builtin(foo) 0
+#endif
+#if defined(__GNUC__) || \
+ (defined(__clang__) && __has_builtin(__builtin_ctz))
+ if constexpr (sizeof(unsigned long long) == sizeof(val)) {
+ return __builtin_ctzll(val);
+ }
+#endif
+ // Create a mask with trailing zeros flipped to 1, lsbset flipped to 0
and
+ // the rest unchanged. This effectively is equivalent to doing -1.
+ // e.g.: 0101000 - 1 = 0100111
+ auto mask = val - 1;
+ // This will create a mask of ones from lsb set to last bit
+ // e.g.: 0101000 ^ 0100111 = 00001111
+ auto masked = val ^ mask;
+ // Shift that mask to that there is a 1 where there was 0 after the
lsb set
+ // before
+ // e.g.: 00001111 >> 1 = 00000111 (val is 0101000 in the example)
+ auto ones = masked >> 1;
+ // Number of bit set is the lsb set. This operation should be
optimized by
+ // the compiler without unsing intrinsics.
+ return std::bitset<64>(ones).count();
+}
+
+template<size_t N>
+constexpr int
+findLsbSet(std::bitset<N> bs)
{
- int lsb = 0;
- if (!val)
- return sizeof(val) * 8;
- if (!bits(val, 31, 0)) {
- lsb += 32;
- val >>= 32;
+ if constexpr (N <= 64) {
+ return findLsbSet(bs.to_ullong());
+ } else {
+ if (bs.none()) return N;
+ // Mask of ones
+ constexpr std::bitset<N>
mask(std::numeric_limits<uint64_t>::max());
+ // Is the lsb set in the rightmost 64 bits ?
+ auto nextQword{bs & mask};
+ int i{0};
+ while (nextQword.none()) {
+ // If yes, shift by 64 bits and repeat
+ i += 64;
+ bs >>= 64;
+ nextQword = bs & mask;
+ }
+ // If yes, account for the the i 64-bit shifts and add the
remaining
+ // using the 4 bit implementation. Store in intermediate variable
to
+ // ensure valid conversion from ullong to uint64_t.
+ uint64_t remaining{nextQword.to_ullong()};
+ return i + findLsbSet(remaining);
}
- if (!bits(val, 15, 0)) {
- lsb += 16;
- val >>= 16;
- }
- if (!bits(val, 7, 0)) {
- lsb += 8;
- val >>= 8;
- }
- if (!bits(val, 3, 0)) {
- lsb += 4;
- val >>= 4;
- }
- if (!bits(val, 1, 0)) {
- lsb += 2;
- val >>= 2;
- }
- if (!bits(val, 0, 0))
- lsb += 1;
- return lsb;
}
/**
--
To view, visit
https://gem5-review.googlesource.com/c/public/gem5/+/67670?usp=email
To unsubscribe, or for help writing mail filters, visit
https://gem5-review.googlesource.com/settings
Gerrit-Project: public/gem5
Gerrit-Branch: develop
Gerrit-Change-Id: I2ec59ab9cda2243666def09e3414d8ef75197d49
Gerrit-Change-Number: 67670
Gerrit-PatchSet: 1
Gerrit-Owner: Gabriel B. <gabriel.bus...@arteris.com>
Gerrit-MessageType: newchange
_______________________________________________
gem5-dev mailing list -- gem5-dev@gem5.org
To unsubscribe send an email to gem5-dev-le...@gem5.org
