Gabe Black has uploaded this change for review. (
https://gem5-review.googlesource.com/c/public/gem5/+/26164 )
Change subject: base: Optimize and otherwise fix a couple of functions in
intmath.hh.
......................................................................
base: Optimize and otherwise fix a couple of functions in intmath.hh.
As described in the Jira issue, this replaces the implementation of
isPowerOf2() and power(). It also revamps floorLog2 so that there only
needs to be one implementation and no assumptions about how big certain
types are.
Jira Issue: https://gem5.atlassian.net/browse/GEM5-140
Change-Id: I0ae05aeba1b5882d2a616613b1679e6206b4cbfe
---
M src/base/intmath.hh
1 file changed, 28 insertions(+), 79 deletions(-)
diff --git a/src/base/intmath.hh b/src/base/intmath.hh
index c6ad329..051b4cf 100644
--- a/src/base/intmath.hh
+++ b/src/base/intmath.hh
@@ -30,6 +30,8 @@
#define __BASE_INTMATH_HH__
#include <cassert>
+#include <cstdint>
+#include <type_traits>
#include "base/logging.hh"
#include "base/types.hh"
@@ -37,97 +39,42 @@
inline uint64_t
power(uint32_t n, uint32_t e)
{
- if (e > 20)
- warn("Warning, power() function is quite slow for large
exponents\n");
-
- if (e == 0)
- return 1;
-
- uint64_t result = n;
- uint64_t old_result = 0;
- for (int x = 1; x < e; x++) {
- old_result = result;
- result *= n;
- if (old_result > result)
- warn("power() overflowed!\n");
+ uint64_t result = 1;
+ uint64_t component = n;
+ while (e) {
+ uint64_t last = result;
+ if (e & 0x1)
+ result *= component;
+ warn_if(result < last, "power() overflowed!");
+ e >>= 1;
+ component *= component;
}
return result;
}
-
+template <class T>
inline int
-floorLog2(unsigned x)
+floorLog2(T x)
{
- assert(x > 0);
+ // Make sure x isn't negative.
+ assert(std::is_unsigned<T>::value || x > 0);
+
+ // A guaranteed unsigned version of x.
+ auto ux = (typename std::make_unsigned<T>::type)x;
int y = 0;
+ constexpr auto xs = sizeof(ux);
- if (x & 0xffff0000) { y += 16; x >>= 16; }
- if (x & 0x0000ff00) { y += 8; x >>= 8; }
- if (x & 0x000000f0) { y += 4; x >>= 4; }
- if (x & 0x0000000c) { y += 2; x >>= 2; }
- if (x & 0x00000002) { y += 1; }
+ if (xs >= 8 && (ux & ULL(0xffffffff00000000))) { y += 32; ux >>= 32; }
+ if (xs >= 4 && (ux & ULL(0x00000000ffff0000))) { y += 16; ux >>= 16; }
+ if (xs >= 2 && (ux & ULL(0x000000000000ff00))) { y += 8; ux >>= 8; }
+ if (ux & ULL(0x00000000000000f0)) { y += 4; ux >>= 4; }
+ if (ux & ULL(0x000000000000000c)) { y += 2; ux >>= 2; }
+ if (ux & ULL(0x0000000000000002)) { y += 1; }
return y;
}
-inline int
-floorLog2(unsigned long x)
-{
- assert(x > 0);
-
- int y = 0;
-
-#if defined(__LP64__)
- if (x & ULL(0xffffffff00000000)) { y += 32; x >>= 32; }
-#endif
- if (x & 0xffff0000) { y += 16; x >>= 16; }
- if (x & 0x0000ff00) { y += 8; x >>= 8; }
- if (x & 0x000000f0) { y += 4; x >>= 4; }
- if (x & 0x0000000c) { y += 2; x >>= 2; }
- if (x & 0x00000002) { y += 1; }
-
- return y;
-}
-
-inline int
-floorLog2(unsigned long long x)
-{
- assert(x > 0);
-
- int y = 0;
-
- if (x & ULL(0xffffffff00000000)) { y += 32; x >>= 32; }
- if (x & ULL(0x00000000ffff0000)) { y += 16; x >>= 16; }
- if (x & ULL(0x000000000000ff00)) { y += 8; x >>= 8; }
- if (x & ULL(0x00000000000000f0)) { y += 4; x >>= 4; }
- if (x & ULL(0x000000000000000c)) { y += 2; x >>= 2; }
- if (x & ULL(0x0000000000000002)) { y += 1; }
-
- return y;
-}
-
-inline int
-floorLog2(int x)
-{
- assert(x > 0);
- return floorLog2((unsigned)x);
-}
-
-inline int
-floorLog2(long x)
-{
- assert(x > 0);
- return floorLog2((unsigned long)x);
-}
-
-inline int
-floorLog2(long long x)
-{
- assert(x > 0);
- return floorLog2((unsigned long long)x);
-}
-
template <class T>
inline int
ceilLog2(const T& n)
@@ -143,7 +90,9 @@
inline bool
isPowerOf2(const T& n)
{
- return n != 0 && floorLog2(n) == ceilLog2(n);
+ // If n is non-zero, and subtracting one borrows all the way to the MSB
+ // and flips all bits, then this is a power of 2.
+ return n && !(n & (n - 1));
}
template <class T, class U>
--
To view, visit https://gem5-review.googlesource.com/c/public/gem5/+/26164
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: I0ae05aeba1b5882d2a616613b1679e6206b4cbfe
Gerrit-Change-Number: 26164
Gerrit-PatchSet: 1
Gerrit-Owner: Gabe Black <[email protected]>
Gerrit-MessageType: newchange
_______________________________________________
gem5-dev mailing list
[email protected]
http://m5sim.org/mailman/listinfo/gem5-dev
