diff options
-rw-r--r-- | include/llvm/ADT/APInt.h | 32 | ||||
-rw-r--r-- | unittests/ADT/APIntTest.cpp | 11 |
2 files changed, 35 insertions, 8 deletions
diff --git a/include/llvm/ADT/APInt.h b/include/llvm/ADT/APInt.h index 8f5c72d8a2..85335cff10 100644 --- a/include/llvm/ADT/APInt.h +++ b/include/llvm/ADT/APInt.h @@ -1505,16 +1505,32 @@ public: } /// \returns the nearest log base 2 of this APInt. Ties round up. + /// + /// NOTE: When we have a BitWidth of 1, we define: + /// + /// log2(0) = UINT32_MAX + /// log2(1) = 0 + /// + /// to get around any mathematical concerns resulting from + /// referencing 2 in a space where 2 does no exist. unsigned nearestLogBase2() const { - // This is implemented by taking the normal log 2 of a number and adding 1 - // to it if MSB - 1 is set. - - // We follow the model from logBase2 that logBase2(0) == UINT32_MAX. This - // works since if we have 0, MSB will be 0. Then we subtract one yielding - // UINT32_MAX. Finally extractBit of MSB - 1 will be UINT32_MAX implying - // that we get BitWidth - 1. + // Special case when we have a bitwidth of 1. If VAL is 1, then we + // get 0. If VAL is 0, we get UINT64_MAX which gets truncated to + // UINT32_MAX. + if (BitWidth == 1) + return VAL - 1; + + // Handle the zero case. + if (!getBoolValue()) + return UINT32_MAX; + + // The non-zero case is handled by computing: + // + // nearestLogBase2(x) = logBase2(x) + x[logBase2(x)-1]. + // + // where x[i] is referring to the value of the ith bit of x. unsigned lg = logBase2(); - return lg + unsigned((*this)[std::min(lg - 1, BitWidth - 1)]); + return lg + unsigned((*this)[lg - 1]); } /// \returns the log base 2 of this APInt if its an exact power of two, -1 diff --git a/unittests/ADT/APIntTest.cpp b/unittests/ADT/APIntTest.cpp index 01a30dfd20..ee547db52a 100644 --- a/unittests/ADT/APIntTest.cpp +++ b/unittests/ADT/APIntTest.cpp @@ -665,6 +665,17 @@ TEST(APIntTest, nearestLogBase2) { uint64_t I6[4] = {0x0, 0x0, 0x0, 0x18}; APInt A6(integerPartWidth*4, ArrayRef<integerPart>(I6, 4)); EXPECT_EQ(A6.nearestLogBase2(), A6.ceilLogBase2()); + + // Test BitWidth == 1 special cases. + APInt A7(1, 1); + EXPECT_EQ(A7.nearestLogBase2(), 0ULL); + APInt A8(1, 0); + EXPECT_EQ(A8.nearestLogBase2(), UINT32_MAX); + + // Test the zero case when we have a bit width large enough such + // that the bit width is larger than UINT32_MAX-1. + APInt A9(UINT32_MAX, 0); + EXPECT_EQ(A9.nearestLogBase2(), UINT32_MAX); } } |